一種基于深度強(qiáng)化學(xué)習(xí)的SDN路由算法

丁懷寶

摘 ?要： 為解決軟件定義網(wǎng)絡(luò)（SDN）中的流量工程（TE）問題，提出了一種深度強(qiáng)化學(xué)習(xí)路由（DRL-Routing）算法.該算法使用較全面的網(wǎng)絡(luò)信息來表示狀態(tài)，并使用一對多的網(wǎng)絡(luò)配置來進(jìn)行路由選擇，獎勵函數(shù)可以調(diào)整往返路徑的網(wǎng)絡(luò)吞吐量. 仿真結(jié)果表明，DRL-Routing可以獲得更高的獎勵，并且經(jīng)過適當(dāng)?shù)挠?xùn)練后，能使各交換機(jī)之間獲得更優(yōu)的路由策略，從而增大了網(wǎng)絡(luò)吞吐量，降低了網(wǎng)絡(luò)延遲和數(shù)據(jù)丟包率.

關(guān)鍵詞： 軟件定義網(wǎng)絡(luò)（SDN）; 流量工程（TE）; 獎勵函數(shù); 深度強(qiáng)化學(xué)習(xí)路由（DRL-Routing）

中圖分類號： ?TP 312 ??????文獻(xiàn)標(biāo)志碼： A ?????文章編號： 1000-5137（2021）01-0128-05

Abstract： In this paper，a deep reinforcement learning routing （DRL-Routing） algorithm was proposed to solve the traffic engineering （TE） problem in software defined networking （SDN）. The algorithm proposed made use of more comprehensive network information to represent the state，and adopted one-to-many network configuration for routing selection. Besides，the reward function was able to adjust the network traffic of the round-trip path. The simulation results showed that DRL-Routing could obtain higher rewards. After proper training，the agent could learn a more excellent routing strategy between the switches，which increased network traffic and reduced network delay and data packet loss rate.

Key words： software defined network（SDN）; traffic engineering（TE）; reward function; deep reinforcement learning routing（DRL-routing）

0 ?引言

隨著Internet的不斷發(fā)展，網(wǎng)絡(luò)中的數(shù)據(jù)流量日益激增.盡管通過增加鏈路帶寬和提高交換設(shè)備處理速度，可以暫時(shí)緩解網(wǎng)絡(luò)流量增長的壓力，但是這些并不能從根本上解決流量工程（TE）[1]中的吞吐量和延遲等方面問題.

傳統(tǒng)路由配置中經(jīng)常采用OSPF[2]（Open Shortest Path First，開放式最短路徑優(yōu)先）算法和LL[3]（Least Loaded，最小負(fù)載）路由算法，但這些算法無法滿足如今越來越復(fù)雜和動態(tài)的網(wǎng)絡(luò)，無法在具有動態(tài)流量分布的網(wǎng)絡(luò)中找到最佳路由路徑.

軟件定義網(wǎng)絡(luò)（SDN）[4]架構(gòu)在數(shù)據(jù)收集、資源管理和路由優(yōu)化等方面提供了許多新的解決方案.SDN控制器對整個網(wǎng)絡(luò)進(jìn)行集中控制，網(wǎng)絡(luò)管理員可以根據(jù)自主定義的路由規(guī)則控制網(wǎng)絡(luò)的轉(zhuǎn)發(fā)流量，充當(dāng)網(wǎng)絡(luò)操作系統(tǒng)的角色.

本文作者提出一種深度強(qiáng)化學(xué)習(xí)路由（DRL-Routing）算法，以解決SDN的吞吐量和延遲等方面的問題.該方法可以調(diào)整從優(yōu)化路徑往返雙向網(wǎng)絡(luò)的吞吐量，有效減少網(wǎng)絡(luò)擁塞的情況.

1 ?強(qiáng)化學(xué)習(xí)

圖1是強(qiáng)化學(xué)習(xí)[5]的基本模型.該模型中，只有兩個實(shí)體，即智能體（Agent）和環(huán)境（Environment）.智能體在當(dāng)前環(huán)境狀態(tài)St執(zhí)行一個動作At，環(huán)境從狀態(tài)St轉(zhuǎn)變到狀態(tài)St+1，同時(shí)環(huán)境針對當(dāng)前動作給出一個動作獎勵Rt+1，智能體使用狀態(tài)St+1和當(dāng)前獎勵Rt+1計(jì)算下一個動作At+1，然后算法如此循環(huán)，最終的目的是在整個決策流程中獲得最大的獎勵.

交互元組表示智能體在狀態(tài)St執(zhí)行At，到狀態(tài)St+1時(shí)，針對動作At給出動作獎勵Rt+1，如此循環(huán)，直至獲得最大數(shù)目的獎勵.

2 ?DRL-Routing概述

2.1 總體架構(gòu)

DRL-Routing嵌入到典型的SDN架構(gòu)中，該架構(gòu)的應(yīng)用層中包含：OpenFlow網(wǎng)絡(luò)發(fā)現(xiàn)應(yīng)用程序和 DRL-Routing應(yīng)用程序.OpenFlow網(wǎng)絡(luò)發(fā)現(xiàn)應(yīng)用程序使用鏈路層發(fā)現(xiàn)協(xié)議（LLDP）[6]發(fā)現(xiàn)網(wǎng)絡(luò)的數(shù)據(jù)平面拓?fù)浣Y(jié)構(gòu).DRL-Routing應(yīng)用程序包含兩個主要功能模塊.

1） 網(wǎng)絡(luò)監(jiān)控模塊（NMM）.該模塊可以獲取網(wǎng)絡(luò)中的信息，包括：鏈路延遲、吞吐量、端口速度等，利用這些信息標(biāo)識網(wǎng)絡(luò)狀態(tài)并計(jì)算獎勵.大部分網(wǎng)絡(luò)信息由控制器檢索得到.

2） 動作轉(zhuǎn)換器模塊（ATM）.該模塊將智能體選擇的動作轉(zhuǎn)換為一組OpenFlow消息，以更新交換機(jī)的流表.在請求更新路徑時(shí)，由路徑上最后一臺交換機(jī)將OpenFlow消息發(fā)送到第一臺交換機(jī)，刪除舊路徑在交換機(jī)中的相應(yīng)規(guī)則.

2.2 參數(shù)描述

DRL-Routing模型中的緩存中的元組表達(dá)式為M=，其中：S是狀態(tài)集，集合了第t個時(shí)間段（Δt）內(nèi)所有網(wǎng)絡(luò)信息;A是動作集;R是獎勵函數(shù);T是動作轉(zhuǎn)換概率;γ∈[0，1]是衰減因子.

4 ?實(shí)驗(yàn)分析

4.1 仿真環(huán)境

使用Mininet[8]平臺建立包含一組虛擬主機(jī)、交換機(jī)和鏈接的環(huán)境，使用Ryu[9]作為OpenFlow控制器來管理網(wǎng)絡(luò)，并使用Iperf[10]生成流量，檢測DRL-Routing路由算法在Fat-tree，NSFNet和ARPANet三種網(wǎng)絡(luò)拓?fù)渖系男阅?

4.2 算法執(zhí)行

通過調(diào)用PDA函數(shù)對智能體進(jìn)行訓(xùn)練，以經(jīng)驗(yàn)驅(qū)動的方式嘗試不同的取值，優(yōu)化往返雙向的網(wǎng)絡(luò)吞吐量，當(dāng)=1 s時(shí)，DRL-Routing算法在所有度量方面提供了最好的性能.經(jīng)過訓(xùn)練之后的智能體已學(xué)習(xí)了路由知識，可以用于具體網(wǎng)絡(luò)拓?fù)涞膶?shí)施.

4.3 實(shí)驗(yàn)結(jié)果

將DRL-Routing算法與傳統(tǒng)的開放式最短路徑優(yōu)先（OSPF）算法、最小負(fù)載（LL）路由算法進(jìn)行了比較，如表1所示.由表1可知：

1） DRL-Routing算法獲得的獎勵更高.例如，在ARPANet拓?fù)渖?，采用DRL-Routing算法獲得的獎勵之和為80.37，而采用OSPF和LL算法獲得的獎勵之和分別為45.02和31.50.

2） 在三種拓?fù)浣Y(jié)構(gòu)上，DRL-Routing算法的文件傳輸時(shí)間相對較少.例如，在NSFNet拓?fù)渖?，采用DRL-Routing算法，40 GB的文件平均傳輸時(shí)間為22.68 s，而OSPF和LL算法的文件傳輸時(shí)間分別為56.70 s和48.00 s，這是因?yàn)镺SPF和LL算法都基于貪婪方法，不適用于流量不斷變化的網(wǎng)絡(luò).

3） DRL-Routing算法在所有網(wǎng)絡(luò)拓?fù)渲芯@得了較高的利用率.例如，在NSFNet上，采用DRL-Routing算法，平均利用率為0.44，而采用OSPF和LL算法，平均利用率分別為0.23和0.27.

5 ?結(jié)論

本文作者介紹了DRL-Routing算法的相關(guān)理論與運(yùn)行機(jī)制，并將其運(yùn)用于Fat-tree，NSFNet和ARPANet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中.實(shí)驗(yàn)表明：DRL-Routing算法在三種常用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上均獲得了較高的獎勵;可以較大程度地縮短文件的傳輸時(shí)間，顯著改善用戶體驗(yàn);減少網(wǎng)絡(luò)中被重傳的數(shù)據(jù)包數(shù)量，大大減少擁塞路徑的出現(xiàn).

參考文獻(xiàn)：

[1] AGARWAL S，KODIALAM M，LAKSHMAN T V.Traffic engineering in software defined networks [C]//IEEE INFOCOM.Turin：IEEE，2013：2211-2219.

[2] 張春青，張宏科.OSPF動態(tài)路由協(xié)議中的路由計(jì)算 [J].北方交通大學(xué)學(xué)報(bào)，2003（3）：100-103.

ZHANG C Q，ZHANG H K.Routing calculation of OSPF dynamic routing protocol[J].Journal of Northern Jiaotong University，2003（3）：100-103.

[3] LI L，SOMANI A K.Dynamic wavelength routing using congestion and neighborhood information [J].IEEE/ACM Transactions on Networking，1999，7（5）：779-786.

[4] ZUO Q Y，CHEN M，ZHAO G S，et al.Research on OpenFlow-based SDN technologies [J].Journal of Software，2013，24（5）：1078-1097.

[5] SUTTON R S，BARTO A G.Reinforcement learning：an introduction [J].IEEE Transactions on Neural Networks，1998，9（5）：1054.

[6] 曾干.基于鏈路層發(fā)現(xiàn)協(xié)議（LLDP）的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn) [J].電腦知識與技術(shù)，2006（20）：45-46，48.

ZENG G.The physical network topology discovery based on LLDP protocol [J].Computer Knowledge and Technology，2006（20）：45-46，48.

[7] WANG Z，F(xiàn)REITAS N D，LANCTOT M.Dueling network architectures for deep reinforcement learning [C]//Proceedings of the 33rd International Conference on Machine Learning.New York：ACM，2016：1995-2003.

[8] 楊俊東，尹強(qiáng)，張碩.基于Mininet的SDN仿真與性能分析 [J].信息通信，2017（3）：189-191.

YANG J D，YIN Q，ZHANG S.Simulation and performance analysis of SDN based on Mininet [J].Information & Communications，2017（3）：189-191.

[9] ISLAM M T，ISLAM N，REFAT M A.Node to node performance evaluation through RYU SDN controller [J].Wireless Personal Communications，2020，112（1）：1-16.

[10] ASADOLLAHI S，GOSWAMI B.Experimenting with scalability of floodlight controller in software defined networks[C]// International Conference on Electrical，Electronics，Communication，Computer，and Optimization Techniques.Mysuru：IEEE，2017：288-292.

（責(zé)任編輯：包震宇）