交换式以太网NC建模与实时性能分析

摘要

交换式以太网的实时性能分析是工业以太网研究领域的一个热点课题，目前还没有一个有效的数学模型来对其进行描述。通过对典型交换机结构的分析，应用网络微积分理论建立了交换机的服务曲线模型，该模型将交换机中的数据流分为实时数据和非实时数据，并得到了最大延迟值和最大缓存需求值等，最大延迟为交换机的实时应用提供了理论边界值，最大缓存需求值为在实时工业环境中的交换机构建提供了理论参考。

正文

《1 引言》

1 引言

交换式以太网采用微冲突域划分技术, 解决了共享式以太网中CSMA/CD仲裁机制所带来的冲突延时不确定性问题。此外, 802.1p, 802.1q、全双工等功能的引入也使交换式以太网应用到实时性较强的工业控制领域成为可能 ^[1,2]。尽管已经有很多将交换式以太网应用到实时数据传输的实例, 但其传输机制多采用令牌驱动、时间驱动或以高带宽来换取高实时性等方式, 带宽浪费严重。交换式以太网采用星型拓扑结构, 其核心功能由基于802.1D的交换机完成。由于不同厂商生产的交换机体系结构存在着很大的差异, 而且网络中的数据流具有非线性特性, 为交换式以太网的建模和实时性能分析带来了困难, 目前, 以太网交换机的建模和实时性能分析仍然是个有待解决的问题。

将采用网络微积分理论对以太网交换机进行建模, 并通过对模型的分析得出量化结论。

《2 以太网交换机结构》

2 以太网交换机结构

交换机的交换结构 (switch fabric) 类型主要包括总线交换、共享内存交换和阵列交换 (crossbar) 3种, 其中阵列交换是目前以太网交换机的主流交换结构 ^[3], 如图1所示。阵列交换机允许多个端口的数据流同时进行交换, 大大减少了总线交换和共享内存交换结构中资源分时复用所带来的等待延迟, 而且, 输入缓存和输出缓存的采用降低了数据包的存取次数, 因此, 具有背板带宽高、交换延迟小的优点, 非常适合构建高速、低延迟的交换网络, 在企业和学术组织中都得到了广泛关注 ^[4,5,6,7]。此外优先级机制IEEE802.1p的采用使得区分服务DiffSev得以在交换式以太网中实现, 交换机的每个输入端口根据实时性要求的不同将输入数据流分成最多可达8个优先级队列。产生数据流的网络节点在发送数据前将优先级标签打入数据帧的VLAN tag字段, 然后, 交换机的输入端口逻辑分类器对其进行分类。经过阵列交换结构后, 输出端口逻辑根据不同数据流的优先级进行调度输出。将以网络微积分为数学工具对采用阵列交换结构的以太网交换机的实时性能进行分析。

《图1》

图1 支持802.1q功能的以太网交换机逻辑结构

Fig.1 The logical structure of Ethernet switch supporting 802.1q

《3 网络微积分NC (network calculus)》

3 网络微积分NC (network calculus)

网络微积分是20世纪末逐渐成形的一门针对计算机网络的确定性排队系统进行分析的系统理论 ^[8,9,10,11], 其以最小加代数 (min-plus algebra) 为数学基础。网络微积分系统理论将目标系统的非线性特性转化到线性域进行处理, 即以非线性系统特征参数的边界值的集合作为网络的特征曲线进行分析。因此, 本质上是一种最糟糕响应分析 (the worst case response analysis) , 这对于分析硬实时系统非常有利。采用网络微积分对计算机网络进行分析时, 首先要建立数据流的到达曲线 (arrival curve) 和传输设备的服务曲线 (service curve) , 通过推导它们之间的内在关系得到所需要的量化参数。

到达曲线用来描述系统输入数据流特征, 设输入数据流R (t) 为累积函数, 当其满足R (t) ≤C_α (R) (t) , 则称α为系统的到达曲线, 其中C_α (R) (t) = (α⨂R) (t) , 符号⨂表示最小加卷积, 其定义为h (t) ⨂x (t) =inf_s:0≤s≤t{h (t-s) +x (s) }。典型的到达曲线有漏斗模型和通用信元速率算法模型GERA (generic cell rate algorithm) , 它们分别对应于精练函数 (affine function) 和梯形函数 (staircase function) 。与到达曲线不同, 服务曲线则用来描述网络传输单元的服务特性, 当输入数据流R (t) 进入网络系统S时, 经传输单元中的调度器后输出数据流为R^* (t) , 当且仅当广义增函数β (0) = 0且R^* (t) ≥ (R⨂β) (t) 时, 则称系统S提供给数据流R (t) 的服务曲线为β (t) , 典型的服务曲线有通用处理器共享曲线GPS和Greedy整形器曲线。

《4 交换式以太网的到达曲线和服务曲线》

4 交换式以太网的到达曲线和服务曲线

由文献[3]可知, 阵列交换机内部存在着输入逻辑、阵列交换结构和输出逻辑3个串连的服务单元, 如图1所示, 其延迟分别为输入逻辑延迟t_input、阵列交换延迟t_s和输出逻辑延迟t_output。阵列交换延迟t_s是很小的确定值, 而端口逻辑中存在的调度器延迟和排队延迟, 是交换机中主要的延迟, 其计算最为关键。设各个单元所提供的服务曲线为β₁ (t) , β₂ (t) , …, β_n (t) , 则由文献[11]可知, 这些串连服务单元所能提供的服务曲线β (t) 为β (t) =β₁ (t) ⨂β₂ (t) …β_n (t) , 当各个服务曲线为速率延迟函数LR (latency-rate) 时, 则

《图2》

《4.1到达曲线》

4.1到达曲线

将分类后的每一个优先级队列作为集成服务数据流, 则由文献[12]的到达曲线α (t) 满足四元组T-SPEC (p, M, r, b) , 即α (t) =min (M+pt, rt+b) , 其中M为最大数据帧长度, p为尖峰速率, b为最大迸发速率, r为平均到达速率, 如图2所示, 实线为到达曲线α (t) , 即:

《图3》

《图4》

图2 交换机中一个优先级数据流的到达曲线

Fig.2 The arrival curve of one priority data flow in switch

《4.2服务曲线》

4.2服务曲线

服务曲线特性由交换机内部的调度器来决定, 传统的交换机内部缺乏灵活的调度策略, 随着人们对网络QoS要求不断提高, 越来越多的厂商开始在其产品内部集成了先进的调度策略, 如速率PQ, WRR, WFQ, DWRR等, 这里以PQ为例来建立交换机的服务曲线。工业以太网环境中通常含有实时和非实时两种数据类型, 因此, 这里将以双队列缓存交换为基础建立以太网交换机的服务曲线模型, 并对其实时性能进行评估。如图3所示, 数据流经过交换机的分类器分类, 在输出端口缓存中形成高优先级的实时消息队列R_H (t) 和低优先级的非实时消息队列R_L (t) , 相应的输出数据流分别为R^*_H (t) 和R^*_L (t) , 高优先级的消息队列的到达曲线为α (t) , 调度器的服务速率为C。

《图5》

图3 双队列交换机服务模型

Fig.3 The service model of double queues switch

《4.2.1 实时消息队列服务曲线》

4.2.1 实时消息队列服务曲线

设s为高优先级消息队列的沉积开始时间, 即R^*_H (s) =R_H (s) , 对于大于s的时刻t来说有R^*_H (t) -R^*_H (s) ≥C (t-s) -M, 则R^*_H (t) ≥R_H (s) +C (t-s) -M=R_H (t) +[C (t-s) -M]⁺ , 其中[Ct-M]⁺为速率为C, 延迟值为M/C的速率延迟函数 ^[13]β_{C, M/C} (t) 。因此R^*_H (t) ≥ (R_H⨂β_{C, M/C}) (t) , 即高优先级消息队列的服务曲线为β_{C, M/C} (t) 。

《4.2.2 非实时消息队列服务曲线》

4.2.2 非实时消息队列服务曲线

设当高优先级消息的到达曲线为α_H (t) 满足公式 (1) 时, 低优先级消息队列不会出现由于高优先级的消息到达速率过快而产生“饥饿”现象。当低优先级消息队列开始在时间s′沉积时, 则有R^*_H (t) = R_H (s′) 和R^*_L (t) =R_L (s′) , 对于大于s′的时间t:

《图6》

又因为R^*_H (t) -R^*_H (s) = R^*_H (t) -R_H (s′) ≤R_H (t) -R_H (s′) ≤α_H (t-s′) , 且R^*_H (t) -R^*_H (s′) ≥0, 则:

《图7》

当0<t< (M—b) / (r—p) 时有

《图8》

当t> (M-b) / (r-p) 时有

《图9》

由式 (5) 和式 (6) , 设

《图10》

则结合公式 (4) 有R^*_L (t) ≥ (R_L⨂s) (t) , 即调度器为低优先级消息队列提供的服务曲线S (t) 是分段的速率延迟函数。

《5 交换式以太网的实时性能评估》

5 交换式以太网的实时性能评估

交换式以太网的实时特性是由网络中所传输数据的到达曲线和交换机的服务曲线决定的, 此外, 交换机内部为消息队列所提供的缓存大小也直接影响着传输的QoS。

实时数据流的到达曲线α (t) = min (p₁t+M, r₁t+b₁) 与服务曲线S₁ (t) = (β_{C, M/C}) (t) 如图4所示, 其中t_max = (M-b₁) / (r₁-b₁) 。根据网络微积分理论中延迟边界的计算方法 ^[10], 当系统的到达曲线和服务曲线分别为α (t) 和β (t) 时, 数据流R (t) 的延迟边界t_d为α (t) 与β (t) 的垂直距离最大值, 即t_d=max_t:t≥0 {min {Δ:Δ≥0 and α (t) ≤β (t+Δ) }}。因此, 实时数据的最大延迟为

《图11》

《图12》

图4 实时消息队列延迟边界和沉积边界

Fig.4 The delay and backlog bounds of real-time queue

实时数据所需的最大缓存由其沉积边界决定, 即到达曲线与服务曲线的横向最大距离

《图13》

由四元组T-SPEC (p, M, r, b) 的特性可知C-r₁>C-p₁, 因此, 非实时数据流到达曲线α₂ (t) =min (p₂t+M, r₂t+b₂) 和服务曲线S₂ (t) 如图5所示, 其中t_max= (M-b₂) / (r₂-p₂) , t_dL存在t_d2和t′_d2两种情况, 而由文献[11]可知, 在实际网络中通常有C-p₁≤r₂, 因此得到非实时数据流的最大延迟值为

《图14》

《图15》

图5 非实时消息队列延迟边界和沉积边界

Fig.5 The delay and backlog bounds of non real-time queue

由p₂t_max+M= (C-r₁) t-b₁可得非实时数据所需最大缓存为

《图16》

当交换机的输入端口逻辑与输出端口逻辑采用相同的调度器时, 其服务曲线相同, 均为速率延迟函数。因此, 根据式 (1) , 当实时和非实时数据流的队列缓存的大小分别满足式 (9) 和式 (11) 时, 其交换延迟的最大值分别为t_switch=2t_dH+t_s和t_switch=2t_dL+t_s, 其中t_dH和t_dL分别满足式 (8) 和式 (10) 。此外, 由GPS特性可知, 每个队列的平均到达速率和应小于最大服务速率C, 即 $\sum_{k = 1}^{Ν} r_{k} \leq C$ $\sum_{k = 1}^{Ν} r_{k} \leq C$ 。

《6 总结》

6 总结

采用了网络微积分的确定性理论建立了具有实时和非实时双队列的交换机的到达曲线和服务曲线模型, 得到了交换机的最大延迟值和最大缓存需求值, 为交换式以太网的实时性能分析提供了有效理论指导。网络微积分理论在不断发展, 已经能够进行网络性能的确定性分析, 其随机性理论还处在起步阶段。下一步的工作是研究应用网络微积分的随机性理论对交换机中的非实时数据流进行建模和分析, 以提高非实时数据服务曲线的软延迟特性。

展示更多