【正文】 第一章TCP擁塞控制機制第一章 TCP 擁塞控制機制1．1 擁塞現(xiàn)象與控制1．1．1 擁塞現(xiàn)象的產(chǎn)生當(dāng)網(wǎng)絡(luò)中存在過多的數(shù)據(jù)包時，網(wǎng)絡(luò)的性能就會下降，這種現(xiàn)象稱為擁塞。在網(wǎng)絡(luò)發(fā)生擁塞時，會導(dǎo)致吞吐量下降，嚴重時會發(fā)生“擁塞崩潰”（congestion collapse）現(xiàn)象。一般來說，擁塞崩潰發(fā)生在網(wǎng)絡(luò)負載的增加導(dǎo)致網(wǎng)絡(luò)效率的降低的時候。1986年10月，Internet遭遇了第一次“擁塞崩潰”事故[1]。在這個期間，由LBL到UC Berkeley的吞吐量從32Kbps跌到了40bps，而這兩個地方的空間距離相隔了400英碼，其站點則隔了兩個IMP的轉(zhuǎn)發(fā)距離。Floyd總結(jié)出擁塞崩潰主要包括以下幾種：傳統(tǒng)的崩潰、未傳送數(shù)據(jù)包導(dǎo)致的崩潰、由于數(shù)據(jù)包分段造成的崩潰、日益增長的控制信息流造成的崩潰等。 網(wǎng)絡(luò)負載與吞吐量及響應(yīng)時間的關(guān)系對于擁塞現(xiàn)象，我們[2]。當(dāng)網(wǎng)絡(luò)負載較小時，吞吐量基本上隨著負載的增長而增長，呈線性關(guān)系，響應(yīng)時間增長緩慢。當(dāng)負載達到網(wǎng)絡(luò)容量時，吞吐量呈現(xiàn)出緩慢增長，而響應(yīng)時間急劇增加，這一點稱為Knee。如果負載繼續(xù)增加，路由器開始丟包，當(dāng)負載超過一定量時，吞吐量開始急劇下降，這一點稱為Cliff。1．1．2 控制階段的劃分TCP擁塞控制過程可分為四個階段[3]：(1)慢啟動階段：舊的TCP在啟動一個連接時會向網(wǎng)絡(luò)中發(fā)送許多數(shù)據(jù)包，由于一些路由器必須對數(shù)據(jù)包排隊，所以這樣就有可能耗盡存儲空間，從而導(dǎo)致TCP連接的吞吐量(throughput)急劇下降。避免這種情況發(fā)生的算法就是慢啟動。當(dāng)建立新的TCP連接時，擁塞窗口(cwnd)初始化為一個數(shù)據(jù)包大小(一個數(shù)據(jù)包缺省為536或512bytes)。源端按cwnd大小發(fā)送數(shù)據(jù)，每收到一個ACK確認，cwnd就增加一個數(shù)據(jù)包發(fā)送量。很顯然，cwnd的增長將隨RTT呈指數(shù)級(exponential)增長：1個、2個、4個、8個…。源端向網(wǎng)絡(luò)中發(fā)送的數(shù)據(jù)量將急劇增加。(2)擁塞避免階段：當(dāng)發(fā)現(xiàn)超時或收到3個相同ACK確認幀時，網(wǎng)絡(luò)即發(fā)生擁塞(TCP這一假定是基于由傳輸引起的數(shù)據(jù)包損壞和丟失的概率很小(小于1%)[3])。此時就進入擁塞避免階段。慢啟動閾值(ssthresh)被設(shè)置為當(dāng)前cwnd的一半，如果是超時，cwnd還要被置1。如果此時cwnd ssthresh，TCP就重新進入慢啟動過程；如果cwndssthresh，TCP就執(zhí)行擁塞避免算法，cwnd在每次收到一個ACK時只增加1/cwnd個數(shù)據(jù)包(這里將數(shù)據(jù)包大小segsize假定為1)，所以在擁塞避免算法中cwnd的增長不是指數(shù)的，而是線性的(linear)。(3)快速重傳和恢復(fù)階段：當(dāng)數(shù)據(jù)包超時時，cwnd要被置為1，重新進入慢啟動，這會導(dǎo)致過大地減小發(fā)送窗口尺寸，降低TCP連接的吞吐量。所以快速重傳和恢復(fù)就是在源端收到3個或3個以上重復(fù)ACK時，就斷定數(shù)據(jù)包已經(jīng)丟失，重傳數(shù)據(jù)包，同時將ssthresh置為當(dāng)前cwnd的一半，而不必等到RTO超時?！　?慢啟動和擁塞避免（不含快速重傳和恢復(fù)） 快速重傳與恢復(fù)由以上分析可以看出：TCP使用的是一種和式增加積式減少(Additive Increase Multiplicative Decrease,AIMD)的基于窗口的端到端擁塞控制機制。TCP源端“發(fā)送速率”由擁塞窗口控制。如果有一個數(shù)據(jù)包丟失，發(fā)送窗口則要減半；否則就簡單地增加一個數(shù)據(jù)包的發(fā)送量。大量的實踐證明這種擁塞控制機制對Internet上大批量文件傳輸?shù)缺M量做好(besteffort)型服務(wù)具有較好的適應(yīng)性。1．2 國外相關(guān)工作1．2．1 控制機制的發(fā)展：Tahoe到Reno1988年Van Jacobson在文獻[1]指出了TCP在控制網(wǎng)絡(luò)擁塞方面的不足，并提出了“慢啟動”(slow start)算法、“擁塞避免”(congestion avoidance)算法。1990年出現(xiàn)的TCP Reno版本增加了“快速重傳”(fast retransmit)算法、“快速恢復(fù)”(fast recovery)算法，避免了網(wǎng)絡(luò)擁塞不夠嚴重時采用“慢啟動”算法而造成過大地減小發(fā)送窗口尺寸的現(xiàn)象，這樣TCP的擁塞控制就由這4個核心部分組成，這就是TCP Reno版本。事實上，在TCP Reno之前還有TCP Tahoe，兩者主要區(qū)別在于后者只有擁塞控制的前三部分，沒有快速恢復(fù)(fast retransmit)，所以可以認為TCP Reno是TCP Tahoe的改進版[4]。但TCP Reno算法仍有不足。首先，源端在檢測到擁塞后，要重傳自數(shù)據(jù)包丟失到檢測到丟失時發(fā)送的全部數(shù)據(jù)包(即Gobackn算法)，而這中間有些數(shù)據(jù)包是正確傳到接收端，不必重傳的。另外，在大多數(shù)TCP實現(xiàn)中，RTO（Retransmit TimeOut）計數(shù)器的值被認為是RTT（Round Trip Time）的均值和方差的估計值的函數(shù)。而準確估計RTO和RTT值并不是一件容易的事。RTT最簡潔的估計方法是應(yīng)用舊RTT值和新RTT采樣值的求加權(quán)和。如下式[5]： (1)，其中為加權(quán)因子且。當(dāng)接近1時。估計的RTT值在最近采樣的短時間內(nèi)幾乎不發(fā)生變化(例如一個經(jīng)歷長時延的數(shù)據(jù)包的RTT)。如果接近0，RTT對時延變化的反應(yīng)就非常靈敏。理論上，RTT的測量比較簡單。它只是數(shù)據(jù)包從發(fā)出到確認ACK返回源端的時間。但由于TCP使用的是用一個ACK確認所有已收到數(shù)據(jù)的“累積”確認方式，所以RTT的估計在實際中往往很復(fù)雜。1．2．2 新改進：NewReno、 SACK和Vegas針對以上缺點，近年來又提出了一些改進算法，其中NewReno和SACK都是改進版。SACK算法是在Reno基礎(chǔ)上進行擴展，對數(shù)據(jù)包進行有選擇地確認和重傳。這樣，源端就能準確地知道哪些數(shù)據(jù)包正確地傳到接收端，從而避免不必要地重傳，減少時延，提高網(wǎng)絡(luò)吞吐量。NewReno沒有選用SACK方法，而是盡力避免了Reno在快速恢復(fù)階段的許多重傳超時，利用一個ACK確認部分發(fā)送窗口，立即重傳余下的數(shù)據(jù)包。顯然,NewReno只需修改源端代碼。綜合來看，即使源端不通過等待超時來恢復(fù)一個窗口數(shù)據(jù)中丟失的包，Reno和NewReno在一個RTT內(nèi)也至多只能重傳一個丟棄的包。當(dāng)然，Tahoe并不局限于此。然而這也說明缺乏SACK算法時,源端只能選擇兩種丟失數(shù)據(jù)的恢復(fù)策略：每一個RTT時間內(nèi)至多重傳一個丟棄的包，或者重傳所有包，其中也包括可能已經(jīng)正確發(fā)送的包。Reno和NewReno使用第一種策略，而Tahoe使用第二種。SACK使用“管道”(pipe)變量表示在發(fā)送路徑上損失的數(shù)據(jù)包的數(shù)量。用tcp remtthresh判斷擁塞是否發(fā)生。由于RTT值與網(wǎng)絡(luò)運行情況有密切關(guān)系，所以近幾年又出現(xiàn)了利用RTT控制擁塞的Vegas[6][7]算法。Vegas就是通過觀察以前的TCP連接中RTT值改變情況來控制擁塞窗口cwnd，如果發(fā)現(xiàn)RTT變大，Vegas就認為網(wǎng)絡(luò)發(fā)生擁塞，并開始減小cwnd。另一方面，如果RTT變小，Vegas就解除擁塞，再次增加cwnd。這樣，cwnd在理想情況下就會穩(wěn)定在一個合適的值上。這樣做的最大好處在于擁塞機制的觸發(fā)只與RTT的改變有關(guān)。而與包的具體傳輸時延無關(guān)。在擁塞避免階段，cwnd值由以下公式?jīng)Q定： (2)其中，rtt是觀察到的回路響應(yīng)時間，base_rtt是所觀察到所有rtt的最小值。α和β是兩個常數(shù)。式(2)表明如果所有數(shù)據(jù)包的RTT穩(wěn)定不變，擁塞窗口cwnd將不變。有研究通過仿真分析了Vegas實際的運行效果，由于它沒有采用包丟失來判斷網(wǎng)絡(luò)可用帶寬，而改以RTT的改變來判斷，所以能較好地預(yù)測網(wǎng)絡(luò)帶寬使用情況，并且對小緩存(smallbuffer)的適應(yīng)性較強，其公平性、效率都較好。但Vegas算法離在Internet上普遍采用還有距離。這倒不是算法本身問題，而是由于使用Vegas和未使用Vegas算法在競爭帶寬方面不公平所致。1．3 慢啟動算法評估1．3．1 面臨的困難和問題擁塞控制算法的困難[8]體現(xiàn)在以下幾方面:(1) ,必須使用不完整的信息完成控制,并使各節(jié)點協(xié)調(diào)工作,還必須考慮某些節(jié)點工作不正常的情況.(2) 中各處的網(wǎng)絡(luò)性能有很大的差異,由于Internet 對報文的正確傳輸不提供保證,算法必須處理報文丟失、亂序到達等情況.(3) ,包括算法的公平性、效率、,在算法設(shè)計時需要進行權(quán)衡.(4) ,(特別是網(wǎng)關(guān)),在網(wǎng)關(guān)上只進行少量的操作,這符合 Internet 的基本設(shè)計思想.人們可以把連接按由建立到終止所經(jīng)歷時間的長短分為長生存期和短生存期連接。有研究表明，當(dāng)前互聯(lián)網(wǎng)上數(shù)據(jù)傳輸大多數(shù)為短生存期連接（如Web頁面點擊），長生存期連接（如ftp下載）占少數(shù)。但是長生存期的連接卻傳送了大部分的數(shù)據(jù)量，而短生存期連接的特點是其傳輸過程往往在慢啟動階段終止。在互聯(lián)網(wǎng)應(yīng)用中，短生存期連接不但對帶寬而且對延遲都比較敏感，這是由互聯(lián)網(wǎng)用戶的要求所決定的。于是可以說，慢啟動機制的性能決定了短生存期連接的傳輸時間和效率。而對于長生存期連接，慢啟動機制只作用于連接建立階段和分組傳輸超時而引起的重傳階段。當(dāng)網(wǎng)絡(luò)發(fā)生擁塞狀況時，慢啟動機制才對長生存期連接的性能有一定的影響，因為當(dāng)前互聯(lián)網(wǎng)的應(yīng)用已經(jīng)不再是Telent、FTP、Gopher等為主要服務(wù)，而是以Web服務(wù)、視頻點播、實時信息發(fā)送等新興服務(wù)為主要類型，其中尤其以Web瀏覽服務(wù)為首要的服務(wù)。而這些服務(wù)主要屬于短生存期的連接。因此，盡管慢啟動階段在整個TCP擁塞控制階段所占比重比較小，所經(jīng)歷的時間很短，但是改善和提高慢啟動的性能仍具有重要意義。1．3．2 算法缺陷分析為了有效提高短生存期連接的傳送效率以及改善長生存期連接的啟動過程和丟包重啟過程的傳輸效率，研究者提出了系列改進方法。其中，M. Allman等設(shè)計一個更大的初始窗口，減少慢啟動經(jīng)歷的時間且大大提高了短生存期連接的慢啟動開始階段的效率[9]；J. Hoe采用基于接收端方法的估測門限值ssthresh替代初始設(shè)定門限閾值（ssthinit），以確保擁塞窗口增長至一合適的值[10]； TCP Vegas采用了一定程度限制慢啟動窗口的指數(shù)增長，即每兩個往返時間間隔（RTT）把擁塞窗口增大一倍[6]。 以上方法從不同的方面對TCP慢啟動進行了優(yōu)化，但均存在局限性， J. Hoe的方法很難在所有互聯(lián)網(wǎng)中接收端配置該算法，源端也無法利用測量的帶寬信息；TCP Vegas協(xié)議雖然限制了窗口的指數(shù)增長，但仍無法避免一個窗口中多個分組丟棄，并且在一定程度上降低了網(wǎng)絡(luò)的傳輸性能。1．3．3 基于網(wǎng)絡(luò)測量的方向網(wǎng)絡(luò)擁塞控制中一個關(guān)鍵問題是網(wǎng)絡(luò)中已存在和待加入的用戶數(shù)目是動態(tài)變化的，于是網(wǎng)絡(luò)帶寬資源的使用和需求就具有相當(dāng)大的不確定性，從而導(dǎo)致網(wǎng)絡(luò)帶寬的供需矛盾，如果能采取一定的措施實時地和動態(tài)地對網(wǎng)絡(luò)的可用資源得出估計和推測，那么網(wǎng)絡(luò)管理就可以依靠該數(shù)據(jù)來保證資源的合理分配，結(jié)果將利于網(wǎng)絡(luò)整體性能的提高，避免擁塞的發(fā)生和緩解擁塞的程度。 TCP Vegas通過計算擁塞窗口與實際測量的的比值，計算出實際傳送帶寬，與期望的傳送帶寬比較，來調(diào)整發(fā)送端的傳送帶寬，并通過兩個門限參數(shù)，使傳送帶寬收斂于網(wǎng)絡(luò)可用帶寬，測量表達式，為擁塞窗口的大小，為分組往返時間，通過計算上一個分組傳送的速率，作為計算當(dāng)前大小和慢啟動門限值的依據(jù)。很顯然，TCP Vegas的測量方法比較粗糙，在某種意義上來說它只是用來判斷源端發(fā)送速率改變的趨勢。只有深入研究網(wǎng)絡(luò)測量的相關(guān)技術(shù)，才能為擁塞控制提供更好的發(fā)展方向?；诰W(wǎng)絡(luò)測量的TCP協(xié)議改進 第二章網(wǎng)絡(luò)測量方法與研究第二章 網(wǎng)絡(luò)測量方法與研究2．1 網(wǎng)絡(luò)測量方法2．1．1 測量方法對比網(wǎng)絡(luò)測量方法[11]主要分為兩種：被動測量和主動測量。 被動測量和主動測量的區(qū)別在于，前者是被動地在網(wǎng)絡(luò)上接收流經(jīng)的數(shù)據(jù)包，而不會對網(wǎng)絡(luò)造成任何的負載；后者則是主動地向?qū)Ψ桨l(fā)出測試數(shù)據(jù)包，根據(jù)數(shù)據(jù)包在網(wǎng)絡(luò)上的傳輸情況來判斷網(wǎng)絡(luò)的性能。被動測量提供了單獨連接或者節(jié)點的性能描述，而主動測量則是針對位于一條路徑上的幾個連接和節(jié)點的性能。 被動測量組件包括了報文sniffer工具、邊緣路由器所生成的流級別的流量統(tǒng)計表，以及另外一臺用于查詢路由信息的空閑的頂級路由器。 主動測量組件則包括了由那些被置于主路由器中心的測量機器組成的網(wǎng)絡(luò)。這些機器交換測試流量，并收集全天的丟包率、延遲和連通性統(tǒng)計。然后將這些測量數(shù)據(jù)存入一個高性能數(shù)據(jù)倉庫。這些數(shù)據(jù)可以被用于流量工程、性能調(diào)試、網(wǎng)絡(luò)操作和以性能為目的所進行的測試。 2．1．2 主動測量方法主動測量數(shù)據(jù)分析技術(shù)是由AMP（Active Measurement Project）組織提出的數(shù)據(jù)分析方法，其目標(biāo)是對主動測量數(shù)據(jù)提供基本的了解和分析，并利用這些數(shù)據(jù)對網(wǎng)絡(luò)的連通性有更好的理解。 主動測量是基于RTT測量，而不是對單程延遲的測量。因為RTT測量更易于實現(xiàn)，而且不會依賴外部設(shè)備去同步兩臺監(jiān)視器的時間。另外，有的測量方法是使用全球定位系統(tǒng)（GPS Global Position System）接收器來同步主機的時間。但是這些系統(tǒng)過于昂貴而且難于安裝，并且獲得的額外信息也很有限，因此并不普及。 具體來說， RTT測量是通過類似Ping的程序，每隔一定時間進行一次。該程序?qū)γ颗_主機發(fā)送ICMP響應(yīng)包，然后等待ICMP的回應(yīng)包，記錄每個站點的測量延遲。發(fā)現(xiàn)或者診斷一個站點故障的最好方法之一就是，查看RTT圖標(biāo)的起伏狀況。這些起伏表明了路由或者配置上的變化所引起兩個站點間RTT的改變情況。 另外一點，就是要查看丟包率。如果一個站點的丟包率過高，那么它可能出現(xiàn)硬件損壞，這種分析是非?；镜摹Ｈ绻獙σ粋€站點的性能有進一步理解，就要通過比較它同其他站點的連通性來獲得。 2．2帶寬測量的研究2．2．1 算法基本原理端到端的數(shù)據(jù)傳輸可以看作源端N0發(fā)送數(shù)據(jù)通過系列中間節(jié)點Ni和到達目的