一种基于TTE调度表的资源分配算法

梁 栋，赵 刚，李世兴，崔迎春，王晓勇

（北方自动控制技术研究所，太原 030006）

0 引言

近年来航空电子体系结构逐渐兴起，时间触发（Time-Triggered）通信机制在它的影响下也渐渐开始被人们所关注。TT体系架构主要是在保证全局时间同步的基础上，通过已经设定好的资源分配计划，使得整个网络能够有序高效地运行，并提高对资源的利用率。时间触发以太网（Time-Triggered Ethernet）就是在上述的架构下提出的，通过用时间触发代替传统网络的事件触发，使整个网络时钟同步的情况下，各种信息流的传输具备更高的实时性。全双工交换式以太网（Avionics Full-Duplex Switched Ethernet，AFDX）在机载信息量增大的情况下暴露了时延抖动大，同步精度低，确定性不够强，带宽利用率低等问题，不能满足DIMA对机载网络的需求[1]。

TTE网络为了满足不同实时性和关键性数据流传输的需求，提出了3种不同的消息类型：时间触发（Time-Triggered，TT）消息，速率受限（Rate-Constrained，RC）消息和“尽力传”（Best-Efforts）消息[2]。TT消息主要传输一些对实时性要求很高的重要信息，传输的优先级最高。RC消息主要传输一些对实时性要求较高的网络信息，优先级低于TT消息。BE消息主要是传输一些对实时性没有太高要求的网络信息，优先级在这三者中的地位最低。

TT消息在网络上根据原先已经规定的时间进行传输，但是如果调度表资源分配不当，各端系统按预先定义时刻发送的TT消息可能会发生冲突，从而导致消息的丢失。本文主要研究了基于调度表的资源分配算法，使交换机能对各个端系统发送的TT消息进行合理的收发。

1 TTE调度表资源分配策略

在TTE网络中，常用的调度方式是在各发送端预先离线设计好任务调度表，然后根据调度表进行消息的发送。调度表中包含一个矩阵周期，由若干个基本周期组成[3-4]。如图1所示，每个基本周期又可以分为两段，TT帧在基本周期前一段时间内发送，RC帧与BE帧在TT帧后面的一段时间内发送。为了不影响下一周期TT帧的发送，在每个基本周期末尾都会预留一定长度的时间作为保护间隔[5]。

在保证了整个网络时钟精确同步的前提下，通过预先设计好的任务调度表，使交换机在接收各个端系统发送的TT流量过程中避免了消息的冲突，减少了数据的丢失。本文不考虑时钟漂移对信息传输的影响，假设系统中设备在每个基本周期开始时全局时钟都是同步的。

图1 基本周期TT段资源分配表

将时间分成若干个基本周期，将每个基本周期中专门接收TT任务的时间段分成有限个时间片，每一个时间片接收一个连接端系统的TT流。在一个基本周期内，交换机要从调度表的表头执行到表尾。当一个新的基本周期开始后，又会重复上面的循环。假如轮到某一端系统不发送TT消息，则相应的时间片为空。上面所述的这种方法就是基于调度表的轮循算法，各个端系统合理分配到调度表中的带宽，既可以保证各个端系统的预约带宽和时延，又可以提高资源的利用率。为了能够实现带宽的合理分配，提高资源利用率，本文提出基于时间触发的公平轮循调度算法。

2 TTE调度表的资源分配算法

2.1 基于时间触发的公平轮循调度算法

设有W个端系统分享交换机的资源，它们各自有自己的预约带宽要求ri（i=l，2，…，W），所有ri的和要小于等于TT段的带宽。

假设每一个基本周期中TT段有L个时间槽，每个时间槽里发送一个连接的TT消息，如果某个时间槽内没有端系统发送的TT消息，则该时间槽为空。

从一个基本周期看，调度器从TT任务的表头执行到表尾，例如在图1中，当时间槽的序号为0时，发送端系统1的TT信息，在时间槽为1时发送端系统4的TT信息，在时间槽n-1没有TT信息发送，显示为空，如此下去直到表尾。下一个基本周期又从TT消息的表头开始重复执行。但是如何对调度表资源进行合理分配，下文中提出一种基于时间触发的公平轮循调度算法。

时间触发公平轮循调度算法：设调度表中一个基本周期TT段的表长为L，基本周期的个数为a，将每个基本周期中的TT段都分成L个时间槽，总共分成aL个时间槽，其中每个时间槽的编号为0，1…L…aL-1，aL，端系统i的预约带宽为ri=ni/aL（1≤ni≤aL，ni为整数，表示各个端系统预约交换机的时间槽的个数），在调度表中，用来表示分配给端系统i的第k（0≤k≤ni-1）个时间槽，定义的开始时标为

理想情况下，交换机应该在时间槽中相应的时标开始时刻接受TT数据，然后在时标结束的时刻将TT数据送出。TTFRR就是依据的时标大小，将调度表中的时间槽合理地逐个分配给每个端系统，当没有TT消息时，显示为空。

2.2 基于时间触发的整形的公平轮循

基于时间触发的整形的公平轮循（Time-Triggered Shaped Fair Round Robin，TTShFRR）主要是通过对结束时标和开始时标的综合利用来实现资源的分配。假设。对调度表中的每一个时间槽T（0≤T≤aL-1）依次进行分配，首先从所有还没有安排的中选出开始时标小于或等于T的组成集合Θ，再从Θ中选出结束时标最小的分配给相应的时间槽。如果有几个的结束时标都最小，则从中任意选取一个。

3 TTShFRR的性能

3.1 TTShFRR调度器的延时性和整形性

首先将漏桶限定作用到端系统i的TT流量上，可用参数（Δi，ri）表示。公式中L为调度表的表长，ri=ni/aL是端系统事先约定好的带宽，端系统i的突发度用Δi表示（单位是信元），则提出定理1。

定理1 端系统i经过TTShFRR调度器的最大信元时延为

证明 在时间段 [k/ri，（1+Δi）/ri+1]（k 为整数）内，端系统i发送的TT信息必定会被调度一次。那么在时间段[t，t+M/ri]（M≥1，M 为整数）内 TT 消息至少会被调度M-1次。假设[t1，t2）是端系统i的一个backlogged时间段（即，在t1之前各个端系统没有消息传输，从t1时间开始一直到时刻t2，端系统i的队列中一直有TT消息在等待调度），假设在backlogged时间段内第k个到达的TT消息的到达时间为bk（k＞1），被交换机选中的时间为dk，那么[t1，bk]内到达了k个TT消息段，由端系统i的TT流量的漏桶参数可得

从前面可以看出，[t1，t1+（k+1）×1/ri]内至少被调度了k次，那么

加上处理的时延，可以得到式（6）。证明完毕。

定理2 端系统i经过TTShRFF交换机输出的TT流量可用参数为（2，ri）的漏桶限制。

证明 在TTShRFF调度器输出流量后端系统i具备了下面几个性质：两个信元之间的最小间隔为1个时间槽，3个信元之间的最小间隔为1/ri，4个信元之间的最小间隔为2/ri，以此类推，那么m个信元之间的最小间隔为（m-2）/ri。假设一个时间为t的时间段中有 m 个信元，那么 t≥（m-2）/ri→m≤ri×t+2，证明完毕。

定理3 端系统i在TTShFRR调度器中所占用的最大缓存为

证明 设[t3，t4]为端系统i从t3开始的某个backlogged时间段，Pi（t3，t4）表示在backlogged时间段内端系统i到达的信元个数，Qi（t3，t4）表示交换机输出的端系统i的信元个数。文献[1]的定理1可知至少有个端系统i的信元在这个时间段内被调度（表示不大于x的最大整数），将处理的时延作为考虑的对象，至少有（）个端系统i的信元被输出。

显然Pi（t3-t4）-Qi（t3-t4）＜2+ri+Δi。证明完毕。

3.2 TTShFRR的公平性

用最大归一化服务量的差别作为公平性的指标。当两个端系统i和j在[t1，t2]时间段内处于backlogged状态，则调度器在此时段内输出的端系统i的时间槽个数Si（t1，t2）和输出的端系统j的时间槽个数Sj（t1，t2）满足如下不等式

4 结论

本文主要研究了一种通过对开始时标和结束时标的综合利用，来完成调度表资源分配的时间触发公平轮循调度算法。TTShFRR提供的最大时延保证与连接数无关，同时还具有良好的公平性。具体实现以上算法时可以在系统中维护两个调度表。在接收端系统发来的TT消息时，交换机设计出新的调度表，旧的调度表继续供端系统使用；当交换机将新的调度表中的数据填好后，新的调度表和旧的调度表进行切换，然后再形成新的调度表。后面将对算法的时延性及公平性等性能进行研究，来证明算法满足网络对实时性的要求。