Research Of Grid Scheduling Model Based On Cooperative Game

Grid Computing is one of the hotspots in the research of Internet,and it is also a direction in developing parallel and distributing computing. Grid is a compositive computing and resource environment,which contains all kinds of computing resources,and make them to be an environment which has reliable, standard and ecomonic computing capability.Grid provides services for the users of resources by gathering the dispersive and free resources,this leads to a benefit relationship between buyers and sellers in economic society,so someone brought forward an idea to solve the problem of the grid task scheduling and resources using through the economic modules.Now that we research the grid from economic point,we must not only protect the benefits of the resources providers,but also protect the benefits of the resources users,including costs,task deadline,we also have to solve the conflicts between resources providers,for example,how to avoid the vicious bid between the providers because of fierce competing, to avoid Nash balanceof noncooperative games,to avoid monopolization of the market,they are all what we have to research.This thesis researches the development of the grid,and the grid scheduling modules.Most of these economic grid scheduling modules are noncooperative,resources providers don't work together,so in this thesis,we import the concept of cooperative game and brand value,and use the Tendering/Contract-Net Model for reference,design and implement a scheduling module and an algorithm,also have discussed the content and meaning of the research.This thesis includes the following contents:1.Introducing cooperative game,and discuss the possibility of the cooperation in the grid platform,also discuss how to buildup a union,and after union allocate tasks and benefits by calculating Shapley to form a steady union.2.Importing the concept of cooperative game and brand value.Resource providers work together according the predefined rules.The central scheduling module assign a task to a union according the assignment value Factor ,then the union allocate task to the members of the union.3.According the concept brought up above,we design and implement an autonomic algorithm based on cooperation game.This algorithm allocate task according brand value,current capacity proportion and assurance ratio provided by providers,every provider all can get benefit which is good load balance.If the task can not be completed on time,the node will be punished.4.Implement the module and the algorithm,add these to globus,and return the task result.The second and the fourth chapter have described the module very detailedly.This module includes seven parts,module to query information which contains task information and resource information,module to maintain a union,module to schedule tasks,module to get instant information,module to allocate tasks to union,module to allocate tasks to members,module to allocate benefits.Grid users submit tasks to scheduling center through the web;scheduling center get dynamic information from instant information module,and it also get brand value,then according the algorithm to calculate the allocation value Factor,and select max{Factor} union,give it to task allocation module;task allocation module prepare for task submitting,and then submit the task to the target union,and monitor the execution situation,for example,load and makespan;the the union splits the task and allocates subtask to members of the union according Shapley value; if the task is completed in time,set pride factorα,and increase the brand value,if the task can't be finished in time,set punishment factorβ;user information querying module get result from other modules or datebase,and return the results to the clients.The fourth chapter described the algorithm.This algorithm allocate a task using allocation value Factor,the value is bigger,the probability is bigger.Allocation value is composed of brand value Va,assurance ratio As and current capacity proportion Cd.Brand value is decided by history records,if a task is completed in time and in quality,the algorithm will encourage the node using pride factor,and the brand value is bigger,but if the task is not completed in time and in quality,the algorithm will punish the node using punishment factor,and the brand value is smaller;the capability proportion is ratio of probability of current capacity divided the probability of current load,the value more bigger,the ratio be allocated is much bigger;assurance is a kind of prediction whether the task can be allocated to that node according the history information of the node and the task information,the most important factor is the estimate of the ETC(excution time to compute).In this thesis,we build up a grid environment and implement the module,apply this algorithm to the module,we also test and evaluate the algorithm,the result shows it can balance load between all the nodes in a real grid environment,it also result in a fair and reasonable competition.It points out the shortage of the algorithm and system at the last thesis, such as to improve ETC-expecting model and the direction of the scheduling module and how to buildup a much bigger union,and make an organization work together with another one,to enable the system to work in a heterogeneous ,multi-tasktypes environment, and to enhance security of the system.