PBFAA算法是一個基于平面的完全自適應最短蟲孔路由算法(Planar一BasedFullyAdaptiveAlgorithm，PBFAA)。

人們對直接網絡中采用蟲孔路由切換技術的自適應路由算法已進行了大量研究，提出了很多算法，但它們或存在自適應性受限，或存在代價較大，或存在靈活性不夠等缺點.在已有算法的基礎上，以低通信延遲、高網絡吞吐率和易VLSI實現為設計目標，提出了一個可擴展性好、自適應性強的基于平面的完全自適應路由算法PBFAA。

算法中將網絡分成兩個虛擬網VIN0和VI1I，VlN0中的虛通道按平面自適應路由策略路由消息，VIN1中的虛通道可完全自適應路由消息，由VIN0保證算法的無死鎖性.由于兩個網絡均具有自適應性，故與已有一些較好的算法如（channel）相比，該算法自適應性更強，更能充分有效地利用網絡資源，提高網絡吞吐率，且容錯能力更強一下面用n維mesh網絡介紹PBFAA算法:

1)算法為每條物理通道設置4條虛通道，用VC_{dimension，label，direction}來表示，其中dimension表示該虛通道沿哪一維傳遞消息；label表示虛通道的序號，取值0，1，2或3；direction可以為 (表示消息將沿正向傳遞)或-(表示消息將沿著逆向傳遞)。例如VC¨，一表示結點的第一維上的序號為1的負向虛通道。

2)將網絡劃分成兩個虛擬網：VIN0和VIN1。在VIN0中使用序號從0至2的虛通道；在VIN1中使用序號為3的虛通道。

3)在VIN0中，按平面自適應路由策略選擇趨于目的結點的虛通道路由消息；在VIN1中，按完全自適應最短路徑路由策略選擇趨于目的結點的虛通道路由消息。在兩虛擬網中按相應路由策略可被選擇的虛通道均稱為所需虛通道，空閑的所需虛通道稱為可用虛通道。

4)當一條消息的頭微片到達某一結點時，如該結點是目的結點則消息被接收，否則：

a)若有可用虛通道，則對可用虛通道按最大間距輸出虛通道選擇策略，對相應維虛通道提出申請Req；若沒有可用虛通道，則暫停提出申請，等待直至有所需虛通道變?yōu)榭捎迷偻咸岢錾暾垼?

b)若申請被響應，則沿相應虛通道將消息傳向鄰近結點；若申請未被響應，則在下一拍重新執(zhí)行同上述a)的操作，直至有申請被響應后將消息傳向鄰近結點。在每一中間結點上都重復執(zhí)行上述操作，直至將消息傳至目的結點。所謂最大間距輸出虛通道選擇策略是指在允許訪問的通道中，對所在維的維間距(中間結點到目的結點)絕對值最大的虛通道首先提出申請，以縮小尋徑區(qū)域。

VIN0中采用的平面自適應路由策略為：在n維mesh網絡中，對每條物理通道的虛通道進行排序，用C_i,j表示第i維上的所有序號為j的虛通道構成的集合，它可分為正向的虛通道集合C_i,j 和逆向的虛通道集合C_i,j-平面自適應

路由算法定義n一1個自適應平面A₀至A_n-1，每個平面由相鄰二維上的虛通道構成：A_i=C_i,0 C_{i 1,1} C_{i 1,2，}0≤i≤n-2。算法可分為兩級(高層和低層)：

1. 高層算法：(在自適應平面之間)1) For i=0，i<(m-1)，i do在A平面中自適應地路由消息趨近目的結點(見低層算法)end。2)在上述過程結束后，若消息還未到達目的結點，則通過A_n-2=C_n-1,0中的虛通道路由消息至目的結點。

2. 低層算法(在自適平面內)：

自適應平面A包含虛通道集合C_i,0，C_{i 1,1}和C_{i 1,2}在A內消息在第i維和第i 1維上趨近目的結點，自適應地路由。為避免死鎖，將消息分為兩類，一類是在路由過程中需增加第i維地址的稱為增向消息，另一類需減小第i維地址的稱為減向消息。同時，將A中的虛通道分成兩個單獨的虛擬子網：增向子網(包括虛通道集合C_i,0 和C_{i 1,1})和減向子網(包括虛通道集合C_i,0-和C_{i 1,2})。這樣，增向消息在增向子網上路由，減向消息在減向子網上路由，每一消息都能在相應子網中自適應地趨近于目的結點。當消息到達的中間結點的第i維地址與目的結點的第i維地址相等時，在A內的路由過程結束，轉向下一個高層步驟。

多層衛(wèi)星網絡中的路由策略不同于傳統(tǒng)的靜態(tài)路由。雖然星座拓撲是周期性和確定性的動態(tài)路由能夠動態(tài)地維護路由表并適時地交換路由信息。自適應路由策略需要知道網絡中每條ISL上的長度和通信量，自適應地選擇符合有效性和可靠性要求的最優(yōu)路徑。路由計算應用離散化的方式在每一個固定時刻t_k計算路由和更新路由表，t_k=kΔt，k=0,1,2,......,K?1并認為在時間區(qū)間Δt內網絡拓撲結構不變，路由恒定采用固定時間切換策略在路由表更新同時發(fā)生切換。

為了進行網絡分析需要如下假定：

1. 網絡衛(wèi)星相互獨立；

2. 每顆衛(wèi)星節(jié)點承擔不同業(yè)務負載按照業(yè)務模型而定；

3. 每個衛(wèi)星節(jié)點承載的業(yè)務獨立業(yè)務量與衛(wèi)星覆蓋的范圍大小和地理位置相關；

自適應路由路由算法

路由算法采用Bellman-Ford后向路由算法最優(yōu)路徑的判則為該路徑的綜合權重(TPW，totalpathweight)TPW表示了一條路徑的時延和帶寬占用綜合性能，考慮的也是有效和可靠綜合性能。TPW由三部分組成，上行鏈路時延D_u、下行鏈路時延D_d和路徑上每個ISL_wi的鏈路權重LW_wi，表示路徑上ISL的集合W={w₁,w₂,.......,w_i,......,w_ns-1}，|W|=n_s?1表示該條路徑包含n_s?1條ISL，n_s為該路徑上的衛(wèi)星數量(包括源衛(wèi)星和目標衛(wèi)星)。其中地面源和目標位置確定之后，采用仰角最大接入方案選定源衛(wèi)星和目標衛(wèi)星。

其中D_wi表示ISL_wi的傳輸時延，W_wi表示平均星上處理和交換時延，f是信息量權重參數。D_u、D_d和D_wi的求解只需知道衛(wèi)星空間位置坐標，用鏈路長度除以傳輸速度即可，無需冗。

根據Jackson原理，針對數據包業(yè)務，可以將每條ISL看成單服務窗混合制排隊模型M/M/1/m，數據包到來的間隔時間服從負指數分布，參數為β；服務時間是參數為μ為負指數分布，每條ISL有m個數據包排隊容量。當系統(tǒng)中已有m個數據包時，新來的數據包不再進入排隊。數據包被丟棄，有

ρ=β/μ

數據包的平均處理和交換時延為

自適應路由策略步驟

多層衛(wèi)星網絡中的路由策略步驟如下：

步驟1設定基本參數，網絡初始化

步驟2固定一個時刻t_k，在該時間區(qū)間t求解衛(wèi)星軌道參量，計算衛(wèi)星位置坐標和ISL長度，建立網絡拓撲結構

步驟3按照設定的業(yè)務模型，計算MLSN的ISL負載

步驟4根據排隊理論，計算數據包星上處理/交換的時延，如式(14)所示

步驟5根據地面源/目標位置，尋找每個衛(wèi)星層中源衛(wèi)星和目標衛(wèi)星(LEO、MEO和GEO源/目標衛(wèi)星)

步驟6根據QOS需求和網絡狀態(tài)，選擇傳輸業(yè)務的衛(wèi)星層，按照Bellman-Ford路由算法尋找最優(yōu)路徑，缺省的業(yè)務承載衛(wèi)星層為LEO層，但是如果MEO源/目標衛(wèi)星相同，且LEO源/目標衛(wèi)星不同，執(zhí)行步驟9；如果GEO源/目標衛(wèi)星相同，且LEO和MEO源/目標衛(wèi)星不同，執(zhí)行步驟10；否則執(zhí)行步驟7

步驟7如果該LEO層路徑包含ISL數量≤ISL_LEO門限，執(zhí)行步驟8；如果該LEO層路徑包含ISL數量>ISL_LEO門限，且MEO層路徑包含ISL數量≤ISL_LEO門限執(zhí)行步驟9；否則執(zhí)行步驟10

步驟8建立LEO衛(wèi)星層最優(yōu)通信路徑，完成傳輸任務

步驟9建立MEO衛(wèi)星層最優(yōu)通信路徑，完成傳輸任務

步驟10建立GEO衛(wèi)星層最優(yōu)通信路徑，完成傳輸任務

步驟11統(tǒng)計多層網絡的特征參量，分析網絡性能

步驟12更新時間區(qū)間，完成新路由表計算，并完成衛(wèi)星越區(qū)切換

自適應路由特征

多層衛(wèi)星網絡自適應路由策略具有如下特征：業(yè)務通過LEO源衛(wèi)星和目標衛(wèi)星接入衛(wèi)星系統(tǒng)，根據QOS需要和網絡狀態(tài)選擇傳輸該業(yè)務的衛(wèi)星層，如果LEO層網絡資源不能滿足該業(yè)務要求，就將該業(yè)務轉到MEO層傳輸甚至GEO層傳輸對于地面源/目標，直接接入MEO或GEO衛(wèi)星情況。因為路由算法實現簡單，所以未作詳細分析。另外仿真結果所示，LEO層的路徑如果包含6條或7條ISL，時延將大于200ms。這時如果將該業(yè)務轉移到MEO，傳輸時間更短，占用星上資源更少。而且如果地面源和目標位置被同一MEO或GEO衛(wèi)星覆蓋這，時就將該業(yè)務轉到MEO和GEO傳輸，以減少星上資源的占用。該策略考慮時延指標和ISL帶寬占用狀況，最優(yōu)路徑選擇兼顧衛(wèi)星系統(tǒng)有效性和可靠性。

互連網絡路由器是大規(guī)模并行處理機(MassivelyParallelProeessors，MPP)系統(tǒng)的關鍵部件，其性能優(yōu)劣直接影響系統(tǒng)性能，因而其如何高效、簡潔地設計和實現對整個系統(tǒng)起著關鍵作用。

路由器根據其所采用的路由算法可分為確定性和自適應路由器兩種，確定性路由器唯一確定路徑、不受網絡狀態(tài)影響，因而實現簡單，已在很多商用MPP中采用，典型的如IntelParagon中采用的2Dmesh路由器、CrayT3D中采用的3Dtorus路由器等；自適應路由器對于一對源和目的結點，視網絡的工作狀態(tài)，可有多條路徑可選，因而有靈活性好、網絡的通道利用率高和網絡容錯能力強等優(yōu)點，正逐步為新一代的MPP系統(tǒng)所采用，但其工程實現難度較大，僅在少數商用MPP系統(tǒng)中得以實現(如CaryT3E)中實現了完全自適應的路由器)，對它的研究一直是國內外的熱點。

路由器設計中的中心問題是路由算法、切換技術和流控策略。確定性路由算法實現簡單，但網絡利用率低，阻塞嚴重。

自適應路由算法，尤其是完全自適應路由算法消除了這種缺陷，減少了網絡的阻塞延遲，提高了網絡的利用率，但實現難度較大。蟲孔路由(Wormholeoruting)是當今MPP系統(tǒng)中普遍采用的切換技術，在源結點處將要傳送的消息報文劃分成多個微片(Filt)，消息頭微片帶路由信息，當頭微片所需某通道空閑時，頭微片經其向前傳送，通道被消息報文所占用，后續(xù)數據微片以流水方式尾隨頭微片經其向前傳送，直到尾微片經其傳送后釋放該通道;當頭微片所需某通道被占用而受阻時，后續(xù)微片也被阻塞、存儲在路徑中各相應路由器的緩沖器中。虛通道流控策略是當今普遍采用的流控方式，能有效提高網絡利用率，同時避免死鎖，綜合采用虛通道流控與一些特殊的仲裁策略能有效提高網絡性能。

自適應構件是跟隨建筑信息模型（BIM）概念而產生的理念，作為某些特性參數可變的部件，貫穿于整個設計項目的CAD和CAE過程。自適應構件主要表現為Revit族，主要應用于建筑設計和水電供暖行業(yè)。但隨著建筑信息模型（BIM）的深化及普及，自適應構件將更廣泛的應用于如勘測、土木工程、規(guī)劃等眾多領域。

在BIM項目設計過程中，使用自適應構件功能，可以在整個設計項目的任意過程中，創(chuàng)立擁有變量參數的自適應構件。在隨后的設計過程中，如需要變動，可直接修改某個參數，在不影響項目進程的情況下，修改成新的方案。

使用自適應構件功能，可以輕松的自行創(chuàng)建內建族文件，這些文件可沿用到另外的項目當中，而不必重新設立參數。

路由選擇方法的精確描述，屬于網路軟件的一部分。對它的要求是正確、簡單、可靠、穩(wěn)定、公平和優(yōu)化。

路由選擇算法可分為自適應型和非自適應型兩大類。自適應型的特點在于它的路由選擇能在一定程度上隨網路運行狀態(tài)（如流量和拓撲）而改變，可避開出現異態(tài)的節(jié)點或鏈路。非自適應型采用靜態(tài)路由選擇算法。常見的非自適應型有擴散式、隨機式、固定式等；而自適應型有集中式、孤立式、分布式等。

固定式是一種應用范圍比較廣的非自適應型路由選擇算法。它是根據網路拓撲和信息流量的統(tǒng)計模型事先確定各節(jié)點的路由表，每個節(jié)點的路由表指明從該節(jié)點出發(fā)到某個目的節(jié)點所應該選擇的輸出鏈路以及下一節(jié)點。路由表由算法確定，而在固定式中是事先預定的。

最短路徑算法為最常用的算法，它尋求在源節(jié)點和目的節(jié)點之間能沿著長度最短的路徑來傳送分組。這里所指的“長度”賦于特別含義，既可以是實際距離，也可以是平均時延或者鏈路費用。長度參數是路由表的依據，如果參數值來自網路運行的當前狀態(tài)，路由表變?yōu)閯討B(tài)生成，這樣的路由選擇算法就屬于自適應型。

Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。

首先，引進一個輔助向量D，它的每個分量D[i]表示當前所找到的從始點v到每個終點vi的的長度：如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強調相對就是說在算法過程中D的值是在不斷逼近最終結果但在過程中不一定就等于長度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權值；否則置D為∞。顯然，長度為 D[j]=Min{D | vi∈V} 的路徑就是從v出發(fā)的長度最短的一條。此路徑為(v,vj)。 那么，下一條長度次短的是哪一條呢？假設該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的弧上的權值之和。 一般情況下，假設S為已求得的終點的集合，則可證明：下一條最短路徑（設其終點為X）或者是弧(v,x)，或者是中間只經過S中的頂點而最后到達頂點X的路徑。因此，下一條長度次短的的長度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的權值，或者是D[k](vk∈S)和弧(vk,vi)上的權值之和。

算法描述如下：

1）arcs表示弧上的權值。若不存在，則置arcs為∞。S為已找到從v出發(fā)的的終點的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點vi可能達到的度的初值為D=arcs[Locate Vex(G,v),i] vi∈V

2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發(fā)到集合V-S上任一頂點vk可達的最短路徑長度。