基于時(shí)間觸發(fā)光纖通道網(wǎng)絡(luò)的交換調(diào)度算法

白 焱，孫萬(wàn)錄，宋 平，李 偉

(1. 中國(guó)科學(xué)院沈陽(yáng)計(jì)算技術(shù)研究所有限公司 沈陽(yáng) 110042；2. 空裝駐沈陽(yáng)地區(qū)第一軍事代表室 沈陽(yáng) 110051；3. 沈陽(yáng)航盛科技有限責(zé)任公司 沈陽(yáng) 110051)

時(shí)間觸發(fā)光纖通道(time trigger fiber channel,TTFC)具有全局時(shí)鐘和預(yù)定義的傳輸時(shí)間表[1]，通過(guò)解決一部分光纖通道(fiber channel, FC)網(wǎng)絡(luò)數(shù)據(jù)交換的沖突問(wèn)題，改善了重要業(yè)務(wù)的傳輸確定性和實(shí)時(shí)性，提升了航電任務(wù)系統(tǒng)的整體性能，成為了航電網(wǎng)絡(luò)通信的發(fā)展方向。

TTFC 網(wǎng)絡(luò)支持時(shí)間觸發(fā)(time trigger, TT)和事件觸發(fā)(events trigger, ET)多種優(yōu)先級(jí)業(yè)務(wù)。TT業(yè)務(wù)具有最高優(yōu)先級(jí)，通過(guò)離線通信調(diào)度保證其準(zhǔn)確性，TT 業(yè)務(wù)可在定義的延遲和抖動(dòng)范圍內(nèi)在TTFC交換網(wǎng)絡(luò)上無(wú)沖突地精確傳送[2]。ET 業(yè)務(wù)按優(yōu)先級(jí)從高到底可劃分為流量控制(rate-constrained, RC)和盡力而為(best-effort, BE)兩種不同的優(yōu)先級(jí)業(yè)務(wù)[3]。TTFC 交換機(jī)是TTFC 網(wǎng)絡(luò)的關(guān)鍵組件，TTFC交換機(jī)在傳統(tǒng)FC 交換機(jī)基礎(chǔ)上增加了時(shí)鐘觸發(fā)TT 業(yè)務(wù)的數(shù)據(jù)交換。傳統(tǒng)FC 交換機(jī)的實(shí)現(xiàn)由于受硬件的交換加速能力限制，大多采用無(wú)阻塞的交叉開(kāi)關(guān)矩陣(crossbar)式直通交換結(jié)構(gòu)[4]，并根據(jù)信元緩存位置的不同分為輸入和輸出兩種排隊(duì)方式。而輸入隊(duì)列會(huì)出現(xiàn)線頭(head of line, HOL)堵塞現(xiàn)象，通常采用虛擬輸出隊(duì)列(virtual output queue, VOQ)的方法來(lái)解決HOL 問(wèn)題[5]。

為提升交換轉(zhuǎn)發(fā)效率，降低轉(zhuǎn)發(fā)延遲，減少交換調(diào)度開(kāi)銷，F(xiàn)C 交換機(jī)采用針對(duì)多優(yōu)先級(jí)的變長(zhǎng)調(diào)度算法來(lái)實(shí)現(xiàn)交換調(diào)度。OSP (orthogonal subspace projection)、p-iDRR (prioritized iDRR)等算法雖支持多優(yōu)先級(jí)，但算法設(shè)計(jì)時(shí)采用固定長(zhǎng)度的信元，其應(yīng)用變長(zhǎng)信元交換時(shí)會(huì)引入額外開(kāi)銷。RRM 算法在輸出端指針同步時(shí)會(huì)增加性能的損耗等，這些問(wèn)題在vp-RRM 算法中已得到了很好地解決。

在TTFC 網(wǎng)絡(luò)中，由于TT 業(yè)務(wù)的加入，占用了交換端口的部分流量，同時(shí)TT 業(yè)務(wù)對(duì)各端口流量的占用不同，導(dǎo)致在進(jìn)行ET 業(yè)務(wù)數(shù)據(jù)交換時(shí)，端口流量也不均勻。目前對(duì)于TTFC 網(wǎng)絡(luò)的研究，大多從網(wǎng)絡(luò)模型仿真的角度對(duì)網(wǎng)絡(luò)的實(shí)現(xiàn)算法進(jìn)行分析，暫沒(méi)有文獻(xiàn)結(jié)合TTFC 網(wǎng)絡(luò)特點(diǎn)，對(duì)ET 業(yè)務(wù)的交換調(diào)度效率進(jìn)行深入分析[6]。vp-RRM 算法基于端口序號(hào)進(jìn)行輪詢調(diào)度，每個(gè)隊(duì)列的輸出是無(wú)差別的，但流量的非均勻分布會(huì)導(dǎo)致個(gè)別隊(duì)列等待時(shí)間較長(zhǎng)，吞吐性能變差[7]。因此，本文在加權(quán)輪詢調(diào)度算法的基礎(chǔ)上，提出了基于流量自適應(yīng)的多優(yōu)先級(jí)變長(zhǎng)輪詢調(diào)度算法(traffic adaptive variablelength priority round robinmatching, tavp-RRM)，該算法針對(duì)非均勻流量狀態(tài)下的交換調(diào)度算法進(jìn)行改進(jìn)，使流量大的端口得到更多的調(diào)度機(jī)會(huì)，以此提升網(wǎng)絡(luò)的吞吐效率。

1 tavp-RRM 算法

tavp-RRM 算法可基于端口流量隊(duì)列的長(zhǎng)度自適應(yīng)調(diào)整其請(qǐng)求優(yōu)先級(jí)，使負(fù)載量大的端口優(yōu)先進(jìn)行數(shù)據(jù)交換，從而提升TTFC 網(wǎng)絡(luò)的吞吐率。其優(yōu)點(diǎn)包括：支持非定長(zhǎng)信元、非固定時(shí)隙、支持單播和廣播隊(duì)列、采用流水線工作和使用VOQ 等。

1.1 tavp-RRM 算法原理

算法原理如下：

1) 為了提升TTFC 網(wǎng)絡(luò)的有序性，廣播和組播業(yè)務(wù)均規(guī)劃為TT 業(yè)務(wù)，ET 業(yè)務(wù)僅處理單播業(yè)務(wù)，因此在本文中，不討論該算法對(duì)組播和廣播業(yè)務(wù)的適用性。

2) 支持多優(yōu)先級(jí)調(diào)度。TTFC 網(wǎng)絡(luò)的ET 業(yè)務(wù)按優(yōu)先級(jí)分為RC 和BE 兩種業(yè)務(wù)。如圖1 所示，業(yè)務(wù)信元傳輸至TTFC 交換機(jī)后，將依據(jù)其優(yōu)先級(jí)存入各個(gè)VOQ 中。VOQ 向輸出端口發(fā)起請(qǐng)求時(shí)，VOQ 的優(yōu)先級(jí)會(huì)根據(jù)其隊(duì)列長(zhǎng)度及等待時(shí)間進(jìn)行調(diào)整。優(yōu)先級(jí)從高到低依次為P3、P2、P1、P0，RC 業(yè)務(wù)的起始優(yōu)先級(jí)為P2，可提升的優(yōu)先級(jí)為P3，BE 業(yè)務(wù)的起始優(yōu)先級(jí)為P0，可提升的優(yōu)先級(jí)為P1。

圖1 VOQ 架構(gòu)示意圖

3) 輸出端口同時(shí)收到多個(gè)輸入端口的請(qǐng)求時(shí)，對(duì)優(yōu)先級(jí)最高的輸入端口先進(jìn)行授權(quán)。

tavp-RRM 調(diào)度算法在研發(fā)階段即注重硬件的可實(shí)現(xiàn)性，經(jīng)過(guò)多次迭代，完成輸入、輸出端口的最優(yōu)匹配[8]。通過(guò)在每個(gè)輸入、輸出端口設(shè)置多個(gè)仲裁器，通過(guò)循環(huán)優(yōu)先級(jí)仲裁來(lái)依次匹配所有有效的輸入和輸出，以保證每一次迭代的獨(dú)立性。

1.2 tavp-RRM 算法執(zhí)行過(guò)程

tavp-RRM 算法的執(zhí)行過(guò)程與 RRM 類似，分為“請(qǐng)求?授權(quán)?接受”，步驟如下：

1) 請(qǐng)求

輸入端口接收到信元后，會(huì)向信元的輸出端口發(fā)起包含當(dāng)前數(shù)據(jù)優(yōu)先級(jí)的請(qǐng)求，請(qǐng)求的優(yōu)先級(jí)由3 種因素決定，分別為ET 業(yè)務(wù)的優(yōu)先級(jí)、當(dāng)前VOQ 的隊(duì)列長(zhǎng)度及當(dāng)前VOQ 的等待時(shí)間。圖2 給出了ET 業(yè)務(wù)VOQ 隊(duì)列優(yōu)先級(jí)的確定流程。

圖2 ET 業(yè)務(wù)VOQ 隊(duì)列優(yōu)先級(jí)的確定流程

基于以下原則來(lái)確定閾值：

① 隊(duì)列長(zhǎng)度的閾值點(diǎn)距離隊(duì)列滿不小于2 個(gè)FC最長(zhǎng)幀的空間，防止閾值生效太晚，從而導(dǎo)致對(duì)外部輸入端產(chǎn)生流控；

② 隊(duì)列長(zhǎng)度的閾值點(diǎn)應(yīng)大于隊(duì)列半滿的位置，避免閾值被頻繁觸發(fā)；

③ 隊(duì)列排隊(duì)時(shí)間閾值應(yīng)小于系統(tǒng)可接收的最大延遲。

本文在仿真及實(shí)驗(yàn)驗(yàn)證過(guò)程中，以隊(duì)列深度的3/4 作為隊(duì)列長(zhǎng)度閾值，以100 μs 作為隊(duì)列排隊(duì)時(shí)間閾值。

2) 授權(quán)

每個(gè)輸出端口處設(shè)有1 個(gè)調(diào)度器，調(diào)度器通過(guò)輪詢調(diào)度算法來(lái)匹配多個(gè)端口的請(qǐng)求，在均勻業(yè)務(wù)狀態(tài)下具有良好的公平性。由于輸入端的業(yè)務(wù)數(shù)據(jù)按照業(yè)務(wù)類型(RC 或BE)分配隊(duì)列緩存，因此每個(gè)輸出端口對(duì)不同類型的業(yè)務(wù)通過(guò)輪詢指針r0 和r1 分別維護(hù)其調(diào)度狀態(tài)。r1 對(duì)應(yīng)RC 業(yè)務(wù)，優(yōu)先級(jí)為P2 或P3；r0 對(duì)應(yīng)BE 業(yè)務(wù)，優(yōu)先級(jí)為P0 或P1。調(diào)度器進(jìn)行調(diào)度時(shí)，先過(guò)濾出當(dāng)前最高優(yōu)先級(jí)的請(qǐng)求，在根據(jù)r0 或r1 的當(dāng)前位置按順序開(kāi)始輪詢查找，對(duì)找到的第一個(gè)請(qǐng)求進(jìn)行授權(quán)，并通過(guò)r0 或r1 更新到當(dāng)前授權(quán)位置的下一個(gè)位置處。

3) 接受

輸入端口會(huì)同時(shí)向多個(gè)輸出端口發(fā)起調(diào)度請(qǐng)求，當(dāng)輸入端口同時(shí)接收到多個(gè)端口的授權(quán)時(shí)，同一時(shí)刻只能接受一個(gè)授權(quán)。因此，輸入端口需要對(duì)接收到的授權(quán)進(jìn)行仲裁來(lái)選擇最終接受方。輸入端口的接受仲裁對(duì)不同類型的業(yè)務(wù)通過(guò)輪詢指針c0 和c1 分別維護(hù)其仲裁狀態(tài)。c1 對(duì)應(yīng)RC 業(yè)務(wù)，優(yōu)先級(jí)為P2 或P3；c0 對(duì)應(yīng)BE 業(yè)務(wù)，優(yōu)先級(jí)為P0 或P1。仲裁器進(jìn)行仲裁時(shí)，先過(guò)濾出當(dāng)前最高優(yōu)先級(jí)的請(qǐng)求，在根據(jù)c0 或c1 的當(dāng)前位置按順序開(kāi)始輪詢查找，對(duì)找到的第一個(gè)授權(quán)進(jìn)行接受，并通過(guò)c0 或c1 更新到當(dāng)前授權(quán)位置的下一個(gè)位置處。圖3 為一個(gè)4×4 端口的調(diào)度過(guò)程，在請(qǐng)求授權(quán)階段，輸出端口 1 在優(yōu)先級(jí) P2、P3 之間選擇高優(yōu)先級(jí)P3 對(duì)應(yīng)的輸入端口3；輸出端口2 在3 路BE 業(yè)務(wù)中選擇輸入端口，輸入端口1 由于其隊(duì)列長(zhǎng)度大于門限值，請(qǐng)求將優(yōu)先級(jí)調(diào)整為為P1，因此選擇高優(yōu)先級(jí)P1 對(duì)應(yīng)的輸入端口1；輸出端口3 在兩個(gè)相同優(yōu)先級(jí) P0 端口間選擇，此時(shí)輸出端口3 對(duì)應(yīng)BE 業(yè)務(wù)的r0=3，按照輪詢機(jī)制，最終選擇輸入端口4 進(jìn)行授權(quán)；輸出端口4 在優(yōu)先級(jí)P1、P0 間選擇高優(yōu)先級(jí)P1 對(duì)應(yīng)的輸入端口1。

圖3 4×4 端口的調(diào)度過(guò)程

接受階段，輸入端口1 同時(shí)收到輸出端口2 和輸出端口4 的授權(quán)，由于兩個(gè)授權(quán)的優(yōu)先級(jí)相同均為P1，按照輪詢機(jī)制從當(dāng)前BE 的指針c0=3 啟動(dòng)輪詢。輸入端口1 優(yōu)先查詢到輸出端口4 的授權(quán)，因此選擇輸出端口4 的授權(quán)進(jìn)行接受。輸入端口3 和4 由于僅接收了1 個(gè)授權(quán)，直接接受即可。

2 仿真分析

使用計(jì)算機(jī)仿真可以大幅降低crossbar 調(diào)度算法性能分析的難度，本節(jié)將通過(guò)計(jì)算機(jī)仿真來(lái)分析tavp-RRM 算法的吞吐量。吞吐量是指輸出端口的平均利用率，即在一個(gè)時(shí)隙內(nèi)平均發(fā)送的信元數(shù)量。在分析吞吐量性能時(shí)，本文將vp-RRM 算法作為比較的對(duì)象，vp-RRM 算法和tavp-RRM 的差異在于對(duì)優(yōu)先級(jí)的管理不同，下面選取均勻業(yè)務(wù)流和非均勻業(yè)務(wù)流對(duì)兩種算法的吞吐量性能進(jìn)行對(duì)比。

1) 均勻業(yè)務(wù)流

輸入端負(fù)載均相同，即 γi=γ，所有業(yè)務(wù)流在VOQ 中均勻分布。均勻業(yè)務(wù)流模型下，tavp-RRM和vp-RRM 的吞吐量均為相同的恒定值：

2) 非均勻業(yè)務(wù)流

業(yè)務(wù)流模型1 的算法吞吐量對(duì)比如圖4 所示，根據(jù)式(2)可推算得知，1 個(gè)輸出端口同時(shí)只轉(zhuǎn)發(fā)兩個(gè)輸入端口的數(shù)據(jù)，在交換調(diào)度時(shí)競(jìng)爭(zhēng)較少，轉(zhuǎn)發(fā)效率本來(lái)較高，基于端口流量隊(duì)列的長(zhǎng)度自適應(yīng)調(diào)整其請(qǐng)求優(yōu)先級(jí)的功能(traffic adaptive, TA)作用不明顯，vp-RRM 和tavp-RRM 仿真結(jié)果基本一致。

圖4 業(yè)務(wù)流模型1 的算法吞吐量對(duì)比

圖5 展示了在16×16 的crossbar 中tavp-RRM和vp-RRM 算法的吞吐量。從圖中可以看到，當(dāng)w=0 時(shí)，業(yè)務(wù)流為均勻業(yè)務(wù)流，tavp-RRM 算法的吞吐量與vp-RRM 算法一致；當(dāng)w=1 時(shí)，業(yè)務(wù)流集中到同一個(gè)端口，達(dá)到滿額負(fù)荷，tavp-RRM 算法的吞吐量與vp-RRM 算法相同。其他狀態(tài)下tavp-RRM 算法的吞吐量性能始終優(yōu)于vp-RRM，且w在0.5 附近時(shí)，性能差異達(dá)到最大。圖5 的仿真結(jié)果說(shuō)明tavp-RRM 算法相對(duì)于vp-RRM 算法，在多個(gè)輸入端口向同一個(gè)輸出端口發(fā)生轉(zhuǎn)發(fā)競(jìng)爭(zhēng)，且流量不均勻時(shí)，具有更高的交換調(diào)度效率。

圖5 業(yè)務(wù)流模型2 的算法吞吐量對(duì)比

3 實(shí)驗(yàn)驗(yàn)證

本文采用復(fù)旦微電子公司的JFM7K325TFPGA設(shè)計(jì)了4×4 端口，速率為2.125 Gb/s 的TTFC 交換機(jī)。為了進(jìn)行算法對(duì)比測(cè)試，TA 功能支持通過(guò)軟件配置進(jìn)行使能或關(guān)閉。

通過(guò)對(duì)交換機(jī)的TT 業(yè)務(wù)轉(zhuǎn)發(fā)進(jìn)行規(guī)劃，使交換機(jī)各端口的TT 業(yè)務(wù)占用不同的帶寬。TT 業(yè)務(wù)在端口1 至端口4 的輸入帶寬占用分別為9%、12%、15%和18%，輸出帶寬在非輸入端口均勻分布。

使用JSDU 公司的XgigLoadTester 測(cè)試儀對(duì)TTFC 交換機(jī)進(jìn)行ET 業(yè)務(wù)的吞吐量測(cè)試，由于測(cè)試儀不支持TT 業(yè)務(wù)注入，為了在測(cè)試中模擬TT業(yè)務(wù)引入的非均勻性，TTFC 交換機(jī)采用如下設(shè)計(jì)：初始化TTFC 交換機(jī)各端口的TT 調(diào)度配置，并在TT 業(yè)務(wù)的轉(zhuǎn)發(fā)時(shí)隙，強(qiáng)制TT 轉(zhuǎn)發(fā)路徑處于忙狀態(tài)，時(shí)隙內(nèi)不進(jìn)行ET 業(yè)務(wù)的轉(zhuǎn)發(fā)[10]。

具體測(cè)試說(shuō)明如下：

1)各端口激勵(lì)數(shù)據(jù)均采用幀長(zhǎng)為1024 B 的ET 幀；

2)測(cè)試拓?fù)洳捎脠D6 所示的不帶自環(huán)的全網(wǎng)絡(luò)拓?fù)淠Ｐ?。受測(cè)試儀功能限制，VOQ 分布采用均勻分布，通過(guò)TT 業(yè)務(wù)的影響引入非均勻因素；

圖6 測(cè)試拓?fù)淠Ｐ?/p>

3)各端口測(cè)試激勵(lì)初始為100%負(fù)載；

4)分別在TA 功能使能和關(guān)閉的狀態(tài)下進(jìn)行測(cè)試。

各端口在未開(kāi)啟TA 功能和開(kāi)啟TA 功能后的對(duì)比如表1 所示。tavp-RRM 算法的實(shí)測(cè)吞吐量性能優(yōu)于vp-RRM，吞吐量提升在5%以上，表明TA功能對(duì)于非均勻流量環(huán)境下的吞吐量有改善作用。

表1 實(shí)測(cè)結(jié)果對(duì)比

4 結(jié) 束 語(yǔ)

本文根據(jù)TTFC 網(wǎng)絡(luò)中ET 業(yè)務(wù)流量不均勻的特點(diǎn)，提出一種多優(yōu)先級(jí)交換調(diào)度方案，基于端口流量隊(duì)列長(zhǎng)度進(jìn)行優(yōu)先級(jí)的自適應(yīng)調(diào)整，使帶寬資源緊張的VOQ 得到更多的授權(quán)機(jī)會(huì)，從而改善TTFC 網(wǎng)絡(luò)的吞吐量性能，提高交換調(diào)度效率，更加適用于TTFC 網(wǎng)絡(luò)的事件觸發(fā)業(yè)務(wù)的交換調(diào)度。