Efficient Resource Discovery in Grid Environments

Abstract

Grid Computing has evolved into an important discipline by differentiating itself from distributed computing through an increased focus on resource sharing, coordination, manageability and high performance. Grid computing combines open, shared, geographically distributed and heterogeneous resources to achieve high computational performance. The objective of the Grid Computing is to solve large problems which can not be solved by single CPU by achieving high computing performance by optimal use of geographically distributed heterogeneous idle resources. These resources may belong to different institutions, different domains; may have different usage policies and may pose different requirements on acceptable requests. One of the major challenges in such highly heterogeneous and complex computing environments is to design efficient Resource Discovery algorithms. Resource Discovery strategies in such cases should be efficient, robust, and scalable. Resource heterogeneity domains, dynamic load on resources, task runtime prediction uncertainty, task-to-resource ratio and resource sharing in the grid environment affects application performance. Grid resources are heterogeneous due to differences in hardware components, differences in Grid software environments, and due to the fact different administrative have different policies for sharing the resources. This work mainly focuses on “Efficient Resource Discovery with heterogeneous resources”. Initially, an in-depth review of existing models, approaches and algorithms has been done. During the literature review, it is observed that query based, agent based, parameter based and ontology based approach are some of the existing approaches. Flooding algorithm, swamping algorithm, name-dropper algorithm and kutten peleg algorithms. Three models; push, pull and push-pull models are currently being used for Resource Discovery process. A comprehensive study of different middleware also has been done. Different QoS parameters have been identified and analyzed as: Time, Cost, Reliability and Security. Time is the measure of delivery period of resources. Cost is the amount payable for using the resource or a set of resources including communication cost and computation cost. Penalty cost is included in case of delay in delivery of the resources required. Communication and computation costs are other costs. Reliability is about making delivery sure for a resource or a set of resources. Security is a mechanism for ensuring the trust while sharing or exchanging a resource among users or users and manager. Three algorithms have been proposed for Resource Discovery namely: “Path Optimization Algorithm, “Weight Optimization Algorithm and “Request Matching Algorithm”. Path Optimization Algorithm is based on the concept of “connected graphs” and their trees. This algorithm optimizes the path traversed for the Resource Discovery process. Weight Optimization Algorithm is based on the concept of directed weighted graph and it optimizes the total cost/total time needed for Resource Discovery process. A method of parallelizing both these algorithms is also described in detail. Request Matching Algorithm is designed based on the ontology approach and it finds the best resource from a set of all matching resources for a given job. It works with the three matchmaking principles. First - to find the acceptable matches; second - to supervise and modernize lists of the requester and provider and third - dynamically create the data updating in the resource pool, for finding the acceptable matches. Complexity analysis as well as comparative analysis of all the three algorithms has been made. To test and validate the proposed algorithms, a customized testbed has been developed as part of this work, namely TUGrid testbed. It has been used to demonstrates the usefulness of this work. Different test cases including different parameters for the Resource Discovery process have been considered for the evaluation of the proposed algorithms. The results clearly demonstrate that the approach is workable and can be effectively used to address the different QoS requirements including Time, Cost, Reliability and Security.