面向時間觸發流的時延感知差分多徑轉發機制

譚兵，蔡岳平，姚宗辰

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

1 引言

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

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

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

2 TT流路徑選擇的研究現狀與分析

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

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

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

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

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

3 時延感知的差分多徑轉發機制

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

3.1 時延感知分析

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

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

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

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

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

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

圖1 TSN交換機內部結構圖

3.2 差分多徑轉發機制

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

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

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

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

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

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

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

算法 1 差分多徑轉發算法

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上對上述差分多徑轉發機制進行了實現，并與最短路徑轉發方案、負載均衡轉發方案、Hop Load轉發方案[11]進行對比。實驗的總交換結點數為5個，每個節點可連接5臺主機，可視為工業系統的終端設備或者控制器。考慮路徑選擇的多樣性，實驗網絡選擇如圖2[13]所示，具有較強冗余性的網絡，圖中鏈路帶寬設置為100 Mbit/s，節點處理速度為2 ns/bit，如表2所示。

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

圖2 網絡實驗拓撲

4.2 性能評價指標

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

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

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

（2）可調度性

可調度性[12]是指在網絡中能夠調度成功的流量個數與需要調度的流量個數之比，即用來評估路徑選擇對后續流量調度的影響。

表2 實驗參數的設置

（3）最大鏈路負載率

最大鏈路負載率Umax是衡量多徑轉發算法能否可能保障網絡鏈路負載均衡的重要指標，是指單位時間內通過的數據量與可以鏈路通過的數據量之比。

4.3 仿真結分析

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

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

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

表1 流量參數的設置

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

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

圖4 TT流可調度性比較

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

圖5 最大鏈路負載率

5 結束語

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