劉曉勝，李瑩雪，張鵬宇，鄭檢，吳海濤

（哈爾濱工業(yè)大學(xué) 電氣工程及自動化學(xué)院，黑龍江 哈爾濱 150001）

1 引言

AFDX 是用于航空子系統(tǒng)之間進(jìn)行數(shù)據(jù)交換的一種通信協(xié)議，調(diào)度算法是保證AFDX 實(shí)時(shí)性的關(guān)鍵。常用的調(diào)度機(jī)制，如先進(jìn)先出策略，靜態(tài)優(yōu)先級調(diào)度（AVLSP）和加權(quán)公平隊(duì)列[1]，在大型AFDX網(wǎng)絡(luò)結(jié)構(gòu)下轉(zhuǎn)發(fā)同一優(yōu)先級的數(shù)據(jù)時(shí)可能會由于路徑的不同而使各個(gè)虛擬鏈路上的數(shù)據(jù)延時(shí)上限差過大，導(dǎo)致AFDX網(wǎng)絡(luò)負(fù)載不平衡。

分組交換網(wǎng)絡(luò)[2]中,基于虛擬時(shí)鐘算法是通過使用一個(gè)按數(shù)據(jù)分組的虛擬時(shí)鐘值排序的隊(duì)列來模擬公平隊(duì)列中的多個(gè)隊(duì)列 從而在不同的流之間實(shí)現(xiàn)對資源的公平分配。借助這一思想，在AFDX 網(wǎng)絡(luò)中調(diào)度同一優(yōu)先級的數(shù)據(jù)時(shí)將其等待時(shí)間從小到大排隊(duì)，優(yōu)先轉(zhuǎn)發(fā)排在隊(duì)首的數(shù)據(jù)，可以減小同優(yōu)先級的數(shù)據(jù)延時(shí)差，均衡AFDX 網(wǎng)絡(luò)負(fù)載。在計(jì)算網(wǎng)絡(luò)延時(shí)時(shí)間上限時(shí)采用軌跡方法[3]，代替網(wǎng)絡(luò)演算法[4]，這種方法分析數(shù)據(jù)包在它傳輸路徑上的最壞情況，更適合計(jì)算延時(shí)上限。

本文將虛擬時(shí)鐘引入AFDX 網(wǎng)絡(luò)，針對同優(yōu)先級的數(shù)據(jù)調(diào)度，進(jìn)行建模與分析。利用軌跡方法對同優(yōu)先級數(shù)據(jù)的傳輸延時(shí)上限進(jìn)行計(jì)算，并與靜態(tài)優(yōu)先級調(diào)度方法下的延時(shí)時(shí)間比較，說明虛擬時(shí)鐘調(diào)度方法可以均衡AFDX網(wǎng)絡(luò)負(fù)載并通過仿真進(jìn)行驗(yàn)證。

2 基于虛擬時(shí)鐘的調(diào)度算法

虛擬時(shí)鐘這一概念廣泛應(yīng)用在分組交換網(wǎng)絡(luò)中，它支持多優(yōu)先級服務(wù)，用一個(gè)根據(jù)虛擬時(shí)鐘排隊(duì)的隊(duì)列模擬公平隊(duì)列調(diào)度中的多個(gè)隊(duì)列[5]。將虛擬時(shí)鐘這一思想引入AFDX 網(wǎng)絡(luò)中，實(shí)現(xiàn)均衡網(wǎng)絡(luò)負(fù)載，保證數(shù)據(jù)轉(zhuǎn)發(fā)的實(shí)時(shí)性。

2.1 AFDX 網(wǎng)絡(luò)

AFDX 是具有確定性的航空電子交換式以太網(wǎng)，支持星型拓?fù)浣Y(jié)構(gòu)。AFDX 網(wǎng)絡(luò)結(jié)構(gòu)示例如圖1所示。它包括六個(gè)交換機(jī)S1-S6 和六個(gè)終端系統(tǒng)e1-e6，交換機(jī)工作在全雙工方式下，端系統(tǒng)的之間的每條數(shù)據(jù)鏈路提供了一個(gè)虛擬的點(diǎn)對點(diǎn)的單向通信通道。虛擬鏈路（VL）是虛擬的通信通道，每個(gè)虛擬鏈路建立了一個(gè)從源終端系統(tǒng)到多個(gè)目的終端系統(tǒng)的無方向的邏輯連接。圖1中v6 是一個(gè)多播的虛擬鏈路，傳輸路徑分別是e4-S3-S4-S5-S6-e5 和e4-S3-S6-e6，其它的則是單播的虛擬鏈路，例如v3，它的傳輸路徑是e2-S1-S4-S5-S6-e6。

圖1 AFDX 網(wǎng)絡(luò)結(jié)構(gòu)示例 Fig.1 An illustrative AFDX network configuration

虛擬鏈路的重要參數(shù)是帶寬分配間隔（BAG）和最大幀長（Smax）。帶寬分配間隔是指兩個(gè)連續(xù)的AFDX 幀起始位之間的最小間隔，BAG的值在l～128 ms 內(nèi)。每個(gè)VL 的最大可用帶寬是由它的BAG 和它所規(guī)定的Smax所決定的。

2.2 AVLSP 調(diào)度算法

AFDX 網(wǎng)絡(luò)中不同類型的數(shù)據(jù)按照其緊急程度賦予不同的優(yōu)先級。在AVLSP 調(diào)度策略下數(shù)據(jù)流經(jīng)過整形后，進(jìn)入相關(guān)優(yōu)先級的緩沖隊(duì)列中，虛電路調(diào)度器工作通常以非搶占方式和工作保持方式進(jìn)行優(yōu)先級調(diào)度。

緊急數(shù)據(jù)具有高優(yōu)先級，高優(yōu)先級數(shù)據(jù)幀發(fā)送延遲小于低優(yōu)先級數(shù)據(jù)幀的延遲，這克服了標(biāo)準(zhǔn)AFDX調(diào)度器中所有數(shù)據(jù)幀的延遲上界均相同的缺陷，但是忽略了數(shù)據(jù)幀在隊(duì)列中的等待時(shí)間。為解決這一問題，本文提出虛擬時(shí)鐘調(diào)度策略。

2.3 虛擬時(shí)鐘調(diào)度算法

在分組交換網(wǎng)絡(luò)中，對每個(gè)分組的虛擬時(shí)鐘值進(jìn)行排隊(duì)，優(yōu)先轉(zhuǎn)發(fā)排在隊(duì)首的數(shù)據(jù)。AFDX網(wǎng)絡(luò)中利用虛擬時(shí)鐘的調(diào)度方法與分組交換網(wǎng)絡(luò)中虛擬時(shí)鐘的調(diào)度有所不同，數(shù)據(jù)的轉(zhuǎn)發(fā)是以幀為單位，采用非搶占優(yōu)先級，在每個(gè)交換節(jié)點(diǎn)上為同一優(yōu)先級的虛擬鏈路上的數(shù)據(jù)都建立一個(gè)虛擬時(shí)鐘iVC，數(shù)據(jù)包i是虛擬鏈路vi上的數(shù)據(jù)，i為數(shù)據(jù)所在的虛擬鏈路號。

計(jì)算數(shù)據(jù)包到達(dá)某一節(jié)點(diǎn)前的延時(shí)，延時(shí)最小的數(shù)據(jù)包最先到達(dá)該節(jié)點(diǎn)，考慮該節(jié)點(diǎn)正處理數(shù)據(jù)，則該數(shù)據(jù)包在這一節(jié)點(diǎn)處等待處理的時(shí)間最長，iVC為虛擬鏈路iVL的數(shù)據(jù)到達(dá)節(jié)點(diǎn)時(shí)刻起至節(jié)點(diǎn)開始處理該數(shù)據(jù)為止的等待時(shí)間。將到達(dá)該節(jié)點(diǎn)的同一優(yōu)先級的iVC從小到大排列，優(yōu)先處理轉(zhuǎn)發(fā)排在隊(duì)首的數(shù)據(jù)。

2.4 建模分析

分析圖2所示的一種AFDX 網(wǎng)絡(luò)結(jié)構(gòu)。

圖2 AFDX 示例結(jié)構(gòu) Fig.2 An illustrative model

假設(shè)圖2中v1-v5 都是單播的虛擬鏈路，具有相同的BAG（4 000 μs）和Smax（4 000 bits），其中v1 和v2 具有高優(yōu)先級，v3-v5 具有低優(yōu)先級。每條鏈路工作速率為100 Mb/s，數(shù)據(jù)在鏈路上的延遲時(shí)間為16 μs，每個(gè)節(jié)點(diǎn)處理數(shù)據(jù)時(shí)間iC為 maxS/R= 40 μs。

系統(tǒng)中數(shù)據(jù)包都經(jīng)過靜態(tài)的路徑。高優(yōu)先級的數(shù)據(jù)包1 和數(shù)據(jù)包2 的路徑分別為e1-S-S1-S4-S5-S6-S7-e6和 e2-SS-S1-S2-S3-S6-S7-e6，低優(yōu)先級的數(shù)據(jù)包3-5 的傳輸路徑分別為e3-S1-S4-S7-e7，e4-S4-S7-e7 和 e5-S-S4-S5-S6-S7-e7。S 和SS 為兩個(gè)延時(shí)環(huán)節(jié)，延時(shí)時(shí)間分別為40 μs 和80 μs。

分析數(shù)據(jù)包1 和2，到達(dá)節(jié)點(diǎn)S1 前的路徑分別為e1-S 和 e2-SS，數(shù)據(jù)包到達(dá)節(jié)點(diǎn)S1 前的延時(shí)包括節(jié)點(diǎn)處延時(shí)和鏈路延時(shí)。計(jì)算數(shù)據(jù)包1 和2到達(dá)節(jié)點(diǎn)S1 之前的延時(shí)時(shí)間分別為40 + 80 + 16 × 2 = 152 μs 和40 + 40 + 16 × 2 = 112 μs，說明數(shù)據(jù)包2 先到達(dá)S1，由于數(shù)據(jù)包3 更早到達(dá)節(jié)點(diǎn)而被優(yōu)先處理，采用非搶占優(yōu)先級，數(shù)據(jù)包1 和2等待處理，到達(dá)S1 時(shí)分別為它們建立虛擬時(shí)鐘VC1和VC2，記錄從到達(dá)節(jié)點(diǎn)開始至開始被處理的等待時(shí)間。VC1＜VC2，則數(shù)據(jù)包1 排在隊(duì)首，節(jié)點(diǎn)處理完數(shù)據(jù)包3 后優(yōu)先處理轉(zhuǎn)發(fā)數(shù)據(jù)包1。

數(shù)據(jù)包3-5 同為低優(yōu)先級，數(shù)據(jù)包4 先到達(dá)節(jié)點(diǎn)S4 優(yōu)先被處理，數(shù)據(jù)包3 和5 到達(dá)節(jié)點(diǎn)S4前傳輸路徑分別為e3 - S1 和 e5-S，延時(shí)分別為40 × 2 + 16 × 2 = 112 μs 和40 + 80 + 16 × 2 = 152 μs，虛擬時(shí)鐘VC5＜VC3,數(shù)據(jù)包5 優(yōu)先被處理。

3 延時(shí)分析計(jì)算

利用網(wǎng)絡(luò)演算法[6]計(jì)算端到端的延遲和抖動，延時(shí)上限為服務(wù)曲線和到達(dá)曲線的最大水平距離，但是幾條鏈路上的數(shù)據(jù)不能同時(shí)被轉(zhuǎn)發(fā)，多個(gè)服務(wù)曲線相加的情況不可能發(fā)生。軌跡方法確定AFDX 網(wǎng)絡(luò)延時(shí)上限時(shí)考慮隨機(jī)的數(shù)據(jù)流，減少不必要的悲觀因素的影響。

3.1 軌跡方法

軌跡方法計(jì)算確定的延時(shí)上限，它假設(shè)數(shù)據(jù)流只經(jīng)過它路徑上的各節(jié)點(diǎn)一次，不會重復(fù)經(jīng)過。

虛擬鏈路端到端的延時(shí)時(shí)間是通過每個(gè)節(jié)點(diǎn)的時(shí)間和鏈路上的延遲時(shí)間之和，通過每個(gè)節(jié)點(diǎn)的時(shí)間由3 個(gè)因素決定：數(shù)據(jù)包到達(dá)節(jié)點(diǎn)時(shí)刻是否有剩余數(shù)據(jù)幀被處理、數(shù)據(jù)的優(yōu)先級和節(jié)點(diǎn)處理數(shù)據(jù)包的時(shí)間。

繁忙周期[7]是軌跡方法中的一個(gè)重要概念。繁忙周期bp（busy period）定義為一段沒有空閑時(shí)間的時(shí)間間隔[t,t’），t為節(jié)點(diǎn)處理完在t時(shí)刻前到達(dá)數(shù)據(jù)的時(shí)刻，t’為節(jié)點(diǎn)處理完到達(dá)數(shù)據(jù)包的時(shí)刻。利用軌跡方法計(jì)算時(shí)認(rèn)為數(shù)據(jù)在t時(shí)刻開始傳輸，每個(gè)節(jié)點(diǎn)相當(dāng)于AFDX 網(wǎng)絡(luò)中的交換機(jī)，每個(gè)數(shù)據(jù)包對應(yīng)相應(yīng)的虛擬鏈路。計(jì)算iV在每個(gè)節(jié)點(diǎn)處的延時(shí)時(shí)間都是在每個(gè)節(jié)點(diǎn)的繁忙周期內(nèi)。

軌跡方法[8]定義，iV的最大端到端延時(shí)被限定在：

t是數(shù)據(jù)包產(chǎn)生的起始時(shí)刻，lasti是VL 訪問的最后節(jié)點(diǎn)，是數(shù)據(jù)在最后一個(gè)節(jié)點(diǎn)的發(fā)送時(shí)間。文獻(xiàn)[9]中給出定義公式，結(jié)果是經(jīng)過Vi的其它數(shù)據(jù)在節(jié)點(diǎn)處的通過時(shí)間、Vi在節(jié)點(diǎn)繁忙周期內(nèi)的處理時(shí)間、傳輸路徑上的延時(shí)和Vi不經(jīng)過最后一個(gè)節(jié)點(diǎn)時(shí)的最大數(shù)據(jù)包處理時(shí)間之和。

3.2 示例分析

根據(jù)虛擬時(shí)鐘調(diào)度算法，圖2中AFDX 網(wǎng)絡(luò)在節(jié)點(diǎn)S1、S4 和S6 處理數(shù)據(jù)包的順序分別為packet 3-packet 1-packet 2 ，packet 4-packet 1-packet 5-packet 3 和packet 2-packet 1-packet 5。將數(shù)據(jù)包i記為pi。的計(jì)算過程如圖3所示。結(jié)果為 536 μs。根據(jù)公式（1）可計(jì)算出最壞情況下的延時(shí)上限為+C1= 536 + 40 = 576 μs。圖4所示v2 上的結(jié)果為416 μs，端到端延時(shí)上限為416+40=456 μs。表1給出其它虛擬鏈路上的數(shù)據(jù)包在最壞情況下的端到端延時(shí)上限計(jì)算結(jié)果。

圖3 計(jì)算過程圖解 Fig.3 The computation of

圖4 計(jì)算過程圖解 Fig.4 The computation of

表1 其它鏈路上的延時(shí)上限計(jì)算 Tab.1 The upper bound of delay on other three VLs

3.3 調(diào)度算法比較與分析

若圖2中示例AFDX 網(wǎng)絡(luò)結(jié)構(gòu)在AVLSP 調(diào)度策略下調(diào)度，優(yōu)先級高的數(shù)據(jù)包被優(yōu)先處理和轉(zhuǎn)發(fā)。對于數(shù)據(jù)包1 和2 節(jié)點(diǎn)S1 處數(shù)據(jù)包處理順序?yàn)閜3-p2-p1，對數(shù)據(jù)包3-5，節(jié)點(diǎn)S4 和節(jié)點(diǎn)S7 數(shù)據(jù)包處理順序分別為 p4-p1-p3-p5 和p4 -p3-p5。和的計(jì)算過程如圖5和6所示，AVLSP 調(diào)度策略下數(shù)據(jù)包1 和2 的延時(shí)上限分別為576 + 40 = 616 μs 和376 + 40 = 416 μs。其它數(shù)據(jù)包在最壞情況下的端到端延時(shí)上限計(jì)算結(jié)果見表2。

圖5 AVLSP 調(diào)度策略的Fig.5 in AVLSP scheduling

圖6 AVLSP 調(diào)度策略的 Fig.6 in AVLSP scheduling

表2 其它鏈路上的延時(shí)上限計(jì)算 Tab.2 The upper bound of delay in FIFO scheduling

與3.2 中的計(jì)算結(jié)果比較，虛擬時(shí)鐘調(diào)度下數(shù)據(jù)包1和2的延時(shí)上限差為120 μs，比在AVLSP調(diào)度下減小了40%，根據(jù)表1和表2低優(yōu)先級的數(shù)據(jù)包之間最大延時(shí)上限差是448 μs，也小于AVLSP 調(diào)度下的結(jié)果。比較結(jié)果說明當(dāng)路徑對同優(yōu)先級數(shù)據(jù)包延時(shí)上限有很大影響時(shí)本文提出的調(diào)度算法能夠均衡網(wǎng)絡(luò)負(fù)載。

4 仿真與分析

按照圖2示例的AFDX 網(wǎng)絡(luò)結(jié)構(gòu)為AFDX 端系統(tǒng)配置五條虛擬鏈路，兩個(gè)優(yōu)先級，利用網(wǎng)絡(luò)仿真軟件OPNET 進(jìn)行仿真，模型如圖7所示，得出兩種調(diào)度方式下各個(gè)虛擬鏈路端到端的延時(shí)，結(jié)果如圖8所示。

圖7 仿真模型 Fig.7 Simulator model

比較兩種調(diào)度策略下的仿真結(jié)果，數(shù)據(jù)包1和5 在虛擬時(shí)鐘調(diào)度下延時(shí)上限比AVLSP 調(diào)度下的結(jié)果小，其它數(shù)據(jù)包的延時(shí)上限比較大，虛擬時(shí)鐘調(diào)度下延時(shí)上限變化比較平緩，即延時(shí)上限差小。計(jì)算虛擬時(shí)鐘調(diào)度和AVLSP 調(diào)度下各個(gè) 虛擬鏈路的數(shù)據(jù)包最大延時(shí)上限差分別是420 μs和280 μs，虛擬時(shí)鐘調(diào)度的優(yōu)越性得到驗(yàn)證。

圖8 仿真結(jié)果 Fig.8 Results of simulation

5 結(jié)論

本文針對同優(yōu)先級的虛擬鏈路數(shù)據(jù)包的處理和轉(zhuǎn)發(fā)提出了虛擬時(shí)鐘調(diào)度方法，減小數(shù)據(jù)間的延時(shí)上限差，達(dá)到均衡網(wǎng)絡(luò)負(fù)載的目的。對示例的AFDX 網(wǎng)絡(luò)結(jié)構(gòu)利用軌跡方法計(jì)算兩種調(diào)度方法下各個(gè)虛擬鏈路數(shù)據(jù)的端到端延時(shí)上限，基 于虛擬時(shí)鐘的調(diào)度方法延時(shí)差比AVLSP 調(diào)度方式減小至少15%，并通過仿真驗(yàn)證。

在實(shí)際情況下AFDX 的網(wǎng)絡(luò)結(jié)構(gòu)更加復(fù)雜，虛擬鏈路上的數(shù)據(jù)傳輸延時(shí)受路徑影響更大，利用本文提出的調(diào)度方法對均衡網(wǎng)絡(luò)負(fù)載、保證數(shù)據(jù)傳輸確定性具有重要意義。本文介紹的虛擬時(shí)鐘調(diào)度方法要求在每個(gè)節(jié)點(diǎn)為每個(gè)數(shù)據(jù)包建立虛擬時(shí)鐘，會影響在高速網(wǎng)絡(luò)下的可擴(kuò)展性。因此，對這種調(diào)度方法還需要進(jìn)一步改進(jìn)。

[1] 陳昕，周擁軍，蔣文保，等，萬劍雄.AFDX 協(xié)議性能分析及調(diào)度算法研究[J].電子學(xué)報(bào)，2009,37（5）.

[2] 高文宇，陳松喬，王建新.分組交換網(wǎng)絡(luò)中虛擬時(shí)鐘調(diào)度算法研究[J].微電子學(xué)與計(jì)算機(jī)，2004,21（7）.

[3] Henri Bauer, Jean-Luc Scharbarg, Christian Fraboul.Applying Trajectory Approach with Static Priority Queuing for Improving the Use of Available AFDX resources.Real-Time Syst, no.48.

[4] 張連明，陳志剛，黃國盛.網(wǎng)絡(luò)演算理論及應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2006（27）.

[5] 石改輝，張?jiān)?優(yōu)先級管理的全雙工交換式以太網(wǎng)實(shí)時(shí)通信[J].活力與指揮控制，2009（11）.

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

[7] Jean-Luc Scharbarg, Frédéric Ridouard ，Christian Raboul.A Probabilistic Analysis of End-To-End Delays on an AFDX Avionic Network.IEEE Transactions on Industrial Informatics, 2009，5（1）.

[8] Henri Bauer, Jean-Luc Scharbarg, Christian Fraboul.Improving the Worst-Case Delay Analysis of an AFDX Network Using an Optimized Trajectory Approach.IEEE Transactions on Industrial Informatics, 2010，6（4）.

[9] S.Martin and P.Minet.Schedulability Analysis of Flows Scheduled with FIFO：Application to the Expedited Forwarding Class.Proc.20th Int.Parallel and Distrib.Process.Symp.Rhodes Island, Greece, Apr.2006.