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

（1.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876；2.國網(wǎng)河南省電力公司信息通信公司，河南 鄭州 450052；3.國網(wǎng)信息通信產(chǎn)業(yè)集團(tuán)有限公司，北京 102211）

1 引言

隨著信息技術(shù)的飛速發(fā)展，在工廠自動化控制、自動駕駛和電力自動化等領(lǐng)域，對數(shù)據(jù)流傳輸?shù)臅r延要求超出了傳統(tǒng)以太網(wǎng)的可控范圍[1]。為解決傳統(tǒng)以太網(wǎng)中實時數(shù)據(jù)的可靠傳輸問題，IEEE 802工作組提出了時間敏感網(wǎng)絡(luò)（TSN,time-sensitive network）的概念。TSN 支持時間觸發(fā)流量（TT,time-triggered traffic）的傳輸，該類流量具有周期性傳輸?shù)奶攸c，并具有確定性的低時延要求。針對TT的調(diào)度問題出現(xiàn)了大量的研究[2-10]。

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

上述研究通過不同方法給出了時間觸發(fā)流量可行的調(diào)度機制，但是在大規(guī)模調(diào)度場景下的求解時間難以滿足調(diào)度需求。為此，本文針對大規(guī)模時間敏感網(wǎng)絡(luò)中時間觸發(fā)流量的調(diào)度問題進(jìn)行了研究，具體包括以下三部分。

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

2)針對網(wǎng)絡(luò)拓?fù)湟?guī)模龐大的問題，設(shè)計了一種拓?fù)湫藜舨呗浴Ｍㄟ^減少不必要的約束條件簡化調(diào)度模型，減少了調(diào)度的求解耗時。

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

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

2.1 時延分析

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

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

圖1 時延分析

當(dāng)不發(fā)生排隊時，D只包含發(fā)送時延、傳播時延和處理時延。傳播時延由信道長度和介質(zhì)中信號的傳播速率決定，可以認(rèn)為具有確定性。交換機內(nèi)部的處理時延與其存儲轉(zhuǎn)發(fā)的能力有關(guān)，可以認(rèn)為具有確定性。發(fā)送時延由幀大小和發(fā)送速率決定，也具有確定性。當(dāng)網(wǎng)絡(luò)中發(fā)生擁塞時，在交換機內(nèi)部排隊時間無法確定，導(dǎo)致產(chǎn)生的排隊時延具有不確定性。

由于端到端時延的不確定性主要來源于可能包含的排隊時延，因此在設(shè)計時間觸發(fā)流的調(diào)度模型時，需要避免排隊情況的出現(xiàn)，從而保證其傳輸?shù)拇_定性。

2.2 調(diào)度模型

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

如圖2 所示，一個基本周期被分為多個時隙，每個時隙從0～tmax編號，被分給特定的時間觸發(fā)流進(jìn)行傳輸，且時隙的長度足夠?qū)挘阋允棺畲髠鬏攩卧∕TU,maximum transmission unit）的數(shù)據(jù)分組穿過最長的網(wǎng)絡(luò)路徑。

圖2 基本周期的時隙分片

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

網(wǎng)絡(luò)的拓?fù)浔唤橛邢驁DG=(V,L)，其中V=S∪H是網(wǎng)絡(luò)中所有節(jié)點的集合，S表示網(wǎng)絡(luò)中的交換機，H表示終端的主機。L?V×V表示網(wǎng)絡(luò)中相互連接的2 個節(jié)點之間的一條有向全雙工鏈路。有序?qū)?Vi,Vj)和(Vj,Vi)分別表示2 條獨立的傳輸鏈路，有序?qū)Φ牡谝粋€元素表示發(fā)送節(jié)點，第二個元素表示目的節(jié)點。定義網(wǎng)絡(luò)中時間觸發(fā)流的集合F為

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

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

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

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

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

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

在時間觸發(fā)流量集合和網(wǎng)絡(luò)拓?fù)湟阎那闆r下，為了提高調(diào)度的成功率，調(diào)度機制應(yīng)在保證時延確定性的前提下，盡可能地提高網(wǎng)絡(luò)中能夠容納的時間觸發(fā)流的數(shù)量。另外，由于一個時間觸發(fā)流對應(yīng)多個其可能傳輸?shù)淖疃搪窂?，但是最終只會選擇其中一條進(jìn)行傳輸，因此可以把時間觸發(fā)流分配到時隙上的問題轉(zhuǎn)化為把路徑分配到時隙上的問題，則優(yōu)化的目標(biāo)是盡可能地提高分配到時隙中的路徑的數(shù)量。某個流組Gm的調(diào)度模型可以形式化描述為

3 拓?fù)湫藜舨呗耘c流分組策略

3.1 拓?fù)湫藜舨呗?/h3>

模型約束條件的建立與網(wǎng)絡(luò)的拓?fù)渚哂忻芮嘘P(guān)系。根據(jù)式(12)可知，拓?fù)浣Y(jié)構(gòu)中每一條鏈路在每一個時隙上都會為模型添加一條約束條件。而當(dāng)拓?fù)湟?guī)模更加龐大時，模型的約束條件數(shù)目會快速增加，從而導(dǎo)致問題的復(fù)雜程度急劇增加，最終導(dǎo)致求解時間不能被接受。

然而，對于一組待調(diào)度的時間觸發(fā)流而言，每一個時間觸發(fā)流最終只會選擇最短路徑集合中的一條路徑進(jìn)行傳輸，該組時間觸發(fā)流可能占用的鏈路資源為最短路徑集合中所有路徑所包含的鏈路。因此，整個拓?fù)浣Y(jié)構(gòu)中剩余的鏈路在本組調(diào)度中不會有流通過，不可能發(fā)生同時傳輸?shù)臎_突情況。通過拓?fù)湫藜舻姆绞綄⒈窘M時間觸發(fā)流調(diào)度時的網(wǎng)絡(luò)拓?fù)溥M(jìn)行修剪，刪除不會進(jìn)行傳輸?shù)逆溌?，從而達(dá)到減少模型約束條件的目的。

圖3 是上述拓?fù)湫藜舻囊粋€示例。圖3 (a)為網(wǎng)絡(luò)原拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)中存在2 個待調(diào)度的流量，分別為flow1=(S7,S5)和flow2=(S3,S5)。flow1從源節(jié)點到目標(biāo)節(jié)點有2 條最短路徑，分別為path1和path2，而flow2從源節(jié)點到目標(biāo)節(jié)點有2 條最短路徑，分別為path3和path4。這4 條路徑所包含的鏈路是本組調(diào)度可能占用的鏈路資源，每條鏈路都會為模型的求解添加約束條件。拓?fù)湫藜糁蟮慕Y(jié)果如圖3(b)所示，鏈路的減少使模型的約束條件減少，從而降低了問題的求解規(guī)模。另外，由于拓?fù)湫藜舨呗圆粫绊懽罱K的調(diào)度結(jié)果，因此調(diào)度成功率保持不變。

圖3 拓?fù)湫藜羰纠?/p>

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

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

然而，這種分組調(diào)度的方式在對每組時間觸發(fā)流進(jìn)行調(diào)度時所獲得的結(jié)果是一個局部最優(yōu)的結(jié)果，最終的調(diào)度結(jié)果與原先的結(jié)果可能具有一定的偏差，從而導(dǎo)致調(diào)度成功率的降低。因此，在進(jìn)行分組調(diào)度時，如何保證一定的調(diào)度成功率是首要考慮的問題。

譜聚類（SC,spectral clustering）[11]是一種基于圖論的聚類方法，將帶權(quán)無向圖劃分為2 個或2 個以上的最優(yōu)子圖，使子圖內(nèi)部盡量相似，而子圖之間距離盡量遠(yuǎn)，所得結(jié)果是一個均勻劃分，即各個劃分所包含的節(jié)點數(shù)目相近。本文將譜聚類的思想引入分組策略的研究中。對于2 個待調(diào)度的流而言，如果它們各自可能傳輸?shù)穆窂街g具有較多重疊的鏈路，則它們同時進(jìn)行傳輸?shù)碾y度也較大。同理，對于2 個流組而言，如果它們中所有的流可能傳輸?shù)穆窂郊现g具有較多重疊的鏈路，則這2 個流組同時進(jìn)行傳輸?shù)碾y度也較大。因此，為了使分組調(diào)度之后的調(diào)度成功率盡可能高，各個流組之間路徑集合的重疊鏈路應(yīng)盡可能少。

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

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

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

圖4 待調(diào)度流量集合劃分示例

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

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

3.3 基于拓?fù)湫藜舨呗院土鞣纸M策略的分組調(diào)度機制

分組調(diào)度機制的整體流程如算法1 所示。算法1 的整體輸入為所有時間觸發(fā)流的集合F、網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)G=(V,L)、分組數(shù)max，輸出為路徑和時隙的映射。最終獲得的即為最終的調(diào)度結(jié)果。在初始化步驟中(算法的1)～3)行)，對F按照基于譜聚類的分組策略進(jìn)行分組，從而得到分組結(jié)果G1,G2,…,Gmax?1,Gmax。另外還要對變量以及前一組流量的調(diào)度結(jié)果帶來的約束進(jìn)行初始化。在每一組的調(diào)度過程中，首先進(jìn)行拓?fù)湫藜簦苊猱a(chǎn)生不必要的約束條件；然后進(jìn)行ILP 模型求解，將得出的調(diào)度結(jié)果更新到中，并將本組調(diào)度帶來的對后續(xù)調(diào)度的約束M(l,t)更新到中。

算法1分組調(diào)度機制

4 仿真實驗和結(jié)果分析

4.1 實驗環(huán)境

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

仿真條件包括網(wǎng)絡(luò)的拓?fù)湟?guī)模和數(shù)量規(guī)模兩方面，前者表現(xiàn)為網(wǎng)絡(luò)中交換機的數(shù)目，后者表現(xiàn)為待調(diào)度流量的數(shù)目。模型的參數(shù)包括是否進(jìn)行拓?fù)湫藜簦ǚ謩e用1 和0 表示）、分組的數(shù)量、基本周期的時隙分片數(shù)量。

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

4.2 仿真結(jié)果和分析

本節(jié)將分組調(diào)度機制與文獻(xiàn)[9-10]調(diào)度方法的仿真實驗結(jié)果進(jìn)行對比，重點分析拓?fù)湫藜粢约傲鞣纸M2 種策略在大規(guī)模調(diào)度場景下的有效性。算法性能的評價指標(biāo)是求解時間與調(diào)度成功率。

表1 仿真條件及參數(shù)的設(shè)置

4.2.1 算法隨流量規(guī)模增長的表現(xiàn)

為了探究不同流量規(guī)模下算法性能的表現(xiàn)，利用表1 中實驗1 的仿真條件和參數(shù)進(jìn)行仿真實驗，網(wǎng)絡(luò)中交換機的數(shù)量為50 個，待調(diào)度流量的數(shù)量為100～550 個，實驗結(jié)果分別如圖5 和圖6 所示。

圖5 求解時間隨TT 流數(shù)量的變化

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

由圖5 可知，當(dāng)采用流分組策略時，本文算法求解時間相對于文獻(xiàn)[9-10]方法有一定下降；并且隨著流量規(guī)模的增加（流量數(shù)目達(dá)到300 個以上時），求解時間降低顯著。在此基礎(chǔ)上，如果采用拓?fù)湫藜舨呗裕蠼鈺r間又有一定的降低。

由圖6 可知，拓?fù)湫藜舨呗栽跍p少求解時間的同時，可以保證成功率不變，這與3.1 節(jié)的理論分析是一致的。對比文獻(xiàn)[9-10]方法和采用流分組策略的結(jié)果，當(dāng)待調(diào)度流量的數(shù)量為150 時，流分組策略的調(diào)度成功率與文獻(xiàn)[9-10]方法相近。而隨著待調(diào)度流量數(shù)量的增加，流分組策略會造成調(diào)度成功率出現(xiàn)一定程度降低，但是降低的程度是可以接受的（圖6 中成功率的偏差在8%之內(nèi)），同時，顯著減少了求解時間。因此，綜合來看分組調(diào)度機制是有效的。

4.2.2 算法隨網(wǎng)絡(luò)拓?fù)湟?guī)模增長的表現(xiàn)

為了探究不同網(wǎng)絡(luò)拓?fù)湟?guī)模下算法性能的表現(xiàn)，利用表1 中實驗2 的仿真條件和參數(shù)進(jìn)行了仿真實驗，待調(diào)度流量的數(shù)量為150，網(wǎng)絡(luò)中交換機的數(shù)量為40～110 個，實驗結(jié)果分別如圖7 和圖8 所示。

圖7 求解時間隨交換機數(shù)量的變化

圖8 調(diào)度成功率隨交換機數(shù)量的變化

幾種方案的求解時間如圖7 所示。當(dāng)采用流分組策略時，求解時間相對于文獻(xiàn)[9-10]方法有了一定的下降，并且隨著網(wǎng)絡(luò)拓?fù)湟?guī)模的增加（交換機數(shù)量超過70 時），求解時間降低愈加顯著。在此基礎(chǔ)上，如果采用拓?fù)湫藜舨呗?，求解時間又有一定的降低。

調(diào)度成功率的結(jié)果如圖8 所示。隨著交換機數(shù)量的增加，可用的鏈路傳輸資源越來越多，因此各種方法的調(diào)度成功率逐漸增加。此外，通過與文獻(xiàn)[9-10]方法的結(jié)果進(jìn)行對比可以看出，隨著網(wǎng)絡(luò)拓?fù)湟?guī)模的增加，流分組策略可以在減少求解時間的同時，保證一定的調(diào)度成功率（圖8 中成功率的偏差在5%以內(nèi)）。此外，對比采用拓?fù)湫藜舨呗郧昂蟮慕Y(jié)果可以看出，拓?fù)湫藜舨呗栽趯崿F(xiàn)降低求解耗時的同時，可以保證調(diào)度成功率保持不變。

4.2.3 模型參數(shù)對于算法性能的影響

1)分組數(shù)目

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

圖9 求解耗時隨分組數(shù)量的變化

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

圖10 調(diào)度成功率隨分組數(shù)量的變化

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

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

圖11 求解耗時隨時隙分片數(shù)量的變化

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

圖12 調(diào)度成功率隨時隙分片數(shù)量的變化

5 結(jié)束語

針對大規(guī)模時間敏感網(wǎng)絡(luò)中時間觸發(fā)流量的調(diào)度問題，本文提出的分組調(diào)度機制通過消除排隊時延保證了時延的確定性。同時，所提拓?fù)湫藜舨呗越鉀Q了由于網(wǎng)絡(luò)拓?fù)湟?guī)模增加而導(dǎo)致的求解時間劇增的問題。所提基于譜聚類的流分組策略解決了由于流量規(guī)模增加而導(dǎo)致的求解時間劇增的問題。仿真實驗表明，該機制在大規(guī)模調(diào)度場景下可以在較短時間內(nèi)求出調(diào)度結(jié)果并保證一定的調(diào)度成功率。

本文所做的工作仍有許多的不足，例如在路由策略中選擇了所有最短路徑的集合作為可能傳輸?shù)穆窂郊?。下一步研究將綜合考慮路由和調(diào)度兩方面的因素來進(jìn)行時間觸發(fā)流量的調(diào)度研究。