Title: Collocation Games And Their Application to Distributed Resource Management
Authors: Jorge Londono, Azer Bestavros, and Shanghua Teng
Date: February 7, 2009
Abstract:
We introduce Collocation Games as the basis of a general framework for
modeling, analyzing, and facilitating the interactions between the
various stakeholders in distributed systems in general, and in cloud
computing environments in particular. Cloud computing enables
fixed-capacity (processing, communication, and storage) resources to
be offered by infrastructure providers as commodities for sale at a
fixed cost in an open marketplace to independent, rational parties
(players) interested in setting up their own applications over the
Internet. Virtualization technologies enable the partitioning of such
fixed-capacity resources so as to allow each player to dynamically
acquire appropriate fractions of the resources for unencumbered
use. In such a paradigm, the resource management problem reduces to
that of partitioning the entire set of applications (players) into
subsets, each of which is assigned to fixed-capacity cloud resources.
If the infrastructure and the various applications are under a single
administrative domain, this partitioning reduces to an optimization
problem whose objective is to minimize the overall deployment cost. In
a marketplace, in which the infrastructure provider is interested in
maximizing its own profit, and in which each player is interested in
minimizing its own cost, it should be evident that a global
optimization is precisely the wrong framework. Rather, in this paper
we use a game-theoretic framework in which the assignment of players
to fixed-capacity resources is the outcome of a strategic "Collocation
Game". Although we show that determining the existence of an
equilibrium for collocation games in general is NP-hard, we present a
number of simplified, practically-motivated variants of the
collocation game for which we establish convergence to a Nash
Equilibrium, and for which we derive convergence and price of anarchy
bounds. In addition to these analytical results, we present an
experimental evaluation of implementations of some of these variants
for cloud infrastructures consisting of a collection of
multidimensional resources of homogeneous or heterogeneous
capacities. Experimental results using trace-driven simulations and
synthetically generated datasets corroborate our analytical results
and also illustrate how collocation games offer a feasible distributed
resource management alternative for autonomic/self-organizing systems,
in which the adoption of a global optimization approach (centralized
or distributed) would be neither practical nor justifiable.