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

（1.浙江科技學(xué)院理學(xué)院 杭州310023；2.浙江大學(xué)計(jì)算機(jī)學(xué)院 杭州310027；3.浙江水利水電?？茖W(xué)校計(jì)算機(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)境下測(cè)試，驗(yàn)證在各種動(dòng)態(tài)條件下的正確性和容錯(cuò)性。對(duì)于路由協(xié)議，同樣需要在大規(guī)模環(huán)境下測(cè)試其路由性能。大規(guī)模網(wǎng)絡(luò)模擬面臨的一個(gè)重大挑戰(zhàn)是對(duì)計(jì)算資源的巨大消耗，不僅需要大量的CPU時(shí)間，而且對(duì)主存容量也提出了極大的挑戰(zhàn)。解決這個(gè)問(wèn)題通常采用并行化和模型抽象，本文正是采用模型抽象的方式解決大規(guī)模網(wǎng)絡(luò)模擬下的背景流量建模問(wèn)題。

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

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

2 相關(guān)工作

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

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

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

3 背景流量模型

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

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

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

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

·具有自適應(yīng)帶反饋控制的速率調(diào)整機(jī)制。Vishwanath[13]等研究發(fā)現(xiàn)，如果流量模型不具有對(duì)網(wǎng)絡(luò)動(dòng)態(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過(guò)程如圖2所示，其作為一種基于用戶行為模擬的產(chǎn)生方法，適合模擬實(shí)際環(huán)境中的自相似業(yè)務(wù)流量。

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

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

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

TCP flow：flow長(zhǎng)度分布特征是大量的短流（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ù)時(shí)間服從分段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)同時(shí)充當(dāng)內(nèi)容提供者和消費(fèi)者。

目前P2P應(yīng)用的流量已經(jīng)超過(guò)Web流量[14]。根據(jù)參考文獻(xiàn)[14]的測(cè)量發(fā)現(xiàn)，P2P流同時(shí)存在很多細(xì)小流和巨量流，流的持續(xù)長(zhǎng)度和流之間的間隔呈重尾分布。因此在flow這一級(jí)別采用混合的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ù)時(shí)間服從混合的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ù)包看成一個(gè)整體，并假設(shè)該整體內(nèi)的所有數(shù)據(jù)包速率相同，這樣表示的flow稱為fluid flow[3]。假設(shè)fluid flow在緩沖隊(duì)列中按FIFO方式獲得服務(wù)。隊(duì)列中匯聚速率恒定部分稱為fluid chunk，通常在隊(duì)列中會(huì)有多個(gè)fluid chunk。隊(duì)列中的fluid和fluid chunk如圖3所示。當(dāng)匯聚流量速率大于服務(wù)速率時(shí)，就會(huì)在隊(duì)列中產(chǎn)生滯留量，并會(huì)改變各個(gè)fluid flow的離開速率。網(wǎng)絡(luò)模擬器只跟蹤fluid flow的速率變化，并產(chǎn)生相應(yīng)的事件，這樣就可避免對(duì)數(shù)據(jù)包的跟蹤，從而大大減少事件數(shù)，提高模擬效率。

圖3 隊(duì)列中的fluid和fluid chunk

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

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

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

3.2.2 背景流與前景流的交互

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

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

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

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

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

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

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

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

4.2 自相似分析

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

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

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

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

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

5 結(jié)束語(yǔ)

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