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

《高速網絡擁塞控制研究碩士畢業(yè)論文》由會員分享，可在線閱讀，更多相關《高速網絡擁塞控制研究碩士畢業(yè)論文（58頁珍藏版）》請在裝配圖網上搜索。

1、 碩士學位論文 論文題目 高速網絡擁塞控制研究 英文題目 Research on Congestion Control for High-Speed Network 碩士研究生 指導教師 學科專業(yè) 計算機軟件與理論 論文提交日期 2009年4月 論文答辯日期 論文評閱人 答辯委員會主席 2009 年 4 月 10 日Abstract摘 要隨著高速網絡應用的日益廣泛，擁塞控制機制的研究變得越來越重要。擁塞控制至少應該包含兩部分：首先是要有源端算法響應路徑中的擁塞，動態(tài)的調節(jié)數據發(fā)送速率;另一方面，要有一個中間節(jié)點管理機制能有效地預測、監(jiān)測路徑中的擁塞程度，通過顯式或隱式的方法在擁塞發(fā)生前及時警告

2、源端。目前研究適合高速網絡的TCP擁塞控制機制成為一個新的研究熱點，一些研究者提出了一些新的算法如：STCP，H-TCP等。這些協(xié)議都是通過修改發(fā)送窗口的增加減小模式來提高TCP在高速網絡中的性能。其中TCPW是以可用帶寬測量為基礎的新的TCP協(xié)議，對原有TCP協(xié)議改動較小，具有較好RTT公平性和較好的TCP友好性，在真實網絡中易于實現，但是TCPW仍存在一些性能缺陷。由于TCPW窗口增長仍采用線性增加模式，因此不能像其他協(xié)議一樣快速獲得更大的發(fā)送窗口，而且在該算法的慢啟動階段仍然采用指數增長模式，從而導致大量突發(fā)數據的產生，造成擁塞。中間節(jié)點控制由路由器擁塞控制算法來實現，主動式隊列管理機制

3、（AQM）是IEFT推薦的基于路由器擁塞控制關鍵技術，它和TCP端到端的擁塞控制相結合，是解決目前網絡擁塞控制問題的一個主要手段。RED算法是AQM的一個典型，但其在算法穩(wěn)定性和參數敏感性方面存在缺陷。本文基于以上兩個算法，開展了以下三個方面的工作。首先對TCPW算法進行改進，主要集中在以下兩點：一是在慢啟動階段發(fā)送窗口較原有算法能較快的到達10個包左右，之后窗口增長速度較原有算法有所減慢，這樣有利于短流傳輸和避免突發(fā)數據產生，從而減緩擁塞；二是在擁塞避免階段采用基于當前擁塞窗口大小的先快后慢的非線性增長方式，使之更適合于高速環(huán)境。通過建立新算法的數學模型分析其穩(wěn)定性、RTT公平性和對TCP友

4、好性，在此基礎上分別對以上兩點改進采用NS2仿真方法加以驗證，發(fā)現算法較原有算法在高速環(huán)境下有更好的吞吐量和更有利于短流數據傳輸。另外本文在分析RED算法基礎上，提出了一種新的改進型AQM算法DRED算法。DRED相對RED算法，能夠動態(tài)調整參數，并且采用非線性函數代替原有的丟包率計算方法。通過動態(tài)調整來調整向源端發(fā)送擁塞通知的速率，維持隊列的穩(wěn)定；通過新丟包率計算方式，提高緩沖的利用率和使隊列長度盡量穩(wěn)定于期望值附近。最后通過仿真來驗證新算法更適應網絡流量的變化，保持隊列長度的穩(wěn)定和丟包率的穩(wěn)定，從而提高了網絡鏈路利用率。關鍵詞：高速網； 擁塞控制； TCPW； RED 52Abstract

5、AbstractWith 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 resp

6、ond 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 m

7、echanisms 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 be

8、tter 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 o

9、f 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

10、 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 algori

11、thm 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.

12、 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 han

13、d, 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 algori

14、thm 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 therefo

15、re 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 o

16、f 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目錄目

17、錄摘 要IAbstractII第一章 緒 論11.1 研究背景11.2 研究現狀31.3 主要研究工作51.4 論文的內容及安排6第二章 擁塞控制算法綜述82.1 擁塞產生的原因82.2 擁塞控制算法分類102.2.1 擁塞控制源端算法102.2.2 源端擁塞控制的研究現狀112.2.3 擁塞控制鏈路算法142.2.4 鏈路擁塞控制研究現狀152.3 擁塞控制算法的評價標準182.3.1 穩(wěn)定性分析182.3.2 公平性分析192.3.3 友好性分析202.4 小結20第三章 TCP Westwood擁塞控制算法改進213.1 引言213.2 TCPW算法的分析223.2.1 TCPW算法的簡

18、介223.2.2 TCPW算法優(yōu)點233.2.3 TCPW算法存在的不足233.3 改進的擁塞控制算法NLTCPW243.3.1 擁塞避免階段改進253.3.2 慢啟動階段改進253.3.3 NLTCPW算法的數學模型263.3.4 仿真環(huán)境下NLTCPW算法的吞吐量性能分析293.3.5 NLTCPW算法RTT公平性實驗323.3.6 NLTCPW算法短流數據傳輸性能分析323.4 小結34第四章 RED算法改進354.1 一種新的自適應RED算法DRED算法354.1.1 RED算法概述354.1.2 RED算法的優(yōu)點364.1.3 RED算法存在的不足364.1.4 DRED算法384.

19、2 DRED算法性能分析404.3 小結45第五章 結論及未來的工作465.1結論465.2 未來的工作47致 謝48攻讀碩士學位期間從事的主要科研工作及發(fā)表的論文49參考文獻50第一章 緒論第一章 緒 論1.1 研究背景近年來隨著信息技術迅速發(fā)展，以互聯網為代表的信息網絡已經逐漸滲透到當今社會的各個領域，成為了國家進步和社會發(fā)展的重要支柱，以及知識經濟的基礎載體和支撐環(huán)境，它的重要性就如同鐵路和高速公路的蓬勃發(fā)展給工業(yè)社會帶來了廣泛而深遠的影響一樣，必將成為21世紀全球最重要的基礎設施之一。就目前的現狀和未來的發(fā)展而言，下一代互聯網的骨干帶寬必將呈現指數型增長。下一代互聯網建設與發(fā)展的各種趨

20、勢表明：大規(guī)模的高速網絡試驗環(huán)境已經形成，未來幾年內，互聯網骨干將全面升級到支持近10Gbps的高速鏈路，而且很有可能持續(xù)增長。但是，雖然下一代互聯網的骨干帶寬呈現指數性的增長，實踐中上述海量數據傳輸業(yè)務的用戶卻并沒有切身感受到網絡帶寬劇增所帶來的好處，于是人們開始懷疑高速網絡中傳輸協(xié)議的性能。這是由于TCP/IP協(xié)議在高速網絡中確實存在效率問題1。因此研究適應于高速網絡的擁塞控制算法成了網絡研究的新熱點。目前，Internet上用戶和應用的數量都在迅速增長，當多個用戶對網絡的需求總量大于網絡實際傳輸能力時，必然會導致網絡擁塞的發(fā)生。雖然擁塞源于資源短缺，但增加資源并不能避免擁塞的發(fā)生，有時甚

21、至會加重擁塞程度2。所以選擇和引進更多、更合理的擁塞控制機制對網絡的高效穩(wěn)定運行是至關重要的。隨著應用需求的豐富和技術的發(fā)展，研究者開始認識到想完全依賴實現在終端系統(tǒng)上的策略與算法很難滿足越來越多的復雜應用需求。于是，人們把注意力轉向網絡中的路由器等中間節(jié)點設備，期望通過增強它們的功能來實現主機端無法達到的目標網。就擁塞控制而言，網絡中間節(jié)點有可能更及時，甚至可以提前準確了解網絡的擁塞狀態(tài)，并依此實施有效的資源管理策略，使網絡能有效地避免擁塞，或盡早從嚴重的擁塞狀態(tài)中恢復過來。當然，對路由器功能的擴展要受繼承性和延續(xù)性的限制，否則將影響技術的實用性。事實上，現有的路由器擴展功能，主要包括調度和

22、隊列/緩存管理。調度(Scheduling)直接管理下次發(fā)哪個分組和分配各個流的帶寬。而隊列/緩存算法管理路由器緩沖區(qū)中分組隊列的長度，即在必要或適當的時候丟掉一些分組。因此根據擁塞控制算法實現的位置不同主要分為兩大類：源端控制和鏈路控制，源算法在主機和網絡邊緣設備中的執(zhí)行作用主要是根據獲得的反饋信息調整發(fā)送速率。鏈路算法在網絡設備(如路由器和交換機)中執(zhí)行，作用是檢測網絡擁塞的發(fā)生，產生擁塞反饋信息。源算法和鏈路算法形成反饋，共同實現擁塞控制，兩者形成的反饋系統(tǒng)共同形成了擁塞控制系統(tǒng)，所以必須在這兩方面同時進行研究和綜合。在實際部署中要考慮效率和費用比的問題同時又要要求源端控制和鏈路控制必須

23、相互獨立，一個對原有系統(tǒng)改動過大的擁塞控制算法不利于部署。比如XCP3(eXplicit Control Protocol)，是美國麻省理工和伯克利針對高帶寬時延乘積網絡提出的一個Internet擁塞控制的新體系結構，它是將端節(jié)點和路由器相結合完成擁塞控制的執(zhí)行模式。XCP協(xié)議其路由器算法主要由有效控制算法（EC）和公平性控制算法（FC）構成。EC僅考慮鏈路的總流量，而不考慮單條流的流量及公平性問題。FC實現目標是將EC計算出來的總的反饋量在包層次上公平地分配給每條流。FC以包為單位來分配EC計算出的總的反饋量。在端節(jié)點數據包結構中增加了cwnd、RTT估計和feedback三個域。發(fā)送端發(fā)送

24、數據包時使用feedback域請求希望得到的擁塞窗口調整的變化量，數據包途經的路由器根據當時網絡可用帶寬的狀況修改feedback域的值。當數據包到達接收端時，feedback域保留的是該數據包途徑的各路由器允許發(fā)送端可以增加的帶寬的最小值或要求發(fā)送端需要減少的帶寬的最大值，然后接收端通過ACK包將feedback域的值反饋給發(fā)送端，最終發(fā)送端按照反饋調整隨后的發(fā)送速率。但是XCP的關鍵算法全部在路由器內實現，在實際網絡中要建造如此強大功能的路由器的造價是十分昂貴的；同時若端節(jié)點或中間路由節(jié)點其中一個不支持此協(xié)議，算法將失效；因此XCP在實際網絡中難以實現和部署。擁塞控制算法的分布性、網絡的復

25、雜性和對擁塞控制算法性能要求等使擁塞控制算法的設計具有很高的難度Error! Reference source not found.，其主要表現如下：1) 算法的分布性擁塞控制算法的實現分布在多個網絡節(jié)點中，必須使用不完整的信息完成控制，并使各節(jié)點協(xié)調工作，還必須考慮某些節(jié)點工作不正常的情況。2) 網絡環(huán)境的復雜性Internet中各處的網絡性能有很大的差異，算法必須具有很好的適應性。另外，由于Internet對報文的正確傳輸不提供保證，算法必須處理報文丟失、亂序到達等情況。3) 算法的性能要求。擁塞控制算法對性能有很高的要求，包括算法的公平性、效率、穩(wěn)定性和收斂性等。某些性能目標之間存在矛盾

26、，在算法設計時需要進行權衡。4) 算法的開銷 擁塞控制算法必須盡量減少附加的網絡流量，特別是在擁塞發(fā)生時。在使用反饋式的控制機制時，這個要求增加了算法設計的困難。算法還必須盡量降低在網絡節(jié)點（特別是網關）上的計算復雜性。1.2 研究現狀目前對網絡擁塞控制的研究主要從以下兩個方面進行：首先是解決源端的算法，通過依靠動態(tài)的調節(jié)源端數據發(fā)送速率，及時能響應路徑中的擁塞；另一方面是解決鏈路算法，通過對中間節(jié)點的有效管理機制能，不斷地預測并監(jiān)測路徑中的擁塞程度，通過顯式或隱式的方法在擁塞發(fā)生前及時警告源端，在擁塞發(fā)生之后抑制源端的發(fā)送速率以超出中間節(jié)點轉發(fā)速率的速度發(fā)送報文分組。傳統(tǒng)的源端TCP擁塞控制

27、算法使得當前的Internet網絡獲得了巨大的成功，但是近幾年來人們越來越清楚的認識到傳統(tǒng)的TCP擁塞控制機制主要采用了慢啟動機制和AIMD（和式增加積式減少）的擁塞避免機制，它在高速長距離網絡中的性能已達到瓶頸4。文獻4分析了傳統(tǒng)TCP在高速長距離網絡中不能達到高吞吐量的主要的原因表現在如下幾個方面：1) 現存的擁塞控制機制對擁塞反應性比較差TCP在高速長距離網絡中對包丟失的敏感程度遠遠高于局域網或者普通的廣域網，這主要歸因于它的擁塞避免算法中基于AIMD（和式增加積式減少）的窗口增加減少原則。在它的擁塞避免算法中每一個往返時延（RTT）至多增加一個數據包的小尺寸來增加擁塞窗口（和式增加），

28、而單個包丟失在高速長距離網絡中的影響是非常普遍的的，當一個TCP連接一旦被探測到有數據包丟失時，立刻要將它的擁塞窗口減少一半（積式減少），這需要花去幾百毫秒甚至幾秒才能重新恢復到原來的窗口大小，這種緩慢的窗口恢復速度會直接導致吞吐率不高，無法充分利用帶寬。相反窗口減小又顯得過于激烈，造成了網絡流量的巨大震蕩，同時也會降低網絡的吞吐量。而另一方面慢啟動也會造成TCP在網絡中的性能下降，但相對而言這方面的影響比擁塞避免階段要小很多，這是因為在TCP連接中往往是通過收到三個重復ACK而不是超時來檢測丟包，所以TCP連接在擁塞避免階段比慢啟動階段要花費更多的時間。2) 對數據包丟失的解釋不同數據包在傳

29、輸過程中可能會由于緩沖區(qū)溢出或者傳輸介質的出錯而引起包丟失或者包損壞的情況，傳統(tǒng)TCP假定鏈路錯誤造成的損失是可以忽略不計的，但是在高速網絡中，當數據傳輸的速率較高時，鏈路錯誤是不能被忽略的，由數據鏈路錯誤引起的丟包和由網絡擁塞引起的丟包的可能性是相同的，所以在高速網絡中不能籠統(tǒng)的認為只要是分組丟失就一定由網絡擁塞引起的。3) 擁塞窗口和丟包率之間存在固定的函數關系在TCP的擁塞控制算法中窗口大小w與丟包率p之間的約束關系為5，由此可見，在這種固定的關系約束下，要保持大的擁塞窗口需要極小的丟包率，即使丟包率能達到這個要求，對于發(fā)送端來說，這也是一個極為不精確的反饋；所以在最后TCP的擁塞控制算

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

31、連接回路的往返時間及擁塞窗口值大小有關，即調整周期等于擁塞窗口大小的二分之一乘以一個窗口數據傳輸的往返時間。特別是在高帶寬網絡中，傳統(tǒng)TCP在一次丟包后要經過幾個甚至幾十個RTT才能恢復到原來的窗口大小。要達到100%完全利用鏈路的理想狀態(tài)那更是不可能實現的。從以上分析可以看出，造成TCP擁塞控制算法在高速網絡中性能不好的主要原因是其擁塞控制機制不適應于高速網絡，目前已經有一些學者提出了多種解決方案，主要分為四類：1)基于丟失的算法;2)基于延遲的算法;3)基于丟失和延遲相混合的算法;4)基于顯示擁塞指示的算法。傳統(tǒng)TCP是典型的基于丟失的算法；FAST TCP5將延遲作為擁塞指示的算法,Af

32、rica TCP6用隊列延遲和包丟失作為網絡的擁塞指示。在正常的工作環(huán)境下，擁塞窗口經過一個RTT被更新且依賴于平均RTT的估計。TCP Africa算法就是一個基于丟失和延遲的“雙模式”算法。XCP3屬于最后一類，它需要通過從網絡環(huán)境中獲取的指示信號來推斷網絡是否發(fā)生擁塞，這種算法的配置需要和路由器同時進行操作?；诼酚善鞯膿砣刂疲存溌房刂扑惴ǎ┲饕峭ㄟ^對其隊列進行管理來實現的，目前的隊列管理主要還是被動式隊列管理(Passive Queue Management，PQM)。本質上PQM并沒有參與到網絡擁塞管理中去，只是在隊列溢出的情況下被動地丟包。若路由器上使用主動式隊列管(Acti

33、ve Queue Management，AQM)機制來控制在什么時候丟多少包，將有效地管理隊列長度，以支持端到端的擁塞控制。其基本思想是通過監(jiān)控路由器輸出端口隊列的平均長度來探測擁塞。一旦發(fā)現擁塞逼近，就隨機地選擇時機對源端進行通知擁塞，使它們在隊列溢出導致丟包之前降低發(fā)送數據速率，從而緩解網絡擁塞。主要的AQM算法有RED8、ARED9、FRED10 、BLUE11 、WRED12、PI13、AVQ14和 REM 15。其中RED、ARED和FRED屬于一類，都是隨機早期檢測算法。PI是基于控制理論提出一種算法，PI控制算法可以有效消除“穩(wěn)態(tài)誤差”，但同時也會減慢系統(tǒng)的反應速度，而且PI控制

34、器只能很好的工作在一定得分范圍的環(huán)境中，這使PI難以在真實的網絡環(huán)境中使用；REM是基于優(yōu)化理論提出的。AQM算法的共同特點是，計算出丟包率后反饋給源端系統(tǒng)，源端系統(tǒng)可以采取的動作包括“丟棄”（Dropping）和“標記”（Marking）。“丟棄”是現有系統(tǒng)都支持的一種操作，而“標記”的方法，可經“顯示”的通知源端系統(tǒng)擁塞的發(fā)生，比較而言“標記”方法性能更好。隨著“顯示擁塞通知”(ECN)的標準化和廣泛采用，將有越來越多的網關支持“標記”的策略。從實際的應用來看，路由器廠商紛紛在自己的產品中支持RED算法，如Ciseo7500等系列路由器，Juniper的M40、M80等；在Differv的

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

36、控制的研究從最初單純解決TCP的低效問題，到圍繞公平性、穩(wěn)定性以及收斂性等方面開展了一系列更深入的研究，但是到目前為此，在該研究領域仍然存在很多開放性問題，其中作者認為最為突出的一點是目前的多數研究沒有充分強調模型分析的重要性，缺乏具有總結性結論和定律的歸納與描述。同時在擁塞控制機制和算法的設計上過分依賴于基于經驗的啟發(fā)式設計結合典型、有限和局部仿真試驗驗證的設計方法，得到的算法往往是靜態(tài)的和準靜態(tài)的，不能適應快速變化的動態(tài)網絡化環(huán)境。高速網絡環(huán)境下擁塞控制算法的優(yōu)化設計還存在很大的研究空間。1.3 主要研究工作隨著Internet的發(fā)展，它的傳輸擁塞控制機制必須保持有效性。技術的趨勢表明越來

37、越多的高帶寬鏈路將應用到互聯網絡中，高速網絡擁塞控制協(xié)議的設計分類兩類:修改TCP協(xié)議、終端與路由器聯合的協(xié)議。針對高速網絡的特點基于TCP協(xié)議采用不同的機制進行改進而來的新協(xié)議包括前面提到的FAST TCP在內的諸如：High-Speed TCP16 、Scalable TCP17、BIC18、CUBIC19和H-TCP20。這些協(xié)議設計的主要目的是在高速網絡下能快速的獲得高的穩(wěn)定的吞吐量，從而提高高速網絡鏈路的利用率。本文首先分析TCPW21算法在高速網環(huán)境下，慢啟動和擁塞避免階段存在問題提出一種改進NLTCPW算法。NLTCPW將TCPW在高帶寬時延積網絡中窗口增加采用線性方式改為一種非

38、線性增長方式，使之窗口增加先快后慢，窗口維持在一個較大的水平，從而獲得更好的帶寬利用率；慢啟動階段窗口開始階段較快的增加到10（包），超過10（包）后減緩增長速度，這樣可以提高WEB流的傳輸，降低網絡丟包率，降低網絡突發(fā)數據量；建立NLTCPW的數學模型，從理論上對NLTCPW的穩(wěn)定性，RTT公平性、TCP友好性進行分析，利用仿真工具在網絡吞吐量、WEB流數據傳輸、丟包率等方面對NLTCPW和TCPW進行了比較分析，結果表明NLTCPW相對TCPW在保持原有算法優(yōu)點情況下提高網絡吞吐量和其在傳輸短流數據方面效率。由于RED算法是IEFT推薦在路由器上的算法，所以研究RED算法實用性更好且易于部

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

40、了闡述，對TCP擁塞控制源算法、鏈路算法及算法的評價標準逐一進行了討論。第三章從理論分析和模擬實驗證實了TCP WestWood算法在鏈路利用率、穩(wěn)定性、RTT公平性、TCP友好性和收斂性等方面的性能，針對TCP WestWood 算法在擁塞避免階段窗口任然采用傳統(tǒng)線性增長方式的缺點，提出了采用非線性增長方式NLTCP WestWood 算法，并且優(yōu)化其慢啟動，并對該算法進行了詳細的仿真實驗。第四章在分析RED算法的基礎上，構建一種改進的DRED算法,并且驗證其隊列長度和丟包率更為穩(wěn)定。第五章是結論部分，在總結本文的研究工作基礎上指出本文研究存在的一些問題，給出進一步的研究方向。重慶郵電大學碩

41、士論文第二章 擁塞控制算法綜述第二章 擁塞控制算法綜述當網絡中存在過多的數據包時，網絡的性能就會下降，這種現象稱為擁塞。在網絡發(fā)生擁塞時，會導致吞吐量下降，嚴重時會發(fā)生“擁塞崩潰”(congestion collapse)現象22。一般來說，擁塞崩潰發(fā)生在網絡負載的增加導致網絡效率的降低的時候。目前對互聯網進行的擁塞控制主要是依靠在源端執(zhí)行的基于窗口的TCP擁塞控制機制和依靠路由執(zhí)行的鏈路控制機制。圖2-1 顯示了負載與吞吐量的關系23，當負載較小時，吞吐量與負載之間呈現線性關系，到達膝點(Knee)之后，隨負載的增加，吞吐量的增量逐漸變小。當負載越過崖點(Cliff)24之后，吞吐量卻急劇下

42、降，此時網絡陷入了嚴重擁塞狀態(tài)，若不及時進行控制，則有可能導致網絡崩潰。擁塞控制的目的就是使吞吐量盡量保持在膝點與崖點之間，使網絡的負載始終保持在一個相應的區(qū)間之間。通常將Knee點附近定義成為擁塞避免區(qū)，Knee和Cliff之間是擁塞恢復區(qū)，而Cliff之外是擁塞崩潰區(qū)間。圖2-1 網絡性能與負載之間關系2.1 擁塞產生的原因擁塞的發(fā)生和的互聯網的設計機制有著密切關系，這種機制包括：1) 數據包交換(packets witched)網絡與電路交換(circuit switched)網絡相比，由于包交換網絡對資源的利用是基于統(tǒng)計復用(statistical multiplexing)的，因此提

43、高了資源的利用效率。但在基于統(tǒng)計復用的情況下，很難保證用的服務質量(quality of service，QoS)，并且很容易出現數據包“亂序”的現象，對亂序數據包的處理會大大增加擁塞控制的復雜性。2) 無連接(connectionless)網絡互聯網的節(jié)點之間在發(fā)送數據之前不需要建立連接，從而簡化了網絡的設計，網絡的中間節(jié)點上無需保留和連接有關的狀態(tài)信息。但無連接模型很難引入接納控制(admission control)，在用戶需求大于網絡資源時難以保證服務質量:此外，由于對數據發(fā)送源的追蹤能力很差，給網絡安全帶來了隱患;無連接也是網絡中出現亂序數據包的主要原因。3) “盡力而為”的服務模型

44、不對網絡中傳輸的數據提供服務質量保證。在這種服務模型下，所有的業(yè)務流被“一視同仁”的公平地競爭網絡資源，路由器對所有的數據包都采用先來先處理(First Come First Service，FCFS)的工作方式，它盡最大努力將數據包包送達日的地。但對數據包傳遞的可靠性、延遲等不能提供任何保證。這很適合Email、Ftp、WWW等業(yè)務。但隨著互聯網的飛速發(fā)展，IP業(yè)務也得到了快速增長和多樣化。特別是隨著多媒體業(yè)務的興起，計算機已經不是單純的處理數據的工具。這對互聯網也就相應地提出了更高的要求。對那些有帶寬、延遲、延遲抖動等特殊要求的應用來說，現有的“盡力而為”服務顯然是不夠的。導致擁塞發(fā)生的原

45、因在于網絡能夠提供的資源不足以滿足用戶的需求，這些資源包括緩存空間、鏈路帶寬容量和中間節(jié)點的處理能力等25。由于互聯網的設計機制導致其缺乏“接納控制”能力，因此在網絡資源不足時不能限制用戶數量，而只能靠降低服務質量來繼續(xù)為用戶服務，也就是“盡力而為”的服務。主要有三方面原因：1) 路由器緩存不足當多條線路上有多個數據包到達時，而且這些數據包都需要相同的輸出線路，路由器則建立一個隊列。如果路由器沒有足夠的緩存來存放這些到達的數據包，那么數據包就會被丟棄。但是盲目增加緩存空間不僅不能緩解擁塞，甚至加重26。2) 帶寬容量不足低速鏈路對高速數據流的輸入也會產生擁塞。所有信源發(fā)送的速率必須小于或等于信

46、道容量。所以在網絡低速鏈路處就會形成帶寬瓶頸，當其滿足不了通過它的所有源端帶寬的要求時，網絡就會發(fā)生擁塞。3) 處理器能力弱處理器的處理能力弱，難以完成必要的維護工作（緩沖區(qū)排隊、更新路由表等），處理速度跟不上高速鏈路，也會產生擁塞。單純地增加網絡資源之所以不能解決擁塞問題，是因為擁塞本身是一個動態(tài)問題，它不可能只靠靜態(tài)的方案來解決，而需要協(xié)議能夠在網絡出現擁塞時保護網絡的正常運行。2.2 擁塞控制算法分類根據算法的實現位置，可以將擁塞控制算法分為三大類:源算法(source Algorithm)、鏈路算法(Link Algorithm)和兩者結合的算法。源算法在主機和網絡邊緣設備中執(zhí)行作用是

47、根據獲得的反饋信息調整發(fā)送速率。鏈路算法在網絡設備(如路由器和交換機)中執(zhí)行，作用是檢測網絡擁塞的發(fā)生，產生擁塞反饋信息。源算法和鏈路算法形成反饋共同實現擁塞控制。2.2.1 擁塞控制源端算法源端算法中使用最廣泛的是TCP協(xié)議中的擁塞控制算法。1988年V.Jacobson在文獻27中指出了TCP在控制網絡擁塞方面的不足，并提出了“慢啟動（slow start）”算法和“擁塞避免（congestion avoidance）”算法。1990年出現了TCP Reno版本增加了“快速重傳”（fast retransmit）算法、“快速恢復”（fast recovery）算法，避免了網絡擁塞不夠嚴重時

48、采用“慢速啟動”算法而造成過大地減少發(fā)送窗口尺寸的現象，這樣TCP的擁塞控制就有慢啟動、擁塞避免、快速重傳和快速恢復三個階段組成，這就是目前Internet上大多數機器運行的TCP擁塞控制機制，即TCP Reno算法。1) 慢啟動：這個狀態(tài)窗口的初始值是一個數據包大?。ㄈ笔?12）一個數據包被發(fā)送，當發(fā)送端收到來自接收端的ACK響應，窗口增加1，發(fā)送端發(fā)送兩個數據包。在擁塞窗口達到最小閾值以前，發(fā)送端每收到一個確認ACK擁塞窗口增加1。窗口的初始值大小是1，在一個和兩個RTT之后窗口大小應該達到2和4，窗口隨RTT成指數規(guī)律增長。在慢啟動階段，用于在最短的時間內盡可能多的使用可用帶寬資源。2

49、) 擁塞避免：在擁塞避免階段，每收到一個ACK窗口增加1/cwnd，窗口成線性增加直到發(fā)送端收到3個重復的ACK。例如，在第N個RTT時，窗口大小是100，在第N+1和第N+2個RTT時，擁塞窗口應該是101和102。在擁塞避免階段，試圖避免擁塞的發(fā)生并且盡可能地使用可用帶寬。3) 快速重傳和快速恢復：一個重復ACK可能是由丟失的數據包或者亂序的數據包引起的，因此源端收到了重復ACK并不能確定是丟失了數據包還是發(fā)生了亂序，當連續(xù)收到3個或3個以上的重復ACK時，源端不需等到重傳超時就重傳那個被認為丟失的包，這就叫快速重傳。在快速重傳可能丟失的數據包之后，連接進入到擁塞避免階段而不是慢啟動階段，

50、這就是快速恢復。快速重傳和快速恢復通常一起實現。當重傳定時器超時，窗口被置為1，重新進入慢啟動階段?？焖僦貍骱涂焖倩謴途褪窃诎l(fā)送端收到3個或者3個以上的重復ACK，判定包丟失，慢啟動閾值設為當前窗口的一半而不必等待該包的計時器超時，同時接下來執(zhí)行的是擁塞避免算法而不是慢啟動算法，當它們恢復丟包失效時，重傳定時器超時是發(fā)現并恢復丟包的最終機制。圖2.2為文獻27中擁塞控制窗口變化圖；圖2.3為TCP Reno擁塞控制窗口變化圖。 圖2-2 慢啟動和擁塞避免圖2-3 快速重傳和快速恢復2.2.2 源端擁塞控制的研究現狀為了解決高速網絡中TCP連接的性能問題，研究者提出了一些不同的新的解決方案，其中

51、對端節(jié)點的研究成為一個熱點28。源端節(jié)點的改進主要集中在控制擁塞窗口的大小和發(fā)送速率等方面。有很多大大地提高網絡性能的擁塞控制端算法被提出。這些新的端算法雖然采用不同的窗口控制機制，但最終目的都是快速響應網絡的擁塞，及時增加和減少擁塞窗口，提高吞吐量，達到高效率的鏈路使用等。最近出現的一些新協(xié)議主要有：1) Scalable TCP(STCP)STCP協(xié)議是Tom Kelly于2003年提交給PFLDnet的以穩(wěn)定性著稱的面向高帶寬時延乘積網絡的新協(xié)議。STCP是個典型的MIMD（積式增加積式減少）協(xié)議15。它的設計思想是通過修改TCP的窗口增加和減少參數來調整發(fā)送窗口大小，STCP算法仍以丟

52、包為擁塞信號，和傳統(tǒng)TCP擁塞控制相比，窗口增加變得更快，窗口減少變得更緩和。該算法在擁塞避免算法是收到新的包： (2-1)收到重復三個包： （2-2）每次丟包后窗口的調整周期為，因此源端提高一倍的發(fā)送速率需要大約70個RTT；該算法可以更好的利用歷經短暫擁塞的高速廣域網的帶寬。2) HighSpeed-TCP(HSTCP) HSTCP協(xié)議14是Sally Floyd等人于2003年2月遞交給IETF的為克服傳統(tǒng)TCP在高速網絡下的局限性而提出的一種實驗性的高速TCP協(xié)議。傳統(tǒng)的TCP擁塞控制算法在丟包率至少的環(huán)境下才能正常工作，擁塞窗口cwnd和丟包率p之間的關系為，HSTCP算法正是從擁塞

53、窗口和丟包率之間的約束關系出發(fā)，采用了更加侵略性的窗口增加和更加保守的窗口減少模式。考慮到光纖鏈路的最小丟包率為,為了能充分利用10Gbps的網絡帶寬，給出了窗口和丟包率的一個新關系,同時增加了三個參數：、,其默認值分別為38，83000和,若當前窗口小于時HSTCP使用與傳統(tǒng)TCP相同的響應函數；反之，HSTCP使用自己的響應函數。HSTCP使用變動的擁塞窗口調節(jié)參數，保證了在不同擁塞程度變化的網絡中也可正常工作，提高了算法在高速網絡下的魯棒性。在擁塞避免階段，算法表述如下：收到新的包 （2-2）收到三個重復包 （2-3）若當前窗口小于時=1，=0.5。若當前窗口大于 （2-4） （2-5）

54、 （2-6）3) SQRT TCP SQRT TCP28協(xié)議是由Tomoya HATANO等人提出的新協(xié)議。算法提出的新機制可以同時提高RTT公平性和TCP友好性且在大瓶頸鏈路上還能有效的利用鏈路帶寬。它的設計思想是：收到新的包則；收到重復三個包則；、 、 的值分別設定為1.25、15、-0.5、0.5。和HSTCP類似，當擁塞窗口小于高速算法的閾值時，采用傳統(tǒng)TCP的擁塞控制機制；當擁塞窗口大于高速算法的閾值，則采用SQRT TCP的擁塞控制機制。因此，SQRT TCP協(xié)議的擁塞控制機制高速環(huán)境表示如下：收到新的包 （2-7）收到重復三個包 （2-8）4) Africa TCP該協(xié)議是個自適

55、應的、公平的、快速增長的TCP擁塞控制機制，通過使用一個延遲的度量來確定瓶頸鏈路是否有擁塞，如下表示擁塞程度用表示 （2-9）是對網絡隊列延遲的一個估計。擁塞度量參數是個常量，通常設為比1大的實數，在算法中設為1.65。擁塞避免階段算法如下當時 （2-10）當時 （2-11）表示高速環(huán)境窗口增加量。2.2.3 擁塞控制鏈路算法要完全依賴實現在源節(jié)點系統(tǒng)上的策略與算法是很難滿足諸如QoS這樣復雜的應用要求的。于是開始將部分研究注意力轉向網絡中的路由等中間節(jié)點設備，期望通過增強他們的功能來實現源端無法達到的技術目標。就擁塞控制而言，網絡鏈路中間節(jié)點有可能更及時，甚至提前準確了解網絡的擁塞狀態(tài)，并依

56、此實施有效的資源管理策略，使網絡能有效地避免擁塞或盡早從嚴重的擁塞狀態(tài)中恢復過來。對路由器功能的擴展要受繼承性和延續(xù)性的限制，否則將影響技術的實用性。事實上，現有的路由器擴展功能，主要包括調度和隊列/緩存管理，并沒有與Internet將流狀態(tài)信息保存在源端的早期設計理念相沖突。調度(scheduler)直接管理輸出鏈路的帶寬資源，而隊列/緩存管理通過控制緩存與隊列的占有間接影響帶寬的分配。管理隊列長度的傳統(tǒng)方法是對每個隊列設置一個最大值(以包為單位)，然后接受包進入隊列直到隊長達到最大值，接下來到達的包就要被拒絕進入隊列直到隊長下降，這種技術也就是傳統(tǒng)的“尾丟棄”(Drop-Tall)算法。由

57、于這種方法是在隊列滿了之后被迫丟包，因此稱為被動式隊列管理(PQM)，雖然Drop-Tail算法在當前Internet上得到了廣泛的使用，但其存在幾個重要問題29。1) “死鎖”(lock-out)現象:在某些情況下，由于同步或其他定時作用的結果，Drop-Tail算法會讓某個流或者少數幾個流獨占隊列空間，阻止其他流的包進入隊列。2) 滿隊列(full queues)問題:由于Drop-Tail只有在隊列滿時才會發(fā)出擁塞信號，因此會使得隊列在相當長時間內處于充滿或幾乎充滿)的狀態(tài)。而隊列管理最重要的目標之一就是降低穩(wěn)定狀態(tài)下隊列的長度，因為端到端的延遲主要就是由于在隊列中排隊等待造成的。3)

58、全局同步(global synchronization)問題:由于Internet上到達路由器的包往往是突發(fā)的。如果隊列是滿的或者幾乎是滿的，就會導致在短時間內連續(xù)大量的丟包。而TCP流具有自適應特性，源端發(fā)現包丟失就急劇地減小發(fā)送窗口，包到達速率就迅速下降，于是網絡擁塞得以解除，但源端得知網絡不再擁塞后又開始增加發(fā)送速度，最終又造成網絡擁塞。在當前的Internet上，丟包是對端節(jié)點進行擁塞通知的主要機制，解決被動式隊列管理問題的方法便是在隊列滿之前丟包，這樣端節(jié)點便能在隊列溢出前對擁塞作出反應。這種方法便稱為主動式隊列管理(AQM)。它使得路由器能夠控制在什么時候丟包和丟多少包，從而有效地

59、管理隊列長度，以支持端到端的擁塞控制。AQM的主要優(yōu)點是：1) 減少網關的報文丟失使用AQM可以保持較小的隊列長度，從而增強網絡中間節(jié)點容納突發(fā)流量的能力。2) 減小報文通過網關的延遲減小平均隊列長度可以有效地減小報文在網絡設備中的排隊延遲。3) 避免lock-out行為的發(fā)生302.2.4 鏈路擁塞控制研究現狀鏈路算法的研究目前集中在主動隊列管理(Active Queue Management，簡稱AQM)。和傳統(tǒng)的“隊尾丟棄(Drop-Tail)”相比，AQM在網絡設備的緩沖溢出之前就丟棄或標記報文31。AQM的代表算法是RED(Random Early Detection)8。研究表明，

60、RED算法比Drop-Tail具有更好的性能。在RFC2309中，強烈推薦使用RED作為今后的標準。但是進一步研究發(fā)現，RED的性能對算法的參數設置十分敏感，至今沒有在Internet中得到廣泛的使用。最近出現的一些新的AQM算法主要有：1) 隨即早期檢測算法RED最早提出的AQM算法是隨機早期檢測(RED)算法，也是目前最常用的一種AQM算法。RED的基本思想是路由器通過監(jiān)控隊列的平均長度來探測擁塞，一旦發(fā)現擁塞逼近，就隨機地選擇源端來通知擁塞，使它們在隊列溢出之前降低發(fā)送數據速率，以緩解網絡擁塞。RED算法主要包括兩步，首先計算平均隊列長度，然后計算丟棄包的概率。RED在計算平均隊長時，采

61、用了類似低通濾波器帶權值的方法 （2-12）其中，為權值，為采樣測量時實際隊列長度。從而“過濾”掉由于Internet數據的突發(fā)性導致的短期隊長變換，盡量反映長期的擁塞變化。權值相當于低通濾波器的時間常數，它決定了路由器對輸入流量變化的反應程度，計算平均隊長的目的就是為了反映擁塞程度并據此來計算丟包概率。RED有兩個與隊列長度相關的闡值：和。當有數據包達到路由器時，RED計算出平均隊長，然后計算丟包率。若 （2-13）是最大丟包率。再對丟包率做進一步調整： （2-14）是上一次丟包開始到現在連續(xù)進入隊列的包的數量。2) 自適應RED算法ARED自適應RED算法(adaptive RED，ARED)9。ARED的基本思想就是通過檢查平均隊長的變化來決定RED是應更激進還是更保守，從而盡量保持平均隊長在和。之間。具體地說，如果平均隊長是在附近振蕩，說明擁塞控制太激進了，那么就減小 （2-15）如果在附近振蕩，說明擁塞控制太保守了，那么就增大 （2-16）ARED是對RED改動很小的一種算法，它保留了RED的基本結構，只需調節(jié)參數，從而保持平均隊長在和之間，消除了RED的隊列延時