一种基于QoS的事务工作流并发调度算法

并发冲突引起的连锁夭折会降低系统性能,提出了一种基于QoS的事务工作流调度算法,该算法适应异构环境需求,支持基于QoS的延迟调度优化策略和SAFE集合扩充优化策略,可根据QoS参数调整相应的调度决策,在保证分布异构环境中复杂事务工作流并发正确性的同时减少连锁夭折.证明了算法不会引起循环等待和饿死现象,可保证调度的可串行性和可恢复性,性能模拟表明该算法适用于长期运行的事务工作流的并发调度,可有效减少连锁夭折,从而减少由此带来的性能损失.     

A fault‐tolerant workflow management system with Quality‐of‐Service‐aware scheduling for scientific workflows in cloud computing

Cloud computing provides solutions to many scientific and business applications. Large‐scale scientific applications, which are structured as scientific workflows, are evaluated through cloud computing. In this paper, we proposed a Quality‐of‐Service‐aware fault‐tolerant workflow management system (QFWMS) for scientific workflows in cloud computing. We have considered two real‐time scientific workflows, i.e., Montage and CyberShake, for an evaluation of the proposed QFWMS. The results of the proposed QFWMS scheduling were evaluated through simulation environment WorkflowSim and compared with three well‐known heuristic scheduling policies: (a) minimum completion time (MCT), (b) Maximum‐minimum (Max‐min), and (c) Minimum‐minimum (Min‐min). By considering Montage scientific workflow, the proposed QFWMS reduces the make‐span 8.86%, 8.94%, and 5.53% compared with existing three heuristic policies. Similarly, the proposed QFWMS reduces the cost 6.19%, 3.52%, and 3.60% compared with existing three heuristic policies. Likewise, by considering CyberShake scientific workflow, the proposed QFWMS reduces the make‐span 19.54%, 21.41%, and 25.71% compared with existing three heuristic policies. Similarly, the proposed QFWMS reduces the cost 8.78%, 8.40%, and 8.61% compared with existing three heuristic policies. More so, for QFWMS, SLA is neither violated for time constraints nor for cost constraints. While for MCT, Max‐min and Min‐min scheduling policies, SLA is violated 32, 37, and 23 times, respectively. Conclusively, the proposed QFWMS scheduling and management system is one of the significant workflow management systems for execution and management of scientific workflows in cloud computing.     

A novel fault-tolerant scheduling approach for collaborative workflows in an edge-IoT environment

As a newly emerging computing paradigm, edge computing shows great capability in supporting and boosting 5G and Internet-of-Things (IoT) oriented applications, e.g., scientific workflows with low-latency, elastic, and on-demand provisioning of computational resources. However, the geographically distributed IoT resources are usually interconnected with each other through unreliable communications and ever-changing contexts, which brings in strong heterogeneity, potential vulnerability, and instability of computing infrastructures at different levels. It thus remains a challenge to enforce high fault-tolerance of edge-IoT scientific computing task flows, especially when the supporting computing infrastructures are deployed in a collaborative, distributed, and dynamic environment that is prone to faults and failures. This work proposes a novel fault-tolerant scheduling approach for edge-IoT collaborative workflows. The proposed approach first conducts a dependency-based task allocation analysis, then leverages a Primary-Backup (PB) strategy for tolerating task failures that occur at edge nodes, and finally designs a deep Q-learning algorithm for identifying the near-optimal workflow task scheduling scheme. We conduct extensive simulative case studies on multiple randomly-generated workflow and real-world edge-IoT server position datasets. Results clearly suggest that our proposed method outperforms the state-of-the-art competitors in terms of task completion ratio, server active time, and resource utilization.     

Autonomic workflow execution in the grid

Mobile agents are being leveraged in both workflow management and grid computing contexts. The convergence of these two research streams supports execution in the grid where tasks are allowed to vary in their level of interdependence. The result is an expansion of grid applications beyond those which consist of homogeneous computations decomposed and performed in parallel to those which support the parallel execution of sequences of interdependent tasks that constitute a workflow. However, grid computation of critical workflows requires that the grid platform exhibits the autonomic characteristic of self-healing in order to ensure workflow execution. To address this issue, in this work, we first develop a model for dynamic fault tolerance technique selection, which can be embedded generically in a mobile agent workflow management system. We then augment an existing architecture for flexible fault tolerance in the grid with our model, thus allowing the system to optimally configure its fault tolerance mechanisms through awareness of the computational environment. The result is a foundation for autonomic workflow management in the grid.     

行为综合功能流水线中的负载平衡蚁群调度算法

在专用集成电路高层次综合中,功能流水线是提高算法描述执行速度的关键技术.针对时间约束和资源约束的两类行为综合功能流水线调度问题,提出了一种基于蚁群优化(ACO)的调度算法.LB-ACO算法将ACO算法与力向算法相结合,使用修改的力向公式定义局部试探因子,用个体调度结果的质量来更新全局试探因子.实验结果表明,LB-ACO算法在保证较低的时间复杂度O(cn2)的前提下,获得接近最优的调度结果.     

一种SDN架构下业务属性相关的多径路由算法

面对当前网络中流量的增长、业务种类的增多,SDN中多数的路由算法只支持一种QoS参数,没有兼顾对系统调度服务公平性的考虑,然而多参数限制的QoS 明显是NP 难问题,该问题用普通的路由算法难以解决,引进蚁群算法,在蚁群算法的基础上,将链路的时延、分组丢失率引入蚁群算法中,作为算法选择路径的依据,提出一种新的路由算法。该算法在对不同业务属性的数据流分类的基础上,根据网络的实时状况,为不同业务属性的数据流选择合适的路径,对网络中的数据流进行多路径传输。仿真实验表明,该算法能有效地降低数据流的时延、分组丢失率。     

An agent‐based workflow scheduling mechanism with deadline constraint on hybrid cloud environment

Summary

With the advances of cloud computing, business and scientific‐oriented jobs with certain workflows are increasingly migrated to and run on a variety of cloud environments. These jobs are often with the property of deadline constraint and have to be completed within limited time. Therefore, to schedule a job with workflow (short for workflow) with deadline constraint is increasingly becoming a crucial research issue. In this paper, we, based on previous work, propose an agent‐based workflow scheduling mechanism to schedule workflows that are with deadline constraint into federated cloud environment.

Design and Methods

We add a workflow agent into the original framework to schedule the deadline‐constraint workflow. The workflow agent can smoothly schedule workflows to the cloud system according to their required resource and automatically monitor their execution. In order to accurately predict the execution time of each task to meet deadline constraint on certain VM with given resource, we inherit the use of rough set theory to estimate execution time of task in our previous work.

Result and Discussion

A heuristic algorithm that is embedded into the workflow agent is also proposed because the problem had been shown to be NP‐complete. The mechanism also adopts dynamic job dispatching method to reduce the usage of VM and to improve the resource utilization. We also conducted experiments to evaluate the efficiency and effectiveness.

Conclusion

The experimental results show that the prediction time is very close to the real execution time and can efficiently schedule multiple scientific workflows to meet the deadline constraints simultaneously.     

BAAQ: an infrastructure for application integration and knowledge discovery in bioinformatics.

The emerging grid computing technologies enable bioinformatics scientists to conduct their researches in a virtual laboratory, in which they share public databases, computational tools as well as their analysis workflows. However, the development of grid applications is still a nightmare for general bioinformatics scientists, due to the lack of grid programming environments, standards and high-level services. Here, we present a system, which we named Bioinformatics: Ask Any Questions (BAAQ), to automate this development procedure as much as possible. BAAQ allows scientists to store and manage remote biological data and programs, to build analysis workflows that integrate these resources seamlessly, and to discover knowledge from available resources. This paper addresses two issues in building grid applications in bioinformatics: how to smoothly compose an analysis workflow using heterogeneous resources and how to efficiently discover and re-use available resources in the grid community. Correspondingly an intelligent grid programming environment and an active solution recommendation service are proposed. Finally, we present a case study applying BAAQ to a bioinformatics problem.     

网格工作流动态调度研究

现有的网格工作流调度算法大都利用遗传算法所具有的并行性和全局解空间搜索的特点来解决工作流调度问题.但是,现有的调度算法没有对动态调度问题进行处理.文中针对网格服务的动态性,提出了服务资源信息中心的概念并给出了网格工作流管理系统的体系结构.在现有的基于遗传算法的网格工作流调度算法的基础上提出了网格服务工作流动态调度算法,补充了不同工作流过程模型的适应度函数的计算.     

面向数据密集型工作流的能耗感知调度策略

随着数据中心规模的扩大,高能耗问题已经成为高性能计算领域的一个重要问题。针对数据密集型工作流的高能耗问题,提出通过引入“虚拟数据访问节点”的方法来量化评估工作流任务的数据访问能耗开销,并在此基础上设计了一种“最小能耗路径”的启发式策略。在经典的HEFT算法和CPOP算法基础上,通过引入该启发式策略设计并实现了2种具有能耗感知能力的调度算法（HEFT-MECP和CPOP-MECP）。实验结果显示,基于最小能耗路径的启发式调度算法能有效降低数据访问操作的能耗开销,在面对大型的数据密集工作流任务时,该启发式调度策略体现了较好的适应性。     

QIACO:一种多QoS约束网格任务调度算法

网格环境下的任务调度问题属于NP难解,难以得到精确的最优解,适合使用蚁群算法等智能优化算法对最优解进行逼近;同时,服务质量(QoS)也是衡量网格性能的一个重要指标,网格任务调度应该满足用户的QoS需求.为解决具有QoS保证的网格任务调度问题.本文以带有Qos约束的任务为研究对象,结合改进的蚁群算法,提出了一种基于蚁群算...     

粒子群优化算法在网格工作流调度中的应用

为了提高网格工作流管理系统的性能,将粒子群优化算法（PSO）引入到网格工作流的调度策略中．分析算法的基本原理,根据网格工作流调度的问题对其进行变形,提出基于粒子群优化算法的网格工作流调度策略,并与基于Dijkstra的网格工作流调度算法进行对比实验．实验数据表明,粒子群优化算法在网格工作流调度中的性能较好．     

Reinforced Ant Colony Optimization for Fault Tolerant Task Allocation in Cloud Environments

Cloud computing is the most emerging technology in distributed systems which provides users flexibility of storing data and sharing of computing resources by making use of the concept of virtualization. Large amount of data processing is required in developing cloud application services which increases the bandwidth. To avoid this, proper scheduling of tasks is required. Task scheduling is a combinatorial optimization problem and is one of the critical issues to be solved in cloud computing. Proper task scheduling not only reduces the make span but also hikes the system performance. In this research work, a novel strategy is proposed to solve task scheduling using Ant Colony Optimization (ACO) by adapting Reinforcement learning (RL) along with fault tolerance to make the scheduling process fault resistant, and to achieve the objective of minimum make-span. The proposed algorithm, Reinforced-Ant Colony Optimization (RACO) yields about 60% of better performance than sole implementation of ACO.

     

K-PSO: An improved PSO-based container scheduling algorithm for big data applications

In recent years, Docker container technology is being applied in the field of cloud computing at an explosive speed. The scheduling of Docker container resources has gradually become a research hotspot. Existing big data computing and storage platforms apply with traditional virtual machine technology, which often results in low resource utilization, a long time for flexible scaling and expanding clusters. In this paper, we propose an improved container scheduling algorithm for big data applications named Kubernetes-based particle swarm optimization(K-PSO). Experimental results show that the proposed K-PSO algorithm converges faster than the basic PSO algorithm, and the running time of the algorithm is cut in about half. The K-PSO container scheduling algorithm and algorithm experiment for big data applications are implemented in the Kubernetes container cloud system. Our experimental results show that the node resource utilization rate of the improved scheduling strategy based on K-PSO algorithm is about 20% higher than that of the Kube-scheduler default strategy, balanced QoS priority strategy, ESS strategy, and PSO strategy, while the average I/O performance and average computing performance of Hadoop cluster are not degraded.     

Agent在工作流管理系统中的应用研究

当前,大多数工作流管理系统都是独立地管理单个工作流,而忽视了工作流之间的资源约束关系,基于ａｇｅｎｔ 的工作流管理系统能够有效地解决这个问题。本文主要讨论基于 ａｇｅｎｔ 的工作流管理系统包括系统配置、工作流执行的动态调度以及多 ａｇｅｎｔ 系统的组织和通信问题。     

三维QoS约束下效益最优的多需求网格资源调度

文中在搭建的三维Qos模型空间下研究基于效益最优的资源调度算法,采用经济模型等关注系统与用户交互的管理方式,向用户提供服务质量保证.文中提出的资源调度策略研究在三维QoS约束下如何才能最大的满足用户和资源调度者的需求,从而使整个系统的效益值最大.文中提出的可以被反复调用的算法用来最优化基于三维的Qos资源调度.实验显示了最优化基于多维QoS的资源调度算法会得到更少的运行费用和更高的调度效率.     

A workflow task scheduling algorithm based on the resources' fuzzy clustering in cloud computing environment

Cloud computing is the key and frontier field of the current domestic and international computer technology, workflow task scheduling plays an important part of cloud computing, which is a policy that maps tasks to appropriate resources to execute. Effective task scheduling is essential for obtaining high performance in cloud environment. In this paper, we present a workflow task scheduling algorithm based on the resources' fuzzy clustering named FCBWTS. The major objective of scheduling is to minimize makespan of the precedence constrained applications, which can be modeled as a directed acyclic graph. In FCBWTS, the resource characteristics of cloud computing are considered, a group of characteristics, which describe the synthetic performance of processing units in the resource system, are defined in this paper. With these characteristics and the execution time influence of the ready task in the critical path, processing unit network is pretreated by fuzzy clustering method in order to realize the reasonable partition of processor network. Therefore, it largely reduces the cost in deciding which processor to execute the current task. Comparison on performance evaluation using both the case data in the recent literature and randomly generated directed acyclic graphs shows that this algorithm has outperformed the HEFT, DLS algorithms both in makespan and scheduling time consumed. Copyright © 2014 John Wiley & Sons, Ltd.     

Multi-objective Energy Aware Scheduling of Deadline Constrained Workflows in Clouds using Hybrid Approach

Cloud computing is undoubtedly one of the most significant advances in the domain of information technology. It facilitates elastic and on-demand provisioning of high performance computing capabilities employing pay-per-use model that has snowballed its adoption by scientists and engineers over the past few years. They often exploit workflows to represent their massive applications. Workflow scheduling in cloud has been devoted considerable investigation by researchers owing to its NP-complete nature of problem. Most of the previous studies targeted optimization of schedule length and execution cost within given deadlines/budget restrictions, or both. However, enormous energy consumption in the cloud data centers is not only negatively impacting the environment but also resulting in increased operational costs and thus cannot be ignored. Efficient scheduling strategies can significantly lessen the energy usage while complying with the user’s Quality of Service limitations. This research study proposes a Hybrid Approach for Energy aware scheduling of Deadline constrained workflows (HAED) using Intelligent Water Drops algorithm and Genetic Algorithm, which provides non-dominated solutions to the user. In particular, it focuses on multiple objectives i.e. reduction of schedule length, execution cost and energy usage within deadlines specified by the user. Its performance has been assessed on four scientific workflows from diverse domains using hypervolume and set coverage. The results achieved with the simulations demonstrate that the solutions produced by HAED are of better quality in terms of accuracy and diversity than non-dominated sorting genetic algorithm and hybrid particle swarm optimization.

     

Task Scheduling and Lightpath Establishment in Optical Grids

Data-intensive Grid applications require huge data transferring between multiple geographically separated computing nodes where computing tasks are executed. For a future WDM network to efficiently support this type of emerging applications, neither the traditional approaches to establishing lightpaths between given source destination pairs are sufficient, nor are those existing application level approaches that consider computing resources but ignore the optical layer connectivity. Instead, lightpath establishment has to be considered jointly with task scheduling to achieve best performance. In this paper, we study the optimization problems of jointly scheduling both computing resources and network resources. We first present the formulation of two optimization problems with the objectives being the minimization of the completion time of a job and minimization of the resource usage/cost to satisfy a job with a deadline. When the objective is to minimize the completion time, we devise an optimal algorithm for a special type of applications. Furthermore, we propose efficient heuristics to deal with general applications with either optimization objective and demonstrate their good performances in simulation.     

Task scheduling accuracy analysis in optical grid environments

Currently optical networks have been employed to meet the ever-increasing data transfer demands of grid applications and thus give rise to the concept of an “optical grid”. Task scheduling is an important issue for an optical grid, for it optimally allocates both grid and optical network resources to accelerate application execution and increase the resource utilization ratio. However, most task scheduling algorithms based on theoretical models may generate accuracy deviations between the scheduled results and the actual finish time of the applications. Accuracy deviations may lead to inefficient resources utilization and unsatisfied Quality of Service (QoS). This paper aims to improve the accuracy of task scheduling algorithms in optical grid environments. We first propose the theoretical task scheduling algorithm and demonstrate that the scheduling result is deviated with actual finish time in the real optical grid environment. Then, we reveal several factors which are likely to influence scheduling accuracy and develop a realistic task scheduling algorithm. We evaluate the theoretical and realistic task scheduling algorithms in our optical grid testbed. The experimental result shows the scheduling accuracy can be improved significantly by the realistic task scheduling algorithm.