一種基於抽樣統計改進的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算法識別出非適應流的能力。