多约束条件下最短路径QoS路由算法 赵海雁 陈立朝

2004年第25卷第1期

(总第93期)华　北　工　学　院　学　报Vol.25　No.1　2004(.93)文章编号:1006-5431(2004)01-0049-03

多约束条件下最短路径QoS路由算法

赵海雁,陈立潮

(华北工学院计算机科学与技术系,山西太原030051)

摘　要:　多约束的服务质量路由(QoSR)是用来寻找一条同时满足多个约束条件的可行路径,这是NPC问

题.结合线性与非线性度量函数将多个QoS度量转化为单一能量值,给出了多约束条件下层次最短路径的

近似算法.

关键词:　QoS路由;最短路径;Dijkstra算法

中图分类号:　TP393.01　　　文献标识码:A

AlgorithmfortheShortestRouteonMulti-ConstrainedQoSRouting

ZHAOHai-yan,CHENLi-chao

(Dept.ofComputerScienceandTechnology,NorthChinaInstituteofTechnology,Taiyuan030051,China)

Abstract:QoSR(quality-of-servicerouting)isusedtofindafeasibleroutetosatisfymulti-constrainedproblem,whichisaNPcomplexityofQoSR.Themultipleweightsareconvertedtoasinglemetricwithlinearandnon-linearweightfunctions,ahierarchicalapproximatealgorithmforshortestrouteonmulti-constrainedproblemisgiven.

Keywords:QoSrouting;shortestroute;Dijkstraalgorithms

[1]QoS的路由是当前的一个研究热点,它基于Dijkstra算法,并在满足多个约束条件(k>1)的路

径的同时结合线性与非线性度量函数将多个QoS度量转化为单一能量值,实现网络资源的高利用率.通常QoS约束可分为链路约束和路径约束,链路约束可转化为对整个路径上瓶颈链路的约束,通过剪枝预先除去不符合要求的链路,进一步缩小在可行路径间的选择范围.QoS路由的目标是寻找最优的可行路径,它选路的两个任务是:分发网络状态信息;根据网络状态信息,寻求满足给定约束条件的可行路径.1　QoS路由的约束条件

1.1　约束条件选择准则

选路约束条件代表了网络的特征,这是决定QoS路由算法[2]的复杂性,也是提供不同服务质量(Qos)保证互联网络可行路径范围的主要因素.需要考虑的因素主要有:¹对任何选择的约束条件而言,必须存在计算路径的有效算法,以保证路由协议能够扩展至Internet等大型网络;º约束条件必须反映网络的基本特性,并应当包含支持基本QoS需求的信息;»约束条件之间必须是相互的以保证约束条件不包含冗余信息.

1.2　约束条件的性质[3]

QoS路由问题包含多个约束条件,如:时延、带宽、成本、抖动和分组丢失率等.但在设计QoS路由算法时主要考虑时延、带宽、成本三个约束条件.通过修剪不满足QoS需求的所有链路,瓶颈约束条,

50华北工学院学报2004年第1期件可作为预处理步骤来处理,这样就可以仅考虑可加约束条件时延与成本.QoS约束条件分为可加的、可乘的与瓶颈的三种.时延、时延抖动、成本为可加约束条件,分组丢失率为可乘约束条件,带宽为瓶颈约束条件.即cp1=c£ce,cp2=c¤ce,cp3=mince.式中,e表示链路;p表示路径;c表示约束条件.∈p∈pc∈p

2　算法理论基础

2.1　Dijkstra算法[4]

Dijkstra算法是在每次将一个节点加入到部分建好的SPT(最短路径树)时,不仅考虑这一步如何处理最优,在处理这一步之前也同时更深层地考虑后续几步,从而获得一个综合评价较好的方案,然后再根据这个综合方案来进行这一步的处理.它包括以下几个步骤:¹初始化,寻找最优节点u(Extract).º将最优节点u加入到部分建成的SPT(最短路径树)算法的松弛节点u(Relax)中.其中松弛节点u是依次检查哪些所有不在SPT中的邻结节点v.»根据花费的大小,有选择地更改v的父节点以及到达节点v的花费值,从而使v沿着其父节点到达SPT的根节点路径最短.

2.2　算法理论基础[5]

用有向图G(V,E)表示一个网络,其中V为节点集.元素v∈V称为图G的一个顶点,代表网络中具有路由能力的节点,如路由器;E为弧集.元素eij∈E记为e=vi→v,称为图G的一条边(弧),代表网络中的一条链路.在QoSR(服务质量路由)中给每个链路e关联上一组相互无关的权植(w1(e),w2(e),…,wk(e))称为链路e的QoS度量,简写为w(e).其中对1≤l≤k路径约束类型的度量wl(e)∈R满足可加性,即对路径p=v0→v1→…→vn有w1(p)=i£w1(vi-1→vi).=1

定义　多约束路径MCP,对于给定的有向图G(V,E),包含源节点s,目标节点t和k≥2重权值,

+wk(e)∈R,以及约束向量c=(c1,c2,…,ck),从s到t的路径p称为多约束路径.若wl(p)≤cl(1≤l≤k),则可简写为w(p)≤c.+n

3　MCP问题近似算法

3.1　算法思想

QoS路由的主要任务是在当前的网络下寻找满足要求的路径.对于给定的QoS请求,Dijkstra将给出单一度量下计算最短路径树(SPT)算法,它具有较低的算法复杂度.然而,对于MCP问题涉及到同时考虑多约束条件下寻径,那么对于这样的较高的复杂度,NPC就无法使用原有的算法.为了更准确地模型化一个网络,现仅用两个约束条件来简化NPC问题,这个就是“最短度量约束路径”的NPC的简单问题.一种可能的思路是把所有链路约束条件融合成一个能量函数,这样最终可以发现一个能同时最小化所有链路约束条件的解.一种混合约束条件的简单方法是使用线性能量函数(如w(e)=Ac(e)+Bd(e))作为边的新度量.但在非线性路径的情况下,线性路径的度量与路径中所有链路度量的和不相等,即最优路径的一部分不一定是最短路径.在这种最短路径与最小度量不相符的非线性能量函数的情况下,应用k最短路径算法来有效地寻找受时延、成本约束的路径,并把路径的多个约束条件(时延、成本)转化为单一的路径度量(D=kDc+Dd)约束,因而易于实现.此方法的优点是对于不能同时满足时延、成本约束的路径全部被修剪,所以搜索空间得到了降低,优化了搜索空间,提高了运行速度.

3.2　层次最短路径算法

[6]根据上述思想,给出在组合度量l(e)=Aw1(e)+Bw2(e)下使用的层次Dijkstra最短路径算法.除

了寻找在l(e)条件下的最短路径,层次最短路径算法还确定在所有最短路径中wl(p)的最小值.为实现上述任务,就需要对标准Dijkstra算法的松弛过程进行修改.层次算法比标准算法增加了表示不同度量下的最短路径的成本w1[u],w2[u],所有最短路径中w1,w2的最小值为min

(w1[u],minw2[u].

(总第93期)

Relax(u,v)[7]

　If(d[v]>d[u]+l(u,v))then多约束条件下最短路径QoS路由算法(赵海雁等)51

d[v]:=d[u]+l(u,v)　　0d[u]:=v/*u的前驱节点是V*/

w1[v]:=w1[u]+w1(u,v)

w2[v]:=w2[u]+w2(u,v)

min　　min　if(min　　min　if(min　　minw1[v]:=w1[v]w2[v]:=w2[v]w1[v]>minw1[v]:=minw2[v]>minw2[v]:=minw1[u]+w1(u,v))thenw1[u]+w1(u,v)w2[u]+w2(u,v))thenw2[u]+w2(u,v)　elseif(d[v]=d[u]+l(u,v))then

MCP问题的基本近似算法框图如图1所示

.

4　结　论

多约束条件下最短路径QoS的路由算法是NPC问题,至今还没有有效的算法.本文根据QoS选路的约束条件及性质,把单播QoS的路由问题抽象为MCP,并给出MCP问题的高效近似算法.为检测此算法的有效性能,简化了约束条件,设计为两个约束条件,并且把权值按比例缩小来仿真大规模网络.实验结果表明:MCP问题的启发式算法在运行时间上更有效.

参考文献:

[1]　SobrinhoJL.AlgebraandalgorithmsforQoSpathcomputationandhop-by-hoproutingintheinternet[A].IEEE

INFOCOM01[C].AlaskaIEEEComputerandCommunicationsSocieties,2001.727-735.

[2]　WangZ,CrowcroftJ.Qualityofserviceroutingforsupportingmultimediaapplications[J].IEEEJournalonSelect-

edAreasinCommunications,1996,14(7):1228-1234.

[3]　JaffeJM.Algorithmsforfindingpathswithmultipleconstraints[J].Networks,1984,14:95-116.

[4]　崔勇,徐恪,吴建平.性能可调启发多约束路由算法[J].电子学报,2002,30(z1):1968-1972.

[5]　ChenS,NahrstedtK.Onfindingmulti-constrainedpaths[J].IEEEICC′,1998,98:874-879.

[6]　KorkmazTrunzM.Multi-constrainedoptimalpathselection[A].IEEEINFOCOM01[C].AlaskaIEEEComputer

andCommunicationsSocieties,2001.834-843.

[7],[:

本文来源：https://www.bwwdw.com/article/6txe.html