计及客户等待时间的云计算效益模型

马 浩 陶 鹏 李 鹏 刘林青 赵 佩

1(国网河北省电力有限公司营销服务中心 河北 石家庄 050000) 2(国网河北省电力有限公司 河北 石家庄 050000)

0 引 言

作为与信息、软件和互联网相关的服务,云计算集成了大量资源和服务,并将其交付到互联网上。客户可以根据需要获得这些资源和服务,而无须考虑硬件的维护和管理。由于其卓越的特性,可以提高客户工作的效率和体验,并减少大量的设备开支和人力支出。而云服务供应商为了维持云计算的运行,将按使用付费的定价模型向客户收取必要的费用[1]。

通常,根据不同参与者的目的,可以将云计算环境视为三层结构,它由基础结构提供者、云服务提供者和客户组成。基础设施提供商维护物理设备,并通过采用虚拟化技术将其用于构建动态资源池。云服务供应商从基础设施提供商那里租用资源,并相应地支付租赁费用,同时,他们构建了用于向客户提供服务的云计算平台。客户根据自身的需求在平台上搜寻解决方案,并根据数量和质量对提供的服务收费。作为基础设施提供商和客户之间的链接,云服务供应商非常重要[2]。此外,效益是云计算平台正常运行的基础,它包括来自客户的收入和基础设施提供商的成本。

研究人员对市场需求、云计算平台中的参数配置、定价方式等众多影响云服务供应商效益的因素进行了研究。考虑到以客户为导向的服务需求是云计算管理机制的基础,此外,服务质量和服务价格是客户最关心的问题,因此,在所有这些因素中,云计算平台中参数的最佳配置和定价模型是最重要的[3]。但是,高质量的服务始终会给云服务供应商带来高昂的成本,这将迫使他们提高服务价格以赚取效益,相反,低廉的服务价格会导致服务质量下降。因此,对于云服务供应商而言,解决增加服务质量和降低服务价格之间的权衡以最大化效益至关重要。文献[4]研究了在云计算环境中实现效益最大化的最佳多服务器配置问题,服务器的数量和执行速度被视为确定多服务器系统配置的基本特征。但是,这些方法很少关注单一多服务器系统中的效益最大化方案,只能采用这种方法来满足一种服务请求。

对于串联结构下的多级多服务器队列系统,每个系统都被视为M/M/m排队模型,每个阶段可以在唯一的多服务器系统中服务一种类型的服务请求,该请求对应于客户发布的子任务。对于耐心有限的客户,云服务供应商应在云计算平台中配置参数,以尽可能满足客户的需求,但是,由于能源支出和租金成本的增长,成本也会增加。因此,如何优化配置参数以在截止时间约束下最大化效益是一个重要的问题。此问题包括三个子问题:如何按照序列结构对多级多服务器队列系统进行建模;如何确定客户在多级多服务器队列系统中等待的总时间;如何通过在截止时间约束下配置云计算平台来实现效益的最大化。

在考虑多级多服务器系统中的效益最大化问题时,相关研究主要集中在具有并行结构的多服务器系统上。文献[5]考虑了具有多条并行生产线的制造系统中的生产设计和调度问题,并通过适当配置一些参数(例如建议的生产率、生产时间间隔等),提出了效益最大化方案。文献[6]解决了相同的并行机器调度问题,其中包含工作截止时间和机器资格约束,以最大限度地减少总的工作完成时间。由于在这些方法中多级多服务器系统以并行结构排列,可以同时满足多种类型的服务请求。但是,他们忽略了所有服务请求(子任务)之间的内部关系,导致必须成功满足某些服务请求(子任务)才能满足客户发布的任务。因此,研究串联结构的多级多服务器排队系统中的效益最大化问题至关重要。在考虑具有多阶段排队系统时,文献[7]分析了具有不同服务时间分布的异构服务的两个阶段,这些阶段受到随机故障和带有一般休假期的强制性服务器休假的影响。讨论了队列中的平均客户数和平均等待时间。文献[8]研究了一个多阶段队列系统,该系统具有一定数量的独立并行服务器,并且在所有或某些阶段都具有多个队列,并提供了一种有效的方法来管理队列,从而在不增加成本的情况下最大化客户满意度。所有这些方法主要集中在解决一个阶段中具有单个服务器的队列系统中的问题,而较少集中于一个阶段中包含多个服务器的情况。

由此本文提出计及等待时长的云计算效益模型,考虑以串联结构排列的多级多服务器队列系统,分析每级多服务器系统中云服务供应商的收入和成本模型,并建立效益最大化模型。根据客户可以等待的最大容忍度,在截止期限约束下定义效益最大化问题,并采用启发式算法来求解这一模型,从而实现效益最大化和客户等待时间的多目标优化。通过算例仿真,分析了效益和已执行服务请求的百分比随期限和服务请求到达率的增加而变化。

1 数学模型

1.1 云计算架构

为了研究云计算环境中服务和应用程序的供求关系,需要考虑服务器提供商、云服务供应商和客户的行为特征。对于服务器提供商,他们采用虚拟化技术来聚合各种IT资源(计算、网络、存储等),并将其提供给远程互联网客户的需求。此外,此类IT资源具有可伸缩性,因此可以根据客户的需求进行调整。典型的情况是服务器的数量和执行速度,这对于不同的应用程序是可变的。

对于云服务供应商,他们致力于在服务器提供商和客户之间建立渠道,从而使客户无须关注服务请求的具体实施细节。实际上,云服务供应商从基础设施提供商那里租用资源,并构建云计算平台以向客户提供服务。对于客户,他们将服务请求提交给云服务供应商,并根据指定的服务级别协议为所提供的服务付费。

1.2 多级多服务器队列系统模型

通常,当客户发布任务时,可以始终将其分为多个子任务,并且这些子任务的执行顺序应遵循连续的逻辑关系。本文假设每个子任务对应一种服务请求,可以在唯一的多服务器系统中进行服务。在此基础上,我们考虑一个云计算平台,多级多服务器队列系统由nM/M/m排队模型组成,它们以串联结构排列。对于每级多服务器系统Si,它具有速度为si的多台服务器,其中i=1,2,…,n。一旦客户发布任务,则当某些服务器可用时,第一个子任务(或第一类服务请求)将立即在第一级多服务器系统中得到服务。当完成第一阶段时,在第一阶段之后的多服务器系统将在随后的阶段中依次服务于后者的子任务(服务请求)。不失一般性地,我们将多级多服务器队列系统视为简化形式,其中此类系统只有两个级,即n=2,而这种简化形式可以很容易地推广到一般情况。

(1)

(2)

由于两级多服务器系统是按串联结构排列的,因此只有在第一级中服务第一类服务请求时,客户才能将第二类服务请求发送到后者中的多服务器系统。那么我们可以发现第一级多服务器系统的起飞时间等于第二级多服务器系统的起飞时间,因此,可以认为后阶段服务请求的到达率等于前阶段服务请求的平均服务率,据此将平均服务费率描述为期望形式,如式(3)所示。

(3)

实际上,可以发现平均服务速率也等于同一阶段的到达速率。给定条件ρ1<1以确保队列系统的遍历性,从长远来看,无须等待就可以响应第一级多服务器系统的传入服务请求。但是,这样的点在很小的时间间隔内是不正确的,这导致传入的服务请求本质上是一种随机流,这可能导致偶尔的流量突发暂时使服务器不堪重负。在此基础上,当多服务器系统中的所有服务器都被执行的服务请求占用时,则新到达的服务请求必须在等待队列中等待。在这种情况下,将其概率表示如下:

(4)

令Wi为第i类服务请求的等待时间,相应的概率分布函数可以描述如下[8]:

(5)

u(t)是脉冲函数:

(6)

令z→∞,则有:

(7)

1.3 效益模型

在本文中,我们选择等待时间来表示服务质量的差异,对于第一和第二多服务器系统中服务请求的服务收费函数定义如下:

(8)

(9)

式中:a1、a2是常数,代表每单位服务的服务费用;D是服务请求可以等待的最大可允许时间。

本文中假定当等待时间不超过最大值时,云服务供应商向客户收取一定的费用。对于给定的两阶段多服务器系统,可以将这种假设分为三种情况。首先,如果在前台花费的第一类服务请求的等待时间超过了最后期限,那么即使他们的服务请求没有得到服务,客户也将离开两阶段多服务器系统,并且他们当然不应该为它们付费。其次,如果在截止期限内满足了第一类服务请求,而总等待时间超过了,那么即使第二类服务请求尚未得到满足,客户也将离开第二台多服务器系统。在这种情况下,他们将只为第一类服务请求付费。最后,如果总等待时间超过了期限,则客户发布的任务成功完成,则客户将为这两种服务请求付费。基于式(8)和式(9),多服务器系统S1和S2中对服务请求的预期费用分别为:

(10)

(11)

式中:FW1(D)和FW(D)表示分别可在第一阶段和第二阶段内服务的服务请求的百分比。

由于截止时间的限制,第一种类型的服务请求只能在前阶段提供服务,这将导致到达后阶段的服务请求到达率下降。因此,当服务请求进入多服务器系统S1时,到达率为λ1,但是当服务请求进入多服务器系统S2时,到达率变为FW1(D)λ2,原因是在截止时间D之前多服务器系统S1中只能处理百分之FW1(D)的传入服务请求,而其余的将不提供服务而离开。因此,由云服务供应商在多服务器系统S1和S2中获得的总收入可表示为:

(12)

(13)

1.4 成本模型

服务提供商的成本包括两个主要部分,即基础设施租赁成本和能源消耗的公用事业成本。基础设施提供商维护大量的服务器以供租赁,云服务供应商根据要求对其进行租赁并支付相应的租赁费用。假设每单位时间一台服务器的租用价格为β,则具有mi台服务器系统的服务器租用价格为miβ。作为服务提供商成本的另一部分,能源消耗的公用事业成本由电价和能源消耗量组成。本文采用如下动态功率模型[9]:

Pd=NswCLV2f

(14)

式中:Nsw是每个时钟周期的平均栅极开关因子;CL是负载电容;V是电源电压;f是时钟频率。在理想情况下,对于某个常数0<φ≤1,电源电压V与时钟频率f之间的关系可以描述为V∝fφ。服务器的执行速度si与时钟频率f呈线性比例,即si∝f,因此动态功率模型可以转化为Pd∝NswCLs(2φ+1)i,为简单起见,假设Pd=bNswCLs(2φ+1)i=ξsαi,其中:ξ=bNswCL;α=2φ+1;b为常数。本文设置NswCL=7,b=1.345 6,φ=0.5。由此可得α=2,ξ=9.419 2。

除了动态功耗之外,服务器空闲时也会消耗静态功率,假设能源价格为每瓦特δ,则多服务器系统每单位时间的总成本可描述为:

(15)

1.5 问题描述

云服务供应商从基础设施提供商处租用服务器并支付费用,同时,它们根据需要向客户提供服务并获得收入。从以上分析可以看出,客户可以忍受的最大等待时间对每级多服务器系统中云服务供应商的成本模型和收益模型都有影响。因此,对于由多级多服务器队列系统组成的云计算平台,必须研究一种适当的方法以在截止期限约束下最大化云服务供应商的总效益。云服务供应商的总效益分别由多服务器系统S1和S2中获得的每个部分组成。在本文中,我们致力于优化租赁服务器的数量m,并优化执行速度,从而获得最佳收益。

G(m1,m2,s1,s2)=G1(m1,s1)+G2(m1,m2,s1,s2)

(16)

注意G1仅由S1本身的特性决定,而G2由S1和S2的特性共同决定,由于在后阶段执行第二种服务请求要比在前阶段执行第一类服务请求滞后,因此第二台多服务器系统中的参数与获得的效益无关,但是由于第二种服务请求的执行受到第一类服务请求的等待时间的影响,因此,该点不能正确地相反。在前阶段花费的等待时间越多,在后阶段花费的等待时间就越少,这将导致第二级多服务器系统获得的效益下降,反之亦然,由此云服务供应商的总效益可以描述如下:

G(m1,m2,s1,s2)=ε1-C1+ε2-C2

(17)

2 求解算法

本节提出一种启发式算法,以找到m1、s1和m2、s2的最佳组合方案。首先,在多服务器系统S1中分析了效益G1与m1以及s1之间的关系,并采用梯度下降算法来配置最优服务器参数以获得最优效益。其次,根据前阶段获得的服务器参数,分析了效益G2与m2以及s2之间的关系,并建立了一个具有约束的最优模型,以同时最大化G2和FW(D)。

2.1 第一级服务器系统效益最大化

2.1.1规模最优

为了在S1中获得最大效益,首先讨论服务器数量m1对G1的影响,G1对m1的偏导数为:

(18)

(19)

(20)

由图1中所绘制的特征关系图可以发现其为减函数,因此可采用二分法来获得最优的m1值。计算得到不同λ1取值下的m1分别为1.991 1、2.337 5、2.681 8、3.024 7,相应的效益G1为27.621、33.312、39.007、44.707。

图1 效益G1随m1和λ1变化曲线

可以看出,当m1较低时,云服务供应商只能从S1中获得极低的效益,甚至是负效益,这是因为服务请求的等待时间非常长,导致在截止时间D仅有很少的需求被响应。随着服务器数量的增长,越来越多的服务器允许在截止时间之前满足越来越多的服务请求,从而增加了收入和效益。当FW1(D)等于1时,收入达到最大值,但是随着m1的进一步增加,服务器数量超过了执行服务请求所需的最大数量,成本将继续增长,导致效益下降。

2.1.2速度最优

同样地,为了获得速度最优的配置方案,令G1对s1求偏导数:

(21)

(22)

(23)

由图2可以发现其特征关系也为递减函数,采用标准的二等分法求得不同λ1取值下的最优s1分别为0.201 44、0.235 78、0.269 87、0.303 79,相应的效益G1为-0.064 63、13.766、27.408和40.862。

图2 效益G1随s1和λ1变化曲线

可以看出,当s1较低时,云服务供应商只能在S1中获得极低的效益,甚至是负效益,这是因为每单位时间只能满足很少的服务请求,而其余的服务请求则由于过多而偏离了系统。随着s1的增加,每单位时间可以满足越来越多的服务请求,这将为云服务供应商带来越来越多的收入和效益。此外,当FW1(D)等于1时,收入达到最大值,但是成本将继续增长,随着s1进一步增加,这将导致效益下降。这是因为服务器的执行速度超过了执行服务请求所需的最大速度。

2.1.3规模和速度最优

根据前面的分析,可以合理地认为m1和s1的影响都可以导致最优效益的增量比前面小节中讨论的更高。因此,我们的目标是找到m1和s1的最佳组合,以使效益G1最大化。图3显示了效益G1的表面作为m1和s1的函数,其中λ1= 5.99。由于曲面是凸面的,我们采用梯度下降算法求出m1和s1,使得式(24)所示的G1(m1,s1)的梯度等于0,从而获得了最优的收益。

图3 效益G1随s1和m1变化曲线

请注意,由于使用了梯度下降算法来解决最小化问题,因此在应使ProfitG1最大化的同时,我们将G1(m1,s1)乘以-1作为目标梯度下降算法的功能。此外,为了加快算法的收敛速度,采用了Arjimo搜索方法来自动调整步长[37]。所得最优效益为G1= 55.706 6,其中m1= 7.559和s1=0.936 8。通过对λ1= 4.99、6.99、7.99的情况进行相同的综合,最优效益分别为G1= 46.286 0、63.918 4、75.354 8,其中:m1=5.931 2、5.9784、8.909 8,s1=0.987 6、1.322 3、1.003 8。

2.2 第二级服务器系统效益最大化

通过选择适当的m1和s1,可以在第一级多服务器系统中获得最佳效益G1。在此基础上,我们进一步找寻最优的m2和s2,以使第二级多服务器系统中的效益G2最大化。

2.2.1规模最优

为了在S2中获得最大效益,首先讨论服务器数量m2对G2的影响。由于G2是m1、m2和s1、s2的函数,在2.1节中获得了最优m1、s1,进一步采用偏导数来找到最优m2:

(25)

(26)

在给定s2和λ1的情况下,效益G2与m1的关系曲线如图4所示。采用二分法来获得最优的m1,以使G2最大化,得到m1的最优值分别为1.768、2.132、2.426、2.766,相应的效益G2分别为27.869 0、33.803 1、39.232 5、44.915 7。

图4 效益G2随m1和λ1变化曲线

2.2.2速度最优

现在考虑执行速度s2对G2的影响,G2相对于s2的偏导数为:

(28)

(29)

在m2和λ1确定下,效益G2随s2的变化曲线如图5所示。对于λ1为 4.99、5.99、6.99,通过二分法得到s2的最优值分别为0.361 5、0.439 7、0.489 1、0.557 2,相应的效益G2分别为32.835 0、46.081 4、58.071 2、70.286 6。

图5 效益G2随s2和λ1变化曲线

2.2.3规模和速度最优

对于云服务供应商而言,在考虑效益的同时,当客户对服务质量感到满意时,他们更有可能向其他客户推荐云计算平台,那么这些潜在客户将为云服务供应商带来更多的效益。但是,如果客户不满意,他们不太可能向其他客户推荐云计算平台,那么云服务供应商获得的相应效益将会减少。本文选择多阶段多服务器队列系统中客户的总等待时间来衡量客户满意度。当等待时间超过最后期限D时,客户会感到不满意,反之亦然。因此,为了在尽可能增加截止时间内服务客户数量的前提下,最大化总效益,本文所构建的云计算效益模型如下:

minf1(X)=-ε2+C2

f2(X)=1-FW(D)

(31)

式中:X=[m2,s2]。本文中采用NSGA-II来求解这一多目标规划问题。

所得非支配解作为优化问题的帕累托解集,以其中一个最优解为例,f1(X)= -57.1,f2(X)=0.001 97,求得最大收益为57.1,并且在截止时间D内响应了99.8%的服务请求。

2.3 一般的n级多服务器队列系统

以上内容充分讨论了具有两阶段多服务器队列系统的效益最大化方案在云计算平台上的应用,由此可进一步扩展到具有n级多服务器队列系统的一般情况。由上述内容,科研发现每级服务器系统的效益仅取决于当前系统和之前系统的参数,而不取决于之后系统。因为无论客户处于什么等待阶段,一旦他们的总等待时间超过了最后期限,即使他们的任务尚未完全执行,他们也会离开多阶段多服务器队列系统。因此,无须为未满足的服务请求(子任务)付费,那么也无须分析在相应的多服务器系统中获得的效益。

3 结果分析

根据第2节的分析,我们发现截止时间内服务请求的百分比不仅受m1、m2和s1、s2的影响,而且还受服务请求到达率λ1和截止时间D的影响。在我们的第一组模拟中,分析了在不同到达率下,截止时间内服务请求的百分比和总效益随截止时间的增加而变化的情况,相应的结果如图6和图7所示。对于λ1分别为4.99、5.99、6.99、7.99的多级多服务器队列系统,截止时间内服务的服务请求百分比和总效益都随截止时间而增加。这是因为随着截止时间的增加,可以满足更多的服务请求,这将给云服务供应商带来更多的收入。此外,随着λ1的减少,总效益减少,而在固定期限内,在期限内提供服务的请求百分比增加。当服务请求的到达率较低时,服务器在多级多服务器队列系统中仅承受很少的压力,因此新的服务请求将会在很大程度上有效减少等待时间以满足截止期限的约束。

图6 截止时间约束下已执行服务请求的完成率

图7 最佳效益与截止时间

在第二组模拟中,分析了在不同的期限内,期限内服务请求的百分比和总效益随服务请求到达率的增加而变化,相应的结果如图8和图9所示。对于D为1、4、7、10的多级多服务器队列系统,总效益增加λ1,而服务请求的百分比在截止时间之内则朝相反的方向变化。请注意,对于D为4、7、10,总效益的变化和在截止时间之前提供的服务请求的百分比彼此接近。而对于D为1,这种变化具有显著差异。这是因为在前一种情况下,最后期限足够长,几乎不能满足所有服务请求;而在后一种情况下,这样的期限太短,无法满足足够的服务请求。因此,在后一种情况下,在截止时间之前提供服务的总效益和服务请求的百分比都远小于在前一种情况下获得的效益。此外,当D为1时,随着λ1进一步增加,总效益反而减少,这是因为收入的增加不足以弥补成本的增加,因此,在这种情况下,应该在效益的最大化与在截止时间之前提供的服务请求的百分比之间进行权衡。

图8 已执行服务请求的完成率随λ1变化特性

图9 最优效益随λ1变化特性

4 结 语

本文研究在考虑客户等待时长的基础上,实现云服务供应商的效益最大化。考虑到每个任务可以通过连续的执行关系分为多个子任务,采用多级多服务器队列系统组成云服务平台,每个系统在每一阶段只为唯一类型的服务请求提供服务。在此基础上,由于最大化云服务供应商的效益与最小化由于过多等待时间而造成的客户损失之间存在矛盾,本文构建了多目标优化模型并进行求解。最后,通过算例仿真分析了本文方法所得最优方案的性能,结果表明,本文方案的动态特性随着客户等待期限和服务请求到达率的增加而增加。