軟件定義網絡中應用二值粒子群優化的控制器部署策略

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

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

?

軟件定義網絡中應用二值粒子群優化的控制器部署策略

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

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

為了確定控制器的最優化部署方案,構建軟件定義網絡中邏輯上集中、物理上分布的控制平面,提出軟件定義網絡中應用二值粒子群優化的控制器部署策略。對控制器部署問題建模,以交換機到控制器的平均時延最短以及在網絡中部署的控制器數量較少為多優化目標。提出粒子重構機制,實現粒子群優化算法的二值化,用以表示控制器在網絡中部署的位置。基于二值粒子群優化算法設計多優化目標的控制器部署策略,仿真得到控制器部署問題的非劣最優解集合,對應給定的控制器數量,得到平均時延最小的控制器部署方案。實驗結果表明,應用二值粒子群優化的控制器部署策略聯合考慮了控制器數量和交換機到控制器的平均時延,為實現控制器最優化部署提供了依據。

控制器部署;軟件定義網絡;二值粒子群優化;非劣最優解集合

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

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

國內外關于控制器部署現有的算法是圍繞時延[6]、可靠性[7-9]等不同的優化指標來確定控制器的部署位置。文獻[6]定義了平均時延和最壞情況時延兩個指標,分析了Internet2網絡上的控制器部署問題,得到了控制器的最優部署方案,并指出在多數網絡拓撲下,增加控制器的數量可以讓時延以接近線性的比例減小,但是文中并沒有給出具體的算法。文獻[7-9]定義有效路徑為可靠性指標,應用貪婪算法得到接近最優的解決方案,但該方法是在給定控制器數量情況下計算其放置位置的,對于不熟悉的網絡拓撲,并不能很容易地知道控制器數量。因此,本文應用二值粒子群優化的控制器部署策略,可以同時確定給定網絡拓撲下控制器的數量及部署位置。

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

1 控制器部署問題建模

對于給定的網絡環境G(V,E),V是所有節點集合,節點總數為n,即|V|=n,E∈V×V為鏈路集合,邊權重代表網絡時延。控制器部署問題的優化目標是交換機到控制器的平均時延最小以及在網絡中部署的控制器數量k較小[6],平均時延為

(1)

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

對所有節點編號,{C}表示控制器集合,|C|=C,{S}表示交換機集合,|S|=n。假定控制器部署在交換機的位置,?i∈{S},?j∈{C},xij取0或1,1表示在交換機j所在位置上部署控制器,反之表示不部署。

BPSO算法將其粒子的每一維及粒子局部最優、全局最優限制為1或0,速度不作限制。定義每個粒子Xi=[xi1,xi2,…,xij,…,xi,n]為一種控制器部署方案,其中i為粒子標號,j表示交換機標號。假設每個交換機的位置只能部署一個控制器,每個控制器至少控制一個交換機。控制器部署問題的優化目標是

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

(2)

(3)

(4)

式中:f1(Xi)表示控制器的總數;f2(Xi)為節點到控制器的平均時延;

dj,i=d(j,i)

(5)

(6)

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

(7)

其中qmax的值為控制器到交換機的平均跳數,為約數,lq表示第q跳的物理鏈路,ha為網絡中所有節點對距離的平均跳數。

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

xij={0,1}

(8)

1≤f1(Xi)≤n

(9)

f2(Xi)≥0

(10)

(11)

式(8)表示xij取0或1;式(9)表示控制器數量在1到總節點數之間,即至少有一個控制器組成控制平面保證網絡能夠正常運行,但是不會每個節點都部署一個控制器;式(10)表示交換機到控制器的時延大于0;式(11)表示任意一個節點只有兩種狀態,有和沒有控制器。

定理1 當網絡中部署的控制器數與交換機數相等時,交換機到控制器的平均時延為0。

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

定理2 當網絡中部署的控制器數為1時,交換機到控制器的平均時延最大。

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

2 基于多目標BPSO算法控制器部署策略

2.1 基于多目標BPSO算法建模

粒子群優化算法(particle swarm optimization,PSO)是一種基于群體智能的全局隨機啟發式搜索算法[13],粒子跟蹤局部最優和全局最優來更新位置。BPSO算法將粒子的每一維及粒子的歷史最優、全局最優限制為1或0,速度不作限制[14-15]。在一個|S|=n維N個粒子的目標搜索空間中,第i個粒子的位置和速度表示為n維的向量,分別為Xi=xi1,xi2,…,xin),Vi=(vi1,vi2,…,vin,i=1,2,…,n)。進化中,粒子跟蹤局部最優和全局最優來更新自己,分別記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次迭代,慣性權重ω依據式(13)變化,ωmax=0.9,ωmin=0.4,c1=c2=2;r1和r2為[0,1]范圍內的隨機數。BPSO粒子位置更新方式如下。

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

}while(k≤n(C))

2.2 基于多目標BPSO算法的控制器部署策略

應用多目標的二值粒子群優化算法,適應度函數為

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

(15)

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

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

步驟3 根據式(15)計算初始時刻粒子的適應度函數F;

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

步驟6 判斷迭代次數t

步驟7 判斷k

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

3 仿真結果

3.1 仿真環境配置

為了驗證算法的有效性,我們采用34節點的Internet2網絡拓撲[13],對每個節點標號,用距離表示時延,單位為km,如圖1所示;假設每個節點放置交換機,而控制器部署在交換機的位置上。實驗仿真中,設置粒子數量為20,最大迭代次數為1 000。

圖1 Internet2網絡拓撲

3.2 Pareto解集

仿真得到了控制器數量從1～34變化的控制器部署方案,表1顯示了控制器數量為1～12的最優部署方案和較優時延值,為管理員部署控制器提供了參考。隨著控制器數量的增加時延減小。控制器數量為1時時延最大,而控制器數量為34,即每個節點均部署控制器時,控制器時延最小為0。

表1 控制器數量為1～12的部署方案

3.3 增加控制器數量的效率

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

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

圖2 隨機平均時延與最優時延之比隨控制器數量的變化

圖3 控制器數量為1～12時的收益比

3.4 算法收斂性

圖4 不同控制器數量下時延隨迭代次數的變化

圖4表示控制器數量分別為5、10、17時應用二值粒子群優化的控制器部署算法的收斂性。該算法可以得到任意控制器數量情況下的控制器部署方案和收斂值。由圖可見,隨著控制器數量增加,算法收斂時間變長,速度變慢。這是因為控制器數量增加,控制器部署可能方案數量增加,收斂到較優方案的時間增加。

4 結 論

本文提出軟件定義網絡中應用二值粒子群優化的控制器部署策略,在滿足網絡性能和預算的條件下,為給定的網絡拓撲部署多少個控制器以及如何部署提供了可行的方案。該策略以控制器數量和控制器到交換機的平均時延為優化目標,要求在控制器數量盡可能少的情況下平均時延最小,應用二值離散粒子群算法迭代進化,得到了最終的非劣最優解集,并以此確定出控制器的數量和部署方案。

[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中基于可靠性優化的控制器放置算法研究[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。 作者簡介:王麗霞(1989—),女,碩士生;曲樺(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61371087);國家高技術研究發展計劃重大專項資助項目(2013ZX0302010-003);國家高技術研究發展計劃資助項目(2014AA01A701,2014AA01A706,2014AA01A707)。

10.7652/xjtuxb201506011

TP391

A

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