Economic Algorithms for the Management of Resources in Computer Systems

Abstract

Cloud computing and distributed Grid computations in the e-science and commercial spheres are beginning to make accessible huge amounts of computing power with “just in time” availability. However, the economic models surrounding these systems are static and uniform, with charging models that, for web-based cloud systems work on a price per unit per hour basis, whilst for educational type resources, fixed contractual arrangements and multi-year projects are more prevalent. The common place practice of using just-in-time capacity planning and variable pricing algorithms, such as those pioneered by airlines like EasyJet, tells us that the cost of delivering these services and the price that should be paid for them is a much more complex beast. Future Grid and Cloud Computing computations will be enabled by participants trading resources in order to construct bundles of goods or services in both new commercial arenas and the more well established “e-science” experiments in science, engineering and, now emerging, social sciences. A combinatorial auction (CA) is a natural choice for determining the optimal allocation for a bundle of required goods and services, but the space and time dimensions that characterise a Grid compute cloud would appear to indicate they are incompatible. This thesis proposes that an analogue of a physical commodities market is more appropriate for distributed resource allocation and that there is a class of bundling problems whose complexity properties appear to make the utilisation of a CA impractical. We therefore compare the two techniques for resource bundling and investigate the crossover point, to enrich our understanding of how combinatorial auctions and distributed markets may be used together to improve distributed resource allocation practices.

Date of Award	1 Oct 2009
Original language	English
Awarding Institution	University of Bath
Supervisor	Julian Padget (Supervisor)