# Dynamic Allocation of SDN Controllers in NFV-Based MEC for the Internet of Vehicles
## 4 Problem Formulation
Then, it checks whether \(g_{unsted}\) has enough spare capacity for supporting the number of requests from \(d_{max}\). If this condition is satisfied, the RSU is assigned to the controller, which is inserted in its list \(G\) (lines 5-6). Otherwise, a new controller is created. To identify how many resources should be allocated to the new controller, the smallest resource \(v^{\prime}\) is removed from the templates list \(V^{\prime}\) (lines 7-11). Then, aiming at creating a controller with a minimum of \(\beta\) times the capacity required to serve \(d_{max}\) RSU, \(v^{\prime}\) is compared with (\(d_{max}\cdot\beta\))(line 12). The \(\beta\) parameter is a demand multiplier that aims to reduce the number of allocated controllers. Finally, a new controller \(g_{v^{\prime}}\) is created considering both the template \(v^{\prime}\) and the number of reserved \(\omega\) resources, as well as the assigned \(d_{max}\) (lines 13-14). These steps are repeated until there are no RSUs to be assigned. ```
1:List of requests by RSUs, \(D\)
2:List of resource capacity templates, \(V\)
3:Demand multiplier, \(\beta\)
4:Amount of resource reservation, \(\omega\)
5:List of controllers with their resource capacity and respective assigned RSUs, \(G\)
6:\(G=\emptyset\)
7:while\(R\
eq\mathcal{O}\)do
8:\(d_{max}\gets max_{request}(D)\)
9:\(g_{unsted}\gets max_{unsted}(G)\)
10:if\(g_{unsted}>d_{max}\)then
11:\(G\gets G\cup\textbf{assignment}(g_{unsted},d_{max})\)
12:else
13:\(G\gets G\cup g_{unsted}\)
14:\(V^{\prime}=V\)
15:while\(V^{\prime}\
eq\mathcal{O}\)do
16:\(v^{\prime}\leftarrow min(V^{\prime})\)
17:if\(v^{\prime}>d_{max}\cdot\beta\)then
18:\(g_{v^{\prime}}\leftarrow\textbf{create}(v^{\prime},\omega)\)
19:\(G\gets G\cup\textbf{assignment}(g_{v^{\prime}},d_{max})\)
20:break
21:break
22:break
23:endwhile
24:endif
25:endwhile
```  
**Algorithm 1** Proposed Algorithm - aSDNulloc  
In order to illustrate the idea behind the proposed heuristic, Figure 5 shows a simple example using the aSDNulloc. The first step consists on removing the greatest demanding infrastructure from the list, which in turn must be allocated to a controller with an idle capacity greater or equal to this infrastructure, but respecting the constraint \(\omega\). If there is no such controller that meets these requirements, then, suitable resources from the list of capacities are assigned to the VNF in charge of executing the SDN controller. It is necessary to take into account that the minimum capacity must be greater than or equal to the infrastructure demand multiplied by the value of \(\beta\). The abovementioned step is repeated until there is no infrastructure to be assigned to VNFs. It is possible to observe that in the third iteration the RSU with three requests is designated to the VNF-2, which had already assigned itself the RSU with five requests and had four units of idle resources. At the end of the iteration the VNF-1 remained with two idle resources and with the same amount in reserve before the adopted \(\omega\). VNF-2, on the other hand, had one resource unit idle and another unit in reserve before the value defined for \(\omega\). Last, it is checked the wasted capacity for all VNFs currently executing controllers in order to identify any underutilization of controllers. To this, a comparison among utilized capacity, wasted capacity, and the list of capacities is carried out. That way, since all infrastructures have already been assigned, then it is needed to identify if there is any overprovisioned VNF. In the affirmative case, resource reallocation must be done. The quality of obtained solution is determined by the summation of controllers' idle capacity, which consists in achieving the value 0 (zero) if the solution is optimal. Thus, the closer to zero, the better the quality of the solution provided by aSDNalloc.