畢業(yè)論文----tcp擁塞控制機制定量性能分析

1、<p><b>　　畢業(yè)設計（論文）</b></p><p>　　題 目：TCP擁塞控制機制定量性能分析 </p><p>　　指導教師： XXXX 職稱： X教授 </p><p>　　學生姓名： XXXX 學號： 20xxxxxxx </p>

2、<p>　　專 業(yè)： 計算機科學與技術 </p><p>　　院（系）： 信息工程學院 </p><p>　　完成時間： </p><p><b>　　年

3、5 月 22日</b></p><p>　　畢業(yè)設計（論文）任務書</p><p>　　附表一 題目來源：指導老師推薦</p><p>　　此表指導教師填后、復印，指導教師、學生各保存一份，交院教學辦一份</p><p>　　畢業(yè)設計（論

4、文）開題報告</p><p><b>　　附表二</b></p><p>　　畢業(yè)設計工作中期檢查Ⅰ</p><p>　　附表三 2007年 4 月 6 日</p><p>　　此表學生填寫，指導教師給出評語后，復印件于第五周

5、交院教學辦公室。</p><p>　　畢業(yè)設計工作中期檢查Ⅱ</p><p>　　附表四 2007年 5 月 9 日</p><p>　　指導教師組織學生口頭匯報后，學生填寫該表，教師給出評語后，于第十周交院教學辦公室。</p><p>　　

6、TCP擁塞控制機制定量性能分析</p><p><b>　　摘要：</b></p><p>　　網絡擁塞問題一直困擾著因特網，隨著網絡信息技術的迅速發(fā)展，新的網絡應用對網絡擁塞控制策略提出了更高的要求。目前，TCP協(xié)議承載著因特網超過70%的傳輸流量，TCP擁塞控制機制可以有效地改善網絡擁塞現象。本文主要研究幾種常見的TCP擁塞控制算法，借助于網絡模擬器NS2，對這幾

7、種常用算法的性能進行定量分析，并給出相應的合理建議，以便改進算法，取得更好的網絡性能。</p><p>　　論文首先介紹了對TCP擁塞控制算法進行研究的必要性，接著闡述了TCP擁塞控制算法的相關基礎知識，包括網絡擁塞的定義、成因，以及TCP擁塞控制算法的思想。</p><p>　　然后介紹了常用的TCP擁塞控制算法：Tahoe、Reno、NewReno、SACK和Vegas TCP。并對這

8、些擁塞控制算法進行了詳細分析，剖析了這些算法對擁塞現象進行控制的機制，包括慢啟動、擁塞避免、快速重傳、快速恢復，以及加入PACK (Partial ACK)和SACK(Selective ACK)的快速恢復等等。</p><p>　　為了比較這些算法的性能，在NS2網絡模擬器環(huán)境下，我們以數據包丟失作為網絡擁塞的信號，對Tahoe、Reno、NewReno和SACK算法進行了模擬實驗。并且對仿真結果進行了分析和比

9、較，結果證明：加入了PACK和SACK的快速恢復算法，可以使TCP更快地從網絡擁塞中恢復到正常工作狀態(tài)。</p><p>　　最后，對TCP擁塞控制算法做了總結，并對將來的工作進行了展望。</p><p><b>　　關鍵詞：</b></p><p>　　擁塞控制 慢啟動 擁塞避免 快速重傳 快速恢復</p><p>　

10、　Quantitative analysis on the performance of TCP congestion control mechanism</p><p>　　Abstract: </p><p>　　The Internet has suffered from the long-term problem of congestion at all times. With t

11、he rapid development of information technology, more careful-designed network congestion control algorithm is required. According to the statistic collected in recent years, TCP carries over 70% Internet traffic. And TCP

12、 congestion control mechanisms can improve congestion problem in the Internet effectively. In the thesis, we research on several common TCP congestion control algorithms，analyze the performanc</p><p>　　This

13、 thesis first introduces the necessity and importance of the network congestion control. And then, the thesis gives the basic concepts of network congestion, including the definition and cause of congestion and the think

14、ing of TCP congestion control algorithms.</p><p>　　Then, the thesis introduces five common TCP congestion control algorithms: Tahoe, Reno, NewReno, SACK and Vegas TCP, analyzes them in detail and discusses

15、the congestion control mechanisms used in them, which are slow-start, congestion avoidance, fast retransmit, fast recovery, fast recovery with PACK and SACK.</p><p>　　In order to compare the performance of t

16、hese algorithms, we use the loss of packets as the signal of network congestion and do simulation on Tahoe, Reno, NewReno and SACK algorithms in the environment of NS2 network simulator. Finally, we conclude that SACK an

17、d NewReno TCP perform better than Reno and Tahoe TCP, especially when multiple packets are dropped from a window of data. </p><p>　　Lastly, the thesis gives the conclusion and prospect.</p><p>　

18、　Key Words:</p><p>　　Congestion Control Slow Start Congestion Avoidance Fast Retransmit Fast Recovery</p><p><b>　　目錄</b></p><p><b>　　前言1</b></p>

19、<p><b>　　1．緒論1</b></p><p><b>　　1.1 擁塞1</b></p><p>　　1.1.1 基本概念1</p><p>　　1.1.2 產生原因1</p><p>　　1.2 擁塞控制2</p><p>　　2．TCP

20、擁塞控制3</p><p>　　2.1 TCP協(xié)議簡介3</p><p>　　2.2 TCP擁塞控制所要解決的主要問題4</p><p>　　2.3 TCP擁塞控制涉及到的參數4</p><p>　　2.4 TCP擁塞控制機制4</p><p>　　2.5 TCP擁塞控制算法5</p><

21、;p>　　2.5.1 Tahoe5</p><p>　　2.5.2 Reno6</p><p>　　2.5.3 NewReno7</p><p>　　2.5.4 SACK8</p><p>　　2.5.5 Vegas9</p><p>　　2.6 TCP擁塞控制算法的特點9</p>&l

22、t;p>　　2.7 TCP擁塞控制算法存在的主要問題9</p><p>　　2.8 TCP擁塞控制算法的改進10</p><p>　　3．網絡仿真軟件NS-211</p><p>　　3.1 NS-2簡介11</p><p>　　3.2 使用NS-2進行網絡模擬的方法和一般過程11</p><p>&l

23、t;b>　　4．仿真12</b></p><p>　　4.1 丟一個包情況下TCP實現的比較13</p><p>　　4.2 丟兩個包情況下TCP實現的比較14</p><p>　　4.3 丟三個包情況下TCP實現的比較16</p><p>　　4.4 丟四個包情況下TCP實現的比較18</p>&l

24、t;p>　　4.5 仿真小結20</p><p>　　5．結論及今后的工作20</p><p><b>　　5.1 結論20</b></p><p>　　5.2 今后的工作21</p><p><b>　　致謝22</b></p><p><b>　

25、　參考文獻23</b></p><p><b>　　附錄24</b></p><p><b>　　前言</b></p><p>　　因特網最初源于美國國防部的ARPANET，其最大特點是采用無連接的端到端的包交換服務。在過去的十年中，因特網逐步發(fā)展成為互聯全球的網絡，它使得用戶在世界范圍內進行通信成為可能。

26、隨著因特網的迅猛發(fā)展，它給人類社會帶來了巨大的變革。但就在因特網深刻影響人類歷史發(fā)展進程的同時，因特網自身的發(fā)展卻面臨著種種困難，其中之一就是網絡擁塞。從因特網誕生起網絡擁塞就與其如影隨形。雖然因特網的相關技術日漸成熟，但網絡擁塞卻仍未很好解決，反而隨著因特網的規(guī)模、用戶和應用的急劇增加，網絡擁塞問題日益突出。因此，如何進行網絡擁塞避免及控制，提高網絡服務質量是非常重要且亟待解決的問題。</p><p>　　目前

27、，端到端傳輸協(xié)議TCP承載著互聯網的絕大多數業(yè)務，其擁塞避免和控制機制是保證因特網穩(wěn)定性的重要因素，可以說，今天因特網的成功很大程度上得益于TCP擁塞控制算法的引進，因此，對TCP擁塞控制算法進行深入的研究具有重要的理論和應用價值。</p><p>　　為了尋找擁塞控制的方案，科研工作者進行了不懈的努力:1988年Jacobson針對TCP在網絡擁塞控制方面的不足，提出了慢啟動(Slow Start)和擁塞避免(

28、Congestion Avoidance)算法；1990年出現的Reno TCP版本則增加了快速重傳(Fast Retransmit)和快速恢復(Fast Recovery)以提高TCP傳輸的頑健性；NewReno TCP增加了恢復應答(Recovery ACK)以提高TCP帶寬恢復能力等等。經過近二十年的發(fā)展，TCP擁塞控制算法己經擁有多個改進版本，TCP協(xié)議的傳輸性能也因此得到了不斷的提高。</p><p>

29、　　在這樣的背景下，通過某種途徑對這些TCP擁塞控制算法進行分析比較，并針對比較過程中出現的問題進行研究以改善網絡性能，就顯得尤為重要。本文著重于深入理解幾種常見的TCP擁塞控制算法，并針對擁塞控制算法暴露出的一些問題，提出合理的建議，以此來改善當前網絡擁塞的狀況。</p><p><b>　　1．緒論</b></p><p><b>　　1.1 擁塞<

30、;/b></p><p>　　1.1.1 基本概念</p><p>　　在某段時間，若對網絡中某一資源的需求超過了該資源所能提供的可用部分，網絡的性能就要變壞，這種情況就叫做擁塞（Congestion）。網絡中發(fā)生擁塞，會導致吞吐量減小，如果用戶仍不斷提出對網絡資源的需求，就會進一步增加網絡的負擔，嚴重時會發(fā)生“擁塞崩潰”(Congestion Collapse)現象。一般來說，擁塞

31、崩潰往往發(fā)生在網絡負載的增加導致網絡效率降低的時候。</p><p>　　1.1.2 產生原因</p><p>　　擁塞發(fā)生的主要原因在于:網絡提供的資源不足，以及網絡資源使用不當，以至于不能滿足用戶對網絡資源的需求。這些資源包括緩存空間、鏈路帶寬容量和中間節(jié)點的處理能力等。下面將詳細說明網絡資源與網絡擁塞的關系。</p><p>　　(1) 存儲空間不足。當一個端

32、口收到幾個輸入端的報文時，接收的報文就會在這個端口的緩沖區(qū)中排隊。如果沒有足夠的存儲空間存儲，當緩沖區(qū)占滿時，報文就會被丟棄。適當增加存儲空間可以緩解擁塞，如果過于增加存儲空間，報文會因在緩沖區(qū)中排隊時間過長而超時，導致源端重發(fā)，從而進一步加重網絡擁塞。如圖1-1描述了過多的分組訪問同一個交換機的緩存所發(fā)生的擁塞現象。假設通信網絡中節(jié)點2，3，5同時發(fā)送數據分組給節(jié)點1，且分組的聚合速率大于節(jié)點1往外發(fā)送分組的速率，則一定會有分組儲存在

33、節(jié)點1的緩沖區(qū)，若這種情況持續(xù)較長時間的話，節(jié)點1的緩沖區(qū)會被占滿，隨后的分組就被丟棄。當目的端發(fā)現有分組丟失時，要求源端重發(fā)，這樣更多的分組涌向節(jié)點1，從而更加重擁塞。</p><p>　?。?）帶寬容量不足。低速鏈路對高速數據流的輸入也會產生擁塞。根據香農信息理論，任何信道帶寬最大值，即信道容量可以這樣計算：C=BLog2(1+S/N)(N為信道白噪聲的平均功率，S為信源的平均功率，B為信道帶寬)。所有信源發(fā)

34、送的速率R必須小于或等于信道容量C。如果R>C，則在理論上無差錯傳輸就是不可能的，并會在網絡低速鏈路處形成帶寬瓶頸，當其滿足不了通過它的所有源端帶寬要求時，網絡就會發(fā)生擁塞。</p><p>　?。?）處理器處理能力弱、速度慢。如果路由器的CPU在執(zhí)行排隊緩存，更新路由表等功能時，處理速度跟不上高速鏈路，也會產生擁塞。同樣，低速鏈路對高速CPU也會產生擁塞。</p><p>　　要避

35、免擁塞的發(fā)生，對以上3點原因需綜合考慮，合理分配和使用網絡資源。例如，提高鏈路速率而不增強處理器的處理能力，只會轉移網絡瓶頸，而不能避免擁塞。所以擁塞往往也是網絡系統(tǒng)各部分資源不匹配、不協(xié)調的結果。擁塞一旦發(fā)生往往會形成一個不斷加重的過程。如果路由器沒有空余的緩存，它就必須丟棄新到的數據包。當數據包丟棄時，源端超時計時器會超時，要求重傳該包。由于沒有得到確認，源端只能保留數據包，結果緩存會進一步消耗，加重擁塞。因此，擁塞控制是一個動態(tài)的

36、、全局性的復雜過程，涉及到所有的主機、所有的路由器，以及與降低網絡傳輸性能有關的所有因素。</p><p><b>　　1.2 擁塞控制</b></p><p>　　為了最大限度地利用資源，使網絡工作在輕度擁塞狀態(tài)是最為理想的，但這增加了滑向擁塞崩潰的風險，因此需要一定的擁塞控制機制來加以約束和限制。</p><p>　　為了便于闡述擁塞控制

37、機制的內涵，我們首先用圖1-2來描述擁塞現象。當網絡負載較小時，吞吐量基本上隨著負載的增長而增長，呈線性關系，響應時間增長緩慢。當負載達到網絡容量時，吞吐量呈現出緩慢增長，而響應時間急劇增加，這一點稱為Knee。如果負載繼續(xù)增加，路由器就開始丟包，當負載超過一定量時，吞吐量開始急劇下降，這一點稱為Cliff。</p><p>　　擁塞控制機制包含擁塞避免(Congestion Avoidance)和擁塞控制(Co

38、ngestion Control)兩種策略。前者的目的是使網絡運行在Knee附近，避免擁塞的發(fā)生；而后者則是使得網絡運行在Cliff的左側區(qū)域。前者是一種“預防”措施，維持網絡的高吞吐量、低延遲狀態(tài)，避免進入擁塞；后者是一種“恢復”措施，使網絡從擁塞中恢復過來，進入正常的運行狀態(tài)。擁塞控制能夠有效地預防死鎖的發(fā)生，提高網絡的性能，其作用不言而喻。在下一章節(jié)，我們將詳細介紹TCP擁塞控制機制。</p><p>&l

39、t;b>　　2．TCP擁塞控制</b></p><p>　　2.1 TCP協(xié)議簡介</p><p>　　TCP(Transmission Control Protocol)協(xié)議是完成端到端信息傳輸的傳輸層協(xié)議，是TCP/IP協(xié)議族的重要成員。TCP協(xié)議主要由差錯控制機制和擁塞控制機制組成，它能夠自動適應網絡狀況的變化。</p><p>　　TCP協(xié)

40、議引入差錯控制機制的目的是保障端到端傳輸的可靠性，為無連接的IP網絡提供基于連接的傳輸服務。</p><p>　　TCP擁塞控制機制的意義更為重大，它可以根據網絡狀況對發(fā)送速率進行調節(jié)，避免擁塞的擴大，這使得互聯網絡的正常運行成為可能。它所采用的擁塞控制算法本質上是一種窗口上限可變的滑窗(Sliding-Window)式流量控制方法，是對滑窗流控算法的繼承和發(fā)展。傳統(tǒng)的滑窗式流控算法的窗口上限是固定的，發(fā)送端每發(fā)

41、送一個報文其發(fā)送窗口減小一個單位，而每接收到一個報文的確認，發(fā)送窗口增加一個單位，這樣終端在一個輪次中能夠發(fā)送報文的最大個數是確定的，因此，在鏈路帶寬充足的情況下，發(fā)送端的傳輸能力將受到發(fā)送窗口上限的限制。TCP流控算法對傳統(tǒng)的滑窗算法進行了擴展，根據網絡狀況對窗口上限進行調節(jié)。在TCP算法中，窗口上限由發(fā)送端的發(fā)送窗口和接收端的通知窗口共同決定(取兩者中的最小值)。這樣，在網絡正常工作時，TCP發(fā)送端可以通過增大窗口上限盡可能多地占用

42、網絡空閑帶寬；而當網絡發(fā)生擁塞時，TCP發(fā)送端可以通過減小發(fā)送窗口上限的方式降低發(fā)送速率，從而起到緩解擁塞的作用。</p><p>　　2.2 TCP擁塞控制所要解決的主要問題</p><p>　　要改善TCP傳輸的穩(wěn)定性，減少擁塞的發(fā)生，或者要與非標準TCP應用在同一網絡中共存，采取一定的TCP擁塞控制機制是必要的。TCP擁塞控制需要解決的主要問題有:</p><p&

43、gt;　　第一、滿足低的報文丟棄率的要求，提高帶寬利用率。</p><p>　　第二、高TCP傳輸的穩(wěn)定性，減少網絡狀態(tài)的振蕩。</p><p>　　第三、保證TCP公平，即TCP友好特性。</p><p>　　2.3 TCP擁塞控制涉及到的參數</p><p>　　TCP擁塞控制機制是通過控制一些重要參數的改變來實現的。用于TCP擁塞控制的

44、參數主要有:</p><p>　　(1)擁塞窗口(cwnd)：是擁塞控制的關鍵參數。它描述發(fā)送端在擁塞控制情況下一次最多能發(fā)送的數據包數量。</p><p>　　(2)通知窗口(awnd)：是接收端給發(fā)送端預設的發(fā)送窗口大小，它只在TCP連接建立的初始階段起作用。</p><p>　　(3)發(fā)送窗口(win)：是發(fā)送端每次實際發(fā)送數據的窗口大小。</p>

45、<p>　　(4)慢啟動門限(ssthresh)：是擁塞控制中用來限制發(fā)送窗口大小的門限值，它是慢啟動階段和擁塞避免階段的分界點，初始值設為65535字節(jié)或awnd的大小。</p><p>　　(5)回路響應時間(RTT)：一個TCP數據包從發(fā)送端發(fā)送直至發(fā)送端收到確認的時間間隔。</p><p>　　(6)重傳超時時長(RTO)：描述數據包從發(fā)送到失效的時間間隔，是判斷數據

46、包丟失與否、網絡是否擁塞的重要參數，通常設為2RTT或5RTT。</p><p>　　下面將介紹TCP擁塞控制機制是如何改變上述參數以達到控制網絡擁塞、提高網絡性能的目的的。</p><p>　　2.4 TCP擁塞控制機制</p><p>　　TCP的擁塞控制機制是由慢啟動、擁塞避免、快速重傳和快速恢復四個核心算法組成的。慢啟動階段用于快速探測并占有網絡可用帶寬；擁

47、塞避免階段是數據傳輸的主要時段；快速重傳則完成了丟失報文的重傳；而快速恢復避免了由于過度地減小發(fā)送窗口而導致網絡性能下降的發(fā)生，使得網絡迅速從擁塞狀態(tài)中恢復。圖2-1描述了TCP擁塞控制中慢啟動和擁塞避免兩個階段的動態(tài)情況。有關它們的具體實現將在下一節(jié)詳細闡述。</p><p>　　2.5 TCP擁塞控制算法</p><p>　　TCP協(xié)議經過多年的發(fā)展，有了多種具體的實現，其中包括Tah

48、oe、Reno、NewReno、SACK和Vegas TCP。運行在主機中的這些實現使得TCP連接在網絡發(fā)生擁塞時回退，并對網絡中的擁塞信號進行響應，正是這些改進的TCP實現的擁塞避免和擁塞控制算法防止了今天網絡的擁塞崩潰。下面詳細介紹這些TCP實現以及運用于這些實現中的擁塞避免和擁塞控制算法。</p><p>　　2.5.1 Tahoe</p><p>　　Tahoe算法是最早被提出來的

49、TCP擁塞控制算法，雖然已歷經近二十年，但至今仍被大多數TCP實現所采用。它的一些經典理論也被后來的大多數TCP擁塞控制算法所沿用，為后繼算法奠定了基礎。其核心思想是讓cwnd以指數型增長方式迅速逼進可用信道容量，然后慢慢接近均衡。Tahoe包括慢啟動、擁塞避免和快速重傳三個部分。</p><p>　　(1)慢啟動 </p><p>　　初始時，cwnd值設置為1，每收到一個成功的A

50、CK，則：</p><p>　　cwnd = cwnd + 1</p><p>　　理想情況下，在一個RTT內，發(fā)送端會收到cwnd個成功的ACK。這樣，每隔一個RTT:</p><p>　　cwnd = 2*cwnd</p><p>　　即在慢啟動階段，cwnd以指數型增長，直到cwnd超過ssthresh值。當cwnd>=ssthr

51、esh時，Tahoe進入擁塞避免階段。</p><p>　　慢啟動的目的是避免連接建立時大量突發(fā)數據流可能造成的擁塞。</p><p>　　(2)擁塞避免 </p><p>　　在擁塞避免階段，每收到一個成功的ACK，則：</p><p>　　cwnd = cwnd + 1 / cwnd</p><p>　　因此

52、，每隔一個RTT， cwnd增1。即在擁塞避免階段，cwnd線性增加。</p><p>　　如果發(fā)生超時或者連續(xù)收到3個重復的ACK（簡稱dup ACK），Tahoe就認為網絡發(fā)生了擁塞。</p><p>　　對于超時，ssthresh = max(cwnd/2，2)</p><p><b>　　cwnd =1</b></p>&

53、lt;p><b>　　然后轉入慢啟動。</b></p><p>　　若是收到連續(xù)3個dup ACK，則Tahoe進入快速重傳階段。</p><p>　　可以看到，當算法進入擁塞避免階段后，擁塞窗口的增長趨于平緩，避免了擁塞窗口持續(xù)快速增長可能導致的擁塞。</p><p>　　(3)快速重傳 </p><p>

54、　　在此階段，首先立即重發(fā)丟失的分組，而不必等待重傳定時器超時，同時設置:</p><p>　　ssthresh=max(cwnd/2，2) </p><p><b>　　cwnd =1</b></p><p>　　然后，轉入慢啟動階段?？焖僦貍骷涌炝怂惴ǖ捻憫俣?，減少了重傳超時的發(fā)生。</p><p>　　Ta

55、hoe核心算法可簡單描述為:</p><p>　　for every ack</p><p>　　{if cwnd < ssthresh then</p><p>　　cwnd++ //慢速啟動</p><p>　　else cwnd +=1/cwnd //擁塞避免</p><p><

56、;b>　　}</b></p><p>　　for every loss //快速重傳</p><p>　　{ssthresh =max(cwnd/2，2)</p><p><b>　　cwnd=1</b></p><p><b>　　}</b></p>&l

57、t;p>　　Tahoe算法的提出使得TCP由以前的單純流量控制轉向擁塞控制，它明確地將TCP數據流的發(fā)送過程劃分為三個階段，慢啟動避免了連接建立時突發(fā)數據流對網絡的沖擊；擁塞避免限制了在傳輸過程中無限制的速率增長，避免了由此可能導致的擁塞；快速重傳則加快了發(fā)送端對擁塞的響應速度，使得擁塞能快速地消除。</p><p>　　2.5.2 Reno</p><p>　　Reno算法是對Ta

58、hoe的改進，從上一小節(jié)我們可以看到，在收到連續(xù)3個dup ACK或在超時的情況下，Tahoe設置cwnd為l，然后進入慢啟動階段。這一方面會引起網絡的激烈振蕩，另一方面大大降低了網絡的利用率。針對這個問題，1990年Jacobson在Tahoe的基礎上提出了Reno算法。</p><p>　　Reno算法對Tahoe的改進主要在兩個方面。第一，收到連續(xù)3個dup ACK后，算法不經過慢啟動，而直接進入擁塞避免階

59、段。第二，增加了快速重傳/快速恢復(FR/FR)機制。事實上，每一個dup ACK表明已經有一個數據包離開了網絡，不管它是不是我們所期望的。根據Jacobson的數據守恒理論(見2.5.3小節(jié))，發(fā)送端這時可以向網絡發(fā)送下一個數據包。快速重傳/快速恢復機制就是這樣做的。具體過程為:</p><p>　　(1)收到3個dup ACK進入FR/FR</p><p>　　ssthresh =ma

60、x(cwnd/2，2)</p><p>　　(2)重發(fā)丟失的數據包</p><p><b>　　(3)窗口膨脹</b></p><p>　　cwnd =ssthresh + ndup</p><p>　　ndup為收到的dup ACK數。</p><p>　　(4)當min(awnd， cwnd)

61、足夠大時，發(fā)送新的數據包</p><p>　　(5)當收到非重復的ACK時 cwnd =ssthresh</p><p>　　(6)轉入擁塞避免階段</p><p>　　經過分析，可以看出：Reno在收到3個dup ACK后，就轉入FR/FR，而遇到超時后，Reno和Tahoe一樣進入慢啟動階段?？梢詮腞eno狀態(tài)轉換圖直觀地看到Reno的整個數據傳輸過程。<

62、;/p><p>　　Reno目前被廣泛采用，以其算法的簡單、有效和魯棒性成為TCP擁塞控制算法的主流。針對Reno的局限性，一些新算法如：NewReno，SACK等對其進行了改進。</p><p>　　2.5.3 NewReno</p><p>　　Reno TCP提出的快速恢復算法提高了報文丟失后TCP的吞吐量和頑健性，但是它僅考慮了每次擁塞發(fā)生時只丟失一個報文的情形

63、。然而在實際網絡中，一旦發(fā)生擁塞，路由器會丟棄大量的報文(對于采用Drop Tail的路由器而言，丟棄尤為嚴重)，TCP在一次擁塞中丟失多個報文的情形非常普遍。在這種情況下，采用Reno TCP算法的發(fā)送端多次將cwnd和ssthresh減半，其結果是TCP的發(fā)送速率呈指數降低，系統(tǒng)吞吐量急劇下降，更有甚者，當發(fā)送窗口小于4 時無法有效地觸發(fā)快速重傳，Reno TCP發(fā)送端會陷入僅通過傳輸超時來發(fā)現報文丟失的困境中。</p>

64、<p>　　NewReno在Reno的基礎上對快速恢復算法進行了修改，添加了恢復應答(Recovery ACK)判斷功能，以增強TCP發(fā)送端通過ACK報文信息分析報文傳輸狀況的能力。NewReno使TCP發(fā)送端可以把一次擁塞丟失多個報文的情形與多次擁塞的情形區(qū)分開來，進而在每一次擁塞發(fā)生后擁塞窗口僅減半一次，從而提高了TCP的頑健性和吞吐量。 </p><p>　　恢復應答(Recovery ACK

65、)— 改進的快速恢復算法</p><p>　　為了介紹NewReno中改進的快速恢復算法，首先定義部分應答(Partial ACK，簡稱PACK)和恢復應答(Recovery ACK，簡稱RACK)報文。</p><p>　　把TCP發(fā)送端恢復階段中接收到的ACK報文（非dup ACK)記為ACKx，在接收到ACKx時TCP終端己發(fā)出的序列號(SN)最大的報文記為PKTy，如果ACKx不是

66、PKTy的應答報文則稱報文ACKx為部分應答，即PACK報文；反之，若ACKx恰好是PKTy的應答報文，則報文ACKx被稱為恢復應答，即RACK報文。TCP發(fā)送端接收到恢復應答表明：經過重傳，TCP發(fā)送端發(fā)送的所有報文都己經被接收端正確接收，網絡已經從擁塞中恢復。</p><p>　　經過NewReno改進的快速恢復算法可以描述為以下幾個步驟:</p><p>　　1. 重新定義“恢復階段

67、”，這里把從快速重傳算法發(fā)現丟失報文到TCP發(fā)送端接收到RACK報文的時段稱為恢復階段。</p><p>　　2. 進入恢復階段后，TCP發(fā)送端重傳被認定為丟失的報文，并分別設置ssthresh和cwnd如下：</p><p>　　ssthresh =max(cwnd/2，2) </p><p>　　cwnd = ssthresh + 3*SMSS</

68、p><p>　　3. 當接收到dup ACK后，TCP發(fā)送端按照式子cwnd =ssthresh + ndup對cwnd進行設定(與Reno TCP的設定方式相似)。</p><p>　　4. 當接收到PACK后，TCP發(fā)送端立即重傳PACK所確認報文的下一個報文，擁塞窗口不受影響。</p><p>　　5. 當接收到RACK后，TCP發(fā)送端認為擁塞中所有被丟棄的報文均

69、已被重傳，擁塞結束，設置cwnd為發(fā)生擁塞時的cwnd的一半，最后退出恢復階段，進入擁塞避免階段。</p><p>　　快速恢復是基于“數據包守恒”原則(Conservation of Packets Principle) 的，即同一時刻在網絡中傳輸的數據包數量是恒定的，只有當“舊”數據包離開網絡后，才能發(fā)送“新”數據包進入網絡。重傳丟失的數據包后，不從慢啟動開始的原因是，一個dup ACK不僅意味著有一個包丟失

70、了，而且表示有一個被發(fā)送的數據包離開了網絡，己經在接收端的緩沖區(qū)中，它不再占有網絡資源。</p><p>　　2.5.4 SACK</p><p>　　SACK TCP也是對Reno TCP的擴展，在Reno TCP的基礎上增加了選擇確認SACK (Selective Acknowledgments)和選擇重傳(Selective Retransmission)。當一個窗口內有多個數據包丟

71、失時，SACK TCP增加了SACK選項，允許接收端在ACK中報告其接收到的不連續(xù)(No-Sequential)的報文，這樣，發(fā)送端就能準確地知道哪些數據包被接收端正確地接收。發(fā)送端使用選擇性重傳機制，可以在一個窗口中一次重傳所有從一個窗口中丟失的數據包，從而減少了時延，提高了網絡吞吐量，也使得TCP更快地從擁塞狀態(tài)恢復。</p><p>　　同樣是一個窗口丟多個包的情況，如果沒有SACK，發(fā)送端或者在每個RTT

72、的時間內最多只能重傳一個丟失的包，或者連那些己經被正確接收的報文一起重傳。Reno TCP和NewReno TCP采用的是第一種策略，而Tahoe TCP則采用了第二種。</p><p>　　為了詳細介紹SACK TCP，先引進兩個概念：pipe變量和數據結構scoreboard。pipe的值為TCP發(fā)送端發(fā)出的未被確認的數據包數的估計值；數據結構scoreboard被保存在發(fā)送端，用來記錄上一個SACK選項中記

73、錄的確認報文。</p><p>　　經過SACK TCP改進的快速恢復算法如下:</p><p>　　1. 在快速恢復階段，只有當pipe的值小于cwnd時，發(fā)送端才發(fā)送新數據包或重傳丟失的數據包。發(fā)送端發(fā)送或重傳一個數據包后，pipe值加1；收到一個包含有SACK選項用以報告新的數據被成功接收的dup ACK后，pipe值減1。</p><p>　　2. 當發(fā)送端

74、可以發(fā)送數據包時，它根據scoreboard重傳丟失的數據包，如果沒有數據包丟失，則發(fā)送新的數據包。</p><p>　　3. 如果發(fā)送端收到PACK，pipe值減去2。因為PACK表示兩個數據包離開了網絡，一個是丟失的數據包，另一個是重傳的數據包。</p><p>　　4. 當發(fā)送端收到RACK后退出快速恢復階段。</p><p>　　2.5.5 Vegas<

75、;/p><p>　　Vegas TCP與上述算法有很大不同，它根據TCP連接中的回路響應時間RTT值的改變情況來控制cwnd的大小。如果發(fā)現RTT變大那么就認為網絡發(fā)生擁塞，并開始減小cwnd；如果RTT變小，Vegas就認為網絡擁塞正在解除，則相應增加cwnd。Vegas的最大優(yōu)點在于擁塞機制的觸發(fā)只與RTT的改變有關，而與數據包的具體傳輸時延無關。</p><p>　　Vegas采用的重傳

76、策略也與Tahoe、Reno不同。Vegas能更加及時地重傳丟失的數據包，它不是等到連續(xù)收到3個dup ACK后才進行重傳，而是當收到第一個dup ACK后，比較數據包發(fā)出的時間和當前時間，然后決定是否重發(fā)，這就明顯提高了響應速度。當達到均衡時，Vegas具有零丟包率、穩(wěn)定的窗口大小、滿負荷使用效率等優(yōu)點。</p><p>　　但是Vegas TCP并未能在互聯網上大規(guī)模使用，主要原因是使用Vegas TCP的流

77、在帶寬競爭能力方面不及未使用Vegas TCP的流，從而導致網絡資源使用不公平，而不是算法本身的問題。</p><p>　　2.6 TCP擁塞控制算法的特點</p><p>　　TCP算法最根本的特點是通過累積確認(Cumulative Acknowledgement)的方式獲知已發(fā)送報文的傳輸情況，通過加增大乘減小(Additive Increase Multiplicative Dec

78、rease，即AIMD)的擁塞控制策略對發(fā)送流量進行調節(jié)以避免擁塞的發(fā)生。</p><p>　　累積確認方式使得TCP通信過程具有顯明的周期性：TCP發(fā)送端在發(fā)送窗口允許的范圍內盡可能地發(fā)送報文，在發(fā)送窗口閉合后則暫停發(fā)送處于等待狀態(tài)，直至下一個輪次發(fā)送的開始。這種發(fā)送報文——等待確認——再發(fā)送報文的過程被形象地稱為自時鐘(Self Clock)。</p><p>　　總之，TCP算法通過

79、窗口增長探測網絡可用的傳輸帶寬，當傳輸出現報文丟失時，TCP算法即認為發(fā)送速率己經超過網絡可用帶寬，此時的發(fā)送速率將被作為以后速率調整的參考。TCP算法通過累積確認發(fā)現報文丟失，一旦發(fā)現有報文被丟棄，TCP終端將下調發(fā)送速率，直到丟棄報文被成功傳輸為止。這樣的特性使得TCP的發(fā)送速率的變化具有周期性，同時也為TCP吞吐量的分析提供了便利。</p><p>　　2.7 TCP擁塞控制算法存在的主要問題</p&

80、gt;<p>　　TCP擁塞控制機制在互聯網中發(fā)揮了行之有效的作用，但TCP擁塞控制算法自身存在的問題也是不容忽視的:</p><p>　　(1)端系統(tǒng)從發(fā)生擁塞到實施控制之間有著明顯的時延，而且端系統(tǒng)缺乏對數據傳輸過程的動態(tài)性了解，無法預知網絡資源的使用情況，目前主要是通過降低發(fā)送到網絡的數據流量來減小網絡負載，從而緩解擁塞。</p><p>　　(2)慢啟動算法中存在的問

81、題尤為突出。首先，由于在慢啟動階段發(fā)送端無法了解瓶頸鏈路帶寬，每個RTT內都會將cwnd增加一倍，如果ssthresh較大，那么發(fā)送端窗口增加到足夠大時，會丟失接近一半的數據包；其次，慢啟動是按照事先設定好的參數開始數據傳輸的，cwnd和 ssthresh一般分別取1個和64個數據包大小，TCP連接在經歷擁塞后也使用慢啟動算法重新開始通信，在網絡可用帶寬較大時，會造成網絡資源利用率降低及延遲增加；再次，TCP基于窗口的擁塞控制機制對于傳

82、輸大批量文件具有良好的適應性，但是為www應用等短小數據流服務時性能較差，往往需要幾個RTT時間探測合適的網絡帶寬，傳輸延遲較大。</p><p>　　(3)公平性問題。Internet采取的基于源端的擁塞控制策略是不公平的，TCP擁塞控制中的公平性問題主要表現在以下兩個方面:</p><p>　　1)TCP中擁塞窗口大小可以表示為RTT的函數，比如，慢啟動階段cwnd隨RTT呈指數增長，

83、擁塞避免階段cwnd隨RTT線性增長，這樣對于長延遲的連接來講，由于其窗口增長速度慢，因而在同樣的條件下獲得的帶寬也就越少，特別是在慢啟動過程中，RTT長的連接的劣勢就表現得更為明顯；</p><p>　　2)TCP提供端到端的可靠傳輸服務，在檢測到擁塞后會自覺地降低發(fā)送速率，隨著網絡中不遵守TCP協(xié)議的各種數據流的出現，TCP流在與這些數據流共存時，其競爭力較弱，往往會喪失應有的帶寬，因此公平地共享帶寬也是一個

84、需要迫切關注的問題。</p><p>　　針對以上TCP擁塞控制中存在的問題，近年來，許多科研人員對這些問題進行了方方面面的研究和改進，以便更好地符合各種網絡應用的需要，適應網絡動態(tài)變化的特性，使網絡運行在最佳狀態(tài)。</p><p>　　2.8 TCP擁塞控制算法的改進</p><p>　　對于TCP擁塞控制存在的問題，目前主要針對以下幾個方面進行了改進:</

85、p><p>　　(1)針對不必要的超時重傳和快速重傳</p><p>　　當前的TCP應用主要有兩種重傳機制：快速重傳和超時重傳。當TCP發(fā)送端收到3個ACK確認信息時就會觸發(fā)快速重傳機制，此時發(fā)送端重傳丟失的數據包并且將cwnd減半。這種情況下，TCP流往往能夠很快從丟包中恢復過來，重新回到原先的發(fā)送速率。但如果TCP發(fā)送端沒有收到3個ACK信號，例如cwnd值小于4，那么TCP發(fā)送端則需要

86、等待相當長時間，以便超時重傳。這樣，小窗口的TCP流就很容易陷入不必要的超時重傳，使其吞吐量大大下降。</p><p>　　為了避免這種不必要的超時重傳，一種改進辦法就是只要TCP發(fā)送端收到一個或兩個ACK信號，并且如果通知窗口awnd允許，便繼續(xù)發(fā)送新的數據包。這是因為只要收到ACK信號，就表明有數據包已經離開網絡被接收端接收了，而此時發(fā)送端還無法判斷數據包是否被丟棄，根據“數據包守恒”原則，發(fā)送端就可以繼續(xù)發(fā)

87、送新的數據包。</p><p>　　(2)針對亂序包和延遲包引起的重傳</p><p>　　在不少情況下，TCP發(fā)送端推斷認為數據包被丟棄了，例如超時計時器過早到時了(事實上數據包或者ACK并沒有丟失，只要再等待一會便可收到)，發(fā)送端便毫無必要地重傳了數據包，而實際上數據包并沒有被丟棄。類似地，如果由于數據包的亂序導致發(fā)送端接收到3個ACK信號，便會觸發(fā)快速重傳，TCP源端也沒有必要地重發(fā)

88、了數據包，并減小了擁塞窗口，對于前者，雖然可以通過更為精確地調節(jié)超時時鐘來減少不必要的超時重傳，但要完全避免卻是不可能的。同樣，對于后者，雖然可以通過提高快速重傳算法的性能來減少不必要的快速重傳，但也不可能完全避免。</p><p>　　為了使得在不必要的超時重傳和快速重傳情況下，TCP性能更加具有魯棒性，一種方法就是出現這些情況時向TCP發(fā)送端反饋有關的信息。這個工作已經由D-SACK擴展(duplicate-

89、SACK extension)完成了。D-SACK擴展允許TCP接收端利用SACK選項來通報已收到的重復的數據包，從而TCP發(fā)送端能夠正確地推斷出接收端是否收到了重復的數據包，以此來避免不必要的重傳。</p><p>　　由此可見，目前還沒有一種TCP擁塞控制算法的設計和實現在所有的環(huán)境中都是“最好的”?，F有擁塞控制的思路、方法和技術在不同環(huán)境中面臨著挑戰(zhàn)，它們還有許多需要改進的地方。</p>&l

90、t;p>　　3．網絡仿真軟件NS-2 </p><p>　　由于網絡的復雜性，目前網絡技術的研究很大程度上僅限于理論研究，在實際上的應用比較困難。隨著計算機技術的發(fā)展，仿真工具在分析和研究復雜網絡中發(fā)揮了很大的作用，所以尋求性能優(yōu)越的仿真工具對于網絡技術的研究有著非常重要的意義。</p><p>　　NS-2(Network Simulator)是由UC Berkely大學開發(fā)的一個

91、基于事件驅動的仿真器。它能近乎真實地模擬網絡環(huán)境在各個層次上的運行，為低成本的實驗提供了一個良好的環(huán)境，能夠方便地對已有的協(xié)議行為進行驗證，比較使用不同的算法對網絡性能造成的影響。</p><p>　　3.1 NS-2簡介</p><p>　　NS-2是面向對象的，基于離散事件驅動的網絡環(huán)境模擬器。它實現了多種網絡協(xié)議的模擬，如傳輸層的TCP、UDP協(xié)議，應用層的FTP、 Telnet、W

92、eb協(xié)議；實現了DropTail、RED等幾種路由器隊列管理機制以及Dijkstra、動態(tài)路由、靜態(tài)路由、組播路由等路由算法。此外，NS-2還支持組播協(xié)議SRM及部分MAC層的協(xié)議。NS-2用C++和Otcl語言編寫而成。它的一個突出優(yōu)點就是它的源代碼全部公開，提供開放的用戶接口，并且容易擴展、配置，用戶可以很方便地將自己開發(fā)的新協(xié)議模塊集成到NS-2環(huán)境中。</p><p>　　3.2 使用NS-2進行網絡模擬

93、的方法和一般過程</p><p>　　進行模擬前，首先要分析模擬涉及哪個層次。NS-2模擬分兩個層次：一個是基于Otcl編程的層次，利用NS-2己有的網絡元素實現模擬，無需對NS-2本身進行任何修改，只要編寫Otcl腳本；另一個層次是基于C++和Otcl編程的層次，如果NS-2中沒有所需的網絡元素，就需要首先對NS-2擴展，添加所需要的網絡元素。這就需要利用分裂對象模型，添加新的C++和Otcl類，然后再編寫Ot

94、cl腳本。這個模擬過程如圖3-1所示。</p><p>　　進行一次模擬過程如下：</p><p>　　(1)編寫Otcl腳本，配置模擬網絡拓撲結構，確定鏈路的基本特性。</p><p>　　(2)建立協(xié)議代理，包括端設備的協(xié)議綁定和通信業(yè)務量模型的建立。</p><p>　　(3)配置業(yè)務量模型的參數，從而確定網絡上業(yè)務量分布。</p

95、><p>　　(4)設置Trace對象。Trace對象能夠把模擬過程中發(fā)生的特定類型的事件記錄在trace文件中。NS-2通過trace文件來保存整個模擬過程。仿真完成后，用戶可以對trace文件進行分析研究。</p><p>　　(5)編寫其他的輔助過程，設定模擬結束時間，至此Otcl腳本編寫完成。</p><p>　　(6)利用NS-2解釋執(zhí)行剛才編寫的Otcl腳本

96、。</p><p>　　(7)分析trace文件，得到有用的數據，也可以使用Nam等工具觀看網絡模擬運行過程。</p><p>　　(8)調整配置拓撲結構和業(yè)務量模型，重新進行上述模擬過程。</p><p><b>　　4．仿真</b></p><p>　　下面我們通過仿真來比較上文提到的Tahoe、 Reno、NewR

97、eno、SACK四種TCP擁塞控制算法，它們都是以丟包作為擁塞信號的。仿真分為四組，TCP分別丟失1、2、3、4個包；每一組仿真都分別運行四種TCP擁塞控制算法。在仿真中它們丟棄相同固定序列號的數據包，以此來比較它們對擁塞響應的情況。</p><p>　　仿真所使用的網絡模型如圖4-1所示，共有五個節(jié)點，四段鏈路，每段鏈路的帶寬和時延都在圖中得以注明，節(jié)點3相當于一個網關(GateWay)，下文提到的網關都是指節(jié)

98、點3。圖中共建立了三條TCP連接，其中節(jié)點0到節(jié)點4的TCP連接是我們所要研究的，而另外兩條連接發(fā)送有限的數據，它們的建立只是為我們所研究的第一條TCP連接創(chuàng)造丟包的條件，以便我們觀察節(jié)點0對丟包現象的反應，從而研究節(jié)點0所采用的擁塞控制機制。仿真數據以包為單位，而不是以字節(jié)為單位，且發(fā)送端發(fā)送的所有數據包大小一致(1000字節(jié))。數據包的序列號SN從0開始計數，發(fā)送端每發(fā)送一個新的數據包，SN增加1，接收端每收到一個數據包就返回一個確

99、認報文ACK。在本仿真中，ACK不與發(fā)送數據包產生沖突，且ACK不丟失。</p><p>　　我們使用網絡仿真軟件NS進行仿真，使用的版本為NS-2.27，安裝在Windows XP系統(tǒng)上。</p><p>　　在四組仿真結果圖形中，橫坐標為時間，以秒為單位，代表了數據包到達或離開網關的時間；縱坐標為數據包的序列號（對100取模，即以100為單位）。圖形中，方塊標示丟失的數據包，小圓點標示

100、被網關收到的ACK，正三角形標示每一個到達或離開網關的數據包。如果數據包經過網關時幾乎沒有經歷排隊時延，那么在圖表中對應產生的兩個正三角形看起來就像一個。沒有被丟棄的數據包在圖表中將產生兩個序列號相同，且共線的正三角形。它們之間的距離代表排隊時延。</p><p>　　4.1 丟一個包情況下TCP實現的比較</p><p>　　在第一組仿真中，四種TCP實現都分別丟了14號數據包。從圖4-

101、2中可以看出，丟包后，Tahoe TCP的恢復需要從慢啟動開始，而Reno、 NewReno和SACK由于加入了快速恢復算法，則可以更平滑地從擁塞狀態(tài)恢復。下面，將根據圖4-2詳細分析四種TCP實現在從擁塞狀態(tài)恢復的過程中窗口的變化。</p><p>　　在Tahoe TCP的仿真結果圖中可以看到， 0到13號數據包成功被接收端接收，擁塞控制窗口cwnd根據慢啟動算法從1指數式增大到15。在第四輪的數據發(fā)送中，T

102、CP發(fā)送端的cwnd為8，前7個數據包都被成功接收，接收端返回7個ACK，cwnd大小由8增加到了15；但第8個數據包(14號)丟失，接收端無法收到確認，但是它仍占用發(fā)送窗口的一個數據包大小，因此TCP發(fā)送端發(fā)送15到28號共14個數據包。接收端收到這些數據包后，返回13號數據包的dup ACK。發(fā)送端收到連續(xù)的3個dup ACK，觸發(fā)快速重傳和慢啟動，將cwnd設置為1，并立刻重傳14號數據包，且將慢啟動門限ssthresh減小為快速

103、重傳前cwnd大小的一半。</p><p>　　圖4-2中Reno TCP與Tahoe TCP的不同在于：收到3個dup ACK后，發(fā)送端的cwnd減半，不進入慢啟動，而是直接進入擁塞避免階段。發(fā)送端收到13號數據包的3個dup ACK后啟動快速重傳和快速恢復算法，將ssthresh減小到7，cwnd的值被設置為ssthresh加3。在快速恢復階段，接收端共收到14個dup ACK， 使得cwnd增大到21，其中

104、有15個數據包(14到28號)沒有被確認，發(fā)送端可以再發(fā)送29-34號共6個數據包。當接收端收到被重傳的14號數據包后返回對28號數據包的確認，發(fā)送端收到這個ACK后退出快速恢復階段，將TCP的擁塞窗口設置為7。</p><p>　　丟一個包的情況下，NewReno和SACK的恢復過程與Reno TCP是一致的。</p><p>　　4.2 丟兩個包情況下TCP實現的比較</p>

105、;<p>　　如圖4-3所示，與前一組仿真相似，在丟失14號和28號兩個數據包后，Tahoe TCP的恢復從慢啟動開始，而Reno、 NewReno和SACK可以較平滑地從擁塞狀態(tài)恢復。下面，根據圖4-3詳細分析四種TCP實現的區(qū)別。</p><p>　　與丟失一個數據包的情況類似，Tahoe TCP收到3個13號數據包的dup ACK后，將cwnd設為1，開始進入慢啟動并重傳數據包14。接收端收到

106、后返回對27號數據包的ACK，發(fā)送端收到ACK后發(fā)送數據包28，29。接收端收到28號數據包后，返回一個28號數據包的ACK。由于對數據包28的確認是對新的數據的確認，因此cwnd 增加1，接收端收到確認后繼續(xù)發(fā)送數據。</p><p>　　在圖4-3中利用快速重傳，Reno發(fā)送端不必等待重傳超時，而是連續(xù)兩次進入快速重傳和快速恢復階段，在連續(xù)兩個RTT時間內兩次將cwnd減半，然后才得以恢復。這個過程極大降低了

107、TCP連接的傳輸效率。</p><p>　　Reno的操作過程和丟失一個包的情形類似，只是由于28號包的丟失，發(fā)送端收到13個而不是14個對13號數據包的重復確認。在接收到最后一個dup ACK后，發(fā)送端的cwnd增加到20，允許發(fā)送29-33號數據包。</p><p>　　由于被重傳的14號數據包成功地被接收端接收，發(fā)送端收到了第一個對27號數據包的確認，退出快速恢復階段，同時設置cwn

108、d為7（由于14號數據包的丟失，cwnd從15降到了7），此時發(fā)送端可以發(fā)送34號數據包。一旦收到對27號數據包第三個重復確認，發(fā)送端再一次進入快速恢復階段，緊接著重傳28號數據包，并將cwnd設置為6（由于已經收到3個dup ACK），此時有7個數據包（28-34號）還沒有得到確認，發(fā)送端已不能發(fā)送任何其他的數據包。在收到第5個和第6個dup ACK時，發(fā)送端cwnd從8增加到9，允許發(fā)送35、36號兩個數據包。</p>