Selling reserved instances in cloud computing

摘要: In this paper, we study the problem of designing new mechanisms for selling reserved instances (also referred to as virtual machines) in cloud computing. Unlike practice today's clouds which users only have a few predefined options reserve (i.e., either 1-year reservation or 3-year reservation), allow resources any length and from time point future. Our goal is maximize social welfare. We propose two mechanisms, one case where all jobs are tight (their lengths exactly their intervals), other more general delayable some flexibility on reservations. Both prompt sense that acceptance payment job determined at very moment its arrival. use competitive analysis evaluate performance our show both ratio O(ln(kT)) under mild assumption, k (res. T) maximum between per-instance-hour valuation length) jobs. then prove no algorithm can achieve better than ln(2kT) same assumption. Therefore, optimal within constant factor.