联合路由规划的时间敏感网络流量调度方法

裴金川，胡宇翔，田乐，胡涛，李子勇

（信息工程大学信息技术研究所，河南 郑州 450002）

0 引言

近年来，网络中多样化应用业务不断出现，实时控制、沉浸式交互、边缘计算等应用领域提出了低时延、低抖动的确定性传输需求[1]。例如，银行高频交易要求时延控制在1 ms 以内，自动驾驶的时延需求为100～250 μs，工控网络中要求毫秒级时延和微秒级抖动。随着信息技术的飞速发展，未来网络中将会衍生出更多毫秒级乃至微秒级时延的业务需求。

然而，传统以太网采用的尽力而为分组转发机制具有长尾时延效应，难以满足上述业务场景中的有界低时延需求[2]。为实现确定性有界低时延的网络数据传输，学术界和产业界已经开始在面向用户需求的新型网络[3]基础研究和关键技术上攻坚布局，时间敏感网络（TSN,time-sensitive network）作为一种新型的网络数据传输技术[4]，可以支持时间敏感流量、尽力而为流量等多类型流量共同传输，全局规划调度不同类型流量并在输出端口消除冲突依次传输，保障时间敏感流量在时延、抖动和可靠性等方面的确定性传输需求[5]。

TSN 工作组致力于在传统以太网的基础上实现流量的确定性转发，修订了IEEE 802.1AS 时钟同步[6]、IEEE 802.1Qbv 流量调度[7]、IEEE 802.1CB可靠性保障[8]和IEEE 802.1Qcc 网络配置[9]等一系列机制的标准。

作为TSN 的核心机制，流量调度是保障TSN数据传输的关键环节[10]。学术界针对具有严格周期性要求的时间敏感流量调度展开了大量的研究，文献[11]采用基于拓扑修剪和谱聚类的分组调度策略，可保证在大规模流量场景下具有较高调度成功率的同时降低调度时间。文献[12]结合TSN 的流量特性设计了一种基于混合遗传算法的调度计算方法，提出的调度压缩机制可以提供更优的带宽分配。为保证网络更新过程的数据传输一致性，文献[13]结合软件定义网络建立了一个新的整数线性规划调度模型，该调度模型中采用的离线调度和在线调度2 种方法均实现了零帧丢失。

此外，流量的可调度性不仅取决于上述研究中对TSN 门控的配置及时隙的映射，良好的路由策略同样可以突破调度瓶颈[14]。研究人员针对时间敏感网络的流量路由已经进行了大量的探索，文献[15]采用了K 最短路径算法进行时间敏感流量路由的选取，并应用贪心随机自适应搜索得到解决方案，但仅凭路由跳数进行路由规划会导致链路拥塞及调度超时。文献[16-20]均强调了时间敏感流量的路由选择对实现低时延低成本的调度具有重要作用。其中，文献[16]通过定义网络链路成本和流量时延优化TSN 拓扑和流量路由以确定冗余链路，使时间敏感流量的路由传输具有容错保障，但冗余传输的保障需要较大的资源开销。文献[17]提出一种调度感知路由算法，即改进Dijkstra 算法，对传输路径设置权重来确定每条时间敏感流的路径。文献[18]分析了时间敏感流量之间的结合性，提出了一种路由感知的方法，通过评估不同周期流量的可组合性以减少流量调度的瓶颈，但对流量分组调度的粒度较粗，难以精细化把控全局流量的调度时延。文献[19]在整数线性规划的基础上提出了基于最大调度流量负载的路由算法以实现最小化流量负载和流量路由跳数的目标，相比最短路径算法提高了60%的可调度性。文献[20]利用时间敏感软件定义网络架构设计了时间敏感流量的增量调度方法，采用最短路径和均衡链路可用容量2 种路由算法计算时间敏感流量的调度配置。文献[21]针对TSN 中的时间敏感流量提出了一种实时路由调度算法，将到达流量的周期升序排列后，通过计算最坏端到端时延为新到达流生成调度路径，且不影响已经调度成功的流量，保证全局流量在截止时间内全部完成传输。Ojewale 等[22]针对时间敏感网络提出了一种链路负载均衡的路由策略，将最小化全局链路负载作为优化目标，但在流量路由时未考虑可能导致流间冲突的因素。

目前，关于TSN 流量调度的研究多基于最短路径等给定的路由方案[11,15,23]，然而采用最短路径优先（SPF,shortest path first）路由算法时，虽然每条时间敏感流按照最少跳数传输，但在单一链路上传输多条时间敏感流时，发生流间冲突导致排队拥塞甚至丢包的可能性较大。调度与路由联合规划是TSN 流量调度发展的主要趋势[10]，现有的联合路由调度研究中考虑了路径长度和传输跳数等路由指标[20,24]，但并未结合时间敏感流量的发送周期、流量负载等特性进行调度，可能导致多条时间敏感流分配到同一条传输链路上发生时隙争用。

上述流量路由调度机制的研究从调度约束的角度对TSN 流量进行传输设计，此处的TSN 流量类型均为时间敏感流量，即具有低抖动和有界低时延传输需求的周期性实时流量。因此，关于TSN 流量的路由调度的研究在考虑调度约束和路由指标的基础上需要进一步考虑流量本身的特性，并结合TSN 流量的传输机制研究解决方案才能取得更优的流量调度性能。

综上分析，现有研究存在以下不足。1) 现有调度方案忽略了网络中部署时间敏感流量之间的路由冲突和依赖关系，使时间敏感网络全局的通信调度能力受到限制。2) 联合路由调度研究中未考虑流量本身特性，只是简单根据路由指标规定流量路径，导致流量调度时延性能难以得到保证。

为此，面向时间敏感网络中时间敏感流量的联合路由调度问题，本文基于时空联合规划的思想，多维度规划TSN 流量调度，即在空间上进行无冲突（CF,conflict-free）路由规划，时间上联合路由对流量整形约束调度，提出了一种联合无冲突路由的多约束流量调度方法，具体研究内容如下。

1) 概述了时间敏感网络的系统模型，并对时间敏感流量传输时延的构成和流量调度时发生路由冲突的情况进行分析。

2) 针对目前时间敏感网络中流量调度与路由分离的问题，设计了一种时间敏感流量调度与路由联合规划的策略，考虑流量之间的路由冲突和依赖关系，通过定义流间冲突度函数，灵活分配流量路由以避免网络队列冲突丢包，在均衡链路负载的同时获得更优的流量传输时延性能。

3) 根据时间敏感网络的时间感知整形机制，在考虑路由指标的基础上结合影响时间敏感流量传输的周期及负载等因素，以降低时间敏感流量传输时延为目标，基于时分多址（TDMA,time division multiple access）的思想设计了联合路由的流量调度约束。

4) 仿真结果表明，与经典调度方法对比，本文方法可以很好地适应不同网络拓扑环境，在保证网络链路低负载的同时为时间敏感流量提供确定性低时延服务。

1 TSN 模型

1.1 网络模型

本文将时间敏感网络抽象建模为无向图G=(V,E)，其中，V=H∪S为时间敏感网络中所有的节点集，H为发送和接收两类终端节点，S为时间敏感交换节点；E为2 个节点连接组成的链路集，(vi ,vj)∈E，vi和vj分别为源节点和目的节点。图1 为网络拓扑示例，其中包含9 个节点和9 条链路，2 个终端节点之间的路由用多个不同链路的集合表示，其中ri={[H1,S1],[S1,S2],[S2,H3]}表示由终端H1到H3的一条路由。

图1 网络拓扑示例

1.2 通信模型

时间感知整形机制如图2 所示，采用TDMA的思想，将流量传输的通信时间分割为若干个传输周期，每个传输周期又划分为若干个时间片。网络中所有数据帧经过传输选择后，结合门控制策略控制传输的时间偏移量，每个时间感知门都有2 个状态，决定队列中排队的帧是否进行传输，状态为0表示门关闭不允许传输数据，状态为1 表示门打开可以传输新到达的数据流。每个时间片对应的门状态由门控列表决定，故时间整形机制可通过为高优先级的时间敏感流量提供确定的传输时隙来保证确定的端到端传输时延。

图2 时间感知整形机制

传播时延dtran、处理时延dproc、排队时延dqueu和发送时延dprop共同构成了时间敏感流量在两节点之间传输的端到端时延D，如式(1)所示。

时间敏感网络的高精度、高可靠流量传输依赖于全局的时钟同步和流量调度时隙的精确规划，考虑到本文主要研究时间敏感网络的流量调度，假设TSN 中设备已完成全局时钟同步，且信道中数据的发送速率一致，均为1 Gbit/s，交换机处理时延为1 μs。流量传输过程的时延构成中，排队时延具有较大的不确定性，故时间敏感流量调度在进行全局门控规划时应避免流量排队或降低排队时延。

时间敏感网络中流量传输时间的精确控制依赖于门控列表中对时隙的划分，门控列表由各流量传输周期驱动控制，由于网络中部署的流周期不同，故将所有时间触发流周期的最小公倍数作为传输的超周期hp。超周期为TSN 门控列表调度循环的单位，如式(2)所示。

每条时间敏感流在超周期内的传输次数为

2 联合路由调度策略

由于TSN 流量调度规划时可能发生流间冲突导致时隙争用[25]，本文将TSN 中的时间敏感流量的调度与路由联合规划。联合路由调度策略由排序、无冲突路由和联合调度3 个阶段组成，排序阶段将流量按周期和负载排序，筛选出周期较小、负载较大的时间敏感流量为优先路由；无冲突路由阶段在路由规划的过程中考虑产生调度冲突的因素，以时延为指标确定启发式评估函数，目标为得到时间敏感流量的无冲突路由，通过对网络中节点的搜索，选取全局时延代价值最小的节点作为路由节点，依次搜索到目的节点后的路径即最优的时间敏感流量路由选择；最后进行联合路由的全局调度约束规划，尽可能降低流量传输时延等调度指标，在增大调度解空间的同时获得最小化的端到端时延。

2.1 无冲突路由规划

IEEE 802.1 Qca 中，TSN 的时间敏感流量默认采用最短路径进行传输，文献[26]表明，TSN 系统中时间敏感流量若采用最短路径优先路由，在交换设备和链路上传输时则可能发生路由冲突或链路故障，产生不确定时延甚至丢包，并不能实现低时延的最优调度。

图3 为时间敏感流间冲突示例。时间敏感流f1、f2和f3的周期分别为100 μs、150 μs 和300 μs，数据大小分别为3 000 B、4 500 B 和8 000 B，在300 μs 的一个超周期内，f1发送3 次，f2发送2 次，f3发送一次，若不进行路由调度直接选取最短路径传输，不同时间敏感流间发生冲突拥塞的概率较大，如f1和f3均路由到 [S1,S2]链路且需要在同一时隙内完成传输，当f1到达交换机S1时，由于f3尚未发送完成，可能与f1发生冲突丢包；若将f1缓存在当前队列中，待其到达目的节点时可能已超过端到端响应截止时间，同样无法满足TSN 的时延调度要求。

图3 时间敏感流间冲突示例

为避免调度时发生冲突丢包，本文提出一种无冲突路由规划方法，综合考虑当前路由节点的已有代价和当前节点到目的节点的预估代价，不同于盲目随机路由搜索，可以优化传输路径的选择与搜索效率。设置无冲突路由规划的全局代价函数为l(n)=g(n)+h(n)，其中，g(n)为当前代价函数，表示从源节点到当前节点n的代价；h(n) 为启发式评估代价函数，表示从当前节点n到目的节点的预估代价。

联合无冲突路由调度的核心思想是考虑时间敏感流量调度过程中可能引发冲突的因素，筛选TSN 中未访问的路由节点，获得最小的全局代价函数值后依次确定无冲突调度的最佳路由节点。结合TSN 的时延敏感特性，设置当前代价函数g(n) 为第i条流传输到中间节点时已产生的传输时延，即端到端时延D。

联合路由调度的方法应尽量将时间敏感流量分散到不同路径的不同时隙以避免流间冲突。本文基于路径集相似度[11]，结合时间感知整形机制及时间敏感流量特征，定义流间冲突度函数为

其中，max(f .S) 和min(f.T) 分别表示本次调度流量集合中的流量负载最大值和流周期最小值。结合时间敏感流量特性，表示任意2 条具有重叠路径的流之间发生最大调度冲突的程度。

式(4)表示任意2 条不同流fi与fj之间的冲突度Ci,j受路径重叠数量|pi∩pj |、帧大小fi.S和帧周期fi.T这3 个因素影响。若待调度流源节点和当前节点的路径与其他流的传输路径存在重叠，则帧发送周期越频繁且流负载越大的2 条流之间越容易发生拥塞冲突，该重叠路径的启发式评估代价越高。

当路径重叠程度为0 时，表明不与任何其他流发生调度冲突；若2 条流之间所经过的链路发生重叠，规划调度时便有发生冲突的可能，故选取流间冲突度最大值与其传播时延的乘积进行时延预留，冲突预留时延为

本文方法中的启发式评估代价函数设定倾向于接近实际的代价值，设置评估代价函数以调度时延为指标，若代价值越接近实际的传输时延，则无冲突路由规划的效果越好。由于无冲突路由规划的目标是得到最优路径，但启发式评估代价函数值作为路径时延评估代价，并非最终调度的端到端时延值，故假设流量到达当前中间传输节点时，后续链路的传输时延为采用SPF路由传输到目的节点所产生的预估时延D*，则启发式评估代价函数h(n) 为

综上，本文针对时间敏感流量无冲突路由规划的全局代价函数为

无冲突路由规划策略的流程如图4 所示，其中open 列表（openlist）存放路由过程中未访问的节点，close 列表（closelist）存放已访问过的节点。通过查找比较TSN 中当前时间敏感流量的所有路由节点代价值，选取出open 列表中代价值最小的节点作为路由节点。

图4 无冲突路由规划策略的流程

应用无冲突路由规划后，图1 中的f3选择{[S1,S3],[S3,S4]}这一中间交换链路，即可避免与f1之间发生调度冲突，且每条流均满足端到端截止时延要求，如图5 所示。

图5 时间敏感流间无冲突示例

2.2 TSN 传输调度约束

虽然IEEE 802.1Qbv 标准中定义了TSN 的门控策略，但并未规定具体的门控调度方法。为保障时间敏感网络调度的低时延低抖动特性，在2.1 节无冲突路由规划的基础上，本节设计了时间感知整形调度约束和联合路由调度约束。

2.2.1 时间感知整形调度约束

由时间感知整形机制可知，TSN 中时间敏感流量的传输过程中具有逐跳的确定性时延，本节根据流量传输的帧偏移量及占用时隙，定义了如下约束保证时间敏感流量的确定性调度时延。

1) 帧偏移约束

时间敏感网络中流量传输的帧偏移量不能早于传输开始时间，且应在其流周期内完成传输。本文假设全局最早传输开始时间为0，此外，将帧偏移量约束在周期范围内，可以减少流偏移的搜索空间，帧偏移约束为

2) 端到端时延约束

为保障服务传输质量，接收端接收与发送端发送的流之间的时延必须小于或等于规定的最大端到端响应时延，否则调度失败。引入端到端时延约束来规定发送端和接收端之间的时延，即

其中，θ表示网络时钟同步的精度偏差。

3) 周期性约束

根据时间敏感网络中时间触发流量的周期性特性，同一终端设备的所有时间敏感数据流需要周期性发送，且每2 条流之间需要间隔固定的周期时长，即同一条流的同一帧发送偏移时间相同，如式(10)所示。

4) 流抖动约束

时间敏感网络中的周期性通信需要对流量传输抖动进行约束，由于在接收端对流量传输的低抖动服务质量较敏感，对中间节点的传输抖动感知较弱，故此处的流抖动约束仅针对接收端前最后一跳的发送节点，如式(11)所示。

其中，帧传输时间Wi,j为fi的数据帧j在最后一跳的到达时间减去第一跳的发送时间。取同一条流任意2 个帧传输时间的差值，判断是否小于流抖动最大约束值。

流抖动约束通过流量传输过程中最后一跳与第一跳的时间差值以控制时延抖动上限。若用户对网络传输过程中的中间节点时延抖动有定制化服务需求，可将流抖动约束进一步扩展到中间节点。

2.2.2联合路由调度约束

本节综合时间和空间因素，在设计无冲突路由约束时考虑时隙约束，设计了联合路由的调度约束。

1) 路径顺序约束

若时间敏感交换机没有收到前驱链路发来的数据帧，则无法处理并转发该数据。数据流在链路中传输时必须遵循既定的顺序，即同一条流在当前链路的传输结束时间必须小于或等于这条数据流在后续链路数据传输的开始时间，即

2) 多播约束

为实现时间敏感网络的无缝冗余机制，时间触发流需要在发送端或之后的某一节点复制多个副本同时发送到不同的传输分支链路中。

3) 帧隔离约束

在实际的网络传输过程中，若多条流在交换机的同一队列中同时到达后发生排队，则会产生拥塞冲突导致丢包，无法保证端到端时延的确定性，故需要约束同一队列内传输的任意2 条数据流的帧之间不产生交错重叠，不同时占用同一调度周期的同一时隙资源。

当2 条来自不同前驱链路的流同时到达交换机时，若无帧隔离约束则可能发生包乱序或丢包[27]，可采用按时间隔离的方法对其转发时间进行约束，即控制前一交换节点队列的开门时间，数据流经过交换机转发到后续链路时，此交换节点的前驱链路数据才能进入队列，即队列中同一时刻只能容纳一条数据流，如图6(a)所示；若队列资源充足，可采用按空间隔离的方法，将同时到达的2 条流分配给不同的队列，控制队列的开门时间从而实现不同数据流的空间隔离，避免数据帧交叉冲突，如图6(b)所示。

图6 帧隔离示意

帧隔离约束可表示为

4) 链路无冲突约束

在同一传输链路传输的任意2 条流需要满足在相同时隙内无重叠的要求，即流相互之间不对同一链路资源进行竞争，保证两者的发送顺序在空间上没有冲突。

2.2.3优化目标

综合上述约束，时间感知整形机制下的时间敏感流量可以在时间和空间2 个维度实现无冲突传输，为满足时间敏感流量全局传输中具有上界的低时延低抖动的服务质量要求，本文将最优化目标设为最小化所有时间敏感流量的最坏端到端传输时延之和，即尽可能降低每条时间敏感流的传输时延上界，如式(16)所示。

其中，帧传输时间Wi,j为数据帧j在最后一跳的到达时间与第一跳的发送时间之差，并由式(8)～式(15)约束。

2.3 算法设计

联合无冲突路由调度方法的整体流程如算法1所示，输入为所有待调度的时间敏感流量集合F及网络拓扑结构G，输出为每条时间敏感流的无冲突路径Ri、传输路径中每个节点交换机的发送时间及流量端到端时延Wi,j。

算法1联合无冲突路由调度

路由规划中，根据每条时间敏感流量的初始偏移时间、负载、周期等变量计算出无冲突路由决策结果。首先，根据当前节点n到源节点的传输时延得到当前时延代价值g(n) 。然后，根据流间冲突度函数得到冲突预留时延Dc，与后续预估时延D*共同组成启发式评估代价（步骤3)～步骤6)）；得到全局代价值l(n) 后筛选出openlist 中值最小的节点n，若节点n不是目的节点，将其邻接节点加入openlist中并将节点n移入closelist（步骤7)～步骤12)），循环上述步骤直到筛选出当前流的无冲突路由（步骤14)），并把当前流的调度约束条件式(8)～式(15)加入全局约束集合中（步骤15)）。最后，根据目标函数对TSN 中的全局流量约束求解调度得到调度结果（步骤17)～步骤20)）。上述算法流程只需遍历待调度的时间敏感流量集合，依据无冲突全局代价值对网络交换节点进行有限次数搜索后即可得到可行的无冲突路由，最终通过多约束求解出最优的联合路由调度决策。

算法复杂度分析如下。对时间敏感流量集合中所有流量依次遍历，其时间复杂度为O(n)，对每条流规划无冲突路由时的复杂度也为O(n)；TSN 中共有n个交换节点，故对应的openlist 和closelist 最大也为n，可得算法空间复杂度为O(n)。综上，联合无冲突路由规划算法的时间复杂度为O(n2)，空间复杂度为O(n) 。

3 实验与结果分析

3.1 实验平台及参数设置

本文仿真实验使用 IBM ILOG CPLEX Optimization Studio 和MATLAB2018b，运行在具有Intel(R)Core(TM) i7-10700 2.90 GHz CPU 和 32 GB RAM的Windows 计算机上。

当前针对时间敏感网络流量调度尚未有标准的流量数据集，因此仿真中的周期性时间敏感流量数据根据网络场景随机生成，随机选取2 个不重复的终端节点为流量的源节点及目的节点，依据DetNet 用例标准[28]中的工业互联通信流量特性指导，设置实验所用时间敏感流量数据包负载大小fi.S为100～ 4 500 B，发送周期fi.T为80～500 μs，为保证时间敏感流量调度验证的有效性，设置截止时间fi.Dmax小于该流的发送周期，则图1中的时间敏感流f1可表示为元组{H1,H3,0,1 000B,150μs,120 μs,5μs} 。网络中的物理传输链路的时间粒度和速度分别为1 μs 和1 Gbit/s。

为验证本文提出的联合CF 路由调度方法，在仿真实验中将CF 调度方法与动态最短可用路径（D/SAP,dynamic/shortest available path）方法[20]、动态最小化链路最大占用（D/MM,dynamic/mini-max）方法[20]和实时路由调度（RTRS,real-time routing scheduler）方法[21]进行对比。D/SAP 方法最小化时间敏感流量路由的链路数量；D/MM 方法旨在最小化网络中的最大负载率，将链路负载较均匀地分布在所有链路上；RTRS 方法将流量按周期升序排列后，计算得到流量最坏端到端时延最小的路径作为时间敏感流量路由。

3.2 不同网络场景下的性能验证

时间敏感网络技术多应用于局域网，先前研究中多选取线形、环形和星形等工业控制网络中的常见的简单拓扑结构进行实验[25.29]，为验证本文方法在不同网络拓扑场景下的适用性，采用文献[30-31]的拓扑类型，随机生成Barabási-Albert 网络[32]和Erdős-Rényi 网络[33]进行仿真验证，所需的网络拓扑参数如表1 所示。

表1 不同场景的网络拓扑参数

当时间敏感流数量为10 和20 时，不同拓扑场景下不同调度方法的平均端到端时延如图 7所示。从图7 可以看出，采用D/SAP 方法的平均调度时延最大且拓扑适应能力最差，在 ER2拓扑场景下流数量增加到20 条时，与其他拓扑场景的平均端到端时延差值最大高达77.3 μs。所提CF 调度方法表现出最优的调度适应能力，其可以根据时间敏感流量特性综合时间和空间2 个维度以避免流间冲突，在表1 所示的4 种拓扑验证下，其平均端到端时延均保持在70 μs 以内，整体时延浮动均小于20 μs。而采用D/MM和RTRS 方法虽然可以平衡TSN 链路上传输的时间敏感流数量分布，但调度过程中无法结合流量传输偏移时间及周期等时间敏感特性，且D/MM 方法对非对称的网络拓扑和负载差异较大的流量感知能力较差，无法最大限度地避免流间冲突。

图7 不同拓扑场景下不同调度方法的平均端到端时延

综合以上4 种拓扑环境及流量调度时延可得，CF 调度方法的拓扑适应能力最佳，相较于表现较好的RTRS 方法，CF 调度方法在时间敏感流数量为10 和20 时分别可以将平均端到端时延降低6.23%和24.07%，且当流数量为20 并采用ER2拓扑进行传输验证时，平均端到端时延降低37.55%。

因此，本文的联合无冲突路由调度方法能在不同网络场景下降低时间敏感流量的调度时延，且不同网络场景下的端到端时延抖动较小，具有较强的拓扑适应能力。

3.3 不同流量规模下的性能验证

时间敏感网络所应用的工业控制、车载网络等场景具有节点复杂、链路交错等特性，为更好地验证本文所提出联合路由规划流量调度方法的有效性，应选取多节点复杂网络拓扑。本节选取CEV（crew exploration vehicle）网络拓扑[34]进行实验，CEV 网络拓扑作为典型且重要的TSN 应用场景，已经在多数TSN 时间敏感流量调度的相关研究[13,21]中作为实验测试拓扑。CEV 网络拓扑结构如图8 所示，包括31 个终端节点和15 个交换节点，满足联合路由调度实验的拓扑节点需求。

图8 CEV 网络拓扑结构

3.3.1不同流量规模对链路负载的影响

不同流量规模对链路负载的影响如表2 和表3所示。由于本文联合路由调度的流量类型仅针对时间敏感流量，在实际的时间敏感网络环境中，若时间敏感流量所占负载较高，则对其他类型的低优先级流量的传输造成过多的时隙抢占，且无法保障时间敏感流量的交付质量[35]，故TSN 的流量调度规划应在保障时延性能的前提下尽可能地预留更多的链路资源。

表2 最大链路负载率

表3 平均链路负载率

由表2 和表3 的实验结果可知，联合无冲突路由调度方法相较于D/SAP 方法，最大链路负载率均有大幅度降低，当流数量仅为5 时，最大链路负载率由32.27%降低至16.27%，且随着流数量增加，采用CF 调度方法的最大链路负载率增幅平稳且较小。RTRS 和D/SAP 方法的链路负载率表现差于D/MM方法。当流数量小于30 条时，联合无冲突路由调度与D/MM 方法所产生的最大链路负载率和平均链路负载率相当；当流数量继续增加时，联合无冲突路由调度的最大链路负载率和平均负载率均低于D/MM 方法，当流数量为40 时，最大链路负载率同比D/MM 方法降低了12.06%，原因是D/MM方法仅考虑链路数量及所流经的时间敏感流量自身属性，而联合无冲突路由方法通过时间敏感流的周期及负载大小计算流间冲突并预估调度时延，从而在流数量较多时避免多条流量拥塞以优化链路中流量分布。

在时间敏感网络中分别选取20 条和40 条时间敏感流量进行全局调度时，网络中所有活跃链路负载率累积分布函数如图9 所示。与D/MM 方法一样，采用联合无冲突路由调度可使交换链路的最大负载率均保持在40%以下；且当流数量由20 条增长到40 条后，联合无冲突路由调度方法可使全局98.9%的链路负载率仍保持在30%以下，整体链路负载并无较大变化，且相较于其他方法，网络中的每条活跃链路的负载分布更加均衡。因此，当网络中流量规模增长时，采用本文方法不会造成链路的瞬间拥塞，保证了流量部署的稳定性。

图9 活跃链路负载率累积分布函数

3.3.2不同流量规模对端到端时延的影响

本文已验证了采用本文方法所产生的链路负载性能可与D/MM 方法持平甚至更优。由于D/MM 方法对流间冲突的感知能力较差，仍可能导致流间冲突影响调度时延性能。为了探究本文方法在不同流量规模下对流量端到端时延的影响，本节在CEV 拓扑下验证了4 种方法的平均和最坏端到端时延，结果如图10 和图11 所示。采用RTRS、D/SAP 和D/MM 方法时，随着网络中流量规模的增大，新增加流量的部署难度增加越来越大。在时间敏感网络部署中的流量逐渐增加到40 条的过程中，采用联合无冲突路由调度的方法所产生的平均端到端时延可以在60 μs 内小幅度平稳增长，最大波动仅为6.03%，最坏端到端时延增长波动也仅为7.18%。表现次优的D/MM 方法产生了最大为15.12%的平均端到端时延增长波动和13.83%的最坏端到端时延增长波动。采用D/SAP 方法产生的平均及最坏端到端时延波动则达到了22.46%和26.40%。当流数量小于20 条时，RTRS 方法调度时延性能略优于D/MM 方法，但随着流数量的增加，RTRS 方法会影响后续流量的时延性能，故不适用于时间敏感流数量较多的场景。

图10 平均端到端时延

图11 最坏端到端时延

显然，当网络中部署的时间敏感流量规模增长时，采用本文方法进行流量调度所产生的平均和最坏端到端时延增长平稳，故相较于其他方法所产生的大幅度波动时延增长，本文方法可以在不同规模的时间敏感流量下实现部署调度的低时延稳定性。

4 结束语

本文针对时间敏感网络中时间敏感流量的调度与路由分离问题，采用时空联合规划的思想，提出了一种联合无冲突路由规划的调度方法，时间上基于时分多址的技术建立时间敏感流量的调度约束模型，空间上结合时间敏感流量调度特性，为时间敏感网络的联合路由规划调度提供了新的解决思路。在不同网络场景和不同流量规模下进行流量调度验证，实验结果表明，所提的联合无冲突路由调度方法能适应不同类型的时间敏感网络拓扑场景，与现有的最短路径优先和负载均衡路由调度方法相比，可以实现全局时间敏感流量部署的低时延稳定传输。

后续工作中，为实现TSN 中多类型流量的融合增量传输，可以尝试在待完善的时间敏感数据集标准下调整评估函数，设计网络资源利用的优化方案并得到全局网络门控的配置。