M.Sc Thesis

M.Sc StudentYoshpa Bennyamin
SubjectEconomic Aspects of QoS in Grid Computing
DepartmentDepartment of Computer Science
Supervisors PROF. Ariel Orda
PROF. Assaf Schuster
Full Thesis textFull thesis text - English Version


Grid resources are usually shared among multiple organizations and typically managed in a “best effort” manner. However, many real-world supercomputing applications, such as weather forecasting and complex system simulations, rely on co-allocation of large numbers of reliable resources making such “best effort” Quality of Service inadequate.

While a supercomputer may be described as a single entity that has control over its resources, Grids usually consist of heterogeneous clusters belonging to different administrative domains. These administrative domains are selfish entities: each tries to maximize its own utilization of resources while disregarding the need to share them with others unless given a proper incentive. Thus, Grid systems are often unpredictable in terms of future resource availability, making it difficult to plan resource utilization in advance.

We demonstrate that incentive mechanisms are required if we are to achieve more than opportunistic QoS with regard to the resource allocation process in the Grid. Specifically, we investigate the problem of distributed automatic resource co-allocation in the presence of selfish resource providers. We develop a formal model of the problem in a setup in which each provider has multiple resource items and each consumer has a single resource choice. We establish the computational intractability of the problem, and, moreover, the computational hardness of approximate solutions. To deal with this problem, we present several distributed resource negotiation algorithms based on heuristics that solve the co-allocation problem under economic constraints.

We show by the means of simulation that system-wide economic efficiency may be achieved without the need of a central entity. Finally, we discuss the design and implementation of this economic sub-system in the QosCosGrid EU project.