New Mechanism for Reservation in Cloud Computing

In this paper, we study the problem of designing new mechanism for selling reserved instances in cloud computing. Our goal is to maximize the social welfare. We propose a prompt mechanism in the sense that the acceptance and the payment for a job is determined at the very moment of its arrival. We show that the mechanisms has a competitive ratio of O(ln(kT)) under some mild assumption, where k (res. T) is the maximum ratio between per-instance-hour valuation (res. length) of any two jobs. We then prove that no algorithm can achieve a competitive ratio better than ln(2kT) under the same assumption. Therefore, our mechanism is optimal within a constant factor.