来源：TSNLAB 微信公众号

 

“ IEEE 802.1Qbv定义了一种时间感知整形器（Time Aware Shaper，TAS），配合控制器的编排，交换机按照配置好的时间控制队列的打开/关闭状态（基于门控列表Gate Control List，GCL），可以实现业务端到端纳秒级别（或时钟同步精度级别）的SLA保障和控制。然而，标准中并未定义GCL应该如何计算，本文针对该问题进行阐述。”

IEEE 802.1Qbv定义的TAS示意如下图1所示，GCL表项中每行数据分别对应了每个队列在对应时刻的O/C状态，交换机按照时间顺序进行轮转。门控机制作为TSN核心技术之一，本质上是通过规定周期性业务每一帧在每个交换机端口上的转发时间，达到时延控制、抖动控制以及其它SLA保障的目的。

图1：门控机制及GCL示意图

然而，标准中并未定义GCL应该如何计算，为了实现各种各样的目标，学术界和产业界对Qbv门控编排（或称之为门控编排、TAS编排）问题进行了深入探讨。本文通过一个简单的例子，阐述门控编排的数学模型、解决方法以及面临的问题。

01

—

以一个例子引入…

如下图所示，有A、B、C三辆车分别从三地出发前往机场，假设各车车速相同，车辆通过道路的时间如图中标识，同时，假定每个路口一次只能通过一辆车，通过时间为2s。那么，如果A、B、C三车分别要求在85秒内、90秒内、86秒内到达机场，问如何安排路口的红绿灯使车辆按照特定顺序通过路口，且保证三辆车都满足其时限要求？

图2：车辆调度问题

该问题求解并不难，一种可行的方式如下图3，即当时间到达20s，A、B辆车同时到达路口甲，由于A车更“着急”，所以A车先通过（此时时刻为22s），B车需要等待2秒；52s时刻，A、C车都到达路口乙，同样原因，A车先通过路口（通过时刻54s）。之后，如果让B车先过，通过时刻为56s，那C车到达机场时间为88s，超过时限限制，因此，需要先让C车通过。58s时刻，三车顺次通过路口乙。最终到达机场的时间：

•A车：20+2+30+2+30=84s

•B车：20+2+2+30+2+2+30=88s，黑体表示等待其它车辆通过的时间

•C车：51+3+2+30=86s，由于C车51s时到达路口，等待A车54s时通过路口，故等待3s时间

图3：车辆调度问题可行解之一

Qbv门控编排问题与上述车辆调度问题极为相似，一个业务流可以认为是例中的车辆，路口可以认为是交换机端口，车辆的时限要求可以认为是业务的时延诉求。然而，实际的Qbv门控编排问题要更加复杂，例如，实际的业务流可能会有多个帧组成，因此，例中车辆的编排可能演变成车队的编排；实际的业务通过端口的时间与报文大小和端口速率有关，非固定值；端口有多个队列组成，报文到达队列的顺序、等待时间可以灵活调整（类似于车道级红绿灯）；如果端设备受控，报文的起始发送偏移（offset）亦可调整（发车时间不固定）；报文还可能存在抖动需求……

下面，进一步阐述门控编排的数学模型。

02

—

门控编排的目标

在讨论目标前，首先明确编排的问题输入，包括业务和网络拓扑信息输入。

•业务信息：门控编排通常适用于具有端到端时延或抖动需求的周期性或时间触发（Time-Triggered Traffic, TT）业务，这里采用简单的业务模型：，分别表示每周期数据量、周期大小、业务时延要求

•网络拓扑信息：假设，分别表示交换机集合、端设备集合以及链路集合。

门控编排的目标包含（但不限于）以下几种：

1、在有限的网络资源（带宽、时隙、队列等）下，尽可能承载更多的业务，且业务的SLA指标可满足

2、部署给定业务，占用资源最少

3、部署给定业务，业务时延最低，抖动要求可满足

4、承载更多的业务类型，如除TT业务外，承载突发性流量、AVB流量等

TIPS：之前车辆的编排问题目标对应于上述第1种

明确了问题的输入输出，下面介绍问题求解过程中需要遵守的约束条件（篇幅有限，仅介绍关键约束）

03

—

编排问题约束条件类型

时延要求满足性约束

其中，表示流在最后一跳的离开时间，表示对应端口的带宽，表示业务在源端的发送偏移。因此，该式表示终端设备收到报文的时刻减去报文发送时刻，亦即路径端到端时延应当在规定的范围内。当前不等式中未考虑链路上的信号传播时延。

转发时间不重叠约束

对于经过同一出端口的任意两条流，其从端口转发的时间窗相互不重叠，即，任意一条流从离开端口的时刻开始，到整个数据帧发送完毕为止，期间不受其它报文影响（这里不考虑帧抢占）。

存储转发约束

在存储转发机制的交换机中，当交换机完整的收到上一跳发送的报文后，才进行转发。这里的表示网络的时钟同步误差。从公式中可以看到，由于时钟误差的存在，相当于在报文的尾部加入了一个保护边带，如下图所示。

图4：时钟同步误差示意

周期混叠约束

当多个流的周期不相同时，需要基于超周期（hyper-period）进行编排，超周期的最小值取所有业务的最小公倍数。因此，一个周期较小的流在超周期上会进行延展，进而需要保证超周期下该流的多个子周期的报文转发约束都得到满足。

上述公式给出了超周期下小周期业务流延展之后的转发时间不重叠约束的简单表达。其中 表示流在超周期下的第个周期。其它约束条件类似。

其它约束

除上述约束条件外，还有抖动要求约束、路径约束、队列隔离约束、队列FIFO属性约束等，详细信息读者可以查看相关论文，本文不做展开。

04

—

常见的求解方法

门控编排问题可以抽象成任务调度问题，是典型的NP-Hard问题，除非NP=P，否则无法在多项式时间内求得最优解。目前学术界对于门控编排问题的求解，或是基于可满足性模理论（Satisfiability Modulo Theory，SMT），如同TTTech公司的论文[2, 3]，类似的还有优化模理论（Optimization Modulo Theory，OMT）；或是基于整数线性规划（Integer Linear Programming，ILP）[4]；或者基于启发式算法，如Tabu-Search、遗传算法、蚁群算法等[5]。当然，还可以通过AI等方法进行加速计算[6]。

图5：几种方法对比

05

—

结合实际场景的优化和简化

TAS编排问题的复杂度

当网络规模变大、业务数目变多，如果要精确调整每条业务流的每一帧在每个节点的接收、发送时刻，来求全局最优解，那么变量和约束数目将按照|F|*M*|L|（流数*帧数*链路数）的基数呈指数级增加。同时，还需要考虑不同周期的业务混叠、路径等因素，导致问题变得十分复杂。例如，当采用MILP求解时，对于一个百节点的多环拓扑+百条流的场景，其求解文件将达2GB，变量和约束数目将达百万级别。这样的问题规模，在合理的时间范围内求最优解是不现实的，然而，在实际场景中，是否有必要做如此精确的求解？

真实场景中的问题简化思路

•逐帧编排→逐流编排：在工业现场、车载网络等场景，很多传感器、采集器等端设备并不会一次性发送很多报文，相反，业务流大多以小包（如100B、64B）、单包的形式，或者即使业务每周期会发送多个报文，对于门控编排问题来说，也可以将多个报文以背靠背方式连在一起作为一个单独的帧进行编排。这样，编排问题的视角从逐帧降级到逐流，业务复杂度的计算基数将从|F|*M*|L|下降到|F|*|L|，当然这样做的代价是牺牲了一定的解的灵活性。但是对于大规模网络场景来说，这种复杂度下降带来的收益要远大于灵活度下降付出的代价，是一种可取的问题简化手段。

•流聚合：实际场景中，往往存在大量业务特征相似甚至相同的业务流（例如大量相同的传感器），对这些业务按照其周期、路径、SLA要求等特征做分类和聚合，同样可以从根本上降低问题的复杂度。

•分域求解：大型网络场景中，例如云化PLC、多厂区IT/OT融合，往往地理上具有分隔的特征。在这种假设下，将全域编排分解成几个子域分别求解，最后再进行合并优化，可以发挥并行计算的优势，降低求解时间。

总之，结合实际场景进行问题简化，不仅可以在求解时间上获得收益，也可以根据场景特征做定制化调整，而其中牺牲的一部分灵活性或浪费的些许带宽资源，是可以容忍的。毕竟，用户真正关心的是可用、好用，其次才是精益求精。

06

—

结语

本文介绍的编排问题模型，仅仅是TSN编排的冰山一角。广义的编排不仅包括TAS编排，还包括针对异步流量的CBS、QoS编排。流量类型除了周期性的TT业务外，还包括突发类流量（如AI质检）、事件触发类流量（控制报文、事件告警业务）等。同时，真实场景中，很可能TSN交换机、异步交换机共存，或存在多个TSN域，那么编排问题不仅要考虑混合业务、还要考虑异构网络，使问题模型变得更加复杂。

当前，TSN的发展如火如荼，然而，若想真正实现规模应用，必然要解决TSN混合+异构编排问题，这依赖于学术界、产业界，无数学者、工程师的共同努力。无论如何，在技术日益革新、国家大力发展工业互联网的时代浪潮下，TSN的未来必将一片光明！

作者简介：

高涛博士，华为公司数据通信产品线 研究工程师， 负责网络演算理论、TSN编排算法、流量建模技术研究。2019年毕业于北京邮电大学获博士学位。

作者联系方式：im.taogao@outlook.com/gaotao11@huawei.com

参考文献：

[1] IEEE 802.1Qbv-2015

[2] Craciunas, Silviu S., et al. "Scheduling real-time communication in IEEE 802.1 Qbv time-sensitive networks." Proceedings of the 24th International Conference on Real-Time Networks and Systems. 2016.

[3] Steiner, Wilfried, Silviu S. Craciunas, and Ramon Serna Oliver. "Traffic planning for time-sensitive communication." IEEE Communications Standards Magazine 2.2 (2018): 42-47.

[4] Schweissguth, Eike, et al. "ILP-based joint routing and scheduling for time-triggered networks." Proceedings of the 25th International Conference on Real-Time Networks and Systems. 2017.

[5] Raagaard, Michael Lander, and Paul Pop. "Optimization algorithms for the scheduling of IEEE 802.1 Time-Sensitive Networking (TSN)." Tech. Univ. Denmark, Lyngby, Denmark, Tech. Rep (2017).

[6] Mai, Tieu Long, Nicolas Navet, and Jörn Migge. "A hybrid machine learning and schedulability analysis method for the verification of TSN networks." 2019 15th IEEE International Workshop on Factory Communication Systems (WFCS). IEEE, 2019.