# Placement of IoT Microservices in Fog Computing Systems: A Comparison of Heuristics
## 3 Heuristics for Microservice Placement
### Modified Best Fit Decreasing  
The Modified Best Fit Decreasing (MBFD) algorithm is a heuristic exploited in [11] to solve a server consolidation problem aimed at optimizing the placement of virtual machines on physical hosts for optimal energy and resource consumption. Because of the similar nature of the problem, we decided to implement an adapted version of MBFD to address the microservice allocation problem in fog computing infrastructures described in Section 2.2. In this adaptation, instead of mapping VMs onto hosts, microservices are mapped onto fog nodes.  
As in the original algorithm [11], the adapted MBFD shown in Algorithm 1 follows a greedy approach.  
The input structures are two lists that contain all the data of the fog nodes and microservices (e.g., fog node capacity) required to compute the solution. The main loop (defined in line 1) iterates on all the microservices ordered by mean service time; the motivation for this choice is to start the mapping process with the most demanding services. This is the same as in the original MBFD algorithm, and does not consider the impact of network delays in a distributed system.  
Next (line 5-11), the algorithm iterates over the fog nodes, trying to place the microservice on each fog node. For every possible mapping, the SLA and the other constraints are checked to verify whether the solution is acceptable. In the case of an acceptable solution, the objective function is computed according to Equations (1) and (7). In this way, the best placement for that microservice is found and added to the solution being built. It is worth noting that the main difference from the original MBFD algorithm lies in the objective function. The objective function is the only part of the algorithm that considers network effects. Therefore, we expect this algorithm to provide higher quality solutions in cases where the network effect is not the main driver of optimal microservice placement.  
```
1:\(msList\): list of microservices, \(fogList\): list of fog nodes
2:\(mapping\): mapping of micro service over fog nodes
3:for\(ms\in\) decreasing_sort(\(msList\)) do
4:\(mapping[ms]\gets None\)
5:\(best\_obj\gets None\)
6:\(new\_mapping\gets mapping\)
7:for\(f\in fogList\)do
8:\(new\_mapping[ms]\gets f\)
9:ifsla_ok(\(solution\)) & constraints_ok(\(solution\)) then
10:\(obj\leftarrow\) compute_obj_function(\(mapping\))
11:if\(best\_obj=None||obj<best\_obj\)then
12:\(mapping[ms]\gets f\)
13:\(best\_obj\gets obj\)
```  
**Algorithm 1** Modified Best Fit Decreasing  
The \(Compute\_solution\) function (Algorithm 2) calculates the object function described in Section 2.2 based on the fog and chain parameters of the new mapping.  
Finally, the algorithm determines whether \(new\_solution\) is a better solution by checking the following:  
* The Service Level Agreement is respected (4): this constraint is represented by the mean service time multiplied by a constant \(k\) (usually 10), as in Section 4.
* Resources are used in a proper way: as an example, the remaining capacity of the fog nodes in a solution should not be less than zero.
* The objective function in (1) in \(new\_solution\) is better than the older one in \(current\_solution\); as network delays are considered, MBFD can balance the placement using awareness of the delay between nodes.  
The result of Algorithm 1 is the list of all microservices mapped over the fog nodes.  
```
1:\(mapping\): mapping of microservices on fog nodes
2: Objective function for a given solution
3:for each \(fogList\)do
4:if\(\Lambda\)!= 0 then
5: calculate \(S_{f}\), \(\sigma_{f}\) and \(R_{f}\)
6:else
7:\(S_{f}\), \(\sigma_{f}\) and \(R_{f}\) all equals to 0
8:for each \(chainList\)do
9: calculate \(R_{c}\) based on the \(m\)'s mapping
10: calculate object function
```  
**Algorithm 2** compute_obj_function