时延及时延抖动限制的最小代价多播路由策略.pdf

《时延及时延抖动限制的最小代价多播路由策略.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第5期计算机学报Vol.25No.52002年5月CINESEJ.COMPUTERSMay2002时延及时延抖动限制的最小代价多播路由策略王明中谢剑英张敬辕(上海交通大学控制工程及网络技术研究室上海200030D摘要满足多种服务质量请求的多播路由问题是目前多播通信中的重要课题之一.该文作者在研究受端到端时延及时延抖动限制的多播路由问题的过程中发现当前许多算法所普遍使用的两个最佳链路选择函数并不能完全体现路由的动态过程同时它们还存在一定的缺陷.而正是由于这种缺陷在某些情况下通过这两个最佳链路选择函数所得到的结果树可能不包含所有的目标节点文中

2、称这种情况为多播不可达.针对上述问题该文提出了多播可达的假设条件以及一个新的最佳链路选择函数并在此基础上提出了一个满足时延及时延抖动双重限制的最小代价多播树的建立算法(DDVBMRAD以及一种动态重组多播组目标节点的方法.仿真结果表明本算法具有很好的时延抖动及代价性能.关键词服务质量多播路由链路选择函数时延时延抖动中图法分类号:TP393StrategyofConstructingMinimumCostMulticastRoutingTreewithdelayanddelayVariationBoundsWANGMing-ZhongXIEJian

3、-YingZANGJing-Yuan(ReSea7hG70/P0fC0nt70Engznee7zngandNetw07kTehn00gyShanghazza0t0ngunzze7SztyShanghaz200030DAbstractThiSpaperStudieStheproblemofconStructingmulticaStroutingtreeWithdelayanddelayVariationboundS.ThiSproblemcanbeformulatedaSthatoffindingaminimumcoStSteinerTreeWhi

4、chSatiSfieStheconStraintSaboVe-mentionedandiSknoWntobecomputationallyin-tractablebeingNP-complete.WhilereSearchingintotheproblemofconStructingmulticaStrout-ingtreeWithdelayanddelayVariationboundSWefindthattWobeStedgeSelectionfunctionSWhicharebetakenabroadtoconStructingmultica

5、StroutingtreeinmanyalgorithmShaVeSomelimitationS.AndjuStbecauSeoftheirlimitationSonacertainoccaSionthefinaltreeconStructedthroughthemcannotSpanallthedeStinationS.AttheSametimetheycannotrepreSentthedy-namiccharacteriSticSoftheroutingproceSScompletely.ThereforeWepropoSeadeStina

6、tionreachablegualificationandaneWedgeSelectionfunction.InadditiontotheproblemofdelayanddelayVariationboundedmulticaStroutingbaSedonouredgeSelectionfunctionWeputforWardaheuriSticalgorithmcalledDelayandDelayVariationBoundedMulticaStRoutingAlgorithm(DDVBMRADbyWhichaminimumcoStmu

7、lticaSttreecanbeconStructed.BeSideSamethodofadjuStingtothedynamicchangeofmulticaStmemberShipiSintroduced.ItiSShoWnthatintermSofdelayVariationandcoSttheheuriSticalgorithmdemonStrateSgoodaVeragecaSebehaV-iorthroughSimulationSonalargenumberofgraphS.KeywordsGoSmulticaStroutingedg

8、eSelectionfunctiondelaydelayVariation收稿日期:2001-05-24;修改稿收到日期:2002-01