虚拟网络映射模型和算法研究

邹晓辉等

摘要：虚拟网络映射是网络虚拟化的关键问题之一，其目的是在满足虚拟网络资源需求的前提下，为该虚拟网络分配合适的底层网络节点和链路资源，从而在共享的物理网络基础设施之上构建彼此隔离的多重异构虚拟网络，为网络基础创新研究提供实验环境和平台，为网络新应用提供承载服务。论述了虚拟网络映射模型和映射算法，并提出基于最小割集理论设计VN映射算法。

关键词：网络虚拟化； 虚拟网络映射； 节点映射； 链路映射

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2014）01-0045-03

0引言

计算机网络产生于20世纪60年代，从最初的军事网，到后来的科研网、商业网和民用网，计算机网络无处不在，整个世界通过互联网实现通信和资源共享。为了应对全球网络规模的不断扩张，20世纪90年代出现了诸如IPV6等促进网络发展的新技术，但由于互联网是由不同的异构自制域（AS）组成的，改造的高成本使得在所有AS上部署新架构非常困难，许多新技术也因此并未得到广泛部署和应用。

2004年，Anderson和Peterson等提出采用网络虚拟化（Network Virtualization）思想来克服当前互联网在网络基础创新上所面临的难点难关。网络虚拟化是指在共享的底层物理网络基础设施之上构建彼此隔离的多重异构虚拟网络，这些虚拟网络可以运行各自的协议、拥有各自的架构，从而为网络基础创新研究提供实验环境和平台，同时也为当前互联网向未来网络演进提供可行途径。网络虚拟化是近几年来国内外学者的一个重要研究方向，研究中，虚拟网络映射是其最基本的问题之一。一个虚拟网络（Virtual Network，VN）由虚拟节点和连接虚拟节点的虚拟链路构成拓扑，是底层物理网络（Substrate Network，SN）的一个资源片。虚拟网络映射也称为虚拟网络植入（virtual network embedding），将虚拟节点映射至底层物理网络节点，将虚拟链路映射至底层的一条或多条物理路径。

本文第2节对虚拟网络映射问题进行了建模，给出了VN映射算法的目标函数和时间窗模型；第3节论述了如何采用启发式算法和整数规划方法进行VN映射，从是否同时映射虚拟节点和虚拟链路的角度，阐述了分离型映射算法和整合型映射算法；第4节对全文进行了归纳并对VN映射算法的研究进行了展望。

1虚拟网络映射问题

虚拟网络映射将合适的物理网络资源片分配给虚拟网络请求，而将虚拟网络则部署到底层物理网络资源上，同时要求分配给虚拟网络的物理网络资源片必须满足虚拟网络资源约束。虚拟网络资源约束包括节点资源约束（如计算能力、部署位置等）和链路资源约束（如链路带宽、延迟约束等）。此外，虚拟网络映射还要解决在线请求、准入控制、拓扑多样性等问题[1]。

1.1虚拟网络映射模型

虚拟网络映射就是一个满足约束的图匹配问题，因而可用无向有权图对底层物理网络和虚拟网络请求进行描述和建模。

现将底层物理网络形式化，表示为无向有权图GS=（NS，LS，ASN，ASL）。其中，NS表示底层节点集合，LS表示底层链路集合，ASN表示底层节点属性集合（如节点的计算能力、物理位置），ASL表示底层链路属性集合（如链路带宽、延迟特性）。虚拟网络请求可以形式化为无向有权图GV=（NV，LV，CVN，CVL），其中Nv表示虚拟节点集合，Lv表示虚拟链路集合，CVN表示虚拟节点约束集合，CVL表示虚拟链路约束集合。

进行虚拟网络映射时，不同VN请求的虚拟节点可以映射到同一个SN物理节点，同一个VN请求的虚拟节点只能映射到不同的SN物理节点。VN请求的一条链路可以映射至SN的一个物理路径（当SN不支持路径切割时）或多个物理路径（当SN支持路径切割时），每个物理路径可具有一个或多个相连的物理链路，而一个物理链路可以同时承载多个虚拟链路的网络流。

1.2目标函数

1.3时间窗模型

在虚拟网络映射算法中，考虑SN资源有限的情况，通常采取时间窗模型[3]，来解决VN映射的在线请求和准入控制问题。

时间窗模型将在线到达的虚拟网络请求转化为离线式映射处理问题，以时间窗为单位周期性执行VN映射。在一个时间窗开始时，释放上个时间窗内离开的VN请求占用的资源，收集该时间窗内的VN请求（新到达的和重新排队的），并将该时间窗内的VN请求按照其映射收益（或其它度量标准）从大到小实现排序，再按序映射至物理网络。对一个时间窗内的VN请求，可以采用批处理的方式先映射该时间窗内所有VN请求的虚拟节点，如果某个VN请求的节点映射不成功，当其重映射次数小于重映射阈值（算法中设置）时，即将该VN请求送至下个时间窗的等待队列，否则，该VN请求被拒绝；然后对该时间窗内所有完成节点映射的VN请求采用批处理的方式进行虚拟链路映射，链路映射不成功的VN请求则被送至下个时间窗的等待队列或者被拒绝。对一个时间窗内的VN请求进行处理时，也可以在完成一个VN请求的节点和链路映射之后，再进行下一个VN请求的节点和链路映射，不能成功映射的VN请求，将被送至下个时间窗的等待队列或者被拒绝。

通过计算一个或多个时间窗内成功映射的虚拟网络请求总数与到达的虚拟网络请求总数比值，即可得到虚拟网络请求接受率，用其来衡量VN映射算法的优劣。

2虚拟网络映射算法

虚拟网络映射通常要满足节点资源约束、链路资源约束、拓扑约束、目标约束等，其优化问题通常是NP-hard的，可以采用启发式算法或建模为整数规划问题进行求解。

2.1启发式算法和整数规划方法

启发式算法主要采用图搜索的方式，从局部出发，根据反馈不断寻找满足目标的虚拟节点和路径，构建虚拟网络。文献[5]提出了一种保持节点紧凑的虚拟网络映射算法，将符合虚拟节点资源约束的所有物理节点作为候选宿主并将其组织成簇，在分簇过程中候选宿主节点除了要满足计算能力等约束外，还需要通过1_割检验，使得该算法求解的节点映射存在可行的链路映射与之对应的概率极大。文中定义了虚拟节点平均分布距离，设计了启发式算法求解最紧凑节点映射问题，然后将链路映射建模为多商品流问题，由此获得对应的最优链路映射方案。该算法求解的VN映射使虚拟节点分布更加紧凑，占用的资源较少，且增大了收益/开销比。但是该算法不适合于有节点位置约束的VN映射问题，由于映射过于集中在局部网络资源，不利于负载均衡，在某种程度上可能降低VN请求接受率。文献[6]提出了基于经典的蚁群算法和遗传算法的VN映射算法，并与已有的VN映射算法在映射收益、映射开销和VN请求接受率等方面进行了比较，为采用经典人工智能算法优化VN映射问题提供了参考。

虚拟网络映射问题可以建模为混合整数规划问题，从全局角度求解虚拟网络构建问题。为降低求解复杂性，通常将整数规划问题松驰为线性规划问题求解。文献[4]是一个具有节点位置约束的VN映射问题，通过将具有位置约束的虚拟节点引入到SN模型图中，构建增广图，并采用混合整数规划方法对VN映射问题进行建模。为降低求解难度，将整数约束松弛为线性约束，求解节点映射，再将所有虚拟节点映射到底层物理节点；而后采用多商品流算法进行链路映射（当底层不支持路径切割时，采用k短路径算法）。文中采用线性规划工具glpk求解VN映射的线性规划问题和多商品流问题。在某些情况下，采用松弛整数规划求解VN映射，性能或许较差，此时应考虑合理设置目标函数、调整或增加约束条件，从而得到更优化的映射方案。

2.2分离型映射算法和整合型映射算法

基于对一个VN请求的节点映射和链路映射是否交替进行的不同状况，可以将VN映射算法归结为分离型映射算法和整合型映射算法两类，现对其展开分析探讨如下。

分离型映射算法是，首先映射完成所有虚拟节点，然后再映射虚拟链路，可参见文献[3-5]。文献[3]中，将节点映射和链路映射分为两个阶段。在节点映射阶段，基于贪婪策略，将虚拟节点请求按其收益进行排序，优先映射收益大的虚拟节点；对每个虚拟节点进行映射时，即在底层网络中寻找满足其资源约束的候选宿主集合，并将所有候选宿主按其CPU能力和周围链路带宽的乘积进行评分，再将虚拟节点映射到评分最高的候选宿主上。在链路映射阶段，则采用基于多商品流的线性规划方法。而对于某些分离型映射算法，在映射虚拟节点时可能并未考虑跟链路有关的因素，当映射某两个虚拟节点间的具有带宽约束的虚拟链路时，就会发生找不到满足带宽需求的物理路径的可能，从而导致映射失败。

整合型映射算法则是，在映射虚拟节点的同时进行虚拟链路映射，如果找不到合适的链路映射，则回溯至上一次节点映射方案重新映射节点。文献[7]提出了子图同构检测方法，在底层网络中逐步构建满足VN约束的子图，子图构建时，需要先定位节点，再寻找可行链路，如果找不到可行链路，则回溯至上一步，重新映射节点，直至完成所有虚拟节点和虚拟链路的映射。当VN请求规模较大时，多次回溯就可能使算法性能变得较差。

3结束语

已有的文献大多基于不同的优化目标来设计VN映射算法，却对在VN映射的同时要确保物理网络的良好连通性较少付诸考虑，未来的研究可以尝试基于割集理论，从最小割集的角度来设计VN映射算法，以此来获取物理网络负载的均衡和连通性，并使得底层网络基础设施可以容纳更多虚拟网络、提高资源利用率。

网络虚拟化的概念虽然已经提出很长时间，但当前与虚拟网络相关的大部分研究多是停留在实验室仿真阶段，基本上都使用GT-ITM工具生成底层物理网络和虚拟网络请求拓扑。VN映射是网络虚拟化最关键的问题之一，只有设计高效的VN映射算法才能推进网络虚拟化技术在实际网络中的实施和部署，从而加快网络技术的创新。

参考文献：

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

[2]卿苏德，廖建新，朱晓民，等. 网络虚拟化环境中虚拟网络的嵌套映射算法[J]. 软件学报， 2012，23（11）： 3045-3058.

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

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

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

[6]CHANG X L， MI X M， MUPPALA J K. Performance evaluation of artificial intelligence algorithms for virtual network embedding[J]. Engineering Applications of Artificial Intelligence， 2013， 26（10）： 2540-2550.

[7]LISCHKA J， KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection. ACM SIGCOMM，2009 Workshop， 81-88.