一種減少網絡振動的智能路由選擇算法設計

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

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

(nestea_god＠hotmail.com)

近年來互聯網和移動通信產業的快速發展,網絡系統不斷向著規?；悩嫽?、動態化的方向演進[1].同時,伴隨著5G網絡的成熟,萬物互聯將帶來網絡終端數量、網絡流量以及應用形式上的新一輪爆發性增長,并對數據轉發速率、超低延遲、高能效比和大規模連接提出更高的要求[2].由此帶來的服務能力和復雜性問題使得當前的網絡系統面臨無數新的挑戰,現有盡力而為的路由轉發算法難以滿足這些應用所帶來的多樣化的網絡服務質量需求.

隨著網絡環境的不斷發展,當面對突發流量或大流量時,基于最短路徑的傳統路由協議可能導致嚴重的網絡擁塞.互聯網需要一種更加智能的路由策略,將網絡狀態與路由策略融合,提升網絡服務質量.然而互聯網龐大的網絡規模和數據流量使得智能機制的設計充滿挑戰.

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

以深度學習技術為基礎的智能路由算法設計,其核心思想是利用大數據驅動的網絡特征獲取機制,從部署范圍的歷史數據中尋找路由選擇與時間、或路由選擇與流量間的映射關系,從而指導后續路由優化.

相比傳統數學模型支持下的路由策略設計,數據驅動的智能路由算法具有復雜度低和通用性強等優勢.其中,復雜度低主要體現在其避免了針對網絡復雜特性和多樣需求的數學建模工作,以歷史流量數據為基礎,通過神經網絡的迭代訓練代替精確建模,大幅降低核心映射的獲取復雜度;通用性強則體現在相同的機器學習模型,可以面向不同的網絡環境和需求場景,采用不同的數據集來求解對應的差異化問題.

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

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

1 問題描述

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

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

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

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

Table 1 Impact of Oscillation Caused by Route Reconfiguration on Network Transmission表1 路由重構引起的振動對網絡傳輸的影響

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

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

2 FSR算法設計

不同于現有研究工作,FSR需要關注轉發路徑的變化,盡可能抑制端到端路由抖動,其主要設計思路有2個特征:

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

2)本算法針對不同的網絡規模,其輸入矩陣也存在較大差異.

考慮到隨輸入參數增加而可能出現的梯度消失或梯度爆炸問題,FSR算法選擇具備卷積層的CNN神經網絡以更好地適應不同規模的網絡輸入.

因此,本節將從算法的優化目標入手,著重研究FSR算法的輸入輸出處理和CNN神經網絡設計,以此為基礎完成抖動抑制算法的設計和實現.

FSR算法中的CNN網絡結構如圖2所示.整體結構由卷積層、池化層和全連接層構成,每一層的參數說明為:

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

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

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

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

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

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

Fig.2 Data processing and neural network design圖2 數據處理與神經網絡設計

2.1 設計目標

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

具體來說,令一個網絡拓撲表示為無向圖G＝,其中頂點集合V表示網絡中的路由節點,邊集合E表示網絡中的鏈路.記網絡中某一鏈路e∈E的負載為Load e.同時,記時間片t內所有源—目的對間的轉發路徑集合為組成路徑n的鏈路集合.則優化目標可以描述為

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

2.2 輸入輸出

FSR算法中,滿足約束條件的可行解范圍由CNN深度學習神經網絡給出.針對CNN神經網絡,本節首先討論算法的數據初始化處理.

區別于傳統流量工程中對網絡流量的矩陣描述,本文中所設計的流量矩陣,同時包含路徑和鏈路的流量分布狀態,在橫向和縱向2個維度的特征關聯性更強,這有助于CNN的卷積層更好地獲取這2個維度間的關聯特征.我們還在輸入上設計了時間通道,使整個數據集更加具有時間連續上的特征.

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

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

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

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

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

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

2.3 神經網絡設計

CNN神經網絡中的神經元采用ReLU激活函數,具體形式為

CNN神經網絡中,卷積層的正向傳播函數為

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

其中,x為訓練集輸入,y為訓練集中期望的輸出結果.

按照CNN神經網絡的基本思想我們給出全連接層也就是DNN神經網絡正向傳播的公式:

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

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

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

輸出:各層的W,b.

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

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

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

CNN神經網絡中的所有權重都用隨機函數初始化,即高斯函數和Xavier函數.利用訓練集不斷優化權重設置,直到獲得CNN神經網絡合理的權重矩陣.

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

在上述神經網絡設計的基礎上,FSR算法采用如圖3所示的結構,利用歷史流量數據進行CNN神經網絡的訓練,完成訓練后,FSR算法通過獲取實時數據進行流量特征的抓取并輸出供優化的備選路由調整方案,通過抖動抑制機制,最終選取路由抖動最小的調整方案,進行下一時間片的路由更新.

Fig.3 Architecture of FSR algorithm圖3 FSR算法架構

2.4 抖動抑制

CNN神經網絡會給出下一時間片內可能的流量優化分布方案,但根據第1節討論過的,這樣的流量分布方案可能帶來普遍的路由抖動、傳輸中斷、數據重傳等問題,進而導致網絡整體傳輸性能下降.于是我們需要在待選方案中,選擇盡可能減小網絡振動的方案,可能的方法有:

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

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

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

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

其中,X i表示鏈路改變數量、改變鏈路中的負載、改變路徑上的時延等可用的輸入參數,a i表示X i所對應的權重系數.

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

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

算法2.抑制振蕩算法.

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

輸出:改變鏈路數量最少的路徑Jmin.

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

2.5 復雜度分析

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

3 實驗分析

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

3.1 實驗設計

在本實驗中,我們期望FSR算法訓練得到的神經網絡,能夠對網絡流量的變化產生恰當的反應,并指導網絡中的路由選擇以較低的變動成本做出有效響應,使得全網流量合理分攤,所有鏈路均得到高效利用.

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

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

Fig.4 Number of congested links in different time slices圖4 不同時間片下擁塞鏈路數量

Fig.5 Experimental topology圖5 實驗拓撲

本節實驗中使用到的網絡流量來自于MAWI Working Group Traffic Archive所提供的WIDE到上游ISP的傳輸鏈路上的跟蹤流量,時間跨度為2009-03-30—2009-04-06.同時,為了橫向對比并驗證FSR算法的性能,我們選取了RDL,LRD兩種算法.其中,LRD算法在流量工程中將流量矩陣作為深度學習的特征輸入,在最大化鏈路利用率的問題上給出了很好的解決方案.RDL算法則將CNN神經網絡應用在流量工程的問題上,并以流量需求矩陣做為特征輸入,能適應突發性流量.

3.2 時間片選擇

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

3.3 實驗結果分析

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

3.3.1 擁塞率

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

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

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

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

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

3.3.2 網絡吞吐

本實驗中,網絡源端的流量生成速率從50 Mbps開始持續增長,一直提升至網絡整體吞吐量不再發生變化,得到的結果如圖7所示.

從圖7可以看出,隨著網絡拓撲逐漸復雜,網絡節點逐漸增多,4種算法的整體吞吐量都呈現增長趨勢.

Fig.7 Network throughput experiment圖7 網絡吞吐實驗

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

3.3.3 平均路徑長度

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

然而,一個恰當的平均路徑長度也是一個優秀的路由選擇算法需要考量的因素.

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

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

從實驗結果可以看出,隨著網絡結構更加復雜、網絡規模不斷增大,除OSPF算法路徑不變外,其他各算法的平均路徑長度都呈現增長趨勢,但除去路徑不變的OSPF算法,FSR在4種拓撲情況下平均路徑均為最短.其中,拓撲1環境下,3種智能路由算法的平均路徑長度差異最小,RDL算法在經過20次更新周期后,平均轉發路徑長度為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個算法的測量可以發現,FSR給出的路由選擇,其平均路徑長度相比對照算法組,有明顯的降低,可以以更高的效率完成數據的轉發操作.

3.3.4 算法運行時間

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

通過實驗可以發現,在4種不同的拓撲下,算法運行時間略有差異,在3種算法的橫向對比中,FSR算法的總體運行時間最長.這主要是由于FSR算法與對比組算法相比,為了減少網絡中的路由抖動而多了一個處理環節.這一設計一方面確實增強了網絡整體運行效率,而另一方面也帶來了一定的額外時間成本.

具體來說,FSR算法在20次路由調整過程中,最短用時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%的帶寬提升,不難發現即便存在算法運行速度上的劣勢,但FSR算法由于抑制了網絡振動,仍舊可以實現比現有機制更好的網絡傳輸效率.

4 相關工作

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

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

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

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

5 總 結

隨著網絡流量的快速增長以及網絡應用模式的不斷更新,路由機制及網絡設備的轉發能力面臨著更為嚴峻的考驗,傳統的、相對固化的路由算法已經很難滿足當前不斷增長和變化的網絡需求.

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

未來,我們將會結合具體的網絡應用場景,進一步研究更有針對性的其他路由抖動收斂機制,同時重點研究算法時間開銷的優化方法,提升FSR算法的執行效率.

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