时间敏感网络流量调度算法研究综述*

王新蕾,周 敏,张 涛

(1.南京信息工程大学 电子与信息工程学院,南京210044;2.无锡学院 江苏省集成电路可靠性技术及检测系统工程研究中心,无锡 214105)

0 引 言

随着科学技术的不断进步,5G、工业物联网、汽车自动驾驶、新一代音视频传输、大数据等新技术应运而生,这些技术需要可靠的数据传输,对传统网络传输技术带来了很大冲击[1]。在传统以太网中,因为终端设备之间共享网络带宽,而这些设备不停地进行流量传输,难免会造成某个设备因流量问题发生网络拥堵,从而不能保证确定和可靠的传输[2]。

2005年,IEEE 802.1工作组成立了IEEE 802.1 AVB工作组,用来保证音/视频桥(Audio Video Bridging,AVB)流的确定性传输。随后,汽车以及传统工业领域也开始关注AVB。2012年,AVB工作组正式改名为时间敏感网络(Time-sensitive Networking,TSN)工作组,正式提出了时间敏感网络这种确定性以太网,研究领域也从AVB流的传输扩展到工业控制网络。在此期间,时钟同步、流量调度、可靠性和资源配置等标准协议逐渐完善。在这之后,多家企业与组织也加入了TSN技术的研究,并将目标转向工业领域,以满足其低时延、低抖动、不拥塞和不丢包的传输要求[3-4]。经过多年的发展,TSN已经成为全球工业界研究和拓展的主流。这种新型网络传输技术能够在一个网络里同时传输周期性和非周期性的流量数据,比起传统以太网,TSN具有确定性和可靠性传输的优势。在TSN工作组不断完善和扩展相关协议标准的过程中,TSN技术已经受到全世界的广泛关注[5],目前在音视频、工业控制和汽车驾驶[6]等领域发挥了重要作用。

IEEE工作组在TSN的协议标准中规定了时间同步、流量调度、可靠性、资源管理4种关键技术。时钟同步机制是TSN的基础,它使所有网络设备的时钟保持一致,从而确保网络的实时性[7]。流量调度是TSN的重要机制,数据在时钟同步机制的基础上,对流量进行整形和调度,使时间触发(Time-triggered,TT)流数据优先完成确定性传输[8]。TSN不仅要保证时间敏感数据的确定性传输,还要确保数据传输过程是安全可靠的,防止出现网络丢包等情况。TSN资源管理机制对网络资源进行合理分配和管理。多家研究机构和大学都在研究完善TSN技术,IEEE工作组指定的802.1Q系列标准协议为后续的TSN研究和应用提供了框架。现在TSN的研究重心放在了无线和5G网络上,对流量调度的要求进一步提高,成为TSN研究的重中之重。

TSN工作组提出了5种基本流量调度机制,一直都是应用领域的标准。众多学者和专家在这些基本框架的基础上改进算法,以实现不同流量的调度。但对于不同的流量,在调度机制或算法的选择上仍需要框架性的分类和研究。本文重点探讨了目前流量调度算法的研究现状以及存在的问题,对调度机制和算法进行了分析,并对未来流量调度算法的发展方向给出建议。

1 TSN流量调度机制

流量调度机制是TSN的关键技术,所有的调度算法和路由方案都是在标准机制框架下完成的。TSN流量调度有以下5种标准机制:基于时间的整形机制、基于信用值的整形机制、循环队列转发机制、帧抢占机制以及异步流量整形机制。

1.1 基于时间的整形机制

为了保障TT流传输时的端到端的低时延,IEEE 802.1Qbv[9]标准提出了时间感知整形器(Time-aware Shaper,TAS),它使用时分多址[10]的思想,将流量分成8个优先级队列。TAS将传输时间划分为多个重复的周期,在每个周期里再划分为两个时间槽,时间槽1调度优先级7(TT流)的流量,时间槽2则调度其他优先级(非TT流)的流量。然而,这种周期性的调度会带来问题,如果时间槽2的流量在当前周期没有传输完成,就会占用下一个周期的时间槽1的传输。为此,TAS规定在时间槽2后面加入保护带,在保护带里不能传输新的流量,只能完成当前流量的传输。图1是带保护带的TAS工作机制。

图1 带保护带的TAS工作机制

在TAS进行流量调度时,会利用门控调度表(Gate Control List,GCL)来控制帧的出队列操作。如图2所示,GCL控制门的开与关,1表示门打开,0表示门关闭。在时钟同步后,门周期性地打开,确定流的有序传输,不同的流队列会选择相应的调度算法进行调度[11]。

图2 门控调度机制

1.2 基于信用值的整形机制

为了保证TSN中AVB流的服务质量不被TT流的调度影响服务质量,IEEE 802.1Qav[12]协议定义了基于信用值的整形机制(Credit Based Shaper,CBS)来对AVB流进行整形和调度。

图3为CBS算法机制的示意图,CBS为每个队列设置一个信用值,只有队列信号值大于或等于0时才能传输数据。当AVB流等待传输时,信用值随着时间线性增长,图中斜率idle slope直到达到最大信用值后保持不变;当AVB流传输时,信用值以send slope为斜率线性下降,直至信用值小于0或其他队列正在传输数据时停止传输并再次以idle slope斜率线性增加,往复进行;如果所有队列都无数据等待传输,则将信用值置0。

图3 CBS调度机制

1.3 循环队列转发机制

为了解决网络拥堵和有界时延的问题,IEEE 802.1Qch[13]提出循环队列转发(Cyclic Queuing and Forwarding,CQF)机制。CQF机制为交换结构设置奇偶循环周期,即以每一跳的时延计算总时延,规避网络拓扑对传输时延的影响。

图4为循环队列转发机制示意图,CQF在每个循环周期内设置两个队列,即队列A和队列B。在奇数循环周期内,队列A只接收帧,队列B则只传输偶数周期接收的帧;在偶数循环周期内,队列A只传输奇数周期的帧而不接收帧,队列B则只接收该偶数周期的帧。如此循环交替接收传输,所有TT流都能实现有序传输。

图4 循环队列转发机制

1.4 帧抢占机制

在调度过程中,可抢占帧的持续传输会阻碍快速帧的及时传输,从而影响快速帧的传输时延,而且1.1节中提到的保护带也会造成带宽浪费[7]。为此,IEEE 802.3br[14]标准定义了快速MAC和可抢占MAC两个子层,对帧抢占(Frame Preemption,FP)的切片和还原进行解释说明。IEEE 802.1Qbu[15]标准则规范了帧传输过程中的抢占接口和模块。

帧抢占要满足以下两个条件:只能在全双工点对点链路中使用;每个被切片的可抢占切片需大于等于64 B[16]。如图5所示,帧抢占的过程为:首先判断可抢占帧是否满足切片条件,若可以切片,则当可抢占帧传输完64 B后开始切片并插入循环冗余校验码;然后开始传输快速帧,之后在剩余可抢占帧切片尾部加入校验和,开始补全余下低速帧的传输。

图5 帧抢占机制

1.5 异步流量整形机制

CQF和TAS机制虽然能为TT流提供低时延的传输,但它们都依赖高精度的时钟同步,同时在多个周期内强制传输数据,这也会造成带宽上的浪费。IEEE 802.1Qcr[17]提出了一种异步流量整形器(Asynchronous Traffic Shaper,ATS),它是基于事件紧急性的调度器(Urgency-based Scheduler,UBS)[18]。UBS划分队列为一个流量整形队列和一个共享队列,流量整形队列为流分配固定的优先级,而共享队列把相同优先级的流放在同一队列,先到的流先调度。

ATS调度机制如图6所示,它对可调度(Scheduled Traffic,ST)流和BE流进行调度,流量在经过ATS整形之后才能进入相应队列。ST流在ATS中经过判断事件紧急性,一部分进入紧急队列,分组调度至速率控制器,之后采取不同速率到达输出端口;另一部分则与BE队列一起调度。

图6 异步整形机制

1.6 流量调度机制小结

TSN中的流量调度可分为两种,即同步调度和异步调度。TAS和CQF属于同步流量调度,而CBS、FP和ATS则属于异步调度流量调度。同步流量调度虽然有时延抖动较低,但是很难适配应用环境;异步流量调度则有着良好的带宽利用率,但抖动比同步流量调度大。表1从时间和优缺点方面对上述5种调度机制进行了对比。

表1 流量调度机制对比

2 TSN调度算法研究现状

TSN将流量划分为TT流、AVB流和尽力而为(Best-effort,BE)流[19]。TT流需要满足低时延和低抖动的要求以实现确定性传输。AVB流由事件触发,只需要确保端口之间的有限时延。BE流就像其名字一般,对时延没有要求,它更关心吞吐量。

调度算法是在5种调度机制上针对调度目标、约束条件、路由选择等的优化方案,其中TAS、GCL、CBS和帧抢占机制为当前TT、AVB和BE流的调度提供基本框架,现有大多数调度算法都在这个框架内进行改进和优化。本文主要对TT流、AVB流以及BE流调度算法的研究现状进行分析和探讨。

2.1 TT流调度算法研究现状

传输时延一直是实时通信一大难题。为了最小化端到端时延,Schweissguth等人[20]提出了一种新型整数线性规划(Integer Linear Programming,ILP)算法,解决了TSN在联合路由调度时TT流无法选择最短路径路由而导致时延变大的问题,提供了比TT流单独调度的固定负载平衡路由更低的通信时延。Nayak等人[21]在此基础上做了改进,引入了最大调度传输负荷和跳数因素,同时最小化了传输负荷和所有流在路由上的累积跳数,大大减少了时延。而Schweissguth等人[22]在之后的研究里增加了对多播流的支持,并提出了一种资源约束优化方法。在优化流时延方面,该方法将ILP模型大小减少了49%以上,将求解时间减少了47.6%。Pang等人[23]则结合软件定义网络建立了一个新型整数线性规划调度模型,同时考虑静态和动态调度。静态调度算法具有更好的TT流可调度性,动态调度算法消耗的时间更少,可调度性略有下降,而这两种调度下都实现了零帧丢失。钟龙[16]则以单调速率调度(Rate Monotonic Scheduling,RMS)算法为基础,提出了一种基于多周期应用的调度算法,将分组调度问题类比于车间作业,对周期、端到端时延、流调度、RMS和门事件进行约束,有效降低了端到端时延。同时他还提出了一种合并门控机制,有效降低了传输损耗和门事件数量。

一些学者更加关注路由与流量整体调度问题。Pahlevan等人[24]增加了路由的节点数并提供更多的路由选择,提出了一种基于遗传算法(Genetic Algorithm,GA)的联合路由调度方法。该方法减少了TT流传输的总时长,还考虑了多播模式对TT流造成的带宽影响,这使得TT流的可调度性、传输效率以及带宽利用率有了显著提高。Huang等人[25]为了减少流量调度的计算时间,提出了一种新型调度感知路由算法。算法考虑了TT流的周期,确定了每个TT流的路径,减少了流量调度阶段路径冲突的发生,将流量调度过程中的计算时间缩短了30%,提高了TT流的可调度性。裴金川等人[26]采用时空联合规划的思想,对时间敏感网络中时间敏感流量的调度与路由分离问题,提出了一种联合无冲突路由规划的调度方法。时间上基于时分多址思想建立TT流的调度约束模型,空间上结合TT流调度特性灵活分配流量路由,在此基础上建立TAS和联合无冲突路由的调度约束模型,保障TT流调度的有界低时延需求。

可满足性模理论(Satisfiability Modulo Theories,SMT)求解器经常用于解决约束条件问题。为了解决TT流调度带来的品质下降的问题,Craciunas等人[27]提出一种基于SMT的回溯算法,将帧偏移量和队列分配定义为整数变量,以满足约束条件为目标,引入了一种增量回溯算法。算法通过向SMT公式添加流变量和约束来探索有效解,从而一次调度一个流。如果找到了解决方案,则继续下一个流的调度。重复步骤,直到所有流都完成调度或者求解器找不到有效解。在后一种情况下,当前流的约束无法满足上一个SMT公式,则删除最后一个流并将其与相关的不可行步骤一起重新引入来回溯SM求解器。Li等人[28]基于SMT,提出了一种面向工业场景的TSN调度算法。在每个端口使用SMT算法计算满足约束条件的时间窗口分配,使用链路中所有TT流的最大公约数取代原有的链路超周期,成为GCL的更新周期,可以有效减少GCL中的时隙数量,使GCL的配置更简单、更高效,还可以更快地计算出调度结果,保证TT流的低延迟,有效地减少运行时间。

为了实现多种调度目标,一些学者采用复合调度方法求解问题,或在一种调度方法中使用其他方法求解问题。Falk等人[29]着眼于调度的等待时长问题,将初始的传输路径规划问题转化成冲突图中的极大独立点集问题。在冲突图中,把流的数据何时沿着网络中的哪条路径传输定义为流的极大配置(configuration vertices,cvertex),每个cvertex只能有一个配置,而当两个cvertex的边界采用了各自的配置就会产生冲突。当独立点集包含所有流时则为极大独立点集。Falk等人使用ILP与极大独立点集的复合方法来遍历每条流的cvertex,这使得冲突图不断扩大并在冲突图中探索极大独立点集,直到独立点集包含所有的流,返回对应的路由和调度方案。曹志鹏等人[30]则提出一种基于K-最短路径(K-Short Path,KSP)的负载均衡路由算法和改进遗传算法的流量调度方法:负载均衡路由算法减小了网络拥堵发生的概率;改进传统遗传算法算子的交叉和遗传概率,提升了迭代速度,从而大幅缩短时延,减少完成时间。臧宇航等人[31]针对域内网络的调度改进了贪婪随机自适应搜索(Greedy Randomized Adaptive Search Rrocedure,GRASP)算法。该算法以调度成功率为目标,能够减少链路堵塞,最小化时延以及提高解的准确率。同时,为了联合路由调度,还提出一种双向A*均衡路由算法,分别从起点和终点两个方向在路由间找到最短路径,提升搜索效率,引入风险均衡思想,优化路由选择,提高调度成功率。

上述文献都提出了自己的调度算法,但大多数是静态调度,如果网络出现抖动就需要重新调度,因此动态调度成了新的重点研究方向。Nasrallah等人[32]设计了一种自适应时隙窗口(Adaptive Slotted Windows,ASW)算法,通过对GCL动态配置ST流和BE流的传输速率比,暂时牺牲BE流的QoS而为高优先级TT流带来超低的时延。Yu等人[33]提出了一种新的自适应组路由和调度(Adaptive Group Routing and Scheduling,AGRS)算法,首先设计了一个预处理阶段来加速动态应用的综合调度过程,删除不必要的节点,并自适应地将符合条件的拓扑完整子图分组;在此基础上,还提出了一种综合考虑路由和调度过程的路由调度程序,以提高可调度性。该过程基于简化的拓扑结构,从而大大减少了执行时间。在文献[33]的研究基础上,冯泽坤等人[34]提出了一种基于ILP的动态流量均衡调度算法,对路由、流的传输定时、无争用、时延和链路负载进行约束,不仅生成了满足实时性的调度表,还保证了链路的负载均衡,让处理动态调度变得更为迅速和准确。周小明等人[35]以最小化TT流的端到端时延为调度目标,提出了一种GCL自适应调整算法。该算法根据可接受的最差时延上界Lexp算出扩容阈值Let,然后通过集中式网络控制器(Central Network Controller,CNC)计算一个GCL周期里实际传输TT帧的个数Nact,此时与最大可传输帧N进行比较,若Nact≠N,则缩小TT流窗口并动态配置到交换机,返回CNC重新计算;当Nact=N时,则判断平均端到端时延Lact是否大于端到端最大时延L或Let,若满足,则扩大TT流窗口并动态配置到交换机,否则返回CNC重新计算。这种算法通过动态配置交换机,保证了TT流的可靠传输,优化了TT流传输的平均时延。

2.2 AVB流调度算法研究现状

仅仅对TT流进行调度有时会导致AVB流在最坏情况下出现时延等问题,因此有必要对AVB流量调度问题进行研究。Berisa等人[36]考虑到GCL中任意数量的AVB队列和CBS信用值的不同配置,提出一种具有帧抢占特征的启发式算法和一种旨在最大化AVB可调度性的新型路由机制。对具有抢占的TSN网络中的AVB流提出了一种新的最坏情况响应时间分析,将TT调度表的创建与AVB流量的可调度性分析结合起来,最小化TT流端到端时延,同时提高AVB流可调度性。Pop等人[37]同时对TT流和AVB进行流量调度,对TT流的调度问题提出了一个ILP调度算法,而在AVB调度问题上则使用了一个基于GRASP的调度算法,同时保证了TT流的调度以及最小化AVB在最坏情况下的端到端时延。Laursen等人[38]则提出了一种KSP和GRASP复合算法来寻找最优GCL方案,不仅降低了TT流传输和抢占对AVB流的影响,还最小化了AVB流调度的最坏端到端时延和保证了带宽利用率。Gavrilut等人[39]提出了一种以禁忌搜索(Tabu Search,TS)的元启发式算法为基础的流量类型分配(Traffic Class Assignment,TTA)算法,用于确定混合临界硬实时和软实时报文的传输类型(AVB流和TT流)的分配,还同时优化了TT流和AVB流的可调度性。王宇涵等人[40]则同时对TT流和AVB流进行实时在线调度,针对TT流的实时调度,提出了基于虚拟最早截止期优先(Virtual Earliest Deadline First,VEDF)的硬实时调度算法。该算法在TT流的每个节点设置一个区域,TT流只有在该区域内到达才能优先调度;针对AVB流的调度,将启发式调度算法和max-sum算法结合,将流开始传输的时间设为变量,约束关系作为函数,迭代计算AVB流传输的开始时间,同时对AVB流的优先级也有所设置,极大地减少了端到端时延和传输完成时间。

2.3 BE流调度算法研究现状

目前国内外对TSN流量调度的研究主要集中在TT流和AVB流上,从而忽略了BE流传输调度问题。Nasrallah等人[32]提出了一种基于TAS机制的自适应带宽共享(Adaptive Bandwidth Sharing,ABS)算法,以提高链路利用率。ABS算法允许BE流在等待传输时,ST流可以与其暂时共享时隙带宽。这样既减少了ST流的传输时延,又保证了BE流的低时延和可调度性。TSN在保证有限的时延和抖动的同时,也暴露出不能有效利用保护带带宽资源的缺点。为此,Zhang等人[41]提出了一个名为包大小感知整形(Packet-size Aware Shaping,PAS)的算法。PAS做出调度决策,计算调度过程的每个包的大小和剩余带宽的数量。PAS在不要求专用MAC层的情况下追求近似于帧抢占的性能,最终使流的优先级和带宽利用率最大化,保障了BE流的传输效率。张楠浠等人[42]针对BE流的调度的3种场景提出了一种抢占式尽力而为流时序重排调度算法,有效减少了带宽资源浪费,提高了带宽利用率。

2.4 流量调度算法研究小结

TSN流量调度算法在当前的调度机制框架上,针对不同调度流量和目标提出了各自的方案,大幅优化了性能。表2列出了文献中提出的算法所用到的调度机制、优势以及缺点。当前的TSN流量调度,除了针对路由选择的算法,TT流的调度离不开TAS机制,而不管是哪种流量类型的调度,都需要通过GCL进行配置,这不免会使流量调度产生局限性,未来可以考虑基于CQF和ATS机制进行算法的改进。TSN调度算法解决了许多调度问题,优化了TSN的流量调度,但同时也会造成求解质量低、求解时间长、适用场景小等问题,需要综合多方面因素,针对实际应用场景进一步改进算法。

表2 调度算法对比

表3总结了TSN流量调度的调度算法、调度流量类型、调度目标、联合路由以及动/静态等特点。目前的流量调度不仅能够保证流量在网络中的有序传输,还大幅优化了实时流量的时延和有界时延抖动问题,而且对端到端时延、约束条件、带宽利用率、可调度性等方面进行优化,实现了性能的提升。但仍然存在着以下三个问题,即联合路由调度问题、混合流量的整体调度问题和实时流动态调度问题。

表3 TSN流量调度总结

1)现有的TSN流量调度大多采用传统以太网的路由方案,只考虑最短路径、负载均衡等指标,没有考虑到TSN不同流量类型的不同要求。表3中虽有联合路由调度的算法,但大多只适用于小规模网络中,仍需考虑实际运用时的可行性。

2)现在大部分对TSN的研究集中在TT流上,而对AVB流和BE流的研究还相对较少。表3列出了一些混合流量调度算法,为了优化ET流的传输性能,大家开始关注AVB流与BE流,在保证TT流可调度的前提下,为其他流量留出队列数以实现混合流的整体调度。但是对AVB流和BE流的研究主要是关注其时延和带宽利用率,并没有对两种流量进行针对性优化。

3)现有的TSN流量调度几乎都是静态调度,缺少对动态调度的研究,会导致实时调度时会出现无法应对丢帧、时间同步误差大等问题,这极大地影响了流量传输的可靠性。表3中有些研究虽提出自己的方案,但解法过于复杂,且只能做到局部动态调度,需要不断优化。

3 流量调度算法发展方向

TSN调度算法研究至今,已经解决了标准协议里很多问题,但是仍然存在路由选择、忽视ET流调度和缺少动态调度等问题。针对这些问题,学者们提出了一些解决思路,这也是未来TSN流量调度算法的研究方向。

目前TSN调度算法的发展方向有联合路由调度、混合流量调度和动态调度等。

1)联合路由调度

很多TSN流量调度算法无法根据不同类型的流选择不同的路由,降低了传输性能,因此需要综合考虑流量和路由问题,给出整体调度方案,将路由选择作为变量,扩大可行解的空间,实现调度目标。不过这种方案也主要适用于静态调度,在动态调度中联合路由调度是目前的研究重点。

2)混合流量调度

混合流量调度在保证TT流的可调度性的前提下,尽可能为AVB流和BE流留下队列和时隙。而目前的混合流量调度算法依赖于标准协议规定的基本调度机制,TT流的调度基于TAS机制,AVB流的调度基于CBS机制,通过门控开关实现不同流量的混合调度。未来可以基于CQF机制和ATS机制提出新的算法。

3)动态调度

由于很难实现全局动态调度,所以目前对动态调度的研究仅限于局部调度。采用全局静态和局部动态的调度方式是现在重点研究方向,全局只需规划TT流和ET流的队列分配方案,落实到各个端口再使用动态调度,这样可以减少传输时延,保证流的可调度性。

针对混合流量的调度,可以考虑当网络拓扑和调度流量固定时,预先计算不同流量在最坏情况下传输完成时间来获得时间槽占用率,判断流量是否满足带宽占用条件,对超出带宽占用的流量重新分配合理的时间槽,这样生成的GCL静态调度表可以实现3种流量的整体调度;对于联合路由的动态调度,可以在每个交换节点和终端添加监控,在拓扑初始化过程中将新访问的节点信息输入到配置文件中,以更新网络拓扑,实现动态调度。

4 结束语

时间敏感网络作为一种综合高精度时间同步和多业务融合传输的确定性网络技术,将信息网和控制网有机融合,已成为工业互联网、车载通信网络以及新一代军工航电领域通信网络构建的关键技术。本文根据流量类型对流量调度算法进行归纳总结,从调度算法和整体调度方案两方面给出了对比分析。尽管调度算法优化了流量的调度,但仍然存在联合路由调度、混合流量调度以及动态调度的问题。针对这三个问题,分别提出未来的研究方向,可以利用时间槽的合理分配和在每个节点添加监控以实现混合流量动态调度的新思路,为后续TSN流量调度算法研究提供建议。