0 引言

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

    針對(duì)該問(wèn)題，本文提出了一種面向SDN控制器負(fù)載均衡的交換機(jī)自適應(yīng)遷移策略。首先將SDN網(wǎng)絡(luò)劃分為各個(gè)子域，對(duì)各子域內(nèi)控制器的負(fù)載進(jìn)行測(cè)量，將測(cè)量數(shù)據(jù)傳到數(shù)據(jù)中心，根據(jù)測(cè)量情況動(dòng)態(tài)地設(shè)置控制器過(guò)載判定門(mén)限值，判斷在各SDN子域是否存在過(guò)載的控制器；然后基于自適應(yīng)遺傳算法^[5]把過(guò)載控制器所在SDN子域作為交換機(jī)遷移過(guò)程的遷出域，選擇該子域的相鄰最優(yōu)子域作為交換機(jī)的遷入域；最后應(yīng)用生存期和淘汰機(jī)制將遷出域內(nèi)負(fù)載度高的交換機(jī)遷移至遷入域，從而實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的負(fù)載均衡，提升了網(wǎng)絡(luò)可靠性。

1 模型構(gòu)建

    在SDN多域網(wǎng)絡(luò)中，扁平式分布架構(gòu)的引入會(huì)引起各個(gè)SDN子域內(nèi)控制器負(fù)載不均衡^[6]，在這里，通過(guò)對(duì)交換機(jī)流量和控制器的負(fù)載進(jìn)行測(cè)量，選擇遷入和遷出子域，將遷出域內(nèi)的負(fù)載度高的交換機(jī)遷移至相鄰的遷入域內(nèi)，實(shí)現(xiàn)了控制器負(fù)載和交換機(jī)數(shù)量在SDN子域的均衡部署。

    為了實(shí)現(xiàn)所設(shè)計(jì)功能，將SDN的子域中的模塊分為交換機(jī)鏈路模塊、控制器模塊、遷移模塊三大部分，如圖1所示。

    底層的交換機(jī)和物理鏈路表示該子域的交換機(jī)鏈路模塊，由多個(gè)交換機(jī)通過(guò)物理鏈路連接構(gòu)成。往上是控制器模塊，負(fù)責(zé)管理網(wǎng)絡(luò)中的流量和拓?fù)洹＿w移模塊位于頂端，網(wǎng)絡(luò)中的各個(gè)控制器都與遷移模塊相連接，負(fù)責(zé)和協(xié)調(diào)交換機(jī)在各個(gè)SDN子域內(nèi)的有效遷移。

1.1 交換機(jī)鏈路模塊

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

1.2 控制器模塊

    不同的SDN控制器歸屬于不同的SDN子域，負(fù)責(zé)管理該子域的網(wǎng)絡(luò)，并與其他域的SDN控制器進(jìn)行相互通信。對(duì)SDN控制器的內(nèi)部模塊進(jìn)行劃分，主要分為5個(gè)部分：(1)南向接口，主要負(fù)責(zé)與數(shù)據(jù)平面通信；(2)負(fù)載收集與測(cè)量模塊，負(fù)載收集該控制器的負(fù)載信息，并聚合其他控制器的負(fù)載信息；(3)評(píng)估與決策模塊，負(fù)責(zé)評(píng)估控制器負(fù)載是否超過(guò)預(yù)設(shè)的門(mén)限值，根據(jù)各控制器的負(fù)載情況進(jìn)行決策，設(shè)定動(dòng)態(tài)門(mén)限值；(4)存儲(chǔ)模塊，儲(chǔ)存子域內(nèi)所有交換機(jī)的鏈路消息、拓?fù)湎⒑土髁肯ⅲ?5)北向接口，負(fù)責(zé)與應(yīng)用平面進(jìn)行通信。

1.3 遷移模塊

    遷移模塊根據(jù)評(píng)估和決策的結(jié)果協(xié)調(diào)各個(gè)SDN子域，實(shí)行遷移策略，選擇遷出和遷入域，將遷出域內(nèi)高負(fù)載度的交換機(jī)遷移至遷入域內(nèi)，完成控制器的負(fù)載均衡和交換機(jī)部署均衡。

2 設(shè)計(jì)實(shí)施

2.1 負(fù)載收集與測(cè)量

    (1)控制器負(fù)載的收集

    在SDN網(wǎng)絡(luò)中，控制器的負(fù)載主要由以下4個(gè)部分構(gòu)成：①待處理的Packet_In 的事件數(shù)(P)；②維護(hù)其管理域和全局的拓?fù)渌璧牧髁?F)；③與其他控制器的通信開(kāi)銷(K)；④安裝上層應(yīng)用產(chǎn)生的流表項(xiàng)(N)。每個(gè)部分在不同控制器中所占的權(quán)值不同，設(shè)定相應(yīng)的權(quán)值分別對(duì)應(yīng)為u₁、u₂、u₃、u₄。因此可以得到控制器負(fù)載的計(jì)算公式為：

    (2)交換機(jī)負(fù)載的測(cè)量

    基于分布式SDN多域部署將整個(gè)網(wǎng)絡(luò)劃分為多個(gè)SDN子域，利用圖論的知識(shí)，設(shè)網(wǎng)絡(luò)拓?fù)錇镚(V，E)，其中，V代表網(wǎng)絡(luò)中交換機(jī)，E代表交換機(jī)之間的鏈路。將網(wǎng)絡(luò)劃分為N個(gè)子域，各個(gè)子域可表示為S_i(W_i，L_i)，其中，W_i表示子域S_i中的交換機(jī)，L_i表示S_i中的鏈路，有：

    定義 交換機(jī)負(fù)載度。交換機(jī)向控制器請(qǐng)求的Packet_In 的事件數(shù)定義為交換機(jī)的負(fù)載度，設(shè)為f_k。

2.2 控制器過(guò)載判定

    由于交換機(jī)流量在時(shí)間和空間上的波動(dòng)性，有可能導(dǎo)致各SDN子域控制器負(fù)載不均衡，因此本文設(shè)計(jì)了一種控制器過(guò)載的動(dòng)態(tài)判定機(jī)制。設(shè)置動(dòng)態(tài)門(mén)限L_A，子域S_i中控制器的負(fù)載值為C_i，判定過(guò)載門(mén)限值設(shè)為ε，則L_A如式(7)所示：

2.3 選擇與遷移策略

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

2.3.1 遷出域和遷入域選擇

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

    在遷出域的相鄰子域中，將具有最小目標(biāo)函數(shù)Q_min所在的子域設(shè)為遷入域，記為S_l。本文采用自適應(yīng)遺傳算法來(lái)求取目標(biāo)函數(shù)的最小值Q_min。

    自適應(yīng)遺傳算法中的要素進(jìn)行如下設(shè)定：

    (1)編碼設(shè)計(jì)

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

    (2)適應(yīng)度函數(shù)

    適應(yīng)度函數(shù)是對(duì)遺傳算法中解的好壞進(jìn)行度量的一種標(biāo)準(zhǔn)，在這里選取目標(biāo)函數(shù)Q作為該算法的適應(yīng)度函數(shù)，根據(jù)適應(yīng)度函數(shù)計(jì)算個(gè)體的適應(yīng)度。

    (3)交叉和變異

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

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

2.3.2 交換機(jī)自適應(yīng)遷移策略

    基于算法1得到整個(gè)網(wǎng)絡(luò)中所要遷入和遷出域，然后計(jì)算出遷入和遷出的兩個(gè)SDN子域的相對(duì)平均負(fù)載度，得到兩個(gè)SDN子域的遷移率。根據(jù)遷移率選擇一定數(shù)目的交換機(jī)，使得遷出域里負(fù)載度高的交換機(jī)遷移到遷入域內(nèi)，并加入存活期和淘汰機(jī)制，防止在遷移過(guò)程中有多個(gè)遷出域?qū)?yīng)一個(gè)遷入域時(shí)，遷入域內(nèi)有過(guò)多的交換機(jī)遷入，造成該遷入域負(fù)載驟增，產(chǎn)生二次遷移問(wèn)題，平衡了各SDN子域內(nèi)交換機(jī)的數(shù)量。

    (1)遷移率的調(diào)整

    遷移率是對(duì)SDN子域的遷入和遷出能力的定量描述，通過(guò)遷移率的比較與計(jì)算可以得出能夠遷入和遷出交換機(jī)的最佳數(shù)量。

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

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

    本文設(shè)計(jì)了一種基于存活期和淘汰機(jī)制的交換機(jī)自適應(yīng)遷移算法，即對(duì)參與遷移的交換機(jī)計(jì)算其存活期，若遷入個(gè)體年齡大于它的存活期就要被淘汰，不再參與遷移過(guò)程。

    存活期基于以下兩個(gè)原則：①負(fù)載度低的交換機(jī)的存活期大于負(fù)載度高的交換機(jī)的存活期；②當(dāng)某個(gè)SDN子域的交換機(jī)規(guī)模過(guò)大時(shí)不再接收新的交換機(jī)。

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

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

    算法2：交換機(jī)自適應(yīng)遷移算法

3 性能評(píng)估

    本文應(yīng)用基于Ryu的分布式SDN控制器^[8]，在此基礎(chǔ)上添加了收集與測(cè)量模塊、評(píng)估決策模塊和存儲(chǔ)模塊，并編寫(xiě)了遷移模塊來(lái)負(fù)責(zé)整個(gè)域內(nèi)交換機(jī)的遷移。運(yùn)用Cbench^[9]軟件，使用Mininet^[10]來(lái)模擬整個(gè)網(wǎng)絡(luò)拓?fù)洌ㄟ^(guò)模擬一定數(shù)量的交換機(jī)連接到控制器，發(fā)送Packet-In消息，并等待控制器下發(fā)flow-mods消息來(lái)衡量控制器的性能。

    模擬一個(gè)具有5個(gè)控制器和100個(gè)交換機(jī)的網(wǎng)絡(luò)拓?fù)洌瑢⒄麄€(gè)網(wǎng)絡(luò)劃分為5個(gè)SDN子域，每一個(gè)子域內(nèi)各部署一個(gè)控制器，使用Mininet來(lái)模擬整個(gè)網(wǎng)絡(luò)拓?fù)洹Ｊ紫葹榱苏f(shuō)明本文所述遷移機(jī)制的有效性和均衡性，采用模擬主機(jī)在網(wǎng)絡(luò)中進(jìn)行發(fā)送數(shù)據(jù)包，在交換機(jī)上產(chǎn)生大量的流量負(fù)載，將本文所采用的交換機(jī)自適應(yīng)遷移策略(Adaptive Migration Policy，AMP)、ElastiCon^[3]提出的就近遷移策略(Nearest Migration Policy，NMP)和隨機(jī)遷移策略(Random Migration Policy，RMP)進(jìn)行對(duì)比。控制器負(fù)載率代表控制器所承受的負(fù)載與可承受最大負(fù)載的比值，如圖3所示，對(duì)比3種策略下控制器負(fù)載率隨時(shí)間的變化。

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

    如圖4所示，在前60 s內(nèi)，由于交換機(jī)的遷出，遷出域控制器的負(fù)載基本上是呈現(xiàn)明顯的下降趨勢(shì)，且遷入域由于有部分負(fù)載度高的交換機(jī)從遷出域中遷移過(guò)來(lái)，因此遷入域控制器的負(fù)載有一定程度的上升；在60 s之后，兩個(gè)域內(nèi)的控制器的負(fù)載基本處于均衡狀態(tài)，由數(shù)據(jù)統(tǒng)計(jì)可以看出，遷出域控制器的初始負(fù)載值是設(shè)定為1 400 Request/s，遷入域控制器的初始負(fù)載值設(shè)定為800 Request/s，經(jīng)過(guò)遷移之后，遷出域控制器負(fù)載值變?yōu)? 133 Request/s，相對(duì)于初始值降低了19.1%，同時(shí)遷入域控制器負(fù)載值變?yōu)闉? 041 Request/s，都低于控制器過(guò)載判定門(mén)限值1 300 Request/s，遷出域和遷入域的負(fù)載得到了很好的均衡。

4 結(jié)論

    本文針對(duì)SDN多域部署下各個(gè)子域控制器之間的負(fù)載不均衡問(wèn)題，設(shè)計(jì)了基于自適應(yīng)遺傳算法的遷入、遷出域選擇機(jī)制，根據(jù)遷移率，存活期和淘汰機(jī)制在遷出域中選擇一定數(shù)目的交換機(jī)遷移到遷入域中，實(shí)現(xiàn)了各SDN子域控制器的負(fù)載均衡和交換機(jī)在各子域內(nèi)的均衡部署。

參考文獻(xiàn)

[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，F(xiàn)ANG 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ìn)的自適應(yīng)遺傳算法及其在作業(yè)車間調(diào)度中的應(yīng)用[J].大連交通大學(xué)學(xué)報(bào)，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，F(xiàn)inland：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.

作者信息:

周  寧，胡  濤，胡宇翔，汪斌強(qiáng)

(中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)，河南 鄭州450002)