朱國(guó)暉，史思潮，翟鵬宇

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)作為一種新型的網(wǎng)絡(luò)架構(gòu)[1]，實(shí)現(xiàn)了控制平面和轉(zhuǎn)發(fā)平面分離，通過(guò)控制器管理整個(gè)網(wǎng)絡(luò)，解決了傳統(tǒng)網(wǎng)絡(luò)僵化的問(wèn)題。隨著大數(shù)據(jù)、云計(jì)算等網(wǎng)絡(luò)技術(shù)的發(fā)展，現(xiàn)有的單控制器部署架構(gòu)不能滿足網(wǎng)絡(luò)的擴(kuò)展性和靈活性[2-3]。針對(duì)此問(wèn)題，研究者提出了將SDN網(wǎng)絡(luò)劃分成多個(gè)獨(dú)立的子域，并且每個(gè)子域中都由一個(gè)主控制器控制，通過(guò)控制器多域解決網(wǎng)絡(luò)的擴(kuò)展性和靈活性問(wèn)題。但隨著網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，對(duì)流量的需求也急劇增加，流量的分布在時(shí)間和空間上存在極大的不確定性。當(dāng)網(wǎng)絡(luò)中某一時(shí)刻或者某一塊區(qū)域的流量出現(xiàn)激增或驟減的情況時(shí)，易導(dǎo)致控制器的負(fù)載不均衡問(wèn)題。

國(guó)內(nèi)外研究者針對(duì)控制器的負(fù)載不均衡問(wèn)題使用不同的策略、算法進(jìn)行了研究。文獻(xiàn)[4]中首次提出遷移交換機(jī)解決控制器負(fù)載不均衡問(wèn)題。在選擇遷入域時(shí)將交換機(jī)與控制器之間的時(shí)延作為選擇標(biāo)準(zhǔn)，分析了控制器部署在不同的位置對(duì)遷移交換機(jī)產(chǎn)生的影響。文獻(xiàn)[5]中提出多控制器負(fù)載均衡策略，主要研究了控制器之間通信產(chǎn)生的時(shí)延對(duì)網(wǎng)絡(luò)的影響，最終實(shí)現(xiàn)控制器負(fù)載均衡的效果。但是，沒(méi)有提前計(jì)算出遷移的交換機(jī)數(shù)量，當(dāng)發(fā)生多個(gè)交換機(jī)遷移可能會(huì)產(chǎn)生交換機(jī)沖突等問(wèn)題。文獻(xiàn)[6]在分布式SDN架構(gòu)中提出安全交換機(jī)遷移策略，在部署網(wǎng)絡(luò)之前提前計(jì)算出過(guò)載概率較大的控制器。當(dāng)網(wǎng)絡(luò)流量出現(xiàn)激增時(shí)，通過(guò)快速卸載過(guò)載概率較大的控制器實(shí)現(xiàn)控制器負(fù)載均衡，但在預(yù)測(cè)控制器負(fù)載時(shí)，增加了網(wǎng)絡(luò)通信的開(kāi)銷(xiāo)。文獻(xiàn)[7-8]提出的算法都是通過(guò)周期性的采集控制器和鏈路的流量情況，計(jì)算控制器的負(fù)載，降低了通信成本。文獻(xiàn)[9]中提出一種兩階段式的策略。將控制器的負(fù)載最大為遷出域，通過(guò)遺傳算法選出負(fù)載最小的控制器的子域作為遷入域，并給遷移的交換機(jī)規(guī)定合理的數(shù)量，避免了多個(gè)交換機(jī)在遷移過(guò)程中產(chǎn)生的沖突問(wèn)題。文獻(xiàn)[10]提出動(dòng)態(tài)交換機(jī)遷移策略。通過(guò)動(dòng)態(tài)信息采集(Dynamic Information Acquisition，DIA)算法動(dòng)態(tài)地采取控制器之間的信息，并判斷是否過(guò)載。再通過(guò)對(duì)遷入域和交換機(jī)選取算法的優(yōu)化，實(shí)現(xiàn)交換機(jī)的遷移，達(dá)到負(fù)載均衡的效果。文獻(xiàn)[11]中交換機(jī)遷移通過(guò)設(shè)置博弈論實(shí)現(xiàn)控制器負(fù)載均衡。博弈論是由過(guò)載控制器子域的鄰域組成，并綜合交換機(jī)遷移成本和時(shí)延問(wèn)題，通過(guò)粒子群算法選出目標(biāo)控制器，實(shí)現(xiàn)交換機(jī)遷移。

綜合分析以上研究，針對(duì)多個(gè)控制器負(fù)載不均衡問(wèn)題主要是通過(guò)遷移交換機(jī)解決，但當(dāng)網(wǎng)絡(luò)需要遷移多個(gè)交換機(jī)時(shí)，在遷移時(shí)又會(huì)產(chǎn)生沖突問(wèn)題，導(dǎo)致遷移交換機(jī)效率較低。為了解決控制器負(fù)載不均衡問(wèn)題，擬提出基于動(dòng)態(tài)遷移優(yōu)化(Dynamic Migration-Optimized Load Balancing，DMOLB)的控制器負(fù)載均衡算法。該算法針對(duì)多個(gè)控制器負(fù)載不均衡問(wèn)題，先計(jì)算出控制器的負(fù)載，并判斷出是否過(guò)載；再將過(guò)載的控制器所在的子域作為遷出域，選擇出負(fù)載較低且與遷移交換機(jī)最近的控制器所在的子域?yàn)檫w入域；最后，設(shè)置子域的遷移度和交換機(jī)有效期，完成交換機(jī)遷移。同時(shí)，通過(guò)與負(fù)載通告(Load Informing based Load Balancing，LILB)算法和階段式控制器負(fù)載均衡(Stage Controller Load Balancing，SCLB)算法相比，驗(yàn)證該算法的性能。

1 相關(guān)研究

在SDN網(wǎng)絡(luò)中，將網(wǎng)絡(luò)劃分為多個(gè)子域，每個(gè)子域中由一個(gè)控制器控制，并且各個(gè)子域之間通過(guò)物理鏈路進(jìn)行互聯(lián)。具體的SDN多域網(wǎng)絡(luò)拓?fù)鋱D如圖1所示。

圖1 SDN多域網(wǎng)絡(luò)拓?fù)鋱D

利用圖論理論，將整個(gè)網(wǎng)絡(luò)可以表示為有向圖圖G=(V,E)，V為所有節(jié)點(diǎn)的集合，E為所有鏈路的集合。將SDN網(wǎng)絡(luò)分成M個(gè)子域，每個(gè)子域都有一個(gè)控制器和多個(gè)交換機(jī)相連，當(dāng)M個(gè)子域中有M個(gè)控制器，表示為C={c1,c2,…,cM}，交換機(jī)的個(gè)數(shù)為N個(gè)，表示為S={s1,s2,…,sN}，交換機(jī)和控制器連接的方式為

(1)

在SDN網(wǎng)絡(luò)的模型中，控制器分為最高控制器和常規(guī)控制器，具體分層式SDN控制器負(fù)載均衡架構(gòu)如圖2所示。

圖2 分層式SDN控制器負(fù)載均衡架構(gòu)

最高控制器包括負(fù)載計(jì)算模塊、負(fù)載信息收集模塊即負(fù)載分析和決策模塊。負(fù)載信息收集模塊主要負(fù)責(zé)收集常規(guī)控制器的負(fù)載情況，并且將負(fù)載信息傳遞為分析和決策模塊，由此模塊分析并決定是否遷移交換機(jī)，并將最終決策下發(fā)給常規(guī)控制，由常規(guī)控制器執(zhí)行交換機(jī)遷移策略。

常規(guī)控制器主要負(fù)責(zé)計(jì)算控制器的負(fù)載，并將負(fù)載信息傳遞給最高控制器，通過(guò)最高控制下發(fā)決策實(shí)現(xiàn)交換機(jī)遷移。

分層式SDN控制器負(fù)載均衡算法具體過(guò)程包括以下4個(gè)步驟。

步驟1常規(guī)控制器通過(guò)固定的周期收集自身的負(fù)載情況，并判斷負(fù)載是否超過(guò)設(shè)定的閾值。如果超過(guò)，立即將過(guò)載信息傳遞給最高控制。

步驟2最高控制器收集到常規(guī)控制器的超載信息，并且會(huì)收集整個(gè)SDN網(wǎng)絡(luò)的常規(guī)控制器的負(fù)載信息，并計(jì)算整個(gè)網(wǎng)絡(luò)控制器的負(fù)載均值。通過(guò)遷移域的策略選出遷入、遷出域和遷移的交換機(jī)，并將遷移策略下發(fā)給常規(guī)控制器。

步驟3常規(guī)控制器接收到最高控制器發(fā)送的遷移策略，完成交換機(jī)的遷移。

步驟4常規(guī)控制器完成交換機(jī)的遷移任務(wù)，至此遷移完成后會(huì)出現(xiàn)新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

2 DMOLB算法設(shè)計(jì)

考慮到遷移通信開(kāi)銷(xiāo)和遷移沖突問(wèn)題，將基于DMOLB的控制器負(fù)載均衡算法分為控制器負(fù)載、選擇遷移域及設(shè)定遷移度和有效期等3個(gè)階段。

2.1 控制器負(fù)載階段

在分層式的SDN網(wǎng)絡(luò)中，控制器的負(fù)載主要包括待處理的Packet-in消息，不同子域之間控制器相互交流的通信開(kāi)銷(xiāo)，維護(hù)域內(nèi)所需要的流量和安裝流表代價(jià)等4個(gè)部分[12]。

1)待處理的Packet-in消息?？刂破髫?fù)載的主要來(lái)源為交換機(jī)向控制器發(fā)送的Packet-in消息數(shù)目[13]。SDN網(wǎng)絡(luò)中子域Gi所接收的Packet-in請(qǐng)求消息的數(shù)目、子域中交換機(jī)的平均請(qǐng)求度及M個(gè)子域中Gi相對(duì)于其他子域請(qǐng)求度的表達(dá)式分別為

(2)

(3)

(4)

式中：ni為子域中交換機(jī)的個(gè)數(shù)；rsk表示交換機(jī)sk向控制器發(fā)送請(qǐng)求的數(shù)量。

2)不同子域之間控制器相互交流的通信開(kāi)銷(xiāo)。每個(gè)子域間的控制器需要交流，控制器之間并不能將子域的請(qǐng)求全部都處理，因此會(huì)產(chǎn)生通信開(kāi)銷(xiāo)?？刂破鱟i與控制器ci產(chǎn)生的通信開(kāi)銷(xiāo)的表達(dá)式為

(5)

式中：dik表示控制器ci與交換機(jī)sk之間的跳數(shù)，如果控制器離交換機(jī)越遠(yuǎn)，則需要流量越多；λ為控制器中交換機(jī)的平均流量。

3)維護(hù)域內(nèi)所需要的流量。在每個(gè)子域中，控制器與交換機(jī)之間也產(chǎn)生通信需要定期維護(hù)和管理。子域內(nèi)控制器與交換機(jī)產(chǎn)生的通信成本的表達(dá)式為

(6)

式中，θ為控制器之間告知對(duì)方狀況的平均代價(jià)，當(dāng)θ<λ，表示控制器之間不能對(duì)子域之間的消息進(jìn)行處理。

4)安裝流表代價(jià)。當(dāng)交換機(jī)發(fā)送消息產(chǎn)生一個(gè)新的流時(shí)，發(fā)送到控制器，則控制器需要安裝一個(gè)新的流表項(xiàng)與之匹配。因此，會(huì)產(chǎn)生安裝代價(jià)。安裝流表項(xiàng)產(chǎn)生的代價(jià)的表達(dá)式為

(7)

式中，f表示Pack-in數(shù)據(jù)包的大小。

每個(gè)子域控制器的負(fù)載為L(zhǎng)ci，表示為在子域Gi中的ci控制器的負(fù)載，主要由上面4部分的加權(quán)和所得，其表達(dá)式為

(8)

式中，ω1～ω4表示對(duì)應(yīng)的權(quán)值。

將式(8)中權(quán)值和做歸一化處理，和為1，表達(dá)式為

(9)

并且在SDN網(wǎng)絡(luò)中每個(gè)子域中只能有一個(gè)控制器，表示為

(10)

通過(guò)式(8)求得加權(quán)和就可以計(jì)算出常規(guī)控制器的負(fù)載情況，并根據(jù)與設(shè)定的閾值作比較，判斷控制器是否過(guò)載。如果發(fā)生過(guò)載，則進(jìn)行遷移域選取階段。

2.2 選擇遷移域階段

一般對(duì)于遷入域的選取只考慮負(fù)載情況，負(fù)載最小的選為遷入域。一是考慮遷入域控制器的負(fù)載是否為最?。欢强紤]遷入域中交換機(jī)和控制器的距離是否較小，因?yàn)榫嚯x最近，時(shí)延則最小?？刂破鞯呢?fù)載綜合計(jì)算公式為

CT=μ1(Lt,maxPavg-Lt)-μ2R

(11)

式中：μ1,μ2參數(shù)為權(quán)值，權(quán)值和為1；Lt表示t時(shí)刻的負(fù)載；Lci表示控制器的負(fù)載值；Lci,max表示控制器負(fù)載最大值；pavg表示全網(wǎng)控制的平均負(fù)載情況；R為交換機(jī)到控制器之間的跳數(shù)。

將控制層的所有控制器負(fù)載情況計(jì)算出并降序排序，依次從高到低選取值高的作為遷入域，當(dāng)出現(xiàn)需要遷移多個(gè)交換機(jī)時(shí)，及時(shí)更新負(fù)載狀態(tài)。按照以上原則依次進(jìn)行交換機(jī)遷移。通過(guò)此階段選出的遷入域，可以減少交換機(jī)遷移的開(kāi)銷(xiāo)。

選擇遷移域階段的具體步驟如下。

步驟1計(jì)算出各子域的交換機(jī)平均請(qǐng)求數(shù)，并將平均請(qǐng)求數(shù)最大的子域選為遷出域。

步驟2在其他相鄰的子域中根據(jù)式(11)計(jì)算CT。

步驟3將CT值從大到小降次排序。

步驟4選擇CT值最大的為遷入域。

2.3 設(shè)定遷移度和有效期階段

通過(guò)選擇遷移域階段選出的遷移域，在此基礎(chǔ)上設(shè)定遷移度和有效期，實(shí)現(xiàn)交換機(jī)的遷移。

1)交換機(jī)的遷移度。計(jì)算需要將子域G0中遷移到子域G1中交換機(jī)的數(shù)量。交換機(jī)的遷移度的表達(dá)式為

(12)

2)交換機(jī)的有效期。交換機(jī)在遷移的過(guò)程中作為有用遷移交換機(jī)的周期數(shù)。交換機(jī)的有效期的表示式為

Y(sh)=Z(sh)-D(sh)

(13)

式中：Z(sh)表示為交換機(jī)在遷移過(guò)程中輪詢周期總數(shù)；D(sh)表示為目前的周期數(shù)。

通過(guò)此階段設(shè)定的遷移度和有效期，遷移度可以計(jì)算出遷移交換機(jī)的數(shù)量，然后選擇有效期內(nèi)的交換機(jī)遷移，控制器負(fù)載大于閾值時(shí)，重新選擇交換機(jī)。否則，交換機(jī)遷移結(jié)束。遷移度和有效期的設(shè)置可以避免交換機(jī)在遷移過(guò)程中產(chǎn)生沖突。

設(shè)定遷移度和有效期階段具體步驟如下。

步驟1計(jì)算遷入、遷出域的子域遷移度，確定交換機(jī)遷移數(shù)目。

步驟2計(jì)算遷移交互機(jī)的有效期。

步驟3選擇有效期內(nèi)的交換機(jī)進(jìn)行遷移。

步驟4判斷控制器是否過(guò)載，如果沒(méi)有過(guò)載，交換機(jī)遷移結(jié)束；如果過(guò)載，返回步驟3，重新選擇交換機(jī)遷移，創(chuàng)建新的SDN網(wǎng)路拓?fù)洹?/p>

3 仿真結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)平臺(tái)為Ubuntu 16.04系統(tǒng),控制器為Floodlight,在Mininet平臺(tái)搭建拓?fù)鋱D，包括1個(gè)最高控制器控制5常規(guī)控制器和11個(gè)交換機(jī)。具體的實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)鋱D如圖3所示。

圖3 網(wǎng)絡(luò)拓?fù)鋱D

參數(shù)設(shè)置類(lèi)比文獻(xiàn)[14]設(shè)置的每個(gè)子域中控制器的功能全部一樣，控制器的容量設(shè)為10 MB，每個(gè)交換機(jī)平均產(chǎn)生流的速率設(shè)為150 kB·s-1?？刂破髦袡?quán)值系數(shù)的比重設(shè)置為0.4∶0.2∶0.2∶0.2。控制器4的負(fù)載超過(guò)設(shè)定的閾值?？刂破?、控制器2、控制器3和控制器5的負(fù)載平穩(wěn)，在設(shè)定的閾值內(nèi),并在30 s的情況下加大控制器4的數(shù)據(jù)流，模擬實(shí)際出現(xiàn)負(fù)載激增的情況。

3.2 仿真結(jié)果分析

為了驗(yàn)證該算法的性能，在相同的實(shí)驗(yàn)環(huán)境下，通過(guò)與文獻(xiàn)[15]中LILB的算法和文獻(xiàn)[9]中基于遷移優(yōu)化的SCLB算法做比較，分別從交換機(jī)的通信開(kāi)銷(xiāo)、傳輸時(shí)延和控制器資源利用率等3個(gè)方面驗(yàn)證算法的性能。

1)控制器負(fù)載情況。根據(jù)網(wǎng)絡(luò)拓?fù)鋱D可以看出，最高控制器控制5個(gè)常規(guī)控制器，常規(guī)控制器的負(fù)載時(shí)刻發(fā)生變化，需要周期的計(jì)算常規(guī)控制器的負(fù)載并判斷是否過(guò)載。算法主要研究5個(gè)常規(guī)控制器負(fù)載變化情況，具體過(guò)程如圖4所示。

圖4 控制器負(fù)載情況

由圖4可以看出，在初始階段給每個(gè)控制器產(chǎn)生新的流，使控制器有負(fù)載，在30 s時(shí)增大控制器4的流，使控制器過(guò)載。通過(guò)控制器負(fù)載階段計(jì)算控制器的負(fù)載，再在選擇遷移域階段將控制器4作為遷出域。最后，將選擇遷移域階段選出的控制器1和控制器2作為遷入域。通過(guò)設(shè)定遷移度和有效期階段將選定的交換機(jī)遷移到該控制器下，實(shí)現(xiàn)了控制器的負(fù)載均衡。整個(gè)負(fù)載均衡過(guò)程持續(xù)了5 s，避免了產(chǎn)生控制器負(fù)載震蕩或者遷移效率低等問(wèn)題。

2)交換機(jī)遷移通信開(kāi)銷(xiāo)。在網(wǎng)絡(luò)中控制器與控制器之間和交換機(jī)與控制器之間都會(huì)產(chǎn)生通信開(kāi)銷(xiāo)，3種算法的通信開(kāi)銷(xiāo)對(duì)比具體如圖5所示。

圖5 交換機(jī)遷移通信開(kāi)銷(xiāo)

由圖5可以看出，DMOLB算法與LILB、SCLB算法相比，交換機(jī)遷移通信開(kāi)銷(xiāo)降低了38%和7.8%。

3)交換機(jī)與控制器之間的傳輸時(shí)延。在交換機(jī)遷移的過(guò)程中，交換機(jī)與控制器之間的傳輸時(shí)延隨Pack-in消息請(qǐng)求速率改變情況如圖6所示。

圖6 交換機(jī)與控制器之間的傳輸時(shí)延

由圖6可以看出，當(dāng)交換機(jī)的請(qǐng)求速率較小時(shí)，3個(gè)策略產(chǎn)生的傳輸時(shí)延基本一致。當(dāng)Packet-in消息的請(qǐng)求速率不斷增加時(shí)，LILB算法需要頻繁收集網(wǎng)絡(luò)信息，使得交換機(jī)和控制器的交互增多。因此，時(shí)延增加的比較明顯。SCLB算法通過(guò)給設(shè)置遷移交換機(jī)的數(shù)量，避免流量擁堵，傳輸時(shí)延增加較少。DMOLB算法通過(guò)交換機(jī)遷移設(shè)置有效時(shí)間，避免交換機(jī)遷移時(shí)產(chǎn)生沖突，并可以有序遷移。因此，傳輸時(shí)延效果比以上兩種算法較好。

4)控制器資源利用率?？刂破髻Y源利用率也是衡量算法性能的重要標(biāo)準(zhǔn)之一，3種算法的控制器資源利用率如圖7所示。

圖7 控制器資源利用率

由圖7可以看出，DMOLB算法和LILB、SCLB兩種算法相比，對(duì)控制器的資源利用率稍有提高。該算法基于在全網(wǎng)搜索遷移域，并能合理制定遷移交換機(jī)的數(shù)量，避免在遷移過(guò)程中產(chǎn)生沖突。因此，控制器的資源利用率有所提高。

該算法與LILB算法和SCLB算法相比，時(shí)延和交換機(jī)的開(kāi)銷(xiāo)有所降低，并且也提高了控制器的資源利用率。但是，在算法運(yùn)行時(shí)間方面有所增加，因?yàn)樵诳紤]遷入域的過(guò)程，不僅考慮了遷入域的負(fù)載，也將遷入域的距離考慮進(jìn)去。因此，增加了算法的時(shí)間復(fù)雜度。

4 結(jié)語(yǔ)

針對(duì)SDN網(wǎng)絡(luò)中多控制器負(fù)載不均衡問(wèn)題，提出了基于動(dòng)態(tài)遷移優(yōu)化的控制器負(fù)載均衡算法。該算法首先提出了具有最高控制器的分層式架構(gòu)，通過(guò)最高控制器控制常規(guī)控制器，減少了常規(guī)控制器之間的通信，降低了通信開(kāi)銷(xiāo)。然后，優(yōu)化了遷入域的選取標(biāo)準(zhǔn)，綜合考慮遷出交換機(jī)與遷入控制器的距離和遷入控制器的負(fù)載兩種因素，降低了遷移成本。該算法總共分為3個(gè)階段，控制器負(fù)載階段計(jì)算出控制器的負(fù)載，并將其作為目標(biāo)函數(shù)；選擇遷移域階段對(duì)遷移域選取標(biāo)準(zhǔn)進(jìn)行優(yōu)化，并選出遷入遷出域；設(shè)定遷移度和有效期階段對(duì)遷出域中的交換機(jī)設(shè)置遷移度和有效期，避免了交換機(jī)遷移產(chǎn)生沖突，最終實(shí)現(xiàn)多控制器負(fù)載均衡。實(shí)驗(yàn)仿真結(jié)果表明，驗(yàn)證該算法對(duì)于LILB算法與SCLB算法，降低了交換機(jī)遷移過(guò)程的通信開(kāi)銷(xiāo)和時(shí)延，提高了控制器的平均負(fù)載均衡率。