UC San Diego
Practical market-based resource allocation
- Author(s): AuYoung, Alvin
- et al.
The arrival of large-scale open platforms such as cloud- computing infrastructures and petascale clusters is fueling the emergence of a new class of users and applications with large and diverse resource needs. Optimizing for traditional system-centric metrics such as response time or throughput does not capture the diverse and often conflicting needs of different users and resource providers. Collaboration between economists and computer scientists over the past ten years has lead to many important results describing designs of market-based mechanisms to address exactly these issues. However, there is very little progress in building these systems due to apprehensions about their potential unfairness and fragility in a live deployment. The resulting reality is that systems continue to rely on traditional and inadequate designs despite theoretical results demonstrating the potentially significant value added to all stakeholders by designing market-based systems. This dissertation investigates the sensitivity, applicability, and practicality of a market-based policy to increase the efficiency of resource allocations --- measured using a utilitarian social welfare metric --- in real, large-scale computing systems. We build upon previous work in this space by moving beyond "paper designs'' and using an iterative process of implementation, deployment, measurement, modeling and simulation. We begin by presenting Mirage, our implementation of a microeconomic resource allocation system for a sensor network, which is still in use today. In this context, we identify the compromises that deployed market-based systems must make when using traditional theoretical designs due to computational challenges and various imperfect conditions of a live deployment. Nonetheless, based upon user data, we find that these systems are still expected to be robust to typical user errors seen in traditional computing systems. We also describe extensions of existing designs to address some of these limitations. Finally, we discuss our experience with deploying systems with real users and applications and conclude by discussing the forthcoming challenges in pushing more widespread adoption of these market-based designs in real systems