基于流式計算的網(wǎng)絡(luò)排隊時延預(yù)測技術(shù)研究

王 亮,王 敏,王曉鵬,羅 威,馮 瑜

(1.中國人民解放軍91054部隊,北京 102442; 2.中國艦船研究設(shè)計中心,武漢 430064; 3.武漢大學(xué) 電子信息學(xué)院,武漢 430072)

0 概述

服務(wù)質(zhì)量(Quality of Service,QoS)是網(wǎng)絡(luò)性能重要評價指標(biāo),網(wǎng)絡(luò)時延是服務(wù)質(zhì)量的基本度量[1-2]。由于網(wǎng)絡(luò)擁塞的客觀存在,通過增加帶寬對網(wǎng)絡(luò)性能的提升非常有限,因此網(wǎng)絡(luò)時延成為研究人員關(guān)注的重點。網(wǎng)絡(luò)時延是指報文或分組從網(wǎng)絡(luò)的一端傳送到另一端需要的時間,主要包括發(fā)送時延、傳播時延、處理時延和排隊時延。受流量測試技術(shù)限制,目前關(guān)于網(wǎng)絡(luò)時延的研究主要集中在對網(wǎng)絡(luò)流往返時間(Round-Trip Time,RTT)的粗粒度時延預(yù)測[3]上。網(wǎng)絡(luò)時延預(yù)測是根據(jù)歷史時延數(shù)據(jù)對網(wǎng)絡(luò)時延變化的預(yù)判,用來為網(wǎng)絡(luò)控制系統(tǒng)的變周期采樣提供采用區(qū)間參考,以及用于分析閉環(huán)控制系統(tǒng)穩(wěn)定性等。但端到端的時延預(yù)測容易忽略突發(fā)的、持續(xù)時間小于監(jiān)控粒度的網(wǎng)絡(luò)延時變化,且無法對時延較長的交換機進行預(yù)測,在實際應(yīng)用上存在一定局限性。

近年來,軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)和帶內(nèi)網(wǎng)絡(luò)遙測(In-band Network Telemetry,INT)技術(shù)[4-6]的快速發(fā)展使排隊時延等細(xì)粒度網(wǎng)絡(luò)時延的預(yù)測成為可能。交換機內(nèi)部排隊時延作為動態(tài)性最強的一類網(wǎng)絡(luò)時延[7]受到研究人員的廣泛關(guān)注。由于排隊時延由流量負(fù)載和可用帶寬決定,因此其成為評價帶寬利用率和擁塞級別的重要指標(biāo),同時也是路由策略度量標(biāo)準(zhǔn)。隨著網(wǎng)絡(luò)數(shù)據(jù)變化日趨復(fù)雜,網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)墓芾聿町愒絹碓酱?而網(wǎng)絡(luò)排隊時延由于時間粒度小,其變化規(guī)律更復(fù)雜,因此尋找更準(zhǔn)確和穩(wěn)定的時延預(yù)測模型成為亟待解決的問題。本文以校園網(wǎng)為研究對象,利用帶內(nèi)網(wǎng)絡(luò)遙測技術(shù)構(gòu)建基于長短期記憶(Long Short-Term Memory,LSTM)網(wǎng)絡(luò)的多時間尺度融合預(yù)測模型(LSTM-Merge),并在流式計算框架下對網(wǎng)絡(luò)排隊時延進行分析和預(yù)測。

1 研究基礎(chǔ)

網(wǎng)絡(luò)流量預(yù)測模型分為線性預(yù)測模型和非線性預(yù)測模型[8]。ARIMA模型[9]和卡爾曼濾波模型是典型的線性預(yù)測模型,使用該模型的前提是網(wǎng)絡(luò)流量具有線性寬、平、穩(wěn)過程的特征。然而隨著通信技術(shù)的發(fā)展,網(wǎng)絡(luò)流量特性趨于復(fù)雜,采用線性模型已難以描述真實網(wǎng)絡(luò)流量特征,因此,研究人員提出灰色模型[9]、小波預(yù)測模型[10]、神經(jīng)網(wǎng)絡(luò)預(yù)測模型[11]以及支持向量回歸模型[12]等非線性時間序列預(yù)測模型。其中,神經(jīng)網(wǎng)絡(luò)預(yù)測模型是常用的非線性模型之一[13]。文獻[14]對比了ANN、小波預(yù)測等無線網(wǎng)絡(luò)流預(yù)測器,認(rèn)為神經(jīng)網(wǎng)絡(luò)預(yù)測器比其他預(yù)測器表現(xiàn)更佳。文獻[15]結(jié)合小波分析與神經(jīng)網(wǎng)絡(luò)對短時交通流量進行預(yù)測并獲得較高預(yù)測精度。文獻[16]采用非線性RBF神經(jīng)網(wǎng)絡(luò)分位數(shù)回歸算法對公共自行車站點需求量進行預(yù)測,給出精度較高的自行車需求區(qū)間。

基于循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network,RNN)的方法常用于解決時間序列預(yù)測問題。在RNN模型中,時間前后關(guān)系的展開使得神經(jīng)網(wǎng)絡(luò)隱層單元可捕捉時間軸上下文關(guān)系[17]。然而由于時間軸上權(quán)重矩陣參數(shù)共享導(dǎo)致長時間變化下RNN捕捉的上下文關(guān)系有限,各時間點輸入對網(wǎng)絡(luò)自我學(xué)習(xí)的正面影響減弱,因此RNN模型的準(zhǔn)確性在長時間跨度下降低。LSTM網(wǎng)絡(luò)是一種改進的RNN,其通過選擇性記憶能在較長時間跨度下持續(xù)學(xué)習(xí)且避免梯度消失[18],對于網(wǎng)絡(luò)流這種具有長相關(guān)性的時間序列而言,可得到較好的預(yù)測效果。記憶單元是LSTM網(wǎng)絡(luò)中的重要部分,其內(nèi)部結(jié)構(gòu)如圖1所示。該結(jié)構(gòu)包括1個具有自循環(huán)連接的神經(jīng)元和與其相關(guān)的輸出門、輸入門及遺忘門。在無外界干擾的情況下,采用自循環(huán)連接結(jié)構(gòu),可在2個時間步之間保持記憶單元的狀態(tài)恒定。輸入門從外部獲取1個新時刻的輸入點,并將數(shù)據(jù)通過激活函數(shù)進行變換處理;輸出門對記憶單元內(nèi)部所有時間狀態(tài)信息整合計算后,輸出相應(yīng)的時間序列值;遺忘門調(diào)整記憶單元自循環(huán)連接,使其選擇記住或遺忘過去的狀態(tài),從而為輸入序列選擇最優(yōu)時間間隔[19-21]。

圖1 記憶單元內(nèi)部結(jié)構(gòu)Fig.1 Internal structure of memory unit

在記憶單元結(jié)構(gòu)中,若將輸入序列表示為X=(x1,x2,…,xn),各時刻隱層狀態(tài)表示為H=(h1,h2,…,hn),輸出序列表示為Y=(y1,y2,…,yn),則LSTM網(wǎng)絡(luò)計算預(yù)測值的過程如下:

1)輸入門輸出:

it=σ(Wixxt+Whht-1+Wicct-1+bi)

(1)

2)遺忘門輸出:

ft=σ(Wfxxt+Whhht-1+Wfcct-1+bf)

(2)

3)記憶單元更新:

(3)

4)輸出門輸出:

ot=σ(Woxxt+Whhht-1+Wocct-1+bo)

(4)

5)預(yù)測值輸出:

ht=ot°h(ct)

(5)

其中,σ和g為激活函數(shù),b為偏移量,°為哈達(dá)馬乘積,W表示各門控單元的循環(huán)權(quán)重,xt表示當(dāng)前輸入向量,ct表示記憶單元的當(dāng)前狀態(tài)。式(3)在接收輸入信息的同時,用ft°ct-1決定過去狀態(tài)ct-1被保留或遺忘的部分,用it°g(Wcxxt+Whhht-1+Wccct-1+bc)決定輸入被保留的部分。由式(4)得到下一個隱層的輸出,并通過式(5)對整個記憶單元內(nèi)部的計算過程進行整合更新最終輸出結(jié)果。

2 基于LSTM的多時間尺度融合預(yù)測模型

本文受文獻[22-23]啟發(fā),提出多尺度時間序列融合模型,采集不同時間尺度的數(shù)據(jù)作為各種LSTM模型的輸入,并將這些模型進行串聯(lián)。此外,文獻[22-23]中的模型主要分析天氣、節(jié)假日等外部因素,而本文模型主要考慮不同的時間段因素(如中午、傍晚和夜間),并將這一特征添加到數(shù)據(jù)源中,以提高模型在不同時間段的預(yù)測準(zhǔn)確性,解決了小粒度預(yù)測模型的適用性問題。本文所提多尺度融合預(yù)測模型結(jié)構(gòu)如圖2所示。其中,Scloseness為基本時間尺度的特征抽象,Sscale1為以n倍間隔在基本時間尺度上采樣的特征抽象,Sscale2為以m倍間隔在基本時間尺度上采樣的特征抽象,以此類推,SscaleN為以k倍間隔在基本時間尺度上采樣的特征抽象,其中n

圖2 多尺度融合預(yù)測模型結(jié)構(gòu)Fig.2 Multi-scale fusion prediction model structure

圖2中時序模型對時間序列數(shù)據(jù)以不同尺度前溯采樣,即各尺度都對應(yīng)相同的標(biāo)簽,從標(biāo)簽處開始以不同時間間隔對過去時間序列采樣,得到Scloseness(以基礎(chǔ)間隔采樣,即基本時間尺度的特征抽象)、Sscale1(以n倍基礎(chǔ)間隔采樣)、Sscale2(以m倍基礎(chǔ)間隔采樣)、SscaleN(以k倍基礎(chǔ)間隔采樣),全連接層對時間段因素進行抽象處理得到SEXT,再將不同尺度的時間序列數(shù)據(jù)融合,具體過程如圖3所示。

圖3 不同尺度前溯采樣過程Fig.3 Process of forward sampling at different scales

全連接層將不同神經(jīng)元數(shù)量的模型輸出統(tǒng)一為與標(biāo)簽一致的輸出。融合層將提取到的特征張量Scloseness,Sscale1,Sscale2,…,SscaleN,SEXT進行融合,且分別賦予不同權(quán)重,表達(dá)式如下:

Sout=WE°SEXT+WN°SscaleN+…+W2°Sscale2+

W1°Sscale1+Wcloseness°Scloseness

(6)

其中,權(quán)重W在訓(xùn)練階段不斷學(xué)習(xí)并調(diào)整到最優(yōu)。該過程是對各特征張量的進一步抽象處理。

本文對網(wǎng)絡(luò)排隊時延的預(yù)測屬于回歸問題,損失函數(shù)選用均方誤差(Mean Square Error,MSE),表示如下:

(7)

均方誤差又稱為L2損失(Quadratic Loss,L2 Loss),其主要利用歐氏距離衡量差異,適用于網(wǎng)絡(luò)時延這種隨機成分高導(dǎo)致異常點較多的數(shù)據(jù)源。采用L2正則化方法限制損失函數(shù)中的參數(shù)值,可防止時延預(yù)測模型過擬合。

多時間尺度融合預(yù)測模型中各處激活函數(shù)均為非線性,多時間尺度融合的LSTM模型主要有2種激活方式:1)記憶細(xì)胞中激活各輸入用Sigmoid函數(shù),如式(8)所示;2)激活循環(huán)層及全連接層用tanh函數(shù),如式(9)所示。

(8)

(9)

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

3.1 流式計算系統(tǒng)的構(gòu)建

為實現(xiàn)對短時預(yù)測技術(shù)在線測試,需采用流式計算平臺處理單向且連續(xù)到達(dá)的網(wǎng)絡(luò)數(shù)據(jù)包。本文模型有2個階段需使用流式計算:1)在預(yù)測前對帶內(nèi)網(wǎng)絡(luò)遙測獲取的數(shù)據(jù)包信息進行逐個轉(zhuǎn)換,使其符合預(yù)測模型的輸入要求;2)在線階段調(diào)用模型流式輸出預(yù)測結(jié)果。整個流式計算平臺的計算速度需快速準(zhǔn)確,才能及時為避免擁塞或動態(tài)路由規(guī)劃提供有效的時延信息。

由于Storm平臺能實時對消息進行逐一處理且速度為亞秒級,因此實時數(shù)據(jù)轉(zhuǎn)換階段采用Storm平臺完成。而Spark Streaming可整合到基于數(shù)據(jù)并行的Spark生態(tài)系統(tǒng)中,其為流式計算與機器學(xué)習(xí)提供了多樣、穩(wěn)定和高效的解決方案接口,并支持用同樣的代碼和系統(tǒng)實現(xiàn)離線與在線分析,因此流式預(yù)測階段使用Spark平臺。本文所構(gòu)建基于流式計算平臺的預(yù)測系統(tǒng)結(jié)構(gòu)如圖4所示。

圖4 基于流式計算平臺的預(yù)測系統(tǒng)結(jié)構(gòu)Fig.4 Prediction system structure based on stream computing platform

3.2 結(jié)果分析

3.2.1 不同融合尺度下的預(yù)測準(zhǔn)確性

為得到不同融合尺度下的預(yù)測準(zhǔn)確性,將無融合、2種時間尺度融合、3種時間尺度融合的LSTM模型預(yù)測結(jié)果進行對比,不同時間尺度融合的最優(yōu)訓(xùn)練超參數(shù)設(shè)置情況如表1～表3所示。其中:無融合模型僅利用近期相關(guān)的過去時間序列進行預(yù)測,預(yù)測范圍取最小采樣間隔300 ms;超參數(shù)中back為前溯時間點數(shù);back 1與back 2分別為其他尺度的前溯時間點數(shù);interval為對最近期依賴的采樣倍數(shù);在LSTM模型與全連接層Dense之間采用Dropout算法,以一定概率暫時舍棄神經(jīng)元,同時對LSTM模型中權(quán)重進行正則化處理,防止神經(jīng)網(wǎng)絡(luò)過擬合。

表1 無融合最優(yōu)訓(xùn)練超參數(shù)設(shè)置Table 1 Optimal training super parameter setting without fusion

表2 2種時間尺度融合最優(yōu)訓(xùn)練超參數(shù)設(shè)置Table 2 Optimal training super parameter setting with two time scales fusion

表3 3種時間尺度無融合最優(yōu)訓(xùn)練超參數(shù)設(shè)置Table 3 Optimal training super parameter setting with three time scales fusion

圖5為無融合、2種時間尺度融合、3種時間尺度融合的LSTM模型預(yù)測結(jié)果對比情況?？梢钥闯?采用3種時間尺度融合的LSTM模型平均相對誤差(Mean Relative Error,MRE)最小,即預(yù)測效果最好。但多尺度疊加意味依賴時間延長,即犧牲實時性來提高準(zhǔn)確性,若取2種時間尺度疊加的LSTM模型,則會提高實時性并降低準(zhǔn)確性。

圖5 不同時間尺度融合LSTM模型預(yù)測結(jié)果的對比Fig.5 Comparison of prediction results of LSTM models with different time scales fusion

3.2.2 不同預(yù)測范圍下的均方根誤差

將多時間尺度融合的LSTM-Merge模型與無融合LSTM模型、支持向量回歸SVR模型、參數(shù)ARIMA模型在0.3 s、0.6 s、0.9 s、1.2 s、1.5 s這5種預(yù)測范圍下的均方根誤差(Root Mean Square Error,RMSE)進行對比,結(jié)果如圖6所示?？梢钥闯?多時間尺度融合的LSTM-Merge模型預(yù)測準(zhǔn)確度最好;參數(shù)ARIMA模型預(yù)測準(zhǔn)確度明顯低于其他預(yù)測模型,說明參數(shù)模型在數(shù)據(jù)源規(guī)律復(fù)雜時的準(zhǔn)確度不如機器學(xué)習(xí)模型;所有模型的預(yù)測范圍越大準(zhǔn)確性越低,但多時間尺度融合模型在增大預(yù)測范圍時RMSE上升最緩慢,說明預(yù)測范圍的增加對多時間尺度融合模型的準(zhǔn)確性影響最小。在閉環(huán)控制系統(tǒng)中,系統(tǒng)的決策時間與預(yù)測范圍越接近,決策效果越好。

圖6 不同預(yù)測范圍下4種模型的RMSE對比Fig.6 Comparison of RMSE of four models under different prediction ranges

4 結(jié)束語

針對網(wǎng)絡(luò)排隊時延的細(xì)粒度特性,本文在軟件定義網(wǎng)絡(luò)和帶內(nèi)網(wǎng)絡(luò)遙測技術(shù)的基礎(chǔ)上,建立基于LSTM的多時間尺度融合LSTM-Merge預(yù)測模型,利用流式計算框架對網(wǎng)絡(luò)排隊時延進行預(yù)測,并分析了不同時間尺度融合LSTM模型的預(yù)測結(jié)果。實驗結(jié)果表明,3種時間尺度融合模型較其他數(shù)目時間尺度融合模型所得預(yù)測結(jié)果的實時性更好且準(zhǔn)確性更高。與LSTM、SVR等預(yù)測模型相比,LSTM-Merge模型所得預(yù)測結(jié)果更精準(zhǔn)。下一步將在預(yù)測更大規(guī)模網(wǎng)絡(luò)時延時引入自編碼降維模塊,實現(xiàn)對時間序列矩陣的有效降維。