基于時(shí)延的軟件定義網(wǎng)絡(luò)控制器部署策略研究

黃爾杰，尚秋峰

?

基于時(shí)延的軟件定義網(wǎng)絡(luò)控制器部署策略研究

黃爾杰，尚秋峰

（華北電力大學(xué)電氣與電子工程學(xué)院，河北 保定 071003）

軟件定義網(wǎng)絡(luò)（SDN）作為一種新興的網(wǎng)絡(luò)架構(gòu)得到了廣泛的關(guān)注。鑒于SDN控制器的部署對(duì)網(wǎng)絡(luò)性能有很大的影響，研究了以最小化控制時(shí)延為優(yōu)化目標(biāo)的控制器部署問題，仿真分析了典型的隨機(jī)算法、k-means算法，并提出I-k-center聚類算法來求解此問題。在IEEE30電力通信拓?fù)渖系姆抡鎸?shí)驗(yàn)表明，I-k-center算法可以有效優(yōu)化網(wǎng)絡(luò)的最大時(shí)延。

軟件定義網(wǎng)絡(luò)；控制器部署；k-center；數(shù)據(jù)鏈路

軟件定義網(wǎng)絡(luò)（Software Defined Networks，SDN）是一種將控制與轉(zhuǎn)發(fā)平面進(jìn)行分離的新穎網(wǎng)絡(luò)架構(gòu)，具有集中控制和網(wǎng)絡(luò)可編程的特點(diǎn)，目前受到了廣泛關(guān)注。已有研究發(fā)現(xiàn)，SDN控制器的部署對(duì)網(wǎng)絡(luò)的性能有較大影響。為了解決SDN控制器部署的問題，目前，科研人員從時(shí)延、可靠性、成本等多個(gè)指標(biāo)進(jìn)行了研究。Hock等[1]2012年提出將網(wǎng)絡(luò)故障率非零時(shí)交換機(jī)與控制器之間的最壞傳輸時(shí)延作為求解CPP的性能尺度。文獻(xiàn)[2]首次提出成本開銷的概念，指出控制器數(shù)量、控制器與交換機(jī)之間的連接以及控制器相互之間的連接所帶來的成本之和應(yīng)該被作為求解CPP的性能尺度。因?yàn)闀r(shí)延在網(wǎng)絡(luò)性能中起著很大的作用，所以本文重點(diǎn)研究了最小化最差時(shí)延的控制器部署策略，并提出I-k-center算法來進(jìn)行算法求解。

1 問題模型

常見的控制器部署有兩種方式：帶內(nèi)模式和帶外模式。帶內(nèi)模式指控制信息走原有的數(shù)據(jù)鏈路，要求交換機(jī)提前和控制器確定相應(yīng)的連接規(guī)則。帶外模式中，要為控制器和交換機(jī)建立獨(dú)立的網(wǎng)絡(luò)來進(jìn)行控制信息的傳輸。帶內(nèi)模式避免了額外的信道開銷，但是增大了數(shù)據(jù)處理的開銷。

本文建立模型時(shí)作出以下幾點(diǎn)假設(shè)：①采用帶內(nèi)模式進(jìn)行相應(yīng)的分析；②實(shí)際部署時(shí)，控制器和交換機(jī)大多采用co-locate原則（控制器和交換機(jī)部署在同一節(jié)點(diǎn)上），因此，認(rèn)為同一節(jié)點(diǎn)的控制器和交換機(jī)之間的時(shí)延為0；③本文考慮采用扁平式的部署方案來部署SDN控制器，即所有的控制器之間是對(duì)等的，控制器之間需要進(jìn)行通信來獲取全網(wǎng)的網(wǎng)絡(luò)信息。

將SDN網(wǎng)絡(luò)表示為無向圖：

=（，）. （1）

式（1）中：為交換機(jī)集合；為鏈路集合。

（，）為節(jié)點(diǎn)到節(jié)點(diǎn)的最短路徑距離。控制器的集合為，控制器的部署位置從交換機(jī)節(jié)點(diǎn)位置當(dāng)中進(jìn)行選取，記為，對(duì)于每個(gè)控制器所控制的交換機(jī)的集合用={，…，}表示。

本文將端到端的最大時(shí)延來作為衡量指標(biāo)，表達(dá)式為：

此多目標(biāo)優(yōu)化模型還有以下的限制，用一些等式和不等式來約束表示：

（，j）≤th1. （2）

（，j）≤th2. （3）

i≠j. （4）

式（2）表示所有的交換機(jī)到所屬的控制器的時(shí)延不能超過給定的閾值th1，式（3）表示所有的控制器之間的同步時(shí)延不能超過給定的閾值th2，式（4）表示任意的兩個(gè)控制器要放置在網(wǎng)絡(luò)中的不同節(jié)點(diǎn)位置上。

2 I-k-center算法流程

I-k-center算法流程如下：①初始化算法，輸入網(wǎng)絡(luò)拓?fù)?（，）和控制器的數(shù)量；②計(jì)算所有節(jié)點(diǎn)間的距離（，）；③將點(diǎn)到其他點(diǎn)的最大距離記為i，選擇i值最小的兩個(gè)點(diǎn)1和2，計(jì)算1、2到其他點(diǎn)的距離之和，記為1和2，如果1＜2，選擇1作為初始點(diǎn)；④選擇與初始點(diǎn)距離最大的點(diǎn)作為第二個(gè)控制器部署點(diǎn)，根據(jù)最近鄰原則進(jìn)行交換機(jī)的分配，形成兩個(gè)子網(wǎng)絡(luò)cluster1和cluster2；⑤在cluster1和cluster2里按步驟④找出新的控制器部署的位置；⑥重復(fù)以上步驟，直到將網(wǎng)絡(luò)劃分為個(gè)子網(wǎng)絡(luò)。

3 仿真結(jié)果

以部署3個(gè)控制器為例，在IEEE30電力通信網(wǎng)絡(luò)中仿真分析隨機(jī)算法、普通的k-means算法，I-k-means[3]算法和I-k-center算法。

圖1為I-k-center的仿真結(jié)果，虛線為控制器所部署位置，同顏色的為控制器控制的交換機(jī)，控制交換時(shí)延最大為351 km。

圖1 I-k-center部署3個(gè)控制器

如圖2所示，在IEEE30電力通信拓?fù)渖线\(yùn)行random、k-means、IM-k-means、k-center四種算法所得到的最大時(shí)延結(jié)果，其中random和k-means取多次運(yùn)行后得到的最大時(shí)延的平均值，k-center和IM-k-means直接輸出最大時(shí)延的值。由圖可知，隨著控制器數(shù)量的增加，四種算法的最大時(shí)延都在降低。以Internet2的34個(gè)城市級(jí)網(wǎng)絡(luò)節(jié)點(diǎn)以及41條鏈路建議部署3+1個(gè)控制器參考，當(dāng)IEEE30節(jié)點(diǎn)電力通信網(wǎng)中在控制器數(shù)量不超過4個(gè)時(shí)，I-k-center算法在只優(yōu)化最大時(shí)延方面整體上要優(yōu)于其他算法。

圖2 不同控制器數(shù)量下的傳輸時(shí)延

以在IEEE30電力通信拓?fù)渖喜渴?個(gè)控制器為例，計(jì)算IM-k-means和k-center的最大時(shí)延的累積分布，IM-k-means部署在節(jié)點(diǎn)1、節(jié)點(diǎn)6、節(jié)點(diǎn)12和節(jié)點(diǎn)24處，I-k-center部署在節(jié)點(diǎn)1、節(jié)點(diǎn)6、節(jié)點(diǎn)12和節(jié)點(diǎn)23處。從圖3可以看出，以160 km的傳輸時(shí)延為例，k-center可以達(dá)到70%多的點(diǎn)滿足要求，而IM-k-means只能達(dá)到60%左右的點(diǎn)滿足時(shí)延要求，所以，可得出在只考慮最大時(shí)延這一指標(biāo)的情況下，I-k-center比IM-k-means可以獲得更好的效果。

圖3 最大時(shí)延的累計(jì)分布

4 結(jié)束語

為了解決SDN控制器部署中的最大時(shí)延優(yōu)化問題，在只考慮最大時(shí)延的這一指標(biāo)的情況下，通過將k-center進(jìn)行修改后的I-k-center作控制器部署的搜索算法，在IEEE30電力通信拓?fù)渖线M(jìn)行仿真，并與常見的幾種算法random、k-means、IM-k-means進(jìn)行對(duì)比分析，仿真結(jié)果表明，I-k-center可以比其他幾種算法更有效地尋找到優(yōu)化最大時(shí)延的控制器部署的點(diǎn)。

［1］Koponen T.Software is the future of networking［C］//The 8th ACM/IEEE Symposium on Architectures for Networking and Communications Systems，2012.

［2］SALLAHI A，STHILAIRE M. Optimal model for the controller placement problem in software defined networks［J］. IEEE Communi-cations Letters，2015，19（01）：30-33.

［3］趙季紅，蔡田杰，曲樺，等.SDN中應(yīng)用網(wǎng)絡(luò)分區(qū)的控制器部署策略［J］.計(jì)算機(jī)工程，2019（01）：73-77.

2095－6835（2019）03－0068－02

TP393.02

A

10.15913/j.cnki.kjycx.2019.03.068

黃爾杰（1993—），男，碩士研究生，研究方向?yàn)檐浖x網(wǎng)絡(luò)。

〔編輯：張思楠〕