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

2019-11-05 00:34:18

字體：大中小

來源：轉載

供稿：網友

　　眾所周知，由于Internet采用的是統計復用(statistical multiplexing)技術，因此必須提供擁塞控制機制。TCP端到端的擁塞控制機制是確保Internet魯棒性（robustness）的重要因素。在發生擁塞時，TCP源端會降低發送數據的速度，從而使得大量的TCP連接能夠共享一條擁塞的鏈路。TCP擁塞控制機制已被證實在防止擁塞崩潰（congestion collapse）方面取得了巨大的成功。但這種機制的有效性依靠于兩個基本的假設：
　　
　　所有（或者幾乎所有）的流都采用了擁塞控制機制
　　
　　這些流采用的機制是同質的（homogene- ous）或者大體上相同即在相似的環境下按可比條件（丟包率、RTT、MTU）不會占用比TCP流更多的帶寬，也即是TCP友好的（TCP-friendly）流。
　　
　　但隨著近十年來計算機網絡的爆炸式增長，非凡是多媒體業務的廣泛應用，Internet已經不可能再僅僅依靠端節點提供的擁塞控制機制。這是由于下述原因，導致以上假設不成立：
　　
　　（1）一些應用沒有采用擁塞控制機制因而不能對擁塞作出反應。許多多媒體應用和組播應用都屬于此類。
　　
　　（2）有些應用使用了擁塞控制算法，但并不是TCP友好的，比如接受端驅動分層組播（Receiver-driven Layered Multicast RLM）采用的就是這種算法。
　　
　　（3）一些用戶由于有意或無意的原因，使用了 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的選擇非常重要，假如w過大，那么RED就不能有效地過慮短暫的擁塞；假如w太小，那么avgQ就會對實際隊列長度的變化反應過慢，不能合理地反映擁塞狀況，在這種情況下，路由器就不能有效檢測到早期的擁塞。w的值應根據不同情況預先設置，一般來說，它是由路由器答應發生的突發業務的大小和持續的時間所決定的。
　　
　　3.2.2 計算丟棄包的概率
　　
　　計算平均隊長的目的就是為了反映擁塞狀況，根據擁塞的程度來計算丟棄包的概率，從而有效地控制平均隊列長度。
　　
　　RED有兩個和隊列長度相關的閾值：minth和maxth。當有包達到路由器時，RED計算出平均隊長avgQ。若avgQ小于minth，則沒有包需要丟棄；當minth≤avgQ≤maxth時，計算出概率P，并以此概率丟棄包；當avgQ>maxth時，所有的包都被丟棄（如圖1所示）。由于RED使用的是基于時間的平均隊長，就有可能會發生實際隊長大于平均隊長的情況，假如隊列已滿，則到達的包只能被丟棄。
　　　

　　計算概率P的方法如下：
　　
　　Pb = maXP×(avgQ-minth) / (maxth-minth)
　　P = Pb / (1-count×Pb)
　　
　　我們注重到P不僅和avgQ有關，而且還和從上一次丟包開始到現在進入隊列的包的數量count有關。隨著count的增加，下一個包被丟棄的可能性也在緩慢增加。這主要是為了在到來的包之間均勻間隔地丟包，避免連續丟包，從而避免對突發流的偏見和產生全局同步現象。
　　
　　對隊列治理而言，吞吐量和排隊延遲始終是一對矛盾的關系。假如平均隊長能夠充分權衡吞吐量最大化和延遲最小化之間的矛盾，從而在總體性能上得到較為理想的結果，則該隊長稱為理想的平均隊長。閾值minth和maxth就是由理想的平均隊長決定的。一般來說，maxth－minth應大于一個回路響應時間內平均隊長的增加值，以避免由于路由器丟棄過多的包而導致全局同步。根據目前Internet上數據流的特點，可以將maxth設為minth的兩倍。由于理想的平均隊長依靠于不同的網絡條件，因此，如何確定理想的平均隊長仍是一個有待研究的問題。
　　
　　3.3 顯式擁塞指示（Explicit Cogestion Notifica- tion ECN ）
　　
　　在RED機制中，當平均隊長超過一定的閾值時便開始丟包了，也就是說RED是在隊列未滿的情況下丟包的，并不是由于隊列溢出而被迫丟包的。在這種情況下丟包，雖然使得RED有效地治理了平均隊長，但也浪費了網絡資源，并且對時延有一定要求地多媒體應用不是很理想。因此除了使用丟包作為擁塞通知方式外，AQM還可以采用其它方法，ECN便是IETF建議使用地一種擁塞通知方式。
　　
　　ECN需要在IP包頭設置一個兩位（bit）的ECN域（如圖2所示），一個是ECT（ECN-Capable Transport）位，由源端設置以顯示源端節點的傳輸協議是支持ECN的；另一個是CE（ Congestion Experienced ）位，由路由器設置，以顯示是否發生了擁塞。IPv4中TOS字節的第6位被設置為ECT位，第7位被設置為CE位。IPv4中TOS字節和IPv6中的流類型字節（traffic class octet）是相對應的，它們的前六位被設置為區分服務中的（Different- iated Services）中的區分服務標記域（DS field）。后兩位保留未用，因此可用來作為ECN域。
　　
　　除了在IP頭中設置ECN域外，ECN還需要傳輸協議的支持。在TCP頭中需要設置兩個標志位：ECN-Echo和CWR（Congestion Window Red- UCed）。ECN-Echo是接受端用來通知源端收到一個CE包；CWR是源端用來通知接受端擁塞窗口已減小。
　　
　　在TCP連接建立階段，源端和目的端TCP交換有關它們是否愿意以及是否支持ECN的信息。然后源端設置IP頭中的ECT位以向網絡顯示其支持ECN，因而，假如路由器需要的話，可以標記IP頭中的CE位作為擁塞通知的方式。下面具體闡述ECN的工作方式。
　　
　　在TCP連接建立階段，若源端支持并愿使用ECN,則其可在SYN包的TCP頭中設置ECN-Echo和CWR標志位。假如源端支持并愿使用ECN，則其可在SYN-ACK包中設置ECN-Echo標志，但不設置CWR標志。這樣當前的TCP便是支持使用ECN的。
　　　

　　圖2 ECN工作原理
　　
　　對路由器來說，假如其隊列位滿，并且其要對源端發出擁塞通知，那么路由器應該首先檢查IP包頭的ECT位是否已經設置，如是則應該設置CE位而不是以丟包作為對源端的通知信息。接著，當目的端接受到了CE包時，就會設置確認包TCP頭的ECN-Echo標志，并且為了防止確認包的丟失，目的端必須在接下來一系列的確認包中設置ECN-Echo標志。假如源端收到了ECN -Echo的確認包，那么也就知道了在發往目的端的路徑中發生了擁塞，因而需要將擁塞窗口減半并且減小慢啟動閾值，同時在接下來要發送的包中設置CWR標志，以通知目的端擁塞窗口已減小，假如目的端接受到了CWR包，就停止在接下來的確認包中設置ECN-Echo標志。
　　
　　假如路由器收到了CE包，則CE位保持不變，包的傳輸還和往常一樣。若發生了嚴重擁塞，隊列滿了，那么路由器別無選擇就只好丟包了。在現在的"延遲確認"（delayed-ACK）TCP應用中，目的端收到兩個包時發送一個確認，那么只要接收到的包中有一個CE包，確認包中的ECN-Echo標志就要設置。
　　
　　另外，假如在一個RTT內，源端同時收到ECN和丟包傳達的擁塞指示，則只對其中之一作出擁塞反應。假如擁塞反應已經開始，則必須等到所有正在傳送的數據都被確認后才能開始新的擁塞反應。
　　
　　3.4 RED和ECN地結合
　　
　　將RED和ECN結合起來，假如擁塞是在隊列滿之前檢測到的，那么除了用丟包作為擁塞通知外，對支持ECN的源端和目的端，還可以采在IP包頭設置CE位的方法。這樣就避免了不必要的丟包，非凡是對短的TCP連接和對時延敏感的TCP連接而言；另外也避免了不必要的TCP超時重傳。在下面的內容中，我們統一將上述兩種方法稱為"標記"（mark）。
　　
　　3.5 RED的優點和存在地問題
　　
　　RED在平均隊長超過了最大閾值后就丟包，而不是采用諸如設置CE位之類的標記包的方法，從而有效地控制了平均隊長，限制了平均時延地大小。在發生擁塞時，RED標記某個流的數據包的概率基本上和該流在路由器中得的帶寬成比例。這是因為發送速度更快的流，其供隨機標記的包也更多。從而消除了對突發流的偏見。RED標記包的概率依靠于擁塞水平，并且均勻地間隔丟包，避免了由于連續丟包導致地全局同步現象。總而言之，RED是IETF推薦的一種基于路由器的有效的擁塞避免機制，其和傳輸協議的合作能有效地控制網絡上發生的擁塞。
　　
　　盡管和"去尾"算法相比，RED是一種更為有效的擁塞控制機制，但其仍然有許多問題：
　　
　　（1）參數設置問題：RED工作性能的優劣很大長度上是由其預先設置的參數w_Q、min_th和max_th決定的。一組RED參數也許是給定業務吞吐量的最優化參數，但對于連續丟包、延遲等就未必是最優參數了。因此如何權衡它們（吞吐量、延遲等）之間的關系，從而找到一組最優的參數仍然是有待進一步研究的問題。另外，RED參數的微小的變化會給總體性能帶來很大的影響。一組RED參數也許在特定的業務環境下表現非常好，但由于Internet 是動態變化的，當流的數量及負荷的改變導致業務環境的變化時，則該組RED參數也會就會給擁塞治理帶來非常不利的影響。
　　
　　（2）不能有效估計擁塞的嚴重性：
　　　

　　圖3 一個RED隊列治理的例子
　　

　　圖4 理想的隊列治理算法工作情況
　　
　　基于"去尾"機制的TCP擁塞控制的一個很大問題就是從路由器丟包開始，到源端檢測到丟包，需相當長時間。在這段時間里，源端繼續以原速或更高的速度發送數據，從而導致更多的包被丟棄。RED通過檢測早期的擁塞從而減輕了這個問題。但RED必須配置足夠的緩沖區來容納從檢測到擁塞到瓶頸鏈路負荷開始下降這段時間到達的數據包。RED還要確保送出的擁塞通知信息的速度充分降低了源端的發送速度而不是降低了鏈路利用率。但當有大量的活躍的TCP（active TCP connections）連接時，總的流量往往突發性非常高，隊長的增減非常迅速，而RED還沒有來得及作出很好的行動。圖3顯示了在這種情況下RED是如何工作的。在從t=1開始發生擁塞，直到t=7負荷才小于鏈路容量，在這之間由于總的流量的突發性，就會有大量包被丟棄或被ECN標記，從而降低了鏈路使用率。圖4顯示了理想的隊列治理算法是如何工作的，其傳遞擁塞指示的速度剛好使得總的源端的發送速度等于或略小于瓶頸帶寬。
　　
　　要解決這個問題，RED不僅需要正確的參數配置，還需要足夠大的緩沖區，比如緩沖區是帶寬延遲積的兩倍。但假如帶寬延遲積很大，又會大大增加端到端的延遲。而且對那些已經在使用的，存儲器不是很大的路由器也無法用此方法解決。
　　
　　（3）和"去尾"算法相比，RED消除了對突發流的偏見，但它并不是通過降低突發流的丟包率來實現的，而是通過增加非突發流的丟包率來消除這種偏見的。
　　
　　（4）由于權重w_Q很小，因此平均隊長的變化很小。當負荷很重時，平均隊長總是在max_th四周緩慢地振動，從而會導致長時的連續標記包（avg_Q>max_th）或者長時連續隨機地標記包（avg_Q< max_th），產生全局同步現象。也由于此原因，盡管RED減小了平均時延，但卻增加了延遲抖動。
　　
　　（5）公平性問題：我們知道，不同的RTT、擁塞窗口的大小、包的大小、目標速度以及TCP/UDP的相互作用都會影響TCP流對帶寬的享用。由于Internet上數據流是異質的，而RED標記包的概率是和該流使用的帶寬成比例的，這就會帶來不公平的帶寬使用。例如兩個TCP流競爭帶寬，一個使用小窗口，另一個使用大窗口，發生擁塞時，RED就會使得小窗口的源端陷入多重超時。另外，由于UDP之類的流沒有擁塞控制機制，其在和TCP-friendly流競爭時會獲得更多的帶寬，有可能使后者陷入"饑餓"。
　　
　　由于RED存在著諸多問題，導致了其它AQM算法的產生。這些AQM算法主要有：SRED、FRED、ARED和BLUE等，由于篇幅的原因，我們對這幾種算法的原理和性能進行具體分析。

上一篇：在CISCO路由器上配置NAT功能(下)

下一篇：在CISCO路由器上配置NAT功能(上)