计算机网络毕业论文带宽感知虚拟网络分配算法设计

1、带宽感知虚拟网络分配算法设计云数据中心需要保证用户租用的虚拟机之间以及虚拟机和因特网之间的可用带宽需求，以下是搜集的一篇探究带宽感知虚拟网络分配算法设计的论文范文，供大家阅读参考。1 引言随着亚马逊 ec2和微软 azure 等云的普遍应用，云计算已经在商业上取得了巨大的成功. 用户从云数据中心( 后文中将云数据中心简称为数据中心 ) 租用 cpu、内存和硬盘存储等资源 1-3 来组建自己的 it 基础设施并运行应用，不仅节省了硬件投资，而且可以实现应用的快速部署 . 从内部实现上来看，云数据中心一般是通过将计算资源虚拟化为大量的虚拟机并租给用户，主要考虑的是计算和存储资源的配给，而没有考虑网

2、络资源的分配和优化. 这将造成用户所租用计算和存储资源使用时性能上的不稳定4-6. 因为虚拟机是通过网络连接起来的，网络资源工作不正常时( 比如网络拥塞，或者由于虚拟机的连接关系导致的网络热点问题等) ，虚拟机的工作性能将会受到较大的影响. 因此，只考虑虚拟机资源分配的传统资源分配方式 tam(traditionalallocationmethod)在很大程度上影响了用户应用的性能 7.解决上述问题的主要思想就是将云数据中心的网络资源也纳入资源划分的范畴，即带宽感知的网络分配 . 用户不仅能租用云数据中心的虚拟机，而且也能同时指定连接这些虚拟机的网络带宽以及特定虚拟机 ( 比如 web服务器

3、) 和因特网的连接带宽 ( 例如将带宽要求写入 sla中 ).云数据中心有责任保证用户租用的虚拟机之间以及虚拟机和因特网之间的可用带宽，进而保证用户应用的性能，也要考虑用户常有的对数据中心的资源的动态租用需求. 这方面的典型研究包括 sec-ondnet7 和 oktopus6.secondnet 通过 vdc来实现虚拟网络 . 将物理上处于同一个数据中心的用户租用虚拟机划分为逻辑上不同的 vdc.不同的 vdc拥有不同的 sla以及一些其他的独有特征 . 其中， sla以 v2v(vm-to-vm) 为单位制定的 . 但是这个模型存在两个问题 : 第一， v2v 级的 sla过于细致 . 对

4、于租户， v2v 理解起来比较直观，制订起来却十分复杂. 因为，租户可能根本不知道自己的 v2v 通信拥有什么特征，同时，租用 vm数量的增加也会使制定规则的数量几何式的增长 . 第二，对于数据中心， v2v 级的分配过于精细，部署复杂，不利于自身基础网络设施架构的复用性. 而oktopus 则通过 vc(virtualcluster)和voc(virtualoversubscribedcluster)两种相互配合的分配方式来保证租户网络通信的需求.vc 提出接入带宽保证的概念，这样可以满足租户带宽资源的需求，同时，相比v2v 的方式，这种方式提高了网络资源的复用率. 相较于 vc，voc额外

5、提出了过度订阅参数，进一步满足网络资源需求不多的网络应用，增加租户选择弹性，节省费用 .vc 和 voc都简化了租户的租用方式，提升了数据中心的基础设施复用率 . 但是， oktopus 对网络资源的侦测层次有限，存在分配给用户的带宽达不到 sla要求的现象，即所谓的假性成功分配现象 . 同时，由于过度订阅的引入，也会造成租户请求的小变化引起 voc内产生连锁反应的情况，这将限制数据中心应对租户租约动态变化的弹性 . 本篇文章设计提出一种更加全面的带宽感知虚拟网络分配算法 .首先，在网络资源分配方面，该算法考虑更加全面.相比 tam、secondnet 以及 oktopus ，本文算法从 vm

6、之间的通信(intra-bandwidth ，网内带宽 ) 和 vm与 internet 的通信(inter-bandwidth ，网际带宽 ) 两方面考虑，全面保证租户网络资源需求 . 其次，对租户更加友好 . 租户只需提出 vm租用数量、网内带宽、网际带宽和弹性因子 ，就可完成虚拟网络的定制 . 同时，为了避免 oktopus 中的假性成功分配问题，本文算法加深资源的侦测层次，掌握更多的网络资源配置信息，能够实现正确地带宽分配 . 弹性因子 给用户提供了动态租用资源的便利性 . 从虚拟网络划分角度来看，各种划分算法可以从以下 5 个方面来评估 :1)vm 之间的带宽保证 : 指 vm可以与

7、虚拟网络内的其他 vm以最大不超过网内带宽值的带宽相互通信 ;2)vm 和因特网之间的带宽保证 : 指虚拟网络到数据中心外部的通信带宽保证值 ;3) 分配友好性 : 指定义租户使用友好的接口，使得用户易理解，方便使用 ;4) 分配的准确性: 指保证分配结果的正确，避免出现假性分配成功的现象 ;5) 分配的弹性 : 指分配过程是否能够很快伸缩来适应租户需求的变动 . 从表 1 中可以看出，在 vm之间带宽保证方面， tam最差，其它三个算法都有考虑 ; 在 vm和因特网之间带宽保证方面， tam和本文算法可以保证，而 secondnet 和 oktopus 没有考虑 ; 在分配友好性方面，本文算

8、法和 oktopus 比较好 ; 在分配的准确性方面， oktopus因为有假性分配问题因此不够准确，其它三种都比较准确 ; 而在分配的弹性方面， tam具有最好的弹性，因为它可以随意分配 vm.本文提出的虚拟网络分配算法不仅考虑 vm之间的带宽保证，也考虑了 vm和因特网之间的带宽保证，同时还考虑了网络资源的弹性分配 . 更进一步的测试表明，本文算法有较好的用户请求接受率，并保证稳定和快速的 vm与因特网之间通信，准确的网络资源分配，以及较好的弹性服务性能 . 本文内容组织如下 : 第 2 节将对云数据中心的虚拟网络分配问题进行描述. 带宽感知的虚拟网络分配算法细节将在第3 节论述 . 第

9、4 节讨论算法效果的实验性分析.第 5 节对文章进行总结 .2 问题描述从上一节描述中可知，本文提出的算法旨在提供一种带宽感知的虚拟网络划分算法，达到租户在各自的虚拟网络内不受外部流量干扰的目的 . 本算法分配的资源分为计算资源和网络资源两部分，计算资源以 vm(vm概念上构成租户需要的计算，内存和硬盘资源 ) 的数量表示，网络资源以带宽保证的链路表示 ( 这些链路资源由 vm与 vm的链路和 vm与 internet 的链路组成，它们共同构成一个逻辑的交换机，称之为 vs，virtualswitch). 除此之外，考虑到租户的对资源需求的动态性变化，本算法引入弹性因子 来提供冗余的备份资源，

10、从而增加虚拟网络应对租户动态请求的灵活性 . 根据以上提出的条件，算法在数据中心网络中分配符合条件约束的虚拟网络 . 图 1 显示了多参数控制下虚拟网络逻辑视图.对于虚拟网络分配问题，数据中心的 vm和交换机可以看成图中的点，网络链路可以看做边，在边上存在带宽限制的情况下，虚拟网络的分配问题可以抽象为在有边限制的图上搜索指定限制条件子图的问题 . 这一问题已被证明是 np-hard 问题 17 ，因此，我们使用启发式算法来找到一个可以接受的解 . 分配虚拟网络时，一方面，本算法引入网内带宽 (intra-bandwidth) 的概念 . 它保证vm可以与虚拟网络内的其他 vm以最大不超过网内带

11、宽值的带宽相互通信，并且不受其他 vm流量的影响，这样虚拟网络内租户 vm 之间的通信就可以不受干扰 . 因此网内带宽是 vm接入虚拟网络的接入带宽保证值 . 它类似于限制交换机上的端口速度，这是一种有上限的服务 . 有了这种服务，类似于 mapreduce9这种对网络需求较高的应用，它们的性能将会更加稳定和良好 6. 另一方面，为实现虚拟网络与 internet 的通信保证，在分配 vm和 internet 的链路时，本算法引入了网际带宽 (inter-bandwidth)的概念. 它是虚拟网络到数据中心外部的通信带宽保证值.web 类应用 8需要快速响应来自 internet的请求，如果链

12、路上充满了其他vm通信的流量，这无疑会影响web的服务质量 10.网际带宽的满足则能保证这种通信需求 . 第三方面，考虑到租户可能需要伸缩自己的虚拟网络，如果在虚拟网络附近保留一些冗余资源，那么在虚拟网络需要“伸”时就能快速分配这些冗余资源，从而快速伸缩来适应租户需求的变化 . 为此，算法引入了弹性因子 ( =v1/(v1+v2)， v1 代表租户需求的 vm数量， v2 代表虚拟网络预留的 vm数量 ). 这一机制模仿内存分配的策略，通过预留冗余资源，来达到快速适应需求变化、弹性分配的目的 . 另外，算法分配虚拟网络时优先使用临近资源，不仅可以缩短虚拟网络内 vm之间的通信时延，还可以节省本

13、已就稀缺的上层网络资源 ( 通信限于临近的设备间，不需要高层网络设备交换转发数据包 ). 如上文分析，此算法提供给租户的定制接口可以抽象为一个 4 元组， n ，intra-bandwidth ，inter-bandwidth， .n 是租户请求的vm数量 ;intra-bandwidth是网内带宽 ;inter-band-width是网际带宽 ; 是虚拟网络预留资源状况的描述 . 这一定制接口非常友好，有利于租户的理解与使用.3 虚拟网络分配算法目前，大部分数据中心的网络设计以树形结构为主13.为增加数据中心吞吐量，数据中心经常采用高性能设备或聚合链路. 出于同样的目的，学界正试图研究出更好

14、的网络架构，比如，fat-tree14，vl215 ，bcube16 和 hull20. 本分配算法集中解决以交换机为中心的网络拓扑结构( 比如， fat-tree).此网络结构类似传统网络，如层次组织、各子层由子树构成. 不同于传统的网络:它们拥有更多样的横向链路，大幅提升网络内部通信的横向带宽.本文设计的启发式算法，就以此网络结构为目标网络 . 该虚拟网络分配算法会响应租户请求 n ，intra-band-width ，inter-bandwidth ， ，并为其从数据中心网络中找出一个包含n(n=n/ ) 台可用 vm的子网络，且此子网络由满足网内带宽和网际带宽保证的链路构成 . 分配算

15、法分为 3 步 . 第 1 步，搜索当前未被租出的 vm.算法会对每一个 vm进行标记，标记它们是否可用 . 然后，以每一个交换机为起点，依次计算处于交换机下行端口的可用 vm数量 . 形成如图 2 所示的一个视图 . 在这些交换机中寻找一个可用 vm数量刚好满足 n 的交换机 . 再以这台交换机将作为下一步分配计算的出发点，完成进一步的分配 . 这种以交换机为中心的搜索可以尽量将租户请求的 vm放置在临近的位置，缩短它们的通信距离，节约上层网络资源 . 同时，由于存在通过冗余链路增加网络通信吞吐量的改良措施，交换机可能重复计算下行链路中已经计算过的 vm资源 . 但这并不会影响分配算法的工作

16、，分配算法将在后续的工作中检查这种问题，如果存在这种由于重复vm导致的分配不足，分配算法将会回退到第一步，重新选择可用交换机进行分配 . 如果全网不存在可满足条件的子网，则分配失败. 第 2 步，以网内带宽为需求，初步构建vs.直观上看， vs是数据中心网络拓扑中的一颗子树，vm正是通过这个虚拟交换机vs 完成带宽保证的通信 . 这颗子树是在资源预留的基础上构建的. 不过这种资源预留策略并不意味着一台vm与 10 台 vm通信就需要在其出口链路上预留 10*intra-band-width(网内带宽 ) 的带宽 . 我们使用 hose 模型19 对链路资源预留进行了优化 . 回到前面的例子，由

17、于 intra-bandwidth 是一种最大带宽保障策略，所以，一台 vm不论与多少台 vm连接通信，它最大拥有 intra-bandwidth 的通信能力 . 对于这台 vm，只需要预留1*intra-bandwidth的通信带宽即可 . 也就是说，通信带宽的预留以网络连接带宽需求较少的一侧为准. 与secondnet 需要预留 10*intra-bandwidth的 v2v 策略相比，这种策略更加节省资源，增加了数据中心服务能力和弹性.分配算法以第一步中获得的交换机为树根，检测每一个下行端口在带宽保证的情况下能够满足的vm数量 . 这个检测过程将在vs中的每一个交换机上逐个进行. 一个下

18、行网络连接在指定带宽保证的情况下可以满足的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 是此网络连接上

19、，最终分配给租户的带宽值 . 这种网络检查将层层向下，直到检查到网络的边缘 vm.这种全面的检查可以保证分配算法的正确性，防止出现类似 oktopus 中的分配不精确问题 . 第 3 步，检测并分配从虚拟网络到 internet 的网络通信路径 . 我们把核心交换机看成是数据中心的边缘，即 internet. 因为它是整个数据中心交换网络的顶层设备，是 vm交换网络向外的出口 . 这样就可以将虚拟网络到 internet 的通信路径寻找问题简化为搜索由第二步初步形成的vs到核心交换机的有效路径问题 . 我们可以通过枚举每层交换机的上行端口来找到从 vs到核心交换机的有效路径 . 但是在极端的情

20、况下，会出现多层查找的问题，比如四层查找问题，包括虚拟交换机、架顶交换机、聚合层交换机和核心层交换机 . 为了算法的可拓展性，我们设计了一种 3 元矩阵来存储交换机之间的连接关系，这个矩阵以交换机为横轴和纵轴的坐标，在横纵轴的焦点上存储将它们直接相连的交换机，若没有则为空 .4 实验验证本文分别从 4 个方面进行了评估 . 首先，通过租户请求的接受率来验证本文虚拟网络分配算法可以保持数据中心网络基础设施较高的复用率 . 其次，通过实例，说明了本文提出的算法可以精确分配虚拟网络，杜绝类似 oktopus 中产生的假性分配成功的现象 . 第三，测量了从核心交换机到 vm的 rtt(roundtri

21、ptime) ，验证了本算法分配的虚拟网络可以保证虚拟网络与 internet 的稳定高速的通信 . 最后，测试了在数据中心不同负载情况下，面对租户请求的动态变化，不同弹性因子 给数据中心带来的服务灵活性的提升 . 本文搭建了一个实验仿真平台 . 此平台构建了一个三层的树状拓扑，过度订阅率选用了 1/10( 这一数据与观测到的实际数据相符15).实验平台总共拥有3200 台 vm.每个机架部署5 台服务器，每台服务器拥有4 台 vm.核心层交换机连接聚合层交换机，聚合层交换机又与架顶交换机相连. 所有以上仿真都由mininet18构建 .图 4 表示了仿真平台的逻辑视图.在整个仿真中，本分配算

22、法将会与上文提到的其它分配方法进行对比 . 为了获得精确可信的结果，我们为不同的分配模型提供相同的测试用例 . 其中， vm的租户需求数量服从平均数为 49 的指数分布 ( 根据数据中心的统计结果选用 5). 租户需求的带宽同样也服从指数分布，同时，选择不同的平均带宽来完成仿真 . 首先测试算法对数据中心基础设施复用率的影响 . 数据中心批准的租户请求数量和数据中心总共收到的租户请求数量的比值即租户需求接受率 . 与 secondnet 的 v2v 策略相比，通过此接受率来说明虚拟网络带来的性能提升 . 为了使对比更加合理，保持参数一致，为两个仿真设置了相同的仿真参数，即两者为相同的一组租户请

23、求( 相同的 vm数量和带宽请求，它们来自前文提到的分布函数 ) 分配数据中心网络 . 每组实验都进行了 10 次，然后，通过取平均数来对比两者的差异 . 如图 5 所示，本文算法 -100m 表示本算法在100mbps平均网内带宽保证下的分配情况 .secondnet-100m 为 secondnet 在100mbps平均带宽保证下分配的图示 . 同样的，本文算法 -500m 和 secondnet-500m 分别表示本算法在 500mbps平均网内带宽和secondnet 在 500mbps平均带宽保证情况下的分配图示 . 横轴显示了租户的总请求数量 . 因为在带宽要求较少时，数据中心的资

24、源可以提供给更多的租户使用，因此正如图 5 所示，当租户的带宽需求较小时，两种分配算法都有较高的租户请求接受率 . 但是，不管租户的请求多或少，本算法分配虚拟网络总是高出 secondnet 接受率的 20%以上 . 同时注意到每种分配算法都在有 120 个租户请求到来时发生了较大的下降情况 . 因为租户请求的平均数为 49，而数据中心共拥有 3200 台 vm.当租户请求到达 120 时，数据中心的资源已经分配殆尽 (49*120=5880) 造成接受率严重下降 .其次，通过一个例子来说明本算法分配的准确性. 如图 6 所示，假设现在到来一个新的请求 (4 台 vm，400mbps网内带宽

25、) 但是数据中心已经分配了一个租户的请求 (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带

26、宽， 400mbps=1gbps-600mbps)，不能满足租户 2*400mbps 的带宽需求，导致假性成功分配现象发生 . 而对于本算法分配的虚拟网络，链路资源检查并不会在li2 处停止，虚拟网络会沿着下行链路检查网络资源，直到网络的边缘(vm). 因此，当检查推进到li3 ，本算法发现资源不足以满足2 台 vm的部署，因此，只暂时批准1 台 vm，接着继续寻找其他可用vm.最后，vm7、vm8和 vm9满足分配条件 ( 根据分配算法一节描述，这三台vm与 vm5连接的链路上只需要1*400mbps 带宽 ) ，本算法分配vm5、vm7、vm8和 vm9给租户 .因此，本算法资源搜索更为细

27、致，保证了分配的准确性. 第三，通过测试核心交换机到 vm的 rtt，测试了本算法分配的虚拟网络的网际通信能力 . 为了检查 vm到 internet 的通信质量，在核心交换机上连接了一台服务器来模拟 inter-net. 同样，本文使用了相同的租户请求序列检测不同的分配算法. 本文随机选择了数据中心的 10 台 vm用作 vm与 in-ternet的通信测试 . 为了更加真实的重现数据中心场景，我们通过在相同的虚拟网络内模拟vm之间稳定的交互数据流，来模拟租户 vm之间的通信，进而重现一种具有网络负载的数据中心网络环境 . 通过测量和计算从核心交换机到 vm的 rtt的平均值与方差，在图 7

28、 中展示了本算法、 tam、second-net 和 oktopus 的服务质量 .secondnet 的平均时延最短，原因是secondnet 的分配条件苛刻，数据中心基础设施复用率很低， secondnet 总处于极轻载的状态 . 相反，本文算法、 tam和 oktopus分配算法宽松一些，因此在数据中心网络中可以部署更多的租户请求，网络也相应慢一些，但很大程度上提高了数据中心的复用率 .从第一个仿真实验中可以看出，secondnet 接收租户请求条件苛刻，限制了数据中心的服务拓展能力和效益 . 而本文算法分配的虚拟网络的平均时延好于 tam和 oktopus. 因为本算法在分配租户请求时考虑了网际带宽，使