基于多商品流模型的虚拟链路映射

邹晓辉 孙静

摘要：网络虚拟化是解决网络僵化问题和更好地共享底层网络资源的一种有效途径，虚拟网络映射是实施网络虚拟化的关键问题之一。虚拟网络映射包括节点映射和链路映射两个方面，其目标是为虚拟网络请求分配合适的底层网络节点和链路资源。阐述了底层网络支持路径分割时，如何基于多商品流模型实现VN链路映射。

关键词：网络虚拟化； 虚拟网络映射； 链路映射； 多商品流

中图分类号：TP3932 文献标识码：A文章编号：2095-2163（2013）06-0107-02

0引言

资源虚拟化通过整合底层基础设施的分散资源，为上层服务提供统一的资源池，实现底层资源共享和透明访问，提高资源利用率，简化资源管理。目前，计算虚拟化、存储虚拟化技术等已经相对成熟，并在实践中得到广泛应用。网络虚拟化作为解决网络僵化问题和更好地共享底层网络资源的一种有效途径，近几年来已经得到业界和国内外学者的广泛关注，但由于网络资源的特殊性，网络虚拟化的实质性研究还处于起步阶段。

在网络虚拟化技术中，虚拟网络映射问题是非常重要的研究方向之一。网络虚拟化通过共享底层网络基础设施（Substrate Network，SN），可以在其上部署多重异构的虚拟网络（Virtual Network，VN），各VN彼此隔离，并分别运行各自的协议、拥有各自的架构。VN由虚拟节点和虚拟链路构成，VN映射问题就是为各VN请求分配SN的节点和链路资源，将虚拟节点和虚拟链路分别映射至合适的底层物理节点和物理路径上。整个虚拟网络映射问题可以分解为节点映射和链路映射两个方面。

由于物理资源的有限性，随着虚拟网络请求的部署和服务结束后资源的释放，形成了很多资源碎片。当SN支持路径分割时，为充分利用这些资源碎片和避免出现瓶颈链路，可以将一条VN链路的带宽需求进行分割，并将一条虚拟链路分流到具有相同起点和终点的多条物理路径上，实现多径映射[1]。多径映射还可以提高VN链路的可靠性，当一条物理路径发生拥塞或失效时，可以将该路径上的网络流量迁移到其它路径上。

本文第1节给出了当SN支持路径分割时的虚拟链路映射模型，第2节阐述了多商品流问题原理及基于多商品流模型的虚拟链路映射，第3节对本文进行了总结。

1底层网络支持路径分割的虚拟链路映射模型

设VN请求的虚拟链路集合LV={lv1，lv2，…，lvk}，lvi=（nvsi，nvti，di），lvi表示集合中的第i个虚拟链路，其中nvsi和nvti为虚拟链路lvi的两个端点，di表示虚拟链路lvi的带宽需求。nvsi和nvti分别映射到底层物理节点Nsi，Nti。设Pi=（pi1，pi2，…，pih）为Nsi和Nti之间的物理路径集合，在底层网络支持路径分割的情况下，可以将虚拟链路lvi的带宽需求分布到Pi的多条物理路径上，由多条物理路径承载虚拟链路的网络流量，可以表示为M（lvi）=（pi1，pi2，…，pih）。每条物理路径可以包含多个相连的物理链路，即pij={（Nsi，Nij1），（Nij1，Nij2），…，（Nijm，Nti）}，其中1≤j≤h，每个物理链路用其部分带宽容量承载映射到其上的虚拟链路，并且在带宽容量有限的情况下每个物理链路可以承载多个虚拟链路的网络流。图1为底层网络支持路径分割的虚拟链路映射示例。

图1中，左图为VN请求拓扑，右图为物理网络拓扑，因为本文只讨论虚拟链路映射，所以忽略了节点映射约束。其中六边型结点代表虚拟节点，虚拟节点之间的连线代表虚拟链路，虚拟链路上的数字表示其带宽需求；圆形结点代表底层网络中的物理节点，物理节点之间的实线连接代表物理链路，物理链路上的数字表示其可用带宽，物理节点之间的虚线代表虚拟链路映射到的物理路径。映射结果如图中所示，即节点映射为{a→A，b→B，c→D}，链路映射为{（a，b）→（A，B），（a，b）→{（A，F），（F，C），（C，B）}，（b，c）→{（B，C），（C，D）}，（c，a）→{（D，E），（E，A）}}。由于（a，b）的带宽需求在一条物理路径上无法满足，所以（a，b）多径映射到两条物理路径（A，B）和{（A，F），（F，C），（C，B）}，物理链路（B，C）承载了两个虚拟链路（a，b）和（b，c）的网络流。

2基于多商品流的虚拟链路映射

2.1 多商品流问题

多商品流问题是指多种商品流（或物质）在网络中从不同的源端向不同的目的端进行传输的网络流问题，是一个多源多汇问题。可以定义如下：

设G=（N，L）表示一商品流网络，其中N表示网络节点的集合，L表示网络链路的集合，链路（u，v）∈L的容量为C（u，v）。设有k个商品流fi（1≤i≤k）经过网络G，商品流fi的源节点和目的节点分别为si和ti，需求为di，fi（u，v）表示商品流fi在链路（u，v）上分布的流量值。则多商品流问题是一个满足以下约束条件[2]的流量分配问题：

其中，式（1）是网络链路容量约束，表示所有商品流fi（1≤i≤k）分布到链路（u，v）上的流量之和不能超过链路（u，v）的容量；式（2）是商品流fi需求约束，表示所有链路上承载的商品流fi的流量之和满足商品流fi的需求；式（3）是流守恒约束，表示在网络的中间节点进口流量总和等于出口流量总和。

根据VN链路映射与多商品流问题的相似性，VN映射请求拓扑中的具有容量约束的一条虚拟链路lvi可以对应多商品流问题中的一个商品流fi，lvi的两个端点对应fi的源点和汇点，则VN虚拟链路映射问题可以建模为多商品流问题进行求解。

2.2基于多商品流模型的虚拟链路映射

设计VN映射算法通常基于某个目标函数，如最大化映射收益、最小化映射开销、提高虚拟网络请求接受率等。基于多商品流模型的虚拟链路映射算法结合某个目标函数与相应的流量分配约束，其求解是线性规划问题。

如前所述，忽略VN请求的节点约束，将VN请求表示成虚拟链路的集合，即R={（nvs1，nvt1，d1），（nvs2，nvt2，d2），…，（nvsk，nvtk，dk）}，把底层物理网络SN形式化为无向有权图GS=（NS，LS，ASL），其中NS表示底层节点集合，LS表示底层链路集合，ASL表示底层链路属性集合（如链路带宽），虚拟链路lvi的两个端点nvsi和nvti分别映射到底层节点Nsi，Nti。令c（u，v）为物理链路（u，v）的单位带宽代价，（u，v）∈LS，令r（u，v）表示物理链路（u，v）的可用带宽，fi（u，v）表示物理链路（u，v）承载的第i个虚拟链路的流量。

基于多商品流问题的约束条件，以最小化映射开销为目标，基于多商品流模型的虚拟链路映射线性规划如下：

具体映射结果可以采用线性规划工具glpk求解。对于具体的VN映射请求，可以根据实际情况合理设置目标函数、调整或增加约束条件，从而得到更优化的映射方案。

3结束语

多商品流模型可以用来求解多源多汇问题，如铁路网车流分配、通信网带宽分配、多商品物流网络设计等。对于链路映射通常采用k短路径算法或基于多商品流的线性规划方法[3-5]。虚拟链路的单径映射是NP-hard问题，当底层网络支持路径分割时，虚拟链路的多径映射建模为基于多商品流模型的线性规划问题降低了映射复杂度。虚拟链路的多径映射，不仅可以实现负载均衡，当底层物理链路失效时，还可以通过链路迁移[6]，将失效链路上的网络流迁移到其他可用链路上，从而提高VN链路的可靠性。

参考文献：

[1]YU ML， YI Y， REXFORD J， et al. Rethinking virtual network embedding： Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review， 2008，38（2）.

[2]刘志文. 网络虚拟化环境下资源管理关键技术研究[D]. 北京：北京邮电大学，2012-5.

[3]ZHANG M， YANG Q， WU C，et al. Hierarchical virtual network mapping algorithm for large-scale network virtualization. IET Commun.， 2012，6.

[4]CHOWDHURY M， RAHMAN MR， BOUTABA R. Virtual network embedding with coordinated node and link mapping. IEEE INFOCOM 2009， 2009.

[5]刘新刚，怀进鹏，高庆一，等. 一种保持结点紧凑的虚拟网络映射方法[J]. 计算机学报， 2012（12）： 2492-2504.

[6]蔡志平，刘强，吕品，等. 虚拟网络映射模型及其优化算法[J]. 软件学报， 2012（12）： 864-877.