Randomized Spanning Tree Based Redundant Fault Tolerance Algorithm for SDN Control Plane

doi:10.3969/j.issn.1006-2475.2025.01.0.017

Abstract

Abstract: In this study， a random spanning tree-based controller layout algorithm DRT2CA （Minimum Two Covering Algorithm Based on Dynamic Random Spanning Tree） is proposed for the control plane fault-tolerant layout problem in software-defined networks. The algorithm aims to minimize the number of controllers and reduce the deployment cost of the control plane under the premise of guaranteeing redundancy fault tolerance. By continuously generating random spanning trees and employing greedy strategies for controller layout search on the tree， the DRT2CA algorithm achieves the minimum redundancy fault-tolerant coverage with fewer controllers and effectively improves the system resource utilization. The experimental results show that under different network scales and controller capacities， the DRT2CA algorithm is able to realize fault-tolerant control plane layout with fewer controllers deployed compared to existing redundant controller deployment algorithms， has higher redundancy layout efficiency， and is able to provide an innovative solution for constructing an efficient and reliable SDN control plane.

Key words: , software defined networks, controller placement problem, fault tolerance, least two coverage

CLC Number:

TP393

GUO Xiaofeng, ZHUANG Yi. Randomized Spanning Tree Based Redundant Fault Tolerance Algorithm for SDN Control Plane[J]. Computer and Modernization, 2025, 0(01): 107-112.

References

［1］ AL-QEREM A， ALAUTHMAN M， ALMOMANI A， et al. IoT transaction processing through cooperative concurrency control on fog-cloud computing environment［J］. Soft Computing， 2020，24（8）：5695-5711.
［2］ MASDARI M， GHAREHPASHA S， GHOBAEI-ARANI M， et al. Bio-inspired virtual machine placement schemes in cloud computing environment： Taxonomy， review， and future research directions［J］. Cluster Computing， 2020，23（4）：2533-2563.
［3］ QI Y Z， WANG D B， YAO W B， et al. Towards multi-controller placement for SDN based on density peaks clustering［C］// ICC 2019-2019 IEEE International Conference on Communications. IEEE， 2019. DOI： 10.1109/ICC.2019.
8761814.
［4］ IQBAL S， QURESHI K N， SHOAIB F， et al. Minimize the delays in software defined network switch controller communication［J］. Concurrency and Computation： Practice and Experience， 2022，34（13）. DOI： 10.1002/cpe.5940.
［5］ DIXIT A， HAO F， MUKHERJEE S， et al. Towards an elastic distributed SDN controller［J］. ACM SIGCOMM Computer Communication Review， 2013，43（4）：7-12.
［6］ TAMIZHSELVAN C， VIJAYALAKSHMI V. SDN-MCHO： Software define network based multi-criterion hysteresis optimization based for reliable device routing in Internet of things for the smart surveillance application［J］. Computer Communications， 2020，153：632-640.
［7］ XIE J J， GUO D K， HU Z Y， et al. Control plane of software defined networks： A survey［J］. Computer Communications， 2015，67：1-10.
［8］ KOPONEN T， CASADO M， GUDE N， et al. Onix： A distributed control platform for large-scale production networks［C］// 9th USENIX Symposium on Operating Systems Design and Implementation （OSDI 10）. Curran Associates， 2010：351-365.
［9］ TOOTOONCHIAN A， GANJALI Y. HyperFlow： A distributed control plane for openflow［C］// Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking. ACM， 2010：10-15.
［10］ FAN Y Q， WANG L F， YUAN X H. Controller placements for latency minimization of both primary and backup paths in SDNs［J］. Computer Communications， 2020，163：35-50.
［11］ LI H， LI P， GUO S. et al. Byzantine-resillent secure software-defined networks with multiple controllers in cloud［J］. IEEE Transactions on Cloud Computing， 2014，2（4）：436-447.
［12］史久根，谢熠君，孙立，等. 软件定义网络中面向时延和负载的多控制器放置策略［J］. 电子与信息学报， 2019，41（8）：1869-1876.
［13］史久根，邾伟，贾坤荥，等. 软件定义网络中基于负载均衡的多控制器部署算法［J］. 电子与信息学报， 2018，40（2）：455-461.
［14］ JIMENEZ Y，CERVELLO-PASTOR C，GARCIA AJ．On the controller placement for designing a distributed SDN control layer［C］∥ 2014 IFIP Networking Conference. IEEE， 2014. DOI： 10.1109/IFIPNetworking.2014.6857117.
［15］ KOTACHI S， SATO T， SHINKUMA R， et al. Fault-tolerant controller placement model by distributing switch load among multiple controllers in software-defined network［J］. IEICE Transactions on Communications， 2022，105（5）：533-544.
［16］ RADAM N S， AL-JANABI S T F， JASIM K S. Multi-controllers placement optimization in SDN by the hybrid HSA-PSO algorithm［J］. Computers， 2022，11（7）. DOI： 10.3390/computers11070111.
［17］ ROS F J， RUIZ P M. On reliable controller placements in software-defined networks［J］. Computer Communications， 2016，77：41-51.
［18］ SAPKOTA A B， DAWADI B B R， JOSHI C S R. Multi-controller placement optimization using naked mole-rat algorithm over software-defined networking environment［J］. Journal of Computer Networks and Communications， 2022，2022（1）. DOI： 10.1155/2022/3145276.
［19］ LI C L， JIANG K， LUO Y L. Dynamic placement of multiple controllers based on SDN and allocation of computational resources based on heuristic ant colony algorithm［J］. Knowledge-Based Systems， 2022，241. DOI： 10.1016/j.kn
osys.2022.108330.
［20］ XIA C Y， ZHANG Y， LIU Y L， et al. Path planning and energy flow control of wireless power transfer for sensor nodes in wireless sensor networks［J］. Turkish Journal of Electrical Engineering and Computer Sciences， 2018，26（5）：2618-2632.
［21］ XIE J J， GUO D K， ZHU X M， et al. Minimal fault-tolerant coverage of controllers in IaaS datacenters［J］. IEEE Transactions on Services Computing， 2020，13（6）：1128-1141.
［22］吴奇，陈鸿昶. 软件定义网络容错控制平面的最小覆盖布局方法［J］. 电子与信息学报， 2020，42（12）：2849-2856.
［23］ DHAR M， DEBNATH A， BHATTACHARYYA B K， et al. A comprehensive study of different objectives and solutions of controller placement problem in software‐defined networks［J］. Transactions on Emerging Telecommunications Technologies， 2022，33（5）. DOI： 10.1002/ett.4440.
［24］ HUNG E， KAO M J. Approximation algorithm for vertex cover with multiple covering constraints［J］. Algorithmica， 2022，84（1）：1-12.
［25］ SINGH A K， SRIVASTAVA S， BANERJEA S. Evaluating heuristic techniques as a solution of controller placement problem in SDN［J］. Journal of Ambient Intelligence and Humanized Computing， 2023，14（9）：11729-11746.

[1]	HAN Xiaolong, ZENG Xi, LIU Kun, SHANG Yu. Stance Detection with LoRA-based Fine-tuning General Language Model [J]. Computer and Modernization, 2025, 0(01): 1-6.
[2]	XU Shengchao, CHEN Fuqiang. A Food Safety Risk Warning Method Based on BP Neural Network [J]. Computer and Modernization, 2025, 0(01): 20-24.
[3]	YAN Xiaoqi, PENG Yiqing, REN Xiaoling. Point Cloud Data Classification Method of PointNet++ with Position Adaptive Convolution [J]. Computer and Modernization, 2025, 0(01): 44-49.
[4]	ZHANG Yue, LI Huayu, ZHANG Zhikang, SHEN Xinyi. Academic Recommendation System Based on Knowledge Graph and Semantic Information [J]. Computer and Modernization, 2025, 0(01): 50-58.
[5]	XIE Zetao, ZHUANG Yi . Transient Fault Detection for Low-orbit Internet Communication System Based on CatBoost [J]. Computer and Modernization, 2025, 0(01): 59-66.
[6]	LIU Haitao, FENG Fan. BD Based Lattice Reduction Assisted Continuous Interference Cancellation Detection Algorithm [J]. Computer and Modernization, 2025, 0(01): 67-73.
[7]	LI Qiusheng1, LI Wei1, ZHOU Dongxu1, GUO Chuang1, JIN Wenxin 2. Optical Fiber Timing Synchronization in Power Systems Based on ARIMA-ELM Algorithm [J]. Computer and Modernization, 2025, 0(01): 74-79.
[8]	LI Xi, PAN Yu. Ground Penetrating Radar Pipeline Object Detection Method Based on Improved YOLOv8 [J]. Computer and Modernization, 2025, 0(01): 94-99.
[9]	TU Fuquan, QI Yanqi, LIU Jian, WANG Shufeng. Metal Gear Surface Defect Detection Algorithm Based on Improved YOLOv8s [J]. Computer and Modernization, 2025, 0(01): 100-106.
[10]	ZHENG Jiuchao, ZHAO Xinyuan. Entity Linking Method Based on Topics and Description Information [J]. Computer and Modernization, 2024, 0(12): 10-14.
[11]	ZHAO Chenyang, XUE Tao, LIU Junhua. Fashion Clothing Pattern Generation Based on Improved Stable Diffusion [J]. Computer and Modernization, 2024, 0(12): 15-23.
[12]	WANG Xiaohang1, LI Yongjie1, YU Lei1, FAN Xiao2. A Method of Using Compound Event Probability Operation to Solve Problem of Negative Information Blocking Maximization [J]. Computer and Modernization, 2024, 0(12): 24-33.
[13]	ZHANG Xiaodong1, BAI Guangzhi1, LI Min1, LI Haoyang2. Oil and Gas Well Production Prediction Model Based on Empirical Wavelet Transform [J]. Computer and Modernization, 2024, 0(12): 53-58.
[14]	LIU Yunhai1, Feng Guang1, WU Xiaoting2, YANG Qun2 . Safety Helmet Wearing Detection Algorithm for Complex Construction Scenes [J]. Computer and Modernization, 2024, 0(12): 66-71.
[15]	LIU Baobao, YANG Jingjing, TAO Lu, WANG Heying . DSMSC Based on Attention Mechanism for Remote Sensing Image Scene Classification [J]. Computer and Modernization, 2024, 0(12): 72-77.