流量管理中隊列調度算法研究

喬俊超，王愛國

(1.武漢郵電科學研究院，湖北 武漢430074;2.烽火通信股份有限公司，湖北 武漢430074)

隨著IPTV對網絡帶寬需求的快速增長，針對流量的管理需求也日益強烈。流量管理主要涉及網絡帶寬控制和分配、通信延遲的降低和擁塞控制的最小化。流量管理提出的目標是用于高效管理網絡資源，并且為用戶提供需要的帶寬和服務等級［1］。在通信設備的內部，流量管理能夠在流量發生擁塞時，對數據進行合理的處理，使得用戶端能夠得到一個很好的QoS體驗。由于流量在設備內部發生擁塞時會導致端口數據吞吐量下降，增加端到端延遲，引起傳輸抖動和數據丟包等問題，因此如何合理地進行流量管理來減少擁塞至關重要。在設備內部的包交換芯片中流量管理部分可以分為以下幾個主要方面:流量分類(Traffic Classification)、流量監控(Traffic Policing)、緩存管理(Buffer Management)、流量調度與整形(Traffic Scheduling & Shaping)、流量標記(Traffic Marking)［2］。本文將主要研究流量調度部分的隊列調度算法。隊列調度的功能是確定輸出端口在下一個時刻，從哪個隊列中輸出數據包。高效和公平性是隊列調度算法兩個很重要的指標，如何高效和公平地調度是一個很復雜的問題，在進行隊列調度時，由于需要平衡調度算法的復雜度、控制的簡易程度和對不同服務等級流量的公平性，所以隊列調度算法目前是研究的熱點。

目前隊列調度有多種算法，例如FIFO、PQ、FQ、WFQ、WRR(CBQ)、DRR、DWRR等。每種隊列調度算法都有其優缺點和適用場景，如何在不同的場景下合理高效地運用調度算法值得研究。本文將針對目前運用較多的DWRR調度算法做研究，分析其優缺點，并在其不足的基礎上提出改進方法。

1 DWRR調度算法

赤字加權輪詢(Deficit Weighted Round Robin，DWRR)是基于Round Robin的算法，由M.Shreedhar和G.Varghese在1995年提出。DWRR是隊列調度算法中的一個基本算法［3］。根據數據包業務類型的不同，匯聚到不同的服務隊列，每個隊列稱為CLS(Class of Services)，DWRR算法按照一定的輪詢機制來輸出每個服務隊列的數據包，同時每個服務隊列基于分配的權重值，享受不同級別的服務。

WRR是基于每個隊列的幀數來計算的，而DWRR是基于每個隊列的字節數來計算的，對數據流的控制更精準。DWRR算法主要有以下幾個參數:

1)DC［i］(Deficit Counter)變量。用以記錄第i個隊列可用的信用度，即每次輪詢該隊列時允許調度器訪問的字節總數。

2)Quantum［i］參數。根據每個隊列的權重值來配置。用于在每次輪詢到第i個隊列時，向DC里面補充一定的信用度，即DC［i］=DC［i］+Quantum［i］。

DWRR算法具體的執行步驟如下:

1)初始化時，根據每個隊列的權重分配相應的Quantum值，并把每個隊列的DC值設為初始值0。

2)開始輪詢，查看當前隊列是否為空，若為空隊列，則跳過本隊列，訪問下一隊列，并把DC［i］設為0;若為非空隊列，則DC［i］=DC［i］+Quantum［i］，若此時DC［i］大于等于隊列頭部數據包幀長，則DC［i］=DC［i］-Queue［i］_head_packetsize，發送該數據包之后，再對此隊列進行判斷，直到隊列為空或者DC［i］小于隊列頭部數據包幀長，則訪問下一隊列，剩余的DC［i］累加到下次輪詢。DC［i］不能小于0。

3)結束一輪輪詢之后，重新從步驟2)開始，如此循環。

DWRR算法優點:解決了WFQ計算復雜度高和WRR無法應對數據包長度變化的問題，提供了一種更精確的帶寬分配算法;但是也存在一些不足，例如若一個隊列一直傳送數據包直到DC［i］小于隊列頭部數據包幀長時，可能引入抖動，使得DWRR難以支持實時業務，同時DWRR算法里面不支持DC［i］為負數，使得當DC［i］小于當前隊列數據包幀長時，可能需要經過若干次輪詢積累足夠信用度之后，才能傳送隊列里的數據包，可能會使隊列出現“帶寬饑餓”現象［4］。因此有必要針對算法中的不足進行改進，使得算法既能夠保證低加權值的延遲性能，同時又能保證對各個隊列帶寬分配的相對公平性，盡量避免出現“帶寬饑餓”。

2 改進的DWRR算法

通過認真分析DWRR算法存在的不足，本文提出了一種改進型DWRR算法——IDWRR(Improved DWRR)，能夠在一定程度上解決DWRR算法的缺點。

為全面提升養殖場的經濟效益，部分養殖戶會獨自飼養生豬，自己屠宰并銷售，通常為家庭分工協作飼養、共同負責產銷，這種自產自銷模式在一定程度上有利于穩定生豬市場，但受到經濟利益的限制，部分養殖戶在生豬養殖中，存在供不應求的現象。為解決這一問題，養殖戶從外地引入肉質，屠宰并兼顧銷售，使疫情因素轉變，一旦消毒不徹底，將會導致外來疫病的傳入，不利于生豬自產自銷事業的發展。另外，不能定期消毒、接種疫苗，也增加了各類疾病發生的幾率，且呈大面積擴散趨勢，不利于生豬養殖事業的發展。

IDWRR算法有以下3個狀態變量:

1)Weight［i］，為 每個隊列的權重值，正整數，可以取0，取0時該隊列變為SP(Strict Priority)模式，這里不討論。指定該隊列相對于其他隊列所占的帶寬比例，需要配置。

2)彈性因子K，為正整數，用于計算隊列的信用額度補給。當每輪輪詢結束后，所有的DC［i］計數器值為負數時，K的值會被重新計算。每個隊列的Quantum［i］=Weight［i］×2K，K的值是下一輪輪詢時，能使所有DC［i］經過補給后大于0的最小值。

3)DC［i］變量，用以追蹤第i個隊列相對于其指定的權重值所占帶寬的情況。DC［i］允許小于0。

相比于之前的DWRR算法，IDWRR算法改進之處主要在于:1)彈性因子K來決定每個隊列每次獲得補充的信用度;2)DC［i］小于0。K值重新計算的條件:當每輪輪詢結束后每個隊列的DC［i］都小于0。

改進后DWRR的算法執行步驟如下:

2)輪詢開始，若當前隊列為空，則保持當前的DC［i］值不變，輪詢下一隊列。若當前隊列非空，則對DC［i］進行信用度補給，即DC［i］=DC［i］+Quantum［i］，補給之后，若DC［i］大于當前隊列頭部數據包幀長時，則發送該數據包，DC［i］=DC［i］-Queue［i］_head_packetsize;發送之后再次進行判斷，若DC［i］≥0且DC［i］的值小于 當 前 隊 列 頭 部 數 據 包 幀 長 時，則DC［i］=DC［i］-Queue［i］_head_packetsize，之后DC［i］變為負數，結束當前隊列，輪詢下一隊列。

3)結束一輪輪詢后，若所有隊列DC［i］都為負數，則重新計算K值，Quantum［i］也隨之改變，接著從第二步開始;否則直接從第二步開始，如此循環。

當所有DC［i］為負時，表明網絡突入大量數據包，可能出現擁塞情況，原有的K值可能不能有效緩解網絡擁塞，所以K值需要重新計算;當只有部分DC［i］為負值時，這時K值不進行更新，因為只要相應數據流的隊列不為空，DC［i］在每輪輪詢時都會獲得補充，這時和DWRR的功能相同。利用彈性因子K的好處在于可以實時統計網絡中的實際數據包幀長，相比于之前的DWRR算法能夠減少延時、減少傳輸抖動;允許DC［i］為負數則使得相應數據流在信用額度不足時，能夠先發送一個數據包，然后再在下一輪補充，這樣在一定程度上增加了公平性。

IDWRR算法的流程圖如圖1所示。

3 仿真結果

3.1 仿真網絡的拓撲結構和主要參數

本文中采用網絡仿真器NS-2來仿真IDWRR算法的性能［5］，并且與未改進的DWRR算法進行比較。仿真網絡的拓撲結構如圖2所示。

圖2中S1，S2和S3分別用戶發送端，D1，D2和D3分別為對應的用戶接收端，CE1和CE2分別為網絡用戶邊緣路由器，C為網絡的核心路由器，CE1與C是瓶頸鏈路，帶寬為2 Mbit/s，核心鏈路帶寬為10 Mbit/s。主要驗證在發送相同數據包的情況下，DWRR和IDWRR在延遲和公平性方面的性能比較。S1，S2和S3分別發送BE，AF和EF數據流，使其進入不同的隊列［6］。S1，S2和S3到CE1的鏈路延時固定為10 ms，BE，AF和EF數據流在NS-2中的配置如表1所示。

表1 NS-2中數據流配置

3.2 仿真結果分析

由于篇幅的限制，在CE1的輸出端口側只針對BE和EF兩個數據流在延時和公平性方面做對比。圖3和圖4的仿真結果分別為BE、EF數據流在兩種算法下延時的比較;圖5的仿真結果是在兩種算法下，BE和EF數據流分別配置相同權重值、公平性的比較。

在數據流的配置中，雖然數據流的幀長是變化的，但是兩種算法采用幀長隨機的隨機種子是一樣的，所以在同一時刻，兩種算法對應的數據流幀長是相同的，這樣能更方便地對比兩種算法的性能。

從圖3和圖4的NS-2仿真結果可以看出，IDWRR相比DWRR減少了數據流傳輸的延時，對于BE數據流的延時，采用DWRR調度算法平均延時45 ms，而采用IDWRR調度算法平均延時32 ms，改進后的算法延時降低約29%;對于EF數據流的延時，采用DWRR調度算法平均延時33 ms，而采用IDWRR調度算法平均延時29 ms，改進后的算法延時降低約12%。通過對BE和EF數據流延時的比較，可以看出IDWRR在延時性上有很大提高。

圖5在公平性方面對兩種算法做出了比較，根據之前的權重配置，從總體上BE數據流的帶寬為0.33 Mbit/s，EF數據流的帶寬為1 Mbit/s。在比較公平性時，本實驗比較數據輸出速率的波動性。從圖5中可以看出對于BE數據流，兩種算法的總體平均速率都是0.33 Mbit/s，但是IDWRR數據流的輸出速率比DWRR要平緩，速率波動比較小;對于EF數據流，兩種算法的總體平均速率雖然都是1 Mbit/s，然而DWRR的數據流輸出比IDWRR速率波動要大。經過仿真分析可以得出改進的IDWRR算法在公平性上比DWRR有提高。

通過對BE和EF數據流在延時和公平性上的仿真分析可以得出，IDWRR算法相比于DWRR算法性能上有很大的提高，符合算法改進的預期效果。

4 結束語

本文主要研究DWRR算法，分析其不足之處，并在其基礎上提出了一種改進算法，改進算法能夠根據彈性因子K來計算當前網絡中的最大數據包幀長，以此來調節每個隊列的信用額度補給Quantum，能夠在一定程度上降低傳輸延遲，提高隊列接入的公平性，從而提高了網絡的服務質量。雖然對傳輸延時有一定的改進，但是隊列調度只依靠這一種算法還不能保證QoS，所以應該和其他算法一起協同工作，來滿足用戶對不同業務QoS的要求。

［1］杜曉萍.時隙可變長分組緩存調度算法［J］.電視技術，2012，36(21):37-41.

［2］XIAO Xipeng.Technical，commercial and regulatory challenges of QoS［M］.American:Morgan Kaufmann Publishers，2008.

［3］Juniper Network.Supporting differentiated service classes:queue scheduling disciplines［EB/OL］.［2012-06-06］.http://folk.ntnu.no/einersen/arkiv/4.klasse/01h/TTM4150-Nettverksarkitektur/Readings/Congestion%20control%20-%20Queue%20scheduling%20disciplines.pdf.

［4］閔捷，周紅瓊，王曉東.一種基于優先級的加權公平隊列調度算法［J］.寧波大學學報:理工版，2012，4(2):42-46.

［5］肖權權，段迅.基于NS2的網絡仿真與性能測試［J］.計算機技術與發展，2012，4(22):25-28.

［6］潘遲龍，張基宏.基于WRR的改進型隊列調度算法［J］.電信快報，2012(1):34-37.