随着亚马逊EC2和微软Azure等云的普遍应用，云计算已经在商业上取得了巨大的成功.用户从云数据中心(后文中将云数据中心简称为数据中心)租用CPU、内存和硬盘存储等资源[1-3]来组建自己的IT基础设施并运行应用，不仅节省了硬件投资，而且可以实现应用的快速部署.从内部实现上来看，云数据中心一般是通过将计算资源虚拟化为大量的虚拟机并租给用户，主要考虑的是计算和存储资源的配给，而没有考虑网络资源的分配和优化.这将造成用户所租用计算和存储资源使用时性能上的不稳定[4-6].因为虚拟机是通过网络连接起来的，网络资源工作不正常时(比如网络拥塞，或者由于虚拟机的连接关系导致的网络热点问题等)，虚拟机的工作性能将会受到较大的影响.因此，只考虑虚拟机资源分配的传统资源分配方式TAM(TraditionalAllocationMethod)在很大程度上影响了用户应用的性能[7].解决上述问题的主要思想就是将云数据中心的网络资源也纳入资源划分的范畴，即带宽感知的网络分配.用户不仅能租用云数据中心的虚拟机，而且也能同时指定连接这些虚拟机的网络带宽以及特定虚拟机(比如Web服务器)和因特网的连接带宽(例如将带宽要求写入SLA中).
云数据中心有责任保证用户租用的虚拟机之间以及虚拟机和因特网之间的可用带宽，进而保证用户应用的性能，也要考虑用户常有的对数据中心的资源的动态租用需求.这方面的典型研究包括Sec-ondNet[7]和Oktopus[6].SecondNet通过VDC来实现虚拟网络.将物理上处于同一个数据中心的用户租用虚拟机划分为逻辑上不同的VDC.不同的VDC拥有不同的SLA以及一些其他的独有特征.其中，SLA以v2v(VM-to-VM)为单位制定的.但是这个模型存在两个问题:第一，v2v级的SLA过于细致.对于租户，v2v理解起来比较直观，制订起来却十分复杂.因为，租户可能根本不知道自己的v2v通信拥有什么特征，同时，租用VM数量的增加也会使制定规则的数量几何式的增长.第二，对于数据中心，v2v级的分配过于精细，部署复杂，不利于自身基础网络设施架构的复用性.而Oktopus则通过VC(VirtualCluster)和VOC(VirtualOversubscribedCluster)两种相互配合的分配方式来保证租户网络通信的需求.VC提出接入带宽保证的概念，这样可以满足租户带宽资源的需求，同时，相比v2v的方式，这种方式提高了网络资源的复用率.相较于VC，VOC额外提出了过度订阅参数，进一步满足网络资源需求不多的网络应用，增加租户选择弹性，节省费用.VC和VOC都简化了租户的租用方式，提升了数据中心的基础设施复用率.但是，Oktopus对网络资源的侦测层次有限，存在分配给用户的带宽达不到SLA要求的现象，即所谓的假性成功分配现象.同时，由于过度订阅的引入，也会造成租户请求的小变化引起VOC内产生连锁反应的情况，这将限制数据中心应对租户租约动态变化的弹性.本篇文章设计提出一种更加全面的带宽感知虚拟网络分配算法.
首先，在网络资源分配方面，该算法考虑更加全面.
相比TAM、SecondNet以及Oktopus，本文算法从VM之间的通信(intra-bandwidth，网内带宽)和VM与Internet的通信(inter-bandwidth，网际带宽)两方面考虑，全面保证租户网络资源需求.其次，对租户更加友好.租户只需提出VM租用数量、网内带宽、网际带宽和弹性因子α，就可完成虚拟网络的定制.同时，为了避免Oktopus中的假性成功分配问题，本文算法加深资源的侦测层次，掌握更多的网络资源配置信息，能够实现正确地带宽分配.弹性因子α给用户提供了动态租用资源的便利性.从虚拟网络划分角度来看，各种划分算法可以从以下5个方面来评估:1)VM之间的带宽保证:指VM可以与虚拟网络内的其他VM以最大不超过网内带宽值的带宽相互通信;2)VM和因特网之间的带宽保证:指虚拟网络到数据中心外部的通信带宽保证值;3)分配友好性:指定义租户使用友好的接口，使得用户易理解，方便使用;4)分配的准确性:指保证分配结果的正确，避免出现假性分配成功的现象;5)分配的弹性:指分配过程是否能够很快伸缩来适应租户需求的变动.从表1中可以看出，在VM之间带宽保证方面，TAM最差，其它三个算法都有考虑;在VM和因特网之间带宽保证方面，TAM和本文算法可以保证，而SecondNet和Oktopus没有考虑;在分配友好性方面，本文算法和Oktopus比较好;在分配的准确性方面，Oktopus因为有假性分配问题因此不够准确，其它三种都比较准确;而在分配的弹性方面，TAM具有最好的弹性，因为它可以随意分配VM.
本文提出的虚拟网络分配算法不仅考虑VM之间的带宽保证，也考虑了VM和因特网之间的带宽保证，同时还考虑了网络资源的弹性分配.更进一步的测试表明，本文算法有较好的用户请求接受率，并保证稳定和快速的VM与因特网之间通信，准确的网络资源分配，以及较好的弹性服务性能.本文内容组织如下:第2节将对云数据中心的虚拟网络分配问题进行描述.带宽感知的虚拟网络分配算法细节将在第3节论述.第4节讨论算法效果的实验性分析.第5节对文章进行总结.
2问题描述
从上一节描述中可知，本文提出的算法旨在提供一种带宽感知的虚拟网络划分算法，达到租户在各自的虚拟网络内不受外部流量干扰的目的.本算法分配的资源分为计算资源和网络资源两部分，计算资源以VM(VM概念上构成租户需要的计算，内存和硬盘资源)的数量表示，网络资源以带宽保证的链路表示(这些链路资源由VM与VM的链路和VM与Internet的链路组成，它们共同构成一个逻辑的交换机，称之为VS，VirtualSwitch).除此之外，考虑到租户的对资源需求的动态性变化，本算法引入弹性因子α来提供冗余的备份资源，从而增加虚拟网络应对租户动态请求的灵活性.根据以上提出的条件，算法在数据中心网络中分配符合条件约束的虚拟网络.图1显示了多参数控制下虚拟网络逻辑视图.
对于虚拟网络分配问题，数据中心的VM和交换机可以看成图中的点，网络链路可以看做边，在边上存在带宽限制的情况下，虚拟网络的分配问题可以抽象为在有边限制的图上搜索指定限制条件子图的问题.这一问题已被证明是NP-hard问题[17]，因此，我们使用启发式算法来找到一个可以接受的解.分配虚拟网络时，一方面，本算法引入网内带宽(intra-bandwidth)的概念.它保证VM可以与虚拟网络内的其他VM以最大不超过网内带宽值的带宽相互通信，并且不受其他VM流量的影响，这样虚拟网络内租户VM之间的通信就可以不受干扰.因此网内带宽是VM接入虚拟网络的接入带宽保证值.它类似于限制交换机上的端口速度，这是一种有上限的服务.有了这种服务，类似于MapReduce[9]这种对网络需求较高的应用，它们的性能将会更加稳定和良好[6].另一方面，为实现虚拟网络与Internet的通信保证，在分配VM和Internet的链路时，本算法引入了网际带宽(Inter-bandwidth)的概念.它是虚拟网络到数据中心外部的通信带宽保证值.Web类应用[8]需要快速响应来自Internet的请求，如果链路上充满了其他VM通信的流量，这无疑会影响Web的服务质量[10].网际带宽的满足则能保证这种通信需求.第三方面，考虑到租户可能需要伸缩自己的虚拟网络，如果在虚拟网络附近保留一些冗余资源，那么在虚拟网络需要“伸”时就能快速分配这些冗余资源，从而快速伸缩来适应租户需求的变化.为此，算法引入了弹性因子α(α=V1/(V1+V2)，V1代表租户需求的VM数量，V2代表虚拟网络预留的VM数量).这一机制模仿内存分配的策略，通过预留冗余资源，来达到快速适应需求变化、弹性分配的目的.另外，算法分配虚拟网络时优先使用临近资源，不仅可以缩短虚拟网络内VM之间的通信时延，还可以节省本已就稀缺的上层网络资源(通信限于临近的设备间，不需要高层网络设备交换转发数据包).如上文分析，此算法提供给租户的定制接口可以抽象为一个4元组，[N，Intra-bandwidth，Inter-bandwidth，α].N是租户请求的VM数量;Intra-bandwidth是网内带宽;Inter-band-width是网际带宽;α是虚拟网络预留资源状况的描述.这一定制接口非常友好，有利于租户的理解与使用.
3虚拟网络分配算法
目前，大部分数据中心的网络设计以树形结构为主[13].为增加数据中心吞吐量，数据中心经常采用高性能设备或聚合链路.出于同样的目的，学界正试图研究出更好的网络架构，比如，fat-tree[14]，VL2[15]，BCube[16]和HULL[20].本分配算法集中解决以交换机为中心的网络拓扑结构(比如，fat-tree).此网络结构类似传统网络，如层次组织、各子层由子树构成.不同于传统的网络:它们拥有更多样的横向链路，大幅提升网络内部通信的横向带宽.本文设计的启发式算法，就以此网络结构为目标网络.该虚拟网络分配算法会响应租户请求[N，Intra-band-width，Inter-bandwidth，α]，并为其从数据中心网络中找出一个包含n(n=N/α)台可用VM的子网络，且此子网络由满足网内带宽和网际带宽保证的链路构成.分配算法分为3步.第1步，搜索当前未被租出的VM.算法会对每一个VM进行标记，标记它们是否可用.然后，以每一个交换机为起点，依次计算处于交换机下行端口的可用VM数量.形成如图2所示的一个视图.在这些交换机中寻找一个可用VM数量刚好满足n的交换机.再以这台交换机将作为下一步分配计算的出发点，完成进一步的分配.这种以交换机为中心的搜索可以尽量将租户请求的VM放置在临近的位置，缩短它们的通信距离，节约上层网络资源.同时，由于存在通过冗余链路增加网络通信吞吐量的改良措施，交换机可能重复计算下行链路中已经计算过的VM资源.但这并不会影响分配算法的工作，分配算法将在后续的工作中检查这种问题，如果存在这种由于重复VM导致的分配不足，分配算法将会回退到第一步，重新选择可用交换机进行分配.如果全网不存在可满足条件的子网，则分配失败.第2步，以网内带宽为需求，初步构建VS.直观上看，VS是数据中心网络拓扑中的一颗子树，VM正是通过这个虚拟交换机VS完成带宽保证的通信.这颗子树是在资源预留的基础上构建的.不过这种资源预留策略并不意味着一台VM与10台VM通信就需要在其出口链路上预留10*intra-band-width(网内带宽)的带宽.我们使用Hose模型[19]对链路资源预留进行了优化.回到前面的例子，由于intra-bandwidth是一种最大带宽保障策略，所以，一台VM不论与多少台VM连接通信，它最大拥有intra-bandwidth的通信能力.对于这台VM，只需要预留1*intra-bandwidth的通信带宽即可.也就是说，通信带宽的预留以网络连接带宽需求较少的一侧为准.与SecondNet需要预留10*intra-bandwidth的v2v策略相比，这种策略更加节省资源，增加了数据中心服务能力和弹性.
