随着车辆智能化、互联以及智能交通技术的提出, 车载信息系统的内涵与外延, 在近年来得到了迅速扩充。这些新技术包括:机载网络^[1-3]、智能设备与车辆的互联、车际信息交互、无人驾驶和高级驾驶辅助系统 (ADAS) 以及实时多媒体娱乐系统等。这些应用导致的数据传输和处理, 对传统的车载网络提出了严重挑战, 例如基于总线式的CAN、LIN、Flexray等传输协议已无法满足车载信息系统的要求。近年来, 车辆信息系统逐渐引入了以太网如时间敏感以太网 (TSN, time sensitive network) 以及时间触发以太网 (time triggered ethernet, TTE) 等^[4], 其中TSN与TTE和标准以太网的传输协议兼容, 且在标准以太网的基础上, 增加了多节点时钟同步传输以及更有效的流量控制功能。Steinbach等人的研究^[5]认为, 用于控制系统的时钟同步且具有确定性的Flexray总线的延迟和抖动性能, 堪与时间触发以太网相比拟, 即Flexray可以与时间触发以太网互相替代。

采用以太网作为车载信息系统的传输协议后, 传统的总线式数据传输变成了交换式数据传输, 但由此将会带来系统交换机内部的数据包排队、丢包等问题, 从而导致更加不确定的传输延迟。其解决途径必须对车载信息系统的数据流、网络拓扑、网络设备数量和连接方式进行周密严谨的设计。

在现阶段, 车辆上的以太网节点数目一般在十几个左右。例如, 德国宝马公司Hyung-Taek等人设计的基于以太网的汽车网络模型^[6], 包含14个终端节点和2个交换机, 即汽车前舱和后舱各一个交换机, 其中前舱交换机子网承载的信息包括驾驶员控制、辅助视频等; 后舱交换机子网主要完成汽车后座的车载多媒体点播和娱乐系统数据传输等, 即将相关小的节点分布到不同的区域中, 跨交换机传输的数据则相对较少。

如何形式化建模, 并分析交换机在级联情况下, 计算数据包的延迟时间, 已成为车载网络系统拓扑结构设计研究的重要问题。目前, 排队论已成为可靠性分析、故障跟踪研究的重要方法之一。文献[7]基于混合排队模型建模故障排除过程, 提出了一种跟踪软件动态失效过程。在处理排错策略和排错资源局限性的基础上, 实现了对构件软件可靠性过程的仿真。文献[8]采用排队论设计了一种适合车辆监控系统中短消息通信网关可靠性和稳定性分析的方法, 该方法能提高监控系统网关的高效性和稳定性。类似的, 排队论也为级联交换机网络中的传输延迟分析提供了一个级联模型设计方法和分析方法。本文旨在基于排队论设计级联模型, 并据此分析传输延迟的计算方法。

1 基于M/M/1级联模型设计及排队系统理论分析

为分析2个交换机级联情况下, 数据包通过第二个交换机的延迟时间, 我们首先建立级联交换机队列模型。

1.1 级联交换机队列模型

将交换机等效为一个排队系统和一个服务台 (M/M/1), 对于车载信息网上的一个网络节点来说, 其到达模型可以简化为图 1所示。

图 1a) 描述了只包含一个交换机的网络系统, 图 1b) 则描述存在级联交换机和旁路的网络。由于在实际系统中, 2个交换机之间不可避免地会互相传输数据 (否则可以独立为2个无关联子网), 因此针对图 1b) 的情形, 有必要分析交换机级联情况下对数据包延迟的影响。

1.2 级联队列系统状态转移及传输延迟计算

在网络中, M/M/1排队系统中的平均服务时间, 对应于包的长度, 而交换机的处理能力为常量 (C bytes/s), 因此, 通过包的产生时间间隔和包的长度, 可以确定M/M/1系统的系统参数, 即包的到达率为λ packets/s, 假设包的平均长度为M bytes, 则交换机的包处理率为C/M packets/s, 即该系统中μ=C/M。

在一个级联队列中, 假设q₁和q₂表示2个级联的M/M/1型队列, 包的到达率为λ, 2个队列的服务率均为μ(相同的交换机), 假定各个队列的到达和服务相互独立, 则可用一个二维马尔可夫过程表示, 若以m, n(m, n≥0) 代表q₁、q₂ 2个排队系统中的包个数 (包括队列中的包和正在服务的包) 则系统的状态转移可用图 2描述。

若系统的稳态存在, 则其局部平衡方程为

(1)

式中，π_{m, n}代表系统状态m, n为稳态的概率。

通过带入, 可验证其解为π_{m, n}=(1-ρ)²ρ^m+n, 其中ρ=λ/μ。

于是, 可以得到其边缘概率

(2)

(3)

上述分析表明级联的2个M/M/1队列可以等效为2个独立队列, 其中每个队列的平均长度均为ρ/(1-ρ)。因此, 通过2个级联队列的包的平均总延迟为2/(μ-λ)。

上述分析隐含的假设是, 数据包在离开第一个队列时, 其包的长度将按指数分布进行了一次随机分配。对于第一个队列而言, 它是一个标准的M/M/1模型, 第一个队列的平均队列长度和等待时间为模型求解值。值得注意的是, 对于第二个队列来说, 数据包在第一个排队系统中的服务时间与第二个排队系统中的服务时间不独立。在上述网络交换系统中, 每个交换机的处理能力相同且为常量 (C bytes/s), 因此, 对于任意一个数据包, 其在第一个队列中的服务时间与第二个队列的服务时间相等, 因此第二个队列中的平均延迟不一定等于1/(μ-λ)。

2 车载系统级联排队分析 2.1 负载较轻时的级联排队系统分析

在系统具有较轻负载时 (例如μ≫λ), 可令1/(μ-λ)≈1/μ; 第二个队列的平均延迟应根据1/(μ-λ) 式估算。但当系统负载较大时 (例如μ≈λ), 则第二个队列的队列长度和延迟时间与M/M/1系统的模型解存在一些差别。

2.2 μ≤λ时的级联排队系统分析

当μ≤λ时, 可知随着时间的增加, 第一个队列的队列长度 (速率近似正比于时间, 即 (λ-μ)T) 趋于无穷, 且系统的服务/空闲百分比为100%。因此, 一定时间之后, 对于第二个队列而言, 包的到达服从参数为μ的指数分布, 包的服务时间与该包与前一个包的到达时间间隔相等。

图 3中的t_i代表第i个包到达第二个队列的时刻, 不妨设t₀=0, 可知t_i-t_i-1(i≥1) 服从参数为μ的指数分布, 由于假设第一个队列和第二个队列的服务时间相等, 因此第i个包在第二个队列中的服务时间等于t_i-t_i-1。考虑第i个包离开系统的时刻T_i:

当i=1时, T₁=t₁+t₁;

当i=2时, 存在2种不同情况, 第一种情况是当t₂≥2t₁, 即第二个包到达时第一个包已离开系统, 此时T₂=t₂+t₂-t₁; 第二种情况是当t₁≤t₂≤2t₁, 此时第二个包到达时第一个包依然在服务, 可知第一个包已经服务的时间为t₂-t₁, 因此第二个包离去的时间T₂=t₂+[t₁-(t₂-t₁)]+t₂-t₁=t₂+t₁;

当i=3时, 存在3种不同情况:

第一种情况是当t₃-t₂≥t₁∩t₃-t₂≥t₂-t₁, 此时T₃=t₃+t₃-t₂;

第二种情况是当t₂-t₁≥t₁∩t₃-t₂≤t₂-t₁, 此时T₃=t₃+t₂-t₁;

第三种情况是当t₂-t₁≤t₁∩t₃-t₂≤t₁, 此时T₃=t₃+t₁;

不难验证, 第n个包离开系统的时刻为:

(4)

因此, 可以得出, 第n个包在系统内的延迟时间为, 其累计概率分布为

可以求得其均值为

(5)

其中, (5) 式的最后一个等号可用数学归纳法证得。这一结果表明, 在μ≤λ时的第二个交换机中, 第n个数据包在系统内的平均延迟时间, 只与其到达顺序有关, 并呈调和级数增长。图 4是通过数值求解 (5) 式得到的前50个包的平均延迟时间。图中横坐标为系统中到达包的序号, 纵坐标代表第n个到达包在系统内的平均延迟时间。由于调和级数与对数函数当n趋于无穷时只差一个常量, 因此可认为随着包个数的增加, 其平均延迟时间的增长与对数曲线近似, 即:

(6)

从 (6) 式可以看出, 尽管随着时间趋于无穷, 系统的平均延迟也趋于无穷大, 但是延迟时间的增长是包个数的对数函数。假设在一个极端的理论系统中, 每10^-9 s产生一个包, 一年大约是3×10⁷ s, 因此, 一年内产生的包的数目约为3×10¹⁶个, 此时系统的平均延迟。根据Little定理可知, 系统内等待的数据包的个数为38个, 可以认为这一排队系统在实际应用中几乎不会产生不利影响。

一个直观的解释是:由于第n个包的延迟时间, 0≤i≤n, 而t_i-t_i-1服从参数为μ的指数分布, 这相当于进行n次指数分布实验取其结果的最大值, 由于P(t>T)=e^-μT, 可知指数分布实验取到较大值的概率呈指数衰减。因此, 在有限次试验中, 几乎不会出现非常大的试验值。更有利的是, 在实际系统中, 这一情况必然不会发生, 因为在各种网络协议中, 数据包的长度有限 (注意到该模型的前提是, 到达时间间隔即为下一个数据包的服务时间), 即数据包的服务时间有限, 这就保证了不存在服务时间非常大的数据包, 即系统内任一数据包的延迟时间都是有限的。

2.3 μ>λ时的级联排队系统分析

下面, 考虑一般情况, 即μ>λ时第二个队列的分布情况。此时, 易知第二个队列的到达率是λ, 服务率为μ。依然考虑图 3所示的到达过程, 可知t_i-t_i-1(i≥1) 服从参数为λ的指数分布。由于假设第一个队列和第二个队列的服务时间相等, 因此第i个包在第二个队列中的服务时间t′_i≤t_i-t_i-1, 可知当第一个排队系统空载时 (依概率1-ρ) 有t′_i < t_i-t_i-1。下面依然考虑第i个包离开系统的时刻T_i:

当i=1时, T₁=t₁+t′₁;

当i=2时, 存在2种不同情况, 第一种情况是当t₂≥t₁+t′₁, 即第二个包到达时第一个包已离开系统, 此时T₂=t₂+t′₂; 第二种情况是当t₁≤t₂≤t₁+t′₁时, 第二个包到达时第一个包依然在服务, 因此第二个包离去的时间T₂=t₁+t′₁+t′₂;

当i=3时, 存在3种不同情况, 第一种情况是当t₃≤t₁+t′₁∪t₂≤t₁+t′₁∩t₃≤t₂+t′₂时, T₃=t₁+t′₁+t′₂+t′; 第二种情况是当t₂≥t₁+t′₁∩t₃≤t₂+t′₂时, T₃=t₂+t′₂+t′₃; 第三种情况是当t₃≥max{t₁+t′₁+t′₂, t₂+t′₂}时, T₃=t₃+t′₃;

不难验证, 第n个包离开系统的时刻满足

(7)

易见, 若令t′_k=t_k-t_k-1, 则 (7) 式与 (4) 式等价, 第n个数据包在系统内的延迟为

(8)

式中, t′_k-(t_k-t_k-1)≤0, E (t′_k)=1/μ, E (t_k-t_k-1)=1/λ。

这里对 (8) 式进行一些定性分析。首先可知E (t′_k)=μ, 令, 并假定i与t′_k, t_k-t_k-1相互独立, 则。由于第二个队列中, 数据包的延迟时间>0, 即必须满足>0, 将其化简, 可得

(9)

式中，n-i的含义是第n个数据包刚刚进入系统时, 系统中剩余的数据包的数目。若令n→+∞, 则可知系统内平均数据包数目不大于。

根据Little定理, 该系统的平均延迟时间T满足

(10)

此外, 令i=n, 有d_n≥t′_n, 即, 平均队列长度。

因此, 一般情况下, 当μ>λ时, 则第二级队列的延迟时间 (或系统内等待的数据包数目) 满足以下2个推论:

1) 系统中, 随时间增长的平均队列长度的增长率比对数曲线更为缓慢, 且时间趋于无穷时, 平均队列长度有界, 其上界是λ/(μ-λ);

2) 总延迟时间 (包括服务时间和排队时间) 有限, 其均值的上界为1/(μ-λ)。

3 仿真实验及分析

使用OPNET网络仿真软件对2个级联的M/M/1队列进行仿真, 分别取μ=λ, μ=1.1λ, μ=1.2λ, μ=2λ, μ=5λ; 仿真采用一个数据包发生过程, 两级排队过程和一个数据包接收过程。其中数据包发生过程按均值为1 s的指数分布产生数据包, 数据包的长度是满足均值为M(bits) 的指数分布, 排队过程选用的模型为acb_-fifo, 包交换的服务率为常数C(bits/s)。

在本例中, 取λ=1(1/s), μ=C/M(1/s), 其中M=100 bits, 按照不同的λ/μ调整C的取值。其他测试条件包括仿真时间200 h, 延迟数据按排队模型默认值设置, 即每2 h采样1次。实验结果如表 1所示。

从表 1可以看出, 当μ≠λ时, 数据包在第一个交换机中的平均延迟时间与理论值1/(μ-λ) 符合的很好; 当系统负载较重时, 数据包在第一个交换机和第二个交换机的延迟时间差别较大, 当μ≤1.2λ时, 在仿真时间内数据包的延迟时间T < 1/(μ-λ); 当系统趋于空载时 (μ≥2λ), 此时发现第二个队列的平均延迟时间比第一个队列大, 甚至超过了理论值1/(μ-λ), 这一问题应该受限于仿真时间和仿真软件的实现方式, 有待于进一步讨论。

图 5给出了μ=λ时的延迟时间与采样值得到的曲线, 可见图 5b) 给出的数据包, 在第二个交换机中的延迟曲线较好的证实了前文中的分析。下一步的仿真验证工作, 将结合实际车辆信息系统中的数据, 给出实际级联交换机网络系统中的数据包延迟分析。

4 结论

由上述分析可知, 在包含2个级联交换机的实际网络中, 在网络负荷较高时 (μ≤1.2λ), 数据包在通过第二个交换机的平均延迟时间总是小于其在第一个交换机的平均延迟时间, 且在第二个交换机中等待的数据包平均数量, 不会由于第一个交换机负荷较高而显著增加; 即使第一个交换机的负荷达到100%时, 第二个交换机内部正等待包的平均数量呈时间的对数函数增加, 而且在实际网络中, 由于数据包的大小有限, 因此延迟时间不会无限增加。这表明第一个交换机对第二个交换机起到了数据缓冲与保护的作用。这一结论的一个直接应用就是在车载网络设计中, 跨交换机的数据传输对直连交换机的本地节点之间数据传输延迟的影响有限, 例如跨交换机传输的非实时视频流数据不会因其流量相对较大而严重影响本地节点的通信。本文进一步的研究方向是结合实际车载信息系统的数据流和交换网络、协议对数据包的延迟进行分析。