基于深度學習的流量工程算法研究與應用

胡道允，齊進，陸錢春，李鋒，房紅強

研究與開發

基于深度學習的流量工程算法研究與應用

胡道允1，齊進1，陸錢春1，李鋒1，房紅強2

（1. 移動網絡和移動多媒體技術國家重點實驗室，廣東 深圳 518057； 2. 中國科學技術大學，安徽 合肥 230026）

隨著5G網絡的發展和應用，網絡中的業務數量呈現出爆發式增長，網絡中的帶寬資源日趨緊張。為了提高網絡資源利用率，并滿足用戶日益提高的業務服務質量要求，基于軟件定義網絡（SDN）提出了一種基于深度學習的流量工程算法（DL-TEA）。通過仿真證明該算法不僅能夠實時地為業務計算一條高效的路徑，同時還能夠提升業務的QoS、網絡資源利用率，降低網絡阻塞率。

軟件定義網絡；流量工程；深度學習；服務質量

1 引言

隨著互聯網技術的發展，尤其隨著5G網絡的部署和應用，網絡中需要傳輸的數據量呈現出爆發式的增長，網絡資源日趨緊張。而用戶對業務QoS（quality of service，服務質量）的要求卻在不斷提高，這給傳統的網絡管理系統帶來了巨大的挑戰。近年來，SDN（software defined networking，軟件定義網絡）的概念被廣泛關注，它通過解耦傳統路由器中的控制和轉發功能，形成一個統一的集中式控制平面[1]。控制平面可以實時地獲得網絡的全局視野和流量信息，實現網絡業務流量的精細化管理，從而提升網絡資源利用率[2-3]。然而，網絡中業務流量的突發性和動態性特點越來越明顯，傳統的最短路由算法極有可能使網絡發生網絡擁塞或者帶寬閑置，這會造成業務QoS下降或者網絡資源浪費[4]。傳統的基于全局業務的網絡資源優化算法，雖然能夠提升網絡資源利用率，但是無法滿足網絡中業務請求的動態性和實時性要求[5-6]。

為解決上述問題，本文基于SDN提出了一種基于DL（deep learning，深度學習）的流量工程算法（DL-TEA）。該算法主要分為離線訓練和在線決策兩個階段：在離線訓練階段，通過深度學習模型學習啟發式算法的路徑信息；在線決策階段利用訓練好的深度學習模型對網絡拓撲進行剪枝，然后利用貪婪算法計算最優路徑。因此，DL-TEA的在線運行耗時和貪婪算法相近，滿足了動態業務的實時路由需求。另外，通過深度學習模型保留了啟發式算法的特征信息，使得DL-TEA的性能接近啟發式算法，與貪婪算法相比，提升了請求QoS、網絡資源利用率，降低了網絡阻塞率。

2 研究現狀

針對動態業務的實時路由問題，參考文獻[7]提出利用遺傳算法更新網絡中鏈路的權重，然后再利用最短路徑算法計算業務路由，該方法雖然能夠保證當前業務路徑最優，但是無法保證網絡全局資源的合理化分配。而針對批量業務的全局最優問題，已經被證明為多商品流問題[5]。由于多商品流問題為NP難問題，所以參考文獻[6]提出了一種SAGA算法，該算法結合遺傳算法和模擬退火算法，通過局部搜索達到負載均衡的目的，但是該算法時間復雜度較高，并且是針對全局靜態請求的優化，無法滿足動態業務的實時性需求。

最近，人工智能技術受到大家的廣泛關注，并且已有相關研究在討論將人工智能技術引入網絡管理中[8]。參考文獻[9]探討了將機器學習應用到網絡的路由場景中。參考文獻[10]提出為業務計算多條路徑，并通過機器學習模型實現快速路由決策。參考文獻[11]通過統計歷史路徑信息，然后利用深度強化學習算法從歷史路徑集合中選擇合適的傳輸路徑。雖然上述兩種算法均能夠解決動態業務的實時路由問題，但是業務的路徑只能從固定的路徑集合中選擇。而本文提出的DL-TEA則是利用深度學習模型統計各鏈路在不同網絡狀態下被不同請求占用的概率信息，然后根據概率信息進行拓撲剪枝，因此業務傳輸路徑不會受限于固定的路徑集合。參考文獻[12]提出先將網絡流進行分類，然后基于深度強化學習實現QoS的路由算法。參考文獻[13]指出深度強化學習在網絡流問題中存在收斂慢、魯棒性低的缺點，并提出通過將網絡節點劃分為驅動節點和從節點的方式壓縮問題的維度，從而提高了模型的收斂時間，但是使用的網絡規模仍控制在100個節點以內，而本文提出的DL-TEA在仿真實驗中能夠支持1 000個節點以上規模的網絡拓撲運算。

3 算法設計

本文提出的DL-TEA算法主要包含兩個部分——離線訓練過程和在線決策過程，如圖1所示。

圖1 基于深度學習的動態路由決策過程

離線訓練過程：首先統計或模擬網絡中的歷史請求信息，然后將批量業務請求和網絡信息作為啟發式算法的輸入，再通過第3.2節中的啟發式算法計算業務路由信息并生成訓練集，最后對深度學習模型進行離線訓練。

在線決策過程：當SDN控制器收到新的業務請求時，將請求信息和當前網絡狀態信息作為輸入傳遞給訓練好的深度學習模型，經過模型計算得到鏈路系數。然后根據鏈路系數大小，通過設置閾值對網絡拓撲進行剪枝，保留系數較大的鏈路。最后根據剪枝后的拓撲，利用第3.1節中的貪婪算法進行路由計算并輸出業務路由信息。另外，由于有限的訓練集無法涵蓋所有的網絡狀態和請求信息，所以模型存在一定概率導致拓撲剪枝過度，造成業務路由計算失敗。為避免上述情況，當業務路徑計算失敗時，DL-TEA會取全量的網絡信息重新進行路由計算。

本文中，使用符號(,,,)表示網絡狀態信息，其中，∈表示網絡節點，(,)∈表示網絡鏈路；b表示鏈路上可用的帶寬。D表示鏈路上的時延信息。另外，定義鏈路∈上權重設置為m。定義(s, d, b)∈表示業務請求，其中，表示請求的源地址，表示請求的目的地址，表示請求的帶寬需求。最終，需要為每個業務都計算一條滿足帶寬需求的路徑P=(e1,e2,…,e)。

3.1 貪婪算法

由于在實際網絡中，用戶會根據不同的業務場景設置不同的優化目標。因此，貪婪算法需要根據用戶的需求設置不同的鏈路權重，然后利用Dijkstra算法計算權重最優路徑。本文中將針對占用帶寬之和最小、請求時延之和最小和網絡擁塞最小3個場景進行討論。針對業務占用帶寬之和最小的優化目標，如式（1）所示。

此場景中，只需保證每個業務的路徑最短，即可得到業務的最優路徑。因此，定義鏈路權重如式（2）所示，針對請求，如果請求帶寬b小于鏈路剩余帶寬b，鏈路權重m=1，否則為無窮大。

同理，針對請求時延之和最小的優化目標，將鏈路的時延設置為鏈路的權重，然后利用Dijkstra算法計算一條滿足帶寬需求的最短時延路徑。

而針對網絡擁塞最小的優化目標，鏈路∈上權重設置為m，如式（3）所示，如果鏈路剩余帶寬大于請求帶寬，則鏈路權重等于鏈路總帶寬除以鏈路剩余帶寬，然后乘以負載均衡系數，否則設置為無窮大。因此，當鏈路上剩余的帶寬資源較多時，則鏈路的權重m較小，在使用Dijkstra算法計算路由時，將更傾向經過該鏈路，從而保證網絡的資源部署相對均衡，減少網絡擁塞。

3.2 啟發式算法

針對批量業務全局優化的流量工程問題，業界已經提出了很多優秀的啟發式算法[5,7]。本文基于模擬退火算法設計了啟發式算法，該算法通過調整業務的路由信息，不斷搜索較優的路由結果，從而實現網絡資源優化。

步驟（1）、（2）利用貪婪算法依次為請求求解并扣除帶寬資源，產生初始解。步驟（3）~（11）為模擬退火過程，每次迭代會隨機選擇一批請求，在釋放帶寬資源后，隨機調整請求順序，然后利用貪婪算法重新計算和部署業務，產生新的結果。最后計算評價函數()，如果新解的結果優于之前的解，則接受該結果，否則按概率接受該組結果。值得注意的是，不同優化目標場景下的評價函數()是不同的。

算法1 模擬退火算法

輸入 網絡拓撲，請求（包含個請求）

輸出 請求的傳輸路徑

（1）根據不同目標設置鏈路權重值

（2）利用貪婪算法依次計算出每個請求的最短路徑，并扣除帶寬資源

（3）while 評價函數沒有收斂：

（4）按概率λ隨機抽取部分業務

（5） 釋放業務的路由和帶寬信息

（6） 亂序后重新利用貪婪算法計算業務路由集合

（7） if()()；

（8） 接受該解

（9） else

（10） 按概率接受新解

（11） end if

3.3 深度學習模型

將請求信息和網絡狀態作為神經網絡的輸入，以當前網絡狀態下業務經過鏈路的概率為輸出，如式（4）所示其中，表示請求的源站點信息，表示請求目的站點信息，表示請求帶寬信息，B表示鏈路的帶寬信息，D表示鏈路的時延信息，h表示鏈路被該請求占用的概率信息。

本文中，采用一個深度神經網絡（DNN），如圖2所示。另外，將請求的源目的節點進行one-hot編碼，因此神經網絡的輸入維度擴展為12，輸出維度為||。針對DNN的隱藏層，采用ReLU函數作為激活函數，并利用殘差網絡對其進行優化，通過殘差塊能夠有效地避免神經網絡的退化問題。針對輸出層采用了sigmoid函數作為激活函數，并在輸出層前添加dropout防止過擬合。輸入的帶寬以及時延不是0到1之間的數值，在中間層加了幾層批量正則化（batch- normalization）層使得經過該層的結果均值為0、方差為1，從而使得模型訓練得更快以及防止梯度爆炸和梯度消失的問題出現。

本文中模擬了不同負載量下不同時刻的請求集合，訓練集生成流程如算法2所示，針對某一時刻的請求集合Q，利用啟發式算法進行網絡優化，得到請求對應的路徑集合P。針對每組結果，執行K次循環，每次循環需要重置網絡狀態，對請求進行隨機排序，然后依次部署請求。在部署過程中，取當前網絡狀態以及當前請求信息和路徑信息作為一個訓練樣本，如步驟（3）～（7）所示。針對單個訓練樣本，如果請求q的路徑pq經過鏈路e，則鏈路e對應的值為1，否則為0。

算法2 訓練集生成過程

輸入 網絡拓撲，批量請求集合

輸出 訓練子集

（1）根據啟發式算法進行求解，得到路徑集合

（2）for=1 to；

（3） 重置網絡狀態，對請求隨機排序

（4） forin；

（5） 收集當前網絡狀態以及請求信息和路徑信息作為訓練樣本

（6） 按路徑部署該請求

（7） end for

（8）end for

4 仿真驗證

在仿真驗證階段，將對比貪婪算法、模擬退火算法和DL-TEA 3種算法在不同優化目標場景下的算法性能和算法耗時。為了保證仿真的準確性，采用了國內某省份的回傳網絡作為仿真拓撲，該拓撲共1 161個節點、2 760條鏈路，如圖3所示。

另外，本文按Erlang=3 500的負載規模，模擬了50個時刻的請求分布情況，每個時刻網絡中平均3 500個請求。然后利用第3節中所述方法生成數據集。其中隨機選擇了40個時刻的數據作為訓練集，剩余10個時刻的數據作為測試集。

圖3 仿真拓撲

用上述數據集對神經網絡模型進行訓練和測試。針對一個請求，如果神經網絡給出的相關鏈路輸出值和訓練集或測試集對應的輸出一致，則認為模型輸出準確，反之則認為輸出錯誤。本文定義鏈路準確率等于正確的輸出鏈路總數除以所有的鏈路輸出總數。鏈路正確率統計結果如圖4所示：從結果中能夠看出，隨著訓練次數的增加，模型的準確率也逐漸提升，最終收斂在99.5%以上。

圖4 深度神經網絡模型鏈路準確率統計

另外，利用上述訓練好的模型，使用DL-TEA對10組測試集中的請求進行求解，最后取10組結果的平均值作為最終仿真結果。

DL-TEA和貪婪算法、模擬退火算法的請求時延對比如圖5所示。從圖5中能夠看出貪婪算法的請求平均時延最高，DL-TEA算法的請求平均時延低于貪婪算法，可以得出DL-TEA算法能夠更好地保證業務的QoS。但是，由于DL-TEA算法是基于模擬退火算法結果進行訓練的，所以請求平均時延略高于模擬退火算法。

圖5 請求平均時延

3種算法的耗時對比如圖6所示，能夠看出DL-TEA和貪婪算法的耗時基本一致，甚至耗時更少，這是因為DL-TEA在在線決策階段，僅需要根據剪枝后的拓撲進行算路，拓撲規模會比原拓撲更小，所以耗時更低。由于模擬退火算法需要不斷迭代，所以耗時最久。這也驗證了DL-TEA能夠滿足業務的高動態實時路由需求。

圖6 算法耗時對比

帶寬占用之和最小場景的仿真結果如圖7所示。在該場景中，統計了請求平均的帶寬占用情況。從結果中能夠看出，DL-TEA比貪婪算法占用了更少的帶寬資源。換句話說，DL-TEA能夠提升網絡的資源利用率。

圖7 請求平均占用帶寬

另外，從圖5和圖7的結果中能夠發現，隨著網絡負載量的提升，請求的平均時延和平均帶寬的占用均會提升。這主要是因為在低負載量的情況下，網絡資源相對充足，業務均可以選擇最小時延或最小跳路徑進行傳輸。當網絡負載量增加時，部分鏈路會出現資源不足的情況，導致部分業務需要走其他路徑進行傳輸，因此請求的平均時延和平均帶寬占用均略有提升。

3種算法在負載均衡場景下的網絡阻塞率仿真結果如圖8所示。從結果中能夠看出，DL-TEA算法的阻塞率同樣低于貪婪算法，并且略高于啟發式算法。綜上所述，DL-TEA算法與貪婪算法相比，能夠保證業務的QoS，提高網絡的資源利用率，降低網絡阻塞率，并且滿足高動態業務的實時路由需求。

圖8 網絡阻塞率仿真結果

由于深度模型的輸出結果是0到1之間的連續數值，所以還需要設置一個合理的閾值來對拓撲進行剪枝。因此本文統計了3 000個請求負載情況下網絡阻塞率和鏈路保留率之間的關系見表1：當保留的鏈路太少時，由于網絡連通性降低，網絡的阻塞率會增加。當僅保留2%左右的鏈路時，網絡阻塞率降至最低，但隨著鏈路保留率的增加，DL-TEA的性能會逐漸退化成貪婪算法。因此，本文的仿真場景中，DL-TEA根據模型輸出的鏈路系數對鏈路進行排序，然后每次僅保留前2%的鏈路集合進行路由。另外，還統計了訓練集中同源宿請求在不同網絡狀態下的路徑分布情況，發現在該仿真拓撲中，同源宿請求的路徑分布相對比較集中，平均每個請求占用的鏈路數量比例也在2%左右。

表1 鏈路保留率和網絡阻塞率關系

另外值得一提的是，在不同組網情況下，鏈路保留率和算法性能之間的關系也會有不同。在仿真場景中，還測試了200個節點的拓撲，發現鏈路保留率在30%時DL-TEA算法性能達到最優，因此，DL-TEA需要依據不同的拓撲組網進行調整。

5 結束語

本文提出了基于深度學習的流量工程算法，并通過仿真驗證該算法既能夠滿足高動態業務的實時路由需求，同時還能夠保證業務的QoS、提升網絡資源利用率、降低網絡阻塞率。但是本文尚未考慮多約束場景下的業務路由問題，后續可以在該方向繼續研究。

[1]MCKEOWN N, ANDERSON T. OpenFlow: enabling innovation in campus networks[C]//Proceedings of ACM SIGCOMM 2008. New York: ACM Press, 2008.

[2]王素彬, 朱永慶. SDN與流量精細化運營[J]. 電信科學, 2014, 30(11): 145-153.

WANG S B, ZHU Y Q. SDN and Traffic Fine Operation[J]. Telecommunications Science, 2014, 30(11): 145-153.

[3]張奇. SDN在傳送網中的關鍵技術及流量工程應用場景[J]. 電信科學, 2015, 31(Z1): 158-162.

ZHANG Q. Key technologies of SDN in transport network and application scenarios of traffic engineering[J].Telecommunications Science, 2015, 31(Z1): 158-162.

[4]樊自甫, 伍春玲, 王金紅. 基于SDN 架構的數據中心網絡路由算法需求分析[J]. 電信科學, 2015, 31(2): 36-45.

FAN Z F, WU C L, WANG J H. Requirements analysis of data center network routing algorithm based on SDN architecture[J]. Telecommunications Science, 2015, 31(2): 36-45.

[5]YU M, REXFORD J, FREEDMAN M J, et al. Scalable flow based networking with DIFANE[C]//Proceedings of SIGCOMM 2010. [S.l.:s.n.], 2010: 351-362

[6]CURTIS A R, KIM W, YALAGANDULA P. Mahout: low-overhead datacenter traffic management using end-host-based elephant detection[C]//Proceedings of IEEE INFOCOM2011. Piscataway: IEEE Press, 2011: 1629-1637.

[7]黃婧潔. SDN網絡的流量工程模型及算法研究[D]. 北京: 北京郵電大學, 2015.

HUANG J J. Research on traffic engineering model and algorithms of SDN[D]. Beijing: Beijing University of Posts and Telecommunication, 2015.

[8]張嗣宏, 左羅. 基于人工智能的網絡智能化發展探討[J]. 中興通訊技術, 2019, 25(2): 57-62.

ZHANG S H, ZUO L. Network intelligence based on artificial intelligence[J]. ZTE Technology Journal, 2019, 25(2): 57-62.

[9]VALADARSKY A, SCHAPIRA M, SHAHAF D, et al. Learning to route[C]//Proceedings of the 16th ACM Workshop. New York: ACM Press, 2017: 185-191

[10]李彥君. 利用機器學習實現快速網絡資源分配的研究[D]. 成都: 電子科技大學, 2016.

LI Y J. Research on fast network resource allocation with machine learning[D]. Chendu: University of Electronic Science and Technology of China, 2016.

[11]XU Z. Experience-driven networking: a deep reinforcement learning based approach[C]//Proceedings of IEEE INFOCOM. Piscataway: IEEE Press, 2018: 1871-1879.

[12]李芃. SDN網絡中基于機器學習的網絡資源分配研究[D]. 南京: 東南大學, 2018.

LI P. Research on network resource allocation based on machine learning in software defined network[D]. Nanjing: Southeast University, 2018.

[13]SUN P H, LI J F, et al. SINET: enabling scalable network routing with deep reinforcement learning on partial nodes[C]//Proceedings of SIGCOMM 2019. [S.l.: s.n.], 2019: 88-89.

Research and application of traffic engineering algorithm based on deep learning

HU Daoyun1, QI Jin1, LU Qianchun1, LI Feng1, FANG Hongqiang2

1. State Key Laboratory of Mobile Network and Mobile Multimedia Technology, Shenzhen 518057, China 2. University of Science and Technology of China, Hefei 230026, China

With the development and application of 5G network, the amount of traffic in network increased rapidly, which caused the lack of bandwidth resource. In order to improve the utilization of network resource and satisfy the critical user requirement for QoS (quality of service), a novel traffic engineering algorithm based on deep learning in SDN was proposed. At last, simulation results show that the proposed algorithm not only can calculate an efficient path for service in real time, but also can improve the QoS and the utilization of network resource, as well as reduce network congestion.

SDN, traffic engineering, deep learning, QoS

TP393

A

10.11959/j.issn.1000?0801.2021027

2020?09?02；

2021?02?01

胡道允（1990? ），男，移動網絡和移動多媒體技術國家重點實驗室工程師，主要研究方向為網絡管控系統、智能網絡算法、智能運維等。

齊進（1971? ），男，博士，移動網絡和移動多媒體技術國家重點實驗室工程師，主要研究方向為網絡控制與管理、大數據分析、智能運維等。

陸錢春（1986? ），女，移動網絡和移動多媒體技術國家重點實驗室工程師，主要研究方向為智能網絡優化。

李鋒（1978? ），男，移動網絡和移動多媒體技術國家重點實驗室工程師，主要研究方向為基于深度學習的控制器策略閉環、控制器自動化能力演進等。

房紅強（1995? ），男，中國科學技術大學碩士生，主要研究方向為光通信網絡和機器學習等。