基于改进的负载平衡组播路由问题模型的研究

基于改进的负载平衡组播路由问题模型的研究

1基于度约束最小半径、负载平衡的多目标优化模型近年来，许多研究人员提出了基于ip层集群分布的不足的担忧，并很快成为研究的热点。Overlay组播是在由许多应用层节点(终端节点和代理节点,它们都能承担组播功能)组成的虚拟Overlay网络上进行组播,每个网络上的边都联系着基础物理层中的单播路径。由于虚拟网络是由许多应用层节点构成的,在建立Overlay组播路由时,需要考虑许多因素和评价指标:第一,每个节点支持的连接数不同,需要考虑它们所能支持的连接限制,一般用节点的度来表示。第二,路由算法应该有效地使用网络资源,尽可能多地携带流量。所以带宽消耗的大小是评价组播路由算法的一个主要指标。第三,另一个主要的性能指标是应该尽可能地保证端对端的延迟,即保证组播树的半径最小(组播树的半径定义为源节点到其它节点的最长简单路径)。此外,需要考虑均衡流量负载的能力,否则会造成系统的利用率低和会话拒绝率高。延迟与负载是两个很难调和的量,因为一棵小半径的组播树将导致在中心节点上的流量集中,结果这些节点成了系统的瓶颈;增加整个网络的半径固然会分散负载,但是又将导致路径变长、延迟增加。为此,不同的研究者按不同的指标提出了不同的算法。其中文献综合这几方面的因素和指标,提出了一种半径受限、负载平衡的组播路由问题模型LRRB(LimitedRadius,ResidualBalancedSteinertree):给定无向图G=(V,E),V是应用层节点的集合,E是边(表示节点之间的点到点连接)的集合。对∀v∈V有组播能力的节点的度约束值dmax(v)∈N;边权函数c:E→R+,c(e)表示节点之间的通信代价;给定一个组播树的半径约束值B∈Z+。给定组播源点s∈V,应用层组播路由问题为求解一棵以s为源点的生成树T⊆G满足:其中T为G的生成树;rad(T)为生成树T的半径;TV为生成树T的节点集合。LRRB模型是固定其中一个寻优目标为某个具体值(作为约束条件),然后优化另一个寻优目标。但是,该模型中的负载均衡策略很复杂,属于“极大-极小型”优化问题,求解算法的复杂一般很高。为此,我们改进了LRRB中的负载均衡的策略,同时考虑度约束、最小半径和负载平衡,建立新的多目标优化模型——.度约束最小半径、负载平衡组播路由模型(MinimumRadius,Residual-Balanced,DegreeLimitedsteinertree,MRRBDL),并提出解决问题的相应算法:给定无向图G=(V,E),V是应用层节点的集合,E是边(表示应用层节点之间的点到点连接)的集合。每一个节点v对应一个度约束值dmax(v)∈N;边权函数c:E→R+,c(e)表示节点之间的通信延迟。给定组播源点s∈V,应用层组播路由问题为求解一棵以s为源点的生成树T⊆G满足:其中rad(T)和u(T)分别表示组播树的半径和节点之间负载的不平衡程度(unbalancedegree)。模型式(1)与模型式(2)在衡量一棵组播树的负载平衡程度时的表现如何呢?如何更加合理地计算节点之间的负载平衡程度呢?模型式(2)是通过不平衡程度从反面来刻画平衡程度的,那么又如何计算一棵组播树中各个节点之间的不平衡程度呢?本文就这些问题本文展开了讨论。2负载平衡度的测量2.1节点实际负载评估上述模型式(2)中的u(T)如何计算,即如何具体量化一棵组播树中各节点间负载的不平衡程度呢?先引入两个概念:亏度(deficientdegree)和饱和度(saturateddegree)。一个节点的绝对亏度定义为该节点的最大可承受负载与实际承受负载之差,相对亏度定义为绝对亏度与最大可承受负载的比值;一个节点的饱和度定义为该节点实际承受负载与最大可承受负载的比值。即:绝对亏度(absolutedeficientdegree):相对亏度(relativedeficientdegree):饱和度(saturateddegree):从而,我们可以分别从用所有节点的绝对亏度方差、相对亏度方差、饱和度方差来量化表示节点负载的不平衡程度。然而,由于δvRDD=1-δvSD成立,则D(δvRDD)=D(δvSD),即相对亏度方差等同于饱和度方差,故实际上,所以我们仅需从绝对亏度方差和相对亏度方差两方面进行讨论。于是有其中上标“*”指上标ADD,RDD之任一种。为了减少舍入误差对评价结果的影响,我们引入,则。显然,对u*(T)寻优等价与对U*(T)寻优。2.2不同组播树的负载不平衡程度的计算由式(2),式(3),式(6)组成的是绝对亏度负载平衡多目标优化模型,简记为ADD-LB;由式(2),式(4),式(6)组成的是相对亏度负载平衡多目标优化模型,简记为RDD-LB。当每个节点的最大可承受负载相同时,D(δvRDD)=D(δvADD)/d2max,从而这两种优化模型等价。而一般情况下,它们并不等价。例如,在如图1(a)所示的网络的7棵不同的组播树(如图1(b)-1(h)所示)中,设节点最大可承受负载即最大度序列为dmax={4,4,3,3,2,2,1,1,1},分别用模型式(1)和模型ADD-LB,RDD-LB计算这7棵组播树的负载不平衡程度。部分中间计算结果如表1所示,在不同的最小延迟半径约束条件下,从这7棵树中的择优结果如表2所示。从表2可以看出,按照模型式(1),组播树cT,dT和hT的不平衡程度不可再区分;而按照模型式(2),它们还可进一步区分:在ADD-LB计算模型中,这7棵组播树的不平衡程度从小到大为U(Th)<U(Tf)<U(Td)<U(Tc)<U(Te)<U(Tg)<U(Tb),然而在RDD-LB计算模型中,它们的不平衡程度从小到大为U(Tb)<U(Th)<U(Td)<U(Tc)<U(Tf)<U(e)<U(g)。表面上看,RDD-LB模型评价组播树Tb在此条件下为这7棵组播树中负载最平衡的似乎有些不可思议,然而只要考虑到给定的最大度约束序列,并仔细考察每个节点的超载情况和欠载情况就会明白,组播树bT的总超载为100%,总欠载为308%,是这7棵组播树中超载最小、欠载最大的,换句话说,是最不饱和的,这也反映出本文提出的计算模型的有效性。另外,我们在表3和表4提供了对于随机选取的10种不同的dmax序列(考虑到不同分布,我们选取有代表性的10个最大度序列(分布均匀的、集中的、偏向某个值的,等等)进行分析),分别使用ADD-LB计算模型和RDD-LB计算模型对组播树Tb~Th的不平衡程度的计算结果。在此之前,首先需要引入U值序列等价和相容的概念,以及根据不同模型所得到的择优结果之间的相等和相容的概念。设U1A≤U2A≤≤UlA和U1B≤U2B≤≤UlB为两个U值序列,若对∀i=1,2,,l均有UiA=UiB,则称这两个U值序列是相容的。更进一步,如果两个相容的U值序列U1A≤U2A≤≤UlA和U1B≤U2B≤≤UlB对于∀i,j=1,2,,l,均有:(1)UiA<UjA当且仅当UiB<UjB,(2)UiA=UjA当且仅当UiB=UjB,则称这两个U值序列等价。无论是按照模型式(1)还是模型式(2)对一组不同的组播树进行负载不平衡程度计算,均可得到一个U值序列,择优时就是选择U值最小的组播树。所以,如果两个U值序列的第1个元素相同,那么根据这两个U值序列的择优结果就是相同的,这时称根据这两个U值序列的择优结果相等;如果这两个U值序列的首项元素不同,但是只要在其中一个U值序列中,这两个首项元素对应的U值相等(即这两个首项元素在该序列中无论哪个排在第一位都是可以的),我们称根据这两个U值序列的择优结果相容。结合前面的讨论,以及表2~表4的计算结果,我们可以得出如下结论:(1)模型式(2)比模型式(1)能够更加细致地区分不同组播树的负载不平衡程度;(2)对于模型式(2)的两个子模型而言,RDD-LB比ADD-LB模型能够更加细致地区分不同组播树的负载不平衡程度。当每个节点的最大可承受负载相同时,ADD-LB模型和RDD-LB模型等价,即按照这两个子模型计算的各个组播树的U(T)值的从大到小的序列是相同的;而一般情况下,它们的U值序列并不等价。甚至在某些情况是,模型式(2)的这两个子模型的择优结果是不相容的,即存在组播树1T和2T使得,UADD(T1)>UADD(T2)且URDD(T1)<URDD(T2)。当两种模型的U值序列相容时,它们的择优结果必然相容(但是不一定相等);当U值序列不相容时,它们的择优结果仍然有可能相等(见表4);(3)在某些条件下,模型(1)和模型(2)的择优结果也是不相容的。3组播路由中负载平衡程度的度量本文改进了半径受限负载平衡组播路由问题模型中的负载平衡策略,同时考虑度约束、最小半径和负载平衡,建立了新的优化模型,并提出了节点的亏度和饱和度等概念,详细分析了它们的不同内涵,对Overlay组播路由中的负载平衡程度进行了精细的度量。大量的算例表明,本文提出的模型对于度量组播路由中节点的负载平衡程度是有效的。基于本文所提出的负载平衡程度的计算模型,考虑:(1)给定一棵组播树,对于不同的