# Optimizing Service Placement for Microservice Architecture in Clouds
## 4 Placement Algorithm
### Heuristic Packing  
Given a partition of the application, the algorithm here is to pack each part into the heterogeneous machines. Without considering the traffic rate, the problem can be formulated as a classical multi-dimensional bin packing problem, which is known to be NP-hard [11]. When there are a large amount of services involved in the application, it is infeasible to find the optimal solution in polynomial time. Considering the time complexity and packing quality, we adopt two greedy heuristics in our packing algorithm: _Traffic Awareness_ and _Most-Loaded Heuristic_. The algorithm is shown in Algorithm 4.  
```
Input: partition of the application \(P=\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{N^{\prime}}\}\), vectors of available resources on each machine \(\{V_{1},V_{2},...,V_{M}\}\) Output: a placement solution \(X\)
1 Calculate vectors of resource demands of each part as: \(\{D^{\prime}_{1},D^{\prime}_{2},...,D^{\prime}_{N^{\prime}}\}\);
2\(X\leftarrow[x_{ij}=0]_{N^{\prime}\times M}\);
3 for\(i\gets 1\); \(i\leq N^{\prime}\); \(i\gets i+1\)do
4\(tf\gets 0\); \(ml\gets 0\); \(y\gets 0\);
5 for\(j\gets 1\); \(j\leq M\); \(j\gets j+1\)do
6 ifpart \(\mathcal{S}_{i}\) can be packed into machine \(m_{j}\)then
7\(tf_{j}\leftarrow\sum t_{uv}\); /* Calculate the total traffic rates between part \(\mathcal{S}_{i}\) and machine \(m_{j}\), for any service \(s_{u}\) in \(\mathcal{S}_{i}\) and any service \(s_{v}\) packed into machine \(m_{j}\) before */
8\(ml_{j}\leftarrow\sum_{k=1}^{R}\frac{d^{k}_{j}}{v^{k}_{i}}\); /* Calculate the load situation between the vector of resource demands from part \(\mathcal{S}_{i}\) and the vector of available resources on machine \(m_{j}\) */
9 if\(tf_{j}>tf\)then
10\(tf\gets tf_{j}\); \(ml\gets ml_{j}\); \(y\gets j\);
11 end if
12 else if\(tf_{j}==tf\) and \(ml_{j}>ml\)then
13\(tf\gets tf_{j}\); \(ml\gets ml_{j}\); \(y\gets j\);
14
15 end if
16
17 end for
18 if\(y==0\)then
19 return\(null\);
20
21 end if
22 else
23\(V_{y}\gets V_{y}-D^{\prime}_{i}\); \(x_{iy}\gets 1\);
24
25 end if
26
27 end for
28 return\(X\);
```  
**Algorithm 4**Heuristic Packing  
In order to find a best possible machine for part \(\mathcal{S}_{i}\), the algorithm calculates two matching factors: \(tf\) and \(ml\). For machine \(m_{j}\), the factor \(tf\) is the sum of the traffic rate between the services in part \(\mathcal{S}_{i}\), and the services have been determined to be packed into machine \(m_{j}\) before. The factor \(ml\) is a scalar value of the load situation between the vector of resource demands from part \(\mathcal{S}_{i}\) and the vector of available resources on machine \(m_{j}\). Assuming \(D^{\prime}_{i}\) is the resource demand vector of part \(\mathcal{S}_{i}\) and \(d^{k}_{j}\) is the amount of resource \(r_{k}\) part \(\mathcal{S}_{i}\) demands, it is \(ml=\sum_{k=1}^{R}\frac{d_{i}^{k}}{v_{i}^{k}}\). The higher \(ml\) is, the more loaded the machine. The idea of this heuristic is to improve the resource efficiency by packing the part to the most loaded machine. As our main goal is to minimize the inter-machine traffic, the algorithm is designed to first prioritize the machines based on the factors of \(tf\). If the factors of \(tf\) are the same, it then prioritizes the machines based on the factors of \(ml\). Consequently, if all parts in the partition can be packed into machines, the algorithm returns the placement solution. Otherwise, it returns \(null\).