今日頭條
官方微信
官方抖音
案例頻道引言
在因特網上，當一個子網或者其中的一部分出現太多分組時，網絡的性能開始下降，諸如網絡延時加大、丟包率上升、吞吐量下降等，這種情況即稱為擁塞（congestion）。導致擁塞出現的原因通常是當前的負載（臨時性地）超過了（網絡中的某一部分）資源的處理能力，或者說用戶提供給網絡的負載大于網絡資源的容量和處理能力，如網絡相對于負載需求表現為節點存儲空間不足、鏈路帶寬不足、處理器處理速度慢，以及系統各部分性能不匹配等等，從而導致網絡上的包時延增加，丟包率上升，吞吐量下降，直接使服務質量下降。在處理網絡的擁塞問題時一般采用兩種方法：一是采取措施預防網絡擁塞，也就是采取流量控制技術；二是采取措施減少已擁塞時的擁塞程度，即減少擁塞時間以及防止擁塞擴散，直至擁塞的消失，也就是采取擁塞控制技術。
擁塞控制的任務是確保子網能夠處理承載所到達的流量，這是全局性的問題，涉及各方面的行為，包括所有的主機、路由器及內部的存儲轉發過程等；流量控制只與特定的發送方和接收方之間的點到點流量有關，它的做法是接收方向發送方提供某種直接的反饋以通告發方另一端的情況，使發方動態調整發送速率，以確保一個快速的發送方不會持續地以超過接收方能力的速率傳輸數據。流量控制和擁塞控制之間的關系是：有些擁塞控制算法在網絡出現擁塞時，通過往各個源端發送消息來通知它們減緩發送數據的速度，可見流量控制只是實現后者的一種技術實現途徑。
1 擁塞控制的通用原則
在計算機網絡這樣復雜的系統中可以用控制論的角度來看待擁塞控制的解決方案：開環的和閉環的。開環的解決方案試圖用良好的設計來解決問題，其本質是從一開始就保證問題不會發生，手段包括：確定何時接受新的流量、確定何時丟棄分組及丟棄那些分組，以及在網絡的不同點上執行調度策略，這些手段在作出決定的時候不考慮當前的網絡狀態；閉環的解決方案則恰恰建立在反饋環路的基礎上，這種方法可以分為三個部分，即監視系統檢測到何時何地發生了擁塞，將該信息傳遞到能夠采取行動的地方，調整系統的運行以改正問題。監視子網的擁塞狀況時可以采用多種度量標準，包括因缺少緩存而丟包的百分比、平均隊列長度、平均分組延遲等；閉環方案的第二部分可以有多種實現方法，一種方法是檢測到擁塞的路由器給流量源發送一個分組通告以擁塞的發生，另外也可以在每個分組中保留一位或一個域用以標志擁塞。為了使收到擁塞信息的主機能采取適當的行動，必須謹慎選擇地時間尺度，選取一個合理的平均值。
當前存在很多擁塞控制算法，總體可以分為開環算法和閉環算法兩大類。開環算法中一類在源端采取行動，另一類在目標端采取行動；閉環算法分為顯式反饋和隱式反饋，其中顯式反饋從擁塞點向源端發送分組以警示源端，隱式反饋中源端利用本地觀察到的現象如分組往返時間來推斷擁塞的發生。目前在Internet上實際使用的擁塞控制基本上是建立在TCP層的窗口控制基礎之上的，即基于窗口的端到端的閉環控制方式, IP層的擁塞控制主要在網絡中間節點如路由器上及鏈路上實施資源控制，IP層所起的作用相對較小。
2 TCP擁塞控制機制
TCP的擁塞控制采用的是基于窗口的端到端的閉環控制方式。目的節點正確地接收到包后將向信源發出確認（ACK）信息。每個信源有一個大小可變的窗口，使用窗口大小來確定還沒有收到確認信息的包的數量。當窗口已滿，信源在發送一個新包前必須等待一個確認信息。TCP算法有兩個重要特征：一個是“自定時”特征，當網絡出現擁塞且確認信息出現延遲時自動放慢信源的發送速率；另一個是使用窗口大小來控制信源速率，大約每個往返時間發送一個窗口的數據包。TCP擁塞控制由慢啟動（slow start）、擁塞避免（congestion avoidance）、快速重傳（fast retransmit）和快速恢復（fast recovery）四個核心部分組成。TCP使用的是加式增加積式減少（AIMD）的基于窗口的端到端的擁塞控制機制，即如果一個數據包丟失，發送窗口就要減半；否則就簡單的增加一個數據包的發送量。大量的實踐證明，這種擁塞控制機制對Internet上大批量文件傳輸等盡力型（best-effect）服務具有較好的適應性。
2.1 TCP Tahoe
TCP Tahoe 算法主要分為兩個階段：慢啟動和擁塞避免，在TCP建立連接時，為發送方增加一個擁塞窗口（cwnd）用以控制發送包的數量,并設置一個慢啟動閾值 （ssthresh）用以判定從慢啟動狀態切換到擁塞避免狀態。一開始，擁塞窗口設置為1，發方發送一個報文段，并啟動定時器，在超時之前收到一個收方應答響應ACK，則cwnd相應增加一個報文段大小變成2，以此類推cwnd按照1,2,4,8……的指數規律增長。如果出現響應超時或連續收到3個以上的重復ACK，則停止繼續增加cwnd，將ssthresh設為當前cwnd的一半（最小為2），如果是超時的情況則將cwnd重新置為1，否則cwnd不變。算法中比較cwnd與ssthresh，當cwnd比ssthresh大時將進入擁塞避免階段，即每收到相應ACK時對cwnd只按照線性規律增加1/cwnd，直到cwnd過大，發包數量相對網絡當前承載能力過多，重新導致超時或重復ACK。當cwnd不大于ssthresh時，則進入慢啟動狀態。
2.2 TCP Reno
Reno 算法對Tahoe算法作了改進，增加了快速重傳/快速恢復機制，即在接連收到3個重復ACK時就斷定丟包，進入快速重傳階段，而無需等待定時器超時，接下來執行的是擁塞避免算法而非慢啟動，這就是快速恢復。當收到第3個重復的ACK時，將ssthresh設置為當前擁塞窗口cwnd的一半，重傳丟失的報文段。然后再改變cwnd的當前值，將其設置為ssthresh加上3倍的報文段大小，此后每收到另一個重復的ACK，就將cwnd增加1個報文段大小并發送1個分組（如果新cwnd允許發送）。當下一個確認新數據的ACK到達時，設置cwnd為ssthresh。這個ACK是進行重傳后的一個往返時間內對丟失報文段重傳的確認，也是對丟失的分組和收到的第1個重復的ACK之間的所有中間報文段的確認。這一步采用的是擁塞避免，因為當分組丟失時，將當前的速率減半而不是置為慢啟動初值。
2.3 TCP Vegas
Vegas對Reno進行了三項改進：首先采用新的重傳觸發機制,即只要收到一個重復的ACK就斷定超時，以便及時檢測到擁塞；而在慢啟動階段則采用了更加謹慎的方式來增加cwnd,以減少不必要的分組丟失；改進“擁塞避免”階段的窗口調整算法，通過觀察以前的TCP 連接中RTT值改變情況來控制擁塞窗口cwnd , 當RTT變大時就認為發生擁塞, 開始減小cwnd，如果RTT變小,就增加cwnd，解除擁塞，理想情況下cwnd就會穩定在一個合適的值上。 這樣使擁塞機制的觸發不再依靠包的具體傳輸時延，而只與RTT的改變有關。
3 IP擁塞控制機制
TCP擁塞控制機制本質上是端到端的控制機制，它默認為IP層對擁塞的發生和擁塞的控制不進行任何支持。當前隨著Internet業務的迅猛發展，僅依靠單一的端到端的擁塞控制機制不可能有效地解決擁塞問題，另外期望所有用戶在Internet應用中都遵守這種端到端的擁塞控制也是不現實的，這要求網絡本身也必須參與對資源的管理與控制。基于此，提出了在路由器中采用排隊算法和數據包丟棄的策略，即IP擁塞控制機制。
3.1 先入先出（FIFO）
FIFO 即“先到先服務”，意指先到達路由器的數據包就先被傳輸，如果緩存已滿則丟包。優先級排隊對基本FIFO排隊進行了簡單改進，它為每個數據包分配一個優先級標志，在路由器按照不同優先級進行多個FIFO排隊，非空的最高優先級隊列優先發送，同一優先級隊列內仍然是FIFO方式。由于高優先級隊列會“搶占”所有其它的隊列，因此用戶不能用不受控的方式為自己的數據包指定高的優先級。一些重要的報文如路由更新包往往采用優先級排隊的方式，其優先級由IP包頭的TOS域定義并由一個特殊的隊列保存, 這其實是區分服務思想的一種實現。
3.2 隨機早檢測算法(RED)
RED算法在路由器監控隊列長度, 一旦發現擁塞迫近, 就通知源端調整擁塞窗口。 它也是通過丟包的方式使源端發現超時或重復應答，隱式通知源端擁塞情況。RED算法包含兩部分：如何監控隊列長度和何時丟棄數據包。首先, RED使用類似TCP計算超時時使用的權值Weight來計算平均排隊長度Qe=(1-Weight)×Qe+Weight×SampleQe
其中，0< Weight< 1, SampleQe是采樣測量時的排隊隊長。使用平均隊長比使用瞬時值更能精確“捕捉”擁塞情況。RED丟棄數據流中包的概率與這個流在路由器中所獲得的帶寬成比例,因為一個發送數量相對較大的數據流可供隨機丟棄的數據包的數量也相對較多。因此在RED算法中需要考慮公平性。
3.3 顯式擁塞指示（ECN）
ECN算法在源端數據包中嵌入ECN, 由路由器根據網絡情況設置CE (Congestion Experienced) 比特位，源端從網絡中接收反饋回來的已被CE置位的數據包, 再將隨后發出的數據包標記為“可丟棄”的數據包。改進算法NewECN可通過調整擁塞窗口cwnd大小, 糾正了有長時間RTT的TCP 連接的偏差, 改進了共享瓶頸處帶寬的公平性。
3.4 公平排隊算法(FQ)
在FQ算法中, 路由器的每個輸出鏈路(outputline)都對應一個排隊隊列，對它們按“輪詢”( round robin)方式處理。當有某條輸出鏈路空閑時, 路由器就順次掃描所有隊列, 將每隊第一個包發出。 當某個流的數據包到達過快時, 其隊列就會很快占滿, 屬于這個流的新到的包就會被丟棄。 采用這種方式, 每個數據流就不可能犧牲其它數據流而額外占用資源。FQ算法并沒有告知源端路由器狀態的機制, 也就是說, FQ仍然要依賴于端到端的擁塞控制機制。它只是將數據流分隔, 使不遵守擁塞控制機制的數據流不至于影響其它流。所以它在沒有犧牲統計復用的情況下提供了公平性, 與端到端的擁塞控制機制也可以較好地協同。由于數據包是變長的, 所以為了在輸出鏈路上公平分配帶寬, 必須考慮包的大小。
3.5 加權公平排隊算法 （WFQ）
它是FQ的改進算法。WFQ對每個流即每個排隊分配一個權值。這個權值決定了路由器每次轉發該隊列的比特數量, 從而控制數據流得到的帶寬。將所有權值看成1, 那么FQ也是一種特殊的WFQ。權值的分配往往對應不同優先級的數據流,例如用IP包頭中TOS域指定流的優先級, 排隊時再按優先級分配權值。這也是區分服務的思想。權值可以由路由器自己決定, 也可以由源端通過某種信令通知路由器來決定。 總之,WFQ 根據不同數據流應用的不同帶寬要求, 對每個排隊隊列采用加權方法分配緩存資源, 從而增加了FQ對不同應用的適應性。
4 TCP/IP擁塞控制算法性能分析
按照擁塞時包丟棄的方式，可以將擁塞控制策略分成3種類型：一是混合式, 即在路由器中不管是哪種數據流, 其優先級如何, 均共同排隊處理, 共享同一路由器資源, 如FIFO，RED等；二是分離式,各數據流在路由器中單獨排隊,如FQ；三是基于部分緩存共享方式，根據緩存大小設置一個閾值來控制包丟失率。 當緩存達到或超過給定閾值時,只有高優先級數據包才能進行緩存, 低優先級數據包則被丟棄，當緩存滿時, 高優先級數據包也被丟棄。
FIFO的主要問題是無法區分不同的數據流,它對擁塞控制不起作用，主要由TCP進行擁塞的檢測和響應。RED 設計的出發點是怎樣與TCP擁塞控制有效配合。對面向連接的TCP數據流來說, RED有可能避免丟棄屬于同一連接的連續數據包, 從而提高連接的吞吐量。在路由器上運行RED可以更精確地管理隊長，其最優隊長取決于各種數據流的特性。ECN不依賴于重傳超時和粗粒度的TCP定時, 對有一定時延要求的應用效果較好。TCP在源端進行擁塞控制, 傳統的FIFO排隊不提供約束所有數據源遵守擁塞控制的機制, 這就有可能讓行為不良的數據流強占大量帶寬。針對此提出了FQ算法即公平排隊法，可以解決這個問題。
5 結束語
以上對當前Internet上實行的各種基于TCP/IP的擁塞和流量控制算法原理進行了總體概述，分析、比較了這些算法的基本性能的優劣。TCP協議通過窗口機制，以丟包率或排隊時延作為擁塞的度量，進行擁塞控制；在整個因特網上，通過分布式的對單個信源傳輸速率進行調整，進行流量控制；而流量控制是擁塞控制的一種有效手段，目的是避免鏈路容量過載，保證服務質量，并使網絡資源得到充分的利用。擁塞/流量控制算法的自相似問題、穩定性、效率問題以及公平性問題都是有待進一步研究和改進的問題，另外，如何在IP層實現擁塞控制以更有效地解決擁塞問題及多點廣播中的擁塞控制等是目前研究的熱點。
參考文獻
北京市公安局海淀分局備案號：11010802023656號