应用层组播的最小延迟生成树算法曹佳1,2+,鲁士文11(中国科学院计算技术研究所,北京100080)2(中国科学院研究生院,北京100049)AMinimumDelaySpanningTreeAlgorithmfortheApplication-LayerMulticastCAOJia1,2+,LUShi-Wen11(InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100080,China)2(GraduateSchool,TheChineseAcademyofSciences,Beijing100049,China)+Correspondingauthor:Phn:+86-10-62565533ext8837,E-mail:jiacao@ict.ac.cn,http://www.ict.ac.cnReceived2004-07-16;Accepted2005-03-11CaoJ,LuSW.Aminimumdelayspanningtreealgorithmfortheapplication-layermulticast.JournalofSoftware,2005,16(10):17661773.DOI:10.1360/jos161766Abstract:Realtimetransmission,whichisdelaysensitive,isanimportantaspectofapplication-layermulticast.Itiscrucialtobuildanefficientmulticasttreetoguaranteethelowerdelay.Thisresearchisfocusedonthealgorithmsoftheminimum-delayspanningtreefortheapplication-layermulticast.Firstly,itisstatedthatthetotaldelayisaffectedbycommunicationdelay,processingdelayandthedegreeofnodes.Thenthenetworkismodeledintothenode-and-edge-weighteddirectedgraphwiththelimiteddegreeofnodes.InthismodeltheproblemisshowntobeNP-hard.Therefore,twokindsofheuristicalgorithmsareproposed,whicharebasedonthemaximumdegreeandthemaximallengthpathrespectively.Finally,thesimulationdemonstratesthattheproposedalgorithmsarevalid.Keywords:application-layermulticast;minimumdelayspanningtree;NP-hard;realtimetransmission摘要:实时传输是应用层组播技术的一个主要应用领域,对网络延迟有严格的限制.保证低延迟组播成功的关键在于构建高效的应用层组播树,研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点度,然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解“度约束最小延迟生成树”的问题,同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性.关键词:应用层组播;最小延迟生成树;NP-hard;实时传输中图法分类号:TP393文献标识码:A组播是一种一对多的通信方式,常用于视频会议、内容发布、远程教学等网络应用.IP组播是一种较早的组播实现机制,虽然具有较高的传输效率,但是对底层的网络设备有支持组播协议的要求,所以在现阶段不能在广大范围内普及.为此,人们提出了应用层组播,希望它既能继承组播的传输特性,例如节约带宽、SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2002AA742052(国家高技术研究发展计划(863))作者简介:曹佳(1978－),女,新疆库尔勒人,博士生,主要研究领域为组播路由;鲁士文(1944－),男,研究员,博士生导师,主要研究领域为计算机网络协议.传输快捷,也可以脱离对底层基础网络提升的依赖,在近期就可以实现较大范围的组播通信.因此,应用层组播成为倍受瞩目的组播实现机制.人们已经研究了多种应用层组播协议,如Narada,NICE,Yoid,ALMI和Scribe等[4].无论何种协议,“保证组播参与者尽快收到组播包”一直是应用层组播的主要追求目标,它对实时传输有重要的意义.解决这个问题的关键在于构建高效的应用层组播树,主要涉及两个方面:①如何将应用层组播的覆盖网络映射成图,即如何抽象问题模型;②如何求解映射图的最小延迟生成树.目前求解应用层组播树算法的主要差异是人们根据不同的应用需求提出了不同的问题模型[16],见表1,然后设计出不同的求解算法.这些问题大多属于NP-complete,不存在多项式时间解.文献[26]将覆盖网络抽象成一个边带权、结点度受限的图,未考虑结点的权值,也就是说,忽略了中间结点的处理时间.然而,现实中应用层组播的中间结点大多是普通主机,它们不具备线速转发的能力,因此在抽象问题模型时不能忽略转发处理时间.MDM模型[1]相对要完善一些,它将覆盖网络抽象成一个结点和边都带权...