基于网络拓扑预优化和提高可用性的虚拟网络映射方法
基于网络拓扑预优化和提高可用性的虚拟网络映射方法
【技术领域】
[0001]本发明属于计算机通信技术领域，尤其涉及一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法。
【背景技术】
[0002]互联网的出现堪称人类文明史上的一座里程碑，它深刻地影响并改变着人们的学习、工作和生活方式。然而，随着互联网用户群体大规模的增长以及网络应用不断的推陈出新，互联网体系结构面临着新的挑战和需求。虽然传统的互联网体系结构为互联网的发展做出了巨大的贡献，但是其在可用性、可靠性、可扩展性、服务质量等多方面的问题逐渐凸显，已经不能满足对新业务的支持，因此研宄和部署全新的网络技术和结构被提上日程。虽然还未最终确定未来网络到底是一个什么样的模式，但是未来网络支持虚拟化已经被普遍
。
[0003]网络虚拟化技术是解决目前互联网硬化的有效方法:一方面，网络虚拟化技术支持多种不同架构的网络以共享方式运行于同一个公共的物理基础网络上，为不同新协议，新技术的验证提供了可能；另一方面，网络虚拟化技术的核心思想是对底层网络资源进行抽象、隔离，从而实现控制平面和数据平面的分离，这种特性正逐渐成为未来网络的关键属性。在网络虚拟化技术中，虚拟网络的高可用性问题是网络虚拟化的关键问题之一。它解决的是如何保证虚拟网及底层物理网络的可靠性和可用性，以及在网络发生故障时如何快速的进行故障恢复的问题，因此对其研宄具有重要的理论和实际意义。
[0004]网络拓扑预优化是实现网络高可用性的一种新方法，它根据故障率的大小及故障恢复时间的长短来衡量高可用。将故障率高于某一阈值的节点和链路，在进行虚拟网络映射前先从底层网络拓扑中去除，以期避免对故障率高的节点和链路的使用，实现网络的高可用性。
[0005]目前针对虚拟网的高可用性的研宄，主要表现在虚拟网的可靠性上和故障诊断方面。在目前考虑了可靠性的虚拟网络映射研宄中，分别假设了底层物理网络的物理节点、物理链路以及区域的失效。为了保证虚拟网络可以从单物理节点失效中完全恢复过来，在虚拟层增加了备份虚拟节点及相应的备份虚拟链路。本发明研宄的一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法，通过去除底层网络故障率较高的节点和链路并限制资源利用率的大小为实现网络的高可用性提供了一种可行的方法。
【发明内容】
[0006]本发明的目的是针对现有技术的不足，提供一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法。
[0007]本发明解决其技术问题所采用的技术方案包括如下步骤:
[0008]步骤(I)通过考虑高可用虚拟网的关键因素，设置故障率阈值；
[0009]步骤⑵将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较，如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及其相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除；否则不做任何改动；
[0010]步骤(3)在节点映射阶段，首先将单位时间窗内的虚网请求按照其收益大小排序;
[0011]步骤(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序；
[0012]4-1.选定CPU需求最大的虚拟节点，判断是否有物理节点剩余，若无物理节点剩余，则将该虚网请求送至等待队列或拒绝请求，若有物理节点剩余则将满足虚拟节点CPU请求的物理节点全选出，在从中选出利用率小于λ，同时在映射后资源利用率小于λ的物理节点分配给该虚拟节点；
[0013]4-2.重复步骤4-1，直至所有虚拟节点完成映射或拒绝；
[0014]步骤(5)判断是否有请求剩余，若有剩余，跳至步骤⑷；若无剩余，跳至步骤(6)。
[0015]步骤(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。
[0016]所述的步骤(I)中，实现高可用的虚拟网映射要考虑的关键因素包括节点和链路要考虑的因素，其中节点要考虑的因素包括节点故障率、节点位置、节点故障恢复时间以及节点资源利用率，这里我们主要考虑节点故障率对高可用的影响；链路要考虑的因素包括链路故障率、链路故障恢复时间以及链路资源利用率，这里我们主要考虑链路故障率对高可用的影响。
[0017]所述的设置适当的故障率阈值是通过统计节点和链路故障率的大小，在保证虚拟请求一定接受率时所设定的值。
[0018]所述的步骤(2)中，在虚拟请求进行映射前，根据以往长期的统计首先对底层网络各个节点和各条链路的故障率值和所设置的故障率阈值相比较。如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及和该节点相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除。
[0019]所述的步骤(3)中，虚网请求的收益是指基础设施提供商映射成功可获得的利润，根据映射成功的虚网带宽和虚网CPU定义:具体表示为成功映射的虚网带宽之和与成功映射的虚网CPU之和的两者总和，即可表示为如下式:
[0020]R(Gv) = α Σ B (ev) + β Σ C(nv)
[0021]之所以按虚拟网请求的收益排序是因为收益越大映射优先级越高。
[0022]所述的步骤(4)中，将该虚拟请求内的虚拟节点按所要求的CPU大小排序。这里之所以将虚拟请求内的虚拟节点按所需CPU大小排序是因为我们在执行节点映射时优先选择需求大的进行映射。。
[0023]所述的步骤(4)中，若底层网络中没有达到虚拟请求的物理节点，就将该虚拟请求送入等待队列，在别的虚拟请求映射完成后，在进行该虚拟请求的映射并判断此时是否有物理节点满足该虚拟请求，若多次映射都没有物理节点能满足该虚拟请求则将该虚拟请求拒绝，不再进行映射。
[0024]所述的步骤(4)中，根据虚拟节点最大的CPU需求，在底层网络中找出能满足此要求的所有物理节点，若是初次映射在该物理节点，判断虚拟节点CPU资源与该物理节点总的资源比值是否小于λ，若小于则执行映射否则切换到物理节点资源大的节点；若是多次映射在该物理节点，判断每次映射时虚拟节点CPU资源与该物理节点剩余资源比值是否小于λ，若小于则执行映射否则切换到其他剩余资源较大的物理节点进行比较映射。这里的λ是我们要实现一定可用性时所设置的资源利用率阈值也可以称为最大的节点压力。
[0025]所述的步骤(5)中，判断是否有请求剩余，若有剩余，说明还有未执行映射的虚拟请求故跳至步骤(4)继续执行虚拟请求映射；若无剩余说明虚拟请求的节点映射已全部映射完成故直接跳转到步骤(6)继续执行链路映射。
[0026]所述的步骤￠)中，已有的链路映射方法主要包括最短路径法及多商品流算法。本文的方法分为两个步骤即节点映射和链路映射，节点映射过程如前所述，在执行完节点映射后我们根据已有多商品流算法执行链路映射，最终完成整个虚拟请求到底层网络的映射。
[0027]本发明有益效果如下:
[0028]本发明解决虚拟网映射技术实现和技术标准化过程中对高可用性急需解决的重要问题，即一种有效可实施的高可用虚拟网映射方法。从目前的研宄工作看，还未见其它有效的解决方法发表。
[0029]本发明显著技术优点提出了一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法，能有效解决映射过程中故障的发生，提高了网络的高可用性。本发明具有广阔的应用前景和广泛的实际使用效果前景。
【附图说明】
[0030]图1是优化前标准的虚拟网络映射拓扑示意图；
[0031]图2是优化后的虚拟网络映射拓扑示意图；
[0032]图3是提高可用性的算法流程图；
【具体实施方式】
[0033]下面结合附图，对本发明做进一步说明。
[0034]如图1-3所示，基于网络拓扑预优化和提高可用性的虚拟网络映射方法，包括如下步骤:
[0035]步骤(I)通过考虑高可用虚拟网的关键因素，设置故障率阈值；
[0036]步骤⑵将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较，如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及其相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除；否则不做任何改动；
[0037]步骤(3)在节点映射阶段，首先将单位时间窗内的虚网请求按照其收益大小排序;
[0038]步骤(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序；
[0039]4-1.选定CPU需求最大的虚拟节点，判断是否有物理节点满足，若无物理节点满足，则将该虚网请求送至等待队列或拒绝请求，若有则将满足虚拟节点CPU请求的物理节点全选出，在从中选出利用率小于λ，同时在映射后资源利用率小于λ的物理节点分配给该虚拟节点；
[0040]4-2.重复步骤4-1，直至所有虚拟节点完成映射或拒绝；
[0041]步骤(5)判断是否有请求剩余，若有剩余，跳至步骤(4);若无剩余，跳至步骤(6)。[0042]步骤(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。
[0043]所述的步骤(I)中，实现高可用的虚拟网映射要考虑的关键因素包括节点和链路要考虑的因素，其中节点要考虑的因素包括节点故障率、节点位置、节点故障恢复时间以及节点资源利用率，这里我们主要考虑节点故障率对高可用的影响；链路要考虑的因素包括链路故障率、链路故障恢复时间以及链路资源利用率，这里我们主要考虑链路故障率对高可用的影响。
[0044]所述的设置适当的故障率阈值是通过统计节点和链路故障率的大小，在保证虚拟请求一定接受率时所设定的值。
[0045]根据长期统计的结果，得出各个节点和链路的故障率及故障恢复时间，并以三元组的形式表示出来，其中链路上面的三元组分别表示链路带宽(单位Μ)、链路故障率、链路故障恢复时间(单位min);即表示为[链路带宽，链路故障率，链路故障恢复时间]。节点上的三元组分别表示节点吞吐量(单位Mpps)、节点故障率、节点故障恢复时间(单位min)；即表示为(节点吞吐量，节点故障率，节点故障恢复时间)。图1是优化前标准的虚拟网络映射拓扑。
[0046]所述的步骤(2)中，在虚拟请求进行映射前，根据以往长期的统计首先对底层网络各个节点和各条链路的故障率值和所设置的故障率阈值相比较。如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及和该节点相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除。
[0047]根据设置的节点和链路故障率阈值，将图1中节点故障率较大的G节点和与G节点相连的所有链路移除，同时将链路故障率较大的DH链路移除，以此得到可用的底层网络拓扑即优化后的网络拓扑，参看图2。所述的故障率阈值大小的设定和虚拟网请求的接受率有着直接关系，为了保证一定的接受率故障率阈值应设置为较大值，只有这样在和底层网络节点和链路比较时，才有更多底层节点和链路的故障率比所设置的故障率阈值小，因此所要删除的节点和链路也就越少。
[0048]所述的步骤(3)中，虚网请求的收益是指基础设施提供商映射成功可获得的利润，根据映射成功的虚网带宽和虚网CPU定义:具体表示为成功映射的虚网带宽B(ev)之和与成功映射的虚网CPU C(nv)之和的两者总和。即可表示为如下式:
[0049]R(Gv) = α Σ B (ev) + β Σ C(nv)
[0050]其中:α和β是用于调节带宽和CPU的权重系数，也可以理解为它们的单价，本文中设置α = β = 1，不影响其一般性。之所以按虚拟网请求的收益排序是因为收益越大映射优先级越高。
[0051]所述的步骤(4)中，将该虚拟请求内的虚拟节点按所要求的CPU大小排序。这里之所以将虚拟请求内的虚拟节点按所需CPU大小排序是因为我们在执行节点映射时优先选择需求大的进行映射。。
[0052]所述的步骤(4)中，若底层网络中没有达到虚拟请求的物理节点，就将该虚拟请求送入等待队列，在别的虚拟请求映射完成后，在进行该虚拟请求的映射并判断此时是否有物理节点满足该虚拟请求，若多次映射都没有物理节点能满足该虚拟请求则将该虚拟请求拒绝，不再进行映射。
[0053]所述的步骤(4)中，根据虚拟节点最大的CPU需求，在底层网络中找出能满足此要求的所有物理节点，若是初次映射在该物理节点，判断虚拟节点CPU资源与该物理节点总的资源比值是否小于λ，若小于则执行映射否则切换到物理节点资源大的节点；若是多次映射在该物理节点，判断每次映射时虚拟节点CPU资源与该物理节点剩余资源比值是否小于λ，若小于则执行映射否则切换到其他剩余资源较大的物理节点进行比较映射。这里的λ是我们要实现一定可用性时所设置的资源利用率阈值也可以称为最大的节点压力。
[0054]所述的步骤(5)中，判断是否有请求剩余，若有剩余，说明还有未执行映射的虚拟请求故跳至步骤(4)继续执行虚拟请求映射；若无剩余说明虚拟请求的节点映射已全部映射完成故直接跳转到步骤(6)继续执行链路映射。
[0055]所述的步骤￠)中，已有的链路映射方法主要包括最短路径法及多商品流算法。本文的方法分为两个步骤即节点映射和链路映射，节点映射过程如前所述，在执行完节点映射后我们根据已有多商品流算法执行链路映射，最终完成整个虚拟请求到底层网络的映射。
【主权项】
1.基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于包括如下步骤: 步骤(I)通过考虑高可用虚拟网的关键因素，设置故障率阈值； 步骤(2)将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较，如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及其相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除；否则不做任何改动； 步骤(3)在节点映射阶段，首先将单位时间窗内的虚网请求按照其收益大小排序； 步骤(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序; 4-1.选定CPU需求最大的虚拟节点，判断是否有物理节点满足，若无物理节点满足，则将该虚网请求送至等待队列或拒绝请求，若有则将满足虚拟节点CPU请求的物理节点全选出，在从中选出利用率小于λ，同时在映射后资源利用率小于λ的物理节点分配给该虚拟节点； 4-2.重复步骤4-1，直至所有虚拟节点完成映射或拒绝； 步骤(5)判断是否有请求剩余，若有剩余，跳至步骤(4);若无剩余，跳至步骤(6); 步骤(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。2.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(I)中，实现高可用的虚拟网映射要考虑的关键因素包括节点和链路要考虑的因素，其中节点要考虑的因素包括节点故障率、节点位置、节点故障恢复时间以及节点资源利用率；链路要考虑的因素包括链路故障率、链路故障恢复时间以及链路资源利用率。3.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(2)中，在虚拟请求进行映射前，根据以往长期的统计首先对底层网络各个节点和各条链路的故障率值和所设置的故障率阈值相比较；如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及和该节点相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除。4.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(3)中，虚网请求的收益是指基础设施提供商映射成功可获得的利润，根据映射成功的虚网带宽和虚网CPU定义:具体表示为成功映射的虚网带宽之和与成功映射的虚网CPU之和的两者总和，表示为如下式:R(Gv) = α Σ B (ev) + β Σ C(nv) 其中:α和β是用于调节带宽和CPU的权重系数，也可以理解为它们的单价，本文中设置α = β = 1，不影响其一般性。5.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(4)中，将该虚拟请求内的虚拟节点按所要求的CPU大小排序。6.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(4)中，根据虚拟节点最大的CPU需求，在底层网络中找出能满足此要求的所有物理节点，若是初次映射在该物理节点，判断虚拟节点CPU资源与该物理节点总的资源比值是否小于λ，若小于则执行映射否则切换到物理节点资源大的节点；若是多次映射在该物理节点，判断每次映射时虚拟节点CPU资源与该物理节点剩余资源比值是否小于λ，若小于则执行映射否则切换到其他剩余资源较大的物理节点进行比较映射。7.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(5)中，判断是否有请求剩余，若有剩余，说明还有未执行映射的虚拟请求故跳至步骤(4)继续执行虚拟请求映射；若无剩余说明虚拟请求的节点映射已全部映射完成故直接跳转到步骤(6)继续执行链路映射。
【专利摘要】本发明公开了一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法。本发明步骤如下：(1)通过考虑高可用虚拟网的关键因素，设置故障率阈值；(2)将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较；(3)在节点映射阶段，将单位时间窗内的虚网请求按照其收益大小排序；(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序；对所有虚拟节点进行映射；（5）判断是否有请求剩余，若有剩余，跳至步骤（4）；若无剩余，跳至步骤(6)；(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。本发明能有效解决映射过程中故障的发生，提高了网络的高可用性。
【IPC分类】H04L12/24, H04L12/46
【公开号】CN104901861
【申请号】CN201510304796
【发明人】吴晓春, 王伟明, 王本宽
【申请人】浙江工商大学
【公开日】2015年9月9日
【申请日】2015年6月4日
【技术领域】
[0001]本发明属于计算机通信技术领域，尤其涉及一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法。
【背景技术】
[0002]互联网的出现堪称人类文明史上的一座里程碑，它深刻地影响并改变着人们的学习、工作和生活方式。然而，随着互联网用户群体大规模的增长以及网络应用不断的推陈出新，互联网体系结构面临着新的挑战和需求。虽然传统的互联网体系结构为互联网的发展做出了巨大的贡献，但是其在可用性、可靠性、可扩展性、服务质量等多方面的问题逐渐凸显，已经不能满足对新业务的支持，因此研宄和部署全新的网络技术和结构被提上日程。虽然还未最终确定未来网络到底是一个什么样的模式，但是未来网络支持虚拟化已经被普遍
。
[0003]网络虚拟化技术是解决目前互联网硬化的有效方法:一方面，网络虚拟化技术支持多种不同架构的网络以共享方式运行于同一个公共的物理基础网络上，为不同新协议，新技术的验证提供了可能；另一方面，网络虚拟化技术的核心思想是对底层网络资源进行抽象、隔离，从而实现控制平面和数据平面的分离，这种特性正逐渐成为未来网络的关键属性。在网络虚拟化技术中，虚拟网络的高可用性问题是网络虚拟化的关键问题之一。它解决的是如何保证虚拟网及底层物理网络的可靠性和可用性，以及在网络发生故障时如何快速的进行故障恢复的问题，因此对其研宄具有重要的理论和实际意义。
[0004]网络拓扑预优化是实现网络高可用性的一种新方法，它根据故障率的大小及故障恢复时间的长短来衡量高可用。将故障率高于某一阈值的节点和链路，在进行虚拟网络映射前先从底层网络拓扑中去除，以期避免对故障率高的节点和链路的使用，实现网络的高可用性。
[0005]目前针对虚拟网的高可用性的研宄，主要表现在虚拟网的可靠性上和故障诊断方面。在目前考虑了可靠性的虚拟网络映射研宄中，分别假设了底层物理网络的物理节点、物理链路以及区域的失效。为了保证虚拟网络可以从单物理节点失效中完全恢复过来，在虚拟层增加了备份虚拟节点及相应的备份虚拟链路。本发明研宄的一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法，通过去除底层网络故障率较高的节点和链路并限制资源利用率的大小为实现网络的高可用性提供了一种可行的方法。
【发明内容】
[0006]本发明的目的是针对现有技术的不足，提供一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法。
[0007]本发明解决其技术问题所采用的技术方案包括如下步骤:
[0008]步骤(I)通过考虑高可用虚拟网的关键因素，设置故障率阈值；
[0009]步骤⑵将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较，如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及其相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除；否则不做任何改动；
[0010]步骤(3)在节点映射阶段，首先将单位时间窗内的虚网请求按照其收益大小排序;
[0011]步骤(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序；
[0012]4-1.选定CPU需求最大的虚拟节点，判断是否有物理节点剩余，若无物理节点剩余，则将该虚网请求送至等待队列或拒绝请求，若有物理节点剩余则将满足虚拟节点CPU请求的物理节点全选出，在从中选出利用率小于λ，同时在映射后资源利用率小于λ的物理节点分配给该虚拟节点；
[0013]4-2.重复步骤4-1，直至所有虚拟节点完成映射或拒绝；
[0014]步骤(5)判断是否有请求剩余，若有剩余，跳至步骤⑷；若无剩余，跳至步骤(6)。
[0015]步骤(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。
[0016]所述的步骤(I)中，实现高可用的虚拟网映射要考虑的关键因素包括节点和链路要考虑的因素，其中节点要考虑的因素包括节点故障率、节点位置、节点故障恢复时间以及节点资源利用率，这里我们主要考虑节点故障率对高可用的影响；链路要考虑的因素包括链路故障率、链路故障恢复时间以及链路资源利用率，这里我们主要考虑链路故障率对高可用的影响。
[0017]所述的设置适当的故障率阈值是通过统计节点和链路故障率的大小，在保证虚拟请求一定接受率时所设定的值。
[0018]所述的步骤(2)中，在虚拟请求进行映射前，根据以往长期的统计首先对底层网络各个节点和各条链路的故障率值和所设置的故障率阈值相比较。如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及和该节点相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除。
[0019]所述的步骤(3)中，虚网请求的收益是指基础设施提供商映射成功可获得的利润，根据映射成功的虚网带宽和虚网CPU定义:具体表示为成功映射的虚网带宽之和与成功映射的虚网CPU之和的两者总和，即可表示为如下式:
[0020]R(Gv) = α Σ B (ev) + β Σ C(nv)
[0021]之所以按虚拟网请求的收益排序是因为收益越大映射优先级越高。
[0022]所述的步骤(4)中，将该虚拟请求内的虚拟节点按所要求的CPU大小排序。这里之所以将虚拟请求内的虚拟节点按所需CPU大小排序是因为我们在执行节点映射时优先选择需求大的进行映射。。
[0023]所述的步骤(4)中，若底层网络中没有达到虚拟请求的物理节点，就将该虚拟请求送入等待队列，在别的虚拟请求映射完成后，在进行该虚拟请求的映射并判断此时是否有物理节点满足该虚拟请求，若多次映射都没有物理节点能满足该虚拟请求则将该虚拟请求拒绝，不再进行映射。
[0024]所述的步骤(4)中，根据虚拟节点最大的CPU需求，在底层网络中找出能满足此要求的所有物理节点，若是初次映射在该物理节点，判断虚拟节点CPU资源与该物理节点总的资源比值是否小于λ，若小于则执行映射否则切换到物理节点资源大的节点；若是多次映射在该物理节点，判断每次映射时虚拟节点CPU资源与该物理节点剩余资源比值是否小于λ，若小于则执行映射否则切换到其他剩余资源较大的物理节点进行比较映射。这里的λ是我们要实现一定可用性时所设置的资源利用率阈值也可以称为最大的节点压力。
[0025]所述的步骤(5)中，判断是否有请求剩余，若有剩余，说明还有未执行映射的虚拟请求故跳至步骤(4)继续执行虚拟请求映射；若无剩余说明虚拟请求的节点映射已全部映射完成故直接跳转到步骤(6)继续执行链路映射。
[0026]所述的步骤￠)中，已有的链路映射方法主要包括最短路径法及多商品流算法。本文的方法分为两个步骤即节点映射和链路映射，节点映射过程如前所述，在执行完节点映射后我们根据已有多商品流算法执行链路映射，最终完成整个虚拟请求到底层网络的映射。
[0027]本发明有益效果如下:
[0028]本发明解决虚拟网映射技术实现和技术标准化过程中对高可用性急需解决的重要问题，即一种有效可实施的高可用虚拟网映射方法。从目前的研宄工作看，还未见其它有效的解决方法发表。
[0029]本发明显著技术优点提出了一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法，能有效解决映射过程中故障的发生，提高了网络的高可用性。本发明具有广阔的应用前景和广泛的实际使用效果前景。
【附图说明】
[0030]图1是优化前标准的虚拟网络映射拓扑示意图；
[0031]图2是优化后的虚拟网络映射拓扑示意图；
[0032]图3是提高可用性的算法流程图；
【具体实施方式】
[0033]下面结合附图，对本发明做进一步说明。
[0034]如图1-3所示，基于网络拓扑预优化和提高可用性的虚拟网络映射方法，包括如下步骤:
[0035]步骤(I)通过考虑高可用虚拟网的关键因素，设置故障率阈值；
[0036]步骤⑵将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较，如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及其相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除；否则不做任何改动；
[0037]步骤(3)在节点映射阶段，首先将单位时间窗内的虚网请求按照其收益大小排序;
[0038]步骤(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序；
[0039]4-1.选定CPU需求最大的虚拟节点，判断是否有物理节点满足，若无物理节点满足，则将该虚网请求送至等待队列或拒绝请求，若有则将满足虚拟节点CPU请求的物理节点全选出，在从中选出利用率小于λ，同时在映射后资源利用率小于λ的物理节点分配给该虚拟节点；
[0040]4-2.重复步骤4-1，直至所有虚拟节点完成映射或拒绝；
[0041]步骤(5)判断是否有请求剩余，若有剩余，跳至步骤(4);若无剩余，跳至步骤(6)。[0042]步骤(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。
[0043]所述的步骤(I)中，实现高可用的虚拟网映射要考虑的关键因素包括节点和链路要考虑的因素，其中节点要考虑的因素包括节点故障率、节点位置、节点故障恢复时间以及节点资源利用率，这里我们主要考虑节点故障率对高可用的影响；链路要考虑的因素包括链路故障率、链路故障恢复时间以及链路资源利用率，这里我们主要考虑链路故障率对高可用的影响。
[0044]所述的设置适当的故障率阈值是通过统计节点和链路故障率的大小，在保证虚拟请求一定接受率时所设定的值。
[0045]根据长期统计的结果，得出各个节点和链路的故障率及故障恢复时间，并以三元组的形式表示出来，其中链路上面的三元组分别表示链路带宽(单位Μ)、链路故障率、链路故障恢复时间(单位min);即表示为[链路带宽，链路故障率，链路故障恢复时间]。节点上的三元组分别表示节点吞吐量(单位Mpps)、节点故障率、节点故障恢复时间(单位min)；即表示为(节点吞吐量，节点故障率，节点故障恢复时间)。图1是优化前标准的虚拟网络映射拓扑。
[0046]所述的步骤(2)中，在虚拟请求进行映射前，根据以往长期的统计首先对底层网络各个节点和各条链路的故障率值和所设置的故障率阈值相比较。如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及和该节点相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除。
[0047]根据设置的节点和链路故障率阈值，将图1中节点故障率较大的G节点和与G节点相连的所有链路移除，同时将链路故障率较大的DH链路移除，以此得到可用的底层网络拓扑即优化后的网络拓扑，参看图2。所述的故障率阈值大小的设定和虚拟网请求的接受率有着直接关系，为了保证一定的接受率故障率阈值应设置为较大值，只有这样在和底层网络节点和链路比较时，才有更多底层节点和链路的故障率比所设置的故障率阈值小，因此所要删除的节点和链路也就越少。
[0048]所述的步骤(3)中，虚网请求的收益是指基础设施提供商映射成功可获得的利润，根据映射成功的虚网带宽和虚网CPU定义:具体表示为成功映射的虚网带宽B(ev)之和与成功映射的虚网CPU C(nv)之和的两者总和。即可表示为如下式:
[0049]R(Gv) = α Σ B (ev) + β Σ C(nv)
[0050]其中:α和β是用于调节带宽和CPU的权重系数，也可以理解为它们的单价，本文中设置α = β = 1，不影响其一般性。之所以按虚拟网请求的收益排序是因为收益越大映射优先级越高。
[0051]所述的步骤(4)中，将该虚拟请求内的虚拟节点按所要求的CPU大小排序。这里之所以将虚拟请求内的虚拟节点按所需CPU大小排序是因为我们在执行节点映射时优先选择需求大的进行映射。。
[0052]所述的步骤(4)中，若底层网络中没有达到虚拟请求的物理节点，就将该虚拟请求送入等待队列，在别的虚拟请求映射完成后，在进行该虚拟请求的映射并判断此时是否有物理节点满足该虚拟请求，若多次映射都没有物理节点能满足该虚拟请求则将该虚拟请求拒绝，不再进行映射。
[0053]所述的步骤(4)中，根据虚拟节点最大的CPU需求，在底层网络中找出能满足此要求的所有物理节点，若是初次映射在该物理节点，判断虚拟节点CPU资源与该物理节点总的资源比值是否小于λ，若小于则执行映射否则切换到物理节点资源大的节点；若是多次映射在该物理节点，判断每次映射时虚拟节点CPU资源与该物理节点剩余资源比值是否小于λ，若小于则执行映射否则切换到其他剩余资源较大的物理节点进行比较映射。这里的λ是我们要实现一定可用性时所设置的资源利用率阈值也可以称为最大的节点压力。
[0054]所述的步骤(5)中，判断是否有请求剩余，若有剩余，说明还有未执行映射的虚拟请求故跳至步骤(4)继续执行虚拟请求映射；若无剩余说明虚拟请求的节点映射已全部映射完成故直接跳转到步骤(6)继续执行链路映射。
[0055]所述的步骤￠)中，已有的链路映射方法主要包括最短路径法及多商品流算法。本文的方法分为两个步骤即节点映射和链路映射，节点映射过程如前所述，在执行完节点映射后我们根据已有多商品流算法执行链路映射，最终完成整个虚拟请求到底层网络的映射。
【主权项】
1.基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于包括如下步骤: 步骤(I)通过考虑高可用虚拟网的关键因素，设置故障率阈值； 步骤(2)将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较，如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及其相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除；否则不做任何改动； 步骤(3)在节点映射阶段，首先将单位时间窗内的虚网请求按照其收益大小排序； 步骤(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序; 4-1.选定CPU需求最大的虚拟节点，判断是否有物理节点满足，若无物理节点满足，则将该虚网请求送至等待队列或拒绝请求，若有则将满足虚拟节点CPU请求的物理节点全选出，在从中选出利用率小于λ，同时在映射后资源利用率小于λ的物理节点分配给该虚拟节点； 4-2.重复步骤4-1，直至所有虚拟节点完成映射或拒绝； 步骤(5)判断是否有请求剩余，若有剩余，跳至步骤(4);若无剩余，跳至步骤(6); 步骤(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。2.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(I)中，实现高可用的虚拟网映射要考虑的关键因素包括节点和链路要考虑的因素，其中节点要考虑的因素包括节点故障率、节点位置、节点故障恢复时间以及节点资源利用率；链路要考虑的因素包括链路故障率、链路故障恢复时间以及链路资源利用率。3.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(2)中，在虚拟请求进行映射前，根据以往长期的统计首先对底层网络各个节点和各条链路的故障率值和所设置的故障率阈值相比较；如果底层网络节点的故障率值大于所设置的故障率阈值，则将该节点及和该节点相连的链路从底层网络拓扑中移除；如果底层网络链路的故障率值大于所设置的故障率阈值，则将该链路从底层网络拓扑中移除。4.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(3)中，虚网请求的收益是指基础设施提供商映射成功可获得的利润，根据映射成功的虚网带宽和虚网CPU定义:具体表示为成功映射的虚网带宽之和与成功映射的虚网CPU之和的两者总和，表示为如下式:R(Gv) = α Σ B (ev) + β Σ C(nv) 其中:α和β是用于调节带宽和CPU的权重系数，也可以理解为它们的单价，本文中设置α = β = 1，不影响其一般性。5.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(4)中，将该虚拟请求内的虚拟节点按所要求的CPU大小排序。6.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(4)中，根据虚拟节点最大的CPU需求，在底层网络中找出能满足此要求的所有物理节点，若是初次映射在该物理节点，判断虚拟节点CPU资源与该物理节点总的资源比值是否小于λ，若小于则执行映射否则切换到物理节点资源大的节点；若是多次映射在该物理节点，判断每次映射时虚拟节点CPU资源与该物理节点剩余资源比值是否小于λ，若小于则执行映射否则切换到其他剩余资源较大的物理节点进行比较映射。7.如权利要求1所述的基于网络拓扑预优化和提高可用性的虚拟网络映射方法，其特征在于所述的步骤(5)中，判断是否有请求剩余，若有剩余，说明还有未执行映射的虚拟请求故跳至步骤(4)继续执行虚拟请求映射；若无剩余说明虚拟请求的节点映射已全部映射完成故直接跳转到步骤(6)继续执行链路映射。
【专利摘要】本发明公开了一种基于网络拓扑预优化和提高可用性的虚拟网络映射方法。本发明步骤如下：(1)通过考虑高可用虚拟网的关键因素，设置故障率阈值；(2)将设置好的故障率阈值分别与底层网络节点和链路的故障率值相比较；(3)在节点映射阶段，将单位时间窗内的虚网请求按照其收益大小排序；(4)选定收益最大的虚网请求，并将该请求内的虚拟节点按照申请的CPU大小排序；对所有虚拟节点进行映射；（5）判断是否有请求剩余，若有剩余，跳至步骤（4）；若无剩余，跳至步骤(6)；(6)将成功执行节点映射的虚网请求采用己有链路映射算法执行链路映射。本发明能有效解决映射过程中故障的发生，提高了网络的高可用性。
【IPC分类】H04L12/24, H04L12/46
【公开号】CN104901861
【申请号】CN201510304796
【发明人】吴晓春, 王伟明, 王本宽
【申请人】浙江工商大学
【公开日】2015年9月9日
【申请日】2015年6月4日
最新回复(0)