资源描述：
《应用层组播的最小延迟生成树算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2005/16(10)1766)2005JournalofSoftware软件学报Vol.16,No.10应用层组播的最小延迟生成树算法’曹佳’,2+鲁士文’1(中国科学院计算技术研究所，北京100080)2(中国科学院研究生院，北京100049)AMinimumDelaySpanningTreeAlgorithmfortheApplication-LayerMulticastCAOJia'"Z',LUShi-Wen''(InstituteofComputingTechnology,
2、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.Am
3、inimumdelayspanningtreealgorithmfortheapplication-layermulticast.JournalofSoftware,2005,16(10):1766-1773.DOI:10.1360/josl61766Abstract:Realtimetransmission,whichisdelaysensitive,isanimportantaspectofapplication-layermulticast.Itiscrucialtobuildanefficien
4、tmulticasttreetoguaranteethelowerdelay.Thisresearchisfocusedonthealgorithmsoftheminimum-delayspanningtreefortheapplication-layermulticast.Firstly,itisstatedthatthetotaldelayisaffectedbycommunicationdelay,processingdelayandthedegreeofnodes.Thenthenetworki
5、smodeledintothenode-and-edge-weighteddirectedgraphwiththelimiteddegreeofnodes.InthismodeltheproblemisshowntobeNP-hard.Therefore,twokindsofheuristicalgorithmsareproposed,whicharebasedonthemaximumdegreeandthemaximallengthpathrespectively.Finally,thesimulat
6、iondemonstratesthattheproposedalgorithmsarevalid.Keywords:application-layermulticast;minimumdelayspanningtree;NP-hard;realtimetransmission摘要:实时传输是应用层组播技术的一个主要应用领域，对网络延迟有严格的限制.保证低延迟组播成功的关健在于构建高效的应用层组播树，研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点
7、度，然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解“度约束最小延迟生成树”的问题，同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性.关键词:应用层组播;最小延迟生成树;NP-hard;实时传输中图法分类号:TP393文献标识码:A组播是一种一对多的通信方式，常用于视频会议、内容发布、远程教学等网络应用.IP组播是一种较早的组播实现机制，虽然具有较高的传输效率，但是对底层的网络设备有支持组播协议的
8、要求，所以在现阶段不能在WSupported勿theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2002AA742052(国家高技术研究发展计划(863))作者简介:曹佳(1978-),女，新疆库尔勒人，博士生，主要研究领域为组播路由;鲁士文(1944-)，男，研究员，博士生导师，主要研究领域为计算机网络协议.曹佳等:应用层组播的最小延迟生成树算法1767广大
