面向海量業務場景的網絡智能流量調度算法研究

杜林峰,崔金鵬,章小寧

(電子科技大學 信息與通信工程學院,成都 611731)

0 引 言

現在互聯網已與社會各個領域深度融合,隨著生產、教育、醫療等領域的發展及其互聯網應用規模的擴張,大量新興業務開始涌現。這些新興業務(例如VR/AR、車聯網、基因工程等應用)不僅數據量大,而且對時延和丟包率要求較高[1]。圖1為VR/AR應用場景。從圖1可以看出,設備需要將傳感器、攝像頭采集到的信息與云端進行交互,并對場景進行更新。由于傳輸的數據量巨大,需要超高速帶寬在短時間內完成,速率達到1 Gbit/s[2]。同時為了保證用戶良好的沉浸式體驗,網絡時延往往要求降低到5 ms以下,網絡丟包率需求達到10-6以下。為了保障網絡的服務質量(quality of service,QoS),滿足不斷增長的流量需求,網絡運營商可以通過增加路由器和鏈路的數量來提高網絡性能,但這將產生巨大的經濟成本。而良好的流量調度策略可以直接緩解網絡擁塞,實現業務流的高效傳輸。因此,研究一種海量業務場景下的流量調度算法實現網絡負載均衡具有重要意義。

圖1 AR/VR應用場景Fig.1 AR/VR application scenarios

在海量業務場景下進行流量調度存在諸多挑戰。第一,海量業務流的并行傳輸導致較高的網絡時延。在VR/AR、車聯網等應用場景下,網絡需要并行傳輸海量的業務流,但由于網絡資源有限,采用傳統的路由協議往往需要較長時間才能完成傳輸任務。第二,海量突發業務造成網絡擁塞。當網絡中出現大量突發業務時,由于鏈路帶寬資源有限,極易造成網絡擁塞,網絡QoS將顯著下降[3]。目前,傳統IP網絡流量調度方法大多基于OSPF路由協議,其通過配置路由參數來確定業務的路由信息,從而實現業務流的路由優化,達到負載均衡[4]。但在新興業務應用場景下,由于業務量大,基于OSPF的路由方法容易出現轉發時延長,鏈路擁塞等問題,無法滿足網絡QoS需求。文獻[5]提出一種基于最短路的QoS路由算法,根據鏈路代價為業務流選擇滿足帶寬約束的路由方案,但該方法計算效率較低,在海量業務場景下難以達到理想效果。文獻[6]提出了一種基于負載均衡的多路徑路由算法,該算法實時計算業務流所有可轉發的路徑集合,然后從中選擇鏈路負載最小的路徑,但由于需要計算業務流所有轉發路徑,在大規模網絡場景中時間成本過高。

近年來,機器學習在圖像識別、自然語言處理、自動駕駛等領域迅速發展,受到了學術界和工業界的廣泛關注[7]。許多學者開始嘗試使用機器學習算法來解決海量業務場景下的網絡流量調度問題。文獻[8]提出了一種基于監督學習的路由框架,該框架將業務流特征和鏈路利用率作為深度神經網絡輸入,并為每條鏈路輸出一個值,最后根據輸出生成路徑。實驗證明該方法能夠有效緩解網絡擁塞,但由于只訓練一個包含所有源、目的節點對的模型,在網絡規模較大時,神經網絡難以擬合。文獻[9]將歷史業務量矩陣作為強化學習模型輸入,預測未來的網絡流量,并通過調整鏈路權值來進行路由配置,實現負載均衡,但需要評估基于歷史業務量矩陣訓練的神經網絡,迭代次數達到了上萬次,模型訓練時間過長,這在業務高動態變化的網絡場景下并不適用。文獻[10]提出了一種基于循環圖神經網絡的RouteNet解決方案。該方案以鄰接矩陣、鏈路容量、備選路由等信息為輸入,對網絡的時延、丟包率等參數進行預測,最終根據預測值選擇最優路由方案。在路由規劃過程中,當網絡拓撲變化太大時,模型往往需要重新訓練,但由于RouteNet中嵌套了循環神經網絡,重新訓練的時間太長,無法滿足網絡高QoS需求。

針對上述方案存在的問題,本文以最小化最大鏈路利用率為目標,提出了一種基于機器學習的網絡智能流量調度算法。該算法以業務量矩陣[11]、網絡拓撲、業務QoS要求(帶寬,端到端時延)為約束,運用啟發式算法計算所有節點對在當前網絡狀態下的最優路由方案,生成標簽數據庫;采用BP神經網絡模型[12]作為學習機制,根據網絡狀態和流量調度方案的映射關系離線訓練網絡智能流量調度模型;在網絡運行階段,當業務流到達時,控制器根據當前網絡狀態采用網絡智能流量調度模型實時對業務流進行調度?？紤]到如果采用單個模型對網絡所有業務流進行調度,將導致流量調度決策時間過長,本文為網絡中所有存在非零業務量需求的節點對分別訓練一個網絡智能流量調度模型,對業務流進行并行調度。在實驗部分,為還原海量網絡數據并發傳輸場景,本文通過流量回放的方法,回放11.5萬條互聯網的真實新興業務流(AR/VR、車聯網等)。

1 負載均衡流量調度問題描述

以最小化最大鏈路利用率為優化目標的流量調度問題稱為負載均衡問題[13]。給定網絡拓撲G(V,E),V表示網絡中所有節點的集合,|V|=N,共有N個節點,其中僅有D個節點對存在非零業務量需求;E表示網絡中所有鏈路的集合,|E|=L,共有L條鏈路。節點用符號v(v∈{1,2,…,N})表示,鏈路用符號e(e∈{1,2,…,L})表示。給定業務量矩陣TM,其中TM為一個N行N列的矩陣,第i行j列代表節點i到節點j的業務量需求。僅考慮D個有非零業務量需求的節點對,每個節點對之間的業務量需求用符號d(d∈1,2,…,D})表示。主要參數如表1所示。

對于每一個業務量需求d,需要計算出該業務量需求下源節點i到目的節點j的所有路徑集合Pi,j。根據實際需求,從所有路徑集合Pi,j中選擇出K條路徑組成備選路徑集合。在單個業務流不可再分的應用場景下,節點i到節點j的業務量需求d只能選擇備選路徑集合中的一條路徑來放置流量,因此滿足約束條件

(1)

(1)式中:Pd為備選路徑集合;xd,p為一個二維變量,當業務量需求d選擇Pd中的路徑p來放置流量時取1,否則取0。

對于網絡拓撲中所有鏈路,使用符號δe,d,p表示鏈路e是否屬于業務量需求d下選擇的備選路徑p,該符號滿足約束條件

(2)

同時,由于網絡拓撲中經過鏈路e的流量之和不能超過該鏈路的鏈路容量,因此變量xd,p還應滿足約束條件

(3)

(3)式中:hd表示業務量需求d的需求量;ce表示鏈路e的鏈路容量。

用z表示網絡拓撲的最大鏈路利用率,定義為

(4)

網絡拓撲中所有鏈路的鏈路利用率都應當不超過最大鏈路利用率,因此滿足約束條件

(5)

本文的目標是在流量調度過程中最小化最大鏈路利用率,優化問題可表示為

minz

s.t. (1), (3), (4), (5), (6)

表1 主要參數Tab.1 Main parameters

2 網絡智能流量調度算法方案

網絡流量調度方案的最優解可以通過求解流量調度整數線性規劃模型(integer linear program,ILP)得到。最優解為某個網絡狀態下各節點對業務路由的最優路徑。但隨著網絡規模的增大,該問題的求解難度指數增加,無法在合理的時間內求出最優解。比較常用的解決方案是設計一種優化同一目標函數的啟發式方法,得到流量調度方案的次優解,以此逼近最優解的性能。但其在網絡時延需求較高的業務場景下并不適用,由于業務需求動態變化,為了使網絡不斷地根據次優解進行路由,算法必須重復運行,這將占用大量的計算資源,且無法保證路由決策的實時性需求。因此,本文設計通過神經網絡模型學習啟發式算法求解的次優解方案,采用神經網絡模型替代啟發式算法進行路由決策,以此逼近最優解性能,并在短時間內實現路由決策。

網絡智能流量調度算法的總體框架如圖2所示。網絡總體架構采用軟件定義網絡(software defined network,SDN)架構。SDN將網絡層的數據轉發與控制解耦,控制平面由控制器進行網絡狀態感知與路由計算,數據平面由網絡節點(例如虛擬交換機)實現數據轉發,控制平面與數據平面之間通過OpenFlow協議進行數據交互[14]。網絡中每個非零業務量需求的節點對都由控制器維護一個網絡智能流量調度模型,用于該節點對業務的路由決策。網絡控制器實時接收更新的網絡狀態(例如業務量矩陣、鏈路剩余帶寬、業務端到端時延等),并調用每個節點對的網絡智能流量調度模型生成該節點對流量調度的最優路徑。隨后控制器將所有節點對的路由方案以流表項的形式下發并注冊到所有網絡節點中,每個節點可以根據注冊的流表項直接進行數據轉發,最終實現全局流量調度。

圖2 網絡智能流量調度算法總體架構Fig.2 Overall architecture of network intelligent traffic scheduling algorithm

由于控制器與網絡節點間采用OpenFlow協議進行通信,在同一網絡狀態下,控制器只需進行一次路由計算。當最優路由方案集合以流表項形式下發至所有網絡節點后,網絡節點僅需周期性地向控制器發送鏈路負載狀態信息,直到出現新的節點業務轉發需求。文獻[15]表明這并不會使網絡負載發生顯著變化,協議開銷可以忽略不計。因此,通過這種方式能夠有效節約網絡資源,降低網絡負載。

網絡智能流量調度算法共包括2個階段:訓練階段和預測階段。訓練階段在實際業務路由開始前完成,運用啟發式算法求解每個業務量矩陣對應的最優路徑方案,使用業務量矩陣與最優路徑方案組成的標簽數據庫訓練每個節點對的BP神經網絡模型,保存模型以在預測階段執行。預測階段即實際應用階段。在預測階段,當控制器檢測到新的數據包時,將解析該數據包,讀取源節點和目的節點編號、轉發帶寬需求等,隨后發送給相應節點對的BP神經網絡模型,得到該數據包的最優轉發路徑。由于只需通過訓練好的BP神經網絡模型進行路由決策,無須執行大量的計算,因此算法能夠有效滿足海量網絡業務的實時性需求,解決傳統路由策略計算成本及時間成本過高的問題。

3 網絡智能流量調度模型設計

3.1 模型輸入輸出設計

業務量矩陣代表網絡中所有源、目的節點對之間的業務量需求,例如業務量矩陣的第i行第j列代表節點i到節點j的業務量需求。準確及時的業務量矩陣能夠有效反映網絡狀態,因此采用業務量矩陣作為神經網絡模型的輸入。為了簡化神經網絡輸入結構,將業務量矩陣展開為向量形式。

考慮到網絡高動態變化的特點,為了實現路由決策的高效性,神經網絡模型直接以當前業務的最優轉發路徑作為輸出。在預測階段開始前,利用K最短路徑算法[16]為每一個非零業務量需求的節點對求解出K條不同的無環備選路徑,而最優路徑將從這K條備選路徑中選擇。為了簡化神經網絡輸出結構,將二進制標簽作為模型輸出。例如當K=5時,模型輸出000代表選擇第1條備選路徑作為最優路徑,輸出001代表選擇第2條備選路徑,以此類推,輸入輸出特征如圖3所示。綜上所述,本文采用M維向量x,N維向量y分別表示神經網絡的輸入輸出,向量x表示為

x=(x1,x2,…,xM-1,xM)

(7)

(7)式中:xi代表網絡控制器上一時刻測算的第i個節點對之間的業務量需求。向量y表示為

y=(y1,y2,…,yN-1,yN)

(8)

(8)式中:yi∈{0,1}代表最優路徑的選擇情況。

圖3 模型輸入輸出特征Fig.3 Features of model’s input and output

3.2 神經網絡模型設計

BP神經網絡是深度學習模型中最常見和有效的神經網絡模型,是一種通過誤差逆向傳播訓練的多層前饋網絡,具有較強的非線性映射與泛化能力。在網絡路由決策領域,BP神經網絡可以通過監督學習的方式有效學習網絡路由預測的特征,在一些應用場景下,BP神經網絡與整數線性規劃中求解最優解的方法性能相近,且性能顯著優于最短路等常見路由算法[17],是啟發式路由算法的一種有效替代方案。本文選擇BP神經網絡來完成網絡路由計算任務,圖4為BP神經網絡具體結構。BP神經網絡共包含L層:輸入層x,輸出層y,以及(L-2)層隱藏層。輸入層x的神經元個數由業務量矩陣的維數決定,例如業務量矩陣為N維,輸入就由N個神經元組成,每個神經元的輸入為相應節點對的業務帶寬需求。輸出層y包含M個神經元,神經元個數M由該節點對的備選路徑個數K決定,要求M=[lbK]。兩層之間的神經元通過加權連接,但是同一層的神經元無連接,同時每一個神經元都有一個加權偏置。隱藏層和輸出層分別采用Relu函數和Sigmoid函數作為激活函數。

BP神經網絡采用反向傳播算法進行訓練,將輸入量xi與權值wi的乘積與一個給定的閾值bi做差,此值通過傳遞函數f得到輸出值yi,同時比較網絡的輸出值與期望值的誤差,通過誤差的反向傳播,利用梯度下降法不斷調整和修改網絡各層之間的鏈接權值和閾值,從而使輸出結果更加接近真實值,同時收斂到預設的目標誤差函數值。通過反向傳播算法改變權重系數,初始權重由網絡隨機賦值,然后根據網絡迭代結果調整直到滿足目標誤差。當所有參數的變化值都小于迭代閾值或達到最大迭代次數時,模型訓練完成。

4 訓練數據生成設計

網絡智能流量調度模型的訓練流程如圖5所示。網絡控制器首先從網絡中采集非對稱業務量矩陣,隨后采用K最短路徑算法計算每個節點對的備選路徑集合,求解不同業務量矩陣下每個節點對的最優路徑組成標簽數據庫,以訓練該節點對的神經網絡模型。

在求解出每個節點對的備選路徑集合后,本文對網絡中所有非零流量業務逐個進行最優路徑計算,每計算一條流量業務d就把該業務的占用帶寬即需求量hd,加到所經過鏈路的流量之和上,以此產生對后續業務計算路徑時的影響。在流量放置過程中,若當前業務流量使得最大鏈路利用率z大于預設值zmax,說明此時網絡出現擁塞,當前業務放置順序并不是最優順序。因此將擁塞鏈路上的業務流量取出重新計算并部署,直到網絡中的最大鏈路利用率降低到預設值以下。在流量業務放置過程中,始終受到(1)式、(3)式的條件約束,即業務量需求d只能選擇Pd中的一條路徑來放置流量,網絡拓撲中經過鏈路e的流量之和不能超過該鏈路的鏈路容量ce。訓練數據生成算法如算法1所示。

圖4 神經網絡結構Fig.4 Neural network architecture

算法1訓練數據生成算法

1)初始化網絡中所有鏈路的流量之和為0,對D條流量業務進行排序,令i=1。

2)將第i條業務放置到網絡拓撲中,即從備選路徑集合Pd中取出備選路徑p,將該業務的占用帶寬加到路徑p所經過鏈路的流量之和上,計算當前網絡的最大鏈路利用率z;比較所有備選路徑的z值,選擇最小值所對應的備選路徑作為該業務的路由方案。

3)檢查當前網絡的最大鏈路利用率z是否超過預設值zmax。若超過,執行步驟4);否則執行步驟6)。

4)將已放入的后N(N>0)條業務從網絡中取出,并將這N條業務的需求量從所經過鏈路的流量之和中減去。

5)將取出的N條業務重新排序,并按當前順序再次放入網絡后,執行步驟3)。

6)如果i≤D,令i=i+1,執行步驟2),否則輸出所有流量業務的路由方案,算法結束。

圖5 網絡智能流量調度模型訓練流程Fig.5 Training process of network intelligent traffic scheduling model

當從網絡中實時采集業務量矩陣之后,運用訓練數據生成算法可以很快求解出每個業務流的路由方案。將每個業務流的路由方案用最優路徑標簽表示,本文實驗中備選路徑集合包含5條路徑,標簽采用3位二進制數,即第1條備選路徑表示為000,第2條備選路徑表示為001,以此類推。這樣每個業務量矩陣在每個非零流量業務需求的節點對上都有一個最優路徑標簽與之對應。當N個業務量矩陣的路由策略計算完畢,對于每個非零業務量需求的節點對就產生了N條訓練數據。帶標簽的訓練數據庫如圖6所示。

訓練數據的質量對于模型表現至關重要,本文對生成的訓練數據庫進行復查評估。對于某個采集的業務量矩陣,當前網絡狀態下所有存在流量需求的節點對從各自的訓練數據庫中取出對應的標簽數據,并按照路徑標簽代表的最優路徑進行業務路由。當網絡中的最大鏈路利用率大于預設值zmax時,則判定該業務量矩陣對應的標簽數據不合格,并從訓練數據庫中剔除。重復以上過程,直到訓練數據庫中所有訓練數據都經過復查評估。通過這種方式,能夠有效提高訓練數據的準確性。

圖6 帶標簽的訓練數據庫Fig.6 Tagged training database

5 實驗結果及分析

為了驗證網絡智能流量調度算法在海量業務場景下的算法性能,將該算法與最短路徑算法、鄰域搜索算法在負載均衡、平均時延和最大丟包率等方面進行實驗對比分析。

本文基于虛擬云環境與OVS搭建的全站式網絡模擬環境進行實驗分析。該網絡環境具有完備的網絡配置、管理和GUI平臺,網絡拓撲如圖7所示。網絡共有100個節點、566條鏈路,其中114個節點對存在非零業務量需求。為了保證網絡環境中的流量真實可信,本文采用了流量回放的方法,即通過回放115K條互聯網開源業務流(視頻、AR/VR、車聯網流量等)來還原真實的海量新興業務場景。實驗中鏈路帶寬設定為100 Mbit/s,采用ONOS作為SDN網絡的控制器[18],分別運行啟發式算法和網絡智能流量調度算法。在運行網絡智能流量調度算法時,將K值設定為5,即每個業務的備選路徑集合包含5條路徑。ONOS每20 s采集一次節點對的業務流組成全局業務量矩陣,使用訓練數據生成算法得到10萬條標簽數據,訓練集和測試集比例為0.9∶0.1。神經網絡采用5層BP神經網絡模型,使用Adam優化器進行參數訓練,共訓練114個網絡智能流量調度模型。

采用最短路徑算法、鄰域搜索算法與網絡智能流量調度算法進行實驗對比分析。最短路徑算法通過構造最短路徑樹,按非降次序逐條構造從起始節點到各個節點的最短路徑。鄰域搜索算法以初始節點為起點,每次迭代選擇鄰域中鏈路剩余帶寬最大的鏈路組成路徑,直至到達目的節點。

圖7 網絡拓撲Fig.7 Network topology

本文選取3個性能參數來評估算法性能:①最大鏈路利用率:網絡中所有鏈路的最大帶寬利用率;②平均時延:數據包在節點對之間轉發所耗費的平均時間;③最大丟包率:轉發過程中所丟失數據包占所發送數據組的最大比率。

圖8為實驗環境下運行最短路算法、鄰域搜索算法及網絡智能流量調度算法后網絡最大鏈路利用率情況對比。運行最短路算法時,網絡最大鏈路利用率最低為79%,最高為100%,這是由于在最短路算法中每個源、目的節點對間的業務流都走路由跳數最少的路徑,而拓撲中的某些鏈路總屬于最短路的一部分,許多業務流都會使用此類鏈路,這將導致此類鏈路的鏈路利用率很高,其余很多鏈路空閑。運行鄰域搜索算法時,網絡最大鏈路利用率最低為83%,最高為100%,原因在于鄰域搜索算法每次都選擇鄰域中剩余帶寬最大的鏈路,這可能導致最后生成的路徑跳數較多,跳數多意味著一個業務流占用了更多鏈路的帶寬資源,所以無法達到較好的負載均衡效果。而運行網絡智能流量調度算法時,網絡最大鏈路利用率最低為59%,最高為71%,網絡鏈路利用率得到明顯優化。因此,網絡智能流量調度算法在海量業務場景下性能優于最短路徑算法以及鄰域搜索算法。

為了更清晰地展示網絡智能流量調度算法的性能提升效果,圖9給出了算法相比于最短路算法、鄰域搜索算法在最大鏈路利用率方面的性能提升。從圖9可以看出,大多數情況下網絡智能流量調度算法得到的最大鏈路利用率都優于最短路算法和鄰域搜索算法,這說明算法在海量業務場景下能夠有效緩解網絡擁塞。

圖8 最大鏈路利用率Fig.8 Comparison of maximum link utilization

圖9 最大鏈路利用率性能對比Fig.9 Performance improvement ratio of maximum link utilization

在最大鏈路利用率得到優化的同時,網絡的時延與丟包率也得到了明顯改善。圖10為3種算法平均時延的情況對比,圖11為最大時延的情況對比。由圖10—圖11可見,運行網絡智能流量調度算法時,網絡平均時延都保持在1 ms以下,最大時延都保持在30 ms以下;而最短路算法和鄰域搜索算法的平均時延往往超過10 ms,最大值達到35 ms;最大時延超過110 ms,最大值達到190 ms。網絡智能流量調度算法可以大大降低網絡時延,避免數據包轉發耗時過高的問題。

圖10 平均時延對比Fig.10 Comparison of average delay

圖11 最大時延對比Fig.11 Comparison of maximum delay

圖12為3種路由算法最大丟包率的情況對比,運行最短路算法和鄰域搜索算法時,每個時刻網絡的最大丟包率都超過60%,甚至達到95%,此時網絡中的某些鏈路已經嚴重擁塞,大量網絡數據包無法轉發到目的節點。而運行網絡智能流量調度算法時,網絡鏈路的最大丟包率保持在7%以下,算法能夠有效降低網絡丟包率,保障數據包的有效傳輸。

綜上,網絡智能流量調度算法能夠根據實時業務量矩陣合理規劃流量調度策略,相比于最短路算法,能夠有效降低網絡最大鏈路利用率、平均時延和最大丟包率,實現負載均衡。通過3種算法的實現效果對比可知,網絡智能流量調度算法能夠有效避免網絡中出現擁塞鏈路,確保數據的有效傳輸。

6 結束語

本文對海量業務場景下的流量調度算法展開研究,提出了一種基于深度學習的網絡智能流量調度算法。本文對負載均衡流量調度問題進行建模,設計智能流量調度算法的總體架構,利用啟發式算法生成訓練數據集,訓練網絡智能流量調度模型對業務流進行實時調度。在實驗平臺上對所提算法進行的性能測試結果表明,所提算法相比于傳統啟發式路由策略具有更好的網絡優化性能,能夠有效緩解網絡擁塞。

圖12 最大丟包率對比Fig.12 Comparison of maximum packet loss rates