当前位置:文档之家› 基于云计算环境的蚁群优化计算资源分配算法

基于云计算环境的蚁群优化计算资源分配算法

基于云计算环境的蚁群优化计算资源分配算法华夏渝,郑骏,胡文心(华东师范大学计算中心,上海200241)摘要:针对云计算的性质,提出一种基于蚁群优化(Ant Colony Optimization )的计算资源分配算法。

分配计算资源时,首先预测潜在可用节点的计算质量,然后根据云计算环境的特点,通过分析诸如带宽占用、线路质量、响应时间等因素对分配的影响,利用蚁群优化得到一组最优的计算资源。

通过在Gridsim环境下的仿真分析和比较,这种算法能够在满足云计算环境要求的前提下,获得比其他一些针对网格的分配算法更短的响应时间和更好地运行质量,因而更加适合于云环境。

关键词:云计算;网格;蚁群;资源分配中图分类号:TP316 文献标识码:AAnt Colony Optimization Algorithm for Computing Resource Allocation Based OnCloud Computing EnvironmentHua xia-yu, Zheng jun, Hu wen-xin(Computer Center Institute, East China Normal University Shanghai, 200241) Abstract:A new allocation algorithm based on Ant Colony Optimization (ACO) was established to satisfy the property of Cloud Computing. When start, this algorithm first prognosticated the capability of the potential available resource node, and then analyzed some factors such as network qualities or response times to acquire a set of optimal compute resources. This algorithm met the needs of cloud computing more than others for Grid environment with shorter response time and better performance, which were proved by the simulation results in the Gridsim environment.Key words: Cloud Computing; Grid; Ant Colony Optimization; resource allocation0引言云计算(Cloud Computing),是指通过互联网连接的超级计算模式,包含了分布式处理(Distributed Computing)、并行处理(Parallel Computing)和网格计算(Grid Computing)的相关技术,或者说是这些计算机科学概念的商业实现。

云计算一种新型的共享基础架构,可以将巨大的系统池连接在一起,以运营商和客户的方式,通过互联网为用户提供各种存储和计算资源。

在云计算环境中,用户将自己的个人电脑,PDA或移动电话等其他设备上的大量信息和处理器资源集中在一起,协同工作。

这是一个大规模的分布式计算模式,该模式由运营商的经济规模决定,并且是抽象的,虚拟化的以及规模动态可变的。

其主要内容为受管理的计算能力,存储,平台和服务。

这些内容通过互联网,按需分配给外部用户,其重要意义在于将计算能力作为一种商品在互联网上进行流通。

云计算的主要优势:快速地降低硬件成本和提升计算能力以及存储容量,用户可以以极低的成本投入获得极高的计算能力,而不用再投资购买昂贵的硬件设备,负担频繁的保养与升级计算资源分配是云计算技术的一个重要组成部分,其效率直接影响整个云计算环境的工作性能。

由于云计算有很多独特的特性,使得原有的针对网格计算的资源分配和调度算法已无法在该环境中有效的工作。

本文提出的蚁群优化分配算法,综合考虑了云计算的一系列特点,以期在这种环境中能够高效地为用户作业分配合适的计算资源。

1 问题描述云计算由网格计算演变而成,并将网格计算作为其骨干和基本结构。

可以说,云计算是网格计算的一种更高级的形式。

但是,这两者之间在现实中存在着巨大的区别,具体可以参见文献[1]。

云计算提供了更多抽象的资源和服务。

这些资源和服务可划分为三个类别,分别是软件即服务(Software as a Service),平台即服务(Platform as a Service)和设备即服务(Infrastructure as a Service) [2,3]。

在软件即服务(SaaS)中,用户会得到一个特殊用途的客户端,该客户端允许用户通过互联网进行远程访问,并且基于使用情况来收取费用。

在平台即服务(PaaS)中,运营商提供一个高等级的综合环境来生成,测试以及部署用户定义的应用。

这种综合环境是一种对开发环境抽象地封装和对有效服务负载地封装。

在设备即服务(IaaS)中,运营商参照和用户达成的服务品质协议(Service-Level Agreement),通过提供硬件,软件和设备(主要是在统一资源层,不过同样也能在组织层),来提供一个完整的软件应用环境,并以资源使用量来收费。

在该级别的服务上,根据云计算环境的弹性特点,提供设备的规模会根据用户应用对资源的需求量来动态地增大或者缩小,比如用户需要用T 个进程,云计算环境就分配给该用户R 的计算资源,如果用户将进程数增加到2T ,则用户的计算资源占有量将动态地扩展到2R 。

本文论述的计算资源分配策略,也充分考虑了云计算的这一特性。

在设备即服务这一级别中,用户的所有数据和配置被封装成为用户镜像[2],分散存储在云环境的各个存储节点上。

由于可运营性的约束,云计算环境的网络可用带宽远比网格环境小得多。

比如,一个传统的企业级计算设施一般都拥有10G 的超高速以太网,高性能计算资源将通过该网络直接和存储区域网络(Storage Area Network )相连。

而在云计算环境中,比如Amazon 公司的EC2(Elastic Compute Cloud)[4]系统只提供了250MB 的可用带宽,并且所有的虚拟服务器都通过单一的一条250MB 连接来访问其存储系统S3(Simple Storage Service)[5]。

所以,在云计算环境中,局域的带宽需要被充分地利用,一个行之有效的方法便是尽量为存储节点资源分配本地的计算资源。

对于本文论述的算法来说,就是尽量为存有用户镜像的本地存储节点分配本地或邻近带宽需求少的计算节点。

云计算环境的运营目标之一是将计算能力作为服务来供用户购买。

企业与个人用户无需再投入昂贵的硬件购置成本,只需要通过互联网来购买租赁计算力,把自己的个人计算机当做接入口,一切都通过互联网连接到云计算环境中,完成对计算能力的获取。

但是,这也预示着云计算的规模会非常巨大。

同时,区别于网格的独占式的资源分配模式,整个云域中的资源将会被所有的用户同时共享,以保证对延迟敏感的作业在云上能够很好的运行。

这意味着在云计算中用户的作业将被划分为进程甚至是线程的粒度级别。

所以,云计算对计算资源分配算法有着苛刻的要求。

本文重点论述的计算资源分配算法,就是要通过对存储节点分配最合适的计算资源,来最大程度的提高云计算环境在提高计算资源上/方面的有效利用率。

2算法描述基于上述云计算环境的特点,我们提出以下资源分配算法。

2.1计算资源的分配流程参照Map/Reduce 提出的云计算框架[6,7],云环境中的每个单元由一个单独的主作业调度节点(master JobTracker)和每个节点集群中的一个从任务分配节点(slave TaskTracker)共同组成。

主节点负责调度构成一个作业的所有任务,这些任务的数据资源分布在不同从节点的存储资源上的用户镜像分片中,主节点监控它们的执行,以及重新执行已经失败的任务。

而从节点仅负责执行由主节点指派的任务。

在接到主节点指派的任务之后,从节点开始为其下属的存储节点寻找合适的计算节点。

首先,该从节点开始检测自身的计算资源余量,如果其剩余计算资源足以满足用户提交作业的用量,则优先分配自身的计算资源,如果资源已经耗尽或者已不足以满足承诺给用户的最小计算资源量,则开始搜寻云环境中合适的其他计算资源。

本文介绍的蚁群分配算法将在这一环节中实现。

搜索在一定范围内进行,目的是为了减小所带来的网络开销。

如果仍然没有合适资源,则从节点报请主作业调度节点移走该节点集群中的用户数据镜像分片。

2.2计算资源优劣度评判条件将slave 节点域看作是一个无向图G(V,E),其中V 是区域Area 中所有slave 节点的集合,E 是连接各slave 节点的网路集合。

寻找合适的计算节点,也就是在E 中寻找一条最优的路径e ∈Area ,其度量标准可以考虑如下几个因素:①预计执行时间:time_cost(e), 指路径e 尽头的计算资源处理该作业预计的耗费时间. ②网路带宽:bandwidth(e),指路径e 所提供的网络最大带宽。

③网络延迟:delay(e),指路径e 产生的最大网络延迟。

设资源选择的约束函数为:Atime_cost(e)+Cdelay(e)res(e)=Bbandwith(e)(1)time_cost(e)<TL s.t bandwith(e)>EL delay(e)<DL ⎧⎫⎪⎪⎨⎬⎪⎪⎩⎭(2)则选择资源和路径的过程就是寻找满足限制条件(2)的尽量小的res(e)的路径和资源的过程,其中A ,B ,C 为三个约束条件的权重;TL ,EL 和DL 为其边界限制条件。

不同的云计算环境可能会有不同的取值。

2.3对各个计算资源完成本次作业执行速度的预测由于在整个云环境中,异构是其非常重要的一个特点。

也就是说,每个节点的结构,软硬件环境,容量,吞吐量等性能都会不同。

同时,网络的情况也比较复杂,任意线路在任意时候的负载将不可预知。

由于云计算环境中的网络带宽远比传统的网格环境带宽低,网络的情况也会有不可预期的大幅度变化。

因此,对节点完成工作所执行速度的计算将会非常困难。

但是,在云计算中,把任务分配给效率最高,开销最少的计算资源将会极大地提高整体的性能。

所以,在分配中需要对潜在的可分配节点进行执行速度预估。

针对云计算异构和变化的特点,我们通过参考文献[8]中的预测算法,设计了一个通过积累历史值来推算下一任务执行速度的预测模型。

相关主题