虚拟网络映射研究

目录虚拟网络的引入虚拟网络概述虚拟网络映射问题介绍虚拟网络映射问题形式化定义虚拟网络映射问题分类虚拟网络映射问题评价指标虚拟网络映射问题研究现状虚拟网络映射问题新方向虚拟网络引入虚拟化技术将计算机物理资源如服务器、网络、内存及存储等予以抽象、转换后呈现出来，使用户可以比原本的组态更好的方式来应用这些资源。这些资源的新虚拟部份是不受现有资源的架设方式，地域或物理组态所限制。一般所指的虚拟化资源包括计算能力和资料储存。虚拟化技术分类平台虚拟化应用程序虚拟化存储虚拟化网络虚拟化桌面虚拟化数据库虚拟化网络虚拟化一个共享的底层物理网络上同时运行多个网络架构或网络的技术虚拟网络概述未来网络架构InternetServiceProviders(ISPs)InfrastructureProvider(InP)ServiceProvider(SP)VirtualNetworkProvider(VNP)VirtualNetworkOperator(VNO)ServiceProvider(SP)虚拟网络概述2. 虚拟网络实例

VPNVLANOverlaynetworksProgrammablenetworks虚拟网络研究方向ResourceallocationResourcediscoveryAdmissioncontrolandusagepolicingVirtualnodesandvirtuallinksResourceschedulingNamingandaddressingDynamismandmobilitymanagementVirtualnetworkoperationsandmanagementSecurityandprivacyHeterogeneityofnetworkingtechnologiesNetworkvirtualizationeconomics虚拟网络映射问题介绍

虚拟网络映射（virtualnetworkembedding）为带有节点和链路资源约束条件的虚拟网络请求分配底层网络资源的问题，NP-hard问题。虚拟网络映射问题，是在共享的底层网络中为带有资源约束的逻辑拓扑分配相应资源。VNE是一个动态资源分

配问题虚拟网络映射问题介绍3. 虚拟网络映射实例a10b10c30d50a20c20b15B20C40EFAD30102020abcd1030B10C30EFAD3010bac1515101015202020202020254025252540151215（a）虚拟网络请求1（c）虚拟网络请求2（b）底层网络（d）底层网络3030虚拟网络问题的形式化定义底层网络

带权无向图，其中，表示底层节点的集合，表示底层链路的集合，和

分别表示底层节点

与底层链路

所具有的属性。2. 虚拟网络带权无向图

，其中，

为虚拟节点的集合，为虚拟链路的集合，与分别表示虚拟节点

与虚拟链路

的资源约束。一般来讲，虚拟节点的资源约束主要考虑该虚拟节点的计算能力需求，虚拟链路的资源约束主要考虑该虚拟链路的带宽资源需求。对于一个虚拟网络请求，用三元组

来表示，其中，表示虚拟网络请求的到达时刻，表示虚拟网络在底层网络中持续的时间。虚拟网络映射问题定义为映射：

，其中，

，

。

虚拟网络映射问题评价指标虚拟网络映射的主要目标

充分利用有限的底层网络资源，为更多的虚拟网络请求提供服务，从而提高底层网络运营收益，相应的评价指标有：1)底层网络长期平均运营收益；2)虚拟网络请求接受率；3)虚拟网络映射长期平均收益开销比。底层网络长期平均运营收益

在t时刻底层网络接受一个虚拟网络的收益可以定义为：

其中，

表示虚拟节点的计算能力需求值，

表示虚拟链路的带宽能力需求值。参数和

可用于调节计算资源与带宽资源的相对权重。在虚拟网络映射问题中，收益一般是指接受该虚拟网络请求为底层网络运营商带来的经济收益。

在t时刻接受一个虚拟网络的开销定义为底层网络分配给该虚拟网络资源的和：虚拟网络映射问题评价指标

其中，

，当底层链路向虚拟链路分配带宽资源时=1，否则=0。

表示向分配带宽的值。参数和1-的含义与式(1)一致。

底层网络运营商需要高效的虚拟网络映射算法以最大化其运营收益。底层网络的长期平均运营收益可以定义为：3. 虚拟网络请求接受率

在相同的底层网络资源状况下，高效的虚拟网络映射算法应能够接受更多的虚拟网络请求。对虚拟网络请求接受率可以做如下定义：其中，

表示从t=0时刻起到T时刻被成功映射的虚拟网络个数，表示从t=0时刻起到T时刻虚拟网络请求的总数。虚拟网络映射问题评价指标4. 虚拟网络映射长期平均收益开销比

虚拟网络映射长期平均收益开销比可以在一定程度上反映底层网络资源的利用效率，它被定义为在一段时间内所有接受的虚拟网络请求的映射收益与其相应的资源开销的比值:

虚拟网络映射问题分类静态映射算法与动态映射算法（S/D）按照不同的底层网络资源分配方式，可以将虚拟网络映射算法分为静态映射算法与动态映射算法。静态映射算法是指静态地为虚拟网络分配固定比例的底层网络资源。而动态映射算法又可以分为动态自适应和动态重配置的映射算法，其中，动态自适应的映射算法根据虚拟网络自身的资源需求动态为其分配底层网络资源；而动态重配置的映射算法是指在虚拟网络资源需求不改变的情况下，根据某种性能指标动态地调整映射方案。

图.动态映射算法虚拟网络映射问题分类2. 离线映射算法与在线映射算法离线映射是指所有虚拟网络请求信息在其被映射前均是已知的；而在线映射算法则不对虚拟网络请求的到达时间，持续时间以及拓扑信息等作任何假设。

图.在线映射算法虚拟网络映射问题分类3. 集中式映射算法与分布式映射算法集中式的虚拟网络映射算法由中心决策机构根据底层网络资源状况，为虚拟网络请求分配相应资源。而分布式的虚拟网络映射算法一般通过底层节点协同完成虚拟网络映射过程。4. 二阶段映射与一阶段映射算法按照不同的虚拟节点与虚拟链路映射顺序，可以将虚拟网络映射算法分为虚拟节点优先映射(或称为二阶段映射)与虚拟节点和链路同时映射(或称为一阶段映射)2类算法。5. 冗余映射与非冗余（简单）映射算法简单的映射算法是尽量充分利用网络资源去满足虚拟网络请求，没有预留多余的冗余资源。那么一旦底层资源失败，很难从失败中恢复。冗余映射算法是，在进行虚拟网络映射时，同时提供节点、链路的备份，使得一旦资源失败能够快速切换。虚拟网络映射问题的研究现状面向负载均衡的虚拟网络映射算法包括无重配置的虚拟网络映射算法与

带有重配置的虚拟网络映射算法。无重配置的虚拟网络映射算法，基本思想是将虚拟节点映射到负载较轻并且离已被映射的虚拟节点较近的底层节点上，当映射完所有虚拟节点后，使用最短路径算法映射虚拟链路。由于底层网络资源状况随着虚拟网络请求的到达与离开而变化，会导致底层网络负载不均衡，资源利用率下降等问题。带有重配置的虚拟网络映射算法，该算法周期性地检查底层节点和链路负载状况，当节点或链路负载超越预先定义的阈值后，将对映射于该节点或链路上的所有虚拟网络进行重映射，以消除资源热点问题。这2种虚拟网络映射算法在提高底层网络资源利用率方面具有较好效果，但这2种算法在虚拟网络映射过程中均没有考虑底层网络与虚拟网络资源约束条件，并且提出的对已映射的虚拟网络进行重映射的算法虽然可以在一定程度上平衡底层网络负载，但会导致虚拟网络服务中断等严重问题。虚拟网络映射问题的研究现状2. 基于流量约束的虚拟网络映射算法主要目标是寻找一种既能满足虚拟网络流量需求又能高效利用底层网络资源的映射方案。流量约束由以下3类约束构成：1)终端流量约束；2)点对问流量约束；3)距离约束。虽然充分考虑了虚拟网络的流量需求，但该算法在映射过程中忽略了虚拟节点资源约束条件，并且该算法只适用于拓扑结构为骨干-星型的虚拟网络请求。底层网络支持路径分裂与迁移的虚拟网络映射算法同时考虑虚拟网络映射问题中的节点与链路资源约束、虚拟网络拓扑需求的多样性，以及虚拟网络准入控制等因素，支持在线虚拟网络请求的虚拟网络映射算法。属于节点映射和链路映射分开的两阶段算法。该算法有益于提高虚拟网络请求接受率和底层网络资源利用率，但由于该算法在虚拟节点映射阶段并没有对虚拟链路的映射进行考虑，因此可能会导致虚拟链路映射开销较大的问题。虚拟网络映射问题的研究现状底层网络支持路径分裂与迁移的虚拟网络映射算法图.支持路径分裂的虚拟网络映射算法虚拟网络映射问题的研究现状底层网络支持路径分裂与迁移的虚拟网络映射算法图.支持路径迁移的虚拟网络映射算法虚拟网络映射问题的研究现状4. 协同节点与链路映射的虚拟网络映射算法节点与链路协同是指在虚拟节点的映射阶段同时考虑虚拟链路映射。一定程度上降低了每次虚拟网络映射的资源开销，为接受更多的虚拟网络请求当底层网络不支持路径分裂时，该算法性能较差。提供了空间，但该算法过度地依赖底层网络支持路径分裂这一特性，忽略了其带来的负面影响。虚拟网络映射问题的研究现状5. 基于子图同构检测的虚拟网络映射算法该算法的基本思想是在同一阶段映射虚拟节点和链路，当虚拟节点被成功映射后，便采用最短路径算法映射与该节点相连的虚拟链路。在映射过程中，如果有虚拟链路映射失败的情况发生，则回溯到上一个虚拟节点映射阶段进行节点重映射。由于该算法在同一阶段映射虚拟节点和链路，因此它可以有效避免虚拟链路被映射到底层网络中长路径的问题，从而降低了虚拟网络映射的底层网络资源开销，提高底层网络资源利用效率，但该算法本质是一种回溯算法，计算开销较大，而且．该算法不能够处理虚拟节点带有位置需求的虚拟网络请求。6. 面向QoS的虚拟网络映射算法该算法的基本思想是尽可能地将一条虚拟链路映射到一条底层链路上。该算法能够处理带有高级别QOS需求的虚拟网络请求，但由于其虚拟节点与虚拟链路的映射过程采用回溯方式进行，计算开销大。此外，当底层网络资源不充足或虚拟网络规模较大时，采用该算法很难获得能够满足虚拟网络映射资源需求的可行映射方案。虚拟网络映射问题的研究现状分布式的虚拟网络映射算法该算法由虚拟网络拓扑分解和映射2个阶段组成。虽然该算法可有效避免集中式虚拟网络映射算法单点故障问题，能够快速应对底层网络局部故障，但当底层网络规模较大时，代理节点间信息同步与交互通信开销大，性能方面还不能与集中式算法相比。动态自适应的虚拟网络映射算法底层链路监测各个虚拟网络的流量状况，并根据其承载的虚拟链路的拥塞级别和性能指标等局部信息，周期性地重新为虚拟链路分配共享的底层带宽资源。够动态自适应地为虚拟网络分配底层网络带宽资源，从而提高了底层网络带宽资源利用效率，但它并没有对虚拟节点的映射和资源分配问题进行考虑，而且由于周期性地对所有虚拟网络的带宽资源分配进行调整，系统的稳定性是一个值得关注的问题。虚拟网络映射问题的研究现状9. 拓扑感知的虚拟网络映射算法借鉴GooglePageRank思想，基于马尔科夫随机游动(randomwalk)模型。为底层(或虚拟)节点资源度量方法NodeRank。节点的NodeRank值不仅可以反映当前节点的资源能力(例如，计算能力与带宽能力)，而且还能够反映其周围节点的资源能力。基于这种拓扑感知的节点资源度量方法，有2种虚拟网络映射算法：RW-MaxMatch和RW-BFS。RW-MaxMatch是一种二阶段的虚拟网络映射算法，该算法的主要思想是：将具有较大NodeRank值的虚拟节点映射到具有较大NodeRank值的底层节点上，然后利用最短路径算法或多商品流算法映射虚拟链路。而RW-BFS是一种一阶段的虚拟网络映射算法，虚拟节点的映射顺序和底层节点的选取均按照广度优先搜索的顺序进行，并且广度优先搜索的每一层网络节点按NodeRank值大小排序。当每个虚拟节点映射成功后便同时映射其虚拟链路，若虚拟节点或链路映射失败则重新映射前一个虚拟节点，虚拟节点映射和虚拟链路映射在映射过程中交替进行。其主要思想是：虚拟网络映射研究新方向底层网络资源的高效利用

对于静态的虚拟网络映射算法，如果要底层网络支持路径分裂和迁移，导致分组无序和分组丢失问题，从而对虚拟网络性能造成影响。可以考虑在底层网络不支持路径分裂时，将虚拟网络映射问