【作者】 申凯；

【导师】 杨寿保；

【作者基本信息】 中国科学技术大学 ， 计算机系统结构， 2008， 博士

【摘要】 网格是建立在Internet上的一种新型的信息技术基础设施,目的是无缝地集成广域资源来合作解决问题,实现计算资源、存储资源、通信资源、软件资源、信息资源、知识资源的全面共享。如何有效管理广域的、异构的、动态的、自治的网格资源是网格技术研究的重点和难点,传统的作业调度方法难以奏效。本文首先介绍网格的概念、演变和分类,分析了网格调度面临的问题。随后第二章在同顾传统调度理论的基础上。结合网格环境,归纳了调度问题在网格环境中的新特征:资源大规模异构性、环境动态不可靠性以及面向用户需求的特性。从两种典型环境入手,通过分析网格社区多集群环境和网格计算市场的特点。针对多集群环境提出基于“全局-局部”模式的层次调度方法。针对计算市场提出基于双向选择的分布式调度方法。本文第二章提出了多集群一致监控的解决方案。设计了一种自描述方法以解决异构资源信息的公共表示问题,基于Ganglia.Grid View,PBS等监控工具设计实现了一个通用的资源监控系统。设计了一种自适应的RTT感知的最小生成树策略以改善系统的可扩展性。论文第四章针对多集群提出了“全局-本地”的二阶段超级调度算法。针对计算密集型应用,在传统的批调度算法中加入对任务完成时限用户QoS的考虑,提出了多集群环境下QoS感知的批调度算法,并应用于多集群的全局队列调度中,与传统批调度算法相比,任务按时完成比率有明显提高。同时.该算法对任务执行时间的预测误差也具有良好的适应性。论文第五章致力于研究经济市场和信任评估相结合的激励机制.把信任机制融入Buyya的网格计算市场模型。提出了网格中信任感知的资源交易模型(Grid Trust Aware ResourceTransaction Model,简写G-Tart模型),详细研究G-Tart模型中的实体、模块、交易流程。在G-Tart模型中,把信任度作为衡量节点交易诚信度的重要指标,激励节点履行已达成的资源交易合约。引出了G-Tart中两个关键问题,即任务代理的资源选择问题和资源代理的任务接受问题。论文第八章从用户代理角度出发。提出了一种基于信任过滤的资源选择方法。该方法首先根据用户信任需求过滤低可信资源。然后对剩余高可信资源综合考虑其价格和风险因素,最后给出了最小机会成本启发式算法。实验表明.该方法能对供求双方产生激励:对资源方保证可靠资源提供者的整体利润:对用户方能显著降低作业失效率、减少成本8%～10%。论文第七章从资源代理角度出发,提出基于收益和成本计算的任务接受策略,根据用户提交任务的相关信息,计算接受任务的沉没成本和机会成本以决定是否接受任务,使得资源提供者和资源请求者都实现自身的经济目标,提高了服务方的收益。论文第八章基于G-Tart模型.利用供求规律.设计了一种分布式调度系统,实现了Oppsim模拟器以模拟该系统。该系统采用用户与资源进行双向选择的模式,通过启发式的策略.动态调节资源价格,引导用户和资源的行为。模拟结果表明该系统能有效解决网格环境中资源负载平衡问题,具有良好的灵活性和可扩展性,能有效提高服务质量,任务完成率方面比Nimrod/G提高了22.5%。本文从网格大规模、动态性和以用户为中心等特点出发.对两种典刑网格环境的调度问题进行了深入分析和有益实践。针对多集群环境提出基于.“全局-局部”模式的层次调度方法和实现方案,具有较强的现实意义:针对计算市场提出G-Tart模型,基于激励驱动的分布式调度方法,为未来经济可行的网格展示了全新的视角和美好的前景。更多还原

【Abstract】 Grid is a new type of information technology infrastructure based on the Internet, which goal is seamlessly integrating wide area resources to solve problems and achieve the comprehensively sharing of computing resources, storage resources, communication resources, software resources, information resources and knowledge resources. The traditional job scheduling method is ineffective for the distributed, heterogeneous, dynamic, and autonomous resources in the Grid.Firstly, the dissertation introduces the concept, evaluation and classification of Grid computing. After analyzing the main problems in grid job scheduling, Chapter2 recalls theory of scheduling and clarifies the new features in grid scheduling, i.e., large-scale heterogeneous machine, dynamic and unreliable environment and user-centric objective. In particular, the research focuses on the two kinds of grid environment named Multi-Clusters and Computational Market. The "Global-Local" 2 stage method is taken for the Multi-Clusters scheduling; while the distributed bi-directional choosing mechanism is adopted for the Computational Market.Resource monitoring is the basis of multi-cluster scheduling and needs to solve issues of heterogeneity and scalability. Chapter3 proposes a self-description method for common representation of heterogeneous resources information. A universal resource monitoring system is implemented based on monitoring tools such as Ganglia, GridView, and PBS, etc. An adaptive RTT-aware MST algorithm is designed to improve system scalability. Experiment shows this method reduces intrusive overhead and improves real-time ability.After that, Chapter 4 proposes and implements the "Global-Local" 2 stage super-scheduler model. Aiming at computing intensive applications, this chapter presents a QoS-aware batch-mode scheduling algorithm. The algorithm is used in the global queue scheduling. Compared to traditional batch-mode scheduling algorithm, it proves to be with equal throughput of system but with improved in-time complete ratio. This algorithm also presents nice adaptability under prediction error of task execution time.Chapter 5 focuses on the incentive mechanism with combination of market and trust. By integrating the trust notion into Grid Market Model, the dissertation introduces the Grid Trust Aware Resource Transaction Model (G-Tart), and describes design ideas, the entities, components and the transaction flow in the model. The trust is set as an important metric measuring the reputation of peers in the market transactions, which can not only stimulate peers to obey the transaction contract, but also provide an incentive for honest service providers. This raises two key issues: how to select appropriate resources and how to accept proper jobs?Thus Chapter 6 proposes a trust-filtered approach is for resource selection to bridge this gap. This approach first filters most of the lower-trust resources basing user’s trust demand. To the remaining resources above demand, it then uses a minimal opportunity-cost algorithm to guide the judgment. Its main idea is to takes both of price and risk into considerations. Simulations show the approach gives two-fold incentives. It effectively guarantees profit of reliable resources, reduces job failure rate and saves cost 8%～10% averagely.Chapter 7 investigates a market-based task service in Gird environment. From providers’ standpoint and basing on relative information provided by users, the provider computes sunk cost and opportunity cost if receiving the task to maximize itself profit. The experiment shows that the scheduler further reduces the cost of resources providers and improves their profit.Finally, based on the G-Tart model, Chapter 8 presents a distributed resource scheduling system for grid environment using supply and demand theory. The Oppsim is implemented to facilicate the system simulation. The system provides a bi-directional choosing mechanism and a QoS guaranteeing mechanism for users and resources to supervise them heuristically. The simulation result of the system shows that the system is scalable, flexible, and capable of handling load balance well. Meanwhile it guarantees QoS of tasks. Task Accomplishment ratio is greater than that in Nimrod/G by 22.5%.By analyzing the characteristic of grid such as large-scale, heterogeneity, unreliability and user-centric, the dissertation gives deeply analysis and beneficial practice on two typical grid environment. It is very useful of the "Global-Local" 2 stage method for the Multi-Clusters scheduling. Meanwhile the dissertation proposes the G-Tart Model which organically combines the market mechanism and trust mechanism, and the incentive-driven distributed scheduling methed shows the brand new view and fine perspective for the future of the grid.更多还原