Internet路由器主動式隊列管理機制綜述(1)

　　 
　　眾所周知，由于Inte.net采用的是統計復用(statistical multiplexing)技術，因此必須提供擁塞控制機制。TCP端到端的擁塞控制機制是確保Internet魯棒性（robustness）的重要因素。在發生擁塞時，TCP源端會降低發送數據的速度，從而使得大量的TCP連接能夠共享一條擁塞的鏈路。

TCP擁塞控制機制已被證明在防止擁塞崩潰（congestion collapse）方面取得了巨大的成功。但這種機制的有效性依賴于兩個基本的假設：
　　
　　所有（或者幾乎所有）的流都采用了擁塞控制機制
　　
　　這些流采用的機制是同質的（homogene- ous）或者大體上相同即在相似的環境下按可比條件（丟包率、RTT、MTU）不會占用比TCP流更多的帶寬，也即是TCP友好的（TCP-friendly）流。
　　
　　但隨著近十年來計算機網絡的爆炸式增長，特別是多媒體業務的廣泛應用，Internet已經不可能再僅僅依靠端節點提供的擁塞控制機制。這是由于下述原因，導致以上假設不成立：
　　
　?。?） 一些應用沒有采用擁塞控制機制因而不能對擁塞作出反應。許多多媒體應用和組播應用都屬于此類。
　　
　?。?） 有些應用使用了擁塞控制算法，但并不是TCP友好的，比如接受端驅動分層組播（Receiver-driven Layered Multicast RLM）采用的就是這種算法。
　　
　?。?） 一些用戶由于有意或無意的原因，使用了 non-TCP的擁塞控制算法。比如修改TCP，使得窗口的初始值很大并且保持不變，即所謂的"快速TCP"。
　　
　　另外，我們知道，Internet上的流量是由無數條異質的數據流混合而成的。從有無有效擁塞控制機制的角度可以將這些異質的流分為以下三類：
　　
　　TCP-friendly流
　　
　　非適應（unresponsive）流：這種流是由于上述原因（1）造成的。
　　
　　適應（responsive）流但非TCP- friendly流：這種流是由于上述原因（2）和（3）引起的。
　　
　　很明顯，這些不受TCP擁塞控制的應用會進一步增加Internet范圍內擁塞崩潰的可能，并且TCP擁塞控制還存在著自相似、效率、公平性等方面的問題。因此盡管TCP擁塞控制機制是必須的而且非常強大，但仍然需要采用基于路由器的擁塞控制機制對端節點的擁塞控制機制進行補充。
　　
　　擁塞避免機制的首要任務是檢測早期的擁塞。這是因為，路由器能夠有效地監控隊列的長度，因此其也能有效地檢測早期的擁塞（incipient congestion）。擁塞避免機制的另一個任務是選擇哪個流發出擁塞通知。因為路由器能夠全面地審視各個流對產生擁塞的影響，因此其也能夠有效地決定將擁塞信息通知哪個源端，使其降低數據發送速度。
　　2 從傳統的被動式隊列管理到主動式隊列管理
　　
　　
　　由于路由器是基于包交換的設備，每個端口采用帶寬統計復用，所以路由器必須在端口上維護一個或多個隊列，否則路由器無法處理多個數據包同時向同一端口轉發以及端口QOS等問題。對隊列進行管理直接影響路由器性能、擁塞管理能力以及QOS能力。路由器有兩類和控制隊列的算法：隊列管理算法和隊列調度算法。前者主要是在必要時通過丟包來管理隊列長度。后者決定下一個要發送哪個包，主要用來管理各流之間帶寬的分配。
　　
　　由于Internet數據本質上是突發的，因此允許傳輸突發的數據包非常必要，而路由器中隊列的重要作用就是吸收（absorb）突發的數據包。較大的隊列能夠吸收更多的突發數據，提高吞吐量，但TCP機制往往會保持較高的隊列占用，從而增加了數據包的排隊延遲。因此需路由器對隊列進行管理，維持較小的隊列長度。因為維持較小的隊列長度除了降低排隊延遲，提高吞吐量外，還能保持較大的隊列空間來吸收突發數據包。擁塞控制機制就是要維持網絡處于低延遲高吞吐量的狀態。
　　
　　當前的隊列管理算法可以分為兩大類：被動式隊列管理（Passive Queue Management，PQM）和主動式隊列管理（Active Queue Management，AQM）。
　　
　　2.1 被動式隊列管理及其缺陷
　　
　　管理路由器隊列長度的傳統技術是對每個隊列設置一個最大值（以包為單位），然后接受包進入隊列直到隊長達到最大值，接下來到達的包就要被拒絕進入隊列直到隊長下降。這種技術也就是所謂的"去尾"（drop-tail）算法。雖然這個方法在當前Internet上得到了廣泛的使用，但其存在幾個重大缺陷：
　　
　　死鎖（lock-out）問題：在某些情況下，"去尾"算法會讓某個流或者少數幾個流獨占隊列空間，阻止其他流的包進入隊列。這種"死鎖"現象通常是由于同步（synchronization）或其他定時作用的結果。
　　
　　滿隊列（full queues）問題：由于"去尾"算法只有在隊列滿時才會發出擁塞信號，因此會使得隊列在相當長時間內處于充滿（或幾乎充滿）的狀態。而隊列管理最重要的目標之一就是降低穩定狀態下隊列的長度，因為端到端的延遲主要就是由于在隊列中排隊等待造成的。
　　
　　全局同步（global synchronization）問題：由于Internet上數據的突發本質，到達路由器的包也往往是突發的。如果隊列是滿的或者幾乎是滿的，就會導致在短時間內連續大量地丟包。而TCP流具有自適應特性，源端發現包丟失就急劇地減小發送窗口，包到達速率就迅速下降，于是網絡擁塞得以解除，但源端得知網絡不再擁塞后又開始增加發送速度，最終又造成網絡擁塞，而且這種現象常常會周而復始地進行下去，從而在一段時間內網絡處于鏈路利用率很低的用狀態，降低了整體吞吐量，這就是所謂地"TCP全局同步"現象。
　　
　　除了"去尾"機制，另外兩種在隊列滿時進行隊列管理的機制是"隨機丟棄"（random drop）和"從前丟棄"（drop front）機制。當隊列滿時，前者從隊列中隨機找出一個包丟棄以讓新來的包進入隊列；后者從隊列頭部丟包，以便讓新包進入隊列。這兩種方法雖然都解決了"死鎖"問題，但仍然沒有解決"滿隊列"問題。由于這幾種方法都是在隊列滿了被迫丟包，因此稱為被動式隊列管理。
　　
　　2.2 主動式隊列管理及其優點
　　
　　在當前的Internet上，丟包是對端節點進行擁塞通知的重要機制，解決路由器"滿隊列"的方法便是在隊列充滿之前丟包，這樣端節點便能在隊列溢出前對擁塞作出反應。這種方法便稱為"主動式隊列管理"（Active Queue Management）。
　　
　　AQM是一族基于FIFO調度策略的隊列管理機制，使得路由器能夠控制在什么時候丟多少包，以支持端到端的擁塞控制。AQM有以下優勢：
　　
　　減少了路由器中丟棄的包的數量：Internet中數據包的突發本質是不可避免的，AQM通過保持較小的平均隊列長度（average queue size），能提供更大的容量吸收突發數據包，從而大大減少了丟包數。進一步說，如果沒有AQM，會有更多的包被丟棄，這主要是因為以下三個原因：
　　
　　1) 由于使用共享的隊列和PQM，會不可避免地產生全局同步，導致很低的平均帶寬利用率，也即吞吐量很低。
　　
　　2) TCP從突發包的丟棄中恢復要比從單個包丟棄中恢復更復雜。
　　
　　3) 如果一個數據包在到達目的端之前被丟棄，則其在傳輸過程中所消耗的資源都被浪費，降低了網絡帶寬的利用率。因此，不必要的包丟棄也就意味著帶寬的浪費。
　　
　　對交互式服務提供了更低的延遲：AQM通過保持較小的平均隊列長度，隊列管理能夠減少包的排隊延遲（queueing delay），而排隊延遲是造成端到端延遲（end to end delay）的主要原因。這對交互式應用比如Web瀏覽、Telnet業務和視頻會議等非常重要。
　　
　　避免了"死鎖"現象：AQM能夠通過確保到來的包幾乎總是有可用的隊列空間，從而阻止"死鎖"行為的發生。也因為這個原因，AQM能防止路由器對低帶寬高突發的流的偏見。
　　RED擁塞控制機制的基本思想是通過監控路由器輸出端口隊列的平均長度來探測擁塞，一旦發現擁塞逼近，就隨機地選擇連接來通知擁塞，使他們在隊列溢出導致丟包之前減小擁塞窗口，降低發送數據速度，從而緩解網絡擁塞。由于RED是基于FIFO隊列調度策略的，并且只是丟棄正進入路由器的數據包，因此其實施起來也較為簡單。
　　
　　3.1 隨機早期檢測的設計目標
　　
　　RED主要試圖達到以下目標：
　　
　　最小化包丟失率和排隊延遲
　　
　　避免全局同步現象
　　
　　避免對突發業務的偏見：網絡中含有大量的突發數據，而傳統的"去尾"算法對突發業務有很大的偏見。在采用"去尾"算法的路由器中，如果某個流的突發性越高，則當該流的包進入隊列時越容易造成隊列溢出，從而導致連續地丟棄大量的該流的包。
　　
　　即使在缺乏傳輸層協議有效配合的情況下也能控制平均隊列長度，從而避免擁塞。
　　
　　為了達成以上目標，RED采用了基于時間的平均隊列長度，并且隨機地選擇正進入路由器地包進行丟棄。這種方法能被有效地實施而無需在路由器中維持每個流（per-flow）的狀態信息。
　　
　　3.2 隨機早期檢測算法
　　
　　RED算法主要分為兩個部分。首先是計算平均隊列長度，以此作為對擁塞程度的估計。另一個就是計算丟棄包的概率。
　　
　　3.2.1 計算平均隊列長度
　　
　　由于Internet數據的突發性，如果一個隊列很多時候是空的，然后迅速被充滿，又很快被取空，這時就不能說路由器發生擁塞而需要向源端發送擁塞指示。因此，RED在計算平均隊長avgQ時，采用了類似低通濾波器（low-pass filter）帶權值的方法：
　　
　　avgQ = (1-w)×avgQ+q×w
　　
　　其中，w為權值，q為采樣測量時實際隊列長度。這樣由于Internet數據的突發本質或者短暫擁塞導致的實際隊列長度暫時的增長將不會使得平均隊長有明顯的變化，從而"過慮"掉短期的隊長變化，盡量反映長期的擁塞變化。
　　
　　在計算平均隊長的公式中，權值w相當于低通濾波器的時間常數，它決定了路由器對輸入流量變化的反應程度。因此對w

原文轉自：http://www.kjueaiud.com