虚拟网络映射最小费用流模型及算法*

陈晓华，李春芝，陈良育，曾振柄

（1.湖州师范学院信息工程学院 湖州313000；2.华东师范大学软件学院 上海200062；3.上海大学数学系 上海200444）

1 引言

网络虚拟化[1]，是未来互联网、云计算和软件定义网络的重要技术[2～6]。多个虚拟网络能够共享同一底层物理网络资源。虚拟化技术分割、整合网络基础设施资源，使得在不影响现有网络情况下部署新的网络架构、协议以及应用成为可能。

随着网络虚拟化技术的发展，多路径虚拟链路映射成为网络虚拟化的重要技术[7]。基于多商品流的虚拟网络链路映射[8]以底层网络总体资源消耗最低的方式映射虚拟链路，取得较好的系统收益。然而基于多商品流的多路径链路映射算法时间复杂度受虚拟网络以及底层网络规模影响较大，难以满足在线虚拟网络映射的实时性要求；且虚拟网络请求是一个动态变化的过程。因此研究虚拟网络映射动态过程，设计有效的虚拟网络多路径链路映射算法对于保证在线虚拟网络映射的实时性具有重要意义。

虚拟网络多路径链路映射主要研究有：

[8]在底层网络支持路径分裂基础上，首次提出了基于多商品流的虚拟网络多路径链路映射，与单路径链路映射相比取得了更好的底层网络资源利用率和系统收益；

·参考文献[9]提出基于最短路径叠加的虚拟网络多路径链路映射，降低了虚拟网络多路径映射的时间复杂度，但牺牲了底层资源利用率及系统收益。

2 虚拟网络映射

2.1 虚拟链路映射动态过程实例

图1中，同时到来4个虚拟网络请求，如图1（a）～图1（d）所示。方案一如图1（e）所示，选择基于多商品流的映射方案，底层网络成功映射VN1，导致物理资源耗尽而无法映射VN2、VN3和VN4。而方案二选择了另外一种方法，如图1（f）所示，因为无法找到足够的物理资源而拒绝了VN1，从而保留了足够的资源，成功映射VN2、VN3和VN4。从静态角度看，方案一能够映射较大资源请求的VN1，比方案二优越；但虚拟网络映射是动态过程，方案二能够提高较小规模虚拟网络映射成功率，影响了底层网络的整体收益，而且方案一的多商品流算法计算复杂度高，并不适合大规模虚拟网络及底层网络环境。

2.2 网络虚拟化的动态特征及代价收益动态倒置现象

网络虚拟化动态特征包括虚拟网络、底层网络和映射算法的动态特征，具体如下。

·虚拟网络动态特征：虚拟网络请求的到来时间、存在时间、虚拟网络节点个数、虚拟链路条数、节点CPU、链路带宽等。

·底层网络动态特征：随着虚拟网络请求的到来和离开，底层网络剩余CPU、链路剩余带宽资源量和分布将会动态变化。

·映射算法动态特征：随着虚拟网络请求资源量的变化，在不同映射算法下，底层网络资源利用率、虚拟网络接收率、底层网络链路资源利用率和虚拟网络拓扑大小是不同的。

从图1可以看出由于虚拟网络映射的动态特征，使得虚拟网络映射存在代价收益动态倒置现象，定义如下：假设有A和B两种不同虚拟网络映射算法，从单个虚拟网络映射的静态角度看，A能够映射较小虚拟网络，B能够映射较大虚拟网络，A映射花费的代价要高于B；由于底层网络资源有限，虽然A花费的代价要高于B，但是A能够映射较多的较小虚拟网络，使得系统收益高于B，本文称之为虚拟网络映射代价收益动态倒置现象。

2.3 虚拟网络映射模型

虚拟网络映射是网络虚拟化主要问题之一，以下介绍底层网络、虚拟网络以及虚拟网络映射模型。

·底层网络：本文通过无向图Gs=（Ns，Ls，，对底层网络建模，其中，Ns为节点集合，Ls为链路集合，为节点属性集合，为链路属性集合。本文设置节点属性为CPU处理器资源，链路属性为带宽资源。

·虚拟网络：与底层网络相同，本文通过无向图Gv=（Nv，Lv，，对虚拟网络建模，其中，Nv为节点集合，Lv为链路集合，为节点属性集合（CPU处理器资源），为链路属性集合（带宽资源）。

·虚拟网络映射：把虚拟节点和链路映射到满足虚拟资源需求的底层节点和路径，可分为节点映射和链路映射。节点映射分为：一个虚拟网络的不同节点不允许映射到同一节点、一个虚拟网络的不同节点可映射到一个节点。链路映射分为单路径映射以及多路径映射。本文在一个虚拟网络的不同节点不允许映射到同一节点以及多路径链路映射情况下，研究虚拟网络映射。

3 虚拟链路映射最小费用流模型及算法

由于多商品流的多路径映射时间复杂度高，不适合大规模虚拟网络及底层网络的虚拟网络映射。为了满足大规模虚拟网络映射在线请求的实时性要求，本文设计了基于最小费用流的多路径链路映射算法。

3.1 最小费用流模型

无向网络：无向网络NG=（V，A，C），其中V是节点集合，A是无向边集合，C是边容量集合，对于每条边（i，j）∈A，对应有一个c（i，j）≥0（或简写为cij）为边的容量。

无向网络流及流量：在NG中，指定一点为源点（记为s），另一点为汇点（记为t），其余的点叫做中间点，坌（i，j）∈A，f={f（i，j）}，满 足 下 述 条 件 的f称 为s到t的无向网络流。

·容量限制条件：坌（i，j）∈A，0≤fij≤cij。

·方向条件：坌i，j∈V，fij=-fji，可行流具有方向性。

·平衡条件：对于中间点，流出量等于流入量，即每个

v（f）称为f的流量。

最小费用流模型：给定NG，每一条边（i，j）∈A，给定一个单位流量的费用b（i，j）≥0（简记为）bij。最小费用流问题就是给定s、t和流量m，求出从s到t的流f满足流量v（f）=m，并使得流的总输送费用b（f）=取最小值，即

3.2 基于最小费用流的多路径映射算法

步骤1调用最小费用流算法找到一条虚拟链路的最小费用流映射，直到完成所有虚拟链路映射。

步骤2找到一条未映射的虚拟链路lv，取出链路两端点v1、v2以及链路流量vbw。

步骤3找出lv映射的两底层结点s1和s2。

步骤4创建无向网络NG=（V，A，C），设置每条边的单位流量费用。

步骤5调用最小费用流算法，如果找到s1到s2带宽流量为vbw的最小费用流f，则将f分配给lv。

其中，步骤4中不同的NG参数及单位流量费用，会产生不同的映射算法，分别为UNMCF-S和UMMCF-L。bw（i，j）表示底层链 路l（i，j）剩余的 带宽总量，bwl（i，j）表示底层链路l（i，j）已经映射的带宽总量。UNMCF-S设置NG及单位流量费用如下：容量c（i，j）=bw（i，j），如果c（i，j）==0，表示节点i与j不存在链路；如果bw（i，j）>0，单位流量费用b（i，j）=1；如果bw（i，j）==0，单 位流量费 用b（i，j）=0。UMMCF-L设置NG及单位流量费用如下：容量c（i，j）=bw（i，j），如果c（i，j）==0，表示节点i与j不存在链路；b（i，j）=bwl（i，j）。

算法1的时间复杂度为O（e·n2），其中n为物理网络的节点数，e为虚拟网络的边数。

算法1基于最小费用流的虚拟链路映射算法

输入：虚拟网络VN,底层网络SN；

输出：虚拟网络多路径映射结果；

（1）while（VN存在链路未分配）do

（2）取一条未分配虚拟链路1v：（v1，v2，vbw）；

（3）找到虚拟节点（v1，v2）对应底层节点（s1，s2）；

（4）创建NG，设置每条边的单位流量费用；

（5）if（调用最小费用流算法找到了s1到s2及带宽流量vbw的最小费用流f）

（6）映射虚拟链路1v到底层网络最小费用流f；

（7）else return null；

（8）end if

（9）end while

（10）return虚拟链路多路径映射结果

4 性能评估

本节评估虚拟网络多路径映射，首先介绍性能评价指标及仿真环境，然后对仿真结果进行说明和评估。

4.1 性能指标

与参考文献[8]一致，本文定义收益成本比、系统收益、虚拟网络接收率以及映射时间作为性能指标。

（1）收益成本比

定义R（Gv（t））为系统收益：R（Gv（t））CPU（nv），其中，为接收的虚拟网络链路带宽总和，为接收的虚拟网络节点CPU总和。定义C（Gv（t））为虚拟网络映射代价：C（Gv（t））为接收的虚拟链路lv对应底层网络路径的带宽总和，fp为接收的虚拟链路lv对应底层网络路径上的链路；定义平均收益成本比为

（2）系统收益

（3）虚拟网络接收率

（4）映射时间

定义在T个时间窗内完成虚拟网络请求映射所花费的时间。

4.2 仿真环境

因为多商品流算法受虚拟网络以及底层网络规模影响较大，本文采用GT-ITM工具随机生成一个由50个节点、约140条链路组成的较小底层网络拓扑。底层网络节点CPU资源和链路带宽资源服从50～100的均匀分布。每个时间窗为100个时间单元。虚拟网络请求过程模拟泊松过程，在每个时间窗内虚拟网络请求到达个数服从均值为20的泊松分布，每个虚拟网络的生存时间服从均值为5个时间窗的指数分布，每个虚拟网络请求节点个数服从2～8的均匀分布，每对虚拟网络节点以0.5的概率相连；设置虚拟网络节点CPU资源与链路带宽资源需求服从0～40的均匀分布，虚拟网络映射等待时间为1个时间窗。每次模拟试验运行约25 000个时间单元，包含5 000个虚拟网络请求。实验在10个不同实例运行，取平均值作为结果。为了评价虚拟网络多路径链路映射结果，本文设置节点映射为贪心算法，多路径链路映射分别采用本文提出的UNMCF-S、UNMCF-L以及多商品流链路映射算法MCF[8]。因为最短路径叠加算法[9]较MCF算法系统收益小，本文不与之比较。

4.3 虚拟网络映射仿真结果

（1）基于最小费用流的虚拟网络映射算法提高了系统收益及虚拟网络接收率

图2、图3表明UNMCF-S、UNMCF-L与MCF比较，本文所提算法的系统收益及虚拟网络接收率得到提高。例如在映射1 000个虚拟网络时，MCF算法的系统收益为10.739 51，而UNMCF-S算法提高到11.691 41。同时MCF算法的虚拟网络接收率为0.305 31，而UNMCF-S及UNMCF-L算法的虚拟网络接收率为0.40，较MCF提高了10%。这是由于虚拟网络映射具有动态性，本文所提算法能够映射更多的较小规模虚拟网络，即提高虚拟网络接收率，从而提高了系统收益。图2、图3也验证了虚拟网络映射代价收益动态倒置现象的存在。

（2）基于最小费用流的虚拟网络映射算法极大地降低了映射时间

基于最小费用流映射算法的时间复杂度低于基于多商品流映射算法，其更适合在线虚拟网络映射。以图4可以看出，基于多商品流映射算法需要首先找到是否有解，然后找到最优解，虽然收益成本比值较基于最小费用流映射算法高（如图5所示），但是映射时间远远超过基于最小费用流的映射算法。

5 结束语

本文分析了虚拟网络映射动态过程，发现了虚拟网络映射代价收益动态倒置现象。基于此，提出虚拟网络多路径链路映射的最小费用流模型，设置单位流量映射费用单价，进而设计基于最小费用流的最小代价、最小负载虚拟网络多路径链路映射算法，提高了虚拟网络接收率及系统收益，有效降低了算法时间复杂度，保证了在线虚拟网络映射的实时性要求，适用于在大规模底层网络上创建虚拟网络。

致谢本文仿真实验在C3S2服务器完成，感谢湖州师范学院C3S2计算中心的大力支持。

参考文献

1 Chowdhury N M M K,Boutaba R.Network virtualization:state of the art and research challenges.IEEE Communications Magazine,2009,47（7）:20～26

2 Anderson T,Peterson L,Shenker S,et al.Overcoming the internet impass through virtualization.IEEE Computer Magazine,2005,38（4）:34～41

3 Sun G,Anand V,Yu H F,et al.Optimal provisioning for elastic service oriented virtual network request in cloud computing.Proceedings of Global Communications Conference（GLOBECOM）,Anaheim,CA,2012:2541～46

4 Drutskoy D,Keller E,Rexford J.Scalable network virtualization in software-defined networks.IEEE Internet Computing,2013,17(2):21～27

5 Sharkh M A,Jammal M,Shami A,et al.Resource allocation in a network-based cloud computing environment:design challenges.IEEE Communications Magazine,2013,51（11）:46～52

6 Wei X L,Chen M,Fan J H,et al.Architecture of the data center network.Journal of Software,2013,24（2）:295～316

7 Fischer A,Botero J,Beck M,et al.Virtual network embedding:a survey.IEEE Communications Surveys and Tutorials,2013,15（4）:1888～1906

8 Yu M,Yi Y,Rexford J,et al.Rethinking virtual network embedding:substrate support for path splitting and migration.Proceedings of Computer Communication Review,2008,38（2）:17～27

9 Zhang Z,Cheng X,Su S,et al.A unified enhanced particle swarm optimization-based virtual network embedding algorithm.International Journal of Communication Systems,2013,26(8):1054～1073