Cloud computing has proliferated as the new computing paradigm that provides flexible, on-demand computing services in a pay-asyou-go fashion. Given fixed cloud resource capacity, a fundamental problem is to determine which user demands to satisfy at each time point, for maximizing the social welfare of the cloud eco-system. Such cloud resource allocation in practice requires online decision making upon arrivals of job requests. A natural, de facto standard here is a posted pricing mechanism: the cloud provider publishes resource prices; cloud users act as price takers who accept/reject the cloud service by comparing the prices with their job valuations. Major cloud providers today typically post fixed prices, while dynamic pricing based on realtime demand-supply could be an more efficient alternative [1] . Since the Spot Instances model in Amazon EC2, various dynamic pricing strategies have emerged, including auction mechanisms [6, 8, 9] , and other dynamic pricing strategies for revenue maximization and efficient cloud resource utilization [4, 7] . This work studies effective pricing functions for a cloud provider to employ, for computing unit resource prices at each time point. Our study of the pricing functions has been partly inspired by dual price design in competitive online algorithms based on the classic primal-dual framework [2] . A key idea there is to update dual prices using exponential functions for making primal resource allocation decisions, leading to provable competitive ratios. Nonetheless, no explicit justifications were provided in the literature on the choice of using exponential dual price functions. We first study the basic case of a single type of cloud resource without resource recycling, and design resource pricing functions based on the current resource utilization levels that capture realtime demand-supply of cloud resources. We prove the optimality of our pricing function design. We then investigate the cases of multiple resource types, and limited resource occupation durations. Our contributions include: First, we justify the use of exponential pricing functions in the literature of both cloud computing [5, 8, 9 ] and online algorithms [2], both from a theoretical point of view and with intuitive interpretation. We prove the optimality of the exponential pricing function. * The full version of the paper is available at https://arxiv.org/abs/1704.05511 Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). Second, we construct optimal pricing functions for more realistic cloud resource allocation scenarios, where the potential total demand of resources is bounded. Interestingly, this result also contributes to the literature on knapsack problems, in that our problem is closely related to a variant of the online knapsack problem [3, 10] , where the total weight of items is upper bounded. Third, we extend the pricing functions to take into account multiple resource types. We propose a joint pricing and scheduling strategy over multiple time slots. We further prove tight competitive ratios for these scenarios. We further verify effectiveness of our price design in realistic cloud computing scenarios using simulation studies, relaxing assumptions made in the theoretical analysis. Finally, we note that our pricing models and algorithms are generally applicable to posted pricing mechanism design in other online resource allocation systems, which share similar characteristics as a cloud computing system.  KEYWORDS
Zhang et al. REF compute posted prices for cloud resources by designing exponential pricing function based on the primal-dual framework for 0-1 Knapsack problem.
Optimal Posted Prices for Online Cloud Resource Allocation
SIGMETRICS '17 Abstracts
Computer Science