一種基于抽樣統計改進的CHOKe算法

李學鋒　鄭毅

摘 要： 對流行的幾種CHOKe算法進行了分析，深入研究了CHOKe算法存在的對高速非適應流的處罰力度不夠，不能夠很好地實現帶寬的公平性的問題。利用到達分組的統計特性，提出一種改進的CHOKe算法，仿真結果表明，在不保持流的狀態信息下，該機制對非適應流具有更好的識別和控制能力，與其他CHOKe算法相比，能進一步加強對非適應流的懲罰，實現更為公平的帶寬分配。

關鍵詞： 主動隊列管理； CHOKe； 非適應流； 公平性

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2013）08-49-03

0 引言

目前Internet網絡擁塞控制的主要方法是采用端到端的TCP擁塞控制與中間結點（路由器）擁塞控制相結合的方法[1]。端到端的TCP擁塞控制根據網絡的丟包情況來判斷網絡的擁塞情況，從而調整源端的發送速率，從源頭來控制進入網絡的包的數量；中間結點的擁塞控制主要依據既定的策略對包進行丟棄，以達到對網絡的擁塞控制。

隨著非響應流在Internet所占比例的增加，中間結點的擁塞控制在整個擁塞控制中占的比重也隨之增加，中間結點擁寒控制算法越來越多地受到人們的關注。CHOKe[2]作為一種工作機制其相對簡單、實現容易的無狀態的中間結點擁塞控制算法受到人們的青睞，但如何進一步提高其對非適應流的識別的精確率，實現轉發流公平性成為當前研究的熱點。本文在深入分析現有的CHOKe各種算法基礎上，提出一種新的改進的CHOKe，并通過NS2模擬驗證了此算法對各流的公平性與對非適應流的精準性的效果。

1 CHOKe算法及其發展

CHOKe（choose and keep for responsive flows， choose and kill for unresponsive flows）算法是一種基于RED的改進算法，是一種完全無狀態的近似公平的隊列管理算法，即無需保留任何流的狀態信息就能實現一定公平的主動隊列管理算法（AQM）。當前CHOKe主要有B_CHOKe、M_CHOKe、A_CHOKe和LA_CHOKe等版本。

B_CHOKe算法：即基本的CHOKe算法，當一個分組到達時，就隨機從當前隊列中取出一個分組與之比較，如果二個分組都屬于同一個流，就同時丟棄這兩個分組；否則對將取出的分組放回隊列中，對剛到達的分組根據當時的擁塞水平計算丟棄概率（該丟棄概率的計算與RED算法相同），再按該概率對到達的分組進行丟棄。

M_CHOKe算法[3]：在B_CHOKe算法的基礎上，加大了從當前隊列中取出的分組的個數，即增加了比較次數。M_CHOKe算法從當前的隊列緩存中取出m（m>1），將所有的m個分組與剛到達的分組進行比較，若有與剛到達的分組有相同的流ID則丟棄。事實上，B_CHOKe算法是M_CHOKe算法當m=1的特例。

A_CHOKe算法[3]：由于CHOKe的完全無狀態的設計，事先并不能知道有多個非適應流，比較難以選取合適的m參數，為此CHOKe還有一種自適應改進類型，即A_CHOKe算法，該算法將minth和maxth之間劃分為k個區間，分別標記為R1，R2，…，Rk。當平均隊列長度位于不同的區間時，就選擇不同的m值。比如，當平均隊列長度位于Ri區間時，m=2i。當平均隊列長度越長，則比較的次數越多，從而能夠自適應地提高CHOKe算法識別出非適應流的能力。

ECHOKe算法[4]：在M_CHOKe的基礎上加大了對非適應流的懲罰力度，將m個分組中與到達分組的流標識匹配，若匹配，將所有匹配分組及到達分組都丟棄；若匹配不成功，將m個分組中的流標識相同者最大者（大于1）的一個分組丟棄。

S_CHOKe算法[5]：按間隔時間T對到達的分組進行采樣，將采樣分組的流標識放入采樣列表，對每一個到達的分組，先從采樣列表中隨機抽取一個流標識進行比較，若相同，則認為是采樣擊中，然后再與路由器隊列中m個分組相比較，若再次一樣，則稱為隊列擊中，刪除擊中分組。S_CHOKe算法以采樣擊中來代替提高擊中概率。

對上面的算法進一步分析，發現存在以下的不足。

⑴ B_CHOKe算法采用只比較一次，當網絡中流較多時，公平性與懲罰力度都會下降。

⑵ M_CHOKe算法與A_CHOKe算法通過增加比較的次數，提高了擊中概率，在擊中精度方面仍存在問題。同時也只是丟棄一個分組，懲罰力度也不夠大；另外，m個分組是從整個隊列中隨機抽出，沒能充分體現網絡數據包的突發性，同時也沒有充分地利用抽出的m個分組的統計信息來進一步加大對非適應流的識別精度。

⑶ ECHOKe將m個分組中擊中的所有分組全部丟棄，在增加了非適應流分組丟棄概率的同時，也增加了適應流的丟棄量。而適應流具有源端響應機制，一旦發現丟包，就會降低發送速率，從而更加不利于公平。因此，ECHOKe的懲罰精度不理想[6]。

⑷ S_CHOKe算法單獨設置的采樣隊列中存放的是到來分組的流ID的采樣，反映的不是路由器輸出隊列的統計特性，按照采樣擊中而進行的丟棄，也就不能體現路出器輸出的公平性，同時單獨設置的采樣隊列也占用了路由器的內存。

2 改進的CHOKe算法

針對現有CHOKe的不足，我們提出一種基于抽樣統計的改進方案——N_CHOKe，算法流程如圖1所示。

N_CHOKe算法的基本思想：路由器FIFO的平均隊列長度計算與RED相同，維持最小門限minth和最大門限maxth兩個閾值。當平均隊列長度小于minth時，新到達分組直接進入到FIFO隊列中；當平均隊列長度大于maxth時，丟棄新到分組；當平均隊列長度在minth與maxth之間時，從現FIFO隊列中的minth處到當前實際隊列結尾處這一段按照一定的間隔抽樣出m個分組，并統計出這個m個分組所屬的流k，以及這k個流包含的分組數。

將新到分組與k個流進行比較，比較結果如下。

⑴ 如果擊中，且被擊中的流的分組數大于等于[m/k]時，丟棄新到分組，并丟棄被擊中流中的一個分組；其余分組返回隊列。這樣做的目的是既要提高對高速非適應流的識別精度，也要在一定程度上加大對非適應流的懲罰力度。如果被擊中流的分組沒有超過[m/k]，則到達分組按照RED計算丟棄概率，并進行相應的處理。

⑵ 如果沒有擊中，新到達分組按照RED計算丟棄概率，并進行相應的處理；且查看k個流的分組長度，如果k個流中有分組數量大于或等于2倍[m/k]，丟棄此流的最后的一個分組。

與以往的其他CHOKe算法相比，N_CHOKe算法主要引入了以下三點措施。

⑴ 抽樣分組的區間的改變。抽樣分組將從隊列的minth處到隊列結尾（緩存區滿）之間抽取，將此區間分成K個小區間，當前平均隊列長度位于區間i時，m=2i。m個分組從minth處到當前隊列長度處抽樣得到，這樣可以更好地反映網絡數據的實時特性。

⑵ 通過統計抽樣出的m個分組所屬流，以及每個流所有的分組個數，充分地利用抽樣分組的統計特性，只有擊中的流的分組數目大于等于平均數時，才認為本次擊中是有效的，即是擊中了非適應流，這樣加大擊中非適應流的準確性，減少誤擊中適應流的比率。

⑶ 當沒有擊中時，通過將分組數目大于等于2*[m/k]的流丟棄一個分組，來加大對非適應流的處罰。

3 仿真試驗與性能分析

為了驗證N_CHOKe算法的有效性，在NS2仿真軟件上進行仿真實驗，對CHOKe、M_CHOKe、ECHOKe、SCHOKe和N_CHOKe進行性能比較。仿真實驗的網絡拓撲如圖2所示。

S1--Sn為發送端，D1--Dn為對應接收端。所有發送端到R1之間的鏈路與R2到接收端之間的鏈路的帶寬為10Mbps，延時為10ms。R1與R2之間的鏈路帶寬為1Mbps，延時為10ms。分組大小500字節，隊列參數minth=100，maxth=300，緩沖隊列長度為500。

本次實驗選擇9個TCP發送流，發送速率為0.1Mbps的FTP流；1個UDP流，UDP流的速率依次為0.1Mbps、0.2Mbps、0.4Mbps、0.8Mbps、1Mbps、2Mbps、4Mbps、8Mbps、10Mbps，每個速率持續發送10s。觀察當UDP速率逐漸提高的情況下，R1與R2間的帶寬分配情況。

通過仿真分析，得到各種UDP流實際占用帶寬如圖3所示，從圖3中可以看出，本文提出的N_CHOKe算法在TCP流與UDP流共存的情況下，對于公平性有了較大的提升。

4 結束語

本文在研究了現有的多種CHOKe算法的基礎上，提出了一種更加有效的N_CHOKe算法，此算法針對非適應流的特點，調整了取出分組的區域，重新設計了分組的丟棄策略，在保護適應流的同時，增加了對非適應流的識別精確度與懲罰力度，更好地分配了網絡資源，提高了網絡上各流之間的公平性。通過NS2進行了模擬實驗，結果顯示N_CHOKe算法提高了網絡上各流之間的公平性。

參考文獻：

[1] 曾振平，汪秉文.因特網擁塞控制的公平性研究綜述[J].計算機科學，2008.35（1）：19-23

[2] BRANDEN B， CLARK D，et al. Recommendations on Queue Management and Congestion Avoidance in the Internet[S].IETF RFC 2309，1998.

[3] PAN R， PRABHAKAR B， PSOUNIS K. CHOKe： A stateless active queue management scheme for approximating fair bandwidth allocation[A]. Proceedings of IEEE INFOCOM2000[C].Piscataway：IEEE Press，2000.2：942-951

[4] 王建新，周雄偉，楊湘.一種懲罰非適應流的無狀態主動隊列管理算法[J].系統工程與電子技術，2006.28（12）：1935-1939

[5] 龔靜，吳春明.S_CHOKe：一種增強CHOKe公平性的主動隊列管理算法[J].電子學報，2010.38（5）：1100-1104

[6] 姜明，邊浩，陳勤.HCHOKe：改進的公平主動隊列管理算法[J].計算機工程，2010.36（10）：115-116