【摘要】為了保障網絡實時性傳輸需求，提升調度成功率，提出了具有實時感知的AVB流路由與調度算法，模擬車載時間敏感網絡（TSN）場景下，音視頻橋（AVB）流傳輸情況，并分析算法對網絡調度成功率的影響。試驗結果表明：隨著數(shù)據流數(shù)量增加，相較于非實時感知算法與部分實時感知算法，具有實時感知的AVB流路由與調度算法使網絡調度成功率分別提升26%和11%，該算法可優(yōu)化TSN網絡對AVB流的帶寬預留，實現(xiàn)對數(shù)據流路由和報文信息的實時感知。

主題詞：時間敏感網絡 網絡演算 基于信用值整形器 路由與調度

中圖分類號：U463.6" "文獻標志碼：A" "DOI： 10.19620/j.cnki.1000-3703.20240510

AVB Routing and Scheduling Algorithm with Real-Time Perception

in TSN

Yan Yunfei， Zhu Yuan， Li Binqi， Zhong Xu

（Tongji University， Shanghai 201804）

【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路由與調度算法[J]. 汽車技術， 2024（10）： 43-48.

YAN Y F， ZHU Y， LI B Q， et al. AVB Routing and Scheduling Algorithm with Real-Time Perception in TSN[J]. Automobile Technology， 2024（10）： 43-48.

1 前言

隨著汽車智能化、網聯(lián)化的發(fā)展，車載通信的傳輸需求日益提高，帶寬高、組網方便、成本低廉的車載以太網作為新一代車載網絡總線技術受到廣泛關注[1]。傳統(tǒng)以太網缺乏實時性和可靠性的保障[2]，而EtherCat、PROFINET等實時以太網協(xié)議并不互通，同一組網中無法保證網絡實時性[3]。為此，IEEE 802.1工作組拓展了原本用于音視頻流量的音視頻橋（Audio Video Bridging，AVB），將其重新命名為時間敏感網絡（Time-Sensitive Networking，TSN）[4]。該協(xié)議族可適應不同應用場景下TSN的流量傳輸需求，在自動駕駛[5-7]、車載多媒體[8-10]等領域逐步推廣應用。

TSN根據通信需求將網絡流量劃分為8個優(yōu)先級，通過虛擬局域網（Virtual Local Area Network，VLAN）報文頭的用戶優(yōu)先級字段進行標識區(qū)分，優(yōu)先級由高到低分別為時間觸發(fā)（Time Triggered，TT）流、AVB流和盡力而為（Best Effort，BE）流。孫國瑋等[11-13]等通過啟發(fā)式算法對路由與調度方法實現(xiàn)了多徑路由優(yōu)化，但規(guī)避了復雜門控排布問題?；谪撦d均衡的AVB路由優(yōu)化算法、動態(tài)AVB流路由與調度等算法，解決部分鏈路擁塞、網絡負載不均衡問題，但會產生額外時延及開銷[14-16]。網絡演算理論提供了計算端到端最差時延和交換機節(jié)點數(shù)據積壓上限的理論基礎[17]，可應用于網絡仿真計算、網絡性能評估[18]和TSN路由與調度機制。當前應用網絡演算理論計算最差時延邊界以指導TSN路由與調度時，缺乏對網絡信息的實時感知，降低了網絡調度的成功率。

為解決上述問題，本文提出一種實時感知的AVB流路由與調度算法，通過感知車載網絡中數(shù)據流的路由情況，調整網絡演算時各交換機端口的最壞情況估計，使用基于網絡演算理論的疊加迭代法計算最差時延，以提升車載網絡調度成功率。

2 系統(tǒng)模型

2.1 網絡拓撲模型

網絡拓撲模型是實際物理網絡模型的抽象，由終端、交換機和物理鏈路組成。本文車載TSN拓撲結構以無向圖表示，如圖1所示。

圖中車載TSN有6個終端，分別為ES1、ES2、ES3、ES4、ES5、ES6，5個交換機SW1、SW2、SW3、SW4、SW5；頂點間實線為TSN數(shù)據鏈路，且由兩頂點序號唯一確定；e（i， j）為連接頂點i和頂點j的數(shù)據鏈路，如e（0，4）為SW1與SW5間的數(shù)據鏈路；圖中虛線為流量的路由，由源終端（如ES1）、途經的交換機（如SW1）和目的終端（如ES3）組成，或以數(shù)據流途經的交換機發(fā)送端口表示；路由表R為網絡中所有路由ri的集合。

2.2 數(shù)據流模型

數(shù)據流模型用于流量的路由與調度，本文討論的車載TSN數(shù)據流包含AVB流和BE流，可表示為[fTi=（l，p，vs，vd，Dr）]。其中：i為數(shù)據流編號，用于區(qū)分不同數(shù)據流；T為流量類型，根據報文的VLAN優(yōu)先級，分別為AVB_A、AVB_B和BE；l為數(shù)據流的數(shù)據幀長度，最小為64 B，最大為1 518 B；p為數(shù)據流的傳輸周期；vs為數(shù)據流的源終端；vd為數(shù)據流的目的終端；Dr為數(shù)據流端到端最差時延需求。

3 理論基礎

3.1 TSN協(xié)議

TSN為兩層網絡，位于網絡架構的數(shù)據鏈路層和物理層。根據VLAN報文頭的用戶優(yōu)先級字段，TSN交換機可在入口識別報文優(yōu)先級，并對進入發(fā)送端口的不同隊列進行流量整形。在TSN協(xié)議族中，IEEE 802.1 Qav定義了基于信用值的整形器（Credit Based Shaper，CBS），用于AVB流的流量整形[4]。

CBS通過AVB流的信用值判斷是否轉發(fā)AVB報文，從而避免大量AVB數(shù)據幀阻塞網絡，其工作機制如圖2所示。

當k（k∈{AVB_A，AVB_B}）流在TSN交換機出口隊列等待轉發(fā)時，其CBS信用值Ck將上升，上升速率為si，k；當AVB流從出口隊列轉發(fā)時，Ck將下降，下降速率為sd，k。Ck的上界為Ck，max，下界為Ck，min。CBS要求k流只能在滿足以下條件時，通過交換機出口向其他節(jié)點轉發(fā)：

a. 無更高優(yōu)先級的AVB報文在隊列中等待。

b. 當前無正在轉發(fā)的報文。

c. Ck≥0。

3.2 網絡演算理論

網絡演算理論根據數(shù)據流通過交換機節(jié)點的服務曲線、到達曲線計算最差時延邊界和數(shù)據積壓上限。

定義最小加卷積和最小加反卷積為：

[ft?gt=inf0≤s≤tft-s+gsft?gt=sups≥0ft+s-gs ] （1）

式中：f（ ）和g（ ）為時間t的連續(xù)函數(shù)，s為（0，t）的某時刻，inf（ ）為上確界函數(shù)，sup（ ）為下確界函數(shù)。

到達曲線α（t）是對數(shù)據流到達交換機情況A（t）的悲觀估計，其約束為[?s≤t， At-As≤αt-s]。服務曲線β（t）是對交換機處理數(shù)據流能力A′（t）的悲觀估計，[A't≥inf0≤s≤tAs+βt-s=At?βt]。通過數(shù)據流的到達曲線和服務曲線，計算數(shù)據流在交換機上的最差時延和最壞數(shù)據積壓，結果如圖3所示。其中，最差時延是服務曲線和到達曲線的最大水平距離，最壞數(shù)據積壓是服務曲線和到達曲線的最大垂直距離。

假設[[ft]+↑=max{0≤s≤t|fs，0}]，此函數(shù)為非負的單調增函數(shù)。TSN網絡的鏈路速率為c，lA，max、lB，max、lBE，max分別為AVB_A、AVB_B和BE流的最大長度，ln，max=max{lB，max，lBE，max}為AVB_B和BE流的最大長度，si，n為AVB流的上升速率，sd，n為AVB流的下降速率，n∈{A，B}。因此，AVB_A流、AVB_B流的服務曲線為[19]：

[βA（t）=si，A?csi，A-sd，A[t-ln，maxc]+↑βB（t）=si，B?csi，B-sd，B[t-lA，max+lBE，maxc+ln，maxc?si，Asd，A]+↑]" （2）

為降低計算的復雜度，AVB流的到達曲線采用經典漏桶模型[20]：

[αhkt=σk+ρk?t] （3）

式中：h為交換機的發(fā)送端口，σk為AVB流的瞬時突發(fā)流量，ρk為AVB流在較長時間跨度內的數(shù)據到達速率。

對于交換機端口hn，若有多條相同優(yōu)先級的AVB流[fi]到達，則[αhnkt=fi∈kαhnfit]，該到達曲線具有疊加性。因此，對于AVB流[fi]，其從源節(jié)點到目標節(jié)點的時延為：

[Dfi=ts+hn∈riDhnk+trDhnk=hαhnkt， βhnkt] （4）

式中：ts為發(fā)送時延，tr為鏈路時延（數(shù)值極小，常忽略不計）。

4 具有實時感知的AVB流路由與調度算法

為實現(xiàn)對AVB流的合理路由和調度，降低CBS帶寬預留的同時，滿足AVB流的時延需求，本文設計具有實時感知的AVB流路由與調度算法。該算法能夠實時感知數(shù)據流對各個交換機輸出端口的影響，對各交換機輸出端口的最壞情況估計進行優(yōu)化，從而提升網絡調度成功率。

4.1 AVB最差時延邊界算法

通過疊加迭代法計算各交換機發(fā)送端口的最差時延，并根據路由結果計算數(shù)據流傳輸?shù)淖畈顣r延邊界。對網絡交換機發(fā)送端口初始化，設置各端口CBS的上升速率。隨后，計算每條路由的流量在網絡中單獨傳輸時，各交換機端口的到達曲線。

在僅考慮該AVB數(shù)據流時，對于流[fi]的節(jié)點出端口hn，最壞延時為[Dhnfi=hαhnfit， βhnfit]。其中，服務曲線為[βhnfit，]到達曲線為[αhnfit=αh0fit+hj=h1hn-1Dhj]。

將同一個交換機輸出端口中，各優(yōu)先級相同的AVB數(shù)據流的到達曲線疊加，計算該端口的最差時延：

[αhnAVB_At=fi∈AVB_AαhnfitαhnAVB_Bt=fi∈AVB_BαhnfitDhnk=hαhnkt， βhnkt] （5）

通過迭代最差時延，不斷更新各數(shù)據流的到達曲線及各交換機端口的最差時延。迭代若干次后，輸出最接近真實情況的各交換機端口的最差時延。按照路由表，計算各AVB流路由時的最差時延[Dfi=ts+hn∈riDhnk]。

疊加迭代法在疊加到達曲線后，各交換機端口的最差時延必定小于等于真實時延，相較于單獨傳輸時，每條流在其經過的交換機端口的到達曲線的截距增加，因而迭代后的最差時延會逐漸接近真實時延。而完全消除誤差所需的迭代次數(shù)受網絡中各數(shù)據流路由交叉端口的數(shù)量、路由最大跳數(shù)影響。

4.2 路由算法與調度算法

路由算法的目的是找到一條從源節(jié)點到目的節(jié)點的最低開銷路徑，即端到端的最差時延。路由經過的交換機節(jié)點數(shù)量越多，轉發(fā)時延越大，端到端最差時延越大。因此，本文選用K最短路徑算法計算AVB流量的路由，得到源節(jié)點到目標節(jié)點的前k條最短路徑，選用迪杰斯特拉算法計算BE流的路由，得到源節(jié)點到目標節(jié)點的一條最短路徑。

為保證網絡資源的有效利用，公平分配帶寬，本文使用局部搜索法作為調度算法，如圖4所示。首先，為所有交換機輸出端口分配相同的帶寬預留，然后，根據網絡演算結果，對未滿足最差時延的鏈路進行調整。調度成功后，嘗試降低部分交換機發(fā)送端口的AVB帶寬預留，最終得到優(yōu)化后的調度結果。

4.3 算法整體運算流程

具有實時感知的AVB流路由與調度算法在TSN的網絡集中配置（Centralised Network Configuration，CNC）節(jié)點中運行，CNC節(jié)點收集各終端的通信需求，并負責所有流量的路由與調度。

算法執(zhí)行過程如圖5所示，在初始化階段，CNC收集網絡傳輸需求，分離AVB流和BE流。首先，對BE流計算路由，設置各交換機端口CBS上升速率初始值，同時，根據BE流的路由情況更新各交換機輸出端口的lBE，max，便于后續(xù)網絡演算；然后，使用K最短路徑算法計算每條AVB流的前k條最短路徑，選取AVB流的路由組成路由表，使用疊加迭代法進行網絡演算，結合局部搜索法找到能夠滿足所有AVB流傳輸需求的局部最優(yōu)解，若該路由表無法滿足傳輸需求則重新選擇路由并進行調度計算；最后，CNC節(jié)點整合各交換機的路由表和CBS配置，將配置報文發(fā)送至各交換機，至此完成網絡配置。

5 試驗及結果分析

對比實時感知、部分實時感知以及非實時感知的AVB流路由與調度算法，分析各算法的調度成功率。

非實時感知的AVB流路由與調度算法不對非AVB數(shù)據流的路由信息進行實時感知。在進行AVB流網絡演算時，將各端口傳輸相同預設長度的BE流數(shù)據幀作為最壞情況計算，即各交換機發(fā)送端口的lBE，max配置為固定值。

部分實時感知的AVB流路由與調度算法在CNC收集數(shù)據流信息后，得到網絡中要傳輸?shù)腂E流數(shù)據幀的最大長度。在進行AVB流網絡演算時，將各端口傳輸本網絡中最大長度的BE流數(shù)據幀作為最壞情況計算，即各交換機發(fā)送端口的lBE，max配置為網絡中需要傳輸?shù)腂E流數(shù)據幀的最大長度。

試驗的網絡拓撲結構見圖1，隨機生成AVB和BE數(shù)據流，總數(shù)為4～12條。通過CNC進行路由調度，試驗使用帶寬為100 Mbit/s的全雙工物理鏈路。隨機生成的數(shù)據流參數(shù)為：l在64～1 518 B范圍內隨機選取，p在12～36 ms范圍內隨機選取，vs、vd在ES1～ES5中隨機選取且互不相同，Dr=1 ms。對AVB流進行路由的K最短路徑算法設定k=3。

對于非實時感知算法，各交換機發(fā)送端口預設的lBE，max分別設為1 500 B、1 000 B和500 B進行測試。本文對于數(shù)據流調度成功率ε的定義為：

[ε=NsNs+Nf] （6）

式中：Ns為調度成功次數(shù)，Nf為調度失敗次數(shù)。

3種算法的測試結果如圖6所示，隨著數(shù)據流的總數(shù)增加，各算法的調度成功率均會下降，相較于非實時感知算法與部分實時感知算法，本文算法的調度成功率分別提升26%和11%。

隨著非實時感知算法減小網絡中BE流數(shù)據幀的預設值，其調度成功率逐漸上升，但與本文算法相比仍有一定差距。在實際數(shù)據傳輸中，各端口并非總是傳輸BE流，因此，預留固定帶寬在資源利用中往往屬于悲觀估計。雖然非實時感知算法樂觀地估計了各端口傳輸?shù)腂E流數(shù)據幀，但該算法的調度結果總體上仍屬悲觀估計。由于非實時感知算法對所有端口的lBE，max進行一致估計，若估計過于樂觀，即預設lBE，max過小，將導致數(shù)據幀較長的BE流經過的發(fā)送端口AVB流的帶寬預留不足，造成實際時延無法滿足傳輸需求。

部分實時感知算法將各端口均需傳輸網絡中最大長度的BE流數(shù)據幀，作為最壞情況分析計算。相較于非實時感知算法，雖然優(yōu)化了BE流數(shù)據幀長度設置方式，但最大值的選擇使部分實時感知算法的調度提升較為有限。

實時感知算法根據路由表中的實際BE流情況，減小網絡演算時所用端口的BE流最大幀長度，從而優(yōu)化AVB流的帶寬預留結果，一定程度上減少了CBS對BE流的阻塞。

綜上所述，本文算法可有效提升網絡調度的成功率，在3種算法均能成功調度的場景下，實時感知算法的帶寬預留結果明顯優(yōu)于部分實時感知與非實時感知算法。

6 結束語

通過對比非實時感知與部分實時感知算法，本文算法在進行AVB的路由和帶寬分配流程中，加入了對其他數(shù)據流路由情況和數(shù)據幀信息的感知環(huán)節(jié)，優(yōu)化了對網絡最壞情況估計，有效提升網絡調度的成功率。

同時，在基于網絡演算理論進行TSN中AVB流的路由與調度時，應對其他類型的數(shù)據流進行實時感知，確定其數(shù)據幀長度和路由信息。若無法確定數(shù)據流的傳輸信息，可在AVB流進行網絡演算過程中，對干擾AVB數(shù)據流傳輸?shù)臄?shù)據幀長度適當?shù)貥酚^估計。對于車載TSN的實際工程應用具有一定指導意義。

目前，本文算法在AVB流路由表的選取中，未縮小路由表的求解空間，因而在AVB數(shù)據流數(shù)量較大的車載網絡中，短時間內難以計算出路由和調度結果。未來，將根據帶寬均衡的思想優(yōu)化AVB路由算法，進一步提升該算法在面對大規(guī)模車載TSN時的求解性能。

參 考 文 獻

[1] 葉鋒， 吳俊博， 曾軍. 車載以太網系統(tǒng)應用問題分析與解決措施[J]. 電力機車與城軌車輛， 2022， 45（2）： 103-106+111.

YE F， WU J B， ZEN J. Analysis and Solution of Application Problems of Vehicle Ethernet System[J]. Electric Locomotives amp; 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 D， 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 H， 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] 黃韜， 魯京京， 朱海龍， 等. 車載時間敏感網絡： 現(xiàn)狀與展望[J]. 北京郵電大學學報， 2023， 46（6）： 46-54.

HUANG T， 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 S， ZINNER H. Level 5 by Layer 2： Time-Sensitive Networking for Autonomous Vehicles[J]. IEEE Communications Standards Magazine， 2018， 2（2）： 62-68.

[7] 朱永健. 基于AVB的車載千兆以太網交換機設計與研究[D]. 天津： 河北工業(yè)大學， 2019.

ZHU Y J. Design and Research of Automotive Gigabit Ethernet Switch Based on AVB[D]. Tianjin： Hebei University of Technology， 2019.

[8] 李昌遠. 基于車載以太網的多媒體系統(tǒng)應用研究[D]. 長春： 吉林大學， 2017.

LI C Y. Research on the Application of Multimedia System based on Ethernet of Vehicle[D]. Changchun： Jilin University， 2017.

[9] 常青. 車載Ethernet AVB節(jié)點設計與實現(xiàn)[D]. 長春： 吉林大學， 2015.

CHANG Q. Design and Implementation of the On-Board Ethernet AVB Node[D]. Changchun： Jilin University， 2015.

[10] AN B， KIM Y S. Latency Analysis of AVB Network and Optimization Design for Automotive[J]. Journal of Semiconductor amp; 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 L. 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? V， 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 P， STEINER W. Routing Optimization of AVB Streams in TSN Networks[J]. ACM SIGBED Review， 2016， 13（4）： 43–48.

[16] SYED A A， AYAZ S， TIM L， et al. Dynamic Scheduling and Routing for TSN Based In-Vehicle Networks[C]// 2021 IEEE International Conference on Communications Workshops （ICC Workshops）. Montreal， QC， Canada： IEEE， 2021.

[17] FIDLER M. Survey of Deterministic and Stochastic Service Curve Models in the Network Calculus[J]. IEEE Communications surveys， 2010， 12（1）： 59-86.

[18] WANG K， CIUCU F， LIN C， 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 M. 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 P， ZHENG Z， 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年7月26日。