基于云基础设施的服务部署优化问题建模*

颉　斌，杨　扬，旷　毅（北京科技大学 计算机通信工程学院，北京 100083）

基于云基础设施的服务部署优化问题建模*

颉斌，杨扬，旷毅
（北京科技大学 计算机通信工程学院，北京 100083）

目前典型的云基础设施提供商所提供的虚拟机资源都是有限的规格类型，当同一个服务部署在不同配置的虚拟机上时，会体现出不同的性能。通过对基于云基础设施的SaaS层服务部署情况进行研究和分析，提出对服务部署策略进行优化的必要性，并将该服务部署优化问题抽象为多目标组合优化问题，对其进行数学建模；然后利用排队论，得出优化指标的计算方法，并进行实验验证。

云计算；服务部署优化；多目标组合优化

0　引言

云计算供应商提供了常见的可从Web浏览器获取的在线服务应用，通常用基础设施即服务（Infrastructure as a Service，IaaS）、平台即服务（Platform as a Service，PaaS）和软件即服务（Software as a Service，SaaS）3个层次来表示。

SaaS可基于传统计算架构提供，也可基于云计算架构提供。在基于云计算架构部署SaaS时，可直接在IaaS层之上部署，也可在PaaS层之上进行部署。IaaS层中的资源，尤其是虚拟机形式的资源，常常是有限的。目前典型的 IaaS提供商所提供的虚拟机资源一般是固定的几种，SaaS提供商在利用 IaaS层中的资源部署应用时，需要考虑部署应用的虚拟机规格。

由于不同类型的用户对 SaaS层的应用服务有不同的服务质量需求，服务提供商需要与不同类型的用户分别签订服务等级协议，以满足其需求。此外，要部署的应用通常由多个不同的服务及其工作流组成，构成应用的每个服务可以生成多个服务实例，每个服务实例部署在不同配置的虚拟机上体现出的性能也不同。因此，对于云供应商而言，服务部署是要实施的最重要的任务。

1　服务部署优化问题分析

1.1SaaS层服务部署方式

云服务是指服务提供者向服务使用者提供的任何类型的IT功能。云服务的典型类别包括基础架构、平台、软件或业务流程服务，常用 IaaS、PaaS和 SaaS 3个层次来表示［1］。本文主要研究SaaS层的服务部署，它的部署方式有基于PaaS平台和基于IaaS平台两种，图1和图2分别表示了这两种方案。

若SaaS层应用要以独立于平台的方式部署在云上，IaaS一定是最佳选择。应用开发者或SaaS提供商可租用IaaS提供商提供的各种虚拟机（Virtual Machine，VM），将应用部署到云环境中，以 SaaS的形式提供给最终用户使用［2］。但是，IaaS层中的资源，尤其是虚拟机形式的资源，不同配置规格提供不同的服务质量，也需要不同的服务价格。

图1　基于PaaS的SaaS部署架构

图2　基于IaaS的SaaS部署架构

1.2优化问题提出

在SaaS中，服务提供商通过接口将功能和数据封装成应用提供给用户访问。应用可以理解成服务的集合。服务可以单独访问，也可以组合访问［3］。因此，一个复杂的应用服务通常是由一组子服务以及这些子服务构成的工作流组成。工作流定义了服务之间的交互方式。

不同的SaaS层用户对应用服务有不同的服务质量需求。为了满足不同的服务等级协议（Service Level A-greement，SLA）［4］，SaaS提供商在部署SaaS层的应用服务时，需要考虑使用由 IaaS提供商提供的哪种 VM配置方案以及每个服务需要多少服务实例，从而为每类用户优化服务部署。由于SLA中需要满足的性能指标较多且可能冲突，同时可能的服务实例和VM类型的组合也较多，因此部署决策问题实际是一个多目标组合优化问题。

2　问题的抽象与建模

总结前文分析，可将云计算环境中的服务部署优化问题的基本模型概括为：IaaS提供商给定一组不同配置和价格的虚拟机，SaaS提供商利用这些虚拟机资源部署应用。应用由一组服务及其工作流组成。SaaS提供商需要找到一种部署应用的方案，实现在满足不同类型的用户的服务质量需求的情况下，最小化部署费用。

应用中每个服务可生成任意多个服务实例，同一个虚拟机上也可以部署多个不同的服务实例，因此，服务实例与虚拟机的组合结果是无限的。优化目标包括延迟、吞吐量和费用，它们无法统一为一个量纲，并存在相互制约关系。

由此可见，云计算环境中的服务部署优化问题是一个典型的多目标组合优化问题，问题初始化变量包括服务实例、虚拟机类型以及优化指标，可做如下数学描述：

其中，S代表组成应用的所有服务集合，si对应服务 i；V为云环境中由IaaS提供商提供的所有虚拟机类型集合，vi对应虚拟机类型i；O代表可优化的 SLA中的指标，如延迟、吞吐量、费用等，每个指标都有对应的边界值，使其在实际问题中有现实意义，这里用 gi（o）≥Ki表示。

S和V中的元素可以任意组合，数学表述如下：

其中，式（7）表示一个 r（rk）代表某个服务实例（si）部署到某种虚拟机（vj）。R为服务部署的具体方案。式（10）表示一个部署方案R必须保证所有服务实例都被部署。式（11）说明一个部署方案R中，某些服务实例可能被部署多次。图3表示了某部署问题中，某种部署方案Ri的生成方式。

图3　部署方案生成示例

由于R所占用的虚拟机种类及数量会随集合值的不同而不同，因此，不同R会对应一组不同的O值。R所包含元素的组合方式有很多种，因此服务部署方案，也就是问题的数学解集RX（式（12））的元素有无穷多个，其中元素Ri代表了一种具体的部署方案，根据 Ri占用的虚拟机资源可得到 Oi，Oi包含了所有要优化的目标值，所有 Oi组成的集合定义为 OX，即式（13）。

服务部署优化的问题对应于其数学模型上的求解为在RX中的众多元素中找到合适的Ri值，使得其对应的Oi值能最好地满足 SLA中规定的各项指标，该 Ri即为优化服务部署方案。

3　优化指标计算及验证

3.1云环境中的 SLA

SLA是服务提供者和服务需求者之间定义的关于服务的具体水平的正式协议，包括服务描述、服务等级参数、保证以及所有违例情况的行动和补救措施［5］。SaaS应用中的SLA主要关注的是与 SaaS应用的服务质量相关的性能参数，例如响应时间、吞吐量、可靠性、易用性、可扩展性和操作便捷性等［6］。为了简化问题，本文选取响应时间、吞吐量和费用3个目标进行优化。

3.2服务实例的吞吐量和延迟

设μ是平均单位服务速率，它是平均请求处理时间的倒数。基于μ，当一个服务实例在多种不同请求到达率下运行在一个具有多种VM配置的部署方案上，可利用排队论来评估服务实例的吞吐量和延迟。

服务请求的到达可将其表示为一个泊松分布。λ是平均请求到达率，即单位时间内对一个服务实例的请求的平均数量。

对一个确定的服务实例而言，它对每个请求的服务处理时间一般是固定的，因此将服务实例建模为一个M/D/1排队，即泊松到达、确定服务时间和单服务窗口。

M/D/1排队系统的服务时间Tn是定长分布。据Little公式，可得顾客平均排队等待时间为［7］：

服务的处理时间与排队等待时间相比，通常可忽略不计，因此，延迟时间等于排队等待时间。把式（14）中，可得延迟时间为：

既然μ已知，当λ给定时，Wq就可以计算出来。当λ＞μ时，所有n个CPU核的使用率都超过了100%，此时的服务实例吞吐量就是μ；而当 λ≤μ时，服务实例的吞吐量即为λ。

3.3端到端的QoS值

由于云环境中的一个应用是由一组服务及其工作流组成的，因此，在计算出应用中各个服务实例的延迟、吞吐量、费用等优化指标值之后，还需要计算整个应用的总优化指标值，即端到端的QoS（Quality of Service）值。

组成应用的各服务之间存在串联、并联和分支等多种情况，对同一个服务而言，也可能是一个或多个服务实例同时提供服务。因此，在计算端到端的 QoS值时，需分别考虑这些情况。

3.4仿真实验验证

本文用MATLAB等工具对前述理论计算公式进行了实验验证。

图4为在单服务实例情况下，当服务速率μ分别为15 req/s、24 req/s、32 req/s时，在不同请求到达率下的平均延迟曲线图。可以看出，当用户请求到达率λ小于服务速率μ时，测量值与理论值曲线的吻合度较高，误差较小；当λ接近μ时，据式（15）可知，延迟值将趋近无限大；当λ＞μ时，理论值公式不再适用，因此与图4所示实际值误差较大。综上所述，当λ＜μ时，该排队模型和计算公式能够较为精确地表示单服务实例的延迟值。

图4　单服务实例平均排队延迟图

这里也对端到端的QoS值进行了验证。假设服务1、2、3和4的服务速率分别是 μ1=24 req/s，μ2=15 req/s，μ3=32 req/s，μ4=32 req/s，图 5为该应用在不同请求到达率下的端到端延迟值。可以看出，前述理论计算方法能够较为精确地表示端到端的延迟值。

图5　端到端的平均延迟曲线

4　结论

本文通过对云计算环境中的服务部署情况的详细分析，提出了在基于云基础设施对 SaaS层服务进行部署时进行优化的必要性。通过抽象和数学建模，将问题表示成一个多目标组合优化问题。最后利用排队论得出了SLA中的优化指标计算方法，并通过仿真实验进行了验证。

下一步研究中，可利用此优化模型，将实际情况与已有多目标优化算法结合，设计出适用于本研究课题的优化算法，并通过仿真实验对算法的有效性进行验证。

［1］徐星，周剑雄，王明哲.基于模型仿真的云计算 PaaS构建模式选择［J］.微电子学与计算机，2014（6）：91-96.

［2］曹伟杰，贺建民，孙志丹.IaaS模式下虚拟机部署机制研究［J］.计算机技术与发展，2012，22（10）：105-108.

［3］张晓娟，易明巍.基于云计算与SOA的企业集成架构及实现［J］.计算机系统应用，2011，20（9）：1-6.

［4］冯国富，唐明伟，刘林源，等.基于服务级别协议的云资源分配［J］.计算机科学，2014，41（4）：36-39.

［5］张健.云计算服务等级协议（SLA）研究［J］.电信网技术，2012（2）：16-21.

［6］程旭.基于SLA的 SaaS应用性能管理机制研究 ［D］.济南：山东大学，2010.

［7］陆传赉.排队论［M］.北京：北京邮电大学出版社，2009.

Service deployment optimization problem modeling based on cloud infrastructure

Xie Bin，Yang Yang，Kuang Yi
（School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China）

The typical cloud infrastructure providers only provide limited types of specifications of virtual machine resources. When the same service is deployed on a different configuration of the virtual machine，it will reflect the different performance.Based on the research and analysis of the service deployment in SaaS，this paper puts forward the need to optimize the service deployment strategies，and abstracts it to a multi-objective combinatorial optimization problem，then models it in mathematical way.

cloud computing；service deployment optimization；multi-objective combinatorial optimization

TP393

A

1674-7720（2015）02-0063-04

国家自然科学基金（61272508）

（2014-09-17）

颉斌（1970-），男，硕士，讲师，主要研究方向：计算机网络，图像处理与模式识别。

杨扬（1955-），男，博士，教授，主要研究方向：计算机网络，图像处理与模式识别。

旷毅（1988-），男，硕士，工程师，主要研究方向：计算机网络。