SDN中基于Q-learning的動態交換機遷移算法

趙季紅，張　彬，王　力，曲　樺，鄭　浪

( 1.西安郵電大學 通信與信息工程學院，西安 710061;2.西安交通大學 電子信息學院，陜西 西安 710049)

SDN中基于Q-learning的動態交換機遷移算法

趙季紅1，2，張彬1，王力2，曲樺2，鄭浪1

( 1.西安郵電大學 通信與信息工程學院，西安 710061;2.西安交通大學 電子信息學院，陜西 西安 710049)

摘要:由于網絡流量動態變化，控制器負載均衡成為大規模部署軟件定義網絡研究的重點。提出基于Q-learning的動態交換機遷移算法，首先對軟件定義網絡中的控制器部署問題建模，再應用Q-learning反饋機制學習實時網絡流量，最后根據Q表格將交換機從高負載控制器動態遷移到低負載控制器上，實現控制器的負載均衡。仿真結果表明，所提算法能夠獲得較低的控制器負載標準方差。

關鍵詞:軟件定義網絡；OpenFlow；控制器；Q學習

軟件定義網絡(Software Defined Network，SDN)[1]具有控制與傳輸分離、集中式控制、軟件可編程特征，能夠使網絡控制與管理的成本降低,便于新業務的快速開發和部署，從而為網絡設計規劃與管理帶來了極大的靈活性，解決網絡結構的僵化問題成為了目前網絡技術研究的重點之一[2]。

SDN雖然能夠解決目前網絡中存在的問題，但是當SDN部署在大規模網絡中，其集中式控制平面的可擴展性和性能將會遇到極大的挑戰[3-4]，onix[5]、HyperFlow[6]等項目通過在網絡中部署多個相互連接的控制器，構建分布式控制平面成為解決上述問題的途徑。文獻[7]研究了SDN分布式控制平面中控制器的靜態部署問題，該方法使得交換機到控制器的時延最短，并保證控制器的處理能力能夠滿足其上所連接交換機上承載的業務需求。但是，在多控制器部署環境下，由于網絡負載動態變化，需要將交換機從負載較重的控制器動態遷移到負載較輕的控制器下，為了避免個別控制器因負載過重造成控制器宕機，要求實現控制器之間的負載均衡。文獻[8]提出了彈性控制平面的概念，知識架構以及遷移過程的簡述，但文章中并沒有給出具體的算法；文獻[9]定義了負載和時延等指標，但是控制器的狀態仍是處于靜態；文獻[10]提出高可靠性控制器部署，但也是靜態情況下，且沒有考慮負載的變化情況;文獻[11]通過分析控制器和轉發平面之間的彈性控制關系，提出通過感知控制器部署和控制流量路由達到最大化快速故障切換率來提高控制平面彈性的機制。總之，交換機的動態遷移算法是目前研究的重點。

本文提出軟件定義網絡中基于Q-learning的動態交換機遷移算法，首先基于Q-learning算法對SDN網絡中交換機動態遷移問題進行數學建模，定義狀態空間、動作空間、即時回報函數、Q值更新函數、動作選擇策略，再提出基于Q-learning的動態交換機遷移算法，給出交換機遷移算法的流程，根據網絡負載的動態變化，應用Q-learning算法確定交換機遷移方案，保證控制器負載均衡。

1交換機遷移問題建模

SDN網絡具有交換與傳輸分離的特征，用戶可以在控制平面上自定義網絡控制與管理策略，數據平面由只負責數據轉發的交換機互聯組成。在大規模部署的SDN網絡中，多個控制器相互連接構成集中式控制平面，交換機連接在控制器上，數據包的轉發策略是由控制器下發給交換機的，而交換機只做數據交換。表1是交換機遷移的相關標號。

表1交換機遷移的相關標號

變量含義ci核心控制節點或者控制器si普通交換機連接si的外設普通交換機或者其他網絡設備

s2從控制域1劃分到控制域2。交換機的遷移過程如圖1、圖2所示。

圖1　交換機s1處于切片1中的c1控制器

圖2　交換機處于切片1中的控制器

si→cj表示交換機si連接在控制器cj上，si→ci?si→cj表示交換機si從控制器ci遷移到控制器cj上。如圖1～圖2所示，控制器c1上連接的交換機s1，s2等，s1上的總流量較多，控制器c2上連接的其他交換機，其總負載較少，將交換機s1從控制器c1上遷移到控制器c2上，保證控制器的負載均衡，提高SDN網絡對用戶業務與應用的響應速度，進而提升SDN網絡的性能和可擴展性。

2基于Q-learning的動態交換機遷

移算法

2.1基于Q-learning動態交換機遷移算法相關

元素定義

應用Q-learning算法的感知管理特性，需要對相關的一些要素進行確定，并動態選擇系統性能指標的最優化動作。基于Q-learning彈性控制器系統模塊與環境的交互示意圖如圖3所示。

圖3　基于Q-learning彈性控制器系統模塊與環境的交互

下面對應用Q-learning算法所要確定的幾個重要因素進行說明。

1)狀態空間定義

智能體合理選擇動作的基礎是先劃分狀態空間s={C1,C2,C3,C4}，合理的狀態變量s應具備兩個特性：(1)可知性，只有智能體可以提取和處理的信息才能作為狀態輸入；(2)無后效性，每一個狀態都與它的前一狀態有關系。

2)動作空間定義

由于系統中可采取的動作大于狀態空間(核心控制器的個數)，而對于Q-learning，每個狀態只能選擇一個動作。所以在彈性控制器結構中，本著就近原則，預先隨機把其余n個交換機分配給m個核心控制器管理。同時，引入遷移代價的概念，即當需要遷移的時候，采用dijkstra算法，交換機負載很小的時候，它也并不會遷移到較遠的核心控制器的管理之下。

3)即時回報函數

回報函數r(s,a)設計是基于系統的性能指標的，希望分配給核心交換機的slaver交換機在遷移代價是最小的，規定回報函數為正值，回報函數

(1)

4)搜索策略

搜索策略用來平衡“探索”和“利用”。“探索”(explore)和“利用”(exploit)是Q-learning搜索策略的兩個重要方面。本文采用最常見的ε貪婪算法

(2)

式中：a表示選取在狀態s下以1-ε選擇具有最大Q值的動作。在系統運行之前，根據就近原則把30個交換機連接到4個核心控制器，并由當前核心控制器控制下一步遷移。

5)Q值更新

預先設置了一個m×n的Q矩陣，并把所有的初始值都設定為相同值，當Q-learning運行第一次的時候，根據dijkstra算法，計算出每個交換機分別到核心交換機的最短距離Lx={lx1,lx2,lx3,lx4}(其中lx1表示標號為x的交換機到標號為1的核心交換機的最短距離，依次類推)。智能算法的控制策略即是選擇哪種學習策略，當把累積回報值作為策略優劣的評估函數時，較好的控制策略對學習體產生盡可能大的累積回報值。 在此狀態下，此時的回報函數值以及所知的之前回報值都可以確定，后續狀態的回報值無法確定，因此，累積回報值計算將是個重要的問題。評估函數采用Q函數累計迭代運算方程為

(3)

在當前狀態s和當前動作a下：r(s,a)為在智能體獲得的即時回報(reward)；Snext∈S為系統將會轉入的下一狀態；γ為折扣系數取值[0,1]；b為Snext下可采取的動作；Q(s,a)為智能體總計期望回報的預計。

2.2基于Q-learning的動態交換機遷移算法

將Q-learning算法思想應用于SDN控制器的動態遷移問題，建立基于Q-learning的控制器負載的動態感知，并能自適應控制器的協調分配。

基于Q-learning的遷移管理流程如下：

1)初始化Q值矩陣[Q(s,a)]m×n，初始化矩陣所有的值全為1。

2)對接下來的每個后續觸發搜索周期，自動重復以下動作：

(1)局部控制域內，流量得不到處理或者處理能力嚴重過剩。系統自動查找Q陣，在Q表，每一個豎列有4個Q值。根據dijkstra算法得出相近的兩個核心控制器，并選取具有最大Q值的狀態作為當前的激活狀態s；

(2)根據ε貪婪算法，針對每一個slaver交換機，在每一豎列中以1-ε機的概率選擇最大Q值的動作，并將該slaver交換機遷移到與相應的核心控制的管理下；并記錄在每個周期內發生遷移的交換機總個數，設為Mi；

(3)對于處于一個周期內的slaver交換機的負載，用每個slaver交換機的負載除以在該周期內每個核心控制器的總負載，得出r(s,a)；

(4)當在狀態s下，選擇動作a后得到的Q值，如果在此狀態下Q值比原二維矩陣中的相應位置Q值大，則更新，反之則不進行更新，由于此列中相應位置對應得到的Q值已經比此時得到的Q值小，所以就沒必要進行更新；

(5)選擇Q陣中每列具有最大Q值的狀態作為下一個狀態，如果最大的Q值還是當前位置的Q，則交換機不發生遷移，反之則遷移；同時更新狀態s的Snext；

(6)回到步驟(2)運行到狀態s，并依次循環。

3仿真結果及分析

3.1仿真環境

考慮到目前還沒有類似Q-learning的自學習算法被用于解決交換機的動態遷移問題，本文只對參數進行仿真，分析所提算法的收斂性，以及保證控制器負載均衡的能力。

假定每個核心控制器所能承受的負載是有限的，當負載變化超過核心控制器的控制范圍時，根據Q學習算法和dijkstra算法，讓與其控制范圍相近周圍的其他核心交換機所控制的交換機遷移到它的控制范圍，讓其有能力處理短時的超負荷的負載。并且，當其他核心交換機出現過載時，此slaver交換機也可以遷移到其他的核心控制器的管理范圍之下。

通過仿真，對一個核心交換機每個周期所管理交換機的負載之和與任一個slaver交換機的負載進行分析，多次測試后發現，此和的方差總是在經過一段時間后趨于穩定，并圍繞著某個值鋸齒形波動。而且隨著程序的進行，每個周期內遷移的交換機個數也趨于穩定，最后也是圍繞某個值作鋸齒形波動，遷移代價越來越小。

在本文中，設置該網絡拓撲包括4個核心控制器和30個普通交換機，即前面m和n的值分別取值為4和30。仿真環境是以北美interent2為參照，共有34個總交換機，在其中選出4個為核心控制器，其余30個交換機在仿真運行開始之前就近劃分到4個核心控制器的控制域范圍中，控制器與交換機部署在統一物理位置，并且控制器的位置保持不變。交換機的流量服從μ=50,σ=0.15的正態分布。設定仿真環境中Q-learning為1 s的刷新周期.

3.2算法仿真結果及性能分析

在本文中，以文獻[7]中北美interent2(如圖4)為仿真架構，通過上面狀態、動作、遷移選擇等要素的選取可以看出，本文中的遷移管理算法實際上是通過回報值的設計和Q表值來指導控制器遷移調度策略的，盡管被遷移的普通控制器的負載、距離等屬性(遷移代價)作為狀態空間沒有直接體現到整個拓撲結構中，但每個被遷移的控制器對當個控制域的流量負載處理過程起到了良好的補充協助作用，且負載對遷移過程的影響是直接通過及時回報值來體現的。

圖4　北美interent2網絡拓撲

并且，Q-learning中的搜索策略使核心控制器不會總是選擇一個回報值最大的交換機，而是以一定概率選擇，那么當當前回報值最大的控制器不在核心控制器的選擇范圍中，就有可能在其他核心控制器的選擇范圍之內，這種選擇機制就保證了核心控制器能夠在不同的選擇策略上積累經驗，這也就支持了遷移任務的動態管理。

3.3控制器負載分析

單個核心控制器在運行和不運行Q-learning機制的負載均衡度(方差)如圖5所示。由圖5可以看出，當剛開始運行控制器系統時，每個核心控制器所控制的交換機都是預先隨機分配的，因此系統并不認為是理想的，所以每個周期剛開始運行時，每個周期都會有交換機的遷移(也包括由于受到遷移代價的影響，選擇次優的核心交換機而引起的非最佳選擇遷移次數)。此時遷移的交換機數很多，開始時遷移個數都基本在13左右，但是隨著時間的推移，程序會使整個系統越來越處于一個優化狀態，遷移次數或者頻率會越來越趨于平穩。最后基本都處于每次只遷移4個交換機。由于程序存在缺陷，沒有記錄在此優化過程中流量狀況不促發彈性控制器系統時的非核心交換機和核心交換機的狀態。

圖5　是否采用Q-learning機制負載均衡度

但是，而在此狀態下，系統整體也處于一個較為平穩的狀態，對于需要的系統何時運行到一個較為平穩的狀態，可以根據單個核心控制器的方差平穩狀態看出，交換機遷移的頻率達到較為穩定的時間和單個核心交換機方差函數趨于平穩的時間應該是相對的。

3.4Q-leaning參數對算法的影響

通過對以往關于貪婪算法的研究，在一定范圍內隨機賦給γ,ε，一定的值。并根據以往的經驗，發現在給定某個ε后，隨著感知周期的運行，對于單個核心控制節點的方差，γ越大，其方差收斂越慢，且其后續方差波動也越來越大。同時，當ε的值越大，系統對Q表值的選擇隨機性變大，當其越小時，又不能體現其選擇公平性。當γ=0.25時，單個核心控制器的方差總是收斂相對較快，后續也最穩定。雖然當γ=0.25，ε=0.3時收斂速度和負載均衡度也比較理想，但當其平穩后負載均衡度比γ=0.25，ε=0.2波動更大，所以最后認定γ=0.25，ε=0.2的效果最理想。因數據量和篇幅的原因只錄入100個周期的數據，同時當γ=0.25，ε=0.2后續曲線相對平穩。圖6給出了γ=0.15，ε=0.2；γ=0.15，ε=0.3；γ=0.25，ε=0.2；γ=0.25，ε=0.3的方差曲線。可以看出基于Q-learning的彈性控制器系統對于系統流量起到了很合理的調節分配作用，由此減少網絡中不必要的丟包而造成的網絡擁塞等。

圖6　不同值下的網絡負載均衡度

另一方面，在彈性控制器系統被觸發的周期內會有交換機的來回遷移，整個網絡較多時候處于能夠處理負載的狀態，只記錄了在觸發階段遷移的個數，并且當單個核心控制器處于穩定狀態后，系統再次被觸發后，每次遷移的個數總是在3左右波動。由此確定，整個系統已達到比較穩定的狀態，處于收斂。

4結束語

本文在軟件定義網絡系統中應用了智能控制理論中的Q-learning算法，在每個感知周期內，Q-learning算法中的狀態選擇是選擇每個核心控制范圍內有額外負載處理能力的交換機與核心控制器的鏈接狀態，將每個有額外處理能力的交換機調配到處理能力不夠的核心控制器下并受其管理作為在每個狀態下所采取的動作，收集到的流量來確定回報，在感知活動中學習經驗，從而提高優化學習效率。

參考文獻：

[1]QIN Z，DENKER G，GIANNELLI C，et al. A software defined networking architecture for the internet-of-things[C]. IEEE network operations & management symposium.[S.l.]:IEEE，2014：1-9.

[2]The openflow switch[EB/OL].[2015-10-10].http://www.open-flowswitch.org.

[3]LEVIN D，WUNDSAM A，HELLER B，et al. Logically centralized? state distribution trade-offs in software defined networks[C]//Proc. HotSDN’12 of ACM SICGCOMM. Helsinki，Finland：[s.n.]，2012：1-6. DOI：10.1145/2342441. 2342443.

[4]左青云，陳鳴，趙廣松，等. 基于OpenFlow的SDN技術研究[J]. 軟件學報，2013，24(5)：1078—1097. DOI：10.3724/SP.J.1001.2013.04390.

[5]KOPONEN T，CASADO M，GUDE N，et al. Onix: a distributed control platform for large-scale production networks[C]//Proc. 9th USENIX conference on operating systems design and implementation.[S.l.]：ACM，2010：351-364.

[6]TOOTOONCHIAN A,GANJALI Y. HyperFlow: a distributed control plane for OpenFlow[C]// Internet Network Management Conference on Research on Enterprise Networking.[S.l.]：ACM，2010：3-5.

[7]HELLER B，SHERWOOD R，MCKEOWN N. The controller Placement problem[C]//Proceedings of the first workshop on Hot topics in software defined networks.[S.l.]:ACM，2012:7-12.

[8]DIXIT A，HAO F，MUKHERJEE S，et al. Towards an elastic distributed SDN controller[J].ACM sigcomm computer communication review，2013，43(4)：7-12.DOI：10.1145/2491185.2491193.

[9]YAO G，BI J，LI Y.On the capacitated controller placement problem in software defined networks[J]. IEEE communications letters，2014，18(8)：1339-1342.DOI：10.1109/LCOMM.2014.2332341.

[10]HOCK D，HARTMANN M，GEBERT S，et al. Pareto-optimal resilient controller placement in SDN-based core networks[C]// International Teletraffic Congress.[S.l.]：IEEE，2013：1-2.DOI：10.1109/ITC.2013.6662939.

[11]BEHESHTI N,ZHANG Y. Fast failover for control traffic in Software-defined NetWorks[C]// IEEE Global Communications Conference (GLOBECOM).Anaheim，CA：IEEE. 1930-529X .DOI:10.1109/GLOCOM.2012.6503519.

趙季紅(1963— )，女，教授，博士生導師，研究方向為數寬帶通信網、新一代網絡的管理與控制；

張彬(1990— )，碩士生，研究方向為移動互聯網；

王力(1985— )，博士研究生，研究方向為網絡控制與管理、SDN、未來網絡；

曲樺(1961— )，教授、博士生導師，主研領域為現代通信網、計算機網絡體系結構；

鄭浪(1985— )，碩士生，研究方向為移動互聯網。

責任編輯：許盈

Dynamic switch migration algorithm in software defined networks based on Q-learning

ZHAO Jihong1，2, ZHANG Bin1, WANG Li2, QU Hua2, ZHENG Lang1

(1.SchoolofTelecommunicationandInformationEngineering,Xi’anUniversityofPosts&Telecommunications,Xi’an710061,China;2.SchoolofElectronicandInformationEngineering,Xi’anJiaotongUniversity,Xi’an710049,China)

Abstract:Load balance for controllers becomes an important research issue for large-scale deployed Software Defined Networks (SDN) with the dynamic network load. A dynamic switch migration algorithm based on Q-learning is proposed in this paper, which models controller placement problem firstly, then uses feedback scheme of Q-learning to learn the real time network load, and migrates switches from high-load controllers to low-load controllers on the bias of Q table lastly, to realize load balance of controllers. Simulation results show that the proposed algorithm gets low standard deviation of load born on controllers.

Key words:software defined networks;OpenFlow;controller;Q-learning

中圖分類號:TP393.0

文獻標志碼:A

DOI：10.16280/j.videoe.2016.06.013

基金項目：國家自然科學基金項目(61371087)；國家“863”計劃項目(2015AA015702)

作者簡介：

收稿日期：2015-12-09

文獻引用格式：趙季紅，張彬，王力，等. SDN中基于Q-learning的動態交換機遷移算法[J].電視技術，2016，40(6)：68-72.

ZHAO J H，ZHANG B，WANG L，et al. Dynamic switch migration algorithm in software defined networks based on Q-learning[J].Video engineering，2016，40(6)：68-72.

專題SDN技術與應用