時間敏感網絡中基于IEEE 802.1Qch 標準的優化調度機制

聶宏蕊，李紹勝，劉勇

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

0 引言

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

已發布的標準 IEEE 802.1Qbv[3]和 IEEE 802.1Qch[4]用于解決標準以太網中不確定性排隊時延的問題。基于IEEE 802.1Qbv 的時間感知整形器（TAS,time-aware shaper）能夠實現微秒級逐跳逐包的細粒度調度，TAS 需要為交換機中每個隊列附加的門控列表（GCL,gate control list）進行配置。但是調度算法的運算復雜度很高，網絡的任何變化都會導致GCL 重新計算和配置。為了簡化TSN 交換機的設計，IEEE 802.1 Qch 標準基于TAS 提出了一種名為循環排隊和轉發（CQF,cyclic queuing and forwarding）的易用模型，也稱蠕動整形器。CQF 提供確定性且易于計算時延的時間敏感流量調度，不需要復雜的配置，TSN 的實現與管理復雜度大大降低，因此，CQF 已經成為TSN 中高選擇的整形器[5]。

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

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

1) 有界時延。算法滿足有界隊列長度約束，并在要求的期限內將時間敏感流傳輸到目的地。

2) 高可調度性。算法具有高網絡可調度性，在時間敏感網絡中可調度數千個時間敏感流，并且保持較高的網絡調度成功率。

3) 調度順序獨立。算法不完全依賴于待調度流量的先后順序，在全局范圍內完成規劃與映射。

4) 端口隊列長度自適應性。隊列長度在滿足傳輸需求的同時應相對較小，降低實現難度與硬件成本，在減小調度粒度的同時考慮運算時間。

5) 可行的執行時間。算法針對離線階段最大化成功映射到目標網絡上的時間敏感流的數量，均衡每個時隙所承載流量負載以提高調度方案的擴展能力，因此要求運算時間低于動態規劃階段的調度規劃算法。解決方案應該具有可接受的算法執行時間和高質量求解結果。

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

1) 基于軟件定義網絡架構和循環隊列與轉發機制，在TSN 中開展數據流的全局路徑規劃、隊列規劃與時隙分配的聯合調度，實現局域網中流量的自動化控制與調度。

2) 提出了網絡與流量多屬性特征的硬件調度時隙自適應生成算法，實現隊列長度與硬件調度時隙的自適應配置，以實現調度粒度與運算時間的平衡，提高網絡的調度能力。

3) 提出了MILP_FITP 算法分別對端到端截止時間要求高的流量進行逐流調度，對多偏移量可選擇的流量的混合整數規劃模型進行規模縮減以加快求解速度，通過均衡資源利用進一步提升網絡的可調度性。

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

1 研究背景與相關工作

1.1 CQF 調度機制

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

圖1 循環排隊與轉發機制示意

1.2 相關工作

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

可滿足性模理論（SMT,satisfiability modulo theories）[13-15]和整數線性規劃（ILP,integer linear programming）[16-19]數學理論可以用來解決路由和調度問題，通過建立網絡與流量的關鍵約束求解滿足要求的路由規劃與調度方案。文獻[20]使用一階邏輯約束來定義調度問題，分別調用SMT 和MIP 求解器，在有和沒有優化目標的情況下求解方案。文獻[21]提出了分組調度機制，建立路由和調度的整數線性規劃模型，通過拓撲修剪和基于譜聚類的流分組策略縮小約束的規模，在較短時間內進行模型的求解，保證一定的調度成功率。文獻[22]提出沖突程度感知流分區多路徑路由技術和基于迭代整數線性規劃的可伸縮性調度技術提高調度成功率和容錯性。文獻[23]建立了一種新的無沖突網絡更新的ILP 調度模型，保證了網絡更新中沒有幀損失，也沒有引入額外的更新時間。

ITP（injection time planning）算法[6]通過將循環流的注入時間映射到隊列資源來實現CQF，簡化了GCL 的配置，通過隨機交換調度成功的流量集合與調度失敗的流量集合以提高調度成功率，得到近似優化解，但未考慮不同場景下隊列長度與硬件調度時隙對調度性能的影響。文獻[7]在ITP 的約束模型下提出了在線流注入時間調度算法，根據網絡資源利用率調整網絡適配器上的發送時間，為新的時間敏感流增量生成流量調度，不需要重新配置先前規劃，實現了快速調度。

綜上所述，現有的優化算法分別采用啟發式算法、元啟發式算法以及整數規劃求解算法求解近似最優調度規劃，求解速度依次遞減，求解質量依次遞增。現有的CQF 調度機制采用逐流調度方式和啟發式算法為網絡實現一個可用的規劃，網絡調度成功率有待提高，且算法的優化解與最優解未進行對比。為此，本文針對局域網絡中的時間敏感流量大規模調度問題，提出了基于CQF 整形機制的聯合路由與調度優化的全局規劃加速生成算法，保證流量的有界時延、網絡高可調度性、調度獨立性與可接受的執行時間。

2 數學模型

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

圖2 TSN 架構

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

圖3 支持CQF 機制的TSN 交換機結構

時間關鍵型應用被建模為周期性流量，每個流量都在其周期內傳輸。考慮一組K個周期性單播時間敏感流集合F={f 1,f2,…,fk,…,fK}，為了簡化，多播的情況可以被分割成具有相同源和不同目的地的多個單播流。每個流由源端系統、目標端系統、幀長度、流量周期、允許的最大端到端時延、有序的傳輸路徑和流量注入網絡時隙的七元組來定義，即

其中，f k.route 和f k.φ分別由路由算法和調度算法生成后配置。系統參數如表1 所示。

表1 系統參數

3 問題描述

在本文中，對于給定網絡拓撲和流量集合，求解的流路由與調度方案需要滿足以下約束。

1) 路由約束

如果節點vi是流fk的源節點，則

如果節點vi是流fk的目的節點，則

如果節點vi是流fk流經路徑的中間節點，則

為了防止出現循環路由同一個節點的情況，對于流fk的每條預留鏈路最多僅可訪問一次，即

2) 調度約束

與調度問題相關的CQF 隊列長度、硬件調度時隙和交換機出端口的調度周期分別表示為Lqueue、Lslot和Tschedule。對于不同時間生成的流量，通過注入網絡時間的規劃實現對TSN 的高效調度。

①流量的時延注入時間約束

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

② 交換機的接收窗口約束

該約束是用來檢查數據包是否在窗口右端內到達，理論上如果硬件調度時隙滿足最小時隙約束，則所有數據包都會滿足該約束。對于任意時間敏感流fk在每一跳的接收時隙為

③流量的截止時間約束

為了保障時間敏感流的有界低時延傳輸，流的所有數據包要在指定時間之前到達目標端系統，即

④ 交換機隊列資源約束

TSN 交換機中隊列的緩存容量有限，在每個時隙中隊列緩存的數據包總大小不能超過緩存大小，數據流fk在鏈路上所占用的時隙可表示為

對于某個端口的任意時隙，端口傳輸的流的總大小不應超過隊列緩存大小，否則隊列溢出，即

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

CQF 標準規定數據包在相鄰2 個節點的發送時隙和接收時隙相同，則最小時隙需要保證隊列中的所有數據包在相同的時隙內從上游節點傳輸到下游節點，時隙的下界約束為

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

考慮數據流最大容忍時延需求和網絡特點，基于流量完全調度的要求，截止時間要求最高的流量有規定時間內送達的約束對硬件調度時隙有上界要求，表示為

其中，Hmax表示深度優先搜索方法得到網絡的最長路徑，Dmin表示流量集中流量DDL 的最小值。如果小于時隙的下界值，則認為該流量無法在網絡中調度；否則作為硬件調度時隙上界約束。

4 算法提出

在標準以太網交換機中，數據包存儲在緩沖池中，而隊列用于存儲數據包的元數據以進行調度。因此，交換機中的最大隊列長度等于緩沖池中數據包緩沖區的數量。端系統為避免占用過多的緩存空間會在數據產生后立即發送，如果沒有嚴格且詳細的發送時間規劃，流量很容易集中到隊列的部分時隙中轉發。由于隊列長度是有限的，一旦數據量超過緩存大小，會出現隊列溢出，導致數據包被丟棄。實際上，可以通過時延流的發送時隙來緩解此問題，從而使隊列的時隙利用更加平衡。但是當流注入網絡的偏移量過大時，終端需要緩存大量的數據包，耗費大量的存儲空間，這將限制終端的發包數量和種類。根據以上分析，在設計調度算法時主要需要解決以下2 個問題。

1) 基于流特征、網絡規模和流量規模確定硬件時隙長度和緩存隊列長度

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

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

2) 進行合理的時間敏感流路由與注入時間映射

基于路由約束式(1)～式(4)和調度約束式(5)～式(9)，構建聯合路由和調度問題為混合整數線性規劃，考慮均衡分配流量占用的路徑與時隙，以最大化可調度流量數量，最小化繁忙鏈路隊列利用率為目標，獲得最優的流量路由與時隙偏移分配策略。CQF-TSN 調度問題可以表述為以下MILP 問題。

CQF-TSN 問題搜索空間的指數增加主要來自以下兩方面：每個流量可用路徑的數量和注入網絡偏移量的數量。除了從底層拓撲模型上可以縮減模型、減少變量與約束的數量，還可以優化ILP 生成過程本身，通過減少ILP 產生的不必要的輔助變量，減少MILP 端變量的數量以及變量的邊界范圍，從而減少搜索空間以降低MILP 的復雜度。

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

對于任意流fk給定的一組路徑按照流量截止時間要求升序排序，將前的流量選擇最短的路徑。定義路徑pk的負載加權和為

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

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

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

5 仿真實驗和結果分析

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

5.1 參數設置

設置鏈路帶寬為1 Gbit/s，網絡最大傳輸單位MTU=1 500 B。網絡拓撲如圖4 所示，這些拓撲幾乎可以被組裝到所有的工業網絡結構中。

圖4 網絡拓撲

流量周期和截止時間的單位為μs，截止時間包含2 種模型，即和與網絡規模、硬件調度時隙無關的模型其中，η為時延系數，無特殊說明則η=0.4。流的源端系統和目標端系統從網絡中的端系統中任意生成一對，隊列緩存最低門限設置為3MTU，帶寬利用比例閾值β=0.9。所對比的調度算法基于固定的隊列長度和硬件調度時隙，實驗參數如表2 所示。

表2 實驗參數

5.2 評估指標

評估算法性能由以下幾個指標完成。

1) 映射流數量，給定仿真網絡中的流參數，滿足所有約束成功調度流的數量。

2) 網絡調度成功率，表示滿足所有約束的求解方案的實驗次數與總實驗次數的比值。

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

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

5) 運行時間，表示算法完成所有流量調度所需要的時間，單位為s。

5.3 仿真結果分析

1) 注入時隙方法

在MILP_FITP 算法中，優化目標是均衡時隙帶寬占有率以緩解調度瓶頸，提高流量調度成功率。為驗證算法的有效性，本文與4 種算法進行對比，網絡拓撲為線性拓撲，發包周期從中隨機選取，為了排除隊列長度和硬件調度時隙的影響，MILP_FITP 算法采用表2 所示的固定配置。對比不同流量注入方案對成功映射流量數量和平均時隙帶寬占有率的影響，仿真結果如圖5 所示。

在固定配置下，MILP_FITP 算法精確求解后網絡調度成功率達100%時最多調度2 000 條流量，因此圖5(a)中MILP_FITP 算法僅保留了250～2 000 條流量的仿真結果，隨著待調度流量數量增加，MILP_FITP 算法對比其他算法的改進增大，待調度流量數量為2 000 時對比FJ-FO 算法達到28%。

圖5 不同注入方案對算法的影響

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

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

2) 流調度順序

考慮流周期、流的截止時間、數據包長度，將待調度流集合按單個因素排序后調用調度算法。網絡拓撲為環形拓撲，仿真網絡中存在2 000 條時間敏感流，流的截止時間采用 2 種模型，發包周期從中隨機抽取。為了排除隊列長度和硬件調度時隙的影響，MILP_FITP 算法采用表2 所示的固定配置，對比不同流排序方案對流映射數量的影響，仿真結果如圖6 所示，橫坐標表示排序原則，分別為不排序（no sort）、按流周期升序排序（f.prd）、按截止時間升序排序（f.ddl）、按包長升序排序（f.size）。

圖6 不同流排序方案對流映射數量的影響

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

3) 網絡拓撲對算法的影響

為了探究網絡拓撲對所提算法的影響，假設仿真網絡中待調度流的數量為2 000 條，分別評估線性拓撲、環形拓撲和雪花形拓撲下的映射流數和平均求解時間，仿真結果如圖7 所示。

不同網絡拓撲下對映射流數和時間成本比較了5 種算法，如圖7(a)所示，MILP_FITP 算法和Tabu-ITP算法在不同網絡拓撲下映射流數最高，FJ-random 算法次之，MILP-FITP 算法映射流數比FJ-FO 算法和FO-CS 算法這類逐流順序調度提高了大約15%。與其他2 個拓撲相比，大多數算法的線性拓撲中的映射流數最少，原因是每個交換機在線性拓撲中最多只存在2 個方向的出端口，任意兩端系統之間只存在唯一傳輸路徑，根據隊列時隙資源的占用發現，隨著映射流量的增加中間4個交換機會陸續在隊列資源占用上出現滿載。MILP_FITP 算法通過全局資源使用的優化可以在3 種拓撲中實現2 000 條流量完全調度。

圖7 不同網絡拓撲對映射流數和平均求解時間的影響

如圖7(b)所示，大多數算法在雪花形拓撲下運行時間最長，環形拓撲次之，線性拓撲與環形拓撲接近。原因是線性拓撲與環形拓撲在網絡規模上接近，而雪花形拓撲網絡規模最大，路由與調度的搜索空間要大得多。FJ-FO 算法、FJ-random 算法和FO-CS 算法平均求解時間為100 s 以下，Tabu-ITP-change 算法平均求解時間最長，MILP_FITP 算法次之。在此網絡規模下，Tabu-ITP-change 算法所計算出的現有的最佳解接近最優解，由于搜索空間大且需要多次交換迭代以防止局部最優結果，時間成本要高于MILP_FITP 算法。

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

為了探究流量數據幀長度、流量周期以及流量截止時間對算法的性能影響，以Tabu-ITP-change算法作為參考進行如下性能對比。

①數據幀長度

測試的網絡拓撲為雪花形網絡，流量周期從{1 000,2 000}μs 中隨機選取，應用2 種截止時間模型，數據幀長度為125～500 B 的小包、500～1 000 B 的中包、1 000～1 500 B 的長包以及125～1 500 B 的隨機包。

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

圖8 不同包長對調度性能的影響

② 發包周期

網絡拓撲為雪花型拓撲，流的截止時間為ddl(2)，時延系數為0.9，發包周期從{1 000,2 000}μs 中隨機選取。不同周期對調度性能的影響如圖9 所示，橫坐標為待調度流數量，實線對應左縱坐標表示Tabu-ITP-change 算法在不同發包周期下的成功調度流比例，虛線對應右縱坐標表示保證待調度流完全映射性能下MILP_FITP 算法所使用的緩存隊列長度。

圖9 不同周期對調度性能的影響

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

③截止時間

網絡拓撲為雪花形拓撲，流量周期從{1 000,2 000}μs 中隨機選取，應用2 種截止時間模型，使用的時延系數分別為0.4 和0.9。仿真結果如圖10 所示，橫坐標表示待調度流量數量。

圖10 不同截止時間對調度性能的影響

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

6 結束語

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