# Placement of IoT Microservices in Fog Computing Systems: A Comparison of Heuristics
## 2 Background and Problem Definition
### Problem Definition
Therefore, we can model the response time \(R_{c}\) of service chain \(c\), that is, the component of the sum in Equation (1), using Equation (7):  
\[R_{c} =\sum_{m\in c}\sum_{f\in\mathcal{F}}x_{m,f}\cdot W_{f}+\sum_{m\in c }S_{m}+\] \[+\sum_{m_{1},m_{2}\in c}\sum_{f_{1},f_{2}\in\mathcal{F}}o_{m_{1}, m_{2}}\cdot x_{m_{1},f_{1}}\cdot x_{m_{2},f_{2}}\cdot\delta_{f_{1},f_{2}} \tag{7}\]  
where \(o_{m_{1},m_{2}}\) is the order of execution of microservices in \(c\). In particular, \(o_{m_{1},m_{2}}=1\iff m_{1}\sim m_{2}\), meaning that service \(m_{1}\) is invoked just before service \(m_{2}\) in the service chain. It is worth noting that our simplified approach to describing network delay can be explained by considering that, in the reference scenario, fog nodes are connected with reliable network links. The network delay \(\delta_{f_{1},f_{2}}\) can be expressed as the latency plus the transmission time. In modern networks (often called Long Fat Networks), latency can be on the order of milliseconds or tens of milliseconds even for high speed networks, while transmission time is the product of the available bandwidth (in the orders of tens or hundreds of MBit/s) and message length. Considering the OpenAPI standard in which most microservices consume JSON tuples, we assume the message length to be relatively small and scarcely variant, which explains our modeling choices. The last part of the model concerns the waiting time \(W_{f}\) on fog node \(f\). For this, we must consider that a generic fog node hosting multiple microservices experiences a service time that is a mixture of distributions, each of which refers to a single microservice. The resulting waiting time can be expressed using the Pollaczek-Khinchin equation (8):  
\[W_{f}=\frac{S_{f}^{2}+\sigma_{f}^{2}}{2}\cdot\frac{\lambda_{f}}{1-\lambda_{f} S_{f}}. \tag{8}\]  
The service time of a mixture of distributions can be described using its mean value (Equation (9)) and standard deviation (Equation (10)):  
\[S_{f} =\frac{1}{P_{f}}\cdot\sum_{m\in\mathcal{M}}x_{m,f}\frac{\lambda_{ m}}{\lambda_{f}}S_{  
The underlying assumption of Equation (8) is that the product form can be used to describe the queuing system of the fog infrastructure. However, this assumption is not always valid. Indeed, in case where the service times of the involved microservices cannot be expressed through exponential distributions, the resulting arrival process cannot be defined with an exponential distribution. In such cases, a G/G/1 model should be used in Equation (8) instead of a M/G/1 model. Unfortunately, there are no closed-form solutions to represent the inter-arrival time of a queuing server following the G/G/1 model. An M/G/1 model approximating the system's behaviour may be exploited in cases where multiple microservices are located on a fog node or where the service times of the microservices present a standard deviation close to the mean value. The presented performance model is accurate as long as the system is close to these assumptions. In light of the previous observations, Equation (8) can be used to describe the microservice chain response time as the sum of the following contributions: the sum of waiting times on the fog nodes, sum of service times, and network delays due to data transfer among two subsequent microservices in the service chain. To evaluate the performance of a microservice placement solution, in this paper we consider the following metrics:  
* Heuristic execution time;
* Service chain response time;
* Number of hops normalized against the length of the service chain;
* Jain index. A detailed definition of the evaluation metrics is provided in Section 4.