高级搜索

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

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

引用本文: 史久根, 谢熠君, 孙立, 郭胜, 刘雅丽. 软件定义网络中面向时延和负载的多控制器放置策略[J]. 电子与信息学报, 2019, 41(8): 1869-1876. 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, 2019, 41(8): 1869-1876. 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]. 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]. The 26th 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]. 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]. The 9th International Conference on Network and Service Management, Zurich, Switzerland, 2013: 18-25. doi: 10.1109/CNSM.2013.6727805.

    1. [1]

      史久根, 徐皓, 张径, 王继. 软件定义网络中基于效率区间的负载均衡在线优化算法. 电子与信息学报, 2019, 41(3): 694-701.

    2. [2]

      胡宇翔, 李子勇, 胡宗魁, 胡涛. 基于流量工程的软件定义网络控制资源优化机制. 电子与信息学报, 2019, 41(0): 1-8.

    3. [3]

      史久根, 王继, 张径, 徐皓. 软件定义网络中基于流量管理的分布式防火墙策略. 电子与信息学报, 2019, 41(1): 91-98.

    4. [4]

      熊余, 杨娅娅, 张振振, 蒋婧. 软件定义时分波分复用无源光网络中基于带宽预测的资源分配策略. 电子与信息学报, 2019, 41(8): 1885-1892.

    5. [5]

      张海波, 荆昆仑, 刘开健, 贺晓帆. 车联网中一种基于软件定义网络与移动边缘计算的卸载策略. 电子与信息学报, 2019, 41(0): 1-8.

    6. [6]

      兰巨龙, 于倡和, 胡宇翔, 李子勇. 基于深度增强学习的软件定义网络路由优化机制. 电子与信息学报, 2019, 41(0): 1-6.

    7. [7]

      刘焕淋, 方菲, 黄俊, 陈勇, 向敏, 马跃. 面向业务的弹性光网络光路损伤感知能效路由策略. 电子与信息学报, 2019, 41(5): 1202-1209.

    8. [8]

      胡宇翔, 范宏伟, 兰巨龙, 段通. 一种支持硬件加速的虚拟网络功能部署模型. 电子与信息学报, 2019, 41(8): 1893-1901.

    9. [9]

      张红旗, 黄睿, 常德显. 一种基于匹配博弈的服务链协同映射方法. 电子与信息学报, 2019, 41(2): 385-393.

    10. [10]

      黄盛. 两用户非正交多址接入的最优时延均衡和功率控制方法. 电子与信息学报, 2019, 41(8): 1902-1908.

    11. [11]

      戴紫彬, 尹安琪, 曲彤洲, 南龙梅. 面向众核密码处理器的高效负载均衡技术. 电子与信息学报, 2019, 41(2): 369-376.

    12. [12]

      卢昱, 刘益岑, 李玺, 陈兴凯, 乔文欣, 陈立云. 面向软件定义网络的服务功能链优化部署算法研究. 电子与信息学报, 2019, 41(1): 74-82.

    13. [13]

      邹虹, 高毅爽, 闫俊杰. 带有卸载时延感知的边缘云增强FiWi网络节能机制. 电子与信息学报, 2019, 41(2): 394-401.

    14. [14]

      王汝言, 徐宁宁, 吴大鹏. 能耗和时延感知的虚拟化云无线接入网络资源分配机制. 电子与信息学报, 2019, 41(1): 83-90.

    15. [15]

      杨凌, 赵膑, 陈亮, 李媛, 张国龙. 基于回声状态网络的卫星信道在线盲均衡算法. 电子与信息学报, 2019, 41(0): 1-8.

    16. [16]

      杨英杰, 冷强, 常德显, 潘瑞萱, 胡浩. 基于属性攻击图的网络动态威胁分析技术研究. 电子与信息学报, 2019, 41(8): 1838-1846.

    17. [17]

      唐伦, 周钰, 杨友超, 赵国繁, 陈前斌. 5G网络切片场景中基于预测的虚拟网络功能动态部署算法. 电子与信息学报, 2019, 41(9): 2071-2078.

    18. [18]

      于存谦, 张黎, 何荣希. 弹性光网络基于区分降级服务和自适应调制的动态路由与频谱分配算法. 电子与信息学报, 2019, 41(1): 38-45.

    19. [19]

      钱志鸿, 田春生, 王鑫, 王雪. D2D网络中信道选择与功率控制策略研究. 电子与信息学报, 2019, 41(0): 1-7.

    20. [20]

      陈树新, 洪磊, 吴昊, 刘卓崴, 岳龙华. 学生 t 混合势均衡多目标多伯努利滤波器. 电子与信息学报, 2019, 41(0): 1-7.

  • 图 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下载量:  16
  • 文章访问数:  261
  • HTML全文浏览量:  186
文章相关
  • 通讯作者:  谢熠君, 2017110977@mail.hfut.edu.cn
  • 收稿日期:  2018-11-20
  • 录用日期:  2019-04-09
  • 网络出版日期:  2019-04-23
  • 刊出日期:  2019-08-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章