TSN網絡下基于網絡周期的流調度方法

林佳爍，王 濤+，王卓薇，詹雙平，成 劍

(1.廣東工業大學 自動化學院，廣東 廣州 510006；2.廣東工業大學 計算機學院，廣東 廣州 510006；3.鵬城實驗室 寬帶通信研究部，廣東 深圳 518055)

0 引 言

時間敏感網絡(time sensitive networking，TSN)是一種新興的確定性網絡傳輸技術，其通過時間同步、路徑計算、資源預留等機制在以太網的基礎上保障網絡中實時業務流的確定性網絡傳輸[1]。不同于其它只能單一傳輸實時數據的時間敏感型網絡技術(如Profinet、EtherCAT、POWERLINK等)，時間敏感網絡支持在同一網絡下混合傳輸非實時業務流數據及實時業務流數據。而保障實時業務流數據的網絡傳輸不被非實時業務流干擾的關鍵機制就是時間同步機制(IEEE 802.1AS[2]，以下簡稱802.1AS)以及門控機制(IEEE 802.1Qbv[3]，以下簡稱802.1Qbv)。

時間同步機制是時間敏感網絡的基石，802.1AS定義了網絡的時間同步協議，保證網絡中的所有設備時鐘都與全局時鐘在一個誤差范圍內同步。而802.1Qbv則在交換機的出口端口處通過門控制列表(gate control list，GCL)對出口隊列進行開和關操作，來實現對網絡數據流的管控。

時間敏感網絡中基于802.1Qbv機制的調度算法大致分為兩種[4]，第一種是離線式調度算法，其一般將網絡建模為一個整數線性規劃問題(ILP)，然后使用SMT(satis-fiability modulo theories)求解器(如Z3等)或線性規劃求解器離線求解[5-7]。第二種是使用啟發式算法來降低算法運行所需要的時間，使得其可以在可接受的時間范圍內在線求解[8，9]。文獻[7]將網絡周期分為多個小的時間槽，然后在每個時間槽里只調度一條實時業務流。盡管這種方法可以有效保證業務流之間的隔離，但也降低了網絡中可調度流的數量。文獻[10]將時間敏感網絡中的流調度問題映射到運籌學領域的作業安排調度問題(no-wait job-shop scheduling，NW-JSP)，然后使用禁忌搜索算法對該問題進行迭代求解。其中，No-wait約束指的是實時業務流在網絡中不會在出口隊列中排隊。但由于其僅假定所有業務流的應用周期都是相同的，難以在實際應用中對具有不同周期的業務流部署。而文獻[5]同樣基于No-wait約束來進行調度，其定義了業務流之間的沖突程度，并在離線調度情況下聯合路徑來進行優化，最終使用ILP來進行求解。文獻[11]針對大規模網絡下采取了類似No-wait約束的傳輸調度方法，其保持門控隊列開關常開并最后使用SMT來求解。

總體而言，No-wait約束的流調度算法可有力保障業務實時性并且其簡單可實現，受到研究人員重點關注，但由于No-wait約束比較嚴格，其可調度的業務流數量受到較大限制；同時，實際場景中動態出現的眾多未知業務流也迫切需要實時在線增量的No-wait約束流調度。如何有效提升TSN中No-wait約束下的流調度能力，包括針對不同周期業務流的支持度、在線增量調度的實時性與容量等性能，是值得深入研究的關鍵問題。

本文首先提出一種基于No-wait約束的多周期業務流在線調度方法，可適用于多周期業務流混合調度的場景。該算法根據網絡流周期的特點，將業務流的宏周期(hyper-cycle)分為多個小的網絡周期，然后使用最早調度原則在線地對網絡業務流進行調度，從而實現多周期業務流的No-wait約束在線實時增量調度。為進一步提升在線調度的容量，根據該在線算法的特點，提出一種基于重合度的離線調度算法，在離線調度場景下使用了禁忌搜索算法以獲得更優的調度結果，提高了剩余可調度空間，為后續的在線調度運行調度奠定良好的基礎。最后，對算法的性能進行實驗分析，并在仿真平臺Omnet++上驗證調度結果的正確性。實驗結果顯示，對于每一條業務流，在線調度算法調度計算耗費時間約為3.98 ms，滿足實時性要求。并且，對離線調度算法的仿真實驗顯示其可以有效解決在線調度無法適用的場景，將網絡的可調度業務流數量提高58%。

1 問題建模

1.1 系統建模

1.1.1 IEEE802.1Qbv模型

圖1展示了時間敏感網絡中一個典型的交換機結構，其支持802.1Qbv標準，在其每個出口端口處，有8個轉發隊列。該交換機根據轉發數據報文中的PCP(priority code point)字段，將數據幀放置入對應的隊列中。然后，通過GCL列表來控制對應的隊列開關。當隊列的狀態是“開”時，隊列中的數據幀能夠被轉發，否則不能被轉發。這種機制可以將實時業務流與非實時業務流隔離到不同的隊列，以實現實時業務流的轉發不受到干擾。并且，通過與時間同步機制進行結合，可以達到對數據流報文逐跳的嚴格精細控制，從而實現數據報文的確定性轉發。

圖1 支持802.1Qbv標準的交換機出口端口架構

1.1.2 網絡模型

本文所使用的符號表示及其意義見表1。給定網絡拓撲G=(V，E)，其中vi∈V表示的是網絡節點，ei=(vi，vj)∈E表示的是網絡中節點之間的鏈路。對于鏈路e∈E，spe表示該鏈路的傳輸速率。

表1 符號表示及其意義對照

對于業務流fi∈F，其中F表示所有業務流的集合，si、di、sizei、pi、ri分別表示該業務流的源節點、目標節點、數據大小、應用周期、轉發路徑。

(1)

1.1.3 網絡周期(基期)

由于網絡中業務流的應用周期不相同，所以設置一個較小的時隙為網絡周期，本文將這個網絡周期稱為基期(base period，bp)，使得所有的業務流的應用周期都為基期的整數倍。此時，將業務流的應用周期與基期的比值稱為RR(reduction ratio)。如圖2所示，基期值為1 ms，兩個業務流Flow0及Flow1的應用周期分別為2 ms和3 ms，則其RR分別為2和3，網絡的宏周期為這兩個應用周期的最小公倍數6 ms。

圖2 網絡周期(基期)、應用周期以及宏周期

1.2 問題描述

時間敏感網絡中的流調度問題是一個NP-hard問題[12]，為了確保實時業務流的確定性網絡服務，對業務流的傳輸有諸多約束條件。本文提出的算法旨在在線求解出滿足約束條件的調度解，該調度解不影響已調度的業務流的傳輸。其包括實時業務流的起始轉發時間，其路由路徑上的交換機的GCL列表配置。其約束條件如下：

約束1：實時業務流fi在其路徑上的鏈路的傳輸窗口不應與其它已分配的窗口沖突，如式(2)所示

?fj∈F，j≠i，?e∈ri

?α∈{k∈N|0≤k

?β∈{k∈N|0≤k

(2)

其中，tIFG表示該出口端口的幀間隙(interframe gap，IFG)，該值為該端口傳輸96個比特所需要的時間。

約束2：傳輸窗口約束：實時業務流fi在鏈路上的傳輸窗口大小應剛好等于其數據大小與鏈路速率的比值，如式(3)所示

?e∈ri，

(3)

約束3：No-wait約束[10]：該約束保證實時業務流fi在網絡中不會排隊，即業務流的隊列時延為0，如式(4)所示

?(u，v)，(v，w)∈ri，

(4)

其中，tprop及tproc分別表示鏈路的傳播時延及交換機的處理時延。

1.3 離線調度與在線調度

根據TSN網絡部署過程的不同，可以將流量調度問題分為離線調度與在線調度。離線調度與在線調度的不同在于，離線調度問題中所有的業務流都是已知的，而在線調度中，未來所要調度的業務流是未知的。一個典型的離線調度例子是，在一個新的工廠中根據已有的設備及裝配流程來規劃TSN網絡的部署及調度。由于工廠的設備以及對應的應用都是已知的，可以在離線狀態下計算出一個較優的調度方案。而在線調度可以認為是在現有的TSN網絡增加額外的設備及應用，此時調度新的業務流不應對原有的實時應用造成影響。在耗費時間方面，離線調度允許較長的計算時間，而在線調度所允許的計算時間較短。

在實際的TSN部署中，大多數情況下設備及應用是已知的，從而可以使用離線調度來進行計算，并進行部署。在本文中，考慮混合調度，其指的是在該已部署的網絡下新增業務流，所以在這種情況下，需考慮離線調度所計算出的調度方案性能。

2 基于No-wait約束的在線流調度方法

本文所提出的基于No-wait約束的在線流調度方法是一種在線的增量式調度算法，其旨在在線地為實時業務流計算出調度結果，即該業務流在源節點的起始發送時間以及其轉發路徑上交換機的GCL列表。

該算法運行流程如圖3所示，首先在初始化階段設置基期值及網絡拓撲，然后進入在線計算階段。對于每個輸入的實時業務流，首先使用最短路徑算法(如Dijkstra算法等)計算該業務流的最短路徑，然后使用最早調度算法(見下文2.2節)計算該業務流的調度結果。若調度成功，則更新網絡的GCL列表，否則停止算法運行。

圖3 算法運行流程

2.1 基期值設置

在該算法中，設置了一個基期，使得所有業務流的應用周期都是該基期的整數倍(見1.1.3節)，然后將實時業務流盡可能地分散調度到各個基期中，來提高可調度流的數量。由于在線運行算法時，未來輸入的業務流特征是不可知的，這就要求該基期的值設置得足夠小，使得其可以被所有未來可能出現的業務流的應用周期整除。

另一方面，基期值又不應設置得過小。這是因為，過小的基期值會導致調度結果過于分散而出現大量時隙碎片，減小了解空間，最終導致可調度流的數量降低。

所以，基期值應剛好設置為可能出現的所有業務流應用周期的最大公約數。在這種情況下，能夠取得最大的流調度數量。

2.2 盡早調度算法

本文所提出的算法旨在在線增量式地求解出調度結果，這就要求新調度的業務流不能干擾已調度的業務流，即已預留的時隙不應被更改。

在該算法中，應將業務流盡可能地調度分散到各個網絡周期中，并且將業務流盡早調度到其網絡周期的前部。這是由于未來所輸入的實時業務流是不可知的，若流的調度過于集中，則可能會導致當需要調度的實時業務流周期太小而無法調度。并且，當每次對新業務流進行調度時，盡管無論調度結果如何，總的剩余可調度時隙都是一樣的，但是應可能地使每個基期的剩余可調度時隙更大，即，應將總的剩余可調度時隙盡可能地分散到各個基期中，從而提高未來網絡的可調度性。

圖4展示了一個案例，其中有3個業務流Flow0～Flow2，RR(應用周期與基期的比值)分別為2/2/1。此時網絡中已調度了業務流Flow0。當要調度新的數據流Flow1時，方案(a)與方案(b)都是可行的。然而，如果使用方案(a)，將會導致調度結果過于集中，這減小了未來的調度問題解空間。例如，當此時有RR為1的實時流Flow2要調度計算時，若采用方案(a)，無論將Flow2放在何處都無法滿足約束；而方案(b)因為其對Flow0及Flow1的調度較為分散而能夠正常對Flow2進行調度。

算法偽代碼如算法1所示，當調度新實時業務流時，首先根據新的流應用周期來更新宏周期(見算法第(3)行，其中lcm函數是求最小公倍數運算)，并計算該流的RRi。然后，在其RRi周期內計算其最早的調度時間offset，其結果應滿足約束條件式(1)～式(4)。最后選擇這RRi周期內最早調度時間作為調度結果。當該業務流在其所有RRi周期都無法調度時，算法停止。此時網絡資源已不足以為該業務流預留時隙。

盡管該算法只輸出了實時業務流在源節點的起始傳輸時間，但這已足夠得到該流在網絡中各節點的傳輸窗口。這是因為在No-wait約束下，業務流數據幀在網絡中不會排隊，所以，當確定了實時業務流的起始傳輸時間，就可以根據式(4)計算出該業務流在其轉發路徑上的每一跳所需預留的時延窗口。

算法1：最早調度算法

輸入：實時業務流fi

輸出：起始傳輸時間start_time

(1) cycle_idx =-1

(2) offset = +∞

(3) hyper-cycle = lcm(hyper-cycle,pi)

(4) RRi= hyper-cycle/pi

(5) for i in range(RRi):

(6) tmp = 計算fi在基期i的最早調度時間

(7) if tmp >bp then//在該基期i無法調度

(8) continue

(9) if tmp

(10) offset = tmp

(11) cycle_idx = i

(12) if offset == 0 then

(13) break

(14) return cycle_idx * bp +offset

另外，若該算法能夠求解出調度結果，則其一定能滿足業務流的最差時延要求，否則，表明此時網絡資源已不足以調度新實時業務流。這是因為，影響業務流時延的最大因素是其在網絡中的隊列時延，而在該算法中，首先為該業務流計算出的路徑是最短路徑，并且，在后續的調度計算過程中，引入了No-wait約束，該約束又保證了業務流在網絡中不會排隊，所以使用該算法可以保證為該業務流計算出的調度結果端到端時延是最低的，其一定能滿足流的最差時延約束。

3 基于重合度的離線流調度算法

在上文中，由于需要調度不同周期的業務流，引入了網絡周期的概念，并且，上文所述的在線調度算法分散地將業務流調度到各個基期中以使得剩余可調度空間最大。而在離線調度情況下，由于無需滿足調度計算的實時性要求，可以在上一章節所述在線算法的基礎上進行改進，從而在離線調度情況下獲得較優解。在本章中，提出一種基于重合度的離線式調度算法，其使用禁忌搜索算法來對業務流進行調度。具體地，其嘗試以不同順序對業務流進行調度，來提高調度結果的重合度，增大網絡剩余的可調度空間，以使得算法在在線調度時可以調度更多的業務流。

3.1 重合度

為了衡量調度結果的好壞，對于每一個鏈路e，定義了一個已調度空間指標me，來表示該鏈路的調度結果在每一個基期的偏移的并集的時隙長度，該指標的值越小，說明調度結果重合度越高，則調度方案越優。如式(5)所示

(5)

例如，在圖4中，將方案(a)與方案(b)進行對比。顯然，在方案(b)中，由于Flow0與Flow1在該鏈路的預留窗口偏移一致，也就是說，Flow0與Flow1的預留窗口偏移的并集小于方案(a)中的并集，即mb

本算法使用重合度來作為網絡調度結果評估的重要指標，調度結果的重合度越高，表明該調度方案越優。為了便于計算，對于每一個鏈路e，計算該鏈路每個基期的預留窗口偏移的并集，來作為評判指標，記為已調度空間me。該指標越小，則說明各個預留窗口的重合度越高。對于給定網絡的調度方案，該指標等于網絡中重合度最低(即已調度空間最大)的端口的已調度空間指標，如式(6)所示

mG=max{me}，fore∈G

(6)

對于某一條實時業務流fi，其評判指標為其路徑上的每一條鏈路的重合度的平均值，如式(7)所示

mfi=avg{me}，fore∈ri

(7)

3.2 基于禁忌搜索算法的離線調度算法

在離線模式下，本文使用禁忌搜索算法來對實時業務流進行調度。為了使得算法在后續的在線調度過程中能夠調度更多的業務流，該算法選用已調度空間指標mG(見式(6))來評估算法調度結果的性能，即，最小化網絡鏈路中最大的已調度空間，減小網絡總體的已調度空間，增大網絡的剩余可調度空間。

本算法采用的禁忌搜索算法架構與文獻[10]相似，但在critical flow選擇、以及解的迭代過程有所不同。本文主要闡述這兩個過程，對于其它過程如初始解生成、鄰域生成等，這里不再贅述。

3.2.1 Critical Flow的選擇

傳統的算法一般使用流完成時間，即FlowSpan來定義Critical Flow，其中FlowSpan的含義指的是所有業務流中最慢完成傳輸的流的時間。而在本文中，由于引入了網絡周期的概念，使得業務流在各個網絡周期中都有分布，此時FlowSpan就失去了其原有的意義。在本文中，對于某一個給定的調度方案，采用已調度空間mG來評估調度方案的性能。而對于critical flow，類比于FlowSpan中最晚完成的業務流，其應該是導致已調度空間mG縮小的實時業務流。

本算法根據式(7)來對每一條業務流計算其已調度空間指標，即，該流路徑上的鏈路指標的平均值。然后，根據選擇出的critical flow，在迭代過程中生成對應的鄰域。

3.2.2 當前解的迭代過程

在算法的每一次迭代過程中，都需要對鄰域中的每一個鄰居使用第2章所介紹的在線調度算法進行調度計算，即，按照該鄰居方案的實時業務流調度順序，以此使用算法1進行調度。然后，使用式(6)計算每一個鄰居節點的已調度空間，然后選擇最優的(已調度空間指標最小的)鄰居節點作為當前解，然后繼續迭代，直到超過連續Y次迭代無法找到更優解，停止迭代[10]。

4 實驗與分析

本節對上文所提出算法進行實驗，并將所調度結果在Omnet++仿真平臺上使用NeSTiNg[13]框架驗證算法的有效性。本文所使用算法為C++編寫，仿真環境為Ubuntu 18.04。

本文所采用的仿真網絡拓撲參考了文獻[14]所使用的Medium-mesh網絡拓撲，如圖5所示，其中交換機之間的網絡鏈路速率為1 GE，終端與交換機之間的網絡鏈路速率為100 Mbps。交換機處理時延tproc為1 μs，鏈路傳播時延tprop為1 μs。為保證數據準確性及可靠性，對每次實驗運行了20次，然后計算這20次實驗的平均值，得到實驗的可靠結果。

圖5 仿真網絡拓撲

4.1 在線調度實驗

本節實驗主要驗證在線調度算法在不同實驗設置下能夠調度的業務流數量。具體的實驗流程為，使算法在線運行并隨機地生成不同數據特征的實時業務流(其中源節點與目標節點隨機選取)，當算法無法求解出調度結果時停止運行，得到此時網絡中已調度的實時業務流的數量。

4.1.1 實驗1-1：流周期影響

本實驗主要研究業務流周期大小對可調度流數量的影響。在該實驗中，設置了兩個實驗，其中實時業務流的周期大小設置見表2，流的其它參數設置為：源節點與目標節點隨機選取，數據幀大小設置為100 Bytes。基期值設置為100 μs。

表2 實驗1-1實時流應用周期設置

實驗結果見表3，在該網絡拓撲下，Case 3能夠調度的流數量遠超過其它兩個案例。這是由于Case 3中的實時流應用周期相比Case 1及Case 2較大，而應用周期較大的流占用的時隙資源較小，與其它流的沖突約束(見約束1)較少，容易取得較高的流調度數量。

表3 應用周期對流調度數量的影響

注意到Case 3中的流應用周期為Case 2中的流應用周期的10倍，即，平均來說，Case 3中的每一條流所占用帶寬為Case 2的十分之一。直覺地，那么Case 3所能調度的流的數量應為Case 2的10倍，但實驗結果顯示其能夠調度的流數量卻達到了Case 2的將近20倍。這是由于盡管Case 3中的業務流占用帶寬為Case 2中的十分之一，但是其可以分散到不同的基期中調度，受到的約束較小，相對地，其解空間也相比Case 2大。

4.1.2 實驗1-2：基期大小影響

如2.1節所述，基期值的設置會影響可調度流數量，基期值太小會使得調度結果過于分散，產生大量的時隙碎片而減小了解空間。在該實驗中，維持實時流的流量特征(實驗設置為Case 2)不變，而改變基期值的大小見表4。

表4 實驗1-2基期值設置

對于該實驗設置的業務流，其應用周期的最大公約數是100 μs，由于基期必須整除所有流的應用周期，所以此時基期所能設置的最大值為100 μs。

實驗結果如圖6所示，隨著基期從10 μs到100 μs不斷增大，網絡平均可調度流的數量也不斷增多。當網絡周期達到100 μs時，流調度數量達到最大，達到了最差情況下(Case 4)的176%。

圖6 基期大小對流調度數量的影響

實驗結果顯示，基期大小對網絡可調度性有較大影響。在實際部署中，算法的基期應設置得較大，來保證網絡的可調度性。由于算法是在線運行的，未來的實時業務流數據特征是未知的，此時應估計所可能出現的業務流應用周期的值大小，并將基期值設置為其最大公約數。

4.1.3 實驗1-3：調度計算時間

本文提出了一種在線調度算法，由于算法需要在線運行，所以對實時流調度計算耗費的時間成為了一個重要的指標，本實驗主要研究該算法在在線調度情況下的調度計算時間。

本實驗選取Case3的實時流生成設置，其中數據幀大小為100 Bytes，基期為1 ms。

實驗結果如圖7所示，圖中數據已做平滑處理。隨著已調度流數量的增加，算法調度計算所耗費的時間也呈一個上升趨勢，并且其波動也越大。這是因為當網絡中已調度的實時流數量較多時，對于當前實時流，所受到的約束(見約束1式(2))增多，其所可能受到的沖突也就越多，所以計算次數增加，耗費時間增大。

圖7 流調度耗時

總體來說，對于單條實時業務流，算法調度計算平均只需要3.98 ms的時間，滿足算法在線運行的要求。

4.2 離線調度實驗

本實驗對第3章提出的離線調度算法進行實驗驗證。在該實驗中，首先使用在線調度器對業務流進行在線調度，并不斷生成業務流。當在線調度計算失敗時，改用離線調度器對前面的所有業務流重新進行調度計算。調度成功后，在該調度結果的基礎上，繼續使用在線調度器為后續的業務流進行在線調度。直到離線調度器也無法調度時則停止計算，實驗流程如圖8所示。該實驗可以驗證本文所述離線算法的有效性，并且同時具有實際意義。例如，在實際部署應用中，由于未來增加的業務流是未知的，所以首先使用在線調度算法來進行增量式調度。當在線調度算法已經無法正常調度業務流時，需要對原來的已調度業務流重新進行計算以使得所有業務流都可以得到調度。

圖8 實驗2流程

其中，實時業務流的流量特征見表5，基期大小均設置為100 μs，業務流的幀數據大小在對應范圍內取平均分布。

表5 實驗2實時流設置

實驗結果如圖9所示，可以看到，相比平均僅能調度40條業務流左右的在線調度，離線調度的調度業務流數量平均提高了58%。并且，觀察到使用離線調度成功調度計算的次數為1～2次。即，平均來說，每次使用離線調度器能使得調度流的數量增加29%～58%。這反映了，對于某一條關鍵業務流，該業務流可能受到的約束較多，當在線調度已經無法對其求解出調度結果時，此時使用離線調度可以重新規劃出一個較優的調度結果，從而使得算法可以在線調度更多的業務流，優化效果較為顯著。

5 結束語

本文對時間敏感網絡No-wait約束下的實時業務流調度問題進行研究，提出了一種在線增量式流調度方法，該方法基于網絡周期，可以對不同應用周期的實時業務流進行增量式調度。并且，為了提高網絡的可調度流數量，該算法將調度結果分散到各個網絡周期。然后，提出了一種基于重合度的離線調度算法，在離線模式下，減小調度結果的已調度空間，以增大剩余可調度空間，為后續的在線調度過程提供了良好的基礎，從而提高了業務流的可調度數量。

當前基于No-wait約束實現的調度器由于約束太大，難以調度較多的業務流。在后續研究中，將研究放松No-wait約束來對業務流進行調度，以提高網絡的可調度性能。