譚兵，蔡岳平，姚宗辰

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

1 引言

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

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

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

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

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

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

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

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

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

3 時延感知的差分多徑轉發(fā)機制

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

3.1 時延感知分析

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

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

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

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

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

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

圖1 TSN交換機內(nèi)部結構圖

3.2 差分多徑轉發(fā)機制

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

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

針對此問題，本文使用差分多徑轉發(fā)算法進行求解。由公式（3）、（5）可知，負載越大的流量對時延的影響也將越大。因此，本文通過設置閾值（平均負載的大小）來判斷差分因子設置的大小。

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

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

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

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

算法 1 差分多徑轉發(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 仿真實驗與結果分析

4.1 實驗設置

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

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

圖2 網(wǎng)絡實驗拓撲

4.2 性能評價指標

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

（1）TT流量端到端平均時延

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

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

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

表2 實驗參數(shù)的設置

（3）最大鏈路負載率

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

4.3 仿真結分析

仿真結果分為3種指標，每種指標對應比對4種方案。4種方案分別是最短路徑轉發(fā)方案、負載均衡轉發(fā)方案、HopLoad轉發(fā)方案、差分多徑轉發(fā)方案。本文將針對不同的方案在不同的指標下，將逐個進行分析。

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

圖3 TT流端到端平均時延比較

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

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

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

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

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

圖5 最大鏈路負載率

5 結束語

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