面向時(shí)間觸發(fā)流的時(shí)延感知差分多徑轉(zhuǎn)發(fā)機(jī)制

譚兵，蔡岳平，姚宗辰

（重慶大學(xué)微電子與通信工程學(xué)院，重慶 400044）

1 引言

時(shí)間敏感網(wǎng)絡(luò)[1]（Time Sensitive Networking，TSN）的誕生源于實(shí)時(shí)以太網(wǎng)概念的提出。在這之前，以EtherCAT、Profinet等為代表的一些實(shí)時(shí)通信技術(shù)已經(jīng)逐步應(yīng)用于各個(gè)領(lǐng)域。雖然這些技術(shù)都基于傳統(tǒng)以太網(wǎng)，但是又具有一些專有機(jī)制，使得相互之間并不能兼容運(yùn)行，也就制約了實(shí)時(shí)以太網(wǎng)的進(jìn)一步發(fā)展。在這種背景下，IEEE802.1工作組提出了時(shí)間敏感網(wǎng)絡(luò)的概念，意圖通過標(biāo)準(zhǔn)化使其在各個(gè)領(lǐng)域都能夠同構(gòu)運(yùn)行，提供實(shí)時(shí)的數(shù)據(jù)傳輸[2]。IEEE 802.1時(shí)間敏感網(wǎng)絡(luò)是一種擴(kuò)展傳統(tǒng)以太網(wǎng)的技術(shù)，具有時(shí)間同步、有界低延時(shí)、低抖動(dòng)、兼容性強(qiáng)等特點(diǎn)，能夠?qū)崿F(xiàn)流的低延時(shí)高可靠傳輸。TSN廣泛應(yīng)用于智能電網(wǎng)、工業(yè)自動(dòng)化、車輛的駕駛系統(tǒng)、航空電子等領(lǐng)域，可提供超高可靠低延時(shí)通信（Ultra Reliable Low Latency Communications，URLLC）。

在這些應(yīng)用中，時(shí)間觸發(fā)（Time Triggered，TT）流扮演著重要的角色，它是一類優(yōu)先級(jí)較高的流量，具有周期性、時(shí)延確定性、時(shí)延有界性的特點(diǎn)。這類流量常用于傳輸關(guān)鍵數(shù)據(jù)，如工業(yè)網(wǎng)絡(luò)中的控制流就是典型的時(shí)間觸發(fā)流[3]。

然而，當(dāng)前TSN中TT流的傳輸還存在著未解決的問題，如在傳統(tǒng)的轉(zhuǎn)發(fā)方案中，具有相同最短路徑的流將會(huì)在同一條路徑傳輸。單條路徑上的傳輸流量過多，導(dǎo)致調(diào)度時(shí)保護(hù)帶寬過多，從而導(dǎo)致端到端平均時(shí)延過長(zhǎng)。采用負(fù)載均衡多路徑轉(zhuǎn)發(fā)可以有效的減少保護(hù)帶寬，但是由于流量的差異性，會(huì)導(dǎo)致最短路徑上保護(hù)帶寬過多。同時(shí)，最為關(guān)鍵的是，沒有考慮分析處理時(shí)延和發(fā)送時(shí)延來減少總時(shí)延。

2 TT流路徑選擇的研究現(xiàn)狀與分析

TSN流量的路徑優(yōu)化問題在TSN網(wǎng)絡(luò)中較為常見，本文關(guān)注的重點(diǎn)是TT流路徑選擇問題。傳統(tǒng)的TSN路徑選擇方法使用快速生成樹協(xié)議（Rapid Spanning Tree Protocol，RSTP）或最短路徑橋接（Shortest Path Bridging，SPB）來確定路徑[4]。在確定路徑之后，TSN再針對(duì)路徑和節(jié)點(diǎn)計(jì)算出門控制列表（Gate Control List，GCL）[5]。端口特定的GCL列表以及精確的時(shí)鐘同步協(xié)議（IEEE 802.1AS）使得基于以太網(wǎng)的網(wǎng)絡(luò)能夠滿足關(guān)鍵任務(wù)應(yīng)用的嚴(yán)格時(shí)延約束[6]。許多研究人員研究了各種路徑選擇問題，實(shí)現(xiàn)在硬截止日期和最壞情況延遲的背景下確定以太網(wǎng)的時(shí)間表和路徑[7,8]，提高TSN應(yīng)用到網(wǎng)絡(luò)物理系統(tǒng)中的控制性能和穩(wěn)定性。

文獻(xiàn)[9]提出在路徑選擇時(shí)考慮最大鏈路負(fù)載率，通過遺傳算法求出流的最佳轉(zhuǎn)發(fā)路徑集，再對(duì)流量進(jìn)行調(diào)度。文中是根據(jù)最小化最大鏈路負(fù)載率來完成選路，公式（1)表示為最大鏈路負(fù)載率，其中ri,j表示流量i在鏈路j上傳輸，F(xiàn)為流量集合，E為鏈路集合。rsli,j為單個(gè)流量負(fù)載的時(shí)隙長(zhǎng)度，cti,j為流量周期。這種解決方案存在的問題是，在路徑選擇時(shí)僅考慮了最大鏈路負(fù)載率，忽視了跳數(shù)及流量負(fù)載帶來的時(shí)延影響。

與文獻(xiàn)[9]相比，文獻(xiàn)[10]中的負(fù)載均衡多徑轉(zhuǎn)發(fā)機(jī)制在最大鏈路負(fù)載率相同時(shí)，流量?jī)?yōu)先考慮跳數(shù)較少的路徑進(jìn)行傳輸。文獻(xiàn)[10]的作者為聯(lián)合路由調(diào)度問題提出了基于整數(shù)線性規(guī)劃（Integer Linear Programming，ILP）的路由調(diào)度解決方案，利用路徑選擇與調(diào)度的同步計(jì)算，實(shí)現(xiàn)每個(gè)流的時(shí)延優(yōu)化。但是，其路徑優(yōu)化選擇參數(shù)指標(biāo)過于單一。文中方案與文獻(xiàn)[9]相比，其不同在于最大負(fù)載率相同時(shí)，優(yōu)先選擇跳數(shù)最少的路徑。

Hop-Load[11]轉(zhuǎn)發(fā)方案在考慮路徑負(fù)載均衡[10]的基礎(chǔ)上，引入了跳數(shù)對(duì)路徑選擇的影響。公式（2）展示了文中提出的路徑優(yōu)化選擇過程，其數(shù)學(xué)表達(dá)式含義同公式（1）。其中，Umax為最大鏈路負(fù)載率。這種解決方案存在的問題是，未考慮不同大小的TT流在各路徑上的處理時(shí)延與發(fā)送時(shí)延的差異性。同時(shí)，由于文獻(xiàn)[11]和文獻(xiàn)[10]均是基于ILP的調(diào)度過程，且其復(fù)雜度較高，上述解決方案在計(jì)算路徑以及調(diào)度時(shí)刻列表時(shí)也是特別耗時(shí)的。

上述最新方案中僅僅是簡(jiǎn)單地考慮跳數(shù)與負(fù)載均衡對(duì)時(shí)延的影響，并沒有考慮不同大小的流量在不同路徑上所帶來的時(shí)延影響。相比文獻(xiàn)[9]和文獻(xiàn)[11]，本文提出的時(shí)延感知差分多徑轉(zhuǎn)發(fā)機(jī)制，不僅考慮了路徑負(fù)載均衡，而且考慮了不同負(fù)載對(duì)流量端到端時(shí)延的影響。差分多徑轉(zhuǎn)發(fā)機(jī)制以基于發(fā)送時(shí)延與處理時(shí)延的多徑轉(zhuǎn)發(fā)指標(biāo)DMFI（Differential Multipath Forwarding Index，DMFI）為基礎(chǔ)，將多徑轉(zhuǎn)發(fā)問題轉(zhuǎn)化為0-1整數(shù)線性規(guī)劃問題，并通過差分多徑轉(zhuǎn)發(fā)算法求解出流的轉(zhuǎn)發(fā)路徑集，實(shí)現(xiàn)流低時(shí)延傳輸。

3 時(shí)延感知的差分多徑轉(zhuǎn)發(fā)機(jī)制

本文提出的方案增加了對(duì)處理與發(fā)送時(shí)延的感知能力，提出了一種時(shí)延感知的差分多徑轉(zhuǎn)發(fā)機(jī)制。首先，通過時(shí)延分析得出DMFI指標(biāo)，用以優(yōu)化各路徑選擇。然后，將路徑選擇問題轉(zhuǎn)化為0-1整數(shù)線性規(guī)劃問題，采用差分多徑轉(zhuǎn)發(fā)算法求出流的轉(zhuǎn)發(fā)路徑集。該方法可以有效地減少收斂時(shí)間和端到端時(shí)延。

3.1 時(shí)延感知分析

通過時(shí)延感知分析，確定差分多徑轉(zhuǎn)發(fā)指標(biāo)DMFI，用以優(yōu)化路徑選擇。在時(shí)延分析上，本文將從幀的傳輸過程的分析。根據(jù)圖1中TSN交換機(jī)內(nèi)部結(jié)構(gòu)圖，可以將TSN中的時(shí)延組成解析出來。數(shù)據(jù)幀在經(jīng)過TSN交換機(jī)時(shí)，需經(jīng)歷(a)轉(zhuǎn)發(fā)處理、(b)排隊(duì)等待、(c)發(fā)送數(shù)據(jù)幀三個(gè)部分。

（1）處理時(shí)延：圖1中的(a)過程，從交換機(jī)接收消息到將消息放入TT隊(duì)列的時(shí)間，交換機(jī)的處理時(shí)延由Ft表示。

（2）排隊(duì)時(shí)延：圖1中的(b)過程，從將數(shù)據(jù)幀放入交換機(jī)傳出端口的隊(duì)列中開始到發(fā)送幀之前的時(shí)間。排隊(duì)時(shí)延取決于端口上的調(diào)度時(shí)刻，在GCL合成時(shí)確定。交換機(jī)端口負(fù)載越大，流量數(shù)越多，調(diào)度時(shí)間Qt也會(huì)越大。

（3）發(fā)送時(shí)延：圖1中的(c)過程，在端口發(fā)送。單個(gè)節(jié)點(diǎn)發(fā)送時(shí)延由Lt表示，并取決于消息的大小和發(fā)送速率。

（4）流量端到端時(shí)延：流量的端到端時(shí)延，包含三個(gè)部分：處理時(shí)延、排隊(duì)時(shí)延、發(fā)送時(shí)延（此處不考慮傳播時(shí)延，傳播時(shí)延與鏈路的物理特性有關(guān)，與負(fù)載大小無關(guān)，此處不加討論）。處理時(shí)延與交換機(jī)的處理能力相關(guān)；排隊(duì)時(shí)延取決于路徑端口上的調(diào)度時(shí)刻，在GCL合成時(shí)確定，與端口的負(fù)載相關(guān)。交換機(jī)端口負(fù)載越大，流量數(shù)越多，排隊(duì)時(shí)間Qt也會(huì)越大。發(fā)送時(shí)延與鏈路帶寬以及數(shù)據(jù)大小相關(guān)，流量端到端時(shí)延用Delay表示，則其計(jì)算方式如（3）式所示。

由公式（3）與上述分析可知，TT流端到端時(shí)延與流量負(fù)載、路徑跳數(shù)、經(jīng)過的節(jié)點(diǎn)數(shù)（等于跳數(shù)）相關(guān)。因此，本文依據(jù)上述分析以增加路徑選擇時(shí)的時(shí)延感知能力，得出了公式（4），并定義為多徑轉(zhuǎn)發(fā)指標(biāo)MFI（Multipath Forwarding Index）。公式（4）的第二項(xiàng)為對(duì)總處理時(shí)延與總發(fā)送時(shí)延的感知處理，并作歸一化處理。Vlink鏈路為發(fā)送速率（帶寬），Vprocess為交換機(jī)節(jié)點(diǎn)處理速度，loadi,j為流量i在鏈路j上的負(fù)載，與公式（1）、（2）不同的是，此處ri,j為流量i選擇在路徑j(luò)上傳輸，hopj表示路徑j(luò)的跳數(shù)。

圖1 TSN交換機(jī)內(nèi)部結(jié)構(gòu)圖

3.2 差分多徑轉(zhuǎn)發(fā)機(jī)制

不同流量負(fù)載之間對(duì)發(fā)送時(shí)延與處理時(shí)延的影響存在差異性，即負(fù)載越大對(duì)處理時(shí)延與轉(zhuǎn)發(fā)時(shí)延的影響越大。因此，為了進(jìn)一步加強(qiáng)對(duì)時(shí)延的感知，本方案加強(qiáng)了負(fù)載較大的流量時(shí)延影響能力。本文在公式（4）的基礎(chǔ)上引入差分因子α，來區(qū)分不同負(fù)載對(duì)時(shí)延的影響程度，并化簡(jiǎn)得到公式（5）。最后將公式（5）定義為差分多徑轉(zhuǎn)發(fā)指標(biāo)（DMFI），作為路徑選擇的依據(jù)。其中，

在數(shù)學(xué)模型的建立上，本文將路徑選擇問題轉(zhuǎn)化為0-1整數(shù)線性規(guī)劃問題，接著提出了一種基于貪心算法的差分多徑轉(zhuǎn)發(fā)算法，實(shí)現(xiàn)對(duì)最優(yōu)路徑集的求解，從而達(dá)到更低的端到端時(shí)延。其中，0-1整數(shù)型線性規(guī)劃數(shù)學(xué)描述如公式（6）、（7）、（8）所示，s公式（6）中的ri,j用以表示流量i是否選擇路徑j(luò)；公式（7）表示每個(gè)流量只能選擇一條路徑；公式（8）為優(yōu)化目標(biāo)。

針對(duì)此問題，本文使用差分多徑轉(zhuǎn)發(fā)算法進(jìn)行求解。由公式（3）、（5）可知，負(fù)載越大的流量對(duì)時(shí)延的影響也將越大。因此，本文通過設(shè)置閾值（平均負(fù)載的大?。﹣砼袛嗖罘忠蜃釉O(shè)置的大小。

算法描述：在對(duì)各路流量的路徑集選擇需遵從兩個(gè)原則。

（1）各流在選擇路徑時(shí)必須滿足Delay小于截止期限。

（2）貪心準(zhǔn)則：由式（3）、（5）可知，負(fù)載越大的流量越適合最短路徑，因此將流量按負(fù)載從大到小的順序排列，路徑根據(jù)跳數(shù)從小到大排列，優(yōu)先給負(fù)載最大的流量安排路徑；選出流量i的路徑時(shí)，使前i個(gè)流量中DMFI最小，若流量i的負(fù)載大于流量的平均負(fù)載，則，否則，用以加強(qiáng)差分感知。以此類推，每添加一個(gè)流量均計(jì)算出DMFI最小的路徑選擇，直到所有流量選擇完。

按照上述兩種原則，采用貪心的思想，通過計(jì)算（5）式的值，每次選取最小的DMFI值得路徑，直到將所有流量挑選完路徑，輸出各流量的轉(zhuǎn)發(fā)路徑。

算法 1 差分多徑轉(zhuǎn)發(fā)算法

Input: TopMatixs: Network topology；

Traf fi ci: Characters, number of fl ows M；

Output: The path selection set of fl ows PATH。

1）Pathi = KSP (traf fi ci, TopMatixs); //采用刪除法求得；

流量i前K條最短路徑；

2）Combine paths with inclusion relationships ;

3）Compute and rank the load, number setting M;

4）Compute the average of the flow load AverageLoad;

5）FOR (i =1, i ++, i < M);

6）FOR (j = 1, j ++,j < N);

7）Compute the delay of fl ow i in path j,

Tt = Ft + Lt ;

8）IF (Tt > deadline (i)) THEN;

9）Delete path j in fl ow i ;

10）END IF;

11）END FOR;

12）END FOR;

13）FOR (i = 1, i ++, i < M);

14）Select the corresponding α according to the load, and then calculate the DMFI value;

15）Update the set of PATH (i, j) ;

16）END FOR;

17）Output the PATH 。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

本文在MATLAB上對(duì)上述差分多徑轉(zhuǎn)發(fā)機(jī)制進(jìn)行了實(shí)現(xiàn)，并與最短路徑轉(zhuǎn)發(fā)方案、負(fù)載均衡轉(zhuǎn)發(fā)方案、Hop Load轉(zhuǎn)發(fā)方案[11]進(jìn)行對(duì)比。實(shí)驗(yàn)的總交換結(jié)點(diǎn)數(shù)為5個(gè)，每個(gè)節(jié)點(diǎn)可連接5臺(tái)主機(jī)，可視為工業(yè)系統(tǒng)的終端設(shè)備或者控制器。考慮路徑選擇的多樣性，實(shí)驗(yàn)網(wǎng)絡(luò)選擇如圖2[13]所示，具有較強(qiáng)冗余性的網(wǎng)絡(luò)，圖中鏈路帶寬設(shè)置為100 Mbit/s，節(jié)點(diǎn)處理速度為2 ns/bit，如表2所示。

本實(shí)驗(yàn)以TSN在工業(yè)網(wǎng)絡(luò)中的應(yīng)用為例，采用工業(yè)網(wǎng)絡(luò)中的TT流的屬性特點(diǎn)。工業(yè)網(wǎng)絡(luò)中TT流主要包含為控制流，而不同終端應(yīng)用產(chǎn)生的控制流大小以及周期又存在著差別，為了充分模擬現(xiàn)實(shí)中的工業(yè)網(wǎng)絡(luò)的環(huán)境，設(shè)置了四種類型[12]控制流來組成TT流，其具體的流量特征如表1所示。

圖2 網(wǎng)絡(luò)實(shí)驗(yàn)拓?fù)?/p>

4.2 性能評(píng)價(jià)指標(biāo)

為了客觀反映不同方案的實(shí)際效果及不同參數(shù)對(duì)差分多徑轉(zhuǎn)發(fā)機(jī)制的影響，本文定義了性能指標(biāo)。

（1）TT流量端到端平均時(shí)延

即將各流量到達(dá)目的地的時(shí)間求和，再除以總流量數(shù)可得流量端到端平均時(shí)延，這是反映出TSN的低時(shí)延性的重要指標(biāo)。

（2）可調(diào)度性

可調(diào)度性[12]是指在網(wǎng)絡(luò)中能夠調(diào)度成功的流量個(gè)數(shù)與需要調(diào)度的流量個(gè)數(shù)之比，即用來評(píng)估路徑選擇對(duì)后續(xù)流量調(diào)度的影響。

表2 實(shí)驗(yàn)參數(shù)的設(shè)置

（3）最大鏈路負(fù)載率

最大鏈路負(fù)載率Umax是衡量多徑轉(zhuǎn)發(fā)算法能否可能保障網(wǎng)絡(luò)鏈路負(fù)載均衡的重要指標(biāo)，是指單位時(shí)間內(nèi)通過的數(shù)據(jù)量與可以鏈路通過的數(shù)據(jù)量之比。

4.3 仿真結(jié)分析

仿真結(jié)果分為3種指標(biāo)，每種指標(biāo)對(duì)應(yīng)比對(duì)4種方案。4種方案分別是最短路徑轉(zhuǎn)發(fā)方案、負(fù)載均衡轉(zhuǎn)發(fā)方案、HopLoad轉(zhuǎn)發(fā)方案、差分多徑轉(zhuǎn)發(fā)方案。本文將針對(duì)不同的方案在不同的指標(biāo)下，將逐個(gè)進(jìn)行分析。

如圖3所示，為TT流端到端平均時(shí)延的對(duì)比。如實(shí)驗(yàn)結(jié)果所示，Hop Load轉(zhuǎn)發(fā)方案平均時(shí)延是比負(fù)載均衡方案的低8.43%左右。差分多徑轉(zhuǎn)發(fā)方案的TT流端到端平均時(shí)延比負(fù)載均衡轉(zhuǎn)發(fā)方案與Hop Load方案要低，通過計(jì)算本文提出的方案比負(fù)載均衡方案減少了22.55%，比Hop Load方案減少了17.32%。

圖3 TT流端到端平均時(shí)延比較

表1 流量參數(shù)的設(shè)置

因此可知，差分多徑轉(zhuǎn)發(fā)方案所需平均時(shí)延最短。差分多徑轉(zhuǎn)發(fā)方案相比最短路徑轉(zhuǎn)發(fā)方案，可以同時(shí)有多兩條路徑端口參與轉(zhuǎn)發(fā)，隊(duì)列長(zhǎng)度大大減小。從另一角度看，多路徑轉(zhuǎn)發(fā)可理解為并行轉(zhuǎn)發(fā)，而最短單路徑則為需等待更多時(shí)間的串行發(fā)送。而相比于差分多徑轉(zhuǎn)發(fā)方案，負(fù)載均衡轉(zhuǎn)發(fā)方案沒考慮跳數(shù)對(duì)時(shí)延的影響導(dǎo)致時(shí)延較高，HopLoad轉(zhuǎn)發(fā)方案則是沒考慮到不同流量負(fù)載在不同路徑上對(duì)時(shí)延的影響，導(dǎo)致時(shí)延過高。

如圖4所示，是不同轉(zhuǎn)發(fā)方案的可調(diào)度性比較。從圖4中可以看出，最短路徑轉(zhuǎn)發(fā)方案的可調(diào)度性最低。這是由于隨著流量數(shù)的增加，會(huì)導(dǎo)致過度使用鏈路從而違反流量調(diào)度中的時(shí)隙不沖突約束和最大端到端時(shí)延約束，導(dǎo)致調(diào)度失敗。而差分多徑轉(zhuǎn)發(fā)與負(fù)載均衡轉(zhuǎn)發(fā)方案則是通過在不同路徑上發(fā)送TT流，以解決單條鏈路的瓶頸問題。在圖4中，顯示差分多徑轉(zhuǎn)發(fā)、負(fù)載均衡轉(zhuǎn)發(fā)的可調(diào)度性與Hop Load轉(zhuǎn)發(fā)方案差別不是很大，具有相似的可調(diào)度性。

圖4 TT流可調(diào)度性比較

如圖5所示，是最大鏈路負(fù)載率，其是用以評(píng)判鏈路是否負(fù)載均衡的標(biāo)準(zhǔn)之一。從圖中可以看出，使用負(fù)載均衡的方案其最大鏈路負(fù)載率是優(yōu)于差分多徑轉(zhuǎn)發(fā)方案。其中，主要原因是其以最大鏈路負(fù)載率為指標(biāo)進(jìn)行路徑選擇的，而在差分多徑轉(zhuǎn)發(fā)方案則更多的考慮了時(shí)延因素。其實(shí)際表現(xiàn)為傳輸時(shí)延較短的路徑轉(zhuǎn)發(fā)的流量會(huì)較多點(diǎn)，進(jìn)而導(dǎo)致多路徑有差分轉(zhuǎn)發(fā)最大鏈路負(fù)載率提高。因此，本文提出的方案是在犧牲部分負(fù)載均衡能力的前提下，為TT流提供更低平均端到端時(shí)延。

圖5 最大鏈路負(fù)載率

5 結(jié)束語

為了實(shí)現(xiàn)TT流在TSN中的低時(shí)延傳輸，本文對(duì)TT流在TSN中的傳輸過程進(jìn)行了分析，確定了影響流量端到端傳輸時(shí)延的因素?；诎l(fā)送時(shí)延與處理時(shí)延的多徑轉(zhuǎn)發(fā)指標(biāo)DMFI成為TT流路徑選擇的依據(jù)。將多徑轉(zhuǎn)發(fā)問題轉(zhuǎn)化為0-1整數(shù)線性規(guī)劃問題，并通過差分多徑轉(zhuǎn)發(fā)算法求解出流的轉(zhuǎn)發(fā)路徑集進(jìn)行路徑選擇。仿真結(jié)果顯示：與負(fù)載均衡多徑轉(zhuǎn)發(fā)和Hop Load轉(zhuǎn)發(fā)機(jī)制相比，提出的方案使時(shí)間觸發(fā)流端到端平均時(shí)延分別降低了22.55%和17.32%。未來研究工作包括解決貪心算法局部最優(yōu)問題的啟發(fā)式算法研究、時(shí)間觸發(fā)流的最壞有界時(shí)延分析等。