時間觸發(fā)光纖通道調(diào)度算法確定性分析

譚小虎，王 勇，褚文奎，劉 安

空軍工程大學(xué) 航空航天工程學(xué)院，西安 710038

1 引言

FC（Fibre Channel，光纖通道）憑借在延遲率、錯位率以及傳輸速率等方面的優(yōu)勢，成為新型航電系統(tǒng)的首選協(xié)議[1]，可以滿足航電網(wǎng)絡(luò)在實時性、可靠性等方面的要求。為支持FC協(xié)議在航電系統(tǒng)中的應(yīng)用，F(xiàn)C協(xié)議標準開發(fā)委員會專門組織建立一個分委會，該分委會制定出針對航空電子環(huán)境下的協(xié)議草案，即FC-AE（光纖通道航空電子環(huán)境），其內(nèi)容就是擴展FC協(xié)議，同時發(fā)展以光纖通道為基本的航電增強型專用系統(tǒng)[2]。FC-AEASM（光纖通道-航空電子環(huán)境-匿名消息）作為FC-AE協(xié)議的子集，就是針對航電系統(tǒng)應(yīng)用而提供的上層協(xié)議，用于航電系統(tǒng)各設(shè)備間安全和低延遲的通信[3]。但是該協(xié)議中卻沒有給出終端系統(tǒng)中消息間的調(diào)度算法，對于大部分終端設(shè)備采用先來先服務(wù)（FCFS）的數(shù)據(jù)發(fā)送控制算法使得消息端到端延遲具有很大的不確定性，造成對系統(tǒng)的分析困難。

目前國內(nèi)對光纖通道方面的研究主要集中在網(wǎng)絡(luò)傳輸?shù)目煽啃浴⑼ㄐ畔到y(tǒng)拓撲結(jié)構(gòu)以及上層協(xié)議的轉(zhuǎn)換方面。文獻[4-6]以網(wǎng)絡(luò)任務(wù)模型為基礎(chǔ)，建立了可靠性模型，同時針對光纖通道三種拓撲結(jié)構(gòu)，推導(dǎo)出可靠性的表達式。文獻[7]對于FC在航空電子環(huán)境中的體系結(jié)構(gòu)進行了論述。文獻[8]對光纖通道的特性進行了介紹，同時對典型的幾種網(wǎng)絡(luò)和總線進行了分析比較。針對網(wǎng)絡(luò)中消息的發(fā)送控制算法，文獻[9]提出了基于實時排隊論的調(diào)度算法，它借助延時率可以反映系統(tǒng)實時性。

基于以上分析，提出時間觸發(fā)調(diào)度算法，通過靜態(tài)規(guī)劃消息的調(diào)度表，通過全局時鐘來觸發(fā)每個消息的發(fā)送，使得網(wǎng)絡(luò)中所有消息都擁有較強的時間確定性。

2 數(shù)據(jù)結(jié)構(gòu)模型設(shè)計

航空電子系統(tǒng)中存在很多類型消息，不同消息對時間延遲的要求也就不同。類似警報和傳感器的消息就是具有硬實時要求的緊急消息，具有嚴格的時延要求，而對于文件發(fā)送等消息就是非緊急消息，時延要求相對較低[10]。所以在時間觸發(fā)FC終端接口中將具有高時延要求的緊急數(shù)據(jù)設(shè)置為時間觸發(fā)消息，其他非緊急消息設(shè)置為事件觸發(fā)消息。根據(jù)FC-AE-ASM消息幀格式，數(shù)據(jù)傳輸過程中將消息幀幀頭中保留的8～11 Byte作為消息類型的標識，設(shè)定用0110表示該消息為時間觸發(fā)消息，其余除了0000表示形式外代表該消息為事件觸發(fā)消息，改進的消息幀格式如圖1所示。對于時間觸發(fā)消息采用時間觸發(fā)的調(diào)度形式進行發(fā)送，而對于事件觸發(fā)消息則采用傳統(tǒng)的先來先服務(wù)策略進行發(fā)送。

圖1 FC-AE-ASM消息格式

3 時間觸發(fā)調(diào)度算法設(shè)計

調(diào)度算法主要涉及對基本周期和矩陣周期的確定。對于矩陣周期，首先根據(jù)消息種類規(guī)劃初始系統(tǒng)矩陣MC0，然后對MC0進行優(yōu)化，得到最終系統(tǒng)矩陣MC。

（1）對基本周期（BC）和矩陣周期（MC）的持續(xù)時間MCT進行確定

首先對于周期消息按照周期遞增的順序排序，得到消息序列 T=[T1,T2,…,TM]，其中 Ti+1≥Ti，(i∈[1,M-1])。取輸入周期消息的最小周期T1作為基本周期BC。規(guī)定MC的持續(xù)時間MCT是輸入周期信號周期的最小公倍數(shù)或者最小公倍數(shù)的整數(shù)倍來保證滿足傳輸每一個消息的平均周期[11]，從式（1）的計算中可得矩陣周期（MC）的行數(shù)R。

式（3）中n是為防止非周期型號對周期信號造成干擾加在兩個周期間的隔離窗口[12]，IDLE是防止傳輸過程中上個基本周期未傳完消息對下一個周期影響所加入的保護間隔。式（4）中Ti是各個通信節(jié)點的消息發(fā)送周期，T1是所有消息的最小傳輸周期。如果a＜νmax，那么生成矩陣的列數(shù)為[a]+3，其中[a]用來傳輸TT消息，一列傳輸ET消息，一列為周期消息和非周期之間的隔離窗口，一列為兩個基本周期之間的保護間隔。如果a＞νmax，則說明鏈路傳輸速率不夠，需要增加傳輸速率來完成消息的發(fā)送。

（3）生成待優(yōu)化的初始矩陣MC0

根據(jù)消息集合I，在滿足發(fā)送周期的情況下將消息按列依次裝入R列矩陣中，得到待優(yōu)化矩陣MC0。

（4）初始矩陣的優(yōu)化

采用價值函數(shù)P對初始矩陣進行優(yōu)化，由此得到最終的優(yōu)化矩陣MC。

式（2）表示消息集合，其中ki(1≤i≤R)表示第i個消息的實例個數(shù)。

（2）確定一個基本周期（BC）可以傳輸?shù)南€數(shù)ν

根據(jù)總線的傳輸波特率B和周期消息比特數(shù)Num以及消息的傳輸時間Lt等參數(shù)，由式（3）可以得出一個基本周期中可以傳輸消息的最大個數(shù)；再者根據(jù)式（4）可以得出基本周期中傳輸?shù)钠骄€數(shù)：

其中P表示在矩陣周期中將消息集合中每個消息傳輸完成實際所需時間，其達到最小值也就得到最優(yōu)值。表示第i個消息的第 j次消息實例的發(fā)送時刻；R、C、Dc分別表示矩陣周期的行數(shù)、列數(shù)和時間窗的寬度。

4 基于FCFS服務(wù)策略的調(diào)度算法及確定性分析

面對光纖通道的高速性，現(xiàn)如今針對終端節(jié)點的調(diào)度算法普遍采用FCFS的服務(wù)策略，其算法復(fù)雜度低，實現(xiàn)條件簡便，可以很好滿足基于事件觸發(fā)的通信系統(tǒng)。但是消息的不可控性，導(dǎo)致引入了時間抖動，抖動的可變性要求采用網(wǎng)絡(luò)演算的方式來計算網(wǎng)絡(luò)的端到端延時，需要說明的是，最后計算的端到端延時都是最壞條件下的上限值[13]。

4.1 網(wǎng)絡(luò)演算理論

在運用網(wǎng)絡(luò)演算理論解決問題的過程中，采用聚集函數(shù)R(t)對進入網(wǎng)絡(luò)的流量進行特征化的描述，該函數(shù)表示在時間[ ]

0,t內(nèi)流入網(wǎng)絡(luò)的數(shù)據(jù)流的比特數(shù)。在借助網(wǎng)絡(luò)演算來計算網(wǎng)絡(luò)端到端的延時時，需要介紹數(shù)據(jù)流的到達曲線和服務(wù)曲線兩個重要概念。

定義1[13]如果存在一個定義于t∈[0,+∞)上的廣義增函數(shù)α，只有在滿足對于任意s≤t時，才有R(t)-R(s)≤α(t-s)，那么數(shù)據(jù)流R的到達曲線就是函數(shù)α。

定義2[13]在系統(tǒng)S中，假設(shè)輸入數(shù)據(jù)流和輸出數(shù)據(jù)流的聚集函數(shù)分別為R和R*，同時存在一個廣義增函數(shù) β，滿足 β(0)=0，使得R*≥R?β，那么就稱函數(shù) β為系統(tǒng)S的服務(wù)曲線。

引理1[14]假設(shè)在某個系統(tǒng)中，數(shù)據(jù)流的到達曲線為α，服務(wù)曲線為β，則進入系統(tǒng)的數(shù)據(jù)流在系統(tǒng)中的延遲上界滿足關(guān)系：

如圖2所示。

圖2 延遲上界計算

4.2 FC網(wǎng)絡(luò)在FCFS服務(wù)策略下確定性分析

采用M端口的FC網(wǎng)絡(luò)交換機，每個端口的數(shù)據(jù)流到達曲線為αi，i=1,2,…,M，根據(jù)端口到達流量的可加性得交換機需處理的數(shù)據(jù)聚合流為：

用C表示交換機的輸出物理鏈路帶寬，同時信用值假設(shè)為無窮大。假設(shè)所有數(shù)據(jù)中最大的數(shù)據(jù)幀長為lmax，每個端口的數(shù)據(jù)連續(xù)傳輸速率為ri，突發(fā)數(shù)據(jù)最大尺寸為bi，根據(jù)FCFS服務(wù)策略可得數(shù)據(jù)的延遲上界為：

對式（8）進行證明：對交換機在忙時段[t1,t2]內(nèi)進行分析，其中t1表示忙時段的開始時間，可以得到：

考慮到忙期的結(jié)束時間點t2，交換機可能處于空閑或者處理 t-τ(0＜τ＜)時刻到達的未處理完的數(shù)

200據(jù)幀兩種狀態(tài)，如果這時處理的數(shù)據(jù)幀是聚合流中最長的，就有：

根據(jù)式（8）和式（9）可以得到：

表示R*≥R?β，再根據(jù)定義2就可以得到輸入數(shù)據(jù)流的到達曲線為：

如果采用漏桶整形器在交換機的端口對到達數(shù)據(jù)流進行流量整形，那么端口的數(shù)據(jù)流到達曲線就可以表示為：

正在無聊之際，在縣城車站上班的表哥打電話給我，要我周日去找他玩，我高興得跳了起來。雖說表哥比我大了十七歲，在一起的時間也少，可我們卻玩得來。

式（13）中ri表示i端口數(shù)據(jù)連續(xù)傳輸速率，bi表示到達數(shù)據(jù)流的最大突發(fā)長度。再根據(jù)到達數(shù)據(jù)流的可加性，則所有端口數(shù)據(jù)流的到達曲線為：

再根據(jù)引理1可得數(shù)據(jù)的延遲上界為：

由此得證。

根據(jù)定理1可知，交換機在服務(wù)策略FCFS模式下，所有數(shù)據(jù)流的延遲上界都同為584 μs。

5 時間觸發(fā)調(diào)度算法確定性分析

基于時間觸發(fā)的FC終端接口和普通FC終端接口的硬件結(jié)構(gòu)和網(wǎng)絡(luò)拓撲相同，所以在對時間觸發(fā)FC交換式網(wǎng)絡(luò)進行性能分析時建立和普通光纖通道相同的交換式網(wǎng)絡(luò)，利用消息的端到端延時來分析網(wǎng)絡(luò)的確定性。

5.1 時間觸發(fā)光纖通道網(wǎng)絡(luò)時間確定性分析

航電系統(tǒng)是一個對消息實時性確定性要求很高的系統(tǒng)，消息的可靠傳輸關(guān)系到網(wǎng)絡(luò)的確定性，消息的傳輸實時性又關(guān)系到航電系統(tǒng)的正常運行。對FC網(wǎng)絡(luò)實時性和確定性進行分析，采用端到端延時作為網(wǎng)絡(luò)性能的評價指標。所謂端到端時延表示消息在端系統(tǒng)的發(fā)送時延、鏈路的傳輸時延和交換機的轉(zhuǎn)發(fā)時延的累計和[15]，其各個時延部分的組成如圖3所示。

圖3 時延各部分組成

圖3 中t1表示上層應(yīng)用的消息分裝為FC-AE-ASM數(shù)據(jù)幀所用的時間，系統(tǒng)性能的好壞決定所用時間的長短，一般來說該時間可以忽略。t2表示數(shù)據(jù)幀在發(fā)送隊列中等待的時間，主要由隊列長度和調(diào)度策略決定，是影響網(wǎng)絡(luò)實時性的因素，通過消息到達調(diào)度表規(guī)劃發(fā)送時間和消息到達隊列時間之差可得。t3和t5表示消息在鏈路傳輸時間，該值為固定值。t4表示消息經(jīng)過交換機的轉(zhuǎn)發(fā)延時，考慮到在時間觸發(fā)FC網(wǎng)絡(luò)中交換機也要配置相應(yīng)調(diào)度表，所以該時間也是一個確定值，通過數(shù)據(jù)幀在交換機調(diào)度表中規(guī)劃的調(diào)度時刻和消息到達交換機時間之差求得。

5.2 時間觸發(fā)光纖通道網(wǎng)絡(luò)建模和確定性分析

鑒于時間觸發(fā)FC網(wǎng)絡(luò)和普通FC網(wǎng)絡(luò)結(jié)構(gòu)相同，所以對時間觸發(fā)FC網(wǎng)絡(luò)的建模采取普通FC的交換式網(wǎng)絡(luò)結(jié)構(gòu)。網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示。網(wǎng)絡(luò)中包括一個交換機和10個終端系統(tǒng)。各個終端節(jié)點的消息設(shè)置如表1所示，鏈路延遲取1 μs。

圖4 TTFC網(wǎng)絡(luò)結(jié)構(gòu)

表1 消息配置信息

根據(jù)消息周期生成的各個消息的調(diào)度時刻如圖5所示。

在交換機中每條時間觸發(fā)消息按照調(diào)度表在各自的調(diào)度時刻進行發(fā)送，交換機速率取1 Gb/s。用tmn表示消息調(diào)度時間，其中m表示源節(jié)點，n表示目的節(jié)點。取每種消息最早調(diào)度時刻作為其延遲計算的標準。由調(diào)度表可知各個消息的調(diào)度時間為：

相應(yīng)的：

圖5 消息的調(diào)度時刻

依次類推：

統(tǒng)計各個消息的調(diào)度時間如表2所示。

表2 調(diào)度時刻計算結(jié)果 μs

則各個消息的最小延遲時間為：

依次類推：

各個消息延遲時間如表3所示。

表3 消息延遲時間計算結(jié)果 μs

與前文結(jié)果相比，時間觸發(fā)服務(wù)策略明顯降低了承載關(guān)鍵緊急消息的高優(yōu)先級數(shù)據(jù)幀的延遲，理論計算結(jié)果表明時間觸發(fā)調(diào)度算法對網(wǎng)絡(luò)實時性確實有一定的改善。

6 光纖通道調(diào)度算法仿真及分析

根據(jù)第4章、第5章對光纖通道中的典型調(diào)度算法進行的建模分析，本章借助OPNET10.0仿真工具，根據(jù)圖4交換式網(wǎng)絡(luò)結(jié)構(gòu)，對時間觸發(fā)終端節(jié)點和交換機進行建模，交換機物理鏈路速率設(shè)置為1 Gb/s，每個端口設(shè)置最大允許突發(fā)數(shù)據(jù)長度為10倍數(shù)據(jù)幀長，交換機提供FCFS和時間觸發(fā)兩種服務(wù)策略，仿真分析兩種服務(wù)策略下?lián)碛邢嗤W(wǎng)絡(luò)流量類型的消息延遲與理論計算的差距，消息配置信息采用表1所設(shè)置類型。

（1）在時間觸發(fā)服務(wù)策略下消息延遲分析

由表4可以看出，采用時間觸發(fā)調(diào)度策略理論計算值和實際仿真結(jié)果非常接近，表示具有很好的時間確定性。

表4 時間觸發(fā)策略下消息端到端延遲 μs

（2）在FCFS服務(wù)策略下消息延遲分析

由表5可以看出，在FCFS服務(wù)策略下基于網(wǎng)絡(luò)演算的理論計算值和仿真結(jié)果具有較大的差距，時間確定性較差。

表5 FCFS策略下消息端到端延遲 μs

7 結(jié)束語

本文根據(jù)FC-AE-ASM以及時間觸發(fā)協(xié)議規(guī)范，針對現(xiàn)有調(diào)度算法缺少時間確定性問題，設(shè)計實現(xiàn)了一種時間觸發(fā)調(diào)度算法，從理論和仿真兩方面對算法性能進行了分析，仿真結(jié)果表明時間觸發(fā)調(diào)度算法擁有很好的時間確定性，對航電系統(tǒng)分析具有很好的指導(dǎo)意義。