強化學習云計算數據中心網絡的智能路由策略

劉景林，郝嘉鈺

（1.泉州經貿職業技術學院 信息技術系，福建 泉州 362000；2.泉州華光職業學院 公共基礎部，福建 泉州 362000）

近年來，隨著電子商務、車聯網與衛星網絡等新興網絡業務的快速發展，全球信息量迅速增加，有傳輸優勢的云計算數據中心網絡也發展迅速，規模不斷擴大，部署種類日漸增多，而其核心技術在高并發下的路徑選擇及路由轉發造成的負載不均衡，已成為制約云計算數據中心網絡運行的首要因素[1].因此，研究更適合云計算數據中心網絡大規模訪問下的智能路由算法很有必要.云計算數據中心網絡主要有服務器、應用軟件、交換機等組網通信，其中路由在整個通信過程中起關鍵作用.路由由多條被選擇的路徑組成，當前絕大部分路由模式是實現服務器間的網絡互通，在一般的訪問規模下，云計算數據中心只需要提供最短路徑的路由方案即可.最短路徑路由指被選擇路徑數量最少的路由方案，適用于整體傳輸性能較好的情況，并非所有情況下都是最優路由方案[2].當存在大規模訪問云應用時（如電子商務中的秒殺業務、衛星網絡中的高并發海量數據下載），會出現最優路由選擇難造成的系統負載不均衡問題.

周學兵等[3]針對數據中心網絡中大規模訪問時能耗過高展開研究，將減少電力消耗作為優化目標，并指出這是一個NP 難題，提出了可提前預測能量消耗的路由算法，此算法以交換機上最短路徑為比較對象，按用戶訪問的路由可能路徑為對比對象，用遍歷所有可能路由路徑的方法找出最優路由方案，但此方案只能在減少能量消耗上占優勢，并未討論資源加載是否過載、大規模訪問等影響負載不均衡的其他關鍵因素，也無法實現人工智能路由.與此同時，路由算法的優劣也可通過路徑是否擁塞進行評價，也有學者針對大規模訪問時，能否影響網絡傳輸、網絡是否擁塞等展開研究.原迪等[4]從大規模訪問時對交換機的影響入手，重點分析了訪問數據流中存在大流、小流，而小流即時性強，大流傳輸時間長，建立適應多流傳輸路由模型，可以為小流建立冗余路徑，以保證大流、小流的高效傳輸，此方法保障了數據流的按時到達，減少了網絡擁塞，但加劇了某一條路徑的負擔，仍可造成負載不均衡.也有學者用多目標優化QoS方法提高系統負載均衡，如段晨等[5]提出衛星網絡中高負載多QoS目標優化算法，但只適用于動態時變衛星網絡，并不適用于云計算數據中心網絡.鐘思等[6]針對數據中心網絡中視頻流直播導致的負載不均衡影響傳輸問題，利用神經網絡感知主機負載狀態與網絡實時負載情況，分析了高負載下的路由特點，并提出基于深度強化學習的避免擁塞算法，證明了人工智能算法在此方面的優勢，但此方案只適用多即時強的直播流，未全面考慮所有的傳輸數據流，也不適合應用于云計算數據中心網絡.

文中對云計算數據中心網絡路由的關鍵技術進行分析，提出人工智能強化學習的智能路由策略，以整個網絡用戶吞吐量最大化與數據中心網絡傳輸成本最小化為優化目標，設計實時最優智能路由方案.

1 云計算數據中心網絡常用路由算法

當前，云計算數據中心網絡常用的路由算法主要有以下幾種.

1）迪杰斯特拉（Dijkstra）算法.該算法是數據中心網絡中常用的路由算法，通過存儲所有頂點計算邊值，當再次使用時直接查詢即可，需要維護最短路徑表，當訪問規模較大時，從路徑表中查找效率低，無法較好實現負載均衡.

2）等價路由算法（equal-cost multipath path,ECMP）.該算法存儲所有dest IP 及相同cost值的路徑，當再次使用時直接查詢，優點是易部署、負載較其他算法均衡，缺點是所有路由等份分配，無法滿足即時性要求高的業務.

3）K最短路徑算法（K-shortest path,KSP）.該算法是Dijkstra 算法的擴展，排除相交路徑及可能形成回路的路徑，同樣需要維護最短路徑表，對硬件的要求高，不易部署，不易實現負載均衡.

4）動態調度負載均衡算法（dynamic scheduling load balancing,DSLB）.該算法原理是貪心地查找最大可用帶寬，與輪詢路由類似，保障帶寬最大的情況下輪詢使用可用路徑，但沒有對時延、可用帶寬等其他性能指標的判斷，有局限性.

除此之外，也有其他學者開展云計算數據中心網絡路由研究，云計算數據中心網絡的路由實現方法有很多，文中主要討論大規模訪問下可保障系統負載均衡的路由解決方案.當大規模訪問云計算數據中心網絡時，為防止負載不均衡，需要整體考慮所有關鍵因素，而人工智能強化學習算法在此方面有較大優勢.

2 強化學習Q-learning算法及其應用

2.1 強化學習Q-learning算法

Q-learning 算法原理是與現實環境不斷迭代并計算Q-value 表的值，收斂后取得最優解，推算得出結論.目前該算法已廣泛應用于國際象棋、自動駕駛、交互博弈等場景，其實現過程如圖1.

算法由4 部分組成.S為環境狀態集合，A是對應S下的每個狀態中可能的動作集合.設在狀態s中采取一個行動a，則新狀態s'的概率是P(s'|s,a)，并設此次采取行動所獲取的獎勵（當獎勵為負值時，表明動作不利于向好的結果發展）是R(s,a,s')，以上組成Q-learning 算法模型的四元組即為(S,A,P,R)，整個算法的求解過程就是找到最優策略π:S->A.為使結論盡可能接近真實值，引入折扣率γ，其中γ∈[0,1]，當γ≈1 時，表示注重長期回報，也可理解成采用Q-learning 結論的概率大；當γ≈0 時，表示注重短期回報，即不采用Q-learning 的結論.

強化學習中的模型很多，比如：Q-learning、確定性策略算法等，基本思想皆是馬爾可夫決策過程（markov decision process,MDP）.文中選用易部署、決策快的Q-learning算法，實現過程見表1.

首先創建一個二維表格，然后不斷循環遍歷所有目標，第06行是獎勵函數，第07～08行是存入二維表格，智能體不斷探索，當到達目標后，便會繼續下一次探索，達到收斂并輸出最終動作為止.強化學習可以解決網絡中的實際問題，在多個研究方向有優勢，已被廣泛應用.王艷芳等[7]針對低軌衛星網絡在高并發負載下路徑選擇難問題，提出強化學習所有傳輸成本并迭代選擇最優解的人工智能路由算法，比傳統路由算法有很大的優勢.陳前斌等[8]利用強化學習解決高負載條件下無線網絡資源分配問題，可以明顯降低時延、能耗.

2.2 強化學習求解多目標優化

使用人工智能強化學習求解有很多優點，例如傳統NP問題有很大求解難度，不易建模，或建模不能完全覆蓋整體問題本等，而強化學習的本質是智能體與環境的不斷迭代，并不斷調整原始值，類似“進化”的過程，整個過程是尋找最佳策略的過程，因此較傳統求解機制有明顯的優勢[9].文中高負載下影響網絡智能路由的因素有很多且具有不確定性，因此相對于使用傳統方式求解，應用強化學習方法求解更優.此外，強化學習求解還在以下幾個方面占有優勢.

1）有較高的泛化能力.指機器學習算法學習能力，從已知（已有）的算法中泛化出新的算法，可替代人的算法學習能力，以實現無人值守、自動完成的功能[10].

2）解決問題高效.強化學習求解不需要將所有輸入全部解出答案，只需要把有代表性的、有影響策略的值求解出來，再找到最優的策略即可.與傳統模型求解相比較，其迭代速度和結果質量均有極大提高.對于特別復雜的問題，可用神經網絡即深度Q 網絡（DQN），一般問題求解可應用Q-learning 或Sarsa[11].

3）初始輸入要求低.在其他機器學習方案中，輸入值的量直接決定生成標簽的優劣，從而可影響最終結果，而強化學習在初始輸入要求較低，生成的訓練模型更具有通用性，可減少其他應用環境的再次輸入、再次訓練，實現“一次輸入，多次應用”[12].

4）搜索速度快.解決網絡路由問題需要用到路徑搜索功能，傳統解決方案是尋找最小跳數或基于Dijkstra 算法，必須掌握整個網絡的基本信息（如Dijkstra 算法中邊值信息），且搜索過程中對計算、存儲能力有一定要求.而強化學習不必掌握整個網絡的基本信息，是尋找最優解的過程，只需從一點開始迭代即可，當迭代到收斂時，便得出需要搜索的路徑，處理問題的本質完全不同[13].

當前，隨著計算機性能的不斷提高，各種框架的不斷完善，強化學習解決優化問題的案例有很多.為提出高效、通用的解決方案，文中應用強化學習解決智能路由問題.

3 智能路由算法

3.1 多目標優化模型

智能路由體現在每次路由決策均選擇最佳路徑實現，此目標對云計算數據中心網絡起到關鍵作用.智能路由一方面兼顧整個網絡的負載均衡，另一方面盡最大限度利用可用的傳輸路徑（帶寬與數量）.由于云計算數據中心具有并非最短路徑是最優傳輸路徑且實時傳輸路徑多變的特點，因此文中基于路徑的傳輸性能與有效帶寬，設計了基于強化學習的多目標優化智能路由算法.

在云計算數據中心網絡中，設G=(V,E)，其中G為整個網絡的拓撲集合；V是其組成拓撲的所有頂點集合，有n=|V|且n>0；E是網絡中所有的邊集合，有，并排除i與j相等的情況，且vi、vj均屬于V集合，而表示云計算數據中心網絡中的網絡鏈接，也就是現實中的傳播時延計算的基礎.在整個數據中心網絡中可用帶寬集合設為Wb，傳播時延集合設為De.

根據上述內容，可定義pst為從起始點到傳輸終止點的所有邊，即

其中，式（1）中的排隊兩端點，即vs≠v1及vm≠vt.假設其中任意的值j與k都有vj≠vk（是不相交鏈路），而在所有不相交的鏈路集合，則有

其中：式（2）中任意的值j與k都有pst(j)∩pst(k)=φ.

在整個網絡中，傳輸帶寬的最小值對路由的選擇起關鍵作用.因此，根據最初的帶寬集合定義，可得知一條路徑中最小帶寬為

另外在pst中同一鏈接源點，有多條鏈路相互鏈接，某一條最大的帶寬為

根據通信理論可知，網絡傳輸時延=傳輸時延+處理時延+排隊時延+傳播時延.在云計算數據中心網絡中，處理時延、排隊時延與傳播時延可忽略，因此起關鍵作用的是傳輸時延.即

為了獲取高效的路徑，需要求出最小傳輸時延，即有

根據最開始的研究，智能路由的目標是盡可能選擇時延低、帶寬高的路徑為傳輸路徑，實現整個網絡的吞吐量轉化成多目標模型.即

下一步將求解多目標優化模型（7）.求解的思路是首先按目標條件求出路徑集合，然后再計算出k條不相交路徑，并輸出最優路由.

3.2 算法實現

文中多目標優化模型的實現過程是在文獻[14，15]的基礎上改進而來.整個算法實現過程的偽代碼見表2.前一部分是按目標條件找出所有的路徑集合，后一部分再從路徑集合中找出符合條件的k條不相交路徑.

表2 生成路徑集合并查找k條不相交路徑

假定優化目標個數是m，模型（7）中的優化目標是相互獨立的.為應用強化學習求解，也可表示為

其中：X是生成獎勵的向量.整個多目標優化的目標是求解X?，即f(X?)在滿足X約束下的最優解，其子目標的最大化，可表示為

算法時間復雜度不高，可從整體上實現多個目標的統一處理.下文將驗證算法的有效性，并評估其性能.

4 實驗仿真與結果分析

通過構建云計算數據中心網絡，并模擬高負載下訪問情況以驗證所提出解決方案的有效性.依據參考文獻[16]的仿真參數，搭建如下仿真平臺.硬件環境：Intel(R)Core(TM)i5 12400F CPU@2.50 GHz×6，32 GB 內存.Python 版本號：Python 3.7.操作系統：Ubuntu 22.04.網絡路由分析與調試工具：Wireshark v3.6.3版，用于分析網絡路由.網絡模擬工具：Mahimahi，用于模擬仿真實驗中的網絡參數.

數據中心網絡選用Fat-tree，其中k=2，搭建云計算數據中心網絡如圖2 所示.鏈路最大帶寬為10 Mbps，時延為5 ms.

圖2 基于Fat-tree的數據中心網絡

強化學習參數見表3所示.

表3 強化學習參數

根據Fat-tree 的特點，隨著網絡規模的增加，各分帶寬也會擴大，能夠為數據中心網絡提供高吞吐量的傳輸能力，有利于緩解高負載的壓力.不同Pod 間的云服務器可相互通信，能應對一定的出錯概率[17].當然，Fat-tree 也有一定的缺陷，如整個網絡的規模取決于最頂層的核心交換機，不論是核心交換機還是邊緣交換機，只要出現故障，即對整個網絡路由有較大的影響[18-21].

仿真對比對象分別為Dijkstra、ECMP、文獻[13]、文獻[14]、智能路由算法（即文中算法）.通過仿真對比以下指標分析各算法的綜合性能.

1）吞吐量.吞吐量用于衡量網絡傳輸能力，其計算方法是單位時間內傳輸的數據量.吞吐量計算式為

式中：G是吞吐量；t是傳輸時間；d是此段時間內傳輸數據的總字節數.

吞吐量反映整個網絡的傳輸能力，傳輸結果如圖3 所示.當訪問量一般時，幾種算法的吞吐量相差不大，隨著訪問次數的增加，文中算法吞吐量最高；文獻[13]中強化學習獎勵函數是固定的，不適合數據中心情景使用；文獻[14]中多目標優化方法不適合負載過高時的應用，性能最差，無法應對高訪問、高負載；ECMP 表現也較一般.文中算法以最大化吞吐量為優化目標之一，且能實時調整最優路由方案，當load=70時，實現了避免擁塞，未造成吞吐量明顯下降，整體傳輸能力優于其他算法.

圖3 吞吐量與負載關系圖

2）負載與平均帶寬利用率.負載并發生成所使用的軟件為Webbench 5.0.平均帶寬利用率的計算式為

式中：Bu是平均帶寬利用率；對于云計算數據中心網絡中的某一條流，Bs是發送前帶寬；Br是實時帶寬；x是統計的流總數量.

負載與平均帶寬利用率間的關系可以直接反映出大規模訪問時的性能，如是否擁塞、能否滿足高負載傳輸等.平均帶寬利用率與負載比較結果如圖4所示.

圖4 平均帶寬利用率與負載關系圖

從圖4中可以得出：當一般規模訪問時，所有算法的平均帶寬利用率都是1，但是隨著訪問規模的增加，Dijkstra算法平均帶寬利用率最先下降，且下降速度快于其他算法，最終在0.17處停止；文獻[13]方案不適合數據中心中應用，與Dijkstra 算法有相似的結果；文獻[14]方案未考慮負載，出現不穩定，波動較大；ECMP 有平分帶寬的能力，平均帶寬利用率優于Dijkstra 算法；智能路由算法根據實時的網絡狀況選擇最優路由，較好地應對了高負載、大規模訪問，有較高的平均帶寬利用率，傳輸性能最佳.

從圖4的試驗數據分析可知，不足之處是訓練過程可能會出現零星的低估問題，影響強化學習的決策，解決方案是應用多個不同的神經網絡，盡可能縮小由于值的低估對算法核心的影響.如Bootstrapping法，將有限的樣本數據通過重新設計抽樣規則生成新的、有代表性的父本數據，從而擴充訓練數據，實現需要的信息訓練數.再者，強化學習求解需要進行大量的試錯和迭代，文中研究可能會導致求解效果不佳或出現過擬合的問題.

5 結語

文中研究了在云計算數據中心網絡大規模訪問時，路由實現難而造成的負載不均衡問題，提出基于強化學習云計算數據中心網絡智能路由算法，實現了根據實時路徑傳輸能力選擇最優路由方案.通過仿真試驗可知，智能路由占用計算資源少，吞吐量高于普通路由方案，該算法綜合考慮了高負載環境下對網絡的影響，能及時地選擇合適的傳輸路徑，可實現集中式訓練一次，分布式執行多次的協作模式，相比其他機器學習模型，可快速找出最優解，響應速度快.但智能路由系統每次只選擇最佳路徑進行路由決策，當訪問規模較小時，默認路由方案會被應用.未來工作中，將繼續研究復雜情況下，如何降低模型的復雜度并減少訓練時間與計算資源，進一步研究深度強化學習（如強化學習確定性策略梯度DPG、近端策略優化PPO等）及多智能體強化學習在云計算數據中心網絡中的路由解決方案.