基于流式計算的網絡排隊時延預測技術研究

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

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

0 概述

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

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

1 研究基礎

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

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

圖1 記憶單元內部結構Fig.1 Internal structure of memory unit

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

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)預測值輸出:

ht=ot°h(ct)

(5)

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

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

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

圖2 多尺度融合預測模型結構Fig.2 Multi-scale fusion prediction model structure

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

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

全連接層將不同神經元數量的模型輸出統一為與標簽一致的輸出。融合層將提取到的特征張量Scloseness,Sscale1,Sscale2,…,SscaleN,SEXT進行融合,且分別賦予不同權重,表達式如下:

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

W1°Sscale1+Wcloseness°Scloseness

(6)

其中,權重W在訓練階段不斷學習并調整到最優。該過程是對各特征張量的進一步抽象處理。

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

(7)

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

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

(8)

(9)

3 實驗結果與分析

3.1 流式計算系統的構建

為實現對短時預測技術在線測試,需采用流式計算平臺處理單向且連續到達的網絡數據包。本文模型有2個階段需使用流式計算:1)在預測前對帶內網絡遙測獲取的數據包信息進行逐個轉換,使其符合預測模型的輸入要求;2)在線階段調用模型流式輸出預測結果。整個流式計算平臺的計算速度需快速準確,才能及時為避免擁塞或動態路由規劃提供有效的時延信息。

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

圖4 基于流式計算平臺的預測系統結構Fig.4 Prediction system structure based on stream computing platform

3.2 結果分析

3.2.1 不同融合尺度下的預測準確性

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

表1 無融合最優訓練超參數設置Table 1 Optimal training super parameter setting without fusion

表2 2種時間尺度融合最優訓練超參數設置Table 2 Optimal training super parameter setting with two time scales fusion

表3 3種時間尺度無融合最優訓練超參數設置Table 3 Optimal training super parameter setting with three time scales fusion

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

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

3.2.2 不同預測范圍下的均方根誤差

將多時間尺度融合的LSTM-Merge模型與無融合LSTM模型、支持向量回歸SVR模型、參數ARIMA模型在0.3 s、0.6 s、0.9 s、1.2 s、1.5 s這5種預測范圍下的均方根誤差(Root Mean Square Error,RMSE)進行對比,結果如圖6所示。可以看出:多時間尺度融合的LSTM-Merge模型預測準確度最好;參數ARIMA模型預測準確度明顯低于其他預測模型,說明參數模型在數據源規律復雜時的準確度不如機器學習模型;所有模型的預測范圍越大準確性越低,但多時間尺度融合模型在增大預測范圍時RMSE上升最緩慢,說明預測范圍的增加對多時間尺度融合模型的準確性影響最小。在閉環控制系統中,系統的決策時間與預測范圍越接近,決策效果越好。

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

4 結束語

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