基于QOS的多播路由算法研究

《基于QOS的多播路由算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

北京交通大学硕士学位论文基于QoS的多播路由算法研究姓名：高玲玲申请学位级别：硕士专业：计算机应用技术指导教师：李伟生20060301 北京交通大学硕士学位论文来生成多播树。算法可以在满足时延约束的情况下，快速地找到性能较好的多播树，同时可以根据网络节点的加入或退出请求来更新多播树，实现对多播树的动态维护。实验结果表明，该算法代价性能良好、能够满足多媒体网络的实时性要求。最后对Qos多播路由算法今后的研究工作提出了一些设想和看法。关键词：多播路由，服务质量，steiner树，时延约束，动态多播 AbstractManymultimcdia印plicati伽ssuchasvedio—on·dem柚d，Vedioconference，lon分distanceeducation，etc，Ⅱecdmulticasttotr柚smitinfo姗ationinneMork．ItisgoodforsavingnetwOrkresOllrce．Winlthespceddeveloprnentofnc咖rktecllnolO盱孤dapplications’th鹳emultiInediaapplicationsrcquirethatneMorkpmvidcsqualityofscrvicc(QoS)．But也e缸ad“ionalmulticastjustpfov妯髂“best幽妒for鼹州ice．nc锄otmeeteverykindsofQoSf研distinctmul由nediaappⅡca瞳ionstllatrequest(bS．舡akeytechniquethatsupponsmultimediaapplicati∞s，theQoSmulticastmutjngproblemgetsmoreattention．HowtocreatcmulticaSttrecsthatsat．sfyconslrainlsbe∞mesoneoftllemosthOt趾ddifficultproblemsofresearchinneMork．Thisthesisccnte墙onthecreatingproblemofmultjcasttfeesbasedonQoS．ItpfesentsailimpmVedstaticalgorithmfordelayc0璐trajnedproblem，pmposesanewdynamicalgorithmfbrdynamicmultic弱troutjIlgpmblem柚ddoesexperimentsforthetwoalgorit胁s．ThemaillresearchworkandresultsareasfoUows：1．su咖arizemanymunic器tIoutingaIgorithmsbasedon(bSandaIlaIyzethecomputationalcomplexity趾dapplicableconditionsofeachalgoritlIm，especianyalgofilhmswithmorenlanone∞nstraint锄ddyll枷icalg嘣thIns．nisis也ebaSisofthefollowingwork．2．B鹪cdons衄eexistinga190血hms，throughmodifyingdelaysbet、jlrecnnodesdyn锄jcally，anewalgori岫fordelay-const豫iIledlllinim啪·cDstn℃cisprcseⅡted，whichh勰Ⅱicccostperfbnnance卸dcangetdday·constrained|llinimum—cost仃eequiddy． !!塞壅夔拦堡主堂鱼堡奎3．Anewh即矗stica190rithnlfbrdynamicQoSmumc雒troutingb嬲cdon柚alysisofdyn锄icmultic雒t咖tingpmbl锄iSpmposed．Thealgo棚mtal【estIleinnuenceOfpatlldelaytOtreccostint0accollIIt，柚dmal【esuseOfthemethod血dingthc七shon骼tpaths柚dthefllnctionofseIectilIgpatlltocreatcmulticasttree．Whjlethedelay00ns仃aintissatis6ed，thcalgoritllnlgetsthelawcost眦equicldy柚dc锄updatemulticast仃ceb黯ed曲ai旧in酬dcting咒qu洫m叨tsofnodcs．Alargcn岫berofsimulatio璐demo璐仃atcthatthealgoritlllIlhasnicccostpcrfbm矾∞卸dc矩satis母thefealtilIlere驴ircmentof删咐ork．Atlast，s嘲e龉锄mptions卸dViewsonfIltllrercse盯chofmulticastroutingal鲥岫sbasedonQoS缸eproposed．Keywords：Multi∞stRoutin岛QIlalilyofScrvicc，Steillcr11ree，Delaycons砌nt，dynamicmultic嬲t 北京交通大学硕士学位论文Y879701独创性声明本人声明，所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽本人所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通大学或其他教学机构的学位或证书而使用过的材料。与我一起工作的同志对本研究所做的任何贡献已在论文中作了明确的说明并表示了谢意。本人签名：高攻攻日期：立堕年』月』日 北京交通大学硕士学位论文关于论文使用授权的说明本人完全了解北京交通大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。论文中所有创新和成果归北京交通大学计算机与信息技术学院所有。未经许可，任何单位和个人不得拷贝。版权所有，违者必究。本人签名：壹垂堑日期：溯‘年；月扩日 绪论11。1QoS多播路由的研究意义网络上的很多应用，需要将信息从一点传输到多点，若采用传统的通信方式，将会造成降低网络传输效率、浪费网络资源等问题。因此，针对该问题提出的多播被广泛应用，以节省网络中的宝贵资源。随着高速网络和多媒体技术的进一步发展，人们越来越多地提出了各种各样的服务质量(0ualityofServicc，QoS)要求。而传统的多播只提供尽力而为服务，无法满足QoS需求。因此，基于QoS的多播路由引起了广泛重视，研究能满足应用要求的基于QoS的多播路由算法是现实而有重要意义的，这种研究对于网络理论和应用的发展将起到重大的推动作用。1．1．1多播路由研究背景网络中传统的通信模式主要有单播(点到点传播)和广播(一点到所有点传播)两种形式。随着通信技术和交换技术的飞速发展，特别是移动计算和分布式计算的迅速普及，单播和广播这两种通信模式已不能满足网络通信的需求，由此，产生了多播方式。计算机网络的许多应用例如视频点播(vOD)、视频，音频会议、远程教学、分布式游戏、计算机支持的协作工作等都需要网络具有多播服务的能力。这些应用需要消耗大量的网络资源，会造成网络拥挤、传输延肘等问题。与传统的单播和广播机制相比较，多播可以解决上述应用所要求的网络利用率高、传输速度快、实时性强等问题，它能显著的节省带宽资 北京交通大学硕士学位论文源，减轻服务器负荷，并且改善传送数据的质量。多播己被看成是m，rF(Intemet工程任务组)的一个关键问题。多播能力则是因特网的一个重要特性。多播也称组播或组内广播等，是一种实现从源节点同时向多个目标节点发送信息的通信形式。典型的多播应用包括更新数据库、命令控制系统、分布式游戏和分布式交互仿真等。多播路由是实现多播通信的关键技术之一，随着人们对多播兴趣的增加，多播路由技术得到了深入的研究。目前解决多播路由问题的典型方法是构建覆盖源节点和目标节点的多播树来传送信息。因为树型路由有两大优点：只在分支点处才进行包复制，网络中要传递的复胄4信息少，能节省带宽资源减少拥塞，降低网络负载；信息并行沿树枝发送到不同目标节点，降低了信息传递延迟。1．1．2QoS多播路由随着视频会议、视频点播等实时多媒体多播通信需求的增长，要求多播路由必须具有严格的服务质量保证，主要包括带宽、时延、时延抖动、代价、丢包率等；与此同时，多播业务也已被用于各种流媒体应用中，如多播业务主干网已被用于传输实时音频／视频新闻、远程学习及视频会议等信息，服务质量保证对于这些多播业务具有特别重要的意义。而传统的多播路由，如基于CBT的路由协议【1】和协议无关多播路由协议PIM【2J等，其构造的多播树主要是基于连通性度量，较适用于提供尽力传输服务，可能难以满足具有服务质量要求的实时多媒体业务传送的需要。因此，具有QoS约束的多播路由算法的研究逐步发展起来。它是以OoS为中心的网络体系结构中不可缺少的组成2 绪论部分，己成为网络研究领域的重要内容和热点问题。所谓Qos多播路由就是根据网络中可用资源和网络业务的QoS要求，寻找从源节点到多个目的节点的传输路径。一般路由选择由两个部分组成：一是根据已有的信息为到达业务选择合适的路径并发送数据包，即寻路过程；二是收集网络状态信息并不断更新消息，也就是节点问路由信息的交互过程。本文所做的路由算法研究是针对第一个部分的。QoS多播路由的主要目标是：为每个接纳的业务请求找到满足其服务质量要求的可行的多播树，满足用户的需求；在满足服务质量需求的情况下，优化全局资源利用率，平衡网络负载，从而最大化网络接受其他业务请求的能力。QoS路由算法的选择对QoS路由的实现起到决定性作用。1．2QoS多播路由的研究现状Qos多播路由就是为多播应用寻找满足各种约束条件的传输路径。其中有两个基本问题：最优化问题和性能界约束问题。最优化问题是寻找对应于QoS度量的最优路径；而性能界约束问题则是寻找大于Qos度量或小于Qos度量的路径，即在满足性能界要求的集合中选择一个解【3l。根据这两个基本问题，Qos约束可分为时延约束、时延抖动约束、带宽约束、代价约束等等。下面将根据各种约束条件对基于00s约束的多播路由算法的研究现状进行介绍。1．2．1单约束多播路由最短路径树(shonestPathTree，sPr)是使多播树上从源节点到3 北京交遥大学硕士学位论文目的节点的每条路径上链路权重之和最小，其算法可用来解决树约束问题；最小代价树(即stciner树)是使多播树上所有链路的代价总和最小，其算法可用来解决树最优化问题。对于sPT的构造算法，人们在Diiks昀算法基础上不断进行改进，到目前为止，构造SPT的快速算法的时间复杂度为O忙佃岫卵)(其中n表示图中节点数目，e表示图中边的数目一。采用图的链式存储结构，利用FiboⅡacci堆构造待发展节点集，就可以在D0栅，oI即)时间内构造sPT。当网络变得足够大时，从源节点到一些目的节点的最短路径常常不止一条，因而由此构成的sPT也就不是唯一的，在众多的sPT中每棵树的总代价也不尽相同。文献[5]提出目的驱动最短路径树算法DDsP，它采用Dijkstm算法路径递增的基本思想，并结合DDMc算法中目的节点共享路径的方法，来降低所构造SPT的总代价。文献[6]在DDsP算法的基础上通过改进节点的搜索过程，提出了一种快速算法FLSPT，该算法的时间复杂度比DDsP算法更低而且所构造的多播树性能相同。文献[7]同样改进搜索过程，但生成的最小代价树总代价比DDSP要小。文献[8]提出一种动态算法SBPT，同样通过目的节点之间共享路径来降低所构造的sPT的总代价。该算法添加一个新目的节点的时间复杂度为。研2)，构造包含小个目的节点的sPT的时间复杂度为。铆H2)，时间复杂度较高而不适合大型网络求解。基于Sle抽er树的问题致力于使多播树的总代价最小，并且已知是NP完全问题，不可能获得多项式时间算法，在可接受的时间内只能计算得到一棵近似的Stcin盯树。针对该问题人们提出了许多求近似最优解的启发式算法。MPHl9J、KMB【101等算法提供了较好的近似最优解，4 绪论但时间复杂度都较高而难于应用于实际路由协议。MPH是大家讨论较多的算法，通常把MPH作为比较steiner树算法的一种标准算法。文献[11]在MPH算法基础上改进，提出局部搜索算法LsMPH，通过牺牲多播树性能来提商效率，虽然时间复杂度没有改变但计算效率有一定提高。文献[12]提出的快速算法FMPH，通过改进MPH算法的搜索过程，以增加较少的存储空间为代价，使得时间复杂度降低，而且其多播树性能与MPH算法相同。DDMc算法f13l通过使目的节点之问尽可能共享路径来降低多播树的总代价，其平均性能较MsTH算法有较大改进，但仍不如MPH算法。Mam算、法【14】在DDMc算法基础上进行改进，通过扩大搜索范围，使所构造的多播树总代价比DDMc更低。1．2．2时延和时延抖动多播路由时延约束是指源节点到每个目的节点的传送时延要在约束范围内；时延抖动约束是指源节点到每个目的节点的传送时延的差值要在约束范围内。K|ompella等人于1993年首次提出了一种满足给定端到端时延约束的多播路由算法【圳，并证明此类问题是NP完全问题。该算法存在时间复杂度大和准确度低等问题。BSMA【16】算法则采用一个切实可行的搜索优化方法，由最短路径树开始，通过替换树中代价较高的边，迭代改进时延约束多播树的总代价。上两个算法均有很好的性能，但因时间复杂度过高而很难应用于实际路由协议。D埘R【17J算法在MClm【14J算法的基础上进行扩展，在构造Steinef树的过程中，拒绝违反时延限制的最小代价路径，而选择满足时延限制但可能不是最小代价的路5 北京交通大学硕士学位论文径，其生成树的代价接近BSMA算法产生的多播树，但时间复杂度远低于BSMA算法。G∞理eN．Rousk船在1997年首次提出了满足端到端时延及时延抖动约束的多播路由问题，并提出了一种有效的集中式算法DvMA【埘。该算法返回的多播树时延抖动很小，但时闻复杂度很高，为0@枷矿)，且代价性能不是很好。文献[19]针对D、礓l^算法的高复杂度，提出一种快速有效的启发式算法DDVcA。该算法主要基于共享树中核心路由器的概念和最小代价路径算法，快速有效地找到满足时延约束和最小时延抖动的多播树。文献[20]中把时延及时延抖动约束的多播路由问题提升到优化的层次上，证明时延及时延抖动约束的最小代价多播路出问题是NP完全问题，继而提出了一种基于动态罚函数法的启发式遗传算法以求解该问题。文献[21]则在DVMA算法的基础上进行简化提出SP．DvMA算法，算法的时延抖动比D、偶IA算法有所增大，但时间复杂度比DVMA有较大降低。文献[22]提出了一种分布式的满足时延及时延抖动的steiner树算法，通过在构造过程中协调时延及时延抖动之间的关系，最终使得每条路径在满足时延约束的同时，也尽量保证彼此之间的时延抖动最小。文献e23]提出了DvDMR算法，通过计算已添加路径的平均时延，要求所加入的每一条新路径均最接近当前平均时延。随着平均时延的不断改变，算法最终可以得到时延抖动最小的多播树。文献[24]提出一个关于“多播可达”的限定条件和一个新的最佳链路选择函数，并以此选择函数为基础提出了一个新的启发式算法D啪MRA，用来构造同时满足时延及时延抖动约束的steiner树。文献【25]提出了一种改进的神经网络模型来解决时延约束的多播路由问题。该算法能快速找6 绪论到一条可行路由，然而它不能克服易于陷入局部最小的缺陷。文献[26]基于最小代价树算法，通过动态修改节点之间的时延，可以快速的获得满足时延约束的最小代价树，其时间复杂度很小。文献[27]提出了一种动态的启发式算法，该算法可以根据网络节点的加入或退出请求来更掰多播树，并且充分考虑了路径时延对多播树总代价的影响，获得多播树性能较好。1．2．3有带宽约束的多播路由文献[28]研讨了具有时延和带宽约束的Qos多播路由问题，提出了一种具有时延及带宽约束的多播路由算法MRDBC。该算法通过分布式方法搜索到多条可行的路径树枝，选择最优(或近优)的一条将新成员连接到多播树上。算法避免了以往算法中大部分的盲目路径搜索，仅要求网络的局部状态信息，而不要求维护网络的全局状态信息，同时算法中多播组成员可以动态的加入或退出。文献[29]采用从理论上保证能够收敛到全局最优解的作为邻域搜索算法扩展的模拟退火方法，提出了一种基于模拟退火的多约束Qos多播路由算法sABDMA。该算法利用DDvCA算法119l获得初始解，并在可行解范围内构造邻域集，通过路径交换策略获得可行的邻域解，不断迭代求解，最终获得满足约束条件的最小代价多播树。文献[30]基于蚁群系统的自组织能力，提出了一个分布式的动态QoS多播路由的算法，即ACs算法。在该算法中，蚁群从多播组的目的节点出发进行搜索，将每次迭代选中的符合Qos约束且具有最小代价的路径加入到多播树中，多播树分布式地被构造。文献[31]提出了一种基于神经网络和遗传算法的新颖的QoS多播路由算法，该算法把7 北京交通大学硕士学位论文神经网络和遗传算法结合起来，并给出了一种便于进行交叉、变异等遗传操作的新编码方式，从而克服传统遗传算法中存在的早熟现象，加快收敛速度。文献[32]把BoA算法中的贝叶斯网络模型结合到强度Pareto进化算法II中，通过构造和学习网络来替代原算法中的交叉重组和变异等遗传操作，提出了一种能够同时优化带宽和时延等参数的多目标oos多播路由算法。该算法可在不做预处理的情况下把每个Qos参数分别作为一个独立的优化目标进行同时优化，能够快速收敛。1．2．4有度约束的多播路由在上述的多播树构造算法中，都假设每个节点可以将信息进行拷贝并向与其邻接的所有节点发送信息，但实际网络中并非所有节点都具备多播能力，或者节点的多播能力受限。例如，在现有的网络中，许多节点不支持多播：同时节点复制信息的数日必然影响节点处理信息的速度，为保证照个网络的传输速度以及节点的负载平衡，每个节点的多播能力应有所限制；加之每个节点的存储和处理信息的能力不同，每个节点只能向与其邻接的其中几个节点传输信息。给每个节点指定度约束来表示节点的多播能力，解决此类问题称为求解带度约束的Stejner树。Bauer等人于1995年提出的sPH算法【33l是目前求解带度约束的多播路由问题中性能较好的stciner树。其基本思想是：从只包括源节点的予图开始，寻找与之距离最近且不违反度约束的一个目的节点，用最短路径将两节点相连，同时将最短路径上的节点也加入图中，然后再找下一个与子图距离最近的不违反度约束的目的节点，将其加入，如此直到所有目的节点全部加入到树中。文献【34】则在分布式带g 绪论时延约束的多播路由算法的基础上提出了解决带度约束的多播路由问题的分布式算法。文献【35】提出了计算机通信网中的一类新问题，即同时带度约束和时延约束的多播路由问题，并使用la伊蛐ge松弛法来解决这类问题。1．3本文研究的主要内容在多播路由算法中，可以采取不同的优化准则，第一个准则是端到端的最小时延，这对于实时会议等多媒体应用来说是至关重要的。另一个优化目标是尽可能有效的利用网络资源，使网络的代价达到最小。这个目标对应于两个参量：最小化链路拥塞，最大化利用链路带宽。一般采用最小化网络代价柬度量网络资源的使用。因此，对具有端到端时延约束的最小代价树问题进行研究具有非常重要的意义。根据上节所述，在网络中寻找覆盖多播组成员节点的时延约束最小代价多播树，是一个NP完全问题。一般地，NP完全问题的最优算法无法在多项式时间内完成，因此，需要寻求有效的启发式算法，降低算法难度，而从性能上逼近理论算法。此外，目前对多播路由算法的研究偏重于静态多播算法，动态多播算法相对很少，而实际网络中节点动态变化的情况是静态算法所不能适应的，需要动态算法加以解决。本文对以上提出的问题进行了研究，文章首先对00S多播路由问题的研究背景和研究现状进行介绍，然后介绍了Qos多播路由问题的模型、度量、分类等方面，随后针对时延约束多播路由问题，在已有的最小代价树算法的基础上给出一种用于时延约束的改进算法，又针对动态多播路由问题，提出了一种新的满足时延约束的动态多播路由算法。9 本文内容安排如下：第一章简要介绍了OoS多播路由的研究意义，包括多播路由的研究背景和发展情况，并对基于Qos的多播路由算法的研究现状进行了研究。第二章介绍了多播路由的一些基础知识，包括00s多播路由的网络模型和度量、QoS多播路由问题的分类以及多播路由树的分类，并介绍了几个相关的基本算法，它们是其后大多数算法的基础，也是同类算法分析比较的标准。第三章首先对时延约束最小代价多播路出问题进行讨论，介绍分析了一些启发式算法，然后以快速最小代价多播树算法为基础，给出一种用于时延约束的多播树算法，该算法通过对节点之间的时延进行动态修改，寻找满足时延限制的最小代价路径，可快速找到满足时延约束的多播树。第四章介绍了多播路出中的动态问题，对动态算法进行了介绍分析，并提出了一种新算法。该算法充分考虑路径时延对多播树总代价的影响，利用前七条最短路径方法和路径选择函数来生成多播树。算法可以在满足时延约束的情况下，快速地找到性能较好的多播树，同时可以根据网络节点的加入或退出请求来更新多播树，实现对多播树的动态维护。最后总结全文并展望了进一步的工作。 基于Oos的多播路由理论介绍2基于QoS的多播路由理论介绍本章主要介绍Qos多播路由问题度量及模型，Qos多播路由问题的分类，多播路由树的分类，并对几个基本算法进行研究与分析。2．1QoS多播路由问题模型及度量在分析Qos路由问题之前，有必要先建立基于Qos约束的多播路由网络模型，了解度量的特性及其合成规则。2．1．1QoS多播路由度量度量在OoS多播路由问题中起着重要的作用，它不仅定义网络可以支持的服务质量类型，也定义应用的服务质量请求范围，并且还可以反映网络的基本特征【36】。通信信息的Oos请求是通过单度量或组合度量来量化和提出的，如果信息的QoS请求不能映射为单度量或组合度量，那么网络就不能支持该信息的QoS请求。假设路径P=(a，b，c，．．．0，k)，用M(a，b)表示对应链路(a，b)的度量，则Qos路由度量可分为如下三类：1)加性度量：M(P)=M(咖)+M(b，c)+⋯+Ma，k)路径的加性度量状态是由该路径上所有链路的特性共同决定的。加性度量包括时延、时延抖动、代价、端到端路由跳数等。2)乘性度量：M(P)=M(a，b)+M(b，c)·⋯·M(i，k)路径上的乘性度量为该路径上所有链路对应度量的乘积。乘性度量包括连接可靠性(即成功传输率：1．丢包率)等。3)凹性度量：M(P)=mill(M(a，b)，M(b，c)，．．．，M(j，k)) 北京交通大学硕士学位论文路径上的凹性度量状态是由传输链路中的瓶颈链路的状态所决定的。也就是说，一条路径上的某个凹性度量取决于该路径上所有链路对应于该度量的值中的最小值。凹性度量包括最常用的剩余带宽、剩余缓存空间和链路速率等。此类度量只与路径上的某个瓶颈链路的QoS度量有关。路由度量还可分为路径约束度量和链路约束度量㈨。由于一条路径的凹性度量依赖于该路径上瓶颈链路的值，所以凹性度量是链路约束度量；而路径的加性度量或乘性度量依赖于该路径上的所有链路的值，所以加性或乘性度量是路径约束度量。这里，各度量之间是不可互相替代的。例如，在QoS多播路由算法中，代价常被作为主要的度量，如著名的stcincr树问题，但是具有加性的代价度量并不能体现路径带宽的凹性，即路径的带宽应是路径中所有链路中带宽的最小值。在具体的设计多播算法的过程中，要根据网络的实际情况和应用的需求来解决闯题，对算法考虑所有度量的做法是不切实际的。例如，对于实时传输的多播应用，时延是必须保证的条件，代价则是评价网络使用效率的标准，都要纳入考虑的范围。而时延抖动、丢包率等可以不加考虑。2．1．2QoS多播路由模型设网络用加权无向图G=(nE)来表示，其中y是网络中所有节点的集合，每个节点表示主机或路由器；E为圈G中边的集合，每条边为连接网络节点的通信链路，链路上的参数代表链路的当前状态。用l川表示网络中的节点数，霉l表示网络中的链路数。5∈Ⅳ为源节点，D=纰如如⋯蚶，Dc矿是一个目标节点集，即多播组，m为多 基于OoS的多播路由理论介绍播组中节点的个数。R+表示正实数集。链路代价函数为c够：E——n，时延函数为D(D：E—R+)，时延抖动函数为‘，‘，：E—确+)，带宽函数为B但：E咖+)；包丢失率函数为：L仁：V—只+)；设有路径P仁，一=n嘻％⋯叫，(n为距，场为v)，表示从节点Ⅱ到节点y的一条路径。f是一个约束集，包括端到端时延，端到端时延抖动、路径带宽、成功传输率等。则对于给定的源节点s∈V，目标节点集D，s和D组成的多播树T(s，D)存在下列关系：定义1路径P的时延为P上各条链路时延的和：D(P)=∑D“，‰)：定义2路径P的代价为P上各条链路代价的和：c(P)一∑c“’yf+。)；定义3路径P的时延抖动为P上各条链路时延抖动的和：，(P)=∑‘，n，‰)；定义4路径P的带宽为P上各条链路带宽的最小值：曰(P)amill(B“，B+。))：定义5路径P的成功传输率为P上各条链路成功传输率的乘积：工(P)。n(1一工以，u+1))；定义6多播树z毫(∥万确夏盖源节点s和多播组D，并且r中每条路径P都能满足约束集c中的一个或多个约柬，r的总代价为c口)。磊co)。由此，可以定义Qos多播路由问题为：网络G∽D，多播源节 北京交通大学硕士学位论文点s∈¨多播目的节点集D￡{阼扣)}，寻找一棵多播树砸J))满足时延约束、时延抖动约束、带宽约束、成功传输率约束、代价约束等约束中的一个或多个。2．2QoS多播路由问题分类从不同的角度，基于Q0s的多播路由问题可以分为不同的类型。本节将从静态与动态、启发式与智能计算、集中式与分布式等方面进行介绍。2．2．1动态算法与静态算法在实际的网络通信中，QoS多播路由可以分为静态多播路由和动态多播路由两种。静态多播路由是针对初始多播组成员来构建多播树，它不能根据当前实际传输量和多播组成员的变化来做路由选择，而是按事先设计好的路由传送信息。但是真实网络中存在很多动念变化，许多多播应用需要网络支持动态多播会话(multic髂tscssion)，例如视频会议和分布式游戏等。这类应用中，用户允许随时加入或退出多播会话，也就是多播组的成员会频繁的改变。支持这种应用需要改变已有的多播树来适应组成员的变化。使用静态多播路由不能适应组成员的这种动态变更，网络资源也得不到有效利用，甚至会导致传送错误。动态多播路由则会针对组成员的频繁变更，处理组成员加入或离开之后多播树的更新闯题。它可以实时地选择路由，适应网络的变化，从而更有效的利用网络资源。1988年，w觚mall【卅首先提出了与多播组成员变化相关的动态多播路由问题，即多播组的成员随时间改变所带来的多播树更新问题， 基于00S的多播路由理论介绍动态多播路由逐渐获得人们的注意。目前动态多播路由在国外已是非常活跃的研究领域，而国内有关这方面的文献相对来说比较少。2．2．2启发式算法与智能计算算法已经证明，多Qos约束的多播路由问题是一个NP完全问题。此外，网络状态信息的不精确性和不确定性对多播路由也有很大的影响，使问题更难于处理。目前，解决该问题的一般方法是采用启发式方法或近似算法。启发式算法搜索的基本原理是【删：对于搜索过程中遇到的每一个节点，按估价函数计算出它的最佳估计值，然后选出当时估计值的最小状态节点，并从该节点开始继续搜索。从该执行过程可以看出，每一个新节点的选择是以当时节点与新节点之间最小估计值为标准，而不是基于整个问题的最小估计值。因此，一般只能找到局部最优解，难以找到全局最优解。所以启发式方法有一个明显的缺点，即缺乏全局观点。另外，启发式方法必须对所解决的问题有较深入的了解，且复杂、难以并行实现，从而无法在大规模的网络系统中实时地找到满意的路由。近年来随着智能计算技术的发展，人们开始把智能计算技术引入到多约束的多播路由问题的求解之中，如遗传算法、模糊逻辑方法、神经网络方法等。其中，遗传算法是近几年提出的一种新型优化算法，它具有并行搜索、自适应群体寻优以及产生一组Pareto最优解集等许多特点，已广泛应用于解决各种肿完全的问趔391。使用遗传算法求解科学研究和工程技术中各种组合搜索和优化计算问题的这一基本思想，首先是由美国Michigan大学的J．Holland教授在20世纪60年代初提 北京交通大学硕士学位论文出，20世纪80年代中期这种思想得到了蓬勃发展。遗传算法的优点在于其简单性、健壮性、并行性、易于实现等，适用于在复杂而庞大的搜索空间中寻找最优解，在搜索过程中自动获取和积累有关搜索空间的知识，自适应地控制搜索过程，不断地缩小搜索空间，从而得到优化解，甚至最优解【381。将遗传算法应用于Qos多播路由选择，可以使得Qos路由选择方法简单、有效。但遗传算法同时也暴露出许多不足和缺陷，针对其不足，近年来又有许多改进的方法出现，其中之一就是将基本遗传算法与传统优化方法相结合的混合遗传算法。蚂蚁系统和蚁群系统则是一种受自然界生物的行为启发而产生的“自然”算法。具体的说，是对蚂蚁或蚁群的行为及其包含的自然规律的研究中产生的。文献[30]中提到对遗传算法和蚁群算法／蚂蚁系统在多约束Qos多播路由问题方面的应用研究的比较，前者不能适应网络的扩展，即不能使扩展后的网络利用其扩展前的网络信息，但后者具有可扩展性。换句话说，当网络的节点数发生变化时，后者在求解QoS约束的多播路由问题时能够利用网络变化前的网络信息而不用重新搜索网络的全部节点。2．2．3集中式算法与分布式算法根据生成多播树的方式，多播路由算法可分为集中式路由和分布式路由两种。集中式路由算法采用了集中处理的方式，利用整个网络拓扑结构和网络状态信息来构造整棵多播树。它需要在网络中的每个节点上都维持一张有关整个网络状态信息的链路状态表，并且周期性的对其更新。这种算法一般都是源路由算法(sour∞-r∞ted袱ltiIIg)，即源节点通 基于Qos的多播路由理论介绍过某个链路协议获得完整的网络拓扑信息，进行路由的计算。集中式路由算法简单明了、易于实旌，缺点在于首先节点在确定路由之前要收集全网拓扑信息，这样易造成链路拥塞，有一定的时延；其次节点要定期更新拓扑信息。以保证不产生回路。分布式路由算法是基于局部状态信息的，其特点在于多播树的计算是由位于不同网络中的多个路由器协作完成的，不需要像集中式路由那样为每个节点都维持一张链路状态表，从而能更好地适应网络规模的动态变化I柏1。其优点如下：1)算法的执行只限于组成员节点，并不是所有网络节点都参与路由算法；2)每个节点只用到局部信息，不需要存在一个存储有整个网络信息的中心节点；3)算法所需的通信费用少，并且建立路由的时间短。而分‘布式算法的缺点在于容易导致环的出现，且计算复杂度比较高。2．2．4单约束算法与多约束算法最优化问题和性能界约束问题是QoS多播路由中的两种最基本的问题【3】。所谓最优化问题就是寻找对应于服务质量度量的最优路径，即在所有的路径中选择对应于度量最好的。而性能界约束问题则是寻找大于对应服务质量度量(如带宽)或小于对应服务质量度量(如时延抖动)的路径，即在满足性能界要求的集合中选择一个解。优化问题要求最优解，磷约束阔题贝lj要求解满足要求即可。将这两类问题加以细分，就得到各种约束问题，下面将根据单约束与多约束分别加以17 北京交通大学硕士学位论文讨论13，蚓。根据单约束条件，Qos多播路由问题基本上可分为：(1)链路约束问题；(2)树约束问题；(3)链路最优化问题；(4)树最优化问题。(1)链路约束问题所谓链路约束就是对于某种度量，寻找使得其上所有链路的对应度量都能满足约束条件的路径。链路约束是属于凹性约束的，对于此类问题可通过从网络拓扑图中删去不合约束要求的链路的方法来解决。例如带宽度量链路约束，寻找的路径的瓶颈带宽要超过约束值。解决该问题的一种方法是把链路约束路由问题简化为链路最优路由问题，即先寻找瓶颈带宽最大的路径，再检查其是否能满足约束条件。如果网络中确实存在满足约束条件的路径，那么最优路径一定能满足约束。另一种方法是拓扑剪枝，即删除带宽小于约束条件的链路，然后从剪枝后的拓扑图中寻找路径，这样，就能找到一条满足链路约束度量请求，但不必是最优的链路约束路由。(2)树约束问题所谓树约束就是指对于某种度量，寻找一棵多播树使得该树上的每一条路径对应的度量都能满足约束条件。树约束是属于加性约束的，此类问题可在多项式时间内求解。例如求具有时延约束的多播树。这是树约束路由问题的一个典型的例子，即寻找一棵多播树，树上每条路径的时延都被限定在一个要求值内。该问题可以直接用Djjkstm算法或Bdllnan-F0rd算法来解决，为约束度量的QoS请求找到的每一条路径都会小于时延要求。 基于Q0s的多播路由理论介绍(3)链路最优化问题所谓链路最优化就是对于某种度量，寻找所对应的度量在所有找到的路径中为最优的路径。链路最优化问题也是凹性约束的，对此可提出来多项式复杂度的方法求解。例如带宽最优路由，寻找在瓶颈链路上有最大可用带宽的路径。链路最优化问题可以通过改进Dijkstra算法或Bcllman．Ford算法来解决。在标准的D独s仃a算法中，选择下一个节点是根据累积的函数值，把到已有树函数值最小的节点加入到路由树上。可阻修改Diikstra算法标准来解决链路最优化路由问题，也就是比较各个节点连接到已有树的带宽，选择带宽最大的节点加入到树上。(4)树最优化问题树最优化就是对应于某种度量，寻找所对应的度量在所有找到的树中为最优的一棵多播树，树最优化问题是加性度量的，此类问题已被证明是NP完全的，无法在多项式时间内求解。树最优路由问题就是著名的Stciner树问题。对于代价度量寻找一棵代价最小的多播树。该问题已知是有NP完全难度的。目前已经提出了很多启发式算法来求解。多约束Qos多播路由问题可以由以上4类问题组合演变而来：(5)链路约束树约束问题；(6)链路约束链路最优化问题；(7)链路约束树最优化问题；(8)树约束链路最优化问题；(9)树约束树最优化问题；(10)多树约束问题等。(5)，(8)类问题在多项式时间内是可解的。如果从网络拓扑结构中移去不满足约束条件的链路，则(6)类问题转化为(4)类问题。(7)(9)类问题已证明是Nl，完全的。 北京交通大学硕士学位论文(5)链路约束树约束问题该问题是由链路约束及树约束组合而来，即对于两种或多种度量，寻找一棵多播树，该树上的每一条路径对应的一种度量值都能满足树约束条件，对应的另一个度量值则满足链路约束条件。例如具有带宽约束和时延约束的路由问题，即寻找一棵多播树，该树的每条路径满足时延约束值，每条路径上的每个链路的带宽都大于带宽度量值。如果满足时延约束的树存在，那么寻找的最短路径多播树必然能满足时延限制。所以可通过修改最短路径算法，在多项式时间内解决该问题。(6)链路约束链路最优化问题该问题由链路约束问题和链路最优问题组合而来，即对于两种度量，找寻一条路径该路径上的所有链路对应一种度量在能找到的路径中是最优的，对应另一种度量则是能满足约束条件。整个问题仍属于凹性约束。例如具有带宽约束的缓存最优路由问题。即寻找的多搔树每条链路的带宽都大于约束值，且每条路径的缓存是最优的。解决该问题首先要进行网络剪枝，删除不能满足带宽约束的链路，然后在剪枝后的网络中按链路最优路由问题的解决方法，找到使另一个度量值最大的路径。由于剪枝操作的复杂度与网络的链路数成正比，因此，链路约束及链路最优路由问题是多项式复杂度。(7)链路约束树最优化问题链路约束及树最优化问题是由链路约束问题和树最优化问题组合而成，即对于两种度量，找到一棵多播树，该树对应于一种度量其值是能找到的树中最优的，对应于另一种度量该树的每条路径上所有∞ 基于Oos的多播路由理论介绍的链路度量值都能满足约束条件。例如带宽约束的代价最小多播路由问题。即寻找一橡多播树，该树上的每条链路的带宽都大于约束值，在此前提下，整棵树的代价是最小的。此类问题可以通过网络剪枝简化为树最优化路由问题来解决，因此问题具有NP完全复杂度。(8)树约束树最优化问题树约束及树最优化问题是由树约束路由问题和树最优化路由问题组合而成的，即对于两种度量，找到一棵多播树，该树对应于一种度量树上每条路径都能满足树约束条件，对应于另一种度量该树是能找到的树中最优的。例如具有时延约束的最小代价多播路由问题。即寻找一棵多播树，该树上每条路径的时延都小于约束值，在此前提下，整棵树的代价是所有多播树中最小的。此类问题也是NP完全难度的，也就是通常所说的约束stcincf树问题。(9)多树约束问题多树约束问题是指对于两种或以上的度量，找到一棵多播树，该树上的路径所对应的度量都能满足各自的约束条件。例如时延和时延抖动约束的多播路由问题。要寻找的多播树上每条路径的时延和时延抖动都小于约束值。该问题无法用简单的剪枝方法来解决，也就是说，该问题在多项式时间内不可解决。2．3多播树的分类一般要求多播服务的业务对带宽和实时性要求较高，涉及用户较 北京交通大学硕士学位论文多，占用的资源也多，因此有必要优化多播路由。多播路由算法就是要寻求最优多播树，理想有效的路由算法将设计一棵仅覆盖多播组成员的树，并体现如下特征：树随着组成员变化动态更新；最小化节点需要保存的状态信息量；避免链路和节点的流量集中；根据费用函数优化路由。多播路由问题根据不同的优化准则及约束条件，需要构造不同的类型的多播路由树。长期以来，人们针对多播树的构造提出了许多算法，但大多数算法都是在几个经典算法的基础上改进而来，其基本思想没有太大的变化。在此，我们简要介绍多播路由树的分类及几个基本算法，它们是其后大多数算法的基础，也是同类算法分析比较的标准。多播路由树有两种类型：一种是有源树，另一种是共享树【41。2．3．1有源树有源树是多播树最简单的一种形式。有源树的根是多播信息流来源，分支形成了通过网络到达接收站点的分布树。有源树也有两种形式：一种是最短路径树(shonestPathTree，简记为sPn，另一种是Stciner树。最短路径树以最短路径贯穿网络，即从源节点到所有多播组成员都是通过最短路径。最短路径树保证了从源节点到每个多播组成员为最短路由，但全树的代价并不一定是最优的，这里树的代价指树中所有链路的代价(这里的代价是一个广义上的代价，它可以根据距离、信道带宽、平均通信量、通信开销、队列平均长度、测量到的时延和其它一些因素的函数而计算出来的)之和。 基于QOS的多播路由理论介绍Dijks仃a算法是最短路径树的典型算法，介绍如下。用cost【i’j】表示弧上的权值，若不存在，则置coSt【i’j】为*。D日kstra算法引进一个辅助向量dist，它的每个分量distIi】，表示当前所找到的从源节点s到每个终点vi的最短路径长度。它的初态为：若从s到Vi有弧，则dist嘲为弧上的权值；否则置dist【i】为oo，显然，长度为dist【j】=min{dist【i】lVi∈V)的路径就是从s出发的长度最短的一条最短路径。S为已找到从s出发的最短路径的终点的集合，它的初始状态为空集。D壮s妇算法步骤如下：1)选择Vi，使得distU】=min{dist【i】IVj∈V—s}vi就是求得的一条从s出发的最短路径的终点，令S=Su{vj}。2)修改从s出发到集合v-S上任意一顶点Vk可达的最短路径长度。如果distD】+cost【i，k】