摘要:隨著Internet的迅速發(fā)展,網(wǎng)絡(luò)規(guī)模、用戶數(shù)量及業(yè)務(wù)量呈現(xiàn)爆炸式增長,由此引發(fā)的網(wǎng)絡(luò)擁塞已經(jīng)成為制約網(wǎng)絡(luò)發(fā)展和應(yīng)用的瓶頸問題。有效解決擁塞對于提高網(wǎng)絡(luò)性能具有重要意義,如何更好的預(yù)防和控制擁塞成為近年來網(wǎng)絡(luò)研究領(lǐng)域的重要問題。該文介紹了現(xiàn)有的擁塞控制算法,并分析了進(jìn)一步的研究方向。
關(guān)鍵詞:網(wǎng)絡(luò)擁塞;擁塞控制;主動隊列管理
中圖分類號:TP393文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)14-3636-02
Research of Algorithm for Internet Congestion Control
HUANG Pei-hua
(Binzhou University, Binzhou 256600, China)
Abstract: With the rapid development of Internet, network scale, user quality and business volume assume the detonation-like growth. Network jam already became the bottle-neck question that restriction network development and application. The effective solution to network jam has vital significance to enhance the network performance. How to prevent and control jam has become the important problem of network research in recent years. In this paper, it's introduced the existing congestion control algorithms and analyzed of the direction of further research.
Key words: network jam; congestion control; active queue management
1 引言
Internet自出現(xiàn)以來得到了蓬勃發(fā)展,近年來更以驚人的速度增長。據(jù)統(tǒng)計20世紀(jì)90年代初,全球互聯(lián)網(wǎng)用戶還不到10萬,而2000年已突破3億,2002年底增加到6.55億,預(yù)計到2010年將高達(dá)20億。有限的網(wǎng)絡(luò)資源被越來越多的用戶共享,使得現(xiàn)有的帶寬難以完全滿足用戶的要求,擁塞的發(fā)生成為在所難免的事情。盡管路由器處理能力已經(jīng)有了很大的提高,但擁塞不會隨著網(wǎng)絡(luò)處理能力的提高而消除。因此,擁塞控制算法對于避免擁塞以及在擁塞發(fā)生時進(jìn)行有效的控制起著至關(guān)重要的作用。
Internet中擁塞控制的大部分工作是由TCP完成的,目前標(biāo)準(zhǔn)的TCP協(xié)議實現(xiàn)都包含了一些避免和控制網(wǎng)絡(luò)擁塞的算法,當(dāng)今Internet的可靠性和穩(wěn)定性與TCP擁塞控制機制密不可分。然而,隨著Internet用戶迅速增加和網(wǎng)絡(luò)應(yīng)用多樣化,這種擁塞控制機制的有效性正面臨著嚴(yán)峻的挑戰(zhàn),網(wǎng)絡(luò)擁塞已經(jīng)成為制約網(wǎng)絡(luò)發(fā)展和應(yīng)用的一個瓶頸,如何更好的預(yù)防和控制擁塞一直是網(wǎng)絡(luò)研究的熱點問題。
網(wǎng)絡(luò)中的擁塞來源于網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡性,擁塞不會隨著網(wǎng)絡(luò)處理能力的提高而消除。所以,擁塞控制算法是盡量避免擁塞以及在擁塞發(fā)生時進(jìn)行有效控制并加以消除的重要手段,它對保證Internet的穩(wěn)定起著至關(guān)重要的作用。
擁塞控制算法的分布性、網(wǎng)絡(luò)的復(fù)雜性和對擁塞控制算法的性能要求又使擁塞控制算法設(shè)計具有很高的難度。到目前為止,擁塞問題還沒有得到很好的解決。
2 擁塞控制算法的研究
目前擁塞控制算法的研究主要著眼于以下幾個方面:
2.1 從控制論角度,可以分為開環(huán)控制和閉環(huán)控制兩大類
開環(huán)擁塞控制是通過良好的設(shè)計來避免問題的出現(xiàn),確保問題在一開始就不會發(fā)生。一旦系統(tǒng)安裝并運行起來,就不再做任何中間階段的更正。當(dāng)流量特征可以準(zhǔn)確規(guī)定、性能要求可以事先獲得時,適于使用開環(huán)控制方式。
閉環(huán)擁塞控制建立在反饋環(huán)路的概念上,它首先檢測網(wǎng)絡(luò)中擁塞的發(fā)生,然后將擁塞信息報告到擁塞控制點,最后擁塞控制點根據(jù)擁塞信息進(jìn)行調(diào)整以消除擁塞。當(dāng)流量特征不能準(zhǔn)確描述或者當(dāng)系統(tǒng)不提供資源預(yù)留時,適于使用閉環(huán)控制方式。
閉環(huán)的擁塞控制可以動態(tài)的適應(yīng)網(wǎng)絡(luò)變化,Internet中主要采用閉環(huán)控制方式。
2.2 根據(jù)實施控制的位置不同,可以分為鏈路算法和源算法
鏈路算法在網(wǎng)絡(luò)設(shè)備(如路由器和交換機)中執(zhí)行,作用是檢測網(wǎng)絡(luò)擁塞的發(fā)生,產(chǎn)生擁塞反饋信息。鏈路算法主要有傳統(tǒng)的隊尾丟棄(Drop-Tail)算法和目前研究的主動隊列管理(Active Queue Management,AQM)算法。和傳統(tǒng)的隊尾丟棄相比,AQM在網(wǎng)絡(luò)設(shè)備緩沖溢出之前就丟棄或標(biāo)記報文。AQM的一個代表是RED(Random Early Discard)算法,研究表明RED比Drop-Tail具有更好的性能。
源算法在主機和網(wǎng)絡(luò)邊緣設(shè)備中執(zhí)行,作用是根據(jù)反饋信息調(diào)整發(fā)送速率,源算法中使用最廣泛的是TCP協(xié)議中的擁塞控制算法。近年來,TCP中采用了很多新的算法,包括慢啟動、擁塞避免、快速重傳、快速恢復(fù)、選擇性應(yīng)答等,大大提高了網(wǎng)絡(luò)傳輸?shù)男阅堋?/p>
TCP中使用的擁塞控制算法已經(jīng)成為保證Internet穩(wěn)定性的重要因素。
2.3 從實施控制的類型上,可以分為基于窗口和基于速率兩種類型
TCP采用的是典型的基于窗口的控制方式。TCP按發(fā)送窗口大小決定發(fā)送的數(shù)據(jù)量,通過調(diào)整滑動窗口大小控制發(fā)送到網(wǎng)絡(luò)的數(shù)據(jù)量?;诖翱诘姆绞揭子趯崿F(xiàn),而且可以限制注入網(wǎng)絡(luò)的最大流量。
基于速率的控制方式是通過對TCP窗口控制機制建模,得到TCP連接吞吐量與網(wǎng)絡(luò)參數(shù)之間的解析式,用來指導(dǎo)源端發(fā)送速率的大小。一般適合多媒體數(shù)據(jù)流的傳輸控制。
2.4 從推斷網(wǎng)絡(luò)狀態(tài)反饋信息的類型上,可以分為顯式擁塞控制和隱式擁塞控制
在顯式反饋方式中,網(wǎng)絡(luò)使用顯式信號(如有效帶寬、緩存容量等)向執(zhí)行流量控制的端點通告其狀態(tài);而在隱式控制方式中,控制端使用流量測量或者通過超時、重復(fù)ACK等隱含信號來推斷網(wǎng)絡(luò)狀態(tài)。
3 基于TCP/IP的擁塞控制算法
3.1 TCP擁塞控制算法
TCP的流量控制是Internet正常運行的基礎(chǔ),圍繞著TCP流量控制的擁塞控制一直是Internet研究的熱點。在Internet發(fā)展初期,擁塞控制主要是通過TCP協(xié)議中端到端的基于滑動窗口的流量控制完成的,TCP的流量控制算法經(jīng)歷了Tahoe、Reno、New Reno、Sack、Vegas等多個版本的增強與改進(jìn)。
TCP基于窗口的擁塞控制策略促進(jìn)了Internet早期的快速發(fā)展,但是所有這些工作都將研究的注意力集中到終端系統(tǒng)上,對于網(wǎng)絡(luò)中間節(jié)點考慮的較少。隨著Internet的迅速發(fā)展,網(wǎng)絡(luò)規(guī)模越來越大,結(jié)構(gòu)日趨復(fù)雜,僅僅依靠端到端的擁塞控制是不夠的。于是,人們把研究的注意力轉(zhuǎn)向網(wǎng)絡(luò)中的路由器等中間節(jié)點設(shè)備,期望通過增強它們的功能來實現(xiàn)主機端無法達(dá)到的技術(shù)目標(biāo)。就擁塞控制而言,網(wǎng)絡(luò)中間節(jié)點能更及時,甚至提前準(zhǔn)確了解網(wǎng)絡(luò)的擁塞狀態(tài),并依次實施有效的資源管理策略,使網(wǎng)絡(luò)能有效的避免擁塞或者盡早從擁塞狀態(tài)中恢復(fù)過來。
3.2 路由器擁塞控制算法
路由器中最常用的隊列管理策略是“隊尾丟棄”。它是一種擁塞恢復(fù)機制,能夠維持Internet的穩(wěn)定運行,但是存在著滿隊列、死鎖以及全局同步等問題。在此基礎(chǔ)上改進(jìn)的“首丟棄”和“隨機丟棄”對死鎖和全局同步是有效的,但沒有解決持續(xù)的滿隊列問題。
如果在路由器中增加智能預(yù)測環(huán)節(jié),使得在路由器緩存被耗盡前有計劃的丟掉一部分分組,就可以提早通知發(fā)送方降低發(fā)送速率,避免可能出現(xiàn)的危險,這就是主動隊列管理的由來。1998年,B.Braden等人提出了主動隊列管理(Active Queue Management,AQM)的研究動議,作為端到端擁塞控制的一種技術(shù)手段,期望在減小排隊時延的同時保證較高的吞吐量。這是一種主動的而非響應(yīng)性的分組丟棄手段,相應(yīng)的隊列管理策略即“主動隊列管理”成為近年來網(wǎng)絡(luò)擁塞控制研究的一個熱點。
一些控制論專家也投身其中,研究有關(guān)網(wǎng)絡(luò)流量的控制理論及網(wǎng)絡(luò)模型。近年來,非線性規(guī)劃理論、系統(tǒng)控制理論和優(yōu)化控制理論被引入到擁塞控制的研究中來,一些研究者嘗試使用嚴(yán)格的數(shù)學(xué)模型來描述由端系統(tǒng)和網(wǎng)關(guān)共同組成的系統(tǒng)。這些研究推動了擁塞控制的研究,一些新的AQM算法不斷涌現(xiàn)。
4 研究方向
擁塞控制不僅是網(wǎng)絡(luò)穩(wěn)定、高效運行的關(guān)鍵,同時又是實現(xiàn)各種服務(wù)質(zhì)量的基礎(chǔ)和前提。實際的網(wǎng)絡(luò)是一個不斷發(fā)展的系統(tǒng),網(wǎng)絡(luò)擁塞控制研究也是一個非常困難、有挑戰(zhàn)性的研究領(lǐng)域。
對網(wǎng)絡(luò)擁塞控制的研究仍有許多工作要做,進(jìn)一步的工作包括:
1) 擁塞控制基于端主機的控制策略和路由器的隊列管理策略存在相互影響、相互作用的關(guān)系,如何在網(wǎng)絡(luò)模型描述的基礎(chǔ)上,從控制系統(tǒng)的角度將兩者結(jié)合起來,設(shè)計出最優(yōu)的擁塞控制策略,是網(wǎng)絡(luò)擁塞控制研究的一個方向。
2) 主動隊列管理技術(shù)通過丟包積極響應(yīng)擁塞,來達(dá)到擁塞避免和緩解的目的,是網(wǎng)絡(luò)擁塞控制最重要的手段。如何實現(xiàn)AQM高級策略,引入新的人工智能算法和遺傳算法與模糊邏輯的綜合應(yīng)用是目前研究的一個熱點問題。
3) 以往的工作主要采用局部線性化方法,缺乏對系統(tǒng)全局動力學(xué)的理論分析。此外,在多種源端擁塞控制策略和路由器避免策略并存時,如何分析整個網(wǎng)絡(luò)的穩(wěn)定性,如何分析各種不確定因素對穩(wěn)定性的影響等,也是需要認(rèn)真考慮的問題。
4) TCP/IP擁塞控制的設(shè)計和實現(xiàn)面臨著眾多的折中,不可能有一種設(shè)計和實現(xiàn)在所有環(huán)境中都是“最好的”?,F(xiàn)有的擁塞控制思路、方法和技術(shù)在多目標(biāo)的不同環(huán)境中面臨著挑戰(zhàn),它們還有許多要改進(jìn)的地方。
5) 目前已經(jīng)有越來越多的移動用戶通過無線系統(tǒng)接入互聯(lián)網(wǎng),由于無線通信固有的特點,使得擁塞控制機制的研究更加困難,極具挑戰(zhàn)。
5 總結(jié)
擁塞控制是一個及其復(fù)雜的問題,論文僅僅對其中的一些方面做了研究,要想完全解決擁塞控制問題必須綜合多種策略,從網(wǎng)絡(luò)的各個部位,多角度全方位對擁塞加以控制。
參考文獻(xiàn):
[1] 章淼,吳建平,林闖.互聯(lián)網(wǎng)端到端擁塞控制研究綜述[J].軟件學(xué)報,2002,12(3).
[2] 林闖,單志廣,任豐原,等.計算機網(wǎng)絡(luò)的服務(wù)質(zhì)量[M].北京:清華大學(xué)出版社,2004.
[3] 章淼.互聯(lián)網(wǎng)端到端擁塞控制的研究[D]:[博士學(xué)位論文].清華大學(xué),2004.