Markov-chain modeling for multicast signaling delay analysis

Feedback signaling plays a key role in flow control because the traffic source relies on the signaling information to make correct and timely flow-control decisions. However, it is difficult to design an efficient signaling algorithm since a signaling message can tolerate neither error nor latency. Multicast flow-control signaling imposes two additional challenges: scalability and feedback synchronization. Previous research on multicast signaling has mainly focused on the development of algorithms without analyzing their delay performance. To remedy this deficiency, we have previously developed a binary-tree model and an independent-marking statistical model for multicast-signaling delay analysis. This paper considers a general scenario where the congestion markings at different links are dependent - a more accurate but complex case. Specifically, we develop a Markov-chain model defined by the link-marking state on each path in the multicast tree. The Markov chain can not only capture link-marking dependencies, but also yield a tractable analytical model. We also develop a Markov-chain dependency-degree model to evaluate all possible Markov-chain dependency degrees without any prior knowledge of them. Using the above two models, we derive the general probability distributions of each path becoming the multicast-tree bottleneck. Also derived are the first and second moments of multicast signaling delays. The proposed Markov chain is also shown to asymptotically reach an equilibrium, and its limiting distribution converges to the marginal link-marking probabilities when the Markov chain is irreducible. Applying the two models, we analyze and contrast the delay scalability of two representative multicast signaling protocols: Soft-Synchronization Protocol (SSP) and Hop-By-Hop (HBH) algorithms.     

Optimal deterministic timeouts for reliable scalable multicast

Reliable multicast protocols suffer from the problem of feedback implosion. To avoid this problem, the number of receivers sending feedback in case of loss must be small. However, losses experienced by different receivers are strongly correlated, since receivers share common resources in the multicast tree. One approach to feedback implosion avoidance relies on delaying feedback at the receivers. We present deterministic timeouts for reliable multicast (DTRM), a distributed algorithm to compute optimal deterministic timeouts for each receiver in a multicast tree as a function of the tree topology and the sender-to-receiver round-trip delays. DTRM has several desirable properties. First, feedback implosion is provably avoided for a single loss anywhere in the tree, provided delay jitter is bounded. Second, the computation of the timeouts can be entirely distributed; receivers and intermediate nodes only rely on local topology information. Third, the timeouts computed by DTRM are optimal with respect to the maximum response time     

Source-adaptive multilayered multicast algorithms for real-timevideo distribution

Layered transmission of data is often recommended as a solution to the problem of varying bandwidth constraints in multicast video applications. Multilayered encoding, however, is not sufficient to provide high video quality and high network utilization, since bandwidth constraints frequently change over time. Adaptive techniques capable of adjusting the rates of video layers are required to maximize video quality and network utilization. We define a class of algorithms known as source-adaptive multilayered multicast (SAMM) algorithms. In SAMM algorithms, the source uses congestion feedback to adjust the number of generated layers and the bit rate of each layer. We contrast two specific SAMM algorithms: an end-to-end algorithm, in which only end systems monitor available bandwidth and report the amount of available bandwidth to the source, and a network-based algorithm, in which intermediate nodes also monitor and report available bandwidth. Using simulations that incorporate multilayered video codecs, we demonstrate that SAMM algorithms can exhibit better scalability and responsiveness to congestion than algorithms that are not source-adaptive. We also study the performance trade-offs between end-to-end and network-based SAMM algorithms     

Multicast-based inference of network-internal delay distributions

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.     

Minimizing the Number of Multicast Transmissions in Single-Hop WDM Networks

The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop wavelength division multiplexing (WDM) networks is studied in this paper. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. Extensive simulations are performed to compare the performance of the proposed heuristic algorithm with two other multicast scheduling algorithms, namely, the greedy and no-partition scheduling algorithms. The greedy algorithm schedules as many destination nodes as possible in the earliest data slot. The no-partition algorithm schedules the destination nodes of a multicast packet to receive the packet in the same data slot without partitioning the multicast transmission into multiple unicast or multicast transmissions. Our simulation results show that (i) an algorithm which partitions a multicast transmission into multiple unicast or multicast transmissions may not always produce lower mean packet delay than the no-partition algorithm when the number of data channels in the system is limited and (ii) the proposed heuristic algorithm always produces lower mean packet delay than the greedy and the no-partition algorithms because this algorithm not only partitions a multicast transmission into multiple unicast or multicast transmissions to keep the packet delay low but also reduces the number of transmissions to conserve resources.     

Internet Multicasting of IPTV With Essentially-Zero Delay Jitter

A technology for multicasting packetized multimedia streams such as IPTV over the Internet backbone is proposed and explored through extensive simulations. An RSVP or DiffServ algorithm is used to reserve resources (i.e., bandwidth and buffer space) in each packet-switched IP router in an IP multicast tree. Each IP router uses an Input-Queued (IQ) switch architecture with unity speedup. A recently proposed low-jitter scheduling algorithm is used to pre-compute a deterministic transmission schedule for each IP router. The IPTV traffic will be delivered through the multicast tree in a deterministic manner, with bounds on the maximum delay and jitter of each packet (or cell). A playback buffer is used at each destination to filter out residual network jitter and deliver a very low-jitter video stream to each end-user. Detailed simulations of an IPTV distribution network, multicasting 75 high-definition video streams over a fully-saturated IP backbone are presented. The simulations represent the transmission of 129 billion cells of real video data and where performed on a 160-node cluster computing system. In the steady-state, each IP router buffers approx. 2 cells (128 bytes) of video data per multicast output-port. The observed delay jitter is zero when a playback buffer of 15 milliseconds is used. All simulation parameters are presented.      

An ant colony optimisation algorithm for aggregated multicast based on minimum grouping model

The tree‐based delivery structure of the traditional Internet protocol multicast requires each on‐tree router to maintain a forwarding state for a group. This leads to a state scalability problem when large numbers of concurrent groups exist in a network. To address this state scalability problem, a novel scheme called aggregated multicast has recently been proposed, in which multiple groups are forced to share one delivery tree. In this paper, we define the aggregated multicast problem based on the minimum grouping model, and propose an ant colony optimisation algorithm. The relative fullness of the tree is defined according to the characteristics of the minimum grouping problem and is introduced as an important component in identifying the aggregation fitness function between two multicast groups. New pheromone update rules are designed based on the aggregation fitness function. To improve the convergence time of the algorithm, we use the changes (brought by each group) in the relative fullness of the current tree as the selection heuristic information. The impact of the relative fullness of the tree is analysed using the hypothesis test, and simulation results indicate that introducing relative fullness to the fitness function can significantly improve the optimisation performance of the algorithm. Compared with other heuristic algorithms, our algorithm has better optimisation performance and is more suitable for scenarios with larger bandwidth waste rates. Copyright © 2011 John Wiley & Sons, Ltd.     

Directional core selection approach and dynamic tree reorganization for delay and delay variation multicast routing

Multicast communication constrained by end‐to‐end and interdestination delay variation is known as delay and delay variation–bounded multicast. These constraints are salient for real‐time multicast communications. In this paper, we propose a directional core selection algorithm for core selection and delay variation–bounded multicast tree generation. Another algorithm, based on k‐shortest paths, is proposed to further decrease the interdestination delay variation of the trees generated by directional core selection. We also propose the dynamic version of both algorithms that respond to dynamic join and leave requests to the ongoing multicast session by reorganizing the tree and avoiding session disruption. Simulations show that the proposed algorithms surpass existing algorithms in end‐to‐end delay, interdestination delay variation, execution time, and failure probability.     

Forwarding state scalability for multicast provisioning in IP networks

Forwarding state scalability is one of the critical issues that delay the multicast deployment in IP networks. With traditional multicast routing protocols, a forwarding tree is built for each multicast session, and each router is required to maintain a forwarding entry for each multicast session whose distribution tree passes through the router. This poses the multicast forwarding state scalability issue when the number of concurrent multicast sessions is very large. We first present a survey of existing work addressing this scalability issue for providing scalable IP multicast. Then we extend an existing multicast routing protocol, Multicast Extension to OSPF (MOSPF), to scale well with respect to the number of concurrent multicast sessions by introducing tunnel support. This extension aims to reduce the protocol overhead associated with MOSPF. Simulation results show that the extension can significantly reduce multicast forwarding state and computational overhead at routers without affecting the per-destination shortest path characteristic of a resulting tree or introducing extra control overhead.     

Resource Allocation in Multi-channel Multi-user Relay System with Fairness Constraints

In this paper, we derive optimal joint power allocation, subchannel pairing and scheduling strategies in multiple orthogonal channels multiple users wireless networks in the presence of a single regenerative relay node. Two models with users’ data rate request (fairness) constraint in different time domains are considered. The first one is called deterministic model in which each user’s data rate request has to be satisfied in each time slot t (named short term fairness constraint) and the second one is called stochastic model in which users have average data rate request (named long term fairness). In these two models the optimization problems of maximizing system capacity with total transmit power constraint and fairness constraint are formulated. The Lagrangian dual method is used to derive the optimal solution for deterministic model and in the stochastic model stochastic approximation and dual method are employed to find out the optimal algorithm. Both algorithms have polynomial times complexity, which is reduced significantly compared with the Exhaustive Search Method (ESM). Since Lagrangian dual method is utilized in both schemes, the dual gap is also analyzed. Furthermore, through the analysis and simulation, we see that the optimal resource allocation algorithm in stochastic model has better performance than that in the deterministic model for its ability to exploit temporal diversity.     

网络拓扑未知环境下确定性网络编码数据传输

针对网络拓扑未知且宿点具有至源点的反馈路径的单源组播问题,提出了确定性网络编码数据传输的编码构造方法.把组播连接过程分为试播与数据传输两个阶段,在试播阶段,源点作为中心控制节点,采用随机线性网络编码策略反复组播试验包至网络,宿点反馈信息至源点,分别测试出组播容量和各信道的编码向量.在数据传输阶段,利用试播阶段获得的参数,采用确定性网络编码数据传输策略传输数据.理论分析表明了方法的可行性,仿真测试结果表明了方法的有效性.     

Multi-Constrained Dynamic QoS Multicast Routing Design Using Ant Colony System

1IntroductionThe objective of Dynamic QoS Multicast Routing(DQMR) is to find the opti mal routing trees in the fu-ture real-ti me communication network, where informa-tion or messages are sent fromthe source nodeto all des-tination nodes , while meeting all QoS requirements forevery admitted connection and achieving global efficien-cy in resource utilization. Different applications haverather diverse QoS constraints on bandwidth, delay,delayjitter and so on. Multiple constraints often mak…     

Traffic engineering in a multipoint-to-point network

The need to guarantee quality-of-service (QoS) to multimedia applications leads to a tight integration between the routing and forwarding functions in the Internet. multiprotocol label switching tries to provide a global solution for this integration. In this context, multipoint-to-point (m2p) networks appear as a key architecture since they provide a cheaper way to connect edge nodes than point-to-point connections. M2p networks have been mainly studied for their load balancing ability. In this paper, we go a step further: we propose and evaluate a traffic management scheme that provides deterministic QoS guarantees for multimedia sources in an m2p network. We first derive an accurate upper bound on the end-to-end delay in an m2p architecture based on the concept of additivity. Broadly speaking, an m2p network is additive if the maximum end-to-end delay is equal to the sum of local maximum delays. We then introduce two admission control algorithms for additive networks: a centralized algorithm and a distributed algorithm and discuss their complexity and their scalability     

ARIES: a rearrangeable inexpensive edge-based on-line Steineralgorithm

Many future applications of computer networks such as distance education, remote collaboration, and teleconferencing will rely on the ability of the network to provide multicast services. We propose and evaluate ARIES, a heuristic for updating multicast trees dynamically in large point-to-point networks. The algorithm is based on monitoring the accumulated damage to the multicast tree within local regions or the tree as nodes are added and deleted and triggering a rearrangement when the number of changes within a connected subtree crosses a set threshold. We derive an analytical upper bound on the competitiveness of the algorithm. We also present simulation results to compare the average-case performance of the algorithm with two other known algorithms for the dynamic multicast problem, GREEDY, and edge-bounded algorithm (EBA). Our results show that ARIES provides the best balance among competitiveness, computational effort, and changes in the multicast tree after each update     

Distributed multicast routing for delay-sensitive applications

A distributed multicast algorithm for constructing minimum cost multicast trees with delay constraints is proposed. The proposed algorithm can always construct a delay-constrained multicast tree, if one exists, and exhibits superior tree cost performance compared to existing algorithms     

基于可用带宽满足时延和时延差别 约束的实时多播路由算法

实时多播路由中具有可加性的代价(Cost)不能确切反映网络本质特性,尤其不能反映路径带宽的凹性(Concave).已有基于代价的算法不能很好适应多播应用,需要新的模型和算法.本文采用可用带宽代替代价作为主要度量,并满足实时多播中二个重要约束度量:时延和时延差别.同时基于此三个度量,本文提出二种新的具有多项式复杂性的实时多播路由算法并比较其性能.新算法通过分析得到每路径时延和二约束之间的关系,有效降低涉及时延和时延差别此类问题的复杂性.新算法采用度量反映实时多播本质特性而具有实际推广性.     

TCP-Peachtree: a multicast transport protocol for satellite IP networks

In this paper, a reliable multicast transport protocol TCP-Peachtree is proposed for satellite Internet protocol (IP) networks. In addition to the acknowledgment implosion and scalability problems in terrestrial wirelined networks, satellite multicasting has additional problems, i.e., different multicast topology, different type of congestion control problems, and low bandwidth feedback link. In TCP-Peachtree, the modified B+ tree logical hierarchical structure is used to form dynamic multicast groups. Local error recovery and acknowledgment (ACK) aggregations are performed within each subgroup and also via logical subgroups. In order to avoid the overall performance degradation caused by some worst receivers, a local relay scheme is designed. Two new algorithms, jump start and quick recovery, which are based on the usage of a type of low-priority segments called NIL segments, are proposed for congestion control. NIL segments are used to probe the availability of network resources and also for error recovery. The delayed selective acknowledgment (SACK) scheme is adopted to address the bandwidth asymmetry problems and a hold state is developed to address persistent fades. The simulation results show that the congestion control algorithms of TCP-Peachtree outperform the TCP-NewReno when combined with our hierarchical groups and improve the throughput performance during rain fades. It is also shown that TCP-Peachtree achieves fairness and is very highly scalability.     

Scheduling reserved traffic in input-queued switches: new delay bounds via probabilistic techniques

We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known, and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem, therefore, reduces to the problem of constructing a schedule for these permutation matrices. We derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm, we first place tokens randomly in continuous time for each permutation matrix. If the nth token that appears corresponds to permutation matrix M/sub k/, then we schedule matrix M/sub k/ in the nth time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms, we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang et al. (see Proc. IEEE IWQoS, London, U.K., 1999 and Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar 2000).     

Scalable flow control for multicast ABR services in ATM networks

We propose a flow-control scheme for multicast ABR services in ATM networks. At the heart of the proposed scheme is an optimal second-order rate control algorithm, called the α-control, designed to deal with the variation in RM-cell round-trip time (RTT) resulting from dynamic drift of the bottleneck in a multicast tree. Applying two-dimensional rate control, the proposed scheme makes the rate process converge to the available bandwidth of the connection's most congested link sensed by the traffic source. It also confines the buffer occupancy to a target regime bounded by a finite buffer capacity as the system enters the equilibrium state. It works well irrespective of the topology of the multicast tree. Using the fluid analysis, we model the proposed scheme and analyze the system dynamics for multicast ABR traffic. We study the convergence properties and derive the optimal-control conditions for the α-control. The analytical results show that the scheme is stable and efficient in the sense that both the source rate and bottleneck queue length rapidly converge to a small neighborhood of the designated operating point. We present simulation results which verify the analytical observations. The simulation experiments also demonstrate the superiority of the proposed scheme to the other schemes in dealing with RM-cell RTT and link-bandwidth variations, achieving fairness in both buffer and bandwidth occupancies, and enhancing average throughput     

A media access and feedback protocol for reliable multicast over wireless channel

A link level reliable multicast requires a channel access protocol to resolve the collision of feedback messages sent by multicast data receivers. Several deterministic media access control protocols have been proposed to attain high reliability, but with large delay. Besides, there are also protocols which can only give probabilistic guarantee about reliability, but have the least delay. In this paper, we propose a virtual token-based channel access and feedback protocol (VTCAF) for link level reliable multicasting. The VTCAF protocol introduces a virtual (implicit) token passing mechanism based on carrier sensing to avoid the collision between feedback messages. The delay performance is improved in VTCAF protocol by reducing the number of feedback messages. Besides, the VTCAF protocol is parametric in nature and can easily trade off reliability with the delay as per the requirement of the underlying application. Such a cross layer design approach would be useful for a variety of multicast applications which require reliable communication with different levels of reliability and delay performance. We have analyzed our protocol to evaluate various performance parameters at different packet loss rate and compared its performance with those of others. Our protocol has also been simulated using Castalia network simulator to evaluate the same performance parameters. Simulation and analytical results together show that the VTCAF protocol is able to considerably reduce average access delay while ensuring very high reliability at the same time.