基于LSTM流量預測的路由規劃和切換

諸葛斌，王林超，宋楊，邵瑜，董黎剛，蔣獻

（浙江工商大學信息與電子工程學院（薩塞克斯人工智能學院），浙江 杭州 310018）

0 引言

運營商基于當前快速增長的網絡需求和日益復雜的網絡環境提出流量預測需求，OMC（operation and maintenance center）系統應支持基于歷史流量數據，通過大數據分析算法進行流量預測，即能根據當前軟件定義網絡（software defined network，SDN）[1]已有的歷史流量數據，結合監督學習、無監督學習等人工智能算法，快速全面預測整體網絡流量趨勢以指導網絡提前進行調整或擴容，并且幫助運營商提前進行大客戶流量營銷。

互聯網和通信設備的快速發展創造了更大、更復雜的網絡結構，網絡的復雜性導致大量流量數據的溢出，并且給網絡管理和流量優化帶來了挑戰，包括路由決策、負載均衡、擁塞控制等服務。同時，研究人員看到兩個可行的解決方案幫助更有效地管理網絡——SDN和機器學習。SDN為所有的網絡設備提供了一個集中的訪問和控制機制，SDN控制器不僅可以監視和測量各種網絡參數和度量，而且可以對資源分配和路由做出更明智和高效的決策，因為它可以全局地查看網絡中的所有內容。然而，SDN控制器接收的數據量可能非常大。雖然SDN控制器本身可以擴展，例如在云上運行它，但是仍然需要有效的算法從接收的數據中提取所需的測量和信息。這是機器學習可以很好輔助SDN的地方。許多流量分類和流量預測問題可以通過各種機器學習算法實現，在保持相對簡單設計的同時提高了系統性能。流量預測對SDN中路由決策、擁塞控制、負載均衡等服務的開展具有重大的促進作用，是一個基礎性的研究領域。

1 基于LSTM模型的流量預測算法設計

1.1 流量預測框架和機制

本文提出的SDN流量預測系統框架如圖1所示，所提的SDN體系架構是一種基于模型化的架構，各層提供的服務和功能均以元模型為基礎，通過資源組合滿足上層用戶的多元化需求。元業務中包含了上層應用的特性和要求，它可以根據應用的特性和要求抽象業務所需的最基本網絡服務功能。控制平面中預測模塊為整個系統的核心模塊，本文將深度學習模型應用到流量預測中進行網絡流量的預測和處理機制的研究，通過與其他各層的模塊進行交互，可以實現對轉發層的優化調度和靈活轉發。

圖1 基于SDN的流量預測框架

在轉發層，將物理設備虛擬化成一個資源池，再通過正交分解將轉發層虛擬化成各種邏輯功能塊，也就是元能力。與流量預測相關的模塊包括流量抓取模塊和轉發信息庫，流量抓取模塊負責抓取流量信息，并將信息發送至控制層中的流量統計模塊。轉發信息庫主要用于保存控制層中流與動作管理模塊下發的流表信息。

控制層中，流量統計模塊用于下發統計信息到流量抓取模塊，接收流量抓取模塊抓取的流量信息進行分析。然后發送至流量預測模塊，流量預測模塊通過深度學習算法對流量進行預測。然后將預測結果發送至結果分析模塊進行流量分析，分析結果分別發送給控制層的策略管理模塊和應用層的應用服務管理元業務模塊。策略管理模塊制定相應的策略發送給流與動作管理模塊。流與動作管理模塊將具體的策略下發至轉發層的轉發信息庫。

其中，應用層的元業務是一個單獨的微服務，它具有平臺無關性和可以支持獨立部署的特點。流量預測相關的業務主要包括應用服務管理模塊和應用處理模塊，應用服務管理元業務用于接收結果分析模塊得出流量分析結果。應用處理元業務用于接收應用服務管理元業務轉發的操作指令，對具體應用做出對應的操作。

SDN流量預測框架的流量預測機制是整個架構的核心部分，流量預測機制為流量預測系統提供了高效的防護策略。

1.2 數據預處理

目前，流量矩陣的估算主要依賴合成數據的流量矩陣評估某個算法的具體效果。幾乎沒有主流的機構可以提供流量矩陣的數據，直到 Uhilg等[2]公布了他們在歐洲探索與學習網 GEANT上獲得的真實可用的流量矩陣數據集。這份流量矩陣數據集囊括了 GEANT中全內部網關協議（Interior gateway protocol，IGP）的流量信息、抽樣了 NetFlow數據和邊界網關協議（border gateway protocol，BGP）路由信息一同建立的流量矩陣。真實公開的流量矩陣可以加強對真實流量矩陣及其動態性的理解。因此，本文采用了CEANT2上部署的25個節點，收集節點之間鏈路的流量作為數據集，然后通過流量數據測量和估算方法計算流量矩陣，再通過流量矩陣進行流量預測。

首先對數據集進行處理，因為下載的數據集以15 min為間隔，為期兩周左右的977個XML文件，每個XML文件中包含了25×25條流量信息。但是本文需要的數據集格式以不同的流劃分文件，每個文件包含了兩周時間內一條流以15 min為間隔的全部數據，文件輸出格式為常用數據集格式CSV。創建一個數組array=[]，設置文件的 path。讀取目錄下的文件名稱，存儲在變量files內。對files循環遍歷該目錄下的所有文件，每次循環調用dom.minidom.parse打開XML文件，打開文件之后通過 rootdata.get Elements By Tag Name 設置讀取范圍在標簽＜dst＞…＜/dst＞之間的元素。標簽內的即需要的流量數據。通過itemlist.firstChild.data[5]確定選擇每個XML文件中的第幾條數據，并將讀取出來的數據保存到數組中。使用to_csv函數將數組array=[]輸出CSV文件保存至相同目錄下。將數據拆分成訓練集和測試集，將第n_0～n_12個數字作為特征。第n_13個數字為標簽。依次循環累加x將第n_x個數字至第n_(x+12)個數字作為特征。第n_(x+13)個數字作為標簽，最后，返回x_train訓練集的特征，y_train測試集的標簽，x_test測試集的特征，y_test測試集的標簽。最后再將數據集進行標準化。

1.3 BL-LSTM模型搭建

人們對一個問題的思考不會從頭開始，如一個人能夠理解一篇文章是因為這個人已經有了一定的語言基礎，人能夠不斷地累積知識，是因為人能夠記憶一些已經學習過的知識。但是傳統的神經網絡做不到這一點，傳統的神經網絡對時序信息的預測和處理是非常困難的。如預測一句話的結尾，或者文章內容的下一段。雖然理論上遞歸神經網絡（recurrent neural network，RNN）可以處理這種“長依賴問題”，但在實際過程中RNN無法學習這種特征。Hochreiter[3]和 Bengio[4]深入研究過為什么RNN不能學習到該特征。于是長短期記憶（long short-term memory，LSTM）網絡——一種新的RNN模型應運而生。由于RNN絕大分都由相同的神經網絡復制鏈接而成，而神經網絡的結構非常簡單，LSTM 也具有這種鏈式結構，但是它不同于簡單的 RNN神經網絡單元里只有一個網絡層，LSTM的內部有4個網絡層。LSTM的核心是網絡單元設計，LSTM 的網絡單元設計類似一個細胞，一個網絡單元內的狀態傳輸結構簡單來說是由一個點乘器和一個加法器構成的，數據的傳輸過程像一個傳送帶，貫穿了整個細胞而且鮮有分支。一個LSTM里有3個門，而LSTM的細胞狀態是由這 3個門控制的。門是由一個sigmoid函數和一個點乘操作組合而成的。門的作用是為了對細胞狀態進行刪除和更改，sigmoid函數輸出的值在0～1，這表示有多少數據可以通過sigmoid層，0表示全丟棄，1表示全接受。LSTM細胞狀態如圖2所示。

圖2 LSTM狀態傳輸

本文基于 LSTM 模型[5]修改的深度學習模型BL-LSTM（based linear regression-LSTM），BL-LSTM算法模型如圖3所示。采用BL-LSTM進行SDN流量預測模型的搭建。具體來說由兩個部分組成，一個是LSTM網絡，另一個是線性回歸模型。LSTM網絡由m個堆疊的LSTM層組成，用于對網絡流量的時空特征進行建模。輸出層采用線性回歸模型計算未來的流量大小。

圖3 BL-LSTM算法模型

開始訓練模型時，不會直接把整個數據集導入模型中，而是使用batch的方式。深度學習的優化算法總的來說是梯度下降法，每次的權重和偏置更新可以分為以下兩種極端。第一種是遍歷完所有數據后再計算損失函數，然后根據新的參數計算新的梯度。這種方法因為數據集的增長和內存的限制，一次性導入整個數據集，變得非常困難。另一種是每次只訓練一個樣本，每載入一個數據就計算一次損失函數，然后求出梯度更新參數，這種方法雖然速度較快，但是收斂性能較差，可能在最優點附近來回移動，無法到達最優點。或者幾次參數的更新互相抵消最終導致目標函數的強烈震蕩，為了克服上述的兩種極端現象，一般采取折中的方法。

訓練模型時將數據分批次載入，這樣一批數據共同決定了梯度方向，方向不容易跑偏，降低了隨機性。另一方面因為一批內的樣本數與整個數據集相比小很多，計算量也大大減小。定義迭代變量 iterations，一個 iterations等于使用batch_size個樣本訓練一次。定義輪詢變量epochs，epochs被定義為向前和向后傳播所有批次的單次訓練迭代，這意味著一個 epoch是整個輸入數據的單次向前和向后傳遞。簡單來說，epoch指的是訓練過程中數據將要被輪詢多少次，即需要完整遍歷數據集多少次。如果 epoch數量太少，神經網絡就有可能發生欠擬合（即對定型數據的學習不夠充分），如果 epoch數量太多，則有可能發生過擬合（即神經網絡對定型數據中的“噪聲”而非信號進行擬合）。BL-LSTM模型搭建的流程如下。

步驟 1創建一個 ArgumentParser對象，添加參數并解析，設置一組特征數量lag為12。

步驟 2經過多次調試最終設置 batch值為256，設置epochs值為600。調用數據處理函數獲取x_train訓練集的特征和y_train訓練集的標簽。

步驟3對x_train進行reshape，將數據轉變為一列的三維數組。設置輸入層、隱藏層和輸出層的參數。

步驟4初始化一個順序模型，加入一個LSTM層，設置return_sequences=True，每個時間步都輸出ht?1。

步驟5將LSTM的輸出結果，輸出到多元線性回歸模型進行訓練。

步驟6獲得完整的模型，輸入測試集x_test，取得預測結果。

步驟7將歸一化后的結果轉化為原始數據。

2 基于流量預測的路由規劃和切換

傳統路徑切換主要為如何在限制條件完成最快的更新，如何解決網絡變化時流量波動等問題。

2.1 SDN路徑切換解決方案

針對多條路徑更新時，因為鏈路的帶寬限制使路徑切換后出現網絡擁塞的問題[9]，本文使用BP-ACO算法[10]進行路由規劃，GEANT獲得的流量矩陣作為數據集通過BL-LSTM算法進行訓練，預測后短時間內的流量趨勢。BP-ACO通過對流量預測的分析進行路由規劃避免流量擁塞，對這個問題本文通過上述基于LSTM模型的流量預測的方法進行處理。

針對域間路由更新導致流表部署時間不同的問題，以及網絡變化時會產生控制器下發的流表和交換機內實際接收到流表的不一致問題。

本文提出了一種新的方法解決SDN的一致性多交換機更新問題，方法是通過協調不同控制域內的控制器，中央控制器向各控制域下發流表，實現控制域的有序更新。但是域內的控制器向不同高質量的，多層虛擬交換機（open vSwitch，OVS）下發流表且OVS部署流表會產生不同的時延，導致轉發數據流時沒有流表而開始丟包。因為新的域內路由有空閑OVS，傳輸時延較低，傳輸過程中因為有一些數據包在鏈路傳輸，所以數據包傳輸失序。雖然失序現象可以通過傳輸控制協議（transmission control protocol，TCP）的重傳機制緩解，但是隨著數據發送速率的不斷上升，傳輸的數據包開始變大，隨機失序情況會越來越明顯。

為了解決域內的一致性問題，本文提出了一種新的方法，該方法通過在拆除現有路由之前檢查新路由的運行狀態。具體的識別過程是通過多播的方式向每一個既在新路徑又在舊路徑上的OVSCNi發送兩條相同的轉發流表。CNi收到相同的數據包之后確認當前網絡的新舊兩條鏈路都能正常轉發數據包，再斷開舊的鏈路。然后，新的路徑開始正式使用，最后將新的路徑剩余帶寬、吞吐量提交給控制器，控制器重新進行路由規劃。

2.2 無損路徑切換算法

一個OVS連接SDN控制器時，觸發Event OFPS witch Features事件，在事件內實例化一個連接 OVS到控制器的網橋，實例化并解析OpenFlow協議，創建一個匹配流表頭部的Match域，控制器向OVS發送報文，OVS接收報文后通過默認流表向控制器發送確認字符（acknowledge character，ACK），控制器通過收到的反饋報文，確認OVS和控制器建立連接。

SDN中央控制向所有只在新鏈路(Lnew)的控制器發送流表，OVS接收SDN控制器發送的流表后開始安裝收到的流表，OVS安裝完流表后發送ACK返回給控制器，中央控制器接收到所有 OVS的 ACK后開始下一步。

SDN中央控制向所有既在新鏈路(Lnew)又在舊鏈路(Lold)的控制器()發送流表，OVS接收SDN控制器發送的流表后開始安裝接收的流表，OVS安裝完流表后發送ACK確認報文返回給控制器，中央控制器接收所有OVS的ACK后開始下一步。

SDN控制器對所有域內鏈路，從遠到近發送多播信號，當R∩收到兩個相同的數據包時，確認兩條鏈路都可以正常工作，則斷開Lold鏈路中屬于本次轉發鏈路的部分。路徑切換流程如圖4所示。

圖4 路徑切換流程

2.3 基于多播的無損路徑更新技術

在SDN中，控制器可以刪除、添加或替換路由表中的源目流表。采取以多播的方式更新路徑，旨在最小化節點資源消耗和鏈路資源消耗總成本。本文通過使控制器向OVS下發相同的源目流表。然后數據包通過先進先出隊列（first input first output，FIFO）的方式沿著某一條路徑傳輸。如果兩個數據包P1、P2沿著同一條路徑傳輸，然后都經過了OVS交換機S1、S2。如果P1在P2之前遍歷S1，那么P1必須在P2之前遍歷S2。當Si≠Sd收到了流表之后，部署安裝流表，經過該OVS的數據包按照新的路由表開始轉發數據包。

SDN控制器可以指示 OVSSi向控制器轉發一段路徑中的所有數據包，通過對這段路徑中的Si打上標簽，在Si這些的路由表中添加一條轉發給控制器的流表。通過控制器識別數據包是否相同，而不是通過交換機Si識別。值得注意的是，只有整條轉發鏈路的最后一個OVS需要將數據包轉發給控制器，而不是轉發鏈路中的每一個OVS。因此，OVS的標準操作和OpenFlow命令可以支持多播轉發所需要的操作。多播傳輸中復制的數據包通過每個數據包的源地址和標識字段辨別。通過這個方法可以分辨當前數據包是多播傳輸中復制的數據包還是通過TCP重傳機制重新發送到Si的數據包。

本文介紹算法的一個例子，SSRU切換開始之前的網絡拓撲如圖5所示，其中，一次只建立(s,d)路徑的一個部分，并替代當前的等效部分。Dx表示一個域，Cx,x∈ { 0,1,2,… ,n}表示舊鏈路上的OVS，Ny,y∈ { 0,1,2,3,… ,n}表示新鏈路上的OVS，CNi:Cx=Ny，x∈ { 0,1,2,… ,n}表示既在新鏈路又在舊鏈路上的OVS。

圖5 SSRU切換開始之前的網絡拓撲

控制器查詢新舊兩條域間路徑上 OVS的dpid，如果找到兩組相同的dpid就可以確認該域處于新舊路徑的交點。首先，向只在新域間路徑的控制器下發流表，然后再部署域內OVS的流表。

切換從CNi下標最大的替換路徑開始，第一段需要切換的路徑N9～N12。控制器向N9～N12新鏈路上的OVS下發流表。

然后，起點S交換機向終點D交換機發送兩條相同的數據包，一條沿著Cx,x∈ { 0,1,2,… ,n}傳輸，一條沿著Ny,y∈ { 0,1,2,… ,n}傳輸。當相交節點N12收到兩個相同的數據包時確認兩條路徑都可以正常轉發，刪除舊鏈路上的流表，停止舊鏈路的轉發。

通過算法計算第二段切換的路徑為N0～N9，因此，向N0～N9新鏈路上的節點下發流表。

起點S交換機向終點D交換機通過多播發送兩條相同的數據包，當相交節點N9收到兩個相同的數據包，確認兩條轉發鏈路建立完成。刪除舊鏈路的轉發流表，流量按照新鏈路開始轉發，完成切換，SSRU切換結束之后的網絡拓撲如圖6所示。

圖6 SSRU切換結束之后的網絡拓撲

中央控制器向源目管理域內的控制器下發流表，然后域內通過上文域內的多播算法對域內路徑進行切換，完成新域間路徑的切換之后，刪除舊域間路徑上的轉發流表。

3 基于RYU的服務鏈功能部署開發與測試

本實驗使用如下硬件設備：華為 FusionCloud服務器 5臺、華為 CE6800交換機兩臺、華為CE12800交換機兩臺、華為S1700交換機一臺、AR交換機一臺。本實驗使用如下軟件：4.18版本的Ryu控制器、2.3.0版本的 mininet、16.04版本的Ubuntu。本節主要介紹了BL-LSTM算法的流量預測和在預測結果下基于 BP-ACO[10]的路由規劃和切換實驗。

3.1 BL-LSTM算法的流量預測實驗

本文以GEANT2部署的25個節點之間的流量信息作為數據集，然后通過流量數據測量和估算方法計算流量矩陣，再通過流量矩陣進行流量預測。通過BL-LSTM實現流量的預測，并將該算法和門控循環單元（gated recurrent unit，GRU）[5]以及棧式自編碼（stacked auto-encoder，SAE）深度學習模型[8]進行比較。選擇第12個端口到第23個端口的鏈路作為被測對象，數據集每隔5 min進行一次測量，持續兩周。該鏈路共記錄977條流量數據。預處理之后的數據集見表1。

表1 預處理之后的數據集

首先讀取977個XML流量數據文件，其次將每份數據集中的12～23端口之間的流量依次插入到新的newdata.CSV文件。

然后通過預處理腳本對獲取的數據進行分組、歸一化、矩陣轉換等數據預處理，腳本處理算法見算法1。

算法1預處理腳本

開始

train, test = [], []

foriin range(lags, len(flow1)):

train.append(flow1[i- lags:i+ 1])

foriin range(lags, len(flow2)):

test.append(flow2[i- lags:i+ 1])

train = np.array(train)

test = np.array(test)

np.random.shuffle(train)

X_train = train[:, :-1]

y_train = train[:, -1]

X_test = test[:, :-1]

y_test = test[:, -1]

returnX_train,y_train,X_test,y_test, scaler

結束

本節實驗將本文提出的 BL-LSTM 算法與GRU算法、SAE算法進行對比，首先將BL-LSTM算法的預測結果與真實數據進行對比，BL-LSTM預測結果曲線如圖7所示，BL-LSTM 曲線很好地擬合了真實值的曲線，但低點較真實值偏高。將歸一化的測試集和預測結果進行反歸一化，縱坐標變為流量的真實大小。

其次，將3種算法的預測結果和真實值進行對比，預測曲線對比如圖8所示。BL-LSTM算法對真實值曲線的擬合效果最好，SAE的效果次之，GRU的效果最差。

使用歸一化過后的測試集和預測結果計算相應的預測評估結果，量化算法之間的區別。其中，以12～23端口之間的流量數據集為例，對測試集的評價結果見表2。

表2 評價結果

由表2可知 BL-LSTM 模型的 MAPE為22.361 037%，誤差最小；SAE次之，GRU的MAPE為43.088 212%，誤差最大。從BL-LSTM、SAE、GRU模型的預測結果看，BL-LSTM模型的預測準確率要高于SAE和GRU。雖然LSTM和GRU都是循環神經網絡，但是在處理時間序列問題上，具有長期記憶特性的循環神經網絡LSTM優勢更大。

25組數據中不同算法的MAPE值如圖9所示，采用25組不同端口之間的數據作為數據集，各種算法預測結果的 MAPE值區別明顯。BL-LSTM預測精度最高，MAPE值在22.5%左右，SAE和GRU略有波動，SAE的MAPE平均值為35.2%，GRU的平均值為45.8%。

圖9 25組數據中不同算法的MAPE值

3.2 切換實驗

運行整理好的mininet拓撲，拓撲主要由4個控制域構成，每個控制器控制一個控制域，SSRU切換之前的轉發路徑如圖10所示。C2的控制域只在舊的鏈路上，C1的控制域只在新的鏈路上。而C0、C3的控制域既在新的鏈路又在舊的鏈路，域間的路由切換需要中央控制器對各控制域有序下發流表實現。

圖10 SSRU切換之前的轉發路徑

每個域內有6臺OVS，它們構成兩條新舊鏈路，以C0的控制域為例，S22～S24只在舊鏈路上的交換機、S18～SS20是只在新鏈路上的交換機、S17和S21既在新鏈路又在舊鏈路上的交換機。域內的路徑切換需要通過多播數據包確認路由更新狀態，進而實現路徑切換，SSRU切換之后的轉發路徑如圖11所示。

圖11 SSRU切換之后的轉發路徑

運行寫好的RYU控制器和mininet拓撲，控制器連接OVS會觸發裝飾器Event OFPS witch Features，每次OVS向控制器泛洪報文的時候將定義的標志（Flags）加 1。控制器連接 OVS如圖12所示。

圖12 控制器連接OVS

經過測試發現55次左右的裝飾器觸發能夠建立完整的連接。本文設置Flags到達55之后控制器開始執行路徑切換。

傳統的 Ryu二層交換機作為控制器，發送37個數據包進行測試，75%的數據包在切換的過程中丟失。二層交換交換機丟包現象如圖13所示。

圖13 二層交換交換機丟包現象

在應用無損路徑切換算法時，發送多組數據包進行測試，沒有數據包在切換的過程中丟失，該算法的丟包率和失序率都明顯優于傳統路徑切換算法。SSRU切換丟包現象如圖14所示。

圖14 SSRU切換丟包現象

發送速率從100 Mbit/s到500 Mbit/s的丟包數量實驗結果見表3，當發送速率從 100 Mbit/s到500 Mbit/s時，丟包率始終維持在0，但是其中伴隨了一些包失序問題，這是因為在路徑切換過程中，新路徑的網絡設備會出現空閑狀態，該路徑上的傳輸速率更快，于是切換過程中后續的數據包經過新鏈路可能會先到達目的地址，導致在一個往返時延（round-trip time，RTT）內可能會出現數據包失序的情況。幸運的是TCP具有重傳機制可以有效地緩解這個問題，用戶數據報協議（user datagram protocol，UDP）也有相關的機制解決少量的數據包失序。

表3 發送速率從100 Mbit/s到500 Mbit/s的丟包數量實驗結果

從H1到H2跨越3個控制域發送數據包，發送速率從800 Mbit/s到1 200 Mbit/s的丟包數量實驗結果見表4。

表4 發送速率從800 Mbit/s到1 200 Mbit/s的丟包數量實驗結果

發送速率逐步提高的實驗結果見表5，可以看出來 SSRU算法在進行路徑切換時引起的平均時延非常少，且這種時延幾乎不影響文件的實際傳輸，在文件的傳輸過程中既保證了業務以及會話的穩定運行，又防止流量只走最短路徑導致網絡局部擁塞，對網絡整體進行了負載均衡。

表5 發送速率逐步提高的實驗結果

對表5出現的縮寫的簡單介紹見表6。

表6 縮寫介紹

傳輸速率對平均時延的影響如圖15所示，可以看出隨著傳輸速率ATR的增長，路徑切換產生的平均時延呈線性增長，這表示SSRU算法在高速傳輸中依然可以保持高可用性。驗證了即使在高的傳輸速率SSRU也可以實現無損的路徑切換。

圖15 傳輸速率對平均時延的影響

4 結束語

隨著近年網絡技術的不斷發展和演進，用戶對網絡資源的需求體量越來越大，內容越來越復雜，傳統的網絡架構很難滿足目前靈活的網絡需求。SDN的革命性技術思想賦予了網絡可編程性和可演進性，實現網絡資源更靈活的管理。為了提高網絡資源利用率，提出了基于LSTM模型的流量預測，為路由規劃提供理論依據。通過提前預測網絡流量，在流量激增之前進行防御措施保證網絡的安全性和穩定性，實現基于流量預測的路由規劃、無損路徑切換等功能。