錢亞冠，王 濱，關曉惠

（1.浙江科技學院理學院 杭州310023；2.浙江大學計算機學院 杭州310027；3.浙江水利水電?？茖W校計算機系 杭州310018）

1 引言

隨著Internet的快速發(fā)展，大規(guī)模分布式應用出現在互聯網上，如P2P、Grid等，這些應用協(xié)議在正式部署前需要在大規(guī)模網絡模擬環(huán)境下測試，驗證在各種動態(tài)條件下的正確性和容錯性。對于路由協(xié)議，同樣需要在大規(guī)模環(huán)境下測試其路由性能。大規(guī)模網絡模擬面臨的一個重大挑戰(zhàn)是對計算資源的巨大消耗，不僅需要大量的CPU時間，而且對主存容量也提出了極大的挑戰(zhàn)。解決這個問題通常采用并行化和模型抽象，本文正是采用模型抽象的方式解決大規(guī)模網絡模擬下的背景流量建模問題。

[1]統(tǒng)計了2004-2007年在SIGCOMM、SOSP/OSDI和NSDI上發(fā)表的論文，發(fā)現25.6%的論文在其模擬實驗中沒有采用背景流量。根據參考文獻[1]的研究，真實的背景流量對應用和協(xié)議行為產生的影響遠超過簡單的流量模型，因此建立真實的背景流量模型對于實驗的驗證和可信度具有重要意義。由于Internet廣泛使用TCP協(xié)議，傳輸層流量明顯受網絡擁塞的影響，因此采用tracedriven的方法建立的流量模型不具有普遍意義[2]。為此，采用簡單的ON/OFF模型[3～5]在應用層建立背景流量模型，但Vishwanath K V[1]也指出，合理的背景流量必須同時具有真實性和響應性，能對前景流量的變化作出反饋響應。因此，在傳輸層建立采用fluid表示的微分方程模型表示這種反饋機制。為了降低時空復雜度，采用fluid[6,7]的概念對流量進行抽象。fluid流量表示與packet表示的區(qū)別在于，前者將連續(xù)的突發(fā)包看成一個整體，由此帶來的好處就是大大降低模擬事件的數量和存儲開銷，缺點是降低了模擬精度，但實驗者一般不關心背景流量的包級行為。因此選用fluid表示背景流量是合適的。

以往的流量模型，主要集中在單一的packet級或fluid級模擬，缺少綜合用戶行為和網絡動態(tài)特征的表達。本文的主要貢獻是提出了運用結構化的方式建立背景流量模型，即在應用層建立用戶的行為模型，在傳輸層建立帶擁塞反饋的流模型。這種模型的優(yōu)點是既體現了應用層的用戶特征，又反映了流量模型對網絡擁塞的反饋機制，同時兼顧了真實性和模擬效率。

2 相關工作

流量模型從驅動方式上可分為兩類。一類是通過數學方法合成流量，試圖解析自相似或長相關特征（LRD）的形成機理，典型的模型有分形布朗運動 （FBM）[8]、F-ARIMA過程[9]、MMP[10]、ON/OFF 過程[3]，但 FBM 等模型的條件假設過于理想，目前能對LRD合理解析的是ON/OFF過程。另一類是根據測量數據生成流量，最簡單的方法是重新將這些數據包按序發(fā)送一次，但這種簡單方式并不能反映網絡的普遍特征，而只反映數據采集時刻的網絡狀況[2]，更普遍的方法是對測量數據進行統(tǒng)計分析，獲得流量的統(tǒng)計特征，再合成流量，如 Harpoon[11]、Tmix[12]、Swing[13]。

流量模型從控制方式上可分為開環(huán)和閉環(huán)兩類。所謂開環(huán)，就是沒有流控機制；而閉環(huán)，其發(fā)送速率會根據網絡的擁塞程度調整。目前大多數模型并沒有考慮反饋機制。Swing是考慮了反饋機制的流量模型，但其屬于包級模型，不適合作為大規(guī)模的背景流量模型。

流量模型從模擬粒度上又可分為基于包級和基于fluid?；趂luid的模型在模擬效率上要優(yōu)于包級，但由于抽象了一些特征，使得模擬精度下降。為了獲得fluid模型和包級模型的交互能力，通常采用微分方程表達fluid模型在TCP上的流控和擁塞避免行為，從而使其具有對網絡動態(tài)性的響應能力。盡管fluid模型很適合大規(guī)模的背景流量發(fā)生器，但目前只局限在對TCP層的行為模擬，并沒有考慮應用層的用戶行為特征。

3 背景流量模型

本文提出的模型是將流量的產生機制分多個尺度（session、flow、fluid）構建，分別表達獨立于網絡條件的用戶行為特征和對網絡動態(tài)變化敏感的傳輸層響應機制，盡可能地接近流量源產生流量的結構化機理。模型框架如圖1所示。

為了滿足大規(guī)模網絡模擬的需要，建立這個背景流量模型的目標如下。

·簡單，計算復雜度低。選擇簡單的ON/OFF模型作為流量源模型，用流體作為抽象級的流量表示。作為背景流量的源節(jié)點，簡化其協(xié)議棧，只保留應用層和傳輸層，通過靜態(tài)路由簡化掉網絡層。

·在用戶端建立多類型的流量源，盡可能反映網絡的真實情況，尤其是流量的突發(fā)特征。為此，提出長流（P2P）和短流（Web）組合、TCP 流和 UDP 流并存的方式，在多個層次上建立模型，分別反映用戶的行為特征和網絡的動態(tài)特征。

·具有自適應帶反饋控制的速率調整機制。Vishwanath[13]等研究發(fā)現，如果流量模型不具有對網絡動態(tài)變化的響應能力，那么相關的實驗結果與真實情況就很難相符。

3.1 ON/OFF模型

ON/OFF模型是一種表示流量源的兩狀態(tài)模型，該模型將激活狀態(tài)持續(xù)階段稱為ON周期，而將空閑狀態(tài)持續(xù)階段稱為OFF周期。大量獨立的ON/OFF信源(ON周期服從重尾分布)在流量匯聚后形成了自相似性[4]。多分辨率下的ON/OFF過程如圖2所示，其作為一種基于用戶行為模擬的產生方法，適合模擬實際環(huán)境中的自相似業(yè)務流量。

3.1.1 Web類型的ON/OFF流量模型

Web用戶產生流量的行為過程為：點擊超鏈接和思考這兩個過程交替進行，分別映射應用層的ON階段和OFF階段；點擊超鏈接后會產生一個新的session，一個session至少包含一個TCP flow，當session結束后，進入下一個思考階段（OFF階段）。在TCP flow層面，又構成自己的ON/OFF過程。根據參考文獻[14]和[15]的研究結論，對Session長度的分布、到達過程、TCP flow長度的分布等作出合理假設。

session：連續(xù)的session之間是獨立不相關的，即session到達過程服從Poisson分布，session長度服從Pareto分布，每個session中包含的TCP Flow個數服從Possion隨機分布。

TCP flow：flow長度分布特征是大量的短流（mice flow，≤10 KB）、少量的大流（elephant flow，≥5 MB），采用混合的Pareto和Weibull分布：

式（1）中的參數 α1、α2、α3分別取 0.38、1.05、2.35；參數β1、β2、β3分別取 2.7、3、200。

flow的到達間隔 （inter-arrival time，IAT）采用分段Weibull分布：

式（2）中的參數 α1、α2分別取 0.76、0.15；參數 β1、β2分別取 0.01、3×10-5。

flow的持續(xù)時間服從分段Pareto分布：

式（3）中的參數 α1、α2分別取 0.43、1.5；參數 β1、β2分別取 0.1、10。

3.1.2 P2P類型的ON/OFF流量模型

P2P應用是典型的Internet范圍內的分布式文件共享系統(tǒng)，P2P區(qū)別于Web的重要特征是：主機系統(tǒng)同時充當內容提供者和消費者。

目前P2P應用的流量已經超過Web流量[14]。根據參考文獻[14]的測量發(fā)現，P2P流同時存在很多細小流和巨量流，流的持續(xù)長度和流之間的間隔呈重尾分布。因此在flow這一級別采用混合的Weibull-Pareto分布：

式（4）中的參數 α1、α2、α3分別取 0.81、0.35、1.42；參數β1、β2、β3分別取 1.36、0.005、400。

flow的到達間隔采用混合的Weibull-Pareto分布：

式（5）中的參數 α1、α2、α3分別取 0.87、0.65、0.97；參數β1、β2、β3分別取 0.35、0.45、0.18。

flow的持續(xù)時間服從混合的Weibull-Pareto分布：

式（6）中的參數 α1、α2、α3分別取 0.35、0.55、1.53；參數β1、β2、β3分別取 88.3、57.2、1.53。

3.2 fluid表示

將連續(xù)的突發(fā)數據包看成一個整體，并假設該整體內的所有數據包速率相同，這樣表示的flow稱為fluid flow[3]。假設fluid flow在緩沖隊列中按FIFO方式獲得服務。隊列中匯聚速率恒定部分稱為fluid chunk，通常在隊列中會有多個fluid chunk。隊列中的fluid和fluid chunk如圖3所示。當匯聚流量速率大于服務速率時，就會在隊列中產生滯留量，并會改變各個fluid flow的離開速率。網絡模擬器只跟蹤fluid flow的速率變化，并產生相應的事件，這樣就可避免對數據包的跟蹤，從而大大減少事件數，提高模擬效率。

圖3 隊列中的fluid和fluid chunk

3.2.1 擁塞避免的微分方程模型

發(fā)送端對網絡動態(tài)變化的響應是通過TCP協(xié)議的擁塞避免算法實現發(fā)送速率的調整，對流量采用fluid的表示形式就是跟蹤flow速率的變化，而這種變化正是由于網絡擁塞引起的。因此，首先采用微分方程為TCP擁塞避免算法建立模型：

在 t時 刻 ，TCPflowi：Wi(t)表示擁塞窗口（congestion window）的大小，Ri(t)表示往返時延，λi(t)表示丟包率。表示算法的加性增加部分，而表示算法的乘性減少部分。式（7）是TCP協(xié)議對網絡擁塞狀況的響應行為，由此可對發(fā)送速率作出調整：Ai=Wi/Ri。這里假設接收窗口無限大，發(fā)送速率僅受沖突窗口的影響。

3.2.2 背景流與前景流的交互

前景流量與背景流量之間的互相影響是通過在交換節(jié)點的緩沖隊列中競爭帶寬引起的。這種競爭會導致過隊列長度、丟包率等參數的變化，可以為前景流量提供排隊信息。為t時刻隊列l(wèi)建立如下的微分方程模型：

其中，ql(t)為 t時刻的隊列長度為背景流和前景流的速率總和，pl(t)為丟包概率，由具體的服務策略決定，Cl為隊列的服務速率（帶寬）。

用微分方程表示的fluid表示的背景流，可以通過固定時間步長，用Runge-Kutta法求解，但前景流量一般為離散事件模擬，并沒有固定的時間步長。為了保持兩者隊列變化信息的一致性，采用參考文獻[16]提出的影子變量方法，即在fluid的固定時間步長之間保存最近的包事件對隊列的改變信息。

3.3 模型實現

通過 DaSSFNet[17]提供的 API實現了fluid和 packet混合模型。DaSSFNet是用C++實現的一個模擬引擎，提供了如 下 的 核 心 類 ：Entity、Process、Input、Output、Link、Event。利用這些類，可以進一步構造網絡元素，如Host、Router、Linker等。模擬過程并沒有真實的數據包產生，而是一系列模擬事件，如包發(fā)送事件、包接收事件等。對于fluid表示的流量，是將多個連續(xù)的數據包看成整體產生事件的。為了產生一定分布的fluid，按升序定義了兩個向量，每個向量元素代表一個Web文件或P2P文件的大小，通過產生滿足§3.1定義的隨機數選擇fluid的流量持續(xù)時間。

4 實驗分析

4.1 實驗建立

硬件平臺為 Intel Core2，1.66 GHz，1 GB 內存，操作系統(tǒng)為Linux Fedora2,Kernel 2.6.29。實驗拓撲采用典型的啞鈴型拓撲，如圖4所示，包含兩個路由器，路由器之間的鏈路bottleneck帶寬為 10 Mbit/s，鏈路時延 5 ms，路由器緩沖隊列容量500 KB，采用FIFO的服務策略。

4.2 自相似分析

隨著網絡測量研究的不斷深入，大量文獻證明從LAN[18]到WAN[19]，網絡流量呈現自相似或分形特征。通過R/S方法估計表征自相似度的Hurst參數[18]。具有自相似特征的時間序列，其Hurst參數的范圍為1/2

20個ON/OFF源匯聚后在不同時間尺度的H參數分別為 0.8415、0.8502、0.8521、0.7776。不同時間尺度下的流量和R/S圖如圖5所示，可以看出，當20個ON/OFF源聚合后，其自相關性是很明顯的。通過進一步測試不同數量的ON/OFF源會聚后的H參數變化，發(fā)現隨著源的數量的增加，H參數增大，也就意味著自相關程度的加強，但并不是線性增加，而是在某種程度上服從冪律分布，H參數的變化趨勢如圖6所示。這也進一步驗證了無限個ON/OFF源的匯聚趨向于長相關的理論，同時也說明5～20個ON/

OFF源的聚合已經能滿足實驗的需要。

4.3 與包級發(fā)生器的性能比較

不同的ON/OFF源數量在相同的模擬時間（取10 000 s）下測量CPU時間。fluid表示的模型CPU時間與ON/OFF源的數量基本呈線性關系遞增，且斜率非常小；而packet表示的模型CPU時間與ON/OFF源的數量基本呈指數關系遞增，如圖7所示。同樣，fluid表示的模型，其存儲消耗量與ON/OFF源的數量基本呈線性關系遞增，而packet表示的模型基本呈指數關系遞增，如圖8所示。由此可以得出一個結論，無論從實際模擬需要的時間看，還是從對存儲器的消耗看，包級流量生成模型是不適合作為背景流量發(fā)生器的。

5 結束語

本文提出的背景流量模型，主要針對大規(guī)模網絡模擬環(huán)境，不但適用于不需要考慮包級細節(jié)的分布式應用模擬，而且適用于需要考慮底層網絡細節(jié)的協(xié)議性能測試。為了實現這個目標，選擇了ON/OFF模型作為用戶層的行為建模，傳輸層采用fluid抽象表示模型，大大縮短了模擬執(zhí)行時間，節(jié)省了大量存儲空間。把這兩種模型結合在一起，不但能更好地描述流量的自相似特征，同時能對網絡動態(tài)變化作出速率調整，更加接近真實的網絡環(huán)境。通過實驗模擬，取得了比較好的效果，證實了最初的設想。將來進一步需要研究的問題是在分布式大規(guī)模環(huán)境下繼續(xù)驗證結論，同時對如何使背景流量快速收斂到穩(wěn)定狀態(tài)的問題作進一步的研究。

參考文獻

1 Vishwanath K V,Vahdat A.Evaluating distributed systems:does background traffic matter. In: Proc USENIX Technical Conference,2008

2 Floyd S,Paxson V.Difficulties in simulating the Internet.IEEE/ACM Trans on Networking,2001,9(4):392～403

3 Jong Suk Ahn,Peter B Danzig.Packet network simulation:Speed up and accuracy versus timing granularity.IEEE/ACM Transactions on Networking,1996,4(5):743～757

4 WalterWillinger,Murad S Taqqu，RobertSherman.Selfsimilarity through high-variability：statistical analysis of ethernet LAN traffic at the source level.IEEE/ACM Transactions on Networking,1997,5(1):71～86

5 Taqqu M S,Willinger W,Sherman R.Proof of a fundamental result in self-similar traffic modeling.Computer Communications Review,1997

6 Liu Y,Presti F L,Misra V,et al.Fluid models and solutions for large-IP networks.In:Proc ACM/SIGMETRICS,2003

7 Liu Y.Scalable fluid models and simulations for large-scale IP networks.ACM Trans on Modeling and Computer Simulation(TOMACS),2004,14(3):305～324

8 Norros I.On the use of fractional brownian motion in the theory of connectionless networks.IEEE JSAC,1995,13(6):953～962

9 Jose C Lopez-Ardao,Candido Lopez-Garcia,Andres Suarez-Gonzalez.On the use ofself-similarprocessesin network simulation.ACM Trans on Modeling and Computer Simulation,2000,10(2):125～151

10 Clegg R G.Simulating Internet traffic with Markov-modulated processes.In:ProceedingsofUK Performance Engineering Workshop,2007

11 Sommers J,Barford P.Self-configuring network traffic generation.In:Proc IMC,2004

12 Weigle M C,Adurthi P,Hern F,et al.Tmix:a tool for generating realistic TCP application workloads in ns-2.CCR,2006,36(3):67～76

13 Vishwanath K V,Vahdat A.Realistic and responsive network traffic generation.In:Proc ACM SIGCOMM,2006

14 Basher N,Mahanti A,Mahanti A,et al.A comparative analysis of Web and peer-to-peer traffic.In:Proc WWW’08,Beijing,China,2008

15 Feldman A.Characteristics of TCP connection arrivals.J Wiley&Sons,2000

16 Liu J,Li Y.Parallel hybrid network traffic models.Transactions of the Society for Modeling and Simulation,2009,85(4):271～286

17 Liu J.Dartmouth S S F (2002),http://www.cs.dartmouth.edu/research/DaSSF/intro.html,2004

18 Leland W E,Taqqu M S,Willinger W,et al.On the self-similar nature of ethernet traffic (extended version).IEEE/ACM Trans on Networking,1994,2(1):1～15

19 Paxson V,Floyd S.Wide-area traffic:the failure of poisson modeling.IEEE/ACM Trans on Networking,1995,3(3):226～244