Method for reducing cloud workflow completion time under the task interruption

As more and more large-scale scientific workflows are delivered to clouds,the business model of workflow-as-a-service is emerging.But there are many kinds of threats in the cloud environment,which can interrupt the task execution and extend the workflow completion time.As an important QoS parameter,the workflow completion time is determined by the critical task path.Therefore,critical path redundancy method is proposed to create a redundant path having the interact parallel relationship with the critical path,which can provide the protection for the tasks in the critical path and reduce the probability of the critical path interruption.Computing instance allocation is an essential part of the cloud workflow execution,since only the tasks assigned the instance can begin execution.In order to further reduce the workflow completion time,computing instance allocation algorithm based on HEFT(heterogeneous earliest finish time)is proposed.The algorithm considers diverse task dependency relationships and takes full advantages of the critical path redundancy method,which can improve the efficiency of workflow execution.Experimental results demonstrate that the proposed method can effectively reduce the cloud workflow completion time under the task interruption.

Graphical-based data placement algorithm for cloud workflow

When workflow task needs several datasets from different locations in cloud,data transfer becomes a challenge.To avoid the unnecessary data transfer,a graphical-based data placement algorithm for cloud workflow is proposed.The algorithm uses affinity graph to group datasets while keeping a polynomial time complexity.By integrating the algorithm,the workflow engine can intelligently select locations in which the data will reside to avoid the unnecessary data transfer during the initial stage and runtime stage.Simulations show that the proposed algorithm can effectively reduce data transfer during the workflow's execution.

Trust Based Meta-Heuristics Workflow Scheduling in Cloud Service Environment

Cloud computing has emerged as a new style of computing in distributed environment. An efficient and dependable Workflow Scheduling is crucial for achieving high performance and incorporating with enterprise systems. As an effective security services aggregation methodology, Trust Work-flow Technology (TWT) has been used to construct composite services. However, in cloud environment, the existing closed network services are maintained and functioned by third-party organizations or enterprises. Therefore service-oriented trust strategies must be considered in workflow scheduling. TWFS related algorithms consist of trust policies and strategies to overcome the threats of the application with heuristic workflow scheduling. As a significance of this work, trust based Meta heuristic workflow scheduling (TMWS) is proposed. The TMWS algorithm will improve the efficiency and reliability of the operation in the cloud system and the results show that the TMWS approach is effective and feasible.

Multi-objective workflow scheduling in cloud system based on cooperative multi-swarm optimization algorithm

In order to improve the performance of multi-objective workflow scheduling in cloud system, a multi-swarm multiobjective optimization algorithm(MSMOOA) is proposed to satisfy multiple conflicting objectives. Inspired by division of the same species into multiple swarms for different objectives and information sharing among these swarms in nature, each physical machine in the data center is considered a swarm and employs improved multi-objective particle swarm optimization to find out non-dominated solutions with one objective in MSMOOA. The particles in each swarm are divided into two classes and adopt different strategies to evolve cooperatively. One class of particles can communicate with several swarms simultaneously to promote the information sharing among swarms and the other class of particles can only exchange information with the particles located in the same swarm. Furthermore, in order to avoid the influence by the elastic available resources, a manager server is adopted in the cloud data center to collect the available resources for scheduling. The quality of the proposed method with other related approaches is evaluated by using hybrid and parallel workflow applications. The experiment results highlight the better performance of the MSMOOA than that of compared algorithms.

云边协同环境下基于局部关键路径的工作流应用调度策略

针对不确定性云边协同环境下工作流应用调度问题,考虑服务器的负载压力、网络拥塞等计算环境因素造成计算性能和传输带宽的不稳定性,采用三角模糊数表示模糊云边协同环境中服务器的计算性能和传输带宽.对于泊松到达的多工作流应用,提出一种基于局部关键路径的多工作流应用调度策略,将局部关键路径作为调度单元进行统一调度,充分避免任务之间的数据传输,旨在满足多工作流应用截止日期约束的前提下,降低其模糊执行代价.仿真结果表明,与其他基准策略相比,在不同的截止时间约束下,该策略都能获得多工作流应用最优的可行调度方案,同时实现了模糊执行代价的有效优化.

Cloud GIS关键技术研究

研究并分析了现有GIS应用系统的不足,根据目前GIS应用发展的主要技术趋势,提出了基于云计算的云GIS的服务层次模型和关键技术。针对云计算分布式异构环境下空间数据资源的特点,提出了云GIS空间数据资源的两种集成方法;根据现有GIS应用技术特点,提出云GIS功能资源的集成与互操作技术,并与工作流结合GIS Web服务组合技术的云GIS搭建式应用开发技术。最后,提出云GIS应用的3种部署模式。

通信计算联合优化的图分割工作流部署方法

为提高计算效率,将复杂的大规模任务分解为简单任务并建模为工作流,交由并行分布式计算集群来完成,已成为云中心处理持续增长的计算和网络任务的重要手段。然而,分布式计算的任务间数据传输所带来的通信带宽占用却容易造成云中心的网络拥塞。如何兼顾计算效率和通信开销,科学地部署工作流意义重大。两类典型的工作流部署算法为基于列表的部署算法和基于分簇的部署算法。然而,前者致力于提高计算效率,未关注工作流中任务之间的通信开销,大规模工作流的部署易带来较重的网络负荷;后者关注通信开销的最小化,但牺牲了工作流中任务的并行计算效率,导致工作流完成时间较长。文中从图论的角度出发,充分挖掘工作流中各任务之间的依赖性和并行性,通过对经典图分割算法进行改进,实现了工作流任务分区过程中通信开销最小化和计算并行性最大化之间的平衡。仿真结果表明,在不同的工作流规模下,所提算法的通信开销比列表部署算法平均减少约35%~50%,工作流完成时间比分簇部署算法平均降低约50%~65%,且对于具有不同通信计算比的工作流均具有良好的稳定性。

基于二维编码两阶段协同进化遗传算法的云工作流调度优化

针对当前启发式算法依赖于特定问题,元启发式方法存在搜索空间不完备或在完备空间上搜索效率不高,以及传统一维编码存在冗余空间等问题,提出一种基于二维编码两阶段协同进化遗传算法(TDTSGA)的云工作流调度优化方法。在TDTSGA中采用一种新的二维个体编码方法,设计了基于二维层次排序和拓扑排序的交叉变异方法,同时采用了两阶段协同进化策略。通过在各种工作流应用案例上进行广泛实验,验证了TDTSGA的优越性。

混合自适应粒子群工作流调度优化算法

针对具有截止期的云工作流完成时间与执行成本冲突的问题,提出一种混合自适应粒子群工作流调度优化算法(HAPSO)。首先,基于截止期建立有向无环图(DAG)云工作流调度模型;然后,通过范数理想点与自适应权重的结合,将DAG调度模型转化为权衡DAG完成时间和执行成本的多目标优化问题;最后,在粒子群优化(PSO)算法的基础上引入自适应惯性权重、自适应学习因子、花朵授粉算法的概率切换机制、萤火虫算法(FA)和粒子越界处理方法,从而平衡粒子群的全局搜索与局部搜索能力,进而求解DAG完成时间与执行成本的目标优化问题。实验中对比分析了PSO、惯性权重粒子群算法(WPSO)、蚁群算法(ACO)和HAPSO的优化结果。实验结果表明,HAPSO在权衡工作流(30~300任务数)完成时间与执行成本的多目标函数值上降低了40.9%~81.1%,HAPSO在工作流截止期约束下有效权衡了完成时间与执行成本。此外,HAPSO在减少完成时间或降低执行成本的单目标上也有较好的效果,验证了HAPSO的普适性。

一种改进樽海鞘群算法及其多目标云工作流调度应用

为了优化云工作流应用的调度效率与代价,提出基于改进樽海鞘群算法的工作流调度策略。建立截止时间与预算约束的多目标优化模型,利用樽海鞘觅食的位置变化对工作流调度进行编解码,设计融合执行跨度与执行代价的权重适应度函数。为了增强樽海鞘群的寻优性能,引入基于疯狂算子的领导者更新模式,通过疯狂变量,减少领导者更新的停滞早熟现象;引入遗传算子的追随者更新模式,利用个体交叉和变异使樽海鞘群具有更均衡的搜索全局性和个体多样性,避免陷入局部最优。结果证明,改进樽海鞘群算法可以有效提升计算精度和收敛速度;应用于工作流调度求解后,其调度解收敛性更好,调度解集空间分布更加一致。

IaaS云满足预算约束的工作流应用调度算法

为了解决IaaS(Infrastructure as a Service)云的工作流调度优化问题,提出基于预算约束的工作流调度算法。以最小化工作流调度时长为目标,算法分调度任务选择和虚拟机实例选择两阶段进行。第一阶段将工作流任务依据依赖关系作层次划分,同层次组成包任务,以Min-Max方法对层次任务估算时间作标准化处理,定义最迟完成时间与最早完成时间差值最大者为调度任务;第二阶段在期望预算下以最早完成时间最小为标准选择资源,实现任务与资源间的映射。利用算例阐述了算法实现过程,并通过仿真实验测试了算法性能。结果证实,改进算法执行效率与调度成功率优于同类算法。

云中使用竞价实例的截止时间约束的工作流调度优化算法

近年来,由于按需资源供应和即付即用付费模式具有的明显优势,在云环境中执行大规模工作流应用程序越来越流行。云服务提供商以不同的价格提供不同性能的资源。为了提高资源的利用率,许多云服务商提供的瞬时资源的价格远低于正常资源的价格,Amazon EC2提供的竞价实例,可以大大降低工作流的执行成本。云中工作流调度的主要问题之一是在满足用户给定的截止时间约束的前提下,找到一种更廉价的调度方法。为解决这个问题,提出了一种使用竞价实例的截止时间约束工作流调度优化算法(Spot-ProLis)。该算法考虑了同一虚拟机上数据传输时长为零的情况,使用概率向上排序的方法对任务进行排序。在资源配置阶段,增加了竞价实例作为候选资源,有效降低了执行成本。实验结果表明,相比经典算法ProLis,所提算法在降低执行成本上具有显著优势。

基于多维度特征融合的云工作流任务执行时间预测方法

任务执行时间估计是云数据中心环境下工作流调度的前提.针对现有工作流任务执行时间预测方法缺乏类别型和数值型数据特征的有效提取问题,提出了基于多维度特征融合的预测方法.首先,通过构建具有注意力机制的堆叠残差循环网络,将类别型数据从高维稀疏的特征空间映射到低维稠密的特征空间,以增强类别型数据的解析能力,有效提取类别型特征;其次,采用极限梯度提升算法对数值型数据进行离散化编码,通过对稠密空间的输入向量进行稀疏化处理,提高了数值型特征的非线性表达能力;在此基础上,设计多维异质特征融合策略,将所提取的类别型、数值型特征与样本的原始输入特征进行融合,建立基于多维融合特征的预测模型,实现了云工作流任务执行时间的精准预测;最后,在真实云数据中心集群数据集上进行了仿真实验.实验结果表明,相对于已有的基准算法,该方法具有较高的预测精度,可用于大数据驱动的云工作流任务执行时间预测.

最后期限动态分配的三步云工作流调度算法

现如今,云环境中的工作流调度问题依然很有挑战性.它的一个重要任务是找到一种能够满足最后期限约束且执行成本最优的调度方案.三步的列表调度算法可以有效地解决这一问题.该算法首先将最后期限分配到每个任务,形成任务子期限;之后再利用两步列表调度策略为每个任务分配资源.然而现有的最后期限分配策略均只能形成静态的子期限,因此还可以进行进一步的优化.本文采用三步列表调度算法进行云工作流调度,并提出一种基于粒子群的动态最后期限分配方法(DY-DD).实验结果表明,相比于其它经典调度算法,本文提出的算法在成功率和执行成本上均具有优势.

基于动态资源选择策略的微服务工作流调度算法

为解决现有云中工作流调度算法在面对大量微服务任务组成的工作流时出现整体调度成本偏高的问题,提出一种基于动态资源选择策略(dynamic resource selection strategy, DRSS)的微服务工作流调度算法——DRSS调度算法。利用任务在工作流中的位置确定任务的子截止期以及调度优先级,采用动态资源选择策略对任务进行调度,获得任务执行的最优资源,在此基础上更新任务状态以及虚拟机实例的资源向量。实验结果表明,该算法在调度成功率与成本方面上较同类算法更优。

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。

基于混合云技术的媒体融合系统设计

为满足融媒体中心对高效、低成本、高可靠性的媒体融合服务需求,设计一个基于混合云技术的媒体融合系统。首先,通过公有云和私有云搭建混合架构,包括用户、混合云管理、混合云三个多源信息合成模块。其次,根据混合云环境的特点和用户需求,设计资源混合模型,包括数据层、特征层和决策层三个层次,并基于证据组合规则、DAG工作流模型对三个层次进行优化。最后,测试系统性能(即所用时间和成本)并与其他方案进行比较。结果表明,所设计的融合任务的通过率保持在100%,在时间和成本上的花费低于其他算法50%以上,系统稳定性较高。提出的媒体融合系统可被实际推广应用。

基于离散粒子群优化的云工作流调度

针对云工作流调度问题面临的安全威胁,首先采用云模型量化任务与虚拟机资源的安全性,通过安全云相似度衡量用户对任务所分配虚拟机资源的安全满意程度;然后建立考虑安全性、完成时间和使用费用的云工作流调度模型,并提出基于离散粒子群优化的云工作流调度算法;最后对所提算法进行仿真实验。实验结果表明,与同类算法相比,该算法在安全效用值、完成时间、使用费用和负载均衡离差方面具有较好的性能表现。

面向云计算的工作流技术

云计算的发展,对提高服务质量与压缩运行成本提出了新的要求.在此背景下,工作流技术被认为是一种较为优越的解决方案:从云计算用户的角度看,工作流提供了对复杂应用的抽象定义、灵活配置和自动化运行;从云计算服务提供者的角度看,工作流实现了任务的自动调度、资源的优化和管理.文章介绍工作流技术与云计算;阐述了云工作流产生的背景;深入剖析了云工作流的技术特征以及与其他工作流(业务工作流、网格工作流)的异同;列举了云工作流的4个实现案例,并对其进行比较.最后,在总结全文的同时,展望了云工作流技术的发展前景.

任务调度算法中新的自适应惯性权重计算方法

粒子群算法(particle swarm optimization,PSO)是解决云计算环境中工作流系统的任务调度优化问题的主流智能算法.然而基于传统自适应惯性权重的粒子群任务调度算法易陷入局部最优,导致调度方案的执行时间与费用较高.因此,通过改进单个粒子的成功值计算方法,提出了一种新的自适应惯性权重计算方法 NAIWPSO(new adaptive inertia weight based particle swarm optimization).该方法通过比较每个粒子的适应度与全局最优值,可以更加精确描述粒子状态,进而提高了权重的自适应性.在新惯性权重基础上,提出了一种解决云工作流系统中任务调度优化问题的改进粒子群算法.新权重可以更准确的调整粒子速度,使算法更好地平衡粒子全局与局部搜索,避免陷入局部最优,获得执行费用更优的调度方案.实验表明,与5种已有惯性权重算法比较,新算法收敛稳定、适应度最低、执行费用平均减少18%.