基于穩態過程的多重分形Web日志仿真生成算法

彭行雄，肖如良

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

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

基于穩態過程的多重分形Web日志仿真生成算法

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

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

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

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

穩態過程；多重分形；自相似；時間序列；日志分析；仿真生成

0 引言

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

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

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

1 相關工作

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

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

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

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

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

2 理論基礎

2.1 alpha穩態

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

E[exp(iθX)]=

(1)

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

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

(2)

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

2.2 二項式b模型

(3)

(4)

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

3 基于alpha穩態過程的用戶到達模型

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

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

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

圖1 不同數據集用戶到達數量與時間間隔關系分布

圖2 不同數據集用戶到達數量與時間間隔關系雙對數分布

圖3 不同數據集用戶到達數量與時間間隔關系半對數分布

圖4 原始數據集與alpha模擬數據集累積概率分布對比

表1alpha穩態過程的擬合參數

Tab.1Fittingparametersofthealphasteadystateprocess

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

圖5 不同數據集用戶到達模式分布情況

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

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

(5)

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

4 基于UAS的算法——MFWS

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

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

圖6 改進后的ON/OFF模型

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

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

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

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

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

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

3)關聯用戶和文件形成原始請求序列Seq。

4)以alpha穩態擬合源數據集的用戶到達模式,計算用戶u的到達時間ΔT作為改進的ON/OFF模型的被動OFF時間。

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

6)判斷是否收斂，是則算法結束；否則判斷Sequ是否為空，為空轉5)，不為空則轉7)。

7)找到連續訪問個數s=1。

8)取出Sequ的前s個文件構成連續訪問序列Y。

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

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

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

5 實驗與結果分析

5.1 數據集

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

5.2 結果分析

5.2.1Hurst指數分析

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

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

表2 不同時間尺度下的Hurst指數比較

5.2.2 分形譜評估

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

圖7 真實數據集與模擬數據集分型譜對比

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

5.2.3 概率密度曲線的評估

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

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

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

6 結語

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

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] 張雪媛,王永剛,張瓊.基于分數布朗運動的自相似流量判別及生成方法[J].計算機應用,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] 鄒強,程強.存儲系統負載自相似性研究綜述[J].計算機科學,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，FujianNormalUniversity,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。 基金項目:福建省高校產學合作項目(2016H6007)。

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

1001- 9081(2017)02- 0587- 06

10.11772/j.issn.1001- 9081.2017.02.0587

TP

A