Research On The Key Technologies Of Resource Management And Scheduling Algorithms Over Grid Environment

Developments in computational infrastructure and networking technology make it possible to construct Grid computing environments to meet the increasing requirement on computational power. To construct such a grid system, resource management and scheduling over grid environment are very important due to the dynamic, heterogeneous and autonomous characteristics of grid resources.Grid resource providers and consumers could have P2P characteristics, such as dynamic, heterogeneous, autonomous, and et al. So, it is necessary to introduce P2P theory into grid resource management and scheduling field. In this dissertation, we present the idea with a series of mechanisms and algorithms.Grids can be classified into two kinds: one is the specialized grid, such as traditional computational grid; one is the universal grid, such as grid systems based on web services and OGSA. Our research results are applicable to both of these grids.Based on the analysis of current resource management and scheduling approaches over grids environment, this dissertation focuses on several critical research issues, including architecture of the grid systems, resources description methods, resource management and scheduling algorithms and system load balance. To verify the effectiveness of the models and algorithms proposed, comprehensive experiments have been carried on an experimental grid platform, Drug Discovery Grid (DDGrid), which provides a convenient and effective computing infrastructure for drug discovery and design applications by utilizing heterogeneous resources donated by the clusters and personal computers scattered over the Internet. The main contributions of the thesis can be summarized as follows:1. Based on the characteristics of grid environment, P2P theory has been introduced into the grid resource management and scheduling. Super node P2P network based architecture has been designed for grid resource management and scheduling, which takes advantages of both the central and distributed resource management models. Thus it can not only reflect the dynamic and autonomous characteristics of grid resources very well but also solve the single point failure and performance bottleneck ness problems caused by centralized models. Moreover, this resulted super node P2P network based grid architecture can make a grid system robust, self-adaptive. Also it can optimize the resource management and scheduling approaches. Furthermore, an overly network topology with IP layer's routing information which is presented with a directed graph is formed. Those nodes carry the routing information of the resource providers and edges express the connections of the nodes. The directed graph can represent the computational resources of a grid node accurately and resolve the problem in current resource description models that the overlay network cannot reflect the IP level information. Also, this efficient and simple method can facilitate the relationship analysis between grid resource providers and consumers.2. For the traditional specialized grid system, a resource scheduling algorithm nTreeMatch has been proposed. Using a DAG to describe a grid task, nTreeMatch algorithm solves the resource scheduling in a matching way between two types of data structure, a tree and a graph. The nTreeMatch algorithm utilizes the routing information supplied by the overlay network topology to decrease the routing cost and enable the hops on the overlay network be as closer as possible on an IP level. In this way, the RDP of the algorithm can be decreased. It has been verified that in a large scale grid system, the nTreeMatch algorithm is a good balance solution between routing state and efficient algorithm.3. For the web service based universal grid system, a resource discovery based grid resource scheduling algorithm GChord has been proposed. Concerning the dynamic characteristics of grids, GChord sends resource requirements over the whole overlay network. As a result, the resource scheduling problem has been translated into the resource services discovery problem. Dynamic schedule and load balance can be achieved. Moreover, problems such as information out-of-date and task rescheduling can also be solved.4. To cope with the dynamic load balancing challenges to grid resource scheduling, the rwAgent algorithm has been proposed. Using the multi-agent theory, this algorithm makes full use of the autonomous and intelligent learning characteristics of the agents. It can not only schedule computational resources dynamically but also get a good load balance state at the same time. Theoretic analysis and experiments have shown the effectiveness of our methods.