基于拥塞规避的非均匀带宽虚拟数据中心嵌入实现方法
基于拥塞规避的非均匀带宽虚拟数据中心嵌入实现方法【
技术领域：
】[0001]本发明设及的是云计算网络领域的技术，具体是一种基于拥塞规避的非均匀带宽虚拟数据中屯、嵌入实现方法。【
背景技术：
】[0002]随着云计算的普及，数据中屯、网络(DCN)虚拟化技术引起广泛关注。虚拟机化技术使得在物理服务器中部署多个虚拟机(V^O实例成为可能，运些虚拟机通过一个共享的物理网络进行通信。当多个租户的虚拟机在共享底层数据中屯、网络产生竞争冲突时，由于网络带宽没有保障引起不可预知的通信延迟和数据丢失，最终导致租赁成本提高，底层网络提供商的收益下降。可预测的网络性能可W通过向租户提供一个虚拟数据中屯、(VDC)来实现。Ballani等人在"Towardspredictabledatacenternetworks，"（ACMSIGCOMMComputerCommunicationReview,vol.41，no.4，pp.242-2532011)中提出了一种基于Hose模型提出了VDC请求的抽象描述。在化se模型中，虚拟数据中屯、是一个N台完全同构的虚拟机的集合，它们通过虚拟链路进行通信。[0003]R.Matthias等人在"Beyondthestars:Revisitingvirtualclusterembeddings，"（ACMSIGCOMMComputerCommunicationReview，vol.45，no.3，pp.12-18，2015.)中则提出：资源可能被执行星形拓扑嵌入所浪费，为此基于可分支化se路由提出HVC-ACE启发算法，但只适用于均匀带宽请求。[0004]即使已经确定虚拟机的放置位置，基于化se模型描述的多路径路由分配是非常困难的，运类似于虚拟专用网络（VPN)下的多路径路由分配。Kodia1am等人"Maximum-throughputroutingoftrafficinthehosemodel."(U.S.PatentNo.7,558，209.7Jul.2009.中）通过应用线性规划的对偶原理解决VPN中类似的问题。[0005]经过对现有技术的检索发现，中国专利文献号CN105072049A，公开（公告）日2015.11.18,公开了一种面向数据中屯、多层次弹性应用的资源分配方法及装置，属于多层次云应用
技术领域：
。该技术方法首先获取用户提出的多层次应用请求;其次对各层的带宽需求进行降序排列；接下来按照各层的带宽需求从高到低的顺序为各层分配虚拟机资源，具体如下:首先对该层请求需要的虚拟机数量根据当前云平台下的树形拓扑结构计算所有分配方案的可行向量FV1，其次，通过递归方法获取每条链路对该层的最优分配方案;接下来计算"按需运行"虚拟资源的数量，并在数据中屯、中进行预留；最后输出该用户多层次应用请求的最优分配方案。但该技术只能求解树形物理数据中屯、网络的资源分配问题，无法解决一般拓扑数据中屯、的VDC嵌入问题。树形拓扑两台服务器之间只存在唯一路径，路由问题非常简单；而目前典型数据中屯、网络中两台服务器之间大多存在多条路径，与树形拓扑中有显著差异。[0006]中国专利文献号CN105103506A，公开(公告）日2015.11.25，公开了一种用于为云计算网络中的非均匀带宽请求分配带宽的方法和系统，其中虚拟网络包含一个或多个虚拟交换机的第一集合，所述一个或多个虚拟交换机管理托管虚拟机(v^O的一个或多个物理服务器的第二集合。方法开始于由一个虚拟交换机接收第一多个VM的请求，其中第一多个VM中的至少一个VM含有与一个或多个VM中其余VM的带宽不同的带宽。然后通过计算与虚拟交换机关联的分配范围(allocation-range，AR)的集合，确定是否接受第一多个VM的请求，其中AR集合中的每个AR表示虚拟交换机内的至少一个不连续VM分配空间，然后对于该请求分配VM。该技术设及的算法称为分配范围算法。但该技术只能求解树形物理数据中屯、网络的VDC嵌入问题，无法解决一般拓扑数据中屯、的VDC嵌入问题。【
发明内容】[0007]本发明针对现有技术存在的上述不足，提出一种基于拥塞规避的非均匀带宽虚拟数据中屯、嵌入实现方法，解决了虚拟数据中屯、(VDC)嵌入问题中的路由问题和虚拟机的放置问题，能获得比现有技术更高的VDC嵌入成功率。[000引本发明通过W下技术方案实现：[0009]本发明设及一种基于拥塞规避的非均匀带宽VDC嵌入实现方法，将VM按带宽需求W递减的顺序排序，先用首次适配捜索法将其依次放置到服务器中；当首次适配捜索法无法放置该VM时启动微扰机制，即W物理网络的最拥塞链路为祀向，捜索对此链路负载贡献最大的瓶颈服务器，优先将瓶颈服务器中所需带宽最小的VM卸载后重新进行所述排序和放置。[0010]所述的最拥塞链路，即物理网络中具有最大链路利用率的链路，该链路表示为：庚中最大链路利用率，表示夫表示物理链路，E表示物理链路集合，Ue表示物理链路e的最大负载，Ce物理链路e的剩余带宽，其具体采用线性规划最优路由方法或K-widest路径负载均衡路由方法计算得到：[00川a)当采用线性规划最优路由方法，所述的最大链路利用率μ即是求解W下线性规划的目标值：[0012]Minimizey[0013]Subjectto：[0017]链路约束，即每个链路的负载与剩余带宽之比不超过最大链路利用率：[001引[0001]其中：路由变量結的取值范围为：0</品<1，e6f，S，d69[0002]对偶变量培和始的约束为：《+始>爲，《含0，始>0，s，de9,eeE。[0019]b)当采用K-widest路径负载均衡路由方法，则首先计算线性规划得到物理链路e的最大负载，即为Ue，然后通过寻找所有I中的最大值得到最大链路利用率μ，计算最大负载Ue的线性规划具体为：[0024]其中：s和d表示服务器，Q为至少分配了一个虚拟机的服务器的集合，廢为从服务器S到服务器d通过链路e的路由分配变量，由负责均衡路由算法确定，讀，娩为线性规划的对偶变量。[0025]所述的链路负载贡献，通过拥塞系数fΣ[S]表示，其中：|Vs|是物理服务器的数量，6(π']最拥塞链路，r表示非均匀带宽VDC请求，rr=Μi，j)Ii=1，…，N;j=1，…，IVsI}为请求r的虚拟机放置组合，其中：当VMi放置在服务器j时放置变量π(i，j)=1;否则31(i，j)=〇，N为请求r的虚拟机数量），μ(πτ)为放置组合πτ所对应的最大利用率，在拥塞系数的计算过程中，考虑所有引起网络拥塞的临时放置组合，即{ΠΤIμ(πτ)〉1}。[0026]所述的首次适配捜索法，具体包括W下步骤：[0027]步骤1、从未放置的虚拟机集合X中选择带宽最大的虚拟机。当VMi被选中，将该虚拟机放置到候选集合S[i]中第一个不会导致网络拥塞的服务器，首次适配捜索会跳过禁忌表化bu[i]中服务器。[0028]步骤2、当VMi暂时放置到服务器j时，采用最大链路利用率μ衡量物理网络的拥塞程度。一旦检测到μ〉1，说明将VMi放置到服务器j会产生网络拥塞，必须撤销运一无效的放置组合，继续尝试将VMi放置到下一个服务器。[0029]步骤3、当物理网络的任何链路都没有出现堵塞，则回到步骤1继续放置下一个虚拟机，直到所有虚拟机全部成功放置[0030]所述的微扰机制，首先通过最拥塞链路?0-Γ)找到向最拥塞链路发送最多流量的瓶颈服务器I，即瓶颈服务器由I=a巧maXsEwn，')&W计算得到；接着从该服务器J中移除最低带宽的VMK，并将瓶颈服务器/的拥塞系数后[刀重置为零，即该服务器的微扰优先级降为最低。[0031]为了防止循环，本发明将服务器I添加到网撤的禁忌列表:Tab叩1，即在后续放置过程中禁止将已经卸载的虚拟机?重复分配到瓶颈服务器中I。技术效果[0032]与现有技术相比，本发明具有拥塞感知的特点，如果发现由于网络拥塞无法放置一个VM时，通过选择性的迁移一些已经分配的虚拟机，帮助释放严重拥塞链路上的流量负载。由于嵌入成功率与设施提供商的收益直接关联，本发明用嵌入成功率衡量方法的性能。仿真结果证实:拥塞规避方法的嵌入成功率非常接近指数时间的回溯方法，显著当前第1页1 2 3 高于首次 适配、相邻适配和贪婪方法等Ξ种方法。在树型物理拓扑的特例中，根据本发明的仿真结 果，拥塞规避方法的嵌入性能优于现有的分配范围方法。所提方法同样适用于均匀带宽请 求，若采用线性规划求解的最优路由，拥塞规避方法的嵌入成功率明显高于HVC-ACE方法。
【附图说明】
[0003] 图1为本发明方法示意图；
[0004] 图中：a为空闲物理链路带宽；b为第Ξ次迭代示意图；C为首次适配方法的失效激 活微扰机制;d为最终方案；
[0005] 图2为拥塞规避算法（congestion-aware)与回溯算法（backtracking)、首次适配 (first-fit)、相邻适配(next-fit)和贪婪算法（greedy)在ht-hee数据中屯、网络中的性 能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0006] 图3为拥塞规避算法与回溯算法、首次适配、相邻适配和贪婪算法在化2数据中屯、 网络中的性能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0007] 图4为拥塞规避算法与回溯算法、首次适配、相邻适配和贪婪算法在BCube数据中 屯、网络中的性能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0008] 图5为拥塞规避算法与回溯算法、首次适配、相邻适配和贪婪算法在BCube中的运 行时间比较:横坐标为虚拟机数，纵坐标为运行时间（单位:秒）；
[0009] 图6为拥塞规避算法与回溯算法、首次适配、分配范围算法(allocation-range)在 树形数据中屯、网络的性能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0010]图7为化t-化ee中拥塞规避算法与HVC-ACE算法处理均匀带宽VDC请求的性能对 比： 横坐标为虚拟机数，纵坐标为嵌入成功率；
[0011] 图8为BCube中拥塞规避算法与HVC-ACE算法处理均匀带宽VDC请求的性能对比：横 坐标为虚拟机数，纵坐标为嵌入成功率。
【具体实施方式】
[0012] 假设一个物理DCN中，V表示节点的集合(Vs表示服务器集合，V-Vs表示交换机集 合），E表示物理链路集合。I Vs I个服务器用{1，…，I Vs I}来标记，而交换机用{I Vs I+1，…，IV }标记。节点V(vev)两端的输入/输出链路的集合分别用r(v)和扩(V)来表示。假设服务器 jeVs上有W个空闲插槽容纳新的虚拟机，一个槽对应一台虚拟机。定义eEE为物理链路。 [OOU] 根据Hose模型，非均匀带宽VDC请求r可W用向量(N，Bl，B2，…，BN)抽象描述，其中： N表示虚拟机的数量，Bi，B2，· · ·，Bn分别表示N个虚拟机的带宽需求。
[0014] 定义πτ= j) 11 = 1，…，N; j = l，…，I Vs I }为请求r的虚拟机放置组合，其中： 放置变量n(i，j) = l:当虚拟机i(带宽为Bi)放置在服务器j;否则，3i(i，j)=〇。
[0015] 定义Q为至少分配了一个虚拟机的服务器的集合，显然，I QI < min( I Vs I，N)。
[0016]
[0017] 定义b(s)为服务器SEQ的接收/发送汇聚流量，可知，b(s)受限于运台服务器s上 所有虚拟机的总带宽和其他不在服务器S上所有虚拟机的总带宽如下：
[001 引
[0019] 本实施例具体步骤如下：
[0020] 步骤1、变量初始化，包括:未放置的虚拟机VM集合:X= {VMl，VM2，…VMN}; VM i的 禁忌服务器集合说細[?] ^0，?=1...化服务器的拥塞因子?Σ[3]^0,3=1···|ν8| ;迭代次数 Η^Ο；
[0021] 步骤2、若未放置的VM集合X二0，则返回嵌入成功。若已达到最大迭代次数Η= I Vs N，则返回嵌入失败。否则从X中选择带宽需求最大的虚拟机，不妨设为VM i，累加迭代次数Η 户化1。计算VM i的备用服务器集合S[i]，服务器j属于VM i的候选服务器集合S[i]的条件 为:它有空置的插槽，其入口/出口总剩余带宽不小于分配到服务器j的虚拟机和其它虚拟 机之间的通信容量。若S[i]\Tabu[i]为空集，则返回嵌入失败。
[0022] 步骤3、先用首次适配捜索法尝试将VM i放置到集合S[i]\Tabu[i]中的某个合适 的服务器中。假设将VM i实验性的置入服务器j，并计算物理网络最大链路利用率μ。若μ〉1 证明网络中存在拥塞，必须撤销运一无效的放置组合并更新服务器的拥塞因子fs[s]，继续 尝试将VM i放置到下一个服务器。若μ<1证明网络中无拥塞，确认将VM i置入服务器j:3i (1〇')^1;并将￥11从未放置集合中移除:乂^乂\{￥11}，回到步骤2继续放置下一个虚拟机。
[0023] 步骤4、若上述首次适配捜索法失效(即未能正确放置VMi)则触发W下微扰机制：
[0024] 寻找对网络拥塞贡献最大的瓶颈服务器:/，使得J = a巧maxsey尼问;将最小带宽虚 拟机(记为VM 0从瓶颈服务器I中移除，7Γ(?，/)^〇;将已卸载的VM ?重新放回到未放置集 合中了 ^ Γ U {VM化复位拥塞因子：0;并更新禁忌表：Talm阳^ Γ加 M[ri U {server/}。 然后回到步骤2继续放置下一个虚拟机。
[0025] W上放置过程计算最大链路利用率μ，需要明确路由分配。本实施例中采用线性规 划最优路由方法或者K-widest路径负载均衡路由方法计算得到，其中：线性规划最优路由 方法是在给定虚拟机放置组合条件下能最小化最大链路利用率，但流量在网络中传输具有 任意分流比，多路路径中会出现延迟差异;K-widest路径负载均衡路由方法有效地利用了 物理网络的多个路径，其中的分支路径数K是可配置的化=1时表示单路径路由），适用于对 路径延时差异敏感的应用。
[0026] 所述的线性规划最优路由方法具体是指:给定一个虚拟机放置组合ΠΤ，最佳路由 F =锭别& J € 0，e e巧获得，最优路由分配可通过求解W下所阐述的线性规划得到。为了 避免网络中的拥塞，线性规划的目标函数设置为最小化物理网络的最大链路利用率记为μ。
[0027] Minimizey [002引 Subject to:
[0029] 流量守恒约束：
[0033] 链路约束，即每个链路的负载与剩余带宽之比不超过最大链路利用率：
[0034]
[0035] 路由变量篇的取值范围为：
[0037] 对偶变量始和锭的约束为：
[0040]最大链路利用率μ即是求解线性规划的目标值。
[0041 ] 所述的K-widest路径负载均衡路由方法具体是指：首先使用J.Y.Yen在"Finding the Κ shortest loopless paths in a network."(Management Science，vol.17，no.11， pp.712-716,1971中）提出的算法，预先计算并存储每一对通信服务器的KsPT条最短路径。然 后本实施例从KsPT无环路最短路径选择K条最宽路径，即最大瓶颈带宽。将服务器S到服务器 d的K条最宽路径用
衰示，其中：s，d = l，…|Vs|，s辛d。定义Cff 为服务器s到服务器d第k条路径的瓶颈带宽，其计算公式为：
[0042]
[0043] 根据运K条路径的剩余带宽容量，本实施例把服务器之间的流量均匀地分配到K条 路径。第k条路径的分流比的计算公式为：
[0044]
[0045] 链路e上的路由分配变量的计算公式为：
[0046]
[0047] 当采用K-widest路径负载均衡路由方法时，在最坏的情况下，拥塞规避嵌入算法 时间复杂度是〇(N|Vs||E|min( |Vs|，N)3'5L)，其中L为输入比特数，|Vs|是物理服务器的数 量，N是VDC中虚拟机的数量，|E|为物理链路数。当采用线性规划最优路由方法时，拥塞规避 嵌入算法的时间复杂度为〇(N I Vs II E 13'5min( I Vs I，N)7L)，在最坏的情况下远高于负载均衡 路由。
[004引拥塞规避嵌入算法实施例具体包括：
[0049] 如图1所示的实施例在包含六个服务器的两层数据中屯、里，演示了拥塞规避嵌入 算法的执行过程。六个服务器的剩余插槽数量分别为曰1 = 〇，曰2 = 2，曰3=1，曰4 =曰日=2和曰6=1 和，空闲物理链路带宽如图1(a)所标识(单化Mbps)。待嵌入的VD村青求具有立个虚拟机，带 宽需求分别为90Mbps、70Mbps和60Mbps。
[0050] 在前两次迭代中，首 次适配捜索法首先将VM1 (90Mbps)放在服务器3中，接着将VM2 (70Mbps)放在服务器2。然而由于网络拥塞，首次适配法无法将VM3(60Mbs)放置到任何服务 器中。
[0051] 例如在第Ξ次迭代中，如果将VM2暂时放置第六个服务器，本实施例会发现第二个 交换机和第Ξ个服务器之间的物理链路发生拥塞，因为它的负载(82Mbps)超过了剩余容量 (75Mbps)，如图1(b)所示。首次适配方法的失效激活微扰机制，会把服务器3识别为瓶颈服 务器并从中移除VM1，如图1(d)所示。在接下来的两次迭代中，该算法会将VM1放置在新的主 机，即第二个服务器，然后成功地把VM3放置在第立个服务器，如图1 (d)所示。
[0化2] 性能评估：w下在Ξ种典型数据中屯、网络(包括化t-化ee、VL2和BCube)中对算法 性能进行仿真测试，同时又考虑了树形物理网络和均匀带宽VD村青求的两种特殊情况，具体 如下：
[0053] 仿真测试中Ξ种典型数据中屯、均由16台服务器组成，物理链路的速率均为IGbps。 每次仿真实验中都根据一种典型数据中屯、拓扑随机生成一个物理网路，向其分配一个随机 产生的VD村青求，其中:N个虚拟机的带宽请求遵循均匀分布。由于嵌入成功率直接关系到数 据中屯、设施提供商的收益，因此本实施例主要采用嵌入成功率衡量算法的性能。除此外本 实施例还关注算法的运行时间，因为运与算法的可行性与用户体验密切相关。
[0054] 多路径数据中屯、网络中本实施例与回溯算法、首次适配算法和相邻适配算法和贪 婪算法的性能比较：
[0055] 假设运五种算法均采用K最宽路径负载均衡路由，分支路径数Κ = 2。
[0056] 在该测试中，服务器和物理链路W概率Ρ具有满容量，服务器剩余插槽数W概率1-Ρ服从[0,4]之间的均匀分布，物理链路的剩余带宽W概率1-Ρ服从[0，1化PS]之间的均匀分 布。VDC请求的带宽Bi (j = 1，…，Ν)遵循[100Mbps，700Mbps ]之间的均匀分布。
[0057] 图2~图4显示了平均成功率随虚拟机数增多(N从2到10)的仿真结果，其中：概率P = 0.5。正如预期回溯算法的成功率最高，原因是:排除部分不会导致一个有效的解决方案 的放置组合外，回溯算法捜索所有可能的放置组合，代价是指数增长的运行时间复杂度。仿 真结果还表明，拥塞规避算法的性能非常接近回溯算法，并且比首次适配，相邻适配和贪婪 算法有显著的优势。
[005引如图5所示，比较了BCube网络下五种算法的运行时间。回溯算法的运行时间高于 其他启发式算法两个数量级W上。同时，拥塞规避算法的运行时间比首次适配和相邻适配 稍长，而比贪婪算法低。由于拥塞规避嵌入算法具有多项式时间复杂度，而回溯算法具有指 数时间复杂度，可W预期随着虚拟机数/服务器数等增多，本实施例提出的拥塞规避算法在 运行时间方面的优势会快速扩大。综上看来，拥塞规避算法为VDC嵌入问题提供了在时间复 杂度和性能之间的良好权衡的解决方案。
[0059 ]树形数据中屯、网络中本实施例与现有技术(分配范围算法)比较：
[0060]仿真采用包含20台服务器的Ξ层树形网络，其核屯、交换机连接两台汇聚交换机， 每台汇聚交换机连接到两台架顶交换机。五台服务器连接到一台架顶交换机。服务器端口 速率为IGbps，而汇聚交换机和架顶交换机之间的链路带宽是5Gbps。本实施例通过仿真比 较所提拥塞规避算法与回溯算法，首次适配和分配范围算法(allocation-range)算法的平 均嵌入成功率，如图6所示。回溯算法能获得最高的嵌入成功率，但遗憾的是它在树形拓扑 下仍然具有指数时间复杂度。拥塞规避嵌入算法的成功率非常接近回溯算法的结果，并明 显高于其他两种算法。
[0061 ] 均匀带宽VDC本实施例与HVC-算法比较：
[0062] 当均匀带宽VDC时，所有N个虚拟机带宽需求是相等的。拥塞规避算法采用线性规 划获取最优路径，优化目标为最小化网络拥塞(最大链路利用率）。图7和8分别在化t-tree 和BCube中，比较了拥塞规避嵌入与HVC-ACE嵌入算法的性能，拥塞规避算法比HVC-ACE成功 率有显著提高。
[0063] 上述具体实施可由本领域技术人员在不背离本发明原理和宗旨的前提下W不同 的方式对其进行局部调整，本发明的保护范围w权利要求书为准且不由上述具体实施所 限，在其范围内的各个实现方案均受本发明之约束。
【主权项】
1. 一种基于拥塞规避的非均匀带宽VDC嵌入实现方法，其特征在于，将VM按带宽需求以 递减的顺序排序，先用首次适配搜索法将其依次放置到服务器中；当首次适配搜索法无法 放置该VM时启动微扰机制，即以物理网络的最拥塞链路为靶向，搜索对此链路负载贡献最 大的瓶颈服务器，优先将瓶颈服务器中所需带宽最小的VM卸载后重新进行所述排序和放 置。2. 根据权利要求1所述的方法，其特征是，所述的最拥塞链路，即物理网络中具有最大 链路利用率的链路，该链路表示为：其中最大链路利用率，表示为e表示物理链路，E表示物理链路集合，ue表示物理链路e的最大负载，C e物理 链路e的剩余带宽。3. 根据权利要求1或2所述的方法，其特征是，所述的最大链路利用率，具体采用线性规 划算法或负载均衡路由算法计算得到： a) 当采用线性规划最优路由方法，所述的最大链路利用率μ即是求解以下线性规划的 目标值： Minimizeu Subject to:链路约束，即每个链路的负载与剩余带宽之比不超过最大链路利用率：其中：路由变量总的取值范围为：对偶变量砖和yj的约束为：b) 当采用负载均衡路由算法，则首先计算线性规划得到物理链路e的最大负载，即为Ue3， 然后通过寻找所有$中的最大值得到最大链路利用率y，计算最大负载Uf3的线性规划具体 为：Subject to其中：S和d表示服务器，Q为至少分配了一个虚拟机的服务器的集合，//d为从服务器S到 服务器d通过链路e的路由分配变量，由负责均衡路由算法确定，衫，y|为线性规划的对偶 变量。4. 根据权利要求1所述的方法，其特征是，所述的链路负载贡献，通过拥塞系数fz[s]表 示，其中：I Vs I是物理服务器的数 量，6叹')最拥塞链路4表示非均匀带宽￥0(：请求，1^={31(^)|1 = 1广_，1^ = 1^-，^|} 为请求r的虚拟机放置组合，其中：当VM i放置在服务器j时放置变量π(i，j) = 1;否则π(i， j)=〇，N为请求r的虚拟机数量，μ(Π〇为放置组合所对应的最大利用率，在拥塞系数的 计算过程中，考虑所有引起网络拥塞的临时放置组合，即{ ΓΤ I μ( Π〇>1}。5. 根据权利要求1所述的方法，其特征是，所述的首次适配搜索法，具体包括以下步骤： 步骤1、从未放置的虚拟机集合X中选择带宽最大的虚拟机；当VM i被选中，将该虚拟机 放置到候选集合S[i]中第一个不会导致网络拥塞的服务器，首次适配搜索会跳过禁忌表 Tabu[i]中服务器； 步骤2、当VM i暂时放置到服务器j时，采用最大链路利用率μ衡量物理网络的拥塞程 度;一旦检测到μ>1，说明将VM i放置到服务器j会产生网络拥塞，必须撤销这一无效的放置 组合，继续尝试将VM i放置到下一个服务器； 步骤3、若物理网络的任何链路都没有出现堵塞，则回到步骤1继续放置下一个虚拟机， 直到所有虚拟机全部成功放置。6. 根据权利要求1所述的方法，其特征是，所述的微扰机制，首先通过最拥塞链路&(ΙΠ 找到向最拥塞链路发送最多流量的瓶颈服务器/，即瓶颈服务器由计 算得到;接着从该服务器/中移除最低带宽的VMi，并将瓶颈服务器if的拥塞系数务[；]:重置为 零，即该服务器的微扰优先级降为最低。7. 根据权利要求6所述的方法，其特征是，为了防止循环，将服务器f添加到侧I的禁忌 列表，即在后续放置过程中禁止将已经卸载的虚拟机?重复分配到瓶颈服务器中J。
【专利摘要】一种基于拥塞规避的非均匀带宽虚拟数据中心嵌入实现方法，将VM按带宽需求以递减的顺序排序，先用首次适配搜索法将其依次放置到服务器中；当首次适配搜索法无法放置该VM时启动微扰机制，即以物理网络的最拥塞链路为靶向，搜索对此链路负载贡献最大的瓶颈服务器，优先将瓶颈服务器中所需带宽最小的VM卸载后重新进行所述排序和放置。本发明解决了虚拟数据中心(VDC)嵌入问题中的路由问题和虚拟机的放置问题，能获得比现有技术更高的VDC嵌入成功率。
【IPC分类】H04L12/803
【公开号】CN105490959
【申请号】CN201510932813
【发明人】闫芳芳, 李 东, 胡卫生
【申请人】上海交通大学
【公开日】2016年4月13日
【申请日】2015年12月15日
技术领域：
】[0001]本发明设及的是云计算网络领域的技术，具体是一种基于拥塞规避的非均匀带宽虚拟数据中屯、嵌入实现方法。【
背景技术：
】[0002]随着云计算的普及，数据中屯、网络(DCN)虚拟化技术引起广泛关注。虚拟机化技术使得在物理服务器中部署多个虚拟机(V^O实例成为可能，运些虚拟机通过一个共享的物理网络进行通信。当多个租户的虚拟机在共享底层数据中屯、网络产生竞争冲突时，由于网络带宽没有保障引起不可预知的通信延迟和数据丢失，最终导致租赁成本提高，底层网络提供商的收益下降。可预测的网络性能可W通过向租户提供一个虚拟数据中屯、(VDC)来实现。Ballani等人在"Towardspredictabledatacenternetworks，"（ACMSIGCOMMComputerCommunicationReview,vol.41，no.4，pp.242-2532011)中提出了一种基于Hose模型提出了VDC请求的抽象描述。在化se模型中，虚拟数据中屯、是一个N台完全同构的虚拟机的集合，它们通过虚拟链路进行通信。[0003]R.Matthias等人在"Beyondthestars:Revisitingvirtualclusterembeddings，"（ACMSIGCOMMComputerCommunicationReview，vol.45，no.3，pp.12-18，2015.)中则提出：资源可能被执行星形拓扑嵌入所浪费，为此基于可分支化se路由提出HVC-ACE启发算法，但只适用于均匀带宽请求。[0004]即使已经确定虚拟机的放置位置，基于化se模型描述的多路径路由分配是非常困难的，运类似于虚拟专用网络（VPN)下的多路径路由分配。Kodia1am等人"Maximum-throughputroutingoftrafficinthehosemodel."(U.S.PatentNo.7,558，209.7Jul.2009.中）通过应用线性规划的对偶原理解决VPN中类似的问题。[0005]经过对现有技术的检索发现，中国专利文献号CN105072049A，公开（公告）日2015.11.18,公开了一种面向数据中屯、多层次弹性应用的资源分配方法及装置，属于多层次云应用
技术领域：
。该技术方法首先获取用户提出的多层次应用请求;其次对各层的带宽需求进行降序排列；接下来按照各层的带宽需求从高到低的顺序为各层分配虚拟机资源，具体如下:首先对该层请求需要的虚拟机数量根据当前云平台下的树形拓扑结构计算所有分配方案的可行向量FV1，其次，通过递归方法获取每条链路对该层的最优分配方案;接下来计算"按需运行"虚拟资源的数量，并在数据中屯、中进行预留；最后输出该用户多层次应用请求的最优分配方案。但该技术只能求解树形物理数据中屯、网络的资源分配问题，无法解决一般拓扑数据中屯、的VDC嵌入问题。树形拓扑两台服务器之间只存在唯一路径，路由问题非常简单；而目前典型数据中屯、网络中两台服务器之间大多存在多条路径，与树形拓扑中有显著差异。[0006]中国专利文献号CN105103506A，公开(公告）日2015.11.25，公开了一种用于为云计算网络中的非均匀带宽请求分配带宽的方法和系统，其中虚拟网络包含一个或多个虚拟交换机的第一集合，所述一个或多个虚拟交换机管理托管虚拟机(v^O的一个或多个物理服务器的第二集合。方法开始于由一个虚拟交换机接收第一多个VM的请求，其中第一多个VM中的至少一个VM含有与一个或多个VM中其余VM的带宽不同的带宽。然后通过计算与虚拟交换机关联的分配范围(allocation-range，AR)的集合，确定是否接受第一多个VM的请求，其中AR集合中的每个AR表示虚拟交换机内的至少一个不连续VM分配空间，然后对于该请求分配VM。该技术设及的算法称为分配范围算法。但该技术只能求解树形物理数据中屯、网络的VDC嵌入问题，无法解决一般拓扑数据中屯、的VDC嵌入问题。【
发明内容】[0007]本发明针对现有技术存在的上述不足，提出一种基于拥塞规避的非均匀带宽虚拟数据中屯、嵌入实现方法，解决了虚拟数据中屯、(VDC)嵌入问题中的路由问题和虚拟机的放置问题，能获得比现有技术更高的VDC嵌入成功率。[000引本发明通过W下技术方案实现：[0009]本发明设及一种基于拥塞规避的非均匀带宽VDC嵌入实现方法，将VM按带宽需求W递减的顺序排序，先用首次适配捜索法将其依次放置到服务器中；当首次适配捜索法无法放置该VM时启动微扰机制，即W物理网络的最拥塞链路为祀向，捜索对此链路负载贡献最大的瓶颈服务器，优先将瓶颈服务器中所需带宽最小的VM卸载后重新进行所述排序和放置。[0010]所述的最拥塞链路，即物理网络中具有最大链路利用率的链路，该链路表示为：庚中最大链路利用率，表示夫表示物理链路，E表示物理链路集合，Ue表示物理链路e的最大负载，Ce物理链路e的剩余带宽，其具体采用线性规划最优路由方法或K-widest路径负载均衡路由方法计算得到：[00川a)当采用线性规划最优路由方法，所述的最大链路利用率μ即是求解W下线性规划的目标值：[0012]Minimizey[0013]Subjectto：[0017]链路约束，即每个链路的负载与剩余带宽之比不超过最大链路利用率：[001引[0001]其中：路由变量結的取值范围为：0</品<1，e6f，S，d69[0002]对偶变量培和始的约束为：《+始>爲，《含0，始>0，s，de9,eeE。[0019]b)当采用K-widest路径负载均衡路由方法，则首先计算线性规划得到物理链路e的最大负载，即为Ue，然后通过寻找所有I中的最大值得到最大链路利用率μ，计算最大负载Ue的线性规划具体为：[0024]其中：s和d表示服务器，Q为至少分配了一个虚拟机的服务器的集合，廢为从服务器S到服务器d通过链路e的路由分配变量，由负责均衡路由算法确定，讀，娩为线性规划的对偶变量。[0025]所述的链路负载贡献，通过拥塞系数fΣ[S]表示，其中：|Vs|是物理服务器的数量，6(π']最拥塞链路，r表示非均匀带宽VDC请求，rr=Μi，j)Ii=1，…，N;j=1，…，IVsI}为请求r的虚拟机放置组合，其中：当VMi放置在服务器j时放置变量π(i，j)=1;否则31(i，j)=〇，N为请求r的虚拟机数量），μ(πτ)为放置组合πτ所对应的最大利用率，在拥塞系数的计算过程中，考虑所有引起网络拥塞的临时放置组合，即{ΠΤIμ(πτ)〉1}。[0026]所述的首次适配捜索法，具体包括W下步骤：[0027]步骤1、从未放置的虚拟机集合X中选择带宽最大的虚拟机。当VMi被选中，将该虚拟机放置到候选集合S[i]中第一个不会导致网络拥塞的服务器，首次适配捜索会跳过禁忌表化bu[i]中服务器。[0028]步骤2、当VMi暂时放置到服务器j时，采用最大链路利用率μ衡量物理网络的拥塞程度。一旦检测到μ〉1，说明将VMi放置到服务器j会产生网络拥塞，必须撤销运一无效的放置组合，继续尝试将VMi放置到下一个服务器。[0029]步骤3、当物理网络的任何链路都没有出现堵塞，则回到步骤1继续放置下一个虚拟机，直到所有虚拟机全部成功放置[0030]所述的微扰机制，首先通过最拥塞链路?0-Γ)找到向最拥塞链路发送最多流量的瓶颈服务器I，即瓶颈服务器由I=a巧maXsEwn，')&W计算得到；接着从该服务器J中移除最低带宽的VMK，并将瓶颈服务器/的拥塞系数后[刀重置为零，即该服务器的微扰优先级降为最低。[0031]为了防止循环，本发明将服务器I添加到网撤的禁忌列表:Tab叩1，即在后续放置过程中禁止将已经卸载的虚拟机?重复分配到瓶颈服务器中I。技术效果[0032]与现有技术相比，本发明具有拥塞感知的特点，如果发现由于网络拥塞无法放置一个VM时，通过选择性的迁移一些已经分配的虚拟机，帮助释放严重拥塞链路上的流量负载。由于嵌入成功率与设施提供商的收益直接关联，本发明用嵌入成功率衡量方法的性能。仿真结果证实:拥塞规避方法的嵌入成功率非常接近指数时间的回溯方法，显著当前第1页1 2 3 高于首次 适配、相邻适配和贪婪方法等Ξ种方法。在树型物理拓扑的特例中，根据本发明的仿真结 果，拥塞规避方法的嵌入性能优于现有的分配范围方法。所提方法同样适用于均匀带宽请 求，若采用线性规划求解的最优路由，拥塞规避方法的嵌入成功率明显高于HVC-ACE方法。
【附图说明】
[0003] 图1为本发明方法示意图；
[0004] 图中：a为空闲物理链路带宽；b为第Ξ次迭代示意图；C为首次适配方法的失效激 活微扰机制;d为最终方案；
[0005] 图2为拥塞规避算法（congestion-aware)与回溯算法（backtracking)、首次适配 (first-fit)、相邻适配(next-fit)和贪婪算法（greedy)在ht-hee数据中屯、网络中的性 能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0006] 图3为拥塞规避算法与回溯算法、首次适配、相邻适配和贪婪算法在化2数据中屯、 网络中的性能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0007] 图4为拥塞规避算法与回溯算法、首次适配、相邻适配和贪婪算法在BCube数据中 屯、网络中的性能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0008] 图5为拥塞规避算法与回溯算法、首次适配、相邻适配和贪婪算法在BCube中的运 行时间比较:横坐标为虚拟机数，纵坐标为运行时间（单位:秒）；
[0009] 图6为拥塞规避算法与回溯算法、首次适配、分配范围算法(allocation-range)在 树形数据中屯、网络的性能比较:横坐标为虚拟机数，纵坐标为嵌入成功率；
[0010]图7为化t-化ee中拥塞规避算法与HVC-ACE算法处理均匀带宽VDC请求的性能对 比： 横坐标为虚拟机数，纵坐标为嵌入成功率；
[0011] 图8为BCube中拥塞规避算法与HVC-ACE算法处理均匀带宽VDC请求的性能对比：横 坐标为虚拟机数，纵坐标为嵌入成功率。
【具体实施方式】
[0012] 假设一个物理DCN中，V表示节点的集合(Vs表示服务器集合，V-Vs表示交换机集 合），E表示物理链路集合。I Vs I个服务器用{1，…，I Vs I}来标记，而交换机用{I Vs I+1，…，IV }标记。节点V(vev)两端的输入/输出链路的集合分别用r(v)和扩(V)来表示。假设服务器 jeVs上有W个空闲插槽容纳新的虚拟机，一个槽对应一台虚拟机。定义eEE为物理链路。 [OOU] 根据Hose模型，非均匀带宽VDC请求r可W用向量(N，Bl，B2，…，BN)抽象描述，其中： N表示虚拟机的数量，Bi，B2，· · ·，Bn分别表示N个虚拟机的带宽需求。
[0014] 定义πτ= j) 11 = 1，…，N; j = l，…，I Vs I }为请求r的虚拟机放置组合，其中： 放置变量n(i，j) = l:当虚拟机i(带宽为Bi)放置在服务器j;否则，3i(i，j)=〇。
[0015] 定义Q为至少分配了一个虚拟机的服务器的集合，显然，I QI < min( I Vs I，N)。
[0016]
[0017] 定义b(s)为服务器SEQ的接收/发送汇聚流量，可知，b(s)受限于运台服务器s上 所有虚拟机的总带宽和其他不在服务器S上所有虚拟机的总带宽如下：
[001 引
[0019] 本实施例具体步骤如下：
[0020] 步骤1、变量初始化，包括:未放置的虚拟机VM集合:X= {VMl，VM2，…VMN}; VM i的 禁忌服务器集合说細[?] ^0，?=1...化服务器的拥塞因子?Σ[3]^0,3=1···|ν8| ;迭代次数 Η^Ο；
[0021] 步骤2、若未放置的VM集合X二0，则返回嵌入成功。若已达到最大迭代次数Η= I Vs N，则返回嵌入失败。否则从X中选择带宽需求最大的虚拟机，不妨设为VM i，累加迭代次数Η 户化1。计算VM i的备用服务器集合S[i]，服务器j属于VM i的候选服务器集合S[i]的条件 为:它有空置的插槽，其入口/出口总剩余带宽不小于分配到服务器j的虚拟机和其它虚拟 机之间的通信容量。若S[i]\Tabu[i]为空集，则返回嵌入失败。
[0022] 步骤3、先用首次适配捜索法尝试将VM i放置到集合S[i]\Tabu[i]中的某个合适 的服务器中。假设将VM i实验性的置入服务器j，并计算物理网络最大链路利用率μ。若μ〉1 证明网络中存在拥塞，必须撤销运一无效的放置组合并更新服务器的拥塞因子fs[s]，继续 尝试将VM i放置到下一个服务器。若μ<1证明网络中无拥塞，确认将VM i置入服务器j:3i (1〇')^1;并将￥11从未放置集合中移除:乂^乂\{￥11}，回到步骤2继续放置下一个虚拟机。
[0023] 步骤4、若上述首次适配捜索法失效(即未能正确放置VMi)则触发W下微扰机制：
[0024] 寻找对网络拥塞贡献最大的瓶颈服务器:/，使得J = a巧maxsey尼问;将最小带宽虚 拟机(记为VM 0从瓶颈服务器I中移除，7Γ(?，/)^〇;将已卸载的VM ?重新放回到未放置集 合中了 ^ Γ U {VM化复位拥塞因子：0;并更新禁忌表：Talm阳^ Γ加 M[ri U {server/}。 然后回到步骤2继续放置下一个虚拟机。
[0025] W上放置过程计算最大链路利用率μ，需要明确路由分配。本实施例中采用线性规 划最优路由方法或者K-widest路径负载均衡路由方法计算得到，其中：线性规划最优路由 方法是在给定虚拟机放置组合条件下能最小化最大链路利用率，但流量在网络中传输具有 任意分流比，多路路径中会出现延迟差异;K-widest路径负载均衡路由方法有效地利用了 物理网络的多个路径，其中的分支路径数K是可配置的化=1时表示单路径路由），适用于对 路径延时差异敏感的应用。
[0026] 所述的线性规划最优路由方法具体是指:给定一个虚拟机放置组合ΠΤ，最佳路由 F =锭别& J € 0，e e巧获得，最优路由分配可通过求解W下所阐述的线性规划得到。为了 避免网络中的拥塞，线性规划的目标函数设置为最小化物理网络的最大链路利用率记为μ。
[0027] Minimizey [002引 Subject to:
[0029] 流量守恒约束：
[0033] 链路约束，即每个链路的负载与剩余带宽之比不超过最大链路利用率：
[0034]
[0035] 路由变量篇的取值范围为：
[0037] 对偶变量始和锭的约束为：
[0040]最大链路利用率μ即是求解线性规划的目标值。
[0041 ] 所述的K-widest路径负载均衡路由方法具体是指：首先使用J.Y.Yen在"Finding the Κ shortest loopless paths in a network."(Management Science，vol.17，no.11， pp.712-716,1971中）提出的算法，预先计算并存储每一对通信服务器的KsPT条最短路径。然 后本实施例从KsPT无环路最短路径选择K条最宽路径，即最大瓶颈带宽。将服务器S到服务器 d的K条最宽路径用
衰示，其中：s，d = l，…|Vs|，s辛d。定义Cff 为服务器s到服务器d第k条路径的瓶颈带宽，其计算公式为：
[0042]
[0043] 根据运K条路径的剩余带宽容量，本实施例把服务器之间的流量均匀地分配到K条 路径。第k条路径的分流比的计算公式为：
[0044]
[0045] 链路e上的路由分配变量的计算公式为：
[0046]
[0047] 当采用K-widest路径负载均衡路由方法时，在最坏的情况下，拥塞规避嵌入算法 时间复杂度是〇(N|Vs||E|min( |Vs|，N)3'5L)，其中L为输入比特数，|Vs|是物理服务器的数 量，N是VDC中虚拟机的数量，|E|为物理链路数。当采用线性规划最优路由方法时，拥塞规避 嵌入算法的时间复杂度为〇(N I Vs II E 13'5min( I Vs I，N)7L)，在最坏的情况下远高于负载均衡 路由。
[004引拥塞规避嵌入算法实施例具体包括：
[0049] 如图1所示的实施例在包含六个服务器的两层数据中屯、里，演示了拥塞规避嵌入 算法的执行过程。六个服务器的剩余插槽数量分别为曰1 = 〇，曰2 = 2，曰3=1，曰4 =曰日=2和曰6=1 和，空闲物理链路带宽如图1(a)所标识(单化Mbps)。待嵌入的VD村青求具有立个虚拟机，带 宽需求分别为90Mbps、70Mbps和60Mbps。
[0050] 在前两次迭代中，首 次适配捜索法首先将VM1 (90Mbps)放在服务器3中，接着将VM2 (70Mbps)放在服务器2。然而由于网络拥塞，首次适配法无法将VM3(60Mbs)放置到任何服务 器中。
[0051] 例如在第Ξ次迭代中，如果将VM2暂时放置第六个服务器，本实施例会发现第二个 交换机和第Ξ个服务器之间的物理链路发生拥塞，因为它的负载(82Mbps)超过了剩余容量 (75Mbps)，如图1(b)所示。首次适配方法的失效激活微扰机制，会把服务器3识别为瓶颈服 务器并从中移除VM1，如图1(d)所示。在接下来的两次迭代中，该算法会将VM1放置在新的主 机，即第二个服务器，然后成功地把VM3放置在第立个服务器，如图1 (d)所示。
[0化2] 性能评估：w下在Ξ种典型数据中屯、网络(包括化t-化ee、VL2和BCube)中对算法 性能进行仿真测试，同时又考虑了树形物理网络和均匀带宽VD村青求的两种特殊情况，具体 如下：
[0053] 仿真测试中Ξ种典型数据中屯、均由16台服务器组成，物理链路的速率均为IGbps。 每次仿真实验中都根据一种典型数据中屯、拓扑随机生成一个物理网路，向其分配一个随机 产生的VD村青求，其中:N个虚拟机的带宽请求遵循均匀分布。由于嵌入成功率直接关系到数 据中屯、设施提供商的收益，因此本实施例主要采用嵌入成功率衡量算法的性能。除此外本 实施例还关注算法的运行时间，因为运与算法的可行性与用户体验密切相关。
[0054] 多路径数据中屯、网络中本实施例与回溯算法、首次适配算法和相邻适配算法和贪 婪算法的性能比较：
[0055] 假设运五种算法均采用K最宽路径负载均衡路由，分支路径数Κ = 2。
[0056] 在该测试中，服务器和物理链路W概率Ρ具有满容量，服务器剩余插槽数W概率1-Ρ服从[0,4]之间的均匀分布，物理链路的剩余带宽W概率1-Ρ服从[0，1化PS]之间的均匀分 布。VDC请求的带宽Bi (j = 1，…，Ν)遵循[100Mbps，700Mbps ]之间的均匀分布。
[0057] 图2~图4显示了平均成功率随虚拟机数增多(N从2到10)的仿真结果，其中：概率P = 0.5。正如预期回溯算法的成功率最高，原因是:排除部分不会导致一个有效的解决方案 的放置组合外，回溯算法捜索所有可能的放置组合，代价是指数增长的运行时间复杂度。仿 真结果还表明，拥塞规避算法的性能非常接近回溯算法，并且比首次适配，相邻适配和贪婪 算法有显著的优势。
[005引如图5所示，比较了BCube网络下五种算法的运行时间。回溯算法的运行时间高于 其他启发式算法两个数量级W上。同时，拥塞规避算法的运行时间比首次适配和相邻适配 稍长，而比贪婪算法低。由于拥塞规避嵌入算法具有多项式时间复杂度，而回溯算法具有指 数时间复杂度，可W预期随着虚拟机数/服务器数等增多，本实施例提出的拥塞规避算法在 运行时间方面的优势会快速扩大。综上看来，拥塞规避算法为VDC嵌入问题提供了在时间复 杂度和性能之间的良好权衡的解决方案。
[0059 ]树形数据中屯、网络中本实施例与现有技术(分配范围算法)比较：
[0060]仿真采用包含20台服务器的Ξ层树形网络，其核屯、交换机连接两台汇聚交换机， 每台汇聚交换机连接到两台架顶交换机。五台服务器连接到一台架顶交换机。服务器端口 速率为IGbps，而汇聚交换机和架顶交换机之间的链路带宽是5Gbps。本实施例通过仿真比 较所提拥塞规避算法与回溯算法，首次适配和分配范围算法(allocation-range)算法的平 均嵌入成功率，如图6所示。回溯算法能获得最高的嵌入成功率，但遗憾的是它在树形拓扑 下仍然具有指数时间复杂度。拥塞规避嵌入算法的成功率非常接近回溯算法的结果，并明 显高于其他两种算法。
[0061 ] 均匀带宽VDC本实施例与HVC-算法比较：
[0062] 当均匀带宽VDC时，所有N个虚拟机带宽需求是相等的。拥塞规避算法采用线性规 划获取最优路径，优化目标为最小化网络拥塞(最大链路利用率）。图7和8分别在化t-tree 和BCube中，比较了拥塞规避嵌入与HVC-ACE嵌入算法的性能，拥塞规避算法比HVC-ACE成功 率有显著提高。
[0063] 上述具体实施可由本领域技术人员在不背离本发明原理和宗旨的前提下W不同 的方式对其进行局部调整，本发明的保护范围w权利要求书为准且不由上述具体实施所 限，在其范围内的各个实现方案均受本发明之约束。
【主权项】
1. 一种基于拥塞规避的非均匀带宽VDC嵌入实现方法，其特征在于，将VM按带宽需求以 递减的顺序排序，先用首次适配搜索法将其依次放置到服务器中；当首次适配搜索法无法 放置该VM时启动微扰机制，即以物理网络的最拥塞链路为靶向，搜索对此链路负载贡献最 大的瓶颈服务器，优先将瓶颈服务器中所需带宽最小的VM卸载后重新进行所述排序和放 置。2. 根据权利要求1所述的方法，其特征是，所述的最拥塞链路，即物理网络中具有最大 链路利用率的链路，该链路表示为：其中最大链路利用率，表示为e表示物理链路，E表示物理链路集合，ue表示物理链路e的最大负载，C e物理 链路e的剩余带宽。3. 根据权利要求1或2所述的方法，其特征是，所述的最大链路利用率，具体采用线性规 划算法或负载均衡路由算法计算得到： a) 当采用线性规划最优路由方法，所述的最大链路利用率μ即是求解以下线性规划的 目标值： Minimizeu Subject to:链路约束，即每个链路的负载与剩余带宽之比不超过最大链路利用率：其中：路由变量总的取值范围为：对偶变量砖和yj的约束为：b) 当采用负载均衡路由算法，则首先计算线性规划得到物理链路e的最大负载，即为Ue3， 然后通过寻找所有$中的最大值得到最大链路利用率y，计算最大负载Uf3的线性规划具体 为：Subject to其中：S和d表示服务器，Q为至少分配了一个虚拟机的服务器的集合，//d为从服务器S到 服务器d通过链路e的路由分配变量，由负责均衡路由算法确定，衫，y|为线性规划的对偶 变量。4. 根据权利要求1所述的方法，其特征是，所述的链路负载贡献，通过拥塞系数fz[s]表 示，其中：I Vs I是物理服务器的数 量，6叹')最拥塞链路4表示非均匀带宽￥0(：请求，1^={31(^)|1 = 1广_，1^ = 1^-，^|} 为请求r的虚拟机放置组合，其中：当VM i放置在服务器j时放置变量π(i，j) = 1;否则π(i， j)=〇，N为请求r的虚拟机数量，μ(Π〇为放置组合所对应的最大利用率，在拥塞系数的 计算过程中，考虑所有引起网络拥塞的临时放置组合，即{ ΓΤ I μ( Π〇>1}。5. 根据权利要求1所述的方法，其特征是，所述的首次适配搜索法，具体包括以下步骤： 步骤1、从未放置的虚拟机集合X中选择带宽最大的虚拟机；当VM i被选中，将该虚拟机 放置到候选集合S[i]中第一个不会导致网络拥塞的服务器，首次适配搜索会跳过禁忌表 Tabu[i]中服务器； 步骤2、当VM i暂时放置到服务器j时，采用最大链路利用率μ衡量物理网络的拥塞程 度;一旦检测到μ>1，说明将VM i放置到服务器j会产生网络拥塞，必须撤销这一无效的放置 组合，继续尝试将VM i放置到下一个服务器； 步骤3、若物理网络的任何链路都没有出现堵塞，则回到步骤1继续放置下一个虚拟机， 直到所有虚拟机全部成功放置。6. 根据权利要求1所述的方法，其特征是，所述的微扰机制，首先通过最拥塞链路&(ΙΠ 找到向最拥塞链路发送最多流量的瓶颈服务器/，即瓶颈服务器由计 算得到;接着从该服务器/中移除最低带宽的VMi，并将瓶颈服务器if的拥塞系数务[；]:重置为 零，即该服务器的微扰优先级降为最低。7. 根据权利要求6所述的方法，其特征是，为了防止循环，将服务器f添加到侧I的禁忌 列表，即在后续放置过程中禁止将已经卸载的虚拟机?重复分配到瓶颈服务器中J。
【专利摘要】一种基于拥塞规避的非均匀带宽虚拟数据中心嵌入实现方法，将VM按带宽需求以递减的顺序排序，先用首次适配搜索法将其依次放置到服务器中；当首次适配搜索法无法放置该VM时启动微扰机制，即以物理网络的最拥塞链路为靶向，搜索对此链路负载贡献最大的瓶颈服务器，优先将瓶颈服务器中所需带宽最小的VM卸载后重新进行所述排序和放置。本发明解决了虚拟数据中心(VDC)嵌入问题中的路由问题和虚拟机的放置问题，能获得比现有技术更高的VDC嵌入成功率。
【IPC分类】H04L12/803
【公开号】CN105490959
【申请号】CN201510932813
【发明人】闫芳芳, 李 东, 胡卫生
【申请人】上海交通大学
【公开日】2016年4月13日
【申请日】2015年12月15日
最新回复(0)