基于随机生成树的SDN控制平面冗余容错算法

doi:10.3969/j.issn.1006-2475.2025.01.0.017

摘要/Abstract

摘要： 针对软件定义网络中控制平面容错布局问题，提出一种基于随机生成树的控制器布局算法DRT2CA（Minimum Two Covering Algorithm Based on Dynamic Random Spanning Tree）。该算法旨在保证冗余容错的前提下，最小化控制器数量，降低控制平面的部署成本。通过不断生成随机生成树，并在树上采用贪心策略进行控制器布局搜索，DRT2CA算法以更少的控制器实现最小的冗余容错覆盖，有效提高系统资源利用率。实验结果表明，在不同网络规模和控制器容量下，DRT2CA算法相较于现有的冗余控制器部署算法，能够以更少的控制器部署数量实现容错控制平面布局，具有更高的冗余布局效率，为构建高效、可靠的SDN控制平面提供了创新性的解决方案。

关键词: 软件定义网络, 控制器放置问题, 容错, 最小二覆盖

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

中图分类号:

TP393

郭小奉, 庄毅. 基于随机生成树的SDN控制平面冗余容错算法[J]. 计算机与现代化, 2025, 0(01): 107-112.

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.

参考文献

［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]	肖军弼, 邱艺. 基于状态感知数据平面的SDN故障检测与恢复方案[J]. 计算机与现代化, 2024, 0(12): 116-123.
[2]	张昊, 路红英. 面向边缘计算应用的拜占庭式容错分布式一致性算法[J]. 计算机与现代化, 2022, 0(12): 33-41.
[3]	胡全贵，赵恩来，贾伟昭，开北强. 数据中心巡检机器人信息平台实时任务容错调度算法[J]. 计算机与现代化, 2020, 0(05): 50-.
[4]	王骞，闫夏莉，叶崛宇，张海阔，李真辉 . 面向权威DNS的数据一致性保障机制[J]. 计算机与现代化, 2020, 0(02): 36-.
[5]	董奇1,黄斌1,颜耀1,李韦韦2,曾玮妮2,张恒1,3. 分布式计算系统回卷恢复容错的仿真设计[J]. 计算机与现代化, 2017, 0(4): 48-51.
[6]	王尚超，汤小春. 异构集群中基于优先级的任务容错调度算法[J]. 计算机与现代化, 2014, 0(4): 69-72.
[7]	黄晗. 基于R-OSGi的平台容错架构设计与实现[J]. 计算机与现代化, 2013, 1(9): 66-70,7.
[8]	陈鹰翔;应忍冬;朱新忠;李超;刘佩林. 航天器上众核系统自修复方案设计[J]. 计算机与现代化, 2013, 218(10): 153-158.
[9]	张科伦. 分布式系统中纠删码容错机制的研究与实现 [J]. 计算机与现代化, 2012, 8(08): 47-50.
[10]	李旺远;王长山. Mesh跳步容错路由算法[J]. 计算机与现代化, 2010, 1(3): 39-4.