基于信源策略树的延迟受限最小代购多播路由算法

基于信源策略树的延迟受限最小代购多播路由算法

1多播路由问题随着ip网络的开发，一些新的多媒体产业出现了，如视频点播、远程分布监测、多媒体视频服务等。这些实时服务要求通信网络为端点和端点的服务质量提供可靠的质量担保，以满足端点用户对服务质量的要求。传统路由机制根据最短路径算法,求解在给定的某个代价准则下的路径,不能很好地支持实时QoS通信的要求。为了支持此类应用,需要寻求满足严格时延约束的有效多播路由算法。因此,设计适应大规模网络运行且满足上述要求的启发式算法,具有重要意义。多播路由最初的研究是无约束的网络代价最小化多播路由问题,大多采用构造树型路由结构实现无约束多点路由。许多研究表明,基于多个不相关可加性度量的QoS多播路由问题是NP完全问题本文研究目标在于寻找基于信源树策略的延迟带宽受限最小代价路由树,同样属于NPC问题。基于信源策略树的QoS多播路由算法已经有不少研究成果,比较典型的有:Wang2多播路由树模型多播路由问题的限制因素不是针对单个路径,而是针对路由树的一个或几个因素,问题的目标是寻找一棵覆盖所有组员的树并使优化目标最佳。根据路由选择策略的不同,目前路由研究的方法围绕着集中式源路由和分布路由进行,它们各有优缺点和适用范围。通信网络可以表示为G=(V,E)。其中V为网络中所有节点的集合,E表示双向链路集,s为多播源点,s∈V,而M⊆{V-{s}}表示多播终点集。t∈M表示多播终点。对于任意一条链路e∈E,定义三种权度量函数,分别是:代价函数cost(e):E→R+;时延函数delay(e):E→R+,以及带宽函数width(e):E→R+R+表示正实数集。则对于给定的源点s,终点t∈M,s和M组成的多播树T=﹤V延迟受限最小代价多播路由树问题可以表述为:对于给定的网络图G=(V,E),多播源点s,目的节点集合M(M={t带宽条件约束:width(P(s,t))≥∆width时延条件约束:delay(P(s,t))≤∆delay且满足式(3)。可以证明此问题的求解是NP困难的3lcmt-k算法3.1最小代价路径为了更清晰的说明我们的算法,首先对点到点时延受限的DCLC-K路径进行定义。大多数点到点路由优化问题都具有这样的特点:好的解是两两“邻近”的;对解作小的改动,就可由一个解移动到另一个解。此类小的改动包括:加一条链路、去除一条链路,小数量的链路被其他链路取代等。最好的情况下,解空间和目标函数都是凸的,此时使用局部搜索技术,往往可以得到全局最优解。通常最小时延路径(minD)并不是代价最小径。在最小代价路径(minC)满足时延要求的情形下,最小代价路径为最优解。反之,最优路径可能为两种情况,一是minD+minC或者minC+minD的两段路径组合,另一种是minD和minC的多段路径组合。我们将最小代价径、最短时延径及它们组合路径中满足时延条件的代价最小路径称为DCLC-K路径,(DCLC:即时延受限最小化代价)简称K路径。K路径中minD和MinC的结合点称为变向点。可以很容易的证明,K路径是自然无环的。对于信源策略的协议来说,使用Floyd算法计算最短时延矩阵和最小代价矩阵以及相应的路由矩阵,K路径可以从上述矩阵中得到3.2最小代价矩阵估计DCMT-K算法采用逐渐向树增加节点的方法,多播目的节点集合为M,向树增加一个节点,多播目标节点集合减少一个节点。步骤1:预处理边,使之满足带宽要求,即将不满足带宽约束要求的边e去除。1)for∀V2)for∀V步骤2:计算网络各节点之间的最小代价矩阵W步骤3:对于∀t∈M,检查delay(P(s,t))<∆,(即检查W步骤4:令M′表示尚未加入到树上的目标节点集合M的剩余节点集合,S表示已经加入到树上的节点集合。Tree负责记录树的拓扑(树枝)。选择节点m对于∀t其中t步骤5:检查对∀v步骤6:检查M′集合。如果M′≠Φ,转到步骤3;如果M′=Φ,则找到了一棵满足式(1～3)条件的树,算法结束。4算法讨论4.1floyd算法本文提出的多播路由算法是基于信源路由策略的,采用了集中处理的方式。即当需要建立满足某QoS(这里指时延受限代价优化)要求的路由时,可以从本地获得预先存在的路由信息,在寻路指令开始到得到结果这段时间无需为计算路径交换信息。从整体时段看,所有的信源策略路由算法都需要经常性的交流网络状态信息,通常可以使用链路状态协议更新节点的全局状态。本文算法首先要采用Floyd算法计算时延和代价的最短径(最小径)及其相应的路由信息阵,然后采用逐渐向主树上增加节点的方法构造多播树。在构造树的过程中将节点划分出两个小子集:多播目标节点V所属集合M,以及信源节点V4.2节点并没有环路的组成和其它逐渐向树上增加节点的多播路由算法不同,本文提出的算法具有自然无环特性,无需为去除环路增加计算开销。下面证明本算法多播树构造过程中无环特性。使用递规方法和反证法证明。1)增加第一个目标节点到树上的过程中没环路产生证明设当前要增加到树上的节点为V2)假设已构造部分没有环路,新增加节点的过程没有环路产生证明采用反证法。如图2所示,使用实线表示已经构造的树,虚线表示即将加入到树上的部分。假设path(Vcostof(path(V而path(V显然相互矛盾,原假设不能成立,即新增节点过程中没有环路产生。由(1)证明了递推的基础成立;(2)证明了递推的延续性存在;所以DCMT-K多播算法自然无环路。5各算法代价及时延限制的仿真本文以VC++高级语言开发的仿真软件包为工具进行仿真,拓扑图生成部分借鉴了Salama博士的方法图3为各算法所求出的多播路由树的代价随节点数的变化情况。仿真得出,网络节点数增加,平均代价缓慢增加,代价指标影响不大。详见表1。图4为各种算法多播树代价随目的节点集合增加的变化情况。仿真表明,随着目标节点数增加,各算法的网络代价逐渐增加,绝对差别拉大,和理论分析相吻合。详见表2。图5为各算法多播树代价随边密度(使用节点平均度数表示)增加的情况。仿真表明,各算法代价指标的差别相对减少,因为随着节点平均度数的增加,两节点间走直接相连的链路可能性增加。详见表3。图6为各算法随时延约束∆放宽多播树代价的变化情况。仿真表明,时延限制对minD多播算法代价没有影响,另外两种算法的代价显著降低(实验中如果时延限制minD不满足,则不计入实验次数。代价取2000次实验平均)。这是因为minD方法组树时根本不考虑代价,所以时限对其总代价无影响;而另两种算法随着时延约束放宽,可供选择的路径增加,各算法依据自身的算法规则选择不同路径的可能性增加,所以代价呈明显下降趋势。可以看到,