# Scheduling for Media Function Virtualization
## 4 System Model and Algorithm
### VMF-FG Scheduling Algorithm  
The VMF-FG scheduling algorithm shown in Algorithm 1 can be implemented using two different graph traversal algorithms, i.e., breadth-first search (BFS) and depth-first search (DFS). With BFS, scheduling of all VMFs at the same depth from the starting node is done together, whereas with DFS, scheduling of VMFs along a path (as far as possible) is performed before backtracking. The two flavors of the VMF-FG scheduling utilize two different data structures in order to traverse the given VMF-FG, the queue for BFS, and the stack for DFS. The VMF-FG scheduling variables are initialized and the VMF-FG traversal starts by initializing \(Q_{vmf}\) with the sink node. Next, a while loop is used to traverse the VMF-FG starting from \(vmf_{smk}\) until \(Q_{vmf}\) is empty. A VMF is dequeued (popped) from \(Q_{vmf}\) and stored in \(f\). For each (already placed) neighboring VMF \(f_{duv}\in\texttt{DustrNbrs}(\mathcal{F},f)\) downstream to \(f\), the scheduling of VMF \(f\) and the associated virtual link \((f,f_{duv})\) is iteratively attempted using procedure \(\texttt{VlinkSch}\). The tentative node to place \(f\) is selected using the next-fit algorithm, starting from the same node where \(f_{duv}\) is placed, i.e., \(\alpha[f_{duv}]\), then the next node and so on (\(\alpha[f_{duv}]+\delta n\)). The neighbors of \(f\) are then added to the VMF queue (l. 12-14). Next, we describe the procedure for virtual link scheduling in detail. The procedure to schedule virtual links is presented in Algorithm 2. The procedure \(\texttt{VlinkSch}\) takes the bandwidth requirement \(bw_{f_{i},f_{j}}\) of the virtual link \((f_{i},f_{j})\), the server nodes for the potential placement of \(f_{i}\) and \(f_{j}\): \(n_{1}\) and \(n_{2}\), the current placement (a), chaining (\(\gamma\)), and link schedule (\(\omega\)) as input. As illustrated in Figure 4, the input schedule at VMF \(f_{j}\) must end \(d_{proc}(f_{j})\) before \(f_{j}\) starts transmitting the processed (output) frame (l. 2). Next, procedure PhhSchGrd (discussed next) is called to greedily allocate \(bw_{f_{i},f_{j}}\) among \(|C|\) cycles between \(t_{end}\) and \(t_{end}-T_{c}+1\). The feasible path \(p\), the associated schedule \(s\), and the timings of the start and end cycles of \(s\) are returned by PhhSchGrd. In the case that a feasible path/schedule does not exist, the procedure is terminated by returning \(\phi\) (l. 5). Else, VMF timings are updated and a schedule for \(f_{i}\) is generated using procedure CpuSch. As shown in Figure 4, \(f_{i}\)'s output timings are obtained by delaying \(f_{i}\)'s input timings (l. 9) by the path delay (PhDel(\(p\))). CpuSch returns an available CPU core on \(n_{1}\) where \(f_{i}\) can be scheduled between time interval \((T_{start}^{out}[f_{i}]-d_{proc}(f_{i}),T_{start}^{out}[f_{i}])\). Before returning, the placement, chaining, and scheduling variables are updated (l. 14). ```
1\(\alpha\), \(\gamma\), \(\omega\leftarrow\phi\), \(\phi\), \(\phi\);
2 for\(vmf_{s\text{nk}}\in\mathcal{F}_{s\text{nk}}\)do
3\(Q_{vmf}\leftarrow\{vmf_{s\text{nk}}\}\); /* initializing a queue if using BFS else a stack if using DFS */
4 while\(|Q_{vmf}|>0\)do
5\(f\leftarrow Q_{vmf}.dequeue()\); /* if DFS do\(pop()\) instead of \(dequeue()\) */ /* schedule \(f\) and vlink \((f,f_{dw})\) */
6 for\(f_{dw}\) in DustrNbrs(\(\mathcal{G},f\))do
7\(\delta n\gets 0\);
8 whileVlinkSch(\(f\),\(f_{dw}\),\(bw_{f,f_{dw}}\), \(\alpha[f_{dw}]+\delta n\), \(\alpha[f_{dw}]\), \(\alpha,\gamma,\omega\)) do
9\(\delta n\leftarrow\delta n+1\);
10
11 end if
12
13 end for /* enqueue the upstream neighbors */
14 for\(nbr\) in UpstrNbrs(\(\mathcal{G},f\))do
15\(Q_{vmf}.enqueue(nbr)\)
16
17 end for
18
19 end for
```  
**Algorithm 1** Simplified pseudocode for the VMF-FG scheduling algorithm; a given VMF-FG \(\mathcal{G}=(\mathcal{F},\mathcal{L})\) is to be scheduled on the MFVi network \(G^{I}=(N,E)\)  
Procedure PthSchGrd iterates over all the paths between \(n_{1}\) and \(n_{2}\) and returns a feasible schedule, if it exists.