面向大規模時間敏感網絡的分組調度機制

邱雪松，黃徐川，李文萃，李溫靜，郭少勇

（1.北京郵電大學網絡與交換技術國家重點實驗室，北京 100876；2.國網河南省電力公司信息通信公司，河南 鄭州 450052；3.國網信息通信產業集團有限公司，北京 102211）

1 引言

隨著信息技術的飛速發展，在工廠自動化控制、自動駕駛和電力自動化等領域，對數據流傳輸的時延要求超出了傳統以太網的可控范圍[1]。為解決傳統以太網中實時數據的可靠傳輸問題，IEEE 802工作組提出了時間敏感網絡（TSN,time-sensitive network）的概念。TSN 支持時間觸發流量（TT,time-triggered traffic）的傳輸，該類流量具有周期性傳輸的特點，并具有確定性的低時延要求。針對TT的調度問題出現了大量的研究[2-10]。

文獻[2]使用可滿足性模理論（SMT,satisfiability modulo theory）和優化模理論（OMT,optimization modulo theory）來實現有效調度。文獻[3]基于整數線性規劃（ILP,integer linear programming）計算式生成門控制列表，通過計算全局調度將資源最佳地分配給時間觸發流量。文獻[4]提出了一種混合遺傳算法，用于生成時間觸發流量的靜態調度表，優化了時隙的分配數量并提高了傳輸效率。文獻[5]提出了一種基于遺傳算法的啟發式調度算法，使用路由和調度的聯合約束來生成靜態的全局調度，從而使可調度性、傳輸效率和資源利用率得到顯著提高。文獻[6-7]基于ILP 提出了針對路由和調度聯合問題的解決方案。文獻[6]使用2 個性能指標（即端到端時延和調度能力）來評估不同流量模式和網絡拓撲的實驗結果。文獻[7]利用ILP 解算器對參數變化很大的問題實例進行了求解，根據求解時長對算法的性能進行了評估。文獻[8]基于SMT 提出了一種聯合路由和調度的迭代算法，但是算法性能對流量之間傳輸路徑的沖突程度敏感，導致成功率較低。文獻[9-10]提出了時間敏感軟件定義網絡（TSSDN,time-sensitive software-defined network）的概念和用于計算調度的ILP 式，TSSDN 利用邏輯集中的控制平面來計算全局的調度方案。

上述研究通過不同方法給出了時間觸發流量可行的調度機制，但是在大規模調度場景下的求解時間難以滿足調度需求。為此，本文針對大規模時間敏感網絡中時間觸發流量的調度問題進行了研究，具體包括以下三部分。

1)建立了分組調度模型，在每一組流量的調度中，通過時間和空間上將待調度流量分離的時分多址（TDMA,time division multiple access）思想消除了排隊時延，保證了時延的確定性。

2)針對網絡拓撲規模龐大的問題，設計了一種拓撲修剪策略。通過減少不必要的約束條件簡化調度模型，減少了調度的求解耗時。

3)針對流量規模龐大的問題，設計了一種基于譜聚類的流分組策略。通過分組調度的方式減少調度求解時間，同時保證較高的成功率。

2 數學模型

2.1 時延分析

時間觸發流從源主機到目的主機沿著指定路徑進行周期性傳輸，其端到端時延包括傳播時延、發送時延、處理時延，當網絡中發生擁塞時，還包括排隊時延。時延分析如圖1 所示。

圖1 中，ti表示節點vi的發送時刻，dtrans、dprop和dproc分別表示發送時延、傳播時延和處理時延。當發生排隊時，排隊時延為dqueu，D表示某個節點和下一節點之間的端到端時延，如式(1)所示。

圖1 時延分析

當不發生排隊時，D只包含發送時延、傳播時延和處理時延。傳播時延由信道長度和介質中信號的傳播速率決定，可以認為具有確定性。交換機內部的處理時延與其存儲轉發的能力有關，可以認為具有確定性。發送時延由幀大小和發送速率決定，也具有確定性。當網絡中發生擁塞時，在交換機內部排隊時間無法確定，導致產生的排隊時延具有不確定性。

由于端到端時延的不確定性主要來源于可能包含的排隊時延，因此在設計時間觸發流的調度模型時，需要避免排隊情況的出現，從而保證其傳輸的確定性。

2.2 調度模型

當多個數據分組試圖在交換機的同一個輸出端口進行傳輸時，會發生排隊的情況，若在時間觸發流傳輸時為其分配特定的鏈路資源僅供其傳輸，就可以消除排隊的情況從而保證端到端時延的確定性。在時間上，可以在一個基本周期內為不同的時間觸發流分配不同的時隙；在空間上，可以為不同的時間觸發流分配不沖突的鏈路資源。通過這種在時間和空間上將不同時間觸發流分離的時分多址思想，可以實現每個時間觸發流到達交換機時，始終有一個空狀態的隊列為其開放，從而避免了排隊情況的出現。

如圖2 所示，一個基本周期被分為多個時隙，每個時隙從0～tmax編號，被分給特定的時間觸發流進行傳輸，且時隙的長度足夠寬，足以使最大傳輸單元（MTU,maximum transmission unit）的數據分組穿過最長的網絡路徑。

圖2 基本周期的時隙分片

基本周期能提供的時隙分片數量有一個上限值。例如，對于1 Gbit/s 的鏈路，假設MTU 為1 500 B，數據分組允許穿越的最長網絡路徑為8 跳，則一個MTU 的數據分組穿越最長網絡路徑的總發送時延為1 500 B×8÷1 Gbit/s×8=0.096 ms。在僅考慮發送時延的情況下，5 ms 的基本周期最多可以提供5÷0.096≈52 個時隙分片，考慮到傳輸距離及交換機處理能力等影響因素，實際時隙分片數量的上限要更小一點。

網絡的拓撲被建模為有向圖G=(V,L)，其中V=S∪H是網絡中所有節點的集合，S表示網絡中的交換機，H表示終端的主機。L?V×V表示網絡中相互連接的2 個節點之間的一條有向全雙工鏈路。有序對(Vi,Vj)和(Vj,Vi)分別表示2 條獨立的傳輸鏈路，有序對的第一個元素表示發送節點，第二個元素表示目的節點。定義網絡中時間觸發流的集合F為

所有的時間觸發流按照特定的分組策略被分組為：G1,G2,…,Gmax?1,Gmax，其中max 表示分組的數量，在調度環節的每次迭代中完成一組時間觸發流集合的調度。一組時間觸發流集合Gm中所有流可能的傳輸路徑的集合為

其中，fj=(s,d)表示集合Gm中的一個流，s和d分別表示fj的源主機和目的主機，表示流fj可能通過的路徑的集合。在本文模型中，被設定為流fj最短路徑的集合，于是PGm包括每個時間觸發流fj∈Gm從源主機到目的主機的所有最短路徑。時隙分片的集合T和所有鏈路的集合L分別如式(4)和式(5)所示。

定義如式(6)～式(9)所示映射。

FP 為時間觸發流和路徑之間的映射，如果流f通過路徑p從源主機到達目的主機，則X(f,p)=1；否則X(f,p)=0。PL 為路徑和鏈路之間的映射，如果路徑p包含鏈路l，則Y(p,l)=1，否則Y(p,l)=0。LT 為鏈路和時隙之間的映射，如果時隙t上的鏈路l在先前的迭代調度過程中已經被占用，則M(l,t)=1，否則M(l,t)=0。PT 為路徑與時隙之間的映射，如果時間觸發流沿著路徑p在時隙t上進行了傳輸，則N(p,t)=1，否則N(p,t)=0。

定義如式(10)～式(12)所示約束。

約束條件(10)表示每一條路徑最多只能分配到一個時隙上。每一個時間觸發流最多只能分配到一個時隙上，由于該流最終只能選擇一條最短路徑進行傳輸，因此對于每個時間觸發流而言，最多只能為其一條可能的最短路徑分配時隙，則有約束條件(11)。如果具有相同鏈路的2 條路徑應被分配到同一個時隙時，可能引起沖突，因此某條鏈路的某個時隙上最多只允許一個時間觸發流進行傳輸，則有約束條件(12)。

在時間觸發流量集合和網絡拓撲已知的情況下，為了提高調度的成功率，調度機制應在保證時延確定性的前提下，盡可能地提高網絡中能夠容納的時間觸發流的數量。另外，由于一個時間觸發流對應多個其可能傳輸的最短路徑，但是最終只會選擇其中一條進行傳輸，因此可以把時間觸發流分配到時隙上的問題轉化為把路徑分配到時隙上的問題，則優化的目標是盡可能地提高分配到時隙中的路徑的數量。某個流組Gm的調度模型可以形式化描述為

3 拓撲修剪策略與流分組策略

3.1 拓撲修剪策略

模型約束條件的建立與網絡的拓撲具有密切關系。根據式(12)可知，拓撲結構中每一條鏈路在每一個時隙上都會為模型添加一條約束條件。而當拓撲規模更加龐大時，模型的約束條件數目會快速增加，從而導致問題的復雜程度急劇增加，最終導致求解時間不能被接受。

然而，對于一組待調度的時間觸發流而言，每一個時間觸發流最終只會選擇最短路徑集合中的一條路徑進行傳輸，該組時間觸發流可能占用的鏈路資源為最短路徑集合中所有路徑所包含的鏈路。因此，整個拓撲結構中剩余的鏈路在本組調度中不會有流通過，不可能發生同時傳輸的沖突情況。通過拓撲修剪的方式將本組時間觸發流調度時的網絡拓撲進行修剪，刪除不會進行傳輸的鏈路，從而達到減少模型約束條件的目的。

圖3 是上述拓撲修剪的一個示例。圖3 (a)為網絡原拓撲結構，網絡中存在2 個待調度的流量，分別為flow1=(S7,S5)和flow2=(S3,S5)。flow1從源節點到目標節點有2 條最短路徑，分別為path1和path2，而flow2從源節點到目標節點有2 條最短路徑，分別為path3和path4。這4 條路徑所包含的鏈路是本組調度可能占用的鏈路資源，每條鏈路都會為模型的求解添加約束條件。拓撲修剪之后的結果如圖3(b)所示，鏈路的減少使模型的約束條件減少，從而降低了問題的求解規模。另外，由于拓撲修剪策略不會影響最終的調度結果，因此調度成功率保持不變。

圖3 拓撲修剪示例

3.2 基于譜聚類的流分組策略

前文所述的調度模型是一個ILP 問題，該問題是一個NP-hard 問題。隨著待調度流量數量的增加，模型的求解時間會急劇增加而變得不能被接受。首先對所有的時間觸發流進行分組，然后對各個流組分別進行調度，即對每個流組的ILP 模型進行求解，并將所得的調度結果作為下一流組ILP 模型的約束條件進行輸入，這種分組調度的方式可以將原來大規模的求解問題劃分為較小規模的ILP 問題，從而在流的數量較多時，顯著的減少最終的總耗時。

然而，這種分組調度的方式在對每組時間觸發流進行調度時所獲得的結果是一個局部最優的結果，最終的調度結果與原先的結果可能具有一定的偏差，從而導致調度成功率的降低。因此，在進行分組調度時，如何保證一定的調度成功率是首要考慮的問題。

譜聚類（SC,spectral clustering）[11]是一種基于圖論的聚類方法，將帶權無向圖劃分為2 個或2 個以上的最優子圖，使子圖內部盡量相似，而子圖之間距離盡量遠，所得結果是一個均勻劃分，即各個劃分所包含的節點數目相近。本文將譜聚類的思想引入分組策略的研究中。對于2 個待調度的流而言，如果它們各自可能傳輸的路徑之間具有較多重疊的鏈路，則它們同時進行傳輸的難度也較大。同理，對于2 個流組而言，如果它們中所有的流可能傳輸的路徑集合之間具有較多重疊的鏈路，則這2 個流組同時進行傳輸的難度也較大。因此，為了使分組調度之后的調度成功率盡可能高，各個流組之間路徑集合的重疊鏈路應盡可能少。

用路徑集相似度的概念來表示2 個路徑集合之間的重疊程度，定義2 個流之間路徑集相似度為

其中，w(fi,fj)是流fi和流fj的傳輸路徑集合之間鏈路重疊程度的表征。對于流集F的一個劃分，即G1,G2,…,Gmax?1,Gmax，其總路徑集相似度為

基于流之間的路徑集相似度來建立無向圖ξ=(F,W)，其中頂點集F由所有時間觸發流組成，邊集W=F×F的權重表示2 個流fi和流fj之間的路徑集相似度w(fi,fj)。2 個頂點之間相連表示對應的2 個流之間的路徑集合存在一定的重疊鏈路，如果這2 個流之間的路徑集合不存在重復鏈路，即路徑集相似度為0，則對應的頂點之間不連接。圖4 給出了待調度流量集合F={f1,f2,…,f8,f9}的一個劃分，即G1={f1,f2,f8},G2={f3,f4,f9},G3={f5,f6,f7}。根據式(15)可知，圖4 中虛線的權重之和表示該劃分的總路徑集相似度。

圖4 待調度流量集合劃分示例

考慮到模型求解耗時的問題，還應使各個分組的大小盡可能一致，避免出現某個分組過大的情況，否則會導致模型求解的總時間變得不再理想，而譜聚類均分劃分的特點可以滿足該需求。

因此，求解流的最佳分組問題被轉化為求解基于路徑集相似度構建的無向圖ξ的最佳劃分問題。在具體實現上，由于Python 中sklearn.cluster 的SpectralClustering 模塊集成了譜聚類方法，將由路徑集相似度構建的相似度矩陣M（Mi,j表示流fi和流fj之間的路徑集相似度）和要分組的數目作為參數輸入，即可獲得分組結果。該結果是一個總路徑集相似度最小且均勻的最佳劃分，分組的結果G1,G2,…,Gmax?1,Gmax將被用于分組調度機制。

3.3 基于拓撲修剪策略和流分組策略的分組調度機制

分組調度機制的整體流程如算法1 所示。算法1 的整體輸入為所有時間觸發流的集合F、網絡的拓撲結構G=(V,L)、分組數max，輸出為路徑和時隙的映射。最終獲得的即為最終的調度結果。在初始化步驟中(算法的1)～3)行)，對F按照基于譜聚類的分組策略進行分組，從而得到分組結果G1,G2,…,Gmax?1,Gmax。另外還要對變量以及前一組流量的調度結果帶來的約束進行初始化。在每一組的調度過程中，首先進行拓撲修剪，避免產生不必要的約束條件；然后進行ILP 模型求解，將得出的調度結果更新到中，并將本組調度帶來的對后續調度的約束M(l,t)更新到中。

算法1分組調度機制

4 仿真實驗和結果分析

4.1 實驗環境

所提調度模型是一個ILP 問題，可直接采用CPLEX 或Lingo 等解算器進行求解，本文基于Python3.7 和IBM 的CPLEX（版本V12.10）進行了仿真實驗。通過Python 的networkx 包生成網絡拓撲，基于sklearn.cluster 的SpectralClustering 模塊完成對調度流量的分組。實驗思路是，通過不同調度規模下算法的仿真表現來驗證其有效性。

仿真條件包括網絡的拓撲規模和數量規模兩方面，前者表現為網絡中交換機的數目，后者表現為待調度流量的數目。模型的參數包括是否進行拓撲修剪（分別用1 和0 表示）、分組的數量、基本周期的時隙分片數量。

實驗的仿真條件及參數如表1 所示。

4.2 仿真結果和分析

本節將分組調度機制與文獻[9-10]調度方法的仿真實驗結果進行對比，重點分析拓撲修剪以及流分組2 種策略在大規模調度場景下的有效性。算法性能的評價指標是求解時間與調度成功率。

表1 仿真條件及參數的設置

4.2.1 算法隨流量規模增長的表現

為了探究不同流量規模下算法性能的表現，利用表1 中實驗1 的仿真條件和參數進行仿真實驗，網絡中交換機的數量為50 個，待調度流量的數量為100～550 個，實驗結果分別如圖5 和圖6 所示。

圖5 求解時間隨TT 流數量的變化

圖6 調度成功率隨TT 流數量的變化

由圖5 可知，當采用流分組策略時，本文算法求解時間相對于文獻[9-10]方法有一定下降；并且隨著流量規模的增加（流量數目達到300 個以上時），求解時間降低顯著。在此基礎上，如果采用拓撲修剪策略，求解時間又有一定的降低。

由圖6 可知，拓撲修剪策略在減少求解時間的同時，可以保證成功率不變，這與3.1 節的理論分析是一致的。對比文獻[9-10]方法和采用流分組策略的結果，當待調度流量的數量為150 時，流分組策略的調度成功率與文獻[9-10]方法相近。而隨著待調度流量數量的增加，流分組策略會造成調度成功率出現一定程度降低，但是降低的程度是可以接受的（圖6 中成功率的偏差在8%之內），同時，顯著減少了求解時間。因此，綜合來看分組調度機制是有效的。

4.2.2 算法隨網絡拓撲規模增長的表現

為了探究不同網絡拓撲規模下算法性能的表現，利用表1 中實驗2 的仿真條件和參數進行了仿真實驗，待調度流量的數量為150，網絡中交換機的數量為40～110 個，實驗結果分別如圖7 和圖8 所示。

圖7 求解時間隨交換機數量的變化

圖8 調度成功率隨交換機數量的變化

幾種方案的求解時間如圖7 所示。當采用流分組策略時，求解時間相對于文獻[9-10]方法有了一定的下降，并且隨著網絡拓撲規模的增加（交換機數量超過70 時），求解時間降低愈加顯著。在此基礎上，如果采用拓撲修剪策略，求解時間又有一定的降低。

調度成功率的結果如圖8 所示。隨著交換機數量的增加，可用的鏈路傳輸資源越來越多，因此各種方法的調度成功率逐漸增加。此外，通過與文獻[9-10]方法的結果進行對比可以看出，隨著網絡拓撲規模的增加，流分組策略可以在減少求解時間的同時，保證一定的調度成功率（圖8 中成功率的偏差在5%以內）。此外，對比采用拓撲修剪策略前后的結果可以看出，拓撲修剪策略在實現降低求解耗時的同時，可以保證調度成功率保持不變。

4.2.3 模型參數對于算法性能的影響

1)分組數目

通過上述實驗分析，可以看出流分組策略針對大規模調度場景具有一定的有效性。為了進一步探究分組的數目對于算法性能的影響，本節利用表1 中實驗3 的仿真條件和參數進行仿真實驗。網絡交換機數量為50，待調度流量的數量為250，分組的數量分別為一個（表示不使用流分組策略）、10～100 個，實驗結果分別如圖9 和圖10所示。求解時間隨著分組數目增加的變化曲線如圖9 所示，可以看出，當分組的數量增加時，求解時間會逐漸降低，但是降低的幅度逐漸變緩。調度成功率如圖10 所示，隨著分組數量的增加，調度的成功率逐漸降低。

圖9 求解耗時隨分組數量的變化

流分組策略可以實現調度求解時間的降低，然而一直增大分組的數量也是不可取的，還應當考慮調度成功率的因素。分組數量為10 時，調度成功率為77.2%；不分組（即分組數量為1）時，調度成功率為82.8%，2 種情況下的成功率相差5%左右。隨著分組數量的增加，求解時間降低的幅度逐漸變緩，但是調度成功率與不分組時成功率（82.8%）相差逐漸增大。因此，分組數目應綜合考慮求解時間和調度成功率兩方面因素進行選擇。

圖10 調度成功率隨分組數量的變化

2) 基本周期的時隙分片數目

為了探究時隙分片的數目對于算法性能的影響，本節利用表1 中實驗4 的仿真條件和參數進行仿真實驗，網絡交換機數量為50，待調度流量的數量為250，流分組的數量為10，基本周期的時隙分片數目為5～15，實驗結果分別如圖11 和圖12 所示。求解時間隨時隙分片數目增加的變化曲線如圖11 所示，可以看出，隨著時隙分片數目的增加，模型逐漸復雜導致求解時間逐漸增加。算法的調度成功率隨時隙分片數目增加的變化曲線如圖12 所示，可以看出，時隙分片的數目越多，調度成功率越高，當時隙分片的數目超過11 時，調度成功率達到100%，此時所有的待調度流量均可以在網絡中傳輸。

圖11 求解耗時隨時隙分片數量的變化

時隙分片的數目代表了網絡在時間維度上容納時間觸發流的能力。時隙分片的數目越多，網絡中能夠同時進行傳輸的時間觸發流也越多，圖12的仿真結果印證了這一點。然而，隨著時隙分片數目的增加，求解時間也會增加，這是因為每增加一個時隙，模型的變量數目（即路徑與時隙的映射變量）以及約束條件（即每條鏈路在每個時隙上的傳輸約束）都會線性增加，這將導致問題規模增大，從而造成求解時間的增加。此外，由于基本周期能提供的時隙分片數目是有上限的，因此時隙分片的數目應當在允許的范圍內綜合考慮求解時間和調度成功率兩方面因素進行選擇。

圖12 調度成功率隨時隙分片數量的變化

5 結束語

針對大規模時間敏感網絡中時間觸發流量的調度問題，本文提出的分組調度機制通過消除排隊時延保證了時延的確定性。同時，所提拓撲修剪策略解決了由于網絡拓撲規模增加而導致的求解時間劇增的問題。所提基于譜聚類的流分組策略解決了由于流量規模增加而導致的求解時間劇增的問題。仿真實驗表明，該機制在大規模調度場景下可以在較短時間內求出調度結果并保證一定的調度成功率。

本文所做的工作仍有許多的不足，例如在路由策略中選擇了所有最短路徑的集合作為可能傳輸的路徑集。下一步研究將綜合考慮路由和調度兩方面的因素來進行時間觸發流量的調度研究。