自適應(yīng)路由

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

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

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

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

2)將網(wǎng)絡(luò)劃分成兩個(gè)虛擬網(wǎng)：VIN0和VIN1。在VIN0中使用序號(hào)從0至2的虛通道；在VIN1中使用序號(hào)為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)時(shí)，如該結(jié)點(diǎn)是目的結(jié)點(diǎn)則消息被接收，否則：

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

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

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

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

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

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

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

多層衛(wèi)星網(wǎng)絡(luò)中的路由策略不同于傳統(tǒng)的靜態(tài)路由。雖然星座拓?fù)涫侵芷谛院痛_定性的動(dòng)態(tài)路由能夠動(dòng)態(tài)地維護(hù)路由表并適時(shí)地交換路由信息。自適應(yīng)路由策略需要知道網(wǎng)絡(luò)中每條ISL上的長(zhǎng)度和通信量，自適應(yīng)地選擇符合有效性和可靠性要求的最優(yōu)路徑。路由計(jì)算應(yīng)用離散化的方式在每一個(gè)固定時(shí)刻t_k計(jì)算路由和更新路由表，t_k=kΔt，k=0,1,2,......,K?1并認(rèn)為在時(shí)間區(qū)間Δt內(nèi)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不變，路由恒定采用固定時(shí)間切換策略在路由表更新同時(shí)發(fā)生切換。

為了進(jìn)行網(wǎng)絡(luò)分析需要如下假定：

1. 網(wǎng)絡(luò)衛(wèi)星相互獨(dú)立；

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

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

自適應(yīng)路由路由算法

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

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

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

ρ=β/μ

數(shù)據(jù)包的平均處理和交換時(shí)延為

自適應(yīng)路由策略步驟

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

步驟1設(shè)定基本參數(shù)，網(wǎng)絡(luò)初始化

步驟2固定一個(gè)時(shí)刻t_k，在該時(shí)間區(qū)間t求解衛(wèi)星軌道參量，計(jì)算衛(wèi)星位置坐標(biāo)和ISL長(zhǎng)度，建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

步驟3按照設(shè)定的業(yè)務(wù)模型，計(jì)算MLSN的ISL負(fù)載

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

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

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

步驟7如果該LEO層路徑包含ISL數(shù)量≤ISL_LEO門(mén)限，執(zhí)行步驟8；如果該LEO層路徑包含ISL數(shù)量>ISL_LEO門(mén)限，且MEO層路徑包含ISL數(shù)量≤ISL_LEO門(mén)限執(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)計(jì)多層網(wǎng)絡(luò)的特征參量，分析網(wǎng)絡(luò)性能

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

自適應(yīng)路由特征

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

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

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

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

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

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

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

使用自適應(yīng)構(gòu)件功能，可以輕松的自行創(chuàng)建內(nèi)建族文件，這些文件可沿用到另外的項(xiàng)目當(dāng)中，而不必重新設(shè)立參數(shù)。

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

路由選擇算法可分為自適應(yīng)型和非自適應(yīng)型兩大類(lèi)。自適應(yīng)型的特點(diǎn)在于它的路由選擇能在一定程度上隨網(wǎng)路運(yùn)行狀態(tài)（如流量和拓?fù)洌┒淖?，可避開(kāi)出現(xiàn)異態(tài)的節(jié)點(diǎn)或鏈路。非自適應(yīng)型采用靜態(tài)路由選擇算法。常見(jiàn)的非自適應(yīng)型有擴(kuò)散式、隨機(jī)式、固定式等；而自適應(yīng)型有集中式、孤立式、分布式等。

固定式是一種應(yīng)用范圍比較廣的非自適應(yīng)型路由選擇算法。它是根據(jù)網(wǎng)路拓?fù)浜托畔⒘髁康慕y(tǒng)計(jì)模型事先確定各節(jié)點(diǎn)的路由表，每個(gè)節(jié)點(diǎn)的路由表指明從該節(jié)點(diǎn)出發(fā)到某個(gè)目的節(jié)點(diǎn)所應(yīng)該選擇的輸出鏈路以及下一節(jié)點(diǎn)。路由表由算法確定，而在固定式中是事先預(yù)定的。

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

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

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

算法描述如下：

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

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