SDN控制域确定与划分机制*

矫培艳，张闯闯，王兴伟+，黄 敏

1.东北大学 软件学院，沈阳 110169

2.东北大学 计算机科学与工程学院，沈阳 110169

3.东北大学 信息科学与工程学院，沈阳 110819

1 引言

传统的网络架构复杂且封闭，使得网络管理员在考虑网络动态和各种应用需求时难以进行操作和管理，其庞大的部署基础使得互联网在物理基础设施、协议以及性能发展方面变得非常困难[1]。网络通常是由大量网络设备构建而成，它们实现了许多复杂的协议。网络运营商负责配置策略以响应各种网络事件和应用程序。他们必须手动将这些高级策略转换为低级配置命令，因此网络管理和性能调整容易出错。网络从业者和研究人员面临的另一个几乎无法克服的挑战被称为“互联网僵化”[2]。然而，随着当前和新兴的互联网应用和服务变得越来越复杂，互联网必须能够发展演进以应对这些新的挑战。软件定义网络（software defined networking，SDN）的核心思想是“可编程网络”，通过将数据平面与控制平面进行解耦[3]，很大程度上简化了网络的管理与配置，实现网络的智能化。

在SDN中，控制器决定交换机如何转发数据流，交换机只负责数据流的转发。SDN中控制平面可以采用不同形式，包括集中式（单控制器）和分布式（多控制器）体系架构[4]。对于许多中等规模的网络来说，单控制器足以应付，然而对于许多大规模广域网而言，由于单控制器架构没有足够的能力在有限时间内处理来自所有交换机的请求，其计算能力成为了网络瓶颈。同时，利用多控制器平面对网络进行分布式管理可以有效避免单点故障[5]。

在SDN中，控制器是整个网络的核心，它能够对网络资源进行正确的调度和控制。控制器需要制定策略以及下发流表给交换机，以便统一管理。而交换机也需要向它所属的控制器发送消息，以便控制器对其进行监控和统计。因此，交换机和控制器之间的响应时间对SDN网络的性能有很大的影响。而该响应时间的主要影响因素为交换机与控制器之间的传播时延和控制器的负载。本文在确定控制域的数量以及进行控制域划分时主要考虑控制器之间的负载均衡，因为负载均衡是衡量控制器性能的重要指标之一。当控制器负载不均衡时，会导致控制器效率以及SDN网络性能下降。

为此，本文研究了SDN 控制器确定与划分问题，以实现各控制器之间负载均衡。论文的主要贡献如下：

（1）设计了基于本征间隙的谱聚类算法的SDN控制域确定机制，通过建立相似矩阵计算得到控制域的最优数量。

（2）设计了基于特征向量的聚类算法的SDN 控制域划分机制，以控制器的负载均衡为目标，根据确定的控制器的最优数量实现SDN控制域的划分。

（3）仿真实验结果表明，本文所提出的机制可以计算出最优的控制域数量，并且可以实现各控制域内交换机节点数量相对均衡。

2 相关工作

SDN在广域网中部署时需要解决的重要问题是控制平面的可扩展性。由于广域网跨越地域广并且拥有众多交换机节点，这导致单个SDN 控制器难以满足网络需求，因此多控制器架构已成为SDN 网络未来的发展趋势[6]。通过将广域网划分成若干个规模较小、节点数量均衡的SDN控制域，拥有平衡节点数量的控制器的服务能力才能显著提高。目前，在解决控制器部署问题的时候，大部分研究都只是解决了给定控制器数量的情况下的控制器放置问题，很少有研究根据网络拓扑确定控制域的最优数量及划分，之后再部署多控制器的机制。文献[7]解释了控制器在SDN 网络中的放置问题，并且指出了控制器部署问题的关键是确定控制器的数量及位置。文献[8]提出了基于改进的K-means算法，该算法主要用于解决SDN控制器的部署问题。算法初始状态只设一个分区，之后慢慢增加分区数量进行循环迭代。然而文中只关注了控制器到各交换机的距离问题，没有考虑到负载均衡。文献[9]提出了一种基于分簇的网络划分算法（network partition algorithm based on clustering，CNPA）来划分网络，其可以保证每个分区都能够缩短控制器和交换机之间的最大端到端延迟。为了减少控制器的排队等待时间，此文提出了在子网络中放置适当数量的多个控制器，但是没有给出控制器的具体数量。文献[10]提出了使用博弈论解决SDN 控制器部署问题，考虑交换机到控制器的时延、控制器之间的时延和控制器的负载均衡三方面进行博弈，寻求一种均衡方法确定控制器部署的数量和位置。然而，该算法时间复杂度较高，只适用于小型网络拓扑。文献[11]提出了一种弹性方案，在不同的情况下，动态改变控制器的个数和位置，但是依旧不能自动计算出控制域的最优数量。综上所述，目前关于多控制器部署问题的解决方案的前提多是控制器的数量已知，很少有研究根据当前网络拓扑确定出控制域的最优数量。

3 模型建立

3.1 网络建模

本文将控制器管理的交换机的数量定义为控制器的负载，每个控制域内有且只有一个控制器。

将网络拓扑建模为图G(V,E)，其中V代表交换机节点集合，E代表链路集合。实际上，SDN控制域的确定与划分问题就是将图划分成若干个子图。

定义1如果将图G划分成K个子图，则Ni可以被定义为Ni(Vi,Ei)。那么，对集合V中的节点进行聚类，就相当于依据相似度划分集合V，得到互不相交的子集V1,V2,…,VK，即。其中Vi表示第i个控制域，K表示控制域的数量。V中的节点按照它们所处的控制域进行排序的结果如式（1）所示。

本文的目标是寻找一个最优的SDN控制域划分使得各控制域中交换机节点数量尽可能均衡。基于RatioCut 和谱聚类算法[12-13]，本文提出了一种SDN 控制域确定与划分机制，可以实现控制器负载均衡。将控制域划分问题转化成图的切割问题，并利用图论中比较典型的RatioCut 分割算法来进行控制域的划分。通过最小化式（2）中的目标函数可以得到平衡的SDN控制域划分。

其中，vol(Ni)表示子图Ni中节点的总数量，wij表示交换机节点si和交换机节点sj之间的链路的权重，也就是这两个节点的相似度。

3.2 SDN控制域确定模型

本文基于谱图理论[14]设计了SDN控制域确定机制。主要思想是使用线性代数思想研究相似矩阵的性质。首先，介绍了改进相似矩阵建立的方法，然后介绍了利用本征间隙自动计算满足目标分区的SDN控制域的最优数量。

谱聚类算法的性能很大程度上受相似度矩阵的影响。根据对广域网中时延的分析，本文选择传播时延作为相似度矩阵的权重值。对于广域网拓扑来说，交换机si和sj之间的相似度wij可以通过式（3）计算。

其中，si是数据样本点，d(si,sj)是两点之间的距离，σ是自定义的参数。此处d代表节点si和sj之间的传播时延，即节点之间的最短距离。

对于σx的取值，如果只采用不同的σx值进行实验后取划分效果最佳的σx，运算时间将会增加。而且假定σx为固定值，则两个节点之间的相似性仅取决于这两点之间的欧氏距离，并且忽略两点的论据节点的分布情况，这将导致不理想的分区效果。因此本文对相似度函数的计算进行了改进，加入邻居节点分布情况。如式（4）所示。

其中，用σi=d(si,sk)来计算本地σ值，sk是节点si的第k个邻居节点。经过多次实验发现，k取4时划分效果最佳。相似度矩阵建立好之后，根据式Anor(i,j)=得到其规范相似度矩阵Anor。其中D为度矩阵，度值可以用来体现样本点周围数据的分布状况。首先对Anor进行分解得到由大到小的非负特征值，即λ1≥λ2≥…≥λn≥0，然后利用本征间隙序列计算出本征间隙向量，最后使用计算SDN控制域的最优数量K。

3.3 SDN控制域划分模型

本文基于归一化Laplacian矩阵特征向量设计了SDN 控制域划分机制。在SDN 控制域的划分过程中，对Laplacian 矩阵进行谱分解然后聚类可以被用于近似最小化式（2）中的SDNcut，从而获得相对平衡的控制域的划分。

为了使各个控制域之间交换机节点数量相对均衡，本文首先计算Laplacian矩阵，如式（5）所示。

其中，A为相似度矩阵，D为度矩阵，度值可以用来体现样本点周围数据的分布状况。度矩阵是将度值作为矩阵的对角元素的矩阵，如式（6）所示。

获得SDN控制域的最优数量K之后进行控制域的划分。首先，将矩阵L分解成L=X∧XT的形式。矩阵X是L的特征向量按列存储得到的。然后，取矩阵X的前K个最小特征值对应的特征向量组成矩阵M=(x1,x2,…,xK)。最后，定义矩阵M的行是由向量Mi(i=1,2,…,n)构成，如式（7）所示。

其中，式（8）中P是对M的每一行进行归一化之后的矩阵。令，根据式（9）计算特征矩阵行向量的相似度矩阵，并依据该特征矩阵对SDN网络中的节点进行聚类。

当R(si,sj)的结果为1时，说明si和sj属于同一类，当R(si,sj)为0时，说明si和sj为不同的类。如果最终计算的结果恰好为K时，则结束计算；否则，选择不同的flag值重新进行划分。

4 算法描述

在本文中，利用Floyd 算法[15]计算任意两个节点之间的最短路径，然后根据最短路径经过的点来获得控制路径的path集。

算法1SDN控制域确定与划分算法

输入：网络拓扑G，划分标准flag。

输出：控制域的数量K以及控制域的划分结果control。

首先利用Floyd 算法计算网络拓扑G距离矩阵并对该矩阵的每一行从小到大排序；然后计算相似度矩阵，对其规范得到规范相似度矩阵，并按照从大到小的顺序将计算得到的矩阵的特征值进行排序；其次使用相似矩阵A计算得到本征间隙序列，从序列中查找到的第一个极大值所对应的下标就是控制域的数量K。在获得SDN 控制域的数量K后进行控制域的划分，依据矩阵L的前K个最小特征向量之间的相似度进行划分。计算特征向量的相似矩阵，并根据该矩阵对SDN网络中的节点进行聚类，如果聚类结果恰好为K，则说明K为控制域的最优数量；否则，选取不同的flag值重新进行域的划分。

5 性能评价

5.1 仿真设置

本文基于Matlab平台进行仿真实现。在仿真实现中采用CERNET2[16]和DFN（http://www.topologyzoo.org/dataset.html）网络拓扑。其中，CERNET2网络拓扑的节点数量为25，如图1所示；DFN网络拓扑的节点数量为51，如图2所示。

Fig.1 CERNET2 network topology图1 CERNET2网络拓扑

Fig.2 DFN network topology图2 DFN网络拓扑

5.2 性能评价

对于CERNET2网络拓扑，首先，通过控制域确定机制计算得到拓扑中的最优控制域的数量为6。然后，基于此结果分别取控制域数量为3、4、5、6、7、8、9、10，采用本文设计的控制域划分机制进行仿真实验，以控制域中节点数量的方差为衡量标准，根据划分结果计算每个控制域数量下的各控制域中节点数量的方差，方差越小，表示划分结果中每个控制域节点数量波动越小、越均衡。

图3为控制域数量的方差，由图3可以看出，当控制域的数量为6时方差最小，即该数量下各控制域节点数量波动最小、最均衡。该图中没有表示出当控制域的数量为2时的结果，此时两个控制域中节点数量分别为21和4，均匀程度更低。

Fig.3 Variance of control domain number(CERNET2)图3 控制域数量的方差（CERNET2）

当控制域中只有1个控制器时可能导致单点故障。当控制域中的控制器数量大于10时，控制器数量过多，将造成成本增加和资源浪费。

图4是当控制域的数量为6时使用本文的控制域划分算法划分的实验结果。相同颜色的节点表示它们属于同一个控制域。例如，对于图中厦门这一点，距杭州的最大时延为37 ms，厦门到广州的最大时延为26 ms。因此，厦门和广州应分为同一个控制域。对于南京来说，南京到武汉之间的时延是29 ms，从南京到合肥的时延是110 ms。因此南京应该和武汉处于同一个控制域。同理，对于图中的其他节点来说该算法在一定程度上均可以进行正确的划分。

图5为以DFN 网络拓扑为实验拓扑时控制域的划分结果。使用本文的控制域划分算法计算得到的控制域最优数量为8，相同颜色的节点表示它们属于同一控制域。从图5中可以看出，使用本文设计的算法可以得到合理的控制域划分，并且节点数量相对均衡。

Fig.4 Control domain partitioning results(CERNET2)图4 控制域划分实验结果（CERNET2）

Fig.5 Control domain partitioning results(DFN)图5 控制域划分实验结果（DFN）

6 结论与展望

本文研究了SDN控制域确定与划分机制。首先基于本征间隙设计了SDN 控制域确定机制，计算得到最优的控制域数量；其次设计了基于归一化Laplacian 矩阵特征向量的控制域划分机制，可以使得划分结果近似均衡。仿真结果表明本文设计的机制可以计算出合理的控制域数量，并且各控制域节点数量相对均衡。

本文在进行控制域划分时是将控制器所连接的交换机的数量作为控制器的负载；然而在实际情况中，SDN 控制器的负载应该是它所控制的交换机对它的数据请求量，下一步工作是解决这种情况下控制域的划分及优化控制器的负载均衡问题。