[發明專利]兩次隨機丟包的被動隊列管理的方法

有效

• 申請號: 201110054044.9
• 申請日: 2011-03-07
• 公開（公告）號: CN102123094A
• 公開（公告）日: 2011-07-13
• 發明（設計）人: 姜文剛;尚婕;孫金生;王執銓
• 申請（專利權）人: 江蘇科技大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 樓高潮

技術領域

本發明涉及數據通信領域，尤其涉及兩次隨機丟包的被動隊列管理的方法。

背景技術

TCP通過“慢啟動”、“擁塞避免”、“快速重傳”、“快速恢復”4個算法設置不同的參數來實現不同TCP擁塞控制，就是和式增加積式減少(AIMD，additive?increase?multiplicativedecrease)，TCP根據擁塞窗口來調整發送速度。瓶頸節點中最常用的隊列管理策略是“棄尾”(Drop?Tail)，即隨著緩沖區的溢出而丟包，是一種被動隊列管理機制。“棄尾”的缺陷包括數據流的全局同步，死鎖及持續隊滿造成的突發數據流被扼殺等。主動隊列管理雖然可以有效地解決“全局同步”問題，但存在參數設置敏感，響應相對滯后于實際網絡狀況的缺陷，其算法比較復雜。在實際使用中，復雜的算法給網絡設備帶來很大的開銷，中間節點的性能下降，反而加重了網絡擁塞，所以目前各種主動隊列管理算法并沒有在網絡上大量使用。

發明內容

本發明的目的就是采用兩次隨機丟包的被動隊列管理的方法，避免全局同步和死鎖，提高網絡資源的利用率。在網絡發生擁塞，瓶頸節點隊列滿時，在瓶頸節點隊列中兩次丟棄數據包，每次隨機丟棄1個。該方法簡單，不會增加瓶頸節點的計算量。由于是在瓶頸節點隊列滿時才丟棄數據包，所以是一種被動式隊列管理的方法。

為了實現上述目的，本發明采用的技術方案是：

當瓶頸節點隊列滿時，計算一個1到隊列長度減1的隨機數，丟棄位于該隨機數的數據包；再次計算一個1到當前隊列長度減1(為丟包前隊列長度減2)的隨機數，再丟棄位于該隨機數的數據包。采用兩次隨機丟包主要是因為：(1)瓶頸節點隊列滿時，說明擁塞比較嚴重，因此只丟棄1個數據包是不夠的；(2)如果一個TCP鏈接在隊列中的數據包個數為n個，隊列最大長度為Q個數據包，則該TCP鏈接第一次被丟包的概率為n/Q，第二次被丟包的概率為(n-1)/(Q-1)或為n/(Q-1)，因此對占據隊列較多的TCP鏈接有更好的懲罰作用，改善公平性。瓶頸節點具體操作步驟如下：

Q表示瓶頸節點隊列的最大長度，q表示當前瓶頸節點隊列長度。

(1)判斷是否有新的數據包要進入瓶頸節點隊列，如果否則還是在第(1)步，如果是則到第(2)步；

(2)判斷是否q≥Q-1，如果是則到第(3)步，如果否則到第(7)步；

(3)調用隨機函數計算得到[1，q-1]之間的隨機數；

(4)丟棄位于步驟(3)計算得到的隨機數位置的數據包；

(5)調用隨機函數計算得到[1，q-2]之間的隨機數；

(6)丟棄位于步驟(5)計算得到的隨機數位置的數據包；

(7)新數據包進入頻率節點隊列，然后再到第(1)步。

本發明方法能避免全局同步和死鎖，改善網絡傳輸的公平性，提高網絡資源的利用率。該方法簡單，適合在現有的Internet上使用。

附圖說明

圖1是本發明方法的流程圖；

圖2是本發明方法進行測試的網絡拓撲。

具體實施方式

下面結合附圖對本發明作進一步詳細說明。

本發明中Q表示隊列的最大長度，q表示當前瓶頸節點隊列長度。瓶頸節點對新數據包的處理方法如圖1所示，

(1)判斷是否有新的數據包要進入瓶頸節點隊列，如果否則還是在第(1)步，如果是則到第(2)步；

(2)判斷是否q≥Q-1，如果是則到第(3)步，如果否則到第(7)步；

(3)調用隨機函數計算得到[1，q-1]之間的隨機數；

(4)丟棄位于步驟(3)計算得到的隨機數位置的數據包；

(5)調用隨機函數計算得到[1，q-2]之間的隨機數；

(6)丟棄位于步驟(5)計算得到的隨機數位置的數據包；

(7)新數據包進入頻率節點隊列，然后再到第(1)步。

圖2是本發明方法的測試網絡環境，R0為瓶頸節點，瓶頸鏈路位于節點R0和節點R1之間，鏈路容量12Mbps，延時15ms，分別采用不同的隊列管理，緩存大小為30packets；節點Si均為持久性FTP業務源，他們與節點R0之間的鏈路容量均為20Mbps，延時15ms，向目標節點Di發送數據；節點Di與節點R1之間的鏈路容量均為20Mbps，延時15ms；數據包均為1040Byte(包括40Byte包頭)。接收端Di的窗口設置足夠大，使得TCP發送僅受擁塞窗口Cwnd控制。