宋小慶，王海生，趙梓旭，魏 健

(陸軍裝甲兵學(xué)院，北京 100071)

1 引言

受各種應(yīng)用場景需求的驅(qū)使，實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)傳輸，成為網(wǎng)絡(luò)技術(shù)的一個(gè)重要發(fā)展方向[1]。遠(yuǎn)程手術(shù)中要求延遲可達(dá)1 ms[2-3]，沉浸式虛擬現(xiàn)實(shí)場景要求延遲為0.5～2 ms[4]，工業(yè)自動(dòng)化領(lǐng)域要求延遲達(dá)亞毫秒[5]，高壓配電要求延遲為5 ms[6]。但傳統(tǒng)總線網(wǎng)絡(luò)如CAN、FlexRay等因帶寬受限難以保證大量數(shù)據(jù)的實(shí)時(shí)傳輸[7]，傳統(tǒng)以太網(wǎng)采用“盡力而為”的傳輸理念難以保證關(guān)鍵流量的實(shí)時(shí)性，新興技術(shù)方案如PROFINET[8]、EtherCAT[9]、TTEthernet[10]等多針對(duì)特定應(yīng)用定制，因兼容性、互操作性等原因難以獲得廣泛應(yīng)用[11]，兼具成本、帶寬、兼容優(yōu)勢和高實(shí)時(shí)、高可靠特性的新方案——時(shí)間敏感網(wǎng)絡(luò)應(yīng)運(yùn)而生[12-13]。

時(shí)間敏感網(wǎng)絡(luò)源于傳統(tǒng)以太網(wǎng)，由IEEE802.1 TSN工作組提出并致力于標(biāo)準(zhǔn)化，獲得Avnu聯(lián)盟等組織的認(rèn)可[14]，利于形成生態(tài)優(yōu)勢，已經(jīng)在車載網(wǎng)絡(luò)[15]、航空網(wǎng)絡(luò)[16]、工業(yè)互聯(lián)網(wǎng)[17]、5G[18]及能源網(wǎng)絡(luò)[19]等方面獲得廣泛關(guān)注。傳統(tǒng)以太網(wǎng)采用“FIFO”方式，不能提供差異化數(shù)據(jù)傳輸服務(wù)，關(guān)鍵數(shù)據(jù)傳輸時(shí)易被沖突，嚴(yán)重影響相關(guān)業(yè)務(wù)的實(shí)現(xiàn)[20]，而時(shí)間敏感網(wǎng)絡(luò)通過流量調(diào)度機(jī)制，使流量相互隔離并有序傳輸，減少傳輸?shù)碾S機(jī)沖突，控制排隊(duì)時(shí)延，保證傳輸實(shí)時(shí)性。當(dāng)前，IEEE802.1 TSN工作組不斷完善時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度機(jī)制，并將其標(biāo)準(zhǔn)化，提升調(diào)度性能。

針對(duì)時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度機(jī)制，介紹基本原理和研究現(xiàn)狀，梳理各機(jī)制的研究重點(diǎn)和研究進(jìn)展，分析各機(jī)制的優(yōu)點(diǎn)和不足，最后闡述當(dāng)前研究趨勢。

2 時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度

2.1 調(diào)度原理與分類

通常，時(shí)間敏感網(wǎng)絡(luò)根據(jù)流量優(yōu)先級(jí)(或類別)，在空間上通過隊(duì)列隔離流量，而后按一定規(guī)則調(diào)度流量，進(jìn)而實(shí)現(xiàn)傳輸時(shí)間的隔離，保證傳輸延遲的確定性。

時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度機(jī)制主要有基于信用整形、時(shí)間感知整形、幀搶占、循環(huán)排隊(duì)轉(zhuǎn)發(fā)、異步流量整形等。按照調(diào)度原理，可分為按時(shí)分復(fù)用原理調(diào)度機(jī)制和按競爭規(guī)則調(diào)度機(jī)制。按時(shí)分復(fù)用原理調(diào)度機(jī)制，將傳輸實(shí)時(shí)性要求直接與傳輸時(shí)隙劃分相對(duì)應(yīng)，通過調(diào)整傳輸時(shí)隙控制流量調(diào)度，因傳輸時(shí)隙易與周期流量匹配，因此該類調(diào)度對(duì)周期流量調(diào)度效果較好，調(diào)度機(jī)制有時(shí)間感知整形和循環(huán)排隊(duì)轉(zhuǎn)發(fā)。按競爭規(guī)則調(diào)度機(jī)制，將傳輸實(shí)時(shí)性要求與優(yōu)先規(guī)則相對(duì)應(yīng)，按優(yōu)先規(guī)則調(diào)度流量，該類調(diào)度對(duì)流量周期性無要求，可混合調(diào)度周期流量和突發(fā)流量，如幀搶占(及嚴(yán)格優(yōu)先級(jí)調(diào)度)是按照流量的優(yōu)先級(jí)調(diào)度，基于信用整形按照信用值調(diào)度，異步流量整形以合格時(shí)間(即流量傳輸緊急度)作為調(diào)度依據(jù)。各調(diào)度機(jī)制可單獨(dú)使用，也可多個(gè)綜合運(yùn)用。

2.2 研究對(duì)象

如圖1所示，時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度研究對(duì)象為有延遲要求的時(shí)間敏感流量和無延遲要求的盡力而為流量，前者是研究重點(diǎn)，后者作為背景流量。時(shí)間敏感流量因?qū)鬏敃r(shí)間“敏感”而得名，這種流量通常按預(yù)定時(shí)間發(fā)送，也稱時(shí)間觸發(fā)流量(對(duì)應(yīng)事件觸發(fā)流量)[21]、計(jì)劃流量(對(duì)應(yīng)突發(fā)流量)，而當(dāng)前許多研究中流量的發(fā)送時(shí)間間隔是固定時(shí)間，因此實(shí)際是周期流量。部分研究針對(duì)非預(yù)定時(shí)間發(fā)送的關(guān)鍵流量即關(guān)鍵非計(jì)劃流量(實(shí)為突發(fā)流量)。另外，最初研究針對(duì)音視頻傳輸[22]，也被稱為AVB(audio video bridging)流量，AVB流量用于基于信用整形機(jī)制，優(yōu)先級(jí)較低，但高于盡力為流量。從抖動(dòng)要求看，時(shí)間敏感流量又分為抖動(dòng)要求高的硬實(shí)時(shí)要求流量和抖動(dòng)要求低的軟實(shí)時(shí)要求流量。

圖1 時(shí)間敏感網(wǎng)絡(luò)研究對(duì)象

2.3 評(píng)價(jià)指標(biāo)

流量調(diào)度評(píng)價(jià)指標(biāo)主要有最壞情況延遲、最壞情況延遲的悲觀度[23](悲觀度越大表示理論值與實(shí)驗(yàn)值差別越大)、帶寬利用率、調(diào)度能力、算法效率等。

3 時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度機(jī)制及研究現(xiàn)狀

首先，從調(diào)度機(jī)制的發(fā)展看，后續(xù)機(jī)制針對(duì)不同應(yīng)用需求，對(duì)前面機(jī)制進(jìn)行完善，如圖2所示。傳統(tǒng)網(wǎng)絡(luò)可采用嚴(yán)格優(yōu)先級(jí)調(diào)度，保證高優(yōu)先級(jí)流量實(shí)時(shí)性，但易導(dǎo)致低優(yōu)先級(jí)流量“餓死”。為避免該問題，基于信用整形將優(yōu)先級(jí)與排隊(duì)時(shí)間綜合為信用值，按照信用值調(diào)度，帶寬利用率高，但流量傳輸時(shí)易相互影響，抖動(dòng)大，最壞情況延遲計(jì)算復(fù)雜、悲觀度較大。而基于時(shí)分復(fù)用的時(shí)間感知整形和循環(huán)排隊(duì)轉(zhuǎn)發(fā)，最壞情況延遲計(jì)算簡單，直接用傳輸時(shí)隙調(diào)度各類流量，避免流量間沖突，利于降低抖動(dòng)和最壞情況延遲悲觀度。相比時(shí)間感知整形，循環(huán)排隊(duì)轉(zhuǎn)發(fā)只有2個(gè)隊(duì)列，解決了幀傳輸?shù)挠薪鐣r(shí)延，算法求解簡單，但流量調(diào)度數(shù)量受限。基于時(shí)分復(fù)用調(diào)度機(jī)制存在3個(gè)問題：一是因保護(hù)帶存在，導(dǎo)致帶寬浪費(fèi)，網(wǎng)絡(luò)實(shí)時(shí)性有提升潛力；二是依賴時(shí)間同步；三是該類機(jī)制主要針對(duì)周期流量，難以調(diào)度突發(fā)流量。而幀搶占可減小保護(hù)帶，減少帶寬浪費(fèi)。異步流量整形關(guān)注每跳的流量調(diào)度情況，不依賴時(shí)間同步，實(shí)現(xiàn)周期流量和突發(fā)流量的混合調(diào)度，抖動(dòng)小、帶寬利用率高，模型設(shè)計(jì)較為復(fù)雜。各種調(diào)度機(jī)制性能比較和使用分別見表1和圖3所示。另外，結(jié)合時(shí)間敏感網(wǎng)絡(luò)的網(wǎng)絡(luò)配置標(biāo)準(zhǔn)和時(shí)間感知整形而提出時(shí)間敏感型軟件定義網(wǎng)絡(luò)(time-sensitive software-defined network,TSSDN)，可實(shí)現(xiàn)在線流量調(diào)度，是當(dāng)前一個(gè)研究熱點(diǎn)，單獨(dú)作為一個(gè)綜述內(nèi)容。

圖2 流量調(diào)度機(jī)制發(fā)展路線圖

表1 時(shí)間敏感網(wǎng)絡(luò)各調(diào)度機(jī)制性能比較

圖3 流量調(diào)度過程

其次，從各調(diào)度機(jī)制的研究看，IEEE802.1 TSN工作組提出流量調(diào)度機(jī)制對(duì)應(yīng)的標(biāo)準(zhǔn)(各調(diào)度分標(biāo)準(zhǔn)正匯總至IEEE802.1Q，為方便區(qū)分，仍以分標(biāo)準(zhǔn)介紹)，明確了各機(jī)制的基本原理，提供了實(shí)現(xiàn)確定邊界延遲傳輸?shù)臈l件。而實(shí)時(shí)傳輸易受眾多因素影響，各研究不斷完善影響因素分析，提高調(diào)度性能。

3.1 基于信用整形

該機(jī)制以IEEE802.1 Qav標(biāo)準(zhǔn)為依據(jù)，采用基于信用整形器(credit based shaper,CBS)，用隊(duì)列隔離流量，根據(jù)各隊(duì)列信用值進(jìn)行調(diào)度，兼顧各優(yōu)先級(jí)流量的實(shí)時(shí)性。信用值由流量所在隊(duì)列的優(yōu)先級(jí)和流量在隊(duì)列中排隊(duì)情況2個(gè)因素決定。一方面，該機(jī)制根據(jù)信用值大小控制各流量傳輸，信用值大的優(yōu)先傳輸；另一方面，流量的排隊(duì)、傳輸分別導(dǎo)致信用值的增、減。信用值增加、減少的快慢與隊(duì)列優(yōu)先級(jí)有關(guān)。

該機(jī)制研究重點(diǎn)是延遲影響因素分析。這主要因?yàn)樵摍C(jī)制流量間仍易沖突，導(dǎo)致最壞情況延遲分析復(fù)雜。延遲分析既要橫向上考慮單個(gè)節(jié)點(diǎn)中各流量間影響、傳輸離散性[24]、以及其他機(jī)制(如時(shí)間感知整形[25])影響等，也要縱向上考慮多個(gè)節(jié)點(diǎn)延遲積累[26]、路由影響[27]等。基于信用整形的最壞情況延遲是眾多因素綜合產(chǎn)生的極端情況，考慮的因素越多、情況越極端得到最壞情況延遲計(jì)算公式越準(zhǔn)確，但最壞情況發(fā)生的概率可能會(huì)越低，悲觀度越大，實(shí)際中應(yīng)綜合悲觀度和復(fù)雜度運(yùn)用該機(jī)制[28]。

機(jī)制研究方面。幀在排隊(duì)過程中，前面幀對(duì)后面幀產(chǎn)生的影響(即幀序列化)易被忽略，Li等[29]推導(dǎo)基于信用整形調(diào)度的最壞情況延遲公式，重點(diǎn)分析幀序列化的影響，同時(shí)去除信用補(bǔ)充與高優(yōu)先級(jí)幀傳輸?shù)闹丿B時(shí)間，降低延遲悲觀度最大達(dá)46.96%。上述研究是按照數(shù)據(jù)流調(diào)度，具有連續(xù)性，而實(shí)際是按照幀調(diào)度，具有離散性，用幀調(diào)度模型比流調(diào)度模型降低悲觀度最大達(dá)13.44%[24]。而Mohammadpour等將原機(jī)制的2個(gè)優(yōu)先級(jí)隊(duì)列擴(kuò)充至任意數(shù)量，增加了調(diào)度流量數(shù)量，利用網(wǎng)絡(luò)演算分析，使延遲悲觀度相比以往研究降低最大達(dá)89%[30]。

機(jī)制綜合運(yùn)用方面。Zhao等[25]分析時(shí)間感知整形機(jī)制下AVB流量的調(diào)度性能，該研究兼顧幀搶占和非幀搶占2種模式，推導(dǎo)信用值非溢出條件，確?；谛庞谜蔚膮?shù)實(shí)現(xiàn)有界的最壞情況延遲。另外，將數(shù)據(jù)壓縮技術(shù)與基于信用整形機(jī)制相結(jié)合也可減少延遲[31]。

分析方法方面。采用不同分析方法也會(huì)影響延遲計(jì)算結(jié)果。研究表明，采用網(wǎng)絡(luò)演算[25]、前向端到端延遲分析[26]、軌跡法[29]比組合性能法有更低的悲觀度，這主要因?yàn)榻M合性能法是先求單個(gè)節(jié)點(diǎn)的延遲，而后將各個(gè)節(jié)點(diǎn)延遲簡單相加獲得端到端延遲，而其他方法分析時(shí)考慮前后節(jié)點(diǎn)的延遲影響，更加合理。

3.2 時(shí)間感知整形

該機(jī)制以IEEE802.1 Qbv標(biāo)準(zhǔn)為依據(jù)。該機(jī)制采用時(shí)間感知整形器(time aware shaper,TAS)，用隊(duì)列隔離流量，通過循環(huán)的門控列表控制每個(gè)隊(duì)列的開關(guān)狀態(tài)，使隊(duì)列內(nèi)流量按劃分時(shí)隙傳輸，實(shí)現(xiàn)傳輸?shù)臅r(shí)間隔離，提供可預(yù)測的有界延遲。該機(jī)制未要求前后節(jié)點(diǎn)時(shí)間同步，各節(jié)點(diǎn)利用本地時(shí)鐘即可調(diào)度，但時(shí)間同步利于流量按照預(yù)定時(shí)間在各節(jié)點(diǎn)間傳輸，保證調(diào)度有效性[32-33]，因此該機(jī)制在現(xiàn)有研究中往往依賴時(shí)間同步，通常被認(rèn)為是同步調(diào)度機(jī)制。標(biāo)準(zhǔn)中該機(jī)制只定義了8個(gè)隊(duì)列，當(dāng)流量的數(shù)量超過8個(gè)時(shí)，流量會(huì)共用隊(duì)列，則共用隊(duì)列的流量會(huì)發(fā)生沖突，調(diào)度更加復(fù)雜。

該機(jī)制研究重點(diǎn)是門控列表生成。門控列表實(shí)為調(diào)度列表，生成復(fù)雜。門控列表生成是在時(shí)隙約束、路由約束、沖突避免約束等的條件下，根據(jù)流量的特性求得最小延遲的解，它是NP完全問題(non-deterministic polynomial complete problem,多項(xiàng)式復(fù)雜度的非確定性問題)[34]，無已知算法可在多項(xiàng)式時(shí)間內(nèi)生成最優(yōu)調(diào)度列表[35]，因此，門控列表生成算法調(diào)度主要為離線調(diào)度。網(wǎng)絡(luò)越復(fù)雜、流量越多，門控列表的求解越難。通常采用2種方式求解：一是運(yùn)用專門的搜索算法，如元啟發(fā)式、啟發(fā)式或遺傳算法[36]；二是利用通用工具，如整數(shù)線性規(guī)劃(integer linear programming,ILP)[37]或可滿足性模理論(satisfiability modulo theories,SMT)[38]求解器?，F(xiàn)有研究多分析時(shí)間同步、路由選擇等對(duì)該機(jī)制調(diào)度效果影響，以及如何設(shè)計(jì)算法快速生成門控列表。

門控列表生成問題可以等效為無等待車間調(diào)度問題(no-wait job-shop scheduling problem,NW-JSP)。Dürr等[39]將調(diào)度列表生成問題等效為無等待數(shù)據(jù)包調(diào)度問題，用禁忌搜索算法尋找保護(hù)帶最少的解，使保護(hù)帶平均降低24%，提高了帶寬利用率。

上面研究針對(duì)固定路由，將路由選擇與流量調(diào)度結(jié)合，可進(jìn)一步提升實(shí)時(shí)性。Pahlevan等[36]考慮路由與調(diào)度的相互影響，利用遺傳算法選擇路由，仿真表明比固定路由可減少保護(hù)帶，平均降低時(shí)延31%。而采用基于路由子集和時(shí)間片的啟發(fā)式算法，在保證效果的同時(shí)，可進(jìn)一步提高算法的效率[40]。

時(shí)間感知整形與基于信用整形綜合使用時(shí)，在文獻(xiàn)[27]、文獻(xiàn)[41]中首先根據(jù)時(shí)間觸發(fā)流量的周期確定其調(diào)度時(shí)間，而后進(jìn)行AVB流量的調(diào)度，這可為時(shí)間觸發(fā)流量提供獨(dú)享的調(diào)度時(shí)間窗口，但會(huì)導(dǎo)致AVB流量的實(shí)時(shí)性降低甚至無法調(diào)度，也減少了可行解的范圍。為此，Gavrilut等[42]綜合路由與調(diào)度前提下，考慮時(shí)間觸發(fā)流量和AVB流量的實(shí)時(shí)性，用“盡快”啟發(fā)式算法進(jìn)行幀偏移，進(jìn)一步優(yōu)化隊(duì)列使用和最小延遲，該方法獲得更多可行解，解決其他方法可能無法調(diào)度的問題。進(jìn)一步地，同時(shí)打開多個(gè)隊(duì)列，使多個(gè)類型流量在一個(gè)共同時(shí)間段內(nèi)傳輸，將使解的范圍進(jìn)一步增大。為此，Shalghum等[43]進(jìn)一步考慮同一節(jié)點(diǎn)上不同優(yōu)先級(jí)流量窗口重疊的情況，基于延遲評(píng)估來優(yōu)化時(shí)間觸發(fā)流量窗口偏移量，實(shí)現(xiàn)了更小悲觀度的端到端延遲，最大降低32.6%。

合理的優(yōu)先級(jí)劃分，也可提升調(diào)度效果。Liu等[44]研究流量不同類型劃分對(duì)調(diào)度影響，將時(shí)間敏感流量的優(yōu)先級(jí)分別定為：單獨(dú)A類、A類與B類、Qbv類(時(shí)間觸發(fā)流量)與A類，比較3種分類調(diào)度效果，實(shí)驗(yàn)表明單獨(dú)A類比A類與B類延遲小，但在大負(fù)載數(shù)據(jù)下會(huì)出現(xiàn)無法調(diào)度問題，采用Qbv類與A類可保證關(guān)鍵數(shù)據(jù)的延遲和抖動(dòng)更小，但A類流量抖動(dòng)會(huì)變大。

特別地，通過預(yù)留調(diào)度時(shí)間可實(shí)現(xiàn)混合流量調(diào)度。為此，Yin等[45]根據(jù)事件觸發(fā)流量的延遲要求，預(yù)先為其分配“虛擬調(diào)度時(shí)間”，減少事件觸發(fā)流量對(duì)時(shí)間觸發(fā)流量的影響，實(shí)現(xiàn)混合流量調(diào)度，同時(shí)采用復(fù)用機(jī)制，事件觸發(fā)流量未傳輸時(shí)，該虛擬調(diào)度時(shí)間由時(shí)間觸發(fā)流量使用，可使事件觸發(fā)流量的可調(diào)度性提升25%，延遲降低45%，帶寬利用率提升13%。

此外，干擾可能會(huì)導(dǎo)致調(diào)度失敗，因?yàn)楦麝?duì)列內(nèi)是按照嚴(yán)格優(yōu)先級(jí)調(diào)度，如某計(jì)劃流量因網(wǎng)絡(luò)傳輸抖動(dòng)等原因不能按時(shí)到達(dá)隊(duì)列時(shí)，則同一隊(duì)列內(nèi)先到達(dá)的非計(jì)劃流量會(huì)提前傳輸，導(dǎo)致計(jì)劃流量可能會(huì)錯(cuò)過一個(gè)調(diào)度周期。為此，Dai等[46]為各數(shù)據(jù)幀設(shè)定優(yōu)先級(jí)，在時(shí)間感知整形機(jī)制中引入緩存機(jī)制，使隊(duì)列中低優(yōu)先級(jí)的非計(jì)劃流量等待優(yōu)先級(jí)高的計(jì)劃流量到達(dá)，確保計(jì)劃流量的可調(diào)度性。

3.3 循環(huán)排隊(duì)轉(zhuǎn)發(fā)

該機(jī)制以IEEE802.1 Qch標(biāo)準(zhǔn)為依據(jù)，采用雙隊(duì)列的循環(huán)排隊(duì)轉(zhuǎn)發(fā)(cyclic queuing and forwarding,CQF)調(diào)度。在相等時(shí)間段內(nèi)，2個(gè)隊(duì)列交替接收和發(fā)送數(shù)據(jù)幀。此機(jī)制中，數(shù)據(jù)幀經(jīng)過每跳的延遲范圍是確定的(即該相等時(shí)間段)，不受網(wǎng)絡(luò)拓?fù)溆绊憽＿@使得端到端延遲只與源端到目的端的跳數(shù)有關(guān)。

該機(jī)制研究重點(diǎn)是起始時(shí)隙分配。這因?yàn)樵摍C(jī)制中，各節(jié)點(diǎn)皆有2個(gè)交替接收、發(fā)送的隊(duì)列且調(diào)度時(shí)間段相等，則前后節(jié)點(diǎn)間調(diào)度時(shí)間段和隊(duì)列也形成對(duì)應(yīng)關(guān)系，即在同一個(gè)時(shí)間段內(nèi)，前一節(jié)點(diǎn)隊(duì)列發(fā)送對(duì)應(yīng)后一節(jié)點(diǎn)隊(duì)列接收，因此在網(wǎng)絡(luò)邊緣(即源端)完成調(diào)度，后續(xù)節(jié)點(diǎn)的調(diào)度也將確定。該機(jī)制相對(duì)簡單，最壞情況延遲易于計(jì)算，但依賴時(shí)間同步。

控制起始時(shí)隙分配影響循環(huán)排隊(duì)轉(zhuǎn)發(fā)調(diào)度效果。姜旭艷等[47]提出一種基于起始時(shí)隙分配的輕量級(jí)資源調(diào)度算法，將時(shí)隙分配問題抽象為多約束條件下資源規(guī)劃最大化問題。實(shí)驗(yàn)表明，該方法調(diào)度能力比不控制起始時(shí)隙的直接調(diào)度算法平均提高41.84%。

結(jié)合流量特征和資源特征減小解的范圍，可進(jìn)一步提升算法的效率。Yan等[48]在文獻(xiàn)[47]中的研究基礎(chǔ)上提出一種啟發(fā)式算法，該算法考慮流量的特征和資源特征減小搜索空間，在方案求解和搜索開銷之間取得良好平衡，可使調(diào)度流量數(shù)量提升10倍，帶寬利用率提升65%。其中，考慮流量的特征指結(jié)合數(shù)據(jù)包的數(shù)量、路徑選擇和周期進(jìn)行優(yōu)先級(jí)排序，考慮資源狀態(tài)指去除方案中高流量密度的情況。

以上研究針對(duì)軟實(shí)時(shí)要求流量，難以處理零抖動(dòng)要求的硬實(shí)時(shí)流量傳輸。為此，Huang等[49]設(shè)計(jì)無等待整形器和循環(huán)整形器進(jìn)行硬實(shí)時(shí)要求的等時(shí)流量調(diào)度。首先，無等待整形器壓縮等時(shí)流量的時(shí)隙資源，以盡可能少的時(shí)隙實(shí)現(xiàn)等時(shí)流量零抖動(dòng)傳輸。然后，循環(huán)整形器一方面利用循環(huán)排隊(duì)轉(zhuǎn)發(fā)原理調(diào)度循環(huán)流量，另一方面通過在發(fā)送端引入雙閉合狀態(tài)實(shí)現(xiàn)與無等待整形器的合并。實(shí)驗(yàn)表明，等時(shí)流量可實(shí)現(xiàn)零抖動(dòng)，且延遲減少81.3%。

進(jìn)一步，大規(guī)模骨干網(wǎng)場景下，傳輸時(shí)延波動(dòng)和短時(shí)突發(fā)流量過載等可能導(dǎo)致調(diào)度失敗。莫益軍等[50]提出基于3個(gè)隊(duì)列的循環(huán)排隊(duì)轉(zhuǎn)發(fā)機(jī)制，引入第3個(gè)隊(duì)列充當(dāng)緩沖，可根據(jù)流量狀態(tài)及時(shí)調(diào)整門控時(shí)機(jī)和排隊(duì)優(yōu)先級(jí)，以避免幀傳輸時(shí)隙錯(cuò)誤。實(shí)驗(yàn)表明，線性拓?fù)湎略摲椒ū纫话鉉QF平均延遲降低27%，重載情況下丟包率降低78%。

另外，當(dāng)網(wǎng)絡(luò)中有新流量注入時(shí)，需花費(fèi)大量時(shí)間重新計(jì)算配置參數(shù)。Quan等[51]提出一種輕量級(jí)動(dòng)態(tài)流量調(diào)度算法。首先，計(jì)算原有流量的最長隊(duì)列的起始時(shí)隙分配方案，使隊(duì)列內(nèi)初始時(shí)隙盡可能冗余；然后，新引入流量在冗余時(shí)隙中搜尋方案，避免對(duì)原有流量調(diào)度的影響。實(shí)驗(yàn)表明，該算法調(diào)度成功率比Naive算法和Tabu算法提高分別多82.5%和29.7%。

3.4 時(shí)間敏感型軟件定義網(wǎng)絡(luò)

該機(jī)制源于軟件定義網(wǎng)絡(luò)技術(shù)，IEEE802.1 Qcc標(biāo)準(zhǔn)和IEEE802.1 Qbv標(biāo)準(zhǔn)可為其提供技術(shù)支持(前者用于網(wǎng)絡(luò)配置，后者實(shí)現(xiàn)調(diào)度)。該機(jī)制從網(wǎng)絡(luò)架構(gòu)角度調(diào)度流量，將時(shí)間敏感網(wǎng)絡(luò)分為控制平面和數(shù)據(jù)平面，將執(zhí)行集中式算法的網(wǎng)絡(luò)應(yīng)用程序部署到網(wǎng)絡(luò)上，具有流量調(diào)度的全局視圖[52]，通過邏輯上的控制器控制網(wǎng)絡(luò)設(shè)備。TSSDN可實(shí)現(xiàn)在線動(dòng)態(tài)調(diào)度，支持具有冗余路徑的任意網(wǎng)絡(luò)拓?fù)?，增加網(wǎng)絡(luò)魯棒性，可應(yīng)對(duì)網(wǎng)絡(luò)拓?fù)渥兓巴ㄐ沛溌饭收系葐栴}[53]。

TSSDN研究重點(diǎn)是調(diào)度配置參數(shù)的快速計(jì)算。該機(jī)制依賴時(shí)間同步，控制平面數(shù)據(jù)傳輸會(huì)對(duì)流量調(diào)度產(chǎn)生一定影響[54]，當(dāng)網(wǎng)絡(luò)復(fù)雜、流量眾多時(shí)，需要設(shè)計(jì)專門算法快速計(jì)算配置參數(shù)。

控制平面的數(shù)據(jù)通常與數(shù)據(jù)平面的數(shù)據(jù)共用網(wǎng)絡(luò)資源，前者的傳輸不可避免會(huì)后者產(chǎn)生影響。為此，Thiele等[54]采用組合性能分析法研究TSSDN，將控制平面流量分別映射到3個(gè)優(yōu)先級(jí)：單獨(dú)作為最高優(yōu)先級(jí)(高于控制流量)、與控制流量同為最高優(yōu)先級(jí)、與視頻流量同優(yōu)先級(jí)，實(shí)驗(yàn)表明將控制平面流量優(yōu)先級(jí)映射到后2種情況時(shí)，可使其他流量延遲更小。

上面研究選用固定路由，而將路由選擇與流量調(diào)度相結(jié)合，利于降低延遲。Nayak等[55]利用ILP來解決路由選擇和調(diào)度時(shí)隙劃分的組合問題，對(duì)比無約束路由、路徑集路由(可能的路由集合)和固定路由(從最短路由中隨機(jī)選取一個(gè))，三者性能接近，說明在計(jì)算能力有限的情況下，直接用最短路由調(diào)度流量的可行性。而利用拓?fù)湫藜舨呗院突谧V聚類的流分組策略等[56]，降低網(wǎng)絡(luò)的復(fù)雜性，進(jìn)一步提升算法效率。

以上研究為靜態(tài)調(diào)度，難以應(yīng)對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)變化，如新增時(shí)間敏感流出現(xiàn)時(shí)，需花費(fèi)大量時(shí)間重新計(jì)算配置參數(shù)。為此，Nayak等[52]在文獻(xiàn)[55]中的研究基礎(chǔ)上，提出在線TSSDN流量調(diào)度方法，可動(dòng)態(tài)計(jì)算時(shí)間觸發(fā)流量的路由和調(diào)度。首先采用“最大最小值”法，求取調(diào)度周期最大且占用路由最小的時(shí)隙和路由分配方案，調(diào)度周期最大保證盡可能多的空閑時(shí)隙可用于新增流量，占用路由最小保證盡可能多的空閑路由用于新增流量。因此，新增流量在空閑時(shí)隙和空閑路由中搜索最優(yōu)解，不影響原有流量的調(diào)度。實(shí)驗(yàn)表明，該方法求解時(shí)間為亞秒，而平均調(diào)度能力是無限制路由調(diào)度的68%。

3.5 幀搶占

該機(jī)制以IEEE802.1 Qbu和IEEE 802.3br標(biāo)準(zhǔn)為依據(jù)，高優(yōu)先級(jí)幀可插入低優(yōu)先級(jí)幀中間傳輸，待高優(yōu)先級(jí)幀傳輸結(jié)束后，繼續(xù)傳輸?shù)蛢?yōu)先級(jí)幀的剩余片段。該機(jī)制可有效減少高優(yōu)先級(jí)數(shù)據(jù)幀的延遲，可用于減小保護(hù)帶，減少帶寬浪費(fèi)。此機(jī)制允許低優(yōu)先級(jí)幀可被多次搶占，但搶占幀不能被更高優(yōu)先級(jí)幀搶占，即幀搶占不允許嵌套。這因?yàn)槊總€(gè)幀只能是express(快速)和preemptable(被搶占)狀態(tài)中的一種。

該機(jī)制研究重點(diǎn)是分析搶占對(duì)延遲的影響。該機(jī)制可降低高優(yōu)先級(jí)流量的延遲和抖動(dòng)[57]，也可降低最低優(yōu)先級(jí)流量的延遲[58]，該機(jī)制主要配合其他機(jī)制使用，提高實(shí)時(shí)性和帶寬利用率。

將幀搶占與時(shí)間感知整形綜合運(yùn)用，可減小保護(hù)帶，提升調(diào)度性能。為此，Thiele等[59]將幀搶占機(jī)制引入時(shí)間感知整形機(jī)制，使保護(hù)帶由1 542字節(jié)降為143字節(jié)，實(shí)驗(yàn)發(fā)現(xiàn)，引入幀搶占使標(biāo)準(zhǔn)以太網(wǎng)達(dá)到與時(shí)間敏感網(wǎng)絡(luò)相當(dāng)?shù)恼{(diào)度能力，因標(biāo)準(zhǔn)以太網(wǎng)設(shè)置更加簡單，基于幀搶占的標(biāo)準(zhǔn)以太網(wǎng)比時(shí)間敏感網(wǎng)絡(luò)更具有應(yīng)用優(yōu)勢。

通過額外手段減少幀的最小限制，可在幀搶占基礎(chǔ)上進(jìn)一步減小保護(hù)帶。為此，Lee等[58]通過增加緩存、補(bǔ)充幀長度等方式，將保護(hù)帶進(jìn)一步減小至64字節(jié)甚至20字節(jié)，仿真表明該方法可降低總延遲，優(yōu)先級(jí)最高的控制類流量和優(yōu)先級(jí)最低的盡力而為流量延遲降低比較明顯，但對(duì)處于中間優(yōu)先級(jí)的AVB流量影響不顯著。

當(dāng)幀搶占與非幀搶占同時(shí)在調(diào)度中存在時(shí)，延遲分析更復(fù)雜。為此，Bello等[23]提出在基于信用整形和時(shí)間感知整形調(diào)度中，幀搶占和非幀搶占共存的通用可調(diào)度性分析，通過數(shù)學(xué)分析和仿真說明，僅僅增加總帶寬并不一定能減小延遲。

3.6 異步流量整形

該機(jī)制以IEEE802.1 Qcr標(biāo)準(zhǔn)為依據(jù)，設(shè)計(jì)異步流量整形器(asynchronous traffic shaper,ATS)，通過每跳流量交織整形限制流量突發(fā)，避免流量突發(fā)級(jí)聯(lián)[60]，提供每跳延遲邊界，并降低對(duì)時(shí)間同步的依賴。異步流量整形通過分離速率控制器和調(diào)度器，實(shí)現(xiàn)帶寬利用率和有界延遲的解耦[61]。

該機(jī)制根據(jù)Specht等[61]提出的基于事件緊急度的調(diào)度器(urgency-based scheduler,UBS)設(shè)計(jì)。通常，因流量間競爭，每一跳都可使流量突發(fā)增大，而增大的突發(fā)流量在下一跳又將影響其他流量的突發(fā)大小，即產(chǎn)生突發(fā)流量的級(jí)聯(lián)，造成延遲分析復(fù)雜。而異步流量整形機(jī)制對(duì)流量進(jìn)行交織整形，使每一跳流量的突發(fā)大小限制在一定數(shù)值(即突發(fā)上界)，從而限制了突發(fā)流量級(jí)聯(lián)，突發(fā)上界簡化了延遲邊界分析，且交織整形不會(huì)增大最壞情況延遲[62]。該機(jī)制中根據(jù)幀的緊急度(指標(biāo)為合格時(shí)間)，確保急需傳輸?shù)膸瑑?yōu)先調(diào)度，在高帶寬利用率情況下，調(diào)度效果比嚴(yán)格優(yōu)先級(jí)調(diào)度更好。

該機(jī)制研究重點(diǎn)是調(diào)度模型的設(shè)計(jì)。IEEE802.1 Qcr標(biāo)準(zhǔn)于2020年11月由草案成為正式標(biāo)準(zhǔn)，晚于其他調(diào)度標(biāo)準(zhǔn)，相關(guān)研究正處于探索階段，研究主要集中在與調(diào)度直接相關(guān)的因素，如模型設(shè)計(jì)、性能論證、參數(shù)設(shè)置、與其他機(jī)制的綜合運(yùn)用等方面。

在模型設(shè)計(jì)上，Specht等[61]較早開始相關(guān)研究，設(shè)置3條映射規(guī)則，將滿足規(guī)則的流共用同一隊(duì)列，減少了所需隊(duì)列數(shù)量，利于流量調(diào)度數(shù)量的擴(kuò)展，并通過多個(gè)隊(duì)列之間的交織整形算法將不同隊(duì)列中的流量進(jìn)行整合發(fā)送，實(shí)現(xiàn)了低復(fù)雜度、低時(shí)間同步要求的異步流量調(diào)度。而Boudec[62]進(jìn)一步證明了在FIFO系統(tǒng)后直連最小交織整形器，不會(huì)增加最壞情況延遲。

在性能論證上，NASRALLAH等[63]研究表明，相比時(shí)間感知整形，異步流量整形對(duì)突發(fā)流量調(diào)度延遲更小，但在高負(fù)載下對(duì)周期流量調(diào)度延遲增加。

在參數(shù)求解上，Specht等[64]通過可滿足性模理論，求解網(wǎng)絡(luò)配置內(nèi)部優(yōu)先級(jí)和流隊(duì)列分配的可行解。而Prados-Garzon等[6]針對(duì)異步流量具有數(shù)量和特性不確定性的特點(diǎn)，利用深度強(qiáng)化學(xué)習(xí)進(jìn)行流量分析預(yù)測和調(diào)度參數(shù)配置，實(shí)現(xiàn)了在線調(diào)度，進(jìn)一步提高了算法的適應(yīng)性。

在與其他機(jī)制綜合運(yùn)用上，將異步流量整形的交織整形引入基于信用整形[65]，可使最壞情況延遲悲觀度降低為0，實(shí)驗(yàn)最大延遲等于理論最壞情況延遲。而將幀搶占引入異步流量整形機(jī)制[66-67]，可降低高優(yōu)先級(jí)流量的端到端延遲，實(shí)驗(yàn)表明延遲降低超過25%。

4 結(jié)論

當(dāng)前，各流量調(diào)度機(jī)制主要研究目標(biāo)是提高實(shí)時(shí)性，研究的主要內(nèi)容從影響流量調(diào)度的相關(guān)因素(如幀大小[59]、優(yōu)先級(jí)劃分[44,54]、時(shí)間同步[32]、保護(hù)帶[58]、網(wǎng)絡(luò)負(fù)載[63])，直接提升實(shí)時(shí)性，拓展至影響延遲計(jì)算的相關(guān)因素(如路由選擇[52,55]、數(shù)據(jù)壓縮[31]、多幀傳輸[68])，綜合提升實(shí)時(shí)性。各研究多假設(shè)網(wǎng)絡(luò)中各因素為恒定不變量、應(yīng)用范圍多為局域網(wǎng)，從實(shí)際應(yīng)用的需求和確定性網(wǎng)絡(luò)的要求看，研究的廣度和深度需進(jìn)一步拓展。當(dāng)前調(diào)度機(jī)制的研究有如下趨勢：

從研究對(duì)象看，非周期的時(shí)間觸發(fā)流量有待研究。如圖1所示，現(xiàn)有研究實(shí)現(xiàn)了周期流量和突發(fā)流量調(diào)度，但現(xiàn)實(shí)中存在發(fā)送時(shí)間間隔不固定、但發(fā)送時(shí)刻可預(yù)知的非周期的時(shí)間觸發(fā)流量(如預(yù)定時(shí)刻的緊急開關(guān)機(jī)信息)，該類流量調(diào)度研究缺乏。

從研究實(shí)現(xiàn)看，在線動(dòng)態(tài)流量調(diào)度有待研究?，F(xiàn)有算法普遍比較復(fù)雜，進(jìn)行流量調(diào)度規(guī)劃需要花費(fèi)大量時(shí)間，因此現(xiàn)有研究多采取離線靜態(tài)調(diào)度，但考慮到網(wǎng)絡(luò)中動(dòng)態(tài)變化情況，如網(wǎng)絡(luò)拓?fù)渥兓痆69]、“即插即用”等場景導(dǎo)致的流量數(shù)量變化[51]，如何快速實(shí)時(shí)調(diào)度規(guī)劃有待研究[70]。

從研究目標(biāo)看，可擴(kuò)展性、高可靠性流量調(diào)度有待研究。從可擴(kuò)展性看，“即插即用”場景中新增流量[52]將導(dǎo)致流量調(diào)度重新規(guī)劃及復(fù)雜度增加，對(duì)算法效率要求更高。從高可靠性看，網(wǎng)絡(luò)中干擾因素，如傳輸時(shí)延波動(dòng)[50]、周期流量抖動(dòng)[71]、網(wǎng)絡(luò)故障[53,72]，可能導(dǎo)致調(diào)度失敗。另外，實(shí)現(xiàn)低延遲調(diào)度，與帶有一定冗余以保證可靠性的調(diào)度相沖突，二者需要適當(dāng)平衡。

從應(yīng)用范圍看，異構(gòu)網(wǎng)絡(luò)和跨域網(wǎng)絡(luò)的流量調(diào)度有待研究。時(shí)間敏感網(wǎng)絡(luò)相比其他實(shí)時(shí)性網(wǎng)絡(luò)的優(yōu)勢主要在于其兼容性、互操作性，而現(xiàn)有研究主要集中于獨(dú)立于外部網(wǎng)絡(luò)的局域網(wǎng)，缺乏跨域網(wǎng)絡(luò)[66]、異構(gòu)網(wǎng)絡(luò)[73]的流量調(diào)度研究。

從理論驗(yàn)證看，規(guī)范的調(diào)度評(píng)估有待研究。各項(xiàng)研究中，實(shí)驗(yàn)對(duì)象差異較大，如流量的數(shù)量、周期性、幀長度等多不相同，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和帶寬也不盡相同，因此時(shí)間敏感網(wǎng)絡(luò)中進(jìn)行幀層次的微觀調(diào)度，得出的宏觀實(shí)驗(yàn)結(jié)果——端到端延遲，使各研究很難具有可比性。為便于各項(xiàng)研究的效果比較，針對(duì)車載網(wǎng)絡(luò)、航空網(wǎng)絡(luò)、工業(yè)互聯(lián)網(wǎng)、5G通信等不同應(yīng)用場景，設(shè)計(jì)統(tǒng)一規(guī)范的測試評(píng)估平臺(tái)成為迫切需求。

時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度關(guān)注排隊(duì)時(shí)延，并未從根本上實(shí)現(xiàn)所有流量的實(shí)時(shí)性傳輸，而是通過調(diào)度機(jī)制使流量有序傳輸，盡可能避免流量隨機(jī)沖突，以犧牲非關(guān)鍵流量的實(shí)時(shí)性為代價(jià)，確保關(guān)鍵流量的實(shí)時(shí)性。隨著研究的深入，流量調(diào)度的研究將由關(guān)注實(shí)時(shí)性向關(guān)注可擴(kuò)展性、高可靠性發(fā)展，研究對(duì)象更加全面、適用場景更加廣泛，流量調(diào)度的范式日趨成熟，使時(shí)間敏感網(wǎng)絡(luò)成為功能完備的確定性網(wǎng)絡(luò)技術(shù)。