趙季紅,孫天驁,曲 樺,張 茵,翟凡妮

(1.西安郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,西安 710061; 2.西安交通大學(xué) 軟件學(xué)院,西安 710049)

0 概述

面對(duì)網(wǎng)絡(luò)流量的爆炸式增長(zhǎng)和新業(yè)務(wù)的快速發(fā)展,傳統(tǒng)網(wǎng)絡(luò)架構(gòu)已經(jīng)無(wú)法滿足日益增長(zhǎng)的網(wǎng)絡(luò)需求,出現(xiàn)了服務(wù)質(zhì)量和可擴(kuò)展性差、可靠性低等問(wèn)題[1]。在該背景下,軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)[2]技術(shù)應(yīng)運(yùn)而生。SDN是一種創(chuàng)新性的網(wǎng)絡(luò)架構(gòu),它通過(guò)開(kāi)放接口將傳統(tǒng)的網(wǎng)絡(luò)體系結(jié)構(gòu)解耦為數(shù)據(jù)平面、控制平面和應(yīng)用平面,在邏輯上實(shí)現(xiàn)了網(wǎng)絡(luò)的集中控制和管理[3-4],且SDN中的控制器不僅可以將控制信息下發(fā)至底層的數(shù)據(jù)平面執(zhí)行,還對(duì)整個(gè)網(wǎng)絡(luò)拓?fù)浜蜖顟B(tài)進(jìn)行實(shí)時(shí)維護(hù),為應(yīng)用平面提供可擴(kuò)展的編程接口。隨著SDN架構(gòu)的不斷推廣,數(shù)據(jù)平面的數(shù)據(jù)量和應(yīng)用平面的業(yè)務(wù)量逐漸增加,單一的控制器已無(wú)法及時(shí)處理大量的流量請(qǐng)求,因此研究SDN中的多控制器部署策略[5]非常必要。

近年來(lái),關(guān)于控制器部署問(wèn)題的研究分為兩類(lèi):一類(lèi)是考慮單一性能指標(biāo),通過(guò)優(yōu)化單目標(biāo)求解控制器位置。文獻(xiàn)[6]較先提出控制器部署問(wèn)題,定義了平均時(shí)延和最壞時(shí)延,并采用貪婪算法對(duì)控制器進(jìn)行部署。文獻(xiàn)[7]考慮到控制器負(fù)載,將控制器部署問(wèn)題建模為在整數(shù)線性規(guī)劃問(wèn)題中求解控制器的最小個(gè)數(shù)以及最優(yōu)位置。文獻(xiàn)[8]考慮了交換機(jī)和鏈路的故障概率,并提出可靠性指標(biāo)控制路徑損失預(yù)期率。文獻(xiàn)[9]為最小化交換機(jī)和相關(guān)控制器之間的傳輸時(shí)延,提出一種基于相似性傳播的改進(jìn)聚類(lèi)方法，該方法不預(yù)先指定控制器的個(gè)數(shù)和位置,而是根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)自適應(yīng)學(xué)習(xí)控制器的最佳個(gè)數(shù)和位置。文獻(xiàn)[10]提出改進(jìn)的I-K-means聚類(lèi)算法,利用網(wǎng)絡(luò)分區(qū)降低網(wǎng)絡(luò)中的質(zhì)心節(jié)點(diǎn)和關(guān)聯(lián)節(jié)點(diǎn)之間的最大時(shí)延,但是該算法考慮的目標(biāo)較為單一,不能適用于復(fù)雜的網(wǎng)絡(luò)環(huán)境。另一類(lèi)是考慮多種性能指標(biāo),將控制器部署問(wèn)題轉(zhuǎn)化為多目標(biāo)規(guī)劃問(wèn)題。文獻(xiàn)[11]定義了全局時(shí)延并將粒子群優(yōu)化算法用于解決控制器部署問(wèn)題。文獻(xiàn)[12]在Pareto最優(yōu)控制器部署框架下研究控制器的彈性部署,并考慮到控制器間傳播時(shí)延、控制器負(fù)載均衡、控制器故障以及網(wǎng)絡(luò)可靠性等多種性能指標(biāo),存在算法復(fù)雜度較高、不適用于大規(guī)模網(wǎng)絡(luò)的問(wèn)題。同時(shí),還有部分研究通過(guò)網(wǎng)絡(luò)劃分降低控制器對(duì)大型網(wǎng)絡(luò)管理的復(fù)雜度。如文獻(xiàn)[13]提出基于密度聚類(lèi)的控制器部署算法,該算法通過(guò)密度聚類(lèi)將網(wǎng)絡(luò)劃分成多個(gè)子網(wǎng)絡(luò),得到最佳控制器個(gè)數(shù)后對(duì)控制器進(jìn)行部署。文獻(xiàn)[14]基于改進(jìn)的標(biāo)簽傳播算法將網(wǎng)絡(luò)劃分成多個(gè)子域,并在子域中分別部署控制器,將平均時(shí)延、可靠性和控制器負(fù)載均衡納入約束條件以達(dá)到最優(yōu)部署。文獻(xiàn)[15]提出一種基于社區(qū)特征的控制器部署策略,先基于模塊度的遺傳算法對(duì)網(wǎng)絡(luò)進(jìn)行劃分,再通過(guò)協(xié)調(diào)控制器之間的傳播時(shí)延和控制器與交換機(jī)之間的控制時(shí)延來(lái)部署控制器。但是上述研究劃分的網(wǎng)絡(luò)結(jié)構(gòu)不合理,且網(wǎng)絡(luò)可靠性也不能得到保障。

針對(duì)以上研究方案中存在的問(wèn)題,結(jié)合改進(jìn)的Louvain社區(qū)檢測(cè)算法[16],本文提出一種SDN控制器部署策略。利用節(jié)點(diǎn)相似度重新定義鏈路權(quán)重,并計(jì)算社區(qū)模塊度,通過(guò)引入控制器負(fù)載差異度對(duì)整個(gè)網(wǎng)絡(luò)拓?fù)溥M(jìn)行劃分,獨(dú)立地根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)劃分合適的分區(qū),以提高網(wǎng)絡(luò)負(fù)載均衡。同時(shí)，本文還通過(guò)交換機(jī)到控制器間傳播時(shí)延、控制器間傳播時(shí)延、控制鏈路可靠性3個(gè)性能指標(biāo)對(duì)已經(jīng)劃分好的各個(gè)子域進(jìn)行域內(nèi)單控制器部署。

1 模型描述與建立

將大型SDN表示為一個(gè)無(wú)向圖G=(V,E)。其中,V表示網(wǎng)絡(luò)中交換機(jī)集合,V=(v1,v2,…,vn),n=|V|表示交換機(jī)個(gè)數(shù)。E表示網(wǎng)絡(luò)中交換機(jī)之間的鏈路集合,E=(e1,e2,…,em),m=|E|表示鏈路個(gè)數(shù),e(u,v)∈E表示交換機(jī)u和交換機(jī)v之間相連的鏈路。C表示控制器集合,C=(c1,c2,…,ck)。將網(wǎng)絡(luò)劃分成K個(gè)不相交的社區(qū),P表示劃分的社區(qū)集合,P=(p1,p2,…,pk),每個(gè)社區(qū)包含一個(gè)控制器和任意t(1≤t≤n)個(gè)交換機(jī),pj=(v1j,v2j,…,vtj,cj)。

定義1映射關(guān)系矩陣Xn×n表示控制器與交換機(jī)的映射關(guān)系,如式(1)所示,若交換機(jī)vi映射到控制器cj,則xi,j=1,否則為0。

(1)

定義2社區(qū)pj內(nèi)交換機(jī)到控制器的平均傳播時(shí)延Lpj-avg如式(2)所示:

(2)

其中,mind(vj,cj)表示交換機(jī)vj∈pj與其所屬控制器cj∈pj之間的最短路徑。

定義3交換機(jī)到控制器的總平均傳播時(shí)延Lsc-avg,其表示各個(gè)社區(qū)交換機(jī)到控制器平均時(shí)延之和,計(jì)算方法如式(3)所示:

(3)

定義4網(wǎng)絡(luò)的控制邏輯分布在多個(gè)控制器上,這些控制器需要同步以保持一致的全局狀態(tài),各個(gè)控制器之間的時(shí)延起重要作用,控制器間平均傳播時(shí)延Lcc-avg的計(jì)算方法如式(4)所示:

(4)

定義5控制平面總平均傳播時(shí)延?？刂破矫鏁r(shí)延包括交換機(jī)到控制器以及控制器間的傳播時(shí)延,因此將控制平面的總平均傳播時(shí)延表示為:

Ltotal=Lsc-avg+Lcc-avg

(5)

定義6控制器負(fù)載差異度?？刂破骺刂频慕粨Q機(jī)越多,控制器負(fù)載越大,將會(huì)導(dǎo)致負(fù)載資源不均衡,不同控制區(qū)域內(nèi)部的通信延遲情況不同,對(duì)網(wǎng)絡(luò)性能造成影響,嚴(yán)重情況下很可能導(dǎo)致網(wǎng)絡(luò)故障。因此為了防止控制器過(guò)載,分配給不同控制器的交換機(jī)數(shù)量應(yīng)該是均衡的。假設(shè)控制器控制一個(gè)交換機(jī)所需的流量為l(n),子網(wǎng)間的負(fù)載平衡狀況可由控制器負(fù)載最大差值來(lái)表示:

(6)

定義7控制路徑平均損失率?？刂坡窂蕉x為用于交換機(jī)與其控制器之間傳輸控制信息的鏈路,其實(shí)現(xiàn)方式主要有2種,一種是帶內(nèi)傳輸,即使用數(shù)據(jù)平面流量轉(zhuǎn)發(fā)的鏈路傳輸控制信息;另一種是帶外傳輸,即使用專用的鏈路來(lái)傳輸控制信息[17]。對(duì)于大規(guī)模網(wǎng)絡(luò),由于交換機(jī)數(shù)量多且控制器與交換機(jī)之間距離較遠(yuǎn),因此本文的控制鏈路選用帶內(nèi)傳輸方式對(duì)信息進(jìn)行傳輸。當(dāng)控制器、交換機(jī)、物理鏈路出現(xiàn)故障時(shí),都會(huì)促使控制鏈路失效,從而導(dǎo)致整個(gè)網(wǎng)絡(luò)癱瘓,因此控制器與交換機(jī)之間的控制鏈路越長(zhǎng),則控制鏈路出現(xiàn)的故障概率越大。控制路徑的平均損失率如式(7)所示:

(7)

其中,l表示物理網(wǎng)絡(luò)組件,包括控制器、交換機(jī)與物理鏈路。dl表示控制路徑,pl表示網(wǎng)絡(luò)組件l的故障率,mc表示控制路徑總數(shù)量,且mc=n?？刂坡窂狡骄鶕p失率δ越小,說(shuō)明方法的可靠性越高。

針對(duì)大規(guī)模SDN,優(yōu)化控制平面總平均傳播時(shí)延、控制器負(fù)載以及控制鏈路可靠性的目標(biāo)分別定義為:

minLtotal

(8)

s.t.β≤β′

(9)

δ≤R

(10)

其中,β′表示控制器負(fù)載最大差值的上限,R表示控制路徑平均損失率的最大值。

2 本文算法描述與分析

2.1 本文算法分析

Louvain算法是一種基于多層次(逐輪啟發(fā)式迭代)優(yōu)化模塊度的算法,該算法通過(guò)最大化每一層的目標(biāo)函數(shù)Q[18]來(lái)檢測(cè)最佳社區(qū)。模塊度Q是評(píng)判劃分社區(qū)結(jié)構(gòu)強(qiáng)度的方法,同時(shí)也是優(yōu)化后的目標(biāo)函數(shù)。它能夠刻畫(huà)發(fā)現(xiàn)的社區(qū)緊密程度,好的社區(qū)劃分結(jié)果要求社區(qū)內(nèi)節(jié)點(diǎn)相對(duì)緊密,社區(qū)外節(jié)點(diǎn)相對(duì)稀疏?；谀K度的社區(qū)發(fā)現(xiàn)算法都是以最大化模塊度Q為目標(biāo),模塊度Q的計(jì)算方法如式(11)所示:

(11)

將節(jié)點(diǎn)從其社區(qū)中移除并移動(dòng)到相鄰社區(qū)來(lái)評(píng)估模塊度Q的增益,模塊度增益如式(12)所示:

(12)

其中,ΔQu→p表示將節(jié)點(diǎn)u移動(dòng)到相鄰社區(qū)p的模塊度增益,wu→p表示社區(qū)p中與節(jié)點(diǎn)u相連的所有鏈路權(quán)重之和。

Louvain算法主要分為以下2個(gè)階段:

1)在第一階段,首先為每一個(gè)節(jié)點(diǎn)分配一個(gè)不同的社區(qū),社區(qū)數(shù)目與節(jié)點(diǎn)個(gè)數(shù)相同。其次對(duì)于每個(gè)節(jié)點(diǎn)vi,將vi從其社區(qū)中移除并將其移動(dòng)到相鄰社區(qū)pj中來(lái)評(píng)估模塊度增益ΔQ。接著,將節(jié)點(diǎn)vi移動(dòng)到模塊度增益最大的社區(qū)中,但前提是max ΔQ>0,否則節(jié)點(diǎn)vi保持原社區(qū)不變。最后,對(duì)所有的節(jié)點(diǎn)按順序重復(fù)此過(guò)程直至所有節(jié)點(diǎn)的社區(qū)不再發(fā)生變化。

2)第二階段的目的是建立一個(gè)新的網(wǎng)絡(luò),將第一階段生成的社區(qū)壓縮成一個(gè)新的節(jié)點(diǎn),新節(jié)點(diǎn)之間的鏈路權(quán)重由對(duì)應(yīng)2個(gè)社區(qū)中節(jié)點(diǎn)之間的鏈路權(quán)重之和表示。重復(fù)第一階段的步驟直至整個(gè)網(wǎng)絡(luò)的模塊度不再發(fā)生變化。Louvain算法步驟簡(jiǎn)單、復(fù)雜度較低,且計(jì)算速度快,因此適用于大型網(wǎng)絡(luò)。

本文提出一種改進(jìn)的Louvain社區(qū)部署策略(Louvain Community Placement Strategy,LCPS),用于解決大規(guī)模SDN下的多控制器部署問(wèn)題。該策略的目標(biāo)是縮短控制器與其隸屬交換機(jī)之間的平均時(shí)延和控制器間的平均時(shí)延,并提高控制器的負(fù)載以及控制鏈路的可靠性。LCPS由2種算法組成:算法1是利用改進(jìn)的Louvain算法對(duì)網(wǎng)絡(luò)社區(qū)進(jìn)行劃分,算法2是在已經(jīng)劃分好的社區(qū)中部署控制器。傳統(tǒng)的Louvain算法存在不足,如社區(qū)劃分效果依賴計(jì)算鏈路權(quán)重的方法,聚類(lèi)過(guò)程中沒(méi)有及時(shí)收斂而導(dǎo)致劃分的社區(qū)過(guò)大等問(wèn)題。針對(duì)該問(wèn)題,本文提出以下2種解決方法:

1)根據(jù)節(jié)點(diǎn)相似度重新定義鏈路權(quán)重的概念。在網(wǎng)絡(luò)中,節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的最短路徑越小,則這2個(gè)節(jié)點(diǎn)的相似度越高?；谧疃搪窂蕉x節(jié)點(diǎn)相似度函數(shù)sim(u,v)如式(13)所示:

(13)

傳統(tǒng)的社交網(wǎng)絡(luò)運(yùn)用Louvain算法劃分社區(qū)時(shí),2個(gè)節(jié)點(diǎn)之間的權(quán)重越大,這2個(gè)節(jié)點(diǎn)合并到同一個(gè)社區(qū)的可能性越大。將Louvain算法應(yīng)用到大規(guī)模SDN網(wǎng)絡(luò)下,節(jié)點(diǎn)間的相似度越高,則它們之間的聯(lián)系越緊密。為了最大化社區(qū)的緊密度,根據(jù)節(jié)點(diǎn)相似度定義相應(yīng)的鏈路權(quán)重函數(shù)w(u,v)如式(14)所示:

(14)

其中,d(u,v)表示節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的最短路徑。w(u,v)的取值范圍為[0,1],且其值越高,則節(jié)點(diǎn)u和節(jié)點(diǎn)v越容易合并到同一個(gè)社區(qū)。

2.2 算法步驟

2.2.1 網(wǎng)絡(luò)社區(qū)劃分算法

算法1的核心思想是利用改進(jìn)的Louvain算法實(shí)現(xiàn)網(wǎng)絡(luò)的均衡劃分。算法1的具體步驟為:

步驟1將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)看成一個(gè)獨(dú)立的社區(qū),初始社區(qū)數(shù)目與節(jié)點(diǎn)個(gè)數(shù)相同。

步驟3重復(fù)上述步驟,直至所有節(jié)點(diǎn)的所在社區(qū)不再發(fā)生變化。

步驟4對(duì)圖進(jìn)行重構(gòu),將所有在同一個(gè)社區(qū)的節(jié)點(diǎn)壓縮成一個(gè)新的節(jié)點(diǎn),社區(qū)內(nèi)節(jié)點(diǎn)之間的鏈路權(quán)重更新為新節(jié)點(diǎn)環(huán)的權(quán)重,社區(qū)間的鏈路權(quán)重更新為新節(jié)點(diǎn)間的鏈路權(quán)重。

步驟5重復(fù)步驟2,直至整個(gè)圖的總模塊度不再發(fā)生變化。

算法1的偽代碼為:

輸入網(wǎng)絡(luò)拓?fù)鋱DG=(V,E),負(fù)載最大差異度β′

輸出社區(qū)集合P

1.初始化社區(qū)的數(shù)目與節(jié)點(diǎn)個(gè)數(shù)相同;

3.for每一個(gè)節(jié)點(diǎn)vi∈v do

4.計(jì)算節(jié)點(diǎn)遷移到相鄰社區(qū)的模塊度增益ΔQ；

6.將節(jié)點(diǎn)遷移到目標(biāo)社區(qū);

7.else

8.節(jié)點(diǎn)不進(jìn)行遷移,保持原有社區(qū);

9.end if

11.end for

12.if totalQ≠totalQ′

13.計(jì)算每個(gè)社區(qū)內(nèi)節(jié)點(diǎn)之間的鏈路權(quán)重,更新為新節(jié)點(diǎn)環(huán)的權(quán)重;

14.計(jì)算每個(gè)社區(qū)之間鏈路權(quán)重之和,更新為新節(jié)點(diǎn)之間的鏈路權(quán)重;

15.重復(fù)步驟1;

16.else

17.輸出社區(qū)集合P;

18.end if

2.2.2 控制器部署策略

算法2的核心思想是遍歷所有社區(qū),搜索控制平面總平均傳播時(shí)延最小、控制路徑平均損失率小于可靠性指數(shù)R的最佳控制器位置。該算法的偽代碼為:

輸入社區(qū)集合P,可靠性指數(shù)R

輸出控制器位置集合C

1.初始化社區(qū)p1中控制器c1的位置使得min Lp1-avg;

2.for 社區(qū)p1每一個(gè)節(jié)點(diǎn)vi∈p1do

3.if(c1≠vi) then

4.計(jì)算當(dāng)前社區(qū)Lp1-avg;

5.記錄當(dāng)前c1的位置;

6.end if;

7.for j=2,j≤k do

9.記錄當(dāng)前cj的位置;

10.k=k+1;

11.end for

12.計(jì)算δ′;

15.else

16.返回步驟2;

17.end if

18.end for

3 仿真與分析

3.1 仿真環(huán)境

實(shí)驗(yàn)基于Java語(yǔ)言,使用Eclipse IDE軟件對(duì)本文算法進(jìn)行仿真。從SNDlib[19]中選取5種規(guī)模不同的拓?fù)淠Ｐ蛠?lái)評(píng)估本文的部署策略,拓?fù)鋵傩匀绫?所示。

表1 實(shí)驗(yàn)拓?fù)鋵傩?/p>

3.2 參數(shù)設(shè)置

鏈路長(zhǎng)度:用Haversine公式代替歐幾里得距離計(jì)算鏈路長(zhǎng)度,流量傳播速度為光速的2/3。

控制器負(fù)載:本文假設(shè)所有控制器都具有相同的負(fù)載能力,并且每個(gè)交換機(jī)所需的控制流量都是相同的,即l(n)=1,因此可用各社區(qū)交換機(jī)數(shù)量的最大差值表示子網(wǎng)間的負(fù)載平衡狀況,實(shí)驗(yàn)設(shè)定最大社區(qū)和最小社區(qū)的節(jié)點(diǎn)差異度不大于2,即β′=2。

可靠性指標(biāo):為保證實(shí)驗(yàn)結(jié)果的真實(shí)可靠,通過(guò)將多次實(shí)驗(yàn)結(jié)果取平均值來(lái)選取可靠性指標(biāo)R值。

3.3 算法復(fù)雜度分析

LCPS算法時(shí)間復(fù)雜度由以下2個(gè)部分組成:

1)網(wǎng)絡(luò)社區(qū)劃分:該算法分為2個(gè)階段,第一階段社區(qū)間節(jié)點(diǎn)轉(zhuǎn)移的時(shí)間復(fù)雜度為O(n),n為實(shí)驗(yàn)拓?fù)渲械逆溌窋?shù)量，第二階段將社區(qū)壓縮為一個(gè)新節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n+m),m為本輪迭代中節(jié)點(diǎn)的個(gè)數(shù)。因此網(wǎng)絡(luò)社區(qū)劃分算法的時(shí)間復(fù)雜度為O(n+m),且過(guò)程中所需計(jì)算量與網(wǎng)絡(luò)規(guī)模呈線性關(guān)系。

2)域內(nèi)控制器部署:計(jì)算k個(gè)社區(qū)中心的時(shí)間復(fù)雜度為O(k×n),計(jì)算社區(qū)的控制平面總平均傳播時(shí)延的復(fù)雜度為O(k×n),總共迭代k次,因此該過(guò)程的時(shí)間復(fù)雜度為O(k2×n)。

綜上可知,整個(gè)LCPS算法的時(shí)間復(fù)雜度為O(k2×n)。

3.4 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文算法的性能,實(shí)驗(yàn)比較了原始Louvain算法、LCPS算法和GABCC算法[15]在傳播時(shí)延、負(fù)載均衡、控制鏈路可靠性3個(gè)方面的差異。

實(shí)驗(yàn)1在不同網(wǎng)絡(luò)規(guī)模下比較3種算法得到的控制器數(shù)量,結(jié)果如圖1所示。從圖1可以看出,原始Louvain算法在不同拓?fù)湎碌玫降目刂破鱾€(gè)數(shù)均為2,且GABCC算法與原始Louvain算法在不同拓?fù)湎碌玫降目刂破鱾€(gè)數(shù)均小于LCPS算法,這是因?yàn)長(zhǎng)CPS算法可以根據(jù)拓?fù)浯笮§`活地劃分社區(qū),確定控制器的數(shù)量和位置,且隨著網(wǎng)絡(luò)規(guī)模的增大,控制器數(shù)量呈現(xiàn)遞增趨勢(shì)。圖2顯示了在Janos-US拓?fù)湎?LCPS算法劃分的社區(qū)以及控制器部署位置。從圖2可以看出,整個(gè)網(wǎng)絡(luò)被劃分成4個(gè)社區(qū),其中,實(shí)心代表控制器位置,空心代表交換機(jī)位置,具有相同形狀的節(jié)點(diǎn)屬于同一個(gè)社區(qū)。

圖1 3種算法在不同拓?fù)湎碌目刂破鱾€(gè)數(shù)

圖2 Janos-US拓?fù)湎驴刂破魑恢?/p>

實(shí)驗(yàn)2實(shí)驗(yàn)比較了3種算法在5種不同網(wǎng)絡(luò)拓?fù)湎碌目刂破矫婵偲骄鶄鞑r(shí)延,結(jié)果如圖3所示。從圖3可以看出,LCPS算法在降低傳播時(shí)延方面優(yōu)于其他2種算法。當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí),3種算法得到的控制平面總平均時(shí)延都很接近,但隨著網(wǎng)絡(luò)規(guī)模的增大,LCPS算法與其他2種算法得到的控制平面總平均時(shí)延差異逐漸增大。如在Janos-US拓?fù)湎?LCPS算法、原始Louvain算法、GABCC算法得到的控制平面總平均傳播時(shí)延分別為8.28 ms、9.34 ms、8.61 ms,相比其他2種算法，LCPS算法的控制平面總平均傳播時(shí)延分別降低了11.3%和3.8%;在TA2拓?fù)湎?3種算法得到的控制平面總平均傳播時(shí)延分別為49.67 ms、63.27 ms、61.20 ms,相比原始Louvain算法,LCPS算法的控制平面總平均傳播時(shí)延最多降低了21.4%,這是由于LCPS算法根據(jù)節(jié)點(diǎn)相似度定義的鏈路權(quán)重更加合理,劃分的社區(qū)內(nèi)部節(jié)點(diǎn)相對(duì)緊密,從而降低了交換機(jī)到控制器間的傳播時(shí)延。

圖3 3種算法在不同拓?fù)湎碌目刂破矫婵偲骄鶄鞑r(shí)延

實(shí)驗(yàn)3本文采用負(fù)載均衡指數(shù)B評(píng)價(jià)3種算法得到的控制器負(fù)載分布狀況,結(jié)果如圖4所示。從圖4可以看出,在不同網(wǎng)絡(luò)拓?fù)湎?LCPS算法的負(fù)載均衡指數(shù)明顯低于其他2種算法,且穩(wěn)定在[0.4,0.5]之間,這是由于LCPS算法在劃分社區(qū)時(shí)引入控制器負(fù)載差異度,可以限制社區(qū)規(guī)模,平衡控制器負(fù)載;原始Louvain算法的負(fù)載均衡狀態(tài)不可控,對(duì)于不同規(guī)模的網(wǎng)絡(luò)拓?fù)?負(fù)載均衡指數(shù)波動(dòng)較大,且高于LCPS算法,因此可能出現(xiàn)負(fù)載分配不平衡的情況。這是由于原始Louvain算法并未對(duì)社區(qū)的規(guī)模進(jìn)行限制,社區(qū)聚類(lèi)的過(guò)程中沒(méi)有及時(shí)收斂,社區(qū)劃分完全取決于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),沒(méi)有考慮負(fù)載均衡的因素;GABCC算法基于遺傳算法對(duì)網(wǎng)絡(luò)進(jìn)行劃分,該控制器部署方式過(guò)于復(fù)雜,且負(fù)載均衡指數(shù)仍處于一個(gè)較高水平。

圖4 3種算法在不同拓?fù)湎碌呢?fù)載均衡指數(shù)

實(shí)驗(yàn)4實(shí)驗(yàn)測(cè)試3種算法在Janos-US拓?fù)湎碌目刂奇溌房煽啃?。本文只考慮鏈路發(fā)生故障的場(chǎng)景,假設(shè)所有的鏈路具有相同的故障率,單位長(zhǎng)度鏈路故障率pl取值為[0,0.1]。圖5表示鏈路故障率與控制鏈路平均損失率之間的關(guān)系。從圖5可以看出,隨著鏈路故障率的逐漸增大,控制鏈路平均損失率呈逐漸增長(zhǎng)的趨勢(shì)。當(dāng)鏈路故障率相同時(shí),LCPS算法的控制鏈路平均損失率最低,GABCC算法最高。隨著鏈路故障率不斷增大,GABCC算法的控制鏈路平均損失率增長(zhǎng)速度最快,LCPS算法最慢。當(dāng)鏈路故障率為0.1時(shí),GABCC算法的控制鏈路平均損失率高達(dá)0.367,這是因?yàn)镚ABCC算法在部署控制器時(shí)并未考慮控制鏈路可靠性,因此當(dāng)發(fā)生鏈路故障時(shí),數(shù)據(jù)傳輸將會(huì)很快中斷。相比GABCC算法和原始Louvain算法,LCPS算法的部署方案能夠有效降低控制鏈路平均損失率,提高控制鏈路可靠性。

圖5 3種算法的控制路徑平均損失率

4 結(jié)束語(yǔ)

本文基于改進(jìn)的Louvain社區(qū)檢測(cè)算法實(shí)現(xiàn)大規(guī)模SDN網(wǎng)絡(luò)下多控制器的均衡部署。通過(guò)在劃分子網(wǎng)時(shí)引入控制器負(fù)載差異度,可以限制子網(wǎng)的大小,從而確保網(wǎng)絡(luò)均衡的劃分。在部署控制器時(shí),綜合考慮控制平面總平均傳播時(shí)延和控制鏈路可靠性,以達(dá)到最小化控制平面?zhèn)鞑r(shí)延和控制鏈路平均故障率的目的。仿真結(jié)果表明,本文提出的控制器部署策略可以根據(jù)不同規(guī)模的網(wǎng)絡(luò)拓?fù)?劃分合適的網(wǎng)絡(luò)分區(qū),有效降低時(shí)延,提高控制鏈路可靠性。下一步將采用基于遷移效率感知的動(dòng)態(tài)交換機(jī)遷移策略[20]，對(duì)網(wǎng)絡(luò)流量動(dòng)態(tài)變化的場(chǎng)景進(jìn)行研究，以平衡控制器負(fù)載、減小控制器響應(yīng)時(shí)間。