SDN中基于動態(tài)遷移優(yōu)化的控制器負(fù)載均衡算法

朱國暉，史思潮，翟鵬宇

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

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

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

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

1 相關(guān)研究

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

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

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

(1)

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

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

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

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

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

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

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

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

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

2 DMOLB算法設(shè)計

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

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

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

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

(2)

(3)

(4)

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

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

(5)

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

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

(6)

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

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

(7)

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

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

(8)

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

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

(9)

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

(10)

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

2.2 選擇遷移域階段

一般對于遷入域的選取只考慮負(fù)載情況，負(fù)載最小的選為遷入域。一是考慮遷入域控制器的負(fù)載是否為最小；二是考慮遷入域中交換機和控制器的距離是否較小，因為距離最近，時延則最小?？刂破鞯呢?fù)載綜合計算公式為

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

(11)

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

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

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

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

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

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

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

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

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

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

(12)

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

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

(13)

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

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

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

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

步驟2計算遷移交互機的有效期。

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

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

3 仿真結(jié)果分析

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

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

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

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

3.2 仿真結(jié)果分析

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

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

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

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

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

圖5 交換機遷移通信開銷

由圖5可以看出，DMOLB算法與LILB、SCLB算法相比，交換機遷移通信開銷降低了38%和7.8%。

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

圖6 交換機與控制器之間的傳輸時延

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

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

圖7 控制器資源利用率

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

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

4 結(jié)語

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