最小延迟的应用层多播树算法研究【商学院℉论文】

《最小延迟的应用层多播树算法研究【商学院℉论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最小延迟的应用层多播树算法研究【商学院℉论文】小型微型计算机系统2010年2月第2期JournalofChineseComputerSystemsV01.31No.22010======皇=====================蛊=======昌=======皇===暑=======富=========兰===r=======芒===============皇===；；；==最小延迟的应用层多播树算法研究郑心炜1，余胜生21（广东商学院信息学院电子商务教研室，广东广州SJ0320）2（华Ill科技大学计算机学院信息存储系统教育部重点实验室，湖北武汉430074）E

2、.mail:auwcihust@163.cam摘要：在构建高效的应用层多播树过程中，许多端系统需要时间处理发送月须考虑节点的处理延迟．本文分析了两类应用层多播路由模型：基于优化延遮证明都是NP难问题，且提出相应的两类启发式近似算法：MRDL-H算法和算法的高效性、健壮性．关键词：应用层多播；最小延迟生成树；路由算法；NP-hard中图分类号：TP393文献标识码：A文章编号：1000-1220{2010)02-0198-04StudyofApplication-IayerMulticastAlgorithmsBasedonMinimumDelay酌问题必模型，并r所

3、提出ZHENGXin-wei',YUSheng-sheng21(CollegeofComlnuarScience&TechnoLogy,H"azhon8UniversltyofScienceandTeclmology,Wuhan430074,Ch/na)2(Injomuuio,r&ience&hoolofGuangdongUniversityⅣB*4sintssSmdks,G妣^即Ilou510320,Chrna)Abstract;lntheconstructinganefficientapplication-lcve/multicasttree,manyendsy

4、stemsneedsomeCimctosendandtransmitdata,sotheprocessdelaymustbeconsidered油resolvingffieproblemof"minimumdelayspanningtree",ffiisthesishasproposedtwoap-plicEdon-levelmulticastroutermodels;MRDLmodelbasedonoptimumdelayandLRRBmodelbasedonloadbalance.Atffiesametime,theyhavebeenproveAtobeNP-h

5、ardproble,ms.Thisthesishasproposedthecorrespondingheuristicalgorithms:MRDLHalgo-rithmandLRRB-Hzdgorithm.ThesimulationresuICshaveprovedthesealgorithmscantransmitthemediastreamefficientlyand肛bustly.Keywords:applicationlevelmulLicast,nunimumdelayspanningtrcc;routingalgorkhm;NP-hard1引言随着In

6、ternet多播技术的发展，应用层多播技术成为倍受瞩日的多播实现机制，如何生成最初的最小多播生成树成了覆盖多播研究的热点之一．Shi等‘¨研究了度约束的延时直径最小化和延时直径约束的度乎衡的两类覆盏多播共享树的生成问题，提出了一系列基于CT算法的启发式集中路由算法．Malouch等521住端系统和代理服务器混合构架下，研究了基于源的、具有度和延时半径约束的多播树生成同题，提出了一个CT的变形算法，该算法采用了度和延时折衷的优化策略，Banerjee等！纠、Chawathe掣”、文献[8]也针对上述同类覆盖多播路由同题各自提出了jf<同的分布式算法，因为现实中应用层多

7、播的中间节点大多是普通主机，不具有线速转发的能力，因此在抽象问题模型时不能忽略转发处理时间，必须考虑节点与边都带权，且节点的最大度受限，我们抽象出新的更全面的求解应用层多播树的问题模型：MRDL和LRRB问题，另外，本文对文献[1]提出的算法进行改进，针对两个模型相应提出相应的启发式算法：MRDL-H算法和LRRB-H算法，通过生成树来发布信息，可以保证所有多摇的参与者尽快地收到多播包．2网络模型和问题描述2.1网络模型和基本定义若多播源能处理的多播应用程序数据的速率为B，同时某个节点v的每条人访问链路数据速率为b州们每条出访问链路数据速率为boi(v)，且必须