高级搜索

软件定义网络中基于效率区间的负载均衡在线优化算法

史久根 徐皓 张径 王继

引用本文: 史久根, 徐皓, 张径, 王继. 软件定义网络中基于效率区间的负载均衡在线优化算法[J]. 电子与信息学报, 2019, 41(3): 694-701. doi: 10.11999/JEIT180464 shu
Citation:  Jiugen SHI, Hao XU, Jing ZHANG, Ji WANG. An Efficient Online Algorithm for Load Balancing in Software Defined Networks Based on Efficiency Range[J]. Journal of Electronics and Information Technology, 2019, 41(3): 694-701. doi: 10.11999/JEIT180464 shu

软件定义网络中基于效率区间的负载均衡在线优化算法

    作者简介: 史久根: 男,1963年生,副教授,研究方向为嵌入式系统、计算机网络和无线传感器网络;
    徐皓: 男,1994年生,硕士生,研究方向为软件定义网络、网络负载均衡和嵌入式系统;
    张径: 男,1993年生,硕士生,研究方向为软件定义网络、网络虚拟化和规则放置;
    王继: 男,1993年生,硕士生,研究方向为软件定义网络、网络虚拟化和规则缓存
    通讯作者: 徐皓,2016170681@mail.hfut.edu.cn
  • 基金项目: 国家重大科学仪器设备开发专项(2013YQ030595)

摘要: 在大型复杂软件定义网络中,为提高网络负载均衡,减少控制器与交换机间的传播时延,该文提出一种基于效率区间的负载均衡在线优化算法。在初始静态网络中,通过贪心算法选择初始控制器集合,并以其为根节点构建M棵改进代价的最小生成树(MST),确定初始M个负载均衡的子网;当网络流量发生变化时,通过广度优先搜索(BFS)调整子网间交换机映射关系使其满足效率区间,保证任意时刻网络的负载均衡。算法均以网络连通性为基础,且均以传播时延为目标重新更新控制器集合。仿真实验表明,该算法在保证任意时刻网络负载均衡的同时,可以保证较低的传播时延,与Pareto模拟退火算法、改进的K-Means算法等相比,可以使网络负载均衡情况平均提高40.65%。

English

    1. [1]

      HLLER B, SHEERWOOD 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]

      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, Vancouver, Canada, 2010: 351–364.

    3. [3]

      TOOTOONCHIAN A and GANJALI Y. HyperFlow: A distributed control plane for OpenFlow[C]. Internet Network Management Conference on Research on Enterprise Networking, San Francisco, USA, 2010: 3–8.

    4. [4]

      YU M, REXDORD J, FREEDMAN M J, et al. Scalable flow-based networking with DIFANE[J]. ACM Sigcomm Computer Communication Review, 2010, 40(4): 351–362. doi: 10.1145/1851275.1851224

    5. [5]

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

    6. [6]

      张栋, 郭俊杰, 吴春明. 层次型多中心的SDN控制器部署[J]. 电子学报, 2017, 45(3): 680–686. doi: 10.3969/j.issn.0372-2112.2017.03.027
      ZHANG Dong, GUO Junjie, and WU Chunming. Controller placement based on hierarchical multi-center SDN[J]. Acta Electronica Sinica, 2017, 45(3): 680–686. doi: 10.3969/j.issn.0372-2112.2017.03.027

    7. [7]

      SAHOO K S, SAHOO B, DASH R, et al. Optimal controller selection in software defined network using a greedy-SA algorithm[C]. International Conference on Computing for Sustainable Global Development, New Delhi, India, 2016: 2342–2346.

    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]

      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

    10. [10]

      JIMENEZ Y, CERVALLO-PASTOR C, and GARCIA A J. On the controller placement for designing a distributed SDN control layer[C]. NETWORKING Conference, Trondheim, Norway, 2014: 1–9.

    11. [11]

      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 & Service Management, 2015, 12(1): 4–17. doi: 10.1109/TNSM.2015.2402432

    12. [12]

      JALILI A, AHMADI V, KESHTGARI M, et al. Controller placement in software-defined WAN using multi objective genetic algorithm[C]. International Conference on Knowledge-Based Engineering and Innovation, Tehran, Iran, 2016: 656–662.

    13. [13]

      RATH H K, REVVOORI V, NADAF S M, et al. Optimal controller placement in software defined networks (SDN) using a non-zero-sum game[C]. International Symposium on A World of Wireless, Mobile and Multimedia Networks, Sydney, Australia, 2014: 1–6.

    14. [14]

      史久根, 邾伟. 软件定义网络中基于负载均衡的多控制器部署算法[J]. 电子与信息学报, 2018, 40(2): 455–461. doi: 10.11999/JEIT170464
      SHI Jiugen and ZHU Wei. 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

    15. [15]

      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

    16. [16]

      覃匡宇, 黄传河, 王才华, 等. SDN网络中受时延和容量限制的多控制器均衡部署[J]. 通信学报, 2016, 37(11): 90–103. doi: 10.11959/j.issn.1000-436x.2016219
      QIN Kuangyu, HUANG Chuanhe, WANG Caihua, et al. Balanced multiple controllers placement with latency and capacity bound in software-defined network[J]. Journal on Communications, 2016, 37(11): 90–103. doi: 10.11959/j.issn.1000-436x.2016219

    1. [1]

      史久根, 谢熠君, 孙立, 郭胜, 刘雅丽. 软件定义网络中面向时延和负载的多控制器放置策略. 电子与信息学报, 2019, 41(8): 1869-1876.

    2. [2]

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

    3. [3]

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

    4. [4]

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

    5. [5]

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

    6. [6]

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

    7. [7]

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

    8. [8]

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

    9. [9]

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

    10. [10]

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

    11. [11]

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

    12. [12]

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

    13. [13]

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

    14. [14]

      柴蓉, 王令, 陈明龙, 陈前斌. 基于时延优化的蜂窝D2D通信联合用户关联及内容部署算法. 电子与信息学报, 2019, 41(11): 2565-2570.

    15. [15]

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

    16. [16]

      张鹤玖, 余宁梅, 吕楠, 刘尕. 一种用于时延积分CMOS图像传感器的10 bit全差分双斜坡模数转换器. 电子与信息学报, 2019, 41(6): 1466-1471.

    17. [17]

      寇广, 王硕, 张达. 基于深度堆栈编码器和反向传播算法的网络安全态势要素识别. 电子与信息学报, 2019, 41(9): 2187-2193.

    18. [18]

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

    19. [19]

      崔维嘉, 张鹏, 巴斌. 基于循环匹配追踪的稀疏重构时延估计算法. 电子与信息学报, 2019, 41(3): 523-529.

    20. [20]

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

  • 图 1  网络负载均衡情况

    图 2  网络平均时延情况

    图 3  最优效率区间

    图 4  网络平均时延情况

    表 1  初始M控制域选择算法

     算法1:初始M控制域选择算法(IMCDS)
     输入:$G = (V, E) , f, {\rm{MLCC}}, {T_{\rm max}}, {W}, D, {\rm{ID}}, $
        $ \{ {\rm{Flag}}, {\rm{Temp}}, {\rm{ICon}}, {\rm{IS}}\} = \varnothing $
     输出:${\rm{ICon}}, {\rm{IS}}$
     (1) $M \leftarrow {{\displaystyle\sum\nolimits_{i = 1}^{\left| V \,\right|} {{f_i}} }}\Bigr/{{\rm{OL}}} , {\rm{OL}} = 0.85 \times {\rm{MLCC}}$;
     (2) ${\rm{ICon}} \leftarrow {C_1}, {C_1} \in \{ \max (D) \cap \max ({\rm{ID}})\} $;
     (3) Adopt $ { \rm{Prim}} ({C_1}, {W}, {\rm{OL}}) $ to construct first improved MST
    based 式(11) and 式(12);
     (4) Update $ {\rm{IS}}_1, {\rm{Flag}}_1 \leftarrow 1, {\rm{Temp}} \leftarrow 1$;
     (5) do
     (6)  ${\rm{ICon}} \leftarrow {C_i}, {C_i} \in \{ {\rm{Flag}}_i = 0 \cap {\rm{furthest \;from\;}} {\rm{ICon}} \cap $
    $ \max (D) \cap \max ({\rm{ID}}),i = 1, ·\!·\!· , n\} $;
     (7)  Adopt $ { \rm{Prim}} ({C_i}, {W}, {\rm{OL}}) $ to construct improved MST
    based on 式(11) and 式(12);
     (8)  Update $ {\rm{IS}}_i, {\rm{Flag}}_i \leftarrow 1, {\rm{Temp}} \leftarrow {\rm{Temp}} + 1$;
     (9) while $ {\rm{Temp}} > M, {\rm{the \ network \ has \ been \ divided \ into}} \ $ M
    domains;
     (10) if there are nodes has not been selected do
     (11)  Add nodes to one closest improved MST by BFS based
    on 式(11) and 式(12);
     (12)  Update ${\rm{IS}} , {\rm{Flag}} \leftarrow 1$;
     (13) end if
     (14) Update centroids ${\rm{ICon}} = \{ {C_1}, {C_2}, ·\!·\!· , {C_M}\} $ based on the
    sum of the shortest distance from all switches in ${\rm{IS}} _i $ to
    new controller $ {C_i}$ is minimized;
     (15) Output ${\rm{ICon}} , {\rm{IS}}$。
    下载: 导出CSV

    表 2  M控制域调整算法

     算法2:M控制域调整算法(M-CDA)
     输入:$G = (V, E), {T_{\max}}, f, {\rm{MLCC}}, (\alpha , \beta ), {\rm{ICon}}, {\rm IS}, T, $
    $ \{ {\rm{LS}}, {\rm{LCon}}, {\rm{TNS}}\} = \varnothing $
     输出:${\rm{LCon}}, {\rm{LS}}$
     (1) for all $ {\rm{}} t\; {\rm{with}} \;0 \le t \le T\; $ do
     (2)  for each $ i \in M $ do
     (3)   ${\rm{TNS}} \leftarrow {\rm{BV}}_{i, j}, {\rm{BV}}_{i, j} \in \{ {\rm{furthest}} \;{\rm{from}} \; $
    $ {\rm{ICon}}_i \cap\max \left(f_{i1}^t, ·\!·\!· ,f_{ij}^t\right) ,j \in {\rm{IS}}_i\} $;
     (4)   end for
     (5)  for each $ i \in M $ do
     (6)   if $\sum\nolimits_{l = t - 1}^t {\rm{L C}}_i^l < \alpha \times {\rm{MLCC}} $ do
     (7)    Add nodes in TNS closest from $ {\rm{ICon}}_i$ to ISi by BFS
    based 式(11),式(12),式(13);
     (8)   end if
     (9)   if $\sum\nolimits_{l = t - 1}^t {\rm{L C}}_i^l > \beta \times {\rm{MLCC}} $ do
     (10)   Add nodes in ISi furthest from ${\rm{ICon}}_i$ to TNS by BFS
    based 式(11),式(12),式(13);
     (11)   end if
     (12)  end for
     (13)  Compute function
          ${\rm{ }} {F_t} = \mu \times ({\rm{NLBI}}^t - 1) + \nu \times \sum\limits_{j = 1}^M {{\rm{TRDT}}_j^t} $
     (14)  if ${F_t} < {F_{t - 1}} $ do
     (15)   ${\rm{LS}} \leftarrow {\rm{IS}}$;
     (16)  end if
     (17) end for
     (18) Update centroids $ {\rm{ICon}} = \{ {C_1}, {C_2}, ·\!·\!· , {C_M}\} $ based on the
    sum of the shortest distance from all switches in ${\rm{}} {\rm{LS}}_i $ to
    new controller Ci is minimized, ${\rm{LCon}} \leftarrow {\rm{ICon}}$;
     (19) Output $ {\rm{LCon}}, {\rm{LS}}$。
    下载: 导出CSV

    表 3  网络拓扑节点数和链路数分布

    网络名称NoelDarkstrandOS3EArnesNtelosSurfnet
    节点数192834344850
    链路数353143496173
    下载: 导出CSV

    表 4  初始静态情况下多网络拓扑的负载均衡情况

    子网络数NoelDarkstrandOS3EArnesNtelosSurfnet
    21.051.001.001.001.001.00
    31.101.071.061.061.001.02
    41.261.141.061.061.081.04
    51.051.071.031.181.251.20
    61.261.061.061.061.131.08
    71.481.251.031.231.171.12
    81.521.431.181.411.171.12
    下载: 导出CSV

    表 5  动态情况下多网络拓扑的负载均衡情况

    子网络数NoelDarkstrandOS3EArnesNtelosSurfnet
    21.081.041.021.041.031.05
    31.091.101.081.111.061.03
    41.181.231.121.161.081.09
    51.201.251.131.231.181.15
    61.341.281.261.281.121.31
    71.411.331.381.361.331.24
    81.511.481.261.341.231.18
    下载: 导出CSV
  • 加载中
图(4)表(5)
计量
  • PDF下载量:  46
  • 文章访问数:  342
  • HTML全文浏览量:  219
文章相关
  • 通讯作者:  徐皓, 2016170681@mail.hfut.edu.cn
  • 收稿日期:  2018-05-15
  • 录用日期:  2018-09-20
  • 网络出版日期:  2018-10-22
  • 刊出日期:  2019-03-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章