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

(國防科技大學(xué) 計算機(jī)學(xué)院， 湖南 長沙 410073)

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

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

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

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

1 相關(guān)研究

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

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

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

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

2 研究動機(jī)

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

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

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

maxDelay=(h+1)d,

(1)

minDelay=(h-1)d.

(2)

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

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

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

圖2 簡單網(wǎng)絡(luò)拓?fù)浼傲鲗嵗?/p>

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

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

3 系統(tǒng)模型

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

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

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

圖4 系統(tǒng)模型

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

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

(3)

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

(4)

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

MAX(lenOfSlot)=GCD(P) .

(5)

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

(6)

4 問題描述

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

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

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

fi.offset

(7)

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

約束2:端到端延遲約束

TSN必須要保證服務(wù)質(zhì)量.因此，在發(fā)送端偏移的時隙加上CQF模型最大的延遲不能超過該數(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ā)送報文的時隙應(yīng)該和相鄰下游交換機(jī)接收報文的時隙相同.滿足CQF傳輸規(guī)則的最小的時隙可以保證該約束.

約束4:隊列資源約束

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

(9)

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

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

5 算法描述

根據(jù)資源調(diào)度模型和約束條件，提出了基于起始時隙分配的資源調(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

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

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

6 實驗評估

6.1 實驗場景

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

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

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

6.2 實驗對比與分析

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

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

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

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

圖7 offset升序與降序的對比

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

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

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

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

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

7 結(jié) 語

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

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

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