启发式多约束QoS组播路由算法分析.pdfVIP

启发式多约束Qos组播路由算法研究 摘 要 近来Intemet上有越来越多的QoS要求的组播应用的涌现，如视频会议、网 络音频／视频广播、远程教育、软件更新等，这加速了网络对可扩展的有效的组 播通信方式支持的需要。与单播通信方式比较起来，组播在点到多点的数据传输 方面更有效，在传统的单播通信方式中，源需要向每个接收者单独传送一份数据 的拷贝，一个数据流就有可能占用了不必要的很大一部分的带宽，如果接收者成 千上万，网络拥塞发生的可能性就大大增高。而在组播通信方式中，主干链路上 只有一个数据的拷贝，路由器只在分枝处进行数据包的复制，所以大大节省了带 宽。 实现组播重要的一环是组播路径的确立，与单播传输路径不同的是组播数据 传输的拓扑是一棵组播树，而构建组播树是组播路由的任务，考虑到现在越来越 多的多媒体应用要求有QoS保证，所以如何构建一棵组播树使其满足相应用户 的QoS要求成为组播研究领域的一个很大的挑战。许多研究者正致力于QoS组 播路由算法和协议的研究和设计，QoS组播路由已经成为近年来的一个热点研究 领域。 在QoS组播路由中，寻找多约束可行路径问题已经被证明是NP完全问题。 CMST问题使服务路径领域受到越来越多的关注，但是针对多重附加约束的多点 路由却没有得到太多的进展，尽管大量正在形成的应运软件对此提出了需求。在 这篇论文中，我们提出了一种构建组播树的启发式算法，HMCMC来解决这个问 题。HMCMC有着低时间复杂度，它的基本思路就是逐步建立一种多点路由，这 需要建立在关于多约束组播路由必威体育精装版研究的基础上。仿真结果表明，与以往算法 相比，该算法在消息开销、连接成功率和连接建立时间等性能指标方面都有较好 的改善。 关键词：Oos路由，多约束组播路由，多约束最小Steiner树，多路径约束 问题 THERESEARCHoNHeuristicMulti．constrained muiticast QoS routingalgorithm Abstract overthe Therecent of Intemet．such proliferationQoS—awaregroupapplications asvideo distributions，distancelearning，softwareupgradingetc， conferencing，news has theneedforscalableandefficientmulticast iSa accelerated support．Multicast moreefficient mechanismthanunicaston data transport point-to．multipoint thetraditionalunicastthesourceneedtosendanindividualof transmitting．In copy thesamedatatoeach a stream a receiver，SO single mayunnecessarilyrequirelarge oftheavailablenetworkbandwidtll．iftherearethousandsofreceivers．it portion in