林佳爍，王 濤+，王卓薇，詹雙平，成 劍

(1.廣東工業(yè)大學(xué) 自動化學(xué)院，廣東 廣州 510006；2.廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006；3.鵬城實驗室 寬帶通信研究部，廣東 深圳 518055)

0 引 言

時間敏感網(wǎng)絡(luò)(time sensitive networking，TSN)是一種新興的確定性網(wǎng)絡(luò)傳輸技術(shù)，其通過時間同步、路徑計算、資源預(yù)留等機制在以太網(wǎng)的基礎(chǔ)上保障網(wǎng)絡(luò)中實時業(yè)務(wù)流的確定性網(wǎng)絡(luò)傳輸[1]。不同于其它只能單一傳輸實時數(shù)據(jù)的時間敏感型網(wǎng)絡(luò)技術(shù)(如Profinet、EtherCAT、POWERLINK等)，時間敏感網(wǎng)絡(luò)支持在同一網(wǎng)絡(luò)下混合傳輸非實時業(yè)務(wù)流數(shù)據(jù)及實時業(yè)務(wù)流數(shù)據(jù)。而保障實時業(yè)務(wù)流數(shù)據(jù)的網(wǎng)絡(luò)傳輸不被非實時業(yè)務(wù)流干擾的關(guān)鍵機制就是時間同步機制(IEEE 802.1AS[2]，以下簡稱802.1AS)以及門控機制(IEEE 802.1Qbv[3]，以下簡稱802.1Qbv)。

時間同步機制是時間敏感網(wǎng)絡(luò)的基石，802.1AS定義了網(wǎng)絡(luò)的時間同步協(xié)議，保證網(wǎng)絡(luò)中的所有設(shè)備時鐘都與全局時鐘在一個誤差范圍內(nèi)同步。而802.1Qbv則在交換機的出口端口處通過門控制列表(gate control list，GCL)對出口隊列進行開和關(guān)操作，來實現(xiàn)對網(wǎng)絡(luò)數(shù)據(jù)流的管控。

時間敏感網(wǎng)絡(luò)中基于802.1Qbv機制的調(diào)度算法大致分為兩種[4]，第一種是離線式調(diào)度算法，其一般將網(wǎng)絡(luò)建模為一個整數(shù)線性規(guī)劃問題(ILP)，然后使用SMT(satis-fiability modulo theories)求解器(如Z3等)或線性規(guī)劃求解器離線求解[5-7]。第二種是使用啟發(fā)式算法來降低算法運行所需要的時間，使得其可以在可接受的時間范圍內(nèi)在線求解[8，9]。文獻[7]將網(wǎng)絡(luò)周期分為多個小的時間槽，然后在每個時間槽里只調(diào)度一條實時業(yè)務(wù)流。盡管這種方法可以有效保證業(yè)務(wù)流之間的隔離，但也降低了網(wǎng)絡(luò)中可調(diào)度流的數(shù)量。文獻[10]將時間敏感網(wǎng)絡(luò)中的流調(diào)度問題映射到運籌學(xué)領(lǐng)域的作業(yè)安排調(diào)度問題(no-wait job-shop scheduling，NW-JSP)，然后使用禁忌搜索算法對該問題進行迭代求解。其中，No-wait約束指的是實時業(yè)務(wù)流在網(wǎng)絡(luò)中不會在出口隊列中排隊。但由于其僅假定所有業(yè)務(wù)流的應(yīng)用周期都是相同的，難以在實際應(yīng)用中對具有不同周期的業(yè)務(wù)流部署。而文獻[5]同樣基于No-wait約束來進行調(diào)度，其定義了業(yè)務(wù)流之間的沖突程度，并在離線調(diào)度情況下聯(lián)合路徑來進行優(yōu)化，最終使用ILP來進行求解。文獻[11]針對大規(guī)模網(wǎng)絡(luò)下采取了類似No-wait約束的傳輸調(diào)度方法，其保持門控隊列開關(guān)常開并最后使用SMT來求解。

總體而言，No-wait約束的流調(diào)度算法可有力保障業(yè)務(wù)實時性并且其簡單可實現(xiàn)，受到研究人員重點關(guān)注，但由于No-wait約束比較嚴(yán)格，其可調(diào)度的業(yè)務(wù)流數(shù)量受到較大限制；同時，實際場景中動態(tài)出現(xiàn)的眾多未知業(yè)務(wù)流也迫切需要實時在線增量的No-wait約束流調(diào)度。如何有效提升TSN中No-wait約束下的流調(diào)度能力，包括針對不同周期業(yè)務(wù)流的支持度、在線增量調(diào)度的實時性與容量等性能，是值得深入研究的關(guān)鍵問題。

本文首先提出一種基于No-wait約束的多周期業(yè)務(wù)流在線調(diào)度方法，可適用于多周期業(yè)務(wù)流混合調(diào)度的場景。該算法根據(jù)網(wǎng)絡(luò)流周期的特點，將業(yè)務(wù)流的宏周期(hyper-cycle)分為多個小的網(wǎng)絡(luò)周期，然后使用最早調(diào)度原則在線地對網(wǎng)絡(luò)業(yè)務(wù)流進行調(diào)度，從而實現(xiàn)多周期業(yè)務(wù)流的No-wait約束在線實時增量調(diào)度。為進一步提升在線調(diào)度的容量，根據(jù)該在線算法的特點，提出一種基于重合度的離線調(diào)度算法，在離線調(diào)度場景下使用了禁忌搜索算法以獲得更優(yōu)的調(diào)度結(jié)果，提高了剩余可調(diào)度空間，為后續(xù)的在線調(diào)度運行調(diào)度奠定良好的基礎(chǔ)。最后，對算法的性能進行實驗分析，并在仿真平臺Omnet++上驗證調(diào)度結(jié)果的正確性。實驗結(jié)果顯示，對于每一條業(yè)務(wù)流，在線調(diào)度算法調(diào)度計算耗費時間約為3.98 ms，滿足實時性要求。并且，對離線調(diào)度算法的仿真實驗顯示其可以有效解決在線調(diào)度無法適用的場景，將網(wǎng)絡(luò)的可調(diào)度業(yè)務(wù)流數(shù)量提高58%。

1 問題建模

1.1 系統(tǒng)建模

1.1.1 IEEE802.1Qbv模型

圖1展示了時間敏感網(wǎng)絡(luò)中一個典型的交換機結(jié)構(gòu)，其支持802.1Qbv標(biāo)準(zhǔn)，在其每個出口端口處，有8個轉(zhuǎn)發(fā)隊列。該交換機根據(jù)轉(zhuǎn)發(fā)數(shù)據(jù)報文中的PCP(priority code point)字段，將數(shù)據(jù)幀放置入對應(yīng)的隊列中。然后，通過GCL列表來控制對應(yīng)的隊列開關(guān)。當(dāng)隊列的狀態(tài)是“開”時，隊列中的數(shù)據(jù)幀能夠被轉(zhuǎn)發(fā)，否則不能被轉(zhuǎn)發(fā)。這種機制可以將實時業(yè)務(wù)流與非實時業(yè)務(wù)流隔離到不同的隊列，以實現(xiàn)實時業(yè)務(wù)流的轉(zhuǎn)發(fā)不受到干擾。并且，通過與時間同步機制進行結(jié)合，可以達到對數(shù)據(jù)流報文逐跳的嚴(yán)格精細控制，從而實現(xiàn)數(shù)據(jù)報文的確定性轉(zhuǎn)發(fā)。

圖1 支持802.1Qbv標(biāo)準(zhǔn)的交換機出口端口架構(gòu)

1.1.2 網(wǎng)絡(luò)模型

本文所使用的符號表示及其意義見表1。給定網(wǎng)絡(luò)拓?fù)銰=(V，E)，其中vi∈V表示的是網(wǎng)絡(luò)節(jié)點，ei=(vi，vj)∈E表示的是網(wǎng)絡(luò)中節(jié)點之間的鏈路。對于鏈路e∈E，spe表示該鏈路的傳輸速率。

表1 符號表示及其意義對照

對于業(yè)務(wù)流fi∈F，其中F表示所有業(yè)務(wù)流的集合，si、di、sizei、pi、ri分別表示該業(yè)務(wù)流的源節(jié)點、目標(biāo)節(jié)點、數(shù)據(jù)大小、應(yīng)用周期、轉(zhuǎn)發(fā)路徑。

(1)

1.1.3 網(wǎng)絡(luò)周期(基期)

由于網(wǎng)絡(luò)中業(yè)務(wù)流的應(yīng)用周期不相同，所以設(shè)置一個較小的時隙為網(wǎng)絡(luò)周期，本文將這個網(wǎng)絡(luò)周期稱為基期(base period，bp)，使得所有的業(yè)務(wù)流的應(yīng)用周期都為基期的整數(shù)倍。此時，將業(yè)務(wù)流的應(yīng)用周期與基期的比值稱為RR(reduction ratio)。如圖2所示，基期值為1 ms，兩個業(yè)務(wù)流Flow0及Flow1的應(yīng)用周期分別為2 ms和3 ms，則其RR分別為2和3，網(wǎng)絡(luò)的宏周期為這兩個應(yīng)用周期的最小公倍數(shù)6 ms。

圖2 網(wǎng)絡(luò)周期(基期)、應(yīng)用周期以及宏周期

1.2 問題描述

時間敏感網(wǎng)絡(luò)中的流調(diào)度問題是一個NP-hard問題[12]，為了確保實時業(yè)務(wù)流的確定性網(wǎng)絡(luò)服務(wù)，對業(yè)務(wù)流的傳輸有諸多約束條件。本文提出的算法旨在在線求解出滿足約束條件的調(diào)度解，該調(diào)度解不影響已調(diào)度的業(yè)務(wù)流的傳輸。其包括實時業(yè)務(wù)流的起始轉(zhuǎn)發(fā)時間，其路由路徑上的交換機的GCL列表配置。其約束條件如下：

約束1：實時業(yè)務(wù)流fi在其路徑上的鏈路的傳輸窗口不應(yīng)與其它已分配的窗口沖突，如式(2)所示

?fj∈F，j≠i，?e∈ri

?α∈{k∈N|0≤k

?β∈{k∈N|0≤k

(2)

其中，tIFG表示該出口端口的幀間隙(interframe gap，IFG)，該值為該端口傳輸96個比特所需要的時間。

約束2：傳輸窗口約束：實時業(yè)務(wù)流fi在鏈路上的傳輸窗口大小應(yīng)剛好等于其數(shù)據(jù)大小與鏈路速率的比值，如式(3)所示

?e∈ri，

(3)

約束3：No-wait約束[10]：該約束保證實時業(yè)務(wù)流fi在網(wǎng)絡(luò)中不會排隊，即業(yè)務(wù)流的隊列時延為0，如式(4)所示

?(u，v)，(v，w)∈ri，

(4)

其中，tprop及tproc分別表示鏈路的傳播時延及交換機的處理時延。

1.3 離線調(diào)度與在線調(diào)度

根據(jù)TSN網(wǎng)絡(luò)部署過程的不同，可以將流量調(diào)度問題分為離線調(diào)度與在線調(diào)度。離線調(diào)度與在線調(diào)度的不同在于，離線調(diào)度問題中所有的業(yè)務(wù)流都是已知的，而在線調(diào)度中，未來所要調(diào)度的業(yè)務(wù)流是未知的。一個典型的離線調(diào)度例子是，在一個新的工廠中根據(jù)已有的設(shè)備及裝配流程來規(guī)劃TSN網(wǎng)絡(luò)的部署及調(diào)度。由于工廠的設(shè)備以及對應(yīng)的應(yīng)用都是已知的，可以在離線狀態(tài)下計算出一個較優(yōu)的調(diào)度方案。而在線調(diào)度可以認(rèn)為是在現(xiàn)有的TSN網(wǎng)絡(luò)增加額外的設(shè)備及應(yīng)用，此時調(diào)度新的業(yè)務(wù)流不應(yīng)對原有的實時應(yīng)用造成影響。在耗費時間方面，離線調(diào)度允許較長的計算時間，而在線調(diào)度所允許的計算時間較短。

在實際的TSN部署中，大多數(shù)情況下設(shè)備及應(yīng)用是已知的，從而可以使用離線調(diào)度來進行計算，并進行部署。在本文中，考慮混合調(diào)度，其指的是在該已部署的網(wǎng)絡(luò)下新增業(yè)務(wù)流，所以在這種情況下，需考慮離線調(diào)度所計算出的調(diào)度方案性能。

2 基于No-wait約束的在線流調(diào)度方法

本文所提出的基于No-wait約束的在線流調(diào)度方法是一種在線的增量式調(diào)度算法，其旨在在線地為實時業(yè)務(wù)流計算出調(diào)度結(jié)果，即該業(yè)務(wù)流在源節(jié)點的起始發(fā)送時間以及其轉(zhuǎn)發(fā)路徑上交換機的GCL列表。

該算法運行流程如圖3所示，首先在初始化階段設(shè)置基期值及網(wǎng)絡(luò)拓?fù)?，然后進入在線計算階段。對于每個輸入的實時業(yè)務(wù)流，首先使用最短路徑算法(如Dijkstra算法等)計算該業(yè)務(wù)流的最短路徑，然后使用最早調(diào)度算法(見下文2.2節(jié))計算該業(yè)務(wù)流的調(diào)度結(jié)果。若調(diào)度成功，則更新網(wǎng)絡(luò)的GCL列表，否則停止算法運行。

圖3 算法運行流程

2.1 基期值設(shè)置

在該算法中，設(shè)置了一個基期，使得所有業(yè)務(wù)流的應(yīng)用周期都是該基期的整數(shù)倍(見1.1.3節(jié))，然后將實時業(yè)務(wù)流盡可能地分散調(diào)度到各個基期中，來提高可調(diào)度流的數(shù)量。由于在線運行算法時，未來輸入的業(yè)務(wù)流特征是不可知的，這就要求該基期的值設(shè)置得足夠小，使得其可以被所有未來可能出現(xiàn)的業(yè)務(wù)流的應(yīng)用周期整除。

另一方面，基期值又不應(yīng)設(shè)置得過小。這是因為，過小的基期值會導(dǎo)致調(diào)度結(jié)果過于分散而出現(xiàn)大量時隙碎片，減小了解空間，最終導(dǎo)致可調(diào)度流的數(shù)量降低。

所以，基期值應(yīng)剛好設(shè)置為可能出現(xiàn)的所有業(yè)務(wù)流應(yīng)用周期的最大公約數(shù)。在這種情況下，能夠取得最大的流調(diào)度數(shù)量。

2.2 盡早調(diào)度算法

本文所提出的算法旨在在線增量式地求解出調(diào)度結(jié)果，這就要求新調(diào)度的業(yè)務(wù)流不能干擾已調(diào)度的業(yè)務(wù)流，即已預(yù)留的時隙不應(yīng)被更改。

在該算法中，應(yīng)將業(yè)務(wù)流盡可能地調(diào)度分散到各個網(wǎng)絡(luò)周期中，并且將業(yè)務(wù)流盡早調(diào)度到其網(wǎng)絡(luò)周期的前部。這是由于未來所輸入的實時業(yè)務(wù)流是不可知的，若流的調(diào)度過于集中，則可能會導(dǎo)致當(dāng)需要調(diào)度的實時業(yè)務(wù)流周期太小而無法調(diào)度。并且，當(dāng)每次對新業(yè)務(wù)流進行調(diào)度時，盡管無論調(diào)度結(jié)果如何，總的剩余可調(diào)度時隙都是一樣的，但是應(yīng)可能地使每個基期的剩余可調(diào)度時隙更大，即，應(yīng)將總的剩余可調(diào)度時隙盡可能地分散到各個基期中，從而提高未來網(wǎng)絡(luò)的可調(diào)度性。

圖4展示了一個案例，其中有3個業(yè)務(wù)流Flow0～Flow2，RR(應(yīng)用周期與基期的比值)分別為2/2/1。此時網(wǎng)絡(luò)中已調(diào)度了業(yè)務(wù)流Flow0。當(dāng)要調(diào)度新的數(shù)據(jù)流Flow1時，方案(a)與方案(b)都是可行的。然而，如果使用方案(a)，將會導(dǎo)致調(diào)度結(jié)果過于集中，這減小了未來的調(diào)度問題解空間。例如，當(dāng)此時有RR為1的實時流Flow2要調(diào)度計算時，若采用方案(a)，無論將Flow2放在何處都無法滿足約束；而方案(b)因為其對Flow0及Flow1的調(diào)度較為分散而能夠正常對Flow2進行調(diào)度。

算法偽代碼如算法1所示，當(dāng)調(diào)度新實時業(yè)務(wù)流時，首先根據(jù)新的流應(yīng)用周期來更新宏周期(見算法第(3)行，其中l(wèi)cm函數(shù)是求最小公倍數(shù)運算)，并計算該流的RRi。然后，在其RRi周期內(nèi)計算其最早的調(diào)度時間offset，其結(jié)果應(yīng)滿足約束條件式(1)～式(4)。最后選擇這RRi周期內(nèi)最早調(diào)度時間作為調(diào)度結(jié)果。當(dāng)該業(yè)務(wù)流在其所有RRi周期都無法調(diào)度時，算法停止。此時網(wǎng)絡(luò)資源已不足以為該業(yè)務(wù)流預(yù)留時隙。

盡管該算法只輸出了實時業(yè)務(wù)流在源節(jié)點的起始傳輸時間，但這已足夠得到該流在網(wǎng)絡(luò)中各節(jié)點的傳輸窗口。這是因為在No-wait約束下，業(yè)務(wù)流數(shù)據(jù)幀在網(wǎng)絡(luò)中不會排隊，所以，當(dāng)確定了實時業(yè)務(wù)流的起始傳輸時間，就可以根據(jù)式(4)計算出該業(yè)務(wù)流在其轉(zhuǎn)發(fā)路徑上的每一跳所需預(yù)留的時延窗口。

算法1：最早調(diào)度算法

輸入：實時業(yè)務(wù)流fi

輸出：起始傳輸時間start_time

(1) cycle_idx =-1

(2) offset = +∞

(3) hyper-cycle = lcm(hyper-cycle,pi)

(4) RRi= hyper-cycle/pi

(5) for i in range(RRi):

(6) tmp = 計算fi在基期i的最早調(diào)度時間

(7) if tmp >bp then//在該基期i無法調(diào)度

(8) continue

(9) if tmp

(10) offset = tmp

(11) cycle_idx = i

(12) if offset == 0 then

(13) break

(14) return cycle_idx * bp +offset

另外，若該算法能夠求解出調(diào)度結(jié)果，則其一定能滿足業(yè)務(wù)流的最差時延要求，否則，表明此時網(wǎng)絡(luò)資源已不足以調(diào)度新實時業(yè)務(wù)流。這是因為，影響業(yè)務(wù)流時延的最大因素是其在網(wǎng)絡(luò)中的隊列時延，而在該算法中，首先為該業(yè)務(wù)流計算出的路徑是最短路徑，并且，在后續(xù)的調(diào)度計算過程中，引入了No-wait約束，該約束又保證了業(yè)務(wù)流在網(wǎng)絡(luò)中不會排隊，所以使用該算法可以保證為該業(yè)務(wù)流計算出的調(diào)度結(jié)果端到端時延是最低的，其一定能滿足流的最差時延約束。

3 基于重合度的離線流調(diào)度算法

在上文中，由于需要調(diào)度不同周期的業(yè)務(wù)流，引入了網(wǎng)絡(luò)周期的概念，并且，上文所述的在線調(diào)度算法分散地將業(yè)務(wù)流調(diào)度到各個基期中以使得剩余可調(diào)度空間最大。而在離線調(diào)度情況下，由于無需滿足調(diào)度計算的實時性要求，可以在上一章節(jié)所述在線算法的基礎(chǔ)上進行改進，從而在離線調(diào)度情況下獲得較優(yōu)解。在本章中，提出一種基于重合度的離線式調(diào)度算法，其使用禁忌搜索算法來對業(yè)務(wù)流進行調(diào)度。具體地，其嘗試以不同順序?qū)I(yè)務(wù)流進行調(diào)度，來提高調(diào)度結(jié)果的重合度，增大網(wǎng)絡(luò)剩余的可調(diào)度空間，以使得算法在在線調(diào)度時可以調(diào)度更多的業(yè)務(wù)流。

3.1 重合度

為了衡量調(diào)度結(jié)果的好壞，對于每一個鏈路e，定義了一個已調(diào)度空間指標(biāo)me，來表示該鏈路的調(diào)度結(jié)果在每一個基期的偏移的并集的時隙長度，該指標(biāo)的值越小，說明調(diào)度結(jié)果重合度越高，則調(diào)度方案越優(yōu)。如式(5)所示

(5)

例如，在圖4中，將方案(a)與方案(b)進行對比。顯然，在方案(b)中，由于Flow0與Flow1在該鏈路的預(yù)留窗口偏移一致，也就是說，F(xiàn)low0與Flow1的預(yù)留窗口偏移的并集小于方案(a)中的并集，即mb

本算法使用重合度來作為網(wǎng)絡(luò)調(diào)度結(jié)果評估的重要指標(biāo)，調(diào)度結(jié)果的重合度越高，表明該調(diào)度方案越優(yōu)。為了便于計算，對于每一個鏈路e，計算該鏈路每個基期的預(yù)留窗口偏移的并集，來作為評判指標(biāo)，記為已調(diào)度空間me。該指標(biāo)越小，則說明各個預(yù)留窗口的重合度越高。對于給定網(wǎng)絡(luò)的調(diào)度方案，該指標(biāo)等于網(wǎng)絡(luò)中重合度最低(即已調(diào)度空間最大)的端口的已調(diào)度空間指標(biāo)，如式(6)所示

mG=max{me}，fore∈G

(6)

對于某一條實時業(yè)務(wù)流fi，其評判指標(biāo)為其路徑上的每一條鏈路的重合度的平均值，如式(7)所示

mfi=avg{me}，fore∈ri

(7)

3.2 基于禁忌搜索算法的離線調(diào)度算法

在離線模式下，本文使用禁忌搜索算法來對實時業(yè)務(wù)流進行調(diào)度。為了使得算法在后續(xù)的在線調(diào)度過程中能夠調(diào)度更多的業(yè)務(wù)流，該算法選用已調(diào)度空間指標(biāo)mG(見式(6))來評估算法調(diào)度結(jié)果的性能，即，最小化網(wǎng)絡(luò)鏈路中最大的已調(diào)度空間，減小網(wǎng)絡(luò)總體的已調(diào)度空間，增大網(wǎng)絡(luò)的剩余可調(diào)度空間。

本算法采用的禁忌搜索算法架構(gòu)與文獻[10]相似，但在critical flow選擇、以及解的迭代過程有所不同。本文主要闡述這兩個過程，對于其它過程如初始解生成、鄰域生成等，這里不再贅述。

3.2.1 Critical Flow的選擇

傳統(tǒng)的算法一般使用流完成時間，即FlowSpan來定義Critical Flow，其中FlowSpan的含義指的是所有業(yè)務(wù)流中最慢完成傳輸?shù)牧鞯臅r間。而在本文中，由于引入了網(wǎng)絡(luò)周期的概念，使得業(yè)務(wù)流在各個網(wǎng)絡(luò)周期中都有分布，此時FlowSpan就失去了其原有的意義。在本文中，對于某一個給定的調(diào)度方案，采用已調(diào)度空間mG來評估調(diào)度方案的性能。而對于critical flow，類比于FlowSpan中最晚完成的業(yè)務(wù)流，其應(yīng)該是導(dǎo)致已調(diào)度空間mG縮小的實時業(yè)務(wù)流。

本算法根據(jù)式(7)來對每一條業(yè)務(wù)流計算其已調(diào)度空間指標(biāo)，即，該流路徑上的鏈路指標(biāo)的平均值。然后，根據(jù)選擇出的critical flow，在迭代過程中生成對應(yīng)的鄰域。

3.2.2 當(dāng)前解的迭代過程

在算法的每一次迭代過程中，都需要對鄰域中的每一個鄰居使用第2章所介紹的在線調(diào)度算法進行調(diào)度計算，即，按照該鄰居方案的實時業(yè)務(wù)流調(diào)度順序，以此使用算法1進行調(diào)度。然后，使用式(6)計算每一個鄰居節(jié)點的已調(diào)度空間，然后選擇最優(yōu)的(已調(diào)度空間指標(biāo)最小的)鄰居節(jié)點作為當(dāng)前解，然后繼續(xù)迭代，直到超過連續(xù)Y次迭代無法找到更優(yōu)解，停止迭代[10]。

4 實驗與分析

本節(jié)對上文所提出算法進行實驗，并將所調(diào)度結(jié)果在Omnet++仿真平臺上使用NeSTiNg[13]框架驗證算法的有效性。本文所使用算法為C++編寫，仿真環(huán)境為Ubuntu 18.04。

本文所采用的仿真網(wǎng)絡(luò)拓?fù)鋮⒖剂宋墨I[14]所使用的Medium-mesh網(wǎng)絡(luò)拓?fù)?，如圖5所示，其中交換機之間的網(wǎng)絡(luò)鏈路速率為1 GE，終端與交換機之間的網(wǎng)絡(luò)鏈路速率為100 Mbps。交換機處理時延tproc為1 μs，鏈路傳播時延tprop為1 μs。為保證數(shù)據(jù)準(zhǔn)確性及可靠性，對每次實驗運行了20次，然后計算這20次實驗的平均值，得到實驗的可靠結(jié)果。

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

4.1 在線調(diào)度實驗

本節(jié)實驗主要驗證在線調(diào)度算法在不同實驗設(shè)置下能夠調(diào)度的業(yè)務(wù)流數(shù)量。具體的實驗流程為，使算法在線運行并隨機地生成不同數(shù)據(jù)特征的實時業(yè)務(wù)流(其中源節(jié)點與目標(biāo)節(jié)點隨機選取)，當(dāng)算法無法求解出調(diào)度結(jié)果時停止運行，得到此時網(wǎng)絡(luò)中已調(diào)度的實時業(yè)務(wù)流的數(shù)量。

4.1.1 實驗1-1：流周期影響

本實驗主要研究業(yè)務(wù)流周期大小對可調(diào)度流數(shù)量的影響。在該實驗中，設(shè)置了兩個實驗，其中實時業(yè)務(wù)流的周期大小設(shè)置見表2，流的其它參數(shù)設(shè)置為：源節(jié)點與目標(biāo)節(jié)點隨機選取，數(shù)據(jù)幀大小設(shè)置為100 Bytes?；谥翟O(shè)置為100 μs。

表2 實驗1-1實時流應(yīng)用周期設(shè)置

實驗結(jié)果見表3，在該網(wǎng)絡(luò)拓?fù)湎?，Case 3能夠調(diào)度的流數(shù)量遠超過其它兩個案例。這是由于Case 3中的實時流應(yīng)用周期相比Case 1及Case 2較大，而應(yīng)用周期較大的流占用的時隙資源較小，與其它流的沖突約束(見約束1)較少，容易取得較高的流調(diào)度數(shù)量。

表3 應(yīng)用周期對流調(diào)度數(shù)量的影響

注意到Case 3中的流應(yīng)用周期為Case 2中的流應(yīng)用周期的10倍，即，平均來說，Case 3中的每一條流所占用帶寬為Case 2的十分之一。直覺地，那么Case 3所能調(diào)度的流的數(shù)量應(yīng)為Case 2的10倍，但實驗結(jié)果顯示其能夠調(diào)度的流數(shù)量卻達到了Case 2的將近20倍。這是由于盡管Case 3中的業(yè)務(wù)流占用帶寬為Case 2中的十分之一，但是其可以分散到不同的基期中調(diào)度，受到的約束較小，相對地，其解空間也相比Case 2大。

4.1.2 實驗1-2：基期大小影響

如2.1節(jié)所述，基期值的設(shè)置會影響可調(diào)度流數(shù)量，基期值太小會使得調(diào)度結(jié)果過于分散，產(chǎn)生大量的時隙碎片而減小了解空間。在該實驗中，維持實時流的流量特征(實驗設(shè)置為Case 2)不變，而改變基期值的大小見表4。

表4 實驗1-2基期值設(shè)置

對于該實驗設(shè)置的業(yè)務(wù)流，其應(yīng)用周期的最大公約數(shù)是100 μs，由于基期必須整除所有流的應(yīng)用周期，所以此時基期所能設(shè)置的最大值為100 μs。

實驗結(jié)果如圖6所示，隨著基期從10 μs到100 μs不斷增大，網(wǎng)絡(luò)平均可調(diào)度流的數(shù)量也不斷增多。當(dāng)網(wǎng)絡(luò)周期達到100 μs時，流調(diào)度數(shù)量達到最大，達到了最差情況下(Case 4)的176%。

圖6 基期大小對流調(diào)度數(shù)量的影響

實驗結(jié)果顯示，基期大小對網(wǎng)絡(luò)可調(diào)度性有較大影響。在實際部署中，算法的基期應(yīng)設(shè)置得較大，來保證網(wǎng)絡(luò)的可調(diào)度性。由于算法是在線運行的，未來的實時業(yè)務(wù)流數(shù)據(jù)特征是未知的，此時應(yīng)估計所可能出現(xiàn)的業(yè)務(wù)流應(yīng)用周期的值大小，并將基期值設(shè)置為其最大公約數(shù)。

4.1.3 實驗1-3：調(diào)度計算時間

本文提出了一種在線調(diào)度算法，由于算法需要在線運行，所以對實時流調(diào)度計算耗費的時間成為了一個重要的指標(biāo)，本實驗主要研究該算法在在線調(diào)度情況下的調(diào)度計算時間。

本實驗選取Case3的實時流生成設(shè)置，其中數(shù)據(jù)幀大小為100 Bytes，基期為1 ms。

實驗結(jié)果如圖7所示，圖中數(shù)據(jù)已做平滑處理。隨著已調(diào)度流數(shù)量的增加，算法調(diào)度計算所耗費的時間也呈一個上升趨勢，并且其波動也越大。這是因為當(dāng)網(wǎng)絡(luò)中已調(diào)度的實時流數(shù)量較多時，對于當(dāng)前實時流，所受到的約束(見約束1式(2))增多，其所可能受到的沖突也就越多，所以計算次數(shù)增加，耗費時間增大。

圖7 流調(diào)度耗時

總體來說，對于單條實時業(yè)務(wù)流，算法調(diào)度計算平均只需要3.98 ms的時間，滿足算法在線運行的要求。

4.2 離線調(diào)度實驗

本實驗對第3章提出的離線調(diào)度算法進行實驗驗證。在該實驗中，首先使用在線調(diào)度器對業(yè)務(wù)流進行在線調(diào)度，并不斷生成業(yè)務(wù)流。當(dāng)在線調(diào)度計算失敗時，改用離線調(diào)度器對前面的所有業(yè)務(wù)流重新進行調(diào)度計算。調(diào)度成功后，在該調(diào)度結(jié)果的基礎(chǔ)上，繼續(xù)使用在線調(diào)度器為后續(xù)的業(yè)務(wù)流進行在線調(diào)度。直到離線調(diào)度器也無法調(diào)度時則停止計算，實驗流程如圖8所示。該實驗可以驗證本文所述離線算法的有效性，并且同時具有實際意義。例如，在實際部署應(yīng)用中，由于未來增加的業(yè)務(wù)流是未知的，所以首先使用在線調(diào)度算法來進行增量式調(diào)度。當(dāng)在線調(diào)度算法已經(jīng)無法正常調(diào)度業(yè)務(wù)流時，需要對原來的已調(diào)度業(yè)務(wù)流重新進行計算以使得所有業(yè)務(wù)流都可以得到調(diào)度。

圖8 實驗2流程

其中，實時業(yè)務(wù)流的流量特征見表5，基期大小均設(shè)置為100 μs，業(yè)務(wù)流的幀數(shù)據(jù)大小在對應(yīng)范圍內(nèi)取平均分布。

表5 實驗2實時流設(shè)置

實驗結(jié)果如圖9所示，可以看到，相比平均僅能調(diào)度40條業(yè)務(wù)流左右的在線調(diào)度，離線調(diào)度的調(diào)度業(yè)務(wù)流數(shù)量平均提高了58%。并且，觀察到使用離線調(diào)度成功調(diào)度計算的次數(shù)為1～2次。即，平均來說，每次使用離線調(diào)度器能使得調(diào)度流的數(shù)量增加29%～58%。這反映了，對于某一條關(guān)鍵業(yè)務(wù)流，該業(yè)務(wù)流可能受到的約束較多，當(dāng)在線調(diào)度已經(jīng)無法對其求解出調(diào)度結(jié)果時，此時使用離線調(diào)度可以重新規(guī)劃出一個較優(yōu)的調(diào)度結(jié)果，從而使得算法可以在線調(diào)度更多的業(yè)務(wù)流，優(yōu)化效果較為顯著。

5 結(jié)束語

本文對時間敏感網(wǎng)絡(luò)No-wait約束下的實時業(yè)務(wù)流調(diào)度問題進行研究，提出了一種在線增量式流調(diào)度方法，該方法基于網(wǎng)絡(luò)周期，可以對不同應(yīng)用周期的實時業(yè)務(wù)流進行增量式調(diào)度。并且，為了提高網(wǎng)絡(luò)的可調(diào)度流數(shù)量，該算法將調(diào)度結(jié)果分散到各個網(wǎng)絡(luò)周期。然后，提出了一種基于重合度的離線調(diào)度算法，在離線模式下，減小調(diào)度結(jié)果的已調(diào)度空間，以增大剩余可調(diào)度空間，為后續(xù)的在線調(diào)度過程提供了良好的基礎(chǔ)，從而提高了業(yè)務(wù)流的可調(diào)度數(shù)量。

當(dāng)前基于No-wait約束實現(xiàn)的調(diào)度器由于約束太大，難以調(diào)度較多的業(yè)務(wù)流。在后續(xù)研究中，將研究放松No-wait約束來對業(yè)務(wù)流進行調(diào)度，以提高網(wǎng)絡(luò)的可調(diào)度性能。