黃爾杰，尚秋峰

?

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

黃爾杰，尚秋峰

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

軟件定義網(wǎng)絡（SDN）作為一種新興的網(wǎng)絡架構得到了廣泛的關注。鑒于SDN控制器的部署對網(wǎng)絡性能有很大的影響，研究了以最小化控制時延為優(yōu)化目標的控制器部署問題，仿真分析了典型的隨機算法、k-means算法，并提出I-k-center聚類算法來求解此問題。在IEEE30電力通信拓撲上的仿真實驗表明，I-k-center算法可以有效優(yōu)化網(wǎng)絡的最大時延。

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

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

1 問題模型

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

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

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

=（，）. （1）

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

（，）為節(jié)點到節(jié)點的最短路徑距離?？刂破鞯募蠟?，控制器的部署位置從交換機節(jié)點位置當中進行選取，記為，對于每個控制器所控制的交換機的集合用={，…，}表示。

本文將端到端的最大時延來作為衡量指標，表達式為：

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

（，j）≤th1. （2）

（，j）≤th2. （3）

i≠j. （4）

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

2 I-k-center算法流程

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

3 仿真結果

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

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

圖1 I-k-center部署3個控制器

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

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

以在IEEE30電力通信拓撲上部署4個控制器為例，計算IM-k-means和k-center的最大時延的累積分布，IM-k-means部署在節(jié)點1、節(jié)點6、節(jié)點12和節(jié)點24處，I-k-center部署在節(jié)點1、節(jié)點6、節(jié)點12和節(jié)點23處。從圖3可以看出，以160 km的傳輸時延為例，k-center可以達到70%多的點滿足要求，而IM-k-means只能達到60%左右的點滿足時延要求，所以，可得出在只考慮最大時延這一指標的情況下，I-k-center比IM-k-means可以獲得更好的效果。

圖3 最大時延的累計分布

4 結束語

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

［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中應用網(wǎng)絡分區(qū)的控制器部署策略［J］.計算機工程，2019（01）：73-77.

2095－6835（2019）03－0068－02

TP393.02

A

10.15913/j.cnki.kjycx.2019.03.068

黃爾杰（1993—），男，碩士研究生，研究方向為軟件定義網(wǎng)絡。

〔編輯：張思楠〕