基于負載均衡的大規模TTE消息調度表生成方法

葉 帆，陳銀超，王 濤，季袁冬，羅懋康,3，江秀強

(1.四川大學空天科學與工程學院, 成都 610207；2.航空工業成都飛機設計研究所，成都 610073；3.四川大學數學學院，成都 610064)

1 引 言

分布式航電系統在航空航天領域具有廣闊的應用前景[1,2].此類系統要求機載網絡必須具備高實時性、高容錯性、高確定性及高帶寬等特性.時間觸發以太網(Time-Triggered Ethernet, TTE)被認為是未來機載網絡的理想解決方案[2,3].時間觸發以太網基于全局同步的時鐘協議實現高確定性、高實時性的時間觸發通信，并根據離線確定的靜態通信調度表來傳輸時間觸發消息.當前，針對TTE調度表生成方法雖然已有較多的研究，但尚未形成統一標準，仍需深入研究[4,5].

針對機載網絡的大規模數據調度需求，本文研究TTE消息的路徑規劃和調度方法.文獻[6-9]設計了基于不同規則的靜態優先級調度方法.這些方法大多采用TTE現有的AS6802標準[2]給出的星型、雪花型拓撲，消息路徑唯一，且使用最短路徑策略生成消息路徑，規則確定、復雜度低，對大規模消息調度問題可行性好、計算時間也少，但是，這些方法沒有考慮到多徑及端系統規模超過50個[8]的復雜拓撲等情形，在實際應用中容易出現因最短路徑上的負載過大而造成消息阻塞的問題，無法進行后續的時序調度.

負載均衡在路徑規劃和時序規劃問題中的應用越來越多[10-13].文獻[10]構建了一個考慮負載的路徑代價函數，利用深度優先搜索算法尋找最小代價值的路由.文獻[11]基于K最短路徑(K shortest paths, KSP)算法計算各業務的備選路徑，在保證待選路徑的較優性的前提下利用遺傳算法優選出盡可能使全網負載均衡的業務路徑組合.文獻[12]則研究了時間觸發(Time-Triggered, TT)流量路徑規劃和時序規劃對速率受限(Rate Constrained, RC)流量實時性的影響，并根據KSP算法和鏈路最大負載最小的原則進行路徑規劃.但是，就我們所知，能夠服務于大規模數據傳輸需求和負載均衡要求的機載網絡的高效數據調度方法還未出現，有待進一步研究.

針對復雜拓撲條件下機載網絡的大規模數據高效傳輸問題，本文提出了一種基于負載均衡思想的TTE消息調度表生成方法.該方法主要有以下幾個特點：

(i)考慮了復雜網絡拓撲.與星型網絡及雪花型網絡等相比，本方法中的消息路徑并不唯一；

(ii)考慮了消息長度的影響.相比單個時隙傳輸，本方法具有更好的實時性；

(iii)設計了基于負載均衡和靜態優先級的調度分配方法.

此外，本方法具有較低的算法復雜度，適用于對大規模消息數據進行高效地時序規劃.

2.1 TTE消息傳輸

TTE支持三種類型的流量在網絡中傳輸，即TT流量, RC流量和盡力而為(Best-Effort, BE)流量[2-6].針對機載網絡的實際需求，本文僅考慮TT流量的傳輸.TT流量根據各網絡節點所加載的靜態調度表中預定義的時間進行傳輸，由全局同步時間觸發，具有確定的延遲和抖動.該流量常被用于具有嚴格確定性和實時性要求的情形，能夠滿足未來機載網絡對大規模數據傳輸確定性和時效性的需求.

時間觸發以太網在空間和時間維度上調度網絡流量，使得網絡具有確定性，即確定數據包何時在何鏈路上傳輸，以及何時最終到達其目的端口.這種調度在空間維度上體現為路徑規劃，需要為每個數據包找到一條合適的路由，即由鏈路和交換機組成的網絡路徑；在時間維度上是時序規劃，需要沿著每個數據包路由的鏈路分配時隙(slot)，每個時隙僅保留用于所配置幀的傳輸.具體的傳輸過程如圖1所示.

路徑規劃需要確定消息傳輸所經過的網絡節點.在圖1中，Sender為發送端，Switch為交換機，Receiver為接收端.此外，還有兩條消息，其中淺灰色的TT消息周期為2ms, 從Sender1傳輸到Receiver，傳輸路徑為

Sender1→Switch1→Switch3→Receiver，

深灰色的TT消息周期為3ms，從Sender2傳輸到Receiver，傳輸路徑為

Sender2→Switch2→Switch3→Receiver.

消息在數據流鏈路上傳輸過程中的時序規劃就是確定消息間的先后順序.在圖1中，兩個TT消息(深灰色和淺灰色所示)同時在Switch3到Receiver的鏈路上傳輸，消息間的先后關系以它們的集群周期為基準.因為淺灰色TT消息和深灰色TT消息的周期分別為3 ms和2 ms，其集群周期，即消息周期的最小公倍數(least common multiple, LCM)為6 ms.因此，可以根據消息傳輸的開始時刻與集群周期的開始時刻間的時間間隔的長短來衡量消息的先后.

圖1 TT消息傳輸示意圖

2.2 TTE消息調度模型

與傳統的星型及雪花型網絡拓撲不同，實際的機載網絡規模大、拓撲結構復雜.為了驗證大規模、非單一路徑網絡拓撲下的算法性能，本文以TTE多跳網絡拓撲[13]為基礎，將三組多跳網絡拓撲互聯組合形成如圖2所示的TTE多跳互聯網絡.該網絡中有終端系統(End System, ES)及網絡交換機(Network Switch, NS)這兩種節點角色，各節點之間通過全雙工鏈路進行連接.在圖2中，ES與NS之間的雙向箭頭代表矩形中各ES與NS之間均存在全雙工鏈路，只不過為了表示清晰在此簡化為一條雙向箭頭.在各個節點中，算法將加載離線生成調度表.根據調度表中的派發時刻和接收時刻, 算法對TT消息進行傳輸，轉發行為只允許發生在網絡交換機中，全雙工鏈路允許雙向通信.

圖2 TTE多跳互聯網絡拓撲

將網絡模型建模為有向圖G=[V,L]，其中V為網絡節點集合，V=ES∪NS，L為網絡中數據流鏈路的集合.數據流鏈路是兩個節點間的定向通信連接，lpk=[vp,vk]∈L，vp,vk∈V.

定義網絡拓撲矩陣G，

(1)

其中，存在vi,vj∈V，使得當數據流鏈路lij存在時網絡拓撲矩陣元素Gij值為1，當數據流鏈路lij不存在時網絡拓撲矩陣元素Gij值為0.

定義集群周期為消息周期的最小公倍數.由于TT消息均為周期性消息，調度過程隨LCM呈現周期性重復.因此，本文所討論的調度表生成問題只考慮一個LCM內的消息調度即可.

TT消息幀格式符合ARINC 664p7規范，消息通過幀的有效載荷進行傳輸.本文假設所有TT消息為周期性消息，且不考慮打包和分段.將TT消息建模為如下的6元組形式，通過該6元組能夠完整描述TT消息的傳輸行為：

mi={mi.period,mi.length,mi.source,mi.dest,

mi.path,mi.offset}

(2)

其中mi.period表示消息周期對應的時間長度，mi.length表示消息長度引發的傳輸時間對應的時間長度，mi.source表示消息傳輸源節點，mi.dest表示消息傳輸目的節點，mi.path表示消息傳輸路徑，為數據流鏈路的有序序列，mi.offset表示消息相對集群周期起始時間的偏移量.為了將時序規劃問題簡化為整數規劃問題，我們使用時隙[5]作為調度表的時間單位對消息的周期和消息傳輸時間進行整數化處理，使得mi.period為消息周期對應的時隙數，mi.length為消息長度引發的傳輸時間對應的時隙數.

本文主要考慮如何以確定性的優化規則分配大規模消息數據的傳輸路徑和傳輸時隙.為了研究方便，并結合實際應用[2-6]，我們作如下的假設：

(i)網絡中所有消息都為周期性的TT消息；

(ii)網絡中所有鏈路資源都可用，交換機采用存儲轉發方式；

(iii)只考慮TT消息單播的情形；

(iv)調度表設計時以時隙為單位對消息周期、消息傳輸時間進行化整；

(v)假設網絡中每次發送的TT消息都能封裝在一個幀里，且一個幀只傳輸一條消息，不考慮幀的打包和分段.

3 基于負載均衡的調度表生成方法

網絡消息的路徑規劃過程根據消息的源節點mi.source，目的節點mi.dest和網絡拓撲G確定各個消息的傳輸路徑mi.path.該路徑為數據流鏈路的有序序列{l1,l2,…,ln}，具體實現過程如圖3所示.首先，我們使用Yen’s KSP算法[14]生成各個消息的待選路徑集合，然后根據規則對消息進行排序，最后按照排序順序依次為消息從待選路徑集合中選擇網絡鏈路最小負載最小的路徑，加入規劃路徑集合.

圖3 路徑規劃流程圖

3.1.1 負載計算公式 定義數據流鏈路lkp上的負載B的計算公式為

(3)

其中，mi.path為消息傳輸路徑，mi.period為消息周期對應的時隙個數，mi.length為消息長度引發的傳輸時間對應的時隙個數.網絡最小鏈路利用率Bmin為

(4)

其中k,p為網絡節點vk,vp.

3.1.2 排序規則 生成待選路徑后，為了選出負載均衡的路徑結果，我們首先需要根據規則對消息進行排序.本文考慮消息長度帶來的影響，定義規則為消息長度越長，排序越靠前，優先進行路徑選擇；消息長度越短越靠后，在已選路徑的負載基礎上進行路徑選擇，相同長度的消息按照原本順序進行排序.

3.1.3 選擇過程 為了達到負載均衡的目的，本文選擇使得消息路徑中鏈路最小負載最小的路徑作為路徑規劃的結果.由于某些消息的傳輸任務路徑唯一，導致一些主干鏈路的負載很高且難以緩解，因而設計鏈路最小負載作為路徑選擇的條件能夠關注到較小負載的均衡狀況，以達到負載均衡的目的.

3.2 時序規劃方法

針對大規模消息的調度問題，本文設計了一種靜態優先級調度方法.與智能優化算法相比，該方法的計算時間更少、效率更高.此外，該方法基于規則，因而具有確定性.對于已知傳輸路徑的消息時序規劃問題，調度過程需要確定各個消息在其路徑的各個數據流鏈路中的首個數據幀的偏移量offsetij(第i個消息在路徑第j個數據流鏈路上傳輸時首個消息幀偏移量)，同時還要確定該消息幀傳輸的結束時刻endij，具體過程為：首先根據優先級評估計算公式計算消息優先級，然后按照從小到大的順序對消息進行優先級排序，評估值越小時排序越靠前、優先級越高，最后根據優先級排序依次按照規則對消息進行調度分配.

(i)優先級評估值計算.由于優先級較高的消息將先進行時序規劃，較低優先級消息的排序會受到已規劃消息的影響，因而應使得較難調度的消息先進行時序規劃，較易調度的消息靠后.鑒于單調速率算法[15]已證明，根據消息周期進行優先級排序具有最優性，消息周期越短，本文綜合考慮消息周期與消息長度對優先級排序的影響，消息周期越短，優先級越高，消息長度越長，優先級越高；反之，消息周期越長，消息長度越長，優先級越低.優先級評估值pi的計算公式為

(5)

這樣，優先級評估值pi越小，消息周期越短、長度越長，優先級越高.當消息優先級評估值相同時，按消息原始順序進行排序.

(ii)調度規則.優先級排序后，我們將按照優先級順序對消息進行調度.若該消息為鏈路中首個被調度的消息，則令其集群周期偏移為0，該鏈路中后續消息將與前一個消息“背靠背”排布進行調度.若產生沖突，則令該消息后移一個slot，直到無沖突.若無法消除該沖突，則無法生成調度表.具體規則如(6)～(8)式所示.

endi,j=offseti,j+mi,length

(6)

(7)

(8)

其中offseti,j表示消息i在其路徑中第j個數據流鏈路上的傳輸時刻距離集群周期LCM起始的偏移量，cont(mi.pathj)表示數據流鏈路mi.pathj上已規劃的消息偏移個數，endi,j表示消息i在其路徑中第j個數據流鏈路上傳輸完畢時刻距離集群周期LCM起始的偏移量，delayi,j表示消息i在其路徑中第j個數據流鏈路上傳輸的硬件延遲和排隊抖動，該數據依據實際的網絡物理性能而離線設定.

4 仿真與分析

4.1 仿真設置

路徑和時序規劃仿真實驗的硬件配置CPU為Intel(R)Core(TM)i7-10510U、內存16GB，采用MATLAB R2016a進行編程計算，并利用PyCharm Community Edition 2021.1.1 x64開發平臺進行SMT對比仿真.

仿真采用的網絡拓撲如圖2所示，包含55個端系統和6個交換機，共61個網絡節點，且轉發行為只發生在交換機上.在仿真程序中，該網絡拓撲表示為矩陣G61×61的形式，如式(1)所示，矩陣元素Gij為1時節點i到節點j間存在數據流鏈路lij，矩陣元素為0則表示不存在數據流鏈路.

由文獻[11]，我們設置網絡鏈路的傳輸速率為100 MB/s，并根據TTE幀格式(符合ARINC 664p7)設置幀長為64～1518 B.由文獻[2]，我們設置消息周期為15、25、30、50、75、150 ms，時隙長度為0.5 ms，并據此對消息周期和幀長進行取整計算，可得幀長傳輸時隙為1～3 slot，消息周期時隙為30、50、60、100、150、300 slot.在可達的前提下，令消息端口均勻分布，消息傳輸需求示例如表1所示.

表1 消息傳輸需求

為了驗證本文所提方法的有效性和在時間復雜度方面的性能提升，我們采用傳統的迪杰斯特拉(Dijkstra，DIJ)路徑規劃算法[6,16]和經典的基于滿足性模理論(Satisfiability Modulo Theory, SMT)的時序規劃方法[5]，并與本文所設計的基于K短路徑的負載均衡路徑規劃方法及基于規則的靜態優先級調度(Static Priority Scheduling, SPS)方法綜合，得到四種方法組合，并在不同消息規模下進行對比仿真實驗.這四種方法分別為：DIJ最短路徑算法+SMT時序規劃方法(DIJ+SMT)，基于K短路徑的負載均衡路徑規劃方法+SMT時序規劃方法(KSP+SMT)，DIJ最短路徑算法+基于規則的靜態優先級調度方法(DIJ+SPS)，以及基于K短路徑的負載均衡路徑規劃方法+基于規則的靜態優先級調度方法(KSP+SPS).對四個方法組合在不同消息規模下進行仿真實驗時的具體消息設置參見表2.

表2 仿真實驗消息設置

4.2 仿真結果與分析

4.2.1 仿真結果 我們以表2中第二組消息為例展示本文方法仿真結果，DIJ算法與KSP方法的路徑規劃結果分別如圖4a和4b所示，兩種方法的時序規劃結果如圖5，6所示.圖4展示了部分路徑結果矩陣Path100×5，其中矩陣行元素為調度消息序號，列元素為路徑結果中數據流鏈路排列序號，矩陣中的元素代表了傳輸路徑中數據流鏈路的序號，0代表無鏈路即無路徑.

圖4 路徑規劃結果:(a)DIJ算法路徑矩陣;(b)KSP方法路徑矩陣

可以看出，當消息為1～10時，兩種路徑方法結果相同.這驗證了KSP方法的有效性和正確性.當消息為90～100時，KSP方法的數據流鏈路路徑與DIJ算法不同.我們以第90個消息為例進行分析.DIJ算法的路徑結果為數據流鏈路1傳輸至數據流鏈路97，KSP算法的路徑結果為數據流鏈路53傳輸至數據流鏈路149.由于兩個算法第1個消息的路徑結果均為數據流鏈路1傳輸至數據流鏈路98，因而對于第90條消息而言，KSP算法緩解了數據流鏈路1上的負載.由此，我們可以推斷其他消息的鏈路負載情況，尤其當網絡中鏈路負載不均勻時，DIJ算法中最短路徑的負載難以緩解，更容易出現路徑阻塞的現象.

圖5和6展示了TT消息調度表，表的橫坐標以時隙為單位，表示一個LCM內的消息幀排布情況，縱坐標表示網絡中的數據流鏈路序號，圖中的黑色小矩形代表各消息已被分配的時隙，通過調度表能夠確定消息在網絡中傳輸的路徑和時間順序.

圖5 KSP+SMT時序規劃結果

圖6 KSP+SPS時序規劃結果

由于消息路徑中數據流鏈路上的時隙偏移offset決定了調度表中消息被分配的時隙的位置，因而通過圖7和8中的時隙偏移offset分布直方圖和分布曲線圖可以看出，本文設計的SPS方法因采用了“背靠背”的排布規則，比SMT方法時隙偏移offset分布更加集中，更靠近LCM前端，體現在調度表中消息排列更為緊湊，更好地保證了TT消息傳輸的確定性和實時性.

圖7 時隙偏移分布直方圖

4.2.2 評估指標與分析 調度方法的關鍵評估指標包括：計算時間指標、延時指標和負載指標.

圖8 時隙偏移分布曲線

上述四種方法在不同規模的消息數據下的計算時間的比較結果如表3所示，其中每個單元格里的上下兩個數據分別是路徑規劃時間和時序規劃時間.通過比較可知，路徑規劃方法的計算時間都是多項式級別的，而SMT方法的計算時間呈現指數型增長.當消息規模為496時，SMT方法很難得出結果.SPS方法的計算時間大多較短，且在消息規模為496時計算時間仍遠小于1 s.因此，相比于DIJ+SMT和KSP+SMT方法，KSP+SPS方法能夠有效減少大規模消息的計算時間.雖然DIJ算法耗時比KSP方法少，但當方法流量不均勻時，DIJ算法更容易出現路徑阻塞的現象，導致調度表生成失敗.因此，為了保證調度表生成方法的適應性，KSP+SPS方法比DIJ+SPS方法更適用于復雜拓撲下大規模消息數據傳輸的場景.

表3 計算時間的對比(單位：s)

延時指標包括平均延時Da和平均延時百分比Dap.假設各個消息的傳輸截止時間為其周期.則該指標可通過下面兩式進行計算：

(9)

(10)

其中，消息個數為N，offseti,last為消息傳輸最后一條路徑上的偏移時隙.四種方法在不同規模消息數據下的延時指標比較結果參見表4，可以看到，四種方法的延時百分比相差不大，KSP+SPS方法的表現好于兩種SMT方法，與DIJ+SPS方法基本持平.因此，KSP+SPS方法能夠較好地滿足消息的確定性和實時性需求.

表4 延時指標對比

消息負載指標包括網絡鏈路最大負載BDmax、平均負載BDavg、負載標準差BDsigm和網絡鏈路負載分布直方圖，由于網絡負載之和不變，若鏈路數量相同則平均負載結果相同，為了對比方法效果平均負載和負載標準差的計算剔除了負載為0的鏈路.兩種路徑規劃方法在不同消息規模下的網絡鏈路最大負載、平均負載和負載標準差如表5所示，在消息規模248和496下的鏈路負載分布直方圖對比結果如圖9和圖10所示.

表5 網絡鏈路負載指標對比

由表5中的BDmax數據可知，對于本文研究的拓撲而言，最短路徑方法和負載均衡方法對于網絡鏈路最大負載的影響都很小.這是由于某些消息調度任務的路徑唯一導致一些主干鏈路上的負載難以緩解.但是，通過負載均衡方法能夠緩解路徑不唯一的消息調度任務帶來的負載影響.由表5中的BDavg，BDsigm可以看出，KSP方法的負載平均值和負載標準差均小于DIJ算法.這表明KSP方法平均負載更小且負載分布更為均衡.進一步，由圖9和圖10可以看出，綠色的KSP方法較小負載的頻率分布高于紅色的DIJ算法，紅色的DIJ算法較大負載的頻率分布高于或持平綠色的KSP方法，且DIJ算法中負載為0的鏈路也多于KSP方法.可見, 本文所設計的基于負載均衡的路徑規劃方法均衡負載的效果較為顯著，能夠較好滿足機載網絡中非TT消息傳輸的負載需求.

圖9 鏈路負載頻率分布直方圖(消息數量=496)

圖10 鏈路負載頻率分布直方圖(消息數量=248)

5 結 論

未來的機載網絡拓撲趨于更加復雜、數據量更大，對調度表生成速度及負載可靠性要求更高.本文提出了一種基于負載均衡的TTE消息調度表生成方法，該方法結合消息長度和負載的影響選取負載均衡的路徑規劃結果，根據優先級評估值以“背靠背”原則為基礎計算消息的時間偏移，實現了對負載均衡的路徑規劃與時序規劃問題的聯合求解.在平均負載、負載標準差方面比傳統的DIJ算法提升了10%以上，改善了鏈路的負載均衡狀況.同時，計算效率比SMT方法提升2到3個數量級，而延時指標與傳統方法則在同一個量級，能保證消息傳輸的實時性.

綜上，該方法在改善鏈路負載的同時提高了調度表生成的效率，能夠滿足更高的TT消息實時性和確定性需求，為機載TTE網絡負載均衡和調度表生成提供了一種可行的解決方案.