汪清等：基于自适应双冗余的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 ·