基于多尺度小波變化的自相似網絡流量預測

何凱霖，丁曉峰

（電子科技大學 成都學院 計算機系，四川 成都611731）

0 引 言

Leland W E等［1］在大量的業務流量監測過程中發現了網絡流量具有自相似 （self－similarity）特性，指出實際流量序列的自相關函數隨時間尺度的增大呈漸近雙曲線衰減而非負指數衰減，流量表現出重尾分布的長相關性 （longrange dependence，LRD）特征，并且不論網絡的拓撲結構、用戶數量、服務類型如何變化，這種自相似性是始終存在的。這宣告了具有短相關特征的流量模型已不能充分反映網絡流量的高可變性，不再適合于網絡流量的分析和建模［2，3］。

后續研究結果表明［4－6］，傳輸層協議本身就是導致網絡流量出現自相似性的決定因素之一，特別是占整個網絡流量的90%左右的TCP協議，其擁塞控制中的超時重傳和指數退避機制會使分組到達時間間隔呈重尾分布；反言之，網絡流量自相似性的存在又給網絡管理和網絡協議的運行增加了復雜性［7］，如大尺度上的突發性會造成網絡資源嚴重過利用率和欠利用率時間的增大，而且隨自相似程度的增加，丟失率、重傳率以及平均隊列長度和響應時間均隨之增長［8］；路由器中包序列的排隊問題也受網絡流量在小尺度時間范圍內波動的影響，而尺度的劃分通常正是以擁塞控制機制中的RTT為基準［9，10］。所以，網絡流量尺度特性和不同尺度上的自相似特征必然影響到TCP的擁塞控制機制，這使傳統模型下所沿用的如下結論都不再適用：緩存線性增長導致報文丟失按指數規律減少以及傳輸帶寬利用率成比例增長等。這直接導致網絡擁塞不可避免，從而造成TCP難以有效地實施網絡控制和QoS保證。因此針對具有自相似特性的流量，網絡協議的優化尚需更多的研究。

本文提出以DWT多尺度分析為依據建立網絡流模型并進行流量預測。把利用該模型計算得到的預測流量相似性程度值Hurst引入路由器的主動隊列管理算法 （AQM）中，采用AQM算法形成的嚴謹的響應方案對異常的估計流量進行處理，可以提高動態流量控制的有效性，實現了網絡協議的優化。

1 流量數據基于DWT的多尺度分析

考慮到網絡流量具有較高的復雜性和不平穩特性，本文首先利用DWT對原始流量數據進行多尺度分解，以獲得包含不同頻率特性的近似分量與細節分量。所謂近似分量是指與分解前的網絡流量基本性質一致的分量，即基本不包含高頻的短相關特性而保留著未分解流量的長相關性等；所謂細節分量是指反映細節特性如動態流量的短期依賴關系即短相關性。因此通過小波變換不僅保持原流量的趨勢并減少突發，能有效達到消噪預處理的效果，且使網絡業務流量的復雜性得到分解。之后在特性相對單一的小波分量上建立刻畫網絡流量特性的序列模型，可實現以較快的收斂性、較高的平穩性和較低的誤差來進行流量預測。基于DWT的多尺度分析方法在網絡流量預測和控制中極具有效性。并且通過分析論證可得網絡協議性能優化空間與預測流量自相似程度密切相關。大的相似性在適當條件下可以提供更優越的性能。

1.1 自相似程度的判斷

為達到對網絡流量自相似性程度進行判斷的目的，本文選取研究者普遍認同的用以刻畫自相似性程度的Hurst參數H，當H取值在1／2＜H＜1之間時，則認為隨機過程具有自相似性，其程度大小隨H值的增大而增加。這種現象映射到實際網絡中就叫做網絡流量突發，目前網絡實際流量的H估計值通常在0.7～0.9之間。以上用于求解Hurst值的方法需要較強的穩定性，故采用R／S法 （resealed adjusted range statistic）。

1.2 基于DWT的多尺度分析過程

要將小波變換應用于網絡流量分析中，需要采用離散小波變換 （DWT）以更好地處理離散數據信號［11，12］。這里將信號f（t）的連續小波變換 （CWT）定義為

圖1 j層小波分解過程

Aj＝ ｛aj，1，aj，2，…，aj，k｝為第j層的尺度系數，反映第j層的低頻近似分量，表達序列的大致趨勢；Dj＝ ｛dj，1，dj，2，…，dj，k｝為第j層的小波系數，反映第j層的高頻細節分量，表達序列在細節上的差異。直觀上，DWT把一維網絡流量信號分解為兩維信號。原始信號A0分解為A1和D1，低頻部分進一步分解，即：A1再分解為A2和D2，…，如此進行可得到任意尺度 （或分辨率）上的近似分量和細節分量，力求構造一個頻率上高度逼近L2（R）空間的正交小波基。而Mallat中的單支重構則是對小波分解的小波系數和尺度系數進行小波逆變換，形成與原始序列等長度的單支序列。

1.3 DWT的具體實施

本文以MATLAB為流量小波變換的輔助工具，作為母小波的函數必須具有很好的時、頻局部特性，以更好地刻畫信號的突變信息。因此這里選取Haar小波、Daubechies小波系 （DbN）、Coiflets小波系 （CoifN）和Symlets小波系 （SymN）等常見小波基進行測試，將原始流量與合成流量分別用相應的小波進行分解，并統計各尺度上小波系數的標準差，最終選擇支集長度較小的、仿真流量性能與原始流量性能較為接近的Db4為實驗用小波基函數。對流量數據的DWT一維多尺度分解、消噪與重構在MATLAB中的實現代碼如下：

2 流量序列預測模型

2.1 FARIMA

網絡流量的建模選用分形自回歸求和滑動平均模型，簡稱 FARIMA （fractional auto－regressive integrated moving average）。在建模過程中使用了3個參數p、d和q，其中d可以體現所要估測流量的長相關性，而p、q則反映所含部分流量的短相關性，所以該方法生成的預測序列能保持與真實序列一致的長相關和短相關特征，具有較高的靈活性。FARIMA是ARIMA （p，d，q）模型的自然擴展，后者可表示為φ（B）（1－B）dXt＝ Θ（B）at，其中B 是滯后算子，1－B為差分算子，｛at｝為白噪聲序列。FARIMA與ARIMA的唯一區別在于參數d允許使用非整數，此時d階差分算子其 中 參 數參數d可由式H＝d＋0.5求得，H 為序列的Hurst參數，即可利用Hurst參數計算間接對d進行近似估計。

2.2 模型整體功能結構

這里將所設計的流量序列預測模型的整體功能進行算法描述，如圖2所示。

（1）為了對網絡自相似性進行估測，需要計算表征其程度大小的H值。這里求解采用的方法是R／S法，其應用對象是代表待測流量的序列f（t），由關系式d＝H－0.5獲得對預測模型FARIMA （p，d，q）中差分參數d的有效估計。

（2）對于帶有明顯相似性和長相關特征的初始流量數據f（t），采用Db4DWT方法予以分解，規定其分解尺度為J，該過程結束后輸出量分別為近似以及細節分量。前者以AJ表示，后者以D1，D2，…，DJ表示。

圖2 基于DWT多尺度分析的協議優化模型

（3）將分解后的近似分量使用FARIMA模型進行預測得到a’j；同理，對 （2）中D1，D2，…，DJ予以相同處理后記所得結果為a’1，a’2，…，a’j。

（4）利用Mallat算法對 （3）中所得兩類分量予以重構，具體公式如下：a′j－1＝

（5）經 （4）得到新的流量序列f′（t），為了明確新的網絡自相似性程度亦即H’值，對f′（t）施以FARIMA模型預測初始流量。一般情況下參數p、q隨現實狀況而定，本文p賦值2，q賦值1。

（6）最后得到FARIMA （p，d，q）擬合流量，進一步以均方誤差來定量評估預測效果，M為數據總量。對比分析利用計算機仿真所得結果與真實流量狀況，總結本文估測結果在變化趨勢等方面對真實狀況的趨近程度。進一步分析當前時刻過后網絡流量在各方面可能發生的變化，以輔助實施網絡協議的擁塞控制策略。

3 網絡協議優化策略及仿真實驗

3.1 網絡擁塞和流量控制機制分析

網絡中經常出現擁塞甚至系統崩潰等情況，用以解決這一問題的方案基本都是在網絡中建立擁塞控制機制，以最具代表性的TCP協議為例 （根據MCI的統計，網絡中總字節數的95%和總報文數的90%均使用TCP傳輸），TCP采用慢啟動、擁塞避免、快速重傳、快速恢復、選擇性應答 （SACK）等算法確保網絡的傳輸性能。然而網絡中不存在專門的連接通道供端系統查明網絡狀況，因此端系統采取控制網絡傳送數據等行動的根據唯有來源于ACK、RTO超時等信息。這就造成反映不及時進而可能導致反饋延遲和網絡抖動等問題［11］。而作為網絡狀態最直接感受者的路由器，如果能在IP層參與擁塞控制，必然成為端系統的有力補充。路由器通過檢測當前負載狀況，可以在網絡設備的緩沖溢出之前丟棄或標記報文，以降低排隊延遲，并形成擁塞指示以輔助端系統進行流量控制［12］。

在流量估算和控制中，當前網絡協議常選擇的是EWMA法。該方法可以滿足低通濾波的要求，相鄰兩個時刻的流量速率估算方式為。應注意，EWMA算法對于只存在短相關性的傳統泊松過程是合理的，即作為短相關流量，其自相關函數呈指數衰減，距當前分組到達時間越近的速率值對于當前速率估算值的影響越大；當時間間隔Ts足夠大時，R（t＋Ts）與R（t）的流量速率是不相關的。這與實際自相似網絡流量中大量存在的長相關特征并不相符，顯然并不適合在擁塞控制協議中用作網絡流量控制的關鍵手段。

此外，我們通過實驗統計了在不同自相似參數下分組丟失率隨緩沖區容量的變化情況，如圖3所示。可觀察到在緩沖區容量相同時，長相關業務在H值越大時分組丟失率越高。這證實了自相似程度增加時，網絡流量突發性增強，重傳率、平均隊列長度和響應時間均增大，網絡性能下降。

圖3 自相似性程度對不同緩沖區容量下的分組丟失率的影響

綜合上述分析，本文嘗試將基于DWT的流量預測模型的結果引入到路由器的主動隊列管理算法 （AQM）中，利用自相似流量的統計規律和預測特征，以擁塞預警而非“被動響應”的方式，形成對網絡協議中的擁塞控制機制的有效優化。

3.2 協議優化策略

在改進AQM算法時，這里選擇基于優化流控思想OFC得到的REM算法作為改進依據，利用FARIMA模型計算Hurst值H’來表征相似性程度大小，根據實際狀況適當改變擁塞控制機制中的參數標記概率，按以下步驟進行：

（1）利用下式求解REM算法中的參數Price：pl（t＋1）＝［pl（t）＋γ（al（bl（t）－b＊l）＋xl（t）－cl））］＋，可以看出該計算公式包含參數al以實現調節功能，此外路由器使用狀況以及帶寬占用情況也是需要考慮的因素。

（2）以標記概率代表擁塞控制機制的擁塞指示，隊列1的計算公式為是常量。其中t代表一段時間。從而得到端到端報文標記概率為引入H’的調節作用，將標記概率計算公式調整為為權重參數，h0為閾值，通常取0.8～0.9之間。

3.3 算法復雜度分析

由于小波變換的計算效率很高，對含N個采樣數據的信號進行Mallat離散小波變換的時間復雜度僅為0（N），對分解后的流量分量采用FARIMA過程進行線性預測時，FARIMA算法乘法操作次數為0（N2），因此對網絡流量進行預測的時間復雜度為0（N2）；空間復雜度上，如果選擇的小波長度為N，那么本算法中進行小波分解和重構所需存儲空間大小是0（N），對分解后流量進行預測時，FARIMA過程需要存儲p、d、q等中間變量，其中d的大小為N，p、q的大小為N2，因此總的空間復雜度為0（N2）。

3.4 實驗仿真與結構分析

（1）實驗方案：本文采用MATLAB軟件和C＋＋語言編程實現該模型，以NS為仿真環境，以Pareto模型產生自相似輸入流量，實驗過程如圖4所示。網絡協議選取目前網絡中應用最廣的TCP版本：TCP New Reno，在尺度為J＝3上運行Mallat算法對網絡流量進行多尺度db4小波分解和重構。

圖4 仿真實驗運行過程

（2）流量分析結論及流量預測模型效果檢驗：首先我們統計了原始流量與合成流量的自相似特性表征值H，經R／S估值，發現在原始流量的H為0.8319時，合成流量的H’值為0.8298，這表明DWT多尺度變換能近似表征出原始流量的LRD特性。此外，多個不同流量樣本數據展現出如下特點；①網絡流量在1秒級以上的尺度上，表現出明顯的LRD特性；②網絡流量在多種時間尺度上表現出非平穩特性。

圖5是一段TCP流經過流量預測模型處理、重構疊加后的流量特征與實際流量的對比，測試顯示模型具有較高的預測精度。

（3）優化后協議性能仿真結果

圖5 流量模型的預測值與實際流量對照

1）在有干擾背景流震蕩的情況下，模擬優化后協議的運行情況。如圖6所示：Flow1為原始流量，Flow2是運行模型擬合、經協議優化后的流量。結果表明這種新的擁塞控制機制可以預測并抑制自相關流量在大尺度上的固有突發，能夠在一定程度上有效保證網絡性能的穩定性。

圖6 仿真結果1

2）圖7是協議間公平性實驗，TCP1和TCP2是運行優化后協議的兩個共享同一瓶頸鏈路的同等條件流量，60s時刻啟動該鏈路上的一個UDP流。此實驗同時測試TCP流之間的公平性以及TCP流與無擁塞控制機制的UDP流之間的公平性。結果表明，經優化后，協議間公平性特征良好，具有較好的可擴展性。

圖7 仿真結果2

4 結束語

就網絡流量而言，是否可對其進行預測有賴于自身性質。如果對自相似性網絡進行流量預測，了解其長相關性非常重要，況且網絡流量的尺度特性對于網絡效率的提高和網絡協議的設計均具有重大的影響，因此本文進行以DWT多尺度分析為基礎的網絡流量建模和預測，并在預測基礎上改變傳統的控制方式，于傳統網絡協議的基礎上改進算法進而實現對自相似網絡的流量預測，對提高資源利用率、進一步實施流量控制工程、網絡性能更優都具有顯著的研究意義。

［1］Leland WE，Gao L，Zhang X L.A network traffic analysis and forecast based on wavelet technology ［J］.Computer Applications and Software，1992，25 （8）：70－72.

［2］WANG Junsong，GAO Zhiwei.Network traffic modeling and forecasting based on RBF neural network ［J］.Computer Engineering and Application，2011，44 （13）：6－11 （in Chinese）.［王俊松，高志偉.基于RBF神經網絡的網絡流量建模及預測［J］.計算機工程與應用，2011，44 （13）：6－11.］

［3］Bai X Y，Ye X M，Jiang H.Network traffic predicting based on wavelet transform and autoregressive model ［J］.Computer Science，2013，34 （7）：47－49.

［4］Chen X T，Liu J X.Network traffic prediction based on wavelet transformation and FARIIMA ［J］.Journal on Communications，2011，32 （4）：153－157.

［5］YIN Bo，XIA Jingbo，FU Kai，et al.Based on IPSO chaos of support vector machine （SVM）network traffic prediction research ［J］.Computer Application Research，2012，29 （11）：4293－4295（in Chinese）. ［尹波，夏靖波，付凱，等.基于IPSO混沌支持向量機的網絡流量預測研究 ［J］.計算機應用研究，2012，29 （11）4293－4295.］

［6］Yang X S，Deb S.Engineering optimization by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimization，2012，1 （4）：330－343.

［7］LI Dandan，ZHANG Runtong.Cognitive network in network traffic prediction model based on ant colony algorithm ［J］.Journal of Electronics，2011 （10）：100－103 （in Chinese）.［李丹丹，張閏彤.認知網絡中基于蟻群算法的網絡流量預測模型 ［J］.電子學報，2011 （10）：100－103.］

［8］BAI Xiangyu，YE Xinming，JIANG Hai.Based on wavelet transform and autoregressive model of network traffic prediction ［J］.Journal of Computer Science，2011，34 （7）：47－49 （in Chinese）.［白翔宇，葉新銘，蔣海.基于小波變換與自回歸模型的網絡流量預測 ［J］.計算機科學，2011，34 （7）：47－49.］

［9］Li Chunfu，Zheng Guangjun，Li Yanqi，et al.Study on control strategy of lockup process of torque converter ［J］.Automobile Technology，2013 （10）：15－17.

［10］MO Yuanbin，LIU Fuyong，ZHANG Yunan.With gauss mutation of artificial fireflies optimization algorithm ［J］.Computer Application Research，2013，30 （1）：121－124 （in Chinese）.［莫愿斌，劉付永，張宇楠.帶高斯變異的人工螢火蟲優化算法 ［J］.計算機應用研究，2013，30 （1）：121－124.］

［11］Yang S M，Guo W，Tang W.A collision resolution algorithm based on time－series forecasting for cognitive wireless networks ［J］.Journal on Communications，2011，32 （11）：51－58.

［12］WANG Fan，HE Xingshi，WANG Yan.The cuckoo search algorithm based on gauss perturbation ［J］.Journal of Computers，2011，25 （4）：566－569 （in Chinese）.［王凡，賀興時，王燕.基于高斯擾動的布谷鳥搜索算法 ［J］.計算機學報，2011，25 （4）：566－569.］