一種基于抽樣統(tǒng)計(jì)改進(jìn)的CHOKe算法

李學(xué)鋒　鄭毅

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

關(guān)鍵詞： 主動(dòng)隊(duì)列管理； CHOKe； 非適應(yīng)流； 公平性

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）08-49-03

0 引言

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

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

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

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

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

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

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

ECHOKe算法[4]：在M_CHOKe的基礎(chǔ)上加大了對(duì)非適應(yīng)流的懲罰力度，將m個(gè)分組中與到達(dá)分組的流標(biāo)識(shí)匹配，若匹配，將所有匹配分組及到達(dá)分組都丟棄；若匹配不成功，將m個(gè)分組中的流標(biāo)識(shí)相同者最大者（大于1）的一個(gè)分組丟棄。

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

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

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

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

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

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

2 改進(jìn)的CHOKe算法

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

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

將新到分組與k個(gè)流進(jìn)行比較，比較結(jié)果如下。

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

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

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

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

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

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

3 仿真試驗(yàn)與性能分析

為了驗(yàn)證N_CHOKe算法的有效性，在NS2仿真軟件上進(jìn)行仿真實(shí)驗(yàn)，對(duì)CHOKe、M_CHOKe、ECHOKe、SCHOKe和N_CHOKe進(jìn)行性能比較。仿真實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)淙鐖D2所示。

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

[5] 龔靜，吳春明.S_CHOKe：一種增強(qiáng)CHOKe公平性的主動(dòng)隊(duì)列管理算法[J].電子學(xué)報(bào)，2010.38（5）：1100-1104

[6] 姜明，邊浩，陳勤.HCHOKe：改進(jìn)的公平主動(dòng)隊(duì)列管理算法[J].計(jì)算機(jī)工程，2010.36（10）：115-116