Distributed Scheduling For A Class Of Service Grid Systems

In a service grid, multiple kinds of grid services can be deployed on each server node, and the grid user authorized may invoke a grid service on a remote server node by accessing the standard interface provided. The resources on which a server resides may not be dedicated on grid services, and provide a higher priority to the local user's tasks which can not be migrated. Due to the heterogeneity of their capabilities, different servers may respond to the same grid service request in a different time. Therefore, grid service requests could be scheduled to migrate from their submitted server nodes to other servers to minimize the total response time.The thesis focuses on the optimal distributed scheduling process in such a service system. A scheduling model for optimizing the whole average response time of all the grid service requests using probability statistics are established at first. Then a coordinating algorithm is designed to solve the optimization problem distributedly in which the optimal solution is approached through iterative coordination between neighbored servers. To enhance the performance of the service requests 'redistribution process, the overlay network organizing server nodes in the system are optimized and a new model overcome the negative influence of the heterogeneity is proposed. The distributed scheduling system discussed in this paper is simulated using GridSim, and the results are presented.The main contents are composed of the following four parts.(1) An optimal grid service requests scheduling problem is established extending K.Li's single-class grid service model to a multi-class grid services model which is more applicable in service grids. To schedule service requests distributedly, the server nodes are organized in an overlay network underlying on the physical communication network. The probability a service request is migrated from a server node to its neighbor nodes is optimized according to the solution of the optimal scheduling problem and the minimal transferring problem. The model is validated by simulation that the requests scheduling process based on the model can enhance the system performance and implemented distributedly. Service requests can be accepted in a few hops if the overlay network is designed properly.(2) A coordinating policy is designed to solve the optimal scheduling problem distributedly. The server nodes coordinating with their neighbors under the control of the policy can approach the optimal acceptance rates of service requests. Whenever the coordinating process is halted, the servers' request acceptance rates can be set based on the current coordination states. It is expectable that the system performance can be enhanced. The coordinating policy can be generalized to solve other separable convex problems like the optimal scheduling problem.(3) The influence of the overlay network on the scheduling process is analyzed and the overlay network is optimized in two aspects. One aspect is rearranging the position of server nodes in the overlay network. The optimal servers' sorting problem is defined, and a heuristic algorithm is proposed. The server with the highest capability is placed on the node with the highest betweenness value and so do the remaining servers. The simulation results can support the heuristic algorithm. The other aspect is to optimize the topology of the overlay network. A new network model is proposed based on the OSN model to overcome the negative influence of the incapability server node on coordinating process by putting them on less important positions. The model is analyzed theoretically and by simulation.(4) Some problems such as organizing server nodes according to an overlay network model, establishing virtual connections, and dealing with withdrawal server nodes are discussed. The service request scheduling process in a service grid is simulated in GridSim, an event-driven grid scheduling simulation environment developed in Java. The behaviors of server node's connecting to the overlay network, coordinating with neighbors and transferring service requests are simulated. The optimal distributed scheduling model, the influence of random entrance/withdrawal of server nodes, and the inaccuracy of probability statistics on the system performance are evaluated in the simulated environment.