李學鋒　鄭毅

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

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

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

0 引言

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

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

1 CHOKe算法及其發(fā)展

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

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

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

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

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

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

對上面的算法進一步分析，發(fā)現(xiàn)存在以下的不足。

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

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

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

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

2 改進的CHOKe算法

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

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

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

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

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

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

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

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

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

3 仿真試驗與性能分析

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

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

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

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

4 結束語

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

參考文獻：

[1] 曾振平，汪秉文.因特網(wǎng)擁塞控制的公平性研究綜述[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] 王建新，周雄偉，楊湘.一種懲罰非適應流的無狀態(tài)主動隊列管理算法[J].系統(tǒng)工程與電子技術，2006.28（12）：1935-1939

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

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