N次隨機丟包的被動隊列管理算法

王文濤, 郭 峰, 王奇楓, 鄭 芳, 唐 菀

(中南民族大學 計算機科學學院，武漢 430074)

擁塞產生的本質原因是網絡資源無法合理分配以滿足通信需求.當通信子網負荷比較小時,網絡的吞吐量隨著網絡負荷的增加而線性增加.當網絡負荷增加到某一值后,網絡吞吐量反而下降,則表征網絡中出現了擁塞現象.當擁塞比較嚴重時,傳輸能力和節(jié)點緩沖器大多用來重傳,從而使通信子網的有效吞吐量下降，引起惡性循環(huán),進而使通信子網處于局部死鎖狀態(tài),最終導致網絡有效吞吐量接近于零.

擁塞控制分為兩部分：1)中間路由節(jié)點擁塞控制；2)邊緣終端節(jié)點擁塞控制，即TCP擁塞控制.

目前主要隊列管理機制分為主動隊列和被動隊列,IEFT推薦RED為主動隊列管理機制.主動隊列(以隨機早檢測RED為典型算法)需要消耗更多運算資源，并且參數設置沒有合理的解決方案，部分緩存沒有得到合理利用，并沒有在實際網絡上使用.文獻[1]指出隨機早檢測算法在現實網絡中的性能并不是最優(yōu)的，因為其算法復雜導致處理速度下降，沒有在實際網絡上使用[2].雖然后續(xù)研究提出改進的CR模型丟棄策略[3]，但并不適用.被動隊列是在隊列滿之后丟包，充分利用緩存，目前網絡中隊列管理采用這種機制，其優(yōu)點是實現比較簡單，但是存在死鎖、全局同步等問題.

邊緣終端節(jié)點擁塞控制通過TCP協議實現.通過“和式增加”、“積式減少”，對“慢啟動”、“擁塞避免”、“快重傳”、“快恢復”4個算法設置參數來實現不同的TCP擁塞控制[4].鑒于AQM的復雜性，以及PQM機制的不足[5],本文在中間節(jié)點擁塞控制方面做了相關研究，提出了N次隨機丟包隊列管理機制.

1 隊列管理機制分析

1.1 AQM

主動隊列管理(Active Queue Management, AQM)是隊列管理策略之一，可以有效解決“全局同步”問題.但是AQM存在參數設置敏感的缺陷，在不同的網絡狀況很難保持其性能[6].為了維持隊列長度穩(wěn)定、減少排隊時延并降低丟包率，主動隊列管理總是提前丟包，同樣會導致中間節(jié)點的傳輸效率下降.可見主動隊列管理是犧牲部分網絡傳輸效率來獲得低時延、隊列長度穩(wěn)定等性能[7].

RED是比較經典的主動隊列管理算法之一[8]，基本思想就是在擁塞發(fā)生的早期，動態(tài)計算當前隊列的平均隊列長度.當新分組到達的時候，根據當前平均隊列長度計算出分組丟棄概率p.在RED引入兩個門限參數m_min,m_max,當前平均隊列長度小于m_min,新來的數據包進入隊列，當前平均隊列長度∈(m_min,m_max)，則根據概率p丟棄，當前平均隊列長度大于m_max，到達分組直接丟棄，式(1)為丟棄概率計算函數，式(2)為平均隊列長度計算公式.隊列允許最大緩沖長度為Q_limit.Q_min,Q_max的計算公式如式(3)、(4)，兩個比例因子(0.4,0.8)、Pmax、w權值根據網絡情況確定[8].Q_avg平均隊列長度計算公式引入了w權值，是為了緩沖網絡抖動的影響，w一般取值為0.002左右，也就是反應了隊列長期的變化趨勢，短期的數據流并不會影響平均隊列長度大幅波動.

(1)

qN=(1-w)×qN-1+q_now.

(2)

Qmin=0.4×Q_limit.

(3)

Qmax=0.8×Q_limit.

(4)

1.2 PQM

被動隊列管理(PQM)是當前網絡中廣泛使用的隊列管理機制，其設計和實現比較簡單，而且對緩存利用率比較高.網絡中最常用的是棄尾隊列(DropTail)[9],也就是當網絡中緩沖區(qū)數據溢出的時候，丟棄到達的分組.

1.2.1 棄尾隊列

棄尾隊列(DropTail)是在隊列滿之后，所有到達的分組直接被丟棄，直到隊列有空余位置才吸收數據包.根據Jacobson對擁塞的研究發(fā)現，這種方式有如下3種嚴重的缺陷：

(1)全局同步現象.當網絡中大量數據通信時，導致網絡擁塞，所有后面到達的分組會被全部丟棄，所有發(fā)送節(jié)點都會檢測到重傳超時，發(fā)送端減小發(fā)送窗口，進入慢啟動或者擁塞避免.網絡空閑之后，所有發(fā)送節(jié)點再次增大發(fā)送速率，再次導致擁塞，重復上述情形，浪費了很多網絡資源.

(2)死鎖.少數TTL比較大的鏈接持續(xù)占用網絡資源，其他鏈接得不到足夠的網絡資源.

(3)隊列持續(xù)滿狀態(tài).當網絡發(fā)生擁塞的時候，隊列一直保持滿狀態(tài)，增加了排隊延遲.對于滿隊列造成的排隊時延，文獻[10]提出給隊列設定一個閾值，當隊列長度超過閾值之后，就開始隨機丟棄數據包，但是這個閾值的設定需要根據網絡情況，而且會造成硬件資源的浪費，對于突發(fā)數據流仍然無能為力.

1.2.2 棄首隊列

棄首隊列(DropFront),就是當緩沖隊列滿時，丟棄隊列首部的數據包，然后新數據包進入隊列.棄首隊列可以減少排隊時延，新來的數據包都能進入隊列，死鎖問題得到解決.但是當數據量比較大的時候仍然不能解決全局同步問題，以及隊列滿問題.

1.2.3 隨機丟棄隊列

隨機丟棄隊列(DropRand)，當緩沖隊列滿的時候，隨機從隊列中丟棄一個數據包，然后新到達的數據包進入隊列.由于隨機性，所以可以解決全局同步問題，以及死鎖問題，但是隊列持續(xù)滿狀態(tài)無法得到快速解決.丟棄一次對于整個隊列的影響速度比較慢.

1.2.4 兩次隨機丟包隊列管理算法

兩次隨機丟包隊列管理算法(DropRand2),當緩沖隊列滿的時候，隨機丟兩次數據包.在一定程度上比一次隨機丟棄隊列DropRand丟包效率要好，也就是加快了對擁塞的響應.對于棄尾隊列滿造成的排隊時延，被動隊列管理解決辦法之一就是如文獻[10]所述人為地縮短中間節(jié)點緩沖區(qū)長度，減少排隊時延.文獻[11]指出，RTT 小的 TCP 數據流的擁塞窗口的增長速度會快于RTT大的TCP數據流，從而占有較多的網絡帶寬，造成RTT不公平性問題.棄尾隊列管理存在速度不公平性，這點鮮見文獻報道.所謂速度不公平性就是連接同樣中間結點的鏈路，如果鏈路的速度不同則其發(fā)送的有效數據包差別很大，這并不是指鏈路速度快的發(fā)送端發(fā)送的有效數據包多，與其相反，仿真表明中間結點采用棄尾隊列管理時，鏈路速度快的發(fā)送端發(fā)送的有效數據包要少于鏈路速度慢的發(fā)送端發(fā)送的有效數據包，而且鏈路速度差異越大，前者發(fā)送的有效數據包就越少.

兩次隨機丟包的隊列管理策略在一定程度上能改善RTT的不公平性，丟包兩次主要是因為：

(1)隊列滿時，說明擁塞比較嚴重，因此只丟棄1個數據包是不夠的；

(2)如果一個 TCP 鏈接在隊列中的數據包個數為n個，隊列最大長度為Q個數據包，則該 TCP鏈接第1次被丟包的概率為n/Q，第2次被丟包的概率為(n-1)/(Q-1)或為n/(Q-1)，因此對占據隊列較多的TCP鏈接有更好的懲罰作用，改善了公平性.

兩次隨機丟包的被動隊列管理的具體算法如下[11]：

1) 有新的數據包要進入隊列，如果q

2) 有新的數據包要進入隊列，如果q≥Q-1，則計算一個[1,Q-1]之間的隨機值，丟棄該值位置的數據包，再次計算一個[1,Q-2]之間的隨機值，丟棄該值位置的數據包，新的數據包進入到隊列.

其中Q表示最大隊列長度，q表示當前隊列長度.

2 DropRandN

文獻[12]提出了N次棄頭的被動隊列管理算法，相對于一次棄頭，算法優(yōu)化了許多.文獻[11]提出了兩次隨機丟包算法，丟包次數是2次. 兩次隨機丟包能夠在一定程度上解決網絡擁塞的3個問題.一次隨機丟棄能夠緩解網絡擁塞，兩次效果又增進一步.可見丟棄次數與緩解網絡擁塞存在密不可分的關系.

2.1 N次隨機丟棄算法

基于以上思考，提出了N次隨機丟包的被動隊列管理算法.該算法是在緩沖隊列滿之后才開始丟棄數據包，所以屬于被動隊列管理算法.它有如下優(yōu)點：

緩沖隊列滿之后，表明當前網絡擁塞比較嚴重，那么隨機丟棄一次、兩次對于緩解擁塞來說太少.N次隨機丟包能夠更快地響應網絡擁塞，迅速地應對、處理擁塞.從概率上來講，N次對于占據隊列較多的發(fā)送端有較好的懲罰作用.

全局同步發(fā)生之后，所有發(fā)送節(jié)點同時減小擁塞窗口，所有節(jié)點發(fā)送速率下降.網絡此時會有部分空閑，但是發(fā)現空閑之后所有節(jié)點同時增大，再次導致網絡擁塞.這樣來回地爭奪帶寬導致了帶寬利用率的下降.N次隨機丟棄算法能夠以一定的數目隨機丟棄數據包，隨機程度比兩次隨機丟包要高，對網絡擁塞節(jié)點懲罰力度更大.能夠更加有效地打破全局同步的僵局.N次的選取借鑒黃金分割點比例0.618∶0.382,0.382接近1/3，故采用N/3.資源發(fā)生死鎖是因為部分節(jié)點因發(fā)送速度差異或者鏈路狀況差異，占據了大部分帶寬，其他節(jié)點發(fā)送速率嚴重下降.主要體現為速度不公平和鏈路RTT時延不公平.采用N次隨機丟棄能夠以更高的概率懲罰占據大量帶寬資源的節(jié)點，相對于兩次隨機丟包而言能夠更好地保證帶寬資源的公平性.

N次隨機丟包具體算法如下.

Qmax表示緩沖隊列長度，Qcurrent表示當前隊列長度，N為與當前節(jié)點通信的其他節(jié)點數目.

觸發(fā)事件：新數據包到達.

1)如果Qcurrent

2)如果Qcurrent>Qmax-1,緩沖區(qū)已滿，無法直接接納更多數據包，根據N值決定丟棄數量Ndrop=N/3,如果Ndrop<3 ,Ndrop=3至少丟3次.

3)根據Ndrop值采用N次隨機丟棄算法丟棄數據包.

2.2 改進的隨機丟棄策略

//一般的隨機丟棄策略

1: for i<-0 to N do

2: length<-_q->length

3: j<-random(length)

4: while(j--) do

5: _q->next

6: end while

7: drop(_q->current)

8: end for

//改進的隨機丟棄策略

1: for i<-0 to N do

2:rand_pos[i]<-random(_q->length)

3: end for

4: k<-0

5: while(j <= _q->length) do

6: j++

7: if(j=rand_pos[k])

8: drop(_q->current)

9: end if

10: _q->next

11: end while

一般的隨機N次丟棄算法，其思想就是每一輪掃描，隨機丟棄N個數據包，N=n/3,每次掃描長度為n, 兩層循環(huán)遍歷隊列，時間復雜度T(n)=O(n2).

改進的隨機N次丟棄算法，首先計算好N次隨機丟棄的位置，然后在掃描的時候通過和預定義丟棄位置對比，決定是否丟棄當前數據包.改進的隨機N次丟棄算法只需要隨機生成丟包位置N次，以及遍歷一輪隊列n次，N=n/3為常數，所以時間復雜度T(n)=O(n).這樣就可以大大降低N次隨機丟包的復雜性，而且只需要一個隨機算法以及遍歷操作，并不像文獻[11]中所說的增加了硬件開銷.

3 DropRandN性能分析

3.1 網絡拓撲結構

以下實驗仿真工具使用NS2,采用與文獻[13]類似的仿真方案.網絡拓撲結構采用經典啞鈴模型，本實驗采用動態(tài)節(jié)點配置,仿真節(jié)點數目可根據腳本動態(tài)設置，初始節(jié)點數目為20.關鍵鏈路位于R0和R1之間，帶寬10Mbit/s,時延10ms.其他節(jié)點與R0,R1鏈路之間帶寬20Mbit/s,延時10ms,所有Sender(i)節(jié)點向Receiver(i)節(jié)點發(fā)送數據，具體參見文獻[12].路由協議采用TCPNewreno，所有數據包大小為1000Byte.

3.2 全局同步問題

由于發(fā)送節(jié)點眾多，所以隨機抽取3個發(fā)送節(jié)點，來分析全局同步問題.R0和R1之間分別采用棄尾、兩次隨機丟包、N次隨機丟包來觀察擁塞窗口的變化情況，見圖1.

圖1 擁塞窗口變化Fig.1 The variation of congestion window

圖1(a)中，發(fā)送節(jié)點Sender20個，接收節(jié)點Receiver20個，R0和R1之間采用棄尾隊列，由于發(fā)送節(jié)點較多，所以只用其中3個節(jié)點觀察擁塞窗口變化情況.圖1(b)采用兩次隨機丟棄隊列管理，圖1(c)采用N次隨機丟包隊列管理.可以看出，圖1(a)出現全局同步現象，而且3個節(jié)點擁塞窗口同步現象十分嚴重.圖1(b)，1(c)采用隨機策略，隨機使得各個發(fā)送節(jié)點發(fā)現擁塞的時機不一致，從而避免全局同步現象的發(fā)生.圖1(c)和圖1(b)相比，3個節(jié)點擁塞窗口變化幅度有所減小，因為當網絡發(fā)生擁塞的時候，N次隨機丟棄能夠更快地處理擁塞情況，幅度的減小也說明N次隨機丟包能夠使網絡中各個節(jié)點擁塞窗口變化更加平緩，這樣有利于提高網絡帶寬的利用率.

3.3 網絡資源死鎖問題(RTT，速度不公平)

RFC2309指出死鎖經常會出現部分鏈路占據大部分帶寬的現象.

在棄尾隊列中，發(fā)送速率是造成死鎖的因素之一，速率快的節(jié)點會比速率慢的節(jié)點先發(fā)現網絡的擁塞，發(fā)送窗口開始減少，速率下降，而速率慢的節(jié)點速率下降得慢，占據大部分帶寬.

對文獻[12]中拓撲結構作如下調整,R0,R1 帶寬為0.5Mbit/s,Sender0,Sender1與R0之間20Mbit/s,Sender2為速度最快鏈路80Mbit/s，然后分別使用DropTail,DropRand2,DropRandN.由圖2可以看出，圖2(a)DropTail棄尾隊列速率最快的節(jié)點擁塞窗口最小，也就是一直處于低速率發(fā)送狀態(tài)，始終處于不公平狀態(tài).這是因為速率快的節(jié)點頻繁呈現擁塞避免，導致發(fā)送速率較低；圖2(b)采用兩次隨機丟包策略，能夠解決這種速率上的不公平；隨機N次丟包算法擁塞窗口中(圖2(c))，擁塞過程數目比圖2(b)要多，也就是圖中尖角.這是因為隨機N次丟包一次丟棄了大量節(jié)點，短時間內不會出現頻繁的擁塞，所以能夠更快速地緩解擁塞.

圖2 3種算法對于擁塞窗口的變化Fig.2 Three algorithm responding to the variation of cwnd

擁有不同RTT時延的鏈路也會產生網絡資源死鎖問題，少部分鏈路占用大部分帶寬.RTT時間比較短的鏈路能夠盡早地檢測到網絡擁塞，開始TCP擁塞避免，而RTT較長的鏈路此時可能還未發(fā)現網絡擁塞，速率沒有下降，所以RTT大的鏈路也會占據大部分帶寬.對文獻[12]中拓撲結構作如下調整,最后一個節(jié)點延時20ms，是其他普通鏈路的兩倍，R0與R1之間鏈路速度為0.5Mbit/s，為了讓網絡更加擁塞，20個節(jié)點同時發(fā)送數據.圖3(a)棄尾隊列可以看出節(jié)點node3擁塞窗口一直很大，比另外2個節(jié)點擁塞窗口都大.由于20個節(jié)點繪圖分析太多，所以隨機抽取2個普通節(jié)點和最后一個RTT大的節(jié)點.經分析得知，由于R0和R1之間采用了棄尾隊列，RTT大的node3節(jié)點短時間內未檢測到擁塞，其他節(jié)點已經開始擁塞避免，擁塞窗口開始減小，節(jié)點node3未減小擁塞窗口，占據大部分帶寬.其他節(jié)點只能分得很小的一部分.文獻[11]中隨機丟2次也能很好地解決死鎖問題，圖3(b)隨機兩次丟棄算法擁塞窗口沒有出現死鎖現象.

N次隨機丟棄算法，由于丟棄的隨機性，能很好地解決死鎖問題，同時丟棄數目的增加能夠對RTT較長有更好的懲罰作用.多個節(jié)點之間擁塞窗口比較接近，這也表明更多的隨機次數能夠有效打破死鎖僵局，圖3(c)各個節(jié)點擁塞窗口變化沒有出現全局同步，同時也沒有出現部分節(jié)點占據大部分帶寬，而且相對于兩次隨機丟包而言，節(jié)點擁塞窗口分布更加均勻，能夠更好地利用帶寬資源.

圖3 不同算法在不同RTT下擁塞窗口變化Fig.3 Cwnd of different algorithms responding to different RTT

3.4 持續(xù)滿

隊列滿后, 后來的數據包全被丟棄, 不能吸收突發(fā)的數據流,但是這是在采用棄尾策略時考慮的問題.隊列滿主要影響是使后來的數據無法進入隊列而被丟棄.

隨機丟棄策略就可以解決這個問題, 在隊列滿時隨機丟棄數據包, 后來的數據包都能夠進入隊列, 就能夠吸收突發(fā)的數據流.兩次隨機丟棄每次可以空出2個位置來吸納突發(fā)數據包.但是兩次隨機丟包空余出來的容量有限，如果數據流持續(xù)擁塞，那么會頻繁丟包.N次隨機丟包可以較好地解決隊列抖動問題，當隊列滿時丟棄N個數據包，隊列有較大空余容量吸收更多數據包，擁塞次數大大減少，這點從圖2(c)和圖3(c)可以看出.

3.5 傳輸效率

文獻[12]的網絡拓撲中，分別采用RED, DropTail, DropRand1, DropRand2,DropRandN,設置發(fā)送節(jié)點個數為4,8,10,12,20,40,接收節(jié)點個數與發(fā)送節(jié)點個數相同.統計100s內關鍵鏈路R0到R1之間的有效包個數如表1.發(fā)送節(jié)點Sender對應Ndrop分別為 3，3，3，4，6，13[11].DropRandN傳輸效率分別比DropTail,RED,DropRand1,DropRand2高出91%,2.6%,1.2%,0.8%.

4 結論

被動隊列的改進主要集中在隨機以及棄首兩個方面，與主動隊列相比，被動隊列算法比較簡單，容易實現，對硬件資源要求也少.主動隊列算法盡可能地利用中間節(jié)點的運算能力來提高改善擁塞狀況.但是事實上中間節(jié)點運算能力并不強，反而加劇擁塞程度；同時基于當前兩次隨機丟棄次數進行了改進，改進的丟棄策略提高了其性能，提出了N次隨機丟棄被動隊列管理算法DropRandN.N次丟棄能夠對占據網絡帶寬的鏈路有更好的懲罰作用，在低速率以及高RTT時延的鏈路發(fā)揮更好的作用.仿真結果表明：該算法能夠很好地處理全局同步、死鎖、隊列持續(xù)滿3個主要問題，其設計簡單、效率高，容易在現有物理網絡基礎上更新.

N次丟棄對于當前擁塞程度判斷不是很準確，這是下一步需要研究的；同時N次也需要改進，因此后續(xù)工作是結合文獻[14]研究出相關關系之后，設計出自適應隨機丟包算法，再次提高網絡傳輸的性能.

參 考 文 獻

[1] Tahiliani M P, Shet K C.Analysis of cautious adaptive red (cared)[C]// IEEE. Advances in Computing, Communications and Informatics (ICACCI), 2013 International Conference on IEEE. Mysore: ICACCI, 2013: 1029-1034.

[2] Raghuvanshi D M, Tahiliani M P. On the effectiveness of CoDel for active queue management[C]// IEEE.Advanced Computing and Communication Technologies (ACCT), 2013 Third International Conference on IEEE. Rohtak: ACCT,2013: 107-114.

[3] Kong Zhizhou, Cai Zixing, Chen Yulin.A packet dropping strategy based on C-R model[C]// IEEE.Intelligent Information Technology Application. Third International Symposium on IEEE. Nanchang: IITA,2009: 437-440.

[4] 王宏偉.TCP/IP網絡擁塞控制中主動隊列管理算法研究[D].沈陽：東北大學,2008.

[5] May M, Bolot J, Diot C, et al.Reasons not to deploy red[C]// IEEE. 1999 Seventh International Workshop on Quality of Service, London:IWQoS′99,1999: 260-262.

[6] 任豐原,林 闖,王福豹.RED算法的穩(wěn)定性:基于非線性控制理論的分析[J]. 計算機學報, 2002(12):1302-1307.

[7] 梁 潘.基于NS2的PQM和AQM的仿真實現與比較[J].常州工學院學報,2010,Z1:60-63;79.

[8] Floyd S, Jacobson V. Random early detection gateways for congestion avoidance [J]. IEEE/ACM Transactions on Networking, 1993, 1(4):397-413.

[9] 王云濤.網絡擁塞控制算法研究[D].上海:東華大學,2010.

[10] Zheng C, Dai Y, Chen J. Is current active queue management really necessary[C]// IEEE. Education Technology and Computer Science, First International Workshop on IEEE. Wuhan: ETCS,2009: 538-541.

[11] 姜文剛,孫金生,王執(zhí)銓.兩次隨機丟包的被動隊列管理算法[J].系統仿真學報,2011(5):987-991;997.

[12] 姜文剛,孫金生,王執(zhí)銓.N次棄頭的被動隊列管理算法[J].小型微型計算機系統,2011(9):1849-1853.

[13] 王文濤,王 豪,郭 峰,等.基于OMNeT++的AODV-UU、DSR-UU 和DYMOUM路由協議性能仿真與分析[J].中南民族大學學報：自然科學版,2013,32(4):91-96.

[14] Jiang W, Shang J, Sun J, et al. Reformed passive queue management algorithm[C]//IEEE.Electrical and Control Engineering, 2011 International Conference on IEEE. Yichang:ICECE,2011: 3087-3090.