| 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 & Information Technology, 2019, 41(3): 694-701. doi: 10.11999/JEIT180464
|
Due to the limitation of individual controller’s processing capacity in large-scale complex Software Defined Networks (SDN), an efficient online algorithm for load balancing among controllers based on efficiency range is proposed to improve load balancing among controllers and reduce the propagation delay between a controller and the switch. In the initial static network, the initial set of controllers is selected by a greedy algorithm, then M improved Minimum Spanning Trees (MST) rooted at the initial set of controllers are constructed, so initial M subnets with load balancing are determined. With the dynamic changes of load, for the purpose of making the controller work within efficiency range at any time, several switches in different subnets are reassigned by Breadth First Search (BFS). The initial set of controllers is updated for minimizing propagation delay in the algorithms’ last step. The algorithm is based on the connectivity of intra-domain and inter-domain. Simulation results show that the proposed algorithms not only guarantee the load balancing among controllers, but also guarantee the lower propagation delay. As to compare to PSA algorithm, optimized K-Means algorithm, etc., it can make Network Load Balancing Index (NLBI) averagely increase by 40.65%.
|
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
|
|
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.
|
|
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.
|
|
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
|
|
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.
|
|
张栋, 郭俊杰, 吴春明. 层次型多中心的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
|
|
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.
|
|
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
|
|
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
|
|
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.
|
|
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
|
|
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.
|
|
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.
|
|
史久根, 邾伟. 软件定义网络中基于负载均衡的多控制器部署算法[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
|
|
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
|
|
覃匡宇, 黄传河, 王才华, 等. 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
|
Figures(4) / Tables(5)
DownLoad:
