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

碩士學(xué)位論文 論文題目 高速網(wǎng)絡(luò)擁塞控制研究 英文題目 Research on Congestion Control for High-Speed Network 碩士研究生 指導(dǎo)教師 學(xué)科專業(yè) 計(jì)算機(jī)軟件與理論 論文提交日期 2009年4月 論文答辯日期 論文評閱人 答辯委員會主席 2009 年 4 月 10 日Abstract摘 要隨著高速網(wǎng)絡(luò)應(yīng)用的日益廣泛，擁塞控制機(jī)制的研究變得越來越重要。擁塞控制至少應(yīng)該包含兩部分：首先是要有源端算法響應(yīng)路徑中的擁塞，動態(tài)的調(diào)節(jié)數(shù)據(jù)發(fā)送速率;另一方面，要有一個中間節(jié)點(diǎn)管理機(jī)制能有效地預(yù)測、監(jiān)測路徑中的擁塞程度，通過顯式或隱式的方法在擁塞發(fā)生前及時警告源端。目前研究適合高速網(wǎng)絡(luò)的TCP擁塞控制機(jī)制成為一個新的研究熱點(diǎn)，一些研究者提出了一些新的算法如：STCP，H-TCP等。這些協(xié)議都是通過修改發(fā)送窗口的增加減小模式來提高TCP在高速網(wǎng)絡(luò)中的性能。其中TCPW是以可用帶寬測量為基礎(chǔ)的新的TCP協(xié)議，對原有TCP協(xié)議改動較小，具有較好RTT公平性和較好的TCP友好性，在真實(shí)網(wǎng)絡(luò)中易于實(shí)現(xiàn)，但是TCPW仍存在一些性能缺陷。由于TCPW窗口增長仍采用線性增加模式，因此不能像其他協(xié)議一樣快速獲得更大的發(fā)送窗口，而且在該算法的慢啟動階段仍然采用指數(shù)增長模式，從而導(dǎo)致大量突發(fā)數(shù)據(jù)的產(chǎn)生，造成擁塞。中間節(jié)點(diǎn)控制由路由器擁塞控制算法來實(shí)現(xiàn)，主動式隊(duì)列管理機(jī)制（AQM）是IEFT推薦的基于路由器擁塞控制關(guān)鍵技術(shù)，它和TCP端到端的擁塞控制相結(jié)合，是解決目前網(wǎng)絡(luò)擁塞控制問題的一個主要手段。RED算法是AQM的一個典型，但其在算法穩(wěn)定性和參數(shù)敏感性方面存在缺陷。本文基于以上兩個算法，開展了以下三個方面的工作。首先對TCPW算法進(jìn)行改進(jìn)，主要集中在以下兩點(diǎn)：一是在慢啟動階段發(fā)送窗口較原有算法能較快的到達(dá)10個包左右，之后窗口增長速度較原有算法有所減慢，這樣有利于短流傳輸和避免突發(fā)數(shù)據(jù)產(chǎn)生，從而減緩擁塞；二是在擁塞避免階段采用基于當(dāng)前擁塞窗口大小的先快后慢的非線性增長方式，使之更適合于高速環(huán)境。通過建立新算法的數(shù)學(xué)模型分析其穩(wěn)定性、RTT公平性和對TCP友好性，在此基礎(chǔ)上分別對以上兩點(diǎn)改進(jìn)采用NS2仿真方法加以驗(yàn)證，發(fā)現(xiàn)算法較原有算法在高速環(huán)境下有更好的吞吐量和更有利于短流數(shù)據(jù)傳輸。另外本文在分析RED算法基礎(chǔ)上，提出了一種新的改進(jìn)型AQM算法DRED算法。DRED相對RED算法，能夠動態(tài)調(diào)整參數(shù)，并且采用非線性函數(shù)代替原有的丟包率計(jì)算方法。通過動態(tài)調(diào)整來調(diào)整向源端發(fā)送擁塞通知的速率，維持隊(duì)列的穩(wěn)定；通過新丟包率計(jì)算方式，提高緩沖的利用率和使隊(duì)列長度盡量穩(wěn)定于期望值附近。最后通過仿真來驗(yàn)證新算法更適應(yīng)網(wǎng)絡(luò)流量的變化，保持隊(duì)列長度的穩(wěn)定和丟包率的穩(wěn)定，從而提高了網(wǎng)絡(luò)鏈路利用率。關(guān)鍵詞：高速網(wǎng)； 擁塞控制； TCPW； RED 52AbstractAbstractWith 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 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 begin 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 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, Congestion window of TCPW is based on additive increase of linear mode. So, in high-speed networks it cant 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 probability 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 the 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, 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 performance 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 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 interpolations size, 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 simulations 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 words: high-speed networks; congestion control; TCPW; RED目錄目錄摘 要IAbstractII第一章 緒 論11.1 研究背景11.2 研究現(xiàn)狀31.3 主要研究工作51.4 論文的內(nèi)容及安排6第二章 擁塞控制算法綜述82.1 擁塞產(chǎn)生的原因82.2 擁塞控制算法分類102.2.1 擁塞控制源端算法102.2.2 源端擁塞控制的研究現(xiàn)狀112.2.3 擁塞控制鏈路算法142.2.4 鏈路擁塞控制研究現(xiàn)狀152.3 擁塞控制算法的評價標(biāo)準(zhǔn)182.3.1 穩(wěn)定性分析182.3.2 公平性分析192.3.3 友好性分析202.4 小結(jié)20第三章 TCP Westwood擁塞控制算法改進(jìn)213.1 引言213.2 TCPW算法的分析223.2.1 TCPW算法的簡介223.2.2 TCPW算法優(yōu)點(diǎn)233.2.3 TCPW算法存在的不足233.3 改進(jìn)的擁塞控制算法NLTCPW243.3.1 擁塞避免階段改進(jìn)253.3.2 慢啟動階段改進(jìn)253.3.3 NLTCPW算法的數(shù)學(xué)模型263.3.4 仿真環(huán)境下NLTCPW算法的吞吐量性能分析293.3.5 NLTCPW算法RTT公平性實(shí)驗(yàn)323.3.6 NLTCPW算法短流數(shù)據(jù)傳輸性能分析323.4 小結(jié)34第四章 RED算法改進(jìn)354.1 一種新的自適應(yīng)RED算法DRED算法354.1.1 RED算法概述354.1.2 RED算法的優(yōu)點(diǎn)364.1.3 RED算法存在的不足364.1.4 DRED算法384.2 DRED算法性能分析404.3 小結(jié)45第五章 結(jié)論及未來的工作465.1結(jié)論465.2 未來的工作47致 謝48攻讀碩士學(xué)位期間從事的主要科研工作及發(fā)表的論文49參考文獻(xiàn)50第一章 緒論第一章 緒 論1.1 研究背景近年來隨著信息技術(shù)迅速發(fā)展，以互聯(lián)網(wǎng)為代表的信息網(wǎng)絡(luò)已經(jīng)逐漸滲透到當(dāng)今社會的各個領(lǐng)域，成為了國家進(jìn)步和社會發(fā)展的重要支柱，以及知識經(jīng)濟(jì)的基礎(chǔ)載體和支撐環(huán)境，它的重要性就如同鐵路和高速公路的蓬勃發(fā)展給工業(yè)社會帶來了廣泛而深遠(yuǎn)的影響一樣，必將成為21世紀(jì)全球最重要的基礎(chǔ)設(shè)施之一。就目前的現(xiàn)狀和未來的發(fā)展而言，下一代互聯(lián)網(wǎng)的骨干帶寬必將呈現(xiàn)指數(shù)型增長。下一代互聯(lián)網(wǎng)建設(shè)與發(fā)展的各種趨勢表明：大規(guī)模的高速網(wǎng)絡(luò)試驗(yàn)環(huán)境已經(jīng)形成，未來幾年內(nèi)，互聯(lián)網(wǎng)骨干將全面升級到支持近10Gbps的高速鏈路，而且很有可能持續(xù)增長。但是，雖然下一代互聯(lián)網(wǎng)的骨干帶寬呈現(xiàn)指數(shù)性的增長，實(shí)踐中上述海量數(shù)據(jù)傳輸業(yè)務(wù)的用戶卻并沒有切身感受到網(wǎng)絡(luò)帶寬劇增所帶來的好處，于是人們開始懷疑高速網(wǎng)絡(luò)中傳輸協(xié)議的性能。這是由于TCP/IP協(xié)議在高速網(wǎng)絡(luò)中確實(shí)存在效率問題1。因此研究適應(yīng)于高速網(wǎng)絡(luò)的擁塞控制算法成了網(wǎng)絡(luò)研究的新熱點(diǎn)。目前，Internet上用戶和應(yīng)用的數(shù)量都在迅速增長，當(dāng)多個用戶對網(wǎng)絡(luò)的需求總量大于網(wǎng)絡(luò)實(shí)際傳輸能力時，必然會導(dǎo)致網(wǎng)絡(luò)擁塞的發(fā)生。雖然擁塞源于資源短缺，但增加資源并不能避免擁塞的發(fā)生，有時甚至?xí)又負(fù)砣潭?。所以選擇和引進(jìn)更多、更合理的擁塞控制機(jī)制對網(wǎng)絡(luò)的高效穩(wěn)定運(yùn)行是至關(guān)重要的。隨著應(yīng)用需求的豐富和技術(shù)的發(fā)展，研究者開始認(rèn)識到想完全依賴實(shí)現(xiàn)在終端系統(tǒng)上的策略與算法很難滿足越來越多的復(fù)雜應(yīng)用需求。于是，人們把注意力轉(zhuǎn)向網(wǎng)絡(luò)中的路由器等中間節(jié)點(diǎn)設(shè)備，期望通過增強(qiáng)它們的功能來實(shí)現(xiàn)主機(jī)端無法達(dá)到的目標(biāo)網(wǎng)。就擁塞控制而言，網(wǎng)絡(luò)中間節(jié)點(diǎn)有可能更及時，甚至可以提前準(zhǔn)確了解網(wǎng)絡(luò)的擁塞狀態(tài)，并依此實(shí)施有效的資源管理策略，使網(wǎng)絡(luò)能有效地避免擁塞，或盡早從嚴(yán)重的擁塞狀態(tài)中恢復(fù)過來。當(dāng)然，對路由器功能的擴(kuò)展要受繼承性和延續(xù)性的限制，否則將影響技術(shù)的實(shí)用性。事實(shí)上，現(xiàn)有的路由器擴(kuò)展功能，主要包括調(diào)度和隊(duì)列/緩存管理。調(diào)度(Scheduling)直接管理下次發(fā)哪個分組和分配各個流的帶寬。而隊(duì)列/緩存算法管理路由器緩沖區(qū)中分組隊(duì)列的長度，即在必要或適當(dāng)?shù)臅r候丟掉一些分組。因此根據(jù)擁塞控制算法實(shí)現(xiàn)的位置不同主要分為兩大類：源端控制和鏈路控制，源算法在主機(jī)和網(wǎng)絡(luò)邊緣設(shè)備中的執(zhí)行作用主要是根據(jù)獲得的反饋信息調(diào)整發(fā)送速率。鏈路算法在網(wǎng)絡(luò)設(shè)備(如路由器和交換機(jī))中執(zhí)行，作用是檢測網(wǎng)絡(luò)擁塞的發(fā)生，產(chǎn)生擁塞反饋信息。源算法和鏈路算法形成反饋，共同實(shí)現(xiàn)擁塞控制，兩者形成的反饋系統(tǒng)共同形成了擁塞控制系統(tǒng)，所以必須在這兩方面同時進(jìn)行研究和綜合。在實(shí)際部署中要考慮效率和費(fèi)用比的問題同時又要要求源端控制和鏈路控制必須相互獨(dú)立，一個對原有系統(tǒng)改動過大的擁塞控制算法不利于部署。比如XCP3(eXplicit Control Protocol)，是美國麻省理工和伯克利針對高帶寬時延乘積網(wǎng)絡(luò)提出的一個Internet擁塞控制的新體系結(jié)構(gòu)，它是將端節(jié)點(diǎn)和路由器相結(jié)合完成擁塞控制的執(zhí)行模式。XCP協(xié)議其路由器算法主要由有效控制算法（EC）和公平性控制算法（FC）構(gòu)成。EC僅考慮鏈路的總流量，而不考慮單條流的流量及公平性問題。FC實(shí)現(xiàn)目標(biāo)是將EC計(jì)算出來的總的反饋量在包層次上公平地分配給每條流。FC以包為單位來分配EC計(jì)算出的總的反饋量。在端節(jié)點(diǎn)數(shù)據(jù)包結(jié)構(gòu)中增加了cwnd、RTT估計(jì)和feedback三個域。發(fā)送端發(fā)送數(shù)據(jù)包時使用feedback域請求希望得到的擁塞窗口調(diào)整的變化量，數(shù)據(jù)包途經(jīng)的路由器根據(jù)當(dāng)時網(wǎng)絡(luò)可用帶寬的狀況修改feedback域的值。當(dāng)數(shù)據(jù)包到達(dá)接收端時，feedback域保留的是該數(shù)據(jù)包途徑的各路由器允許發(fā)送端可以增加的帶寬的最小值或要求發(fā)送端需要減少的帶寬的最大值，然后接收端通過ACK包將feedback域的值反饋給發(fā)送端，最終發(fā)送端按照反饋調(diào)整隨后的發(fā)送速率。但是XCP的關(guān)鍵算法全部在路由器內(nèi)實(shí)現(xiàn)，在實(shí)際網(wǎng)絡(luò)中要建造如此強(qiáng)大功能的路由器的造價是十分昂貴的；同時若端節(jié)點(diǎn)或中間路由節(jié)點(diǎn)其中一個不支持此協(xié)議，算法將失效；因此XCP在實(shí)際網(wǎng)絡(luò)中難以實(shí)現(xiàn)和部署。擁塞控制算法的分布性、網(wǎng)絡(luò)的復(fù)雜性和對擁塞控制算法性能要求等使擁塞控制算法的設(shè)計(jì)具有很高的難度Error! Reference source not found.，其主要表現(xiàn)如下：1) 算法的分布性擁塞控制算法的實(shí)現(xiàn)分布在多個網(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對報(bào)文的正確傳輸不提供保證，算法必須處理報(bào)文丟失、亂序到達(dá)等情況。3) 算法的性能要求。擁塞控制算法對性能有很高的要求，包括算法的公平性、效率、穩(wěn)定性和收斂性等。某些性能目標(biāo)之間存在矛盾，在算法設(shè)計(jì)時需要進(jìn)行權(quán)衡。4) 算法的開銷 擁塞控制算法必須盡量減少附加的網(wǎng)絡(luò)流量，特別是在擁塞發(fā)生時。在使用反饋式的控制機(jī)制時，這個要求增加了算法設(shè)計(jì)的困難。算法還必須盡量降低在網(wǎng)絡(luò)節(jié)點(diǎn)（特別是網(wǎng)關(guān)）上的計(jì)算復(fù)雜性。1.2 研究現(xiàn)狀目前對網(wǎng)絡(luò)擁塞控制的研究主要從以下兩個方面進(jìn)行：首先是解決源端的算法，通過依靠動態(tài)的調(diào)節(jié)源端數(shù)據(jù)發(fā)送速率，及時能響應(yīng)路徑中的擁塞；另一方面是解決鏈路算法，通過對中間節(jié)點(diǎn)的有效管理機(jī)制能，不斷地預(yù)測并監(jiān)測路徑中的擁塞程度，通過顯式或隱式的方法在擁塞發(fā)生前及時警告源端，在擁塞發(fā)生之后抑制源端的發(fā)送速率以超出中間節(jié)點(diǎn)轉(zhuǎn)發(fā)速率的速度發(fā)送報(bào)文分組。傳統(tǒng)的源端TCP擁塞控制算法使得當(dāng)前的Internet網(wǎng)絡(luò)獲得了巨大的成功，但是近幾年來人們越來越清楚的認(rèn)識到傳統(tǒng)的TCP擁塞控制機(jī)制主要采用了慢啟動機(jī)制和AIMD（和式增加積式減少）的擁塞避免機(jī)制，它在高速長距離網(wǎng)絡(luò)中的性能已達(dá)到瓶頸4。文獻(xiàn)4分析了傳統(tǒng)TCP在高速長距離網(wǎng)絡(luò)中不能達(dá)到高吞吐量的主要的原因表現(xiàn)在如下幾個方面：1) 現(xiàn)存的擁塞控制機(jī)制對擁塞反應(yīng)性比較差TCP在高速長距離網(wǎng)絡(luò)中對包丟失的敏感程度遠(yuǎn)遠(yuǎn)高于局域網(wǎng)或者普通的廣域網(wǎng)，這主要?dú)w因于它的擁塞避免算法中基于AIMD（和式增加積式減少）的窗口增加減少原則。在它的擁塞避免算法中每一個往返時延（RTT）至多增加一個數(shù)據(jù)包的小尺寸來增加擁塞窗口（和式增加），而單個包丟失在高速長距離網(wǎng)絡(luò)中的影響是非常普遍的的，當(dāng)一個TCP連接一旦被探測到有數(shù)據(jù)包丟失時，立刻要將它的擁塞窗口減少一半（積式減少），這需要花去幾百毫秒甚至幾秒才能重新恢復(fù)到原來的窗口大小，這種緩慢的窗口恢復(fù)速度會直接導(dǎo)致吞吐率不高，無法充分利用帶寬。相反窗口減小又顯得過于激烈，造成了網(wǎng)絡(luò)流量的巨大震蕩，同時也會降低網(wǎng)絡(luò)的吞吐量。而另一方面慢啟動也會造成TCP在網(wǎng)絡(luò)中的性能下降，但相對而言這方面的影響比擁塞避免階段要小很多，這是因?yàn)樵赥CP連接中往往是通過收到三個重復(fù)ACK而不是超時來檢測丟包，所以TCP連接在擁塞避免階段比慢啟動階段要花費(fèi)更多的時間。2) 對數(shù)據(jù)包丟失的解釋不同數(shù)據(jù)包在傳輸過程中可能會由于緩沖區(qū)溢出或者傳輸介質(zhì)的出錯而引起包丟失或者包損壞的情況，傳統(tǒng)TCP假定鏈路錯誤造成的損失是可以忽略不計(jì)的，但是在高速網(wǎng)絡(luò)中，當(dāng)數(shù)據(jù)傳輸?shù)乃俾瘦^高時，鏈路錯誤是不能被忽略的，由數(shù)據(jù)鏈路錯誤引起的丟包和由網(wǎng)絡(luò)擁塞引起的丟包的可能性是相同的，所以在高速網(wǎng)絡(luò)中不能籠統(tǒng)的認(rèn)為只要是分組丟失就一定由網(wǎng)絡(luò)擁塞引起的。3) 擁塞窗口和丟包率之間存在固定的函數(shù)關(guān)系在TCP的擁塞控制算法中窗口大小w與丟包率p之間的約束關(guān)系為5，由此可見，在這種固定的關(guān)系約束下，要保持大的擁塞窗口需要極小的丟包率，即使丟包率能達(dá)到這個要求，對于發(fā)送端來說，這也是一個極為不精確的反饋；所以在最后TCP的擁塞控制算法不得不引入丟包來估計(jì)帶寬，但是隨著帶寬時延乘積的增加，在實(shí)際網(wǎng)絡(luò)中該平衡狀態(tài)難以實(shí)現(xiàn)，從而使網(wǎng)絡(luò)帶寬不能得到有效的利用。4) 擁塞避免階段傳統(tǒng)TCP在連續(xù)收到三個重復(fù)ACK，才開始重傳并且減少慢啟動閥值和擁塞窗口。但在擁塞嚴(yán)重的情況下，第二個或第三個重復(fù)ACK包很可能不會到達(dá)源端。這一方面增加了網(wǎng)絡(luò)重傳丟失數(shù)據(jù)包的時間，另一方面會造成不必要的重傳，而轉(zhuǎn)入不必要的慢啟動階段。從而降低了系統(tǒng)吞吐量、增加了延時、影響了系統(tǒng)的性能。這些對于高速網(wǎng)絡(luò)來說都是非常不利的。5) 過長的恢復(fù)周期每個TCP連接發(fā)生丟包后窗口減半，然后再恢復(fù)到原來的窗口大小需要花去很長時間。就單個TCP連接而言，它的調(diào)整周期和連接回路的往返時間及擁塞窗口值大小有關(guān)，即調(diào)整周期等于擁塞窗口大小的二分之一乘以一個窗口數(shù)據(jù)傳輸?shù)耐禃r間。特別是在高帶寬網(wǎng)絡(luò)中，傳統(tǒng)TCP在一次丟包后要經(jīng)過幾個甚至幾十個RTT才能恢復(fù)到原來的窗口大小。要達(dá)到100%完全利用鏈路的理想狀態(tài)那更是不可能實(shí)現(xiàn)的。從以上分析可以看出，造成TCP擁塞控制算法在高速網(wǎng)絡(luò)中性能不好的主要原因是其擁塞控制機(jī)制不適應(yīng)于高速網(wǎng)絡(luò)，目前已經(jīng)有一些學(xué)者提出了多種解決方案，主要分為四類：1)基于丟失的算法;2)基于延遲的算法;3)基于丟失和延遲相混合的算法;4)基于顯示擁塞指示的算法。傳統(tǒng)TCP是典型的基于丟失的算法；FAST TCP5將延遲作為擁塞指示的算法,Africa TCP6用隊(duì)列延遲和包丟失作為網(wǎng)絡(luò)的擁塞指示。在正常的工作環(huán)境下，擁塞窗口經(jīng)過一個RTT被更新且依賴于平均RTT的估計(jì)。TCP Africa算法就是一個基于丟失和延遲的“雙模式”算法。XCP3屬于最后一類，它需要通過從網(wǎng)絡(luò)環(huán)境中獲取的指示信號來推斷網(wǎng)絡(luò)是否發(fā)生擁塞，這種算法的配置需要和路由器同時進(jìn)行操作?；诼酚善鞯膿砣刂疲存溌房刂扑惴ǎ┲饕峭ㄟ^對其隊(duì)列進(jìn)行管理來實(shí)現(xiàn)的，目前的隊(duì)列管理主要還是被動式隊(duì)列管理(Passive Queue Management，PQM)。本質(zhì)上PQM并沒有參與到網(wǎng)絡(luò)擁塞管理中去，只是在隊(duì)列溢出的情況下被動地丟包。若路由器上使用主動式隊(duì)列管(Active Queue Management，AQM)機(jī)制來控制在什么時候丟多少包，將有效地管理隊(duì)列長度，以支持端到端的擁塞控制。其基本思想是通過監(jiān)控路由器輸出端口隊(duì)列的平均長度來探測擁塞。一旦發(fā)現(xiàn)擁塞逼近，就隨機(jī)地選擇時機(jī)對源端進(jìn)行通知擁塞，使它們在隊(duì)列溢出導(dǎo)致丟包之前降低發(fā)送數(shù)據(jù)速率，從而緩解網(wǎng)絡(luò)擁塞。主要的AQM算法有RED8、ARED9、FRED10 、BLUE11 、WRED12、PI13、AVQ14和 REM 15。其中RED、ARED和FRED屬于一類，都是隨機(jī)早期檢測算法。PI是基于控制理論提出一種算法，PI控制算法可以有效消除“穩(wěn)態(tài)誤差”，但同時也會減慢系統(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)可以采取的動作包括“丟棄”（Dropping）和“標(biāo)記”（Marking）。“丟棄”是現(xiàn)有系統(tǒng)都支持的一種操作，而“標(biāo)記”的方法，可經(jīng)“顯示”的通知源端系統(tǒng)擁塞的發(fā)生，比較而言“標(biāo)記”方法性能更好。隨著“顯示擁塞通知”(ECN)的標(biāo)準(zhǔn)化和廣泛采用，將有越來越多的網(wǎng)關(guān)支持“標(biāo)記”的策略。從實(shí)際的應(yīng)用來看，路由器廠商紛紛在自己的產(chǎn)品中支持RED算法，如Ciseo7500等系列路由器，Juniper的M40、M80等；在Differv的業(yè)務(wù)框架下，由RED演化出來的RIO(RED with IN/OUT)成為提供確保服務(wù)(Assured Services)的基本算法。由于RED算法的有效性目前己被廣泛使用在網(wǎng)絡(luò)隊(duì)列管理中來提高系統(tǒng)的綜合性能。隨著高速網(wǎng)絡(luò)的發(fā)展，擁塞控制算法的研究由于其巨大的復(fù)雜性，已不滿足于以往的基于主觀方法提出解決方案再進(jìn)行模擬分析擁塞控制算法性能的思路，而必須建立起其理論上的框架，用控制理論和優(yōu)化理論等現(xiàn)代分析方法來研究網(wǎng)絡(luò)的動力學(xué)模型和特性，揭示Internet網(wǎng)絡(luò)形成擁塞現(xiàn)象的物理機(jī)制，分析各種算法以及算法的組合的性能，發(fā)展更有效的擁塞控制算法，以滿足人們對網(wǎng)絡(luò)快速增長的需求?？偟膩碚f，高速網(wǎng)絡(luò)擁塞控制的研究從最初單純解決TCP的低效問題，到圍繞公平性、穩(wěn)定性以及收斂性等方面開展了一系列更深入的研究，但是到目前為此，在該研究領(lǐng)域仍然存在很多開放性問題，其中作者認(rèn)為最為突出的一點(diǎn)是目前的多數(shù)研究沒有充分強(qiáng)調(diào)模型分析的重要性，缺乏具有總結(jié)性結(jié)論和定律的歸納與描述。同時在擁塞控制機(jī)制和算法的設(shè)計(jì)上過分依賴于基于經(jīng)驗(yàn)的啟發(fā)式設(shè)計(jì)結(jié)合典型、有限和局部仿真試驗(yàn)驗(yàn)證的設(shè)計(jì)方法，得到的算法往往是靜態(tài)的和準(zhǔn)靜態(tài)的，不能適應(yīng)快速變化的動態(tài)網(wǎng)絡(luò)化環(huán)境。高速網(wǎng)絡(luò)環(huán)境下?lián)砣刂扑惴ǖ膬?yōu)化設(shè)計(jì)還存在很大的研究空間。1.3 主要研究工作隨著Internet的發(fā)展，它的傳輸擁塞控制機(jī)制必須保持有效性。技術(shù)的趨勢表明越來越多的高帶寬鏈路將應(yīng)用到互聯(lián)網(wǎng)絡(luò)中，高速網(wǎng)絡(luò)擁塞控制協(xié)議的設(shè)計(jì)分類兩類:修改TCP協(xié)議、終端與路由器聯(lián)合的協(xié)議。針對高速網(wǎng)絡(luò)的特點(diǎn)基于TCP協(xié)議采用不同的機(jī)制進(jìn)行改進(jìn)而來的新協(xié)議包括前面提到的FAST TCP在內(nèi)的諸如：High-Speed TCP16 、Scalable TCP17、BIC18、CUBIC19和H-TCP20。這些協(xié)議設(shè)計(jì)的主要目的是在高速網(wǎng)絡(luò)下能快速的獲得高的穩(wěn)定的吞吐量，從而提高高速網(wǎng)絡(luò)鏈路的利用率。本文首先分析TCPW21算法在高速網(wǎng)環(huán)境下，慢啟動和擁塞避免階段存在問題提出一種改進(jìn)NLTCPW算法。NLTCPW將TCPW在高帶寬時延積網(wǎng)絡(luò)中窗口增加采用線性方式改為一種非線性增長方式，使之窗口增加先快后慢，窗口維持在一個較大的水平，從而獲得更好的帶寬利用率；慢啟動階段窗口開始階段較快的增加到10（包），超過10（包）后減緩增長速度，這樣可以提高WEB流的傳輸，降低網(wǎng)絡(luò)丟包率，降低網(wǎng)絡(luò)突發(fā)數(shù)據(jù)量；建立NLTCPW的數(shù)學(xué)模型，從理論上對NLTCPW的穩(wěn)定性，RTT公平性、TCP友好性進(jìn)行分析，利用仿真工具在網(wǎng)絡(luò)吞吐量、WEB流數(shù)據(jù)傳輸、丟包率等方面對NLTCPW和TCPW進(jìn)行了比較分析，結(jié)果表明NLTCPW相對TCPW在保持原有算法優(yōu)點(diǎn)情況下提高網(wǎng)絡(luò)吞吐量和其在傳輸短流數(shù)據(jù)方面效率。由于RED算法是IEFT推薦在路由器上的算法，所以研究RED算法實(shí)用性更好且易于部署,RED算法存在的一個主要問題就是其參數(shù)是靜態(tài)配置的，而互聯(lián)網(wǎng)是基于帶寬統(tǒng)計(jì)復(fù)用的，一條鏈路上往往有很多活躍流，并且流量變化很大，RED算法不能適應(yīng)這種變化導(dǎo)致其在很多情況下性能會大大下降。我們的研究目的就是對RED算法的參數(shù)配置進(jìn)行改進(jìn)，使其能夠根據(jù)流量的變化來自動配置參數(shù)，從而保證性能的穩(wěn)定。另一方面修改RED的丟包率計(jì)算策略，由原來的線性計(jì)算變?yōu)榉蔷€性，這樣有利于緩沖隊(duì)列資源的有效使用和隊(duì)列長度的穩(wěn)定。1.4 論文的內(nèi)容及安排第一章緒論介紹網(wǎng)絡(luò)擁塞控制的研究概況及研究背景，最后對本文的研究內(nèi)容進(jìn)行了概述。第二章網(wǎng)絡(luò)網(wǎng)絡(luò)擁塞控制機(jī)制對網(wǎng)絡(luò)擁塞的原因，網(wǎng)絡(luò)擁塞的現(xiàn)象及擁塞控制的基本機(jī)制進(jìn)行了闡述，對TCP擁塞控制源算法、鏈路算法及算法的評價標(biāo)準(zhǔn)逐一進(jìn)行了討論。第三章從理論分析和模擬實(shí)驗(yàn)證實(shí)了TCP WestWood算法在鏈路利用率、穩(wěn)定性、RTT公平性、TCP友好性和收斂性等方面的性能，針對TCP WestWood 算法在擁塞避免階段窗口任然采用傳統(tǒng)線性增長方式的缺點(diǎn)，提出了采用非線性增長方式NLTCP WestWood 算法，并且優(yōu)化其慢啟動，并對該算法進(jìn)行了詳細(xì)的仿真實(shí)驗(yàn)。第四章在分析RED算法的基礎(chǔ)上，構(gòu)建一種改進(jìn)的DRED算法,并且驗(yàn)證其隊(duì)列長度和丟包率更為穩(wěn)定。第五章是結(jié)論部分，在總結(jié)本文的研究工作基礎(chǔ)上指出本文研究存在的一些問題，給出進(jìn)一步的研究方向。重慶郵電大學(xué)碩士論文第二章 擁塞控制算法綜述第二章 擁塞控制算法綜述當(dāng)網(wǎng)絡(luò)中存在過多的數(shù)據(jù)包時，網(wǎng)絡(luò)的性能就會下降，這種現(xiàn)象稱為擁塞。在網(wǎng)絡(luò)發(fā)生擁塞時，會導(dǎo)致吞吐量下降，嚴(yán)重時會發(fā)生“擁塞崩潰”(congestion collapse)現(xiàn)象22。一般來說，擁塞崩潰發(fā)生在網(wǎng)絡(luò)負(fù)載的增加導(dǎo)致網(wǎng)絡(luò)效率的降低的時候。目前對互聯(lián)網(wǎng)進(jìn)行的擁塞控制主要是依靠在源端執(zhí)行的基于窗口的TCP擁塞控制機(jī)制和依靠路由執(zhí)行的鏈路控制機(jī)制。圖2-1 顯示了負(fù)載與吞吐量的關(guān)系23，當(dāng)負(fù)載較小時，吞吐量與負(fù)載之間呈現(xiàn)線性關(guān)系，到達(dá)膝點(diǎn)(Knee)之后，隨負(fù)載的增加，吞吐量的增量逐漸變小。當(dāng)負(fù)載越過崖點(diǎn)(Cliff)24之后，吞吐量卻急劇下降，此時網(wǎng)絡(luò)陷入了嚴(yán)重?fù)砣麪顟B(tài)，若不及時進(jìn)行控制，則有可能導(dǎo)致網(wǎng)絡(luò)崩潰。擁塞控制的目的就是使吞吐量盡量保持在膝點(diǎn)與崖點(diǎn)之間，使網(wǎng)絡(luò)的負(fù)載始終保持在一個相應(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)網(wǎng)絡(luò)與電路交換(circuit switched)網(wǎng)絡(luò)相比，由于包交換網(wǎng)絡(luò)對資源的利用是基于統(tǒng)計(jì)復(fù)用(statistical multiplexing)的，因此提高了資源的利用效率。但在基于統(tǒng)計(jì)復(fù)用的情況下，很難保證用的服務(wù)質(zhì)量(quality of service，QoS)，并且很容易出現(xiàn)數(shù)據(jù)包“亂序”的現(xiàn)象，對亂序數(shù)據(jù)包的處理會大大增加擁塞控制的復(fù)雜性。2) 無連接(connectionless)網(wǎng)絡(luò)互聯(lián)網(wǎng)的節(jié)點(diǎn)之間在發(fā)送數(shù)據(jù)之前不需要建立連接，從而簡化了網(wǎng)絡(luò)的設(shè)計(jì)，網(wǎng)絡(luò)的中間節(jié)點(diǎn)上無需保留和連接有關(guān)的狀態(tài)信息。但無連接模型很難引入接納控制(admission control)，在用戶需求大于網(wǎng)絡(luò)資源時難以保證服務(wù)質(zhì)量:此外，由于對數(shù)據(jù)發(fā)送源的追蹤能力很差，給網(wǎng)絡(luò)安全帶來了隱患;無連接也是網(wǎng)絡(luò)中出現(xiàn)亂序數(shù)據(jù)包的主要原因。3) “盡力而為”的服務(wù)模型不對網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)提供服務(wù)質(zhì)量保證。在這種服務(wù)模型下，所有的業(yè)務(wù)流被“一視同仁”的公平地競爭網(wǎng)絡(luò)資源，路由器對所有的數(shù)據(jù)包都采用先來先處理(First Come First Service，F(xiàn)CFS)的工作方式，它盡最大努力將數(shù)據(jù)包包送達(dá)日的地。但對數(shù)據(jù)包傳遞的可靠性、延遲等不能提供任何保證。這很適合Email、Ftp、WWW等業(yè)務(wù)。但隨著互聯(lián)網(wǎng)的飛速發(fā)展，IP業(yè)務(wù)也得到了快速增長和多樣化。特別是隨著多媒體業(yè)務(wù)的興起，計(jì)算機(jī)已經(jīng)不是單純的處理數(shù)據(jù)的工具。這對互聯(lián)網(wǎng)也就相應(yīng)地提出了更高的要求。對那些有帶寬、延遲、延遲抖動等特殊要求的應(yīng)用來說，現(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ù)量，而只能靠降低服務(wù)質(zhì)量來繼續(xù)為用戶服務(wù)，也就是“盡力而為”的服務(wù)。主要有三方面原因：1) 路由器緩存不足當(dāng)多條線路上有多個數(shù)據(jù)包到達(dá)時，而且這些數(shù)據(jù)包都需要相同的輸出線路，路由器則建立一個隊(duì)列。如果路由器沒有足夠的緩存來存放這些到達(dá)的數(shù)據(jù)包，那么數(shù)據(jù)包就會被丟棄。但是盲目增加緩存空間不僅不能緩解擁塞，甚至加重26。2) 帶寬容量不足低速鏈路對高速數(shù)據(jù)流的輸入也會產(chǎn)生擁塞。所有信源發(fā)送的速率必須小于或等于信道容量。所以在網(wǎng)絡(luò)低速鏈路處就會形成帶寬瓶頸，當(dāng)其滿足不了通過它的所有源端帶寬的要求時，網(wǎng)絡(luò)就會發(fā)生擁塞。3) 處理器能力弱處理器的處理能力弱，難以完成必要的維護(hù)工作（緩沖區(qū)排隊(duì)、更新路由表等），處理速度跟不上高速鏈路，也會產(chǎn)生擁塞。單純地增加網(wǎng)絡(luò)資源之所以不能解決擁塞問題，是因?yàn)閾砣旧硎且粋€動態(tài)問題，它不可能只靠靜態(tài)的方案來解決，而需要協(xié)議能夠在網(wǎng)絡(luò)出現(xiàn)擁塞時保護(hù)網(wǎng)絡(luò)的正常運(yùn)行。2.2 擁塞控制算法分類根據(jù)算法的實(shí)現(xiàn)位置，可以將擁塞控制算法分為三大類:源算法(source Algorithm)、鏈路算法(Link Algorithm)和兩者結(jié)合的算法。源算法在主機(jī)和網(wǎng)絡(luò)邊緣設(shè)備中執(zhí)行作用是根據(jù)獲得的反饋信息調(diào)整發(fā)送速率。鏈路算法在網(wǎng)絡(luò)設(shè)備(如路由器和交換機(jī))中執(zhí)行，作用是檢測網(wǎng)絡(luò)擁塞的發(fā)生，產(chǎn)生擁塞反饋信息。源算法和鏈路算法形成反饋共同實(shí)現(xiàn)擁塞控制。2.2.1 擁塞控制源端算法源端算法中使用最廣泛的是TCP協(xié)議中的擁塞控制算法。1988年V.Jacobson在文獻(xiàn)27中指出了TCP在控制網(wǎng)絡(luò)擁塞方面的不足，并提出了“慢啟動（slow start）”算法和“擁塞避免（congestion avoidance）”算法。1990年出現(xiàn)了TCP Reno版本增加了“快速重傳”（fast retransmit）算法、“快速恢復(fù)”（fast recovery）算法，避免了網(wǎng)絡(luò)擁塞不夠嚴(yán)重時采用“慢速啟動”算法而造成過大地減少發(fā)送窗口尺寸的現(xiàn)象，這樣TCP的擁塞控制就有慢啟動、擁塞避免、快速重傳和快速恢復(fù)三個階段組成，這就是目前Internet上大多數(shù)機(jī)器運(yùn)行的TCP擁塞控制機(jī)制，即TCP Reno算法。1) 慢啟動：這個狀態(tài)窗口的初始值是一個數(shù)據(jù)包大?。ㄈ笔?12）一個數(shù)據(jù)包被發(fā)送，當(dāng)發(fā)送端收到來自接收端的ACK響應(yīng)，窗口增加1，發(fā)送端發(fā)送兩個數(shù)據(jù)包。在擁塞窗口達(dá)到最小閾值以前，發(fā)送端每收到一個確認(rèn)ACK擁塞窗口增加1。窗口的初始值大小是1，在一個和兩個RTT之后窗口大小應(yīng)該達(dá)到2和4，窗口隨RTT成指數(shù)規(guī)律增長。在慢啟動階段，用于在最短的時間內(nèi)盡可能多的使用可用帶寬資源。2) 擁塞避免：在擁塞避免階段，每收到一個ACK窗口增加1/cwnd，窗口成線性增加直到發(fā)送端收到3個重復(fù)的ACK。例如，在第N個RTT時，窗口大小是100，在第N+1和第N+2個RTT時，擁塞窗口應(yīng)該是101和102。在擁塞避免階段，試圖避免擁塞的發(fā)生并且盡可能地使用可用帶寬。3) 快速重傳和快速恢復(fù)：一個重復(fù)ACK可能是由丟失的數(shù)據(jù)包或者亂序的數(shù)據(jù)包引起的，因此源端收到了重復(fù)ACK并不能確定是丟失了數(shù)據(jù)包還是發(fā)生了亂序，當(dāng)連續(xù)收到3個或3個以上的重復(fù)ACK時，源端不需等到重傳超時就重傳那個被認(rèn)為丟失的包，這就叫快速重傳。在快速重傳可能丟失的數(shù)據(jù)包之后，連接進(jìn)入到擁塞避免階段而不是慢啟動階段，這就是快速恢復(fù)?？焖僦貍骱涂焖倩謴?fù)通常一起實(shí)現(xiàn)。當(dāng)重傳定時器超時，窗口被置為1，重新進(jìn)入慢啟動階段?？焖僦貍骱涂焖倩謴?fù)就是在發(fā)送端收到3個或者3個以上的重復(fù)ACK，判定包丟失，慢啟動閾值設(shè)為當(dāng)前窗口的一半而不必等待該包的計(jì)時器超時，同時接下來執(zhí)行的是擁塞避免算法而不是慢啟動算法，當(dāng)它們恢復(fù)丟包失效時，重傳定時器超時是發(fā)現(xiàn)并恢復(fù)丟包的最終機(jī)制。圖2.2為文獻(xiàn)27中擁塞控制窗口變化圖；圖2.3為TCP Reno擁塞控制窗口變化圖。 圖2-2 慢啟動和擁塞避免圖2-3 快速重傳和快速恢復(fù)2.2.2 源端擁塞控制的研究現(xiàn)狀為了解決高速網(wǎng)絡(luò)中TCP連接的性能問題，研究者提出了一些不同的新的解決方案，其中對端節(jié)點(diǎn)的研究成為一個熱點(diǎn)28。源端節(jié)點(diǎn)的改進(jìn)主要集中在控制擁塞窗口的大小和發(fā)送速率等方面。有很多大大地提高網(wǎng)絡(luò)性能的擁塞控制端算法被提出。這些新的端算法雖然采用不同的窗口控制機(jī)制，但最終目的都是快速響應(yīng)網(wǎng)絡(luò)的擁塞，及時增加和減少擁塞窗口，提高吞吐量，達(dá)到高效率的鏈路使用等。最近出現(xiàn)的一些新協(xié)議主要有：1) Scalable TCP(STCP)STCP協(xié)議是Tom Kelly于2003年提交給PFLDnet的以穩(wěn)定性著稱的面向高帶寬時延乘積網(wǎng)絡(luò)的新協(xié)議。STCP是個典型的MIMD（積式增加積式減少）協(xié)議15。它的設(shè)計(jì)思想是通過修改TCP的窗口增加和減少參數(shù)來調(diào)整發(fā)送窗口大小，STCP算法仍以丟包為擁塞信號，和傳統(tǒng)TCP擁塞控制相比，窗口增加變得更快，窗口減少變得更緩和。該算法在擁塞避免算法是收到新的包： (2-1)收到重復(fù)三個包： （2-2）每次丟包后窗口的調(diào)整周期為，因此源端提高一倍的發(fā)送速率需要大約70個RTT；該算法可以更好的利用歷經(jīng)短暫擁塞的高速廣域網(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ā)，采用了更加侵略性的窗口增加和更加保守的窗口減少模式?？紤]到光纖鏈路的最小丟包率為,為了能充分利用10Gbps的網(wǎng)絡(luò)帶寬，給出了窗口和丟包率的一個新關(guān)系,同時增加了三個參數(shù)：、,其默認(rèn)值分別為38，83000和,若當(dāng)前窗口小于時HSTCP使用與傳統(tǒng)TCP相同的響應(yīng)函數(shù)；反之，HSTCP使用自己的響應(yīng)函數(shù)。HSTCP使用變動的擁塞窗口調(diào)節(jié)參數(shù)，保證了在不同擁塞程度變化的網(wǎng)絡(luò)中也可正常工作，提高了算法在高速網(wǎng)絡(luò)下的魯棒性。在擁塞避免階段，算法表述如下：收到新的包 （2-2）收到三個重復(fù)包 （2-3）若當(dāng)前窗口小于時=1，=0.5。若當(dāng)前窗口大于 （2-4） （2-5） （2-6）3) SQRT TCP SQRT TCP28協(xié)議是由Tomoya HATANO等人提出的新協(xié)議。算法提出的新機(jī)制可以同時提高RTT公平性和TCP友好性且在大瓶頸鏈路上還能有效的利用鏈路帶寬。它的設(shè)計(jì)思想是：收到新的包則；收到重復(fù)三個包則；、 、 的值分別設(shè)定為1.25、15、-0.5、0.5。和HSTCP類似，當(dāng)擁塞窗口小于高速算法的閾值時，采用傳統(tǒng)TCP的擁塞控制機(jī)制；當(dāng)擁塞窗口大于高速算法的閾值，則采用SQRT TCP的擁塞控制機(jī)制。因此，SQRT TCP協(xié)議的擁塞控制機(jī)制高速環(huán)境表示如下：收到新的包 （2-7）收到重復(fù)三個包 （2-8）4) Africa TCP該協(xié)議是個自適應(yīng)的、公平的、快速增長的TCP擁塞控制機(jī)制，通過使用一個延遲的度量來確定瓶頸鏈路是否有擁塞，如下表示擁塞程度用表示 （2-9）是對網(wǎng)絡(luò)隊(duì)列延遲的一個估計(jì)。擁塞度量參數(shù)是個常量，通常設(shè)為比1大的實(shí)數(shù)，在算法中設(shè)為1.65。擁塞避免階段算法如下當(dāng)>時 （2-10）當(dāng)>時 （2-11）表示高速環(huán)境窗口增加量。2.2.3 擁塞控制鏈路算法要完全依賴實(shí)現(xiàn)在源節(jié)點(diǎn)系統(tǒng)上的策略與算法是很難滿足諸如QoS這樣復(fù)雜的應(yīng)用要求的。于是開始將部分研究注意力轉(zhuǎn)向網(wǎng)絡(luò)中的路由等中間節(jié)點(diǎn)設(shè)備，期望通過增強(qiáng)他們的功能來實(shí)現(xiàn)源端無法達(dá)到的技術(shù)目標(biāo)。就擁塞控制而言，網(wǎng)絡(luò)鏈路中間節(jié)點(diǎn)有可能更及時，甚至提前準(zhǔn)確了解網(wǎng)絡(luò)的擁塞狀態(tài)，并依此實(shí)施有效的資源管理策略，使網(wǎng)絡(luò)能有效地避免擁塞或盡早從嚴(yán)重的擁塞狀態(tài)中恢復(fù)過來。對路由器功能的擴(kuò)展要受繼承性和延續(xù)性的限制，否則將影響技術(shù)的實(shí)用性。事實(shí)上，現(xiàn)有的路由器擴(kuò)展功能，主要包括調(diào)度和隊(duì)列/緩存管理，并沒有與Internet將流狀態(tài)信息保存在源端的早期設(shè)計(jì)理念相沖突。調(diào)度(scheduler)直接管理輸出鏈路的帶寬資源，而隊(duì)列/緩存管理通過控制緩存與隊(duì)列的占有間接影響帶寬的分配。管理隊(duì)列長度的傳統(tǒng)方法是對每個隊(duì)列設(shè)置一個最大值(以包為單位)，然后接受包進(jìn)入隊(duì)列直到隊(duì)長達(dá)到最大值，接下來到達(dá)的包就要被拒絕進(jìn)入隊(duì)列直到隊(duì)長下降，這種技術(shù)也就是傳統(tǒng)的“尾丟棄”(Drop-Tall)算法。由于這種方法是在隊(duì)列滿了之后被迫丟包，因此稱為被動式隊(duì)列管理(PQM)，雖然Drop-Tail算法在當(dāng)前Internet上得到了廣泛的使用，但其存在幾個重要問題29。1) “死鎖”(lock-out)現(xiàn)象:在某些情況下，由于同步或其他定時作用的結(jié)果，Drop-Tail算法會讓某個流或者少數(shù)幾個流獨(dú)占隊(duì)列空間，阻止其他流的包進(jìn)入隊(duì)列。2) 滿隊(duì)列(full queues)問題:由于Drop-Tail只有在隊(duì)列滿時才會發(fā)出擁塞信號，因此會使得隊(duì)列在相當(dāng)長時間內(nèi)處于充滿或幾乎充滿)的狀態(tài)。而隊(duì)列管理最重要的目標(biāo)之一就是降低穩(wěn)定狀態(tài)下隊(duì)列的長度，因?yàn)槎说蕉说难舆t主要就是由于在隊(duì)列中排隊(duì)等待造成的。3) 全局同步(global synchronization)問題:由于Internet上到達(dá)路由器的包往往是突發(fā)的。如果隊(duì)列是滿的或者幾乎是滿的，就會導(dǎo)致在短時間內(nèi)連續(xù)大量的丟包。而TCP流具有自適應(yīng)特性，源端發(fā)現(xiàn)包丟失就急劇地減小發(fā)送窗口，包到達(dá)速率就迅速下降，于是網(wǎng)絡(luò)擁塞得以解除，但源端得知網(wǎng)絡(luò)不再擁塞后又開始增加發(fā)送速度，最終又造成網(wǎng)絡(luò)擁塞。在當(dāng)前的Internet上，丟包是對端節(jié)點(diǎn)進(jìn)行擁塞通知的主要機(jī)制，解決被動式隊(duì)列管理問題的方法便是在隊(duì)列滿之前丟包，這樣端節(jié)點(diǎn)便能在隊(duì)列溢出前對擁塞作出反應(yīng)。這種方法便稱為主動式隊(duì)列管理(AQM)。它使得路由器能夠控制在什么時候丟包和丟多少包，從而有效地管理隊(duì)列長度，以支持端到端的擁塞控制。AQM的主要優(yōu)點(diǎn)是：1) 減少網(wǎng)關(guān)的報(bào)文丟失使用AQM可以保持較小的隊(duì)列長度，從而增強(qiáng)網(wǎng)絡(luò)中間節(jié)點(diǎn)容納突發(fā)流量的能力。2) 減小報(bào)文通過網(wǎng)關(guān)的延遲減小平均隊(duì)列長度可以有效地減小報(bào)文在網(wǎng)絡(luò)設(shè)備中的排隊(duì)延遲。3) 避免lock-out行為的發(fā)生302.2.4 鏈路擁塞控制研究現(xiàn)狀鏈路算法的研究目前集中在主動隊(duì)列管理(Active Queue Management，簡稱AQM)。和傳統(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的性能對算法的參數(shù)設(shè)置十分敏感，至今沒有在Internet中得到廣泛的使用。最近出現(xiàn)的一些新的AQM算法主要有：1) 隨即早期檢測算法RED最早提出的AQM算法是隨機(jī)早期檢測(RED)算法，也是目前最常用的一種AQM算法。RED的基本思想是路由器通過監(jiān)控隊(duì)列的平均長度來探測擁塞，一旦發(fā)現(xiàn)擁塞逼近，就隨機(jī)地選擇源端來通知擁塞，使它們在隊(duì)列溢出之前降低發(fā)送數(shù)據(jù)速率，以緩解網(wǎng)絡(luò)擁塞。RED算法主要包括兩步，首先計(jì)算平均隊(duì)列長度，然后計(jì)算丟棄包的概率。RED在計(jì)算平均隊(duì)長時，采用了類似低通濾波器帶權(quán)值的方法 （2-12）其中，為權(quán)值，為采樣測量時實(shí)際隊(duì)列長度。從而“過濾”掉由于Internet數(shù)據(jù)的突發(fā)性導(dǎo)致的短期隊(duì)長變換，盡量反映長期的擁塞變化。權(quán)值相當(dāng)于低通濾波器的時間常數(shù)，它決定了路由器對輸入流量變化的反應(yīng)程度，計(jì)算平均隊(duì)長的目的就是為了反映擁塞程度并據(jù)此來計(jì)算丟包概率。RED有兩個與隊(duì)列長度相關(guān)的闡值：和。當(dāng)有數(shù)據(jù)包達(dá)到路由器時，RED計(jì)算出平均隊(duì)長，然后計(jì)算丟包率。若 （2-13）是最大丟包率。再對丟包率做進(jìn)一步調(diào)整： （2-14）是上一次丟包開始到現(xiàn)在連續(xù)進(jìn)入隊(duì)列的包的數(shù)量。2) 自適應(yīng)RED算法ARED自適應(yīng)RED算法(adaptive RED，ARED)9。ARED的基本思想就是通過檢查平均隊(duì)長的變化來決定RED是應(yīng)更激進(jìn)還是更保守，從而盡量保持平均隊(duì)長在和。之間。具體地說，如果平均隊(duì)長是在附近振蕩，說明擁塞控制太激進(jìn)了，那么就減小 （2-15）如果在附近振蕩，說明擁塞控制太保守了，那么就增大 （2-16）ARED是對RED改動很小的一種算法，它保留了RED的基本結(jié)構(gòu)，只需調(diào)節(jié)參數(shù)，從而保持平均隊(duì)長在和之間，消除了RED的隊(duì)列延時