2. 国家计算机网络应急技术处理协调中心, 北京 100029
虚拟计算环境中任务具有数量庞大、需求模糊、种类多样等特征，使得资源匹配面临巨大挑战.依据虚拟计算实验床平台公布数据，提出了一种融合虚拟资源与任务聚类的资源匹配优化模型.该模型通过分析任务需求、消耗等特征，基于改进二分K均值进行任务聚类，并结合虚拟资源类型生成优化的资源匹配列表.经实验分析验证，该模型有效缩小资源匹配范围，提高任务运行成功率，为精准匹配提供基础.
2. National Computer Network Emergency Response Technical Team/Coordination Center, Beijing 100029, China
Under virtual computing environment(VCE), tasks have features of large quantity, ambiguous requirements, and various types. This makes resource matching face enormous challenges. According to the data published by VCE platform, a resource matching optimization model combined with resource and task clustering was proposed. By analyzing task requirements and consumption characteristics, the model clustered tasks based improved bised K-means, and combined with the virtual resource types to generate optimized matching resource list. The experimental analysis verified that the model effectively reduced resource matching range and improved the successful rate of tasks to provide the foundation for precision matching.
面向互联网的虚拟计算环境以资源虚拟化为核心，围绕资源的按需聚合和自主协同两个核心机制提供对互联网应用的基础服务支撑[1].如何更好地适应互联网资源的自然特征、满足灵活多变的应用需求、实现资源的可信共享和高效利用是虚拟计算环境亟待解决的重要问题[2].由于虚拟资源具有动态变化、种类多样、高度自治等特征，海量任务具有需求模糊、类型多样等特征，使得资源匹配面临挑战.学者们大多从资源聚类[3-5]、任务偏好[6-7]等角度提供有效解决方案.笔者通过模拟虚拟计算环境中资源匹配的应用场景，对虚拟资源与任务进行聚类分析，提出了一种基于聚类的资源匹配优化算法，为精准匹配提供行之有效的解决方案.
1 虚拟资源与任务的聚类模型 1.1 虚拟资源定义及类型所谓虚拟计算环境(VCE，virtual computing environment)是指建立在开放的互联网基础设施之上，以网络资源的按需聚合与自主协同为核心机制，为终端用户或应用系统提供和谐、可信、透明的一体化服务环境，实现有效资源共享和便捷合作[1].其中，相关定义如下.
定义1 虚拟资源(VR，virtual resource)是虚拟计算平台中执行任务的基本单元，虚拟资源集合表示为VR={VR1, VR2, …, VRn}.其中VRi=(VRID, CAVR, RAVR)；CAVR(configuration attributes of virtual resource)表示虚拟资源的物理配置属性，如物理机类型、CPU、内存、磁盘、网络带宽、地理位置等. RAVR(running attributes of virtual resource)表示虚拟资源动态运行属性，如CPU、内存、磁盘等实时变化值.
资源匹配的大致步骤为，一是获取应用申请中的任务需求，找到符合任务需求的虚拟资源列表L0；二是针对不同任务类型，分配与之相对应的虚拟资源，生成满足匹配优化目标的列表L.文献[3]中通过分析虚拟资源在CPU、内存、磁盘、网络带宽等信息，通过模糊聚类算法将虚拟资源分为3类，即计算型、存储型、带宽型.其中，计算型代表了CPU类型、CPU利用率及操作系统的特征；存储型具备容量、存储类型及方式等特征；带宽型则突显了接入方式与网络带宽的主要特征.
1.2 任务定义及聚类模型定义2 任务.任务是指当用户期望获得某种应用服务而通过客户端向服务器发出的请求时，请求中包含与应用相关的需求等，通过任务管理层将请求解析为实现该应用而形成的程序指令，用符号T(Task)加以标识.虚拟计算环境的任务为元任务，即任务调度器进行任务分配的最小单位，且任务之间相互独立，不考虑任务的跨资源节点执行.任务描述如下：
T={t1, t2, …, tn}表示任务集合，n=|T|为任务集合的数量，ti(i∈[1, n])表示第i个任务，ti={tID, dtask, tsev, tstatus, tdata}，各属性含义如下：
1) tID为任务标识；
2) dtask={d1, d2, …, dk}，用以表示运行任务的资源应须具备的配置属性.其中，dk描述的是运行任务所须满足的第k个资源配置属性；
3) tsev表示服务提供商应满足与任务相对应的服务相关属性；
4) tstatus表示任务在虚拟计算环境中的状态；
5) tdata表示任务实际消耗虚拟资源的情况.
从任务定义中可看出，影响任务聚类的因素有很多，从运行需求、服务指标、任务状态与任务消耗等特征对任务进行聚类分析.基于二分K均值的改进算法对任务特征进行聚类分析，步骤如下：
1) 数据标准化.对原始数据x进行标准化处理，消除数据中的量纲，将数据压缩到[0, 1].
| $ x' = \frac{{x-\bar x}}{s}, x'' = \frac{{x'-{{x'}_{\min }}}}{{{{x'}_{\max }}-{{x'}_{\min }}}} $ | (1) |
2) 设置初始K值. K=10n，其中，n为参数维度.选取任务消耗参数CPU与内存作为维度，即n=2，K取100.为避免分类过细的情况，将内存与CPU消耗分为强、中、弱3种，除去噪声点，共计10种类型，即K值最小为10.
3) 取值半径r.计算参数在[0, 1]区间中，以0.1为间隔的概率，再得出累积分布函数(CDF，cumulative distribution function)F(X).当分布函数F(X)≥95%时，对应的值设为r.
4) 将所有数据点作为一个簇，再选择能够最大程度降低误差平方和(SSE，sum of squared error)的簇划分为2个簇，直至簇的数目达到用户设定的K值.
5) 为避免二分K均值算法出现聚类过细的情况，这里设置合并参数φ，φ∈(0, 1].假设α与β为任意2个质心，用d(α, β)表示2个质心的距离，d为K个子簇质心之间距离的平均值.当2个簇之间的距离d(α, β)不大于φ×d时，则2个簇合并；反之，则不合并.可看出，φ值越小，簇的数量越小.
2 基于聚类的资源匹配优化模型资源匹配是以任务调度为目标，目的是选择能够满足任务需求、服务质量与匹配目标的虚拟资源.通过虚拟资源管理服务器与任务管理服务器获取虚拟资源VR与任务T相关信息，其中VR={VR1, VR2, …, VRn}，VRi=(VRID, CAVR, RAVR)；T={t1, t2, …, tn}，ti={tID, dtask, tsev, tstatus, tdata}.融合上述两小节聚类结果的资源匹配优化算法描述如下：
1) 接收资源匹配申请，获取任务的运行需求，即虚拟资源运行任务所必需的配置信息以及任务运行的时限等服务标准；
2) 查询满足任务需求的虚拟资源，生成资源匹配初始列表L0；
3) 搜索列表L0中虚拟资源的类型，即分为计算型、存储型及网络型；同时，通过改进二分K均值的任务聚类分析结果，掌握任务消耗特征；
4) 根据2) 与3) 分析结果，将虚拟资源匹配给适应其配置需求与消耗特征的任务，形成资源匹配优化列表L，并发送给任务管理服务器.
3 实验结果与分析 3.1 任务聚类下面对虚拟计算实验床平台所发布的一周运行数据进行分析，从任务需求、统计数量、任务消耗等特征进行聚类研究，现将实验结果阐述如下.
图 1描述的是基于网络服务提供商与省份属性进行的任务聚类分析，依据网络服务提供商(ISP，internet service provider)不同，可将任务分为5类，即移动互联网、联通互联网、铁通互联网、教育和科研计算机网、中国公用计算机互联网.
|
图 1 基于网络服务提供商与省份的任务聚类结果 |
图 2通过累积分布函数(CDF, cumulative distribution function)分别描述任务消耗CPU与内存的情况.可以看出，任务ctest-app-33608与ctest-app-33108近90%的任务消耗CPU为0.1；总体来说，所有任务消耗CPU超过0.5的为极少数；任务ctest-app-33608与ctest-app-33609超过90%任务消耗内存为0.1，各任务具有不同内存消耗特征.
|
图 2 不同任务消耗CPU与内存的累积分布函数曲线 |
依据任务参数，即任务的内存与CPU消耗情况进行聚类研究，聚类分析结果图 3描述了取值半径r为1和0.5时，当合并系数φ从0.3增加到0.62时，簇类数量减少.随着合并系数的增加，簇类数量也减少，当合并系数为0.62时，任务聚类数量为10.也就是说，当取值半径减小、合并系数增加时，簇类数目也逐渐越少.
|
图 3 r与φ不同取值的任务聚类结果 |
Min-Min算法是一种实现简单、执行时间快的调度算法，其思想是首先映射小的任务，并且映射到执行快的机器上；Max-Min算法与之不同的是先调度大任务，任务到资源的映射是选择最早完成时间最大的任务映射到所对应的机器上.这两种经典的任务调度被广泛应用到计算场景中，实验模拟在任务调度不变的前提下，将基于聚类的资源匹配优化模型应用到任务调度中验证模型有效性.不同于以往的资源匹配模型，基于虚拟资源与任务聚类的资源匹配优化模型(RTC-RMOM，resource matching optimization model based on resource and task clustering)进一步筛选初始匹配列表L0中符合任务需求的虚拟资源，结合虚拟资源与任务的聚类结果，将任务类型相对应的虚拟资源进行匹配，这样可以缩减精准匹配范围.
实验选取1万个任务，经过20次验证，将经典任务调度算法Min-Min、Max-Min，基于资源模糊聚类的调度优化算法FCS-Min-Min[3]、FCS-Max-Min[3]与基于虚拟资源与任务聚类的资源匹配优化的任务调度算法RTC-Min-Min与RTC-Max-Min进行比较.
图 4(a)的Min-Min任务成功率介于83%~90%，FCS-Min-Min通过资源模糊聚类分析有效提高任务成功率，而RTC-Min-Min在FCS-Min-Min基础上，利用虚拟资源与任务双重聚类分析，任务成功率最高为96.9%，与FCS-Min-Min相比，平均提高了近3.7%.同样地，在图 4(b)中，经由多次实验结果表明，与经典算法Max-Min比较，FCS-Max-Min与RTC-Max-Min仍在不同程度上提高了任务执行成功数，其中算法RTC-Max-Min较Max-Min平均提高了近6.2%.
|
图 4 基于虚拟资源与任务聚类的任务成功数对比 |
虚拟计算所具有的开放、动态、异构等特性，海量资源的多样性与高度自治性，以及应用需求模糊、数量庞大等诸多不确定因素，使得资源匹配面临巨大挑战，从虚拟资源与任务双重角度进行聚类分析是非常必要而有效的解决方式.在后续研究中，应建立线上实时分析与线下离线处理相结合的分析手段，挖掘虚拟资源与任务的多维特征，为资源匹配优化提供更精准的理论基础.
| [1] | Lu Xicheng, Wang Huaimin, Wang Ji. Internet-based virtual computing environment: beyond the data center as a computer[J]. Future Generation Computer System-the International Journal of Grid Computing and Science, 2013, 29(1): 309–322. doi: 10.1016/j.future.2011.08.005 |
| [2] | Liu Zhenhua, Wierman A, Chen Yuan, et al. Data center demand response: avoiding the coincident peak via workload shifting and local generation[J]. Performance Evaluation, 2013, 70(10): 770–791. doi: 10.1016/j.peva.2013.08.014 |
| [3] |
朱春鸽, 张哲宇, 刘欣然, 等. 虚拟计算环境下基于模糊聚类的资源调度算法[J]. 北京邮电大学学报, 2015, 38(S1): 6–10.
Zhu Chunge, Zhang Zheyu, Liu Xinran, et al. Research on fuzzy clustering based on algorithm for resource scheduling in virtual computing environment[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(S1): 6–10. |
| [4] |
孙佳佳, 王兴伟, 高程希, 等. 云环境下基于神经网络和群搜索优化的资源分配机制[J]. 软件学报, 2014, 25(8): 1858–1873.
Sun Jiajia, Wang Xingwei, Gao Chengxi, et al. Resource allocation scheme based on neural network and group search optimization in cloud environment[J]. Journal of Software, 2014, 25(8): 1858–1873. |
| [5] | Guo Fengyu, Yu Long, Tian Shengwei, et al. A workflow task scheduling algorithm based on the resources' fuzzy clustering in cloud computing environment[J]. International Journal of Communication Systems, 2015, 28(6): 1053–1067. doi: 10.1002/dac.v28.6 |
| [6] | Hussain H, Malik S U R, Hameed A, et al. A survey on resource allocation in high performance distributed computing systems[J]. Parallel Computing (Systems & Applications), 2013, 39(11): 709–736. |
| [7] | Di S, Kondo D, Cappello F. Characterizing and modeling cloud applications/jobs on a Google data center[J]. Journal of Supercomputing, 2014, 69(1): 139–160. doi: 10.1007/s11227-014-1131-z |