Optimal Online Balanced Graph Partitioning

Distributed applications generate a significant amount of network traffic. By collocating frequently communicating nodes (e.g., virtual machines) on the same clusters (e.g., server or rack), we can reduce the network load and improve application performance. However, the communication pattern of different applications is often unknown a priori and may change over time, hence it needs to be learned in an online manner. This paper revisits the online balanced partitioning problem that asks for an algorithm that strikes an optimal tradeoff between the benefits of collocation (i.e., lower network load) and its costs (i.e., migrations). Our first contribution is a significantly improved deterministic lower bound of Ω(k · ℓ) on the competitive ratio, where ℓ is the number of clusters and k is the cluster size, even for a scenario in which the communication pattern is static and can be perfectly partitioned; we also provide an asymptotically tight upper bound of O(k·ℓ) for this scenario. For k = 3, we contribute an asymptotically tight upper bound of Θ(ℓ) for the general model in which the communication pattern can change arbitrarily over time. We improve the result for k = 2 by providing a strictly 6-competitive upper bound for the general model.