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

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

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

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

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

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

(zhangt@nuaa.edu.cn)

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

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

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

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

1 TSN流量調(diào)度標準框架

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

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

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

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

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

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

1.2 TSN固有流量控制機制

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

1.2.1 保護帶機制

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

1.2.2 幀搶占機制

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

1.2.3 流量整形機制

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

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

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

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

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

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

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

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

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

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

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

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

以圖2中的網(wǎng)絡和表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個MTU，s2的周期為150 μs，大小為4 500 B，即3個MTU，2條流所能容忍的最大端到端延時均為2 ms，最大延時抖動均為5 μs.假設鏈路傳播延時與交換機處理延時均為1 μs，所有鏈路帶寬均為1 Gbps，則每個幀的傳輸延時為12.336 μs.圖3采用甘特圖展示了一種可行調(diào)度方案.橫坐標表示時間，縱坐標表示鏈路，矩形表示幀傳輸實例.

Table 1 Flow Instance表1 流量實例

2.2 調(diào)度約束

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

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

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

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

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

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

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

2.3 調(diào)度目標

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

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

即最小化所有實時流端到端延時之和.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.7 小 結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總 結(jié)

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

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