Flexible Instance: Meeting Deadlines of Delay Tolerant Jobs in The Cloud with Dynamic Pricing

A wide range of cloud computing jobs are delay tolerant up to a predefined deadline. Existing IaaS services offer either high cost and high fulfillment ratio or low cost without fulfillment ratio guarantee, where the fulfillment ratio is the ratio of job execution time to the time between job submission and completion. Neither of the services represents a cost-effective way to exploit job elasticity. This work proposes flexible instance, a cloud service where user-specified service fulfillment ratio, as a new pricing factor, is guaranteed by the provider to meet deadlines. Job elasticity is exploited by the provider to enhance resource utilization, by regulating demand fluctuation through computation arbitrage across the temporal domain. We leverage a two-stage pricing framework to agilely adapt cloud resource price to the demand-supply dynamics. The first stage uses an online strategy to reserve resources for each cloud user to guarantee its specified fulfillment ratio. We set the price of resources dynamically according to resource utilization, with a pricing curve O(ln p)-competitive to the optimal fixed-price offline strategy in provider revenue. The second stage allows cloud users to submit a small budget to compete for extra service fulfillment ratio for execution speedup. A Nash bargaining framework is explored to achieve fairness, resource efficiency, and revenue maximization simultaneously. Extensive simulations driven by real-world traces show that flexible instance can reduce user cost for job execution while increasing provider revenue.