基于缓冲和预选的网格资源调度优化

资源发现是影响调度效率的关键,针对网格资源发现中复杂的查询过程,通过资源代理,将用户任务发生过调度的资源在本地进行缓存,构成黑白资源名单。同时,在网格资源代理空闲时,按照最近调度的QoS参数为参考值,进行资源的预选择,存放在本地记录,由此构成了本地记录优先的资源发现。针对该方法,设计了支撑该方法的优化代理体系结构,讨论了记录管理问题,给出了优化资源调度过程的算法。实验表明,该方法缩短了任务的平均调度时间,从而缩短了任务平均完成时间,提高了吞吐量,达到了优化的目的。     

Flexible Grid service management through resource partitioning

In this paper, a distributed and scalable Grid service management architecture is presented. The proposed architecture is capable of monitoring task submission behaviour and deriving Grid service class characteristics, for use in performing automated computational, storage and network resource-to-service partitioning. This partitioning of Grid resources amongst service classes (each service class is assigned exclusive usage of a distinct subset of the available Grid resources), along with the dynamic deployment of Grid management components dedicated and tuned to the requirements of a particular service class introduces the concept of Virtual Private Grids. We present two distinct algorithmic approaches for the resource partitioning problem, the first based on Divisible Load Theory (DLT) and the second built on Genetic Algorithms (GA). The advantages and drawbacks of each approach are discussed and their performance is evaluated on a sample Grid topology using NSGrid, an ns-2 based Grid simulator. Results show that the use of this Service Management Architecture in combination with the proposed algorithms improves computational and network resource efficiency, simplifies schedule making decisions, reduces the overall complexity of managing the Grid system, and at the same time improves Grid QoS support (with regard to job response times) by automatically assigning Grid resources to the different service classes prior to scheduling.     

Performance metrics and ontologies for Grid workflows

Many Grid workflow middleware services require knowledge about the performance behavior of Grid applications/services in order to effectively select, compose, and execute workflows in dynamic and complex Grid systems. To provide performance information for building such knowledge, Grid workflow performance tools have to select, measure, and analyze various performance metrics of workflows. However, there is a lack of a comprehensive study of performance metrics which can be used to evaluate the performance of a workflow executed in the Grid. Moreover, given the complexity of both Grid systems and workflows, semantics of essential performance-related concepts and relationships, and associated performance data in Grid workflows should be well described. In this paper, we analyze performance metrics that performance monitoring and analysis tools should provide during the evaluation of the performance of Grid workflows. Performance metrics are associated with multiple levels of abstraction. We introduce an ontology for describing performance data of Grid workflows and illustrate how the ontology can be utilized for monitoring and analyzing the performance of Grid workflows.     

一种面向效益均衡的网格资源预留机制

网格环境中的资源预留机制为跨站点的协同资源分配提供可靠的服务质量保证.针对传统预留机制存在本地任务QoS难以得到保障的缺陷,提出一种基于效益均衡的预留机制.该机制通过比较资源顸留收益与预留对本地任务执行所造成的负面影响来确定资源预留数量,以期取得网格任务QoS保障和本地任务QoS保障的效益均衡.模拟实验采用真实系统负载在较大规模的计算网格系统中检验了该机制的性能表现,实验结果显示,基于效益均衡的预留机制能有效提高资源利用率,同时能显著降低任务的资源费用情况.     

A multi-dimensional scheduling scheme in a Grid computing environment

In this paper, we propose a novel distributed resource-scheduling algorithm capable of handling multiple resource requirements for jobs that arrive in a Grid computing environment. In our proposed algorithm, referred to as multiple resource scheduling (MRS) algorithm, we take into account both the site capabilities and the resource requirements of jobs. The main objective of the algorithm is to obtain a minimal execution schedule through efficient management of available Grid resources. We first propose a model in which the job and site resource characteristics can be captured together and used in the scheduling algorithm. To do so, we introduce the concept of a n-dimensional virtual map and resource potential. Based on the proposed model, we conduct rigorous simulation experiments with real-life workload traces reported in the literature to quantify the performance. We compare our strategy with most of the commonly used algorithms in place on performance metrics such as job wait times, queue completion times, and average resource utilization. Our combined consideration of job and resource characteristics is shown to render high-performance with respect to above-mentioned metrics in the environment. Our study also reveals the fact that MRS scheme has a capability to adapt to both serial and parallel job requirements, especially when job fragmentation occurs. Our experimental results clearly show that MRS outperforms other strategies and we highlight the impact and importance of our strategy.     

Ontology‐based Grid resource management

Grid resources are typically diverse in nature with respect to their software and hardware configurations, resource usage policies and the kind of application they support. Aggregating and monitoring these resources, and discovering suitable resources for the applications become a challenging issue. This is partially due to the representation of Grid metadata supported by the existing Grid middleware which offers limited scope for matching the job requirements that directly affect scheduling decisions. This paper proposes a semantic component in conventional Grid architecture to support ontology‐based representation of Grid metadata and facilitate context‐based information retrieval that complements Grid schedulers for effective resource management. Web Ontology language is used for creating Grid resource ontology and Algernon inference engine has been used for resource discovery. This semantic component has been integrated with conventional Grid schedulers. Several experiments have also been carried out to investigate the performance overhead that arises while integrating this component with Grid schedulers. Copyright © 2009 John Wiley & Sons, Ltd.     

Grid resource management policies for load-balancing and energy-saving by vacation queuing theory

The resource management is the central component of grid system. The analysis of the workload log file of LCG including the job arrival and the resource utilization daily cycle shows that the idle sites in the Grid are the source of load imbalance and energy waste. Here we focus on these two issues: balancing the workload by transferring jobs to idle sites at prime time to minimize the response time and maximize the resource utilization; power management by switch the idle sites to sleeping mode at non-prime time to minimize the energy consume. We form the M/G/1 queue model with server vacations, startup and closedown to analysis the performance metrics to instruct the design of load-balancing and energy-saving policies. We provide our Adaptive Receiver Initiated (ARI) load-balancing strategy and power-management policy for energy-saving. The simulation experiments prove the accuracy of our analysis and the comparisons results indicate our policies are largely suitable for large-scale heterogeneous grid environment.     

Grid resource brokering algorithms enabling advance reservations and resource selection based on performance predictions

We present algorithms, methods, and software for a Grid resource manager, that performs resource brokering and job scheduling in production Grids. This decentralized broker selects computational resources based on actual job requirements, job characteristics, and information provided by the resources, with the aim to minimize the total time to delivery for the individual application. The total time to delivery includes the time for program execution, batch queue waiting, and transfer of executable and input/output data to and from the resource. The main features of the resource broker include two alternative approaches to advance reservations, resource selection algorithms based on computer benchmark results and network performance predictions, and a basic adaptation facility. The broker is implemented as a built-in component of a job submission client for the NorduGrid/ARC middleware.     

网格计算资源管理中的信誉度模型

网格资源管理作为网格研究的核心内容,受到研究人员的高度关注。目前已经提出的诸多管理模型中,基于计算经济的模型被人们普遍看好。文中针对计算经济模型,提出了资源信誉度、资源提供者信誉度、资源消费者信誉度的概念。在此基础上,深入研究了信誉度评价的评价模型和算法以及信誉度评价实现中的一些处理策略。对信誉度评价所需的资源使用记录进行了定义,根据评价需要对现有RUR进行了扩展。最后通过仿真实验对信誉度评价算法进行验证,得到了相应的实验结果和结论。     

Dynamic Instrumentation, Performance Monitoring and Analysis of Grid Scientific Workflows

While existing work concentrates on developing QoS models of business workflows and Web services, few tools have been developed to support the monitoring and performance analysis of scientific workflows in Grids. This paper describes novel Grid services for dynamic instrumentation of Grid-based applications, performance monitoring and analysis of Grid scientific workflows. We describe a Grid dynamic instrumentation service that provides a widely accessible interface for other services and users to conduct the dynamic instrumentation of Grid applications during the runtime. We introduce a Grid performance analysis service for Grid scientific workflows. The analysis service utilizes various types of data including workflow graphs, monitoring data of resources, execution status of activities, and performance measurements obtained from the dynamic instrumentation of invoked applications, and provides a rich set of functionalities and features to support the online monitoring and performance analysis of scientific workflows. Workflows and their relevant information including performance metrics are stored and utilized for comparing the performance of constructs of different workflows and for supporting multi-workflow analysis. The work described in this paper is supported in part by the Austrian Science Fund as part of the Aurora Project under contract SFBF1104 and by the European Union through the IST-2002-511385 project K-WfGrid.     

Grid commerce, market-driven G-negotiation, and Grid resource management.

Although the management of resources is essential for realizing a computational grid, providing an efficient resource allocation mechanism is a complex undertaking. Since Grid providers and consumers may be independent bodies, negotiation among them is necessary. The contribution of this paper is showing that market-driven agents (MDAs) are appropriate tools for Grid resource negotiation. MDAs are e-negotiation agents designed with the flexibility of: 1) making adjustable amounts of concession taking into account market rivalry, outside options, and time preferences and 2) relaxing bargaining terms in the face of intense pressure. A heterogeneous testbed consisting of several types of e-negotiation agents to simulate a Grid computing environment was developed. It compares the performance of MDAs against other e-negotiation agents (e.g., Kasbah) in a Grid-commerce environment. Empirical results show that MDAs generally achieve: 1) higher budget efficiencies in many market situations than other e-negotiation agents in the testbed and 2) higher success rates in acquiring Grid resources under high Grid loadings.     

Replication based fault tolerant job scheduling strategy for economy driven grid

In this paper, the problem of fault tolerance in grid computing is addressed and a novel adaptive task replication based fault tolerant job scheduling strategy for economy driven grid is proposed. The proposed strategy maintains fault history of the resources termed as resource fault index. Fault index entry for the resource is updated based on successful completion or failure of an assigned task by the grid resource. Grid Resource Broker then replicates the task (submitting the same task to different backup resources) with different intensity, based on vulnerability of resource towards faults suggested by resource fault index. Consequently, in case of possible fault at a resource the results of replicated task(s) on other backup resource(s) can be used. Hence, user job(s) can be completed within specified deadline and assigned budget, even on the event of faults at the grid resource(s). Through extensive simulations, performance of the proposed strategy is evaluated and compared with the Time Optimization and Checkpointing based Strategy in an economy driven grid environment. The experimental results demonstrate that in the presence of faults, proposed fault tolerant strategy improves the number of tasks completed with varied deadline and fixed budget as well as number of tasks completed with varied budget and fixed deadline. Additionally, the proposed strategy used a smaller percentage of deadline time as compare to both Time Optimization and Checkpointing based Strategy. Although the proposed strategy has a percentage of budget spent greater than that of Time Optimization Strategy and Checkpointing based Strategy, it is accepted as a proposed strategy in time optimization where the main objective is to maximize tasks completed within a given deadline. It can be concluded from the experiments that the proposed strategy shows improvement in satisfying the user QoS requirements. It can effectively schedule tasks and tolerate faults gracefully even in the presence of failures, but the costs are slightly higher in terms of budget consumption. Hence, the proposed fault tolerant strategy helps in sustaining user??s faith in the grid, by enabling the grid to deliver reliable and consistent performance in the presence of faults.     

基于网络断层扫描的网格网络性能测量分析

网格计算通过网络连接来获得一个高性能和高效的计算平台。网格网络的监测和性能测量为网格性能分析、负载平衡、任务调度等提供了重要的科学依据,而成为大规模网格服务的关键组件。现有的几种网格监测方法因缺乏对监测数据的推断分析而无法对网格网络的性能进行测量。通过对网格网络性能测量的特点、GloPerf及传统网络测量技术的分析,提出了基于网络断层扫描的网格网络性能测量方法。研究结果为网格网络性能的测量提供了新的途径。     

Meeting security and user behavior requirements in Grid scheduling

Most of current research in Grid computing is still focused on the improvement of the performance of Grid schedulers. However, unlike traditional scheduling, in Grid systems there are other important requirements to be taken into account. One such a requirement is the secure scheduling, namely achieving an efficient allocation of tasks to reasonable trustful resources. In this paper we formalize the Grid scheduling problem as a non-cooperative non-zero sum game of the Grid users in order to address the security requirements. The premise of this model is that in a large-scale Grid, the cooperation among all users in the system is unlikely to happen. The users’ cost of playing the game is interpreted as a total cost of the secure job execution in Grid. The game cost function is minimized, at global (Grid) and local (users) levels, by using four genetic-based hybrid meta-heuristics. We have evaluated the proposed model under the heterogeneity, the large-scale and dynamics conditions using a Grid simulator. The relative performance of four hybrid schedulers is measured by the makespan and flowtime metrics. The obtained results suggested that it is more resilient for the Grid users to pay some additional scheduling cost, due to verification of the security conditions, instead of taking the risk of assigning their tasks to unreliable resources.     

Grid resource discovery based on distributed learning automata

This paper focuses on resource discovery problem for Grid. Grid is a devices and services environment that has evolved with the goal of resource sharing. Grid resource discovery encompasses locating and retrieving computational resources. Existing resource discovery solutions are not well adapted to the dynamicity and heterogeneity of Grid. Query propagation is a novel approach that forwards an unsupported query from its resident peer to an adjacent peer. The concept of next generation intelligent Grid environments needs intelligent modules for resource discovery. Learning automaton is a stochastic tool with learning ability which simply adapts to the progressive environmental changes. The proposed method utilizes a distributed learning automata (DLA) which is a network of learning automata (LA). Here, multiple DLA are used for forwarding domain-specific queries. Different Grid scales are utilized for evaluation of the proposed method. Results demonstrate that the resource discovery based on DLA optimizes resource utilization, maximizes throughput, minimizes response time and avoids overload. Moreover, the algorithm is also scalable, fully distributed and failure-free.     

教育资源网格模型及副本创建策略

教育资源网格是解决目前分布式教育资源共享问题的有效手段.针对中小学教育资源共享问题,提出了层次式的教育资源网格模型,定义了各层节点的功能.通过与欧洲数据网格对比,分析了教育资源网格的特点.基于层次式的教育资源网格,对影响副本创建策略性能的因素进行了分析,然后引入网络带宽和文件大小两个参数,提出了一种动态副本创建策略(dynamic replica creation strategy,简称EDRS).利用数据网格模拟工具OptorSim构建了教育资源网格虚拟环境,分析比较了EDRS策略与Caching-LRU策略、Caching-LFU策略和基于经济模型的副本创建策略的性能.最后,综合各项指标分析了不同策略对教育资源网格系统性能的影响.结果表明,EDRS策略在教育资源网格应用中有着更好的系统性能.     

WiGriMMA: A Wireless Grid Monitoring Model Using Agents

The complexity, heterogeneity, device mobility and the unpredictable user behavior demands proper automation of monitoring activity in the wireless Grid to enable the user needs. Since the wireless devices can dynamically join/leave the Grid, and its state may be affected by various parameters (like the battery power, signal strength, the number of jobs submitted to it, device mobility, etc.) leading to overload state, it is essential to monitor the devices so that long term resource planning can be achieved. This paper proposes a Wireless Grid Monitoring Model using Agents (WiGriMMA) that monitor the device mobility and state, communicates the state to Grid information server (GIS), provides the resource availability information, controls the selfish users and the device state so that the device is not overloaded. The model is simulated to test its operation effectiveness considering the performance parameters such as resource availability, resource stability, device state, job execution rate, user behavior and agent overhead. The results show that the proposed WiGriMMA performs better than the existing Grid monitoring model (GridView) in terms of the resource availability, device states and the job execution rate.     

A standards‐based Grid resource brokering service supporting advance reservations,coallocation, and cross‐Grid interoperability

The problem of Grid‐middleware interoperability is addressed by the design and analysis of a feature‐rich, standards‐based framework for all‐to‐all cross‐middleware job submission. The architecture is designed with focus on generality and flexibility and builds on extensive use, internally and externally, of (proposed) Web and Grid services standards such as WSRF, JSDL, GLUE, and WS‐Agreement. The external use provides the foundation for easy integration into specific middlewares, which is performed by the design of a small set of plugins for each middleware. Currently, plugins are provided for integration into Globus Toolkit 4 and NorduGrid/ARC. The internal use of standard formats facilitates customization of the job submission service by replacement of custom components for performing specific well‐defined tasks. Most importantly, this enables the easy replacement of resource selection algorithms by algorithms that address the specific needs of a particular Grid environment and job submission scenario. By default, the service implements a decentralized brokering policy, striving to optimize the performance for the individual user by minimizing the response time for each job submitted. The algorithms in our implementation perform resource selection based on performance predictions, and provide support for advance reservations as well as coallocation of multiple resources for coordinated use. The performance of the system is analyzed with focus on overall service throughput (up to over 250 jobs per min) and individual job submission response time (down to under 1 s). Copyright © 2009 John Wiley & Sons, Ltd.     

A reputation-driven scheduler for autonomic and sustainable resource sharing in Grid computing

The obstacle for the Grid to be prevalent is the difficulty in using, configuring and maintaining it, which needs excessive IT knowledge, workload, and human intervention. At the same time, inter-operation amongst Grids is on track. To be the core of Grid systems, the resource management must be autonomic and inter-operational to be sustainable for future Grid computing. For this purpose, we introduce HOURS, a reputation-driven economic framework for Grid resource management. HOURS is designed to tackle the difficulty of automatic rescheduling, self-protection, incentives, heterogeneous resource sharing, reservation, and SLA in Grid computing. In this paper, we focus on designing a reputation-based resource scheduler, and use emulation to test its performance with real job traces and node failure traces. To describe the HOURS framework completely, a preliminary multiple-currency-based economic model is also introduced in this paper, with which future extension and improvement can be easily integrated into the framework. The results demonstrate that our scheduler can reduce the job failure rate significantly, and the average number of job resubmissions, which is the most important metric in this paper that affects the system performance and resource utilization from the perspective of users, can be reduced from 3.82 to 0.70 compared to simple sequence resource selection.     

基于Ganglia与MDS结合的网格监控体系研究

资源监控可以为使用者提供网格环境中与资源相关的性能数据,同时也可以为作业调度提供必要的资源信息支持。Ganglia可以监控基于集群的广域系统中的节点(处理器集)的状态,MDS可以用来监控和发现网格资源和服务,本文通过对Ganglia与MDS的结合进行研究,提出了一个功能强大且严密的网格资源和作业监控体系,同时将该监控体系加入到校园计算网格平台中。