基于随机网络演算的TTE网络时延分析

赵露茜， 李峭， 林晚晴， 熊华钢

北京航空航天大学 电子信息工程学院， 北京　100083



基于随机网络演算的TTE网络时延分析

赵露茜， 李峭*， 林晚晴， 熊华钢

北京航空航天大学 电子信息工程学院， 北京100083

时间触发以太网(TTE)是一种新颖的混合型时间触发和事件触发的通信网络，通过引入时间触发(TT)流量，增强了航空电子全双工(AFDX)交换式以太网的确定性。虽然TT流量具有完全的时间确定性，但是与AFDX中虚拟链路(VL)兼容的速率约束(RC)流量仍具有一定非确定性。传统用于AFDX网络实时性能分析的方法在考虑TT流量固定分区调度时隙的影响下已不再适用，为了保障RC流量的实时性能，分别提出了基于确定性网络演算和随机网络演算两种延迟分析模型。在确定性网络演算下，通过构造TT流量的聚合到达曲线和RC流量的服务曲线以得到RC的确定性延迟上界；在随机网络演算下，通过切诺夫(Chernoff)边界定理构造RC流量的两状态伯努利分布模型，得到概率保证下的延迟上界。对比实验结果表明：随机网络演算模型可以有效减小确定性网络演算模型对RC流量性能分析的悲观性，同时从一定程度上验证了两种理论分析模型的正确性。

航空电子； 时间触发以太网； 性能分析； 网络演算； 随机网络演算； 延迟上界

时间触发以太网[1-3](TTE)是一种改进时间关键性和安全关键性的应用于航空航天领域的网络，它通过离线设计时间触发(TT)流量的调度时隙，部分消除了航空电子全双工(AFDX)交换式以太网[4]的非确定性。

TTE网络为了支持不同实时性和安全性需求的应用，将流量划分为3类[5]，TT流量、速率约束(RC)流量和尽力传(BE)流量。TT流量用于对延迟、抖动等确定性要求高的应用，RC流量用于对确定性要求稍弱一些的应用，它与AFDX中虚拟链路(VL)的传输模式兼容，BE流量为传统以太网通信方式，具有最低优先级且无需服务质量(QoS)保证。

目前国内外对于TTE网络研究主要集中在网络的配置优化以及TT调度表的离线设计。Tamas-Selicean等[6-7]在考虑最小化RC延迟的情况下，综合优化TTE网络的虚拟链路帧分配、路由分配等配置方法；文献[8]针对分区调度表提出了一种基于时间窗检测的TT与RC流量的转换策略。此外，Steiner[9-10]提出一种基于可满足性模理论(SMT)解析器的TT调度表生成方法，通过给定的约束集求得满足条件的可行解；Tamas-Selicean和Steiner[11-12]基于Tabu搜索离线设计了TT调度表，并在TT调度的前提条件下对RC流量时序关系进行分析。文献[13]引入一种分区的调度机制，将每个基本周期划分为专门用于发送TT流量和RC/BE流量的两段。

目前对于RC流量确定性分析的研究还比较少，由于TT帧固定调度时隙的影响，传统用于AFDX网络实时性能分析的方法[14-18]已不再适用。文献[19]中针对TT流量的孔隙调度模型，提出了确定性网络演算对RC流量的分析方法，然而由于最坏情况为小概率事件，上述分析方法下的最坏延迟估计具有较大的悲观性。

本文针对TT流量的分区调度模型，提出基于确定性网络演算的RC性能分析模型，同时为了改善确定性网络演算带来的悲观性，本文还基于随机网络演算对RC流量进行分析建模，分别得到RC流量的确定性上界和概率保证下的上界。实验对两种模型的估计结果进行了比较，并对两种建模方法进行了仿真验证。

1　TTE网络分区调度模型

TT调度模型并不由TTE协议提供，而是灵活地提供给设计者。文献[13]提出一种分区模式的TT调度表，如图1所示。TT流量的传输在时域上独立于RC和BE流量，同时在带宽上隔离RC和BE流量，RC流量获得配置带宽，BE流量利用空闲带宽尽最大可能传送数据帧。

图1　分区时间触发(TT)调度表Fig.1　Partitioned time-triggered (TT) schedule

每个节点(终端/交换机)端口有一张分区的TT调度表，图2为一张对应于实验网络拓扑交换机S1端口1的调度表示意图。由于各TT流量的数据帧严格按照周期性(2的幂次方)从终端发送，各调度表的时间轴以矩阵周期(Matrix Cycle, MC)为单位周期性的循环，一个矩阵周期的长度lMC定义为网络中所有TT流量周期的最小公倍数:

(1)

此外，一个矩阵周期又划分为若干个基本周期(Basic Cycle, BC)，基本周期的长度lBC定义为网络中所有TT流量的最小可能周期:

(2)

那么一个矩阵周期包括nBC个基本周期:

nBC=lMC/lBC

(3)

每个基本周期被划分为两段，前一段专门用于发送TT数据帧，后一段专门用于发送RC和BE数据帧。根据左端紧缩原则，将TT帧均匀间隔的纵向分布放置在nBC个基本周期内。

图2　基本周期和矩阵周期Fig.2　Basic cycle and matrix cycle

TT与RC流量的传输模式[5]分为3种：抢占(Preemption)模式、及时阻断(Timely Block)模式和洗牌(Shuffling)模式，如图 3所示。抢占模式表示若RC帧在传输的过程中遇到TT帧，则RC帧被终止传送，直至TT帧传输完毕并再次有空闲时段时，RC帧被继续发送。及时阻断模式表示RC帧在传输前需要预判距离下一个相邻的TT帧之间是否有足够的空闲时段供其完整传输，若没有RC帧将被延迟传送。洗牌模式表示RC帧将推迟TT帧预先安排的传输时隙。考虑到及时阻断模式在TTE网络中应用更广泛，本文主要研究在这种传输模式下的网络性能。

图3　TT与速率约束(RC)流量的传输模式Fig.3　Transmission modes between TT and rate-constrained (RC) flow

2　基于确定性网络演算的RC延迟分析

2.1确定性网络演算

网络演算[20]是一种网络性能分析方法，可以用于计算网络流量的延迟上界。网络演算主要概念包括到达曲线、服务曲线、最小加代数下的卷积和反卷积运算。

(4)

(5)

式中：σ为最大突发度；ρ为流量平均速率上界。

(6)

(7)

(8)

2.2RC流量确定性延迟上界分析

在TTE网络中，RC流量与AFDX的虚拟链路相兼容，每条流量τRCi在源终端受到最大帧长SRCi，max以及两个相邻帧之间的最小帧间隔BAGRCi的约束。因此在源终端τRCi的到达曲线可以表示为

(9)

然而由于在当前节点端口排队的原因，τRCi的输出到达曲线即下一节点端口的输入到达曲线的突发度有所增加：

(10)

假设τRCi在沿其路径上的第h个节点端口中还有其他n-1条已知输入到达曲线的RC流量，它们的聚合到达曲线可以表示为

(11)

RC聚合流量的服务取决于链路物理速率C以及调度表的占空比，更具体来说取决于在一个基本周期内配置TT时段的长度lTT，以及由于及时阻断模式下造成最多一个RC帧长度的阻塞时延。在最坏情况下，一个基本周期内RC流量的延迟为

l1=lTT+SRC，max/C

(12)

(13)

(14)

图4　RC聚合流量的服务曲线Fig.4　Service curve of aggregate RC flows

图5　最大水平距离Fig.5　Maximum horizontal deviation

3　基于随机网络演算的RC延迟分析

3.1随机网络演算

虽然确定性网络演算给出RC流量的延迟上界，但是由于在考虑聚合流量的情况下，这种最坏情况发生的可能性非常小。Chang等[21]在2001年提出一种基于确定性流量和确定性服务的统计上界模型。

Chang的随机网络演算的流量模型需要满足以下条件：

1) τ1,τ2,…,τn为相互独立的流量。

2) τ1,τ2,…,τn为平稳的流量。

(15)

3.2RC流量概率性延迟上界分析

(16)

稳定性条件确保一定存在τ<∞，作为忙时段的上界：

(17)

(18)

(19)

引理1(切诺夫边界[22])一个随机变量X，对于任意常量x和所有θ≥0，都有

(20)

式中：EeθX称为随机变量X的矩量母函数[22]。

即

(21)

式中：Λ(θ)为累积量母函数，它是矩量母函数上界的自然对数。

(22)

式中：

(23)

证明：根据h节点端口积压式(17)和切诺夫边界引理(引理 1)，对于∀θ≥0有

(24)

式中：

那么

(25)

(26)

另外，根据端口RC聚合流量概率保证下的积压上界可以求得其概率保证下的延迟上界为

(27)

4　实验分析

图6　时间触发以太网(TTE)网络架构Fig.6　Time-triggered ethermet (TTE) network architecture

Table 1　Periods of TT flows　ms

表2　RC流量带宽分配间隔(BAGs)

基于VC++开发平台，首先实现了确定性网络演算对RC流量延迟上界估计的算法，再以其得到的各节点端口前的流量突发度和积压上界作为输入量，开发随机性网络演算对RC流量概率延迟估计的算法(保证概率为10-5)。由两种方法计算得到的各条RC流量的端到端延迟如图7 所示，图中横轴表示顺序排列的RC流量(RC1, RC2(e7), RC2(e8), RC3, …)；此外，表3给出部分RC流量延迟的数值结果。根据运行结果分析可知，在当前TTE网络配置下，随机网络演算在概率保证下对RC流量延迟上界的估计比确定性网络演算对RC流量延迟上界的估计减少了26.58%。在该算例中，随机网络演算在TTE网络中的应用减少了确定性网络演算的悲观性。

表3　部分RC流量延迟比较

除此之外，为了验证两种理论算法的正确性，通过仿真的方法对TTE网络中RC延迟进行统计，最大的仿真延迟结果如表3第4栏所示。从图7中可以清楚的看出，最大仿真延迟均未超过理论计算值，一方面，这是由于理论上界在极限情况下得到，在仿真情况下很难发生；另一方面，由于仿真结果小于或等于实际最坏延迟，因此从一定程度上验证了两种理论估计结果的正确性。

下面比较在不同TT流量占用率的情况下，随机网络演算对确定性网络演算的改进情况。假设RC流量条数和路径均不变，通过增加TT流量的条数来增大TT流量的带宽占用率。图8 给出了TT带宽占用率分别为6%、10%和20%的情况下，随机网络演算(保证概率为10-5)相对于确定性网络演算对RC延迟估计结果减小的比例。可以看出，随着TT流量占用率的增大，RC调度的随机因素随之降低，因而两种理论方法对于RC延迟的估算结果的差异性明显降低。

图7　RC流量延迟比较Fig.7　Latency comparison of RC flows

图8　不同TT占用率下两种理论方法的差异Fig.8　Difference between two theoretical methods under different TT occupancy rate

5　结　论

针对TTE交换网络，本文提出了两种基于分区调度策略下RC流量延迟的分析方法。

1) 确定性网络演算模型给出RC流量确定的延迟上界，然而具有较大的悲观性。随机网络演算模型给出概率保证下的RC流量的延迟上界，在一定程度上改善了这种悲观性。

2) 随着TT流量带宽占用率的增加，随机网络演算模型对确定性网络演算模型的悲观性优化随之降低。

3) 分区调度是其中一种TT调度策略，下一步，应将随机网络演算应用于基于孔隙调度策略下的TTE网络中RC流量的概率延迟上界分析。

[1]SAE. Time-triggered ethernet： AS6802[S]. Warrendale, PA: SAE International, 2011.

[2]KOPETZ H, GRUNSTEIDL G. The time-triggered ethernet (TTE) design[C]//8th IEEE International Symposium on Object Oriented Real-Time Distributed Computing. Piscataway, NJ: IEEE Press, 2005: 22-33.

[3]KOPETZ H. Real-time systems: Design principles for distributed embedded applications[M]. Berlin: Springer, 2011: 167-188.

[4]ARINC. ARINC Specification 664P7: Aircraft data network, Part 7: Avionics full-duplex switched Ethernet network[S]. New York: Aeronautical Radio Inc., 2009.

[5]STEINER W, BAUER G, HALL B, et al. TTEthernet dataflow concept[C]//8th IEEE International Symposium on Network Computing and Applications. Piscataway, NJ: IEEE Press, 2009: 319-322.

[6]TAMAS-SELICEAN D. Design of mixed-criticality applications on distributed real-time systems[D]. Denmark: Technical University of Denmark, 2014： 86-98.

[7]TAMAS-SELICEAN D, POP P, STEINER W. Design optimization of TTEthernet-based distributed real-time systems[J]. Real-Time Systems, 2015, 51(1): 1-35.

[8]易娟, 熊华钢, 何峰, 等. TTE网络流量转换策略及其延时性能保障调度算法研究[J]. 航空学报, 2014, 35(4): 1071-1078.

YI J, XIONG H G, HE F, et al. Research on traffic classes transformation strategy and real-time guarantee scheduling algorithm in TTEthernet[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(4): 1071-1078 (in Chinese).

[9]STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//IEEE 31st Real-Time Systems Symposium (RTSS). Piscataway, NJ: IEEE Press, 2010: 375-384.

[10]STEINER W. Synthesis of static communication schedules for mixed-criticality systems[C]//14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Work-shops. Piscataway, NJ: IEEE Press, 2011: 11-18.

[11]TAMAS-SELICEAN D, POP P, STEINER W. Synthesis of communication schedules for TTEthernet-based mixed-criticality systems[C]//Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hard-ware/Software Codesign and System Synthesis. New York: ACM Press, 2012: 473-482.

[12]TAMAS-SELICEAN D, POP P, STEINER W. Timing analysis of rate constrained traffic for the TTEthernet communication protocol[C]//Proceedings of the 18th IEEE International Symposium on Real-Time Distributed Computing. Piscataway, NJ: IEEE Press, 2015: 119-126.

[13]刘晚春, 李峭, 何峰, 等. 时间触发以太网同步及调度机制的研究[J]. 航空计算技术, 2011, 41(4): 122-127.

LIU W C, LI Q, HE F, et al. Research on time-triggered Ethernet synchronization and scheduling mechanism [J]. Aeronautical Computing Technique, 2011, 41(4): 122-127 (in Chinese).

[14]FRANCES F, FRABOUL C, GRIEU J. Using network calculus to optimize the AFDX network[C]//3rd European Congress ERTS Embedded Real-time Software. Toulouse, France: OATAO Press, 2006: 1-8.

[15]BOYER M. Half-modeling of shaping in FIFO net with network calculus[C]//18th International Conference on Real-Time and Network Systems, 2010: 59-68.

[16]SCHARBARG J L, RIDOUARD F, FRABOUL C. A probabilistic analysis of end-to-end delays on an AFDX avionic net-work[J]. IEEE Transactions on Industrial Informatics, 2009, 5(1): 28-49.

[17]RIDOUARD F, SCHARBARG J L, FRABOUL C. Probabilistic upper bounds for heterogeneous flows using a static priority queueing on an AFDX network[C]//IEEE International Conference on Emerging Technologies and Factory Automation. Piscataway, NJ: IEEE Press, 2008: 1220-1227.

[18]ADNAN M, SCHARBARG J L, ERMONT J, et al. Model for worst case delay analysis of an AFDX network using timed automata[C]//IEEE Conference on Emerging Technologies and Factory Automation. Piscataway, NJ: IEEE Press, 2010: 1-4.

[19]ZHAO L X, XIONG H G, ZHENG Z, et al. Improving worst case latency analysis for rate-constrained traffic in the time-triggered Ethernet network[J]. IEEE Communications Letters, 2014, 18(11): 1927-1930.

[20]LE BOUDEC J Y, THIRAN P. Network calculus: A theory of deterministic queuing systems for the internet [M]. Berlin: Springer, 2001: 3-59.

[21]CHANG C S, CHIU Y M, SONG W T. On the performance of multiplexing independent regulated inputs [C]//ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. New York: ACM Press, 2001: 184-193.

[22]FIDLER M. An end-to-end probabilistic network calculus with moment generating functions[C]//14th IEEE International Workshop on Quality of Service. Piscataway, NJ: IEEE Press, 2006: 261-270.

赵露茜女， 博士研究生。主要研究方向： 实时网络的性能分析方法。

E-mail: zhaoluxi@buaa.edu.cn

李峭男， 博士， 讲师。主要研究方向： 实时通信、 性能评价。

Tel.: 010-82338894

E-mail: avionics@buaa.edu.cn

林晚晴女， 硕士研究生。主要研究方向： 高速交换网络结构与调度算法。

E-mail: LWQ_1991@buaa.edu.cn

熊华钢男， 博士， 教授， 博士生导师。主要研究方向： 通信网络理论与技术、航空电子信息综合和超宽带通信。

E-mail: hgxiong@buaa.edu.cn

Stochastic network calculus for analysis of latency onTTEthernet network

ZHAO Luxi, LI Qiao*, LIN Wanqing, XIONG Huagang

School of Electronic and Information Engineering, Beihang University, Beijing100083, China

Time-triggered Ethernet (TTE) is a novel hybrid communication network with time-triggered and event-triggered messages. The determinacy of avionics full duplex (AFDX) switched Ethernet is improved by introducing the time-trigger (TT) flow. Even though TT flow has full time certainty, rate-constraint (RC) flow which is compatible with the virtual link (VL) in the AFDX network is still uncertain. Since the influence of fixed schedule slots of TT flow, traditional performance analysis methods used in the AFDX network are not suitable for the. In order to guarantee the real-time performance of RC flow, we propose two latency analysis models respectively based on the deterministic network calculus and stochastic network calculus. Under the deterministic network calculus, the latency upper bounds of RC flow are obtained by constructing the aggregate arrival curve of TT flow and service curve for RC flow. Under the stochastic network calculus, we compute the probabilistic upper bounds for RC flow by constructing two states Bernoulli distribution models for RC flow through Chernoff bound. Comparison results show that stochastic network calculus reduces the pessimism of deterministic network calculus on the performance analysis of RC flow. In addition, simulation results verify the correctness of two theoretical methods in some degree.

avionics; time-triggered Ethernet; performance analysis; network calculus; stochastic network calculus; latency upper bound

2015-07-08； Revised： 2015-09-06； Accepted： 2015-11-13； Published online： 2015-11-2314:29

s： National Natural Science Foundation of China (61301086)； the Fundamental Research Funds for the Central Universities (YWF-14-DZXY-018, YWF-14-DZXY-023)

. Tel.： 010-82338894E-mail: avionics@buaa.edu.cn

2015-07-08； 退修日期： 2015-09-06； 录用日期： 2015-11-13；

时间： 2015-11-2314:29

www.cnki.net/kcms/detail/11.1929.V.20151123.1429.006.html

国家自然科学基金 (61301086)； 中央高校基本科研业务费专项资金 (YWF-14-DZXY-018, YWF-14-DZXY-023)

.Tel.： 010-82338894E-mail: avionics@buaa.edu.cn

10.7527/S1000-6893.2015.0305

V247; TP393

A

1000-6893(2016)06-1953-09

引用格式： 赵露茜， 李峭， 林晚晴， 等． 基于随机网络演算的TTE网络时延分析[J]． 航空学报, 2016, 37(6): 1953-1962. ZHAO L X, LI Q, LIN W Q, et al. Stochastic network calculus for analysis of latency on TTEthernet network[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(6): 1953-1962.

http://hkxb.buaa.edu.cnhkxb@buaa.edu.cn

URL： www.cnki.net/kcms/detail/11.1929.V.20151123.1429.006.html