A large-scale service system with packing constraints: Minimizing the number of occupied servers

We consider a large-scale service system model proposed in [14], which is motivated by the problem of efficient placement of virtual machines to physical host machines in a network cloud, so that the total number of occupied hosts is minimized. Customers of different types arrive to a system with an infinite number of servers. A server packing configuration is the vector k = {ki}, where ki is the number of type-i customers that the server "contains". Packing constraints are described by a fixed finite set of allowed configurations. Upon arrival, each customer is placed into a server immediately, subject to the packing constraints; the server can be idle or already serving other customers. After service completion, each customer leaves its server and the system. It was shown in [14] that a simple real-time algorithm, called Greedy, is asymptotically optimal in the sense of minimizing Σ_k X_k^1+α in the stationary regime, as the customer arrival rates grow to infinity. (Here α > 0, and X_k denotes the number of servers with configuration k.) In particular, when parameter α is small, and in the asymptotic regime where customer arrival rates grow to infinity, Greedy solves a problem approximating one of minimizing Σ_k X_k, the number of occupied hosts. In this paper we introduce the algorithm called Greedy with sublinear Safety Stocks (GSS), and show that it asymptotically solves the exact problem of minimizing Σ_k X_k. An important feature of the algorithm is that sublinear safety stocks of X_k are created automatically - when and where necessary - without having to determine a priori where they are required. Moreover, we also provide a tight characterization of the rate of convergence to optimality under GSS. The GSS algorithm is as simple as Greedy, and uses no more system state information than Greedy does.