基于擴展Dijkstra的多約束QoS路由研究

袁玉瑩，付 雄

(南京郵電大學 計算機學院，江蘇 南京 210003)

0 引 言

隨著Internet網絡的廣泛應用，一方面由于實時業(yè)務對網絡傳輸的時延、丟包率、抖動等特性較為敏感，如果網絡中發(fā)生突發(fā)性的問題，實時業(yè)務將會受到很大的影響。另一方面，以太網業(yè)務占用了很多的帶寬，這對當前的網絡傳輸也提出了挑戰(zhàn)。服務質量(QoS)的應用范圍涉及到通信網絡技術、交通規(guī)劃、系統(tǒng)工程等很多領域，如何在網絡上提供各種業(yè)務的QoS保證變得越來越重要。

服務質量(quality of service，QoS)是指由源節(jié)點向目的節(jié)點傳輸相應的業(yè)務流時，需要滿足傳輸層的某些性能度量約束[1-2]。常見的QoS度量參數包括時延、帶寬、代價、丟包率、抖動等，業(yè)務在網絡傳輸過程中必須滿足QoS約束。QoS約束可以反映在路徑約束、鏈路約束等方面，其中路徑約束是指從源節(jié)點到目的節(jié)點的某條可行路徑上，端到端的QoS約束，例如可乘性度量參數時延約束。鏈路約束指從源節(jié)點到目的節(jié)點的某條可行路徑上每一條鏈路的約束，例如凹性度量參數帶寬約束。QoS度量參數按照性質可以分為可加性度量參數、可乘性度量參數和凹性度量參數[3]。鏈路的時延、花費和抖動屬于可加性度量參數，特點是QoS度量約束總值等于可行路徑上所有鏈路QoS度量之和。鏈路的利用率和丟包率屬于可乘性度量參數，特點是QoS度量約束總值等于可行路徑上所有鏈路的QoS度量之積。帶寬屬于凹性度量參數，特點是QoS度量約束總值等于可行路徑上所有鏈路的最小QoS度量值。

多約束QoS路由是根據網絡中的狀態(tài)信息以及不同業(yè)務對QoS度量參數的要求，為其選擇滿足多種約束(例如時延、帶寬、代價、丟包率和抖動[4-6])的可行路徑的一種路由機制。QoS約束可以是一維的參數，也可以是多維的參數，如果業(yè)務需要滿足多個QoS度量約束時，稱為多約束QoS路由。

目前大多數多約束QoS路由研究僅在網絡中尋找單一的可行路徑或者是單一的最優(yōu)路徑，如果路徑上發(fā)生局部堵塞或者故障時，分組數據則會丟失，因此以太網業(yè)務中的雙路徑路由主要是在源節(jié)點和目的節(jié)點之間尋找兩條滿足多約束QoS條件的最優(yōu)可行路徑，當工作路徑堵塞嚴重或者發(fā)生故障時，可以進行主備切換，用另一條保護路徑正常進行數據的傳輸，在一定程度上能夠消除路徑上的路由振蕩問題，同時減輕了網絡的負載[7]。

多約束QoS路由計算需要解決的問題是在源節(jié)點與目的節(jié)點之間找到能夠滿足多個獨立QoS度量參數約束的最優(yōu)路徑。目前國際上主要的研究方法大致分為三種：精確算法(如Dijkstra算法，Bellman-Ford算法)、近似算法(如拉格朗日松弛算法)以及啟發(fā)式算法(如蟻群算法、遺傳算法)[8]。

對于計算多約束QoS路由的可行路徑，當可加性約束條件或者可乘性約束條件數量在兩個或兩個以上的時候，該問題則是一個NP完全問題[9]，而研究表明傳統(tǒng)的路由算法很難有效地解決NP完全[10-11]問題。在目前所有求解從源節(jié)點至目的節(jié)點的最短路徑的算法中，最為高效的是Dijkstra算法，它可以根據給定的任意條件，快速求解出源節(jié)點與目的節(jié)點之間的最短路徑。該算法的思路是通過預處理去除不滿足帶寬約束的所有鏈路邊，這樣就不需要再考慮帶寬的約束。除了帶寬約束外，還有其他QoS度量參數約束時，如果約束參數較少，可以使用K-Shortest Path[12]算法，將除帶寬以外其他度量參數的約束條件通過某種專門設計好的函數轉化為一個單獨的度量參數約束[13]。這種方法的優(yōu)點是能夠去除所有不能同時滿足多個QoS約束條件的路徑，但是當QoS度量參數約束較多時，該方法幾乎不能找到一個合適的函數將多個QoS度量參數轉化為一個度量參數。

因此針對所研究的多約束QoS雙路徑路由問題，文中設計了一種基于擴展Dijkstra的多約束QoS雙路徑路由算法(multi-constrained QoS dual-path routing algorithm based extended Dijkstra，ED_MCQDP)，旨在網絡中尋找到能夠滿足多個QoS度量參數約束并且求解精度較高的雙路徑路由。

1 蟻群算法基本原理

蟻群算法，又稱螞蟻算法，由意大利學者Dorigo等人提出，是一種尋找圖中最優(yōu)路徑的概率型算法[14]，最初應用于解決旅行商問題，目前擴展到用于解決交通路由、資源分配、通信網絡中的路由問題以及負載均衡等[15]。

算法1：蟻群算法。

輸入：節(jié)點集合M，螞蟻數量n，迭代次數c

輸出：最優(yōu)路徑path

1.τij(0)=0// 設置初始信息素

2. for(i=0;i

3. for(j=1;j<=n;j++)

4. if(q>q0)

7.τij(t+1)=(1-ρ)τij(t)+ρΔτij// 經過的路徑信息素全局更新

8.τij(t+1)=(1-ρ)τij(t)// 其他鏈路信息素更新

9. end if

10. end for

11. end for

12. return path

蟻群算法的選擇概率公式如下：

(1)

(2)

螞蟻每走一步或者完成一次遍歷之后，需要更新殘留的信息素，對舊的信息素進行一定程度的揮發(fā)，避免累積過多的殘留信息素，導致啟發(fā)信息被淹沒。螞蟻k從節(jié)點i移動到節(jié)點j之后，利用公式(3)迭代更新節(jié)點i和節(jié)點j上的信息素濃度，其中ρ為信息素揮發(fā)因子(ρ的取值范圍是[0,1])，則1-ρ是信息素殘留因子。

(3)

(4)

其中，Q是常數，對算法的收斂速度有一定的影響。公式(4)表示信息素增量可以根據QoS度量參數進行動態(tài)調整，從而找到時延小、代價小、丟包率小以及抖動小的路徑。

蟻群算法使用概率公式進行路徑尋找，發(fā)現較優(yōu)解的能力很強，但是該算法在網絡規(guī)模較大時，搜索時間很長，而且容易陷入局部最優(yōu)解，并非全局最優(yōu)解。

2 Dijkstra算法基本原理

Dijkstra算法的基本思想是根據路徑權值的大小進行迭代，從而計算出從源節(jié)點至目的節(jié)點的最優(yōu)路徑[16]。

算法2：Dijkstra算法。

輸入：節(jié)點個數n，源節(jié)點s，目的節(jié)點v

輸出：最短路徑

1.S={2,3,…,n},dist[1]=0,dist[i]=weight(1,i)

2.while (S.length>0)

3.S=S-{j}

4. if (dist[v]+weight(v,t)

5. dist[t]=dist[v]+weight(u,v)

6.end while

7.return path

由算法2可知，Dijkstra算法的核心步驟是從未遍歷過的節(jié)點中選擇路徑權值最小的邊，該步驟需要遍歷所有的節(jié)點得到最小權值的邊，在網絡規(guī)模龐大的情況下，搜索時間很長。此外Dijkstra算法是根據單個參數(路徑長度的權值)尋找路徑，不能直接用于多個QoS度量參數約束的路由計算。

3 基于擴展Dijkstra的多約束QoS雙路徑路由算法設計

假設G(V,E)表示網絡拓撲模型，其中V表示網絡模型中所有網絡節(jié)點(例如交換機、路由器和主機等)組成的集合，E表示網絡節(jié)點之間的邊(即鏈路)組成的集合，每一條邊表示兩個網絡節(jié)點之間的直達通信路徑，每個網絡節(jié)點以及每條邊的QoS度量參數均是已知的。假設源節(jié)點為s(s∈V)，目的節(jié)點為d(d∈V)。實際常用的QoS度量參數包括時延(delay)、帶寬(bandwidth)、丟包率(loss)、代價(cost)、抖動(jitter)，對于網絡模型中的任意一個網絡節(jié)點n(n∈V)，給定四種QoS度量參數，分別為時延函數delay(n)，丟包率函數loss(n)，代價函數cost(n)，抖動函數jitter(n)。對于網絡模型中的任意一條邊e(e∈E)，給定四種QoS度量參數，分別為時延函數delay(e)，帶寬函數bandwidth(e)，代價函數cost(e)，抖動函數jitter(e)。

定義1(時延)：對于任意從源節(jié)點s至目的節(jié)點d的路由路徑P(s,d)(s、d∈V)，時延delay(P(s,d))的計算公式如下：

(5)

定義2(帶寬)：對于任意從源節(jié)點s至目的節(jié)點d的路由路徑P(s,d)(s、d∈V)，帶寬bandwidth(P(s,d))的計算公式如下：

bandwidth(P(s,d))=min{bandwidth(e),

e∈P(s,d)}

(6)

定義3(丟包率)：對于任意從源節(jié)點s至目的節(jié)點d的路由路徑P(s,d)(s、d∈V)，丟包率loss(P(s,d))的計算公式如下：

(7)

定義4(代價)：對于任意從源節(jié)點s至目的節(jié)點d的路由路徑P(s,d)(s、d∈V)，代價cost(P(s,d))的計算公式如下：

(8)

定義5(抖動)：對于任意從源節(jié)點s至目的節(jié)點d的路由路徑P(s,d)(s、d∈V)，抖動jitter(P(s,d))的計算公式如下：

(9)

文中所研究的多約束QoS雙路徑路由問題即在網絡拓撲圖G中尋找從源節(jié)點s到目的節(jié)點d的兩條路徑，它們均滿足公式(10)的約束條件。

(10)

其中，D、B、L、J分別代表以太網業(yè)務中QoS度量參數延遲、帶寬、丟包率和抖動的約束限制。

在對網絡拓撲進行路由查找之前，先對網絡拓撲結構進行精簡處理，將網絡拓撲結構過濾成一個新的簡單網絡拓撲結構，去除不滿足帶寬約束的邊以及孤立的網絡節(jié)點，則算法后續(xù)不再考慮帶寬度量參數的約束，只需要考慮延遲、代價、丟包率和抖動度量參數的約束。

(11)

算法3：ED_MCQOP算法。

輸入：網絡拓撲圖G(V,E)；n個網絡節(jié)點；源節(jié)點s；目的節(jié)點d；各個網絡節(jié)點(d,c,l,j)取值；每條鏈路邊的(d,b,c,j)取值；約束條件(D,B,L,J)的值。

輸出：兩條符合多約束QoS要求的路徑p1、p2。

1. remove all links which meet bandwidth(link)

2. remove all isolated nodes which belong toV

3.P={s}

4.N={neighbors ofs}

5. for each nodev∈N

7.f(v)=s// 前一跳節(jié)點

8. end for

9. whileN≠?

10. minL=min{L(s,v),v∈N}

11. new root=i(i∈the path with minL andi?P)

12. deleteifromN

13. additoP

14. for each nodej(j∈i’s neighbors andj?Pandj?N)

15. addjtoN

16. end for

17. for each nodekini’s neighbors

18. ifk?PN andL(k)>∑L(s,k)

19.L(k)=∑L(s,k)

20.f(i)=k

21. end if

22. end for

23. end while

24. ifL(s)>(AD+BL+CJ)/cost(P(s,d) return failure

25. else get the first pathp1

26. end if

27. for each nodev∈p1

28. if(v!=s&&v!=d) remove nodevand all links associated with nodev

29. end if

30. end for

31. updatePandN

32. recalculateL(v)

33. ifL(s) > (AD+BL+CJ)/cost(P(s,d) return failure

34. else get the second pathp2 and return pathp1 andp2

35. end if

假設Φ(x)是QoS度量參數中延遲的懲罰函數，如果路徑滿足延遲度量參數的約束時(delay(P(s,d))≤D)，值為1，否則等于rd(0

假設網絡拓撲中有m只螞蟻，n個網絡節(jié)點，已知每個網絡節(jié)點的QoS度量參數d、c、l、j取值，以及每條邊的QoS度量參數d、b、c、j取值，給定約束限制條件時延D、帶寬B、代價C、丟包率L、抖動J的取值，ED_MCQOP算法的偽代碼如算法3所示。

基于擴展Dijkstra的多約束QoS雙路徑路由算法首先對網絡拓撲圖進行一系列簡化，刪除不滿足帶寬約束的所有鏈路(第1行)，以及所有孤立的網絡節(jié)點，即沒有鏈路鏈接的網絡設備(第2行)，在網絡規(guī)模較大時，該操作可以有效地減少網絡規(guī)模的復雜度，減少算法的迭代次數。然后構造兩個網絡節(jié)點集合，一個是網絡節(jié)點集合P，集合P僅包含源節(jié)點s(第3行)，另一個是節(jié)點集合N，包含源節(jié)點s的所有鄰居節(jié)點(第4行)，第5行至第8行根據公式(11)引入多約束QoS約束限制，計算由源節(jié)點至源節(jié)點的所有鄰節(jié)點的多約束QoS度量值，并存儲每個節(jié)點的前一跳節(jié)點。

記錄可行路徑中多約束QoS度量值最小的路徑，將不屬于節(jié)點集P的網絡節(jié)點i標記為新的根節(jié)點root，并且從網絡節(jié)點集N中刪除網絡節(jié)點i，將網絡節(jié)點i添加到網絡節(jié)點集P中(第10至第13行)，將新的根節(jié)點root的所有鄰節(jié)點(不包括已經在網絡節(jié)點集P和網絡節(jié)點集N中的網絡節(jié)點)添加到網絡節(jié)點集N中(第14行至第16行)。遍歷節(jié)點i的所有鄰節(jié)點，進行多約束QoS度量值的比較更新，核心思想與第2節(jié)的Dijkstra算法一致，將滿足條件的節(jié)點標記值進行更新，更新節(jié)點的前一跳節(jié)點(第17行至第22行)。

當節(jié)點集N不為空時，進行第9行至第23行的迭代，得出具有最優(yōu)多約束QoS度量值的路徑，將其與給定的多約束QoS度量參數值進行比較，如果不滿足給定的約束條件，則說明網絡拓撲G(V,E)中不存在滿足多約束QoS約束限制條件的可行路徑，計算路由失敗，算法結束(第24行)。否則，得到第一條滿足多約束QoS條件的路徑p1(第25行)。刪除第一條可行路徑中除了源節(jié)點與目標節(jié)點的網絡節(jié)點以及每條與節(jié)點相關的鏈路(第27行至第30行)，該步驟是為了進一步減少網絡拓撲的復雜度，減少算法的迭代次數。然后刪除網絡拓撲中孤立的邊和網絡節(jié)點，更新網絡節(jié)點集P和網絡節(jié)點集N(第31行)，根據第3行至第23行，重新計算網絡節(jié)點的多約束QoS度量值L(v)(第32行)，將得到的最優(yōu)多約束QoS度量值的路徑與給定的多約束QoS度量參數值進行比較，如果不滿足給定的約束條件，則說明當前網絡拓撲中，不存在兩條滿足多約束QoS條件的可行路徑，至此，查找路由失敗，路由結束(第33行)。否則，得到第二條滿足多約束QoS條件的路徑p2，至此，獲取到兩條多約束QoS雙路徑路由，路由路徑計算成功(34行)。

文中所設計的基于擴展Dijkstra的多約束QoS雙路徑路由算法，考慮到以太網業(yè)務在實際網絡中，第一條路由路徑上的節(jié)點所在的不同子網絡的規(guī)?？赡芊浅４螅@樣在某些子網絡發(fā)生故障時，進行主備切換，使用第二條路徑進行正常工作，從而大大提高了數據傳輸的可靠性。同時，本算法在尋找可行性路徑的過程中，通過網絡拓撲圖的精簡，減少了網絡規(guī)模的復雜度，達到了減少算法計算復雜度的目的，并且充分考慮到了多約束QoS約束限制條件，使多約束QoS雙路徑路由計算能獲得最優(yōu)解且整體可靠性較高。

4 實驗結果與分析

本實驗主要從算法的迭代次數、平均時延、平均帶寬、平均代價、平均丟失率以及平均抖動來分析算法的性能。算法的迭代次數是指該算法從開始運行到最終返回滿足多約束QoS的兩條路徑或者查找路由失敗結束所需的迭代次數，與算法的時間復雜度有關。在該實驗中，為了減少實驗誤差，選取了100對源節(jié)點和目的節(jié)點，通過重復進行實驗計算平均值的方法獲取算法的平均迭代次數。

實驗所采用的不同規(guī)模的網絡模型均由基于MPLS的網絡管理系統(tǒng)通過批量建立離線設備節(jié)點生成，網絡節(jié)點數量分別設置為100、200、300、400和500，選取時延、代價、抖動三個可加性度量參數、一個可乘性度量參數丟包率以及一個凹性度量參數帶寬，由隨機數生成器生成一定區(qū)間內的隨機數，在不同的網絡規(guī)模下分別運用基于擴展Dijkstra的多約束QoS雙路徑路由算法、蟻群算法、遺傳算法記錄算法的迭代次數、時延、帶寬、代價、丟包率以及抖動。

圖1表示網絡拓撲圖中在不同的網絡規(guī)模下，ED_MCQOP算法、蟻群算法以及遺傳算法的平均迭代次數。從圖中可以看出，隨著網絡規(guī)模的增加，算法的平均迭代次數也隨之增加。同時，蟻群算法的平均迭代次數增長得最快，ED_MCQOP算法的平均迭代次數在不同網絡規(guī)模下相對于蟻群算法和遺傳算法都較少。

圖1 不同網絡規(guī)模下三種算法的平均迭代次數

假設時延約束delay=30 ms，圖2表示網絡拓撲圖中不同網絡規(guī)模下ED_MCQOP算法、蟻群算法以及遺傳算法的平均時延。從圖中可以看出，相較于蟻群算法和遺傳算法，ED_MCQOP算法的平均時延大多數情況下相對較低。

圖2 不同網絡規(guī)模下三種算法的平均時延

假設帶寬約束bandwidth=15 Mbit/s，圖3表示網絡拓撲圖中不同網絡規(guī)模下ED_MCQOP算法、蟻群算法以及遺傳算法的平均帶寬。從圖中可以看出，相較于蟻群算法和遺傳算法，ED_MCQOP算法的平均帶寬大多數情況下相對較低。

圖3 不同網絡規(guī)模下三種算法的平均帶寬

假設代價約束cost=30，圖4表示網絡拓撲圖中不同網絡規(guī)模下ED_MCQOP算法、蟻群算法以及遺傳算法的平均代價。從圖中可以看出，一般情況下，ED_MCQOP算法的平均帶寬相對較低。

圖4 不同網絡規(guī)模下三種算法的平均代價

假設丟包率約束loss=4.5×10-3%，圖5表示網絡拓撲圖中不同網絡規(guī)模下ED_MCQOP算法、蟻群算法以及遺傳算法的平均丟包率。從圖中可以看出，相較于蟻群算法和遺傳算法，ED_MCQOP算法的平均丟包率大多數情況下相對較低。

假設抖動約束jitter=20 ms，圖6表示網絡拓撲圖中不同網絡規(guī)模下ED_MCQOP算法、蟻群算法以及遺傳算法的平均抖動。從圖中可以看出，相較于蟻群算法和遺傳算法，ED_MCQOP算法的平均抖動大多數情況下相對較低。

圖5 不同網絡規(guī)模下三種算法的平均丟包率

圖6 不同網絡規(guī)模下三種算法的平均抖動

5 結束語

文中基于擴展的Dijkstra算法和蟻群算法的融合，研究包含延遲、帶寬、代價、丟包率和抖動度量參數的多約束QoS雙路徑路由問題，實驗結果表明，基于擴展Dijkstra的多約束QoS雙路徑路由算法在求解性能上優(yōu)于蟻群算法和遺傳算法，可用于求解網絡拓撲中的NP完全問題。