聶宏蕊，李紹勝，劉勇

（1.北京郵電大學(xué)信息與通信工程學(xué)院，北京 100876；2.北京郵電大學(xué)人工智能學(xué)院，北京 100876）

0 引言

在許多分布式硬實(shí)時(shí)和安全關(guān)鍵應(yīng)用領(lǐng)域，例如汽車和工業(yè)控制應(yīng)用，當(dāng)前專有的基于總線的網(wǎng)絡(luò)技術(shù)在支持不斷增長(zhǎng)的通信帶寬需求方面已達(dá)到極限[1]。以太網(wǎng)因支持更高的數(shù)據(jù)速率、更低的成本，在可擴(kuò)展性和兼容性等方面具有很大的優(yōu)勢(shì)，正在開始逐步取代專有現(xiàn)場(chǎng)總線[2]。然而，傳統(tǒng)的IP 服務(wù)允許傳送數(shù)據(jù)包而不會(huì)丟失，也不會(huì)出現(xiàn)排序問題。但是，它們不能提供嚴(yán)格的QoS 保證，不適合具有高實(shí)時(shí)性與高安全性要求的應(yīng)用。確定性轉(zhuǎn)發(fā)服務(wù)對(duì)數(shù)據(jù)包傳輸過程中的時(shí)延、丟包和抖動(dòng)有嚴(yán)格的要求，這對(duì)于嚴(yán)格的實(shí)時(shí)應(yīng)用是非常理想的。為了實(shí)現(xiàn)確定性低時(shí)延傳輸，工業(yè)界在標(biāo)準(zhǔn)以太網(wǎng)的基礎(chǔ)上提出了多種專屬網(wǎng)絡(luò)協(xié)議，如時(shí)間觸發(fā)以太網(wǎng)（TTEthernet,time triggered Ethernet）技術(shù)、工業(yè)以太網(wǎng)控制自動(dòng)化技術(shù)（EtherCAT,Ethernetcontrol automation technology）和串行實(shí)時(shí)通信系統(tǒng)（SERCOS,serial real time communication system）——SERCOSIII 等。但是，不同體系下的網(wǎng)絡(luò)技術(shù)出現(xiàn)了不兼容、難移植、互操作性差等問題。在日益增長(zhǎng)的確定性網(wǎng)絡(luò)標(biāo)準(zhǔn)化需求的驅(qū)動(dòng)下，IEEE 時(shí)間敏感網(wǎng)絡(luò)（TSN,time-sensitive networking）工作組正在研究關(guān)鍵機(jī)制的標(biāo)準(zhǔn)化，提出了一系列鏈路層增強(qiáng)機(jī)制的標(biāo)準(zhǔn)和規(guī)范。

已發(fā)布的標(biāo)準(zhǔn) IEEE 802.1Qbv[3]和 IEEE 802.1Qch[4]用于解決標(biāo)準(zhǔn)以太網(wǎng)中不確定性排隊(duì)時(shí)延的問題。基于IEEE 802.1Qbv 的時(shí)間感知整形器（TAS,time-aware shaper）能夠?qū)崿F(xiàn)微秒級(jí)逐跳逐包的細(xì)粒度調(diào)度，TAS 需要為交換機(jī)中每個(gè)隊(duì)列附加的門控列表（GCL,gate control list）進(jìn)行配置。但是調(diào)度算法的運(yùn)算復(fù)雜度很高，網(wǎng)絡(luò)的任何變化都會(huì)導(dǎo)致GCL 重新計(jì)算和配置。為了簡(jiǎn)化TSN 交換機(jī)的設(shè)計(jì)，IEEE 802.1 Qch 標(biāo)準(zhǔn)基于TAS 提出了一種名為循環(huán)排隊(duì)和轉(zhuǎn)發(fā)（CQF,cyclic queuing and forwarding）的易用模型，也稱蠕動(dòng)整形器。CQF 提供確定性且易于計(jì)算時(shí)延的時(shí)間敏感流量調(diào)度，不需要復(fù)雜的配置，TSN 的實(shí)現(xiàn)與管理復(fù)雜度大大降低，因此，CQF 已經(jīng)成為TSN 中高選擇的整形器[5]。

要充分挖掘TSN 的確定性傳輸能力，流量調(diào)度在保證實(shí)時(shí)傳輸、確定性傳輸中起著重要的作用，確定每個(gè)數(shù)據(jù)幀在交換機(jī)出端口的傳輸時(shí)隙，保證所有數(shù)據(jù)幀無沖突共網(wǎng)傳輸。研究人員對(duì)此進(jìn)行了大量研究探索，目前，CQF 的工作通過啟發(fā)式的輕量級(jí)簡(jiǎn)單規(guī)劃，將隊(duì)列長(zhǎng)度和硬件調(diào)度時(shí)隙作為資源常數(shù)值參與調(diào)度規(guī)劃的計(jì)算[6-7]。對(duì)于隊(duì)列與時(shí)隙的貪心式占用方法，流量容易在隊(duì)列的同一接收時(shí)隙匯集，出現(xiàn)隊(duì)列負(fù)載不均的問題。

基于上述問題，本文設(shè)計(jì)了一種基于混合整數(shù)線性規(guī)劃優(yōu)化的路由與調(diào)度模型。首先，提出了基于網(wǎng)絡(luò)與流量多屬性特征的硬件時(shí)隙自適應(yīng)（AHTS,adaptive hardware time slot）生成調(diào)度算法；然后，將計(jì)算出的隊(duì)列長(zhǎng)度和硬件調(diào)度時(shí)隙作為混合整數(shù)線性規(guī)劃與逐流調(diào)度的流量注入時(shí)隙規(guī)劃（MILP_FITP,mixed integer linear programming flow injection time planning）算法的輸入來求解調(diào)度方案，MILP_FITP 算法應(yīng)具有以下特性。

1) 有界時(shí)延。算法滿足有界隊(duì)列長(zhǎng)度約束，并在要求的期限內(nèi)將時(shí)間敏感流傳輸?shù)侥康牡亍?/p>

2) 高可調(diào)度性。算法具有高網(wǎng)絡(luò)可調(diào)度性，在時(shí)間敏感網(wǎng)絡(luò)中可調(diào)度數(shù)千個(gè)時(shí)間敏感流，并且保持較高的網(wǎng)絡(luò)調(diào)度成功率。

3) 調(diào)度順序獨(dú)立。算法不完全依賴于待調(diào)度流量的先后順序，在全局范圍內(nèi)完成規(guī)劃與映射。

4) 端口隊(duì)列長(zhǎng)度自適應(yīng)性。隊(duì)列長(zhǎng)度在滿足傳輸需求的同時(shí)應(yīng)相對(duì)較小，降低實(shí)現(xiàn)難度與硬件成本，在減小調(diào)度粒度的同時(shí)考慮運(yùn)算時(shí)間。

5) 可行的執(zhí)行時(shí)間。算法針對(duì)離線階段最大化成功映射到目標(biāo)網(wǎng)絡(luò)上的時(shí)間敏感流的數(shù)量，均衡每個(gè)時(shí)隙所承載流量負(fù)載以提高調(diào)度方案的擴(kuò)展能力，因此要求運(yùn)算時(shí)間低于動(dòng)態(tài)規(guī)劃階段的調(diào)度規(guī)劃算法。解決方案應(yīng)該具有可接受的算法執(zhí)行時(shí)間和高質(zhì)量求解結(jié)果。

本文主要的研究工作如下。

1) 基于軟件定義網(wǎng)絡(luò)架構(gòu)和循環(huán)隊(duì)列與轉(zhuǎn)發(fā)機(jī)制，在TSN 中開展數(shù)據(jù)流的全局路徑規(guī)劃、隊(duì)列規(guī)劃與時(shí)隙分配的聯(lián)合調(diào)度，實(shí)現(xiàn)局域網(wǎng)中流量的自動(dòng)化控制與調(diào)度。

2) 提出了網(wǎng)絡(luò)與流量多屬性特征的硬件調(diào)度時(shí)隙自適應(yīng)生成算法，實(shí)現(xiàn)隊(duì)列長(zhǎng)度與硬件調(diào)度時(shí)隙的自適應(yīng)配置，以實(shí)現(xiàn)調(diào)度粒度與運(yùn)算時(shí)間的平衡，提高網(wǎng)絡(luò)的調(diào)度能力。

3) 提出了MILP_FITP 算法分別對(duì)端到端截止時(shí)間要求高的流量進(jìn)行逐流調(diào)度，對(duì)多偏移量可選擇的流量的混合整數(shù)規(guī)劃模型進(jìn)行規(guī)模縮減以加快求解速度，通過均衡資源利用進(jìn)一步提升網(wǎng)絡(luò)的可調(diào)度性。

4) 仿真結(jié)果表明，所提算法具有很好的網(wǎng)絡(luò)調(diào)度和資源利用率性能，具有可行的執(zhí)行時(shí)間。與按流順序逐時(shí)隙調(diào)度（FJ-FO,flow injection by flow order）方法、按流順序隨機(jī)時(shí)隙調(diào)度（FJ-random,flow injection by random）方法、基于特定領(lǐng)域知識(shí)的禁忌搜索啟發(fā)式（Tabu-ITP-change,Tabu-injection time planning in exchanging mode）算法和基于一次性分配結(jié)果的偏移調(diào)整注入（FO-CS,flow offset and cycle shift）方法對(duì)比，驗(yàn)證了所提算法的有效性。

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

1.1 CQF 調(diào)度機(jī)制

循環(huán)排隊(duì)與轉(zhuǎn)發(fā)傳輸示意如圖1(a)所示。CQF 將一個(gè)輸出端口的發(fā)送時(shí)間分為一系列相等的時(shí)間間隔，每個(gè)時(shí)間間隔被稱為一個(gè)周期，持續(xù)時(shí)間為L(zhǎng)slot。循環(huán)排隊(duì)與轉(zhuǎn)發(fā)隊(duì)列示意如圖1(b)所示。CQF 通過利用2 個(gè)交替執(zhí)行入隊(duì)和退隊(duì)操作的隊(duì)列，保證奇隊(duì)列中的一個(gè)數(shù)據(jù)包在奇周期循環(huán)內(nèi)從上游節(jié)點(diǎn)發(fā)送，并在同一周期內(nèi)被下游節(jié)點(diǎn)接收并緩存到偶隊(duì)列中，偶周期循環(huán)中情況則相反。因此，端到端的時(shí)延只取決于循環(huán)長(zhǎng)度和路徑跳數(shù)H，最大時(shí)延約束為(H+1)Lslot，最小時(shí)延約束為(H-1)Lslot，有2Lslot的抖動(dòng)，提供了確定性的排隊(duì)和轉(zhuǎn)發(fā)。同時(shí)，其他類型的流轉(zhuǎn)發(fā)與時(shí)隙無關(guān)，圖1(a)中淺灰色長(zhǎng)方形表示盡為而為（BE,best effort）流，它們可以在未被完全規(guī)劃的時(shí)隙內(nèi)進(jìn)行節(jié)點(diǎn)之間的傳輸以提高帶寬利用率；ES 表示網(wǎng)絡(luò)中的端系統(tǒng)；SW 表示TSN 交換機(jī)；τ表示一個(gè)硬件調(diào)度時(shí)隙。圖1(b)中Q 表示優(yōu)先級(jí)隊(duì)列。

圖1 循環(huán)排隊(duì)與轉(zhuǎn)發(fā)機(jī)制示意

1.2 相關(guān)工作

流調(diào)度計(jì)算本身是一個(gè)復(fù)雜的問題，它已經(jīng)被證明是一個(gè)NP-hard 問題。TSN 中基于IEEE 802.1 Qbv 的TAS 模型對(duì)應(yīng)的調(diào)度算法通常從2 個(gè)方面進(jìn)行無沖突規(guī)劃：空間隔離與時(shí)間隔離。空間隔離主要體現(xiàn)在路由算法，即為每條流選擇一條傳輸路徑。時(shí)間隔離主要體現(xiàn)在調(diào)度方法，即控制數(shù)據(jù)幀在何時(shí)發(fā)送出去。路由子問題的優(yōu)化目標(biāo)傳統(tǒng)上基于最短路徑算法，理論上單一流可以實(shí)現(xiàn)從源到目的端的最快調(diào)度，然而，Laursen 等[8]已證明SP 算法對(duì)于TSN 來說并不是最佳路由算法，因?yàn)榇罅苛髁靠赡軙?huì)因使用相同或部分相同路徑而出現(xiàn)調(diào)度瓶頸，導(dǎo)致網(wǎng)絡(luò)不可調(diào)度?；诓煌瑑?yōu)化目標(biāo)的啟發(fā)式算法被提出，例如，文獻(xiàn)[9]提出了基于遺傳算法的啟發(fā)式路由與算法，主要目標(biāo)是滿足流的最后截止期限，該算法結(jié)合了路由和調(diào)度約束，使用聯(lián)合約束生成靜態(tài)全局調(diào)度；文獻(xiàn)[10]引入了啟發(fā)式列表調(diào)度器，在一個(gè)步驟中使用聯(lián)合路由和調(diào)度約束生成有效的調(diào)度以實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的負(fù)載平衡；文獻(xiàn)[11]提出了一種混合遺傳算法的設(shè)計(jì)方法，包括TSN 中路由和調(diào)度問題的染色體表示、遺傳算子的選擇以及鄰域搜索，以找到接近最優(yōu)的網(wǎng)絡(luò)負(fù)載平衡的解決方案；文獻(xiàn)[12]基于啟發(fā)式K最短路徑啟發(fā)式方法與基于貪婪隨機(jī)自適應(yīng)搜索過程的元啟發(fā)式算法來解決時(shí)間觸發(fā)的聯(lián)合路由和調(diào)度問題，最小化使用隊(duì)列的數(shù)量以及流的端到端時(shí)延。

可滿足性模理論（SMT,satisfiability modulo theories）[13-15]和整數(shù)線性規(guī)劃（ILP,integer linear programming）[16-19]數(shù)學(xué)理論可以用來解決路由和調(diào)度問題，通過建立網(wǎng)絡(luò)與流量的關(guān)鍵約束求解滿足要求的路由規(guī)劃與調(diào)度方案。文獻(xiàn)[20]使用一階邏輯約束來定義調(diào)度問題，分別調(diào)用SMT 和MIP 求解器，在有和沒有優(yōu)化目標(biāo)的情況下求解方案。文獻(xiàn)[21]提出了分組調(diào)度機(jī)制，建立路由和調(diào)度的整數(shù)線性規(guī)劃模型，通過拓?fù)湫藜艉突谧V聚類的流分組策略縮小約束的規(guī)模，在較短時(shí)間內(nèi)進(jìn)行模型的求解，保證一定的調(diào)度成功率。文獻(xiàn)[22]提出沖突程度感知流分區(qū)多路徑路由技術(shù)和基于迭代整數(shù)線性規(guī)劃的可伸縮性調(diào)度技術(shù)提高調(diào)度成功率和容錯(cuò)性。文獻(xiàn)[23]建立了一種新的無沖突網(wǎng)絡(luò)更新的ILP 調(diào)度模型，保證了網(wǎng)絡(luò)更新中沒有幀損失，也沒有引入額外的更新時(shí)間。

ITP（injection time planning）算法[6]通過將循環(huán)流的注入時(shí)間映射到隊(duì)列資源來實(shí)現(xiàn)CQF，簡(jiǎn)化了GCL 的配置，通過隨機(jī)交換調(diào)度成功的流量集合與調(diào)度失敗的流量集合以提高調(diào)度成功率，得到近似優(yōu)化解，但未考慮不同場(chǎng)景下隊(duì)列長(zhǎng)度與硬件調(diào)度時(shí)隙對(duì)調(diào)度性能的影響。文獻(xiàn)[7]在ITP 的約束模型下提出了在線流注入時(shí)間調(diào)度算法，根據(jù)網(wǎng)絡(luò)資源利用率調(diào)整網(wǎng)絡(luò)適配器上的發(fā)送時(shí)間，為新的時(shí)間敏感流增量生成流量調(diào)度，不需要重新配置先前規(guī)劃，實(shí)現(xiàn)了快速調(diào)度。

綜上所述，現(xiàn)有的優(yōu)化算法分別采用啟發(fā)式算法、元啟發(fā)式算法以及整數(shù)規(guī)劃求解算法求解近似最優(yōu)調(diào)度規(guī)劃，求解速度依次遞減，求解質(zhì)量依次遞增。現(xiàn)有的CQF 調(diào)度機(jī)制采用逐流調(diào)度方式和啟發(fā)式算法為網(wǎng)絡(luò)實(shí)現(xiàn)一個(gè)可用的規(guī)劃，網(wǎng)絡(luò)調(diào)度成功率有待提高，且算法的優(yōu)化解與最優(yōu)解未進(jìn)行對(duì)比。為此，本文針對(duì)局域網(wǎng)絡(luò)中的時(shí)間敏感流量大規(guī)模調(diào)度問題，提出了基于CQF 整形機(jī)制的聯(lián)合路由與調(diào)度優(yōu)化的全局規(guī)劃加速生成算法，保證流量的有界時(shí)延、網(wǎng)絡(luò)高可調(diào)度性、調(diào)度獨(dú)立性與可接受的執(zhí)行時(shí)間。

2 數(shù)學(xué)模型

TSN 架構(gòu)如圖2 所示。支持CQF 整形機(jī)制的TSN 架構(gòu)基于IEEE 802.1Qcc[24]所提出的全集中式控制架構(gòu)的控制配置模型，通過一個(gè)中心化用戶配置節(jié)點(diǎn)與終端用戶之間交換用戶需求。用戶網(wǎng)絡(luò)接口（UNI,user network interface）位于中心化用戶配置（CUC,centralized user configuration）與中心化網(wǎng)絡(luò)配置（CNC,centralized network configuration）之間。CUC 收集數(shù)據(jù)平面中網(wǎng)絡(luò)拓?fù)?、流特征以及用戶需求，并將用戶需求傳達(dá)給CNC，控制面從全局資源視角將網(wǎng)絡(luò)資源與流特征作為調(diào)度算法的輸入，計(jì)算出滿足傳輸要求的配置并下發(fā)給各個(gè)設(shè)備。隨后，數(shù)據(jù)平面設(shè)備根據(jù)收到的配置來自動(dòng)控制數(shù)據(jù)包的發(fā)送、緩存與轉(zhuǎn)發(fā)。

圖2 TSN 架構(gòu)

TSN 被建模為有向圖G=(V,E)，其中，V=ES ∪SW 是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合；E?V×V表示2 個(gè)節(jié)點(diǎn)之間有一條全雙工鏈路，每一條全雙工鏈路都可以被2 個(gè)方向的邏輯鏈路表示為(vi,vj)和(v j,vi)，其中前面的元素表示源端系統(tǒng)，后面的元素表示目標(biāo)端系統(tǒng)；分別表示網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)和鏈路數(shù)。支持CQF 機(jī)制的TSN 交換機(jī)結(jié)構(gòu)如圖3 所示。交換機(jī)支持U個(gè)輸入/輸出端口，每個(gè)端口支持8 個(gè)輸出隊(duì)列。IEEE 802.1Q[25]標(biāo)準(zhǔn)封裝了虛擬局域網(wǎng)數(shù)據(jù)幀格式，以太網(wǎng)報(bào)頭中的優(yōu)先權(quán)代碼點(diǎn)（PCP,priority code point）字段標(biāo)記了數(shù)據(jù)流的優(yōu)先級(jí)。兩隊(duì)列用于時(shí)間敏感流的排隊(duì)轉(zhuǎn)發(fā)，在奇偶周期交替打開隊(duì)列6 和隊(duì)列7。

圖3 支持CQF 機(jī)制的TSN 交換機(jī)結(jié)構(gòu)

時(shí)間關(guān)鍵型應(yīng)用被建模為周期性流量，每個(gè)流量都在其周期內(nèi)傳輸?？紤]一組K個(gè)周期性單播時(shí)間敏感流集合F={f 1,f2,…,fk,…,fK}，為了簡(jiǎn)化，多播的情況可以被分割成具有相同源和不同目的地的多個(gè)單播流。每個(gè)流由源端系統(tǒng)、目標(biāo)端系統(tǒng)、幀長(zhǎng)度、流量周期、允許的最大端到端時(shí)延、有序的傳輸路徑和流量注入網(wǎng)絡(luò)時(shí)隙的七元組來定義，即

其中，f k.route 和f k.φ分別由路由算法和調(diào)度算法生成后配置。系統(tǒng)參數(shù)如表1 所示。

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

3 問題描述

在本文中，對(duì)于給定網(wǎng)絡(luò)拓?fù)浜土髁考?，求解的流路由與調(diào)度方案需要滿足以下約束。

1) 路由約束

如果節(jié)點(diǎn)vi是流fk的源節(jié)點(diǎn)，則

如果節(jié)點(diǎn)vi是流fk的目的節(jié)點(diǎn)，則

如果節(jié)點(diǎn)vi是流fk流經(jīng)路徑的中間節(jié)點(diǎn)，則

為了防止出現(xiàn)循環(huán)路由同一個(gè)節(jié)點(diǎn)的情況，對(duì)于流fk的每條預(yù)留鏈路最多僅可訪問一次，即

2) 調(diào)度約束

與調(diào)度問題相關(guān)的CQF 隊(duì)列長(zhǎng)度、硬件調(diào)度時(shí)隙和交換機(jī)出端口的調(diào)度周期分別表示為L(zhǎng)queue、Lslot和Tschedule。對(duì)于不同時(shí)間生成的流量，通過注入網(wǎng)絡(luò)時(shí)間的規(guī)劃實(shí)現(xiàn)對(duì)TSN 的高效調(diào)度。

①流量的時(shí)延注入時(shí)間約束

假設(shè)所有的流都在零參考時(shí)間開始計(jì)算流的偏移量，為了使流量可以按門控列表周期性地進(jìn)行有序傳輸，需要保證時(shí)間敏感流在它本身的周期內(nèi)發(fā)送出去，不會(huì)與流量下個(gè)周期的數(shù)據(jù)幀發(fā)生沖突，即

② 交換機(jī)的接收窗口約束

該約束是用來檢查數(shù)據(jù)包是否在窗口右端內(nèi)到達(dá)，理論上如果硬件調(diào)度時(shí)隙滿足最小時(shí)隙約束，則所有數(shù)據(jù)包都會(huì)滿足該約束。對(duì)于任意時(shí)間敏感流fk在每一跳的接收時(shí)隙為

③流量的截止時(shí)間約束

為了保障時(shí)間敏感流的有界低時(shí)延傳輸，流的所有數(shù)據(jù)包要在指定時(shí)間之前到達(dá)目標(biāo)端系統(tǒng)，即

④ 交換機(jī)隊(duì)列資源約束

TSN 交換機(jī)中隊(duì)列的緩存容量有限，在每個(gè)時(shí)隙中隊(duì)列緩存的數(shù)據(jù)包總大小不能超過緩存大小，數(shù)據(jù)流fk在鏈路上所占用的時(shí)隙可表示為

對(duì)于某個(gè)端口的任意時(shí)隙，端口傳輸?shù)牧鞯目偞笮〔粦?yīng)超過隊(duì)列緩存大小，否則隊(duì)列溢出，即

3) 硬件調(diào)度時(shí)隙約束硬件的調(diào)度粒度為一個(gè)時(shí)隙，所有流量周期都應(yīng)被預(yù)定義的Lslot整除。最大時(shí)隙約束是所有流量周期的最大公約數(shù)（GCD,greatest common divisor），根據(jù)流量周期特征獲得的時(shí)隙上界為

CQF 標(biāo)準(zhǔn)規(guī)定數(shù)據(jù)包在相鄰2 個(gè)節(jié)點(diǎn)的發(fā)送時(shí)隙和接收時(shí)隙相同，則最小時(shí)隙需要保證隊(duì)列中的所有數(shù)據(jù)包在相同的時(shí)隙內(nèi)從上游節(jié)點(diǎn)傳輸?shù)较掠喂?jié)點(diǎn)，時(shí)隙的下界約束為

其中，BW 為鏈路的發(fā)送速率；thop_delay為交換機(jī)的每跳固定時(shí)延，包括處理時(shí)延和傳播時(shí)延；tsync_proc為時(shí)鐘的同步精度。

考慮數(shù)據(jù)流最大容忍時(shí)延需求和網(wǎng)絡(luò)特點(diǎn)，基于流量完全調(diào)度的要求，截止時(shí)間要求最高的流量有規(guī)定時(shí)間內(nèi)送達(dá)的約束對(duì)硬件調(diào)度時(shí)隙有上界要求，表示為

其中，Hmax表示深度優(yōu)先搜索方法得到網(wǎng)絡(luò)的最長(zhǎng)路徑，Dmin表示流量集中流量DDL 的最小值。如果小于時(shí)隙的下界值，則認(rèn)為該流量無法在網(wǎng)絡(luò)中調(diào)度；否則作為硬件調(diào)度時(shí)隙上界約束。

4 算法提出

在標(biāo)準(zhǔn)以太網(wǎng)交換機(jī)中，數(shù)據(jù)包存儲(chǔ)在緩沖池中，而隊(duì)列用于存儲(chǔ)數(shù)據(jù)包的元數(shù)據(jù)以進(jìn)行調(diào)度。因此，交換機(jī)中的最大隊(duì)列長(zhǎng)度等于緩沖池中數(shù)據(jù)包緩沖區(qū)的數(shù)量。端系統(tǒng)為避免占用過多的緩存空間會(huì)在數(shù)據(jù)產(chǎn)生后立即發(fā)送，如果沒有嚴(yán)格且詳細(xì)的發(fā)送時(shí)間規(guī)劃，流量很容易集中到隊(duì)列的部分時(shí)隙中轉(zhuǎn)發(fā)。由于隊(duì)列長(zhǎng)度是有限的，一旦數(shù)據(jù)量超過緩存大小，會(huì)出現(xiàn)隊(duì)列溢出，導(dǎo)致數(shù)據(jù)包被丟棄。實(shí)際上，可以通過時(shí)延流的發(fā)送時(shí)隙來緩解此問題，從而使隊(duì)列的時(shí)隙利用更加平衡。但是當(dāng)流注入網(wǎng)絡(luò)的偏移量過大時(shí)，終端需要緩存大量的數(shù)據(jù)包，耗費(fèi)大量的存儲(chǔ)空間，這將限制終端的發(fā)包數(shù)量和種類。根據(jù)以上分析，在設(shè)計(jì)調(diào)度算法時(shí)主要需要解決以下2 個(gè)問題。

1) 基于流特征、網(wǎng)絡(luò)規(guī)模和流量規(guī)模確定硬件時(shí)隙長(zhǎng)度和緩存隊(duì)列長(zhǎng)度

從調(diào)度模型分析，Lslot與流的周期屬性、截止時(shí)間屬性、鏈路速率、交換機(jī)緩存隊(duì)列長(zhǎng)度、網(wǎng)絡(luò)規(guī)模等因素相關(guān)，交換機(jī)緩存隊(duì)列長(zhǎng)度的增加在一定程度上會(huì)增加Lslot的下界值。文獻(xiàn)[6-7]表明，Lqueue增加會(huì)使所容納的數(shù)據(jù)包會(huì)增加，可調(diào)度的流數(shù)也增加。然而，上一時(shí)隙緩存的數(shù)據(jù)包必須在下一時(shí)隙全部發(fā)送這一約束將增加數(shù)據(jù)流的單跳時(shí)延，經(jīng)過路徑累積會(huì)增加數(shù)據(jù)流的端到端總時(shí)延，導(dǎo)致流量不可調(diào)度。受到底層硬件資源的限制，Lqueue增加會(huì)使交換機(jī)的內(nèi)存需求增大，交換機(jī)的實(shí)現(xiàn)難度和成本也會(huì)增加。更重要的是，門控的控制精度與Lslot成反比，在給定流量周期的情況下，源端系統(tǒng)可選擇的注入偏移隨Lslot減少會(huì)增加，在提升控制精度的同時(shí)會(huì)增加搜索空間。Lslot的大小受到鏈路帶寬的約束，如果預(yù)留的時(shí)間遠(yuǎn)超過隊(duì)列緩存所需要的發(fā)送時(shí)間，剩余時(shí)隙將會(huì)出現(xiàn)無數(shù)據(jù)傳輸?shù)那闆r。因此，硬件調(diào)度時(shí)隙Lslot對(duì)基于CQF 機(jī)制的網(wǎng)絡(luò)傳輸性能產(chǎn)生重要的影響。

在算法1 中，基于硬件調(diào)度時(shí)隙約束計(jì)算得到Lslot的上下界，當(dāng)給定的Lqueue過大時(shí)，生成的硬件調(diào)度時(shí)隙下界值過大，Lslot不能整除所有數(shù)據(jù)流的周期，則不能保證流量集合F的調(diào)度（1)～2)行）。算法以MTU 的幅度進(jìn)行調(diào)節(jié)，以保證數(shù)據(jù)傳輸?shù)目烧{(diào)度性與完整性（3)～5)行）。檢查在交換機(jī)緩存隊(duì)列長(zhǎng)度最低門限下的硬件調(diào)度時(shí)隙范圍是否滿足流量的截止時(shí)間屬性，將可能不可調(diào)度的流移入集合Fddl（6)～12)行）。如果調(diào)整后的CQF 緩存隊(duì)列長(zhǎng)度大于最低閾值，則利用優(yōu)化器對(duì)硬件調(diào)度時(shí)隙進(jìn)行整數(shù)規(guī)劃優(yōu)化（13)～22)行）。為了平衡調(diào)度控制粒度和調(diào)度時(shí)間敏感流的數(shù)量，在模型中引入時(shí)間敏感流的帶寬利用比例閾值β，剩余部分可供給其他類型流量利用，也可以作為提供因同步時(shí)間精度不夠所溢出的數(shù)據(jù)幀的余量時(shí)隙長(zhǎng)度以供動(dòng)態(tài)調(diào)整。最后利用優(yōu)化的硬件調(diào)度時(shí)隙篩選出可能不可調(diào)度的流移入集合Fddl，更新待調(diào)度流量集合F*（23)～24)行）。

2) 進(jìn)行合理的時(shí)間敏感流路由與注入時(shí)間映射

基于路由約束式(1)～式(4)和調(diào)度約束式(5)～式(9)，構(gòu)建聯(lián)合路由和調(diào)度問題為混合整數(shù)線性規(guī)劃，考慮均衡分配流量占用的路徑與時(shí)隙，以最大化可調(diào)度流量數(shù)量，最小化繁忙鏈路隊(duì)列利用率為目標(biāo)，獲得最優(yōu)的流量路由與時(shí)隙偏移分配策略。CQF-TSN 調(diào)度問題可以表述為以下MILP 問題。

CQF-TSN 問題搜索空間的指數(shù)增加主要來自以下兩方面：每個(gè)流量可用路徑的數(shù)量和注入網(wǎng)絡(luò)偏移量的數(shù)量。除了從底層拓?fù)淠Ｐ蜕峡梢钥s減模型、減少變量與約束的數(shù)量，還可以優(yōu)化ILP 生成過程本身，通過減少ILP 產(chǎn)生的不必要的輔助變量，減少M(fèi)ILP 端變量的數(shù)量以及變量的邊界范圍，從而減少搜索空間以降低MILP 的復(fù)雜度。

路由問題可以拆分為2 個(gè)子問題：路由生成和路由選擇。對(duì)每個(gè)流fk生成一組可用路由集合，然后引入決策變量做出一個(gè)上層決策，如果流fk通過路徑pk從源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)，則否則

對(duì)于任意流fk給定的一組路徑按照流量截止時(shí)間要求升序排序，將前的流量選擇最短的路徑。定義路徑pk的負(fù)載加權(quán)和為

流量注入網(wǎng)絡(luò)偏移量的可選數(shù)量由流量周期與硬件調(diào)度時(shí)隙相關(guān)，搜索空間為，其中，K表示待調(diào)度流的數(shù)目。算法1 基于流量特征及網(wǎng)絡(luò)規(guī)模將流量分為待調(diào)度的流量集合*F與可能不可調(diào)度流量集合Fddl，*F作為混合整數(shù)規(guī)劃的輸入，F(xiàn)ddl將采用增量式逐流調(diào)度選擇路徑鏈路最繁忙時(shí)隙的帶寬占用率低的時(shí)隙注入網(wǎng)絡(luò)。定義鏈路e最繁忙時(shí)隙的帶寬占用率為

為了進(jìn)一步縮減偏移量的搜索規(guī)模，待調(diào)度的流量集合F*按截止時(shí)間要求升序排序，流集合可偏移范圍小于后半部分由于截止時(shí)間大的流量可調(diào)整范圍較大，這部分流量應(yīng)盡可能利用較大偏移量時(shí)隙對(duì)應(yīng)的緩存，將小偏移量的時(shí)隙緩存留給集合中的流量，因此在約束條件中，從流量隨機(jī)選取50%的流量提高偏移量選擇下限為

在算法2 中，首先將待調(diào)度的流量集合F*時(shí)間要求升序排序，然后基于DDL 順序完成路由生成與選擇（1)～6)行）?；谟布{(diào)度時(shí)隙和路由結(jié)果設(shè)置變量、更新變量空間、設(shè)置目標(biāo)函數(shù)、設(shè)置約束條件和完成優(yōu)化調(diào)度（7)～20)行）。完成計(jì)算密集型的精確優(yōu)化之后，如果得到優(yōu)化解，依次對(duì)Fddl中的流量進(jìn)行調(diào)度（21)～37)行），對(duì)于注入偏移時(shí)隙調(diào)整范圍內(nèi)的任意時(shí)隙off，checkConstr(off)需要保證其截止時(shí)間約束滿足式(7)，checkSlot(off)同時(shí)保證在流量注入后該流路徑上的所有出端口對(duì)應(yīng)的緩存隊(duì)列不存在溢出問題，滿足交換機(jī)隊(duì)列資源約束式(9)。off_option 包含所有滿足條件的注入偏移時(shí)隙選擇。為了均衡每個(gè)時(shí)隙所承載流量負(fù)載，基于式(15)為路徑所包含的鏈路e計(jì)算最繁忙時(shí)隙的帶寬占用率，并選擇資源利用率最小的注入偏移時(shí)隙。如果未得到優(yōu)化解，則模型設(shè)置的計(jì)算時(shí)間太小或模型不可調(diào)度。

5 仿真實(shí)驗(yàn)和結(jié)果分析

仿真在Python 的框架下完成，使用networkx 對(duì)網(wǎng)絡(luò)建模并生成不同的流量集。所有的MILP 實(shí)例都在Gurobi 優(yōu)化器（9.5.1 版）中求解，求解器超時(shí)時(shí)間設(shè)置為1 200 s。硬件配置為i7-8750H CPU，運(yùn)行頻率為2.20 GHz，內(nèi)存為8 GB。為驗(yàn)證MILP_FITP算法的性能，將其與FJ-FO 算法、FJ-random 算法，Tabu-ITP-change 算法[6]和FO-CS 算法[26]進(jìn)行了對(duì)比，禁忌表長(zhǎng)度為500，交換概率為0.7。所對(duì)比的調(diào)度算法均基于最短路徑算法計(jì)算得到的路由結(jié)果。

5.1 參數(shù)設(shè)置

設(shè)置鏈路帶寬為1 Gbit/s，網(wǎng)絡(luò)最大傳輸單位MTU=1 500 B。網(wǎng)絡(luò)拓?fù)淙鐖D4 所示，這些拓?fù)鋷缀蹩梢员唤M裝到所有的工業(yè)網(wǎng)絡(luò)結(jié)構(gòu)中。

圖4 網(wǎng)絡(luò)拓?fù)?/p>

流量周期和截止時(shí)間的單位為μs，截止時(shí)間包含2 種模型，即和與網(wǎng)絡(luò)規(guī)模、硬件調(diào)度時(shí)隙無關(guān)的模型其中，η為時(shí)延系數(shù)，無特殊說明則η=0.4。流的源端系統(tǒng)和目標(biāo)端系統(tǒng)從網(wǎng)絡(luò)中的端系統(tǒng)中任意生成一對(duì)，隊(duì)列緩存最低門限設(shè)置為3MTU，帶寬利用比例閾值β=0.9。所對(duì)比的調(diào)度算法基于固定的隊(duì)列長(zhǎng)度和硬件調(diào)度時(shí)隙，實(shí)驗(yàn)參數(shù)如表2 所示。

表2 實(shí)驗(yàn)參數(shù)

5.2 評(píng)估指標(biāo)

評(píng)估算法性能由以下幾個(gè)指標(biāo)完成。

1) 映射流數(shù)量，給定仿真網(wǎng)絡(luò)中的流參數(shù)，滿足所有約束成功調(diào)度流的數(shù)量。

2) 網(wǎng)絡(luò)調(diào)度成功率，表示滿足所有約束的求解方案的實(shí)驗(yàn)次數(shù)與總實(shí)驗(yàn)次數(shù)的比值。

3) 已用鏈路平均隊(duì)列時(shí)隙資源利用率（RU_U），表示實(shí)際分配流量的隊(duì)列時(shí)隙資源占已用隊(duì)列時(shí)隙資源的比例。

4) 可用鏈路平均隊(duì)列時(shí)隙資源利用率（RU_A），表示理論上分配給流量的隊(duì)列時(shí)隙資源占所有可用端口（不包括連接到主機(jī)的端口）隊(duì)列的比例。

5) 運(yùn)行時(shí)間，表示算法完成所有流量調(diào)度所需要的時(shí)間，單位為s。

5.3 仿真結(jié)果分析

1) 注入時(shí)隙方法

在MILP_FITP 算法中，優(yōu)化目標(biāo)是均衡時(shí)隙帶寬占有率以緩解調(diào)度瓶頸，提高流量調(diào)度成功率。為驗(yàn)證算法的有效性，本文與4 種算法進(jìn)行對(duì)比，網(wǎng)絡(luò)拓?fù)錇榫€性拓?fù)?，發(fā)包周期從中隨機(jī)選取，為了排除隊(duì)列長(zhǎng)度和硬件調(diào)度時(shí)隙的影響，MILP_FITP 算法采用表2 所示的固定配置。對(duì)比不同流量注入方案對(duì)成功映射流量數(shù)量和平均時(shí)隙帶寬占有率的影響，仿真結(jié)果如圖5 所示。

在固定配置下，MILP_FITP 算法精確求解后網(wǎng)絡(luò)調(diào)度成功率達(dá)100%時(shí)最多調(diào)度2 000 條流量，因此圖5(a)中MILP_FITP 算法僅保留了250～2 000 條流量的仿真結(jié)果，隨著待調(diào)度流量數(shù)量增加，MILP_FITP 算法對(duì)比其他算法的改進(jìn)增大，待調(diào)度流量數(shù)量為2 000 時(shí)對(duì)比FJ-FO 算法達(dá)到28%。

圖5 不同注入方案對(duì)算法的影響

在相同隊(duì)列與硬件調(diào)度時(shí)隙配置下，圖5(b)對(duì)比了不同算法的資源利用情況，仿真網(wǎng)絡(luò)中存在2 000 條流量，RU_A 與RU_U 越接近代表隊(duì)列時(shí)隙資源的實(shí)際占用越平均。由于逐流順序調(diào)度算法（FJ-FO 和FO-CS）映射流數(shù)量較少，理論上的資源利用率會(huì)比其他3 種算法低。FJ-random 算法隨機(jī)搜索未考慮帶寬利用率，雖然映射流數(shù)量有所增加，但是資源利用率與實(shí)際占用的資源利用率差值與FJ-FO 和FO-CS 相似。由于一些時(shí)隙在約束內(nèi)可以使用，比如連接到端系統(tǒng)的交換機(jī)的第零時(shí)隙，但實(shí)際上沒有數(shù)據(jù)包待轉(zhuǎn)發(fā)，因此RU_A＜RU_U。Tabu-ITP-change 算法基于流密度對(duì)流進(jìn)行交換優(yōu)化，一定程度上均衡了資源利用，但是啟發(fā)類算法為了平衡求解質(zhì)量與收斂速度，優(yōu)化程度低于MILP_FITP 算法。

時(shí)間成本與算法關(guān)系如圖5(c)所示，F(xiàn)O-CS 與FJ-FO 算法的解質(zhì)量相近，F(xiàn)J-FO 解質(zhì)量相較更優(yōu)但時(shí)間成本高于FO-CS。FJ-random 算法解質(zhì)量適中，時(shí)間成本最低，但未考慮資源利用問題，部分時(shí)隙資源滿載后調(diào)度無法調(diào)度。Tabu-ITP-change 算法在低負(fù)載下很小的迭代后收斂得到較優(yōu)解，時(shí)間成本低，但是隨著流量增加，計(jì)算密集型的啟發(fā)式算法的求解時(shí)間很高。

2) 流調(diào)度順序

考慮流周期、流的截止時(shí)間、數(shù)據(jù)包長(zhǎng)度，將待調(diào)度流集合按單個(gè)因素排序后調(diào)用調(diào)度算法。網(wǎng)絡(luò)拓?fù)錇榄h(huán)形拓?fù)?，仿真網(wǎng)絡(luò)中存在2 000 條時(shí)間敏感流，流的截止時(shí)間采用 2 種模型，發(fā)包周期從中隨機(jī)抽取。為了排除隊(duì)列長(zhǎng)度和硬件調(diào)度時(shí)隙的影響，MILP_FITP 算法采用表2 所示的固定配置，對(duì)比不同流排序方案對(duì)流映射數(shù)量的影響，仿真結(jié)果如圖6 所示，橫坐標(biāo)表示排序原則，分別為不排序（no sort）、按流周期升序排序（f.prd）、按截止時(shí)間升序排序（f.ddl）、按包長(zhǎng)升序排序（f.size）。

圖6 不同流排序方案對(duì)流映射數(shù)量的影響

在所有排序策略中，MILP_FITP 算法均優(yōu)于其他算法，和流的調(diào)度順序無關(guān)，實(shí)驗(yàn)結(jié)果和預(yù)期相符。在流截止時(shí)間升序排序之后f.ddl 小的流先調(diào)度，避免了在無序情況下隊(duì)列與時(shí)延約束而導(dǎo)致的不可調(diào)度，該排序方式獲得最優(yōu)性能。由于截止時(shí)間模型ddl(1)極大減少了因超時(shí)而導(dǎo)致的不可調(diào)度，因此排序后FJ-random、Tabu-ITP-chang 算法也均可實(shí)現(xiàn)2 000 條流量成功調(diào)度?；诹髁棵芏鹊淖⑷霑r(shí)隙的Tabu-ITP-change 算法映射結(jié)果優(yōu)于隨機(jī)選擇注入時(shí)隙的FJ-random 算法映射結(jié)果。順序注入時(shí)隙的FJ-FO 算法在所有排序策略中映射流數(shù)量均小于其他算法。逐流調(diào)度算法理論上先調(diào)度的流可選擇的資源更多。FJ-FO 算法按流順序優(yōu)先選擇最近的時(shí)隙，減少了流時(shí)隙的排列數(shù)量。由于流生成周期、包長(zhǎng)、截止時(shí)間均是隨機(jī)產(chǎn)生的，因此未排序時(shí)調(diào)度順序隨機(jī)性更大。排序原則使流在某些特征上有序，因此算法在排序之后成功映射的流數(shù)量反而變得更少，并且受到排序策略影響的程度更大。逐流調(diào)度算法中，隨機(jī)性越好映射流數(shù)量越多，且在熱點(diǎn)鏈路上的流量調(diào)整會(huì)在一定程度上提高算法的性能，但是并不能讓算法保證完全調(diào)度。

3) 網(wǎng)絡(luò)拓?fù)鋵?duì)算法的影響

為了探究網(wǎng)絡(luò)拓?fù)鋵?duì)所提算法的影響，假設(shè)仿真網(wǎng)絡(luò)中待調(diào)度流的數(shù)量為2 000 條，分別評(píng)估線性拓?fù)?、環(huán)形拓?fù)浜脱┗ㄐ瓮負(fù)湎碌挠成淞鲾?shù)和平均求解時(shí)間，仿真結(jié)果如圖7 所示。

不同網(wǎng)絡(luò)拓?fù)湎聦?duì)映射流數(shù)和時(shí)間成本比較了5 種算法，如圖7(a)所示，MILP_FITP 算法和Tabu-ITP算法在不同網(wǎng)絡(luò)拓?fù)湎掠成淞鲾?shù)最高，F(xiàn)J-random 算法次之，MILP-FITP 算法映射流數(shù)比FJ-FO 算法和FO-CS 算法這類逐流順序調(diào)度提高了大約15%。與其他2 個(gè)拓?fù)湎啾龋蠖鄶?shù)算法的線性拓?fù)渲械挠成淞鲾?shù)最少，原因是每個(gè)交換機(jī)在線性拓?fù)渲凶疃嘀淮嬖? 個(gè)方向的出端口，任意兩端系統(tǒng)之間只存在唯一傳輸路徑，根據(jù)隊(duì)列時(shí)隙資源的占用發(fā)現(xiàn)，隨著映射流量的增加中間4個(gè)交換機(jī)會(huì)陸續(xù)在隊(duì)列資源占用上出現(xiàn)滿載。MILP_FITP 算法通過全局資源使用的優(yōu)化可以在3 種拓?fù)渲袑?shí)現(xiàn)2 000 條流量完全調(diào)度。

圖7 不同網(wǎng)絡(luò)拓?fù)鋵?duì)映射流數(shù)和平均求解時(shí)間的影響

如圖7(b)所示，大多數(shù)算法在雪花形拓?fù)湎逻\(yùn)行時(shí)間最長(zhǎng)，環(huán)形拓?fù)浯沃?，線性拓?fù)渑c環(huán)形拓?fù)浣咏Ｔ蚴蔷€性拓?fù)渑c環(huán)形拓?fù)湓诰W(wǎng)絡(luò)規(guī)模上接近，而雪花形拓?fù)渚W(wǎng)絡(luò)規(guī)模最大，路由與調(diào)度的搜索空間要大得多。FJ-FO 算法、FJ-random 算法和FO-CS 算法平均求解時(shí)間為100 s 以下，Tabu-ITP-change 算法平均求解時(shí)間最長(zhǎng)，MILP_FITP 算法次之。在此網(wǎng)絡(luò)規(guī)模下，Tabu-ITP-change 算法所計(jì)算出的現(xiàn)有的最佳解接近最優(yōu)解，由于搜索空間大且需要多次交換迭代以防止局部最優(yōu)結(jié)果，時(shí)間成本要高于MILP_FITP 算法。

4) 流量特征對(duì)算法的影響

為了探究流量數(shù)據(jù)幀長(zhǎng)度、流量周期以及流量截止時(shí)間對(duì)算法的性能影響，以Tabu-ITP-change算法作為參考進(jìn)行如下性能對(duì)比。

①數(shù)據(jù)幀長(zhǎng)度

測(cè)試的網(wǎng)絡(luò)拓?fù)錇檠┗ㄐ尉W(wǎng)絡(luò)，流量周期從{1 000,2 000}μs 中隨機(jī)選取，應(yīng)用2 種截止時(shí)間模型，數(shù)據(jù)幀長(zhǎng)度為125～500 B 的小包、500～1 000 B 的中包、1 000～1 500 B 的長(zhǎng)包以及125～1 500 B 的隨機(jī)包。

不同包長(zhǎng)對(duì)調(diào)度性能的影響如圖8 所示，橫坐標(biāo)表示待調(diào)度流數(shù)量，折線圖表示Tabu-ITP-change 算法成功調(diào)度流百分比，Tabu-ITP-change 算法無法實(shí)現(xiàn)完全調(diào)度，柱狀圖表示AHTS+MILP_FITP 算法網(wǎng)絡(luò)調(diào)度成功率。AHTS+MILP_FITP 算法在一定范圍內(nèi)可以實(shí)現(xiàn)完全調(diào)度。AHTS 算法根據(jù)流量特征、網(wǎng)絡(luò)規(guī)模生成隊(duì)列長(zhǎng)度和硬件調(diào)度時(shí)隙以最大化流量調(diào)度，AHTS算法確定Lqueue和Lslot后，重復(fù)100 次實(shí)驗(yàn)以統(tǒng)計(jì)網(wǎng)絡(luò)調(diào)度成功率。在1 000 條以下輕負(fù)載的時(shí)間敏感流場(chǎng)景下并不會(huì)出現(xiàn)資源爭(zhēng)用問題，所提算法可以完全求解。包長(zhǎng)增加會(huì)在不同階段出現(xiàn)無法調(diào)度的問題，增加隊(duì)列長(zhǎng)度雖然會(huì)緩解資源爭(zhēng)用問題，但是Lslot增加伴隨著無法滿足時(shí)間敏感流的時(shí)延約束問題。一旦AHTS+MILP_FITP 算法出現(xiàn)網(wǎng)絡(luò)調(diào)度成功率下降，說明網(wǎng)絡(luò)在滿負(fù)荷運(yùn)轉(zhuǎn)，增加待調(diào)度流數(shù)量無法提高成功映射流數(shù)量。從圖8 中的柱狀圖可以看出，待調(diào)度流為600 條時(shí)長(zhǎng)包出現(xiàn)網(wǎng)絡(luò)調(diào)度成功率降低的現(xiàn)象，而待調(diào)度流超過800 條時(shí)中包和隨機(jī)包均出現(xiàn)了網(wǎng)絡(luò)調(diào)度成功率降低的現(xiàn)象，中包對(duì)應(yīng)的網(wǎng)絡(luò)調(diào)度成功率更高。Tabu-ITP-chang 算法在900 條流之后隨機(jī)包對(duì)應(yīng)曲線高于中包對(duì)應(yīng)曲線柱狀圖現(xiàn)象相符。

圖8 不同包長(zhǎng)對(duì)調(diào)度性能的影響

② 發(fā)包周期

網(wǎng)絡(luò)拓?fù)錇檠┗ㄐ屯負(fù)?，流的截止時(shí)間為ddl(2)，時(shí)延系數(shù)為0.9，發(fā)包周期從{1 000,2 000}μs 中隨機(jī)選取。不同周期對(duì)調(diào)度性能的影響如圖9 所示，橫坐標(biāo)為待調(diào)度流數(shù)量，實(shí)線對(duì)應(yīng)左縱坐標(biāo)表示Tabu-ITP-change 算法在不同發(fā)包周期下的成功調(diào)度流比例，虛線對(duì)應(yīng)右縱坐標(biāo)表示保證待調(diào)度流完全映射性能下MILP_FITP 算法所使用的緩存隊(duì)列長(zhǎng)度。

圖9 不同周期對(duì)調(diào)度性能的影響

隨著發(fā)包間隔增大，時(shí)間敏感流從端注入網(wǎng)絡(luò)的時(shí)隙有更多選擇，可調(diào)度的流數(shù)量隨之增加。由圖 9 可知，采用固定Lslot和Lqueue配置的Tabu-ITP-change 算法流量調(diào)度性能較低，當(dāng)仿真網(wǎng)絡(luò)里的流量增加時(shí)，成功調(diào)度流比例在不同的發(fā)包周期下均出現(xiàn)下降的情況。雪花形拓?fù)渎酚傻淖畲筇鴶?shù)為4 跳，在時(shí)延系數(shù)為0.9 情況下，發(fā)包周期為1 000 μs 的數(shù)據(jù)會(huì)產(chǎn)生超時(shí)情況，而低頻流的截止時(shí)間范圍更大，流量不會(huì)因?yàn)闀r(shí)延約束而無法調(diào)度。因此發(fā)包周期為1 000 μs 對(duì)應(yīng)的曲線下降更快。由于隊(duì)列溢出情況的出現(xiàn)，增加待調(diào)度流數(shù)量即使成功映射的流數(shù)量會(huì)增加，但映射比例在下降，因?yàn)椴糠謳L(zhǎng)度較小的流被替換進(jìn)調(diào)度成功流集合中。在式(5)～式(9)的約束下，Lslot會(huì)限制時(shí)隙的選擇，Lqueue會(huì)限制容納流量的數(shù)量。自適應(yīng)的硬件調(diào)度時(shí)隙與隊(duì)列長(zhǎng)度可以有效提升調(diào)度流比例，MILP_FITP 算法幾乎保持全部映射。進(jìn)一步探究在保持全部映射的性能下隊(duì)列緩存長(zhǎng)度的變化，隨著待調(diào)度流的增加，發(fā)包周期大的流所需要得到的隊(duì)列緩存長(zhǎng)度會(huì)比發(fā)包周期小的流短，由于相同時(shí)間內(nèi)發(fā)送的數(shù)據(jù)包會(huì)少于高頻流，因此其會(huì)在較大待調(diào)度流數(shù)出現(xiàn)隊(duì)列緩存瓶頸問題。高頻流的低時(shí)延要求會(huì)導(dǎo)致網(wǎng)絡(luò)中存在流數(shù)上限，不能理想地增加緩存隊(duì)列長(zhǎng)度，由于Lslot會(huì)對(duì)應(yīng)增加以滿足式(11)，因此圖9 中超過一定數(shù)量的待調(diào)度流沒有標(biāo)記，流數(shù)超過臨界值的網(wǎng)絡(luò)無流調(diào)度。

③截止時(shí)間

網(wǎng)絡(luò)拓?fù)錇檠┗ㄐ瓮負(fù)?，流量周期從{1 000,2 000}μs 中隨機(jī)選取，應(yīng)用2 種截止時(shí)間模型，使用的時(shí)延系數(shù)分別為0.4 和0.9。仿真結(jié)果如圖10 所示，橫坐標(biāo)表示待調(diào)度流量數(shù)量。

圖10 不同截止時(shí)間對(duì)調(diào)度性能的影響

如圖10(a)所示，實(shí)線對(duì)應(yīng)Tabu-ITP-change 算法性能，縱坐標(biāo)表示成功調(diào)度流百分比。由流周期和時(shí)延系數(shù)決定的截止時(shí)間模型，其時(shí)延系數(shù)越大，可選的注入時(shí)隙越多，映射比例越大。影響算法調(diào)度性能的主要原因如下：1)Lslot不合適，無論如何優(yōu)化流量的注入時(shí)間也無法在規(guī)定時(shí)間內(nèi)到達(dá)終端系統(tǒng)；2)Lqueue不合適，在某些節(jié)點(diǎn)的隊(duì)列出現(xiàn)溢出現(xiàn)象。截止時(shí)間模型ddl(1)中，在500 條流量以內(nèi)，Tabu-ITP-change 算法在固定配置下基本上實(shí)現(xiàn)完全映射，有一小部分流量因?yàn)樗阉鞑煌耆脑驅(qū)е聲r(shí)延約束無法滿足。由于Lqueue不合適導(dǎo)致網(wǎng)絡(luò)無法承載更多的流量，待調(diào)度流大于700 條時(shí)調(diào)度性能明顯下降。虛線對(duì)應(yīng)AHTS+MILP_FITP 算法的調(diào)度性能，提出算法在一定范圍內(nèi)可以保證待調(diào)度流的完全調(diào)度。圖10(b)給出了不同截止時(shí)間下隊(duì)列長(zhǎng)度與硬件調(diào)度時(shí)隙的選擇情況，左縱坐標(biāo)表示CQF隊(duì)列長(zhǎng)度，右縱坐標(biāo)表示硬件調(diào)度時(shí)隙。不同截止時(shí)間下的時(shí)隙長(zhǎng)度曲線重合，隊(duì)列長(zhǎng)度柱狀圖持平，表明在可調(diào)度流量數(shù)量范圍內(nèi)，流的截止時(shí)間模型與容忍性并不影響隊(duì)列緩存長(zhǎng)度和時(shí)隙長(zhǎng)度的選擇，網(wǎng)絡(luò)中待調(diào)度流數(shù)不同時(shí)，其優(yōu)化計(jì)算得到的隊(duì)列長(zhǎng)度和時(shí)隙長(zhǎng)度可能是相同的。當(dāng)流截止時(shí)間要求高時(shí)，只能用短時(shí)隙長(zhǎng)度進(jìn)行快速轉(zhuǎn)發(fā)才能實(shí)現(xiàn)流調(diào)度，由于Lqueue與Lslot之間具有約束關(guān)系，且隊(duì)列溢出限制支持的流數(shù)量有上限，必須啟用短隊(duì)列交換機(jī)進(jìn)行轉(zhuǎn)發(fā)，該現(xiàn)象與圖10(a)中對(duì)應(yīng)的待調(diào)度流完全映射區(qū)間相一致。當(dāng)時(shí)延要求與時(shí)隙長(zhǎng)度相關(guān)、與流特征無關(guān)時(shí)，則可以通過增加隊(duì)列長(zhǎng)度和時(shí)隙長(zhǎng)度增加網(wǎng)絡(luò)中可調(diào)度流數(shù)量。但是從圖10(b)的趨勢(shì)來看，當(dāng)流量負(fù)載增大時(shí)，隊(duì)列長(zhǎng)度增加很大，有必要根據(jù)成本等因素考慮通過其他途徑增加承載能力。

6 結(jié)束語

本文關(guān)注局域網(wǎng)中的大規(guī)模流量調(diào)度問題，提出了一個(gè)通用的全局規(guī)劃高優(yōu)化的路由與調(diào)度機(jī)制，建立了全局資源視圖，為上層算法設(shè)計(jì)者提供了資源映射問題的高層抽象；通過建立路由與調(diào)度的混合整數(shù)規(guī)劃模型，提出了一種基于流分類的MILP 與逐流調(diào)度算法。該算法使TSN 的路徑上所能容納的時(shí)間敏感流數(shù)最大，并實(shí)現(xiàn)了網(wǎng)絡(luò)的負(fù)載均衡，調(diào)度結(jié)果具有擴(kuò)展能力，使用工業(yè)控制網(wǎng)絡(luò)中的3 種典型拓?fù)鋵?duì)算法進(jìn)行了評(píng)估。在相同隊(duì)列配置下的實(shí)驗(yàn)結(jié)果表明，MILP_FITP 算法與FJ-FO、FJ-random、FO-CS、Tabu-ITP-change 算法相比，映射流數(shù)最高提高28%，在隊(duì)列時(shí)隙資源利用上更均衡。雖然啟發(fā)式算法通過引入流密度方差和多類型加權(quán)排序使映射質(zhì)量獲得良好的改進(jìn)，但在測(cè)試規(guī)模下求解的時(shí)間復(fù)雜度與精確算法相比并不低，且求解質(zhì)量低于MILP_FITP 算法。實(shí)驗(yàn)結(jié)果表明，在中小型局域網(wǎng)絡(luò)中AHTS+MILP_FITP 算法顯著提高了網(wǎng)絡(luò)的調(diào)度能力，實(shí)現(xiàn)了可接受時(shí)間成本內(nèi)路由與時(shí)隙調(diào)度規(guī)劃的優(yōu)化。