City Research Online

Abstract

Recently, there has been much interest in Computational Grids which provide trans-parent access to large-scale distributed computational resources. One key issue in these open and heterogeneous environments is the efficient allocation of resources. Clients and service providers belong to different organisations and have different priorities, requirements, and goals, making resource management a complex task.

Economic approaches to resource allocation can offer a solution, as they are naturally decentralised, and as decisions about whether to consume or provide resources are taken locally by the clients or service providers. The use of currency offers incentives for service providers to contribute resources, while clients have to act responsibly due to their limited budget. To maximise the benefit of the clients, it is essential to choose an appropriate resource allocation protocol. There exist various economic protocols with different properties, however, their performance in Grid settings has not yet been sufficiently studied.

In this thesis, we review and classify existing work on market protocols in computational clusters and Grids. We then develop a simulation model of an electronic marketplace and evaluate several market protocols for different computational environments, task loads, and optimisation requirements of the clients. We study situations, in which the tasks are independent and arrive randomly. Three scenarios are examined in which the clients have different requirements concerning the execution of their tasks. In two scenarios, the completion times of the tasks need to be minimised. In the first one, all tasks are equally important, whereas in the second one, they have different values for the clients and are weighted accordingly. In the third scenario, tasks have different priorities combined with hard or soft deadlines which need to be met in order to deliver maximum value to the clients.

The resource allocation protocols, which are evaluated, include continuous double auctions (CDA), periodic double auctions (PDA), and a proportional sharing protocol (PSP). Also, several pre-emptive protocols, with and without task migration, are investigated, as well as protocols, in which the service providers are allowed to set reserve prices. The simulation results reveal that the choice of the protocol should depend on the optimisation requirements of the clients, the number of resources in the system, the heterogeneity of these resources, the amount of load and background load in the system, the local scheduling policy at the resources, and the communication delays. We found that, in most situations, CDA leads to very good results. However, with high heterogeneity and load, it can be outperformed by PDA, PSP, and the pre-emptive protocols without migration. Also reserve prices can lead to performance improvements. In most cases, the best results are achieved by pre-emptive protocols which allow migration.

To verify our simulation model and thus our results, we developed a basic Grid computing infrastructure, that is based on the model, and carried out experiments in a local area network. We also demonstrated the effectiveness of our infrastructure for solving real-world problems by deploying a computationally intensive bioinformatics application.

Publication Type:	Thesis (Doctoral)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science School of Science & Technology > School of Science & Technology Doctoral Theses Doctoral Theses

Export

Downloads