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

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

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

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

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.     

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

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

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的动态组播路由算法

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

Algorithms for delay constrained group multicast routing

Multicast routing allows network sources to use network resources efficiently by sending only a single copy of data to all group members. In the delay constrained group multicast routing problem (DCGMRP), every group member is also a source, and has an individual minimal delay and bandwidth requirement. The routing algorithm must, for each member of the group, construct a source‐based routing tree spanning all the other member nodes without exceeding the capacities of the traversed links, while satisfying the stated delay constraints. Previous work adopted the direct, intuitive approach by first creating a source‐based multicast tree independently for each member node, and then iteratively locating network links whose capacity constraint are violated and eliminating the violation by rerouting the trees. In this paper, we investigate a number of efficient and effective algorithms, DCGM _ IA ⁺, DCGM _ GR and DCGM _ CP , for solving DCGMRP and compare their performance with previous proposals. Through extensive experiments, our proposals are shown to outperform previous algorithms in constructing group multicast trees with low costs and high success ratios. Copyright © 2005 John Wiley & Sons, Ltd.     

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

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

基于遗传算法的时延受限代价最小组播路由选择方法

目前多媒体业务的涌现对网络提出了更高的要求。希望既能满足实时性，又能够高效地利用网络资源。本文提出了一种基于遗传算法的组播路由选择方法，该方法在满足时延限制条件的基础上寻找代价最小的组播树。实验表明，该算法收敛速度快，可靠性高，能够满足多媒体网络对实时性的要求。     

无线mesh网中最小编码代价低时延多播路由

提出了一种无线mesh网中最小网络编码代价低时延多播路由协议(MNCLDMR, minimal network coding and low delay multicast routing)。MNCLDMR的目标是选择合适的网络编码节点,最小化网络编码代价,降低网络时延。MNCLDMR主要思想是引入拓扑关键节点和网络编码关键节点的概念,以下一跳的节点是否是网络编码关键节点或拓扑关键节点作为路由判据,采用MNCLD算法构造多播树。仿真结果表明,MNCLDMR可以达到预定目标,合理形成网络编码机会,能实现最小网络编码代价低时延多播路由。     

Tree-based differential evolution algorithm for QoS multicast routing

Differential evolution(DE)algorithm has attracted more and more attention due to its fast optimization performance and good stability.When DE algorithm is applied into multi-constrained multicast routing optimization problem,a common solution to such problem is to merge the paths into a tree after finding paths from the source node to each destination node.This method maybe obtains the better result,but it can consume a lot of computational time.To solve the problem,a tree-based DE algorithm is introduced in this paper.The central operations of the algorithm are realized with tree structure.This method saves the time of finding paths and integrating them to construct a multicast tree.The experiments show that the proposed algorithm can achieve higher success rate than several common algorithms with much smaller running time for different networks.     

Layered-routing approach for solving multicast routing and wavelength assignment problem

We have developed a new layered-routing approach to address the problem of all-optical multicast over wavelength-routed wavelength division multiplexing (WDM) networks. We model the WDM network as a collection of wavelength layers with sparse light- splitting (LS) and wavelength conversion (WC) capabilities. We apply the degree constraint technique to solve the problem. The approach is capable of completing multicast routing and wavelength assignment (MCRWA) in one step. We propose two generic frameworks to facilitate heuristic development. Any heuristic that is derived from either Prim’s or Kruskal’s algorithm can be easily imported to solve the MCRWA problem. One example is given for each framework to demonstrate heuristic development. Extensive simulations were carried out to measure the performance of heuristics developed from the frameworks. The results show that the STRIGENT scheme is suitable for hardware design and it is advisable to deploy light splitters and wavelength converters to the same node for better performance.     

基于延时及带宽约束的组播路由算法

本文分析了网络中基于延时和带宽受限的组播路由优化问题,提出了一种新的启发式算法,并进行了实验和分析。文中构造的路由方案成功地解决了当网络中存在多组组播通信时的QoS路由选择问题。此方案不仅保证了组播业务所需的带宽、端到端延时、减小了丢包率,而且有效地控制了算法的复杂性并可适用于大规模的网络中。     

一种基于拉格朗日松弛的时延约束多播路由算法

提出了一种基于拉格朗日松弛方法的时延约束最小代价多播路由算法(LR-DLMA)。该算法充分利用拉格朗日松弛方法的特点，通过构建封闭图，对封闭图进行拉格朗日松弛求得满足条件的多播树。仿真实验结果表明本算法性能稳定，其代价性能接近性能最好的BSMA算法，并具有快速、低时延的特点。     

An integrated routing and admission control mechanism for real‐time multicast connection establishment

There are two major difficulties in real‐time multicast connection setup. One is the design of an efficient distributed routing algorithm which optimizes the network cost of routing trees under the real‐time constraints. The other is the integration of routing with admission control into one single phase of operations. This paper presents a real‐time multicast connection setup mechanism, which integrates multicast routing with real‐time admission control. The proposed mechanism performs the real‐time admission tests on a cost optimal tree (COT) and a shortest path tree (SPT) in parallel, aiming at optimizing network cost of the routing tree under real‐time constraints. It has the following important features: (1) it is fully distributed; (2) it achieves sub‐optimal network cost of routing trees; (3) it takes less time and less network messages for a connection setup. Copyright © 2001 John Wiley & Sons, Ltd.     

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.     

基于时延的分层多播拥塞控制协议设计

提出了一种适用于多媒体传输的接收端驱动的分层多播拥塞控制机制，简称BDP（based on delay parameters）协议。该协议依据时延参数的动态变化来估测路径可用带宽，保证了网络资源的有效利用，实现了自适应的加层判断；预测网络的拥塞状况，实现了对拥塞的快速响应。ns2仿真结果表明，BDP协议取得良好的稳定性、扩展性、快速收敛性，相比于现有的MRAAR-MT协议，BDP协议表现了更好的TCP公平性。     

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

基于固定和移动IP混合网络，针对时延敏感的实时通信业务，建立了网络模型，提出了有时延约束的低代价组播路由问题，给出了一种分布启发式组播路由算法，证明了算法的正确性，分析了算法的复杂度。仿真结果表明，算法是有效的、稳定的。