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

劉 靜

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

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

劉 靜1，2

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

定義1（廣義增函數(shù)） 廣義增函數(shù)f（t）是指當s≤t時，f（s）≤f（t）的函數(shù)。可記F為在t＜0時f（t）=0的廣義增函數(shù)的集合，F(xiàn)0為在t≤0時f（t）=0的廣義增函數(shù)的集合。

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

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

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

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

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

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

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

圖1 延遲和積壓示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 模型設(shè)計

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

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

本文將端系統(tǒng)發(fā)出優(yōu)先級為P1的硬實時數(shù)據(jù)流稱為緊急數(shù)據(jù)流（URG），優(yōu)先級為P2的硬實時數(shù)據(jù)流稱為傳感器數(shù)據(jù)流（SEN），優(yōu)先級為P3的硬實時數(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)，且大部分數(shù)據(jù)幀的長度小于1 000 Byte［14］。

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

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

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

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

3.2 模型分析

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

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

3.3 模型仿真

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

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

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

3.4 結(jié)果比較

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

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

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

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

4 結(jié)束語

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

［1］ 郭利鋒，王 勇，張 磊，等.AFDX交換機的隊列整形調(diào)度研究［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］.電子學報，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ò)演算的計算機網(wǎng)絡(luò)性能分析模型研究［D］.長沙：國防科學技術(shù)大學，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ò)演算計算交換式工業(yè)以太網(wǎng)中的最大時延［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)用混合隊列調(diào)度策略的AFDX實時性優(yōu)化研究［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

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

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

2014-12-02

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