Multicast routing for multimedia communication

The authors present heuristics for multicast tree construction for communication that depends on: bounded end-to-end delay along the paths from source to each destination and minimum cost of the multicast tree, where edge cost and edge delay can be independent metrics. The problem of computing such a constrained multicast tree is NP-complete. It is shown that the heuristics demonstrate good average case behavior in terms of cost, as determined by simulations on a large number of graphs     

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.     

On minimizing end-to-end delay with optimal traffic partitioning

Multipath transport provides higher usable bandwidth for a session. It has also been shown to provide load balancing and error resilience for end-to-end multimedia sessions. Two key issues in the use of multiple paths are 1) how to minimize the end-to-end delay, which now includes the delay along the paths and the resequencing delay at the receiver, and 2) how to select paths. This paper presents an analytical framework for the optimal partitioning of real-time multimedia traffic that minimizes the total end-to-end delay. Specifically, it formulates optimal traffic partitioning as a constrained optimization problem using deterministic network calculus and derives its closed-form solution. Compared with previous work, the proposed scheme is simpler to implement and enforce. This analysis also greatly simplifies the solution to the path selection problem as compared to previous efforts. Analytical results show that for a given flow and a set of paths, a minimal subset can be chosen to achieve the minimum end-to-end delay with O(N) time, where N is the number of available paths. The selected path set is optimal in the sense that adding any rejected path to the set will only increase the end-to-end delay.     

适于低轨卫星IP网络的特定源组播算法

为了解决低轨卫星IP网络中现有特定源组播算法的信道资源浪费问题,本文提出了一套新的特定源组播算法,即基于核心群的特定源组播算法(CSSM)和加权的CSSM算法(w-CSSM).CSSM算法以源节点作为初始核心群,通过核心群和剩余组成员的最短路径方法逐步扩展直至整棵组播树构建完成,所得的树代价最小,从而大大提高了网络的带宽利用率和传输效率.在w-CSSM算法中,加权因子可以自适应调整以适度增大树代价、降低端到端传播时延,以支持某些有严格端到端时延要求的实时组播业务.通过与低轨卫星IP网络中典型特定源组播算法MRA的仿真比较,可以看出CSSM和w-CSSM算法的树代价性能比MRA有较大改善,不过端到端传播时延略高.     

Two algorithms for multi‐constrained optimal multicast routing

Multimedia applications, such as video‐conferencing and video‐on‐demand, often require quality of service (QoS) guarantees from the network, typically in the form of minimum bandwidth, maximum delay, jitter and packet loss constraints, among others. The problem of multicast routing subject to various forms of QoS constraints has been studied extensively. However, most previous efforts have focused on special situations where a single or a pair of constraints is considered. In general, routing under multiple constraints, even in the unicast case is an NP‐complete problem. We present in this paper two practical and efficient algorithms, called multi‐constrained QoS dependent multicast routing (M_QDMR) and (multicasting routing with multi‐constrained optimal path selection (M_MCOP)), for QoS‐based multicast routing under multiple constraints with cost optimization. We provide proof in the paper that our algorithms are correct. Furthermore, through extensive simulations, we illustrate the effectiveness and efficiency of our proposals and demonstrate their significant performance improvement in creating multicast trees with lower cost and higher success probability. Copyright © 2003 John Wiley & Sons, Ltd.     

Reliability constrained routing in QoS networks

The issue of handling network failures is becoming increasingly important. In this paper, we address the problem of constrained routing by treating reliability as one of the QoS requirements. The problem is to create a feasible path from a given node to the destination such that the bandwidth and reliability requirements of the path are satisfied and the cost of the path is minimized (Reliability Constrained Least Cost Routing Problem). To solve the problem, we propose an approach which employs a novel concept, called partial protection, wherein backup paths are created for a selected set of domains in the network so as to meet the reliability constraints. The Partial Protection Approach (PPA) has two steps: Primary Path Creation and Backup Path Creation if necessary. To implement PPA, we propose three scalable two-pass resource reservation schemes, viz., Conservative, Optimistic, and Hybrid schemes. These schemes differ depending on whether the backup paths are created during the forward pass, reverse pass, or both. We evaluate the performance of the proposed schemes for dynamic multicast groups with different bandwidth and reliability requirements using average call acceptance rate and average tree cost as performance metrics. Our studies show that group dynamics and reliability requirements have significant impact on the performance of the schemes.     

Multicast routing with end-to-end delay and delay variationconstraints

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session     

A heuristic multicast algorithm to support QoS group communications in heterogeneous network

This paper examines the problem of quality-of-service group communications in a heterogeneous network, which consists of multiple mobile ad hoc networks attached to the backbone Internet. A heuristic multicast algorithm named delay and delay variation multicast algorithm (DDVMA) is proposed. DDVMA is designed for solving the delay- and delay-variation-bounded multicast tree problem, which has been proved to be NP-complete. It can find a multicast tree satisfying the multicast end-to-end delay constraint and minimizing the multicast delay variation. Two concepts, which can help the DDVMA achieve better performance in terms of multicast delay variation than the delay and delay variation constraint algorithm that is known to be the most efficient so far, are proposed, namely, 1) the proprietary second shortest path and 2) the partially proprietary second shortest path. An analysis is given to show the correctness of DDVMA, and simulations are conducted to demonstrate the performance improvement of DDVMA in terms of multicast delay variation. It is also shown that the strategy employed by DDVMA is also applicable to handling the mobility of mobile hosts in a heterogeneous network.     

基于QoS的动态组播路由算法

在分析了网络中基于QoS的组播路由问题的基础上,本文提出了一种新的动态算法,并进行了实验和分析,文中构造的路由方案成功地解决了当网络中存在多个组播及组播节点动态变化情况下的QoS路由选择问题,此方案不仅保证了带宽,端到端延时和延时抖动,优化了路由树的代价,而且有效地控制了算法的复杂性并可适用于大规模的网络中。     

Ad Hoc网络中基于粒子群优化的QoS多播路由研究

针对Ad Hoc网络中带QoS约束的多播路由问题，提出了一种新的结合MAODV多播路由发现方法和粒．子群优化算法的QoS多播路由发现算法。仿真试验显示该算法较好地改进了端到端传输的代价、延时和带宽利用率，能够找到一棵消耗趋于最小、状态稳定的多播路由树。     

Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing

The advent of various real-time multimedia applications in high-speed networks creates a need for quality of service (QoS) based multicast routing. The Steiner tree problem, is a well-known NP-complete problem, provides the mathematical structure behind multicast communications. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. In this paper, we propose various algorithms to solve the bandwidth-delay-constrained least-cost multicast routing problem based on Tabu Search (TS), addressing issues of the selected initial solution and move type as two major building blocks in short-term memory version of Tabu Search and longer-term memory with associated intensification and diversification strategies as advanced Tabu Search techniques. We evaluate the performance and efficiency of the proposed TS-based algorithms in comparison with other existing TS-based algorithms and heuristics on a variety of random generated networks with regard to total tree cost. Finally we identify the most efficient algorithm uncovered by our testing.     

基于克隆选择的QoS组播路由优化

衡量QoS组播路由主要性能指标有延时,代价,带宽等,本文所提出的基于遗传算法的多约束QoS组播路由优化算法.引入了一个综合性能指标Q适应度函数,对延时、带宽、代价这3个性能指标进行权衡.以减小组播树的代价和延时,增大带宽,提高组播的服务质量.并对解决传统算法对于存在两组及以上的组播树,他们的代价都是最优的,延时和带宽都满足受限条件时无法选择的问题十分有效的.     

Multipath routing for video delivery over bandwidth-limited networks

The delivery of quality video service often requires high bandwidth with low delay or cost in network transmission. Current routing protocols such as those used in the Internet are mainly based on the single-path approach (e.g., the shortest-path routing). This approach cannot meet the end-to-end bandwidth requirement when the video is streamed over bandwidth-limited networks. In order to overcome this limitation, we propose multipath routing, where the video takes multiple paths to reach its destination(s), thereby increasing the aggregate throughput. We consider both unicast (point-to-point) and multicast scenarios. For unicast, we present an efficient multipath heuristic (of complexity O(|V|/sup 3/)), which achieves high bandwidth with low delay. Given a set of path lengths, we then present and prove a simple data scheduling algorithm as implemented at the server, which achieves the theoretical minimum end-to-end delay. For a network with unit-capacity links, the algorithm, when combined with disjoint-path routing, offers an exact and efficient solution to meet a bandwidth requirement with minimum delay. For multicast, we study the construction of multiple trees for layered video to satisfy the user bandwidth requirements. We propose two efficient heuristics on how such trees can be constructed so as to minimize the cost of their aggregation subject to a delay constraint.     

Ad Hoc网络中一种基于QoS的分布式多播路由算法

通过分析Ad Hoe网络的特点及基于QoS的多播路由问题，提出了一种新的分布式多播路由算法。实验和分析的结果表明，文中构造的路由方案成功地解决了Ad Hoe网中基于QoS的多播路由问题。当Ad Hoe网络的拓扑结构改变不太快时，本文提出的路由方案不仅满足了实时业务对网络带宽和端到端延时的要求，优化了路由树的代价，而且有效地控制了算法的复杂性并可适用于大规模的网络中。     

QoS路由的多路径算法

本文分析了预约网络中采用多路径路由传送数据以保证应用的带宽要求、和/或端到端时延限制条件.文中提出的路由方案综合了单路径和多路径路由的优点:通过多路径路由以降低呼叫阻塞率,同时侧重单路径路由以降低协议开销.在考察网络中的四个一般性问题基础上,提出了启发式算法.     

一种改进的多播路由算法

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗。DDSP(Destination-Driven Shortest Path)算法是一个性能较好,计算效率较高的低代价最短路径树算法,在该算法基础上,通过改进结点的搜索过程,提出一种改进的快速低代价最短路径树算法。由算法分析和实验比较得出,改进算法的计算效率高于DDSP算法,且算法构造的最短路径树的性能也优于DDSP算法构造的树．     

A new delay‐constrained algorithm for multicast routing tree construction

New multimedia applications provide guaranteed end‐to‐end quality of service (QoS) and have stringent constraints on delay, delay‐jitter, bandwidth, cost, etc. The main task of QoS routing is to find a route in the network, with sufficient resources to satisfy the constraints. Most multicast routing algorithms are not fast enough for large‐scale networks and where the source node uses global cost information to construct a multicast tree. We propose a fast and simple heuristic algorithm (EPDT) for delay‐constrained routing problem for multicast tree construction. This algorithm uses a greedy strategy based on shortest‐path and minimal spanning trees. It combines the minimum cost and the minimum radius objectives by combining respectively optimal Prim's and Dijkstra's algorithms. It biases routes through destinations. Besides, it uses cost information only from neighbouring nodes as it proceeds, which makes it more practical, from an implementation point of view. Copyright © 2004 John Wiley & Sons, Ltd.     

QoS multicast routing by using multiple paths/trees in wireless ad hoc networks

In this paper, we investigate the issues of QoS multicast routing in wireless ad hoc networks. Due to limited bandwidth of a wireless node, a QoS multicast call could often be blocked if there does not exist a single multicast tree that has the requested bandwidth, even though there is enough bandwidth in the system to support the call. In this paper, we propose a new multicast routing scheme by using multiple paths or multiple trees to meet the bandwidth requirement of a call. Three multicast routing strategies are studied, SPT (shortest path tree) based multiple-paths (SPTM), least cost tree based multiple-paths (LCTM) and multiple least cost trees (MLCT). The final routing tree(s) can meet the user’s QoS requirements such that the delay from the source to any destination node shall not exceed the required bound and the aggregate bandwidth of the paths or trees shall meet the bandwidth requirement of the call. Extensive simulations have been conducted to evaluate the performance of our three multicast routing strategies. The simulation results show that the new scheme improves the call success ratio and makes a better use of network resources.     

Network tomography from measured end-to-end delay covariance

End-to-end measurement is a common tool for network performance diagnosis, primarily because it can reflect user experience and typically requires minimal support from intervening network elements. However, pinpointing the site of performance degradation from end-to-end measurements is a challenging problem. We show how end-to-end delay measurements of multicast traffic can be used to infer the under-lying logical multicast tree and the packet delay variance on each of its links. The method does not depend on cooperation from intervening network elements; multicast probing is bandwidth efficient. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the approach through simulations, and analyze its failure modes and their probabilities.     

Multicast-based inference of network-internal loss characteristics

Robust measurements of network dynamics are increasingly important to the design and operation of large internetworks like the Internet. However, administrative diversity makes it impractical to monitor every link on an end-to-end path. At the same time, it is difficult to determine the performance characteristics of individual links from end-to-end measurements of unicast traffic. In this paper, we introduce the use of end-to-end measurements of multicast traffic to infer network-internal characteristics. The bandwidth efficiency of multicast traffic makes it suitable for large-scale measurements of both end-to-end and internal network dynamics. We develop a maximum-likelihood estimator for loss rates on internal links based on losses observed by multicast receivers. It exploits the inherent correlation between such observations to infer the performance of paths between branch points in the tree spanning a multicast source and its receivers. We derive its rate of convergence as the number of measurements increases, and we establish robustness with respect to certain generalizations of the underlying model. We validate these techniques through simulation and discuss possible extensions and applications of this work