0 引言

    软件定义网络(Software-Defined Networking，SDN)多域控制器部署解决了可扩展性和灵活性的问题^[1-2]，由于流量的传输具有时间性和空间性^[3]，在某个时间段或者某个域内会出现流量激增和瞬减，因此在各个子域中的控制器的流量负载情况不尽相同，从而导致该域的控制器出现过载和轻载的状况，不利于整个网络架构的稳定和控制器负载均衡^[4]。

    针对该问题，本文提出了一种面向SDN控制器负载均衡的交换机自适应迁移策略。首先将SDN网络划分为各个子域，对各子域内控制器的负载进行测量，将测量数据传到数据中心，根据测量情况动态地设置控制器过载判定门限值，判断在各SDN子域是否存在过载的控制器；然后基于自适应遗传算法^[5]把过载控制器所在SDN子域作为交换机迁移过程的迁出域，选择该子域的相邻最优子域作为交换机的迁入域；最后应用生存期和淘汰机制将迁出域内负载度高的交换机迁移至迁入域，从而实现整个网络的负载均衡，提升了网络可靠性。

1 模型构建

    在SDN多域网络中，扁平式分布架构的引入会引起各个SDN子域内控制器负载不均衡^[6]，在这里，通过对交换机流量和控制器的负载进行测量，选择迁入和迁出子域，将迁出域内的负载度高的交换机迁移至相邻的迁入域内，实现了控制器负载和交换机数量在SDN子域的均衡部署。

    为了实现所设计功能，将SDN的子域中的模块分为交换机链路模块、控制器模块、迁移模块三大部分，如图1所示。

    底层的交换机和物理链路表示该子域的交换机链路模块，由多个交换机通过物理链路连接构成。往上是控制器模块，负责管理网络中的流量和拓扑。迁移模块位于顶端，网络中的各个控制器都与迁移模块相连接，负责和协调交换机在各个SDN子域内的有效迁移。

1.1 交换机链路模块

    一个完整的SDN网络被切分成各个SDN子域，因此各个交换机群组也被归类到不同的SDN的子域中。假设所有的交换机都支持OpenFlow协议^[7]，主要执行数据转发。一个完整的OpenFlow交换机如图2所示，包括流表、安全通道及OpenFLow协议三部分，交换机与交换机之间、交换机与控制器之间由物理链路相连接。

1.2 控制器模块

    不同的SDN控制器归属于不同的SDN子域，负责管理该子域的网络，并与其他域的SDN控制器进行相互通信。对SDN控制器的内部模块进行划分，主要分为5个部分：(1)南向接口，主要负责与数据平面通信；(2)负载收集与测量模块，负载收集该控制器的负载信息，并聚合其他控制器的负载信息；(3)评估与决策模块，负责评估控制器负载是否超过预设的门限值，根据各控制器的负载情况进行决策，设定动态门限值；(4)存储模块，储存子域内所有交换机的链路消息、拓扑消息和流量消息；(5)北向接口，负责与应用平面进行通信。

1.3 迁移模块

    迁移模块根据评估和决策的结果协调各个SDN子域，实行迁移策略，选择迁出和迁入域，将迁出域内高负载度的交换机迁移至迁入域内，完成控制器的负载均衡和交换机部署均衡。

2 设计实施

2.1 负载收集与测量

    (1)控制器负载的收集

    在SDN网络中，控制器的负载主要由以下4个部分构成：①待处理的Packet_In 的事件数(P)；②维护其管理域和全局的拓扑所需的流量(F)；③与其他控制器的通信开销(K)；④安装上层应用产生的流表项(N)。每个部分在不同控制器中所占的权值不同，设定相应的权值分别对应为u₁、u₂、u₃、u₄。因此可以得到控制器负载的计算公式为：

    (2)交换机负载的测量

    基于分布式SDN多域部署将整个网络划分为多个SDN子域，利用图论的知识，设网络拓扑为G(V，E)，其中，V代表网络中交换机，E代表交换机之间的链路。将网络划分为N个子域，各个子域可表示为S_i(W_i，L_i)，其中，W_i表示子域S_i中的交换机，L_i表示S_i中的链路，有：

    定义 交换机负载度。交换机向控制器请求的Packet_In 的事件数定义为交换机的负载度，设为f_k。

2.2 控制器过载判定

    由于交换机流量在时间和空间上的波动性，有可能导致各SDN子域控制器负载不均衡，因此本文设计了一种控制器过载的动态判定机制。设置动态门限L_A，子域S_i中控制器的负载值为C_i，判定过载门限值设为ε，则L_A如式(7)所示：

2.3 选择与迁移策略

    选择与迁移策略主要包含两部分内容：(1)基于自适应遗传算法的迁入和迁出域选择策略；(2)基于存活期和淘汰机制的交换机动态迁移策略。首先利用自适应遗传算法搜索能力强的特点，设定适应度函数作为度量，在进化过程的每一代，动态地选择交叉概率P_c和变异概率P_m，选择出实施迁移的最佳SDN子域。然后计算出迁入和迁出SDN子域的相对平均负载度，动态地计算出两个SDN子域的迁移率，根据迁移率确定可进行迁移交换机的数目，按照交换机负载度的高低进行排序，应用存活期和淘汰机制把迁出域内一定数目的高负载度交换机迁移到迁入域内，从而实现SDN多域控制器的负载均衡和交换机的部署均衡。

2.3.1 迁出域和迁入域选择

    将控制器负载最大的子域设为迁出域，设为Sh。迁入域的选择是综合考量各类影响因素后得到的结果，不仅要考虑候选SDN子域的控制器负载情况(记为C)，还要考虑到迁入域和迁出域之间的传输时延(记为D)，迁入过程所产生的通信流量记为T。设目标函数为Q，如式(8)所示：

    在迁出域的相邻子域中，将具有最小目标函数Q_min所在的子域设为迁入域，记为S_l。本文采用自适应遗传算法来求取目标函数的最小值Q_min。

    自适应遗传算法中的要素进行如下设定：

    (1)编码设计

    在这里本文采用二进制编码，将原问题表示为一个二进制的0~1字符串的形式，然后在位串空间上进行迭代遗传操作，得到的结果再通过解码的过程来还原成其解空间的解。例如，(0，1，1，0，1，0)就是一个长度为6的二进制编码染色体。

    (2)适应度函数

    适应度函数是对遗传算法中解的好坏进行度量的一种标准，在这里选取目标函数Q作为该算法的适应度函数，根据适应度函数计算个体的适应度。

    (3)交叉和变异

    自适应遗传算法中的交叉操作是指两个将相互配对的个体按照一致交叉的方式相互交换部分基因，从而形成两个新的个体，交叉概率为P_c。与之类似，变异操作是指将个体的染色体编码串中的某些基因座上的基因值用该基因座上的其他等位基因来替换，形成新的个体，记变异概率为Pm。

    算法1：迁入、迁出域选择算法

2.3.2 交换机自适应迁移策略

    基于算法1得到整个网络中所要迁入和迁出域，然后计算出迁入和迁出的两个SDN子域的相对平均负载度，得到两个SDN子域的迁移率。根据迁移率选择一定数目的交换机，使得迁出域里负载度高的交换机迁移到迁入域内，并加入存活期和淘汰机制，防止在迁移过程中有多个迁出域对应一个迁入域时，迁入域内有过多的交换机迁入，造成该迁入域负载骤增，产生二次迁移问题，平衡了各SDN子域内交换机的数量。

    (1)迁移率的调整

    迁移率是对SDN子域的迁入和迁出能力的定量描述，通过迁移率的比较与计算可以得出能够迁入和迁出交换机的最佳数量。

    式(10)中两个SDN子域的一个平均负载度为0，另一个为极值时，M(q，p)=0，需要满足条件d+e=0。

    (2)基于存活期的淘汰机制

    本文设计了一种基于存活期和淘汰机制的交换机自适应迁移算法，即对参与迁移的交换机计算其存活期，若迁入个体年龄大于它的存活期就要被淘汰，不再参与迁移过程。

    存活期基于以下两个原则：①负载度低的交换机的存活期大于负载度高的交换机的存活期；②当某个SDN子域的交换机规模过大时不再接收新的交换机。

    在此，为交换机设定两个参数：年龄Y(X_j)和寿命L(X_j)。交换机X_j每经过一次迁移流程，称为一代，其年龄加1，其存活的代数不能超过其存活期L(X_j)。为了防止子域的交换机数量过多或过少，引入规模控制门限值R，f(X_j)为交换机的负载度函数值，当前域的最大、最小和平均负载度分别为f_max、f_min、f_avg，设置在SDN子域中交换机最大数目为M_max。规模控制门限值R为：

其中，min LT是允许最小寿命，max LT是允许最大寿命。

    算法2：交换机自适应迁移算法

3 性能评估

    本文应用基于Ryu的分布式SDN控制器^[8]，在此基础上添加了收集与测量模块、评估决策模块和存储模块，并编写了迁移模块来负责整个域内交换机的迁移。运用Cbench^[9]软件，使用Mininet^[10]来模拟整个网络拓扑，通过模拟一定数量的交换机连接到控制器，发送Packet-In消息，并等待控制器下发flow-mods消息来衡量控制器的性能。

    模拟一个具有5个控制器和100个交换机的网络拓扑，将整个网络划分为5个SDN子域，每一个子域内各部署一个控制器，使用Mininet来模拟整个网络拓扑。首先为了说明本文所述迁移机制的有效性和均衡性，采用模拟主机在网络中进行发送数据包，在交换机上产生大量的流量负载，将本文所采用的交换机自适应迁移策略(Adaptive Migration Policy，AMP)、ElastiCon^[3]提出的就近迁移策略(Nearest Migration Policy，NMP)和随机迁移策略(Random Migration Policy，RMP)进行对比。控制器负载率代表控制器所承受的负载与可承受最大负载的比值，如图3所示，对比3种策略下控制器负载率随时间的变化。

    从图3中可以看出，刚开始时设定3种策略下所属的控制器都处于过载状态，随着时间的推移，随机迁移策略RMP对于要迁移的SDN子域随机选择，导致曲线处于无规律波动状态，有所下降但波动幅度较大；在0~60 s内，就近迁移策略NMP和自适应迁移策略AMP呈下降趋势；大约60 s迁移过程完成之后波动幅度较小，趋于稳定，但AMP的相对负载率在0.76左右比起RMP的0.91有明显的下降，交换机迁移效率提升了19.7%，表明采用本文提出的自适应迁移策略可以使过载控制器的负载率得到明显改善，控制器资源得到充分的调动，各个控制器的负载更加均衡。

    如图4所示，在前60 s内，由于交换机的迁出，迁出域控制器的负载基本上是呈现明显的下降趋势，且迁入域由于有部分负载度高的交换机从迁出域中迁移过来，因此迁入域控制器的负载有一定程度的上升；在60 s之后，两个域内的控制器的负载基本处于均衡状态，由数据统计可以看出，迁出域控制器的初始负载值是设定为1 400 Request/s，迁入域控制器的初始负载值设定为800 Request/s，经过迁移之后，迁出域控制器负载值变为1 133 Request/s，相对于初始值降低了19.1%，同时迁入域控制器负载值变为为1 041 Request/s，都低于控制器过载判定门限值1 300 Request/s，迁出域和迁入域的负载得到了很好的均衡。

4 结论

    本文针对SDN多域部署下各个子域控制器之间的负载不均衡问题，设计了基于自适应遗传算法的迁入、迁出域选择机制，根据迁移率，存活期和淘汰机制在迁出域中选择一定数目的交换机迁移到迁入域中，实现了各SDN子域控制器的负载均衡和交换机在各子域内的均衡部署。

参考文献

[1] HU T，LAN J，ZHANG J.Bidirectional matching strategy for multi-controller deployment in distributed software defined networking[J].IEEE Access，2018，6：14946-14953.

[2] HU T，YI P，ZHANG J，et al.Reliable and load balance-aware multi-controller deployment in SDN[J].China Communications，2018，15(11)：184-198.

[3] DIXIT A， HAO F， MUKHEＲJEE S，et al．Towards an elastic distributed SDN controller[C].HotSDN′13.New York:ACM,2013: 7-12.

[4] ZHONG H，FANG Y，CUI J.LBBSRT：an efficient SDN load balancing scheme based on server response time[J].Future Generation Computer Systems，2017，68：183-190.

[5] 梁霞.改进的自适应遗传算法及其在作业车间调度中的应用[J].大连交通大学学报，2009，30(4)：47-49.

[6] YEGANEH S H，GANJALI Y.Kandoo：a framework for efficient and scalable offloading of control applications[C].Proceedings of ACM SIGCOMM HOTSDN，2012.Helsinki，Finland：ACM，2012：19-24.

[7] EUGEN B，RADU B，SERBAN G O，et al.On multi controller placement optimization in software defined networking based WANs[C].Proceedings of The Fourteenth International Conference on Networks，2015.ICN，2015：261-266.

[8] ASADOLLAHI S，GOSWAMI B，SAMEER M.Ryu controller′s scalability experiment on software defined networks[C].IEEE(ICCTAC)，Bangalore，2018：1-5.

[9] JAWAHARAN R，MOHAN P M，DAS T，et al.Empirical evaluation of SDN controllers using mininet/wireshark and comparison with cbench[C].ICCCN，Hangzhou，2018：1-2.

[10] KHALID A，QUINLAN J J，SREENAN C J.MiniNAM：a network animator for visualizing real-time packet flows in Mininet[C].ICIN 2017，Paris，2017：229-231.

作者信息:

周  宁，胡  涛，胡宇翔，汪斌强

(中国人民解放军战略支援部队信息工程大学，河南 郑州450002)