[科普中國]-自適應(yīng)路由

概述

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

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

路由器設(shè)計中的中心問題是路由算法、切換技術(shù)和流控策略。確定性路由算法實現(xiàn)簡單，但網(wǎng)絡(luò)利用率低，阻塞嚴(yán)重。

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

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

人們對直接網(wǎng)絡(luò)中采用蟲孔路由切換技術(shù)的自適應(yīng)路由算法已進(jìn)行了大量研究，提出了很多算法，但它們或存在自適應(yīng)性受限，或存在代價較大，或存在靈活性不夠等缺點(diǎn).在已有算法的基礎(chǔ)上，以低通信延遲、高網(wǎng)絡(luò)吞吐率和易VLSI實現(xiàn)為設(shè)計目標(biāo)，提出了一個可擴(kuò)展性好、自適應(yīng)性強(qiáng)的基于平面的完全自適應(yīng)路由算法PBFAA。

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

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

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

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

4)當(dāng)一條消息的頭微片到達(dá)某一結(jié)點(diǎn)時，如該結(jié)點(diǎn)是目的結(jié)點(diǎn)則消息被接收，否則：

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

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

VIN0中采用的平面自適應(yīng)路由策略為：在n維mesh網(wǎng)絡(luò)中，對每條物理通道的虛通道進(jìn)行排序，用Ci,j表示第i維上的所有序號為j的虛通道構(gòu)成的集合，它可分為正向的虛通道集合Ci,j+和逆向的虛通道集合Ci,j-平面自適應(yīng)

路由算法定義n一1個自適應(yīng)平面A0至An-1，每個平面由相鄰二維上的虛通道構(gòu)成：Ai=Ci,0+Ci+1,1+Ci+1,2，0≤i≤n-2。算法可分為兩級(高層和低層)：

高層算法：(在自適應(yīng)平面之間)

1) For i=0，iISLLEO門限，且MEO層路徑包含ISL數(shù)量≤ISLLEO門限執(zhí)行步驟9；否則執(zhí)行步驟10

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

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

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

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

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

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