時間觸發光纖通道調度算法確定性分析

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

空軍工程大學 航空航天工程學院，西安 710038

1 引言

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

目前國內對光纖通道方面的研究主要集中在網絡傳輸的可靠性、通信系統拓撲結構以及上層協議的轉換方面。文獻[4-6]以網絡任務模型為基礎，建立了可靠性模型，同時針對光纖通道三種拓撲結構，推導出可靠性的表達式。文獻[7]對于FC在航空電子環境中的體系結構進行了論述。文獻[8]對光纖通道的特性進行了介紹，同時對典型的幾種網絡和總線進行了分析比較。針對網絡中消息的發送控制算法，文獻[9]提出了基于實時排隊論的調度算法，它借助延時率可以反映系統實時性。

基于以上分析，提出時間觸發調度算法，通過靜態規劃消息的調度表，通過全局時鐘來觸發每個消息的發送，使得網絡中所有消息都擁有較強的時間確定性。

2 數據結構模型設計

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

圖1 FC-AE-ASM消息格式

3 時間觸發調度算法設計

調度算法主要涉及對基本周期和矩陣周期的確定。對于矩陣周期，首先根據消息種類規劃初始系統矩陣MC0，然后對MC0進行優化，得到最終系統矩陣MC。

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

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

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

（3）生成待優化的初始矩陣MC0

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

（4）初始矩陣的優化

采用價值函數P對初始矩陣進行優化，由此得到最終的優化矩陣MC。

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

（2）確定一個基本周期（BC）可以傳輸的消息個數ν

根據總線的傳輸波特率B和周期消息比特數Num以及消息的傳輸時間Lt等參數，由式（3）可以得出一個基本周期中可以傳輸消息的最大個數；再者根據式（4）可以得出基本周期中傳輸的平均消息個數：

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

4 基于FCFS服務策略的調度算法及確定性分析

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

4.1 網絡演算理論

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

0,t內流入網絡的數據流的比特數。在借助網絡演算來計算網絡端到端的延時時，需要介紹數據流的到達曲線和服務曲線兩個重要概念。

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

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

引理1[14]假設在某個系統中，數據流的到達曲線為α，服務曲線為β，則進入系統的數據流在系統中的延遲上界滿足關系：

如圖2所示。

圖2 延遲上界計算

4.2 FC網絡在FCFS服務策略下確定性分析

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

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

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

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

200據幀兩種狀態，如果這時處理的數據幀是聚合流中最長的，就有：

根據式（8）和式（9）可以得到：

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

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

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

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

再根據引理1可得數據的延遲上界為：

由此得證。

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

5 時間觸發調度算法確定性分析

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

5.1 時間觸發光纖通道網絡時間確定性分析

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

圖3 時延各部分組成

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

5.2 時間觸發光纖通道網絡建模和確定性分析

鑒于時間觸發FC網絡和普通FC網絡結構相同，所以對時間觸發FC網絡的建模采取普通FC的交換式網絡結構。網絡結構如圖4所示。網絡中包括一個交換機和10個終端系統。各個終端節點的消息設置如表1所示，鏈路延遲取1 μs。

圖4 TTFC網絡結構

表1 消息配置信息

根據消息周期生成的各個消息的調度時刻如圖5所示。

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

相應的：

圖5 消息的調度時刻

依次類推：

統計各個消息的調度時間如表2所示。

表2 調度時刻計算結果 μs

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

依次類推：

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

表3 消息延遲時間計算結果 μs

與前文結果相比，時間觸發服務策略明顯降低了承載關鍵緊急消息的高優先級數據幀的延遲，理論計算結果表明時間觸發調度算法對網絡實時性確實有一定的改善。

6 光纖通道調度算法仿真及分析

根據第4章、第5章對光纖通道中的典型調度算法進行的建模分析，本章借助OPNET10.0仿真工具，根據圖4交換式網絡結構，對時間觸發終端節點和交換機進行建模，交換機物理鏈路速率設置為1 Gb/s，每個端口設置最大允許突發數據長度為10倍數據幀長，交換機提供FCFS和時間觸發兩種服務策略，仿真分析兩種服務策略下擁有相同網絡流量類型的消息延遲與理論計算的差距，消息配置信息采用表1所設置類型。

（1）在時間觸發服務策略下消息延遲分析

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

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

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

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

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

7 結束語

本文根據FC-AE-ASM以及時間觸發協議規范，針對現有調度算法缺少時間確定性問題，設計實現了一種時間觸發調度算法，從理論和仿真兩方面對算法性能進行了分析，仿真結果表明時間觸發調度算法擁有很好的時間確定性，對航電系統分析具有很好的指導意義。