路由优化中的费用问题

2001年3月通信学报Vol.22 No.3第22卷第3期JOURNAL OF CHINA INSTTUTE OF COMMUNICATIONSMarch 2001短文路由优化中的费用问题董庆阳况勇李毓麟. (上海交通大学区域光纤通信网和新型光通信系统国家重点实验室上海200030 )摘要本文研究了路由费用"的物理意义"费用”和网络参数之间的关系以及不同的费用"对通信性能和网络运行环境的影响。提出了-种广义费用的概念将费用”的意义明确化。通过仿真结果表明广义费用优化既可改善网络的运行环境,也可提高通信路由的综合性能。关键词路由优化路由费用链路费用不对称网络多播路由中图分类号:TN919.2文献标识码A文章编号:1000- 436X( 2001 )03 - 0109- 051Cost" in optimization of routingDONG Qing-yang ,KUANG Yong L Yu-lin( National Laboratory on Local Fiber-Opic Conmunication Networks & AdvancedOptical Communication Systems Shanghai Jjiaotong University Shanghai 200030 ,China )Abstract :In this paper ,the plhysical meaning of' cost" ,the relation betweenh cost" and networks parameters andthe effect of' cost" on communication performance and operating environments of networks are studied. A gener-al cost is put forward ,which specifies the meaning of cost. The results of simulations indicate that the general costoptimization can improve integrate performance of routing and make operating environments of networks better.Key words routing optimization jtouting cost inetworks with asymmetric link cost imulticast routing1引言计算机通信网络中,通信结点之间路由选择是-个关键问题。对路由进行优化的主要目标是降低路由费用。例如在点到点通信中需要降低两点之间通信路径所占的费用即路径所占链路的费用之和。人们通常以链路长度作为链路费用网络上两个结点之间费用最优的路径:即最短的路径。然而我们通过仿真发现,链路长度并不是最好的链路费用。本文中我们将对链路费用和网络物理参数之间的关系及其对通信性能和网络运行环境的影响进行研究以寻找一个优化的链路费用。由于点到点通信是点到多点通信的一个特例而且点到多点通信的路由优化要比点到点通信的路由优化复杂得多,因此，,我们以点到多点通信(又称多播)的路由优化问题为研究对象。2链路费用不对称网络中的路由优化问题大部分文献1 ~ 4 ]在研究路由优化时都用无向图来描沭网络这是从数学意义上来研究路由优化。但在实际的网络中,网络链路的费用中国煤化工马链路上被预留的带宽作为链路费用全双工链路在上行和下行两个1YHCNMH G定相同即链路费用是不对称的。链路费用不对称网络可以用有向图来描述给定有向图G =( V ,E rc),V是结点收稿日期雨亦数据_ 31修订日期2000- 10-08通信学报2001年集合,E 是有向连接的集合边费用函数c :E→R+( R+表示不包括0的正实数) 1 V|= n,1 E1= m任何属于E的连接e =( u ,v )的存在隐含着连接e' =( v , )的存在(按网络术语,即连接是全双工的)连接e和e'分别对应费用函数( e)(e' ),(e)和( e' )是不相关的。在有向图上寻找-组结点之间费用最低路由(即路由所占的链路的费用之和为最小,又称网络费用最优)归结为Steiner树问题。该问题可以描述为给定非空的结点集合D和源结点s ,DCV ,1 D1= prs∈V\ D求以s为根扩展到D所有成员的多播路由树πs ,D),I( s ,D)cE,>e∈π.0( e )最小。Steiner树是NP完全问题。目前仅有KMB、MPH、ADH等启发式算法2]能在多项式时间内求解该问题,而且这些算法只适用于无向图即链路费用对称的网络。我们对目前最好的启发式算法MPH3]进行改进使它适用于链路费用不对称的网络。改进后的MPH算法称为DMPH算法(directedMPH21)用Dijkstra算法寻找源s到D集合各结点的费用最低路径并以费用最低的路径作为初始Steiner 树T; ,k: = 1 2)Vw∈V% ,V%是T;树上的结点。求w到未加入T的D结点的费用最低路径从中选择费用最低的路径P; ,Tμ←Tn∪P, k= h+1 3)如果k =p算法停止,得到的T,即准Steiner树。否则继续步骤2)如果准Steiner树上有f个结点其中包括p个D结点和f - p个Steiner结点。DMPH算法.需调用f次Dijkstra算法故时间复杂性为0( fin2 )而MPH算法的时间复杂性是0( pn2 )f≥p可见DMPH算法的时间复杂性增加。3链路费用的比较针对链路e ,主要的参数有链路.上被预留的带宽B(e )使用费用P(e入时延D(e)等。B( e )是指链路e上被预留的带宽之和。P( e )是指路由使用链路e所支付的费用,它 与链路长度、通信质量、路由在链路上预留的带宽等因素有关。通常,-个通信进程在路由经过的链路上预留的带宽是相同的并且支付的使用费用和其它链路参数的关系不大为简单起见,可以将链路的使用费用归一化为1[1]即各条链路的使用费用相同。D(e)是指信息通过链路e的时间延迟,包括排队时延、交换时延、发送时延、传输时延等主要是传输时延,它与链路长度有关。3.1预留带宽费用网络中业务量的分布越均匀越好。业务量过于集中容易引起拥塞,导致分组排队延迟增加、丢失率上升等问题。如果以链路上的预留带宽B( e )作为链路费用，那么路由优化算法会尽量选用预留带宽较少即比较空闲的链路作通信路径。这样可以使业务流在网络中的分布较为平均减少业务集中和拥塞的发生。我们通过下面的仿真来进行验证在结点数为20、平均连接度为4的ATM随机网络上针对某通信组规模(组成员数给定组成员随机选择)分别以B( e)D( e)或P( e )为链路费用,用DMPH算法寻找组成员之间的网络费用最优路由树。观察此通信组规模下网络最多能接纳的多播数。网络接纳的多播数越多,说明业务量在中国煤化工选用ATM网络是因为ATM网络具有接入分HCNMHGoncontrol)随机网络的构造方法是网络结点随机分布在一个平面上结点间按概率P。{u ,)}4]进行连接P。{(u,)}= BeadtD)(1)d(u ,心)是结点u和w之间的距离,L是结点间可能的最大距离。开始时网络是空载的。随着通信组数的增多数键路.上被预留的带宽也增加。我们采用一种比较简单的CAC机制:当链路上被第3期董庆阳等路由优化中的费用问题预留的带宽总和大于链路容量的85%则认为该链路已经饱和不能再接纳新的连接5]。如果连接请求使某条链路发生饱和则认为该次连接请求失败。如果失败的连接数占所有连接请求(包括成功的或失败的连接请求)数的15%以上则认为网络已处于饱和状态,不能再支持新的连接了。此时网络上成功建立的连接数即网络最多能接纳的多播数。我们在仿真中使用等效带宽为0.5Mbit/s的VBR视频源。链路容量是155Mbit/so链路时延只考虑传输时延。构造了30个随机网络(式1中a=0.3β=0.6),每个随机网络上进行10次仿真。仿真结果是300次仿真的平均值,它符合置信系数为0.95置信区间和平均值之比不超过5%的要求(置信区间可以用学生氏t方法来估计)图1是在链路费用分别为B(e)DX(e)或P(e)时网络最多能接纳的多播数横坐标为通信组的规模。从中可以看出当链路费用是B(e)时,网络接纳的多播数最多。其次是链路费用P(e)当链路费用是DX(e)时网络能接纳的多播数最少。原因很明显,连接都在寻找较短的链路作路由,这些链路上就容易饱和,产生拥塞。既然链路费2500用是B( e )时网络接纳的多播数最多,那么反言之对于相+预留带宽费用同的多播数如果以B(e)作链路费用时,业务量分布最为2000 '"使用费用均匀。这对于改善网络的运行环境和提高服务质量是非常1500-◆时延费用有利的。3.2使用 费用1000 F如果以链路的使用费用P( e )作为链路费用,那么网络费用最优路由树的使用费用最低,这对于降低网络资源00 t的使用量,减少网络用户支付的使用费用有利。那么以B(e)或D(e)作为链路费用时,网络费用最优路由树的使2用费用又如何呢我们定义几个参数:P( b)是以B( e )作组成员数为链路费用时,网络费用最优路由树R的使用费用,Pr( p)图1网络 支持的多播数是以P(e)作为链路费用时,网络费用最优路由树R的使用费用,PI(d)是以D(e)作为链路费用时,网络费用最优路由树R的使用。显然对于相同的路由请求,P(p)最小。我们在-组结点数为50、平均连接度为4的随机网络(式1中a = 0.2 β= 0.3 )仿真平台上来比较P( 6入PI[ p)和PI[ d )仿真方法是对于相同的路由请求,链路费用分别是B(e )P(e)或D(e)时,计算网络费用最优路由树,再统计各路由树的使用费用P(b入PI{p)和P( d)B( e )是在15和125之间任取的随机数表示网络链路的背景业务量。注意，链路在上行和下行两个方向上被预留的带宽是不相关的,仿真中链路时延只考虑传输时延。P( b)P(p)和P(d)的比较结果如图2所示。可以看出，以B(e)或D(e)作为链路费用时,网络费用最优路由树的使用费用和最优的使用费用相差并不大。可以说路由树的使用费用对链路费用的选取并不敏感。3.3时延 费用中国煤化工如果以链路时延D( e )作为链路费用那么MHcNMHG树是没有意义的。因为人们关心的是源到每个目的地的时延而不是整个路由树的时延之和。我们可以通过目的地平均费用来衡量时延费用。所谓的目的地平均费用,即源在路由树上到各目的地(接收者)的费用的平均值。如果链路赛用是D(e),目的地费用最优路由树的目的地平均时延最低。那么如果以通信学报2001年B(e)或P(e)为链路费用时,目的地费用最优路由树的目的地的平均时延又如何呢?为了比较我们定义:D}(b)是以B(e)作为链路费用时,目的地费用最优路由树R的目的地平均时延;D,(p)是以P(e)作为链路费用时,目的地费用最优路由树R的目的地平均时延;D}(d)是以D(e)作为链路费用时,目的地费用最优路由树R的目的地平均时延。显然对于相同的路由请求,D,[ d )最小。同样在- -组结点数为50、平均连接度为4的随机网络仿真平台上来比较D(b)D}( p)和D( d )，仿真方法和3.2节描述的一样,B( e )仍然是在15和125之间任取的随机数。仿真结果如图3所示。可以看出,D1( b)比D( d )高34%左右。如果B( e )的动态范围扩大这个值也会增大。DK p)比D)( d )高23%左右。也就是说,目的地费用最优树的平均时延对链路费用的选择还是比较敏感的。.15.4F1. 101.3E+----+ D。(b)/D.(d)+ Pr(b)/Pn(p)+.05+Po(d)/Pe(p)1.2上●Dr(P)D。(d)1.00412202836组成员数1.1r41220"2836组戚员数图2使用费用比较图3 时延比较4广义链路费用分析链路费用对于路由性能的影响可以看出单一的参数作为链路费用总是存在-定缺陷。链路上的预留带宽作为链路费用时,网络中的业务量分布比较平均,这对改善网络的运行环境费用有利,但时延特性不能得到改善链路时延作费用时,可以改善路由的时延特性。但容易造成业务量集中;使用费用作为链路费用时,业务量的分布特性和时延特性介于预留带宽费用和时延费用之间。为了进-步提高网络运行的性能,可以将上述几种参数进行综合。综合后的费用可称为广义费用( general cost )简称为GC。我们将预留带宽和时延进行综合。期望它既能使业务量在网络中均匀分布,又能改善路由的时延特性。综合后的费用是Be).. Xe)GC.d e)= λB、+μDm(2)GCu(e)作为链路e的广义费用。λ和μ是两个系数入≥0yμ≥0,它们决定时延或预留带宽在广义费用中所占的比重,λ越大表明预留带宽的作用越明显，如此可以类推μ的意义。B是链路的最大带宽;Dw是源到目的地最大的允许中国煤化工来考察广义费用优化对通信性能和网络运行环境的影响。仿真中λ .YHCN MH G数只具有参考意义,实际应用中还可以根据情况进行调整。例如对时延要求不严格时μ可以取为0。)Bv取155Mbit/s ,Dw取0.04s。链路时延D( e )只考虑传输时延。假设是光纤链路数据在光纤内的传输速率是真空中光速的2/3.我们把网络结点随机分布在3500km x 3000km的平面上,该平面与中国领土的充资陕和大小接近。第3期董庆阳等路由优化中的费用问题113 .4.1业务 量分布将GCm(e)作为链路费用观察业务量在网络中的分布情况。观察的方法仍是看按不同的链路费用优化网络费用时,网络最多能接纳的多播数。定义:A( GCp)是链路费用为GCl(e)时,网络能接纳的多播数;A( b )是链路费用为B( e )时,网络能接纳的多播数;同理定义A( d )和A(p)仿真环境和方法和3.1节描述的一样。仿真结果如图4所示。可以看出链路费用为广义费用GCu(e)时业务量的均匀性比预留带宽作链路费用时略差-些,但比使用费用和时延作链路费用时的业务分布都要好。因此,GC.(e)也可以优化业务量的分布。4.2使用费用我们再来考察GC( e )对使用费用的影响。定义2.0P(GC)是以GCLe)作为链路费用时,网络费用最优-. A(GCu)/A(d)路由树R的使用费用。把它与P( p )作比较。仿真环境和1.5E +t一 -+A(GCw)/A(p) .◆A( GCw)/A(b)方法和3.2节描述的一样,结果如图5所示。可以看出以GC,(e)作为链路费用时网络费用最优路由树的使用费1.0用PI{ GC)和最优的使用费用P[(p) 比较接近。).5CGC( e )可以代替使用费用。21组成员敷4.3时延1.12我们仍利用.图4网络支持多播数比较+ D,( GCx)De(d)目的地费用最优路由树来考察GCu(e)对时延的影响。1.081.06. Pn(GCu)/Pu(p)定义D,(GC)是以GCL(e)作为链路费用时,目的地1.04费用最优路由树R的目的地平均时延。把它与D( d )作1.02比较。仿真环境和方法与3.2节描述的一样结果如图51.0036所示。可以看出,以CGC( e )为链路费用时,目的地费用最优路由树的目的地平均时延D( GCuat )要比最优的目图5使用 费用和时延费用的比较的地平均时延D)( d )高12%左右。但GC( e )可以改善业务流在网络中的分布减少业务量集中和拥塞发生的可能性，这也就降低了分组的排队时延即GC(e)可以从另一个方面降低时延。5结束语论文研究了链路费用和网络参数之间的关系及其对通信性能和网络运行环境的影响对链路的预留带宽、使用费用或时延作为链路费用时对网络运行环境和路由性能的影响并在此基础上提出了广义费用的概念。广义费用将不同的链路参数综合使路由费用的意义明确化,提高了通信的综合性能。我们还为评估费用对通信性能的影响程度提供了-种方法还可以利用这些方法来选择更适合于应用的费用参数。参考文献:中国煤化工[1] KUMAR K B JAFFE J M. Routing to muliple destinations in cu.MHCNMHGCom31( 3)343 - 351.[2] WINTER P. Steiner problem in networks a survey[ J ]. IEEE Networks ,1987 ,1K2):129- 161.[3] TAKAHASHI H ,MATSUYAMA A. An approximate solution for Steiner problens in graph[ J ]. Math Japonica ,1980 24 :573 - 577.[4 ] WAXMAN B M. Routing of multipoint connection[J ] IEEE JISAC ,1988 A( 9):1617- 1622.[5] SALAMA H F ,REEVES D s. Evaluation of multicast routing algorithm for real time conmunication on high-speed network[ J ]. IEEEJSAC 們分数据332 - 345.