2. 西安石油大学, 陕西 西安 710065
2. Xi'an Shiyou University, Xi'an 710065, China
1 引言
软件定义网络(software defined network，SDN)具有网络控制与传输的分离的特征，能够简化网络控制、快速开发并部署新型应用，已经在IP网络、光网络、无线网络中得到了广泛的应用[1-3].OpenFlow协议是SDN技术普遍采用的协议[4]，能够通过集中式控制器向OpenFlow交换机下发流表，实现网络的控制与传输分离.但是，当大规模部署OpenFlow交换机建立复杂SDN网络时，集中式控制器会成为网络性能的瓶颈[5].
为了解决大规模部署SDN时OpenFlow控制器的性能瓶颈问题，Onix作为逻辑上集中、物理上分布的控制平面被提出[6].在Onix中，每个控制器独立部署且相互连接构成控制平面，控制器之间通过相互共享信息获取SDN的全网信息.每个控制器下连接了若干个OpenFlow交换机，由控制器根据SDN全网信息向其连接的OpenFlow交换机下发流表，实现对网络流量的控制与优化.在Onix的基础上，文[7]提出弹性控制平面架构，通过静态规划确定SDN中部署的控制器个数和位置，构建SDN控制平面；再根据OpenFlow交换机上的负载动态迁移OpenFlow交换机，调整OpenFlow交换机和控制器的连接关系，重构SDN控制平面，保证每个控制器上的负载均衡，避免某个控制器成为性能瓶颈.图 1所示为静态控制器部署和动态交换机迁移示意图.图 1(a)中，根据控制平面的静态规划，交换机S1连接到控制器C1上，图 1(b)中，由于控制器C1上的负载已接近上限，而控制器C2上的负载较小，因此将交换机S1从控制器C1迁移到控制器C2上，保证控制器C1和控制器C2上的负载较为均衡，避免控制器C1成为性能瓶颈.
|
| 图 1 静态控制器部署和动态交换机迁移 Figure 1 The static controller placement and the dynamic switch migration |
当解决SDN控制平面构建和重构问题时，文[8]提出基于K-center的静态控制器部署算法，可以确定任意规模SDN网络中部署的控制器个数和位置.文[9]考虑了时延、代价等因素，给出了静态控制器部署问题的通用模型.文[10]使用K-center算法解决OpenFlow交换机的动态迁移问题，但是该算法只能在某个时间点上启动，确定当前时间点上如何迁移OpenFlow交换机，保证控制器上的负载均衡.文[11-12]通过定义近似的优化目标并求解该优化问题，调整交换机和控制器之间的连接关系，在某一时刻得到近似最优解，其实质是将动态选择问题转变为静态优化问题.文[13]按照控制器和其连接的交换机对OpenFlow网络分簇，通过迁移交换机完成簇之间的动态变化，保证控制器上的负载均衡，同时使网络具备高可靠性.但是该方法在确定交换机迁移方案时，需要在某一固定时刻进行簇的调整，其实质是静态交换机迁移.文[14]同时在多个交换机的问题域内建立博弈模型，根据某一时刻的网络负载，使用博弈论解决交换机迁移问题，将交换机动态迁移问题转变为静态优化问题.考虑到OpenFlow交换机上的动态随时都在变化，并且任意交换机上负载变化的规律不同，因此需要提出OpenFlow交换机动态迁移算法，解决交换机负载实时变化的问题.
由于SDN网络中各个交换机上的负载动态变化，并且其变化的规律难以描述，因此需要应用动态选择算法[15-18]，在不了解交换机负载变化统计规律的条件下，动态调整交换机与控制器的连接关系，完成交换机的动态迁移.文[19]提出吸引子选择模型描述大肠杆菌在生长过程中的动力学模型，可以在不了解事物内在联系的情况下，通过简单的反馈进行动态优化选择，适用于解决OpenFlow交换机负载动态变化的问题.在此基础上，本文提出基于吸引子选择的OpenFlow交换机动态迁移算法.根据交换机迁移的特征和吸引子算法模型，对交换机迁移问题建模，确定吸引子算法中各参数的物理含义，并提出动态迁移算法，根据吸引子算法的解确定将哪些交换机从原控制器迁移到目标控制器，使控制器上的负载均衡.
2 OpenFlow交换机迁移模型SDN网络被定义为{S，C}，其中S为交换机集合，包含的交换机个数为nS；C为控制器集合，包含的控制器个数为nC.si表示交换机集合中的任意一个交换机，cj表示控制器集合中的任意一个控制器.任意交换机和控制器之间的连接关系被定义为bij，取0或1，0表示交换机si没有连接到控制器cj上，1表示交换机si连接到控制器cj上.
对于任意控制器cj，其上连接的交换机的总数为ncj且：
|
(1) |
由于OpenFlow交换机只有新建立流表时才会向控制器发送Packetin包，要求控制器向其下发流表.因此，任意控制器cj上的负载定义为其上连接的所有OpenFlow交换机发往该控制器上的Packetin包的总个数：
|
(2) |
针对OpenFlow交换机动态迁移问题，其目标是完成交换机动态迁移后，保证控制器上的负载均衡，通过控制器上负载的标准方差描述：
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
为了得到OpenFlow交换机动态迁移的方法，当解决交换机迁移问题时，还需要考虑时延约束、代价约束、二值约束、数值约束等.
(1) 时延约束：当bij=1时，交换机si到控制器cj的时延定义为dij且该时延必须小于阈值TD，如式(4) 所示.TD取决于交换机对控制下发流表的时延要求.TD越大，交换机对控制器下发流表的时延要求越低，交换机迁移时可选的控制器范围越大，完成交换机迁移后控制器上的负载越均衡；TD越小，交换机对控制器下发流表的时延要求越高，交换机迁移时的控制器可选范围越小，完成迁移后控制器上的负载均衡效果越差.
(2) 代价约束：被迁移的OpenFlow交换机总数被定义为代价，记为e且e必须小于阈值TE，如式(5) 所示.TE越小，交换机迁移动作被触发后，被迁移的交换机个数越少，迁移后控制器负载均衡效果越差；反之，TE越大，每次被迁移的交换机个数越多，迁移完成后，控制器上的负载越均衡.
(3) 二值约束：任意一个交换机只能连接到一个控制器上，如式(6) 所示.
(4) 数值约束：所有控制器上连接的交换机的总数必须为nS，如式(7) 所示.
3 基于吸引子选择的OpenFlow交换机迁移算法吸引子选择模型描述了大肠杆菌生长过程的动力学模型，如式(8) 和式(9) 所示，xi表示基因表达水平，代表了大肠杆菌不同的进化方向，保证了大肠杆菌能够向乳糖浓度最高的位置运动，在该位置上大肠杆菌制造蛋白质的速度最快，生长速度最快.
|
(8) |
|
(9) |
其中，vg表示大肠杆菌的生长速度；Wij表示不同基因表达水平之间的影响系数；θ为基因表达水平的阈值；ηi是xi的随机噪声，保证基因表达水平具有一定的活性；ym表示蛋白质生成的量.
为了解决OpenFlow交换机动态迁移问题，根据交换机迁移模型对吸引子选择模型中的参数进行重新定义.xbij表示交换机i和控制器j连接的概率；xbcs表示交换机s和控制器c连接的概率；由于交换机上的负载在不断变化，交换机和控制器之间的连接关系相互影响，最终造成了连接关系变化的程度不同并体现在vg上，如式(10) 和式(11) 所示：
|
(10) |
|
(11) |
式(10) 中，第1部分和第2部分表示的是确定动作，第3部分表示随机动作.当vg越大时，第1部分和第2部分值越大，第3部分对整个系统的影响较小，整个系统更稳定；相反地，当vg越小时，第1部分和第2部分的值越小，第3部分对整个系统的影响越大，系统越不稳定.W(bij，bsc)表示bsc对bij的影响系数.如果c=j，则当xbsc减小时xbij增大，当xbsc增大时xbij减小，并且xbij和xbsc之间的影响系数W(bij，bsc)=1，表示交换机i从控制器j上迁移到其它控制器的概率上升，控制器j上负载下降的概率上升；如果c≠j，则bij和bsc之间没有关系，xbij和xbsc之间的影响系数W(bij，bsc)=0.θbij定义为W(bij，bsc)的上限，可以减少xbsc急剧变化时对xbij造成的影响.ηbij是高斯噪声，保证了吸引子选择模型具有足够的活动能力来应对环境的变化.式(11) 中，μ为常数，调整bij和bsc之间的影响程度.
通过式(10) 和式(11)，基于吸引子优化的OpenFlow交换机动态迁移算法保证了吸引子能够在动态迁移算法中迁移到最优解，因此吸引子选择模型中的生长速度vg定义为与优化目标r正相关的参数，即迁移的OpenFlow交换机个数越多，控制器上的负载越均衡，优化目标的值越小：
|
(12) |
式(12) 表示在大规模部署的SDN中，控制器上负载的标准方差越小，吸引子优化算法中的生长速度越快，吸引子选择模型越稳定，被迁移的OpenFlow交换机个数越少.式(12) 中，r为上一次交换机迁移动作完成后控制器负载的标准方差；δ、γ、φ为常数，调整r对vg的影响.
以上确定了任意一对交换机和控制器之间的连接关系，在此基础上，给出基于吸引子优化的OpenFlow交换机动态迁移算法流程：
Step 1 t0时刻，根据交换机i和控制器j的连接关系bij，生成吸引子优化模型中的基因表达水平xbij.如果交换机i和控制器j相连，则xbij较大；如果交换机i和控制器j不相连，则xbij较小.
Step 2 对于所有控制器，根据式(3) 控制器上负载的标准方差；对于任意i和j，根据式(10)、式(11) 和式(12) 计算xbij.
Step 3 对于任意的i和j，为了提高算法的健壮性和稳定性，使用概率选择方法确定交换机i和控制器j的连接关系，即bij=1的概率为p(cij).概率选择方法为
|
(13) |
Step 4 对于任意给定的i和j，比较t时刻所有交换机与控制器的连接关系bij与t-1时刻所有交换机与控制器的连接关系bij，确定需要迁移的交换机及迁移的目的控制器.
Step 5记录t时刻的迁移代价，根据式(14) 确定下一次启动OpenFlow交换机动态迁移的时间间隔，保证OpenFlow交换机迁移动作被触发的不会太频繁，造成迁移代价过大；也不会造成OpenFlow交换机动态迁移动作不能及时触发，使得该算法对控制器负载变化反应不及时，造成控制器成为性能瓶颈.
|
(14) |
以Internet 2项目典型的34节点网络拓扑为仿真环境，在文[20]使用静态控制器部署算法确定控制器部署数量和部署位置的基础上，验证所提算法的性能.文[20]使用C语言编写的离散事件驱动仿真平台，通过模拟交换机上的负载和各交换机之间的时延，验证控制器静态部署和交换机迁移算法.
如图 2所示，仿真环境中包括34个OpenFlow交换机和4个控制器，时延阈值被定义为1 200 ms，根据文[20]的结论，在节点7、14、24、33处部署控制器.仿真过程中，每间隔10个时间单位，每个独立的交换机向其连接的控制器上发送的Packetin包变化一次，变化的概率服从(5，10) 之间的均匀分布.
|
| 图 2 仿真拓扑 Figure 2 The network topology of the simulation |
仿真过程中，当确定式(10)、式(11) 和式(12) 中相关参数时，为了避免bij和bsc强相关时对基因表达水平造成较大的影响，仿真过程中ηbij设置为均值为0.2、方差为0.5的高斯噪声，θbij=0.5；为了放大bij和bsc弱相关时对系统的变化的推动作用，μ=10；为了放大基因表达水平对大肠杆菌生长速度的影响，δ=10，γ=1，φ=0.
4.1 约束参数对所提算法的影响图 3所示为在不同的代价约束下，控制器上负载标准方差随时间单位的变化曲线.
|
| 图 3 控制器负载标准方差 Figure 3 The standard deviation of the load on the controllers |
从图 3可以看出，通过应用所提OpenFLow交换机动态迁移算法，控制器上负载的标准方差越来越小，当时间单位达到50时，代价阈值设为5和10时控制器上负载的标准方差可以收敛到0.8；当代价阈值设为5和10时，控制器上负载的标准方差基本相差不大；当代价阈值设为17时，所提算法收敛的速度较慢，但是收敛的值较小，说明代价阈值设置为5不仅能够获得较好的收敛性，收敛速度较快且其代价较小.
图 4为在不同的代价约束下，OpenFlow交换机迁移时的代价随时间单位的变化曲线.从图 4可以看出，代价约束越高，OpenFlow交换机迁移完成时所产生的代价越大.这是因为代价约束越高，每次OpenFlow交换机迁移时，能够迁移的OpenFlow交换机个数越多，虽然保证了控制器上的负载更加均衡，但是由于代价被定义为OpenFlow交换机被迁移的个数，因此更高的代价约束导致了更高的迁移代价.
|
| 图 4 本文算法的代价曲线 Figure 4 The cumulative cost of the proposed algorithm |
仿真过程中，OpenFlow交换机迁移的时间间隔由式(14) 确定，在其中δ=100，用于减少τ对交换机迁移时间间隔的影响，保证交换机迁移的时间间隔变化较为平稳.图 5为τ分别为300、500、1000时控制器负载标准方差随时间间隔的曲线，代价阈值被定义为5.
|
| 图 5 τ取不同值时控制器负载的标准方差 Figure 5 The standard deviation of the load on the controllers with different τ |
从图 5可以看出，τ的取值对算法的收敛性几乎没有影响，这是因为所提算法具有一定的健壮性，具备动态应对环境变化的能力，选择优化效果较为稳定.
表 1为τ取不同值时平均迁移的OpenFlow交换机个数和计算代价，其中计算代价采用时间来衡量.
| τ=300 | τ=500 | τ=1 000 | |
| 迁移代价 | 437.69 | 793.85 | 1 234.41 |
从表 1可以看出，τ取值越小，OpenFlow交换机迁移动作被触发的越频繁，并且每次被迁移的交换机个数越多，造成计算代价越大.
由于时延约束会影响交换机时选择控制器的范围，因此给出不同时延约束下本文所提算法的控制器负载标准方差和迁移代价分析，如表 2和图 6所示，其中代价约束为10，τ=500.
| TD=600 | TD=1 200 | TD=2 000 | |
| 控制器负载标准方差的收敛值 | 0.84 | 0.54 | 0.53 |
|
| 图 6 不同时延约束下的迁移代价 Figure 6 The migration cost with different delay constraint |
从表 2和图 6可以看出，当时延约束较小时，交换机迁移过程中可选的控制器范围较小，交换机迁移完成后，控制器上的负载变化较小，即负载均衡效果较差，同时迁移代价较小；当时延约束较大时，交换机即使可以选择更多的控制器进行迁移，但是对进一步提高交换机上负载均衡效果的影响不大，使得当时延约束较大时，本文所提算法的负载均衡效果和迁移代价变化都不大.
4.2 对比算法性能分析表 3为所提算法与其它算法关于控制器负载均衡性能的比较；图 7所示为本文所提算法与文[10-14]所提算法关于交换机迁移代价、控制器负载标准方差的对比曲线.本文所提算法记为AS-DSM(attractor selection-dynamic switch migration)，文[10]所提算法记为K-DSM(K-center-dynamic switch migration)、文[11-12]所提算法记为DHA-DSM(distributed heuristic approximate-dynamic switch migration)、文[13]所提算法记为CT-DSM(crash-tolerant-dynamic switch migration)、文[14]所提算法记为GD-DSM(game model-dynamic switch migration).本文所提算法的代价阈值设置为5，τ=300，时延约束为1 200.
| 控制器负载标准方差 | 时间单位 | |||
| 10 | 50 | 100 | 150 | |
| AS-DSM | 3.5 | 0.7 | 0.7 | 0.7 |
| K-DSM | 4.6 | 2.1 | 1.6 | 1.2 |
| DHA-DSM | 2.4 | 2.6 | 2.5 | 2.5 |
| CT-DSM | 1.9 | 1.9 | 1.7 | 1.8 |
| GD-DSM | 2.2 | 2.3 | 2.3 | 2.3 |
|
| 图 7 迁移代价的对比 Figure 7 Comparison of the migration cost |
从表 3可以看出，所提算法和K-DSM算法具有自学习能力，能够随着时间较快地收敛到最优解，保证控制器负载的标准方差较小；DHA-DSM、CT-DSM和GD-DSM算法将动态交换机迁移算法转化为静态优化算法，每次求解都需要初始化优化问题，不能利用上一次优化问题的解，其优化结果基本保持不变.
从图 7和表 3可以看出，所提算法的负载均衡效果优于其它算法，并且其代价小于其它算法.这是因为本文所提算法能够适应动态变化的环境，动态选择最优的OpenFlow交换机迁移目标，确保每迁移一个OpenFlow交换机能够最大程度减少控制器上负载的标准方差.
表 4所示为所提算法与其它算法在相同仿真环境下的运算时间对比，仿真环境与文[16]一致，采用8核OS X操作系统，2.6 GHz Intel i5处理器进行仿真.
| AS-DSM | K-DSM | DHA-DSM | CT-DSM | GD-DSM | |
| 平均运行时间/s | 0.133 | 4.351 | 4.466 | 5.583 | 4.877 |
从表 4可以看出，所提AS-DSM算法的平均运行时间最短.这是因为K-DSM、DHA-DSM、CT-DSM、GD-DSM算法将交换机动态迁移问题转化为静态优化问题，每次交换机上负载发生变化时都需要初始化优化问题，而本文所提AS-DSM算法只需要在交换机上负载发生变化时进行简单的反馈就可以得到交换机迁移的解.因此，随着时间的推进，所提算法的平均时间较短，而其它算法的平均运行时间较长.
5 总结本文利用吸引子算法能够通过简单反馈解决动态选择问题的特征，分析OpenFlow交换机动态迁移问题，在此基础上对吸引子算法建模，在不能准确描述OpenFlow交换机负载的条件下解决OpenFlow交换机动态迁移问题.仿真结果表明，所提算法的负载均衡效果较好且迁移代价较小.所提算法建立的OpenFlow交换机迁移模型为使用已有选择优化算法求解OpenFlow交换机迁移提供了基础；使用的吸引子选择模型能够适应动态变化且不能使用解析式进行描述的环境，为解决同类问题提供了借鉴.
| [1] | Lin P, Hart J, Krishnaswamy U, et al. Seamless interworking of SDN and IP[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 475–476. DOI:10.1145/2534169 |
| [2] | Channegowda M, Nejabati R, Simeonidou D. Software-defined optical networks technology and infrastructure:Enabling software-defined optical network operations[J]. Journal of Optical Communications and Networking, 2013, 5(10): A274–A282. DOI:10.1364/JOCN.5.00A274 |
| [3] | Chin W H, Fan Z, Haines R. Emerging technologies and research challenges for 5G wireless networks[J]. IEEE Wireless Communications, 2014, 21(2): 106–112. DOI:10.1109/MWC.2014.6812298 |
| [4] | Sezer S, Scott-Hayward S, Chouhan P K, et al. Are we ready for SDN? Implementation challenges for software-defined networks[J]. IEEE Communications Magazine, 2013, 51(7): 36–43. DOI:10.1109/MCOM.2013.6553676 |
| [5] | Levin D, Wundsam A, Heller B, et al. Logically centralized? State distribution trade-offs in software defined networks[C]//ACM SIGCOMM Proceeding on HotSDN. New York, NJ, USA:ACM, 2012:1-6. http://dx.doi.org/10.1145%2F2342441.2342443 |
| [6] | Koponen T, Casado M, Gude N, et al. Onix:A distributed control platform for large-scale production networks[C]//Usenix Conference on Operating Systems Design and Implementation. Berkeley, CA, USA:USENIX Association, 2010:351-364. |
| [7] | Dixit A, Hao F, Mukherjee S, et al. Towards an elastic distributed SDN controller[C]//ACM SIGCOMM Proceeding on HotSDN. New York, NJ, USA:ACM, 2013, 8-12. |
| [8] | Heller B, Sherwood R, McKeown N. The controller placement problem[C]//ACM SIGCOMM Proceeding on HotSDN. New York, NJ, USA:ACM, 2012:7-12. |
| [9] | Lange S, Gebert S, Zinner T, et al. Heuristic approaches to the controller placement problem in large scale SDN networks[J]. IEEE Transactions on Network and Service Management, 2015, 12(1): 4–17. DOI:10.1109/TNSM.2015.2402432 |
| [10] | Yao G, Bi J, Li Y, et al. On the capacitated controller placement problem in software defined networks[J]. IEEE Communications Letters, 2014, 18(8): 1339–1342. DOI:10.1109/LCOMM.2014.2332341 |
| [11] | Cheng G Z, Chen H, Hu H C, et al. Toward a scalable SDN control mechanism via switch migration[J]. China Communications, 2017, 14(1): 111–123. DOI:10.1109/CC.2017.7839762 |
| [12] | Cheng G, Chen H, Wang Z, et al. DHA:Distributed decisions on the switch migration toward a scalable SDN control plane[C]//IFIP Networking Conference. Piscataway, NJ, USA:IEEE, 2015:1-9. |
| [13] | Liang C, Kawashima R, Matsuo H. Scalable and crash-tolerant load balancing based on switch migration for multiple open flow controllers[C]//International Symposium on Computing and Networking. Piscataway, NJ, USA:IEEE, 2014:171-177. http://ieeexplore.ieee.org/document/7052178/ |
| [14] | Cheng G Z, Chen H C. Game model for switch migrations in software-defined network[J]. Electronic Letters, 2014, 50(23): 1699–1700. DOI:10.1049/el.2014.2086 |
| [15] |
洪露, 纪志成, 龚成龙.
一类克隆选择算法的收敛性方法研究[J]. 信息与控制, 2011, 40(2): 232–236.
Hong L, Ji Z H, Gong C L. Convergence method analysis of a class of clonal selection algorithm[J]. Information and Control, 2011, 40(2): 232–236. |
| [16] |
石刚, 井元伟, 邹德旋.
主从式免疫克隆选择算法求解任务分配问题[J]. 信息与控制, 2011, 40(3): 424–428.
Shi G, Jing Y W, Zou D X. Solving task assignment problem by master-slave immune clone selection algorithm[J]. Information and Control, 2011, 40(3): 424–428. |
| [17] |
邢志浩, 王宏, 梁韡.
隐式路由协议的一种转发节点快速选择算法[J]. 信息与控制, 2006, 35(2): 135–140.
Xing Z H, Wang H, Liang W. A forwarder fast selection algorithm for implicit routing protocol[J]. Information and Control, 2006, 35(2): 135–140. |
| [18] |
解志斌, 汪晋宽, 王赟, 等.
多天线系统分集复用模式快速选择算法[J]. 信息与控制, 2009, 38(1): 55–58, 63.
Xie Z B, Wang J K, Wang Y, et al. A fast diversity and multiplexing selection algorithm for multi-antenna systems[J]. Information and Control, 2009, 38(1): 55–58, 63. |
| [19] | Chikara F, Kunihiko K. A generic mechanism for adaptive growth rate regulation[J]. PLoS Computational Biology, 2008, 4(1): 35–42. |
| [20] | Wang L X, Qu H, Zhao J H, et al. A strategy of controller placement in software defined networks using binary particle swarm optimization[J]. Journal of Xi'an Jiaotong University, 2015, 49(6): 67–71. |