基于时延约束的改进型实时QoS多播路由算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于时延约束的改进型实时QoS多播路由算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要:多播技术是将特定数据选择性地传送至多个客户端的方法,因而其服务质量是评价其优劣的关键。结合FLSPT算法和贪婪法思想,提出一种基于时延约束的改进型实时qos多播路由算法,它利用启发式策略,使得节点在多播树时能满足时延约束的条件下建立最小代价路径。测试结果表明,采用该算法可获得较小的端到端时延,能改善网络服务质量,适用于成员数目变化频繁的多播应用。

关键词:QRTMRH算法;时延约束;多播路由;服务质量

中图分类号:TP301文献标识码:B

文章编号:1004-373X(2009)10-076-04

Improved Delay-constrained QoS Real-time Multicast Routing Algorithm

WU Weimin,QIN Jun

(College of Media Technology,Nanjing University of Posts and Telecommunications,Nanjing,210003,China)

Abstract:Data can be sent to selective and usually large number of clients by multicast technology.Therefore QoS is the key feature to evaluate such systems.This thesis proposes an improved delay-constrained QoS real-time multicast routing algorithm which combined FLSPT algorithm with the greedy idea.By Heuristic strategy,this algorithm can establish a path with minimal cost which can satisfy delay constraint as any node joining the multicast tree.The testing result proves that this new algorithm has limited end to end delay.It can improve the transmission quality of the network and is suitable for multicast application with variable numbers.

Keywords:QRTMRH algorithm;delay-constrained;multicast router;QoS

0 引 言

当前通信网络在带宽和处理能力上的提高,使它能提供更多的多媒体业务。其中,许多业务均要求网络具有多播能力,如流媒体、音频/视频会议交互式仿真、网络游戏、远程教育、软件分发等,它们对当前的Internet网络提出了新的要求。传统点到点的通信方式,效率较低,而多播允许向一组目的主机同时传送,极大地提高了通信的效率。为了实现多播通信,往往需要建立一棵多播树,信源发出的数据包沿着多播树进行转发,这棵多播树是由多播路由算法决定的。因此,构造多播树的多播路由算法决定了多播的质量和效率。

从用户的角度出发,希望得到具有带宽保证,端到端较低的延迟,小延迟抖动等满足一定服务质量(Quality of Service,QoS)保证的传输服务。而目前的Internet仅能提供尽力而为的服务,不主动为用户提供服务质量保证。按照QoS度量参数的不同性质,可将QoS度量参数分为以下3种:累加型、累乘型和凹型。累加型度量,如端到端延迟等;累乘型度量,如报文丢失率等;凹型度量,如瓶颈带宽等[1]。对于不同类型的QoS度量以及多个QoS度量的组合,其计算代价是不同的。如目前已经证明,基于任意两个或两个以上累加型的或累乘型的多约束条件下的路由选择问题是NP完全问题[2]。

对具体网络而言,设计路由算法时考虑所有度量是不切实际的,因此往往结合实际情况和应用需求来简化问题。例如,在研究传输实时多媒体信息的多播树时,将时延和带宽作为必须保证的条件,费用成为评价网络利用率的重要因素。对于此类业务,在保证时延约束的前提下,可采用在接收端设置缓冲,可降低时延抖动,因此可不考虑时延抖动。目前多媒体网络应用通常具备纠错功能,能容忍一定的丢包率。因此,在研究利用多播方式实时传输多媒体时,可选择时延、带宽、费用三个约束度量。但对于其他应用,如多媒体会议,因其数据传输是实时交互的,时延抖动影响很大,因此这个约束度量是必须的。国内外学者对高质量多播路由算法的研究主要集中在带宽受限的多播路由、时延受限最小费用多播路由、时延与时延抖动受限多播路由和时延受限多播路由等几方面。

1 基于时延约束最小代价的实时多播路由算法

源节点和多个目的节点的集合构成多播组。多播路由算法按其研究网络的组成员是否变化,可以分为静态和动态算法,静态算法不能根据当前实际传输量和拓扑变化进行拓扑选择,而是按最初设计好的路由传送。但是真实网络中存在很多动态变化,动态多播算法可以处理组成员加入或离开后多播树的更新问题,从这个意义上说,动态多播算法显得非常重要。首先多播协议应具备自适应能力,即协议针对路由器出错的情况,能够重新构造最优多播树,并能避免因链路出错而造成的回路问题。其次,由于多播应用需要网络支持动态对话,组成员的变更频繁,为此动态多播算法需要处理成员的加入和离开之后多播树的更新问题。无论以哪种算法构造初始多播树,组成员的动态变更都是使树保持性能最优化的障碍之一。在实时多播应用中,确保成员的加入/退出不破坏正在进行的多播会话是至关重要的。因此,处理实时多播路由问题的常用方法是通过接枝/剪切机制渐进地修改多播树,使得多播树拓扑结构的改变最小化,即每次组成员变化后对树所做的修改都尽可能最小化,以维持路由的稳定性。

目前,国内外有文献对实时多播树的重构问题进行了研究。在加入节点时,动态贪婪算法(Greedy)使用多播树的最短路径,而基于源的最短路径算法则使用多播源节点的最短路径[3],在一定的约束条件下,该算法能较好地工作。DDSP算法(Destination-Driven Shortest Path)[4]采用Dijkstra算法路径递增的基本思想,当源节点到某节点的最短路径不惟一时,它总能选择一条与其他目的节点共享路径最长的最短路径,以降低所构建最短路径树的总消耗,但存在一定的重复计算问题。FLSPT算法(Fast Low-Cost Shortest Path Tree)[5]是通过改变DDSP算法中确定节点的父节点手段,在计算节点可达最短路径长度时保存其最优的父节点,这样做不需要重新搜索,从而减少了计算量。但在Q集合中选择了距源点y的路径最小点u后,如果不把该u点从Q集合中删除掉,就会出现死循环;同时,如果u是目的结点,如果不把该结点从目的结点集合里删除也会出现死循环。与DDSP算法构造的多播树相比,该构造的多播树具有相同的性能,且其时间复杂度低于DDSP算法[6]。

将FLSPT算法和贪婪法思想相结合,提出一种具有低时延、高质量的动态多播路由算法。由于采用了启发式策略,将它称为启发式实时QoS多播路由算法(QoS-based Real Time Multicast Routing Heuristic Algorithm,QRTMRH)。

2 改进的时延约束动态算法――启发式实时QoS多播路由算法

QRTMRH算法主要是将FLSPT算法与贪婪法的思想相结合。当某个节点加入多播树M时,该节点在满足时延约束的条件下,选择到多播树的最小代价路径来加入某个多播会话。若此路径不满足时延要求时,以网络初始化时最小时延路径来加入多播会话。某个成员加入多播树时,若满足时延约束条件时,则代价最小的路径,称为嫁接路径(Graft Path)。若在某个新加入的节点处产生了分支,则称之为嫁接节点(Graft Node)。

对QoS启发式实时多播路由算法(QRTMRH)的描述如下:

(1) 以源节点y作为初始树M。

(2) 以源节点y为根,用FLSPT算法计算出各个节点之间的最小时延路径(以Pdelay表示)和最小代价路径(以Pprice表示),进而计算出各条链路的代价和时延。这样任何两个节点之间都存在两条路径:一条是最小时延路径Pdelay;另一条是最小代价路径Pprice。当成员选择加入多播会话的路径时,如果有两条或者更多路径具有相同的最小代价时,Pprice时延最小的路径优先;与之类似,若有两条或更多路径具有相同的最小时延时,则选择Pdelay代价最小的路径。一种例外是,时延和代价都相等,在这种情况下可随机选择其中任何一个。另外,Pprice和Pdelay可能为同一条路径。根据它们的关系,可得出如下的描述:

price(Pprice) ≤ price(Pdelay)

delay(Pdelay) ≤ delay(Pprice)

(3) 成员加入多播树M的处理过程。通过加入申请操作,一台主机可以随时加入多播会话。初始多播树只有一个节点y,即M0={y}。假设经过k次加入申请操作之后的多播树为Mk,当又有一个新节点v加入当前的多播树时,则多播权为Mk+1,而T为多播树节点的集合。这时可能出现以下两种情况:

①v已在多播树Mk上。则保持多播树Mk不变,即:Mk+1=Mk,Tk+1=Tk∪{v}。

②v不在多播树Mk上。假设多播树Mk上有N个节点,对每个点,因为已计算过其到v的最小时延路径和最小代价路径,所以有2N条不同路径可连接v和Tk。将这些路径按代价升序排列,然后逐个查找,直到找到某一条满足时延要求的路径。假设路径P(k,v)满足上述条件,而k在多播树上,则此时k为嫁接节点,然后将嫁接路径P(k,v)合并到Mk上,生成树Mk+1。

成员加入多播会话可能导致回路的出现。因此在任何嫁接路径合并到已有多播树之前,必须对嫁接路径进行检查,判断多播树上是否已经有节点存在。若存在多播组成员节点在已有的多播树上,则修剪该路径并更新其下游节点的多播路径。对于以上所述关于成员加入的处理过程,用伪代码简要描述如下:

If (vMk) {

miniPrice=∞

For (each k of Mk){

If (delay(Pprice(k,v))+delay(P(y,k))≤Δ) {

//Δ为时延约束条件

If (price(Pprice(k,v))

miniPrice =price(Pprice(k,v))

GraftPath=Pprice(k,v),GraftNode=k

}

}

Else If delay(Pdelay(k,v))+ delay(P(y,k))≤Δ{

If(price(Pdelay(k,v))

miniPrice = price(Pdelay(k,v))

GraftPath= Pdelay (k,v),GraftNode=k

}

}

Mk+1=Mk∪GraftPath

}

}

Else Tk+1=Tk +{v}

(4) 多播树中某个成员离开的处理过程。当某个主机退出多播会话时,可能出现以下两种情况:

①如果节点v不是叶子节点,则只需将它从多播组Tk中删除,之后v不再接收而是只转发信息。

② 若节点v是叶子节点,则从多播树中删除节点v,并停止接受信息。此外还需要删除v的上游节点,直到遇到上游节点具有其他分支或遇到多播成员节点为止。

对于某个成员离开多播组的伪代码描述如下:

Mk+1=Mk

If(v is leaf node){

Remove(v)

While(US(m)&&US(m) has only subnode m) {//US(m)表示m的上游节点

Mk+1=Mk+1-P(m,US(m))

Remove(US(m))

}

Mk+1=Mk+1-P(m,US(m))

}

Tk+1=Tk-{v}

3 算法测试模型及算法分析

为了对上述算法进行测试,采用了由Waxmam提出并经Salama修改的测试模型[7,8]。根据节点间距离的概率来判断网络中的链路是否存在,概率计算函数如下:

ρ(u,v)=αe-d(u,v)/βL

式中:d(u,v)是节点u和节点v之间的欧拉距离;L是节点对之间最大的欧拉距离;α和β是实数类型的参数,且满足α,β∈(0,1)。增加参数α,可以加大网络中链路的密度,提高β可增加较短链路的数量;不同α和β的组合可生成不同类型的网络图。实验中取α=0.3,β=0.3。在每个网络中,链路的时延与链路的长度成正比;边代价和边长度成正比。链路的代价随机取0~10间的实数,各节点的度在2～5间变化。

如果有满足时延约束条件Δ的多播树存在,则至少存在一条从源节点y到多播组成员节点m的路径,其时延小于Δ。Pdelay(y,m)是y到m的路径中时延最小的路径,因此其时延必然小于Δ。也就是说,对于任一多播组成员m,Pdelay(y,m)的时延总是小于Δ。包含这些路径的树就是一个满足时延约束的树。QRTMRH算法总能找到符合条件的多播树。

各节点间的Pprice和Pdelay是事先通过FLSPT算法计算的,QRTMRH算法中大部分的运算时间用于处理节点请求。如果某个节点离开多播会话,则修剪多播树所需的最坏时间为Ο(|T|)。若某节点请求加入多播会话,QRTMRH算法首先找到嫁接节点,再将嫁接路径合并到多播树上,必要时还需要删除回路。其中,寻找嫁接节点的时间为Ο(|T|),计算嫁接路径长度的时间最多为Ο(|V|),因而合并时间最多也是Ο(|V|),而删除回路的时间最多为Ο(|T|)。

4 测试结果

利用上述的测试模型,对QRTMRH算法与KPP算法和SPT算法在不同情况下进行比较。测试时对每个数据点进行100次测试,最终的结果按统计平均值记入。

图1所示为计算时间随成员节点数变化的情况,其中网络的节点数为90,成员节点数从1增加到80。

图1 计算时间随多播成员节点数变化趋势

QRTMRH算法与SPT算法的计算时间随节点数增加而呈线性变化,但SPT的增长速度更慢一些。其原因在于SPT算法只需找到源节点的最小时延路径,而QRTMRH算法要在多播树上找到合适的嫁接节点。此外,KPP算法的计算时间比SPT算法和QRTMRH算法增长速度要快得多。因为无论什么时候只要有新成员加入,KPP算法均要对整个多播树进行计算。

图2所示为不同算法的网络代价随其节点数变化情况的比较。其中成员节点数从20增到220,时延约束Δ取源节点到所有节点的最大时延。KPP算法的代价最低;SPT算法的代价最高;QRTMRH算法适中。对算法进行分析发现,SPT算法只考虑了时延,未进行代价优化;KPP算法对新加入成员的路径都满足时延约束且代价最小;QRTMRH算法对新加入成员的路径可能不是代价最小的路径,却是时延最小的路径。

图2 网络代价随多播成员数目变化趋势

由此可见,QRTMRH算法的计算费用比SPT算法低,但却高于KPP算法。随着成员节点数目增加,QRTMRH算法的计算时间几乎呈现线性增加,而KPP算法计算时间的增长速度比QRTMRH算法快得多。

5 结 语

将贪婪法的思想与FLSPT算法相结合,提出并介绍了QRTMRH算法。测试结果表明,QRTMRH算法得到的多播树虽然不是最优化的,但在较短的时间获取了次优解,在性能和速度间取得了很好的平衡。它可以很好地满足端到端时延约束且成员数目变化频繁的多播应用,是一种值得推广的高效算法。

参考文献

[1]林玉侠,朱慧玲,马正新,等.QoS路由度量参数的选择问题研究[J].电信科学,2003,19(7):26-31.

[2]Li Taoshen,Chen Songqiao,Chen Yan.Research on Anycast Routing Algorithm with Multiple QoS Parameters Constraint[J].Journal of Communication and Computer,2005,2(4):54-60.

[3]陈益峰,何炎祥,曹建农.内容传递网络处理能力受限放置贪婪算法[J].软件学报,2007,18(1):146.

[4]Zhang B X,Mouftah H T.A Destination-driven Shortest Path Tree Algorithm[A].Proc.of the 4th IEEE Int′l Conf.on Communications.Kingston,2002,4:2 258-2 262.

[5]Zhang Baoxian,Kruntz M M,Chen Changjia.A Fast Delay-Constrained Multicast Routing Algorithm[A].Proc. of the 9th IEEE Int′l Conf.on Communications.2001,9:2 676-2 680.

[6]汪维清,汪维华,张明义.低代价最短路径树快速算法的时间复杂度研究[J].计算机工程与设计,2007,22(5):43.

[7]Fujinoki H,Christensen K.The New Shortest Best Path Tree(SBPT)Algorithm for Dynamic Multicast Tree[A].Proc.of the 24th IEEE Int′l Conf.on Local Computer Networks.1999:204-211.

[8]Salama H F,Reeves D S,Viniotis Y.The Delay-constrained Minimum Spanning Tree Problem[A].2nd IEEE Symposium on Computers and Communications (ISCC′97).Alexandria,Egypt,1997:699-703.

[9]李星亮,黄乘顺,傅篱.一种时延受限、低代价的组播路由算法[J].通信技术,2008,41(5):103-104.

[10]王宇,许都,王宏,等.一个效率可观的启发式多约束QoS路由算法[J].计算机应用研究,2008,25(2):345-347.

[11]颜昕,李腊元.多QoS约束的层次多播路由算法框架[J].计算机科学,2007,34(2):27-34.