计算网格资源管理与调度理论及技术的研究-智能与分布计算实验室

计算网格资源管理与调度理论及技术的研究

姓名	李春林
论文答辩日期	2003.10.17
论文提交日期	2003.10.17
论文级别	博士
中文题名	计算网格资源管理与调度理论及技术的研究
英文题名	Research of Theory and Techniques of Computational Grid Resource Management and Schedule
导师1	卢正鼎
导师2
中文关键词	计算网格;网格资源管理;资源调度;移动代理;经济调度;效用函数;网格资源路由
英文关键词	computational grids;grid resource management;resource scheduling;mobile agent;economical scheduling;utility function;grid resource routing
中文文摘	计算网格（computational grids）是近年来国际上兴起的一种新兴的信息科学技术，其目标是把因特网（Internet）整合成一种超大规模的巨大计算机系统，以实现计算资源、存储资源、信息资源、知识资源等的全面共享。计算网格在国民经济和国防的诸多领域里具有广泛的应用前景。计算网格系统中包含各种各样的资源，这些资源具有动态变化、广域分布及系统异构等特点，这在一定程度上阻碍了计算网格的应用向纵深发展，同时也给计算网格的应用基础研究提出了新的挑战。计算网格资源管理与调度是高性能网格计算领域中的一个重要研究课题，其目的就是要解决计算网格资源的描述、组织、管理与调度等关键科学技术问题。从理论与实践的结合上，对计算网格资源管理与调度的若干关键问题进行了研究与探索，其主要研究工作及贡献可体现在以下几个方面：系统地研讨了计算网格资源管理与调度的理论、方法及技术。将移动Agent技术、微观经济学模型与计算网格资源管理与调度问题结合起来研究，将交叉学科的方法引入本研究中，试图为计算网格资源管理与调度系统的设计提供一种新的思路和途径。综合论述及分析了国内外计算网格资源管理与调度的发展状况及其技术特征，指出了相关研究工作的局限性。根据计算网格资源管理与调度的特性，建立了一种基于移动可适应性Agent的网格计算模型，将移动Agent技术作为计算网格资源管理逻辑抽象和物理实现的工具，将计算网格资源管理中的资源、作业、任务等实体抽象成Agent主体，进而将计算网格映像成一个Agent的集合。提出了一种基于Agent的计算网格资源管理（AGRM）体系结构框架。在AGRM中，计算网格的实体可包含计算资源和服务，它们可用网格代理表示。每个网格Agent既可以是服务的提供者，也可以是服务的请求者。每个网格Agent可独立、异步地进行操作。AGRM体系结构中可包含三种网格Agent：网格资源Agent，网格请求Agent和网格任务Agent。网格资源Agent定义网格资源描述，并把它发布到资源路由器中。网格请求Agent从本地资源路由器检索服务描述，网格资源路由器通过转发资源请求来查找资源节点，最终将资源请求转发给满足该请求的计算资源。网格任务Agent通过竞标向一个或多个网格资源Agent购买资源，最后使用该资源完成计算任务。AGRM体系结构框架可为计算网格资源管理与调度系统的设计提供参考及依据。运用层次结构的思想，研究提出了一种分层式网格资源模型。在该模型中，网格资源可按节点所分布的地理区域、连通性以及节点之间的相关性等因素进行分簇（cluster）。网格中的每个节点可看成是第零层簇，由有关节点组成的簇被称作第一层簇，几个第一层簇的组合被称作第二层簇，类似地，可定义第三层簇和第k层簇。网格资源分层模型可表示成一个加权图G = ( V, E )，其中V表示节点集，E表示连接节点的通信链路集。以该模型为基础设计了一种分层式网格资源路由（HGRR）协议。该协议主要包括三个功能模块：初始化模块，路由信息更新模块，路由决策模块。其中路由决策模块主要利用离散动态规划原理，通过求多段图的方法来获得最优网格资源路由决策。在该协议中，各节点只需维护局部路由信息及网格资源簇结构的主要信息，它能适应计算网格资源结构的动态变化，可有效地解决计算网格资源发现及定位问题。文中给出了HGRR协议的主要实现过程、正确性证明及复杂性分析。设计了一种基于Agent的网格资源经济调度模型。运用拍卖与投标模型有效地分配网格资源和调度网格任务Agent，以实现计算网格用户之间公平而有效的资源分配，可适应计算网格资源供需状态的动态变化。给出了网格任务Agent效用函数及竞标函数的定义，并对网格任务Agent的效用函数进行了优化。设计了基于费用比例的网格资源分配算法，网格任务Agent的资源节点选择算法和网格任务Agent投标算法。研究分析了网格任务Agent的竞标函数所具有的特征，描述了网格资源Agent的效用函数模型。通过仿真实验验证了所建议的网格资源经济调度模型及方法的可用性和有效性。研究了计算网格资源的形式描述方法，设计了适应于计算网格资源描述的相关数据结构；设计及分析了实现计算网格资源管理的三个过程（procedures），即网格资源登记过程，网格资源发现过程和网格资源经济调度过程，从而为计算网络资源管理与调度的实现奠定了理论及技术基础。
英文文摘	Computational grid is a burgeoning information science and technology in recent years. Its main objective is to combine Internet into a whole very large-scale computer system in order to share all computing resources, storage resources, information resources and knowledge resources. The computational grids have been increasingly used by various fields of the national economy and the national defense. A computational grid system consists of various resources. These resources have some features of dynamic change, geographical dispersion and heterogeneous systems, which will in certain extent hinder the development of grid application and present challenges for application basis research of the grid computing. The resource management and schedule are a very important research issue for application basis in the field of high-performance computational grids. The objective of the research issue is to solve key problems of science and technology for specification, organization, management and schedule of the grid resources. Combining theory with practice, this dissertation studies the key technologies of grid resource management and schedule. The major research work and contributions in this dissertation are as follows. The theory, method and techniques of computational grid resource management and schedule have systematically been studied. The mobile agents and microeconomy model are introduced into the research area of computational grid resource management and schedule, so that a research method of cross-discipline is introduced into this research issue. On this basis, a new idea and approach to computational grid resource management and schedule are presented. A comprehensive overview of computational grid resource management and schedule is made, and related work’s limitations are pointed out. On basis of the features of computational grid resource management and schedule, a mobile agent-based grid computing model is built up, which can make the mobile agents as the logic abstract object and the physical implementation tools of computational grid resource management, so that the entities of resource job and task of computational grid resource management can be abstracted to the agent main body, which can map the computational grids into a set of agents. The architecture of mobile agent-based grid resource management (AGRM) is presented. In AGRM framework, the entities of computational grids include the computing resources and services that can be represented by grid agents. Each grid agent may be a provider of services and may also be an applicant of services. Each grid agent can be independently and asynchronously operated. AGRM architecture includes three grid agents: grid resource agents, grid request agents and grid task agents. Grid resource agents define grid resource description and distribute the description to grid resource routers. Grid resource request agents search the service description. Grid resource routers forward the resource requests to find the resource node, and finally transfer the resource requests to the resoure node that can satisfy the requests. Grid task agents buy the resources of the grid resource agents by bidding, and finally perform computational task using these resources. This AGRM framework can provide references and basis for designing computational grid resource management and scheduling systems. The layered grid resource model is built up according to the layered idea. In this model, the clustering problem of grid resources depends on the network topology, geographical location of nodes and connectivity, as well as the relativity between nodes. Each node can be considered as 0th-level cluster. A region which consists of such several nodes can be called first-level cluster. Several first-level clusters are combined to form the second-level clusters. Similarly, the third-level clusters and Kth-level clusters can be defined. The layered grid resource model is also represented as a weighted digraph G = (V, E), where V denotes the set of nodes and E denotes the set of communication links connecting the nodes. On basis of this model, a hierarchical grid resource routing (HGRR) protocol is presented. HGRR protocol includes three functional modules: intialization module, routing update module and routing decision module, where the routing decision module is based on the discrete dynamic programming principle which allows the optimal routing to be found by computing the multi-segment map. Each resource node only remains local routing information and main information of clustering structure of grid resources. HGRR protocol can dynamically adapt to changes of grid resource structures. This routing protocol can effectively solve the problems of grid resources discovery and location. The main procedures for realizing the routing protocol are presented. The proof of correctness and complexity analysis of the protocol are also made. An agent-based grid resource economical scheduling model is proposed, which use bid and auction model to manage and allocate grid resources. This mechanism can effectively and fairly allocate grid resources, and adapt the dynamic changes for grid resources status. The definitions of utility function and bid function of grid task agents are given, and the utility function of grid task agents is optimized. A grid resource allocation algorithm based on cost proportion, a resource node selection algorithm and a bid algorithm are designed. The features of bid function for grid task agents are studied and analysed, and utility function model of grid resource agents is described. The availability and efficiency of the proposed grid resource economical scheduling model and method have been verified by simulations. The formal description methods of the computational grid resource are studied. The data structures of the grid resource description are designed. Three main procedures for realizing computational grid resource management are designed and analyzed. These three procedures include grid resource registration process, grid resource discovery process and grid resource economical scheduling process. The designed data structures and main procedures can provide the theoretical and technical basis for realizing the AGRM system.