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

張 彤 馮佳琦 馬延瀅 渠思源 任豐原,4

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106)

2(軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心 南京 210093)

3(蘭州大學(xué)信息科學(xué)與工程學(xué)院 蘭州 730000)

4(清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 北京 100084)

(zhangt@nuaa.edu.cn)

當(dāng)前，很多行業(yè)領(lǐng)域都需要確定性低延時(shí)的網(wǎng)絡(luò)連接.例如工業(yè)自動(dòng)化網(wǎng)絡(luò)要求端到端延時(shí)在幾微秒到幾毫秒之間[1]；汽車內(nèi)的自動(dòng)駕駛系統(tǒng)要求車載網(wǎng)絡(luò)的端到端延時(shí)在250 μs以內(nèi)，車內(nèi)電子控制系統(tǒng)更要求不超過10 μs[2]；航空電子全雙工交換以太網(wǎng)(avionics full duplex switched Ethernet, AFDX)則要求128 ms以內(nèi)的端到端延時(shí)[3]等.除延時(shí)性能外，以上應(yīng)用場景還要求幾微秒的延時(shí)抖動(dòng)和極低的丟包率.傳統(tǒng)以太網(wǎng)致力于通過帶寬復(fù)用提高資源利用率，然而缺少確定性傳輸機(jī)制只能提供盡力而為的傳輸服務(wù)，難以滿足上述應(yīng)用場景的傳輸需求.

為了實(shí)現(xiàn)確定性低延時(shí)傳輸，工業(yè)界在標(biāo)準(zhǔn)以太網(wǎng)的基礎(chǔ)上提出了多種專屬網(wǎng)絡(luò)協(xié)議，如實(shí)時(shí)以太網(wǎng)TTEthernet,EtherCAT,PROFINET,SERCOIII等，稱為工業(yè)以太網(wǎng)，逐步成為工業(yè)控制網(wǎng)絡(luò)的主流技術(shù).然而，互不兼容的網(wǎng)絡(luò)技術(shù)導(dǎo)致了應(yīng)用難兼容、互操作性差、不易移植且開發(fā)部署和運(yùn)營維護(hù)成本高等問題.隨著工業(yè)互聯(lián)網(wǎng)的發(fā)展，在日益增長的互聯(lián)互通和確定性網(wǎng)絡(luò)標(biāo)準(zhǔn)化需求的驅(qū)動(dòng)下，IEEE 802將原本致力于滿足帶寬預(yù)留業(yè)務(wù)需求的音/視頻橋接(audio video bridging, AVB)工作組升級為時(shí)間敏感網(wǎng)絡(luò)(time-sensitive networking, TSN)工作組，提出了一系列鏈路層增強(qiáng)機(jī)制與流量策略的標(biāo)準(zhǔn)和規(guī)范，主要包括時(shí)間同步、流量調(diào)度、可靠傳輸和網(wǎng)絡(luò)管理標(biāo)準(zhǔn)，將標(biāo)準(zhǔn)以太網(wǎng)擴(kuò)展為TSN[4].TSN遵循標(biāo)準(zhǔn)的以太網(wǎng)協(xié)議體系，天然具有更好的互聯(lián)互通優(yōu)勢，可以在提供確定性延時(shí)、帶寬保證的同時(shí)，實(shí)現(xiàn)開放的2層轉(zhuǎn)發(fā)[5].因此，TSN可以對相互隔離的工業(yè)控制網(wǎng)絡(luò)進(jìn)行互聯(lián).近年來，TSN作為新一代以太網(wǎng)技術(shù)，在工業(yè)互聯(lián)網(wǎng)、移動(dòng)前傳、航空電子網(wǎng)絡(luò)、車載網(wǎng)絡(luò)、專業(yè)音視頻等多個(gè)領(lǐng)域廣泛應(yīng)用，得到了學(xué)術(shù)界和工業(yè)界的持續(xù)關(guān)注.

流量調(diào)度是TSN標(biāo)準(zhǔn)中的核心機(jī)制.不同類別的業(yè)務(wù)流量對網(wǎng)絡(luò)的端到端延時(shí)和帶寬具有不同的要求.流量調(diào)度通過一定的調(diào)度算法在所有交換機(jī)出端口確定每個(gè)數(shù)據(jù)幀的傳輸順序和時(shí)間，保證所有幀在出口鏈路上依次傳輸而不會發(fā)生沖突，同時(shí)在全網(wǎng)范圍聯(lián)合保證每個(gè)幀能夠順利通過傳輸路徑上的所有出端口，并滿足流量各自的延時(shí)和帶寬要求，使不同類別的業(yè)務(wù)流量在同一網(wǎng)絡(luò)上得以共存[6].

文獻(xiàn)[6]對TSN的關(guān)鍵協(xié)議及應(yīng)用場景進(jìn)行綜述，闡述了時(shí)間同步協(xié)議、調(diào)度與流量整形標(biāo)準(zhǔn)、幀搶占標(biāo)準(zhǔn)、流預(yù)留協(xié)議，以及TSN在車載網(wǎng)絡(luò)、工業(yè)互聯(lián)網(wǎng)、航空電子網(wǎng)絡(luò)和移動(dòng)前傳網(wǎng)絡(luò)中的應(yīng)用場景.文獻(xiàn)[7]對車載嵌入式系統(tǒng)相關(guān)的TSN標(biāo)準(zhǔn)進(jìn)行綜述，包括標(biāo)準(zhǔn)的演進(jìn)、基于模型的分布式軟件開發(fā)、調(diào)度與可調(diào)度性分析、仿真平臺、硬件演進(jìn)和安全性.在調(diào)度與可調(diào)度性分析部分對現(xiàn)有調(diào)度機(jī)制根據(jù)性能目標(biāo)進(jìn)行了簡單分類和描述.本文主要關(guān)注TSN中的流量調(diào)度，將介紹流量調(diào)度的標(biāo)準(zhǔn)框架、網(wǎng)絡(luò)與流量模型、所有調(diào)度約束和可能的調(diào)度目標(biāo)的形式化表征，對流量調(diào)度問題進(jìn)行系統(tǒng)建模；進(jìn)而按照采用的求解算法對現(xiàn)有調(diào)度機(jī)制進(jìn)行全面的分類和詳細(xì)描述，并對TSN流量調(diào)度的研究現(xiàn)狀進(jìn)行分析和總結(jié)；最后討論TSN流量調(diào)度的設(shè)計(jì)空間和發(fā)展趨勢.本文是對文獻(xiàn)[6-7]中流量調(diào)度部分的系統(tǒng)化展開和擴(kuò)展，補(bǔ)充了調(diào)度框架、問題和機(jī)制的細(xì)節(jié).

1 TSN流量調(diào)度標(biāo)準(zhǔn)框架

TSN屬于確定性網(wǎng)絡(luò)，即網(wǎng)絡(luò)中的部分流量必須遵循某種硬實(shí)時(shí)條件的網(wǎng)絡(luò).TSN中實(shí)時(shí)流量的端到端延時(shí)必須小于等于1個(gè)確定值.此外，工業(yè)控制網(wǎng)絡(luò)協(xié)議中使用最為廣泛的TTEthernet也屬于確定性網(wǎng)絡(luò).TTEthernet是為工業(yè)控制網(wǎng)絡(luò)中混合關(guān)鍵性實(shí)時(shí)應(yīng)用所提出的在標(biāo)準(zhǔn)以太網(wǎng)之上的擴(kuò)展機(jī)制.TTEthernet與TSN在很多方面存在相似之處，然而在流量調(diào)度上存在重要區(qū)別[8].本節(jié)首先對比了TSN和TTEthernet流量調(diào)度標(biāo)準(zhǔn)框架，進(jìn)而介紹TSN中固有的流量控制機(jī)制.TSN中的流量調(diào)度必須在標(biāo)準(zhǔn)框架和固有機(jī)制的基礎(chǔ)上運(yùn)行.

1.1 TSN與TTEthernet流量調(diào)度框架

圖1分別展示了TTEthernet交換機(jī)和TSN交換機(jī)，每個(gè)交換機(jī)只畫出了2個(gè)入端口和1個(gè)出端口.流量調(diào)度作用于網(wǎng)絡(luò)中所有交換機(jī)的出端口.TTEthernet和TSN在每個(gè)出端口均使用了8個(gè)優(yōu)先級隊(duì)列，用來標(biāo)記流量的重要程度.二者的區(qū)別在于，TTEthernet交換機(jī)在每個(gè)出端口設(shè)置1個(gè)共享緩沖區(qū)來存放該出端口暫未傳輸?shù)膸?，調(diào)度機(jī)制決定的是幀從緩沖區(qū)進(jìn)入優(yōu)先級隊(duì)列的時(shí)間；而TSN交換機(jī)中共享緩沖區(qū)的位置由優(yōu)先級過濾器代替，幀直接進(jìn)入優(yōu)先級隊(duì)列進(jìn)行緩存.此外，TTEthernet的優(yōu)先級隊(duì)列直連出端口，一旦出端口空閑，隊(duì)列中的幀可立即按優(yōu)先級傳輸；而TSN的每個(gè)優(yōu)先級隊(duì)列通過門電路與出端口相連，只有門開放時(shí)相應(yīng)隊(duì)列中的幀才可按優(yōu)先級傳輸.調(diào)度機(jī)制決定的是不同隊(duì)列門的開閉時(shí)刻.

Fig. 1 Illustration of TTEthernet switch and TSN switch圖1 TTEthernet交換機(jī)與TSN交換機(jī)示意圖

TTEthernet中的每臺交換機(jī)都具備根據(jù)本地實(shí)時(shí)網(wǎng)絡(luò)調(diào)度分配數(shù)據(jù)幀的能力.本地實(shí)時(shí)網(wǎng)絡(luò)調(diào)度可由全局傳輸機(jī)制推導(dǎo)得出，規(guī)定了每個(gè)實(shí)時(shí)數(shù)據(jù)幀在網(wǎng)絡(luò)每一跳的發(fā)送和接收時(shí)間窗口.在交換機(jī)內(nèi)部，實(shí)時(shí)網(wǎng)絡(luò)調(diào)度則規(guī)定了每個(gè)出端口數(shù)據(jù)幀從緩沖區(qū)進(jìn)入優(yōu)先級隊(duì)列的時(shí)刻.不同隊(duì)列之間按嚴(yán)格優(yōu)先級傳輸.實(shí)時(shí)流量與非實(shí)時(shí)流量進(jìn)入不同隊(duì)列進(jìn)行隔離.實(shí)時(shí)流量進(jìn)入高優(yōu)先級隊(duì)列，非實(shí)時(shí)流量進(jìn)入低優(yōu)先級隊(duì)列，以減少對實(shí)時(shí)流量的干擾，保證實(shí)時(shí)流量在交換機(jī)內(nèi)的有界傳輸延時(shí).TTEthernet需要時(shí)間同步協(xié)議SAE AS6802提供全網(wǎng)的統(tǒng)一時(shí)鐘，各交換機(jī)協(xié)同調(diào)度，使得數(shù)據(jù)幀能夠順利地依次通過路徑上的各交換機(jī)，保證實(shí)時(shí)流量端到端延時(shí)也有界.

TSN由精確時(shí)間協(xié)議(precise time protocol, PTP)或通用精確時(shí)間協(xié)議(generic PTP, gPTP)提供全網(wǎng)各節(jié)點(diǎn)的時(shí)鐘同步.在統(tǒng)一時(shí)鐘的基礎(chǔ)上，由端口門控制列表(gate control list, GCL)在不同時(shí)刻開放和關(guān)閉各隊(duì)列出口的門，決定各隊(duì)列是否可以傳輸數(shù)據(jù).GCL可根據(jù)實(shí)時(shí)流量的周期和尺寸離線生成.表中每個(gè)門開放的時(shí)間段稱為時(shí)間窗口，每個(gè)時(shí)間窗口可傳輸1個(gè)或多個(gè)數(shù)據(jù)幀，取決于窗口大小.實(shí)時(shí)流量進(jìn)入高優(yōu)先級隊(duì)列，非實(shí)時(shí)流量進(jìn)入低優(yōu)先級隊(duì)列，在門開放的所有隊(duì)列之間按嚴(yán)格優(yōu)先級傳輸.TSN和TTEthernet在流量調(diào)度上的區(qū)別主要體現(xiàn)在3個(gè)方面：1)流量特性不同.TTEthernet定義的流量類型包括時(shí)間觸發(fā)(time-triggered, TT)流量、速率限制(rate-constrained, RC)流量和盡力而為(best-effort, BE)流量，而TSN定義的流量類型包括TT流量、音視頻橋接(AVB)流量和BE流量.RC流量和AVB流量均為事件觸發(fā)流量，但AVB流量主要傳輸音頻和視頻.TTEthernet的消息只包含1幀，而TSN中每個(gè)消息可能包含多個(gè)幀.2)調(diào)度位置不同.TTEthernet的調(diào)度位于共享緩沖區(qū)，決策的是每個(gè)幀進(jìn)入優(yōu)先級隊(duì)列的時(shí)刻；而TSN的調(diào)度位于優(yōu)先級隊(duì)列出口，決策的是各隊(duì)列的門的開閉時(shí)刻.3)調(diào)度粒度不同.TTEthernet的調(diào)度粒度為單個(gè)數(shù)據(jù)幀，而TSN的調(diào)度粒度為隊(duì)列.由于調(diào)度粒度更粗，TSN在單個(gè)幀傳輸過程中存在一定程度的不確定性，提供的確定性等級低于TTEthernet，但對調(diào)度方案的約束更少，擴(kuò)大了解空間，具有更多的靈活性.

1.2 TSN固有流量控制機(jī)制

所有流量調(diào)度機(jī)制都需要在TSN固有流量控制機(jī)制的基礎(chǔ)上運(yùn)行.因此本節(jié)對TSN中定義的固有流量控制機(jī)制進(jìn)行簡單介紹，主要包括保護(hù)帶機(jī)制、幀搶占機(jī)制和流量整形機(jī)制.

1.2.1 保護(hù)帶機(jī)制

標(biāo)準(zhǔn)以太網(wǎng)未定義搶占機(jī)制，如果1個(gè)數(shù)據(jù)幀已經(jīng)開始在端口傳輸，即使更高優(yōu)先級的幀到達(dá)該端口也必須先等待當(dāng)前幀傳輸完成，這稱為優(yōu)先級反轉(zhuǎn).這種現(xiàn)象使得實(shí)時(shí)幀可能在預(yù)設(shè)的時(shí)間窗口內(nèi)無法完成傳輸，只能等待下個(gè)窗口，又會導(dǎo)致下個(gè)窗口內(nèi)預(yù)設(shè)的其他幀無法完成傳輸.這種連鎖反應(yīng)會造成該出端口及路徑上后續(xù)所有出端口的幀傳輸錯(cuò)亂，大幅增加端到端延時(shí)，導(dǎo)致不確定性.為緩解這種現(xiàn)象，TSN提出了保護(hù)帶機(jī)制，主要有2種實(shí)現(xiàn)方法：1)在每個(gè)實(shí)時(shí)隊(duì)列的時(shí)間窗口前設(shè)置一段所有門全部關(guān)閉的時(shí)間作為保護(hù)帶，長度為最大幀傳輸時(shí)長.保護(hù)帶內(nèi)不允許任何新的幀開始傳輸，但之前已經(jīng)在傳輸?shù)膸稍诒Ｗo(hù)帶內(nèi)繼續(xù)完成傳輸.這樣在實(shí)時(shí)隊(duì)列門開放時(shí)一定不會發(fā)生優(yōu)先級反轉(zhuǎn).2)不顯式設(shè)置保護(hù)帶，而是在每次實(shí)時(shí)隊(duì)列的門開放前進(jìn)行判斷，阻止會干擾實(shí)時(shí)幀傳輸?shù)姆菍?shí)時(shí)幀，防止優(yōu)先級反轉(zhuǎn)的發(fā)生.保護(hù)帶機(jī)制能夠避免非實(shí)時(shí)流量對實(shí)時(shí)流量的干擾，但會同時(shí)引入帶寬浪費(fèi).

1.2.2 幀搶占機(jī)制

IEEE 802.3br[9]和IEEE 802.1Qbu[10]標(biāo)準(zhǔn)共同定義了幀搶占機(jī)制以解決優(yōu)先級反轉(zhuǎn)問題.IEEE 802.3br定義了MAC合并子層，以及幀搶占的切片操作、切片還原和驗(yàn)證等核心功能.IEEE 802.1Qbu則提供了搶占接口及模塊級別的定義.若端口上高優(yōu)先級幀到達(dá)時(shí)低優(yōu)先級幀正在傳輸，首先判斷低優(yōu)先級幀已傳輸?shù)牟糠趾褪Ｓ嗖糠质欠窬笥诘扔谝蕴W(wǎng)的最小幀長(60 B)，若滿足則允許切片操作：中斷低優(yōu)先級幀的傳輸，并將低優(yōu)先級幀已傳輸?shù)牟糠盅a(bǔ)上校驗(yàn)和組裝成完整的幀，然后在1個(gè)幀間隙后傳輸高優(yōu)先級幀，待高優(yōu)先級幀傳輸完成后低優(yōu)先級幀剩余部分補(bǔ)全為完整的幀繼續(xù)傳輸.與保護(hù)帶機(jī)制相比，幀搶占機(jī)制減少了帶寬浪費(fèi)，但是會引入不可避免的操作開銷.此外，搶占機(jī)制需要專用的硬件結(jié)構(gòu)支持，增加了硬件復(fù)雜度；不滿足切片條件的情況下無法實(shí)施搶占操作，不能完全消除優(yōu)先級反轉(zhuǎn)問題.

1.2.3 流量整形機(jī)制

流量整形的主要功能是限制網(wǎng)絡(luò)中的突發(fā)流量，將突發(fā)流量以較為均勻的速率向外發(fā)送可以減少網(wǎng)絡(luò)擁塞并降低丟包率.TSN固有的流量整形機(jī)制主要包括時(shí)間感知整形器(time-aware shaper, TAS)、基于信用值的整形器(credit-based shaper, CBS)、循環(huán)排隊(duì)和轉(zhuǎn)發(fā)(cyclic queuing and forwarding, CQF)和異步流量整形器(asynchronous traffic shaping, ATS).

TAS由IEEE 802.1Qbv標(biāo)準(zhǔn)定義[11]，在GCL的時(shí)間窗口中調(diào)度不同優(yōu)先級隊(duì)列的流量傳輸.在全網(wǎng)時(shí)鐘同步的條件下，TAS中GCL周期性地控制各隊(duì)列出口門的開閉，并且每一時(shí)刻在所有門開放的隊(duì)列中按照嚴(yán)格的優(yōu)先級進(jìn)行傳輸.TAS的基本思想是時(shí)分多址(time division multiple access, TDMA)技術(shù)，為不同隊(duì)列分配不重疊的傳輸時(shí)隙，使流量傳輸速率匹配出口鏈路帶寬的同時(shí)對不同優(yōu)先級的流量進(jìn)行隔離，減少低優(yōu)先級流量對高優(yōu)先級流量的干擾.由于需要時(shí)間同步操作且門控列表的配置較為復(fù)雜，TAS在擴(kuò)展性方面存在挑戰(zhàn).

CBS由IEEE 802.1Qav標(biāo)準(zhǔn)定義[12]，是一種常用的網(wǎng)絡(luò)流量整形算法，在TSN中作用于AVB流量.CBS賦予每個(gè)AVB隊(duì)列1個(gè)信用值，初始為0.當(dāng)隊(duì)列中AVB幀傳輸時(shí)，信用值以發(fā)送率為斜率線性降低；當(dāng)隊(duì)列中AVB幀等待時(shí)，信用值以空閑率為斜率線性增長；當(dāng)AVB隊(duì)列出口的門為關(guān)閉狀態(tài)時(shí)，信用值保持不變；當(dāng)AVB隊(duì)列為空而信用值大于0時(shí)，將信用值重置為0.只有當(dāng)隊(duì)列的信用值非負(fù)時(shí)，AVB幀才可開始傳輸.CBS通常與TAS聯(lián)合使用，因此AVB幀開始傳輸需要滿足3個(gè)條件：1)隊(duì)列出口門開放；2)隊(duì)列信用值非負(fù)；3)門開放的更高優(yōu)先級隊(duì)列中無數(shù)據(jù)傳輸.CBS在TAS的基礎(chǔ)上進(jìn)一步對AVB流量的傳輸進(jìn)行整形，降低了AVB流量的突發(fā)并緩解了更低優(yōu)先級隊(duì)列的饑餓.

CQF由IEEE 802.1Qch標(biāo)準(zhǔn)定義[13]，主要解決幀傳輸?shù)挠薪缪訒r(shí)問題.橋接網(wǎng)絡(luò)基礎(chǔ)標(biāo)準(zhǔn)802.1Q[3]指定的延時(shí)敏感流的轉(zhuǎn)發(fā)和排隊(duì)機(jī)制中最壞情況的端到端延時(shí)與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)密切相關(guān)，難以實(shí)現(xiàn)延時(shí)敏感流量所要求的有界延時(shí).為解決此問題，CQF以循環(huán)的方式協(xié)調(diào)交換機(jī)的入隊(duì)和出隊(duì)操作.CQF將時(shí)間分為等長的周期，且所有交換機(jī)的周期對齊.每個(gè)流量等級使用2個(gè)隊(duì)列，偶數(shù)周期內(nèi)隊(duì)列1接收新到達(dá)的幀而不傳輸幀，隊(duì)列2傳輸上一周期到達(dá)的幀而不接收新的幀；奇數(shù)周期內(nèi)，隊(duì)列2接收新到達(dá)的幀而不傳輸幀，隊(duì)列1傳輸上一周期到達(dá)的幀而不接收新的幀.因此在第i周期到達(dá)的幀將在第i+1周期內(nèi)傳輸，且必須在該周期內(nèi)被下一跳交換機(jī)接收.需要精確設(shè)置周期長度，既保證周期內(nèi)所有幀能順利傳輸至下一跳，又不會造成過長的延時(shí).通過CQF，最壞情況的端到端延時(shí)只與周期長度和網(wǎng)絡(luò)跳數(shù)有關(guān)，與拓?fù)浣Y(jié)構(gòu)無關(guān)，上下界均很容易計(jì)算.

ATS由IEEE 802.1Qcr標(biāo)準(zhǔn)定義[14]，是基于緊迫度調(diào)度器(urgency-based scheduler, UBS)[15]的異步整形機(jī)制，適用于滿足漏桶速率限制的所有周期或非周期流量，即任意時(shí)間間隔d內(nèi)，流si的累計(jì)數(shù)據(jù)量wi(d)≤bi+rid，bi為突發(fā)程度，ri為漏桶速率.ATS在每個(gè)出端口設(shè)置2層隊(duì)列：整形隊(duì)列和優(yōu)先隊(duì)列.每個(gè)整形隊(duì)列設(shè)單獨(dú)的整形器，能夠?qū)﹃?duì)列中的多條流進(jìn)行交叉整形；優(yōu)先隊(duì)列決定輸出流量的優(yōu)先級，隊(duì)列與優(yōu)先級一一對應(yīng).到達(dá)出端口的流量先進(jìn)入整形隊(duì)列，整形器為隊(duì)中的每條流單獨(dú)維護(hù)一個(gè)時(shí)間戳，記錄該流最近一次傳輸幀的時(shí)刻，并采用漏桶算法或令牌桶算法確定下一幀的傳輸時(shí)刻，以此限制每條流的傳輸速率.每條優(yōu)先隊(duì)列從所有整形隊(duì)列的出口收集相應(yīng)優(yōu)先級的流量，隊(duì)列間按嚴(yán)格優(yōu)先級傳輸.ATS中每個(gè)交換機(jī)根據(jù)本地時(shí)間對流量進(jìn)行整形和優(yōu)先級調(diào)度，不需要全局時(shí)鐘同步，因此在擴(kuò)展性上優(yōu)于TAS,CBS,CQF.

2 TSN流量調(diào)度問題

本節(jié)主要介紹TSN流量調(diào)度的形式化問題，包括TSN網(wǎng)絡(luò)模型、流量模型、調(diào)度約束和調(diào)度目標(biāo).TSN流量調(diào)度問題有2類形式化方法：1)以幀為調(diào)度對象，計(jì)算每一幀在經(jīng)過的所有出端口的隊(duì)列分配及傳輸開始時(shí)刻；2)以時(shí)間窗口為調(diào)度對象，計(jì)算每一幀在所有出端口上的時(shí)間窗口分配以及所有時(shí)間窗口的開放和關(guān)閉時(shí)刻.可以看出，第1類問題求解的是TTEthernet的調(diào)度對象，第2類問題求解的是TSN的調(diào)度對象.然而，第1類問題的調(diào)度結(jié)果可直接轉(zhuǎn)化為第2類問題的結(jié)果，反之則不成立.通過隊(duì)列中所有幀的傳輸開始時(shí)刻和幀大小可推導(dǎo)出該隊(duì)列傳輸幀的所有時(shí)段，即時(shí)間窗口；但已知時(shí)間窗口的開閉時(shí)刻并不能確定窗口內(nèi)每一幀的傳輸時(shí)間.因此第1類形式化問題更加精確，并且同時(shí)適用于TTEthernet和TSN.可見盡管TTEthernet與TSN的實(shí)際調(diào)度框架存在顯著區(qū)別，但在形式化的調(diào)度問題是一致的.本文即介紹此類形式化調(diào)度問題.

2.1 網(wǎng)絡(luò)與流量模型

將網(wǎng)絡(luò)抽象為有向圖G=(V,E)，如圖2所示.V為點(diǎn)集，表示網(wǎng)絡(luò)中的交換機(jī)(switch， SW)和端系統(tǒng)(end system, ES).圖2包括2個(gè)交換機(jī)和4個(gè)端系統(tǒng)，每個(gè)交換機(jī)有多個(gè)入端口和出端口，負(fù)責(zé)根據(jù)目的地址將入端口的幀轉(zhuǎn)發(fā)至對應(yīng)出端口；端系統(tǒng)可以是傳感器、執(zhí)行器、電子控制單元，通常包含CPU、內(nèi)存和網(wǎng)卡.E?V×V為邊集，其中每個(gè)元素代表1條單向鏈路.TSN建立在全雙工以太網(wǎng)之上，節(jié)點(diǎn)va與vb間的物理鏈路對應(yīng)2條單向鏈路[va,vb]和[vb,va].每條單向鏈路[va,vb]由三元組cab,dab,nab定義，分別表示該鏈路的帶寬容量、傳播延時(shí)以及相連的出端口隊(duì)列數(shù).在TSN標(biāo)準(zhǔn)中，端系統(tǒng)出口鏈路nab=1，而交換機(jī)出口鏈路nab=8.

Fig. 2 TSN network model圖2 TSN網(wǎng)絡(luò)模型

TSN中的流量包括TT流、AVB流和BE流，傳輸優(yōu)先級依次降低.TT流量用于具有嚴(yán)格時(shí)間約束的實(shí)時(shí)應(yīng)用，需要確定性低延時(shí)保證；AVB流量用于軟實(shí)時(shí)應(yīng)用，提供有界的最壞情況端到端延時(shí)，但比TT流量的延時(shí)約束寬松；BE流量為傳統(tǒng)的以太網(wǎng)流量，無任何延時(shí)保證.其中TT流為周期性數(shù)據(jù)傳輸，周期長度和數(shù)據(jù)大小由應(yīng)用預(yù)先定義，為已知量；而AVB流和BE流為非周期性隨機(jī)數(shù)據(jù)傳輸，到達(dá)間隔與數(shù)據(jù)大小均為未知量.由于TSN的流量調(diào)度為離線操作，無法處理未知的AVB和BE流量，因此只對TT流進(jìn)行形式化定義.從發(fā)送端vi1經(jīng)過中間節(jié)點(diǎn)vi2，…,vi(ni-1)到達(dá)接收端vini的TT流si，其路徑Ri可表示為[[vi1,vi2],[[vi2,vi3],…,[vi(ni-1),vini]].每條si可采用四元組Li,Ji,Si,Ti定義，分別表示該流所能容忍的最大端到端延時(shí)、最大延時(shí)抖動(dòng)、每周期發(fā)送的數(shù)據(jù)量和周期長度.定義表示通過鏈路[va,vb]的流集合，則鏈路[va,vb]的超周期為通過該鏈路所有TT流周期的最小公倍數(shù).如圖3所示，流s1的周期為100 μs，流s2的周期為150 μs，則2條流共同鏈路的超周期為300 μs.調(diào)度機(jī)制只需確定1個(gè)超周期的GCL并在多個(gè)超周期間循環(huán)執(zhí)行.則表示si在與鏈路[vb,va]相連的出端口上的隊(duì)列分配，因此有pi[va,vb]≤nab.

Fig. 3 TT schedule synthesis example圖3 TT流調(diào)度實(shí)例

以圖2中的網(wǎng)絡(luò)和表1中的流量為例，s1的路徑為[[ES1,SW1],[SW1,SW2],[SW2,ES3]]，s2的路徑為[[ES2,SW1],[SW1,SW2],[SW2,ES4]]，2條流在鏈路[SW1,SW2]上存在爭用；s1的周期為100 μs，大小為1 500 B，即1個(gè)MTU，s2的周期為150 μs，大小為4 500 B，即3個(gè)MTU，2條流所能容忍的最大端到端延時(shí)均為2 ms，最大延時(shí)抖動(dòng)均為5 μs.假設(shè)鏈路傳播延時(shí)與交換機(jī)處理延時(shí)均為1 μs，所有鏈路帶寬均為1 Gbps，則每個(gè)幀的傳輸延時(shí)為12.336 μs.圖3采用甘特圖展示了一種可行調(diào)度方案.橫坐標(biāo)表示時(shí)間，縱坐標(biāo)表示鏈路，矩形表示幀傳輸實(shí)例.

Table 1 Flow Instance表1 流量實(shí)例

2.2 調(diào)度約束

其中,α=0,1，β=0,1,2.

即同一幀在后繼鏈路上傳輸實(shí)例的開始時(shí)刻必須大于等于前驅(qū)鏈路上傳輸實(shí)例的完成時(shí)刻，即前驅(qū)鏈路上的開始時(shí)刻、傳輸延時(shí)、傳播延時(shí)之和.dax為鏈路[va,vx]的傳播延時(shí)，pa為節(jié)點(diǎn)va的處理延時(shí)，δ為全網(wǎng)內(nèi)時(shí)鐘偏差的最大值，用于在時(shí)鐘同步存在誤差的情況下保證鏈路傳輸?shù)臅r(shí)序.以圖3中的s1為例，其幀傳輸實(shí)例在3條鏈路上的開始時(shí)間需滿足:

4) 延時(shí)約束.該約束闡述了實(shí)時(shí)流量的端到端延時(shí)約束.對S中的?si=Li,Ji,Si,Ti，其路徑Ri=[[vi1,vi2],[[vi2,vi3],…,[vi(ni-1),vini]]，Ni=表示si每次發(fā)送的消息所包含的幀數(shù)，有：

消息最后一幀到達(dá)接收端的時(shí)刻與第1幀在發(fā)送端傳輸開始時(shí)刻之間的時(shí)間間隔即為端到端延時(shí)，必須小于等于流si能容忍的最大端到端延時(shí)Li.滿足延時(shí)約束的流稱為可調(diào)度的，反之則稱為不可調(diào)度的.以圖3中的s1為例，需要滿足:

5) 抖動(dòng)約束.該約束闡述了實(shí)時(shí)流量的延時(shí)抖動(dòng)約束.對S中的?si=Li,Ji,Si,Ti，其路徑Ri=[[vi1,vi2],[[vi2,vi3],…,[vi(ni-1),vini]]，Ni=表示si每次發(fā)送的消息所包含的幀數(shù)，Di為消息從發(fā)送端到最后一跳之前的總傳輸、傳播和處理延時(shí)，有：

同一隊(duì)列中的任意2條流之間，只有當(dāng)1條流的幀全部離開隊(duì)列，另一條流的幀才可以開始進(jìn)入隊(duì)列；若2條流被分配至不同隊(duì)列中，則無此要求.以圖3中的s1,s2為例，在進(jìn)入交換機(jī)SW1時(shí)需同時(shí)滿足:

其中,α=0,1，β=0,1,2.

2.3 調(diào)度目標(biāo)

流量調(diào)度在滿足2.2節(jié)約束條件的同時(shí)優(yōu)化傳輸性能.由于TSN支持的應(yīng)用種類繁多，對網(wǎng)絡(luò)性能要求多樣，流量調(diào)度也有著不同的優(yōu)化目標(biāo).列出當(dāng)前常用的TSN流量調(diào)度優(yōu)化目標(biāo)：

1) 最小化端到端延時(shí).一種典型的目標(biāo)為最小化實(shí)時(shí)流量的端到端延時(shí).盡管實(shí)時(shí)流量具有明確的延時(shí)上界，但部分實(shí)時(shí)應(yīng)用期望在此基礎(chǔ)上進(jìn)一步減小該延時(shí)以加速應(yīng)用運(yùn)行，因此有：

即最小化所有實(shí)時(shí)流端到端延時(shí)之和.

2) 最小化實(shí)時(shí)流量占用隊(duì)列數(shù).從幀隔離約束中可看出，若2條流被分配至同一隊(duì)列，則需要在時(shí)間上進(jìn)行隔離；若分配至不同隊(duì)列，則2條流已經(jīng)在空間上隔離，無需時(shí)間上的隔離.時(shí)間上的隔離為滿足實(shí)時(shí)流量的端到端延時(shí)約束帶來壓力，減小了實(shí)時(shí)流量傳輸?shù)慕饪臻g.空間上的隔離能夠避免該問題，但同時(shí)會增加實(shí)時(shí)流量占用的隊(duì)列.然而，TSN中還存在AVB和BE流量，這些非實(shí)時(shí)流量通過使用更多隊(duì)列能夠顯著提升時(shí)間性能和靈活性.因此在混合流量的TSN中，一種優(yōu)化目標(biāo)為在滿足實(shí)時(shí)流量延時(shí)約束的前提下最小化其占用的隊(duì)列數(shù)，將更多隊(duì)列留給非實(shí)時(shí)流量，適用于同時(shí)關(guān)注非實(shí)時(shí)流量性能的場景.令κ[va,vb]表示出端口實(shí)時(shí)流量所需隊(duì)列數(shù)，有：

即最小化全網(wǎng)所有交換機(jī)中實(shí)時(shí)流量占用的總隊(duì)列數(shù)，同時(shí)引入約束：對?[va,vb]∈E,si∈S，有：

3) 最小化總傳輸時(shí)長.在實(shí)時(shí)流量未傳輸?shù)乃袝r(shí)隙，由AVB和BE流量按嚴(yán)格優(yōu)先級傳輸以填充帶寬.每個(gè)出端口的GCL中，非實(shí)時(shí)隊(duì)列的開放時(shí)間可由所有實(shí)時(shí)隊(duì)列開放時(shí)間的并集取反得到，在此期間非實(shí)時(shí)隊(duì)列中緩存的流量按嚴(yán)格優(yōu)先級傳輸.在非搶占場景中，每次實(shí)時(shí)隊(duì)列開放前均需設(shè)置保護(hù)帶，是TSN帶寬浪費(fèi)的主要來源.并且若實(shí)時(shí)隊(duì)列頻繁開放和關(guān)閉，會導(dǎo)致非實(shí)時(shí)隊(duì)列的傳輸時(shí)隙碎片化，甚至由于時(shí)隙過小無法傳輸完整的幀，同時(shí)也會使GCL過長，對交換機(jī)內(nèi)存造成壓力.因此，應(yīng)當(dāng)在滿足實(shí)時(shí)傳輸約束的條件下盡可能減小門開放的次數(shù)，將實(shí)時(shí)流量合并至盡可能少的時(shí)間窗口內(nèi)傳輸.為實(shí)現(xiàn)該目的，一種常用的優(yōu)化目標(biāo)為最小化實(shí)時(shí)流量的總傳輸時(shí)長.由于實(shí)時(shí)流量為固定模式的周期流量，最小化總傳輸時(shí)長即等價(jià)于最小化保護(hù)帶寬、最小化門開放次數(shù)以及最小化GCL長度，同時(shí)提高帶寬利用率、非實(shí)時(shí)隊(duì)列傳輸時(shí)隙，減小內(nèi)存壓力.總傳輸時(shí)長為所有實(shí)時(shí)流傳輸完成時(shí)刻的最大值，有：

每幀的完成時(shí)間cij減去該幀在通過的所有鏈路上的傳輸延時(shí)和傳播延時(shí)即為該幀在所有交換機(jī)中的緩存時(shí)間，該目標(biāo)最小化網(wǎng)絡(luò)中所有幀的總緩存時(shí)間.

以上優(yōu)化目標(biāo)分別反映了TSN應(yīng)用或網(wǎng)絡(luò)本身所要求的性能指標(biāo)，既可單目標(biāo)優(yōu)化也可結(jié)合多目標(biāo)共同優(yōu)化.多目標(biāo)優(yōu)化可以采用加權(quán)、Pareto前沿、字典序優(yōu)先級等方法處理不同目標(biāo)的優(yōu)先級.

3 TSN流量調(diào)度機(jī)制

在定義流量調(diào)度問題后，需要對該問題進(jìn)行求解以得到流量傳輸方案和GCL.GCL的合成已被證明是NP完全問題，本節(jié)詳細(xì)介紹TSN流量調(diào)度機(jī)制，所采用的求解算法可以分為5類：整數(shù)線性規(guī)劃(integer linear programming, ILP)、啟發(fā)式算法(heuristic)、可滿足性模理論(satisfiability modulo theories, SMT)/優(yōu)化模理論(optimization modulo theories, OMT)、禁忌搜索(tabu search, TS)和貪心隨機(jī)自適應(yīng)搜索(greedy randomized adaptive search procedure, GRASP).ILP為數(shù)學(xué)優(yōu)化方法，通過遍歷約束條件定義的整個(gè)解空間可獲得理論最優(yōu)解，但求解時(shí)間與變量數(shù)成指數(shù)關(guān)系，存在擴(kuò)展性問題，適用于小規(guī)模網(wǎng)絡(luò)尋找最優(yōu)解；啟發(fā)式算法根據(jù)一定規(guī)則每次將1條流加入GCL中，直到所有流都被調(diào)度或某條流不可調(diào)度.由于只需探索一種流順序空間，啟發(fā)式算法具有多項(xiàng)式求解時(shí)間，但無法獲得最優(yōu)解也不能保證解的質(zhì)量，主要適用于TT流量負(fù)載較低的大規(guī)模網(wǎng)絡(luò).SMT/OMT,TS,GRASP屬于元啟發(fā)式算法，求解質(zhì)量和速度介于ILP和啟發(fā)式算法之間，從初始解開始通過迭代搜索解空間提升解的質(zhì)量，無需探索整個(gè)解空間，能夠在可接受的求解時(shí)間內(nèi)獲得較高質(zhì)量的解，適用于大規(guī)模網(wǎng)絡(luò)尋找近似最優(yōu)解.3種元啟發(fā)式算法的區(qū)別在于初始解生成和搜索的規(guī)則不同，OMT通過SMT檢驗(yàn)和區(qū)域搜索探索整個(gè)解空間，迭代次數(shù)多但可獲得最優(yōu)解；TS和GRASP達(dá)到終止條件即停止迭代，保證較低的求解時(shí)間但只能獲得探索過的最優(yōu)解.也有調(diào)度機(jī)制采用以上多種方法的復(fù)合方法對調(diào)度問題進(jìn)行求解.表2列出了5種求解算法的優(yōu)勢、缺點(diǎn)和適用場景，具體算法將在每一類機(jī)制中詳細(xì)闡述.

Table 2 Scheduling Algorithm Comparison表2 調(diào)度算法對比

3.1 基于ILP的流量調(diào)度機(jī)制

ILP是由整數(shù)變量、線性目標(biāo)函數(shù)和線性不等式約束組成的數(shù)學(xué)規(guī)劃.線性不等式構(gòu)成定義完整解空間的多面體，可行解為其中的整數(shù)點(diǎn).在最小化問題中，最優(yōu)解為取得最小目標(biāo)函數(shù)值的可行解，在最大化問題中則為取得最大目標(biāo)函數(shù)值的可行解.ILP的求解方法為遍歷所有可行解以尋找最優(yōu)解，盡管可采用分支定界等技術(shù)限制解空間的探索次數(shù)，但最壞情況下依然需要枚舉所有可行解.在TSN流量調(diào)度問題中，求解時(shí)間與變量數(shù)成指數(shù)關(guān)系，因此ILP存在可擴(kuò)展性問題，主要適用于小規(guī)模問題尋找最優(yōu)解.

3.2 基于啟發(fā)式算法的流量調(diào)度機(jī)制

啟發(fā)式流量調(diào)度的核心思想為貪心算法：從空白的GCL開始，每次調(diào)度1條流，以最優(yōu)化當(dāng)前性能指標(biāo)為原則確定該流的調(diào)度方案并寫入相關(guān)的GCL中；對所有流依次調(diào)度，已調(diào)度流的方案作為未調(diào)度流的先驗(yàn)條件；直到所有流均被調(diào)度或某條流不可調(diào)度時(shí)，算法停止并返回最新的GCL.啟發(fā)式算法每次調(diào)度只需探索很小的解空間，并且調(diào)度次數(shù)為有限值，求解時(shí)間較??；但由于調(diào)度每條流時(shí)并未考慮后續(xù)流，可能做出不恰當(dāng)?shù)臎Q策導(dǎo)致全局次優(yōu)解，解空間的縮小也可能令本可調(diào)度的流變?yōu)椴豢烧{(diào)度.因此，啟發(fā)式算法主要適用于TT流量負(fù)載較低的大規(guī)模問題.

文獻(xiàn)[16]中TT流按截止時(shí)間排序，截止時(shí)間相同的流按周期從小到大排序，依次進(jìn)行調(diào)度.以最小化TT流占用的隊(duì)列數(shù)為第1目標(biāo)，在調(diào)度每條流時(shí)首先將其分配至所有出端口的第1隊(duì)列；在該隊(duì)列分配下以最小化延時(shí)為第2目標(biāo)，采用盡快傳輸策略從發(fā)送端鏈路到接收端鏈路依次確定最早的滿足鏈路順序約束且與已調(diào)度流無沖突的傳輸時(shí)間；若端到端延時(shí)不大于該流截止時(shí)間，則調(diào)度成功并寫入可行解，否則將該流重新分配至下一隊(duì)列并重復(fù)盡早傳輸策略(as soon as possible, ASAP)，直到該流成功調(diào)度或遍歷所有隊(duì)列均不可調(diào)度.所有流可調(diào)度時(shí)返回整體調(diào)度方案，否則僅返回部分可行的調(diào)度方案，整個(gè)過程具有多項(xiàng)式運(yùn)行時(shí)間.文獻(xiàn)[19]關(guān)注TSN的保護(hù)帶問題，在已知GCL的基礎(chǔ)上利用非實(shí)時(shí)幀填充其中的保護(hù)帶以提高帶寬利用率.針對每段保護(hù)帶，以最大化填充幀的總優(yōu)先級或總大小為目標(biāo)，在保護(hù)帶容量約束下，構(gòu)造帶有順序約束的背包問題.首先提出基于動(dòng)態(tài)規(guī)劃的理想求解算法，為減小求解時(shí)間復(fù)雜度進(jìn)而提出基于貪心算法的快速求解算法，依次從所有非實(shí)時(shí)隊(duì)列頭部選擇優(yōu)先級或尺寸最大的幀進(jìn)行填充，實(shí)現(xiàn)了保護(hù)帶的充分利用；最后分別提出基于比較二叉樹結(jié)構(gòu)和有序列表結(jié)構(gòu)的硬件調(diào)度器實(shí)現(xiàn)該快速算法.文獻(xiàn)[20]改進(jìn)了TSN交換機(jī)的隊(duì)列結(jié)構(gòu)，通過增加出端口隊(duì)列將非實(shí)時(shí)流量隊(duì)列擴(kuò)展為由多條隊(duì)列組成的隊(duì)列集，并設(shè)定閾值將同一優(yōu)先級的非實(shí)時(shí)幀根據(jù)大小分配至不同隊(duì)列中，修改GCL將擴(kuò)展的隊(duì)列與原隊(duì)列采用優(yōu)先級調(diào)度器共同調(diào)度.由于對非實(shí)時(shí)隊(duì)列進(jìn)行了細(xì)粒度劃分，幀尺寸較小的隊(duì)列其保護(hù)帶也能夠進(jìn)一步減小，對帶寬利用率的提高有很大幫助.文獻(xiàn)[21-22]關(guān)注計(jì)算任務(wù)與流量的整體調(diào)度，在文獻(xiàn)[18]的基礎(chǔ)上進(jìn)一步開放了計(jì)算任務(wù)的節(jié)點(diǎn)放置以及路由選擇.文獻(xiàn)[21]以計(jì)算任務(wù)節(jié)點(diǎn)和TT流的路徑組合作為基因組，以所有TT流的總傳輸時(shí)長作為適應(yīng)度函數(shù)，以單點(diǎn)交叉算子生成種群，采用遺傳算法求解計(jì)算節(jié)點(diǎn)、路由和GCL的聯(lián)合調(diào)度方案.文獻(xiàn)[22]將計(jì)算任務(wù)按通信量從小到大排序，依次為每個(gè)任務(wù)規(guī)劃其計(jì)算節(jié)點(diǎn)、通信流的路徑和每一跳的傳輸時(shí)間.以最小化TT流總傳輸時(shí)長為目標(biāo)，采用啟發(fā)式列表調(diào)度算法依次遍歷任務(wù)可行的計(jì)算節(jié)點(diǎn)，進(jìn)而在每個(gè)節(jié)點(diǎn)規(guī)劃下遍歷通信流的可選路徑，在每條路徑上計(jì)算與已規(guī)劃流不沖突的最早可傳輸時(shí)間，選擇完成時(shí)間最小的節(jié)點(diǎn)、路徑和傳輸時(shí)間作為該任務(wù)的聯(lián)合調(diào)度方案.

3.3 基于SMT/OMT的流量調(diào)度機(jī)制

SMT是求解約束滿足問題的一種元啟發(fā)式理論方法，用于判斷由邏輯或數(shù)學(xué)語言(如線性整數(shù)代數(shù)、位向量代數(shù))組成的一階公式能否成立，若可以成立則給出一組使得公式成立的變量取值(稱為真值指派).在優(yōu)化問題求解中SMT通常用于檢驗(yàn)約束條件能否滿足，真值指派即對應(yīng)可行解.OMT將SMT作為基礎(chǔ)組成部分，能夠在給出滿足約束的變量取值基礎(chǔ)上找到最小化目標(biāo)函數(shù)的最優(yōu)解.

基于SMT/OMT的TSN流量調(diào)度機(jī)制將調(diào)度問題的每個(gè)約束條件看作一個(gè)子句，改寫為不等式的析取范式，將所有約束條件用合取符號連接作為SMT要求的合取范式.Steiner等人[8,23-26]在該方向進(jìn)行了持續(xù)研究，提出了一系列基于SMT/OMT的流量調(diào)度機(jī)制.文獻(xiàn)[8,23]將調(diào)度變量均定義為整數(shù)，采用SMT搜索滿足約束條件的調(diào)度方案.為提高算法的可擴(kuò)展性，在SMT中引入增量回溯算法：每次將一條流的變量和約束加入SMT公式，檢驗(yàn)最新的約束集是否成立，一旦找到可行解即將其固定為常數(shù)，并繼續(xù)加入新的流；若加入新流后無可行解則進(jìn)行回溯，在更大的取值空間內(nèi)搜索可行解；重復(fù)以上過程直到所有流均被調(diào)度或判斷原問題無可行解.該方法減小了SMT的平均檢驗(yàn)次數(shù)，在實(shí)時(shí)流量負(fù)載較低的場景中顯著提高了算法性能.文獻(xiàn)[24]同樣采用SMT搜索可行調(diào)度方案，同時(shí)提出了分解的SMT進(jìn)一步提高對約束條件數(shù)量的可擴(kuò)展性.將實(shí)時(shí)幀按固定數(shù)量分為不同子集，將子集的變量和約束構(gòu)成獨(dú)立的SMT公式，依次采用SMT搜索可行解，不同子集的幀傳輸時(shí)間不重疊；若某個(gè)子集無可行解，則可直接判斷原問題不可調(diào)度.該方法相比增量回溯具有更快的求解速度，但禁止不同子集中幀和時(shí)隙的穿插利用，也相應(yīng)地降低了調(diào)度方案的品質(zhì).文獻(xiàn)[25]進(jìn)而在靜態(tài)的實(shí)時(shí)流量調(diào)度中引入周期性的固定時(shí)間片傳輸非實(shí)時(shí)流量.一方面在實(shí)時(shí)流量調(diào)度問題中增加約束條件定義恰當(dāng)?shù)目臻e間隔，規(guī)定實(shí)時(shí)幀均不在該間隔內(nèi)傳輸，并采用SMT搜索引入空閑間隔后的調(diào)度方案；另一方面在GCL合成后對其進(jìn)行后處理，在不破壞原始約束的條件下增大GCL的循環(huán)周期，引入更多空閑間隔，進(jìn)一步幫助非實(shí)時(shí)流量降低延時(shí).文獻(xiàn)[26]采用的是以時(shí)間窗口為調(diào)度對象的形式化方法，調(diào)度變量為幀到窗口的分配以及窗口開閉時(shí)刻；將每條鏈路上時(shí)間窗口的開/閉時(shí)刻按序?qū)懭霐?shù)組，將約束條件用一階數(shù)組理論的語法和運(yùn)算符表示，采用OMT搜索變量取值空間，給出最小化所有實(shí)時(shí)流延時(shí)抖動(dòng)加權(quán)和的最優(yōu)解.文獻(xiàn)[27]革新了現(xiàn)有調(diào)度算法以鏈路超周期作為GCL時(shí)長的現(xiàn)狀，提出以基本周期循環(huán)GCL，即鏈路所有TT流周期的最大公約數(shù).每個(gè)基本周期內(nèi)GCL的開閉完全一致，保證每條流在其自身周期內(nèi)到達(dá)后均能通過端口.依次在網(wǎng)絡(luò)中每個(gè)出端口局部應(yīng)用SMT計(jì)算滿足調(diào)度約束的時(shí)間窗口分配，遍歷所有出端口后形成全局調(diào)度方案，相比全局SMT求解大幅減小了計(jì)算開銷.文獻(xiàn)[28]同時(shí)考慮TT流和BE流，提出了松弛時(shí)間的概念，即在每個(gè)TT幀傳輸之后引入一段空白時(shí)隙用來傳輸BE幀，針對松弛時(shí)間引入新的調(diào)度約束，規(guī)定同一鏈路上不同流的幀傳輸時(shí)間和松弛時(shí)間均不重疊、鏈路總松弛時(shí)間具有給定的上下界等，并以最大化松弛時(shí)間為目標(biāo)調(diào)度TT流，采用OMT求解調(diào)度方案，在保證TT流延時(shí)約束的條件下降低BE流的延時(shí).文獻(xiàn)[29-30]提出任務(wù)與流量的整體調(diào)度機(jī)制，將應(yīng)用建模為端系統(tǒng)上的計(jì)算任務(wù)與網(wǎng)絡(luò)流量傳輸?shù)男蛄?將計(jì)算任務(wù)的截止時(shí)間約束、順序約束、無沖突約束等與流量傳輸約束合并，構(gòu)成統(tǒng)一的混合整數(shù)線性規(guī)劃問題，并采用SMT算法求解最小化應(yīng)用響應(yīng)時(shí)間的整體調(diào)度方案.

3.4 基于TS的流量調(diào)度機(jī)制

TS也為元啟發(fā)式算法，其核心思想是在解空間中引導(dǎo)式搜索最小化代價(jià)函數(shù)的可行調(diào)度方案.從初始解開始，通過遷移不斷生成臨近解來探索解空間；若當(dāng)前解的代價(jià)函數(shù)小于歷史最優(yōu)解，則將其存儲為當(dāng)前最優(yōu)解；為防止陷入局部最優(yōu)解，TS采用禁忌表存儲產(chǎn)生歷史最優(yōu)解的遷移，避免重復(fù)訪問；當(dāng)在某個(gè)局部區(qū)域內(nèi)多步迭代均未探索到更優(yōu)解時(shí)，轉(zhuǎn)移至未探索的區(qū)域；當(dāng)達(dá)到終止條件(如搜索時(shí)間達(dá)到閾值，迭代次數(shù)達(dá)到閾值)時(shí)，停止搜索并返回當(dāng)前最優(yōu)解.

文獻(xiàn)[31-32]提出基于TS的流量調(diào)度機(jī)制，定義代價(jià)函數(shù)為wTTδTT+wRCδRC，δTT和δRC分別為TT幀與RC幀的可調(diào)度程度，定義為幀傳輸延時(shí)與截止時(shí)間的差值，wTT和wRC則為對應(yīng)的權(quán)重；并定義了前驅(qū)幀/當(dāng)前幀傳輸提前、當(dāng)前幀/后繼幀傳輸延后4種遷移；以盡快傳輸策略生成初始調(diào)度方案，對當(dāng)前方案中不可調(diào)度的幀進(jìn)行提前傳輸，對可調(diào)度程度最高的幀進(jìn)行延后傳輸，生成臨近方案候選列表，并選擇其中代價(jià)函數(shù)最小的臨近方案；若臨近方案代價(jià)函數(shù)小于當(dāng)前方案，則更新當(dāng)前方案并將產(chǎn)生該臨近方案的遷移寫入禁忌表；在搜索過程中持續(xù)更新最優(yōu)方案，當(dāng)搜索時(shí)間達(dá)到閾值時(shí)返回最新的最優(yōu)方案.此外，文獻(xiàn)[31]將TT流和RC流的路徑選擇也定義為傳輸方案的一部分，將重路由也定義為遷移，采用TS算法搜索路由與調(diào)度聯(lián)合方案.文獻(xiàn)[33]提出基于TS的流量類型分配與調(diào)度聯(lián)合機(jī)制，探索流量類型分配空間.TSN中硬實(shí)時(shí)流量必須在截止期限內(nèi)完成傳輸，一旦超過則效用立刻降為零，而在期限內(nèi)任何時(shí)間完成的效用沒有區(qū)別；軟實(shí)時(shí)流量在完成時(shí)間超過截止期限時(shí)效用不會立刻降為零而是隨完成時(shí)間增大逐漸降低；為混合流量重新分配TT或AVB的類型可以保證硬實(shí)時(shí)流量在期限內(nèi)完成的同時(shí)為軟實(shí)時(shí)流量提供更多傳輸?shù)臋C(jī)會，最大化軟實(shí)時(shí)流量的效用.定義代價(jià)函數(shù)為硬實(shí)時(shí)流量可調(diào)度程度與軟實(shí)時(shí)流量效用的加權(quán)和，并定義了流類型切換、修改GCL、流等級切換3種遷移；初始方案為硬實(shí)時(shí)流量分配TT類型而軟實(shí)時(shí)流量分配AVB類型，采用盡快傳輸策略生成該類型分配下的調(diào)度方案.每次搜索首先生成固定數(shù)量的臨近方案，并選擇其中代價(jià)函數(shù)最大的；若臨近方案代價(jià)函數(shù)大于當(dāng)前方案，則更新當(dāng)前方案并將產(chǎn)生該臨近方案的遷移寫入禁忌表；在搜索過程中持續(xù)更新最優(yōu)方案，當(dāng)搜索時(shí)間達(dá)到閾值時(shí)返回最新的最優(yōu)方案.

3.5 基于GRASP的流量調(diào)度機(jī)制

GRASP類似于TS算法，也是在解空間中引導(dǎo)式搜索最優(yōu)解的元啟發(fā)式算法，與TS的區(qū)別在于初始解生成和鄰域搜索算法不同.GRASP適用于求解組合優(yōu)化問題，初始解通過貪心算法生成，每次迭代包含構(gòu)造和搜索2個(gè)階段.構(gòu)造階段每次通過貪心隨機(jī)算法生成一個(gè)新的初始可行解；搜索階段采用爬山算法對該初始解進(jìn)行鄰域搜索并持續(xù)優(yōu)化，得到局部最優(yōu)解，若新的局部最優(yōu)解比當(dāng)前最優(yōu)解代價(jià)函數(shù)更小，則更新當(dāng)前最優(yōu)解；多次迭代，構(gòu)造與搜索交替執(zhí)行，直到滿足終止條件時(shí)返回當(dāng)前最優(yōu)解.

Pop等人也設(shè)計(jì)了基于GRASP的調(diào)度機(jī)制[16,34].文獻(xiàn)[16]以提升TT流和AVB流的可調(diào)度程度為目標(biāo)，以TT流可調(diào)度的方案為可行解，以AVB流的可調(diào)度程度為代價(jià)函數(shù)來判斷可行解的質(zhì)量.文獻(xiàn)[34]將目標(biāo)函數(shù)寫為三元組(|S|-|x|,Kx,Λx)，以TT流的可調(diào)度程度、占用隊(duì)列數(shù)和端到端延時(shí)為評價(jià)指標(biāo)，按字典序進(jìn)行比較.文獻(xiàn)[16,34]針對盡快傳輸策略和最遲傳輸策略分別設(shè)計(jì)了5種變體，共12種啟發(fā)式策略作為候選算法.在構(gòu)造階段采用貪心隨機(jī)算法，為每條流預(yù)測12種算法對目標(biāo)函數(shù)的增量，選擇增量最小的γ種組成候選列表，再從中隨機(jī)選擇一個(gè)算法調(diào)度該流，形成初始解.在搜索階段，每次從當(dāng)前解中移除最多π條流，采用貪心隨機(jī)算法重新調(diào)度移除的流形成臨近解；一旦臨近解的代價(jià)函數(shù)小于當(dāng)前解即結(jié)束本輪搜索，以臨近解為當(dāng)前解開始下一輪搜索，達(dá)到搜索的終止條件后進(jìn)入下一個(gè)構(gòu)造階段.在達(dá)到GRASP的終止條件后，返回歷史最優(yōu)調(diào)度方案.

3.6 基于復(fù)合方法的流量調(diào)度機(jī)制

部分調(diào)度機(jī)制采用以上多種方法的復(fù)合方法求解調(diào)度問題中不同的子問題，或在一種方法迭代的每一步采用其他方法計(jì)算當(dāng)前調(diào)度方案和指標(biāo).

文獻(xiàn)[35]以最小化TT流占用隊(duì)列數(shù)為調(diào)度目標(biāo)來為AVB和BE流留出盡可能多的隊(duì)列，將TT流調(diào)度問題形式化為ILP問題，并采用ILP求解器求解調(diào)度方案，并在此基礎(chǔ)上以AVB流可調(diào)度、最小化AVB流端到端延時(shí)及最大化網(wǎng)絡(luò)帶寬利用率為目標(biāo)，構(gòu)建代價(jià)函數(shù)為3個(gè)指標(biāo)的加權(quán)和，采用GRASP為AVB流選擇路徑.文獻(xiàn)[36]關(guān)注AVB流的可調(diào)度性，采用網(wǎng)絡(luò)演算理論[37]對TT流對AVB流的阻塞反映到AVB流的最壞情況端到端延時(shí)上界中，并以所有AVB流的端到端延時(shí)上界與截止時(shí)間的差值作為目標(biāo)函數(shù)，提出了聯(lián)合路由與調(diào)度策略JRS決策TT流的路徑和GCL.JRS迭代執(zhí)行K-最短路徑算法選擇路徑以及GRASP算法搜索該路由方案下的最優(yōu)GCL，計(jì)算目標(biāo)函數(shù)值并在迭代過程中不斷更新最優(yōu)路由與GCL聯(lián)合方案.文獻(xiàn)[38-40]均關(guān)注無等待調(diào)度問題，要求幀一旦從發(fā)送端發(fā)出，在中間節(jié)點(diǎn)上無等待，因此調(diào)度變量只包括幀在發(fā)送端的傳輸開始時(shí)間，而在后續(xù)端口的傳輸時(shí)間可通過累加鏈路傳輸延時(shí)、傳播延時(shí)和交換機(jī)處理延時(shí)直接得到.文獻(xiàn)[38]以最小化所有TT流的總傳輸時(shí)長為目標(biāo)，將問題分解為流排序和時(shí)間表制定，采用TS與啟發(fā)式算法聯(lián)合求解.TS搜索TT流的順序空間：根據(jù)每條TT流在通過所有節(jié)點(diǎn)上的總處理時(shí)間和最大處理時(shí)間分別升序和降序排列，結(jié)合隨機(jī)排序算法共生成5個(gè)初始序列；分別從每個(gè)初始序列開始，將最后完成的流作為關(guān)鍵流，將其插入前驅(qū)流之前或與前驅(qū)流交換位置生成臨近序列，并將關(guān)鍵流寫入禁忌表；每次生成新序列后采用貪心算法按序?yàn)槊織l流分配與前流無沖突的最早傳輸開始時(shí)間，形成該序列下的調(diào)度方案，計(jì)算整體傳輸時(shí)長作為該序列的評價(jià)指標(biāo)，選擇傳輸時(shí)長最小且關(guān)鍵流不在禁忌表中的臨近序列進(jìn)行遷移；當(dāng)多次迭代未能更新最優(yōu)序列時(shí)停止搜索，返回當(dāng)前最優(yōu)序列的調(diào)度方案.文獻(xiàn)[39]將TT流的路由和調(diào)度問題歸約為沖突圖，將每條流的每種配置，即路徑和傳輸開始時(shí)間作為節(jié)點(diǎn)，節(jié)點(diǎn)間的沖突邊表示同時(shí)采用2個(gè)節(jié)點(diǎn)的配置會破壞約束，即存在沖突.沖突圖中包含所有流的無關(guān)點(diǎn)集即為有效的路由和調(diào)度方案，采用ILP與啟發(fā)式算法聯(lián)合求解.初始沖突圖包括每條流的初始配置，通過迭代遍歷每條流的路由和開始時(shí)間，擴(kuò)充沖突圖，并依次調(diào)用啟發(fā)式算法和ILP在擴(kuò)充圖中尋找最大無關(guān)點(diǎn)集，直到該點(diǎn)集包含所有流，返回對應(yīng)的路由和開始時(shí)間方案.文獻(xiàn)[40]將TT流用圖表示，以流為節(jié)點(diǎn)，流之間的相關(guān)程度為邊的權(quán)重，提出啟發(fā)式圖劃分算法將所有流劃分為相關(guān)度最少的多個(gè)分組；采用GRASP算法探索多徑路由空間，初始路由隨機(jī)生成，在當(dāng)前路由方案下對流進(jìn)行劃分，將對相關(guān)度貢獻(xiàn)最大的流替換路由方案進(jìn)行鄰域搜索，多次迭代得到?jīng)_突最小的路由和分組方案.每組TT流獨(dú)立采用ILP求解各自的約束，前驅(qū)組的可行解作為后續(xù)組的先驗(yàn)約束，直到所有分組的可行解共同構(gòu)成調(diào)度方案.

3.7 小 結(jié)

表3總結(jié)了TSN流量調(diào)度機(jī)制的調(diào)度目標(biāo)、調(diào)度對象、求解方法等特點(diǎn).從3.1～3.6節(jié)分析中可以看出，現(xiàn)有的TSN流量調(diào)度機(jī)制能夠從機(jī)理上保證流量在網(wǎng)絡(luò)中按序、無沖突傳輸，且滿足實(shí)時(shí)流量確定性延時(shí)與有界延時(shí)抖動(dòng)的性能要求，在此基礎(chǔ)上針對端到端延時(shí)、帶寬利用率、內(nèi)存占用時(shí)間等性能指標(biāo)分別優(yōu)化且均實(shí)現(xiàn)了不同程度的性能提升.然而也具有3個(gè)共性問題：

1) 現(xiàn)有流量調(diào)度機(jī)制大多基于時(shí)間感知整形器TAS設(shè)計(jì)，通過端口的GCL控制各隊(duì)列出口的開閉，為不同隊(duì)列分配不重疊的傳輸時(shí)隙對不同優(yōu)先級的流量進(jìn)行隔離.在TAS整形框架中，調(diào)度機(jī)制需要嚴(yán)格規(guī)定每個(gè)TT幀到達(dá)和離開每個(gè)端口的精確時(shí)間且必須滿足嚴(yán)苛的約束條件，導(dǎo)致變量與約束數(shù)量眾多且解空間受限，為調(diào)度方案質(zhì)量與求解時(shí)間的有效權(quán)衡造成了困難.

2) 現(xiàn)有流量調(diào)度機(jī)制均采用離線方法計(jì)算靜態(tài)的流量調(diào)度方案，導(dǎo)致缺少對動(dòng)態(tài)環(huán)境下幀到達(dá)和離開端口的時(shí)間偏差的補(bǔ)償能力，難以抵抗在線運(yùn)行時(shí)網(wǎng)絡(luò)與流量固有且難以避免的不確定性，如幀丟失、時(shí)間同步誤差、緊急事件觸發(fā)的突發(fā)流量等.一旦某一幀未能按調(diào)度方案給定的時(shí)刻到達(dá)指定端口，則可能導(dǎo)致該幀及后續(xù)幀無法在分配的時(shí)隙完成傳輸，擾亂既定的流發(fā)送時(shí)序，誘發(fā)連鎖反應(yīng)導(dǎo)致不可預(yù)期的傳輸結(jié)果，具有較弱的靈活性和魯棒性.

3) 現(xiàn)有流量調(diào)度機(jī)制主要關(guān)注實(shí)時(shí)流量，而非實(shí)時(shí)流量大多只是簡單填充實(shí)時(shí)流量的剩余帶寬和時(shí)隙.然而非實(shí)時(shí)流量也承載著業(yè)務(wù)語義，同樣具有業(yè)務(wù)定義的優(yōu)先順序，以及延時(shí)、帶寬保證等差異化的性能要求；缺少對非實(shí)時(shí)流量的個(gè)性化關(guān)照會導(dǎo)致非實(shí)時(shí)流量難以準(zhǔn)確充分地利用網(wǎng)絡(luò)資源和實(shí)現(xiàn)相關(guān)業(yè)務(wù)的效用最大化.

針對上述問題，部分研究工作提出了新的調(diào)度思路，擴(kuò)展了TSN流量調(diào)度機(jī)制的設(shè)計(jì)空間.第4節(jié)對該部分研究工作進(jìn)行了闡述.

Table 3 Scheduling Mechanisms Summary表3 調(diào)度機(jī)制總結(jié)

4 TSN流量調(diào)度發(fā)展趨勢

在現(xiàn)有TSN流量調(diào)度機(jī)制的基礎(chǔ)上，流量調(diào)度的發(fā)展趨勢主要包括動(dòng)態(tài)分配傳輸時(shí)隙、混合流量整體調(diào)度、流量調(diào)度與路由聯(lián)合規(guī)劃、流量與任務(wù)聯(lián)合調(diào)度、其他整形器框架下的調(diào)度、可靠性感知的流量調(diào)度、融合網(wǎng)絡(luò)中的流量調(diào)度等.

2) 混合流量的整體調(diào)度.為進(jìn)一步優(yōu)化非實(shí)時(shí)流量的傳輸性能，實(shí)現(xiàn)非實(shí)時(shí)流量的效用最大化，部分研究工作在TT流調(diào)度的基礎(chǔ)上關(guān)注AVB,RC流所要求的延時(shí)性能和BE流所要求的帶寬利用率.一方面在TT流的調(diào)度中考慮其他流量的性能指標(biāo)，在保證自身可調(diào)度的條件下為其他流量留出最大隊(duì)列數(shù)或空閑時(shí)隙；另一方面直接將非實(shí)時(shí)流量的性能指標(biāo)寫入優(yōu)化目標(biāo)，將AVB,RC流的傳輸方案與TT流共同決策.可見已有研究開始關(guān)注RC流和AVB流的性能，但相關(guān)調(diào)度算法主要關(guān)注延時(shí)指標(biāo)，在傳輸效用的個(gè)性化關(guān)照方面還有進(jìn)一步完善的空間.此外，當(dāng)前對于BE流主要以提高網(wǎng)絡(luò)整體的帶寬利用率為主，同樣缺少對BE流自身性能要求的細(xì)化分析和針對性優(yōu)化.

3) 流量調(diào)度與路由聯(lián)合規(guī)劃.現(xiàn)有流量調(diào)度機(jī)制大多基于給定的路由方案，通常采用生成樹協(xié)議或最短路徑路由算法確定；在此基礎(chǔ)上流量調(diào)度執(zhí)行端口隊(duì)列和幀傳輸時(shí)隙分配.由于路由機(jī)制只考慮路由相關(guān)指標(biāo)，如路徑長度、負(fù)載均衡等，并未考慮每條流的分類和性能要求，因此可能產(chǎn)生不利于甚至阻礙調(diào)度機(jī)制提高流傳輸性能的路由方案.若路由機(jī)制將多條延時(shí)緊迫的TT流分配至同一鏈路，則由于嚴(yán)重的時(shí)隙爭用難以滿足所有流的截止時(shí)間，更難以為其他流量留出優(yōu)化的空間.因此，已有部分研究開始考慮將流量調(diào)度與路由聯(lián)合規(guī)劃，增大傳輸解空間，使更多流量可調(diào)度并且取得更優(yōu)的性能.可以看出，路由與調(diào)度聯(lián)合機(jī)制的主要思路是將路徑選擇設(shè)為變量，與調(diào)度方案針對同一目標(biāo)共同決策，主要適用于離線計(jì)算的場景.在實(shí)際中網(wǎng)絡(luò)可能發(fā)生實(shí)時(shí)動(dòng)態(tài)變化，可以進(jìn)一步探索在線路由與調(diào)度的聯(lián)合機(jī)制.

4) 任務(wù)與流量整體調(diào)度.實(shí)時(shí)應(yīng)用不僅要求網(wǎng)絡(luò)傳輸?shù)拇_定性低延時(shí)，應(yīng)用本身也需要確定性的低響應(yīng)時(shí)間.為將延時(shí)的確定性從網(wǎng)絡(luò)擴(kuò)展到應(yīng)用層，就需要運(yùn)行在端系統(tǒng)上的計(jì)算任務(wù)與網(wǎng)絡(luò)中的流量整體調(diào)度，否則任務(wù)執(zhí)行與流量傳輸不匹配會導(dǎo)致應(yīng)用響應(yīng)時(shí)間的增大和不確定性.因此，少量研究將端系統(tǒng)計(jì)算任務(wù)采用與流量傳輸采用統(tǒng)一的方法建模，將應(yīng)用抽象為計(jì)算與傳輸?shù)娜蝿?wù)序列，將計(jì)算任務(wù)的執(zhí)行時(shí)隙也作為調(diào)度變量，根據(jù)計(jì)算任務(wù)特性與流量傳輸?shù)囊蕾囮P(guān)系定義任務(wù)調(diào)度約束，以整體應(yīng)用性能為目標(biāo)合成任務(wù)與流量的聯(lián)合調(diào)度方案.實(shí)時(shí)系統(tǒng)應(yīng)用的計(jì)算與通信模式多種多樣且較為復(fù)雜，在現(xiàn)有工作的基礎(chǔ)上可以進(jìn)一步討論不同應(yīng)用下的計(jì)算任務(wù)與流量傳輸模型以獲得更為精準(zhǔn)的調(diào)度結(jié)果.

5) 基于其他整形器框架的調(diào)度.現(xiàn)有流量調(diào)度機(jī)制大多基于TAS調(diào)度TT流和基于CBS調(diào)度AVB流，而基于其他整形器的調(diào)度機(jī)制較少.然而CQF和ATS也是TSN中的通用整形器，分別適用于周期性流量以及周期與非周期性混合流量整形，因此有研究開始關(guān)注基于其他整形器的流量調(diào)度機(jī)制.少數(shù)研究提出了基于ATS的流量調(diào)度機(jī)制，包括流的隊(duì)列分配和隊(duì)列的優(yōu)先級分配2部分決策.根據(jù)ATS的隊(duì)列分配規(guī)則設(shè)計(jì)端口的隊(duì)列分配約束，分析ATS作用在流的端到端延時(shí)上界設(shè)計(jì)延時(shí)約束，并分別采用SMT求解器和拓?fù)渑判蚯蠼馄?topology rank solver, TRS)求解調(diào)度方案[42].在此基礎(chǔ)上，基于CQF和ATS的流量調(diào)度機(jī)制還可繼續(xù)豐富和完善.

6) 可靠性感知的調(diào)度.為增強(qiáng)TSN流量傳輸?shù)目煽啃?，采用逐流控制?shí)現(xiàn)零擁塞丟棄是一種基本技術(shù)手段.分布式流預(yù)留協(xié)議(Stream Reservation Protocol, SRP)[43]中的連接準(zhǔn)入控制可為特定流按需預(yù)留網(wǎng)絡(luò)資源，避免因不同流爭用網(wǎng)絡(luò)資源為確定性傳輸帶來負(fù)面影響.此外，TSN工作組還開發(fā)了幀副本和消除(FRER)策略[44]，通過在多個(gè)不相交的路徑發(fā)送幀副本，為無法容忍幀丟失的應(yīng)用程序提供冗余高可靠傳輸服務(wù)，接收的第1個(gè)消息將被正常處理，其他副本將被丟棄.基于FRER策略，文獻(xiàn)[45-46]提出可靠性感知的路由方案，考慮鏈路的失效概率，計(jì)算傳輸路徑的可靠性指標(biāo)，分別采用ILP和蟻群算法為每條流選擇可靠性高、相互沖突小、延時(shí)小的路徑，為流量調(diào)度提供更大的可行解空間.然而，F(xiàn)RER支持的消息副本多路徑冗余傳輸雖可顯著增強(qiáng)確定性可靠傳輸，但引入的過量帶寬開銷是一個(gè)不可回避的問題，需要進(jìn)一步研究解決方案和替代策略來加以克服.此外，也可將調(diào)度與可靠性感知的路由結(jié)合，求解具有可靠性保證的聯(lián)合方案.

7) 融合網(wǎng)絡(luò)中的流量調(diào)度.由于TSN互聯(lián)互通的優(yōu)勢，目前TSN與新型網(wǎng)絡(luò)的融合已成為研究熱點(diǎn).2017年IEC與IEEE聯(lián)合成立了IEC/IEEE60802工作組，負(fù)責(zé)制定TSN在工業(yè)自動(dòng)化領(lǐng)域應(yīng)用的規(guī)范.OPC UA基金會則成立了現(xiàn)場級通信(FLC)工作組，將TSN相關(guān)標(biāo)準(zhǔn)與OPC UA規(guī)范融合，提供適用于智能制造和工業(yè)互聯(lián)網(wǎng)領(lǐng)域的工業(yè)通信架構(gòu).專注通信產(chǎn)品認(rèn)證的產(chǎn)業(yè)聯(lián)盟AVnu也開始重點(diǎn)關(guān)注TSN相關(guān)技術(shù)和產(chǎn)品專業(yè)音視頻傳輸、汽車和工業(yè)自動(dòng)化等領(lǐng)域的市場應(yīng)用.融合網(wǎng)絡(luò)中流量的類型與特征各異，需要根據(jù)性能要求將融合網(wǎng)絡(luò)流量與TSN標(biāo)準(zhǔn)機(jī)制進(jìn)行映射，按TSN流量類型調(diào)度.文獻(xiàn)[47]將工業(yè)自動(dòng)化和控制系統(tǒng)流量總結(jié)為8類：同步通信流量、循環(huán)流量、事件觸發(fā)流量、網(wǎng)絡(luò)控制流量、配置與診斷流量、盡力而為流量、視頻流量、音頻流量，并為每種流量分別映射了TSN標(biāo)準(zhǔn)中的嚴(yán)格優(yōu)先級、轉(zhuǎn)發(fā)和排隊(duì)增強(qiáng)、時(shí)間同步、時(shí)間感知整形、幀搶占、流預(yù)留、逐流過濾和監(jiān)管、幀復(fù)制和消除以及直通交換等機(jī)制.文獻(xiàn)[48]遵循文獻(xiàn)[47]中的流量分類，將每個(gè)網(wǎng)絡(luò)周期劃分為多個(gè)階段，每個(gè)階段單獨(dú)分配給一類流量；將工廠自動(dòng)化網(wǎng)絡(luò)分為機(jī)器層、生產(chǎn)單元層和主干層，并將流量分為層內(nèi)流量和跨層流量，同一類型的層內(nèi)和跨層流量分別占用其階段的前半部分和后半部分傳輸，層內(nèi)流量往往比跨層流量具有更低的延時(shí)要求，因此采用每流調(diào)度，而跨層流量采用整體調(diào)度以降低計(jì)算復(fù)雜度，實(shí)現(xiàn)了工廠自動(dòng)化網(wǎng)絡(luò)的混合流量在融合網(wǎng)絡(luò)中的隔離和高性能傳輸.文獻(xiàn)[33]將信息物理系統(tǒng)中的應(yīng)用分為3類：硬實(shí)時(shí)應(yīng)用、軟實(shí)時(shí)應(yīng)用和非時(shí)間關(guān)鍵應(yīng)用，根據(jù)截止時(shí)間和效用函數(shù)基于TS算法為混合流量分配TSN中的TT或AVB類型，并采用盡快傳輸策略確定流量傳輸時(shí)間.

針對當(dāng)前TSN流量調(diào)度存在的問題，可以考慮改進(jìn)TSN流量調(diào)度問題的結(jié)構(gòu)加以完善.TSN中的流量規(guī)劃與調(diào)度需要做的決策主要包括每條流到隊(duì)列的分配以及每個(gè)幀實(shí)例在每個(gè)端口的傳輸時(shí)隙分配.可以對流量調(diào)度任務(wù)進(jìn)行合理分解，開展全局靜態(tài)規(guī)劃與局部動(dòng)態(tài)調(diào)度聯(lián)合調(diào)度方法的研究，基本思路是：將無需全局信息的傳輸時(shí)隙分配從全局規(guī)劃中移除，由端口的局部調(diào)度完成.全局規(guī)劃只決策每流的隊(duì)列分配，探索對目標(biāo)函數(shù)最有利的隊(duì)列分配方案，大幅降低變量與約束條件的數(shù)量，并將端到端延時(shí)與抖動(dòng)約束分解到每個(gè)端口上，為局部調(diào)度提供指導(dǎo)；局部調(diào)度根據(jù)端口和幀的實(shí)時(shí)狀態(tài)動(dòng)態(tài)分配傳輸時(shí)隙，利用以太網(wǎng)固有流量控制機(jī)制在相鄰節(jié)點(diǎn)間傳遞資源與流量信息，利用出端口的優(yōu)先級轉(zhuǎn)發(fā)和幀搶占機(jī)制為不同隊(duì)列的幀實(shí)時(shí)分配可用的時(shí)隙或帶寬資源，并根據(jù)本地的延時(shí)與抖動(dòng)約束進(jìn)行適當(dāng)延時(shí)補(bǔ)償以保證傳輸確定性.

5 總 結(jié)

為實(shí)現(xiàn)確定性低延時(shí)的網(wǎng)絡(luò)傳輸需求，IEEE 802 TSN工作組提出了一系列增強(qiáng)機(jī)制與策略，將以太網(wǎng)擴(kuò)展為TSN.流量調(diào)度是TSN的核心機(jī)制，通過規(guī)定幀傳輸?shù)捻樞蚝蜁r(shí)隙保證網(wǎng)絡(luò)內(nèi)無沖突傳輸，滿足延時(shí)與帶寬要求，并優(yōu)化傳輸性能.本文系統(tǒng)地闡述了TSN流量調(diào)度的標(biāo)準(zhǔn)框架，形式化描述了TSN流量調(diào)度問題，包括典型的調(diào)度約束和調(diào)度目標(biāo).在此基礎(chǔ)上對現(xiàn)有的TSN流量調(diào)度機(jī)制按采用的算法分類，分別進(jìn)行了分析與總結(jié)，最后討論了TSN流量調(diào)度的設(shè)計(jì)空間和發(fā)展趨勢，為后續(xù)的研究奠定了基礎(chǔ).隨著計(jì)算系統(tǒng)算力的提高，TSN流量調(diào)度機(jī)制的可擴(kuò)展性將大幅提升，并且對調(diào)度問題的建模與求解更加完善.

作者貢獻(xiàn)聲明：張彤負(fù)責(zé)提出綜述思路、設(shè)計(jì)綜述內(nèi)容、論文撰寫和最后版本修訂；馮佳琦負(fù)責(zé)收集和分析時(shí)間敏感網(wǎng)絡(luò)流量控制標(biāo)準(zhǔn)相關(guān)的文獻(xiàn)資料；馬延瀅負(fù)責(zé)收集和分析時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度形式化問題相關(guān)的文獻(xiàn)資料；渠思源負(fù)責(zé)收集和分析時(shí)間敏感網(wǎng)絡(luò)流量調(diào)度算法相關(guān)的文獻(xiàn)資料；任豐原負(fù)責(zé)對文章學(xué)術(shù)性和技術(shù)性內(nèi)容進(jìn)行審閱和關(guān)鍵性修訂.