一种基于业务感知和可调节跳数的虚拟化层构建算法

马 丁， 费 选， 慕小武

(1.河南工业大学 人工智能与大数据学院，河南 郑州 450001； 2.郑州大学 数学与统计学院，河南 郑州 450001)

0 引言

近年来，随着网络流量的迅速增长，多样化应用的不断涌现，传统中间盒(middlebox)的设备架构已经难以满足现有的需求，网络功能虚拟化(network function virtualization, NFV)正是在此背景下应运而生[1-2]。VNF(virtual network function)将网络功能与物理设备解耦，然后将网络功能软件化，抽象为虚拟网络功能。VNF可以部署在通用x86平台上，极大增加了核心网络的灵活性和可扩展性，降低了网络企业的硬件投资成本和运维成本[3-4]。

为了满足业务的需求，网络数据流从源端系统到目的端系统通常需要以特定的顺序依次经过一系列VNFs。其中，通过特定顺序链接起来的VNFs逻辑序列被称为服务功能链(service function chain, SFC)。目前，针对SFC映射的研究较多集中在5G、互联网、光网络等多样化网络场景中VNF实例(virtual network function instance，VNFI)的部署与映射。其中，Sahhaf等[5]将高层VNF分解为多个子图，通过分组和建立集群的方式进行映射，提高了资源利用率，降低了开销。胡宇翔等[6]针对已有研究未考虑具有高性能数据处理需求的服务链VNF部署问题，提出一种支持硬件加速的VNF部署模型。Ye等[7]基于5G网络背景，提出了一种面向多路数据流SFC映射的端到端数据包时延模型。Cao等[8]针对虚拟网服务提供中的资源利用率问题，提出了一种动态VNF的映射和调度方法。Pei等[9]针对云系统地理位置分散的特点，对动态VNF放置以及SFC的映射问题进行了研究。Abujoda等[10]提出了一个分布式的SFC映射框架，使不同提供商既能够合作完成映射，又能够维持各自的隐私和自治。Hu等[11]从网络安全的角度出发，通过SFC的柔性组合，构建安全保证的端到端路径。Fu等[12]针对动态、复杂的物联网环境，提出一种基于深度学习方法的SFC映射机制。Sun等[13]针对能量感知的在线SFC映射方法展开了研究。

然而，上述研究均未涉及中间虚拟化层的构建细节。本文尝试对NFV环境下的虚拟化层构建方法进行研究，探究面向业务感知的节点集合构建方法和高性能低开销的链路集合构建方法。并通过分层图算法对所构建的虚拟化层的服务提供能力进行了模拟仿真。

1 问题模型与描述

1.1 虚拟化层

网络拓扑的抽象对于有效地进行SFC映射是至关重要的[10]。例如，网络功能提供商(network function provider，NFP)的信息发布策略是不同的：互联网服务提供商(internet service provider,ISP)通常发布简化的PoP(point of pre-sence)级别的拓扑[14]；云服务提供商(如亚马逊)可以跨越不同区域广告其所能够提供的资源。对网络拓扑的抽象可以隐藏NFPs认为是机密的信息。

虚拟化层(virtualization layer，VL)是对底层物理网络拓扑的抽象，是介于物理网络与SFC之间的中间层，如图1所示。建立VL需要对SFC请求的业务类型进行感知，对网络拓扑进行抽象，构建业务一致性视图，隐藏业务无关细节，隐藏NFPs的隐私信息。

SFC请求在虚拟化层进行映射的过程分为两个阶段，如图1所示，其中，彩色的椭圆表示NFP部署的VNF，白色圆圈表示PoP。

(1)分析SFC请求的业务类型，选择匹配该类业务的VL；

(2)根据SFC请求，选择SFC映射算法在VL上进行VNF和逻辑链路的映射，构建源端系统到目的端系统的服务路径，如图1中的红色箭头线段序列所示。

图1 基于虚拟化层的SFC映射Figure 1 Virtualization layer based SFC mapping

1.2 问题描述

1.2.1 物理网络

物理网络拓扑可以用带权无向图表示，标记为G=(N,L)，其中N和L分别表示物理网络节点和链路的集合。VNFI可以部署在物理网络的任意功能节点上。功能节点n(n∈N)的CPU容量(CPU capacity) 标记为C(n)；该节点上部署的VNFI集合标记为S(n)={Sk|节点n部署有VNFISk}，如果S(n)≠Ø，该节点为功能节点，否则为交换节点，只进行数据包的转发。物理链路l(l∈L)的带宽标记为B(l)。表示物理网络无环路径的集合，ni,nj∈N之间的无环路径集合标记为(ni,nj)，P∈表示物理网络中的一条无环路径，H(P)表示路径P的跳数(hop count)，即长度。

1.2.2 服务功能链请求

服务功能链请求(service function chain request，SFCR)可以使用带权有向图表示，标记为GR=(NR,LR)，其中，NR和LR分别表示逻辑节点和逻辑链路的集合。逻辑节点nR(nR∈NR)的VNF需求标记为S(nR)，CPU资源需求标记为μ(S(nR))，逻辑链路lR(lR∈LR)的带宽需求标记为μ(lR)。

1.2.3 虚拟化层

VL的拓扑也可以用带权无向图表示，标记为GV=(NV,LV)，其中NV和LV分别表示VL的节点集合和链路集合。

VL的构建问题定义：根据SFCR中的VNF需求，建立从GV到G的子集Gf=(Nf,f) 的映射：

(1)

整个构建过程包括节点集合NV的构建与链路集合LV的构建。

(1)节点集合构建。首先需要分析业务的VNF需求，将已部署相应VNF的功能节点集合Nf作为VL的候选节点集合，建立物理功能节点与VL节点之间的映射：

(2)

如果M′N(nV)=M′N(mV), 当且仅当nV=mV,即不同的VL节点不能由相同的功能节点映射。

同时建立NV与Nf之间的逆映射：

(3)

如果M′N(n)=M′N(m), 当且仅当n=m, 即每个功能节点只能托管一个VL节点，即NV和Nf是一对一映射。

映射完成之后，VL的节点集合构建完成。

(2)链路集合构建。VL节点之间的链路构建可以采用节点间最短路径的构建方法，即计算∀nV,mV∈NV,MN(nV)与MN(mV)之间的最短路径，然后再将VL链路(nV,mV)映射其上，建立链路映射ML：

ML(nV,mV)⊆f(MN(nV)，MN(mV))。

(4)

映射完成之后，VL的链路集合构建完成。

(3)构建开销。VL的构建开销C(GV)包括构建节点集合NV所需要的CPU资源开销和构建链路集合所需要的带宽资源开销，定义如下：

(5)

式中：C(nV)是映射VL节点所分配的CPU资源；B(lV)是映射VL链路所分配的带宽资源。

VL构建的目标是在保证SFC承载能力的基础上最小化构建开销C(GV)。

2 虚拟化层构建算法

在1.2节描述问题的同时给出了构建节点集合与链路集合的基本思路。首先在节点映射时考虑了SFCR的VNF需求，因此映射完毕后所有与该类业务无关的VNF不再出现在VL中，实现了业务感知。但是，在链路映射后构建出的VL拓扑是完全图，冗余链路过多，由式(5)可知，链路数量越多，带宽开销越大，因此必须要进行冗余链路的识别与消除。而链路数量与VL的服务提供能力是成正比的，因此在进一步优化链路数量、减少带宽开销的同时，需要保证SFC请求的映射性能。

2.1 定义冗余链路

在该链路所映射的物理路径中，至少存在一条物理链路，使该物理链路的两个顶点逆映射后为VL的已有顶点。

∀nV,mV∈NV,MN(nV)与MN(mV)之间的最短路径记为Pshortest(MN(nV),MN(mV))，(nV,mV)为冗余链路，需要同时满足条件：

(1)H(Pshortest(MN(nV),MN(mV)))>1；

(2)∀(nij,nij+1)∈Pshortest(MN(nV),MN(mV))，∃nix,nix+1,M′N(nix),M′N(nix+1) ∈NV。

2.2 面向业务感知和可调节跳数的构建算法

本文提出一种可调节跳数的非冗余链路映射方法(non-redundant link mapping method with adjustable hop count，NRLMAH))。首先，在映射链路时，选择相应功能节点之间有效路径长度在跳数约束内且无冗余的链路。其次，由低至高调整候选路径的跳数约束，随着跳数增加，VL的链路数量增加，服务提供能力增加，开销也随之增加，当跳数约束达到阈值时，继续增加跳数，开销继续增加，但服务提供能力趋于稳定。

整合面向业务感知的节点映射方法和NRLMAH，提出一种面向业务感知和可调节跳数的VL构建算法(visualization layer constructing algorithm based on VNF-aware and adjustable hop count, VLC-VAAH)如下。

算法1VLC-VAAH。

输入：物理网络拓扑G=(N,L)，SFCRGR=(NR,LR)，跳数约束hop；

输出：VL拓扑GV=(NV,LV)，映射结果MN和ML。

①foralln∈Ndo

②if节点n部署有SFCR所需的VNFI

③ 创建节点nV∈NV；

④ 创建节点nV与节点n之间的映射

MN(nV)及逆映射M′N(n)；

⑤elseif

⑥ 将n纳入非候选功能节点集合Q；

⑦endif

⑧endfor//节点映射结束

⑨forallnV∈NV

⑩ 以MN(nV)为根，不断添加节点n，建立高度为hop+1的BFS树T(MN(nV))。为确保无冗余链路，需进行以下处理：

当n∉Q&&M′N(n)≠nV，将n添加为树的叶子节点；如果n∈Q，则以n为子树的根继续生成BFS树；

ML(nV,M′N(nleaf))={P(MN(nV),nleaf)}；

在算法VLC-VAAH中，VL的节点数量为|NV|，在物理网络构建BFS树的时间复杂度为O(|N|+|L|)，因此VLC-VAAH算法的时间复杂度为O(|NV|(|N|+|L|))。

3 实验及分析

本文使用所提出的虚拟化层构建算法建立跳数约束为2、3、4、5的虚拟服务层，并在其上分别运行分层图算法[15]映射SFC请求，满足最小化时延的需求。通过服务请求接受率、收益、开销、收益开销比[16]等性能指标对虚拟层服务提供能力进行仿真实验研究。

3.1 仿真环境设置

物理网络拓扑利用GT-ITM随机生成，包含50个节点和约123条链路。节点CPU容量和链路带宽容量在[2 500,5 000]区间均匀分布，每个节点可以部署1～5个VNF。根据文献[5]，将VNF的执行时延和链路传输时延的设定在[1,10]区间，VL节点与链路的资源分配系数设定为0.2，因此VL的节点CPU容量和链路带宽容量在[50,100]区间均匀分布。

SFC请求需求的VNF数量设定为3，类型随机选择，其中每个VNF的计算资源需求在[1,25]区间均匀分布，VNF之间的链路带宽需求在[1,50]区间均匀分布。SFC请求的到达时间服从泊松分布，平均100个时间单位内到达5个，每个请求的服务时间服从平均1 000个时间单位的指数分布。每次仿真的时间约为50 000个时间单位，从0开始每间隔2 000个时间单位采集一次数据。

3.2 仿真结果分析

图2表明，当跳数约束等于3、4、5时，平均请求接受率较为接近，但与跳数约束为2相比，至少提高了15%。图3和图4表明，当跳数约束等于3、4、5时，长期平均收益和开销也非常接近，比跳数为2时分别至少提高33%和19%。进一步从图5中可以看出，与跳数为2时相比，跳数等于3、4、5时的长期收益开销比分别提高了12%、13.5%和15.5%。分析其原因，当跳数为2时，链路数量过少，难以建立有效的链路映射，请求接受率较低，收益开销比较低。当跳数约束提高为3时，链路数量增加，可映射路径选择增多，服务提供能力提升，各项指标均得到大幅提升。当继续增加跳数约束值时，VL构建开销持续增加，与跳数为3时相比，跳数为4和5的构建开销分别增加约27%和52%，如表1所示。然而性能提升却趋于平缓，例如，与跳数为3时相比，跳数为4和5的平均请求接受率，分别增加约0.7%和1.2%，其他指标的增加与之类似。仿真结果表明，VLC-VAAH算法是有效的，能够在特定规模的物理网络上构建性价比最优的VL。

图2 SFC平均请求接受率比较Figure 2 Comparison of average request acceptance ratio

图3 长期平均收益比较Figure 3 Comparison of long-term average revenue

图4 长期平均开销比较Figure 4 Comparison of long-term average cost

图5 长期平均收益开销比比较Figure 5 Comparison of long-term revenue/cost ratio

表1 VL构建开销对比Table 1 Comparison of cost of VL

4 结论

(1)在物理网络与SFC请求之间构建VL可以生成业务一致性视图，屏蔽底层无关细节，隐藏NFPs的隐私信息。

(2)可调节跳数的非冗余链路映射方法能够有效地消除VL上的冗余链路，同时能够通过跳数的调节有效地均衡VL的构建开销与服务提供能力。

(3)所提出VLC-VAAH算法是有效的，能够在特定规模的物理网络上构建性价比最优的VL，所构建的VL能够有效地进行SFC映射。

(4)如何针对5G网络的不同应用场景构建特定的VL，并进行跨域的资源编排是下一阶段研究的问题。