來源：TSNLAB 微信公眾號
“ IEEE 802.1Qbv定義了一種時間感知整形器（Time Aware Shaper，TAS），配合控製器的編排，交換機按照配置好的時間控製隊列的打開/關閉狀態（基於門控列表Gate Control List，GCL），可以實現業務端到端納秒級別（或時鍾同步精度級別）的SLA保障和控製。然而，標準中並未定義GCL應該如何計算，本文針對該問題進行闡述。”
IEEE 802.1Qbv定義的TAS示意如下圖1所示，GCL表項中每行數據分別對應了每個隊列在對應時刻的O/C狀態，交換機按照時間順序進行輪轉。門控機製作為TSN核心技術之一，本質上是通過規定周期性業務每一幀在每個交換機端口上的轉發時間，達到時延控製、抖動控製以及其它SLA保障的目的。
圖1：門控機製及GCL示意圖
然而，標準中並未定義GCL應該如何計算，為了實現各種各樣的目標，學術界和產業界對Qbv門控編排（或稱之為門控編排、TAS編排）問題進行了深入探討。本文通過一個簡單的例子，闡述門控編排的數學模型、解決方法以及麵臨的問題。
01
—
以一個例子引入…
如下圖所示，有A、B、Csanliangchefenbiecongsandichufaqianwangjichang，jiashegechechesuxiangtong，cheliangtongguodaoludeshijianrutuzhongbiaoshi，tongshi，jiadingmeigelukouyicizhinengtongguoyiliangche，tongguoshijianwei2s。那麼，如果A、B、C三車分別要求在85秒內、90秒內、86秒內到達機場，問如何安排路口的紅綠燈使車輛按照特定順序通過路口，且保證三輛車都滿足其時限要求？
圖2：車輛調度問題
該問題求解並不難，一種可行的方式如下圖3，即當時間到達20s，A、B輛車同時到達路口甲，由於A車更“著急”，所以A車先通過（此時時刻為22s），B車需要等待2秒；52s時刻，A、C車都到達路口乙，同樣原因，A車先通過路口（通過時刻54s）。之後，如果讓B車先過，通過時刻為56s，那C車到達機場時間為88s，超過時限限製，因此，需要先讓C車通過。58s時刻，三車順次通過路口乙。最終到達機場的時間：
•A車：20+2+30+2+30=84s
•B車：20+2+2+30+2+2+30=88s，黑體表示等待其它車輛通過的時間
•C車：51+3+2+30=86s，由於C車51s時到達路口，等待A車54s時通過路口，故等待3s時間
圖3：車輛調度問題可行解之一
Qbv門(men)控(kong)編(bian)排(pai)問(wen)題(ti)與(yu)上(shang)述(shu)車(che)輛(liang)調(tiao)度(du)問(wen)題(ti)極(ji)為(wei)相(xiang)似(si)，一(yi)個(ge)業(ye)務(wu)流(liu)可(ke)以(yi)認(ren)為(wei)是(shi)例(li)中(zhong)的(de)車(che)輛(liang)，路(lu)口(kou)可(ke)以(yi)認(ren)為(wei)是(shi)交(jiao)換(huan)機(ji)端(duan)口(kou)，車(che)輛(liang)的(de)時(shi)限(xian)要(yao)求(qiu)可(ke)以(yi)認(ren)為(wei)是(shi)業(ye)務(wu)的(de)時(shi)延(yan)訴(su)求(qiu)。然(ran)而(er)，實(shi)際(ji)的(de)Qbv門控編排問題要更加複雜，例如，實際的業務流可能會有多個幀組成，因此，例中車輛的編排可能演變成車隊的編排；實際的業務通過端口的時間與報文大小和端口速率有關，非固定值；端口有多個隊列組成，報文到達隊列的順序、等待時間可以靈活調整（類似於車道級紅綠燈）；如果端設備受控，報文的起始發送偏移（offset）亦可調整（發車時間不固定）；報文還可能存在抖動需求……
下麵，進一步闡述門控編排的數學模型。
02
—
門控編排的目標
在討論目標前，首先明確編排的問題輸入，包括業務和網絡拓撲信息輸入。
•業務信息：門控編排通常適用於具有端到端時延或抖動需求的周期性或時間觸發（Time-Triggered Traffic, TT）業務，這裏采用簡單的業務模型：，分別表示每周期數據量、周期大小、業務時延要求
•網絡拓撲信息：假設，分別表示交換機集合、端設備集合以及鏈路集合。
門控編排的目標包含（但不限於）以下幾種：
1、在有限的網絡資源（帶寬、時隙、隊列等）下，盡可能承載更多的業務，且業務的SLA指標可滿足
2、部署給定業務，占用資源最少
3、部署給定業務，業務時延最低，抖動要求可滿足
4、承載更多的業務類型，如除TT業務外，承載突發性流量、AVB流量等
TIPS：之前車輛的編排問題目標對應於上述第1種
明確了問題的輸入輸出，下麵介紹問題求解過程中需要遵守的約束條件（篇幅有限，僅介紹關鍵約束）
03
—
編排問題約束條件類型
時延要求滿足性約束
qizhong，biaoshiliuzaizuihouyitiaodelikaishijian，biaoshiduiyingduankoudedaikuan，biaoshiyewuzaiyuanduandefasongpianyi。yinci，gaishibiaoshizhongduanshebeishoudaobaowendeshikejianqubaowenfasongshike，yijilujingduandaoduanshiyanyingdangzaiguidingdefanweinei。dangqianbudengshizhongweikaolvlianlushangdexinhaochuanboshiyan。
轉發時間不重疊約束
duiyujingguotongyichuduankouderenyiliangtiaoliu，qicongduankouzhuanfadeshijianchuangxianghubuzhongdie，ji，renyiyitiaoliuconglikaiduankoudeshikekaishi，daozhenggeshujuzhenfasongwanbiweizhi，qijianbushouqitabaowenyingxiang（這裏不考慮幀搶占）。
存儲轉發約束
在zai存cun儲chu轉zhuan發fa機ji製zhi的de交jiao換huan機ji中zhong，當dang交jiao換huan機ji完wan整zheng的de收shou到dao上shang一yi跳tiao發fa送song的de報bao文wen後hou，才cai進jin行xing轉zhuan發fa。這zhe裏li的de表biao示shi網wang絡luo的de時shi鍾zhong同tong步bu誤wu差cha。從cong公gong式shi中zhong可ke以yi看kan到dao，由you於yu時shi鍾zhong誤wu差cha的de存cun在zai，相xiang當dang於yu在zai報bao文wen的de尾wei部bu加jia入ru了le一yi個ge保bao護hu邊bian帶dai，如ru下xia圖tu所suo示shi。
圖4：時鍾同步誤差示意
周期混疊約束
當多個流的周期不相同時，需要基於超周期（hyper-period）進(jin)行(xing)編(bian)排(pai)，超(chao)周(zhou)期(qi)的(de)最(zui)小(xiao)值(zhi)取(qu)所(suo)有(you)業(ye)務(wu)的(de)最(zui)小(xiao)公(gong)倍(bei)數(shu)。因(yin)此(ci)，一(yi)個(ge)周(zhou)期(qi)較(jiao)小(xiao)的(de)流(liu)在(zai)超(chao)周(zhou)期(qi)上(shang)會(hui)進(jin)行(xing)延(yan)展(zhan)，進(jin)而(er)需(xu)要(yao)保(bao)證(zheng)超(chao)周(zhou)期(qi)下(xia)該(gai)流(liu)的(de)多(duo)個(ge)子(zi)周(zhou)期(qi)的(de)報(bao)文(wen)轉(zhuan)發(fa)約(yue)束(shu)都(dou)得(de)到(dao)滿(man)足(zu)。
上述公式給出了超周期下小周期業務流延展之後的轉發時間不重疊約束的簡單表達。其中 表示流在超周期下的第個周期。其它約束條件類似。
其它約束
除上述約束條件外，還有抖動要求約束、路徑約束、隊列隔離約束、隊列FIFO屬性約束等，詳細信息讀者可以查看相關論文，本文不做展開。
04
—
常見的求解方法
門控編排問題可以抽象成任務調度問題，是典型的NP-Hard問題，除非NP=P，否則無法在多項式時間內求得最優解。目前學術界對於門控編排問題的求解，或是基於可滿足性模理論（Satisfiability Modulo Theory，SMT），如同TTTech公司的論文[2, 3]，類似的還有優化模理論（Optimization Modulo Theory，OMT）；或是基於整數線性規劃（Integer Linear Programming，ILP）[4]；或者基於啟發式算法，如Tabu-Search、遺傳算法、蟻群算法等[5]。當然，還可以通過AI等方法進行加速計算[6]。
圖5：幾種方法對比
05
—
結合實際場景的優化和簡化
TAS編排問題的複雜度
當網絡規模變大、業務數目變多，如果要精確調整每條業務流的每一幀在每個節點的接收、發送時刻，來求全局最優解，那麼變量和約束數目將按照|F|*M*|L|（流數*幀數*鏈路數）的基數呈指數級增加。同時，還需要考慮不同周期的業務混疊、路徑等因素，導致問題變得十分複雜。例如，當采用MILP求解時，對於一個百節點的多環拓撲+百條流的場景，其求解文件將達2GB，變bian量liang和he約yue束shu數shu目mu將jiang達da百bai萬wan級ji別bie。這zhe樣yang的de問wen題ti規gui模mo，在zai合he理li的de時shi間jian範fan圍wei內nei求qiu最zui優you解jie是shi不bu現xian實shi的de，然ran而er，在zai實shi際ji場chang景jing中zhong，是shi否fou有you必bi要yao做zuo如ru此ci精jing確que的de求qiu解jie？
真實場景中的問題簡化思路
•逐幀編排→逐流編排：在工業現場、車載網絡等場景，很多傳感器、采集器等端設備並不會一次性發送很多報文，相反，業務流大多以小包（如100B、64B）、單(dan)包(bao)的(de)形(xing)式(shi)，或(huo)者(zhe)即(ji)使(shi)業(ye)務(wu)每(mei)周(zhou)期(qi)會(hui)發(fa)送(song)多(duo)個(ge)報(bao)文(wen)，對(dui)於(yu)門(men)控(kong)編(bian)排(pai)問(wen)題(ti)來(lai)說(shuo)，也(ye)可(ke)以(yi)將(jiang)多(duo)個(ge)報(bao)文(wen)以(yi)背(bei)靠(kao)背(bei)方(fang)式(shi)連(lian)在(zai)一(yi)起(qi)作(zuo)為(wei)一(yi)個(ge)單(dan)獨(du)的(de)幀(zhen)進(jin)行(xing)編(bian)排(pai)。這(zhe)樣(yang)，編(bian)排(pai)問(wen)題(ti)的(de)視(shi)角(jiao)從(cong)逐(zhu)幀(zhen)降(jiang)級(ji)到(dao)逐(zhu)流(liu)，業(ye)務(wu)複(fu)雜(za)度(du)的(de)計(ji)算(suan)基(ji)數(shu)將(jiang)從(cong)|F|*M*|L|下降到|F|*|L|，當dang然ran這zhe樣yang做zuo的de代dai價jia是shi犧xi牲sheng了le一yi定ding的de解jie的de靈ling活huo性xing。但dan是shi對dui於yu大da規gui模mo網wang絡luo場chang景jing來lai說shuo，這zhe種zhong複fu雜za度du下xia降jiang帶dai來lai的de收shou益yi要yao遠yuan大da於yu靈ling活huo度du下xia降jiang付fu出chu的de代dai價jia，是shi一yi種zhong可ke取qu的de問wen題ti簡jian化hua手shou段duan。
•流聚合：實際場景中，往往存在大量業務特征相似甚至相同的業務流（例如大量相同的傳感器），對這些業務按照其周期、路徑、SLA要求等特征做分類和聚合，同樣可以從根本上降低問題的複雜度。
•分域求解：大型網絡場景中，例如雲化PLC、多廠區IT/OT融(rong)合(he)，往(wang)往(wang)地(di)理(li)上(shang)具(ju)有(you)分(fen)隔(ge)的(de)特(te)征(zheng)。在(zai)這(zhe)種(zhong)假(jia)設(she)下(xia)，將(jiang)全(quan)域(yu)編(bian)排(pai)分(fen)解(jie)成(cheng)幾(ji)個(ge)子(zi)域(yu)分(fen)別(bie)求(qiu)解(jie)，最(zui)後(hou)再(zai)進(jin)行(xing)合(he)並(bing)優(you)化(hua)，可(ke)以(yi)發(fa)揮(hui)並(bing)行(xing)計(ji)算(suan)的(de)優(you)勢(shi)，降(jiang)低(di)求(qiu)解(jie)時(shi)間(jian)。
zongzhi，jieheshijichangjingjinxingwentijianhua，bujinkeyizaiqiujieshijianshanghuodeshouyi，yekeyigenjuchangjingtezhengzuodingzhihuatiaozheng，erqizhongxishengdeyibufenlinghuoxinghuolangfeidexiexudaikuanziyuan，shikeyirongrende。bijing，yonghuzhenzhengguanxindeshikeyong、好用，其次才是精益求精。
06
—
結語
本文介紹的編排問題模型，僅僅是TSN編排的冰山一角。廣義的編排不僅包括TAS編排，還包括針對異步流量的CBS、QoS編排。流量類型除了周期性的TT業務外，還包括突發類流量（如AI質檢）、事件觸發類流量（控製報文、事件告警業務）等。同時，真實場景中，很可能TSN交換機、異步交換機共存，或存在多個TSN域，那麼編排問題不僅要考慮混合業務、還要考慮異構網絡，使問題模型變得更加複雜。
當前，TSN的發展如火如荼，然而，若想真正實現規模應用，必然要解決TSN混合+異構編排問題，這依賴於學術界、產業界，無數學者、工程師的共同努力。無論如何，在技術日益革新、國家大力發展工業互聯網的時代浪潮下，TSN的未來必將一片光明！
作者簡介：
高濤博士，華為公司數據通信產品線 研究工程師， 負責網絡演算理論、TSN編排算法、流量建模技術研究。2019年畢業於北京郵電大學獲博士學位。
作者聯係方式：im.taogao@outlook.com/
參考文獻：
[1] IEEE 802.1Qbv-2015
[2] Craciunas, Silviu S., et al. "Scheduling real-time communication in IEEE 802.1 Qbv time-sensitive networks." Proceedings of the 24th International Conference on Real-Time Networks and Systems. 2016.
[3] Steiner, Wilfried, Silviu S. Craciunas, and Ramon Serna Oliver. "Traffic planning for time-sensitive communication." IEEE Communications Standards Magazine 2.2 (2018): 42-47.
[4] Schweissguth, Eike, et al. "ILP-based joint routing and scheduling for time-triggered networks." Proceedings of the 25th International Conference on Real-Time Networks and Systems. 2017.
[5] Raagaard, Michael Lander, and Paul Pop. "Optimization algorithms for the scheduling of IEEE 802.1 Time-Sensitive Networking (TSN)." Tech. Univ. Denmark, Lyngby, Denmark, Tech. Rep (2017).
[6] Mai, Tieu Long, Nicolas Navet, and Jörn Migge. "A hybrid machine learning and schedulability analysis method for the verification of TSN networks." 2019 15th IEEE International Workshop on Factory Communication Systems (WFCS). IEEE, 2019.