# MPResiSDN: Multipath Resilient Routing Scheme for SDN-Enabled Smart Cities Networks
## 4 MPResiSDN System
### System Algorithm  
In this section, the MPResiSDN algorithm is described. the algorithm has seven functions: TopologyDiscovery(), ChallengeDetector(), DiversePaths(\(k\), \(src\), \(dst\), \(G\)), FindSwitches(\(path\)), DetermineInOutPorts(\(sw\), \(path\)), ReversePath(\(path\)), and GenerateRule(\(sw\), \(in\), \(out\)). The pseudocode of the MPResiSDN algorithm is illustrated in Algorithm 1. Initially, TopologyDiscovery() determines the network topology. The function results in a set of nodes \(N\), links \(L\), and a graph \(G=(N,L)\). The ChallengeDetector() function reads the sensory information from the lightning, humidity, and temperature sensors. It analyses the results to detect the existence of natural challenges and specifies the type of challenge. Most importantly, this function specifies a suitable value for the number of alternative paths to be used, (\(k\)). The DiversePaths(\(k\), \(src\), \(dst\), \(G\)) function takes the specified value \(k\) and the determined topology graph \(G\) to compute \(k\) diverse paths between a source node \(src\) and a destination sink \(dst\). The FindSwitches(\(path\)) function takes a path as input and determines all connected switches. The DetermineInOutPorts(\(sw\), \(path\)) function takes a switch ID and the path it belongs to as inputs. Then, it determines the connected input and output ports for each switch in the path. The ReversePath(\(path\)) function takes a \(path\) as input and determines the reverse path associated with it. Finally, the GenerateRule(\(sw\), \(in\), \(out\)) function generates the SDN rules to be pushed to the OpenFlow switches. It takes a switch ID along with its associated input and output ports as inputs. Then it produces an SDN rule to be used later to fill the switch's routing table. The code flow for the MPResiSDN algorithm is described here. At the initialization level, the network topology \(G\) is obtained by the TopologyDiscovery() function and passed to the DiversePaths(\(k\), \(src\), \(dst\), \(G\)) function. The parameter \(k\) is determined by the ChallengeDetector() function and passed to the DiversePaths(\(k\), \(src\), \(dst\), \(G\)) function. Then, the DiversePaths(\(k\), \(src\), \(dst\), \(G\)) function immediately generates the \(k\) diverse paths to be used. Subsequently, the SDN rules list is initialized, and the process begins of generating the SDN rules to enable the system to utilize the determined \(k\) paths. At first, the algorithm takes each path in turn and applies several processing steps. For each path, the algorithm determines all switches on the path using the FindSwitches(\(path\)) function. Then, for each found switch, the input and output ports are determined using the DetermineInOutPorts(\(sw\), \(path\)) function and the associated SDN rule is generated using the GenerateRule(\(sw\), \(in\), \(out\)) function. Eventually, the SDN rule is appended to the SDN rules list. SDN rules are created to handle the acknowledgment packets. The ReversePath(\(path\)) function is used to generate the reversed path of the original forward path. Then, the same  
Figure 6: SDN OpenFlow flow entry format. processing steps that were applied to the forward path are applied to the reversed path. The generated rules list is utilized to fill the routing tables of all switches belonging to the path. Note that all switches use the resulting routing tables until an event happens, e.g., a new challenge is detected, or a link or a node is damaged. When any of these events happens, the SDN controller reruns the algorithm and updates the routing tables of all switches. To consider the algorithmic complexity of our algorithm, we focus on expensive functions and loops. Hence, to compute \(k\) shortest paths, our algorithm uses the Floyd-Warshall algorithm to find diverse paths, which incur \(O(n^{2})\) with a network of size \(n\) nodes [57].