时间触发光纤通道调度算法确定性分析

谭小虎，王 勇，褚文奎，刘 安

空军工程大学 航空航天工程学院，西安 710038

1 引言

FC（Fibre Channel，光纤通道）凭借在延迟率、错位率以及传输速率等方面的优势，成为新型航电系统的首选协议[1]，可以满足航电网络在实时性、可靠性等方面的要求。为支持FC协议在航电系统中的应用，FC协议标准开发委员会专门组织建立一个分委会，该分委会制定出针对航空电子环境下的协议草案，即FC-AE（光纤通道航空电子环境），其内容就是扩展FC协议，同时发展以光纤通道为基本的航电增强型专用系统[2]。FC-AEASM（光纤通道-航空电子环境-匿名消息）作为FC-AE协议的子集，就是针对航电系统应用而提供的上层协议，用于航电系统各设备间安全和低延迟的通信[3]。但是该协议中却没有给出终端系统中消息间的调度算法，对于大部分终端设备采用先来先服务（FCFS）的数据发送控制算法使得消息端到端延迟具有很大的不确定性，造成对系统的分析困难。

目前国内对光纤通道方面的研究主要集中在网络传输的可靠性、通信系统拓扑结构以及上层协议的转换方面。文献[4-6]以网络任务模型为基础，建立了可靠性模型，同时针对光纤通道三种拓扑结构，推导出可靠性的表达式。文献[7]对于FC在航空电子环境中的体系结构进行了论述。文献[8]对光纤通道的特性进行了介绍，同时对典型的几种网络和总线进行了分析比较。针对网络中消息的发送控制算法，文献[9]提出了基于实时排队论的调度算法，它借助延时率可以反映系统实时性。

基于以上分析，提出时间触发调度算法，通过静态规划消息的调度表，通过全局时钟来触发每个消息的发送，使得网络中所有消息都拥有较强的时间确定性。

2 数据结构模型设计

航空电子系统中存在很多类型消息，不同消息对时间延迟的要求也就不同。类似警报和传感器的消息就是具有硬实时要求的紧急消息，具有严格的时延要求，而对于文件发送等消息就是非紧急消息，时延要求相对较低[10]。所以在时间触发FC终端接口中将具有高时延要求的紧急数据设置为时间触发消息，其他非紧急消息设置为事件触发消息。根据FC-AE-ASM消息帧格式，数据传输过程中将消息帧帧头中保留的8～11 Byte作为消息类型的标识，设定用0110表示该消息为时间触发消息，其余除了0000表示形式外代表该消息为事件触发消息，改进的消息帧格式如图1所示。对于时间触发消息采用时间触发的调度形式进行发送，而对于事件触发消息则采用传统的先来先服务策略进行发送。

图1 FC-AE-ASM消息格式

3 时间触发调度算法设计

调度算法主要涉及对基本周期和矩阵周期的确定。对于矩阵周期，首先根据消息种类规划初始系统矩阵MC0，然后对MC0进行优化，得到最终系统矩阵MC。

（1）对基本周期（BC）和矩阵周期（MC）的持续时间MCT进行确定

首先对于周期消息按照周期递增的顺序排序，得到消息序列 T=[T1,T2,…,TM]，其中 Ti+1≥Ti，(i∈[1,M-1])。取输入周期消息的最小周期T1作为基本周期BC。规定MC的持续时间MCT是输入周期信号周期的最小公倍数或者最小公倍数的整数倍来保证满足传输每一个消息的平均周期[11]，从式（1）的计算中可得矩阵周期（MC）的行数R。

式（3）中n是为防止非周期型号对周期信号造成干扰加在两个周期间的隔离窗口[12]，IDLE是防止传输过程中上个基本周期未传完消息对下一个周期影响所加入的保护间隔。式（4）中Ti是各个通信节点的消息发送周期，T1是所有消息的最小传输周期。如果a＜νmax，那么生成矩阵的列数为[a]+3，其中[a]用来传输TT消息，一列传输ET消息，一列为周期消息和非周期之间的隔离窗口，一列为两个基本周期之间的保护间隔。如果a＞νmax，则说明链路传输速率不够，需要增加传输速率来完成消息的发送。

（3）生成待优化的初始矩阵MC0

根据消息集合I，在满足发送周期的情况下将消息按列依次装入R列矩阵中，得到待优化矩阵MC0。

（4）初始矩阵的优化

采用价值函数P对初始矩阵进行优化，由此得到最终的优化矩阵MC。

式（2）表示消息集合，其中ki(1≤i≤R)表示第i个消息的实例个数。

（2）确定一个基本周期（BC）可以传输的消息个数ν

根据总线的传输波特率B和周期消息比特数Num以及消息的传输时间Lt等参数，由式（3）可以得出一个基本周期中可以传输消息的最大个数；再者根据式（4）可以得出基本周期中传输的平均消息个数：

其中P表示在矩阵周期中将消息集合中每个消息传输完成实际所需时间，其达到最小值也就得到最优值。表示第i个消息的第 j次消息实例的发送时刻；R、C、Dc分别表示矩阵周期的行数、列数和时间窗的宽度。

4 基于FCFS服务策略的调度算法及确定性分析

面对光纤通道的高速性，现如今针对终端节点的调度算法普遍采用FCFS的服务策略，其算法复杂度低，实现条件简便，可以很好满足基于事件触发的通信系统。但是消息的不可控性，导致引入了时间抖动，抖动的可变性要求采用网络演算的方式来计算网络的端到端延时，需要说明的是，最后计算的端到端延时都是最坏条件下的上限值[13]。

4.1 网络演算理论

在运用网络演算理论解决问题的过程中，采用聚集函数R(t)对进入网络的流量进行特征化的描述，该函数表示在时间[ ]

0,t内流入网络的数据流的比特数。在借助网络演算来计算网络端到端的延时时，需要介绍数据流的到达曲线和服务曲线两个重要概念。

定义1[13]如果存在一个定义于t∈[0,+∞)上的广义增函数α，只有在满足对于任意s≤t时，才有R(t)-R(s)≤α(t-s)，那么数据流R的到达曲线就是函数α。

定义2[13]在系统S中，假设输入数据流和输出数据流的聚集函数分别为R和R*，同时存在一个广义增函数 β，满足 β(0)=0，使得R*≥R⊗β，那么就称函数 β为系统S的服务曲线。

引理1[14]假设在某个系统中，数据流的到达曲线为α，服务曲线为β，则进入系统的数据流在系统中的延迟上界满足关系：

如图2所示。

图2 延迟上界计算

4.2 FC网络在FCFS服务策略下确定性分析

采用M端口的FC网络交换机，每个端口的数据流到达曲线为αi，i=1,2,…,M，根据端口到达流量的可加性得交换机需处理的数据聚合流为：

用C表示交换机的输出物理链路带宽，同时信用值假设为无穷大。假设所有数据中最大的数据帧长为lmax，每个端口的数据连续传输速率为ri，突发数据最大尺寸为bi，根据FCFS服务策略可得数据的延迟上界为：

对式（8）进行证明：对交换机在忙时段[t1,t2]内进行分析，其中t1表示忙时段的开始时间，可以得到：

考虑到忙期的结束时间点t2，交换机可能处于空闲或者处理 t-τ(0＜τ＜)时刻到达的未处理完的数

200据帧两种状态，如果这时处理的数据帧是聚合流中最长的，就有：

根据式（8）和式（9）可以得到：

表示R*≥R⊗β，再根据定义2就可以得到输入数据流的到达曲线为：

如果采用漏桶整形器在交换机的端口对到达数据流进行流量整形，那么端口的数据流到达曲线就可以表示为：

正在无聊之际，在县城车站上班的表哥打电话给我，要我周日去找他玩，我高兴得跳了起来。虽说表哥比我大了十七岁，在一起的时间也少，可我们却玩得来。

式（13）中ri表示i端口数据连续传输速率，bi表示到达数据流的最大突发长度。再根据到达数据流的可加性，则所有端口数据流的到达曲线为：

再根据引理1可得数据的延迟上界为：

由此得证。

根据定理1可知，交换机在服务策略FCFS模式下，所有数据流的延迟上界都同为584 μs。

5 时间触发调度算法确定性分析

基于时间触发的FC终端接口和普通FC终端接口的硬件结构和网络拓扑相同，所以在对时间触发FC交换式网络进行性能分析时建立和普通光纤通道相同的交换式网络，利用消息的端到端延时来分析网络的确定性。

5.1 时间触发光纤通道网络时间确定性分析

航电系统是一个对消息实时性确定性要求很高的系统，消息的可靠传输关系到网络的确定性，消息的传输实时性又关系到航电系统的正常运行。对FC网络实时性和确定性进行分析，采用端到端延时作为网络性能的评价指标。所谓端到端时延表示消息在端系统的发送时延、链路的传输时延和交换机的转发时延的累计和[15]，其各个时延部分的组成如图3所示。

图3 时延各部分组成

图3 中t1表示上层应用的消息分装为FC-AE-ASM数据帧所用的时间，系统性能的好坏决定所用时间的长短，一般来说该时间可以忽略。t2表示数据帧在发送队列中等待的时间，主要由队列长度和调度策略决定，是影响网络实时性的因素，通过消息到达调度表规划发送时间和消息到达队列时间之差可得。t3和t5表示消息在链路传输时间，该值为固定值。t4表示消息经过交换机的转发延时，考虑到在时间触发FC网络中交换机也要配置相应调度表，所以该时间也是一个确定值，通过数据帧在交换机调度表中规划的调度时刻和消息到达交换机时间之差求得。

5.2 时间触发光纤通道网络建模和确定性分析

鉴于时间触发FC网络和普通FC网络结构相同，所以对时间触发FC网络的建模采取普通FC的交换式网络结构。网络结构如图4所示。网络中包括一个交换机和10个终端系统。各个终端节点的消息设置如表1所示，链路延迟取1 μs。

图4 TTFC网络结构

表1 消息配置信息

根据消息周期生成的各个消息的调度时刻如图5所示。

在交换机中每条时间触发消息按照调度表在各自的调度时刻进行发送，交换机速率取1 Gb/s。用tmn表示消息调度时间，其中m表示源节点，n表示目的节点。取每种消息最早调度时刻作为其延迟计算的标准。由调度表可知各个消息的调度时间为：

相应的：

图5 消息的调度时刻

依次类推：

统计各个消息的调度时间如表2所示。

表2 调度时刻计算结果 μs

则各个消息的最小延迟时间为：

依次类推：

各个消息延迟时间如表3所示。

表3 消息延迟时间计算结果 μs

与前文结果相比，时间触发服务策略明显降低了承载关键紧急消息的高优先级数据帧的延迟，理论计算结果表明时间触发调度算法对网络实时性确实有一定的改善。

6 光纤通道调度算法仿真及分析

根据第4章、第5章对光纤通道中的典型调度算法进行的建模分析，本章借助OPNET10.0仿真工具，根据图4交换式网络结构，对时间触发终端节点和交换机进行建模，交换机物理链路速率设置为1 Gb/s，每个端口设置最大允许突发数据长度为10倍数据帧长，交换机提供FCFS和时间触发两种服务策略，仿真分析两种服务策略下拥有相同网络流量类型的消息延迟与理论计算的差距，消息配置信息采用表1所设置类型。

（1）在时间触发服务策略下消息延迟分析

由表4可以看出，采用时间触发调度策略理论计算值和实际仿真结果非常接近，表示具有很好的时间确定性。

表4 时间触发策略下消息端到端延迟 μs

（2）在FCFS服务策略下消息延迟分析

由表5可以看出，在FCFS服务策略下基于网络演算的理论计算值和仿真结果具有较大的差距，时间确定性较差。

表5 FCFS策略下消息端到端延迟 μs

7 结束语

本文根据FC-AE-ASM以及时间触发协议规范，针对现有调度算法缺少时间确定性问题，设计实现了一种时间触发调度算法，从理论和仿真两方面对算法性能进行了分析，仿真结果表明时间触发调度算法拥有很好的时间确定性，对航电系统分析具有很好的指导意义。