A new heuristic algorithm for finding minimum‐cost multicast trees with bounded path delay

This article presents a new heuristic algorithm called DDBMA (Dynamic Delay Bounded Multicast Algorithm) to construct a minimum‐cost multicast tree. The heuristic depends on (1) bounded delay along paths from source nodes to each destination node; (2) minimum cost of the multicast tree; (3) dynamic multicast tree status which is maintained by updating the existing multicast tree when nodes in the network request to join or leave. Copyright © 1999 John Wiley & Sons, Ltd.     

多信道广播组总延误端到端延迟变化路由问题

在高速分组交换环境中,提出了构造多信道广播树,且满足实时交互性应用端到端变化要求的总延误问题.多信道广播路由将寻找从源到包括所有多信道广播终端的一棵有根树.在多媒体应用中,关于路由问题有两种要求:最小总延误和延迟变化.在实践中链路延迟和终端延迟的概念是有区别的.重新定义延迟的概念,也就是端到端的路径延迟定义为截止延迟或界定延迟,延误成员数的延迟定义为松驰延迟.终端的松驰延迟具有的特征是沿着一棵树从源到任何一个终端的累积延迟可以超过松驰延迟的值.确定这样一棵约束树的问题是NP-完全的.由时间的复杂性和动态成员的灵活性,提出了一个有效的启发式算法.     

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     

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.     

Multicast routing and wavelength assignment with delay constraint in WDM networks with sparse wavelength conversions

With the developments in multimedia and other real-time group applications, the question of how to establish multicast trees satisfying Quality-of-Service (QoS) requirements is becoming a very important problem. In this paper, multicast routing and wavelength assignment with delay constraint (MCRWA-DC) in wavelength division multiplexing (WDM) networks with sparse wavelength conversions is studied. We propose a colored multigraph model for the temporarily available wavelengths. Based on this colored multigraph model, two heuristic algorithms are proposed to solve the MCRWA-DC problem. The proposed algorithms have the following advantages:(1) finish multicast routing and wavelength assignment in one step; (2) the total cost of the multicast tree is low; (3) the delay from the source node to any multicast destination node is bounded; and (4) locally minimize the number of wavelength conversions and the number of different wavelengths used to satisfy a multicast request. Simulation results show that the proposed algorithms work well and achieve satisfactory blocking probability.     

Algorithms for precomputing constrained widest paths and multicast trees

We consider the problem of precomputing constrained widest paths and multicast trees in a communication network. Precomputing and storing of the relevant information minimizes the computational overhead required to determine an optimal path when a new connection request arrives. We evaluate algorithms that precompute paths with maximal bandwidth (widest paths), which in addition satisfy given end-to-end delay constraints. We analyze and compare both the worst case and average case performance of the algorithms. We also show how the precomputed paths can be used to provide computationally efficient solutions to the constrained widest multicast tree problem. In this problem, a multicast tree with maximal bandwidth (widest multicast tree) is sought, which in addition satisfies given end-to-end delay constraints for each path on the tree from the source to a multicast destination.     

A distributed algorithm of delay-bounded multicast routing formultimedia applications in wide area networks

Multicast routing is to find a tree which is rooted from a source node and contains all multicast destinations. There are two requirements of multicast routing in many multimedia applications: optimal network cost and bounded delay. The network cost of a tree is defined as the sum of the cost of all links in the tree. The bounded delay of a routing tree refers to the feature that the accumulated delay from the source to any destination along the tree shall not exceed a prespecified bound. This paper presents a distributed heuristic algorithm which generates routing trees having a suboptimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages and convergence time, and flexible in dynamic membership changes. A large amount of simulations have been done to show the network cost of the routing trees generated by our algorithm is similar to, or even better than, other existing algorithms     

支持延时约束的覆盖多播路由协议的研究

研究有度和延时约束的覆盖多播路由问题,提出了一个新的覆盖多播路由协议-延时受限的树协议(DBTP)。该协议采用分布式和树优先的策略,使多播组成员之间能自组织地构建一棵基于源的覆盖多播树。DBTP协议采用了一种新的启发式局部优化算法,通过调节启发因子,能灵活地在延时和代价之间进行折衷。仿真实验表明,无论在静态还是动态节点模型下,选择适当的启发参数,DBTP都能获得较高的节点接纳率。     

ESC: Estimation of selecting core for reducing multicast delay variation under delay constraints

With the spread of multimedia group applications, the construction of multicast trees satisfying the Quality of Service (QoS) requirements becomes a problem of prime importance. A principal factor of these real‐time applications is to optimize the delay‐ and delay variation‐bounded multicast tree (DVBMT) problem. This problem is to satisfy the minimum delay variation and the end‐to‐end delay within an upper bound. The DVBMT problem is known as an NP‐complete problem. The representative algorithms are the DVMA, the DDVCA, and the ECS algorithm. In this paper, we show that the proposed ESC algorithm outperforms the DDVCA and the ECS algorithm. The efficiency of our algorithm is verified through performance evaluation and the enhancement is up to about 19.6% in terms of normalized surcharge for multicast delay variation. The time complexity of our algorithm is O(mn²), which is comparable to the well‐known DDVCA. Copyright © 2010 John Wiley & Sons, Ltd.     

QoS multicast routing with delay constraints

Proliferation of group-based real-time applications, such as online games and video conferencing has motivated research into QoS multicast routing. These types of applications require consideration of both source-to-destination delay (i.e., packet delay from the source to all destinations) and inter-destination delay variation (i.e., the difference in packet delay from the source to different destinations) constraints. In this paper, we formulate a new combined problem for delay partitioning and multicast routing with source-to-destination delay and inter-destination delay variation constraints in a QoS framework, where a delay dependent cost function is associated with each network link. After identifying the problem asnp-complete, we introduce a Genetic Algorithm (ga) based algorithm that computes a source-based multicast tree which satisfies both constraints with near-optimal cost. We compare differentga schemes using different selection operators and find that the combination of Steady Statega and Remainder Stochastic Sampling selection operator works best for our problem. Simulation results also show that ourga heuristic consistently perfornis better than several other simple heuristics.     

有时延及时延差别约束的最小代价组播路由问题

本文把有时延、时延差别约束的组播路由问题提到优化的层次上,提出了有时延、时延差别约束的最小代价组播路由优化问题,并证明此问题是NP－complete问题。继而提出了一种基于动态罚函数法的启发式遗传算法以及解该问题,并分析了算法的复杂度。仿真表明,本文算法是有效的、稳定的。在满足两种约束的情况下,能够使网络代价优化。     

A resource‐tuned QoS multicast routing protocol

This paper presents a novel framework for quality‐of‐service (QoS) multicast routing with resource allocation that represents QoS parameters, jitter delay, and reliability, as functions of adjustable network resources, bandwidth, and buffer, rather than static metrics. The particular functional form of QoS parameters depends on rate‐based service disciplines used in the routers. This allows intelligent tuning of QoS parameters as functions of allocated resources during the multicast tree search process, rather than decoupling the tree search from resource allocation. The proposed framework minimizes the network resource utilization while keeping jitter delay, reliability, and bandwidth bounded. This definition makes the proposed QoS multicast routing with resource allocation problem more general than the classical minimum Steiner tree problem. As an application of our general framework, we formulate the QoS multicast routing with resource allocation problem for a network consisting of generalized processor sharing nodes as a mixed‐integer quadratic program and find the optimal multicast tree with allocated resources to satisfy the QoS constraints. We then present a polynomial‐time greedy heuristic for the QoS multicast routing with resource allocation problem and compare its performance with the optimal solution of the mixed‐integer quadratic program. The simulation results reveal that the proposed heuristic finds near‐optimal QoS multicast trees along with important insights into the interdependency of QoS parameters and resources.     

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.     

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.     

时延受限低代价的一种组播路由动态算法

提出了一种适合目的节点动态加入的、时延受限低代价多播路由的启发式算法DLHMA算法。该算法基于MPH算法的基本思想进行扩展,在满足时延限制条件和多播树代价增加最小的基础上,逐步将目的节点添加到多播树上。最后,证明了算法的正确性,分析了算法的动态性,并进行了仿真实验。结果表明,该算法可以实现新加目的节点的动态加入,并保证所获得多播树的低代价。     

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.     

一种时延和时延抖动受约束的启发式多播路由算法

多播路由算法在组播应用中是至关重要的,对视频会议等交互式实时组播业务来说,不仅要考虑时延约束,而且要考虑时延抖动约束。本文提出了一种基于最短时延路径的时延和时延抖动约束的启发式算法,仿真结果表明该算法复杂度较低,而且性能也较好,在算法复杂度和性能之间达到了很好的折中。     

Multicast routing, load balancing, and wavelength assignment ontree of rings

There are two steps to establish a multicast connection in WDM networks: routing and wavelength assignment. The shortest path tree (SPT) and minimum spanning tree (MST) are the two widely used multicast routing methods. The SPT method minimizes the delay from the source to every destination along a routing tree, and the MST method is often used to minimize the network cost of the tree. Load balancing is an important objective in multicast routing, which minimizes the maximal link load in the system. The objective of wavelength assignment is to minimize the number of wavelengths used in the system. This paper analyzes the performance of the shortest path tree (SPT) and minimum spanning tree (MST) methods in the tree of ring networks, regarding the performance criteria such as the delay and network cost of the generated routing trees, load balancing, and the number of wavelengths required in the system. We prove that SPT and MST methods can not only produce routing trees with low network costs and short delays, but also have good competitive ratios for the load balancing problem (LBP) and wavelength assignment problem (WAP), respectively     

Restricted dynamic Steiner trees for scalable multicast in datagramnetworks

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree     

A Distributed Routing Method for Dynamic Multicasting

Single point, sender based control does not scale well for multicast delivery. For applications, such as group video or teleconferencing a low total cost multicast tree is required. In this article we present a destination driven algorithm to minimize the total tree cost of multicast tree in a dynamic situation for the whole session duration. In this heuristic approach we considered the staying duration of participants are available at the time of joining. The performance of our algorithm is analyzed through extensive simulation and evaluated against several other existing dynamic multicast routing and also against one well known near optimum heuristic algorithm used for solving Steiner tree problem. We have further tested our algorithm using erroneous information given by the joining participants. Simulation results show that its performance does not degrade that much even when the range of error is considerably high, which proves the robustness of our algorithm.