# Placement of IoT Microservices in Fog Computing Systems: A Comparison of Heuristics
## 2 Background and Problem Definition
### Problem Definition  
We now define the problem of microservice placement in a fog computing infrastructure. In order to formalize the optimization problem, we introduce the symbols and notation in Table 1.  
The goal of the optimization problem is to minimize the average response time of each service chain; thus, the objective function in Equation (1) is a weighted sum of the response time for every considered service chain. The weights \(w_{c},\forall c\in\mathcal{C}\) are chosen such that \(\sum_{c}w_{c}=1\). One possible approach, which we use in this paper, is to consider the weight of every service chain proportional to its activation frequency \(\lambda_{c}\), that is, \(w_{c}=\lambda_{c}/\Lambda\) with \(\Lambda=\sum_{c}\lambda_{c}\), although other solutions can be adopted without altering the general validity of the model. \[\min obj(X)=\sum_{c\in\mathcal{C}}w_{c}R_{c}\] (1) subject to: \[\sum_{f\in\mathcal{F}}x_{m,f} =1\quad\forall m\in\mathcal{M}, \tag{2}\] \[\lambda_{f}S_{f} <1\quad\forall f\in\mathcal{F},\] (3) \[R_{c} <T_{c}^{SLA}\quad\forall c\in\mathcal{C},\] (4) \[x_{m,f} =\{0,1\},\quad\forall m\in\mathcal{M},f\in\mathcal{F}, \tag{5}\] \begin{table}
\begin{tabular}{c c} \hline \hline  & **Model Parameters** \\ \hline \(\mathcal{M}\) & Set of microservices \\ \(\mathcal{F}\) & Set of fog nodes \\ \(\mathcal{C}\) & Set of service chains \\ \(\lambda_{m}\) & Incoming rEquation rate to microservice \(m\) \\ \(\lambda_{f}\) & Incoming rEquation rate to fog node \(f\) \\ \(\lambda_{c}\) & Incoming rEquation rate to service chain \(c\) \\ \(\Lambda\) & Incoming global request rate \\ \(S_{m}\) & Avg. service time for microservice \(m\) \\ \(\sigma_{m}\) & Standard deviation of \(S_{m}\) \\ \(P_{f}\) & Computational power of fog node \(f\) \\ \(W_{f}\) & Avg. waiting time on fog node \(f\) \\ \(S_{f}\) & Avg. service time on fog node \(f\) \\ \(\sigma_{f}^{\prime}\) & Standard deviation of \(S_{m}\) \\ \(R_{f}\) & Avg. response time for fog \(f\) \\ \(R_{c}\) & Avg. response time for service chain \(c\) \\ \(T_{c}^{\delta LA}\) & SLA of service chain \(c\) \\ \(\sigma_{m_{1},m_{2}}\) & Services order of execution in a chain \\ \(\delta_{f_{1},f_{2}}\) & Network delay between nodes \(f_{1}\) and \(f_{2}\) \\ \hline \multicolumn{2}{c}{**Model indices**} \\ \hline \(f\) & Fog node \\ \(c\) & Service chain \\ \(m\) & Microservice \\ \hline \multicolumn{2}{c}{**Decision variables**} \\ \hline \(x_{m,f}\) & Allocation of microservice \(m\) to fog node \(f\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notation and parameters for the proposed model. The optimization problem is characterized by three constants. Equation (2) means that every microservice is allocated to one and only one fog node. Equation (3) forces every fog node not to be in an overload condition (\(\lambda_{f}S_{f}\) is the load on fog node \(f\)). The model can be extended to cope with additional constraints, such as available memory on the fog nodes or I/O limits; for the sake of simplicity, we focus here on a model with as few constraints as possible. The last model constraint, Equation (4), requires that the SLA of each service chain be respected. In this paper, we consider  
\[T_{SLA}=K\cdot\sum_{m\in c}S_{m} \tag{6}\]  
where \(K\) is a coefficient. The last constraint, Equation (5), captures the Boolean nature of the decision variable \(x_{m,f}\). The objective function of the optimization problem requires a model for the response time of a service chain. To this end, we must consider that the invocation of a generic service chain \(c\) can be described as a sequence of the wait time, service time, and network delay for every fog node hosting a service belonging to that chain.