一種基于TTE調(diào)度表的資源分配算法

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 TTShFRR的性能

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

首先將漏桶限定作用到端系統(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)度器的最大信元時(shí)延為

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

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

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

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

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

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

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

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

3.2 TTShFRR的公平性

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

4 結(jié)論

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