基于SLA网格计算资源分配框架.docVIP

基于SLA网格计算资源分配框架 　　摘要：资源最优分配问题是最优化理论中的一个经典问题。它的目标是：在一个特定的应用环境中，满足某种需求（时间限制、资源总数限制、服务自量限制等），使用有限的资源，最大程度完成多个任务，使得代价总和（通常是费用总和）最小。本文将给出在SLA限制下网格应用程序资源分配框架，同时给出最优分配的启发式算法。 　　关键词：网格；最优分配；SLA 　　 　　1．最优分配问题模型 　　问题的基本模型：有资源集合RS，在任务集合TR中分配，使得系统性能量度（目标函数）达到最优化。其中K种资源指代不同资源类型，例如计算资源(Computing Resource)、服务提供商资源（Service Providers Resource）、网络资源（Network Resource）、数据存储资源（Data Storage Resource）等，每种资源都是集合，所以RS通常为一矩阵，该矩阵有K个列向量代表有K种类型的资源，每个列向量表示某种资源的集合。即RSi表示第i种资源集合。 　　用ST表示一个可行的资源分配集合，则Map(TR,RS1)∈ST（i∈[1,K]）。“可行”意味着分配能满足基本要求，例如：满足不同服务质量（QoS）要求或者时间要求，完成任务。用Costrainti(ST)表示与资源分配矩阵ST相关的，完成任务TRi的限制条件；用Costi(ST)表示与资源分配矩阵ST相关的，完成任务TRi的所需的代价，这样，剩余资源分配问题可刻化如下： 　　在满足条件下，其中Con表示应用环境中的限制条件；剩余资源分配的目标函数可形式化为： 　　式(1)是一个非线性整数编程问题，也是一个NP-hard问题。在某些时候，有效的算法还取决于目标函数的形式。如果不能预先知道问题结构信息，就需要使用某种形式的有哪些信誉好的足球投注网站算法。为了清晰的描述问题，使用图1描述一个使用场景。 　　对图1的解释：用户通过Web UI使用网络资源，用户发送请求，根据请求的不同，选择不同的计算模型（Computing Model）（1）每种类型的用户请求实例包含一种限制，反映用户的需求，例如时间限制，换句话说，请求实例伴随着模型的选择和限制（也就是上文中的Con，Con可以根据要求进行扩展）。当Computing Model Provider接收到用户的请求时，创建Computing Model实例（2）每种计算模型需要从不同数据库集合里面选择数据进行计算，这些数据由服务提供商提供（3）这些数据被组装并被存储起来，这项服务由数据库提供商提供（4）Computing Model实例请求获取数据（5）并使用这些数据（6）进行计算，最后，将计算结果返回给用户（7） 　　2．网格应用与资源 　　为了进一部描述问题，假设只存在四种类型的资源：计算资源（compute resources），服务提供商资源（Service provider resources），网络资源（network resources），数据存储资源（data storage resource）。计算资源负责计算任务；SP是网络环境中提供基于请求的服务的节点（例如财政数据，法律数据，信用数据，健康数据等）；网络资源提供网络环境下，节点之间数据传输的带宽；数据存储负责网格计算中数据的存储。此外，服务提供商提供不同SLA（Service Level Agreement）限制下实现相同功能的服务。SAL是网络服务商和客户之间的协议，它详细定义了不同服务质量（QoS）的服务，通常不同等级的服务的费用是不同的。 　　使用图2来表示基于假设条件下的网格应用程序，它可以根据具体需求进行扩展。应用程序被形式化的定义成包含弧和节点的图形（类似于图2）。图2包含三种类型的节点： 　　 计算结点。这些结点处理计算任务，主要是完成计算模型所给出的计算任务。这些结点在图中用圆形表示。 　　服务结点。这些结点在图中使用矩形表示，它们被计算结点调用。 　　 逻辑数据存储结点。这些结点在图中使用圆柱形表示，它们表示计算数据的存储。这些逻辑数据存储元素必须通过网络映射到物理数据存储设备。 　　图2包含三种类型的弧： 　　 优先级弧。从任务ti到任务tj的弧意味着tj只能等待ti执行完，并向它传输完所有数据后才能开始执行。弧上的标签表示ti向tj传输的数据量。 　　 服务请求弧。从任务ti到服务sj的弧意味着在执行ti时调用服务sj。弧上的标签表示每次执行任务ti是调用服务tj的次数。任务ti可以按次序或并发地调用任意一种服务集合。为了表示按次序地调用服务，可以刻化从ti到si再到任务sk的弧，这意味着，ti先调用si，随后再调用sk。 　　 逻辑数据存储弧。这种弧线可以从任务ti到逻辑数据