# The Value of Simple Heuristics for Virtualized Network Function Placement
## 3 Placement Heuristics
### All Shortest Path Placement  
Our third heuristic takes advantage of the fact that there can be more than one shortest path between a source and destination. To increase the probability of accepting a request, this heuristic searches for all shortest paths in the network and chooses the one that has a maximum-minimum nodal resource. The search for all shortest paths is performed by using a search method similar to BFS. BFS explores the links of the graph to discover the node that is reachable from the source node. It computes the shortest distance (in terms of number of hops) from the source to each reachable node in the graph. We modified BFS to start from the source and end when it reaches the destination node. Also, in addition to the distance, we record the shortest paths themselves. In our search for shortest paths we define an array and a set for each node \(u\) in the physical network:  
Figure 1: Random placement example.  
Figure 2: Random placement example.  
* \(dist_{u}\): An array that represents the shortest distance (number of hops) from the source node.
* \(nodes_{u}\): A set which records nodes involved in each shortest path found from source node to node \(u\).  
The initial value of \(dist\) for all nodes is infinity, except for the source node which is equal to 0, and initially set of \(nodes\) for all nodes is empty. The search algorithm starts traversing the physical network graph and while visiting neighbor \(y\) of node \(x\) it compares the value of \(dist_{y}\) with \(dist_{x}+1\). If \(dist_{y}\) is greater than \(dist_{x}+1\), \(dist_{y}\) describes a path longer than the shortest path. So we decrease \(dist_{y}\) to \(dist_{x}+1\) and assign \(nodes_{x}\) to \(nodes_{y}\). If \(dist_{y}=dist_{x}+1\), we found another shortest path to node \(y\). In this case, \(nodes_{y}\) is the union of \(nodes_{x}\) and \(nodes_{y}\). The pseudo-code of this search algorithm is presented as Algorithm 1. This algorithm finds all possible shortest paths for any pairs of nodes. The output of the algorithm is \(nodes_{dest}\), which is a set of shortest paths from a source nod \(x\) to a destination node \(dest\) in the physical network.  
```
Result:\(nodes_{dest}\) that contains all shortest paths  x is the source node;  y are the neighbors of node \(x\); while\(y\sim destination\)do if\(dist_{y}>dist_{x}+1\)then \(dist_{y}\gets dist_{x}+1\); \(nodes_{y}\gets nodes_{x}\); elseif\(dist_{y}=dist_{x}+1\)then \(nodes_{y}\leftarrow[nodes_{y};nodes_{x}]\); \(x\gets y\); \(y\gets neighbors-of-y\);  end while
```  
**Algorithm 1**Finding all shortest paths.  
The following example demonstrates how we update the parameters of each node during the search for all shortest paths. As shown in Figure 3, we consider a network of 6 nodes and want to find all shortest paths from node 1 to 5. In the first stage, we update the parameters of the source node's neighbors, which are nodes 2 and 3. Figure 2(a) shows the first stage and updated parameters of the neighbors of node 1. Figure 2(b) shows the second stage, after we updated the parameters for neighbors of node 2. In the final stage, when processing node 5, \(dist_{5}=dist_{3}+1\). So we update \(nodes_{5}\) to the union of \(nodes_{3}\) and \(nodes_{5}\). Figure 2(c) shows the final stage. All available shortest paths from 1 to 5 are recorded in \(nodes_{5}\).  
We applied this all shortest path heuristic to the same example in the previous sections and the resulting placement is shown in Figure 4. Between the source and destination of the SG there are two shortest paths \(\{1,3,5\}\), and \(\{1,2,5\}\). The maximum-minimum resource belongs to the second path. All NFs are placed in the source node as the policy here is to place them in the first node that has sufficient nodal resources.  
Figure 3: First, second, and final stages of finding all shortest paths.