一种多服务器资金分配方法

技术领域

本发明涉及系统资源分配技术领域，特别是一种多服务器资金分配方法。

背景技术

对于具有相应工作负载的应用程序，云服务提供商必须适当地分配现有资源，以实现最大的系统吞吐量，并确保各个服务器的基本性能。在云计算系统中，服务提供商在多个服务器之间平衡资源分配是非常重要的。

Y.Hu等人(Y.Hu,J.Wong,G.Iszlai,and M.Litoiu,“Resource provisioning forcloud computing,”in Proceedings of the 2009Conference of the Center forAdvanced Studies on Collaborative Research.IBM Corp.,2009,pp.101–111.)提出了一种基于响应时间分布的自主资金管理算法，该算法用于确定共享分配和专用分配两者之间合适的资金分配策；Kenli Li等人(Li K,Mei J,Li K.A fund-constrained investmentscheme for profit maximization in cloud computing.IEEE Trans ServComput.2018；11(6):893-907.https://doi.org/10.1109/TSC.2016.2589241.)提出了一种启发式策略来克服应用领域的选择问题，该策略是为了满足不同应用领域的市场需求而提出的；M.Mazzucco等人(M.Mazzucco,D.Dyachuk,and R.Deters,Maximizing cloudproviders’revenues via energy aware allocation policies,InternationalConference on Cloud Computing,IEEE,2010,pp.131–138.)通过降低电力成本一定程度的解决了云计算的经济问题，其思想是基于动态的用户需求和系统行为来提高服务器的利用率。但是现有的资源管理方案都是用有限的资源来维护系统功能，并且没有考虑到各个服务器的吞吐量和服务器之间的公平性。

发明内容

本发明的目的在于提供一种操作简单、实用性强、既能保证效率又能兼顾服务器之间的公平的多服务器分配资金方法。

实现本发明目的的技术解决方案为：一种多服务器资金分配方法，包括以下步骤：

步骤1、建立多服务器系统的资金消耗及服务器请求模型，得出服务请求与资金消耗的相互关系；

步骤2、根据系统当前的可用资金状态制定不同的资金调度策略：高可用资金状态时，只需按需分配；低可用资金状态时，利用博弈论构建符合多服务器系统的合作博弈模型；所述高可用资金状态是指系统需求不大于现有资金、低可用资金状态是指系统需求大于现有资金；

步骤3、使用拉格朗日乘子法对构建的合作博弈模型进行转化，计算出相应的纳什均衡解，从而得到多服务器系统最优的资金分配方案。

进一步地，步骤1所述的建立多服务器系统的资金消耗及服务器请求模型，得出服务请求与资金消耗的相互关系，具体如下：

步骤1.1、初始化多服务器系统的资金需求F

步骤1.2、建立每个服务器的任务模型，计算每个服务器的任务量Q

其中Q

步骤1.3、建立每个服务器的成本模型，计算每个服务器的花费C

其中C

步骤1.4、建立每个服务器的资金模型，计算每个服务器i执行一个任务的总成本F

步骤1.5、更新系统的资金需求F

进一步地，步骤2所述的根据系统当前的可用资金状态制定不同的资金调度策略，具体如下：

步骤2.1、若系统需求不大于现有资金，即F

步骤2.2、若系统需求大于现有资金，即F

其中

进一步地，步骤3所述的使用拉格朗日乘子法对构建的合作博弈模型进行转化，计算出相应的纳什均衡解，从而得到多服务器系统最优的资金分配方案，具体如下：

步骤3.1、将构建的合作博弈模型转化为相应的对偶问题；

步骤3.2、求出对偶问题的最优解，通过梯度投影求解拉格朗日乘子α,β

步骤3.3、将拉格朗日乘子α,β

本发明与现有技术相比，其显著优点在于：(1)操作简单，实用性强：云服务提供商只需要根据本发明提出的模型计算每个服务器所需要的花费和系统的资金需求，再根据资金分配方案为每个服务器分配资金；通过使用拉格朗日乘子法对构建的合作博弈模型进行转化，可以更简便地得到资金分配的最优解；(2)提高了多服务器系统的效率，降低了多服务器系统的硬件需求：在构建模型的时候，考虑到了每个服务器的吞吐量和服务器的效率，在保证系统效率的情况下能兼顾服务器的吞吐量和服务器之间的公平性。

附图说明

图1是本发明保证服务器基本运行指标的多服务器资金分配方法的流程示意图。

图2是M/M/M排队系统的结构示意图。

具体实施方式

本发明提出的资金分配策略是指通过服务提供者，负载均衡器将用户请求分发到应用程序服务器。当服务提供者的资金不足时，各个应用程序服务器会合作博弈来争夺有限的资源，其目的是维持及时完成自己的服务请求或工作负载的可能性。与此同时，服务提供者期望较高的系统吞吐量，因为有使用有限的资金执行尽可能多的任务的总体请求。很明显，资金缺乏时，将资金分配给多服务器系统本质上是一个资源共享问题，可以使用Nash议价方法来解决。

Nash议价是一种广泛应用在资源配置问题中的具有强大功能的技术，基于此项技术，本发明提出了一种解决服务提供商多服务器系统资金分配问题的博弈论方法，该方法不仅考虑了系统吞吐量，而且考虑了单个服务器的吞吐量。将分配问题建模为多个服务器之间的合作博弈，并推导出分配共享资金来源的Nash议价解决方案。

一种多服务器资金分配方法，包括以下步骤：

步骤1、建立多服务器系统的资金消耗及服务器请求模型，得出服务请求与资金消耗的相互关系；

步骤2、根据系统当前的可用资金状态制定不同的资金调度策略：高可用资金状态时，只需按需分配；低可用资金状态时，利用博弈论构建符合多服务器系统的合作博弈模型；所述高可用资金状态是指系统需求不大于现有资金、低可用资金状态是指系统需求大于现有资金；

步骤3、使用拉格朗日乘子法对构建的合作博弈模型进行转化，计算出相应的纳什均衡解，从而得到多服务器系统最优的资金分配方案。

进一步地，步骤1所述的建立多服务器系统的资金消耗及服务器请求模型，得出服务请求与资金消耗的相互关系，具体如下：

步骤1.1、初始化多服务器系统的资金需求F

步骤1.2、建立每个服务器的任务模型，计算每个服务器的任务量Q

其中Q

步骤1.3、建立每个服务器的成本模型，计算每个服务器的花费C

其中C

步骤1.4、建立每个服务器的资金模型，计算每个服务器i执行一个任务的总成本F

步骤1.5、更新系统的资金需求F

进一步地，步骤2所述的根据系统当前的可用资金状态制定不同的资金调度策略，具体如下：

步骤2.1、若系统需求不大于现有资金，即F

步骤2.2、若系统需求大于现有资金，即F

其中

进一步地，步骤3所述的使用拉格朗日乘子法对构建的合作博弈模型进行转化，计算出相应的纳什均衡解，从而得到多服务器系统最优的资金分配方案，具体如下：

步骤3.1、将构建的合作博弈模型转化为相应的对偶问题；

步骤3.2、求出对偶问题的最优解，通过梯度投影求解拉格朗日乘子α,β

步骤3.3、将拉格朗日乘子α,β

下面结合附图及具体实施例对本发明作进一步详细说明。

实施例

结合图1，本实施例多服务器分配资金方法，包括以下步骤：

步骤1、建立多服务器系统的资金消耗及服务器请求模型，导出服务请求与资金消耗的相互关系，具体如下：

步骤1.1、初始化多服务器系统的资金需求F

步骤1.2、建立每个服务器的任务模型：

结合图2，将云计算系统中的服务器看作是M/M/M排队系统，由N台异构服务器组成，每个服务器的任务到达率为λ

由于云计算系统是资金敏感系统，有限的资金资源无法支持服务器的连续运行。因此，服务器i上的任务执行数量是到达的任务数量与服务器在T工作期间可以处理的任务数量之间的较小值，该值为：

其中

步骤1.3、建立每个服务器的成本模型：

服务器i的租赁成本是单位时间为r

其中ξ为处理器有效系数，ε为一个常数，值为

服务器i总的能量消耗为基功率，表示为：

其中P

由于云计算系统中服务器的利用率有限，服务器i的速率为s

因此，T工作时间的动态功耗为：

得出服务器i在T工作期间的总消耗成本为：

服务器i执行一个任务的总成本为：

步骤1.4、建立每个服务器的资金模型：

设置F

F

系统的资金状态可以分高资金状态和低资金状态两种，低资金状态数字化表示为F

步骤1.5、更新系统的资金需求：F

步骤2、根据系统当前的可用资金状态制定不同的资金调度策略：高可用资金状态时，只需按需分配；低可用资金状态时，利用博弈论构建符合多服务器系统的合作博弈模型，具体如下：

服务提供商需要两种资金分配策略来分配两种系统状态下的资金，当系统为高资金状态时，服务提供者只需要根据不同服务器的资金请求将资金分配给各个服务器；当系统为低资金状态时，单个服务器需要再竞争资金来最大化各自的性能。同时，服务提供商需要使整个系统的吞吐量最大化，即通过各个服务器之间的合作使整个系统的收益最大化。

系统将有限的资金分配给各个服务器，在保证各个服务器性能的前提下使系统的吞吐量最大化，即在资金有限的情况下最大化整个系统和单个服务器的吞吐量，提出一个既能保证服务器之间的公平又能兼顾效率的资金分配方案。

步骤2.1、若系统需求不大于现有资金，即F

步骤2.2、若系统需求大于现有资金，即F

步骤3、使用拉格朗日乘子法对构建的合作博弈模型进行转化，计算出其相应的纳什均衡解，从而得到多服务器系统最优的资金分配方案，具体如下：

步骤3.1将构建的合作博弈模型转化为相应的对偶问题：

将可用资金分配给多个服务器的问题可以建立一个合作博弈的模型。为了兼顾效率和公平，用Nash议价来解决该问题。

一个合作游戏可以这样描述:N个玩家(N个服务器)竞争他们主人(服务提供者)的有限的资源(资金)，

其中R

一对(U,u

M

其中

存在一个唯一的Nash议价解u

在合作博弈问题中，至少有两名玩家带着性能函数和初始性能的要求进入博弈。由于初始性能协议，游戏还保证了最低的投资保证，这符合对资金敏感的云计算系统的设计要求，需要系统的最大吞吐量和对单个服务器的较低投资限制。为了更容易的解决问题，将(9)等价为：

其中P′

计算出服务器i在其预算分配基金F

在发明中N台服务器能够实现严格高于初始性能的性能。

根据合作博弈模型，通过总体吞吐量最大化系统收益，满足单个服务器初始需求的问题为：

其中式(13)、式(14)、式(15)为三个约束，分别表示：所有可用资金都可以分配给服务器来执行系统的任务；分配给每个服务器的资金不能超过在每个服务器上所执行任务的成本；每个服务器所实现的吞吐量高于其初始需求。

将P

用拉格朗日乘子来求解该优化问题，将式(16)进一步转化为：

式(17)的拉格朗日表达式为：

其中

其中

因此(17)的最优解可以推导为：

其中α,β

为了得到最优解，需要得到满足KKT条件的拉格朗日乘子的值，在(22)式中

综上，求解式(17)最优解的关键在于的得到拉格朗日乘子的值，且拉格朗日乘子独立于其它的服务器，将该优化问题转化为相应的对偶问题来求解最优解。

步骤3.2、求出对偶问题的最优解，通过梯度投影求解拉格朗日乘子α,β

由于P

上诉拉格朗日问题

原始问题有唯一的最优解，拉格朗日函数对于(17)的每一个最优解

当(25)存在最优解F

步骤3.3、将拉格朗日乘子α,β

为了得到原问题P

s.t.β

其中d(α,β

梯度投影被广泛应用于求解带约束最优化问题中，在梯度项目中使用贪婪搜索可能会陷入局部最优。因此，需要通过分析来验证梯度法得到的解是全局最优解。对偶函数d(α,β

综上所述，函数d(α,β