软件定义网络中面向时延和负载的多控制器放置策略

史久根; 谢熠君; 孙立; 郭胜; 刘雅丽

doi:10.11999/JEIT181053

软件定义网络中面向时延和负载的多控制器放置策略

doi: 10.11999/JEIT181053

合肥工业大学计算机与信息学院合肥 230009

基金项目: 国家重大科学仪器设备开发专项(2013YQ030595)

详细信息

作者简介:
史久根：男，1963年生，副教授，研究方向为嵌入式系统、计算机网络和无线传感器网络

谢熠君：男，1995年生，硕士生，研究方向为软件定义网络、控制器放置和嵌入式系统

孙立：男，1993年生，硕士生，研究方向为软件定义网络、路由多播和嵌入式系统

郭胜：男，1993年生，硕士生，研究方向为软件定义网络、网络虚拟化和规则放置

刘雅丽：女，1996年生，硕士生，研究方向为软件定义网络、网络虚拟化和规则缓存

通讯作者:
谢熠君　2017110977@mail.hfut.edu.cn

中图分类号: TP393.3
计量
- 文章访问数: 1919
- HTML全文浏览量: 1093
- PDF下载量: 79
- 被引次数: 0
出版历程
- 收稿日期: 2018-11-20
- 修回日期: 2019-04-09
- 网络出版日期: 2019-04-23
- 刊出日期: 2019-08-01

Multi-controller Placement Strategy Based on Latency and Load in Software Defined Network

School of Computer and Information, Hefei University of Technology, Hefei 230009, China

Funds: The National Major Scientific Instruments Development Project (2013YQ030595)

摘要

摘要: 在多控制器管理的软件定义网络(SDN)中，时延和负载是控制器放置问题(CPP)要考虑的重要因素。该文以降低控制器之间的传播时延、流请求的传播时延和排队时延、均衡控制器间负载为目标，提出一种控制器放置及动态调整的策略，其中包括用于初始控制器放置的负载均衡算法(BCRA)和遗传算法(GA)，用于动态调整控制器负载的在线调整算法(ADOA)。以上算法均考虑网络连通性。仿真结果表明：在初始控制器放置时，在保证流请求的传播时延、排队时延和控制器传播时延较低的情况下，BCRA部署在中小型网络中时，其负载均衡性能与GA相近且优于k-center和k-means算法；GA部署在大型网络中时，与BCRA, k-center和k-means算法相比，使得负载均衡率平均提高了49.7%。在动态情况下，与现有动态调整算法相比，ADOA可以保证较低排队时延和运行时间的同时，仍能使负载均衡参数小于1.54。
- 软件定义网络 /
- 控制器放置 /
- 负载均衡 /
- 网络时延 /
- 动态调整
Abstract: In Software Defined Networks (SDN), latency and load are important factors for Controller Placement Problem (CPP). To reduce the transmission latency between controllers, the propagation latency and queuing latency of flow requests, and balance the controller load, a strategy on how to place and adjust the controller is proposed. It mainly includes Genetic Algorithm (GA) and Balanced Control Region Algorithm (BCRA) which are used to place the initial controller and one Algorithm of Dynamic Online Adjustment (ADOA), that is an online adjusting algorithm in term dynamic controlling. The above algorithms are all based on the network connectivity. The simulation results show that in initial controller placement situation, under the premise of guaranteeing the lower propagation latency, queue latency and controller transmission latency of flow request, when BCRA is deployed in small and medium-sized networks, its load balancing performance is similar to that of GA and superior to k-center and k-means algorithm; When GA is deployed in large networks, compared with BCRA, k-center and k-means, the load balancing rate increases averagely 49.7%. In the dynamic situation, ADOA can guarantee lower queuing delay and running time, and can still make the load balance parameter less than 1.54.
- Software Defined Network (SDN) /
- Controller placement /
- Load balancing /
- Network latency /
- Dynamic adjustment

HTML全文

图 1 OS3E网络中的性能指标

下载: 全尺寸图片幻灯片

图 2 IRIS网络中的性能指标

下载: 全尺寸图片幻灯片

图 3 动态调整后的网络排队时延

下载: 全尺寸图片幻灯片

图 4 动态调整后的网络负载均衡情况

下载: 全尺寸图片幻灯片

图 5 动态调整后控制器数量

下载: 全尺寸图片幻灯片

图 6 算法运行时间

下载: 全尺寸图片幻灯片

表 1 BCRA算法

　算法1 BCRA算法

　输入：图

$G(V,E)$ ,

${\lambda _{i,j}}$ ,

${\rm{Cons}}$ ,

${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$ ,

$C\;$ //

${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$ ,

$C\;$ 都是空集

　输出：

$F$ 的值，控制器集合

$C$ 和子网集合

${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$

　(1)　计算各个节点的度

$D$ ; //步骤(1)～步骤(10)是网络划分阶段；
　(2)　计算

$k = \sum\nolimits_{j = 1}^n {{\lambda _j}} /{\rm{LCPmax}}$ ; //

${\lambda _j}$ 表示第

$j$ 个交换机流量，

${\rm{LCPmax}}$ 表示最大负载；

　(3)　while

$\left| C\, \right| < k$

　(4)　如果算法第1次执行，则选择度最大的节点

${\rm{Cons}}$ 作为控制器节点；否则，从剩余节点中找到度最大的节点并组成集合，再从该集
合中选择距离当前控制器节点最近的点

${\rm{Cons}}$ 作为新的控制器节点；

　(5)　将节点

${\rm{Cons}}$ 加入控制器集合

$C$ ；

　(6)　while

${\rm{LC}}{{\rm{P}}_{{\rm{cons}}}} < {\mu _{{\rm{cons}}}}$ //基于

${\rm{Con}}$ 使用广度优先搜索方法构建树；

　(7)　选择离

${\rm{Con}}$ 最近且未被分配的节点

$j$ ，将其加入

${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$ ；

　(8)　end while

　(9)　end while

　(10)　找到每个控制器对应的交换机集合

$\left\{ {{\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} \right\} ,{\rm{cons}} \in C\;$ ,计算

$F\;$ 的值并记为

${\rm{Fold}}$ ；

　(11)　while

${\rm{BL}} - 1 > \xi$ //

$\xi$ 是一个极小值，步骤(11)—步骤(19)是子网调整阶段；

　(12)　找到负载最大的控制器

${\rm{Cons}}$ 的子网，并计算子网内的边界交换机与相邻控制器之间的距离；

　(13)　预先计算将距离最小的交换机分配给相邻控制器后的

$F$ 的值，并标记为

${\rm{Fnew}}$ ；

　(14)　if

${\rm{Fnew}} \le {\rm{Fold}}$

　(15)　将距离最小的交换机分配给相邻控制器，并令

${\rm{Fold = Fnew}}$ ；
　(16)　更新交换机集合

$\left\{ {{\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} \right\}$ 并计算

$\sum\nolimits_{j \in {\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} {\lambda _{{\rm{cons}},j}^{}}$ ；

　(17)　 end if

　(18)　

$F = {\rm{Fold}}$ ；

　(19)　end while

　(20)　输出

$F,C,\left\{ {{\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} \right\}$

下载: 导出CSV

表 2 BLA算法

　算法2 BLA算法

　输入：图

$G(V,E)$ ,

${\lambda _{i,j}}$ ,

${\mu _i}$ ,

${\rm{CA}}$ ,

$C\,$ //

${\rm{CA}}$ 是空集

　输出：适应度函数值

$F$

　(1)　for

$i \in C$

　(2)　选择节点

$j$ ，其满足离控制器

$i$ 最近且未被标记；
　(3)　if

$\sum\nolimits_{j \in {\rm{C}}{{\rm{A}}_i}} {{\lambda _{i,j}}} < {\mu _i}$

　(4)　将节点

$j$ 加入

${\rm{C}}{{\rm{A}}_i}$ ；

　(5)　end if

　(6)　end for

　(7)　找到每个控制器对应的交换机集合

$\left\{ {{\rm{C}}{{\rm{A}}_i}} \right\} ,i \in C\,$ ，计算

$F\,$ 的值并记为

${\rm{Fold}}$ ；

　(8)　接着调用BCRA的子网调整阶段算法；//即算法1的步
骤(11)—步骤(19)；

　(9)　输出

$F$

下载: 导出CSV

表 3 ADOA算法

　算法3 ADOA算法

　输入：

${\rm{C}}{{\rm{A}}_i}$ ,

${\lambda _{i,j}}$ ,

${\mu _i}$ ,

$C$ ,

${\rm{LC}}{{\rm{P}}_i}^{}$ ,

$D$

　输出：

${\rm{C}}{{\rm{A}}_{i,o}}$

　(1)　while

${\rm{LC}}{{\rm{P}}_i}$ 改变并且

${\rm{T}}{{\rm{q}}_i} > {\rm{Tqmax}}$

　(2)　选择当前子网中度最大的节点

$o$ 作为从控制器；

　(3)　for

$j \in {\rm{C}}{{\rm{A}}_i}$

　(4)　如果

${\rm{LC}}{{\rm{P}}_o} > {\rm{LC}}{{\rm{P}}_i}$ ，则跳出当前循环并转入步骤2；

　(5)　if 相对于控制器

$i$ ，节点

$j$ 离控制器

$o$ 近；

　(6)　预先计算将

$j$ 分配给

$o$ 后的

${\rm{T}}{{\rm{q}}_o}$ ；

　(7)　如果

${\rm{T}}{{\rm{q}}_o} < {\rm{Tqmax}}$ ，则令

$j \in {\rm{C}}{{\rm{A}}_{i,o}}$ 且

$j \notin {\rm{C}}{{\rm{A}}_i}$ ；

　(8)　end if

　(9)　end for

　(10)　end while

　(11)　输出

${\rm{C}}{{\rm{A}}_{i,o}}$

下载: 导出CSV

参考文献(18)

HELLER B, SHERWOOD R, and MCKEOWN N. The controller placement problem[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 473–478. doi: 10.1145/2377677.2377767

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

ZHANGA Bang, WANG Xingwei, and HUANG Min. Multi-objective optimization controller placement problem in internet-oriented software defined network[J]. Computer Communications, 2018, 123: 24–35. doi: 10.1016/j.comcom.2018.04.008

JALILI A, KESHTGARI M, and AKBARI R. Optimal controller placement in large scale software defined networks based on modified NSGA-II[J]. Applied Intelligence, 2018, 48(9): 2809–2823. doi: 10.1007/s10489-017-1119-5

HU Ying, LUO Tao, BEAULIEU N C, et al. The energy-aware controller placement problem in software defined networks[J]. IEEE Communications Letters, 2017, 21(4): 741–744. doi: 10.1109/LCOMM.2016.2645558

SALLAHI A and ST-HILAIRE M. Optimal model for the controller placement problem in software defined networks[J]. IEEE Communications Letters, 2015, 19(1): 30–33. doi: 10.1109/LCOMM.2014.2371014

JIMÉNEZ Y, CERVELLÓ-PASTOR C, and GARCÍA A. On the controller placement for designing a distributed SDN control layer[C]. 2014 IFIP Networking Conference, Trondheim, Norway, 2014: 1–9. doi: 10.1109/IFIPNetworking.2014.6857117.

YAO Guang, BI Jun, LI Yuliang, 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

HUQUE M T I U, SI Weisheng, JOURJON G, et al. Large-scale dynamic controller placement[J]. IEEE Transactions on Network and Service Management, 2017, 14(1): 63–76. doi: 10.1109/TNSM.2017.2651107

SOOD K and XIANG Yong. The controller placement problem or the controller selection problem?[J]. Journal of Communications and Information Networks, 2017, 2(3): 1–9. doi: 10.1007/s41650-017-0030-x

WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. An effective approach to controller placement in software defined wide area networks[J]. IEEE Transactions on Network and Service Management, 2018, 15(1): 344–355. doi: 10.1109/TNSM.2017.2785660

高先明, 王宝生, 邓文平, 等. SDN网络中控制器放置问题综述[J]. 通信学报, 2017, 38(7): 155–164. doi: 10.11959/j.issn.1000-436x.2017136

GAO Xianming, WANG Baosheng, DENG Wenping, et al. Survey of controller placement problem in software defined network[J]. Journal on Communications, 2017, 38(7): 155–164. doi: 10.11959/j.issn.1000-436x.2017136

WANG Tao, LIU Fangming, and XU Hong. An efficient online algorithm for dynamic SDN controller assignment in data center networks[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 2788–2801. doi: 10.1109/TNET.2017.2711641

HU Tao, GUO Zehua, YI Peng, et al. Multi-controller based software-defined networking: A survey[J]. IEEE Access, 2018, 6: 15980–15996. doi: 10.1109/ACCESS.2018.2814738

WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. On the data aggregation point placement in smart meter networks[C]. The 26th International Conference on Computer Communication and Networks, Vancouver, Canada, 2017: 1–6. doi: 10.1109/ICCCN.2017.8038499.

史久根, 邾伟, 贾坤荥, 等. 软件定义网络中基于负载均衡的多控制器部署算法[J]. 电子与信息学报, 2018, 40(2): 455–461. doi: 10.11999/JEIT170464

SHI Jiugen, ZHU Wei, JIA Kunying, et al. Multi-controller deployment algorithm based on load balance in software defined network[J]. Journal of Electronics &Information Technology, 2018, 40(2): 455–461. doi: 10.11999/JEIT170464

WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. A K-means-based network partition algorithm for controller placement in software defined network[C]. 2016 IEEE International Conference on Communications, Kuala Lumpur, Malaysia, 2016: 1–6. doi: 10.1109/ICC.2016.7511441.

BARI M F, ROY A R, CHOWDHURY S R, et al. Dynamic controller provisioning in software defined networks[C]. The 9th International Conference on Network and Service Management, Zurich, Switzerland, 2013: 18-25. doi: 10.1109/CNSM.2013.6727805.

施引文献

资源附件(0)

访问统计