王新蕾,周 敏,張 濤

(1.南京信息工程大學(xué) 電子與信息工程學(xué)院,南京210044;2.無(wú)錫學(xué)院 江蘇省集成電路可靠性技術(shù)及檢測(cè)系統(tǒng)工程研究中心,無(wú)錫 214105)

0 引 言

隨著科學(xué)技術(shù)的不斷進(jìn)步,5G、工業(yè)物聯(lián)網(wǎng)、汽車(chē)自動(dòng)駕駛、新一代音視頻傳輸、大數(shù)據(jù)等新技術(shù)應(yīng)運(yùn)而生,這些技術(shù)需要可靠的數(shù)據(jù)傳輸,對(duì)傳統(tǒng)網(wǎng)絡(luò)傳輸技術(shù)帶來(lái)了很大沖擊[1]。在傳統(tǒng)以太網(wǎng)中,因?yàn)榻K端設(shè)備之間共享網(wǎng)絡(luò)帶寬,而這些設(shè)備不停地進(jìn)行流量傳輸,難免會(huì)造成某個(gè)設(shè)備因流量問(wèn)題發(fā)生網(wǎng)絡(luò)擁堵,從而不能保證確定和可靠的傳輸[2]。

2005年,IEEE 802.1工作組成立了IEEE 802.1 AVB工作組,用來(lái)保證音/視頻橋(Audio Video Bridging,AVB)流的確定性傳輸。隨后,汽車(chē)以及傳統(tǒng)工業(yè)領(lǐng)域也開(kāi)始關(guān)注AVB。2012年,AVB工作組正式改名為時(shí)間敏感網(wǎng)絡(luò)(Time-sensitive Networking,TSN)工作組,正式提出了時(shí)間敏感網(wǎng)絡(luò)這種確定性以太網(wǎng),研究領(lǐng)域也從AVB流的傳輸擴(kuò)展到工業(yè)控制網(wǎng)絡(luò)。在此期間,時(shí)鐘同步、流量調(diào)度、可靠性和資源配置等標(biāo)準(zhǔn)協(xié)議逐漸完善。在這之后,多家企業(yè)與組織也加入了TSN技術(shù)的研究,并將目標(biāo)轉(zhuǎn)向工業(yè)領(lǐng)域,以滿足其低時(shí)延、低抖動(dòng)、不擁塞和不丟包的傳輸要求[3-4]。經(jīng)過(guò)多年的發(fā)展,TSN已經(jīng)成為全球工業(yè)界研究和拓展的主流。這種新型網(wǎng)絡(luò)傳輸技術(shù)能夠在一個(gè)網(wǎng)絡(luò)里同時(shí)傳輸周期性和非周期性的流量數(shù)據(jù),比起傳統(tǒng)以太網(wǎng),TSN具有確定性和可靠性傳輸?shù)膬?yōu)勢(shì)。在TSN工作組不斷完善和擴(kuò)展相關(guān)協(xié)議標(biāo)準(zhǔn)的過(guò)程中,TSN技術(shù)已經(jīng)受到全世界的廣泛關(guān)注[5],目前在音視頻、工業(yè)控制和汽車(chē)駕駛[6]等領(lǐng)域發(fā)揮了重要作用。

IEEE工作組在TSN的協(xié)議標(biāo)準(zhǔn)中規(guī)定了時(shí)間同步、流量調(diào)度、可靠性、資源管理4種關(guān)鍵技術(shù)。時(shí)鐘同步機(jī)制是TSN的基礎(chǔ),它使所有網(wǎng)絡(luò)設(shè)備的時(shí)鐘保持一致,從而確保網(wǎng)絡(luò)的實(shí)時(shí)性[7]。流量調(diào)度是TSN的重要機(jī)制,數(shù)據(jù)在時(shí)鐘同步機(jī)制的基礎(chǔ)上,對(duì)流量進(jìn)行整形和調(diào)度,使時(shí)間觸發(fā)(Time-triggered,TT)流數(shù)據(jù)優(yōu)先完成確定性傳輸[8]。TSN不僅要保證時(shí)間敏感數(shù)據(jù)的確定性傳輸,還要確保數(shù)據(jù)傳輸過(guò)程是安全可靠的,防止出現(xiàn)網(wǎng)絡(luò)丟包等情況。TSN資源管理機(jī)制對(duì)網(wǎng)絡(luò)資源進(jìn)行合理分配和管理。多家研究機(jī)構(gòu)和大學(xué)都在研究完善TSN技術(shù),IEEE工作組指定的802.1Q系列標(biāo)準(zhǔn)協(xié)議為后續(xù)的TSN研究和應(yīng)用提供了框架?，F(xiàn)在TSN的研究重心放在了無(wú)線和5G網(wǎng)絡(luò)上,對(duì)流量調(diào)度的要求進(jìn)一步提高,成為T(mén)SN研究的重中之重。

TSN工作組提出了5種基本流量調(diào)度機(jī)制,一直都是應(yīng)用領(lǐng)域的標(biāo)準(zhǔn)。眾多學(xué)者和專家在這些基本框架的基礎(chǔ)上改進(jìn)算法,以實(shí)現(xiàn)不同流量的調(diào)度。但對(duì)于不同的流量,在調(diào)度機(jī)制或算法的選擇上仍需要框架性的分類和研究。本文重點(diǎn)探討了目前流量調(diào)度算法的研究現(xiàn)狀以及存在的問(wèn)題,對(duì)調(diào)度機(jī)制和算法進(jìn)行了分析,并對(duì)未來(lái)流量調(diào)度算法的發(fā)展方向給出建議。

1 TSN流量調(diào)度機(jī)制

流量調(diào)度機(jī)制是TSN的關(guān)鍵技術(shù),所有的調(diào)度算法和路由方案都是在標(biāo)準(zhǔn)機(jī)制框架下完成的。TSN流量調(diào)度有以下5種標(biāo)準(zhǔn)機(jī)制:基于時(shí)間的整形機(jī)制、基于信用值的整形機(jī)制、循環(huán)隊(duì)列轉(zhuǎn)發(fā)機(jī)制、幀搶占機(jī)制以及異步流量整形機(jī)制。

1.1 基于時(shí)間的整形機(jī)制

為了保障TT流傳輸時(shí)的端到端的低時(shí)延,IEEE 802.1Qbv[9]標(biāo)準(zhǔn)提出了時(shí)間感知整形器(Time-aware Shaper,TAS),它使用時(shí)分多址[10]的思想,將流量分成8個(gè)優(yōu)先級(jí)隊(duì)列。TAS將傳輸時(shí)間劃分為多個(gè)重復(fù)的周期,在每個(gè)周期里再劃分為兩個(gè)時(shí)間槽,時(shí)間槽1調(diào)度優(yōu)先級(jí)7(TT流)的流量,時(shí)間槽2則調(diào)度其他優(yōu)先級(jí)(非TT流)的流量。然而,這種周期性的調(diào)度會(huì)帶來(lái)問(wèn)題,如果時(shí)間槽2的流量在當(dāng)前周期沒(méi)有傳輸完成,就會(huì)占用下一個(gè)周期的時(shí)間槽1的傳輸。為此,TAS規(guī)定在時(shí)間槽2后面加入保護(hù)帶,在保護(hù)帶里不能傳輸新的流量,只能完成當(dāng)前流量的傳輸。圖1是帶保護(hù)帶的TAS工作機(jī)制。

圖1 帶保護(hù)帶的TAS工作機(jī)制

在TAS進(jìn)行流量調(diào)度時(shí),會(huì)利用門(mén)控調(diào)度表(Gate Control List,GCL)來(lái)控制幀的出隊(duì)列操作。如圖2所示,GCL控制門(mén)的開(kāi)與關(guān),1表示門(mén)打開(kāi),0表示門(mén)關(guān)閉。在時(shí)鐘同步后,門(mén)周期性地打開(kāi),確定流的有序傳輸,不同的流隊(duì)列會(huì)選擇相應(yīng)的調(diào)度算法進(jìn)行調(diào)度[11]。

圖2 門(mén)控調(diào)度機(jī)制

1.2 基于信用值的整形機(jī)制

為了保證TSN中AVB流的服務(wù)質(zhì)量不被TT流的調(diào)度影響服務(wù)質(zhì)量,IEEE 802.1Qav[12]協(xié)議定義了基于信用值的整形機(jī)制(Credit Based Shaper,CBS)來(lái)對(duì)AVB流進(jìn)行整形和調(diào)度。

圖3為CBS算法機(jī)制的示意圖,CBS為每個(gè)隊(duì)列設(shè)置一個(gè)信用值,只有隊(duì)列信號(hào)值大于或等于0時(shí)才能傳輸數(shù)據(jù)。當(dāng)AVB流等待傳輸時(shí),信用值隨著時(shí)間線性增長(zhǎng),圖中斜率idle slope直到達(dá)到最大信用值后保持不變;當(dāng)AVB流傳輸時(shí),信用值以send slope為斜率線性下降,直至信用值小于0或其他隊(duì)列正在傳輸數(shù)據(jù)時(shí)停止傳輸并再次以idle slope斜率線性增加,往復(fù)進(jìn)行;如果所有隊(duì)列都無(wú)數(shù)據(jù)等待傳輸,則將信用值置0。

圖3 CBS調(diào)度機(jī)制

1.3 循環(huán)隊(duì)列轉(zhuǎn)發(fā)機(jī)制

為了解決網(wǎng)絡(luò)擁堵和有界時(shí)延的問(wèn)題,IEEE 802.1Qch[13]提出循環(huán)隊(duì)列轉(zhuǎn)發(fā)(Cyclic Queuing and Forwarding,CQF)機(jī)制。CQF機(jī)制為交換結(jié)構(gòu)設(shè)置奇偶循環(huán)周期,即以每一跳的時(shí)延計(jì)算總時(shí)延,規(guī)避網(wǎng)絡(luò)拓?fù)鋵?duì)傳輸時(shí)延的影響。

圖4為循環(huán)隊(duì)列轉(zhuǎn)發(fā)機(jī)制示意圖,CQF在每個(gè)循環(huán)周期內(nèi)設(shè)置兩個(gè)隊(duì)列,即隊(duì)列A和隊(duì)列B。在奇數(shù)循環(huán)周期內(nèi),隊(duì)列A只接收幀,隊(duì)列B則只傳輸偶數(shù)周期接收的幀;在偶數(shù)循環(huán)周期內(nèi),隊(duì)列A只傳輸奇數(shù)周期的幀而不接收幀,隊(duì)列B則只接收該偶數(shù)周期的幀。如此循環(huán)交替接收傳輸,所有TT流都能實(shí)現(xiàn)有序傳輸。

圖4 循環(huán)隊(duì)列轉(zhuǎn)發(fā)機(jī)制

1.4 幀搶占機(jī)制

在調(diào)度過(guò)程中,可搶占幀的持續(xù)傳輸會(huì)阻礙快速幀的及時(shí)傳輸,從而影響快速幀的傳輸時(shí)延,而且1.1節(jié)中提到的保護(hù)帶也會(huì)造成帶寬浪費(fèi)[7]。為此,IEEE 802.3br[14]標(biāo)準(zhǔn)定義了快速M(fèi)AC和可搶占MAC兩個(gè)子層,對(duì)幀搶占(Frame Preemption,FP)的切片和還原進(jìn)行解釋說(shuō)明。IEEE 802.1Qbu[15]標(biāo)準(zhǔn)則規(guī)范了幀傳輸過(guò)程中的搶占接口和模塊。

幀搶占要滿足以下兩個(gè)條件:只能在全雙工點(diǎn)對(duì)點(diǎn)鏈路中使用;每個(gè)被切片的可搶占切片需大于等于64 B[16]。如圖5所示,幀搶占的過(guò)程為:首先判斷可搶占幀是否滿足切片條件,若可以切片,則當(dāng)可搶占幀傳輸完64 B后開(kāi)始切片并插入循環(huán)冗余校驗(yàn)碼;然后開(kāi)始傳輸快速幀,之后在剩余可搶占幀切片尾部加入校驗(yàn)和,開(kāi)始補(bǔ)全余下低速幀的傳輸。

圖5 幀搶占機(jī)制

1.5 異步流量整形機(jī)制

CQF和TAS機(jī)制雖然能為T(mén)T流提供低時(shí)延的傳輸,但它們都依賴高精度的時(shí)鐘同步,同時(shí)在多個(gè)周期內(nèi)強(qiáng)制傳輸數(shù)據(jù),這也會(huì)造成帶寬上的浪費(fèi)。IEEE 802.1Qcr[17]提出了一種異步流量整形器(Asynchronous Traffic Shaper,ATS),它是基于事件緊急性的調(diào)度器(Urgency-based Scheduler,UBS)[18]。UBS劃分隊(duì)列為一個(gè)流量整形隊(duì)列和一個(gè)共享隊(duì)列,流量整形隊(duì)列為流分配固定的優(yōu)先級(jí),而共享隊(duì)列把相同優(yōu)先級(jí)的流放在同一隊(duì)列,先到的流先調(diào)度。

ATS調(diào)度機(jī)制如圖6所示,它對(duì)可調(diào)度(Scheduled Traffic,ST)流和BE流進(jìn)行調(diào)度,流量在經(jīng)過(guò)ATS整形之后才能進(jìn)入相應(yīng)隊(duì)列。ST流在ATS中經(jīng)過(guò)判斷事件緊急性,一部分進(jìn)入緊急隊(duì)列,分組調(diào)度至速率控制器,之后采取不同速率到達(dá)輸出端口;另一部分則與BE隊(duì)列一起調(diào)度。

圖6 異步整形機(jī)制

1.6 流量調(diào)度機(jī)制小結(jié)

TSN中的流量調(diào)度可分為兩種,即同步調(diào)度和異步調(diào)度。TAS和CQF屬于同步流量調(diào)度,而CBS、FP和ATS則屬于異步調(diào)度流量調(diào)度。同步流量調(diào)度雖然有時(shí)延抖動(dòng)較低,但是很難適配應(yīng)用環(huán)境;異步流量調(diào)度則有著良好的帶寬利用率,但抖動(dòng)比同步流量調(diào)度大。表1從時(shí)間和優(yōu)缺點(diǎn)方面對(duì)上述5種調(diào)度機(jī)制進(jìn)行了對(duì)比。

表1 流量調(diào)度機(jī)制對(duì)比

2 TSN調(diào)度算法研究現(xiàn)狀

TSN將流量劃分為T(mén)T流、AVB流和盡力而為(Best-effort,BE)流[19]。TT流需要滿足低時(shí)延和低抖動(dòng)的要求以實(shí)現(xiàn)確定性傳輸。AVB流由事件觸發(fā),只需要確保端口之間的有限時(shí)延。BE流就像其名字一般,對(duì)時(shí)延沒(méi)有要求,它更關(guān)心吞吐量。

調(diào)度算法是在5種調(diào)度機(jī)制上針對(duì)調(diào)度目標(biāo)、約束條件、路由選擇等的優(yōu)化方案,其中TAS、GCL、CBS和幀搶占機(jī)制為當(dāng)前TT、AVB和BE流的調(diào)度提供基本框架,現(xiàn)有大多數(shù)調(diào)度算法都在這個(gè)框架內(nèi)進(jìn)行改進(jìn)和優(yōu)化。本文主要對(duì)TT流、AVB流以及BE流調(diào)度算法的研究現(xiàn)狀進(jìn)行分析和探討。

2.1 TT流調(diào)度算法研究現(xiàn)狀

傳輸時(shí)延一直是實(shí)時(shí)通信一大難題。為了最小化端到端時(shí)延,Schweissguth等人[20]提出了一種新型整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)算法,解決了TSN在聯(lián)合路由調(diào)度時(shí)TT流無(wú)法選擇最短路徑路由而導(dǎo)致時(shí)延變大的問(wèn)題,提供了比TT流單獨(dú)調(diào)度的固定負(fù)載平衡路由更低的通信時(shí)延。Nayak等人[21]在此基礎(chǔ)上做了改進(jìn),引入了最大調(diào)度傳輸負(fù)荷和跳數(shù)因素,同時(shí)最小化了傳輸負(fù)荷和所有流在路由上的累積跳數(shù),大大減少了時(shí)延。而Schweissguth等人[22]在之后的研究里增加了對(duì)多播流的支持,并提出了一種資源約束優(yōu)化方法。在優(yōu)化流時(shí)延方面,該方法將ILP模型大小減少了49%以上,將求解時(shí)間減少了47.6%。Pang等人[23]則結(jié)合軟件定義網(wǎng)絡(luò)建立了一個(gè)新型整數(shù)線性規(guī)劃調(diào)度模型,同時(shí)考慮靜態(tài)和動(dòng)態(tài)調(diào)度。靜態(tài)調(diào)度算法具有更好的TT流可調(diào)度性,動(dòng)態(tài)調(diào)度算法消耗的時(shí)間更少,可調(diào)度性略有下降,而這兩種調(diào)度下都實(shí)現(xiàn)了零幀丟失。鐘龍[16]則以單調(diào)速率調(diào)度(Rate Monotonic Scheduling,RMS)算法為基礎(chǔ),提出了一種基于多周期應(yīng)用的調(diào)度算法,將分組調(diào)度問(wèn)題類比于車(chē)間作業(yè),對(duì)周期、端到端時(shí)延、流調(diào)度、RMS和門(mén)事件進(jìn)行約束,有效降低了端到端時(shí)延。同時(shí)他還提出了一種合并門(mén)控機(jī)制,有效降低了傳輸損耗和門(mén)事件數(shù)量。

一些學(xué)者更加關(guān)注路由與流量整體調(diào)度問(wèn)題。Pahlevan等人[24]增加了路由的節(jié)點(diǎn)數(shù)并提供更多的路由選擇,提出了一種基于遺傳算法(Genetic Algorithm,GA)的聯(lián)合路由調(diào)度方法。該方法減少了TT流傳輸?shù)目倳r(shí)長(zhǎng),還考慮了多播模式對(duì)TT流造成的帶寬影響,這使得TT流的可調(diào)度性、傳輸效率以及帶寬利用率有了顯著提高。Huang等人[25]為了減少流量調(diào)度的計(jì)算時(shí)間,提出了一種新型調(diào)度感知路由算法。算法考慮了TT流的周期,確定了每個(gè)TT流的路徑,減少了流量調(diào)度階段路徑?jīng)_突的發(fā)生,將流量調(diào)度過(guò)程中的計(jì)算時(shí)間縮短了30%,提高了TT流的可調(diào)度性。裴金川等人[26]采用時(shí)空聯(lián)合規(guī)劃的思想,對(duì)時(shí)間敏感網(wǎng)絡(luò)中時(shí)間敏感流量的調(diào)度與路由分離問(wèn)題,提出了一種聯(lián)合無(wú)沖突路由規(guī)劃的調(diào)度方法。時(shí)間上基于時(shí)分多址思想建立TT流的調(diào)度約束模型,空間上結(jié)合TT流調(diào)度特性靈活分配流量路由,在此基礎(chǔ)上建立TAS和聯(lián)合無(wú)沖突路由的調(diào)度約束模型,保障TT流調(diào)度的有界低時(shí)延需求。

可滿足性模理論(Satisfiability Modulo Theories,SMT)求解器經(jīng)常用于解決約束條件問(wèn)題。為了解決TT流調(diào)度帶來(lái)的品質(zhì)下降的問(wèn)題,Craciunas等人[27]提出一種基于SMT的回溯算法,將幀偏移量和隊(duì)列分配定義為整數(shù)變量,以滿足約束條件為目標(biāo),引入了一種增量回溯算法。算法通過(guò)向SMT公式添加流變量和約束來(lái)探索有效解,從而一次調(diào)度一個(gè)流。如果找到了解決方案,則繼續(xù)下一個(gè)流的調(diào)度。重復(fù)步驟,直到所有流都完成調(diào)度或者求解器找不到有效解。在后一種情況下,當(dāng)前流的約束無(wú)法滿足上一個(gè)SMT公式,則刪除最后一個(gè)流并將其與相關(guān)的不可行步驟一起重新引入來(lái)回溯SM求解器。Li等人[28]基于SMT,提出了一種面向工業(yè)場(chǎng)景的TSN調(diào)度算法。在每個(gè)端口使用SMT算法計(jì)算滿足約束條件的時(shí)間窗口分配,使用鏈路中所有TT流的最大公約數(shù)取代原有的鏈路超周期,成為GCL的更新周期,可以有效減少GCL中的時(shí)隙數(shù)量,使GCL的配置更簡(jiǎn)單、更高效,還可以更快地計(jì)算出調(diào)度結(jié)果,保證TT流的低延遲,有效地減少運(yùn)行時(shí)間。

為了實(shí)現(xiàn)多種調(diào)度目標(biāo),一些學(xué)者采用復(fù)合調(diào)度方法求解問(wèn)題,或在一種調(diào)度方法中使用其他方法求解問(wèn)題。Falk等人[29]著眼于調(diào)度的等待時(shí)長(zhǎng)問(wèn)題,將初始的傳輸路徑規(guī)劃問(wèn)題轉(zhuǎn)化成沖突圖中的極大獨(dú)立點(diǎn)集問(wèn)題。在沖突圖中,把流的數(shù)據(jù)何時(shí)沿著網(wǎng)絡(luò)中的哪條路徑傳輸定義為流的極大配置(configuration vertices,cvertex),每個(gè)cvertex只能有一個(gè)配置,而當(dāng)兩個(gè)cvertex的邊界采用了各自的配置就會(huì)產(chǎn)生沖突。當(dāng)獨(dú)立點(diǎn)集包含所有流時(shí)則為極大獨(dú)立點(diǎn)集。Falk等人使用ILP與極大獨(dú)立點(diǎn)集的復(fù)合方法來(lái)遍歷每條流的cvertex,這使得沖突圖不斷擴(kuò)大并在沖突圖中探索極大獨(dú)立點(diǎn)集,直到獨(dú)立點(diǎn)集包含所有的流,返回對(duì)應(yīng)的路由和調(diào)度方案。曹志鵬等人[30]則提出一種基于K-最短路徑(K-Short Path,KSP)的負(fù)載均衡路由算法和改進(jìn)遺傳算法的流量調(diào)度方法:負(fù)載均衡路由算法減小了網(wǎng)絡(luò)擁堵發(fā)生的概率;改進(jìn)傳統(tǒng)遺傳算法算子的交叉和遺傳概率,提升了迭代速度,從而大幅縮短時(shí)延,減少完成時(shí)間。臧宇航等人[31]針對(duì)域內(nèi)網(wǎng)絡(luò)的調(diào)度改進(jìn)了貪婪隨機(jī)自適應(yīng)搜索(Greedy Randomized Adaptive Search Rrocedure,GRASP)算法。該算法以調(diào)度成功率為目標(biāo),能夠減少鏈路堵塞,最小化時(shí)延以及提高解的準(zhǔn)確率。同時(shí),為了聯(lián)合路由調(diào)度,還提出一種雙向A*均衡路由算法,分別從起點(diǎn)和終點(diǎn)兩個(gè)方向在路由間找到最短路徑,提升搜索效率,引入風(fēng)險(xiǎn)均衡思想,優(yōu)化路由選擇,提高調(diào)度成功率。

上述文獻(xiàn)都提出了自己的調(diào)度算法,但大多數(shù)是靜態(tài)調(diào)度,如果網(wǎng)絡(luò)出現(xiàn)抖動(dòng)就需要重新調(diào)度,因此動(dòng)態(tài)調(diào)度成了新的重點(diǎn)研究方向。Nasrallah等人[32]設(shè)計(jì)了一種自適應(yīng)時(shí)隙窗口(Adaptive Slotted Windows,ASW)算法,通過(guò)對(duì)GCL動(dòng)態(tài)配置ST流和BE流的傳輸速率比,暫時(shí)犧牲BE流的QoS而為高優(yōu)先級(jí)TT流帶來(lái)超低的時(shí)延。Yu等人[33]提出了一種新的自適應(yīng)組路由和調(diào)度(Adaptive Group Routing and Scheduling,AGRS)算法,首先設(shè)計(jì)了一個(gè)預(yù)處理階段來(lái)加速動(dòng)態(tài)應(yīng)用的綜合調(diào)度過(guò)程,刪除不必要的節(jié)點(diǎn),并自適應(yīng)地將符合條件的拓?fù)渫暾訄D分組;在此基礎(chǔ)上,還提出了一種綜合考慮路由和調(diào)度過(guò)程的路由調(diào)度程序,以提高可調(diào)度性。該過(guò)程基于簡(jiǎn)化的拓?fù)浣Y(jié)構(gòu),從而大大減少了執(zhí)行時(shí)間。在文獻(xiàn)[33]的研究基礎(chǔ)上,馮澤坤等人[34]提出了一種基于ILP的動(dòng)態(tài)流量均衡調(diào)度算法,對(duì)路由、流的傳輸定時(shí)、無(wú)爭(zhēng)用、時(shí)延和鏈路負(fù)載進(jìn)行約束,不僅生成了滿足實(shí)時(shí)性的調(diào)度表,還保證了鏈路的負(fù)載均衡,讓處理動(dòng)態(tài)調(diào)度變得更為迅速和準(zhǔn)確。周小明等人[35]以最小化TT流的端到端時(shí)延為調(diào)度目標(biāo),提出了一種GCL自適應(yīng)調(diào)整算法。該算法根據(jù)可接受的最差時(shí)延上界Lexp算出擴(kuò)容閾值Let,然后通過(guò)集中式網(wǎng)絡(luò)控制器(Central Network Controller,CNC)計(jì)算一個(gè)GCL周期里實(shí)際傳輸TT幀的個(gè)數(shù)Nact,此時(shí)與最大可傳輸幀N進(jìn)行比較,若Nact≠N,則縮小TT流窗口并動(dòng)態(tài)配置到交換機(jī),返回CNC重新計(jì)算;當(dāng)Nact=N時(shí),則判斷平均端到端時(shí)延Lact是否大于端到端最大時(shí)延L或Let,若滿足,則擴(kuò)大TT流窗口并動(dòng)態(tài)配置到交換機(jī),否則返回CNC重新計(jì)算。這種算法通過(guò)動(dòng)態(tài)配置交換機(jī),保證了TT流的可靠傳輸,優(yōu)化了TT流傳輸?shù)钠骄鶗r(shí)延。

2.2 AVB流調(diào)度算法研究現(xiàn)狀

僅僅對(duì)TT流進(jìn)行調(diào)度有時(shí)會(huì)導(dǎo)致AVB流在最壞情況下出現(xiàn)時(shí)延等問(wèn)題,因此有必要對(duì)AVB流量調(diào)度問(wèn)題進(jìn)行研究。Berisa等人[36]考慮到GCL中任意數(shù)量的AVB隊(duì)列和CBS信用值的不同配置,提出一種具有幀搶占特征的啟發(fā)式算法和一種旨在最大化AVB可調(diào)度性的新型路由機(jī)制。對(duì)具有搶占的TSN網(wǎng)絡(luò)中的AVB流提出了一種新的最壞情況響應(yīng)時(shí)間分析,將TT調(diào)度表的創(chuàng)建與AVB流量的可調(diào)度性分析結(jié)合起來(lái),最小化TT流端到端時(shí)延,同時(shí)提高AVB流可調(diào)度性。Pop等人[37]同時(shí)對(duì)TT流和AVB進(jìn)行流量調(diào)度,對(duì)TT流的調(diào)度問(wèn)題提出了一個(gè)ILP調(diào)度算法,而在AVB調(diào)度問(wèn)題上則使用了一個(gè)基于GRASP的調(diào)度算法,同時(shí)保證了TT流的調(diào)度以及最小化AVB在最壞情況下的端到端時(shí)延。Laursen等人[38]則提出了一種KSP和GRASP復(fù)合算法來(lái)尋找最優(yōu)GCL方案,不僅降低了TT流傳輸和搶占對(duì)AVB流的影響,還最小化了AVB流調(diào)度的最壞端到端時(shí)延和保證了帶寬利用率。Gavrilut等人[39]提出了一種以禁忌搜索(Tabu Search,TS)的元啟發(fā)式算法為基礎(chǔ)的流量類型分配(Traffic Class Assignment,TTA)算法,用于確定混合臨界硬實(shí)時(shí)和軟實(shí)時(shí)報(bào)文的傳輸類型(AVB流和TT流)的分配,還同時(shí)優(yōu)化了TT流和AVB流的可調(diào)度性。王宇涵等人[40]則同時(shí)對(duì)TT流和AVB流進(jìn)行實(shí)時(shí)在線調(diào)度,針對(duì)TT流的實(shí)時(shí)調(diào)度,提出了基于虛擬最早截止期優(yōu)先(Virtual Earliest Deadline First,VEDF)的硬實(shí)時(shí)調(diào)度算法。該算法在TT流的每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)區(qū)域,TT流只有在該區(qū)域內(nèi)到達(dá)才能優(yōu)先調(diào)度;針對(duì)AVB流的調(diào)度,將啟發(fā)式調(diào)度算法和max-sum算法結(jié)合,將流開(kāi)始傳輸?shù)臅r(shí)間設(shè)為變量,約束關(guān)系作為函數(shù),迭代計(jì)算AVB流傳輸?shù)拈_(kāi)始時(shí)間,同時(shí)對(duì)AVB流的優(yōu)先級(jí)也有所設(shè)置,極大地減少了端到端時(shí)延和傳輸完成時(shí)間。

2.3 BE流調(diào)度算法研究現(xiàn)狀

目前國(guó)內(nèi)外對(duì)TSN流量調(diào)度的研究主要集中在TT流和AVB流上,從而忽略了BE流傳輸調(diào)度問(wèn)題。Nasrallah等人[32]提出了一種基于TAS機(jī)制的自適應(yīng)帶寬共享(Adaptive Bandwidth Sharing,ABS)算法,以提高鏈路利用率。ABS算法允許BE流在等待傳輸時(shí),ST流可以與其暫時(shí)共享時(shí)隙帶寬。這樣既減少了ST流的傳輸時(shí)延,又保證了BE流的低時(shí)延和可調(diào)度性。TSN在保證有限的時(shí)延和抖動(dòng)的同時(shí),也暴露出不能有效利用保護(hù)帶帶寬資源的缺點(diǎn)。為此,Zhang等人[41]提出了一個(gè)名為包大小感知整形(Packet-size Aware Shaping,PAS)的算法。PAS做出調(diào)度決策,計(jì)算調(diào)度過(guò)程的每個(gè)包的大小和剩余帶寬的數(shù)量。PAS在不要求專用MAC層的情況下追求近似于幀搶占的性能,最終使流的優(yōu)先級(jí)和帶寬利用率最大化,保障了BE流的傳輸效率。張楠浠等人[42]針對(duì)BE流的調(diào)度的3種場(chǎng)景提出了一種搶占式盡力而為流時(shí)序重排調(diào)度算法,有效減少了帶寬資源浪費(fèi),提高了帶寬利用率。

2.4 流量調(diào)度算法研究小結(jié)

TSN流量調(diào)度算法在當(dāng)前的調(diào)度機(jī)制框架上,針對(duì)不同調(diào)度流量和目標(biāo)提出了各自的方案,大幅優(yōu)化了性能。表2列出了文獻(xiàn)中提出的算法所用到的調(diào)度機(jī)制、優(yōu)勢(shì)以及缺點(diǎn)。當(dāng)前的TSN流量調(diào)度,除了針對(duì)路由選擇的算法,TT流的調(diào)度離不開(kāi)TAS機(jī)制,而不管是哪種流量類型的調(diào)度,都需要通過(guò)GCL進(jìn)行配置,這不免會(huì)使流量調(diào)度產(chǎn)生局限性,未來(lái)可以考慮基于CQF和ATS機(jī)制進(jìn)行算法的改進(jìn)。TSN調(diào)度算法解決了許多調(diào)度問(wèn)題,優(yōu)化了TSN的流量調(diào)度,但同時(shí)也會(huì)造成求解質(zhì)量低、求解時(shí)間長(zhǎng)、適用場(chǎng)景小等問(wèn)題,需要綜合多方面因素,針對(duì)實(shí)際應(yīng)用場(chǎng)景進(jìn)一步改進(jìn)算法。

表2 調(diào)度算法對(duì)比

表3總結(jié)了TSN流量調(diào)度的調(diào)度算法、調(diào)度流量類型、調(diào)度目標(biāo)、聯(lián)合路由以及動(dòng)/靜態(tài)等特點(diǎn)。目前的流量調(diào)度不僅能夠保證流量在網(wǎng)絡(luò)中的有序傳輸,還大幅優(yōu)化了實(shí)時(shí)流量的時(shí)延和有界時(shí)延抖動(dòng)問(wèn)題,而且對(duì)端到端時(shí)延、約束條件、帶寬利用率、可調(diào)度性等方面進(jìn)行優(yōu)化,實(shí)現(xiàn)了性能的提升。但仍然存在著以下三個(gè)問(wèn)題,即聯(lián)合路由調(diào)度問(wèn)題、混合流量的整體調(diào)度問(wèn)題和實(shí)時(shí)流動(dòng)態(tài)調(diào)度問(wèn)題。

表3 TSN流量調(diào)度總結(jié)

1)現(xiàn)有的TSN流量調(diào)度大多采用傳統(tǒng)以太網(wǎng)的路由方案,只考慮最短路徑、負(fù)載均衡等指標(biāo),沒(méi)有考慮到TSN不同流量類型的不同要求。表3中雖有聯(lián)合路由調(diào)度的算法,但大多只適用于小規(guī)模網(wǎng)絡(luò)中,仍需考慮實(shí)際運(yùn)用時(shí)的可行性。

2)現(xiàn)在大部分對(duì)TSN的研究集中在TT流上,而對(duì)AVB流和BE流的研究還相對(duì)較少。表3列出了一些混合流量調(diào)度算法,為了優(yōu)化ET流的傳輸性能,大家開(kāi)始關(guān)注AVB流與BE流,在保證TT流可調(diào)度的前提下,為其他流量留出隊(duì)列數(shù)以實(shí)現(xiàn)混合流的整體調(diào)度。但是對(duì)AVB流和BE流的研究主要是關(guān)注其時(shí)延和帶寬利用率,并沒(méi)有對(duì)兩種流量進(jìn)行針對(duì)性優(yōu)化。

3)現(xiàn)有的TSN流量調(diào)度幾乎都是靜態(tài)調(diào)度,缺少對(duì)動(dòng)態(tài)調(diào)度的研究,會(huì)導(dǎo)致實(shí)時(shí)調(diào)度時(shí)會(huì)出現(xiàn)無(wú)法應(yīng)對(duì)丟幀、時(shí)間同步誤差大等問(wèn)題,這極大地影響了流量傳輸?shù)目煽啃?。?中有些研究雖提出自己的方案,但解法過(guò)于復(fù)雜,且只能做到局部動(dòng)態(tài)調(diào)度,需要不斷優(yōu)化。

3 流量調(diào)度算法發(fā)展方向

TSN調(diào)度算法研究至今,已經(jīng)解決了標(biāo)準(zhǔn)協(xié)議里很多問(wèn)題,但是仍然存在路由選擇、忽視ET流調(diào)度和缺少動(dòng)態(tài)調(diào)度等問(wèn)題。針對(duì)這些問(wèn)題,學(xué)者們提出了一些解決思路,這也是未來(lái)TSN流量調(diào)度算法的研究方向。

目前TSN調(diào)度算法的發(fā)展方向有聯(lián)合路由調(diào)度、混合流量調(diào)度和動(dòng)態(tài)調(diào)度等。

1)聯(lián)合路由調(diào)度

很多TSN流量調(diào)度算法無(wú)法根據(jù)不同類型的流選擇不同的路由,降低了傳輸性能,因此需要綜合考慮流量和路由問(wèn)題,給出整體調(diào)度方案,將路由選擇作為變量,擴(kuò)大可行解的空間,實(shí)現(xiàn)調(diào)度目標(biāo)。不過(guò)這種方案也主要適用于靜態(tài)調(diào)度,在動(dòng)態(tài)調(diào)度中聯(lián)合路由調(diào)度是目前的研究重點(diǎn)。

2)混合流量調(diào)度

混合流量調(diào)度在保證TT流的可調(diào)度性的前提下,盡可能為AVB流和BE流留下隊(duì)列和時(shí)隙。而目前的混合流量調(diào)度算法依賴于標(biāo)準(zhǔn)協(xié)議規(guī)定的基本調(diào)度機(jī)制,TT流的調(diào)度基于TAS機(jī)制,AVB流的調(diào)度基于CBS機(jī)制,通過(guò)門(mén)控開(kāi)關(guān)實(shí)現(xiàn)不同流量的混合調(diào)度。未來(lái)可以基于CQF機(jī)制和ATS機(jī)制提出新的算法。

3)動(dòng)態(tài)調(diào)度

由于很難實(shí)現(xiàn)全局動(dòng)態(tài)調(diào)度,所以目前對(duì)動(dòng)態(tài)調(diào)度的研究?jī)H限于局部調(diào)度。采用全局靜態(tài)和局部動(dòng)態(tài)的調(diào)度方式是現(xiàn)在重點(diǎn)研究方向,全局只需規(guī)劃TT流和ET流的隊(duì)列分配方案,落實(shí)到各個(gè)端口再使用動(dòng)態(tài)調(diào)度,這樣可以減少傳輸時(shí)延,保證流的可調(diào)度性。

針對(duì)混合流量的調(diào)度,可以考慮當(dāng)網(wǎng)絡(luò)拓?fù)浜驼{(diào)度流量固定時(shí),預(yù)先計(jì)算不同流量在最壞情況下傳輸完成時(shí)間來(lái)獲得時(shí)間槽占用率,判斷流量是否滿足帶寬占用條件,對(duì)超出帶寬占用的流量重新分配合理的時(shí)間槽,這樣生成的GCL靜態(tài)調(diào)度表可以實(shí)現(xiàn)3種流量的整體調(diào)度;對(duì)于聯(lián)合路由的動(dòng)態(tài)調(diào)度,可以在每個(gè)交換節(jié)點(diǎn)和終端添加監(jiān)控,在拓?fù)涑跏蓟^(guò)程中將新訪問(wèn)的節(jié)點(diǎn)信息輸入到配置文件中,以更新網(wǎng)絡(luò)拓?fù)?實(shí)現(xiàn)動(dòng)態(tài)調(diào)度。

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

時(shí)間敏感網(wǎng)絡(luò)作為一種綜合高精度時(shí)間同步和多業(yè)務(wù)融合傳輸?shù)拇_定性網(wǎng)絡(luò)技術(shù),將信息網(wǎng)和控制網(wǎng)有機(jī)融合,已成為工業(yè)互聯(lián)網(wǎng)、車(chē)載通信網(wǎng)絡(luò)以及新一代軍工航電領(lǐng)域通信網(wǎng)絡(luò)構(gòu)建的關(guān)鍵技術(shù)。本文根據(jù)流量類型對(duì)流量調(diào)度算法進(jìn)行歸納總結(jié),從調(diào)度算法和整體調(diào)度方案兩方面給出了對(duì)比分析。盡管調(diào)度算法優(yōu)化了流量的調(diào)度,但仍然存在聯(lián)合路由調(diào)度、混合流量調(diào)度以及動(dòng)態(tài)調(diào)度的問(wèn)題。針對(duì)這三個(gè)問(wèn)題,分別提出未來(lái)的研究方向,可以利用時(shí)間槽的合理分配和在每個(gè)節(jié)點(diǎn)添加監(jiān)控以實(shí)現(xiàn)混合流量動(dòng)態(tài)調(diào)度的新思路,為后續(xù)TSN流量調(diào)度算法研究提供建議。