带qos约束的多播路由算法研究

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

1、重庆邮电大学硕士论塞笙二童堑笙(2)网络中需要传送的复制信息最少，而且信息的复制只在树叉处进行，从而节省网络带宽资源，提高每次多播通信时的资源利用率，并能减少拥塞，降低网络负载。1．2多播路由算法研究现状为了能够有效地进行多播通信，最关键的就是确定多播路由，而多播路由算法就是用来构建多播路由树的。多播树是通过在每个路由器中设置路由表建立的，路由表给出了为使信息传送到组成员，此路由器应该选择哪一个邻接节点。由于网络存在动态变化的特性，因此每个路由器中的路由表也需要随着网络的变化而进行定期的更新。下面对多播路由

2、算法进行介绍。多播路由算法根据不同的角度和准则可以有不同的分类。按其网络成员是否可以随时加入或离开多播组分为静态和动态两类路由算法。静态多播路由算法中，多播组成员固定不变，路由计算是一次性完成的，并且在一次连接过程中多播成员和路由树都不发生改变，信息只能按照刚开始设计好的路由进行传送。但是在实际的网络中，网络拓扑结构和多播组成员都会经常性的变化，因而动态多播路由算法允许组成员动态的加入或离开，多播树也根据网络拓扑的变化而更新。按是否由一个节点集中运算或分布式运算可分为集中式和分布式两类算法。集中式算法一般来

3、讲都是源节点通过某个链路协议掌握整个网络拓扑结构后，进行路由计算。集中式算法往往快速简单，但是由一个节点维护整个网络的状态，其开销有可能会非常大。并且当网络比较大时，搜索整个网络的状态也会变得很困难。但这些算法可以作为其它算法比较的工具，具有一定的理论意义。分布式算法中网络的每个节点都参与运算，这些节点只掌握网络的部分信息，通过节点间相互交换信息来计算路由。分布式算法相对于集中式算法较复杂且速度慢，但不需要节点掌握整个网络的状态。按是否有QoS约束条件可分为无约束算法和有约束算法两类。许多现有的算法是为非实

4、时网络设计的无约束多播路由算法，它们往往只尽量优化多播树的费用，不考虑QoS约束条件，但实时多媒体应用对QoS约束提出了严格的要求。有约束的多播路由算法通常是在给定QoS约束的条件下尽可能使生成的多播树的费用最小。实际上，一种多播路由算法可以同时属于以上一种或几种分类。总的来说，目前对静态的集中式多播路由算法(包括无约束和有约束)研究较多，而对分布式多2重庆邮电大学硕士论文第一章绪论播路由算法和动态多播路由算法的研究较少。目前大部分算法的复杂度都比较高，很难应用到实际的网络环境中去。静态无约束算法主要有最短

5、路径算法、Steiner树算法以及中心树三类。最短路径算法的典型算法有Dijkstra算法、BellmanFord算法和反向最短路径算法RPF。Steiner树的典型算法有KMB算法【41、MPH算法【5l、ADH算法[61。中心树的主要问题是选择一个合适的中心点，比较典型的中心点选择方案有最佳中心方案、随即选择方案、最大中心树、最小最大路径方案等【7】。静态有约束算法根据不同的约束条件可以分为时延、时延及时延抖动、节点度数等算法。目前，比较典型的时延约束算法有KPP算法【引、BSMA算法【91、CDKS算

6、法【10】等；典型的时延和时延抖动约束算法有DVMA算法【111、DDVCA算法【12]等：节点度数约束的算法主要是F．Bauer提出的带度约束SPH算法【13】。分布式算法和动态算法比较复杂，到目前为止这两种算法的研究成果相对较少。比较典型的分布式算法有GHS算法【14】和分布式SPH算法【151等。典型的动态算法有加权贪婪算法【16】、动态最短路径算法【171、VTDM算法【181、CRCDM算法【19】等。对以上不同类型的算法还可以用不同的方法来运算，例如用遗传算法【20。231、蚂蚁算法【24】等。

7、遗传算法可以用来求解许多领域的各种组合搜索和优化问题。多播路由算法中的Steiner树问题和有约束问题都属于NP完全问题，因此有许多学者尝试用遗传算法来解决多播路由问题，但到目前为止，这方面的努力还不是很成功，这是因为一个图中树的编码空间太大，而这些编码在实际中有极大部分都是不可行解。现有的算法往往结合启发式算法和遗传算法，其算法复杂度肯定要比单纯使用启发式算法高，因此还不如直接使用启发式算法。总的来说，遗传算法要实际应用到多播路由问题中太复杂了，但与之相关的研究还是具有一定的理论意义。1．3多播路由协议要

8、确定多播路由，首先要收集网络中的相关状态信息，基于这些状态信息，多播路由算法就可以确定相应的路由。一般来说，网络的状态信息主要包括网络的拓扑结构、链路和路由器的负载情况、链路和路由器的失效和有效以及网络中路由器的类别(是否具有多播功能)等。这些状态信息的收集是由路由协议(RoutingProtoc01)来完成的。下面，我们将介绍几个在实际应用中比较常见的多播路由协议。重庆邮电大学壁垒茎箜二主笪笙1．3．1距离矢量