網(wǎng)絡(luò)擁塞算法總結(jié)

網(wǎng)絡(luò)擁塞控制的目的不是要完全避免擁塞的發(fā)生，而是通過擁塞控制，提高網(wǎng)絡(luò)的性能及數(shù)據(jù)處理能力，保障網(wǎng)絡(luò)的穩(wěn)定和持續(xù)運(yùn)行，并且保證數(shù)據(jù)傳輸?shù)墓叫?。我們知道，網(wǎng)絡(luò)擁塞的根本原因在于端系統(tǒng)發(fā)出的數(shù)據(jù)超出了網(wǎng)絡(luò)的處理能力，而擁塞控制算法的基本思想則是解決這一問題，通常的方法就是TCP擁塞控制算法和IP擁塞控制算法。1.TCP擁塞控制算法通常，TCP的擁塞控制分為4個階段，即慢啟動（slowstart）階段、擁塞避免（congestionavoidance）階段、快速重傳（fastretransmit）階段、快速恢復(fù)（fastrecovery）階段；可參考《TCP/IP詳解卷I》的相關(guān)內(nèi)容。在實際的實現(xiàn)過程中，TCP對擁塞的控制都是通過改變一些參數(shù)來實現(xiàn)的，如擁塞窗口（cwnd）、通告窗口（awin）、發(fā)送窗口（win）、慢啟動閾值（ssthresh）、往返時延（RTT）、超時重傳計數(shù)器（RTO）、快速重傳閾值等。a） TCP擁塞控制算法的演進(jìn)我們知道，TCP是端到端的協(xié)議，所以，基于TCP的擁塞控制也是端到端的算法，具體包括TCPTahoe算法、TCPReno算法、TCPNewReon算法、TCPSACK算法等，下面對這幾種算法進(jìn)行簡單的介紹。TCPTahoe算法該算法包括慢啟動、擁塞避免、快速重傳以及RTT估計量的修改，這是TCP擁塞控制的基礎(chǔ)，其它的算法依賴于此。TCPReno算法該算法在Tahoe的基礎(chǔ)之上增加了“快速恢復(fù)”階段，Reno算法在快速重傳后并不將cwnd減少至1MSS，而是將cwnd減半，進(jìn)入擁塞避免階段。但該算法也存在不足，當(dāng)發(fā)送端檢測擁塞后，需要重傳全部數(shù)據(jù)包（包括已經(jīng)正確傳輸?shù)臄?shù)據(jù)包）。TCPNewReno算法該算法是對Reno算法的補(bǔ)充，它通過盡量避免Reno在快速恢復(fù)階段的重傳超時，在快速恢復(fù)階段，發(fā)送方收到一個部份的ACK后，立即重傳余下的數(shù)據(jù)包，從而提高傳輸性能，目前在互聯(lián)網(wǎng)上使用最多的就是TCPNewReno算法。TCPSACK算法該算法是對Reno算法的補(bǔ)充，使用該算法，當(dāng)檢測到數(shù)據(jù)丟失后，不用重傳全部數(shù)據(jù)包，而是對數(shù)據(jù)包進(jìn)行選擇性確認(rèn)和重傳，從而減少重傳，時延，提高傳輸性能。SACK算法并不是每一個TC端都支持。b） TCP擁塞控制算法的優(yōu)缺點(diǎn)TCP擁塞控制是端到端的控制，它可以降低網(wǎng)絡(luò)交換設(shè)備的工作負(fù)擔(dān)，保持設(shè)備的穩(wěn)定性，而且其算法所涉及的設(shè)備少，非常容易實現(xiàn)，所以目前的互聯(lián)網(wǎng)大部份都是基于TCP擁塞控制來實現(xiàn)的。但它也存在一些缺點(diǎn)，如在高速網(wǎng)絡(luò)中不能有效利用帶寬（確認(rèn)機(jī)制、、重傳機(jī)制等）；與UDP相比，存在對網(wǎng)絡(luò)資源的不公平使用問題，因為當(dāng)出現(xiàn)網(wǎng)絡(luò)擁塞時，遵循擁塞控制TCP應(yīng)用得到的資源會越來越少，而沒有擁塞機(jī)制的UDP應(yīng)用會得到越來越多的資源等。2. IP擁塞控制算法TCP擁塞控制是端到端的擁塞管理，但在實際的數(shù)據(jù)傳輸中，網(wǎng)絡(luò)本身也會造成擁塞，所以需要讓網(wǎng)絡(luò)本身參與到擁塞控制中，也就是IP擁塞控制算法，通過對路由器的緩沖隊列進(jìn)行管理控制，從而提高路由器性能、擁塞管理和QoS能力。a） IP擁塞控制算法的分類IP擁塞控制的典型算法一般有先進(jìn)先出（FIFO）、隨機(jī)早期檢測（RED）、顯示擁塞指示算法（ECN）、公平排隊算法（FQ）、加權(quán)公平排隊算法（WFQ）等。先進(jìn)先出（FIFO）算法先進(jìn)先出的最大優(yōu)點(diǎn)在于實施起來簡單，其原理是第一個到達(dá)的數(shù)據(jù)包將被首先傳輸，由于路由器的緩存總是有限的，當(dāng)緩沖區(qū)滿后，隨后到達(dá)的包將被丟棄。由于FIFO總是丟棄到達(dá)隊尾的包，所以經(jīng)常和去尾（Drop-Tail）算法在概念上被淆。FIFO是一種包的調(diào)度策略，Drop-Tail是一種包的丟棄策略。由于FIFO和Drop-Tail實施起來比較簡單，因而目前去尾的先入先出是Intemet上最廣泛使用的隊列調(diào)度管理方式。隨機(jī)早期檢測（RED）算法RED算法通過監(jiān)控路由器中的數(shù)據(jù)包排隊長度，在緩存占滿之前，一旦發(fā)現(xiàn)擁塞迫近就按一定的概率丟棄進(jìn)入路由器的數(shù)據(jù)包，這樣就可以及早地通知源端減小擁塞窗口，從而減少進(jìn)入網(wǎng)絡(luò)的數(shù)據(jù)量。這意味著路由器以后不必丟棄更多的數(shù)據(jù)包，從而提高網(wǎng)絡(luò)的吞吐量。RED算法主要包含兩部分：如何監(jiān)控平均隊列長度和如何丟棄數(shù)據(jù)包。顯示擁塞指示算法（ECN）ECN由RFC2481推薦，在IPv4報頭結(jié)構(gòu)中的TOS字段中的設(shè)置ECN域，ECN在源端數(shù)據(jù)包中嵌入ECN使能發(fā)送比特位，由路由器根據(jù)網(wǎng)絡(luò)的具體情況設(shè)置CE位。發(fā)送端接收到這種置位的數(shù)據(jù)包后就認(rèn)為網(wǎng)絡(luò)發(fā)生擁塞，從而減小發(fā)送速率。詳見：/network-analyst-24396-1-1.html公平排隊（FQ）算法公平算法通過對數(shù)據(jù)流進(jìn)行分隔，讓不同的數(shù)據(jù)流互不影響，為數(shù)據(jù)流公平的分配資源。每個輸出線路都分配一個隊列，路由器按“輪詢”方式來回掃描所有隊列，并依次將每隊的第一個包發(fā)出去，當(dāng)某個流的數(shù)據(jù)到達(dá)過快且隊列占滿后，屬于該流的新到數(shù)據(jù)會被丟棄。公平排隊算法遵循以下規(guī)則：當(dāng)只有一個流時，將所有帶寬分配給該流；當(dāng)有X個流要共享帶寬時，每個流得到的帶寬為1/X。加權(quán)公平排隊（WFQ）算法加權(quán)公平排隊算法是對公平排隊算法的改進(jìn)，它對每個流分配一個權(quán)值，該值決定路由器每次發(fā)送數(shù)據(jù)的數(shù)量，從而控制數(shù)據(jù)流的帶寬分配。權(quán)值的分配跟據(jù)不同優(yōu)先級的數(shù)據(jù)流而定，如在IP報頭中的TOS字段指定的優(yōu)先級，在排隊時再按優(yōu)先級分配權(quán)值，這也是區(qū)分服務(wù)的思想。注：FQ是一種特殊的WFQ，即將所有權(quán)值看成1。b）IP擁塞控制算法的優(yōu)缺點(diǎn)IP擁塞控制在網(wǎng)絡(luò)層實現(xiàn)，可以區(qū)分不同的發(fā)送端產(chǎn)生的數(shù)據(jù)流，在路由器中通過隊列調(diào)度，接受或丟棄數(shù)據(jù)，可以達(dá)到對帶寬的公平處理，對于短期的擁塞，IP擁塞控制可以處理得比較好，但對于長期的擁塞卻無能為力。而且相應(yīng)的算法也存在不足，如RED算法會導(dǎo)致不穩(wěn)定，不適合對時延敏感的應(yīng)用，ECN算法存在兼容性問題，F(xiàn)IFO沒有考慮數(shù)據(jù)包的重要程度等。3.TCP與IP擁塞比較TCP擁塞控制實際上是一種基于源的擁塞控制方法，實現(xiàn)在端系統(tǒng)中，這種擁塞控制方法在網(wǎng)絡(luò)擁塞發(fā)生到感知到擁塞后采取控制行動之間存在著比較大的延遲；IP擁塞控制在網(wǎng)絡(luò)中實現(xiàn)，可以及時感知