Ahab: Data-Driven Virtual Cluster Hunting

Virtual clusters are an important concept to provide isolation and predictable performance for multi-tenant applications in shared data centers. The problem of how to embed virtual clusters in a resource efficient manner has received much attention over the last years. However, existing virtual cluster embedding algorithms typically optimize the embedding of a single request. We demonstrate that this can lead to fragmentation and suboptimal data center resource utilization over time. We propose an alternative in two stages: First, we describe a novel embedding algorithm, called Tetris, which, in an effort to avoid resource fragmentation over time, takes into account the specific node-to-link resource ratios of the individual requests. While Tetris can be suboptimal when embedding only one request, we find that it performs much better than the state-of-the-art algorithms over time. Second, we allow the algorithm to strategically reject individual requests, even if there are sufficient resources: our proposed algorithm, Ahab, hence selects ("hunts") useful requests over time. An important property of Ahab is that it is data-driven: it uses information about previous requests and embeddings. We report on extensive simulations, which demonstrate the optimization potential of Tetris (+4%) and Ahab (+13%), compared to existing solutions such as Kraken and Oktopus. Furthermore, Ahab illustrates how data-driven algorithms can replace man-made heuristics.