SDN環境下基于QLearning算法的業務劃分路由選路機制

金子晉，蘭巨龍，江逸茗，孫鵬浩，魏鵬

?

SDN環境下基于QLearning算法的業務劃分路由選路機制

金子晉，蘭巨龍，江逸茗，孫鵬浩，魏鵬

（國家數字交換系統工程技術研究中心，河南 鄭州 450002）

隨著當前網絡的多元化發展，用戶對于網絡的需求也不斷增加，網絡的承載性受到極大挑戰。在軟件定義網絡環境下，提出一種以業務屬性為依據、基于QLearning算法的路由選路機制，設計了鏈路發現、鏈路分類、強化學習訓練及值表下發4個模塊，根據網絡的實施情況對不同屬性的業務流分配不同的路徑以保障用戶路由的QoS。實驗結果表明，所提算法可使數據流的總體分組丟失率低于5%，對于部分屬性的業務流可接近0分組丟失，同時對于時延也有大幅降低。

SDN；QLearning算法；業務屬性分類；多路徑路由

1 引言

根據中國互聯網絡信息中心（CNNIC，China Internet Network Information Center）發布的第41次《中國互聯網絡發展狀況統計報告》，截至2017年12月，中國互聯網用戶數量達7.72億，普及率達55.8%[1]。隨著互聯網技術及各種新興技術的不斷發展進步，用戶的需求也從單一的數據傳輸轉變為數據、視頻、交互及時事多媒體等多樣化的網絡應用，以微博、抖音、快手、網盤、視頻網站等為代表的新型流媒體業務的興起，也進一步加劇了網絡需求的多樣化，對網絡的承載性提出了極大的挑戰。而傳統的IP網絡架構設備底層具有封閉性，策略部署十分困難，其安全性和靈活性也有不足，因此，斯坦福大學的McKeown[2]提出了軟件定義網絡（SDN，software defined networking）的新型架構。

SDN是一種控制平面與轉發平面獨立的網絡，具有控制跟轉發分離、有開放的編程接口、集中式的控制等特點。在傳統的網絡中，交換機/路由器通過自學習維持著在SDN環境下的路由表，交換機根據流表進行路由轉發。當前SDN網絡中，基于流量的路由算法大多仍采用以跳數為度量的最短路徑算法得到最優路徑。然而，這種算法并未考慮到時延、帶寬及資源利用率等方面的因素，所選取的鏈路不一定是最優路徑，而且可能存在某一鏈路被多條業務流選取為最優路徑的情況，造成鏈路擁塞和資源浪費。

一直以來，路由的服務質量（QoS，quality of service）問題都是學術界的研究熱點，在傳統網絡架構中，就有很多方法來保障用戶的QoS。例如，Best Effort模型（即盡力而為模型）[3]是一個單一的服務模型，網絡采用先入先出的調度原則，盡最大的可能性發送報文，但對時延、可靠性等性能不提供任何保證。綜合服務模型[4]將業務定義為有保證的業務、控制負載的業務、盡力而為的業務，在發送方和接收方之間使用RSVP（資源預留協議）作為每個數據流的信令，從接收方到發送方之間沿途的每一個網絡單元都要支持QoS控制機制，為每一個要求QoS的數據流預留資源。

學術界和產業界對在SDN環境中的路由策略做了大量的研究。在減少資源浪費方面，田銘等[5]提出了一種基于鏈路繁忙趨勢值的等價多路徑選擇算法，通過鏈路在網絡中的路徑趨勢值表征鏈路的可能任務量，鏈路帶寬表征鏈路的傳輸能力，通過計算鏈路的繁忙趨勢值，從而在等價多路徑中選擇瓶頸鏈路繁忙趨勢值最小的路徑，實現流量盡量避免在網絡的熱點鏈路上傳輸，有效避免了擁塞，增大了吞吐量，提高了資源利用率，該方法對資源的利用率有較好的提升，但是未能考慮到流量特性的差異，對最優方案的選擇有所影響；孔祥彬等[6]在研究中以代寬為度量參數，將業務流提出的帶寬約束要求轉換成鏈路代價，使用基于Dijkstra算法的QoS路由算法為業務流選擇滿足帶寬約束的QoS路由，一定程度上提高了檢測的收斂速度，有利于根據信任度的變化進行模型的調整和重構，具有效率高、速度快的特點，但是考慮因素仍然有些單一，不夠全面。

在解決時延問題方面，王紅川等[7]的研究引入了“虛擬時延”的概念，提出了VL-EDF（virtual latency earliest deadline first algorithm）隊列調度算法，對不同的數據分組賦予不同的“虛擬時延”值，結合數據分組的到達時間和截止時間動態調整傳輸的次序，該方法可以很好地處理對時延要求高的數據分組，但是未能考慮其他相關影響因素；YAN等[8]提出了HiQoS的概念，利用源到目的節點的多條路徑，并使用排隊機制為不同業務的傳輸帶寬提供保障，同時，作者還提出了一種故障檢測策略，每隔一段時間對鏈路的狀態進行更新，當發生故障時可以對數據分組進行重路由，該方法可以有效減小時延且路由具有一定的頑健性，但是單路徑傳輸使資源沒有得到充分利用且并未照顧到所有因素。

在滿足用戶個性化定制方面，Seddiki等[9-10]提出了一種家用FlowQoS體系結構，通過應用程序標識并使用流表規則在家庭路由器上以適當的速率轉發流量，FlowQoS控制器對上下行流量進行標識和QoS配置，并對用戶指定的應用流進行優先轉發，以適應用戶的個人喜好，該方法可以滿足用戶對應用的優先級需求，提升流量的轉發速率，然而并沒有考慮到數據分組丟失率等因素。

上述論文都從某一個方面解決了路由服務質量的問題，但并未統籌考慮。本文基于現有的研究成果，提出一種以業務分類為依據的路由選路算法，將業務流按屬性分類，結合鏈路的時延、帶寬及分組丟失率等因素建立權值公式，運用機器學習算法進行動態優化，從而選擇合適的路徑進行路由。

2 業務屬性相關的多路徑傳輸機制的設計與實現

為了實現在SDN環境下以業務分類為依據的路由選路算法，本文提出以下路徑規劃系統，如圖1所示，主要包含鏈路發現、鏈路分類、強化學習訓練及值表下發4個模塊，而所用拓撲如圖2所示，由7臺交換機及12臺主機構成。

圖1 路徑規劃系統架構

圖2 實驗拓撲

圖3 流表分組頭域

圖4 QLearning流程

2.1 業務的劃分

隨著網絡技術的不斷發展，網絡業務種類也不斷增加，不同的數據分組種類對QoS的需求也有所不同。根據3GPP對網絡業務的劃分[11]，把網絡流量劃分為會話類業務、流媒體業務、交互類業務、數據類業務4種。

會話類業務：是一種單向傳輸，不需要進行交互的實時類業務，如視頻通話等，對時延有較高的要求而可以承受一定的分組丟失率。

流媒體業務：是一種單方面的實時業務，如視頻點播、電子商務等，對時延和分組丟失率的要求相對較高。

交互類業務：是一種終端用戶（人或機器）和遠程設備（如遠程服務器）進行在線數據交互的業務，為請求響應模式，具有非實時性，如Web瀏覽、網絡游戲等，對時延和分組丟失率均有一定的要求。

數據類業務：非實時類業務，如后臺的E-mail接收、文件下載等，對分組丟失率有較高要求，對時延要求較低。

在本文中，采用分組頭域中的ToS域進行數據分組業務類型區分，在OpenFlow V1.0中，流表的分組頭域中包括12個元組（Tuple），相關內容如圖3所示[12]。

2.2 基于QLearning算法規劃路由

2.3 鏈路信息采集及處理

根據不同屬性業務對各參數要求各不相同的特性，所用權重關系如表1所示。

表1 權重關系

為了獲取鏈路中各項數據信息，本文采用Iperf[14]工具監測鏈路中各項數據。同時，為了對數據進行統一考量，采用min-max標準法[15]對各項數據進行歸一化處理，使其統一映射到[0,1]區間內，計算方法如下。

3 實驗與結果分析

3.1 實驗仿真

本文的實驗環境為Windows7操作系統，CPU型號為Core i7-4710HQ，主頻2.50 GHz，采用mininet[16]工具對底層網絡進行搭建（場景如圖2所示），對4種業務流值指定如表2所示，而相應的參數賦值如表3所示。

表2 業務流ToS值

表3 參數賦值

在Iperf工具中指定階梯帶寬以測試當前鏈路的最大可用帶寬，由圖5可知，當主機終端設置發送帶寬為72 Mbit/s時，分組丟失率為0，當發送帶寬增加到150 Mbit/s時，已出現分組丟失現象，分組丟失率為0.74%，隨著發送帶寬的增加，分組丟失率也在增加，顯示的帶寬基本穩定在100 Mbit/s，即可知鏈路的最大可用帶寬為100 Mbit/s。

圖5 Iperf服務器接收不同發送帶寬結果示意

同時，在不同周期下，QLearning算法路由選擇的準確率如表4所示，從表中可以看出，隨著訓練周期的增加，準確率不斷逼近100%，在本文拓撲中，當訓練周期到達40時，基本收斂。

表4 路由選擇準確率

3.2 實驗結果對比

本文綜合時延、鏈路可用帶寬、分組丟失率、帶寬利用率等因素，以業務屬性為依據規劃路由路徑。將本文所得實驗結果與ECMP（equal-cost multipath routing）算法[17]及文獻[18]的蟻群算法進行了對比，經過多次實驗，可得各路由算法對4種業務的時延及分組丟失率如圖6和圖7所示（從左至右分別為會話類業務、流媒體業務、交互類業務及數據類業務）。

圖6 各算法時延對比

圖7 各算法分組丟失率對比

從圖6和圖7可以看出，本文算法能為4種不同屬性業務保障分組丟失率且有效降低時延，所得結果明顯優于現有算法，在會話類業務和數據類業務方面提升尤為明顯。

4 結束語

本文提出了一種基于機器學習QLearning算法、以業務流屬性劃分的路由QoS保障機制，結合底層網絡實際情況、鏈路及業務自身屬性等多個方面因素，對網絡資源利用率進行合理分配，避免局部擁塞狀況，同時盡可能地滿足用戶QoS需求。當然，本文算法還具有一定的局限性，下一步，將引入更深層次的機器學習算法（如Double Deep QLearning等）進行模型的訓練。同時，本文算法基于固定拓撲，而網絡拓撲往往是動態變化的，在這方面仍有不足之處，以待后續研究。

[1] LI J. 41th China Internet development statistics report[J].China Radio,2018(3):96-96.

[2] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM Sigcomm Computer Communication Review, 2008, 38(2):69-74.

[3] 張鵬飛, 黃生葉, 趙海琳. 寬帶綜合業務網絡中盡力而為業務性能研究[J]. 計算機工程, 2007, 35(9):126-127.

ZHANG P F, HUANG S Y, ZHAO H L.Study on queueing system performance of best effort service in broad band Integrated service network[J].Computer Engineering, 2007, 35(9):126-127.

[4] 向渝, 雷維禮, 黃順吉. IP QoS綜合服務模型研究[J]. 電訊技術, 2001, 41(3):106-110.

XIANG Y, LEI W L, HUANG S J.Research on IP QoS intserv model[J].Telecommunication Engineering,2001, 41(3):106-110.

[5] 田銘, 蘭巨龍, 朱宣勇. 一種基于鏈路繁忙趨勢值的等價多路徑選擇算法[J]. 信息工程大學學報, 2010, 11(2):190-195.

TIAN M, LAN J L, ZHU X Y. An equivalent multi path selection algorithm based on link busy trend value [J]. Journal of Information Engineering University, 2010, 11(2):190-195.

[6] 孔祥彬, 沈蘇彬, 李莉. 一種基于SDN網絡的QoS路由選擇方案[J]. 計算機技術與發展, 2018(2):102-106.

KONG X B, SHEN S B, LI L. A QoS routing scheme based on software－defined networking[J]. Computer Technology and Development, 2018(2):102-106.

[7] 王紅川. 智能電網通信網中數據傳輸時延問題的研究[D]. 上海:上海交通大學, 2014.

WANG H C. Research on the data transmission delay in the smart grid communication networks[D]. Shanghai: Shanghai Jiaotong University, 2014.

[8] YAN J Y, ZHANG H L, SHUAI Q J. HiQoS: an SDN-based multipath QoS solution[J]. China Communication 2015, 12(5):123-133.

[9] SEDDIKI M S, SHAHBAZ M, DONOVAN S, et al. FlowQoS: QoS for the rest of us[C]//The Workshop on Hot Topics in Software Defined Networking. 2014:207-208.

[10] SEDDIKI M S, SHAHBAZ M, DONOVAN S, et al. FlowQoS: per-flow quality of service for broadband access networks[J]. 2015.

[11] Quality of service (QoS) concept and architecture[J]. 2005.

[12] 雷葆華, 王峰, 王莤. SDN核心技術剖析和實戰指南[J]. 中國科技信息, 2013(21):52-52.

LEI B H, WANG F, WANG J. SDN core technology analysis and practical guide [J]. China Science and technology information, 2013(21): 52-52.

[13] LI J, WANG J. Control device and system and transmission channel control method in software-defined networking: WO/2015/ 192306[P]. 2015.

[14] TIRUMALA A, QIN F, DUGAN J, et al. Iperf1.7.0–the TCP/UDP bandwidth measurement tool[EB/OL]. http://dast.nlanr.net/Projects/ Iperf. 2007.

[15] JAIN K Y, BHANDARE K S. Min max normalization based data perturbation method for privacy protection[J]. International Journal of Computer and Communication Technology, 2011, 2,(8): 45-50.

[16] KAUR K, SINGH J, GHUMMAN N S. Mininet as software defined networking testing Platform[C]//International Conference on Communiction, Computing & Systems. 2014.

[17] 董青. 增強型網絡路由策略研究[D]. 成都: 電子科技大學, 2013.

DONG Q. Enhanced network routing strategy research[D]. Chengdu: University of Electronic Science and Technology, 2013.

[18] 余翔, 易明敏, 楊路. 一種SDN架構下業務屬性相關的多徑路由算法[J]. 電信科學, 2016, 32(11):10-15.

YU X, YI M, YANG L. A multi-path routing algorithm based on business attributes under SDN architecture [J]. Telecommunication Science, 2016, 32(11):10-15.

QLearning based business differentiating routing mechanism in SDN architecture

JIN Zijin, LAN Julong, JIANG Yiming, SUN Penghao, WEI Peng

National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China

With the diversified development of the current network, users’ demand grows as well which brings great challenge for its load ability. A QLearning based business differentiating routing mechanism in SDN architecture was proposed to guarantee users’ routing QoS. To do that, four modules (discovery of link, classification of link, intensive learning and-value table sending) were designed to assign different paths to data streams of different attributes. The experiment shows that the proposed algorithm can decrease the packet loss rate to less than 5% and for some of the data streams, this rate is almost 0, simultaneously, it also helps the delay problem.

SDN, QLearning algorithm, business differentiating, multipath routing

TP391

A

10.11959/j.issn.2096-109x.2018073

金子晉（1992-），女，浙江三門人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為新一代信息網絡體系結構下路由相關技術。

蘭巨龍（1962-），男，河北張北人，國家數字交換系統工程技術研究中心教授、博士生導師，主要研究方向為新一代信息網絡關鍵理論與技術。

江逸茗（1984-），男，江蘇南通人，國家數字交換系統工程技術研究中心講師，主要研究方向為網絡虛擬化、網絡架構。

孫鵬浩（1992-），男，山東青島人，國家數字交換系統工程技術研究中心博士生，主要研究方向為可編程網絡、數字交換技術。

魏鵬（1994-），男，湖南衡陽人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為新一代信息網絡體系結構。

2018-06-25；

2018-08-15

金子晉，2738808824@qq.com

國家自然科學基金資助項目（No.61502530）

The National Natural Science Foundation of China (No.61502530)