多模態(tài)網(wǎng)絡(luò)中時間敏感網(wǎng)絡(luò)模態(tài)的智能調(diào)度機制

楊思錦，莊雷，宋玉，王家興，陽鑫宇

（1.鄭州大學(xué)計算機與人工智能學(xué)院，河南 鄭州 450001；2.鄭州大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450002）

0 引言

隨著“互聯(lián)網(wǎng)+”“工業(yè)4.0”與“網(wǎng)絡(luò)5.0”的深度融合發(fā)展，現(xiàn)有互聯(lián)網(wǎng)基礎(chǔ)架構(gòu)及技術(shù)體系存在網(wǎng)絡(luò)結(jié)構(gòu)僵化、IP 單一承載、未知威脅難以抑制等基礎(chǔ)性問題，無法通過有限的資源動態(tài)化提供智慧、高效、多元的網(wǎng)絡(luò)差異化服務(wù)[1]。為打破上述網(wǎng)絡(luò)發(fā)展困境，加速推進新型網(wǎng)絡(luò)技術(shù)發(fā)展，我國鄔江興院士團隊[2]提出了一種網(wǎng)絡(luò)各層功能多模態(tài)呈現(xiàn)的網(wǎng)絡(luò)架構(gòu)——全維可定義的多模態(tài)智慧網(wǎng)絡(luò)。其確定了新型網(wǎng)絡(luò)基線方式，具有底層資源可重構(gòu)、多模態(tài)網(wǎng)絡(luò)并存、全業(yè)務(wù)承載、智慧化管理等特點[3]。作為未來通信網(wǎng)絡(luò)的發(fā)展范式，多模態(tài)網(wǎng)絡(luò)以開放式的網(wǎng)絡(luò)架構(gòu)，通過可編程技術(shù)支撐泛在物聯(lián)網(wǎng)和工業(yè)網(wǎng)多業(yè)務(wù)形態(tài)的并存部署，成為學(xué)術(shù)界和工業(yè)界的關(guān)注點[4]。

目前，在新型多模態(tài)智慧網(wǎng)絡(luò)中，由于不同的網(wǎng)絡(luò)模態(tài)和差異化的業(yè)務(wù)需求等因素，導(dǎo)致指數(shù)增長的數(shù)據(jù)量對業(yè)務(wù)控制信息實時性與確定性之間的矛盾。此外，通信平臺網(wǎng)絡(luò)化、共享化和數(shù)字化導(dǎo)致各種網(wǎng)絡(luò)數(shù)據(jù)流急劇增多，同時也加劇了網(wǎng)絡(luò)風(fēng)暴、時延、抖動及網(wǎng)絡(luò)丟包等問題。例如，智能電網(wǎng)作為多模態(tài)網(wǎng)絡(luò)最具代表性的行業(yè)應(yīng)用場景之一，是典型的多業(yè)務(wù)共存環(huán)境專網(wǎng)，其生產(chǎn)控制區(qū)業(yè)務(wù)和智能變電站業(yè)務(wù)對控制信令和數(shù)據(jù)采集有嚴(yán)格的低時延、有界抖動、高可靠等多種需求[5]。針對此類確定性的差異化需求，多模態(tài)網(wǎng)絡(luò)需要為其提供包括時延、抖動、丟包率等關(guān)鍵指標(biāo)在內(nèi)的確定性業(yè)務(wù)保障。

當(dāng)前能夠保障確定性傳輸?shù)募夹g(shù)主要有時間敏感網(wǎng)絡(luò)（TSN,time-sensitive network）和確定性網(wǎng)絡(luò)（DetNet,deterministic networking）等，它們主要研究網(wǎng)絡(luò)確定性傳輸與低時延高可靠路徑問題。TSN 工作組開發(fā)了相關(guān)的IEEE 協(xié)議標(biāo)準(zhǔn)，以支持專業(yè)的局域網(wǎng)實時應(yīng)用[6]。TSN 通過全網(wǎng)時鐘同步、時間感知整形（TAS,time-aware shaper）、流量調(diào)度等機制，實現(xiàn)了局域網(wǎng)范圍內(nèi)的時間敏感流和非實時流的共網(wǎng)傳輸。為了實現(xiàn)大規(guī)模確定性傳輸需求，IETF DetNet 工作組正在開發(fā)確定性體系架構(gòu)，其擴展了TSN 協(xié)議標(biāo)準(zhǔn)，致力于三層大規(guī)模確定性及可靠性傳輸[7]。TSN 和DetNet 兩者相互結(jié)合，通過協(xié)議擴展，來保證數(shù)據(jù)傳輸具有確定的低時延和低抖動，以滿足差異化的服務(wù)質(zhì)量（QoS,quality of service）要求，現(xiàn)已廣泛應(yīng)用于工業(yè)自動化、自動駕駛、智能電網(wǎng)等應(yīng)用場景[8]。但隨著新型IP、工業(yè)互聯(lián)、空天地一體化等大規(guī)模時間敏感應(yīng)用的興起，如何實現(xiàn)多樣化網(wǎng)絡(luò)模態(tài)共生共存環(huán)境下的TSN 模態(tài)的流量調(diào)度，充分發(fā)揮網(wǎng)絡(luò)特色模態(tài)的業(yè)務(wù)優(yōu)勢，成為當(dāng)前面臨的一個重要挑戰(zhàn)。

流量調(diào)度是實現(xiàn)確定性傳輸?shù)暮诵臋C制，其通過特定的調(diào)度算法在選定的所有交換機出口確定每個數(shù)據(jù)幀的傳輸時隙，保證所有幀在出口鏈路上依次無沖突地傳輸，同時滿足流量各自的時延和帶寬等要求，使不同類別的業(yè)務(wù)需求在同一網(wǎng)絡(luò)上共存。調(diào)度與路由聯(lián)合規(guī)劃是實現(xiàn)大規(guī)模流量調(diào)度的主要發(fā)展趨勢之一，其被排除在IEEE 802.1 標(biāo)準(zhǔn)之外。聯(lián)合調(diào)度的一個關(guān)鍵難題是如何將動態(tài)時隙分配與產(chǎn)生的大量路徑相協(xié)調(diào)，在大規(guī)模場景下，該問題計算復(fù)雜度高，難以滿足時延調(diào)度需求。因此，本文引入深度強化學(xué)習(xí)（DRL,deep reinforcement learning）算法預(yù)測隊列的利用率，生成顯式路由方案，并與基于循環(huán)隊列與轉(zhuǎn)發(fā)機制相結(jié)合，設(shè)計了一種多模態(tài)網(wǎng)絡(luò)場景下面向時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合路由與調(diào)度機制，從而使業(yè)務(wù)流在滿足差異化QoS 目標(biāo)上實現(xiàn)快速調(diào)度。

本文主要研究工作如下。

1) 基于多模態(tài)體系架構(gòu)和循環(huán)隊列與轉(zhuǎn)發(fā)機制，在時間敏感網(wǎng)絡(luò)模態(tài)下開展數(shù)據(jù)流的全局靜態(tài)隊列規(guī)劃與局部時隙動態(tài)分配聯(lián)合調(diào)度，實現(xiàn)大規(guī)模場景下的時間敏感流的自動化控制與調(diào)度。

2) 建立機器學(xué)習(xí)輔助的聯(lián)合調(diào)度優(yōu)化模型，引入改進的DRL 算法建立流量狀態(tài)與網(wǎng)絡(luò)狀態(tài)及路由隊列狀態(tài)之間的關(guān)系，以預(yù)測下一時隙隊列利用率，實現(xiàn)在線智能的顯式路由決策。

3) 通過基于NeSTiNg 模型的仿真來驗證本文調(diào)度機制。仿真結(jié)果表明，本文調(diào)度機制可以很好地為時間敏感應(yīng)用提供低時延、低抖動的服務(wù)，同時提高了流的可調(diào)度性和資源利用率；與經(jīng)典調(diào)度機制對比，本文調(diào)度機制的有效性更好。

1 背景與相關(guān)工作

1.1 CSQF 調(diào)度機制

DetNet 工作組提出了適應(yīng)大規(guī)模網(wǎng)絡(luò)標(biāo)準(zhǔn)的循環(huán)指定排隊和轉(zhuǎn)發(fā)（CSQF,cycle specified queuing and forwarding）機制。不同于TSN 中的時間緊迫觸發(fā)整形機制，如TAS、循環(huán)排隊與轉(zhuǎn)發(fā)（CQF,cycle queuing and forwarding），CSQF 放松了嚴(yán)格的同步約束，通過增加一個接收隊列、一個發(fā)送隊列和多個額外隊列來實現(xiàn)靈活的傳輸調(diào)度。其中，額外隊列可以增加數(shù)據(jù)包緩存，并具有一定的處理抖動和流量突發(fā)的能力。CSQF 允許使用段路由對數(shù)據(jù)包進行路由和調(diào)度，可同時動態(tài)協(xié)調(diào)每個端口的傳輸周期。

DetNet 草案[9]描述了在大規(guī)模確定性網(wǎng)絡(luò)中，所有網(wǎng)絡(luò)設(shè)備通過IEEE 1588v2 精確網(wǎng)絡(luò)時間協(xié)議（PTP,precise time protocol）實現(xiàn)了全局頻率同步。這使路由器能夠根據(jù)本地時間將時間域劃分為多個等長的周期，以便合理安排轉(zhuǎn)發(fā)行為進行周期映射。并且相鄰設(shè)備之間有穩(wěn)定的周期映射關(guān)系，在通過自適應(yīng)學(xué)習(xí)獲得映射關(guān)系后進行后續(xù)業(yè)務(wù)的轉(zhuǎn)發(fā)。在流量整形與轉(zhuǎn)發(fā)方面，草案規(guī)定時間敏感流的每個數(shù)據(jù)包都攜帶一個具有當(dāng)前周期號的標(biāo)識符，以便設(shè)備確定再次轉(zhuǎn)發(fā)的周期。在轉(zhuǎn)發(fā)周期內(nèi)，只有發(fā)送隊列中緩存的數(shù)據(jù)包可以發(fā)送，而其余隊列只能接收或等待轉(zhuǎn)發(fā)。

1.2 相關(guān)工作

以前大多數(shù)的聯(lián)合調(diào)度相關(guān)研究都是基于嚴(yán)格的時間同步，利用TSN 機制實現(xiàn)局域網(wǎng)內(nèi)的確定性業(yè)務(wù)。文獻[10]將時間觸發(fā)流和速率約束流分離，優(yōu)化了幀到虛擬鏈路的分配和虛擬鏈路路由的靜態(tài)調(diào)度，采用禁忌搜索算法搜索路由與調(diào)度聯(lián)合方案。文獻[11]提出了一種基于遺傳算法的啟發(fā)式調(diào)度方法，以時間觸發(fā)流的路由和調(diào)度約束組合作為基因，生成了靜態(tài)全局調(diào)度。文獻[12]設(shè)計了一種解決路由和調(diào)度的整數(shù)線性規(guī)劃（ILP,integer linear programming），以最小化端到端時延為目標(biāo)，通過刪減流與鏈路無關(guān)的映射條件來縮小問題的規(guī)模，并通過ILP 求解器獲得具有較低通信時延的調(diào)度方案。文獻[13]提出了一種音視頻橋接（AVB,audio video bridging）流和時間觸發(fā)（TT,time-triggered）流共存的聯(lián)合調(diào)度方法。在考慮AVB 流的同時解決了TT 流的聯(lián)合路由與調(diào)度問題，其結(jié)合K-最短路徑算法和基于貪婪隨機自適應(yīng)搜索過程的元啟發(fā)式算法，提出了聯(lián)合路由與調(diào)度策略以決策TT流的路徑和門控列表（GCL,gate control list）。聯(lián)合路由與調(diào)度策略迭代執(zhí)行集成的路由算法并搜索最優(yōu)的GCL，最后在迭代過程中不斷更新最優(yōu)路由與GCL 方案。文獻[14]提出了一種啟發(fā)式列表調(diào)度器用于TSN 的全局調(diào)度，將調(diào)度和路由約束合并為一組約束，并在單個步驟中利用該約束計算特定于端口的GCL；根據(jù)終端系統(tǒng)之間的最短路徑，采用啟發(fā)式列表調(diào)度算法依次遍歷可行的計算節(jié)點，并在每個節(jié)點下遍歷流的可選路徑，在滿足最小化流總傳輸時延的目標(biāo)基礎(chǔ)上，選擇完成時間最小的路徑和傳輸時延。文獻[15]提出了一種基于配置沖突圖的方法，將路由和調(diào)度問題歸約為沖突圖，通過在沖突圖中搜索一個獨立的頂點集來解決原始的流量規(guī)劃問題；在導(dǎo)出配置沖突圖過程中，將路徑和傳輸開始時間作為節(jié)點，若同時采用2 個節(jié)點的配置，則會破壞約束，即2 個節(jié)點存在沖突，沖突圖中的所有無關(guān)點組合被認為是有效的路由和調(diào)度方案，但其同樣采用ILP 聯(lián)合啟發(fā)式算法進行求解。文獻[16]考慮大規(guī)模TSN 的無等待調(diào)度和多路徑路由問題，采用離線調(diào)度方法，以已知的TT流為節(jié)點，以流之間的相關(guān)程度為邊，通過基于迭代TLP 的可伸縮調(diào)度（IIS,iterated integer-linearprogramming based scheduling）技術(shù)將流分組，并以圖劃分算法將IIS 迭代之間的沖突程度降至最低；采用貪心隨機自適應(yīng)搜索算法探索多路徑路由技術(shù)，經(jīng)過多次迭代，最終找出沖突最小的分組和多路徑方案。其同樣采用ILP 求解每組的約束，最終所有分組的可行解組合為可行的調(diào)度方案。上述流量調(diào)度機制大多基于TAS 調(diào)度TT 流，基于CBS（credit-based shaper）調(diào)度AVB 流，且需要嚴(yán)格的全網(wǎng)時鐘同步及復(fù)雜的門控調(diào)度列表，因此，以上機制在大規(guī)模確定性網(wǎng)絡(luò)中效果不佳。

在最新的大規(guī)模確定性網(wǎng)絡(luò)研究中。Krolikowski等[17]采用CSQF 與分段路由提出了離線和在線2 種集中控制平面算法，以最大化流量接受率。其主要關(guān)注的是確定性網(wǎng)絡(luò)的有界時延和抖動，將聯(lián)合路由與調(diào)度問題描述為一個多商品流問題的擴展，通過列生成和動態(tài)規(guī)劃的方法進行問題的求解。但在線快速調(diào)度只適用于小部分流。文獻[18]在文獻[17]的基礎(chǔ)上，提出了一種負載均衡的解決方案，在產(chǎn)生候選路徑的過程中，考慮鏈路的負載，在解決單個調(diào)度路徑路由問題的情況下，生成可行的負載均衡策略。但其未討論多流競爭資源的問題。文獻[19]提出了一種基于軟件定義的時間敏感網(wǎng)絡(luò)跨域調(diào)度機制，基于3 種廣域時鐘同步技術(shù)保障了納秒級的域間同步；利用時隙無沖突約束條件限制了邊緣流量的到達時間，解決了域間鏈路時延的對齊問題；最后在線計算得到全局的門控調(diào)度列表。但其未考慮路由帶來的路徑瓶頸問題。

綜上所述，現(xiàn)有時間敏感網(wǎng)絡(luò)的流量調(diào)度大多基于給定的路由方案，路由算法通常采用最短路徑或生成樹協(xié)議來確定，未考慮多流聚合時的資源爭用問題，且主要適用于離線計算的場景。然而，在實際網(wǎng)絡(luò)中，流量可能實時動態(tài)變化，此外，在大規(guī)模多模態(tài)網(wǎng)絡(luò)調(diào)度場景下，在線智能化的路由與調(diào)度聯(lián)合機制是必要的。為此，本文針對多模態(tài)網(wǎng)絡(luò)中大規(guī)模時間敏感網(wǎng)絡(luò)模態(tài)的流量調(diào)度問題進行了研究，提出了基于CSQF整形機制的時間敏感網(wǎng)絡(luò)模態(tài)智能調(diào)度機制和算法，聯(lián)合調(diào)度路徑和隊列資源，保證了多業(yè)務(wù)場景下流量的有界時延及可調(diào)度性。

2 系統(tǒng)模型

本節(jié)針對時間敏感網(wǎng)絡(luò)模態(tài)的流量調(diào)度問題，在遵循CSQF的基本轉(zhuǎn)發(fā)準(zhǔn)則下，設(shè)計了基于CSQF的網(wǎng)絡(luò)模型和數(shù)學(xué)模型。

2.1 基于CSQF 的網(wǎng)絡(luò)模型

針對基于CSQF 的確定性多模態(tài)基礎(chǔ)網(wǎng)絡(luò)，本文將時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合路由與調(diào)度問題定義為在滿足調(diào)度模型的約束條件下，針對時間觸發(fā)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施和流量模式F，尋找一個可行的網(wǎng)絡(luò)調(diào)度，以最大化可調(diào)度數(shù)據(jù)流數(shù)量。為不失一般性，本文將網(wǎng)絡(luò)拓撲建模為有向圖 G=(V ,E)，其中，V={v1,v2,…,vV}表示底層多模態(tài)路由節(jié)點集合，E={e1,e2,…,eE}表示相互連接的有向邊集合。每一個鏈路 e=(u ,v )∈E 包含一個從節(jié)點u到節(jié)點v的長距離鏈路時延和處理時延le。每條鏈路e的帶寬容量為Ce，在一個周期T內(nèi)鏈路傳輸?shù)淖畲罅髁慷x為周期流量，用CeT 表示。時間敏感流定義為元組f=(src,dst,t,period,pnum,Df)∈F，每個流fi分別由源節(jié)點、目的節(jié)點、流傳輸時延、發(fā)送周期、數(shù)據(jù)包數(shù)量和最大端到端時延組成。系統(tǒng)參數(shù)如表1 所示。

表1 系統(tǒng)參數(shù)

為了統(tǒng)一時間敏感流的不同傳輸周期，設(shè)置超周期P等于所有時間敏感流的最小公倍數(shù)，如式(1)所示。

2.2 基于CSQF 的數(shù)學(xué)模型

本文調(diào)度機制的目的是最大化可調(diào)度時間敏感流的數(shù)量，其目標(biāo)函數(shù)為

其中，Scheduled(fi)表示時間敏感流fi可成功調(diào)度。對于每個流f∈F，本文將可行路徑集表示為PATH，對應(yīng)于流f的源和目的地之間的路徑，其端到端時延滿足路徑 p∈PATH 上的E2E（end to end）時延約束。在每個超周期內(nèi)，若分配的時隙在每個邊不重疊，并且滿足每個流的調(diào)度約束，則網(wǎng)絡(luò)調(diào)度是可行的。本文提出的基于CSQF 的調(diào)度機制必須滿足以下核心約束條件。

1) 周期約束

為了限制周期T的上限和下限，本文在CSQF中設(shè)置了等長的時隙，如式(3)所示。

其中，MTU 為最大數(shù)據(jù)包長度。

2) 截止時間約束

對于每個確定性數(shù)據(jù)流，該約束是實現(xiàn)有界時延的確定性轉(zhuǎn)發(fā)關(guān)鍵。對于每一條輸入流，其發(fā)送時延、處理時延和鏈路時延組成了端到端時延，三者之和應(yīng)該小于或等于端到端最大時延。該約束定義為

3) 分配配置約束

為了確保多個流不會被同時調(diào)度到同一條鏈路，在基于CSQF 實現(xiàn)的調(diào)度中，一次只能為一個時間敏感流fi保留一個時隙資源。該約束定義為

4) 時隙無重疊約束

在基于CSQF 的調(diào)度中，要確保每個流在每個輸出端口上的時隙必須比輸入鏈路上的時隙調(diào)度得晚，即在任何傳輸周期內(nèi)，流fi在下一跳的傳輸時間應(yīng)大于后續(xù)流fj的出端口時間。式(7)確保了流fi在出端口的傳輸時間和其他任何流fj的出端口時間都不重疊。該約束定義為

當(dāng)網(wǎng)絡(luò)基礎(chǔ)設(shè)施的規(guī)模和復(fù)雜性增加，將多個業(yè)務(wù)的時間敏感流映射到某個網(wǎng)絡(luò)路徑上時，可能稍后才會發(fā)現(xiàn)該路徑上的單個鏈路過載，或者因時隙重疊阻塞了流的傳輸，從而使數(shù)據(jù)流無法滿足其時延約束。此外，如果選擇的下一跳不需要排隊就能轉(zhuǎn)發(fā)，那么就網(wǎng)絡(luò)節(jié)點而言，較長的可行路徑甚至?xí)a(chǎn)生更低的時延。為了解決路由和調(diào)度之間的相互依賴，一種顯式路由策略是必要的。下面將介紹基于預(yù)測隊列緩存利用率的顯式路由策略，聯(lián)合動態(tài)資源調(diào)度，以確定最佳路由和調(diào)度選項。

3 時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合調(diào)度機制

針對時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合調(diào)度問題，本文設(shè)計了時間敏感網(wǎng)絡(luò)模態(tài)的智能調(diào)度機制和算法。首先，在基于CSQF 的多隊列轉(zhuǎn)發(fā)平面中，來自不同上游節(jié)點的數(shù)據(jù)包可以映射到相同的發(fā)送周期并共享相同的隊列，因此會產(chǎn)生聚合調(diào)度問題。此時，隊列緩存是產(chǎn)生數(shù)據(jù)包丟失的主要因素。為了解決該問題，本文設(shè)計了一個基于預(yù)測隊列利用率的顯式路由解決方案，以獲得端到端時延與網(wǎng)絡(luò)負載之間的均衡，同時解決靜態(tài)路由造成的資源爭用問題。該方案以DRL 為基礎(chǔ)，依據(jù)當(dāng)前隊列緩存狀態(tài)和網(wǎng)絡(luò)指標(biāo)，預(yù)測下一跳隊列利用率，并根據(jù)當(dāng)前和預(yù)測的隊列利用率實現(xiàn)負載均衡的顯式路由。其次，時間敏感流與資源分配關(guān)系是NP 難問題，因此，基于顯式路由方案，本文設(shè)計了一種時間敏感網(wǎng)絡(luò)模態(tài)的在線多約束迭代調(diào)度算法，按流的固有到達順序逐流進行調(diào)度，從而減少了計算時間，獲得滿足約束的局部最優(yōu)解，提高了可調(diào)度數(shù)據(jù)流的數(shù)量。

3.1 基于DRL 的顯式路由

本文提出的顯式路由方案考慮當(dāng)前和預(yù)測的隊列緩存利用率，決定緩沖區(qū)中數(shù)據(jù)包的下一跳。當(dāng)轉(zhuǎn)發(fā)節(jié)點接收到數(shù)據(jù)包時，它會根據(jù)多個指標(biāo)（如隊列利用率和最大化時延）選擇下一跳候選集，以避免數(shù)據(jù)包丟失、降低排隊時延或達到無等待傳輸，減少抖動。

在基于DRL 預(yù)測整形緩存利用率的路由問題中，狀態(tài)、動作、獎勵的具體含義如下。

1) 狀態(tài)。在時間敏感網(wǎng)絡(luò)模態(tài)中，狀態(tài)指數(shù)據(jù)分析代理解析出的網(wǎng)絡(luò)中的流請求信息和網(wǎng)絡(luò)信息，狀態(tài)用st=[Ft,bwt,qut,pri]表示，其中，F(xiàn)t為t時刻流請求集合，bwt為t時刻帶寬容量，qut為當(dāng)前節(jié)點隊列整形緩存利用率，pri 為流的優(yōu)先級。

2) 動作。動作指將描述的狀態(tài)信息st作為輸入，根據(jù)優(yōu)化策略函數(shù)指定每個流的下一跳，并生成一個流量分配配置操作。強化學(xué)習(xí)智能體在獲得當(dāng)前環(huán)境狀態(tài)st后，根據(jù)策略函數(shù)π 生成動作向量at，并將動作的獎勵rt反饋給智能體。動作向量at可表示為

其中，at=[a1,a2,…,an]，每個分量ai(0≤i≤ n)表示鄰居節(jié)點之間可用隊列緩存的比重。

3) 獎勵。獎勵是對選擇動作所獲收益的評價。本文模型的目標(biāo)是讓數(shù)據(jù)包的時延降低到所需時間間隔內(nèi)，同時最大限度地提高整形緩存隊列的利用率，因此，在節(jié)點i和時間t內(nèi)，將屬于流fj緩存中的數(shù)據(jù)包轉(zhuǎn)發(fā)到下一節(jié)點，其獎勵為

其中，bwi,t表示剩余鏈路容量，qi,t表示剩余緩存資源，Bwi和Qi分別表示節(jié)點的總?cè)萘颗c總緩存資源，Pj表示流fj的長度。

本文采用三層DQN 神經(jīng)網(wǎng)絡(luò)來解決多狀態(tài)和動作問題，將網(wǎng)絡(luò)狀態(tài)作為輸入層，通過與特征對應(yīng)的計算，網(wǎng)絡(luò)模型得到下一時隙緩存隊列的預(yù)測值。為了取得較好的訓(xùn)練效果，采用策略梯度的方法，即用神經(jīng)網(wǎng)絡(luò)將策略參數(shù)化，尋找最優(yōu)的參數(shù)使所有數(shù)據(jù)流的端到端時延最小。損失函數(shù)則是對參數(shù)化后的目標(biāo)函數(shù)求梯度，使其以最快的速度向目標(biāo)函數(shù)收斂。此時搜索空間相比于初始階段較小，故損失函數(shù)為

針對下一跳選擇機制，使用隊列利用率qu(k)和帶寬利用率來度量路由器，記為RANK，并基于該RANK 值從候選集中選擇下一跳。路由器k的RANK 為

其中，參數(shù) α+β+γ=1。每個路由器根據(jù)式(12)定義的鄰居節(jié)點 N (k)確定下一跳候選集Hk，即

基于隊列緩存利用率的路徑選擇算法允許每個路由器選擇具有較低隊列利用率的下一跳。雖然所選路徑不一定是路由跳數(shù)最少的，但考慮緩存隊列的利用率及鏈路利用率，可以實現(xiàn)更低的排隊時延，有效利用底層網(wǎng)絡(luò)資源。隊列緩存的顯式路由算法如算法1 所示。在離散時間段內(nèi)，對于每個路由器，采用鏈路容量、業(yè)務(wù)模式、當(dāng)前隊列緩存利用和流優(yōu)先級作為輸入，經(jīng)過運行階段和中央控制器的信息分發(fā)，每個確定性路由節(jié)點可以根據(jù)神經(jīng)網(wǎng)絡(luò)的輸出做出路由決策，實現(xiàn)負載均衡的路徑方案。

算法1基于隊列緩存的顯式路由算法

3.2 動態(tài)調(diào)度算法設(shè)計

時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合路由與調(diào)度機制的整體流程如算法2 所示。

算法2時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合路由與調(diào)度機制

算法2 的輸入為順序到達的流量模型F、網(wǎng)絡(luò)拓撲G，輸出為最終可調(diào)度的數(shù)據(jù)流集合Fsched。首先，算法初始化可調(diào)度流量集合（第1)行）；隨后，通過算法1 的顯式路由算法得到可行的調(diào)度路徑集（第2)行），并基于每個路由器的RANK 值進行鏈路的排序，得到一條顯式路由（第3)～5)行）。在進行迭代調(diào)度過程中，先根據(jù)預(yù)定義的路由和CSQF 多隊列機制，產(chǎn)生2.2 節(jié)定義的鏈路無重疊的約束條件式(3)～式(7)（第7)行）。在滿足約束條件下，求解目標(biāo)函數(shù)得到一個可行的調(diào)度方案，將該調(diào)度結(jié)果更新到Fsched中，并迭代計算未成功調(diào)度的具有較高優(yōu)先級的流（第8)～14)行）。最后得到可調(diào)度的全部數(shù)據(jù)流。

4 仿真實驗

4.1 實驗環(huán)境

本文在NeSTiNg[20]上實現(xiàn)了調(diào)度模型實例。NeSTiNg 是基于 OMNeT++離散事件模擬器和INET 框架的模擬器，可為網(wǎng)絡(luò)層的DetNet 服務(wù)和鏈路層的TSN 提供構(gòu)建塊，能夠輕松地進行實驗。本文使用Python 和Tensorflow 搭建DRL 網(wǎng)絡(luò)并進行模型的訓(xùn)練。

考慮多樣化的綜合網(wǎng)絡(luò)環(huán)境，本文設(shè)置了具有9 個核心節(jié)點和100 個邊緣節(jié)點的大規(guī)模多模態(tài)網(wǎng)絡(luò)場景。接入和核心鏈路的容量分別為10 Mbit/s和100 Mbit/s，鏈路時延為1～10 ms，設(shè)置每個多模態(tài)路由節(jié)點的帶寬為100 Mbit/s。底層多模態(tài)網(wǎng)元均采用3 個隊列的CSQF，用于確定性流量傳輸，隊列大小為1 MB，周期持續(xù)時間T=10 μs，超周期P=10 ms。依據(jù)實際場景業(yè)務(wù)需求和TSN 實驗臺定義的流量特征，生成具有隨機源和目的地的時間敏感流[21]，所有的流連續(xù)不斷地產(chǎn)生，均服從均值為λ 的泊松分布。本文在網(wǎng)絡(luò)中部署了2 000 條具有4 種不同周期的流，周期分別為1 ms、2 ms、5 ms、10 ms。所有應(yīng)用程序的帶寬要求遵循泊松分布，持續(xù)時間服從指數(shù)分布，模擬時間設(shè)置為1 800 s。

4.2 結(jié)果和分析

為了證明時間敏感網(wǎng)絡(luò)模態(tài)的聯(lián)合調(diào)度機制的有效性，本文將其與基于CSQF 的最短路徑（SP-CSQF,short path CSQF-based）機制和隨機列生成（CG-RR-CSQF,column generation and randomized rounding-CSQF）機制[17]進行了結(jié)果對比。調(diào)度性能的評價指標(biāo)是運行時間與調(diào)度成功率。

4.2.1 流量規(guī)模對調(diào)度性能的影響

調(diào)度成功率隨TS 流數(shù)量的變化如圖1 所示。隨著流數(shù)量的增加，3 種策略的調(diào)度成功率均有下降趨勢，但本文機制一直保持最高的調(diào)度成功率。當(dāng)網(wǎng)絡(luò)中時間敏感流數(shù)量為200 時，本文機制與CGRR-CSQF 機制均能調(diào)度98%的流量，而SP-CSQF機制只能成功調(diào)度約80%的流量。當(dāng)流數(shù)量大于200 時，會產(chǎn)生資源爭用問題，但本文機制采用的智能顯式路由策略會根據(jù)不同的流量特征選擇下一跳，相比于最短路徑，路由節(jié)點和鏈路不會成為流量瓶頸，而且采用的整形機制錯開了TS 流之間的傳輸時隙，因此，本文機制調(diào)度成功率相比于SP-CSQF和CG-RR-CSQF 分別提高了31%和7%。

圖1 調(diào)度成功率隨TS 流數(shù)量的變化

隨著流數(shù)量的增多，3 種調(diào)度機制的運行時間變化如圖2 所示。從圖2 中可以看出，本文機制可以在較短的時間內(nèi)提供解決方案，在降低求解時間的同時保證了穩(wěn)定的調(diào)度成功率。這對于在線調(diào)度來說是合理的。CG-RR-CSQF 和SP-CSQF 均采用離線調(diào)度方式，而且需要預(yù)知所有流的信息，計算時間長；而本文機制在線動態(tài)調(diào)度逐流進行計算，減少了計算時間。綜合來看，本文基于預(yù)測隊列的聯(lián)合調(diào)度機制是有效的。

圖2 運行時間隨TS 流數(shù)量的變化

4.2.2 不同網(wǎng)絡(luò)規(guī)模對調(diào)度性能的影響

為了探究網(wǎng)絡(luò)規(guī)模對調(diào)度性能的影響，本文隨機生成3 個不同規(guī)模的網(wǎng)絡(luò)，分別包含50 個、100 個和150 個路由節(jié)點，待處理流的數(shù)量為1 000 個。

網(wǎng)絡(luò)規(guī)模對丟包率的影響如圖3 所示。隨著網(wǎng)絡(luò)規(guī)模的增大，更多的下一跳候選節(jié)點可以帶來更好的性能，所以3 種調(diào)度機制的丟包率都略有下降，但本文機制具有較低的丟包率。3.1 節(jié)的理論描述可以很好地解釋這一結(jié)果，本文使用的神經(jīng)網(wǎng)絡(luò)具有較強的學(xué)習(xí)能力，具有與非線性關(guān)系的關(guān)聯(lián)能力，與CG-RR-CSQF 和SP-CSQF 相比，避免了緩沖區(qū)資源較少的路由作為下一跳，因此降低了丟包率。

圖3 網(wǎng)絡(luò)規(guī)模對丟包率的影響

網(wǎng)絡(luò)規(guī)模對調(diào)度成功率的影響如圖4 所示。隨著網(wǎng)絡(luò)規(guī)模的增大，可選的下一跳及可用的鏈路資源也越來越多，因此3 種調(diào)度機制的調(diào)度成功率均有上升。通過與SP-CSQF 和CG-RR-CSQF 對比可以看出，本文機制采用的動態(tài)路由方案在處理大規(guī)模網(wǎng)絡(luò)時具有較高的調(diào)度成功率。

圖4 網(wǎng)絡(luò)規(guī)模對調(diào)度成功率的影響

4.2.3 調(diào)度機制對時延的影響

時延是確定性網(wǎng)絡(luò)需要解決的首要因素，因為確定性時延應(yīng)用所需的時延是有界的，這為網(wǎng)絡(luò)調(diào)整數(shù)據(jù)傳輸提供了一定程度的靈活性。為了評估調(diào)度機制對時延的影響，本節(jié)以數(shù)據(jù)包在網(wǎng)絡(luò)中經(jīng)歷的平均跳數(shù)為基準(zhǔn)，對比了不同調(diào)度機制的性能，結(jié)果如圖5 所示。本文機制的平均跳數(shù)大于CG-RR-CSQF 和SP-CSQF。這說明根據(jù)網(wǎng)絡(luò)狀態(tài)調(diào)整傳輸時延的機制是有效的，即本文考慮隊列利用率的方案可以避免選擇隊列緩沖資源較少的路由器，并基于預(yù)測的隊列利用率選擇滿足有界時延的下一跳，雖然增加了跳數(shù)，但減少了排隊時延，降低了端到端時延。而CG-RR-CSQF和SP-CSQF 雖然經(jīng)歷的平均跳數(shù)相對較少，但其不能根據(jù)網(wǎng)絡(luò)狀態(tài)調(diào)整傳輸時延，因此會增大排隊時延，造成較高的丟包率。此外，這也從側(cè)面證明了本文機制適合長距離傳輸，且隨著時間的推移趨于收斂且具有穩(wěn)定性。

圖5 不同調(diào)度機制的性能

4.2.4 不同層數(shù)的DQN 對調(diào)度性能的影響

本節(jié)評估不同層數(shù)的DQN 對調(diào)度性能的影響。DQN-1、DQN-2、DQN-3 分別表示層數(shù)為1、2、3 的DQN，共有100 個訓(xùn)練周期，每個周期迭代1 000 次。不同DQN 層數(shù)調(diào)度成功率隨訓(xùn)練周期的變化如圖6 所示。通過對比可知，從宏觀來看，隨著DQN 層數(shù)的增加，調(diào)度機制的整體性能逐漸提高；且隨著訓(xùn)練次數(shù)的增加，調(diào)度成功率也顯著增加。尤其當(dāng)運行60 個訓(xùn)練周期后，DQN-3 的性能明顯優(yōu)于DQN-1 和DQN-2，這說明在運行時間隨訓(xùn)練周期增加而增加的條件下，本文使用的DQN-3 具有明顯的實效，且收斂性良好。

圖6 不同DQN 層數(shù)調(diào)度成功率隨訓(xùn)練周期的變化

5 結(jié)束語

本文依據(jù)TSN 相關(guān)理論基礎(chǔ)和標(biāo)準(zhǔn)，對多模態(tài)網(wǎng)絡(luò)中的時延敏感流調(diào)度機制進行了擴展和改進，提出了一種基于CSQF 的大規(guī)模時間敏感網(wǎng)絡(luò)模態(tài)聯(lián)合路由與調(diào)度機制，以適應(yīng)多樣化網(wǎng)絡(luò)模態(tài)共生共存的環(huán)境。該機制利用DRL 預(yù)測轉(zhuǎn)發(fā)節(jié)點的隊列緩存利用率，將聯(lián)合路由與調(diào)度機制分解為全局靜態(tài)和局部動態(tài)的結(jié)合。在動態(tài)調(diào)度過程中，基于預(yù)測的隊列利用率生成不同的顯式路由，解決了由于流量聚合而造成的數(shù)據(jù)丟包率高的問題。同時，智能選擇下一跳機制可消除排隊時延，保證時延的有界性及確定性。另外，基于CSQF 的迭代調(diào)度機制解決了離線調(diào)度求解時間長的問題。實驗結(jié)果表明，在多網(wǎng)絡(luò)模態(tài)融合的多模態(tài)場景下，本文聯(lián)合路由與調(diào)度機制可以在較短的時間內(nèi)得出調(diào)度結(jié)果且具有較高的資源利用率和調(diào)度成功率。