區分服務中一種動態概率優先級調度算法

摘要：提出了一種動態概率優先級算法DPP，針對一類對延時和丟包率要求相對較高的應用，根據AF1隊列長度動態調整概率計算參數p，有效地解決了由于突發流量帶來的QoS性能下降問題。不同實驗環境下的仿真結果表明，DPP算法有效改善了突發性對分組平均排隊延時的影響，減少了分組丟包率。

關鍵詞：區分服務； 概率優先級調度； 突發流量； 動態概率優先級調度

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)12-0339-03

區分服務被視為解決當今IP網絡服務質量問題最有前景的技術。區分服務網絡可以在傳統IP網絡的盡力而為型服務之上提供多種其他的服務，并以路由器節點上的每跳行為描述。目前除了缺省PHB－BE之外，IETF還定義了兩種典型的PHB，即加速型EF和確保型AF^[1]。獎賞服務PS在邊緣對數據流進行整形，丟棄超過約定帶寬的數據包，以保證輸入數據流速率小于輸出帶寬，在核心通過EF PHB保證EF流的帶寬。因此，獎賞服務可以提供低延時、低抖動、低丟失率和保證帶寬的高質量傳輸服務。確保服務AS在邊緣對包進行標記，當包的到達速率超過預約速率時，并不像EF對包進行丟棄一樣，而是將其標記為高丟棄優先級。當數據包到達網絡核心時，AF PHB根據當前網絡狀況對包實行優先級丟棄^[2]。

典型的區分服務節點的輸出端是由一個EF、四個AF（AFi，i=1，2，3，4）^[3]和一個BE構成的多隊列調度系統。在EF與AF/BE之間采用嚴格優先級調度SP，可以保證EF具有三低一保證的特性，并且不受AF/BE負載變化的影響。由于在邊緣路由器上對EF流進行整形，EF作為一個具有良好行為的流進入網絡，也不會使AF/BE流發生“餓死”現象^[4]。對于AF流在網絡邊緣并沒有丟棄數據包，到達核心的數據流仍具有較大的突發性。如果在AF與BE之間仍然采用嚴格優先級調度的話，很有可能將BE流“餓死”^[5]。文獻[6]中提出的概率優先級調度算法PP，通過合理設置參數p可以解決BE流“餓死”問題。

不同的應用對QoS要求不同。本文在PP算法的基礎上，針對一類對延時和丟包率要求相對較高的應用，提出了動態概率優先級調度算法DPP，改善了該類應用在突發環境下的QoS性能，同時對其他業務類沒有產生大的影響。

4結束語

現有的概率優先級調度算法用于區分服務中，能夠很好地解決AF與BE之間采用嚴格優先級調度帶來的BE流“餓死”問題。本文提出的DPP算法對于一類對延時和丟包率要求較高的應用，動態調整AF1隊列參數P₁，有效地解決了由于流量突發性帶來的分組平均排隊延時和丟包率增大問題，同時通過控制參數mp，能夠盡量減少對其他隊列性能的影響。

參考文獻：

[1]林闖，單志廣，任豐原.計算機網絡的服務質量[M].北京:清華大學出版社， 2004:35-50.

[2]CLARK D， FANG W. Explicit allocation of best effort packet delivery[J]. IEEE/ACM Transactions on Networking， 1998，6(4):362-373.

[3]HEINEHAN J， FINNER T， BAKER F， et al. RFC 2597， Assured forwarding PHB group[S].[S.l.]: IETF， 1999.

[4]MAO J M， MOH W M， WEI B. PQWRR scheduling algorithm in supporting of diffServ[C]//Proc of IEEE ICC’01. Helsinki:[s.n.]， 2001.

[5]JUNG S， KWAK J， BYEON O. Performance analysis of queue sche－duling mechanisms for EF PHB and AF PHB in diffServ networks[C]//Proc of IEEE HSNMC’02. Korea:[s.n.]， 2002.

[6]JIANG Y， THAM C K， KO C C. A probabilistic priority scheduling discipline for multi－service networks[C]//Proc of IEEE ISCC’01. Tunisia:[s.n.]， 2001.

[7]THAM C K， YAO Q， KO C C. Achieving differentiated services through multi－class probabilistic priority scheduling[J]. Computer Networks， 2002，40(4):577-593.

[8]UCB/LBNL/VINT network simulator－NS(version 2)[EB/OL].http://www－mash.cs.berkeley.edu/ns/.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”