自適應路由

互連網路路由器是大規模並行處理機系統的關鍵部件，根據其所採用的路由算法可分為確定性和自適應路由器兩種，自適應路由器對於一對源和目的結點，視網路的工作狀態，可有多條路徑可選。

基本介紹

• 中文名：自適應路由
• 外文名：Adaptive Routing
• 路由器分類：確定性和自適應路由器
• 優點：靈活性好、網路的通道利用率高等
• 典型：Cary T3E
• 套用領域：通信工程、計算機科學、電子科學

概述

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

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

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

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

PBFAA算法

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；若沒有可用虛通道，則暫停提出申請，等待直至有所需虛通道變為可用再同上提出申請；

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

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內的路由過程結束，轉向下一個高層步驟。

多層衛星自適應路由策略

多層衛星網路中的路由策略不同於傳統的靜態路由。雖然星座拓撲是周期性和確定性的動態路由能夠動態地維護路由表並適時地交換路由信息。自適應路由策略需要知道網路中每條ISL上的長度和通信量，自適應地選擇符合有效性和可靠性要求的最優路徑。路由計算套用離散化的方式在每一個固定時刻t_k計算路由和更新路由表，t_k=kΔt，k=0,1,2,......,K−1並認為在時間區間Δt區域網路絡拓撲結構不變，路由恆定採用固定時間切換策略在路由表更新同時發生切換。

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

1. 網路衛星相互獨立；
   
2. 每顆衛星節點承擔不同業務負載按照業務模型而定；
   
3. 每個衛星節點承載的業務獨立業務量與衛星覆蓋的範圍大小和地理位置相關；
   

路由算法

路由算法採用Bellman-Ford後向路由算法最優路徑的判則為該路徑的綜合權重(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為該路徑上的衛星數量(包括源衛星和目標衛星)。其中地面源和目標位置確定之後，採用仰角最大接入方案選定源衛星和目標衛星。

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

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

ρ=β/μ

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

策略步驟

多層衛星網路中的路由策略步驟如下：

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

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

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

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

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

步驟6根據QOS需求和網路狀態，選擇傳輸業務的衛星層，按照Bellman-Ford路由算法尋找最優路徑，預設的業務承載衛星層為LEO層，但是如果MEO源/目標衛星相同，且LEO源/目標衛星不同，執行步驟9；如果GEO源/目標衛星相同，且LEO和MEO源/目標衛星不同，執行步驟10；否則執行步驟7

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

步驟8建立LEO衛星層最優通信路徑，完成傳輸任務

步驟9建立MEO衛星層最優通信路徑，完成傳輸任務

步驟10建立GEO衛星層最優通信路徑，完成傳輸任務

步驟11統計多層網路的特徵參量，分析網路性能

步驟12更新時間區間，完成新路由表計算，並完成衛星越區切換

特徵

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