基于軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制

汪碩，黃玉棟，黃韜，霍如，劉韻潔

（1.北京郵電大學(xué)網(wǎng)絡(luò)與交換國家重點(diǎn)實驗室，北京 100876；2.網(wǎng)絡(luò)通信與安全紫金山實驗室，江蘇 南京 211111；3.北京工業(yè)大學(xué)信息學(xué)部，北京 100124）

1 引言

在許多物理網(wǎng)絡(luò)環(huán)境中，如工業(yè)自動化、車載網(wǎng)絡(luò)、航空航天網(wǎng)絡(luò)，關(guān)鍵實時應(yīng)用對網(wǎng)絡(luò)的帶寬、時延、抖動、丟包率有嚴(yán)格的要求。一方面，當(dāng)前部署在物理網(wǎng)絡(luò)環(huán)境中的傳統(tǒng)總線存在帶寬速率低、標(biāo)準(zhǔn)互不兼容的缺點(diǎn)。另一方面，以太網(wǎng)相比于傳統(tǒng)總線具有支持更高帶寬速率、更低開銷，以及更易于與現(xiàn)有IT 系統(tǒng)整合的特點(diǎn)，但因其盡力而為的轉(zhuǎn)發(fā)模式存在長尾時延效應(yīng)，無法滿足關(guān)鍵實時應(yīng)用的傳輸要求。因此，時間敏感網(wǎng)絡(luò)（TSN,time-sensitive networking）致力于在以太網(wǎng)的基礎(chǔ)上增強(qiáng)確定性轉(zhuǎn)發(fā)能力，從而實現(xiàn)時間敏感流量和盡力而為流量的共網(wǎng)傳輸。

時間敏感網(wǎng)絡(luò)工作組提出的全網(wǎng)時鐘同步、時間感知門控等機(jī)制，已經(jīng)能夠滿足局域網(wǎng)范圍內(nèi)的實時應(yīng)用傳輸需求[1-2]。但隨著5G 超可靠低時延、云化PLC（programmable logic controller）、遠(yuǎn)程控制、工廠互聯(lián)等大規(guī)模時間敏感應(yīng)用的興起，如何實現(xiàn)時間敏感網(wǎng)絡(luò)的跨域調(diào)度成為當(dāng)前的一個重要挑戰(zhàn)。

時間敏感網(wǎng)絡(luò)的工業(yè)自動化標(biāo)準(zhǔn)[3]提出了時間敏感網(wǎng)絡(luò)域的概念，一個時間敏感網(wǎng)絡(luò)域是一個終端與交換設(shè)備的管理組。在機(jī)器與機(jī)器通信時，如控制器與執(zhí)行器、主動機(jī)械臂和從動機(jī)械臂、控制器與控制器間通信，存在機(jī)器屬于不同域的場景，跨域的應(yīng)用需要運(yùn)行在整個融合的時間敏感網(wǎng)絡(luò)域的頂層。在數(shù)據(jù)平面，Dorr 等[4]提出用域ID 標(biāo)識TSN 域，并將TSN 域抽象為虛擬網(wǎng)橋，然后根據(jù)目的MAC 地址、VLAN 值、優(yōu)先級值這3 個參數(shù)在發(fā)往鄰域的出端口進(jìn)行時間敏感流的識別與轉(zhuǎn)換。在控制平面，Chen[5]提出了一個新的配置實體間協(xié)議（CCP,config-entity to config-entity protocol）來進(jìn)行不同域的網(wǎng)絡(luò)控制器間的協(xié)商與信息傳輸，使用鏈路層發(fā)現(xiàn)協(xié)議來尋找相鄰的TSN 域。B?hm 等[6]設(shè)計了一個時間敏感網(wǎng)絡(luò)控制器間的東西向協(xié)議，并基于Ryu 控制器進(jìn)行了跨域的門控列表配置下發(fā)的概念原型驗證。

跨域調(diào)度的一個關(guān)鍵難題是如何生成多域融合的門控列表配置信息。以前的相關(guān)工作大多討論局域網(wǎng)內(nèi)的調(diào)度生成機(jī)制，其將鏈路時延視為零，且認(rèn)為單域內(nèi)設(shè)備時隙嚴(yán)格對齊。在最新的時間敏感網(wǎng)絡(luò)跨域研究中，文獻(xiàn)[7]通過部署確定性IP 路由器來保證每跳轉(zhuǎn)發(fā)時延有界且小于30 μs，成功驗證了可以在工廠邊緣利用虛擬PLC 跨域遠(yuǎn)程控制執(zhí)行器，但其只討論了一條時間敏感流與盡力而為流共傳的場景，未討論多條時間敏感流跨域調(diào)度的問題。文獻(xiàn)[8]將工廠車間網(wǎng)絡(luò)劃分為多個子網(wǎng)，并提出一種利用工廠網(wǎng)絡(luò)層次結(jié)構(gòu)的等時流量調(diào)度方法，其構(gòu)建了域內(nèi)域間分開調(diào)度的兩步調(diào)度思想，但并未給出嚴(yán)格意義的跨域調(diào)度框架和數(shù)學(xué)模型。

軟件定義網(wǎng)絡(luò)將網(wǎng)絡(luò)控制邏輯與其底層硬件分離，能夠提供網(wǎng)絡(luò)的全局視圖，實現(xiàn)網(wǎng)絡(luò)可編程。本文提出了基于軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制，聯(lián)合調(diào)度路徑、隊列和時隙資源，保證跨域場景下的流量有界時延指標(biāo)。該機(jī)制首先融合全球?qū)Ш叫l(wèi)星系統(tǒng)（GNSS,global navigation satellite system）[9]、廣域精確授時（WPT,wide-area precise timing）[10]、地面光纖高精度授時WR-PTP（white rabbit precision time protocol）[11]技術(shù)，實現(xiàn)跨域場景下的1～100 ns 域間時間同步，達(dá)到時間敏感網(wǎng)絡(luò)802.1AS 標(biāo)準(zhǔn)所要求的精度。然后，為解決域間設(shè)備長距鏈路時延帶來的時隙對齊問題，提出了時隙無沖突跨域調(diào)度模型，利用時隙無沖突約束嚴(yán)格限制跨域流量在邊緣節(jié)點(diǎn)出端口的到達(dá)時間，從而在疊加鏈路時延后得到精確的鄰域到達(dá)時間，最終在線計算生成融合各域的全局調(diào)度門控列表，通過精確的全局門控列表控制來保證流量時延有界。實驗結(jié)果表明，在典型的跨域遠(yuǎn)程工控場景下，該模型能調(diào)度上百條時間敏感流量，并具有可行的秒級的算法執(zhí)行時間。

2 背景與動機(jī)

2.1 全網(wǎng)時鐘同步

精確的全網(wǎng)時鐘同步是基于時隙的調(diào)度整形的基礎(chǔ)。時間敏感網(wǎng)絡(luò)的802.1AS-Rev 標(biāo)準(zhǔn)定義了通用精準(zhǔn)時鐘協(xié)議（gPTP,generalized precision time protocol），gPTP 利用最佳主時鐘選擇算法選出主時鐘，并以主時鐘為根節(jié)點(diǎn)形成樹狀拓?fù)?，在頻率對齊的基礎(chǔ)上，對設(shè)備和鏈路時延進(jìn)行實時測量補(bǔ)償校準(zhǔn)，其他節(jié)點(diǎn)以主時鐘為參考進(jìn)行匹配調(diào)節(jié)和主從同步，最終實現(xiàn)納秒級的全網(wǎng)時鐘同步。gPTP 與精確時鐘同步PTP 的區(qū)別在于它是一個完全基于二層網(wǎng)絡(luò)的非IP 路由的協(xié)議，其精簡了無關(guān)的二層機(jī)制，增強(qiáng)了二層的時間同步機(jī)制。

在工業(yè)領(lǐng)域，時鐘同步主要有普遍時鐘和工作時鐘這兩種同步要求[12]。普遍時鐘存在于工廠內(nèi)部和車間范圍，采用外接時鐘源來實現(xiàn)精度不低于100 μs 的工廠內(nèi)時間同步；工作時鐘主要應(yīng)用于生產(chǎn)線內(nèi)的設(shè)備和機(jī)器間的精度不低于1 μs的時間同步，例如具有精準(zhǔn)事件序列的機(jī)器人運(yùn)動控制、實時數(shù)據(jù)傳輸?shù)取Ｒ驗闀r間敏感網(wǎng)絡(luò)是一個局域網(wǎng)標(biāo)準(zhǔn)，目前還沒有涉及工廠間、跨域及廣域場景下的時鐘同步方案。

2.2 時間感知整形

為嚴(yán)格保障關(guān)鍵應(yīng)用的時延和抖動要求，在全網(wǎng)時鐘同步的基礎(chǔ)上，時間感知整形機(jī)制被提出。時間感知整形（TAS,time-aware shaper）是增強(qiáng)的出端口流量調(diào)度整形機(jī)制，采用類似時分復(fù)用的方式保證時間敏感的業(yè)務(wù)流在傳輸中具有逐跳的確定性時延。

TAS 在每一個優(yōu)先級隊列后增加了一個由門控列表里的門控條目驅(qū)動控制的門。當(dāng)門是打開狀態(tài)時，對應(yīng)隊列中業(yè)務(wù)流進(jìn)行出隊傳輸；當(dāng)門是關(guān)閉狀態(tài)時，對應(yīng)隊列中業(yè)務(wù)流不可被傳輸。在時間敏感流的隊列門打開前，TAS 通過設(shè)定保護(hù)帶寬，保證其他流量的傳輸不阻礙時間敏感流的傳輸。時間感知整形的配置對象為門控列表條目，每個條目需要配置的參數(shù)為時間點(diǎn)以及對應(yīng)時刻的門狀態(tài)（打開或者關(guān)閉），并可計算選配最大為1 522 B 的保護(hù)帶寬大小。在局域網(wǎng)范圍內(nèi)，基于時間感知整形的相關(guān)硬件設(shè)備已趨于成熟，相關(guān)局域調(diào)度和優(yōu)化算法已有大量的研究。Steiner[13]自2010 年開始利用SMT/OMT 求解器研究了時間觸發(fā)以太網(wǎng)中的時間觸發(fā)流的調(diào)度合成問題。Dürr 等[14]設(shè)計了一種基于整數(shù)線性規(guī)劃公式的車間工件調(diào)度模型來計算單局域網(wǎng)內(nèi)的門控列表，并提出了一種軟件定義的多周期流傳輸調(diào)度方法[15]。

2.3 動機(jī)

時間敏感網(wǎng)絡(luò)工作組提出的全網(wǎng)時鐘同步、時間感知門控等機(jī)制當(dāng)前被限制在7 跳網(wǎng)絡(luò)半徑的局域網(wǎng)范圍內(nèi)。但新興的5G超可靠低時延、云化PLC、遠(yuǎn)程控制、工廠互聯(lián)、邊緣實時計算等大規(guī)模時間敏感應(yīng)用要求實現(xiàn)跨域的實時流量調(diào)度。例如，云化PLC 場景需要將PLC 從生產(chǎn)線遷移到工廠邊緣甚至另一個工廠，從云端經(jīng)過城域網(wǎng)、接入網(wǎng)接入工廠內(nèi)部對機(jī)器設(shè)備進(jìn)行實時操作和運(yùn)動控制?；?G 的車路協(xié)同、虛擬現(xiàn)實交互場景，要求網(wǎng)絡(luò)達(dá)到1～10 ms 的端到端時延和微秒級抖動。

網(wǎng)絡(luò)中的一跳時延包括鏈路的傳播時延、交換機(jī)內(nèi)部的處理時延、出端口隊列的排隊時延，以及出端口發(fā)送的傳輸時延。因為局域網(wǎng)內(nèi)鏈路長度通常小于100 m，其調(diào)度算法將設(shè)備間的鏈路時延設(shè)為零，并認(rèn)為全網(wǎng)是嚴(yán)格時間同步的。然而，在跨域調(diào)度中，首先各個子域的設(shè)備時鐘只與該域的主時鐘進(jìn)行同步，域間缺少時鐘同步機(jī)制；其次，跨域傳輸?shù)逆溌窌r延不可忽視，從一個域的出端口傳輸?shù)搅硪粋€域的出端口，存在跨域端口的門控列表的時隙對齊問題，即如果包的到達(dá)存在抖動，則無法根據(jù)包在一個域的發(fā)送時間確定另一個域的門控列表的開關(guān)時間，時隙錯位嚴(yán)重時會導(dǎo)致跨域關(guān)鍵流量包丟失。

為解決上述問題，本文提出了基于軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制，通過軟件定義網(wǎng)絡(luò)技術(shù)將網(wǎng)絡(luò)控制邏輯與其底層硬件分離，利用其提供的網(wǎng)絡(luò)全局視圖，對跨域時間敏感流量實現(xiàn)確保有界時延抖動的全局調(diào)度。軟件定義產(chǎn)生的控制器開銷以及軟件定義網(wǎng)絡(luò)（SDN,software defined network）對TSN 的影響可參考控制架構(gòu)相關(guān)研究[6,16]。

3 軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制描述

3.1 軟件定義的時間敏感網(wǎng)絡(luò)

軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制如圖1所示，本文采用802.1Qcc 標(biāo)準(zhǔn)定義的全集中式控制架構(gòu)?？刂破矫娼M件包括中心化用戶配置（CUC,centralized user configuration）和中心化網(wǎng)絡(luò)控制器（CNC,central network controller）。CUC 相當(dāng)于編排器，負(fù)責(zé)采集終端業(yè)務(wù)的帶寬時延抖動等網(wǎng)絡(luò)服務(wù)質(zhì)量需求，并將其轉(zhuǎn)換后通過北向接口發(fā)給中心化網(wǎng)絡(luò)控制器；CNC 相當(dāng)于控制器，包含計算拓?fù)渎窂降染W(wǎng)絡(luò)功能，并通過南向接口下發(fā)更新路由路徑、門控列表等配置信息給時間敏感網(wǎng)絡(luò)交換機(jī)。

圖1 軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制

數(shù)據(jù)平面設(shè)備包括時間敏感交換機(jī)和終端。時間敏感交換機(jī)支持時鐘同步和時間感知整形機(jī)制，每個交換機(jī)的出端口有0～7 共8 個優(yōu)先級隊列，其中時間敏感流量被標(biāo)記為最高優(yōu)先級7，盡力而為流量被標(biāo)記為剩余的低優(yōu)先級。終端軟件間的語義互操作采用開放平臺通信統(tǒng)一架構(gòu)（OPC-UA,open platform communications united architecture）的發(fā)布訂閱模式，以保證發(fā)布者和訂閱者能在跨域調(diào)度代理機(jī)中基于統(tǒng)一數(shù)據(jù)結(jié)構(gòu)的主題進(jìn)行交互。

時間敏感網(wǎng)絡(luò)的跨域調(diào)度工作流程如下。1)TSN 域A 中的發(fā)送端向中心化用戶配置發(fā)起連接建立請求；2) 中心化用戶配置將發(fā)送端的業(yè)務(wù)服務(wù)質(zhì)量請求轉(zhuǎn)換為具體的網(wǎng)絡(luò)需求參數(shù)，并下發(fā)給中心化網(wǎng)絡(luò)控制器；3) 中心化網(wǎng)絡(luò)控制器根據(jù)A 域的拓?fù)浜蜁r隙資源計算跨域流量在A 域的門控列表配置信息；4) 中心化網(wǎng)絡(luò)控制器根據(jù)A 域的出端口門控時間以及跨鏈路時延，計算得到流量到達(dá)B 域的時間，再根據(jù)B 域的拓?fù)浜蜁r隙資源計算跨域流量在B 域的門控列表配置信息；5) 若跨域調(diào)度成功，則分別對兩域的交換機(jī)下發(fā)更新門控列表配置；6) 中心化用戶配置響應(yīng)請求，返回具體的發(fā)包開始時間給發(fā)送端。

3.2 域間時鐘同步

本文機(jī)制首先基于 GNSS[9]、WPT[10]、WR-PTP[11]技術(shù)來協(xié)同保障跨域場景下的1～100 ns域間時間同步，從而達(dá)到時間敏感網(wǎng)絡(luò)802.1AS 標(biāo)準(zhǔn)所要求的精度。

在TSN 域內(nèi)，主節(jié)點(diǎn)配置高級晶振主時鐘（銫原子鐘或銣原子鐘），其授時精度近似于世界協(xié)調(diào)時間這一基準(zhǔn)時間，可作為域內(nèi)的主時鐘；其他節(jié)點(diǎn)為從時鐘，主從時鐘間通過通用精準(zhǔn)時鐘協(xié)議實現(xiàn)精確時間同步。

在TSN 域間，可采用包括美國的全球定位系統(tǒng)GPS 和中國的北斗衛(wèi)星系統(tǒng)在內(nèi)的全球?qū)Ш叫l(wèi)星系統(tǒng)進(jìn)行衛(wèi)星授時。衛(wèi)星時鐘和晶振時鐘的誤差特性互補(bǔ)。衛(wèi)星時鐘的秒時鐘誤差服從正態(tài)分布，隨機(jī)誤差大，累積誤差??；而晶振時鐘與國際標(biāo)準(zhǔn)時間相比，每秒的時間偏移很小，且偏移量較穩(wěn)定，其隨機(jī)誤差小，累積誤差大。衛(wèi)星時鐘與晶振時鐘通過具有信號跟蹤能力的數(shù)字鎖相環(huán)進(jìn)行結(jié)合，產(chǎn)生高精度和高穩(wěn)定性的時鐘。此外，基于GNSS 載波相位觀測量及狀態(tài)空間域改正的廣域精確授時技術(shù)，在中國科學(xué)院國家授時中心經(jīng)過連續(xù)數(shù)月的測試后驗證了授時精度能夠達(dá)到0.48 ns。最后，基于光纖網(wǎng)絡(luò)的地面高精度授時系統(tǒng)能實現(xiàn)1 000 km 覆蓋范圍內(nèi)的納秒級時鐘同步，也可作為域間時鐘同步的補(bǔ)充。

3.3 調(diào)度時隙設(shè)計

為了實現(xiàn)時間敏感流的有界時延抖動傳輸，時間控制的門根據(jù)門控列表條目在隊列中每個時隙的開始處執(zhí)行打開或關(guān)閉操作。以圖1 為例，當(dāng)時間敏感流在T00 時刻到達(dá)時，隊列7 的門打開，使時間敏感流無排隊地開始傳輸，而其余門關(guān)閉。在時間敏感流傳輸完成之后，其余的門在T01 時刻打開以傳輸盡力而為流，而隊列7 的門關(guān)閉。在時間敏感流再次到達(dá)之前，在T02 時刻，所有門都關(guān)閉以形成最大傳輸單元大小的保護(hù)帶。最后，重復(fù)執(zhí)行門控列表的條目以進(jìn)行周期傳輸調(diào)度。

因此，流的調(diào)度由門控列表的計算決定，而計算的優(yōu)化取決于時隙劃分的設(shè)計和時間敏感流發(fā)送開始時間的確定。為滿足中心化調(diào)度的實時性，本文設(shè)計了在線增量式調(diào)度方法和變長調(diào)度時隙。一方面，以前的離線調(diào)度方法[14,17-18]要求提前已知所有流的信息，需要花費(fèi)數(shù)小時甚至數(shù)天的時間進(jìn)行計算，以合成接近最優(yōu)的調(diào)度方案；本文采用增量式調(diào)度方法，按流的固有順序逐流計算流的調(diào)度方案，從而減少計算時間開銷，保證中心化控制器調(diào)度的實時性。另一方面，離線調(diào)度為簡化計算參數(shù)，常將時隙大小設(shè)為固定值，如傳輸最大傳輸單元大小的包所需的時間[19-20],甚至傳輸7 跳長度所需的時間[15]，造成極大的帶寬和時隙資源浪費(fèi)；本文采用變長調(diào)度時隙，根據(jù)包的實際大小計算出包的傳輸時延，并將其作為模型的調(diào)度時隙，從而提高帶寬利用率。

4 時隙無沖突的跨域調(diào)度模型

在域間保證嚴(yán)格的時鐘同步后，針對時間敏感流量跨域調(diào)度的時隙對齊問題，本節(jié)設(shè)計了時隙無沖突的跨域調(diào)度數(shù)學(xué)模型?？缬蛘{(diào)度需要解決3 個問題：1) 如何設(shè)計跨域流量在域A 內(nèi)的傳輸調(diào)度，以保證流能準(zhǔn)時準(zhǔn)確地到達(dá)域邊節(jié)點(diǎn)；2) 如何獲得跨域到達(dá)時刻，以計算域B 的門控列表，并保證兩域的門控時隙對齊；3) 如何壓縮域間流量所使用的時隙資源，以保留更多的時隙資源給域內(nèi)流量。

4.1 輸入和決策變量

本文使用花體字母表示集合，使用大寫粗體字母表示矩陣，使用小寫粗體字母表示向量。網(wǎng)絡(luò)拓?fù)浣橛邢驁DG=(V ,E)，其中，V 是節(jié)點(diǎn)集合，E是邊的集合。此外，V=(S ∪H)，其中S 和H 分別是交換機(jī)和主機(jī)的集合。E是一組表示網(wǎng)絡(luò)中鏈路的元組，E={(i,j)|i,j∈V,i≠j}，并且節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在一條邊?？缬虻臅r間敏感流被表示為元組f=(sf,df,pf,tf,dlf)，其中，sf是源節(jié)點(diǎn)，df是目的節(jié)點(diǎn)，pf是發(fā)送周期，tf是流的傳輸時延，dlf是流的截止時間。

表1 給出了用于調(diào)度問題的拓?fù)湎嚓P(guān)和流相關(guān)的參數(shù)[21]。

表1 拓?fù)浼傲飨嚓P(guān)參數(shù)

超周期等于所有流量周期的最小公倍數(shù)。在每個超周期中，傳輸模式從全局角度重復(fù)，因此只需要確保時間敏感流在一個超周期長度上滿足調(diào)度約束。下面介紹跨域時隙無沖突調(diào)度的決策變量、約束條件和求解目標(biāo)。

為了描述邊與邊之間的關(guān)系，本文使用邊-邊鄰接矩陣AEE的元素的值，并在行ep∈E和列en∈E有如下定義。

式(1)表明，如果節(jié)點(diǎn)v∈V 既是邊ep的目的節(jié)點(diǎn)又是邊en的源節(jié)點(diǎn)，則AEE[ep][en]值為1；否則為0。|E|表示邊集合中的元素數(shù)量。

為了描述流與邊之間的關(guān)系，本文使用一組二進(jìn)制決策變量u∈{0,1}|F|×|E|并有如下定義。

本文采用最短路徑算法來確定路由，且對于每一個u[fcd][e]=1，有一個傳輸開始時間矩陣的值t[fcd][e]表示流fcd在邊e上的傳輸開始時間。

整數(shù)線性規(guī)劃是一個被廣泛用于建模網(wǎng)絡(luò)調(diào)度問題的數(shù)學(xué)工具，且有成熟商用的高性能求解器。該整數(shù)線性規(guī)劃模型的輸入變量和決策變量如下。

1) 輸入變量

? 全局網(wǎng)絡(luò)拓?fù)鋱D為G=(V ,E)。

? 跨域時間敏感流集合為Fcd?N。

2) 決策變量

? 流所流經(jīng)的邊的向量為u[fcd][e]。

? 流在邊上的傳輸開始時間為t[fcd][e]。

4.2 約束條件

為保證跨域流量在域A 內(nèi)能準(zhǔn)時準(zhǔn)確地到達(dá)域邊節(jié)點(diǎn)，本文采用時隙無沖突調(diào)度模型，即每個包在交換機(jī)的出端口進(jìn)行傳輸?shù)拈_始互不沖突，一個包完全傳輸完成后再傳輸下一個包。這樣實現(xiàn)了出端口最大隊列長度為1，因此排隊時延為0，包在到達(dá)域邊節(jié)點(diǎn)時不會產(chǎn)生抖動。其約束條件如下。

1) 傳輸開始時間約束

如果流在邊上的傳輸開始時間t[fcd][e]大于流的發(fā)送周期，則它應(yīng)該對流的周期取模以符合周期性調(diào)度，如式(3)所示。式(4)確保每個輸出端口上的流傳輸在下一個傳輸周期開始之前結(jié)束，即流在超周期中各個發(fā)送周期內(nèi)的傳輸互不影響。時間表t[fcd][e]中的每一列都代表邊的門控狀態(tài)改變的時間點(diǎn)，用該時間點(diǎn)可合成每個輸出端口上的門控列表。

2) 時隙無沖突約束

在任何周期內(nèi)，對于流fcd1和任何流fcd2，每個交換機(jī)的出端口的傳輸時間都不重疊。該約束定義為

其中

3) 域內(nèi)鄰邊約束

在域內(nèi)，鏈路傳播時延可視為0，又因為采用時隙無沖突調(diào)度，排隊時延也為0，因此一跳時延等于交換機(jī)內(nèi)處理時延加出端口傳輸時延，是一個恒定值。前一條邊的傳輸開始時間t[fcd][ep]加上一跳時延hF[fcd]（如果超出流周期，則錯開一個周期），等于下一跳的傳輸開始時間t[fcd][en]。該約束定義為

?ep∈E,?en∈E:ep≠en,且AEE[ep][en]=1,

?fcd∈Fcd:

若u[fcd][ep]+u[fcd][en] ≥ 2,則

4) 域間鄰邊約束

在域間，鏈路傳播時延不可視為0，假設(shè)域間鏈路時延為λ，則到達(dá)域B 的傳輸開始時間t[fcd][en]等于域 A 邊緣節(jié)點(diǎn)的傳輸開始時間t[fcd][ep]加上一跳時延hF[fcd]以及域間鏈路時延λ。根據(jù)式(7)可獲得跨域到達(dá)時刻以計算域B 的門控列表，并保證兩域的門控時隙對齊。該約束定義為

?ep∈E,?en∈E:ep≠en,且AEE[ep][en]=1

ep∈域A,en∈域B

?fcd∈Fcd:

若u[fcd][ep]+u[fcd][en] ≥ 2,則

5) 截止時間約束

對于每一條跨域流量，其端到端時延由域A 內(nèi)逐跳時延之和、跨域鏈路時延以及域B 內(nèi)逐跳時延之和三部分組成。該約束要求流在截止時間之內(nèi)到達(dá)目的節(jié)點(diǎn)，即

4.3 目標(biāo)函數(shù)

為保留更多的時隙資源給域內(nèi)流量，本文壓縮域間流量所使用的時隙資源，將模型的目標(biāo)函數(shù)設(shè)置為最小化跨域時間敏感流在發(fā)送第一跳的邊es的發(fā)送開始時間，該發(fā)送時間定義為SST，目標(biāo)函數(shù)可以表示為

5 仿真實驗

本節(jié)評估在第4 節(jié)所述時隙無沖突跨域調(diào)度模型的性能。首先給出仿真設(shè)置；然后評估模型求解性能，包括流調(diào)度能力、可擴(kuò)展性和執(zhí)行時間。

5.1 仿真設(shè)置

本文仿真使用Python 實現(xiàn)時隙無沖突跨域調(diào)度實例，使用Networkx 圖形庫創(chuàng)建復(fù)雜的網(wǎng)絡(luò)拓?fù)洌刹煌牧髁磕Ｊ?，使用IBM ILOG CPLEX優(yōu)化求解器的Python API（Linux 版本12.10.0）求解整數(shù)線性規(guī)劃公式。計算服務(wù)器配有4 個英特爾i5-8259U 中央處理單元和16 GB 的隨機(jī)存取存儲器。

1) 拓?fù)溥x擇

線形、環(huán)形和雪花形是工業(yè)控制網(wǎng)絡(luò)的主要拓?fù)漕愋蚚22]。本文將A/B 域各有8 個節(jié)點(diǎn)的這3 種拓?fù)渥鳛闇y試拓?fù)浣Y(jié)構(gòu)，在域的邊緣隨機(jī)選擇一個節(jié)點(diǎn)作為跨域連接節(jié)點(diǎn)。鏈路帶寬被設(shè)置為1 Gbit/s。為了驗證算法的可擴(kuò)展性，將跨域鏈路時延集合設(shè)置為{0.2,1,5}ms，分別代表接入網(wǎng)、城域網(wǎng)、廣域網(wǎng)3 種不同距離的網(wǎng)絡(luò)中[23]的跨域調(diào)度場景。

2) 流量生成

對于集合中的每個流f，通過從頂點(diǎn)集合中均等概率地選擇2 個值來創(chuàng)建源節(jié)點(diǎn)和目的節(jié)點(diǎn)，以降低路由算法對調(diào)度結(jié)果的影響。所有流量都在廣域監(jiān)視和控制系統(tǒng)（由IEC 61850 定義）以及DetNet用例的工業(yè)機(jī)器與機(jī)器通信的流量特性的指導(dǎo)下生成[24]。數(shù)據(jù)包長度為100～1 500 B。通常流的發(fā)送周期和截止時間為毫秒量級，從集合{1,2,4,8}ms中隨機(jī)抽取一個值來模擬發(fā)送周期pF，從20～50 ms隨機(jī)選擇一個值來模擬流的截止時間dlF，以保證實驗的普遍適用性。

5.2 調(diào)度能力仿真結(jié)果

調(diào)度能力表示可調(diào)度跨域時間敏感流的數(shù)量。設(shè)置跨域鏈路時延為0.2 ms，將流數(shù)量劃分為200～800 條的4 個級別，每個級別進(jìn)行5 次實驗，取平均值作為結(jié)果。當(dāng)前工廠互聯(lián)、遠(yuǎn)程控制等跨域時間敏感應(yīng)用需求遠(yuǎn)小于域內(nèi)應(yīng)用，因此上百條流已經(jīng)可以滿足當(dāng)前的調(diào)度需求。探索調(diào)度上千條跨域流量將作為未來工作。

環(huán)形拓?fù)湎?，不同時隙大小對調(diào)度能力的影響如圖2 所示。在調(diào)度200 條流時，變長時隙和最大傳輸單元（MTU,maximum transmission unit）大小的時隙均能調(diào)度接近100%的流量，而以7 跳MTU 大小為時隙的方案只能調(diào)度約40%的流量。隨著流數(shù)量增加，各方案調(diào)度能力均有所下降，但變長時隙一直保持最高的可調(diào)度流數(shù)量；相比于MTU 固定時隙，變長時隙的調(diào)度能力最大提升了18%，相比于7 跳MTU 固定時隙，變長時隙的調(diào)度能力最大提升了69%。因此，后面的調(diào)度仿真均采用變長時隙方案。

圖2 不同時隙大小對調(diào)度能力的影響

不同拓?fù)鋵φ{(diào)度能力的影響如圖3 所示，雪花形拓?fù)渲锌烧{(diào)度的流數(shù)量最多，線形拓?fù)渲锌烧{(diào)度的流數(shù)量最少，環(huán)形拓?fù)渑c雪花形拓?fù)浣咏?。其原因是線形拓?fù)淞髡{(diào)度時流經(jīng)的跳數(shù)更多，單條流會占用更多的出端口時隙資源，導(dǎo)致調(diào)度能力下降。在調(diào)度800 條流時，雪花形拓?fù)渲械恼{(diào)度能力比線形拓?fù)涮嵘?4.5%。

圖3 不同拓?fù)鋵φ{(diào)度能力的影響

5.3 可擴(kuò)展性仿真結(jié)果

環(huán)形拓?fù)湎?，將流?shù)量劃分為200～800 條的4 個級別，不同跨域距離對模型可擴(kuò)展性的影響如圖4所示。接入網(wǎng)、城域網(wǎng)、廣域網(wǎng)這3 種網(wǎng)絡(luò)中，模型的可調(diào)度流數(shù)量相差不大，最低也保持了77.5%的調(diào)度能力。因此，隨著跨域鏈路時延增大，模型的調(diào)度能力沒有下降，該模型具有良好的可擴(kuò)展性。

圖4 不同跨域距離對模型可擴(kuò)展性的影響

此外，本節(jié)設(shè)置了兩組發(fā)送周期，一組高頻周期為{1,2,4,8} ms，一組低頻周期為{4,8}ms。0.2 ms跨域鏈路時延下，不同發(fā)送周期對模型可擴(kuò)展性的影響如圖5 所示，低頻周期組在4 個流級別均能調(diào)度100%的流量。這是因為低頻流在一個超周期內(nèi)占用的時隙資源相比高頻流更少，產(chǎn)生調(diào)度沖突的概率大大降低。隨著流的發(fā)送周期增大，模型的調(diào)度能力將顯著提高。

圖5 不同發(fā)送周期對模型可擴(kuò)展性的影響

5.4 執(zhí)行時間仿真結(jié)果

本節(jié)在環(huán)形拓?fù)洹?.2 ms 跨域鏈路時延下，將流數(shù)量劃分為200～800 條的4 個級別，對比了在線調(diào)度和離線調(diào)度的執(zhí)行時間。因為執(zhí)行時間的值變化很大，將log10 的對數(shù)函數(shù)作為執(zhí)行時間，其累積分布函數(shù)如圖6 所示，隨著調(diào)度流數(shù)量增多，在線調(diào)度執(zhí)行時間不斷增大，但最少有60%的流量逐流調(diào)度時間小于1 s，所有流的逐流調(diào)度時間均小于10 s，即具有秒級的在線調(diào)度執(zhí)行時間；而離線調(diào)度需要數(shù)小時，平均每條流需要幾十秒的執(zhí)行時間，因此離線調(diào)度的累積分布函數(shù)是一條直線，遠(yuǎn)大于在線調(diào)度方法。

圖6 在線和離線調(diào)度的執(zhí)行時間對比

6 結(jié)束語

本文提出了基于軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機(jī)制，融合了3 種廣域時鐘同步技術(shù)來保障納秒級域間時間同步，設(shè)計了時隙無沖突跨域調(diào)度模型，解決了域間鏈路時延帶來的時隙對齊問題。實驗結(jié)果表明，在典型的跨域工控場景下，該模型能調(diào)度上百條時間敏感流量，并具有秒級的逐流執(zhí)行時間。