基于自适应双冗余的TTE调度方法及性能分析

工程科学学报，第41卷，第3期：393-400,2019年3月 Chinese Journal of Engineering,Vol.41,No.3:393-400,March 2019 DOI:10.13374/j.issn2095-9389.2019.03.013:http://journals.ustb.edu.cn 基于自适应双冗余的TTE调度方法及性能分析 汪 清”，滕立平”，崔鑫”，王阔”，王娴四，李文健) 1)天津大学电气自动化与信息工程学院，天津3000722)天津津航计算技术研究所，天津300308 ☒通倍作者，E-mail:2017234342@ju.edu.cm 摘要针对TTE(time-triggered Ethernet,TTE)网络对业务安全性与对业务实时性要求高的问题，提出了一种自适应双冗余 的网络结构，设计冗余报文的时间标签，自适应恢复传输，并设计了TTE网络中的混合流量(TT(time-triggered)流，RC(rate- constrained)流，BE(best-effort)流)调度规划方法，根据报文的重要性，发送端自适应的对网络报文进行分类，其中，TT信总双 网备份传输，RC、BE信息在双网分散传输.此外，基于确定性网络分析方法，推导了自适应双冗余调度方法下RC流的闭式延 迟界，并仿真验证了在极限网络、确定网络以及排队论仿真模型下所提方法减小网络延迟的效果，满足TTE网络在保障业务 安全性的情况下对业务实时性的要求. 关键词自适应双冗余：时间触发以太网：调度规划：RC延迟：性能界 分类号V247.2:TP393.0 TTE scheduling method based on adaptive dual redundancy and performance analysis WANG Qing,TENG Li-ping),CUI Xin),WANG Kuo),WANG Xian,LI Wenjian2) 1)School of Electrical and Information Engineering,Tianjin University,Tianjin 300072,China 2)Tianjin Jinhang Computing Technology Research Institute,Tianjin 300308,China Corresponding author,E-mail:2017234342@tju.edu.cn ABSTRACT Time-triggered Ethernet (TTE)is a new high-speed,real-time and fault-tolerant communications technology that com- bines high real-time services and traditional best-effort services.TTE is highly valuable in the application of transmission technology in the aerospace field.To ensure the security requirements of important information,the TTE network adopts a dual redundant network structure.Traditional links execute switching operation at the occurrence of failure,and the physical link switching causes some over- head and delays.When using dual-network transmission,the protocol is complicated,and the discard windows discard redundant pack- ets,which will also cause the increase of network delay.In this paper,an adaptive dual redundant network structure was proposed. This structure did not only meet the real-time performance requirements of the TTE network services,but also met the security require- ments of the TTE network service.Time labels for redundant messages were designed in this structure,and using time labels could re- store transmissions adaptively.A scheduling scheme of mixed traffic-time-triggered (TT)traffic,rate-constrained (RC)traffic,and best-effort (BE)traffic-in TTE network was designed.Based on the importance of the packet,the sender adaptively classified the network packet.Among the mixed traffic scheduling transmission,the TT traffic through the terminal redundancy was processed and backed ups,and it was transmitted in dual networks.RC and BE traffics were not important information:therefore,they did not need backup:they were transmitted dispersedly in dual networks.In addition,based on deterministic network analysis method,the closed delay bound of RC traffic under adaptive double redundant scheduling method was deduced.Furthermore,several simulation result un- der extreme network,determined network,and queuing theory simulation model show that the scheduling method based on adaptive du- al redundancy can reduce the network delay.This design does not only satisfy the security requirements of the TTE network,but also meets the real-time requirements of the service. 收稿日期：201801-26 基金项目：国家高技术研究发展计划资助项目(2015AA01A706):民用航天预研基金资助项目([2016]1299)

工程科学学报，第 41 卷，第 3 期: 393--400，2019 年 3 月 Chinese Journal of Engineering，Vol． 41，No． 3: 393--400，March 2019 DOI: 10． 13374 /j． issn2095--9389． 2019． 03． 013; http: / /journals． ustb． edu． cn 基于自适应双冗余的 TTE 调度方法及性能分析 汪 清1) ，滕立平1) ，崔 鑫1) ，王 阔1) ，王 娴1) ，李文健2) 1) 天津大学电气自动化与信息工程学院，天津 300072 2) 天津津航计算技术研究所，天津 300308 通信作者，E-mail: 2017234342@ tju． edu． cn 摘 要 针对 TTE( time-triggered Ethernet，TTE) 网络对业务安全性与对业务实时性要求高的问题，提出了一种自适应双冗余 的网络结构，设计冗余报文的时间标签，自适应恢复传输，并设计了 TTE 网络中的混合流量( TT( time-triggered) 流，ＲC( rate￾constrained) 流，BE( best-effort) 流) 调度规划方法，根据报文的重要性，发送端自适应的对网络报文进行分类，其中，TT 信息双 网备份传输，ＲC、BE 信息在双网分散传输． 此外，基于确定性网络分析方法，推导了自适应双冗余调度方法下 ＲC 流的闭式延 迟界，并仿真验证了在极限网络、确定网络以及排队论仿真模型下所提方法减小网络延迟的效果，满足 TTE 网络在保障业务 安全性的情况下对业务实时性的要求． 关键词 自适应双冗余; 时间触发以太网; 调度规划; ＲC 延迟; 性能界 分类号 V247. 2; TP393. 0 收稿日期: 2018--01--26 基金项目: 国家高技术研究发展计划资助项目( 2015AA01A706) ; 民用航天预研基金资助项目( ［2016］1299) TTE scheduling method based on adaptive dual redundancy and performance analysis WANG Qing1) ，TENG Li-ping1) ，CUI Xin1) ，WANG Kuo1) ，WANG Xian1)  ，LI Wen-jian2) 1) School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China 2) Tianjin Jinhang Computing Technology Ｒesearch Institute，Tianjin 300308，China Corresponding author，E-mail: 2017234342@ tju． edu． cn ABSTＲACT Time-triggered Ethernet ( TTE) is a new high-speed，real-time and fault-tolerant communications technology that com￾bines high real-time services and traditional best-effort services． TTE is highly valuable in the application of transmission technology in the aerospace field． To ensure the security requirements of important information，the TTE network adopts a dual redundant network structure． Traditional links execute switching operation at the occurrence of failure，and the physical link switching causes some over￾head and delays． When using dual-network transmission，the protocol is complicated，and the discard windows discard redundant pack￾ets，which will also cause the increase of network delay． In this paper，an adaptive dual redundant network structure was proposed． This structure did not only meet the real-time performance requirements of the TTE network services，but also met the security require￾ments of the TTE network service． Time labels for redundant messages were designed in this structure，and using time labels could re￾store transmissions adaptively． A scheduling scheme of mixed traffic—time-triggered ( TT) traffic，rate-constrained ( ＲC) traffic，and best-effort ( BE) traffic—in TTE network was designed． Based on the importance of the packet，the sender adaptively classified the network packet． Among the mixed traffic scheduling transmission，the TT traffic through the terminal redundancy was processed and backed ups，and it was transmitted in dual networks． ＲC and BE traffics were not important information; therefore，they did not need backup; they were transmitted dispersedly in dual networks． In addition，based on deterministic network analysis method，the closed delay bound of ＲC traffic under adaptive double redundant scheduling method was deduced． Furthermore，several simulation result un￾der extreme network，determined network，and queuing theory simulation model show that the scheduling method based on adaptive du￾al redundancy can reduce the network delay． This design does not only satisfy the security requirements of the TTE network，but also meets the real-time requirements of the service．

·394· 工程科学学报，第41卷，第3期 KEY WORDS adaptive dual redundant structure;time-triggered Ethernet:scheduling scheme:delay of RC traffic:performance bound 时间触发以太网利用同步控制器SM(synchro- 节点i 节点 nization master),同步客户端SC(synchronization cli- 应用层 应用层 ent),压缩控制器CM(compression master)三种基础 设施保障整个网络的时间同步.合理的时间规 冗余处理 冗余处理 划以及时刻调度表的设计，使TTE网络中的不同信 1通道 B通道 通道 B通道 物理层物理层 物理层 物理层 息流合理传输，减少延迟，避免链路争抢以及冲突下 重要信息在时间窗的碰撞丢失.目前国内外的研究 集中在TTE(time-triggered Ethernet)网络的调度设 A网 计.文献4]中使用Tabu搜索离线设计TT(time- triggered)调度表.文献5]提出一种TT转换成TT- ○B网 RC(rate-constrained),的调度策略，保障TT信息不会 图1冗余至节点结构图 因时间窗碰撞而丢失.文献[6]将混合流量分区调 Fig.1 Network node redundancy 度，介绍了离线与动态生成周期调度表的方法.文 (RC)流量，尽力传(BE(best-effort))流量4-.TT 献]提出用先验调度与后验稀释对周期调度表进 流、RC流、BE流传输遵循的调度规则不同，优先级 行分区设计的方法.时间触发以太网对混合流量进 也不同. 行合理调度，实现不同任务流的无冲突复合，避免数 在冗余至节点的以太网结构中，实现自适应的 据帧对链路的争抢，保证通信任务的实时性与准确 双冗余网络的方法如下： 性。该网络广泛应用于航天领域，提高航天以太网 (1)重要TT流信息在以太网报文数据区设计 的信息准确性与实时性8-0 报文的时间标签，经过终端冗余处理，采用冗余传输 当网络发生故障时，传统的冗余链路切换会造 机制，AB两个通道同时复制，双通道发送相同的TT 成一定的开销与延迟.文献11-12]提出了热切换 流，双网实现双冗余备份，保证一条通道或者交换机 的双冗余结构，网络终端设备通过两条链路与网络 出现故障，重要TT流信息不丢失. 相连，其中一条用于工作，另一条用于备份，当前工 (2)终端对网络中的报文根据实时性、可靠性 作链路断开后，切换到备用链路上进行网络通信 和响应时间需求的不同，将报文分成重要报文和次 传统的冗余链路切换时间较长，开销大，难以满足航 要报文，对于重要报文双冗余传输，次要报文经过终 天领域应用要求.基于PRP协议，两个节点同时在 端分类，采用双通道分散传输的报文调度方法进行 两个链路上传输数据，虽然无链路切换时间和故障 调度. 恢复时间，但是这种方法协议复杂，增加了网络报文 (3)接收端利用时间标签，采用时间优先法处 数量，丢弃算法丢弃冗余报文，使用丢弃窗口也会带 理冗余报文.当发生故障时，可以自适应的实现具 来网络延迟) 有零故障恢复时间的信息传输，提高系统的实时性 因此，本文拟设计自适应双冗余结构，并对TE TTE自适应双冗余网络通过重要信息(TT)的 网络中的混合流量进行合理调度，提高网络可用资 时间标签，实现网络故障时，可以自适应的零故障恢 源利用率，降低网络延迟，进一步保证时间触发以太 复时间的信息传输，根据时间标签处理冗余报文，提 网的实时性 高系统的实时性，无需网络故障冗余链路切换以及 丢弃窗口对网络延迟造成的影响，同时，自适应的判 1基于自适应双冗余结构的TT卫调度方法 断网络报文信息重要性并进行分类，针对不同报文 1.1自适应双冗余网络设计 采取不同的信息调度方式，次要报文在网络状态良 本文首先设计了一种冗余至节点的双以太网结 好时在双网分散传输，有效降低了网络的通信负荷， 构，如图1所示.每个节点配备了两个完全独立的 提高网络带宽利用率 网络接口，构成了A、B两个独立以太网物理通道. 1.2TTE流量混合调度原则 TTE网络采用混合流量传输模式，传输流量按 混合调度模式的TTE周期调度表设计如图2 照时间关键特性分为时间触发(TT)流量，速率受限 所示，若干个基本周期(basic cycle,,BC)组成一个

工程科学学报，第 41 卷，第 3 期 KEY WOＲDS adaptive dual redundant structure; time-triggered Ethernet; scheduling scheme; delay of ＲC traffic; performance bound 时间触发以太网利用同步控制器 SM ( synchro￾nization master) ，同步客户端 SC ( synchronization cli￾ent) ，压缩控制器 CM ( compression master) 三种基础 设施保障整个网络的时间同步［1--3］． 合理的时间规 划以及时刻调度表的设计，使 TTE 网络中的不同信 息流合理传输，减少延迟，避免链路争抢以及冲突下 重要信息在时间窗的碰撞丢失． 目前国内外的研究 集中在 TTE( time-triggered Ethernet) 网络的调度设 计． 文献［4］中使用 Tabu 搜索离线设计 TT( time￾triggered) 调度表． 文献［5］提出一种 TT 转换成 TT-- ＲC( rate-constrained) 的调度策略，保障 TT 信息不会 因时间窗碰撞而丢失． 文献［6］将混合流量分区调 度，介绍了离线与动态生成周期调度表的方法． 文 献［7］提出用先验调度与后验稀释对周期调度表进 行分区设计的方法． 时间触发以太网对混合流量进 行合理调度，实现不同任务流的无冲突复合，避免数 据帧对链路的争抢，保证通信任务的实时性与准确 性． 该网络广泛应用于航天领域，提高航天以太网 的信息准确性与实时性［8--10］． 当网络发生故障时，传统的冗余链路切换会造 成一定的开销与延迟． 文献［11--12］提出了热切换 的双冗余结构，网络终端设备通过两条链路与网络 相连，其中一条用于工作，另一条用于备份，当前工 作链路断开后，切换到备用链路上进行网络通信． 传统的冗余链路切换时间较长，开销大，难以满足航 天领域应用要求． 基于 PＲP 协议，两个节点同时在 两个链路上传输数据，虽然无链路切换时间和故障 恢复时间，但是这种方法协议复杂，增加了网络报文 数量，丢弃算法丢弃冗余报文，使用丢弃窗口也会带 来网络延迟［13］． 因此，本文拟设计自适应双冗余结构，并对 TTE 网络中的混合流量进行合理调度，提高网络可用资 源利用率，降低网络延迟，进一步保证时间触发以太 网的实时性． 1 基于自适应双冗余结构的 TTE 调度方法 1. 1 自适应双冗余网络设计 本文首先设计了一种冗余至节点的双以太网结 构，如图 1 所示． 每个节点配备了两个完全独立的 网络接口，构成了 A、B 两个独立以太网物理通道． TTE 网络采用混合流量传输模式，传输流量按 照时间关键特性分为时间触发( TT) 流量，速率受限 图 1 冗余至节点结构图 Fig． 1 Network node redundancy ( ＲC) 流量，尽力传( BE( best-effort) ) 流量［14--15］． TT 流、ＲC 流、BE 流传输遵循的调度规则不同，优先级 也不同． 在冗余至节点的以太网结构中，实现自适应的 双冗余网络的方法如下: ( 1) 重要 TT 流信息在以太网报文数据区设计 报文的时间标签，经过终端冗余处理，采用冗余传输 机制，AB 两个通道同时复制，双通道发送相同的 TT 流，双网实现双冗余备份，保证一条通道或者交换机 出现故障，重要 TT 流信息不丢失． ( 2) 终端对网络中的报文根据实时性、可靠性 和响应时间需求的不同，将报文分成重要报文和次 要报文，对于重要报文双冗余传输，次要报文经过终 端分类，采用双通道分散传输的报文调度方法进行 调度． ( 3) 接收端利用时间标签，采用时间优先法处 理冗余报文． 当发生故障时，可以自适应的实现具 有零故障恢复时间的信息传输，提高系统的实时性． TTE 自适应双冗余网络通过重要信息( TT) 的 时间标签，实现网络故障时，可以自适应的零故障恢 复时间的信息传输，根据时间标签处理冗余报文，提 高系统的实时性，无需网络故障冗余链路切换以及 丢弃窗口对网络延迟造成的影响，同时，自适应的判 断网络报文信息重要性并进行分类，针对不同报文 采取不同的信息调度方式，次要报文在网络状态良 好时在双网分散传输，有效降低了网络的通信负荷， 提高网络带宽利用率． 1. 2 TTE 流量混合调度原则 混合调度模式的 TTE 周期调度表设计如图 2 所示，若干个基本周期( basic cycle，BC) 组成一个 · 493 ·

汪清等：基于自适应双冗余的TTE调度方法及性能分析 ·395· TT的矩阵周期(matrix cycle,MC).基本周期是所 序.接收顺序约束如表2所示. 有TT流周期的最大公约数，矩阵周期是所有TT流 表1发送端发送任务表 周期的最小公倍数因.周期调度表从纵向来看，是 Table 1 Task table sent by transmitter ports 并列的n个基本周期，依次首尾相连，n个基本周期 发送端 接收端 帧长 周期/ms 的总时间是矩阵周期的时间长度.从横向上看，每 A 2 个基本周期都是由前半部分的TT帧与后半部分的 X D 1 1 RC+BE帧组成的. A E 4 基本周期0 B C 1 2 T BE+RC B D 2 基本周期1 B E 1 1 TT BE+RC 基本周期2 表2接收顺序约束表 TT BE+RC Table 2 Receiver port constraint table 基本周期3 第一个接收的 第二个接收的 TT BE+RC 接收端 TT信息发送端 TT信总发送端 图2周期调度示意图 C B A Fig.2 Periodic scheduling diagram D A 根据发送任务表与接收端的接收先后条件，对 所有TT任务进行复合表的生成.生成时间调度表 根据已知的A、B两个发送端的发送任务情况， 需要满足如下几个原则： 接收端接收情况以及周期调度表的生成规则，对有 (1)左端紧缩原则，尽量将T帧放在左边时间 两个集群的任务表生成无冲突复合表，如图4所示. 段，T帧占用的越小，用于传输其他信息的空间就 根据发送任务表中TT帧的周期长度，得出基本周 越大； 期BC为1ms,矩阵周期MC为4ms.按照不同的顺 (2)周期为2"ms相同的不同TT任务满足在周 序排列，剩余的可用空间大小不同，对生成各种表格 期调度表上按照2m-1-1纵向间隔排列： 的剩余空闲区域进行比较，使用剩余空间最大的表 (3)根据复合表分配各端口周期调度表，以保 即为最优周期调度表.交换机S1与SS1所接收的 证TT流在交换机中无冲突复合 TT流都将在时钟同步的前提下按照复合表无冲突 1.3TT流离线周期调度表设计 用于分析调度表生成方法的网络拓扑如图3所 复合. 根据无冲突复合表，提取相同的发送端的TT 示，两个发送终端A和B,两个TTE网络交换机S1 帧任务时间段，形成发送端的调度周期表.发送端 和SS1,三个接收终端C、D和E. A与发送端B的周期调度表分别如图5和图6所 发送端A、B的TT流发送任务表如表1所示，3 示.按照该发送端周期调度表，在保证TTE网络全 个TT流，分别发往不同的目的终端. 局时钟同步的前提下，可实现在交换机内无冲突复 在已知发送端的发送任务的前提下，还需要确 合，在预定时间段内处理信息，避免相同时间窗信息 定接收端C、D和E接收不同发送端TT流的先后顺 因碰撞而丢失. 1.4TTE自适应网络混合流量调度设计 TT流按照周期调度、左端紧缩原则生成TT流 的周期调度表，RC、BE流按照混合调度原则，在每 个基本周期TT流发送完的空闲区域发送，同时RC 流具有比BE流更高的优先级，优先在空闲区域发 SS1 送RC流，随后发送BE流. 终端对网络中的报文根据实时性、可靠性和 响应时间需求的不同，将报文分成重要报文和次 图3网络拓扑示例 要报文，对于重要报文(TT)双冗余备份传输，次要 Fig.3 Network topology example 报文(RC、BE)经过终端分类，采用双冗余分散传

汪 清等: 基于自适应双冗余的 TTE 调度方法及性能分析 TT 的矩阵周期( matrix cycle，MC) ． 基本周期是所 有 TT 流周期的最大公约数，矩阵周期是所有 TT 流 周期的最小公倍数［6］． 周期调度表从纵向来看，是 并列的 n 个基本周期，依次首尾相连，n 个基本周期 的总时间是矩阵周期的时间长度． 从横向上看，每 个基本周期都是由前半部分的 TT 帧与后半部分的 ＲC + BE 帧组成的． 图 2 周期调度示意图 Fig． 2 Periodic scheduling diagram 根据发送任务表与接收端的接收先后条件，对 所有 TT 任务进行复合表的生成． 生成时间调度表 需要满足如下几个原则: ( 1) 左端紧缩原则，尽量将 TT 帧放在左边时间 段，TT 帧占用的越小，用于传输其他信息的空间就 越大; ( 2) 周期为 2m ms 相同的不同 TT 任务满足在周 期调度表上按照 2m － 1 － 1 纵向间隔排列; ( 3) 根据复合表分配各端口周期调度表，以保 证 TT 流在交换机中无冲突复合． 图 3 网络拓扑示例 Fig． 3 Network topology example 1. 3 TT 流离线周期调度表设计 用于分析调度表生成方法的网络拓扑如图 3 所 示，两个发送终端 A 和 B，两个 TTE 网络交换机 S1 和 SS1，三个接收终端 C、D 和 E． 发送端 A、B 的 TT 流发送任务表如表 1 所示，3 个 TT 流，分别发往不同的目的终端． 在已知发送端的发送任务的前提下，还需要确 定接收端 C、D 和 E 接收不同发送端 TT 流的先后顺 序． 接收顺序约束如表 2 所示． 表 1 发送端发送任务表 Table 1 Task table sent by transmitter ports 发送端 接收端 帧长 周期/ms A C 2 2 A D 1 1 A E 1 4 B C 1 2 B D 1 2 B E 1 1 表 2 接收顺序约束表 Table 2 Ｒeceiver port constraint table 接收端 第一个接收的 TT 信息发送端 第二个接收的 TT 信息发送端 C B A D A B E A B 根据已知的 A、B 两个发送端的发送任务情况， 接收端接收情况以及周期调度表的生成规则，对有 两个集群的任务表生成无冲突复合表，如图 4 所示． 根据发送任务表中 TT 帧的周期长度，得出基本周 期 BC 为 1 ms，矩阵周期 MC 为 4 ms． 按照不同的顺 序排列，剩余的可用空间大小不同，对生成各种表格 的剩余空闲区域进行比较，使用剩余空间最大的表 即为最优周期调度表． 交换机 S1 与 SS1 所接收的 TT 流都将在时钟同步的前提下按照复合表无冲突 复合． 根据无冲突复合表，提取相同的发送端的 TT 帧任务时间段，形成发送端的调度周期表． 发送端 A 与发送端 B 的周期调度表分别如图 5 和图 6 所 示． 按照该发送端周期调度表，在保证 TTE 网络全 局时钟同步的前提下，可实现在交换机内无冲突复 合，在预定时间段内处理信息，避免相同时间窗信息 因碰撞而丢失． 1. 4 TTE 自适应网络混合流量调度设计 TT 流按照周期调度、左端紧缩原则生成 TT 流 的周期调度表，ＲC、BE 流按照混合调度原则，在每 个基本周期 TT 流发送完的空闲区域发送，同时 ＲC 流具有比 BE 流更高的优先级，优先在空闲区域发 送 ＲC 流，随后发送 BE 流． 终端对网络中的报文根据实时性、可靠性和 响应时间需求的不同，将报文分成重要报文和次 要报文，对于重要报文( TT) 双冗余备份传输，次要 报文( ＲC、BE) 经过终端分类，采用双冗余分散传 · 593 ·

·396 工程科学学报，第41卷，第3期 TT RC+BE TT流 A通道 A网 TT调度+ TT流 冗余备份 RCI+BEI A-D A-E B-E B-D B-C TT流 A-D Free B-E A-C B通道 B网 A-D Free B-E B-D B-C /RC1流，BE1流 TT调度+ 元余分散 RC2+BE2 RC流，BE流 A-D Free B-E RC2流，BE2流 A-C 图7节点混合流量调度示意图 图4无冲突复合表 Fig.7 Node mixed traffic scheduling Fig.4 No conflict compound table 定延迟数据相加，即可得到系统延迟 A-D A-E Free Free Free 实际网络仿真是在确定网络拓扑情况下，RC流 的发送目的端不再采取极端发送的方式，在此非极 A-D Free Free A-C 限情况下，根据实际源端以及节点处的RC流排队 数量情况计算延迟. A-D Fre Free Free Free 对于网络中由发送端发送的所有流都经一个交 换机到达同一目的端的极限情况，本文采用确定性 A-D Free Free A-C 延迟上界分析法，通过计算某条消息流在发送终端 图5发送端A调度表 及经过的每一个交换机上的最坏情况来进行递归延 Fig.5 Transmitter port A schedule table 迟估算闭，分别对非双冗余网络拓扑与自适应双冗 余网络的最大延迟界进行闭式推导. Free Free B-E B-D B-C 2.1单级自适应双冗余网络延迟界 假设单级非自适应双冗余网络有n个发送端， Free B-E Free 2n个交换机，n个接收端，一个发送端在2n个交换 机中任选其中一个进行连接.每个发送端发送m个 Free Free B-E B-D B-C RC信息流.接收端可接收多个交换机的转发信息. 由同一发送端发往任一交换机最多有m个RC流 Free B-E Free 在接收端，极限情况下，所有交换机转发的RC流目 图6发送端B调度表 的端相同，则该终端接收到的RC流数量为nm个. Fig.6 Transmitter port B schedule table 在发送过程中，受到最大带宽分配间隔的限 制89.在一个基本周期中，发送完所有需发送TT 输，在发送端对分类好的报文按照混合调度的原 流后，再多发送一个RC流即造成堵塞，在这种情况 则进行周期调度表设计，各节点通道按照各自的 下，一个基本周期内的延迟为 周期调度表进行发送.混合流量调度的节点示意 h=LTT +SRC-max /C (1) 图如图7所示 式中，lm为一个基本周期内配置的TT流发送长度， 2TTE网络极限情况延迟界理论分析 C为链路物理速率，SRcm表示每个RC流的最大帧 长度，大小取[64,1518]字节. 网络延迟性能分析是分析网络实时性的重要工 从而，在非自适应双冗余网络结构中，极限情况 具，包括极限的延迟界分析、排队论模型以及实际网 下源端的延迟上界为Pm： 络拓扑仿真等. 排队论模型是将排队服务理论应用在网络 数据处理的过程中.在时间触发以太网中，源端和 Dc,=H()= .-L RC+ 交换机节点处需要对数据进行排队服务处理，排队 的等待时间即是某一信息流在该节点处的排队延 迟，将节点处的排队延迟与传输延迟、技术延迟等固

工程科学学报，第 41 卷，第 3 期 图 4 无冲突复合表 Fig． 4 No conflict compound table 图 5 发送端 A 调度表 Fig． 5 Transmitter port A schedule table 图 6 发送端 B 调度表 Fig． 6 Transmitter port B schedule table 输，在发送端对分类好的报文按照混合调度的原 则进行周期调度表设计，各节点通道按照各自的 周期调度表进行发送． 混合流量调度的节点示意 图如图 7 所示． 2 TTE 网络极限情况延迟界理论分析 网络延迟性能分析是分析网络实时性的重要工 具，包括极限的延迟界分析、排队论模型以及实际网 络拓扑仿真等． 排队论模型［16］是将排队服务理论应用在网络 数据处理的过程中． 在时间触发以太网中，源端和 交换机节点处需要对数据进行排队服务处理，排队 的等待时间即是某一信息流在该节点处的排队延 迟，将节点处的排队延迟与传输延迟、技术延迟等固 图 7 节点混合流量调度示意图 Fig． 7 Node mixed traffic scheduling 定延迟数据相加，即可得到系统延迟． 实际网络仿真是在确定网络拓扑情况下，ＲC 流 的发送目的端不再采取极端发送的方式，在此非极 限情况下，根据实际源端以及节点处的 ＲC 流排队 数量情况计算延迟． 对于网络中由发送端发送的所有流都经一个交 换机到达同一目的端的极限情况，本文采用确定性 延迟上界分析法，通过计算某条消息流在发送终端 及经过的每一个交换机上的最坏情况来进行递归延 迟估算［17］，分别对非双冗余网络拓扑与自适应双冗 余网络的最大延迟界进行闭式推导． 2. 1 单级自适应双冗余网络延迟界 假设单级非自适应双冗余网络有 n 个发送端， 2n 个交换机，n 个接收端，一个发送端在 2n 个交换 机中任选其中一个进行连接． 每个发送端发送 m 个 ＲC 信息流． 接收端可接收多个交换机的转发信息． 由同一发送端发往任一交换机最多有 m 个 ＲC 流． 在接收端，极限情况下，所有交换机转发的 ＲC 流目 的端相同，则该终端接收到的 ＲC 流数量为 nm 个． 在发送过程中，受到最大带宽分配间隔的限 制［18--19］． 在一个基本周期中，发送完所有需发送 TT 流后，再多发送一个 ＲC 流即造成堵塞，在这种情况 下，一个基本周期内的延迟为 l1 = lTT + SＲC·max /C ( 1) 式中，lTT为一个基本周期内配置的 TT 流发送长度， C 为链路物理速率，SＲCi ·max表示每个 ＲC 流的最大帧 长度，大小取［64，1518］字节． 从而，在非自适应双冗余网络结构中，极限情况 下源端的延迟上界为［20］: D0 ＲCi = H( α0 ＲC，β0 ＲC ) = ∑ m i = 1 SＲC·i max C( lBC － l1 ) lBC + l1 [ + ∑ m i = 1 SＲC·i max C － ∑ m i = 1 SＲCi ·max C( lBC － l1 ) ( lBC － l1 ] ) ( 2) · 693 ·

汪清等：基于自适应双冗余的TTE调度方法及性能分析 ·397· 式中，任一RC流的到达曲线表示为aRc,服务曲线 可以看出，采用自适应冗余方案，RC信息流的 可表示为Bc,lc为基本周期中TT所在占的时间长 延迟界小于非自适应双冗余的延迟界.自适应双冗 度.每一节点的RC流最大延迟均为该节点处到达 余方案下的调度方法可减小网络延迟 曲线与服务曲线的水平距离. 2.2多级自适应双冗余网络延迟界 极限情况下一节点的延迟上界为： 对于多级网络，该网络中从不同源端到达不同 DRc,≤H(RCBRC）= 目的端的经过的交换机用k:表示，其中，最多经过 的交换机数为 +BAGRC =maxk; (6) C(lBc - 可假设极端情况下所有的流都走同一条物理链 路，经链路中相同的交换机，并经过网络中最多交换 SRCD RCa 机k到达同一目的端，对单级网络情况下的延迟进 台BAGRC, 行推广.非自适应双冗余结构下，源端的RC流延迟 C 为式(2)，由于是多级链路，链路中的交换机数量不 SRCi'max 罗 SRCDRC 定，则在每一个交换机节点处，都需要聚合所有发送 BAGRC (Igc-h) 3) 端发送的RC流，则节点处的延迟为式(3)，整个网 C(Iuc -1) 络链路上的延迟，为每个节点处的延迟之和 式中，BAGC表示RC需要满足的最大带宽分配间隔 D=DRe+∑De (7) 单级自适应双冗余的网络拓扑中冗余网络交换 机为2n个，在自适应双冗余拓扑中，由于发送端双 式中，Dc,为多级拓扑下每个交换机节点处的延迟， 网发送RC流，则在两个通道中平分m个RC流，在 见式(3). 极限情况下，同一接收端最多接收到的RC流数量 自适应双冗余结构下，每个节点对所有流分开 为mn/2.m个信息流，现经过双通道处理，分散进 发送，每一节点的延迟仍为服务曲线与到达曲线的 行发送，每个通道分别发送m/2或者(m+1)2或 水平距离，流的数量减半，其中，Dc,为多级拓扑下 者(m-1)/2,这取决于该数量m的奇偶性，这里以 每个交换机节点处的延迟，见式(5). m为偶数作进一步的性能分析. 基于时间触发以太网的双冗余结构，文献21] 在自适应双冗余网络结构中，极限情况下源端 提出了基于模拟退火算法的容错拓扑选择方案，该 的延迟上界为 方法提出，在冗余网络中，网络的双网备份，造成了 物理链路、网络成本的增加，可以采取一定概率下删 Dc,=H(,Bc) 减交换机与物理链路，降低网络成本，同时保障网络 C(-1) 1+ 冗余性质和延迟符合限制.在优化的双冗余拓扑 下，由于删减交换机造成网络结构的改变，对应的双 C(1c-l,) ua-6 (4 冗余拓扑最长路径下的交换机数（即节点需要叠加 的最大延迟数目)也会发生改变 极限情况下一节点的延迟上界为： k'=(1-Ps)·k (8) DRc≤H(aRc,BRc)= 式中，P、为一个随机概率的最大值，表示在概率条 件下，冗余拓扑中的交换机以此概率被删减，极限情 台BAGRC 况下，多跳网络以此概率减小跳数.在该优化的冗 C(lgc - BC+ 余拓扑情况下，仍考虑极限情况，所有源端流沿最长 跳数路径冗余分散发动，计算延迟方法相同，叠加次 数由某最长跳数路径上的交换机数决定，结果不同， BAGRC 上界公式任然适用. C 3仿真验证 台BAGRC, 通过RC流理论延迟界的推导公式，在单级/多 C (luc -1) 级，非自适应冗余/自适应冗余调度策略的网络拓扑

汪 清等: 基于自适应双冗余的 TTE 调度方法及性能分析 式中，任一 ＲC 流的到达曲线表示为 α1 ＲC，服务曲线 可表示为 β1 ＲC，lBC为基本周期中 TT 所在占的时间长 度． 每一节点的 ＲC 流最大延迟均为该节点处到达 曲线与服务曲线的水平距离． 极限情况下一节点的延迟上界为: D1 ＲCi ≤H( α1 ＲC，β1 ＲC ) = ∑ mn i = 1 SＲCi ·max + ∑ mn i = 1 SＲC·i max BAGＲCi DＲCi C( lBC － l1 ) lBC [ + ∑ mn i = 1 SＲCi ·max + ∑ mn i = 1 SＲCi ·max BAGＲCi DＲCi C － ∑ mn i = 1 SＲCi ·max + ∑ mn i = 1 SＲCi ·max BAGＲCi DＲCi C( lBC － l1 ) ( lBC － l1 ] ) ( 3) 式中，BAGＲCi 表示 ＲC 需要满足的最大带宽分配间隔． 单级自适应双冗余的网络拓扑中冗余网络交换 机为 2n 个，在自适应双冗余拓扑中，由于发送端双 网发送 ＲC 流，则在两个通道中平分 m 个 ＲC 流，在 极限情况下，同一接收端最多接收到的 ＲC 流数量 为 mn /2． m 个信息流，现经过双通道处理，分散进 行发送，每个通道分别发送 m /2 或者( m + 1) /2 或 者( m － 1) /2，这取决于该数量 m 的奇偶性，这里以 m 为偶数作进一步的性能分析． 在自适应双冗余网络结构中，极限情况下源端 的延迟上界为 D0 ＲCi = H( α0 ＲC，β0 ＲC ) = ∑ m/2 i = 1 SＲCi ·max C( lBC － l1 ) lBC + l1 [ + ∑ m/2 i = 1 SＲCi ． max C － ∑ m/2 i = 1 SＲCi ·max C( lBC － l1 ) ( lBC － l1 ] ) ( 4) 极限情况下一节点的延迟上界为: D1 ＲCi ≤H( α1 ＲC，β1 ＲC ) = ∑ mn/2 i = 1 SＲCi ·max + ∑ mn/2 i = 1 SＲC·i max BAGＲCi DＲCi C( lBC － l1 ) lBC [ + ∑ mn/2 i = 1 SＲCi ·max + ∑ mn/2 i = 1 SＲCi ·max BAGＲCi DＲCi C － ∑ mn/2 i = 1 SＲCi ·max + ∑ mn/2 i = 1 SＲCi ·max BAGＲCi DＲCi C( lBC － l1 ) ( lBC － l1 ] ) ( 5) 可以看出，采用自适应冗余方案，ＲC 信息流的 延迟界小于非自适应双冗余的延迟界． 自适应双冗 余方案下的调度方法可减小网络延迟． 2. 2 多级自适应双冗余网络延迟界 对于多级网络，该网络中从不同源端到达不同 目的端的经过的交换机用 ki 表示，其中，最多经过 的交换机数为 k = maxki ( 6) 可假设极端情况下所有的流都走同一条物理链 路，经链路中相同的交换机，并经过网络中最多交换 机 k 到达同一目的端，对单级网络情况下的延迟进 行推广． 非自适应双冗余结构下，源端的 ＲC 流延迟 为式( 2) ，由于是多级链路，链路中的交换机数量不 定，则在每一个交换机节点处，都需要聚合所有发送 端发送的 ＲC 流，则节点处的延迟为式( 3) ，整个网 络链路上的延迟，为每个节点处的延迟之和． D = D0 ＲCi + ∑ k j = 1 Dj ＲCi ( 7) 式中，Dj ＲCi 为多级拓扑下每个交换机节点处的延迟， 见式( 3) ． 自适应双冗余结构下，每个节点对所有流分开 发送，每一节点的延迟仍为服务曲线与到达曲线的 水平距离，流的数量减半，其中，Dj ＲCi 为多级拓扑下 每个交换机节点处的延迟，见式( 5) ． 基于时间触发以太网的双冗余结构，文献［21］ 提出了基于模拟退火算法的容错拓扑选择方案，该 方法提出，在冗余网络中，网络的双网备份，造成了 物理链路、网络成本的增加，可以采取一定概率下删 减交换机与物理链路，降低网络成本，同时保障网络 冗余性质和延迟符合限制． 在优化的双冗余拓扑 下，由于删减交换机造成网络结构的改变，对应的双 冗余拓扑最长路径下的交换机数( 即节点需要叠加 的最大延迟数目) 也会发生改变． k' = ( 1 － PNS )·k ( 8) 式中，PNS为一个随机概率的最大值，表示在概率条 件下，冗余拓扑中的交换机以此概率被删减，极限情 况下，多跳网络以此概率减小跳数． 在该优化的冗 余拓扑情况下，仍考虑极限情况，所有源端流沿最长 跳数路径冗余分散发动，计算延迟方法相同，叠加次 数由某最长跳数路径上的交换机数决定，结果不同， 上界公式任然适用． 3 仿真验证 通过 ＲC 流理论延迟界的推导公式，在单级/多 级，非自适应冗余/自适应冗余调度策略的网络拓扑 · 793 ·