[發明專利]控制隊列緩沖區的方法

有效

• 申請號: 201210426544.5
• 申請日: 2002-04-05
• 公開（公告）號: CN103220229A
• 公開（公告）日: 2013-07-24
• 發明（設計）人: M.邁爾;R.盧維格
• 申請（專利權）人: 艾利森電話股份有限公司
• 主分類號: H04L12/861
• 分類號: H04L12/861
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 朱海煜

技術領域

本申請書涉及控制隊列緩沖區的方法，所述隊列緩沖區連接到鏈路并且被安排來對準備通過所述鏈路發送的數據單元進行排隊。

背景技術

在基于數據單元的通信中，亦即，其中，要傳輸的信息分成多個單元，而且各個單元通過通信網絡發送，眾所周知，在沿著網絡的鏈路上提供隊列緩沖區，使得通過這樣的鏈路傳輸的單元可以被緩沖。緩沖區可以是發送或輸入緩沖區(亦即用于要通過所述鏈路發送的數據單元的緩沖區)或接收或輸出緩沖區(亦即用于已經通過所述鏈路發送的數據單元的緩沖區)。

用于傳輸數據的這樣的單元可以有不同的名稱，諸如通信協議數據單元、幀、分組、段、單元(cell)等，取決于特定的上下文、所用的特定通信協議和某些其他習慣。在本文獻的情況下，所有這樣的數據單元都一般地稱作數據單元。

把數據單元放入隊列、使它們在所述隊列中向前走、并從所述隊列取出數據單元的程序稱作隊列管理。

在數據單元傳輸網絡中一種已知的現象是所謂擁塞現象。擁塞的意思是已經不可能輕易地處理準備通過所述連接或鏈路傳輸的數據單元數目的狀態。由于在給定鏈路上擁塞的結果，與所述鏈路相關的隊列緩沖區中的數據單元數目將增加。對擁塞狀態作出反應，眾所周知，已實現一種所謂隊滿丟棄(drop-on-full)的數據單元丟棄機制，按照所述機制，所述隊列緩沖區接收新數據單元時，將與隊列長度相關的參數，諸如實際隊列長度或平均隊列長度與預定的閾值比較，若超過閾值，則丟棄數據單元。所述閾值指示隊滿狀態。“丟棄”的意思是不把它放入隊列，因而不會把它進一步傳輸。

準備丟棄的數據單元可以是新到的數據單元，在這種情況下，所述機制被稱作隊尾丟棄，除隊尾丟棄技術外，已知還實現所謂隨機丟棄，其中按照隨機函數挑選一個已經在隊列中的數據單元，或者所謂隊首丟棄，其中丟棄所述隊列中的第一個數據單元。這樣的隊滿丟棄機制不僅用來減少擁塞鏈路的負載，而且用來向所述數據單元的信源和/或目的地發出暗示性擁塞通知。就是說，例如，正如從TCP(傳輸控制協議)已知的，對數據單元的接收者和發送者一般都實現擁塞控制機制，使得當檢測到數據單元已經丟失時，減少數據單元的發送速率和/或數量。

除一旦超過預定的閾值，亦即一旦判定隊“滿”，就開始丟棄數據單元這樣的隊列管理系統之外，還有人提出了比較老練的管理方案，被稱作積極的隊列管理，在意見征詢(Request?for?Comment?(RFC))2309中作了描述。更具體地說，RFC?2309建議被稱作隨機早期檢測(RED)的積極隊列管理機制。按照RFC?2309，RED的概念是認識到不要等到隊滿，而是實現一種在達到隊滿狀態之前就導致丟棄某些分組的機制是有用的。

按照RFC?2309，RED算法包括兩個主要部分，就是說，首先估計平均隊列的大小，然后決定是否丟棄輸入的數據單元。更具體地說，當新數據單元到達時，所述算法估計平均隊列大小，若平均隊列大小處于最小閾值min_th和最大閾值max_th之間，則作為平均隊列大小的函數計算一個幾率值，并根據所得幾率判斷是否要丟棄所述輸入的數據單元。若平均隊列大小超過最大閾值max_th，則所述輸入的數據單元必須丟棄。幾率函數是一個線性函數，它具有一個值p(min_th)＝0，而其中p(max_th)是預定的最大幾率max_p，其中max_p小于1。

關于最小閾值min_th或最大閾值max_th的選擇，RFC?2309并未提供任何信息。

在Sally?Floyd和Van?Jacobson在1993年8月的IEEE/ACM?Transaction?on?networking上的“避免擁塞的隨機早期檢測網關”一文中對RED算法作了廣泛的討論，其中最小閾值min_th，最大閾值max_th和最大幾率max_p都被設置為固定的參數。關于min_th和max_th的選擇，它指出這些閾值的最佳值取決于需要的平均隊列大小，而max_th的最佳值部分地取決于鏈路可以允許的最大平均延遲時間。另外，它指出max_th至少應為min_th的兩倍。