網(wǎng)絡(luò)擁塞控制算法研究綜述

姚麗君　孔金生

摘要：在本文中，作者著重闡述了TCP擁塞控制和IP擁塞控制中的典型算法以及目前一些較有影響的擁塞控制算法，分析了當(dāng)前擁塞控制算法設(shè)計(jì)過程中存在的不足，并給出了一個(gè)有意義的研究方向。

關(guān)鍵詞：TCP擁塞控制IP擁塞控制控制理論

0引言

近二十年來，計(jì)算機(jī)網(wǎng)絡(luò)經(jīng)歷了飛速的發(fā)展，使得信息的交流變得方便和快捷，然而由于網(wǎng)絡(luò)數(shù)據(jù)流量的激增，擁塞問題隨之而產(chǎn)生，且變得越來越嚴(yán)重，己經(jīng)成為制約網(wǎng)絡(luò)發(fā)展和應(yīng)用的一個(gè)瓶頸，如何更好的預(yù)防和控制擁塞是近年來網(wǎng)絡(luò)研究的熱點(diǎn)問題之一。產(chǎn)生網(wǎng)絡(luò)擁塞的根本原因在于用戶(或叫端系統(tǒng))提供給網(wǎng)絡(luò)的負(fù)載大于網(wǎng)絡(luò)資源容量和處理能力，表現(xiàn)為數(shù)據(jù)包延時(shí)增加、丟棄概率增大、上層應(yīng)用系統(tǒng)性能下降。

1TCP擁塞控制

據(jù)統(tǒng)計(jì)，Internet上的95％的數(shù)據(jù)流使用的是TCP協(xié)議，因此TCP擁塞控制一直是網(wǎng)絡(luò)擁塞控制研究的重點(diǎn)。

1.1TCP Tahoe Tahoe是TCP的早期版本，它包括了最基本的TCP擁塞控制算法，由“慢啟動(dòng)”、“擁塞避免”和“快速重傳”三部分組成?！翱焖僦貍鳌备鶕?jù)3個(gè)重復(fù)的確認(rèn)分組來判斷分組丟失的出現(xiàn)，從而減少等待“重傳時(shí)鐘”超時(shí)的過程，提高了分組的傳輸效率。除此之外，Tahoe對(duì)往返時(shí)間的計(jì)算也作了相應(yīng)的改進(jìn)，以便更準(zhǔn)確地設(shè)定超時(shí)重傳的時(shí)間。

1.2TCP Reno Reno在Tahoe的基礎(chǔ)上增加了“快速恢復(fù)”算法來提高擁塞恢復(fù)的效率。當(dāng)發(fā)送端收到一定數(shù)量的重復(fù)ACK之后，即進(jìn)入“快速恢復(fù)”階段。源端在接收到足夠多的重復(fù)的ACK之后，用接著到來的重復(fù)ACK觸發(fā)新數(shù)據(jù)分組的發(fā)送。只有在接收到新發(fā)分組的ACK后，源端才退出“快速恢復(fù)”階段。Reno的“快速恢復(fù)”優(yōu)化了單個(gè)分組從數(shù)據(jù)窗口。

1.3TCP New-Reno New-Reno對(duì)Reno算法作了一些小改進(jìn)，以消除有多個(gè)分組從同一數(shù)據(jù)窗口丟失時(shí)對(duì)重傳定時(shí)器的等待。改進(jìn)考慮到發(fā)送端在“快速恢復(fù)”階段收到的“恢復(fù)ACK”是確認(rèn)部分而不是全部出現(xiàn)在“快速恢復(fù)”階段的分組。New-Reno直到所有在“快速恢復(fù)”階段開始時(shí)出現(xiàn)的分組都被確認(rèn)，才會(huì)退出“快速恢復(fù)”。

1.4TCP SACK Sack算法也是對(duì)Reno的改進(jìn)，當(dāng)檢測到擁塞后，不用重傳數(shù)據(jù)包丟失到檢測到丟失時(shí)發(fā)送的全部數(shù)據(jù)包，而是對(duì)這些數(shù)據(jù)包進(jìn)行有選擇的確認(rèn)和重傳，從而避免不必要的重傳，減少時(shí)延，提高網(wǎng)絡(luò)吞吐量。由于使用選擇重傳，所以在一個(gè)窗口中數(shù)據(jù)包多包丟失的情況下，Sack性能優(yōu)于New-Reno。但是Sack的主要缺點(diǎn)是要修改接收端TCP。

1.5TCP Vegas Vegas對(duì)Reno進(jìn)行了三項(xiàng)改進(jìn)：首先采用新的重傳觸發(fā)機(jī)制，即只要收到一個(gè)重復(fù)的ACK就斷定超時(shí)，以便及時(shí)檢測到擁塞；而在慢啟動(dòng)階段則采用了更加謹(jǐn)慎的方式來增加擁塞窗口cwnd，以減少不必要的分組丟失：改進(jìn)“擁塞避免”階段的窗口調(diào)整算法，通過觀察以前的TCP連接中RTT值改變情況來控制cwnd，當(dāng)RTT變大時(shí)就認(rèn)為發(fā)生擁塞，開始減小cwnd，如果RTT變小，就增加cwnd，解除擁塞，理想情況下cwnd就會(huì)穩(wěn)定在一個(gè)合適的值上。這樣使擁塞機(jī)制的觸發(fā)不再依靠包的具體傳輸時(shí)延，而只與RTT的改變有關(guān)。

2IP擁塞控制

在互聯(lián)網(wǎng)這樣的復(fù)雜系統(tǒng)中，不能指望所有用戶在其應(yīng)用中兼容端到端的TCP擁塞控制機(jī)制，網(wǎng)絡(luò)也需要參與資源的控制工作。因此，需要采用路由器的擁塞控制方法，即IP擁塞控制。

2.1先進(jìn)先出(First ln first Out，F(xiàn)IFO)FIFO是一種最簡單的調(diào)度算法，又被稱為“先到先服務(wù)”，即第一個(gè)到達(dá)路由器的數(shù)據(jù)包首先被傳輸，接著到達(dá)的數(shù)據(jù)分組在路由器中排隊(duì)，等待輸出，如果包到達(dá)時(shí)緩存己滿，那么路由器就不得不丟棄該包。這種方法的優(yōu)點(diǎn)是實(shí)施簡單，但沒有考慮被丟棄包的重要程度。由于FIFO總是丟棄到達(dá)隊(duì)尾的包，所以又稱為“去尾”(drop tail)算法。但“去尾”和FIFO是兩個(gè)不同的概念。FIFO是一種包調(diào)度策略，決定包傳送的順序；“去尾”是一種丟棄策略，決定哪些包被丟棄。

2.2隨機(jī)早期檢測(Random Early Detection，RED)RED解決的問題主要包括：①早期探測路由器可能發(fā)生的擁塞，并通過隨機(jī)丟棄或標(biāo)記分組來通知源端采取措施避免可能發(fā)生的擁塞：②公平地處理包括突發(fā)性、持久性和間隙性的各種TCP業(yè)務(wù)流；③避免多個(gè)TCP連接由于隊(duì)列溢出而造成同步進(jìn)入“慢啟動(dòng)”狀態(tài)；④維持較小的隊(duì)列長度，在高吞吐量和低時(shí)延之間做出合理平衡。

2.3顯式擁塞指示算法(ExpIicit Congestion Notification，ECN)在ECN算法中，路由器采用RED算法管理緩沖區(qū)，當(dāng)平均隊(duì)列長度處于兩個(gè)閾值之間時(shí)，路由器按照一定概率給報(bào)文設(shè)置CE使能位，而不是簡單地丟棄該報(bào)文。當(dāng)下端路由器發(fā)生擁塞時(shí)，首先選擇有CE使能位的報(bào)文丟棄。ECN優(yōu)勢在于不需要重傳超時(shí)，有效地提高網(wǎng)絡(luò)帶寬的使用效率。

2.4公平排隊(duì)算法(Fair queuing，F(xiàn)Q)FQ算法是一種“輪詢”調(diào)度算法。在FQ算法中，路由器對(duì)每個(gè)輸出線路有一個(gè)排隊(duì)隊(duì)列，路由器按“輪詢”方式處理包。當(dāng)一條線路閑時(shí)，路由器就來回掃描所有隊(duì)列，依次將每隊(duì)第一個(gè)包發(fā)出。當(dāng)某個(gè)流的數(shù)據(jù)包到達(dá)過快時(shí)，其隊(duì)列就會(huì)很快占滿，屬于這個(gè)流的新到的包就會(huì)被丟棄。采用這種方式，每個(gè)數(shù)據(jù)流就不可能犧牲其它數(shù)據(jù)流而多占資源。

2.5加權(quán)公平排隊(duì)算(Weighted Fair queuing，WFQ)WFQ是FQ的改進(jìn)算法。對(duì)每個(gè)流(排隊(duì))分配一個(gè)權(quán)值。這個(gè)權(quán)值決定了路由器每次發(fā)往該隊(duì)列的比特?cái)?shù)量，從而控制數(shù)據(jù)流得到的帶寬。WFQ中權(quán)值可以由路由器自己決定，也可以由源端通過某種信令通知路由器來決定。總之，WFQ根據(jù)不同數(shù)據(jù)流應(yīng)用的不同帶寬要求，對(duì)每個(gè)排隊(duì)隊(duì)列采用加權(quán)方法分配緩存資源，從而增加了FQ對(duì)不同應(yīng)用的適應(yīng)性。

3TCP與IP擁塞控制比較

顯然TCP基于窗口的端到端擁塞控制，本質(zhì)上是一種基于信源的控制策略。它有明顯的不足：①在感知到擁塞到采取控制行動(dòng)之間存在著顯著的時(shí)延；②信源可能不按照網(wǎng)絡(luò)的指令操作；③某些策略中反饋需要在網(wǎng)絡(luò)中增加額外的分組?；贗P的擁塞控制策略實(shí)施在網(wǎng)絡(luò)層，不必依賴信源來均勻地分配資源，所以不存在以上那些問題?；贗P的擁塞控制策略是公平的，基于IP控制的主要問題在于增加共享資源(主要是路由器)的復(fù)雜性。事實(shí)上，很多策略的復(fù)雜性是與共享路由器的信源數(shù)成正比的，當(dāng)網(wǎng)絡(luò)的鏈路速率增加時(shí)信源數(shù)量也隨之增加。

4總結(jié)

從以上的TCP和IP擁塞控制中典型算法的分析介紹中不難看出，這些算法雖然在以往算法的基礎(chǔ)上進(jìn)行了改進(jìn)，系統(tǒng)性能有所改善，但其自身幾乎都存在著這樣或那樣的問題。其直接原因就是這些算法的設(shè)計(jì)都是針對(duì)局部的某一具體問題進(jìn)行，依靠直覺的推斷，根據(jù)經(jīng)驗(yàn)改進(jìn)算法，缺乏一套有效的系統(tǒng)的理論分析工具對(duì)算法的設(shè)計(jì)進(jìn)行指導(dǎo)?？刂评碚撟鳛橐婚T相當(dāng)成熟的系統(tǒng)理論，有相當(dāng)多的方法可以借鑒到擁塞控制中來。近來，國內(nèi)外的很多專家學(xué)者都認(rèn)識(shí)到了可以應(yīng)用控制理論的方法來解決Internet中的擁塞控制問題，并進(jìn)行了一些嘗試工作。然而，由于Internet本身是一個(gè)復(fù)雜的巨系統(tǒng)，而且其中的各種不同控制策略之間也會(huì)互相影響，使得對(duì)網(wǎng)絡(luò)穩(wěn)定性和動(dòng)態(tài)性能的分析更加困難，因而這方面的研究還不成熟，所以，如何有效的將控制理論的思想運(yùn)用于日趨復(fù)雜的Internet中，來指導(dǎo)目前單純根據(jù)經(jīng)驗(yàn)來改進(jìn)算法的不足，將是一個(gè)未來研究的熱點(diǎn)問題，也是一個(gè)難點(diǎn)問題。