一种虚拟化资源调度的方法及虚拟化资源调度系统

摘要

本发明公开了一种虚拟化资源调度的方法及虚拟化资源调度系统。接收来自外部管理用户请求，或，按照预先设置策略触发调度请求，根据当前系统中虚拟机和物理服务器的资源需求信息，计算并获取虚拟化资源调度方案；根据接收的虚拟化资源调度方案中包含的物理服务器资源流动信息，调度相关物理服务器的资源；根据虚拟化资源调度方案包含的容量信息，与相应物理服务器建立该容量的资源通道；从映射的物理服务器获取调度资源，为外部的业务实体提供调度的虚拟资源。应用本发明，可以提高资源调度效率、实现资源在全局的优化调度。

说明书

技术领域

本发明涉及虚拟化资源调度技术，特别涉及一种虚拟化资源调度的方法 及虚拟化资源调度系统。

背景技术

自从亚马逊与2006年推出弹性计算云(EC2，Elastic Compute Cloud) 平台并大获成功之后，业界掀起了一股基于虚拟化弹性资源池提供共享数据 中心基础设施，对内整合(私有云)共享资源或对外租赁服务的全新商业模 式(IaaS模式的公有云)研究的旋风。

虚拟化技术和弹性计算云平台的结合带来了全新的资源整合和使用模 式，其中，资源的按需分配和动态流动对于提高弹性计算云平台资源的利用 率、提高弹性计算云服务的服务质量以及降低弹性计算云用户的总体拥有成 本具有十分重要的意义。

在云计算资源池中，每个物理服务器通过运行虚拟化软件，从而被虚拟 化成若干相互独立的虚拟机，作为业务实体承载的单位。虚拟化的该物理服 务器对应的各虚拟机之间共享该物理服务器的硬件资源，也就是说，该物理 服务器的硬件资源可以被对应的各虚拟机共享，即可以在本地资源之间进行 调度。现有技术中，本地资源主要包括CPU资源和内存资源，下面对本地 资源调度进行简要说明。

本地CPU资源调度方法：

图1为现有进行CPU资源调度的虚拟机监视器结构示意图。参见图1， 虚拟机监视器包括：

截获模块，用于截获多个客户操作系统发送的频率调整指令，并获取所 有频率调整指令各自对应的期望频率；

获取模块，用于根据期望频率获取所有期望频率各自对应的虚拟CPU 的负载信息；

分配模块，用于根据虚拟CPU的负载信息分配真实CPU资源，进一步 地，负载越重的虚拟CPU分配到的真实CPU资源越多。

本地内存资源调度方法：

区别于本地CPU资源调度方法注重优化调度策略设计的特点，在虚拟 化平台上进行本地内存资源调度，还面临着虚拟机内部内存使用情况获取不 易与内存需求预测等实际困难，因此，在调度策略上，基于每个虚拟机拥有 相同的业务优先级的假设，并以最小化本地与中断次数为优化目标，通过在 该物理服务器对应的多个虚拟机之间设置进行两两迭代的试探搜索算法，根 据试探搜索算法结果进行内存资源调度。

随着虚拟化技术以及资源共享研究的不断深入，跨越物理服务器边界在 全局范围内实现资源的动态共享与实时调度成为虚拟化资源共享调度发展 的趋势，但由上述可见，现有的虚拟化资源调度方法，基本局限在一台物理 服务器对应的多个虚拟机内部进行资源调度，虚拟化资源调度模型过于简 单，没有综合考虑到全局资源调度方案中，资源远程使用时不可忽视的性能 成本与网络容量限制等因素，缺乏虚拟化全局资源、优化全局资源调度的能 力。

与传统的资源调度以资源为对象在业务实体之间进行细粒度优化调度 的视角不同，虚拟机迁移调度方法采用业务实体迁移的方式来实现各类资源 的全局配置，虚拟化资源系统根据各物理服务器资源情况，以虚拟机为调度 单位，将虚拟机在各物理服务器之间进行调度，这样，资源可在多个物理服 务器之间共享。但该虚拟机迁移调度方法中，以虚拟机为调度单位，调度单 位粒度较粗，例如，不足一个调度单位的资源不参与调度，使得调度效率较 低，资源在全局得不到有效的优化调度；而且，每次资源调度，可能需要对 原有已调度的资源进行重新调度，调度较为复杂，使得单次调度所涉及资源 类型复杂，例如，需要涉及CPU资源、内存资源、磁盘资源等的综合决策， 并受到物理服务器资源具体配置等诸多条件限制，其最优化调度问题不能直 接建模为连续规划问题；进一步地，上述现有技术均采用静态设计思路，未 统筹考虑资源池建设与运营生命周期内资源配置与业务部署方案，以及业务 负载压力等动态可变因素对于调度效果的影响。

发明内容

有鉴于此，本发明的主要目的在于提出一种虚拟化资源调度的方法，提 高资源调度效率、实现资源在全局的优化调度。

本发明的另一目的在于提出一种虚拟化资源调度系统，提高资源调度效 率、实现资源在全局的优化调度。

为达到上述目的，本发明提供了一种虚拟化资源调度的方法，该方法包 括：

接收来自外部管理用户请求，或，按照预先设置策略触发调度请求，根 据当前系统中虚拟机和物理服务器的资源需求信息，计算并获取虚拟化资源 调度方案；

根据接收的虚拟化资源调度方案中包含的物理服务器资源流动信息，调 度相关物理服务器的资源；

根据虚拟化资源调度方案包含的容量信息，与相应物理服务器建立该容 量的资源通道；

从映射的物理服务器获取调度资源，为外部的业务实体提供调度的虚拟 资源。

物理服务器的资源需求信息包括物理服务器节点的可供量或需求量信 息，采用贪心匹配算法计算并获取虚拟化资源调度方案。

所述采用贪心匹配算法计算并获取虚拟化资源调度方案具体包括：

获取资源池物理服务器节点集合以及资源产销关系信息s_i，其中，s_i表 示第i个物理服务器节点的可供量或需求量；

将所有本地资源供大于求的物理服务器节点按产量从大到小排列组成 队列O；

将所有本地资源供不应求的物理服务器节点按需求从大到小排列组成 队列I；

从队列O和队列I中分别取出物理服务器节点i和物理服务器节点j：

如果|s_i|＞|s_j|，将{i→j:s_j}加入虚拟化资源调度方案，更新s_i＝s_i+s_j，将i重 新插入队列I；

如果|s_i|＜|s_j|，将{i→j:s_i}加入虚拟化资源调度方案，更新s_j＝_si+s_j，将j 重新插入队列O；

输出虚拟化资源调度方案。

所述物理服务器的资源需求信息中进一步包括资源远程调运成本信息， 采用运输优化算法计算并获取虚拟化资源调度方案。

所述采用运输优化算法计算并获取虚拟化资源调度方案具体包括：

获取资源供大于求的物理服务器节点可供资源a_i；

获取资源供不应求的物理服务器节点b_j；

获取第i个资源供大于求的物理服务器节点与第j个资源供不应求的物 理服务器节点的资源远程调运成本c_ij；

计算的最小值；式中，

$\left(\begin{array}{cc}\underset{j=1}{\overset{n}{\Sigma }}{x}_{\mathrm{ij}}=a_i& (i=1,...,m),\end{array}\right)$$\left(\begin{array}{cc}\underset{i=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}=b_j& (j=1,...,n);\end{array}\right)$

m为资源供大于求的物理服务器节点数，n为资源供不应求的物理服务 器节点数。

所述物理服务器的资源需求信息中进一步包括资源远程调运成本信息， 采用最短路算法计算并获取虚拟化资源调度方案。

所述物理服务器的资源需求信息中进一步包括资源远程调运成本信息 以及网络系统负载信息，采用最小费用流算法计算并获取虚拟化资源调度方 案。

当资源瓶颈在于物理服务器端时，通过逻辑池方法获取资源远程调运成 本信息。

当资源瓶颈在于网络连接时，通过物理池方法获取资源远程调运成本信 息。

所述物理服务器的资源需求信息中进一步包括网络带宽限制信息。

所述采用最小费用流算法计算并获取虚拟化资源调度方案具体包括：

将资源池中各物理服务器分类为资源富余的物理服务器以及资源紧张 的物理服务器；

将资源池中的物理服务器之间的网络连接带宽实时限制映射为网络中 节点间弧的流量上限，获取并确定容量限制c_ij；

将带宽消耗对于业务系统的影响作为网络图中节点对弧(i，j)间的资源 运输成本b_ij；

获取的最小值。

当通信性能受限于物理服务器时，采用逻辑池方法获取资源运输成本信 息。

当通信性能受限于网络拓扑与互联架构时，采用物理池方法获取资源运 输成本信息。

通过将调整单位流量花费最小的增广链作为费用最小的增广链获取所 述最小值。

一种虚拟化资源调度系统，该系统包括：分布式业务网络DSN多业务 资源管理器、资源调度决策器、分布式虚拟机资源调度器、多个虚拟机以及 多个物理服务器，其中，

DSN多业务资源管理器，用于按照业务类型向外部的业务实体提供业 务接口，维护业务类型对应的虚拟机与物理服务器的资源映射，接收来自外 部管理用户请求，或，按照预先设置策略触发调度请求，输出至资源调度决 策器；

资源调度决策器，用于提供用户接口，接收调度请求，根据当前系统中 虚拟机和物理服务器的资源需求信息，计算并获取虚拟化资源调度方案，发 送至分布式虚拟机资源调度器；

分布式虚拟机资源调度器，用于根据接收的虚拟化资源调度方案中包含 的物理服务器资源流动信息，调度相关物理服务器的资源；

虚拟机，用于从映射的物理服务器获取调度资源，通过DSN多业务资 源管理器为外部的业务实体提供调度的虚拟资源；

物理服务器，用于通过运行虚拟化软件虚拟化成多个相互独立的虚拟 机，根据虚拟化资源调度方案包含的容量信息，与相应物理服务器建立该容 量的资源通道。

所述DSN多业务资源管理器进一步用于获取业务实体负载信息，实施 用户请求分流与调整。

所述虚拟化资源调度方案包括：不停机虚拟机迁移、本地资源流动以及 异地资源流动。

所述资源调度决策器包括：映射模块以及计算模块，其中，

映射模块，用于提供用户接口，接收调度请求，将实际调度场景映射为 基本规划模型，根据当前系统中虚拟机和物理服务器的资源需求信息，确定 调度优化目标以及对应的网络描述参数集合；

计算模块，用于根据映射模块确定的网络描述参数集合，计算并获取资 源流动的虚拟化资源调度方案，发送至分布式虚拟机资源调度器。

所述分布式虚拟机资源调度器包括：监测模块以及实施模块，其中，

监测模块，用于从实际网络环境中提取基本规划模型所需的参数以及用 于决定映射模块采用基本规划问题模型的状态参数；

实施模块，用于根据接收的虚拟化资源调度方案中包含的物理服务器资 源流动信息，调度相关物理服务器的资源。

所述监测模块包括参数获取子模块以及状态监测子模块，其中，

参数获取子模块，用于从实际网络环境中提取规划模型所需的限制参数 与成本参数；

状态监测子模块，用于完成从实际网络环境中提取用于决定映射模块采 用基本规划问题模型的状态参数。

由上述的技术方案可见，本发明提供的一种虚拟化资源调度的方法及虚 拟化资源调度系统，接收来自外部管理用户请求，或，按照预先设置策略触 发调度请求，根据当前系统中虚拟机和物理服务器的资源需求信息，计算并 获取虚拟化资源调度方案；根据接收的虚拟化资源调度方案中包含的物理服 务器资源流动信息，调度相关物理服务器的资源；根据虚拟化资源调度方案 包含的容量信息，与相应物理服务器建立该容量的资源通道；从映射的物理 服务器获取调度资源，为外部的业务实体提供调度的虚拟资源。这样，充分 利用跨平台细粒度资源共享机制，提高了资源使用效率以及资源调度效率， 实现了资源在全局的优化调度。

附图说明

图1为现有进行CPU资源调度的虚拟机监视器结构示意图。

图2为本发明实施例虚拟化资源调度系统结构示意图。

图3为本发明虚拟化资源调度的方法第一实施例流程示意图。

图4为本发明虚拟化资源调度的方法第二实施例流程示意图。

图5为本发明实施例资源全局匹配问题采用贪心匹配算法计算优化调 度方案的流程示意图。

图6为本发明实施例求解最小费用流基本算法min_flow(G)流程示意 图。

图7为本发明实施例资源池生命周期内的全局资源最优化调度问题分 析与求解模型结构示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图及具体 实施例对本发明作进一步地详细描述。

本发明实施例的目的在于给出切合分布式业务网络(DSN，Distributed  Service Network)私有云平台资源池实际环境的全局资源调度策略，充分利 用跨平台细粒度资源共享机制，在提高资源使用效率以及资源调度效率的同 时，通过针对远程资源访问限制与损耗的条件分析，利用最优化规划理论， 权衡调度策略性能提升(资源使用效率优化效果)与成本开销，并结合对于 资源池资源配置与使用情况的动态反馈，提供可根据实际需要逐步精化的自 适应与复杂度可调整的资源调度方法。其核心思想在于：

在虚拟资源调度系统中，首先根据当前系统中虚拟机和物理服务器的资 源需求信息计算并获取虚拟化资源调度方案；

然后，综合考虑资源池组网环境具体限制与远程资源访问成本的前提 下，利用最优化规划思路解决全局资源最优化调度问题。资源池组网环境具 体限制包括：物理服务器之间的实时网络带宽限制等；远程资源访问成本用 于反映全局资源流动的业务实体资源消耗需求成本，例如，远程内存资源访 问、磁盘资源访问等；

进一步地，针对资源池建设与运营的不同阶段对应的资源配置与业务部 署需求，结合资源负载压力实时变化等综合因素，为相关业务实体设置不同 的状态，动态调整所采用的调度问题分析粒度和规约求解算法，从而在调度 效果与响应时间、计算成本之间取得权衡；

最后，针对当前系统网络状态分析资源瓶颈所处位置的不同，为相关业 务实体设置不同的状态，动态调整所采用的限制参数获取方法，从而在建模 效果与中间计算成本之间取得权衡。

图2为本发明实施例虚拟化资源调度系统结构示意图。参见图2，该系 统包括：DSN多业务资源管理器、资源调度决策器、分布式虚拟机资源调 度器、多个虚拟机以及多个物理服务器，其中，

DSN多业务资源管理器，用于按照业务类型向外部的业务实体提供业 务接口，维护业务类型对应的虚拟机与物理服务器的资源映射，接收来自外 部管理用户请求，或，按照预先设置策略触发调度请求，输出至资源调度决 策器；

本发明实施例中，为了提高资源共享效率，降低资源调度的复杂度， DSN多业务资源管理器根据业务类型对外部的业务实体进行分类，为每一 类业务实体维护对应的虚拟机资源，管理虚拟机与物理服务器的资源映射。

外部的业务实体位于核心功能层，用于提供业务应用场景，核心功能层 向上对各类电信应用软件提供调用接口。例如，以网络电话(VoIP，Voice over  Internet Protocol)为代表的语音类业务调用接口、以流媒体(Streaming)为 代表的内容共享类业务调用接口等。

核心功能层内部利用点对点传输(P2P，Peer to Peer)等分布式技术， 将来自终端的大量用户请求分发给包括分布式语音交换以及分布式内容交 换的叠加(Overlay)网络中的各个对等节点，各对等节点使用由基础设施 层提供的虚拟资源，即虚拟机提供服务。

业务类型包括：DSN分布式交换业务以及内容交换业务。

DSN多业务资源管理器位于核心功能层以下的基础设施层，基础设施 层向核心功能层提供计算、存储、调度等抽象网络能力，利用系统级虚拟化 技术以虚拟机方式实现对物理服务器资源的灵活划分，并可以借助无停机虚 拟机迁移、资源流动等技术实现不同业务、不同虚拟机、不同物理服务器之 间细粒度的资源动态调度决策与实施，组成本发明实施例的虚拟化资源调度 系统。

DSN多业务资源管理器还用于获取业务实体负载信息，实施用户请求 分流与调整。也就是说，DSN多业务资源管理器负责管理核心功能层中对 等节点的动态加入/退出；同时根据接收的资源调度策略，依据各对等节点 的实时负载，实施用户请求分流与调整，实现应用层的负载均衡与容灾机制。

资源调度决策器，用于提供用户接口，接收调度请求，根据当前系统中 虚拟机和物理服务器的资源需求信息，计算并获取虚拟化资源调度方案，发 送至分布式虚拟机资源调度器；

本发明实施例中，调度请求来自系统管理员或核心功能层，虚拟化资源 调度方案为物理资源到虚拟机资源的映射调整策略。

资源调度决策器通过可控的触发机制和执行机制，在运营商为核心网部 署的各个物理服务器内或物理服务器之间实施虚拟化资源调度方案，具体虚 拟化资源调度方案包括：本地资源流动以及异地资源流动等。异地资源流动 也就是在保持现有系统虚拟机与物理服务器映射关系的前提下，将物理服务 器空闲的资源在各虚拟机之间进行调度，例如，可以将物理服务器A空闲 的资源在物理服务器A以及物理服务器B对应的虚拟机之间进行调度。

本发明实施例中的虚拟化资源调度方案可作为DSN融合架构(虚拟化 资源调度系统)中基础设施层的组成部分，用于完成DSN VoIP、DSN  Streaming等P2P业务在DSN融合架构提供的统一资源池上进行跨物理服务 器的全局资源动态调度。

资源调度决策器包括：映射模块以及计算模块，其中，

映射模块，用于提供用户接口，接收调度请求，将实际调度场景映射为 基本规划模型，根据当前系统中虚拟机和物理服务器的资源需求信息，确定 调度优化目标以及对应的网络描述参数集合；

计算模块，用于根据映射模块确定的网络描述参数集合，计算并获取资 源流动的虚拟化资源调度方案，发送至分布式虚拟机资源调度器。

分布式虚拟机资源调度器，用于根据接收的虚拟化资源调度方案中包含 的物理服务器资源流动信息，调度相关物理服务器的资源；

本发明实施例中，根据虚拟化资源调度方案调度资源，具体可参见相关 技术文献，在此不再赘述。

分布式虚拟机资源调度器包括：监测模块以及实施模块，其中，

监测模块，用于从实际网络环境中提取基本规划模型所需的参数以及用 于决定映射模块采用基本规划问题模型的状态参数，包括参数获取子模块以 及状态监测子模块，

参数获取子模块，用于从实际网络环境中提取规划模型所需的限制参数 与成本参数；

状态监测子模块，用于完成从实际网络环境中提取用于决定映射模块采 用基本规划问题模型的状态参数，即当前可用资源分布情况。

实施模块，用于根据接收的虚拟化资源调度方案中包含的物理服务器资 源流动信息，调度相关物理服务器的资源。

虚拟机，用于从映射的物理服务器获取调度资源，通过DSN多业务资 源管理器为外部的业务实体提供调度的虚拟资源；

物理服务器，位于物理层，用于通过运行虚拟化软件虚拟化成多个相互 独立的虚拟机，根据虚拟化资源调度方案包含的容量信息，与相应物理服务 器建立该容量的资源通道。

本发明实施例中，每个物理服务器上运行多个虚拟机，每个虚拟机中运 行用于业务系统请求处理等逻辑功能软件。

本发明实施例中，触发虚拟化资源调度的调度请求可以是系统管理员人 工发起，也可以是按照预先设置策略进行自动触发。

图3为本发明虚拟化资源调度的方法第一实施例流程示意图。参见图3， 该流程包括：

步骤301，管理员根据实际需要，决定人为发起全局资源分配优化调度 请求，向DSN多业务资源管理器发起全局资源动态调整请求(GloSch_req())；

步骤302，DSN多业务资源管理器接收全局资源动态调整请求 (GloSch_cal_req(P))，请求资源调度决策器根据当前资源池可用资源分布 情况计算全局资源动态调度方案(全局调整方案D)；

本步骤中，可用资源分布情况是指物理服务器上的可用资源，可由分布 式虚拟机资源调度器向上报告给DSN多业务资源管理器。当然，实际应用 中，还可以结合虚拟机和物理服务器的资源需求信息，或其它相关信息进行 计算，关于计算全局资源动态调度方案，后续再进行详细描述。

步骤303，资源调度决策器调用预先设置的优化调度算法，计算全局资 源动态调度方案，并发送至分布式虚拟机资源调度器；

本步骤中，关于优化调度算法，后续再进行详细描述，资源调度决策器 通过GloFlow_req()消息将全局资源动态调度方案发送至分布式虚拟机资源 调度器。

步骤304，分布式虚拟机资源调度器根据接收的全局资源动态调度方案， 向物理服务器发起对应的物理服务器资源流动指令(VM_flow(u，v，vol))；

本步骤中，分布式虚拟机资源调度器将全局资源动态调度方案拆分成针 对特定物理服务器对之间物理资源流动指令集合，发送给对应物理服务器对 执行。资源流动指令中，u，v为物理服务器标识，vol为物理服务器u和物 理服务器v之间建立资源流动的容量。

步骤305，物理服务器接收资源流动指令(VM_flow(u，v，vol))，根据 指令携带的信息，在物理服务器u和物理服务器v之间建立容量为vol的资 源流动渠道，并向分布式虚拟机资源调度器反馈操作成功与否 (Success/Failure)的提示信息；

本步骤中，通过(VM_flow_confirm())消息向分布式虚拟机资源调度 器反馈提示信息。

步骤306，分布式虚拟机资源调度器接收提示信息，修改可用资源统计 数据，并向DSN多业务资源管理器返回调整结果信息；

本步骤中，调整结果信息即为接收的提示信息。

步骤306，DSN多业务资源管理器接收调整结果信息，修改可用资源统 计数据，并向管理员返回调整结果信息。

图4为本发明虚拟化资源调度的方法第二实施例流程示意图。参见图4， 该流程包括：

步骤401，DSN多业务资源管理器周期性监控资源池各物理服务器可用 资源情况P，计算资源分配-业务需求匹配度；

本步骤中，由DSN多业务资源管理器周期性的对其所监控的物理服务 器资源分配与使用情况匹配程度来判定是否自动触发全局资源动态调度请 求。计算得到的资源分配-业务需求匹配度为调度效果，可通过资源使用效 率与业务效益两方面综合考虑。具体的综合计算方法不限，可由管理员根据 资源池具体情况手动确定，具体可参见相关技术文献，在此不再赘述。

步骤402，判断资源分配-业务需求匹配度小于预先设置的阈值，触发 全局资源分配优化调度请求(GloSch_cal_req(P))；

步骤403，资源调度决策器调用预先设置的优化优化调度算法，计算全 局资源动态调度方案，并发送至分布式虚拟机资源调度器；

本步骤中，资源调度决策器通过GloFlow_req()消息将全局资源动态调 度方案发送至分布式虚拟机资源调度器。

步骤404，分布式虚拟机资源调度器根据接收的全局资源动态调度方案， 向物理服务器发起对应的物理服务器资源流动指令(VM_flow(u，v，vol))；

步骤405，物理服务器接收资源流动指令(VM_flow(u，v，vol))，根据 指令携带的信息，在物理服务器u和物理服务器v之间建立容量为vol的资 源流动渠道，并向分布式虚拟机资源调度器反馈操作成功与否 (Success/Failure)的提示信息；

本步骤中，通过(VM_flow_confirm())消息向分布式虚拟机资源调度 器反馈提示信息。

步骤406，分布式虚拟机资源调度器接收提示信息，修改可用资源统计 数据，并向DSN多业务资源管理器返回调整结果信息。

在根据当前资源池可用资源分布情况或当前系统中虚拟机和物理服务 器的资源需求信息确定虚拟化资源调度方案后，如果多个物理服务器都能够 提供所需资源，如前所述，本发明实施例由于不同网络规模与组网环境下的 资源池中资源瓶颈所处位置的不同，例如，对于业务实体资源需求量较大的 情形，其资源瓶颈所处位置可能在于物理服务器侧，可能导致既定规划问题 的不同规约方式，从而得到该问题的不同特例，而且，即使组网环境给定， 随着承载业务类型的不同以及实时负载的动态变化，资源瓶颈所处位置也可 能发生迁移。因此，本发明实施例中，进一步提供一种对于特定环境下足够 精确的抽象问题建模方法，从而在期望调度效果和解决算法复杂度之间实现 权衡。期望调度效果可根据计算结果进行资源调度之后的资源-需求匹配度 来衡量，可通过资源使用效率与业务效益两方面综合考虑，具体的综合计算 方法不限，可由管理员根据资源池具体情况手动确定。

为此，本发明实施例的映射模块与计算模块在完成具体问题规约与求解 时的核心思想是在实际资源池调度应用中，首先选用与实际匹配程度可接受 且复杂度最低的规划解决算法，力求缩短调度方案计算时间，一旦调度效果 超过预先设置的可容忍最低限度时，调度效果可通过物理资源使用效率以及 用户请求拒绝率进行表征，也就是在模型输入参数未发生变化的前提下，反 复进行全局调度操作后，调度效果仍然低于预先设置阈值再逐步细化对于资 源池环境的调度问题刻画模型，或者，通过管理员在资源池环境发生显著改 变时，例如，新业务系统上线、服务器数量变化、组网环境调整等，手动调 整问题刻画模型。从而通过切换到求精后问题模型所对应的复杂度较高的规 划求解算法来优化调度效果。

例如，在小规模、单业务资源池中可假设网络互联资源无限充足，容量 (带宽c，输入限制)与成本(b，优化目标)均为0，此时，在考虑当前系 统中虚拟机和物理服务器的资源需求信息的基础上，进行资源全局匹配，则 即采用贪心匹配算法计算优化调度方案。

图5为本发明实施例资源全局匹配问题采用贪心匹配算法计算优化调 度方案的流程示意图。参见图5，该流程包括：

步骤501，输入资源池物理服务器节点集合以及资源产销关系信息；

本步骤中，将各物理服务器作为网络图节点集合，资源产销关系信息s_i表示第i个物理服务器节点的可供量或需求量。

步骤502，将所有本地资源供大于求的产出节点按产量从大到小排列组 成队列O；

本步骤中，资源供大于求的物理服务器节点称为产出节点。

步骤503，将所有本地资源供不应求的消费节点按需求从大到小排列组 成队列I；

步骤504，循环执行步骤502和步骤503，直到消费节点集合为空；

步骤505，从队列O和队列I中分别取出节点i和节点j：

如果|s_i|＞|s_j|，将{i→j:s_j}加入资源全局调度方案D，更新s_i＝s_i+s_j，将i重 新插入队列I；

本步骤中，如果节点i的可用资源满足节点j的远程访问需求量，则将 “由i向j提供j所需数量资源”的决定写入资源全局调度方案D(已经将j移 出需求队列)，重新更新i的可用资源数量，仍然插入供应队列(前面已经 将其取出队列)。

如果|s_i|＜|s_j|，将{i→j:s_i}加入资源全局调度方案D，更新s_j＝s_i+s_j，将j 重新插入队列O。

本步骤中，如果节点i可用资源不足以支持节点j的远程访问需求量， 则将“由i向j提供i能提供数量资源”的决定写入资源全局调度方案D(已 经将i移出供应队列)，重新更新j的需要资源数量，仍然插入需求队列(前 面已经将其取出队列)。

步骤506，输出资源全局调度方案D。

随着组网规模的扩大，在组网环境复杂的大规模、单业务资源池中，进 一步地，可以考虑资源远程调运的成本优化，下面分作两种情况进行考虑。

第一种情况：网络系统轻载

在网络系统轻载时，可不考虑资源远程调运的容量限制，而根据调度优 化效果来选择逻辑池或物理池方法，逻辑池方法不考虑交换机对系统网络的 影响，物理池方法考虑交换机对系统网络的影响，仅对调运成本进行监测估 算。

这样，可采用一般调运成本获取方法，此时，资源全局匹配问题进一步 细化，求精得到运输问题模型。

下面对运输问题的数学模型与求解算法进行说明。

假设有某种物资需要调运，这种物资的剂量单位可以是重量、包装单位 或其他。已知有m个地点(物理服务器)可以供应这种物资，即产地，用 i＝1，2，...，m表示，有n个地点需要该种物资，即销地，用j＝1，2，...，m表示，如 果m个产地的可供量，即产量为a_i(i＝1，2，...，m)，n个销地的需要量，即销量为 b_j(j＝1，2，...，n)，从第i个产地到第j个销地的单位物资运价为c_ij。如果用x_ij代 表从第i个产地调运给第j个销地的物资的单位数量，则在产销平衡的条件 下，使总的运费支出最小，可以表述为如下的运输问题数学模型：

$\min \underset{i=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{c}_{\mathrm{ij}}{x}_{\mathrm{ij}}$

$s.t.\left(\begin{array}{cc}\underset{j=1}{\overset{n}{\Sigma }}{x}_{\mathrm{ij}}=a_i& (i=1,...,m)\\ \underset{i=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}=b_j& (j=1,...n)\\ & x_{\mathrm{ij}}\ge 0\end{array}\right)$

运输问题最优解的经典算法为表上作业法，近似最优解的O(m+n)贪心 算法包括最小元素法和Vogel法等。具体算法可参见相关技术文献，在此不 再赘述。

此外，实际应用中，还可以根据实际情况综合选择更为简单的其他规划 问题模型。例如，简单使用物理服务器之间局域网连接跳数来简化逻辑池方 法，就得到另一个特例“最短路问题”。

下面对最短路问题的数学模型与求解算法进行说明。

最常用的求最短路的算法有两种：一是求某一点至其他点之间最短距离 的Dijkstra算法；另一种是求网络图上任意两点之间最短距离的矩阵算法， 其中，

Dijkstra算法：

如果以d_ij表示网络图中两相邻点i与j的距离，假设i与j不相邻，令 d_ij＝∞，显然，d_ii＝0，设Ls_i表示从s点到i点的最短距离，则获取从s点到某 一点t的最短路，即求特定点对(s，t)之间最短路的Dijstra算法 min_distance_pair(G，s，t)，用Dijkstra算法时步骤如下：

A、从点s出发，因L_ss＝0，将该值标注在s旁的小方框内，表示s点已标 号；

B、从s点出发，找出与s相邻的点中，距离最小的一个，设为r，将 L_sr＝L_ss+d_sr的值标注在r旁的小方框内，表明点r也已标号；

C、从已标号的点出发，找出与这些点相邻的所有未标号点p，若有， L_sp＝min_p{min_r{min{L_ss+d_sp；L_sr+d_rp}}}，则对p点标号，并将L_sp的值标注在p点旁 的小方框内；

D、重复步骤C，一直到t点得到标号为止。

任意两点间最短距离的矩阵算法

如果以d_ij表示网络图中两相邻点i与j的距离，假设i与j不相邻，令 d_ij＝∞，显然，d_ii＝0，由此得到的矩阵D(0)表明从i点到j点的直接最短距离， 但从i点到j点的最短路不一定是i→j，用矩阵算法求解任意两点间最短路 时步骤如下：

A1、从D(0)开始；

本步骤中，元素d_ij(0)是从i点到j点的直接最短距离，设k＝1。

B1、利用D(k-1)构造新的矩阵D(k)，给出网络中任意两点经过中间节点 数不超过(2k-1)时的最短距离。

本步骤中，方法是：令d_ij(k+1)＝min{d_ir(k-1)+d_rj(k-1)}，其中，k＝k+1。

C1、重复步骤B1，直到k＝m时出现D(m+1)＝D(m)，矩阵D(m)的各个元素 值记为各点间最短距离。

本步骤中，假设网络中有n个点，则一般计算迭代次数m满足下式：

$m-1\le \frac{\lg (n-1)}{\lg 2}\le m$

第二种情况：网络系统负载重

当系统负载达到一定程度时，再启用对于容量参数的监测获取来进行规 划求解。此时，将上述“运输问题”进一步细化，求精得到“最小费用流问 题”，最小费用流问题的数学模型与求解算法说明后续再进行描述，根据资 源瓶颈所处位置不同，又分为两种情况：

其一、如果资源瓶颈在于物理服务器端，则可考虑使用逻辑池方法增加 对于调运成本参数的获取与使用；

其二、如果资源瓶颈在于网络连接，可考虑使用物理池方法增加对于调 运成本参数的建模分析，并换用物理池方法用于容量参数的获取分析。

这样，DSN资源融合平台架构下的资源调度决策器根据资源池中的资 源使用监控情况，实时调整对于最优化资源调度的问题建模，并结合调度优 化结果与期望匹配程度来调整所使用的具体规划求解算法。

实际应用中，当业务种类增加、网络型业务密集形成大规模、多业务资 源池时，可以进一步综合考虑资源池组网环境具体限制与远程资源访问成本 两方面因素，可以考虑采用“最小费用流问题”。为此，需要首先完成从实 际调度场景(系统网络架构)到基本规划模型(调度方案模型)的映射，下 面分别进行说明。

一、基本规划模型的映射：

本发明实施例中，可以通过如下具体步骤综合考虑“网络带宽限制”与 “业务系统资源消耗需求成本”等因素时，在虚拟化资源池中各物理服务器 之间进行资源最优化调度的问题，通过将各因素映射为网络图模型下的“最 小费用流”规划问题进行求解。也就是说，将包含各影响因素的实际调度场 景映射为基本规划模型，该基本规划模型为最小费用流规划模型。

首先，对资源池中各物理服务器进行分类为资源富余的物理服务器以及 资源紧张的物理服务器：将全局资源的最优调度问题抽象为在若干资源产出 点，即资源富余的物理服务器与若干资源消费点，即资源紧张的物理服务器 之间资源调运问题；

本步骤中，当全局调度机制被触发时，DSN多业务资源管理器获取各 物理服务器上当前可用资源储量及各本地业务虚拟机对已分配资源的使用 情况统计信息，进行计算，得到网络图中的对应于物理服务器的节点i的资 源需求量s_i。

其次，将云计算资源池中的物理服务器之间的网络连接带宽实时限制抽 象(映射)为网络中节点间弧的流量上限，获取并确定容量限制c_ij；

本步骤中，具体确定方法可能包含但不局限于：

在通信性能受限于端点服务器场景下，不考虑组网架构的逻辑池方法； 和，

在通信性能受限于网络拓扑与互联架构场景下，综合考虑组网架构的物 理池方法。

下面进行具体说明。

一、带宽限制到资源限制的流量建模转换方法

本发明实施例中，最小费用流问题中的产品资源与弧上流量上限等输入 变量为采用统一度量标准的同类资源，而在具体的资源池全局调度问题中， 产品为跨物理服务器共享的硬件资源，例如，内存等，而用弧流量建模反映 的为网络连接带宽限制，并非同种资源，度量单位也不一致，例如，硬件资 源度量单位为M，弧流量度量单位为M/s，为解决该问题，可采用如下方法 将带宽限制转换成对远程共享资源的限制：

(1)利用网络设备获取任意两个节点i，j之间的实时网络带宽限制d_ij。 在实际资源调度场景下，如有硬件条件，可直接使用两端物理服务器的端到 端带宽实时监测数值作为d_ij的输入。

(2)对于所考虑的单位大小的远程共享资源，确定单位时间内其消费 者到提供者之间的数据访问而消耗的带宽m。例如，对于远程共享内存而言， 给定业务系统类型和共享内存大小，可估计一段时间之内资源使用者对于资 源提供者进行远程内存访问而消耗的网络数据通信量，从而估算出m。估算 的方法包括：

通过本地内存访问频次来估算远程访问频次：获取给定业务系统中业务 逻辑节点的本地内存访问频率与平均每次访问数据量/本地内存大小，用这 两个数值乘积再乘以远程内存大小得到远程内存访问净通信量，再除以网络 通信开销比例(远程访问协议和IP网络数据包头开销)，从而得到估算数 值；或者，

直接测量不同远程内存分配大小下，网络访问数据通信量的统计数值， 后进行曲线拟合，得到二者的数量关系，再据其进行计算。

(3)任意两个节点，例如，物理服务器节点i，j之间流量限制c_ij确定为：

c_ij＝d_ij/m

二、不考虑组网架构的逻辑池方法

该情形下，资源池中各物理服务器之间的网络互联带宽相对于目前需求 而言无限充足。此时，跨物理服务器共享资源的带宽限制根据两个端点服务 器的自身富余带宽的较小值来确定。

三、综合考虑组网架构的物理池方法

该情形下，综合资源池的具体组网架构，引入对于内部交换机的带宽限 制考虑。此时，跨物理服务器共享资源的带宽限制根据两个端点物理服务器 之间提供局部交换服务的各个相关交换设备、网络线缆的当前富余带宽的最 小值来确定。例如，目前主流交换机上配有流量监控功能，能实时监测各端 口的实时富余带宽，取端点物理服务器之间网络路径上的监测数据最小值即 可。

在实际组网环境下，可利用交换设备自身的流量监控机制实现对节点间 链路带宽分配d和利用效率v的实时统计，因而，可直接用d(1-v)数值作为d_ij的输入。

确定调运成本b_ij

第三步，将全局资源调度机制引入的资源消耗成本例如，带宽消耗对于 业务系统的影响作为网络图中节点对弧(i，j)间的资源运输成本b_ij。

对应前述的流量限制建模方法，确定调运成本的具体实现方法同样包括 但不限于如下两类：

在通信性能受限于端点服务器场景下，不考虑组网架构的逻辑池方法； 和，

在通信性能受限于网络拓扑与互联架构场景下，综合考虑组网架构的物 理池方法。

下面进行具体说明。

一、不考虑组网架构的逻辑池方法

如果资源池中各物理服务器之间的网络互联带宽相对需求而言无限充 足，此时，跨物理服务器共享资源的带宽消耗成本来自原来可供业务系统本 地备份使用的两个端点物理服务器自身富余带宽。具体方法如下：

(1)根据物理服务器节点本地业务系统增加单位带宽的效益增益和本 地业务系统减少单位带宽的效益损失，综合估算其本地单位带宽资源远程调 运成本。所用运算符综合资源远程调运的边际成本，其实际涵义可根据需要 定义，例如，数值乘、取较大值、取较小值等。

(2)根据两个物理服务器节点本地单位带宽资源远程调运成本，综合 估算二者之间单位资源调运成本。所用运算符综合两个节点本地成本，其实 际涵义可根据需要定义，例如，数值乘、取较大值、取较小值等。

二、综合考虑组网架构的物理池方法

该情形下，资源池中各物理服务器之间的网络互联带宽有限。此时，跨 物理服务器共享资源的带宽消耗成本还来自对应交换设备与网络线缆的富 余带宽。具体来说，其建模方法如下：

(1)根据物理服务器节点本地业务系统增加单位带宽的效益增益和本 地业务系统减少单位带宽的效益损失，综合估算其本地单位带宽资源远程调 运成本。所用运算符综合资源远程调运的边际成本，其实际涵义可根据需要 定义，例如，数值乘、取较大值、取较小值等。

(2)根据两个物理服务器节点本地单位带宽资源远程调运成本，综合 估算二者之间单位资源调运成本。所用运算符综合两个节点本地成本，其实 际涵义可根据需要定义，例如，数值乘、取较大值、取较小值等。

(3)根据对应物理服务器节点的本地单位带宽资源调运成本，确定交 换机节点与相邻服务器节点之间的单位资源调运成本。

(4)根据与直接相邻物理服务器节点之间的单位资源调运成本之和， 综合决定两个相邻交换机节点之间的单位资源调运成本。其中所用运算符综 合两个节点本地成本，其实际涵义可根据需要定制，例如，数值加、取较大 值、取较小值等。

这样，全局资源的最优调度问题归结为所建立的网络模型中的最小费用 流问题，可利用相关算法，例如，最小费用流求解算法来制定性价比最/次 优的资源调运方案。

下面对最小费用流问题及其求解算法进行说明。

最小费用流问题描述：设网络有n个节点(n为自然数)，f_ij为弧(i，j) 上的流量，表示节点i提供给节点j远程使用的资源数量；c_ij为该弧的容量(实 时带宽限制)，b_ij为在弧(i，j)上通过单位流量时的费用，s_i表示第i个节 点的可供量或需求量，当i为网络图中的发点时，s_i＞0，即资源富余的物理 服务器节点；i为网络图中的收点时，s_i＜0，即资源紧张的物理服务器节点； i为中转点(网络图中其他节点)时，s_i＝0，即既非发点也非收点，例如， 交换机等局域网互联设备的资源需求量始终为零。

当网络共需平衡时，将各发点物资调运到各收点(或从各 发点按最大流量调运到各收点)，使总调运费用最小的问题，可归结为如下 线性规划模型：

$\min \underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{b}_{\mathrm{ij}}{f}_{\mathrm{ij}}$

求最小费用流时，一方面，可以通过寻找增广链来调整流量，并判别是 否达到了最大流量，但另一方面，为了保证每步调整的流量花的费用最少， 需要找出每一步费用最小的增广链，以保证最终给出的流量或最大流量也是 费用最少的，增广链为使网络中给定发点到收点资源调运数量增加的流量调 整路径。

设b(f)为可行流f的费用，沿增广链调整后的流量为f′(f′＞f)，相应 费用为b(f′)，则费用差Δb(f)：

$\mathrm{\Delta b}\left(f\right)=b\left(f^{\prime }\right)-b\left(f\right)=\underset{{\mu }^{+}}{\Sigma }{b}_{\mathrm{ij}}({f^{\prime }}_{\mathrm{ij}}-f_{\mathrm{ij}})-\underset{{\mu }^{-}}{\Sigma }{b}_{\mathrm{ij}}({f^{\prime }}_{\mathrm{ji}}-f_{\mathrm{ji}})=\theta [\underset{{\mu }^{+}}{\Sigma }{b}_{\mathrm{ij}}-\underset{{\mu }^{-}}{\Sigma }{b}_{\mathrm{ji}}]$

使比值[Δb(f)/θ]最小，亦即将调整单位流量花费最小的增广链作为费用 最小的增广链。

实际应用中，如果将每条弧作为正向弧或反向弧出现时，通过该弧的单 位流量的费用在该弧旁作为权数标注，则寻找费用最小的增广链，又可转化 为一个求发点至收点的最短路问题。因此，上述求最小费用流的步骤可归结 如下。

图6为本发明实施例求解最小费用流基本算法min_flow(G)流程示意 图。参见图6，该流程包括：

步骤601，从零流f₀开始；

本步骤中，f₀是可行流，也是相应的流量为零时费用最小的可行流。

步骤602，对可行流f_k构造加权网络W(f_k)；

本步骤中，构造加权网络W(f_k)具体包括：

对o＜f_ij＜c_ij的弧(i，j)，当其为正向弧时，设通过单位流的费用为b_ij， 为反向弧时，相应费用为b_ji＝-b_ij。这样，在加权网络W(f_k)中的节点i和节点 j点之间，可以分别给出弧(i，j)和(j，i)，弧(i，j)对应的权数为b_ij， 即在弧(i，j)上通过单位流量时的费用，弧(j，i)对应的权数为b_ji，即在 弧(j，i)上通过单位流量时的费用，其中，i≤k，j≤k。

对0＜f_ij＝c_ij的弧(i，j)，由于该弧流量已饱和，在增广链中只能作为反 向弧，也就是在加权网络W(f_k)中，只给出弧(j，i)，即弧(j，i)对应的权 数为b_ji。

对f_ij＝0的弧(i，j)，在增广链中只能为正向弧，也就是在加权网络W(f_k) 中，只给出弧(i，j)，即弧(i，j)对应的权数为b_ij。

步骤603，在构造的加权网络W(f_k)中，获取费用最小的增广链；

本步骤中，获取费用最小的增广链，即获取从发点到收点的最短路径。

步骤604，将获取的费用最小的增广链上流量调整至允许的最大值，得 到新流量f_k+1。

本步骤中，将获取的最短路径对应的增广链上流量调整至允许的最大 值，得到一个新的流量f_k+1，其中，f_k+1＞f_k。

步骤605，返回执行步骤602，直至在加权网络W(f_k+m)中不存在增广链， 该f_k+m为所需的最小费用最大流。

关于最小费用流基本算法的其他说明，具体可参见相关技术文献，在此 不再赘述。

图7为本发明实施例资源池生命周期内的全局资源最优化调度问题分 析与求解模型结构示意图。参见图7，通过采用自适应方法，可用于指导整 个资源池建设与运营周期之内的全局资源最优化调度问题分析与求解，具体 来说：

当小规模、单业务资源池时，可以抽象为资源匹配问题；

当规模扩大、组网复杂度增加形成大规模、单业务资源池时，可以抽象 为运输最优化问题；

而当业务种类增加、网络密集型业务形成大规模、多业务资源池时，可 以抽象为最小费用流问题。

由上述可见，本发明实施例中，在虚拟资源调度系统中，综合考虑资源 池组网环境具体限制与远程资源访问成本的前提下，利用最优化规划思路解 决了全局资源最优化调度问题；

针对资源池建设与运营的不同阶段，通过为调度实体设置不同的状态， 结合资源池资源配置与业务部署、负载压力等综合因素，动态调整所采用的 问题分析粒度和规约求解算法，从而在调度效果与响应时间、计算成本之间 取得权衡；

针对资源瓶颈的所处位置不同，分别提出了服务器端资源受限场景下的 逻辑池参数获取方法和网络资源受限场景下的物理池参数获取方法。

具有如下技术优点：

其一，针对虚拟资源调度系统中全局资源调度机制的特点与需求，综合 考虑资源池组网环境具体限制与远程资源访问成本，建立起以“最小费用流” 问题为基础的问题分析与求解思路。

其二，针对资源池建设与运营的不同阶段，设计管理员人为触发场景， 实施调度问题建模分析与求解算法的自适应调整，从而在算法复杂度与调度 效果之间取得权衡：首先选用与实际匹配程度可接受且复杂度最低的规划解 决算法力求缩短调度方案计算时间，一旦调度效果超过可容忍最低限度时， 再利用本发明实施例方法逐步细化对于资源池环境的调度问题刻画模型，从 而通过切换到求精后问题模型所对应的复杂度较高的规划求解算法来优化 调度效果。

其三，提出服务器端资源受限场景下的逻辑池参数获取方法和网络资源 受限场景下的物理池参数获取方法。以此为基础，为监测模块设置状态，针 对实际运营场景下资源池资源瓶颈的所处位置不同，动态调整所使用的参数 获取方法，从而在模型及其求解复杂度与调度效果之间取得权横。

以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范 围。凡在本发明的精神和原则之内，所作的任何修改、等同替换以及改进等， 均应包含在本发明的保护范围之内。