彭行雄，肖如良

(1.福建師范大學(xué) 軟件學(xué)院，福州 350117； 2.福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心，福州 350117)

(*通信作者電子郵箱xiaoruliang@163.com)

基于穩(wěn)態(tài)過程的多重分形Web日志仿真生成算法

彭行雄1,2，肖如良1,2*

(1.福建師范大學(xué) 軟件學(xué)院，福州 350117； 2.福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心，福州 350117)

(*通信作者電子郵箱xiaoruliang@163.com)

運行在服務(wù)器集群的軟件系統(tǒng)需要Web日志的大規(guī)模數(shù)據(jù)集以滿足性能測試的需求，但現(xiàn)有仿真生成算法因模型單一而無法滿足要求。針對此問題，提出一種基于alpha穩(wěn)態(tài)過程的多分形Web日志的仿真生成算法。首先,在長相關(guān)尺度(LRD)下采用alpha穩(wěn)態(tài)過程來描述Web日志的自相似性；其次,在短相關(guān)尺度(RSD)下采用二項式b模型描述Web日志的多重分形性;最后,將長相關(guān)模型和短相關(guān)模型融合于改進的ON/OFF框架中。與單一的模型相比，新算法的參數(shù)物理意義明確，具有良好的自相似性和多分形性。實驗結(jié)果表明，該算法能夠較準確地模擬真實Web日志，可以有效地應(yīng)用于Web日志大規(guī)模數(shù)據(jù)集的仿真生成。

穩(wěn)態(tài)過程；多重分形；自相似；時間序列；日志分析；仿真生成

0 引言

在Web服務(wù)器性能測試中，分析Web日志特征對于服務(wù)器性能評測與決策有著重要意義。然而Web日志中包含用戶隱私信息，企業(yè)及政府等機構(gòu)極少愿意公開日志供研究人員使用；現(xiàn)有已公開的Web日志數(shù)據(jù)年代久遠，其特征不符合當(dāng)前大數(shù)據(jù)時代特征[1]。隨著數(shù)據(jù)規(guī)模的增大，生成有代表性卻不失一般性的大規(guī)模數(shù)據(jù)集是有困難的，而單一的傳統(tǒng)仿真模型很難表現(xiàn)出多種復(fù)雜Web日志一般性特征。如何生成仿真且一般性可控的Web日志大規(guī)模數(shù)據(jù)集，是學(xué)術(shù)界的熱點問題，也是本文研究的主題。

以O(shè)N/OFF模型[2]為代表的自相似模型，將自相似過程看成是無數(shù)用戶數(shù)據(jù)源采用獨立同分布形式疊加的結(jié)果，這種模型能對自相似現(xiàn)象給出明確的物理解釋，但是在構(gòu)造模型的過程中作了很多前提假設(shè)(如文件大小分布是重尾的[3]，那么訪問文件所需要的時間也是重尾的)，且這些前提假設(shè)條件常常與實際情況不相符合，這使得流疊加模型難以對實際流量進行仿真。隨著非線性動力學(xué)的發(fā)展，通過對Web日志序列的研究，發(fā)現(xiàn)其中含有豐富的非線性特性，因此逐漸開始采用計算智能的相關(guān)理論進行分析，其中以多分形小波模型(Multi-fractal Wavelet Model, MWM)[4]為代表的多重分形模型，通過將Web日志分為高頻和低頻，有效地揭示了突發(fā)性流量的局部較精細的本質(zhì)特征。但是這類方法建立在重構(gòu)相空間(Web日志模型的非線性特征量的提取及分析)的基礎(chǔ)上，預(yù)測結(jié)果受相空間形狀的影響，如果參數(shù)選取不合適，就有可能產(chǎn)生較大誤差。

針對以上問題，本文提出一種模型融合算法：基于穩(wěn)態(tài)過程的多重分形Web日志仿真生成算法(Multi-Fractal Web log simulation algorithm based on Stable process, MFWS)。MFWS將alpha穩(wěn)態(tài)模型與二項式b模型融合，不僅能夠更加準確地模擬Web日志的高斯性、非高斯性以及多分形性等特征，而且其參數(shù)的物理意義明確，能夠很好地應(yīng)用于不同Web服務(wù)器平臺。

1 相關(guān)工作

為了有效地仿真生成Web日志，已經(jīng)有很多相關(guān)的研究。當(dāng)前模擬生成的方法主要是自相似方法和多重分形方法，具體如下：

1)在自相似方法中，通過模擬突發(fā)性特征來生成Web日志。其中，被不少研究者采用的ON/OFF模型[2]結(jié)構(gòu)簡單，具有明確物理意義，構(gòu)造的每一個過程都能找到原型；然而在構(gòu)造過程中作了一定假設(shè)，與實際流量不符，而且還忽略了很多細節(jié)。分形布朗運動(Fractional Brownian Motion, FBM)[5]模型雖然易于處理，參數(shù)簡單，且能在高斯條件下描述自相似性，但是只適用于高斯分布情況，而且無法同時描述長相關(guān)尺度(Long Range Dependence, LRD)和短相關(guān)尺度(Short Range Dependence, SRD)[5]。M/G/∞排隊模型[6]能夠描述短相關(guān)性，但是需要在計算量和計算精度之間進行折中。分形自回歸滑動平均(Fractional Auto-Regressive Integrated Moving Average, FARIMA)模型[7]雖然靈活，能夠同時描述長相關(guān)性和短相關(guān)性，但過于復(fù)雜，仿真運算量太大，且對負載中的突發(fā)性缺乏表述。

2)在多重分形方法中，通過擴展單分形自相似過程來模擬小時間尺度的Web日志突發(fā)性特征。二項式b模型[8]首先用于存儲系統(tǒng)的流量仿真。它通過偏差參數(shù)b來描述局部突發(fā)行為，將單位時間內(nèi)的流量二項式分解來達到多分形的目的，有參數(shù)少、模型簡單的優(yōu)點。Hong等[9]推薦在一個相對較小的時間范圍用二項式b模型合成流量，雖然提高了模擬的精度，但是沒有在長時間范圍生成流量。MWM模型[4]基于多分形小波理論對流量信號進行多尺度特性分析，通過設(shè)定限制方式，巧妙地避免了仿真流量出現(xiàn)負值的問題；但是在構(gòu)造小波系數(shù)和尺度系數(shù)之間的隨意乘法因子時，沒有根據(jù)實際流量的概率密度特征進行分析，缺乏真實性，且難以調(diào)整。因此有研究者以一定規(guī)律來產(chǎn)生乘法因子，如文獻[10]提出一種改進的MWM方法，提出一個β模型來初始化乘法因子提高仿真性能，但參數(shù)物理意義不足。

在以上各項工作中，構(gòu)造模型的過程中采用最頻繁的分布規(guī)律為重尾分布中的Pareto規(guī)律來作為分布原型。然而，無法確認流量數(shù)據(jù)是否真的符合Pareto分布。文獻[11]指出隨著網(wǎng)絡(luò)媒體的多樣化、緩存技術(shù)的提升，廣延指數(shù)(StretchedExponential,SE)分布[11]能更加準確地描述Web日志特征，然而其參數(shù)卻不容易確定，而且沒有考慮流量的非高斯性。文獻[12]在用戶行為分形建模時發(fā)現(xiàn)Web日志符合alpha穩(wěn)態(tài)[13]，此外alpha穩(wěn)態(tài)包含4個參數(shù)，每個均有相應(yīng)的物理意義，這使得研究人員可以針對不同的應(yīng)用環(huán)境很方便地轉(zhuǎn)換流量模型。由于alpha穩(wěn)態(tài)只存在特征函數(shù)，卻沒有具體的分布函數(shù)，這為仿真帶來了困難。但是文獻[13]中采用逼近法模擬alpha穩(wěn)態(tài)得到了近似分布函數(shù)，這為alpha穩(wěn)態(tài)的使用帶來了方便。

綜上所述，自相似方法和多重分形方法各有優(yōu)缺點，本文借鑒這兩類方法的優(yōu)點，將流量序列分為長相關(guān)過程和短相關(guān)過程，考慮到Web日志的多樣性，選擇具有物理意義的模型進行構(gòu)造；其中長相關(guān)過程采用alpha穩(wěn)態(tài)來模擬Web日志自相似的高斯和非高斯特性，短相關(guān)過程采用二項式b模型來模擬Web日志的多重分形特征，在改進的ON/OFF模型的基礎(chǔ)上提出一種模型融合算法——MFWS，以此達到提高Web日志仿真性能的目標。

2 理論基礎(chǔ)

2.1 alpha穩(wěn)態(tài)

文獻[14]研究表明：對于不同的Web服務(wù)器，Web日志到達模型分為獨立同分布和自相似性兩種；而且，即使同樣具有自相似性，有的Web日志具有高斯性，而有的Web日志體現(xiàn)出非高斯性。于是文獻[14]發(fā)現(xiàn)用alpha穩(wěn)態(tài)來描述Web日志特征更加合理。之所以alpha穩(wěn)態(tài)具有準確的仿真性能，是因為相對于傳統(tǒng)方法使用的冪律分布，alpha穩(wěn)態(tài)更適合于描述Web日志。隨著對大量數(shù)據(jù)的調(diào)查[11]發(fā)現(xiàn)，所謂的冪律僅僅適用于分布曲線的尾端部分(x軸遠離原點位置)。另外文獻[15]中利用美國真實稅收情況估計出的收入分布曲線也表明：當(dāng)取雙對數(shù)坐標時，曲線尾端是直線，即冪律分布；當(dāng)取半對數(shù)(y軸為對數(shù))時，曲線頂端為直線，即指數(shù)分布。數(shù)學(xué)家Nolan[13]指出alpha穩(wěn)態(tài)分布正好具備這種尾端趨近于冪律分布，而在頭端(x軸靠近原點位置)偏離冪律、趨向于指數(shù)分布的性質(zhì)。即：一個隨機變量X被稱為具有穩(wěn)定分布，若存在參數(shù)0<α≤2，σ>0，-1≤β≤1，μ∈R，使得其特征函數(shù)E的形式如式(1)所示：

E[exp(iθX)]=

(1)

式中:sign(·)為符號函數(shù)。文獻[14]發(fā)現(xiàn)：α表示分布中的突發(fā)程度，β表示分布的尾部變化情況。如果β≠0，說明alpha穩(wěn)態(tài)的波峰是偏斜的：取負值表示alpha穩(wěn)態(tài)的波峰偏向左尾部(left-tail)；反之，取正值則表示alpha穩(wěn)態(tài)的波峰偏向右尾部(right-tail)。因此參數(shù)α和β決定了alpha穩(wěn)態(tài)的基本形狀。σ表示分布的方差，μ表示分布的均值，j表示X的第j個特征。由式(1)可知，當(dāng)α=2時，得式(2)：

E[exp(iθX)]=exp(-σ2θ2+jμθ)

(2)

此時，alpha穩(wěn)態(tài)的特征函數(shù)E退化為高斯特征函數(shù)。因此隨著α取值的不同，alpha穩(wěn)定過程可以表示高斯和非高斯情況下的隨機過程。此外，alpha穩(wěn)態(tài)包含4個參數(shù)，每個均具有相應(yīng)的物理意義，這使得研究人員可以針對不同的應(yīng)用環(huán)境很方便地轉(zhuǎn)換仿真模型。雖然alpha穩(wěn)態(tài)沒有分布函數(shù)，但是可以使用Matlab軟件中的stbl工具來進行模擬，這為模擬Web日志的到達模型提供了方便。

2.2 二項式b模型

(3)

(4)

二項式b模型近似于“二八定律”：20%的操作中包含80%的數(shù)據(jù)。在二項式b模型中，如偏置參數(shù)b=0.8意味著在一個給定的時間間隔內(nèi)，80%的流量只占時間間隔的一半(剩余20%占時間間隔的另一半)。然后這個過程反復(fù)遞歸，通過偏置參數(shù)b反映流量的局部突發(fā)行為，因此偏置參數(shù)b具有一定的物理意義。在實際中使偏置參數(shù)b為0.5到1之間的隨機數(shù)，這樣能增加分形的復(fù)雜性。

3 基于alpha穩(wěn)態(tài)過程的用戶到達模型

在選用alpha穩(wěn)態(tài)過程作為Web日志建模依據(jù)之前，需要對實際的Web日志數(shù)據(jù)進行測量分析，以驗證采用alpha穩(wěn)態(tài)過程的合理性。對1995年美國國家航天航空局(NationalAeronauticsandSpaceAdministration，NASA)網(wǎng)站的八月份1 569 898條請求序列和MovieLens-1M的1 000 209條電影評分日志進行統(tǒng)計，圖1表示用戶到達數(shù)量與時間間隔關(guān)系Rel，橫坐標為兩個用戶之間的時間間隔(100ms)，縱坐標為時間間隔內(nèi)到達的用戶數(shù)量。可以看出大部分用戶在很短時間間隔內(nèi)到達，而少部分用戶是相隔很長一段時間才能到達。對圖1的橫縱坐標取對數(shù)，這兩個數(shù)據(jù)集的雙對數(shù)曲線如圖2所示，可以看出在雙對數(shù)坐標下，Rel曲線頭部(靠近坐標原點)為曲線，尾部(遠離坐標原點)大致為直線；對圖1的縱坐標取對數(shù)，其半對數(shù)曲線如圖3所示，可以看出在半對數(shù)坐標下，Rel曲線頭部大致為直線，尾部為曲線(當(dāng)出現(xiàn)大量縱坐標值相等時，取其中點的橫坐標值)。因此Rel是一種頭部為指數(shù)分布，尾部為冪律分布的曲線，這是符合alpha穩(wěn)態(tài)過程的[13]。

可以使用stbl工具的stblfit函數(shù)擬合此數(shù)據(jù)集參數(shù)，接著生成符合這兩個參數(shù)模型的alpha穩(wěn)態(tài)隨機數(shù)集合，將此隨機數(shù)集合與兩個數(shù)據(jù)集用戶到達模式累積概率分布進行比較，結(jié)果如圖4所示。由圖4可以發(fā)現(xiàn)alpha穩(wěn)態(tài)與兩個源數(shù)據(jù)集的累積概率分布差異不大，因此可以模擬基于alpha穩(wěn)態(tài)過程的用戶到達(UserArrivebasedonalphaStableprocess，UAS)模型獲得alpha穩(wěn)態(tài)過程的4個參數(shù)，如表1所示。

為了體現(xiàn)出參數(shù)的物理意義，圖5(a)中NASA數(shù)據(jù)集的突發(fā)性更為均勻，圖形平緩，而圖5(b)中MovieLens-1M數(shù)據(jù)集的突發(fā)性更為集中，圖形陡峭，因此NASA的α更大；其次兩個數(shù)據(jù)集的概率密度分布曲線都向右偏，因此β>0。從圖5的數(shù)據(jù)分布情況來看也不難解釋兩個數(shù)據(jù)集的方差σ和均值μ的差異性。

圖1 不同數(shù)據(jù)集用戶到達數(shù)量與時間間隔關(guān)系分布

圖2 不同數(shù)據(jù)集用戶到達數(shù)量與時間間隔關(guān)系雙對數(shù)分布

圖3 不同數(shù)據(jù)集用戶到達數(shù)量與時間間隔關(guān)系半對數(shù)分布

圖4 原始數(shù)據(jù)集與alpha模擬數(shù)據(jù)集累積概率分布對比

表1alpha穩(wěn)態(tài)過程的擬合參數(shù)

Tab.1Fittingparametersofthealphasteadystateprocess

數(shù)據(jù)集αβσμNASA1．790．9310．8328．40MovieLens?1M1．060．900．9311．49

圖5 不同數(shù)據(jù)集用戶到達模式分布情況

然后使用stbl工具的stblinv函數(shù)隨機獲取用戶到達時間間隔序列ΔT={ΔT1, ΔT2,…, ΔTu,…, ΔTm}，其中m表示有m個用戶，用戶u距離用戶u-1的到達時間間隔為ΔTu。為了使ΔT更真實，改進ΔT如式(5)所示：

ΔT=ΔT/ln (1+Actu)

(5)

對于活躍度高的用戶u，其ΔTu通常很小，這樣會造成短時間內(nèi)同一個用戶頻繁訪問，因此給出對ΔT的懲罰因子1/ln(1+Actu),其中Actu表示用戶u的流行度。

4 基于UAS的算法——MFWS

在單分形模型中，ON/OFF模型因其構(gòu)造簡單而受到廣泛使用，然而其假設(shè)存在與真實流量不符合的現(xiàn)象，因此本文提出一種基于UAS的多重分形Web日志仿真算法——MFWS，改進ON/OFF模型如圖6所示。

圖6中Tu時刻表示某Web日志中某用戶u到達(發(fā)生點擊事件)的時刻,T(u+1)時刻表示用戶u訪問結(jié)束，下一個用戶u+1到達的時刻，將兩次用戶到達時刻之間的時間間隔ΔTu稱為用戶間隔，也稱為Web對象被動OFF時間。用戶的一次點擊行為引發(fā)服務(wù)器發(fā)送多個Web文件，第i個文件和第i+1個文件在傳輸?shù)倪^程中由于網(wǎng)絡(luò)延遲等[11]造成訪問時間間隔Δti，也稱為主動OFF時間。

圖6 改進后的ON/OFF模型

根據(jù)第3章的方法可以使用alpha穩(wěn)態(tài)分布生成用戶間隔ΔT,對于文件間隔Δt,傳統(tǒng)的做法是采用冪律分布來建立數(shù)學(xué)模型[16]，然而在Web服務(wù)器端收集到的用戶訪問Web文件時間僅為Web服務(wù)器發(fā)送Web文件時間，卻沒有用戶訪問Web時間。不同的Web服務(wù)器性能也會導(dǎo)致這種數(shù)學(xué)模型缺乏一般性，同時也無法表現(xiàn)出Web日志的多重分形特性。在實際中，主動OFF時間比被動OFF時間小很多，屬于小時間尺度，根據(jù)Hong等[9]的研究，本文認為同樣也可以將二項式b模型用在小時間尺度的Web日志中。改進方法為在ON/OFF模型模擬文件間隔Δt時采用二項式b模型，具體做法如下：

對NASA網(wǎng)站數(shù)據(jù)進行分析發(fā)現(xiàn)，用戶發(fā)出連續(xù)動作次數(shù)概率近似服從Zipf定律[16]。假設(shè)用戶u的總請求序列是Sequ={sequ1,sequ2,…，sequi}，其中rui為用戶u訪問的第i個Web文件，則第i個Web文件被訪問的概率為p(rui)=iω，利用最小二乘法擬合可得ω=-0.924。這個結(jié)果與ω=-1 的Zipf 定律非常接近。由此可知在Web對象中，用戶連續(xù)訪問2個以上Web文件的概率低于60%，而用戶連續(xù)訪問16個以上Web文件的概率已經(jīng)非常接近于0。文獻[8]指出將時間ΔTu內(nèi)的流量進行n次分離即是二項式分形，但實際中的n存在限制。根據(jù)二項式b模型的偏置參數(shù)b∈(0.5,1)，不可能存在用戶連續(xù)訪問的16個文件都能獨占一個時間區(qū)間，從而二項式分離次數(shù)0≤n≤4。

當(dāng)確定用戶u的連續(xù)訪問序列長度s后，從Sequ中取出前s個Web文件，組成用戶u當(dāng)前連續(xù)訪問序列Yu，隨機選擇二項式分離次數(shù)n，對每個用戶到達時間間隔ΔTu以及連續(xù)訪問的文件序列Yu，建立一棵高度為n+1的滿二叉樹Treeu,將ΔTu分為z=2n個相等區(qū)間，根據(jù)式(3)和(4)計算每個區(qū)間內(nèi)的Web文件數(shù)量，先序遍歷Treeu的葉子節(jié)點組成的時間序列Yu′={yu1′,yu2′,…,yut′,…,yuz′}，其中yut′表示第t個時間區(qū)間內(nèi)用戶訪問的Web文件數(shù)量,用戶訪問Web文件時間為ΔTu+t*ΔTu/z，則Yu′是用戶u的一個含有多分形特性的Web對象。

基于以上分析，本文提出一種基于UAS的多重分形Web日志仿真算法——MFWS。該算法通過改進ON/OFF模型，利用alpha穩(wěn)態(tài)過程模擬用戶到達時間間隔ΔT，利用二項式b模型模擬用戶連續(xù)訪問Web文件時間間隔Δt，算法流程如下：

1)生成每個用戶u的屬性并形成集合U。

2)生成每個文件i的屬性并形成集合I。

3)關(guān)聯(lián)用戶和文件形成原始請求序列Seq。

4)以alpha穩(wěn)態(tài)擬合源數(shù)據(jù)集的用戶到達模式,計算用戶u的到達時間ΔT作為改進的ON/OFF模型的被動OFF時間。

5)將Seq變成用戶請求序列Sequ,遍歷u,記錄算法開始時間currentTime。

6)判斷是否收斂，是則算法結(jié)束；否則判斷Sequ是否為空，為空轉(zhuǎn)5)，不為空則轉(zhuǎn)7)。

7)找到連續(xù)訪問個數(shù)s=1。

8)取出Sequ的前s個文件構(gòu)成連續(xù)訪問序列Y。

9)以二項式b模型分離Y為連續(xù)訪問時間序列Y′，并以Y′的每個元素的Δt作為改進ON/OFF模型的主動OFF時間。

10)將序列Y′加入到用戶的新訪問序列Sequ′中。

11)從Sequ中刪除前s個文件序列，轉(zhuǎn)6)。

5 實驗與結(jié)果分析

5.1 數(shù)據(jù)集

在生成Web日志之后需要觀察模擬Web日志的仿真性能，采用真實數(shù)據(jù)集作為參照比對。實驗采用NASA數(shù)據(jù)集以及MovieLens-1M電影評分數(shù)據(jù)集,其中NASA為31天采集的1 569 898條日志數(shù)據(jù)；MovieLens-1M為6 040個用戶對3 952個電影的1 000 209條評分記錄。

5.2 結(jié)果分析

5.2.1Hurst指數(shù)分析

由自相似性的定義[3]知，要驗證生成的Web日志是否滿足自相似過程，必須滿足自相關(guān)函數(shù)r(m)(k)=r(k)～αk-β，0<β<1,H=2-2β且H∈(0.5,1)。其中α和β為自相關(guān)函數(shù)參數(shù)，H為Hurst指數(shù)。Hurst指數(shù)值越接近于1，說明Web日志具有較強的自相似性?？疾煺鎸崝?shù)據(jù)集與模擬數(shù)據(jù)集的Hurst指數(shù)對比情況，按照不同時間間隔來獲取不同時間尺度下的請求序列，最后用Hurst指數(shù)來估計各個不同時間尺度序列的自相似特性。將真實數(shù)據(jù)集的Hurst指數(shù)記為real_Hurst，將MFWS模擬數(shù)據(jù)集的Hurst指數(shù)記為MFWS_Hurst，將Web代理緩存生成器(WorkloadGenerationtoolforWebProxycaches,PWG)算法[16]模擬數(shù)據(jù)集的Hurst指數(shù)記為PWG_Hurst。如表2所示，可以發(fā)現(xiàn)對于每個真實數(shù)據(jù)集，隨著時間尺度增大，real_Hurst在減小。這是因為隨著時間尺度的增大，自相似系數(shù)r(k)的取值變少，在擬合的過程中，也就造成擬合效果不佳。

通過表2還可以看出，算法MFWS和PWG都有較好的自相似性(Hurst指數(shù)大于0.5)，但是通過將這兩個算法的Hurst指數(shù)值與真實數(shù)據(jù)的Hurst指數(shù)值對比，可以發(fā)現(xiàn)MFWS的Hurst指數(shù)與真實數(shù)據(jù)集更加接近，這是因為PWG算法采用的是冪律分布，在模擬不同類型數(shù)據(jù)集時不如alpha穩(wěn)態(tài)分布合適，這說明MFWS具有更加良好的自相似性。

表2 不同時間尺度下的Hurst指數(shù)比較

5.2.2 分形譜評估

分形譜是Web日志模型在多重分形尺度上的本質(zhì)體現(xiàn)，因而分形譜是衡量多重分形模型好壞的一項重要標準[17]。將兩個真實數(shù)據(jù)集(real)和利用MWFS算法模擬產(chǎn)生的數(shù)據(jù)集(MWFS)的分形譜進行對比分析；另外，為了使實驗更有說服力，將多分形小波算法的模擬數(shù)據(jù)集(MWM)也作為實驗對比參照。α表示holder指數(shù)，f(α)表示奇異譜，以隨機抽樣的方式任意抽取這三個數(shù)據(jù)集中1 s內(nèi)的Web日志，分形譜實驗對比結(jié)果如圖7所示。

圖7 真實數(shù)據(jù)集與模擬數(shù)據(jù)集分型譜對比

由圖7可以看出，在α=1.1時，源數(shù)據(jù)集以及兩種算法模擬的數(shù)據(jù)集的奇異譜非常相似，但是在α=1.1的兩邊，只有MWFS算法的模擬數(shù)據(jù)集更加接近于源數(shù)據(jù)集，說明MWFS算法在多分形譜描述上要優(yōu)于MWM模型[16]，與實際流量分形譜更為接近，能更準確地描述真實流量的多分形特性。

5.2.3 概率密度曲線的評估

分析數(shù)據(jù)集的用戶到達模式概率密度分布，是為了驗證仿真生成的數(shù)據(jù)集的用戶到達模型是否符合實際數(shù)據(jù)集用戶到達模式概率密度分布，體現(xiàn)MWFS算法的真實性。由圖8可知，兩個不同數(shù)據(jù)集的概率密度分布與仿真數(shù)據(jù)集的概率密度分布非常相似，說明仿真效果良好；其次，仿真數(shù)據(jù)具有很明顯的重尾特征，這與真實情況相符。因此，MWFS算法仿真數(shù)據(jù)集符合原始數(shù)據(jù)集的用戶到達模式特征。

通過對比真實數(shù)據(jù)集和模擬數(shù)據(jù)集的自相似特征、多分形特征和用戶到達模式特征，可以發(fā)現(xiàn)MWFS算法具有較好的仿真性能，并且第3章中給出的各項參數(shù)物理意義明確，能夠反映真實數(shù)據(jù)集特征。雖然MWFS算法仿真性能良好，但是由于采用的ON/OFF模型是一種流疊加模型，其時間復(fù)雜度也隨著要生成的模擬數(shù)據(jù)集量級呈線性增長；另外，二項式b模型在創(chuàng)建和遍歷二叉樹時也會消耗大量時間。然而，MWFS得到的ΔT屬于每個用戶的固有屬性，對每個用戶的ΔT的多分形過程作為一次ON/OFF源，這為多個ON/OFF源的并發(fā)執(zhí)行提供了可能，在運行時間上勢必會有所減少。

圖8 不同數(shù)據(jù)集用戶到達模式的概率密度分布

6 結(jié)語

自相似性和多分形性是Web日志仿真的關(guān)鍵，本文提出一種基于穩(wěn)態(tài)過程的多分形Web日志仿真生成算法MWFS，它以alpha穩(wěn)態(tài)模型代替冪律模型在大時間尺度下建立Web日志中的用戶到達模型，同時以二項式b模型在小時間尺度下進行二項式分形，將這兩個模型通過改進的ON/OFF模型進行融合。實驗表明，MWFS算法同時具備良好的自相似性和多分形性；同時MWFS的各項參數(shù)物理意義明確，能夠方便研究人員應(yīng)用于不同的Web服務(wù)器上。如何實現(xiàn)并行化仿真生成是下一步要做的工作。

References)

[1] CALZAROSSA M C, MASSARI L, TESSERA D.Workload characterization: a survey revisited [J].ACM Computing Surveys, 2016, 48(3): Article No.48.

[2] CROVELLA M E, BESTAVROS A.Self-similarity in World Wide Web traffic: evidence and possible causes [J].IEEE/ACM Transactions on Networking, 1997, 5(6): 835-846.

[3] SARLA P, DOODIPALA M R, DINGARI M.Self-similarity analysis of Web users arrival pattern at selected Web centers [J].American Journal of Computational Mathematics, 2016, 6(1): 17-22.

[4] RIEDI R H, CROUSE M S, RIBEIRO V J, et al.A multifractal wavelet model with application to network traffic [J].IEEE Transactions on Information Theory, 1999, 45(3): 992-1018.

[5] 張雪媛,王永剛,張瓊.基于分數(shù)布朗運動的自相似流量判別及生成方法[J].計算機應(yīng)用,2013,33(4):947-949,963.(ZHANG X Y, WANG Y G, ZHANG Q.Self-similar traffic discrimination and generating methods based on fractal Brown motion [J].Journal of Computer Applications, 2013, 33(4): 947-949, 963.)

[6] GOMEZ M E, SANTONJA V.Analysis of self-similarity in I/O workload using structural modeling [C]// Proceedings of the 1999 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems.Piscataway, NJ: IEEE, 1999: 234.

[7] LELAND W E, TAQQU M S, WILLINGER W, et al.On the self-similar nature of Ethernet traffic [C]// SIGCOMM’93: Proceedings of the 1993 Conference proceedings on Communications Architectures, Protocols and Applications.New York: ACM, 1993: 183-193.

[8] WANG M Z, MADHYASTHA T, CHAN N H, et al.Data mining meets performance evaluation: fast algorithms for modeling bursty traffic [C]// ICDE’02: Proceedings of the 18th International Conference on Data Engineering.Washington, DC: IEEE Computer Society, 2002: 507.

[9] HONG B, MADHYASTHA T M.The relevance of long-range dependence in disk traffic and implications for trace synthesis [C]// Proceedings of the 22nd IEEE / 13th NASA Goddard Conference on Mass Storage Systems and Technologies.Piscataway, NJ: IEEE, 2005: 316-326.

[10] WEN J, MA Y, LIU P, et al.Distributed multipliers in MWM for analyzing job arrival processes in massive HPC workload datasets [J].Future Generation Computer Systems, 2014, 37(7): 335-344.

[11] GUO L, TAN E, CHEN S, et al.The stretched exponential distribution of Internet media access patterns [C]// PODC’08: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing.New York: ACM, 2008: 283-294.

[12] CHEN S, GHORBANI M, WANG Y Z, et al.Trace-based analysis and prediction of cloud computing user behavior using the fractal modeling technique [C]// Proceedings of the 2014 IEEE International Congress on Big Data (BigData Congress).Piscataway, NJ: IEEE, 2014: 733-739.

[13] NOLAN J P.Stable distributions: models for heavy tailed data [EB/OL].[2016- 01- 30].https://www.researchgate.net/publication/247635151_Stable_Distribution_Models_for_Heavy-Tailed_data.

[14] 鄒強,程強.存儲系統(tǒng)負載自相似性研究綜述[J].計算機科學(xué),2013,40(3):24-30.(ZOU Q, CHENG Q.Survey of studies on self-similarity in storage system workload [J].Computer Science, 2013, 40(3): 24-30.)

[16] BUSARI M, WILLIAMSON C.ProWGen: a synthetic workload generation tool for simulation evaluation of Web proxy caches [J].Computer Networks, 2002, 38(6): 779-794.

[17] THOMPSON J R, WILSON J R.Multifractal detrended fluctuation analysis: practical applications to financial time series [J].Mathematics and Computers in Simulation, 2016, 126(C): 63-88.

This work is partially supported by the Fujian Provincial Great Plan Project (2016H6007).

PENG Xingxiong, born in 1991, M.S.candidate.His research interests include machine learning.

XIAO Ruliang, born in 1966, Ph.D., professor.His research interests include software engineering, new technology of big data software.

Multi-fractal Web log simulation generation algorithm based on stable process

PENG Xingxiong1,2, XIAO Ruliang1,2*

(1.FacultyofSoftware，F(xiàn)ujianNormalUniversity,FuzhouFujian350117,China; 2.FujianProvincialEngineeringResearchCenterofPublicServiceBigDataAnalysisandApplication,FuzhouFujian350117,China)

The software system running on the server cluster needs large-scale data sets of Web log to meet the performance test requirement, but the existing simulation generation algorithm cannot meet the requirements due to the single model.Aiming at this problem, a new multi-fractal Web log simulation generation algorithm based on alpha stable process was proposed.Firstly, the self-similarity of Web log was described by alpha stable process in Long Range Dependence (LRD).Secondly, the multi-fractal of Web log was described by binomial-bmodel in Short Range Dependence (SRD).Finally, the model of long range dependence and the model of short range dependence were integrated into the improved ON/OFF framework.Compared with the single model, the parameters of the proposed algorithm has clear physical meaning equipped with good performance of self-similarity and multi-fractal.The experimental results show that the proposed algorithm can accurately simulate the real Web log and be effectively applied in Web log simulation generation with large-scale data sets.

stable process; multi-fractal; self-similarity; time series; log analysis; simulation generation

2016- 06- 14;

2016- 08- 18。 基金項目:福建省高校產(chǎn)學(xué)合作項目(2016H6007)。

彭行雄(1991—)，男，湖北孝感人，碩士研究生，主要研究方向：機器學(xué)習(xí)； 肖如良(1966—)，男，湖南婁底人，教授，博士，CCF高級會員，主要研究方向：軟件工程、大數(shù)據(jù)軟件新技術(shù)。

1001- 9081(2017)02- 0587- 06

10.11772/j.issn.1001- 9081.2017.02.0587

TP

A