一種基于優先級的帶寬時延路由算法

李軍旺

摘要：針對王勇智算法在負荷較重時，低等級業務丟包率較高的不足，文章改進了其剪枝條件，引入節點時延和優先級約束，提出一種基于優先級的帶寬時延約束路由算法P-BDCBR。從仿真結果來看，改進的算法在重負荷時，在丟包率以及吞吐量等方面較原算法有一定的優越性。

關鍵詞：節點時延；優先級；帶寬時延約束

1 問題的提出

在高速多媒體網絡中，時延是一個很重要的QoS度量參數，時延過大，會造成用戶在視覺和聽覺上的不適應，甚至無法播放。針對高速多媒體網絡中的時延約束，國內外研究者很多，也提出了一些較好的算法，如Wang等[1]提出的基于帶寬與時延約束的路由算法，Juttner等提出的基于時延約束、代價最小的路由算法，王勇智基于節點負荷率提出的Wang-Crowcroft改進算法。

至今提出的各種算法，它們針對的具體問題與所采用的策略是不相同的，已經證明當相加型或相乘型約束大于或等于兩個時，其最優路徑的求解是NP完全問題，在多項式時間內沒有精確的解，故大多采用啟發式算法[2]。對于時延約束類的路徑求解問題，一般將帶寬作為先決條件，剪去不滿足要求的鏈路，然后用最短路徑算法求解時延問題。這類算法最關鍵的問題是剪枝，通過剪去不滿足QoS要求的鏈路來簡化尋找路徑的拓撲結構，以降低算法的計算復雜度。

2 —種基于優先級的帶寬時延改進算法

2.1 王勇智算法分析

王勇智針對Wang-Crowcroft算法的不足，提出了一種基于節點負荷率的帶寬時延約束路由算法。該算法在Wang-Crowcroft算法的基礎上加入節點負荷率的約束條件，以鏈路時延和節點負荷率為度量，剪去不合要求的鏈路，再用Dijkstra算法計算最短路徑。該算法的優點是可以在一定程度上降低高帶寬鏈路的擁塞度，其缺點是開銷大以及未考慮對不同優先級的業務進行區別處理，在負荷較重時，傳統盡力而為業務的丟包率可能較高。

2.2 算法的改進思路與描述

針對王勇智算法在負荷較重時，低等級業務丟包率較高的不足，本文改進了其剪枝條件，引入節點時延和優先級約束。當節點負荷較大，超過門閥值時，不是簡單的剪枝，而是根據業務的優先級，將高優先級的業務映射到其他鏈路，而低優先級的業務仍按原鏈路傳輸。基于以上考慮，將MPLS的約束路由機制與業務優先級相結合，提出一種基于優先級的帶寬時延約束路由算法P-BDCBR。

2.2.1 節點時延的定義

其中，Dn表示節點的時延；T表示節點在輕負荷時的轉發處理時間；Ek（n）表示優先級為k的業務在節點緩存中的相對緩存占用率，其在數值上等于所占緩存與總緩存的比。

假設在MPLS網絡中某個節點中同時有M個優先級的業務流，這些業務流在緩存區中按其優先級的高低排隊，當一優先級為k的業務流到達時，該業務流只能排在優先級為k-1的業務流之前而排在優先級為k+l的業務流之后。因此，當有新的業務流到達時，只需計算比其優先級高的業務占用的緩存區就可以了。顯然，即使是在網絡狀態相同的情況下，Ek（n）也會因為業務優先級的不同而有所不同，保證了不同優先級業務占用的資源。設有m個優先級的業務，則有：

Em（n）≥Em-1（n）……≥Ek（n）……≥E1（n）。

這樣，既保證了高優先級業務能得到優先服務，又可以在一定程度上降低低優先級業務的丟包率。

2.2.2 分組丟棄策略

采用優先級與RED算法相結合的丟棄策略[3]，在MPLS網絡每個節點內部，用MD算法來決定分組的丟棄與否，而丟棄哪個分組由優先級來決定。

2.2.3 算法的改進思路與描述

采用源路由策略，當一個業務流到達MPLS網絡時，采用改進的剪枝策略，剪去帶寬與鏈路時延不符合要求的鏈路，然后計算節點的時延值。隨著流過節點的流量的增加，節點的負荷會越來越重，節點的時延也會相應有所提高，當達到門閥值時，對于高優先級的業務，則將該節點剪去，將高優先級業務映射到其他節點，然后用Dijkstra算法計算最小代價路徑；對于低優先級的業務，由于其肯定沒有達到時延的門閥值，所以仍按原路徑發送。這樣可在均衡流量的同時，在一定程度上降低了低優先級業務的丟包率。

3 算法的仿真實驗及比較分析

采用ns-allinone-2.30版本，在MNS_v2.0擴展包的基礎上添加MPLS流量工程模塊，修改部分底層C++源代碼與ns-mpls-cr.tcl文件。實驗在Windows+Cygwin環境下進行。本次實驗只驗證BE類流在高優先級的EF類流加入的時候在兩種算法下的表現。主要從丟包率和請求的吞吐量（Throughput）兩個方面進行對比分析，仿真結果如圖1一2所示。

從圖1一2可以看出：在0.5?5 s的時間段內，BE流的吞吐量比較平穩，丟包率也比較低，兩種算法性能表現相似。這是因為此時網絡的整體負荷較小，性能穩定。

5?8 s的時間段內，BE流吞吐量下降，丟包率有所升高。兩種算法相比，P-BDCBR算法的變化幅度相對明顯。這是因為隨著EF類流的加入，網絡中的流量不斷增多，網絡整體性能下降，但由于此時網絡的整體負荷不是很大，性能還可以。對于王勇智算法由于沒有考慮優先級，業務流在競爭時是“平等”的，而對于P-BDCBR算法，由于EF類流的優先級較高，爭搶資源時有優勢，故對BE類流有一定影響，吞吐量下降明顯些，丟包率高些。

8?15 s的時間段內，BE流吞吐量進一步下降，丟包率進一步升高，到15 s左右達到極限值。兩種算法相比，P-BDCBR算法下BE流的變化幅度比5?8 s時更明顯些。這是因為隨著網絡中的流量進一步增加，網絡負荷越來越重、性能下降，此時EF流由于優先級較高搶占了較多資源，對BE流的影響更加明顯。

15?30 s的時間段內，BE流的吞吐量增加、丟包率下降，兩種算法相比，差別較大，P-BDCBR算法明顯要優異些。這是因為在15 s左右，節點時延達到門閥值，P-BDCBR算法的EF流被映射到備用鏈路，網絡的負荷迅速減輕。而王勇智算法的EF流、BE流同時被映射到備用鏈路，仍存在相互搶奪資源的情況。

4 結語

P-DBCBR算法在原算法的基礎上，改進了它的剪枝策略，加入了優先級約束，將優先級與流量有機地結合起來。當節點的負荷較重時，既保證了高優先級業務的“優先性”，又在一定程度上降低了低優先級業務的丟包率，提高了網絡的吞吐量，減少了擁塞。從仿真結果來看，改進的算法在重負荷時，在丟包率以及吞吐量等方面較原算法有一定的優越性。

[參考文獻]

[1]WANG Z， CROWCROFT J.QoS Routing for supporting resource reservation[J].IEEE Journal on Selected Areas in Communications，1996（7）：1288-1294.

[2]尹國定，于戰科，倪明放.多約束QoS路由的一種啟發式算法[J].計算機工程與科學，2004（2）：53-55.

[3]金明嘩，黃永明，李樂民.一種新的IP分組丟棄策略PRDP[J].電子與信息學報，2002（8）：1073-1079.