基于混合流量預測的虛擬網絡拓撲重構方法

史朝衛, 孟相如, 康巧燕, 蘇玉澤

(1. 空軍工程大學信息與導航學院, 陜西 西安 710077; 2. 中國人民解放軍94303部隊, 山東 濰坊 261000)

0 引 言

隨著互聯網技術的高速發展,網絡用戶數量急劇增加,傳統互聯網架構日益僵化,已難以應對用戶多樣化的業務需求[1-2]。網絡虛擬化技術通過屏蔽不同物理網絡之間的架構差異,將物理網絡資源池化[3-4],為用戶提供無差別的網絡服務,逐漸成為研究熱點[5],池化資源的分配也隨即成為一個更具挑戰性的任務。虛擬網絡映射技術通過動態調用物理網絡資源,為用戶提供定制服務,提高了網絡資源的利用率[6]。

傳統靜態虛擬網絡映射技術通常將虛擬鏈路的帶寬設置為流量最大值,以滿足用戶動態變化的帶寬需求,但是這種策略將會導致資源的過配置,一定程度上造成了資源浪費。因此,虛擬網絡拓撲動態重構技術逐漸引起學術界關注[7-8]。文獻[7]基于流量感知,提出虛擬網絡拓撲動態重構方法,通過動態調整虛擬鏈路帶寬資源提高物理網絡資源利用率。但是該方法沒有對下一周期內鏈路的流量進行預測,刪除了大量虛擬鏈路來釋放帶寬資源,會導致下一周期內因不能滿足用戶需求而需要頻繁重構虛擬網絡,這種現象稱為乒乓效應。文獻[8]為避免乒乓效應,規定新構建的虛擬鏈路在一段時間內不能刪除,一些利用率比較低的虛擬鏈路可能長時間占用大量帶寬資源,導致資源浪費。

為了適應虛擬網絡拓撲中流量在未來時刻的動態變化,準確刪除利用率過低的虛擬鏈路并將流經該鏈路的流量遷移至其他鏈路,本文引入流量預測算法,將流量預測結果作為虛擬網絡拓撲重構的輸入。傳統的自回歸滑動平均(auto-regressive moving average,ARMA)模型[9]和差分ARMA(auto-regressive integrated moving average,ARIMA)模型[10]適用于對具有長相關性的大尺度網絡流量進行預測,對于具有混沌性特征的強非線性小尺度網絡流量預測效果不佳[11]。文獻[12-13]等將神經網絡應用于小尺度網絡流量預測,但這種單一預測模型性能有限,容易收斂于局部最優。文獻[14-15]采用組合模型進行網絡流量數據的訓練預測,其中文獻[14]提出基于支持向量機(support vector machine,SVM)回歸算法和ARIMA模型的組合模型預測網絡流量,文獻[15]利用局部投影技術對流量數據進行高位去噪,采用基于徑向基函數(radial basis function,RBF)神經網絡對去噪后的流量序列進行訓練預測。上述基于SVM和RBF神經網絡的組合流量預測算法雖然可以提高預測精度,但是計算復雜度較高,訓練預測時間較長。

對此,本文提出一種基于混合流量預測的虛擬網絡拓撲重構方法(virtual network topology reconfiguration approach based on hybrid traffic prediction, VNTR-HTP),對具有強非線性特征的小尺度網絡流量進行預測,并根據預測結果進行虛擬網絡拓撲重構。由于小尺度網絡流量具有混沌性等強非線性特征,為提高預測精度,本文首先采用小波分解方法將流量數據分解為高頻的細節時間序列和低頻的近似時間序列[16],然后利用相空間重構和基于粒子群優化的組合參數選擇算法,對分解后的流量序列進行特征提取構建訓練樣本[17]。之后分別采用混沌模型對具有混沌特征的細節時間序列進行處理,采用極限學習機(extreme learning machine, ELM)[18]神經網絡對近似時間序列進行處理,再將兩者輸出的數據序列進行線性疊加即可得到流量預測序列。ELM神經網絡具有預測精度高、訓練速度快等優點,可以在保證預測準確度的同時減少算法運行時間,提高流量預測效率。虛擬網絡拓撲重構方法根據下一周期內鏈路的流量預測結果實時進行拓撲重構,在避免出現乒乓效應的同時節省更多帶寬資源。

1 虛擬網絡拓撲重構模型

在網絡虛擬化過程中,虛擬網絡控制平臺可以根據用戶需求構建邏輯隔離的虛擬網絡并根據用戶需求變化對已分配的資源進行動態調整。本節對虛擬網絡拓撲重構進行建模分析,并引入混合流量預測算法,根據下一周期流量預測結果對虛擬網絡拓撲進行動態重構。

1.1 虛擬網絡拓撲重構流程

為避免虛擬鏈路流量擁塞,本文設置鏈路利用率上限閾值WH,避免單條鏈路聚集過多流量而影響服務質量。基于混合流量預測的虛擬網絡拓撲重構流程如圖1所示。

圖1 VNTR-HTP模型

首先,虛擬網絡控制平臺時刻感知虛擬鏈路當前流量,利用歷史數據預測下一周期鏈路流量值,并計算節點i和節點j之間的鏈路帶寬利用率uij。然后將鏈路利用率uij分別與上限閾值WH和下限閾值WL進行比較。若存在uij≥WH,則計算鏈路過載流量并增加鏈路帶寬值Bij。如果存在鏈路在一個預測周期內的帶寬利用率都滿足uij≤WL并且滿足其它約束條件,則刪除該條虛擬鏈路,并在保證鏈路利用率uij≤WH的基礎上將當前鏈路上的流量遷移至目標虛擬鏈路。

虛擬網絡拓撲重構如圖2所示,當預測到下一周期鏈路lad的帶寬利用率滿足uad≥WH,則計算鏈路過載流量并增加鏈路帶寬值Bad。當預測到下一周期鏈路lab的帶寬利用率滿足uab≤WL,并且由節點a到節點b的另一條鏈路lacb上有充足的帶寬資源,能夠保證鏈路lab上的流量遷移過去之后其帶寬利用率仍滿足uacb≤WH。此時,將流經鏈路lab的流量遷移至鏈路lacb,并刪除鏈路lab,回收帶寬資源。

圖2 拓撲重構示例

1.2 虛擬網絡拓撲重構方法

VNTR-HTP方法根據下一周期虛擬鏈路流量預測結果決定是否進行虛擬網絡拓撲重構。詳細拓撲重構方法流程如下所示。

算法 1拓撲重構方法

步驟 1感知虛擬鏈路當前流量,利用基于參數優化的流量預測算法預測下一周期鏈路流量值,并計算每條鏈路的帶寬利用率uij,將帶寬利用率高的虛擬鏈路存入集合Lh,將帶寬利用率低的虛擬鏈路存入集合Lv

步驟 2for 集合Lh中的每一條虛擬鏈路lij

步驟 3計算鏈路過載流量并增加鏈路帶寬值

步驟 4end for

步驟 5for 集合Lv中的每一條虛擬鏈路lij

步驟 6選擇節點i和j之間的其他路徑并將其存入集合Lr

步驟 7ifLr=?

步驟 8保留虛擬鏈路lij

步驟 9else

步驟 10fork=1:length(Lr)

步驟 11計算第k條鏈路剩余可用帶寬資源Bk

步驟 12ifBk>uijBij

步驟 13刪除虛擬鏈路lij,并將流經該虛擬鏈路的流量遷移至集合Lr中的第k條虛擬鏈路上

步驟 14break

步驟 15else

步驟 16continue

步驟 17end if

步驟 18end for

步驟 19end if

步驟 20end for

其中,步驟1通過流量預測算法預測下一周期內的流量值并計算每條鏈路的帶寬利用率,步驟2～步驟4通過增加過載虛擬鏈路的帶寬值以避免鏈路擁塞,步驟5～步驟12確保目標虛擬鏈路有足夠的帶寬資源可以承載遷移的流量,步驟13執行流量遷移并將帶寬利用率低的虛擬鏈路刪除以回收帶寬資源。

2 基于參數優化選擇的混合流量預測算法

流量預測算法是執行虛擬網絡拓撲重構的核心子算法,流量預測的精度和預測所需的時間對拓撲重構的結果和效率有重要影響。為提高流量預測精度與預測效率,本文引入了基于參數優化選擇的混合流量預測算法(hybrid traffic prediction based on parameter optimization selection, HTP-POS)。HTP-POS算法流程如圖3所示,其主要包含小波分解、相空間重構、參數優化選擇和混合流量預測等4個步驟。

圖3 HTP-POS算法流程

HTP-POS算法利用小波分解方法將流量序列分解為近似時間序列和細節時間序列,采用相空間重構法構建訓練樣本并利用不同的流量預測模型對不同時間序列進行獨立分析,以提高流量預測精度與預測效率。

2.1 小波分解

由于小尺度網絡流量序列具有混沌特性,直接進行流量預測容易產生較大的預測誤差,因此本文采用小波分解方法,將網絡流量分解為近似和細節時間序列后分別采用不同的模型進行處理,提高預測精度。近似時間序列是流量序列中變化緩慢的部分,是時間序列的框架,占全部信息的大部分;細節時間序列是流量序列中變化迅速的部分,反映的是時間序列的細節信息,占全部信息的小部分。進行小波分解時,分解層數越大,所能觀察到的網絡流量細節特征就越多,但當分解層數過大時,計算量也會迅速增加,預測效率降低。根據文獻[16]可知,當分解層數為3時,預測誤差基本可以達到預期效果,同時具有較低的計算復雜度。因此本文將網絡流量序列分解為一個近似時間序列AT3和3個細節時間序列DT1、DT2和DT3。

2.2 相空間重構

在時間序列的預測問題中,對數據進行訓練預測時需要提取訓練樣本的特征信息,而這些特征信息在一維空間是不可分的[17]。相空間重構方法可以把一維的時間序列運用某種映射法則映射到高維相空間,提取出序列中深層次信息,然后計算和分析奇異吸引子在高維相空間中的運動情況和分布情況,根據其特點找出隱藏在原始系統中的變化發展規律,是一種十分有效的、主要對非線性時間序列所反映的更深層次的信息進行挖掘提取的方法。

基于小尺度網絡流量混沌性和突變性特點,為提取能夠反映流量序列變化規律的特征信息,本文采用基于坐標延遲的相空間重構方法,將小尺度網絡流量預測轉化為非線性時間序列預測問題,把所處理的流量序列的相關信息映射到高維空間,提取序列中深層次信息,構建訓練樣本。

坐標延遲法在進行相空間重構時所采用的方法是通過一維時間序列[x1,x2, …,xn]的不同時間延遲對多維相空間矢量進行構造,即選取合適的嵌入維數m和延遲時間τ,將原始混沌時間序列重構為如下m維相空間:

(1)

式中,N為相空間中相點的個數且N=n-(m-1)τ;n為原一維時間序列長度。

2.3 基于粒子群優化的組合參數選擇算法

在進行相空間重構過程中,參數m和τ的選擇對流量預測結果有重要影響。為了提高預測精度與預測效率,本文提出基于粒子群優化的組合參數選擇算法,選擇合適的參數m和τ,在保證算法運行效率的同時提高預測精度。算法流程如圖4所示。

圖4 基于粒子群優化的組合參數選擇算法流程

基于粒子群優化的組合參數選擇算法具體步驟如下所示。

算法2基于粒子群優化的組合參數選擇算法

步驟 1初始化網絡流量信息,設定參數m和τ的取值范圍分別為M和T,粒子隨機生成初始位置參數與速度參數;

步驟 2計算每個粒子的適應度值;

步驟 3對每個粒子,用它的適應度值和個體極值比較,如果較好,則替換個體極值;

步驟 4對每個粒子,用它的適應度值和種群極值比較,如果較好,則替換種群極值;

步驟 5更新粒子的速度和位置;

步驟 6如果滿足結束條件,執行步驟7,否則執行步驟2;

步驟 7輸出優化參數選擇方案。

2.4 混合流量預測

對于進行相空間重構后的近似時間序列和細節時間序列,本文分別采用不同的訓練預測模型對其進行分析處理。針對具有混沌特征的細節時間序列,采用混沌模型對其進行訓練預測,得到預測序列。對于近似時間序列,采用ELM神經網絡進行訓練預測。ELM神經網絡是一類單隱層前饋神經網絡,以函數逼近理論為基礎,訓練時隨機地選擇輸入權值,通過解析的方法確定輸出權值,可以極大地提高人工神經網絡的收斂速度,具有訓練簡潔、結構簡單、學習收斂速度快等優點。

將經過混沌模型處理后的細節時間序列和經過ELM神經網絡處理后的近似時間序列進行線性疊加即可得到預測序列。

3 性能評估與分析

為了驗證本文提出的VNTR-HTP方法性能,本節設計了兩組仿真實驗。第1組仿真實驗驗證了流量預測算法HTP-POS的性能,第2組仿真實驗驗證了虛擬網絡拓撲重構方法VNTR-HTP的性能。

3.1 仿真環境設置

本文的仿真實驗在Windows7操作系統中進行,CPU是Intel(r)Core(TM)i7-4510 @ 2.60GHz,RAM是8.00G,分析軟件為Matlab2017a。

設置虛擬網絡包含20個節點和80條鏈路,虛擬鏈路帶寬設置為[0.3, 0.5]Gbps。以1s為間隔對實際網絡流量lbl-tcp-3.tcp[15]進行采樣,得到初始網絡流量序列,虛擬網絡每組節點對之間的流量從該初始序列中隨機連續選擇。

設置嵌入維數m的范圍為[5, 25],延遲時間τ的范圍設為[1, 10]。鏈路利用率上限閾值WH設為0.8,下限閾值WL設為0.2。設置流量預測誤差閾值為0.04。為消除隨機因素對實驗結果的干擾,運行10次仿真實驗,并取平均值作為最終輸出結果。

3.2 流量預測算法性能仿真

3.2.1HTP-POS算法性能驗證

首先,利用本文提出的HTP-POS算法對200～800s內的流量進行預測,分析HTP-POS算法的性能,結果如圖5和圖6所示。

圖5 真實流量與預測流量對比

圖6 網絡流量序列的預測誤差

從圖5可以看出,流量預測序列與真實序列可以精準擬合。HTP-POS算法通過小波分解將混沌序列分解為近似時間序列和細節時間序列,用不同的訓練模型對兩個序列進行分別處理,實現了網絡流量的精準預測,得到了良好的預測結果。從圖6可以看出,雖然訓練樣本經過相空間重構與參數優化選擇,但是在受到噪聲影響或者出現突發性流量序列時,仍然會存在一定的預測誤差。并且,HTP-POS算法預測的網絡流量誤差值最大為0.035左右,在可接受范圍內。

3.2.2 不同流量預測算法性能對比

本文選取均方誤差(meansquareerror,MSE)、誤差平方和(sumofsquarederror,SSE)和平均絕對相對誤差(meanabsoluterelativeerror,MARE) 3個指標衡量算法預測精度,具體定義如下:

(2)

(3)

(4)

為全方位評價HTP-POS算法性能,本文針對同一網絡流量序列,選取文獻[9]提出的ARMA算法、文獻[14]提出的基于SVM和ARIMA的組合算法和文獻[15]提出的基于RBF的流量預測算法作為對比算法對比分析HTP-POS算法的性能,結果如表1所示。

表1 不同流量預測算法性能比較

由表1可以看出,本文提出的HTP-POS算法具有較小的預測誤差且運行時間最短。HTP-POS算法通過小波分解方法分解流量序列,利用基于粒子群優化的相空間重構方法構建具有足夠特征的訓練樣本,提高了算法預測精度。基于混沌模型和ELM神經網絡的流量預測模型具有訓練速度快、預測精度高等優點,在保證預測精度的同時減少算法運行時間,提高了流量預測效率。文獻[9]提出的ARMA算法僅利用單一的ARMA模型進行流量預測,運行時間較短,但預測誤差較大。文獻[14]提出的組合算法融合了Morlet-SVR和ARIMA算法的優點,預測精度高于ARMA算法,但是其復雜度較高。文獻[15]提出的基于RBF的流量預測算法利用前饋型的RBF神經網絡對降噪后的流量序列進行分析預測,算法性能優于ARMA算法,但其運行時間長,預測效率較低。綜合比較4種算法的預測誤差和運行時間可知,HTP-POS算法在保證預測精度的同時降低了算法運行時間,提高了虛擬網絡拓撲重構效率。

3.3 虛擬網絡拓撲重構方法性能仿真

3.3.1 不同虛擬網絡拓撲重構方法性能比較

本節在相同環境下對比分析本文提出的VNTR-HTP方法與文獻[8]提出的IW方法的性能，結果如圖7所示。

圖7 不同拓撲重構方法節省的帶寬資源對比

從圖7可以看出,IW方法在進行拓撲重構時為了避免乒乓效應,在一段時間內不刪除新構建的虛擬鏈路,一些帶寬利用率較低的虛擬鏈路將長期占用帶寬資源,導致資源浪費,節省的帶寬資源較少。VNTR-HTP方法引入流量預測功能,利用混合流量預測算法對下一周期的流量進行預測,根據預測結果進行拓撲重構,節省了更多的帶寬資源。

3.3.2 鏈路利用率閾值設置對VNTR-HTP方法性能影響

本小節仿真模擬在設置不同鏈路利用率閾值時,VNTR-HTP方法節省的帶寬資源變化情況。鏈路利用率閾值上限WH分別為0.7、0.8和0.9,利用率閾值下限WL為0.2時,VNTR-HTP方法節省的帶寬資源變化情況如圖8所示。

圖8 不同WH時VNTR-HTP方法節省的帶寬

從圖8可以看出,隨著WH的增大,節省的帶寬資源逐漸增大。當WH增大時,擁塞的虛擬鏈路數量減少,每條虛擬鏈路有更多的資源可以用來承載從帶寬利用率低的虛擬鏈路上遷移過來的流量,從而節省更多的帶寬資源。鏈路利用率閾值上限WH為0.8,利用率閾值下限WL分別為0.1、0.2和0.3時,VNTR-HTP方法節省的帶寬資源變化情況如圖9所示。

圖9 不同WL時VNTR-HTP方法節省的帶寬

從圖9可以看出,隨著WL的增大,節省的帶寬資源也隨之增加。隨著WL逐漸增大,有更多的虛擬鏈路滿足鏈路刪除的條件,刪除的虛擬鏈路數量隨之增加,釋放的帶寬資源也隨之增多。

4 結 論

針對目前虛擬網絡控制平臺在構建虛擬網絡時為了滿足用戶動態變化的帶寬需求,通常直接把虛擬鏈路帶寬設置為流量最大值的問題,本文提出了一種基于混合流量預測的虛擬網絡拓撲重構方法,利用基于參數優化選擇的混合流量預測算法對下一周期的網絡流量進行預測,根據流量預測結果進行虛擬網絡拓撲重構。仿真結果表明,HTP-POS算法在保證預測精度的同時,運行時間更短,預測效率更高,VNTR-HTP方法可以節省更多的帶寬資源。下一步將在虛擬網絡拓撲重構的基礎上研究流量動態遷移策略,進一步提高網絡資源利用率。