計(jì)算機(jī)網(wǎng)絡(luò)擁塞控制算法研究

王榮平

摘 要：為了避免網(wǎng)絡(luò)擁塞Internet主要依賴TCP端到端擁塞控制，互聯(lián)網(wǎng)的穩(wěn)定運(yùn)行有一部分要?dú)w功于以TCP為代表的端到端擁塞控制機(jī)制，這個(gè)機(jī)制起了很大的作用。但是由于互聯(lián)網(wǎng)上的應(yīng)用和用戶的增多，互聯(lián)網(wǎng)規(guī)模的爆炸，這個(gè)機(jī)制已經(jīng)不能全面的滿足網(wǎng)絡(luò)中各種復(fù)雜應(yīng)用的需求，擁塞已經(jīng)成為迫在眉睫的問題。 在本文中，當(dāng)前的TCP/IP網(wǎng)絡(luò)的擁塞控制兩個(gè)層，并以此為基礎(chǔ)針對(duì)網(wǎng)絡(luò)的實(shí)際應(yīng)用需求做了深入研究。

關(guān)鍵詞：擁塞控制；TCP/IP網(wǎng)絡(luò)；PID；控制主動(dòng)隊(duì)列管理

計(jì)算機(jī)網(wǎng)絡(luò)已有幾十年的歷史，但無論是網(wǎng)絡(luò)技術(shù)發(fā)展迅速，還是應(yīng)用范圍與影響深度，變化最快的階段還是面向大眾的最近十年。計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展歷史表明：用戶需求是推動(dòng)網(wǎng)絡(luò)技術(shù)發(fā)展的最根本原動(dòng)力。

在九十年代初期，用戶抱怨接入速度過慢；九十年代中期，主干網(wǎng)傳輸速度受到了質(zhì)疑；九十年代后期，用戶對(duì)網(wǎng)絡(luò)多媒體服務(wù)和服務(wù)質(zhì)量要求日趨強(qiáng)烈。而擁塞控制技術(shù)是其他技術(shù)發(fā)展的基礎(chǔ)，所以研究擁塞控制技術(shù)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)發(fā)展有極為深遠(yuǎn)的意義。

1 網(wǎng)絡(luò)擁塞的概念及產(chǎn)生原因

由于網(wǎng)絡(luò)中有很多的數(shù)據(jù)包而導(dǎo)致性能下降，這種現(xiàn)象稱為擁塞。關(guān)于擁塞現(xiàn)象，可用圖1來闡述。當(dāng)有較小的網(wǎng)絡(luò)覆蓋時(shí)，隨著負(fù)載的增長(zhǎng)而增長(zhǎng)的吞吐量，響應(yīng)時(shí)間更加緩慢。

2 網(wǎng)絡(luò)擁塞控制算法及存在問題

擁塞控制算法“擁塞避免”了這兩種不同的機(jī)制“擁塞控制”。擁塞控制用于從網(wǎng)絡(luò)擁塞狀態(tài)中恢復(fù)，擁塞機(jī)制，因此，“恢復(fù)”的機(jī)制；其目標(biāo)是避免網(wǎng)絡(luò)擁塞避免進(jìn)入停滯狀態(tài)在低潛伏時(shí)間，在網(wǎng)絡(luò)運(yùn)行，高輸入輸出量的狀態(tài)下，因此擁塞避免是“預(yù)防”機(jī)制。根據(jù)產(chǎn)生網(wǎng)絡(luò)擁塞的原因可知，雖然源于資源短缺而產(chǎn)生的擁塞，但單方面的增加資源有時(shí)只能加重?fù)砣潭炔⒉荒芙鉀Q擁塞的發(fā)生。比如說，有時(shí)為了增大報(bào)文通過網(wǎng)關(guān)的延遲而增加網(wǎng)關(guān)的緩存，在數(shù)據(jù)包轉(zhuǎn)發(fā)完成一條長(zhǎng)時(shí)間排隊(duì)已經(jīng)超時(shí)，但是源端卻認(rèn)為這些數(shù)據(jù)包已經(jīng)被丟棄，于是開始重新傳輸，但這些仍然被傳輸?shù)木W(wǎng)絡(luò)分組，因此一個(gè)網(wǎng)絡(luò)資源浪費(fèi)導(dǎo)致堵塞。

3 TCP/IP擁塞控制結(jié)構(gòu)分類

在擁塞閉環(huán)的控制中，源端調(diào)節(jié)發(fā)送速率是通過反饋信號(hào)來完成的，因此擁塞控制中必不可少的一個(gè)環(huán)節(jié)就是反饋環(huán)節(jié)。一般有以下兩種反饋方式：隱式反饋和顯式反饋。在隱式反饋，終端系統(tǒng)負(fù)責(zé)引進(jìn)和傳輸狀態(tài)的監(jiān)測(cè)數(shù)據(jù)，并從此處推測(cè)網(wǎng)絡(luò)擁塞的狀態(tài)，進(jìn)而來調(diào)節(jié)發(fā)送的速率。但終端的所有功能之后限制或難以準(zhǔn)確地推斷出在各種有限信息的網(wǎng)絡(luò)的負(fù)荷狀況。信息或標(biāo)記分組丟失使用作為反饋信號(hào)一般是指在隱式反饋。

對(duì)于現(xiàn)有的擁塞策略，根據(jù)該層級(jí)和網(wǎng)絡(luò)的網(wǎng)絡(luò)模型實(shí)現(xiàn)的位置，基于通信子網(wǎng)的擁塞控制策略和TCP/IP網(wǎng)絡(luò)擁塞策略。一開始主要集中在TCP的擁塞控制上來研究端主機(jī)擁塞控制。擁塞控制算法的策略，這里面包括數(shù)據(jù)包調(diào)整策略和隊(duì)列管理算法策咯，這些是基于通訊子網(wǎng)的，后者是更為主要研究方向。通過數(shù)據(jù)流如何排隊(duì)來決定哪些包可以傳輸，以此來來分配帶寬，就是數(shù)據(jù)包調(diào)度策略。

根據(jù)隊(duì)列長(zhǎng)度變化情況來選取路由器的主動(dòng)隊(duì)列管理策略。從網(wǎng)絡(luò)狀態(tài)來看，根據(jù)控制算法調(diào)整傳輸速率，因此路由器隊(duì)列緩存中的隊(duì)列長(zhǎng)度才得到控制。如圖2和3所示。

由此可見，基于通信子網(wǎng)的擁塞控制策略和端主機(jī)的擁塞控制策略是相互影響相互作用相輔相成的。反饋信號(hào)從發(fā)送隊(duì)列管理策略需要根據(jù)主機(jī)策略的需要來調(diào)整利率；隊(duì)列管理可以通過變化來影響端主機(jī)的發(fā)送速率還可以維持合理的隊(duì)列長(zhǎng)度變化。兩者一起可以實(shí)現(xiàn)一個(gè)完整的網(wǎng)絡(luò)擁塞控制。

4 控制算法比較

4.1 TCP控制算法比較

最初的NSFNET程序規(guī)范TCP協(xié)議，這是RFC793，其實(shí)這也是較為完整齊全并且也是最早的TCP規(guī)范。在設(shè)計(jì)之初，他被給予了很高的TCP協(xié)議的使命，更需要成為這些網(wǎng)絡(luò)互聯(lián)系統(tǒng)中的最可靠性傳輸協(xié)議。

互聯(lián)網(wǎng)絡(luò)中的可靠傳輸起碼包括這兩方面：第一個(gè)是正確的數(shù)據(jù)，這是由于前的傳輸介質(zhì)的傳輸質(zhì)量差，所以需要校驗(yàn)和計(jì)算，在傳輸層和下面實(shí)現(xiàn)的協(xié)議層；第二個(gè)是完整，對(duì)數(shù)據(jù)進(jìn)行排序，此功能是必需的TCP進(jìn)行復(fù)雜的操作來完成，但基本上是建立TCP窗口控制，擁塞控制實(shí)際上是在Internet上使用的基礎(chǔ)上，TCP擁塞控制網(wǎng)絡(luò)擁塞控制一直是研究的一個(gè)重點(diǎn)，因?yàn)?5%的互聯(lián)網(wǎng)使用對(duì)數(shù)據(jù)流的TCP協(xié)議。

4.2 IP控制算法比較

TCP基于窗口的擁塞控制機(jī)制的因特網(wǎng)的魯棒性方面發(fā)揮了關(guān)鍵作用。然而，隨著迅猛發(fā)展的Internet本身，它越來越龐大的規(guī)模，日益復(fù)雜的結(jié)構(gòu)，研究人員正在慢慢地認(rèn)識(shí)到，僅僅依靠端的TCP擁塞控制是不夠的，互聯(lián)網(wǎng)絡(luò)也應(yīng)該參加控制資源的工作。以影響TCP擁塞控制的動(dòng)態(tài)性能更為了實(shí)現(xiàn)IP層擁塞控制的目的。為了實(shí)現(xiàn)擁塞控制，出現(xiàn)了一系列的調(diào)度和隊(duì)列管理算法。

4.3 兩大類算法比較

圖4是一個(gè)典型的互聯(lián)網(wǎng)實(shí)例，其中IP控制的Hop-by-Hop類型和TCP控制的End-and-End類型為典型實(shí)例。基于以上的分析和討論，我們可以看到，本質(zhì)上是擁塞控制方法的來源在TCP的擁塞控制的基礎(chǔ)上，最終實(shí)現(xiàn)系統(tǒng)操作。

顯然，這種擁塞控制方法在網(wǎng)絡(luò)擁塞之間有相當(dāng)大的延遲感知擁塞控制后實(shí)施行動(dòng)，在少量的數(shù)據(jù)傳輸情況下，可以利用該數(shù)據(jù)傳送發(fā)生之后的傳播反饋信息到達(dá)發(fā)送源。IP網(wǎng)絡(luò)擁塞控制的實(shí)現(xiàn)，它可以感知到網(wǎng)絡(luò)擁塞的發(fā)生。能及時(shí)的采取行動(dòng)來加以控制。

5 TCP/IP擁塞控制算法存在的問題

TCP/IP擁塞控制機(jī)制在網(wǎng)絡(luò)中發(fā)揮了不可或缺的作用，但TCP/IP擁塞控制算法本身有不能忽視的問題：

從擁塞的發(fā)生到端系統(tǒng)采取控制之間有顯著的延時(shí)控制，由于對(duì)端系統(tǒng)缺乏一些了解，對(duì)動(dòng)態(tài)數(shù)據(jù)傳輸過程也缺乏認(rèn)識(shí)，因此無法預(yù)測(cè)到具體使用網(wǎng)絡(luò)資源的情況，只能將數(shù)據(jù)發(fā)送到控制網(wǎng)絡(luò)流量，減少網(wǎng)絡(luò)負(fù)載，從而通過減少緩解網(wǎng)絡(luò)擁塞。ACK Congestion的現(xiàn)象：ACK自計(jì)時(shí)技術(shù)往往會(huì)失效在非對(duì)稱網(wǎng)中，這樣ACK的傳輸時(shí)間就是ACK到達(dá)源端的間隔，但是由于ACK遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)包，因此會(huì)導(dǎo)致源端將數(shù)據(jù)包發(fā)送到網(wǎng)絡(luò)并超過了路由器難以承受的速度。

6 TCP/IP擁塞控制算法的改進(jìn)

由于收到重復(fù)的ACK可能會(huì)導(dǎo)致錯(cuò)誤的系統(tǒng)問題，根據(jù)網(wǎng)絡(luò)負(fù)載、吞吐量和延遲的關(guān)系，把Rtt的變化和三個(gè)重復(fù)的ACK共同控制慢啟動(dòng)的閾值和擁塞窗口的大小。

新的往返延遲會(huì)影響之后舊的RTT，這里可引入一個(gè)控制因素P。 當(dāng)新的RTT#舊的RTT時(shí)，P=0；當(dāng)新的RTT>舊的RTT時(shí)，P=1；當(dāng)收到3個(gè)重復(fù)的ACK時(shí)候控制慢啟動(dòng)閾值以及擁塞窗口大小的算法。這個(gè)算法中的P值為0或者1，和三個(gè)重復(fù)的ACK共同控制慢啟動(dòng)閾值和擁塞窗口的大小，使系統(tǒng)能更加準(zhǔn)確地判斷數(shù)據(jù)包有沒有丟失，只有增加延遲時(shí)間也收到3三個(gè)重復(fù)的ACK時(shí)，能減少慢啟動(dòng)閾值和擁塞窗口為之前的一半，提高資源的利用率。

7 結(jié)論

本文闡述了一些最新的工作，特別是在網(wǎng)絡(luò)擁塞控制方面的研究，擁塞控制的原理，揭示了現(xiàn)在所面臨的擁塞控制問題，進(jìn)行了一些簡(jiǎn)單的總結(jié)和鏈路的算法有兩個(gè)來源。

參考文獻(xiàn)：

[1] 羅萬明，林闖，閻寶平.TCP擁塞控制研究.計(jì)算機(jī)學(xué)報(bào)，2001，24（1）：1-18.

[2] 鄧亞平，葉凌偉，陳雁.TCP/IP擁塞控制算法的改進(jìn).計(jì)算機(jī)科學(xué)，2001：110-113.

[3] 包俊杰，王剛，李波.TCP擁塞控制綜述.重慶教育學(xué)院報(bào)，2003，11.

[4] 謝希仁.計(jì)算機(jī)網(wǎng)絡(luò)（第三版）.大連理工大學(xué)出版社，2000.