# Optimizing Service Placement for Microservice Architecture in Clouds
## 2 Problem Formulation
### Objective  
To achieve a desired performance of service-based applications, a scheduler should not only consider the multi-resource demands of services but also the traffic situation between services.  
\begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Description** \\ \hline \(\mathcal{M}\) & Set of heterogeneous machines in the cluster: \(\mathcal{M}=\{m_{1},m_{2},...,m_{M}\}\) \\ \hline \(M\) & Number of the machines: \(M=|\mathcal{M}|\) \\ \hline \(\mathcal{R}\) & Set of resource types: \(\mathcal{R}=\{r_{1},r_{2},...,r_{R}\}\) \\ \hline \(R\) & Number of the resource types: \(R=|\mathcal{R}|\) \\ \hline \(V_{i}\) & Vector of available resources on machine \(m_{i}\): \(V_{i}=(v_{i}^{1},v_{i}^{2},...,v_{i}^{R})\) \\ \hline \(v_{i}^{j}\) & Amount of resource \(r_{j}\) available on machine \(m_{i}\) \\ \hline \(\mathcal{S}\) & A service-based application which is composed by a set of services: \(\mathcal{S}=\{s_{1},s_{2},...,s_{N}\}\) \\ \hline \(N\) & Number of services in the application: \(N=|\mathcal{S}|\) \\ \hline \(D_{i}\) & Vector of resource demands of service \(s_{i}\): \(D_{i}=(d_{i}^{1},d_{i}^{2},...,d_{i}^{R})\) \\ \hline \(d_{i}^{j}\) & Amount of resource \(r_{j}\) that service \(s_{i}\) demands \\ \hline \(\mathbb{T}\) & Matrix of communication traffic between services: \(\mathbb{T}=[t_{ij}]_{N\times N}\) \\ \hline \(t_{ij}\) & Traffic rate from service \(s_{i}\) to service \(s_{j}\) \\ \hline \(\mathbb{X}\) & A placement solution: \(\mathbb{X}=[x_{ij}]_{N\times M}\), where \(x_{ij}=1\) if service \(s_{i}\) is to be placed on machine \(m_{j}\), otherwise \(x_{ij}=0\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notation and Description.  
As services, especially data-intensive services, often need to transfer data frequently, the network performance would directly influence the overall performance. Considering the network dynamics, the placement of different services of an application is crucial for maintaining the overall performance, particularly when unexpected network latency or congestion occurs in the cluster. Given the traffic situation, the most intuitive solution is to place the services that have high traffic rate among them on the same machine so that the co-located services can leverage the loopback interface to get a high network performance without consuming actual network resources of the cluster. However, such services cannot all be co-located on one machine due to limited resource capacities. Thus, with the resource constraints, we try to find a placement solution to minimize the overall traffic between services that are placed on different machines (inter-machine traffic) while satisfying multi-resource demands of services, so that the objective of this work can be formulated as:  
\[\textbf{Minimize} \sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{\begin{subarray}{c}p=1\\ q\
eq p\end{subarray}}^{M}t_{ij}\cdot x_{ip}\cdot x_{jq} \tag{1}\] \[\textbf{Subject to:} \sum_{j=1}^{M}x_{ij}=1\ (\forall i\in\{1,2,...,N\})\] (2) \[\sum_{i=1}^{N}x_{ij}\cdot d_{i}^{k}\leq v_{j}^{k}\ (\forall j\in\{1,2,...,M\}, \forall k\in\{1,2,...,R\})\] (3) \[x_{ij}\in\{0,1\}\ (\forall i\in\{1,2,...,N\},\forall j\in\{1,2,...,M\}) \tag{4}\]  
Equation (2) guarantees that each service is placed on a machine. Equation (3) guarantees that resource demands on a machine do not exceed its resource capacities. Equation (1) expresses the goal of this work.