Research On Quality Of Service Guarantees In Grid Task Scheduling

Grid is an advanced infrastructure of information technology. It aims at efficiently integrating computational resources, storage resources, communication resources and information resources to provide a virtual, uniform and transparent computing envi-ronment for users. The importance of Grid has drawn much attention from many countries and governments and has attracted lots of research. Scheduling grid tasks properly and efficiently can make full use of grid resources, improve system efficiency and satisfy users'applications. Thus, task scheduling has become one of the most im-portant areas of grid research. With the foundation of Open Grid Service Architecture (OGSA), Grid technology has been developing to the "service-oriented" direction and service of quality (QoS) becomes an important factor that should be considered when scheduling grid tasks. Moreover, Ian Foster, "the father of the Grid", takes providing non-trivial QoS as an important judging criterion of grid. Because of the dynamic and autonomous features of grid, it is a hard and challenging problem to guarantee QoS. Though resource reservation is an effective means to provide QoS guarantee, it will cause the problem of "resource fragmentations" and influence the completion of non-reservation tasks. It is meaningful to study how to make use of resource reservations while decreasing their negative impacts. Grid economy provides a general solution for resource management and especially double auction model has been applied to grid resource allocation widely. However, most double auction based resource allocation and task scheduling use the auction theory in economy area directly, only caring about users'economic profit rather than effective QoS guarantee. Recently, service grid is the mainstream direction to construct grid system. In the service grid environment, the scheduler needs to dynamically integrate lots of temporary grid services into com-posite services according to users'immediate requirements. Thus, we need a service scheduling mechanism to realize the matching and composition of grid services and provide users with the required QoS. We have done research on the problems related to QoS guarantee during task scheduling and the actual work develops in two aspects: "planning in advance" and "attention in process". The former is concerned with task scheduling related to resource reservation; the latter focus on how to map the users' QoS requirements into economy based resource allocation and grid service scheduling. The achievements of this paper are as follows.1. A fuzzy grid resource reservation mechanism, FRRM, is put forward. Under tra-ditional resource reservation mechanism the resource allocation happens before the reservation tasks actually use the resources, which can not deal with the dy-namic change of resources during the book-ahead time. FRRM is able to perceive the resource change during the book-ahead time, schedule the accepted reserva-tion requests dynamically according to the resources' run-time information. The resource-reservation graph is introduced to describe the admission control and reservation scheduling strategy under FRRM, and FRRM's fault tolerance to resource error is also studied.2. The scheduling strategies for preemptable and non-preemptable tasks are pre-sented. The former can be obtained by modifying the existing scheduling strat-egy while the latter is modeled as a Multi-line Bin Packing (MBP) problem. Multi2Single algorithm is put forward to transform the MBP problem to a Single-line Bin Packing (SBP) problem. Based on the existing research on the classic BP problem, we put forward heuristics to solve the SBP problem. Moreover, theo-retical analysis and experimental simulation have also been performed to analyze and compare the worse-case and average-case performances of these algorithms. Compared with traditional Min-min and Suffrage, our algorithms can reduce the makespan considerably and buffer the negative impacts of reservation tasks on non-reservation tasks effectively.3. A Greedy Double Auction Protocol (GDAP) is presented to deal with quan-tifiable grid resources and a Qos-enabled Double Auction Protocol (QDAP) is presented to deal with grid services. We have proven that GDAP has the fea-tures of strategy-proof, individual rational and weak budget-balance. Compared with traditional auction strategy based on MDA, GDAP can improve the resource utilization and user satisfaction percentage considerably, in accordance with the large scale resource sharing target of grid. QDAP first introduces QoS into double auction protocol and aims at maximizing the service utilization while providing effective QoS guarantee for consumers. Experiments have been performed to compare QDAP with PMDA and CDA and the results show that QDAP leads to a better auction fairness and a higher service utilization; thus, it is more suitable for the service grid.4. We have researched the service scheduling problem under multi QoS constraints. We use mobile agent as the application carrier and the user's requirements for composite grid services are met through the migration of mobile agent between service instances. A routing algorithm with QoS constraints based on ant al-gorithm for mobile agent (MRBAA) is put forward. MRBAA supports mobile agent's parallel access to grid services and takes into account the data exchange between services. Under MRBAA, the mobile agent migrates in the purpose of maximizing the user's utility while considering the user's QoS requirements. Compared with the fast greedy algorithm and the random selection algorithm, MRBAA outperforms them in the aspects of both successful scheduling percent-age and utility.