劉佳美,徐巧枝

(內(nèi)蒙古師范大學 計算機科學技術(shù)學院,呼和浩特 010022)

0 概述

軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)是一種將網(wǎng)絡(luò)控制和轉(zhuǎn)發(fā)功能相分離的新型網(wǎng)絡(luò)架構(gòu)[1],其可簡化網(wǎng)絡(luò)管理,提高網(wǎng)絡(luò)的可編程性和靈活性。近年來,隨著機器學習技術(shù)的快速發(fā)展,研究人員開始嘗試在SDN中引入機器學習方法,以提高網(wǎng)絡(luò)管理和控制效率,解決傳統(tǒng)方法中依賴配件、配置復雜的問題。

分布式SDN的架構(gòu)包括扁平式和層次式[2]2種方式,其中,扁平式架構(gòu)將整個網(wǎng)絡(luò)劃分為若干個SDN子域,每個子域內(nèi)分配一個控制器負責集中管理域內(nèi)交換機,且多個控制器被分別部署在不同的子域內(nèi),從而構(gòu)建一個邏輯上集中、而物理位置上分布的SDN架構(gòu),如Onix[3]、Hyperflow[4]等。在扁平式架構(gòu)下,主要采用交換機遷移和重定向流的策略[5]來平衡多個控制器之間的負載,以減輕控制器的負載,但是頻繁遷移交換機將會增加網(wǎng)絡(luò)延遲和開銷,降低網(wǎng)絡(luò)性能。層次式架構(gòu)將控制平面劃分為垂直的層次,常見的方式為將控制器分為普通控制器和全局控制器兩層[6-7],或者在控制器和交換機之間增加一個中間層[8],但是這些方案均未對全局控制器或者中間層控制器的過載問題進行深入研究和解決。

文獻[9]提出了SHLB模型,在控制平面與數(shù)據(jù)平面之間插入一個中間層,在中間層采用分流策略將不同類型的數(shù)據(jù)流傳輸給不同類型的控制器,可有效緩解控制平面負載不均的問題,并采用文獻[10]中的實時調(diào)度策略解決中間層過載問題。但是全局控制器在發(fā)現(xiàn)某個控制器資源負載過輕或過重時,需要合并或者開啟新的控制器,在此過程中,將會涉及大量流控制策略的遷移,造成網(wǎng)絡(luò)延遲的增加,從而影響網(wǎng)絡(luò)性能。

與以往的單邊研究思路不同,本文在提出網(wǎng)絡(luò)流量預測算法后,通過收集不同的網(wǎng)絡(luò)參數(shù),在SHLB模型的基礎(chǔ)上對其進行改進,并提出基于最大熵和隱馬爾科夫算法的流量預測與多控制器預部署PPME模型。該模型基于捕獲的歷史數(shù)據(jù)流,利用最大熵算法預測未來一段時間內(nèi)數(shù)據(jù)流的分布,從而產(chǎn)生控制平面內(nèi)各類控制器的預部署方案,加入隱馬爾科夫鏈對預測方案進行優(yōu)化,并采用增強學習算法對實際數(shù)據(jù)流與預測數(shù)據(jù)流進行比較。

1 相關(guān)工作

1.1 SHLB模型

SHLB模型是一個可擴展的、分層的SDN控制平面負載均衡模型,該模型在控制平面與數(shù)據(jù)平面之間增加一個中間層,將SDN網(wǎng)絡(luò)分為控制層、中間層和數(shù)據(jù)層三層。控制層包含若干個控制器,其接收中間層轉(zhuǎn)發(fā)的數(shù)據(jù)流,按照設(shè)定規(guī)則對數(shù)據(jù)流進行處理,并將處理結(jié)果反饋給中間層。中間層接收到數(shù)據(jù)層交換機的消息流后,按類別或者其他規(guī)則將其轉(zhuǎn)發(fā)給某個控制器,再接收該控制器的處理結(jié)果并通知其相應(yīng)的交換機。數(shù)據(jù)層由大量的SDN交換機組成,其將無法處理的數(shù)據(jù)流轉(zhuǎn)發(fā)給中間層,接收中間層的處理結(jié)果并更新流表規(guī)則。SHLB模型架構(gòu)如圖1所示。

圖1 SHLB模型架構(gòu)Fig.1 SHLB model architecture

SHLB模型控制層中的控制器按角色可分為全局控制器和局部控制器,其中,全局控制器負責保障控制層的負載均衡,并對局部控制器進行動態(tài)調(diào)整。局部控制器一方面接收、處理與響應(yīng)中間層的數(shù)據(jù)流和請求,另一方面需周期性地向全局控制器報告實時的資源利用率并接收其命令。

從細粒度的時間點來看,網(wǎng)絡(luò)流是一個不斷變化的動態(tài)變量,但是從一個時間范圍來看,其又是相對穩(wěn)定的。如果負載均衡模型只基于當前時間點考慮這種變化,而不考慮未來數(shù)據(jù)流的變化趨勢,可能會造成控制器的低性價比遷移,即這種遷移并不能保證一定時間段內(nèi)網(wǎng)絡(luò)性能的整體提高,而只對當前突發(fā)的網(wǎng)絡(luò)數(shù)據(jù)流提供幫助,可能造成整體網(wǎng)絡(luò)延遲的增加。為了解決該問題,本文提出了PPME模型,采用增強學習算法對實際數(shù)據(jù)流與預測數(shù)據(jù)流進行比較,若偏差大于設(shè)定閾值,則重新生成部署方案;否則,仍采用舊方案。在方案運行期間,控制器不再進行遷移,以降低遷移對網(wǎng)絡(luò)性能的影響。

1.2 最大熵原理

最大熵模型[11]是一種對數(shù)線性模型,其是在給定事件集上挖掘潛在約束條件,并在樣本數(shù)據(jù)有限的情況下,選取一種能夠滿足已知約束條件,且盡可能使未知事件均勻分布的恰當模型。最大熵模型是采用概率估計的方法,基于信息熵理論[12]而建立起來的概率統(tǒng)計模型。信息熵作為一個隨機事件不確定性的度量,隨機事件越不確定,則其熵越大;若隨機事件退化為確定事件,則其熵為0。隨機變量X的信息熵可以被定義為:

定義1假設(shè)X={x1,x2,…,xn}是一個離散隨機變量,則其熵H(X)表示為:

(1)

其中,n為離散隨機變量可取值的總數(shù)量,pi=P{X=xi}表示X取值為xi的概率,若某一項pi=0,即X取值為xi的概率為0。

定義2隨機變量X與Y的聯(lián)合分布形成的聯(lián)合熵用H(X,Y)表示,則其條件熵為:

(2)

定義3假設(shè)p(x)、q(x)是X中取值的2個概率分布,則p對q的相對熵為:

(3)

隨機變量X與Y的互信息定義為X與Y的聯(lián)合分布和獨立分布乘積的相對熵,分別如下所示:

I(X,Y)=D(P(X,Y)‖P(X)P(Y))

(4)

(5)

1.2.1 最大熵迭代算法

最大熵迭代算法具體步驟為:

輸入特征函數(shù)f1,f2,…,fn

輸出最優(yōu)參數(shù)值w*,最優(yōu)模型Pw

2)更新wi值,wi←wi+?i。

步驟2如果不是所有的wi都收斂,則重復步驟1。

近年來,最大熵算法不僅被廣泛應(yīng)用于機器翻譯、詞性標注、語法分析與文本分類等領(lǐng)域[13-15],還被應(yīng)用于構(gòu)建預測模型。文獻[16]運用最大熵算法預測在RCP2.6和RCP8.5 2個未來氣候變暖的情景下,水楊柳在云南省的潛在分布情況。文獻[17]采用最大熵原理構(gòu)建流量預測算法,根據(jù)歷史預測誤差對各種單一預測算法進行取舍,最終得到預測結(jié)果的分布情況。通過對實際網(wǎng)絡(luò)流量進行預測與測量,結(jié)果發(fā)現(xiàn),與其他預測算法相比,最大熵算法具有較高的預測精度,且預測結(jié)果更合理。

網(wǎng)絡(luò)流量會隨著時間和空間不斷發(fā)生變化。在時間維度上,網(wǎng)絡(luò)流量會隨著一天中的不同時段發(fā)生變化,比如白天的流量高于夜晩的流量,此外,網(wǎng)絡(luò)流量還可能在極短的時間內(nèi)發(fā)生劇烈變化[18]。本文提出的PPME模型在SDN控制層中利用最大熵算法,通過歷史網(wǎng)絡(luò)流量預測未來網(wǎng)絡(luò)流量,從而實現(xiàn)對控制器的預部署,以降低控制器遷移的頻率,提高網(wǎng)絡(luò)性能。

1.2.2 隱馬爾科夫算法

隱馬爾科夫算法[19-20]廣泛應(yīng)用于語言識別、強化學習和生物信息學等領(lǐng)域。隱馬爾科夫算法是一個有限離散時間的馬爾科夫模型,該模型假設(shè)系統(tǒng)是一個具有隱狀態(tài)的馬爾科夫過程。它可以被定義為一組λ=(Π,A,B),Π是初始概率分布,A是轉(zhuǎn)移概率矩陣,B是一個觀測概率序列(發(fā)射概率)。具體來說,一個隱馬爾科夫算法是由以下要素[21]定義的:

1)Q={q1,q2,…,qN}是一組狀態(tài),其中,N為隱藏狀態(tài)的數(shù)量,qt為t時刻的隱藏狀態(tài)。

2)O={o1,o2,…,oT}是一組觀測值,其中,T是觀測值的數(shù)量,oT是T時刻的可觀測狀態(tài)。每個觀測狀態(tài)都來源于一個詞匯表V={v1,v2,…,vM},其中,M為觀測值的數(shù)量。

3)A={a11,a12,…,aN1,…,aNN}是一個N×N的轉(zhuǎn)移概率矩陣。aij(1≤i,j≤N)表示狀態(tài)i變?yōu)闋顟B(tài)j的概率,具體表示方法為:

aij=P(qt+1=sj|qt=si)

(6)

aij≥0,?i,j

(7)

(8)

隱馬爾科夫算法的狀態(tài)圖如圖2所示,其中,Hi(i=1,2,…,T)為隱藏狀態(tài)集合,Oi(i=1,2,…,T)為觀測值集合。馬爾科夫過程位于可觀測狀態(tài)之上,由當前狀態(tài)決定,A只能觀測Oi,且Oi由馬爾科夫過程和B的隱狀態(tài)決定。

圖2 隱馬爾科夫算法狀態(tài)圖Fig.2 State diagram of hidden Markov algorithm

2 本文模型設(shè)計

針對傳統(tǒng)方法不能對網(wǎng)絡(luò)流量的變化特征進行準確描述,且預測精度較低的問題,本文提出PPME模型,該模型在控制層引入最大熵和隱馬爾科夫算法,通過學習歷史數(shù)據(jù)流來預測未來一段時間的數(shù)據(jù)流,從而提前部署控制器,以減少控制器的遷移次數(shù),縮短網(wǎng)絡(luò)延遲。PPME模型的設(shè)計總共分為3個部分,首先,收集歷史網(wǎng)絡(luò)數(shù)據(jù)流并對其進行分類。其次,利用最大熵算法對未來網(wǎng)絡(luò)流進行預測,并產(chǎn)生預測結(jié)果,最后,利用隱馬爾科夫算法對預測結(jié)果進行評估,優(yōu)化控制器部署。

2.1 數(shù)據(jù)流收集與分類

2.1.1 數(shù)據(jù)預處理

本文從 MAWI Working Group獲取了12月×30天×24小時的流量集,該流量集已被廣泛應(yīng)用于流分類,可以幫助研究人員評估其流量檢測方法[22]。數(shù)據(jù)集中的數(shù)據(jù)特征包括產(chǎn)生數(shù)據(jù)包的時間、傳輸控制層的協(xié)議、目標地址、發(fā)送地址以及數(shù)據(jù)包配置信息(數(shù)據(jù)包大小、端口號與MAC地址)等。對于本文來說,影響流量預測的主要因素是數(shù)據(jù)包的數(shù)量、時間和協(xié)議類型,因此,PPME模型以數(shù)據(jù)包大小、數(shù)據(jù)包協(xié)議名稱和時間作為特征值,通過對數(shù)據(jù)進行整理,生成了網(wǎng)絡(luò)流數(shù)據(jù)矩陣,具體如圖3所示,其中,行表示每秒內(nèi)各個協(xié)議數(shù)據(jù)包的數(shù)量,列表示各種協(xié)議類型。在單位時間內(nèi),不同協(xié)議的數(shù)據(jù)流數(shù)量差別較大,如圖4所示,其中,HTTP數(shù)據(jù)流最多,且HTTPS、UDP和ICMP數(shù)據(jù)流相差不大,而IPv6、UDPv6及其他數(shù)據(jù)流較少,利用該流量分布指導控制層中控制器的分類及部署。

圖3 網(wǎng)絡(luò)流數(shù)據(jù)矩陣Fig.3 Network flow data matrix

圖4 各種協(xié)議數(shù)據(jù)流的分布Fig.4 Distribution of various protocol data flows

2.1.2 數(shù)據(jù)流分類

關(guān)于數(shù)據(jù)流的分類,部分研究采用機器學習的方法,如文獻[23]提出的TrAdaBoost模型,其是AdaBoost模型的改進,在解決多級網(wǎng)絡(luò)流量的分類方面具有較好的性能。實驗比較了TrAdaBoost模型與本文模型對所得數(shù)據(jù)流的識別效果,如表1所示。從表1可以看出,在準確度與所需時間方面,本文PPME模型更具有優(yōu)勢。

表1 TrAdaBoost模型與本文模型的比較Table 1 Comparison between TrAdaBoost model and the proposed model

2.2 數(shù)據(jù)流預測

在了解一個隨機事件的概率分布時,預測滿足所有的約束且不進行任何條件下的主觀假設(shè),概率分布最均勻時預測風險最小,從而得到概率分布的熵最大,即最大熵數(shù)學模型。因為網(wǎng)絡(luò)流復雜多變,且很多人為的主觀預測很難得到驗證,通過客觀的歷史數(shù)據(jù)構(gòu)造概率矩陣,以求得最大熵情況下的概率矩陣作為當時的預測結(jié)果,可以最大程度地提高預測的準確性。

由于數(shù)據(jù)包的數(shù)量能夠客觀反映數(shù)據(jù)流量,因此PPME模型將數(shù)據(jù)包的數(shù)量和數(shù)據(jù)包的協(xié)議類型作為主要特征參數(shù),并設(shè)計了數(shù)據(jù)流預測算法,數(shù)據(jù)流預測算法為基于最大熵的網(wǎng)絡(luò)流預測算法,其中,G為數(shù)據(jù)包矩陣,N為數(shù)據(jù)包總數(shù),Z為概率矩陣,E為最小常數(shù)誤差。最大熵網(wǎng)絡(luò)流預測算法的具體步驟為:

步驟1將訓練矩陣轉(zhuǎn)化為概率矩陣,即Z(i,j)=G(i,j)/N。

步驟2將訓練矩陣乘以其轉(zhuǎn)置矩陣,得到概率方陣,即Z1=Z0×Z0T。

步驟3對概率方陣進行迭代冪運算,Z2=Z1×Z1T,Z3=Z2×Z2T,…,Zn=Zn-1×Zn-1T。

步驟4計算方差|Zn-Zn-1|,直到方差小于設(shè)置的常數(shù)E,則結(jié)果收斂,且在該結(jié)果上進行預測時產(chǎn)生的誤差最小;否則重復步驟3。

在最大熵算法中,通過將訓練矩陣乘以訓練矩陣的轉(zhuǎn)置矩陣可以得到一個概率方陣,通過對該概率方陣進行迭代冪運算,最終可得到一個趨于穩(wěn)定的各種協(xié)議數(shù)據(jù)流量的比例關(guān)系。根據(jù)該比例關(guān)系對控制器進行預部署,可以提高控制器的利用率,降低控制器遷移過程對網(wǎng)絡(luò)運行的影響,從而提高網(wǎng)絡(luò)性能。

2.3 預測結(jié)果的優(yōu)化

由于最大熵算法的計算量非常龐大,目前還沒有有效的方法能徹底解決其計算復雜度問題,導致PPME控制器預部署方案的生成需要花費較長時間,對于合理的部署方案,盡可能延長其工作時間是非常有必要的。通過對預測流量與實際流量進行擬合,結(jié)果發(fā)現(xiàn),最大熵算法的預測結(jié)果在一段時間內(nèi)具有較為穩(wěn)定的預測準確度,如圖5所示。最大熵算法在模擬流量曲線的過程中,流量變化曲線的導數(shù)越大,則算法的預測準確度越低,且時效性越差。在理想條件下,導數(shù)為0且流量曲線不變化時是預測算法的理想狀態(tài),但是對于網(wǎng)絡(luò)流來說,其流量曲線在不斷變化,幾乎不可能出現(xiàn)導數(shù)為0的情況,因此單一的最大熵算法無法滿足較長時間的預測準確度。為了解決該問題,PPME模型在控制層引入了隱馬爾科夫鏈,利用隱馬爾科夫的五元組(隱含狀態(tài)S,觀測狀態(tài)O,初始狀態(tài)概率矩陣P、隱含狀態(tài)轉(zhuǎn)移概率矩陣M,觀測狀態(tài)轉(zhuǎn)移概率矩陣K),通過對不同階段的預測結(jié)果給予獎勵或懲罰,并對歷時較長的隱馬爾科夫過程給予γ平方衰減,以降低其權(quán)重。

圖5 單一最大熵算法的預測準確度隨時間的變化曲線Fig.5 Change curve of prediction accuracy of the single maximum entropy algorithm over time

不同階段的訓練獎勵機制可以在很大程度上提高最大熵算法預測結(jié)果的準確度。通過對每個階段的數(shù)據(jù)進行最大熵預測,極大地減少了最大熵算法的運算量,提高了運算效率。

在部署周期優(yōu)化算法中,設(shè)置初始指數(shù)W0為1 000,警戒比例K0為0.618,阻尼指數(shù)K2為1,假設(shè)矩陣Z有n行、m列,其具體步驟為:

步驟1對矩陣的每行進行遍歷,forxin range(n),x∈[0,n) 。

步驟2對矩陣的每列進行遍歷,foryin range(m),y∈[0,m) 。

步驟3初始化:令WX=W0。

步驟4加強學習,WX=WX+K2×Z[x,y]。

步驟5如果WX>K0×W0,保持使用原有預測方案,否則重新使用最大熵算法進行網(wǎng)絡(luò)流量預測,并部署控制器。

實驗驗證了加入隱馬爾科夫算法后的預測擬合效果,如圖6所示。使用單一的最大熵算法在前600 min內(nèi),預測準確度較高,但隨著時間的延長,預測準確度呈降低趨勢;加入隱馬爾科夫后該算法仍可以保持較高的預測準確度,這說明了本文算法通過不斷調(diào)整每個階段預測結(jié)果的準確度,可在多數(shù)情況下較準確地預測復雜場景下的網(wǎng)絡(luò)流量情況,優(yōu)化最大熵算法的預測結(jié)果。

圖6 最大熵算法加入隱馬爾科夫算法前后的網(wǎng)絡(luò)流量對比Fig.6 Comparison of network traffic before and after adding hidden Markov algorithm to maximum entropy algorithm

3 實驗結(jié)果評估

3.1 最大熵算法預測結(jié)果的準確度

本文對所采集的網(wǎng)絡(luò)流以8∶2的比例進行分割,分別作為訓練集和測試集。實驗將采用最大熵算法對訓練集中的數(shù)據(jù)進行訓練,并預測之后時間段的流量。通過比較預測結(jié)果與實際流量來評估最大熵算法預測結(jié)果的準確度。

本文以4個不同大小的數(shù)據(jù)集(流量包個數(shù)依次為12 104、63 741、180 040、623 120)為研究對象,實驗采用支持向量回歸(Support Vector Regression,SVR)模型、梯度提升回歸樹(Gradient Boosting Regression Tree,GBRT)模型與本文提出的PPME模型對其下一時刻流量值的預測情況與實際流量進行對比,如圖7所示。從圖7可以看出,對于不同的數(shù)據(jù)集,預測準確度存在差異,當數(shù)據(jù)量較小時,3種算法的預測準確度相差不大,且均能達到85%左右,但是隨著流量數(shù)據(jù)的增加,SVR模型和GBRT模型的預測誤差逐漸增大,而本文提出的PPME模型仍然保持較高的預測準確度,且最大熵的核心是收斂的,因此數(shù)據(jù)集的大小不會影響最大熵的準確度,在大型復雜的網(wǎng)絡(luò)場景下,最大熵算法的預測準確度較穩(wěn)定。

圖7 3種模型在不同數(shù)據(jù)集中預測準確度的對比Fig.7 Comparison of prediction accuracy of three models in different datasets

3.2 預部署的有效性

本文模型將不同協(xié)議的網(wǎng)絡(luò)流分配到相應(yīng)類型的控制器中進行處理,實驗采用與SHLB模型相同的計算機作為控制器,每個控制器所能裝載的數(shù)據(jù)包個數(shù)如圖8所示。從圖8可以看出,當數(shù)據(jù)流達到30 000個/s時,控制器負載率達到了80%,即認為控制器滿負載。因此,本文對每個控制器每秒最多分配30 000個數(shù)據(jù)包,然后再進行部署。

圖8 不同數(shù)量數(shù)據(jù)包的控制器負載率Fig.8 Controller load rates for different number of packets

圖9比較了PPME模型與SHLB模型部署的控制器個數(shù)。考慮到圖4所示的各協(xié)議數(shù)據(jù)包的分布情況,相比SHLB模型,PPME模型考慮了一段時間內(nèi)各類網(wǎng)絡(luò)流的整體情況,對于數(shù)據(jù)量巨大的HTTP數(shù)據(jù)流,PPME模型部署了多余的控制器,避免當HTTP數(shù)據(jù)流增加時控制器發(fā)生遷移,而對于數(shù)量相對較少的HTTPS、UDP及ICMP數(shù)據(jù)流則部署較少的控制器,避免了資源浪費,同時降低了控制器遷移的次數(shù)與頻率。

圖9 PPME模型與SHLB模型控制器分配情況對比Fig.9 Comparison of controller allocation between PPME model and SHLB model

在進行控制器分配后,對于多組數(shù)據(jù),實驗通過發(fā)送包工具發(fā)送不同速率的流量數(shù)據(jù)包對PPME模型和SHLB模型進行測試,中間層實體資源利用情況和網(wǎng)絡(luò)響應(yīng)時間如圖10和圖11所示。實驗結(jié)果表明,PPME模型在網(wǎng)絡(luò)發(fā)生特殊狀況后,系統(tǒng)的處理速度和性能均更好,且承受突發(fā)狀況的能力更強。

圖10 中間層內(nèi)存利用率Fig.10 Memory utilization of middle layer

圖11 中間層網(wǎng)絡(luò)響應(yīng)時間Fig.11 Response time of middle layer network

4 結(jié)束語

本文基于最大熵和隱馬爾科夫算法構(gòu)建了PPME模型,通過對不同類型的網(wǎng)絡(luò)數(shù)據(jù)包數(shù)量進行預測,為SDN模型中的控制器提供預部署方案的理論依據(jù)。PPME模型能夠?qū)崿F(xiàn)在復雜網(wǎng)絡(luò)情景下對流量的準確預測,同時,將網(wǎng)絡(luò)流量以協(xié)議類型進行分類,能夠達到對SDN中多控制器實現(xiàn)預部署的目的。實驗結(jié)果表明,PPME模型對網(wǎng)絡(luò)流量的預測準確度達到85%以上,實現(xiàn)了對SDN中控制器的預部署策略,有效緩解網(wǎng)絡(luò)中的擁堵問題,提高SDN環(huán)境中的資源利用率和控制器的工作效率,且保證了SDN控制網(wǎng)絡(luò)的穩(wěn)定性。下一步將在云環(huán)境下,將各控制器的決策控制情況匯報給云端,并在云端利用EM高斯方差進行聚類分析。