【正文】 率的降低的時候。在這個期間，由LBL到UC Berkeley的吞吐量從32Kbps跌到了40bps，而這兩個地方的空間距離相隔了400英碼，其站點則隔了兩個IMP的轉(zhuǎn)發(fā)距離。 網(wǎng)絡(luò)負(fù)載與吞吐量及響應(yīng)時間的關(guān)系對于擁塞現(xiàn)象，我們[2]。當(dāng)負(fù)載達(dá)到網(wǎng)絡(luò)容量時，吞吐量呈現(xiàn)出緩慢增長，而響應(yīng)時間急劇增加，這一點稱為Knee。1．1．2 控制階段的劃分TCP擁塞控制過程可分為四個階段[3]：(1)慢啟動階段：舊的TCP在啟動一個連接時會向網(wǎng)絡(luò)中發(fā)送許多數(shù)據(jù)包，由于一些路由器必須對數(shù)據(jù)包排隊，所以這樣就有可能耗盡存儲空間，從而導(dǎo)致TCP連接的吞吐量(throughput)急劇下降。當(dāng)建立新的TCP連接時，擁塞窗口(cwnd)初始化為一個數(shù)據(jù)包大小(一個數(shù)據(jù)包缺省為536或512bytes)。很顯然，cwnd的增長將隨RTT呈指數(shù)級(exponential)增長：1個、2個、4個、8個…。(2)擁塞避免階段：當(dāng)發(fā)現(xiàn)超時或收到3個相同ACK確認(rèn)幀時，網(wǎng)絡(luò)即發(fā)生擁塞(TCP這一假定是基于由傳輸引起的數(shù)據(jù)包損壞和丟失的概率很小(小于1%)[3])。慢啟動閾值(ssthresh)被設(shè)置為當(dāng)前cwnd的一半，如果是超時，cwnd還要被置1。(3)快速重傳和恢復(fù)階段：當(dāng)數(shù)據(jù)包超時時，cwnd要被置為1，重新進(jìn)入慢啟動，這會導(dǎo)致過大地減小發(fā)送窗口尺寸，降低TCP連接的吞吐量。　　 慢啟動和擁塞避免（不含快速重傳和恢復(fù)） 快速重傳與恢復(fù)由以上分析可以看出：TCP使用的是一種和式增加積式減少(Additive Increase Multiplicative Decrease,AIMD)的基于窗口的端到端擁塞控制機(jī)制。如果有一個數(shù)據(jù)包丟失，發(fā)送窗口則要減半；否則就簡單地增加一個數(shù)據(jù)包的發(fā)送量。1．2 國外相關(guān)工作1．2．1 控制機(jī)制的發(fā)展：Tahoe到Reno1988年Van Jacobson在文獻(xiàn)[1]指出了TCP在控制網(wǎng)絡(luò)擁塞方面的不足，并提出了“慢啟動”(slow start)算法、“擁塞避免”(congestion avoidance)算法。事實上，在TCP Reno之前還有TCP Tahoe，兩者主要區(qū)別在于后者只有擁塞控制的前三部分，沒有快速恢復(fù)(fast retransmit)，所以可以認(rèn)為TCP Reno是TCP Tahoe的改進(jìn)版[4]。首先，源端在檢測到擁塞后，要重傳自數(shù)據(jù)包丟失到檢測到丟失時發(fā)送的全部數(shù)據(jù)包(即Gobackn算法)，而這中間有些數(shù)據(jù)包是正確傳到接收端，不必重傳的。而準(zhǔn)確估計RTO和RTT值并不是一件容易的事。如下式[5]： (1)，其中為加權(quán)因子且。估計的RTT值在最近采樣的短時間內(nèi)幾乎不發(fā)生變化(例如一個經(jīng)歷長時延的數(shù)據(jù)包的RTT)。理論上，RTT的測量比較簡單。但由于TCP使用的是用一個ACK確認(rèn)所有已收到數(shù)據(jù)的“累積”確認(rèn)方式，所以RTT的估計在實際中往往很復(fù)雜。SACK算法是在Reno基礎(chǔ)上進(jìn)行擴(kuò)展，對數(shù)據(jù)包進(jìn)行有選擇地確認(rèn)和重傳。NewReno沒有選用SACK方法，而是盡力避免了Reno在快速恢復(fù)階段的許多重傳超時，利用一個ACK確認(rèn)部分發(fā)送窗口，立即重傳余下的數(shù)據(jù)包。綜合來看，即使源端不通過等待超時來恢復(fù)一個窗口數(shù)據(jù)中丟失的包，Reno和NewReno在一個RTT內(nèi)也至多只能重傳一個丟棄的包。然而這也說明缺乏SACK算法時,源端只能選擇兩種丟失數(shù)據(jù)的恢復(fù)策略：每一個RTT時間內(nèi)至多重傳一個丟棄的包，或者重傳所有包，其中也包括可能已經(jīng)正確發(fā)送的包。SACK使用“管道”(pipe)變量表示在發(fā)送路徑上損失的數(shù)據(jù)包的數(shù)量。由于RTT值與網(wǎng)絡(luò)運行情況有密切關(guān)系，所以近幾年又出現(xiàn)了利用RTT控制擁塞的Vegas[6][7]算法。另一方面，如果RTT變小，Vegas就解除擁塞，再次增加cwnd。這樣做的最大好處在于擁塞機(jī)制的觸發(fā)只與RTT的改變有關(guān)。在擁塞避免階段，cwnd值由以下公式?jīng)Q定： (2)其中，rtt是觀察到的回路響應(yīng)時間，base_rtt是所觀察到所有rtt的最小值。式(2)表明如果所有數(shù)據(jù)包的RTT穩(wěn)定不變，擁塞窗口cwnd將不變。但Vegas算法離在Internet上普遍采用還有距離。1．3 慢啟動算法評估1．3．1 面臨的困難和問題擁塞控制算法的困難[8]體現(xiàn)在以下幾方面:(1) ,必須使用不完整的信息完成控制,并使各節(jié)點協(xié)調(diào)工作,還必須考慮某些節(jié)點工作不正常的情況.(2) 中各處的網(wǎng)絡(luò)性能有很大的差異,由于Internet 對報文的正確傳輸不提供保證,算法必須處理報文丟失、亂序到達(dá)等情況.(3) ,包括算法的公平性、效率、,在算法設(shè)計時需要進(jìn)行權(quán)衡.(4) ,(特別是網(wǎng)關(guān)),在網(wǎng)關(guān)上只進(jìn)行少量的操作,這符合 Internet 的基本設(shè)計思想.人們可以把連接按由建立到終止所經(jīng)歷時間的長短分為長生存期和短生存期連接。但是長生存期的連接卻傳送了大部分的數(shù)據(jù)量，而短生存期連接的特點是其傳輸過程往往在慢啟動階段終止。于是可以說，慢啟動機(jī)制的性能決定了短生存期連接的傳輸時間和效率。當(dāng)網(wǎng)絡(luò)發(fā)生擁塞狀況時，慢啟動機(jī)制才對長生存期連接的性能有一定的影響，因為當(dāng)前互聯(lián)網(wǎng)的應(yīng)用已經(jīng)不再是Telent、FTP、Gopher等為主要服務(wù)，而是以Web服務(wù)、視頻點播、實時信息發(fā)送等新興服務(wù)為主要類型，其中尤其以Web瀏覽服務(wù)為首要的服務(wù)。因此，盡管慢啟動階段在整個TCP擁塞控制階段所占比重比較小，所經(jīng)歷的時間很短，但是改善和提高慢啟動的性能仍具有重要意義。其中，M. Allman等設(shè)計一個更大的初始窗口，減少慢啟動經(jīng)歷的時間且大大提高了短生存期連接的慢啟動開始階段的效率[9]；J. Hoe采用基于接收端方法的估測門限值ssthresh替代初始設(shè)定門限閾值（ssthinit），以確保擁塞窗口增長至一合適的值[10]； TCP Vegas采用了一定程度限制慢啟動窗口的指數(shù)增長，即每兩個往返時間間隔（RTT）把擁塞窗口增大一倍[6]。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的測量方法比較粗糙，在某種意義上來說它只是用來判斷源端發(fā)送速率改變的趨勢。基于網(wǎng)絡(luò)測量的TCP協(xié)議改進(jìn) 第二章網(wǎng)絡(luò)測量方法與研究第二章 網(wǎng)絡(luò)測量方法與研究2．1 網(wǎng)絡(luò)測量方法2．1．1 測量方法對比網(wǎng)絡(luò)測量方法[11]主要分為兩種：被動測量和主動測量。被動測量提供了單獨連接或者節(jié)點的性能描述，而主動測量則是針對位于一條路徑上的幾個連接和節(jié)點的性能。 主動測量組件則包括了由那些被置于主路由器中心的測量機(jī)器組成的網(wǎng)絡(luò)。然后將這些測量數(shù)據(jù)存入一個高性能數(shù)據(jù)倉庫。 2．1．2 主動測量方法主動測量數(shù)據(jù)分析技術(shù)是由AMP（Active Measurement Project）組織提出的數(shù)據(jù)分析方法，其目標(biāo)是對主動測量數(shù)據(jù)提供基本的了解和分析，并利用這些數(shù)據(jù)對網(wǎng)絡(luò)的連通性有更好的理解。因為RTT測量更易于實現(xiàn)，而且不會依賴外部設(shè)備去同步兩臺監(jiān)視器的時間。但是這些系統(tǒng)過于昂貴而且難于安裝，并且獲得的額外信息也很有限，因此并不普及。該程序?qū)γ颗_主機(jī)發(fā)送ICMP響應(yīng)包，然后等待ICMP的回應(yīng)包，記錄每個站點的測量延遲。這些起伏表明了路由或者配置上的變化所引起兩個站點間RTT的改變情況。如果一個站點的丟包率過高，那么它可能出現(xiàn)硬件損壞，這種分析是非?；镜?。 2．2帶寬測量的研究2．2．1 算法基本原理端到端的數(shù)據(jù)傳輸可以看作源端N0發(fā)送數(shù)據(jù)通過系列中間節(jié)點Ni和到達(dá)目的節(jié)點Nn，其中N0為源端點，Nn為目標(biāo)結(jié)點，路徑R由n條鏈路連接而成分別為li（1～n），帶寬分別為Bi，其中瓶頸鏈路lmin的帶寬為Bmin，分組Pkt的大小為P，假設(shè)數(shù)據(jù)傳輸過程中，路徑R沒有任何其他干擾流量，同時忽略目標(biāo)節(jié)點返回應(yīng)答分組的延遲對網(wǎng)絡(luò)帶寬的影響，N0發(fā)送分組的時間間隔為φ。 網(wǎng)絡(luò)模型 瓶頸鏈路與端到端分組間隔情況源節(jié)點N0發(fā)送分組k經(jīng)由各中間結(jié)點及鏈路到達(dá)目標(biāo)結(jié)點Nn，分組到達(dá)節(jié)點Ni的經(jīng)歷時間為前i1個結(jié)點上的排隊時間（源節(jié)點N0沒有排隊延遲）、在前i條鏈路上的傳輸時間以及前i條鏈路的時延之和，即， (1)根據(jù)前述約定，由于沒有其他流量干擾，分組在所有鏈路的起始端結(jié)點的排隊時間為0，即，如果在第k＋1個數(shù)據(jù)包到達(dá)第i個結(jié)點時，第k個分組已經(jīng)離開第i個結(jié)點，那么，第k＋1個分組在結(jié)點i的排隊時間為0，否則為二者的時間差，即， (2)分組k，k＋1到達(dá)Nn的時間間隔為Δ= (3)第k個分組沒有完全離開瓶頸鏈路，第k＋1個分組就到達(dá)瓶頸鏈路，兩分組到達(dá)目標(biāo)節(jié)點的時間間隔將由兩個分組離開瓶頸鏈路的時間差決定，Δ=P/Bmin，有端到端的帶寬，即為瓶頸鏈路帶寬，Be2e=Bmin=P/()=P/Δ (4)2．2．2 主要算法對比現(xiàn)有的帶寬測量算法[12]主要有兩種，其他的算法和應(yīng)用工具大都是在它們基礎(chǔ)之上的改進(jìn)。1數(shù)據(jù)包對基本算法該算法是基于這樣的簡單事實：若兩個數(shù)據(jù)包排隊在瓶頸鏈接處，則當(dāng)它們離開節(jié)點時，它們將有t秒的時間間隔。為保證第二個包的傳輸延遲不小于第一個包，并且包對間的距離不至于連續(xù)增加，兩個包的大小應(yīng)相等。2Pathchar算法該算法通過分析數(shù)據(jù)包的大小和其RTT（往返時延）的線性關(guān)系來估計每一跳的帶寬。令是一個B 比特數(shù)據(jù)包的RTT，是鏈路帶寬。則可得 （6） （其中c是常數(shù)，它是傳輸延遲、處理延遲和排隊延遲的總和）。這樣可得 （7）為獲得，發(fā)送不同大小的數(shù)據(jù)包到節(jié)點i，為函數(shù)(B)建立采樣點，再通過線性回歸法求得斜率， 同法可求。在一跳轉(zhuǎn)發(fā)中，數(shù)據(jù)包通過輸入鏈路到達(dá)路由器，路由器將該數(shù)據(jù)包放入緩存器的隊列中，等待其他先到或者優(yōu)先級更高的數(shù)據(jù)包被路由器轉(zhuǎn)發(fā)。由以上的數(shù)據(jù)包轉(zhuǎn)發(fā)過程描述[12]，我們可以將數(shù)據(jù)包轉(zhuǎn)發(fā)的延遲分為排隊延遲（Queuing Time）,傳輸延遲（Transfers Delay）以及傳播延遲（Transmission Latency）幾個部分。路由器查找路由表以及數(shù)據(jù)包在路由器中其他的處理時間對特定的設(shè)備相對固定。顯然數(shù)據(jù)包k在第i跳的延遲為 (8)則通路P總延遲為 （9）對于特定的網(wǎng)絡(luò)節(jié)點和是固定的，因背景流量的存在和流量的突發(fā)特性使得在緩存中排隊的數(shù)據(jù)包數(shù)目不確定，即是可變的，因此在測量端到端的延遲時，測量值有較大的變化。在IP網(wǎng)絡(luò)中，鏈路帶寬指在沒有任何負(fù)載的情況下，鏈路可以提供給流的最大IP層吞吐量。鏈路帶寬經(jīng)常稱為鏈路容量（link capacity）。鏈路帶寬測量主要測量路徑中的各鏈路的容量和利用率。該方案主要內(nèi)容是源端主機(jī)通過測量返回ACK的速率來對鏈路上可用帶寬進(jìn)行估計，即其主要是基于端到端的速率測量（RE Rate Estimate）。首先決定樣本帶寬，它是由ACK間隔時間和發(fā)送字節(jié)數(shù)計算得到，然后通過低通濾波器的處理，對累積誤差和傳輸誤差進(jìn)行消除，就得到最終所需要的估計帶寬。基于網(wǎng)絡(luò)測量的TCP協(xié)議改進(jìn) 第三章基于帶寬測量的TCP分段逼近算法第三章 基于帶寬測量的TCP分段逼近算法3．1問題分析3．1．1 慢啟動階段TCP慢啟動機(jī)制在探測網(wǎng)絡(luò)帶寬方面是按照窗口大小從1開始指數(shù)增長的規(guī)律，這導(dǎo)致了兩個主要問題：第一，慢啟動的窗口大小由1個報文段進(jìn)行遞增。同時導(dǎo)致短小數(shù)據(jù)連接對可用帶寬的低利用率，使窗口大小遠(yuǎn)小于路徑帶寬延遲乘積。第二，源端無法得知網(wǎng)絡(luò)可用帶寬的容量，而在開始階段使用系統(tǒng)提供的默認(rèn)參數(shù)。結(jié)果會出現(xiàn)一個發(fā)送窗口中多個報文段丟棄，而TCP源端喪失了自時鐘特性。TCP性能大幅下降，再次通過慢啟動實現(xiàn)自時鐘。以前的設(shè)置都是根據(jù)大范圍的實際調(diào)查和一定的理論分析對這些參數(shù)進(jìn)行初始化。雖然其具有一定的合理性，當(dāng)按照網(wǎng)絡(luò)的發(fā)展趨勢，其靈活性總會受到這樣的或那樣的挑戰(zhàn)。然而由于網(wǎng)絡(luò)中主機(jī)數(shù)目的不確定性決定了傳輸數(shù)據(jù)參數(shù)的動態(tài)變化。所以，滯后性始終是無法完全解決的一個缺陷。但是，在一定程度上可以說，低效率問題已經(jīng)得到了較好的解決?？梢园l(fā)現(xiàn)的規(guī)律是，給定i，則前i1個數(shù)值之和與第i個數(shù)值相差1。而由慢啟動階段進(jìn)入擁塞避免階段的分界條件是cwnd＝ssthresh。瀏覽整個增加幅度差隊列，此時差值最大。目前標(biāo)準(zhǔn)的慢啟動擁塞窗口的速度變化如圖1中曲線a所示，窗口增加幅度的趨勢是越來越快。然而當(dāng)發(fā)送速率接近網(wǎng)絡(luò)帶寬時，這樣的變化規(guī)律會導(dǎo)致以上的問題。于是，在一定程度上說，過渡階段高丟包率問題可以得到較好地解決。 這里必須重點強調(diào)”端到端”的原則。不管中間設(shè)備（路由器）可能會發(fā)生什么問題，這個原則可以保證數(shù)據(jù)可以在任何種類的異構(gòu)網(wǎng)絡(luò)中傳輸。因此，為了判斷網(wǎng)絡(luò)的可用帶寬，源端必須通過不斷增大發(fā)送速率來探測該帶寬大小，直到其收到被動反饋，比如說超時或重復(fù)確認(rèn)，而這些都是表示網(wǎng)絡(luò)容量達(dá)到耗盡程度的信號。主機(jī)采用監(jiān)測TCP的ACK報文段的方式來對帶寬進(jìn)行估計，也就是，源端通過測量和計算返回ACK的速率來進(jìn)行該TCP連接上可用帶寬的端到端估計。3．2．2 擁塞信號的處理 在擁塞階段（即源端接收到三個重復(fù)的ACKs或超時），源端利用測量得到的帶寬來把擁塞窗口和慢啟動閾值設(shè)為恰當(dāng)?shù)闹担瑥亩鴨右粋€稱之為更快速恢復(fù)的過程。若該傳輸過程沒有發(fā)生丟包事件，那么把已傳輸數(shù)據(jù)的計數(shù)簡單地除以時間就可以得到當(dāng)前源端所使用帶寬的比較準(zhǔn)確的估計。 然而，源端無法分辨是哪一個報文段觸發(fā)了DUPACK傳輸，因此，其不能按報文段的數(shù)量來更新數(shù)據(jù)包計數(shù)。按照這個