主動隊列對web性能影響的研究論文

主動隊列對WEB性能影響的研究摘要我們首先呈現(xiàn)一個關(guān)于主動隊列管理技術(shù)（AQM）和顯式堵塞通知在網(wǎng)絡(luò)中經(jīng)歷大量用戶瀏覽網(wǎng)頁后響應(yīng)時間的分布情況的經(jīng)驗研究。三種著名的方案可以考慮：比例積分(PI)控制器,隨機指數(shù)標(biāo)記(REM)控制器和自適應(yīng)隨機早期檢測(ARED)。研究了在有顯式堵塞通知和無顯式堵塞通知下這些AQM方案的影響。我們的主要衡量性能指標(biāo)是端到端的HTTP請求-響應(yīng)交換響應(yīng)時間。對于這種方法,我們的主要結(jié)果是：如果不支持顯式堵塞通知,ARED操作在字節(jié)模式是表現(xiàn)最好的AQM方案,提供比尾部丟包FIFO排隊在提供的負載超過鏈路容量的90%時有更好的響應(yīng)時間性能。然而,ARED操作在包模式(有或沒有顯式堵塞通知)是表現(xiàn)最差的方案。甚至比尾部丟包FIFO排隊還要差。顯式堵塞通知支持有利于PI和REM。在顯式堵塞通知下,PI和REM是所有方案中表現(xiàn)最佳的方案,顯式堵塞通知為在字節(jié)模式下的ARED操作提供重要的響應(yīng)時間改進。對于REM,顯式堵塞通知帶來的好處是戲劇性的。沒有顯式堵塞通知,REM比尾部丟包的FIFO排隊在所有負載下的響應(yīng)時間性能都還要差。AQM對于響應(yīng)時間是否有重大的改善很大程度上依賴于流經(jīng)歷的往返時延的分布情況，當(dāng)流的RTT增加時引起AQM和顯式堵塞通知對于響應(yīng)時間性能的影響降低。我們得出結(jié)論,AQM可以提高網(wǎng)頁類應(yīng)用程序和網(wǎng)絡(luò)性能的工作負載。特別是,在AQM和顯式堵塞通知下,提供的鏈接可以在接近飽和水平?jīng)]有明顯退化上操作達到用戶預(yù)期的性能。關(guān)鍵字：網(wǎng)絡(luò)擁塞控制；AQM算法；標(biāo)記/丟失概率；PI控制器

第一章引言計算機科學(xué)的迅速發(fā)展是20世紀科學(xué)發(fā)展史上最偉大的事件之一，標(biāo)志著人類社會進入了信息時代。隨著現(xiàn)代高科技技術(shù)的發(fā)展，計算機技術(shù)和通信技術(shù)的結(jié)合形成了計算機通信系統(tǒng)。計算機網(wǎng)絡(luò)就是把分布在不同地點的具有獨立功能的多臺計算機系統(tǒng)通過通信線路和設(shè)備互相連接在一起，按照網(wǎng)絡(luò)協(xié)議進行信息通信，實現(xiàn)資源共享的計算機通信系統(tǒng)。20世紀80年代出現(xiàn)的Internet是現(xiàn)在全球最大的計算機網(wǎng)絡(luò)。Internet在過去的幾十年經(jīng)歷了爆炸式發(fā)展。1980年ARPA網(wǎng)（Internet的前身）只包含200臺計算機，從1986年接入6000臺計算機開始，5年后數(shù)量就達到了60萬，一直到上一世紀末，全球Internet用戶達到2億之多?，F(xiàn)在Internet網(wǎng)絡(luò)的容量與規(guī)模仍以驚人的速度繼續(xù)不斷的向前發(fā)展，人類日常的生活與工作也越來越覺得離不開Internet。Internet的出現(xiàn)使得傳統(tǒng)的信息獲取、傳送、存儲和處理方式發(fā)生了根本的變化，人們的生活與工作方式也隨之發(fā)生了很大的變化。Internet網(wǎng)絡(luò)的強大功能使得計算機網(wǎng)絡(luò)在社會各個領(lǐng)域已有廣泛的應(yīng)用，對全世界科學(xué)、經(jīng)濟和社會產(chǎn)生了重大影響。Internet網(wǎng)絡(luò)使終端與計算機之間、計算機與計算機之間能快速地相互傳輸數(shù)據(jù)、程序和信息，并可對這些數(shù)據(jù)信息進行分散、分級、集中管理和處理，從而使用戶解除了地理位置的束縛，提高了數(shù)據(jù)處理的速度。如自動訂票系統(tǒng)、銀行財經(jīng)系統(tǒng)、政府的計劃統(tǒng)計系統(tǒng)、氣象數(shù)據(jù)收集系統(tǒng)等。Internet網(wǎng)絡(luò)可以讓用戶充分利用計算機系統(tǒng)共享網(wǎng)絡(luò)上的軟件資源和硬件資源。如大容量磁盤存儲器、異常昂貴的外部設(shè)備、數(shù)據(jù)庫、應(yīng)用軟件等，使得網(wǎng)絡(luò)中分散的資源互通有無，分工協(xié)作，資源使用率大為提高，處理能力大為增強，處理的平均費用大為下降。Internet網(wǎng)絡(luò)上設(shè)備分散，數(shù)據(jù)安全可靠。當(dāng)網(wǎng)絡(luò)上某處計算機發(fā)生故障時，可由別處的計算機代為處理，也可把數(shù)據(jù)備份到其他計算機上，有網(wǎng)絡(luò)作為公用后備，投資少，效益高。當(dāng)某處計算機負擔(dān)過重時，可將新的作業(yè)傳送到網(wǎng)絡(luò)中另一個較空閑的計算機上去處理，從而減少了用戶等待時間，均衡了網(wǎng)絡(luò)負載。多媒體網(wǎng)絡(luò)的應(yīng)用，使聲、文、圖像多種信息的收集、傳送、存儲和處理融為一體，給計算機網(wǎng)絡(luò)用戶提供了很大的方便。如用戶可以在網(wǎng)絡(luò)上收聽廣播、收看電視、查詢信息等。隨著網(wǎng)絡(luò)應(yīng)用范圍不斷擴大，用戶數(shù)量的爆炸式增長，Internet遇到了網(wǎng)絡(luò)擁塞的問題。所謂擁塞（Congestion）是指在某一時刻，當(dāng)網(wǎng)絡(luò)中某一資源的到達量超過了該資源在相關(guān)網(wǎng)絡(luò)節(jié)點的承載量時，稱該節(jié)點在該時刻發(fā)生了擁塞。擁塞導(dǎo)致的直接后果是分組丟失率提高，端到端延時加大，網(wǎng)絡(luò)性能降低，嚴重時會產(chǎn)生擁塞崩潰，幾乎沒有數(shù)據(jù)包可以送達目的地。擁塞崩潰的出現(xiàn)可以追溯到Internet的早期發(fā)展中。1984年Nagle報告了由于TCP連接中不必要的重傳所誘發(fā)的擁塞崩潰，1986～1987年間這種現(xiàn)象在美國曾經(jīng)多次發(fā)生，嚴重時一度使美國LBL到UCBerkeley之間的數(shù)據(jù)吞吐量從32Kb/s跌落到了40b/s。擁塞崩潰在20世紀80年代中期最先提出的時候，主要是由于TCP連接重傳那些正在傳送或己經(jīng)被接收方接收了的數(shù)據(jù)包所引起。我們將這種由于不必要的重傳數(shù)據(jù)包而引起的擁塞崩潰稱為典型擁塞崩潰。典型擁塞崩潰的問題己經(jīng)通過定時器和TCP的改進應(yīng)用而基本得到解決。當(dāng)今的Internet中的擁塞控制機制代表著一種最大利用的人工反饋系統(tǒng)，隨著Internet在規(guī)模、應(yīng)用種類、應(yīng)用領(lǐng)域的不斷擴大，擁塞控制在多網(wǎng)絡(luò)融合方面起著日益重要的作用。人們一致認為這種成為社會基本資源的網(wǎng)絡(luò)如何得到有效控制已經(jīng)變得日益緊迫了。鑒于網(wǎng)絡(luò)的規(guī)模和復(fù)雜性，傳統(tǒng)的擁塞控制開始是基于直接推斷、實驗證明的方法，直到本世紀初，國外研究人員開始嘗試使用分析模擬和反饋控制理論。最近幾年，人們把分析模型用于Internet的擁塞控制[6]。擁塞控制策略包括擁塞避免（Congestionavoidance）和擁塞控制（Congestioncontrol）兩種不同的機制。擁塞避免是“預(yù)防機制”，它的目標(biāo)是避免網(wǎng)絡(luò)進入擁塞狀態(tài)，使網(wǎng)絡(luò)運行在高吞吐量、低延遲的狀態(tài)。擁塞控制是“恢復(fù)機制”，作為擁塞避免失敗的補救措施。擁塞控制的研究目的不是完全避免擁塞，而是研究怎樣的擁塞程度更為合適。這是因為：TCP/IP網(wǎng)絡(luò)采用分組交換技術(shù)來提高網(wǎng)絡(luò)鏈路的利用率，經(jīng)常造成數(shù)據(jù)包在路由器的緩存中排隊待發(fā)；如果隊列緩存經(jīng)常為空，雖然傳輸延遲小，但此時網(wǎng)絡(luò)利用率低；反之，隊列緩存總被占用，傳輸延遲加大了，但網(wǎng)絡(luò)利用率較高。擁塞控制的目標(biāo)是實現(xiàn)網(wǎng)絡(luò)綜合指標(biāo)的最優(yōu)化。根據(jù)擁塞控制算法實現(xiàn)的位置可以分為兩大類：在傳輸層實現(xiàn)的源端擁塞控制，已被廣泛應(yīng)用的是TCP擁塞控制；在網(wǎng)絡(luò)層實現(xiàn)的通信子網(wǎng)擁塞控制，也稱為IP擁塞控制。當(dāng)網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)分組接近網(wǎng)絡(luò)的處理能力時，網(wǎng)絡(luò)中間節(jié)點（如交換機、路由器等）設(shè)備緩存（buffer）中等待服務(wù)的數(shù)據(jù)分組隊列（queue）會逐漸增大，在網(wǎng)絡(luò)中的分組由于往返時間的增大有可能導(dǎo)致發(fā)送端定時器超時，而發(fā)生數(shù)據(jù)重傳現(xiàn)象。如果隊列長度超出中間節(jié)點的緩存中隊列的容量，分組就會由于隊列溢出而被丟棄。網(wǎng)絡(luò)中發(fā)生分組丟失或者重傳現(xiàn)象，就標(biāo)志著發(fā)生了網(wǎng)絡(luò)擁塞。如果不采用及時的、適宜的方法去控制網(wǎng)絡(luò)擁塞，保證網(wǎng)絡(luò)穩(wěn)定運行，將導(dǎo)致網(wǎng)絡(luò)癱瘓。因此在網(wǎng)絡(luò)中為了避免出現(xiàn)網(wǎng)絡(luò)擁塞，最大限度提高網(wǎng)絡(luò)的利用率，最大可能地保證網(wǎng)絡(luò)的穩(wěn)定運行，保證網(wǎng)絡(luò)信息的可靠傳輸，采用有效的擁塞控制機制是非常重要的。擁塞會造成網(wǎng)絡(luò)吞吐量的急劇下降和響應(yīng)時間的增加。圖1.1中是網(wǎng)絡(luò)有擁塞控制算法和無擁塞控制算法時有效吞吐量對于網(wǎng)絡(luò)負載的變化曲線。由圖可知，如果不采用擁塞控制機制，當(dāng)網(wǎng)絡(luò)負載較大時會導(dǎo)致有效吞吐量的急劇下降，而有效的擁塞控制機制能使網(wǎng)絡(luò)在這種情況下仍然維持較高的有效吞吐量。在Internet中，擁塞控制算法根據(jù)其實現(xiàn)的位置可以分為源算法（sourcealgorithm）和鏈路算法（linkalgorithm），也可以分別稱之為端節(jié)點算法和中間節(jié)點算法，兩者協(xié)作完成網(wǎng)絡(luò)的擁塞控制。其中鏈路算法的研究主要集中在主動隊列管理（ActiveQueueManagement，AQM）。AQM的思想是：網(wǎng)絡(luò)中間節(jié)點在隊列溢出之前通過丟棄或標(biāo)記部分分組，以通知端系統(tǒng)網(wǎng)絡(luò)的擁塞狀況，端系統(tǒng)及時對可能發(fā)生或者已經(jīng)發(fā)生的擁塞進行響應(yīng)，避免即將發(fā)生的擁塞或者緩解已經(jīng)發(fā)生的擁塞。AQM算法使網(wǎng)絡(luò)中間節(jié)點主動的參與到擁塞控制之中，期望在保證較高吞吐量的基礎(chǔ)上，中間節(jié)點上的AQM機制有效地控制隊列長度，從而實現(xiàn)控制端到端的時延和時延抖動，保證網(wǎng)絡(luò)的服務(wù)質(zhì)量（QualityofService，QoS）。AQM是近年來擁塞控制領(lǐng)域的一個研究熱點，AQM機制可以減少數(shù)據(jù)分組的突發(fā)性丟棄，減小端到端延遲，并可以避免少數(shù)連接流占用大多數(shù)隊列資源現(xiàn)象的發(fā)生。AQM是當(dāng)前擁塞控制研究的一個熱點。但是已提出的AQM算法大多數(shù)是基于經(jīng)驗，啟發(fā)式的算法，沒有用系統(tǒng)理論的觀點進行分析和設(shè)計。近幾年系統(tǒng)控制理論被引入到擁塞控制的研究中，已經(jīng)有一些基于控制理論的AQM算法被提出，但大多此類算法都是基于傳統(tǒng)控制理論（包括經(jīng)典控制理論和現(xiàn)代控制理論）設(shè)計的。由于網(wǎng)絡(luò)的復(fù)雜性和時變特性，這些算法的實用性和有效性還存在一些問題，需要更進一步的研究。

第二章經(jīng)典AQM算法在使用AQM算法的網(wǎng)絡(luò)中間節(jié)點中，路由器根據(jù)自身擁塞狀況對分組進行轉(zhuǎn)發(fā)、丟棄/標(biāo)記。圖2.1是在路由器使用AQM控制機制的框圖。AQM機制根據(jù)緩沖區(qū)隊列長度或者其它測度檢測擁塞，計算丟棄/標(biāo)記數(shù)據(jù)分組的概率。中間節(jié)點通過對分組的丟棄或標(biāo)記，及時通知端系統(tǒng)網(wǎng)絡(luò)的擁塞狀況，發(fā)送端可以及時的調(diào)整自己的數(shù)據(jù)發(fā)送速率，盡量避免擁塞的產(chǎn)生。圖2.1在路由器中使用主動隊列管理當(dāng)前AQM算法的研究根據(jù)其研究方法和思想主要可以分為以下幾種：（1）基于經(jīng)驗的啟發(fā)式算法，如RED；（2）基于優(yōu)化理論的算法，如REM；（3）基于控制理論進行已有的算法穩(wěn)定性分析、參數(shù)整定或者設(shè)計新的AQM算法，如PI；2.1RED算法隨機早期檢測（RandomEarlyDetection，RED）由Floyd等提出的RED是目前已提出的最主要的AQM的算法。它在隊列溢出之前以一定概率丟失或標(biāo)記分組，及時通知端系統(tǒng)網(wǎng)絡(luò)的擁塞情況，以便發(fā)送端對發(fā)送速率做出調(diào)整，減小網(wǎng)絡(luò)發(fā)生擁塞的可能性。RED算法由兩部分組成，每當(dāng)有新的分組到達隊列時：（1）由瞬時隊列長度計算出平均隊列長度；（2）根據(jù)平均隊列長度計算丟棄概率，并以此概率丟棄剛到達隊列的分組。平均隊列長度avg和丟棄概率p的計算方法，分別見式（2.1）和（2.2）：（2.1）（2.2）其中：為計算avg的權(quán)值，q為瞬時隊列長度。式中:為最小閾值，為最大閾值，為最大概率。圖2.2所示為RED中丟棄概率與平均隊列長度之間的函數(shù)關(guān)系。RED使用平均隊列長度而不是瞬時隊列長度進行網(wǎng)絡(luò)擁塞程度的度量，其計算平均隊列長度的過程本質(zhì)上是一個截止頻率為,（其中δ為采樣間隔，在RED中即為分組到達的間隔時間）的低通濾波器，目的是為了平滑由于數(shù)據(jù)突發(fā)產(chǎn)生的瞬間的隊列變化。從控制理論的角度分析，計算丟棄概率p的部分是一個比例控制器。RED算法與Drop-Tail相比，可以有效的控制平均隊列長度，從而控制了端到端的延時，同時減少了分組的突發(fā)性丟棄，避免了TCP全局同步問題。此外由于RED算法的隨機丟棄機制，占用帶寬越高的流的分組越容易被丟棄，所以算法可以在無需維護每個流狀態(tài)的前提下提供一定程度的公平性，避免死鎖問題。實驗結(jié)果證明RED的性能優(yōu)于Drop-Tail。盡管RED已被廣泛應(yīng)用于網(wǎng)絡(luò)隊列管理中來提高網(wǎng)絡(luò)系統(tǒng)的性能，但是RED算法仍然存在以下問題：1）算法性能對網(wǎng)絡(luò)參數(shù)和狀態(tài)敏感；2）不能總是保證所有的流公平地分享帶寬；3）算法魯棒性不佳，導(dǎo)致路由器隊列長度大幅震蕩甚至溢出；4）使用RED算法的平均隊列長度會隨著活動流數(shù)量的增多而增加，即RED算法中網(wǎng)絡(luò)負載和隊列長度存在耦合。從控制理論的角度分析，RED算法中網(wǎng)絡(luò)負載和隊列長度的耦合的根本原因是算法中的比例控制器使系統(tǒng)存在靜差。此外，一方面RED算法使閉環(huán)系統(tǒng)的帶寬過低，從而導(dǎo)致系統(tǒng)對于干擾和負載變化的響應(yīng)速度很慢（低通濾波器是造成響應(yīng)過慢的一個主要因素）；另外一個方面，當(dāng)系統(tǒng)在負載較輕或較重時，穩(wěn)態(tài)的丟棄概率可能會小于或大于，這時算法工作在圖3.2所示曲線的非線性區(qū)域，導(dǎo)致系統(tǒng)難以穩(wěn)定，從而造成隊列大幅度振蕩。2.2ARED算法自適應(yīng)RED（AdaptiveRED，ARED）針對RED存在的缺陷，出現(xiàn)了不少RED的派生算法，包括ARED（AdaptiveRED）、SRED（StabilizedRED）和RED-PD（REDPreferentialDropping）等。它們的主要思路是根據(jù)網(wǎng)絡(luò)中負載的情況對丟失概率進行動態(tài)調(diào)整，這里主要介紹ARED算法。ARED在RED算法的基礎(chǔ)上增加了根據(jù)平均隊列長度調(diào)整的策略，以改變RED算法的控制激進程度。當(dāng)平均隊列長度小于，就減小以使控制更為保守；反之當(dāng)平均隊列大于時，就增大以使控制更為激進。ARED使用了兩個額外的參數(shù)α和β來對進行調(diào)整，其調(diào)整策略是：每當(dāng)平均隊列長度avg被更新時，如果avg的值所在區(qū)域發(fā)生變化，的更新方法如2.3式所示：（2.3）其中β>α>1，當(dāng)選取β=α=1時，ARED算法就變成了普通的RED算法。ARED對RED算法改動很小，但在一定程度上彌補了RED算法參數(shù)對于網(wǎng)絡(luò)條件的依賴性，算法性能得到了較大的改善。2.3PI算法比例-積分（ProportionalIntegral，PI）前面提到的AQM控制機制大多在研究工作很大程度上是依賴于直覺的、啟發(fā)性的、針對局部個別問題的，沒有以系統(tǒng)的理論作為分析和設(shè)計的依據(jù)。因此算法的性能難以保證，另外在算法參數(shù)的選擇問題上也具有一定的困難性。Misra等將Internet中的數(shù)據(jù)流看作一個連續(xù)狀態(tài)的流體，并據(jù)此假設(shè)建立了TCP/AQM系統(tǒng)的一個流體流非線性動態(tài)模型（Fluid-FlowModel）。該模型可描述為：（2.4）式中：W為TCP擁塞窗口大小，q為瞬時隊列長度，R為往返時間RTT=q/C+d，d為傳輸延時，C是鏈路帶寬，N為網(wǎng)絡(luò)負載（TCP連接數(shù)），p為分組丟棄/標(biāo)記的概率。研究表明式（2.4）所示的模型可以在一定程度上較好的描述TCP/AQM系統(tǒng)的動態(tài)特性，因此被大多數(shù)基于控制理論的算法用于擁塞控制算法的設(shè)計和分析。Hollot據(jù)此線性化后的模型，用經(jīng)典線性控制理論分析了RED的穩(wěn)定性和參數(shù)選擇的依據(jù)，并給出了一種用于AQM的比例-積分（ProportionalIntegral，PI）控制器，控制算式見式（2.10）：（2.5）其中，為比例增益系數(shù)，積分增益系數(shù)。（2.6）這里E(s)是當(dāng)前隊列長度和目標(biāo)隊列長度之間的誤差。使用離散的形式，誤差可以表示為：（2.7）對式（2.6）使用雙線性變換：（2.8）這里T是采樣周期。由此，我們可以得到PI控制器傳遞函數(shù)的離散形式如下：（2.9）可以得到式（2.9）的離散化形式為：(2.10)式中：，PI算法在一定程度上克服了網(wǎng)絡(luò)參數(shù)變化的擾動，在大多數(shù)網(wǎng)絡(luò)環(huán)境下可以將隊列長度控制在一個目標(biāo)值附近，并保證了一定的穩(wěn)定裕度。算法降低了端到端的延時抖動，提高了系統(tǒng)性能，更有助于AQM技術(shù)目標(biāo)的實現(xiàn)。但是PI算法也存在對擾動響應(yīng)太慢的問題?；诳刂评碚撛O(shè)計和分析主動隊列管理機制具有以下優(yōu)越性：設(shè)計方法更加科學(xué)，參數(shù)配置容易。控制理論是在系統(tǒng)數(shù)學(xué)模型的基礎(chǔ)上建立起來的完善的理論體系，可以根據(jù)系統(tǒng)的穩(wěn)態(tài)和動態(tài)性能要求選擇合適的；控制器，根據(jù)系統(tǒng)的穩(wěn)定性、準確性、快速性、魯棒性等要求決定控制器的參數(shù)；算法的性能對網(wǎng)絡(luò)條件的敏感性降低，在控制器的設(shè)計階段就已經(jīng)將系統(tǒng)的穩(wěn)態(tài)精度、響應(yīng)速度、穩(wěn)定裕度、抗干擾能力等作為設(shè)計目標(biāo)；大部分基于控制理論設(shè)計的AQM機制的復(fù)雜程度與RED相當(dāng)，實現(xiàn)簡單，適用于高速網(wǎng)絡(luò)。特別是從經(jīng)典控制理論推導(dǎo)出的控制器，其報文丟棄概率通常是瞬時隊列長度的線性函數(shù)；具有明確的控制目標(biāo)，消除了隊列長度與負載的耦合，減小了隊列振蕩。2.4REM算法隨機指數(shù)標(biāo)記（RandomExponentialMarking，REM）典型的基于優(yōu)化理論方法的AQM算法是REM（RandomExponentialMarking）。它的設(shè)計是從最優(yōu)化流控制（OptimizationFlowControl）理論得到的，其設(shè)計目標(biāo)是在較低的隊列延遲下保證隊列輸入速率和輸出速率的匹配。算法包含2個主要部分。一個是價格機制（pricemechanism），用于擁塞的測量；另一個是指數(shù)標(biāo)記（exponentialmarking），用于擁塞的反饋，但是算法并沒有明確說明使用指數(shù)函數(shù)的優(yōu)勢。 (2.11)式中：p(t)為t時刻的價格；b(t)為t時刻的隊列長度；為期望隊列長度；x(t)為t時刻隊列的輸入速率；c(t)為t時刻隊列的輸出速率；γ和α是較小的正實數(shù)。(2.12)其中m(t)為t時刻分組的標(biāo)記/丟棄概率；φ為大于1的正實數(shù)。式（2.11）、（2.12）用于標(biāo)記概率的計算。其中式（2.11）用于計算價格，以對網(wǎng)絡(luò)的擁塞程度進行度量，用戶越多則價格也越高。α用于調(diào)整隊列長度誤差和速率誤差之間的權(quán)值，γ用于控制REM算法對于網(wǎng)絡(luò)條件的響應(yīng)速度。式（2.12）由價格計算標(biāo)記概率，價格越高則標(biāo)記概率也越高。REM算法是一個二階網(wǎng)絡(luò)擁塞控制算法，通過解耦網(wǎng)絡(luò)性能的平衡值和分組丟棄率的平衡值，使得網(wǎng)絡(luò)達到平衡時，系統(tǒng)具有較低的分組丟棄率和較短的隊列時延，能更好的保證Internet的服務(wù)質(zhì)量，提高網(wǎng)絡(luò)的穩(wěn)定性。REM算法利用了Kell提出的網(wǎng)絡(luò)流量優(yōu)化理論中“價格”的概念來探測和控制網(wǎng)絡(luò)的擁塞狀態(tài)?！皟r格”的變化由兩方面的因素決定，一方面是瞬時隊列長度與目標(biāo)隊列長度之間的差值，另一方面是報文到達速率與鏈路帶寬的差值。REM將報文到達速率與鏈路帶寬的差值和瞬時隊列長度與目標(biāo)隊列長度的差值的加權(quán)組合定義為鏈路“價格”。REM利用一條通路上所有連接的“價格”值的累加和作為這條通路的擁塞度量，并把它嵌入到，可以被源端檢測到的端到端的包標(biāo)記概率中。REM的目標(biāo)是使報文到達速率與鏈路帶寬相匹配，從而清空緩沖區(qū)。

第三章實驗方法實驗中，我們構(gòu)建了一個實驗室網(wǎng)絡(luò)用來仿真兩個互聯(lián)網(wǎng)提供商網(wǎng)絡(luò)的互連。特別地是，我們仿真了一條對等的連接用來負載源節(jié)點和目的節(jié)點之間的網(wǎng)絡(luò)流量傳輸，并且兩個ISP網(wǎng)絡(luò)之間的網(wǎng)絡(luò)傳輸在兩個方向上取得均衡。架構(gòu)中所有的系統(tǒng)全部是運行于FREEBSD4.5下的英特爾機制。在這個網(wǎng)絡(luò)的邊緣，一系列的機器在運行，例如網(wǎng)站請求發(fā)生器用來仿真成千上萬個用戶瀏覽網(wǎng)頁的行為。另外，在網(wǎng)絡(luò)的每一個邊緣也運行著類似網(wǎng)站響應(yīng)發(fā)生器的機器，產(chǎn)生網(wǎng)絡(luò)傳輸流來響應(yīng)瀏覽請求。試驗臺上共有44個網(wǎng)絡(luò)流量發(fā)生器。在本文在余下內(nèi)容中，我們將以瀏覽器代稱請求發(fā)生器，用服務(wù)器網(wǎng)絡(luò)流量響應(yīng)器。該網(wǎng)絡(luò)的核心是有運行于有ALTQ擴展成的FREEBSD的兩個路由器組成。ALTQ在網(wǎng)絡(luò)接口處把IP輸出隊列擴展成可選擇的隊列管理科目。ALTQ通常有PI,REM和ARED組成。路由器有三個點對點的以太網(wǎng)段組成（2個100MPS的以太網(wǎng)段和1個光纖的Gbit的以太網(wǎng)）實現(xiàn)互連。Gbit的以太網(wǎng)用來仿真不擁塞的網(wǎng)絡(luò)環(huán)境，而100MPS的以太網(wǎng)用來仿真擁塞的網(wǎng)絡(luò)環(huán)境。當(dāng)運行于不擁擠的網(wǎng)絡(luò)環(huán)境時，路由器配置靜態(tài)的路徑，從而在GBIT以太網(wǎng)中實現(xiàn)網(wǎng)絡(luò)中的全雙工傳輸。當(dāng)我們需要模擬一下路由瓶頸時，靜態(tài)路徑需要重新配置，在一個方向的網(wǎng)絡(luò)傳輸流通過10MPS以太網(wǎng)傳輸，在相反的方向上，利用另一個100mps以太網(wǎng)進行網(wǎng)絡(luò)傳輸，這種配置可以用來模擬廣域網(wǎng)的網(wǎng)絡(luò)連接。影響這個網(wǎng)絡(luò)仿真的另一個重要因素是端到端延遲。我們使用一個本地修改的FreeBSD組件配置瀏覽器出包的延遲，仿真每次TCP傳輸時的不同往返時延。通過擴展dummynet機制，從調(diào)整每次流的帶寬擴展成一個新的模式，即對每次數(shù)據(jù)流的數(shù)據(jù)包隨即附加一個最小的延遲。在一個跟定的數(shù)據(jù)流中所有的最小延遲相同（通過IP尋址5元組）。毫秒級的最小延遲從每次實驗分配的一個輪回時間里隨即采樣獲得。通常采用兩輪循環(huán)分發(fā)。第一次是離散的統(tǒng)一分發(fā)。一次統(tǒng)一分發(fā)的時間在[10,150]之間（平均80毫秒）。一次分發(fā)的最小值和最大值是通過文獻[5]中所描述的方法來選擇來近似網(wǎng)絡(luò)往返時延的變化范圍。統(tǒng)一分發(fā)確保了在這個范圍內(nèi)可以有很大的變化。第二個最小的往返時延是更加普遍的分布，其源自于一個最近關(guān)于往返時延的測量研究中，通過TCP連接傳送一個大學(xué)校園的網(wǎng)關(guān)。本次試驗中通過TCP發(fā)送的來回的次數(shù)是有最小的RTT循環(huán)時間加上路由器的隊列延遲之和組成的。（終端系統(tǒng)配置成無資源限制，從而沒有延遲）TCP傳輸窗口采用的是16KBIT，因為這被廣泛應(yīng)用于OS平臺上。大多數(shù)的windows版本上，通常具有默認的windows值或比這個更小。3.1類網(wǎng)頁流的產(chǎn)生流量是驅(qū)使我們的仿真是基于一個最近的大規(guī)模的網(wǎng)頁流分析。由此產(chǎn)生的模型是一個應(yīng)用程序級描述，具體描述了HTTP/1.0和HTTP/1.1協(xié)議在實際中如何運行。它是基于實驗數(shù)據(jù),適用于合成Web工作負載。這個模型的一個重要特性是它反映了在我們目前使用的許多瀏覽器和服務(wù)器中持續(xù)使用HTTP連接實現(xiàn)。此外，文獻16中區(qū)分了“頂層”Web對象（通常是一個HTML文件）和它們嵌入對象（例如，圖像文件）。這些數(shù)據(jù)在這時聚集，近于所有TCP連接的15％承載HTTP協(xié)議得到了有效的持續(xù)性（分別為用于請求兩個或多個對象），但超過這些所有對象的50％（40％字節(jié)數(shù)）在這些持續(xù)的連接被轉(zhuǎn)移。該模型作為經(jīng)驗分布用來描述合成HTTP工作負載的元素。該模型的元素在在新增流中有明顯的作用。大多數(shù)的網(wǎng)頁瀏覽行為在客戶請求程序（瀏覽器）中被仿真。它最主要的參數(shù)是瀏覽用戶數(shù)量的仿真（最典型的是幾百到幾千）。對每個用戶的仿真，這個程序?qū)崿F(xiàn)了一個簡單的狀態(tài)機的功能，可代表了用戶的狀態(tài)如思考或者請求一個web網(wǎng)頁。如果請求一個web網(wǎng)頁發(fā)送一個請求到服務(wù)器端(執(zhí)行遠程機器上)。然后對于每個嵌入式參考請求發(fā)送到一些服務(wù)器上。瀏覽器同樣決定了適當(dāng)?shù)氖褂贸掷m(xù)和非持續(xù)的連接;所以新連接的15%是隨機選擇持續(xù)的。另一個隨機選擇是從每秒的分布請求是持續(xù)連接，用于確定有多少請求將使用持續(xù)連接。程序的另一個參數(shù)是平行TCP連接的數(shù)量，允許每個瀏覽用戶使嵌入的請求在一個頁面上。對于每一個請求，一個消息的隨機樣本大小，來自于請求大小分布，通過網(wǎng)絡(luò)發(fā)送到一個服務(wù)器程序的實例。這消息作為響應(yīng)返回指定的服務(wù)器字節(jié)數(shù)量。（一個隨機樣本大小的分布不同的取決于是否它是一個頂層或嵌入的請求）。服務(wù)器傳回字節(jié)大小到瀏覽器中。對每一個請求/響應(yīng)的交換，瀏覽器記錄其響應(yīng)時間。響應(yīng)時間定義為運行時間，無論是在套接字連接()操作(一個非持續(xù)的連接)或初始請求(在一個持續(xù)連接)或套接字寫()操作(在持續(xù)連接后續(xù)請求)和最后字節(jié)響應(yīng)被返回的時間。注意,這個響應(yīng)時間是頁面的每一個對象的時間,而不是加載一個頁面中所有對象的總時間。當(dāng)一個頁面所有的請求/響應(yīng)被完成時，模擬瀏覽用戶進入思維狀態(tài)，在一個隨機的時間段中不會做出更多的請求。這個網(wǎng)頁的數(shù)量要求用戶從分布連續(xù)頁面請求繼承一個給定服務(wù)器的樣本。當(dāng)頁面請求的數(shù)量被完成，接下來的服務(wù)器隨機地從一組活動服務(wù)器中選擇，用來處理下一個頂層請求。在實驗過程中用戶的數(shù)量是不變的。表1元素描述請求大小HTTP請求的長度字節(jié)反應(yīng)大小HTTP應(yīng)答長度字節(jié)頁面大小每個頁面的嵌入式(文件)的引用數(shù)量持續(xù)性連接使用每秒的持續(xù)連接請求數(shù)判斷時間兩個連續(xù)頁面之間檢索時間每頁面的服務(wù)器一個頁面中的所有對象的的服務(wù)器連續(xù)頁面檢索從一個給定服務(wù)器的連續(xù)頂層頁面請求數(shù)3.2實驗校準我們的實驗提供的負載定義為從模仿固定數(shù)量的網(wǎng)絡(luò)用戶產(chǎn)生的網(wǎng)絡(luò)交通瀏覽行為。它表示為由用戶產(chǎn)生的不擁擠的長期平均吞吐量(字節(jié)/秒)。在我們實驗過程中有三個關(guān)鍵因素必須在實驗操作之前校準：鏈接吞吐量和用戶統(tǒng)一的模擬瀏覽數(shù)量以及一般最小往返時間分布1、確保沒有端到端路徑的元素時，被代表的是一個主要的通信瓶頸,而不是當(dāng)他們被限制到100Mbps時，連接到這兩個路由器中。2、在網(wǎng)絡(luò)上提供的負載可以通過控制模擬用戶的使用數(shù)量來預(yù)測，并把它作為交通發(fā)電機的一個參數(shù)。3、確保產(chǎn)生的數(shù)據(jù)包到達的時間序列(如包數(shù)每毫秒)是如預(yù)期那樣長范圍相關(guān)的，因為分布的響應(yīng)大小是一個重尾分布。為了驗證這些校準，我們首先配置網(wǎng)絡(luò)連接到路由器并運行在1Gbps上來消除擁塞。所有的校準實驗運行在長度等于2400的掉尾巴隊列包(關(guān)于選擇原因這個是第4部分中討論)。我們在每個瀏覽器上運行了一個瀏覽器程序的實例和在所有服務(wù)器上運行了一個服務(wù)器程序的實例。每一個瀏覽器被配置為模擬相同數(shù)量的活躍用戶和7000到35000等不同的總活躍用戶數(shù)。我們演示了兩套校準實驗：一個是統(tǒng)一的最小RTT分布，另一個是更一般的最小RTT分布。相反方向上負載的測量本質(zhì)上是相同的,所以沒有繪制在這圖中。提供的負載表示為鏈接的吞吐量是一個模擬用戶數(shù)量的線性函數(shù)，它用來指示沒有基本的系統(tǒng)資源限制和產(chǎn)生的負載可以輕松地超出100Mbps鏈路的能力。對于我們每一個最小RTT分布，這些數(shù)據(jù)可以被用來確定模擬用戶的數(shù)量，并將會在缺乏瓶頸的鏈路上產(chǎn)生一個特定提供的負載。這個功能是用于后續(xù)實驗中控制網(wǎng)絡(luò)上提供的負載。例如，如果我們想要有產(chǎn)生一個提供負載等于100Mbps鏈路的能力，我們將需要在ISP1上模擬一個用戶群體和在ISP2上一個用戶群體，這樣在ISP1中模擬用戶群體得到的總請求流量到在ISP2上的服務(wù)器，再加上總響應(yīng)流量從ISP1服務(wù)器到ISP2上模擬用戶群體，等于平均100Mbps。類似情況也會有持續(xù)的交通流量從ISP2到ISP1中。為了產(chǎn)生一個提供100Mbps的負載，用于確定均勻分布最小實時傳輸系統(tǒng)，大約9520用戶必須在1Gbps鏈接兩側(cè)模擬(即9520用戶在ISP1和9520用戶ISP2總數(shù)為19040仿真用戶)。注意，正如預(yù)期的那樣，更多的用戶必須通過使用更為一般的最小RTT分布來模擬實現(xiàn)給定目標(biāo)的負載。這是因為響應(yīng)時間變得更長了，用戶在他們能產(chǎn)生新的請求之前，他們必須等待更長的時間，進而在單位時間內(nèi)產(chǎn)生更少的請求。在實驗中使用web流量的動機是產(chǎn)生的交通假設(shè)會正確地展現(xiàn)實驗室網(wǎng)絡(luò)符合在實踐研究中發(fā)現(xiàn)的那些真實網(wǎng)絡(luò)的要求，特別地，一個遠程依賴數(shù)據(jù)包到達過程。實證數(shù)據(jù)生成的網(wǎng)絡(luò)流量顯示尾分布對于用戶“思考”時間和響應(yīng)大小。例如，雖然在實驗中產(chǎn)生的平均響應(yīng)大小大約為1000字節(jié)，也產(chǎn)生109字節(jié)一樣大小的響應(yīng)。我們分析驗證到達路由器接口的數(shù)據(jù)包和字節(jié)數(shù)量實際上構(gòu)成了一個LRD到達過程。因此，盡管我們的研究只考慮網(wǎng)絡(luò)流量，但是在路由器對列中到達過程的動態(tài)性是說明到達過程是在實際網(wǎng)絡(luò)中觀察到的。3.3實驗步驟每個實驗運行在使用模擬用戶選擇的固定群體上，正如上面描述的，將一個名義上提供的負載放在一個無約束網(wǎng)絡(luò)上。每個瀏覽器程序模擬同等數(shù)量的用戶。在實驗中提供的負載用來表示能夠消耗兩臺路由器100Mbps鏈接中90%或98%的用戶群體。我們證明了在提供的負載上升到鏈接能力的80%時，AQM響應(yīng)分布時間的分布與傳統(tǒng)下降的尾巴FIFO隊列幾乎相同。因為這些分布同樣十分相似于在擁堵的網(wǎng)絡(luò)上響應(yīng)時間分布，我們推斷AQM沒有任何優(yōu)勢在掉尾低于80%負載時?；谶@個原因我們在這里開始研究90%的負載。這里很重要再強調(diào)一下，像“98%負載”這樣的詞被用來當(dāng)作“能夠產(chǎn)生一個在1Gbps鏈路上平均負載一直為98Mbps的Web用戶群體”的簡稱。每個實驗運行120分鐘，這樣可以確保足夠的采樣樣本(在每個實驗中超過10000000個請求/響應(yīng)交換)，但是數(shù)據(jù)只在90分鐘的間隔內(nèi)采集，這樣可以消除開始的啟動效應(yīng)和終端同步異常終止。對于每個給定方案的AQM實驗要被重復(fù)三次通過每次設(shè)置不同隨機種子數(shù)。為了促進不同AQM方案的比較，不同方案的實驗在每個隨機數(shù)發(fā)生器上運行相同的初始種子設(shè)置。我們在表述我們的結(jié)果時使用的關(guān)鍵性能指標(biāo)是對于HTTP請求/響應(yīng)交換所需要的端到端響應(yīng)時間。我們記錄這些作為響應(yīng)時間到達2秒的累計分布圖。在這些圖中，我們展示從每個獨立重復(fù)實驗得來的混合結(jié)果。我們同樣也展示了在一個擁堵1Gbps鏈接上獲得的結(jié)果，這樣提供了一個比較的基準。在所有的圖中，這個“擁塞的網(wǎng)絡(luò)”線代表著最有可能的響應(yīng)時間分布。我們同樣記錄了一部分在鏈接隊列丟棄的IP數(shù)據(jù)報，和在實驗中請求/響應(yīng)交換完成的數(shù)量。我們記錄測量的這些值代表著在一個實驗中的三次重復(fù)。

第四章丟包環(huán)境下的AQM實驗對于PI和REM，我們針對目標(biāo)隊列長度分別為24和240個數(shù)據(jù)包的情況進行了分析。選這兩個值代表兩個研究點：一個代表可能產(chǎn)生的最小延遲（24），另一個則代表可能提供的高鏈路利用率（240）。對于ARED，我們對相同的兩個目標(biāo)隊列長度進行了分析。針對所有的ARED參數(shù)的設(shè)置，完全按照S.Floyd,R.Gummadi,S.Shenker,AdaptiveRED:AnAlgorithmforIncreasingtheRobustnessofRED’sActiveQueueManagement,/floyd/papers/adaptiveRed.pdf,August1,2001.中的指導(dǎo)方針進行設(shè)置，用于實現(xiàn)所需的目標(biāo)延遲（隊列大小）。對于以上的這三種算法中，我們設(shè)置的最大隊列大小足夠滿足其內(nèi)封包的數(shù)量，以保證不會出現(xiàn)隊尾丟棄的情況。并且我們所有的仿真實驗都使用統(tǒng)一的最小時延分布。4.1丟包環(huán)境下PI的仿真結(jié)果 圖4.1給出了目標(biāo)隊列長度在24和240個數(shù)據(jù)包，負載為90％和98％情況下PI算法的仿真結(jié)果。當(dāng)負載為90％時，若目標(biāo)隊列長度為24，則對于基本上所有的請求/響應(yīng)交換都對應(yīng)較低的響應(yīng)時間。當(dāng)然除了最多10％的業(yè)務(wù)量，這些交換請求需要超過大約500毫秒來完成。對于這部分請求/響應(yīng)交換，在目標(biāo)隊列達到240的時候，能夠得到相對更好的處理性能。表2提供的負載丟包率完成的請求（百萬）鏈路使用率（Mbps）1Gbps網(wǎng)絡(luò)90%015.091.398%016.298.2尾部丟棄90%1.914.790.098%5.815.191.9PI90%1.114.588.198%4.114.989.4PI90%0.414.688.398%3.715.090.0REM90%1.614.386.498%4.914.687.5REM90%3.213.783.398%5.414.486.2PI,REM算法下的丟包率，完成的請求以及鏈路使用率當(dāng)負載為98%時，對于優(yōu)化“短”的交換，即那些需要在小于約400毫秒內(nèi)完成的請求，還是“長”的交換，即那些需要超過400毫秒的時間來完成的響應(yīng)的請求，這兩者時間之間的權(quán)衡，變得更為清晰。即負載為98%，目標(biāo)隊列長度為24個封包時，至少70%的請求/響應(yīng)交換將得到較低的響應(yīng)時間。但是在兩個負載情況下，兩種隊列長度，對于那些非常大的交換請求（需要2秒才能完成的）其性能都一致?？傮w來說，我們認為當(dāng)使用的目標(biāo)隊列長度為參考值24時，PI提供了最佳的相應(yīng)時間性能。表2總結(jié)了，丟包率，鏈路使用率和實驗中完成的請求數(shù)。圖4.1中分析在高負載下，即產(chǎn)生大量丟包情況下的實驗結(jié)果，我們可以發(fā)現(xiàn)一個特點。在500毫秒到1秒之間的曲線較為平坦。這是TCP操作中超時重傳機制的時間間隔所致。Figure4.1:ResponsetimedistributionforPIwithpacketdrops4.2丟包環(huán)境下REM的仿真結(jié)果圖4.2給出了目標(biāo)隊列長度在24和240個數(shù)據(jù)包，負載為90％和98％情況下REM算法的仿真結(jié)果。在負載為90%的情況下，隊列長度為24個封包的仿真性能顯著優(yōu)于隊列長度為240個封包的。同樣在負載為98%的情況下，依然呈現(xiàn)上述結(jié)果。所以整體來說，對于PI和REM算法，當(dāng)其目標(biāo)隊列長度為24個封包時，便可以提供最佳的響應(yīng)時間性能。Figure4.2:ResponsetimedistributionforREMwithpacketdrops4.3丟包環(huán)境下ARED的仿真結(jié)果Figure4.3:ResponsetimedistributionforAREDinpacket-modewithdrops針對ARED的仿真主要在兩個模式下進行：封包模式和字節(jié)模式（利用ARED算法根據(jù)封包或是比特計算平均的隊列長度）。之前在丟包情況下，對封包模式的ARED算法的仿真的結(jié)果并不理想。L.Le,J.Aikat,K.Jeffay,F.D.Smith,TheEffectsofActiveQueueManagementonWebPerformance,ACMSIGCOMM2003,August2003,pp.265-276.此文，將ARED算法與先進先出隊列尾部丟棄機制在各種負載情況下進行了全面對比，并指出ARED增加了HTTP傳輸?shù)捻憫?yīng)時間。這些結(jié)果在這里得到了驗證。在ARED封包模式下，圖4.3顯示了其在兩種負載，和兩種目標(biāo)隊列長度情況下，相對于PI和REM算法的一個顯著差距。但是正如圖4.4中顯示的那樣的，當(dāng)在字節(jié)模式下，ARED將提供明顯更好的響應(yīng)時間。Figure4.4:ResponsetimedistributionforAREDinbyte-modewithdrops表3提供的負載丟包率完成的請求鏈路使用率AREDmin=12max=3690%0.913.885.298%2.11.3986.2AREDbytemin=12max=3690%0.814.688.098%3.614.889.4AREDmin=120max=36090%1.113.984.998%3.314.086.1AREDbytemin=120max=36090%0.914.687.698%4.214.687.8ARED算法下的丟包率，完成的請求以及鏈路使用率有趣的是，正如表3中看到的，在負載為98%時，字節(jié)模式的ARED將比封包模式下存在較高的丟包率，但是在實驗中其完成了更多的響應(yīng)以及更高的網(wǎng)絡(luò)利用率。與PI和REM相同的是，得到ARED最佳性能的隊列閥值與目標(biāo)隊列長度為24個封包相對應(yīng)（）。4.4比較所有丟包方案我們以drop-tail策略(隊列長度為24個數(shù)據(jù)包或240個數(shù)據(jù)包)的性能表現(xiàn)作為基準來評估AQM算法的性能，此外，我們還嘗試找到一種適合隊尾丟棄策略的最佳隊列長度。在我們的實驗中，鏈路帶寬為100Mbps,幀的平均大小略大于500個字節(jié)，這意味著100毫秒內(nèi)有大約2400個數(shù)據(jù)包的隊列進入緩存區(qū)。我們把長度為240個數(shù)據(jù)包的drop-tail隊列的性能表現(xiàn)作為基準來比較各種AQM算法，因為即使在100Mbps的速率下只有10毫秒的緩存時間，但是這符合為測試AQM算法而設(shè)定的目標(biāo)之一，并表現(xiàn)出了的良好的性能，F(xiàn)igure4.5:Comparisonofallschemesat90%load在圖片4.5和圖片4.6中，在網(wǎng)絡(luò)負載為90%、98%的情況下，我們比較了PI，REM和ARED算法（參數(shù)設(shè)置為最佳）的響應(yīng)時間性能。為了調(diào)整這些曲線，在100Mbps擁塞的網(wǎng)絡(luò)和1Gbps非擁塞的網(wǎng)絡(luò)中，也顯示了drop-tail策略的響應(yīng)時間性能，非擁塞的網(wǎng)絡(luò)性能曲線表示最佳的響應(yīng)時間分布，也為各種AQM算法的比較提供了一個基準。100Mbps網(wǎng)絡(luò)的drop-tail曲線（在所有圖片中標(biāo)記為drop-tail的曲線）代表基本的性能，這是所有的AQM算法都應(yīng)該能超過的，因此，在評估一種AQM算法時，如果它的響應(yīng)時間CDF優(yōu)于drop-tail的時，那么它的性能是絕對可以接受的。在比較兩種AQM算法的性能時，如果其響應(yīng)時間的累積分布函數(shù)在大范圍內(nèi)明顯高于其他算法，在剩余范圍內(nèi)不相上下，我們可以認為該算法的響應(yīng)時間性能更優(yōu)。比較各種AQM算法在網(wǎng)絡(luò)負載為90%情況下的性能，運行在字節(jié)模式的ARED算法性能最佳，對于所有的請求/響應(yīng)數(shù)據(jù)交換具有最佳的響應(yīng)時間。PI、REM和drop-tail算法對于大約40%的交互能表現(xiàn)出相同的性能，這些交互在大約125毫秒或者更少的時間內(nèi)能完成。對于到兩秒的其余的分布，PI優(yōu)于REM和drop-tail,而REM的性能要么劣于drop-tail,要么兩者一樣。Figure4.6:Comparisonofallschemesat98%load在網(wǎng)絡(luò)負載為98%的情況下，單字節(jié)模式中PI、REM和ARED性能幾乎相同，大約65%的請求/響應(yīng)交互過程能在300毫秒或者更少的時間內(nèi)完成。另外，這三種算法都優(yōu)于drop-tail。對于剩下的35%的交互過程，ARED和PI的響應(yīng)時間要么與drop-tail相似，要么略優(yōu)于drop-tail，而相比drop-tail,REM的響應(yīng)時間稍微遜色一點。然而，在網(wǎng)絡(luò)負載最大的情況下，所有的AQM算法都不能補償性能的退化。表2和表3顯示，在網(wǎng)絡(luò)負載為給定的90%和98%的情況下，采用drop-tail策略的含240個數(shù)據(jù)包的隊列，其鏈路利用率比任何AQM算法都好一點。其完成的請求/響應(yīng)交互比其他的算法也稍微多一些。然而，相比其他的算法，drop-tail的丟包率更高。字節(jié)模式的ARED在兩種不同網(wǎng)絡(luò)負載的情況下相比PI和REM丟包率稍微低一點。相比REM，ARED和PI交互的次數(shù)更多，鏈路利用率更高。圖片4.5和圖片4.6顯示，在網(wǎng)絡(luò)負載為98%，AQM參數(shù)設(shè)置最佳的情況下，至少90%的請求/響應(yīng)交互能在2秒內(nèi)完成。從圖片4.5，圖片4.6中得出的結(jié)論對于響應(yīng)時間高達50秒的數(shù)據(jù)交互過程也成立（99.95%的請求/響應(yīng)數(shù)據(jù)交互）。對于剩余的0.05%的數(shù)據(jù)交互，drop-tail算法性能最佳，字節(jié)模式的ARED的性能優(yōu)于PI和REM。從實驗中我們可以得出的主要結(jié)論是，相比drop-tail先入先出的隊列管理策略，AQM算法，特別是PI和字節(jié)模式的ARED能夠改善網(wǎng)頁數(shù)據(jù)交換的響應(yīng)時間，但這是以其鏈路利用率的輕微下降為代價的。

第五章結(jié)論從我們的實驗結(jié)果中，我們得到以下實驗結(jié)論。這些結(jié)論是基于這樣一個前提，即用戶可以感知的相應(yīng)時間是性能分析的首要標(biāo)準，雖然鏈路利用率和丟包率也很重要，但在實驗中作為次要的測量標(biāo)準。在陳述我們的結(jié)論之前，很有必要列出我們最初AQM研究的一些初級結(jié)論：對于負載為80%的鏈路負載率，沒有其他AQM策略比簡單的尾部丟包策略的性能更好。而且，相同活躍數(shù)量的用戶產(chǎn)生的這些負載在100Mb/s上的相應(yīng)時間和在1Gb/s鏈路上并沒有實質(zhì)性差別。因此，對于web或是類似web的業(yè)務(wù)類型，AQM策略只在鏈路出現(xiàn)高負載時才能發(fā)揮其優(yōu)勢。對于負載為90%和98%的鏈路負載率，我們得到如下的結(jié)論。ARED在字節(jié)模式下的性能顯著強于其在封包模式下。而且，目前推薦使用的ARED策略是在封包模式下，但該種方式其實是性能最差的AQM設(shè)計。當(dāng)不采用顯式堵塞通知時，字節(jié)模式的ARED是這幾種AQM策略中性能最優(yōu)的，它比PI和REM都要好，并且比起隊尾丟包更加能夠提供一個合理的相應(yīng)時間。REM和封包模式下的ARED比起隊尾丟包策略其提供的性能更差。我們認為，AQM可以提升網(wǎng)頁業(yè)務(wù)下的網(wǎng)絡(luò)性能和應(yīng)用。如果網(wǎng)絡(luò)中反復(fù)無規(guī)律出現(xiàn)高負載情況，理論上PI和REM提供最佳的調(diào)度性能，但這也只是在端系統(tǒng)和路由器都能提供顯式堵塞通知的情況下。在這種情形下，對于高負載網(wǎng)絡(luò)性能的提升是本質(zhì)的。不論使用AQM策略之后在響應(yīng)時間上的性能提升是否顯著（當(dāng)與隊尾丟包FIFO相比），其效果都嚴重依賴于業(yè)務(wù)流往返時延（RTT）的范圍。隨著流往返時延（RTT）的增加，AQM策略在響應(yīng)時間性能的提升作用將會減弱。如果網(wǎng)絡(luò)的飽和度不確定，那么字節(jié)模式下的ARED策略將會提供最佳的網(wǎng)絡(luò)性能。綜上所述，這些結(jié)果都表明，在應(yīng)用或是網(wǎng)絡(luò)性能沒有顯著下降的前提下，我們應(yīng)該設(shè)計當(dāng)網(wǎng)頁業(yè)務(wù)量90%以上，提供基于其業(yè)務(wù)量變化所主導(dǎo)的相應(yīng)最佳的AQM策略。

參考文獻[1]J.Aikat,J.Kaur,D.Smith,K.Jeffay,VariabilityinTCPRoundtripTimes,Proc.2003ACMInternetMeasurementConference,MiamiBeach,FL,October2003,pp.279-284.[2]S.Athuraliya,ANoteonParameterValuesofREMwithReno-likeAlgorithms,,March2002.[3]S.Athuraliya,V.H.Li,S.H.Low,QingheYin,REM:ActiveQueueManagement,IEEENetwork,Vol.15,No.3,May2001,pp.48-53.[4]B.Braden,etal,RecommendationsonQueueManagementandCongestionAvoidanceintheInternet,RFC2309,April,1998.[5]M.Christiansen,K.Jeffay,D.Ott,andF.D.Smith,TuningREDforWebTraffic,Proc.,ACMSIGCOMM2000,Sept.2000,pp.139-150.[6]W.Feng,D.Kandlur,D.Saha,K.Shin,ASelf-ConfiguringREDGateway,Proc.,INFOCOM‘99,March1999,pp.1320-1328.[7]S.Floyd,R.Gummadi,S.Shenker,AdaptiveRED:AnAlgorithmforIncreasingtheRobustnessofRED’sActiveQueueManagement,/floyd/papers/adaptiveRed.pdf,August1,2001.[8]S.Floyd,andV.Jacobson,RandomEarlyDetectionGatewaysforCongestionAvoidance,IEEE/ACMTransactionsonNetworking,Vol.1No.4,August1993,p.397-413.[9]F.Hernández-Campos,F.D.Smith,K.Jeffay,GeneratingRealisticTCPWorkloads,Proc.,ComputerMeasurementGroup’s2004Intl.Conference,LasVegas,NV,December2004.[10]C.V.Hollot,V.Misra,W.-B.Gong,D.Towsley,OnDesigningImprovedControllersforAQMRoutersSupportingTCPFlows,Proc.,IEEEINFOCOM2001,April2