朱世珂，束永安

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230601)

基于軟件定義網(wǎng)絡(luò)的分層式控制器負(fù)載均衡機(jī)制

朱世珂*，束永安

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230601)

針對(duì)軟件定義網(wǎng)絡(luò)(SDN)多控制器負(fù)載均衡過(guò)程中控制器之間通信開(kāi)銷(xiāo)大以及控制器吞吐量低等問(wèn)題，提出一種分層式控制器負(fù)載均衡機(jī)制?；诜謱邮郊軜?gòu)，通過(guò)超級(jí)控制器與域控制器協(xié)作完成負(fù)載均衡，并采用預(yù)定義負(fù)載閾值以減少域控制器與超級(jí)控制器之間的消息交換開(kāi)銷(xiāo)；同時(shí)，該機(jī)制可以有效選擇出過(guò)載最重的域控制器，并從該過(guò)載域控制器所控制的交換機(jī)中選取多個(gè)符合遷移標(biāo)準(zhǔn)的交換機(jī)，將其同時(shí)分別遷移到多個(gè)綜合性能高的域控制器上，從而解決多控制器間負(fù)載不均衡問(wèn)題。實(shí)驗(yàn)結(jié)果表明，與層次式SDN控制器協(xié)同負(fù)載均衡方案(COLBAS)以及用于控制器負(fù)載均衡的動(dòng)態(tài)和自適應(yīng)算法(DALB)相比，所提機(jī)制系統(tǒng)的消息數(shù)量降低了約79個(gè)百分點(diǎn)，且該系統(tǒng)的吞吐量分別比DALB、COLBAS分別提高了約8.57%、52.01%。所提機(jī)制能夠有效降低通信開(kāi)銷(xiāo)，并提高系統(tǒng)吞吐量，有更好的負(fù)載均衡效果。

軟件定義網(wǎng)絡(luò)；分層式控制器；負(fù)載閾值；交換機(jī)遷移；負(fù)載均衡

0 引言

隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)已經(jīng)無(wú)法滿(mǎn)足人類(lèi)的需求，新的網(wǎng)絡(luò)架構(gòu)軟件定義網(wǎng)絡(luò)(Software Defined Network, SDN)[1]應(yīng)運(yùn)而生。

SDN的設(shè)計(jì)思想主要是將網(wǎng)絡(luò)的控制功能和轉(zhuǎn)發(fā)功能分離，使得控制平面能夠更有效地提供統(tǒng)一的網(wǎng)絡(luò)監(jiān)控能力。作為數(shù)據(jù)轉(zhuǎn)發(fā)控制的核心，控制平面表現(xiàn)出越來(lái)越重要的作用。當(dāng)網(wǎng)絡(luò)規(guī)模增大，控制器接收的流超出其最大負(fù)載時(shí)，控制器將無(wú)法繼續(xù)正常工作。目前，解決控制器負(fù)載不均衡問(wèn)題主要有以下兩種方法：一是通過(guò)為控制器配置多冗余容量來(lái)應(yīng)對(duì)大量突發(fā)流，但是這種方法會(huì)造成資源浪費(fèi)以及增加系統(tǒng)開(kāi)銷(xiāo)；二是增加控制器數(shù)量，但是多控制器可能會(huì)存在某一個(gè)或者某些控制器發(fā)生負(fù)載時(shí)，其他控制器卻處于不工作或輕負(fù)載的狀態(tài)，這種控制器之間負(fù)載的不均衡，會(huì)導(dǎo)致網(wǎng)絡(luò)性能的下降。

為了解決多控制器之間負(fù)載不均衡、控制器之間通信開(kāi)銷(xiāo)大以及系統(tǒng)吞吐量低等問(wèn)題，本文提出基于SDN的分層式控制器負(fù)載均衡機(jī)制，旨在提供一種兩層控制器架構(gòu)，通過(guò)頂層超級(jí)控制器選擇出要遷移的交換機(jī)以及將其遷移到目標(biāo)控制器上，以降低控制器之間的通信開(kāi)銷(xiāo)，提高系統(tǒng)吞吐量，達(dá)到更好的負(fù)載均衡效果。

1 相關(guān)研究

針對(duì)多控制器之間的負(fù)載不平衡問(wèn)題，文獻(xiàn)[2]提出一種用于控制器負(fù)載均衡的動(dòng)態(tài)和自適應(yīng)算法(Dynamic and Adaptive algorithm for controller Load Balancing, DALB)，文獻(xiàn)[3]提出一種基于多個(gè)分布式控制器的負(fù)載通知策略的負(fù)載平衡機(jī)制，這兩種方案均減少了由網(wǎng)絡(luò)傳輸引起的決策延遲；但是該策略周期性收集負(fù)載信息增加了控制器之間的通信開(kāi)銷(xiāo)。文獻(xiàn)[4]提出用于可擴(kuò)展SDN的多控制器的負(fù)載分配方案，實(shí)現(xiàn)了可擴(kuò)展；但并未考慮相鄰控制器也過(guò)載的情況。文獻(xiàn)[5]提出一種新穎的負(fù)載平衡策略,使用擴(kuò)展服務(wù)器動(dòng)態(tài)分配流量，緩解了負(fù)載，提高了吞吐量。文獻(xiàn)[6]提出一種用于SDN控制平面的分布式負(fù)載平衡算法，其目的是動(dòng)態(tài)平衡SDN控制器集群上的控制流量，從而最大限度地減少延遲、緩解負(fù)載，并提高整體集群吞吐量。上述方案都是基于單層控制器的負(fù)載均衡方案，雖然可以緩解控制器負(fù)載，但是無(wú)法高效解決各個(gè)控制器之間的負(fù)載平衡問(wèn)題，很難滿(mǎn)足大型網(wǎng)絡(luò)的需求。

針對(duì)單層控制器負(fù)載平衡時(shí)通信開(kāi)銷(xiāo)大、吞吐量低等問(wèn)題，文獻(xiàn)[7]提出了一種控制器協(xié)同負(fù)載平衡策略(COoperative Load BAlancing Scheme for hierarchical SDN controllers, COLBAS)，文獻(xiàn)[8]提出balanceflow概念，兩種方案均采用兩層控制器架構(gòu)，通過(guò)超級(jí)控制器與常規(guī)控制器協(xié)同完成負(fù)載均衡；但是常規(guī)控制器群需要周期性向超級(jí)控制器發(fā)送負(fù)載信息，增加了系統(tǒng)開(kāi)銷(xiāo)。類(lèi)似地，文獻(xiàn)[9]提出一種基于集群控制器的交換機(jī)遷移機(jī)制的動(dòng)態(tài)負(fù)載均衡方法，由于協(xié)調(diào)器節(jié)點(diǎn)周期性收集負(fù)載消息，同樣會(huì)增加系統(tǒng)開(kāi)銷(xiāo)。文獻(xiàn)[10]提出一種軟件定義網(wǎng)絡(luò)的分布式層次控制器平面，采用三層架構(gòu)，有效解決了可擴(kuò)展性和可靠性問(wèn)題；但其僅僅是描述了一種層次式架構(gòu)，并沒(méi)有具體描述如何解決控制器之間的負(fù)載問(wèn)題。文獻(xiàn)[11]提出一種SDN的動(dòng)態(tài)負(fù)載平衡架構(gòu)，超級(jí)控制器與分割成簇的常規(guī)控制器進(jìn)行通信，當(dāng)檢測(cè)到過(guò)載簇時(shí)，超級(jí)控制器將常規(guī)控制器分割成新簇，并更新常規(guī)控制器的簇矢量；但是，其僅僅是簡(jiǎn)單描繪了一種負(fù)載平衡架構(gòu)，并沒(méi)有驗(yàn)證這種架構(gòu)對(duì)于控制器負(fù)載平衡的可行性。文獻(xiàn)[12-15]的目標(biāo)均是規(guī)劃出流傳輸?shù)淖顑?yōu)路徑，但負(fù)載均衡時(shí)，每次可供選擇的路徑少，且流劃分粒度粗，很難達(dá)到最優(yōu)效果。以上方案在大型網(wǎng)絡(luò)中依然面臨著負(fù)載均衡過(guò)程中控制器之間通信開(kāi)銷(xiāo)大以及控制器吞吐量低等問(wèn)題。

2 系統(tǒng)模型

本文采用分層式控制平面架構(gòu)進(jìn)行負(fù)載均衡的研究，如圖1所示，分層式控制平面架構(gòu)分為三層：物理層、域控制器層、超級(jí)控制器層。底層是物理層，包含大量連接的OpenFlow交換機(jī)或路由器(本文默認(rèn)為OpenFlow交換機(jī))，其主要功能是負(fù)責(zé)數(shù)據(jù)的轉(zhuǎn)發(fā)；中間層是域控制器層，由若干域控制器組成，每個(gè)域控制器控制一個(gè)域，每個(gè)域包含若干交換機(jī)，其主要功能包括處理交換機(jī)的流轉(zhuǎn)發(fā)請(qǐng)求、向底層交換機(jī)下發(fā)轉(zhuǎn)發(fā)規(guī)則，并將其發(fā)送到超級(jí)控制器層等；頂層是超級(jí)控制器層，超級(jí)控制器層將域控制器視為設(shè)備，為域控制器提供全局網(wǎng)絡(luò)視圖，并制定相應(yīng)的全局策略下發(fā)到域控制器。超級(jí)控制器層包括兩個(gè)超級(jí)控制器：一個(gè)保持活動(dòng)狀態(tài)，另一個(gè)處于待機(jī)狀態(tài)，兩個(gè)超級(jí)控制器之間采用熱備份策略[16],使得活動(dòng)狀態(tài)下的超級(jí)控制器在發(fā)生故障或者過(guò)載的情況下，保證冗余并保持網(wǎng)絡(luò)可用于實(shí)時(shí)處理，因此該程序可以將恢復(fù)時(shí)間調(diào)整為最小的恢復(fù)時(shí)間。當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，頂層的超級(jí)控制器會(huì)處理大量信息，容易造成網(wǎng)絡(luò)過(guò)載，此時(shí)，應(yīng)保持待機(jī)狀態(tài)的超級(jí)控制器被激活，由于超級(jí)控制器之間可以通過(guò)分布式協(xié)議同步全局抽象網(wǎng)絡(luò)視圖，所以待機(jī)狀態(tài)的超級(jí)控制器被激活后，可以很快接收過(guò)載超級(jí)控制器下的負(fù)載較大的域控制器，從而達(dá)到負(fù)載平衡的效果。而且超級(jí)控制器之間采用文獻(xiàn)[16]中的熱備份策略進(jìn)行數(shù)據(jù)同步，該策略大大降低了超級(jí)控制器之間的通信開(kāi)銷(xiāo)。

圖1 分層式控制平面架構(gòu)Fig. 1 Hierarchical control plane architeture

3 分層式控制器負(fù)載均衡機(jī)制

交換機(jī)可以同時(shí)連接多個(gè)域控制器，但其中只有一個(gè)是master控制器，其他都是slave控制器。每個(gè)域控制器管理SDN網(wǎng)絡(luò)的一個(gè)域，而且每個(gè)域控制器中都包含兩個(gè)組件：1)負(fù)載測(cè)量組件，負(fù)責(zé)收集本控制器的負(fù)載信息，判斷域控制器的負(fù)載是否超過(guò)閾值；2)負(fù)載通知組件，負(fù)責(zé)將本控制器的負(fù)載信息發(fā)送給超級(jí)控制器。

超級(jí)控制器中包含三個(gè)組件：1)負(fù)載收集組件，負(fù)責(zé)匯總所有域控制器的負(fù)載信息；2)平衡決策組件，負(fù)責(zé)進(jìn)行負(fù)載平衡決策；3)交換機(jī)遷移組件，負(fù)責(zé)遷移所選取的交換機(jī)來(lái)平衡控制器之間的負(fù)載。

本文的負(fù)載均衡機(jī)制的基本思路如下：首先，域控制器周期性測(cè)量自身的負(fù)載信息，并檢查域控制器的負(fù)載是否超過(guò)預(yù)設(shè)的負(fù)載閾值，如果超過(guò)負(fù)載閾值，超級(jí)控制器向其他域控制器發(fā)送負(fù)載狀態(tài)請(qǐng)求，其他域控制器將當(dāng)前的負(fù)載狀態(tài)發(fā)送給超級(jí)控制器；然后超級(jí)控制器中的平衡決策組件進(jìn)行遷移決策，完成遷移后，所有的域控制器更新自身的負(fù)載信息。更新超級(jí)控制器上域控制器負(fù)載狀態(tài)的過(guò)程如圖2所示。

圖2 更新超級(jí)控制器上域控制器負(fù)載狀態(tài)的步驟Fig. 2 Steps for updating load status of domain controllers on a super controller

接下來(lái)詳細(xì)介紹超級(jí)控制器中的負(fù)載收集組件、平衡決策組件和交換機(jī)遷移組件，以及域控制器中的負(fù)載測(cè)量組件和負(fù)載通知組件。

3.1 負(fù)載測(cè)量組件

負(fù)載測(cè)量組件在每個(gè)域控制器上運(yùn)行，用來(lái)周期性測(cè)量域控制器的負(fù)載信息，包括流表?xiàng)l目數(shù)(F)、交換機(jī)的平均消息到達(dá)速率(I)以及每個(gè)交換機(jī)與域控制器交互的往返時(shí)間(R)。SDN控制器的負(fù)載由許多因素組成，如處理PACKET_IN事件、安裝流條目等。在不同的情況下，這些因素的比例差異很大。但是PACKET_IN事件的處理通常被認(rèn)為是總體負(fù)載中最重要的部分。因此，計(jì)算PACKET_IN消息的平均到達(dá)速率來(lái)表示域控制器的負(fù)載。

3.2 負(fù)載通知組件

為了作出正確的負(fù)載平衡策略，域控制器可以周期性地向超級(jí)控制器發(fā)送自身的負(fù)載信息，這樣可以減少?zèng)Q策延遲，但是增加了通信開(kāi)銷(xiāo)。為了解決上述問(wèn)題，為每個(gè)域控制器定義一個(gè)負(fù)載閾值T，表示消息的到達(dá)速率為每秒T個(gè)消息，負(fù)載閾值根據(jù)每個(gè)域控制器自身的性能決定。當(dāng)域控制器的當(dāng)前負(fù)載值L超過(guò)負(fù)載閾值T時(shí)，才會(huì)將其負(fù)載信息發(fā)送給超級(jí)控制器,這樣可以避免周期性發(fā)送負(fù)載信息所帶來(lái)的高通信開(kāi)銷(xiāo)。

3.3 負(fù)載收集組件

負(fù)載收集組件運(yùn)行在超級(jí)控制器上，其負(fù)責(zé)收集域控制器發(fā)送的負(fù)載信息。負(fù)載收集組件收到過(guò)載域控制器的負(fù)載消息后，向過(guò)載域控制器發(fā)送確認(rèn)消息，并向其他域控制器發(fā)送負(fù)載狀態(tài)請(qǐng)求，域控制器收到超級(jí)控制器的負(fù)載狀態(tài)請(qǐng)求后，向超級(jí)控制器發(fā)送自身負(fù)載狀態(tài)，然后超級(jí)控制器將收集到的所有域控制器的負(fù)載信息匯總。

3.4 平衡決策組件

平衡決策組件首先要判斷過(guò)載域控制器是否是所有域控制器中過(guò)載最重的控制器，然后決定選擇哪個(gè)或哪些交換機(jī)進(jìn)行遷移，并選擇哪個(gè)或哪些域控制器作為目標(biāo)域控制器來(lái)接收所選擇的交換機(jī)。

3.4.1 最重過(guò)載域控制器的選擇

在負(fù)載均衡過(guò)程中，有一個(gè)問(wèn)題是不可避免的，即如果兩個(gè)或者多個(gè)域控制器的負(fù)載同時(shí)超過(guò)其負(fù)載閾值，將導(dǎo)致它們同時(shí)進(jìn)行遷移操作。如果它們同時(shí)將交換機(jī)遷移到相同的目標(biāo)域控制器，可能會(huì)導(dǎo)致目標(biāo)域控制器也過(guò)載。為了解決上述問(wèn)題，本文提出了最重過(guò)載域控制器的概念，并根據(jù)式(1)選擇最重過(guò)載域控制器:

P=(LLoad-TLoad)/TLoad

(1)

其中：P表示過(guò)載域控制器的過(guò)載比例；LLoad表示過(guò)載域控制器的當(dāng)前負(fù)載值；TLoad表示過(guò)載域控制器的負(fù)載閾值。如果存在兩個(gè)或多個(gè)域控制器同時(shí)過(guò)載，則根據(jù)P值對(duì)過(guò)載域控制器進(jìn)行降序排列，優(yōu)先選取P值最大的過(guò)載域控制器作為最重過(guò)載域控制器，并根據(jù)P值從大到小依次對(duì)過(guò)載域控制器進(jìn)行遷移操作，即優(yōu)先處理P值最大的過(guò)載域控制器，完成遷移操作后，在剩余的過(guò)載域控制器中再一次選取P值最大的過(guò)載域控制器進(jìn)行遷移操作，直至負(fù)載平衡。如果它們的過(guò)載比例相同，采用以下約束公式：

(2)

(3)

3.4.2 交換機(jī)選擇

交換機(jī)的平均消息到達(dá)速率越大，帶給域控制器的負(fù)載越大。同時(shí)，交換機(jī)中的流表?xiàng)l目越多，域控制器所要管理的流表就越大，域控制器的負(fù)載也就越大。此外，交換機(jī)與域控制器交互的往返時(shí)間也是影響負(fù)載的重要因素。因此，如果域控制器過(guò)載，根據(jù)上述三個(gè)因素，采用式(4)選擇交換機(jī)進(jìn)行遷移:

HS=α*F+β*I+λ*R

(4)

其中：HS表示選擇遷移交換機(jī)的標(biāo)準(zhǔn)；α、β和λ表示權(quán)重系數(shù)，設(shè)置α、β和λ的值分別為0.1、0.8、0.1。如果域控制器過(guò)載，根據(jù)HS值對(duì)過(guò)載域控制器所控制的交換機(jī)進(jìn)行降序排列，并優(yōu)先選擇HS值最大的交換機(jī)進(jìn)行遷移。如果HS值最大的交換機(jī)可以將過(guò)載域控制器的負(fù)載降低到負(fù)載閾值以下，則只選擇該交換機(jī)進(jìn)行遷移；如果不是，則按照HS值降序排列的順序從大到小選取多個(gè)交換機(jī)一起遷移，直到滿(mǎn)足下列約束公式：

LMigrate≤TTarget-LTarget

(5)

LLoad-LMigrate

(6)

其中：LMigrate表示過(guò)載域控制器所要遷移的負(fù)載；TTarget表示目標(biāo)域控制器的負(fù)載閾值；LTarget表示目標(biāo)域控制器的當(dāng)前負(fù)載值。要確保過(guò)載域控制器所要遷移的負(fù)載不超過(guò)目標(biāo)域控制器的負(fù)載閾值與其當(dāng)前負(fù)載值的差，以及過(guò)載域控制器的當(dāng)前負(fù)載值與過(guò)載域控制器所要遷移的負(fù)載的差值要小于過(guò)載域控制器的負(fù)載閾值。

3.4.3 目標(biāo)域控制器的選擇

所要遷移的交換機(jī)與目標(biāo)域控制器之間交互的往返時(shí)間越大，遷移的效率就越低。因此，在選擇目標(biāo)域控制器時(shí)，綜合考慮域控制器的負(fù)載條件以及每個(gè)交換機(jī)與域控制器交互的往返時(shí)間，并根據(jù)式(7)來(lái)選擇目標(biāo)域控制器：

CTarget=μ1*(TTarget-LTarget)-μ2*R

(7)

其中：CTarget表示選擇目標(biāo)域控制器的標(biāo)準(zhǔn)；μ1、μ2表示權(quán)重系數(shù)，權(quán)重系數(shù)總和為1。根據(jù)CTarget值對(duì)所有的域控制器進(jìn)行降序排列，并優(yōu)先選擇CTarget值最大的域控制器作為目標(biāo)域控制器。如果需要遷移的交換機(jī)不止一個(gè)，則根據(jù)CTarget值從大到小依次選取與需要遷移的交換機(jī)個(gè)數(shù)一樣的目標(biāo)域控制器，并將選取的交換機(jī)按照HS值從大到小分別遷移到按照CTarget值從大到小排列的目標(biāo)域控制器上，保證每個(gè)目標(biāo)域控制器只接收一個(gè)遷移交換機(jī)，避免多個(gè)交換機(jī)遷移到一個(gè)目標(biāo)域控制器上的情況。同時(shí)，如果存在多個(gè)CTarget值一樣的域控制器，采用以下約束公式：

(8)

(9)

ri=(LMigrate+L(Bi))/T(Bi);i∈s

(10)

其中：Q表示目標(biāo)域控制器的負(fù)載均衡率；s表示CTarget值相同的域控制器的集合；T(Bi)表示域控制器Bi的負(fù)載閾值；r0表示域控制器的整體負(fù)載率；ri表示目標(biāo)域控制器接收遷移交換機(jī)后的負(fù)載率。當(dāng)存在多個(gè)CTarget值一樣時(shí)，優(yōu)先選取Q值最小的域控制器作為目標(biāo)域控制器。因?yàn)镼的值越小，系統(tǒng)整體負(fù)載平衡越好。

3.5 交換機(jī)遷移組件

當(dāng)超級(jí)控制器確定最重過(guò)載域控制器，并需要遷移多個(gè)交換機(jī)時(shí)，如果按照HS值從大到小依次將交換機(jī)遷移到同一個(gè)目標(biāo)域控制器上，不僅會(huì)大大增加目標(biāo)域控制器的負(fù)載，還會(huì)消耗大量時(shí)間，降低了整個(gè)系統(tǒng)的性能。因此，本文根據(jù)CTarget值對(duì)所有的域控制器進(jìn)行降序排列，并根據(jù)CTarget值從大到小依次選取與遷移交換機(jī)個(gè)數(shù)對(duì)應(yīng)的多個(gè)目標(biāo)域控制器，然后將選取的交換機(jī)按照HS值從大到小分別遷移到按照CTarget值從大到小排列的目標(biāo)域控制器上，保證每個(gè)目標(biāo)域控制器只接收一個(gè)遷移交換機(jī)，避免多個(gè)交換機(jī)遷移到一個(gè)目標(biāo)域控制器上的情況。

交換機(jī)遷移到目標(biāo)域控制器的過(guò)程如下：首先，最重過(guò)載域控制器通過(guò)controller-controller信道向目標(biāo)域控制器發(fā)送交換機(jī)遷移請(qǐng)求消息來(lái)觸發(fā)交換機(jī)遷移；然后目標(biāo)域控制器向所要遷移的交換機(jī)發(fā)送一個(gè)Role-Request消息，通知交換機(jī)它的角色更改為equal，目標(biāo)域控制器收到交換機(jī)發(fā)送的Role-Reply消息后，通知過(guò)載域控制器已經(jīng)完成角色更改。目標(biāo)域控制器轉(zhuǎn)變成equal后，也可以從交換機(jī)接收異步消息，但是不對(duì)其作處理。由于過(guò)載域控制器可能有很多即將處理的消息，因此過(guò)載域控制器繼續(xù)與交換機(jī)進(jìn)行通信，完成未完成的工作，直到交換機(jī)向目標(biāo)域控制器發(fā)送“終止遷移”。收到“終止遷移”消息后，目標(biāo)域控制器向交換機(jī)發(fā)送Role-Request消息使自己變成master域控制器，過(guò)載域控制器變成slave控制器，至此交換機(jī)遷移完成。

3.6 分層式控制器負(fù)載均衡機(jī)制描述

分層式控制器負(fù)載均衡機(jī)制的具體過(guò)程如下：

步驟1 測(cè)量組件測(cè)量F、I以及R的值。

步驟2 如果域控制器的當(dāng)前負(fù)載值L大于負(fù)載閾值T，則表示該域控制器為過(guò)載域控制器。負(fù)載通知組件就會(huì)將該過(guò)載域控制器的負(fù)載信息發(fā)送給超級(jí)控制器。

步驟3 超級(jí)控制器的負(fù)載收集組件匯總所有域控制器的負(fù)載信息。

步驟4 如果同時(shí)存在多個(gè)過(guò)載域控制器，則根據(jù)式(1)選取P值最大的過(guò)載域控制器作為要遷移的過(guò)載域控制器；如果存在多個(gè)P值相同的過(guò)載域控制器，則根據(jù)式(3)選取θ值最大的過(guò)載域控制器進(jìn)行遷移操作。

步驟5 根據(jù)式(4)對(duì)HS值進(jìn)行降序排列，并從大到小選取一個(gè)或多個(gè)交換機(jī)作為遷移交換機(jī)，選取的交換機(jī)個(gè)數(shù)由式(5)～(6)決定，直到選取的交換機(jī)個(gè)數(shù)滿(mǎn)足式(5)～(6)的約束條件。

步驟6 根據(jù)式(7)，按照CTarget值從大到小依次選取與需要遷移的交換機(jī)個(gè)數(shù)一樣的目標(biāo)域控制器，并將選取的交換機(jī)按照HS值從大到小分別遷移到選取的目標(biāo)域控制器上；若存在多個(gè)CTarget值一樣的域控制器，則選取使得式(8)的值最小的域控制器作為目標(biāo)域控制器。

步驟7 利用交換機(jī)遷移組件進(jìn)行遷移操作。

步驟8 更新相應(yīng)控制器上的負(fù)載狀態(tài)。

4 仿真實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

在版本為12.04的64位Ubuntu虛擬機(jī)下，采用mininet進(jìn)行仿真實(shí)驗(yàn)。超級(jí)控制器與域控制器均使用Floodlight控制器，交換機(jī)采用OpenFlow交換機(jī)。為了評(píng)估控制器的性能，使用Cbench軟件。Cbench是一款性能測(cè)量工具，專(zhuān)為基于OpenFlow控制器而設(shè)計(jì)，它可以模擬OpenFlow交換機(jī)的數(shù)據(jù)包請(qǐng)求。

4.2 實(shí)驗(yàn)評(píng)估

本文采用圖1所示的層次式控制器平面架構(gòu)進(jìn)行實(shí)驗(yàn)，并通過(guò)測(cè)量三個(gè)性能指標(biāo)(通信開(kāi)銷(xiāo)、負(fù)載均衡效果以及吞吐量)進(jìn)行實(shí)驗(yàn)分析。為了驗(yàn)證本文所提機(jī)制能夠有效地權(quán)衡負(fù)載均衡度和遷移交換機(jī)的通信開(kāi)銷(xiāo)，將其控制器協(xié)作負(fù)載均衡方案(COLBAS)[7]、動(dòng)態(tài)和自適應(yīng)算法(DALB)[2]進(jìn)行實(shí)驗(yàn)對(duì)比。其中，COLBAS是通過(guò)底層控制平面周期性向頂層控制器發(fā)送負(fù)載信息，引起高通信開(kāi)銷(xiāo)，且系統(tǒng)吞吐量低；DALB是控制器之間周期性互相收集負(fù)載信息，同樣引起高通信開(kāi)銷(xiāo)。

4.2.1 通信開(kāi)銷(xiāo)

為了測(cè)量本文所提出的方法在通信開(kāi)銷(xiāo)方面的效率，將提出的方法中交換負(fù)載狀態(tài)所需要的消息數(shù)量與COLBAS、DALB進(jìn)行比較。本文假設(shè)域控制器層有n個(gè)域控制器，COLBAS和DALB均需要n(n-1)個(gè)消息來(lái)交換控制器之間的負(fù)載狀態(tài)，因?yàn)樗鼈冃枰ハ嗍占?fù)載狀態(tài)；而本文所提的方案中，超級(jí)控制器與域控制器之間只需要2n個(gè)交換消息?；谶@種理論評(píng)估，在不失一般性的情況下，分別在3至10個(gè)域控制器下進(jìn)行比較。如圖3所示，顯然，當(dāng)域控制器數(shù)量增加時(shí)，COLABAS和DALB中的域控制器之間需要相互收集負(fù)載狀態(tài)，且消息數(shù)量的基數(shù)增大，而本文所提方法只有在達(dá)到負(fù)載閾值時(shí)才會(huì)收集負(fù)載信息，這樣使得COLABAS和DALB的消息數(shù)量遠(yuǎn)遠(yuǎn)高于本文方法。例如，如果采用10個(gè)域控制器，本文所提方法的消息數(shù)量?jī)H僅是COLBAS和DALB消息數(shù)量的21%，所以相比COLBAS和DALB，本文方法的通信開(kāi)銷(xiāo)大大降低。

圖3 遷移消息的規(guī)范化數(shù)量對(duì)比Fig. 3 Comparison of normalized number for migration messages

4.2.2 負(fù)載均衡評(píng)估

采用5個(gè)域控制器進(jìn)行實(shí)驗(yàn)，并設(shè)置域控制器1、域控制器3、域控制器4和域控制器5的負(fù)載閾值為7 000，域控制器2的負(fù)載閾值為8 000，即域控制器1、域控制器3、域控制器4和域控制器5每秒最多可接收7 000個(gè)PACKET_IN消息，域控制器2每秒最多可接收8 000個(gè)PACKET_IN消息。由圖4可知，從0 s至40 s，5個(gè)域控制器的負(fù)載都是低于其負(fù)載閾值的。在45 s時(shí)，突然增加域控制器2的消息到達(dá)速率，使其負(fù)載超過(guò)負(fù)載閾值，并觸發(fā)負(fù)載均衡機(jī)制。此時(shí)，超級(jí)控制器將域控制器2中所選擇的兩個(gè)交換機(jī)分別遷移到域控制器1和域控制器3上，域控制器2的負(fù)載降低，域控制器1和域控制器3的負(fù)載上升，而域控制器4和域控制器5上的負(fù)載未發(fā)生變化，從而達(dá)到了負(fù)載均衡的效果。而且，從圖4中可以看出，負(fù)載均衡在5 s內(nèi)完成，這個(gè)完成時(shí)間是可以接受的。

圖4 負(fù)載平衡完成時(shí)間Fig. 4 Load balancing completion time

4.2.3 吞吐量比較

吞吐量指控制器每秒可處理的消息數(shù)量。采用4個(gè)域控制器(A,B,C,D)進(jìn)行實(shí)驗(yàn)，通過(guò)Chench工具測(cè)得域控制器處理PACKET-IN消息的最大速率為每秒10 154個(gè)。先向4個(gè)域控制器每秒注入5 000個(gè)數(shù)據(jù)包，運(yùn)行到20 s時(shí)，突然向域控制器A每秒注入15 000個(gè)數(shù)據(jù)包。分別利用COLBAS、DALB以及本文方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 不同算法吞吐量對(duì)比Fig. 5 Throughput comparison of different algorithms

從圖5可以看出，20 s時(shí)控制器的平均吞吐量急劇下降。這是由于域控制器A發(fā)生過(guò)載，導(dǎo)致PACKET_IN消息因緩沖區(qū)溢出而開(kāi)始丟失，造成吞吐量降低。域控制器過(guò)載會(huì)觸發(fā)負(fù)載均衡機(jī)制，域控制器A將部分負(fù)載遷移到其他域控制器上，從而提高了系統(tǒng)吞吐量，并使系統(tǒng)吞吐量趨于穩(wěn)定。顯然，與COLBAS、DALB相比，本文所提方法的系統(tǒng)吞吐量比DALB提高了約8.57%，比COLBAS提高了約52.01%，這是由于本文所提方法可以同時(shí)將過(guò)載域控制器的多個(gè)交換機(jī)分別遷移到多個(gè)對(duì)應(yīng)的目標(biāo)域控制器上，大大提高了系統(tǒng)的吞吐量。而DALB可以將交換機(jī)遷移到局部最優(yōu)域控制器上，但是需要收集大量負(fù)載信息，并且負(fù)載策略較復(fù)雜，降低了系統(tǒng)的總吞吐量，使得吞吐量低于本文方法。COLBAS需要周期性收集負(fù)載信息，負(fù)載策略更為復(fù)雜，所以其系統(tǒng)總吞吐量低于COLBAS和本文方法。

5 結(jié)語(yǔ)

針對(duì)SDN多控制器中存在的負(fù)載不均衡等問(wèn)題，本文提出一種分層式控制器負(fù)載均衡機(jī)制。該機(jī)制以降低通信開(kāi)銷(xiāo)、提高系統(tǒng)吞吐量、達(dá)到更好的負(fù)載均衡度為目標(biāo)，采用分層式架構(gòu)，通過(guò)超級(jí)控制器與域控制器協(xié)作完成負(fù)載均衡。仿真結(jié)果表明，該機(jī)制與COLBAS、DALB相比，能夠避免周期性收集負(fù)載信息，有效降低了通信開(kāi)銷(xiāo)，同時(shí)交換機(jī)遷移更合理，提高了系統(tǒng)吞吐量，而且負(fù)載均衡完成時(shí)間更少，達(dá)到了更好的負(fù)載均衡效果。下一步工作，將會(huì)研究如何降低超級(jí)控制器與域控制器之間因信息傳輸所造成的決策延遲。

References)

[1] 張朝昆,崔勇,唐翯祎,等.軟件定義網(wǎng)絡(luò)(SDN)研究進(jìn)展[J].軟件學(xué)報(bào),2015,26(1):62-81.(ZHANG C K, CUI Y, TANG H Y, et al. State-of-the-art survey on Software-Defined Networking (SDN) [J]. Journal of Software, 2015, 26(1): 62-81).

[2] ZHOU Y H, ZHU M F, XIAO L M, et al. A load balancing strategy for SDN controller based on distributed decision [C]// Proceedings of the 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ: IEEE, 2014: 851-856.

[3] YU J K, WANG Y, PEI K K, et al. A load balancing mechanism for multiple SDN controllers based on load informing strategy [C]// Proceedings of the 2016 18th Asia-Pacific Network Operations and Management Symposium. Piscataway, NJ: IEEE, 2016: 1-4.

[4] KYUNG Y, HONG K, NGUYEN T M, et al. A load distribution scheme over multiple controllers for scalable SDN [C]// Proceedings of the 2015 Seventh International Conference on Ubiquitous and Future Networks. Piscataway, NJ: IEEE, 2015: 808-810.

[5] SAIFULLAH M A, MOHAMED M A M. Open flow-based server load balancing using improved server health reports [C]// Proceedings of the 2016 2nd International Conference on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics. Piscataway, NJ: IEEE, 2016: 649-651.

[6] CIMORELLI F, PRISCOLI F D, PIETRABISSA A, et al. A distributed load balancing algorithm for the control plane in software defined networking [C]// Proceedings of the 2016 24th Mediterranean Conference on Control and Automation. Piscataway, NJ: IEEE, 2016: 1033-1040.

[7] SELVI H, GUR G, ALAGOZ F. Cooperative load balancing for hierarchical SDN controllers [C]// Proceedings of the 2016 IEEE 17th International Conference on High Performance Switching and Routing. Piscataway, NJ: IEEE, 2016: 100-105.

[8] HU Y N, WANG W D, GONG X Y, et al. BalanceFlow: controller load balancing for openFlow networks [C]// Proceedings of the 2012 IEEE 2nd International Conference on Cloud Computing and Intelligent Systems. Piscataway, NJ: IEEE, 2012: 780-785.

[9] LIANG C, KAWASHIMA R, MATSUO H. Scalable and crash-tolerant load balancing based on switch migration for multiple open flow controllers [C]// Proceedings of the 2014 Second International Symposium on Computing and Networking. Piscataway, NJ: IEEE, 2014: 171-177.

[10] BHOLE P D, PURI D D. Distributed hierarchical control plane of software defined networking [C]// Proceedings of the 2015 International Conference on Computational Intelligence and Communication Networks. Piscataway, NJ: IEEE, 2015: 516-522.

[11] SUFIEV H, HADDAD Y. A dynamic load balancing architecture for SDN [C]// Proceedings of the 2016 IEEE International Conference on the Science of Electrical Engineering. Piscataway, NJ: IEEE, 2016: 1-3.

[12] WANG X M, HUANG C H, HE K, et al. Virtual path assignment based on load balancing for SDNs [C]// Proceedings of the 2016 IEEE 22nd International Conference on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2016: 247-255.

[13] SCHEPPER T D, LATRE S, FAMAEY J. A transparent load balancing algorithm for heterogeneous local area networks [C]// Proceedings of the 2017 IFIP/IEEE International Symposium on Integrated Network Management. Piscataway, NJ: IEEE, 2017: 160-168.

[14] 曹儐,劉勰,孫奇.軟件定義網(wǎng)絡(luò)架構(gòu)下的動(dòng)態(tài)自適應(yīng)負(fù)載均衡策略研究[J].重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,27(4):460-465.(CAO B, LIU X, SUN Q. Dynamically adaptive load balancing strategy under the software defined network structure [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2015, 27(4): 460-465.)

[15] 曲樺,趙季紅,樊斌 ,等.軟件定義網(wǎng)絡(luò)中應(yīng)用蟻群優(yōu)化的負(fù)載均衡算法[J].北京郵電大學(xué)學(xué)報(bào),2017,40(3):51-55.(QU H, ZHAO J H, FAN B, et al. Ant colony optimization for load balance in software defined network [J]. Journal of Beijing University of Posts and Telecommunications, 2017, 40(3): 51-55.)

[16] PASHKOV V, SHALIMOV A, SMELIANSKY R. Controller failover for SDN enterprise networks [C]// Proceedings of the 2014 International Science and Technology Conference (Modern Networking Technologies). Piscataway, NJ: IEEE, 2014: 1-6.

This work is partially supported by Natural Science Foundation of Anhui Province (1408085MF125).

ZHUShike, born in 1992, M. S. candidate. His research interests include software defined network, load balancing.

SHUYongan, born in 1966, Ph. D., professor. His research interests include wireless network, software defined network, next-generation network architecture.

Loadbalancingmechanismforhierarchicalcontrollersbasedonsoftwaredefinednetwork

ZHU Shike*, SHU Yong’an

(CollegeofComputerScienceandTechnology,AnhuiUniversity,HefeiAnhui230601,China)

Aiming at the problems that the communication overhead between controllers is large and the controller throughput is low during the load balancing process of multi-controller in Software Defined Network (SDN), a hierarchical controller load balancing mechanism was proposed. Based on the hierarchical architecture, the load balancing was completed through the collaboration of super controller and domain controller, and the predefined load threshold was used to reduce the message exchange overhead between domain controller and super controller. At the same time, the most overloaded domain controller was effectively selected. A plurality of switches conforming to the migration standard were selected from the switches controlled by the most overload domain controller. Simultaneously the selected switches were respectively migrated to a plurality of domain controllers with high overall performance, which solving the problem of load imbalance among multiple controllers. The experimental results showed that, compared with the COoperative Load BAlancing Scheme for hierarchical SDN controllers (COLBAS) and the Dynamic and Adaptive algorithm for controller Load Balancing (DALB), the number of messages in the proposed mechanism system was reduced by about 79 percentage points, and the throughput of the proposed system was about 8.57% higher than DALB and 52.01% higher than COLBAS. The proposed mechanism can effectively reduce the communication overhead and improve the system throughput to achieve a better load balancing effect.

Software Defined Network (SDN); hierarchical controller; load threshold; switch migration; load balancing

2017- 06- 21;

2017- 08- 31。

安徽省自然科學(xué)基金資助項(xiàng)目(1408085MF125)。

朱世珂(1992—)，男，安徽淮北人，碩士研究生，主要研究方向：軟件定義網(wǎng)絡(luò)、負(fù)載均衡； 束永安(1966—)，男，安徽舒城人，教授，博士，主要研究方向：無(wú)線(xiàn)網(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、下一代網(wǎng)絡(luò)體系結(jié)構(gòu)。

1001- 9081(2017)12- 3351- 05

10.11772/j.issn.1001- 9081.2017.12.3351

(*通信作者電子郵箱1838182190@qq.com)

TP393

A