满足qos约束多播路由算法

《满足qos约束多播路由算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AThesisinOperationalResearchandCyberneticsQoSConstrainedMulticastRoutingAlgorithmsByChenXinghuaSupervisor：AssociateProfessorZhengLianweiNortheasternUniVersi锣January2008盛暑算●茁呷；．茹秘籽、“_I．，f独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包括其他人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研

2、究所做的任何贡献均己在论文中作了明确的说明并表示感谢。学位论文作者签名：际兴辛签字日期溯年7月B日学位论文版权使用授权书本学位论文作者完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门和机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。(如作者和导师不同意网上交流，请在下方签名；否则视为同意。)学位论文作者签名：签字日期：导师签名：签字日期：Jl■，I1●l■★oI东北大学硕士学位论文摘要满足QoS约束的多播路由算法摘要当前许多多媒体业务都要求网络具有多播(multic2Ls

3、t)能力，例如：音频、视频会议、交互式仿真、网络游戏、分布式数据库等。多播技术，将同样的数据从一个源节点同时传输给大量的目的节点，从而大大节省了网络带宽，减少了数据冗余，在一定程度上解决了多媒体通信中的带宽瓶颈问题，将成为未来的一项重要技术。多播路由算法的目标是寻找一棵连接源节点和多个目的节点的多播树，同时满足各种服务质量需求。在实时交互性多播应用中，时延和时延抖动等服务质量因素尤为重要。为此，论文主要研究满足QoS约束中时延和时延抖动约束的多播路由问题。论文首先研究时延约束下的多播路由问题，该问题的目标是创建一棵覆盖源节点和目的节点的代价最小树，且满足端到端时延要求。这个问

4、题被证明是NP完全问题。我们在研究已有算法的基础上，提出两个新的启发式算法。一种算法充分考虑链路共享对网络费用和链路时延的影响，提出了关键节点的概念。使得算法可以在满足时延约束的情况下，找到费用最小的多播树。另一种算法提出了节点优先函数和链路选择函数的概念，在构造满足时延约束低代价的树时运用了单播策略。分析的结论是这两种算法都是低复杂度、低费用并符合时延约束的多播路由算法。然后，论文分析限制时延抖动对某些多播应用的重要意义，并就时延和时延抖动约束的多播路由问题提出了一种新的链路选择函数。基于这个函数我们提出了一个时延和时延抖动约束的启发式Steiner树算法，通过仿真表明，该

5、算法在时延抖动方面有较好的性能。关键词：多播技术；QoS约束；时延；时延抖动；多播路由算法：最小代价II1▲J—iⅡ毒．}ol●_■，QoSConstrainedMulticastRoutingA190rit№sAbstractRec∞tly，m趾yoftllemulti-mediaapplicatio馏r。quirene帆ofI(st0pro“demultic嬲t．Theseapplicatio邶，forinst锄ce，c觚beaudio、vide0C0nf．erence、distributedsirnulation、n酣Ⅳorkgame、distributeddatab嬲

6、eandsoon．Multic嬲ttech-Ilology，which仃{msmitstlles锄edatafbmaso眦℃etoal鹕emmlberofdestinationnod懿sinlultaIleously'iIlordcrtosaveagreatdealofb锄dwidtll锄dreduCedatarcdulld雠cyiIlmenetwork，canresolvenleproblemofbaIldwidmbottl胁ccksofmenmltimediaco舢nuIlicationsinacenameXtent，aIldwiUbeCome姐importantt葩hn

7、olog)，iIlme如ture．111emainpu印oseofmultic嬲troutinga190ritllmsist0C0nstmCta仃∞rootedatmesoⅧ-ceandspaIlIlingalldestinations，whilemequalityofservice(QoS)winbesatisficd．Delay砸lddelayvariationarctwoQoSmetricsmatdircctlyrclatedt0real．timeintemctiveapplications．II