# Scheduling for Media Function Virtualization
## 4 System Model and Algorithm
### VMF-FG Scheduling Algorithm
More precisely, for path \(p\), first, a greedy schedule is allocated for the destination link (\((p[-2],p[-1])\)) and it is checked whether it is compatible with the other links in \(p\) using procedure PhhSch. If not, \(\phi\) is returned; otherwise, PthSch returns the packet schedule for the whole path \(p\). The current path \(p\), the associated schedule \(s\), and the start and end timings \(t_{start}\), \(t_{end}\) of \(s\) are returned. Figure 4: Illustration for the relationship between different VMF timing schedules. ```
/* VMF input output timing Global :G^I, \(\tau_{start}^{out}\), \(\tau_{end}^{out}\), \(\tau_{start}^{in}\), \(\tau_{end}^{in}\)
1 Procedure VlinkSch(\(f_{i}\), \(f_{j}\), \(bv_{f_{i}f_{j}}\), \(n_{1}\), \(n_{2}\), \(\alpha\), \(\gamma\), \(\omega\)):
2\(t_{end}\gets\)\(\tau_{start}^{out}[f_{j}]-d_{proc}(f_{j})\);
3\(p\), \(s\), \(t_{start}^{in}\), \(t_{end}^{in}\leftarrow\) PthSchGrad(\(bv_{f_{i}f_{j}}\), \(n_{1}\), \(n_{2}\), \(\omega\), \(t_{end}\));
4 if\(p==\phi\)then
5 return False;
6
7 end if
8 else
9\(T_{start}^{in}[f_{j}]\), \(T_{end}^{in}[f_{j}]\gets t_{start}^{in}\), \(t_{end}^{in}\);
10\(T_{start}^{out}[f_{i}]\), \(T_{in}^{out}[f_{i}]\gets t_{start}^{in}-\) PthDel(\(G^{I}\), \(p\)), \(t_{end}^{in}-\) PthDel(\(G^{I}\), \(p\)); /* get a core on \(n_{1}\) for\(f_{i}\) scheduling */
11\(core\leftarrow\)\(\texttt{PushSch}(f_{i}\), \(n_{1}\), \(T_{start}^{out}[f_{i}]-d_{proc}(f_{i})\), \(T_{start}^{out}[f_{i}])\);
12 if\(core==\phi\)then
13 return False
14
15 end if
16\(\alpha[f_{i}]\), \(\gamma[(f_{i},f_{j})],\omega[(f_{i},f_{j})]\leftarrow(n_{1},core)\), \(p\), \(s\);
17 return True;
18
19 end if
20
21 end if
22
23 end if
```  
**Algorithm 2** Procedure for allocating a schedule for a virtual link  
We are interested in scalability of the above heuristic with the problem size; thus, we analyze the run time complexity in terms of VMF-FG and MFVi network size, i.e, \(|\mathcal{F}|\), \(|\mathcal{L}|\), \(|N|\), and \(|E|\). The run time of Algorithm 3 is dominated by procedure Pths that returns a maximum of \(K\) paths between \(n_{1}\) and \(n_{2}\), and thus has complexity \(O(|K||N|(|E|+|N|log(|N|)))\); thus, procedure VlinkSch in Algorithm 2 also has \(O(|K||N|(|E|+|N|log(|N|)))\) complexity. The given VMF-FG procedure is traversed using BFS (Algorithm 1) that has a complexity of \((|\mathcal{F}|+|\mathcal{L}|)\) and \(\forall(f,f_{d}w)\in\mathcal{L}\) procedure VlinkSch is called. This results in an overall run time complexity of the heuristic to be \(O(|\mathcal{F}|+|\mathcal{L}||K||N|(|E|+|N|log(|N|)))\). ```
Global :G^I, \(|\mathcal{C}|\)
1 Procedure PthsSchGrad(\(bv\), \(n_{1}\), \(n_{2}\), \(\omega\), \(t_{end}\)):
2\(\tilde{t}_{end}\gets t_{end}\%|\mathcal{C}|\);
3 for\(p\) in Pths(\(G^{I}\), \(n_{1}\), \(n_{2}\), \(K\))do
4 for\(d\) in \([0,|\mathcal{C}|]\)do
5\(t_{end}^{new}\leftarrow(\tilde{t}_{end}-\Delta t)\%|\mathcal{C}|\);
6\(s_{link},t_{start},t_{end}\leftarrow\)\(\texttt{GradAlloc}(bw\), \(\omega\), \(p[-2]\), \(p[-1]\), \(t_{end}^{new}\));
7 if\(s_{link}\
eq\phi\)then
8\(s\leftarrow\) PthSch(\(s_{link}\), \(p\));
9 if\(s\
eq\phi\)then
10 return\(p\), \(s\), \(t_{start}\), \(t_{end}\);
11
12 end if
13
14 end if
15
16 end for
17 return\(\phi\), \(\phi\), \(\phi\), \(\phi\);
18
19 end for
```  
**Algorithm 3** Procedure for chaining and scheduling on a path