大規(guī)模網(wǎng)絡(luò)模擬的背景流量建模*

錢亞冠，王 濱，關(guān)曉惠

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

3 背景流量模型

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

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

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

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

·具有自適應(yīng)帶反饋控制的速率調(diào)整機(jī)制。Vishwanath[13]等研究發(fā)現(xiàn)，如果流量模型不具有對網(wǎng)絡(luò)動態(tài)變化的響應(yīng)能力，那么相關(guān)的實(shí)驗(yàn)結(jié)果與真實(shí)情況就很難相符。

3.1 ON/OFF模型

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

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

Web用戶產(chǎn)生流量的行為過程為：點(diǎn)擊超鏈接和思考這兩個過程交替進(jìn)行，分別映射應(yīng)用層的ON階段和OFF階段；點(diǎn)擊超鏈接后會產(chǎn)生一個新的session，一個session至少包含一個TCP flow，當(dāng)session結(jié)束后，進(jìn)入下一個思考階段（OFF階段）。在TCP flow層面，又構(gòu)成自己的ON/OFF過程。根據(jù)參考文獻(xiàn)[14]和[15]的研究結(jié)論，對Session長度的分布、到達(dá)過程、TCP flow長度的分布等作出合理假設(shè)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 fluid表示

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

圖3 隊列中的fluid和fluid chunk

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

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

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

3.2.2 背景流與前景流的交互

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

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

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

3.3 模型實(shí)現(xiàn)

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)建立

硬件平臺為 Intel Core2，1.66 GHz，1 GB 內(nèi)存，操作系統(tǒng)為Linux Fedora2,Kernel 2.6.29。實(shí)驗(yàn)拓?fù)洳捎玫湫偷膯♀徯屯負(fù)?，如圖4所示，包含兩個路由器，路由器之間的鏈路bottleneck帶寬為 10 Mbit/s，鏈路時延 5 ms，路由器緩沖隊列容量500 KB，采用FIFO的服務(wù)策略。

4.2 自相似分析

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

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

OFF源的聚合已經(jīng)能滿足實(shí)驗(yàn)的需要。

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

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

5 結(jié)束語

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

參考文獻(xiàn)

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