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

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

1 引言

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

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

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

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

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

2 背景與動(dòng)機(jī)

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

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

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

2.2 時(shí)間感知整形

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

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

2.3 動(dòng)機(jī)

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

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

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

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

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

軟件定義的時(shí)間敏感網(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ù)的帶寬時(shí)延抖動(dòng)等網(wǎng)絡(luò)服務(wù)質(zhì)量需求，并將其轉(zhuǎn)換后通過(guò)北向接口發(fā)給中心化網(wǎng)絡(luò)控制器；CNC 相當(dāng)于控制器，包含計(jì)算拓?fù)渎窂降染W(wǎng)絡(luò)功能，并通過(guò)南向接口下發(fā)更新路由路徑、門(mén)控列表等配置信息給時(shí)間敏感網(wǎng)絡(luò)交換機(jī)。

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

數(shù)據(jù)平面設(shè)備包括時(shí)間敏感交換機(jī)和終端。時(shí)間敏感交換機(jī)支持時(shí)鐘同步和時(shí)間感知整形機(jī)制，每個(gè)交換機(jī)的出端口有0～7 共8 個(gè)優(yōu)先級(jí)隊(duì)列，其中時(shí)間敏感流量被標(biāo)記為最高優(yōu)先級(jí)7，盡力而為流量被標(biāo)記為剩余的低優(yōu)先級(jí)。終端軟件間的語(yǔ)義互操作采用開(kāi)放平臺(tái)通信統(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)行交互。

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

3.2 域間時(shí)鐘同步

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

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

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

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

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

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

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

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

4.1 輸入和決策變量

本文使用花體字母表示集合，使用大寫(xiě)粗體字母表示矩陣，使用小寫(xiě)粗體字母表示向量。網(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之間存在一條邊。跨域的時(shí)間敏感流被表示為元組f=(sf,df,pf,tf,dlf)，其中，sf是源節(jié)點(diǎn)，df是目的節(jié)點(diǎn)，pf是發(fā)送周期，tf是流的傳輸時(shí)延，dlf是流的截止時(shí)間。

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

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

超周期等于所有流量周期的最小公倍數(shù)。在每個(gè)超周期中，傳輸模式從全局角度重復(fù)，因此只需要確保時(shí)間敏感流在一個(gè)超周期長(zhǎng)度上滿足調(diào)度約束。下面介紹跨域時(shí)隙無(wú)沖突調(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|表示邊集合中的元素?cái)?shù)量。

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

本文采用最短路徑算法來(lái)確定路由，且對(duì)于每一個(gè)u[fcd][e]=1，有一個(gè)傳輸開(kāi)始時(shí)間矩陣的值t[fcd][e]表示流fcd在邊e上的傳輸開(kāi)始時(shí)間。

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

1) 輸入變量

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

? 跨域時(shí)間敏感流集合為Fcd?N。

2) 決策變量

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

? 流在邊上的傳輸開(kāi)始時(shí)間為t[fcd][e]。

4.2 約束條件

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

1) 傳輸開(kāi)始時(shí)間約束

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

2) 時(shí)隙無(wú)沖突約束

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

其中

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

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

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

?fcd∈Fcd:

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

4) 域間鄰邊約束

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

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

ep∈域A,en∈域B

?fcd∈Fcd:

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

5) 截止時(shí)間約束

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

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

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

5 仿真實(shí)驗(yàn)

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

5.1 仿真設(shè)置

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

1) 拓?fù)溥x擇

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

2) 流量生成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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