基于节点多属性的虚拟网络映射算法

张 鑫，王 珺，王晓璇

(南京邮电大学 江苏省无线通信实验室，江苏 南京 210003)

0 引 言

随着互联网规模和应用范围越来越广泛，传统的TCP/IP网络结构难以应对日益复杂和多样化的信息社会的发展。同时智能手机、平板电脑的普及，使得互联网服务提供商需要面临更加复杂和多样化的用户需求与业务，而现有的网络体系无法快速、便捷地实现业务和服务的更新与迭代。针对当前互联网发展所面临的困境，Stanford Nick McKeown教授等颠覆传统的网络结构，提出一种新型、革命式的网络模型，即软件定义网络(software defined network，SDN)及OpenFlow协议[1-2]。SDN与TCP/IP网络相比较，能够实现控制平面和转发平面的分离，网络具备可编程的特性。因此SDN网络模型主要包括SDN网络应用、SDN Controller、支持OpenFlow协议网络设备、南北向接口等。

目前，网络虚拟化技术受到工业界和学术界的高度青睐，它不仅是解决互联网发展瓶颈的关键技术，也是云计算的核心技术。同时集中控制网络架构SDN日益成熟和完善，尤其在云计算数据中心等场景下，为了实现动态调整与快速部署，必须实现业务部署的自动化。采用集中控制的方式，网络运营商可以通过控制器编程，实现自动化动态业务部署，缩短业务部署周期与成本。近些年，随着IaaS(Infrastructure as a Service)的发展，大多数主流的数据中心网络基本采用基于SDN网络模型构建虚拟网络实现网络虚拟化。

网络虚拟化技术聚焦的重点是在共享的、资源有限的物理网络中实现、分配各种不同用户或者组织要求的逻辑网络，同时保证每个逻辑网络之间能够隔离并且安全、正常地对外提供应用与服务。同时具体实现网络虚拟化技术又面临很多问题，首先就是逻辑网络映射到物理网络，即虚拟网络映射问题。目前虚拟网络映射问题已经得到广泛关注，同时因其映射过程中会受到各种条件的限制，因此属于NP-hard问题。

1 相关工作

文献[3]在不限制地理位置的条件下，底层物理网络支持路径迁移与路径分裂的特性，节点映射阶段利用Greedy算法来映射，链路映射阶段采取多商品流算法完成链路映射。文献[4]基于马尔可夫随机游动模型，利用K-核分解技术将虚拟网络划分为核心网络和边缘网络，优先考虑生存时间最短的虚拟网络请求(区别于以收入为导向的调度策略)。文献[5]在节点映射阶段引入网络拓扑属性，即在考虑CPU和带宽的同时考虑节点的度(度是节点最基本最重要的拓扑属性，可衡量在拓扑结构中节点的相对影响和相对重要性，反映了与网络剩余部分的连接程度，节点的度等于其与邻居节点的直接链路数)，以增强节点与其他节点联系能力的影响。

文献[6]基于一种QoSMap机制，通过选择高质量保证的物理链路满足虚拟网络的QoS要求，同时基于一跳距离的中继路由节点构建备份路径，最终为虚拟链路映射提供服务质量保证。文献[7]在离线且未考虑节点映射阶段，提出将隐藏跳数(虚拟链路映射到的底层路径经过的中间物理节点)纳入到链路映射阶段。算法将虚拟网络请求分成有特定资源请求和无明确资源请求两类，先处理有特定需求的请求，使得虚拟网络映射过程中剩余网络资源较多。

文献[8]从已有算法平等地对待底层网络的节点和链路资源，实际上这些物理资源中某些资源相比其他的资源更重要，这些关键资源的耗尽会对未来的请求接受率有较大的影响。拓扑感知映射在已有算法的成本函数中引入比例因子，对资源进行区分。引入重优化机制，周期性的重优化机制不适用于实际的网络，文献中提出当有虚拟网络请求被拒绝时执行重优化算法，以有效地均衡负载。文献[9]基于图论和数据结构的理论基础，采取广度优先搜索的原则完成虚拟网络的链路映射，尽可能使得虚拟网络中节点映射到物理网络中，其位置上仍然能够保持在同一个区域内，最终使得BFS-VNE虚拟网络映射算法在相应的虚拟网络映射算法性能参数上优于其他虚拟网络映射算法。同时文献[10-11]中分别描述目前现有的虚拟网络映射模型及K最短路径算法。目前一些虚拟网络映射算法已经开始考虑确保网络正常稳定接纳虚拟网络请求，例如文献[12-15]。

现有的虚拟网络映射算法仅仅考虑单个节点所具有的CPU资源和带宽资源，同时未能从邻居节点及相关节点来全局考虑整个网络拓扑，导致后续的链路映射成功率下降，使得虚拟网络请求的数目变少，网络运营商的网络收益下滑。文中将基于节点多个属性，改进传统的节点映射度量方法，提出基于节点属性的虚拟网络映射方法。

2 虚拟网络映射问题模型

虚拟网络映射问题就是将网络服务提供商需要的虚拟网络请求，映射到满足其计算和链路资源的网络运营商的物理网络中。

2.1 物理网络

2.2 虚拟网络

2.3 虚拟网络映射问题描述

2.4 虚拟网络映射问题的主要性能参数

虚拟网络映射问题最主要解决的是物理网络资源利用效率，希望能够接受更多的虚拟网络请求，同时进一步提高网络基础设施提供商的收益，其有关性能参数定义如下所述。

2.4.1 虚拟网络收益

由某时间段全部映射成功的虚拟网络请求的节点CPU计算资源和链路的带宽资源的总和决定，在某个时刻一个虚拟网络请求所带来的网络收益可以表示为：

(1)

其中，调节系数α∈(0,1)，一般情况取α=0.5；c(nv)表示某一时刻虚拟网络Gv中节点nv的CPU计算资源数值；b(lv)表示虚拟网络链路lv的带宽资源数值。

2.4.2 网络映射开销

虚拟网络映射过程中全部的虚拟网络请求所需要的资源消耗即底层网络为满足虚拟网络中节点、链路资源约束而消耗的物理网络资源，可以表示为：

(2)

2.4.3 物理网络平均收益

定义如下：

(3)

2.4.4 虚拟网络请求接受率

定义如下：

(4)

其中，分子表示某单位时间范围内虚拟网络映射过程中成功接受到虚拟网络请求数量，分母表示某单位时间范围内虚拟网络映射过程中总的虚拟网络请求数量。

3 虚拟网络映射算法描述

本节分析现有虚拟网络映射算法存在的缺点与不足，同时在原有Two-Stage虚拟网络映射算法的基础上实现MNA-VNE虚拟网络映射算法。首先介绍传统虚拟网络映射过程中节点综合资源评估计算，针对现有评估准则中的缺陷进行改进与优化，同时提出新的虚拟网络映射算法。

虚拟网络映射数学模型如图1所示。

图1 虚拟网络映射数学模型

3.1 节点度量准则

传统的虚拟网络映射算法中，节点映射阶段中节点的度量不仅取决于单个节点所具有剩余CPU计算资源，同时也需要考虑网络中剩余链路带宽资源，因此网络中衡量节点资源的计算公式为：

(5)

其中，NR(n)表示节点n的综合资源数值；CPU(n)表示节点n的CPU资源数值；BW(m)表示节点n连接的链路带宽资源之和。

传统虚拟网络映射算法中关于节点资源评估计算存在诸多不足：

(1)节点的计算资源属性。

现有的虚拟网络映射算法中对于节点资源计算评估大多基于网络中的单个节点，未从全局角度考虑网络拓扑结构，不能真实反映出节点映射阶段中物理节点的优先级和重要性。

图2 网络拓扑结构I

从图2可以计算得出，物理节点A与物理节点D的NR值相等，传统的虚拟网络映射算法无法区分节点A和D的优先级，认为节点A的邻居节点具备更多的CPU计算资源，当有虚拟网络请求到达时，虚拟节点应该优先选择物理节点A作为映射的节点。

(2)节点的带宽资源约束。

未能考虑与节点相连接的链路带宽资源相加不能准确地反映该节点在映射过程中的优先级及重要性，同时也会在映射过程中造成链路瓶颈，从而导致后续链路映射无法进行。

从图3中可得出，物理节点A和物理节点B：90*(10+10)=30*(20+20+20)=1 800。由于NR(A)=NR(B)，虚拟网络映射过程中的虚拟节点e将会在节点A与节点B中进行选择。如果选择了节点A在其后的链路映射中，如果要求链路带宽需要大于10，由于节点A的链路带宽不符合节点F的带宽要求，必须重新进行节点映射。

图3 网络拓扑结构II

(3)网络中节点的度。

根据图4可知，当一个虚拟网络请求到达物理网络中，虚拟网络映射过程中需要完成节点映射，物理网络中节点A的相邻节点数目为3，而节点F的相邻节点数目为4，因此虚拟节点g在完成虚拟网络映射过程中，会优先考虑节点F，因为物理网络中节点F周围的节点资源更加丰富，以便后续的链路映射能够更好地完成。

图4 网络拓扑结构III

针对上述不足，首先给出节点映射阶段中的几个概念，然后重新定义一种基于节点多属性的评估公式，以更好地进行虚拟节点的映射。

首先，计算节点的计算资源属性。节点的计算资源值不仅与单个节点自身的CPU计算资源有关，而且还与其邻居节点的CPU计算资源有关。定义如下：

RC(nv)=CPU(nv)+CPU(nv)·

(6)

然后，改进节点的链路带宽资源属性。针对链路带宽资源存在的不足，对其进行重新修改，改进公式如下：

(7)

其中，BW(nv)表示该节点的链路带宽资源值；bw(lv)表示满足该节点的映射链路带宽值；θi为链路带宽的加权系数，根据实际网络具体情况设置。例如网络中链路带宽资源分布在[1,100]之间，考虑链路带宽资源丰富的加权系数越大，[1,10]范围内为0.1，(10,20]范围内为0.2，依次类推。

最后，考虑节点的拓扑属性。充分考虑节点的邻居节点的数目对虚拟网络映射的影响，因此用节点的度表示该节点邻居节点的个数，其定义如下：

N(nv)=Neighbour(nv)

(8)

其中，N(nv)表示网络中节点的度；Neighbour(nv)表示节点的相邻节点的数目。

综上，得出基于节点多属性的评估方法：

NR(nv)=RC(nv)*BW(nv)*N(nv)

(9)

其中，NR(nv)表示该节点的属性综合度量值；RC(nv)表示节点的计算资源值；BW(nv)表示节点的链路带宽资源值；N(nv)表示节点的度。

3.2 节点映射算法步骤

文中提出的MNA-VNE虚拟网络映射算法是在原有两阶段虚拟网络映射算法基础上的改进与优化。下面主要介绍MNA-VNE虚拟网络映射算法的节点映射算法与链路映射算法。

节点映射阶段算法的详细描述及流程如下：

Step1：对到达的每一个虚拟网络请求按照网络收益值从大到小依次排序，其具体公式为：R(Gv,t)=α∑CPU(nv)+(1-α)∑BW(lv)，其中α∈(0,1)，CPU(nv)为虚拟网络请求中节点nv的CPU计算资源值，BW(lv)为该节点nv某条链路带宽，并选取收益值最大的虚拟网络请求进行映射。

Step2：对虚拟网络请求中的每个节点按式9进行计算，然后需要针对物理网络中的物理节点按式9进行计算评估，将物理节点按照NR(ns)数值从大到小依次排序形成一个队列，如果虚拟网络中NR(nv)的最大值小于等于物理网络中节点NR(ns)的最大值，则满足节点映射的条件，将虚拟节点nv映射到物理节点ns上。

Step3：第一个虚拟节点映射成功之后，优先选择刚刚已经完成映射过的物理节点进行映射，如果不满足虚拟网络映射的资源需求，则将虚拟网络中第二个映射节点的资源能力值与该物理节点邻居节点进行比较，如果符合映射要求，则将虚拟节点映射到该物理节点的邻居节点，否则将从Step2的队列中选取最大满足要求的节点，并将其映射到该物理节点上。

Step4：如果在虚拟网络映射中，虚拟网络中节点NR(nv)的最大值大于物理网络中节点NR(ns)的最大值，则该虚拟网络映射无法进行，虚拟网络映射失败。

Step5：重复上述Step1，将之前已经映射的物理网络中物理节点的剩余资源再一次进行计算，并再一次按照从大到小排序，最后直到虚拟网络请求中所有节点映射完成。

3.3 链路映射算法步骤

在3.2节的节点映射算法的基础上，实现虚拟网络中的链路映射。虚拟网络链路映射过程中将继续根据最短路径算法的思想实现虚拟链路的部署，首先排除不满足其虚拟网络带宽资源需求的物理网络链路，在此基础上采用K最短路径算法完成链路映射。

3.4 仿真实验

将MNA-VNE算法与文献[3]和文献[9]中的虚拟网络映射算法进行仿真实验对比及理论分析。其中文献[3]的Greedy-VNE和文献[9]的BFS-VNE均采用式5中的节点资源评估准则，并利用Python Matplotlib绘图，将所得实验数据在虚拟网络请求接受率、网络收益/开销比两个性能指标上进行比较。

3.4.1 实验环境

仿真实验中设置一个中等规模的物理网络，其中包括100个物理节点和大概500条物理链路。为了能够与上述虚拟网络映射算法进行比较与分析，其虚拟网络请求等一系列参数均按照文献[3]中GT-ITM实验中的参数进行设置。同时每次仿真实验运行80 000单位时间，取10次实验结果的平均值(单位时间为ms)。

3.4.2 仿真结果分析

由图5可以得出，这3种虚拟网络映射算法在仿真实验初始阶段的虚拟网络请求接受率比较稳定。但随着仿真时间的不断推移，3种算法的虚拟网络请求接受率都出现了不同程度的下降，其中Greedy-VNE算法下降得最快。主要原因是刚开始实现虚拟网络映射时，由于网络中剩余的CPU计算资源与链路带宽资源较为充裕，物理网络中有足够的物理网络资源能够满足其虚拟网络的资源请求，但随着到达的虚拟网络请求的数量越来越多，物理网络中的可用资源在逐渐减少，最终导致虚拟网络请求接受率逐步下降。由于MNA-VNE算法在节点映射阶段采用全新的度量评估方法，充分考虑网络节点拓扑，同时采用物理节点可重映射的方法，代替部分链路映射，减少了底层物理网络中链路带宽资源的消耗，从而得到更多的虚拟网络请求。因此，当虚拟网络映射过程到最后时，MNA-VNE虚拟网络映射算法相比其他两种算法具有明显的优势。

图5 虚拟网络请求接受率

从图6可以看出，3种算法的网络收益开销比随着仿真时间不断增加，都出现了不同程度的下降。其主要原因是随着虚拟网络请求数目的增多，物理网络可以接受的虚拟网络请求数目越来越少，剩余的物理网络资源可能无法满足虚拟网络请求的资源需要，虚拟网络请求中的链路映射需要消耗更多的时间和资源，导致虚拟网络映射的开销增加。由于MNA-VNE算法采用物理节点可重用，进一步降低物理网络中链路带宽资源的消耗，使得网络资源开销减少，从而接受到更多的虚拟网络请求，增加了底层网络的收益，从而提升了网络收益/开销比。所以从图中的曲线变化走势可以得出，MNA-VNE虚拟网络映射算法在虚拟网络收益/开销比性能参数上优于其他两种虚拟网络映射算法。

图6 虚拟网络收益/开销比

4 结束语

在传统两阶段静态虚拟网络映射算法的基础上，充分考虑网络中节点所具有的多种属性，具体包括节点的资源属性及网络拓扑属性，并且采取物理节点可重用技术，尽可能考虑链路映射过程，提出MNA-VNE虚拟网络映射算法。该算法考虑单个节点的邻居节点的资源属性，提高了后续链路映射的成功率。仿真实验表明，MNA-VNE虚拟网络映射算法在虚拟网络请求接收率、网络收益/开销比等性能参数上更具有优势。