一種基于優(yōu)先級的帶寬時延路由算法

李軍旺

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

關鍵詞：節(jié)點時延；優(yōu)先級；帶寬時延約束

1 問題的提出

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

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

2 —種基于優(yōu)先級的帶寬時延改進算法

2.1 王勇智算法分析

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

2.2 算法的改進思路與描述

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

2.2.1 節(jié)點時延的定義

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

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

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

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

2.2.2 分組丟棄策略

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

2.2.3 算法的改進思路與描述

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

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

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

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

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

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

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

4 結語

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

[參考文獻]

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

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

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