用户QoS与网络资源感知的服务功能链部署方法

崔雅君，李 华，阮宏玮，许 彤，王显荣

(内蒙古大学 计算机学院，呼和浩特 010020)

1 引 言

随着计算机网络技术和云应用技术的发展，运营商希望可以自动化的为客户提供更多的服务，从各类资源的供给到资源的弹性伸缩，提高运维的自动化，并支撑业务生态系统的进化.网络功能虚拟化(NFV)与软件定义网络(SDN)的协同应用为云数据中心运营商提供了自动化管理云数据中心存储、计算资源的工具，实现了对网络服务的灵活管理和高效利用.服务提供商为了满足用户的动态需求，选择将虚拟服务功能按照一定逻辑顺序进行合理链接并部署在物理网络上提供完整的端到端服务.这种将网络中两个或多个服务功能(SF)互连，为应用驱动的网络提供支持的技术被称为服务功能链(SFC).SFC适应各种网络场景，如：电信运营商网络(TSP)、物理网络功能与虚拟网络功能共存的混合NFV网络以及云网络等为用户提供指定的网络服务，处理用户请求产生的大量流量[1].

尽管SFC使得服务模式变得更加灵活和经济，目前也有一些关于SFC部署方法的研究，但多从如何降低运营商的运营成本及资源利用率等考虑问题，忽略了对用户QoS体验的考虑，或者对用户QoS维度的考虑较为单一，导致用户的体验并不理想.在目前服务市场竞争非常激烈的情形下，可能导致用户的流失.因此需要深入的分析SFC的部署问题及其现有解决方法，从更多维度考虑用户的QoS需求研究SFC的部署方法.

2 相关工作

云计算及网络功能虚拟化的快速发展，使得传统以终端为中心的网络服务模型正在向以数据为中心的动态网络服务模型以及以云计算为核心的边缘计算服务模型转变.为了实现服务部署的灵活性，运行商开始基于虚拟网络功能进行服务功能链的部署.因此，SFC部署问题已经成为近年来国内外的研究热点.SFC部署问题可概述为在网络中寻找服务的最佳放置位置，也即服务如何映射到物理网络的可用资源上.可利用优化理论将其规约为多约束条件下求解SFC优化部署的问题，此类问题现已被证明是NP-Hard问题[2]，也即在NP≠P的条件下，如果要使目标函数在多项式时间内获得可行解，需要通过应用精确、启发式或元启发式算法进行解决.但是在采用精确算法方面，Moen等将服务功能的资源映射建模成了整数线性规划问题(ILP)进行求解[3]，但该方法仅在网络规模较小时适用，在大规模网络中可能会产生组合爆炸带来较高的运行成本.因而目前研究提出的算法大多是启发式或元启发式的.如文献[4]提出了一种可扩展的启发式方法CoordVNF，该方法能够在合理的运行时间内解决服务的放置及资源分配问题，同时该方法可扩展应用到较大规模的网络场景中.但是这些研究仅考虑了运营商的运营成本，未考虑提供给用户的服务质量问题，这可能会使提供的服务不能满足用户服务需求从而影响服务链的部署.还有一些研究虽考虑了用户体验，但是未能考虑用户对服务更多维度的QoS需求.如：文献[5，6]考虑了时延问题，将服务链映射问题建模成了整数线性规划(ILP)问题进行求解，同时作者还提出了一种基于Viterbi的启发式算法处理ILP的复杂性.文献[7]研究了SFC部署对用户服务水平协议(SLA)的影响，提出了一种启发式算法使得部署的SFC能耗及负载最小，也即通过降低服务器能耗保证用户体验.文献[8]提出了一种基于强化学习的服务链映射算法，解决了动态场景下服务功能与资源的映射问题，该算法有效降低了业务的平均传输时延，提升了系统的负载均衡性能.文献[9]考虑了SFC部署对时延敏感型用户服务体验的影响，提出了一种以最小化SFC延迟为目标的启发式方法来部署SFC.文献[10]以最小化运营商代价为目标，考虑了服务时延以及资源可用性.文献[11]提出了一种MILP模型和一种启发式算法BACON，通过最小化服务功能间的通信延迟来提高QoS.文献[12]构建了一个虚拟功能干扰度评估模型，提出了考虑虚拟功能间干扰的部署算法，将求解干扰度最小化问题转换为多目标优化问题并利用模拟退火算法进行求解，提高了服务链的执行性能.文献[13]在部署虚拟网络功能时考虑了提供给用户的服务质量问题，并采用启发式的贪心算法求解.

为了更好的比较现有方法，表1按解决方法，优化目标，评价指标以及是否考虑QoS等条目对现有工作进行了总结.

表1 现有SFC部署方法

从上述工作看SFC的部署策略大多考虑了运营商的运营成本以及节点资源利用率等问题，但对提供给用户服务质量的考量较为单一，如：仅考虑了服务时延.但事实上，QoS是各种存在服务供需关系的场合中普遍存在的概念，用于评估服务方满足客户服务需求的能力[14].在目前市场竞争如此激烈的情况下，运营商要保证在市场中的竞争力，其提供的服务必须满足用户需求，否则此次部署的服务就是失败的.因此，本文在研究SFC部署时要着重解决的关键问题就是保证运营商提供的服务是满足用户QoS要求的.相比于目前SFC部署工作中不考虑或仅考虑服务时延的单维度的QoS参数，本文进一步考虑了影响用户体验的服务时延、服务可用性、链路丢包及链路拥塞多个维度的QoS参数，并且探索了新的方法旨在保证用户多维度需求的同时使运营商的成本代价最小.

3 问题描述

软件定义网络和网络功能虚拟化的不断发展，使得运营商对数据中心的网络管理更加的高效和灵活.SFC是云数据中心构建基于网络的安全高效服务的基础关键步骤之一，在SDN网络中，控制器需要根据用户的需求制定部署策略来构建服务链，同时部署服务链上每个节点的业务逻辑.

3.1 部署模型

运营商及服务商多通过SLA体现为用户提供的服务质量.本文的服务链部署目标是在网络资源有限的情况下，运营商仍能保证用户与之签订的SLA中规定的QoS，同时使运营商的代价最低，涉及的QoS参数主要包括服务时延及服务可用性等网络性能指标.

为了更加直观的描述待解决的问题，本文给出如图1所示的部署模型，示意部署工作的输入及输出.

图1 部署模型

图1中的用户QoS需求由SLA中规定的关键性指标表示，如：在高可用网络中服务时延不得超过150ms，包的丢失率小于1%等.SLA是用于评价SFC成功部署的关键指标，若不满足约定，则部署失败.网络资源约束表示当前部署SFC的网络拓扑环境，由有限的节点资源、链路资源、带宽资源等体现.

SFC构建策略根据业务需求及应用场景组合虚拟网络功能，形成逻辑上的服务功能链，如图2所示.SFC部署策略基于SDN控制器获取全局网络视图，根据已得到的逻辑服务链路、网络资源约束和用户QoS需求为每个虚拟网络功能找到在物理链路中最佳的放置位置，得到一条实例化的服务路径.

图2 服务链的构建

实例化的服务链为视频会议、网络购物等利用网络作为数据传输平台的业务提供服务，运营商需要基于业务特点与用户签订协议以提供满足用户要求的服务.如视频会议以及视频点播等业务需要满足用户对低延迟和低抖动等传输性能的需求.但是网络规模以及用户数量的不断增长降低了SFC部署的成功率，在资源总量能够满足需求的情况下，究其原因是现有网络不考虑用户的QoS需求，仅提供“尽力而为”的服务，考虑的服务质量较少，导致了服务可用性差，SFC部署的失败率增高.如果在部署SFC时，先满足用户QoS需求再考虑运营商部署成本的最小化将会大大提高SFC部署的成功率.

一般而言用户服务质量通常用丢包率、延迟和延迟抖动3个参数来衡量，只有有效地控制这3个参数，才能够为用户提供优质的QoS[15].由此，本文将SFC部署中要解决的关键问题定义为在资源受限的网络环境中尽可能多的部署满足用户多维度QoS需求的服务链路并且使运营商的部署代价最低.

3.2 形式化描述

为了对本文提出的SFC部署问题进行求解，需要进一步解释说明部署模型中涉及的相关定义，下面给出网络资源和用户QoS需求的形式化描述.

3.2.1 网络资源的形式化描述

现实中云数据中心的资源是有限的且是动态变化的，当前网络环境中资源的使用情况对SFC部署的成功率有很大影响.基于此，本文对使用的物理网络资源情况做了以下描述：

假设构建SFC所需的网络功能集为S=，其中SFi表示第i个服务功能，1<=i<=n，n表示请求的服务功能数量.将一系列虚拟服务功能组合成的SFC映射到物理网络中为用户提供服务，也即SFC的服务路径SFCpath描述为：SF1→SF2→…→SFn.

P=<，S>表示从源节点Ns到目的节点Nt的流量必须经过S描述的服务功能序列.在此路径中未部署服务的节点仅起到转发数据的作用.

文中涉及的主要参数及定义如表2所示.

表2 参数及意义

本文的主要目标是满足用户QoS需求的同时，网络资源消耗最小.目标函数如式(1)所示.

Min(Rcost)

(1)

本文SFC的部署需要遵守的网络资源约束由式(2)-式(4)表示.

ΣCsfi≤TCj

(2)

ΣBsfi≤TBj

(3)

ΣMsfi≤TMj

(4)

式(2)-式(4)表示需要遵守的网络资源约束，即当前在节点j部署的服务所需的计算资源、存储资源以及带宽资源不能超过节点j现有的物理资源.

假设节点j的可用程度由SFAvailj表示，它由节点j的物理资源使用情况决定，也即要求节点j现有的计算资源、存储资源和带宽资源量满足当前服务的资源需求.在本文中表示为所需资源与现有资源比值的乘积，计算方法如式(5)所示.

(5)

其中任意一个子项比值小于1时，令子项的值为1，否则为0.

服务链路的可用程度由每个节点的可用程度共同决定，计算方法如式(6)所示.

(6)

本文将目标函数定义为最小化的网络资源消耗，其求解的关键前提之一是满足底层资源约束.上文已对此进行了具体的定义，接下来将对求解的另一前提进行形式化描述.

3.2.2 用户QoS需求的形式化描述

QoS于业务应用而言代表用户对网络服务的满意程度，于网络而言代表运营商向用户提供的服务参数指标，因此本文将SLA中大多数用户较为关心的服务时延及服务可用性等QoS参数作为成功部署的关键评价指标，其中服务可用性在本文中描述为节点资源的可用性.服务的处理时间与当前节点的可用程度有关，假设服务在理想状态下的处理时延为DSF，本文根据节点的可用程度定义SFi在节点j上的处理时延为D(Nsfi，j)，计算方法如式(7)所示.

(7)

当SFAvailj≠0时，SFi在节点j上的处理时延D(Nsfi，j)被描述为服务在理想状态下的处理时延DSF与节点可用程度SFAvailj的乘积.当SFAvailj=0时，即节点j不可用时，SFi在节点j上的处理时延D(Nsfi，j)是无穷大的.

假设服务链路的时延开销为DSFC，包括SF间传输时延以及SF的处理时延，计算方法如式(8)所示.

DSFC=D((Nsfi，p)，(Nsfi+1，k))+D(Nsfi，j)

(8)

其中D((Nsfi，p)，(Nsfi+1，k))表示承载SFi的节点p到承载SFi+1的节点k之间的传输时延.

为了满足SLA，链路中总的时延开销不能超过SLA中规定的时延QDSFC，如式(9)所示.

(9)

数据传输过程中，若数据无法被及时转发出去会造成转发设备的缓冲过载而造成网络传输性能下降的情况.当网络发生拥塞时，通常会导致链路的丢包率上升，时延增加，吞吐量下降[16].由此可见网络拥塞会影响当前链路的吞吐量，同时也是衡量链路负载性能的重要指标.

式(10)定义了链路的拥塞情况，用于衡量模型的负载均衡度.

(10)

式(11)定义了当前节点j的缓存.式(12)定义了当前路径的丢包情况.链路中丢包率不能超过SLA中规定的丢包率QLRSFC，如式(13)所示.

Ncachej=Msfj-Msri

(11)

(12)

LR≤QLRSFC

(13)

本文将用户的QoS需求刻画为用户对服务时延、服务可用程度和链路丢包率的需求.同时为保证网络服务的传输性能进一步提高服务质量还考虑了链路的拥塞情况.相比于目前的研究工作，本文从更多维度考虑影响SFC部署成功率的因素.

4 算法设计

SFC的部署问题是一个多目标组合优化求最优解的问题.目前此类问题通常采用启发式或者元启发式方法进行求解，但是启发式方法可能会陷入与真实最优解相差很大的局部最优中[1]，也即可行解与最优解的偏离程度无法被预计.而元启发式解决方法可以在合理的时间内脱离局部最优，提高解的质量.目前用到的元启发式解决方法有遗传算法，模拟退火算法等.

4.1 算法的考虑

模拟退火算法(SA)模仿固体退火的过程[17]，迭代自适应的寻找解，多用来求解多目标优化问题中的最小值问题，其求解方法简单通用，易于加入约束条件，编写程序简单.更重要的是，模拟退火算法能以一定的概率接收相较于当前目标函数值较差的解[18]，但是这个概率会随着时间的推移而降低(逐渐降低才能趋向稳定得到终解)，也即理论上经过足够长的时间后此算法可跳出局部陷阱从而收敛到全局最优解.但是也带来了一个矛盾：解的质量与求解时间之间的矛盾.由于网络环境是动态变化且规模不断增大的，因此单纯的使用模拟退火算法求解本文提出的问题，此矛盾将更为突出.

为了在不增加求解时间的同时提高解的质量，需要反复进行迭代运算，也即在有限的时间内求解目标函数.换言之，当问题的规模不可避免地增大时，能否能得到最优解取决于影响迭代次数的控制参数Δt的设定，因此，参数设定成了模拟退火算法应用中的一个关键环节.

禁忌搜索算法(TS)模仿人类的记忆，通过记忆能力指导搜索过程，对已搜索的局部最优解进行标记，避免了搜索中的迂回、重复，并且在搜索过程中可以接受劣解从而增强获取全局最优解的概率[19].但是禁忌搜索算法对于初始解的依赖性很强，一个好的初始解可使禁忌搜索算法在解空间中搜索到更好的解，而一个差的初始解则会降低禁忌搜索算法的收敛速度，搜索到的解也相对较差.为了更加直观的分析两种算法，表3从5个维度对两种算法进行了归纳总结.

表3 SA与TS算法对比

综上所述，模拟退火算法和禁忌搜索算法各有优缺点，对于本文研究的在资源约束与用户QoS约束下部署SFC的问题，虽然应用这两种算法都可以解决，但是单一使用某一算法存在依赖于控制迭代的参数或者依赖于初始解的问题，所以如果想取得更好的优化效果和更高的优化效率，需要将两种算法相结合.因此，本文利用模拟退火算法与禁忌搜索算法的优点，提出了一种模拟退火算法与禁忌搜索算法相结合的算法求解SFC部署问题，用禁忌搜索的记忆功能降低因模拟退火对参数的强依赖带来的无法收敛到全局最优的概率.

4.2 算法描述

本文的问题是在既考虑用户QoS需求约束又考虑网络资源约束下寻找目标函数最优值，其求解过程需要两个核心功能，一是找到一个满足条件的较好的初始解，也即可行的解(算法2描述了对解可行性的判断)，二是需要不断对解寻优以期得到全局最优解.本文设计的SA-TS算法如算法1所示.

算法1.SA-TS算法

输入：网络拓扑G=(N，L)，服务请求S;

输出：最优路径SFCpath，链路代价Rcost(SFCpath);

1.while不满足终止条件

2. 随机产生一个初始解SFCpath0，计算其物理资源消耗Rcost(SFCpath0);

3. 构造新解SFCpathnew，计算Rcost(SFCpathnew);

4.ifRcost(SFCpathnew)>Rcost(SFCpath0)

5. 以概率p设置SFCpathnew=SFCpath0;//以概率p接受劣解

6.endif

7.endwhile

8.ifSFCpath0满足可行性//调用算法1判断SFCpath0的可行性

9. 计算物理资源消耗Rcost(SFCpath0);

10.else

11. 跳转到步骤2 // 不满足可行性，重新随机初始解

12.endif

13.SFCcurrent=SFCpath0;//初始化当前解SFCcurrent等于SFCpath0

14.SFCpath=SFCpath0;//初始化最优解SFCpath等于SFCpath0

15.Rcost(SFCpath)=Rcost(SFCpath0);//初始化最小消耗Rcost(SFCpath)等于Rcost(SFCpath0)

16.在SFCcurrent邻域内构建包含M个互不相同的候选解SFCtest1…SFCtestm的集合candi;

17.计算候选解集合candi中每个候选解的物理资源消耗Rcost(SFCtest1) …Rcost(SFCtestm)，并存入矩阵FitR;

18.将FitR按资源消耗总值排序，得到最小值MinFitR，及其路径SFCtemp;

19.ifMinFitR

20.Rcost(SFCpath)=MinFitR;

21.SFCpath=SFCtemp;//令最优解作为当前解

22.SFCcurrent=SFCtemp;//更新截止目前的最优解

23. 更新禁忌表中各禁忌对象长度;

24.Tslist(SFCtemp)=L;//将候选解加入禁忌表，设置禁忌长度为L

25.else//候选解的值不如当前

26.ifTslist(SFCtemp)==0

27.SFCcurrent=SFCtemp;//解禁

28. 更新禁忌表中各禁忌对象长度;

29.endif

30.Tslist(SFCtemp)=L;//将候选解加入禁忌表，设置禁忌长度为L

31.endif

32.returnSFCpath，Rcost(SFCpath)//返回最优路径，及最优路径的链路代价;

算法2.解的可行性判断

输入：TCi，TMi，TBi，Csfi，Msfi，Bsfi，QDSFC，QLRSFC，SFCpath

输出：解可行or解不可行

1.利用式(5)和式(6)分别计算部署服务的节点可用性SFAvailj和服务链可用性SFCAvail;

2.ifSFAvailj=0 orSFCAvail=0 //资源可用性约束

3.return解不可行

4.else

5. 利用式(7)计算节点j上的服务功能SFi的处理时延;

6. 利用式(8)计算服务链路的时延开销DSFC;

7. 利用式(9)计算总的链路时延TotalDelay;

8.ifTotalDelay>QDSFC//时延约束

9.return解不可行;

10.else

11.利用式(11)和式(12)分别计算当前节点j的缓存Ncachej及当前路径的丢包情况LR

12.ifLR>QLRSFC//丢包约束

13.return解不可行;

14.endif

15.endif

16.endif

17.return解可行;

5 仿真实验及性能分析

5.1 仿真环境和参数设置

本文仿真实验在配置为Intel(R)Core(TM) i5-4210M 2.0GHz，8GB内存的计算机上进行.仿真网络由12个节点提供底层资源.每个节点随机分配计算、存储以及带宽资源，同时为了使模拟场景更加通用，用"单元"来量化资源单位.分配到的资源服从[10000，15000]单元的均匀分布.链路中的带宽资源在[10，15]单元上均匀分布.服务的请求数量服从250-450的泊松分布.

假设实验中用户的请求序列S包括4个虚拟服务功能，每个功能的资源使用互不影响.用户的QoS需求包括：请求时延在100ms以内，丢包率在5%以内，可用性在90%以上.

5.2 仿真结果与分析

为了验证SA-TS算法的性能，本文采用服务功能链部署成功率，总的资源消耗以及服务链路拥塞率作为评价指标，并与基于贪婪算法的GLT和GLR[20]进行了比较.贪婪算法对问题求解时不做全局考虑，而是依据某个原则进行选择优化.GLT算法仅考虑服务请求时延的最小化，GLR算法仅考虑资源消耗最小.

图3对比了在3种策略下，SFC部署的成功率随SFC请求数量增多的变化.当服务请求数量较少时，网络资源充足，因此3种策略的部署成功率都很高.随着服务请求数量的增多，网络中的可用资源逐渐紧张，此时SA-TS算法的部署成功率最高，GLR算法的成功率最低，这是因为GLR算法仅考虑网络资源消耗的最小化，未考虑用户的QoS需求，当提供的服务不能达到用户的最低要求时会重新发送请求，导致部署成功率最低.SA-TS算法优先考虑了用户的QoS的需求，在不超出网络资源容量的前提下，部署成功率最高.并且随着请求强度的增加，SA-TS算法下SFC的部署成功率下降幅度最小，相比于其他两种算法，本文提出的SA-TS算法平均提升了11%的部署成功率.

图3 3种算法下SFC部署成功率对比

图4对比了在3种策略下，运营商提供的总的资源消耗情况.其中GLR算法的资源消耗最少，原因是GLR算法不考虑提供的服务质量，每次部署仅考虑最低的资源消耗代价，故而对底层资源的消耗最少.GLT算法的资源消耗最多，SA-TS算法与之相比资源消耗降低了5%，原因是GLT算法部署时仅考虑时延最小，没有将时延限制在一个可容忍的范围内，也即未充分利用底层资源，造成了资源的浪费.

图4 3种算法下资源消耗总量对比

本文用链路的拥塞率来衡量模型的负载情况，拥塞率越低，模型的负载均衡性能越高.图5对比了在3种策略下，服务链的负载均衡情况.随着服务请求数目的增多，计算资源等物理资源被逐渐消耗，缓存占用逐渐增多，导致服务链的拥塞率逐渐上升.仿真结果表明，SA-TS算法的链路性能较好，链路拥塞率平均降低了16%.这是因为SA-TS算法保证了QoS，减少了服务请求重发的次数，降低了链路缓存量.

图5 3种算法下服务链拥塞率对比

6 结 论

运营商在实际部署服务功能链时需要满足SLA中关于服务质量的约定，因此服务部署的成功与否很大程度上与用户能够体验的服务质量有关.为在网络资源有限的环境下进一步提高服务功能链的部署成功率，本文综合考虑了用户的QoS需求与最小化的运营商代价，形式化描述了用户的QoS需求及网络资源情况，并在此基础上提出了一种用户QoS与网络资源感知的服务功能链部署方法(SA-TS).针对当前的部署研究不考虑用户QoS或对QoS维度考虑单一带来的部署成功率低等问题，SA-TS方法从时延、服务可用性及拥塞等多个维度保证用户QoS需求，提高了部署效率，优化降低了运营商的部署成本，并且本文的算法既不依赖于初始解，又有记忆功能，避免走回头路，降低了单纯使用SA的随机性，使其不错过邻域中的好解.仿真结果显示，相比于其他部署方法，SA-TS方法在有限的资源环境下保证了用户多个维度的QoS需求并以较低的代价达到了部署的SFC成功率最高的目的.