虚拟网络映射算法 - 图文

虚拟网络映射问题

1网络虚拟化概述

网络虚拟化技术是指：通过抽象、分配、隔离机制，在一个公共物理网络(Substrate Network,SN)上支持多个虚拟网络，各个虚拟网络可以使用相互独立的协议体系，并能够根据动态变化的用户需求对整个网络中的节点资源和链路资源进行合理配。每一个虚拟网络是底层网络的一份资源片，它由虚拟节点(例如，虚拟路由器)和虚拟链路组成。网络虚拟化的优势之一是支持多个异构的网络架构共亨物理基础设施。

网络虚拟化环境与当前Internet的最大区别就在于：当前的Internet仅仅由互联网服务提供商(ISP)一个角色组成，而网络虚拟化环境由两个不同的角色组成，即基础设施提供商(Infrastrueture Providers,InP)和服务提供商(Service Providers,SP)。当前网络环境中ISP不仅提供物理的基础设施，而且直接为用户提供相应的

网络服务来满足终端用户需求。然而在网络虚拟化环境中把服务提供从ISP中解耦出

来,新增了服务提供商(SP)和虚拟网络提供商(VNP)两个角色，而原来的ISP只负责提供并管理底层网络设备成为网络基础设施提供商(InP)，由SP代替它负责网络服务的运营。其中VNP相当于中间商或经纪人(Broker)为SP代理构建虚拟网络的服务。

2网络虚拟化模型

图1展示了现有网络模型向网络虚拟化环境下的模型的转变：在网络虚拟化的环境中，基础设施层由各个基础设施提供商(InP)建造和部署的物理网络组成，这些底层的物理网络包括大量支持虚拟化的可编程节点，例如可重构的虚拟路由器、服务器及终端等。InP通过将底层网络资源虚拟化为多个“切片”的资源，然后对虚拟化的资源以统一描述方式将底层资源的细节屏蔽，为上层提供统一的虚拟资源抽象SP通过中间商Broker向InP申请和“租赁”物理资源，构建独立的虚拟网络，并在该虚拟网络上部署自己的网络架构，运行独立的定制协议，来为用户提供服务。

网络虚拟化环境中主要参与者的功能如下：基础设施提供商：网络虚拟化环境下，基础设施提供商部署并管理底层的物理网络资源，负责物理基础设施的运营及维护，并通过可编程的接口向不同的服务提供商提供资源。基础设施提供商

图1

相互间通过所提供的资源质量、允许用户可支配的访问配置自由度相区别。多个基础设施提供商可以基于基础设施提供商互联规定进行通信、合作来建立端到端的物理基础设施。服务提供商：服务提供商从多个基础设施提供商租赁资源建立虚拟网络、部署定制协议，通过对分配的网络资源实施可编程，为虚网用户提供端到端的服务。服务提供商与基础设施提供商之间的关系可以由网络配置协定规定。服务提供商之间可以依据服务提供商互联协定建立平等关系。服务提供商也可以担任基础设施提供商的角色，构建虚拟子网并将其租赁给其他服务提供商。 3虚拟网络映射

如图2所示在两个基础设施提供商提供的物理网络上，实现了两个相互独立、互不影响的虚拟网络，分别为五个用户提供服务。存在多个基础设施提供商主要是考虑到实际情况下可能存在的商业竞争。底层物理网络的每个物理节点可以同时支持多个虚拟节点，虚网1与虚网2中的虚拟节点都同时映射到了基础设施提供商1的物理节点b和c上。同样，每条物理链路也可以同时支持多条虚拟链路。用户可以选择加入不同的虚网，也可以同时加入多个虚网。每个虚拟网是由来自多个基础设施提供商的虚拟资源构成的，虚拟网由单个服务提供商组建、管理。虚网1(Virtual Network l,VN1)和虚网2 (Virtual Network2,VN2)分别由SP1和SP2创

建。SP1租赁InP1的物理资源组建虚拟网VN1，并向连接到VNI的用户U1、U2、U3、U4提供端到端的服务。而SP2通过向InP1、InP2租赁物理资源组建VN2，并通过VN2向用户U3、U4、U5提供服务。

图2

虚拟网络是由一组虚拟节点和虚拟链路组成的虚拟拓扑，是物理拓扑的子集，是基于网络虚拟化环境下的实体。其映射关系是虚拟节点映射到物理节点上，并且多个虚拟节点可一共存。虚拟链路映射到物理链路上。虚拟网络映射是根据服务提供商(SP)的请求建立虚拟网络(包括拓扑、资源需求和位置限定等要素)。将虚节点逻辑地部署在位置和资源都满足要求的基底网络的相应物理节点上，虚链路则由部署了相应虚节点的物理节点间的满足资源约束等条件的路径相连接，同时为节点和链路分配相应虚拟网络的请求，资源虚拟网络映射即实现一个虚拟网络请求的实例化或初始化。

单个虚网是由虚拟节点和虚拟链路构成的集合。虚网映射，或称虚网嵌入是为虚拟网请求在底层物理网络上寻找合适的物理资源以满足虚拟网的资源要求。为了映射整张虚网，虚网映射要为虚节点在物理网络找到一个合适的物理节点，且需要满足节点的资源请求，同时，为虚链路在物理网络上找到多条物理链路，并且每一条链路的剩余带宽都要满足虚链路映射的请求。底层物理网络由多个基础设施提供商组成，他们之间是合作与竞争的关系，如果虚网跨多个基础设施提供商映射，需要多个基础设施提供商之间进行合作。

对于虚拟网络映射的影响因素主要有一下几个方面：资源约束，VN中节点和链接对资源的需求，比如在一个VN中，每个节点需要1GHz的CPU资源，每条链接需要10Mbps的带宽资源等；节点对地理位置约束以及链接传输数据时对延迟时间的约束等。访问控制，在基础设施资源有限时，当VN数量非常大时，会出现基础设施资源无法完全满足VN需求的情况，此时必须有选择性的拒绝某些VN请求。虚拟网会有多样化的拓扑结构。 4虚网映射分类

虚网映射算法是一种资源调度算法，利用底层提供的虚拟资源进行有效地资源管理和调度。已有的虚网映射算法分为静态映射和动态映射两种分类：静态映射算法是在虚网生命周期内不允许资源分配的任何改变；动态映射算法则允许基于虚网的当前业务需求及服务性能自适应改变资源分配。

静态虚拟网络映射方法根据映射时划分的阶段数目，分为两阶段映射方法、一阶段映射方法和链路映射方法。两阶段映射方法将VN映射过程分为节点映射和链路映射两个阶段。目前的方法都是启发式方法，一阶段映射方法同时映射节点和链路，将VN作为一个整体进行映射。其又可以进一步的分为集中式方法和分布式方法两种形式。链路映射方法是在假设节点已经映射到SN中之后，解决链路映射问题的方法。

图3

动态虚拟网络映射方法可分为选择性重配置和基于基础设施变化两种：选择性重配置是根据VN 的动态变化，相应地进行重配置，以解决周期的映射方案在下周期无法适用的问题。选择性重配置方法根据重配置策略的不同，可分为周期

性重配置、VN拒绝重配置以及异常情况重配置3种方式。基于基础设施变化是指通过对基础设施的路径映射方式进行修改来求解VNMP，可分为基于路径分割和基于路径拼接两种方法。

多基础设施提供者问题是指基础设施资源由多个不同的InP提供下的VNMP，现有的求解方法主要有基于策略和基于机制设计两种。基于策略的方法是指采用启发式的方法选择VN所需要的基础设施资源并完成VN映射，异构基础设施资源之间的交互通过设计特定的协议来实现；基于机制设计的方法旨在于构建一个公平、合理的资源分配方案，通过经济学中的机制设计原理，避免InP为了追求自身利益最大化、对外虚报其内部拓扑以及内部映射信息而导致全局分配方案效率较低的问题。目前对虚拟网络映射的研究主要是基于当基础设施提供商，多基础设施提供商问题的研究还较少。 5虚拟网络映射的网络模型

物理拓扑通常用加权无向图Gs??Ns,Es?表示：每个物理节点ns具有属性集合A(ns)，包括CPU资源C(ns)、地理位置loc(ns)，每条物理链路es具有属性集合A(es)，其中包括带宽资源B(es)；虚网拓扑通常也由加权无向图Gv??Nv,Ev?表示，同样具有各自的属性集合。

为了降低虚网映射的复杂度，多数算法将虚网映射分为两个阶段求解：节点映射和链路映射。对于虚节点映射，每个虚节点应能够确定地映射到一个物理节点上。对于虚链路映射，需要取决于流是否是可分离的，流是可分离的，虚链路可以采用多条物理路径映射，流是不可分离的，虚链路可以采用单条路径映射。由于节点的主要资源是CPU，链路的主要资源是带宽，所以，下面在介绍节点映射和链路映射的数学模型时，节点的约束条件仅考虑CPU，链路的约束条件仅考虑带宽。

不同虚拟网络的虚拟结点可以映射到同一个物理结点，但是同一个虚拟网络中的虚拟结点必须映射到不同的物理结点。每个虚拟节点都要映射到不同的物理

RiRiRi?NS?NS:NS?ns?Ns|RCPU?nS??minn?NRiC?nV?，节点上，表示为FNRi:NVVV??Ri其中，NS表示该集合至少存在一个物理节点，该物理节点的剩余CPU资源至少

能满足虚拟网请求Ri中的一个虚拟节点的CPU映射要求。物理节点剩余CPU资源

RCPU(ns)定义为物理节点的总CPU减去该节点已经映射使用的CPU：

RCPU?nS??C?nS???nV?nS?C?n?。每条虚拟链路都要映射到不同的物理路径上，表示

VRi?PSRi?PS：PSRi?P?PS|B?P??mine?ERiB?eV?，其中，PSRi表示该为FERi:EVvV??集合至少存在一条物理路径，该物理路径的剩余带宽至少能满足虚拟网络请求Ri的一条虚拟链路的带宽映射要求。物理路径的集合由PS表示，其中源节点为ns，目的节点为nt的物理路径可表示为PS(ns,nt)。物理路径P的可用带宽B(P)等于该路径上具有最少剩余带宽的链路的可用带宽：B?P??minRBW?es?，物理链路剩余带

es?P宽资源RBW?es?定义为物理链路的总带宽减去该链路已经映射使用的带宽：

RBW?es??B?es???ev?es?B?e?。

v下面给出虚拟网络映射的一个实例，解释虚网映射问题：

图4

图右侧表示物理网络，其中，线条上方的数字表示物理链路的总带宽，矩形框中的数字表示物理节点的总的CPU资源。图左侧表示两个虚拟网请求VN1和VN1。虚网映射的结果为：VN1的虚拟节点a、b、c分别映射到物理节点D、A、F上，其虚拟链路(a,b)、(a,c)、(b,c)分别映射到物理路径(D,A)、(D,E,F)、(A,G,F)上。VN2的虚拟节点d、e分别映射到物理节点B、C上，其虚拟链路(d,e)映射到物理链路(B,C)上。物理链路(B,C)的总带宽是5，虚链路(d,e)的请求带宽是4，所以物理链路(B,C)的剩余带宽是1。根据图给出的物理节点CPU及物理链路带宽的配置情况，上述映射方案是能够满足VN1和VN2的资源请求的。 5.1两阶段虚网映射算法

贪婪式的节点映射步骤：步骤一：对所有的虚拟网络请求，按照他们的收益进行排序；步骤二：判断是否有请求，如果无请求则停止；步骤三：取出最大收益的请求；步骤四：找到可用CPU的能力满足节点约束的物理节点子集S(CPU的能力应比虚拟网络的需求大)，如果S==?，将此需求重新放回到请求队列，然后跳转到步骤二；步骤五：对于每个虚拟节点，都在物理节点集合S中找到最大可用资源节点H ，然后跳转到步骤二。这是目前对节点的映射的主要方法。

而多商品流问题是对链路的映射方法，多商品流问题(Multi-commodity Flow Problem)是多种商品(或货物)在网络中从不同的源节点流向不同的宿节点的网络流问题。已知一商品流网络G=(V,E)，其中边?u,v??E的容量为c(u,v)。有k个商品流K1,K2,?,Kk,每个商品流定义为Ki??si,ti,di?，其中si和ti是物品i的源节点和宿节点，而di是需求。物品i沿边(u,v)的流量是fi(u,v)。多商品流问题(MCF)就是求一个符合以下限制条件的流量分配问题：容量的限制，?fi?u,v??c?u,v?；流

i?1k量

i守

i恒

i，

w?V?f?u,w??0iwhu?esi,tin；

需求满足，

w?V?f?s,w??d在网络中只要满足了上面三个约束条件的的流??fi?w,ti??di。

w?V量分配问题就是多商品流问题。 5.2单阶段虚网映射算法

采用两阶段优化方法是把多目标优化问题简化成两个阶段的单目标优化问题，但是，一方面很难得到全局最优；另一方面，如果出现坏的映射决定时需要回溯，而回溯是非常耗时的。例如，如果节点映射完成后发现无法满足所有的链路约束需求，则需要把节点约束回溯或者重新映射一次。因此，如果同时考虑这两个阶段，则能实现收益率更高的虚拟网络映射，也能达到更快的映射速度。

路径切割方法：主要用于处理虚拟链路映射的问题，通过该方法，一条虚拟链路能够映射到底层物理网络中的多条底层路径上。路径迁移方法：主要用于处理在线虚拟网络请求的问题，该方法周期性地优化已有的映射关系，采取的方法有重新映射到新的底层路径或者改变路径分割率。 6虚网映射的收益与开销

对于基础设施提供商来说，虚拟网络映射算法的目标是耗费最小的物理资源

尽可能产生更大的收益。我们把每个虚拟网产生的收益定义为：

R?GV??nV?NV?c?n????b?e?。同时虚拟网消耗的物理资源所产生的成本可定义

VVeV?NVnV?NV为：C?GV??

a?P,e?b?P,e?。 ?a?n?c?n???????VVVveV?EVP?PSeV

本文来源：https://www.bwwdw.com/article/g3d2.html