# Reaching Consensus with Byzantine Faulty Controllers in Software-Defined Networks

Authors: Chien-Fu Cheng; Jerry Chun-Wei Lin; Gautam Srivastava; Chu-Chiao Hsu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

The combination of the Internet of Things (IoT) and Cloud computing are both popular applications that are based on the Internet. However, the traditional networking structure can no longer support the transmission of the huge number of packets required by cloud computing and IoT. Therefore, a new-generation architecture, software-defined networking (SDN), came into being. The new-generation SDN can control routing through software, making flexible and convenient management a key feature of SDN. However, attacks and threats are prevalent in today’s networking environment. When an SDN controller encounters a hacker attack or virus infection, it will not function properly. Hence, we need to design a fault-tolerant mechanism for the above environment. In this paper, a fault-tolerant consensus protocol is proposed to improve the fault tolerance of SDNs with multiple controllers.


---

## Body

## 1. Introduction

With the flourishing enhancement of cloud computing and the Internet of Things (IoT), the scale of the Internet has grown at a very rapid rate [1–5]. This also makes the current Internet Protocol (IP) network architecture gradually unable to forward such a large amount of network traffic. This is because, in the current IP network infrastructure, the packets are forwarded through routers. The routing table of these routers is constructed by traditional routing protocols, which are preconfigured and embedded in the hardware by the vendor and run by a specific model. Network administrators do not have control over packets forwarding, thus resulting in poor utilization of network bandwidth [6]. Take multitenancy technology in data centers as an example, this cloud service is very convenient to users, but it is a heavy burden for the traditional IP network infrastructure [7]. The reason is that the routes to forwarding packets are calculated by dynamic routing protocols, and it is hard for the network administrator to identify which route the packets of a specific application have taken. Moreover, when customized adjustments of the network configurations are needed, the network administrator has to log in to each router or switch to manually change the settings via the Command-Line Interface (CLI). This method has a major drawback, that is, manual configuration of routers one by one involves a high risk of mistyping or giving inconsistent commands, which may cause failure of the entire network [8].


### 1.1. Software-Defined Networks (SDN)

When attempting to solve issues of increased utilization of network bandwidth using the classical IP network infrastructure, the software-defined networking- (SDN-) based architecture is proposed. SDN divides a network into a control plane and a data plane. In this network, the controller in the control plane is responsible for the control of the network, while switches in the data plane are responsible for packets forwarding. The controller can communicate with the switches in the data plane via the southbound interface. The southbound interface in SDN is better standardized. In the present, the OpenFlow interface is the most influential southbound interface [9]. On the other hand, applications can communicate with the controller via the northbound interface, but so far, this interface has not been standardized. Common northbound interfaces include REST [10] and SNMP [11].Simply put, SDN is a concept of networking architecture. It does not specify the use of any specific technology. The core ideas are to separate control from forwarding and to use software programs to control the network and flexibly manage the network [12]. OpenFlow is a concrete protocol that can be implemented as the southbound interface in SDN. SDN has the following characteristics: Applications can flexibly control network traffic, optimize load balancing according to user needs, and make the use of bandwidth more adequate. Moreover, SDN considers time and energy saving to network management according to user needs. On the other hand, SDN combined with the virtualization technology can be used to enable different services in data center, thus sharing network equipment and reducing equipment investment.Nowadays, Open Networking Foundation (ONF) is the most influential organization for SDN. It was founded in 2011 by Google, Facebook, and Microsoft [13]. Unlike other standards organizations formed by manufacturers of network equipment, ONF was created by “users” of network equipment. The mission of ONF is to promote OpenFlow protocol as the only standard for the southbound interface [14]. Established in 2013, OpenDaylight (ODL) is another well-known organization for SDN. It was initiated by 18 well-known IT companies [15]. The objective of ODL is to create an open SDN platform. As shown in Figure 1, this platform comprises three major layers. The top layer consists of the northbound interface and built-in applications and services. The middle layer is formed by network services and platform services. The bottom layer is the southbound interface. The northbound interface supports REST APIs. The southbound interface supports OpenFlow protocols and many other protocols, such as SNMP, LISP, XMPP, PCEP, OF-Config, Net-Config, BGP-LS, and even private interfaces defined by vendors [16].Figure 1
OpenDaylight platform [16].However, attacks and threats are prevalent in today’s networking environment [17–19]. As for security, a number of scholars have investigated the security mechanisms of SDN in recent years. The security issues that have been discussed in the SDN literature include access control [20], authentication [21], and nonrepudiation [22]. For access control, Nayak et al. [20] constructed a system called Resonance in an OpenFlow-based network. This system executes dynamic access controls based on flow-level messages and real-time alerts. For authentication, Porras et al. [21] designed for the NOXZ OpenFlow controller a software program called FortNOX to support role-based authorization as well as detection and negotiation of conflicting flow-entries. For nonrepudiation, Yao et al. [22] proposed a source address validation mechanism, called the Virtual Source Address Validation Edge (VAVE), for the OpenFlow/NOX network architecture. VAVE has three major features, including supporting on-demand filtering, rapidly reacting to route changes, and avoiding unnecessary checks to reduce the load on the router.The Virtualizing Network Function (NFV) instead uses software such as firewall, router, load balancer, and customer’s premise equipment (CME) to implement the network functions of physical devices. The NFV undermines the idea that the network features should exist on a particular hardware device. This is because, after virtualization of the network function, it has excellent elastic configuration features, allowing the deployment effectiveness of network services to be speeded up and costs of buying dedicated hardware reduced. Many great personalized services can be introduced easily with the complementarity of SDN and NFV.


### 1.2. Distributed Control Architecture

The controller of SDN is responsible for managing network resources and planning flow-entries according to the demand of upper-layer applications for the bottom-layer switches. Figure2 illustrates a centralized control architecture and a distributed control architecture. The earlier SDN architecture is based on centralized control, that is, the entire network is managed by only one controller [23]. However, the single point of failure (SPOF) is likely to happen when the SDN is managed by a single controller. Moreover, the scalability problem is also an important issue if the network is huge. It would be hard to ensure the stability and efficiency of the network. Therefore, subsequent scholars proposed to use multiple controllers to collaboratively deal with the control tasks [24].Figure 2
Illustrations of control architecture. (a) The centralized architecture. (b) The distributed architecture.
(a)(b)For example, Kyung et al. [25] propose the Load Distribution (LD) algorithm to avoid the overload problem of the controllers. The basic concept of the LD algorithm is that when the loading of the default controller reaches the threshold, the tasks it has received will be transferred to other controllers. Wang et al. [26] suggested to segment a large network into several domains and then use multiple controllers to, respectively, manage the domains to reduce the loading of the controllers. Wang et al. pointed out that finding an optimal number of controllers for a multidomain SDN environment is an NP-hard problem. For this problem, they proposed an approximation algorithm called the Greedy Subgraph Cover Problem (GSGCP), which is capable of placing a smaller number of controllers to manage a multidomain SDN. In addition, Yannan et al. [27] suggested that considering the expected percentage of control path loss in the problem of placing controllers can help effectively increase the reliability of SDN. They call the problem as the Reliability-aware Controller Placement (RCP) problem. In their study, the authors also show that the RCP problem is also an NP-hard problem.


### 1.3. Fault-Tolerant Mechanism

As mentioned above, a distributed control structure involving the collaboration of multiple controllers can effectively enhance the performance and stability of SDNs. However, attacks and threats are prevalent in today’s networking environment. SDN controllers may not work normally when it is encountered by hackers or virus infection. Generally, faults of SDN controllers can be classified into crash fault [28], omission fault [29], and Byzantine fault [30–32]. A crash fault means that the controller will stop functioning properly. The omission fault of a controller occurs when messages are fully or partially omitted by the controller. Unlike the crash fault or omission fault, a Byzantine fault may cause a controller to send wrong messages or conspire with other faulty devices to interfere with the operation of nonfaulty controllers, thereby delivering incorrect computing results. These malicious behaviours include, for example, sending an incorrect flow-entry to the switch to prevent packets from being delivered to the correct destination and sending a specific flow-entry to the switch to enable the attacker to receive a copy of all the packets delivered to or sent from a particular host (i.e., eavesdropping packets).To provide a reliable SDN with multiple-controller architecture, we need a mechanism that ensures the correctness of the computing results even if any controller has a fault or is under attack. That is, we have to design a protocol that can take advantage of the distributed system to let controllers work together to resist attacks from Byzantine controllers. Therefore, even in the presence of a faulty controller, the system will still deliver correct computing results. In a distributed system, we can establish the system’s fault tolerance capability by solving the consensus problem. Common applications of the consensus protocol include the leader election problem in the P2P network [33], duplicated files storage coordination problem [34], cruise control problem in the car platoon [35], and clock synchronization [36, 37]. The requirements of the consensus protocol are shown in Table 1 [38]. The main contributions of this paper are summarized as follows: (1) We design a consensus protocol for SDN with multiple-controller architecture. (2) The proposed consensus protocol can tolerate the most damaging type of faults (i.e., Byzantine fault). (3) By solving the consensus problem in SDN with multiple-controller architecture, we can create a highly reliable networking environment.Table 1
The requirements of the consensus protocol.
ConsensusEach correct processor should compute a common value.ValidityIf the initial value of each processors isvi, then each correct processor should obtain the value vi.The remainder of this paper is organized as follows. “Preliminaries” describes the preliminary. “Concept and Approach” describes the protocol for solving the consensus problem. “An Execution Example” shows an example of solving the consensus problem. Finally, conclusions are drawn in “Conclusion.”


## 1.1. Software-Defined Networks (SDN)

When attempting to solve issues of increased utilization of network bandwidth using the classical IP network infrastructure, the software-defined networking- (SDN-) based architecture is proposed. SDN divides a network into a control plane and a data plane. In this network, the controller in the control plane is responsible for the control of the network, while switches in the data plane are responsible for packets forwarding. The controller can communicate with the switches in the data plane via the southbound interface. The southbound interface in SDN is better standardized. In the present, the OpenFlow interface is the most influential southbound interface [9]. On the other hand, applications can communicate with the controller via the northbound interface, but so far, this interface has not been standardized. Common northbound interfaces include REST [10] and SNMP [11].Simply put, SDN is a concept of networking architecture. It does not specify the use of any specific technology. The core ideas are to separate control from forwarding and to use software programs to control the network and flexibly manage the network [12]. OpenFlow is a concrete protocol that can be implemented as the southbound interface in SDN. SDN has the following characteristics: Applications can flexibly control network traffic, optimize load balancing according to user needs, and make the use of bandwidth more adequate. Moreover, SDN considers time and energy saving to network management according to user needs. On the other hand, SDN combined with the virtualization technology can be used to enable different services in data center, thus sharing network equipment and reducing equipment investment.Nowadays, Open Networking Foundation (ONF) is the most influential organization for SDN. It was founded in 2011 by Google, Facebook, and Microsoft [13]. Unlike other standards organizations formed by manufacturers of network equipment, ONF was created by “users” of network equipment. The mission of ONF is to promote OpenFlow protocol as the only standard for the southbound interface [14]. Established in 2013, OpenDaylight (ODL) is another well-known organization for SDN. It was initiated by 18 well-known IT companies [15]. The objective of ODL is to create an open SDN platform. As shown in Figure 1, this platform comprises three major layers. The top layer consists of the northbound interface and built-in applications and services. The middle layer is formed by network services and platform services. The bottom layer is the southbound interface. The northbound interface supports REST APIs. The southbound interface supports OpenFlow protocols and many other protocols, such as SNMP, LISP, XMPP, PCEP, OF-Config, Net-Config, BGP-LS, and even private interfaces defined by vendors [16].Figure 1
OpenDaylight platform [16].However, attacks and threats are prevalent in today’s networking environment [17–19]. As for security, a number of scholars have investigated the security mechanisms of SDN in recent years. The security issues that have been discussed in the SDN literature include access control [20], authentication [21], and nonrepudiation [22]. For access control, Nayak et al. [20] constructed a system called Resonance in an OpenFlow-based network. This system executes dynamic access controls based on flow-level messages and real-time alerts. For authentication, Porras et al. [21] designed for the NOXZ OpenFlow controller a software program called FortNOX to support role-based authorization as well as detection and negotiation of conflicting flow-entries. For nonrepudiation, Yao et al. [22] proposed a source address validation mechanism, called the Virtual Source Address Validation Edge (VAVE), for the OpenFlow/NOX network architecture. VAVE has three major features, including supporting on-demand filtering, rapidly reacting to route changes, and avoiding unnecessary checks to reduce the load on the router.The Virtualizing Network Function (NFV) instead uses software such as firewall, router, load balancer, and customer’s premise equipment (CME) to implement the network functions of physical devices. The NFV undermines the idea that the network features should exist on a particular hardware device. This is because, after virtualization of the network function, it has excellent elastic configuration features, allowing the deployment effectiveness of network services to be speeded up and costs of buying dedicated hardware reduced. Many great personalized services can be introduced easily with the complementarity of SDN and NFV.


## 1.2. Distributed Control Architecture

The controller of SDN is responsible for managing network resources and planning flow-entries according to the demand of upper-layer applications for the bottom-layer switches. Figure2 illustrates a centralized control architecture and a distributed control architecture. The earlier SDN architecture is based on centralized control, that is, the entire network is managed by only one controller [23]. However, the single point of failure (SPOF) is likely to happen when the SDN is managed by a single controller. Moreover, the scalability problem is also an important issue if the network is huge. It would be hard to ensure the stability and efficiency of the network. Therefore, subsequent scholars proposed to use multiple controllers to collaboratively deal with the control tasks [24].Figure 2
Illustrations of control architecture. (a) The centralized architecture. (b) The distributed architecture.
(a)(b)For example, Kyung et al. [25] propose the Load Distribution (LD) algorithm to avoid the overload problem of the controllers. The basic concept of the LD algorithm is that when the loading of the default controller reaches the threshold, the tasks it has received will be transferred to other controllers. Wang et al. [26] suggested to segment a large network into several domains and then use multiple controllers to, respectively, manage the domains to reduce the loading of the controllers. Wang et al. pointed out that finding an optimal number of controllers for a multidomain SDN environment is an NP-hard problem. For this problem, they proposed an approximation algorithm called the Greedy Subgraph Cover Problem (GSGCP), which is capable of placing a smaller number of controllers to manage a multidomain SDN. In addition, Yannan et al. [27] suggested that considering the expected percentage of control path loss in the problem of placing controllers can help effectively increase the reliability of SDN. They call the problem as the Reliability-aware Controller Placement (RCP) problem. In their study, the authors also show that the RCP problem is also an NP-hard problem.


## 1.3. Fault-Tolerant Mechanism

As mentioned above, a distributed control structure involving the collaboration of multiple controllers can effectively enhance the performance and stability of SDNs. However, attacks and threats are prevalent in today’s networking environment. SDN controllers may not work normally when it is encountered by hackers or virus infection. Generally, faults of SDN controllers can be classified into crash fault [28], omission fault [29], and Byzantine fault [30–32]. A crash fault means that the controller will stop functioning properly. The omission fault of a controller occurs when messages are fully or partially omitted by the controller. Unlike the crash fault or omission fault, a Byzantine fault may cause a controller to send wrong messages or conspire with other faulty devices to interfere with the operation of nonfaulty controllers, thereby delivering incorrect computing results. These malicious behaviours include, for example, sending an incorrect flow-entry to the switch to prevent packets from being delivered to the correct destination and sending a specific flow-entry to the switch to enable the attacker to receive a copy of all the packets delivered to or sent from a particular host (i.e., eavesdropping packets).To provide a reliable SDN with multiple-controller architecture, we need a mechanism that ensures the correctness of the computing results even if any controller has a fault or is under attack. That is, we have to design a protocol that can take advantage of the distributed system to let controllers work together to resist attacks from Byzantine controllers. Therefore, even in the presence of a faulty controller, the system will still deliver correct computing results. In a distributed system, we can establish the system’s fault tolerance capability by solving the consensus problem. Common applications of the consensus protocol include the leader election problem in the P2P network [33], duplicated files storage coordination problem [34], cruise control problem in the car platoon [35], and clock synchronization [36, 37]. The requirements of the consensus protocol are shown in Table 1 [38]. The main contributions of this paper are summarized as follows: (1) We design a consensus protocol for SDN with multiple-controller architecture. (2) The proposed consensus protocol can tolerate the most damaging type of faults (i.e., Byzantine fault). (3) By solving the consensus problem in SDN with multiple-controller architecture, we can create a highly reliable networking environment.Table 1
The requirements of the consensus protocol.
ConsensusEach correct processor should compute a common value.ValidityIf the initial value of each processors isvi, then each correct processor should obtain the value vi.The remainder of this paper is organized as follows. “Preliminaries” describes the preliminary. “Concept and Approach” describes the protocol for solving the consensus problem. “An Execution Example” shows an example of solving the consensus problem. Finally, conclusions are drawn in “Conclusion.”


## 2. Preliminaries

In this study, we assume that the underlying SDN is synchronous, and the failure type of faulty controllers includes Byzantine fault and dormant fault. Besides, we must reasonably limit the number of faulty controllers to ensure the system can work properly. The number of faulty controllers that can be tolerated by the system is subject to the number of controllers in the network. The following are environmental assumptions:(i)
The underlying network is synchronous(ii)
LetN be the set of controllers in the network, where N=ni∣1≤i≤n,n=N(iii)
Each controller has an identifier and can be identified uniquely in the network(iv)
The failure types of the fallible controllers are crash, omission, and Byzantine fault(v)
Each controller has an initial value, and the domain rangeD=0,1(vi)
The maximum number of faulty controllers allowed isn≥3fb+fd+1, where fb is the number of Byzantine controllers and fd is the number of dormant (i.e., crash fault and omission fault) controllers(vii)
A nonfaulty controller does not know the fault status of other controllers.In this paper, a consensus protocol is designed for SDNs. The proposed consensus protocol can take advantage of the distributed system to let controllers work together to resist attacks from Byzantine controllers. That is, all of the nonfaulty controllers within the networks are able to compute an identical consensus value by using the proposed consensus protocol. We will present the problem to address using the following equations: We can clearly express the objective function as in Equation (1), where we say that Cni is the consensus value computed using ni. Equation (2) restricts each controller’s initial value and says that it comes from the range {0, 1}. Equation (3) constrains the number of allowed faulty controllers in the SDN (we will explain how this quantity limit is derived in “Concept and Approach”).
(1)Cni=Cnj,∀non‐faultycontrollerni,nj∈Nandi≠j,subject to
(2)Dni∈0,1,∀ni∈N,(3)n≥3fb+fd+1.


## 3. Concept and Approach

Here, we identify our concepts as well as approach for Consensus Protocol for SDN (CPSDN). First, all controllers are able to select the initial value using domain range D=0,1. As the next step, each controller is examined and allowed to exchange their corresponding initial value with all of the other controllers. After message exchange finishes, all of the controllers compute their own consensus value making use of the collected messages. In other words, there are exactly 2 phases in (CPSDN) which are known as Msg_Exchanging as well as Cons_Making phase, respectively. Next, we give descriptions for the two phases introduced as follows.


### 3.1. Msg_Exchanging Phase

To start, each and every controller sends its initial value to every other controller in the SDN. Later, the controller will rely on adequate collaboration (i.e., exchanging the collected initial values from other controllers) to overcome the faults and attacks from a few controllers. Hence, the first work is to compute the number of rounds required in the message exchanging. According to Siu et al. [39], if a message is unauthenticated in the network with m Byzantine processors and b dormant processors, there must be at least n−1/3+2m+b+1 processors, and the minimum number of rounds of message exchange is n−1/3+1. In the proposed protocol, only the controller is involved. Therefore, the constraint of our system model is n>n−1/3+2fb+fd, and the number of rounds of message exchange is at most fb+1(fb=n−1/3,fb is the maximum number of Byzantine controllers n=∣N∣).Next, we will explain how the controller stores the collected messages. As mentioned above, the number of rounds of message exchanging isfb+1. Besides, in each and every round, the controller will transmit the messages collected in the previous round to all the other controllers in the network. This means the number of messages will grow at a very rapid speed (exponentially). Therefore, using an appropriate data structure to store the collected messages is very important. Bar-Noy et al. [40] pointed out that the tree structure is very suitable for storing data collected by this exchange method. In this paper, we will also store messages collected in the message exchange process in a tree structure, called the SDN-tree. Figure 3 shows a clear example of what is known as a 2-level SDN-tree. The SDN-tree as given can be organized and labelled in the following manner: Each and every vertex of a given SDN-tree is first labelled to be a nonrepeating sequence α of the controller identifies. To avoid being strongly influenced by well-known Byzantine controllers, no vertices are kept with repeating names within an SDN-tree. The SDN-tree root is then labelled clearly as “root” as well as every parent of a given vertex is then labelled clearly as the sequence αni (i.e., α concatenates ni, where ni is a single controller name) is labelled α, and the value of vertex of SDN-tree is a value. Figure 3 shows an example of that the parent of the vertex n2n1 (i.e., n2 concatenates n1) is the vertex n2. The value stored in the vertex n2n1 is “1.”Figure 3
An example of SDN-tree.The checksum, as well as the time-out mechanism, may be able to detect messages that are contaminated by any dormant controllers. As such, in our proposed protocol, we show that those contaminated messages are clearly marked by “Ω0.” Here, the value “Ω0” is to be used only for the marking of contaminated messages and only from dormant controllers. So, in the upcoming rounds of the message exchange as defined earlier, any and all messages collected from previous rounds will automatically be exchanged. Then, if and only if the message that is received is one of Ωj, Ωj+1 instead then Ωj will then be clearly stored so as to represent the contaminated value which came from the previous round. We note here that the main purpose of +1 noted earlier is to be able to show the number of rounds for message exchange that have already passed. This very simple procedure can then aid us to be able to determine if and only if the message exchange has a contaminated value of the preceding controller or even a contaminated value for the current controller.


### 3.2. Cons_Making Phase

Here, we describe what is known as theCons_Making phase. This is known as where a consensus value can be computed. So, to describe the Cons_Making phase, we start by noting that the function called voteSDN is first used for the computation of consensus value starting at the root in SDN-tree. We work here from the furthest leaves all the way to root. The function voteSDN contains 5 conditions that can be presented in the following manner: If and only if vertex α can be defined as a leaf, then and only then there will be only 1 value within vertex α. Therefore, majority of the value then can be defined as value of vertex α (this is Condition 1); Condition 2 can be defined as when we used to be able to remove any influence from the well-known Byzantine controllers; Condition 3 then will be used for the removal of any influence that may arise from the dormant controllers; Condition 4 then will only be used if and only if we get a majority value. If and only if majority value exists, then and only then the output for default value ⊥ exists, where we can say that ⊥∉V (Condition 5). Conditions 1, 4, and 5 bear similarities to the well-known majority voting convention [32]. The function voteSDN can be clearly seen in Algorithm 1.Algorithm 1: The VoteSDN function.
voteSDN Function/ // for each controller ni∈N1.Begin2.if vertex σ is a leaf then --- (1)3.  outputvalσ4.else5.if #Ω0σ≥3·fb−i+1+n−1mod3 ---- (2)6.   output the value ofσ7.  if majchildσ=Ωi, where 1≤i≤n−1/3−1 ---- (3)8.   outputΩi−19.if majchildσ=v ----- (4)10.   outputv11.if majchildσ=null -----(5)12.   output ⊥13.End#.valσ is the value of vertex σ. Function majchildσ is used to find out the majority value in vertex σ’s child nodes.


### 3.3. The Pseudo Code ofCPSDN

TheCPSDN protocol pseudocode is clearly given in Algorithm 2. We define the involved functions in the protocol as follows:
(i)
crtαp,v: create vertex αp, set valαp=v(ii)
dormtnj: check controller nj is dormant controller(iii)
sendMSG,nj,msg,nk: send MSG message with value msg as proposed by controller nj to nk(iv)
packi,msg: structure of level i of SDN-tree, pack level i of SDN-tree with message msg(v)
unpacki,msg: structure of level i of SDN-tree, unpack message msg(vi)
delrptSDN−tree: delete vertices with duplicate signs in SDN-tree(vii)
voteSDNSDN−tree: input leaves of SDN-tree and compute consensus value with accordance with tree structure of SDN-tree.Algorithm 2: The proposed CPSDN protocol (for each controller).
/∗ phase 1: Msg_Exchanging∗/1.crt(root,vi);2.for i=1 to fb+1do3.packi−1,msg;4.for nj∈Ndo5.sendMSG,ni,msg,nj;7.wait until (time-out interval)6.end8.for nj∈Ndo9.ifdormtnj=true then10.packagei−1,m;11.for α∈mdo12.v=Ω0;13.crtαnj,v;14.end15.else if receive MSG,nj,msg from nj then16.unpacki−1,msg;17.for α∈msgdo18.if v=Ωi then19.v=Ωi+1;20.else21.v=valα;22.crtαnj,v;23.end24.delrptSDN−tree;25.end/∗ Phase 2: Cons_Making∗/26.if i=fb+1 do27.   consensusvalue=voteSDNSDN−tree;28.return consensus value;


## 3.1. Msg_Exchanging Phase

To start, each and every controller sends its initial value to every other controller in the SDN. Later, the controller will rely on adequate collaboration (i.e., exchanging the collected initial values from other controllers) to overcome the faults and attacks from a few controllers. Hence, the first work is to compute the number of rounds required in the message exchanging. According to Siu et al. [39], if a message is unauthenticated in the network with m Byzantine processors and b dormant processors, there must be at least n−1/3+2m+b+1 processors, and the minimum number of rounds of message exchange is n−1/3+1. In the proposed protocol, only the controller is involved. Therefore, the constraint of our system model is n>n−1/3+2fb+fd, and the number of rounds of message exchange is at most fb+1(fb=n−1/3,fb is the maximum number of Byzantine controllers n=∣N∣).Next, we will explain how the controller stores the collected messages. As mentioned above, the number of rounds of message exchanging isfb+1. Besides, in each and every round, the controller will transmit the messages collected in the previous round to all the other controllers in the network. This means the number of messages will grow at a very rapid speed (exponentially). Therefore, using an appropriate data structure to store the collected messages is very important. Bar-Noy et al. [40] pointed out that the tree structure is very suitable for storing data collected by this exchange method. In this paper, we will also store messages collected in the message exchange process in a tree structure, called the SDN-tree. Figure 3 shows a clear example of what is known as a 2-level SDN-tree. The SDN-tree as given can be organized and labelled in the following manner: Each and every vertex of a given SDN-tree is first labelled to be a nonrepeating sequence α of the controller identifies. To avoid being strongly influenced by well-known Byzantine controllers, no vertices are kept with repeating names within an SDN-tree. The SDN-tree root is then labelled clearly as “root” as well as every parent of a given vertex is then labelled clearly as the sequence αni (i.e., α concatenates ni, where ni is a single controller name) is labelled α, and the value of vertex of SDN-tree is a value. Figure 3 shows an example of that the parent of the vertex n2n1 (i.e., n2 concatenates n1) is the vertex n2. The value stored in the vertex n2n1 is “1.”Figure 3
An example of SDN-tree.The checksum, as well as the time-out mechanism, may be able to detect messages that are contaminated by any dormant controllers. As such, in our proposed protocol, we show that those contaminated messages are clearly marked by “Ω0.” Here, the value “Ω0” is to be used only for the marking of contaminated messages and only from dormant controllers. So, in the upcoming rounds of the message exchange as defined earlier, any and all messages collected from previous rounds will automatically be exchanged. Then, if and only if the message that is received is one of Ωj, Ωj+1 instead then Ωj will then be clearly stored so as to represent the contaminated value which came from the previous round. We note here that the main purpose of +1 noted earlier is to be able to show the number of rounds for message exchange that have already passed. This very simple procedure can then aid us to be able to determine if and only if the message exchange has a contaminated value of the preceding controller or even a contaminated value for the current controller.


## 3.2. Cons_Making Phase

Here, we describe what is known as theCons_Making phase. This is known as where a consensus value can be computed. So, to describe the Cons_Making phase, we start by noting that the function called voteSDN is first used for the computation of consensus value starting at the root in SDN-tree. We work here from the furthest leaves all the way to root. The function voteSDN contains 5 conditions that can be presented in the following manner: If and only if vertex α can be defined as a leaf, then and only then there will be only 1 value within vertex α. Therefore, majority of the value then can be defined as value of vertex α (this is Condition 1); Condition 2 can be defined as when we used to be able to remove any influence from the well-known Byzantine controllers; Condition 3 then will be used for the removal of any influence that may arise from the dormant controllers; Condition 4 then will only be used if and only if we get a majority value. If and only if majority value exists, then and only then the output for default value ⊥ exists, where we can say that ⊥∉V (Condition 5). Conditions 1, 4, and 5 bear similarities to the well-known majority voting convention [32]. The function voteSDN can be clearly seen in Algorithm 1.Algorithm 1: The VoteSDN function.
voteSDN Function/ // for each controller ni∈N1.Begin2.if vertex σ is a leaf then --- (1)3.  outputvalσ4.else5.if #Ω0σ≥3·fb−i+1+n−1mod3 ---- (2)6.   output the value ofσ7.  if majchildσ=Ωi, where 1≤i≤n−1/3−1 ---- (3)8.   outputΩi−19.if majchildσ=v ----- (4)10.   outputv11.if majchildσ=null -----(5)12.   output ⊥13.End#.valσ is the value of vertex σ. Function majchildσ is used to find out the majority value in vertex σ’s child nodes.


## 3.3. The Pseudo Code ofCPSDN

TheCPSDN protocol pseudocode is clearly given in Algorithm 2. We define the involved functions in the protocol as follows:
(i)
crtαp,v: create vertex αp, set valαp=v(ii)
dormtnj: check controller nj is dormant controller(iii)
sendMSG,nj,msg,nk: send MSG message with value msg as proposed by controller nj to nk(iv)
packi,msg: structure of level i of SDN-tree, pack level i of SDN-tree with message msg(v)
unpacki,msg: structure of level i of SDN-tree, unpack message msg(vi)
delrptSDN−tree: delete vertices with duplicate signs in SDN-tree(vii)
voteSDNSDN−tree: input leaves of SDN-tree and compute consensus value with accordance with tree structure of SDN-tree.Algorithm 2: The proposed CPSDN protocol (for each controller).
/∗ phase 1: Msg_Exchanging∗/1.crt(root,vi);2.for i=1 to fb+1do3.packi−1,msg;4.for nj∈Ndo5.sendMSG,ni,msg,nj;7.wait until (time-out interval)6.end8.for nj∈Ndo9.ifdormtnj=true then10.packagei−1,m;11.for α∈mdo12.v=Ω0;13.crtαnj,v;14.end15.else if receive MSG,nj,msg from nj then16.unpacki−1,msg;17.for α∈msgdo18.if v=Ωi then19.v=Ωi+1;20.else21.v=valα;22.crtαnj,v;23.end24.delrptSDN−tree;25.end/∗ Phase 2: Cons_Making∗/26.if i=fb+1 do27.   consensusvalue=voteSDNSDN−tree;28.return consensus value;


## 4. An Execution Example

The flowchart of the proposedCPSDN is shown in Figure 4. An example in this section will be presented that is able to show via demonstrating the manner in which CPSDN helps controllers achieve consensus. We assume here that the network consists of five controllers, which includes N=n1,n2,n3,n4,n5. Among these controllers, controller n3 is a Byzantine controller, and controller n5 is a dormant controller. Table 2 shows the initial value of each nonfaulty controller.Figure 4
The flow chart of the proposedCPSDN protocol.Table 2
The initial value of each nonfaulty controller.
n1n2n4vi010In the first round of theMsg_Exchanging phase, each controller will send its initial value to all other controllers in the network. When nonfaulty controller receives the initial values from other controllers, it will store the received initial values in level 1 of its SDN-tree. Controller n5 is a dormant controller. Under the operation of error checking codes and the time-out mechanism, it will be detected (as shown in Figure 5(a)). On the other hand, due to the controller n3 is a Byzantine faulty controller, it may send inconsistent initial value to other controllers in the network. As shown in Figure 5(a), some controllers receive 0 as the initial value of Controller n3, and some receive 1.Figure 5
An example of executionCPSDN. (a) The SDN-trees of nonfaulty controllers n1, n2, and n4 after the 1st of Msg_Exchanging phase. (b) The SDN-trees of nonfaulty controllers n1, n2, and n4 after the 2nd of Msg_Exchanging phase.
(a)(b)Next, the controllers enter the second round of theMsg_Exchanging phase. In the second round, controllers will exchange the messages collected in the first round with each other. Byzantine controller n3 is likely to continue interfering (i.e., sends arbitrary values to nonfaulty controllers). On the other hand, when forwarding the value received from a dormant controller, nonfaulty controllers will mark the value by Ωi. The SDN-trees of nonfaulty controllers n1, n2, and n4 after the 2nd of Msg_Exchanging phase are shown in Figure 5(b).In this example, the number of rounds required in theMsg_Exchanging phase is 2 (fb+1=n−1/3+1=2). Hence, after two rounds of message exchange, each nonfaulty controller will enter the Cons_Making phase. In the Cons_Making phase, each nonfaulty controller will use the voteSDN function to compute the consensus value. In this example, the consensus value computed by the nonfaulty controllers is “⊥” (voteSDNroot=voteSDN0,1,1,0,Ω0=⊥). The process of computing the consensus value by voteSDN function is shown in Table 3.Table 3
The process of computing the consensus value byvoteSDN function.
voteSDNn1=voteSDNn1n2,n1n3,n1n4,n1n5(i)voteSDNn1=voteSDN0,0,0,Ω0=0✓voteSDNn2=voteSDNn2n1,n2n3,n2n4,n2n5(ii)voteSDNn2=voteSDN1,1,1,Ω0=1✓voteSDNn3=voteSDNn3n1,n3n2,n3n4,n3n5(iii)voteSDNn3=voteSDN0,1,1,Ω0=1✓voteSDNn4=voteSDNn4n1,n4n2,n4n3,n4n5(iv)voteSDNn4=voteSDN0,0,1,Ω0=0✓voteSDNn5=voteSDNn5n1,n5n2,n5n3,n5n4(v)voteSDNn5=voteSDNΩ1,Ω1,1,Ω1=Ω0


## 5. Conclusion

A distributed control structure involving the collaboration of multiple controllers can effectively enhance the performance and stability of SDNs. However, attacks and threats are prevalent in today’s networking environment. SDN controllers may not work normally when it is encountered by hackers or virus infection. To provide a reliable SDN with a distributed control architecture, we need a mechanism that ensures the correctness of the computing results even if any controller has a fault or is under attack. Hence, we discussed the fault-tolerant consensus problem in the SDN with distributed control architecture. With the proposedCPSDN protocol, if the number of controllers n is greater than n−1/3+2fb+fd, we can ensure that the nonfaulty controller can reach the common consensus value after fb+1 rounds of message exchange. For some applications that require very high reliability, reaching a consensus is not enough. Hence, we must consider another related problem, called the fault diagnosis problem. This will be the direction of our future research in SDNs.



---

*Source: 6662175-2021-04-12.xml*