基于时间敏感网络的门控调度算法研究_李佳庆.pdf

引用格式:李佳庆，陈水忠，魏刚，等 基于时间敏感网络的门控调度算法研究J 电光与控制，2023，30(3):58-62 LI J Q,CHEN S Z,WEI G,etal Research on gating scheduling algorithm based on time sensitive network J Electronics Optics Control,2023,30(3):58-62基于时间敏感网络的门控调度算法研究李佳庆1，2，陈水忠2，魏刚2，李昕2(1 光电控制技术重点实验室，河南 洛阳471000;2 中国航空工业集团公司洛阳电光设备研究所，河南 洛阳471000)摘要:时间敏感网络在标准以太网的基础上通过增加高精度时间同步、资源预留及路径控制、流量整形和业务调度等一系列关键技术，能够保证数据传输的实时性和可靠性。然而，启发式算法在实现门控调度时，数据的周期比过大会导致缓存容量增大和相同优先级数据同时、同向传输时无控制调度等问题。为此，优化改进了门控调度的启发式算法，通过采取数据周期感知和输出缓存长度感知循环等技术，解决了缓存容量不足和时延抖动等问题。仿真结果表明，与传统的启发式算法相比，所提算法在数据周期比超过 60 倍时能有效减少门控列表 90%的存储空间，在相同优先级数据传输情况下平均时延抖动降低了约 50%。关键词:时间敏感网络;网络传输;门控调度;门控列表;启发式算法;时延抖动中图分类号:TP393 11文献标志码:Adoi:10 3969/j issn 1671 637X 2023 03 011Research on Gating Scheduling AlgorithmBased on Time Sensitive NetworkLI Jiaqing1,2,CHEN Shuizhong2,WEI Gang2,LI Xin2(1 Science and Technology on Electro-Optical Control Laboratory,Luoyang 471000,China;2 Luoyang Institute of Electro-Optical Equipment,AVIC,Luoyang 471000,China)Abstract:On the basis of standard Ethernet,Time Sensitive Network(TSN)can ensure the real-time andreliability of data transmission by adding a series of key technologies such as high-precision timesynchronization,resource reservation and path control,and traffic shaping and service scheduling However,when heuristic algorithm realizes gating scheduling,the excessive cycle ratio of data leads to the problems ofincreased cache capacity and uncontrolled scheduling when data with the same priority are transmitted in thesame direction at the same time Therefore,the heuristic algorithm of gating scheduling is optimized andimproved,and the problems of insufficient cache capacity and delay jitter are solved by adopting technologiessuch as data cycle sensing and output cache length sensing cycle The simulation results show that,comparedwith the traditional heuristic algorithm,the algorithm can effectively reduce the storage space of the gatecontrol list by 90%when the data cycle ratio exceeds 60 times,and the average delay jitter is reduced byabout 50%under the same priority data transmissionKey words:time sensitive network;network transmission;gating scheduling;gate control list;heuristicalgorithm;delay jitter0引言随着新一代宽带移动通信技术的飞速发展，网络环境越来越复杂，对其承载网的传输性能提出了严苛的要求，传统以太网已经无法满足网络传输需求。时间敏感网络(Time Sensitive Network，TSN)的提出为解决传统以太网无法满足低时延、高可靠性、高稳收稿日期:2022-05-04修回日期:2022-05-31作者简介:李佳庆(1997)，男，河南洛阳人，硕士生。定性等需求的问题提供了思路。TSN 技术的核心是当某事件发生后，网络系统在一个可以准确预留的时间范围内做出正确反应。目前，TSN 的研究主要包括标准协议的制定，TSN网络时延、稳定性、流量控制等性能的分析，门控调度算法研究和高精度的时钟同步影响等。文献 1 研究了 TSN 周期和非周期数据的传输调度，提出了周期分组、组间插非周期的方法;文献 2 3研究了 TSN 最优化调度方法，分别从保护带优化和时间感知整形优化的角度，将保护带和调度时间大幅优化;文献 4 研Vol 30No 3Mar 2023第 30 卷第 3 期2023 年 3 月电光与控制Electronics Optics Control李佳庆等:基于时间敏感网络的门控调度算法研究究了多跳 TSN 交换网络完全确定性调度问题;文献 5 研究了实时应用时间敏感的软定义网络，提出整数线性规划解决路由和调度的组合问题，降低确定的端到端延迟和时延抖动。本文主要对 TSN 协议 IEEE802 1Qbv 门控调度中的启发式算法进行优化改进，改进后的算法能更加合理地将门控传输时隙分配给不同的周期数据流量，同时，提高了相同优先级数据的传输时延精度、降低了数据流量在网络中端到端的平均时延和时延抖动，减少了交换机内部门控列表所需的存储空间。1门控调度模型1 1物理网络模型物理网络为全双工交换式互联网络，记为 G=v，ssw，lFD，其中:v 为该网络所有终端的集合，设一个完整的网络中有 n 个终端，表示为 v=vi|i=1，2，n;ssw表示网络交换机的集合，设一个完整的网络中有 m 个交换机，表示为 ssw=sswjj=1，2，m;lFD表示网络中终端与交换机连边的集合，物理网络节点之间采用有线全双工连接，lFD=lij，li ji=1，n，j j，j=1，m，j=1，m，lij表示第 i 个终端与第 j 个交换机的连接状况，lj j表示第 j 个交换机与其他交换机的连接状况，lij，lj j为 0 表示无连接，lij，lj j为 1 表示有连接。1 2数据流量模型时间敏感网络定义了流量具备优先级的特点，优先级集合记为 p，p=pkk=1，2，o。流量模型记为 s，s=sii=1，2，n，其中，si表示第 i 个终端的数据流。流量长度记为 l，l=lii=1，2，n。流量周期记为 t，t=tii=1，2，n。流量优先级记为 q，q=qii=1，2，n，其中，qi=pk。流量内部数据段数据记为 d，d=dii=1，2，n。因此每个终端的数据流量模型 si可表示为 si=li，qi，ti，di。1 3门控调度模型在 IEEE802 1Qbv 标准协议中对门控调度进行了定义与规划，其模型如图 1 所示。图 1门控调度模型Fig 1Gating scheduling model在 Qbv 标准协议中定义了传输门用于控制数据的传输的门，其状态为开和关，当门处于开时，允许与之连接的队列传输数据，当门处于关时，拒绝与之连接的队列传输数据;定义了门的开关操作用于控制队列传输从停止到开始、从开始到停止;定义了门循环用于控制门顺序重复地进行开关操作6 7。门控列表记为 GGCL，GGCL=(T，tts，l)。其中:T 表示门控大周期;tts表示门控小周期，tts=ttsaa=1，2，x，且T=ttsa;l表示门控开关列表，l=laa=1，x，其中，x 为列表长度89。2门控调度算法标准调度传输流程对门控列表的配置只进行一次操作，一般通过在交换机内部存储列表参数，交换机启动运行后读取一次静态参数。但该方式不能适应实际网络环境，因此对于门控调度的研究多集中于门控列表的生成与配置。2 1启发式算法门控列表内参数量大、类型多，其中，门控大周期、门控子周期和每个门控子周期门的开关状态参数是实现门控调度机制的核心。基于此，文献 10 研究并提出了启发式算法，该算法较好地解决了上述参数的动态生成、映射和配置问题。启发式算法的核心是将各个节点的周期数据流在调度表上进行动态分配，生成网络中所有交换机的门控制列表。启发式算法首先选择优先级最高的数据流，然后为该数据流从源端到目的端的路径上分配与数据流长度成正比的传输时隙。随后按照优先级降序对每个数据流重复上述过程。在完成优先级从高到低数据流的时隙分配后，选择最低优先级数据流，判断延迟源端发送该条数据流是否影响到比自身优先级高的数据流传输，若不影响，则延迟源端发送间接降低端到端的时延;若影响，则不做任何改变。随后按照优先级升序对其每个数据流重复上述过程。启发式算法规定门控大周期 T 为T=LCM(ti)(1)式中，LCM(*)表示取最小公倍数函数。因此 T 为所有数据流的周期的最小公倍数。门控小周期 ttsa的分配由该小周期内的传输数据的长度和传输速率决定，表达式为ttsa=lis(2)式中，s 表示网络传输速率。95第 3 期在门控大周期 T 内，每个数据流的传输都需要一次门控操作，门控操作列表 la表达式为la=qi Aoo(3)式中:Aoo表示 o 行 o 列的单位矩阵;qi=pk。因此la=(0)1 (k 1)(1)(0)1 (o k)1 o(4)式中:0 表示门关闭;1 表示门开启。门控操作列表存储于门控列表中，每个门控操作列表在门控列表中存储长度为 1，因此门控列表长度 x由门控操作列表个数影响。在门控大周期 T 内，门控操作列表个数由 T 内有数据流传输的时隙个数 x1和无数据流传输的时隙个数 x2决定。x1表达式为x1=ni=1Tti(5)根据式(2)和式(5)求得 T 内有数据流传输的总时长T为T=ni=1Ttili()s(6)x2表达式为x2=T Tmax(ttsa)=T ni=1Ttili()smax(ttsa)(7)因此 x 表达式为x=x1+x2=ni=1Tti+T ni=1Ttili()smax(ttsa)。(8)2 2算法存在的问题启发式算法在实现门控调度时存在一定的局限性，主要体现在如下几个方面。1)在计算周期数据流传输时隙时，每个 si的周期ti之间数量级不能相差过大，数量级相差越大，式(1)计算值越大，最终导致式(8)计算值也越大，使得交换机内部需要的缓存容量越大。2)启发式算法的核心是对不同优先级的数据先后顺序划分时隙，而对于相同优先级的数据同时同向传输则无控制调度，按照先入先出的原则传输