# SDN-Based Routing for Backhauling in Ultra-Dense Networks
## 5 Problem Formulation  
As stated before, dense and random deployment of the network infrastructure imposes new challenges in the backhauling, which becomes the capacity bottleneck and may not be able to support all the traffic demanded by cells. As consequence, we formulate a new routing problem that is particularly suited for this scenario. We suppose that the admission of an access point to the network is constrained by the control traffic, i.e., a small cell can be admitted only if there is at least one path on the backhaul network that supports its control-traffic bandwidth demand. By contrast, the data traffic demand can be only partially satisfied (i.e., it is not constrained). The main concept is that control traffic is mandatory for an access point to function, hence, it cannot be limited. Conversely, if the backhaul network is not able to support all the data traffic demand, the SDN controller instructs the small-cell BS to take actions at RAN level to reduce its data traffic such as call blocking, UE's throughput reduction and load balancing policies [34]. In general, in a UDN, UEs are under the radio coverage of multiple cells,  
Figure 1: Considered scenario. hence, they can be forced to connect to different cells, thus operating load balancing directly at the ingress nodes. As a consequence, we want to jointly solve:  
* a bandwidth-constrained problem for the control traffic;
* the minimization of the _total amount of unsatisfied traffic demand_ (_UTD_) of the cells, with a fair distribution of unsatisfied demands. The routing algorithm allows the finding of the path from a source node to a destination for both control and data traffic. In particular, being \(\mathcal{L}_{v,w}\) the set of all the possible paths from ingress node \(v\) to egress node \(w\), whose generic element is \(L_{v,w}\), the routing algorithm allows selection of one of these paths for the control \(\underline{L}_{v,w}^{C}\) and for the data traffic \(\underline{L}_{v,w}^{D}\) (The two flows have different constraints, hence, can have different routes even if they have the same ingress and egress nodes.). Each path \(L_{v,w}^{C(D)}\) is composed by a set of edges \(L_{v,w}^{C(D)}=\{e_{v,i},e_{i,j},...,e_{k,w}\}\). As a consequence, we can define two three-dimensional matrices \(\mathbf{P}^{C}\) and \(\mathbf{P}^{D}\) with dimension \(V\mathcal{V}\mathcal{V}\mathcal{V}\mathcal{V}\mathcal{V}\mathcal{V}\) whose element \(p_{v,w,e_{i,j}}^{C(D)}=1\) if the path from ingress node \(v\) to egress node \(w\) passes through link \(e_{i,j}\), zero otherwise. The total demand of traffic through edge \(e_{i,j}\in\mathcal{E}\) is  
\[Q_{e_{i,j}}=\sum_{(v,w)\in\mathcal{V}^{2}}\left[d_{v,w}^{C}p_{v,w,e_{i,j}}^{C }+d_{v,w}^{D}p_{v,w,e_{i,j}}^{D}\right] \tag{1}\]  
where \(\mathcal{V}^{2}\) is the set of all the possible vertex-pairs, \((v,w)\), whose dimension is \(V\) X \(V\). If the edge capacity, \(c_{e_{i,j}}\), is lower than \(Q_{e_{i,j}}\), the link \(e_{i,j}\) is not able to support all the traffic demand. Let us define two matrices of allocation \(\mathbf{A}^{C}\) and \(\mathbf{A}^{D}\), whose element \(a_{v,w}^{C(D)}\) represents the amount of capacity that has been allocated to the flow from node \(v\) to node \(w\) for the control and data traffic, respectively. We can formulate the optimization problem as  
\[\min_{\mathcal{L}_{v,w}\forall(v,w)\in\mathcal{V}^{2}} \left\{\sum_{(v,w)\in\mathcal{V}^{2}}\frac{d_{v,w}^{D}-a_{v,w}^{D}}{d _{v,w}^{D}}\right\}\] (2) s.t. : \[d_{v,w}^{C}=a_{v,w}^{C}\quad\forall(v,w)\in\mathcal{V}^{2} \tag{3}\] \[d_{v,w}^{D}\leq a_{v,w}^{D}\quad\forall(v,w)\in\mathcal{V}^{2} \tag{4}\]  
where the first constraint imposes that the control-traffic capacity demand is always satisfied, while the second imposes that the amount of capacity assigned to a data flow does not exceed the demand. Moreover, _fairness_ is introduced by normalizing the UTD for the data-traffic demand of each flow, \(d_{v,w}^{D}\). The aim is to have almost the same percentage of UTDs for different flows.