文摘

虚拟化是一个有效的方法充分利用计算资源(如服务器。将虚拟机(vm)的大量服务器中极大地影响数据中心网络的性能(DCNs公司)。随着网络资源已成为一个主要的性能瓶颈DCNs公司,我们专注于虚拟机放置Traffic-Aware平衡均匀利用DCNs公司中的链接。在本文中,我们首先提出了一个虚拟机放置问题Traffic-Aware平衡(VMPPTB),然后证明它是np难度和设计基于处理时间最长的放置算法(LPTBP算法)来解决这个问题。利用交流地点,我们提出位置感知的虚拟机放置问题Traffic-Aware平衡(LVMPPTB),这是一个多目标优化问题的同时尽量减少请求的最大数量的虚拟机分区和最小化对上行链路的最大带宽占用的机架(ToR)开关。我们也证明了它是np困难,设计了一个启发式算法(基于负载水平最低的第一位置算法,LLBP算法)来解决这个问题。通过大量的仿真,验证了提出的启发式算法显著平衡对上行链路的带宽占用ToR开关,每个请求的同时保持虚拟机分区的数量足够小。

1。介绍

随着虚拟化技术(1]成为主流方法多元各种物理资源在现代云数据中心,有效和高效的虚拟机(vm)成为一个重要的问题。VMware等机制能力计划(2和Novell PlateSpin侦察3]巩固vm,这样消耗的CPU、内存和权力进行了优化。由于增加部署本应用MapReduce (4),数据中心网络(宽带)正在成为应用程序性能和可伸缩性的瓶颈。因此,这些机制没有考虑网络资源在云数据中心并不可行。

三层树状架构是普遍地用于现代数据中心(5),如图1。这种架构,然而,本质上存在可伸缩性问题因为链接连接到核心层交换机通常从低层传输更多的流量。物理机器(PMs)连接到同一个机架的顶部(ToR)开关可以在完整的线路速度,沟通和项目经理之间的交通连接到不同ToR开关必须遍历链接的核心层,这通常是数据中心网络的瓶颈(DCNs公司)。在这篇文章中,我们将vm在经前综合症有效地平衡流量的核心层DCNs公司减少对上行链路的最大带宽占用架的顶部(ToR)开关。

可伸缩性的问题DCNs公司最近吸引了学术界的极大关注。最近的一些工作解决这个问题通过设计新的宽带架构,针对网络对分带宽最大化(6- - - - - -8)和降低宽带的整体超额认购比例。其他文件(9- - - - - -11)解决这个问题通过优化虚拟机安置在经前综合症不同的优化目标。对分带宽可以提高;然而,在核心层的可用带宽不能充分的利用。核心层的高度利用链接的数量不超过25% (12),这意味着大量的链接核心层中未得到充分利用。我们提出的虚拟机放置Traffic-Aware平衡可以均匀流量分散到链接的核心层利用高对分带宽。因为核心/聚合层的链路利用率高于ToR层和核心环节的一个重要部分作为热点持续出现(12,13),我们只考虑交通DCNs公司的核心层,和虚拟机之间的流量相同的请求下ToR开关不造成任何交通对核心层。

我们正式定义的虚拟机放置问题交通平衡(VMPPTB)作为一个优化问题,最大限度地减少对上行链路的最大带宽占用的每个ToR开关。我们证明了它的np困难减少的多处理器调度问题(14),设计一个基于处理时间最长放置算法(LPTBP算法)来解决这个问题。VMPPTB LPTBP算法提供了一个最优解问题;然而,生成的位置模式趋于均匀的地方vm下的每个请求每个ToR开关。的事实,VM租户的请求只有与其他虚拟机在同一通信请求(通信位置属性),我们应该减少虚拟机分区的数量的每个请求在同一时间(即。,将虚拟机相同的请求在尽可能少的经前综合症)。我们进一步提出交通平衡位置感知的虚拟机放置问题(LVMPPTB),旨在减少虚拟机分区的最大数量的每个请求和上行链路的最大带宽占用ToR同时开关。我们也证明它从VMPPTB np难度降低,设计了一种基于负载水平最低的第一位置算法(LLBP算法)来解决这个问题。

我们的贡献总结如下:(我)我们正式表述的虚拟机放置问题交通平衡(VMPPTB),证明其计算的复杂性,设计了一种基于处理时间最长放置算法(LPTBP算法)。(2)利用通信位置属性,我们进一步提出了交通平衡位置感知的虚拟机放置问题(LVMPPTB),证明其np困难,设计了一种基于负载水平最低的第一位置算法(LLBP算法)。(3)我们设计了一个基于贪婪的放置算法(算法)英镑作为基线,并把LPTBP算法最优解。我们评估的性能LLBP通过广泛的模拟,而英镑算法和LPTBP算法。

本文的其余部分组织如下。我们在部分简要介绍相关工作2。问题证明是节中给出的公式和计算复杂性3。节4我们描述LPTBP LLBP算法。我们评估算法部分5。最后,我们在部分结论6。

2。相关工作

在[9),作者解决网络可伸缩性问题通过使用traffic-aware虚拟机(VM)位置。他们安置问题定义为一个优化问题的沟通成本降到最低VM,通信成本被定义为每一对VM之间的跳。他们认为,虚拟机之间的流量矩阵是已知的。生成的布置方案可以减少虚拟机之间的通信距离与大流量和减少聚合流量进入更高层次的数据中心网络架构(宽带)。

在[10),作者提出了联合优化虚拟机位置和路由选择。他们努力最小化平均拥塞率DCNs公司的每一个环节。他们的放置策略执行更好的多样性与丰富的连通性和拓扑路径。虽然平均拥塞率最小化,DCNs公司可能不是显著的交通平衡。流量矩阵也认为是提前知道。

在[11),作者提出了一个Min-Cut Ratio-Aware VM (MCRVMP)位置的问题。他们试图减少需求和能力的最大比率在所有削减网络,减少在哪里定义为一组链接,东道主分割成两个不相交的连接组件,能力是能力的链接,和总需求流量的主机。通过这种方式,每个网络减少可能闲置产能吸收出乎意料的交通。这项工作仅仅是用于中型数据中心、和交通利率预先假定为已知。

提前了解流量矩阵是一个很强的假设。在[15),作者提出了采用产品交通模式模型描述交通vm之间,交通率被定义为活动水平两个虚拟机交流的产物。类似的目的(9),他们倾向于更活跃的vm到物理机器(PMs)减少沟通成本。该产品交通模式在某种程度上是不现实的。生成的方案可能导致热点位置,与更高的活动水平放置在vm主机连接到相同的开关;的上行链路切换可能成为热点。

在[16),作者制定位置的问题作为一个优化问题造成的总成本最小化网络流量和利用经前综合症。当经前综合症的数量是固定的,作者提出了三种不同的交通成本函数来解决优化问题。数据中心拓扑中,然而,不考虑在设计交通成本函数。

3所示。问题公式化

在本节中,我们定义了虚拟机放置问题基于树状架构如fat-tree [6]和VL2 [7]。数据中心通常利用三层树状结构,物理机器(PMs)直接与机架的顶部(ToR)开关,ToR与聚合交换机,交换机连接和聚合交换机进一步与核心交换机。树状拓扑结构,然而,往往是超额认购,因为一个更高级别的链接必须携带从低水平的几个链接。作为更高层次链接通常瓶颈和热点12),我们探索平衡交通联系的数据中心网络的核心层(DCNs公司)。

在虚拟机放置问题,虚拟机之间的交通连接到同一个ToR开关不转移核心开关层DCNs公司。我们只需要考虑交通ToR交换机的上行链路,因为交通可以动态地聚合层和核心层之间的负载平衡使用负载平衡机制像勇敢的负载平衡6]。妥善放置虚拟机的多个请求,我们可以更好的均匀,有效利用每一个环节的核心层DCNs公司,从而减少对上行链路的最大带宽占用ToR开关。

3.1。VMPPTB问题

我们定义的虚拟机放置问题场景,宽带ToR开关,表示为一组。对于每个ToR开关,我们可以虚拟机在一个点连接。让的上行th ToR开关,让被累积在上行带宽占用。假设有请求从不同的租户在云数据中心,和相应的请求数量的VM。如果,请求的vm可以放置在相同的ToR开关,当,请求的vm必须划分为几个经前综合症。VM的带宽要求的请求表示为。如果虚拟机被放置在ToR开关吗,它将贡献在上行带宽占用。我们应该适当的把所有的vm下的请求ToR开关最小化最大上行链路的带宽占用ToR开关与约束,每个虚拟机应放置在某些ToR开关和虚拟机放置在一个ToR开关的数量应不超过。

让是一个二进制的指标是否VM的请求被放置在托。考虑

本文的描述中使用的符号的符号进行了总结。

我们正式定义的虚拟机放置问题交通平衡(VMPPTB)如下:

目标函数(2)最小化最大带宽占用ToR交换机的上行链路。约束(3)确保每个VM的请求被放置在某些ToR开关。约束(4)保证虚拟机的数量在每个ToR开关是不超过一个点的能力。约束(5)更新上行带宽占用当我们把一个VM下ToR开关。

我们证明VMPPTB是np难问题。

定理1。的虚拟机放置问题交通平衡(VMPPTB)上面定义,找到它的最优解是赋权。

证明。这可以证明减少的多处理器调度问题(MSP)。给定一组独立的工作和大量的处理器考虑到工作长度,什么是安排所有工作所需的最短时间在处理器,这样没有重叠?MSP是一个np难问题[14]。
例如,我们组作为一些租户的请求,工作作为的请求,长度的工作随着带宽的要求的的请求,处理器是ToR开关。原来VMPPTB的实例,除了vm置于ToR开关的数量是有限的在VMPPTB。然而,我们可以设置非常大的约束在任何位置模式。通过这种方式,可以减少MSP VMPPTB。因此,我们证明VMPPTB是np难问题。

因为我们有证明VMPPTB是从MSP np难度降低,我们可以解决VMPPTB解决MSP近似算法设计。一个简单但经典算法称为处理时间最长(LPT)算法可以实现的一个上界(17]。它是可行的设计基于处理时间最长的位置(LPTBP)算法来解决VMPPTB。我们第一次在nonincreasing vm的所有请求的带宽需求订单。然后我们地方VM下的最大带宽要求ToR开关,上行的最小带宽占用。我们重复这个过程,直到vm的所有请求都放在经前综合症。

3.2。LVMPPTB问题

LPTBP算法可以生成一个近似最优解VMPPTB;然而,它不能把请求的通信位置vm考虑(例如vm的请求只有与其他虚拟机在同一通信请求)。因此,如果请求的所有虚拟机放置在尽可能少的ToR开关,本质上它可以减少交通的核心层,进一步减轻核心层的热点地区。

让是的一个子集,其中包含的ToR开关vm的请求放置。表示虚拟机分区的数量的请求应该最小化,有效地利用通信位置属性。名为位置感知的虚拟机放置问题的多目标优化问题与交通平衡(LVMPPTB)的目标是最小化最大上行链路的带宽占用ToR开关和减少虚拟机分区的所有请求的最大数量的同时,也就是正式定义如下:

我们也证明LVMPPTB是np难问题。

定理2。Locaility-Aware虚拟机放置问题交通平衡(LVMPPTB),发现它的最优解是np困难。

证明。因为我们证明,VMPPTB是np难问题,我们可以证明从VMPPTB LVMPPTB np困难减少它。LVMPPTB的一个特殊的实例是在宽带只有一个请求。因此,这个请求的虚拟机分区的数量等于该请求的虚拟机数量除以最大数量的虚拟机放置在ToR开关。结果与VMPPTB是一样的。VMPPTB如果我们可以找到一个最佳的解决方案,我们也可以找到一个最佳的解决方案,这种特殊的实例LVMPPTB,反之亦然。随着VMPPTB赋权,LVMPPTB np困难证明。

4所示。算法

我们已经证明,虚拟机放置问题交通平衡(VMPPTB)是一个np难问题。随着VMPPTB减少的多处理器调度问题,我们设计了一个基于处理时间最长放置(LPTBP)算法来解决VMPPTB,如算法所示1。

LPTBP算法旨在实现均衡的上行链路的带宽占用ToR交换机通过将VM与最大带宽需求下ToR开关每次最小带宽占用。首先,被放入一个二维数组。和最初是。VM的最大带宽要求,LPTBP算法选择ToR开关用最小带宽占用VM下的地方,然后更新,,。LPTBP算法重复这个过程,直到没有vm可以放置在任何ToR开关和输出一个虚拟机安置模式。

尽管LPTBP算法近似比(17),输出位置模式不利用通信位置属性。因此,我们首先提出一个启发式算法命名为受载荷基于位置(LLBP)来解决流量平衡的位置感知的虚拟机放置问题(LVMPPTB)所示的算法2。

LLBP算法将请求nonincreasing订单的数量的vm。对于每个请求,LLBP试图找到一个最小值空ToR开关设置,可以容纳所有的虚拟机。ToR开关(es)在一个空的ToR开关集(是)完全可用和连接到vm。如果空ToR开关设定存在,LLBP地方nonincreasing订单中的所有请求的VM下的带宽要求空ToR开关设置在第一受载荷方式(将VM最大带宽需求ToR开关下最小带宽占用)。如果没有这样的空ToR开关设置存在一个请求,LLBP试图找到一个最小ToR开关也将举行vm和ToR下的vm开关设置在第一种方法负载水平最低。

LLBP第一个地方vm请求的最大数量的虚拟机,和一个空ToR开关设置的存在是为了满足通信位置属性,和虚拟机分区的数量将会很小。LLBP重复这个过程,直到没有这样的空ToR开关组的存在。在这个时候,对于这些较小的请求数量的VM, LLBP试图找到一些ToR开关集持有他们的VM,放置在几个ToR开关,和虚拟机分区的数量将会上升。请求的最坏情况是,每个虚拟机放置在一个ToR开关,通信的局部性特性很难满足。然而,随着虚拟机的数量小,虚拟机分区的数量会更小,这些虚拟机之间的通信的开销更小。所有请求的虚拟机放置在一个受载荷方法,和对上行链路的带宽占用ToR开关可以平衡。因此,LLBP达到一个更好的权衡之间的虚拟机分区的数量的请求和上行链路的带宽占用ToR开关。

我们也设计一个基于贪婪的位置(英镑)算法,算法中所示3。英镑算法地方VM下的所有请求顺序ToR开关ToR开关顺序,这意味着每个VM的请求放置尽可能相同的其他虚拟机请求。

我们说明了三种算法的一个例子,如图2。有三个请求,,,置于5 ToR开关,,,,,。ToR开关可以连接3个vm。vm的数字3请求4、5和6。虚拟机的设置的带宽需求的请求,,,分别。三种算法的结果如图2(一)-2(c)的输出位置模式LTPBP算法达到最好的平衡在上行链路的带宽占用ToR开关(775825)。然而,虚拟机分区的请求的数量都超过3。的输出位置模式LLFBP算法实现带宽占用(650之间的权衡1100)和地点(虚拟机分区的请求的数量都小于2)。尽管英镑算法保证了位置(虚拟机分区的数量都小于2),这是最严重的一次平衡带宽占用(3751500年),显著不同。让的比率最大带宽占用超过最小带宽占用。如图2,是,是关于,是关于。我们最初设置作为一个默认的无穷。如果我们将一个值,输出位置模式可能被改变。如果VM在LPTBP,输出位置模式没有改变。当,需要更多的ToR开关。如果在LLBP,新的输出VM模式如图位置2(d),互换的VM的模式的虚拟机。虽然有更多的虚拟机分区,上行链路的带宽占用更多的平衡。

5。评价

在本节中,我们提出了启发式算法的性能进行评估(基于负载水平最低的第一个位置,LLBP算法)广泛的模拟与不同的设置。我们实现一个基于贪婪的位置(英镑)算法,使其预期的基线算法的性能。处理时间最长的基于位置(LPTBP)算法可以作为最优解算法的性能。我们比较LLBP启发式算法的性能对英镑和LPTBP算法。我们目前的仿真设置和显示评价结果和相应的分析。

5.1。仿真设置

在我们的模拟中,我们设置了五个参数如下:ToR开关的数量虚拟机的数量,可以放置在每个ToR开关请求的数量每个请求的,虚拟机的数量,每个请求的vm的带宽需求。DCNs公司的规模来标示和。在模拟中,我们设置,,,。是来自之间均匀分布和。来自正态分布的意思吗和方差,在那里是来自之间均匀分布和和是来自之间均匀分布和。由其他参数决定。我们假设所有可用的虚拟机槽被请求的VM。

5.2。仿真结果

我们运行算法,英镑LPTBP算法,LLBP启发式算法在相同的随机生成的数据集在每个规模100发的宽带。我们记录的最小带宽占用和最大上行链路的带宽占用的所有ToR开关每一轮平均值如图3。很明显,英镑算法的性能最差,LPTBP算法是最好的,在中间LLBP算法。根据仿真结果,大于,几乎是,是关于。值接近的例子的结果部分4。

尽管英镑算法的地方尽可能多虚拟机相同的请求在同样ToR开关,充分利用通信位置属性,对上行链路的带宽占用所有的ToR开关显著不同。LPTBP算法可以vm的流量均匀分散到所有的ToR交换机的上行链路;然而,它分配请求的vm下几个ToR开关。提出LLBP算法同时平衡对上行链路的带宽占用所有的ToR开关和利用通信位置属性。从仿真结果和分析,我们可以得出结论,LLBP算法执行有效的不同尺度下DCNs公司。

6。进一步优化

6.1。位置

数据中心网络的拓扑结构的分类(DCNs公司)属于switch-centric,服务器为中心,和其他的拓扑结构,根据其结构特点。Switch-centric拓扑由树状(6,7,18,19,平20.),和光学拓扑(21,22]。服务器为中心的拓扑分为拓扑用于大型数据中心(23,24]和模块化数据中心(mdc) [25,26]。其他拓扑结构包括非结构化(27,28和无线网络拓扑29日,30.]。DCNs公司的位置可以被定义为不同的级别。例如,在fat-tree [6)在图4逻辑上,我们可以分类位置为ToR级别(和),pod级别(和),和树级别(和)。位置是不同的,如服务器级别、齿条水平,和行级。我们可以为不同位置的优化级别设置不同的值。

6.2。不同的优化目标

节3,我们提出位置感知的虚拟机放置问题Traffic-Aware平衡(LVMPPTB),这是一个多目标优化问题的同时尽量减少请求的最大数量的虚拟机分区和最小化对上行链路的最大带宽占用ToR开关。我们还可以优化一个目标,而另一个目标是固定的。例如,我们可以限制的最大带宽的上行ToR切换到一个固定值来优化虚拟机分区的请求的数量。

6.3。在线平衡

虚拟机放置问题的场景发生在运行应用程序,从一开始,由离线处理算法。一旦应用程序正在运行的虚拟机,各种问题可能发生在不同的时间,而我们应该使用一个在线算法执行虚拟机迁移的负载平衡和容错。我们也可以考虑几个虚拟机之间的相关性来优化虚拟机迁移(31日]。

6.4。容错

LPTBP LLBP,我们假设所有请求租户的正常运行。如果请求迷路的事件发生时,我们需要设计一个容错机制来检索请求的损失。超时重传可能是一个解决问题的方法。

7所示。结论

在本文中,我们制定虚拟机放置问题交通平衡(VMPPTB)平衡交通数据中心。我们证明基于np困难,设计了一个处理时间最长放置算法。利用通信位置属性,我们提出交通平衡位置感知的虚拟机放置问题(LVMPPTB),同时最小化虚拟机分区的每个请求的最大数量,最大限度地减少对上行链路的最大带宽占用的职权范围。我们证明了自己的np困难,设计了一个基于负载水平最低的第一位置的启发式算法。我们进行了广泛的模拟来评估算法的性能。

符号

:	ToR交换机的设置
:	最大数量的vm下ToR开关
:	数量的vm下ToR开关
:	上行ToR开关
:	累积在上行带宽占用
:	上行带宽容量的上限
:	来自租户的请求
:	每个请求的请求的虚拟机数量
:	带宽需求的虚拟机的请求
:	指标是否VM的请求正在
:	组ToR开关与vm的请求。

信息披露

意见,调查结果、结论和建议表达本文的作者和不一定反映资助机构或政府的观点。

相互竞争的利益

作者宣称没有利益冲突。

确认

这项工作一直在支持部分由中国973项目(2014 cb340303),中国国家科学基金会项目(61472252和61472252号),重点实验室开放项目的信息网络安全的公安部第三研究所(公安部)(批准号C15602),百度的开放项目(批准号181515 p005267)和上海重点实验室开放项目计划(没有数据的科学。201609060001)。作者也要感谢道梁为他贡献的早期版本。