A Survey on Multi-controller Consensus Mechanisms

doi:10.11871/jfdc.issn.2096-742X.2021.01.002

Abstract

Abstract:

[Background] With the increasing application of blockchain in infrastructures of the new generation of Internet in terms of the domain name, routing and public key system, the importance of blockchain is becoming increasingly prominent. As the core technology of blockchain or even the whole field of distributed system, consensus algorithms directly affect the transaction processing capacity, scalability and security of blockchain, as well as their role as a foundation in Internet infrastructure. [Objective] In this paper, we introduce the consensus mechanism for sharing data among multiple controllers in Software Defined Network (SDN), analyze the problems existing in the current design and propose solutions, and provide a reference for relevant research work. [Methods] Based on the classic distributed consensus algorithms, this paper summarizes the research status of consensus mechanism with a focus on the consensus in the multi-controller layer of SDN and the existing problems, proposes solutions based on the blockchain technology, and introduces the current research status of applying blockchain technology to SDN. [Results] The consensus mechanisms in the multi-controller cluster of SDN are mainly represented by Raft-like fault-tolerant consensus mechanisms in actual deployment, which cannot deal with the malicious behaviors to controllers or switches. Some existing researches have tried to introduce Byzantine fault-tolerant consensus mechanism, and improve the system performance adaptively. However, in the current SDN control layer, the consensus mechanism used to realize data sharing among controllers still has some problems, such as inflexible deployment of consensus network and huge cost caused by the controller consensus mechanism. [Conclusions] The third-party data-sharing service on controller layer based on blockchain proposed in this paper has advantages in security, credibility and flexible deployment, etc., which can provide solutions to solve the above mentioned problems. As an extended architecture of data sharing service, the credible blockchain-based SDN infrastructure proposed in this paper can provide a variety of secure and trusted services for SDN.

Key words: blockchain, multi-controller, consensus, SDN, Byzantine fault tolerance

GUAN Jianfeng,NIU Xiaotong,GAO Xianming,YAN Zhiwei. A Survey on Multi-controller Consensus Mechanisms[J]. Frontiers of Data and Computing, 2021, 3(1): 15-33.

Figures/Tables 7

Table 1

Summary of consensus mechanisms"

分类	名称	提出年份	拜占庭容错（容错比例）	去中心化程度	交易处理效率	是否需要代币	区块链应用场景
经典分布式共识	Paxos^[20]	1989	否（< ）	低	高	否	联盟链/私有链
	Raft^[21]	2013	否（< ）	低	高	否	联盟链/私有链
	PBFT^[12]	1999	是（< ）	低	高	否	联盟链/私有链
	QU^[22]	2005	是（< ）	低	高	否	联盟链/私有链
	HQ^[23]	2006	是（< ）	低	高	否	联盟链/私有链
	Zyzzyva^[24]	2007	是（< ）	低	高	否	联盟链/私有链
	Zeno^[25]	2009	是（< ）	低	高	否	联盟链/私有链
	Zzyzx^[26]	2010	是（< ）	低	高	否	联盟链/私有链
	Aardvark^[27]	2009	是（< ）	低	高	否	联盟链/私有链
	Spinning^[28]	2009	是（< ）	低	高	否	联盟链/私有链
	Prime^[29]	2011	是（< ）	低	高	否	联盟链/私有链
	RBFT^[30]	2013	是（< ）	低	高	否	联盟链/私有链
	Hot-Stuff^[31]	2018	是（< ）	低	高	否	联盟链/私有链
	SBFT^[32]	2018	是（< ）	低	高	否	联盟链/私有链
	HoneyBadger^[33]	2016	是（< ）	低	高	否	联盟链/私有链
	VABA^[34]	2018	是（< ）	低	高	否	联盟链/私有链
区块链共识算法	比特币^[35]	2009	是（< ）	高	低	是	公有链
	以太坊^[36]	2014	是（< ）	高	低	是	公有链
	Bitcoin-NG^[37]	2016	是（< ）	高	低	是	公有链
	Peercoin^[38]	2012	是（< ）	高	较高	是	公有链
	DPoS^[39]	2013	是（< ）	中	较高	是	公有链
	Nextcoin^[40]	2013	是（< ）	高	较高	是	公有链
	Casper TFG^[41]	2015	是（< ）	高	较高	是	公有链
	Ouroboros^[42]	2017	是（< ）	高	较高	是	公有链
	Tendermint^[43]	2014	是（< ）	中	较高	是	公有链
	peerCensus^[44]	2016	是（< ）	中	较高	是	公有链
	ByzCoin^[45]	2016	是（< ）	中	较高	是	公有链
	Algorand^[46]	2016	是（< ）	中	较高	是	公有链
	Casper FFG^[47]	2017	是（<）	中	较高	是	公有链
	Thunderella^[48]	2018	是（< ）	中	较高	是	公有链

Table 1

Fig.1

Fig.2

Table 2

Comparison of adaptive BFT consensus mechanisms in multi-controller layer"

设计方案	研究动机	主要思想
MORPH^[73]	前期多控制器BFT共识方面的研究缺少对自适应控制器-交换机连接重新分配过程的分析,也没有考虑当控制器发生不同类型故障时分配策略的差异性设计。	当检测到控制器发生拜占庭故障或非拜占庭故障时,采取不同的交换机-控制器适应性重分配策略,并在分配时考虑当前分别处于正常和故障状态的控制器数量、控制器的最大延迟和能力等实时条件以达到最佳的网络配置从而降低通信开销。
BFT Protocols for Heterogeneous Resource Allocations in Distributed SDN Control Plane^[74]	前期的基于RSM的多控制器BFT共识机制设计的方法可扩展性较差,需要引入更有效的方法提高分布式SDN控制平面的总体吞吐量。	在MORPH的基础上,提出“基于组的一致执行分离”方法,适应性地为每个交换机分配控制器分组,考虑了当前各控制器通信延迟、执行能力等实时条件,所提议的模型与最先进的方法相比,在系统响应时间和通信开销方面明显减少。
P4BFT ^[75]	多控制器BFT类共识中存在着控制器间信息传输及消息识别匹配消耗过多CPU负载、引发额外延迟、增加重配置时间、对交换机具有专用功能要求使得部署灵活性差等问题。	提出一种基于P4的P4BFT机制,引入处理节点（processing node）执行匹配功能,来减少SDN控制器向其目标配置交换机所传输的消息总量;并通过考虑交换机处理能力和上限重构延迟等实时约束来优化处理节点的选择,从而减少控制平面负载和重配置时间。
BIRDSDN ^[77]	当前针对控制器-交换机映射重配置的研究,缺少对实时因素的考虑,导致交换机重新配置的时间长,无法为交换机选择最可靠的控制器,缺少针对多控制器层节点发生崩溃故障和拜占庭故障的快速检测和恢复方案。	在进行控制器-交换机映射更新时,适应性地考虑了通信链路故障概率、拓扑、负载、距离和延迟等实时因素,以使交换机能够分配到最可靠的控制器。

Table 2

Fig.3

Fig.4

Fig.5

References 83

[1]	严斌峰. 用规模化应用拉动区块链“新基建”[N]. 中国电子报, 2020-04-28(005).
[2]	孙毅, 范灵俊, 洪学海. 区块链技术发展及应用:现状与挑战[J]. 中国工程科学, 2018,20(2):27-32.
[3]	A. Papageorgiou, A. Mygiakis, K. Loupos and T. Krousarlis. DPKI: A Blockchain-Based Decentralized Public Key Infrastructure System[C]. 2020 Global Internet of Things Summit (GIoTS), Dublin, Ireland, 2020, pp. 1-5.
[4]	刘冰洋, 杨飞, 任首首, 魏鑫鹏, 杨雪, 王闯, 延志伟. 去中心化互联网基础设施[J]. 电信科学, 2019,35(08):74-87.
[5]	袁勇, 倪晓春, 曾帅, 等. 区块链共识算法的发展现状与展望[J]. 自动化学报, 2018,44(11):2011-2022.
[6]	郑敏, 王虹, 刘洪, 等. 区块链共识算法研究综述[J]. 信息网络安全, 2019, ( 7):8-24.
[7]	S. Scott-Hayward, S. Natarajan, S. Sezer. A survey of security in software defined networks[J]. IEEE Commun. Surveys Tuts., 2016,18(1):623-654.
[8]	王蒙蒙, 刘建伟, 陈杰, 毛剑, 毛可飞. 软件定义网络:安全模型、机制及研究进展[J]. 软件学报, 2016,27(04):969-992.
[9]	Yinbo Yu, Xing Li, Xue Leng, Libin Song, Kai Bu, Yan Chen, Jianfeng Yang, Liang Zhang, Kang Cheng, Xin Xiao. Fault Management in Software-Defined Networking: A Survey[J]. IEEE Communications Surveys & Tutorials, 2019,21(1):349-392.
[10]	F. Bannour, S. Souihi and A. Mellouk. Distributed SDN Control: Survey, Taxonomy, and Challenges[J]. IEEE Communications Surveys & Tutorials, 2018,20(1):333-354.
[11]	范捷, 易乐天, 舒继武. 拜占庭系统技术研究综述[J]. 软件学报, 2013,24(6):1346-1360.
[12]	Castro M, Liskov B. Practical Byzantine fault tolerance[C]// Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI). New Orleans, LA, USA, February 22-25, 1999: 173-186.
[13]	Cachin C. Vukoli M. Blockchain Consensus Protocols in the Wild[EB/OL]. 2017. https://arxiv.org/abs/1707.01873.
[14]	S. Bano. et al. Consensus in the age of blockchains[EB/OL]. 2017.https://arxiv.org/abs/1711.03936.
[15]	刘懿中, 刘建伟, 喻辉. 区块链共识机制研究: 典型方案对比[J]. 中兴通讯技术, 2018,24(6):2-7.
[16]	刘懿中, 刘建伟, 张宗洋, 等. 区块链共识机制研究综述[J]. 密码学报, 2019,6(4):395-432.
[17]	Garay J, Kiayias A . SoK: A Consensus Taxonomy in the Blockchain Era[J]. Cryptographers’Track at the RSA Conference, 2020,12006:284-318.
[18]	AKKOYUNLU E A, EKANADHAM K, HUBER R V. Some constraints and tradeoffs in the design of network communications[C]// Proceedings of the fifth ACM symposium on Operating systems principles, 1975: 67-74.
[19]	Lamport L, Shostak R, Pease M . The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982,4(3):382-401 .
[20]	L. Lamport. Paxos Made Simple[J]. ACM SIGACT, 2001,32(4):18-25.
[21]	Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]// 2014 USENIX Annual Technical Conference, 2014: 305-319.
[22]	Abd-El-Malek M, Ganger G R, Goodson G R, et al. Fault-scalable Byzantine fault-tolerant services[J]. ACM SIGOPS Operating Systems Review, 2005,39(5):59-74.
[23]	Cowling J, Myers D, Liskov B, et al. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance[C]// Proceedings of the 7th symposium on Operating systems design and implementation. 2006: 177-190.
[24]	Kotla R, Alvisi L, Dahlin M, et al. Zyzzyva: speculative byzantine fault tolerance[C]// Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles. 2007: 45-58.
[25]	Singh A, Fonseca P, Kuznetsov P, et al. Zeno: Eventually Consistent Byzantine-Fault Tolerance[C]// Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2009, April 22-24, 2009, Boston, MA, USA. 2009,9:169-184.
[26]	Hendricks J, Sinnamohideen S, Ganger G R, et al. Zzyzx: Scalable fault tolerance through Byzantine locking[C]// 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN). IEEE, 2010: 363-372.
[27]	Clement A, Wong E L, Alvisi L, et al. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults[C]// Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2009, April 22-24, 2009, Boston, MA, USA. 2009,9:153-168.
[28]	Veronese G S, Correia M, Bessani A N, et al. Spin one's wheels? Byzantine fault tolerance with a spinning primary[C]// 2009 28th IEEE International Symposium on Reliable Distributed Systems. IEEE, 2009: 135-144.
[29]	Amir Y, Coan B, Kirsch J, et al. Prime: Byzantine replication under attack[J]. IEEE transactions on dependable and secure computing, 2010,8(4):564-577.
[30]	Aublin P L, Mokhtar S B, Quéma V. Rbft: Redundant byzantine fault tolerance[C]// 2013 IEEE 33rd International Conference on Distributed Computing Systems. IEEE, 2013: 297-306.
[31]	Abraham I, Gueta G, Malkhi D. Hot-stuff the linear, optimal-resilience, one-message BFT devil[EB/OL].2018. http://arxiv.org/abs/1803.05069.
[32]	Gueta G G, Abraham I, Grossman S, et al. SBFT: a Scalable Decentralized Trust Infrastructure for Blockchains[EB/OL].2018. http://arxiv.org/abs/1804.01626.
[33]	Miller A, Xia Y, Croman K, et al. The honey badger of BFT protocols[C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 31-42.
[34]	Gueta G G, Abraham I, Malkhi D, Spiegelman A. Validated Asynchronous Byzantine Agreement with Optimal Resilience and Asymptotically Optimal Time and Word Communication [EB/OL]. 2018. http://arxiv.org/abs/1811.01332
[35]	Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[EB/OL].2008. http://bitcoins.info/bitcoin.pdf.
[36]	Buterin V. A next-generation smart contract and decentralized application platform[EB/OL].2014. https://whitepaperdatabase.com/wp-content/uploads/2017/09/Ethereum-ETH-whitepaper.pdf.
[37]	Eyal I, Gencer A E, Sirer E G, et al. Bitcoin-ng: A scalable blockchain protocol[C]// 13th USENIX symposium on networked systems design and implementation (NSDI’16). 2016: 45-59.
[38]	King S, Nadal S.M. PPcoin: Peer-to-peer crypto-currency with proof-of-stake[EB/OL]. 2012. https://www.peercoin.net/assets/paper/peercoin-paper.pdf.
[39]	I. Grigg, EOS — An introduction [EB/OL].2018. http://iang.org/papers/EOS_An_Introduction.pdf.
[40]	何洪亮 . 未来币(NXT):第二代虚拟货币的卓越代表[J]. 现代营销(下旬刊), 2016(09):107.
[41]	Zamfir V. Introducing Casper .the Friendly Ghost[EB/OL].2018. https://blog.ethereum.org/2015/08/01/introducing-casper-friendly-ghost/.
[42]	Kiayias A, Russell A, David B, et al. Ouroboros: A provably secure proof-of-stake blockchain protocol[C]// Annual International Cryptology Conference. Springer, Cham, 2017: 357-388.
[43]	J. Kwon, Tendermint: Consensus without mining[EB/OL].2014. https://tendermint.com/static/docs/tendermint.pdf.
[44]	Decker C, Seidel J, Wattenhofer R. Bitcoin meets strong consistency[C]// Proceedings of the 17th International Conference on Distributed Computing and Networking. 2016: 1-10.
[45]	Kogias E K, Jovanovic P, Gailly N, et al. Enhancing bitcoin security and performance with strong consistency via collective signing[C]// 25th USENIX security symposium (USENIX security 16). 2016: 279-296.
[46]	Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling byzantine agreements for cryptocurrencies[C]// Proceedings of the 26th Symposium on Operating Systems Principles. 2017: 51-68.
[47]	V. Buterin, V. Griffith. Casper the friendly finality Gadget. [EB/OL].2017. http://arxiv.org/abs/1710.09437
[48]	Pass R, Shi E. Thunderella: Blockchains with optimistic instant confirmation[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2018: 3-33.
[49]	Yang L, Dantu R, Anderson T, Gopal R. Forwarding and Control Element Separation (ForCES) Framework.2004. http://tools.ietf.org/html/rfc3746
[50]	McKeown N, Anderson T, Balakrishnan H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):69-74.
[51]	OpenDayLight Project[EB/OL].2017. http:// www.opendaylight.org/.
[52]	Berde P, Gerola M, Hart J, et al. ONOS: towards an open, distributed SDN OS[C]// Proceedings of the third workshop on Hot topics in software defined networking. 2014: 1-6.
[53]	Koponen T, Casado M, Gude N, et al. Onix: A distributed control platform for large-scale production networks[C]// Proceeding of 9th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2010,October 4-6, 2010, Vancouver, BC, Canada, Proceedings. 2010,10:1-6.
[54]	Zhou B, Wu C, Hong X, et al. Programming network via distributed control in software-defined networks[C]// 2014 IEEE International Conference on Communications (ICC). IEEE, 2014: 3051-3057.
[55]	Katta N, Zhang H, Freedman M, et al. Ravana: Controller fault-tolerance in software-defined networking[C]// Proceedings of the 1st ACM SIGCOMM symposium on software defined networking research. 2015: 1-12.
[56]	Phemius K, Bouet M, Leguay J. Disco: Distributed multi-domain sdn controllers[C]// 2014 IEEE Network Operations and Management Symposium (NOMS). IEEE, 2014: 1-4.
[57]	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. 2010,3.
[58]	Chandrasekaran B, Benson T. Tolerating SDN application failures with LegoSDN[C]// Proceedings of the 13th ACM workshop on hot topics in networks. 2014: 1-7.
[59]	Akella A, Krishnamurthy A. A highly available software defined fabric[C]// Proceedings of the 13th ACM Workshop on Hot Topics in Networks. 2014: 1-7.
[60]	Muqaddas A S, Bianco A, Giaccone P, et al. Inter-controller traffic in ONOS clusters for SDN networks[C]// 2016 IEEE International Conference on Communications (ICC). IEEE, 2016: 1-6.
[61]	Zhang Y, Ramadan E, Mekky H, et al. When raft meets SDN: How to elect a leader and reach consensus in an unruly network[C]// Proceedings of the First Asia-Pacific Workshop on Networking. 2017: 1-7.
[62]	Sakic E, Kellerer W. Response time and availability study of RAFT consensus in distributed SDN control plane[J]. IEEE Transactions on Network and Service Management, 2017,15(1):304-318.
[63]	Giovanni Venâncio, Rogério C. Turchetti, Edson T. Camargo, Elias P. Duarte. VNF-Consensus: A virtual network function for maintaining a consistent distributed software-defined network control plane[J]. International Journal of Network Management, 2020: e2124.
[64]	Levin D, Wundsam A, Heller B, et al. Logically centralized? State distribution trade-offs in software defined networks[C]// Proceedings of the first workshop on Hot topics in software defined networks. 2012: 1-6.
[65]	Guo Z, Su M, Xu Y, et al. Improving the performance of load balancing in software-defined networks through load variance-based synchronization[J]. Computer Networks, 2014,68:95-109. doi: 10.1016/j.comnet.2013.12.004
[66]	C. Copeland et al.. Tangaroa: A Byzantine Fault Tolerant Raft[EB/OL].2014. http://www.scs.stanford.edu/14au-cs244b/labs/projects/copeland_zhong.pdf.
[67]	E. Sakic and W. Kellerer. Impact of Adaptive Consistency on Distributed SDN Applications: An Empirical Study[J]. IEEE Journal on Selected Areas in Communications, 2018,36(12):2702-2715. doi: 10.1109/JSAC.2018.2871309
[68]	He Li, Peng Li, Song Guo, Amiya Nayak. Byzantine-resilient secure software-defined networks with multiple controllers in cloud[J]. IEEE Transactions on Cloud Computing, 2014,2(4):436-447. doi: 10.1109/TCC.2014.2355227
[69]	El Defrawy K, Kaczmarek T. Byzantine fault tolerant software-defined networking (SDN) controllers[C]// 2016 IEEE 40th Annual Computer Software and Applications Conference (COMPSAC). IEEE, 2016,2:208-213.
[70]	P. M. Mohan, T. Truong-Huu and M. Gurusamy. Primary-Backup Controller Mapping for Byzantine Fault Tolerance in Software Defined Networks[C]. GLOBECOM 2017 - 2017 IEEE Global Communications Conference, Singapore, 2017: 1-7.
[71]	Sridharan V, Gurusamy M. Game-theoretic approach to malicious controller detection in software defined networks[C]// 2018 IEEE International Conference on Communications (ICC). IEEE, 2018: 1-6.
[72]	Bin Yuan, Hai Jin, Deqing Zou, Laurence Tianruo Yang, Shui Yu. A Practical Byzantine-Based Approach for Faulty Switch Tolerance in Software-Defined Networks[J]. IEEE Transactions on Network and Service Management, 2018,15(2):825-839. doi: 10.1109/TNSM.2018.2822668
[73]	Ermin Sakic, Nemanja Ðerić, Wolfgang Kellerer. MORPH: An Adaptive Framework for Efficient and Byzantine Fault-Tolerant SDN Control Plane[J]. IEEE Journal on Selected Areas in Communications, 2018,36(10):2158-2174. doi: 10.1109/JSAC.2018.2869938
[74]	Sakic E, Kellerer W. BFT protocols for heterogeneous resource allocations in distributed SDN control plane[C]// ICC 2019-2019 IEEE International Conference on Communications (ICC). IEEE, 2019: 1-7.
[75]	Sakic E, Deric N, Goshi E, et al. P4BFT: Hardware-Accelerated Byzantine-Resilient Network Control Plane[C]// 2019 IEEE Global Communications Conference (GLOBECOM). IEEE, 2019: 1-7.
[76]	Zhi Y, Yang L, Yu S, et al. BQSV: Protecting SDN Controller Cluster’s Network Topology View Based on Byzantine Quorum System with Verification Function[C]// International Symposium on Cyberspace Safety and Security. Springer, Cham, 2019: 73-88.
[77]	Moazzeni S, Khayyambashi M R, Movahhedinia N, et al. Improving the reliability of Byzantine fault-tolerant distributed software-defined networks[J]. International Journal of Communication Systems, 2020,33(9):e4372.
[78]	Tselios C, Politis I, Kotsopoulos S. Enhancing SDN security for IoT-related deployments through blockchain[C]// 2017 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). IEEE, 2017: 303-308.
[79]	Abou El Houda Z, Hafid A S, Khoukhi L. Cochain-SC: An intra-and inter-domain Ddos mitigation scheme based on blockchain using SDN and smart contract[J]. IEEE Access, 2019,7:98893-98907. doi: 10.1109/Access.6287639
[80]	Sharma P K, Singh S, Jeong Y S, et al. Distblocknet: A distributed blockchains-based secure sdn architecture for iot networks[J]. IEEE Communications Magazine, 2017,55(9):78-85.
[81]	Xue C, Xu N, Bo Y. Research on key technologies of software-defined network based on blockchain[C]// 2019 IEEE International Conference on Service-Oriented System Engineering (SOSE). IEEE, 2019: 239-2394.
[82]	Guan Z, Lyu H, Zheng H, et al. Distributed Audit System of SDN Controller Based on Blockchain[C]// International Conference on Smart Blockchain. Springer, Cham, 2019: 21-31.
[83]	FISCO BCOS [EB/OL]. http://fisco-bcos.org/zh/.