杜林峰,崔金鵬,章小寧

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

0 引 言

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

用z表示網(wǎng)絡(luò)拓?fù)涞淖畲箧溌防寐?定義為

(4)

網(wǎng)絡(luò)拓?fù)渲兴墟溌返逆溌防寐识紤?yīng)當(dāng)不超過最大鏈路利用率,因此滿足約束條件

(5)

本文的目標(biāo)是在流量調(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)解為某個(gè)網(wǎng)絡(luò)狀態(tài)下各節(jié)點(diǎn)對業(yè)務(wù)路由的最優(yōu)路徑。但隨著網(wǎng)絡(luò)規(guī)模的增大,該問題的求解難度指數(shù)增加,無法在合理的時(shí)間內(nèi)求出最優(yōu)解。比較常用的解決方案是設(shè)計(jì)一種優(yōu)化同一目標(biāo)函數(shù)的啟發(fā)式方法,得到流量調(diào)度方案的次優(yōu)解,以此逼近最優(yōu)解的性能。但其在網(wǎng)絡(luò)時(shí)延需求較高的業(yè)務(wù)場景下并不適用,由于業(yè)務(wù)需求動(dòng)態(tài)變化,為了使網(wǎng)絡(luò)不斷地根據(jù)次優(yōu)解進(jìn)行路由,算法必須重復(fù)運(yùn)行,這將占用大量的計(jì)算資源,且無法保證路由決策的實(shí)時(shí)性需求。因此,本文設(shè)計(jì)通過神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)啟發(fā)式算法求解的次優(yōu)解方案,采用神經(jīng)網(wǎng)絡(luò)模型替代啟發(fā)式算法進(jìn)行路由決策,以此逼近最優(yōu)解性能,并在短時(shí)間內(nèi)實(shí)現(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ā)與控制解耦,控制平面由控制器進(jìn)行網(wǎng)絡(luò)狀態(tài)感知與路由計(jì)算,數(shù)據(jù)平面由網(wǎng)絡(luò)節(jié)點(diǎn)(例如虛擬交換機(jī))實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā),控制平面與數(shù)據(jù)平面之間通過OpenFlow協(xié)議進(jìn)行數(shù)據(jù)交互[14]。網(wǎng)絡(luò)中每個(gè)非零業(yè)務(wù)量需求的節(jié)點(diǎn)對都由控制器維護(hù)一個(gè)網(wǎng)絡(luò)智能流量調(diào)度模型,用于該節(jié)點(diǎn)對業(yè)務(wù)的路由決策。網(wǎng)絡(luò)控制器實(shí)時(shí)接收更新的網(wǎng)絡(luò)狀態(tài)(例如業(yè)務(wù)量矩陣、鏈路剩余帶寬、業(yè)務(wù)端到端時(shí)延等),并調(diào)用每個(gè)節(jié)點(diǎn)對的網(wǎng)絡(luò)智能流量調(diào)度模型生成該節(jié)點(diǎn)對流量調(diào)度的最優(yōu)路徑。隨后控制器將所有節(jié)點(diǎn)對的路由方案以流表項(xiàng)的形式下發(fā)并注冊到所有網(wǎng)絡(luò)節(jié)點(diǎn)中,每個(gè)節(jié)點(diǎn)可以根據(jù)注冊的流表項(xiàng)直接進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),最終實(shí)現(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é)點(diǎn)間采用OpenFlow協(xié)議進(jìn)行通信,在同一網(wǎng)絡(luò)狀態(tài)下,控制器只需進(jìn)行一次路由計(jì)算。當(dāng)最優(yōu)路由方案集合以流表項(xiàng)形式下發(fā)至所有網(wǎng)絡(luò)節(jié)點(diǎn)后,網(wǎng)絡(luò)節(jié)點(diǎn)僅需周期性地向控制器發(fā)送鏈路負(fù)載狀態(tài)信息,直到出現(xiàn)新的節(jié)點(diǎn)業(yè)務(wù)轉(zhuǎn)發(fā)需求。文獻(xiàn)[15]表明這并不會(huì)使網(wǎng)絡(luò)負(fù)載發(fā)生顯著變化,協(xié)議開銷可以忽略不計(jì)。因此,通過這種方式能夠有效節(jié)約網(wǎng)絡(luò)資源,降低網(wǎng)絡(luò)負(fù)載。

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

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

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

業(yè)務(wù)量矩陣代表網(wǎng)絡(luò)中所有源、目的節(jié)點(diǎn)對之間的業(yè)務(wù)量需求,例如業(yè)務(wù)量矩陣的第i行第j列代表節(jié)點(diǎn)i到節(jié)點(diǎn)j的業(yè)務(wù)量需求。準(zhǔn)確及時(shí)的業(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ò)高動(dòng)態(tài)變化的特點(diǎn),為了實(shí)現(xiàn)路由決策的高效性,神經(jīng)網(wǎng)絡(luò)模型直接以當(dāng)前業(yè)務(wù)的最優(yōu)轉(zhuǎn)發(fā)路徑作為輸出。在預(yù)測階段開始前,利用K最短路徑算法[16]為每一個(gè)非零業(yè)務(wù)量需求的節(jié)點(diǎn)對求解出K條不同的無環(huán)備選路徑,而最優(yōu)路徑將從這K條備選路徑中選擇。為了簡化神經(jīng)網(wǎng)絡(luò)輸出結(jié)構(gòu),將二進(jìn)制標(biāo)簽作為模型輸出。例如當(dāng)K=5時(shí),模型輸出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ò)控制器上一時(shí)刻測算的第i個(gè)節(jié)點(diǎn)對之間的業(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è)計(jì)

BP神經(jīng)網(wǎng)絡(luò)是深度學(xué)習(xí)模型中最常見和有效的神經(jīng)網(wǎng)絡(luò)模型,是一種通過誤差逆向傳播訓(xùn)練的多層前饋網(wǎng)絡(luò),具有較強(qiáng)的非線性映射與泛化能力。在網(wǎng)絡(luò)路由決策領(lǐng)域,BP神經(jīng)網(wǎng)絡(luò)可以通過監(jiān)督學(xué)習(xí)的方式有效學(xué)習(xí)網(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ò)路由計(jì)算任務(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)元個(gè)數(shù)由業(yè)務(wù)量矩陣的維數(shù)決定,例如業(yè)務(wù)量矩陣為N維,輸入就由N個(gè)神經(jīng)元組成,每個(gè)神經(jīng)元的輸入為相應(yīng)節(jié)點(diǎn)對的業(yè)務(wù)帶寬需求。輸出層y包含M個(gè)神經(jīng)元,神經(jīng)元個(gè)數(shù)M由該節(jié)點(diǎn)對的備選路徑個(gè)數(shù)K決定,要求M=[lbK]。兩層之間的神經(jīng)元通過加權(quán)連接,但是同一層的神經(jīng)元無連接,同時(shí)每一個(gè)神經(jīng)元都有一個(gè)加權(quán)偏置。隱藏層和輸出層分別采用Relu函數(shù)和Sigmoid函數(shù)作為激活函數(shù)。

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

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

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

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

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

3)檢查當(dāng)前網(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ù)重新排序,并按當(dāng)前順序再次放入網(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

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

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

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

5 實(shí)驗(yàn)結(jié)果及分析

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

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

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

圖7 網(wǎng)絡(luò)拓?fù)銯ig.7 Network topology

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

圖8為實(shí)驗(yàn)環(huán)境下運(yùn)行最短路算法、鄰域搜索算法及網(wǎng)絡(luò)智能流量調(diào)度算法后網(wǎng)絡(luò)最大鏈路利用率情況對比。運(yùn)行最短路算法時(shí),網(wǎng)絡(luò)最大鏈路利用率最低為79%,最高為100%,這是由于在最短路算法中每個(gè)源、目的節(jié)點(diǎn)對間的業(yè)務(wù)流都走路由跳數(shù)最少的路徑,而拓?fù)渲械哪承╂溌房倢儆谧疃搪返囊徊糠?許多業(yè)務(wù)流都會(huì)使用此類鏈路,這將導(dǎo)致此類鏈路的鏈路利用率很高,其余很多鏈路空閑。運(yùn)行鄰域搜索算法時(shí),網(wǎng)絡(luò)最大鏈路利用率最低為83%,最高為100%,原因在于鄰域搜索算法每次都選擇鄰域中剩余帶寬最大的鏈路,這可能導(dǎo)致最后生成的路徑跳數(shù)較多,跳數(shù)多意味著一個(gè)業(yè)務(wù)流占用了更多鏈路的帶寬資源,所以無法達(dá)到較好的負(fù)載均衡效果。而運(yùn)行網(wǎng)絡(luò)智能流量調(diào)度算法時(shí),網(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)化的同時(shí),網(wǎng)絡(luò)的時(shí)延與丟包率也得到了明顯改善。圖10為3種算法平均時(shí)延的情況對比,圖11為最大時(shí)延的情況對比。由圖10—圖11可見,運(yùn)行網(wǎng)絡(luò)智能流量調(diào)度算法時(shí),網(wǎng)絡(luò)平均時(shí)延都保持在1 ms以下,最大時(shí)延都保持在30 ms以下;而最短路算法和鄰域搜索算法的平均時(shí)延往往超過10 ms,最大值達(dá)到35 ms;最大時(shí)延超過110 ms,最大值達(dá)到190 ms。網(wǎng)絡(luò)智能流量調(diào)度算法可以大大降低網(wǎng)絡(luò)時(shí)延,避免數(shù)據(jù)包轉(zhuǎn)發(fā)耗時(shí)過高的問題。

圖10 平均時(shí)延對比Fig.10 Comparison of average delay

圖11 最大時(shí)延對比Fig.11 Comparison of maximum delay

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

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

6 結(jié)束語

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

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