虚拟网络映射研究

目录虚拟网络的引入虚拟网络概述虚拟网络映射问题介绍虚拟网络映射问题形式化定义虚拟网络映射问题分类虚拟网络映射问题评价指标虚拟网络映射问题研究现状虚拟网络映射问题新方向虚拟网络引入虚拟化技术将计算机物理资源如服务器、网络、内存及存储等予以抽象、转换后呈现出来，使用户可以比原本的组态更好的方式来应用这些资源。这些资源的新虚拟部份是不受现有资源的架设方式，地域或物理组态所限制。一般所指的虚拟化资源包括计算能力和资料储存。虚拟化技术分类平台虚拟化应用程序虚拟化存储虚拟化网络虚拟化桌面虚拟化数据库虚拟化网络虚拟化一个共享的底层物理网络上同时运行多个网络架构或网络的技术虚拟网络概述未来网络架构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)距离约束。虽然充分考虑了虚拟网络的流量需求，但该算法在映射过程中忽略了虚拟节点资源约束条件，并且该算法只适用于拓扑结构为骨干-星型的虚拟网络请求。底层网络支持路径分裂与迁移的虚拟网络映射算法同时考虑虚拟网络映射问题中的节点与链路资源约束、虚拟网络拓扑需求的多样性，以及虚拟网络准入控制等因素，支持在线虚拟网络请求的虚拟网络映射算法。属于节点映射和链路