高级搜索

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

史久根 徐皓 张径 王继

引用本文: 史久根, 徐皓, 张径, 王继. 软件定义网络中基于效率区间的负载均衡在线优化算法[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]

      向敏, 饶华阳, 张进进, 陈梦鑫. 基于GCN的软件定义电力通信网络路由控制策略. 电子与信息学报, 2020, 42(0): 1-8.

    2. [2]

      吴奇, 陈鸿昶. 软件定义网络容错控制平面的最小覆盖布局方法. 电子与信息学报, 2020, 42(0): 1-8.

    3. [3]

      左志斌, 常朝稳, 祝现威. 一种基于数据平面可编程的软件定义网络报文转发验证机制. 电子与信息学报, 2020, 42(5): 1110-1117.

    4. [4]

      归伟夏, 陆倩, 苏美力. 关于系统级故障诊断的烟花-反向传播神经网络算法. 电子与信息学报, 2020, 42(5): 1102-1109.

    5. [5]

      唐伦, 魏延南, 谭颀, 唐睿, 陈前斌. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略. 电子与信息学报, 2020, 42(5): 1244-1252.

    6. [6]

      黄静琪, 胡琛, 孙山鹏, 高翔, 何兵. 一种基于异步传感器网络的空间目标分布式跟踪方法. 电子与信息学报, 2020, 42(5): 1132-1139.

    7. [7]

      刘焕淋, 杜理想, 陈勇, 胡会霞. 串扰感知的空分弹性光网络频谱转换器稀疏配置和资源分配方法. 电子与信息学报, 2020, 42(7): 1718-1725.

    8. [8]

      晋守博, 魏章志, 李耀红. 基于大通讯时滞的2阶多智能体系统的一致性分析. 电子与信息学报, 2020, 42(0): 1-6.

    9. [9]

      宋晨, 周良将, 吴一戎, 丁赤飚. 基于时频集中度指标的多旋翼无人机微动特征参数估计方法. 电子与信息学报, 2020, 42(0): 1-8.

    10. [10]

      张颖君, 陈恺, 鲍旭华. 一种基于程序执行时间量化分析的软件水印方法. 电子与信息学报, 2020, 41(0): 1-9.

    11. [11]

      董亚非, 胡文晓, 钱梦瑶, 王越. 基于DNA适配体的荧光生物传感器. 电子与信息学报, 2020, 42(6): 1374-1382.

    12. [12]

      雷维嘉, 杨苗苗. 时间反转多用户系统中保密和速率优化的预处理滤波器设计. 电子与信息学报, 2020, 42(5): 1253-1260.

    13. [13]

      吕敬祥, 罗文浪. 无线传感网络量化及能量优化策略. 电子与信息学报, 2020, 42(5): 1118-1124.

    14. [14]

      徐瑨, 吴慧慈, 陶小峰. 5G网络空间安全对抗博弈. 电子与信息学报, 2020, 41(0): 1-11.

    15. [15]

      缪祥华, 单小撤. 基于密集连接卷积神经网络的入侵检测技术研究. 电子与信息学报, 2020, 41(0): 1-7.

    16. [16]

      游凌, 李伟浩, 张文林, 王科人. 基于深度神经网络的Morse码自动译码算法. 电子与信息学报, 2020, 41(0): 1-6.

    17. [17]

      李劲松, 彭建华, 刘树新, 季新生. 一种基于线性规划的有向网络链路预测方法. 电子与信息学报, 2020, 41(0): 1-9.

    18. [18]

      杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法. 电子与信息学报, 2020, 42(5): 1140-1148.

    19. [19]

      张惊雷, 厚雅伟. 基于改进循环生成式对抗网络的图像风格迁移. 电子与信息学报, 2020, 42(5): 1216-1222.

    20. [20]

      赵国繁, 唐伦, 胡彦娟, 赵培培, 陈前斌. 面向可靠性的5G网络切片重构及映射算法. 电子与信息学报, 2020, 42(6): 1478-1485.

  • 图 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下载量:  51
  • 文章访问数:  874
  • HTML全文浏览量:  331
文章相关
  • 通讯作者:  徐皓, 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搜索

/

返回文章