路径互联网络

Vol.
13,No.
112002JournalofSoftware软件学报1000-9825/2002/13(11)2065-11互联网络服务质量路由算法研究综述崔勇,吴建平,徐恪,徐明伟(清华大学计算机科学与技术系,北京100084)E-mail:cy@csnet1.
cs.
tsinghua.
edu.
cnhttp://netlab.
cs.
tsinghua.
edu.
cn/~cuiy摘要:如何提供不同的服务质量(qualityofservice,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-servicerouting,简称QoSR)则是其中的核心技术和热点问题.
QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1)满足业务QoS需求;(2)最大限度地提高网络利用率.
由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.
在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.
在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.
最后指出了该领域中需要进一步研究的热点问题.
关键词:服务质量路由;NP完全问题;启发式算法;有效性中图法分类号:TP393文献标识码:A当前Internet只提供尽力发送(best-effort)服务,网络层不区分用户业务的种类,而将网络资源公平地提供给各类业务,在分组丢失、延迟等方面公平地对待各类业务.
这种尽力发送的机制使网络层无法保证传输的参数,然而丢失率、带宽、端到端延迟、延迟抖动等对于应用业务往往是至关重要的.
例如,文件传输业务要求分组的丢失率尽可能低,而传输延迟不是关键因素;实时多媒体业务则更看重延迟和抖动.
这就要求网络能够区别对待各种业务,并对它们提供不同的服务质量.
由于IP是无连接的协议,不要求像ATM网络那样在数据传输前从源到目标节点建立连接.
这种尽力发送的体系结构是无连接、与状态无关的,它既不能支持资源预留,也不能预测传输参数,甚至还可能产生多媒体实时业务不希望的乱序等.
由此,面向服务质量的网络体系结构应运而生.
1服务质量路由概述定义1(服务质量).
服务质量(qualityofservice,简称QoS)是网络在传输业务流时,业务流对网络服务的需求的集合,其中业务流是指与特定QoS相关的从源到目的地的分组流[1].
也就是说,QoS是应用业务对网络传输服务提出的一组可度量的要求,主要包括带宽、端到端延迟、分组丢失率、抖动、花费等.
网络在传输相应的数据业务时,必须满足这组要求.
QoS需求可以通过一个约束集来描述,包括链路约束、路径约束和树约束[2].
链路约束定义了从源到目的地的每一条链路的约束,如带宽约束;路径收稿日期:2001-12-31;修改日期:2002-04-10基金项目:国家自然科学基金资助项目(90104002;69725003);国家高技术研究发展计划资助项目(2002AA103067;2001AA121013)作者简介:崔勇(1976-),男,新疆乌鲁木齐人,博士生,主要研究领域为计算机网络体系结构,协议的仿真和测试,多目标优化的路由算法及其评价;吴建平(1953-),男,山西太原人,博士,教授,博士生导师,主要研究领域为计算机网络体系结构,计算机网络协议测试,形式化技术;徐恪(1974-),男,江苏洪泽人,博士,讲师,主要研究领域为计算机网络体系结构,计算机系统性能评价;徐明伟(1971-),男,辽宁朝阳人,博士,副教授,主要研究领域为计算机网络体系结构,计算机网络性能评价,协议测试.
2066JournalofSoftware软件学报2002,13(11)约束定义了从源到目的地的一条路径上端到端QoS需求,如延迟;树约束定义了对组播中整个组播树的约束,例如对组播树延迟的约束是对树中从源到所有目的地的路径中最大延迟的约束.
定义2(可行路径(可行树)).
可行路径(可行树)是网络中从源到(所有)目标节点的一条路径(组播树),并且该路径(树)具有足够的尚未分配的资源,能够满足特定的QoS需求.
定义3(服务质量路由(QoSR)).
服务质量路由(QoSrouting)是一种基于数据流QoS请求和网络可用资源进行路由的机制[1].
或者,QoSR是一种动态路由协议,并且在其路径选择标准里可能包含可用带宽、链路和端到端路径利用率、资源消费量、延迟、跳数以及抖动等QoS参数[3].
当前Internet的主要路由协议都是"尽力发送"的,选择路由时即便源到目的节点之间存在"更好的"路径,只要不是最短路径就不会投入使用,因此可能导致某些链路空闲时另外一些链路的拥塞.
QoSR路由就是将传统的最短路径变为一条更好的路径,其主要目标包括以下两点[1]:(1)为每一个接纳的QoS业务连接请求,找到满足其QoS要求的可行路径(组播树);(2)优化全局资源利用率,平衡网络负载,从而最大化网络接受其他QoS请求的能力.
为了提供QoS保证,数据传输前通常需要沿着计算好的路径,从源到目的地传播一个消息,用来通知路径上的所有节点为这个QoS业务保留相应的资源(如带宽、缓存等),而后续的数据传输则沿着这条已经预留了资源的路径.
因此,QoSR具有面向连接的特性.
根据计算可行路径的时刻,QoSR可以分为预计算和在线计算两种.
预计算(pre-computation)采用一个后台进程,根据网络状态信息来构造路由表,当QoS请求时,只需通过查找路由表就能确定可行路径[4].
在典型网络设置中,QoS连接请求的到达速率远大于网络的变化速度,因此可以使用预计算模式[5].
由于QoS业务的多样性,路由表为了包含每个可能的QoS业务,其规模会相当庞大因而降低了可扩展性.
在线计算则是当QoS请求到达时,再根据状态信息计算可行路径.
这种方式虽然不需要事先构造路由表,但每次路由计算延迟较大,并且路由器负担很重.
QoSR问题很难完全解决的原因包括:(1)寻找同时满足两个以上路径约束(优化)的可行路径,具有NPC(NP-complete)的计算复杂度[6];(2)为了提高可扩展性所使用的层次化模型,产生了多种参数如何聚集的问题[7];(3)网络状态信息的陈旧性极大地影响了QoSR算法的性能[8];(4)将QoSR融入到当前这种尽力发送的路由体系结构中,原有的尽力发送业务将受到巨大的冲击.
2网络模型和QoS度量2.
1有权图模型网络由交换节点、链路和主机组成,在研究当中往往将其抽象为有权图G(V,E).
定义4(有向图).
有向图G是由一个非空有限集合V(G)和其中某些元素的有序对集合E(G)构成的二元组,记为G=(V(G),E(G)).
其中,V(G)称为图G的节点集,元素v∈V称为图G的一个顶点或节点;E(G)称为图G的边集,元素eij∈E记为e(vi,vj)或eij=vivj,为V中元素的有序对,称为图G的一条从vi到vj的边(弧).
定义5(有权图).
在有向图G=(V,E)中,令元素e∈E具有一组有序数列(w1,w2,…,wk)作为e的属性,则称G为有权图,其中(w1,w2,…,wk)称为弧e的度量(权值).
节点集V可以表示路由器、交换机、集线器等网络节点设备,在研究路由问题时,V中的元素为具有路由能力的交换节点;E则为连接V中两个节点的链路及具有的k个属性(w1,w2,…,wk),这些属性可以是可用带宽、延迟、队列长度、花费等参数.
对于对称网络有eij(w1,w2,…,wk)=eji(w1,w2,…,wk),而不对称网络中通常eij≠eji.
现实中的网络往往是不对称的,但在研究中为了简便起见,常常使用对称网络模型以减少弧的数量[9],本文亦如此.
如图1所示为一个有权图模型.
Linkstate=(Delay,Bandwidth,Cost)①(6,2,2)(5,3,3)(1,1,3)(3,2,3)(2,4,2)cde(4,2,3)ba(1,4,8)(1,5,7)①链路状态属性=(延迟,带宽,花费).
Fig.
1Weightedgraphnetworkmodel图1有权图网络模型崔勇等:互联网络服务质量路由算法研究综述2067定义6(路径).
在图G中,如果对i=1,2,…,k1有vi,vi+1∈E,则P=(v1,v2,…,vk)为图G的一条从v1到vk的路径,也记作P={ei,i+1|i=1,2,…,k1}.
QoSR的目标就是选择一条从源节点v1到目标节点vk的可行路径P,使其满足业务QoS要求.
例如,图1中从节点a到节点c的路径有(a,b,e,c),(a,d,c),(a,e,c)等.
2.
2QoS度量QoS要求需要通过可测量的QoS度量来实现.
常用的几种QoS度量主要包括可用带宽、端到端延迟、分组丢失率、抖动和花费,不同的度量具有不同的性质.
按照这些性质,QoS度量可以分为可加性度量、可乘性度量和最小性度量3类.
对于图G中的路径P=(v1,v2,…,vs),若ei,i+1∈P(其中i=1,2,…,s1),将ei,i+1的第j个属性记为或,整个路径P的第j个属性记为w,则以上3类度量的定义如下jiiw1,+)(1,+iijewjP[10]:定义7(可加性度量).
若,则称路径P的第j个属性为可加性度量.
∑=+=111,sijiijPww可加性度量包括延迟、抖动、花费、转发跳数(hopcount)等.
例如,一条路径P的延迟为从源到目的地的所有链路延迟的总和.
如图1中路径(a,b,e,c)的延迟总和为3,花费为18.
定义8(可乘性度量).
若,则称路径P的第j个属性为可乘性度量.
∏=+=111,sijiijPww例如,分组丢失率为可加乘度量,其中链路丢失率.
在求解有关可乘性度量的过程中,可以类比参照可加性度量的有关求解方法101,≤≤+jiiw[11].
定义9(最小性度量).
若,则称路径P的第j个属性为最小性度量.
}{min1,1,.
.
.
2,1jiisijPww+==例如,带宽为最小性度量,即路径带宽为路径上瓶颈链路的带宽.
如图1中路径(a,b,e,c)的带宽为1(其中链路(b,e)为带宽瓶颈).
对于求解的问题可转化为问题.
对于不同类型的QoS度量以及多个QoS度量的组合,其计算的代价是不同的.
例如,求解多重最小性度量的组合可以在多项式时间内完成,而多重可加性度量的组合通常不能在多项式时间内完成.
}{max1,1,.
.
.
,2,1jiisijPww+==}{min1,1,.
.
.
,2,1jiisijPww+==3单播QoSR算法按照所求解的问题类型和求解方法,QoSR算法可以分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.
其中概率求解类的一个主要方面是对信息陈旧性和算法有效性的考虑,我们将在第4节加以分析.
3.
1多项式非启发类多项式非启发类算法针对的并不是典型的QoSR问题,而是多项式可解的问题,但是这类问题及其求解思路是QoSR算法的基础.
Wang和Crowcroft使用Dijkstra最短路径树算法实现了带宽延迟受限的源路由求解[12].
首先在网络拓扑图中将带宽不足要求的链路剪除掉,然后再以延迟为关键字使用最短路径树算法计算,这样求得的路径满足带宽约束并具有最短延迟.
此外,他们对最短最宽路径提出了分布式预计算方法.
两个节点间的最宽路径是指在这两个节点之间所有的路径中,瓶颈带宽最大的路径[12,13].
最短最宽路径(shortest-widestpath)是指在多条最宽路径中最短的路径.
算法中每个节点通过链路状态协议维护全局状态,并使用扩展Bellman-Ford算法[14](或Dijkstra算法[15])为每个可能的连接目的地预先计算出下一跳,这样,在连接请求时只需简单地查找路由表.
这个算法在各个节点网络状态信息一致的情况下可以保证无回路.
3.
2QoS度量相关如果所有的QoS度量都与某一类度量相关,那么QoSR问题也可在多项式时间内求解.
基于这种思想,Ma-steenkiste证明了当网络中使用一类加权公平队列(WFQ)(如调度算法[16])时,端到端延迟、抖动、队列长度等都是带宽的函数,而不再彼此独立,这样,原来多约束的NPC问题就有可能简化[17].
考虑到这些参数的相关性以后,通过扩展的Bellman-Ford算法在多项式时间内就可以通过源路由策略求解.
Orda对基于速率调度的2068JournalofSoftware软件学报2002,13(11)QoSR算法做了较为全面的研究[18].
每个节点通过广播可用速率代替传统的可用带宽等状态,将延迟保证映射为速率保证.
通过执行至多M次标准最短路径树算法,能够找到端到端延迟受限的路径,并能够满足抖动等其他方面的约束[19].
但是这些分析对传输延迟是无效的,因此往往限定在高速网络中[20].
3.
3探测法探测法的思想是从源节点开始,通过逐个询问其他节点,逐步逼近并到达目标节点.
算法通常基于广播和多路路由的机制,在多条路径中寻找可行路径;在询问抵达目标节点之前不能断定可行路径.
为了避免回路和扩散重复信息,节点需要记录大量探测数据.
此外,探测法需要较长的路由时间,但它可以有效地与资源预留相结合.
在Cidon等人提出的分布式多路路由算法[21]中,每个节点维护全局状态,根据QoS请求,首先找到多条花费合理的路径,控制信息(资源预留)并行地通过这些路径从源发送向目的节点,直到抵达目的节点时完成连接的建立.
在多条路径上同时预留资源可能会加快路由速度,但大大增加了网络的动态变化性.
该算法的一些变体着重于研究如何折衷路由时间和路径优化.
Shin和Chou设计了延迟受限的分布式算法[22].
每个节点不需要保存全局状态,而通过广播方式从源向目的节点传送累加了延迟的路由信息.
中间节点在收到路由信息时,首先累加自己的延迟,如果仍然小于规定的延迟,则再转发给其他邻居.
但是收到的路由信息必须满足以下两个条件之一:(1)它是第一次收到该信息;(2)信息中累计的延迟比该节点原来收到的要小.
路由信息的扩散路径就是延迟受限的可行路径.
若给路由信息设置适当的优先级,并使用特定的调度算法,则可以保证在每条链路上最多发送一次这种路由信息.
为了降低上述Shin-Chou算法的通信开销,Chen和Nahrstedt提出了一种分布式路由的框架[23]:(1)根据到目的节点的拓扑距离,探测只在一个有选择的子集上转发;(2)限制路径长度并在探测失败时动态地增加这个长度.
这种算法实际上是在路由时间和通信开销之间选择的折衷,因为探测失败时,会增加路由时间和通信开销.
如果在每个节点保存了全局信息(即便不准确),并为源节点赋予一定的票(ticket)数,每个探测至少需要具有一票,则上述算法可以获得更好的性能[24].
3.
4扩展距离向量算法扩展Bellman-Ford算法(EBFA)就是一种典型的用于求解多重受限QoSR问题的伪多项式非启发类算法[25].
由于很多求解该问题的启发式算法都是基于EBFA的[26,27],因此这里首先介绍EBFA.
定义10(路径偏序关系""和"=".
偏序关系中并不是任意两个元素Pwv和Qw都必然存在""和"="3种关系中的一种,例如,)3,2,1(=Pwr与)1,2,3(=Qwv之间不存在其中的任意一种关系.
定义11(最优路径).
设P是从源节点到目标节点的一条最优路径,如果不存在从源节点到目标节点的路径Q使得,则称P为一条最优路径.
PQwwvv互联网络服务质量路由算法研究综述2069个数,则相应的算法复杂度为O.
∏=ikiXEN2||||,.
.
.
,2,1{=′xCiλ+kkcPw)(wChen和Nahrstedt设计了多重路径受限的源路由算法[28].
算法的思想是将QoS度量的取值范围R或Z映射到一个有限集合C,从而保证多项式可解.
以花费Cost为例,设C为最大花费约束,x为一个小于C的正整数.
算法将每个链路的花费映射到集合中,其中属于区间[0,C]的花费映射到中,属于区间的花费映射为(x+1);花费C映射为x.
可以证明,满足新问题的可行路径在原来的问题中也是一条可行路径,而新问题可以通过扩展Dijkstra算法或者扩展Bellman-Ford算法,在多项式时间内求解.
算法的性能与x密切相关:随着x的增大,找到可行路径的概率也增大,但同时引入了更大的开销.
因此,可以通过选取x来调节该算法的性能.
}1+},.
.
.
,2,1{x),(+∞C对于延迟受限的最小花费问题(DCLC),存在一些伪多项式时间的近似算法[29,30].
对于任意0>ε,存在一个多项式时间的算法能够找到一条路径,在满足延迟受限的同时,其花费不超过最小花费的)1(ε+倍.
由于这些算法的计算复杂度与ε有关,因此被称为伪多项式算法.
例如,Lorenz算法的复杂度为+εnmnmOnloglognlog[30],其中m,n分别为网络的节点数和边数.
Orda等人设计了通过量化花费函数的预计算算法[5],该算法针对多重可加性约束的路径优化问题,基于通用Bellman-Ford算法,将计算复杂度减小到CHmOlog1ε,其中H为最长路径的跳数,C为路径花费的上限.
3.
6路径子空间搜索路径子空间搜索是指通过启发式算法,直接限制路径数量,从而在路径集合的子空间中搜索可行路径的方法.
这种方法在源节点或者中间节点就可以计算出可行路径,而不需要像探测法那样一直询问到目的节点,因而具有较高的启发性.
Yuan和Liu设计了路径受限的多重路径受限的分布式算法[27].
他们在EBFA中直接限制|PATH|的大小从而减小算法复杂度.
令X为|PATH|最大数目,在原EBFA算法向PATH加入一条最优路径之前,判断是否满足|PATH|通过这样简单的限制,能够保证算法复杂度为O(X2|N||E|).
他们通过试验数据说明了路径受限算法性能大大优于粒度受限的算法.
Salama等人对复杂度为NPC的DCLC问题设计了分布式启发算法[31].
与EBFA类似,为每个可能的目的网络,每个节点保存一个花费向量和一个延迟向量.
为建立DCLC可行路径,源节点向目的节点发送一个控制信息,已经部分建立的可行路径的末端节点i收到该信息后,将信息继续向目标节点传递.
设(i,j)是从i到目标节点的最小花费路径中下一跳的链路,(i,k)为最小延迟路径中下一跳的链路,则传递规则是:只要加上从节点j开始的最小延迟路径仍然满足QoS约束,节点就选择(i,j);否则选择(i,k).
由于算法本质上可能产生回路,因此他们设计了检测回路以及遇到回路时回退的方法.
3.
7花费函数为了降低QoSR算法的复杂度并提供更好的QoS支持,一种可能的方式是通过研究花费函数,从而保证所计算的最小花费路径能够满足QoS需求.
例如,通过将链路花费与利用率结合,能够降低连接阻塞概率,抑制路由抖动[8].
Korkmaz等人设计了一种在多个可加性约束的条件下求解优化路径的通用算法[11].
算法首先构造路径花费函数λλ+=cPwPg.
.
.
)()(11,其中为路径P的第i维属性,为一个业务流所对应的QoS要求.
最小化花费函数所找到的路径,为多重受限QoSR问题提供了一个连续的近似频谱:从)(Piic1=λ的线性近似,到∞=λ时的渐近近似.
因此,原来的多约束QoSR问题转化为最小化所对应的路径问题.
)(limPgλλ∞→Ergun等人设计了一种启发式算法,使得一条链路基于不同的花费能够提供不同的延迟[32].
该算法的思想是将传统的DCLC问题分解为两个问题:(1)使用传统方法找到一条可行路径;(2)将整个路径的延迟分割成2070JournalofSoftware软件学报2002,13(11)路径中每个链路延迟的约束,从而得到路径的最小花费.
文中对这两个问题分别设计了ε优化的近似算法.
对于分割求解的方式,Lorenz等人研究了花费函数为连续凸函数时的分割方式[33];Raz等人研究了花费函数为离散函数时的分割方式[29].
Fortz等人研究了如何根据测量结果设置路径权值,从而使OSPF协议所计算的最短路径能够平衡负载并满足QoS需求[34].
Juttner等人基于拉格朗日松弛法设计了DCLC的源路由求解算法[35].
算法首先构造路径花费函数)()()(PdPcPg+=λλ,其中c为原来的花费,)为路径P的延迟,0(Pd≥λ.
然后以为关键字使用Dijkstra算法计算最短路径P,如果)(Pgλ0=λ且同时P满足延迟要求,则P为原DCLC问题的最优解;如果P不能满足要求则可通过增大λ而加大对的惩罚力度,求得满足延迟要求的路径.
令)(PgλDtsPPPLgλλλ∈=)},(|)()(min{,其中D为延迟要求,则对0≥λ有)(λL为原DCLC问题的花费下界.
算法通过计算特定的λ从而最大化)(λL,得到花费下界,并给出一条可行路径.
3.
8算法小结为了降低复杂性和提高性能,有些QoSR算法将以上几种思想结合起来.
例如,将花费函数与概率模型结合,以概率相同的方式分割路径花费[29];将路径子空间搜索与探测法结合,在搜索失败的情况下回退探测[31];QoS度量相关与花费函数的ε优化结合[5]等.
此外,多类算法中都使用到ε优化的方法.
表1给出了单播算法的比较,每个算法以第一作者命名,状态信息表示计算QoSR的节点需要收集和维护的网络状态信息的类别,其中部分算法将在第4节进行分析.
4算法有效性分析一个QoSR算法首先要在理论上保证避免回路(或者能够检测排除回路),然后还需要进一步考虑实际网络的情况,包括网络模型、路由信息是否陈旧等问题,才能够保证算法是实际可用的.
4.
1路由回路问题在Salama等人所提出的算法[31]中,由于控制信息可能在最小延迟路径和最小花费路径之间不断变化,因此可能造成回路,这就属于算法本身理论上的缺陷.
在文献[31]中采用检测回退的方法来解决这个问题:当控制信息对同一节点访问两次时,说明算法产生了回路.
这时回退路径选择过程,直到找到一个原来在其后使用最小花费路径的节点,将该节点原来沿最小花费路径传递改为沿最小延迟路径传递.
可以证明,在所有节点网络信息一致的前提下,这种机制能够消除回路[31].
Sobrinho通过代数学方法详细研究了分布式QoSR中路由回路和最短路径问题[36].
文献[36]定义了链路度量的二元操作和一个抽象的全序关系以及在这个关系中路径度量的保序性.
其中保序性是指,对任意两条路径P,Q,如果给这两条路径P,Q同时追加上路径L时,在序关系中,P和Q的关系与(P+L)和(Q+L)的序关系相同,也就是说,追加过程不改变原来路径度量的序关系.
该文证明了路径中QoS约束的度量函数的保序性是使用Dijkstra算法计算最短路径的充要条件;否则,计算过程中有可能产生回路.
4.
2陈旧信息的影响在研究QoSR问题时,通常假设每个节点已知本地状态信息,并通过协议交互获得全局状态.
然而,这些状态信息是不精确的[37],其原因包括以下4个方面:(1)在传播本地状态的过程中,存在不可忽略的网络传输延迟和协议交互延迟;(2)网络状态是不断更新的(如可用带宽、延迟),考虑到传输网络状态信息的开销,所以路由更新间隔不可能无限小(定期更新的时间间隔或者触发更新的触发门限);(3)链路度量的粒度往往在路由计算开销和阻塞概率之间折衷;(4)层次化的网络结构造成信息压缩.
对于前两方面所造成的网络状态信息在时间上的不精确性,我们称为陈旧性.
为了讨论陈旧信息对算法性能的影响,需要区分路由失败和建连失败的概念.
路由失败是指根据所保存的网络状态信息和新的QoS连接请求,无法计算出可行路径.
建连失败是指,虽然算法计算出了可行路径,但是实际上由于信息的陈旧性,该路径已经不能够支持这个QoS连接.
建连失败通常是沿着这条不可行路径预留资源时发生的,因此导致了额外开销以及对其他QoS请求的阻碍.
崔勇等:互联网络服务质量路由算法研究综述2071Shaikh等人发现若信息的陈旧性小,则计算DCLC路径时应该使用剪枝的机制;否则不应使用剪枝机制[8].
此外,随着陈旧性的增加,路由失败的概率减小而建连失败的概率迅速增加.
为了避免陈旧性,一种方式是基于本地状态路由[23,38],如Shin等人设计的分布式探测算法[22].
Nelakuditi等人设计了网络边缘路由器根据业务流阻塞的统计数据计算可行路径的方法,能够将业务流均衡地分配到网络上[38].
Table1ThecomparisonofUnicastQoSRalgorithms表1单播服务质量路由算法的比较Algorithm①Problemtosolve②Routingstrategy③Computationcomplexity④Stateinformation⑤Heuristicclass⑥EBFA[25]Multiplepath-constrained⑦Distributedrouting⑧Pseudo-Polynomial⑨Global⑩Non-heuristic⑾Cidon[21]Generalproblem⑿DistributedroutingO(e)GlobalDetection⒀Shin[22]Delay-Constrained⒁DistributedroutingO(e)Local⒂DetectionChen[28]Bandwidth-Constrained⒃Sourcerouting⒄O(xne)GlobalDetectionYuan[27]Multiplepath-constrainedDistributedrouting∏=ikiXnO2eGlobalQoSmetric-constrained⒅Chen[23]GeneralproblemDistributedroutingO(e)LocalQoSmetric-constrainedOrda[5]Multiplepath-constrainedoptimal⒆DistributedroutingO(Polynomial/ε)⒇GlobalQoSmetric-constrainedε-optimal(21)Yuan[27]Multiplepath-constrainedDistributedrouting)(2neXOGlobalPathsubspacesearch(22)Salama[31]Delay-Constrainedleast-cost(23)DistributedroutingO(n3)GlobalPathsubspacesearchMa[17]Multiplelink-constrained(24)SourceroutingO(kne)GlobalQoSmetricsrelated(25)Ma[17]Bandwidth-ConstrainedSourceroutingO(nlogn+e)GlobalQoSmetricsrelatedOrda[18]Delay-Constrainedleast-costDistributedroutingPolynomial(26)GlobalQoSmetricsrelatedKorkmaz[11]Multiplepath-constrainedoptimalpathSourceroutingPolynomialGlobalParticularcostfunction(27)Ergun[32]Delay-Constrainedoptimal(28)SourceroutingO(Polynomial/ε)GlobalCostfunctionpartitionedε-optimal(29)Raz[29]Multiplepath-constrainedSourceroutingeenOlog13εGlobalCostfunctionpartitionedε-optimal(30)Juttner[35]Delay-Constrainedleast-costSourcerouting)log(42mmOGlobalLagrangerelaxation(31)Wang[12]Bandwidth-ConstrainedSourceroutingO(nlogn+e)GlobalNon-heuristicWang[12]Optimalbandwidth(32)DistributedroutingO(ne)GlobalNon-heuristicGuerin[39]Bandwidth-ConstrainedSourceroutingO(nlogn+e)Global(imprecise)(33)Probabilitysolution(34)Guerin[39]Delay-ConstrainedSourceroutingPolynomialGlobal(imprecise)ProbabilitysolutionLorenz[40]Delay-ConstrainedSourceroutingO(De)Global(imprecise)Probabilitysolutionε-optimal(35)nisthenodenumber,mistheedgenumber,Xisthenumberofoptimalpaths,kistheconstraintnumberofmultiplepathconstraints,andDistheupperboundofdelay(delayisapositiveinteger)(36).
①算法名称,②所解决的路由问题,③路由策略,④时间复杂度,⑤状态信息,⑥启发式类别,⑦多重路径受限,⑧分布式路由,⑨伪多项式,⑩全局,⑾非启发式,⑿一般问题,⒀探测法,⒁延迟受限,⒂本地,⒃带宽受限,⒄源路由,⒅限定QoS度量,⒆多重路径受限优化,⒇O(polynomial/ε),(21)限定QoS度量ε优化,(22)路径子空间搜索,(23)延迟受限最小花费,(24)多重路径链路受限,(25)QoS度量相关,(26)多项式,(27)特定花费函数,(28)延迟受限优化,(29)分割花费函数ε优化,(30)分割离散花费函数ε优化,(31)拉格朗日松弛,(32)带宽优化,(33)不精确全局,(34)概率求解,(35)概率求解ε优化,(36)n为节点数,m为边数,X为最优路径的数目,k为多重路径约束的约束个数,D为延迟的上限(延迟为正整数).
4.
3网络模型的影响研究者们往往通过模拟试验对所设计的QoSR算法进行性能评价,然而不同的模型可能导致不同的评价结果,而模型对算法性能的影响还可能进一步反馈到算法的改进中.
由于Internet缺少典型的拓扑结构和业务流,因此网络模型的选择非常困难[41,42].
常用的拓扑模型包括[42]:(1)众所周知(Well-Known)的拓扑结构,如MCI骨干网[27]、ARPAnet等;(2)随机生成的拓扑结构,如平面随机图[35]、Transit-Stub模型[7]、层次化模型等;(3)特定规则的结构,如网格结构[27]、完全图等.
Shaikh等人通过模拟试验[8]说明,在链路密集的网络中,由于网络直径相对较小,以及对QoS请求的连接通常可以找到较短的可行路径,因此应该减少网络状态更新的次数(增大更新周期或触发间隔).
同时,由于链路密集造成的每次广播开销很大,应该考虑使用支撑树的方式转发状态信息.
2072JournalofSoftware软件学报2002,13(11)业务流的模型应该包括QoS连接请求的到达方式、QoS连接的持续时间、QoS参数的分布等.
Shaikh等人的研究结果表明[8],应该仅对持续时间较长的连接采用QoSR寻找可行路径,而对于短时间的业务应该基于事先提供静态路由进行转发.
比较重尾(long-tailed)分布和指数分布的连接时间,当平均连接时间相同时,重尾分布具有更多的短期连接,因此更有必要在网络边缘检测短时间连接,以便仅对长时间连接提供QoS路由.
此外,在带宽受限的算法中,如果考虑了信息的陈旧性,由于突发到达的(burst)连接可以认为是一个要求更大带宽的连接请求,这样会增加链路状态的波动以及对不合理资源分配的敏感性,因此应避免剪枝造成的非最短可行路径.
4.
4基于概率求解由于信息的陈旧性可能导致建连失败,因此可以考虑求解以最大概率满足QoS约束的可行路径,这类问题往往基于概率求解.
在源路由的链路状态模型下,Guerin和Orda研究了不精确的状态信息下,带宽和延迟分别受限的QoSR问题[39].
源节点对网络中的每条链路l具有概率分布函数,表示链路l具有剩余w个单位带宽的概率.
其中,为链路的容量.
带宽受限路由的任务就是寻找一条路径,能够以最大概率满足新的QoS连接请求所要求的x个单位带宽.
这样,以为链路l的度量,使用最短路径树算法即可求解.
延迟受限情况与此类似,设节点对网络中的每条链路l具有概率分布函数,表示链路l延迟为d个单位的概率.
Lorenz为此设计了将全局约束转化为局部约束的启发式算法:将端到端延迟沿着路径分割成链路延迟约束,并且保持所有的链路具有相同的概率,满足分割后的链路延迟约束)(wpl)(dpl],.
.
.
,1,0[lcw∈lc)(logxpl[40].
Zhang和Liu设计了基于蚂蚁算法的通用QoSR算法,可以包含对带宽、延迟、丢失率抖动等参数的考虑[43].
蚂蚁根据不同路径上信息素的多少,以概率选择前进的路径,同时沿着路径行走时在路径上留下信息素.
据此,该算法将QoS业务类型分成M类,每类分别应用蚂蚁寻路的方法.
在建立QoS连接的过程中,业务类型d在r点以一定的概率),(srdρ选择下一跳s点,同时更改概率值),(srdρ,从而达到全局优化.
5总结与展望5.
1总结服务质量路由(QoSR)是未来互联网络的一个核心功能,其主要目标包括两个:(1)为每个接受的QoS业务流提供服务质量保证;(2)达到网络全局资源的最佳利用.
前者要求在多约束条件下计算可行路径;后者则要求在多条可行路径中进一步优化.
优化的方式通常是首先设计花费(cost)函数,然后求解函数值最优的可行路径.
然而,通常多约束下求解(优化的)可行路径属于NP完全问题,不能在多项式时间内精确求解,为此研究者们设计了很多启发式算法或近似算法.
这些算法还具有以下3方面的不足:(1)计算复杂度过高而不能在网络中实际应用;(2)算法性能过低而找不到实际存在的可行路径;(3)大部分算法只是针对QoSR问题中某些特殊情况的.
目前研究的几类热点算法仍然存在以下问题:多项式非启发类的算法只能解决单一可加性约束(优化)的问题;基于QoS度量相关的算法只能应用于基于速率调度的特定网络环境下,而且不支持对传输延迟的考虑;伪多项式的EBFA能够精确求解多重受限QoSR问题,但由于其指数级别的复杂度因而也是不可取的;基于探测的启发式算法路由时间长、通信开销大,还可能阻塞其他业务以及中间节点需要保存大量的状态;限定QoS度量的算法复杂度与QoS度量的粒度关系密切;路径子空间搜索的算法需要较好的启发函数,它以增大路由失败概率和降低路由性能为代价,减小了计算开销;基于特定花费函数的算法难以实现花费的可扩充性,同时,花费的计算代价较高;基于概率求解的算法不易确定和传播链路概率值,并且需要在花费和最大概率之间折衷.
此外,很多算法使用ε优化的方式,无形中增加了业务的QoS要求.
5.
2展望随着网络和应用业务的快速发展,QoSR日益成为网络研究的核心问题之一.
目前的研究成果表明,在一定区域内部通过合理地配置基于链路状态的QoSR协议,为支持QoS所引入的开销是完全可能接受的[4],然而QoSR领域在以下几个方面还有待进一步深入研究.
崔勇等:互联网络服务质量路由算法研究综述20735.
2.
1可扩展性通过网络状态聚集能够以对数缩减信息量,相应的分层路由可以通过限制每层内节点的数量使用源路由方式,从而很好地解决可扩展性问题.
但这同时又引入了新的问题:如何聚集状态信息、如何基于聚集状态设计良好的启发式算法.
目前所设计的状态信息聚集方法往往会丢失大量的可用信息,严重影响了QoSR算法的性能;同时,所设计的启发式算法也往往是基于全局状态源路由策略的.
此外,由于很多QoSR问题的精确求解复杂度都是NPC的,因此需要设计快速、有效的启发式算法.
5.
2.
2信息陈旧性状态信息的陈旧性是实际网络中不可避免的,并且会对QoSR算法的性能和有效性造成显著影响.
然而对这种陈旧性的分析涉及到复杂的随机数学模型,相关的讨论往往基于模拟试验数据,而缺少定量的理论分析.
此外,通常的算法只是停留在理论设计和分析上,缺乏对信息陈旧情况下算法实际性能的考虑.
因此,可以考虑基于概率模型求解,寻找以最大概率满足QoS约束的可行路径,从而有效地减少建连失败对网络造成的额外负担.
5.
2.
3多路路由与重路由在多条可能的路径上同时探测可行路径的方法中,如何与资源预留相结合尚无定论[21].
此外,网络提供多条从源到目的的路径,并将这些路径并行复用起来(如增加带宽)而对用户业务透明,这是一种多路复用的路由方式.
然而,其主要问题是多条路径之间如何同步,以及如何避免分组的延迟抖动、乱序等[44].
由于网络资源和可行路径分配的不合理,因而在某些情况下需要重新路由.
重路由可在网络资源不足时进行,能够有效地重新分配网络资源,但由于存在状态保存、同步和开销等问题,使重路由变得很困难.
5.
2.
4网络模型不同的网络拓扑结构和QoS业务流往往对QoSR算法的性能造成很大的影响,包括网络直径、节点互联粒度、网络资源分布、路径长度分布、连接持续时间分布、QoS需求分布等参数.
因此,QoSR需要在以下两个方面与网络模型结合起来:(1)评价QoSR算法和协议的性能、有效性;(2)针对实际网络设计高效的QoSR算法和协议,如对持续时间短的连接使用静态路由[8].
由于Internet缺乏"典型的"网络拓扑结构和业务流,因此,如何使用适当的网络模型来指导QoSR的研究,将是进一步的研究方向.
5.
2.
5与其他网络组件结合今后的网络应该是QoSR和尽力发送相结合的[45].
网络的路由目标是最大化资源效用,这包括尽可能地接纳更多的QoS连接请求,同时最大化尽力发送业务的吞吐量和相应速度.
由于这两者是矛盾的,因此二者融入的过程会产生很多问题.
例如,在有资源预留的链路空闲时,没有资源预留的链路却可能由于尽力发送业务而造成拥塞.
这种拥塞的链路仍然有可能因为尚未预留资源而接受QoS请求.
此外,QoSR算法必须与其他网络组件结合才能提供QoS保证,包括状态收集、资源预留、分组调度等,因此可以考虑这种结合过程对QoSR算法和其他网络组件的简化.
References:[1]Crawley,E.
,Nair,R.
,Rajagopalan,B.
etal.
AframeworkforQoS-basedroutingintheInternet.
RFC2386,1998.
[2]Lee,W.
C.
,Hluchyi,M.
G.
,Humblet,P.
A.
Routingsubjecttoqualityofserviceconstraintsintegratedcommunicationnetworks.
IEEENetwork,1995,9(4):46~55.
[3]Qualityofserviceglossaryofterms.
QoSForum.
1999.
http://www.
qosforum.
com.
[4]Apostolopoulos,G.
,Guerin,R.
,Kamat,S.
ImplementationandperformancemeasurementsofQoSroutingextensionstoOSPF.
In:Doshi,B.
,ed.
PrecedingsoftheIEEEINFOCOM'99.
NewYork,NY:IEEECommunicationSociety,1999.
680~688.
[5]Orda,A.
,Sprintson,A.
QoSrouting:theprecomputationperspective.
In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
Israel:IEEECommunicationSociety,2000.
128~136.
[6]Garey,M.
S.
,Johnson,D.
S.
Computersandintractability:aguidetothetheoryofNP-completeness.
Oxford:Freeman,W.
H.
,1979.
[7]Hao,F.
,Zegura,E.
W.
OnscalableQoSrouting:performanceevaluationoftopologyaggregation.
In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
IEEECommunicationSociety,2000.
147~156.
[8]Shaikh,A.
,Rexford,J.
,Shin,K.
G.
Evaluatingtheimpactofstalelinkstateonquality-of-servicerouting.
IEEE/ACMTransactionsonNetworking,2001,9(2):162~176.
2074JournalofSoftware软件学报2002,13(11)[9]Chen,S.
,Nahrstedt,K.
Anoverviewofquality-of-serviceroutingfornext-generationhigh-speednetworks:problemsandsolutions.
IEEENetwork,1998,12(6):64~79.
[10]Wang,B.
,Hou,J.
C.
MulticastroutinganditsQoSextension:problems,algorithms,andprotocols.
IEEENetwork,2000,14(1):22~36.
[11]Korkmaz,T.
,Krunz,M.
Multi-Constrainedoptimalpathselection.
In:Sengupta,B.
,ed.
ProceedingsoftheIEEEINFOCOM2001.
Piscataway,NJ:IEEECommunicationSociety,2001.
834~843.
[12]Wang,Z.
,Crowcroft,J.
QoSroutingforsupportingresourcereservation.
IEEEJournalonSelectedAreasinCommunications,1996,14(7):1228~1234.
[13]Guerin,R.
Orda,A.
Networkswithadvancereservations:theroutingperspective.
In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
IEEECommunicationSociety,2000.
118~127.
[14]Bellman,R.
E.
DynamicProgramming.
Princeton,NJ:PrincetonUniversityPress,1957.
[15]Dijkstra,E.
Anoteontwoproblemsinconnexionwithgraphs.
NumericalMathematics,1959,1:269~271.
[16]Bennett,J.
,Zhang,H.
Hierarchicalpacketfairqueueingalgorithms.
ACMSIGCOMMComputerCommunicationReview,1996,26(4):143~156.
[17]Ma,Q.
,Steenkiste,P.
Quality-of-Serviceroutingwithperformanceguarantees.
In:Campbell,A.
T.
,Nahrstedt,K.
,eds.
Proceedingsofthe4thInternationalIFIPWorkshoponQualityofService.
NewYork:IFIPWG6.
1,1997.
[18]Orda,A.
Routingwithend-to-endQoSguaranteesinbroadbandnetworks.
IEEE/ACMTransactionsonNetworking,1999,7(3):365~374.
[19]Pornavalai,C.
,Chakraborty,G.
,Shiratori,N.
QoSbasedroutingalgorithminintegratedservicespacketnetworks.
JournalofHighSpeedNetworks,1998,7(2):99~112.
[20]Clark,D.
,Pasquale,J.
,Estrin,D.
,etal.
Strategicdirectionsinnetworksandtelecommunications.
ACMComputingSurveys,1996,28(4):679~690.
[21]Cidon,I.
,Rom,R.
,Shavitt,Y.
Multi-Pathroutingcombinedwithresourcereservation.
In:Hasegawa,T.
,Pickholtz,R.
,eds.
ProceedingsoftheIEEEINFOCOM'97.
Kobe:IEEECommunicationSociety,1997.
92~100.
[22]Shin,K.
G.
,Chou,C.
C.
Adistributedroute-selectionschemeforestablishingreal-timechannel.
In:Puigjaner,R.
,ed.
ProceedingsofIFIPthe6thInternationalConferenceonHighPerformanceNetworking(HPN'95).
Palma:Chapman&Hall,1995.
319~329.
[23]Chen,S.
,Nahrstedt,K.
Distributedquality-of-serviceroutinginhigh-speednetworksbasedonselectiveprobing.
In:Nolley,E.
,ed.
Proceedingsofthe23rdAnnualConferenceonLocalComputerNetworks(LCN'98).
Boston,MA:IEEECommunicationSociety,1998.
80~89.
[24]Chen,S.
,Nahrstedt,K.
DistributedQoSroutingwithimprecisestateinformation.
In:Pressley,A.
,ed.
Proceedingsofthe7thInternationalConferenceonComputerCommunicationsandNetworks(IC3N'98).
IEEECommunicationSociety,1998.
614~621.
[25]Widyono,R.
Thedesignandevaluationofroutingalgorithmsforreal-timechannels.
TechnicalReport,TR-94-024,Berkeley:InternationalComputerScienceInstitute,1994.
[26]Yuan,X.
OntheextendedBellman-Fordalgorithmtosolvetwo-constrainedqualityofserviceroutingproblems.
In:Park,E.
K.
,ed.
Proceedingsofthe8thInternationalConferenceonComputerCommunicationsandNetworks(IC3N'99).
Boston,MA:IEEECommunicationSociety,1999.
304~310.
[27]Yuan,X.
,Liu,X.
Heuristicalgorithmsformulti-constrainedqualityofservicerouting,In:Sengupta,B.
,ed.
ProceedingsoftheIEEEINFOCOM2001.
Piscataway,NJ:IEEECommunicationSociety,2001.
844~853.
[28]Chen,S.
,Nahrstedt,K.
Onfindingmulti-constrainedpaths.
In:Goldston,R.
,ed.
ProceedingsoftheIEEEInternationalConferenceonCommunications(ICC'98).
Atlanta:IEEECommunicationSociety,1998.
874~879.
[29]Raz,D.
,Shavitt,Y.
,Raz,D.
etal.
OptimalpartitionofQoSrequirementswithdiscretecostfunctions,In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
IEEECommunicationSociety,2000.
613~622.
[30]Lorenz,H.
,Orda,A.
,Raz,D.
etal.
EfficientQoSpartitionandroutingofunicastandmulticast,In:Steenkiste,P.
,ed.
Proceedingsofthe8thInternationalWorkshoponQualityofService(IWQoS2000).
Pittsburgh:IEEECommunicationsSociety,2000.
75~83.
[31]Salama,H.
F.
,Reeves,D.
S.
,Viniotis,Y.
Adistributedalgorithmfordelay-constrainedunicastrouting.
IEEE/ACMTransactionsonNetworking,2000,8(2):239~250.
[32]Ergun,F.
,Sinha,R.
,Zhang,L.
QoSroutingwithperformance-dependentcosts,In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
IEEECommunicationSociety,2000.
137~146.
[33]Lorenz,H.
,Orda,A.
OptimalpartitionofQoSrequirementsonuncicastpathsandmulticasttrees.
In:Doshi,B.
,ed.
ProceedingsoftheIEEEINFOCOM'99.
NewYork:IEEECommunicationSociety,1999.
246~253.
[34]Fortz,B.
,Thorup,M.
InternettrafficengineeringbyoptimizingOSPFweights.
In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
IEEECommunicationSociety,2000.
519~528.
崔勇等:互联网络服务质量路由算法研究综述2075[35]Juttner,A.
,Szviatovski,Mecs,B.
I.
etal.
,LagrangerelaxationbasedmethodfortheQoSroutingproblem.
In:Sengupta,B.
,ed.
ProceedingsoftheIEEEINFOCOM2001.
IEEECommunicationSociety,2001.
859~868.
[36]Sobrinho,J.
L.
AlgebraandalgorithmsforQoSpathcomputationandhop-by-hoproutingintheInternet.
In:ProceedingsoftheIEEEINFOCOM2001.
IEEECommunicationSociety,2001.
727~735.
[37]Guerin,R.
A.
,Orda,A.
QoSroutinginnetworkswithinaccurateinformation:theoryandalgorithms.
IEEE/ACMTransactionsonNetworking,1999,7(3):350~364.
[38]Nelakuditi,S.
,Zhang,Z.
Tsang,R.
P.
Adaptiveproportionalrouting:alocalizedQoSroutingapproach.
In:Sidi,M.
,ed.
ProceedingsoftheIEEEINFOCOM2000.
IEEECommunicationSociety,2000.
1566~1575.
[39]Guerin,R.
,Orda,A.
QoS-Basedroutinginnetworkswithinaccurateinformation:theoryandalgorithms.
In:Hasegawa,T.
,Pickholtz,R.
,eds.
ProceedingsoftheIEEEINFOCOM'97.
Kobe:IEEECommunicationSociety,1997.
75~83.
[40]Lorenz,D.
H.
,Orda,A.
QoSroutinginnetworkswithuncertainparameters.
IEEE/ACMTransactionsonNetworking,1998,6(6):768~778.
[41]Floyd,S.
,Paxson,V.
DifficultiesinsimulatingtheInternet.
IEEE/ACMTransactionsonNetworking,2001,9(4):392~403.
[42]Zegura,E.
W.
,Calvert,K.
L.
,Donahoo,M.
J.
Aquantitativecomparisonofgraph-basedmodelsforInternettopology.
IEEE/ACMTransactionsonNetworking.
1997,5(6):770~783.
[43]Zhang,S.
,Liu,Z.
AQoSroutingalgorithmbasedonantalgorithm.
In:Neuvo,Y.
,ed.
ProceedingsoftheIEEEInternationalConferenceonCommunications(ICC2001).
IEEECommunicationSociety,2001.
1581~1585.
[44]Vutukury,S.
,Garcia-Luna-Aceves,J.
J.
Asimpleapproximationtominimum-delayrouting.
ComputerCommunicationReview,1999,29(4):227~238.
[45]Ma,Q.
,Steenkiste,P.
Supportingdynamicinter-classresourcesharing:amulti-classQoSroutingalgorithm.
In:Doshi,B.
,ed.
ProceedingsoftheIEEEINFOCOM'99.
NewYork:IEEECommunicationSociety,1999.
649~660.
ResearchonInternetworkQoSRoutingAlgorithms:aSurveyCUIYong,WUJian-ping,XUKe,XUMing-wei(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China)E-mail:cy@csnet1.
cs.
tsinghua.
edu.
cnhttp://netlab.
cs.
tsinghua.
edu.
cn/~cuiyAbstract:ItisachallengingproblemtoprovideQoS(quality-of-service)guaranteeforthenext-generationnetworks,amongwhichQoSR(QoSrouting)isoneofthekeyissues.
QoSRseekstofindafeasiblepathforQoStrafficwithtwoobjectives:(1)providingtheQoSguaranteeforQoStraffic,(2)maximizingtheutilizationofthewholenetwork.
However,somemulti-constrainedQoSRproblems,whichareNP-complete,can'tberesolvedaccuratelyinpolynomialtime.
Thusheuristicsarestudiedextensivelyinrecentyears.
BasedontheweightedgraphnetworkmodelandQoSmetrics,thebasicconceptofQoSRisintroducedandthehotissuesoftheunicastQoSRheuristicsareanalyzedinthispaper.
QoSRalgorithmscanbeclassifiedintotheseveralclasses:polynomialnon-heuristics,pseudo-polynomialnon-heuristics,QoSmetricsrestriction,pathsubspacesearch,QoSmetricsrelation,costfunctionsstudyandpossibilitysolution.
Aftertypicalalgorithmsareanalyzed,thesummaryandconparisonaregivenforeachoftheaboveclasses.
Thevalidityofalgorithmsisdissectedindetail,includingtheroutingloopproblem,stalenetworkstateinformation,theimpactofthenetworktopologiesandtrafficmodels.
Basedonthevalidityanalysis,asummaryisgivenfortheQoSRalgorithmsbasedonprobabilitymodels.
Atlast,keyissuesarepointedouttobefurtherstudiedintheQoSRfield.
Keywords:QoSR(quality-of-servicerouting);NP-completeproblem;heuristics;validityReceivedDecember31,2001;acceptedApril10,2002SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.
90104002,69725003;theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNos.
2002AA103067,2001AA121013