Algorithms and Market Design for Resource Allocation in Cloud Computing Systems
Creators: name: Narayana, Sushirdeep
Publisher: name: University of Illinois Chicago
Year: 2025

description: Over the past several years, cloud computing resources have been allocated and priced using simple approaches. On the allocation side, even though users in cloud computing systems demand multiple resource types, the allocation has been typically done using a single resource abstraction. On the pricing side, most cloud resources have been sold using pricing schemes resembling resources whose usage can be measured like water, natural gas or electricity. This thesis dissertation involves the design and development of algorithms, mechanisms, and market design to enable fairer and more efficient solutions to the problems faced by cloud providers around the themes of allocation of multiple resources and managing future demands of a customer.

First, when considering resource allocation, we investigated the fair division of multiple resources among agents with Leontief preferences where each agent has a finite amount of work to complete. This setting was termed as limited demands. The Least Cost Product (LCP) mechanism was proposed which is the counterpart of the Maximum Nash Welfare solution in this setting. We characterized the structure of LCP allocations and prove that it is Pareto optimal, and that it satisfies relatively weaker fairness properties when compared to Dominant Resource Fairness allocations. Experimental simulations suggest, however, that the violations of fairness guarantees in LCP allocations are rare in randomly generated examples.

Second, we investigated the problem of managing the future demands of a customer as a keep- alive caching problem where there is a cost associated with the time an object is kept in the cache. We drew motivation from serverless computing and explored keep-alive caching policies. The standard policy in serverless systems like Amazon Lambda, Microsoft Azure Functions is to use the fixed keep-alive window to keep a serverless application active. We characterized the optimal keep-alive caching policies in this framework and derived a closed form for the Hawkes process and Poisson process. Performances of the optimal, approximate, and fixed keep-alive policies were evaluated on a data-trace of Azure Functions, Microsoft’s Function as a Service serverless platform.

Finally, we explored custom keep-alive cache policies based on individual customer utilities rather than cache policies based on a system average performance. We assume each customer submits a bid for a preferred cost of a cold start (cache-miss) for her application. We design and develop cache allocation policy based on online learning from a mixture of fixed allocation experts. We show that our custom policy is efficient and monotonically non-increasing with respect to the submitted bid. We examine two payment schemes to achieve incentive compatibility. In the first payment scheme, the customer's are charged based on Myerson's optimal auction design theory, whereas in the second payment scheme the customer's pay their externality as in VCG mechanisms. We show via experimental simulations that the revenue generated by the two payment schemes comes close to recovering the costs, while being approximately incentive compatible.