【作者】 高瞻；

【导师】 罗四维；

【作者基本信息】 北京交通大学 ， 计算机应用技术， 2010， 博士

【摘要】 网格是一种先进的信息技术基础设施,目的是有效整合Internet上广泛分布的各种计算资源、存储资源、通信资源、信息资源等,向用户提供虚拟、统一、透明的计算环境。网格的重要性已经受到多个国家和政府的关注,并吸引了大量的研究。合理、有效地调度网格任务可以充分利用网格资源,提高系统效率,更好地完成用户的网格应用,因此网格任务调度问题成为网格研究的重要内容之一。随着开放网格服务体系结构(OGSA)标准的确立,“面向服务”成为近些年网格发展的方向,服务质量(QoS)成为网格任务调度过程中必须要考虑的一个重要因素。“网格之父”Ian Foster更是把提供非平凡的服务质量作为网格的判断标准之一。由于网格具有动态性和自治性的特点,QoS保证是一项非常复杂和具有挑战性的工作。资源预留是实现QoS保证的有效手段,但也会产生“资源碎片问题”,影响非预留任务的完成效果。如何在有效使用资源预留的同时减少它所带来的不良后果成为一个很有意义的研究内容。网格经济(Grid Economy)的出现为网格资源管理提供了一个公共的解决方案,其中双向拍卖模型被广泛地应用于网格资源分配中。但目前基于双向拍卖的网格资源分配和任务调度大多直接使用经济学领域中已有的拍卖理论,仅仅关注于用户的经济收益,而对服务质量的有效保证重视不够。目前,服务网格是网格构建的主流方向之一。在服务网格环境下,调度器需要根据用户的即时要求,动态地把大量临时性的网格服务组合为可增值的复合服务。因此,需要一种服务调度机制来实现网格服务的组合、匹配,同时向用户提供所需的服务质量。本文针对在网格任务调度过程中与服务质量保证相关的若干问题进行了研究,具体工作从对服务质量保证的“事先规划”和“事中注意”两个方面开展。前者涉及了与资源预留相关的任务调度问题；后者聚焦于如何把用户服务质量需求映射到基于经济机制的资源分配和网格服务调度中。本文取得的主要创新成果如下：1.提出了一种模糊的网格资源预留机制FRRM。传统的资源预留机制在预留任务实际使用资源之前就完成了资源分配,无法应对在预留提前时间内资源的动态变化。FRRM能够感知预留提前时间内资源状态的变化,根据资源的运行时信息动态地调度已接纳的预留请求。引入了资源-预留图对FRRM下的预留请求接纳控制以及预留任务调度策略进行描述,分析了FRRM对资源故障的容错性。分别在模拟任务集和真实任务集上进行了FRRM和传统预留机制的对比实验。实验结果表明FRRM能够显著减小任务抢占代价,有效提高资源利用率,对网格的动态环境具有更好的适应性。2.给出了当存在资源预留时,针对于抢占式任务和非抢占式任务的调度策略。前者可以通过对已有调度策略的改进来实现；后者则被建模为一个多组装箱(Multi-line Bin Packing, MBP)问题。提出了Multi2Single算法把MBP问题转化为具有相同最优化目标的单组装箱(Single-line Bin Packing, SBP)问题,并在经典装箱(Bin Packing, BP)问题研究的基础上给出了解决SBP问题的启发式装箱算法。通过理论分析和模拟实验对装箱算法的最坏情况渐近性能比和平均性能比进行了分析。与传统的调度算法Mim-min和Suffrage相比,我们提出的算法可以明显减小非预留任务的最大调度长度(makespan),有效缓冲了预留任务对非预留任务调度目标的不良影响。3.提出了一种面向可量化网格资源的贪心双向拍卖协议GDAP和一种面向网格服务的服务质量可保证的双向拍卖协议QDAP。证明了GDAP具有策略性防伪、个人理性和弱预算平衡的特点。与传统的基于MDA (Multi-unit Double Auction)的拍卖策略相比,GDAP在兼顾经济效益的同时能够大大提高网格资源利用率及用户满意率,有利于实现网格大规模资源共享的目标。QDAP首次把服务质量引入到双向拍卖协议中,在最大化服务利用率的同时向消费者提供有效的服务质量支持。把QDAP与传统的双向拍卖策略PMDA和CDA进行了实验对比,结果表明QDAP具有更好的拍卖公平性、较高的服务利用率,更加适应于服务网格环境。4.研究了具有多QoS约束的网格服务调度问题。以移动Agent作为应用的载体,通过移动Agent在不同服务实例之间的迁移来满足用户对复合网格服务的访问需求。提出了一种多QoS约束下基于蚂蚁算法的移动Agent路由算法(MRBAA), MRBAA支持移动Agent对多个服务的并行访问,并考虑了服务间的数据交互。在MRBAA下,移动Agent以最大化用户效用为目标进行迁移,同时兼顾用户的QoS需求。与快速贪心算法和随机选择算法的对比实验表明,MRBAA在调度成功率和提供的效用方面都具有更好的效果。更多还原

【Abstract】 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.更多还原