1、通過輕量級仿真捕獲TCP猝發性作者：黃寶儀譯注1，瑞士聯邦科技研究所 John Heideman譯注2，美國南加州大學信息科學研究所關鍵詞：TCP模擬，網絡仿真，抽象技術，有限狀態自動機摘要:數據傳輸過程中的猝發性（burstiness）譯注3日益成為協議分析中無法忽視的關鍵屬性。為了保存TCP通信出現的這種猝發性或伸縮（scaling）現象，我們開發出一種行為模型，用以捕獲TCP的窗口控制與閉環控制。通過一種稱之為"窮舉狀態探查"的全新模擬技術，我們在限定了連接長度和丟包率的情況下系統地檢驗了各個TCP狀態。這種限制范圍覆蓋了TCP在通常萬維網數據交換條件下的大多數行為。

2、當連接超出此范圍時，我們將引發一個抽象錯誤并切換至一個更具體的模型，以此保持模擬的精確性。通過對那些到達時間間隔落入某臨界區間即往返時間（RTT）或重發超時（RTO）的包進行計數，我們能創造一個顯示背對背包譯注4傳送回合狀態及其轉變的有限狀態自動機(FSA)。我們證明一個TCP的FSA近似可以產生一些適用于生成后臺傳輸量的TCP輕量級仿真模型，并且這些模型能夠精確地再現IP網絡傳輸中多重分形的伸縮行為。一、介紹：仿真已經成為研究大規模網絡協議的必要工具。有著數千節點的實驗臺并不適合通用目的。仿真研究通常通過研究特定后臺傳輸量下的一些新的數據流來考量一種新的協議(如運輸協議，排隊規則等)。對后臺

3、傳輸量的仿真是困難的，原因如下：必須精確地模擬因特網傳輸中固有的猝發性；必須模擬大量的連接，并且必須能夠有效地模擬萬維網數據傳輸量，因為萬維網是當前因特網的最主要應用。正確地模擬數據傳輸量對得出正確結論而言是極其重要的。例如：關于RED12的研究在不同的仿真12和模擬研究5中得出了十分不同的結論。這些研究的一個關鍵差異就是對模擬傳輸的猝發性估計不同。用以捕獲猝發性的一種很有希望的解決方案就是在傳輸建模時采用結構化的方法9，仔細模擬在一個真實網絡中數據傳輸量是如何產生的。在捕獲多種時間尺度下的因特網行為的過程中有兩種機制是至關重要的：1， 用戶級屬性：呈指數分布的萬維網會話到達時間和呈重尾分布譯

4、注5的會話期限會導致較大時間尺度內的持續猝發。例如，大尺度內的自相似性。2， 網絡機制：TCP的閉環控制和基于窗口的傳送機制對中小時間尺度內的異常猝發性有著很大影響。例如，往返時間尺度下的周期性和小尺度下的多重分形性。使用這種傳輸建模方法的一個問題就是狀態開銷。一個對有400用戶的ISP網絡的仿真要使用幾千個隨機變量來保存用戶級屬性，并且要使用數十萬個TCP連接來捕獲多種網絡機制。即使采用并行仿真技術，隨著仿真規模的擴大，內存利用率也往往是關鍵的瓶頸。最后，仿真模型必須正確地模擬當前的因特網傳輸量。TCP是因特網最重要的傳輸協議（占字節傳輸量的95%，包傳輸量的90%，數據流的80%，見6，2

5、9），并且萬維網傳輸量（HTTP）占TCP傳輸量的絕大多數(經常達到60-80%)。雖然長期存在的TCP數據流的穩態行為已經被仔細研究、模擬和分析過（由Floyd開始10，詳見15第二部分），但是這些研究未對較短的數據流進行模擬。雖然那些較長的數據流占因特網字節轉送量的大多數，但大多數數據流是較短的。有些研究29，7指出流量或萬維網文件尺寸呈一種冪次法則譯注6分布，平均值為15-30個包或5-10千字節。 而且，TCP在慢啟動階段變化最快，因此必須小心地模擬這一階段，這對捕獲那些影響到小時間尺度行為的網絡機制來說是十分重要的。我們工作的主要貢獻在于提供了一種能夠有效模擬短期TCP連接的途徑，用

6、以產生后臺傳輸量。我們能做到這一點是由于利用了因特網傳輸量的重尾分布特性，而且我們的方法可以在更具體地表示長期連接的同時非常高效地表示短期連接。由于大多數數據流是短的，這種方法能極大地減少仿真的內存需求。我們用一個有限狀態自動機(FSA)模型來有效地表示短連接。我們用一種全新的技術建立了這個FSA模型：模擬器輔助的窮舉狀態分析。我們利用一個模擬器來研究定量數據段丟失的全部可能情形。通過這些研究，我們構造了一個FSA來近似模擬TCP的擁塞控制行為。根據TCP規格或其某一實現來手工創建這個FSA是非常容易產生誤差的。因此我們利用一個模擬器自動地枚舉狀態空間，并且我們正在開發軟件以便完全自動地創建F

7、SA。我們的方法要求對TCP行為作出三種假設。第一，我們假設大多數較短的TCP數據流可以被模擬成若干背對背包的傳送回合，這些回合由約一次往返時間的延遲分隔開13（出現誤差時延遲會增加）。第二，丟包率是獨立同分布的（與猝發丟失相反）。我們在4.6節中將用我們的FSA模型仿真與詳細的TCP仿真相比較，以驗證我們的這些假設。第三，我們現在的模型只考慮每個數據流最多發生一次丟失的情形，在數據流較短且丟失率較低（5%）的情況下這種假設是適當的。當這些假設被違背時，我們能檢測到，并且會用一個充分詳細的等價TCP模型替換我們的FSA TCP模型，這樣一來，我們就能通過產生一個抽象錯誤來保持仿真的精確性。我們

8、在4.2節中驗證了第三個假設，并且當我們把FSA模型應用于后臺傳輸量仿真時，我們仍然能夠調整它。二、相關工作：我們的工作建立在前人的三方面工作基礎之上：窮舉狀態分析方法是基于通過總體狀態探查而進行的協議分析和短期TCP傳輸分析的。我們的總體TCP行為分析是基于TCP啟動階段行為模擬研究的。我們的FSA仿真模型應用是基于仿真抽象研究的。通過狀態探查而進行的協議分析：有限狀態圖是用以理解協議的行為、正確性和性能的工具之一。人們習慣于用FSA協議近似法來證明協議的正確性。這種工作通常面臨的問題之一就是控制那些必須考慮的狀態空間的大小。典型的做法就是通過假設來限定問題的范圍，或者采用一些技術盡來可能地

9、合并狀態（例如21）。我們的工作同時采用了這兩種技術來限定狀態空間，并且采用模擬器驅動的FSA結構，以此降低出錯的可能性并減少狀態空間的開銷。此外，與前人在大型FSA表示方面的研究不同，我們所關注的是性能分析和近似，而不是正確性評估。TCP穩態的性能分析：關于TCP穩態行為描述方面的研究已經有很多了。早在1991年Floyd就提出了一種簡單的試探式分析方法，可以預測在多個路由器擁塞的情況下的TCP性能。Ott、Kemperman和Mathis完成了一次關于TCP窗口大小行為的正式分析研究24，Lakshman和Madhow提出了一個更加精細的TCP模型19，這個模型假設了較高的延遲-帶寬積和隨

10、機的包丟失。Mathis等人22和Lakshman等人19分別獨立地導出相似的閉型方程，可以近似計算在無序丟失的假設下的TCP穩態帶寬（無重發超時時限）。最近Padhye等人25計算出了那些會導致重發超時和推遲確認的包丟失的概率。 他們的模型在上述方程基礎上增加了對最大窗口大小和超時區間的考慮，能夠較好地預言長TCP連接的帶寬。這些研究的一個共同點就是它們都集中關注非限定長度的TCP連接的穩態行為。有人建議把這些近似值用于確定可接受的擁塞控制界限（由Floyd首先提出11，最近的建議見27，26）。對現實的因特網業務的研究表明，盡管長連接占用了大量帶寬，但絕大多數連接是短的。更準確地說，連接長

11、度服從重尾分布，其均值相當小，約為15-30個包或5-10千字節29，7。 我們參考的這些相關工作與我們自己的工作之間的主要差別就在于對這些短數據流的檢驗。TCP慢啟動性能分析：對短TCP連接的分析已經有兩種研究了。Heidemann等人13模擬了假設無丟失情況下的短TCP連接，以此來比較若干種可選的請求/應答協議。Cardwell等人綜合了上述模型和穩態模型25，推導出了有關短連接和長連接丟包率的閉型解。他們模擬了連接建立時間（包括SYN丟失的情況）、慢啟動階段發送的報文段數量和慢啟動階段的耗時，這都是初始窗口大小和慢啟動窗口增加率的函數。象上述兩種研究一樣，我們也用背對背報文段的傳送回合來

12、模擬TCP，這種回合以第一個報文段被發出為開始，以收到確認為結束。與13不同，我們考慮了包丟失的可能性。與Cardwell等人不同，我們采用的是窮舉狀態分析技術。這樣我們就可以更精確地模擬非線性的慢啟動速度，而他們只能用一個指數來近似的表示。另外，我們也說明了我們的方法如何能夠輕易地用于對TCP傳輸量的高效仿真。仿真抽象：甚大規模仿真需要采用抽象技術，以便從仿真中去除那些對結果無影響的細節。一個常用的抽象技術實例就是把以太網當做10Mb/s的“管道”，而不去模擬MAC層爭用和重傳的細節。Ahn和Danzig建議在數據流仿真中進行包一級的抽象2；他們并不模擬一個數據流中的各個包，而是把它們視為背

13、對背包組。 在上述建議和13的啟發下，我們利用這種方法來判斷TCP運行時間狀態。盡管我們現在分別表示了傳輸中的各個報文段，但是采用Ahn和Danzig的數據流表示法將減少運行時間和內存開銷。另一個有希望的建議就是把TCP模擬成一組微分方程23。雖然這種方法在一定程度上考慮了傳輸量的動態變化，但在模擬的傳輸量具有高猝發性的時候它就無法精確地模擬了。三、TCP建模：流量與擁塞控制機制是任何網絡傳輸協議的核心。這些算法決定了數據包是如何快速地注入網絡的。開環協議把包注入網絡而不考慮網絡或接收方的情況；閉環協議卻會對網絡或接收方發出的擁塞或緩沖區分配信號作出反應。采用了端到端擁塞控制的閉環協議（如TC

14、P）是因特網獲得成功的關鍵，因為它們能夠適應擁塞現象11。我們的目標就是很好地捕獲TCP閉環擁塞控制機制的關鍵方面，以便精確地模擬TCP。理想中我們的模型將能夠很好地再現TCP合計傳輸量譯注7，在較大時間尺度內，它應該與詳細的TCP的合計傳輸量沒什么區別。這一節簡要概述了TCP的擁塞控制機制，并且描述了我們如何用若干背對背包的傳送回合來模擬TCP，這些回合由約一次往返時間的延遲分隔開（見13）。然后我們描述了我們是如何利用仿真版的TCP來把這一模型植入我們所考量的領域的。3.1 關鍵的算法與時間尺度TCP的擁塞控制17和推遲確認3算法決定了短TCP連接的行為。具體地說，TCP是ACK定時的-這

15、就是說，只有在收到接收方的確認之后才會發送新的TCP報文段，發送的新報文段的數量受到擁塞窗口（簡稱cwnd）的限制。在慢啟動期間，每收到一個ACK，cwnd就加1。當慢啟動閥值所指定的數據量（簡稱ssthresh）已經被發送，或者報文段丟失時，慢啟動就結束了。按照推遲確認規則，客戶在收到兩個完整的報文段或者定時器到期之后就發出ACK。如果報文段丟失，TCP將會檢測到，并將用兩種方法予以恢復。第一種方法是快速重傳法18，28，這是恢復單個包丟失的優化方法。如果接收方檢測到一個丟失的報文段，那么它就開始為每一個已經收到的報文段發送ACK。發送方把三個連續的ACK視為該包的丟失信號并且會立即進行重發

16、。第二種方法就是，如果無法使用快速重傳法，則發送方最終將超時（在一個RTO的延遲之后），并將重發未確認的報文段。我們可以在多種時間尺度下觀察TCP的行為：在最粗糙的粒度下（秒），用戶發起新的連接。慢啟動、快速重傳和超時的時間尺度都可以用發送方接收方之間的往返時間來衡量。而ACK定時則發生在非常細小的時間尺度上，可以與包發送的時間相比較。由于這些多種時間尺度的存在，因特網傳輸量表現出一種復雜的、多重分形的行為方式9。 要模擬TCP就必須考慮這種多樣性。試圖再現TCP行為的其它研究（基于速率的RAP方法，見27）的經驗表明，對粗粒度TCP行為的模擬可以再現非常類似TCP的傳輸量，但是在傳輸量統計中

17、明顯缺少細粒度的修正。3.2 簡單FSA的推導我們用一個簡單模型來近似表示TCP，目標是再現中粒度與粗粒度的TCP行為。我們模擬了TCP的慢啟動、快速重傳和超時機制的效果，但我們沒有直接復制那些算法。接下來我們將說明我們能夠再現很大的時間尺度下的TCP合計傳輸量，但我們不期望（也不聲稱）我們能再現很細粒度的ACK定時效果。圖1：左一：在一個短TCP連接中的包交換。左二：序號FSA。左三：回合規模FSA。右一：帶有推遲確認接收器的Reno TCP FSA。圖1的左邊顯示了一個典型的萬維網TCP連接請求。連接建立之后，請求被發出，然后數據被發回給萬維網用戶。數據傳輸由TCP的慢啟動算法控制，通過一

18、系列“回合”進行傳送。每一回合都以傳送一個數據段開始，以收到對該段的確認結束。若發出了多個報文段，則會收到多個ACK；我們假設這些傳送可以重疊。我們分別模擬了有推遲確認機制的接收方和沒有推遲確認機制的接收方。若接收方實施了推遲確認，我們會立即為第一個數據段產生ACK。而在真實的實現中，這些報文段將是定時器驅動的，有1-500ms的隨機延遲，在典型的實現中延遲平均值為100ms。我們通過兩個步驟把這個模型繪制為一個狀態機。第一，考慮圖1的中間部分。各狀態上的數字顯示被發送報文段的序號。灰色橢圓形中的短弧顯示一個包傳送時間的延遲；較長的水平弧顯示大約一次往返的延遲，這相當于發出包后等待確認的時間。

19、狀態圖頂上的那一排狀態記錄了在沒有發生丟失的條件下該圖左部進行包交換的行為。（這部分圖左上方的狀態是傳送一個報文段，然后經歷一個RTT的延遲，然后有兩個報文段處于狀態二，依此類推。）為了模擬包丟失的效果我們向下擴展了這個FSA。包丟失不僅影響了發送下一個報文段之前的延時，也影響到下一回合發送的報文段的數量。丟失一個包可能引發一次超時或者一次快速重傳，我們用向下的粗線表示超時，用向下的細線表示快速重傳，這兩種線都標有丟失的報文段的號碼。丟失報文段的重傳和其他的報文段（如果有的話）共同決定了新的狀態。圖1中間的FSA顯示如果1號報文段丟失，那么TCP連接將等待一次重傳超時，然后重新發送這個報文段。

20、如果3號報文段丟失，那么TCP會先繼續發出兩個報文段，然后丟失的3號報文段才會發生超時。這一模型創造了一個完整卻又冗長的FSA。為了簡化這個狀態機，我們把一系列接連發送的包（背對背包）組合起來，只用弧表示超時和往返延遲。圖1中間的FSA用灰色的圓把這些回合組合起來。圖1的右邊我們表示的是同樣的信息，但是圓內的數字代表的是這一回合內發送的報文段的數量。粗弧仍然代表一次超時延遲，而所有的細弧都表示大約一個RTT的延遲。若一回合中發送了多個報文段，那么這些回合相應的狀態就有多條向下的細線來表示狀態的轉變，每條細線都標有該回合內丟失的報文段的號碼。這個FSA中的位置表示的是TCP的擁塞窗口（wnd）和

21、慢啟動的閥值（ssh）。我們采用的另一個優化措施就是合并了圖中有著相同的擁塞窗口與慢啟動閥值的狀態。圖1右邊的FSA顯示了這一點，由于在第一或者第二回合中丟失了第一個包而導致的超時都會引起狀態的變化，在新的狀態中只會發送一個報文段。這種抽象也允許在不同的丟失模式都終結于同一狀態的情況下進行一定程度的狀態聚合，條件是其終結狀態的待發包數量、擁塞窗口大小、慢啟動閥值都相同。最后，我們得到一個更加易于管理的狀態機（即圖1的右一），這個狀態機可以捕獲TCP連接動態變化的實質。3.3 完整FSA的創建根據TCP規格或其某一實現來手工創建這個FSA是很容易產生誤差的。而且，TCP有許多變異的版本，我們希望

22、都能考慮到。我們在同一個模擬器上系統地進行了一系列試驗。我們對各種規模的傳輸都進行了數據流追蹤（考慮了發送方產生的數據流）。我們計算了包的到達時間間隔，在RTT與RTO已知的前提下，對FSA的相應部分進行了后臺計算。我們系統地為每一個可能丟失的報文段重復這種計算過程。例如，我們構造了一個具有四個節點的網絡：瓶頸鏈路的速度為1.5Mb/s，延遲為100ms，有兩個邊緣鏈路，速度為5Mb/s，延遲為2ms（因此總往返時間為204ms）。 對圖1左邊的狀態機而言，一次追蹤會顯示出這樣的報文段序號/到達時間間隔序列：1/316.7ms，2/1.6，3/220，4/1.6，5/1.6，6。這個序列表明傳

23、送1個報文段之后會有一個RTT的延遲（外加由推遲確認計時器導致的另外100ms的延遲），傳送2個背對背報文段之后會有一個RTT的延遲，然后傳送3個背對背報文段，這就轉化成了FSA頂上那一排狀態。當我們在丟失了第三個包的情況下重復這一試驗時，我們看到這樣的序列：1/316.7ms，2/1.6，3/316.7，4/1.6，5/898.4，3。 我們再一次看到1個報文段與一個RTT的延遲（外加推遲確認導致的延遲），然后是2個報文段與一個RTT的延遲（外加推遲確認導致的延遲），在丟失的報文段被重傳之前又發送了2個報文段并且發生了一次超時。在圖1右一中，這表現為：從左上角的節點開始，向右移動，然后順著細

24、線向下，然后順著粗線向下。根據經驗法則，我們把到達時間間隔少于50%的情況看作背對背包，到達時間間隔超過200%時看作重傳，但是這種方法并不區分推遲確認定時器的影響。如上所述，這種方法與基于仿真的典型的協議研究是不同的，那些典型研究只探查隨機的或者指定的配置，而且通常只考慮TCP行為的統計摘要。利用這種方法，我們建立了多個TCP FSA模型，在這些模型中有的模擬Tahoe TCP，有的模擬Reno TCP譯注8，有的模擬發送方，有的模擬接收方，有的采用推遲確認機制，有的不采用。我們采用了ns-2譯注9的單路TCP實現，在每個數據流丟失0個或1個包且每個數據流最多傳送31個報文段的前提下探查了狀

25、態空間。15中的圖2和圖3顯示了最終得到的FSA模型。這兩個圖和圖1右一很類似（線條代表RTO或RTT延遲，圓中的數字代表該回合發送了多少報文段，向下的線條顯示出第i個報文段在該回合內丟失）。 另外，靠近某些節點的括號中的數字表示在發生一次丟失之后的cwnd與ssthresh值。盡管這種追蹤是自動生成的，但是對追蹤結果的分析卻是徒手進行的。這一過程的自動化實現并不困難，而且將有助于更深入地探查狀態空間，同時還有助于探查其他的TCP變異版本。我們可以再現一個TCP連接的進行過程，這只需要從圖中左上角標有“1”的狀態開始，對剩余的待發報文段的數量進行持續追蹤即可。如果這一回合中沒有丟失報文段，那么

26、就可以在一個RTT的延遲之后向右移向標有“2”的狀態。如果在整個連接期間都沒有丟失包，那么這個FSA TCP連接將一直向右平移，直到全部的報文段被發送完畢。然而，如果有一個報文段被丟棄，那么FSA TCP連接將沿著那條對應于這個被丟棄的包的線向下移動（可能是這一回合傳送的第1個、第2個或第n個包）。從節點邊上括號中的那兩個數字可以看出Reno TCP和Tahoe TCP調整其慢啟動閥值的方法相同，而這兩者減小其擁塞窗口大小的方法卻略有不同。當由于重復確認而導致的包重傳發生時，Reno TCP把擁塞窗口的大小減小到當前窗口大小的一半。而Tahoe TCP總是把擁塞窗口的大小減至1。四、為網絡仿真

27、產生后臺傳輸量我們的TCP FSA模型的一種應用就是對TCP進行輕量級仿真，這就可以產生大量類似于萬維網的后臺傳輸量，以便供網絡仿真使用。我們的方法就是把FSA模型轉化成一個抽象版的TCP。下文將說明我們的方法可以大大減少多數據流仿真中的內存消耗，同時又可以保持在很大時間尺度范圍內的仿真精確性。4.1 構造輕量級TCP代理我們已經在ns-2模擬器中實現了我們的FSA TCP代理4。 我們實現的FSA驅動TCP協議模擬器由若干部分組成。我們直接用一套C+數據結構實現了TCP FSA模型的狀態。各個活動的FSA TCP連接都在FSA中保留一個指針，用來表明它在這個狀態機中的位置、剩余的待發報文段的

28、數量和RTT的近似值。FSA TCP代理向該模擬器發送規則的包；我們對這些包所消耗的內存大小做了一定的優化。當這些包中有一個包被丟棄（因為路由器隊列溢出或者包損壞），對應的FSA TCP代理將直接得到通知。FSA模擬器的實現與該模型的一個重要差異就在于我們處理違背了模型限制的情形的方法不同。在模擬器中我們可以檢測到違背限制的情形（例如，一個數據流中丟失了兩個包），并且會產生一個抽象錯誤。為了從錯誤中恢復，我們用一個常規的（即充分詳細的）TCP代理來替代我們的抽象FSA TCP代理。我們不能重新生成全部的TCP狀態（例如，RTT估計值的準確細節），但是我們可以保存cwnd和ssthresh的值。

29、由于有了這種求助于一個更詳細的TCP實現的能力，我們就能夠在限制了模型規模的前提下對TCP行為進行精確仿真。4.2 每一數據流的單個包丟失我們現在實現的FSA TCP考慮了每個數據流最多只發生一次丟失的情形。這個限制是因為我們創造的狀態機現在只是半自動的。假設包丟失的概率是獨立同分布的，我們可以對我們的模型不能涵蓋某一給定數據流的概率進行量化，這只需要對FSA中所有穿越了2條（或更多）丟包路徑的路徑求和即可。這可以簡化為：其中p是一個報文段丟失的概率，n是待發的報文段數量。（直觀地看，這就是每種連接長度下，我們丟失了2個報文段并且正確發送了其他報文段的概率。）圖2顯示了該方程對各種誤差率的計算

30、結果。該圖確定了我們預期在仿真中產生多少抽象錯誤。當丟包率超出我們假定范圍不太多（少于2%）時，模型失效的概率是相當低的，但是對于更高的丟包率和更長的連接來說，要精確地建模就必須能夠處理至少每數據流丟失2個包的情況。圖2：單包丟失模型失效的概率是連接長度的函數，對于帶有推遲確認機制的Reno TCP協議而言，這個概率也隨著p取值譯注10的不同而變化。（由方程1計算得到）圖3：用于評估FSA TCP仿真的一個類似于ISP的拓撲結構。420個客戶（左）通過快速接入媒體與40個服務器（右）進行連接。4.3 試驗方法論我們用一種通常的情形來評估FSA TCP的性能（內存開銷與執行時間）及其精確性。我們

31、使用了一個類似于ISP的拓撲結構（圖3）譯注11，這個結構和Feldmann等人先前用于伸縮分析9的結構很相似。為了表明FSA TCP的伸縮性，我們在10個萬維網會話到100個萬維網會話的范圍內連續改變TCP連接數，每個會話大約包含200個TCP連接。這些TCP連接的到達時刻服從泊松隨機分布，連接長度服從帕累托分布譯注12，均值為10KB，伸縮系數（alpha）為1.2。為了進行這一組FSA TCP仿真，我們用FSA TCP替換了那些小于等于31KB的TCP連接，其他較長的連接用原先的TCP實現來處理。所有仿真運行在詳細交付模式下，在4200秒仿真時間（比一小時略長）后停止。我們使用了一臺Pe

32、ntium II 450MHz機器，物理內存為1GB，運行FreeBSD 3.0和我們修改過的ns-2.1b5。4.4 仿真性能圖4計算了我們的FSA TCP在內存和時間開銷方面的性能，并與模擬器中常規的（詳細的）TCP做了比較。圖4中的每一個點都是一次仿真的結果。仿真結果是確定的，用同樣的隨機種子重復運行就一定會產生同樣的結果，因此我們并未給出置信區間。圖4：FSA TCP仿真的內存和時間開銷。圖5：FSA TCP引起的失真：吞吐量譯注13差異（用百分比表示）和延遲差異。圖4的左圖表明FSA TCP較之詳細的TCP而言，內存利用率顯著提高。創建的TCP連接越多，FSA TCP節省的內存就越多

33、。這也說明對涉及數以百計的并發TCP連接的仿真試驗來說，TCP狀態的總開銷占了內存開銷的一大部分。（ns 2.1b6版所作的優化可能改變這一差異；我們還未在該平臺下進行此實驗。）FSA TCP對大量的細節作了抽象，只需要很少的狀態，實質上只需要在FSA中保存一個指向當前狀態的指針和一個記錄RTT的浮點數。在圖4右圖中，可以看出FSA TCP在運行時間開銷方面并沒有太大改進。這是因為仿真時間與事件調度表的大小成正比（除非物理內存耗盡），而調度表的大小是由各時刻預定的事件或包的數量決定的。現在，如FSA圖所示，我們在ns-2中實現的FSA TCP可以準確地產生指定數量的單個的包。這樣，對詳細的TC

34、P和FSA TCP來說預定的事件或包的數量是一樣多的，因此我們在仿真運行時間方面沒有多大改進。我們正在考慮對FSA TCP進行一項優化，即按照Ahn與Danzig的建議2，用一個代表性的包事件來代表各回合的所有包。這種方法能夠避免對單個的包進行調度，從而可以極大地減小事件隊列的規模并加快仿真的運行速度。4.5 獨立數據流的失真抽象技術帶來的一個風險就是它可能導致仿真中的失真和誤差。FSA TCP并未實現詳細的TCP中那種RTT估計機制，而且它也不模擬由ACK定時引發的獨立包與ACK之間的間隔。這將導致延遲上的差異，進而導致那些與延遲相關的度量標準的差異。為了給這些差異定量，我們測量了連接吞吐量

35、和出于瓶頸隊列中的各個包的排隊延遲。對不同數量的連接，我們都運行了兩次相同的仿真。一次采用FSA TCP，另一次采用詳細的TCP。我們計算了各個連接的吞吐量差異比率和瓶頸隊列排隊延遲的絕對差。圖5的左圖表明FSA TCP的吞吐量與詳細的TCP相差大約3%，而且這種失真基本上不受傳輸量的影響。圖5右圖表明FSA TCP中（處于瓶頸隊列中的）每個包的延遲與詳細的TCP相差約10-20ms，換言之就是在RTT為140-400ms的網絡中相差5-14%。 這些結果說明FSA TCP可以用于為只要求較粗粒度精確性（粒度達到數百毫秒或按RTT計算）的場合生成后臺傳輸量。然而我們應該避免在捕獲細粒度時間尺度

36、（粒度低于10ms或按包計算）下的TCP行為時使用FSA TCP。4.6 合計傳輸量中的失真我們在TCP仿真中采用FSA近似法的主要目標就是利用有限的資源來模擬大量的后臺傳輸量。為了計算FSA在這一方面的效能，我們必須了解4.5節所述的失真現象是如何出現在合計傳輸量中的。我們將說明這些失真帶來的的影響并不發生相互作用（潛在地有可能相互放大），而且在中、長時間尺度下（即長于10ms），這些影響是難以察覺的。我們采用了小波分析方法8，9來評估FSA TCP合計傳輸量的伸縮行為。在這一節中，我們首先簡要描述小波分析及其產生的定標圖的解釋方法。然后，我們將用這一工具來比較FSA合計傳輸量和詳細的TCP

37、的傳輸量。小波分析我們利用一個時間序列的小波變換來研究傳輸中的全局伸縮性質。特別地，我們檢驗了每一追蹤尺度內包含的平均能量，并且研究了當我們由較粗尺度移向較細尺度時這個數值會如何變化。在j尺度下的平均能量是小波系數平方（即）的和；例如：其中是j尺度下系數的個數。為了確定數據的全局伸縮性質，我們在圖6中把繪制成尺度j的一個函數，j沿最粗尺度向最細尺度展開；我們也定性地確定了在什么尺度范圍內與尺度j之間存在線性關系；換而言之，就是在什么樣的時間尺度范圍內存在自相似伸縮性（詳見1）。對一個精確的自相似追蹤加入某一特殊的時間尺度的周期后就會出現一個傾角；這就是說，在這個時間尺度內存在一個更高頻率的包到

38、達時間間隔。當我們在實況網絡追蹤中應用這種全局伸縮分析方法時，我們經常觀察到在大時間尺度下存在一種線性關系模式，在RTT尺度下存在一個傾角。在圖6中，底軸是尺度j，作為參考我們把j對應的時間標在頂軸上（以秒計）。圖6：詳細的TCP和FSA TCP的全局伸縮性的比較。（圖中有兩條線，但彼此重合。）對FSA TCP進行小波分析我們運行了我們的類似于ISP的方案腳本，同時在連接較短時盡可能地采用了FSA TCP。 我們對從瓶頸鏈路上采集到的包的追蹤紀錄進行分解，從而得到了10ms時間序列。在對這一時間序列進行小波分析之后，我們得到了圖6所示的全局伸縮圖。圖中有兩條線，一條是詳細的TCP傳輸量，另一條

39、是FSA TCP傳輸量，這兩條線在所有時間尺度下都重疊。這表明我們的FSA TCP可以很好地保持合計傳輸量中的自相似性和小時間尺度下的不規則行為。這證明FSA TCP抽象可以在大于10ms的時間尺度下精確地模仿后臺傳輸。包一級的網絡數據傳輸具有自相似或分形的特性，在細時間尺度下有非平凡的伸縮行為。Feldmann等人提出：引起小時間尺度下的非平凡伸縮行為的原因就是TCP的閉環控制9。由于FSA TCP可以精確地再現具體的行為，人們可能產生這樣的直覺：它能捕獲中、粗粒度下的TCP閉環控制的效果，而且當連接過長或發生多個包丟失時我們能夠產生一個抽象錯誤，并且用完全詳細的表示方法來代替FSA TCP

40、。五、結論與展望我們已經描述了如何生成一個基于TCP包交換行為抽象的TCP FSA表示。我們也說明了如何生成一個TCP狀態的抽象FSA表示，以便在仿真中產生后臺傳輸量；以及如何在抽象模型和詳細模型間做出必要的選擇，以便優化內存利用率并提高精確性。我們證明：對后臺傳輸量的FSA TCP仿真可以產生和詳細的TCP仿真相同的結果。這些結果都表明FSA模型可以在中、粗時間尺度下捕獲TCP的關鍵特性，即這一模型有其適用的領域。顯然，未來的工作將包含以下若干方面：首先，我們會使FSA的創建過程完全自動化。我們已經能夠對各個丟包情形進行自動追蹤，而對這些追蹤的分析也將可以自動完成。這將使我們能夠更輕易地探查

41、每一連接的多包丟失和猝發丟失，以及推遲確認機制如何影響性能的具體細節。其次，我們也會探查其他的TCP變異版本。利用這些工具與帶有選擇性應答機制的TCP版本譯注14做出比較將是很有趣的。最后，我們在4.4節提出：若能以單個對象來表示多個背對背包，那么FSA TCP仿真的運行時間性能就可以得到提高。對此，我們也將作進一步研究。致謝我們要感謝Sally Floyd，他在對TCP性能的討論中提出了用窮舉狀態探查法進行分析的思想。我們要感謝Deborah Estrin為這些模型及其仿真應用做出的技術貢獻，同時還要感謝Vishwesh Kulkarni，他參與了這一工作的初期討論。我們還要感謝Ted Fa

42、ber、George Fankhauser、Ulrich Fiedler和Lukas Ruf，他們仔細審閱了這篇論文。譯注：1： 黃寶儀，女，1999年在南加州大學取得計算機科學博士學位，隨后在瑞士聯邦科技研究所做博士后工作，現任臺灣大學電子工程系助理教授。2： John Heideman，1995年在南加州大學取得計算機科學博士學位，后任南加州大學信息科學研究所助理教授，曾擔任黃寶儀的指導教師。3： burstiness，又譯偶發性、叢發性，指網絡傳輸量的不均衡現象。4： back-to-back packet，指以物理媒體所允許的最小間隔連續發送的包，具體定義見RFC 1242。5： he

43、avy-tailed distribution，重尾分布，若一隨機變量X滿足重尾分布，則P X>xx-a，當x時，0<a<2。在這種分布中，當a減小時，大量的概率質量集中在分布的尾部。6： power-law，冪次法則，描述了個體的規模與名次之間存在的冪次反比關系：R(x)=ax-b。其中x為規模，R(x)為名次，a為系數，b為冪次。7： aggregated TCP traffic，TCP合計傳輸量，指的是包括新數據包、重傳數據包和丟失數據包在內的傳輸量的總和。8： 目前TCP協議主要包含有四個版本：TCP Tahoe、TCP Reno、TCP NewReno和TCP SA

44、CK。TCP Tahoe是早期的TCP版本，它包括了3個最基本的擁塞控制算法：“慢啟動”、“擁塞避免”和“快速重傳”。TCP Reno在TCP Tahoe基礎上增加了“快速恢復”算法。TCP NewReno對TCP Reno中的“快速恢復”算法進行了修正。TCP SACK避免了之前版本的TCP重傳一個窗口內所有數據包的情況，只重傳那些被丟棄的數據包。另外，還有一種未被大規模使用的版本：TCP Vegas，它通過觀察TCP連接中RTT值改變感知網絡是否發生擁塞，從而控制擁塞窗口大小。9： ns-2，一種面向對象的、離散事件驅動的網絡環境模擬器，由UC Berkeley分校開發，可以模擬各種IP網

45、絡。它通過“代理”（agent）對象來模擬各種協議，用戶可以自行實現某些協議的代理；通過“追蹤”（trace）對象來記錄出隊、入隊、丟棄、接收事件。10：原文作“q的取值”，應為筆誤，故改作“p的取值”。11：原文作“（圖2）”，應為筆誤，故改作“（圖3）”。12：Pareto，帕累托分布，最簡單的一種重尾分布，其密度函數為p(x)=akax-a-1，a，k>0,x>=k，分布函數為F (x)=P X=<x=1-(k/x) a。13：throughput，吞吐量，指的是在不發生丟失的情況下所能達到的最高速率，具體定義見RFC 1242。14：即SACK TCP。參考書目：1

46、P. Abry and D. Veitch. Wavelet analysis of long-range dependenttraffic. IEEE Transactions on Information Theory, 44:2-15, 1998.2 J. Ahn and P. B. Danzig. Speedup vs. simulation granularity. IEEE/ACM Transactions on Networking, 4(5):743-757, October 1996.3 R. Braden. Requirements for Internet hosts-c

47、ommunication layers.RFC 1122, Internet Request For Comments, October 1989.4 L. 4 Breslau, D. Estrin, K. Fall, S. Floyd, A. Helmy, J. Heidemann, P. Huang, S. McCanne, K. Varadhan, H. Yu, Y. Xu, and VINT Project. Advances in network simulation. IEEE Computer, 33(5):59-67, May 2000.5 M. Christiansen, K

48、. Jeffay, D. Ott, and F. D. Smith. Tuning red forweb traffic. In Proceedings of the ACM SIGCOMM, pages 139-150, Stockholm, Sweden, August 2000.6 K. Claffy, G. Miller, and K. Thompson. The nature of the beast: Recent traffic measurements from an Internet backbone. In Proc. of the INET '98, July 1

49、998.7 C. R. Cunha, A. Bestavros, and M. E. Crovella. Characteristics of WWWClient-based Traces. Technical Report BU-CS-95-010, Computer Science Department, Boston University, July 1995.8 A. Feldmann, A. Gilbert, and W. Willinger. Data networks as cascades: Explaining the multifractal nature of inter

50、net wan traffic. In Proceedings of the ACM SIGCOMM, pages 42-55, Vancouver, Canada, September 1998. ACM.9 A. Feldmann, A. C. Gilbert, P. Huang, and W. Willinger. Dynamics of IP traffic: A study of the role of variability and the impact of control. In Proceedings of the ACM SIGCOMM, pages 301-313, Ca

51、mbridge, MA, August 1999. ACM.10 S. Floyd. Connections with multiple congested gateways in packetswitched networks part 1: One-way traffic. ACM Computer Communication Review, 21(5):30-47, October 1991.11 S. Floyd and K. Fall. Promoting the use of end-to-end congestion control in the internet. ACM/IE

52、EE Transactions on Networking, 7(4):458-473, August 1999.12 S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1(4):397-413, Sept 1993.13 John Heidemann, Katia Obraczka, and Joe Touch. Modeling the performance of HTTP over several

53、 transport protocols. ACM/IEEE Transactions on Networking, 5(5):616-630, October 1997.14 Ahmed Helmy, Deborah Estrin, and Sandep Gupta. Fault-oriented test generation for multicast routing protocol design. In Proceedings of the Formal Description Techniques & Protocol Specification, Testing, and

54、 Verification (FORTE/PSTV), pages 93-109, Paris, France, November 1998. IFIP.15 P. Huang and J. Heidemann. Capturing TCP Burstiness for Lightweight Simulation. Technical Report TIK-Nr.92, Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology, Zurich, 2000.16 V. Jacobson

55、 and R.T. Braden. TCP extensions for long-delay paths. RFC 1072, Internet Request For Comments, October 1988.17 Van Jacobson. Congestion avoidance and control. In Proceedings of the SIGCOMM '88, pages 314-329, Stanford, California, August 1988. ACM.18 Van Jacobson. Berkeley TCP evolution from 4.3-Tahoe to 4.3-Reno. In Proceedings of the 18th Internet Engineering Task Force, pages 363-376, Vancouver, Canada, July 1990. Talk slides and notes.19 T.V. Laks