杜林峰,崔金鵬,章小寧

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

0 引 言

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

圖1 AR/VR應(yīng)用場景Fig.1 AR/VR application scenarios

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

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

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

1 負載均衡流量調(diào)度問題描述

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

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

(1)

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

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

(2)

同時,由于網(wǎng)絡(luò)拓撲中經(jīng)過鏈路e的流量之和不能超過該鏈路的鏈路容量,因此變量xd,p還應(yīng)滿足約束條件

(3)

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

用z表示網(wǎng)絡(luò)拓撲的最大鏈路利用率,定義為

(4)

網(wǎng)絡(luò)拓撲中所有鏈路的鏈路利用率都應(yīng)當不超過最大鏈路利用率,因此滿足約束條件

(5)

本文的目標是在流量調(diào)度過程中最小化最大鏈路利用率,優(yōu)化問題可表示為

minz

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

表1 主要參數(shù)Tab.1 Main parameters

2 網(wǎng)絡(luò)智能流量調(diào)度算法方案

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

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

圖2 網(wǎng)絡(luò)智能流量調(diào)度算法總體架構(gòu)Fig.2 Overall architecture of network intelligent traffic scheduling algorithm

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

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

3 網(wǎng)絡(luò)智能流量調(diào)度模型設(shè)計

3.1 模型輸入輸出設(shè)計

業(yè)務(wù)量矩陣代表網(wǎng)絡(luò)中所有源、目的節(jié)點對之間的業(yè)務(wù)量需求,例如業(yè)務(wù)量矩陣的第i行第j列代表節(jié)點i到節(jié)點j的業(yè)務(wù)量需求。準確及時的業(yè)務(wù)量矩陣能夠有效反映網(wǎng)絡(luò)狀態(tài),因此采用業(yè)務(wù)量矩陣作為神經(jīng)網(wǎng)絡(luò)模型的輸入。為了簡化神經(jīng)網(wǎng)絡(luò)輸入結(jié)構(gòu),將業(yè)務(wù)量矩陣展開為向量形式。

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

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

(7)

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

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

(8)

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

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

3.2 神經(jīng)網(wǎng)絡(luò)模型設(shè)計

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

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

4 訓(xùn)練數(shù)據(jù)生成設(shè)計

網(wǎng)絡(luò)智能流量調(diào)度模型的訓(xùn)練流程如圖5所示。網(wǎng)絡(luò)控制器首先從網(wǎng)絡(luò)中采集非對稱業(yè)務(wù)量矩陣,隨后采用K最短路徑算法計算每個節(jié)點對的備選路徑集合,求解不同業(yè)務(wù)量矩陣下每個節(jié)點對的最優(yōu)路徑組成標簽數(shù)據(jù)庫,以訓(xùn)練該節(jié)點對的神經(jīng)網(wǎng)絡(luò)模型。

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

圖4 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.4 Neural network architecture

算法1訓(xùn)練數(shù)據(jù)生成算法

1)初始化網(wǎng)絡(luò)中所有鏈路的流量之和為0,對D條流量業(yè)務(wù)進行排序,令i=1。

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

3)檢查當前網(wǎng)絡(luò)的最大鏈路利用率z是否超過預(yù)設(shè)值zmax。若超過,執(zhí)行步驟4);否則執(zhí)行步驟6)。

4)將已放入的后N(N>0)條業(yè)務(wù)從網(wǎng)絡(luò)中取出,并將這N條業(yè)務(wù)的需求量從所經(jīng)過鏈路的流量之和中減去。

5)將取出的N條業(yè)務(wù)重新排序,并按當前順序再次放入網(wǎng)絡(luò)后,執(zhí)行步驟3)。

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

圖5 網(wǎng)絡(luò)智能流量調(diào)度模型訓(xùn)練流程Fig.5 Training process of network intelligent traffic scheduling model

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

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

圖6 帶標簽的訓(xùn)練數(shù)據(jù)庫Fig.6 Tagged training database

5 實驗結(jié)果及分析

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

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

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

圖7 網(wǎng)絡(luò)拓撲Fig.7 Network topology

本文選取3個性能參數(shù)來評估算法性能:①最大鏈路利用率:網(wǎng)絡(luò)中所有鏈路的最大帶寬利用率;②平均時延:數(shù)據(jù)包在節(jié)點對之間轉(zhuǎn)發(fā)所耗費的平均時間;③最大丟包率:轉(zhuǎn)發(fā)過程中所丟失數(shù)據(jù)包占所發(fā)送數(shù)據(jù)組的最大比率。

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

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

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

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

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

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

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

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

綜上,網(wǎng)絡(luò)智能流量調(diào)度算法能夠根據(jù)實時業(yè)務(wù)量矩陣合理規(guī)劃流量調(diào)度策略,相比于最短路算法,能夠有效降低網(wǎng)絡(luò)最大鏈路利用率、平均時延和最大丟包率,實現(xiàn)負載均衡。通過3種算法的實現(xiàn)效果對比可知,網(wǎng)絡(luò)智能流量調(diào)度算法能夠有效避免網(wǎng)絡(luò)中出現(xiàn)擁塞鏈路,確保數(shù)據(jù)的有效傳輸。

6 結(jié)束語

本文對海量業(yè)務(wù)場景下的流量調(diào)度算法展開研究,提出了一種基于深度學(xué)習的網(wǎng)絡(luò)智能流量調(diào)度算法。本文對負載均衡流量調(diào)度問題進行建模,設(shè)計智能流量調(diào)度算法的總體架構(gòu),利用啟發(fā)式算法生成訓(xùn)練數(shù)據(jù)集,訓(xùn)練網(wǎng)絡(luò)智能流量調(diào)度模型對業(yè)務(wù)流進行實時調(diào)度。在實驗平臺上對所提算法進行的性能測試結(jié)果表明,所提算法相比于傳統(tǒng)啟發(fā)式路由策略具有更好的網(wǎng)絡(luò)優(yōu)化性能,能夠有效緩解網(wǎng)絡(luò)擁塞。

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