鏈路分離路徑算法研究*

劉 靜 趙 晶

(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