高速網(wǎng)絡(luò)擁塞控制研究碩士畢業(yè)論文

《高速網(wǎng)絡(luò)擁塞控制研究碩士畢業(yè)論文》由會(huì)員分享，可在線閱讀，更多相關(guān)《高速網(wǎng)絡(luò)擁塞控制研究碩士畢業(yè)論文（58頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 碩士學(xué)位論文 論文題目 高速網(wǎng)絡(luò)擁塞控制研究 英文題目 Research on Congestion Control for High-Speed Network 碩士研究生 指導(dǎo)教師

2、 學(xué)科專(zhuān)業(yè) 計(jì)算機(jī)軟件與理論 論文提交日期 2009年4月 論文答辯日期 論文評(píng)閱人 答辯委員會(huì)主席 2009 年 4 月 10 日 Abstract 摘 要 隨著高速網(wǎng)絡(luò)應(yīng)用的日益廣泛，擁塞控制機(jī)制的研究變得越來(lái)越重要。擁塞控制至少應(yīng)該包含兩部分：首先是要有源端算法響應(yīng)路徑中的擁塞，動(dòng)態(tài)的調(diào)節(jié)數(shù)據(jù)發(fā)送速率;另一方面，要有一個(gè)中間節(jié)點(diǎn)管理機(jī)制能有效地預(yù)測(cè)、監(jiān)

3、測(cè)路徑中的擁塞程度，通過(guò)顯式或隱式的方法在擁塞發(fā)生前及時(shí)警告源端。 目前研究適合高速網(wǎng)絡(luò)的TCP擁塞控制機(jī)制成為一個(gè)新的研究熱點(diǎn)，一些研究者提出了一些新的算法如：STCP，H-TCP等。這些協(xié)議都是通過(guò)修改發(fā)送窗口的增加減小模式來(lái)提高TCP在高速網(wǎng)絡(luò)中的性能。其中TCPW是以可用帶寬測(cè)量為基礎(chǔ)的新的TCP協(xié)議，對(duì)原有TCP協(xié)議改動(dòng)較小，具有較好RTT公平性和較好的TCP友好性，在真實(shí)網(wǎng)絡(luò)中易于實(shí)現(xiàn)，但是TCPW仍存在一些性能缺陷。由于TCPW窗口增長(zhǎng)仍采用線性增加模式，因此不能像其他協(xié)議一樣快速獲得更大的發(fā)送窗口，而且在該算法的慢啟動(dòng)階段仍然采用指數(shù)增長(zhǎng)模式，從而導(dǎo)致大量突發(fā)數(shù)據(jù)的產(chǎn)生，造成

4、擁塞。中間節(jié)點(diǎn)控制由路由器擁塞控制算法來(lái)實(shí)現(xiàn)，主動(dòng)式隊(duì)列管理機(jī)制（AQM）是IEFT推薦的基于路由器擁塞控制關(guān)鍵技術(shù)，它和TCP端到端的擁塞控制相結(jié)合，是解決目前網(wǎng)絡(luò)擁塞控制問(wèn)題的一個(gè)主要手段。RED算法是AQM的一個(gè)典型，但其在算法穩(wěn)定性和參數(shù)敏感性方面存在缺陷。 本文基于以上兩個(gè)算法，開(kāi)展了以下三個(gè)方面的工作。首先對(duì)TCPW算法進(jìn)行改進(jìn)，主要集中在以下兩點(diǎn)：一是在慢啟動(dòng)階段發(fā)送窗口較原有算法能較快的到達(dá)10個(gè)包左右，之后窗口增長(zhǎng)速度較原有算法有所減慢，這樣有利于短流傳輸和避免突發(fā)數(shù)據(jù)產(chǎn)生，從而減緩擁塞；二是在擁塞避免階段采用基于當(dāng)前擁塞窗口大小的先快后慢的非線性增長(zhǎng)方式，使之更適合于高速

5、環(huán)境。通過(guò)建立新算法的數(shù)學(xué)模型分析其穩(wěn)定性、RTT公平性和對(duì)TCP友好性，在此基礎(chǔ)上分別對(duì)以上兩點(diǎn)改進(jìn)采用NS2仿真方法加以驗(yàn)證，發(fā)現(xiàn)算法較原有算法在高速環(huán)境下有更好的吞吐量和更有利于短流數(shù)據(jù)傳輸。另外本文在分析RED算法基礎(chǔ)上，提出了一種新的改進(jìn)型AQM算法——DRED算法。DRED相對(duì)RED算法，能夠動(dòng)態(tài)調(diào)整參數(shù)，并且采用非線性函數(shù)代替原有的丟包率計(jì)算方法。通過(guò)動(dòng)態(tài)調(diào)整來(lái)調(diào)整向源端發(fā)送擁塞通知的速率，維持隊(duì)列的穩(wěn)定；通過(guò)新丟包率計(jì)算方式，提高緩沖的利用率和使隊(duì)列長(zhǎng)度盡量穩(wěn)定于期望值附近。最后通過(guò)仿真來(lái)驗(yàn)證新算法更適應(yīng)網(wǎng)絡(luò)流量的變化，保持隊(duì)列長(zhǎng)度的穩(wěn)定和丟包率的穩(wěn)定，從而提高了網(wǎng)絡(luò)鏈路利用率

6、。 關(guān)鍵詞：高速網(wǎng)； 擁塞控制； TCPW； RED 52 Abstract Abstract With the development of the applications on high-speed network, research on congestion control becomes more and more important. Congestion control should include two parts: end-to-end control and link control. End-to-end control could adjust

7、the data sending rate dynamically in order to respond to link congestion. On the other hand, the link control can predicate and monitor the degree of congestion effectively, then send the warning to sender before congestion happening by explicit or implicit method. Now more and more scientists beg

8、in on the researches of the TCP congestion control mechanisms for high-speed networks and this research has become a focal subject. There are some typical protocols:, such as STCP, H-TCP,TCPW etc. These new protocols enhance the performance on the high-speed networks through adjusting the increases

9、and decreases mode of window, TCPW algorithm is a better one, it is based on BWE (Bandwidth Estimation) and has little changes on TCP protocol. it also provides a sensible fairness increment with respect to TCP Reno, Moreover, TCPW is friendly to Reno. But there are still some shortages in it, Conge

10、stion window of TCPW is based on additive increase of linear mode. So, in high-speed networks it can’t obtain high throughput rapidly. During the slow-start stage, the congestion window of TCPW is based on exponential growth mode, then this will cause the datagram increases too fast and prompt the p

11、robability of congestion. Link control is implemented by router. The active queue management mechanism(AQM) is, which the IETF recommends, the essential technology based on the router congestion control, combining with the TCP end-to-end congestion control, it provide an effective method to solve th

12、e congestion control question on Internet. RED algorithm is typical algorithm in AQM, but it exist some drawbacks, for example, the instability and the parameter sensitivity. In this paper, we give the researches on the following three aspects based on the above algorithm: TCPW and RED. At first,

13、we improve the performance of the TCPW from two points. One enhances the former method by reducing the increasing speed of the datagram and increasing the increasing speed before the window is 10 during the slow-start stage. This decreases the occurring rate of congestion and improves the performanc

14、e of short-term linkages transmission. On the other hand, we use a simple nonlinear mode to increase the congestion widow instead of the linear mode. This new mathematical model and the new algorithm is friendly to Reno and have fairness increment with respect to TCP Reno. Through the simulation on

15、NS-2 platform, the experiments show that the new algorithm can obtain more throughput than TCPW in high-speed network and improve the short-term linkages transmission. Secondly, the other work an improved algorithm DRED of active queue management (AQM), is proposed. Based on the interpolation’s size

16、, DRED can adjust dynamically the size Pmax, and therefore adjust the sending rate of congestion notification to the source end in time. The new algorithm uses the nonlinear mode to adjust the probability of drop, and maintain the stability of queue length of mathematical expectation. At last, the s

17、imulations on NS-2 show that DRED can adapt the change of network flow validly, hold the stability of queue length and also decrease the probability of drop. So it is superior to the RED algorithm in maintaining the stability of queue length and enhancing the utilization ration of the links. Key

18、words: high-speed networks; congestion control; TCPW; RED 目錄 目錄 摘 要 I Abstract II 第一章 緒 論 1 1.1 研究背景 1 1.2 研究現(xiàn)狀 3 1.3 主要研究工作 5 1.4 論文的內(nèi)容及安排 6 第二章 擁塞控制算法綜述 8 2.1 擁塞產(chǎn)生的原因 8 2.2 擁塞控制算法分類(lèi) 10 2.2.1 擁塞控制源端算法 10 2.2.2 源端擁塞控制的研究現(xiàn)狀 11 2.2.3 擁塞控制鏈路算法 14 2.2.4 鏈路擁塞控制研究現(xiàn)狀 15 2.3 擁塞控制算法的評(píng)

19、價(jià)標(biāo)準(zhǔn) 18 2.3.1 穩(wěn)定性分析 18 2.3.2 公平性分析 19 2.3.3 友好性分析 20 2.4 小結(jié) 20 第三章 TCP Westwood擁塞控制算法改進(jìn) 21 3.1 引言 21 3.2 TCPW算法的分析 22 3.2.1 TCPW算法的簡(jiǎn)介 22 3.2.2 TCPW算法優(yōu)點(diǎn) 23 3.2.3 TCPW算法存在的不足 23 3.3 改進(jìn)的擁塞控制算法NLTCPW 24 3.3.1 擁塞避免階段改進(jìn) 25 3.3.2 慢啟動(dòng)階段改進(jìn) 25 3.3.3 NLTCPW算法的數(shù)學(xué)模型 26 3.3.4 仿真環(huán)境下NLTCPW算法的吞吐量性能分析 2

20、9 3.3.5 NLTCPW算法RTT公平性實(shí)驗(yàn) 32 3.3.6 NLTCPW算法短流數(shù)據(jù)傳輸性能分析 32 3.4 小結(jié) 34 第四章 RED算法改進(jìn) 35 4.1 一種新的自適應(yīng)RED算法—DRED算法 35 4.1.1 RED算法概述 35 4.1.2 RED算法的優(yōu)點(diǎn) 36 4.1.3 RED算法存在的不足 36 4.1.4 DRED算法 38 4.2 DRED算法性能分析 40 4.3 小結(jié) 45 第五章 結(jié)論及未來(lái)的工作 46 5.1結(jié)論 46 5.2 未來(lái)的工作 47 致 謝 48 攻讀碩士學(xué)位期間從事的主要科研工作及發(fā)表的論文 49 參考文獻(xiàn)

21、 50 第一章 緒論 第一章 緒 論 1.1 研究背景 近年來(lái)隨著信息技術(shù)迅速發(fā)展，以互聯(lián)網(wǎng)為代表的信息網(wǎng)絡(luò)已經(jīng)逐漸滲透到當(dāng)今社會(huì)的各個(gè)領(lǐng)域，成為了國(guó)家進(jìn)步和社會(huì)發(fā)展的重要支柱，以及知識(shí)經(jīng)濟(jì)的基礎(chǔ)載體和支撐環(huán)境，它的重要性就如同鐵路和高速公路的蓬勃發(fā)展給工業(yè)社會(huì)帶來(lái)了廣泛而深遠(yuǎn)的影響一樣，必將成為21世紀(jì)全球最重要的基礎(chǔ)設(shè)施之一。就目前的現(xiàn)狀和未來(lái)的發(fā)展而言，下一代互聯(lián)網(wǎng)的骨干帶寬必將呈現(xiàn)指數(shù)型增長(zhǎng)。下一代互聯(lián)網(wǎng)建設(shè)與發(fā)展的各種趨勢(shì)表明：大規(guī)模的高速網(wǎng)絡(luò)試驗(yàn)環(huán)境已經(jīng)形成，未來(lái)幾年內(nèi)，互聯(lián)網(wǎng)骨干將全面升級(jí)到支持近10Gbps的高速鏈路，而且很有可能持續(xù)增長(zhǎng)。但是，雖然下一代互聯(lián)網(wǎng)

22、的骨干帶寬呈現(xiàn)指數(shù)性的增長(zhǎng)，實(shí)踐中上述海量數(shù)據(jù)傳輸業(yè)務(wù)的用戶卻并沒(méi)有切身感受到網(wǎng)絡(luò)帶寬劇增所帶來(lái)的好處，于是人們開(kāi)始懷疑高速網(wǎng)絡(luò)中傳輸協(xié)議的性能。這是由于TCP/IP協(xié)議在高速網(wǎng)絡(luò)中確實(shí)存在效率問(wèn)題[1]。因此研究適應(yīng)于高速網(wǎng)絡(luò)的擁塞控制算法成了網(wǎng)絡(luò)研究的新熱點(diǎn)。 目前，Internet上用戶和應(yīng)用的數(shù)量都在迅速增長(zhǎng)，當(dāng)多個(gè)用戶對(duì)網(wǎng)絡(luò)的需求總量大于網(wǎng)絡(luò)實(shí)際傳輸能力時(shí)，必然會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞的發(fā)生。雖然擁塞源于資源短缺，但增加資源并不能避免擁塞的發(fā)生，有時(shí)甚至?xí)又負(fù)砣潭萚2]。所以選擇和引進(jìn)更多、更合理的擁塞控制機(jī)制對(duì)網(wǎng)絡(luò)的高效穩(wěn)定運(yùn)行是至關(guān)重要的。 隨著應(yīng)用需求的豐富和技術(shù)的發(fā)展，研究者開(kāi)

23、始認(rèn)識(shí)到想完全依賴實(shí)現(xiàn)在終端系統(tǒng)上的策略與算法很難滿足越來(lái)越多的復(fù)雜應(yīng)用需求。于是，人們把注意力轉(zhuǎn)向網(wǎng)絡(luò)中的路由器等中間節(jié)點(diǎn)設(shè)備，期望通過(guò)增強(qiáng)它們的功能來(lái)實(shí)現(xiàn)主機(jī)端無(wú)法達(dá)到的目標(biāo)網(wǎng)。就擁塞控制而言，網(wǎng)絡(luò)中間節(jié)點(diǎn)有可能更及時(shí)，甚至可以提前準(zhǔn)確了解網(wǎng)絡(luò)的擁塞狀態(tài)，并依此實(shí)施有效的資源管理策略，使網(wǎng)絡(luò)能有效地避免擁塞，或盡早從嚴(yán)重的擁塞狀態(tài)中恢復(fù)過(guò)來(lái)。當(dāng)然，對(duì)路由器功能的擴(kuò)展要受繼承性和延續(xù)性的限制，否則將影響技術(shù)的實(shí)用性。事實(shí)上，現(xiàn)有的路由器擴(kuò)展功能，主要包括調(diào)度和隊(duì)列/緩存管理。調(diào)度(Scheduling)直接管理下次發(fā)哪個(gè)分組和分配各個(gè)流的帶寬。而隊(duì)列/緩存算法管理路由器緩沖區(qū)中分組隊(duì)列的長(zhǎng)度

24、，即在必要或適當(dāng)?shù)臅r(shí)候丟掉一些分組。 因此根據(jù)擁塞控制算法實(shí)現(xiàn)的位置不同主要分為兩大類(lèi)：源端控制和鏈路控制，源算法在主機(jī)和網(wǎng)絡(luò)邊緣設(shè)備中的執(zhí)行作用主要是根據(jù)獲得的反饋信息調(diào)整發(fā)送速率。鏈路算法在網(wǎng)絡(luò)設(shè)備(如路由器和交換機(jī))中執(zhí)行，作用是檢測(cè)網(wǎng)絡(luò)擁塞的發(fā)生，產(chǎn)生擁塞反饋信息。源算法和鏈路算法形成反饋，共同實(shí)現(xiàn)擁塞控制，兩者形成的反饋系統(tǒng)共同形成了擁塞控制系統(tǒng)，所以必須在這兩方面同時(shí)進(jìn)行研究和綜合。在實(shí)際部署中要考慮效率和費(fèi)用比的問(wèn)題同時(shí)又要要求源端控制和鏈路控制必須相互獨(dú)立，一個(gè)對(duì)原有系統(tǒng)改動(dòng)過(guò)大的擁塞控制算法不利于部署。比如XCP[3](eXplicit Control Protocol)，

25、是美國(guó)麻省理工和伯克利針對(duì)高帶寬時(shí)延乘積網(wǎng)絡(luò)提出的一個(gè)Internet擁塞控制的新體系結(jié)構(gòu)，它是將端節(jié)點(diǎn)和路由器相結(jié)合完成擁塞控制的執(zhí)行模式。XCP協(xié)議其路由器算法主要由有效控制算法（EC）和公平性控制算法（FC）構(gòu)成。EC僅考慮鏈路的總流量，而不考慮單條流的流量及公平性問(wèn)題。FC實(shí)現(xiàn)目標(biāo)是將EC計(jì)算出來(lái)的總的反饋量在包層次上公平地分配給每條流。FC以包為單位來(lái)分配EC計(jì)算出的總的反饋量。在端節(jié)點(diǎn)數(shù)據(jù)包結(jié)構(gòu)中增加了cwnd、RTT估計(jì)和feedback三個(gè)域。發(fā)送端發(fā)送數(shù)據(jù)包時(shí)使用feedback域請(qǐng)求希望得到的擁塞窗口調(diào)整的變化量，數(shù)據(jù)包途經(jīng)的路由器根據(jù)當(dāng)時(shí)網(wǎng)絡(luò)可用帶寬的狀況修改feedba

26、ck域的值。當(dāng)數(shù)據(jù)包到達(dá)接收端時(shí)，feedback域保留的是該數(shù)據(jù)包途徑的各路由器允許發(fā)送端可以增加的帶寬的最小值或要求發(fā)送端需要減少的帶寬的最大值，然后接收端通過(guò)ACK包將feedback域的值反饋給發(fā)送端，最終發(fā)送端按照反饋調(diào)整隨后的發(fā)送速率。但是XCP的關(guān)鍵算法全部在路由器內(nèi)實(shí)現(xiàn)，在實(shí)際網(wǎng)絡(luò)中要建造如此強(qiáng)大功能的路由器的造價(jià)是十分昂貴的；同時(shí)若端節(jié)點(diǎn)或中間路由節(jié)點(diǎn)其中一個(gè)不支持此協(xié)議，算法將失效；因此XCP在實(shí)際網(wǎng)絡(luò)中難以實(shí)現(xiàn)和部署。 擁塞控制算法的分布性、網(wǎng)絡(luò)的復(fù)雜性和對(duì)擁塞控制算法性能要求等使擁塞控制算法的設(shè)計(jì)具有很高的難度Error! Reference source not f

27、ound.，其主要表現(xiàn)如下： 1) 算法的分布性 擁塞控制算法的實(shí)現(xiàn)分布在多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中，必須使用不完整的信息完成控制，并使各節(jié)點(diǎn)協(xié)調(diào)工作，還必須考慮某些節(jié)點(diǎn)工作不正常的情況。 2) 網(wǎng)絡(luò)環(huán)境的復(fù)雜性 Internet中各處的網(wǎng)絡(luò)性能有很大的差異，算法必須具有很好的適應(yīng)性。另外，由于Internet對(duì)報(bào)文的正確傳輸不提供保證，算法必須處理報(bào)文丟失、亂序到達(dá)等情況。 3) 算法的性能要求。 擁塞控制算法對(duì)性能有很高的要求，包括算法的公平性、效率、穩(wěn)定性和收斂性等。某些性能目標(biāo)之間存在矛盾，在算法設(shè)計(jì)時(shí)需要進(jìn)行權(quán)衡。 4) 算法的開(kāi)銷(xiāo) 擁塞控制算法必須盡量減少附加的網(wǎng)絡(luò)流量

28、，特別是在擁塞發(fā)生時(shí)。在使用反饋式的控制機(jī)制時(shí)，這個(gè)要求增加了算法設(shè)計(jì)的困難。算法還必須盡量降低在網(wǎng)絡(luò)節(jié)點(diǎn)（特別是網(wǎng)關(guān)）上的計(jì)算復(fù)雜性。 1.2 研究現(xiàn)狀 目前對(duì)網(wǎng)絡(luò)擁塞控制的研究主要從以下兩個(gè)方面進(jìn)行：首先是解決源端的算法，通過(guò)依靠動(dòng)態(tài)的調(diào)節(jié)源端數(shù)據(jù)發(fā)送速率，及時(shí)能響應(yīng)路徑中的擁塞；另一方面是解決鏈路算法，通過(guò)對(duì)中間節(jié)點(diǎn)的有效管理機(jī)制能，不斷地預(yù)測(cè)并監(jiān)測(cè)路徑中的擁塞程度，通過(guò)顯式或隱式的方法在擁塞發(fā)生前及時(shí)警告源端，在擁塞發(fā)生之后抑制源端的發(fā)送速率以超出中間節(jié)點(diǎn)轉(zhuǎn)發(fā)速率的速度發(fā)送報(bào)文分組。 傳統(tǒng)的源端TCP擁塞控制算法使得當(dāng)前的Internet網(wǎng)絡(luò)獲得了巨大的成功，但是近幾年來(lái)人們?cè)絹?lái)

29、越清楚的認(rèn)識(shí)到傳統(tǒng)的TCP擁塞控制機(jī)制主要采用了慢啟動(dòng)機(jī)制和AIMD（和式增加積式減少）的擁塞避免機(jī)制，它在高速長(zhǎng)距離網(wǎng)絡(luò)中的性能已達(dá)到瓶頸[4]。文獻(xiàn)[4]分析了傳統(tǒng)TCP在高速長(zhǎng)距離網(wǎng)絡(luò)中不能達(dá)到高吞吐量的主要的原因表現(xiàn)在如下幾個(gè)方面： 1) 現(xiàn)存的擁塞控制機(jī)制對(duì)擁塞反應(yīng)性比較差 TCP在高速長(zhǎng)距離網(wǎng)絡(luò)中對(duì)包丟失的敏感程度遠(yuǎn)遠(yuǎn)高于局域網(wǎng)或者普通的廣域網(wǎng)，這主要?dú)w因于它的擁塞避免算法中基于AIMD（和式增加積式減少）的窗口增加減少原則。在它的擁塞避免算法中每一個(gè)往返時(shí)延（RTT）至多增加一個(gè)數(shù)據(jù)包的小尺寸來(lái)增加擁塞窗口（和式增加），而單個(gè)包丟失在高速長(zhǎng)距離網(wǎng)絡(luò)中的影響是非常普遍的的，當(dāng)一

30、個(gè)TCP連接一旦被探測(cè)到有數(shù)據(jù)包丟失時(shí)，立刻要將它的擁塞窗口減少一半（積式減少），這需要花去幾百毫秒甚至幾秒才能重新恢復(fù)到原來(lái)的窗口大小，這種緩慢的窗口恢復(fù)速度會(huì)直接導(dǎo)致吞吐率不高，無(wú)法充分利用帶寬。相反窗口減小又顯得過(guò)于激烈，造成了網(wǎng)絡(luò)流量的巨大震蕩，同時(shí)也會(huì)降低網(wǎng)絡(luò)的吞吐量。而另一方面慢啟動(dòng)也會(huì)造成TCP在網(wǎng)絡(luò)中的性能下降，但相對(duì)而言這方面的影響比擁塞避免階段要小很多，這是因?yàn)樵赥CP連接中往往是通過(guò)收到三個(gè)重復(fù)ACK而不是超時(shí)來(lái)檢測(cè)丟包，所以TCP連接在擁塞避免階段比慢啟動(dòng)階段要花費(fèi)更多的時(shí)間。 2) 對(duì)數(shù)據(jù)包丟失的解釋不同 數(shù)據(jù)包在傳輸過(guò)程中可能會(huì)由于緩沖區(qū)溢出或者傳輸介質(zhì)的出錯(cuò)而

31、引起包丟失或者包損壞的情況，傳統(tǒng)TCP假定鏈路錯(cuò)誤造成的損失是可以忽略不計(jì)的，但是在高速網(wǎng)絡(luò)中，當(dāng)數(shù)據(jù)傳輸?shù)乃俾瘦^高時(shí)，鏈路錯(cuò)誤是不能被忽略的，由數(shù)據(jù)鏈路錯(cuò)誤引起的丟包和由網(wǎng)絡(luò)擁塞引起的丟包的可能性是相同的，所以在高速網(wǎng)絡(luò)中不能籠統(tǒng)的認(rèn)為只要是分組丟失就一定由網(wǎng)絡(luò)擁塞引起的。 3) 擁塞窗口和丟包率之間存在固定的函數(shù)關(guān)系 在TCP的擁塞控制算法中窗口大小w與丟包率p之間的約束關(guān)系為[5]，由此可見(jiàn)，在這種固定的關(guān)系約束下，要保持大的擁塞窗口需要極小的丟包率，即使丟包率能達(dá)到這個(gè)要求，對(duì)于發(fā)送端來(lái)說(shuō)，這也是一個(gè)極為不精確的反饋；所以在最后TCP的擁塞控制算法不得不引入丟包來(lái)估計(jì)帶寬，但是隨著

32、帶寬時(shí)延乘積的增加，在實(shí)際網(wǎng)絡(luò)中該平衡狀態(tài)難以實(shí)現(xiàn)，從而使網(wǎng)絡(luò)帶寬不能得到有效的利用。 4) 擁塞避免階段 傳統(tǒng)TCP在連續(xù)收到三個(gè)重復(fù)ACK，才開(kāi)始重傳并且減少慢啟動(dòng)閥值和擁塞窗口。但在擁塞嚴(yán)重的情況下，第二個(gè)或第三個(gè)重復(fù)ACK包很可能不會(huì)到達(dá)源端。這一方面增加了網(wǎng)絡(luò)重傳丟失數(shù)據(jù)包的時(shí)間，另一方面會(huì)造成不必要的重傳，而轉(zhuǎn)入不必要的慢啟動(dòng)階段。從而降低了系統(tǒng)吞吐量、增加了延時(shí)、影響了系統(tǒng)的性能。這些對(duì)于高速網(wǎng)絡(luò)來(lái)說(shuō)都是非常不利的。 5) 過(guò)長(zhǎng)的恢復(fù)周期 每個(gè)TCP連接發(fā)生丟包后窗口減半，然后再恢復(fù)到原來(lái)的窗口大小需要花去很長(zhǎng)時(shí)間。就單個(gè)TCP連接而言，它的調(diào)整周期和連接回路的往返時(shí)間及

33、擁塞窗口值大小有關(guān)，即調(diào)整周期等于擁塞窗口大小的二分之一乘以一個(gè)窗口數(shù)據(jù)傳輸?shù)耐禃r(shí)間。特別是在高帶寬網(wǎng)絡(luò)中，傳統(tǒng)TCP在一次丟包后要經(jīng)過(guò)幾個(gè)甚至幾十個(gè)RTT才能恢復(fù)到原來(lái)的窗口大小。要達(dá)到100%完全利用鏈路的理想狀態(tài)那更是不可能實(shí)現(xiàn)的。 從以上分析可以看出，造成TCP擁塞控制算法在高速網(wǎng)絡(luò)中性能不好的主要原因是其擁塞控制機(jī)制不適應(yīng)于高速網(wǎng)絡(luò)，目前已經(jīng)有一些學(xué)者提出了多種解決方案，主要分為四類(lèi)：1)基于丟失的算法;2)基于延遲的算法;3)基于丟失和延遲相混合的算法;4)基于顯示擁塞指示的算法。傳統(tǒng)TCP是典型的基于丟失的算法；FAST TCP[5]將延遲作為擁塞指示的算法,Africa T

34、CP[6]用隊(duì)列延遲和包丟失作為網(wǎng)絡(luò)的擁塞指示。在正常的工作環(huán)境下，擁塞窗口經(jīng)過(guò)一個(gè)RTT被更新且依賴于平均RTT的估計(jì)。TCP Africa算法就是一個(gè)基于丟失和延遲的“雙模式”算法。XCP[3]屬于最后一類(lèi)，它需要通過(guò)從網(wǎng)絡(luò)環(huán)境中獲取的指示信號(hào)來(lái)推斷網(wǎng)絡(luò)是否發(fā)生擁塞，這種算法的配置需要和路由器同時(shí)進(jìn)行操作。 基于路由器的擁塞控制（即鏈路控制算法）主要是通過(guò)對(duì)其隊(duì)列進(jìn)行管理來(lái)實(shí)現(xiàn)的，目前的隊(duì)列管理主要還是被動(dòng)式隊(duì)列管理(Passive Queue Management，PQM)。本質(zhì)上PQM并沒(méi)有參與到網(wǎng)絡(luò)擁塞管理中去，只是在隊(duì)列溢出的情況下被動(dòng)地丟包。若路由器上使用主動(dòng)式隊(duì)列管(Acti

35、ve Queue Management，AQM)機(jī)制來(lái)控制在什么時(shí)候丟多少包，將有效地管理隊(duì)列長(zhǎng)度，以支持端到端的擁塞控制。其基本思想是通過(guò)監(jiān)控路由器輸出端口隊(duì)列的平均長(zhǎng)度來(lái)探測(cè)擁塞。一旦發(fā)現(xiàn)擁塞逼近，就隨機(jī)地選擇時(shí)機(jī)對(duì)源端進(jìn)行通知擁塞，使它們?cè)陉?duì)列溢出導(dǎo)致丟包之前降低發(fā)送數(shù)據(jù)速率，從而緩解網(wǎng)絡(luò)擁塞。主要的AQM算法有RED[8]、ARED[9]、FRED[10] 、BLUE[11] 、WRED[12]、PI[13]、AVQ[14]和 REM [15]。其中RED、ARED和FRED屬于一類(lèi)，都是隨機(jī)早期檢測(cè)算法。PI是基于控制理論提出一種算法，PI控制算法可以有效消除“穩(wěn)態(tài)誤差”，但同時(shí)也會(huì)

36、減慢系統(tǒng)的反應(yīng)速度，而且PI控制器只能很好的工作在一定得分范圍的環(huán)境中，這使PI難以在真實(shí)的網(wǎng)絡(luò)環(huán)境中使用；REM是基于優(yōu)化理論提出的。AQM算法的共同特點(diǎn)是，計(jì)算出丟包率后反饋給源端系統(tǒng)，源端系統(tǒng)可以采取的動(dòng)作包括“丟棄”（Dropping）和“標(biāo)記”（Marking）?！皝G棄”是現(xiàn)有系統(tǒng)都支持的一種操作，而“標(biāo)記”的方法，可經(jīng)“顯示”的通知源端系統(tǒng)擁塞的發(fā)生，比較而言“標(biāo)記”方法性能更好。隨著“顯示擁塞通知”(ECN)的標(biāo)準(zhǔn)化和廣泛采用，將有越來(lái)越多的網(wǎng)關(guān)支持“標(biāo)記”的策略。從實(shí)際的應(yīng)用來(lái)看，路由器廠商紛紛在自己的產(chǎn)品中支持RED算法，如Ciseo7500等系列路由器，Juniper的M4

37、0、M80等；在Differv的業(yè)務(wù)框架下，由RED演化出來(lái)的RIO(RED with IN/OUT)成為提供確保服務(wù)(Assured Services)的基本算法。由于RED算法的有效性目前己被廣泛使用在網(wǎng)絡(luò)隊(duì)列管理中來(lái)提高系統(tǒng)的綜合性能。 隨著高速網(wǎng)絡(luò)的發(fā)展，擁塞控制算法的研究由于其巨大的復(fù)雜性，已不滿足于以往的基于主觀方法提出解決方案再進(jìn)行模擬分析擁塞控制算法性能的思路，而必須建立起其理論上的框架，用控制理論和優(yōu)化理論等現(xiàn)代分析方法來(lái)研究網(wǎng)絡(luò)的動(dòng)力學(xué)模型和特性，揭示Internet網(wǎng)絡(luò)形成擁塞現(xiàn)象的物理機(jī)制，分析各種算法以及算法的組合的性能，發(fā)展更有效的擁塞控制算法，以滿足人們對(duì)網(wǎng)絡(luò)快

38、速增長(zhǎng)的需求。 總的來(lái)說(shuō)，高速網(wǎng)絡(luò)擁塞控制的研究從最初單純解決TCP的低效問(wèn)題，到圍繞公平性、穩(wěn)定性以及收斂性等方面開(kāi)展了一系列更深入的研究，但是到目前為此，在該研究領(lǐng)域仍然存在很多開(kāi)放性問(wèn)題，其中作者認(rèn)為最為突出的一點(diǎn)是目前的多數(shù)研究沒(méi)有充分強(qiáng)調(diào)模型分析的重要性，缺乏具有總結(jié)性結(jié)論和定律的歸納與描述。同時(shí)在擁塞控制機(jī)制和算法的設(shè)計(jì)上過(guò)分依賴于基于經(jīng)驗(yàn)的啟發(fā)式設(shè)計(jì)結(jié)合典型、有限和局部仿真試驗(yàn)驗(yàn)證的設(shè)計(jì)方法，得到的算法往往是靜態(tài)的和準(zhǔn)靜態(tài)的，不能適應(yīng)快速變化的動(dòng)態(tài)網(wǎng)絡(luò)化環(huán)境。高速網(wǎng)絡(luò)環(huán)境下?lián)砣刂扑惴ǖ膬?yōu)化設(shè)計(jì)還存在很大的研究空間。 1.3 主要研究工作 隨著Internet的發(fā)展，它的傳

39、輸擁塞控制機(jī)制必須保持有效性。技術(shù)的趨勢(shì)表明越來(lái)越多的高帶寬鏈路將應(yīng)用到互聯(lián)網(wǎng)絡(luò)中，高速網(wǎng)絡(luò)擁塞控制協(xié)議的設(shè)計(jì)分類(lèi)兩類(lèi):修改TCP協(xié)議、終端與路由器聯(lián)合的協(xié)議。針對(duì)高速網(wǎng)絡(luò)的特點(diǎn)基于TCP協(xié)議采用不同的機(jī)制進(jìn)行改進(jìn)而來(lái)的新協(xié)議包括前面提到的FAST TCP在內(nèi)的諸如：High-Speed TCP[16] 、Scalable TCP[17]、BIC[18]、CUBIC[19]和H-TCP[20]。這些協(xié)議設(shè)計(jì)的主要目的是在高速網(wǎng)絡(luò)下能快速的獲得高的穩(wěn)定的吞吐量，從而提高高速網(wǎng)絡(luò)鏈路的利用率。 本文首先分析TCPW[21]算法在高速網(wǎng)環(huán)境下，慢啟動(dòng)和擁塞避免階段存在問(wèn)題提出一種改進(jìn)NLTCPW算

40、法。NLTCPW將TCPW在高帶寬時(shí)延積網(wǎng)絡(luò)中窗口增加采用線性方式改為一種非線性增長(zhǎng)方式，使之窗口增加先快后慢，窗口維持在一個(gè)較大的水平，從而獲得更好的帶寬利用率；慢啟動(dòng)階段窗口開(kāi)始階段較快的增加到10（包），超過(guò)10（包）后減緩增長(zhǎng)速度，這樣可以提高WEB流的傳輸，降低網(wǎng)絡(luò)丟包率，降低網(wǎng)絡(luò)突發(fā)數(shù)據(jù)量；建立NLTCPW的數(shù)學(xué)模型，從理論上對(duì)NLTCPW的穩(wěn)定性，RTT公平性、TCP友好性進(jìn)行分析，利用仿真工具在網(wǎng)絡(luò)吞吐量、WEB流數(shù)據(jù)傳輸、丟包率等方面對(duì)NLTCPW和TCPW進(jìn)行了比較分析，結(jié)果表明NLTCPW相對(duì)TCPW在保持原有算法優(yōu)點(diǎn)情況下提高網(wǎng)絡(luò)吞吐量和其在傳輸短流數(shù)據(jù)方面效率。 由

41、于RED算法是IEFT推薦在路由器上的算法，所以研究RED算法實(shí)用性更好且易于部署,RED算法存在的一個(gè)主要問(wèn)題就是其參數(shù)是靜態(tài)配置的，而互聯(lián)網(wǎng)是基于帶寬統(tǒng)計(jì)復(fù)用的，一條鏈路上往往有很多活躍流，并且流量變化很大，RED算法不能適應(yīng)這種變化導(dǎo)致其在很多情況下性能會(huì)大大下降。我們的研究目的就是對(duì)RED算法的參數(shù)配置進(jìn)行改進(jìn)，使其能夠根據(jù)流量的變化來(lái)自動(dòng)配置參數(shù)，從而保證性能的穩(wěn)定。另一方面修改RED的丟包率計(jì)算策略，由原來(lái)的線性計(jì)算變?yōu)榉蔷€性，這樣有利于緩沖隊(duì)列資源的有效使用和隊(duì)列長(zhǎng)度的穩(wěn)定。 1.4 論文的內(nèi)容及安排 第一章緒論介紹網(wǎng)絡(luò)擁塞控制的研究概況及研究背景，最后對(duì)本文的研究?jī)?nèi)容進(jìn)行了

42、概述。 第二章網(wǎng)絡(luò)網(wǎng)絡(luò)擁塞控制機(jī)制對(duì)網(wǎng)絡(luò)擁塞的原因，網(wǎng)絡(luò)擁塞的現(xiàn)象及擁塞控制的基本機(jī)制進(jìn)行了闡述，對(duì)TCP擁塞控制源算法、鏈路算法及算法的評(píng)價(jià)標(biāo)準(zhǔn)逐一進(jìn)行了討論。 第三章從理論分析和模擬實(shí)驗(yàn)證實(shí)了TCP WestWood算法在鏈路利用率、穩(wěn)定性、RTT公平性、TCP友好性和收斂性等方面的性能，針對(duì)TCP WestWood 算法在擁塞避免階段窗口任然采用傳統(tǒng)線性增長(zhǎng)方式的缺點(diǎn)，提出了采用非線性增長(zhǎng)方式NLTCP WestWood 算法，并且優(yōu)化其慢啟動(dòng)，并對(duì)該算法進(jìn)行了詳細(xì)的仿真實(shí)驗(yàn)。 第四章在分析RED算法的基礎(chǔ)上，構(gòu)建一種改進(jìn)的DRED算法,并且驗(yàn)證其隊(duì)列長(zhǎng)度和丟包率更為穩(wěn)定。 第五

43、章是結(jié)論部分，在總結(jié)本文的研究工作基礎(chǔ)上指出本文研究存在的一些問(wèn)題，給出進(jìn)一步的研究方向。 重慶郵電大學(xué)碩士論文 第二章 擁塞控制算法綜述 第二章 擁塞控制算法綜述 當(dāng)網(wǎng)絡(luò)中存在過(guò)多的數(shù)據(jù)包時(shí)，網(wǎng)絡(luò)的性能就會(huì)下降，這種現(xiàn)象稱為擁塞。在網(wǎng)絡(luò)發(fā)生擁塞時(shí)，會(huì)導(dǎo)致吞吐量下降，嚴(yán)重時(shí)會(huì)發(fā)生“擁塞崩潰”(congestion collapse)現(xiàn)象[22]。一般來(lái)說(shuō)，擁塞崩潰發(fā)生在網(wǎng)絡(luò)負(fù)載的增加導(dǎo)致網(wǎng)絡(luò)效率的降低的時(shí)候。目前對(duì)互聯(lián)網(wǎng)進(jìn)行的擁塞控制主要是依靠在源端執(zhí)行的基于窗口的TCP擁塞控制機(jī)制和依靠路由執(zhí)行的鏈路控制機(jī)制。 圖2-1 顯示了負(fù)載與吞吐量的關(guān)系[23]，當(dāng)負(fù)載較小時(shí)，吞吐量與

44、負(fù)載之間呈現(xiàn)線性關(guān)系，到達(dá)膝點(diǎn)(Knee)之后，隨負(fù)載的增加，吞吐量的增量逐漸變小。當(dāng)負(fù)載越過(guò)崖點(diǎn)(Cliff)[24]之后，吞吐量卻急劇下降，此時(shí)網(wǎng)絡(luò)陷入了嚴(yán)重?fù)砣麪顟B(tài)，若不及時(shí)進(jìn)行控制，則有可能導(dǎo)致網(wǎng)絡(luò)崩潰。擁塞控制的目的就是使吞吐量盡量保持在膝點(diǎn)與崖點(diǎn)之間，使網(wǎng)絡(luò)的負(fù)載始終保持在一個(gè)相應(yīng)的區(qū)間之間。通常將Knee點(diǎn)附近定義成為擁塞避免區(qū)，Knee和Cliff之間是擁塞恢復(fù)區(qū)，而Cliff之外是擁塞崩潰區(qū)間。 圖2-1 網(wǎng)絡(luò)性能與負(fù)載之間關(guān)系 2.1 擁塞產(chǎn)生的原因 擁塞的發(fā)生和的互聯(lián)網(wǎng)的設(shè)計(jì)機(jī)制有著密切關(guān)系，這種機(jī)制包括： 1) 數(shù)據(jù)包交換(packets witched

45、)網(wǎng)絡(luò) 與電路交換(circuit switched)網(wǎng)絡(luò)相比，由于包交換網(wǎng)絡(luò)對(duì)資源的利用是基于統(tǒng)計(jì)復(fù)用(statistical multiplexing)的，因此提高了資源的利用效率。但在基于統(tǒng)計(jì)復(fù)用的情況下，很難保證用的服務(wù)質(zhì)量(quality of service，QoS)，并且很容易出現(xiàn)數(shù)據(jù)包“亂序”的現(xiàn)象，對(duì)亂序數(shù)據(jù)包的處理會(huì)大大增加擁塞控制的復(fù)雜性。 2) 無(wú)連接(connectionless)網(wǎng)絡(luò) 互聯(lián)網(wǎng)的節(jié)點(diǎn)之間在發(fā)送數(shù)據(jù)之前不需要建立連接，從而簡(jiǎn)化了網(wǎng)絡(luò)的設(shè)計(jì)，網(wǎng)絡(luò)的中間節(jié)點(diǎn)上無(wú)需保留和連接有關(guān)的狀態(tài)信息。但無(wú)連接模型很難引入接納控制(admission control

46、)，在用戶需求大于網(wǎng)絡(luò)資源時(shí)難以保證服務(wù)質(zhì)量:此外，由于對(duì)數(shù)據(jù)發(fā)送源的追蹤能力很差，給網(wǎng)絡(luò)安全帶來(lái)了隱患;無(wú)連接也是網(wǎng)絡(luò)中出現(xiàn)亂序數(shù)據(jù)包的主要原因。 3) “盡力而為”的服務(wù)模型 不對(duì)網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)提供服務(wù)質(zhì)量保證。在這種服務(wù)模型下，所有的業(yè)務(wù)流被“一視同仁”的公平地競(jìng)爭(zhēng)網(wǎng)絡(luò)資源，路由器對(duì)所有的數(shù)據(jù)包都采用先來(lái)先處理(First Come First Service，F(xiàn)CFS)的工作方式，它盡最大努力將數(shù)據(jù)包包送達(dá)日的地。但對(duì)數(shù)據(jù)包傳遞的可靠性、延遲等不能提供任何保證。這很適合Email、Ftp、WWW等業(yè)務(wù)。但隨著互聯(lián)網(wǎng)的飛速發(fā)展，IP業(yè)務(wù)也得到了快速增長(zhǎng)和多樣化。特別是隨著多媒體業(yè)務(wù)

47、的興起，計(jì)算機(jī)已經(jīng)不是單純的處理數(shù)據(jù)的工具。這對(duì)互聯(lián)網(wǎng)也就相應(yīng)地提出了更高的要求。對(duì)那些有帶寬、延遲、延遲抖動(dòng)等特殊要求的應(yīng)用來(lái)說(shuō)，現(xiàn)有的“盡力而為”服務(wù)顯然是不夠的。 導(dǎo)致?lián)砣l(fā)生的原因在于網(wǎng)絡(luò)能夠提供的資源不足以滿足用戶的需求，這些資源包括緩存空間、鏈路帶寬容量和中間節(jié)點(diǎn)的處理能力等[25]。由于互聯(lián)網(wǎng)的設(shè)計(jì)機(jī)制導(dǎo)致其缺乏“接納控制”能力，因此在網(wǎng)絡(luò)資源不足時(shí)不能限制用戶數(shù)量，而只能靠降低服務(wù)質(zhì)量來(lái)繼續(xù)為用戶服務(wù)，也就是“盡力而為”的服務(wù)。主要有三方面原因： 1) 路由器緩存不足 當(dāng)多條線路上有多個(gè)數(shù)據(jù)包到達(dá)時(shí)，而且這些數(shù)據(jù)包都需要相同的輸出線路，路由器則建立一個(gè)隊(duì)列。如果路由器沒(méi)有

48、足夠的緩存來(lái)存放這些到達(dá)的數(shù)據(jù)包，那么數(shù)據(jù)包就會(huì)被丟棄。但是盲目增加緩存空間不僅不能緩解擁塞，甚至加重[26]。 2) 帶寬容量不足 低速鏈路對(duì)高速數(shù)據(jù)流的輸入也會(huì)產(chǎn)生擁塞。所有信源發(fā)送的速率必須小于或等于信道容量。所以在網(wǎng)絡(luò)低速鏈路處就會(huì)形成帶寬瓶頸，當(dāng)其滿足不了通過(guò)它的所有源端帶寬的要求時(shí)，網(wǎng)絡(luò)就會(huì)發(fā)生擁塞。 3) 處理器能力弱 處理器的處理能力弱，難以完成必要的維護(hù)工作（緩沖區(qū)排隊(duì)、更新路由表等），處理速度跟不上高速鏈路，也會(huì)產(chǎn)生擁塞。 單純地增加網(wǎng)絡(luò)資源之所以不能解決擁塞問(wèn)題，是因?yàn)閾砣旧硎且粋€(gè)動(dòng)態(tài)問(wèn)題，它不可能只靠靜態(tài)的方案來(lái)解決，而需要協(xié)議能夠在網(wǎng)絡(luò)出現(xiàn)擁塞時(shí)保護(hù)網(wǎng)絡(luò)的

49、正常運(yùn)行。 2.2 擁塞控制算法分類(lèi) 根據(jù)算法的實(shí)現(xiàn)位置，可以將擁塞控制算法分為三大類(lèi):源算法(source Algorithm)、鏈路算法(Link Algorithm)和兩者結(jié)合的算法。源算法在主機(jī)和網(wǎng)絡(luò)邊緣設(shè)備中執(zhí)行作用是根據(jù)獲得的反饋信息調(diào)整發(fā)送速率。鏈路算法在網(wǎng)絡(luò)設(shè)備(如路由器和交換機(jī))中執(zhí)行，作用是檢測(cè)網(wǎng)絡(luò)擁塞的發(fā)生，產(chǎn)生擁塞反饋信息。源算法和鏈路算法形成反饋共同實(shí)現(xiàn)擁塞控制。 2.2.1 擁塞控制源端算法 源端算法中使用最廣泛的是TCP協(xié)議中的擁塞控制算法。 1988年V.Jacobson在文獻(xiàn)[27]中指出了TCP在控制網(wǎng)絡(luò)擁塞方面的不足，并提出了“慢啟動(dòng)（slow

50、start）”算法和“擁塞避免（congestion avoidance）”算法。1990年出現(xiàn)了TCP Reno版本增加了“快速重傳”（fast retransmit）算法、“快速恢復(fù)”（fast recovery）算法，避免了網(wǎng)絡(luò)擁塞不夠嚴(yán)重時(shí)采用“慢速啟動(dòng)”算法而造成過(guò)大地減少發(fā)送窗口尺寸的現(xiàn)象，這樣TCP的擁塞控制就有慢啟動(dòng)、擁塞避免、快速重傳和快速恢復(fù)三個(gè)階段組成，這就是目前Internet上大多數(shù)機(jī)器運(yùn)行的TCP擁塞控制機(jī)制，即TCP Reno算法。 1) 慢啟動(dòng)： 這個(gè)狀態(tài)窗口的初始值是一個(gè)數(shù)據(jù)包大?。ㄈ笔?12）一個(gè)數(shù)據(jù)包被發(fā)送，當(dāng)發(fā)送端收到來(lái)自接收端的ACK響應(yīng)，窗口增

51、加1，發(fā)送端發(fā)送兩個(gè)數(shù)據(jù)包。在擁塞窗口達(dá)到最小閾值以前，發(fā)送端每收到一個(gè)確認(rèn)ACK擁塞窗口增加1。窗口的初始值大小是1，在一個(gè)和兩個(gè)RTT之后窗口大小應(yīng)該達(dá)到2和4，窗口隨RTT成指數(shù)規(guī)律增長(zhǎng)。在慢啟動(dòng)階段，用于在最短的時(shí)間內(nèi)盡可能多的使用可用帶寬資源。 2) 擁塞避免： 在擁塞避免階段，每收到一個(gè)ACK窗口增加1/cwnd，窗口成線性增加直到發(fā)送端收到3個(gè)重復(fù)的ACK。例如，在第N個(gè)RTT時(shí)，窗口大小是100，在第N+1和第N+2個(gè)RTT時(shí)，擁塞窗口應(yīng)該是101和102。在擁塞避免階段，試圖避免擁塞的發(fā)生并且盡可能地使用可用帶寬。 3) 快速重傳和快速恢復(fù)： 一個(gè)重復(fù)ACK可能是由丟

52、失的數(shù)據(jù)包或者亂序的數(shù)據(jù)包引起的，因此源端收到了重復(fù)ACK并不能確定是丟失了數(shù)據(jù)包還是發(fā)生了亂序，當(dāng)連續(xù)收到3個(gè)或3個(gè)以上的重復(fù)ACK時(shí)，源端不需等到重傳超時(shí)就重傳那個(gè)被認(rèn)為丟失的包，這就叫快速重傳。在快速重傳可能丟失的數(shù)據(jù)包之后，連接進(jìn)入到擁塞避免階段而不是慢啟動(dòng)階段，這就是快速恢復(fù)?？焖僦貍骱涂焖倩謴?fù)通常一起實(shí)現(xiàn)。當(dāng)重傳定時(shí)器超時(shí)，窗口被置為1，重新進(jìn)入慢啟動(dòng)階段?？焖僦貍骱涂焖倩謴?fù)就是在發(fā)送端收到3個(gè)或者3個(gè)以上的重復(fù)ACK，判定包丟失，慢啟動(dòng)閾值設(shè)為當(dāng)前窗口的一半而不必等待該包的計(jì)時(shí)器超時(shí)，同時(shí)接下來(lái)執(zhí)行的是擁塞避免算法而不是慢啟動(dòng)算法，當(dāng)它們恢復(fù)丟包失效時(shí)，重傳定時(shí)器超時(shí)是發(fā)現(xiàn)并恢復(fù)

53、丟包的最終機(jī)制。圖2.2為文獻(xiàn)[27]中擁塞控制窗口變化圖；圖2.3為T(mén)CP Reno擁塞控制窗口變化圖。 圖2-2 慢啟動(dòng)和擁塞避免 圖2-3 快速重傳和快速恢復(fù) 2.2.2 源端擁塞控制的研究現(xiàn)狀 為了解決高速網(wǎng)絡(luò)中TCP連接的性能問(wèn)題，研究者提出了一些不同的新的解決方案，其中對(duì)端節(jié)點(diǎn)的研究成為一個(gè)熱點(diǎn)[28]。源端節(jié)點(diǎn)的改進(jìn)主要集中在控制擁塞窗口的大小和發(fā)送速率等方面。有很多大大地提高網(wǎng)絡(luò)性能的擁塞控制端算法被提出。這些新的端算法雖然采用不同的窗口控制機(jī)制，但最終目的都是快速響應(yīng)網(wǎng)絡(luò)的擁塞，及時(shí)增加和減少擁塞窗口，提高吞吐量，達(dá)到高效率的鏈路使用等。 最近出現(xiàn)的一些新

54、協(xié)議主要有： 1) Scalable TCP(STCP) STCP協(xié)議是Tom Kelly于2003年提交給PFLDnet的以穩(wěn)定性著稱的面向高帶寬時(shí)延乘積網(wǎng)絡(luò)的新協(xié)議。STCP是個(gè)典型的MIMD（積式增加積式減少）協(xié)議[15]。它的設(shè)計(jì)思想是通過(guò)修改TCP的窗口增加和減少參數(shù)來(lái)調(diào)整發(fā)送窗口大小，STCP算法仍以丟包為擁塞信號(hào)，和傳統(tǒng)TCP擁塞控制相比，窗口增加變得更快，窗口減少變得更緩和。該算法在擁塞避免算法是收到新的包： (2-1) 收到重復(fù)三個(gè)包：

55、 （2-2） 每次丟包后窗口的調(diào)整周期為，因此源端提高一倍的發(fā)送速率需要大約70個(gè)RTT；該算法可以更好的利用歷經(jīng)短暫擁塞的高速?gòu)V域網(wǎng)的帶寬。 2) HighSpeed-TCP(HSTCP) HSTCP協(xié)議[14]是Sally Floyd等人于2003年2月遞交給IETF的為克服傳統(tǒng)TCP在高速網(wǎng)絡(luò)下的局限性而提出的一種實(shí)驗(yàn)性的高速TCP協(xié)議。傳統(tǒng)的TCP擁塞控制算法在丟包率至少的環(huán)境下才能正常工作，擁塞窗口cwnd和丟包率p之間的關(guān)系為，HSTCP算法正是從擁塞窗口和丟包率之間的約束關(guān)系出發(fā)，采用了更加侵略性的窗口增加和更加保守的窗口減少模式?？紤]到光纖鏈路的最小丟包率

56、為,為了能充分利用10Gbps的網(wǎng)絡(luò)帶寬，給出了窗口和丟包率的一個(gè)新關(guān)系,同時(shí)增加了三個(gè)參數(shù)：、、,其默認(rèn)值分別為38，83000和,若當(dāng)前窗口小于時(shí)HSTCP使用與傳統(tǒng)TCP相同的響應(yīng)函數(shù)；反之，HSTCP使用自己的響應(yīng)函數(shù)。HSTCP使用變動(dòng)的擁塞窗口調(diào)節(jié)參數(shù)，保證了在不同擁塞程度變化的網(wǎng)絡(luò)中也可正常工作，提高了算法在高速網(wǎng)絡(luò)下的魯棒性。 在擁塞避免階段，算法表述如下： 收到新的包 （2-2） 收到三個(gè)重復(fù)包 （2-3） 若當(dāng)前窗口小

57、于時(shí)=1，=0.5。 若當(dāng)前窗口大于 （2-4） （2-5） （2-6） 3) SQRT TCP SQRT TCP[28]協(xié)議是由Tomoya HATANO等人提出的新協(xié)議。算法提出的新機(jī)制可以同時(shí)提高RTT公平性和TCP友好性且在大瓶頸鏈路上還能有效的利用鏈路帶寬。它的設(shè)計(jì)思想是：收到新的包則；收到重復(fù)三個(gè)包則；、 、、 的值分別設(shè)定為1.25、15、-0.5、0.5。和HSTCP類(lèi)似，當(dāng)擁塞窗口小于高速

58、算法的閾值時(shí)，采用傳統(tǒng)TCP的擁塞控制機(jī)制；當(dāng)擁塞窗口大于高速算法的閾值，則采用SQRT TCP的擁塞控制機(jī)制。因此，SQRT TCP協(xié)議的擁塞控制機(jī)制高速環(huán)境表示如下： 收到新的包 （2-7） 收到重復(fù)三個(gè)包 （2-8） 4) Africa TCP 該協(xié)議是個(gè)自適應(yīng)的、公平的、快速增長(zhǎng)的TCP擁塞控制機(jī)制，通過(guò)使用一個(gè)延遲的度量來(lái)確定瓶頸鏈路是否有擁塞，如下表示 擁塞程度用表示

59、 （2-9） 是對(duì)網(wǎng)絡(luò)隊(duì)列延遲的一個(gè)估計(jì)。擁塞度量參數(shù)是個(gè)常量，通常設(shè)為比1大的實(shí)數(shù)，在算法中設(shè)為1.65。擁塞避免階段算法如下 當(dāng)>時(shí) （2-10） 當(dāng)>時(shí) （2-11） 表示高速環(huán)境窗口增加量。 2.2.3 擁塞控制鏈路算法 要完全依賴實(shí)現(xiàn)在源節(jié)點(diǎn)系統(tǒng)上的策略與算法是很難滿足諸如QoS這樣復(fù)雜的應(yīng)用要求的。于是開(kāi)始將部分研究注意力轉(zhuǎn)向網(wǎng)絡(luò)中的路由等中間節(jié)點(diǎn)設(shè)備，期望通過(guò)增強(qiáng)他們的

60、功能來(lái)實(shí)現(xiàn)源端無(wú)法達(dá)到的技術(shù)目標(biāo)。就擁塞控制而言，網(wǎng)絡(luò)鏈路中間節(jié)點(diǎn)有可能更及時(shí)，甚至提前準(zhǔn)確了解網(wǎng)絡(luò)的擁塞狀態(tài)，并依此實(shí)施有效的資源管理策略，使網(wǎng)絡(luò)能有效地避免擁塞或盡早從嚴(yán)重的擁塞狀態(tài)中恢復(fù)過(guò)來(lái)。對(duì)路由器功能的擴(kuò)展要受繼承性和延續(xù)性的限制，否則將影響技術(shù)的實(shí)用性。事實(shí)上，現(xiàn)有的路由器擴(kuò)展功能，主要包括調(diào)度和隊(duì)列/緩存管理，并沒(méi)有與Internet將流狀態(tài)信息保存在源端的早期設(shè)計(jì)理念相沖突。調(diào)度(scheduler)直接管理輸出鏈路的帶寬資源，而隊(duì)列/緩存管理通過(guò)控制緩存與隊(duì)列的占有間接影響帶寬的分配。 管理隊(duì)列長(zhǎng)度的傳統(tǒng)方法是對(duì)每個(gè)隊(duì)列設(shè)置一個(gè)最大值(以包為單位)，然后接受包進(jìn)入隊(duì)列直到隊(duì)

61、長(zhǎng)達(dá)到最大值，接下來(lái)到達(dá)的包就要被拒絕進(jìn)入隊(duì)列直到隊(duì)長(zhǎng)下降，這種技術(shù)也就是傳統(tǒng)的“尾丟棄”(Drop-Tall)算法。由于這種方法是在隊(duì)列滿了之后被迫丟包，因此稱為被動(dòng)式隊(duì)列管理(PQM)，雖然Drop-Tail算法在當(dāng)前Internet上得到了廣泛的使用，但其存在幾個(gè)重要問(wèn)題[29]。 1) “死鎖”(lock-out)現(xiàn)象: 在某些情況下，由于同步或其他定時(shí)作用的結(jié)果，Drop-Tail算法會(huì)讓某個(gè)流或者少數(shù)幾個(gè)流獨(dú)占隊(duì)列空間，阻止其他流的包進(jìn)入隊(duì)列。 2) 滿隊(duì)列(full queues)問(wèn)題: 由于Drop-Tail只有在隊(duì)列滿時(shí)才會(huì)發(fā)出擁塞信號(hào)，因此會(huì)使得隊(duì)列在相當(dāng)長(zhǎng)時(shí)間內(nèi)處

62、于充滿〔或幾乎充滿)的狀態(tài)。而隊(duì)列管理最重要的目標(biāo)之一就是降低穩(wěn)定狀態(tài)下隊(duì)列的長(zhǎng)度，因?yàn)槎说蕉说难舆t主要就是由于在隊(duì)列中排隊(duì)等待造成的。 3) 全局同步(global synchronization)問(wèn)題: 由于Internet上到達(dá)路由器的包往往是突發(fā)的。如果隊(duì)列是滿的或者幾乎是滿的，就會(huì)導(dǎo)致在短時(shí)間內(nèi)連續(xù)大量的丟包。而TCP流具有自適應(yīng)特性，源端發(fā)現(xiàn)包丟失就急劇地減小發(fā)送窗口，包到達(dá)速率就迅速下降，于是網(wǎng)絡(luò)擁塞得以解除，但源端得知網(wǎng)絡(luò)不再擁塞后又開(kāi)始增加發(fā)送速度，最終又造成網(wǎng)絡(luò)擁塞。 在當(dāng)前的Internet上，丟包是對(duì)端節(jié)點(diǎn)進(jìn)行擁塞通知的主要機(jī)制，解決被動(dòng)式隊(duì)列管理問(wèn)題的方法便是在

63、隊(duì)列滿之前丟包，這樣端節(jié)點(diǎn)便能在隊(duì)列溢出前對(duì)擁塞作出反應(yīng)。這種方法便稱為主動(dòng)式隊(duì)列管理(AQM)。它使得路由器能夠控制在什么時(shí)候丟包和丟多少包，從而有效地管理隊(duì)列長(zhǎng)度，以支持端到端的擁塞控制。AQM的主要優(yōu)點(diǎn)是： 1) 減少網(wǎng)關(guān)的報(bào)文丟失 使用AQM可以保持較小的隊(duì)列長(zhǎng)度，從而增強(qiáng)網(wǎng)絡(luò)中間節(jié)點(diǎn)容納突發(fā)流量的能力。 2) 減小報(bào)文通過(guò)網(wǎng)關(guān)的延遲 減小平均隊(duì)列長(zhǎng)度可以有效地減小報(bào)文在網(wǎng)絡(luò)設(shè)備中的排隊(duì)延遲。 3) 避免lock-out行為的發(fā)生[30] 2.2.4 鏈路擁塞控制研究現(xiàn)狀 鏈路算法的研究目前集中在主動(dòng)隊(duì)列管理(Active Queue Management，簡(jiǎn)稱AQM)。

64、和傳統(tǒng)的“隊(duì)尾丟棄(Drop-Tail)”相比，AQM在網(wǎng)絡(luò)設(shè)備的緩沖溢出之前就丟棄或標(biāo)記報(bào)文[31]。AQM的代表算法是RED(Random Early Detection)[8]。研究表明，RED算法比Drop-Tail具有更好的性能。在RFC2309中，強(qiáng)烈推薦使用RED作為今后的標(biāo)準(zhǔn)。但是進(jìn)一步研究發(fā)現(xiàn)，RED的性能對(duì)算法的參數(shù)設(shè)置十分敏感，至今沒(méi)有在Internet中得到廣泛的使用。 最近出現(xiàn)的一些新的AQM算法主要有： 1) 隨即早期檢測(cè)算法RED 最早提出的AQM算法是隨機(jī)早期檢測(cè)(RED)算法，也是目前最常用的一種AQM算法。RED的基本思想是路由器通過(guò)監(jiān)控隊(duì)列的平均長(zhǎng)度

65、來(lái)探測(cè)擁塞，一旦發(fā)現(xiàn)擁塞逼近，就隨機(jī)地選擇源端來(lái)通知擁塞，使它們?cè)陉?duì)列溢出之前降低發(fā)送數(shù)據(jù)速率，以緩解網(wǎng)絡(luò)擁塞。RED算法主要包括兩步，首先計(jì)算平均隊(duì)列長(zhǎng)度，然后計(jì)算丟棄包的概率。 RED在計(jì)算平均隊(duì)長(zhǎng)時(shí)，采用了類(lèi)似低通濾波器帶權(quán)值的方法 （2-12） 其中，為權(quán)值，為采樣測(cè)量時(shí)實(shí)際隊(duì)列長(zhǎng)度。從而“過(guò)濾”掉由于Internet數(shù)據(jù)的突發(fā)性導(dǎo)致的短期隊(duì)長(zhǎng)變換，盡量反映長(zhǎng)期的擁塞變化。權(quán)值相當(dāng)于低通濾波器的時(shí)間常數(shù)，它決定了路由器對(duì)輸入流量變化的反應(yīng)程度，計(jì)算平均隊(duì)長(zhǎng)的目的就是為了反映擁塞程度并據(jù)此來(lái)計(jì)算丟包概率。

66、 RED有兩個(gè)與隊(duì)列長(zhǎng)度相關(guān)的闡值：和。當(dāng)有數(shù)據(jù)包達(dá)到路由器時(shí)，RED計(jì)算出平均隊(duì)長(zhǎng)，然后計(jì)算丟包率。 若 （2-13） 是最大丟包率。再對(duì)丟包率做進(jìn)一步調(diào)整： （2-14） 是上一次丟包開(kāi)始到現(xiàn)在連續(xù)進(jìn)入隊(duì)列的包的數(shù)量。 2) 自適應(yīng)RED算法ARED 自適應(yīng)RED算法(adaptive RED，ARED)[9]。ARED的基本思想就是通過(guò)檢查平均隊(duì)長(zhǎng)的變化來(lái)決定RED是應(yīng)更激進(jìn)還是更保守，從而盡量保持平均隊(duì)長(zhǎng)在和。之間。 具體地說(shuō)，如果平均隊(duì)長(zhǎng)是在附近振蕩，說(shuō)明擁塞控制太激進(jìn)了，那么就減小 （2-15） 如果在附近振蕩，說(shuō)明擁塞控制太保守了，那么就增大 （2-16） ARED是對(duì)RED改動(dòng)很小的一種算法，它保留了RED的基本結(jié)構(gòu)，只需調(diào)節(jié)參數(shù)，從而保持平均隊(duì)長(zhǎng)在和之間，消除了RED的隊(duì)列延時(shí)