高级搜索

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

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

引用本文: 史久根, 谢熠君, 孙立, 郭胜, 刘雅丽. 软件定义网络中面向时延和负载的多控制器放置策略[J]. 电子与信息学报, doi: 10.11999/JEIT181053 shu
Citation:  Jiugen SHI, Yijun XIE, Li SUN, Sheng GUO, Yali LIU. Multi-controller Placement Strategy Based on Latency and Load in Software Defined Network[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT181053 shu

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

    作者简介: 史久根: 男,1963年生,副教授,研究方向为嵌入式系统、计算机网络和无线传感器网络;
    谢熠君: 男,1995年生,硕士生,研究方向为软件定义网络、控制器放置和嵌入式系统;
    孙立: 男,1993年生,硕士生,研究方向为软件定义网络、路由多播和嵌入式系统;
    郭胜: 男,1993年生,硕士生,研究方向为软件定义网络、网络虚拟化和规则放置;
    刘雅丽: 女,1996年生,硕士生,研究方向为软件定义网络、网络虚拟化和规则缓存;
    通讯作者: 谢熠君, 2017110977@mail.hfut.edu.cn
  • 基金项目: 国家重大科学仪器设备开发专项(2013YQ030595)

摘要: 在多控制器管理的软件定义网络(SDN)中,时延和负载是控制器放置问题(CPP)要考虑的重要因素。该文以降低控制器之间的传播时延、流请求的传播时延和排队时延、均衡控制器间负载为目标,提出一种控制器放置及动态调整的策略,其中包括用于初始控制器放置的负载均衡算法(BCRA)和遗传算法(GA),用于动态调整控制器负载的在线调整算法(ADOA)。以上算法均考虑网络连通性。仿真结果表明:在初始控制器放置时,在保证流请求的传播时延、排队时延和控制器传播时延较低的情况下,BCRA部署在中小型网络中时,其负载均衡性能与GA相近且优于k-center和k-means算法;GA部署在大型网络中时,与BCRA, k-center和k-means算法相比,使得负载均衡率平均提高了49.7%。在动态情况下,与现有动态调整算法相比,ADOA可以保证较低排队时延和运行时间的同时,仍能使负载均衡参数小于1.54。

English

    1. [1]

      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

    2. [2]

      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

    3. [3]

      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

    4. [4]

      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

    5. [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

    6. [6]

      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

    7. [7]

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

    8. [8]

      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

    9. [9]

      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

    10. [10]

      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

    11. [11]

      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

    12. [12]

      高先明, 王宝生, 邓文平, 等. 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

    13. [13]

      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

    14. [14]

      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

    15. [15]

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

    16. [16]

      史久根, 邾伟, 贾坤荥, 等. 软件定义网络中基于负载均衡的多控制器部署算法[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

    17. [17]

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

    18. [18]

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

    1. [1]

      于天放芮兰兰邱雪松. 基于软件定义网络的服务器集群负载均衡技术研究. 电子与信息学报, doi: 10.11999/JEIT180207

    2. [2]

      史久根邾伟贾坤荥徐颖. 软件定义网络中基于负载均衡的多控制器部署算法. 电子与信息学报, doi: 10.11999/JEIT170464

    3. [3]

      史久根徐皓张径王继. 软件定义网络中基于效率区间的负载均衡在线优化算法. 电子与信息学报, doi: 10.11999/JEIT180464

    4. [4]

      张少军兰巨龙江逸茗孙鹏浩. 流特征感知的软件定义网络控制器动态关联机制. 电子与信息学报, doi: 10.11999/JEIT171149

    5. [5]

      姚琳元陈颖宋飞张宏科. 基于时延的软件定义网络快速响应控制器部署. 电子与信息学报, doi: 10.3724/SP.J.1146.2014.00211

    6. [6]

      熊钢胡宇翔段通兰巨龙. 一种软件定义网络的安全服务链动态组合机制. 电子与信息学报, doi: 10.11999/JEIT150876

    7. [7]

      唐伦梁荣张亚陈前斌. 异构密集网络下基于POMDP负载感知的负载均衡算法研究. 电子与信息学报, doi: 10.11999/JEIT161347

    8. [8]

      伊鹏刘邦舟王文博张少军. 一种考虑软件定义网络控制节点故障的控制器部署和交换机迁移方法. 电子与信息学报, doi: 10.11999/JEIT161216

    9. [9]

      刘焕淋胡浩熊翠连陈勇向敏马跃. 基于时频联合碎片感知的资源均衡虚拟光网络映射算法. 电子与信息学报, doi: 10.11999/JEIT171208

    10. [10]

      史久根许辉亮陆立鹏. 软件定义网络中数据中心虚拟机迁移序列问题的研究. 电子与信息学报, doi: 10.11999/JEIT160792

    11. [11]

      伊鹏刘洪胡宇翔. 一种可扩展的软件定义数据中心网络流调度策略. 电子与信息学报, doi: 10.11999/JEIT160623

    12. [12]

      史久根王继张径徐皓. 软件定义网络中基于流量管理的分布式防火墙策略. 电子与信息学报, doi: 10.11999/JEIT180223

    13. [13]

      秦晰唐国栋常朝稳王瑞云. 软件定义网络中基于密码标识的报文转发验证机制. 电子与信息学报, doi: 10.11999/JEIT171226

    14. [14]

      姚琳元董平张宏科. 基于对象特征的软件定义网络分布式拒绝服务攻击检测方法. 电子与信息学报, doi: 10.11999/JEIT160370

    15. [15]

      熊余杨娅娅张振振蒋婧. 软件定义时分波分复用无源光网络中基于带宽预测的资源分配策略. 电子与信息学报, doi: 10.11999/JEIT180837

    16. [16]

      周烨杨旭李勇苏厉金德鹏曾烈光. 基于分类的软件定义网络流表更新一致性方案. 电子与信息学报, doi: 10.3724/SP.J.1146.2012.01431

    17. [17]

      兰巨龙于倡和胡宇翔李子勇. 基于深度增强学习的软件定义网络路由优化机制. 电子与信息学报, doi: 10.11999/JEIT180870

    18. [18]

      王颖余金科裴科科邱雪松. 基于负载通告的SDN多控制器负载均衡机制. 电子与信息学报, doi: 10.11999/JEIT161054

    19. [19]

      李宁林家儒. CDMA/OFDMA异构网络中最小化中断概率的网络选择方案. 电子与信息学报, doi: 10.3724/SP.J.1146.2011.00387

    20. [20]

      王静刘景美王新梅. 基于网络编码的多播路由算法性能分析. 电子与信息学报, doi: 10.3724/SP.J.1146.2007.00638

  • 图 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
  • 加载中
图(6)表(3)
计量
  • PDF下载量:  9
  • 文章访问数:  81
  • HTML全文浏览量:  53
  • 引证文献数: 0
文章相关
  • 通讯作者:  谢熠君, 2017110977@mail.hfut.edu.cn
  • 收稿日期:  2018-11-20
  • 录用日期:  2019-04-09
  • 网络出版日期:  2019-04-23
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章