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

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

一种改进的时延受限低代价光组播路由算法

针对光网络时延受限光组播路由计算复杂度高的问题,提出一种基于改进的和声搜索求解时延受限光组播路由的算法。论文通过引入自适应的和声记忆保留率及微调概率提高和声算法搜寻到全局最优光组播树的能力;算法设计了一个能够保持备选光组播树多样性的动态适应度函数以扩大光组播路由的搜索范围;同时,算法在初始化和声库时采用精英保留策略简化和声迭代过程。仿真结果表明,提出的改进算法能够求得代价更低的光组播路由,且算法在较大光网络规模下具有较好的收敛稳定性。     

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

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

一种支持QoS的拓扑自适应动态组播路由算法

YAM、QoSMIC、DSDMR等一类支持QoS的动态组播路由算法允许组播成员动态地加入和离开，同时为接收方提供多个可选择的组播接入路径，以满足不同应用的QoS需求。但这些算法普遍存在控制信令开销大和结点加入时延长，可扩展性不好等问题。本文在分析这些算法的基础上，提出改进的支持QoS的动态组播路由算法，即拓扑自适应动态组播路由（Topology Adaptive Dynamic Multicast Routing，TADMR）算法。该算法避免了以往算法中大部分盲目的路径搜索，并使结点加入时延不再受限于固定的等待时钟，而与网络拓扑相自适应。性能分析和仿真结果表明，该算法具有较低的控制信令开销和结点加入时延，适用于各种网络规模和群组规模，具有良好的可扩展性。     

一种新的QoS保证的快速组播路由算法

提出了一种新的服务质量保证的组播路由算法。算法使用了一个修改的斯坦利树近似算法来构建时延有界的低代价组播树，再通过最小时延路径与其他尚不在组播树的组内节点连接，并消除环路。理论和仿真表明，新算法与其他一些时延有界组播路由算法一样有较好的性能。并且有较小的复杂度。     

基于遗传算法的路由选择问题的研究

为了在一个通信网络中,找到多源点到多目的点的路由总代价最小的符合带宽-时延约束的路由集,根据服务质量组播路由的特点,结合遗传算法的寻优特性,采用一种求解带宽-时延约束的两层遗传算法的方法,进行了理论分析和实验验证,取得了多源点到多目的点组播路由集的代价数据。结果表明,所提出的算法可以有效找到多组播路由问题的优化解。     

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

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

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

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

时延和时延抖动约束的低费用多播路由算法

为了有效支持交互式实时组播业务,不仅要考虑时延约束,而且要考虑时延抖动约束,同时还需高效管理网络资源,以降低多播费用。本文提出了一种新的时延和时延抖动约束的低费用我播路由启发式算法,仿真结果表明该算法复杂度较低,时延抖动较小,又降低了网络费用,是一种快速有效的多播路由算法。     

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

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

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.     

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.     

基于蚂蚁算法的时延受限分布式多播路由研究

本文探讨了在高速包交换计算机网络中,具有端到端时延限制的多播路由问题。提出了一种新颖的基于蚂蚁算法的多播路由优化算法,该算法是完全分布式的。仿真实验表明,用该算法产生的多播路由树的费用比已存在的主要算法更好,并且适应于多播成员数的变化。     

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.     

Virtual-node-based multicast routing and wavelength assignment in sparse-splitting optical networks

This paper investigates several problems associated with optical multicast routing and wavelength assignment in sparse-splitting optical networks for interactive real-time media distribution. Unfortunately, the constrained multicast routing with optimized wavelength assignment leads to NP-complete condition. Thus, in this paper, a virtual-node-based multicast routing algorithm is first proposed to satisfy the requirements of interactive real-time multicasting as well as the constraints from underlying optical networks. For the constructed multicast tree, we then associate an effective wavelength assignment algorithm. The experimental results show that the proposed algorithm combination performs well in terms of (1) the wavelength channel cost, (2) the maximum variation of inter-destination node delays, (3) the signal quality, and (4) the number of wavelength conversions.     

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

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

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     

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.