Load-aware optimal placement for heterogeneous controllers in software-defined networking based on unbalanced graph partitioning

doi:10.11772/j.issn.1001-9081.2016.04.0883

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (4): 883-888.DOI: 10.11772/j.issn.1001-9081.2016.04.0883

Load-aware optimal placement for heterogeneous controllers in software-defined networking based on unbalanced graph partitioning

WANG Yefu^1,2, ZENG Guosun¹, DING Chunling³

1. Department of Computer Science and Technology, Tongji University, Shanghai 200092, China;
2. State Key Laboratory of High-end Server & Storage Technology(INSPUR Company Limited), Jinan Shandong 250101, China;
3. Department of Chemistry, Tongji University, Shanghai 200092, China

Received:2015-10-02 Revised:2015-11-27 Online:2016-04-08 Published:2016-04-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61272107, 61202173, 61103068), the Open Foundation of the State Key Laboratory of High-end Server and Storage Technology (2014HSSA10), the Program of Shanghai Subject Chief Scientist (10XD1404400), the Huawei Innovation Research Project (IRP-2013-12-03).

基于图非均衡划分的软件定义网络异构控制器负载优化部署

王也夫^1,2, 曾国荪¹, 丁春玲³

1. 同济大学计算机科学及技术系, 上海 200092;
2. 高效能服务器和存储技术国家重点实验室(浪潮集团有限公司), 济南 250101;
3. 同济大学化学系, 上海 200092

通讯作者: 王也夫
作者简介:王也夫(1991-),男,安徽安庆人,硕士研究生,主要研究方向:软件定义网络、SDN控制器管理模型; 曾国荪(1964-),男,江西吉安人,教授,博士,博士生导师,主要研究方向:并行计算、可信软件、信息安全; 丁春玲(1965-),女,江西宜春人,高级工程师,硕士,主要研究方向:建模分析。
基金资助:
国家自然科学基金资助项目(61272107, 61202173, 61103068);高效能服务器和存储技术国家重点实验室开放基金资助项目(2014HSSA10);上海市优秀学科带头人计划项目(10XD1404400);华为创新研究计划项目(IRP-2013-12-03)。

Abstract

Abstract: In wide-area Software Defined Networking (SDN) deployments, logically centralized controllers are usually physically placed in a distributed manner. To address the unbalanced controller load problem in controller placement, a load-aware optimal placement for heterogeneous controllers based on unbalanced graph partitioning was proposed. First, the controller placement problem and related metrics, controller load balance and latency, were analyzed. Secondly, controller load balance and latency caused by controller placement were quantified and computed using graph theory and cosine similarity. Moreover, based on graph partitioning theory, the load-aware controller placement problem was transformed into a specified graph partitioning problem. Finally, a load-aware optimal controller placement scheme was presented based on multi-level graph partitioning. Simulation experiments conducted on real network topologies indicate that the proposed scheme can effectively achieve nearly optimal controller load balance.

Key words: Software-Defined Networking (SDN), controller, optimal placement, graph partitioning, load balance

摘要： 大规模软件定义网络(SDN)往往需要逻辑上集中的控制器在物理上分布式部署。针对控制器部署中控制器负载不均衡的问题,提出一种基于图非均衡划分的SDN异构控制器负载优化部署方法。首先,分析控制器部署要求以及部署带来的控制器负载均衡和时延问题;其次,利用图论和余弦相似度,量化描述和计算异构控制器情况下的控制器负载均衡和时延,并运用图划分理论将控制器负载优化部署问题转化为一个具体的图划分问题;最后,基于多级划分的图划分思想,提出控制器负载优化部署方法。对实际网络拓扑的模拟实验结果表明,提出的部署方法可以有效实现接近最优的控制器负载分布。

关键词: 软件定义网络, 控制器, 优化部署, 图划分, 负载均衡

CLC Number:

TP393.02

WANG Yefu, ZENG Guosun, DING Chunling. Load-aware optimal placement for heterogeneous controllers in software-defined networking based on unbalanced graph partitioning[J]. Journal of Computer Applications, 2016, 36(4): 883-888.

王也夫, 曾国荪, 丁春玲. 基于图非均衡划分的软件定义网络异构控制器负载优化部署[J]. 计算机应用, 2016, 36(4): 883-888.

References

[1] KIM H, FEAMSTER N. Improving network management with software defined networking[J]. IEEE Communications Magazine, 2013, 51(2):114-119.
[2] HELLER B, SHERWOOD R, MCKEOWN N. The controller placement problem[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4):7-12.
[3] HU Y, WANG W, GONG X, et al. On the placement of controllers in software-defined networks[J]. The Journal of China Universities of Posts and Telecommunications, 2012, 19(2):92-97.
[4] HU Y, WANG W, GONG X, et al. On reliability-optimized controller placement for software-defined networks[J]. China Communications, 2014, 11(2):38-54.
[5] HU Y, WANG W, GONG X, et al. Reliability-aware controller placement for software-defined networks[J]. Wireless Communication Over Zigbee for Automotive Inclination Measurement China Communications, 2013, 11(2):672-675.
[6] BEHESHTI N, ZHANG Y. Fast failover for control traffic in software-defined networks[C]//Proceedings of the 2012 IEEE Global Communications Conference. Piscataway, NJ:IEEE, 2012, 2665-2670.
[7] 姚琳元, 陈颖, 宋飞, 等. 基于时延的软件定义网络快速响应控制器部署[J]. 电子与信息学报, 2014, 36(12):2802-2808.(YAO L Y, CHEN Y, SONG F, et al. Delay-aware controller placement for fast response in software-defined network[J]. Journal of Electronics & Information Technology, 2014, 36(12):2802-2808.)
[8] KREUTZ D, RAMOS F, VERISSIMO P, et al. Software-defined networking:a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1):14-76.
[9] Open Network Foundation. SDN architecture overview[EB/OL].[2015-08-01].https://www.opennetworking.org/images/stories/downloads/sdn-resources/technical-reports/TR_SDN-ARCH-Overview-1.1-11112014.02.pdf.
[10] MCKEOWN M, ANDERSON T, BALAKRISHNAN H, et al. Openflow:enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2):69-74.
[11] JAMMAL M, SINGH T, SHAMI A, et al. Software defined networking:state of the art and research challenges[J]. Computer Networks, 2014, 72:74-98.
[12] HOCK D, HARTMANN M, GEBERT S, et al. Pareto-optimal resilient controller placement in SDN-based core networks[C]//Proceedings of 25th International Teletraffic Congress. Piscataway, NJ:IEEE, 2013:1-9.
[13] 沈轶炜, 曾国荪. 异构计算中一种图的非均衡划分算法[J]. 计算机科学, 2006, 33(6):260-263.(SHEN Y W, ZENG G S. An unbalanced partitioning scheme for graphs in heterogeneous computing[J]. Computer Science, 2006, 33(6):260-263.)
[14] Center for Applied Internet Data Analysis. CAIDA data server[EB/OL].[2015-08-01]. http://data.caida.org/datasets/topology/ipv4.allpref24-aslinks/team-1/2015/.

[1]	Yiting SUN, Yue GUO, Changjin LI, Hongjun ZHANG, Kang LIU, Junjiao Liu, Limin SUN. Intrusion detection method for control logic injection attack against programmable logic controller [J]. Journal of Computer Applications, 2023, 43(6): 1861-1869.
[2]	Chao GE, Chenlei CHANG, Zheng YAO, Hao SU. Synchronous control of neural network based on event-triggered mechanism [J]. Journal of Computer Applications, 2023, 43(5): 1641-1646.
[3]	Qi GAO, Na LYU, Jingcheng MIAO. Wireless virtual network embedding algorithm based on load balance [J]. Journal of Computer Applications, 2022, 42(10): 3148-3153.
[4]	AN Xin, XIA Jinwei, YANG Haijiao, OUYANG Yiming, REN Fuji. Discrete controller synthesis based resource management method of heterogeneous multi-core processor system [J]. Journal of Computer Applications, 2020, 40(6): 1698-1706.
[5]	LI Zhongwei, TAN Kai, GUAN Yadong, JIANG Wenqi, YE Lin. In-vehicle CAN bus-off attack and its intrusion detection algorithm [J]. Journal of Computer Applications, 2020, 40(11): 3224-3228.
[6]	SU Zhenyu, SONG Guixiang, LIU Yanming, ZHAO Yuan. Threat modeling and application of server management control system [J]. Journal of Computer Applications, 2019, 39(7): 1991-1996.
[7]	JIN Tao, DONG Xiucheng, LI Yining, REN Lei, FAN Peipei. Optimization of fractional PID controller parameters based on improved PSO algorithm [J]. Journal of Computer Applications, 2019, 39(3): 796-801.
[8]	GUO Xuancheng, LIN Hui, YE Xiucai, XU Chuanfeng. Controller deployment and switch dynamic migration strategy in software defined WAN [J]. Journal of Computer Applications, 2019, 39(2): 453-457.
[9]	FAN Zifu, ZHOU Kaiheng, YAO Jie. Game theory based SDN master controller reselection mechanism [J]. Journal of Computer Applications, 2018, 38(3): 776-779.
[10]	GU Junhua, HUO Shijie, WU Junyan, YIN Jun, ZHANG Suqi. Parallel multi-layer graph partitioning method for solving maximum clique problems [J]. Journal of Computer Applications, 2018, 38(12): 3425-3432.
[11]	XU Lijie. Broadcasting energy-efficiency optimization algorithms for asymmetric duty-cycled sensor network [J]. Journal of Computer Applications, 2018, 38(11): 3275-3281.
[12]	FAN Zifu, YAO Jie, YANG Xianhui. Controller deployment strategy based on delay optimization in software defined network [J]. Journal of Computer Applications, 2018, 38(1): 207-211.
[13]	LUO Xiaoxia, SI Fengwei, LUO Xiangyu. Effects of large-scale graph structural feature on partitioning quality [J]. Journal of Computer Applications, 2018, 38(1): 1-5.
[14]	CHEN Dapeng, ZHANG Jiugen, LIANG Xing. Optimal control of chilled water system in central air-conditioning based on artificial immune and particle swarm optimization algorithm [J]. Journal of Computer Applications, 2017, 37(9): 2717-2721.
[15]	HU Huangshui, SHEN Weina, WANG Chuhang, ZHANG Bangcheng. Self-adaptive fuzzy controller based power control for wireless sensor networks [J]. Journal of Computer Applications, 2017, 37(9): 2470-2473.

Load-aware optimal placement for heterogeneous controllers in software-defined networking based on unbalanced graph partitioning

基于图非均衡划分的软件定义网络异构控制器负载优化部署

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics