HSTC：TSN 中的混合流量調(diào)度機制

尹長川，李妍玨，朱海龍，何欣欣，韓文璇

（1.北京郵電大學(xué)先進(jìn)信息網(wǎng)絡(luò)北京實驗室，北京 100876；2.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876)

0 引言

隨著工業(yè)4.0 時代的到來，工業(yè)生產(chǎn)控制系統(tǒng)智能化程度越來越高，對信息的實時性和確定性傳輸提出了更高要求。為保證系統(tǒng)安全性和靈活性，同一交換設(shè)備必須支持時間敏感流與大帶寬流的混合傳輸。傳統(tǒng)以太網(wǎng)在可擴展性和成本特性等方面具有很大優(yōu)勢[1]，但其并不適合對實時性和安全性有較高要求的應(yīng)用[2]。為保證實時信息的確定性傳輸，目前工業(yè)自動化網(wǎng)絡(luò)中發(fā)展出一系列成熟的解決方案，如EtherCAT、AFDX、EtheReal、Powerlink等主流的現(xiàn)場總線技術(shù)。這些技術(shù)均是對以太網(wǎng)協(xié)議的擴展[3]，并通過各自專用的以太網(wǎng)設(shè)備和技術(shù)標(biāo)準(zhǔn)來實現(xiàn)流量整形，因此很難實現(xiàn)彼此兼容，更無法與傳統(tǒng)IP 以太網(wǎng)互聯(lián)通信，網(wǎng)絡(luò)靈活性較差。IEEE 802.1 時間敏感網(wǎng)絡(luò)（TSN,time-sensitive networking）任務(wù)組致力于將以太網(wǎng)的實時和安全關(guān)鍵機制標(biāo)準(zhǔn)化[4]，從而實現(xiàn)時間敏感流與非時間敏感流在以太網(wǎng)中的混合共存[5-6]，為關(guān)鍵通信提供確定性時延保障。

TSN 作為一種擴展的標(biāo)準(zhǔn)以太網(wǎng)技術(shù)，其可向后兼容標(biāo)準(zhǔn)以太網(wǎng)，從而獲得低時延抖動的高穩(wěn)健通信鏈路。同時，TSN 是一個協(xié)議簇，其包含多個實現(xiàn)不同功能的子協(xié)議。例如，IEEE 802.1 AS[7]提出精確時間協(xié)議（gPTP,general precise time protocol）來實現(xiàn)TSN 全局網(wǎng)絡(luò)的時鐘統(tǒng)一，為確定性的網(wǎng)絡(luò)傳輸提供基準(zhǔn)保障。IEEE 802.1Qbv[8]中定義時間感知整形（TAS,time-aware shaper），通過控制交換機門控列表來實現(xiàn)網(wǎng)絡(luò)中的流量整形。IEEE 802.1Qch[9]中定義了循環(huán)排隊轉(zhuǎn)發(fā)（CQF,cyclic queuing and forwarding）機制，通過循環(huán)切換乒乓隊列實現(xiàn)流量整形，實現(xiàn)了對TAS 機制的簡化。IEEE 802.1Qav[10]提出了基于信用的整形（CBS,credit-based shaper）機制。IEEE 802.1Qcc[11]對TSN的管理和配置進(jìn)行了說明。

流量調(diào)度是保證TSN 系統(tǒng)中信息實時性、確定性傳輸?shù)年P(guān)鍵技術(shù)，研究人員對此進(jìn)行了大量研究探索。為優(yōu)化現(xiàn)有調(diào)度機制的性能，文獻(xiàn)[12]提出驗證網(wǎng)絡(luò)調(diào)度性的方法和門控列表的啟發(fā)式求解算法，以解決TAS 門控列表配置復(fù)雜的問題；文獻(xiàn)[13]通過比較不同數(shù)據(jù)壓縮方法對CBS 機制性能的影響，提出一種TSN 的流壓縮算法，降低了流的端到端時延；文獻(xiàn)[14]提出一種注入時間規(guī)劃算法來調(diào)整流注入交換機的時間，以實現(xiàn)CQF 機制中的全局流量規(guī)劃，并在多種典型的網(wǎng)絡(luò)拓?fù)湎逻M(jìn)行了評估驗證；文獻(xiàn)[15]提出一種動態(tài)的流注入時間調(diào)度算法，充分挖掘基于CQF 機制的TSN 的確定性傳輸能力，根據(jù)網(wǎng)絡(luò)資源利用率調(diào)整網(wǎng)絡(luò)適配器上的發(fā)送時間，實現(xiàn)對網(wǎng)絡(luò)中新時間敏感流的調(diào)度。而目前對TSN 混合調(diào)度技術(shù)的研究多集中于TAS 與CBS 的結(jié)合，例如，文獻(xiàn)[16]以最小化流預(yù)留（SR,stream reservation）流的預(yù)留帶寬為目標(biāo)，引入數(shù)據(jù)包的傳輸時延作為約束，減小了BE（best-effort）流的端到端時延，但相同優(yōu)先級間的流量會產(chǎn)生相互干擾，導(dǎo)致SR 流的預(yù)留帶寬增大，降低系統(tǒng)資源利用率；文獻(xiàn)[17]提出了一種感知的分組加權(quán)循環(huán)策略，根據(jù)子周期長度調(diào)度音視頻橋接（AVB,audio-video-bridging）隊列，減少了AVB 幀的平均調(diào)度間隔，并將整個調(diào)度周期分為一個受保護(hù)的時隙和一個不受保護(hù)的時隙，利用動態(tài)規(guī)劃最小化保護(hù)帶，從而提高帶寬利用率。事實上，相對于CBS，CQF 調(diào)度方案的求解和時延分析更簡單，雖然其調(diào)度粒度較粗，但仍能滿足大帶寬周期流的傳輸需要。因此，若將CQF 與能實現(xiàn)高精度調(diào)度的TAS相結(jié)合，即可在滿足混合流傳輸需求的前提下，降低調(diào)度方案的求解復(fù)雜度。但目前關(guān)于該混合調(diào)度機制的研究仍較少。文獻(xiàn)[18]提出限制TAS 隊列與CQF 隊列不可同時開啟，以實現(xiàn)時間敏感流的零抖動，并降低時間敏感流對其他周期流的影響，但CQF 的雙關(guān)門機制會帶來緩存資源和傳輸帶寬的浪費；文獻(xiàn)[19]對TAS 結(jié)合CQF 的混合傳輸框架進(jìn)行了探究，提出一種參數(shù)選擇方法來確定網(wǎng)絡(luò)的循環(huán)周期和時間調(diào)度單元，以實現(xiàn)減少低時間敏感流的平均時延，但該方案只給出了高時間敏感流的調(diào)度方案，且在確定時間調(diào)度單元時，對于CQF 機制帶給網(wǎng)絡(luò)的約束考慮不夠全面。因此，基于現(xiàn)有研究的不足，本文提出一種將TAS 與CQF 結(jié)合的流量調(diào)度（HSTC,hybrid traffic scheduling combining TAS and CQF）機制，以實現(xiàn)TSN 中混合流的高效調(diào)度。

本文的主要貢獻(xiàn)如下。

1) 提出一種采用HSTC 機制的新型TSN 系統(tǒng)設(shè)計方案，可滿足時間敏感流與大帶寬流的混合傳輸需求，并給出調(diào)度方案的完整求解步驟。

2) 在提出的系統(tǒng)架構(gòu)下設(shè)計確定網(wǎng)絡(luò)最小調(diào)度時隙的方法，并基于該最小時隙調(diào)整預(yù)訂流量（ST,scheduled traffic）流的采樣周期，通過降低ST流對發(fā)送帶寬的占用，為SR 流預(yù)留更多傳輸資源，從而提升網(wǎng)絡(luò)可調(diào)度性。

3) 進(jìn)一步針對SR 流，提出奇偶映射的流映射策略，并且，當(dāng)網(wǎng)絡(luò)中出現(xiàn)SR 流不可調(diào)度的情況時，設(shè)計流偏移規(guī)劃（FOP,flow offset planning）算法，對SR 流的注入時間進(jìn)行偏移調(diào)整，通過提高系統(tǒng)資源利用率，進(jìn)一步提升網(wǎng)絡(luò)可調(diào)度性。

1 預(yù)備知識

TSN 是一個協(xié)議簇，其中包含多種實現(xiàn)不同功能的子協(xié)議，本文關(guān)注的問題是TSN中的流量調(diào)度技術(shù)，并提出一種將現(xiàn)有的TAS 與CQF 結(jié)合的混合流量調(diào)度機制，下面首先對2 種相關(guān)TSN 協(xié)議進(jìn)行介紹。

1.1 IEEE 802.1Qbv

在TSN 中，IEEE 802.1Qbv[8]基于系統(tǒng)時間同步定義了時間感知整形機制，該機制提供基于流量等級的周期性流量調(diào)度，每個隊列優(yōu)先級不同，進(jìn)入交換機的數(shù)據(jù)包根據(jù)幀頭的優(yōu)先級信息，被轉(zhuǎn)發(fā)至相應(yīng)隊列。TAS 機制如圖1 所示，其中，各隊列出口側(cè)都有一個時間感知門，當(dāng)門控編碼為O 時，門開啟，可以發(fā)送數(shù)據(jù)；當(dāng)門控編碼為C 時，門關(guān)閉。當(dāng)多個門同時開啟時，優(yōu)先級選擇器根據(jù)隊列優(yōu)先級由高至低傳輸數(shù)據(jù)包，隊列門控由門控列表進(jìn)行周期性控制。

圖1 TAS 機制

TAS 通過門控列表進(jìn)行流量調(diào)度，控制精度很高，適用于傳輸對時延要求較高的時間敏感流。但隨著網(wǎng)絡(luò)中流數(shù)量的增加，門控列表的計算復(fù)雜度會迅速提升，因此，如何高效求解門控列表是TAS機制需要解決的核心問題。

1.2 IEEE 802.1Qch

IEEE 802.1Qch[9]提出循環(huán)排隊轉(zhuǎn)發(fā)的流量整形機制，該機制可被看作TAS 機制的簡化形式，其同樣需要基于全局系統(tǒng)的精準(zhǔn)時間同步。為降低對時間同步的要求，文獻(xiàn)[20-21]對循環(huán)特定轉(zhuǎn)發(fā)等CQF 的改進(jìn)機制進(jìn)行了研究。

具體地，CQF 機制將2 個出口隊列劃分為一組，通過“乒乓”式的策略，按隊列循環(huán)周期交替開啟2 個隊列的門控，從而實現(xiàn)流量整形。如圖2 所示，奇數(shù)時隙，隊列1 門控打開，可以進(jìn)行傳輸，而隊列2 門控關(guān)閉，只能進(jìn)行數(shù)據(jù)包的接收緩存；偶數(shù)時隙，2 個隊列進(jìn)行狀態(tài)切換。

圖2 CQF 機制

基于上述的存儲轉(zhuǎn)發(fā)機制，當(dāng)采用CQF 機制進(jìn)行流量調(diào)度時，數(shù)據(jù)包在單個交換機內(nèi)部經(jīng)歷的最大轉(zhuǎn)發(fā)時延是確定的，數(shù)據(jù)包的端到端時延僅與其經(jīng)過的交換機跳數(shù)有關(guān)。因此，CQF 機制大大降低了TAS 機制中門控列表帶來的計算復(fù)雜度，且時延抖動很小[22]，但相對于TAS，CQF 的控制精度較低，數(shù)據(jù)包時延較大，并不適合傳輸時間敏感度較高的關(guān)鍵信息。

綜上，本文提出一種將TAS 與CQF 進(jìn)行有機結(jié)合的混合流量調(diào)度機制，該機制在滿足混合流傳輸需求的前提下，降低了調(diào)度方案的求解復(fù)雜度，并通過提高系統(tǒng)的資源利用率，大幅提升了網(wǎng)絡(luò)調(diào)度成功率，實現(xiàn)了TSN 中的高效流調(diào)度。

2 系統(tǒng)模型

2.1 系統(tǒng)架構(gòu)

本文所提混合流量調(diào)度機制的TSN 交換機結(jié)構(gòu)如圖3 所示，其中，系統(tǒng)共有w個流輸入端口，每個輸出端口前有8 個輸出隊列。由于TSN使用IEEE 802.3[1]中虛擬局域網(wǎng)（VLAN,virtual local area network）頭中的PCP（priority code point）字段（0～7）標(biāo)記特定流的優(yōu)先級，因此輸出隊列至多可分為 8 個優(yōu)先級。本文為采用TAS 機制的隊列分配最高優(yōu)先級7，為采用CQF機制的兩組隊列分配優(yōu)先級6 和5，為BE 隊列分配最低優(yōu)先級4，其余2 個隊列可根據(jù)實際情況擴展使用。輸入流經(jīng)過交換結(jié)構(gòu)后，流過濾器根據(jù)PCP 字段將流轉(zhuǎn)發(fā)至相應(yīng)隊列。隊列出口側(cè)采用門控列表控制，當(dāng)多個門控同時打開時，優(yōu)先級選擇器按照隊列優(yōu)先級由高到低將數(shù)據(jù)包轉(zhuǎn)發(fā)至輸出端口。

圖3 TSN 交換機結(jié)構(gòu)

2.2 問題描述

本文將輸入流映射為四類，分別為ST 流、SR_A類流、SR_B 類流及BE 流。其中，ST 流傳輸控制信息、同步信息等時間敏感信息，這些流數(shù)量少且包長短，但對時延和抖動有很高要求，傳輸過程應(yīng)盡可能無等待，因此ST 隊列采用TAS 機制并具有最高優(yōu)先級7。本文假設(shè)網(wǎng)絡(luò)中共有n條ST 流，由文獻(xiàn)[23-25]可知，關(guān)鍵控制流的采樣周期通常在一定范圍內(nèi)可調(diào)，因此在本文中，每條ST 流定義為一個五元組，其中，為流最小采樣周期，為流最大采樣周期，為數(shù)據(jù)包總長度，為流截止時間，PT為流優(yōu)先級，所有ST 流優(yōu)先級都為7。

SR 流是網(wǎng)絡(luò)中傳輸非關(guān)鍵信息的大帶寬周期流，相對于ST 流，其采樣周期大且對時延和抖動的要求低，但往往數(shù)量較多且包長較長。本文假設(shè)網(wǎng)絡(luò)中共有m條SR 流，每條SR 流定義為一個四元組，其中，為采樣周期，為包長，為截止時間（DDL，dealine），為優(yōu)先級，SR 流被劃分為A 類和B 類，優(yōu)先級分別為6 和5。

BE 流為網(wǎng)絡(luò)中盡力傳輸?shù)牧?，無固定周期，本文不考慮BE 流的具體參數(shù)，僅將其優(yōu)先級定義為最低優(yōu)先級4。

為更充分地利用系統(tǒng)資源，提高網(wǎng)絡(luò)可調(diào)度性，實現(xiàn)工業(yè)網(wǎng)絡(luò)中混合流的高效傳輸，本文提出一種結(jié)合TAS 與CQF 的TSN 混合流量調(diào)度機制，在該機制的設(shè)計過程中，主要需解決以下2 個問題。

1) 確定ST 流實際采樣周期

ST 流承載網(wǎng)絡(luò)關(guān)鍵信息，應(yīng)盡可能無等待傳輸，但由于ST 隊列具有最高優(yōu)先級，若多個門控同時打開，當(dāng)且僅當(dāng)ST 隊列為空時，其他隊列才有傳輸機會。若ST 流始終按照最小采樣周期采樣，隨著ST 流數(shù)量上升，大部分傳輸帶寬將被ST 流占用。調(diào)整ST 流采樣周期如圖4 所示，應(yīng)盡可能增大ST 流的實際采樣周期，以降低其帶寬占用，為SR 流預(yù)留更多傳輸資源。圖4 中，Tu為網(wǎng)絡(luò)最小時間調(diào)度單位。

圖4 調(diào)整ST 流采樣周期

2) SR 流規(guī)劃

本文使用兩組不同優(yōu)先級隊列傳輸SR 流，因此如何進(jìn)行合理的流映射是SR 流規(guī)劃中首先解決的問題。

其次，由于系統(tǒng)單位時隙的最大吞吐量以及交換機隊列的最大緩存有限，隨著SR 流數(shù)目增加，僅僅依靠調(diào)整ST 流，難以保證全局流的可調(diào)度性，因此需對SR 流進(jìn)行調(diào)整。SR 流對時延保障要求較低，只需在截止時間前傳輸完成即可，但由于CQF嚴(yán)格的存儲轉(zhuǎn)發(fā)機制，上一時隙到達(dá)交換機的數(shù)據(jù)包必須在下一時隙全部發(fā)送，因此本文對SR 流的調(diào)整方式為時延源節(jié)點處數(shù)據(jù)包的發(fā)送時間，以實現(xiàn)SR 流在交換機處的時延注入。為實現(xiàn)對各源節(jié)點數(shù)據(jù)傳輸?shù)木_控制，本文所提機制均假設(shè)基于集中式軟件定義網(wǎng)絡(luò)（SDN,software defined network）架構(gòu)[26]，即存在集中用戶配置（CUC，central user configuration）實現(xiàn)流拆包、傳輸時間計算以及路由選擇，存在集中式網(wǎng)絡(luò)配置器（CNC,central network controller）來接收流傳輸請求，對網(wǎng)絡(luò)帶寬和時延進(jìn)行監(jiān)控，并實現(xiàn)配置信息下發(fā)。

網(wǎng)絡(luò)拓?fù)浼傲魈匦匀鐖D5 所示。設(shè)圖5 中4 條數(shù)據(jù)流具有相同流特性，最大傳輸單元（MTU,maximum transmission unit）為網(wǎng)絡(luò)最大傳輸幀長，交換機隊列的最大緩存為2MTU。若不對SR 流進(jìn)行注入時間調(diào)整，如圖6 所示，由于交換機緩存溢出，流3 和流4 的所有數(shù)據(jù)包都會被丟棄；若將二者在每個周期均向后偏移一個Tu注入，如圖7所示，則網(wǎng)絡(luò)中所有數(shù)據(jù)包均可成功傳輸。

圖5 網(wǎng)絡(luò)拓?fù)浼傲魈匦?

圖6 未調(diào)整SR 流注入時間

圖7 調(diào)整SR 流注入時間

當(dāng)對SR 流進(jìn)行注入調(diào)整時，除了避免緩存溢出，還需考慮在發(fā)送時刻來自更高優(yōu)先級流的干擾，當(dāng)待發(fā)送數(shù)據(jù)量超過單位時隙的最大吞吐量時，網(wǎng)絡(luò)將發(fā)生丟包。

2.3 網(wǎng)絡(luò)約束

在本文中，對于TSN 中一組給定的流，求解的流調(diào)度方案需滿足以下網(wǎng)絡(luò)約束。

1) 最小時隙約束

由于Tu為最小時間調(diào)度單位，因此所有流周期都必須為Tu的整數(shù)倍，令為所有SR 流周期的最大公約數(shù)，則Tu的最大取值需小于，且Tu的取值范圍為的因數(shù)集L={l1,l2,…,lk}，即

由于ST 流的采樣周期有上下界，因此Tu需大于或等于所有ST 流采樣周期最小值中的最大值，小于或等于所有ST 流采樣周期最大值中的最小值，即

為減少關(guān)鍵流的時延和抖動，本文假設(shè)在某一時隙采樣的ST 流數(shù)據(jù)包需在該時隙內(nèi)全部傳輸完成，即

對于SR 流，由于采用CQF 機制，為保證時延可控，在上一個時隙內(nèi)注入交換機的數(shù)據(jù)包需其在下一個時隙內(nèi)全部轉(zhuǎn)發(fā)，即

其中，BufSize 是交換機單個隊列的最大緩存，B是鏈路傳輸速率，δmax是網(wǎng)絡(luò)中由于時間同步精度等問題引起的最大時延。

2) 門控約束

對于SR 隊列，由于CQF 機制以Tu為門控狀態(tài)切換周期，上一個Tu內(nèi)關(guān)閉的隊列一定在下一個Tu打開，反之亦然。因此，所有SR 隊列的門控周期TCQF均為2T u，即

對于采用TAS 機制的ST 隊列，其門控循環(huán)周期TTAS為所有ST 流實際采樣周期的最小公倍數(shù)，如式(6)所示。

門控列表的總循環(huán)周期TGate為ST 隊列與SR 隊列門控循環(huán)周期的最小公倍數(shù)，即

由于交換機內(nèi)存有限，在一個門控循環(huán)周期內(nèi)，交換機最多可存儲Gatemax個門控事件，因此TGate不能大于Gatemax，即

3) ST 流約束

② 總線占用率約束。為保證網(wǎng)絡(luò)中的流均可調(diào)度，首先需保證在任意單位時隙Tu內(nèi)，ST 流對總線的占用率均不大于1，即

③截止時間約束。本文取的實際采樣周期為其截止時間，則的數(shù)據(jù)包從產(chǎn)生到發(fā)送完成的總時延需小于或等于該流的截止時間，即

對于ST 流，由于所有ST 流具有相同最高優(yōu)先級7，在任意時隙內(nèi)，當(dāng)且僅當(dāng)ST 隊列為空時，其余隊列才能進(jìn)行發(fā)送。此外，在本文約束條件下，任意Tu內(nèi)ST 隊列及SR 隊列內(nèi)待發(fā)送的數(shù)據(jù)包都將在該時隙內(nèi)發(fā)送完成，因此不需要考慮上一時隙發(fā)送的數(shù)據(jù)包對下一個時隙造成的干擾。則對于任意一條ST 流，其時延包括比先進(jìn)入隊列的ST 流數(shù)據(jù)包的傳輸時間、自身數(shù)據(jù)包的傳輸時間。ST 流時延構(gòu)成如圖8 所示，的時延可由式(12)計算得到。

圖8 ST 流時延構(gòu)成

4) SR 流約束

①轉(zhuǎn)發(fā)時延約束。為保證轉(zhuǎn)發(fā)時延可控，CQF機制要求在上一個Tu內(nèi)進(jìn)入隊列緩存的數(shù)據(jù)包必須在下一Tu內(nèi)全部發(fā)送。數(shù)據(jù)包在交換機內(nèi)經(jīng)歷的轉(zhuǎn)發(fā)時延包括兩部分，第一部分為緩存時延，第二部分為傳輸時延。因為門控切換周期為Tu，所以緩存時延和傳輸時延的上界均為Tu。因此，數(shù)據(jù)包在交換機內(nèi)部經(jīng)歷的轉(zhuǎn)發(fā)時延需小于或等于2T u，即

② 最大偏移約束。本文以時刻0 作為計算相對偏移量的參考點，由轉(zhuǎn)發(fā)時延約束可知，SR 流數(shù)據(jù)包的最大轉(zhuǎn)發(fā)時延為2T u，因此的最大注入偏移為其截止時間減去最大轉(zhuǎn)發(fā)時延，即

對于任意一條SR 流，由于采用CQF 機制，其時延包括以下部分：更高優(yōu)先級流的發(fā)送時延，其中包括ST 流及優(yōu)先級高于的其他SR 流；優(yōu)先級與相同，但先進(jìn)入隊列的其他SR 流的發(fā)送時延；交換機緩存時延；數(shù)據(jù)包的發(fā)送時延。本文假設(shè)入隊速率遠(yuǎn)大于出隊速率，因此所有SR 流數(shù)據(jù)包在交換機中的緩存時延均為Tu。令hp(i)表示所有優(yōu)先級高于的流合集，sp(i)表示所有優(yōu)先級與相同的流合集。SR 流時延構(gòu)成如圖9 所示，則的時延可由式(16)計算得到。

圖9 SR 流時延構(gòu)成

本文的研究問題為如何在滿足以上所有約束的前提下，實現(xiàn)對TSN 流調(diào)度方案的高效求解。為評估所提方案性能，本文采用網(wǎng)絡(luò)調(diào)度成功率SRate[27]作為性能衡量指標(biāo)，該指標(biāo)表示當(dāng)滿足網(wǎng)絡(luò)的全部約束條件時，可成功求解出網(wǎng)絡(luò)調(diào)度方案的仿真實驗次數(shù)ns與總實驗次數(shù)nall的比值，即

3 HSTC 機制

本文所提的HSTC 機制可分為以下兩部分。

1) 根據(jù)網(wǎng)絡(luò)約束，確定網(wǎng)絡(luò)最小時隙Tu，并調(diào)整ST 流的采樣周期，降低ST 流對總線的占用，為SR 流預(yù)留更多傳輸資源，提高網(wǎng)絡(luò)調(diào)度成功率。

2) 對SR 流進(jìn)行規(guī)劃。首先，采用奇偶映射的方法將SR 流映射為SR_A 類及SR_B 類；其次，當(dāng)經(jīng)過ST 流采樣周期調(diào)整后，網(wǎng)絡(luò)狀態(tài)仍為不可調(diào)度時，采用FOP 算法對SR 流進(jìn)行注入偏移調(diào)整，進(jìn)一步提升網(wǎng)絡(luò)可調(diào)度性。

3.1 確定 Tu 調(diào)整ST 流采樣周期

由網(wǎng)絡(luò)約束可知，Tu與流屬性、鏈路速率、交換機緩存大小、最大門控數(shù)量等因素有關(guān)，而TAS的控制精度與Tu成反比，因此需在滿足所有網(wǎng)絡(luò)約束的前提下，求解網(wǎng)絡(luò)最小時隙，以盡可能提升TAS 的控制精度。其次，由ST 流的采樣周期約束可知，對于ST 流，其實際采樣周期上界為k iTu，Tu越小，k iTu接近理想采樣周期上界的可能性越大，則當(dāng)對所有ST 流進(jìn)行采樣周期調(diào)整后，ST 流整體總線占用率就越小。因此，本文提出一種在HSTC 機制中確定最小時隙Tu并調(diào)整ST 流采樣周期的方案，具體步驟如下。

步驟1將的因數(shù)集L內(nèi)的元素按升序排列，并令x=1，Tu=L(x)。

步驟2檢查此時Tu的取值是否滿足式(1)～式(4)的最小時隙約束，若滿足進(jìn)入步驟3，否則令x=x+1，Tu=L(x)，重復(fù)步驟2。

步驟3按照流編號，對每一條ST 流計算

步驟4檢查此時各參數(shù)取值是否滿足式(5)～式(8)的門控約束，若滿足則流程結(jié)束，否則令x=x+1，Tu=L(x)，返回步驟2。

上述算法的流程如圖10 所示。

圖10 確定Tu 并調(diào)整ST 流采樣周期算法流程

3.2 SR 流規(guī)劃

3.2.1 SR 流映射

現(xiàn)有的流分類方法通常是將更高優(yōu)先級分配給時間敏感度高的流，例如IEEE 802.1QBA[28]中將發(fā)送間隔和截止時間更小的流分為A 類，其余分為B 類，但在本文研究場景下，這樣的流映射方式并不合理。如圖11(a)所示，對于一組給定的SR 流，若將截止時間較短的前50%的流映射為A 類，后50%映射為B 類，則當(dāng)對SR 流進(jìn)行注入調(diào)整時，由于A 類流的最大可偏移量小于B 類流的最小可偏移量，則相對于B 類流，A 類流的調(diào)整范圍集中在偏移量較小的少量時隙中，很容易發(fā)生緩存溢出，且偏移量較大時隙的緩存資源被浪費。而對于B 類流，由于可調(diào)整范圍較大，應(yīng)盡可能利用偏移量較大時隙的緩存資源，將偏移量小的緩存時隙留給A 類流。

因此，為充分利用SR 隊列緩存資源，本文采用奇偶映射的方式對SR 流進(jìn)行分類，如圖11(b)所示。將所有SR 流按截止時間升序排序并編號后，將奇數(shù)流映射為A 類，偶數(shù)流映射為B 類，從而平衡兩組SR 隊列的可偏移范圍，減少由于緩存溢出導(dǎo)致的調(diào)度失敗，從而提高網(wǎng)絡(luò)的可調(diào)度性。

圖11 SR 流映射

3.2.2 FOP 算法

采用2.1 節(jié)提出的方案確定Tu及ST 流實際采樣周期，可為SR 流預(yù)留更多傳輸資源，但當(dāng)SR流數(shù)量較大時，該方案仍難以保證網(wǎng)絡(luò)的可調(diào)度性，因此，在2.1 節(jié)基礎(chǔ)上，本文進(jìn)一步提出FOP算法對SR 流進(jìn)行注入時間規(guī)劃。

ST 流具有最高優(yōu)先級，在每個時隙Tu內(nèi)優(yōu)先傳輸，且由式(13)中SR 流轉(zhuǎn)發(fā)時延約束可知，對于任意SR 隊列，門控開啟后該隊列內(nèi)數(shù)據(jù)包必須在一個時隙內(nèi)全部發(fā)送，因此在進(jìn)行注入調(diào)整時，只需保證被調(diào)度的SR 流滿足相關(guān)約束，則其就不會對下一時隙的ST 流造成干擾。

超周期Tsup是網(wǎng)絡(luò)中ST 流及SR 流的流周期的最小公倍數(shù)，如式(18)所示。由于ST 流及SR 流都是周期流，因此整個網(wǎng)絡(luò)以Tsup為循環(huán)周期，在求解調(diào)度方案時，僅需保證一個超周期內(nèi)網(wǎng)絡(luò)的可調(diào)度性即可。

Qbuf1和Qbuf2記錄優(yōu)先級為6 和5 的兩組隊列在各時隙內(nèi)的緩存占用率，即

由式(14)中SR 流最大偏移約束可知，對于任意一條SR 流，其至多可推遲個時隙注入交換機，即在考慮注入偏移時，已將SR 流在交換機中的最大轉(zhuǎn)發(fā)時延2T u考慮在內(nèi)；其次，由于SR 隊列采用CQF 機制，因此在任意時隙內(nèi)，同一優(yōu)先級的一組隊列中有且只有一個隊列進(jìn)行緩存，另一隊列進(jìn)行數(shù)據(jù)發(fā)送。綜上，在進(jìn)行偏移注入調(diào)整時，只需保證表Qband、Qbuf1和Qbuf2中沒有任何時隙的帶寬占用率或緩存占用率大于1，即可保證調(diào)度方案滿足式(15)中SR 流的時延約束。FOP 算法偽代碼如算法1 所示。

算法1FOP 算法

在算法1 中，步驟1)進(jìn)行初始化，此時還未對SR 流進(jìn)行調(diào)度，因此只需根據(jù)式(19)更新ST流在各時隙的發(fā)送帶寬占用率，fail_tmp 用來標(biāo)記是否存在不可調(diào)度的SR 流，將Schedulability 的初始值設(shè)為真，即網(wǎng)絡(luò)可調(diào)度。

步驟2)對SR 流進(jìn)行流排序，由于采用逐流調(diào)度，先調(diào)度流可選擇利用的網(wǎng)絡(luò)資源更多，因此流調(diào)度順序?qū)W(wǎng)絡(luò)調(diào)度成功率有重要影響[14-15]，應(yīng)綜合考慮流特性，優(yōu)先調(diào)度占用資源多的流。例如，優(yōu)先調(diào)度包長最長的流，優(yōu)先調(diào)度周期最短的流，優(yōu)先調(diào)度截止時間更短的流；為綜合考慮以上特性，本文方案采用加權(quán)求和方式得到每條SR 流的調(diào)度優(yōu)先值ovj，并按ovj大小對SR 流降序排序并編號，ovj計算式為

其 中，x1、x2和x3分別為包長、周期和 截止時間的權(quán)重。由于3 種流特性維度不同，因此先通過將各流參數(shù)與所有待調(diào)度流中該參數(shù)的最大值相除，進(jìn)行歸一化處理后再進(jìn)行加權(quán)求和。由于3 種因素對網(wǎng)絡(luò)調(diào)度成功率的影響并不相同[14]，且影響程度與系統(tǒng)中流參數(shù)的取值范圍緊密相關(guān)，為確定權(quán)重大小，本文在相同的網(wǎng)絡(luò)參數(shù)生成范圍內(nèi)進(jìn)行蒙特卡羅仿真實驗，每次實驗給定一組TSN 流，并分別僅按一種因素進(jìn)行流排序，其余調(diào)度步驟相同，最終比較3 種策略下的網(wǎng)絡(luò)調(diào)度成功率。經(jīng)大量實驗發(fā)現(xiàn)，在本文采用的網(wǎng)絡(luò)配置和流配置下，以3 種方案中最優(yōu)策略和次優(yōu)策略間性能差值最大點的網(wǎng)絡(luò)調(diào)度成功率之比作為權(quán)重之比時，加權(quán)排序算法的性能較優(yōu)，因此本文按照該方式確定x1、x2、x3的取值。

步驟3)～步驟22)按照流排序結(jié)果，依次對SR 流進(jìn)行調(diào)度，其中，cspace 是待調(diào)度流可選注入時隙的集合。在每個循環(huán)中，步驟4)將cspace初始化為空。步驟5)～步驟9)在流的可調(diào)整偏移范圍內(nèi)，通過check_slot 依次檢查每個時隙是否可用，具體過程如下。

1) 對于待調(diào)度流，通過式(23)和式(24)計算其在一個時隙內(nèi)對帶寬的占用率q1及對緩存的占用率q2。

2) 對于偏移調(diào)整范圍內(nèi)的任意時隙c_tmp，若流在該時隙注入，需保證一個超周期內(nèi)的任意發(fā)送時隙和緩存時隙均不存在溢出，即當(dāng)c_tmp 滿足式(25)和式(26)的約束時，c_tmp為一個可用偏移時隙。

3) 將可用偏移時隙加入集合cspace。為均衡各時隙負(fù)載，充分利用系統(tǒng)資源，減少發(fā)送溢出和緩存溢出，應(yīng)優(yōu)先選擇資源利用率低的時隙注入，步驟11)對篩選出的時隙按綜合利用率occ_tmp進(jìn)行升序排序，occ_tmp計算式為

4 實驗和評估

為驗證所提HSTC 機制核心算法的性能，本文搭建實驗平臺，從ST 流帶寬占用率、流調(diào)度優(yōu)先級、SR 流映射、注入時隙選擇等角度，將本文所提機制與現(xiàn)有機制進(jìn)行性能仿真對比驗證，對比當(dāng)網(wǎng)絡(luò)中的ST 流及SR 流都經(jīng)由圖3 所示結(jié)構(gòu)的TSN 交換機轉(zhuǎn)發(fā)至同一接收端時，不同調(diào)度方案的性能。

4.1 實驗參數(shù)設(shè)置

實驗設(shè)置網(wǎng)絡(luò)最大幀長MTU=1 500 B，交換機單隊列的最大緩存值BufSize=6MTU，鏈路速率B=1 000 Mbit/s，δmax=1 μs。每條ST 流的最大采樣周期和包長分別從集合{0.6,0.8,1,1.2,1.6}ms 和{0.4,0.5,0.6,0.7,0.8,0.9,1}KB 中隨機選取，所有ST 流的最小采樣周期均設(shè)為0.1 ms，ST 流的截止時間為其實際采樣周期。SR 流采樣周期和包長分別從集合{4,6,8,10,12,16,20}ms 和{1.5,2,2.5,3,3.5,4,4.5}KB 中隨機選取，每條SR 流的截止時間取范圍內(nèi)一個隨機整數(shù)值。

4.2 實驗結(jié)果分析

1) ST 流帶寬占用率

為驗證調(diào)整ST 流采樣周期對網(wǎng)絡(luò)性能的影響，實驗在不考慮網(wǎng)絡(luò)中存在其他類型流的前提下，仿真當(dāng)網(wǎng)絡(luò)中存在2～12 條ST 流時，調(diào)整采樣周期前后ST流對系統(tǒng)發(fā)送帶寬的占用率，實驗結(jié)果如圖12 所示。

圖12 ST 流對系統(tǒng)發(fā)送帶寬的占用率

由圖12 可知，當(dāng)不進(jìn)行采樣周期調(diào)整，始終以相同最小采樣周期作為ST 流的實際采樣周期時，隨著流數(shù)量的增加，ST 流對發(fā)送帶寬的占用率近似呈線性關(guān)系增長，當(dāng)流數(shù)目達(dá)到12 時，發(fā)送ST 流占據(jù)了80%以上的網(wǎng)絡(luò)帶寬，這將導(dǎo)致SR 流幾乎無法傳輸。而采用本文所提方案調(diào)整采樣周期后，ST 流的帶寬占用率大幅降低，為SR 預(yù)留出了更多傳輸資源，從而有利于提高網(wǎng)絡(luò)可調(diào)度性。

2) 流調(diào)度優(yōu)先級

在逐流調(diào)度過程中，先調(diào)度流可選擇利用的網(wǎng)絡(luò)資源更多，為提升網(wǎng)絡(luò)調(diào)度成功率，應(yīng)優(yōu)先調(diào)度占用資源較多的流。因此，在本文所提的FOP 算法中，綜合考慮了截止時間、采樣周期及包長3 個衡量資源占用的流參數(shù)，通過加權(quán)求和對SR 流進(jìn)行排序調(diào)度。實驗與3 種常用的流排序方案，即最短截止時間優(yōu)先、最小采樣周期優(yōu)先和最大包長優(yōu)先的方案進(jìn)行對比，仿真當(dāng)網(wǎng)絡(luò)中存在10 條ST 流、180～250 條SR 流時，不同流排序方案的網(wǎng)絡(luò)調(diào)度成功率，仿真結(jié)果如圖13 所示。

圖13 不同流排序方案的網(wǎng)絡(luò)調(diào)度成功率

實驗結(jié)果表明，本文所提方案具有最優(yōu)性能，其余3 種方案性能排序依次為最大包長優(yōu)先、最短截止時間優(yōu)先、最小采樣周期優(yōu)先。其中，當(dāng)SR流數(shù)量為210 條時，最大包長優(yōu)先方案與最短截止時間優(yōu)先方案的網(wǎng)絡(luò)調(diào)度成功率差值達(dá)到最大，此時3種方案的網(wǎng)絡(luò)調(diào)度成功率之比約為0.62:0.26:0.12，因此本文按照該比值確定加權(quán)排序算法中x1、x2、x3的權(quán)重。實驗結(jié)果表明，相對于次優(yōu)的最大包長優(yōu)先方案，HSTC 機制所采用的加權(quán)排序方案至多能將網(wǎng)絡(luò)調(diào)度成功率提高52%。

3) SR 流映射

為提高交換機緩存利用率，減少偏移量較小時隙的緩存溢出，本文提出奇偶映射的流映射策略，為驗證該方法性能，與文獻(xiàn)[28]所提的按DDL映射的方案進(jìn)行對比。在對比實驗中，將截止時間最短的前50%的流映射為SR_A 類，后50%的流映射為SR_B 類，其他參數(shù)相同，仿真當(dāng)網(wǎng)絡(luò)中存在10 條ST 流、200～250 條SR 流的情況下，2 種流映射方案的網(wǎng)絡(luò)調(diào)度成功率，仿真結(jié)果如圖14 所示。

圖14 不同流映射方案的網(wǎng)絡(luò)調(diào)度成功率

由圖14 可知，隨著SR 流數(shù)量的增加，奇偶映射方案對提升網(wǎng)絡(luò)調(diào)度成功率的影響越顯著，2 種方案的網(wǎng)絡(luò)調(diào)度成功率的最大差值達(dá)到0.2，因此可證明，在本文所研究場景下，奇偶映射是一種合理有效的流映射方案。

4) 注入時隙選擇

在FOP 算法中，當(dāng)采用加權(quán)排序確定SR 流調(diào)度順序后，針對某條待調(diào)度流，本文采用時隙排序方案確定流的實際注入時隙，為驗證該方案的有效性，實驗與隨機選擇注入及文獻(xiàn)[29]所采用的最近注入的方案進(jìn)行對比，仿真在網(wǎng)絡(luò)中存在10 條ST流、100～280 條SR 流的情況下，不同注入選擇方案的網(wǎng)絡(luò)調(diào)度成功率和平均帶寬利用率，仿真結(jié)果如圖15 和圖16 所示。

圖15 不同注入選擇方案的網(wǎng)絡(luò)調(diào)度成功率

圖16 不同注入選擇方案的平均帶寬利用率

由圖15 可知，相較于次優(yōu)的隨機選擇注入方案，HSTC 中的時隙排序方案可將網(wǎng)絡(luò)調(diào)度成功率的值至多提升0.77。同時，由圖16 仿真結(jié)果可知，時隙排序方案的極限帶寬利用率可達(dá)88%，而其余2 種方式僅能達(dá)到62%和76%，這表明，本文的注入時隙選擇方案實現(xiàn)了更好的負(fù)載均衡，通過增大系統(tǒng)帶寬利用率來提升網(wǎng)絡(luò)可調(diào)度性。

5) 綜合對比

為對所提出的HSTC 機制進(jìn)行性能綜合驗證，在本文所研究場景下，以相同網(wǎng)絡(luò)配置及流參數(shù)與文獻(xiàn)[14]所提結(jié)合特定領(lǐng)域知識的啟發(fā)式求解（Tabu-ITP-交換）方案及文獻(xiàn)[15]所提在線逐流調(diào)度（FITS,flow injection time scheduling）方案進(jìn)行性能對比。其中，禁忌表的長度為100 條，交換概率系數(shù)設(shè)為0.8，仿真當(dāng)網(wǎng)絡(luò)中存在10 條ST 流、220～250 條SR 流的情況下，3 種方案的網(wǎng)絡(luò)調(diào)度成功率和求解時間，仿真結(jié)果如圖17 和圖18 所示。

圖17 不同方案的網(wǎng)絡(luò)調(diào)度成功率

圖18 不同方案的求解時間

由圖 17 可知，使用啟發(fā)式方法求解的Tabu-ITP-交換方案具有最高網(wǎng)絡(luò)調(diào)度成功率，該方案通過引入流密度和流多級排序，獲得收斂速度和映射質(zhì)量之間的良好折中，但由圖18 的求解時間可知，相對于逐流調(diào)度的2 種方案，啟發(fā)式方案的求解時間復(fù)雜度仍舊極高，難以實現(xiàn)系統(tǒng)流的快速求解及部署。HSTC 與TA-ITP-交換方案的最大網(wǎng)絡(luò)調(diào)度成功率差值小于4%，且隨流數(shù)目增加性能差距不斷減小，并大幅降低求解時長。FITS 方案以最小的隊列消耗增量確定偏移量以實現(xiàn)負(fù)載均衡，且求解時間復(fù)雜度較低，但在確定流調(diào)度順序時，沒有考慮不同流參數(shù)對網(wǎng)絡(luò)調(diào)度成功率的影響大小，采取直接將不同維度的流參數(shù)相乘求積后排序的方法，且沒有考慮截止時間的影響，因此相較其余2 種方法，網(wǎng)絡(luò)調(diào)度成功率較低。綜上，在本文所研究場景下，HSTC 機制實現(xiàn)了降低求解復(fù)雜度與提升調(diào)度性能的雙重優(yōu)化。

5 結(jié)束語

目前，如何在工業(yè)網(wǎng)絡(luò)中充分發(fā)揮TSN 精準(zhǔn)的流量調(diào)度能力，為生產(chǎn)控制系統(tǒng)提供確定性和實時性保障，仍是TSN 的一個研究重點。為此，本文提出HSTC 機制，將TAS 與CQF 這2 種現(xiàn)有方案進(jìn)行有機結(jié)合，并根據(jù)時間敏感流和大帶寬流的流特性，為兩類流制定不同的調(diào)度策略。實驗結(jié)果表明，HSTC 機制通過提升系統(tǒng)資源利用率顯著提高了網(wǎng)絡(luò)可調(diào)度性，實現(xiàn)了TSN 混合流的高效調(diào)度。

現(xiàn)有對TSN 的網(wǎng)絡(luò)規(guī)劃多基于離線調(diào)度場景，但在實際工業(yè)網(wǎng)絡(luò)中，還存在由事件觸發(fā)的少量突發(fā)流量，這些流無固定參數(shù)，但對系統(tǒng)的正常運轉(zhuǎn)有著重要影響，因此如何改進(jìn)現(xiàn)有方案，使之同時支持突發(fā)流的混合傳輸，是本文下一步的研究方向。