沙特国王大学计算机与信息科学学院：基于有色Petri网的服务器整合问题方法研究

Journal of King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com基于有色Petri网和CPN工具伊萨姆·阿佐尼沙特阿拉伯利雅得沙特国王大学计算机和信息科学学院接收日期：2014年12月14日;修订日期：2015年1月26日;接受日期：2015年2月15日2015年10月9日在线发布本文提出了一种利用有色Petri网（CPNs）解决异构机群中服务器合并问题的新方法。服务器整合旨在通过减少运行群集中现有虚拟机所需的服务器数量来降低能源成本并提高资源利用率。它利用了新兴的实时迁移技术，允许在服务器之间迁移虚拟机，而无需停止其提供的服务。服务器整合方法试图找到旨在最小化集群的必要大小的迁移计划。我们的方法找到的计划，不仅最大限度地减少使用的服务器的总数，但也最大限度地减少总的数据迁移开销。后一个目标没有被其他方法和化学方法考虑在内。我们探讨了使用CPN工具在分析状态空间的CPNs。由于CPN模型的状态空间可以随着集群的大小呈指数增长，我们研究了不同的技术来生成和分析状态空间，以便在可接受的时间和计算能力内找到良好的服务器整合计划©2015作者制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍虚拟化技术的进步使得网格和集群计算系统中的服务器整合成为使用虚拟机来运行企业的应用程序，可以通过将多个虚拟机分组在一个物理机器中来减少集群中的机器数量这允许跨应用程序更好地多路复用集群资源。电子邮件地址：ialazzoni@ksu.edu.sa沙特国王大学负责同行审查为了处理集群应用程序的动态工作负载，有必要使用动态服务器整合技术。动态服务器整合技术采用虚拟机（VM）的实时迁移。使用实时迁移，可以跨物理机（PM）重新分配VM，以提高集群的可扩展性（Clark等人， 2005年）。然而，重要的是减少迁移开销，即，传输的数据量，因为这对迁移VM运行的应用程序的性能有影响（Wood等人， 2007年）。已经提出了几种用于计算机集群的动态服务器合并的方法（参见Bobroff etal. （2007）和Hermenier et al.（2009））。这些方法旨在最小化托管VM所需的PM的数量。然而，这些方法中的大多数忽略了随之而来的迁移开销。虽然服务器整合在概念上http://dx.doi.org/10.1016/j.jksuci.2015.02.0011319-1578© 2015作者制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词有色Petri网;异构集群;服务器合并;离散优化;CPN工具;状态空间搜索异构计算机集群的服务器整合377与NP难的经典向量填充问题接近这些需求包括最小化迁移开销的需求以及处理可能异构的物理机的需求。此外，服务器整合必须考虑对虚拟机放置的不同约束。在 本 文 中 ， 我 们 提 出 了 一 种 基 于 有 色 Petri 网（ CPNs ） 的 合 并 新 方 法 （ Jensen 和 Kristensen ，2009）。CPNs提供了一种图形化的语言来描述和分析并发系统的模型CPN已经在很多领域中使用，但是本文是第一篇推荐在异构集群的服务器整合中使用作为一种建模语言，CPNs自然地对服务器整合问题进行建模，因此我们的目标是探索它们作为求解方法的用途。在CPN模型中，我们使用位置对PM进行建模，并使用彩色标记对VM进行建模CPN模型旨在获取每个PM的资源通过这样做，我们的方法具有适用于异构集群的优势与此同时，我们的方法直接在CPN模型中加入了对VM放置的约束我们使用CPN工具来创建CPN模型并分析它们的状态空间。由于本文中开发的CPN模型的状态空间可以指数增长，我们提出了几种技术来减少状态空间的大小，并有效地探索它。该文件的贡献概述如下：1. 我们将探讨在服务器整合的上下文中使用CPN。2. 所提出的方法不仅最大限度地减少了托管虚拟机所需的服务器数量，而且还最大限度地减少了所需的重新配置成本。3. 所提出的方法适用于异构集群，并可以将几种类型的约束的虚拟机的位置。4. 我们实验不同的技术来处理由此产生的大状态空间，允许扩展的方法工作在更大的集群大小。本文的结构如下。在第2节中，我们更正式地定义了合并问题。相关工作在第3节中讨论。我们在第4节中说明了我们的方法。在第5节中，我们提出并分析了几种技术的实验结果，以解决状态爆炸问题时，我们的方法应用于较大的集群。第6节是本文的结论。2.问题公式化考虑一个由许多物理机器组成的集群。每个PM有一些处理单元，并提供vides一定量的内存。使用虚拟化技术，许多虚拟机被整合在物理机器上。每个VM都需要一定数量的内存。根据在VM上运行的应用程序的状态，可以将VM分类为活动或非活动VM。活动VM需要多个处理单元。另一方面，不活动的VM不需要 处 理 单 元 。 集 群 模 型 是 类 似 于 Ferreto 等 人 。（2011），Hermenier et al. （2009）和Murtazaev and Oh（2011）。集群的配置将VM映射到PM。从初始可行配置开始，其中每个VM已被分配足够量的存储器并且每个活动VM可以访问其自己所需数量的处理单元，目标是重新配置集群以达到使用最小可能数量的PM的可行配置。重新配置步骤必须尊重VM对处理单元和存储器的要求：如果目的地PM没有足够的空闲存储器量，则不能迁移VM，并且如果目的地PM没有所需数量的空闲处理单元，则不能迁移活动VM重新配置计划概述了达到使用最少PM数量的配置为了减少迁移开销，重新配置计划还需要最小化传输的数据总量。迁移单个VM的开销等于其所需的内存大小（以下称为其内存大小）。考虑图1中的初始配置。每个下午亲vides一个单一的处理单元，并有1024 MB的可用存储器。有七个具有不同内存大小的VM。每个活动VM需要单个处理单元。每个VM都标有其内存大小和状态。我们的目标是找到一个重新配置计划，以达到配置，使用最少数量的PM。重新配置计划应最大限度地减少总的数据迁移开销。图2示出了仅需要三个物理机器的可能的最小配置。下面概述了一个最佳的重新配置计划，以达到最小的配置在图。第二章：1. 将VM5从PM5迁移到PM4（迁移成本=256MB）。2. 将VM7从PM1迁移到PM2（迁移成本=384MB）。此计划的总迁移成本为640 MB。结果配置仅使用三个PM。将此重新配置计划与使用首次拟合递减（FFD）启发式计算的另一个重新配置计划进行对比，该启发式已在其他服务器整合工作中使用（参见Bobroff等人，2007年，Hermenier等人，2009和Wood等人，2007年）。在FFD中，VM首先按其内存大小以降序排序给定VM的排序序列，如果需要的话，每个VM被迁移到它将适合的第一个（最低索引的）PM（Coffman等人，（1997年）：1. 迁移VM2从PM3 到 PM2（移徙成本=512 MB）。2. 迁移VM 1从PM4 到 PM1（移徙成本=256 MB）。3. 迁移VM3从PM2 到 PM1（移徙成本=256 MB）。4. 迁移VM5从PM5 到 PM3（移徙成本=256 MB）。5. 迁移VM6从PM4 到 PM3（移徙成本=256 MB）。由此产生的配置使用三台机器类似的最佳重新配置计划。然而，该计划的总迁移成本为1536 MB，比最佳重新配置计划多240%。FFD不考虑378I. 阿佐尼图1一个包含5台机器的同构集群的初始示例配置。半圆形框表示PM，圆形表示VM。图2仅使用三个PM的最小配置虚拟机在群集中的初始放置此外，FFD不考虑所产生的迁移开销。这两个主要原因解释了使用FFD发现的计划的显著寻找最佳的重新配置计划似乎与NP-难的二维装箱问题有关（参见Caprara和Toth，2001，Skiena，2008和Spieksma，1994），其中维度对应于处理单元的数量和可用内存的数量然而，这两个问题之间存在着重要的区别在寻找最佳的重新配置计划时，集群从初始可行配置开始。然后，目标是确定达到最小可行配置的中间步骤。中间步骤必须遵守VM对处理单元和内存的要求（以及可能的其他约束）。这些步骤还应最大限度地减少总虚拟机迁移开销。这些要求增加了寻找最优重构方案的难度。可能由于缺少平台要求，某些虚拟机可能无法整合到给定的在寻找最优重构方案时，必须对中间构形进行约束以满足这些位置约束。在第4节中，我们将讨论如何扩展CPN模型以纳入此类约束。3. 相关工作已经提出了几种服务器整合的方法。Hermenier等人（2009）的作者介绍了Entropy，这是一种用于同质集群的动态合并管理器Entropy中的整合基于约束编程，并将迁移开销纳入异构计算机集群的服务器整合379帐户.熵使用两个阶段。第一阶段查找托管所有VM所需的最小节点数以及使用此节点数的可行配置示例第二阶段计算一个等效的可行配置，最大限度地减少重新配置时间。熵使用几种技术来降低计算成本，包括使用VM和PM等价类。Entropy代表了与我们的方法最接近的整合经理。然而，我们的方法直接考虑异构的物理机器，可以扩展到包括第2节中讨论的重新配置约束。Bobroff等人的作者。（2007）提出了一种基于时间序列预测技术和区间支持算法的动态合并管理器。虚拟机的资源需求（包括CPU需求）可能会随时间而变化，因此需要预测每个预测间隔的这些需求。基于FFD的重配置算法试图最小化托管虚拟机的物理机的数量，该物理机受制于需求过载资源容量的速率由与服务水平协议（SLA）相关的指定阈值限制不考虑VM迁移开销。我们的方法假设虚拟机的资源需求是固定的，并考虑了迁移开销。ReCon（Mehta 和Neogi，2008年）是一个规 划工具，可用于推荐多集群数据中心中的服务器整合。服务器整合的目标是在满足系统、应用和法律约束的同时，最大限度地减少所需PM的数量该问题是制定一个优化框架，使用CPLEX解决。尽管该工具为每个合并窗口调用优化器以找到重新配置计划中的最佳步骤，但是合并所有步骤的最终重新配置计划可能不会最小化总迁移开销。此外，ReCon可能无法很好地扩展大型数据中心。Ferreto等人（2011）的作者提出了一种LP公式和算法来控制VM迁移。他们的服务器整合方法不迁移具有稳定资源需求的虚拟机，以减少迁移对其工作负载性能的影响。该方法被证明可以减少虚拟机迁移的数量和所需的物理机，但是，总的数据迁移开销没有被考虑在内。因此，具有大内存需求的虚拟机被认为与具有小内存需求的虚拟机相同。他们的方法相比，修改版本的FFD只迁移虚拟机与不同的资源需求。Sercon是另一种服务器整合算法（Murtazaev和Oh，2011）。该算法最大限度地减少所需的物理机器的数量，同时也试图最大限度地减少迁移的数量但是，它不考虑总的数据迁移开销，也不考虑迁移的虚拟机的不同内存需求（我们的CPN方法）。Sercon算法继承了一些著名的装箱算法，如FFD的属性，除了它的目标，以尽量减少迁移的数量这是通过遵循全有或全无属性来完成的，即来自节点的所有VM都被迁移，或者如果其中一个VM失败，则不迁移任何VM。通过仿真实验，比较了Sercon算法和FFD算法在迁移效率方面的差异，并分析了它们对VM迁移次数的影响。Sercon的可扩展性分析表明，该算法，Rithm对于中等 规模的数据中心（ VM数量最多 为1000，PM数量最多为100）具有足够的可扩展性。作者还提出了一个简单的算法，称为迁移排序，以改善整体迁移时间。这个想法是将所有计划的迁移分组到最少数量的非重叠迁移队列中。该算法可以应用在我们的上下文中，以减少最佳的重新配置计划的整体迁移时间，因为计划中的一些步骤可以并行完成。我们的方法不考虑VM之间的通信流量模式在某些情况下，相互带宽使用量较大的虚拟机Meng等人（2010）的工作提出了一种流量感知的VM放置策略。作者制定的VM放置作为一个优化问题，并设计了一个启发式近似解决大型数据中心的VM放置问题此外，Shrivastava et al. （2011）将虚拟机之间的通信流量模式和底层网络拓扑知识结合到多层应用程序的虚拟机放置决策中。在Jayasinghe等人（2011）中，作者提出了结构约束感知的VM放置，以提高部署在基础设施即服务（IaaS）云中的服务的性能和可用性他们的方法侧重于创建初始VM放置，以满足三种类型的结构约束：(i)需求约束，其定义每个VM所需的资源分配的下限，（ii）可用性约束，其描述VM放置的配置和反配置约束，以及（iii）通信约束，其描述VM对之间的通信成本他们的方法基于数据中心的物理网络拓扑和逻辑分组将数据中心建模为树结构同样，我们的方法可以扩展到包括数据中心的层次结构此外，我们的方法侧重于虚拟机的动态放置，同时最大限度地减少迁移开销。Khanna等人（2006）的作者开发了一种在检测到性能问题时迁移VM在他们的方法中，他们假设SLA到VM资源利用率的映射。当超过资源利用的阈值时，VM重新分配过程被触发。他们的方法试图最大限度地减少VM迁移的数量。我们的方法是独立于应用程序的，并且不监控单个VM的性能。在Speitkamp和Bichler（2010）中，在多维装箱问题的背景下正式分析了服务器整合问题。比较了几种算法 ， 包 括 FFD 和 线 性 规 划 松 弛 算 法 。 在 Gao 等 人（2012）中，使用蚁群优化Meta启发式来解决服务器合并问题。 在Deng et al. （2013），作者提出了一种新的服务器整合管理器，其使用线性规划来找到最优配置，然后使用优化的基于拓扑排序的迁移顺序生成方法来降低重新配置成本。这是通过尽可能重叠不同VM的迁移过程来实现的所有这些技术都没有考虑在重新配置计划中引起的VM数据迁移Grama和Kumar（1999）的工作调查了用于解决离散优化问题（例如服务器合并问题）的几种离散优化问题通常被表述为寻找380I. 阿佐尼图（状态空间图）中从指定的初始节点到几个可能的最终节点之一的路径。作者还回顾了几种搜索状态空间的技术，如各种深度优先和最佳优先搜索，并讨论了如何将这些算法并行化。CPN工具包括有限的功能来控制状态空间的生成方式。然而，为了将我们的方法扩展到更大的集群，在我们的CPN模型的背景下探索这些技术的使用是有意义的。4. 所提出的方法为了说明我们的方法，我们为图1中的配置开发了一个CPN模型。一个全面的有色Petri网和CPN工具指南 ， 包 括 正 式 定 义 ， 可 以 在 Jensen 和 Kristensen（2009）中找到。第4.1节描述了CPN模型，第4.2节描述了使用CPN工具生成和分析状态空间。4.1. CPN模型CPN模型如图3所示。在该模型中，令牌在PM中指定VM在PM上的放置当当VM在两个PM之间迁移时，对应的令牌通过位置网络移动。融合集CPU和MEMORY用于在VM不断迁移时分别记录每个PM上的可用CPU和内存资源。PlaceQ记录了总的累积迁移成本。颜色集定义如下：colsetUNIT = unit;colset INT = int;colsetBOOL = bool;colsetSTRING = string;colsetvmStatus = with A|inti;colset cpuReqt = int;colset memReqt = int;colset accCosts = int;colset VM = product vmStatus * vmID * cpuReqt *memReqt;列PM =索引PM，其中1.. numMachines; colsetINTxPM = product INT * PM;colsetVMxPM = productVM * PM;变量声明如下：图3图1中配置的CPN模型。异构计算机集群的服务器整合381-在CPN模型中包括放置约束的一种方法是将相应的条件添加到转换进入PM的保护中。例如，假设对于图1中的配置，VM5不能被整合到PM1上。我们可以将下面 的合取词添加 到转换的保 护输入 PM ： not（p=PM（1）andalso i=5）。我们对每个放置约束重复相同的操作，从而禁用相应的绑定。4.2. 状态空间生成和分析颜色集VM用于对虚拟机进行建模。VM具有状态（活动或不活动）、标识号、表示VM需要多少处理单元的数字以及表示其存储器大小的数字。例如，令牌颜色（A，2，3，512）表示活动的虚拟机VM 2。VM2需要三个处理单元，其内存大小为512 MB。为了对给定PM中的可用处理单元进行建模，我们使用融合集CPU。位置cpu1和cpu2是融合集的成员在融合集中的地方总是共享相同的标记。颜色类型INTxPM的令牌驻留在由CPU的融合位置表示的复合位置中。令牌的值表示相应PM中空闲处理单元的数量因此，在图1的初始标记中， 3，融合位置cpu1中的一个令牌具有颜色（0，PM（1）），因为最初PM 1保持活动VM（VM 7），因此PM 1没有空闲处理单元。如果PM中的空闲处理单元数量少于VM所需的数量，则活动VM无法进入PM（请参阅转换进入PM的保护）。如果VM进入PM，则CPU的复合位置中的标记的值被更新（参见从transitionenter PM到placecpu1的弧的表达式）。这与VM离开PM的情况类似。融合集MEMORY用于对给定PM中的可用内存进行建模。位置memory1和memory2是融合集合的成员颜色类型为INTxPM的令牌驻留在由MEMORY的融合位置表示的复合位置中。令牌的值表示相应PM中的空闲内存量。因此，在图3的初始标记中，融合位置存储器1中的一个令牌具有颜色（640，PM（1）），因为PM（1）最初托管VM 7，因此PM（1）中的空闲存储器量是1024 384=640 MB。正如转换进入PM的保护所示，如果VM的内存大小超过PM中的空闲内存量，当VM进入PM时，MEMORY的复合位置中的标记的值被更新（参见从transitionenter PM到placememory1的弧的表达式）。这类似于VM离开PM的情况。我们用来减少状态空间的一种技术是强制一个令牌可以驻留在位置网络中的任何给定标记处。这是通过使用这个地方来实现的。P. 这是合理的，因为目标是找到一个最佳的重新配置计划，最大限度地减少总的VM迁移开销。每个迁移的VM引起的迁移开销等于其内存大小，因此并行迁移两个或更多个VM不会影响迁移开销。这显著地减小了状态空间，而不影响所得到的最优重新配置计划。我们使用CPN Tools的状态空间工具来找到最优的重构方案。图4示出了用于生成和搜索状态空间的查询函数。这些查询是用CPN ML编程语言编写的（在Jensen和Kristensen，2009年的第3章中介绍）。对于由n表示的给定标记，函数numIdleMachines返回空闲的物理机器的数量。空闲PM不托管任何VM，并且因此不 存 在 与 该 PM 相 对 应 的 适 当 的 令 牌 PM 。 函 数numBusyMachines返回繁忙（非空闲）机器的数量，因此它等于numMachines-numIdleMachi- nes（n）。变量numMachines在前面用值5声明。块1计算整合VM所需的非空闲机器的最小数量这是通过定义谓词DesiredTerminal1来完成的，如果由n表示的标记满足在原地网络中没有VM令牌的条件，则该谓词返回true。为了找到最小数量的忙碌（非空闲 ） 机 器 ， 我 们 使 用 CPN ML 预 定 义 函 数SearchNodes。SearchNodes应用组合函数Int.min，它接 受 两 个 整 数 参 数 并 返 回 它 们 的 最 小 值 。SearchNodes 函 数 仅 探 索 满 足 DesiredTerminal1 的 标记。该函数的输出是满足DesiredTerminal1的任何标记所需的非空闲机器的最小数量。它存储在变量x中，将在下一个块中使用。块2搜索最优重构计划。这是通过搜索对应于使用最小数量的非空闲机器x并且最小化总累积迁移成本的配置 的 标 记 来 完 成 的 。 如 果 由 n 表 示 的 标 记 满 足DesiredTerminal1并且非空闲机器的数量等于x，则谓词DesiredTerminal2返回true。函数tot_cost返回给定标记的总累积迁移成本，其等于驻留在位置Q的令牌的值。为了找到最小配置，我们使用函数SearchNodes两次 。 在 第 一 次 ， 我 们 使 用 它 来 找 到 满 足DesiredTerminal2的所有标记上的总累积迁移成本的最小值（该值存储在mc中）。在第二次，我们使用它来找到满足DesiredTerminal2的标记，并且其总累积迁移成本等于mc。第二个SearchNodes的输出是对应于最小配置的所有标记的列表从这个标记开始，使用CPN工具可以向后遍历状态空间，以找到从初始标记开始的路径。该路径代表最优的恢复计划。图5示出了对应于第2节中讨论的最优重新配置计划的最优重新配置计划。val numMachines =5; var x，y：INT;vart：vmStatus;vari：vmID;var CPU：cpuReqt;varCPU：memReqt;var cost：accCosts;var z：UNIT;varv：VM;varp：382I. 阿佐尼图 4用于生成和搜索图1的CPN模型的状态空间的CPN ML查询。3 .第三章。在生成状态空间时，需要设置分支选项以指定不计算节点的后继者的条件。由于总的迁移成本可以无限增长，因为他们被迁移，这是重要的是提供一个上限的总迁移成本。这可以在CPN Tools的状态空间工具中使用OGSet.BranchingOptions函数完成，如下所示：图图5状态空间中的路径表示图1中的配置的最优重配置计划。1.一、OGSet.BranchingOptionstransInsts= NoLimit，Bindings=NoLimit，Predicate= fn n =>（tot_cost（n）= max_tot_cost）};异构计算机集群的服务器整合383表1不同上界下的状态空间统计总的迁移成本。在最后一列中，总成本是针对计算出的最优重新配置计划。设置上限状态空间统计信息约束节点数弧数秒数122000 MB 14，855 30，61760640 MB 3128 6300 3总累计迁移成本640640这确保生成部分状态空间，其中总累积迁移成本不超过在CPN ML查询开始时声明的max tot cost。除了使用分支选项之外，还可以在状态空间工具中设置停止选项，以确定状态空间的计算何时停止。例如，以下函数在max Secs秒数（也在CPN ML查询开始时声明OGSet.StopOptions{Nodes=NoLimit，Arcs=NoLimit，Secs=max_Secs，Predicate = fn _=> false};然后可以继续计算状态空间可以重复这种停止和继续状态空间计算的模式，注意在每个计算回合结束时发现的最优重新配置计划是到目前为止计算的这是我们的方法的一个优点，可以用来处理潜在的大状态空间。5. 评价第4节中提出的方法可能会遇到状态爆炸问题。对于比第2节中讨论的集群更大的集群，状态空间可以具有非常大数量的可达状态，使得找到最佳重构计划是不可行的本节介绍应用几种技术来缓解状态爆炸问题的结果。这些技术并不能保证最佳的重新配置计划，而是在合理的时间和计算能力内找到比FFD效果更好的重新配置计划。5.1. 控制参数max_tot_cost和max_Secs考虑用于生成和分析CPN模型的状态空间的CPN ML查询（参见图4）。有两个变量限制探索状态空间的大小：max_tot_cost和max_Secs。第一个变量为总累积迁移成本设置上限，而第二个变量允许CPN Tools在指定的时间段（以秒为单位）后停止生成为了与其他服务器整合方法进行比较，我们将max_Secs设置为60 s（参见Murtazaev andOh（2011））。因此，可以设 置 来 控 制 状 态 空 间 大 小 的 唯 一 变 量 是max_tot_cost。处 理 状 态 爆 炸 问 题 的 第 一 种 技 术 是 将 变 量max_tot_cost设置为较小的值。表1显示了在两种不同设置下计算的状态空间大小的信息。这些设置对总累积迁移成本使用不同的上限（即，max_tot_cost的不同值）。如结果所示，对于第二种设置，使用较低的max_tot_cost值可以显著减少状态空间的大小和生成状态空间所需的时间请注意，状态空间工具用于配备3.00 GHz双核处理器和2 GB RAM的戴尔台式机。这 种 技 术 受 到 两 个 主 要 限 制 。 首 先 ， 确 定max_tot_cost的合适值可能不容易。微不足道它可以基于其他算法（如FFD）的使用，但是生成的状态空间的大小对所选值非常敏感其次，如下面所讨论的，当考虑较大的集群大小时，状态空间的大小呈指数级增加在这种情况下，在60 s中生成的状态空间探索总累积迁移成本远小于max_tot_cost的状态（节点），并且返回的重新配置计划在最小化所使 用 的 物 理 机 的 数 量 方 面 远 非 最 优 因 此 ， 为max_tot_cost设置合适的值对此类情况的影响较小。为了证实上一段中讨论的第二个限制，表2显示了在10个PM和14个VM的集群上应用我们的方法的结果我们假设通过组合具有图1的初始配置的五机器集群的两个实例来构建集群，同时重命名PM和VM，使得它们中的每一个获得唯一的名称。之所以选择这一点，是因为第4节中的结果提供了关于最佳重新配置计划中最小物理机数量和最小累积迁移成本的提示我们将此设置称为使用图1的基本配置的两个实例的倍数构建的集群。1.一、稍后，我们将使用更高的倍数来显示更大集群上的表2中的结果假设max_Secs设置为60 s。对于表2中所示的结果，可以观察到两点。首先，所获得的重新配置计划不是最优的，因为存在另一个计划，其可以使用6个PM而不是8个PM来达到配置。这可以使用具有图1的基本配置的五机器集群的最优重新配置计划的相同步骤来实现两次：每个复合集群一次。其次，很明显，将max_tot_cost设置为较大的值对结果没有这是因为在60 s内可以生成的状态空间存在最大限制请注意两个集合中节点和弧的结果数量当使用更高的倍数时，可以进行相同的观察，然而，所获得的重新配置计划在使PM的数量最小化方面变得最差。例如，当使用图1的基本配置的三个实例的倍数时。 1并将上限设置为2000 MB，则发现PM的最小数量为13 PM（假设max_Secs设置为60 s）。存在另一个重新配置计划，其可以达到具有9个PM的配置。5.2. 控制参数Bindings为了解决5.1节中讨论的问题，我们提出了一种新的技术，该技术利用了CPN Tools中的一个特性，该特性允许控制状态空间的生成方式。之一384I. 阿佐尼×表2使用图1的基本配置的两个实例的倍数构建的集群的状态空间统计。1.一、设置上限状态空间统计最小PM数累计节点数弧数秒数迁移成本12000 MB21,71129,4566085122640 MB20,20927,9446085126. 结论图 4 中 的 ML 函 数 OGSet.BranchingOptions 的 参 数 是Bindings，其指定要用于为状态空间中的每个节点找到后继标记的启用绑定的最大数目。通过将Bindings设置为一个特定的数字（默认值为NoLimit），状态空间的生成变得更加深度优先，而不是CPN Tools中状态空间生成的默认广度优先方式。我们将绑定设置为3，因为这会产生足够的随机性来改进所发现的最佳重新配置计划。同时，我们的实验表明，将绑定设置为三个可以获得良好的结果，生成状态空间的时间段。表3示出了在使用图1的基本配置的二到六个实例的倍数构建的集群上应用该技术的结果，假设max_Secs被设置为60 s并且Upper Bound被设置为640 MB按顺序的倍数以适应不同的集群大小。该表还包括执行FFD直到达到使用相同最小PM数5.3. 其他方法针对CPN模型的状态爆炸问题，已有几种方法被提出。这些方法包括双曲线集方法（Valmari，1988）、扫描线方法（Christensen等人，2001）和等效方法（见Jensen和Kristensen（2009）第8.4节）。这些方法可以应用于某些集群配置，其中某些依赖关系和对称性被利用。不过，一般来说，这些方法未必适用在具有高度异质性的集群配置上。因此，我们不探讨这种方法。此外，CPNTools目前没有实现任何状态缩减方法。本文提出了一种使用CPN和CPN Tools进行服务器整合的新方法我们的方法考虑到总的数据迁移开销，这在其他方法中没有考虑过。该方法提出了几种技术，以应付由此产生的大状态空间。使用我们的方法的一个额外的优点是，可以在任何时候暂停生成状态空间，返回到目前为止计算的最佳结果。这增加了我们的方法的反应性，从而提高了它对更大集群的适用性。我们的方法的另一个优势是CPN模型固有的灵活性，以捕获对虚拟机放置的几个约束主要的挑战是有效地处理由此产生的指数增长的状态空间。作为未来的工作，我们计划探索其他技术的状态空间分析，旨在提高我们的方法的可扩展性，通常用于常见的数据中心的大型集群工作致谢这项研究得到了沙特阿拉伯利雅得沙特国王大学计算机与信息科学学院研究中心（RC）的支持（项目ID：RC1303103）。引用Bobroff，N.，Kochut，A.，贝蒂，K.A.，2007.动态放置虚拟机以管理SLA违规。集成网络管理研讨会论文集，pp。119-128. Caprara，A.，Toth，P.，2001.二维向量装箱问题的下界与算法。离散应用数学 111（3），231克里斯滕森，S.，克里斯滕森，L.M.，Mailund，T.，2001.状态 空 间 探 索 的 扫 描 线 方 法 。 在 Proceedings of theInternational Conference on Tools and Algorithms for theConstruction and Analysis of Systems，pp.450-464克拉克角Fraser，K.，Hand，S.，汉森，J.G.，Jul，E.，林巴赫角，普拉特岛，Warfield，A.，2005年虚拟机的实时迁移网络系统设计与实现研讨会论文集273-286。科夫曼，E.G.，Garey，M.R.，约翰逊，D.S.，1997.装箱的近似算法：综述。在：近似算法的NP-难问题。出版社：PWS Publishing Co，pp. 46比93CPLEX。http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.CPN Tools. http://cpntools.org/网站。登湖，Jin，H.，吴，S.，2013.合并：虚拟化环境中的服务器整合。在独立，自主和安全计算的国际会议论文集，pp。606-612表3使用绑定=3的CPN方法和FFDCPN方法FFD倍数最小总最小总累计数number积累PMs迁移经前综合症迁移成本成本27 102472432311 1280113712416 1152162816521 1536212944626 1152263072异构计算机集群的服务器整合385Ferreto，TC，内托，硕士，Calheiros，R. N.，De Rose，C.A.F.，2011年。针对虚拟化数据中心的具有迁移控制的服务器整合。未来一代Comput. 系统 27（8），1027-1034。高，Y.，Guan，H.，齐，Z.，王，B.，2012.蚁群算法求解虚拟化数据中心服务器整合问题。J. Comput. 告知。系统 8（16），6631-6640。Grama，A.，库马尔，V.，1999.离散优化问题的并行搜索技术研究现状。IEEE Trans. Knowl. Data Eng. 11（1），28-35.Hermenier，F.，洛尔卡，X. ，Menaud，J. M.，穆勒，G.，Lawall，J.，2009. Entropy：集群的整合管理器。在虚拟执行环境会议论文集，pp。41比50Jayasinghe，D.，Pu，C.，Eilam，T.，Steinder，M.，惠利岛，Snible，E.，2011.通过结构化约束感知虚拟机放置，提高IaaS云上托管的服务的性能和可用性。在服务计算会议的会议记录中，pp。72比79詹森，K.，克里斯滕森，L.M.，2009.着色Petri网-并发系统的建模和验证。斯普林格。Khanna，G.，Beaty，K.，Kar，G.，Kochut，A.，2006.虚拟化服务器环境中的应用程序性能管理。在网络运营和管理专题论文集，pp。373-381.Mehta，S.，Neogi，A.，2008. ReCon：一个在多集群数据中心推荐动态服务器整合的工具。网络运营与管理研讨会论文集，pp。363- 370。孟，X.，帕帕斯，五，张，L.，2010.通过流量感知虚拟机部署提高数据中心网络的可扩展性。在信息通信会议的会议记录中，pp。1154-1162年。Murtazaev，A.，哦，S.，2011. Sercon：使用虚拟机实时迁移实现绿色计算的服务器整合算法。 IETETech. Rev. 28（3），212-231。Shrivastava，V.，Zerfos，P.，李，K.- W.，Jamjoom，H.，刘玉- H、Banerjee，S.，2011年。数据中心中的应用感知虚拟机迁移在信息通信会议的会议记录，pp。66比70Skiena，S.，2008年，第二版。算法设计手册（Algorithm DesignManual）Speitkamp，B.，Bichler，M.，2010.虚拟化数据中心服务器整合问题的数学规划方法。IEEE传输服务Comput. 3（4），266-278。Spieksma，F.C.R.，1994.二维向量装箱问题的分枝定界算法。Comput.操作员Res. 21（1），19-25.Valmari，A.，1988.通过减少可达性图生成的错误检测。在Proceedings of the European Workshop on Appli- cation andTheory of Petri Nets，pp. 95比112Wood，T.，Shenoy，P.，文卡塔拉曼尼，A.，Yousif，M.，2007.虚拟机迁移的黑盒和灰盒策略。USENIX Symposiumon Networked Systems Design and Implementation（USENIX网络系统设计与实现研讨会）