面向时延敏感业务的服务功能链部署

赵东成，谢景昭，孙 罡

（电子科技大学光纤传感与通信教育部重点实验室 成都 611731）

服务时延一直是服务部署中的一个重点研究问题，研究人员也对减小服务时延进行了大量的研究。目前，对于减小服务时延的研究主要分为两个方面。1） 一方面的研究是考虑减少数据包的处理、排队和转发的时延，但由于受制于云网络的容量和设备自身的处理能力和处理速度，这方面研究的提升空间有限。因此，文献[1-5]指出除了减少数据包的处理、排队和转发时延外，通过将服务功能链（service function chain, SFC）部署在更合理的物理路径上，从而减少对链路资源的消耗和部署路径的传播时延，也能有效地降低服务功能链的整体时延。2） 此外，服务卸载和雾计算为应对云网络的资源消耗和时延问题提供了新的范例。然而，目前关于服务卸载的研究大多考虑将正在运行的计算服务从移动手机或云网络卸载到雾网络。目前，在云-雾网络中，利用服务卸载来部署服务功能链的研究还不够深入。

因此，本文考虑在部署服务功能链时，通过有效的在线博弈决策，将每个服务功能链的一部分虚拟网络功能卸载和部署到雾网络中，从而降低对云网络的资源需求和缩短SFC 的部署路径的长度，进而减小SFC 的路径时延。本文提出了一种基于服务卸载和在线博弈的最小化时延的SFC 部署算法（elay-minimum service function chain deploying of services offloading and online game, DSFCD-SOOG），该算法结合有效的在线博弈和服务卸载决策，在云-雾网络中部署SFC，以减少SFC 的端到端时延。最后，验证了DSFCD-SOOG 算法在SFC 部署中的部署成本、SFC 的路径时延和部署成功率方面的优越性。

1 相关工作

随着互联网的发展，传统网络的僵化问题越来越严重，研究人员提出了网络功能虚拟化技术[6-10]。随着越来越多的网络用户接入，集中式的云网络面临着巨大的挑战，这也给服务功能链的部署带来了困难。为了解决这些挑战，分布式的雾/边缘计算应运而生[11-13]。该计算可以使接入网拥有少量的计算资源，利用这些资源可以为一些小型业务提供计算资源，从而降低对云网络资源的需求。

为了更加灵活地利用接入网的雾计算资源，研究人员提出对接入网的雾计算资源进行切片和虚拟化。然后，将服务功能链中的一部分虚拟网络功能卸载并部署到接入网中，使得虚拟网络功能的部署更加灵活，同时也能有效地降低服务功能链的整体时延。计算卸载能够灵活地利用雾计算资源，成为了一个新的研究热点[14-15]，它们考虑将一些云计算服务卸载到边缘网络上，从而降低云计算的流量负载，满足用户相应的需求。

服务时延一直以来都是服务提供商和用户所关心的一个重要问题。在数据包的处理、排队和转发时延难以改善时，通过将服务功能链部署在更加合理和更短的物理路径上，减少对链路资源的消耗和部署路径的传播时延，进而降低服务功能链的整体时延也是研究人员关注的问题。因此，在面对时延敏感业务的服务功能链部署问题时，有效地减小部署路径的传播时延也是研究的重要方向。因此，本文研究了具有时延需求的用户到用户的服务功能链的部署问题，通过将服务卸载和云-雾网络的资源调度相结合以降低服务功能链的时延。

2 问题定义和数学建模

本节给出了具有时延需求的用户到用户的SFC 请求，以及由雾接入网和云网络组成的物理网络，研究假设每条物理链路都有一个时延约束，每个用户到用户的SFC 请求都有一个整体时延需求。在知道各条物理链路时延约束的前提下，通过服务卸载和联合调度云-雾计算的资源，解决用户到用户的服务功能链的最小化时延和资源效率的配置问题。

2.1 物理网络

在本文中，物理网络由多个分布式的雾无线接入网和集中式的云网络组成。将物理网络建模为无向加权图GP= （NP,EP），其中NP={n1,n2, ···,n|NP|}定义为所有物理节点（如服务器和路由器）的集合，|NP|表示物理节点的数量。EP={l1,l2, ···,l|EP|}定义为所有物理链路的集合，|EP|表示物理链路的数量。本文定义RC=（CN,CE,LN）为物理网络资源约束的集合，其中CN表示物理节点的属性（如服务器资源的 容 量c（nk）和 服 务 器 资 源 的 单 位 成 本p（nk））。CE表示物理链路的属性（如时延d（lj）、带宽的容量b（lj）和 链 路 资 源 的 单 位 成 本p（lj））。LN={L（n1）,L（n2） ,···,L（n|NP|）}表示所有物理节点位置的集合。

2.2 用户到用户的SFC 请求

本文将具有时延需求的用户到用户的SFC 请求建模为无向加权图GR= （NR,ER），其中，NR={f1,f2, ···,f|NR|}表示用户到用户的SFC 请求中所有虚拟网络功能（virtual network function, VNF）的集合，|NR|表示SFC 请求中所有VNF 的数量。ER={e1,e2, ···,e|ER|}表示所有SFC 链路的集合，|ER|表示所有SFC 链路的数量。定义MC=（CN,CE,CD,LN,LU1,LU2）为部署约束，其中，CN={ε（f1）, ε（f2） ,···, ε（f|NR|）}表示SFC 请求中所有VNF 的计算资源需求的集合，CE={ε（e1）, ε（e2） ,···, ε（e|ER|）}表示所有SFC 链路的带宽资源需求的集合，CD表示托管SFC 请求的物理路径的可容忍的总体传输时延，LN={L（f1）L（f2） ,···,L（f|NR|）}描述了所有VNF 的位置约束的集合。由于接入网中的雾计算资源相对稀缺，本研究只允许每个SFC 请求使用自身用户所在的接入网的雾计算资源。因此，每个SFC 请求的VNF 只能部署到用户所在的云网络或雾接入网中。LU1和LU2分别表示两个用户的位置。

2.3 部署SFC 的网络模型

在用户到用户的服务功能链的部署过程中，本研究的重点是部署VNF 和SFC 的虚拟链路。首先，本文将VNF 的部署过程建模为：

本文在部署VNF 的同时部署SFC 链路，将SFC 链路的部署过程建模为：

2.4 基于性别大战的在线博弈的SFC 部署模型

将上述博弈过程建模为BoS 模型，在这个模型中，有两个参与者（包括接入网的总计算资源Rg与剩余计算资源rg的比例Rg/rg和云网络的总计算资源Rc与剩余计算资源rc的比例Rc/rc）有一些共同的兴趣，但是共同利益的结果不同，并且有相对冲突的偏好。该模型基于两种策略：1）将虚拟网络功能卸载并部署到接入网中；2）将虚拟网络功能部署到云网络中。这两种策略是给定并为玩家预知的。

因此，将每个VNF 的部署过程看作是一个博弈过程，接入网的总计算资源Rg与剩余计算资源rg的比例Rg/rg和云网络的总计算资源Rc与剩余计算资源rc的比例Rc/rc作为两个参与者进行博弈，决定是否将VNF 卸载并部署到接入网中。将VNF卸载并部署到接入网作为第一策略（即S1），将VNF部署到云网络中作为第二策略（即S2），Rg/rg作为第一玩家（即P1），Rc/rc作为第二个玩家（即P2），博弈策略如表1 所示。

表1 用于服务卸载的博弈策略

3 算法设计

由于具有时延需求的用户到用户的服务功能链的部署是一个NP 问题，整数线性规划很难快速地得到解决方案。为解决这一难题，基于BoS 在线博弈的SFC 部署模型，本文设计了一个基于服务卸载和在线博弈的最小化时延的SFC 部署算法（DSFCD-SOOG），联合调度云计算和雾计算的资源，解决用户到用户的SFC 的最小化时延和资源效率的部署问题。DSFCD-SOOG 算法如算法1 所示。

算法1：基于服务卸载和在线博弈的最小化时延的SFC 部署算法（DSFCD- SOOG）

输入：物理网络GP= （NP,EP）和资源约束RC =（CN,CE,LN）

SFC 请求队列QueuedSFC

2） 如果QueuedSFC≠Ø，就执行下一步；否则，转到步骤9）；

3） 根据LeavedSFC，更新LeavedSFC 和物理网络资源，让LeavedSFC=Ø，执行下一步；

4） 调 用SDSFCD-SOOG 子 算 法 来 映 射 队 列QueuedSFC 中的第一个SFC 请求SFC1，执行下一步；

5） 如果找到SFC1的一个部署方案M，就执行下一步；否则，转步骤7）；

DSFCD-SOOG 算法展示了将队列QueuedSFC中所有到达的用户到用户的SFC 请求部署到物理网络中的过程。当本文部署每个SFC 请求时，本研究调用SDSFCD-SOOG 子算法来部署SFC，如子算法1 所示。在部署每个SFC 请求时，本研究首先将用户U1所在的雾接入网中的所有物理服务器存储到UG中，然后将用户U2所在的雾接入网中的所有物理服务器存储到UG中，再将云网络中所有物理服务器存储到UC中，最后部署SFC 请求的每个VNFfi。

子算法1：单个SFC 请求的部署算法

输入：一个SFC 请求GR= （NR,ER）和部署约束MC = （CN,CE,CD,LN,LU1,LU2）

输出：部署方案M

1） 将用户U1和用户U2所在的雾接入网中的所有可用物理服务器储存在UG中，将云网中的所有可用物理服务器储存在UC中；

2） 遍历NR中的每一个VNFfi，如果NR中的每一个VNF 已经遍历完，就转步骤14），否则执行下一步；

3） 遍历UG中的每个物理服务器nj∈UG，如果UG中的服务器已经遍历完，就转步骤7），否则执行下一步；

4） 如果物理服务器nj满足VNFfi的位置约束，执行下一步，否则就转步骤3）；

5） 尝试将fi映射到服务器nj上，并根据公式（8）计算成本VNFCost（fi→nj），执行下一步；

6） 找到链路ei的最小时延路径pei和找到从服务 器nj到 用 户U2的 最 小 时 延 路 径pi+1（nj,LU2），根据式（3）和式（9）计算路径pei的时延PathDelay（pei）和部署成本PathCost（pei），根据式（4）和式（10）计算路径pi+1（nj,LU2）的路径时延PathDelay（pi+1（nj,LU2））和部署成本PathCost（pi+1（nj,LU2）），根据式（11）和式（12）计算和记录fi的总路径时延TDelay（fi→nj）和总部署成本TCost（fi→nj），转至步骤3）；

7） 从VNFfi在雾接入网中的所有部署方案中找到一个总路径时延TDelay（fi→nj）最小的部署方案M（fi）和M（ei），执行下一步；

8） 遍历UC中的每个物理服务器nk∈UC，如果UC中的服务器已经遍历完，就转步骤12），否则执行下一步；

9） 如果物理服务器nk满足VNFfi的位置约束，执行下一步，否则就转步骤8）；

10） 尝试将fi映射到服务器nk上，并根据式（8）计算部署成本VNFCost（fi→nk），执行下一步；

12） 从虚拟网络功能fi在云网络中的所有部署方案中找到一个总路径时延TDelay（fi→nk）′最小的部署方案M（fi）′和M（ei）′，执行下一步；

13） 找到最小总时延的纯策略纳什均衡点作为聚点均衡点，并将部署方案存储在M中，转至步骤2）；

14） 找到最后一条链路e|ER|的最小时延路Pe|ER|并存储在M中，根据式（2）计算总部署成本TCost（M）；

15） 返回M和TCost（M）。

本文将虚拟网络功能fi部署到接入网的物理服务器nj上的部署成本定义为VNFCost（fi→nj）：

同时，当虚拟网络功能fi被部署到接入网中的物理服务器nj上时，可以找到从服务器nj到用户U2的 部 署 路 径pi+1（nj,LU2）。将 物 理 路 径pi+1（nj,LU2）的部署成本定义为PathCost（pi+1（nj,LU2））：

当虚拟网络功能fi部署到接入网中的物理服务器nj上时，可以计算出总路径时延TDelay（fi→nj）和总部署成本TCost（fi→nj），分别为：

SDSFCD-SOOG 子算法中部署方案M的总部署成本TCost（M）和总的部署时延TDelay（M）由式（1）和式（2）可计算得出。

4 仿真实验与结果分析

4.1 仿真环境

为了解决用户到用户的服务功能链的最小化时延和资源有效的配置问题，本文考虑联合调度云计算和雾计算的资源，因此物理网络由多个分布式的雾无线接入网和集中式的云网络组成。图1 所示为雾无线接入网。本文使用有46 个节点和76 条链路的USANET 网络作为云网络，如图2 所示。在本文的仿真中，有15 个雾无线接入网连接到USANET网络中的黑色节点。

图1 雾无线接入网

图2 USANET 网络

在本仿真中，假设云网络中物理服务器的计算资源服从均匀分布U[50, 80]个CPU 核心，雾无线接入网中物理服务器的计算资源服从均匀分布U[20, 40]个CPU 核心，物理链路的带宽资源服从均匀分布U[40, 60]单位。一般情况下，本文假设：1）雾接入网和云网络的计算资源的单位成本服从均匀分布U[0.5, 1]元；2）云网络的带宽资源的单位成本服从均匀分布U[1, 1.5]元；3）雾接入网的带宽资源的单位成本服从均匀分布U[0.1, 0.2]元；4）每条物理网络链路的带宽资源的单位成本与链路长度成正比，每条物理网络链路的传输时延与链路长度成正比，因此本文假设每条物理链路的传输时延服从均匀分布U[0.1, 0.2]ms。

另外，当用户到用户的SFC 请求中的VNF 数量n=8 时，本文每次仿真10 000 个用户到用户的SFC 请求的结果。假设这些用户到用户的SFC 请求按照泊松过程动态到达，每个SFC 请求中每个VNF 的计算资源需求服从均匀分布U[5, 10]个CPU 核心，一个用户到用户的SFC 请求中所有虚拟链路的带宽资源需求相同，但各个用户到用户的SFC 请求的带宽资源需求服从均匀分布U[5,10]Gbps。

本文通过对比在云网络的部署方案和在雾网络的部署方案，论证了云计算与雾计算资源联合调度在减少用户到用户的SFC 请求的路径时延方面的优势，对比了文献[14]和文献[15]中提出的SFC部署算法，即PSECO 算法和SAMA 算法。PSECO算法用于将SFC 请求卸载并部署到接入网，而SAMA 算法用于将SFC 请求部署到云网络中。

4.2 仿真结果与分析

图3 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均SFC 路径时延。从结果可以看出，本文DSFCD-SOOG 算法的平均SFC 路径时延低于PSECO 算法和SAMA 算法。这是因为本文的主要优化目标是最小化路径时延，在部署每个虚拟网络功能fi时，联合调度云计算和雾计算资源，解决用户到用户的服务功能链的最小化时延和资源有效的部署问题，尝试将VNFfi分别部署到接入网和云网络中，并将VNFfi的部署问题建模为BoS 在线博弈问题，通过持续的在线博弈，最终确定每个虚拟网络功能fi是否被卸载，以及最终的部署方案，利用服务卸载和雾计算资源来减少用户到用户的SFC 请求的总体时延。因此，与PSECO算法和SAMA 算法相比，本文算法的平均SFC 路径时延更低。

图3 平均SFC 路径时延

图4 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均SFC 链路部署成本。结果表明，本文算法的平均SFC 链路部署成本低于PSECO 算法和SAMA 算法。这是因为当本算法将SFC 的每个VNFfi部署到服务器nj上时，本研究会找到从VNFfi到之前的VNFfi-1的最小时延路径pei，同时找到从服务器nj到用户U2的最小时延路径pi+1（nj,LU2），这将使部署路径尽可能保持在最短路径上。然而，SAMA 算法使用云网络来部署SFC 请求，这使得VNF 部署方案远离用户。虽然PSECO 算法使用雾计算来部署SFC 请求，使得VNF 部署方案的部署方案更接近用户，但由于接入网资源不足，为了保证部署成功率，PSECO 算法会尽可能多地部署VNF 到接入网中，这通常会造成乒乓路径和导致部署路径更长。因此，与PSECO 和SAMA 算法相比，本算法可以获得更低的平均SFC 链路部署成本。

图4 平均SFC 链路部署成本

图5 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均VNF 部署成本。同样地，从结果可以看出，本算法的平均VNF 部署成本低于PSECO 算法和SAMA 算法。这是因为本算法联合调度云计算和雾计算资源来解决SFC 的最小化时延和资源有效的部署问题时，SAMA 算法使用云网络来部署SFC请求，PSECO 算法使用雾接入网来部署SFC 请求，而本文DSFCD-SOOG 算法同时使用云计算和雾计算的资源来部署SFC 请求，这样就有更多的服务器可供选择，并且可以选择成本较低的服务器。另外，虽然本文的主要优化目标是最小化路径时延，但还考虑了服务器成本、接入网的总计算资源与剩余计算资源的比例和云网络的总计算资源与剩余计算资源的比例对部署时延的影响，因此在降低时延的同时，还可以在更合理地利用资源，从而减小VNF 的部署成本。因此，DSFCDSOOG 算法的平均VNF 部署成本低于PSECO 和SAMA 算法。

图5 平均VNF 部署成本

图6 展示了DSFCD-SOOG 算法、PSECO 算法和SAMA 算法的平均SFC 部署成本，其中用户到用户的SFC 请求中的VNF 数量，即n=8。同样地，可以看出本算法的平均SFC 部署成本低于PSECO 算法和SAMA 算法。这是因为平均SFC 部署成本是平均SFC 链路部署成本和平均VNF 部署成本之和，而本文DSFCD-SOOG 算法的平均SFC 链路部署成本和平均VNF 部署成本低于PSECO 和SAMA 算法。

图6 平均SFC 部署成本

图7 显示了3 个算法的SFC 部署成功率。结果表明，本文DSFCD-SOOG 算法的SFC 部署成功率高于PSECO 算法和SAMA 算法。这是因为本研究的DSFCD-SOOG 算法联合调度云计算和雾计算的资源，以解决SFC 的最小化时延和资源有效的部署问题，相比于PSECO 算法和SAMA 算法可以提供更多的资源。此外，考虑到接入网总计算资源与剩余计算资源的比例和云网络的总计算资源与剩余计算资源的比例对部署时延的影响，部署SFC 时也会在更加合理地使用资源，为更多的请求提供服务。因此，本文算法比PSECO 算法和SAMA算法具有更高的SFC 部署成功率。

图7 SFC 部署成功率

5 结 束 语

本文研究了具有时延需求的用户到用户的服务功能链的部署问题。为了尽量减少SFC 部署方案的路径时延，提出了基于服务卸载和在线博弈的最小化时延的DSFCD-SOOG 算法，通过将在线博弈和服务卸载决策相结合，在云-雾网络中部署用户到用户的SFC，以减少SFC 部署方案的路径时延。最后，利用云-雾网络的联合环境对本文DSFCD-SOOG 算法进行了评估。结果表明，相比于对比算法，本算法的平均VNF 部署成本大约降低了5%、平均SFC 链路部署成本大约降低了14%、平均SFC 部署成本大约降低了10%、平均SFC 路径时延大约降低了14%，同时SFC 部署成功率大约提升了40%。