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