Research On Grid Scheduling

Grid computing, which emerged during the early 1990s in USA, has madegreat strides during the late 1990s and early 2000s. Now it has been becoming animportant research area in distributed computing, and is expected to continue toflourish in the new millennium.Scheduling is one of key issues in computing grid, offering a way of efficientlyusing grid resources. Among all challenges in grid scheduling, we study two ofthem in this thesis: the first one is herd behavior in scheduling, and the secondone is the tough problem of handling efficiently the communications whenscheduling a parallel-job.In order to avoid the herd behavior, based on the balls-and-bins model andthe techniques of DHT and data replication, we propose a novel stochasticscheduling algorithm. Our simulation results show that this new stochasticalgorithm can effectively prevent herd behavior, and provide much betterperformance both on the scheduling overhead and job turn-around time thanconventional ones.On the other hand, for the tough problem of handling efficiently thecommunications in scheduling, we struggle to partition resources into sites, whichcan be considered as "parallel machines", to isolate communications fromscheduling. In this thesis, we use flooding with a limited TTL(Time-To-LIVE) toexploit the proximity property between resources, and partition resources intogroups in a parallel & distributed fashion. Our simulation results havedemonstrated the validity and rationality of this method.