链路分离路径算法研究*

刘 静 赵 晶

(91469部队 北京 100841)

链路分离路径算法研究*

刘 静 赵 晶

(91469部队 北京 100841)

传统的QoS路由算法只在源节点和目的节点之间提供一条QoS路径,这一做法已不能满足在网络连接出现故障时保持业务持续不间断地进行这一要求。分离路径算法试图在源节点和目的节点之间寻找满足一定QoS约束的分离路径(链路分离或节点分离),一条主用路径,另一条备用路径。当主用路径出现故障时,将其承载的业务流转换到备用路径上,从而实现快速的业务恢复。因此,分离路径算法研究有很重要的实用价值。

服务质量; 链路分离; 节点分离

ClassNumberTP301.6

1 引言

大规模多媒体网络的发展,以及多媒体流和视讯会议等新业务的出现,对网络服务质量(QoS)提出了更高的要求。不仅要满足业务的QoS要求,还要在网络连接出现故障时能保持业务持续不间断地进行。如果在源节点和目的节点之间只有一条QoS路径已不能满足用户在链路故障时对业务快速恢复的要求。要达到这些要求,目前的做法是在源节点和目的节点之间为一个连接提供一对链路分离(或节点分离)路径,其中一条为主用路径,另一条备用。当主用路径出现故障时,将其承载的业务流转换到备用路径上,从而实现快速的业务恢复。

RFC2386[1]中是这样描述的:QoS是网络在传输数据流时要求满足的一系列服务请求,可以量化为带宽、时延、时延抖动、丢失率、吞吐量等性能指标。ITU-T在建议书E.800中给出QoS定义[2]:QoS是服务性能的总效果,这个效果决定了一个用户对服务的满意程度。因此在最简单的意义上,有QoS的服务就能够满足用户的应用需求的服务。从技术角度来看,QoS是指网络系统各种性能尺度的综合,主要包括可提供的带宽、丢包率、差错率、时延和抖动、接通率等方面。具体应用不同,对QoS各项指标的要求也不同。比如:长文件传输要求传输速率高且分组丢失低,但对时延和抖动不是太敏感;而视频会议不仅要求传输速率高,而且对时延和抖动也很敏感。

2 网络模型

通常将QoS路径选择问题描述为一个有向图G(V,E)[3]。其中V={vij}是节点集,可以表示交换机、路由器和主机,也可以是子网;E={eij}是边集,代表网络链路。设|V|=n,|E|=m。边eij标识为eij=(vi,vj),表示从节点vi到节点vj之间的一条直通链路,其中i,j=1,2,…,n,j≠i,vi,vj∈V。

文献[4～5]给出了比较完整的网络模型,即定义了节点上和链路上的各项QoS参数。文献[4]又对该网络模型做了简化,把定义在节点上的参数分别附加到该节点引出的所有链路上,即以该节点为头的所有链路上。这样就得到抽象的网络模型中,节点vi(i=1,2,…,n)上不再有QoS参数,所有的QoS需求通过可测量的QoS度量参数来实现。

3 分离路径

在源节点和目的节点之间为一个连接提供一对链路分离(或节点分离)路径,这一做法,比起单一路径有很多优势[6]: 1)保证了数据包在源节点和目的节点之间的可靠传输。 2)在主路径上某链路或节点发生故障时,能迅速将其承载的业务流转换到备用路径上,从而实现快速的业务恢复。 3)能减少网络拥塞。 4)减小分组丢失率,保持网络中负载平衡。

分离路径(Disjoint Paths)分为链路分离路径(Link Disjoint Paths)和节点分离路径(Node Disjoint Paths)两种。

定义1 链路分离路径(Link Disjoint Paths)

路径p和q是网络图G(V,E)中(有向或无向)的从源节点v1到目的节点vk的两条路径。对于∀eij=(vi,vj)∈E,eij∈p和eij∈q不同时成立,则称路径p和q是从源节点v1到目的节点vk的一对链路分离路径,简称p和q是链路分离路径。记作:E(p∩q)=Φ。

定义2 节点分离路径(Node Disjoint Paths)

路径p和q是有向图G(V,E)中(有向或无向)的从源节点v1到目的节点vk的两条路径。对于∀vi∈V(i≠1且i≠k),vi∈p和vi∈q不同时成立,则称路径p和q是从源节点v1到目的节点vk的一对节点分离路径,简称p和q是节点分离路径。记作:V(p∩q)=Φ。

通过上面的定义可以看出,节点分离路径一定是链路分离路径,但链路分离路径并不一定是节点分离路径。

4 分离路径的简化

4.1 无向图分离路径问题的转化

对于无向图中的分离路径问题,一般都可以转化为其链路分裂图[16]的对应问题,然后运用有向图中的分离路径算法来求解。

定义3 链路分裂图(Link Split Graph)

网络由无向图G(V,E)表示,对于图中任意无向链路{u,v}∈E,将{u,v}分裂为两条有向链路(u,v)和(v,u),并且链路(u,v)和(v,u)上的所有参数都等于{u,v}上相应参数,得到有向图G′(V,E′),则称有向图G′(V,E′)为无向图G(V,E)的链路分裂图。注意,这里{u,v}表示无向图中节点u,v之间的链路,(u,v)表示有向图中节点u到节点v的链路。

例如,图1(a)所示的无向图对应的链路分裂图如图1(b)所示。

图1 无向图和其对应的链路分裂图

为了保证所研究的有向网络中不同时存在链路(u,v)和(v,u)这一假设,通常做法是对节点u和v进行节点分裂[2],这样可以避免在网络图中同时存在链路(u,v)和(v,u)。

定义4 节点分裂(Node Split)

对节点v∈V作如下变换:

1)将节点v∈V(v≠s,t,其中s,t分别为源节点和目的节点)分裂为两个节点v′和v″,并增加链路(v′,v″),并且将链路(v′,v″)的权重置为0;

2)将链路(u,v)∈E(其中u≠v)替换为(u,v′),(v,u)∈E替换为(v″,u),链路权重保持不变。

对节点v这一变换过程称为节点分裂。

如图2示,图2(a)为原始图,图2(b)为将u和v进行节点分裂后的修正图。

图2 避免网络中同时存在链路(u,v)和(v,u)

4.2 节点分离路径问题的转化

对于节点分离路径问题,可以通过节点分裂的方法,然后在其节点分裂图中运用链路分离路径算法求解(详见文献[8～9])。节点分裂图是这样得到的:在有向网络G(V,E)中,对v∈V且v≠s,t的所有节点进行节点分裂,所得新的有向图G′(V′,E′)就是网络G(V,E)的节点分裂图。

如图3(a)所示有向图G(V,E)中,源节点s=a和目的节点t=f,通过节点分裂得到原有向图G(V,E)的节点分裂图G′(V′,E′),如图3(b)所示。

图3 节点分裂图

5 分离路径算法研究现状

RF(Remove-Find)方法是在一对源节点和目的节点之间建立两条链路分离路径的一种简单方法。这种方法虽然简单直接,但是它有以下两个缺点: 1)有时候在网络G(V,E)存在从源节点到目的节点之间的两条链路分离路径,但是RF方法会导致剩余图G′(V,E′)不连通,从而得不到第二条路径。 2)第二条路径的长度可能很大,即RF方法所得的两条链路分离路径是问题的可行解而不是最优解。

为了克服RF方法的缺点,Suurballe于1974年提出了一种算法[10],通过路径增益(path augmentation)方法,以总长度最小为目标在寻找k条节点分离路径。1984年,Suurballe和Tarjan改进了Suurballe算法[7]。随后的Bhandari[11]通过修改原始的Dijkstra算法,提出了一个针对有向图的链路分离问题的算法。文献[7,10～11]中研究的是链路上只包含一个QoS参数的分离路径问题,该问题被称为最优链路分离路径问题。Sidhu等[12]利用节点的分布式距离矢量信息给出了在网络中寻找分离路径的可行算法。Alexander[13]分析了在有向平面图(planar graph)中在给定节点之间寻找k对节点分离路径问题,并提出了多项式时间算法。LEE S-W[14]等给出了在图G中在给定节点之间寻找前k条最短路径的可行算法。Taft-Plotkin等[15]分析了在多个QoS参数下如何在面向连接的网络中寻找最大程度链路分离路径问题,并提出了MADSWIP算法。张品等[16]研究了QoS约束下的链路分离路径问题,建立了两种QoS约束下的链路分离优化路径问题的模型。郭宇春等[8～9]建立了多约束链路分离路径问题模型,并给出了启发式算法—DIMCRA算法。

6 结语

本文首先给出了链路分离路径问题的网络模型和一般描述，然后提出了无向图中的分离路径问题以及节点分离路径问题的简化方法，并在文章最后介绍了已有的一些链路分离路径算法及特点。

[1]Craely E, Nair R, Rajagopalan B, et al. A Framework for QoS-based Routing in the Internet[J]. IETF RFC2386,1998(8):233-237:22-23.

[2]谢希仁.计算机网络[M].第四版.北京:电子工业出版社,2003:89-90.

[3]Chen Shigang, Klara Nahrstedt. An overview of Quality of service routing for next generation high-speed networks: Problems and Solutions[J]. IEEE Network,1998,12(6):64-79.

[4]汪泽焱,顾红芳.一种求解QoS路由算法的数学模型研究[J].计算机工程与应用2003,39(8):157-159.

[5]冯径,马小骏,顾冠群.适应QoS路由机制的网络模型研究[J].计算机学报,2000,23(8):799-805.

[6]Supreeth K S. Multi-constrained node-disjoint multi-path QoS routing algorithms for status dissemination networks[D]. Washington: Washington State University,2004:16-21.

[7]Suubralle J W, TARJAN R E. A quick method for finding shortest pairs of disjoint paths[J]. Networks,1984,14(2):325-336.

[8]Yuchun Guo, Kuipers F, Mieghem P V. A link-disjoint paths algorithm for reliable QoS routing[J]. International Journal of Communication Systems,2003,16(9):779-798.

[9]郭宇春,Fernando Kuipers, Piet Van Mieghem,等.多约束分离路径算法[J].铁道学报,2005,27(2):49-57.

[10]Suubralle J W. Disjoint paths in a network[J]. Networks,1974,4(2):125-145.

[11]Bhandari R. Optimal diverse routing in telecommunication fiber networks[C]//Proc IEEE NFOCOM 94. Toronto,1994:1498-1508.

[12]D Sidhu, R Nair, S Abdallah. Finding disjoint paths in networks[J]. ACM SIGCOMM Computer Communication Review,1991,21(4):43-51.

[13]Alexander S. Finding k disjoint paths in a directed planar graph[J]. SIAM Journal on Computing,1994,23(4):780-788.

[14]LEE S W, WU C S. A k-best paths algorithm for highly reliable communication network[J]. IEICE Trans on Communication,1999,E82-B(4):586-590.

[15]Taft-Plotkin N, Bellur B, Ogier R. Quality-of-service routing using maximally disjoint paths[C]//Proceedings of IWQoS, London,1999:119-128.

[16]张品,李乐民,王晟.QoS约束下的链路分离问题研究[J].通信学报,2006,27(6):36-42.

StudyoftheAlgorithmsforLinkDisjointPaths

LIU Jing ZHAO Jing

(No. 91469 Troops of PLA, Beijing 100841)

It has only one QoS path between source node and destination node in the tradional QoS routing algorithms, but now those techniques can not satisfy the requirement that many services must go sostenuto when some connections are in failure. The algorithms for disjoint paths try to find two link or node disjoint paths with some QoS constraints between source node and the destination node, then, one of the paths is used as primary path, another as backup path. A service flow will be redirected to the backup path if the primary path fails. Therefore, the research on algotithms for disjoint paths is very valuable and usable.

quality of service, link disjoint, node disjoint

2013年10月3日,

:2013年11月17日

刘静,女,硕士,工程师,研究方向:通信工程。赵晶,女,工程师,研究方向:通信工程。

TP301.6DOI:10.3969/j.issn1672-9730.2014.04.017