應(yīng)用混合隊(duì)列調(diào)度策略的AFDX實(shí)時(shí)性優(yōu)化研究

劉 靜

（1.渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714099；2.渭南市智慧城市工程技術(shù)研究中心，陜西渭南714099）

應(yīng)用混合隊(duì)列調(diào)度策略的AFDX實(shí)時(shí)性優(yōu)化研究

劉 靜1，2

（1.渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714099；2.渭南市智慧城市工程技術(shù)研究中心，陜西渭南714099）

航空電子全雙工交換式以太網(wǎng)（AFDX）對(duì)傳輸?shù)臄?shù)據(jù)流采用先到先服務(wù)（FCFS）調(diào)度策略，導(dǎo)致安全關(guān)鍵性數(shù)據(jù)的網(wǎng)絡(luò)延遲較大，擁塞情況下的數(shù)據(jù)流延遲存在不確定性。為解決該問(wèn)題，提出一種用于優(yōu)化AFDX網(wǎng)絡(luò)實(shí)時(shí)性的混合隊(duì)列調(diào)度策略，綜合FCFS調(diào)度策略、靜態(tài)優(yōu)先級(jí)隊(duì)列調(diào)度策略和差額輪詢調(diào)度策略的優(yōu)點(diǎn)，通過(guò)網(wǎng)絡(luò)演算分析數(shù)據(jù)流的延遲上界，理論驗(yàn)證硬實(shí)時(shí)數(shù)據(jù)流滿足AFDX網(wǎng)絡(luò)通信需求。仿真實(shí)驗(yàn)結(jié)果表明，混合隊(duì)列調(diào)度策略不僅可以保證AFDX網(wǎng)絡(luò)中安全關(guān)鍵性數(shù)據(jù)流的實(shí)時(shí)性，以及非安全關(guān)鍵性數(shù)據(jù)流的調(diào)度公平性，而且能有效隔離惡意數(shù)據(jù)流。

混合隊(duì)列調(diào)度策略；網(wǎng)絡(luò)演算；航空電子全雙工交換式以太網(wǎng)；虛鏈路；端到端延遲

1 概述

近年來(lái)，航空電子系統(tǒng)網(wǎng)絡(luò)協(xié)議作為現(xiàn)代航空電子系統(tǒng)的重要組成部分，得到了快速發(fā)展［1］。航空電子全雙工交換式以太網(wǎng)（Avionics Full Duplex Sw itched Ethernet Network，AFDX）是空中客車公司在研制空客A380的過(guò)程中，基于IEEE 802.3［2］和美國(guó)愛(ài)瑞克664（ARINC 664）［3］標(biāo)準(zhǔn)提出的新一代航空數(shù)據(jù)總線。相比之前的美國(guó)愛(ài)瑞克429（ARINC 429）、軍標(biāo)-1553（M IL-STD-1553）以及增強(qiáng)型1553B標(biāo)準(zhǔn)，AFDX進(jìn)一步提高了機(jī)載網(wǎng)絡(luò)的靈活性、模塊性、擴(kuò)展性、傳輸速率等。AFDX網(wǎng)絡(luò)采用全雙工技術(shù)避免傳統(tǒng)以太網(wǎng)在終端系統(tǒng)中的資源沖突問(wèn)題。然而，AFDX并沒(méi)有完全消除傳統(tǒng)以太網(wǎng)傳輸中的不確定性，各種數(shù)據(jù)流在交換機(jī)內(nèi)部競(jìng)爭(zhēng)資源，導(dǎo)致更大的延遲和不公平性［4］。

為此，越來(lái)越多的研究人員開始致力于AFDX網(wǎng)絡(luò)的性能提升以及可靠性驗(yàn)證工作。網(wǎng)絡(luò)性能指標(biāo)一般包括吞吐量、端到端延時(shí)、延遲抖動(dòng)、差錯(cuò)率等。其中端到端延時(shí)是AFDX網(wǎng)絡(luò)的關(guān)鍵性能參數(shù)。目前關(guān)于AFDX網(wǎng)絡(luò)端到端延時(shí)的研究主要包括計(jì)算端到端延時(shí)上界和減少網(wǎng)絡(luò)端到端延時(shí)這2個(gè)方面。

AFDX協(xié)議［3］中使用先到先服務(wù)（First Come First Serve，F(xiàn)CFS）調(diào)度策略，該策略公平地對(duì)待每一種數(shù)據(jù)流，調(diào)度服務(wù)器按照數(shù)據(jù)流到達(dá)順序來(lái)轉(zhuǎn)發(fā)相應(yīng)的數(shù)據(jù)。文獻(xiàn)［4］用網(wǎng)絡(luò)演算［5-6］方法計(jì)算了特定配置下的AFDX網(wǎng)絡(luò)的端到端延時(shí)上界，發(fā)現(xiàn)網(wǎng)絡(luò)演算方法計(jì)算了最壞情況下的網(wǎng)絡(luò)端到端延時(shí)上界，通常實(shí)際網(wǎng)絡(luò)中的端到端延時(shí)要小于該上界。文獻(xiàn)［7］在運(yùn)用網(wǎng)絡(luò)演算分析計(jì)算數(shù)據(jù)流在FCFS策略下的網(wǎng)絡(luò)端到端延時(shí)，發(fā)現(xiàn)FCFS策略不區(qū)分優(yōu)先級(jí)，容易引起某些緊急數(shù)據(jù)流的傳輸超時(shí)，不能很好地滿足不同數(shù)據(jù)流的實(shí)時(shí)性傳輸要求。

為了滿足不同數(shù)據(jù)流的服務(wù)質(zhì)量要求，文獻(xiàn)［8］在交換機(jī)中應(yīng)用靜態(tài)優(yōu)先級(jí)（Static Priority，SP）調(diào)度策略，使安全關(guān)鍵性數(shù)據(jù)流的延遲上界小于FCFS調(diào)度策略下的延遲上界，但仍不能完全滿足航空電子系統(tǒng)中數(shù)據(jù)流的傳輸要求。文獻(xiàn)［9］將AFDX網(wǎng)絡(luò)數(shù)據(jù)流分為3個(gè)優(yōu)先級(jí)，改進(jìn)傳統(tǒng)優(yōu)先級(jí)算法，降低高優(yōu)先級(jí)數(shù)據(jù)流的延遲抖動(dòng)上界，但忽略了同一優(yōu)先級(jí)的數(shù)據(jù)流的公平調(diào)度。文獻(xiàn)［10］針對(duì)AFDX中有一定時(shí)延要求的非安全關(guān)鍵類數(shù)據(jù)流采用負(fù)載分類的方法，提高了較小負(fù)載的實(shí)時(shí)性，但導(dǎo)致較大負(fù)載面臨更大時(shí)延。文獻(xiàn)［11］分析了AFDX網(wǎng)絡(luò)中多包發(fā)送的響應(yīng)時(shí)間，可以應(yīng)用于異構(gòu)分布式網(wǎng)絡(luò)，但在時(shí)延分析中以位為單位，所求得的結(jié)果存在誤差。文獻(xiàn)［12］提出通過(guò)優(yōu)化虛鏈路的參數(shù)來(lái)提高AFDX網(wǎng)絡(luò)的鏈路帶寬利用率，降低了部分鏈路的最大延遲上界，但大幅提高了多包數(shù)據(jù)延遲。文獻(xiàn)［13］結(jié)合靜態(tài)優(yōu)先級(jí)策略，并通過(guò)軌跡法得到AFDX網(wǎng)絡(luò)中數(shù)據(jù)流的較小平均時(shí)延上限，但對(duì)部分?jǐn)?shù)據(jù)的延遲影響很大。文獻(xiàn)［14］在交換機(jī)中應(yīng)用差額輪詢（Deficit Round Robin，DRR）調(diào)度策略，保證數(shù)據(jù)流的公平調(diào)度，但降低了安全關(guān)鍵性數(shù)據(jù)流的實(shí)時(shí)性。綜上所述，優(yōu)化AFDX網(wǎng)絡(luò)協(xié)議，建立確定網(wǎng)絡(luò)端到端延遲的AFDX網(wǎng)絡(luò)，對(duì)于擴(kuò)大AFDX的應(yīng)用范圍具有重要作用。

本文在分析AFDX網(wǎng)絡(luò)中數(shù)據(jù)流實(shí)時(shí)性需求的基礎(chǔ)上，提出了一種新的調(diào)度策略，使AFDX中安全關(guān)鍵性數(shù)據(jù)流的實(shí)時(shí)性得以保障，同時(shí)為非安全關(guān)鍵性數(shù)據(jù)流提供公平的調(diào)度服務(wù)，并在特定的AFDX網(wǎng)絡(luò)配置下，從理論推導(dǎo)和實(shí)驗(yàn)仿真2個(gè)方面證明新的調(diào)度策略對(duì)AFDX網(wǎng)絡(luò)實(shí)時(shí)性的優(yōu)化作用。

2 網(wǎng)絡(luò)演算及調(diào)度策略

2.1 網(wǎng)絡(luò)演算基本理論

20世紀(jì)90年代初，Cruz R L在研究網(wǎng)絡(luò)傳輸時(shí)延的過(guò)程中分析了6種網(wǎng)絡(luò)基礎(chǔ)元素，同時(shí)定義了整形器、服務(wù)曲線和到達(dá)曲線等概念。隨后，Boudec JY和Chang C S等人進(jìn)一步發(fā)展了網(wǎng)絡(luò)演算理論，特別是引入了極小代數(shù)的數(shù)學(xué)表示方法，使其得到了廣泛應(yīng)用，同時(shí)，隨機(jī)性網(wǎng)絡(luò)演算也取得了一些研究成果［15］。

現(xiàn)在的網(wǎng)絡(luò)演算理論最重要的概念是到達(dá)曲線和服務(wù)曲線，網(wǎng)絡(luò)演算理論可以使用這2個(gè)概念計(jì)算延遲、積壓等參數(shù)的上確界。

定義1（廣義增函數(shù)） 廣義增函數(shù)f（t）是指當(dāng)s≤t時(shí)，f（s）≤f（t）的函數(shù)?？捎汧為在t＜0時(shí)f（t）=0的廣義增函數(shù)的集合，F(xiàn)0為在t≤0時(shí)f（t）=0的廣義增函數(shù)的集合。

定義2（極小卷積） 設(shè)f，g∈F，則f和g的極小卷積為（f?g）（t）=inf｛f（t-s）+g（s）|0≤s≤t｝，且當(dāng)t＜0時(shí)，（f?g）（t）=0。

定義3（到達(dá)曲線） 設(shè)A，α∈F，如果對(duì)于所有s≤t：A（t）-A（s）≤α（t-s），則稱A的值受限于α，α為A的到達(dá)曲線，或者數(shù)據(jù)流A經(jīng)過(guò)α整流。

定義4（服務(wù)曲線） 當(dāng)網(wǎng)絡(luò)元素S的輸入和輸出累積函數(shù)分別為A（t）和D（t）時(shí)，稱服務(wù)曲線為β當(dāng)且僅當(dāng)β∈F0且D＞A?β。

網(wǎng)絡(luò)演算理論可以計(jì)算已知到達(dá)曲線的數(shù)據(jù)流，通過(guò)已知服務(wù)曲線的網(wǎng)絡(luò)元素過(guò)程中的數(shù)據(jù)流的延遲、交換機(jī)的積壓等參數(shù)的上確界。

定義7（輸出流的到達(dá)曲線） 假設(shè)一個(gè)到達(dá)曲線為α的流通過(guò)一個(gè)服務(wù)曲線為β的網(wǎng)絡(luò)元素，則輸出流的到達(dá)曲線為α*=α?β。

定義8（串聯(lián)系統(tǒng)的服務(wù)曲線） 假設(shè)一個(gè)流順序經(jīng)過(guò)網(wǎng)絡(luò)元素S1和S2，Si提供的服務(wù)曲線為βi，i=1，2，則串聯(lián)系統(tǒng)所提供的服務(wù)曲線為βΣ=β1?β2。

當(dāng)輸入數(shù)據(jù)流的到達(dá)曲線為α（t）=rt+b，起到服務(wù)節(jié)點(diǎn)作用的網(wǎng)絡(luò)元素的服務(wù)曲線為β（t）= C［t-d］+，則最大延遲為，最大積壓為Backlog=rd+b，如圖1所示。

圖1 延遲和積壓示意圖

隨著應(yīng)用需求的不斷提高，網(wǎng)絡(luò)演算也不斷發(fā)展，并在整形器和窗口流量控制領(lǐng)域取得了卓越的研究成果，更因?yàn)槌晒忉屃送话l(fā)量?jī)H計(jì)算一次（pay burst only once）的串聯(lián)鏈路延遲不需累加現(xiàn)象而得到進(jìn)一步普及。

2.2 AFDX混合隊(duì)列調(diào)度策略

在實(shí)際應(yīng)用中，網(wǎng)絡(luò)中傳輸各式各樣的數(shù)據(jù)流，依據(jù)不同的實(shí)時(shí)性需求，可以將航電網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)分為4類［16］：（1）非周期性，有極高時(shí)延要求的緊急數(shù)據(jù)，如警報(bào)；（2）周期性，有硬性時(shí)延要求的數(shù)據(jù)，如傳感器數(shù)據(jù)；（3）非周期性，有一定時(shí)延要求但不緊急的數(shù)據(jù)；（4）非周期性，也沒(méi)有時(shí)延要求的數(shù)據(jù)，如文件傳輸。其中，第（1）類和第（2）類為安全關(guān)鍵性數(shù)據(jù)流；第（3）類和第（4）類為非安全關(guān)鍵性數(shù)據(jù)流。本文主要研究前3類數(shù)據(jù)流的實(shí)時(shí)特性。

通過(guò)對(duì)數(shù)據(jù)劃分優(yōu)先級(jí)，可以有效地降低高優(yōu)先級(jí)數(shù)據(jù)流的傳輸時(shí)延。本文在傳統(tǒng)靜態(tài)優(yōu)先級(jí)隊(duì)列調(diào)度機(jī)制的基礎(chǔ)上，結(jié)合流量整形和輪詢調(diào)度算法，提出應(yīng)用于AFDX網(wǎng)絡(luò)的混合隊(duì)列調(diào)度策略（M ixed Queue Scheduling on AFDX，MQSA），用于滿足AFDX網(wǎng)絡(luò)中數(shù)據(jù)流的實(shí)時(shí)性需求。

MQSA策略依據(jù)數(shù)據(jù)流對(duì)實(shí)時(shí)性的需求，分別賦予其從高到低3個(gè)優(yōu)先級(jí)。數(shù)據(jù)流在進(jìn)入各自優(yōu)先級(jí)的緩沖隊(duì)列后，按照靜態(tài)優(yōu)先級(jí)策略進(jìn)行調(diào)度。安全關(guān)鍵性數(shù)據(jù)流的數(shù)據(jù)幀一般比較短小，相同優(yōu)先級(jí)的數(shù)據(jù)幀采用先到先服務(wù)（FCFS）的調(diào)度策略。非安全關(guān)鍵性數(shù)據(jù)流的數(shù)據(jù)幀的大小不一，對(duì)不同鏈路的非安全關(guān)鍵性數(shù)據(jù)流采用差額輪詢調(diào)度策略。其中，交換機(jī)中的調(diào)度器工作通常以非搶占方式和工作保持方式進(jìn)行服務(wù)。

在AFDX端系統(tǒng)中，使用虛鏈路（V irtual Link，VL）機(jī)制保證數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性，且多條虛鏈路可以同時(shí)存在于同一物理鏈路中。虛鏈路中設(shè)有2個(gè)重要參數(shù)：（1）一條虛鏈路中2個(gè)相鄰數(shù)據(jù)幀之間的最小帶寬分配間隔（Bandw idth Allocation Gap，BAG），其取值范圍是1 ms～128 ms；（2）虛鏈路中允許傳輸幀的最大長(zhǎng)度為L(zhǎng)max。MQSA策略的AFDX調(diào)度器邏輯結(jié)構(gòu)如圖2所示。

圖2 AFDX混合隊(duì)列調(diào)度器邏輯結(jié)構(gòu)

在圖2中，ES為端系統(tǒng)；矩形模塊為數(shù)據(jù)庫(kù)。不同數(shù)據(jù)進(jìn)入相應(yīng)的優(yōu)先級(jí)隊(duì)列中，等待調(diào)度與發(fā)送。設(shè)混合隊(duì)列調(diào)度器物理鏈路輸出速率為C bit/s。1號(hào)優(yōu)先級(jí)隊(duì)列的優(yōu)先級(jí)最高，2號(hào)隊(duì)列次之，3號(hào)隊(duì)列的優(yōu)先級(jí)最低。為了突出差額輪詢調(diào)度（DRR）的特點(diǎn)，對(duì)部分?jǐn)?shù)據(jù)繪制了不同的陰影。

2.3 調(diào)度策略時(shí)延分析

2.3.1 先到先服務(wù)調(diào)度策略

2.3.2 靜態(tài)優(yōu)先級(jí)隊(duì)列調(diào)度策略

當(dāng)端系統(tǒng)采用靜態(tài)優(yōu)先級(jí)（SP）隊(duì)列策略服務(wù)時(shí)，高優(yōu)先級(jí)的數(shù)據(jù)流將被優(yōu)先發(fā)送。若有3個(gè)優(yōu)先級(jí)（P1，P2，P3）的數(shù)據(jù)流，且P1優(yōu)先級(jí)最高，P2次之，P3最低，則優(yōu)先級(jí)Pi聚合流的到達(dá)曲線為αi：

其中，j為相同優(yōu)先級(jí)、不同數(shù)據(jù)流的編號(hào)。

端系統(tǒng)對(duì)優(yōu)先級(jí)為i的數(shù)據(jù)流服務(wù)曲線為βi，其具體表達(dá)式如下［9］：

由定義6可得，各優(yōu)先級(jí)數(shù)據(jù)流的延遲上界具體如下：

此時(shí)，高優(yōu)先級(jí)數(shù)據(jù)流的延遲上界明顯小于低優(yōu)先級(jí)的延遲上界。在航電系統(tǒng)中，將緊急的數(shù)據(jù)賦予較高優(yōu)先級(jí)可知，采用靜態(tài)優(yōu)先級(jí)隊(duì)列策略克服了傳統(tǒng)AFDX調(diào)度器中所有數(shù)據(jù)幀延遲上界相同的缺陷，滿足了航電應(yīng)用需求。

2.3.3 差額輪詢調(diào)度策略

差額輪詢（DRR）調(diào)度策略是在一個(gè)輪詢周期里訪問(wèn)所有非空隊(duì)列的調(diào)度算法［17］。數(shù)據(jù)流在一輪服務(wù)中得到的服務(wù)量與該數(shù)據(jù)流所分配的帶寬成正比，從而為不同的數(shù)據(jù)流提供較為公平的調(diào)度服務(wù)。因?yàn)镈RR是一種不需要全局時(shí)鐘和排序過(guò)程的公平調(diào)度算法，所以被廣泛應(yīng)用于思科路由器和微軟W indow s NT等真實(shí)環(huán)境中。

在一個(gè)有n個(gè)輸入流的調(diào)度中，DRR策略為第i個(gè)輸入流隊(duì)列維護(hù)一個(gè)計(jì)數(shù)器θi，每一個(gè)輪詢周期為第i個(gè)隊(duì)列分配ωi的帶寬額。DRR策略以字節(jié)為調(diào)度單位，在一次輪詢操作中，如果一個(gè)輸入流隊(duì)列中有長(zhǎng)度li不大于計(jì)數(shù)器θi的待發(fā)數(shù)據(jù)幀時(shí)，則發(fā)送該數(shù)據(jù)幀，同時(shí)更新計(jì)數(shù)器θi=θi-li。如果li＞θi，則更新計(jì)數(shù)器θi=θi+ωi；如果無(wú)待發(fā)數(shù)據(jù)幀，則更新計(jì)數(shù)器θi=0。更新完計(jì)數(shù)器后，開始調(diào)度下一個(gè)隊(duì)列。

其中，ωi和ωj是每個(gè)輪詢周期為第i個(gè)和第j個(gè)隊(duì)列分配的帶寬額。

因?yàn)椴铑~輪詢調(diào)度是以字節(jié)為單位，且每次增加的固定帶寬額為ωi，所以服務(wù)曲線的服務(wù)速率是離散而非連續(xù)的，因此，修正延遲上界為i=。

2.3.4 混合隊(duì)列調(diào)度策略

混合隊(duì)列調(diào)度策略（MQSA）是將數(shù)據(jù)流經(jīng)過(guò)2次調(diào)度，保障硬實(shí)時(shí)數(shù)據(jù)流的實(shí)時(shí)性，同時(shí)對(duì)非硬實(shí)時(shí)數(shù)據(jù)流公平調(diào)度的策略。在混合隊(duì)列調(diào)度策略中，優(yōu)先級(jí)為1和2的硬實(shí)時(shí)數(shù)據(jù)流，先按照FIFO策略排隊(duì)，然后使用SP隊(duì)列調(diào)度機(jī)制服務(wù)，相當(dāng)于經(jīng)過(guò)一個(gè)串聯(lián)服務(wù)系統(tǒng)。優(yōu)先級(jí)為3的非硬實(shí)時(shí)數(shù)據(jù)流使用的是一個(gè)DRR和SP隊(duì)列調(diào)度機(jī)制串聯(lián)的系統(tǒng)。

此時(shí)，根據(jù)網(wǎng)絡(luò)演算理論，可以得到MQSA策略為各個(gè)優(yōu)先級(jí)的虛鏈路VLi提供的服務(wù)曲線。

通過(guò)對(duì)比應(yīng)用MQSA策略的端系統(tǒng)為不同優(yōu)先級(jí)數(shù)據(jù)流所提供的服務(wù)曲線，發(fā)現(xiàn)β1，i和β2，i同SP策略下的服務(wù)曲線相同，即MQSA策略保證了較高優(yōu)先級(jí)數(shù)據(jù)流的實(shí)時(shí)性。

根據(jù)虛鏈路VLi的BAGi和設(shè)置，可以得到對(duì)應(yīng)的到達(dá)曲線。根據(jù)網(wǎng)絡(luò)演算理論，可以得到對(duì)應(yīng)數(shù)據(jù)流經(jīng)過(guò)調(diào)度器的延遲上界。

3 AFDX網(wǎng)絡(luò)模型

3.1 模型設(shè)計(jì)

為了研究混合隊(duì)列調(diào)度策略（MQSA）在AFDX網(wǎng)絡(luò)中的作用，構(gòu)建了一個(gè)AFDX網(wǎng)絡(luò)原型系統(tǒng)，如圖3所示。為了簡(jiǎn)化問(wèn)題分析，本文不考慮AFDX本身的冗余傳輸系統(tǒng)，同時(shí)規(guī)定交換機(jī)的緩沖區(qū)夠大，不存在丟包情況。系統(tǒng)由4臺(tái)全雙工交換機(jī)（SW 1，SW 2，SW 3，SW 4）連接，有9個(gè)源端系統(tǒng)（ES1，ES2，…，ES9）和1個(gè)目的端系統(tǒng)（ES10），網(wǎng)絡(luò)中的每個(gè)物理鏈路中同時(shí)存在若干虛鏈路（VL）。每臺(tái)交換機(jī)均使用MQSA策略進(jìn)行服務(wù)，存儲(chǔ)轉(zhuǎn)發(fā)速率設(shè)為常見的C=100 M b/s，每根物理連接線長(zhǎng)度設(shè)為10 m，電信號(hào)在電纜中的傳輸速率設(shè)為2× 108m/s。AFDX網(wǎng)絡(luò)中所有虛鏈路都是靜態(tài)的，不存在尋找路由的情況。4臺(tái)交換機(jī)均為雙全工交換機(jī)，級(jí)聯(lián)時(shí)會(huì)降低交換機(jī)對(duì)部分?jǐn)?shù)據(jù)流的服務(wù)曲線，但通過(guò)引理4可以分析該樹形拓?fù)浣Y(jié)構(gòu)中交換機(jī)的服務(wù)曲線。本文研究的實(shí)時(shí)性是從一個(gè)源端系統(tǒng)到目的端系統(tǒng)的延遲。

圖3 AFDX網(wǎng)絡(luò)原型系統(tǒng)

本文將端系統(tǒng)發(fā)出優(yōu)先級(jí)為P1的硬實(shí)時(shí)數(shù)據(jù)流稱為緊急數(shù)據(jù)流（URG），優(yōu)先級(jí)為P2的硬實(shí)時(shí)數(shù)據(jù)流稱為傳感器數(shù)據(jù)流（SEN），優(yōu)先級(jí)為P3的硬實(shí)時(shí)數(shù)據(jù)流稱為盡力而為服務(wù)數(shù)據(jù)流（BST），則系統(tǒng)中有91條虛鏈路傳輸緊急數(shù)據(jù)流，34條虛鏈路傳輸傳感器數(shù)據(jù)流，42條虛鏈路傳輸盡力而為服務(wù)數(shù)據(jù)流。各類數(shù)據(jù)流的虛鏈路參數(shù)設(shè)置如表1～表3所示，其BAG值都設(shè)置在128 ms之內(nèi)，且大部分?jǐn)?shù)據(jù)幀的長(zhǎng)度小于1 000 Byte［14］。

表1 緊急數(shù)據(jù)流的虛鏈路BAG值和幀長(zhǎng)

表2 傳感器數(shù)據(jù)流的虛鏈路BAG值和幀長(zhǎng)

表3 盡力而為服務(wù)數(shù)據(jù)流的虛鏈路BAG值和幀長(zhǎng)

為了驗(yàn)證MQSA策略為盡力服務(wù)數(shù)據(jù)流調(diào)度的公平性，將ES4和ES7所發(fā)出的BAG值為2 ms的2條虛鏈路中傳輸?shù)臄?shù)據(jù)幀長(zhǎng)度，設(shè)置為最大長(zhǎng)度1 518 Byte，則這2條數(shù)據(jù)流將占用SW 4的12 144 000 bit/s的帶寬。這在實(shí)際應(yīng)用中是需要避免的，本文稱其為惡意數(shù)據(jù)流。

3.2 模型分析

網(wǎng)絡(luò)系統(tǒng)中存在若干物理連接線，由于電信號(hào)在物理連接線中傳輸?shù)乃俾适枪潭ㄖ?，則連接線相當(dāng)于Cruz所定義的固定延遲元素［5］，對(duì)應(yīng)的服務(wù)曲線βC=C［t-Δ］+，Δ為電信號(hào)在10 m傳輸線的傳輸時(shí)延，即Δ=10m/（2×108m/s）=5×10-8s。

應(yīng)用網(wǎng)絡(luò)演算理論分析每條虛鏈路中數(shù)據(jù)流的延遲上界，需要將其所經(jīng)過(guò)的一系列網(wǎng)絡(luò)元素當(dāng)作一個(gè)服務(wù)器。例如ES1所發(fā)出的一條緊急數(shù)據(jù)流，通過(guò)物理鏈路連接SW 1，而后依次連接SW 3，SW 4，最終達(dá)到目的端系統(tǒng)ES10，由此可知ES1到ES10經(jīng)過(guò)了一個(gè)服務(wù)曲線為βE-E=βC?βSW1?βC?βSW3?βC?βSW4?βC的服務(wù)器。到達(dá)曲線需要分級(jí)分析，先分析不同優(yōu)先級(jí)的聚合數(shù)據(jù)流，再分析同一聚合流下的微數(shù)據(jù)流。由此已知網(wǎng)絡(luò)系統(tǒng)是一個(gè)樹形結(jié)構(gòu)，參考文獻(xiàn)［18］可得到各個(gè)微數(shù)據(jù)流的延遲上界。

3.3 模型仿真

為了驗(yàn)證MQSA策略對(duì)AFDX網(wǎng)絡(luò)實(shí)時(shí)性的優(yōu)化效果，運(yùn)用M atlab的TrueTime1.5工具箱構(gòu)建了包含AFDX端系統(tǒng)和交換機(jī)的網(wǎng)絡(luò)仿真平臺(tái)。同時(shí)，對(duì)FIFO和SP隊(duì)列調(diào)度機(jī)制進(jìn)行實(shí)驗(yàn)仿真，對(duì)比3種隊(duì)列調(diào)度策略在AFDX網(wǎng)絡(luò)中的實(shí)時(shí)性能。

MQSA策略的實(shí)現(xiàn)關(guān)鍵是DRR調(diào)度的實(shí)現(xiàn)，其算法偽代碼如下：

在該算法中，VL-Num是同一優(yōu)先級(jí)下采用DRR調(diào)度的虛鏈路數(shù)量；theta為隊(duì)列計(jì)數(shù)器；L為數(shù)據(jù)幀長(zhǎng)度；W為每次分配的帶寬額，本文的W值統(tǒng)一設(shè)定為1 00 Byte。該算法的時(shí)間復(fù)雜度為O（VL-Num），與FIFO策略的復(fù)雜度相同。

3.4 結(jié)果比較

將仿真程序在不同調(diào)度策略下分別運(yùn)行1 000 s，不同類型數(shù)據(jù)流的延遲統(tǒng)計(jì)結(jié)果如圖4～圖6所示。圖中橫軸為不同BAG值和不同調(diào)度策略（從左至右分別為FIFO策略、SP策略、MQSA策略）組合的類別。仿真結(jié)果表明，F(xiàn)IFO策略公平地調(diào)度所有數(shù)據(jù)流，但沒(méi)有根據(jù)數(shù)據(jù)流的實(shí)時(shí)性需求提供區(qū)分的服務(wù)質(zhì)量。SP策略保證了硬實(shí)時(shí)數(shù)據(jù)流的實(shí)時(shí)性，卻不能保障盡力而為服務(wù)數(shù)據(jù)流的公平發(fā)送，也不能隔離惡意數(shù)據(jù)流的影響。MQSA策略既可以保證硬實(shí)時(shí)數(shù)據(jù)的實(shí)時(shí)性，公平地調(diào)度盡力服務(wù)數(shù)據(jù)流，也能有效地隔離惡意數(shù)據(jù)流。

圖4 URG數(shù)據(jù)流在不同調(diào)度策略下的延遲統(tǒng)計(jì)

圖5 SEN數(shù)據(jù)流在不同調(diào)度策略下的延遲統(tǒng)計(jì)

圖6 BST數(shù)據(jù)流在不同調(diào)度策略下的延遲統(tǒng)計(jì)

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

本文在分析AFDX網(wǎng)絡(luò)中數(shù)據(jù)流實(shí)時(shí)性需求的基礎(chǔ)上，對(duì)原有的調(diào)度策略進(jìn)行改進(jìn)，提出應(yīng)用于AFDX的混合隊(duì)列調(diào)度策略（MQSA），并利用網(wǎng)絡(luò)演算方法分析了各個(gè)數(shù)據(jù)流的延遲上界，以確保硬實(shí)時(shí)數(shù)據(jù)流滿足通信要求。實(shí)驗(yàn)仿真結(jié)果表明，MQSA策略不僅可以滿足安全關(guān)鍵性數(shù)據(jù)流的實(shí)時(shí)性需要，公平地調(diào)度非安全關(guān)鍵性數(shù)據(jù)流，也能減少惡意數(shù)據(jù)流對(duì)其他數(shù)據(jù)流延遲的影響。本文對(duì)于發(fā)展和完善AFDX網(wǎng)絡(luò)，加快AFDX網(wǎng)絡(luò)在我國(guó)新一代飛機(jī)上的應(yīng)用，推動(dòng)國(guó)內(nèi)航空數(shù)據(jù)總線的發(fā)展具有重要意義。今后的研究工作主要集中在進(jìn)一步完善調(diào)度算法、確定交換機(jī)緩沖區(qū)大小、可靠性驗(yàn)證等方面，以期提高AFDX網(wǎng)絡(luò)的運(yùn)行效率，更好地滿足航空電子系統(tǒng)的需求。

［1］ 郭利鋒，王 勇，張 磊，等.AFDX交換機(jī)的隊(duì)列整形調(diào)度研究［J］.計(jì)算機(jī)工程，2011，37（24）：58-60.

［2］ Frazier H.The 802.3 Zgigabit Ethernet Standard［J］. IEEE Network，1998，12（3）：6-7.

［3］ ARINC.ARINC 664-7-2005：Aircraft Data Network，Part7-deterministic Network［S］.2005.

［4］ Charara H，Scharbarg J，Ermont J，et al.Methods for Bounding End-to-end Delays on an AFDX Network［C］//Proceedings of the 18th Euromicro Conference on Real-time Systems.Washington D.C.，USA：IEEE Press，2006：192-202.

［5］ Cruz R L.A Calculus for Network Delay.I.Network Elements in Isolation［J］.IEEE Transactions on Information Theory，1991，37（1）：114-131.

［6］ Cruz R L.A Calculus for Network Delay.2.Network Analysis［J］.IEEE Transactions on Information Theory，1991，37（1）：132-141.

［7］ Scharbarg J，Ridouard F，F(xiàn)raboul C.A Probabilistic Analysis of End-to-end Delays on an AFDX Avionic Network［J］.IEEE Transactions on Industrial Informatics，2009，5（1）：38-49.

［8］ Ridouard F，Scharbarg J，F(xiàn)raboul C.Probabilistic Upper Bounds for Heterogeneous Flows Using a Static Priority Queuing on an AFDX Network［C］//Proceedings of the 13th International Conference on Emerging Technologies and Factory Automation.Washington D.C.，USA：IEEE Press，2008：1220-1227.

［9］ 陳 昕，周擁軍，蔣文保，等.AFDX協(xié)議性能分析及調(diào)度算法研究［J］.電子學(xué)報(bào)，2009，37（5）：1000-1005.

［10］ Dong Haiyong，Lin Yi，Zhang Yanyuan，et al.Using Static Priority Queueing to optimize the Avionics Full Duplex Sw itched Ethernet［C］//Proceedings of the 9th International Conference on Natural Computation. Washington D.C.，USA：IEEE Press，2013：23-25.

［11］ Gutiérrez J J，Palencia J C，Harbour M G.Holistic Schedulability Analysis for Multipacket Messages in AFDX Networks［J］.Real-tim e System s，2014，50（2）：230-269.

［12］ Sheikh A，Brun O，Chéram y M，et al.Optimal Design of Virtual Links in AFDX Networks［J］.Real-time System s，2013，49（3）：308-336.

［13］ Bauer H，Scharbarg J L，F(xiàn)raboul C.Applying Trajectory Approach with Static Priority Queuing for Improving the Use of Available AFDX Resources［J］.Real-time Systems，2012，48（1）：101-133.

［14］ Hua Yu，Liu Xue.Scheduling Heterogeneous Flow s with Delay-aware Deduplication for Avionics Applications［J］.IEEE Transactions on Parallel and Distributed System s，2012，23（9）：1790-1802.

［15］ 樊葆華.基于網(wǎng)絡(luò)演算的計(jì)算機(jī)網(wǎng)絡(luò)性能分析模型研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2009.

［16］ Mifdaoui A，F(xiàn)rances F，F(xiàn)raboul C.Full Duplex Switched Ethernet for Next Generation“1553B”-based Applications［C］//Proceedings of the 13 th IEEE Real Time and Em bedded Technology and Applications Symposium. Washington D.C.，USA：IEEE Press，2007：45-56.

［17］ Shreedhar M，Varghese G.Efficient Fair Queuing Using Deficit Round-robin［J］.IEEE/ACM Transactions on Networking，1996，4（3）：375-385.

［18］ 張奇智，張 彬，張衛(wèi)東，等.基于網(wǎng)絡(luò)演算計(jì)算交換式工業(yè)以太網(wǎng)中的最大時(shí)延［J］.控制與決策，2005，20（1）：117-120.

編輯陸燕菲

Research on Optimization of AFDX Real-tim e Using Mixed Queue Scheduling Policy

LIU Jing1，2
（1.College of Mathematics and Information Science，Weinan Normal University，Weinan 714099，China；2.Research Center of Weinan Wisdom City Engineering Technology，Weinan 714099，China）

Avionics Full Duplex Switched Ethernet Network（AFDX）is an aircraft data network using the First Come First Serve（FCFS）scheduling strategy to transmit data.In this circumstance，the delay of the critical data is large while congestion is uncertain.To cope with this problem，this paper presents a Mixed Queue Scheduling Policy on AFDX（MQSA）to optimize the real-time performance.The policy integrates the advantages of FCFS，Static Priority（SP）and Deficit Round Robin（DRR）.It analyzes the delay bounds using MQSA based on network calculus，and delay bounds of critical data can meet requirement of communication.Simulation results show that this policy not only ensures real time critical data，but also ensures the fairness of scheduling non-critical data，and it can isolate malicions data flow effectively.

mixed queue scheduling policy；network calculus；Avionics Full Duplex Switched Ethernet Network（AFDX）；Virtual Link（VL）；end to end delay

劉 靜.應(yīng)用混合隊(duì)列調(diào)度策略的AFDX實(shí)時(shí)性優(yōu)化研究［J］.計(jì)算機(jī)工程，2015，41（11）：135-141.

英文引用格式：Liu Jing.Research on Optimization of AFDX Real-time Using Mixed Queue Scheduling Policy［J］. Computer Engineering，2015，41（11）：135-141.

1000-3428（2015）11-0135-07

A

TN915.03

10.3969/j.issn.1000-3428.2015.11.024

國(guó)家自然科學(xué)青年基金資助項(xiàng)目（61402335）；國(guó)家統(tǒng)計(jì)局科研計(jì)劃基金資助項(xiàng)目（2012LY 056）；陜西省自然科學(xué)基金資助項(xiàng)目（2012JM 8031）；渭南師范學(xué)院科研計(jì)劃基金資助項(xiàng)目（15YKP002）。

劉 靜（1983-），女，講師、博士研究生，主研方向：航空電子系統(tǒng)，智能信息處理。

2014-12-02

2015-02-01 E-m ail：liujing8318@126.com