鏈路分離路徑算法研究*

劉 靜 趙 晶

(91469部隊(duì) 北京 100841)

鏈路分離路徑算法研究*

劉 靜 趙 晶

(91469部隊(duì) 北京 100841)

傳統(tǒng)的QoS路由算法只在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間提供一條QoS路徑,這一做法已不能滿足在網(wǎng)絡(luò)連接出現(xiàn)故障時(shí)保持業(yè)務(wù)持續(xù)不間斷地進(jìn)行這一要求。分離路徑算法試圖在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間尋找滿足一定QoS約束的分離路徑(鏈路分離或節(jié)點(diǎn)分離),一條主用路徑,另一條備用路徑。當(dāng)主用路徑出現(xiàn)故障時(shí),將其承載的業(yè)務(wù)流轉(zhuǎn)換到備用路徑上,從而實(shí)現(xiàn)快速的業(yè)務(wù)恢復(fù)。因此,分離路徑算法研究有很重要的實(shí)用價(jià)值。

服務(wù)質(zhì)量; 鏈路分離; 節(jié)點(diǎn)分離

ClassNumberTP301.6

1 引言

大規(guī)模多媒體網(wǎng)絡(luò)的發(fā)展,以及多媒體流和視訊會議等新業(yè)務(wù)的出現(xiàn),對網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)提出了更高的要求。不僅要滿足業(yè)務(wù)的QoS要求,還要在網(wǎng)絡(luò)連接出現(xiàn)故障時(shí)能保持業(yè)務(wù)持續(xù)不間斷地進(jìn)行。如果在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間只有一條QoS路徑已不能滿足用戶在鏈路故障時(shí)對業(yè)務(wù)快速恢復(fù)的要求。要達(dá)到這些要求,目前的做法是在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間為一個(gè)連接提供一對鏈路分離(或節(jié)點(diǎn)分離)路徑,其中一條為主用路徑,另一條備用。當(dāng)主用路徑出現(xiàn)故障時(shí),將其承載的業(yè)務(wù)流轉(zhuǎn)換到備用路徑上,從而實(shí)現(xiàn)快速的業(yè)務(wù)恢復(fù)。

RFC2386[1]中是這樣描述的:QoS是網(wǎng)絡(luò)在傳輸數(shù)據(jù)流時(shí)要求滿足的一系列服務(wù)請求,可以量化為帶寬、時(shí)延、時(shí)延抖動、丟失率、吞吐量等性能指標(biāo)。ITU-T在建議書E.800中給出QoS定義[2]:QoS是服務(wù)性能的總效果,這個(gè)效果決定了一個(gè)用戶對服務(wù)的滿意程度。因此在最簡單的意義上,有QoS的服務(wù)就能夠滿足用戶的應(yīng)用需求的服務(wù)。從技術(shù)角度來看,QoS是指網(wǎng)絡(luò)系統(tǒng)各種性能尺度的綜合,主要包括可提供的帶寬、丟包率、差錯(cuò)率、時(shí)延和抖動、接通率等方面。具體應(yīng)用不同,對QoS各項(xiàng)指標(biāo)的要求也不同。比如:長文件傳輸要求傳輸速率高且分組丟失低,但對時(shí)延和抖動不是太敏感;而視頻會議不僅要求傳輸速率高,而且對時(shí)延和抖動也很敏感。

2 網(wǎng)絡(luò)模型

通常將QoS路徑選擇問題描述為一個(gè)有向圖G(V,E)[3]。其中V={vij}是節(jié)點(diǎn)集,可以表示交換機(jī)、路由器和主機(jī),也可以是子網(wǎng);E={eij}是邊集,代表網(wǎng)絡(luò)鏈路。設(shè)|V|=n,|E|=m。邊eij標(biāo)識為eij=(vi,vj),表示從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj之間的一條直通鏈路,其中i,j=1,2,…,n,j≠i,vi,vj∈V。

文獻(xiàn)[4～5]給出了比較完整的網(wǎng)絡(luò)模型,即定義了節(jié)點(diǎn)上和鏈路上的各項(xiàng)QoS參數(shù)。文獻(xiàn)[4]又對該網(wǎng)絡(luò)模型做了簡化,把定義在節(jié)點(diǎn)上的參數(shù)分別附加到該節(jié)點(diǎn)引出的所有鏈路上,即以該節(jié)點(diǎn)為頭的所有鏈路上。這樣就得到抽象的網(wǎng)絡(luò)模型中,節(jié)點(diǎn)vi(i=1,2,…,n)上不再有QoS參數(shù),所有的QoS需求通過可測量的QoS度量參數(shù)來實(shí)現(xiàn)。

3 分離路徑

在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間為一個(gè)連接提供一對鏈路分離(或節(jié)點(diǎn)分離)路徑,這一做法,比起單一路徑有很多優(yōu)勢[6]: 1)保證了數(shù)據(jù)包在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的可靠傳輸。 2)在主路徑上某鏈路或節(jié)點(diǎn)發(fā)生故障時(shí),能迅速將其承載的業(yè)務(wù)流轉(zhuǎn)換到備用路徑上,從而實(shí)現(xiàn)快速的業(yè)務(wù)恢復(fù)。 3)能減少網(wǎng)絡(luò)擁塞。 4)減小分組丟失率,保持網(wǎng)絡(luò)中負(fù)載平衡。

分離路徑(Disjoint Paths)分為鏈路分離路徑(Link Disjoint Paths)和節(jié)點(diǎn)分離路徑(Node Disjoint Paths)兩種。

定義1 鏈路分離路徑(Link Disjoint Paths)

路徑p和q是網(wǎng)絡(luò)圖G(V,E)中(有向或無向)的從源節(jié)點(diǎn)v1到目的節(jié)點(diǎn)vk的兩條路徑。對于?eij=(vi,vj)∈E,eij∈p和eij∈q不同時(shí)成立,則稱路徑p和q是從源節(jié)點(diǎn)v1到目的節(jié)點(diǎn)vk的一對鏈路分離路徑,簡稱p和q是鏈路分離路徑。記作:E(p∩q)=Φ。

定義2 節(jié)點(diǎn)分離路徑(Node Disjoint Paths)

路徑p和q是有向圖G(V,E)中(有向或無向)的從源節(jié)點(diǎn)v1到目的節(jié)點(diǎn)vk的兩條路徑。對于?vi∈V(i≠1且i≠k),vi∈p和vi∈q不同時(shí)成立,則稱路徑p和q是從源節(jié)點(diǎn)v1到目的節(jié)點(diǎn)vk的一對節(jié)點(diǎn)分離路徑,簡稱p和q是節(jié)點(diǎn)分離路徑。記作:V(p∩q)=Φ。

通過上面的定義可以看出,節(jié)點(diǎn)分離路徑一定是鏈路分離路徑,但鏈路分離路徑并不一定是節(jié)點(diǎn)分離路徑。

4 分離路徑的簡化

4.1 無向圖分離路徑問題的轉(zhuǎn)化

對于無向圖中的分離路徑問題,一般都可以轉(zhuǎn)化為其鏈路分裂圖[16]的對應(yīng)問題,然后運(yùn)用有向圖中的分離路徑算法來求解。

定義3 鏈路分裂圖(Link Split Graph)

網(wǎng)絡(luò)由無向圖G(V,E)表示,對于圖中任意無向鏈路{u,v}∈E,將{u,v}分裂為兩條有向鏈路(u,v)和(v,u),并且鏈路(u,v)和(v,u)上的所有參數(shù)都等于{u,v}上相應(yīng)參數(shù),得到有向圖G′(V,E′),則稱有向圖G′(V,E′)為無向圖G(V,E)的鏈路分裂圖。注意,這里{u,v}表示無向圖中節(jié)點(diǎn)u,v之間的鏈路,(u,v)表示有向圖中節(jié)點(diǎn)u到節(jié)點(diǎn)v的鏈路。

例如,圖1(a)所示的無向圖對應(yīng)的鏈路分裂圖如圖1(b)所示。

圖1 無向圖和其對應(yīng)的鏈路分裂圖

為了保證所研究的有向網(wǎng)絡(luò)中不同時(shí)存在鏈路(u,v)和(v,u)這一假設(shè),通常做法是對節(jié)點(diǎn)u和v進(jìn)行節(jié)點(diǎn)分裂[2],這樣可以避免在網(wǎng)絡(luò)圖中同時(shí)存在鏈路(u,v)和(v,u)。

定義4 節(jié)點(diǎn)分裂(Node Split)

對節(jié)點(diǎn)v∈V作如下變換:

1)將節(jié)點(diǎn)v∈V(v≠s,t,其中s,t分別為源節(jié)點(diǎn)和目的節(jié)點(diǎn))分裂為兩個(gè)節(jié)點(diǎn)v′和v″,并增加鏈路(v′,v″),并且將鏈路(v′,v″)的權(quán)重置為0;

2)將鏈路(u,v)∈E(其中u≠v)替換為(u,v′),(v,u)∈E替換為(v″,u),鏈路權(quán)重保持不變。

對節(jié)點(diǎn)v這一變換過程稱為節(jié)點(diǎn)分裂。

如圖2示,圖2(a)為原始圖,圖2(b)為將u和v進(jìn)行節(jié)點(diǎn)分裂后的修正圖。

圖2 避免網(wǎng)絡(luò)中同時(shí)存在鏈路(u,v)和(v,u)

4.2 節(jié)點(diǎn)分離路徑問題的轉(zhuǎn)化

對于節(jié)點(diǎn)分離路徑問題,可以通過節(jié)點(diǎn)分裂的方法,然后在其節(jié)點(diǎn)分裂圖中運(yùn)用鏈路分離路徑算法求解(詳見文獻(xiàn)[8～9])。節(jié)點(diǎn)分裂圖是這樣得到的:在有向網(wǎng)絡(luò)G(V,E)中,對v∈V且v≠s,t的所有節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)分裂,所得新的有向圖G′(V′,E′)就是網(wǎng)絡(luò)G(V,E)的節(jié)點(diǎn)分裂圖。

如圖3(a)所示有向圖G(V,E)中,源節(jié)點(diǎn)s=a和目的節(jié)點(diǎn)t=f,通過節(jié)點(diǎn)分裂得到原有向圖G(V,E)的節(jié)點(diǎn)分裂圖G′(V′,E′),如圖3(b)所示。

圖3 節(jié)點(diǎn)分裂圖

5 分離路徑算法研究現(xiàn)狀

RF(Remove-Find)方法是在一對源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立兩條鏈路分離路徑的一種簡單方法。這種方法雖然簡單直接,但是它有以下兩個(gè)缺點(diǎn): 1)有時(shí)候在網(wǎng)絡(luò)G(V,E)存在從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的兩條鏈路分離路徑,但是RF方法會導(dǎo)致剩余圖G′(V,E′)不連通,從而得不到第二條路徑。 2)第二條路徑的長度可能很大,即RF方法所得的兩條鏈路分離路徑是問題的可行解而不是最優(yōu)解。

為了克服RF方法的缺點(diǎn),Suurballe于1974年提出了一種算法[10],通過路徑增益(path augmentation)方法,以總長度最小為目標(biāo)在尋找k條節(jié)點(diǎn)分離路徑。1984年,Suurballe和Tarjan改進(jìn)了Suurballe算法[7]。隨后的Bhandari[11]通過修改原始的Dijkstra算法,提出了一個(gè)針對有向圖的鏈路分離問題的算法。文獻(xiàn)[7,10～11]中研究的是鏈路上只包含一個(gè)QoS參數(shù)的分離路徑問題,該問題被稱為最優(yōu)鏈路分離路徑問題。Sidhu等[12]利用節(jié)點(diǎn)的分布式距離矢量信息給出了在網(wǎng)絡(luò)中尋找分離路徑的可行算法。Alexander[13]分析了在有向平面圖(planar graph)中在給定節(jié)點(diǎn)之間尋找k對節(jié)點(diǎn)分離路徑問題,并提出了多項(xiàng)式時(shí)間算法。LEE S-W[14]等給出了在圖G中在給定節(jié)點(diǎn)之間尋找前k條最短路徑的可行算法。Taft-Plotkin等[15]分析了在多個(gè)QoS參數(shù)下如何在面向連接的網(wǎng)絡(luò)中尋找最大程度鏈路分離路徑問題,并提出了MADSWIP算法。張品等[16]研究了QoS約束下的鏈路分離路徑問題,建立了兩種QoS約束下的鏈路分離優(yōu)化路徑問題的模型。郭宇春等[8～9]建立了多約束鏈路分離路徑問題模型,并給出了啟發(fā)式算法—DIMCRA算法。

6 結(jié)語

本文首先給出了鏈路分離路徑問題的網(wǎng)絡(luò)模型和一般描述，然后提出了無向圖中的分離路徑問題以及節(jié)點(diǎn)分離路徑問題的簡化方法，并在文章最后介紹了已有的一些鏈路分離路徑算法及特點(diǎn)。

[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]謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)[M].第四版.北京:電子工業(yè)出版社,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路由算法的數(shù)學(xué)模型研究[J].計(jì)算機(jī)工程與應(yīng)用2003,39(8):157-159.

[5]馮徑,馬小駿,顧冠群.適應(yīng)QoS路由機(jī)制的網(wǎng)絡(luò)模型研究[J].計(jì)算機(jī)學(xué)報(bào),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].鐵道學(xué)報(bào),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].通信學(xué)報(bào),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