軟件定義網(wǎng)絡(luò)中應(yīng)用二值粒子群優(yōu)化的控制器部署策略

王麗霞,曲樺,趙季紅,2,王力

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.西安郵電學(xué)院通信工程系,710061,西安)

?

軟件定義網(wǎng)絡(luò)中應(yīng)用二值粒子群優(yōu)化的控制器部署策略

王麗霞1,曲樺1,趙季紅1,2,王力1

(1.西安交通大學(xué)電子與信息工程學(xué)院,710049,西安;2.西安郵電學(xué)院通信工程系,710061,西安)

為了確定控制器的最優(yōu)化部署方案,構(gòu)建軟件定義網(wǎng)絡(luò)中邏輯上集中、物理上分布的控制平面,提出軟件定義網(wǎng)絡(luò)中應(yīng)用二值粒子群優(yōu)化的控制器部署策略。對(duì)控制器部署問題建模,以交換機(jī)到控制器的平均時(shí)延最短以及在網(wǎng)絡(luò)中部署的控制器數(shù)量較少為多優(yōu)化目標(biāo)。提出粒子重構(gòu)機(jī)制,實(shí)現(xiàn)粒子群優(yōu)化算法的二值化,用以表示控制器在網(wǎng)絡(luò)中部署的位置?；诙盗Ｗ尤簝?yōu)化算法設(shè)計(jì)多優(yōu)化目標(biāo)的控制器部署策略,仿真得到控制器部署問題的非劣最優(yōu)解集合,對(duì)應(yīng)給定的控制器數(shù)量,得到平均時(shí)延最小的控制器部署方案。實(shí)驗(yàn)結(jié)果表明,應(yīng)用二值粒子群優(yōu)化的控制器部署策略聯(lián)合考慮了控制器數(shù)量和交換機(jī)到控制器的平均時(shí)延,為實(shí)現(xiàn)控制器最優(yōu)化部署提供了依據(jù)。

控制器部署;軟件定義網(wǎng)絡(luò);二值粒子群優(yōu)化;非劣最優(yōu)解集合

軟件定義網(wǎng)絡(luò)(software defined network,SDN)把原有封閉體系解耦,將控制平面與轉(zhuǎn)發(fā)平面分離,提供了一種可編程的網(wǎng)絡(luò)實(shí)現(xiàn),由控制器組成邏輯上集中的控制平面來管理和監(jiān)督一些簡(jiǎn)單的轉(zhuǎn)發(fā)設(shè)備[1-2],這樣的網(wǎng)絡(luò)重構(gòu)簡(jiǎn)化了控制平面設(shè)計(jì),提供了可擴(kuò)展的網(wǎng)絡(luò)接口及接近最優(yōu)的路徑選擇,同時(shí)全局視圖的網(wǎng)絡(luò)資源管理便于統(tǒng)一、靈活、高效地網(wǎng)絡(luò)管理和維護(hù)[3]。

集中式控制平面的可擴(kuò)展性較差,大規(guī)模網(wǎng)絡(luò)中其性能急劇下降。目前多采取邏輯上集中、物理上分布的控制平面部署形式[4],例如Onix[3]、HyperFlow[5]等,這些網(wǎng)絡(luò)架構(gòu)通過把多個(gè)轉(zhuǎn)發(fā)設(shè)備劃分到不同的控制域中,形成分布式的控制平面,這是未來大規(guī)模SDN網(wǎng)絡(luò)部署的重要解決思路。對(duì)于給定的網(wǎng)絡(luò)拓?fù)?控制器部署問題主要考慮控制器的數(shù)量和控制器部署位置兩方面[6]。

國(guó)內(nèi)外關(guān)于控制器部署現(xiàn)有的算法是圍繞時(shí)延[6]、可靠性[7-9]等不同的優(yōu)化指標(biāo)來確定控制器的部署位置。文獻(xiàn)[6]定義了平均時(shí)延和最壞情況時(shí)延兩個(gè)指標(biāo),分析了Internet2網(wǎng)絡(luò)上的控制器部署問題,得到了控制器的最優(yōu)部署方案,并指出在多數(shù)網(wǎng)絡(luò)拓?fù)湎?增加控制器的數(shù)量可以讓時(shí)延以接近線性的比例減小,但是文中并沒有給出具體的算法。文獻(xiàn)[7-9]定義有效路徑為可靠性指標(biāo),應(yīng)用貪婪算法得到接近最優(yōu)的解決方案,但該方法是在給定控制器數(shù)量情況下計(jì)算其放置位置的,對(duì)于不熟悉的網(wǎng)絡(luò)拓?fù)?并不能很容易地知道控制器數(shù)量。因此,本文應(yīng)用二值粒子群優(yōu)化的控制器部署策略,可以同時(shí)確定給定網(wǎng)絡(luò)拓?fù)湎驴刂破鞯臄?shù)量及部署位置。

二值粒子群優(yōu)化算法(binary particle swarm optimization, BPSO)是基于群體智能的全局隨機(jī)啟發(fā)式搜索算法,粒子跟蹤局部最優(yōu)和全局最優(yōu)來更新位置,有收斂速度快、效率高、極易實(shí)現(xiàn)全局優(yōu)化等優(yōu)點(diǎn)?？刂破鞑渴饐栴}解決的是一個(gè)NP-hard(non-deterministic polynomial hard)問題[6],多目標(biāo)則可以提供非劣解集[10]。應(yīng)用二值粒子群優(yōu)化的控制器部署策略將每個(gè)粒子定義為一種控制器部署方案,以交換機(jī)到控制器的時(shí)延和需要的控制器數(shù)量為優(yōu)化目標(biāo),應(yīng)用多目標(biāo)二值粒子群優(yōu)化算法[11-12]迭代進(jìn)化得到非劣最優(yōu)解集,并依此確定控制器的數(shù)量及其最優(yōu)部署方案。最后,在Internet2拓?fù)鋄13]下仿真驗(yàn)證該算法,提供可行部署方案。

1 控制器部署問題建模

對(duì)于給定的網(wǎng)絡(luò)環(huán)境G(V,E),V是所有節(jié)點(diǎn)集合,節(jié)點(diǎn)總數(shù)為n,即|V|=n,E∈V×V為鏈路集合,邊權(quán)重代表網(wǎng)絡(luò)時(shí)延?？刂破鞑渴饐栴}的優(yōu)化目標(biāo)是交換機(jī)到控制器的平均時(shí)延最小以及在網(wǎng)絡(luò)中部署的控制器數(shù)量k較小[6],平均時(shí)延為

(1)

式中:d(v,s)表示節(jié)點(diǎn)v∈V到控制器s∈V的最短路徑。本文的目標(biāo)是尋找控制器的部署集合S′使得|S′|=k,k盡可能小時(shí)La最小。

對(duì)所有節(jié)點(diǎn)編號(hào),{C}表示控制器集合,|C|=C,{S}表示交換機(jī)集合,|S|=n。假定控制器部署在交換機(jī)的位置,?i∈{S},?j∈{C},xij取0或1,1表示在交換機(jī)j所在位置上部署控制器,反之表示不部署。

BPSO算法將其粒子的每一維及粒子局部最優(yōu)、全局最優(yōu)限制為1或0,速度不作限制。定義每個(gè)粒子Xi=[xi1,xi2,…,xij,…,xi,n]為一種控制器部署方案,其中i為粒子標(biāo)號(hào),j表示交換機(jī)標(biāo)號(hào)。假設(shè)每個(gè)交換機(jī)的位置只能部署一個(gè)控制器,每個(gè)控制器至少控制一個(gè)交換機(jī)?？刂破鞑渴饐栴}的優(yōu)化目標(biāo)是

min(f1(Xi),f2(Xi))

(2)

(3)

(4)

式中:f1(Xi)表示控制器的總數(shù);f2(Xi)為節(jié)點(diǎn)到控制器的平均時(shí)延;

dj,i=d(j,i)

(5)

(6)

qmax?ha(i,j)/f1(Xi)

(7)

其中qmax的值為控制器到交換機(jī)的平均跳數(shù),為約數(shù),lq表示第q跳的物理鏈路,ha為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)距離的平均跳數(shù)。

控制器部署問題的約束條件為

xij={0,1}

(8)

1≤f1(Xi)≤n

(9)

f2(Xi)≥0

(10)

(11)

式(8)表示xij取0或1;式(9)表示控制器數(shù)量在1到總節(jié)點(diǎn)數(shù)之間,即至少有一個(gè)控制器組成控制平面保證網(wǎng)絡(luò)能夠正常運(yùn)行,但是不會(huì)每個(gè)節(jié)點(diǎn)都部署一個(gè)控制器;式(10)表示交換機(jī)到控制器的時(shí)延大于0;式(11)表示任意一個(gè)節(jié)點(diǎn)只有兩種狀態(tài),有和沒有控制器。

定理1 當(dāng)網(wǎng)絡(luò)中部署的控制器數(shù)與交換機(jī)數(shù)相等時(shí),交換機(jī)到控制器的平均時(shí)延為0。

證明 ?i,j,j=i時(shí),dj,i=d(j,i)=0

定理2 當(dāng)網(wǎng)絡(luò)中部署的控制器數(shù)為1時(shí),交換機(jī)到控制器的平均時(shí)延最大。

式中:ha(i,j)恒定,qmax?ha(i,j)/f1(X)取最大值。

2 基于多目標(biāo)BPSO算法控制器部署策略

2.1 基于多目標(biāo)BPSO算法建模

粒子群優(yōu)化算法(particle swarm optimization,PSO)是一種基于群體智能的全局隨機(jī)啟發(fā)式搜索算法[13],粒子跟蹤局部最優(yōu)和全局最優(yōu)來更新位置。BPSO算法將粒子的每一維及粒子的歷史最優(yōu)、全局最優(yōu)限制為1或0,速度不作限制[14-15]。在一個(gè)|S|=n維N個(gè)粒子的目標(biāo)搜索空間中,第i個(gè)粒子的位置和速度表示為n維的向量,分別為Xi=xi1,xi2,…,xin),Vi=(vi1,vi2,…,vin,i=1,2,…,n)。進(jìn)化中,粒子跟蹤局部最優(yōu)和全局最優(yōu)來更新自己,分別記pbest=(pi1,pi2,…,pin),gbest=(pg1,pg2,…,pgn),i=1,2,…,n,如式(12)、(13)所示,式(14)是速度歸一化取值方式

(12)

ω=ωmax-((ωmax-ωmin)/tmax)t

(13)

(14)

式(12)為粒子i的第j維速度更新方程;t為第t次迭代,慣性權(quán)重ω依據(jù)式(13)變化,ωmax=0.9,ωmin=0.4,c1=c2=2;r1和r2為[0,1]范圍內(nèi)的隨機(jī)數(shù)。BPSO粒子位置更新方式如下。

do{[vmax,j]=max(v);vj=0;

}while(k≤n(C))

2.2 基于多目標(biāo)BPSO算法的控制器部署策略

應(yīng)用多目標(biāo)的二值粒子群優(yōu)化算法,適應(yīng)度函數(shù)為

F=min(f1(Xi),f2(Xi))

(15)

基于多目標(biāo)BPSO算法的控制器部署策略步驟如下。

步驟1 限定粒子群的位置以及速度范圍,設(shè)定種群規(guī)模N,粒子最大進(jìn)化次數(shù)tmax,控制器數(shù)量n(C);

步驟3 根據(jù)式(15)計(jì)算初始時(shí)刻粒子的適應(yīng)度函數(shù)F;

步驟5 所有粒子維數(shù)處理完畢,判斷t

步驟6 判斷迭代次數(shù)t

步驟7 判斷k

步驟8 得到最終的非劣最優(yōu)解集,分析判斷選取最優(yōu)的k值和部署情況。

3 仿真結(jié)果

3.1 仿真環(huán)境配置

為了驗(yàn)證算法的有效性,我們采用34節(jié)點(diǎn)的Internet2網(wǎng)絡(luò)拓?fù)鋄13],對(duì)每個(gè)節(jié)點(diǎn)標(biāo)號(hào),用距離表示時(shí)延,單位為km,如圖1所示;假設(shè)每個(gè)節(jié)點(diǎn)放置交換機(jī),而控制器部署在交換機(jī)的位置上。實(shí)驗(yàn)仿真中,設(shè)置粒子數(shù)量為20,最大迭代次數(shù)為1 000。

圖1 Internet2網(wǎng)絡(luò)拓?fù)?/p>

3.2 Pareto解集

仿真得到了控制器數(shù)量從1～34變化的控制器部署方案,表1顯示了控制器數(shù)量為1～12的最優(yōu)部署方案和較優(yōu)時(shí)延值,為管理員部署控制器提供了參考。隨著控制器數(shù)量的增加時(shí)延減小。控制器數(shù)量為1時(shí)時(shí)延最大,而控制器數(shù)量為34,即每個(gè)節(jié)點(diǎn)均部署控制器時(shí),控制器時(shí)延最小為0。

表1 控制器數(shù)量為1～12的部署方案

3.3 增加控制器數(shù)量的效率

為了驗(yàn)證本文算法的有效性,仿真結(jié)果與文獻(xiàn)[6]給出的Internet2環(huán)境下的部署結(jié)果比較如圖2、3所示,結(jié)果顯示本文算法能夠有效地解決控制器部署問題。

圖2顯示了隨機(jī)平均時(shí)延與優(yōu)化之后的最優(yōu)時(shí)延的比值,設(shè)為R,隨著控制器數(shù)量的變化,表現(xiàn)了某個(gè)控制器數(shù)量環(huán)境下,算法優(yōu)化部署的效益性。該值越大,表示優(yōu)化時(shí)延相對(duì)隨機(jī)平均時(shí)延越小,即效益越好。例如控制器數(shù)量為4時(shí),應(yīng)用本文算法所得最優(yōu)時(shí)延為1 108.16 km,見表1,隨機(jī)平均時(shí)延為1 794.24 km(由最短路徑所得的隨機(jī)部署時(shí)延值),隨機(jī)平均時(shí)延與最優(yōu)時(shí)延之比約為1.6,同理得控制器數(shù)量為3時(shí)比例約為1.49,說明控制器數(shù)量為4時(shí)比控制器數(shù)量為3時(shí)得到了更大的時(shí)延優(yōu)化比值、更優(yōu)的部署效益。由圖2可見,控制器數(shù)量為4時(shí),隨機(jī)平均時(shí)延與最優(yōu)時(shí)延之比最大,說明控制器數(shù)量為4時(shí),部署效益最好。

圖2 隨機(jī)平均時(shí)延與最優(yōu)時(shí)延之比隨控制器數(shù)量的變化

圖3 控制器數(shù)量為1～12時(shí)的收益比

3.4 算法收斂性

圖4 不同控制器數(shù)量下時(shí)延隨迭代次數(shù)的變化

圖4表示控制器數(shù)量分別為5、10、17時(shí)應(yīng)用二值粒子群優(yōu)化的控制器部署算法的收斂性。該算法可以得到任意控制器數(shù)量情況下的控制器部署方案和收斂值。由圖可見,隨著控制器數(shù)量增加,算法收斂時(shí)間變長(zhǎng),速度變慢。這是因?yàn)榭刂破鲾?shù)量增加,控制器部署可能方案數(shù)量增加,收斂到較優(yōu)方案的時(shí)間增加。

4 結(jié) 論

本文提出軟件定義網(wǎng)絡(luò)中應(yīng)用二值粒子群優(yōu)化的控制器部署策略,在滿足網(wǎng)絡(luò)性能和預(yù)算的條件下,為給定的網(wǎng)絡(luò)拓?fù)洳渴鸲嗌賯€(gè)控制器以及如何部署提供了可行的方案。該策略以控制器數(shù)量和控制器到交換機(jī)的平均時(shí)延為優(yōu)化目標(biāo),要求在控制器數(shù)量盡可能少的情況下平均時(shí)延最小,應(yīng)用二值離散粒子群算法迭代進(jìn)化,得到了最終的非劣最優(yōu)解集,并以此確定出控制器的數(shù)量和部署方案。

[1]MENDONCA M, ASTUTO B N, NGUYEN X N, et al.A survey of software-defined networking: past, present, and future of programmable networks [J].IEEE Communications Surveys and Tutorials, 2014, 16(3): 1617-1634.

[2]Open Networking Foundation.Software-defined networking definition[EB/OL].(2013-05-01)[2014-05-12].http:∥www.openflowswitch.org.

[3]KOPONEN T, CASADO M, GUDE N, et al.Onix: a distributed control platform for large-scale production networks [C]∥Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation.Berkeley, CA, USA: USENIX Association, 2010: 351-364.

[4]LEVIN D, WUNDSAM A, HELLER B, et al.Logically centralized?: state distribution trade-offs in software defined networks [C]∥Proceedings of the First Workshop on Hot Topics in Software Defined Networks.New York, USA: ACM, 2012: 1-6.

[5]LANTZ B, HELLER B, MCKEOWN N.A network in a laptop: rapid prototyping for software-defined networks [C]∥Proceedings of the 9th ACM Sigcomm Workshop on Hot Topics in Networks.New York, USA: ACM, 2010: 1-6.

[6]HELLER B, SHERWOOD R, MCKEOWN N.The controller placement problem [C]∥Proceedings of the First Workshop on Hot Topics in Software Defined Networks.New York, USA: ACM, 2012: 7-12.

[7]HU Yannan, WANG Wendong, GONG Xiangyang, et al.Reliability-aware controller placement for software-defined networks [C]∥Proceedings of the 2013 IFIP/IEEE International Symposium on Integrated Network Management.Piscataway, NJ, USA: IEEE, 2013: 672-675.

[8]BEHESHTI N, ZHANG Ying.Fast failover for control traffic in software-defined networks [C]∥Proceedings of the 2012 IEEE Global Communications Conference.Piscataway, NJ, USA: IEEE, 2012: 2665-2670.

[9]劉娟, 黃韜, 魏亮.SDN中基于可靠性優(yōu)化的控制器放置算法研究[EB/OL].(2013-12-06)[2014-05-05].http:∥www.paper.edu.cn/releasepaper/content/201312-161.

[10]ZITZLER E, THIELE L.Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach [J].IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271.

[11]COELLO C A, LECHUGA M S.MOPSO: a proposal for multiple objective particle swarm optimization [C]∥Proceedings of the 2002 Congress on Evolutionary Computation.Piscataway, NJ, USA: IEEE, 2002: 1051-1056.

[12]MANTWAY A H, Al-MUHAINI M M.Multi-objective BPSO algorithm for distribution system expansion planning including distributed generation [C]∥Proceedings of the 2008 Transmission and Distribution Conference and Exposition.Piscataway, NJ, USA: IEEE, 2008: 1-8.

[13]Internet2 Open Science, Scholarship and Services Exchange.Internet2 network [EB/OL].(2013-06-04)[2014-06-21].http:∥www.internet2.edu/network/ose/.

[14]KENNEDY J, EBERHART R.Particle swarm optimization [C]∥Proceedings of the International Conference on Neural Networks.Piscataway, NJ, USA: IEEE, 1995: 1942-1948.

[15]KENNEDY J, EBERHART R C.A discrete binary version of the particle swarm algorithm [C]∥Proceedings of the 1997 Conference on Systems, Man and Cybernetics.Piscataway, NJ, USA: IEEE, 1997: 4101-4108.

(編輯 武紅江)

A Strategy of Controller Placement in Software Defined Networks Using Binary Particle Swarm Optimization

WANG Lixia1, QU Hua1, ZHAO Jihong1,2, WANG Li1

(1.School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 2.School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710061, China)

A strategy of controller placement in software defined networks using the binary particle swarm optimization is proposed to find the optimal placement scheme of controllers and to build a logically centralized and physically distributed control plan for the controller placement problem in SDN.An optimization model is built for the problem, and the optimization goals are to minimize both the number of controllers and the latency from controllers to switch.The binary particle reconstruction mechanism is put forward to denote the position of the controller in the network.A binary particle swarm algorithm is applied to find the set of Pareto optimum for the problem, from which a strategy of controller placement is provided.Simulation results show that the proposed algorithm gets the optimal placement strategies with minimum latency for different number of controllers.

controller placement problem; software defined network; binary particle swarm optimization; pareto set

2014-11-14。 作者簡(jiǎn)介:王麗霞(1989—),女,碩士生;曲樺(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61371087);國(guó)家高技術(shù)研究發(fā)展計(jì)劃重大專項(xiàng)資助項(xiàng)目(2013ZX0302010-003);國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2014AA01A701,2014AA01A706,2014AA01A707)。

10.7652/xjtuxb201506011

TP391

A

0253-987X(2015)06-0067-05