一種基于TTE調度表的資源分配算法

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

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

0 引言

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

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

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

1 TTE調度表資源分配策略

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

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

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

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

2 TTE調度表的資源分配算法

2.1 基于時間觸發的公平輪循調度算法

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

假設每一個基本周期中TT段有L個時間槽，每個時間槽里發送一個連接的TT消息，如果某個時間槽內沒有端系統發送的TT消息，則該時間槽為空。

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

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

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

2.2 基于時間觸發的整形的公平輪循

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

3 TTShFRR的性能

3.1 TTShFRR調度器的延時性和整形性

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

定理1 端系統i經過TTShFRR調度器的最大信元時延為

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

從前面可以看出，[t1，t1+（k+1）×1/ri]內至少被調度了k次，那么

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

定理2 端系統i經過TTShRFF交換機輸出的TT流量可用參數為（2，ri）的漏桶限制。

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

定理3 端系統i在TTShFRR調度器中所占用的最大緩存為

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

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

3.2 TTShFRR的公平性

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

4 結論

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