# Optimizing Service Placement for Microservice Architecture in Clouds
## 3 Minimum K-Cut Problem  
As a service-based application typically cannot be placed on one machine, an effective partition of the set of services involved in the application is necessary during the deployment. After partition, each subset of the services should be able to be packed into a machine, which means the machine has sufficient resources to run all the services in the subset. Considering the traffic rate between different services, the quality of the partition is crucial for the application performance. To tackle this problem, we first discuss the minimum k-cut problem to understand the problem's complexity. Let \(G=(V,E)\) be an undirected graph, where \(V\) is the node set, and \(E\) is the edge set. In the graph, each edge \(e_{u,v}\in E\) has a non-negative weight \(w_{u,v}\). A k-cut in graph \(G\) is a set of edges, which when removed, partition the graph into \(k\) disjoint nonempty components \(G^{\prime}=\{G_{1},G_{2},...,G_{k}\}\). The minimum k-cut problem is to find a k-cut of minimum total weight of edges whose two ends are in different components, which can be computed as:  
\[\sum_{i=1}^{k-1}\sum_{j=i+1}^{k-1}\sum_{ \begin{subarray}{c}u\in G_{i}\\ v\in G_{j}\end{subarray} }w_{u,v} \tag{5}\]  
A minimum cut is a simply minimum k-cut when \(k=2\). Figure 1 shows an example of a minimum cut of a graph. There are 2 cuts shown in the figure, and the dash line is a minimum cut of the graph, as the total weight of edges cut by the dash line is the minimum of all cuts. Given a service-based application, we can represent it as a graph, where the nodes represent services and the weights of edges represent the traffic rate. Specifically, the traffic rate from service \(s_{i}\) to service \(s_{j}\) and the rate from service \(s_{j}\) to service \(s_{i}\) are represented as two edges respectively in the graph. Hence, finding a minimum k-cut of the graph is equivalent to partitioning the application into \(k\) parts while keeping overall traffic between different parts to a minimum. However, for arbitrary \(k\), the minimum k-cut problem is NP-hard [10]. Different from developing a deterministic algorithm, [PERSON]'s algorithm [12] provides an efficient randomized approach to find a minimum cut of a graph. The basic idea of the [PERSON]'s algorithm is to randomly choose an edge \(e_{u,v}\) from the graph with probability proportional to the weight of edge \(e_{u,v}\) and merge the node \(u\) and node \(v\) into one (called edge contraction). In order to find a minimum cut, the algorithm iteratively contracts the edge which are randomly chosen until two nodes remain. The edges that remain at last are then output by the algorithm. The pseudocode is shown in Algorithm 1. ```
Input:\(G=(V,E)\) Output: A cut of \(G\) while\(|V|>2\)do
2 choose an edge \(e_{u,v}\) with probability proportional to its weight;
3\(G\gets G/e_{u,v}\) ; // contract edge \(e_{u,v}\)
4 end while return the cut in \(G\);
```  
**Algorithm 1**Contraction Algorithm (\(k=2\))  
Figure 2 shows an example process of the contraction algorithm (\(k=2\)). The algorithm iteratively merges two nodes of the chosen edge, and all other edges are reconnected to the merged node. For a graph \(G=(V,E)\) with \(n=|V|\) nodes and \(m=|E|\) edges, [PERSON] [12] argues that the contraction algorithm returns a minimum cut of the graph with probability \(\Omega(1/n^{2})\). Therefore, if we perform the contraction algorithm independently \(n^{2}\log n\) times, we can find a minimum cut with high probability; if we do not get a minimum cut, the probability is less than \(\Omega(1/n)\). For minimum k-cut, the contraction algorithm is basically the same, except that it terminates when k nodes remain (change \(|V|>2\) to \(|V|>k\) in Algorithm 1) and returns all the edges left in the graph \(G\). Similarly, the contraction algorithm returns a minimum k-cut of the graph with probability \(\Omega(1/n^{2k-2})\). If we perform the algorithm independently \(n^{2k-2}\log n\) times, we can obtain a minimum k-cut with high probability.