一种竞拍机制下的低时延服务功能链部署算法

赵季红，季文君，曲 桦，吴豆豆

(1.西安邮电大学 通信与信息工程学院,陕西 西安 710121; 2.西安交通大学 电信学院，陕西 西安 710054)

在传统网络中，网络功能直接部署在专有硬件设备上，如网络地址转换、负载均衡、防火墙、网关和入侵检测等功能[1]。传统的部署方式降低了网络适应社会发展和变化的能力。此外，为满足用户的需求，运营商需部署更具专业化的网络功能，将导致巨额的投资成本和运营成本,而由此产生的网络膨胀和高昂的建设成本阻碍着网络的进步和发展[2]。随着社会和技术的快速发展，用户所需网络功能的数量和类型呈几何式增加。为此，网络功能虚拟化(Network Function Virtualization,NFV)作为一种能够根据用户需求快速、灵活地部署网络功能的新技术，为网络的发展提供了新的解决方案[3]。软件定义网络(Software Defined Network,SDN)利用OpenFlow技术将网络的控制平面和数据平面分离，通过软件实现集中控制，加速网络的创新周期[4]。

为了更好地应对多样化的应用场景和差异化的服务质量要求(Quality of Service,QoS)，SDN/NFV协同的未来网络架构作为第5代移动通信(5th Generation Mobile Networks,5G)网络技术领域中的革新技术，为运营商的发展带来机遇和挑战[5]。为部署5G网络，网络运营商正在转向虚拟化网络功能(Virtualized Network Function,VNF)，与易于出现故障的专用硬件相比，VNF仅需较少的维护便可提供更高的灵活性[6]。服务功能链(Service Function Chains,SFC)作为网络虚拟技术中的一种常见用例，能够使网络运营商和基础设施提供商在软件定义的虚拟网络上的各个位置灵活地协调VNF[7]。

随着5G商用服务的到来，一大批新兴应用对时延保障问题提出了新的要求[8]。以4K技术为例，其要求的网络时延需在12～17 ms之间，虚拟现实(Virtual Reality,VR)技术要求端到端时延需小于7 ms。然而，对于超高可靠超低时延通信场景(ultra Reliable & Low Latency Communication,uRLLC)要求业务端到端时延为3～5 ms，以时延更为敏感的车联网场景为例，业界公认的时延需小于3 ms[9]。

在相关研究中，文献[10]为低时延服务提出一种成本高效的服务功能链编排方法，通过引入深度学习算法和交叉熵为用户提供具有优异性能和低资源成本的SFC，但是该算法具有较高的时间复杂度，不适用于大规模网络中SFC的部署，且较高的算法时间复杂度终将影响服务的端到端时延。文献[11]提出了一种基于时延感知的VNF选择算法，通过选择合适的VNF控制SFC的端到端时延，在实际网络环境中该选择算法会使网络资源逐步向高等级用户集中，资源的不平衡将直接影响用户的接受率。文献[12]提出一种服务可持续的自主资源调整算法，通过动态资源调整实现用户时延要求的实时保障，其优点在于保证了服务的可持续性，局限性在于该算法适用于小范围内的资源调整，对整个服务功能链的低时延保障能力有限。基于QoS感知的VNF部署模型[13]，在时延约束中考虑虚拟化开销带来的时延变化，但是其局限性在于缺少对网络资源环境的感知，在处理时延敏感型服务请求时无法为其提供低时延保障。在文献[14]提出的基于机器学习的SFC部署算法中，时延模型以流量负载和CPU利用率为特征，利用随机森林回归对VNF处理时延进行预测，虽然体现出对当前网络状态的感知，但是缺少对底层网络资源的优化，SFC部署的成功率也会因此受限于当前网络资源环境的状态。

基于上述研究成果及不足之处，在对时延敏感型服务功能链部署算法进行设计时，主要考虑了以下3个方面的内容：1)以保障服务的低时延要求为基本前提；2)对时延敏感型服务进行底层资源的优化设计，通过对底层资源的竞拍实现资源利用率的提升，进而实现对运营商利益的保障，推动网络虚拟技术的发展；3)保证部署算法具有较低的时间复杂度。

在SDN/NFV协同的未来网络中，针对时延敏感型服务功能链的部署问题，基于网络资源环境的实时变化，先利用资源优化模型实现服务功能链对底层资源的高效利用，通过引入拍卖模型平衡时延要求与高资源利用率间的关系。再将博弈论中的拍卖模型引入服务功能链的部署问题中，并且拟提出一种启发式多路径拍卖(Multi-Path Auction,MPA)算法，MPA基于博弈论中的竞争与激励机制，通过网络资源竞争实现SFC的最终部署，即为时延敏感型服务提供一种资源高效的服务功能链的部署算法。

1 方法概述

1.1 网络模型

首先，将物理网络抽象为一个加权无向图G=(N,L)，对应网络场景，N代表底层网络服务器节点集合，L表示连接服务器节点的链路集合，每个节点服务器n∈N配置有一定大小的处理器(Central Processing Unit,CPU)和存储资源，每一条物理链路ln∈L配置有一定大小的带宽资源。其次，定义服务请求与服务功能链一一对应，用s={(np,nt);V}表示用户的服务请求，其中：np∈N表示服务请求的源节点；nt∈N表示服务请求的目的节点；V∈{A,B,C,D,E}表示该服务请求所需的VNF集合。

1.2 问题描述

设服务请求s={(n1,n3);(A,B,C)}，服务功能链r1和r2均可为该用户提供所需服务，但是两条服务功能链在节点和链路资源配置上存在明显差异，在应对相同的服务请求时，两条服务功能链对底层资源的利用率也会存在高低的差异，不同服务功能链资源配置如图1所示。

不同的部署方案会显著影响通信时延，从而影响SFC的性能和用户体验。考虑VNF处理时延取决于所部署节点的资源配置，包括该服务器的CPU和存储资源的利用率，而传输时延主要取决于网络拥塞程度。为满足用户更低的时延要求，可以通过提高VNF的CPU和存储资源的配置降低其处理时延，通过平衡链路带宽资源的利用率，避免交换机的拥塞排队可以降低传输时延。基于资源配置与时延间的关系，考虑在实际的网络环境中：一方面，对于时延敏感型服务，为保证用户更低的时延要求需要为其服务功能链配置更多的底层资源，以实现服务请求的正常交付，避免因服务协议(Service Level Agreement,SLA)的违规造成不必要的经济损失；另一方面，网络运营商需要通过不断提高对底层资源的利用率降低投资成本和运营成本。因此，保证对底层资源高效利用的时延敏感型服务功能链的部署问题亟待解决。

1.3 拍卖原理

经济学理论中的拍卖模型越来越多地被应用在通信领域的网络资源分配问题中。拍卖模型按照不同的拍卖规则分为公开拍卖和密封拍卖两种，其中常用的拍卖模型有公开增价拍卖、公开减价拍卖、一级密封拍卖和二级密封拍卖。

公开增价拍卖又称英式拍卖，在该拍卖过程中，卖家进行由低到高的阶梯式喊价，买家通过举手参与竞拍，在卖家不断提高价格的过程中有买家退出竞拍，当买家仅剩一人时拍卖结束，此时的拍品价格即为成交价格。英式拍卖有以下4个特点：1)公开竞价，即拍品对每一个潜在的竞拍者具有相同的价值，但竞拍者对拍品的估价会因各自利益的考量而不同；2)竞价逐轮上升至仅剩一位竞拍者为止；3)拍品由最高竞价者得；4)最高竞价者支付款项。拍卖的目标是保证帕累托效率，即拍品由最高估价者得。整个拍卖模型中包含竞拍者对拍品的估价e、拍品的成本c、成交价g和竞拍者收益u等几个重要参数。

在SFC部署问题中引入英式拍卖模型，以实现服务功能链底层资源的合理配置。在利用拍卖模型表述服务功能链部署问题中存在的竞争关系时，将其具体表述为当服务请求到达时，满足该服务请求的备选路径间存在竞争关系，即图1中r1和r2的关系，通过竞拍流程平衡服务请求的时延要求与底层资源占用间的关系，包括CPU、存储和链路资源。因此，整个服务功能链的部署过程被分为路径发现模块和拍卖竞争模块两个部分。当用户请求到达时，基于资源优化模型的路径发现模块确定该SFC的备选路径集合，再基于拍卖模型的竞拍流程确定当前虚拟网络(Virtual Network,VN)中满足用户时延要求且资源成本最小的SFC，所得SFC部署方案即为最终输出。

实际网络环境中的上述竞争过程存在天然的约束，即拍品对每一个竞拍者有一份私有价值，其他竞拍者不知道该价值，拍卖的目标是使成功部署的服务功能链具有对低时延的保证能力和更高的底层资源的利用率。

2 路径发现模块

2.1 资源优化模型

当给定一物理网络拓扑，SFC部署的目标是确定VNF最优的放置节点以及虚拟链路到物理链路的映射关系，同时保证资源成本的最小化。因此，所提资源优化模型的输出结果为一组嵌入在底层网络上的链式有序的VNF，定义优化目标为最小化SFC占用的底层资源成本，并通过约束条件保证模型的有效性，需满足的约束有节点资源约束、链路约束、实例化约束和流量守恒约束。资源优化模型的目标函数为

链路约束保证物理链路具有的带宽资源hln能够成功映射虚拟链路lv∈Lv，将其表示为

∀s∈S,∀n∈N,∀v∈V

流量守恒约束保证除源节点和目的节点外的其他部署节点均处于流量平衡状态，将该约束表示为

2.2 路径发现流程

路径发现流程是基于资源优化模型提出的，主要目的是确定备选路径集合R={r1,r2,…,rn}，集合中的ri∈R代表该链路是一条基于资源优化模型确定的且满足用户服务请求的SFC，同时，∀ri∈R满足ri∩rj=∅,i≠j的条件。

定义竞拍决策为二进制决策变量，其表达式为

3 竞争拍卖模块

3.1 拍卖模型

确定备选路径集合后，拍卖模型的目标是通过备选路径ri∈R间的竞拍实现服务请求的最终部署，即到达的服务请求作为拍卖者，多条备选路径为竞拍者，输出的是满足用户低时延要求的且资源成本最小的SFC。

在竞拍过程中，竞拍者给出的估价与竞拍者自身拥有的资源配置有关，体现在ri的资源成本和其时延表现上。将SFC中的时延问题划分为处理时延和传输时延。处理时延主要取决于所有承载VNF的物理节点的处理负载，即总处理需求与节点处理能力的比率关系，表示为

传输时延主要取决于在传输数据流的过程中涉及的所有物理节点间的链路利用率，即总流量请求与链路容量之比，表达式为

利用M/M/1排队模型对排队和处理时延进行建模并计算[13]，得出部署在节点n处的虚拟网络功能v所需处理时延，表示为

同理，节点n处的排队时延可表示为

将备选路径ri的时延计算表示为

对数据进行标准化处理，估价ei与ri的资源成本f和时延δ有关，但是数据f和δ并不在同一量级，需要将数据资源成本和时延归一化到区间[a,β]范围内，表示为

其中，参数a=-100，β=100。

对数据进行同趋化处理，竞拍者基于自身资源配置的差异给出的估价各不相同，时延越低给出的估价越高，资源成本越低给出的估价越高，而竞拍者的估价越高在竞拍中越会占有优势，数据性质不同便无法正确反映不同作用力的综合结果，因此，通过改变逆指标数据的性质使所有指标对估价的作用力同趋化。竞拍者ri给出的估价为

ei=-(δ′+f′)

竞拍过程中，利用拍卖者的收益实现SFC的时延约束。拍卖者的收益是在第j轮竞拍中ri给出的成交价减去拍品成本，可表示为

φij=gij-ci

其中，拍品的成本与服务请求的最低时延要求δq有关，通过将δq标准化处理得到δ′q，最后的成交价将由最高估价给出，并考虑通过拍卖者收益实现时延约束，将拍品成本定义为

ci=-(δ′q+f′)

进而有，φij>0时，表示满足时延要求，φij<0时，表示竞拍者ri的时延不满足服务要求。

3.2 竞拍流程

竞拍中，服务请求作为拍卖方，集合R中的备选路径组成具有多个竞拍者的竞拍者集合，通过拍卖获得对服务请求的SFC部署的权限。针对时延敏感型服务部署过程中存在的资源优化欠缺的问题，通过竞拍流程在保证时延服务低时延要求前提下实现其对底层资源利用率的提升。具体的MPA算法如下。

输入：服务功能链备选路径集R，

物理网络拓扑G=(N,L)。

输出：服务功能链部署方案ro

步骤1∀ri∈R获取估价集合E={e1,e2,…,en}。

步骤2对E中的元素进行循环计算。

步骤3排序获取最高估价者r′i和e′i，若估价相同则占用物理节点较少的路径优先。

步骤4拍卖方将此轮成交价gij广播给竞拍方。

步骤5如果φij>0，则跳出循环。

步骤6或者将xn赋值为 0。

步骤7输出服务功能链部署策略。

4 仿真结果

4.1 实验设置

通过仿真实验，验证所提MPA算法各个性能的有效性。对比算法选择经典贪心最短路径(Greedy Shortest Path,GSP)算法和文献[10]提出的反馈调整(Closed-Loop Feedback,CLF)算法。其中，GSP算法通过寻求最短路径实现SFC端到端时延的最小化，CLF算法通过结合网络功能的整合分裂和寻求长度受限的最短路径实现SFC的部署，同时，引入深度学习算法进行反馈调整以进一步提高部署的成功率，并且该算法的目的同样是为低时延服务提供一种成本高效的服务功能链部署方法。仿真中选择和比较的性能参数主要有用户接受率、时延、部署时间以及资源利用率。

利用轻量级软件定义网络和测试平台mininet绘制物理网络拓扑，底层网络拓扑如图2所示，包含有24个节点和43条链路，链路上的数字表示链路通信延迟，单位为ms。

图2 底层网络拓扑

首先，定义实验中资源配置包括链路的带宽资源以及节点中的CPU资源和存储资源。其次，将所有节点的CPU和存储资源随机设置在10～20个单位之间，并将链接资源随机设置在50～100个单位之间。在实际的网络环境中，VN在长期为用户提供服务的过程中即使是相同类型VNF，其资源配置也存在差异，因此，实验中对网络拓扑中每个节点服务器进行初始化，使得每个节点中的VNF类型和资源配置不尽相同。

4.2 实验结果分析

针对时延敏感型服务的底层资源配置问题，3种不同算法的用户接受率对比情况，如图3所示。

图3 3种不同算法的用户接受率对比

由图3可以看出，所提的MPA算法在用户接受率方面的性能表现明显优于CLF和GSP算法。实验中：对于CLF算法，当SFC的长度大于5个单位时其用户接受率低于90%；对于GSP算法，其平均用户接受率仅为73.5%，在面对用户连接数密度较大的情境时，将严重影响SFC部署的成功率，进而影响用户体验；对于所提的MPA算法，即使在SFC长度不断增加的情况下(SFC的长度从4个单位增加到8个单位)，MPA算法的用户接受率依然稳定在90%以上。

服务功能链在不同长度下的时延对比情况如图4所示。

图4 3种不同算法的时延对比情况

由图4可以看出，与GSP算法相比，所提的MPA算法同时考虑了时延与资源成本的双重指标，避免陷入局部最优，并且SFC的时延降低了29%左右。在时延敏感型服务的低时延保障方面，与CLF算法相比，MPA算法同样具有优异的表现。

3种部署算法的部署时间对比情况，如图5所示。

图5 3种不同算法的部署时间对比

CLF算法通过整合和拆分虚拟网络功能实现底层资源利用率的提升，并利用反馈调整模块实现节点和链路的资源调整，整个算法时间复杂度较高。实际的网络环境中，对VNF整合拆分的时间以及映射过程中反馈调整的时间都将额外增加部署时间的成本，最终作用在链路的时延上，在实验中该时间成本设置为一个范围在[5,8]的随机值。实验结果表明，MPA算法的部署时间始终低于CLF和GSP算法。对于时延敏感型服务更低的SFC部署时间成本将显著改善用户体验，有利于保障运营商和用户的利益。

3种不同算法的资源利用率对比情况，如图6所示。

图6 3种不同算法的资源利用率对比情况

由图6可以看出，与其他两种算法对比，所提的MPA算法对底层资源利用率更加高效。与CLF算法相比，并结合时延方面的性能表现，MPA算法在保证低时延要求的前提下，最大程度地利用网络资源，在降低投资成本和运营成本问题中具有实际意义。

5 结语

为解决时延敏感型服务资源优化欠缺的问题，并考虑在降低投资和运营成本方面具有实际的应用价值，提出了一种基于拍卖模型的启发式多路径拍卖算法实现时延敏感型服务对底层资源的高效利用。实验结果表明，所提出的算法通过引入拍卖模型降低了算法的部署时间，同时在保障了服务低时延要求的基础上提高了资源的利用率，从而使得该算法能够更加适用于低时延的应用场景。考虑到时延敏感型服务对时延的敏感性以及低时延的特性，在服务请求期间结合机器学习算法实现服务时延的可预见性，保证时延的稳定性，提高部署算法的灵活性以适应网络资源环境的实时变化是后续的研究方向之一。