SDN中基于強化學習的路由算法

摘要：針對傳統網絡路由算法在網絡負載增加、流量變化快速時常常出現效率不高或性能下降的問題，將Q-Learning算法與網絡拓撲（Network Topology）相結合，提出一種基于強化學習的路由算法（NTQ-Learning）并應用于軟件定義網絡（Software Defined Networking，SDN）中。將強化學習算法引入SDN的路由決策過程，通過定義狀態空間、動作空間和獎勵機制，使其在SDN中動態學習并找到最優路由策略，以在不同的網絡負載下最小化網絡延遲，從而提高網絡的整體性能和效率。仿真實驗結果表明，與傳統算法Dijkstra相比，NTQ-Learning算法能夠快速適應流量變化，在網絡負載增大時有效降低時延。

關鍵詞：軟件定義網絡；強化學習；路由決策

中圖分類號：TP393文獻標志碼：A

收稿日期：2024-06-13

基金項目：

教育部產學合作協同育人項目（批準號：220705841293829）資助；山東省高校教改項目重點項目（Z2023238）資助。

通信作者：

云紅艷，女，博士，教授，主要研究方向為計算機網絡、語義web與本體工程、大數據集成應用。E-mail：yunhy2001@163.com

互聯網技術的迅速發展帶來通信需求的不斷增長，面對龐大的網絡服務需求，某些鏈路上的流量超過了其承載能力，導致數據包在傳輸過程中出現延遲增加、丟包增加甚至完全中斷的現象。在網絡中部署智能化的路由算法，選擇最優路徑來傳輸數據，可以有效避免鏈路擁塞。傳統網絡在轉發數據包時主要依靠基于跳數的路由算法^[1]，常用的距離向量路由算法（Distance Vector Routing）和鏈路狀態路由算法（Link State Routing）均為分布式算法^[2]，通過選擇任意兩點之間的最小跳數路徑轉發數據，但在面對復雜網絡拓撲和大規模網絡需求時會出現路由震蕩、計數到無窮等問題，而軟件定義網絡（Software Defined Networking，SDN）的出現有效改善了這一現象。SDN是一種新型網絡架構，核心理念是將網絡的控制平面（control plane）和數據轉發平面（data plane）分離，以實現網絡的集中化管理和編程控制^[3]。在SDN架構中，控制平面負責制定網絡策略和路由規則，數據平面負責實際的數據包轉發。SDN控制器是控制平面的核心，可以與網絡設備通信，并利用開放的API（Application Programming Interface）編程控制這些設備?，F有的SDN控制器多使用簡單的最短路徑算法（如Dijkstra算法）計算網絡路徑^[4]，但已經無法滿足當今復雜網絡環境下的路由需求。近年來，研究表明啟發式算法（如蟻群算法^[5]、遺傳算法^[6]等）在解決路由問題時具有良好的效果，基于強化學習（Reinforcement Learning）的路由算法相較于啟發式算法能夠更好地適應網絡環境的動態變化^[7-9]。強化學習源于對馬爾可夫決策問題的研究，核心思想是通過不斷迭代逐步逼近最優貝爾曼方程的解。路由問題本質就是一個馬爾可夫決策過程，網絡中的節點和鏈接可以被視為狀態空間中的不同狀態，節點之間的通信和鏈接的負載被看作是影響狀態轉移的因素，每個路由決策都會導致網絡狀態的變化，并產生相應的獎勵或成本，因此使用強化學習算法解決路由問題在理論上滿足條件。利用強化學習算法，SDN可以更加智能地進行路由規劃和管理，以適應復雜多變的網絡環境，提高網絡性能和效率。本文旨在探討基于強化學習的路由算法^[10-11]在SDN中路由決策的優勢，將強化學習思想引入路由決策中，將Q-Learning算法與網絡拓撲（Network Topology）相結合，提出NTQ-Learning算法，闡述NTQ-Learning算法的設計與實現，包括狀態空間的定義、獎勵機制的設計以及Q值更新策略等方面。通過仿真實驗驗證不同學習率和折扣因子對NTQ-Learning算法性能和收斂速度的影響，利用不同網絡負載下算法的平均時延分析NTQ-Learning算法和Dijkstra算法的性能。

1 NTQ-Learning算法的設計與實現

1.1 強化學習

強化學習可以描述為智能體（Agent）與環境進行交互的過程，在交互過程中智能體不斷試錯，并從環境中獲得反饋，以便在給定的環境中獲得最大化的累積獎勵^[12-14]。強化學習的目標就是找到一個最優策略π，使得累計獎勵∑^∞k=0γ^kRt+k最大化。最優值函數（Optimal Value Function）和最優動作值函數（Optimal Action-Value Function）是構建最優策略的基礎，分別表示在最優策略下值函數和動作值函數的上確界。值函數V^πs用來估計在給定狀態下，遵循特定策略所能獲得的期望回報，是一種策略的評估，表示在狀態s下，按照策略π進行操作所能得到的未來累積獎勵的期望值

V^πs=Eπ∑^∞k=0γ^kRt+k|St=s（1）

其中，t表示時間步；k表示從起始時間步開始經過的時間步數；Rt+k是在時間t獲得的即時獎勵；γ是折扣因子（0lt;γ≤1），用于調節未來獎勵的當前價值。

對于給定的狀態s，最優值函數V^*s表示在狀態s下，遵循最優策略π^*所能獲得的最大期望回報

V^*s=maxπV^πs（2）

其中，maxπ表示對所有可能策略的最大化。

動作值函數Q^πs，a與值函數類似，即在特定狀態下采取特定行動的期望回報的估計，智能體在每個時間步根據當前狀態s，從動作空間中選擇一個具體的動作a，然后遵循策略π進行后續操作所能得到的未來累積獎勵的期望值，其中，At表示在時間t采取的動作

Q^πs，a=Eπ∑^∞k=0γ^kRt+k|St=s，At=a（3）

對于一個給定的狀態s和動作a，最優動作值函數Q^*s，a表示在狀態s下采取動作a，然后遵循最優策略π^*所能獲得的最大期望回報

Q^*s，a=maxπQ^πs，a（4）

其中，maxπ表示對所有可能策略的最大化。

通過優化這些函數，智能體可以學習如何選擇能夠最大化長期回報的動作。

1.2 NTQ-Learning算法設計

Q-Learning算法是基于值函數的強化學習算法，用于求解序列決策問題。算法的關鍵在于通過不斷交互和學習，智能體能夠自主地發現在給定狀態下應該采取的最佳行動，以獲得最大的長期回報^[15]。本文將強化學習思想引入路由決策中，對Q-Learning算法進行部分改進，與網絡拓撲（Network Topology）緊密結合，提出NTQ-Learning算法。其中狀態集合和動作集合都為網絡拓撲中的交換機，將從源節點到達目的節點的獎勵值設置為10，而沒有到達目的節點的獎勵值設置為0。算法的具體流程為：

Step 1 獲取網絡拓撲信息和鏈路信息，根據獲取到的信息初始化Q表：對于相互連接的交換機之間的鏈路，設Q=1；對于無直接連接的交換機之間的鏈路，設Q=-1；將交換機到自身的Q值設置為0；

Step 2 在每個時間步內，以源節點為初始狀態s，若當前狀態未達到目的節點狀態，重復執行：

（1）使用ε-greedy策略（圖1）在動作集合中選擇一個動作a。ε-greedy策略是一種在強化學習中常用的探索策略，基于參數ε，控制智能體在每個時間步選擇探索動作和利用當前最優動作之間的權衡^[16]，ε-greedy策略通過random.uniform方法生成一個在（0，1）區間內均勻分布的隨機數，當隨機數大于ε時，選取當前狀態下Q值最大的動作作為下一步動作；當隨機數小于或等于ε時，則隨機選取某一動作執行；

（2）智能體執行選擇的動作a，環境返回一個新的狀態s′和獎勵r；

（3）根據s′和r，計算并更新Q值

Qs，a=Qs，a+αr+γmaxa′Qs′，a′-Qs，a

其中，α是學習率，γ是折扣因子，maxa′Qs′，a′為下一狀態的最大估計值，a′是下一狀態最大Q值對應的動作；

（4）智能體轉移到新的狀態s′；

Step 3" 根據訓練好的Q表計算源節點與目的節點的最優路由。

2 仿真實驗及結果分析

2.1 實驗環境

實驗使用虛擬機VMware Workstation 16.2.1，Linux系統及Ubuntu 20.04.6，選用Mininet作為Linux系統的仿真工具，通過Mininet設置包含一組虛擬主機、交換機和鏈路連接的環境，測試過程使用ryu控制器作為網絡的控制平臺，采用Iperf工具模擬和生成網絡中的數據流，以測試和評估NTQ-Learning算法在不同情況下的性能表現，以及不同網絡負載下NTQ-Learning算法和Dijkstra算法的平均時延。

2.2 實驗設置

實驗使用Mininet搭建網絡拓撲（圖2）。拓撲中含10個交換機，分別為dpid：1至dpid：a，每個交換機用唯一標識符dpid標識，以便控制器識別并發送指令或配置信息。交換機之間通過定義set_adjacent（self， s1， s2， port， weight）方法設置端口及連接信息。交換機之間的連接帶寬設定為10Mbit/s，傳播延遲設置為5ms。ryu控制器通過pip install ryu命令安裝在本地主機上，監聽本地主機的6633端口，使用sudo mn--controller=remote，ip=lt;controller_ipgt;，port=lt;controller_portgt;命令啟動搭建好的網絡拓撲并與ryu控制器連接。ryu控制器通過執行nohup command amp; 語句，使命令在后臺運行并將命令的輸出寫入到指定的.log文件中。實驗中，command使用ryu-manager命令運行算法，命令中添加--observe-links參數來獲取實時拓撲信息。

首先調整學習率α和折扣因子γ。更新Q值時，α控制著對新信息的重視程度，如果α過高，算法可能過度關注最新的獎勵，導致收斂速度快但不穩定；如果α過低，算法比較保守，但需要更多的迭代次數才能收斂到最優解。γ決定了在計算未來獎勵時的折現程度，即當前狀態的獎勵會以多大比例影響到下一個狀態的Q值。γ越接近1，越強調長期獎勵；γ越接近0，越強調即時獎勵。α和γ直接影響算法的性能和收斂速度，合理選擇和調整這兩個參數，確定最佳的參數組合，可以使算法更好地適應不同的環境和問題，從而獲得更優的策略。

由于NTQ-Learning算法的主要目標是通過最大化長期獎勵來選擇動作，即更重視長期獎勵，因此γ應選擇較大的值。分別設置γ=0.5和γ=0.9，選擇交換機8到交換機7的路由為測試路線，依次調整α后運行算法，運行結果將輸出到前文提到的.log文件中。根據輸出結果觀察不同學習率下算法獲得穩定的最大累積獎勵所需的迭代次數，確定α和γ的最佳組合。

2.3 實驗結果及分析

實驗結果如圖3所示。當α較小時，算法的學習過程非常緩慢，較少的迭代次數很難達到理想性能。當αgt;0.3時，算法經過一定的迭代次數都能夠獲得最大的累積獎勵，且α越大，算法收斂越快，因為較大的α可以讓算法更快地學習到新策略。

根據實驗結果可知，當α=0.7和α=0.9時，算法幾乎經過同樣的迭代次數獲得最大累積獎勵，但是當α=0.9時，算法的收斂過程中出現較大的震蕩。這是因為過高的學習率使算法過度關注最新獎勵而忽視之前積累的經驗，導致算法對最新獎勵作出過于激進的反應，從而降低算法收斂過程中的穩定性。對比圖3（a）和（b）可知，當α=0.5時，算法在γ=0.9時獲得穩定最大累積獎勵所需的迭代次數是γ=0.5時的2倍多，說明α較高時，γ變大并不會使算法得到更好的收斂性和穩定性。綜上可知，α=0.7，γ=0.5時算法能夠更好地適應環境，且具有較好的收斂性和穩定性。因此，將算法的學習率設置為0.7，折扣因子設置為0.5來進行不同網絡負載下平均時延的對比實驗。

平均時延（Tdelay）是指在網絡通信中，從發送數據到接收數據所需時間的平均值，是衡量網絡性能的重要指標之一，直接影響用戶體驗和系統的效率。在網絡通信中，減小平均時延可以提高數據傳輸速率和響應性，從而改善用戶體驗

Tdelay=1n∑（Tsend+Tspread+Tdeal+Tqueue）

其中，Tsend為發送時延，Tspread為傳播時延，Tdeal為處理時延，Tqueue為排隊時延，n表示數據包個數。

實驗主要針對NTQ-Learning算法和Dijkstra算法進行仿真分析，結果如圖4所示。當網絡負載較小時，兩種算法的平均時延幾乎一致，當網絡負載超過50%，兩種算法的平均時延都隨著網絡負載增加而不斷地升高，但NTQ-Learning算法的平均時延相比于Dijkstra算法始終較低，在網絡負載較大時表現出較好的性能。因為NTQ-Learning算法具有一定的動態適應性，可以根據環境變化進行學習和調整。網絡負載增加時，NTQ-Learning算法通過不斷嘗試和學習逐漸發現更優的路徑選擇策略，從而在高負載時仍能保持較低的平均時延。相比之下，Dijkstra算法是一種靜態算法，在計算最短路徑時只考慮節點之間的距離，不會根據網絡負載的變化進行調整，導致網絡負載增加時平均時延也迅速增加。

3 結論

本文針對傳統路由算法在通信需求增加、網路負載增大時出現效率不高和時延增加的問題，將強化學習思想引入路由決策中，并在SDN中進行NTQ-Learning算法路由決策仿真設計與實現。仿真實驗驗證了NTQ-Learning算法在降低網絡時延、提升路由效率以及適應網絡變化等方面的有效性，在網絡服務需求不斷增大時相比于傳統路由算法具有更好的性能。

參考文獻

[1]朱國暉，牛皎月，王丹妮.SDN網絡中基于深度強化學習的動態路由算法[J].西安郵電大學學報， 2022， 27（6）：1-6.

[2]劉柯池.SDN下基于強化學習的智能路由算法[D].哈爾濱：哈爾濱工業大學，2021.

[3]張皛.軟件定義網絡（SDN）架構下的網絡管理與優化研究[J].現代計算機，2023，29（15）：100-104.

[4]KUMAR D， THAKUR J. Performance analysis of various shortest-path routing algorithms using RYU controller in SDN[J]. International Journal of Wireless and Mobile Computing，2023，25（3）：225-234.

[5]劉振鵬，張慶文，李明，等.基于蟻群優化算法的SDN路由策略[J].昆明理工大學學報（自然科學版）， 2022， 47（3）：60-66.

[6]李姝，馮永新，張文波.遺傳算法與帶權搜索融合的QoS組播路由算法[J].小型微型計算機系統， 2023， 44（12）： 2752-2756.

[7]楊宋亮.SDN架構下智能路由算法研究[D]. 綿陽：西南科技大學，2023.

[8]JUSTUS R， PETER S， HANI S， et al. QR-SDN： Towards reinforcement learning states， actions， and rewards for direct flow routing in software-defined networks[J].IEEE Access，2020， 8： 174773-174791.

[9]李文萌.SDN網絡基于流量分類和強化學習的QoS路由優化算法[D].南京：南京郵電大學，2022.

[10] 李行健.一種面向SDN控制平面的拓撲路由優化算法[J].工業控制計算機，2024，37（1）：69-71.

[11] HASSEN H， MEHERZI S， JEMAA Z B. Improved exploration strategy for Q-Learning based multipath routing in SDN networks[J].Journal of Network and Systems Management，2024，32（2）： 25.

[12] 車向北，康文倩，歐陽宇宏，等.基于強化學習的SDN路由優化算法[J].計算機工程與應用，2021，57（12）：93-98.

[13] 王月娟，張蘇寧，吳水明，等.基于秩的Q-路由選擇算法[J].計算機與現代化，2018（10）：1-5.

[14] 宋麗君，周紫瑜，李云龍，等.改進Q-Learning的路徑規劃算法研究[J].小型微型計算機系統， 2024， 45（4）： 823-829.

[15] 陳必康.基于OpenFlow協議的SDN路由算法的研究與實現[D].南京：南京郵電大學，2020.

[16] 孔凌輝，饒哲恒，徐彥彥，等.基于深度強化學習的無線網絡智能路由算法[J].計算機工程，2023，49（9）：199-207.

Routing Algorithm Based on Reinforcement Learning in SDN

LIU Tian-tian^1，2，YUN Hong-yan¹，SHAN Kai¹

（1.College of Computer Science amp; Technology， Qingdao University， Qingdao 266071， China;

2.Qingdao Institute for Food and Drug Control， Qingdao 266071， China）

Abstract： Traditional routing algorithms often have low efficiency or performance degradation when faced with challenges such as increasing network load and rapid traffic changes. It was combined Q-Learning with Network Topology to propose a reinforcement learning-based routing algorithm called NTQ-Learning， which was applied in Software Defined Networking（SDN）. Reinforcement learning algorithm was introduced into the routing decision-making process of SDN. By defining state space， action space and reward mechanism， reinforcement learning algorithm can dynamically learn and find the optimal routing strategy in SDN to minimize network delay under different network loads， thus improving the overall performance and efficiency of the network. Simulation results show that compared with Dijkstra algorithm， NTQ-Learning algorithm can quickly adapt to traffic changes and effectively reduce the delay when the network load increases.

Keywords： software defined networking; reinforcement learning; routing decision