22 基于最大延迟路径的算法.docVIP

应用层组播的最小延迟生成树算法( 曹 佳1,2+, 鲁士文1 1(中国科学院 计算技术研究所,北京 100080) 2(中国科学院 研究生院,北京 100049) A Minimum Delay Spanning Tree Algorithm for the Application-Layer Multicast CAO Jia1,2+, LU Shi-Wen1 1(Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100080, China) 2(Graduate School, The Chinese Academy of Sciences, Beijing 100049, China) + Corresponding author: Phn: +86-10ext 8837, E-mail: jiacao@, Received 2004-07-16; Accepted 2005-03-11 Cao J, Lu SW. A minimum delay spanning tree algorithm for the application-layer multicast. Journal of Software, 2005,16(10):1766?1773. DOI: 10.1360/jos161766 Abstract: Real time transmission, which is delay sensitive, is an important aspect of application-layer multicast. It is crucial to build an efficient multicast tree to guarantee the lower delay. This research is focused on the algorithms of the minimum-delay spanning tree for the application-layer multicast. Firstly, it is stated that the total delay is affected by communication delay, processing delay and the degree of nodes. Then the network is modeled into the node-and-edge-weighted directed graph with the limited degree of nodes. In this model the problem is shown to be NP-hard. Therefore, two kinds of heuristic algorithms are proposed, which are based on the maximum degree and the maximal length path respectively. Finally, the simulation demonstrates that the proposed algorithms are valid. Key words: application-layer multicast; minimum delay spanning tree; NP-hard; real time transmission 摘 要: 实时传输是应用层组播技术的一个主要应用领域,对网络延迟有严格的限制.保证低延迟组播成功的关键在于构建高效的应用层组播树,研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点度,然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解“度约束最小延迟生成树”的问题,同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性. 关键词: 应用层组播;最小延迟生成树;NP-hard;实时传输 中图法分类号: TP393　　　文献标识码: A 组播是一种一对多的通信方式,常用于视频会议、内容发布、远程教学等网络应用.IP组播较早的组播实现机制,虽然具有较高的传输效率,但是对底层的网络设备有要求,所以不能在广大范围内普及.为此人们提出了应用层组播,希望它既继承组播的传输特性,例如节约带宽、传输快捷,也可以脱离对底层基础网络的依赖,实现较大范围的组播通信.因此应用层组播成为