机载时间敏感网络流量调度算法性能研究

孔 璇，张 双，刘智武

(中国航空工业集团公司 西安航空计算技术研究所，西安 710068)

0 引言

在硬实时通信系统中，消息传输的最大延迟必须得到保障且不能容忍任何的数据丢失[1]。严格的时间确定性，即确定的网络时延和抖动，对于机载系统中的安全关键应用是至关重要的。某些带有关键控制信息的数据帧需要按照一定时间周期进行传输，一旦时延和抖动超过了上限，可能导致严重的机器、设备损坏及人身伤害。基于不同的设计思想，目前应用在机载网络的确定性以太网主要有基于时间触发以太网(TTE, time-triggered ethernet)和时间敏感网络(TSN, time sensitive network)。

在TTE网络中，消息被划分为时间触发(TT, time-triggered)消息、速率受限(RC, rate-constraint)消息和尽力而为(BE, best-effort)消息[2]。通过对链路资源预先规划和静态时间调度表的设计[3]，实现TT、RC和BE消息在同一网络中的数据转发，保证了时间触发流量的延时是可控的，并且固定在一定的范围内[4]。TTE能够精确描述网络中各种消息的调度行为，但是实现较为复杂，并且TT业务的分组调度是根据时间调度表对缓存空间的读写操作，并没有采取基于排队理论的网桥实现，和传统以太网的转发交换的具体实现和设计思想存在较大差异[5]。

TSN是由以太网音视频桥接(AVB, audio video bridging)网络演进而来的[6]，其通过时钟同步、流预留、循环排队、门控列表和抢占等机制保证了数据流的有界低时延。该技术的核心是以时间感知整形(TAS, time-aware shaper)和帧抢占为代表的流量调度算法。

TAS引入了时分多址(TDMA, time division multiple access)的思想，通过门控时间表(GCL, gate control list)控制队列门控开关的打开闭合，在链路上创建独享的保护窗口[7]，使时间敏感业务在保护窗口内无干扰地传输，从而提供确定的时延[8]。TAS的研究包括最坏情况分析和调度合成。通过最坏情况分析，可以得到通信系统的时延上限。文献[9]研究了基于IEEE 802.1Qbv的预定流量时间感知，结果表明，TAS可以支持非常低的延迟以及抖动保证，同时，利用帧抢占机制，可以增强整形器的性能；考虑到相同优先级帧间干扰的问题，文献[10]分析了TAS与基于信用值的整形器(CBS, credit-based shaper)的组合性能。然而，基于模拟和形式的方法并不能解决TSN的配置问题[11]，应通过调度合成提高网络通信的确定性。文献[12-13]指出，调度合成是通过计算传输路由和GCL共同实现的。

帧抢占允许高优先级流量中断低优先级流量的传输，减少高优先级的阻塞时间，解决了保护窗口过长引起的带宽浪费问题。文献[14-15]分析了帧抢占调度的优势并给出了时延及抖动性能的优化方法。

上述文献试图采用商用的TSN数据流传输场景进行网络仿真，评估流量调度机制对网络确定性的影响，且要求应用和网络完全同步，没有针对不同关键等级的机载业务给出量化的性能评估。针对上述问题，通过探索TAS和帧抢占算法的特征，推导出一个数据流传输时延的数学模型，使用开源TSN网络仿真平台，评估了TAS和帧抢占在机载应用场景下的性能结果，分析算法在可靠性、通信性能和适用场景的不同。

1 TSN系统模型

1.1 交换架构

IEEE 802.1Q标准中规定了TSN交换机架构，如图1所示，TSN交换机的每个全双工端口都配置了8个优先级队列。到达交换机的数据帧在转发到出端口之前，要经过过滤、计时。出端口的8个队列对应不同的流量类别，交换机根据优先码将数据帧分配给出口队列，传输选择(TS, transmission selection)从优先级最高的队列头部选择符合条件的数据帧，发送到链路上，如果队列整形器的时隙与数据帧配置相符，则允许数据帧传输。TSN工作组规定了各种不同的整形器，如严格优先级和基于信用的整形器(IEEE 802.1Qav)。如图2所示，TAS是在其他整形器之后生效的，通过TS后，MAC负责传输数据帧，这里就涉及到帧抢占机制。

图1 TSN交换机架构

图2 出端口传输选择(TS)和门控开关

1) 时间感知整形器：TAS是出口队列的一个门控开关，分为基于流的TAS和基于类的TAS，通过打开或关闭对应的出口队列来启用或禁用它，只有启用的队列才能进行数据流的传输。驱动程序根据GCL来周期地改变门控开关的状态。GCL中规定了门控开关的开启时间和保持时间，GCL循环一次所需的时间与网络周期时间相同。

2) 帧抢占：帧抢占采用了IEEE 802.1Qbu和IEEE 802.3br的抢占式MAC传输机制，将出端口分为2个MAC服务接口，即快速MAC(eMAC, express MAC) 和可抢占MAC(pMAC, preemptable MAC)。如图3所示，pMAC可被eMAC抢占，进入队列后，等待eMAC数据传输完成后，再传输pMAC数据。如果没有帧抢占，一个最大传输单元(MTU, maximum transmission unit)帧(1 500字节) 在1 Gpbps速率下，能够阻塞端口约12.5 μs，而帧抢占将最大阻塞时间限制为1 μs。如果发生了抢占，被抢占帧的剩余部分的数据负载将重新整合成新的帧，称为分片，其长度至少为64字节。端口的出口队列分为快速队列或可抢占队列，分别在eMAC和pMAC中处理快速帧和可抢占帧。

图3 帧抢占机制

1.2 流

流是指具有传输方向的数据流。TSN将数据流分为同步流、循环流和“尽力而为”流。对于同步流而言，发送周期需要高精度网络时钟同步技术的支持，数据流按照规定的起始时间和偏移，在指定的网络周期内完成传输。同步流具有最小的端到端时延和最小的抖动上限，例如某些运动控制应用。循环流的发送周期无需与网络周期同步，其传输起始时间可以是网络周期内的任何时刻，其端到端延迟不超过一个网络周期，抖动以周期时间来衡量。一个网络周期内，同步流和循环流只传输一帧，最大帧长为300字节。TSN需要保证最大数据负载的同步流和循环流的时延上限。

1.3 帧延迟

为了确定网络传输时延和抖动上限，需要分析端到端时延的组成因素。

发送方发出一帧数据，从发送方开始传输数据到接收方收到全部数据的时间间隔称为端到端延迟，由传播延迟、帧相关延迟、帧无关延迟及排队延迟共同决定，其中前三者统称为路径延迟，每个流的路径延迟是恒定的，它只取决于路径长度和帧长。因此，保证端到端的传输延迟需要确定排队延迟的上限。

1.4 网络拓扑

在时间敏感网络中，主要的网络构件包括端系统、网络交换机和物理链路。

端系统作为数据流的发送方或接收方，需要同时支持同步流、循环流和“尽力而为”流的收发处理。与传统以太网不同，TSN端系统集成了时钟同步模块和流量整形模块，基于统一的全局时钟，能够满足数据流无冲突的发送和接收。

网络交换机主要功能是同时支持TSN三种数据流的转发，同时，交换机集成了时钟同步模块、流量过滤警管模块和数据容错控制机制。时钟同步模块记录数据流通过交换机入端口和出端口的高精度时间戳，以支持网络各端口队列的流量整形算法；通过流量过滤管制模块，可以解决数据流在交换机内部的带宽占用问题，保证数据流能够在流量整形器计划的时延窗口转发出去；交换机转发数据流的整个过程，采用数据容错控制机制对错误进行恢复。

TSN端系统与交换机之间以及交换机与交换机之间，通过物理链路两两互连的，构成的网络拓扑按照交换机的互联方式可以分为总线型和交换型，如图4所示。

图4 时间敏感网络拓扑结构

总线型拓扑是时间敏感网络的典型拓扑结构，在工业界已得到广泛应用。在总线型拓扑中，每个交换机都需要连接一个或多个端系统，且每个交换机都与其相邻交换机相连。尽管拓扑结构简单，但不同调度算法在总线型网络上的表现出的特征和性能仍存在差异。如果网络系统需要链路冗余，总线型拓扑的通信路径可以扩展成一个环，即，将收发两端连接成环形，以防止网络分区。

为了提高网络的传输带宽和冗余容错能力，机载网络通常采用交换型拓扑结构。在交换型拓扑中，端系统连接到交换机上，交换机采用级联的方式构成交换网络，交换机与交换机之间至少存在两条相互隔离的通信链路。

2 TSN调度算法

2.1 帧抢占

帧抢占原理如图5所示，当链路中有可抢占帧时，快速帧提出传输请求，发送方首先判断当前状态下是否允许切片操作，如果允许，则在适当位置中断可抢占帧的传输。待快速帧传输完成后，被中断的可抢占帧后半部分会被加上适当的前导码继续传输。接收方根据前导码来判断帧的类型、进行帧的重组。

图5 帧抢占原理

帧抢占通过抢占BE帧的传输来减少快速帧的排队时间，可以为单帧的端到端延迟和抖动提供最坏情况下的上限。然而，随着网络中快速帧数量的增加，快速帧不能互相抢占，帧抢占会降级为严格优先级调度。在最坏的情况下，网络中所有的快速帧都使用相同的出端口，按照严格的优先级顺序传输。帧抢占的端到端延迟和抖动上限主要依赖于发送方，假设所有的快速帧都是已知的、周期的，通过最坏情况分析，可以计算出每一跳的排队延迟上限。因此，采用帧抢占调度算法，时延、抖动的确定性强烈依赖于对网络中所有潜在的快速帧的了解。

2.2 基于流的调度

基于流的调度算法采用了TTE网络规划的思想，关注每条数据流的传输，它适用于机载网络同步流的传输。为了实现每个流在时间上和空间上的隔离，基于流的调度要求发送周期与网络周期对齐，并且需要精确配置每条数据流传输的起始时刻(即GCL)和路由，以保证最小的排队延迟。由于排队延迟很小，甚至不存在，流的路径延迟通常优于端到端延迟，从而实现了传输的高确定性。

基于流的调度只有在转发高优先级流量时，BE的传输门才关闭，因此，网络的带宽利用率很高。在机载网络中，基于流的调度规划是一个复杂HP-Hard问题，规划难度较大。为了便于应用程序及时地提供数据以及网络在预留的时隙内发送数据，网络设备需要非常高精度的时间同步。时间上的微小偏差可能导致后续所有通信错过时间窗口的级联反应，从而产生网络重新同步的额外时延。为了防止这种情况的发生，需要对所有的流进行严格警管，因此，基于流的调度要求每个流在其路径上的每个交换机上有两个门操作。当发送方发送了过多流量或是在错误的时间发送流量时，占用了其他优先级流量的带宽，交换机通过其入端口门操作和出端口门操作实施基于流的调度策略，保证了数据流的时延。

在交换机的入端口处，设置流过滤器，内建的门操作根据数据帧的特征，如虚链路(VLAN)、MAC地址、IP地址等，对转发前的每条数据流进行约束、监管，以防止在交换机出端口处的队列被非法帧淹没。交换机在对流量的警管策略上，按照控制方式可以分为以下两种：

1)对单条流的限流：限制单条流的发送，降低到过滤器的预设门限值；

2)对单条流的阻断：完全阻断错误的或流量异常的某条流。

此外，基于流的调度在交换机的出端口处还设置了基于信用的整形器(CBS)，通过门控操作确保交换机在特定的时机将被筛选出的数据转发出去。

综上，基于流的调度非常适合于机载同步流的调度，其缺点是规划复杂度高，且存在实际的可伸缩性问题(GCL长度)。

2.3 基于类的调度

与基于流的调度相比，基于类的调度是一种保证周期消息的端到端延迟和抖动的TAS方法。如图6所示，假设发送方按照如下规则发送周期消息：

图6 基于类的调度

1)发送周期与网络周期相同；

2)发送周期和网络周期不严格对齐；

3)发送时刻可以偏离发送周期的±50%，即一个完整的周期。

在基于类的调度中，所有具有相同时延和抖动要求的数据流被分配到同一个专用的通信类中。由于TAS只区分出口队列，这个通信类需要映射到一个专用的出口队列上。每个网络周期开放一次传输门，门打开的时间间隔称为类窗口，其长度可以任意配置，但它需要与网络中的交换机匹配。由于传输门只打开一次，类窗口必须足够大，以保证所有流都在一个周期内发送出去。为此，提出下列公式来计算类窗口的大小。

如前所述，所有循环流，端到端延迟不能大于一个网络周期时间：

(1)

也可以表示为：

(2)

基于这个约束条件，给出一个基于公式(2)的类窗口大小tw的推导。

该推导适用于基于有向图G(ν,ε)建模的任意网络。顶点v代表交换机和主机，交换机的全双工链路用一个出站边和一个入站边表示，交换机在出端口配置了队列和传输门，参数符号见表1所示。

表1 参考符号

(3)

(4)

tcycle和tw与循环流s无关，故：

(5)

(6)

根据最长路径和最大帧长，可以确定路径延迟：

(7)

(8)

将式(7)和式(8)代入式(6)，可得:

(9)

综上，tw的值足够大，当考虑路径长度和流s其他帧的潜在干扰时，能够保证每个流都可以到达目的节点。式(9)提供了一个tw的上限，如果要tw变得更小，有以下3个方法：

2)限制发送模型所允许的传输抖动；

3)使用相应的流量整形和警管策略来执行更可预测的行为。

基于类的调度保证了一个周期内的端到端延迟和抖动，通过tw的数学模型，证明了基于类的调度需要很少的GCL条目，发送方只需要粗时间同步，由于粗同步精度需要更少的同步时间，基于类的调度允许在运行时动态地启用和禁用发送端口。然而，机载安全关键业务不允许发生数据丢弃，因此，基于类的调度需要在交换机上有大量高优先级的缓冲区。由于计算tw时考虑了最坏情况，类窗口很大，而tw的空闲时间不能被BE使用，导致带宽效率很低。

综上，基于类的调度提供了端到端延迟和抖动保证、同步开销和网络配置之间的权衡，但代价是更宽松的边界和更大的缓冲区。

3 仿真分析

为了测试帧抢占和TAS算法在机载网络业务流量下的最佳和最坏边界，使用离散仿真工具NeSTiNg开展调度算法的性能评估，该工具扩展了OMNeT++/INET协议栈的TSN功能，包括帧抢占、TAS和基于信用的整形[16]。

3.1 仿真模型

OMNeT++可以用于模拟通信网的业务流，通信协议的模型，排队网络以及多处理器和分布式系统[17], NeSTiNg作为融合IEEE TSN网络的模拟器，可以塑造各种流量整形器的模型，还可以模拟交换机入端口、出端口的虚链路(VLAN)标记和多个分支、循环的控制功能。

如1.4节所述，为了更加真实地反映调度算法在机载背景流量下的性能，采用交换型拓扑开展仿真验证。端系统和交换机的仿真模型设计具体如下：

1) 端系统模型：主要由时钟同步模块、带宽预留模块、发送模块和接收模块构成。

(1)时钟同步模块：负责为网络模型提供统一的全局时钟，OMNeT++提供了sim_Time( )函数，可以获取当前仿真系统时间值，其精度符合 高精度时间同步协议(PTP，precise time protocol)的要求[18]，主节点的时钟同步模块通过调用该API将全局时钟同步至从节点的时钟模块。当端系统模型发送或接收数据流时，其内部的数据帧处理函数调用INET框架提供的IEEE802时钟模块接口函数获取当前时间戳，并将其嵌入至发送数据帧或接收数据帧中。时钟同步模块提供时钟同步周期处理功能，即当时钟同步周期开始时，时钟同步模块向全网广播时钟同步数据帧；当主节点接收到从节点的延迟响应请求时，检查时间戳信息和数据帧类型，调用OMNeT++的getHardwareDelay( )函数，模拟硬件延时，随后将时间戳嵌入应答数据帧中发送至从节点。此外，从节点的时间同步模块通过调用updateClock( )函数，修正本地的时钟偏差。

(2)带宽预留模块：负责为发送方和接收方预留充足的通信带宽，主要包括通信节点注册函数、网络配置更新函数、通信节点故障管理函数等。对网络中发送方模型和接收方模型内的每一条数据流创建唯一标识符StreamID, 通过定义数据流的发送方标识、接收方标识、数据帧负载长度、数据帧间隔、保护窗口长度等参数，配置仿真环境的背景流量。例如，带宽预留模块通过调用OMNeT++内建的getCurrentPeriod( )、getCurrentTicks( )获取当前时刻并判断该时刻是否在保护窗口内，通过调用INET框架的各类EVENT状态和EtherFrame类型，创建或注销特定的数据流。

(3)发送模块：负责数据帧的发送控制，在模块出口队列处构建调度模块，将不同数据流输出到交换机的入端口上。根据IEEE802.1协议规定，在NeSTiNg调度模块中，每条数据流通过VLAN标识映射到深度为8的发送队列上，基于类的调度算法通过VLAN标识中的一个3位的优先级码点(PCP，priority code point)为每一类数据流配置不同的GCL长度。此外，发送模块还具备发送处理接口函数，负责传输门发送数据帧的逻辑判断。

(4)接收模块：负责从交换机的各个出端口接收数据流，通过调用各个数据流的数处理模块完成。

2) 交换机模型：主要由交换转发模块和端口调度模块构成。

(1)交换转发模块：负责数据流在交换机内部的数据处理，主要由INET框架的链路组件实现。通过构建MAC模块模拟传输和转发延迟，构建转发模块跟踪数据帧从交换机入端口队列到出端口队列的流动，通过中继单元的延迟模块，模拟交换机的处理延迟，最后根据VLAN标识将数据帧移交至不同的出端口队列。

(2)端口调度模块：负责交换机入端口及出端口的调度算法实现。交换机除了具备端系统发送模块和接收模块的功能外，还需构建基于流的检索模块，通过PCP值，传输门选择适合传输的下一条数据流。控制路径分为从入端口向下到出端口，以及从出端口向上转发。在向下控制路径空闲之后，传输门才能触发对新到达的数据流的处理；在向上控制路径空闲之后，传输门根据GCL依次轮询，排队等待下一条符合条件的数据流。

3.2 仿真过程

使用网络规模nl∈(10,20,30,50)为的网络拓扑,链路带宽均为1 Gbps。遍历nl值，随机为网络分配nl个同步流、周期流和“尽力而为”流传输业务，以模拟不同的机载业务。具体如下：

1)同步流参考了文献[19]中TT业务帧的数据负载、发送周期、门控开关的保护窗口等参数，即配置同步流的发送周期分别为2 000 μs、8 000 μs、16 000 μs、32 000 μs，配置同步流的帧间隔分别为2 000 μs、4 000 μs、8 000 μs、16 000 μs，消息负载可变且无分组转发，优先级最高，不同任务流量的优先级可变，具有一定随机性；

2)周期流参考了文献[20]中机电系统采集、状态判断、控制、告警发送、数据处理、异常处理、故障记录等任务的特征，即配置周期流的任务周期分别为100 ms、200 ms、400 ms，消息优先级中等，且不同任务流量的优先级不同，任务周期越小，优先级越高；

3)“尽力而为”流参考了文献[21]中机载视频影像的业务特点，配置“尽力而为”流的数据负载为需要分组发送的长消息，消息优先级最低，不同任务流量的优先级相同。

随后，随机选择一个发送方及一个接收方，在基于流的调度仿真中，每个节点只模拟单个流的源节点以及多个流的目的节点，流的负载在间隔[64 B,300 B]中随机抽取。帧抢占仿真时，发送方以线路速率向接收方发送可抢占的BE帧。

3.3 仿真结果分析

图7列出了3种调度算法的累计排队延迟，即单个帧在从发送方到接收方的路径上等待队列所花费的总时间。

在图7(a)中，可以看到，在机载网络业务流量下，帧抢占产生的累计排队延迟的平均值是微秒级的。然而，帧抢占最坏情况下的延迟超过300 μs，这个数量级比平均累积排队延迟大很多，也就是说，即使只有一个业务类别使用快速帧，由于排队延迟的变化，端到端延迟也会有差异。此外，由于流量分配的随机性，nl值的增大并不一定会使排队延迟变小。统计结果表明，对于关键等级高的实时业务，采用帧抢占并不能保证确定性，需要提前对整个机载网络业务进行充分的规划和编排。

在图7(b)中，可以看到，在机载网络业务流量下，基于流的调度可以可靠地实现接近零排队，最大累计排队时延为5.1 μs。然而，高确定性带来的问题是，需要使用强大的网络配置工具，对每条机载业务数据流进行规划，解决NP-Hard问题。

基于类的调度的仿真结果如图7(c)所示。nl的值越大，累计排队延迟就越小。主要有以下两个原因：

图7 仿真结果分析

首先，由于tcycle是恒定的5 ms，随着机载网络规模和业务数量的增加，nl越大，类窗口tw就越大，即当传输门关闭时，数据到达接收方所造成的排队延迟就越小；

4 结束语

文章研究了TSN的3种调度算法，即帧抢占、基于流的调度和基于类的调度，分析了这些算法的工作原理，建立了数学模型，开展了机载应用场景的仿真。结果表明，帧抢占不需要网络同步，但其确定性强依赖于对机载网络潜在有冲突的快速帧的规避；基于流的调度适用于机载强实时业务，但规划较为复杂，且存在GCL长度伸缩的问题；基于类的调度适用于周期业务，它很容易进行配置规划，但由于类窗口较大，带宽效率较低。总之，每种方法都可以服务于特定的、对网络存在不同要求的机载应用，单一的调度算法不能服务于所有的机载业务，因此需要将这些算法组合起来。综上所述，后续需评估网络调度算法之间的相互作用，为进一步的研究提供充分的机会。