一種實時保證的交換式互連緩衝容量確定方法
2023-05-09 05:12:11
專利名稱：一種實時保證的交換式互連緩衝容量確定方法
技術領域：
本發明針對航空航天安全關鍵任務，對平臺電子系統綜合化互連技術中交換機緩 衝容量，提出一種保證消息傳輸延時的緩衝容量確定方法，屬於航空航天電子綜合化系統 互連技術領域。
背景技術：
隨著航空航天任務需求(高性能處理、高接口帶寬、強實時性、高可靠性等需求) 的進一步提升，空天飛行器電子互連技術及體系架構經歷了從分離式、聯合式向綜合式發 展過程。航空電子全雙工交換式乙太網(Avionics Full Duplex Switched Ethernet, AFDX)，作為綜合化系統的支撐互連技術之一，具有更高的可靠性、抗惡劣環境適應性和確 定的實時性，成為美國國家航空航天局NASA構建未來空間飛行器綜合化體系架構互連候 選，並已應用於先進大型客機項目(如空中巴士A380和B787)，成為構築新一代民機航空電 子系統的基礎。AFDX交換機是互連繫統的重要部件和關鍵因素。對於空天飛行器綜合化系 統中的安全關鍵任務通常要滿足強實時和高可靠性。如何在AFDX交換機中對緩衝容量進 行合理設置，使之不僅滿足消息調度的強實時要求，同時避免交換機入線、出線隊列緩衝區 消息溢出，從而提高系統的可靠性，具有重要意義。入線、出線隊列緩衝容量的分配與交換機分組調度方法密切相關。AFDX協議只給 出了入線、出線隊列緩衝容量的預設值，並沒有給出強實時保證下的緩衝容量的確定方法。目前為止，研究強實時條件下交換機緩衝的公開資料不多見。現有資料記載有針 對FDDI區域網和FC-AL環網建立了分析性模型，為確定消息實時傳輸和溢出的條件提供有 益借鑑，但針對的是共享介質型網絡，沒有涉及交換式網絡的研究。還有人提出基於隨機網 絡演算(Network Caculus)方法，開展AFDX網絡節點緩衝溢出的概率研究，但並沒有探究 強實時條件下交換機緩衝容量與消息參數的定量關係。
發明內容
本發明針對目前在強實時保證下AFDX交換機的緩衝容量確定技術欠缺的情況， 針對空天飛行器安全關鍵任務需求，提供一種實時保證的交換式互連緩衝容量確定方法， 從而滿足消息調度的強實時要求，同時避免交換機入線、出線隊列緩衝區消息溢出，提高系 統的可靠性。本發明提供一種實時保證的交換式互連緩衝容量確定方法，其中，所述方法包括 步驟步驟一、建立消息模型和交換機隊列等效結構模型；所建立的消息模型，包括實時消息流Si =Si = (Ci5Pi)；實時消息集合Ms =Ms = (S1, S2,…，SJ ；其中,Ci表示實時消息流最大長度，Pi表示實時消息流產生周期，也表示實時消 息流最大允許延遲時間。所述的建立的交換機隊列等效結構模型為將具有m個隊列的交換機轉化為一個具有η個隊列的等效交換機，其中轉換後的每個隊列中只有一個實時消息流，其中，m、η為 大於0的整數。步驟二、建立分組調度和緩衝模型；所建立的分組調度和緩衝模型具體包括如下1)設定交換機工作最差情況η條入線隊列同時競爭一條出線隊列；2)設置調度輪轉的最大長度Lmk 指交換機在分組調度中每次輪轉所允許的最大 時隙數，分組調度輪轉周期的上限；每個入線隊列Qi按照調度時間軸被分配Lme中的Wi個 時隙用於調度本隊列的實時消息流，當Qi待調度的實時消息量小於Wi個時隙應發生的消息 量，則在Qi發送完待調度的實時消息後，Qdf發送非實時消息直到Wi中剩餘調度時間結束， 然後，下一隊列Qi+1將被調度；其中，Wi為輪轉權值；3)進入交換機的消息幀根據時隙大小重新打包；步驟三、建立消息實時調度條件，並確定關鍵參數；所述消息實時調度條件包括時限約束條件和輪轉權值約束條件；時限約束條件 為當t = Pi時，Xi(t)≥Ci,其中，
表示入線隊列Qi被調度並發送實時消息的最小時開銷時間量；間量；輪轉權值Wi約束條件
其中，θ代表調度程序進行連接輪轉的切換所述確定的關鍵參數x州為
其中，Hli = [t/Lffi]，[ ·]表示對實數取整，Hli彡1，t代表時間。步驟四、給出實時確保的分組調度方法，其分組調度方法採用下式表示
,其中，Hii = [PiZlJ，Hii > 1 ； Ci-(Pi-m,-Lm)步驟五、確定分組調度方法與輸入、輸出緩衝容量的關係模型；其中，入線隊列可達緩衝容量的關係模型
能被q整除其中，代表入線隊列可達緩衝容量，代表實時消息流Si的入線隊列可達緩衝餘度；任意時刻，在步驟四所述的分組調度方法下，實時消息流Si緩衝在入線隊列Qi中
的關係模型
其中，_ ρω代表輸入緩衝區中的最大消息數。其中，出線隊列可達緩衝容量的關係模型N:r=ISfIc^, SS,其中，c代表出線隊列可達緩衝容量，
表實時消息流Si的出線隊列可達緩衝餘度；任意時刻，在步驟四所述的分組調度方法下，實時消息流Si緩衝在出線隊列中的
關係模型=[Pi+L^+T]+i，其中，代表輸出緩衝區中含實時消息流Si的最大
八 「max
消息數；τ代表交換機出線隊列響應時間。步驟六、確定實時確保的輸入緩衝容量和輸出緩衝容量；輸入緩衝容量為WpHCi，其中，表示入線隊列Qi的緩衝容量，輸出緩衝容量為，其中表示出線隊列的緩衝容量。
1=1Si本發明一種用於實時保證的交換式互連緩衝容量確定方法，其優點與積極效果在 於(1)針對空天飛行器安全關鍵任務需求，能確保實時消息流的強實時要求；(2)確保實 時消息流不發生溢出；(3)合理設置緩衝容量，降低容量開銷；(4)方法簡單易行，可重複性 強。
圖1是本發明交換機互連緩衝容量確定方法的整體步驟流程圖；圖2是本發明步驟一中建立交換機隊列等效結構模型的示意圖；圖3a是本發明步驟二中建立的分組調度模型和緩衝模型的示意圖；圖3b是圖3a中調度方法的調度時間軸的示意圖；圖4是本發明步驟三中AFDX交換機消息調度規則下的關鍵參數Xi (t)的示意圖；圖5是本發明出線隊列的緩衝容量與所有入線隊列實時消息流關係模型的示意 圖；圖6是實施例二中實時消息流在不同入線隊列緩衝容量下的消息溢出率的示意 圖。
具體實施例方式下面將結合附圖和實施例對本發明作進一步的詳細說明。本發明依據AFDX協議的交換機消息調度原則，指明了在交換機中運用負載匹配 進行分組調度所應確定的基本參數，並以此為基礎研究了分組調度與入線/出線隊列緩衝 容量之間的關係，給出了強實時條件下AFDX交換機中的入線、出線隊列緩衝容量的確定方法。本發明提供一種實時保證的交換式互連緩衝容量確定方法，如圖1所示，具體包 括步驟如下步驟一、建立消息模型和交換機隊列等效結構模型。首先建立消息模型。採用實時通信中的周期性任務模型假設有η個實時消息流 要在交換機中調度，分別用S1, S2,…，Si,…，Sn表示，由這些實時消息流組成一個實時消息集合Ms Ms = (S1, S2,…，Si,…，SJ(1)其中，η為大於0的整數，i = 1，2，...，n。對於實時消息流Si和交換機，有如下設定1)實時消息流產生周期Pi 表示第i個實時消息流Si的消息產生周期，對於非周 期性消息，則表示消息產生最小時間間隔；實時消息流產生周期Pi的最小值用Pmin表示；2)實時消息流最大長度Ci 表示第i個實時消息流Si的傳輸時間，包括網絡協議 規定的分隔符、幀頭、信息域和校驗域等幀的全部內容；3)實時消息流最大允許延遲時間，等於實時消息流產生周期Pi ；4)實時消息流與交換機參數均以時隙為基本時間單位進行歸一化，時隙歸一化結 果為1。每個實時消息流由一個二維數組表示Si = (CijPi)(2)然後建立交換機隊列等效結構模型。建立隊列等效結構模型，可以將m個交換機 隊列轉化為一個η個等效交換機隊列，其中轉換後的每個等效交換機隊列中只有一個實時 消息流。為後續步驟的實現奠定基礎。該隊列等效結構模型的方法如圖2所示，當隊列j中的實時消息流為k個時，以 對，匁，…，匁表示，可以將隊列j分為k個隊列，以隊列j+Ι，隊列j+2，…，隊列j+k表示，每 個隊列分別對應一個實時消息流，這些隊列之間的調度切換時間為零，其中，j、k均為大於 0的整數。這樣，通過建立交換機隊列等效結構模型，將單個隊列實時消息流的數量簡化到 一個，下面的步驟是在隊列等效結構模型基礎上進行的。步驟二、建立分組調度和緩衝模型。AFDX採用緩存到緩存的流量控制方法，AFDX交換機的隊列分為兩類入線隊列和 出線隊列。如圖3a所示，建立AFDX交換機的分組調度和緩衝模型，該模型具體為1)設定交換機工作最差情況n條入線隊列同時競爭一條出線隊列；2)設置調度輪轉的最大長度Lmk 指交換機在分組調度中每次輪轉所允許的最大 時隙數，即分組調度輪轉周期的上限。如圖3a所示，每個入線隊列Qi按照調度時間軸被分 配Lmk的一部分用於調度本隊列的實時消息流，所被分配的時隙個數為Wi, Wi為稱為輪轉權 值。當Qi被調度時，將允許調度並向出線隊列發送Wi時間量的實時消息，若待調度的實時 消息量小於Wi個時隙應發生的消息量，則在Qi發送完待調度的實時消息後，Q1將發送非實 時消息直到Wi剩餘調度時間結束。然後，下一隊列Qi+1將被調度。具體輪轉權值Wi在步驟 四中確定。3)進入交換機的消息幀根據時隙大小重新打包。4)為提供高可靠、強實時的數據交互，必須在交換機的輸入/輸出隊列中選擇合 適的緩衝容量。所謂合適，容量小了會溢出，容量過大會浪費資源，合適值要在剛好不溢出 時留有20 30%餘量。本發明的緩衝容量確定方法目的就是提供了合適的輸入緩衝容量 和輸出緩衝容量。如圖3a所示，入線消息流S1, S2,…，Si,…，Sn進入AFDX交換機以後，分別存入 到入線對列Q1,Q2, -,Qi,…，Qn的緩衝區，各隊列經過調度輸出到出線隊列緩衝區。各入線隊列的調度是依據上述分組調度和緩衝模型裡調度方法被調度的。步驟三、建立消息實時調度條件，並確定關鍵參數。對於η個實時消息流構成的集合Ms,交換機應為每個入線隊列中的實時消息流提 供調度。交換機中的調度方法為每個入線隊列i分配一個權值Wi, i = 1，…，n，如圖3b調 度方法中的調度時間軸所示。在強實時條件下，分組調度方法為每個入線隊列所分配的權 值Wi應同時保證消息傳輸的時限約束條件和輪轉權值約束條件.1)時限約束條件對任意時間間隔t，用XJt)表示入線隊列Qi被調度並發送實時消息的最小時間 量，消息集合Ms中每個消息在最大允許延遲時間內，應有足夠發送該消息的時間，因此對於 任意實時消息流Si,當t = Pi時，應有Xi (t) = Xi (Pi) ^ Cii = 1,2, ...，n(3) 2)輪轉權值Wi的約束條件
YW^Lmr-O(4)
i=l其中，θ為調度進行連接輪轉的切換開銷時間量。若分組調度方法同時滿足上述時限約束條件和輪轉權值約束條件，，則該分組調 度方法可實現實時消息流的實時傳輸，此時進一步確定關鍵參數，即消息調度的最小時間 量Xi⑴。在交換機工作最差情況下，確定入線隊列可被調度發送的實時消息量非常重要。 入線隊列Qi被調度並發送實時消息的最小時間量Xi(t)，對於實時消息是否超時具有重要影響。依據AFDX交換機規則要求，結合Xi (t)的定義，入線隊列Qi被調度並發送消息的 最小時間量是通過「最差情形」來確定的。「最差情形」具備以下條件①在、時刻之前，交 換機中入線隊列Qi無高優先級消息(對應於實時消息)待發送，而有足夠的低優先級消息 (對應於非實時消息)待發送；②在、時刻，除入線隊列Qi的每個隊列均有足夠的消息(高 優先級或低優先級)待發送；③在、時刻，入線隊列Qi由於無高優先級的消息，低優先級的 消息得到調度；恰在此時，高優先級的實時消息流Si到達。因此，可得Xi (t)的表達式
0,0 < < LURXi(J) = IMR(5)
- Wi + min{%, t - IniLm }，t>Lm其中，參數Hii = [t/LME], [ ·]表示對實數取整，Hii彡1 ；t代表時間。圖4給出了 AFDX交換機消息調度規則下的關鍵參數Xi (t)的示意圖，其中，橫軸 為時間軸，陰影部分為入線隊列Qi被調度並發送實時消息量。其中，由於非實時消息流的 存在，使得在第一個Lmk內，Xi (t)的值為零；從第2個Lmk周期時間開始，Xi (t)大於零。步驟四、給出確保實時的分組調度方法；由步驟三得到的Xi (t)，消息產生周期Pi內入線隊列Qi可被調度並發送消息的最 小時間量為Xi(Pi),而待發送的實時消息量所需時間為Ci,從負載匹配的角度出發，令消息 發送量和消息量相等，即Xi (Pi) = Ci,則可得到一種負載匹配的分組調度方法。AFDX支持雙優先級，由式(5)，可得其負載匹配的分組調度方法採用下式進行
Ci ,0<Pt— Lmr <Lmr Wi=IciImi ，Pi-TnrLwi^Wi (6)
C'l，·。，P^m,-^wi m, -1式(6)中，參數Hii = [Pi/!腿]叫 > 1
步驟五、確定步驟四的分組調度方法下，輸入、輸出緩衝容量的關係模型； 1)確定輸入緩衝容量的關係模型；
實時消息流Si的入線隊列可達緩衝餘度定義為入線隊列可達緩衝容量與消息長 度的比值(通常取整數)，並記為MJrt
N_ = {能被 整除
~|[g;j '/C,] + l, gf 不能被 C,.整除1 ]其中，表示入線隊列可達緩衝容量，是指在入線隊列Qi的緩衝容量為實 時消息流Si不被覆蓋或溢出時的緩衝容量。由限制條件式(3)和式(4)，與如式(6)所示的分組調度方法，能得到Xi(Gc-I) Pi+Pi+U彡kCi;因此可知，入線隊列Qi中實時消息流Si從第1個消息到達開始至第k個 消息到達後的P^Lme時間段內最少可被調度並發送的消息量為kCi，k為大於ο的整數，因 此在如式(6)所示的分組調度方法下，入線隊列Qi中實時消息流Si在其到達後的PJLmk時 間內得到調度並發送。對於實時消息流Si每？,周期會產生一個新消息，所以在P^Lmk的時間內入線隊列
ρ +1,
Qi中產生並緩衝的消息數不超過[^"^] + 1。因此，任意時刻，在如式(6)所示的分組調度 方法下，輸入緩衝容量的關係模型，也就是實時消息流Si緩衝在入線隊列Qi中的最大消息 數記為況二 』滿足況二二 ^mW。當實時消息流Si緩衝在入線隊列Qi中緩衝餘度不小於其最大消息數時，即 Ci 2 M"=，必不會溢出，則任意時刻，在如式(6)所示的分組調度方法下，實時消息流
IiOI ,IIiaX *
Si緩衝在入線隊列Qi中的可達緩衝餘度,滿足W >[1 + ^-] + 1 ο其中，關於式子XAk-DPi+Pi+、)SkCi的說明如下首先，根據式(5)，當t = Pi
0,0<P < Lmr
時，存在柳『,+min{^_^}，其中，w,=@。然後，進-步翻
XjkPi+L腿)彡IOCi (Pi),其中，k為自然數。最後，由限制條件(3)和分組調度方法(6)，可知， Xi(Pi) = Ci,則進一步得到 Xi(Gc-I)PJP^L服)^kCi02)確定出線隊列可達緩衝容量的關係模型；
9
由交換機分組調度和緩衝模型，η個入線隊列競爭一個出線隊列，因此出線隊列的 緩衝容量應與所有入線隊列實時消息流相關，如圖5所示，其中，調度方法對應於圖3a的調 度方法，均為步驟四所得到的分組調度方法；出線隊列緩衝區對應於圖3a，是交換機中一 部分A Wn對應於圖3b Cn對應於S1 Sn的消息量C1 Cn ；入線隊列Q1中實時消 息流S1所對應的出線隊列緩衝區部分表示由交換機調度實時消息流S1時緩衝於出線隊列 緩衝區中容量；入線隊列Qn中實時消息流Sn所對應的出線隊列緩衝區部分表示由交換機 調度實時消息流Sn時緩衝於出線隊列緩衝區中容量。由入線隊列Qi中實時消息流Si所對應的出線隊列的緩衝容量記為，實時消 息流Si不被覆蓋或溢出時的緩衝容量定義為出線隊列可達緩衝容量，記為容；7"。實時消息流Si的出線隊列可達緩衝餘度定義為出線隊列可達緩衝容量與消息長 度的比值，通常取整數，並記為
,即 由上可知，在如式(6)所示的分組調度方法下，實時消息流Si到達出線隊列後，將 在PJLme+τ時間得到發送，則得到輸出緩衝容量的關係模型，即對於實時消息流Si出線隊
列緩衝區中含Si的最大消息數γ。，滿足
,其中，τ代表交換機出
線隊列響應時間。進一步，消息集Ms應為所有實時消息流Si出線隊列緩衝容量部分之和，所以在 如式(6)所示的分組調度方法下，消息集禮在出線隊列緩衝區的緩衝容量G°utput，滿足
Goutput》ZCCM，出線隊列在任意時刻都不發生溢出。 /=1步驟六、確定實時確保的輸入緩衝容量和輸出緩衝容量。1)輸入緩衝容量確定；在如式(6)所示的分組調度方法下，緩衝容量滿足gf"""' =2· 時，入線隊列Qi中 的實時消息流Si在任意時刻都不發生溢出。由步驟五中可知，+ + 1，根據式(5)，當
，無意
義！所以有Pi >Lmk，則可得
這樣就確定了輸入緩衝容量，
並保證消息不溢出且實時傳輸要求。2)輸出緩衝容量確定；在如式(6)所示的分組調度方法下，出線隊列緩衝容量滿^ ,時，出線
/=1
隊列中的所有實時消息流Si在任意時刻都不發生溢出。根據步驟五中出線隊列可達緩衝容量的關係
),由限制條件可知
,這裡取τ =Pi,可得
。這樣就確定了輸出緩衝容量，
並保證消息不溢出且實時傳輸要求。通過步驟六，就分別確定出了 AFDX交換機入線隊列輸入緩衝容量和出線隊列輸 出緩衝容量，所確定出的緩衝容量能確保所有實時消息流不發生溢出，並在其消息最大允 許延遲內得到調度。實施例一實時消息集合如表1所示，實時消息流產生周期的最小值Pmin = 0. 12ms ；設定Lme = 0. 06ms ；數據傳輸率為r = lOOMBytes/s。AFDX交換機採用式(6)的負 載匹配的調度方法，由表1中數據可知該消息集可實現實時調度。表1實施例一的消息集及其分組調度方法 以消息S4為例說明，其在最差情形下的傳輸如表2所示。對於實時消息流S4，待 發送的實時消息量所需時間C4 = L4Zr = 0. 01ms，其中L4為消息字長度。最差情形下實時消息流S4傳輸時序如表2所示，實時消息流S4對應的發送的時間 量為Ts，Ta表示發送非實時消息的時間量。在t = Oms時刻，入線隊列Q4中，實時消息流S4 未到達，會發送已到達的非實時消息，此時發送非實時消息的時間量Ta = W4 = 0.01ms ；t = 0. Olms時刻，下一隊列Q5將被調度，然後依次按照Q6> Q7>…、Q10、Q」 Q2、Q3 ；當t = 0. 06ms 時刻，輪轉一周，入線隊列Q4第二次被調度，而此時，會發送已經存在實時消息流S4,發送實 時消息的時間量Ts = W4 = 0. Olms = C4,即在0. 07 ( = 0. 06+0. 01)ms時刻就能發送完實時 消息流S4。因0.07 <0.12，所有滿足實時調度傳輸條件。其它實時消息流的傳輸與實時 消息流S4相同，所以針對該實施例一中的消息集可實現實時調度。表2最差情形下消息流S4傳輸時序
實施例二建立的消息模型和交換機隊列等效結構模型消息集禮=(S1, S2, S2, S4}，其中S1 =(C1 = 30，P1 = 150)，S2 = (C2 = 30，P2 = 250)，S3 = (C3 = 40，P3 = 300)禾Π S4 = (C4 =60，P4 = 300)，如表3所示。C^Pi與Wi的單位都為時間單位。表3實施例二的消息集及調度方法 如表3所示，這裡入線埠 η = 4，每個入線埠只有一個實時消息流，設置Lmk = 100(時間單位)。建立消息實時調度條件；1)時限約束條件消息集合Ms中每個消息Si在最大允許延遲時間Pi內，應有足夠發送該消息的時 間，因此應有 2)輪轉權值Wi的約束條件沒；
/=1 然後根據式(5)確定關鍵參數Xi (t)。由Xi (Pi) = Ci,則可得到一種負載匹配的分組調度方法。根據式(6)，該實施例中 負載匹配的分組調度方法為=W1 = 30，W2 = 15，W3 = 20和W4 = 30。如表3所示，可知，該 消息集可實現實時調度。確定入線隊列可達緩衝容量的關係模型在如式(6)所示的分組調度方法下，任意時亥IJ，消息集中所 有實時消息流Si緩衝在入線隊列Qi中的可達緩衝餘度N:分別為確定出線隊列可達緩衝容量的關係模型在如式(6)所示的分組調度方法下，任意時 刻，出線隊列緩衝區中含Si的最大消息數N=分另Ij為
^r=[A±^±I] + 1 = [150 + 100 + 150] + 1 = 3>+ 1 =
和 ^r 二 [m±^±M]+1=3。進一步可得，消息集M(S1;S2，... ,Sn)在任意時刻都不發生溢出條件下的出線隊列
緩衝區的緩衝容量為V聲> YjKZiCi。
/=1最後確定實時確保的輸入緩衝容量和輸出緩衝容量1)輸入緩衝容量確定；保證消息不溢出且實時傳輸要求條件下，消息集中所 有實時消息流Si緩衝在入線隊列Qi中的輸入緩衝容量分別為
gr, =([l + m] + i).ci=2-Cl=60 , g產=2.C2=60,=I-C3=SO 和
g，'=2.C4 =120。2)輸出緩衝容量確定；保證消息不溢出且實時傳輸要求條件下，出線隊列緩衝容量為
Goutput > YjN^Ci = Y^Ci = 480。 (=1 /=1通過編寫仿真程序，仿真時間均為5分鐘，傳輸的消息總數如表4中所示，單位為 字，對實施例二進行了仿真。仿真結果驗證了本發明的方法的準確性。隨著入線隊列緩衝容量的增加，消息集Ms中的入線隊列緩衝區數據包溢出情況如 圖6所示。圖6中消息溢出率為入線隊列溢出消息數與入線隊列消息總數之比，其中，可以 看出當入線隊列緩衝容量不小於2 · Ci時，所有入線隊列緩衝區不會發生溢出入線對列緩 衝區。同樣，隨著出線隊列緩衝容量的增加，消息集Ms中在的出線隊列緩衝區數據包溢 出情況如表4所示。從仿真運算結果可以看出，在強實時條件下，隨入線、出線隊列緩衝容
量的增大，相應緩衝中數據包溢出現象明顯減少。當出線隊列緩衝容量不小於時，出
/=1
線隊列緩衝區不會發生溢出。仿真實驗結果與理論分析所得到的結論相吻合，驗證了理論 分析結果的正確性。表4不同出線隊列緩衝容量下消息溢出率比較
13出線隊列緩衝容量出線隊列緩衝容量參數η Tcl i=lYp-C1 1=1/=1/=1 .I^ci i=l仿真時鐘5min5min5min5min5min傳輸消息總數51988975198879519890251989115198875出線隊列消息溢出數355190O0消息溢出率6.8*10e-53.7*10e-6000
權利要求
一種實時保證的交換式互連緩衝容量確定方法，其特徵在於，該交換式互連緩衝容量確定方法具體包括如下步驟步驟一、建立消息模型和交換機隊列等效結構模型；所建立的消息模型，包括實時消息流SiSi＝(Ci，Pi)；實時消息集合MSMS＝{S1，S2，…，Sn}；其中，Ci表示實時消息流最大長度，Pi表示實時消息流產生周期，i＝1，2，…，n，n為大於0的整數；所述的交換機隊列等效結構模型為將m個交換機隊列轉化為一個n個等效交換機隊列，其中轉換後的每個隊列中只有一個實時消息流，其中，m、n為大於0的整數；步驟二、建立分組調度和緩衝模型；所建立的分組調度和緩衝模型具體包括1)設定交換機工作最差情況n條入線隊列同時競爭一條出線隊列；2)設置調度輪轉的最大長度LMR指交換機在分組調度中每次輪轉所允許的最大時隙數，分組調度輪轉周期的上限；每個入線隊列Qi按照調度時間軸被分配LMR中Wi個時隙用於調度本隊列的實時消息流，當Qi待調度的實時消息量小於Wi個時隙應發生的消息量，則在Qi發送完待調度的實時消息後，Q1將發送非實時消息直到Wi中剩餘調度時間結束，然後，下一隊列Qi+1將被調度；其中，Wi為輪轉權值；3)進入交換機的消息幀根據時隙大小重新打包；步驟三、建立消息實時調度條件，並確定關鍵參數；所述消息實時調度條件包括時限約束條件和輪轉權值約束條件；對於實時消息流Si，時限約束條件為當t＝Pi時，Xi(t)≥Ci，其中，Xi(t)表示入線隊列Qi被調度並發送實時消息的最小時間量；輪轉權值Wi約束條件其中，θ代表調度程序進行連接輪轉的切換開銷時間量；所述確定的關鍵參數Xi(t)為其中，mi＝[t/LMR]，mi≥1，t代表時間；步驟四、給出實時確保的分組調度方法，其分組調度方法採用下式表示其中，mi＝[Pi/LMR]，mi＞1；步驟五、確定步驟四的分組調度方法下，輸入、輸出緩衝容量的關係模型；任意時刻，在步驟四所述的分組調度方法下，確定的實時消息流Si緩衝在入線隊列Qi中的關係模型為其中，代表輸入緩衝區中的最大消息數；任意時刻，在步驟四所述的分組調度方法下，確定的實時消息流Si緩衝在出線隊列中的關係模型為其中，代表輸出緩衝區中含實時消息流Si的最大消息數；τ代表交換機出線隊列響應時間；步驟六、確定實時確保的輸入緩衝容量和輸出緩衝容量；在輸入緩衝容量為其中，表示入線隊列Qi的緩衝容量，輸出緩衝容量為其中表示出線隊列的緩衝容量。FSA00000260470000011.tif,FSA00000260470000012.tif,FSA00000260470000021.tif,FSA00000260470000022.tif,FSA00000260470000023.tif,FSA00000260470000024.tif,FSA00000260470000025.tif,FSA00000260470000026.tif,FSA00000260470000027.tif,FSA00000260470000028.tif,FSA00000260470000029.tif
2.根據權利要求1所述的一種實時保證的交換式互連緩衝容量確定方法，其特徵在 於，步驟四所述的分組調度方法，具體是當t = Pi時，根據消息發送量和實時消息量相等 的式子:X「t) =Xi(Pi) = Ci得到的，其中，Xi (Pi)為消息產生周期Pi內入線隊列Qi被調度 並發送消息的最小時間量。
3.根據權利要求1所述的一種實時保證的交換式互連緩衝容量確定方法，其特徵在 於，步驟五中所述的實時消息流Si緩衝在入線隊列Qi中的關係模型，由步驟三的時限約束 條件和輪轉權值約束條件，與步驟四的分組調度方法，得到式子AiGk-DPi+Pi+L。^kCi, 則入線隊列Qi中的實時消息流Si在該實時消息流Si到達後的PJLme時間內得到調度並發 送；其中，k為大於0的整數；則任意時刻，在步驟四的分組調度方法下，實時消息流Si緩衝在入線隊列Qi中的可達緩衝餘度^Trf >[1 + ^] + 1，其中，#_ ,表示實時消息流S1緩衝在入線隊列Qi中可達緩衝餘度，Ci=I^f/C/]』 sTmmcM^ 代表入線隊列可達緩衝容量。 Itc /c-]+l' C"不能被 整除 Vr
4.根據權利要求1所述的一種實時保證的交換式互連緩衝容量確定方法，其特徵在 於，步驟五中所述的實時消息流Si緩衝在出線隊列中的關係模型，在步驟四的分組調度方 法下，實時消息流Si到達出線隊列後，將在P^Lmk+ τ時間得到發送，消息集Ms在出線隊列緩衝區的緩衝容量要滿足,時，出線隊列在任意時刻都不發生溢出，其中，/=1Goutput為消息集Ms在出線隊列緩衝區的緩衝容量，η為入線隊列的個數。
全文摘要
本發明一種實時保證的交換式互連緩衝容量確定方法，針對目前在強實時保證下AFDX交換機的緩衝容量確定技術欠缺的情況，通過建立消息模型和交換機隊列等效結構模型、分組調度和緩衝模型、消息實時調度條件，並確定關鍵參數，依據AFDX協議的交換機消息調度原則，指明了在交換機中運用負載匹配進行分組調度所應確定的基本參數，並以此為基礎確定了分組調度與入線、出線隊列緩衝容量之間的關係，給出了強實時條件下AFDX交換機中的入線、出線隊列緩衝容量的確定方法。本發明的方法能確保實時消息流的強實時要求，確保實時消息流不發生溢出，同時通過合理設置緩衝容量，降低容量開銷，該方法簡單易行，可重複性強。
文檔編號H04L12/58GK101924713SQ20101027474
公開日2010年12月22日 申請日期2010年9月7日 優先權日2010年9月7日
發明者史燕華, 周強, 曲振亮, 辛惠娟 申請人:北京航空航天大學