分配算法以第一步中获得的交换机为树根，检测每一个下行端口在带宽保证的情况下能够满足的VM数量.这个检测过程将在VS中的每一个交换机上逐个进行.一个下行网络连接在指定带宽保证的情况下可以满足的VM数量表示为:nr=max(M)当切当，M={m'|m'∈(0，n']，n'=min(n，m)，min(m'，n-m')*intra-bandwidth≤Bl}此下行网络连接需要保留的带宽为:Br=min(nr*intra-bandwith，(n-nr)*intra-bandwith)nr是可以部署在相应下行网络连接的VM数量.M是一个集合，它由相应网络连接可以容纳的VM的数量组成.m是此下行网络连接相连的另一侧交换机能够容纳的可用VM总数.Bl是此下行网络连接上剩余的带宽.n是虚拟网络总共要分配的VM数量.Br是此网络连接上，最终分配给租户的带宽值.这种网络检查将层层向下，直到检查到网络的边缘———VM.这种全面的检查可以保证分配算法的正确性，防止出现类似Oktopus中的分配不精确问题.第3步，检测并分配从虚拟网络到Internet的网络通信路径.我们把核心交换机看成是数据中心的边缘，即Internet.因为它是整个数据中心交换网络的顶层设备，是VM交换网络向外的出口.这样就可以将虚拟网络到Internet的通信路径寻找问题简化为搜索由第二步初步形成的VS到核心交换机的有效路径问题.我们可以通过枚举每层交换机的上行端口来找到从VS到核心交换机的有效路径.但是在极端的情况下，会出现多层查找的问题，比如四层查找问题，包括虚拟交换机、架顶交换机、聚合层交换机和核心层交换机.为了算法的可拓展性，我们设计了一种3元矩阵来存储交换机之间的连接关系，这个矩阵以交换机为横轴和纵轴的坐标，在横纵轴的焦点上存储将它们直接相连的交换机，若没有则为空.

　　4实验验证

　　本文分别从4个方面进行了评估.首先，通过租户请求的接受率来验证本文虚拟网络分配算法可以保持数据中心网络基础设施较高的复用率.其次，通过实例，说明了本文提出的算法可以精确分配虚拟网络，杜绝类似Oktopus中产生的假性分配成功的现象.第三，测量了从核心交换机到VM的RTT(RoundTripTime)，验证了本算法分配的虚拟网络可以保证虚拟网络与Internet的稳定高速的通信.最后，测试了在数据中心不同负载情况下，面对租户请求的动态变化，不同弹性因子α给数据中心带来的服务灵活性的提升.本文搭建了一个实验仿真平台.此平台构建了一个三层的树状拓扑，过度订阅率选用了1/10(这一数据与观测到的实际数据相符[15]).实验平台总共拥有3200台VM.每个机架部署5台服务器，每台服务器拥有4台VM.核心层交换机连接聚合层交换机，聚合层交换机又与架顶交换机相连.所有以上仿真都由mininet[18]构建.图4表示了仿真平台的逻辑视图.

　　在整个仿真中，本分配算法将会与上文提到的其它分配方法进行对比.为了获得精确可信的结果，我们为不同的分配模型提供相同的测试用例.其中，VM的租户需求数量服从平均数为49的指数分布(根据数据中心的统计结果选用[5]).租户需求的带宽同样也服从指数分布，同时，选择不同的平均带宽来完成仿真.首先测试算法对数据中心基础设施复用率的影响.数据中心批准的租户请求数量和数据中心总共收到的租户请求数量的比值即租户需求接受率.与SecondNet的v2v策略相比，通过此接受率来说明虚拟网络带来的性能提升.为了使对比更加合理，保持参数一致，为两个仿真设置了相同的仿真参数，即两者为相同的一组租户请求(相同的VM数量和带宽请求，它们来自前文提到的分布函数)分配数据中心网络.每组实验都进行了10次，然后，通过取平均数来对比两者的差异.如图5所示，本文算法-100M表示本算法在100Mbps平均网内带宽保证下的分配情况.SecondNet-100M为SecondNet在100Mbps平均带宽保证下分配的图示.同样的，本文算法-500M和SecondNet-500M分别表示本算法在500Mbps平均网内带宽和SecondNet在500Mbps平均带宽保证情况下的分配图示.横轴显示了租户的总请求数量.因为在带宽要求较少时，数据中心的资源可以提供给更多的租户使用，因此正如图5所示，当租户的带宽需求较小时，两种分配算法都有较高的租户请求接受率.但是，不管租户的请求多或少，本算法分配虚拟网络总是高出SecondNet接受率的20%以上.同时注意到每种分配算法都在有120个租户请求到来时发生了较大的下降情况.因为租户请求的平均数为49，而数据中心共拥有3200台VM.当租户请求到达120时，数据中心的资源已经分配殆尽(49*120=5880)造成接受率严重下降.

　　其次，通过一个例子来说明本算法分配的准确性.如图6所示，假设现在到来一个新的请求(4台VM，400Mbps网内带宽)但是数据中心已经分配了一个租户的请求(VM1，VM2，VM3，VM4，600Mbps网内带宽).由于VM5，VM6，VM7，VM8和VM9可用，并且只有以sw1为根的树状子拓扑可以容纳4台以上的租户需求，所以，Oktopus顺序检查sw1的两个下行链路带宽是否满足需求.检查发现Li2所连分支拥有两台可用VM，Li2的可用带宽1Gbps大于需求带宽2*400Mbps，另一路通过同样的检测.最终，Oktopus将VM5，VM6，VM7和VM8分配给租户.然而实际上，Li3只余留400Mbps带宽(分配给VM4600Mbps带宽，400Mbps=1Gbps-600Mbps)，不能满足租户2*400Mbps的带宽需求，导致假性成功分配现象发生.而对于本算法分配的虚拟网络，链路资源检查并不会在Li2处停止，虚拟网络会沿着下行链路检查网络资源，直到网络的边缘(VM).因此，当检查推进到Li3，本算法发现资源不足以满足2台VM的部署，因此，只暂时批准1台VM，接着继续寻找其他可用VM.最后，VM7、VM8和VM9满足分配条件(根据分配算法一节描述，这三台VM与VM5连接的链路上只需要1*400Mbps带宽)，本算法分配VM5、VM7、VM8和VM9给租户.

　　因此，本算法资源搜索更为细致，保证了分配的准确性.第三，通过测试核心交换机到VM的RTT，测试了本算法分配的虚拟网络的网际通信能力.为了检查VM到Internet的通信质量，在核心交换机上连接了一台服务器来模拟Inter-net.同样，本文使用了相同的租户请求序列检测不同的分配算法.本文随机选择了数据中心的10台VM用作VM与In-ternet的通信测试.为了更加真实的重现数据中心场景，我们通过在相同的虚拟网络内模拟VM之间稳定的交互数据流，来模拟租户VM之间的通信，进而重现一种具有网络负载的数据中心网络环境.通过测量和计算从核心交换机到VM的RTT的平均值与方差，在图7中展示了本算法、TAM、Second-Net和Oktopus的服务质量.SecondNet的平均时延最短，原因是SecondNet的分配条件苛刻，数据中心基础设施复用率很低，SecondNet总处于极轻载的状态.相反，本文算法、TAM和Oktopus分配算法宽松一些，因此在数据中心网络中可以部署更多的租户请求，网络也相应慢一些，但很大程度上提高了数据中心的复用率.

　　从第一个仿真实验中可以看出，SecondNet接收租户请求条件苛刻，限制了数据中心的服务拓展能力和效益.而本文算法分配的虚拟网络的平均时延好于TAM和Oktopus.因为本算法在分配租户请求时考虑了网际带宽，使得租户的VM可以与Internet稳定快速通信.同时，本文算法分配的虚拟网络，其网络通信的RTT方差更小，更加稳定.SecondNet稳定的原因依然是其以牺牲复用率为代价的轻载.TAM的时延方差最大，最不稳定，因为TAM在分配租户请求时忽略了租户的网络资源需求情况，导致租户的VM放置很不均匀.有些地方VM扎堆放置，有的地方相对空闲，导致有些VM通信艰难，有些VM通信状况较好.而对于Oktopus，由于假性成功分配以及对网际带宽考虑不足，一些资源不允许的情况仍旧接受租户请求，导致VM通信不畅，引起RTT不稳定.最后，测试了本算法的弹性变化能力，即分配的虚拟网络应对租户请求动态变化的性能.通过预先指定的α分配租户请求，在不同的数据中心负载情况下，测试虚拟网络应对租户需求动态变化的性能提升.不失一般性，租户的动态需求序列服从指数分布，平均数采用了租户需求数的一半.在不同的α情况下，检测了租户动态请求的接受率，如图8所示.

　　结果表明，在弹性因子α=0.8的情况下，无论平均带宽需求为100Mbps或500Mbps，本算法分配的虚拟网络可以在不修改任何已有配置的情况下满足30%的租户请求.在α=0.6的情况下，租户接受率可以提升到60%.当α=0.4时，接受率接近于80%.因而，虚拟网络可以通过不同的α提供不同级别的应对需求动态变化的服务.同时对于不同的应用场景，α应有不同的适用范围.对于Web类应用，由于服务易变性较大，应设置较小的α来满足这种动态特性.如Web服务器在人们的休闲时间工作频繁，而在午夜以后服务极少.而对于类似数据分析的批量作业，租户请求的动态变化可能性较小，α可以设置较大.

　　5总结

　　保持云数据中心服务的简易性和弹性是数据中心的要义，然而数据中心网络应用服务的不稳定限制了它的发展与使用.本文中本文设计呈现了一种考虑更多网络资源影响因素的虚拟网络分配模型，避免了一些现有研究引发的问题如提供给租户的接口过于复杂、假性分配成功等.通过带宽预留和VM备用，本算法保证了租户网络应用的性能和服务弹性，为虚拟网络部署提供了一种有效的方法.