SSA:一種面向CQF模型的TSN資源調(diào)度算法

姜旭艷， 嚴(yán)錦立， 全 巍， 孫志剛

(國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院， 湖南 長(zhǎng)沙 410073)

工業(yè)控制網(wǎng)絡(luò)和5G網(wǎng)絡(luò)中包括時(shí)間敏感流、帶寬約束型流量和Best-Effort流量，其中優(yōu)先級(jí)最高的時(shí)間敏感流通常具有周期性的特點(diǎn)，對(duì)端到端延遲和抖動(dòng)有著嚴(yán)格的要求，延遲通常在毫秒級(jí)別[1].例如在能源開(kāi)采應(yīng)用中，網(wǎng)絡(luò)時(shí)延在250 μs～1 ms之間，抖動(dòng)不能超過(guò)1μs.如果不能保證服務(wù)質(zhì)量(quality of service，QoS)，整個(gè)生產(chǎn)過(guò)程就會(huì)失敗，甚至導(dǎo)致系統(tǒng)癱瘓.因此，保證時(shí)間敏感流量的服務(wù)質(zhì)量對(duì)系統(tǒng)的安全穩(wěn)定運(yùn)行至關(guān)重要[2].

標(biāo)準(zhǔn)以太網(wǎng)是競(jìng)爭(zhēng)性網(wǎng)絡(luò)，數(shù)據(jù)傳輸由于排隊(duì)等因素具有不確定性，只能提供盡力而為的服務(wù)，無(wú)法保證時(shí)間敏感流的服務(wù)質(zhì)量[3].IEEE 802.1時(shí)間敏感網(wǎng)絡(luò)任務(wù)組提出的實(shí)時(shí)以太網(wǎng)技術(shù)——時(shí)間敏感網(wǎng)絡(luò)(TSN)，利用全局時(shí)間同步、確定性分組轉(zhuǎn)發(fā)、幀復(fù)制及冗余消除等技術(shù)為時(shí)間敏感流提供低延遲、低抖動(dòng)的確定性傳輸服務(wù)[4]，目前已經(jīng)逐漸應(yīng)用到工業(yè)控制領(lǐng)域和5G網(wǎng)絡(luò)中.保證TSN性能的關(guān)鍵在于時(shí)間同步和資源調(diào)度，時(shí)間同步是保證服務(wù)質(zhì)量的前提，資源調(diào)度是實(shí)現(xiàn)確定性傳輸?shù)年P(guān)鍵.目前時(shí)間同步已有詳細(xì)的標(biāo)準(zhǔn)及算法，而資源調(diào)度在不同的調(diào)度模型和應(yīng)用中存在很大差異.隨著網(wǎng)絡(luò)規(guī)模不斷增長(zhǎng)、應(yīng)用需求愈發(fā)復(fù)雜，研究高效的TSN資源調(diào)度算法對(duì)TSN的大規(guī)模應(yīng)用具有重要意義.

資源調(diào)度主要包括數(shù)據(jù)平面的調(diào)度模型和控制平面的調(diào)度算法，調(diào)度算法根據(jù)約束條件將調(diào)度模型的資源(如隊(duì)列資源、時(shí)隙資源、帶寬資源等)合理分配給網(wǎng)絡(luò)中的時(shí)間敏感流和其他類型的流量，同時(shí)要最大化網(wǎng)絡(luò)資源利用率.資源調(diào)度問(wèn)題可以歸納為一個(gè)裝箱問(wèn)題，即從時(shí)間和空間兩個(gè)維度上合理地為報(bào)文分配鏈路資源，因此是一個(gè)NP完全問(wèn)題[5].

現(xiàn)有的資源調(diào)度模型主要包括TTTech公司提出的時(shí)間觸發(fā)以太網(wǎng)(time-triggered Ethernet，TTEthernet)中的交換模型和TSN中的時(shí)間感知的整形器(time aware shaper，TAS).TTEthernet根據(jù)靜態(tài)的調(diào)度表(schedule table)對(duì)時(shí)間敏感流進(jìn)行逐跳的轉(zhuǎn)發(fā)控制.TAS的原理類似于TTEthernet中的調(diào)度表，但TTEthernet調(diào)度的粒度是數(shù)據(jù)流，而TAS調(diào)度的粒度則是隊(duì)列.控制平面的調(diào)度算法包括SMT Solver、OMT Solver、ILP Solver和禁忌搜索算法等[6-8]，這些算法雖然能夠得到可行的調(diào)度方案，但是逐跳地分配鏈路資源的計(jì)算復(fù)雜度通常較高.為了降低復(fù)雜度，通過(guò)對(duì)TAS進(jìn)行簡(jiǎn)單配置，提出了循環(huán)隊(duì)列轉(zhuǎn)發(fā)模型CQF.CQF根據(jù)奇偶時(shí)隙進(jìn)行隊(duì)列切換，每個(gè)時(shí)隙只有一個(gè)隊(duì)列能夠傳輸報(bào)文，另一個(gè)隊(duì)列用于接收?qǐng)?bào)文.目前缺乏基于CQF模型的資源調(diào)度算法.

1 相關(guān)研究

工業(yè)控制網(wǎng)絡(luò)中的實(shí)時(shí)數(shù)據(jù)交換從基于總線的交換向以太網(wǎng)交換演進(jìn)，標(biāo)準(zhǔn)的以太網(wǎng)技術(shù)無(wú)法滿足實(shí)時(shí)系統(tǒng)的要求，在標(biāo)準(zhǔn)以太網(wǎng)的基礎(chǔ)上發(fā)展起來(lái)的時(shí)間敏感網(wǎng)絡(luò)TSN和時(shí)間觸發(fā)網(wǎng)絡(luò)TTEthernet能夠?yàn)橄到y(tǒng)中的時(shí)間敏感流提供低延遲、低抖動(dòng)的傳輸服務(wù).

在TSN和TTEthernet中，關(guān)于資源調(diào)度問(wèn)題的研究主要從數(shù)據(jù)平面的調(diào)度模型和控制平面的調(diào)度算法兩個(gè)方面展開(kāi).調(diào)度模型實(shí)現(xiàn)確定性轉(zhuǎn)發(fā)機(jī)制，向控制平面提供可配置的資源.控制平面則根據(jù)流量及調(diào)度模型的特征構(gòu)建約束條件，使用調(diào)度算法求解可行的調(diào)度方案，根據(jù)調(diào)度方案對(duì)數(shù)據(jù)平面進(jìn)行配置.文獻(xiàn)[5，8-10]采用SMT為T(mén)TEthernet中的時(shí)間敏感流尋找滿足約束條件的可行解，文獻(xiàn)[11]則采用Tabu搜索算法尋找最優(yōu)的調(diào)度方案.所有流量特征是預(yù)知的，離線地計(jì)算滿足網(wǎng)絡(luò)約束(鏈路資源、交換機(jī)資源、端到端延遲等)和應(yīng)用約束(發(fā)送依賴等)的調(diào)度方案，為每個(gè)數(shù)據(jù)幀規(guī)劃沿路由路徑的每個(gè)交換機(jī)上的發(fā)送時(shí)刻.

TSN的TAS調(diào)度模型對(duì)應(yīng)的調(diào)度算法是在滿足約束條件的前提下配置控制每個(gè)隊(duì)列傳輸開(kāi)關(guān)的時(shí)間門(mén)控表.文獻(xiàn)[6]發(fā)現(xiàn)TAS中存在輸出端幀交錯(cuò)的問(wèn)題，需要增加隊(duì)列隔離、流隔離等方式解決，并采用SMT找到滿足約束的可行解.除此之外還提出使用OMT，通過(guò)設(shè)定最優(yōu)化目標(biāo)，求解滿足約束條件的最優(yōu)解.文獻(xiàn)[1，7]則使用ILP建模求解調(diào)度問(wèn)題.除此之外，為了解決大規(guī)模網(wǎng)絡(luò)下的調(diào)度問(wèn)題，文獻(xiàn)[7]提出基于Tabu的啟發(fā)式算法以降低計(jì)算開(kāi)銷(xiāo).上述這些方法都是基于TAS模型提出的調(diào)度方案，而對(duì)于CQF模型，目前缺乏相應(yīng)的資源調(diào)度算法.本文將CQF模型中的調(diào)度問(wèn)題抽象為多約束條件下的資源規(guī)劃最大化問(wèn)題，提出了一種基于起始時(shí)隙分配的輕量級(jí)的資源調(diào)度算法SSA.SSA借鑒了貪心算法的思想，與TAS中使用啟發(fā)式方法的調(diào)度算法相比，計(jì)算開(kāi)銷(xiāo)低.除了貪心算法之外，也可以使用其他方法，例如Tabu搜索算法、SMT等工具求解本文提出的多約束條件下的資源最大化問(wèn)題.

TSN和TTEthernet中不同調(diào)度模型所對(duì)應(yīng)的調(diào)度算法的特點(diǎn)及解決方案如表1所示.

2 研究動(dòng)機(jī)

IEEE 802.1Qch提出的循環(huán)隊(duì)列轉(zhuǎn)發(fā)模型是對(duì)IEEE 802.1Qci per-stream filtering and policing(PSFP)和IEEE 802.1Qbv time aware shaper(TAS)的一種簡(jiǎn)單配置，它通過(guò)流量整形為關(guān)鍵數(shù)據(jù)流提供確定且易于計(jì)算的延遲服務(wù)[7].PSFP提供過(guò)濾、分類和流量監(jiān)管功能；TAS提出了門(mén)控機(jī)制，隊(duì)列后面的門(mén)結(jié)構(gòu)根據(jù)門(mén)控列表(gate control list)指定的時(shí)隙來(lái)改變狀態(tài).

CQF由一個(gè)循環(huán)定時(shí)器(cycle timer)和兩個(gè)傳輸隊(duì)列構(gòu)成.在CQF模型中，全局時(shí)間被劃分為等長(zhǎng)的時(shí)隙，數(shù)據(jù)傳輸需要遵循以下兩條規(guī)則:1)上游交換機(jī)傳輸報(bào)文的時(shí)隙與下游的鄰居交換機(jī)接收?qǐng)?bào)文的時(shí)隙相同；2)交換機(jī)在某個(gè)時(shí)隙內(nèi)接收的報(bào)文一定會(huì)在下一個(gè)時(shí)隙傳輸出去.基于上述兩條規(guī)則，奇數(shù)時(shí)隙，隊(duì)列Q7保存輸入端口接收的幀(接收模式，不發(fā)送幀)，同時(shí)隊(duì)列Q6發(fā)送在上一個(gè)偶數(shù)時(shí)隙緩存的數(shù)據(jù)幀(發(fā)送模式，不接收幀)，如圖1a所示；偶數(shù)時(shí)隙，操作相反，如圖1b所示.

基于上述傳輸方式，CQF可以確定報(bào)文的延遲范圍.假定時(shí)隙長(zhǎng)度為d，鏈路速率足夠大，交換機(jī)SWi要將報(bào)文msg傳輸給下游的鄰居交換機(jī)SWj.在最壞情況下，若SWi在時(shí)隙slotk的開(kāi)始時(shí)刻將報(bào)文msg傳輸?shù)絊Wj，SWj在時(shí)隙slotk+1的結(jié)束時(shí)刻將msg傳輸出去，那么msg在這兩個(gè)交換機(jī)之間的延遲就是2d；在最好情況下，若SWi在時(shí)隙slotk的結(jié)束時(shí)刻將msg傳輸?shù)絊Wj，SWj在時(shí)隙slotk+1的開(kāi)始時(shí)刻(即時(shí)隙slotk的結(jié)束時(shí)刻)將msg傳輸出去，那么msg在這兩個(gè)交換機(jī)之間的延遲就是0.將上述情況一般化，假定h為跳數(shù)(路由路徑上的交換機(jī)的數(shù)目)，那么一個(gè)幀的最大延遲maxDelay和最小延遲minDelay即

maxDelay=(h+1)d,

(1)

minDelay=(h-1)d.

(2)

換言之，一個(gè)幀的端到端延遲范圍由時(shí)隙長(zhǎng)度和跳數(shù)確定.

圖2a所示TSN網(wǎng)絡(luò)中包含三個(gè)終端host1、host2和host3以及一臺(tái)交換機(jī)SW1.假定時(shí)隙長(zhǎng)度為150 μs，交換機(jī)的輸出端口中每個(gè)CQF隊(duì)列的長(zhǎng)度均為3.2 kB.網(wǎng)絡(luò)中有f1，f2，f3三條時(shí)間敏感流，流的信息如圖2b所示，假定三條數(shù)據(jù)流均從0時(shí)刻開(kāi)始傳輸.

若不采用任何調(diào)度策略，將三條流的傳輸用甘特圖表示，如圖3a所示.根據(jù)CQF的傳輸規(guī)則(1)和傳輸規(guī)則(2)，上游交換機(jī)在時(shí)隙sloti內(nèi)發(fā)送的幀會(huì)在相同的時(shí)隙內(nèi)，即時(shí)隙sloti內(nèi)被相鄰的下游交換機(jī)接收，下游的鄰居交換機(jī)在時(shí)隙sloti+1將該幀傳輸出去.數(shù)據(jù)流f3第0個(gè)周期的報(bào)文f3,0在host2的第0個(gè)時(shí)隙slot0送往SW1，SW1本應(yīng)該在時(shí)隙slot0將f3,0緩存到CQF隊(duì)列，并在第1個(gè)時(shí)隙將f3,0發(fā)往host3.但在SW1的時(shí)隙slot0內(nèi)，報(bào)文f1,0和f2,0已經(jīng)占用了1000 Bytes+1200 Bytes=2200 Bytes的隊(duì)列資源，SW1在時(shí)隙slot0上可用的隊(duì)列資源即3200-2200 Bytes=1000 Bytes，小于f3,0的幀長(zhǎng)1500 Bytes，SW1只能丟棄f3,0，所以f3,0無(wú)法在時(shí)隙1傳輸?shù)絟ost3.

圖2 簡(jiǎn)單網(wǎng)絡(luò)拓?fù)浼傲鲗?shí)例

雖然SW1在slot0內(nèi)的隊(duì)列資源有限，但在slot1內(nèi)隊(duì)列資源充足，因此，可以將f3,0的發(fā)送時(shí)間往后偏移一個(gè)時(shí)隙，從而提高資源利用率.如果f3,0能夠在slot0被SW1緩存，并在時(shí)隙slot1被SW1送往host3，根據(jù)CQF的最大延遲計(jì)算公式(1)，其最大的端到端延遲為(1+1)×150 μs=300 μs.那么將f3,0往后偏移一個(gè)時(shí)隙后，其最大的端到端延遲即300 μs+150 μs=450 μs，小于其允許的最大端到端延遲750 μs，因此將f3,0的發(fā)送時(shí)間往后偏移一個(gè)時(shí)隙是可行的.將三條流的傳輸用甘特圖表示，如圖3b所示.值得注意的是，f3,0偏移發(fā)送時(shí)間后的最大端到端延遲變成了450 μs，但f3其余報(bào)文的最大端到端延遲為300 μs，會(huì)在host3上造成抖動(dòng)，所以將f3所有報(bào)文的發(fā)送時(shí)間都往后偏移一個(gè)時(shí)隙.

綜上所述，合理地在源端偏移時(shí)間敏感流的發(fā)送時(shí)隙，可以提高網(wǎng)絡(luò)資源的利用率.本文根據(jù)以上發(fā)現(xiàn)，設(shè)計(jì)基于起始時(shí)隙分配的資源調(diào)度算法，從而最大化能夠成功調(diào)度的流的數(shù)量.

3 系統(tǒng)模型

本文將TSN網(wǎng)絡(luò)的拓?fù)涑橄鬄闊o(wú)向圖，用G表示網(wǎng)絡(luò)拓?fù)?，G={V,E}.V表示網(wǎng)絡(luò)節(jié)點(diǎn)的集合，V=SW∪H，其中SW表示交換機(jī)的集合，H表示終端的集合.E表示連接兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的邊的集合.交換機(jī)的每個(gè)輸出端口包含8個(gè)隊(duì)列，其中優(yōu)先級(jí)最高的兩個(gè)隊(duì)列用作CQF隊(duì)列，用于緩存時(shí)間敏感流，其余隊(duì)列緩存低優(yōu)先級(jí)的流量.本文只討論時(shí)間敏感流的調(diào)度，所以只對(duì)CQF隊(duì)列資源的調(diào)度進(jìn)行討論.圖4所示的Q7和Q6即交

圖3 TSN調(diào)度傳輸示意圖

終端是數(shù)據(jù)流的來(lái)源及目的地，它對(duì)每條流報(bào)文的發(fā)送時(shí)隙進(jìn)行配置，調(diào)度器Scheduler根據(jù)配置信息和全局時(shí)鐘調(diào)度緩存隊(duì)列Buffer中的報(bào)文，如圖4中的終端H0所示.終端也能夠?qū)?shù)據(jù)流進(jìn)行準(zhǔn)入控制，數(shù)據(jù)流被標(biāo)記為無(wú)法調(diào)度時(shí)，調(diào)度器不會(huì)調(diào)度屬于該數(shù)據(jù)流的幀.如果屬于同一條流的數(shù)據(jù)幀的偏移量不同，那么它們的端到端延遲也不同，從而產(chǎn)生抖動(dòng)，因此本文假定數(shù)據(jù)同一數(shù)據(jù)流的所有數(shù)據(jù)幀在源端的發(fā)送偏移量相同.交換機(jī)和終端均使用IEEE 1588 Precision Time Protocol(PTP)進(jìn)行全局的時(shí)間同步，時(shí)隙的長(zhǎng)度是相同的，并且是固定的.某個(gè)時(shí)隙內(nèi)，終端H0和交換機(jī)SW0內(nèi)的數(shù)據(jù)傳輸情況如圖4所示.

圖4 系統(tǒng)模型

時(shí)間敏感流是周期性的[6,12]，屬于同一條流的兩個(gè)數(shù)據(jù)幀之間的最小發(fā)送間隔即為該流的周期，每個(gè)周期發(fā)送的數(shù)據(jù)量是固定的.假定流的信息是已知的，流在每個(gè)周期只發(fā)送一個(gè)報(bào)文，并且在0時(shí)刻就開(kāi)始產(chǎn)生數(shù)據(jù).用包含源端、目的端、發(fā)送周期、每個(gè)周期的數(shù)據(jù)量大小、傳輸路徑和允許的最大端到端延遲的六元組來(lái)描述數(shù)據(jù)流:

fi={fi.src,fi.dest,fi.period,fi.size,fi.path,fi.deadline}.

(3)

fi∈F，用fi,j表示fi的第j個(gè)數(shù)據(jù)幀.由于屬于一個(gè)數(shù)據(jù)流的所有數(shù)據(jù)幀在源端的偏移是相同的，因此用fi.offset表示數(shù)據(jù)幀從源端發(fā)送時(shí)對(duì)應(yīng)的時(shí)隙.本文的調(diào)度粒度是交換機(jī)輸出端口上的CQF隊(duì)列，因此在描述傳輸路徑時(shí)需要攜帶傳輸端口.用fi傳輸經(jīng)過(guò)的交換機(jī)端口來(lái)表示路徑，那么路徑的表達(dá)式如下:

(4)

根據(jù)CQF的傳輸規(guī)則，對(duì)時(shí)隙長(zhǎng)度lenOfSlot進(jìn)行分析.由于以時(shí)隙為基本單位對(duì)數(shù)據(jù)進(jìn)行偏移，假定lenOfSlot能夠整除所有數(shù)據(jù)流的周期.將所有數(shù)據(jù)流的周期記作P，P={f0.period,f1.period,…,fn.period}，那么最大的時(shí)隙長(zhǎng)度為

MAX(lenOfSlot)=GCD(P) .

(5)

即lenOfSlot的最大值為數(shù)據(jù)流周期的最大公約數(shù).CQF規(guī)定，報(bào)文在相鄰兩個(gè)節(jié)點(diǎn)的發(fā)送時(shí)隙與接收時(shí)隙相同.那么，時(shí)隙的長(zhǎng)度至少需要保證隊(duì)列中的最后一個(gè)報(bào)文在相鄰節(jié)點(diǎn)之間的發(fā)送時(shí)隙與接收時(shí)隙相同，因此最小的時(shí)隙長(zhǎng)度為

(6)

4 問(wèn)題描述

時(shí)間敏感流是周期性流量，正常情況下會(huì)循環(huán)往復(fù)地運(yùn)行，直接計(jì)算出數(shù)據(jù)流在無(wú)限個(gè)時(shí)隙內(nèi)的傳輸計(jì)劃是不現(xiàn)實(shí)的.考慮到數(shù)據(jù)流的傳輸也是周期性的，因此在描述約束條件前，需要確定調(diào)度周期T.只要在T內(nèi)數(shù)據(jù)流的傳輸符合約束條件，那么在整個(gè)過(guò)程中流的傳輸都符合約束條件.一般情況下，數(shù)據(jù)流周期的值是任意的，因此，將調(diào)度周期T設(shè)置為所有流的周期的最小公倍數(shù)，即T=LCM(P).這樣，調(diào)度計(jì)劃每隔T循環(huán)執(zhí)行一次即可.在上述假設(shè)下，數(shù)據(jù)流的傳輸主要包括以下4個(gè)約束條件.

約束1:幀發(fā)送偏移

每個(gè)數(shù)據(jù)幀在源端的偏移量以時(shí)隙為單位.偏移量應(yīng)不超過(guò)每個(gè)周期內(nèi)時(shí)隙的數(shù)量，即

fi.offset

(7)

在源端偏移時(shí)隙，可以提高資源利用率，但是，當(dāng)偏移量過(guò)大時(shí)，下一個(gè)數(shù)據(jù)幀已產(chǎn)生，上一個(gè)數(shù)據(jù)幀卻還未發(fā)送，終端上需要緩存大量的數(shù)據(jù)幀，耗費(fèi)的存儲(chǔ)開(kāi)銷(xiāo)大.

約束2:端到端延遲約束

TSN必須要保證服務(wù)質(zhì)量.因此，在發(fā)送端偏移的時(shí)隙加上CQF模型最大的延遲不能超過(guò)該數(shù)據(jù)流允許的最大端到端延遲，即

fi.offset×lenOfSlot+(fi.hop+1)×lenOfSlot≤fi.deadline .

(8)

其中，fi.hop為數(shù)據(jù)流從源端至發(fā)送端的總跳數(shù).

約束3:接收窗口約束

根據(jù)描述的CQF傳輸規(guī)則(1)，上游交換機(jī)發(fā)送報(bào)文的時(shí)隙應(yīng)該和相鄰下游交換機(jī)接收?qǐng)?bào)文的時(shí)隙相同.滿足CQF傳輸規(guī)則的最小的時(shí)隙可以保證該約束.

約束4:隊(duì)列資源約束

交換機(jī)輸出端口的緩存隊(duì)列的資源是有限的.換言之，某段鏈路在一個(gè)時(shí)隙能夠傳輸?shù)臅r(shí)間敏感型數(shù)據(jù)幀的數(shù)量是有限的，在這個(gè)時(shí)隙內(nèi)傳輸?shù)臄?shù)據(jù)的總長(zhǎng)度不應(yīng)該超過(guò)緩存隊(duì)列的長(zhǎng)度.若流fi的第j個(gè)報(bào)文在時(shí)隙t經(jīng)過(guò)SWk的端口l，則O(i,j,k,l,t)=1，否則為0.隊(duì)列資源約束的形式化描述如下:

(9)

t與i，j，k，l之間存在如下關(guān)系:

在滿足上述約束條件的情況下，算法要使能夠調(diào)度的流的數(shù)量最大化.因此，鏈路時(shí)隙分配問(wèn)題實(shí)際上是一個(gè)優(yōu)化問(wèn)題.

5 算法描述

根據(jù)資源調(diào)度模型和約束條件，提出了基于起始時(shí)隙分配的資源調(diào)度算法，如算法1所示.

算法1 SSA調(diào)度算法

輸入:F,G

輸出:F.OFFSET

BEGIN

1T=compute_LCM(P);

2F=flow_sort(F);

3 FOREACHfiINFDO:

4 FOREACH offset IN[fi.period-1,0] DO:

5 latency=count_e2e_latency(fi,offset,slot_cycle);

6 IF latency

7fi.flag=sw_queue_constraint(fi,G,T);

8 IFfi.sched_flag==SUCCESS THEN:

9 update_global_resource(fi,G,T);

10 BREAK;

11 ELSE

12 CONTINUE;

13 END IF

14 ELSE

15fi.sched_flag=FAIL;

16 CONTINUE;

17 END IF

18 END FOR

19 END FOR

END

首先，計(jì)算調(diào)度周期(第1行)，調(diào)度周期T為所有時(shí)間敏感流的周期的最小公倍數(shù)，調(diào)度方案在這個(gè)周期內(nèi)循環(huán)執(zhí)行.接著，按照設(shè)定的參數(shù)(路徑長(zhǎng)度、報(bào)文大小、允許的最大端到端延遲、周期大小)進(jìn)行排序(第2行)，位置靠前的數(shù)據(jù)流優(yōu)先分配資源.然后，按照既定的順序?yàn)閿?shù)據(jù)流分配資源(第3～19行).4個(gè)約束條件中，幀發(fā)送偏移約束對(duì)應(yīng)第4行，端到端延遲約束對(duì)應(yīng)第5行和第6行，隊(duì)列資源約束則對(duì)應(yīng)第7行.為了讓CQF模型能夠正常傳輸報(bào)文，用戶設(shè)定的時(shí)隙一定大于允許的最小時(shí)隙長(zhǎng)度，接收窗口約束得到滿足.

算法借鑒了貪心算法的思想.對(duì)流進(jìn)行排序時(shí)(第2行)，優(yōu)先映射占用資源較少的數(shù)據(jù)流，根據(jù)這一思想提出了4種貪心策略，即按照路徑長(zhǎng)度升序、報(bào)文大小升序、允許的最大端到端延遲升序、周期大小降序的方式調(diào)整流的順序.以報(bào)文大小升序?yàn)槔?，排序后，每次映射時(shí)選擇的總是當(dāng)前尺寸最小的報(bào)文.在源端對(duì)時(shí)隙進(jìn)行偏移時(shí)，采用偏移量遞減的貪心策略，從最大的偏移量對(duì)數(shù)據(jù)流進(jìn)行映射(第4行)，為后映射的流保留位置相對(duì)靠前的時(shí)隙.

6 實(shí)驗(yàn)評(píng)估

6.1 實(shí)驗(yàn)場(chǎng)景

目前應(yīng)用TSN的工業(yè)控制網(wǎng)絡(luò)中，大多是環(huán)形拓?fù)洌绛h(huán)形以太列車(chē)網(wǎng)絡(luò)(Ethernet train bone，ETB).因此，本文模擬搭建了一個(gè)環(huán)形網(wǎng)絡(luò)，如圖5所示.

圖5 環(huán)形網(wǎng)絡(luò)拓?fù)?/p>

環(huán)形網(wǎng)絡(luò)中包括7個(gè)支持CQF轉(zhuǎn)發(fā)模型的TSN交換機(jī)，每個(gè)交換機(jī)連接的終端數(shù)量從集合{1,2,3}中隨機(jī)選擇，時(shí)隙長(zhǎng)度設(shè)置為125 μs.網(wǎng)絡(luò)中時(shí)間敏感流數(shù)量從集合{100,150,200,250}中選擇.由于目前沒(méi)有開(kāi)源的支持TSN測(cè)試的數(shù)據(jù)集，文中的數(shù)據(jù)流為隨機(jī)產(chǎn)生.每條數(shù)據(jù)流中每個(gè)周期產(chǎn)生的報(bào)文數(shù)量為1.數(shù)據(jù)流的周期長(zhǎng)度為時(shí)隙的整數(shù)倍，周期范圍為2～9個(gè)時(shí)隙，報(bào)文大小在64～1 500 Bytes之間，允許的最大端到端延遲至少要大于CQF的最大端到端延遲.在上述場(chǎng)景中運(yùn)行SSA，為時(shí)間敏感流計(jì)算出調(diào)度計(jì)劃，并根據(jù)調(diào)度成功率對(duì)算法的質(zhì)量進(jìn)行評(píng)估.

6.2 實(shí)驗(yàn)對(duì)比與分析

不在發(fā)送端控制幀的發(fā)送時(shí)隙，先映射的流先分配隊(duì)列資源，隊(duì)列資源不足時(shí)直接將流標(biāo)記為不可調(diào)度，稱這種調(diào)度方式為直接調(diào)度(direct scheduling，DS).接下來(lái)從不同的維度展示SSA的調(diào)度效果，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析.

將交換機(jī)CQF隊(duì)列的長(zhǎng)度均設(shè)置為15 kB，在上述實(shí)驗(yàn)場(chǎng)景中分別生成100,150,200,250條數(shù)據(jù)流，按照不同的參數(shù)對(duì)流進(jìn)行排序(周期降序、數(shù)據(jù)幀大小升序、路徑長(zhǎng)度升序、允許的最大端到端延遲升序)，使用SSA計(jì)算調(diào)度方案，統(tǒng)計(jì)調(diào)度成功率.同時(shí)，計(jì)算DS成功率，與SSA進(jìn)行對(duì)比，如圖6所示.不論使用何種排序方式，SSA的調(diào)度成功率均高于DS.計(jì)算得到，SSA能夠使DS的調(diào)度成功率平均提高41.84%.

圖6 SSA調(diào)度與DS調(diào)度的對(duì)比

在偏移源端的發(fā)送時(shí)隙時(shí)，采用了偏移量遞減的貪心策略.為了驗(yàn)證這種方式的有效性，本文設(shè)計(jì)了偏移量遞增的分配方式.在上述實(shí)驗(yàn)場(chǎng)景中生成了200條數(shù)據(jù)流，CQF隊(duì)列長(zhǎng)度同樣為15 kB，分別運(yùn)行兩種算法，結(jié)果如圖7所示.偏移量遞減比偏移量遞增的調(diào)度成功率平均高3.89%，偏移量遞減的調(diào)度方式比不調(diào)整偏移量的調(diào)度方式的調(diào)度成功率平均高18.32%.與按照偏移量遞增的方式相比，偏移量遞減的方式能夠?yàn)橹芷谳^小的報(bào)文留下調(diào)度周期中相對(duì)靠前的時(shí)隙，因此調(diào)度成功率比偏移量遞增的方式高.在周期大小降序的流映射方式中，與偏移量遞增相比，偏移量遞減的方式能夠?qū)⒄{(diào)度成功率提高9.65%.按周期大小排序，位置靠后的報(bào)文的周期小，可選擇的偏移量的范圍也小，周期大的報(bào)文占用了靠后的時(shí)隙，留下了相對(duì)靠前的時(shí)隙資源，因

圖7 offset升序與降序的對(duì)比

此調(diào)度成功率得到明顯提高.

為了研究隊(duì)列資源對(duì)調(diào)度成功率的影響，本文調(diào)整隊(duì)列長(zhǎng)度，將CQF隊(duì)列長(zhǎng)度分別設(shè)置為8,10,12,14 kB，生成200條數(shù)據(jù)流，統(tǒng)計(jì)調(diào)度成功的流的數(shù)量，如圖8所示.實(shí)驗(yàn)表明，隨著隊(duì)列資源的增多，調(diào)度成功率也隨之提高.CQF隊(duì)列長(zhǎng)度相同時(shí)，4種排序方式之間進(jìn)行對(duì)比，按照?qǐng)?bào)文大小排序的調(diào)度成功率遠(yuǎn)大于其他4種方式，即報(bào)文大小對(duì)調(diào)度成功率的影響最大.

圖8 隊(duì)列長(zhǎng)度對(duì)成功調(diào)度的流的數(shù)量影響

將隊(duì)列長(zhǎng)度分別設(shè)置為2,4,6,8,10,12,14,16,18,20 kB，采用包大小升序的排序方式、偏移量降序的調(diào)度方式，計(jì)算200條時(shí)間敏感流的成功調(diào)度的數(shù)量，實(shí)驗(yàn)結(jié)果如圖9所示.本文設(shè)定時(shí)隙長(zhǎng)度為125 μs，在千兆以太網(wǎng)中，一個(gè)時(shí)隙可以傳輸?shù)淖畲蟮臅r(shí)間敏感流大小為15.625 kB.在時(shí)隙長(zhǎng)度不變的情況下，當(dāng)隊(duì)列長(zhǎng)度小于15.625 kB時(shí)，增長(zhǎng)隊(duì)列長(zhǎng)度，相當(dāng)于增加分配給時(shí)間敏感流的帶寬，如圖9中的理論帶寬所示，那么能夠成功調(diào)度的流的數(shù)量也隨之增加.當(dāng)CQF隊(duì)列的長(zhǎng)度超過(guò)15.625 kB時(shí)，由于鏈路速率的限制，即使再增加隊(duì)列長(zhǎng)度，調(diào)度成功率也不會(huì)繼續(xù)增長(zhǎng).

圖9 帶寬資源對(duì)成功調(diào)度的流的數(shù)量影響

7 結(jié) 語(yǔ)

本文研究發(fā)現(xiàn)，在基于CQF模型的資源調(diào)度中，需要從時(shí)間維度上對(duì)資源進(jìn)行分配.如果在端系統(tǒng)上直接發(fā)送數(shù)據(jù)流，某些時(shí)隙內(nèi)的流量會(huì)超過(guò)隊(duì)列長(zhǎng)度，而在另一些時(shí)隙中存在大量的空閑隊(duì)列資源.通過(guò)延遲端系統(tǒng)的發(fā)送時(shí)間，可以利用這些空閑資源，成功調(diào)度更多的流量.為此，本文將基于CQF模型的資源調(diào)度問(wèn)題抽象為多約束條件下的資源規(guī)劃最大化問(wèn)題，將約束條件歸納為：1)幀發(fā)送偏移約束；2)接收窗口約束；3)端到端延遲約束；4)隊(duì)列資源約束.

本文借鑒貪心算法思想，提出了基于起始時(shí)隙分配的資源調(diào)度算法(SSA)，通過(guò)對(duì)端系統(tǒng)的時(shí)隙進(jìn)行調(diào)度，提高隊(duì)列資源利用率，以最大化成功調(diào)度的流的數(shù)量.本文分別從周期、報(bào)文大小、路徑長(zhǎng)度、允許的最大端到端延遲4個(gè)角度出發(fā)，提出了4種貪心策略，使占用資源少的報(bào)文能夠被優(yōu)先調(diào)度.

本文構(gòu)建了工業(yè)控制網(wǎng)絡(luò)中典型的環(huán)形網(wǎng)絡(luò)拓?fù)鋵?duì)算法的有效性進(jìn)行評(píng)估，通過(guò)與不控制發(fā)送時(shí)隙的分配策略相比，本文提出的SSA算法平均可以提高41.84%.通過(guò)對(duì)4種策略的對(duì)比結(jié)果發(fā)現(xiàn)，報(bào)文大小對(duì)資源調(diào)度的影響最大.