TSN中流的路由与调度的研究

参考文献

[1] 张彤,冯佳琦,马延滢,渠思源,任丰原.时间敏感网络流量调度综述[J].计算机研究与发展,2022,59(04):747-764.

[2] Li Q, Li D, Jin X, Wang Q, Zeng P. A Simple and Efficient Time-Sensitive Networking Traffic Scheduling Method for Industrial Scenarios. Electronics. 2020; 9(12):2131. https://doi.org/10.3390/electronics9122131

[3] Eike Schweissguth, Peter Danielis, Dirk Timmermann, Helge Parzyjegla, and Gero Mühl. 2017. ILP-based joint routing and scheduling for time-triggered networks. In Proceedings of the 25th International Conference on Real-Time Networks and Systems (RTNS '17). Association for Computing Machinery, New York, NY, USA, 8–17. https://doi.org/10.1145/3139258.3139289

[4] M. Pahlevan and R. Obermaisser, “Genetic Algorithm for Scheduling Time-Triggered Traffic in Time-Sensitive Networks,” 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA), 2018, pp. 337-344, doi: 10.1109/ETFA.2018.8502515.

[5] Maryam Pahlevan, Nadra Tabassam, and Roman Obermaisser. 2019. Heuristic list scheduler for time triggered traffic in time sensitive networks. SIGBED Rev. 16, 1 (February 2019), 15–20. https://doi.org/10.1145/3314206.3314208

[6] V. Gavriluţ, L. Zhao, M. L. Raagaard and P. Pop, “AVB-Aware Routing and Scheduling of Time-Triggered Traffic for TSN,” in IEEE Access, vol. 6, pp. 75229-75243, 2018, doi: 10.1109/ACCESS.2018.2883644.

正文

通常来说，论文开始的时候会有一个introduction和related work，这两部分每篇文献都会有介绍，所以这里就不展开讲了。

一、TSN流量调度形式化

要研究一个东西，首先要将它形式化，所以这里讲一下如何形式化TSN中的流量调度，它包含四个部分，也就是网络模型、流量模型、调度约束以及调度目标。
其中，TSN有两类形式化方法，分别以帧或者是时间窗口作为调度对象，但是我们可以通过队列中所有帧的传输开始时刻和帧大小推导出该队列传输帧的所有时段，也就是时间窗口；但已知时间窗口的开闭时刻却并不能确定窗口内每一帧的传输时间。因此第一类形式化问题更加精确，所以我们一般使用第一类形式化方法。
形式化问题在每篇文献里面都会提到，所以我在这里就简单表述一下。

1、网络模型

先看一下网络模型，我们通常将网络抽象为有向图G，其中包含了点集和边集。

TSN建立在全双工以太网之上，所以节点Va 与Vb 间的物理链路对应两条单向链路[Va，Vb]和[Vb，Va]。每条单向链路[Va，Vb]由三元组定义，分别表示该链路的带宽容量、传播延时以及相连的出端口队列数，在TSN标准中，端系统出口链路队列数为1，而交换机出口链路队列数为8。

2、流量模型

接下来看一下流量模型，TSN中的流量包括TT流、AVB流和BE流，传输优先级依次降低。其中TT流为周期性数据传输，周期长度和数据大小由应用预先定义为已知量；而AVB 流和BE流为非周期性随机数据传输，到达间隔与数据大小均为未知量。由于TSN的流量调度为离线操作，无法处理未知的AVB和BE流量，因此只对TT流进行形式化定义。
对于TT流fi，它可以由下列四元组定义，这个四元组里面的元素对于流之后的调度都很重要，包括决定传输优先级、判断是否调度成功等；

另外，流的传输路径如下所示，那么它的路径可以形式化为Ri。

当流在一个周期内开始调度时，超过MTU的流会被分为多个帧，当第j个帧开始调度时，那么我们用下列三元组表示它，后两个元素是我们已知的，我们会根据调度机制确定该帧的起始传输时刻。

Tips

另外，在流的调度时有一个比较常用的时期，也就是超周期，调度机制只需确定1个超周期的 GCL，就可以在之后的多个超周期内循环执行。而我在这篇文献《A Simple and Efficient Time-Sensitive Networking Traffic Scheduling Method for Industrial Scenarios》里看到一个新的概念——基本周期，它是所有流周期的最大公约数，它分为多个时隙，每个基期的时隙数量和大小相同。具有相同周期的流量可以对不同的基期使用相同的时隙，而不同时段的流量和具有BP时段的流量不能共享时隙的，因为不同时段的流使用相同的时隙会导致后续某个基期的时隙冲突。像下图表示的那样，流1和流3的周期均为2·BP，流2的周期为3·BP，m和n代表基期内的不同时隙。流1和流3可以在不同的基期内交替使用相同的时隙，例如，流1安排在BP1的时隙n中，流 3可以安排在BP 2的时隙n中。因为本例中没有流与流2的周期相同，flow2安排在时隙m中，那么时隙m不能用于任何基期内的流1和流3，如果其他流的周期与流2的周期相同，则可以使用这个时隙m。每个基期的时隙的打开/关闭都是相同的，因此GCL只需要按照图中的灰色部分进行配置。

这篇文献用了SMT的调度方法，使用这种基于基期的调度算法，显示可以大大减小GCL的大小，像下面这两张图表示的那样，可以很明显地看到基期和超周期使用的GCL的对比。

另外，与以前使用超周期的调度相比，该算法能够更快地计算调度结果。下面的第一张图是小型网络中两种方法的对比，第二张和第三张图显示的是中型网络中的对比。比较遗憾的是这篇文献中我们所关心的两种方法的可调度率以及延迟没有对比。

3、调度约束

接下来就是调度约束了，一般都会有以下几项约束：帧约束、链路约束、流传输约束、延时约束、抖动约束和帧隔离约束。

4、调度目标

最后是调度目标，通常来说，我们会从以下调度目标中选择一个或者两个来作为优化目标，分别是：最小化端到端延迟、最小化实时流量占用队列数、最小化总传输时长、最小化帧缓存时间等等，当考虑多个优化目标时，一般采用加权、字典序优先级等方法。

二、TSN流量调度机制

接下来是比较重要的调度机制，通常论文的创新点和重点都会集中在这部分。调度机制大致有以下五种方法，ILP、启发式、SMT/OMT、TS、GRASP。

通常论文有使用其中一种方法为调度算法的，也有组合使用其中两种方法的，当然，组合使用一般是联合路由与调度的情况。

由于将路由与调度建模为独立问题时会忽略路由和调度问题的相互依赖性，限制了TT通信全局调度的能力，所以我认为应当联合路由与调度进行求解。

1、ILP

在这篇文章《ILP-based joint routing and scheduling for time-triggered networks》中，将基于ILP的调度扩展到联合路由和调度（JRaS）公式，并基于两个性能指标（可调度性和通信延迟）分析了JRaS公式以及固定路由和基于ILP的调度。通过第一和第二张图我们可以看到，在可变负载和不同拓扑下，JRaS的可调度性是优于其他两种方式的，第三张图展示了即使在具有控制流量的扩展环拓扑中，jras的可调度性依然是最大的。

但它的缺点也是很明显的，jras在高负载的情况下提供了一些路由效率很低的解决方案，这可能会导致稍高的延迟。如果使用更高的时间限制，jras可以得到更好的延迟结果。

2、遗传算法

以上我们可以看到，用基于ILP的方法来解决大型调度问题，这种方法速度较慢。此外，使用ILP解决方案不考虑多播TT消息、交互流依赖和分布式实时应用程序。而这篇文章《Genetic Algorithm for Scheduling Time-Triggered Traffic in Time-Sensitive Networks》提出了一种基于遗传算法的启发式调度方法，主要目标是在满足最后期限的同时，优化TT传输的总时间和TT通信的开销。
遗传算法的目标是找到具有最小makespan的全局时间表。此优化过程具有以下优点：
1）由于优化了TTflow的传输时间，调度能力将得到提高。
2） 优化的制造周期使TTflow的传输计划更加紧凑。因此，在每个TT时隙之前为避免与非TT通信量的干扰而保留的保护频带的数量显著减少。
3） 这还可以提高带宽利用率，缩短因专用TT时隙而阻塞的非TT消息的等待时间。
另外使用列表调度器用于对比，列表调度器首先查找所有终端系统之间的最短路径，然后使用这些固定路径来解决调度问题。从下面第一张图中，我们可以看到，在不同TT负荷和网格拓扑下，GA相比于列表调度器的可调度性更高。第二张图显示在环状拓扑下，GA的可调度性依然高于LS。

为什么GA和LS的差异如此明显，究其原因，很简单，LS总是使用最短路径，而GA则查找导致更优化制造周期的路由；LS中使用的固定路由在某些物理链路上造成高流量负载，而其他链路的利用率较低。相比之下，GA在使用联合调度和路由约束计算路由时受益于负载平衡。
但GA的缺点也是显而易见的，它为了找到更优的解就要花费更多的时间，解决问题的速度也就要慢于LS。

3、启发式算法

既然LS是依靠查找最短路径导致调度率不高，那么检查所有可能路径的启发式列表调度器的效果又如何呢？这篇文章《Heuristic list scheduler for time triggered traffic in time sensitive networks》介绍了联合路由与调度的启发式列表调度算法，总体而言，与LS相比，HLS将使得makespan缩短，而减少的makespan也可能导致保护带数量降低，TT传输计划更加紧凑。

结果还表明，在高流量负载的情况下，HLS比LS提高了总体可调度性比率。

当然，和上一篇文章相同的是，HLS的执行时间也比LS的长。

4、启发式（K-最短路径）与GRASP复合方法

上面提到的方法中完全确定性TT传输的路由或GCL合成方法都是孤立地看待TT流量，完全忽略了对AVB流量的影响。而忽略AVB流量会导致路由和GCL以AVB流量为代价为TT进行优化，从而导致AVB的WCD非常大。
这篇文章《AVB-Aware Routing and Scheduling of Time-Triggered Traffic for TSN》提出了TSN中考虑AVB流量的TT流量联合路由和调度，保证了TT流量的可调度性，同时减少了AVB流量的WCD，从而满足其端到端延迟要求。
最后看一下启发式（K-最短路径）与GRASP复合方法。这篇文章主要算法是下图中的JRS:

在此算法中，路由启发式算法中使用KSP来减少搜索空间，迭代为每个TT流选择路由，来均匀分配链路利用率；然后利用基于GRASP的元启发式算法根据这个目标函数来寻找最佳调度解决方案，该目标函数计算的是AVB流的延误总和。

在达到给定时间限制或迭代次数后目标函数没有改进时，这个算法就终止。
论文里设计了三组实验，分别是不考虑AVB的情况下根据队列利用率和端到端延迟评估TT调度启发式质量，以及根据TT流的可调度性评估GCL合成期间考虑TT路由的重要性，最后一组实验是考虑AVB的情况下，根据JRS确定可调度解决方案的能力（包括延迟、可调度性、执行时间等因素）来评估JRS。

对于第一组实验，从图中我们可以看出，相对于ILP，GRASP的执行时间很快，但是队列利用率和端到端延迟不如ILP。

对于第二组实验，TC1和TC2是具有替代路由的拓扑，从图中我们可以看出，随着拓扑的大小和利用率的增加，最短路径路由很难为TTflow找到可调度的解决方案。启发式路由能够显著改善最短路径路由，因为拓扑越来越大，利用率越来越高。正如从结果中看到的，对于具有替代路由的拓扑，如果想获得可以调度TT流的解决方案，优化路由是非常重要的，并且启发式路由能够在短时间限制内找到这样的结果。

对于第三组实验，TT延迟这列最小化了TT流的延迟，TT队列这列最小化了TT队列的数量，从表中可以看出，如果在调度过程中忽略AVB，就像“TT延迟”和“TT队列”方法一样，我们无法找到AVB流的可调度解决方案。然而，如果我们在调度期间考虑AVB流（表6中的“TT+AVB”标题），我们能够找到TT和AVB流都可调度的解决方案。
但这仅适用于较小的测试用例，对于较大的测试用例和现实测试用例，为了获得可调度的解决方案，我们还必须优化TTflow的路由，也就是使用JRS。
总的来说，只有使用在路由和调度优化过程中考虑AVB的JRS方法，才能获得所有AVB流都可调度的可调度解决方案。

三、思考与启发

以上文献有两篇最后都以列表调度器为对照组做了对比实验，结果都是优化TT传输的总时间和TT通信的开销，之后可以尝试实现启发式列表调度算法和遗传算法，对比一下可调度性和执行时间；最后一篇文献讲了在TT路由与调度时考虑AVB对于AVB可调度性的重要性，我觉得这个也可以尝试实现一下，对比一下可调度性，毕竟TSN作为新一代的网络技术，需要保证多种业务流量的公网高质量传输，所以可以在保证TSN的可调度性时，也减少AVB流的WCD，使其满足端到端需求；除此之外，在多篇文献的实验中，常用的拓扑一般是不同流量负载下的网格拓扑、环拓扑，是因为网格拓扑具有更多的路由可能性和更高的连通性，而环拓扑解决了工业系统的典型结构，之后我做实验的时候也会参考这两种拓扑；最后一点考虑的是硕士开题报告了，我认为之后所写的论文针对的应用场景很重要，毕竟创新点和算法也是根据这个应用场景展开的，我看了《5G+TSN融合部署场景与技术发展白皮书》中写了，比如像远程控制业务，这种在工业互联网的应用系统中,典型的闭环控制过程周期可能低至毫秒级别，同时对业务的传输有十分严格的可靠性和确定性要求，针对这种环境的算法优化目标一定是降低TSN流的延迟与抖动，提高其可调度性；但是像采集及运维类业务，比如一些工业企业存在大量设备维护、原材料及产品数据需要通过传感器、RFID、智能终端等方式上传云端。上述业务涉及的音视频、控制信号、物联网数据的传输则采用不同的传输机制和质量要求，针对这种环境的算法优化目标可以是在保证TSN流的可调度性下，减少AVB流的WCD。
先明确了针对的应用环境，之后便可以选择针对性的优化算法。