課題來源： 指導(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ù)、回路往返時(shí)間)動(dòng)態(tài)變化，這些使得網(wǎng)絡(luò)擁塞的狀況愈加嚴(yán)重和復(fù)雜。擁塞容易造成傳輸時(shí)延和吞吐量等服務(wù)質(zhì)量(QoS)性能指標(biāo)下降，嚴(yán)重影響帶寬、緩存等網(wǎng)絡(luò)資源的利用率。因此，擁塞控制一直是網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)問題。網(wǎng)絡(luò)擁塞控制的目的不是要完全避免擁塞的發(fā)生，而是通過擁塞控制，提高網(wǎng)絡(luò)的性能及數(shù)據(jù)處理能力，保障網(wǎng)絡(luò)的穩(wěn)定和持續(xù)運(yùn)行，并且保證數(shù)據(jù)傳輸?shù)墓叫?。我們知道，網(wǎng)絡(luò)擁塞的根本原因在于端系統(tǒng)發(fā)出的數(shù)據(jù)超出了網(wǎng)絡(luò)的處理能力，而擁塞控制算法的基本思想則是解決這一問題，通常的方法就是TCP擁塞控制算法。以TCP為代表的端到端擁塞控制機(jī)制對(duì)互聯(lián)網(wǎng)的穩(wěn)定運(yùn)行起了很大的作用。但是隨著互聯(lián)網(wǎng)規(guī)模的增長，互連網(wǎng)上的用戶和應(yīng)用都在快速增長，它在很多方面己經(jīng)不能滿足復(fù)雜網(wǎng)絡(luò)中各種應(yīng)用的需求，擁塞已經(jīng)成為一個(gè)十分重要的問題。因此分析網(wǎng)絡(luò)擁塞控制協(xié)議,尋找最優(yōu)算法有著深遠(yuǎn)的目的和意義。國內(nèi)外同類課題研究現(xiàn)狀及發(fā)展趨勢(shì)：隨著計(jì)算機(jī)和通信技術(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的一個(gè)研究熱點(diǎn)。這種機(jī)制的最大優(yōu)勢(shì)是設(shè)計(jì)簡單，可擴(kuò)展性強(qiáng)?；ヂ?lián)網(wǎng)在過去的十幾年中經(jīng)歷了爆炸式的增長，這已經(jīng)充分證明了這種設(shè)計(jì)機(jī)制的成功。然而這種優(yōu)勢(shì)并不是沒有代價(jià)的，隨著互聯(lián)網(wǎng)用戶數(shù)量的膨脹，網(wǎng)絡(luò)的擁塞問題也越來越嚴(yán)重。例如由于隊(duì)列溢出，互聯(lián)網(wǎng)路由器會(huì)丟棄約10的數(shù)據(jù)包。在最初的TCP協(xié)議中只有流控制(flow control)而沒有擁塞控制，接收端利用TCP報(bào)頭將接收能力通知發(fā)送端。這樣的控制機(jī)制只考慮了接收端的接收能力，而沒有考慮網(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)計(jì)，互聯(lián)網(wǎng)上95的數(shù)據(jù)流使用的是TCP/IP協(xié)議，因此，互聯(lián)網(wǎng)上主要的互連協(xié)議TCP/IP的擁塞控制(congestion control)機(jī)制對(duì)控制網(wǎng)絡(luò)擁塞具有特別重要的意義。擁塞控制是確?；ヂ?lián)網(wǎng)魯棒性(robustness)的關(guān)鍵因素，也是各種管理控制機(jī)制和應(yīng)用(如多媒體通信中QoS控制、區(qū)分服務(wù)(differentiated services)的基礎(chǔ)，因此關(guān)于互聯(lián)網(wǎng)的擁塞控制問題一直是網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)，擁塞控制算法對(duì)保證Internet的穩(wěn)定具有十分重要的作用。課題研究的主要內(nèi)容和方法，研究過程中的主要問題和解決辦法：目前擁塞控制的研究一般分為TCP層的擁塞控制和IP層的擁塞控制，TCP層的擁塞控制主要是基于窗口的和式增加積式減少的擁塞控制機(jī)制，TCP基于窗口的端到端擁塞控制對(duì)于Internet的魯棒性起到了關(guān)鍵作用，并且在現(xiàn)實(shí)的互聯(lián)網(wǎng)中，擁塞控制的大部分工作都是由TCP來完成的，所以研究TCP層的擁塞控制對(duì)于網(wǎng)絡(luò)擁塞有相當(dāng)大的意義。隨著Internet本身的迅速發(fā)展，網(wǎng)絡(luò)規(guī)模越來越龐大，結(jié)構(gòu)越來越復(fù)雜，僅僅依靠TCP擁塞控制機(jī)制來提高網(wǎng)絡(luò)服務(wù)質(zhì)量還不夠。網(wǎng)絡(luò)必須參與資源的控制工作，因此需要采用路由器端的擁塞控制方法，即IP擁塞控制問題，通常也稱之為隊(duì)列管理機(jī)制，通過排隊(duì)算法決定哪些包可以傳輸，通過丟棄策略決定哪些包被丟棄以此分配緩存。未來的網(wǎng)絡(luò)擁塞控制的方向應(yīng)該是，以TCP層擁塞控制為基礎(chǔ)，結(jié)合IP層的隊(duì)列管理策略，共同解決網(wǎng)絡(luò)擁塞問題。第一：擁塞控制的基本知識(shí)研究。第二：TCP協(xié)議實(shí)現(xiàn)中一般都包含有四個(gè)相互關(guān)聯(lián)的擁塞控制算法的研究：慢作。因此，僅僅依靠TCP協(xié)議無法控制擁塞，最有效的擁塞檢測和回避是在路由器中實(shí)現(xiàn)的。第三：路由器中采用的擁塞控制算法通過檢測緩沖區(qū)的使用情況及隊(duì)列長度來判斷擁塞，通過丟棄緩沖隊(duì)列中的數(shù)據(jù)包來控制擁塞。 解決辦法：查找資料、請(qǐng)教導(dǎo)師、請(qǐng)教學(xué)者課題研究起止時(shí)間和進(jìn)度安排：起止時(shí)間：2012年1月22日2012年5月20日進(jìn)度安排：2012年1月22日2012年3月1日 確定論文題目，收集資料,寫開題報(bào)告。2012年3月2日2012年3月31日 收集資料、相關(guān)知識(shí)，對(duì)論文內(nèi)容進(jìn)行系統(tǒng)研究。2012年4月1日2012年4月15日 實(shí)現(xiàn)算法并應(yīng)用，進(jìn)行多次修改研究。2012年4月16日2012年5月1日 撰寫論文，準(zhǔn)備答辯。課題研究所需主要設(shè)備、儀器及藥品：計(jì)算機(jī)外出調(diào)研主要單位，訪問學(xué)者姓名：指導(dǎo)教師審查意見：指導(dǎo)教師 （簽字） 2012年3 月 教研室（研究室）評(píng)審意見：_教研室（研究室）主任 （簽字） 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ù)、回路往返時(shí)間)動(dòng)態(tài)變化，這些使得網(wǎng)絡(luò)擁塞的狀況愈加嚴(yán)重和復(fù)雜。擁塞容易造成傳輸時(shí)延和吞吐量等服務(wù)質(zhì)量(QoS)性能指標(biāo)下降，嚴(yán)重影響帶寬、緩存等網(wǎng)絡(luò)資源的利用率。因此，擁塞控制一直是網(wǎng)絡(luò)研究領(lǐng)域的熱點(diǎn)問題。Internet主要依賴TCP端到端擁塞控制來避免網(wǎng)絡(luò)擁塞，以TCP為代表的端到端擁塞控制機(jī)制對(duì)互聯(lián)網(wǎng)的穩(wěn)定運(yùn)行起了很大的作用。但是隨著互聯(lián)網(wǎng)規(guī)模的增長，互連網(wǎng)上的用戶和應(yīng)用都在快速增長，它在很多方面己經(jīng)不能滿足復(fù)雜網(wǎng)絡(luò)中各種應(yīng)用的需求，擁塞已經(jīng)成為一個(gè)十分重要的問題。近年來，在擁塞控制領(lǐng)域開展了大量的研究工作，擁塞控制算法可以分為兩個(gè)主要部分：在端系統(tǒng)上使用的源算法和在網(wǎng)絡(luò)設(shè)備上使用的鏈路算法。在路由器中引入適當(dāng)?shù)年?duì)列管理機(jī)制，可以有效地對(duì)擁塞進(jìn)行監(jiān)測和預(yù)防，路由器中的擁塞控制策略己經(jīng)成為一個(gè)研究熱點(diǎn)。本文首先對(duì)擁塞現(xiàn)象的產(chǎn)生進(jìn)行了說明，分析了擁塞現(xiàn)象產(chǎn)生的根源，總結(jié)了源算法和鏈路算法。接著，討論了幾種主要的TCP擁塞控制算法以及一些經(jīng)典的路由器擁塞控制策略以及對(duì)比了這兩種控制策略，并闡述了網(wǎng)絡(luò)擁塞控制的部分最新研究方法和成果。通過歸納、總結(jié)互聯(lián)網(wǎng)擁塞控制的研究現(xiàn)狀，主要對(duì)TCP層的網(wǎng)絡(luò)擁塞控制問題進(jìn)行了分析與研究。然后，在此基礎(chǔ)上，提出了一種改進(jìn)的擁塞控制算法，通過實(shí)驗(yàn)結(jié)果分析，此算法減少了網(wǎng)絡(luò)的丟包數(shù)和提高網(wǎng)絡(luò)的吞吐量，最后，分析了進(jìn)一步的研究方向。關(guān)鍵詞：擁塞控制；算法；TCP/IP；路由器目 錄第一章 引言11.1課題背景11.2網(wǎng)絡(luò)中的擁塞現(xiàn)象及原因11.3 網(wǎng)絡(luò)擁塞控制算法及存在的問題2第二章 擁塞現(xiàn)象及擁塞控制算法研究42.1 擁塞現(xiàn)象42.2 擁塞現(xiàn)象產(chǎn)生的原因52.3 擁塞控制算法的概況62.3.1 Internet的網(wǎng)絡(luò)模型72.3.2擁塞控制算法設(shè)計(jì)的困難72.3.3擁塞控制算法7第三章 擁塞控制算法比較93.1 TCP/IP體系結(jié)構(gòu)93.2 TCP層擁塞控制算法103.2.1 TCP Tahoe113.2.2 TCP Reno123.2.3 TCP New Reno123.2.4 TCP Sack123.2.5 TCP Vegas123.3 IP層擁塞控制算法133.3.1 先進(jìn)先出（FIFO）133.3.2 公平排隊(duì)（FQ）和加權(quán)公平排隊(duì)（WFQ）133.3.3 隨機(jī)檢測算法（RED）143.2 兩類算法比較153.5 其他擁塞控制算法163.5.1 基于方程的擁塞控制算法163.5.2 適應(yīng)性虛擬隊(duì)列163.5.3 TCP Westwood16第四章 擁塞控制算法改進(jìn)184.1 各階段算法改進(jìn)184.1.1慢啟動(dòng)184.1.2“超時(shí)重傳”和“快速重傳”194.2 對(duì)目的端點(diǎn)主機(jī)的擁塞控制策略的改進(jìn)224.3 對(duì)目的端點(diǎn)主機(jī)的擁塞控制策略的改進(jìn)23第五章 結(jié)束語27參考文獻(xiàn)28Abstract29第一章 引言1.1課題背景隨著計(jì)算機(jī)和通信技術(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的一個(gè)研究熱點(diǎn)。這種機(jī)制的最大優(yōu)勢(shì)是設(shè)計(jì)簡單，可擴(kuò)展性強(qiáng)?；ヂ?lián)網(wǎng)在過去的十幾年中經(jīng)歷了爆炸式的增長，這已經(jīng)充分證明了這種設(shè)計(jì)機(jī)制的成功。然而這種優(yōu)勢(shì)并不是沒有代價(jià)的，隨著互聯(lián)網(wǎng)用戶數(shù)量的膨脹，網(wǎng)絡(luò)的擁塞問題也越來越嚴(yán)重。例如由于隊(duì)列溢出，互聯(lián)網(wǎng)路由器會(huì)丟棄約10的數(shù)據(jù)包。在最初的TCP協(xié)議中只有流控制(flow control)而沒有擁塞控制，接收端利用TCP報(bào)頭將接收能力通知發(fā)送端。這樣的控制機(jī)制只考慮了接收端的接收能力，而沒有考慮網(wǎng)絡(luò)的傳輸能力，導(dǎo)致了網(wǎng)絡(luò)崩潰(congestion collapse)的發(fā)生。1986年10月，由于擁塞崩潰的發(fā)生，美國LBL到UC Berkeley的數(shù)據(jù)吞吐量從32Kbps跌落到40bps。據(jù)統(tǒng)計(jì)，互聯(lián)網(wǎng)上95的數(shù)據(jù)流使用的是TCP/IP協(xié)議，因此，互聯(lián)網(wǎng)上主要的互連協(xié)議TCP/IP的擁塞控制(congestion control) 機(jī)制對(duì)控制網(wǎng)絡(luò)擁塞具有特別重要的意義。擁塞控制是確?；ヂ?lián)網(wǎng)魯棒性(robustness)的關(guān)鍵因素，也是各種管理控制機(jī)制和應(yīng)用(如多媒體通信中QoS控制、區(qū)分服務(wù)的基礎(chǔ)，因此關(guān)于互聯(lián)網(wǎng)的擁塞控制問題一直是網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)，擁塞控制算法對(duì)保證Internet的穩(wěn)定具有十分重要的作用。1.2網(wǎng)絡(luò)中的擁塞現(xiàn)象及原因 當(dāng)在網(wǎng)絡(luò)中存在過多的報(bào)文時(shí)，網(wǎng)絡(luò)的性能會(huì)下降，這種現(xiàn)象稱為擁塞。使用圖1來描述擁塞的發(fā)生。當(dāng)負(fù)載較小時(shí)，吞吐量的增長和負(fù)載相比基本呈線性關(guān)系，延遲增長緩慢；在負(fù)載超過Knee之后，吞吐量增長緩慢，延遲增長較快；當(dāng)負(fù)載超過Cliff之后，吞吐量急劇下降，延遲急劇上升。由圖1.1得出，負(fù)載在Knee附近時(shí)網(wǎng)絡(luò)的使用效率最高。擁塞控制就是網(wǎng)絡(luò)節(jié)點(diǎn)采取措施來避免擁塞的發(fā)生或者對(duì)擁塞的發(fā)生做出反應(yīng)。在圖1.1中就是使負(fù)載保持在Knee附近，和流控制相比，擁塞控制主要考慮端節(jié)點(diǎn)之間的網(wǎng)絡(luò)環(huán)境，目的是使負(fù)載不超過網(wǎng)絡(luò)的傳送能力；而流控制主要考慮接收端，目的是使發(fā)送端的發(fā)送速率不超過接收端的接收能力。網(wǎng)絡(luò)中的擁塞來源于網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡性。擁塞不會(huì)隨著網(wǎng)絡(luò)處理能力的提高而消除。網(wǎng)絡(luò)的吞吐量與通信子網(wǎng)負(fù)荷(即通信子網(wǎng)中正在傳輸?shù)姆纸M數(shù))有著密切的關(guān)系。當(dāng)通信子網(wǎng)負(fù)荷比較小時(shí),網(wǎng)絡(luò)的吞吐量(分組數(shù)/秒)隨網(wǎng)絡(luò)負(fù)荷(每個(gè)節(jié)點(diǎn)中分組的平均數(shù))的增加而線性增加。當(dāng)網(wǎng)絡(luò)負(fù)荷增加到某一值后,若網(wǎng)絡(luò)吞吐量反而下降,則表征網(wǎng)絡(luò)中出現(xiàn)了擁塞現(xiàn)象。在一個(gè)出現(xiàn)擁塞現(xiàn)象的網(wǎng)絡(luò)中,到達(dá)某個(gè)節(jié)點(diǎn)的分組將會(huì)遇到無緩沖區(qū)可用的情況,從而使這些分組不得不由前一節(jié)點(diǎn)重傳,或者需要由源節(jié)點(diǎn)或源端系統(tǒng)重傳。當(dāng)擁塞比較嚴(yán)重時(shí),通信子網(wǎng)中相當(dāng)多的傳輸能力和節(jié)點(diǎn)緩沖器都用于這種無謂的重傳,從而使通信子網(wǎng)的有效吞吐量下降。由此引起惡性循環(huán),使通信子網(wǎng)的局部甚至全部處于死鎖狀態(tài),最終導(dǎo)致網(wǎng)絡(luò)有效吞吐量接近為零。 KneeCliff 吞吐量 負(fù)載 響應(yīng)時(shí)間 負(fù)載 圖1.1 負(fù)載與吞吐量、響應(yīng)時(shí)間關(guān)系曲線網(wǎng)絡(luò)發(fā)展到今天，其應(yīng)用領(lǐng)域不斷拓寬，各種應(yīng)用模式不斷涌現(xiàn)，像音頻和視頻這樣的對(duì)網(wǎng)絡(luò)資源要求較高的多媒體應(yīng)用更是呈現(xiàn)出爆炸性的增長趨勢(shì)。而目前的網(wǎng)絡(luò)資源相對(duì)于快速增長的網(wǎng)絡(luò)應(yīng)用模式是遠(yuǎn)遠(yuǎn)不夠的。因此如何使相對(duì)有限的網(wǎng)絡(luò)資源更加高效的利用，盡最大可能滿足這些應(yīng)用需求，避免擁塞崩潰的發(fā)生。這正是擁塞控制研究的目的和意義。1.3 網(wǎng)絡(luò)擁塞控制算法及存在的問題擁塞控制算法包含擁塞避免(congestion avoidance)和擁塞控制(congestion control)這兩種不同的機(jī)制。擁塞控制是“恢復(fù)”機(jī)制，它用于把網(wǎng)絡(luò)從擁塞狀態(tài)中恢復(fù)出來；擁塞避免是“預(yù)防”機(jī)制，它的目標(biāo)是避免網(wǎng)絡(luò)進(jìn)入擁塞狀態(tài)，使網(wǎng)絡(luò)運(yùn)行在高吞吐量、低延遲的狀態(tài)下。由網(wǎng)絡(luò)擁塞產(chǎn)生的原因可知，雖然擁塞的產(chǎn)生源于資源短缺，但單方面增加資源并不能避免擁塞的發(fā)生，有時(shí)甚至?xí)又負(fù)砣潭?。例如，增加網(wǎng)關(guān)緩存會(huì)增大報(bào)文通過網(wǎng)關(guān)的延遲，當(dāng)數(shù)據(jù)包經(jīng)過長時(shí)間的排隊(duì)完成轉(zhuǎn)發(fā)時(shí)它們?cè)缂撼瑫r(shí)，而源端認(rèn)為這些數(shù)據(jù)包已經(jīng)被丟棄，開始重傳，但這些數(shù)據(jù)包仍在網(wǎng)絡(luò)中傳輸，反而浪費(fèi)了網(wǎng)絡(luò)資源且加重了網(wǎng)絡(luò)擁塞。又如，處理機(jī)的處理速率太慢可能導(dǎo)致網(wǎng)絡(luò)擁塞，但單純提高該處理器的性能，網(wǎng)絡(luò)的瓶頸又會(huì)轉(zhuǎn)移到其它地方，導(dǎo)致系統(tǒng)各部分的不匹配?？偠灾?，擁塞控制算法的設(shè)計(jì)存在以下幾方面的困難：(1) 算法的分布性：擁塞控制算法的實(shí)現(xiàn)分布在不同的網(wǎng)絡(luò)層次以及多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn) 中，采用分布式的擁塞控制算法可以降低單個(gè)節(jié)點(diǎn)的處理復(fù)雜度，同時(shí)提高網(wǎng)絡(luò)的穩(wěn)健性。(2) 算法的可擴(kuò)展性：網(wǎng)絡(luò)中各處的性能有很大的差異，對(duì)于不同的網(wǎng)絡(luò)條件，如網(wǎng)絡(luò)規(guī)模的變化，帶寬的變化，鏈路傳輸時(shí)延的變化，不同的端系統(tǒng)狀況，以及存在多種數(shù)據(jù)流時(shí)，擁塞控制算法都應(yīng)具有相對(duì)較好的性能指標(biāo)。(3) 算法的性能要求：擁塞控制算法對(duì)性能有很高的要求，包括算法的效率、公平性、穩(wěn)定性、魯棒性和收斂性。通常的擁塞控制策略只能達(dá)到部分的性能要求，因此對(duì)這些指標(biāo)需要綜合考慮。(4) 算法的易實(shí)現(xiàn)性：擁塞控制算法的設(shè)計(jì)與實(shí)現(xiàn)要盡可能簡單，不僅要盡量減少附加的網(wǎng)絡(luò)流量，而且要減少反饋信號(hào)的復(fù)雜度。同時(shí)擁塞控制算法的設(shè)計(jì)還必須盡可能降低該算法在網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算量和實(shí)現(xiàn)的復(fù)雜度。(5) 擁塞的復(fù)雜性：計(jì)算機(jī)網(wǎng)絡(luò)已發(fā)展成為一個(gè)龐大的復(fù)雜性系統(tǒng)，其復(fù)雜性在于網(wǎng)絡(luò)拓?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ò)動(dòng)力學(xué)己經(jīng)發(fā)展成為一個(gè)新的跨學(xué)科領(lǐng)域。擁塞控制算法的分布性、網(wǎng)絡(luò)的復(fù)雜性和對(duì)擁塞控制算法的性能要求又使擁塞控制算法的設(shè)計(jì)具有很高的難度。到目前為止，擁塞問題還沒有得到很好的解決。第二章 擁塞現(xiàn)象及擁塞控制算法研究2.1 擁塞現(xiàn)象擁塞現(xiàn)象是指到達(dá)通信子網(wǎng)中某一部分的分組數(shù)量過多，使得該部分網(wǎng)絡(luò)來不及處理，以致引起這部分乃至整個(gè)網(wǎng)絡(luò)性能下降的現(xiàn)象，嚴(yán)重時(shí)甚至?xí)?dǎo)致網(wǎng)絡(luò)通信業(yè)務(wù)陷入停頓，即出現(xiàn)死鎖現(xiàn)象。這種現(xiàn)象跟公路網(wǎng)中經(jīng)常所見的交通擁擠一樣，當(dāng)節(jié)假日公路網(wǎng)中車輛大量增加時(shí)，各種走向的車流相互干擾，使每輛車到達(dá)目的地的時(shí)間都相對(duì)增加(即延遲增加)，甚至有時(shí)在某段公路上車輛因堵塞而無法開動(dòng)(即發(fā)生局部死鎖)。 網(wǎng)絡(luò)的吞吐量與通信子網(wǎng)負(fù)荷(即通信子網(wǎng)中正在傳輸?shù)姆纸M數(shù))有著密切的關(guān)系。當(dāng)通信子網(wǎng)負(fù)荷比較小時(shí)，網(wǎng)絡(luò)的吞吐量(分組數(shù)/秒)隨網(wǎng)絡(luò)負(fù)荷(每個(gè)節(jié)點(diǎn)中分組的平均數(shù))的增加而線性增加。當(dāng)網(wǎng)絡(luò)負(fù)荷增加到某一值后，若網(wǎng)絡(luò)吞吐量反而下降，則表征網(wǎng)絡(luò)中出現(xiàn)了擁塞現(xiàn)象。在一個(gè)出現(xiàn)擁塞現(xiàn)象的網(wǎng)絡(luò)中，到達(dá)某個(gè)節(jié)點(diǎn)的分組將會(huì)遇到無緩沖區(qū)可用的情況，從而使這些分組不得不由前一節(jié)點(diǎn)重傳，或者需要由源節(jié)點(diǎn)或源端系統(tǒng)重傳。當(dāng)擁塞比較嚴(yán)重時(shí)，通信子網(wǎng)中相當(dāng)多的傳輸能力和節(jié)點(diǎn)緩沖器都用于這種無謂的重傳，從而使通信子網(wǎng)的有效吞吐量下降。由此引起惡性循環(huán)，使通信子網(wǎng)的局部甚至全部處于死鎖狀態(tài)，最終導(dǎo)致網(wǎng)絡(luò)有效吞吐量接近為零。 計(jì)算機(jī)網(wǎng)絡(luò)(Computer network)就是把分布在不同地點(diǎn)的具有獨(dú)立功能的多臺(tái)計(jì)算機(jī)系統(tǒng)通過通信線路和網(wǎng)絡(luò)設(shè)備互相連接在一起，按照一定的網(wǎng)絡(luò)協(xié)議進(jìn)行信息通信，實(shí)現(xiàn)資源共享的計(jì)算機(jī)通信系統(tǒng)，它是計(jì)算機(jī)技術(shù)與通信技術(shù)結(jié)合的產(chǎn)物。20世紀(jì)80年代出現(xiàn)的互聯(lián)網(wǎng)(Internet)是現(xiàn)在全世界最大的計(jì)算機(jī)網(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臺(tái)計(jì)算機(jī)，從1986年接入6000臺(tái)計(jì)算機(jī)開始，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)可以輕易實(shí)現(xiàn)遠(yuǎn)程信息訪問、用戶間通訊、交互式娛樂、電子商務(wù)等?；ヂ?lián)網(wǎng)在社會(huì)各個(gè)領(lǐng)域的廣泛應(yīng)用使得傳統(tǒng)的信息獲取、傳送、存儲(chǔ)和處理方式發(fā)生了根本性的變化，改變了人們的生活與工作方式，對(duì)世界經(jīng)濟(jì)發(fā)展和社會(huì)生活方式產(chǎn)生了重大影響。自從互聯(lián)網(wǎng)誕生以來，網(wǎng)絡(luò)資源和網(wǎng)絡(luò)流量分布的不均衡使得擁塞問題一直困擾著其發(fā)展。伴隨著網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大和應(yīng)用類型的豐富，網(wǎng)絡(luò)擁塞也變得越來越嚴(yán)重。為易于擴(kuò)展，網(wǎng)絡(luò)端節(jié)點(diǎn)要求盡可能簡單，其不對(duì)數(shù)據(jù)流的狀態(tài)進(jìn)行記錄和管理，導(dǎo)致網(wǎng)絡(luò)無法對(duì)用戶的發(fā)送行為進(jìn)行約束。當(dāng)不存在一種對(duì)數(shù)據(jù)流進(jìn)行隔離的機(jī)制并且用戶又不對(duì)自身的發(fā)送行為進(jìn)行約束時(shí)，網(wǎng)絡(luò)的運(yùn)行就面臨著癱瘓的危險(xiǎn)。如果不及時(shí)采用適當(dāng)?shù)姆椒▉砜刂凭W(wǎng)絡(luò)擁塞，網(wǎng)絡(luò)的穩(wěn)定性將無法得到保障。實(shí)際上，這個(gè)現(xiàn)象在八十年代初就已經(jīng)出現(xiàn)，并被稱為“擁塞崩潰”(Congestion collapse)。計(jì)算機(jī)網(wǎng)絡(luò)中的鏈路容量、網(wǎng)絡(luò)節(jié)點(diǎn)中的緩存和處理器等都是網(wǎng)絡(luò)的資源，在某段時(shí)間內(nèi)如果用戶提供給網(wǎng)絡(luò)的負(fù)載大于網(wǎng)絡(luò)資源容量和網(wǎng)絡(luò)節(jié)點(diǎn)的處理能力，網(wǎng)絡(luò)便會(huì)產(chǎn)生阻塞，性能變壞，這就是網(wǎng)絡(luò)中的擁塞現(xiàn)象?？梢杂萌缦玛P(guān)系式表示：資源需求>網(wǎng)絡(luò)可用資源網(wǎng)絡(luò)產(chǎn)生擁塞時(shí)，網(wǎng)絡(luò)的性能便會(huì)降低，甚至有可能使整個(gè)系統(tǒng)發(fā)生崩潰，具體表現(xiàn)在網(wǎng)絡(luò)吞吐量和效率的降低、路由器緩沖隊(duì)列的急劇增加、報(bào)文延時(shí)的增加、報(bào)文的丟失、報(bào)文到達(dá)的延時(shí)抖動(dòng)劇烈等方面。當(dāng)網(wǎng)絡(luò)處于擁塞崩潰狀態(tài)時(shí)，微小的負(fù)載增量都將使網(wǎng)絡(luò)的有效吞吐量急劇下降。圖1.1清楚地表述了網(wǎng)絡(luò)負(fù)載與吞吐量和延遲之間的關(guān)系。當(dāng)網(wǎng)絡(luò)的負(fù)載較小時(shí)，隨著負(fù)載增加，吞吐量相應(yīng)增加。當(dāng)負(fù)載接近網(wǎng)絡(luò)的容量時(shí)，吞吐量將會(huì)停止增加，如果負(fù)載繼續(xù)增加，就會(huì)導(dǎo)致分組丟棄，這時(shí)網(wǎng)絡(luò)的吞吐量會(huì)突然降低，并接近于0。把吞吐量接近于0的現(xiàn)象稱為擁塞崩潰(congestion collapse)，并且把擁塞崩潰點(diǎn)稱為cliff，因?yàn)樨?fù)載超過這一點(diǎn)后吞吐量會(huì)突然降低，而把負(fù)載增加后吞吐量增加很少但傳輸延遲迅速增加的那點(diǎn)稱為擁塞臨界點(diǎn)(knee)。而擁塞避免(congestion avoidance)工作在knee處，它鼓勵(lì)用戶增加負(fù)載，只要不會(huì)使延遲增加就可以。當(dāng)網(wǎng)絡(luò)輕載時(shí)，隨著負(fù)載的增加，吞吐量隨之迅速增加，延遲增長緩慢；當(dāng)過了Knee點(diǎn)之后，負(fù)載增加時(shí)吞吐量增加趨于平緩， 延遲增長較快；當(dāng)超過Cliff點(diǎn)后負(fù)載增加時(shí)吞吐量急劇下降，延遲急劇上升。擁塞時(shí)網(wǎng)絡(luò)的具體表現(xiàn)為數(shù)據(jù)包經(jīng)受的時(shí)延增大，丟棄概率增高。而發(fā)送放在遇到大時(shí)延時(shí)進(jìn)行的不必要重傳會(huì)引起路由器利用其鏈路帶寬來轉(zhuǎn)發(fā)不必要的分組拷貝。數(shù)據(jù)包丟棄概率的增加也會(huì)引起發(fā)送方執(zhí)行重傳因緩存溢出而丟棄的數(shù)據(jù)包。這些都導(dǎo)致鏈路傳輸容量的浪費(fèi)，有效利用率降低。2.2 擁塞現(xiàn)象產(chǎn)生的原因擁塞發(fā)生的原因是“需求”大于“供給”。網(wǎng)絡(luò)中有限的資源由多個(gè)用戶共享使用。由于沒有“接納控制”算法，網(wǎng)絡(luò)無法根據(jù)資源的情況限制用戶的數(shù)量；缺乏中央控制，網(wǎng)絡(luò)也無法控制用戶使用資源的數(shù)量。目前Internet上用戶和應(yīng)用的數(shù)量都在迅速增長。如果不使用某種機(jī)制協(xié)調(diào)資源的使用，必然會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞。雖然擁塞源于資源短缺，但增加資源并不能避免擁塞的發(fā)生，有時(shí)甚至?xí)又負(fù)砣潭?。例如：增加網(wǎng)關(guān)緩沖會(huì)增大報(bào)文通過網(wǎng)關(guān)的延遲，如果總延遲超過端系統(tǒng)重傳時(shí)鐘的值，就會(huì)導(dǎo)致報(bào)文重傳，反而加重了擁塞。擁塞總是發(fā)生在網(wǎng)絡(luò)中資源“相對(duì)”短缺的位置。擁塞發(fā)生位置的不均衡反映了Internet的不均衡性。首先是資源分布的不均衡。圖2.1(a)中帶寬的分布是不均衡的，當(dāng)以1Mb/s的速率從S向D發(fā)送數(shù)據(jù)時(shí)，在網(wǎng)關(guān)R會(huì)發(fā)生擁塞。其次是流量分布的不均衡。圖2.1(b)中帶寬的分布是均衡的，當(dāng)A和B都以1Mb/s的速率向C發(fā)送數(shù)據(jù)時(shí)，在網(wǎng)關(guān)R也會(huì)發(fā)生擁塞。Internet中資源和流量分布的不均衡都是廣泛存在的，由此導(dǎo)致的擁塞不能使用增加資源的方法來解決。 DRS 1Mb 100Kb (a)AC 1Mb 1MbRBD 1Mb 1Mb (b) 圖2.1 擁塞產(chǎn)生原因示意網(wǎng)絡(luò)產(chǎn)生擁塞的根本原因在于用戶提供給網(wǎng)絡(luò)的負(fù)載大于網(wǎng)絡(luò)資源的容量和處理能力。擁塞產(chǎn)生的直接原因主要表現(xiàn)在如下三點(diǎn)：(1) 存儲(chǔ)空間不足。幾個(gè)輸入數(shù)據(jù)流共同需要同一個(gè)輸出端口，在這個(gè)端口就會(huì)建立排隊(duì)。如果沒有足夠的存儲(chǔ)空間存儲(chǔ)，數(shù)據(jù)包就會(huì)丟棄。對(duì)突發(fā)數(shù)據(jù)流更是如此。增加存儲(chǔ)空間在某種程度上可以緩解這一矛盾，但如果路由器有無限存儲(chǔ)量時(shí)，擁塞只是會(huì)變得更壞，而不是更好，因?yàn)樵诰W(wǎng)絡(luò)鬼數(shù)據(jù)包經(jīng)過長時(shí)間排隊(duì)完成轉(zhuǎn)發(fā)時(shí)，它們?cè)缫殉瑫r(shí)，發(fā)送端認(rèn)為它們己經(jīng)被丟棄，而這些數(shù)據(jù)包還會(huì)繼續(xù)向下一個(gè)路由器轉(zhuǎn)發(fā)，從而浪費(fèi)網(wǎng)絡(luò)資源且加重了網(wǎng)絡(luò)擁塞。(2) 帶寬容量不足。根據(jù)香農(nóng)信息理論，任何信道帶寬最大值即信道容量C=Blog2(1+S/N)(其中N為信道白噪聲的平均功率，S為信源的平均功率，B為信道帶寬)。所有信源發(fā)送的速率R必須小于或等于信道容量C。如果R>C，則在理論上無差錯(cuò)傳輸就是不可能的，所以在網(wǎng)絡(luò)低速鏈路處就會(huì)形成帶寬瓶頸，當(dāng)其滿足不了通過它的所有源端帶寬要求時(shí)，網(wǎng)絡(luò)就會(huì)發(fā)生擁塞。由于互聯(lián)網(wǎng)的設(shè)計(jì)機(jī)制導(dǎo)致其缺乏“接納能力”，因此在網(wǎng)絡(luò)資源不足時(shí)不能限制用戶數(shù)量，而只能靠降低服務(wù)質(zhì)量來繼續(xù)為用戶服務(wù)，也就是盡力而為的服務(wù)。擁塞發(fā)生后，表現(xiàn)為端到端時(shí)延加大、數(shù)據(jù)包被丟棄概率增大、網(wǎng)絡(luò)服務(wù)質(zhì)量下降、甚至整個(gè)系統(tǒng)崩潰等。1984年Nagle報(bào)告了由于TCP連接中沒有必要的重傳所誘發(fā)的擁塞崩潰，1986-1987年間這種現(xiàn)象曾經(jīng)多次發(fā)生，嚴(yán)重在端到端擁塞控制的實(shí)現(xiàn)中包括終端系統(tǒng)機(jī)制和路由器機(jī)制兩個(gè)有機(jī)部分。目前在Internet中，最主要的擁塞控制機(jī)制是由終端系統(tǒng)的TCP協(xié)議完成的，這也是網(wǎng)絡(luò)能保持魯棒性的主要原因。本文研究以TCP層擁塞控制為基礎(chǔ)，結(jié)合IP層的隊(duì)列管理策略，共同解決網(wǎng)絡(luò)擁塞問題。2.3 擁塞控制算法的概況擁塞控制方法：(1) 緩沖區(qū)預(yù)分配法。該法用于虛電路分組交換網(wǎng)中。在建立虛電路時(shí)，讓呼叫請(qǐng)求分組途經(jīng)的節(jié)點(diǎn)為虛電路預(yù)先分配一個(gè)或多個(gè)數(shù)據(jù)緩沖區(qū)。若某個(gè)節(jié)點(diǎn)緩沖器已被占滿，則呼叫請(qǐng)求分組另擇路由，或者返回一個(gè)“忙”信號(hào)給呼叫者。這樣，通過途經(jīng)的各節(jié)點(diǎn)為每條虛電路開設(shè)的永久性緩沖區(qū)(直到虛電路拆除)，就總能有空間來接納并轉(zhuǎn)送經(jīng)過的分組。此時(shí)的分組交換跟電路交換很相似。當(dāng)節(jié)點(diǎn)收到一個(gè)分組并將它轉(zhuǎn)發(fā)出去之后，該節(jié)點(diǎn)向發(fā)送節(jié)點(diǎn)返回一個(gè)確認(rèn)信息。該確認(rèn)一方面表示接收節(jié)點(diǎn)已正確收到分組，另一方面告訴發(fā)送節(jié)點(diǎn)，該節(jié)點(diǎn)已空出緩沖區(qū)以備接收下一個(gè)分組。上面是“停一等”協(xié)議下的情況，若節(jié)點(diǎn)之間的協(xié)議允許多個(gè)未處理的分組存在，則為了完全消除擁塞的可能性，每個(gè)節(jié)點(diǎn)要為每條虛電路保留等價(jià)于窗口大小數(shù)量的緩沖區(qū)。這種方法不管有沒有通信量，都有可觀的資源(線路容量或存儲(chǔ)空間)被某個(gè)連接占有，因此網(wǎng)絡(luò)資源的有效利用率不高。這種控制方法主要用于要求高帶寬和低延遲的場合，例如傳送數(shù)字化語音信息的虛電路。(2) 分組丟棄法。該法不必預(yù)先保留緩沖區(qū)，當(dāng)緩沖區(qū)占滿時(shí)，將到來的分組丟棄。若通信子網(wǎng)提供的是數(shù)據(jù)報(bào)服務(wù)，則用分組丟棄法來防止擁塞發(fā)生不會(huì)引起大的影響。但若通信子網(wǎng)提供的是虛電路服務(wù)，則必須在某處保存被丟棄分組的備份，以便擁塞解決后能重新傳送。有兩種解決被丟棄分組重發(fā)的方法，一種是讓發(fā)送被丟棄分組的節(jié)點(diǎn)超時(shí)，并重新發(fā)送分組直至分組被收到；另一種是讓發(fā)送被丟棄分組的節(jié)點(diǎn)在嘗試一定次數(shù)后放棄發(fā)送，并迫使數(shù)據(jù)源節(jié)點(diǎn)超時(shí)而重新開始發(fā)送。但是不加分辨地隨意丟棄分組也不妥，因?yàn)橐粋€(gè)包含確認(rèn)信息的分組可以釋放節(jié)點(diǎn)的緩沖區(qū)，若因節(jié)點(diǎn)元空余緩沖區(qū)來接收含確認(rèn)信息的分組，這便使節(jié)點(diǎn)緩沖區(qū)失去了一次釋放的機(jī)會(huì)。解決這個(gè)問題的方法可以為每條輸入鏈路永久地保留一塊緩沖區(qū)，以用于接納并檢測所有進(jìn)入的分組，對(duì)于捎帶確認(rèn)信息的分組，在利用了所捎帶的確認(rèn)釋放緩沖區(qū)后，再將該分組丟棄或?qū)⒃撋訋Ш孟⒌姆纸M保存在剛空出的緩沖區(qū)中。(3) 定額控制法。這種方法在通信子網(wǎng)中設(shè)置適當(dāng)數(shù)量的稱做“許可證”的特殊信息，一部分許可證在通信子網(wǎng)開始工作前預(yù)先以某種策略分配給各個(gè)源節(jié)點(diǎn)，另一部分則在子網(wǎng)開始工作后在網(wǎng)中四處環(huán)游。當(dāng)源節(jié)點(diǎn)要發(fā)送來自源端系統(tǒng)的分組時(shí)，它必須首先擁有許可證，并且每發(fā)送一個(gè)分組注銷一張?jiān)S可證。目的節(jié)點(diǎn)方則每收到一個(gè)分組并將其遞交給目的端系統(tǒng)后，便生成一張?jiān)S可證。這樣便可確保子網(wǎng)中分組數(shù)不會(huì)超過許可證的數(shù)量，從而防止了擁塞的發(fā)生。2.3.1 Internet的網(wǎng)絡(luò)模型 擁塞現(xiàn)象的發(fā)生和Internet的設(shè)計(jì)機(jī)制有著密切的聯(lián)系。Internet的網(wǎng)絡(luò)模型可以用以下幾點(diǎn)來抽象：(1) 報(bào)文交換(packet-switched)網(wǎng)絡(luò)。和電路交換(circuit-switched)相比，報(bào)文交換通過共享提高了資源的利用效率。但在共享方式下，如何保證用戶的服務(wù)質(zhì)量是一個(gè)很棘手的問題；在報(bào)文交換網(wǎng)絡(luò)中可能出現(xiàn)報(bào)文“亂序”現(xiàn)象，對(duì)亂序報(bào)文的處理增加了端系統(tǒng)的復(fù)雜性。(2) 無連接(connectionless)網(wǎng)絡(luò)。Internet的節(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ò)資源時(shí)難以保證服務(wù)質(zhì)量；在無連接模型中對(duì)數(shù)據(jù)發(fā)送源的追蹤能力很差，給網(wǎng)絡(luò)的安全帶來了隱患；無連接也是網(wǎng)絡(luò)中亂序報(bào)文出現(xiàn)的一個(gè)主要原因。(3) best-effort的服務(wù)模型。best-effort即網(wǎng)絡(luò)不對(duì)數(shù)據(jù)傳輸?shù)姆?wù)質(zhì)量提供保證。這個(gè)選擇和早期網(wǎng)絡(luò)中的應(yīng)用有關(guān)。傳統(tǒng)的網(wǎng)絡(luò)應(yīng)用主要是FTP、Telnet、SMTP等，它們對(duì)網(wǎng)絡(luò)性能(帶寬、延遲、丟失率等)的變化不敏感，best-effort模型可以滿足需要。但best-effort模型不能很好滿足新出現(xiàn)的多媒體應(yīng)用的要求，這些應(yīng)用對(duì)延遲、速率等性能的變化比較敏感。這要求網(wǎng)絡(luò)在原有服務(wù)模型的基礎(chǔ)上進(jìn)行擴(kuò)充。2.3.2擁塞控制算法設(shè)計(jì)的困難 擁塞控制算法的設(shè)計(jì)困難體現(xiàn)在以下方面：(1) 算法的分布性。擁塞控制算法的實(shí)現(xiàn)分布在多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中，必須使用不完整的信息完成控制，并使各節(jié)點(diǎn)協(xié)調(diào)工作，還必須考慮某些節(jié)點(diǎn)工作不正常的情況。(2) 網(wǎng)絡(luò)環(huán)境的復(fù)雜性。Internet中各處的網(wǎng)絡(luò)性能有很大的差異，算法必須具有很好的適應(yīng)性；另外由于Internet對(duì)報(bào)文的正確傳輸不提供保證，算法必須處理報(bào)文丟失、亂序到達(dá)等情況。(3) 算法的性能要求。擁塞控制算法對(duì)性能有很高的要求，包括算法的公平性、效率、穩(wěn)定性和收斂性等。某些性能目標(biāo)之間存在矛盾，在算法設(shè)計(jì)時(shí)需要進(jìn)行權(quán)衡。(4) 算法的開銷。擁塞控制算法必須盡量減少附加的網(wǎng)絡(luò)流量，特別是在擁塞發(fā)生時(shí)。在使用反饋式的控制機(jī)制時(shí)，這個(gè)要求增加了算法設(shè)計(jì)的困難。算法還必須盡量降低在網(wǎng)絡(luò)節(jié)點(diǎn)(特別是網(wǎng)關(guān))上的計(jì)算復(fù)雜性。目前的策略是將大部分計(jì)算放在端節(jié)點(diǎn)完成，在網(wǎng)關(guān)上只進(jìn)行少量的操作，這符合Internet的基本設(shè)計(jì)思想。2.3.3擁塞控制算法在設(shè)計(jì)和比較擁塞控制算法時(shí)，需要一定的評(píng)價(jià)方法。從用戶的角度出發(fā)，可以比較端系統(tǒng)的吞吐率、丟失率和延遲等指標(biāo)，這些是用戶所關(guān)心的。由于擁塞控制算法對(duì)整個(gè)網(wǎng)絡(luò)系統(tǒng)都有影響，在評(píng)價(jià)算法時(shí)更應(yīng)該從整個(gè)系統(tǒng)的角度出發(fā)進(jìn)行考慮。兩個(gè)重要的評(píng)價(jià)指標(biāo)是資源分配的效率和資源分配的公平性。 1、資源分配的效率資源分配的效率可以用Power函數(shù)來評(píng)價(jià)。Power函數(shù)定義為： Power=ThroughputResponse Time 在上式中，一般取a=l。如果評(píng)價(jià)偏重吞吐量，則取a>l；如果評(píng)價(jià)偏重反應(yīng)時(shí)間，則Power取a<l。Knee Cliff Power Load 圖2.2 Power函數(shù)示意圖2.2示意當(dāng)負(fù)載位于Knee時(shí)Power取最大值。使用Power函數(shù)有一定的局限性。它主要基于M/M/1隊(duì)列的網(wǎng)絡(luò)，并假設(shè)隊(duì)列的長度為無窮。Power函數(shù)一般在單資源、單用戶的情況下使用。 2、資源分配的公平性多用戶情況下需要考慮資源分配的公平性。公平性評(píng)價(jià)的主要方法包括Max-Min Fairness，F(xiàn)airness Index等。Max-min fairness被非正式的定義為：每個(gè)用戶的吞吐量至少和其它共享相同瓶頸的用戶的吞吐量相同。Max-Min Fairness是一種理想的狀況，但是它不能給出公平的程度。Fairness Index提供了一個(gè)計(jì)算公式，可以計(jì)算公平的程度。它定義為： Fairness Index的計(jì)算結(jié)果位于0和l之間，并且結(jié)果不受衡量單位的影響。它的一個(gè)性質(zhì)是：如果n個(gè)用戶中只有k個(gè)用戶平均共享資源，而另(n-k)個(gè)用戶沒有任何資源，計(jì)算結(jié)果為k/n。由于公平性是針對(duì)資源分配而言的，所以在評(píng)價(jià)前首先要確定“資源”的含義。目前大多數(shù)研究在評(píng)價(jià)公平性時(shí)都針對(duì)吞吐量，這是從用戶的角度出發(fā)考慮的，并不完全適合網(wǎng)絡(luò)中的資源狀況。網(wǎng)絡(luò)中的資源包括鏈路帶寬、網(wǎng)關(guān)的緩沖和網(wǎng)關(guān)的處理能力等，在考察公平性時(shí)應(yīng)當(dāng)將這些資源的分配情況綜合考慮。第三章 擁塞控制算法比較3.1 TCP/IP體系結(jié)構(gòu)TCP/IP(Transmission Control Protocol/Internet Protocol)即傳輸控制協(xié)議互連網(wǎng)絡(luò)協(xié)議，是ARPANET最有影響力的研究成果之一，現(xiàn)時(shí)的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)成為事實(shí)上的因特網(wǎng)上的通信標(biāo)準(zhǔn)，也是事實(shí)上的國際標(biāo)準(zhǔn)和工業(yè)標(biāo)準(zhǔn)。TCP/IP協(xié)議的體系結(jié)構(gòu)可以用一個(gè)四層的分層模型來描述，分成網(wǎng)絡(luò)接口層、IP層、運(yùn)輸層和應(yīng)用層。如圖所示：應(yīng)用層運(yùn)輸層（TCP/UDP層）IP層網(wǎng)絡(luò)接口層 圖3.1TCP/IP體系結(jié)構(gòu)網(wǎng)絡(luò)接口層又稱數(shù)據(jù)鏈路層，定義了特定介質(zhì)的物理連接特性，及在該介質(zhì)上發(fā)生、接收的信息幀的格式。其作用是傳輸經(jīng)IP層處理過的信息，并提供一個(gè)主機(jī)與實(shí)際網(wǎng)絡(luò)的接口，TCP/IP支持的數(shù)據(jù)鏈路技術(shù)很多，其特色在于它可以在任何一種物理網(wǎng)絡(luò)上運(yùn)行。IP層采用的是IP協(xié)議，負(fù)責(zé)IP數(shù)據(jù)報(bào)從主機(jī)發(fā)往任何網(wǎng)絡(luò)，到達(dá)其目的地。IP層為每一個(gè)IP數(shù)據(jù)報(bào)分配一個(gè)全網(wǎng)惟一的傳送地址(IP地址)，并據(jù)此IP地址段的信息把IP數(shù)據(jù)報(bào)轉(zhuǎn)發(fā)到其目的地。另外IP層還具有分組路由和擁塞控制等功能。 運(yùn)輸層(TCP/UDP層)提供的是端到端的通信功能，主要由兩個(gè)協(xié)議構(gòu)成。TCP協(xié)議提供的是面向連接的、可靠的傳輸服務(wù)；用戶數(shù)據(jù)報(bào)協(xié)議UDP提供的是無連接的、不可靠的傳輸服務(wù)。TCP協(xié)議還具有差錯(cuò)檢測、流量控制、擁塞控制等功能。應(yīng)用層包含了所有的高層協(xié)議，例如：遠(yuǎn)程登錄的虛擬終端協(xié)議(Telnet)、文件傳輸協(xié)議(FTP)、Web傳輸協(xié)議(HTTP)和郵件傳輸協(xié)議(SMTP)等，為各種用戶提供了所需的服務(wù)。目前擁塞控制的研究一般分為TCP層的擁塞控制和IP層的擁塞控制，TCP層的擁塞控制主要是基于窗口的和式增加積式減少的擁塞控制機(jī)制，TCP基于窗口的端到端擁塞控制對(duì)于Internet的魯棒性起到了關(guān)鍵作用，并且在現(xiàn)實(shí)的互聯(lián)網(wǎng)中，擁塞控制的大部分工作都是由TCP來完成的，所以研究TCP層的擁塞控制對(duì)于網(wǎng)絡(luò)擁塞有相當(dāng)大的意義。隨著Internet本身的迅速發(fā)展，網(wǎng)絡(luò)規(guī)模越來越龐大，結(jié)構(gòu)越來越復(fù)雜，僅僅依靠TCP擁塞控制機(jī)制來提高網(wǎng)絡(luò)服務(wù)質(zhì)量還不夠。網(wǎng)絡(luò)必須參與資源的控制工作，因此需要采用路由器端的擁塞控制方法，即IP擁塞控制問題，通常也稱之為隊(duì)列管理機(jī)制，通過排隊(duì)算法決定哪些包可以傳輸，通過丟棄策略決定哪些包被丟棄以此分配緩存。未來的網(wǎng)絡(luò)擁塞控制的方向應(yīng)該是，以TCP層擁塞控制為基礎(chǔ)，結(jié)合IP層的隊(duì)列管理策略，共同解決網(wǎng)絡(luò)擁塞問題。 NSPSMHTTPFTPDNSTELENT. UDP TCP RARP ARP IP ICMP局域網(wǎng)X.25網(wǎng)無線網(wǎng)電話網(wǎng).應(yīng)用層運(yùn)輸層 IP層網(wǎng)絡(luò)接口層圖3.2 TCP/IP體系結(jié)構(gòu)中各層所應(yīng)用的主要協(xié)議口3.2 TCP層擁塞控制算法互聯(lián)網(wǎng)最初源于美國國防部的ARPANET計(jì)劃。上世紀(jì)60年代中期正是冷戰(zhàn)的高峰，美國國防部希望有一個(gè)命令和控制網(wǎng)絡(luò)，以確保在核戰(zhàn)爭的條件下幸免于難，而傳統(tǒng)基于電路交換的電話網(wǎng)絡(luò)則過于脆弱。國防部指定其下屬的高級(jí)研究計(jì)劃局解決這個(gè)問題，從而誕生ARPANET，其最大特點(diǎn)是采用無連接的端到端報(bào)文交換服務(wù)。到了80年代中期，演變?yōu)榛ヂ?lián)網(wǎng)。TCP協(xié)議最初只是作為NSFNET的程序規(guī)范，即RFC 793，這也是最早的較為完整且齊全的TCP規(guī)范。這個(gè)規(guī)范簡單描述了如何進(jìn)行主機(jī)到主機(jī)的可靠傳輸，并描述了傳輸控制協(xié)議執(zhí)行的功能，相應(yīng)的實(shí)現(xiàn)程序及程序接口。TCP協(xié)議在設(shè)計(jì)之初就被賦予了很高的使命，需要成為報(bào)文交換計(jì)算機(jī)網(wǎng)絡(luò)和這些網(wǎng)絡(luò)互聯(lián)系統(tǒng)中的高可靠性傳輸協(xié)議。需要明確的是，網(wǎng)絡(luò)中的可靠傳輸包括兩方面：首先是數(shù)據(jù)的正確，由于以前的傳輸介質(zhì)質(zhì)量很差，所以在傳輸層及以下各層協(xié)議中都實(shí)現(xiàn)了校驗(yàn)和計(jì)算；其次是數(shù)據(jù)的完整保序，這個(gè)特性需要TCP執(zhí)行復(fù)雜的操作來實(shí)現(xiàn)，通常我們強(qiáng)調(diào)TCP的可靠傳輸時(shí)主要指后者。目前在Internet上實(shí)際使用的擁塞控制基本上是建立在TCP窗口控制基礎(chǔ)之上的，據(jù)統(tǒng)計(jì)，Internet上的95的數(shù)據(jù)流使用的是TCP協(xié)議，因此TCP擁塞控制一直是網(wǎng)絡(luò)擁塞控制研究的重點(diǎn)。TCP擁塞控制的基本框架是在文中提出的，文中Van Jacobson指出用顯式的方法來實(shí)現(xiàn)基于窗口的運(yùn)輸層協(xié)議會(huì)導(dǎo)致端系統(tǒng)對(duì)網(wǎng)絡(luò)擁塞的錯(cuò)誤反應(yīng)，并提出了一系列算法來解決這一問題，這些算法包括：RRT的估計(jì)重傳計(jì)數(shù)器的指數(shù)回退、慢啟動(dòng)、擁塞窗口的動(dòng)念調(diào)整等。正是這些算法奠定了TCP擁塞控制的基礎(chǔ)。TCP/IP一般通過Internet串行線路協(xié)議SLIP或點(diǎn)對(duì)點(diǎn)協(xié)議PPP在串行線上進(jìn)行數(shù)據(jù)傳送。TCP/IP協(xié)議的基本傳輸單位是數(shù)據(jù)包 (datagram)。TCP協(xié)議負(fù)責(zé)把數(shù)據(jù)分成若干個(gè)數(shù)據(jù)包/段，并給每個(gè)數(shù)據(jù)包加上包頭，IP協(xié)議在每個(gè)包頭上再加上接收端主機(jī)地址，這樣數(shù)據(jù)找到自己要去的地方。如果傳輸過程中出現(xiàn)數(shù)據(jù)丟失、數(shù)據(jù)失真等情況，TCP協(xié)議會(huì)自動(dòng)要求數(shù)據(jù)重新傳輸并重新組包。TCP協(xié)議保證數(shù)據(jù)傳輸?shù)馁|(zhì)量，總之IP協(xié)議保證數(shù)據(jù)的傳輸。數(shù)據(jù)在傳輸時(shí)每通過一層就要在數(shù)據(jù)上加個(gè)包頭，其中數(shù)據(jù)供接收端同一層協(xié)議使用，而在接收端每經(jīng)過一層要把用過的包頭去掉，這樣來保證傳輸數(shù)據(jù)的格式完全一致。TCP/IP協(xié)議需要針對(duì)不同的網(wǎng)絡(luò)進(jìn)行不同的設(shè)置，且每個(gè)節(jié)點(diǎn)一般需要一個(gè)“IP地址”、一個(gè)“子網(wǎng)掩碼”、一個(gè)“默認(rèn)網(wǎng)關(guān)”。不過可以通過動(dòng)態(tài)主機(jī)配置協(xié)議（DHCP），給客戶端自動(dòng)分配一個(gè)IP地址，這樣避免了出錯(cuò)也簡化了TCP/IP協(xié)議的設(shè)置，我們可以指定一臺(tái)計(jì)算機(jī)具有多個(gè)IP地址，因此在訪問互聯(lián)網(wǎng)時(shí)不要以為一個(gè)IP地址就是一臺(tái)計(jì)算機(jī)；另外通過特定的技術(shù)，也可以使多臺(tái)服務(wù)器共用一個(gè)IP地址，這些服務(wù)器在用戶看起來就像一臺(tái)主機(jī)似的。在TCP/IP中所有的協(xié)議都被封裝在IP分組中通過IP網(wǎng)間網(wǎng)傳輸。IP是一個(gè)路由協(xié)議這就意味著使用IP通信的兩個(gè)節(jié)點(diǎn)不必連接到同一物理線路上(不進(jìn)行路由)。擁塞控制的方法，無論什么形式都可以分為兩類：開環(huán)控制和閉環(huán)控制。開環(huán)控制是預(yù)先設(shè)計(jì)一個(gè)好的網(wǎng)絡(luò)，確保它不會(huì)發(fā)生擁塞，而網(wǎng)絡(luò)在運(yùn)行過程中不再采取措施。比較典型的例子就是資源預(yù)留協(xié)議(RSVP)，這類控制機(jī)制較適用于簡單的音頻和活動(dòng)圖像業(yè)務(wù)。但是網(wǎng)絡(luò)的業(yè)務(wù)流量通常是很難精確控制對(duì)于復(fù)雜的網(wǎng)絡(luò)系統(tǒng)來說是遠(yuǎn)遠(yuǎn)不夠的。顯然，對(duì)網(wǎng)絡(luò)這樣不斷變化的復(fù)雜系統(tǒng)，開環(huán)系統(tǒng)并不是理想的選擇。TCP是目前Internet上應(yīng)用廣泛的傳輸層協(xié)議，實(shí)施擁塞控制是TCP的兩個(gè)主要任務(wù)之一，由于IP層在發(fā)生擁塞時(shí)不向端系統(tǒng)提供任何顯式的反饋信息，因而TCP擁塞控制采用的是基于窗口的端到端的閉環(huán)控制方式。閉環(huán)控制能夠根據(jù)網(wǎng)絡(luò)中反饋至端系統(tǒng)的擁塞指示信息，依據(jù)一定的控制策略，及時(shí)調(diào)整源端系統(tǒng)的數(shù)據(jù)傳輸速率，避免網(wǎng)絡(luò)狀況的惡化，既保證了傳輸?shù)馁|(zhì)量又能充分利用網(wǎng)絡(luò)資源。在TCP擁塞控制的算法中，有以下幾個(gè)重要參數(shù)：擁塞窗口(cwnd)：擁塞控制的關(guān)鍵參數(shù)，控制源端在擁塞情況下一次最多能發(fā)送多少數(shù)據(jù)包。通告窗口(awnd)：接收端對(duì)源端發(fā)送窗口大小所做的限制，在建立連接時(shí)由接收方通過ACK確認(rèn)捎帶給源端。慢啟動(dòng)閾值(ssthresh)：用來控制源端從慢啟動(dòng)階段轉(zhuǎn)換到擁塞避免階段的門限值。回路響應(yīng)時(shí)間(RTT)：一個(gè)數(shù)據(jù)包從源端發(fā)送到接收端，直至源端收到目的端對(duì)該數(shù)據(jù)包確認(rèn)信息所經(jīng)歷的時(shí)間間隔。超時(shí)重傳計(jì)數(shù)器(RTO)：描述數(shù)據(jù)包從發(fā)送到失效的時(shí)間間隔，是源端用來判斷數(shù)據(jù)包是否丟失和網(wǎng)絡(luò)擁塞的重要參數(shù)，通常設(shè)為2RTT或5RTT。TCP的擁塞控制由慢啟動(dòng)、擁塞控制、快速重傳和快速恢復(fù)四個(gè)核心算法組成。這四個(gè)基本算法互相聯(lián)系，經(jīng)過大量的事實(shí)證明，它對(duì)Internet上大批量文件傳輸?shù)确?wù)具有良好的適應(yīng)性，成為目前在Internet上主要使用的端系統(tǒng)擁塞控制機(jī)制。此后的TCP擁塞控制方法基本上都是在此基礎(chǔ)上的一些改進(jìn)。以下是對(duì)這些改進(jìn)中的典型算法的分析。3.2.1 TCP TahoeTahoe算法由3個(gè)主要部分組成，和式增加積式減少(AIMD)、慢啟動(dòng)、快速重傳?！昂褪皆黾印庇脕碇?jǐn)慎地探測端到端路徑上的可用帶寬，具體表現(xiàn)為TCP發(fā)送方在無丟包事件發(fā)生時(shí)，每收到一個(gè)ACK，就將擁塞窗口增加一點(diǎn)，直到丟包事件發(fā)生，這個(gè)線性增長階段也稱為擁塞避免?！胺e式減少”方法在丟包事件發(fā)生時(shí)將當(dāng)前的擁塞窗口值減半，這樣就降低了發(fā)送方的發(fā)送速率，從而減輕擁塞程度。慢啟動(dòng)是數(shù)據(jù)發(fā)送的初始化階段，發(fā)送方以很慢的速率開始發(fā)送，但以指數(shù)的速度快速增加其發(fā)送速率，從而減小初始階段因發(fā)送方發(fā)送窗口過小而造成的帶寬浪費(fèi)。快速重傳是當(dāng)發(fā)送方收到3個(gè)冗余的ACK而檢測到丟包時(shí)不必等到重傳超時(shí)而立即重傳丟失的包。這些方法正是TCP擁塞控制的基礎(chǔ)，以后的各種改進(jìn)都依賴于此基礎(chǔ)。3.2.2 TCP RenoTCP Reno是在Tahoe的基礎(chǔ)上增加了“快速恢復(fù)”階段。和Tahoe相比較，Reno在快速重傳后并不將擁塞窗口減至1MSS，進(jìn)入慢啟動(dòng)階段。而是將擁塞窗口減半，進(jìn)入擁塞避免階段，這是因?yàn)榕c發(fā)生超時(shí)事件不同，收到冗余的ACK表明發(fā)送的其它包已經(jīng)被接收方收到，兩個(gè)端系統(tǒng)間仍有數(shù)據(jù)的流動(dòng)，網(wǎng)絡(luò)處于輕度擁塞。因此，發(fā)送端直接將擁塞窗口減至1MSS是不合適的，但Reno算法也存在缺點(diǎn)，當(dāng)發(fā)送端檢測到擁塞后，要重傳數(shù)據(jù)包丟失到檢測到丟失時(shí)發(fā)送的全部數(shù)據(jù)包，這其中包括已正確傳輸?shù)浇邮斩耍槐刂貍鞯陌Ｏ旅娴腘ew Reno和Sack算法正式針對(duì)Reno算法的這一缺點(diǎn)的改進(jìn)。3.2.3 TCP New RenoNew Reno對(duì)Reno的改進(jìn)是通過盡量避免Reno在快速恢復(fù)階段的許多重傳超時(shí)，利用一個(gè)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算法也是對(duì)Reno的改進(jìn)，當(dāng)檢測到擁塞后，不用重傳數(shù)據(jù)包丟失到檢測到丟失時(shí)發(fā)送的全部數(shù)據(jù)包，而是對(duì)這些數(shù)據(jù)包進(jìn)行有選擇的確認(rèn)和重傳，從而避免不必要的重傳，減少延時(shí)，提高網(wǎng)絡(luò)吞吐量。由于使用選擇重傳，所以在一個(gè)窗口中數(shù)據(jù)包多丟失的情況下，Sack性能優(yōu)于New Reno，但是Sack的主要缺點(diǎn)是要修改接收端TCP。 3.2.5 TCP VegasTCP Vegas算法和以前的算法大不相同，它是通過觀察以前TCP連接中的RRT值的改變來控制擁塞窗口的，如果RRT值變大，TCP Vegas就認(rèn)為網(wǎng)絡(luò)發(fā)生擁塞，就減小擁塞窗口；反之，則增大擁塞窗口。這樣做的好處是擁塞控制機(jī)制的出發(fā)只和RRT的改變有關(guān)，而與包的具體時(shí)延無關(guān)。為了提高吞吐率、降低分組丟棄率，TCP Vegas采用了3種與眾不同的技術(shù)：(1) 新的重傳機(jī)制，它將引發(fā)重傳的重復(fù)應(yīng)答(ACK)數(shù)從3個(gè)減少到2個(gè)或者1個(gè)，因此TCP能夠?qū)Ψ纸M丟棄做出更快速響應(yīng)。(2) 新的擁塞避免機(jī)制，它改變了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) 擴(kuò)展的“慢啟動(dòng)”(slow-start)機(jī)制，在Reno等版本的“慢啟動(dòng)”階段，發(fā)送窗13以指數(shù)增長方式更新，而Vegas“慢啟動(dòng)”階段的發(fā)送窗口增長速度為Reno等版本的1/2，主要目的是在這一階段利用(2)所描述的方法檢測和避免擁塞。由于TCP Vegas只和RTT的改變有關(guān)，RRT的準(zhǔn)確度對(duì)于Vegas來說非常重要，事實(shí)上，在其實(shí)現(xiàn)中也采取了許多措施來保證RTT計(jì)量的精確度，如更細(xì)粒度的時(shí)問計(jì)算等。但是，它忽略了一個(gè)事實(shí)，即TCP分組長度對(duì)于RTT是有影響的， 相同網(wǎng)絡(luò)條件下，較大TCP分組的RTT會(huì)較大。TCP Vegas雖然在一定程度上提高了吞吐量，降低了丟包率，但是存在錯(cuò)誤估算往返傳播時(shí)延的可能，從而導(dǎo)致算法性能下降的問題。表3.1 TCP典型擁塞算法比較優(yōu)點(diǎn)缺點(diǎn)TCP Tahoe建立了TCP擁塞控制的基礎(chǔ)，避免了擁塞崩潰的發(fā)生沒有快速恢復(fù)，輕度擁塞時(shí)，擁塞窗口減小過太（減至1）降低了吞吐量TCP Reno增加r快速恢復(fù)，輕度擁塞時(shí)候保持較高擁塞窗口檢測到丟包，重傳所有丟失與檢測到丟事件所有的包TCP New Reno利用一個(gè)ACK確認(rèn)部分發(fā)送窗口，避免了過多的重傳在高速網(wǎng)絡(luò)中不能有效利用帶寬（其實(shí)這也是所有現(xiàn)行TCP共同的缺點(diǎn)）TCP Sack檢測到擁塞時(shí)，選擇性的重傳包，避免了不必要的重傳要修改TCP接收端，實(shí)現(xiàn)復(fù)雜3.3 IP層擁塞控制算法TCP基于窗口的擁塞控制機(jī)制對(duì)于Internet的魯棒性起到了關(guān)鍵性的作用。然而，隨著Internet本身的迅猛發(fā)展，其規(guī)模越來越龐大，結(jié)構(gòu)也日趨復(fù)雜，研究者們也認(rèn)識(shí)到僅僅依靠TCP端到端的擁塞控制是不夠的，網(wǎng)絡(luò)也應(yīng)該參加資源的控制工作。網(wǎng)絡(luò)本身要參與到擁塞控制中，已經(jīng)成為了一個(gè)不可回避的問題。現(xiàn)在，IP層擁塞控制的研究也越來越多已經(jīng)形成了一個(gè)新的熱點(diǎn)研究方向。IP層擁塞控制就其本質(zhì)來說是通過對(duì)路由器緩沖區(qū)隊(duì)列中的分組實(shí)施調(diào)度和管理來影響TCP擁塞控制的動(dòng)態(tài)性能以達(dá)到目的的。已經(jīng)出現(xiàn)了一系列的隊(duì)列調(diào)度和管理的算法來實(shí)現(xiàn)擁塞控制。下面我們會(huì)對(duì)其中的一些典型算法進(jìn)行詳細(xì)描述。3.3.1 先進(jìn)先出（FIFO） FIFO又叫先到先服務(wù)(FCFS)，即第一個(gè)到達(dá)的包將被首先服務(wù)由于路由器的緩存總是有限的，當(dāng)緩沖區(qū)滿后，隨后到達(dá)的包將被丟棄。由于FIFO總是丟棄到達(dá)隊(duì)尾的包，所以經(jīng)常和去尾(Drop-Tail)算法在概念上被混淆。FIFO是一種包的調(diào)度策略，Drop-Tail是一種包的丟棄策略。由于FIFO和Drop-Tail實(shí)施起來比較簡單，因而目前去尾的先入先出是Internet上最廣泛使用的隊(duì)列調(diào)度管理方式。然而去尾的FIFO自身存在一些問題，例如：它不能區(qū)分不同的數(shù)據(jù)流，也不提供強(qiáng)制數(shù)據(jù)流遵守?fù)砣刂频臋C(jī)制，這就有可能讓某些數(shù)據(jù)流強(qiáng)占大量帶寬，引發(fā)公平性問題。例如UDP