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

劉曉飛

（ 安慶師范大學(xué) 計算機與信息學(xué)院，安徽 安慶 246133 ）

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

劉曉飛

（ 安慶師范大學(xué) 計算機與信息學(xué)院，安徽 安慶 246133 ）

網(wǎng)絡(luò)參數(shù)的動態(tài)變化使網(wǎng)絡(luò)擁塞變得嚴(yán)重和復(fù)雜，擁塞控制一直是個重要的研究內(nèi)容。目前主要采用以TCP為代表的端到端擁塞控制機制，然而，隨著互聯(lián)網(wǎng)上的應(yīng)用和用戶的增多，這個機制已不能滿足網(wǎng)絡(luò)中各種復(fù)雜應(yīng)用的需求，網(wǎng)絡(luò)擁塞已成為一個迫在眉睫的問題。文章探討了網(wǎng)絡(luò)擁塞出現(xiàn)的原因，分析了TCP擁塞控制的原理及四個TCP擁塞控制算法的性能，論述了TCP擁塞控制面臨的問題及相應(yīng)算法的改進(jìn)措施，提出了其進(jìn)一步的研究方向。

擁塞控制； TCP/IP網(wǎng)絡(luò)； PID； 主動隊列管理

計算機網(wǎng)絡(luò)已有幾十年的歷史，其發(fā)展歷史表明：用戶需求是推動網(wǎng)絡(luò)技術(shù)發(fā)展的原動力[1]。在90年代初期，用戶抱怨接入速度過慢；90年代中期，主干網(wǎng)傳輸速度受到了質(zhì)疑[2]；90年代后期，用戶對網(wǎng)絡(luò)多媒體服務(wù)和服務(wù)質(zhì)量要求日趨強烈，網(wǎng)絡(luò)擁塞也愈加嚴(yán)重，研究擁塞控制技術(shù)對計算機網(wǎng)絡(luò)體系結(jié)構(gòu)發(fā)展有極為深遠(yuǎn)的意義[3]。

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

由于網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)量超過帶寬，導(dǎo)致網(wǎng)絡(luò)傳輸性能下降，這種現(xiàn)象稱為擁塞[4]。如圖1所示。隨著負(fù)載的增加，吞吐量與傳輸延遲也同步增加，當(dāng)網(wǎng)絡(luò)中出現(xiàn)擁塞后，即到達(dá)涯點，吞吐量與延遲急劇增大[5]。

1.1.擁塞控制算法的作用點

我們定義擁塞控制算法的作用點為擁塞控制算法的程序?qū)嶓w所運行的物理環(huán)境和軟件協(xié)議環(huán)境，它包括物理作用點與協(xié)議作用點兩個子集。物理作用點是指擁塞控制算法實體所運行的物理主機與設(shè)備[6-7]；協(xié)議作用點是指擁塞控制算法實體在TCP/IP協(xié)議棧內(nèi)，垂直方向的位置。

1.2.網(wǎng)絡(luò)擁塞產(chǎn)生的原因

（1）存儲空間不夠。如果沒有足夠的存儲空間來存儲，數(shù)據(jù)包將被丟棄。發(fā)送端會對這些被丟棄的數(shù)據(jù)包重新傳輸，這樣一來網(wǎng)絡(luò)資源的浪費增加了網(wǎng)絡(luò)擁塞。

（2）帶寬信息通道窄。信息理論提示到，任何信道帶寬最大值就是信道容量C=Blog2(1+S/N)，所有從源率R發(fā)送的字母必須小于或等于該信道容量C。如果R>C，則在理論上不可能存在無差別傳輸，它可以在網(wǎng)絡(luò)中將形成以低速鏈路帶寬瓶頸，當(dāng)不能滿足要求時，將導(dǎo)致網(wǎng)絡(luò)擁塞[8-9]。

根據(jù)產(chǎn)生網(wǎng)絡(luò)擁塞的原因可知，雖然源于資源短缺而產(chǎn)生擁塞，但單方面的增加資源有時只能加重?fù)砣潭萚10-11]。比如說，有時為了增大報文通過網(wǎng)關(guān)的延遲而增加網(wǎng)關(guān)的緩存，在數(shù)據(jù)包轉(zhuǎn)發(fā)完成時，其已超時，但是源端卻認(rèn)為這些數(shù)據(jù)包已經(jīng)被丟棄，于是開始重新傳輸，從而加重了擁塞。

2.TCP/IP擁塞控制結(jié)構(gòu)

對于現(xiàn)有的擁塞控制機制，根據(jù)該層級和網(wǎng)絡(luò)的網(wǎng)絡(luò)模型實現(xiàn)的位置，可分為基于通信子網(wǎng)的擁塞控制策略和基于源主機的擁塞控制策略[12]（如圖2所示）。兩種類型的擁塞控制原理如圖3和4所示。

圖1 網(wǎng)絡(luò)負(fù)載與吞吐量及響應(yīng)時間的關(guān)系

圖2 TCP/IP網(wǎng)絡(luò)擁塞控制策略結(jié)構(gòu)圖

圖3 基于端主機的擁塞控制模型

圖4 主動隊列管理策略控制模型

3. 控制算法比較

3.1.TCP擁塞控制算法

最初的NSFNET程序規(guī)范的TCP協(xié)議，這是RFC793。這個規(guī)范對如何進(jìn)行主機到主機的可靠傳輸進(jìn)行了簡單描述，也介紹了一些傳輸控制協(xié)議執(zhí)行的功能，實現(xiàn)了相應(yīng)的方案和程序接口。

需要明確的是，如表1所示，互聯(lián)網(wǎng)絡(luò)中的可靠傳輸起碼包括這兩方面：第一個是正確的數(shù)據(jù)，這是由于以前的傳輸介質(zhì)的傳輸質(zhì)量較差，所以需要校驗和計算，在傳輸層和下面實現(xiàn)的協(xié)議層[13]；第二是擁塞控制實際上是在Internet上使用的TCP來實現(xiàn)的，95%的互聯(lián)網(wǎng)使用對數(shù)據(jù)流的TCP協(xié)議。

3.2.IP擁塞控制算法

TCP基于窗口的擁塞控制機制的因特網(wǎng)的魯棒性方面發(fā)揮了關(guān)鍵作用。然而，隨著迅猛發(fā)展的Internet本身，它越來越龐大的規(guī)模，日益復(fù)雜的結(jié)構(gòu)，使僅依靠端的TCP擁塞控制是不夠的，互聯(lián)網(wǎng)絡(luò)也應(yīng)該參加控制資源的工作。為了實現(xiàn)擁塞控制，出現(xiàn)了一系列的隊列管理算法[14]（如表2所示）。

表1 TCP典型擁塞算法比較

表2 IP典型擁塞算法比較

3.3.兩大類算法比較

兩類算法的比較如表3所示。

表3 擁塞控制算法的比較

圖5是一個典型的互聯(lián)網(wǎng)實例，包括IP控制的Hop-by-Hop類型和TCP控制的End-and-End類型?？梢钥闯?，本質(zhì)上，擁塞控制方法是基于TCP的。顯然，這種擁塞控制方法具有相當(dāng)大的延遲[15-16]，在感知擁塞現(xiàn)象后采取行動，在傳輸數(shù)據(jù)量小的情況下，也能夠?qū)砣畔⒎答伒皆唇Y(jié)點。

圖5 典型互聯(lián)網(wǎng)實例

4.其它擁塞控制算法

（1）基于方程的擁塞控制(equation-based congestion control)。它把發(fā)送速率作為丟失事件率的函數(shù)運算，給出可接收的最大發(fā)送速率并使用控制方程顯示得到[17]。因此該算法中的一個關(guān)鍵部分是丟失事件率的計算。

（2）TCP Westwood。TCP Westwood是一種來調(diào)整擁塞窗的TCP協(xié)議，且是由發(fā)送方采用。它的主要目的不是在少量丟包時擁塞窗口減半來提高連接吞吐量而是對擁塞窗口進(jìn)行定量的減少[18]。

用來調(diào)整擁塞窗口的偽代碼如下，收到3個冗余的ACK時：

當(dāng)發(fā)生超時事件時：

其中ssthresh就是慢啟動閾值，cwnd是擁塞窗口的大小，BWE估計帶寬連接，最小RTTmin被測量到的往返時間，SEG大小是數(shù)據(jù)包的解釋的大小[19-21]。

結(jié)果表明，TCP Westwood的整體性能比TCP要好，可獲得更高的吞吐量和更多更好的信息。但該算法也風(fēng)險不可避免的問題，一些連接問題，可能因為帶寬高估導(dǎo)致的。

5.存在的問題及改進(jìn)方法

TCP/IP擁塞控制機制在網(wǎng)絡(luò)中發(fā)揮了不可或缺的作用，但TCP/IP擁塞控制算法本身有不能忽視的問題：（1）從發(fā)生擁塞到端系統(tǒng)實施控制之間存在明顯的時間延遲，而且終端系統(tǒng)對動態(tài)數(shù)據(jù)傳輸過程也認(rèn)識不足，無法預(yù)知網(wǎng)絡(luò)資源的具體使用情況；（2）慢啟動算法存在尤為突出的問題。首先，由于發(fā)送方無法理解慢啟動階段瓶頸鏈路的帶寬，會造成網(wǎng)絡(luò)資源利用率降低及延遲增加，特別是在網(wǎng)絡(luò)可用帶寬較大時；其次，TCP/ IP為短小數(shù)據(jù)流服務(wù)時，往往需要若干時間的RTT來檢測網(wǎng)絡(luò)帶寬，傳輸延遲經(jīng)常需要幾個RTT時間來檢測相應(yīng)的網(wǎng)絡(luò)帶寬，傳輸延遲這里是不太可靠的。

針對TCP/IP擁塞控制出現(xiàn)了上面的幾個問題，近幾年來，很多人對他們進(jìn)行了各種各樣的探討和改進(jìn)，以便更好地符合各種網(wǎng)絡(luò)應(yīng)用的需要、適應(yīng)網(wǎng)絡(luò)動態(tài)變化的特性，使網(wǎng)絡(luò)運行在最佳狀態(tài)[22]。

使用累計確認(rèn)、超時重傳和后退等機制只是早期TCP的實現(xiàn)。Nagle指出[23-24]，可以根據(jù)源端相鄰節(jié)點之間的比例，擴大兩者之間的上限值，適當(dāng)增大新回合中慢啟動的絕對閾值，通過加大慢啟動回合數(shù)來提高網(wǎng)絡(luò)發(fā)送速率。這樣保證了發(fā)送方的發(fā)送速率，可以使整個網(wǎng)絡(luò)的擁塞現(xiàn)象得到極大的緩解。

6.結(jié)語

本文闡述了擁塞控制研究的現(xiàn)狀、擁塞控制的原理，揭示擁塞控制所面臨的問題，并進(jìn)行了研究與綜述。通過對擁塞控制算法現(xiàn)狀的分析，探討了現(xiàn)行的TCP擁塞控制算法在各個階段存在的一些不可忽視的問題，并總結(jié)了改進(jìn)方法。

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

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

[3] 包俊杰，王剛，李波.TCP擁塞控制綜述[J].重慶教育學(xué)院報，2003，16（6）：30-33.

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

[5] 林闖，劉衛(wèi)東.TCP網(wǎng)絡(luò)中的擁塞控制[J].計算機世界，2001，PBl-B1.

[6] 張故轅，謝劍英，傅春.一種基于模糊邏輯的主動隊列管理算法[J].電子學(xué)報，2002，30（8）：1246-1249.

[7] 單玉峰，柴喬林.TCP友好擁塞/速率控制算法及其在多發(fā)媒體數(shù)據(jù)傳輸中的應(yīng)用[J].計算機學(xué)報，2001，（8）：886-990.

[8] 章淼，吳建平，林闖.互聯(lián)網(wǎng)端到端擁塞控制研究綜述[J].軟件學(xué)報，2002，13（3）：354-363.

[9] 陳尚兵.IP網(wǎng)絡(luò)中擁塞控制和可擴展組播路由研究[D].杭州：浙江大學(xué)，2003.

[10] 楊凱鋒，洪佩琳，束永安，李津生.Internet由器中的擁塞控制策略[J].小型微型計算機系統(tǒng)，2000，2l （4）：353-356.

[11] Jacobson V. Congestion Avoidance and Control [C]. In: Proceeding of SIOCOM, 312-329.

[12] Floyd S, Jacobson V. On Traffic Phase Effects in Packet-Switched [J]. Gateways, 1992, 3(3): 115-156.

[13] 王德鎖，舒勤.TCP擁塞控制機制在高速網(wǎng)絡(luò)中的局限性[J].中國測試技術(shù)，2004，（3）.

[14] 張賢達(dá)，保錚等.通信信號處理[M].北京：國防工業(yè)出版社，2000.

[15] 勝美，趙春明.基于最小二乘算法及子空間方法的盲多用戶檢測算法[J].通信學(xué)報，2003，24（5）：129-132.

[16] 薛強，吳偉陵.衰落信道中基于CMA的自適應(yīng)多用戶檢測算法[J].重慶郵電學(xué)院學(xué)報，2001，13（1）：17-19.

[17] 張浩亮，段煉，薛強，等.一種新的基于CMA的盲自適應(yīng)多用戶檢測算法[J].北京郵電大學(xué)學(xué)報，2003，26（1）：78-81.

[18] 朱小剛，潘理，諸鴻文等.盲恒模多用戶檢測算法的實現(xiàn)和性能優(yōu)化[J].通信技術(shù)，2002，（8）：9-11.

[19] 馮熳，廖桂生.恒模算法：進(jìn)展與展望[J].信號處理，2003，19 （5）：441-445.

[20] 方晨，劉昊，時龍興. 一種基于自適應(yīng)競爭窗口的無線傳感器網(wǎng)絡(luò)擁塞緩解策略[J].東南大學(xué)學(xué)報（自然科學(xué)版），2013，43 （4）：687-689.

[21] 潘守偉，蔣道霞.無線傳感器網(wǎng)絡(luò)中基于路由協(xié)議的擁塞控制技術(shù)研究[J].科技創(chuàng)新導(dǎo)報，2014，（5）：11-13.

[22] 趙正偉，許剛，畢經(jīng)平. 基于優(yōu)先級的時限感知的數(shù)據(jù)中心網(wǎng)絡(luò)擁塞控制算法[J].高技術(shù)通訊，2014，24（6）：587-595.

[23] 許建真，曹歡歡，宋愛玲. 基于訪問控制的無線傳感網(wǎng)鏈?zhǔn)椒謱勇酚蓞f(xié)議[J].計算機與現(xiàn)代化，2015，（4）：14-19.

[24] 韓存武，刁奇，常舒瑞，等.基于降維狀態(tài)觀測器的最優(yōu)擁塞控制研究[J].高技術(shù)通訊，2015，25（12）：1047-1052.

Research and Review of Computer Network Congestion Control Algorithm

LIU Xiaofei
( Anqing Normal University, Anqing Anhui 246133, China )

The dynamic changes of network parameters make the congestion of the network become more and more serious and complex, and the congestion control is always an important research direction. At present, the end to end congestion control mechanism based on TCP is mainly adopted. With the application of Internet and the increase of users, this mechanism has been unable to fully meet the needs of complex applications in the network. Network congestion has become an urgent problem. This paper discusses the cause of network congestion, then analyzes the performance of TCP congestion control principle and four TCP congestion control algorithm, and then focuses on the improvement of TCP congestion control facing problem and the corresponding algorithm, and finally puts forward the direction of further research.

congestion control, TCP/IP network, PID, control active queue management

TP338

A

1673-9639 (2016) 04-0109-05

（責(zé)任編輯 田 波）（責(zé)任校對 毛 志）

2016-03-09

劉曉飛（1980-），男，安徽安慶人，副教授，碩士，研究方向：計算機應(yīng)用技術(shù)。