# SDN-Based Routing for Backhauling in Ultra-Dense Networks
## 6 Proposed Approach
### Data-Flow Routing  
Data traffic path selection is always based on a modified Dijkstra algorithm. However, the algorithm is not constrained and introduces a proportional fairness concept. At the beginning of this phase, the residual capacity matrix, \(\mathbf{R}\), has the value achieved at the end of control-flow allocation.  
The SDN controller lists data flows in descending order, and then performs the allocation starting from the data flow with the highest capacity demand. At the \(s\)-th iteration the Dijkstra algorithm is used to determine the path for the \(s\)-th data flow that has \(v\) as ingress node, \(w\) as egress node and the traffic demand \(d^{D}_{v,w}\).  
As before, first the algorithm looks for the path that has minimum cost and sufficient capacity to accommodate the data-flow demand. If this path, \(L^{D}_{v,w}=\{e_{v,i},e_{i,j},...,e_{k,w}\}\), exists, the residual capacity of all edges belonging to \(L^{D}_{v,w}\) is updated as \(r_{e_{i,j}}(s)=r_{e_{i,j}}(s-1)-d^{D}_{v,w}\).  
However, if no path in \(\mathcal{L}_{v,w}\) supports the traffic demand of the \(s\)-th data flow, the route selection is based on the minimum amount of UTD. Toward this goal, we define the set of data flows allocated on the edge \(e_{i,j}\) at the \((s-1)\)-th step as \(\mathcal{E}_{i,j}(s-1)\). That is, the data flow from ingress node \(v\) to egress node \(w\), \((v,w)\in\mathcal{E}_{i,j}(s-1)\) if \(e_{i,j}\in L^{D}_{v,w}\). Hence, at the \(s\)-th iteration for each possible path from node \(v\) to node \(w\) belonging to the set \(\mathcal{L}_{v,w}\), the UTD is calculated, and the route that guarantees the minimum UTD is selected. The UTD for the considered flow (\(UTD^{D}_{v,w}\)) in the path \(L_{v,w}\) is derived taking into account a proportionally fair distribution of the UTD among all the data flows allocated on an edge, i.e.,  
\[UTD^{D}_{v,w}=\max_{\epsilon_{ij}\in L_{v,w}}\left\{\frac{d^{D}_{v,w}}{\sum_{( q,r)\in\mathcal{E}_{ij}(s-1)}d^{D}_{q,r}}\left[\sum_{(q,r)\in\mathcal{E}_{ij}(s-1 )}d^{D}_{q,r}-r_{\epsilon_{ij}}(0)\right]\right\} \tag{5}\]  
More in detail, \(\left[\sum_{(q,r)\in\mathcal{E}_{ij}(s-1)}d^{D}_{q,r}-r_{\epsilon_{ij}}(0)\right]\) is the amount of requested data traffic that cannot be satisfied by the edge \(\epsilon_{ij}\), which is the sum of all the allocated demands minus the capacity of the edge. The total amount of data traffic that cannot be satisfied by the edge \(e_{i,j}\), is fairly distributed among all the paths allocated on that edge. In particular, the weighted UTD of the flow \((v,w)\) on edge \(e_{i,j}\) is proportional to its original demand, \(d^{D}_{v,w}\). Finally, the \(UTD^{D}_{v,w}\) is given by the edge \(e_{i,j}\in L_{v,w}\) that introduces the maximum amount of weighted UTD. Indeed, the traffic that can pass through the path \(L_{v,w}\) depends on the edge that has the minimum capacity (i.e., the bottleneck).  
As a consequence, the selected path is  
\[\bar{L}^{D}_{v,w}=\arg\min_{\mathcal{L}_{v,w}}UTD^{D}_{v,w} \tag{6}\]  
and the capacity allocated to the data flow is \(a^{D}_{v,w}=d^{D}_{v,w}-UTD^{D}_{v,w}\).  
The procedure is repeated for all the data flows. Figure 2 reports the flow diagram of the proposed algorithm.  
Figure 2: Proposed routing algorithm flow diagram.