端到端时延上限确定的服务链部署算法

王泽南，张娇，汪硕，黄韬，F.Richard Yu

（1.网络通信与安全紫金山实验室，江苏 南京 211111；2.北京邮电大学网络与交换技术国家重点实验室，北京 100876；3.加拿大卡尔顿大学，渥太华 K1S 5B6）

1 引言

随着5G 网络的发展，远程医疗、自动驾驶、AR/VR、工业自动化等业务正在成为可能，并处于稳步推进的过程中。这些新业务对网络端到端时延提出了更严苛的要求。例如，自动驾驶需要网络提供低于10 ms 的端到端时延，保证汽车能够及时地执行命令[1]。游戏玩家在体验AR/VR 游戏时，需要网络提供低于20 ms 的端到端时延，以消除游戏图像和动作不匹配造成的眩晕[2]。因此，提供端到端严格的时延保障对这些业务至关重要。

当今的网络依赖于众多的网络功能设备，文献[3]指出网络中近半的设备均为网络功能设备。随着网络功能虚拟化（NFV,network function virtualization）技术[4]的普及，可以预见越来越多的网络功能设备将以虚拟网络功能（VNF,virtual network function）的形式进行部署。软件定义网络（SDN,software define network）[5]作为与NFV 互补的技术，可以实现流量在VNF 之间按顺序进行传递，从而实现VNF 按序串成链来提供网络服务，这也称为服务链。在面对时延敏感业务的服务链请求时，如何保障服务链端到端的时延吸引了学术界和工业界的关注。

现有许多文献[6-9]研究了如何通过优化服务链的部署来为服务链提供端到端的时延保障。但是这些工作都无法为服务链提供严格的时延保障。例如，文献[6-7]在建模的过程中，认为数据包通过VNF 节点的时延是固定的，这将对服务链的端到端时延建模带来较大的误差。由于VNF 节点分配的资源大小是可以变化的，而VNF 节点的数据包处理速率将随着分配资源的大小而改变，从而影响数据包通过VNF 节点的时延。文献[8-9]通过使用排队论来避免这一问题，然而，基于排队论计算得到的时延为数据包平均时延，不能保证每一个数据包均能在该时延内完成传输。显然，这对一些时延敏感的业务是不可容忍的。

为了解决上述问题，一些工作提出了基于网络演算计算服务链的端到端时延。由于基于网络演算得到的时延为时延上限，因此能保证全部的数据包在该时延内完成传输。例如，文献[10]率先将网络演算应用于计算服务链中单条业务流的端到端时延中。由于不同的服务链会共享网络基础设施，不同的业务流量之间会存在资源竞争。因此，文献[10]中的模型不能扩展到多条服务链的场景。文献[11]考虑了服务链之间的资源竞争并基于随机网络演算推导了服务链的端到端时延，并将推导得到的结果在实验仿真中进行了验证。然而，上述工作仅仅是基于网络演算推导了服务链的端到端时延，并未进一步将网络演算与服务链的部署相结合。

本文将网络演算应用到服务链的部署问题中，旨在保障部署后的服务链具有严格的端到端时延上界。严格的时延保障指经过服务链的每一个数据包的时延都符合业务的需求。这种为业务流量提供严格时延保障的服务链称为确定性服务链（DSC,deterministic service chain）。在DSC 的部署问题中，DSC 的目标是为接收的服务链请求提供严格的端到端时延保障的同时，提高接收的服务链的数量。首先对DSC 的部署问题进行建模，由于网络演算在推导服务链时延的过程中引入了非线性约束，因此问题最终被建模为混合整数非线性规划。为了简化问题的求解，DSC 问题被分解为2 个子问题，分别是服务链路由子问题与VNF 节点资源分配子问题，通过引入最大允许的VNF 总时延，实现对2 个子问题的协同优化。最后，通过实验验证了所提模型和算法的有效性，结果显示所提算法能在提高接收的服务链数量的同时，严格保障接收的每一条服务链的端到端时延。

2 网络演算基本概念

时延是网络性能的一个重要指标，目前存在多种不同的工具和方法对网络端到端性能进行建模和分析。其中最常见的工具是排队理论，它将数据包的到达建模为泊松过程，并计算平均的时延和队列长度。然而，文献[12]指出，网络中的流量具有自相似性和突发性，因此泊松过程不能准确地描述流量的到达特征。此外，排队论得到的时延为平均时延，不能保证每个数据包都能在该时延内完成传输。因此，另一种工具——网络演算应运而生。

在网络演算中，最基本且最关键的概念是到达曲线、服务曲线和服务曲线串联。到达曲线描述流将要发送的最大数据量，服务曲线描述服务节点保证处理的最小数据量。如图1 所示，假设业务到达流量经过了令牌桶过滤器（TBF,token bucket filter），TBF 的发送速率为ρ，令牌桶的大小为σ，则经过TBF 的流的到达曲线可表示为ρt+σ。业务流量被发送到节点进行处理，假设该节点的服务曲线为γ(t−θ)，该服务曲线表示该节点的处理速率为γ，数据包在得到处理之前将等待θ时间[13]。基于到达曲线和服务曲线，可以得到2 个重要概念，分别是时延上限和队列长度上限。时延上限的值等于到达曲线与服务曲线的最大水平偏差，队列长度上限的值等于到达曲线和服务曲线的最大垂直偏差。如果用α(t) 和β(t) 分别表示到达曲线和服务曲线，则时延上限的表达式为式(1)，队列长度上限的表达式为式(2)。在这里，可以得到时延上限的值为σ/ +γ θ，队列长度的上限为ρ+θ σ。

上述为网络演算在单个节点中的运用，然而在网络中，通常存在多个节点串联的情况。此时，端到端的时延上限或队列长度上限不能简单地通过累加单个VNF 节点上的时延上限或队列长度上限来获得。网络演算理论给出了计算多节点串联情况下的端到端服务曲线的方法。如图2 所示，2 个独立的节点分别对应2 条服务曲线，假设这两个节点的服务曲线分别为β1(t)=γ1(t−θ1)和β2(t)=γ2(t−θ2)。然后，串联后的2 个节点的端到端服务曲线为β1(t)⊗β2(t)，其中符号⊗表示最小化卷积，其具体表达式如式(3)所示。在图2 的情况中，2 个节点串联后的端到端服务曲线是γ2(t−θ1−θ2)。

网络演算能够计算多个网络节点串联后端到端的服务曲线，而服务链则由多个VNF 节点串联组成。这意味着，当得到服务链中每个VNF 的服务曲线后，网络演算能够计算服务链的端到端服务曲线，从而计算数据包经过服务链的时延上限。因此，网络演算在本文问题场景中具有良好的适用性。

3 问题描述

本节给出了DSC 部署问题的系统模型和数学建模。DSC 的目标是为每一个接收的网络业务请求确定最佳的服务链部署方案，在保证服务链端到端时延严格满足业务需求的同时，使接收的服务链总量最大。

3.1 系统模型

1) 底层网络基础设施

2) 网络业务请求

在本文问题中，假设全部的网络业务请求同时全部到达（模型和算法也支持业务请求逐个到达的情况）。对于每一个网络业务请求，网络运营商需要决定是否对其接收。使用S={s1,s2,…,sK}表示全部网络业务请求的集合，其中K为集合S中业务请求的数量。第k个网络业务请求包含一条服务链。服务链由一组按序排列的VNF 节点Fk和一组虚拟链路Lk组成，为了便于说明，分别用表示业务请求中的第i个VNF 节点和第j条虚拟链路。服务链中的每一个VNF 都有一种对应的类型，=1表示的类型为ψh。此外，每一种类型的VNF 都会被分配一定的资源。业务请求除了包含的服务链，还会指定业务流量的起点和终点，分别表示为。业务流量由源点的用户生成，在进入网络之前首先会经过TBF 进行整形。TBF 的参数包含ρk和σk，这意味着允许终端用户一次性发送大小为σk的数据量，但平均的发送速率不能超过ρk。业务流量从入口节点开始，依次按序经过全部的VNF 节点，最终到达终点节点。所有数据包的端到端时延应满足业务的时延要求，记为Dk。

3) 服务链部署示例

以一个例子来介绍业务请求中服务链的部署。部署主要包括VNF 节点的映射、虚拟链路的映射以及VNF 节点的资源分配。部署示例如图3 所示。假设业务请求中包含的服务链由3 个VNF 组成，源点为底层物理节点1，终点为底层物理节点4。为了便于表示服务链的源点和终点，构造了一个伪头部VNF和伪尾部VNF。这2 个伪VNF 提前映射到源点和终点。接下来，需要确定每个VNF 和虚拟链路的映射。在本例中，VNF1映射到底层物理节点2，而VNF2和VNF3都映射到物理节点3。业务流量通过最短路径依次遍历底层物理节点1、2、3、4。同时虚拟链路被映射到对应的路径上，特别是，VNF2和VNF3之间的虚拟链路并没有映射到物理链路，而是映射到底层物理节点3 内部的链路。当服务链中的节点和链路的映射确定后，需要为VNF 所映射的VNF实例分配资源，即完成了一条服务链的部署。

3.2 数学建模

本节将基于上述系统模型，对DSC 的部署问题进行数学建模。

1) DSC 部署问题的优化目标

DSC 部署问题的优化目标是最大化接收的业务量，且保证服务链的端到端上限时延严格满足业务的需求。接收的业务总量表示为式(4)，其中Wk表示是否接收业务请求sk。

2) 底层物理节点容量限制

在系统模型中，Rhn表示分配给节点上类型为ψh的VNF 的总资源量。式(5)保证了分配给一个底层物理节点上所有类型的VNF 的资源总量不能超过该底层物理节点的资源容量。

3) 底层物理链路容量限制

底层物理链路也有带宽限制。首先，为了表示虚拟链路是如何映射到底层物理链路的，定义变量。如果业务请求sk中的第j条虚拟链路映射到之间的物理链路，则。此外，物理链路2 个方向的流量将共享带宽。因此，式(6)保证了物理链路上的总流量满足其带宽限制。

4) VNF 映射限制

为了表示服务链中的VNF 是如何映射到底层物理节点的，定义变量表示业务sk中的第i个VNF 被映射到上。式(7)确保了接收的每一个请求中的每个VNF 都完成映射且仅被映射一次。

5) VNF 类型限制在系统模型中，假设每个底层物理节点支持部分的VNF 类型，例如，高性能防火墙需要FPGA硬件加速，则只有配备了FPGA 的物理节点才能支持该网络功能。式(8)表示一个VNF 只能被映射到支持该VNF 类型的底层物理节点。

6) 虚拟链路映射限制

每条虚拟链路可以从2个不同的方向映射到一条物理链路。此外，每条虚拟链路可以映射到多条物理链路。因此，使用式(9)保证一条虚拟链路不会同时映射到物理链路的2 个方向上，以避免产生环路。此外，使用式(10)保证每个底层物理节点的输出流量总量与输入流量总量相等，如此，同一个业务请求中的虚拟链路最终可以形成端到端连续的路由路径。

7) 端到端时延限制

最后一个限制条件是端到端时延的限制。Dk*表示部署后的服务链的端到端时延上限。Dk*的确切形式将在第4 节中详细介绍。式(11)表示服务链的端到端时延应严格满足业务的时延要求。

4 服务链端到端时延上限计算

在问题的数学建模中，服务链部署后的端到端时延暂时用Dk*表示。本节将应用网络演算推导Dk*的具体表达式。

根据第2 节给出的示例，需要计算服务链的端到端时延上限，则首先需要获取业务流量的到达曲线以及服务链的端到端服务曲线。在系统模型中，业务流量在进入网络之前由TBF 进行整形。因此，业务流量的到达曲线很容易得到。式(12)表示业务sk的到达曲线。

接下来，将推导业务sk的端到端服务曲线。业务流量在网络中会经过VNF 节点、物理交换机和物理链路，这些网元都有其各自的服务曲线。首先，研究VNF 节点的服务曲线。本文使用速率−时延服务曲线对VNF 节点进行建模。由于分配给VNF 的资源是可变化的，因此VNF 服务曲线中的速率参数会随之变化。为此，通过实验验证了VNF 节点的速率与分配的资源之间的关系。实验中开发了2 种示例性质的 VNF，分别为 VNF-Firewall 和VNF-NAT。调整分配给VNF 的CPU 资源的百分比并测量VNF的速率，例如当分配的CPU资源为40%时，则意味着数据包处理进程消耗了CPU 40%的时间片，结果如图4 所示。从图4 可以看出，VNF的速率与分配的资源量成正比。因此，分配的资源与速率的关系如式(13)所示，其中λhn是一个常数，可以通过实验获得。最终，上类型为ψh的VNF 的总服务曲线如式(14)所示。

式(14)中的服务曲线代表的是整个VNF的服务曲线。然而，多个服务链可能共享同一个VNF 并竞争资源。因此，对于每一条服务链，需要计算其在VNF 上独立的服务曲线。基于单个VNF 上独立的服务曲线，计算服务链端到端时延上限的一种简易方法是根据业务的到达曲线和VNF 上独立的服务曲线计算服务链经过每一个VNF 的时延上限，然后端到端的时延上限为每一个VNF 上的时延上限的累加。然而，由于“pay burst once”现象的存在，这种简易的方法会放大端到端的时延上限。因此，正确的方法是在考虑服务链之间竞争的情况下，计算服务链端到端整体的服务曲线，并根据端到端整体的服务曲线和业务流量的到达曲线计算端到端时延上限。

为此，首先需要推导服务链经过单个VNF 时独立的服务曲线。根据文献[14]可知sk所经过的VNF 上交叉流量的到达曲线。式(15)表示底层物理节点上类型为ψh的VNF 上的总流量大小。基于式(15)，sk中第i个VNF所在的VNF 实例上的总流量大小可以表示为式(16)。为了简化的表达式，定义一个变量，其值如式(17)所示。然后，的值可以简化为式(18)，sk所经过的VNF上交叉流量的到达曲线可以表示为式(19)。根据文献[14]中第4.B 节中给出的理论，针对的独立服务曲线仍然为rate-latency 的类型，其具体形式如式(20)所示，其中和的值分别如式(21)和式(22)所示。

在得到sk中单个VNF 独立的服务曲线后，可以根据网络演算理论轻松地得到sk端到端的服务曲线。根据网络演算理论[15]，s k中多个串联的VNF的服务曲线如式(23)所示。符号⊗表示极小化卷积。sk端到端的服务曲线仍然是rate-latency 类型，如果使用式(24)表示sk的端到端服务曲线，则γk和θk的值分别如式(25)和式(26)所示。最后，可以基于网络演算理论得到sk中所有VNF 节点串联后的端到端时延上限为式(27)。

由式(25)和式(26)可以观察到，端到端服务曲线的速率参数取决于全部串联的VNF 节点中的最小速率，而端到端服务曲线中的时延参数是全部串联的VNF 节点的时延之和。这一观察结果指导本文将更多的资源分配给瓶颈VNF 节点，以提高串联的VNF 节点中最小的速率，从而提高端到端服务曲线的速率。此外，这对研究交换机和物理链路的时延也具有一定的指导意义。交换机的服务曲线认为是rate-latency 类型，可以表示为γs(t−θs)。由于交换机的处理速率γs大于全部的VNF节点，因此在端到端服务曲线中考虑交换机并不会影响γk的值。因此，数据包每经过一个交换机只会为数据包增加一个固定的时延值，即θs。服务链路由路径中包含的交换机数量等于包含的物理链路的数量减1。因此，数据包经过交换机产生的时延的值如式(28)所示。

对于物理链路，文献[14]指出其服务曲线是一个脉冲函数，即速率为无限大，时延为一个固定值。这也符合常识的判断，物理链路中的数据包不会产生排队，数据包经过物理链路的时延等于物理链路的传输时延。在系统模型中，使用′表示至的传播时延。因此，数据包经过物理链路产生的时延的值如式(29)所示。

5 服务链部署算法

本节介绍一种名为JRRA（joint routing and resource allocation）的启发式算法来解决DSC 的部署问题。JRRA 首先确定最优服务链路由路径，该路径依次包含所有需要的VNF 节点，然后确定包含的VNF 节点的资源分配量。服务链路由路径的选择和VNF 节点的资源分配量将决定服务链的端到端时延。虽然已有许多相关文献[16]研究了不同场景下的服务链优化部署问题，但是尚没有算法能运用于DSC 问题，同时本问题还存在3 个挑战。

第一个挑战来自服务链的路由。在不考虑VNF节点时延的情况下，需要找到端到端时延最小的路径，同时，该路径需要满足一些额外的要求。第二个挑战来自VNF 节点的资源分配。从式(25)、式(26)和式(27)可以看出，服务链中任一VNF 节点分配的资源量将影响数据包通过服务链的时延。因此，服务链中所有VNF 节点的资源分配应该协同进行考虑。此外，由于不同的服务链之间会共享VNF 节点，不同的服务链中共享的VNF 节点的资源分配也应该协同进行考虑。第三个挑战来自服务链路由与VNF 节点分配的协同，由于两者都将对服务链的端到端时延产生影响，因此需要将两者协同进行考虑。

JRRA 算法分为两步。第一步，将服务链路由建模成了一个可解的线性规划问题，此外还提出了一种基于多层拓扑的启发式服务链路由方法来解决第一个挑战。第二步，通过推导确定为每个VNF节点分配的资源量来解决第二个挑战。通过引入最大允许的VNF 时延参数将第一步与第二步进行协同来解决第三个挑战。

5.1 算法概述

算法1JRRA 算法主流程

JRRA 算法的流程如算法1 所示，首先根据ρk/Jk的值（每单位服务链长度的吞吐）降序排列所有业务请求，然后按序逐个部署业务请求。对于单个业务请求的部署，将按照图5 所示的示例进行说明。假设图5 中的业务请求s k的带宽要求为5 Mbit/s，业务从（节点A）开始，到（节点F）结束，所需的VNF 类型依次为VNF1、VNF2和VNF3。首先去除剩余带宽小于5 Mbit/s 的物理链路，构造一个拓扑Gk（算法1 的第3 行），即节点A 和节点B之间的物理链路将被移除。拓扑Gk中剩余的每条链路的时延等于其原来的时延加上它所连接的交换机的转发时延的一半，这是为了将节点时延转移至链路时延。接下来的目标是在Gk中为sk找到最短且可行路径（FS-Path,feasible and shortest path）。FS-Path 应满足如下3 个要求。1) 从开始，到结束。2) 路径上所有物理链路的剩余带宽都能够承载业务。3) 端到端时延（仅包含交换机时延和链路传输时延，不包含VNF 节点时延）最小。如何找到FS-Path 的方法将在5.2 节中介绍，在这里使用一个函数FeasibleShortestPath()表示该方法（算法1的第5 行）。如果找不到FS-Path，sk将被拒绝。否则，将继续在FS-Path 中为其包含的VNF 节点分配资源。

在VNF 节点资源分配的过程中，引入一个参数，名为最大允许VNF 节点时延的值等于业务的端到端时延需求Dk减去FS-Path 的总时延（算法1 的第7 行）。然后，分配给每个VNF节点资源可以根据推导得到，具体推导过程在5.3 节中描述，这里使用函数VNF_Resource()来替换它（算法1 的第8 行）。由于分配给每个VNF节点的资源数量在寻找服务链路由的过程中是不可预测的，因此无法确定底层物理节点是否能够为VNF 节点提供足够的资源。因此，VNF 节点所需的资源可能存在不能被满足的情况。为了处理这种情况，函数VNF_Resource()将返回资源不能被满足的VNF 节点，这些VNF 节点包含在U-VNFs 集合中。U-VNFs 集合中的节点将从拓扑Gk中删除。然后，在更新后的kG将重新寻找FS-Path（算法1 的第11 行）。如果所有VNF 节点所需要的资源都可以满足，则业务请求sk将被接收。

5.2 服务链路由与节点映射

本节将介绍算法1中函数FeasibleShortestPath()的实现。根据FS-Path 的要求，可以通过求解以下ILP 模型来找到FS-Path。

然而，当网络规模较大时，基于ILP 的解决方案面临计算时间长的问题。因此，本文也提出了一种高效的启发式算法来确定FS-Path。经典的Dijkstra算法[17]可以得到2 个节点之间的最小加权路径，即时延最小的路径。然而，Dijkstra 无法找到按序经过所需的VNF 的最小加权路径。文献[18]中提出的基于多层拓扑的服务链路由方法可以有效地解决这一问题，但该方法不能保证路径包含的物理链路的剩余带宽能够满足业务的需求。虽然剩余带宽小于业务带宽需求的物理链路已经在拓扑Gk中被提前移除，但业务流量可能会多次经过同一条物理链路，从而导致物理链路的剩余带宽出现不能够满足需求的情况。例如，在图5 中，当业务的路由路径为A→C(VNF1)→E(VNF2)→C(VNF3)→E→F 时，端到端时延为10 ms，小于图中标注的路由路径。但是，业务流量在节点C 和节点E 之间的物理链路上经过了3 次，因此对该链路的带宽要求为15 Mbit/s，然而该链路的剩余带宽仅为8 Mbit/s。因此，本节提出了一个时延惩罚因子α（一个大于1 的常数），并将其应用于文献[18]所提方法中。当文献[18]中的方法找到的路由路径包含剩余带宽不足的物理链路时，将这些物理链路的时延乘以α。如此，这些物理链路在最小加权路径的寻找过程中将逐渐不被优先选择。

算法2JRRA 服务链路由算法

算法2 给出了JRRA 算法中完整的服务链路由算法过程。首先，基于拓扑Gk构造一个新的多层拓扑图，如图6 所示，其中层数等于服务链的长度加1，每一层的拓扑与Gk保持一致。层之间的连接取决于所需VNF 类型的位置。例如，节点B 和节点C 支持的类型为VNF1，则节点B1与节点B2相连，节点C1与节点C2相连。这确保了当路由路径从第1 层到达第2 层时，必定会经过类型为VNF1的VNF。类似地，将其他相邻的两层之间进行连接。每层中物理链路的时延与Gk保持一致，连接相邻两层的链路的时延设置为0。指定节点A1和节点F4分别作为服务链路由的起点和终点，运用Dijkstra算法寻找到起点和终点之间的最小加权路径S-Path（算法2 中第3 行），S-Path 将依次经过第一层到达第四层，也就是说，选择的S-Path 也将依次包含所需的VNF。然后，将检查得到的S-Path，以保证其中所包含的物理链路的剩余带宽是足够的（算法2中第10 行）。不合格的物理链路将加入U-Links 集合，并将U-Links 集合中的链路的时延乘以α后再重新寻找S-Path（算法2 中第10～13 行）。最终，通过检查的S-Path 即FS-Path。

5.3 VNF 节点资源分配

本节将介绍算法1 中的VNF_Resource()函数的实现。在推导VNF 的资源数量之前，已经确定了最大允许的VNF 节点时延，即。接下来，将基于的值，以业务请求sk为例，推导出为sk所对应的FS-Path包含的VNF节点分配的最优资源量。分配的资源量应满足以下3 个要求。1) 端到端总的VNF 节点时延在sk之前接收部署的业务的端到端总VNF 节点时延不应增加；3) VNF 节点的处理速率应大于所承载的全部业务的带宽需求。当满足上述3 个要求时，分配给VNF节点的最小资源量即最优资源量。

接下来，以sk为例说明如何推导出最优的VNF资源分配方案。为了简化推导过程中使用到的表达式，首先定义了式(31)所示的变量。然后，式(21)和式(22)可以分别简化为式(32)和式(33)。其中表示分配给sk中第i个VNF 部署所在的VNF 实例的资源量。由于端到端的VNF总时延与分配给VNF的资源成反比，则当端到端的总VNF 时延等于时，分配的资源量最小。因此，将式(33)中的值代入式(27)，可以得到式(34)。

由式(25)可知，服务链端到端服务曲线的速率由服务链中处理速率最小的VNF 决定，处理速率最小的VNF 将限制端到端服务曲线的速率，从而增加端到端的VNF 时延。因此，应该提高处理速率最小的VNF 的处理速率，避免出现瓶颈。另一方面，如果某一VNF 的处理速率大于服务链端到端服务曲线的速率，这对于提高服务链整体处理速率没有帮助，从而造成资源浪费。综上，服务链中的每一个VNF 的处理速率都将与服务链端到端的处理速率保持一致，因此，服务链中的每个VNF都应该具有相同的速率，据此，可以得到式(35)。将式(35)中的的表达式代入式(34)，可以得到γk的值。然后，再将γk的值代入式(35)，可以得到的值。

然而，上述资源分配方案可能不能满足第二个和第三个要求。以业务sk中第i个VNF 所在的VNF实例为例，另一个业务sk'中的VNF 可能在业务sk部署之前就已经存在于该VNF 实例中。在部署sk时，需要重新确定分配给该VNF 实例的资源量，只需要保证γk′的值不降低，θk′的值不增加即可。应保证不增加sk'对应的VNF节点的总时延。为此，因此，可以得到式(36)和式(37)。至此，第二个要求已经满足。根据第三个要求，即VNF 节点的处理速率应大于所承载的全部业务的带宽需求，可以得到式(38)。最终，确定满足3 个要求，即同时满足式(35)、式(36)、式(37)和式(38)的最小VNF 节点资源分配量，即最优的VNF 节点资源分配方案。

综上，DSC 问题的优化目标是帮助服务提供商最大化接收的业务量，即最大化式(4)的值，同时通过协同优化服务链路由与VNF 节点资源分配，使通过服务链的数据包的最大时延小于业务的时延需求，即保证每一个数据包均能在指定时延内完成传输。

6 实验分析

本节通过数值模拟来评估所提模型和算法的性能。首先介绍实验设置，然后从不同方面对算法的性能进行评估，并对实验结果进行讨论。

6.1 实验设置

为了获得准确的统计，每个数据点通过平均10 次独立模拟的结果得到。基于Python 进行数值模拟，利用Python 中的PySCIPOpt 套件[19]求解ILP 模型。此外，运行数值模拟的计算机配备了主频为3.40 GHz 的CPU 以及大小为16 GB 的内存。实验在Internet Topology Zoo[20]提供的2 个真实的网络拓扑中进行，其中网络拓扑1 由42 个物理节点和66 条物理链路组成，而网络拓扑2 由13 个物理节点和15 条物理链路组成。每个物理节点包含的CPU核数在[50,100]中随机生成，此外，每个物理节点对VNF 类型的默认支持率为70%，假如网络中存在30 种不同类型的VNF，则每个物理节点将随机支持其中的21 种VNF 类型。每条物理链路包含2 个参数，包括可用带宽和传播时延。每条物理链路的带宽在[10,100]Gbit/s 中随机生成，传播时延在[1,5]ms中随机生成。

为了生成业务请求，首先生成一组VNF 类型，包含30 种不同的VNF 类型。对于每一种VNF 类型，所需CPU 资源和处理速率之间的关系已经在式(13)中进行了讨论。式(13)中的常数λhn在[0,1]中随机产生，例如，λhn=0.5表示在物理节点上，类型为ψh的VNF 处理1 Gbit/s 的流量需要0.5 个CPU 核（占用1 个CPU 50%的运行周期）。业务请求中的服务链包含的VNF 的数量从[2,7]中随机选择，每一个VNF 的类型将从VNF 类型的集合中随机选择。此外，每个业务请求的入口和出口节点从全部的物理节点中随机选择。每个业务请求的流量在进入网络前都将由TBF 进行流量整形。每个业务请求中TBF 的rate 参数在[100,1 000]Mbit/s 中随机生成，burst 参数在[1,10]Mbit/s 中随机生成。最后，当网络拓扑1 作为实验网络拓扑时，共随机生成2 000 个业务请求，而当网络拓扑2 作为实验网络拓扑时，共随机生成500 个业务请求。如果算法能为业务请求找到一个可行的解决方案，则该请求将被接收，否则请求被拒绝。

本节对比了以下2 种算法。1) JRRA-MLT 算法。JRRA-MLT算法基于多层拓扑图为业务寻找服务链的路由。2) JRRA-ILP 算法。JRRA-ILP 算法与JRRA-MLT算法的不同之处在于JRRA-ILP通过5.2节中的ILP 模型来寻找服务链的路由。JRRA-MLT和JRRA-ILP 算法均通过5.3 节中的方法确定VNF节点的资源分配量。

6.2 实验结果

DSC 部署问题的目标是帮助服务提供商最大化接收的业务量，即式(4)所示的值。因此，在实验中，使用接收的业务量作为算法的性能评估指标，并测试了一些因素对算法性能的影响。

图7 展示了采用不同的实验网络拓扑的情况下不同算法接收的业务量大小。从图7 中可以看出，JRRA-ILP 算法的性能表现优于JRRA-MLT 算法。这是因为基于ILP 确定的服务链路由路径具有更小的端到端时延，当链路时延和交换机时延越小时，则对应的最大允许的VNF 节点时延则变得更大，从而减少VNF 节点对资源的使用。由于VNF 节点资源使用的降低，在网络中VNF 节点资源总量固定的情况下，所能服务的业务总量得到增加。此外，可以观察到，在2 种网络拓扑中，JRRA-MLT 算法的性能仅比JRRA-ILP 算法降低了10%左右，这证明了所设计的基于多层网络拓扑的服务链路由算法能有效地寻找到可行且端到端时延相对较小的服务链路由路径。考虑到基于多层网络拓扑的服务链路由算法计算复杂度更低，该算法适用于大规模网络拓扑，并能取得与最优结果近似的性能表现。

1) 服务链长度的影响

首先评估了服务链长度对算法性能的影响。本文测试了4 种不同范围的服务链长度，分别是(1,2]、[3,4]、[5,6]和[7,8)。评估结果展示在图8 和图9 中。可以观察到，在2 种不同的实验网络拓扑中，随着服务链长度的增加，接收的业务总量均减小，造成这一现象的原因有以下2 个。首先，服务链长度的增加意味着服务链中包含的VNF 数量的增加，则接收相同大小的服务链将消耗更多的VNF 节点资源，因此，在物理节点资源总量一定的情况下，随着服务链长度的增加，接收的业务总量下降。第二个原因在于，随着服务链长度的增加，意味着服务链路由长度的增加，即服务链所经过的物理链路数量增加，这导致服务链端到端时延组成中的交换机时延和链路时延的占比提高，从而导致最大允许的VNF 节点时延降低。因此，服务链需要占用更多的VNF 节点资源来降低VNF 节点的时延。在这双重原因叠加下，接收的业务总量迅速下降。

2) 物理节点对VNF 类型的支持率的影响

假设每个底层物理节点只能支持部分的VNF类型，将物理节点上支持的VNF 类型数量占网络中VNF 类型的总数量定义为物理节点对VNF 类型的支持率，默认情况下每个物理节点的VNF 类型支持率为70%。这里评估物理节点对VNF 类型的支持率对业务接收总量的影响。从图10 和图11 中可以看出，2 种算法接收的业务总量均随着物理节点对VNF 类型的支持率的上升而增加。这可以通过多层网络拓扑进行解释，当物理节点对VNF 类型的支持率上升时，同一种类型的VNF 将在更多的物理节点上得到支持，这意味在服务链路由的过程中，多层网络拓扑的层与层之间的连接链路数将增加。如此，在源点和终点之间存在更多的可行路径可供选择，则找到端到端时延更小的服务链路由路径的概率也越大。当服务链路由路径的端到端时延越小时，最大允许的VNF 节点时延将增加，服务链对VNF 节点资源的占用将降低，从而更多的业务请求可以被接收。

3) 业务时延要求的影响

接下来，进一步研究业务时延要求的影响。默认情况下，业务的时延要求在[20,100]ms 中随机生成。在产生业务请求的过程中将时延的要求固定，探究设置不同业务时延需求时接收的业务总量的变化。图12 和图13 显示，随着业务时延要求的上升，接收的业务总量也会增加。这一点很容易解释，根据算法1 第7 行，当业务的时延要求较大时，在服务链路由路径不变的情况下，最大允许VNF 节点时延变大。在上文也多次讨论过了最大允许VNF节点时延变大将增大接收的业务总量。此外，观察到在网络拓扑1 中，当业务时延要求设置为20 ms 时，接收的业务总量显著下降。这是因为网络拓扑1 的规模较大，当业务时延要求设置为20 ms 时，部分业务因找不到可行的服务链路径而被直接拒绝（算法2 中第7～8 行）。由于网络拓扑2 的规模较小，这种情况并未发生。

4) 业务在线到达场景下算法性能

最后，评估业务在线到达场景下算法的性能表现。由于不能提前得知全部业务请求的信息，因此无法对业务请求进行排序。每到达一个业务请求，运行算法对业务进行部署，若无法找到满足业务时延的部署方案，则业务请求被拒绝。图14 和图15展示了随着累计到达的业务请求数量的增加，接收的业务总量的变化。可以看到，在前期业务请求到达时，JRRA-ILP 和JRRA-MLT 算法均能为业务找到可行的部署方案而接收业务请求，从而2 种算法的性能表现一致。随着接收的业务数量逐渐增加，由于JRRA-MLT 算法比JRRA-ILP 算法在接收同一个业务请求时将消耗更多的VNF 节点资源，从而导致JRRA-MLT 算法更早地耗尽了VNF 节点资源。例如，在网络拓扑1 中，当第600 个左右的业务请求到达时，JRRA-MLT 的业务接收率开始下降，接收的业务总量开始落后于JRRA-ILP。

7 结束语

远程医疗、自动驾驶、工业自动化等业务对网络端到端时延的要求更加严格。本文研究了DSC的部署问题，旨在为网络业务中的服务链提供端到端时延严格保障的同时，最大化接收的业务总量。本文将网络演算运用于服务链的端到端时延计算中，实现为业务提供严格的端到端时延保障；将DSC 部署问题建模为混合整数非线性规划问题，并将该问题拆解为服务链路由子问题和VNF 节点资源分配子问题；将服务链路由子问题建模为可解的线性规划问题，同时也提出了一种高效的启发式法。此外，理论推导了VNF 节点的最佳资源分配值。最后，通过实验验证了所提算法的性能，结果显示所提算法在性能表现上与最优解接近。

本文研究成果在未来有望运用于部署了虚拟网络功能的5G 核心网中，为远程医疗等业务提供确定性时延保障。不过在实际生产环境中设计解决DSC 问题时，需要进一步考虑VNF 实例的不同类型的服务曲线以及不同的部署模型，这也是DSC问题未来的研究方向。