丁永強(qiáng)，王 勇，譚小虎，褚文奎，方 挺

（1.空軍工程大學(xué)第一航空學(xué)院，河南 信陽 464000；2.空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

光纖通道調(diào)度算法研究*

丁永強(qiáng)1，王 勇2，譚小虎2，褚文奎2，方 挺2

（1.空軍工程大學(xué)第一航空學(xué)院，河南 信陽 464000；2.空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

針對(duì)光纖通道協(xié)議中沒有規(guī)定數(shù)據(jù)調(diào)度算法的問題，在滿足系統(tǒng)實(shí)時(shí)性的情況下，經(jīng)過對(duì)FC-AE-ASM協(xié)議的深入分析，提出一種基于令牌桶的優(yōu)先級(jí)和加權(quán)輪轉(zhuǎn)相結(jié)合的調(diào)度算法，同時(shí)給出了權(quán)值分配和輪轉(zhuǎn)周期的確定方法。在以消息的延遲率作為算法性能的評(píng)價(jià)指標(biāo)的基礎(chǔ)上，經(jīng)過仿真，對(duì)調(diào)度算法的性能進(jìn)行了驗(yàn)證，結(jié)果顯示出該算法可以很好地滿足航空電子系統(tǒng)實(shí)時(shí)性要求。

光纖通道，權(quán)值分配，輪轉(zhuǎn)周期，延時(shí)率

0 引言

光纖通道（Fiber Channel，F(xiàn)C）作為航空電子系統(tǒng)統(tǒng)一網(wǎng)絡(luò)的理想?yún)f(xié)議［1］，它具有高可靠性、高帶寬以及高實(shí)時(shí)性的特點(diǎn)，可以滿足航電系統(tǒng)對(duì)延遲率、誤碼率的要求。作為研究將光纖通道應(yīng)用于航空電子環(huán)境的分委員會(huì)，制定了光纖通道航空電子環(huán)境（Fiber Channel Avionics Environment，F(xiàn)C-AE）［2］的草案。主要作用就是支持以FC作為標(biāo)準(zhǔn)的航空電子專用系統(tǒng)［3］。作為光纖通道協(xié)議簇中的FC-AEASM支持航空電子系統(tǒng)中傳感器、處理器和顯示器間的低延遲、安全和確定的通信［4］，但是該協(xié)議卻沒有給出網(wǎng)絡(luò)中消息的調(diào)度算法，在滿足航空電子環(huán)境中對(duì)實(shí)時(shí)性、延時(shí)性和大的網(wǎng)絡(luò)吞吐能力的要求下，如何合理地安排節(jié)點(diǎn)上數(shù)據(jù)的發(fā)送和接收是一個(gè)很值得思考的問題［5］。

結(jié)合國(guó)內(nèi)的研究情況來看，主要集中在網(wǎng)絡(luò)傳輸?shù)目煽啃浴⑼負(fù)浣Y(jié)構(gòu)、終端協(xié)議芯片等方面。文獻(xiàn)［6-8］以網(wǎng)絡(luò)任務(wù)模型為基礎(chǔ)，建立了可靠性模型，同時(shí)針對(duì)光纖通道3種拓?fù)浣Y(jié)構(gòu)，推導(dǎo)出可靠性的表達(dá)式；文獻(xiàn)［9］基于航電系統(tǒng)提出一種新型串行網(wǎng)絡(luò)結(jié)構(gòu)，同時(shí)進(jìn)行建模和仿真分析；文獻(xiàn)［10］針對(duì)FC協(xié)議，設(shè)計(jì)實(shí)現(xiàn)了終端協(xié)議芯片，測(cè)試結(jié)果表明滿足協(xié)議要求；針對(duì)網(wǎng)絡(luò)中消息的發(fā)送控制算法，文獻(xiàn)［11］提出了基于實(shí)時(shí)排隊(duì)論的調(diào)度算法，雖然它借助延時(shí)率可以反映系統(tǒng)實(shí)時(shí)性，但對(duì)于重負(fù)載以及搶占情況過多的情況下，開銷大的同時(shí)也不一定滿足系統(tǒng)實(shí)時(shí)性要求。

基于以上分析，提出了加權(quán)輪詢調(diào)度算法（WRR）加優(yōu)先級(jí)隊(duì)列調(diào)度算法（PQ）相結(jié)合的調(diào)度算法，既很好地調(diào)度高優(yōu)先級(jí)的緊急任務(wù)，又可以防止低優(yōu)先級(jí)任務(wù)被餓死的現(xiàn)象發(fā)生，最后經(jīng)過對(duì)調(diào)度算法實(shí)時(shí)性仿真，驗(yàn)證了該算法可以很好地滿足現(xiàn)在的航空電子系統(tǒng)對(duì)實(shí)時(shí)性的需求。

1 FC-AE-ASM網(wǎng)絡(luò)建模

FC-AE-ASM協(xié)議規(guī)定了支持FC網(wǎng)絡(luò)協(xié)議的上層數(shù)據(jù)特征，但沒有給出網(wǎng)絡(luò)中消息的調(diào)度方式，在這首先定義網(wǎng)絡(luò)模型結(jié)構(gòu)和FC-AE-ASM的數(shù)據(jù)特征。

1.1 網(wǎng)絡(luò)結(jié)構(gòu)

交換式網(wǎng)絡(luò)結(jié)構(gòu)以其強(qiáng)大的互連功能和提供更多的冗余帶寬，成為新一代航空電子系統(tǒng)的主要拓?fù)浣Y(jié)構(gòu)，所以在本文中主要討論交換式網(wǎng)絡(luò)中的FC-AE-ASM消息調(diào)度。網(wǎng)絡(luò)是由FC交換機(jī)和通信終端組成，采用默認(rèn)方式登錄，節(jié)點(diǎn)間消息傳遞使用三類服務(wù)，同時(shí)交換機(jī)采用動(dòng)態(tài)靜態(tài)相結(jié)合的路由策略。發(fā)送消息終端隨機(jī)發(fā)送單播、多播或廣播消息，在網(wǎng)絡(luò)中允許多個(gè)節(jié)點(diǎn)同時(shí)發(fā)送只含有一個(gè)數(shù)據(jù)幀的消息，接收終端只需根據(jù)數(shù)據(jù)表示符來確定數(shù)據(jù)是否是自己所需要以及該條數(shù)據(jù)的含義即可，不用區(qū)分發(fā)消息的終端是什么。網(wǎng)絡(luò)結(jié)構(gòu)模型如圖1所示。

1.2 數(shù)據(jù)模型

在航電網(wǎng)絡(luò)中所有消息的格式和長(zhǎng)度都是固定的，即采用標(biāo)準(zhǔn)的數(shù)據(jù)幀，每條數(shù)據(jù)根據(jù)其唯一的32位數(shù)據(jù)ID來識(shí)別幀的內(nèi)容，標(biāo)準(zhǔn)幀格式如圖2所示。每條數(shù)據(jù)相應(yīng)代表一條數(shù)據(jù)流，網(wǎng)絡(luò)中的消息大部分為周期消息，即使是非周期消息也可以確定它發(fā)送的最大時(shí)間間隔，對(duì)于任意數(shù)據(jù)流Si，給出如下定義：第i個(gè)數(shù)據(jù)流的長(zhǎng)度用Ci表示；數(shù)據(jù)產(chǎn)生的周期表示為Pi，Pmin為周期最小值；數(shù)據(jù)允許的最大延時(shí)為Di，一般取Pi=Di；每條鏈路的傳輸速率用v表示（假設(shè)每條鏈路的傳輸速率相同）；第i個(gè)數(shù)據(jù)流對(duì)鏈路的占用要求表示為Ui，Ui=（Ci/v）/Pi，網(wǎng)絡(luò)總的鏈路占用率為每條鏈路的占用率之和，表示為。

1.3 實(shí)時(shí)調(diào)度輪轉(zhuǎn)約束條件

強(qiáng)實(shí)時(shí)條件下，當(dāng)算法為消息i分配的權(quán)值wi滿足下面兩個(gè)條件時(shí)就可以實(shí)現(xiàn)強(qiáng)實(shí)時(shí)的調(diào)度。

1.3.1 輪詢權(quán)值的約束條件

其中TRL表示信道輪轉(zhuǎn)周期，取值小于Pmin并且為正整數(shù)；M為強(qiáng)實(shí)時(shí)的信道個(gè)數(shù)。

1.3.2 時(shí)限的約束條件：

在任意時(shí)間間隔t內(nèi)，消息i發(fā)送的最小時(shí)間量：

處于消息集合中的每條消息在其允許的最小延遲時(shí)間內(nèi)有足夠的時(shí)間被發(fā)送，即就是滿足：

2 消息調(diào)度算法

航空電子系統(tǒng)中的數(shù)據(jù)以周期性任務(wù)模型來傳輸。消息的類型一般分為緊急消息、周期性消息和數(shù)據(jù)塊消息。在每個(gè)終端節(jié)點(diǎn)中設(shè)置3個(gè)不同優(yōu)先級(jí)隊(duì)列，消息按照優(yōu)先級(jí)和允許最大延遲時(shí)間從小到大進(jìn)行排隊(duì)為M1，M2，…，Mn。它們構(gòu)成一個(gè)等待傳輸隊(duì)列集合 M={M1，M2，…，Mn}。一般情況下，消息產(chǎn)生時(shí)間表示為Tscr，消息到達(dá)時(shí)間表示為Tdst，消息的隊(duì)列調(diào)度就是由4條入線進(jìn)入的消息同時(shí)競(jìng)爭(zhēng)一條出線，要保證消息最大允許延遲也就是Tdst和Tscr差值小于消息周期Pi。在選擇調(diào)度算法的時(shí)候，通常有加權(quán)循環(huán)調(diào)度算法（WRR）、優(yōu)先級(jí)隊(duì)列調(diào)度算法（PQ）以及加權(quán)公平調(diào)度算法（WFQ）。在本文中提出PQ+WRR算法相結(jié)合的調(diào)度形式，充分結(jié)合兩種算法的優(yōu)勢(shì)，同時(shí)采用令牌桶算法來控制緊急消息過多使得優(yōu)先級(jí)較低的消息得不到調(diào)度情況。

2.1 PQ調(diào)度算法

優(yōu)先級(jí)調(diào)度算法的基本原理就是到達(dá)的數(shù)據(jù)包由頭部服務(wù)類型字段來確定分類，之后根據(jù)相應(yīng)類別進(jìn)入4個(gè)優(yōu)先級(jí)隊(duì)列，調(diào)度器首先調(diào)度高優(yōu)先級(jí)的隊(duì)列，直到隊(duì)列為空時(shí)，才可以調(diào)度低優(yōu)先級(jí)隊(duì)列。該算法的優(yōu)點(diǎn)就是可以保證實(shí)時(shí)性較強(qiáng)任務(wù)的低延時(shí)和低抖動(dòng)。缺點(diǎn)就是在高優(yōu)先級(jí)任務(wù)較多的情況下，低優(yōu)先級(jí)隊(duì)列長(zhǎng)時(shí)間得不到調(diào)度，從而產(chǎn)生餓死的現(xiàn)象。隊(duì)列調(diào)度原理如圖3所示。

2.2 WRR調(diào)度算法

加權(quán)輪詢調(diào)度算法基本原理就是業(yè)務(wù)根據(jù)不同需求分配到不同隊(duì)列，之后按照占用帶寬的比例為相應(yīng)隊(duì)列分配一個(gè)權(quán)值W，這樣對(duì)于緊急性高，實(shí)時(shí)性強(qiáng)的任務(wù)所分配的權(quán)值就大，調(diào)度器按照權(quán)值來調(diào)度消息。它克服了PQ算法存在餓死的現(xiàn)象，缺點(diǎn)就是在消息長(zhǎng)度變化情況下的支持性不夠好。算法原理如圖4所示。

2.3 令牌桶算法

令牌桶算法［12］是網(wǎng)絡(luò)流量速率限制中常使用的一種算法，用來控制發(fā)送到網(wǎng)絡(luò)上數(shù)據(jù)數(shù)目，同時(shí)允許發(fā)送突發(fā)數(shù)據(jù)。容量固定的令牌桶可以以恒定速率產(chǎn)生令牌，若令牌沒有消耗或者消耗速率小于其產(chǎn)生的速率，那么令牌就不斷增多，直至將桶填滿，達(dá)到最大令牌數(shù)。令牌桶的控制機(jī)制為桶內(nèi)是否存在令牌是決定發(fā)送數(shù)據(jù)的依據(jù)，每一個(gè)令牌代表一個(gè)字節(jié)，當(dāng)桶內(nèi)存在令牌時(shí)，允許發(fā)送數(shù)據(jù)，相反則不允許發(fā)送數(shù)據(jù)。如果令牌桶中有足夠多的令牌，同時(shí)突發(fā)門限被合理配置，這樣流量就可以以峰值速率進(jìn)行發(fā)送。算法原理如圖5所示。

本質(zhì)上來說，令牌桶算法是一種測(cè)量引擎，可以用來控制突發(fā)流量，同時(shí)用發(fā)送流量的多少指定流量速率，令牌桶算法有單速率雙色、單速率三色和雙速率三色3種技術(shù)，其中單速率三色是對(duì)單速率雙色的邏輯描述。

在本文使用單速率三色標(biāo)記方式，IETF RFC2697將單速率三色算法用CIR、CBS和EBS進(jìn)行評(píng)估。CIR表示令牌產(chǎn)生的速度，也叫做最大發(fā)送速度；CBS表示令牌桶深度，也就是可接受突發(fā)數(shù)據(jù)包的最大容量；EBS表示額定突發(fā)容量。單速率方式下采用兩個(gè)令牌桶。這樣CBS中沒有使用的令牌都被放入另一個(gè)桶內(nèi)，在突發(fā)流量超過CIR時(shí)使用，所以第2個(gè)桶的大小是第2個(gè)桶的容量和第1個(gè)桶中未使用的令牌之和。

3 基于令牌桶的PQ+WRR算法

本文提出的調(diào)度算法由PQ+WRR分組調(diào)度器和令牌桶流量調(diào)節(jié)器構(gòu)成，本文采用令牌桶算法這種流量調(diào)節(jié)器來控制實(shí)時(shí)性緊急任務(wù)占用過多的網(wǎng)絡(luò)帶寬，同時(shí)結(jié)合優(yōu)先級(jí)調(diào)度算法為高優(yōu)先級(jí)的緊急任務(wù)提供低延時(shí)、低抖動(dòng)的性能，以及為網(wǎng)絡(luò)中其他業(yè)務(wù)提供最佳服務(wù)。當(dāng)分組數(shù)據(jù)到達(dá)區(qū)分服務(wù)位置時(shí)，若該數(shù)據(jù)分組被標(biāo)記成緊急任務(wù)，那么它就要令牌桶所過濾，此時(shí)令牌桶中有令牌，那么就會(huì)通過PQ調(diào)度，立刻轉(zhuǎn)發(fā)，相反就會(huì)經(jīng)過WRR算法進(jìn)行調(diào)度。當(dāng)非緊急任務(wù)到達(dá)時(shí)，首先會(huì)通過WRR算法進(jìn)行調(diào)度，之后再經(jīng)過優(yōu)先級(jí)調(diào)度算法發(fā)送出去。在上述算法中，緊急任務(wù)總是最先得到服務(wù)，但是由于令牌桶對(duì)其的控制，使得緊急任務(wù)不可能長(zhǎng)時(shí)間占據(jù)整個(gè)帶寬，保證了低優(yōu)先級(jí)任務(wù)可以的到調(diào)度，這樣就克服了兩種算法的缺點(diǎn)，提高網(wǎng)絡(luò)的總體性能。算法調(diào)度原理如下頁圖6所示。

算法具體實(shí)現(xiàn)：為方便軟件實(shí)現(xiàn)，相應(yīng)兩個(gè)隊(duì)列調(diào)度數(shù)據(jù)包的個(gè)數(shù)就是其權(quán)值，為了充分利用帶寬，在高優(yōu)先級(jí)隊(duì)列為空時(shí)，立即調(diào)度低優(yōu)先級(jí)隊(duì)列，具體實(shí)現(xiàn)流程如圖7所示。

3.1 調(diào)度算法參數(shù)設(shè)計(jì)

在調(diào)度算法中，輪轉(zhuǎn)周期的選擇對(duì)系統(tǒng)性能有著關(guān)鍵的影響。權(quán)值的分配方式直接關(guān)系系統(tǒng)分配的信道資源數(shù)目，也決定了消息隊(duì)列分配的權(quán)值大小。

3.1.1 權(quán)值分配

在單信道WRR算法中為保證消息傳輸?shù)膶?shí)時(shí)性，消息i的權(quán)值通常取

3.1.2 輪轉(zhuǎn)周期TRL的選擇

本文定義輪轉(zhuǎn)函數(shù)為：

當(dāng)輪轉(zhuǎn)函數(shù)取值最小時(shí)，相應(yīng)的輪轉(zhuǎn)周期就是當(dāng)前分配方式下的最優(yōu)值，這時(shí)分配權(quán)值和初始權(quán)值的差值最小，有效利用率最高。

4 仿真結(jié)果

仿真過程中，首先根據(jù)FC-AE-ASM協(xié)議建立節(jié)點(diǎn)、狀態(tài)和網(wǎng)絡(luò)模型，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)特征如表1所示，網(wǎng)絡(luò)中的消息以數(shù)據(jù)包的形式傳輸，鏈路速率為1 Gbit/s。節(jié)點(diǎn)中的消息按照提出的調(diào)度算法進(jìn)行排隊(duì)，針對(duì)不同的權(quán)值分配方式，在每個(gè)消息傳送成功后，記錄其延遲時(shí)間和延遲率。

表1 仿真數(shù)據(jù)

4.1 不同權(quán)值分配方式下F函數(shù)與TRL的關(guān)系

仿真數(shù)據(jù)如表1所示。根據(jù)實(shí)時(shí)調(diào)度的輪轉(zhuǎn)約束條件以及輪轉(zhuǎn)函數(shù)的定義，可得其關(guān)系如下：

由圖8可知當(dāng)采用分配方式1時(shí)，在TRL=6 μs時(shí)輪轉(zhuǎn)函數(shù)min（F）=0.75取得最小值，表明此時(shí)分配權(quán)值和初始權(quán)值差值最小，有效利用率最高。同理在分配方式2條件下，在TRL=10 μs時(shí)輪轉(zhuǎn)函數(shù)min（F）=0.2取得最小值，有效利用率最高。

經(jīng)過上面的結(jié)果，本文取TRL=10 μs，對(duì)兩種權(quán)值的分配方式下消息的延遲時(shí)間和延時(shí)率進(jìn)行仿真，結(jié)果如圖9～圖11所示：

由仿真結(jié)果看出，在權(quán)值分配方式1的情況下，消息的延遲時(shí)間隨著仿真時(shí)間的進(jìn)行在不斷波動(dòng)，而在權(quán)值分配方式2的情況下，每條消息的延遲時(shí)間都保持不變，說明在權(quán)值分配方式2的情況下調(diào)度效果更好。從延遲率來看，兩種分配方式下所有消息的延遲率都沒有超過1，可以滿足系統(tǒng)對(duì)實(shí)時(shí)性的要求，但是相對(duì)來說消息的時(shí)間延遲率一方面代表系統(tǒng)的實(shí)時(shí)性，另一方面也代表消息傳輸對(duì)系統(tǒng)的容忍程度，相應(yīng)的值越小，內(nèi)外各種因素影響系統(tǒng)的可能性就越低，這樣來說，分配方式1更適合在現(xiàn)代航空系統(tǒng)中應(yīng)用。相比于文獻(xiàn)［5］中的調(diào)度方式，本文的算法較好地改變了調(diào)度性能。

5 結(jié)論

在對(duì)FC-AE-ASM協(xié)議深入研究的基礎(chǔ)上，針對(duì)數(shù)據(jù)的發(fā)送控制，提出了基于令牌桶的PQ+WRR算法，同時(shí)給出了權(quán)值分配和輪轉(zhuǎn)周期的確定方法。最后經(jīng)過仿真驗(yàn)證了這種算法可以很好地滿足系統(tǒng)對(duì)實(shí)時(shí)性的要求。對(duì)于目前國(guó)內(nèi)在光纖通道中對(duì)于調(diào)度算法的研究方面具有很好的借鑒作用。

［1］GASKA T D.COTS fibre channel network technology insertion into avionicssystems ［C］//IEEE 1998 National Aerospace and Electronics Conference，1998：120-127.

［2］ANSI.Rev.2.4.Fibre channel avionics environment（FC-AE）［S］.USA：American National Standard for Information Systems，2004.

［3］INCTIS.T11/02-041v1.Fibre Channel-Avionics environment［S］.Washington：InternationalCommittee forInformation Technology Standards，2002.

［4］INCITS.T11/08-013v1-FC-AE-ASM/AM1［S］.Washington：International Committee for Information Technology Standards，2008.

［5］丁凡，宋麗茹，熊華鋼.FC-AE-ASM網(wǎng)絡(luò)數(shù)據(jù)發(fā)送控制算法研究［J］.電子與信息學(xué)報(bào)，2009，31（6）：1509-1512.

［6］翟正軍，陳康，焦航.FC-AE-ASM網(wǎng)絡(luò)的模糊可靠性研究［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（8）：2467-2469.

［7］徐亞軍，張曉林，熊華鋼.FC互連的可靠性建模［J］.北京航空航天大學(xué)學(xué)報(bào)，2005，31（5）：539-543.

［8］易川，翟正軍，羊昌燕.基于蒙特卡羅法的FC-AE-ASM網(wǎng)絡(luò)可靠性研究［J］. 計(jì)算機(jī)工程與應(yīng)用，2014，50（3）：59-62.

［9］劉達(dá)，王勇，褚文奎，等.航空電子系統(tǒng)中串行光纖通道網(wǎng)絡(luò)建模與仿真［J］.應(yīng)用激光，2015，35（6）：724-728.

［10］劉達(dá)，王勇，李炳乾，等.基于FPGA的FC終端協(xié)議處理芯片的設(shè)計(jì)與實(shí)現(xiàn)［J］.火力與指揮控制，2017，42（7）：124-128.

［11］付中培，吳勇，張建東，等.FC-AE-ASM網(wǎng)絡(luò)調(diào)度算法研究［J］.現(xiàn)代電子技術(shù)，2011，34（6）：108-111.

［12］蔣維成.令牌桶算法比較研究［J］.電腦知識(shí)與技術(shù)，2010，6（4）：861-862.

［13］MAODE M，HAMIDZADEH B，HAMDI M.Providing deterministic quality-of-service guarantees on WDM optical network ［J］.IEEE Journal on Selected Areas in Communications，2000，18（10）：2072-2083.

［14］林強(qiáng)，熊華鋼，張其善.光纖通道交換機(jī)在強(qiáng)實(shí)時(shí)約束條件下的分組調(diào)度［J］.計(jì)算機(jī)學(xué)報(bào).2006，29（4）：570-575.

［15］周立，王昊天，何鋒，等.航空電子多信道實(shí)時(shí)分組調(diào)度方法［J］.航空學(xué)報(bào)，2010，31（10）：2034-2039.

Research on Fiber Channel Scheduling Algorithm

DING Yong-qiang1，WAGN Yong2，TAN Xiao-hu2，CHU Wen-kui2，F(xiàn)ANG Ting2
（1.College of The First Aeronautic，Air Force Engineering University，Xinyang 464000，China；2.College of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi’an 710038，China）

This paper primarily aim at the problem that it don’t have data scheduling algorithm in FC.Through analysis deeply，an algorithm which combine PQ with WRR basing on Token Bucket algorithm is presented，at the same time，include ensured the way of weight distribution and turnaround time.Delay rate is as to the performance of algorithm.Simulation turn out that the scheduling algorithm can meet real-time in avionics system.

FC，weight distribution，turnaround time，delay rate

TP914

A

10.3969/j.issn.1002-0640.2017.11.17

1002-0640（2017）11-0077-05

2016-10-05

2016-11-07

航空科學(xué)基金資助項(xiàng)目（20165515001）

丁永強(qiáng)（1981-），男，河南信陽人，博士，講師。研究方向：機(jī)載總線技術(shù)。