基于VNF组合的服务功能链设计及映射算法

朱国晖,刘 璐,雷兰洁

(西安邮电大学 通信与信息工程学院,西安 710061)

0 概述

软件定义网络(Software Define Network,SDN)[1]和网络功能虚拟化(Network Function Virtualization,NFV)[2-3]技术的产生使得现有网络模型变得更加开放和灵活[4]。NFV可以在传统的专用硬件设备上实现虚拟网络功能(Virtualized Network Function,VNF)[5],并将其在通用设备上运行,提高网络的高效性、灵活性和扩展性,降低运营商对专用设备的依赖[6]。服务功能链(Service Function Chain,SFC)[7-8]通过NFV提供各种网络服务,即SFC由虚拟网络功能根据需求按一定的逻辑顺序组合而成[9]。传统虚拟网络(Virtualized Network,VN)映射[10-12]必须确保不同虚拟节点网络请求被映射到不同的物理节点上,并且节点拥有足够的计算资源,同时,在虚拟链路映射到底层网络路径上时满足其带宽要求。与传统的虚拟网络映射相比,每个SFC可看作由许多连接的VNF组成的线性链。由于多个VNF可共享同一个物理设备以提高物理资源利用率[13],因此可以指定2个(或2个以上)VNF进行组合,且各VNF的功能和资源需求不同。

目前,已有相关文献考虑对虚拟网络功能进行聚合或拆分处理。文献[14]对租户资源需求进行主动拆分,利用更小的资源粒度提高物理资源利用率,但是增加了算法的复杂度。文献[15]提出功能聚合的概念,将相同端节点的服务链组成一个簇,簇中功能相同的2个(或2个以上)节点聚合为一个资源相加的大节点,达到降低虚拟网络功能实例化成本的目的,但是算法未考虑功能聚合后资源需求的增大,在映射时导致请求接受率降低和物理资源碎片化。文献[16]针对所有网络服务的差异性,提出剩余链路带宽资源分配的优化算法,通过给虚拟节点和链路添加权重,设计总资源消耗较低的SFC拓扑。

本文以降低总带宽消耗为优化目标,组合映射VNF节点,提出基于虚拟网络功能组合的服务功能链设计及映射算法A-VNFC。利用整数线性规划(Integer Linear Programming,ILP)模型在小规模物理网络中对总带宽消耗(Total Bandwidth Consumption,TBC)目标函数求最优解,寻找可组合的VNF并利用VNF决策树检查全部组合策略,直至迭代出最小的TBC。在此基础上,通过优化调整SFC拓扑,达到降低TBC的目的。

1 问题描述和模型建立

1.1 问题描述

由于物理服务器支持不同的网络功能,同时服务功能链也允许VNF的多对一映射,因此可将VNF进行组合。然而,在实际情况下,一些VNF由于功能约束或冲突不能进行组合和映射到相同服务器中。另外,在决定是否对不同功能进行组合时,需要权衡以下2个方面:

1)执行VNF组合后可节省的带宽消耗以及其他潜在益处。

2)组合的VNF可能会映射到一个距离其他VNF较远的多功能服务器中,从而导致消耗更多的带宽。

例如,在图1(a)中没有组合v1和v2(功能需求分别为f1和f2),将其分别映射至节点B和节点D中,总带宽需求为:80+60+60+50+50=300 Gb/s。如图1(b)所示,v1和v2组合映射至一个物理节点A上(即仅有节点A可以同时支持f1和f2),但是在物理链路中从节点A到节点C再到节点E需要配置110 Gb/s的带宽来支持从v1和v2到v3之间的流量,导致总带宽消耗450 Gb/s。在执行VNF组合后,总带宽消耗反而大于不执行组合时,由此可见,在设计SFC拓扑的过程中需要判断VNF组合的必要性。

图1 SFC映射过程Fig.1 Mapping process of SFC

1.2 物理网络模型

物理网络模型采用带权重的无向图Gs=(Ns,Ls)表示物理网络。其中,Ns为物理节点集合,Ls为物理链路集合。每个物理节点ns∈Ns的计算能力为R(ns),每个节点支持的功能集合为F(ns)∈Ω,Ω表示所有通用网络功能的集合。一个物理节点可作为单功能服务器提供一个功能,也可作为多功能服务器提供多种网络功能,物理链路ls∈Ls的可用带宽资源表示为bw(ls)。

1.3 网络服务功能链请求

1.4 基于功能组合的SFC设计及映射模型

1.4.1 VNF组合处理

(1)

(2)

1.4.2 SFC映射过程

SFC映射包含节点映射和链路映射2个过程。在节点映射时,SFC中的VNF(或组合后的VNF)映射到相同的物理节点上,其映射过程的数学表达式为MN:Nv→Ns,具体过程如下:

(3)

式(3)需要满足的资源约束条件如下:

(4)

(5)

其中,式(4)代表物理节点可以提供的SFC网络功能需求,式(5)为计算资源能力约束,表示虚拟链路必须映射至可满足其带宽需求的物理节点中。

(6)

2 算法设计

本文在整数线性规划数学模型下,求解SFC拓扑设计与映射问题的最优解,在约束条件中规定组合的节点对可以映射至一个物理节点中,但不允许节点拆分。由于整数线性规划模型适用于小型网络,因此另提出适用于大规模网络的基于节点组合的启发式算法。然后,以降低总带宽消耗为目标,判断节点对组合的必要性,直至所有的节点对检查完成并迭代出目标最小值,最后通过四边形调整算法进一步优化迭代后的SFC拓扑,减少带宽消耗。

2.1 整数线性规划模型

本文使用整数线性规划模型对SFC拓扑设计及映射问题进行精确定义,提出约束条件及优化目标并求得目标函数最优解。ILP模型所用参数及参数释义如表1所示。

表1 ILP模型参数释义Table 1 Parameter interpretation of ILP model

设定目标函数为最小总带宽消耗,公式如下:

(7)

目标函数的约束条件包含3个部分,具体如下:

1)VNF组合约束

(8)

2)VNF映射约束

(9)

(10)

(11)

3)虚拟链路映射约束

(12)

式(8)约束表示如果2个VNF可以组合,则它们可以映射到同一个物理节点,式(9)确保一个虚拟节点至多映射到一个底层节点,不允许VNF分割,式(10)和式(11)分别为计算能力约束和功能约束,式(12)确保虚拟链路可以映射到物理路径中。

2.2 虚拟网络功能组合策略

由问题描述可知,部分VNF组合后并未达到降低带宽的目的。因此,确定VNF组合方式并生成新的SFC拓扑是本文算法的重要步骤。VNF组合的必要条件为满足式(8)所示的组合约束条件,即组合后存在可以承载其映射资源需求的物理节点。图2给出SFC请求和VNF的组合决策树。图2(a)表示SFC拓扑结构,其中,虚线圈出的虚拟节点表示2个节点满足约束条件,可以进行组合并映射至同一物理节点中,每一对可组合的VNF代表一种组合策略。图2(b)表示VNF组合策略决策树,其从端节点开始检查图2(a)中每一种组合策略执行后是否能达到TBC降低的目的,从而构成新的SFC拓扑。其中,& 表示节点组合,| 表示节点不组合,即1& 2表示节点1和节点2组合,1|2表示节点1和节点2不组合。具体算法流程如图3所示。

图2 VNF组合策略Fig.2 Combination strategy of VNF

图3 VNF组合策略流程Fig.3 Procedure of VNF combination strategy

2.3 基于虚拟网络功能组合的SFC映射算法

本文提出基于虚拟网络功能组合的SFC映射算法A-VNFC,在设计VNF组合时,考虑映射在物理网络中的所有VNF和虚拟链路的反馈情况。A-VNFC算法主要分为以下4个步骤:

1)不考虑VNF组合执行映射算法,对SFC请求进行映射,计算TBC并将其作为总带宽消耗的初始最值。

2)对VNF进行组合处理,计算映射组合后SFC拓扑的TBC数值,若总带宽消耗小于初始值,则更新数据,将组合后的TBC作为初始值。

3)重复步骤2)直至所有组合策略检查完毕,迭代出最终TBC。

4)在迭代完成后,对SFC拓扑中的节点执行四边形调整优化算法,进一步降低TBC。

节点组合方法如2.2节所述,在SFC拓扑映射阶段使用文献[17]的NS-NFV算法,该算法在选择物理候选节点时引入节点亲密度[18]属性,亲密度越高,节点之间经过的链路跳数越少,需求带宽也越少。本文在此算法的基础上,使用四边形调整策略优化带宽资源配置,主要优化在一条服务链中的3个连续VNF节点。例如,将任意连续的3个虚拟节点vi-1→vi→vi+1分别映射至物理节点si-1、si和si+1中,若存在物理节点ti对应于VNF节点vi,则满足如下公式:

dis(si-1,ti)+dis(ti,si+1)

dis(si,si+1)

(13)

其中,dis(s,t)表示物理节点s和t之间的带宽资源消耗。若类似的节点ti可以被找到,则将VNF节点vi重新映射至节点ti上,以求得映射的最小带宽消耗。

A-VNFC算法的具体步骤如算法2所示,其输入为一条SFC,最终输出迭代后的总带宽消耗。首先对未进行节点组合处理的SFC请求通过NS算法进行映射处理,并将计算得到的TBC数值作为TBCmin。然后寻找满足约束条件下的n种组合策略,若无则跳转至第9行以降低TBC,若有则跳转至第3行逐一检查n种组合策略是否可以降低TBC,并且重复执行第3行直至检查完所有的组合策略,求出TBCmin值之后跳转至第9行以优化TBC。

算法2A-VNFC算法

输入一条SFC请求r

输出TBCmin

1.使用NS-NFV算法,映射SFC并计算TBCmin数值

2.为SFC请求r寻找n种满足约束的虚拟节点组合策略,若存在跳转至第3步,若无VNF可组合跳转至第9步

3.对组合策略i,即组合后的SFC子拓扑进行拓扑映射并计算TBC(i)

4.If TBC(i)

5.Else TBC(i)>TBC,则组合策略i失败;

6.i++;

7.If i<=n;跳转至第3步

8.Else映射结束

9.将虚拟节点存入集合V={v1,v2…,vm},物理节点存入集合S={s1,s2,…,sm}

10.令x=m-1

11.while x>1时执行

12.for vi的任意底层节点tido

13.if dis(si-1,ti)+dis(ti,si+1)

14.映射vi至底层节点ti,更新集合V和集合S

15.end if;end for

16.令x=x-1;end while

17.根据式(7)计算其TBCmin值

18.输出TBCmin

3 仿真结果与分析

仿真部分主要选择TBC性能与本文相似的2种算法[19]进行对比,即关键子拓扑映射反馈(Close-loop with Critical Mapping Feedback,CCMF)算法和最大组合开环(Open-loop with Maximum Combination,OMC)算法,这2种算法均使用VNF组合策略,却并未判断组合必要性。本文以总带宽消耗TBC作为算法性能评价指标,验证A-VNFC算法的优越性。

3.1 仿真环境

本文的仿真环境与比较算法的仿真环境基本一致。实验使用JAVA语言通过eclipse工具在64位的Windows7操作系统平台下进行仿真评估。首先用小型网络实现ILP模型和启发式算法的仿真,然后在大型网络中评估本文算法性能。

本文采用GT-ITM[20]工具生成底层物理网络和SFC拓扑。小型物理网络由6个服务器通过8条物理链路相互连接,其中3个服务器被随机分配为多功能服务器,剩余的则为单功能服务器。每个单功能服务器提供一种网络功能,多功能服务器提供3种网络功能,其功能从6种网络功能中随机分配。大型物理网络由24个服务器通过43条物理链路相互连接，其中10个服务器被随机分配为多功能服务器，其功能从8种网络功能种随机分配。每个服务器随机分配1 500 unit的计算资源并且每条物理链路分配足够的带宽资源。另外,随机生成30条SFC请求,每条请求由2个～6个VNF组成,每个VNF请求计算需求小于50 unit并且每条虚拟链路带宽需求小于30 Gb/s。VNF组合率设置为0.3,表示所有VNF的30%可以被随机选择与另一个VNF组合。为保证仿真的可靠性,对于以上参数设置进行5次实验取平均值。

3.2 仿真结果

由于ILP模型的计算复杂度较高,因此先在6节点的网络中进行仿真,结果如图4所示。在不同数量的SFC请求下评估ILP算法、A-VNFC算法、OMC算法和CCMF算法的TBC性能。从图4可以看出,本文算法可根据SFC映射反馈来决定VNF是否组合构成新的的拓扑,并在映射算法中对节点和链路进行调整以达到最小带宽,因此,其TBC低于OMC算法和CCMF算法,并且非常接近ILP算法的最优结果。

图4 6节点网络中的TBC性能Fig.4 TBC performance in a 6-node network

根据SFC请求数量的增加观察3种算法的TBC变化,结果如图5(a)所示。可以看出,3种算法的TBC均随SFC请求数量的增加而增加,但A-VNFC算法的增幅明显低于OMC算法和CCMF算法。这是因为A-VNFC算法考虑映射在底层网络的节点及链路反馈情况进行VNF组合,减少了带宽消耗。图5(b)给出SFC请求的大小对TBC的影响。可以看出,随着SFC请求变大,TBC也明显增加,但是TBC的增加速度在SFC请求达到6以后变缓慢。这是因为随着SFC大小的增加,会有更多的VNF可进行组合,因此节省了带宽消耗。

图5 SFC请求对TBC性能的影响Fig.5 Impact of SFC request on TBC performance

图6给出VNF组合概率对TBC性能的影响。从图6可以看出,随着组合概率的增加,TBC的数值降低,且A-VNFC算法的降幅较其他2种算法更大,说明A-VNFC算法可以根据映射反馈为VNF组合做出最合适的选择。

图6 VNF组合概率对TBC性能的影响Fig.6 Influence of VNF combination probability on TBCperformance

图7给出多功能服务器数量和服务器上可提供功能数量对TBC的影响。从图7(a)可以看出,TBC随多功能服务器数量的增加而呈下降趋势,这是因为多功能服务器越多,供给VNF组合的概率就越大。在图7(b)中,TBC随服务器提供的功能数量的增加而增加,原理同上,都是因为服务器提供给VNF组合的概率增加。

图7 物理服务器对TBC性能的影响Fig.7 Impact of physical servers on TBC performance

4 结束语

本文从网络功能组合的角度研究NFV中的服务功能链拓扑设计及映射,提出基于VNF组合的服务功能链设计及映射算法。利用物理网络中多功能物理服务器可承载多个不同类型VNF的特性,将服务链中的两个VNF映射到同一个物理节点,以减少实例化成本和总带宽消耗。仿真结果表明,该算法可有效降低不同场景下的物理网络总带宽消耗。下一步将研究多条服务功能链请求到达时的最优拓扑设计和映射,并在NFV仿真环境下进行更大规模的应用与验证。