梁 棟，趙 剛，李世興，崔迎春，王曉勇

（北方自動控制技術研究所，太原 030006）

0 引言

近年來航空電子體系結構逐漸興起，時間觸發(fā)（Time-Triggered）通信機制在它的影響下也漸漸開始被人們所關注。TT體系架構主要是在保證全局時間同步的基礎上，通過已經(jīng)設定好的資源分配計劃，使得整個網(wǎng)絡能夠有序高效地運行，并提高對資源的利用率。時間觸發(fā)以太網(wǎng)（Time-Triggered Ethernet）就是在上述的架構下提出的，通過用時間觸發(fā)代替?zhèn)鹘y(tǒng)網(wǎng)絡的事件觸發(fā)，使整個網(wǎng)絡時鐘同步的情況下，各種信息流的傳輸具備更高的實時性。全雙工交換式以太網(wǎng)（Avionics Full-Duplex Switched Ethernet，AFDX）在機載信息量增大的情況下暴露了時延抖動大，同步精度低，確定性不夠強，帶寬利用率低等問題，不能滿足DIMA對機載網(wǎng)絡的需求[1]。

TTE網(wǎng)絡為了滿足不同實時性和關鍵性數(shù)據(jù)流傳輸?shù)男枨?，提出?種不同的消息類型：時間觸發(fā)（Time-Triggered，TT）消息，速率受限（Rate-Constrained，RC）消息和“盡力傳”（Best-Efforts）消息[2]。TT消息主要傳輸一些對實時性要求很高的重要信息，傳輸?shù)膬?yōu)先級最高。RC消息主要傳輸一些對實時性要求較高的網(wǎng)絡信息，優(yōu)先級低于TT消息。BE消息主要是傳輸一些對實時性沒有太高要求的網(wǎng)絡信息，優(yōu)先級在這三者中的地位最低。

TT消息在網(wǎng)絡上根據(jù)原先已經(jīng)規(guī)定的時間進行傳輸，但是如果調(diào)度表資源分配不當，各端系統(tǒng)按預先定義時刻發(fā)送的TT消息可能會發(fā)生沖突，從而導致消息的丟失。本文主要研究了基于調(diào)度表的資源分配算法，使交換機能對各個端系統(tǒng)發(fā)送的TT消息進行合理的收發(fā)。

1 TTE調(diào)度表資源分配策略

在TTE網(wǎng)絡中，常用的調(diào)度方式是在各發(fā)送端預先離線設計好任務調(diào)度表，然后根據(jù)調(diào)度表進行消息的發(fā)送。調(diào)度表中包含一個矩陣周期，由若干個基本周期組成[3-4]。如圖1所示，每個基本周期又可以分為兩段，TT幀在基本周期前一段時間內(nèi)發(fā)送，RC幀與BE幀在TT幀后面的一段時間內(nèi)發(fā)送。為了不影響下一周期TT幀的發(fā)送，在每個基本周期末尾都會預留一定長度的時間作為保護間隔[5]。

在保證了整個網(wǎng)絡時鐘精確同步的前提下，通過預先設計好的任務調(diào)度表，使交換機在接收各個端系統(tǒng)發(fā)送的TT流量過程中避免了消息的沖突，減少了數(shù)據(jù)的丟失。本文不考慮時鐘漂移對信息傳輸?shù)挠绊?，假設系統(tǒng)中設備在每個基本周期開始時全局時鐘都是同步的。

圖1 基本周期TT段資源分配表

將時間分成若干個基本周期，將每個基本周期中專門接收TT任務的時間段分成有限個時間片，每一個時間片接收一個連接端系統(tǒng)的TT流。在一個基本周期內(nèi)，交換機要從調(diào)度表的表頭執(zhí)行到表尾。當一個新的基本周期開始后，又會重復上面的循環(huán)。假如輪到某一端系統(tǒng)不發(fā)送TT消息，則相應的時間片為空。上面所述的這種方法就是基于調(diào)度表的輪循算法，各個端系統(tǒng)合理分配到調(diào)度表中的帶寬，既可以保證各個端系統(tǒng)的預約帶寬和時延，又可以提高資源的利用率。為了能夠實現(xiàn)帶寬的合理分配，提高資源利用率，本文提出基于時間觸發(fā)的公平輪循調(diào)度算法。

2 TTE調(diào)度表的資源分配算法

2.1 基于時間觸發(fā)的公平輪循調(diào)度算法

設有W個端系統(tǒng)分享交換機的資源，它們各自有自己的預約帶寬要求ri（i=l，2，…，W），所有ri的和要小于等于TT段的帶寬。

假設每一個基本周期中TT段有L個時間槽，每個時間槽里發(fā)送一個連接的TT消息，如果某個時間槽內(nèi)沒有端系統(tǒng)發(fā)送的TT消息，則該時間槽為空。

從一個基本周期看，調(diào)度器從TT任務的表頭執(zhí)行到表尾，例如在圖1中，當時間槽的序號為0時，發(fā)送端系統(tǒng)1的TT信息，在時間槽為1時發(fā)送端系統(tǒng)4的TT信息，在時間槽n-1沒有TT信息發(fā)送，顯示為空，如此下去直到表尾。下一個基本周期又從TT消息的表頭開始重復執(zhí)行。但是如何對調(diào)度表資源進行合理分配，下文中提出一種基于時間觸發(fā)的公平輪循調(diào)度算法。

時間觸發(fā)公平輪循調(diào)度算法：設調(diào)度表中一個基本周期TT段的表長為L，基本周期的個數(shù)為a，將每個基本周期中的TT段都分成L個時間槽，總共分成aL個時間槽，其中每個時間槽的編號為0，1…L…aL-1，aL，端系統(tǒng)i的預約帶寬為ri=ni/aL（1≤ni≤aL，ni為整數(shù)，表示各個端系統(tǒng)預約交換機的時間槽的個數(shù)），在調(diào)度表中，用來表示分配給端系統(tǒng)i的第k（0≤k≤ni-1）個時間槽，定義的開始時標為

理想情況下，交換機應該在時間槽中相應的時標開始時刻接受TT數(shù)據(jù)，然后在時標結束的時刻將TT數(shù)據(jù)送出。TTFRR就是依據(jù)的時標大小，將調(diào)度表中的時間槽合理地逐個分配給每個端系統(tǒng)，當沒有TT消息時，顯示為空。

2.2 基于時間觸發(fā)的整形的公平輪循

基于時間觸發(fā)的整形的公平輪循（Time-Triggered Shaped Fair Round Robin，TTShFRR）主要是通過對結束時標和開始時標的綜合利用來實現(xiàn)資源的分配。假設。對調(diào)度表中的每一個時間槽T（0≤T≤aL-1）依次進行分配，首先從所有還沒有安排的中選出開始時標小于或等于T的組成集合Θ，再從Θ中選出結束時標最小的分配給相應的時間槽。如果有幾個的結束時標都最小，則從中任意選取一個。

3 TTShFRR的性能

3.1 TTShFRR調(diào)度器的延時性和整形性

首先將漏桶限定作用到端系統(tǒng)i的TT流量上，可用參數(shù)（Δi，ri）表示。公式中L為調(diào)度表的表長，ri=ni/aL是端系統(tǒng)事先約定好的帶寬，端系統(tǒng)i的突發(fā)度用Δi表示（單位是信元），則提出定理1。

定理1 端系統(tǒng)i經(jīng)過TTShFRR調(diào)度器的最大信元時延為

證明 在時間段 [k/ri，（1+Δi）/ri+1]（k 為整數(shù)）內(nèi)，端系統(tǒng)i發(fā)送的TT信息必定會被調(diào)度一次。那么在時間段[t，t+M/ri]（M≥1，M 為整數(shù)）內(nèi) TT 消息至少會被調(diào)度M-1次。假設[t1，t2）是端系統(tǒng)i的一個backlogged時間段（即，在t1之前各個端系統(tǒng)沒有消息傳輸，從t1時間開始一直到時刻t2，端系統(tǒng)i的隊列中一直有TT消息在等待調(diào)度），假設在backlogged時間段內(nèi)第k個到達的TT消息的到達時間為bk（k＞1），被交換機選中的時間為dk，那么[t1，bk]內(nèi)到達了k個TT消息段，由端系統(tǒng)i的TT流量的漏桶參數(shù)可得

從前面可以看出，[t1，t1+（k+1）×1/ri]內(nèi)至少被調(diào)度了k次，那么

加上處理的時延，可以得到式（6）。證明完畢。

定理2 端系統(tǒng)i經(jīng)過TTShRFF交換機輸出的TT流量可用參數(shù)為（2，ri）的漏桶限制。

證明 在TTShRFF調(diào)度器輸出流量后端系統(tǒng)i具備了下面幾個性質(zhì)：兩個信元之間的最小間隔為1個時間槽，3個信元之間的最小間隔為1/ri，4個信元之間的最小間隔為2/ri，以此類推，那么m個信元之間的最小間隔為（m-2）/ri。假設一個時間為t的時間段中有 m 個信元，那么 t≥（m-2）/ri→m≤ri×t+2，證明完畢。

定理3 端系統(tǒng)i在TTShFRR調(diào)度器中所占用的最大緩存為

證明 設[t3，t4]為端系統(tǒng)i從t3開始的某個backlogged時間段，Pi（t3，t4）表示在backlogged時間段內(nèi)端系統(tǒng)i到達的信元個數(shù)，Qi（t3，t4）表示交換機輸出的端系統(tǒng)i的信元個數(shù)。文獻[1]的定理1可知至少有個端系統(tǒng)i的信元在這個時間段內(nèi)被調(diào)度（表示不大于x的最大整數(shù)），將處理的時延作為考慮的對象，至少有（）個端系統(tǒng)i的信元被輸出。

顯然Pi（t3-t4）-Qi（t3-t4）＜2+ri+Δi。證明完畢。

3.2 TTShFRR的公平性

用最大歸一化服務量的差別作為公平性的指標。當兩個端系統(tǒng)i和j在[t1，t2]時間段內(nèi)處于backlogged狀態(tài)，則調(diào)度器在此時段內(nèi)輸出的端系統(tǒng)i的時間槽個數(shù)Si（t1，t2）和輸出的端系統(tǒng)j的時間槽個數(shù)Sj（t1，t2）滿足如下不等式

4 結論

本文主要研究了一種通過對開始時標和結束時標的綜合利用，來完成調(diào)度表資源分配的時間觸發(fā)公平輪循調(diào)度算法。TTShFRR提供的最大時延保證與連接數(shù)無關，同時還具有良好的公平性。具體實現(xiàn)以上算法時可以在系統(tǒng)中維護兩個調(diào)度表。在接收端系統(tǒng)發(fā)來的TT消息時，交換機設計出新的調(diào)度表，舊的調(diào)度表繼續(xù)供端系統(tǒng)使用；當交換機將新的調(diào)度表中的數(shù)據(jù)填好后，新的調(diào)度表和舊的調(diào)度表進行切換，然后再形成新的調(diào)度表。后面將對算法的時延性及公平性等性能進行研究，來證明算法滿足網(wǎng)絡對實時性的要求。