优先级驱动的泛化航电网络实时性能分析

2022-09-05于思凡何锋熊华钢

航空学报 2022年7期

于思凡，何锋，熊华钢

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

当前交换式网络利用空分交换结构，能够在一个网段同时进行多个消息并发处理，提高了整网吞吐量，能够满足新一代航空电子综合技术对通信网络的需求。应用于军用飞机F-35的光纤通道(Fibre Channel，FC)和民用飞机空客A380的航空电子全双工交换式以太网(Avionics Full Duplex Switched Ethernet，AFDX)都属于典型交换式网络。优先级作为一种调度机制广泛应用于交换式网络的实时通信调度中，用于满足不同重要程度的消息对实时性能的要求。为了保障消息的通信诉求，需要对交换式网络中不同优先级的消息进行实时性能评估。在交换式网络设计初期，网络具体参数未知时，同样有对不同优先级占比情况下的整网实时性能的预估需求，目的在于形成反馈机制，以指导机载网络的具体设计。

解析计算是一种对网络进行数学建模、计算得到端到端延迟上界的实时性能分析方法。消息端到端的最大延迟刻画了消息最难调度场景，通过解析计算获得的消息延迟上界与消息真实最坏延迟之间的差异性刻画了不同方法的计算悲观性。典型的解析计算方法包括网络演算、轨迹法、整体法等。其中网络演算基于最小加代数理论，以流量曲线和服务曲线为建模目标，通过分析流经节点的数据流在节点处积压的情况，实现整个网络的服务性能分析。轨迹法根据数据流既定路径轨迹，构造数据帧沿其传输路径上的最坏情况，从而实现端到端延迟分析。相比于网络演算，轨迹法不是针对每个节点的最坏情况，部分克服了网络演算中利用输出曲线突发度增大模拟数据帧到达存在的不确定性带来的悲观性。整体法通过对数据帧到达时延抖动的迭代计算实现数据帧在输出节点的最坏延迟分析，并通过对路径上各个节点的最坏延迟累加得到端到端延迟上界。在数据传输时，每个节点的最后延迟基本上不会达到，导致了整体法的悲观性。

网络演算易于理解与实现，已成为使用最普遍的解析计算方法，并发展出分组网络演算、偏置网络演算、实时网络演算、共轭网络演算等其他形式的变体。但网络演算方法依赖于网络拓扑和详细配置参数，无法在设计初期对网络实时性刻画，由此发展出泛化网络演算。与已有网络演算方法对具体网络实时性评价不同，泛化网络演算无需组网拓扑和流量具体配置参数，利用抽象出的组网特征参数对网络实时性能进行预估，进而形成反馈机制，用于指导网络具体设计。即使在未知网络拓扑和流量具体配置参数的情况下，泛化网络演算的算法有效性超过38%，具备网络实时性预估的能力。但目前泛化网络演算缺乏对不同优先级数据流实时性评价的能力。

为了在未知网络拓扑与消息详细配置参数的情况下，对采用优先级调度策略的交换式网络进行实时性能预估，本文提出优先级驱动的泛化网络演算，研究贡献在于：抽象出网络中端口发送高、低优先级数据流的最大带宽利用率两个特征参数分别对网络中高、低优先级数据流的分布进行抽象，进而对高、低优先级占比进行刻画与预估；基于抽象出的优先级调度策略交换式网络的组网特征参数，分别对高、低优先级数据流的服务曲线进行泛化，并分别得到高、低优先级数据流的端到端延迟上界；对高、低优先级延迟确界变化进行分析与对比，给出优先级占比推荐方案，用于指导优先级调度策略交换式航电网络的设计。

1 泛化网络演算

泛化网络演算无需组网拓扑和流量具体配置参数，利用抽象出的组网特征参数对网络实时性能进行预估。本节对交换式网络和最坏延迟分析进行总结，并对网络演算和泛化网络演算进行介绍。

1.1 交换式网络

为了满足新一代航空电子系统对综合化互连在带宽、实时性、可靠性等方面更高的性能要求，机载网络逐步发展为具有灵活性的交换式拓扑结构。交换式网络中利用空分交换结构，计算节点之间存在多条通信链路，节点之间的通信可以并发进行，大大提高了整网通信吞吐量。光纤通道和航空电子全双工交换式以太网作为典型交换式网络被新型机载互连系统所采用。由8个交换机和12个端系统组成的交换式网络如图1所示。

图1 交换式网络结构Fig.1 Switch-based network structure

考虑到机载网络实时性传输需求，应用于机载环境的交换式网络需要通过流量控制机制保障网络的实时性。例如AFDX网络的实时性主要体现在基于虚拟链路的调度、寻址、路由等过程中。AFDX网络中虚拟链路按照给定的带宽分配间隔(Bandwidth Allocation Interval，BAG)进行整形，使得每条虚拟链路都有规定的最大带宽，并提供了其端到端延迟上界可计算的基础，从而保障了数据流的实时性。AFDX网络中虚拟链路的流量整形过程如图2所示。

图2 AFDX网络虚拟链路流量整形机制Fig.2 Traffic shaping mechanism of virtual links in AFDX

1.2 最坏延迟分析

交换式网络的实时性指网络中通信任务的传输必须在指定的时间内完成，即消息的端到端延迟必须不能大于规定的截止期限。消息的端到端延迟为消息从源端系统到目的端系统传输时间的总和。消息的端到端延迟主要分为3个部分：物理链路上的传输延迟，消息帧从交换机输入端口发送到输出端口的时间(不包含消息在输出端口排队的时间)，消息在端系统或交换机输出端口等待排队调度的时间。

物理链路上的传输延迟取决于帧的传输时间，即消息帧长与物理链路传输带宽的比值。消息经过多条物理链路时，物理链路上的传输总延迟是单个帧传输延迟与经过物理链路数量的乘积。消息帧从交换机输入端口发送到输出端口的时间称为交换机固有技术时延，具有确定的上界。当消息经过多个交换机时，该部分传输延迟是交换机固有技术时延与经过交换机个数的乘积。消息在端系统或交换机输出端口等待排队调度的时间取决于消息输出排队的过程，具有高度不确定性，是本文研究的重点。

1.3 泛化网络演算

网络演算是一种基于最小加代数理论的端到端延迟上界分析方法。网络演算中定义了到达曲线和服务曲线，分别表示网络节点处到达数据流的上包络和网络节点对具有不同服务质量需求的数据流的最小服务能力。到达曲线与服务曲线之间的最大水平距离表示网络节点处数据流的最坏时间延迟，最大垂直距离表示网络节点处数据流的最大数据积压。对数据流传输路径上各节点处的最坏延迟求和，得到端到端延迟上界。

网络演算依据详细配置参数计算数据流延迟上界，但存在根据组网特征参数进行实时性评价的需求，用于指导网络设计。目前研究中存在对保证速率(Guaranteed Rate，GR)网络通过网络特征计算确定性端到端延迟上界的方法。该方法通过流量的最大跳数、带宽利用率、突发度等得到端到端延迟上界。对于AFDX和FC等交换式网络，由于虚拟链路的流整形或其他整形过程，不能保证每个流在输出端口按照给定的速率服务，这种方法并不适用，由此文献[20]提出泛化网络演算。与已有网络演算方法对具体网络实时性评价不同，泛化网络演算在未知组网拓扑和流量详细配置参数的情况下，依据网络规模、带宽利用率、数据比特流速率等组网特征参数，分别得到基本延迟上界和考虑分组的延迟上界，如图3所示。相比于网络演算，即使在数据帧长显著变化的情况下，2种延迟上界的有效性均超过38%，具备对网络实时性预估的能力，得到的结果可以指导网络设计。

图3 泛化网络演算Fig.3 Generalized network calculus

2 优先级驱动的泛化网络演算

优先级作为一种调度机制广泛应用于实时通信调度中，用于解决不同重要程度消息对实时传输的需求。例如现有AFDX交换机支持高、低2级优先级。目前泛化网络演算缺乏对不同优先级数据流实时性评价的能力。

为了实现优先级驱动的泛化性能分析，对采用优先级调度策略的交换式网络进行实时性预估，首先分析优先级调度机制，抽象出交换式网络优先级调度策略的特征参数，进而基于特征参数对源节点和交换机端口处对高、低优先级服务曲线进行泛化，之后在突发度包络函数的边界约束下对高、低优先级数据流在源节点和交换机处延迟的最坏情况进行建模，得到延迟上界，累加得到端到端延迟上界。

2.1 优先级调度机制

当消息端到端延迟不满足既定要求时，有以下3个解决方案：① 限制数据流的数量；② 增加额外的交换机或物理链路；③ 将数据流划分为高、低优先级，不满足要求的消息采用高优先级。由于应用的限制一般不能减少数据流的数量，增加额外的交换机或物理链路会增加网络成本，因此可以将数据流划分为高、低优先级以减少高优先级数据流延迟上界。由此可以看出，优先级调度机制在实时通信调度中广泛应用。

ARINC667 P7协议中规定的优先级调度算法为基于静态优先级的非抢占式队列调度(Static Priority Un-interrupt Scheduling, SPUS)。该算法规定：在数据流发送过程中，只要高优先级队列非空，高优先级数据流优先发送；但低优先级数据流正在发送时，高优先级数据流不能打断正在传输的低优先级数据流，必须等到发送完成后再进行发送。基于静态优先级的非抢占式队列调度如图4所示。

图4 基于静态优先级的非抢占式队列调度Fig.4 Static priority un-interrupt scheduling

2.2 服务曲线模型

在基于静态优先级的非抢占式队列调度策略中，高优先级数据流的传输受限于交换机端口的输出速率，同时高优先级数据流不能打断正在传输的低优先级数据流。因此在确定性网络演算中，端口port对高优先级数据流的服务曲线()为

(1)

由于交换机端口优先对高优先级数据流服务，因此低优先级数据流的传输受限于交换机端口的输出速率和交换机端口对高优先级数据流的服务。在确定性网络演算中，端口port对低优先级数据流的服务曲线()为

(2)

式中：为高优先级数据流集合；flow为经过端口port的任意数据流；为数据流flow的比特流速率；为数据流flow的突发度。

2.3 交换式网络特征参数

在交换式网络设计初期，只能依赖组网特征参数对网络实时性评价。本文抽象出物理链路速率,网络中数据帧长度上界,网络中数据流的比特速率,网络中端口发送高、低优先级数据流的最大带宽利用率、网络中数据流经过交换机跳数的最大值6个特征参数对网络进行刻画。参数具体含义如下：

：物理链路速率。可以不失一般性地假设网络中物理链路速率一致，例如网络中物理链路速率均为=100 Mbit/s。物理链路速率刻画网络中链路传输情况。

：网络中数据流的比特流速率。假设网络中数据流的比特流速率相等，均为。网络中数据流的比特流速率刻画网络中流量规模。

：网络中端口发送低优先级数据流的最大带宽利用率，即flow。其中：port,L为输出端口port发送低优先级数据流的最大带宽利用率。同样利用实现网络初期设计者对低优先级流量占比的刻画和预估。

2.4 高优先级数据流延迟上界分析

基于高低优先级流量占比的预估，可以在泛化网络演算角度下进行不同优先级流量的延迟分析。关键在于如何实施突发度包络函数约束下的不同优先级流量的约束。相对来说，高优先级流量的约束可以考虑低优先级的最大帧长的影响，但是低优先级的约束就需要将高优先级占比的整体情况进行考虑。

2.4.1 高优先级数据流在源节点处延迟

(3)

(4)

式中：port为源节点的输出端口；max,为数据流flow中数据帧的最大长度。

(5)

(6)

(7)

2.4.2 高优先级数据流在交换机处延迟

在交换机输出端口，高优先级数据流同样受限于端口的服务速率和对正在传输的低优先级数据帧的服务。因此在交换机输出端口，高优先级数据流的服务曲线()仍为

(8)

(9)

式中：port为第1个交换机输出端口。

(10)

(11)

(12)

为了得到统一的高优先级数据流延迟上界，对网络中高优先级数据流包络函数的上界进行定义。定义网络中高优先级数据流在第hop个节点处突发度的包络函数的上界为(hop)，则可以得出

(13)

(14)

(15)

(16)

(17)

(18)

根据计算得到的高优先级数据流在第个节点处的突发度表达式可以得到

(19)

由此可以解出(hop)表达式为

(20)

2.4.3 高优先级数据流端到端延迟

(21)

2.5 低优先级数据流延迟上界分析

对于低优先级，消息的传输受高优先级数据流的传输的约束。延迟上界分析的关键在于依据组网特征参数对低优先级数据流在源节点、交换机处服务曲线进行泛化，进而通过泛化网络演算理论得到低优先级数据流端到端延迟上界公式。

2.5.1 低优先级数据流在源节点处泛化服务曲线

(22)

2.5.2 低优先级数据流在交换机处泛化服务曲线

(23)

2.5.3 低优先级数据流端到端延迟

(24)

其中的表达式为

(25)

低优先级数据流突发度的包络函数()的表达式为

()=

(26)

3 算法验证

依据优先级驱动的泛化网络演算模型，以具备输入流量漏桶整形的交换式网络为例，对高、低优先级数据流端到端延迟上界随带宽利用率、比特流速率、网络中数据流经过交换机的最大跳数、高优先级占比的变化进行分析与对比，验证算法的正确性与合理性，并给出优先级占比分配推荐方案。

3.1 高优先级数据流延迟上界分析

选取交换式网络的典型参数，假设物理链路的传输速率为100 Mbit/s，网络中数据帧的最大长度为1 000 Bytes。当网络中数据流经过交换机的最大跳数为3时，高优先级数据流端到端延迟上界如图5所示。可以看出，当网络中端口发送高优先级数据流的最大带宽利用率一定时，数据流的比特流速率越大，网络中高优先级数据流的数目越少，在交换机输出端口排队造成的延迟越小，端到端延迟上界越小。当网络中数据流的比特流速率一定时，端口发送高优先级数据流的最大带宽利用率越大，网络中高优先级数据流的数目越多，在交换机输出端口排队造成的延迟越大，端到端延迟上界越大。

图5 不同高优先级数据流延迟上界μH随ρ变化曲线Fig.5 Gurve of μH changing with ρ under different upper bound delays for high-priority streams

当网络中数据流的比特流速率为0.5 Mbit/s 时，高优先级数据流延迟上界如图6所示。可以看出，当网络中端口发送高优先级数据流的最大带宽利用率相同时，高优先级数据流经过交换机的个数越多，端到端延迟上界越大，这与基本网络演算的结论一致。

图6 不同高优先级数据流延迟上界μH随h变化曲线Fig.6 Curve of μH changing with h under different upper bound delays for high-priority streams

3.2 低优先级数据流延迟上界分析

假设物理链路传输速率为100 Mbit/s，网络中数据帧的最大长度为1 000 Bytes，网络中端口发送高优先级数据流的最大带宽利用率为15%。当网络中数据流经过交换机的最大跳数为3时，低优先级数据流端到端延迟上界如图7所示。与高优先级数据流的分析相同，当网络中端口发送低优先级数据流的最大带宽利用率一定时，数据流比特流速率越大，低优先级数据流的端到端延迟上界越小。当网络中数据流的比特流速率一定时，端口发送低优先级数据流的最大带宽利用率越大，低优先级数据流端到端延迟上界越大。

图7 不同低优先级数据流延迟上界μL随ρ变化曲线Fig.7 Curve of μL changing wiht ρ under different upper bound delays for low-priority streams

当网络中数据流比特流速率为0.5 Mbit/s时，低优先级数据流端到端延迟上界如图8所示。同理，低优先级数据流经过交换机的个数越多，端到端延迟上界越大，与基本网络演算结论一致。

图8 不同低优先级数据流延迟μL随、h变化曲线Fig.8 Curve of μL changing with h under different upper bound for low-priority streams

3.3 高、低与不区分优先级数据流延迟上界对比

基于优先级驱动的泛化网络演算模型，分析当网络中端口最大带宽利用率之和一致时，高、低优先级数据流延迟上界变化趋势，能够对网络设计中分配高、低优先级数据流占比进行指导。同时与泛化网络演算得到的相同端口最大带宽利用率，但不区分优先级的延迟上界结果进行对比，验证算法的正确性与合理性。

与空客A380网络规模相似的网络中端口发送数据流的带宽利用率约为25%。设定网络中端口处发送高优先级数据流最大带宽利用率和低优先级数据流最大带宽利用率之和为定值0.25，即+=025，得出高、低优先级数据流端到端延迟上界随网络中端口处发送高优先级数据流的最大带宽利用率、数据流的比特流速率变化曲线如图9所示。

从图9中可以看出，对于高优先级数据流，网络中数据流的比特流速率一定时，网络中端口发送高优先级数据流的最大带宽利用率越高，网络中高优先级数据流越多，在交换机端口处排队造成的延迟越大，高优先级数据流的端到端延迟上界越大。除正在传输的低优先级数据帧外，低优先级数据流的传输不对高优先级数据流产生影响。

图9 高优先级、低优先级和不区分优先级数据流端到端延迟上界Fig.9 Upper bound on end-to-end delay of high priority, low priority and un-priority streams

对于低优先级数据流，网络中数据流的比特流速率一定时，低优先级数据流的延迟上界随着网络中端口处发送高优先级数据流的最大带宽利用率的增大先减小再增大。网络中端口处发送高优先级数据流的最大带宽利用率增大导致高优先级数据流对低优先级数据流延迟影响增大。同时网络中端口发送低优先级数据流的最大带宽利用率减小，导致网络中低优先级数据流数量减少，低优先级数据流间排队延迟减少。这2种影响相互平衡形成图9所示结果，可以看出虽然比特流速率的不同会导致低优先级延迟转折点的稍许变化，但基本上围绕在高优先级流量占整个流量的40%左右。

因此，图9所示的高、低优先级数据流端到端延迟上界曲线展示了网络中高、低优先级数据流的数量对延迟上界的影响。当网络中端口处发送高、低优先级数据流最大带宽利用率之和+及数据流的比特流速率一定时，可以选择图中圆点位置(相同数据流的比特流速率，低优先级数据流延迟最小)处的高优先级数据流最大带宽利用率。在保证高优先级数据流延迟上界的基础上，可以最大程度降低低优先级数据流延迟上界。在与空客A380网络规模相似的机载网络中，选择高优先级数据流占比40%左右，低优先级数据流占比60%左右，以实现高低优先级流量端到端传输延迟的最佳平衡。因此基于优先级驱动的泛化网络演算，给出了优先级占比推荐方案。

对于不区分优先级网络中的数据流，当网络中端口发送数据流的最大带宽利用率同样为25%时，依据文献[20]中的泛化网络演算模型，得到延迟上界随网络中数据流的比特流速率变化的图像如图9中不区分优先级曲线所示。由高优先级与不区分优先级曲线对比可以看出，设置高、低优先级降低了高优先级数据流的延迟上界，且高优先级数据流占比越低，降低效果越显著。相比于不区分优先级，低优先级延迟先减小后增大，这是增大导致端口对低优先级服务速率减少与减小导致低优先级数据流数目减少相平衡的结果。同时通过图9可发现，当高优先级数据流的占比为0时，低优先级与不区分优先级的延迟上界结果一致。对于优先级驱动的泛化网络演算模型，当为0时，低优先级延迟上界计算模型退化为文献[20]中的泛化网络演算模型，因此延迟上界结果一致，验证了算法的正确性与合理性。

4 案例分析

基于随机生成的实验案例，对比采用优先级驱动的泛化网络演算和具备详细参数的网络演算得到的端到端延迟上界结果，从而分析优先级驱动的泛化网络演算的算法性能。通过2种算法对比高、低优先级数据流延迟上界，用于具体指导网络设计。

案例采用12个端系统和4个交换机，每个交换机与3个端系统以及另外3个交换机通过100 Mbit/s 的物理链路相连，拓扑结构如图10所示。案例中采用120条数据流，数据流通过虚拟链路承载，数据流的配置信息随机生成。数据流的源节点与目的节点从12个端系统中随机选取(源节点与目的节点不相同且之间经过交换机)，数据流的最大帧长从84～1 538 Bytes中随机选取。选定网络中数据流的比特速率为0.1 Mbit/s，并由此计算出数据流的带宽分配间隔。网络中虚拟链路路径通过负载均衡策略自动生成。

图10 案例分析拓扑结构Fig.10 Topology of case study

对于实验案例，分别分配高优先级数据流的数目占端口发送数据流数目的百分比为10%～90%，并以10%为间隔。通过具备详细参数的网络演算分别计算高、低优先级数据流端到端延迟上界；此外，通过统计的方法得到组网特征参数，并通过优先级驱动的泛化网络演算分别计算高、低优先级数据流端到端延迟上界，如图11所示。

图11 基本网络演算与泛化网络演算对比Fig.11 Comparison of basic network calculus and generalized network calculus

对于具备详细参数的网络演算下的高优先级数据流，随高优先级数据流占比增大，其端到端延迟上界增大。而随着高优先级数据流占比增大，低优先级数据流端到端延迟上界略微增大，在图11 中变化不明显。对于优先级驱动的泛化网络演算下的高优先级数据流，变化趋势与基本网络演算相同，但延迟高于基本网络演算。由于实验案例的组网特征参数由统计得出，不能保证在不同高优先级数据流占比下网络中端口发送高、低优先级数据流最大带宽利用率之和+为定值，因此优先级驱动的泛化网络演算计算出的低优先级数据流端到端延迟上界并非一直增长趋势,但趋势变化不大。

定义同一网络配置下具备详细配置参数的网络演算得到的延迟上界占优先级驱动的泛化网络演算得到的延迟上界的比例为优先级驱动的泛化网络演算的算法有效性。分别对比高、低优先级数据流在具备详细配置参数的网络演算和优先级驱动的泛化网络演算下的延迟上界。可以看出，与具备详细配置参数的网络演算依赖网络拓扑、流量详细配置参数和优先级不同，优先级驱动的泛化网络演算依据抽象出的端口发送高、低优先级数据流带宽利用率等组网特征参数，进行采用优先级调度机制网络的实时性能分析。在不同高优先级数据流占比下，高优先级数据流延迟上界算法有效性均高于39%，低优先级数据流延迟上界算法有效性均高于33%。由此可以得出，在未知组网拓扑以及流量具体配置参数和优先级的情况下，优先级驱动的泛化网络演算具备对采用高、低优先级调度机制的交换式网络实时性预估的能力。

分别对比具备详细参数的网络演算和优先级驱动的泛化网络演算下高、低优先级数据流延迟上界，均可以得出高优先级数据流延迟上界小于低优先级数据流延迟上界的结论。因此区分优先级可以改善高优先级数据流延迟上界，适合实时性要求高的消息应用。并且通过具备详细参数的网络演算和优先级驱动的泛化网络演算2种，都可以得出降低高优先级数据流占比可以明显改善高优先级数据流延迟上界，但对低优先级数据流延迟上界影响不大的结论。因此在网络设计中可以将对实时性要求高的消息设置为高优先级，且消息实时性要求越高，网络中高优先级数据流占比应越小。