# SDN-Based Routing for Backhauling in Ultra-Dense Networks
## 6 Proposed Approach
### SDN-Based Routing--OpenFlow Approach  
As already stated the proposed routing algorithm runs at the SDN controller that supervises the FDs behavior by means of OpenFlow protocol. When a change occurs in the network, the SDN controller recomputes traffic-routes following the steps described before, and sends a MODIFY-STATE command to FDs affected by changes. FDs change corresponding entries in the forwarding tables. In particular, three types of messages are supported: _controller-to-switch, asynchronous_ and _symmetric_. _Controller-to-switch messages_ are initiated by the SDN controller and used to manage and observe the FDs' state. Hence, these messages are used for feature/status requests and configurations. For example, the SDN controller periodically performs traffic monitoring (READ-STATE message) to collect links' statistics, in order to react in real time. SDN controller sends a flow-status request to FDs, which answer with a flow-status reply that contains _flow-duration_ and _byte-count_, thus, to evaluate the link throughput. _Asynchronous messages_ are initiated by FDs to update the SDN controller of events and changes (e.g., a new flow, status change, etc.). _Symmetric messages_ are initiated by either the FD or the controller and sent without solicitation, such as HELLO or ERROR messages. For example, if a link goes down the FD sends an ERROR message to the controller that selects new paths that do not involve the failed link. Figure 3 reports the message-flow for updating the network knowledge and forwarding tables in two cases: (a) SDN controller initiated (status update), (b) FD-initiated (link failure). Consequently, an SDN can timely react to the network changes. Indeed, in an SDN-based network the convergence time of routing algorithms is low and quite invariant respect to the network size [22]. Convergence time depends only on the reactivity of FDs to notify a change in the network to the SDN controller. Only the SDN controller must be advised, then it computes new routes and simultaneously instructs all the involved FDs. Conversely, in a traditional network if a change occurs, the FD first updates its routing tables, then sends a message to its neighbors. These on their turn updated their tables and send the message to their neighbors and so on. The message propagates in the network. Then each node updates its routing tables and sends its best paths to the other routers. This messages flooding introduces a significant delay because all FDs must be advised, then updated routing information must be propagated. Obviously, the convergence time and the delay increase with the network dimension. Moreover, SDN allows use of a centralized algorithm as the one we propose. Indeed, in this case a distributed algorithm would be impracticable, because all routes are calculated/updated together so that to fairly distribute the UTDs. This operation can be done only by a central entity that has a global view of the network. As an example, Figure 4 reports the path-reconfiguration that follows the increase of the data-traffic demand of the node \(D\). In particular, three nodes, \((D,E,F)\), are involved in  
Figure 3: Messages-flow for network updates: (**a**) SDN controller initiated (status update), (**b**) FD-initiated (link failure). the network changes. The routes are depicted only for these nodes, and we suppose, in this example, that only data traffic is present directed toward the CN. Initially, the node \(D\) requires 30 Mbps that can be entirely routed toward the CN by means the direct link. The network can satisfy all the traffic demands (i.e., no UTDs). When node \(D\) increases its traffic demand up to 50 Mbps, the shortest path (i.e., the direct path toward the CN) would lead an UTD for the node \(D\) of 20 Mbps. The proposed algorithm instead looks for the solution that minimizes the total UTD.