软件定义网络(Software Defined Network, SDN)[1]采用与传统互联网截然不同的控制架构，将控制平面与数据平面分离，通过开放和可编程接口实现软件定义[2]。随着网络规模的扩大，典型的单控制器结构已经不能满足用户的需求，单控制器节点的服务能力极有可能成为网络性能的瓶颈，并且带来控制架构难以拓展和单点攻击等一系列问题[3]。因此实现一个逻辑上集中、物理上分布的控制器集群成为解决SDN控制架构可拓展性的良好解决方案。
为了解决单控制器带来的问题，业界提出了多控制器架构，如HyperFlow[4]、Onix[5]、Ethane[6]、Kandoo[7]等。多控制器架构能够有效提高SDN可扩展性，但同时也带来了一系列问题，例如控制平面负载均衡问题。控制平面负载均衡问题是SDN目前面临的主要问题。近年来，研究发现交换机与控制器之间的映射关系是静态的，不能动态适应流量的变化，这一静态关系会造成控制平面负载不均衡[8]。目前为解决交换机与控制器之间的静态映射问题，学术界提出了动态多控制器架构的概念。动态多控制器架构通过实时监控控制平面流量情况，调节控制平面负载，能够有效解决控制平面负载不均衡问题。动态多控制器架构主要从两个方面均衡控制平面负载：1) 迁移过载控制器下交换机至空闲控制器；2) 增减控制器数量。
针对上述控制平面负载不均衡问题，Hock等[9]提出了一种Pareto最优的控制器布局方式(Pareto-based Optimal COntroller placement, POCO)。POCO针对某个控制器失效时如何对多控制器重新布局这个问题，综合考虑控制器性能、容错能力和负载均衡并提出了当控制器失效时对其管理的交换机进行迁移的策略。ElastiCon[10]采用基于窗口的双门限方法动态地迁移交换机实现控制器和交换机之间的动态配置, 以达到均衡控制平面负载的目的，这种策略提高了控制器资源利用率。ElastiCon在负载决策窗口内设置负载阈值，当控制器负载超过上、下门限时，采取增加新控制器、删除已有控制器或迁移交换机等动作。然而上述两种方案都主张将交换机迁移至邻近控制器，虽然减小了网络时延，但是会造成控制器邻近区域负载过大，不能有效均衡控制平面负载。Yao等[11]针对控制器放置问题提出CCPP(Capacitated Controller Placement Problem)算法，CCPP中提及当某个控制器过载时，可以将交换机迁移至控制器容量使用率最低的控制器，这种策略称作利用率最低迁移策略(Lowest Utilization Migration Algorithm，LUMA)。但是LUMA没有考虑控制器和交换机之间的通信时延，导致网络时延较大。陈飞宇等[12]提出的动态交换机迁移算法(Dynamic Switch Migration Algorithm, DSMA)方案把交换机与控制器之间的映射关系建模成0-1规划问题，利用单目标优化免疫粒子群算法首先得到满足控制平面负载均衡要求的一组解，然后考虑控制器与交换机之间的通信开销，在这一组解中选出最合适的交换机控制器部署方案。DSMA能够有效均衡控制平面负载，然而DSMA中单目标优化算法寻优过程只考虑到负载均衡度，没有考虑交换机迁移产生的通信开销，寻优方向过于单一。
基于上述控制平面负载均衡方案的不足，本文提出一种于多目标优化的动态交换机迁移算法(Dynamic Switch Migration Algorithm based on Multi-objective optimization, M-DSMA)。首先, 通过问题建模在理论上对SDN控制平面负载均衡问题进行分析，设计了满足负载均衡度和交换机迁移所产生的通信开销多重约束的目标函数；其次, 设计了一种多目标遗传算法对问题进行处理。M-DSMA可以从负载均衡度和通信开销两个方向寻优，从而权衡负载均衡度和通信开销。
1 问题建模OpenFlow[13]中定义了交换机与多控制器相连的概念，多连接可以有效地避免控制器单点故障问题。OpenFlow将控制器分为三种:Equal控制器、Slave控制器和Master控制器。Equal控制器对交换机具有所有权限，不仅能够接收交换机发来的异步消息(例如PACKET_IN、FLOW-REMOVED消息等)，还可以发送控制器-交换机消息以修改交换机的状态。Slave控制器不接收任何交换机异步消息，但可以处理Slave控制器的角色请求消息。Master控制器与Equal控制器对交换机所具有的权限类似，但每个交换机只能有一个Master控制器，可以拥有多个Equal控制器或Slave控制器。由于Equal控制器、Slave控制器和Master控制器的不同特性，各交换机可以在不同的控制器间平滑无缝迁移。
本文讨论的控制平面负载均衡问题通过优化交换机与控制器映射关系并据此迁移交换机实现。控制平面负载均衡的理想状态是所有的控制器节点都处于较低负载状态，并且交换机迁移所产生的通信开销较小。为了阐述优化交换机与控制器映射关系的过程，引入以下几个概念。
定义1 交换机与控制器之间的映射关系建模成0-1矩阵F=(fij)M×N用于描述交换机与控制器之间的映射关系。
| ${f_{ij}} = \left\{ \begin{array}{l} 1,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{控制器}}{C_j}{\rm{是交换机}}{S_i}{\rm{的Master控制器}}{\kern 1pt} \\ 0,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{其他}} \end{array} \right.$ | (1) |
其中：M表示交换机个数; N表示控制器个数；fij的值为1表示控制器Cj是交换机Si的Master控制器；fij的值为0表示控制器Cj是交换机Si的Equal控制器或Salve控制器。
定义2 负载均衡度。SDN控制器的负载主要由以下四个因素决定[14]：1) 处理PACKET_IN事件；2) 维护本控制器管理域的网络视图；3) 与其他控制器的通信；4) 安装流表项。在不同的网络环境中，处理PACKET_IN事件对负载影响最大，因此把到达控制器的PACKET_IN事件数目作为该控制器的负载值。控制器负载值的计算式如下：
| $L{C_j} = \sum\limits_{i = 0}^M {\left( {{x_i} \times {f_{ij}}} \right)} $ | (2) |
其中：LCj表示控制器Cj的当前负载；xi表示交换机Si发送到控制器Cj的PACKET_IN事件数目。
负载均衡度是为了衡量所有控制器的负载差异情况，因此本文利用标准差表示负载均衡度，如式(3) 所示：
| $\sigma {\rm{ = }}\sqrt {\sum\limits_{i = 1}^N {{{\left( {L{C_i} - \overline {LC} } \right)}^2}} /N} $ | (3) |
其中：
定义3 负载均衡代价的主要组成部分为交换机迁移产生的通信开销，定义通信开销为cost，即交换机与控制器的映射状态从当前映射状态(用F=(fij)M×N表示)到新的状态(用F1 =(fij1)M×N表示)所产生的通信开销。本文用控制器与交换机之间的最小距离表示通信开销cost，如式(4) 所示计算通信开销:
| $cost = \sum\limits_{i = 1}^M {\left( {{m_i}*\left( {{H_{ij}} + {H_{i{j^1}}}} \right)} \right)} $ | (4) |
其中：Hij表示待迁移交换机Si与过载控制器Cj的最短距离；Hij1表示待迁移交换机Si与目标控制器Cj1的最短距离。交换机与控制器映射状态从F=(fij)M×N到F1 =(fij1)M×N，根据式(5) 计算mi值，mi值为0表示交换机Si的状态未发生改变；mi值为1表示交换机Si的状态发生改变。
| ${m_i} = \left\{ {\begin{array}{*{20}{l}} {{\rm{0}},} & {{f_{ij}} = f_{i{j^1}}^1 = 1\;{\rm{且}}\;j = {j^1}}\\ {1,} & {{f_{ij}} = f_{i{j^1}}^1 = 1\;{\rm{且}}\;j \ne {j^1}} \end{array}} \right.$ | (5) |
控制平面负载均衡问题有两个目标：第一个目标是均衡控制平面负载；另一个目标是从当前映射状态转换到新的映射状态只需要最小的通信开销。理论上，控制平面负载均衡度和交换机迁移所产生的通信开销是相互矛盾的两个指标，无法使这两个衡量指标同时达到最优。然而，基于单目标优化的迁移算法寻优方向单一，搜索空间较小，这就造成了优化结果不理想。针对这个问题，本文设计了负载均衡度和交换机迁移所产生的通信开销这两个相互矛盾的目标，使得搜索最优解能力加强，可以取得较好的优化结果。因此可以得出本文交换机部署的多目标优化模型如下：
| $\left\{ {\begin{array}{*{20}{l}} {\min } & {\cos \left( t \right)}\\ {\min } & \sigma \end{array}} \right.$ | (6) |
| ${\rm{s}}{\rm{.t}}{\rm{.}}\quad L{T_j} > L{C_j},\forall j$ | (7) |
| $\sum\limits_{j{\rm{ = }}1}^N {{f_{ij}}{\rm{ = }}1} ,\forall i$ | (8) |
式(6) 是模型的两个目标函数，即在交换机的动态迁移过程中兼顾控制平面负载均衡度和交换机迁移产生的通信开销。约束条件(7) 表示映射状态转换后控制器的负载不能超过其阈值LTj，即要保证迁移交换机之后不会造成其他控制器过载。约束条件(8) 表示每个交换机只能有一个Master控制器。
2 算法M-DSMA描述SDN控制平面的负载均衡问题是非确定多项式完全(Non-deterministic Polynomial Complete, NPC)问题，很难在多项式时间内找到其最优解。遗传算法通过模拟生物进化机制在全局范围内搜索最优解，是解决NP问题的常用技术之一。遗传算法在不需要了解问题域的先验知识的前提下，采用交叉、变异策略使得种群不断靠近最优解区域。本文基于遗传算法的这些优点，提出了一种利用遗传算法进行多目标优化的SDN负载均衡算法。
针对交换机迁移过程中没有考虑通信开销的问题，设计了基于多目标优化的负载均衡算法M-DSMA。M-DSMA的设计主要由以下几个方面构成：对种群进行编码设计、初始化种群、个体评价以及基本的遗传算子。本文提出的M-DSMA算法中多目标进化框架是基于多目标遗传算法NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ)实现的，具体算法流程如图 1所示。
|
图 1 M-DSMA流程 Figure 1 Flow diagram of M-DSMA |
在遗传算法中首先要解决的是问题域的编码问题，只有先将问题进行抽象、编码成为遗传学中的个体，才能形成种群进行选择、交叉和变异等操作。由于本文要优化的目标是控制器与交换机之间的0-1映射关系，所以将问题域中的0-1矩阵转化为遗传学中的个体基因。为了准确描述0-1矩阵中表达的交换机与控制器之间的映射关系，本文利用组编码方式将交换机和交换机的Master控制器结合在一起，即将0-1矩阵F中每行的0和1共同组成一个基因。随后将所有行组成的基因序列串在一起形成一个基因序列组，这个基因序列组构成了遗传个体，多个个体则组成了一个种群。遗传算法基于这个群体迭代生成若干子代，在子代中寻找近似最优解。本文中的初始化种群规模为n=100。
图 2给出了交换机与控制器之间映射关系编码示例。在图 2中，OpenFlow网络中有3个控制器和6个交换机，如图所示交换机S1、S2、S3的Master控制器为C1，S4、S5的Master控制器为C2，S6的Master控制器为C3。用编码100表示某个交换机的Master控制器为C1，同理用编码010表示某个交换机的Master控制器为C2，从而可以得出如图 2所示的交换机与控制器映射关系可表示成长度为3*6位的0-1序列。这个序列的第一个三位子序列表示交换机S1与控制器的映射关系，第二个三位子序列表示交换机S2与控制器的映射关系，所以图 2中个体可编码为100100100010010001。这种编码方式确保了每个交换机只能有一个Master控制器。
|
图 2 交换机与控制器之间映射关系编码示例 Figure 2 Example of mapping relationship between switch and controller |
遗传算法是对群体进行的进化操作，需要生成初始种群，初始种群的生成是随机的。本文中设置初始种群规模n=100。
2.2 操作算子编码完成之后，遗传算法需要对初始种群迭代生成若干子代，在子代中寻找近似最优解，达到进化的目的。种群的进化离不开个体的评价和基本的遗传算法操作算子，遗传算子主要包括选择算子、交叉算子和变异算子。
2.2.1 选择运算选择运算是从子代中选择较优的个体作为新一代父体，继续重复迭代过程。个体的优势是通过定义适应度函数来衡量的，而适应度函数是以个体的属性(如：个体的负载均衡度和迁移交换机产生的通信开销)为基础的。
2.2.2 适应度函数适应度函数的目的是衡量个体优劣性，从而选择较优的个体作为遗传的父代个体。本文借助NSGA-Ⅱ算法定义适应度函数，NSGA-Ⅱ算法中对个体的评价主要有以下三个步骤：
1) 快速非支配排序算子设计，多目标优化问题的设计关键在于求取Pareto最优解集，NSGA-Ⅱ算法中的快速非支配排序依据目标函数对种群进行分层。本文中根据每个个体(即一种交换机与控制器映射关系)的负载均衡度、通信开销计算个体的等级，同一等级可能包含多个个体。
2) 个体拥挤距离算子设计，为了在同一等级的个体中进行选择性排序，NSGA-Ⅱ算法提出个体拥挤距离的概念。为了避免陷入局部搜索，个体拥挤距离的计算基于个体属性的分布，个体属性值分布密集则个体拥挤距离越小；反之，个体拥挤距离越大。个体之间拥挤距离越大，该个体越优。
3) 精英策略选择算子设计，精英策略是指保留父代个体中的优秀个体作为子代，防止获得的Pareto最优解丢失。
2.2.3 交叉运算交叉算子是指在父本个体和母本个体的基因序列上随机地选择一个或者多个基因位点作为交叉点，然后交换这两个个体上对应的部分基因序列。交叉的发生具有一定的概率性，如果交叉发生的概率过大，那么遗传算法能够搜索到更多的解空间，但是搜索能力增强的同时带来了更多性能上的不稳定。相反，如果交叉发生的概率太小，遗传算法搜索问题最优解的速度将会放缓，甚至出现种群停滞不前无法进化的情况。一般的交叉概率设置在0.25到1.00之间，本文设置交叉概率为0.8。本文采用单点交叉，交换个体A和个体B交叉点及其之后全部的基因序列，如图 3所示，交叉运算主要由以下2个步骤组成：
|
图 3 交叉实例示意图 Figure 3 Schematic diagram of the crossover-example |
1) 在父代个体上随机选择一个基因作为交叉点，个体A和个体B的交叉点位置相同，如图 3(a)中所示，个体A的基因为100001100010010001，交叉点基因为100；个体B的基因为100010010010001001，交叉点基因为010。
2) 个体A、B上的交叉点基因分别为100和010，如图 3(b)所示，交换这两个基因及其之后的所有基因。交叉运算之后得到个体A、B的基因分别为100001010010001001、100010100010010001。交叉结果表示个体A中交换机S3的Master控制器由C1变为C2，交换机S5的Master控制器由C2变为C3；个体B中交换机S3的Master控制器由C2变为C1，交换机S5的Master控制器由C3变为C2。
2.2.4 变异运算在繁殖过程中，新产生的个体的基因会以一定的概率出错，这一行为称为变异，变异能够增加新的信息以扩大搜索空间。变异操作也是按一定概率进行的，较低的概率可防止群体中重要而单一的基因的丢失，而较高的概率会使得遗传算法趋于纯粹的随机搜索，本文根据经验值设定变异概率值为0.2。如图 4中所示，变异有以下2个步骤：
|
图 4 变异实例示意图 Figure 4 Schematic diagram of the mutation-example |
1) 在个体上随机选择变异点。如图 4(a)所示，个体基因为100100010010100001，随机选择变异点，变异点基因为100，表示交换机S5的Master控制器为C1。
2) 改变变异点基因。遵循一个交换机只能有一个Master的原则，变异点基因序列中必须仅有一个基因位为1。如图 4(b)所示，更改变异点基因为001，表示交换机S5的Master控制器为从C1变为C3。变异运算之后得到个体基因为100100010010001001。
|
图 5 控制器负载分布 Figure 5 Load distribution of the controller |
在Mininet[17]上建立多控制器拓扑，本文模拟了5个控制器与20个交换机的网络。通过增加某些交换机发送PACKET_IN包的速率使得某些控制器过载，引起控制平面负载不均衡触发M-DSMA算法。为了说明基于多目标遗传的M-DSMA算法能够有效地权衡负载均衡度和迁移交换机产生的通信开销，与基于单目标优化的负载均衡算法DSMA作对比实验。图 5表示分别运行M-DSMA算法和DSMA算法、交换机迁移前后控制器负载值的变化情况。
图 5中虚线表示控制器负载阈值，可以看出迁移前有两个控制器发生过载，分别使用DSMA和M-DSMA这两种负载均衡方案后，控制平面负载都得到了有效均衡，所有控制器负载均低于控制器负载阈值。通过实验数据可以计算得出迁移前后控制平面负载均衡度分别为：σ迁移前=1 692 packet/s，σDSMA=211.485 6 packet/s，σM-DSMA=57.693 7 packet/s。从计算结果中可知，多目标优化算法效果比单目标优化算法负载均衡效果好。
图 6~7分别表示单目标优化和多目标优化搜索最优解的过程。单目标优化算法依据负载均衡度这个目标搜索一组最优解。
|
图 6 单目标求解过程 Figure 6 Solving process of the single objective |
|
图 7 多目标求解过程 Figure 7 Solving process of the multi-objective |
从图 6可以看出，随着迭代次数的增加，种群中最优的负载均衡度逐渐减小，说明单目标优化算法能够实现控制平面负载均衡。多目标优化算法依据负载均衡度和通信开销这两个相互矛盾的目标搜索最优解，可以找到较好的交换机控制器部署关系。从图 7可以看出，第1代种群、第50代种群、第100代种群的分布情况，随着迭代次数的增加，Pareto前沿面趋向于原点，说明多目标优化算法能够有效权衡负载均衡度和通信开销，负载均衡度和通信开销均可以取得较优解。
M-DSMA兼顾负载均衡度和通信开销，且这两个指标均优于DSMA。如图 8~9所示，实验中通过提高部分交换机发包速率来逐次提高负载均衡度，模拟多次不同的交换机与控制器重新布局，从而得出负载均衡度和通信开销对比图。图 8为负载均衡度对比，从图 8可以看出，M-DSMA能够大幅度降低负载均衡度，更有效地均衡控制平面负载。图 9为通信开销对比，从图 9可以看出，多次实验中M-DSMA的通信开销始终小于DSMA通信开销，说明M-DSMA能够在均衡控制平面负载的同时更加有效地兼顾通信开销。根据每次实验结果取平均值，计算得出：相比于算法DSMA，算法M-DSMA降低了30%~50%的通信开销
|
图 8 负载均衡度对比 Figure 8 Comparison of the load balancing degree |
|
图 9 通信开销对比 Figure 9 Comparison of the communication overhead |
本文针对交换机与控制器之间静态映射关系导致的负载均衡问题，提出了基于多目标优化的负载均衡方案M-DSMA。M-DSMA以负载均衡度和迁移交换机产生的通信开销为优化目标，采用遗传算法找到交换机分布的近似最优解。仿真实验结果表明，与基于单目标优化的均衡算法DSMA相比，M-DSMA能够有效均衡控制平面负载，同时降低迁移交换机产生的通信开销。然而，本文只关注了在控制器资源能满足交换机流请求下交换机如何迁移的情况，对于需要添加新控制器的情况，将在下一步的工作中继续研究。
| [1] | MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow:enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74. doi: 10.1145/1355734 |
| [2] | 黄韬, 刘江, 魏亮, 等. 软件定义网络核心原理与应用实践[M]. 北京: 人民邮电出版社, 2014 : 4 -5. ( HUANG T, LIU J, WEI L, et al. Software Define Network Core Principle and Application Practice[M]. Beijing: Posts & Telecom Press, 2014 : 4 -5. ) |
| [3] | TOOTOONCHIAN A, GORBUNOV S, GANJALI Y, et al. On controller performance in software-defined networks[C]//Hot-ICE'12:Proceedings of the 2012 2nd USENIX Conference on Hot Topics in Management of Internet, Cloud, and Enterprise Networks and Services. Berkeley, CA:USENIX Association, 2012:10-10. |
| [4] | TOOTOONCHIAN A, GANJALI Y. HyperFlow:a distributed control plane for OpenFlow[C]//INM/WREN'10:Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking. Berkeley, CA:USENIX Association, 2010:3-3. |
| [5] | KOPONEN T, CASADO M, GUDE N, et al. Onix:a distributed control platform for large-scale production networks[C]//OSDI'10:Proceedings of the 2010 9th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA:USENIX Association, 2010:351-364. |
| [6] | CASADO M, FREEDMAN M J, PETTIT J, et al. Ethane:taking control of the enterprise[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(4): 1-12. doi: 10.1145/1282427 |
| [7] | YEGANEH S H, GANJALI Y. Kandoo:a framework for efficient and scalable offloading of control applications[C]//HotSDN'12:Proceedings of the First Workshop On Hot Topics In Software Defined Networks. New York:ACM, 2012:19-24. |
| [8] | YAO G, BI J, GUO L Y, et al. On the cascading failures of multi-controllers in software defined networks[C]//Proceedings of the 2013 21st IEEE International Conference on Network Protocols. Piscataway, NJ:IEEE, 2013:1-2. |
| [9] | HOCK D, GEBERT S, HARTMANN M, et al. POCO-framework for Pareto-optimal resilient controller placement in SDN-based core networks[C]//Proceedings of the 2014 IEEE Network Operations and Management Symposium. Piscataway, NJ:IEEE, 2014:1-2. |
| [10] | DIXIT A, HAO F, MUKHERJEE S, et al. Towards an elastic distributed SDN controller[C]//HotSDN'13:Proceedings of the 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York:ACM, 2013:7-12. |
| [11] | YAO G, BI J, LI Y L, et al. On the capacitated controller placement problem in software defined networks[J]. IEEE Communication Letters, 2014, 18(8): 1339-1342. doi: 10.1109/LCOMM.2014.2332341 |
| [12] | 陈飞宇, 汪斌强, 孟飞, 等. 一种软件定义网络中交换机动态迁移算法[J]. 计算机应用研究, 2016, 33(5): 1446-1449. ( CHEN F Y, WANG B Q, MENG F, et al. Dynamic switches migration algorithm in software defined networks[J]. Application Research of Computers, 2016, 33(5): 1446-1449. ) |
| [13] | REN T T, XU Y W. Analysis of the new features of OpenFlow 1.4[C]//Proceedings of the 2nd International Conference on Information, Electronics and Computer. Amsterdam:Atlantis Press, 2014:73-77. |
| [14] | CHENG G, CHEN H, HU H, et al. Dynamic switch migration towards a scalable SDN control plane[J]. International Journal of Communication Systems, 2016, 29(9): 1482-1499. doi: 10.1002/dac.v29.9 |
| [15] | 邓莉, 姚力, 金瑜. 云计算中基于多目标优化的动态资源配置方法[J]. 计算机应用, 2016, 36(9): 2396-2401. doi: 10.11772/j.issn.1001-9081.2016.09.2396 |
| [16] | DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017 |
| [17] | DE OLIVEIRA R L S, SHINODA A, SCHWEITZER C M, et al. Using Mininet for emulation and prototyping software defined networks[C]//Proceedings of the 2014 IEEE Colombian Conference on Communications and Computing. Piscataway, NJ:IEEE, 2014:1-6. |