SDN多控制器部署及流量均衡研究*

陈俊彦，李 玥，梁楚欣，雷晓春

(1.桂林电子科技大学计算机与信息安全学院，广西 桂林 541004;2.广西云计算与大数据协同创新中心，广西 桂林 541004)

1 引言

现有的网络中，单个控制器已经无法满足网络需求，控制器负载过高导致网络性能下降。软件定义网络SDN(Software Define Network)可以很好地解决这些问题。软件定义网络(SDN)是一种新型的网络架构，其核心是将交换机网络的控制平面和数据平面分离[1]，交换机只负责数据转发，控制功能由控制器来负责，此外，SDN还可利用控制平面的北向接口进行编程，大幅提高了网络的灵活性。本文在SDN架构中，利用改进的k-means++算法对网络进行划分，相比k-means算法的划分结果要更均衡，在成本相同的情况下负载差异度更低，从而得出多控制器部署的最佳方案；然后利用网络流量均衡算法，对多条路径转发的情况采取流量均衡策略，使流量分配更均衡，从而大幅提高网络的性能。

2 相关研究

针对多控制器的部署和网络流量均衡问题，相关研究人员提出了许多解决方案。覃匡宇等[1]就受时延和容量限制的多控制器部署问题，提出在谱聚类的基础上，为聚类算法增加均衡部署的目标函数，并对多控制器部署算法引入惩罚函数来防止出现孤立点。Das等[2]基于Steiner树的控制器间延迟模型，提出了一个多目标整数线性规划方法，以推导无故障时控制器优化配置的同步代价场景，以及对单链路故障的恢复能力。Yang等[3]研究了单链路和多链路故障下的SDN控制器配置问题。张栋等[4]研究了分层分布式控制平面控制器配置问题，采用多级k路开关划分算法对大系统进行划分，以扩展网络拓扑。Chen等[5]提出了一种新的社区检测控制器部署方法，借助复杂网络分析理论，将待部署控制器的网络拓扑视为一个由多个社区组成的网络，然后在每个社区中选择一个合适的位置放置控制器，避免了全局部署的复杂性。史文根等[6]提出了一种控制器的放置和调整策略，主要包括用于初始控制器配置的遗传算法和平衡控制域算法，以及一种动态在线调整算法，即长期动态控制中的在线调整算法。鲁垚光等[7]提出了一种基于链路偏好的随机路由算法和2种流调度算法，实现了动态负载均衡和节能。Lu等[8]根据目标将控制器配置问题分为延迟、可靠性、成本和多目标4个方面，并分析了不同应用场景下的具体算法。Wang等[9]利用带内环境，即所有交换机通过专用交换机连接到一个控制器的设计，设计了一个由负载收集器、负载平衡器和交换机迁移器组成的负载调整机制。Wang等[10]提出了一种同时考虑负载平衡、连通性和延迟的多控制器布局算法。

上述多控制器部署及网络负载均衡方案均未考虑拓扑中的网络带宽及时延。因此，本文将链路带宽和传输延迟作为网络边的权重，针对网络对于控制器负载均衡的需求，利用负载差异度来表示控制器所管理交换机个数的差异程度，得出最优的多控制器部署策略。

3 控制器部署模型

本文通过改进的k-means++聚类算法对多控制器进行划分，所得到的控制器的部署位置是根据某些规则在交换机节点中选出的，所以将控制器和交换机之间的时延理想化为零，只考虑交换机之间的时延。

将SDN网络建模为一个无向图G=(V,E)，其中，V表示交换机集合，E表示交换机间链路的集合。聚类算法将网络划分为k类，每一类的交换机仅由一个控制器控制，即网络中需要k个控制器。设定网络中交换机的个数为M，控制器j所管理的交换机集合表示为CVj，每个控制器所能管理的交换机上限为n个[1]。

交换机集合表示如式(1)所示：

V={v1,v2,…,vM}

(1)

控制器的集合表示如式(2)所示：

C={c1,c2,…,ck}

(2)

控制器j所管理的交换机如式(3)所示：

CVj={vi|vi∈V,vi由控制器j管理,

1≤i≤M,1≤j≤k}

(3)

3.1 多控制器部署算法

k-means算法是一种经典的无监督聚类算法，其核心思想如下所示：首先随机产生k个点作为网络中k个类的聚类中心，计算图中所有点到这k个聚类中心的距离，将这些点划分到距离最近的一个聚类中心所属的类中，完成第1次划分。随后在第1次划分中所得的k个类中重新选择聚类中心，再按第1次的方法重新计算并归类，至结果不发生变化为止[3]。

k-means算法存在一些缺陷，首先，算法的k值需要预先设定，然后算法根据设定的值来进行分类。但是，在实际的大型网络中，网络复杂，很难在初始时便确定聚类个数，所以预先设定k值容易导致设定错误，从而导致划分结果并不是最优结果。其次，k-means算法起初是随机选择聚类中心的，而这个初始的聚类中心则是后续计算的基础，所以对结果的影响较大，容易造成初始得到的聚类中心不佳从而导致划分结果不均衡。最后，聚类的划分以迭代的方式进行，若网络较复杂，则需要多次计算，从而导致算法开销加大[5]。

在网络的实际划分中，k值代表了将网络划分为k个类，而在SDN网络中也可代表需要k个控制器。将交换机和控制器之间的时延问题抽象为点到聚类中心的距离问题，即抽象为图的最短路径的问题。

对于k-means算法中随机选择聚类中心而导致结果不一定最优的问题，研究人员提出一种改进算法k-means++。在聚类中心的选择上，k-means++算法将距离较远的节点作为初始聚类中心，并且这个节点是从已有的点中选择的。然后计算图中其他点到此聚类中心的距离，距离越大则下次迭代时作为新的聚类中心的概率就越大，至聚类中心不再发生变化，则完成初始聚类中心的选择。随后对于网络的划分步骤与k-means算法的相同。

k-means++算法改良了k-means算法对于初始聚类中心选择过于随机的问题，通过多步计算得到初始聚类中心，提高了算法的准确度。但是，k-means++算法并未考虑网络中边的权重，容易造成某条链路流量过高，负载过大，所以还要加入其它约束条件。

本文提出一种改进的k-means++算法对多控制器进行划分，该算法将链路带宽和传输延迟作为网络边的权重，即点与点之间的距离。交换机不同，所拥有的带宽也不同。而交换机在图中所连接的交换机个数不同，传输延迟也不同。本文按节点的度来衡量，度越大，则所连接的点越多，即所连的交换机越多，传输延迟越大，边的权重如式(4)所示:

α*bw+β*delay

(4)

其中,bw为链路带宽，delay为传输延迟，α与β是2个因素的权值。同时，针对网络对于控制器负载均衡的需求，本文用负载差异度来表示控制器所管理交换机个数的差异程度。计算方法如式(5)所示：

(5)

3.2 网络流量均衡算法

本文提出一种基于存储桶权重的多路径网络流量均衡算法。首先通过深度优先搜索算法得出网络中存在的所有路径，然后根据路径成本实施流量均衡策略。本文在计算路径成本时，参考了OSPF(Open Shortest Path First)协议中对接口成本的计算方法。成本与带宽成反比。首先计算单条路径的成本，然后累加求和得出多条路径的成本，最后计算每条路径的存储桶权重。在OpenFlow协议中，存储桶权重越高，优先级越高，即优先选择存储桶权重高的路径。

单条路径的成本sw的计算公式如式(6)所示：

sw=1/bw(Mbps)

(6)

设有m条路径，则其总成本SW的计算公式如式(7)所示：

(7)

单条路径的存储桶权重(cw)的计算公式如式(8)所示：

(8)

由以上公式可得，路径成本越低，所得存储桶权重越高，在OpenFlow协议中，存储桶权重越高，优先级越高。在流量均衡策略中，优先选择优先级高的路径。

4 实验与分析

4.1 多控制器部署

本文将SDN多控制器和交换机之间的关系抽象为无向连通图，将控制器和交换机之间最小时延的问题建模为节点之间最短路径的问题。所选用的网络拓扑结构如图1和图2所示。

Figure 1 Biznet topology图1 Biznet拓扑

Figure 2 Claranet topology图2 Claranet拓扑

k-means算法和本文提出的算法对2个网络拓扑的划分结果图如图3～图6所示。

Figure 3 Partition result of Biznet by k-means(k=4)图3 k-means对Biznet划分结果(k=4)

Figure 4 Partition result of Biznet by the proposed algorithm(k=4)图4 本文算法对Biznet划分结果(k=4)

Figure 5 Partition result of Claranet by the proposed algorithm (k=3)图5 本文算法对Claranet划分结果(k=3)

Figure 6 Partition result of Claranet by k-means(k=4)图6 k-means对Claranet划分结果(k=4)

Figure 7 Comparison of Biznet network load difference图7 Biznet网络负载差异度对比

Figure 8 Comparison of Claranet network load difference图8 Claranet网络负载差异度对比

根据算法划分结果和负载差异度的计算公式，得出每个结果的负载差异度，将2种算法进行比较得出最优的多控制器部署策略。

⑮帕诺斯·艾烈珀洛斯:《基提翁的芝诺和庄子的德性与幸福》，彭荣译，《商丘师范学院学报》2015年第1期。

实验所得网络负载差异度如图7和图8所示。

对于聚类中心k值的选取，本文采用负载均衡度作为基本衡量指标，综合部署成本、实际流量等情况选取最佳k值。

通过实验分析可得，本文提出的算法对Claranet拓扑进行聚类时，由于算法在选择初始聚类中心点时进行了改进，所以负载差异度较k-means的小。在划分为3、4个类时，即k=3、k=4时，k-means和本文算法的负载均衡度均为下降趋势，但在划分类增多时，其负载均衡度反而会上升，但本文算法的负载均衡度始终比k-means的要小。由实验结果可知，对于Claranet拓扑的划分，本文算法将其划分为3个类和4个类时的负载均衡度相似，k值代表网络中控制器的个数，k=3比k=4要减少一个控制器，即成本更低。

4.2 网络流量均衡

本文采用Mininet对上述Biznet网络拓扑进行仿真实验。控制器采用ryu控制器，主机为h1和h2。

实验假设主机h1为客户端，h2为服务端。观察拓扑可得h1和h2传送数据的线路有2条，分别为h1-S12-S10-h2(路径1)和h1-S12-S11-S10-h2(路径2)。反之同理。故本次仿真实验选择S10来观察数据传送情况，以分析网络中流量均衡情况。

首先令客户端h1向h2发送5个数据包。h1传送的数据包如图9所示，h2接收的数据包如图10所示。

Figure 9 Data packets transfered by h1图9 h1传送数据包

Figure 10 Data packets received by h2图10 h2接收数据包

查看交换机S12端口的流表信息(如图11所示)和组表信息(如图12所示)，分析数据传送是否成功。

Figure 11 S12 flow table content of switch图11 交换机S12流表内容

Figure 12 S12 group table content of switch
图12 交换机S12组表内容

Figure 13 S12 port data of switch 图13 交换机S12端口数据

由图11和图12的交换机S12端口的流表和组表数据可知，控制器下发了2个流给交换机来实现数据转发，其中的group值与组表中的group值相同，表明流操作是由ID为96196854的组进行的，且数据传送成功。

同时通过组表信息可得端口1的存储桶权重为7，端口2的存储桶权重为3，2个端口存储桶权重比值为7/3≈2.33。由图13的交换机S12端口数据可知，端口1发送数据包(tx pkts)个数为2 062 375，端口3发送数据包(tx pkts)个数为966 178，比值为2062375/966178≈2.13。

综上所述，在网络流量均衡的策略下，网络根据存储桶权重进行分配，可以使数据包均衡地在网络上进行传送，从而不会出现某一条路径流量过大、负载过高导致网络性能下降的情况。

5 结束语

本文通过改进的k-means++聚类算法将网络划分为多类，将链路带宽和传输延迟作为无向图边的权重引入聚类算法，得出划分结果后，再通过负载差异度的计算分析和控制器成本的综合考量，得出最优的多控制器部署方案。随后通过网络流量均衡算法，使数据包在有多条路径可选择的情况下合理选择传送路径，使网络中各个路径的负载均衡，避免因大量数据包涌入同一端口而导致网络性能下降等问题。

未来可以在流量均衡策略中增加多个约束条件，而不是只根据存储桶权重来决定优先级。