汽车技术

TSN中具有实时感知的AVB路由与调度算法^*

PDF下载

燕云飞 , 朱元 , 栗彬琦 , 钟旭

汽车技术 | 车联网通信性能优化与安全技术专题 2024,(10): 43-48

收起

汽车技术 | 车联网通信性能优化与安全技术专题 2024, (10): 43-48

TSN中具有实时感知的AVB路由与调度算法^*

全屏

燕云飞, 朱元, 栗彬琦, 钟旭

作者信息

同济大学，上海 201804

AVB Routing and Scheduling Algorithm with Real-Time Perception in TSN

Yunfei Yan, Yuan Zhu, Binqi Li, Xu Zhong

Affiliations

Tongji University, Shanghai 201804

出版时间: 2024-10-24 doi: 10.19620/j.cnki.1000-3703.20240510

文章导航

摘要

收起

为了保障网络实时性传输需求，提升调度成功率，提出了具有实时感知的AVB流路由与调度算法，模拟车载时间敏感网络（TSN）场景下，音视频桥（AVB）流传输情况，并分析算法对网络调度成功率的影响。试验结果表明：随着数据流数量增加，相较于非实时感知算法与部分实时感知算法，具有实时感知的AVB流路由与调度算法使网络调度成功率分别提升26%和11%，该算法可优化TSN网络对AVB流的带宽预留，实现对数据流路由和报文信息的实时感知。

关键词

时间敏感网络 / 网络演算 / 基于信用值整形器 / 路由与调度

Abstract

收起

In order to ensure the real-time transmission requirements of the network and improve the success rate of scheduling, an Audio Video Bridging (AVB) stream routing and scheduling algorithm with real-time perception is proposed to simulate the AVB stream transmission in the scenario of vehicle-mounted Time-Sensitive Networking (TSN), and the influence of the proposed algorithm on the success rate of network scheduling is analyzed. The experimental results show that with the increase of the number of data flows, compared with the non-real-time perception algorithm and some real-time perception algorithms, the AVB flow routing and scheduling algorithm with real-time perception increases the success rate of network scheduling by 26% and 11% respectively, and the algorithm can optimize the bandwidth reservation of AVB flow in the TSN network and realize the real-time perception of data flow routing and packet information.

Key words

Time-Sensitive Networking (TSN) / Network calculus / Credit based shaper / Routing and scheduling

引用本文

燕云飞, 朱元, 栗彬琦, 钟旭. TSN中具有实时感知的AVB路由与调度算法^*. 汽车技术, 2024 , (10) : 43 -48 . DOI: 10.19620/j.cnki.1000-3703.20240510

Yunfei Yan, Yuan Zhu, Binqi Li, Xu Zhong. AVB Routing and Scheduling Algorithm with Real-Time Perception in TSN[J]. Automobile Technology, 2024 , (10) : 43 -48 . DOI: 10.19620/j.cnki.1000-3703.20240510

正文

收起

1 前言

收起

随着汽车智能化、网联化的发展，车载通信的传输需求日益提高，带宽高、组网方便、成本低廉的车载以太网作为新一代车载网络总线技术受到广泛关注^[1]。传统以太网缺乏实时性和可靠性的保障^[2]，而EtherCat、PROFINET等实时以太网协议并不互通，同一组网中无法保证网络实时性^[3]。为此，IEEE 802.1工作组拓展了原本用于音视频流量的音视频桥（Audio Video Bridging，AVB），将其重新命名为时间敏感网络（Time-Sensitive Networking，TSN）^[4]。该协议族可适应不同应用场景下TSN的流量传输需求，在自动驾驶^[5-7]、车载多媒体^[8-10]等领域逐步推广应用。

TSN根据通信需求将网络流量划分为8个优先级，通过虚拟局域网（Virtual Local Area Network，VLAN）报文头的用户优先级字段进行标识区分，优先级由高到低分别为时间触发（Time Triggered，TT）流、AVB流和尽力而为（Best Effort，BE）流。孙国玮等^[11-13]等通过启发式算法对路由与调度方法实现了多径路由优化，但规避了复杂门控排布问题。基于负载均衡的AVB路由优化算法、动态AVB流路由与调度等算法，解决部分链路拥塞、网络负载不均衡问题，但会产生额外时延及开销^[14-16]。网络演算理论提供了计算端到端最差时延和交换机节点数据积压上限的理论基础^[17]，可应用于网络仿真计算、网络性能评估^[18]和TSN路由与调度机制。当前应用网络演算理论计算最差时延边界以指导TSN路由与调度时，缺乏对网络信息的实时感知，降低了网络调度的成功率。

为解决上述问题，本文提出一种实时感知的AVB流路由与调度算法，通过感知车载网络中数据流的路由情况，调整网络演算时各交换机端口的最坏情况估计，使用基于网络演算理论的叠加迭代法计算最差时延，以提升车载网络调度成功率。

2 系统模型

收起

2.1 网络拓扑模型

网络拓扑模型是实际物理网络模型的抽象，由终端、交换机和物理链路组成。本文车载TSN拓扑结构以无向图表示，如图1所示。

图中车载TSN有6个终端，分别为ES1、ES2、ES3、ES4、ES5、ES6，5个交换机SW1、SW2、SW3、SW4、SW5；顶点间实线为TSN数据链路，且由两顶点序号唯一确定；e(i, j)为连接顶点i和顶点j的数据链路，如e(0,4)为SW1与SW5间的数据链路；图中虚线为流量的路由，由源终端（如ES1）、途经的交换机（如SW1）和目的终端（如ES3）组成，或以数据流途经的交换机发送端口表示；路由表R为网络中所有路由r_i的集合。

2.2 数据流模型

数据流模型用于流量的路由与调度，本文讨论的车载TSN数据流包含AVB流和BE流，可表示为

f i T = (l, p, v s, v d, D r)

。其中：i为数据流编号，用于区分不同数据流；T为流量类型，根据报文的VLAN优先级，分别为AVB_A、AVB_B和BE；l为数据流的数据帧长度，最小为64 B，最大为1 518 B；p为数据流的传输周期；v_s为数据流的源终端；v_d为数据流的目的终端；D_r为数据流端到端最差时延需求。

3 理论基础

收起

3.1 TSN协议

TSN为两层网络，位于网络架构的数据链路层和物理层。根据VLAN报文头的用户优先级字段，TSN交换机可在入口识别报文优先级，并对进入发送端口的不同队列进行流量整形。在TSN协议族中，IEEE 802.1 Qav定义了基于信用值的整形器（Credit Based Shaper，CBS），用于AVB流的流量整形^[4]。

CBS通过AVB流的信用值判断是否转发AVB报文，从而避免大量AVB数据帧阻塞网络，其工作机制如图2所示。

当k（k∈{AVB_A,AVB_B}）流在TSN交换机出口队列等待转发时，其CBS信用值C_k将上升，上升速率为s_i,_k；当AVB流从出口队列转发时，C_k将下降，下降速率为s_d,_k。C_k的上界为C_k_,max，下界为C_k_,min。CBS要求k流只能在满足以下条件时，通过交换机出口向其他节点转发：

a. 无更高优先级的AVB报文在队列中等待。

b. 当前无正在转发的报文。

c. C_k≥0。

3.2 网络演算理论

网络演算理论根据数据流通过交换机节点的服务曲线、到达曲线计算最差时延边界和数据积压上限。

定义最小加卷积和最小加反卷积为：

（1）

f t ⊗ g t = i n f 0 ≤ s ≤ t f t - s + g s f t ⊘ g t = s u p s ≥ 0 f t + s - g s

式中：f( )和g( )为时间t的连续函数，s为(0,t)的某时刻，inf( )为上确界函数，sup( )为下确界函数。

到达曲线α(t)是对数据流到达交换机情况A(t)的悲观估计，其约束为

∀ s ≤ t, A t - A s ≤ α t - s

。服务曲线β(t)是对交换机处理数据流能力A′(t)的悲观估计，

A' t ≥ i n f 0 ≤ s ≤ t A s + β t - s = A t ⊗ β t

。通过数据流的到达曲线和服务曲线，计算数据流在交换机上的最差时延和最坏数据积压，结果如图3所示。其中，最差时延是服务曲线和到达曲线的最大水平距离，最坏数据积压是服务曲线和到达曲线的最大垂直距离。

假设

[f t] ↑ + = m a x {0 ≤ s ≤ t | f s, 0}

，此函数为非负的单调增函数。TSN网络的链路速率为c，l_A,max、l_B,max、l_BE,max分别为AVB_A、AVB_B和BE流的最大长度，l_n,max=max{l_B,max,l_BE,max}为AVB_B和BE流的最大长度，s_i,_n为AVB流的上升速率，s_d,_n为AVB流的下降速率，n∈{A,B}。因此，AVB_A流、AVB_B流的服务曲线为^[19]：

（2）

β A (t) = s i, A ∙ c s i, A - s d, A [t - l n, m a x c] ↑ + β B (t) = s i, B ∙ c s i, B - s d, B [t - l A, m a x + l B E, m a x c + l n, m a x c ∙ s i, A s d, A] ↑ +

为降低计算的复杂度，AVB流的到达曲线采用经典漏桶模型^[20]：

（3）

α k h t = σ k + ρ k ∙ t

式中：h为交换机的发送端口，σ_k为AVB流的瞬时突发流量，ρ_k为AVB流在较长时间跨度内的数据到达速率。

对于交换机端口h_n，若有多条相同优先级的AVB流

f i

到达，则

α k h n t = ∑ f i ∈ k α f i h n t

，该到达曲线具有叠加性。因此，对于AVB流

f i

，其从源节点到目标节点的时延为：

（4）

D f i = t s + ∑ h n ∈ r i D k h n + t r D k h n = h α k h n t, β k h n t

式中：t_s为发送时延，t_r为链路时延（数值极小，常忽略不计）。

4 具有实时感知的AVB流路由与调度算法

收起

为实现对AVB流的合理路由和调度，降低CBS带宽预留的同时，满足AVB流的时延需求，本文设计具有实时感知的AVB流路由与调度算法。该算法能够实时感知数据流对各个交换机输出端口的影响，对各交换机输出端口的最坏情况估计进行优化，从而提升网络调度成功率。

4.1 AVB最差时延边界算法

通过叠加迭代法计算各交换机发送端口的最差时延，并根据路由结果计算数据流传输的最差时延边界。对网络交换机发送端口初始化，设置各端口CBS的上升速率。随后，计算每条路由的流量在网络中单独传输时，各交换机端口的到达曲线。

在仅考虑该AVB数据流时，对于流

f i

的节点出端口h_n，最坏延时为

D f i h n = h α f i h n t, β f i h n t

。其中，服务曲线为

β f i h n t ，

到达曲线为

α f i h n t = α f i h 0 t + ∑ h j = h 1 h n - 1 D h j

。

将同一个交换机输出端口中，各优先级相同的AVB数据流的到达曲线叠加，计算该端口的最差时延：

（5）

α A V B_A h n t = ∑ f i ∈ A V B_A α f i h n t α A V B_B h n t = ∑ f i ∈ A V B_B α f i h n t D k h n = h α k h n t, β k h n t

通过迭代最差时延，不断更新各数据流的到达曲线及各交换机端口的最差时延。迭代若干次后，输出最接近真实情况的各交换机端口的最差时延。按照路由表，计算各AVB流路由时的最差时延

D f i = t s + ∑ h n ∈ r i D k h n

。

叠加迭代法在叠加到达曲线后，各交换机端口的最差时延必定小于等于真实时延，相较于单独传输时，每条流在其经过的交换机端口的到达曲线的截距增加，因而迭代后的最差时延会逐渐接近真实时延。而完全消除误差所需的迭代次数受网络中各数据流路由交叉端口的数量、路由最大跳数影响。

4.2 路由算法与调度算法

路由算法的目的是找到一条从源节点到目的节点的最低开销路径，即端到端的最差时延。路由经过的交换机节点数量越多，转发时延越大，端到端最差时延越大。因此，本文选用K最短路径算法计算AVB流量的路由，得到源节点到目标节点的前k条最短路径，选用迪杰斯特拉算法计算BE流的路由，得到源节点到目标节点的一条最短路径。

为保证网络资源的有效利用，公平分配带宽，本文使用局部搜索法作为调度算法，如图4所示。首先，为所有交换机输出端口分配相同的带宽预留，然后，根据网络演算结果，对未满足最差时延的链路进行调整。调度成功后，尝试降低部分交换机发送端口的AVB带宽预留，最终得到优化后的调度结果。

4.3 算法整体运算流程

具有实时感知的AVB流路由与调度算法在TSN的网络集中配置（Centralised Network Configuration，CNC）节点中运行，CNC节点收集各终端的通信需求，并负责所有流量的路由与调度。

算法执行过程如图5所示，在初始化阶段，CNC收集网络传输需求，分离AVB流和BE流。首先，对BE流计算路由，设置各交换机端口CBS上升速率初始值，同时，根据BE流的路由情况更新各交换机输出端口的l_BE,max，便于后续网络演算；然后，使用K最短路径算法计算每条AVB流的前k条最短路径，选取AVB流的路由组成路由表，使用叠加迭代法进行网络演算，结合局部搜索法找到能够满足所有AVB流传输需求的局部最优解，若该路由表无法满足传输需求则重新选择路由并进行调度计算；最后，CNC节点整合各交换机的路由表和CBS配置，将配置报文发送至各交换机，至此完成网络配置。

5 试验及结果分析

收起

对比实时感知、部分实时感知以及非实时感知的AVB流路由与调度算法，分析各算法的调度成功率。

非实时感知的AVB流路由与调度算法不对非AVB数据流的路由信息进行实时感知。在进行AVB流网络演算时，将各端口传输相同预设长度的BE流数据帧作为最坏情况计算，即各交换机发送端口的l_BE,max配置为固定值。

部分实时感知的AVB流路由与调度算法在CNC收集数据流信息后，得到网络中要传输的BE流数据帧的最大长度。在进行AVB流网络演算时，将各端口传输本网络中最大长度的BE流数据帧作为最坏情况计算，即各交换机发送端口的l_BE,max配置为网络中需要传输的BE流数据帧的最大长度。

试验的网络拓扑结构见图1，随机生成AVB和BE数据流，总数为4~12条。通过CNC进行路由调度，试验使用带宽为100 Mbit/s的全双工物理链路。随机生成的数据流参数为：l在64~1 518 B范围内随机选取，p在12~36 ms范围内随机选取，v_s、v_d在ES1~ES5中随机选取且互不相同，D_r=1 ms。对AVB流进行路由的K最短路径算法设定k=3。

对于非实时感知算法，各交换机发送端口预设的l_BE,max分别设为1 500 B、1 000 B和500 B进行测试。本文对于数据流调度成功率ε的定义为：

（6）

ε = N s N s + N f

式中：N_s为调度成功次数，N_f为调度失败次数。

3种算法的测试结果如图6所示，随着数据流的总数增加，各算法的调度成功率均会下降，相较于非实时感知算法与部分实时感知算法，本文算法的调度成功率分别提升26%和11%。

随着非实时感知算法减小网络中BE流数据帧的预设值，其调度成功率逐渐上升，但与本文算法相比仍有一定差距。在实际数据传输中，各端口并非总是传输BE流，因此，预留固定带宽在资源利用中往往属于悲观估计。虽然非实时感知算法乐观地估计了各端口传输的BE流数据帧，但该算法的调度结果总体上仍属悲观估计。由于非实时感知算法对所有端口的l_BE,max进行一致估计，若估计过于乐观，即预设l_BE,max过小，将导致数据帧较长的BE流经过的发送端口AVB流的带宽预留不足，造成实际时延无法满足传输需求。

部分实时感知算法将各端口均需传输网络中最大长度的BE流数据帧，作为最坏情况分析计算。相较于非实时感知算法，虽然优化了BE流数据帧长度设置方式，但最大值的选择使部分实时感知算法的调度提升较为有限。

实时感知算法根据路由表中的实际BE流情况，减小网络演算时所用端口的BE流最大帧长度，从而优化AVB流的带宽预留结果，一定程度上减少了CBS对BE流的阻塞。

综上所述，本文算法可有效提升网络调度的成功率，在3种算法均能成功调度的场景下，实时感知算法的带宽预留结果明显优于部分实时感知与非实时感知算法。

6 结束语

收起

通过对比非实时感知与部分实时感知算法，本文算法在进行AVB的路由和带宽分配流程中，加入了对其他数据流路由情况和数据帧信息的感知环节，优化了对网络最坏情况估计，有效提升网络调度的成功率。

同时，在基于网络演算理论进行TSN中AVB流的路由与调度时，应对其他类型的数据流进行实时感知，确定其数据帧长度和路由信息。若无法确定数据流的传输信息，可在AVB流进行网络演算过程中，对干扰AVB数据流传输的数据帧长度适当地乐观估计。对于车载TSN的实际工程应用具有一定指导意义。

目前，本文算法在AVB流路由表的选取中，未缩小路由表的求解空间，因而在AVB数据流数量较大的车载网络中，短时间内难以计算出路由和调度结果。未来，将根据带宽均衡的思想优化AVB路由算法，进一步提升该算法在面对大规模车载TSN时的求解性能。

基金

收起

*南昌市汽车智能与新能源研究所前瞻技术研究(TPD-TC202211-07)
联合汽车电子有限公司高级研究项目(NE-2023-06)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

叶锋, 吴俊博, 曾军. 车载以太网系统应用问题分析与解决措施[J]. 电力机车与城轨车辆, 2022, 45(2): 103-106+111.

, WU

J B

, ZEN

. Analysis and Solution of Application Problems of Vehicle Ethernet System[J]. Electric Locomotives & Mass Transit Vehicles, 2022, 45(2): 103-106+111.

[2]

DECOTIGNIE

J D

. Ethernet-Based Real-Time and Industrial Communications[J]. Proceedings of the IEEE, 2005, 93(6): 1102-1117.

[3]

FRANK

, NAYAK

N G

. No-Wait Packet Scheduling for IEEE Time-Sensitive Networks (TSN)[C]// Proceedings of the 24th International Conference on Real-Time Networks and Systems. New York, USA: Association for Computing Machinery, 2016.

[4]

DENG

L B

, XIE

G Q

, LIU

, et al. A Survey of Real-Time Ethernet Modeling and Design Methodologies: from AVB to TSN[J]. ACM Computing Surveys, 2022, 55(2): 1-36.

[5]

黄韬, 鲁京京, 朱海龙, 等. 车载时间敏感网络: 现状与展望[J]. 北京邮电大学学报, 2023, 46(6): 46-54.

HUANG

, LU

J J

, ZHU

H L

, et al. Automotive In-Vehicle Time-Sensitive Networking: The State of the Art and Prospect[J]. Journal of Beijing University of Posts and Telecommunications, 2023, 46(6): 46-54.

[6]

SAMII

, ZINNER

. Level 5 by Layer 2: Time-Sensitive Networking for Autonomous Vehicles[J]. IEEE Communications Standards Magazine, 2018, 2(2): 62-68.

[7]

朱永健. 基于AVB的车载千兆以太网交换机设计与研究[D]. 天津: 河北工业大学, 2019.

ZHU

Y J

. Design and Research of Automotive Gigabit Ethernet Switch Based on AVB[D]. Tianjin: Hebei University of Technology, 2019.

[8]

李昌远. 基于车载以太网的多媒体系统应用研究[D]. 长春: 吉林大学, 2017.

C Y

. Research on the Application of Multimedia System based on Ethernet of Vehicle[D]. Changchun: Jilin University, 2017.

[9]

常青. 车载Ethernet AVB节点设计与实现[D]. 长春: 吉林大学, 2015.

CHANG

. Design and Implementation of the On-Board Ethernet AVB Node[D]. Changchun: Jilin University, 2015.

[10]

, KIM

Y S

. Latency Analysis of AVB Network and Optimization Design for Automotive[J]. Journal of Semiconductor & Display Technology, 2019, 18(3): 127-132.

[11]

孙国玮. 确定性算力网络中的资源调度和路由问题研究[D]. 北京: 北京邮电大学, 2023.

SUN

G W

. Study on Resourse Scheduling and Routing Problems in Deterministic Computing First Network[D]. Beijing: Beijing University of Posts and Telecommunications, 2023.

[12]

朱琳. 时间敏感网络的域内及域间流量调度算法研究[D]. 北京: 北京邮电大学, 2023.

ZHU

. Research on Intra-Domain and Cross-Domain Traffic Scheduling Algorithm for Time-Sensitive Network[D]. Beijing: Beijing University of Posts and Telecommunications, 2023.

[13]

韩文璇. 时间敏感网络中混合流量调度算法的研究[D]. 北京: 北京邮电大学, 2023.

HAN

W X

. Research on Hybrid Traffic Scheduling Algorithms in Time Sensitive Networking[D]. Beijing: Beijing University of Posts and Telecommunications, 2023.

[14]

GAVRILUŢ

, ZHAO

L X

, RAAGAARD

M L

, et al. AVB-Aware Routing and Scheduling of Time-Triggered Traffic for TSN[J]. IEEE Access, 2018, 6: 75229-75243.

[15]

LAURSEN

S M

, POP

, STEINER

. Routing Optimization of AVB Streams in TSN Networks[J]. ACM SIGBED Review, 2016, 13(4): 43-48.

[16]

SYED

A A

, AYAZ

, TIM

, et al. Dynamic Scheduling and Routing for TSN Based In-Vehicle Networks[C]// 2021 IEEE International Conference on Communications Workshops (ICC Workshops). Canada: IEEE, 2021.

[17]

FIDLER

. Survey of Deterministic and Stochastic Service Curve Models in the Network Calculus[J]. IEEE Communications surveys, 2010, 12(1): 59-86.

[18]

WANG

, CIUCU

, LIN

, et al. A Stochastic Power Network Calculus for Integrating Renewable Energy Sources into the Power Grid[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(6): 1037-1048.

[19]

JOAN

A R D A

, BOYER

. Complete Modelling of AVB in Network Calculus Framework[C]// Proceedings of the 22nd International Conference on Real-Time Networks and Systems. New York, USA: Association for Computing Machinery, 2014.

[20]

ZHAO

L X

, POP

, ZHENG

, et al.Timing Analysis of AVB Traffic in TSN Networks Using Network Calculus[C]// 2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). Porto, Portugal: IEEE, 2018.

2024年第卷第10期

PDF下载

218

引用本文

BibTeX

文章信息

doi: 10.19620/j.cnki.1000-3703.20240510

首发时间：2025-12-22
出版时间：2024-10-24

补充材料

相关文章

文章信息

作者

出版历史

修回日期：2024-07-26

基金

*南昌市汽车智能与新能源研究所前瞻技术研究(TPD-TC202211-07)

联合汽车电子有限公司高级研究项目(NE-2023-06)

作者信息

同济大学，上海 201804

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/qcjs/CN/10.19620/j.cnki.1000-3703.20240510

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT