Application-System Balanced Optimization Methods For QoS-based Scheduling In Grids

With Grid technologies progressing towards a commercial and service-oriented paradigam, research focus is shifted to investigate how to ensure Grid to provide non-trivial Quality of Service (QoS). QoS guarantee in Gird makes a clear distinction between user's metrics and system's metrics. The existing QoS-oriented scheduling approaches usually are dedicated to certain user's criteria or only pursuit system-centric performance criteria. To this end, it is urgent to design a reasonable, effiecient and fair scheduling approach which could satisfy users'QoS demands and also meet systems'internal requirements. Therefore, QoS-based application-system balanced optimization scheduling in Grids becomes an important issue with theoretical and practical value.The characteristics of Grid QoS such as diversity and interplay bring up great challenge for QoS-oriented schechduling, especially sometimes QoS of user and system conflict. In order to guarantee and improve the QoS requirements of user and system in Grid environment, analyzing current user's most concerned criteria including time and cost, and aiming at system's criteria including workload fairness and global benefit which is usually the most important criteria in economy theory, this thesis deeply investigates efficient and effective Grid application-system balanced scheduling mechanisms. The main research content and contributions are as follows:1. Balanced-based optimization strategy for scheduling general Grid applicationAccording to the fact that QoS requirements of user and system usually remain conflicts, a sequential-game-based balanced optimization scheduling scheme which optimizes the criteria of application's finishing time and Grid system's workload fairness, is presented. SGPUBO gets scheduling solution in a sequential game, which is turned into an iteration of activity distribution and processor allocation. In the first phase, activities'exectuted performances are compared among different sites, and in the second phase, processors are allocated on the basis of the conditions of admitting activities at each site. The simulation experimental results show the allocation concentration tendency of SGPUBO. Applying Tail Migration strategy, SGPUBOwTM is proposed which could achieve better performance on makespan. Comparised with two traditional leading algorithms Min-Min and Sufferage on performance, SGPUBOwTM leads to better application time and system load fairness in an efficient way.2. Balanced-based Optimization strategy for scheduling workflow applicationConsidering the fact that traditional workflow preprocess scheme DBL, which allocates the total time float by an equal means, could lead to waste of Deadline Remaining, an uneven slack deadline assignment scheme based on DBL(DBL_UnevenExt) scheme is proposed. The DBL_UnevenExt algorithm makes choises of Deadline Remaining allocation based on Performance Cost Ratio Distance and Time Requirement Distance between Service Levels. The experimental results indicate that DBL_UnevenExt could enlarge cost optimization intervals of activities by allocating the Deadline Remaining to the more suitable activity. Based on workflow preprocess with DBL_UnevenExt, a novel approach called DBLUCUBO is proposed to realize workflow balanced optimization aiming of minimzing application cost and system workload fairness. The approach makes Full-ahead-planning for every subworkflow based on sequtial game scheme in Just-in-time mode. The experimantal results show that DBLUCUBO could optimize the cost of workflow application and improve fairness of grid system.3. Balanced-based Optimization scheme for intra-domain schedulingExsiting intra-domain scheduling solutions usually resort to traditional local scheduling scheme, which could not satisfy some new requirements of intra-domain scheuling in commercial grid. From this prospective, a Fair Global Benefit Maximization intra-site Allocation CGMBA is proposed. Based on the cooperative model of intra-domain and the definition admistrate domain's'balanced state', a theoretical proof that the system would gain maximal global benefit if and only if it was in a balanced state is presented. On the basis of this conclusion, Grid task-bundle allocation problem is turned into an iteration process involving retail price, market price and assignment amount of tasks in CGBMA. The experimental results indicate that CGBMA could provide an effective solution with global benefit optimization. Meanwhile, owing to CGBMA's self-selection property which is inherited from market model, load unfairness condition turns worse with the scale of task bundle getting larger. A Cooperative-game-based Global Benefit Maximization Allocation with Fairness Improvement (CGBMAFI) is then presented. The experimental results indicate that administration domain could get better optimize global benefit and user could obtain better executing performance and Performance Cost Ratio with CGBMAFI.