基于时延的软件定义网络控制器部署策略研究

黄尔杰，尚秋峰



基于时延的软件定义网络控制器部署策略研究

黄尔杰，尚秋峰

（华北电力大学电气与电子工程学院，河北 保定 071003）

软件定义网络（SDN）作为一种新兴的网络架构得到了广泛的关注。鉴于SDN控制器的部署对网络性能有很大的影响，研究了以最小化控制时延为优化目标的控制器部署问题，仿真分析了典型的随机算法、k-means算法，并提出I-k-center聚类算法来求解此问题。在IEEE30电力通信拓扑上的仿真实验表明，I-k-center算法可以有效优化网络的最大时延。

软件定义网络；控制器部署；k-center；数据链路

软件定义网络（Software Defined Networks，SDN）是一种将控制与转发平面进行分离的新颖网络架构，具有集中控制和网络可编程的特点，目前受到了广泛关注。已有研究发现，SDN控制器的部署对网络的性能有较大影响。为了解决SDN控制器部署的问题，目前，科研人员从时延、可靠性、成本等多个指标进行了研究。Hock等[1]2012年提出将网络故障率非零时交换机与控制器之间的最坏传输时延作为求解CPP的性能尺度。文献[2]首次提出成本开销的概念，指出控制器数量、控制器与交换机之间的连接以及控制器相互之间的连接所带来的成本之和应该被作为求解CPP的性能尺度。因为时延在网络性能中起着很大的作用，所以本文重点研究了最小化最差时延的控制器部署策略，并提出I-k-center算法来进行算法求解。

1 问题模型

常见的控制器部署有两种方式：带内模式和带外模式。带内模式指控制信息走原有的数据链路，要求交换机提前和控制器确定相应的连接规则。带外模式中，要为控制器和交换机建立独立的网络来进行控制信息的传输。带内模式避免了额外的信道开销，但是增大了数据处理的开销。

本文建立模型时作出以下几点假设：①采用带内模式进行相应的分析；②实际部署时，控制器和交换机大多采用co-locate原则（控制器和交换机部署在同一节点上），因此，认为同一节点的控制器和交换机之间的时延为0；③本文考虑采用扁平式的部署方案来部署SDN控制器，即所有的控制器之间是对等的，控制器之间需要进行通信来获取全网的网络信息。

将SDN网络表示为无向图：

=（，）. （1）

式（1）中：为交换机集合；为链路集合。

（，）为节点到节点的最短路径距离。控制器的集合为，控制器的部署位置从交换机节点位置当中进行选取，记为，对于每个控制器所控制的交换机的集合用={，…，}表示。

本文将端到端的最大时延来作为衡量指标，表达式为：

此多目标优化模型还有以下的限制，用一些等式和不等式来约束表示：

（，j）≤th1. （2）

（，j）≤th2. （3）

i≠j. （4）

式（2）表示所有的交换机到所属的控制器的时延不能超过给定的阈值th1，式（3）表示所有的控制器之间的同步时延不能超过给定的阈值th2，式（4）表示任意的两个控制器要放置在网络中的不同节点位置上。

2 I-k-center算法流程

I-k-center算法流程如下：①初始化算法，输入网络拓扑=（，）和控制器的数量；②计算所有节点间的距离（，）；③将点到其他点的最大距离记为i，选择i值最小的两个点1和2，计算1、2到其他点的距离之和，记为1和2，如果1＜2，选择1作为初始点；④选择与初始点距离最大的点作为第二个控制器部署点，根据最近邻原则进行交换机的分配，形成两个子网络cluster1和cluster2；⑤在cluster1和cluster2里按步骤④找出新的控制器部署的位置；⑥重复以上步骤，直到将网络划分为个子网络。

3 仿真结果

以部署3个控制器为例，在IEEE30电力通信网络中仿真分析随机算法、普通的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直接输出最大时延的值。由图可知，随着控制器数量的增加，四种算法的最大时延都在降低。以Internet2的34个城市级网络节点以及41条链路建议部署3+1个控制器参考，当IEEE30节点电力通信网中在控制器数量不超过4个时，I-k-center算法在只优化最大时延方面整体上要优于其他算法。

图2 不同控制器数量下的传输时延

以在IEEE30电力通信拓扑上部署4个控制器为例，计算IM-k-means和k-center的最大时延的累积分布，IM-k-means部署在节点1、节点6、节点12和节点24处，I-k-center部署在节点1、节点6、节点12和节点23处。从图3可以看出，以160 km的传输时延为例，k-center可以达到70%多的点满足要求，而IM-k-means只能达到60%左右的点满足时延要求，所以，可得出在只考虑最大时延这一指标的情况下，I-k-center比IM-k-means可以获得更好的效果。

图3 最大时延的累计分布

4 结束语

为了解决SDN控制器部署中的最大时延优化问题，在只考虑最大时延的这一指标的情况下，通过将k-center进行修改后的I-k-center作控制器部署的搜索算法，在IEEE30电力通信拓扑上进行仿真，并与常见的几种算法random、k-means、IM-k-means进行对比分析，仿真结果表明，I-k-center可以比其他几种算法更有效地寻找到优化最大时延的控制器部署的点。

［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中应用网络分区的控制器部署策略［J］.计算机工程，2019（01）：73-77.

2095－6835（2019）03－0068－02

TP393.02

A

10.15913/j.cnki.kjycx.2019.03.068

黄尔杰（1993—），男，硕士研究生，研究方向为软件定义网络。

〔编辑：张思楠〕