0 引言

    軟件定義網絡(Software-Defined Networking，SDN)多域控制器部署解決了可擴展性和靈活性的問題^[1-2]，由于流量的傳輸具有時間性和空間性^[3]，在某個時間段或者某個域內會出現流量激增和瞬減，因此在各個子域中的控制器的流量負載情況不盡相同，從而導致該域的控制器出現過載和輕載的狀況，不利于整個網絡架構的穩定和控制器負載均衡^[4]。

    針對該問題，本文提出了一種面向SDN控制器負載均衡的交換機自適應遷移策略。首先將SDN網絡劃分為各個子域，對各子域內控制器的負載進行測量，將測量數據傳到數據中心，根據測量情況動態地設置控制器過載判定門限值，判斷在各SDN子域是否存在過載的控制器；然后基于自適應遺傳算法^[5]把過載控制器所在SDN子域作為交換機遷移過程的遷出域，選擇該子域的相鄰最優子域作為交換機的遷入域；最后應用生存期和淘汰機制將遷出域內負載度高的交換機遷移至遷入域，從而實現整個網絡的負載均衡，提升了網絡可靠性。

1 模型構建

    在SDN多域網絡中，扁平式分布架構的引入會引起各個SDN子域內控制器負載不均衡^[6]，在這里，通過對交換機流量和控制器的負載進行測量，選擇遷入和遷出子域，將遷出域內的負載度高的交換機遷移至相鄰的遷入域內，實現了控制器負載和交換機數量在SDN子域的均衡部署。

    為了實現所設計功能，將SDN的子域中的模塊分為交換機鏈路模塊、控制器模塊、遷移模塊三大部分，如圖1所示。

    底層的交換機和物理鏈路表示該子域的交換機鏈路模塊，由多個交換機通過物理鏈路連接構成。往上是控制器模塊，負責管理網絡中的流量和拓撲。遷移模塊位于頂端，網絡中的各個控制器都與遷移模塊相連接，負責和協調交換機在各個SDN子域內的有效遷移。

1.1 交換機鏈路模塊

    一個完整的SDN網絡被切分成各個SDN子域，因此各個交換機群組也被歸類到不同的SDN的子域中。假設所有的交換機都支持OpenFlow協議^[7]，主要執行數據轉發。一個完整的OpenFlow交換機如圖2所示，包括流表、安全通道及OpenFLow協議三部分，交換機與交換機之間、交換機與控制器之間由物理鏈路相連接。

1.2 控制器模塊

    不同的SDN控制器歸屬于不同的SDN子域，負責管理該子域的網絡，并與其他域的SDN控制器進行相互通信。對SDN控制器的內部模塊進行劃分，主要分為5個部分：(1)南向接口，主要負責與數據平面通信；(2)負載收集與測量模塊，負載收集該控制器的負載信息，并聚合其他控制器的負載信息；(3)評估與決策模塊，負責評估控制器負載是否超過預設的門限值，根據各控制器的負載情況進行決策，設定動態門限值；(4)存儲模塊，儲存子域內所有交換機的鏈路消息、拓撲消息和流量消息；(5)北向接口，負責與應用平面進行通信。

1.3 遷移模塊

    遷移模塊根據評估和決策的結果協調各個SDN子域，實行遷移策略，選擇遷出和遷入域，將遷出域內高負載度的交換機遷移至遷入域內，完成控制器的負載均衡和交換機部署均衡。

2 設計實施

2.1 負載收集與測量

    (1)控制器負載的收集

    在SDN網絡中，控制器的負載主要由以下4個部分構成：①待處理的Packet_In 的事件數(P)；②維護其管理域和全局的拓撲所需的流量(F)；③與其他控制器的通信開銷(K)；④安裝上層應用產生的流表項(N)。每個部分在不同控制器中所占的權值不同，設定相應的權值分別對應為u₁、u₂、u₃、u₄。因此可以得到控制器負載的計算公式為：

    (2)交換機負載的測量

    基于分布式SDN多域部署將整個網絡劃分為多個SDN子域，利用圖論的知識，設網絡拓撲為G(V，E)，其中，V代表網絡中交換機，E代表交換機之間的鏈路。將網絡劃分為N個子域，各個子域可表示為S_i(W_i，L_i)，其中，W_i表示子域S_i中的交換機，L_i表示S_i中的鏈路，有：

    定義 交換機負載度。交換機向控制器請求的Packet_In 的事件數定義為交換機的負載度，設為f_k。

2.2 控制器過載判定

    由于交換機流量在時間和空間上的波動性，有可能導致各SDN子域控制器負載不均衡，因此本文設計了一種控制器過載的動態判定機制。設置動態門限L_A，子域S_i中控制器的負載值為C_i，判定過載門限值設為ε，則L_A如式(7)所示：

2.3 選擇與遷移策略

    選擇與遷移策略主要包含兩部分內容：(1)基于自適應遺傳算法的遷入和遷出域選擇策略；(2)基于存活期和淘汰機制的交換機動態遷移策略。首先利用自適應遺傳算法搜索能力強的特點，設定適應度函數作為度量，在進化過程的每一代，動態地選擇交叉概率P_c和變異概率P_m，選擇出實施遷移的最佳SDN子域。然后計算出遷入和遷出SDN子域的相對平均負載度，動態地計算出兩個SDN子域的遷移率，根據遷移率確定可進行遷移交換機的數目，按照交換機負載度的高低進行排序，應用存活期和淘汰機制把遷出域內一定數目的高負載度交換機遷移到遷入域內，從而實現SDN多域控制器的負載均衡和交換機的部署均衡。

2.3.1 遷出域和遷入域選擇

    將控制器負載最大的子域設為遷出域，設為Sh。遷入域的選擇是綜合考量各類影響因素后得到的結果，不僅要考慮候選SDN子域的控制器負載情況(記為C)，還要考慮到遷入域和遷出域之間的傳輸時延(記為D)，遷入過程所產生的通信流量記為T。設目標函數為Q，如式(8)所示：

    在遷出域的相鄰子域中，將具有最小目標函數Q_min所在的子域設為遷入域，記為S_l。本文采用自適應遺傳算法來求取目標函數的最小值Q_min。

    自適應遺傳算法中的要素進行如下設定：

    (1)編碼設計

    在這里本文采用二進制編碼，將原問題表示為一個二進制的0~1字符串的形式，然后在位串空間上進行迭代遺傳操作，得到的結果再通過解碼的過程來還原成其解空間的解。例如，(0，1，1，0，1，0)就是一個長度為6的二進制編碼染色體。

    (2)適應度函數

    適應度函數是對遺傳算法中解的好壞進行度量的一種標準，在這里選取目標函數Q作為該算法的適應度函數，根據適應度函數計算個體的適應度。

    (3)交叉和變異

    自適應遺傳算法中的交叉操作是指兩個將相互配對的個體按照一致交叉的方式相互交換部分基因，從而形成兩個新的個體，交叉概率為P_c。與之類似，變異操作是指將個體的染色體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替換，形成新的個體，記變異概率為Pm。

    算法1：遷入、遷出域選擇算法

2.3.2 交換機自適應遷移策略

    基于算法1得到整個網絡中所要遷入和遷出域，然后計算出遷入和遷出的兩個SDN子域的相對平均負載度，得到兩個SDN子域的遷移率。根據遷移率選擇一定數目的交換機，使得遷出域里負載度高的交換機遷移到遷入域內，并加入存活期和淘汰機制，防止在遷移過程中有多個遷出域對應一個遷入域時，遷入域內有過多的交換機遷入，造成該遷入域負載驟增，產生二次遷移問題，平衡了各SDN子域內交換機的數量。

    (1)遷移率的調整

    遷移率是對SDN子域的遷入和遷出能力的定量描述，通過遷移率的比較與計算可以得出能夠遷入和遷出交換機的最佳數量。

    式(10)中兩個SDN子域的一個平均負載度為0，另一個為極值時，M(q，p)=0，需要滿足條件d+e=0。

    (2)基于存活期的淘汰機制

    本文設計了一種基于存活期和淘汰機制的交換機自適應遷移算法，即對參與遷移的交換機計算其存活期，若遷入個體年齡大于它的存活期就要被淘汰，不再參與遷移過程。

    存活期基于以下兩個原則：①負載度低的交換機的存活期大于負載度高的交換機的存活期；②當某個SDN子域的交換機規模過大時不再接收新的交換機。

    在此，為交換機設定兩個參數：年齡Y(X_j)和壽命L(X_j)。交換機X_j每經過一次遷移流程，稱為一代，其年齡加1，其存活的代數不能超過其存活期L(X_j)。為了防止子域的交換機數量過多或過少，引入規模控制門限值R，f(X_j)為交換機的負載度函數值，當前域的最大、最小和平均負載度分別為f_max、f_min、f_avg，設置在SDN子域中交換機最大數目為M_max。規模控制門限值R為：

其中，min LT是允許最小壽命，max LT是允許最大壽命。

    算法2：交換機自適應遷移算法

3 性能評估

    本文應用基于Ryu的分布式SDN控制器^[8]，在此基礎上添加了收集與測量模塊、評估決策模塊和存儲模塊，并編寫了遷移模塊來負責整個域內交換機的遷移。運用Cbench^[9]軟件，使用Mininet^[10]來模擬整個網絡拓撲，通過模擬一定數量的交換機連接到控制器，發送Packet-In消息，并等待控制器下發flow-mods消息來衡量控制器的性能。

    模擬一個具有5個控制器和100個交換機的網絡拓撲，將整個網絡劃分為5個SDN子域，每一個子域內各部署一個控制器，使用Mininet來模擬整個網絡拓撲。首先為了說明本文所述遷移機制的有效性和均衡性，采用模擬主機在網絡中進行發送數據包，在交換機上產生大量的流量負載，將本文所采用的交換機自適應遷移策略(Adaptive Migration Policy，AMP)、ElastiCon^[3]提出的就近遷移策略(Nearest Migration Policy，NMP)和隨機遷移策略(Random Migration Policy，RMP)進行對比。控制器負載率代表控制器所承受的負載與可承受最大負載的比值，如圖3所示，對比3種策略下控制器負載率隨時間的變化。

    從圖3中可以看出，剛開始時設定3種策略下所屬的控制器都處于過載狀態，隨著時間的推移，隨機遷移策略RMP對于要遷移的SDN子域隨機選擇，導致曲線處于無規律波動狀態，有所下降但波動幅度較大；在0~60 s內，就近遷移策略NMP和自適應遷移策略AMP呈下降趨勢；大約60 s遷移過程完成之后波動幅度較小，趨于穩定，但AMP的相對負載率在0.76左右比起RMP的0.91有明顯的下降，交換機遷移效率提升了19.7%，表明采用本文提出的自適應遷移策略可以使過載控制器的負載率得到明顯改善，控制器資源得到充分的調動，各個控制器的負載更加均衡。

    如圖4所示，在前60 s內，由于交換機的遷出，遷出域控制器的負載基本上是呈現明顯的下降趨勢，且遷入域由于有部分負載度高的交換機從遷出域中遷移過來，因此遷入域控制器的負載有一定程度的上升；在60 s之后，兩個域內的控制器的負載基本處于均衡狀態，由數據統計可以看出，遷出域控制器的初始負載值是設定為1 400 Request/s，遷入域控制器的初始負載值設定為800 Request/s，經過遷移之后，遷出域控制器負載值變為1 133 Request/s，相對于初始值降低了19.1%，同時遷入域控制器負載值變為為1 041 Request/s，都低于控制器過載判定門限值1 300 Request/s，遷出域和遷入域的負載得到了很好的均衡。

4 結論

    本文針對SDN多域部署下各個子域控制器之間的負載不均衡問題，設計了基于自適應遺傳算法的遷入、遷出域選擇機制，根據遷移率，存活期和淘汰機制在遷出域中選擇一定數目的交換機遷移到遷入域中，實現了各SDN子域控制器的負載均衡和交換機在各子域內的均衡部署。

參考文獻

[1] HU T，LAN J，ZHANG J.Bidirectional matching strategy for multi-controller deployment in distributed software defined networking[J].IEEE Access，2018，6：14946-14953.

[2] HU T，YI P，ZHANG J，et al.Reliable and load balance-aware multi-controller deployment in SDN[J].China Communications，2018，15(11)：184-198.

[3] DIXIT A， HAO F， MUKHEＲJEE S，et al．Towards an elastic distributed SDN controller[C].HotSDN′13.New York:ACM,2013: 7-12.

[4] ZHONG H，FANG Y，CUI J.LBBSRT：an efficient SDN load balancing scheme based on server response time[J].Future Generation Computer Systems，2017，68：183-190.

[5] 梁霞.改進的自適應遺傳算法及其在作業車間調度中的應用[J].大連交通大學學報，2009，30(4)：47-49.

[6] YEGANEH S H，GANJALI Y.Kandoo：a framework for efficient and scalable offloading of control applications[C].Proceedings of ACM SIGCOMM HOTSDN，2012.Helsinki，Finland：ACM，2012：19-24.

[7] EUGEN B，RADU B，SERBAN G O，et al.On multi controller placement optimization in software defined networking based WANs[C].Proceedings of The Fourteenth International Conference on Networks，2015.ICN，2015：261-266.

[8] ASADOLLAHI S，GOSWAMI B，SAMEER M.Ryu controller′s scalability experiment on software defined networks[C].IEEE(ICCTAC)，Bangalore，2018：1-5.

[9] JAWAHARAN R，MOHAN P M，DAS T，et al.Empirical evaluation of SDN controllers using mininet/wireshark and comparison with cbench[C].ICCCN，Hangzhou，2018：1-2.

[10] KHALID A，QUINLAN J J，SREENAN C J.MiniNAM：a network animator for visualizing real-time packet flows in Mininet[C].ICIN 2017，Paris，2017：229-231.

作者信息:

周  寧，胡  濤，胡宇翔，汪斌強

(中國人民解放軍戰略支援部隊信息工程大學，河南 鄭州450002)