时间触发以太网(TTE)^[1]是支持时间触发、速率约束和普通以太网流量的综合化网络互连技术，其中时间触发(TT)流量的发送、转发和接收时刻由静态调度表决定，具有严格的时间确定性，适用于航空、航天、车辆等高安全关键性应用领域^[2-4]。TT流量调度涉及包含无冲突约束、路径依赖约束等在内的多种约束条件，推出TTE的TTTech公司的科研人员提出采用可满足性模理论(SMT)约束求解的时间触发调度表生成方案^[5]。SMT求解器^[6]本质上只能蛮力搜索调度表的可行解，随着流量规模的扩大，为了降低每次搜索的规模，采用增量化的调度表生成方法，一次只求解一个流量子集的调度表^[5]。然而，如果不考虑可调度性对求解过程的影响，且在每次输入流量子集的时候不对约束条件进行缩减，仍然经常出现长期不停机的情况。

对于具有严格周期性要求的TT流量^[7]，可调度性的分析与测试方法可以借鉴文献[8]引入的干涉时间的概念，以及文献[9-10]关于多处理器下严格周期任务可调度性判定的相关方法，进而将严格周期可调度性的测试方法引入到TT流量调度表增量化生成中；更进一步，笔者发现SMT增量化求解过程不仅受限于是否可调度，而且其计算效率和回溯次数与流量集合可调度的难易程度有关。

本文的贡献在于，提出了一种基于可调度性排序的增量化时间触发调度表生成方法。不仅可以通过TT可调度性测试先排除完全不可调度的情况，而且在SMT增量化求解过程中，充分认识到严格周期利用率因子(SPU)^[11]对于TT流量可调度性的综合量化能力，依据SPU值对流量按调度难度降序排列，在给定的求解步长下将流量分批，组成可调度性能依次递减的流量子集，先难后易增量化求解；并且，通过计算已调度集合对未调度集合的干涉时间得到未调度流量发送时刻的可行范围，起到缩减约束数量的作用，使计算效率不仅优于原始的SMT调度求解方法^[5]，而且在网络规模较大的情况下，回溯次数显著低于随机和周期升序排序的增量化调度方法。另外，在“干涉时间”的论证过程中，给出一种基于时间轴延拓的干涉时间计算方法；与原来的将每个消息传输时刻对周期取模^[8]的方法相比，更加易于理解。

本文首先介绍了TT流量的调度约束条件，并归纳了单网段下新增TT流量的可调度性判定规则；其后，详细阐明基于可调度性排序的TT流量增量化调度表生成方法；最后，通过案例研究和对照组实验展示了本文所提出的调度方法的高效性。

1.   TT流量的调度约束条件

TTE的物理拓扑可表示为一个无向图G=(V, E)，其中节点集V代表端系统和交换机，边集E代表连接节点的物理通信链路。物理链路仅存在于交换机节点间或一个交换机和一个端系统节点间；每条物理链路(电/光缆)都是全双工通信，以(v₁, v₂)表示，其中v₁, v₂∈V；而物理链路中包含的双向数据流链路(Dataflow Link, DL)，以[v₁, v₂]和[v₂, v₁]来表示。

在TTE中，每条TT流量都以帧(消息)的形式周期性地传输。设F_TT={f₁, f₂, …, f_n}为一个包含n条TT流量的集合，每条流量f_i都有且仅有一个源节点(端系统)，并通过树状路径P_i连接到一个或多个目的节点(端系统)。这种树状路径P_i可以表示为一组数据流链路的集合，即P_i={L_{i, 1}, L_{i, 2}, …, L_{i, m}}。

用一个四元组来表示一条TT流量f_i：

式中：p_i为流量的周期；l_i为帧长(消息的传输时间)；o_i为一个集合，表示流量f_i在其经过的所有数据流链路上的起始发送时刻(第1个帧的发送时刻)，即o_i={o_i^{(L_{i, 1})}, o_i^{(L_{i, 2})}, …, o_i^{(L_{i, m})}}。因为TT流量基于严格周期发送，即流量f_i在链路L_{i, k}上的任意第r个帧的发送时刻为o_{i, r}^{(L_{i, k})}=o_{i, 1}^{(L_{i, k})}+(r-1)p_i，所以只需考虑第1个帧的发送时刻，此后令o_i^{(L_{i, k})}=o_{i, 1}^{(L_{i, k})}。在实际应用中，选取合适的时间单位将p_i和l_i规范为正整数，且令o_i^{(L_i, k)}的取值为非负整数。

在TTE中，TT流量的起始发送时刻o_i需要满足一系列的约束条件^{[5, 7, 12]}。

1) 流量周期约束。任意一条TT流量的第1个帧在其经过的所有数据流链路上的派发时刻应限制在第1个周期内。

2) 无冲突约束。任意一条数据流链路上，不同流量的帧发送时间区间互不重叠。即对于∀f_i∈F_TT和f_j∈F_TT，且i≠j，如果它们经过某条相同的数据流链路L_{i, k}=L_{j, h}，则对于取值范围为的任意负整数a和取值范围为的任意非负整数b，要求式(3)和式(4)同时成立；其中LCM(p_i, p_j)为p_i和p_j的最小公倍数。

3) 路径依赖约束。TT流量的单跳延迟有范围限制。min(d_hop)为单跳延迟下限，由物理链路固定传输延迟决定；max(d_hop)为单跳延迟上界，由交换机的内存大小决定。

4) 中继同步约束。对于多播流量f_i，由相同节点分叉出的路径上消息的发送时刻相同。

5) 端到端传输约束。限定流量从源节点到目的节点的端到端最大允许传输延迟为max(d_latency)。设流量f_i有Q个目的节点(Q为正整数，Q≥1)，不失一般性，令源节点对应的起始链路序号为1，对应目的节点的末端链路序号为m_q(q=1, 2, …, Q)。

6) 应用层约束。在应用层，由于不同的TT流量有不同的任务要求，所以可限定从同一端系统节点出发的所有TT的起始发送时刻的最小间隔δ^[13]，设所有TT源端起始链路序号均为1。

7) 协议控制帧(PCF)约束。在TTE中，各个通信节点本地时钟的同步，通过时钟同步消息的交换来实现，这种时钟同步消息即PCF帧。因此，PCF帧的传输相比普通TT流量有更高的优先级，即TT流量的调度不能与PCF帧占用的时间资源冲突。

2.   新增TT流量的单网段可调度性

TT流量遵循严格周期调度的形式。在某一条数据流链路(单网段)上的TT流量调度问题等价于单处理器下的严格周期任务调度问题。第1节中约束1)、约束2)决定了TTE网络整体配置的可行性，是新增TT流量在每个网段必须满足的条件。由于这些必要性条件易于检查，在SMT求解之前可以快速排除不满足无冲突约束的新增流量。

将文献[10]中的严格周期任务的判定条件推广到TT流量，作为单网段可调度性的判定依据。

定理1  对∀f_i, f_j∈F_TT，i≠j，若有L_{i, k}∈P_i，L_{j, h}∈P_j，L_{i, k}, L_{j, h}∈P_i∩P_j且设L_{i, k}和L_{j, h}是同一条数据链路，则2条流量在这条数据流链路上无冲突传输的充要条件如式(9)所示：

式中：g_{i, j}为p_i和p_i的最大公约数。

设网络中已存在具有可行调度的流量集合F_TT={f₁, f₂, …, f_n}，需要考查新增单条流量f_r在其某个数据流链路L_{r, s}上的可调度性问题。

借鉴文献[8]的“干涉时间”概念，即待考查的流量经过的某一条数据流链路L_{r, s}，存在已获得调度的其他流量，则在新增流量f_r一个周期内的时间单元集合T_r={0, 1, …, p_r-2, p_r-1}中会有部分单元已占用。对于给定的某条已获得调度的流量，可以将其每个消息的释放时刻对p_r取模^[8]评价其对于新增流量的干涉情况；但本文给出并证明的方法(参见定理2)是从已存在流量的初始时刻合理延拓时间轴，在一些离散时刻进行检测，同样可以得到干涉情况，且具有更直观的效果。

定理2(基于时间轴延拓的干涉时间计算方法)网络中2条流量f_i、f_r，若存在L_{i, k}∈P_i、L_{r, s}∈P_r，且恰好L_{i, k}和L_{r, s}是同一条数据链路(记为L_{i, k}=L_{r, s})，则流量f_i在该数据链路上对f_r干涉的时间单元集合I(i, k, r, s)可由式(10)计算得到：

式中：t为离散时间点；g_{i, r}为p_i和p_r的最大公约数；α和β为非负整数，取值为α=0, 1, …, (l_i-1)和β=0, 1, …, (p_r/g_{i, r}-1)。

证明  为保证2条流量f_i和f_r无冲突传输，由式(9)可得，o_r^{L_{r, s}}不能选取(会发生冲突)的全部时间单元在区间，其中为任意整数。显然，这些时间单元以g_{i, r}为周期无限延伸；由于g_{i, r}能整除p_r，这些冲突时间单元也以p_r周期性重复，从而可以任取时间轴上长度为p_r的区间，将其中的冲突时间单元对p_r取模即可得I(i, k, r, s)；运算中的取值范围限制为{0, 1, …, (p_r/g_{i, r}-1)}，被重新记为β。  证毕

根据定理2，可以求出流量集合F_TT在链路L_{r, s}上对f_r的全部干涉时间单元集合：I_all(r, s)=。

然后，再计算排除干涉时间单元后T_r中剩余的连续空闲时间长度的最大值，若该值大于等于l_r，则f_r在L_{r, s}上可以严格周期调度^[8]。引用文献[9]中定义的函数LLC()来表示一个非空集合中连续整数的最长长度。因此，新增流量f_r在其任意一条数据流链路L_{r, s}(s=1, 2, …, m)上可以无冲突传输的充要条件为

3.   增量化TT调度表生成方法

3.1   方法步骤

基于可调度性排序的增量化TT调度表生成方法的总体步骤如下：

步骤1  先对集合F_TT进行可调度性测试，具体包括端系统测试和交换机测试：如果测试未通过，则返回“不可调度”；若测试通过，继续步骤2。

步骤2  通过计算TT流量的SPU，将集合F_TT中的流量按照可调度性由难到易的顺序进行排序，排序结果对应为TT流量序列R_TT=[f_R1, f_R2, …, f_Rn]。

步骤3  每次增加的流量条数被称为SMT增量化求解的“步长”，记为变量Δ，并设当前待求解流量的序号范围为B~E(即E=B+Δ-1)；初始化参数：B=1，E=Δ；并在SMT求解器中创建一个逻辑上下文语境，用于存储添加的约束，记作“CTX”。

步骤4  清空CTX，并根据第1节所述，生成待调度流量集合F_{TT_curr}={f_Ri|i=B, B+1, …, E}的调度约束，并将生成约束增加到CTX中；其中“无冲突约束”和“应用层约束”均包含两部分，即“已调度流量集合F_{TT_succ}={f_Ri|i=1, 2, …, B-1}和待调度集合F_{TT_curr}之间”、“待调度集合F_{TT_curr}内部”，其他约束只需考虑待调度集合F_{TT_curr}内部。

步骤5  调用SMT求解器检查CTX的可满足性，若“满足”，则可从SMT求解器中获取满足CTX中所有约束的一个模型(model)，它是待调度集合F_{TT_curr}中流量发送时刻的一组可行解，记录之，执行步骤6；若“不满足”，执行步骤7。

步骤6  调整参数：B=E+1，E=min(B+Δ-1, n)；若B>E，结束调度方法，返回“调度成功”，否则继续步骤4。

步骤7  若B=1，结束调度方法，返回“调度失败”；否则，执行回溯操作：B=max(B-Δ, 1)，继续步骤4。

3.2   TT可调度性测试

类比于文献[10]中严格周期任务调度意义下的厚度概念，定义一组TT流量F_{TT_group}={f₁, f₂, …, f_m}的厚度C_{TT_group}为按严格周期形式传输TT集合F_{TT_group}中所有流量所需的数据流链路的数目。

将多处理器下严格周期任务的可调度性分析方法^[9]推广到流量厚度C_{TT_group}的计算中。将集合F_{TT_group}中的TT流量逐条放到数据流链路上；在已有的TT流量的基础上，由于只是逐条增加，并不涉及新增流量之间的可调度性计算；该方法的关键是判断单个数据流链路在已调度的TT流量基础上，是否能够无冲突传输新增的某条TT流量，这一判断可以利用定理2计算干涉时间，通过式(11)来完成。

基于TT流量的厚度计算，可以对TTE网络中待调度的TT流量集合进行如下的可调度性测试。

1) 端系统测试：对TTE网络中的每个端系统，分别统计其发出、接收的TT流量集合F_{TT_out}、F_{TT_in}；测试通过准则为C_{TT_out}≤1且C_{TT_in}≤1。

2) 交换机测试：对于含有多级交换机SW的网络，端系统ES接入的交换机通过各个端口与下一级交换机全双工互连。检查对象为端系统接入的交换机SW^*(N>M)，如图 1所示。设交换机SW^*所连接的N个端系统集合为V₁，TTE网络中的其余端系统集合为V₂，统计源端系统属于V₁目的端系统属于V₂的TT流量集合为F_{TT_out}，而源端系统属于V₂目的端系统属于V₁的TT流量集合为F_{TT_in}；测试通过准则为C_{TT_in}≤M且C_{TT_out}≤M。

图  1  端系统接入的交换机示意图

Figure  1.  Schematic diagram of switch accessed by end systems

下载: 全尺寸图片 幻灯片

3.3   考虑可调度性的TT流量排序

TTE要求所有TT流量均可调度，因此在求解次序的安排上，将TT流量按照可调度难度降序排列；在排序过程中，流量的可调度性难度是用SPU^[11]来衡量的。具体方法如下：

输入：待排序的TT流量集合F_TT={f₁, f₂, …, f_n}。

输出：以可调度性增序排列的TT流量序列R_TT=[f_R1, f_R2, …, f_Rn]，重新排序的索引集合{R_i}, i=1, 2, …, n。

步骤1  将F_TT赋予某临时变量集合S存储，令R_TT为空集∅。

步骤2  如果S为空集，则结束运算，输出R_TT；否则执行步骤3。

步骤3  分别计算集合S中流量f_i的SPU值，作为严格周期利用率因子u_S⁽ⁱ⁾，如式(12)所示:

式中：u_S⁽ⁱ⁾由两部分计算累加而成; 为单独传输流量f_i所需带宽; 为集合S中除了f_i之外的其余流量对流量f_i的干涉时间所占用的带宽。

步骤4  u_S⁽ⁱ⁾值越小，则在S\{f_i}中的流量已经被调度的条件下，新增流量f_i无冲突调度的可能性越大，调度难度越小；找到集合S中使u_S⁽ⁱ⁾最小的TT流量，并将它的索引记为k。

步骤5  将流量f_k从集合S中移除，并将f_k添加到R_TT序列的最前端，形成按照SPU值降序的序列，随后返回执行步骤2。

3.4   无冲突约束规模的缩减

在增量化TT调度表求解中，一次只生成流量的序号范围为B~E的TT流量子集(待调度集合F_{TT_curr})的调度约束(3.1节步骤4)。在TT流量的几类调度约束中，无冲突约束数量最多，且最为重要，用于保证网络中所有TT流量传输的时间区间互不重叠。

在生成待调度集合F_{TT_curr}的无冲突约束时，不仅要考虑F_{TT_curr}内部的TT流量之间互不冲突，还要确保这部分TT流量与网络中已调度流量集合F_{TT_succ}间的无冲突传输；其中后者的约束数目会随着B值的增长而迅速增加。

考虑到网络中已调度流量F_{TT_succ}的调度表已知，所以对于F_{TT_curr}与F_{TT_succ}间的无冲突约束生成，可以不采用传统的规范形式(见式(3)和式(4))，而采用集合间无冲突约束的生成方法。通过计算网络已调度流量F_{TT_succ}在L_{r, s}上对流量f_r(f_r∈F_{TT_curr})的干涉时间，求出f_r在L_{r, s}上的空闲时隙集合T_free(r, s)；再从集合T_free(r, s)中顺次寻找连续整数长度大于等于消息长度的区间，进而得到o_r^{(L_{r, s})}的可行取值范围。集合间无冲突约束的生成方法如下：

输入：TT流量的已调度集合F_{TT_succ}和待调度集合F_{TT_curr}，SMT求解器中用于存储约束的逻辑上下文语境CTX。

输出：F_{TT_succ}和F_{TT_curr}集合之间的经过优化的无冲突约束，并添加到CTX中。

步骤1  令流量序号r=1，路径序号s=1。

步骤2  在待调度集合F_{TT_curr}中选取第r条流量f_r。

步骤3  选取流量f_r所对应的路径集合P_r中第s段数据链路D_{r, s}。

步骤4  计算已调度流量在数据链路D_{r, s}上对f_r的干涉时间单元，并赋给集合I_{TT_succ}(r, s)。

步骤5  在流量f_r的1个周期内的时间单元集合T_r中排除受干涉的时间单元，并赋给集合T_free(r, s)。

步骤6  在T_free(r, s)中查找到第1个连续整数长度不小于消息长度l_r的区间，设区间的左右端点为t₁和t₂，t₁≤t₂，记为闭区间[t₁, t₂]；如果找不到这样的区间，则令t₁=0和t₂=0。

步骤7  如果[t₁, t₂]为[0, 0]，则跳转到步骤10；否则形成约束如式(15)所示，并将该约束以逻辑“或”的关系添加到CTX。

步骤8  在T_free(r, s)中顺次查找到下一个连续整数长度不小于消息长度l_r的区间，仍用t₁和t₂存储区间左右端点的值；如果找不到这样的区间，则令t₁=0和t₂=0。

步骤9  跳转到步骤7。

步骤10  如果P_r中还有未被选取的数据链路，则令s=s+1，跳转到步骤3。

步骤11  如果f_r中还有未被选取的TT流量，则令r=r+1，s=1，跳转到步骤2；否则，结束运算，输出添加了新约束后的CTX。

如果采用令式(3)和式(4)同时成立的传统无冲突约束规范，为了保证与F_{TT_succ}不冲突，o_r^{(L_{r, s})}的约束个数N₁(r, s)如式(16)所示:

而采用集合间无冲突约束的生成方法，生成已调度流量F_{TT_succ}与待调度流量F_{TT_curr}间的无冲突约束，约束规模取决于可行区间[t₁, t₂]的个数。因此对于∀f_r∈F_{TT_curr}, ∀L_{r, s}∈P_r，与o_r^{(L_{r, s})}有关的约束个数范围为式(17)，其中不等式右边为f_r在L_{r, s}上空闲时隙集合T_free(r, s)中连续整数区间个数的上限值。考虑到并非所有空闲区间的长度都能达到l_r，并且F_{TT_succ}中不同流量在L_{r, s}上对f_r的干涉时间区间可能会有重叠，因此实际可行区间[t₁, t₂]的个数(即N₂(r, s))通常会远小于这个上限值。

因为，所以采用优化后的无冲突约束生成方法，可以显著降低约束规模，提高SMT求解效率。

4.   案例分析

4.1   测试案例的生成

为了对基于可调度性排序的增量化TT调度表生成方法的性能进行评价，本文生成了一系列不同规模的测试案例。案例的网络拓扑选取雪花型拓扑^[7]。具体到本案例，如图 2所示，拓扑包含30个端系统，11个交换机，40条通信链路(80条数据流链路)；为了叙述方便，定义与同一交换机(非中心交换机)相连的所有端系统为一个“瓣”，图 2中所示拓扑共有10个“瓣”。网络中的每个端系统都发送相同数目的TT流量，并根据雪花型网络拓扑的结构特点，将TT流量区分为下述4种类型：

图  2  带有30个端系统的雪花型拓扑

Figure  2.  A snowflake topology with 30 end systems

下载: 全尺寸图片 幻灯片

1) 局域内多播。源端系统将TT流量发送给仅经过单跳的所有端系统(即源端系统所属“瓣”内的其余端系统)。

2) 局域外多播。源端系统将TT流量发送给全网中2~3个“瓣”(不包括源端系统所在“瓣”)内的所有端系统。

3) 局域内单播。目的端系统为源端系统所属“瓣”内的某个端系统(不包括源端系统)。

4) 局域外单播。目的端系统为源端系统所属“瓣”外的某个端系统。

每个端系统可以发送任一种类型的TT流量，规定测试案例中各类型TT流量的数目与每个端系统发送TT数的关系如表 1所示。表中四元组(n₁, n₂, n₃, n₄)分别为局域内多播、局域外多播、局域内单播、局域外单播的TT流量数目。

表  1  4种TT流量类型的数量分布

Table  1.  Quantity distribution of four kinds of TT traffic

每个端系统发送TT数	各类型TT流量数量
2	(0，0，1，1)
4	(0，0，2，2)
6	(0，0，3，3)
8	(1，1，3，3)
10	(1，1，4，4)
12	(1，1，5，5)
14	(2，2，5, 5)
16	(2，2，6，6)
18	(2，2，7，7)

下载: 导出CSV 

| 显示表格

TT消息的帧长在64~1 518 Byte中随机选取，周期取值为2^x3^yw ms，其中非负整数x, y∈{0, 1, 2}并等概率随机选取，基数w为正整数，全网带宽为100 Mbit/s。对于TT流量的调度约束参数设置，将min(d_hop)设为130 μs，max(d_hop)设为390 μs，端到端延迟上界max(d_latency)设为1 ms，应用层约束最小间隔δ设为50 μs。对于TTE网络中的同步开销，PCF帧长64 Byte，集成周期取值10 ms。

增量化调度表求解的步长Δ取值为6^[14]。整个实验运行在Intel i5 3.20 GHz CPU的主机(4 GB内存)。

4.2   案例结果

原始的SMT调度表生成方法^[5]没有考虑无冲突约束的缩减。图 3对比了无冲突约束规模缩减前后，不同测试案例规模(每个端系统发送TT数)下的增量化TT调度表生成所需时间；其中，TT流量的周期基数w∈{1, 5}。可以看出，经过无冲突约束规模缩减后，调度表求解时间得到大幅降低。这是因为，F_{TT_curr}与F_{TT_succ}集合间无冲突约束的生成方法使用干涉时间作为已调度流量集合整体对待调度流量的联合约束，代替了传统的两两TT流量的无冲突约束生成方法(式(3)和式(4)同时成立)，从而大规模缩减约束数量，提高了调度表求解效率。

图  3  无冲突约束规模缩减前后运行时间对比

Figure  3.  Comparison of running time before and after contention-free constraints reduction

下载: 全尺寸图片 幻灯片

为了评价不同TT流量排序方法下增量化TT调度表求解的性能，测试选取4种排序方法，分别是：随机排序(即不考虑可调度性)、周期升序(相当于可调度难度降序)，基于SPU值计算的流量可调度难度降序排序(即3.3节步骤1~步骤7的方法，简称“SPU降序”)，以及基于SPU值计算的流量可调度难度升序排序(简称“SPU升序”)。其中，“SPU升序”的排序方法是将3.3节步骤4中每次寻找SPU值最小的流量改为寻找SPU值最大的流量。

TT流量的周期基数w∈{1, 5, 7}，使实验结果进一步展示非调和周期参数下^[15]的调度性能。图 4给出了3种流量排序方法下，增量化TT调度表求解的回溯次数(3.1节步骤7的执行次数)对比；表 2为增量化调度表生成的运行时间对比。对于长期不停机的情况，增量化调度表求解设有时间上限，若超过该时间值仍没结束，则返回“无法判定”，本文设定时间上限为20 000 s。

图  4  不同流量排序方法下的增量化求解回溯次数

Figure  4.  Backtracking times of incremental scheduling method under different traffic ranking methods

下载: 全尺寸图片 幻灯片

表  2  不同流量排序方法下的运行时间

Table  2.  Running time under different traffic ranking methods

s
排序方法	每个端系统发送TT数
	6	8	10	12	14	16
SPU升序	3	17 259	7 530	—	—	—
随机排序	27	1 951	914	—	—	—
周期升序	9	22	38	256	2 716	3 609
SPU降序	10	21	41	44	78	662

下载: 导出CSV 

| 显示表格

综合图 4、表 2可以看出，随机排序由于没有考虑流量的可调度性因素，增量化求解过程的回溯次数明显高于按可调度难度降序排序的2种方法(周期升序和SPU降序)，进而导致调度表生成所需的运行时间也大幅增加；而且，随着案例规模的增大，会出现“无法判定”的情况。对于周期升序和SPU降序，当案例规模不大时，增量化求解性能接近；而当网络中的TT流量规模较大时，本文提出的排序方法在增量化求解的回溯次数、运行时间方面，都明显低于周期升序；原因在于：TT流量的可调度性不仅取决于流量的周期大小，正如第2节所述，还与TT的帧长、不同TT间周期的最大公约数等因素有关；而本文的方法通过SPU值的计算，综合考虑进了这些影响可调度性的因素，排序结果更能反应流量的可调度难度的高低。

“SPU升序”是为了印证“SPU降序”的合理性而设置的对照组。从结果可以看出，它的增量化求解回溯次数和运行时间都明显高于可调度难度降序，甚至高于随机排序；这是因为它使流量按照可调度难度升序排列并依次接受调度，增量化求解的回溯主要发生在流量排序序列的后部，一旦开始回溯，可能会需要回溯多次直至在3.1节步骤5中得到“满足”的判断，才能继续执行3.1节步骤6新增流量子集进行调度。

5.   结论

1) 本文提出了一种可用于TTE网络的基于可调度性排序的增量化时间触发调度表生成方法。

2) 在增量化调度表生成中，通过干涉时间的计算对无冲突约束规模进行缩减，可以大幅降低运行时间。

3) 案例研究表明，在网络中TT流量规模较大时，本文方法可以在一定程度上避免随机选取流量进行增量化调度时长期不停机导致的“无法判定”的情况，并且在增量化求解的回溯次数和运行时间方面均低于其他排序方法。