一种时延受限的多播路由算法

很多实时多媒体应用要求通信网络提供多播服务支持，而且往往需要传输的信息满足源端到目的端的时延约束。该文对时延约束的多播路由问题进行了研究，基于原有的从源端到目的端的时延受限路径构造算法，提出了一种时延受限多播路由算法。该算法能够快速构建满足时延约束的多播树。理论分析表明，该算法的时间复杂度和CDKS算法相同。仿真实验结果表明，该算法所构建的多播树代价低于CDKS算法。     

一种新的时延受限多播路由算法

为了满足多播业务的实时性要求、提高资源利用率,提出一种新的时延受限最小代价树多播路由算法。该算法基于最小代价多播树的生成方法,对节点之间的时延进行动态修改,寻找满足时延限制的最短路径,可快速找到满足时延约束的多播树。实验结果表明,该算法生成速度快、代价性能良好、能够满足多媒体网络的实时性要求。     

时延约束动态组播路由的快速低代价算法

提出一种时延约束动态组播路由的快速低代价算法。该算法利用改进的时延约束最短路径子图,在加入组播节点时避免非时延约束最短路径的搜索,提高算法的计算效率。通过使新加入节点与树上已有节点共享最短路径,降低整棵组播树的代价。仿真结果表明,该算法计算时间少,组播树总代价低,能使组播树更稳定。     

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

通过对时延约束组播路由网络模型的分析,提出了一种基于拉格朗日松弛法的时延约束的低代价组播路由算法(LR-DLMR)。由于封闭图对原网络的多播不可达问题,该算法并没有构建原网络的封闭图,从而有效利用了链路中间节点信息。仿真实验结果表明本算法具有良好的稳定性,有较低的代价和时延。     

一种基于禁忌搜索的时延约束组播路由算法

提出了一种使用禁忌搜索方法构造组播树的时延约束最小代价组播路由算法（TSBDMA)。该算法充分利用禁忌搜索方法中灵活的记忆功能和禁忌规则等特点,以最小时延树为初始解,并使用换边操作构造邻域集,最终求得满足条件的组播树。仿真实验结果表明本算法具有代价性能良好、可靠性高、收敛速度快、时延低的特点。     

基于关键节点的触发重组动态组播路由算法

提出了一种基于关键节点的触发重组动态组播路由算法(CRKDMR)。它在一定条件下优先选择包含关键节点的路径将新的组播节点连接到已有组播树,以此实现更多链路共享,降低组播树费用。相对于现有的触发重组算法,它提出了更为全面和合理的触发函数。随机网络模型的仿真结果表明,CRKDMR算法的性能好,效差和对树的改变都比较小,同时可以在代价性能和对树的改变间进行很好的权衡。     

一种延时约束费用最小分布式动态组播路由算法

多媒体应用一般包含多个组播成员,它消耗大量的网络资源且有严格的端端延时约束.针对这个问题,提出了一种延时约束费用最小的分布式动态组播路由启发算法DDDDCLCMR(distributeddynamicdelay-constrainedleast-costmulticastroutingalgorithm).在DDDDCLCMR算法中,组播源点很少或根本不参与路由计算;即使组播成员发生改变,组播树变化也很小,算法扩展性好.实验结果表明,无论组播成员改变与否,DDDCLCMR算法都能获得满足延时约束且费用很低的组播树.     

An effective algorithm for delay-constrained dynamic multicasting

With the development of multimedia group applications, the construction of multicast routing tree satisfying Quality of Service (QoS) is more important. In many multicast applications, it is required that the network supports dynamic multicast, which the membership of the multicast group changes with the time. In this paper an effective heuristic algorithm is proposed for dynamic multicast routing with delay-constrained. Aims of this proposed algorithm is to guarantee that: (1) the cost of multicast tree is as small as possible at each node addition/removal event, (2) all the maximal path delay is meet a fixed delay-constrained, (3) minimize perturbation to an existing tree. The proposed algorithm is based on ‘damage’ and ‘usefulness’ concept, and a Balancing Factor (BF) is provided to judge whether or not to arrange a region of tree. Mutation operation in Genetic Algorithm (GA) is also employed to find an attached node in tree for a dynamic adding node. Simulation shows that our algorithm performs well than those static heuristic algorithms in term of cost especially.     

一种改进的时延受限多播路由算法

针对DCMPH算法不能合理选择连接路径的问题,提出一种改进的满足时延限制的多播路由算法。该算法对不能用最小代价路径连接到多播树上的目的节点,求出其到多播树上所有节点的最小时延路径,再从中选出一条能满足时延限制的费用最小的路径,添加到多播树上。实验结果表明,与DCMPH算法相比,该算法构造多播树的代价更低。     

参数可调的克隆多播路由算法

近年来,时延受限的代价最小多播树问题备受关注.到目前为止,BSMA(bounded shortest multicast algorithm)算法被认为是最好的受限多播路由算法;然而,过长的计算时间限制了其应用.作为一种全局优化算法,遗传算法(genetic algorithm,简称GA)被越来越多地应用于多播路由问题.与传统的算法相比,遗传算法的全局搜索能力更强,但其易"早熟"的特点使它并不总是能得到最优多播树.提出的基于克隆策略的多播路由算法,有效地解决了"遗传"多播路由算法中的"早熟"问题,并通过引入一个可调因子缩小了搜索空间,加快了算法的收敛速度.算法实现简单、控制灵活.仿真结果表明,该算法的性能优于BSMA算法和传统的遗传算法.     

时延约束的链路选择平衡优化组播路由算法

针对时延约束的最小代价组播树生成方法,提出一种快速有效的时延约束组播路由算法。该算法改进了KPP算法,设计了代价和时延动态优化的链路选择函数。在选择路径时,该算法综合考虑了时延和代价两个参数,保证了组播树的性能,降低了时间复杂度低。仿真结果表明,该算法能正确地构造出时延约束组播树,同时还具有较低的代价和计算复杂度。     

一种有效的分布式QoS组播路由算法

提出了一种解决Qos限制代价优化问题的分布式组播路由算法，分析和仿真表明本算法和以前的几种算法相比，具有Qos要求严格时成功率高，代价优化、性能稳定的特点。算法的这些特点使其特别适合于因特网上对Qos要求严格的宽带多媒体应用。     

量子克隆多播路由算法

BSMA(bounded shortest multicast algorithm)被认为是最好的受限多播路由算法;然而,过长的计算时间限制了其应用.作为一种全局优化算法,遗传算法(GA)被越来越多地应用于解决多播路由问题.与传统的算法相比,遗传算法的全局搜索能力更强,但其易"早熟"的特点使它并不总是能够得到最优多播树.提出量子克隆多播路由算法,有效地解决了"遗传"多播路由算法中的"早熟"问题,量子交叉的引入,加快了算法的收敛速度.算法实现简单、控制灵活.仿真结果表明,该算法的性能优于BSMA算法和传统的遗传算法.     

多QoS约束的层次多播路由算法框架

为了解决网络路由的扩展性问题。大型网络通常被划分成若干个不同的域。拓扑聚集是对这些域的拓扑状态信息进行汇总的过程。在拓扑聚集的基础上，QoS层次多播路由算法用来构造满足QoS要求的域闻多播树。现有的QoS层次多播路由算法在其拓扑聚集和路径计算的过程中都只考虑了存在两个QoS特征值的情况。本文提出了一种具有多QoS约束的层次多播路由算法框架HMRMQ（Hierarchical Multicast Routing with Multiple QoS constraints），此算法框架不仅为基于多QoS特征值的拓扑状态聚集和状态信息表示提供了新的方法，而且提出了一种适应于多QoS约束的层次多播路由新算法。我们提出的状态信息表示法和拓扑聚集算法都具有很好的扩展性，分布式的路由算法也便于某些安全性策略的实施。理论分析和实验结果不仅证明了HMRMQ的正确性和有效性，同时也表明了HMRMQ在网络路由的扩展性、路由成功率、网络代价以及报文负载等方面都具有良好的性能。     

受时延约束的组播路由算法

提出了一种新的受时延约束的组播路由算法。算法借鉴了MPH算法的思想，最初的组播树只包含源结点，然后每次将到达组播树的代价最小且满足时延约束的结点及其相应的路径加入到组播树，直到所有的成员加入为止。谊算法能够快速地得到一棵满足时延约束的组播树，并且组播树的代价也很小。实验表明：该算法简单，复杂度低，性能良好，易于在分布式环境中实现，可应用于实际的应用系统中。     

多播路由KPP算法的改进

论文提出一种满足端到端时延限制的多播路由算法。该算法参考KPP[7]算法,在构造多播路由树的过程中动态调整路径的选取,使尽可能地共享网络中的链路,并对所构造的多播树进行进一步的调整优化,最后得到一棵低代价的满足端到端时延限制的多播路由树。论文通过对KPP算法进行分析发现KPP算法思想忽略了对转发节点的处理,而且在两节点间路径的选取过程中仅仅选取最佳路径,这就导致了对边稠密的图,KPP算法存在缺陷。算法基于上述缺陷完善了KPP算法,在复杂的网络图中应用该算法比KPP算法更加有效,实验模拟表明该算法构造的多播树与KPP算法构造的多播树相比能优化9%到10%。     

WDM网络中一种时延约束多播路由算法

文章提出了一种在有限波长转换器的WDM网络中,基于拉格朗日松驰的时延约束最小代价多播路由算法。该算法将WDM网络中的寻径与波长分配合成一步,并充分考虑到波长转换器的限制,利用拉格朗日松驰方法的特点,通过对松驰参数的变化得到每链路上的聚合代价,从而得到一棵近似于最优解的多播树。     

基于遗传算法的带时延约束组播路由算法

探讨了带时延约束组播路由优化算法,选用时延约束信息产生备选路径集并编码,给出了在该编码方式下使用不同进化阶段应用不同变异概率思想的改进遗传算法.仿真试验结果表明,该算法是可行有效的.     

A distributed multicast routing algorithm for real-time applications in wide area networks

The problem of constructing a minimal cost multicast routing tree (MRT) with delay constraints in wide area networks (WAN) is considered. A new distributed token-passing based algorithm that constructs a sub-optimal MRT satisfying given delay constraints for all members in the multicast group is presented. In contrast with the previous works by Jia [A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks, IEEE/ACM Trans. Network. 6 (1998) 828–837] and several others [Y. Im, Y. Lee, S. Wi, Y. Choi, Delay constrained distributed multicast routing algorithm, Comput. Comm. 20 (1997) 60–66; X. Jia, Y. Zhang, N. Pissinou, K. Makki, A distributed multicast routing protocol for real-time multicast applications, Comput. Networks 31 (1999) 101–110; Q. Sun, H. Langendorfer, A distributed delay-constrained dynamic multicast routing algorithm, Telecommun. Systems 11 (1999) 47–58], in which cycles may occur, we show that the multicast routing network produced by our algorithm is indeed a tree, namely, cycle free. Also the success rate of our algorithm to find a feasible solution, if one exists, is guaranteed to be 100%, while Jia's algorithm is not. Furthermore, our algorithm is fault tolerant and can also adapt to cases where the multicast group members are allowed to join or leave the multicast session dynamically. Simulations have been conducted and the results show that the MRT generated by our algorithm has better performance compared to previous methods.     

基于量子遗传退火策略的多播路由优化模型及其算法

针对网络通信中带时延约束的多播路由问题,提出了一种基于量子遗传退火策略的路由算法。文中对路由选择问题的优化模型进行了描述,并深入研究了量子遗传退火及其在多播路由选择优化问题中的应用。仿真实验表明,与基于遗传算法的多播路由算法相比,该算法具有更快的收敛速度和更好的全局寻优能力。