本发明提出了一种面向云数据中心网络优化的虚拟机部署方法，其包括如下步骤：(1)云租户请求资源拓扑分析，分析云用户请求的资源拓扑的特点并根据问题本身的难易程度实施启发式部署策略；(2)执行启发式部署策略，由于该问题本身是NP难的，在不能保证部署方案最优的情况下，采用基于图论的部署策略。藉由本发明可以实现在最小化云数据中心网络链路的最大利用率，以最大程度地来减少网络拥塞发生的可能性。
1.一种面向云数据中心网络优化的虚拟机部署方法，其特征在于包括步骤：（1）资源拓扑分析，分析的对象包括租户请求数量n以及每个请求的拓扑结构，其中请求的拓扑结构以带权无向图给出，顶点表示虚拟机，边表示虚拟机两两之间的通信，边的权值表示两台虚拟机通信的流量大小；
（2）若根据对租户请求资源拓扑的分析以及问题本身的难易程度，无法实现最优部署，则执行基于图论的启发式部署策略；
（3-1）对所有的租户请求按照请求的虚拟机数量作降序排列形成待部署的请求队列Q ，定义i表示迭代次数，初始化i为1；
（3-2）对于Q中的第i个请求Qi，如果存在某个物理机，其剩余可用资源最佳满足Qi的虚拟机数量请求，则将Qi部署到该物理机上，转入步骤（3-7），否则，转入步骤（3-3）；
（3-3）查找请求Qi表示的带权无向图中是否存在桥，若存在，转入步骤（3-4），否则，转入步骤（3-6）；
（3-4）去掉请求Qi中找到的所有桥，原图被切割为多个子图，并按照各个子图中包含的顶点数对子图做降序排列；
（3-5）对步骤（3-4）中已排序的多个子图寻找最适合的物理机，若找到相应的物理机，则把相应子图中的虚拟机部署到该物理机上，然后转入步骤（3-7），否则，转入步骤（3-6）；
（3-6）对没有部署的请求或者分割后的请求采用最佳适应或者分治思想进行部署；
（3-7）令i= i+ 1，返回步骤（3-2），直至所有请求全部部署到物理机。
2.根据权利要求1所述的面向云数据中心网络优化的虚拟机部署方法，其特征在于， 所述步骤（3-6）中最佳适应思想部署策略包括：（3-6-1）对于某个请求或者切割后的某个子请求，首先找到该请求中未被分配且通信流量需求最大的顶点，即虚拟机；
（3-6-2）根据该请求的虚拟机数量找到剩余可用资源最佳适应的物理机；
（3-6-3）依次将该顶点和与之相邻的顶点部署到物理机上，直至该请求被完全部署或者该物理机剩余可用资源为空；
（3-6-4）若该请求中存在未被分配的虚拟机，则转入步骤（3-6-1），否则结束。
3.根据权利要求1所述的面向云数据中心网络优化的虚拟机部署方法，其特征在于，所述步骤（3-6）中分治思想部署策略包括：（3-6-1）对于某个请求或者切割后的某个子请求，首先找到该请求中未被分配且通信流量需求最大的顶点，即虚拟机；
（3-6-2）找到距离当前物理机最近且具有最大剩余可用资源的物理机；
（3-6-3）依次将该顶点和与之相邻的顶点部署到物理机上，直至该请求被完全部署或者该物理机剩余可用资源为空；
（3-6-4）若该请求中存在未被分配的虚拟机，则转入步骤（3-6-1），否则结束。
4.根据权利要求3所述的面向云数据中心网络优化的虚拟机部署方法，其特征在于，所述步骤（3-6-2）中分治思想部署策略的物理机之间距离的计算方法包括：规定处于同一个柜顶交换机下的物理机距离为1；
规定不在同一个柜顶交换机下，但是处于同一个汇聚层交换机下的物理机的距离为2；
规定不在同一个柜顶交换机下，也不在同一个汇聚层交换机下，但是处于同一个核心层交换机下的物理机之间的距离为3。
一种面向云数据中心网络优化的虚拟机部署方法
技术领域
[0001] 本发明涉及数据中心和云计算技术领域，具体涉及一种面向云数据中心网络优化的虚拟机部署方法。
背景技术
[0002] 当今云数据中心中资源分配变得越来越重要，高效的资源分配方案不仅可以为云提供者带来更多的利润，而且可以提供更加可靠的服务。云数据中心资源以虚拟机的形式分配给租户，而且随着应用的复杂化，租户对数据中心网络带宽的要求越来越高，这就使得网络带宽变成了提高服务质量的关键，尤其在当今数据中心规模不断扩大，租户请求的物理资源不断变化的情况下，避免网络拥塞显得至关重要。
[0003] 但是，基于优化目的不同，已有的虚拟机部署策略多种多样，例如以减少物理机能耗为优化目标或者是使网络通信开销最小化等。但是，这些部署方案均没有考虑到数据中心网络链路的使用情况，导致某些链路的负载过重出现网络拥塞，从而降低数据中心性能。针对数据中心网络拥塞问题，已有研究的侧重在于降低数据中心能耗，没有达到降低网络链路负载的目的，不能保证服务的可靠性。
发明内容
[0004] 本发明的主要目的在于提供一种面向云数据中心网络优化的虚拟机部署方法，其能够很大程度降低网络链路的负载，提高数据中心的可扩展性，最大程度地降低数据中心网络拥塞发生的可能性，从而克服现有技术中的不足。
[0005] 为实现上述技术效果，本发明提出的技术方案包括：
[0006] 本发明实施例提供了一种面向云数据中心网络优化的虚拟机部署方法，包括步骤：
[0007] (1)资源拓扑分析，分析的对象包括租户请求数量n以及每个请求的拓扑结构；其中请求的拓扑结构以带权无向图给出，顶点表示虚拟机，边表示虚拟机两两之间的通信，边的权值表示两台虚拟机通信的流量大小；
[0008] (2)若根据对租户请求资源拓扑的分析以及该问题本身的难易程度，无法实现最优部署，则执行基于图论的启发式部署策略；
[0009] (3)执行所述启发式部署策略，包括步骤：
[0010] (3-1)对所有的租户请求按照请求的虚拟机数量做降序排列形成待部署的请求队列Q；定义i表示迭代次数，初始化i为1；
[0011] (3-2)对Q中的第i个请求Qi，如果存在某个物理机，其剩余可用资源最佳满足Qi的虚拟机数量请求，那么将Qi部署到该物理机上，转入步骤(3-7)；否则，转入步骤(3-3)； (3-3)查找请求Qi表示的带权无向图中是否存在桥，若存在，转入步骤(3-4)；否则，转入步骤(3-6)；
[0012] (3-4)去掉请求Qi中找到的所有桥，原图被切割为多个子图，并按照各个子图中包含的顶点数对子图做降序排列；
[0013] (3-5)对步骤(3-4)中已排序的多个子图寻找最适合的物理机，若找到相应的物理机，则把相应子图中的虚拟机部署到该物理机上，然后转入步骤(3-7)；否则，转入步骤 (3-6)；
[0014] (3-6)对没有部署的请求或者分割后的请求采用最佳适应或者分治思想进行部署；
[0015] (3-7)令i＝i+1，返回步骤(3-2)，直至所有请求全部部署到物理机。
[0016] 进一步的，所述步骤(3-6)中最佳适应思想部署策略
[0017] (3-6-1)对于某个请求或者切割后的某个子请求，首先找到该请求中未被分配且通信流量需求最大的顶点(虚拟机)；
[0018] (3-6-2)根据该请求的虚拟机数量找到剩余可用资源最佳适应的物理机；
[0019] (3-6-3)依次将该顶点和与之相邻的顶点部署到物理机上，直至该请求被完全部署或者该物理机剩余可用资源为空；
[0020] (3-6-4)若该请求中存在未被分配的虚拟机，则转入步骤(3-6-1)，否则结束。
[0021] 进一步的，所述步骤(3-6)中分治思想部署策略包括：
[0022] (3-6-1)对于某个请求或者切割后的某个子请求，首先找到该请求中未被分配且通信流量需求最大的顶点(虚拟机)；
[0023] (3-6-2)找到距离当前物理机最近且具有最大剩余可用资源的物理机；
[0024] (3-6-3)依次将该顶点和与之相邻的顶点部署到物理机上，直至该请求被完全部署或者该物理机剩余可用资源为空；
[0025] (3-6-4)若该请求中存在未被分配的虚拟机，则转入步骤(3-6-1)；否则结束。
[0026] 进一步的，步骤(3-6-2)中所述分治思想部署策略的物理机之间距离的计算方法包括：规定处于同一个柜顶交换机下的物理机距离为1；
[0027] 规定不在同一个柜顶交换机下，但是处于同一个汇聚层交换机下的物理机的距离为2；规定不在同一个柜顶交换机下，也不在同一个汇聚层交换机下，但是处于同一个核心层交换机下的物理机之间的距离为3。
[0028] 与现有技术相比，本发明的有益效果至少在于：以减少数据中心网络拥塞为目标，提出了一种请求资源拓扑感知的虚拟机部署策略，可以有效降低网络拥塞发生的可能性，从而提高数据中心网络可靠性和可扩展性，此外还能够同时降低数据中心网络通信的总开销。
附图说明
[0029] 图1为本发明一典型实施例的功能架构图；
[0030] 图2为本发明一典型实施例中一种数据中心基础网络架构的示意图。
具体实施方式
[0031] 下面结合附图及实施例对本发明的技术方案作更进一步的解释说明。
[0032] 本发明实施例提供的一种面向云数据中心网络优化的虚拟机部署方法包括：(1)云租户请求资源拓扑分析，分析云用户请求的资源拓扑的特点并根据问题本身的难易程度实施一种启发式部署策略；
[0033] (2)启发式部署策略，由于该问题本身是NP难的，在不能保证部署方案最优的情况下，采用一种基于图论的部署策略。
[0034] 进一步地，请参阅图1所示为本发明一典型实施例的功能架构图。该实施例的执行过程包括；
[0035] (1)排序：对所有的租户请求按照请求的虚拟机数量做降序排列形成待部署的请求队列；
[0036] (2)划分：对无法将请求中的所有虚拟机部署到同一个物理机上的情况，采用以请求拓扑中的桥作为切割边对请求进行划分；
[0037] (3)选择：若划分后的请求仍旧无法达到将属于同一个子请求的虚拟机部署到同一个物理机上的目的时，则首先选择该请求中具有最大通信流量需求的虚拟机进行部署。
[0038] (4)部署：将选中的虚拟机部署到选中的物理机上。
[0039] 本发明实施例主要是在掌握数据中心可用剩余资源的情况下，云系统接收来自租户的一系列资源请求，然后根据资源拓扑以及剩余可用资源状况，产生一种基于图论的启发式的虚拟机部署策略。
[0040] 初始情况下，已知系统参数如下：
[0041] N：数据中心的物理机数量，一般应为同构的物理机；
[0042] c：每台物理机可以容纳的虚拟机的数量；
[0043] b(s,t)：物理链路s，t之间的带宽，其中s，t表示物理机或者路由器。
[0044] 在明确上述3个系统参数的基础上，云系统接收用户提交的一系列资源请求，请求资源拓扑以带权无向图的形式给出，顶点数量表示该请求需求的虚拟机数量，各边权值表示虚拟机之间通信的流量大小。
[0045] 在接收完所有请求之后，跳转到启发式部署：
[0046] 启发式部署：
[0047] (1)对所有的租户请求按照请求的虚拟机数量做降序排列形成待部署的请求队列Q；定义i表示迭代次数，初始化i为1；
[0048] (2)对Q中的第i个请求Qi，如果存在某个物理机，其剩余可用资源最佳满足Qi的虚拟机数量请求，那么将Qi部署到该物理机上，转入步骤(7)；否则，转入步骤(3)；
[0049] (3)查找请求Qi表示的带权无向图中是否存在桥，若存在，转入步骤(4)；否则，转入步骤(6)；
[0050] (4)去掉请求Qi中找到的所有桥，原图被切割为多个子图，并按照各个子图中包含的顶点数对子图做降序排列；
[0051] (5)对(4)中已排序的多个子图寻找最适合的物理机，若找到相应的物理机，则把相应子图中的虚拟机部署到该物理机上，然后转入步骤(7)；否则，转入步骤(6)；
[0052] (6)对没有部署的请求或者分割后的请求采用最佳适应或者分治思想进行部署。
[0053] (7)令i＝i+1，返回(2)，直至所有请求全部部署到物理机。
[0054] 其中，所述步骤(6)中最佳适应思想部署策略或分时思想部署策略为：
[0055] a.最佳适应思想部署策略为：
[0056] (6-1)对于某个请求或者切割后的某个子请求，首先找到该请求中未被分配且通信流量需求最大的顶点(虚拟机)；
[0057] (6-2)根据该请求的虚拟机数量找到剩余可用资源最佳适应的物理机；
[0058] (6-3)依次将该顶点和与之相邻的顶点部署到物理机上，直至该请求被完全部署或者该物理机剩余可用资源为空；
[0059] (6-4)若该请求中存在未被分配的虚拟机，则转入(6-1)；否则结束。
[0060] b.分治思想部署策略为：
[0061] (6-1)对于某个请求或者切割后的某个子请求，首先找到该请求中未被分配且通信流量需求最大的顶点(虚拟机)；
[0062] (6-2)找到距离当前物理机最近且具有最大剩余可用资源的物理机；
[0063] (6-3)依次将该顶点和与之相邻的顶点部署到物理机上，直至该请求被完全部署或者该物理机剩余可用资源为空；
[0064] (6-4)若该请求中存在未被分配的虚拟机，则转入(6-1)；否则结束。
[0065] 进一步的，所述分治思想部署策略步骤(6-2)中分治思想部署策略的物理机之间距离的计算方法为：
[0066] 规定处于同一个柜顶交换机下的物理机距离为1；
[0067] 不在同一个柜顶交换机下，但是处于同一个汇聚层交换机下的物理机的距离为2；
[0068] 既 不在同一个柜顶交换机下，也不在同一个汇聚层交换机下，但是处于同一个核心层交换机下的物理机之间的距离为3。
[0069] 藉由本发明，可以实现在最小化云数据中心网络链路的最大利用率，并以最大程度地来减少网络拥塞发生的可能性。
[0070] 应当理解，以上所述仅是本发明的优选实施方式，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。
