一種減少網(wǎng)絡(luò)振動的智能路由選擇算法設(shè)計

邵天竺 王曉亮 陳文龍 唐曉嵐 徐 敏

(首都師范大學(xué)信息工程學(xué)院 北京 100048)

(nestea_god＠hotmail.com)

近年來互聯(lián)網(wǎng)和移動通信產(chǎn)業(yè)的快速發(fā)展,網(wǎng)絡(luò)系統(tǒng)不斷向著規(guī)?；?、異構(gòu)化、動態(tài)化的方向演進[1].同時,伴隨著5G網(wǎng)絡(luò)的成熟,萬物互聯(lián)將帶來網(wǎng)絡(luò)終端數(shù)量、網(wǎng)絡(luò)流量以及應(yīng)用形式上的新一輪爆發(fā)性增長,并對數(shù)據(jù)轉(zhuǎn)發(fā)速率、超低延遲、高能效比和大規(guī)模連接提出更高的要求[2].由此帶來的服務(wù)能力和復(fù)雜性問題使得當(dāng)前的網(wǎng)絡(luò)系統(tǒng)面臨無數(shù)新的挑戰(zhàn),現(xiàn)有盡力而為的路由轉(zhuǎn)發(fā)算法難以滿足這些應(yīng)用所帶來的多樣化的網(wǎng)絡(luò)服務(wù)質(zhì)量需求.

隨著網(wǎng)絡(luò)環(huán)境的不斷發(fā)展,當(dāng)面對突發(fā)流量或大流量時,基于最短路徑的傳統(tǒng)路由協(xié)議可能導(dǎo)致嚴重的網(wǎng)絡(luò)擁塞.互聯(lián)網(wǎng)需要一種更加智能的路由策略,將網(wǎng)絡(luò)狀態(tài)與路由策略融合,提升網(wǎng)絡(luò)服務(wù)質(zhì)量.然而互聯(lián)網(wǎng)龐大的網(wǎng)絡(luò)規(guī)模和數(shù)據(jù)流量使得智能機制的設(shè)計充滿挑戰(zhàn).

機器學(xué)習(xí)技術(shù)近來已取得高速發(fā)展,在計算機網(wǎng)絡(luò)方面,有監(jiān)督和無監(jiān)督的人工神經(jīng)網(wǎng)絡(luò)(ANN)技術(shù)從路由策略到入侵檢測的各種領(lǐng)域中得到廣泛應(yīng)用.盡管傳統(tǒng)的淺層人工神經(jīng)網(wǎng)絡(luò)經(jīng)常被用于主動網(wǎng)絡(luò)管理的流量預(yù)測,然而其性能實際上是相對受限的[3],因為單純增加ANN的隱藏層數(shù)量難以改善網(wǎng)絡(luò)操作決策(例如調(diào)度、路由等)的性能.然而,深度學(xué)習(xí)系統(tǒng)(例如Deep Belief Networks,Deep ANNs和Deep Boltzmann)的快速發(fā)展給網(wǎng)絡(luò)領(lǐng)域的研究提供了新的突破點,它的算法性能顯著提高[4].

以深度學(xué)習(xí)技術(shù)為基礎(chǔ)的智能路由算法設(shè)計,其核心思想是利用大數(shù)據(jù)驅(qū)動的網(wǎng)絡(luò)特征獲取機制,從部署范圍的歷史數(shù)據(jù)中尋找路由選擇與時間、或路由選擇與流量間的映射關(guān)系,從而指導(dǎo)后續(xù)路由優(yōu)化.

相比傳統(tǒng)數(shù)學(xué)模型支持下的路由策略設(shè)計,數(shù)據(jù)驅(qū)動的智能路由算法具有復(fù)雜度低和通用性強等優(yōu)勢.其中,復(fù)雜度低主要體現(xiàn)在其避免了針對網(wǎng)絡(luò)復(fù)雜特性和多樣需求的數(shù)學(xué)建模工作,以歷史流量數(shù)據(jù)為基礎(chǔ),通過神經(jīng)網(wǎng)絡(luò)的迭代訓(xùn)練代替精確建模,大幅降低核心映射的獲取復(fù)雜度;通用性強則體現(xiàn)在相同的機器學(xué)習(xí)模型,可以面向不同的網(wǎng)絡(luò)環(huán)境和需求場景,采用不同的數(shù)據(jù)集來求解對應(yīng)的差異化問題.

然而,隨著智能化路由技術(shù)的發(fā)展,新的技術(shù)挑戰(zhàn)也隨之而來.通過實驗我們發(fā)現(xiàn),目前的智能路由算法在基于歷史數(shù)據(jù)進行路由更新時,很容易因為局部流量的微小變動而導(dǎo)致大范圍的、無關(guān)流量的調(diào)整,在每個調(diào)整周期造成大范圍的鏈接斷連、丟包以及路徑切換,對網(wǎng)絡(luò)傳輸性能帶來了負面影響.顯然,這是智能路由算法迫切需要優(yōu)化的問題.

本文中,我們提出了一種對路由抖動敏感的智能路由調(diào)度算法FSR(flap suppression routing).FSR的核心思想是在實現(xiàn)全網(wǎng)鏈路負載均勻分配、最大化利用全網(wǎng)轉(zhuǎn)發(fā)資源的同時,尋求與當(dāng)前路由選擇變動最小的更新方案,使得每個更新周期帶來的路由抖動盡可能小,路由快速收斂,提升網(wǎng)絡(luò)整體轉(zhuǎn)發(fā)效率.實驗發(fā)現(xiàn),FSR算法能夠明顯提升路由收斂速度,與對照算法相比提升約30%的網(wǎng)絡(luò)吞吐量,并顯著減少網(wǎng)絡(luò)丟包和鏈路擁塞.

1 問題描述

路由選擇是互聯(lián)網(wǎng)網(wǎng)絡(luò)層的核心機制,穩(wěn)定而高效的路由選擇可以保障一個網(wǎng)絡(luò)系統(tǒng)良好的運行.傳統(tǒng)路由協(xié)議的核心建立在最短路徑的選擇上,而并未考慮網(wǎng)絡(luò)當(dāng)前的負載分布和未來可能的流量分布情況,所以傳統(tǒng)路由面對復(fù)雜網(wǎng)絡(luò)狀態(tài)特別是突發(fā)流量的情況下容易造成網(wǎng)絡(luò)擁塞.如圖1(a)左圖所示,在節(jié)點A和節(jié)點B之間的鏈路由于突發(fā)流量造成擁塞時,基于最短路徑的路由算法無法有效避讓.更令人失望的是,由于傳統(tǒng)路由選擇算法不具備從歷史流量分布中學(xué)習(xí)規(guī)律的能力,所以造成的擁塞情況在流量規(guī)律性很強的場景下會反復(fù)發(fā)生,嚴重降低網(wǎng)絡(luò)使用體驗.

因此,設(shè)計一種新型的智能化路由策略是網(wǎng)絡(luò)發(fā)展的迫切要求.它應(yīng)融合網(wǎng)絡(luò)當(dāng)前狀態(tài)信息,從網(wǎng)絡(luò)的歷史行為中尋找規(guī)律,進行智能化路由選擇,提升網(wǎng)絡(luò)運行效率,實現(xiàn)如圖1(a)右圖所示的效果.目前,已有一些相關(guān)工作利用深度學(xué)習(xí)進行路由選擇.其中,算法LRD[5]提出了獨特的流量矩陣,將流量矩陣作為深度學(xué)習(xí)的特征輸入,并且在最大化鏈路利用率的問題上給出了較好的解決方案.算法RDL[6]則首次將CNN神經(jīng)網(wǎng)絡(luò)應(yīng)用在流量工程上,與LRD不同的是,RDL以流量需求矩陣做為特征輸入,對于突發(fā)性流量具有更好的適應(yīng)性.

然而,經(jīng)過實驗研究發(fā)現(xiàn),目前智能路由算法仍然存在進一步改進的空間.由于目前的智能路由算法主要是學(xué)習(xí)歷史流量的分布特征與路由選擇直接的映射關(guān)系,并將其應(yīng)用到當(dāng)前流量環(huán)境的路由選擇問題中,所以當(dāng)網(wǎng)絡(luò)流量分布發(fā)生變化時,很容易引起較大范圍的路由抖動.如圖1(b)左圖所示,預(yù)期節(jié)點D和節(jié)點B間鏈路可用性降低時,原本僅需調(diào)整數(shù)據(jù)流2即可,即將數(shù)據(jù)流2的轉(zhuǎn)發(fā)路徑調(diào)整為A—B鏈路.但由于當(dāng)前智能路由算法尚未考慮路由振動,故無關(guān)的轉(zhuǎn)發(fā)路徑1也受到影響,重新進行了選路,這無疑會影響整個網(wǎng)絡(luò)的傳輸效率.

我們在NS3仿真平臺上設(shè)計了一個18條鏈路構(gòu)成的拓撲,對該網(wǎng)絡(luò)重放30 min的測試流量并每5 min重構(gòu)網(wǎng)絡(luò)路由,并觀察3個重構(gòu)周期,結(jié)果如表1所示:

Table 1 Impact of Oscillation Caused by Route Reconfiguration on Network Transmission表1 路由重構(gòu)引起的振動對網(wǎng)絡(luò)傳輸?shù)挠绊?/p>

RDL算法平均每次路由更新都會導(dǎo)致約9.7條鏈路受到影響,比例達到50%以上,而受到影響的完整轉(zhuǎn)發(fā)路徑達到4.7條.LRD算法相類似,在同樣實驗條件下,它會導(dǎo)致約12條鏈路受到影響,比例達到約70%,受影響的轉(zhuǎn)發(fā)路徑達到5條.這無疑會影響整體網(wǎng)絡(luò)的轉(zhuǎn)發(fā)性能.在300 Mbps帶寬的鏈路上,RDL和LRD算法分別取得的平均帶寬為229.93 Mbps和234.43 Mbps.其中,在第1個路由更新周期調(diào)整完成后,2種算法取得的平均帶寬均受到嚴重影響,分別下降到176 Mbps和135 Mbps,只能達到最大帶寬的58.67%和45%,傳輸效率受到顯著影響.

于是,針對這一問題,本文提出了一種振動抑制的智能路由選擇算法FSR,在圖1(b)右圖所示的情況下,僅調(diào)整受D—B鏈路影響的數(shù)據(jù)流2,將因此帶來的路由抖動收斂到最小狀態(tài),進而提升網(wǎng)絡(luò)傳輸效率.由此,保證盡可能少的改動網(wǎng)絡(luò)路由選擇,同時提升網(wǎng)絡(luò)資源的利用率.

2 FSR算法設(shè)計

不同于現(xiàn)有研究工作,FSR需要關(guān)注轉(zhuǎn)發(fā)路徑的變化,盡可能抑制端到端路由抖動,其主要設(shè)計思路有2個特征:

1)在挖掘歷史流量的特征信息時,不滿足于傳統(tǒng)機制對鏈路狀態(tài)與時間關(guān)聯(lián)規(guī)律的探尋,而是尋找路徑-鏈路-時間3個維度的變化特征.本文設(shè)計了如圖2所示的模型結(jié)構(gòu),通過鏈路、路徑2個維度構(gòu)建流量矩陣,再增加時間通道刻畫二維流量矩陣的時間變化特性.以此做為輸入數(shù)據(jù),使得訓(xùn)練得到的神經(jīng)網(wǎng)絡(luò)可以更加全面地刻畫流量特征,從而尋找路由動蕩最小的全局路由方案.

2)本算法針對不同的網(wǎng)絡(luò)規(guī)模,其輸入矩陣也存在較大差異.

考慮到隨輸入?yún)?shù)增加而可能出現(xiàn)的梯度消失或梯度爆炸問題,FSR算法選擇具備卷積層的CNN神經(jīng)網(wǎng)絡(luò)以更好地適應(yīng)不同規(guī)模的網(wǎng)絡(luò)輸入.

因此,本節(jié)將從算法的優(yōu)化目標(biāo)入手,著重研究FSR算法的輸入輸出處理和CNN神經(jīng)網(wǎng)絡(luò)設(shè)計,以此為基礎(chǔ)完成抖動抑制算法的設(shè)計和實現(xiàn).

FSR算法中的CNN網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示.整體結(jié)構(gòu)由卷積層、池化層和全連接層構(gòu)成,每一層的參數(shù)說明為:

第1層(L1).該層為輸入層,每個輸入樣本為10＠30×18的輸入矩陣,其中10代表共有10個時間采集點,30為整個網(wǎng)絡(luò)中有30條鏈路,18表示18個OD對.

第2層(C2).該層為卷積層,主要作用是對原始輸入樣本進行空間濾波,因此該層與輸入層之間的連接是局部連接.在該層使用15種濾波器,每種濾波器去卷積輸入矩陣就得到不同特征的映射,即得到15個特征圖.卷積核的大小設(shè)置為2×2,每個特征圖的大小為16×16.

第3層(P3).該層為池化層,主要作用是減少模型特征提取方面的誤差.我們設(shè)置2×2的池化窗口,采用最大池化的方式對上一層數(shù)據(jù)進行池化操作.

第4層(F4).該層為卷積層,作用與第2層(C2)相同,在該層使用20種濾波器,每種濾波器去卷積輸入矩陣就得到不同特征的映射,即得到20個特征圖.卷積核的大小設(shè)置為2×2,每個特征圖的大小為16×16.

第5層(H5).該層為池化層,參數(shù)與第3層(P3)相同.

第6層(O6)與第7層(B7).這2層為全連接層(第3隱含層),作用是配合前面的卷積層和后面的輸出層,組成分類部分,因此該層前后都是全連接.神經(jīng)元個數(shù)分別為60個和30個.

Fig.2 Data processing and neural network design圖2 數(shù)據(jù)處理與神經(jīng)網(wǎng)絡(luò)設(shè)計

2.1 設(shè)計目標(biāo)

考慮到當(dāng)前智能路由算法可能帶來的路由抖動問題,本文的優(yōu)化目前將以全網(wǎng)流量的均勻分布作為約束條件,以最小化相鄰時間片的路由選擇為優(yōu)化目標(biāo),設(shè)計整體智能路由算法.

具體來說,令一個網(wǎng)絡(luò)拓撲表示為無向圖G＝,其中頂點集合V表示網(wǎng)絡(luò)中的路由節(jié)點,邊集合E表示網(wǎng)絡(luò)中的鏈路.記網(wǎng)絡(luò)中某一鏈路e∈E的負載為Load e.同時,記時間片t內(nèi)所有源—目的對間的轉(zhuǎn)發(fā)路徑集合為組成路徑n的鏈路集合.則優(yōu)化目標(biāo)可以描述為

為了求解這一優(yōu)化問題,FSR算法將采用深度學(xué)習(xí)算法得到滿足Max(Load e)＜K約束條件的可行解范圍,之后在可行解范圍內(nèi)求解鏈路改變最小的最優(yōu)解.

2.2 輸入輸出

FSR算法中,滿足約束條件的可行解范圍由CNN深度學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)給出.針對CNN神經(jīng)網(wǎng)絡(luò),本節(jié)首先討論算法的數(shù)據(jù)初始化處理.

區(qū)別于傳統(tǒng)流量工程中對網(wǎng)絡(luò)流量的矩陣描述,本文中所設(shè)計的流量矩陣,同時包含路徑和鏈路的流量分布狀態(tài),在橫向和縱向2個維度的特征關(guān)聯(lián)性更強,這有助于CNN的卷積層更好地獲取這2個維度間的關(guān)聯(lián)特征.我們還在輸入上設(shè)計了時間通道,使整個數(shù)據(jù)集更加具有時間連續(xù)上的特征.

為了描述網(wǎng)絡(luò)歷史流量特征,FSR算法采用如圖2所示的三維矩陣(T,L,U)作為算法輸入.其中,T＝(T b,T b－1,…,T b－h(huán)＋1)為歷史流量數(shù)據(jù)的時間片;L＝(L01,L02,…,L ij)表示節(jié)點i到節(jié)點j間的鏈路上的流量;U＝(U01,U02,…,U mn)表示節(jié)點m到節(jié)點n的完整路徑上的流量.對矩陣中某一行求和,可以得知所有通過該鏈路的傳輸路徑的總流量.而觀察某一列的非空項,則可以得知該時間片內(nèi)此源—目的(OD)對間的路徑所包含的鏈路,橫坐標(biāo)代表了路徑情況,而縱坐標(biāo)表示鏈路情況.我們對于不同的路由拓撲輸入的矩陣大小是不同的,所以對于一旦處理維度較大的輸入矩陣時,ANN的訓(xùn)練參數(shù)會急劇增加,容易出現(xiàn)梯度消失或爆炸的現(xiàn)象.而在前面加上了卷積層的CNN能更好地去適應(yīng)不同的路由拓撲.

訓(xùn)練數(shù)據(jù)采集自MAWI Working Group Traffic Archive所提供的WIDE到上游ISP的傳輸鏈路上的跟蹤流量.首先,將網(wǎng)絡(luò)總體流量數(shù)據(jù)按照時間片分割為流量序列,這里時間片長度可以任意指定,時間片長度為5 min.之后,將該流量序列輸入到提前構(gòu)建好的網(wǎng)絡(luò)拓撲中(網(wǎng)絡(luò)拓撲具體形式參加第4節(jié)實驗部分),按照OSPF協(xié)議進行該流量序列的路由轉(zhuǎn)發(fā),并以30s的間隔觀察網(wǎng)絡(luò)流量分布情況,對于任意鏈路的負載Load e＞K的情況,剔除該流量分布數(shù)據(jù),將剩余的所有流量分布情況做為訓(xùn)練數(shù)據(jù)使用.將訓(xùn)練數(shù)據(jù)轉(zhuǎn)化為網(wǎng)絡(luò)流量特征矩陣的形式則可得到最終的訓(xùn)練集DataSettrain.

FSR算法中,CNN輸出的結(jié)果是當(dāng)前流量分布情況下的可行解范圍,具體的形式是針對每一個OD對,給出其可行路徑方案的概率值.FSR算法是去解決一個多分類的問題,于是本方案不僅為最終的結(jié)果進行了標(biāo)簽的標(biāo)注,同時為每一個OD對的路徑進行了序號的標(biāo)注,于是可以準(zhǔn)確地通過標(biāo)簽來反映出拓撲路徑的選擇.

首先,需要在算法運行之前,針對每一個OD對,給出其可選的路徑方案集合Path,為了控制神經(jīng)網(wǎng)絡(luò)算法的可行解空間,FSR算法需要對Path集合進行預(yù)處理,設(shè)每個源—目的對間的可行路徑數(shù)量上限為n,于是,對于給定的網(wǎng)絡(luò)拓撲G＝中,FSR算法需要的路徑集合Path為

FSR算法中CNN在此基礎(chǔ)上,針對每一個OD對(i,j),輸出其Path集合中每一條路徑的選擇概率p,即CNN的輸出為

之后,FSR算法在CNN的輸出集中,按照選擇概率p降序排列,并計算每一個路徑方案Path(i,j)所對應(yīng)的鏈路抖動幅度,最終將抖動幅度最小的方案做為FSR算法的輸出,進行下一時間片的路由調(diào)整.

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

CNN神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元采用ReLU激活函數(shù),具體形式為

CNN神經(jīng)網(wǎng)絡(luò)中,卷積層的正向傳播函數(shù)為

其中,a l為第l層神經(jīng)元的輸出,z l為第l層神經(jīng)元的輸入,W l為從l－1層映射到l層的權(quán)值矩陣,b l為與上面參數(shù)對應(yīng)的偏移值,σ為激活函數(shù)ReLU.另外,FSR中采用均方差來度量損失值,對應(yīng)的損失函數(shù)可為

其中,x為訓(xùn)練集輸入,y為訓(xùn)練集中期望的輸出結(jié)果.

按照CNN神經(jīng)網(wǎng)絡(luò)的基本思想我們給出全連接層也就是DNN神經(jīng)網(wǎng)絡(luò)正向傳播的公式:

根據(jù)隨機梯度下降法可以給出全連接反向傳播公式:

算法1.CNN全連接層算法.

輸入:最大迭代次數(shù)Max、學(xué)習(xí)率α、輸入的樣本對{(x1,y1),(x2,y2),…,(x m,y m)};

輸出:各層的W,b.

閾值,就跳出循環(huán)輸出各層的W,b結(jié)束?/針對池化層,本文采用的是最大池化(max pooling)的方法,設(shè)置大小為2×2的池化窗口來減少模型特征提取方面的誤差,這一誤差主要來自2個方面:1)鄰域大小受限造成的估計值方差增大;2)卷積層參數(shù)誤差造成的估計均值偏移.

結(jié)合上文給出的卷積層正向傳播函數(shù)可以得到池化層輸出的反向傳播函數(shù):

其中,upsample操作為最大池化的過程.

CNN神經(jīng)網(wǎng)絡(luò)中的所有權(quán)重都用隨機函數(shù)初始化,即高斯函數(shù)和Xavier函數(shù).利用訓(xùn)練集不斷優(yōu)化權(quán)重設(shè)置,直到獲得CNN神經(jīng)網(wǎng)絡(luò)合理的權(quán)重矩陣.

訓(xùn)練階段,FSR算法把訓(xùn)練集輸入上述CNN網(wǎng)絡(luò)中,不斷地進行迭代計算來自動地調(diào)整模型參數(shù).同時,在訓(xùn)練中采用了10重交叉驗證(10-fold cross-validation)的方式,這樣可以有效地避免陷入局部優(yōu)化問題.

在上述神經(jīng)網(wǎng)絡(luò)設(shè)計的基礎(chǔ)上,FSR算法采用如圖3所示的結(jié)構(gòu),利用歷史流量數(shù)據(jù)進行CNN神經(jīng)網(wǎng)絡(luò)的訓(xùn)練,完成訓(xùn)練后,FSR算法通過獲取實時數(shù)據(jù)進行流量特征的抓取并輸出供優(yōu)化的備選路由調(diào)整方案,通過抖動抑制機制,最終選取路由抖動最小的調(diào)整方案,進行下一時間片的路由更新.

Fig.3 Architecture of FSR algorithm圖3 FSR算法架構(gòu)

2.4 抖動抑制

CNN神經(jīng)網(wǎng)絡(luò)會給出下一時間片內(nèi)可能的流量優(yōu)化分布方案,但根據(jù)第1節(jié)討論過的,這樣的流量分布方案可能帶來普遍的路由抖動、傳輸中斷、數(shù)據(jù)重傳等問題,進而導(dǎo)致網(wǎng)絡(luò)整體傳輸性能下降.于是我們需要在待選方案中,選擇盡可能減小網(wǎng)絡(luò)振動的方案,可能的方法有:

1)最小化路徑變動.這是設(shè)計上最為簡單的方法,我們將主觀抹去所有傳輸路徑本身的差異性,僅從路徑變動的角度去衡量不同方案帶來的網(wǎng)絡(luò)振動.例如原有傳輸路徑為A—B—C—D,下一時間片給出的方案中,一項為A—E—C—D,另一項為A—E—F—D,那么我們將選擇前者,因為它相對于現(xiàn)有傳輸路徑,僅改變了一跳,帶來的可能的網(wǎng)絡(luò)抖動是最小的.這樣的處理好處是方法簡單、計算開銷小、便于大規(guī)模部署,不足之處則是忽視了不同路徑本身的重要程度.

2)最小化流量變動.這是一個更復(fù)雜但更合理的方法.若使用這一方法,則我們不再單純關(guān)注相鄰時間片網(wǎng)絡(luò)傳輸路徑的變化跳數(shù),而是要考慮被調(diào)整的路徑所對應(yīng)的總體流量大小.這是由于一條傳輸路徑在相鄰時間片內(nèi)可能存在較大的路徑調(diào)整,但是該路徑上僅有10 MB流量,我們應(yīng)該認為這對網(wǎng)絡(luò)性能的影響非常有限.如果一條路徑本身調(diào)整幅度不大,但該路徑上承載了10 GB流量,那么我們有理由相信這對網(wǎng)絡(luò)的影響遠比前者更大.

3)加權(quán)的流量變動最小化.在1)2)方法的基礎(chǔ)上,如果我們同時考慮流量的大小和優(yōu)先級,那么我們可以得到一個更加合理但復(fù)雜度顯著提升的抖動抑制方法.這需要我們更好地權(quán)衡算法有效性與算法開銷間的平衡,甚至設(shè)計專門的機器學(xué)習(xí)機制來處理算法的復(fù)雜性.

于是,綜合1)～3)路由抖動的評價思想,我們將路由抖動定義為

其中,X i表示鏈路改變數(shù)量、改變鏈路中的負載、改變路徑上的時延等可用的輸入?yún)?shù),a i表示X i所對應(yīng)的權(quán)重系數(shù).

本文我們將按照最小化路徑變動中的思想,定義備選的路徑方案相比上一時刻所最終決定的路徑方案中每個OD對改變的鏈路數(shù)量分別為m1,m2,…,m K,其中K為OD對數(shù)量.于是,按照最小化路徑變動的思想可得到:

在本文中,FSR算法采用第1種最小化路徑變動機制來抑制路由抖動,如算法2所示.

算法2.抑制振蕩算法.

輸入:OD對數(shù)量K、每個OD對改變的鏈路數(shù)量m1,m2,…,m K;

輸出:改變鏈路數(shù)量最少的路徑Jmin.

具體來說,在運行階段以5 min為一個時間間隔,在每個時間間隔結(jié)束時,把當(dāng)前網(wǎng)絡(luò)的流量情況整理為網(wǎng)絡(luò)流量特征矩陣(T,L,U)輸入CNN神經(jīng)網(wǎng)絡(luò)中.CNN神經(jīng)網(wǎng)絡(luò)此時做為擁塞控制模型最終將提供可行路徑方案的概率集合OutputCNN,將此集合做為網(wǎng)絡(luò)振動抑制算法的輸入?yún)?shù),最終FSR算法可以給出當(dāng)前時刻的最佳路由方案.

2.5 復(fù)雜度分析

我們對FSR算法的復(fù)雜度進行估算分析.從整體上來看,本文提出的FSR算法是由CNN神經(jīng)網(wǎng)絡(luò)以及抑制抖動算法所組成,我們首先來討論神經(jīng)網(wǎng)絡(luò)的復(fù)雜度.CNN神經(jīng)網(wǎng)絡(luò)的復(fù)雜度可以直接按照表達式O(M2×K2×Cin×Cout)獲得,其中M為輸出特征圖(feature map)的尺寸,K為卷積核(kernel)的尺寸,Cin為輸入通道數(shù),Cout為輸出通道數(shù).輸出特征圖尺寸又由輸入尺寸X、卷積核尺寸K、填充Pad ding、步長Stride這4個參數(shù)決定,具體可表示為M＝(X－K＋2×Pad ding)/Stride＋1.對于不同拓撲的輸入尺寸的增大,時間復(fù)雜度也會隨之升高.另一方面,本文提出的抑制振蕩算法為最小值的排序算法,抖動抑制算法時間復(fù)雜度為O(n),故整體算法的復(fù)雜度取決于神經(jīng)網(wǎng)絡(luò)的復(fù)雜度.

3 實驗分析

我們設(shè)計了4組實驗分別對FSR算法與對照組算法RDL、算法LRD進行了綜合的性能對比和實驗結(jié)果分析.實驗內(nèi)容包括擁塞率、吞吐量、傳輸路徑的平均跳數(shù)和算法運行時間.

3.1 實驗設(shè)計

在本實驗中,我們期望FSR算法訓(xùn)練得到的神經(jīng)網(wǎng)絡(luò),能夠?qū)W(wǎng)絡(luò)流量的變化產(chǎn)生恰當(dāng)?shù)姆磻?yīng),并指導(dǎo)網(wǎng)絡(luò)中的路由選擇以較低的變動成本做出有效響應(yīng),使得全網(wǎng)流量合理分攤,所有鏈路均得到高效利用.

為了驗證算法有效性,我們在NS3仿真平臺上設(shè)計了4組實驗,使用的仿真設(shè)備硬件配置為:CPU為I7-8700K,GPU為NVIDIA TESLA T4,內(nèi)存為64 GB,分別從網(wǎng)絡(luò)擁塞率、網(wǎng)絡(luò)最大吞吐量、網(wǎng)絡(luò)的平均路徑長度和運行時間這4個方面對算法性能進行了綜合的對比與分析評價.另外,由于路由選擇與網(wǎng)絡(luò)拓撲具有相關(guān)性,為了驗證算法在不同網(wǎng)絡(luò)拓撲下的性能,構(gòu)造了4種拓撲結(jié)構(gòu)同時進行實驗,如圖4所示.

關(guān)于本實驗中4種不同的拓撲設(shè)計,其目的是為了驗證在不同節(jié)點和可選路由規(guī)模的情況下,FSR算法對于網(wǎng)絡(luò)流量優(yōu)化及路由抖動抑制的綜合效果.FSR算法和當(dāng)前智能路由算法能夠優(yōu)化網(wǎng)絡(luò)流量分布的前提,是網(wǎng)絡(luò)中任意2個節(jié)點間存在足夠數(shù)量的可選路由路徑.所以對于結(jié)構(gòu)過于簡單、節(jié)點間連接不夠豐富的拓撲,路由調(diào)整空間受限,實驗無法分析出智能路由算法與傳統(tǒng)路由算法性能上的差別.因此,本實驗中,我們按照節(jié)點數(shù)量逐漸增加,可選路由數(shù)量逐漸增加的思路,設(shè)計了如圖5所示的4種拓撲結(jié)構(gòu).

Fig.4 Number of congested links in different time slices圖4 不同時間片下?lián)砣溌窋?shù)量

Fig.5 Experimental topology圖5 實驗拓撲

本節(jié)實驗中使用到的網(wǎng)絡(luò)流量來自于MAWI Working Group Traffic Archive所提供的WIDE到上游ISP的傳輸鏈路上的跟蹤流量,時間跨度為2009-03-30—2009-04-06.同時,為了橫向?qū)Ρ炔Ⅱ炞CFSR算法的性能,我們選取了RDL,LRD兩種算法.其中,LRD算法在流量工程中將流量矩陣作為深度學(xué)習(xí)的特征輸入,在最大化鏈路利用率的問題上給出了很好的解決方案.RDL算法則將CNN神經(jīng)網(wǎng)絡(luò)應(yīng)用在流量工程的問題上,并以流量需求矩陣做為特征輸入,能適應(yīng)突發(fā)性流量.

3.2 時間片選擇

本文我們將路由選擇按照時間片進行周期更新.時間片在本實驗中具體設(shè)定為5 min.關(guān)于時間片的取值,其實質(zhì)是網(wǎng)絡(luò)資源充分利用與路由穩(wěn)定性間的平衡問題.我們分別以5 min,10 min,30 min,60 min作為路由重構(gòu)的時間片選擇,使用拓撲4的網(wǎng)絡(luò)環(huán)境,以2 000 Mbps生成速率在120 min內(nèi)統(tǒng)計擁塞鏈路的數(shù)量,實驗結(jié)果如圖4所示.可以看出,時間片間隔越長,路由穩(wěn)定性越好,對于網(wǎng)絡(luò)連接的影響越小,但是另一方面,時間片間隔越長,由于路由靈活性降低,網(wǎng)絡(luò)中出現(xiàn)鏈路利用率不均的情況越來越驗證,造成網(wǎng)絡(luò)中鏈路擁塞的數(shù)量越來越大.所以得出時間片的選取將是針對不同網(wǎng)絡(luò)環(huán)境進行資源利用率和路由穩(wěn)定性間的權(quán)衡取舍,在本實驗中,5 min的時間間隔是我們在實驗中挑選的一個實踐數(shù)值,該數(shù)值在我們設(shè)置的網(wǎng)絡(luò)環(huán)境中能夠較好地平衡網(wǎng)絡(luò)流量分配和傳輸穩(wěn)定性,并證明本文提出方案的有效性.

3.3 實驗結(jié)果分析

本節(jié)將詳細討論每一組實驗的具體設(shè)計和實驗結(jié)果,并對實驗結(jié)果進行詳細分析和討論.實驗結(jié)果顯示FSR算法在得到的網(wǎng)絡(luò)性能上全方面優(yōu)于對照算法組,證明FSR算法有效抑制了路由重構(gòu)時帶來的網(wǎng)絡(luò)性能下降,與對照算法相比提升約30%的網(wǎng)絡(luò)吞吐量,同時顯著降低路徑長度和擁塞概率.

3.3.1 擁塞率

本實驗考察各算法在網(wǎng)絡(luò)流量不斷增加的情況下,能否利用網(wǎng)絡(luò)現(xiàn)有帶寬資源,保障網(wǎng)絡(luò)通信效率,盡可能減少網(wǎng)絡(luò)擁塞.

在圖5所述的4個網(wǎng)絡(luò)拓撲中,分別測試FSR,RDL以及LRD算法在網(wǎng)絡(luò)流量不斷增加的情況下網(wǎng)絡(luò)擁塞出現(xiàn)的概率.其中網(wǎng)絡(luò)流量從100 Mbps一直增長到最大3 600 Mbps,直至所有鏈路均完全擁塞,即擁塞率達到100%為止.在這一過程中,每增加100 Mbps流量分析一次網(wǎng)絡(luò)擁塞率.在本實驗中,我們將網(wǎng)絡(luò)中某一條鏈路的利用率大于某個閾值定義為該鏈路出現(xiàn)了擁塞,統(tǒng)計所有鏈路中處于擁塞狀態(tài)的鏈路占比,作為網(wǎng)絡(luò)當(dāng)前的擁塞率.我們得到了如組圖6所示的實驗結(jié)果.

Fig.6 Congestion rate experiment圖6 擁塞率實驗

FSR在每一種拓撲中,均表現(xiàn)出了最好的網(wǎng)絡(luò)擁塞抑制能力,說明FSR在不同網(wǎng)絡(luò)狀況下,均具備較為良好的網(wǎng)絡(luò)資源利用能力.具體來看,在拓撲1中,FSR與對照組算法的差異最為明顯,FSR的優(yōu)勢最大.

以全網(wǎng)10%擁塞率為例,對照組算法中,RDL算法在拓撲1中,當(dāng)源端發(fā)出流量達到280 Mpbs左右時,即出現(xiàn)10%的全網(wǎng)擁塞.LRD算法則在相同情況下,當(dāng)源端流量達到350 Mbps時,出現(xiàn)10%擁塞.OSPF算法與LRD算法相當(dāng),相對比來看,FSR算法可以堅持到源端流量達到550 Mbps時,才出現(xiàn)全網(wǎng)10%的擁塞.相比RDL和LRD,FSR算法分別提升96%與57%.再以全網(wǎng)鏈路全部擁塞出現(xiàn)時的源端流量來看,RDL算法與LRD算法非常接近,均在源端吞吐達到950 Mbps時,全網(wǎng)出現(xiàn)完全擁塞,OSPF算法則在約860 Mbps時出現(xiàn)完全擁塞.FSR算法則可以堅持到源端吞吐達到1 100 Mpbs時才出現(xiàn)全網(wǎng)擁塞.與對照組算法相比,在相同的網(wǎng)絡(luò)環(huán)境下,最大可承受的源端吞吐量提升了16%～28%.由此可見,FSR算法可形成更加合理的路由選擇,并更加充分利用全網(wǎng)網(wǎng)絡(luò)資源,在相同的網(wǎng)絡(luò)條件下,使得網(wǎng)絡(luò)可以承擔(dān)更大的流量壓力.

3.3.2 網(wǎng)絡(luò)吞吐

本實驗中,網(wǎng)絡(luò)源端的流量生成速率從50 Mbps開始持續(xù)增長,一直提升至網(wǎng)絡(luò)整體吞吐量不再發(fā)生變化,得到的結(jié)果如圖7所示.

從圖7可以看出,隨著網(wǎng)絡(luò)拓撲逐漸復(fù)雜,網(wǎng)絡(luò)節(jié)點逐漸增多,4種算法的整體吞吐量都呈現(xiàn)增長趨勢.

Fig.7 Network throughput experiment圖7 網(wǎng)絡(luò)吞吐實驗

另一方面,從整體上來看,FSR算法在相同網(wǎng)絡(luò)拓撲結(jié)構(gòu)下,相比對照組算法,能夠達到更大的網(wǎng)絡(luò)吞吐量.其中,拓撲1網(wǎng)絡(luò)環(huán)境下,4種算法差距最小,RDL和LRD算法幾乎相同,OSPF略好于前兩者,LRD算法最終達到約305 Mbps,RDL算法最終達到約320 Mbps,略微優(yōu)于LRD算法,OSPF算法達到約345 Mbps.FSR算法最終可以達到385 Mbps,相比對照組算法,分別提升約20%,26%和12%.拓撲3中,FSR算法取得了最大的吞吐量優(yōu)勢.對照組算法中,OSPF算法達到約580 Mbps,LRD算法最終取得約640 Mbps的最大吞吐量,RDL算法則可達到720 Mbps.與此相對比的是,FSR算法可以達到最大865 Mbps的最大吞吐量,相比對照組算法,分別提升約49%,20%和35%.

3.3.3 平均路徑長度

為了在網(wǎng)絡(luò)資源受限或者流量分布不均的情況下,充分利用網(wǎng)絡(luò)資源提高全網(wǎng)吞吐能力,路由路徑的調(diào)整則必然會存在“舍近求遠”的情況,從而達到網(wǎng)絡(luò)負載的均衡.

然而,一個恰當(dāng)?shù)钠骄窂介L度也是一個優(yōu)秀的路由選擇算法需要考量的因素.

在4種網(wǎng)絡(luò)拓撲中,分別運行OSPF,FSR,LRD和RDL這4種算法,同時,利用實驗設(shè)計階段選取的網(wǎng)絡(luò)流量,并分別記錄每個算法20次的網(wǎng)絡(luò)路由調(diào)整結(jié)果,計算全網(wǎng)源—目的對間的平均路徑長度,得到如圖8所示的實驗結(jié)果.

Fig.8 Average path length experiment圖8 平均路徑長度實驗

從實驗結(jié)果可以看出,隨著網(wǎng)絡(luò)結(jié)構(gòu)更加復(fù)雜、網(wǎng)絡(luò)規(guī)模不斷增大,除OSPF算法路徑不變外,其他各算法的平均路徑長度都呈現(xiàn)增長趨勢,但除去路徑不變的OSPF算法,FSR在4種拓撲情況下平均路徑均為最短.其中,拓撲1環(huán)境下,3種智能路由算法的平均路徑長度差異最小,RDL算法在經(jīng)過20次更新周期后,平均轉(zhuǎn)發(fā)路徑長度為8.09,LRD算法為7.29,而FSR算法的平均路徑長度為5.89.在拓撲3和拓撲4中,FSR的平均路徑長度均大幅度低于對照算法組中的智能路由算法.以拓撲4為例,RDL為28.34,LRD為25.94,同情況下FSR則為16.11,平均路徑長度分別降低了43%和38%,但相比OSPF算法依然提升了約79%.

綜上所述,通過對4種拓撲下3個算法的測量可以發(fā)現(xiàn),FSR給出的路由選擇,其平均路徑長度相比對照算法組,有明顯的降低,可以以更高的效率完成數(shù)據(jù)的轉(zhuǎn)發(fā)操作.

3.3.4 算法運行時間

除了網(wǎng)絡(luò)性能之外,一個路由選擇算法還需要考慮算法自身的效率問題,效率低下的算法可能導(dǎo)致路由計算開銷較大,從而影響算法可用性,為了考察FSR算法的算法效率,我們設(shè)計了一組實驗,在同樣進行20次路由選擇的條件下,記錄3種智能路由選擇算法的運行時間,并在4種不同的拓撲上分別進行該實驗.

通過實驗可以發(fā)現(xiàn),在4種不同的拓撲下,算法運行時間略有差異,在3種算法的橫向?qū)Ρ戎?FSR算法的總體運行時間最長.這主要是由于FSR算法與對比組算法相比,為了減少網(wǎng)絡(luò)中的路由抖動而多了一個處理環(huán)節(jié).這一設(shè)計一方面確實增強了網(wǎng)絡(luò)整體運行效率,而另一方面也帶來了一定的額外時間成本.

具體來說,FSR算法在20次路由調(diào)整過程中,最短用時3.35s,最長用時4.38s,平均用時3.73s.而與之對比的是,對照組算法中,RDL算法最短用時2.28 s,最長用時3.3 s,平均用時2.69 s,LRD算法最短用時2.83 s,最長用時3.68 s,平均用時為3.17 s.FSR算法運行時間確實長于對照組的2種算法,平均運行時間方面,FSR相比RDL要多消耗1.04 s,而相比LRD算法要多消耗0.56 s.

通過上述實驗可以看出,FSR算法由于額外的抖動抑制操作,在運行時間上比對照組算法多出了額外的時間開銷.但考慮到FSR算法在實際吞吐率測試中帶來約30%的帶寬提升,不難發(fā)現(xiàn)即便存在算法運行速度上的劣勢,但FSR算法由于抑制了網(wǎng)絡(luò)振動,仍舊可以實現(xiàn)比現(xiàn)有機制更好的網(wǎng)絡(luò)傳輸效率.

4 相關(guān)工作

流量工程和路由策略是互聯(lián)網(wǎng)技術(shù)的基礎(chǔ)并受到了學(xué)術(shù)界和工業(yè)界的共同研究.這些研究廣泛涉及了互聯(lián)網(wǎng)的各種應(yīng)用形式,包括傳統(tǒng)網(wǎng)絡(luò)[7]、數(shù)據(jù)中心網(wǎng)絡(luò)[8]和核心骨干網(wǎng)[9].相關(guān)研究的核心目標(biāo)均是為了滿足在復(fù)雜多變的應(yīng)用環(huán)境中盡可能地優(yōu)化滿足靈活的服務(wù)質(zhì)量要求,而這一個問題的求解則建立在數(shù)學(xué)模型的建立和求解基礎(chǔ)上.然而,正如引言所述,網(wǎng)絡(luò)規(guī)模的龐大和流量需求的多變?yōu)檫@一類問題的數(shù)學(xué)建模工作提出了巨大的挑戰(zhàn),通常的做法是針對具體應(yīng)用場景進行必要的簡化假設(shè),并以此使得數(shù)學(xué)模型可以有效求解.然而現(xiàn)實網(wǎng)絡(luò)環(huán)境往往是多種應(yīng)用需求、流量特性和網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜疊加,簡化假設(shè)在實際場景中往往難以滿足.針對上述問題,目前還難以找到一個有效的通用模型,并在優(yōu)化效果上達到實際使用的需求,因此,傳統(tǒng)基于數(shù)學(xué)模型的網(wǎng)絡(luò)管理機制越來越難以滿足快速發(fā)展的網(wǎng)絡(luò)應(yīng)用的需求.

另一方面,隨著計算能力的提高和數(shù)據(jù)的爆炸式增長,人工智能得到了極大的發(fā)展,強大的計算能力可以模仿更深的神經(jīng)網(wǎng)絡(luò)(DNN),而大數(shù)據(jù)可以提供足夠的訓(xùn)練樣本.其中人工神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)技術(shù)取得了最大的發(fā)展,其通過構(gòu)建更多層次的深度神經(jīng)網(wǎng)絡(luò),實現(xiàn)學(xué)習(xí)和識別抽象模式,并已廣泛應(yīng)用于圖像分類、物體識別、通信以及其他各個相關(guān)領(lǐng)域[10-11].

機器學(xué)習(xí)技術(shù)已被廣泛應(yīng)用于解決各類網(wǎng)絡(luò)管理問題,包括擁塞控制[12-13]、資源分配[14]和視頻流的比特率選擇[15]等.其中,對于路由選擇問題,早期Q路由[16]首次將Q學(xué)習(xí)[17]應(yīng)用于網(wǎng)絡(luò)路由上下文.與傳統(tǒng)基于最短路徑的路由策略相比,Q路由通過歷史規(guī)律的學(xué)習(xí),可以更加有效地避免網(wǎng)絡(luò)擁塞并降低傳輸時延.在Q路由中,每個路由器分別學(xué)習(xí)從數(shù)據(jù)包頭到輸出端口的映射.這涉及路由器以每個數(shù)據(jù)包分辨率不斷交換有關(guān)其針對不同目的地的延遲信息.我們認為,在每個數(shù)據(jù)包級別上以分散方式進行操作,在可伸縮性和通信開銷方面提出了重大挑戰(zhàn).

針對這些問題,近年來也取得了一定的研究成果[18-19].其中,LRD算法通過強化學(xué)習(xí)的方式來進行智能的路由選擇,將經(jīng)典的最小化最大鏈路利用率作為研究的目標(biāo),希望通過歷史網(wǎng)絡(luò)流量來驅(qū)動路由的選擇.RDL采用了深度卷積神經(jīng)網(wǎng)絡(luò)(CNN)來控制網(wǎng)絡(luò)流量,利用當(dāng)前請求發(fā)送的流量數(shù)據(jù)來合理地規(guī)劃路由的路徑選擇,通過利用在線的方式不斷地迭代CNN神經(jīng)網(wǎng)絡(luò),以此來得到更具適應(yīng)力、平均時延和丟包率更低的模型.然而,正如本文引言討論的,當(dāng)前智能路由算法對路由更新時的振動抑制還存在較大優(yōu)化空間.

5 總 結(jié)

隨著網(wǎng)絡(luò)流量的快速增長以及網(wǎng)絡(luò)應(yīng)用模式的不斷更新,路由機制及網(wǎng)絡(luò)設(shè)備的轉(zhuǎn)發(fā)能力面臨著更為嚴峻的考驗,傳統(tǒng)的、相對固化的路由算法已經(jīng)很難滿足當(dāng)前不斷增長和變化的網(wǎng)絡(luò)需求.

動態(tài)靈活的路由調(diào)整機制,以及基于歷史數(shù)據(jù)學(xué)習(xí)網(wǎng)絡(luò)流量和路由選擇規(guī)律的能力,是智能路由算法核心優(yōu)勢所在.本文聚焦于當(dāng)前智能路由算法在每個路由更新周期所帶來的大范圍的路由抖動以及由此引發(fā)的網(wǎng)絡(luò)轉(zhuǎn)發(fā)效率降低的問題,提出了一種路由抖動敏感的智能路由選擇算法,核心思想是在追求全網(wǎng)鏈路負載均勻分配、充分利用全網(wǎng)轉(zhuǎn)發(fā)資源的同時,尋求與當(dāng)前路由選擇變動最小的更新方案,使得每個更新周期帶來的路由抖動盡快收斂,提升網(wǎng)絡(luò)整體轉(zhuǎn)發(fā)效率.FSR算法利用CNN生成當(dāng)前網(wǎng)絡(luò)拓撲環(huán)境的路由方案可行解,并從可行解中尋找路由抖動最小的最優(yōu)解.實驗表明:FSR算法與對照算法相比提升約30%的網(wǎng)絡(luò)吞吐量,同時顯著降低網(wǎng)絡(luò)丟包和擁塞概率.

未來,我們將會結(jié)合具體的網(wǎng)絡(luò)應(yīng)用場景,進一步研究更有針對性的其他路由抖動收斂機制,同時重點研究算法時間開銷的優(yōu)化方法,提升FSR算法的執(zhí)行效率.

作者貢獻聲明:邵天竺,負責(zé)實驗方案設(shè)計與仿真、數(shù)據(jù)分析,參與方案設(shè)計、論文編寫;王曉亮(通信作者),負責(zé)方案設(shè)計、論文編寫,參與實驗方案設(shè)計;陳文龍,參與方案設(shè)計;唐曉嵐,參與實驗方案設(shè)計;徐敏,參與方案設(shè)計、數(shù)據(jù)分析.