擁塞控制機制與網(wǎng)絡(luò)傳輸服務(wù)質(zhì)量計算機畢業(yè)論文

《擁塞控制機制與網(wǎng)絡(luò)傳輸服務(wù)質(zhì)量計算機畢業(yè)論文》由會員分享，可在線閱讀，更多相關(guān)《擁塞控制機制與網(wǎng)絡(luò)傳輸服務(wù)質(zhì)量計算機畢業(yè)論文（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 課題來源： 指導(dǎo)教師給定 課題研究的目的和意義： 以TCP/IP協(xié)議為基礎(chǔ)的Internet自從20世紀(jì)90年代以來，其網(wǎng)絡(luò)規(guī)模、用戶數(shù)量及業(yè)務(wù)量都呈現(xiàn)爆炸式的增長，新型網(wǎng)絡(luò)應(yīng)用也不斷涌現(xiàn)，網(wǎng)絡(luò)的參數(shù)(如激活的連接數(shù)、回路往返時間)動態(tài)變化，這些使得網(wǎng)絡(luò)擁塞的狀況愈加嚴(yán)重和復(fù)雜。擁塞容易造成傳輸時延和吞吐量等服務(wù)質(zhì)量(QoS)性能指標(biāo)下降，嚴(yán)重影響帶寬、緩存等網(wǎng)絡(luò)資源的利用率。因此，擁塞控制一直是網(wǎng)絡(luò)研究領(lǐng)域的熱點問題。 網(wǎng)絡(luò)擁塞控制的目的不是要完全避免擁塞的發(fā)生，而是通過擁塞控制，提高網(wǎng)絡(luò)的性能及數(shù)據(jù)處理能力，保障網(wǎng)絡(luò)的穩(wěn)定和持續(xù)運行，并且保證數(shù)據(jù)傳輸?shù)墓叫?。我們知道?/p>

2、網(wǎng)絡(luò)擁塞的根本原因在于端系統(tǒng)發(fā)出的數(shù)據(jù)超出了網(wǎng)絡(luò)的處理能力，而擁塞控制算法的基本思想則是解決這一問題，通常的方法就是TCP擁塞控制算法。以TCP為代表的端到端擁塞控制機制對互聯(lián)網(wǎng)的穩(wěn)定運行起了很大的作用。但是隨著互聯(lián)網(wǎng)規(guī)模的增長，互連網(wǎng)上的用戶和應(yīng)用都在快速增長，它在很多方面己經(jīng)不能滿足復(fù)雜網(wǎng)絡(luò)中各種應(yīng)用的需求，擁塞已經(jīng)成為一個十分重要的問題。 因此分析網(wǎng)絡(luò)擁塞控制協(xié)議,尋找最優(yōu)算法有著深遠(yuǎn)的目的和意義。 國內(nèi)外同類課題研究現(xiàn)狀及發(fā)展趨勢： 隨著計算機和通信技術(shù)的發(fā)展，Internet網(wǎng)絡(luò)在過去十幾年中經(jīng)歷了爆炸式的增長。但是，信息傳送量的逐漸增大和網(wǎng)絡(luò)組成的日益復(fù)雜使得網(wǎng)絡(luò)負(fù)載超過了網(wǎng)

3、絡(luò)的處理能力，越來越嚴(yán)重的網(wǎng)絡(luò)擁塞問題隨之而來。互聯(lián)網(wǎng)采用的是無連接的端到端數(shù)據(jù)包交換，提供盡力而為(best effort)的服務(wù)。端到端擁塞控制是目前Internet的一個研究熱點。這種機制的最大優(yōu)勢是設(shè)計簡單，可擴展性強。互聯(lián)網(wǎng)在過去的十幾年中經(jīng)歷了爆炸式的增長，這已經(jīng)充分證明了這種設(shè)計機制的成功。然而這種優(yōu)勢并不是沒有代價的，隨著互聯(lián)網(wǎng)用戶數(shù)量的膨脹，網(wǎng)絡(luò)的擁塞問題也越來越嚴(yán)重。例如由于隊列溢出，互聯(lián)網(wǎng)路由器會丟棄約10％的數(shù)據(jù)包。在最初的TCP協(xié)議中只有流控制(flow control)而沒有擁塞控制，接收端利用TCP報頭將接收能力通知發(fā)送端。這樣的控制機制只考慮了接收端的接收能力，

4、而沒有考慮網(wǎng)絡(luò)的傳輸能力，導(dǎo)致了網(wǎng)絡(luò)崩潰(congestion collapse)的發(fā)生。1986年10月，由于擁塞崩潰的發(fā)生，美國LBL到UC Berkeley的數(shù)據(jù)吞吐量從32 Kbps跌落到40 bps。據(jù)統(tǒng)計，互聯(lián)網(wǎng)上95％的數(shù)據(jù)流使用的是TCP/IP協(xié)議，因此，互聯(lián)網(wǎng)上主要的互連協(xié)議TCP/IP的擁塞控制(congestion control)機制對控制網(wǎng)絡(luò)擁塞具有特別重要的意義。擁塞控制是確?；ヂ?lián)網(wǎng)魯棒性(robustness)的關(guān)鍵因素，也是各種管理控制機制和應(yīng)用(如多媒體通信中QoS控制、區(qū)分服務(wù)(differentiated services)的基礎(chǔ)，因此關(guān)于互聯(lián)網(wǎng)的擁塞控制

5、問題一直是網(wǎng)絡(luò)研究的一個熱點，擁塞控制算法對保證Internet的穩(wěn)定具有十分重要的作用。 課題研究的主要內(nèi)容和方法，研究過程中的主要問題和解決辦法： 目前擁塞控制的研究一般分為TCP層的擁塞控制和IP層的擁塞控制，TCP層的擁塞控制主要是基于窗口的和式增加積式減少的擁塞控制機制，TCP基于窗口的端到端擁塞控制對于Internet的魯棒性起到了關(guān)鍵作用，并且在現(xiàn)實的互聯(lián)網(wǎng)中，擁塞控制的大部分工作都是由TCP來完成的，所以研究TCP層的擁塞控制對于網(wǎng)絡(luò)擁塞有相當(dāng)大的意義。隨著Internet本身的迅速發(fā)展，網(wǎng)絡(luò)規(guī)模越來越龐大，結(jié)構(gòu)越來越復(fù)雜，僅僅依靠TCP擁塞控制機制來提高網(wǎng)絡(luò)服務(wù)質(zhì)量還

6、不夠。網(wǎng)絡(luò)必須參與資源的控制工作，因此需要采用路由器端的擁塞控制方法，即IP擁塞控制問題，通常也稱之為隊列管理機制，通過排隊算法決定哪些包可以傳輸，通過丟棄策略決定哪些包被丟棄以此分配緩存。未來的網(wǎng)絡(luò)擁塞控制的方向應(yīng)該是，以TCP層擁塞控制為基礎(chǔ)，結(jié)合IP層的隊列管理策略，共同解決網(wǎng)絡(luò)擁塞問題。 第一：擁塞控制的基本知識研究。 第二：TCP協(xié)議實現(xiàn)中一般都包含有四個相互關(guān)聯(lián)的擁塞控制算法的研究：慢作。因此，僅僅依靠TCP協(xié)議無法控制擁塞，最有效的擁塞檢測和回避是在路由器中實現(xiàn)的。 第三：路由器中采用的擁塞控制算法通過檢測緩沖區(qū)的使用情況及隊列長度 　　　　　來判斷擁塞，通過丟棄緩沖隊列

7、中的數(shù)據(jù)包來控制擁塞。 解決辦法：查找資料、請教導(dǎo)師、請教學(xué)者 課題研究起止時間和進度安排： 起止時間： 2012年1月22日—2012年5月20日 進度安排： 2012年1月22日—2012年3月1日 確定論文題目，收集資料,寫開題報告。 2012年3月2日—2012年3月31日 收集資料、相關(guān)知識，對論文內(nèi)容進行系統(tǒng)研究。 2012年4月1日—2012年4月15日 實現(xiàn)算法并應(yīng)用，進行多次修改研究。 2012年4月16日—2012年5月1日 撰寫論文，準(zhǔn)備答辯。 課題研究所需主要設(shè)備、儀器及藥品： 計算機

8、 外出調(diào)研主要單位，訪問學(xué)者姓名： 指導(dǎo)教師審查意見： 指導(dǎo)教師 （簽字） 　　　　2012年3 月 教研室（研究室）評審意見： ____________教研室（研究室）主任 （簽字）

9、 　　　　2012年3 月 系（部）主任審查意見： ____________系（部）主任 （簽字） 　　　　2012年3 月 摘要：以TCP/IP協(xié)議為基礎(chǔ)的Internet自從20世紀(jì)90年代以來，其網(wǎng)絡(luò)規(guī)模、用戶數(shù)量及業(yè)務(wù)量都呈現(xiàn)爆炸式的增長，新型網(wǎng)絡(luò)應(yīng)用也不斷涌現(xiàn)，網(wǎng)絡(luò)的參數(shù)(如激活的連接數(shù)、回路往返時間)動態(tài)變化，這些使得網(wǎng)絡(luò)擁塞的狀況愈加嚴(yán)重和復(fù)雜。擁塞容易造成傳輸時延和吞吐量等服務(wù)質(zhì)量(QoS)性能指標(biāo)下降，嚴(yán)

10、重影響帶寬、緩存等網(wǎng)絡(luò)資源的利用率。因此，擁塞控制一直是網(wǎng)絡(luò)研究領(lǐng)域的熱點問題。Internet主要依賴TCP端到端擁塞控制來避免網(wǎng)絡(luò)擁塞，以TCP為代表的端到端擁塞控制機制對互聯(lián)網(wǎng)的穩(wěn)定運行起了很大的作用。但是隨著互聯(lián)網(wǎng)規(guī)模的增長，互連網(wǎng)上的用戶和應(yīng)用都在快速增長，它在很多方面己經(jīng)不能滿足復(fù)雜網(wǎng)絡(luò)中各種應(yīng)用的需求，擁塞已經(jīng)成為一個十分重要的問題。近年來，在擁塞控制領(lǐng)域開展了大量的研究工作，擁塞控制算法可以分為兩個主要部分：在端系統(tǒng)上使用的源算法和在網(wǎng)絡(luò)設(shè)備上使用的鏈路算法。在路由器中引入適當(dāng)?shù)年犃泄芾頇C制，可以有效地對擁塞進行監(jiān)測和預(yù)防，路由器中的擁塞控制策略己經(jīng)成為一個研究熱點。 本文首

11、先對擁塞現(xiàn)象的產(chǎn)生進行了說明，分析了擁塞現(xiàn)象產(chǎn)生的根源，總結(jié)了源算法和鏈路算法。接著，討論了幾種主要的TCP擁塞控制算法以及一些經(jīng)典的路由器擁塞控制策略以及對比了這兩種控制策略，并闡述了網(wǎng)絡(luò)擁塞控制的部分最新研究方法和成果。通過歸納、總結(jié)互聯(lián)網(wǎng)擁塞控制的研究現(xiàn)狀，主要對TCP層的網(wǎng)絡(luò)擁塞控制問題進行了分析與研究。然后，在此基礎(chǔ)上，提出了一種改進的擁塞控制算法，通過實驗結(jié)果分析，此算法減少了網(wǎng)絡(luò)的丟包數(shù)和提高網(wǎng)絡(luò)的吞吐量，最后，分析了進一步的研究方向。 關(guān)鍵詞：擁塞控制；算法；TCP/IP；路由器 目

12、 錄 第一章 引言 1 1.1課題背景 1 1.2網(wǎng)絡(luò)中的擁塞現(xiàn)象及原因 1 1.3 網(wǎng)絡(luò)擁塞控制算法及存在的問題 2 第二章 擁塞現(xiàn)象及擁塞控制算法研究 4 2.1 擁塞現(xiàn)象 4 2.2 擁塞現(xiàn)象產(chǎn)生的原因 5 2.3 擁塞控制算法的概況 6 2.3.1 Internet的網(wǎng)絡(luò)模型 7 2.3.2擁塞控制算法設(shè)計的困難 7 2.3.3擁塞控制算法 7 第三章 擁塞控制算法比較 9 3.1 TCP/IP體系結(jié)構(gòu) 9 3.2 TCP層擁塞控制算法 10 3.2.1 TCP Tahoe 11 3.2.2 TCP Reno 12 3.2.3 TCP New Re

13、no 12 3.2.4 TCP Sack 12 3.2.5 TCP Vegas 12 3.3 IP層擁塞控制算法 13 3.3.1 先進先出（FIFO） 13 3.3.2 公平排隊（FQ）和加權(quán)公平排隊（WFQ） 13 3.3.3 隨機檢測算法（RED） 14 3.2 兩類算法比較 15 3.5 其他擁塞控制算法 16 3.5.1 基于方程的擁塞控制算法 16 3.5.2 適應(yīng)性虛擬隊列 16 3.5.3 TCP Westwood 16 第四章 擁塞控制算法改進 18 4.1 各階段算法改進 18 4.1.1慢啟動 18 4.1.2“超時重傳”和“快速重傳” 19

14、 4.2 對目的端點主機的擁塞控制策略的改進 22 4.3 對目的端點主機的擁塞控制策略的改進 23 第五章 結(jié)束語 27 參考文獻 28 Abstract 29 第一章 引言 1.1課題背景 隨著計算機和通信技術(shù)的發(fā)展，Internet網(wǎng)絡(luò)在過去十幾年中經(jīng)歷了爆炸式的增長。但是，信息傳送量的逐漸增大和網(wǎng)絡(luò)組成的日益復(fù)雜使得網(wǎng)絡(luò)負(fù)載超過了網(wǎng)絡(luò)的處理能力，越來越嚴(yán)重的網(wǎng)絡(luò)擁塞問題隨之而來?；ヂ?lián)網(wǎng)采用的是無連接的端到端數(shù)據(jù)包交換，提供盡力而為(best effort)的服務(wù)。端到端擁塞控制是目前Internet的一個研究熱點。這種機制的最大優(yōu)勢是設(shè)計簡單

15、，可擴展性強?；ヂ?lián)網(wǎng)在過去的十幾年中經(jīng)歷了爆炸式的增長，這已經(jīng)充分證明了這種設(shè)計機制的成功。然而這種優(yōu)勢并不是沒有代價的，隨著互聯(lián)網(wǎng)用戶數(shù)量的膨脹，網(wǎng)絡(luò)的擁塞問題也越來越嚴(yán)重。例如由于隊列溢出，互聯(lián)網(wǎng)路由器會丟棄約10％的數(shù)據(jù)包。在最初的TCP協(xié)議中只有流控制(flow control)而沒有擁塞控制，接收端利用TCP報頭將接收能力通知發(fā)送端。這樣的控制機制只考慮了接收端的接收能力，而沒有考慮網(wǎng)絡(luò)的傳輸能力，導(dǎo)致了網(wǎng)絡(luò)崩潰(congestion collapse)的發(fā)生。1986年10月，由于擁塞崩潰的發(fā)生，美國LBL到UC Berkeley的數(shù)據(jù)吞吐量從32Kbps跌落到40bps。據(jù)統(tǒng)計，

16、互聯(lián)網(wǎng)上95％的數(shù)據(jù)流使用的是TCP/IP協(xié)議，因此，互聯(lián)網(wǎng)上主要的互連協(xié)議TCP/IP的擁塞控制(congestion control) 機制對控制網(wǎng)絡(luò)擁塞具有特別重要的意義。擁塞控制是確保互聯(lián)網(wǎng)魯棒性(robustness)的關(guān)鍵因素，也是各種管理控制機制和應(yīng)用(如多媒體通信中QoS控制、區(qū)分服務(wù)的基礎(chǔ)，因此關(guān)于互聯(lián)網(wǎng)的擁塞控制問題一直是網(wǎng)絡(luò)研究的一個熱點，擁塞控制算法對保證Internet的穩(wěn)定具有十分重要的作用。 1.2網(wǎng)絡(luò)中的擁塞現(xiàn)象及原因 當(dāng)在網(wǎng)絡(luò)中存在過多的報文時，網(wǎng)絡(luò)的性能會下降，這種現(xiàn)象稱為擁塞。使用圖1來描述擁塞的發(fā)生。當(dāng)負(fù)載較小時，吞吐量的增長和負(fù)載相比基本

17、呈線性關(guān)系，延遲增長緩慢；在負(fù)載超過Knee之后，吞吐量增長緩慢，延遲增長較快；當(dāng)負(fù)載超過Cliff之后，吞吐量急劇下降，延遲急劇上升。由圖1.1得出，負(fù)載在Knee附近時網(wǎng)絡(luò)的使用效率最高。擁塞控制就是網(wǎng)絡(luò)節(jié)點采取措施來避免擁塞的發(fā)生或者對擁塞的發(fā)生做出反應(yīng)。在圖1.1中就是使負(fù)載保持在Knee附近，和流控制相比，擁塞控制主要考慮端節(jié)點之間的網(wǎng)絡(luò)環(huán)境，目的是使負(fù)載不超過網(wǎng)絡(luò)的傳送能力；而流控制主要考慮接收端，目的是使發(fā)送端的發(fā)送速率不超過接收端的接收能力。 網(wǎng)絡(luò)中的擁塞來源于網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡性。擁塞不會隨著網(wǎng)絡(luò)處理能力的提高而消除。 網(wǎng)絡(luò)的吞吐量與通信子網(wǎng)負(fù)荷(即通信子網(wǎng)中

18、正在傳輸?shù)姆纸M數(shù))有著密切的關(guān)系。當(dāng)通信子網(wǎng)負(fù)荷比較小時,網(wǎng)絡(luò)的吞吐量(分組數(shù)/秒)隨網(wǎng)絡(luò)負(fù)荷(每個節(jié)點中分組的平均數(shù))的增加而線性增加。當(dāng)網(wǎng)絡(luò)負(fù)荷增加到某一值后,若網(wǎng)絡(luò)吞吐量反而下降,則表征網(wǎng)絡(luò)中出現(xiàn)了擁塞現(xiàn)象。在一個出現(xiàn)擁塞現(xiàn)象的網(wǎng)絡(luò)中,到達(dá)某個節(jié)點的分組將會遇到無緩沖區(qū)可用的情況,從而使這些分組不得不由前一節(jié)點重傳,或者需要由源節(jié)點或源端系統(tǒng)重傳。當(dāng)擁塞比較嚴(yán)重時,通信子網(wǎng)中相當(dāng)多的傳輸能力和節(jié)點緩沖器都用于這種無謂的重傳,從而使通信子網(wǎng)的有效吞吐量下降。由此引起惡性循環(huán),使通信子網(wǎng)的局部甚至全部處于死鎖狀態(tài),最終導(dǎo)致網(wǎng)絡(luò)有效吞吐量接近為零。

19、 Knee Cliff 吞吐量 負(fù)載 響應(yīng)時間 負(fù)載 圖1.1 負(fù)載與吞吐量、響應(yīng)時間關(guān)系曲線 網(wǎng)絡(luò)發(fā)展到今天，其應(yīng)用領(lǐng)域不斷拓寬，各種應(yīng)用模式不斷涌現(xiàn)，像音頻和視頻這樣的對網(wǎng)絡(luò)資源要求較高的多媒體應(yīng)用更是呈現(xiàn)出爆炸性的增長趨勢。而目前的網(wǎng)絡(luò)資源相對于快速增長的網(wǎng)絡(luò)應(yīng)用模式是遠(yuǎn)遠(yuǎn)不夠的。因此如何使相對有限的網(wǎng)絡(luò)資源更加

20、高效的利用，盡最大可能滿足這些應(yīng)用需求，避免擁塞崩潰的發(fā)生。這正是擁塞控制研究的目的和意義。 1.3 網(wǎng)絡(luò)擁塞控制算法及存在的問題 擁塞控制算法包含擁塞避免(congestion avoidance)和擁塞控制(congestion control)這兩種不同的機制。擁塞控制是“恢復(fù)”機制，它用于把網(wǎng)絡(luò)從擁塞狀態(tài)中恢復(fù)出來；擁塞避免是“預(yù)防”機制，它的目標(biāo)是避免網(wǎng)絡(luò)進入擁塞狀態(tài)，使網(wǎng)絡(luò)運行在高吞吐量、低延遲的狀態(tài)下。由網(wǎng)絡(luò)擁塞產(chǎn)生的原因可知，雖然擁塞的產(chǎn)生源于資源短缺，但單方面增加資源并不能避免擁塞的發(fā)生，有時甚至?xí)又負(fù)砣潭取＠?，增加網(wǎng)關(guān)緩存會增大報文通過網(wǎng)關(guān)的延遲，當(dāng)數(shù)據(jù)包

21、經(jīng)過長時間的排隊完成轉(zhuǎn)發(fā)時它們早己超時，而源端認(rèn)為這些數(shù)據(jù)包已經(jīng)被丟棄，開始重傳，但這些數(shù)據(jù)包仍在網(wǎng)絡(luò)中傳輸，反而浪費了網(wǎng)絡(luò)資源且加重了網(wǎng)絡(luò)擁塞。又如，處理機的處理速率太慢可能導(dǎo)致網(wǎng)絡(luò)擁塞，但單純提高該處理器的性能，網(wǎng)絡(luò)的瓶頸又會轉(zhuǎn)移到其它地方，導(dǎo)致系統(tǒng)各部分的不匹配?？偠灾瑩砣刂扑惴ǖ脑O(shè)計存在以下幾方面的困難： (1) 算法的分布性：擁塞控制算法的實現(xiàn)分布在不同的網(wǎng)絡(luò)層次以及多個網(wǎng)絡(luò)節(jié)點 中，采用分布式的擁塞控制算法可以降低單個節(jié)點的處理復(fù)雜度，同時提高網(wǎng)絡(luò)的穩(wěn)健性。 (2) 算法的可擴展性：網(wǎng)絡(luò)中各處的性能有很大的差異，對于不同的網(wǎng)絡(luò)

22、條件，如網(wǎng)絡(luò)規(guī)模的變化，帶寬的變化，鏈路傳輸時延的變化，不同的端系統(tǒng)狀況，以及存在多種數(shù)據(jù)流時，擁塞控制算法都應(yīng)具有相對較好的性能指標(biāo)。 (3) 算法的性能要求：擁塞控制算法對性能有很高的要求，包括算法的效率、公平性、穩(wěn)定性、魯棒性和收斂性。通常的擁塞控制策略只能達(dá)到部分的性能要求，因此對這些指標(biāo)需要綜合考慮。 (4) 算法的易實現(xiàn)性：擁塞控制算法的設(shè)計與實現(xiàn)要盡可能簡單，不僅要盡量減少附加的網(wǎng)絡(luò)流量，而且要減少反饋信號的復(fù)雜度。同時擁塞控制算法的設(shè)計還必須盡可能降低該算法在網(wǎng)絡(luò)節(jié)點的計算量和實現(xiàn)的復(fù)雜度。 (5) 擁塞的復(fù)雜性：計算機網(wǎng)絡(luò)已發(fā)展成為一個龐大的復(fù)雜性系統(tǒng)，其復(fù)雜性在于網(wǎng)絡(luò)

23、拓?fù)浣Y(jié)構(gòu)的復(fù)雜性，網(wǎng)絡(luò)數(shù)據(jù)流的復(fù)雜性如自相似，自組織臨界和擁塞相變現(xiàn)象等。目前，一些與復(fù)雜性研究相關(guān)的理論和方法被廣泛地應(yīng)用于網(wǎng)絡(luò)擁塞演化規(guī)律的研究中，其中，網(wǎng)絡(luò)動力學(xué)己經(jīng)發(fā)展成為一個新的跨學(xué)科領(lǐng)域。擁塞控制算法的分布性、網(wǎng)絡(luò)的復(fù)雜性和對擁塞控制算法的性能要求又使擁塞控制算法的設(shè)計具有很高的難度。到目前為止，擁塞問題還沒有得到很好的解決。 第二章 擁塞現(xiàn)象及擁塞控制算法研究 2.1 擁塞現(xiàn)象 擁塞現(xiàn)象是指到達(dá)通信子網(wǎng)中某一部分的分組數(shù)量過多，使得該部

24、分網(wǎng)絡(luò)來不及處理，以致引起這部分乃至整個網(wǎng)絡(luò)性能下降的現(xiàn)象，嚴(yán)重時甚至?xí)?dǎo)致網(wǎng)絡(luò)通信業(yè)務(wù)陷入停頓，即出現(xiàn)死鎖現(xiàn)象。這種現(xiàn)象跟公路網(wǎng)中經(jīng)常所見的交通擁擠一樣，當(dāng)節(jié)假日公路網(wǎng)中車輛大量增加時，各種走向的車流相互干擾，使每輛車到達(dá)目的地的時間都相對增加(即延遲增加)，甚至有時在某段公路上車輛因堵塞而無法開動(即發(fā)生局部死鎖)。 網(wǎng)絡(luò)的吞吐量與通信子網(wǎng)負(fù)荷(即通信子網(wǎng)中正在傳輸?shù)姆纸M數(shù))有著密切的關(guān)系。當(dāng)通信子網(wǎng)負(fù)荷比較小時，網(wǎng)絡(luò)的吞吐量(分組數(shù)/秒)隨網(wǎng)絡(luò)負(fù)荷(每個節(jié)點中分組的平均數(shù))的增加而線性增加。當(dāng)網(wǎng)絡(luò)負(fù)荷增加到某一值后，若網(wǎng)絡(luò)吞吐量反而下降，則表征網(wǎng)絡(luò)中出現(xiàn)了擁塞現(xiàn)象。在一個出現(xiàn)擁塞現(xiàn)象的網(wǎng)

25、絡(luò)中，到達(dá)某個節(jié)點的分組將會遇到無緩沖區(qū)可用的情況，從而使這些分組不得不由前一節(jié)點重傳，或者需要由源節(jié)點或源端系統(tǒng)重傳。當(dāng)擁塞比較嚴(yán)重時，通信子網(wǎng)中相當(dāng)多的傳輸能力和節(jié)點緩沖器都用于這種無謂的重傳，從而使通信子網(wǎng)的有效吞吐量下降。由此引起惡性循環(huán)，使通信子網(wǎng)的局部甚至全部處于死鎖狀態(tài)，最終導(dǎo)致網(wǎng)絡(luò)有效吞吐量接近為零。 計算機網(wǎng)絡(luò)(Computer network)就是把分布在不同地點的具有獨立功能的多臺計算機系統(tǒng)通過通信線路和網(wǎng)絡(luò)設(shè)備互相連接在一起，按照一定的網(wǎng)絡(luò)協(xié)議進行信息通信，實現(xiàn)資源共享的計算機通信系統(tǒng)，它是計算機技術(shù)與通信技術(shù)結(jié)合的產(chǎn)物。20世紀(jì)80年代出現(xiàn)的互聯(lián)網(wǎng)(Inter

26、net)是現(xiàn)在全世界最大的計算機網(wǎng)絡(luò)。以TCP/IP(Transfer control protocol/Internet protocol)網(wǎng)絡(luò)協(xié)議為基礎(chǔ)的互聯(lián)網(wǎng)在過去幾十年經(jīng)歷了爆炸式發(fā)展。1980年ARPA網(wǎng)(Internet的前身)只包含200臺計算機，從1986年接入6000臺計算機開始，5年后數(shù)量就達(dá)到了60萬，一直到上一世紀(jì)末，全球互聯(lián)網(wǎng)用戶達(dá)到2億多?，F(xiàn)在互聯(lián)網(wǎng)的容量與規(guī)模仍以驚人的速度繼續(xù)向前發(fā)展。 通過互聯(lián)網(wǎng)可以輕易實現(xiàn)遠(yuǎn)程信息訪問、用戶間通訊、交互式娛樂、電子商務(wù)等?；ヂ?lián)網(wǎng)在社會各個領(lǐng)域的廣泛應(yīng)用使得傳統(tǒng)的信息獲取、傳送、存儲和處理方式發(fā)生了根本性的變化，改變了人們的生

27、活與工作方式，對世界經(jīng)濟發(fā)展和社會生活方式產(chǎn)生了重大影響。 自從互聯(lián)網(wǎng)誕生以來，網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡使得擁塞問題一直困擾著其發(fā)展。伴隨著網(wǎng)絡(luò)規(guī)模的日益擴大和應(yīng)用類型的豐富，網(wǎng)絡(luò)擁塞也變得越來越嚴(yán)重。為易于擴展，網(wǎng)絡(luò)端節(jié)點要求盡可能簡單，其不對數(shù)據(jù)流的狀態(tài)進行記錄和管理，導(dǎo)致網(wǎng)絡(luò)無法對用戶的發(fā)送行為進行約束。當(dāng)不存在一種對數(shù)據(jù)流進行隔離的機制并且用戶又不對自身的發(fā)送行為進行約束時，網(wǎng)絡(luò)的運行就面臨著癱瘓的危險。如果不及時采用適當(dāng)?shù)姆椒▉砜刂凭W(wǎng)絡(luò)擁塞，網(wǎng)絡(luò)的穩(wěn)定性將無法得到保障。實際上，這個現(xiàn)象在八十年代初就已經(jīng)出現(xiàn)，并被稱為“擁塞崩潰”(Congestion collapse)。

28、計算機網(wǎng)絡(luò)中的鏈路容量、網(wǎng)絡(luò)節(jié)點中的緩存和處理器等都是網(wǎng)絡(luò)的資源，在某段時間內(nèi)如果用戶提供給網(wǎng)絡(luò)的負(fù)載大于網(wǎng)絡(luò)資源容量和網(wǎng)絡(luò)節(jié)點的處理能力，網(wǎng)絡(luò)便會產(chǎn)生阻塞，性能變壞，這就是網(wǎng)絡(luò)中的擁塞現(xiàn)象。可以用如下關(guān)系式表示： ∑資源需求>網(wǎng)絡(luò)可用資源 網(wǎng)絡(luò)產(chǎn)生擁塞時，網(wǎng)絡(luò)的性能便會降低，甚至有可能使整個系統(tǒng)發(fā)生崩潰，具體表現(xiàn)在網(wǎng)絡(luò)吞吐量和效率的降低、路由器緩沖隊列的急劇增加、報文延時的增加、報文的丟失、報文到達(dá)的延時抖動劇烈等方面。當(dāng)網(wǎng)絡(luò)處于擁塞崩潰狀態(tài)時，微小的負(fù)載增量都將使網(wǎng)絡(luò)的有效吞吐量急劇下降。 圖1.1清楚地表述了網(wǎng)絡(luò)負(fù)載與吞吐量和延遲之間的關(guān)系。當(dāng)網(wǎng)絡(luò)的負(fù)載較小時，隨著負(fù)載增加，吞吐量

29、相應(yīng)增加。當(dāng)負(fù)載接近網(wǎng)絡(luò)的容量時，吞吐量將會停止增加，如果負(fù)載繼續(xù)增加，就會導(dǎo)致分組丟棄，這時網(wǎng)絡(luò)的吞吐量會突然降低，并接近于0。把吞吐量接近于0的現(xiàn)象稱為擁塞崩潰(congestion collapse)，并且把擁塞崩潰點稱為cliff，因為負(fù)載超過這一點后吞吐量會突然降低，而把負(fù)載增加后吞吐量增加很少但傳輸延遲迅速增加的那點稱為擁塞臨界點(knee)。而擁塞避免(congestion avoidance)工作在knee處，它鼓勵用戶增加負(fù)載，只要不會使延遲增加就可以。當(dāng)網(wǎng)絡(luò)輕載時，隨著負(fù)載的增加，吞吐量隨之迅速增加，延遲增長緩慢；當(dāng)過了Knee點之后，負(fù)載增加時吞吐量增加趨于平緩， 延遲增

30、長較快；當(dāng)超過Cliff點后負(fù)載增加時吞吐量急劇下降，延遲急劇上升。擁塞時網(wǎng)絡(luò)的具體表現(xiàn)為數(shù)據(jù)包經(jīng)受的時延增大，丟棄概率增高。而發(fā)送放在遇到大時延時進行的不必要重傳會引起路由器利用其鏈路帶寬來轉(zhuǎn)發(fā)不必要的分組拷貝。數(shù)據(jù)包丟棄概率的增加也會引起發(fā)送方執(zhí)行重傳因緩存溢出而丟棄的數(shù)據(jù)包。這些都導(dǎo)致鏈路傳輸容量的浪費，有效利用率降低。 2.2 擁塞現(xiàn)象產(chǎn)生的原因 擁塞發(fā)生的原因是“需求”大于“供給”。網(wǎng)絡(luò)中有限的資源由多個用戶共享使用。由于沒有“接納控制”算法，網(wǎng)絡(luò)無法根據(jù)資源的情況限制用戶的數(shù)量；缺乏中央控制，網(wǎng)絡(luò)也無法控制用戶使用資源的數(shù)量。目前Internet上用戶和應(yīng)用的數(shù)量都在迅

31、速增長。如果不使用某種機制協(xié)調(diào)資源的使用，必然會導(dǎo)致網(wǎng)絡(luò)擁塞。雖然擁塞源于資源短缺，但增加資源并不能避免擁塞的發(fā)生，有時甚至?xí)又負(fù)砣潭取＠纾涸黾泳W(wǎng)關(guān)緩沖會增大報文通過網(wǎng)關(guān)的延遲，如果總延遲超過端系統(tǒng)重傳時鐘的值，就會導(dǎo)致報文重傳，反而加重了擁塞。擁塞總是發(fā)生在網(wǎng)絡(luò)中資源“相對”短缺的位置。擁塞發(fā)生位置的不均衡反映了Internet的不均衡性。首先是資源分布的不均衡。圖2.1(a)中帶寬的分布是不均衡的，當(dāng)以1Mb/s的速率從S向D發(fā)送數(shù)據(jù)時，在網(wǎng)關(guān)R會發(fā)生擁塞。其次是流量分布的不均衡。圖2.1(b)中帶寬的分布是均衡的，當(dāng)A和B都以1Mb/s的速率向C發(fā)送數(shù)據(jù)時，在網(wǎng)關(guān)R也會發(fā)生擁塞。I

32、nternet中資源和流量分布的不均衡都是廣泛存在的，由此導(dǎo)致的擁塞不能使用增加資源的方法來解決。 D R S 1Mb 100Kb (a) A C 1Mb 1Mb R B D

33、 1Mb 1Mb (b) 圖2.1 擁塞產(chǎn)生原因示意 網(wǎng)絡(luò)產(chǎn)生擁塞的根本原因在于用戶提供給網(wǎng)絡(luò)的負(fù)載大于網(wǎng)絡(luò)資源的容量和處理能力。擁塞產(chǎn)生的直接原因主要表現(xiàn)在如下三點： (1) 存儲空間不足。幾個輸入數(shù)據(jù)流共同需要同一個輸出端口，在這個端口就會建立排隊。如果沒有足夠的存儲空間存儲，數(shù)據(jù)包就會丟棄。對突發(fā)數(shù)據(jù)流更是如此。增加存儲空間在某種程度上可以緩解這一矛盾，但如果路由器有無限存儲量時，擁塞只是會變得更壞，而不是更好，因為在網(wǎng)

34、絡(luò)鬼數(shù)據(jù)包經(jīng)過長時間排隊完成轉(zhuǎn)發(fā)時，它們早已超時，發(fā)送端認(rèn)為它們己經(jīng)被丟棄，而這些數(shù)據(jù)包還會繼續(xù)向下一個路由器轉(zhuǎn)發(fā)，從而浪費網(wǎng)絡(luò)資源且加重了網(wǎng)絡(luò)擁塞。 (2) 帶寬容量不足。根據(jù)香農(nóng)信息理論，任何信道帶寬最大值即信道容量C=Blog2(1+S/N)(其中N為信道白噪聲的平均功率，S為信源的平均功率，B為信道帶寬)。所有信源發(fā)送的速率R必須小于或等于信道容量C。如果R>C，則在理論上無差錯傳輸就是不可能的，所以在網(wǎng)絡(luò)低速鏈路處就會形成帶寬瓶頸，當(dāng)其滿足不了通過它的所有源端帶寬要求時，網(wǎng)絡(luò)就會發(fā)生擁塞。 由于互聯(lián)網(wǎng)的設(shè)計機制導(dǎo)致其缺乏“接納能力”，因此在網(wǎng)絡(luò)資源不足時不能限制用戶數(shù)量，而只能靠

35、降低服務(wù)質(zhì)量來繼續(xù)為用戶服務(wù)，也就是盡力而為的服務(wù)。擁塞發(fā)生后，表現(xiàn)為端到端時延加大、數(shù)據(jù)包被丟棄概率增大、網(wǎng)絡(luò)服務(wù)質(zhì)量下降、甚至整個系統(tǒng)崩潰等。1984年Nagle報告了由于TCP連接中沒有必要的重傳所誘發(fā)的擁塞崩潰，1986-1987年間這種現(xiàn)象曾經(jīng)多次發(fā)生，嚴(yán)重在端到端擁塞控制的實現(xiàn)中包括終端系統(tǒng)機制和路由器機制兩個有機部分。目前在Internet中，最主要的擁塞控制機制是由終端系統(tǒng)的TCP協(xié)議完成的，這也是網(wǎng)絡(luò)能保持魯棒性的主要原因。本文研究以TCP層擁塞控制為基礎(chǔ)，結(jié)合IP層的隊列管理策略，共同解決網(wǎng)絡(luò)擁塞問題。 2.3 擁塞控制算法的概況 擁塞控制方法： (1) 緩沖

36、區(qū)預(yù)分配法。該法用于虛電路分組交換網(wǎng)中。在建立虛電路時，讓呼叫請求分組途經(jīng)的節(jié)點為虛電路預(yù)先分配一個或多個數(shù)據(jù)緩沖區(qū)。若某個節(jié)點緩沖器已被占滿，則呼叫請求分組另擇路由，或者返回一個“忙”信號給呼叫者。這樣，通過途經(jīng)的各節(jié)點為每條虛電路開設(shè)的永久性緩沖區(qū)(直到虛電路拆除)，就總能有空間來接納并轉(zhuǎn)送經(jīng)過的分組。此時的分組交換跟電路交換很相似。當(dāng)節(jié)點收到一個分組并將它轉(zhuǎn)發(fā)出去之后，該節(jié)點向發(fā)送節(jié)點返回一個確認(rèn)信息。該確認(rèn)一方面表示接收節(jié)點已正確收到分組，另一方面告訴發(fā)送節(jié)點，該節(jié)點已空出緩沖區(qū)以備接收下一個分組。上面是“停一等”協(xié)議下的情況，若節(jié)點之間的協(xié)議允許多個未處理的分組存在，則為了完全消除擁

37、塞的可能性，每個節(jié)點要為每條虛電路保留等價于窗口大小數(shù)量的緩沖區(qū)。這種方法不管有沒有通信量，都有可觀的資源(線路容量或存儲空間)被某個連接占有，因此網(wǎng)絡(luò)資源的有效利用率不高。這種控制方法主要用于要求高帶寬和低延遲的場合，例如傳送數(shù)字化語音信息的虛電路。 (2) 分組丟棄法。該法不必預(yù)先保留緩沖區(qū)，當(dāng)緩沖區(qū)占滿時，將到來的分組丟棄。若通信子網(wǎng)提供的是數(shù)據(jù)報服務(wù)，則用分組丟棄法來防止擁塞發(fā)生不會引起大的影響。但若通信子網(wǎng)提供的是虛電路服務(wù)，則必須在某處保存被丟棄分組的備份，以便擁塞解決后能重新傳送。有兩種解決被丟棄分組重發(fā)的方法，一種是讓發(fā)送被丟棄分組的節(jié)點超時，并重新發(fā)送分組直至分組被收到；另

38、一種是讓發(fā)送被丟棄分組的節(jié)點在嘗試一定次數(shù)后放棄發(fā)送，并迫使數(shù)據(jù)源節(jié)點超時而重新開始發(fā)送。但是不加分辨地隨意丟棄分組也不妥，因為一個包含確認(rèn)信息的分組可以釋放節(jié)點的緩沖區(qū)，若因節(jié)點元空余緩沖區(qū)來接收含確認(rèn)信息的分組，這便使節(jié)點緩沖區(qū)失去了一次釋放的機會。解決這個問題的方法可以為每條輸入鏈路永久地保留一塊緩沖區(qū)，以用于接納并檢測所有進入的分組，對于捎帶確認(rèn)信息的分組，在利用了所捎帶的確認(rèn)釋放緩沖區(qū)后，再將該分組丟棄或?qū)⒃撋訋Ш孟⒌姆纸M保存在剛空出的緩沖區(qū)中。 (3) 定額控制法。這種方法在通信子網(wǎng)中設(shè)置適當(dāng)數(shù)量的稱做“許可證”的特殊信息，一部分許可證在通信子網(wǎng)開始工作前預(yù)先以某種策略分配給各

39、個源節(jié)點，另一部分則在子網(wǎng)開始工作后在網(wǎng)中四處環(huán)游。當(dāng)源節(jié)點要發(fā)送來自源端系統(tǒng)的分組時，它必須首先擁有許可證，并且每發(fā)送一個分組注銷一張許可證。目的節(jié)點方則每收到一個分組并將其遞交給目的端系統(tǒng)后，便生成一張許可證。這樣便可確保子網(wǎng)中分組數(shù)不會超過許可證的數(shù)量，從而防止了擁塞的發(fā)生。 2.3.1 Internet的網(wǎng)絡(luò)模型 擁塞現(xiàn)象的發(fā)生和Internet的設(shè)計機制有著密切的聯(lián)系。Internet的網(wǎng)絡(luò)模型可以用以下幾點來抽象： (1) 報文交換(packet-switched)網(wǎng)絡(luò)。和電路交換(circuit-switched)相比，報文交換通過共享提高了資源的利用效率。但在共享方

40、式下，如何保證用戶的服務(wù)質(zhì)量是一個很棘手的問題；在報文交換網(wǎng)絡(luò)中可能出現(xiàn)報文“亂序”現(xiàn)象，對亂序報文的處理增加了端系統(tǒng)的復(fù)雜性。 (2) 無連接(connectionless)網(wǎng)絡(luò)。Internet的節(jié)點之間在發(fā)送數(shù)據(jù)之前不需要建立連接。無連接模型簡化了網(wǎng)絡(luò)的設(shè)計，在網(wǎng)絡(luò)的中間節(jié)點上不需要保存和連接有關(guān)的狀態(tài)信息。但是使用無連接模型難以引入“接納控制”(admission control)算法，在用戶需求大于網(wǎng)絡(luò)資源時難以保證服務(wù)質(zhì)量；在無連接模型中對數(shù)據(jù)發(fā)送源的追蹤能力很差，給網(wǎng)絡(luò)的安全帶來了隱患；無連接也是網(wǎng)絡(luò)中亂序報文出現(xiàn)的一個主要原因。 (3) best-effort的服務(wù)模型。b

41、est-effort即網(wǎng)絡(luò)不對數(shù)據(jù)傳輸?shù)姆?wù)質(zhì)量提供保證。這個選擇和早期網(wǎng)絡(luò)中的應(yīng)用有關(guān)。傳統(tǒng)的網(wǎng)絡(luò)應(yīng)用主要是FTP、Telnet、SMTP等，它們對網(wǎng)絡(luò)性能(帶寬、延遲、丟失率等)的變化不敏感，best-effort模型可以滿足需要。但best-effort模型不能很好滿足新出現(xiàn)的多媒體應(yīng)用的要求，這些應(yīng)用對延遲、速率等性能的變化比較敏感。這要求網(wǎng)絡(luò)在原有服務(wù)模型的基礎(chǔ)上進行擴充。 2.3.2擁塞控制算法設(shè)計的困難 擁塞控制算法的設(shè)計困難體現(xiàn)在以下方面： (1) 算法的分布性。擁塞控制算法的實現(xiàn)分布在多個網(wǎng)絡(luò)節(jié)點中，必須使用不完整的信息完成控制，并使各節(jié)點協(xié)調(diào)工作，還必須考慮某

42、些節(jié)點工作不正常的情況。 (2) 網(wǎng)絡(luò)環(huán)境的復(fù)雜性。Internet中各處的網(wǎng)絡(luò)性能有很大的差異，算法必須具有很好的適應(yīng)性；另外由于Internet對報文的正確傳輸不提供保證，算法必須處理報文丟失、亂序到達(dá)等情況。 (3) 算法的性能要求。擁塞控制算法對性能有很高的要求，包括算法的公平性、效率、穩(wěn)定性和收斂性等。某些性能目標(biāo)之間存在矛盾，在算法設(shè)計時需要進行權(quán)衡。 (4) 算法的開銷。擁塞控制算法必須盡量減少附加的網(wǎng)絡(luò)流量，特別是在擁塞發(fā)生時。在使用反饋式的控制機制時，這個要求增加了算法設(shè)計的困難。算法還必須盡量降低在網(wǎng)絡(luò)節(jié)點(特別是網(wǎng)關(guān))上的計算復(fù)雜性。目前的策略是將大部分計算放在端節(jié)

43、點完成，在網(wǎng)關(guān)上只進行少量的操作，這符合Internet的基本設(shè)計思想。 2.3.3擁塞控制算法 在設(shè)計和比較擁塞控制算法時，需要一定的評價方法。從用戶的角度出發(fā)，可以比較端系統(tǒng)的吞吐率、丟失率和延遲等指標(biāo)，這些是用戶所關(guān)心的。由于擁塞控制算法對整個網(wǎng)絡(luò)系統(tǒng)都有影響，在評價算法時更應(yīng)該從整個系統(tǒng)的角度出發(fā)進行考慮。兩個重要的評價指標(biāo)是資源分配的效率和資源分配的公平性。 1、資源分配的效率 資源分配的效率可以用Power函數(shù)來評價。Power函數(shù)定義為： Power=Throughput／Response Time 在上式中，一般取a=l。如果

44、評價偏重吞吐量，則取a>l；如果評價偏重反應(yīng)時間，則Power取a

45、 2、資源分配的公平性 多用戶情況下需要考慮資源分配的公平性。公平性評價的主要方法包括Max-Min Fairness，F(xiàn)airness Index等。 Max-min fairness被非正式的定義為：每個用戶的吞吐量至少和其它共享相同瓶頸的用戶的吞吐量相同。Max-Min Fairness是一種理想的狀況，但是它不能給出公平的程度。 Fairness Index提供了一個計算公式，可以計算公平的程度。它定義為： Fairness Index的計算結(jié)果位于0和l之間，并且結(jié)果不受衡量單位的影響。它的一個性質(zhì)

46、是：如果n個用戶中只有k個用戶平均共享資源，而另(n-k)個用戶沒有任何資源，計算結(jié)果為k/n。 由于公平性是針對資源分配而言的，所以在評價前首先要確定“資源”的含義。目前大多數(shù)研究在評價公平性時都針對吞吐量，這是從用戶的角度出發(fā)考慮的，并不完全適合網(wǎng)絡(luò)中的資源狀況。網(wǎng)絡(luò)中的資源包括鏈路帶寬、網(wǎng)關(guān)的緩沖和網(wǎng)關(guān)的處理能力等，在考察公平性時應(yīng)當(dāng)將這些資源的分配情況綜合考慮。 第三章 擁塞控制算法比較 3.1 TCP/IP體系結(jié)構(gòu) TCP/IP(Transmission Control Protocol/Internet Protocol)即傳輸控制協(xié)議／互連網(wǎng)絡(luò)

47、協(xié)議，是ARPANET最有影響力的研究成果之一，現(xiàn)時的TCP/IP協(xié)議已成為一組完整的協(xié)議，構(gòu)成網(wǎng)絡(luò)體系結(jié)構(gòu)，除傳輸控制協(xié)議(TCP)和互連網(wǎng)絡(luò)協(xié)議(IP)外，還包括工具性協(xié)議、管理性協(xié)議及應(yīng)用協(xié)議等多種其它協(xié)議，TCP/IP協(xié)議己經(jīng)成為事實上的因特網(wǎng)上的通信標(biāo)準(zhǔn)，也是事實上的國際標(biāo)準(zhǔn)和工業(yè)標(biāo)準(zhǔn)。TCP/IP協(xié)議的體系結(jié)構(gòu)可以用一個四層的分層模型來描述，分成網(wǎng)絡(luò)接口層、IP層、運輸層和應(yīng)用層。如圖所示： 應(yīng)用層 運輸層（TCP/UDP層） IP層 網(wǎng)絡(luò)接口層 圖3.1TCP/IP體系結(jié)構(gòu) 網(wǎng)絡(luò)接口層又稱

48、數(shù)據(jù)鏈路層，定義了特定介質(zhì)的物理連接特性，及在該介質(zhì)上發(fā)生、接收的信息幀的格式。其作用是傳輸經(jīng)IP層處理過的信息，并提供一個主機與實際網(wǎng)絡(luò)的接口，TCP/IP支持的數(shù)據(jù)鏈路技術(shù)很多，其特色在于它可以在任何一種物理網(wǎng)絡(luò)上運行。IP層采用的是IP協(xié)議，負(fù)責(zé)IP數(shù)據(jù)報從主機發(fā)往任何網(wǎng)絡(luò)，到達(dá)其目的地。 IP層為每一個IP數(shù)據(jù)報分配一個全網(wǎng)惟一的傳送地址(IP地址)，并據(jù)此IP地址段的信息把IP數(shù)據(jù)報轉(zhuǎn)發(fā)到其目的地。另外IP層還具有分組路由和擁塞控制等功能。 運輸層(TCP/UDP層)提供的是端到端的通信功能，主要由兩個協(xié)議構(gòu)成。TCP協(xié)議提供的是面向連接的、可靠的傳輸服務(wù)；用戶數(shù)據(jù)報協(xié)議

49、UDP提供的是無連接的、不可靠的傳輸服務(wù)。TCP協(xié)議還具有差錯檢測、流量控制、擁塞控制等功能。 應(yīng)用層包含了所有的高層協(xié)議，例如：遠(yuǎn)程登錄的虛擬終端協(xié)議(Telnet)、文件傳輸協(xié)議(FTP)、Web傳輸協(xié)議(HTTP)和郵件傳輸協(xié)議(SMTP)等，為各種用戶提供了所需的服務(wù)。 目前擁塞控制的研究一般分為TCP層的擁塞控制和IP層的擁塞控制，TCP層的擁塞控制主要是基于窗口的和式增加積式減少的擁塞控制機制，TCP基于窗口的端到端擁塞控制對于Internet的魯棒性起到了關(guān)鍵作用，并且在現(xiàn)實的互聯(lián)網(wǎng)中，擁塞控制的大部分工作都是由TCP來完成的，所以研究TCP層的擁塞控制對于網(wǎng)絡(luò)擁塞有相當(dāng)大的

50、意義。隨著Internet本身的迅速發(fā)展，網(wǎng)絡(luò)規(guī)模越來越龐大，結(jié)構(gòu)越來越復(fù)雜，僅僅依靠TCP擁塞控制機制來提高網(wǎng)絡(luò)服務(wù)質(zhì)量還不夠。網(wǎng)絡(luò)必須參與資源的控制工作，因此需要采用路由器端的擁塞控制方法，即IP擁塞控制問題，通常也稱之為隊列管理機制，通過排隊算法決定哪些包可以傳輸，通過丟棄策略決定哪些包被丟棄以此分配緩存。未來的網(wǎng)絡(luò)擁塞控制的方向應(yīng)該是，以TCP層擁塞控制為基礎(chǔ)，結(jié)合IP層的隊列管理策略，共同解決網(wǎng)絡(luò)擁塞問題。 NSP SM HTTP FTP DNS TELENT ......... UDP T

51、CP RARP ARP IP ICMP 局域網(wǎng) X.25網(wǎng) 無線網(wǎng) 電話網(wǎng) ......... 應(yīng)用層 運輸層 IP層 網(wǎng)絡(luò)接口層 圖3.2 TCP/IP體系結(jié)構(gòu)中各層所應(yīng)用的主要協(xié)議口 3.2 TCP層擁塞控制算法 互聯(lián)網(wǎng)最初源于美國國防部的ARPANET計劃。上世紀(jì)60年代中期正是冷戰(zhàn)的高峰，美國國防部希望有一個命令和控制網(wǎng)絡(luò)，以確保在核戰(zhàn)爭的條件下幸免于難，而傳統(tǒng)基于電路交換的電話網(wǎng)絡(luò)則過于脆弱。國防部指定其下屬的高級研究計劃局解決這個問題，

52、從而誕生ARPANET，其最大特點是采用無連接的端到端報文交換服務(wù)。到了80年代中期，演變?yōu)榛ヂ?lián)網(wǎng)。TCP協(xié)議最初只是作為NSFNET的程序規(guī)范，即RFC 793，這也是最早的較為完整且齊全的TCP規(guī)范。這個規(guī)范簡單描述了如何進行主機到主機的可靠傳輸，并描述了傳輸控制協(xié)議執(zhí)行的功能，相應(yīng)的實現(xiàn)程序及程序接口。TCP協(xié)議在設(shè)計之初就被賦予了很高的使命，需要成為報文交換計算機網(wǎng)絡(luò)和這些網(wǎng)絡(luò)互聯(lián)系統(tǒng)中的高可靠性傳輸協(xié)議。需要明確的是，網(wǎng)絡(luò)中的可靠傳輸包括兩方面：首先是數(shù)據(jù)的正確，由于以前的傳輸介質(zhì)質(zhì)量很差，所以在傳輸層及以下各層協(xié)議中都實現(xiàn)了校驗和計算；其次是數(shù)據(jù)的完整保序，這個特性需要TCP執(zhí)行復(fù)

53、雜的操作來實現(xiàn)，通常我們強調(diào)TCP的可靠傳輸時主要指后者。 目前在Internet上實際使用的擁塞控制基本上是建立在TCP窗口控制基礎(chǔ)之上的，據(jù)統(tǒng)計，Internet上的95％的數(shù)據(jù)流使用的是TCP協(xié)議，因此TCP擁塞控制一直是網(wǎng)絡(luò)擁塞控制研究的重點。TCP擁塞控制的基本框架是在文中提出的，文中Van Jacobson指出用顯式的方法來實現(xiàn)基于窗口的運輸層協(xié)議會導(dǎo)致端系統(tǒng)對網(wǎng)絡(luò)擁塞的錯誤反應(yīng)，并提出了一系列算法來解決這一問題，這些算法包括：RRT的估計重傳計數(shù)器的指數(shù)回退、慢啟動、擁塞窗口的動念調(diào)整等。正是這些算法奠定了TCP擁塞控制的基礎(chǔ)。 TCP/IP一般通過Internet串行線路協(xié)

54、議SLIP或點對點協(xié)議PPP在串行線上進行數(shù)據(jù)傳送。TCP/IP協(xié)議的基本傳輸單位是數(shù)據(jù)包 (datagram)。TCP協(xié)議負(fù)責(zé)把數(shù)據(jù)分成若干個數(shù)據(jù)包/段，并給每個數(shù)據(jù)包加上包頭，IP協(xié)議在每個包頭上再加上接收端主機地址，這樣數(shù)據(jù)找到自己要去的地方。如果傳輸過程中出現(xiàn)數(shù)據(jù)丟失、數(shù)據(jù)失真等情況，TCP協(xié)議會自動要求數(shù)據(jù)重新傳輸并重新組包。TCP協(xié)議保證數(shù)據(jù)傳輸?shù)馁|(zhì)量，總之IP協(xié)議保證數(shù)據(jù)的傳輸。數(shù)據(jù)在傳輸時每通過一層就要在數(shù)據(jù)上加個包頭，其中數(shù)據(jù)供接收端同一層協(xié)議使用，而在接收端每經(jīng)過一層要把用過的包頭去掉，這樣來保證傳輸數(shù)據(jù)的格式完全一致。TCP/IP協(xié)議需要針對不同的網(wǎng)絡(luò)進行不同的設(shè)置，且每

55、個節(jié)點一般需要一個“IP地址”、一個“子網(wǎng)掩碼”、一個“默認(rèn)網(wǎng)關(guān)”。不過可以通過動態(tài)主機配置協(xié)議（DHCP），給客戶端自動分配一個IP地址，這樣避免了出錯也簡化了TCP/IP協(xié)議的設(shè)置，我們可以指定一臺計算機具有多個IP地址，因此在訪問互聯(lián)網(wǎng)時不要以為一個IP地址就是一臺計算機；另外通過特定的技術(shù)，也可以使多臺服務(wù)器共用一個IP地址，這些服務(wù)器在用戶看起來就像一臺主機似的。在TCP/IP中所有的協(xié)議都被封裝在IP分組中通過IP網(wǎng)間網(wǎng)傳輸。IP是一個路由協(xié)議這就意味著使用IP通信的兩個節(jié)點不必連接到同一物理線路上(不進行路由)。 擁塞控制的方法，無論什么形式都可以分為兩類：開環(huán)控制和閉環(huán)控制。

56、開環(huán)控制是預(yù)先設(shè)計一個好的網(wǎng)絡(luò)，確保它不會發(fā)生擁塞，而網(wǎng)絡(luò)在運行過程中不再采取措施。比較典型的例子就是資源預(yù)留協(xié)議(RSVP)，這類控制機制較適用于簡單的音頻和活動圖像業(yè)務(wù)。但是網(wǎng)絡(luò)的業(yè)務(wù)流量通常是很難精確控制對于復(fù)雜的網(wǎng)絡(luò)系統(tǒng)來說是遠(yuǎn)遠(yuǎn)不夠的。顯然，對網(wǎng)絡(luò)這樣不斷變化的復(fù)雜系統(tǒng)，開環(huán)系統(tǒng)并不是理想的選擇。TCP是目前Internet上應(yīng)用廣泛的傳輸層協(xié)議，實施擁塞控制是TCP的兩個主要任務(wù)之一，由于IP層在發(fā)生擁塞時不向端系統(tǒng)提供任何顯式的反饋信息，因而TCP擁塞控制采用的是基于窗口的端到端的閉環(huán)控制方式。閉環(huán)控制能夠根據(jù)網(wǎng)絡(luò)中反饋至端系統(tǒng)的擁塞指示信息，依據(jù)一定的控制策略，及時調(diào)整源端系統(tǒng)

57、的數(shù)據(jù)傳輸速率，避免網(wǎng)絡(luò)狀況的惡化，既保證了傳輸?shù)馁|(zhì)量又能充分利用網(wǎng)絡(luò)資源。 在TCP擁塞控制的算法中，有以下幾個重要參數(shù)： 擁塞窗口(cwnd)：擁塞控制的關(guān)鍵參數(shù)，控制源端在擁塞情況下一次最多能發(fā)送多少數(shù)據(jù)包。 通告窗口(awnd)：接收端對源端發(fā)送窗口大小所做的限制，在建立連接時由接收方通過ACK確認(rèn)捎帶給源端。 慢啟動閾值(ssthresh)：用來控制源端從慢啟動階段轉(zhuǎn)換到擁塞避免階段的門限值。 回路響應(yīng)時間(RTT)：一個數(shù)據(jù)包從源端發(fā)送到接收端，直至源端收到目的端對該數(shù)據(jù)包確認(rèn)信息所經(jīng)歷的時間間隔。 超時重傳計數(shù)器(RTO)：描述數(shù)據(jù)包從發(fā)送到失效的時間間隔，是源端用來

58、判斷數(shù)據(jù)包是否丟失和網(wǎng)絡(luò)擁塞的重要參數(shù)，通常設(shè)為2RTT或5RTT。 TCP的擁塞控制由慢啟動、擁塞控制、快速重傳和快速恢復(fù)四個核心算法組成。這四個基本算法互相聯(lián)系，經(jīng)過大量的事實證明，它對Internet上大批量文件傳輸?shù)确?wù)具有良好的適應(yīng)性，成為目前在Internet上主要使用的端系統(tǒng)擁塞控制機制。此后的TCP擁塞控制方法基本上都是在此基礎(chǔ)上的一些改進。以下是對這些改進中的典型算法的分析。 3.2.1 TCP Tahoe Tahoe算法由3個主要部分組成，和式增加積式減少(AIMD)、慢啟動、快速重傳?！昂褪皆黾印庇脕碇?jǐn)慎地探測端到端路徑上的可用帶寬，具體表現(xiàn)為TCP發(fā)送方在無丟包事

59、件發(fā)生時，每收到一個ACK，就將擁塞窗口增加一點，直到丟包事件發(fā)生，這個線性增長階段也稱為擁塞避免。“積式減少”方法在丟包事件發(fā)生時將當(dāng)前的擁塞窗口值減半，這樣就降低了發(fā)送方的發(fā)送速率，從而減輕擁塞程度。慢啟動是數(shù)據(jù)發(fā)送的初始化階段，發(fā)送方以很慢的速率開始發(fā)送，但以指數(shù)的速度快速增加其發(fā)送速率，從而減小初始階段因發(fā)送方發(fā)送窗口過小而造成的帶寬浪費?？焖僦貍魇钱?dāng)發(fā)送方收到3個冗余的ACK而檢測到丟包時不必等到重傳超時而立即重傳丟失的包。這些方法正是TCP擁塞控制的基礎(chǔ)，以后的各種改進都依賴于此基礎(chǔ)。 3.2.2 TCP Reno TCP Reno是在Tahoe的基礎(chǔ)上增加了“快速恢復(fù)”階段。

60、和Tahoe相比較，Reno在快速重傳后并不將擁塞窗口減至1MSS，進入慢啟動階段。而是將擁塞窗口減半，進入擁塞避免階段，這是因為與發(fā)生超時事件不同，收到冗余的ACK表明發(fā)送的其它包已經(jīng)被接收方收到，兩個端系統(tǒng)間仍有數(shù)據(jù)的流動，網(wǎng)絡(luò)處于輕度擁塞。因此，發(fā)送端直接將擁塞窗口減至1MSS是不合適的，但Reno算法也存在缺點，當(dāng)發(fā)送端檢測到擁塞后，要重傳數(shù)據(jù)包丟失到檢測到丟失時發(fā)送的全部數(shù)據(jù)包，這其中包括已正確傳輸?shù)浇邮斩?，不必重傳的包。下面的New Reno和Sack算法正式針對Reno算法的這一缺點的改進。 3.2.3 TCP New Reno New Reno對Reno的改進是通過盡量避免

61、Reno在快速恢復(fù)階段的許多重傳超時，利用一個ACK來確定部分發(fā)送窗口，立即重傳余下的數(shù)據(jù)包，從而提高網(wǎng)絡(luò)性能。目前，在Internet中最廣泛使用的是New Reno算法。然而New Reno算法也存在著不足，文分析并指出了New Reno在高速遠(yuǎn)距離網(wǎng)絡(luò)中不能有效利用帶寬的不足，并給出了解決方法。 3.2.4 TCP Sack 如前所述，Sack算法也是對Reno的改進，當(dāng)檢測到擁塞后，不用重傳數(shù)據(jù)包丟失到檢測到丟失時發(fā)送的全部數(shù)據(jù)包，而是對這些數(shù)據(jù)包進行有選擇的確認(rèn)和重傳，從而避免不必要的重傳，減少延時，提高網(wǎng)絡(luò)吞吐量。由于使用選擇重傳，所以在一個窗口中數(shù)據(jù)包多丟失的情況下，Sack

62、性能優(yōu)于New Reno，但是Sack的主要缺點是要修改接收端TCP。 3.2.5 TCP Vegas TCP Vegas算法和以前的算法大不相同，它是通過觀察以前TCP連接中的RRT值的改變來控制擁塞窗口的，如果RRT值變大，TCP Vegas就認(rèn)為網(wǎng)絡(luò)發(fā)生擁塞，就減小擁塞窗口；反之，則增大擁塞窗口。這樣做的好處是擁塞控制機制的出發(fā)只和RRT的改變有關(guān)，而與包的具體時延無關(guān)。為了提高吞吐率、降低分組丟棄率，TCP Vegas采用了3種與眾不同的技術(shù)： (1) 新的重傳機制，它將引發(fā)重傳的重復(fù)應(yīng)答(ACK)數(shù)從3個減少到2個或者1個，因此TCP能夠?qū)Ψ纸M丟棄做出更快速響應(yīng)。 (2)

63、新的擁塞避免機制，它改變了TCP Reno、TCP Tahoe等版本中通過分組丟棄來檢測網(wǎng)絡(luò)擁塞的基本思想，而是通過觀察己發(fā)送分組的RRT的變化來判斷網(wǎng)絡(luò)的擁塞狀況，即：如果觀察到RTT變大，則認(rèn)為網(wǎng)絡(luò)開始擁塞，因此減小發(fā)送窗口值，如果RRT變小，TCP Vegas認(rèn)為網(wǎng)絡(luò)正變得暢通，因此增大發(fā)送窗口值。 (3) 擴展的“慢啟動”(slow-start)機制，在Reno等版本的“慢啟動”階段，發(fā)送窗13以指數(shù)增長方式更新，而Vegas“慢啟動”階段的發(fā)送窗口增長速度為Reno等版本的1/2，主要目的是在這一階段利用(2)所描述的方法檢測和避免擁塞。 由于TCP Vegas只和RTT的改變有

64、關(guān)，RRT的準(zhǔn)確度對于Vegas來說非常重要，事實上，在其實現(xiàn)中也采取了許多措施來保證RTT計量的精確度，如更細(xì)粒度的時問計算等。但是，它忽略了一個事實，即TCP分組長度對于RTT是有影響的， 相同網(wǎng)絡(luò)條件下，較大TCP分組的RTT會較大。 TCP Vegas雖然在一定程度上提高了吞吐量，降低了丟包率，但是存在錯誤估算往返傳播時延的可能，從而導(dǎo)致算法性能下降的問題。 表3.1 TCP典型擁塞算法比較 優(yōu)點 缺點 TCP Tahoe 建立了TCP擁塞控制的基礎(chǔ)，避免了擁塞崩潰的發(fā)生 沒有快速恢復(fù)，輕度擁塞時，擁塞窗口減小過太（減至1）降低了吞吐量 TCP Re

65、no 增加r快速恢復(fù)，輕度擁塞時候保持較高擁塞窗口 檢測到丟包，重傳所有丟失與檢測到丟事件所有的包 TCP New Reno 利用一個ACK確認(rèn)部分發(fā)送窗口，避免了過多的重傳 在高速網(wǎng)絡(luò)中不能有效利用帶寬（其實這也是所有現(xiàn)行TCP共同的缺點） TCP Sack 檢測到擁塞時，選擇性的重傳包，避免了不必要的重傳 要修改TCP接收端，實現(xiàn)復(fù)雜 3.3 IP層擁塞控制算法 TCP基于窗口的擁塞控制機制對于Internet的魯棒性起到了關(guān)鍵性的作用。然而，隨著Internet本身的迅猛發(fā)展，其規(guī)模越來越龐大，結(jié)構(gòu)也日趨復(fù)雜，研究者們也認(rèn)識到僅僅依靠TCP端到端的擁塞

66、控制是不夠的，網(wǎng)絡(luò)也應(yīng)該參加資源的控制工作。網(wǎng)絡(luò)本身要參與到擁塞控制中，已經(jīng)成為了一個不可回避的問題。現(xiàn)在，IP層擁塞控制的研究也越來越多已經(jīng)形成了一個新的熱點研究方向。IP層擁塞控制就其本質(zhì)來說是通過對路由器緩沖區(qū)隊列中的分組實施調(diào)度和管理來影響TCP擁塞控制的動態(tài)性能以達(dá)到目的的。已經(jīng)出現(xiàn)了一系列的隊列調(diào)度和管理的算法來實現(xiàn)擁塞控制。下面我們會對其中的一些典型算法進行詳細(xì)描述。 3.3.1 先進先出（FIFO） FIFO又叫先到先服務(wù)(FCFS)，即第一個到達(dá)的包將被首先服務(wù)由于路由器的緩存總是有限的，當(dāng)緩沖區(qū)滿后，隨后到達(dá)的包將被丟棄。由于FIFO總是丟棄到達(dá)隊尾的包，所以經(jīng)常和去尾(Drop-Tail)算法在概念上被混淆。FIFO是一種包的調(diào)度策略，Drop-Tail是一種包的丟棄策略。由于FIFO和Drop-Tail實施起來比較簡單，因而目前去尾的先入先出是Internet上最廣泛使用的隊列調(diào)度管理方式。然而去尾的FIFO自身存在一些問題，例如：它不能區(qū)分不同的數(shù)據(jù)流，也不提供強制數(shù)據(jù)流遵守?fù)砣刂频臋C制，這就有可能讓某些數(shù)據(jù)流強占大量帶寬，引發(fā)公平性問題。例如UDP