劉博陽，胡舒凱，施得君，盧宏生

（1.戰(zhàn)略支援部隊(duì)信息工程大學(xué)，鄭州 450001；2.江南計算技術(shù)研究所，江蘇 無錫 214100；3.國家并行計算機(jī)工程技術(shù)研究中心，北京 100190）

0 概述

在2022 年上半年top500 的榜單中，美國橡樹嶺國家實(shí)驗(yàn)室的超級計算機(jī)“Frontier”超過“富岳”，排在了top500 的第一位。“Frontier”基于HPE Cray EX235A 架構(gòu)，使用Slingshot 互連技術(shù)，處理器選擇AMD RPYC 64C 2 GHz，擁有8 730 112 個內(nèi)核。根據(jù)Linpack 基準(zhǔn)測試，“Frontier”峰值性能達(dá)到了1.102 Exaflop/s，即每秒110.2 億億次，超過了E 級計算機(jī)每秒百億億次的標(biāo)準(zhǔn)［1］?！癋rontier”的發(fā)布標(biāo)志著超算的發(fā)展正式進(jìn)入E 級時代。

隨著高性能計算系統(tǒng)進(jìn)入E 級時代，超算整體規(guī)模越來越大，急劇膨脹的系統(tǒng)規(guī)模對高性能互連網(wǎng)絡(luò)設(shè)計在拓?fù)浣Y(jié)構(gòu)、路由算法、擁塞控制等方面提出了更高的要求。在單個節(jié)點(diǎn)故障概率相同的條件下，高性能計算系統(tǒng)的規(guī)模越大，系統(tǒng)無故障工作的期望時間MTTF（Mean Time to Failure）就越短，系統(tǒng)性能隨故障數(shù)量提高而呈現(xiàn)階梯式下降趨勢，故障數(shù)量每累積到一定程度，系統(tǒng)性能就發(fā)生一次嚴(yán)重下降［2］。分析近年來超算規(guī)模變化與故障的情況可以發(fā)現(xiàn)，隨著系統(tǒng)規(guī)模的擴(kuò)大，容錯能力在超算中的重要性逐漸提升至與效率、算力相當(dāng)?shù)某潭龋?］。在E 級時代的超大規(guī)模高性能計算系統(tǒng)中，頻繁的因故障停工，無論是在時間成本上還是在能耗上都是不可接受的，而故障的發(fā)生不可避免，因此，要有相應(yīng)的容錯手段來保證出現(xiàn)少量故障時整個系統(tǒng)仍能保持一定的工作能力，進(jìn)而延長系統(tǒng)的單次工作時間。

高維胖樹是一種近年來被提出的混合拓?fù)浣Y(jié)構(gòu)，其不僅擁有與胖樹結(jié)構(gòu)［4］相當(dāng)?shù)膶Ψ謳捫阅?，還有較經(jīng)典胖樹更好的可擴(kuò)展性與更低的網(wǎng)絡(luò)直徑，在E 級甚至后E 級時代有望成為主流高性能互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。本文對高性能互連網(wǎng)絡(luò)中容錯路由相關(guān)工作進(jìn)行介紹，分析高維胖樹及其故障情況，提出一種針對高維胖樹葉交換機(jī)故障的容錯路由算法VTFTR，并對其優(yōu)越性進(jìn)行實(shí)驗(yàn)分析。

1 相關(guān)工作

1.1 容錯路由算法

容錯路由算法是互連網(wǎng)絡(luò)容錯設(shè)計的重要組成部分，可以使計算節(jié)點(diǎn)之間在發(fā)生故障時仍然保持一定的通信能力。容錯路由的設(shè)計基礎(chǔ)是存在物理鏈路或路由路徑的冗余，冗余的設(shè)置一般是以成本增加或性能下降為代價來實(shí)現(xiàn)的。以網(wǎng)絡(luò)中兩個固定節(jié)點(diǎn)之間的連接為例，增加一條用于容錯的物理鏈路會額外占用兩個端口，從而導(dǎo)致網(wǎng)絡(luò)可支持的最大規(guī)模下降，也可以使用不增加物理鏈路的方法，在路徑上出現(xiàn)故障時從其他節(jié)點(diǎn)間的路徑上繞行，這種方法會擠占其他路徑上的網(wǎng)絡(luò)資源，引起整體網(wǎng)絡(luò)性能下降。容錯算法設(shè)計的重點(diǎn)是平衡容錯性能與成本之間的關(guān)系，設(shè)計目標(biāo)是以盡可能低的性能代價或硬件成本來實(shí)現(xiàn)最好的容錯效果。

對于路由算法設(shè)計而言，對死鎖的預(yù)防或恢復(fù)很有必要。轉(zhuǎn)向模型是一種應(yīng)用廣泛的路由算法設(shè)計思路，其核心是通過控制消息在Mesh/Torus 中的流動方向來預(yù)防可能產(chǎn)生的死鎖。轉(zhuǎn)向模型的成本主要在于限制消息的轉(zhuǎn)向會降低部分鏈路的使用率，從而導(dǎo)致網(wǎng)絡(luò)性能下降。目前最常見的死鎖預(yù)防方法是在可能形成環(huán)路的部分進(jìn)行虛通道切換［5］，在一條物理通道中劃分出多條虛擬通道。容錯虛通道在Mesh/Torus 拓?fù)浣Y(jié)構(gòu)與Dragonfly［6］拓?fù)浣Y(jié)構(gòu)中得到十分廣泛的使用，其用于容錯的成本是非容錯路徑可用的緩沖等網(wǎng)絡(luò)資源下降。動態(tài)緩沖管理［7］的使用通過私有緩沖與共享緩沖組合的方法，從一定程度上減輕了使用多條虛通道帶來的緩沖資源浪費(fèi)與頭阻塞問題。即便如此，過多地設(shè)置容錯虛通道、頻繁地進(jìn)行容錯虛通道切換，仍然會給路由芯片的設(shè)計帶來極大困難。文獻(xiàn)［8］提出一種轉(zhuǎn)向模型與虛通道相結(jié)合的容錯算法，該算法在不同的虛網(wǎng)絡(luò)中分別使用不同的路由規(guī)則，保證每一套虛網(wǎng)絡(luò)中無環(huán)路存在，最終達(dá)到使用少量虛通道實(shí)現(xiàn)片上Mesh 網(wǎng)絡(luò)無死鎖容錯的效果。

1.2 高維胖樹

如圖1 所示，胖樹結(jié)構(gòu)是高性能互連網(wǎng)絡(luò)中常用的一種拓?fù)浣Y(jié)構(gòu)，其憑借著高對分帶寬、高可擴(kuò)展性、優(yōu)良的容錯能力、拓?fù)湟子诖罱ǖ葍?yōu)勢在當(dāng)前的高性能計算系統(tǒng)中占據(jù)了主流位置［9］。目前，關(guān)于胖樹的研究主要分為3 個方向：

圖1 4-port 3-tree 胖樹結(jié)構(gòu)Fig.1 4-port 3-tree fat-tree structure

1）拓展胖樹結(jié)構(gòu)的使用范圍，如提升胖樹結(jié)構(gòu)在數(shù)據(jù)中心的表現(xiàn)［10］、探索在片上網(wǎng)絡(luò)中使用類胖樹結(jié)構(gòu)的可能性［11］。

2）尋找性能優(yōu)于胖樹的新拓?fù)浣Y(jié)構(gòu)，如第一臺使用Hyperx 結(jié)構(gòu)［12］的超算，其某些方面的性能優(yōu)于等規(guī)模的胖樹結(jié)構(gòu)［13］，LIANG等［14］提出一種在部分通信模式下性能高于三層胖樹的均等拓?fù)?，WANG等［15］結(jié)合胖樹與k-ary n-cube 的結(jié)構(gòu)特點(diǎn)提出k-Cube k-Ary n-Tree（CAT）與Mirrored k-Cube k-Ary n-Tree（MiCAT）兩種拓?fù)浣Y(jié)構(gòu)，可以大幅降低網(wǎng)絡(luò)對交換機(jī)與鏈路在數(shù)量上的需求。

3）對胖樹結(jié)構(gòu)進(jìn)行拓展或者優(yōu)化。近年來，一系列胖樹的拓展結(jié)構(gòu)先后被提出，ADDO等［16］提出一種胖樹的拓展結(jié)構(gòu)Zfattree 并給出其彈回重路由容錯路由策略，WANG等［17］提出一種可以降低硬件成本的鏡像叉樹網(wǎng)絡(luò)，并針對該網(wǎng)絡(luò)給出鄰居切換算法、下一級算法與X 轉(zhuǎn)彎算法3 種容錯路由算法。此外，還有一種結(jié)合胖樹與多維環(huán)網(wǎng)結(jié)構(gòu)而提出的高維胖樹結(jié)構(gòu)，高維胖樹擁有優(yōu)于經(jīng)典胖樹的可擴(kuò)展性，同時還兼具多維環(huán)網(wǎng)結(jié)構(gòu)的部分優(yōu)勢，是E 級時代高性能互連網(wǎng)絡(luò)拓?fù)涞闹匾M成。

如圖2 所示（RSW 為行交換機(jī)，CSW 為列交換機(jī)，LSW 為葉交換機(jī)），高維胖樹是一種新型混合拓?fù)洌@種結(jié)構(gòu)可以視為將高維環(huán)網(wǎng)每一維度的連接從環(huán)連接替換為高階交換機(jī)或胖樹連接。高維胖樹結(jié)構(gòu)的雛形可以認(rèn)為是1996年日立公司的高性能計算系統(tǒng)SR2201所使用的Hybrid Crossbar Network［18］。Hybrid Crossbar Network 是一個三維的拓?fù)浣Y(jié)構(gòu)，每一維度連接使用交叉開關(guān)來實(shí)現(xiàn)。高階路由芯片YARC［19］與對應(yīng)高階路由器的提出與使用［20］，將高性能互連網(wǎng)絡(luò)帶入了高階時代。文獻(xiàn)［21］與文獻(xiàn)［22］分別提出使用高階路由器構(gòu)建的高維胖樹結(jié)構(gòu)。高維胖樹在文獻(xiàn)［21］中被稱為K-ary N-direct M-indirect結(jié)構(gòu)（在該作者的后續(xù)論文中修改為K-ary N-direct S-indirect（KNS）），在文獻(xiàn)［22］中被稱為k-ary n-bridge 結(jié)構(gòu)。其中，KNS 結(jié)構(gòu)的定義更為豐富，每一維度的連接可以使用高階交換機(jī)、胖樹或者RUFT（Reduced Unidirectional Fat-Tree）［23］結(jié)構(gòu)來實(shí)現(xiàn)。國防科技大學(xué)的天河團(tuán)隊(duì)在其E 級原型機(jī)中使用了該拓?fù)洌⒎Q其為k-dimension tree［24］。本文將該結(jié)構(gòu)統(tǒng)稱為高維胖樹（k-dimension fat-tree）。高維胖樹擁有優(yōu)秀的可擴(kuò)展性，使用72 端口交換機(jī)構(gòu)建的二維胖樹規(guī)模可以達(dá)到十萬個節(jié)點(diǎn)以上，基本滿足E 級時代的設(shè)計需求。此外，在高維胖樹中二維以上的算法性能均可由二維擴(kuò)展推出。因此，本文所提算法與相關(guān)分析均是基于二維胖樹，每個子維度上至多使用二層胖樹。

圖2 二維胖樹（16×16）Fig.2 2-dimension fat-tree（16×16）

胖樹拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)間存在大量的路徑冗余，且其上下網(wǎng)的模式較Mesh 而言更難產(chǎn)生死鎖，當(dāng)前已經(jīng)有大量相關(guān)的容錯算法［2，25-26］。高維胖樹中一般采取維序路由，當(dāng)使用誤路由［27］進(jìn)行容錯設(shè)計時維序路由的無環(huán)特性可能被打破，因此，高維胖樹中容錯路由的設(shè)計需要預(yù)防死鎖。

高維胖樹中的交換機(jī)類型主要分為根交換機(jī)與葉交換機(jī)，其中，葉交換機(jī)直接與計算節(jié)點(diǎn)相連，根交換機(jī)負(fù)責(zé)每一維度上葉交換機(jī)之間的連接。高維胖樹結(jié)構(gòu)每一個子維度上的根交換機(jī)與葉交換機(jī)都可以視為一個獨(dú)立的胖樹結(jié)構(gòu)，因此，當(dāng)根交換機(jī)發(fā)生故障時可以使用胖樹中的算法進(jìn)行上下行路由容錯。而葉交換機(jī)是高維胖樹中較為獨(dú)特的結(jié)構(gòu)，需要為其故障設(shè)計獨(dú)特的容錯算法。根據(jù)高維胖樹的結(jié)構(gòu)特點(diǎn)，在使用維序路由時，葉交換機(jī)故障會影響其自身連接的所有計算節(jié)點(diǎn)，同時影響其所在行列間的所有通信。以規(guī)模為n×n的二維胖樹為例，任意一個葉交換機(jī)故障都會導(dǎo)致網(wǎng)絡(luò)中的n2條節(jié)點(diǎn)間的通路斷開，極大影響網(wǎng)絡(luò)的可用性。高維胖樹中葉交換機(jī)故障的影響范圍和處理模式與Mesh/Torus中的節(jié)點(diǎn)故障具有很高的相似度，因此，進(jìn)行容錯設(shè)計時可以參考部分Mesh/Torus 網(wǎng)絡(luò)中的容錯算法［28-29］。文獻(xiàn)［30］提出一種針對葉交換機(jī)故障的誤路由容錯算法，采用一定的誤路由策略，可以在故障發(fā)生時屏蔽故障節(jié)點(diǎn)以便維護(hù)人員進(jìn)行故障排除。但是，該算法只描述了單個故障的對策，還需要考慮在故障節(jié)點(diǎn)得到維修前出現(xiàn)新故障的情況，且該算法不選擇切換虛通道來預(yù)防死鎖，沒有對算法可能產(chǎn)生死鎖的情況進(jìn)行分析。文獻(xiàn)［31］提出一種通過實(shí)時重構(gòu)路由表、選擇中介節(jié)點(diǎn)繞行解決高維胖樹中鏈路故障的容錯算法，該算法每選擇一個中介節(jié)點(diǎn)就需要進(jìn)行一次虛通道切換，在故障數(shù)量較多時會因?yàn)槿蒎e虛通道的設(shè)置而降低網(wǎng)絡(luò)資源利用率，從而給硬件設(shè)計帶來難度。

2 VTFTR 算法

結(jié)合轉(zhuǎn)向模型與虛通道切換的思想，本文提出一種針對高維胖樹中葉交換機(jī)故障的容錯路由算法VTFTR，該算法通過控制容錯路徑的選擇與轉(zhuǎn)向，可以選擇出最短跳步數(shù)的容錯路徑，同時顯著降低對容錯虛通道數(shù)量的需求。在高維胖樹中，報文在根交換機(jī)的上下行路徑會導(dǎo)致每個維度的正負(fù)方向間存在部分重疊，因此，傳統(tǒng)的禁止單個轉(zhuǎn)向的方法并不適用。在高維胖樹中避免環(huán)路的形成，至少要在網(wǎng)絡(luò)中禁止兩個以上的轉(zhuǎn)向，因此，只要使單套網(wǎng)絡(luò)中僅存在x維度至y維度的轉(zhuǎn)向或僅存在y維度至x維度的轉(zhuǎn)向，就可以保證網(wǎng)絡(luò)無環(huán)無死鎖，最終達(dá)到僅靠一條容錯虛通道實(shí)現(xiàn)無死鎖容錯路由的效果。為了更好地描述算法，本文使用部分詞語對網(wǎng)絡(luò)中的結(jié)構(gòu)或路由操作進(jìn)行替代，具體如表1 所示。

表1 文中部分詞語釋義Table 1 Definitions of some words in the text

2.1 算法說明

VTFTR 算法的基礎(chǔ)是xy維序路由，每次發(fā)現(xiàn)故障時通過路由重構(gòu)修改3 項(xiàng)信息：將xy路由中經(jīng)過故障節(jié)點(diǎn)的路徑修改為yx路由；將故障發(fā)生列從所有行交換機(jī)的容錯備選條目中刪除；將故障發(fā)生行從所有列交換機(jī)的容錯備選條目中刪除。在此基礎(chǔ)上，本文算法根據(jù)故障數(shù)量與狀態(tài)進(jìn)行如下處理：

1）發(fā)現(xiàn)葉交換機(jī)故障。消息在行交換機(jī)查表時發(fā)現(xiàn)目標(biāo)葉交換機(jī)故障無法下行，通過查詢備選條目路由至同行的其他任意葉交換機(jī)，之后進(jìn)行一次列路由至目標(biāo)所在行，再通過一次行路由到達(dá)目標(biāo)葉交換機(jī)。

2）后續(xù)發(fā)生故障。xy路由路徑上發(fā)現(xiàn)的故障可以繼續(xù)按照第1）步中的處理方式進(jìn)行繞行；yx容錯路徑上的突發(fā)故障則需要在列交換機(jī)上進(jìn)行一次誤路由，到達(dá)非故障所在行后重新進(jìn)行一次xy路由即可。

3）存在多點(diǎn)故障。在已存在故障且未發(fā)現(xiàn)新故障時，網(wǎng)絡(luò)中節(jié)點(diǎn)間的通信分為3 種：（1）正常路徑不經(jīng)過故障節(jié)點(diǎn)，采取xy路由；（2）正常路徑經(jīng)過故障節(jié)點(diǎn)而容錯路徑不經(jīng)過故障節(jié)點(diǎn)，采取yx容錯路由；（3）xy與yx路由均經(jīng)過故障節(jié)點(diǎn)，則采取第（1）步或第（2）步中的誤路由方案進(jìn)行繞行。

具體地，如圖3 所示，當(dāng)報文發(fā)現(xiàn)葉交換機(jī)故障時，報文在行路由階段選擇原中介節(jié)點(diǎn)的同行備選節(jié)點(diǎn)進(jìn)行路由，繞開故障節(jié)點(diǎn)之后進(jìn)行一次列路由，到達(dá)相應(yīng)的列之后再行路由至目標(biāo)節(jié)點(diǎn)。圖中虛線箭頭為無故障情況下的原始路徑，實(shí)線部分是LSW(xd，ys)故障后的兩條容錯路徑。

圖3 VTFTR 容錯路徑Fig.3 Fault-tolerant path in VTFTR

圖3 中路由策略對應(yīng)的偽代碼如算法1 所示：

算法1Routing in fig.3

當(dāng)葉交換機(jī)發(fā)生故障時，發(fā)現(xiàn)故障的根交換機(jī)將故障葉交換機(jī)的信息通過消息包傳遞到子網(wǎng)管理模塊，子網(wǎng)管理模塊通過廣播包的方式改寫全部根交換機(jī)的路由表項(xiàng)，將存在葉交換機(jī)故障的維度從容錯選項(xiàng)中刪除或屏蔽，保證后續(xù)再出現(xiàn)故障時不會因?yàn)槿蒎e而路由至已經(jīng)故障的葉交換機(jī)，以至于形成死鎖或其他問題。具體表現(xiàn)為：當(dāng)網(wǎng)絡(luò)中無故障發(fā)生時，所有行/列交換機(jī)的備選條目均為n-1 個，當(dāng)某個葉交換機(jī)發(fā)生故障時，所有行/列交換機(jī)中去往該列/行條目對應(yīng)的備選條目不變，去往所有其他列/行的備選條目中屏蔽該列對應(yīng)的條目，達(dá)到將此列/行從容錯路徑中刪除的效果。

如圖4 所示，行交換機(jī)0 在無故障時，每個端口的備選條目都包含同行的其他全部葉交換機(jī)；當(dāng)葉交換機(jī)12 與葉交換機(jī)21 發(fā)生故障后，行交換機(jī)0 中的容錯條目被修改，故障所在列（1和2）從容錯條目中被刪除。網(wǎng)絡(luò)中的葉交換機(jī)因?yàn)楣收隙龠M(jìn)入容錯路由時，不會選擇列1 與列2 作為容錯路徑，避免了路徑上出現(xiàn)多故障的可能性。列交換機(jī)0 的情況同理。

圖4 VTFTR 容錯條目修改Fig.4 Fault-tolerant table modification in VTFTR

最終，在多故障情況下本文算法中節(jié)點(diǎn)的路徑選擇如圖5 所示。S1 至D1 之間葉交換機(jī)02 與20 同時故障，報文需要誤路由至03 節(jié)點(diǎn)，再進(jìn)行一次yx路由到達(dá)目標(biāo)節(jié)點(diǎn)；S2 至D2 之間葉交換機(jī)02 故障，需要進(jìn)行yx路由經(jīng)過11 到達(dá)D2；S3 至D3 之間無故障存在，按照xy維序路由即可。該算法提供的繞路方案會破壞網(wǎng)絡(luò)的無環(huán)特性從而導(dǎo)致死鎖，因此，需要在容錯路徑從列路由到行路由時進(jìn)行一次虛通道切換進(jìn)入容錯虛通道。圖中實(shí)線部分為無故障虛通道，虛線部分為容錯虛通道。

圖5 多故障下的路徑示例Fig.5 Examples of paths with multiple faults

2.2 VTFTR 優(yōu)越性分析

VTFTR 算法的優(yōu)越性主要體現(xiàn)在3 個方面：

1）優(yōu)勢1。通過控制容錯路徑，將多故障問題化解為單故障問題，避免了路徑上重復(fù)出現(xiàn)故障節(jié)點(diǎn)的情況，能選出跳步數(shù)最少的容錯路徑。

2）優(yōu)勢2。通過將維序路由與虛通道切換相結(jié)合，控制容錯路徑的選擇，僅使用一條容錯虛通道即可實(shí)現(xiàn)對多個故障的無死鎖容錯。

3）優(yōu)勢3。容錯能力強(qiáng)，只要故障節(jié)點(diǎn)沒有覆蓋所有行列，即可保證全網(wǎng)無故障節(jié)點(diǎn)間可達(dá)，且在每次路由重構(gòu)完成前對新故障有即時處理的策略。

其中，優(yōu)勢1 通過本文算法的定義與描述即可推導(dǎo)，且通過圖5 可以看出，該算法容錯時根據(jù)故障情況分別需要2、3、4 次行/列路由，相較于目前現(xiàn)有的算法（文獻(xiàn)［30］所提算法，下文稱算法A），大部分路徑會有2～4 個跳步的節(jié)約。由優(yōu)勢1 可知，本文算法中的穩(wěn)定路徑至多包含行-列-行三步，容錯路徑上突發(fā)故障的即時誤路由策略至多包含列-行-列與行-列-行-列兩種，只需在yx路由時（即列路由到行路由之間）進(jìn)行一次虛通道切換，即可保證無故障路徑與容錯路徑均無死鎖。

對優(yōu)勢3 推論如下：該算法理論上可以在（n-1）行/列的交換機(jī)都存在單個或多個故障的情況下仍然保持其他非故障節(jié)點(diǎn)間的通信。在故障節(jié)點(diǎn)數(shù)超過n時，在k個葉交換機(jī)發(fā)生故障的情況下，仍然有的概率保持網(wǎng)絡(luò)中正常節(jié)點(diǎn)間連接。更直觀地，在16×16個葉交換機(jī)組成的二維胖樹中，如果故障葉交換機(jī)的數(shù)量在15 個及以下，VTFTR 可以實(shí)現(xiàn)完全容錯；如果故障節(jié)點(diǎn)超過16 個，以20 個為例，VTFTR 只有極小的概率（4.807e-22）無法維持非故障節(jié)點(diǎn)間的連接。VTFTR的強(qiáng)容錯能力還表現(xiàn)在，當(dāng)發(fā)現(xiàn)葉交換機(jī)故障后，路由重構(gòu)完成前如果出現(xiàn)了新故障，該算法的繞行策略仍然可以完成容錯路由，且根據(jù)優(yōu)勢2 可保證無死鎖，不再需要額外的容錯虛通道。

2.3 VTFTR 無死鎖推論

本節(jié)對VTFTR 的無死鎖特性進(jìn)行推導(dǎo)與論證。VTFTR 中的虛通道分為無故障虛通道（默認(rèn)虛通道）與容錯虛通道，要證明VTFTR 無死鎖，只需要證明報文在無故障虛通道與容錯虛通道中均無環(huán)無死鎖即可。

在高維胖樹（仍然以二維胖樹為例，更高維度同理）中，報文在網(wǎng)絡(luò)中的路徑根據(jù)維度與方向可以分為x上、x下、y上、y下4 種，其中，“上”指從 葉交換機(jī)到行列交換機(jī)，“下”則相反。VTFTR 的基本路由策略采取維序路由，報文根據(jù)源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的位置關(guān)系，按照x上＞x下＞y上＞y下的優(yōu)先級進(jìn)行路由。按照固定維序進(jìn)行路由的報文在網(wǎng)絡(luò)中不會形成環(huán)路，也就不會產(chǎn)生死鎖。

在無故障發(fā)生時，所有報文均選擇無故障虛通道并采取維序路由，該環(huán)節(jié)不會產(chǎn)生死鎖。當(dāng)故障存在時，報文在無故障虛通道進(jìn)行一次維序路由后進(jìn)行一次虛通道切換，在容錯虛通道中重新按照x上、x下、y上、y下的順序進(jìn)行維序路由。根據(jù)2.2 節(jié)VTFTR 優(yōu)越性分析，參考圖5 中多故障模式下的路徑示例，在VTFTR 中至多需要切換一次容錯虛通道、進(jìn)行一次序的優(yōu)先級重置，即可完成對多故障節(jié)點(diǎn)與突發(fā)故障節(jié)點(diǎn)的繞行。在低序到高序的部分進(jìn)行虛通道切換，即可確保本文算法整體不會產(chǎn)生死鎖。

3 實(shí)驗(yàn)結(jié)果與性能分析

本文實(shí)驗(yàn)在NetSim 網(wǎng)絡(luò)模擬器中進(jìn)行，NetSim是基于正在某超算系統(tǒng)中使用的交換機(jī)結(jié)構(gòu)而設(shè)計開發(fā)的網(wǎng)絡(luò)模擬器。

3.1 實(shí)驗(yàn)方案

在NetSim 模擬器中構(gòu)建不同規(guī)模的二維胖樹進(jìn)行如下兩組測試：

1）單點(diǎn)故障。在小規(guī)模（8×8）的二維胖樹中測試單葉交換機(jī)故障情況下的單點(diǎn)通信延遲與全網(wǎng)通信性能變化，將本文算法與算法A 進(jìn)行對比。

2）多點(diǎn)故障。在4 096 個節(jié)點(diǎn)規(guī)模的二維胖樹中，測試不同注入率下虛通道的設(shè)置與容錯路徑的使用對全網(wǎng)平均延遲與吞吐率的影響，逐漸增加網(wǎng)絡(luò)中葉交換機(jī)的故障數(shù)量，觀察算法在多點(diǎn)故障下的容錯能力。根據(jù)VTFTR 的容錯原理可知，當(dāng)多點(diǎn)故障分布的行列增加時，需增加跳步容錯的路徑越多，整體網(wǎng)絡(luò)沖突越嚴(yán)重，相應(yīng)的網(wǎng)絡(luò)性能會越差。因此，還需要對每種確定的故障數(shù)量情況進(jìn)行不同分布的模擬，觀察故障分布對容錯性能的影響。需要說明的是，算法A 用于多點(diǎn)故障時沒有死鎖預(yù)防策略，存在死鎖的可能，因此，多點(diǎn)故障時選擇對本文算法在不同故障數(shù)量與不同故障分布情況下的性能進(jìn)行模擬實(shí)驗(yàn)，以觀察本文算法的容錯成本。

3.2 結(jié)果分析

在單點(diǎn)故障（高維胖樹拓?fù)湓诮Y(jié)構(gòu)上具有對稱性，單個葉交換機(jī)的故障位置對結(jié)果不會產(chǎn)生影響）中，首先對比單點(diǎn)通信延遲的增加。網(wǎng)絡(luò)中任意行列均不同的兩點(diǎn)間通信延遲為237 ns，本文算法誤路由時增加2 個跳步，延遲為307 ns，yx路由時不增加跳步，延遲為237 ns；算法A 增加4 個跳步，延遲為377 ns。2 種算法單點(diǎn)通信延遲的差距符合預(yù)期。圖6 中0 error 1vc 為VTFTR 無故障時的全網(wǎng)性能，較不配置容錯虛通道（0 error 2 vc）時的性能有略微下降，該現(xiàn)象的原因是設(shè)置的容錯虛通道資源沒有使用，屬于正常的容錯成本，可以通過提高硬件成本或改變緩沖配置來降低該影響。對比圖6 中吞吐率與網(wǎng)絡(luò)延遲的數(shù)據(jù)可以看出，在單點(diǎn)故障發(fā)生時，使用VTFTR 進(jìn)行容錯只在高注入率時有少量的吞吐率下降與網(wǎng)絡(luò)延遲上升。算法A 在注入率超過50%時延遲明顯上升，這是因?yàn)樵撍惴ㄊ褂霉潭ǖ娜蒎e路徑，網(wǎng)絡(luò)負(fù)載提升到一定程度時，容錯路徑上的網(wǎng)絡(luò)擁塞嚴(yán)重。綜合來看，VTFTR 的性能表現(xiàn)優(yōu)于算法A，具體地，VTFTR 與算法A 在低注入率時性能表現(xiàn)差別不大，均對網(wǎng)絡(luò)性能沒有明顯影響，但是在注入率升高至50%以上時，本文算法的吞吐率較算法A 有明顯提升，網(wǎng)絡(luò)延遲有明顯下降，原因是本文算法在單點(diǎn)故障容錯時較算法A 少用了2 個～4 個跳步，且隨機(jī)分配容錯路徑較固定容錯路徑能避免單一容錯路徑上的擁塞。

圖6 單點(diǎn)故障下2 種算法的性能對比Fig.6 Performance comparison of two algorithms under single point fault

當(dāng)網(wǎng)絡(luò)中存在多點(diǎn)故障時，故障的行列分布會在一定程度上影響容錯算法的整體性能。圖7 是故障葉交換機(jī)數(shù)量為5 時不同故障分布情況對應(yīng)的網(wǎng)絡(luò)性能（c 為故障同列，all 為故障不同行不同列，r 為故障同行，r1、r2為隨機(jī)），可以看出，不同分布之間網(wǎng)絡(luò)性能差距極小。在圖8 中，故障數(shù)量增加至10 個，故障分布對網(wǎng)絡(luò)性能的影響逐漸凸顯，但是整體吞吐率的波動在2%以內(nèi)。

圖7 故障分布對網(wǎng)絡(luò)性能的影響（5 節(jié)點(diǎn)）Fig.7 Effect of fault distribution on network performance（5 nodes）

圖8 故障分布對網(wǎng)絡(luò)性能的影響（10 節(jié)點(diǎn)）Fig.8 Effect of fault distribution on network performance（10 nodes）

在模擬不同故障數(shù)量對網(wǎng)絡(luò)的影響時，將故障節(jié)點(diǎn)設(shè)置在不同行不同列，降低故障分布給結(jié)果帶來的影響。如圖9 所示，網(wǎng)絡(luò)整體性能隨著故障數(shù)量的增加而逐漸降低，主要表現(xiàn)在吞吐率的下降與延遲的增加。當(dāng)故障數(shù)量較少時，全網(wǎng)的通信性能幾乎不變，故障數(shù)量上升至5 時，VTFTR 能以1%的吞吐率下降與少許延遲提升為代價實(shí)現(xiàn)非故障節(jié)點(diǎn)間的正常通信。即使葉交換機(jī)故障數(shù)量上升至10，其他節(jié)點(diǎn)之間的網(wǎng)絡(luò)仍然可以正常使用，代價僅為2%的吞吐率下降與延遲上升。

圖9 不同故障數(shù)量對網(wǎng)絡(luò)性能的影響Fig.9 Effect of different fault numbers on network performance

結(jié)合模擬結(jié)果可以看出：在網(wǎng)絡(luò)負(fù)載較低時，容錯路徑的使用對整個網(wǎng)絡(luò)間的通信影響極小，無論是吞吐率還是整個網(wǎng)絡(luò)的延遲都沒有因?yàn)槿蒎e路徑與虛通道的設(shè)置而降低；在網(wǎng)絡(luò)負(fù)載較高時，對于仍處于網(wǎng)絡(luò)中的節(jié)點(diǎn)來說，整個網(wǎng)絡(luò)的延遲仍然沒有明顯提升；在多點(diǎn)故障尤其是故障數(shù)量較多時，本文算法能夠以較低的吞吐率下降為代價實(shí)現(xiàn)對全部無故障節(jié)點(diǎn)的無死鎖容錯路由，相較于算法A，VTFTR算法不僅在單點(diǎn)故障時表現(xiàn)更好，還補(bǔ)充了多點(diǎn)故障時的無死鎖容錯方案，整體容錯能力有較大提升。

4 結(jié)束語

本文通過分析高維胖樹中的容錯設(shè)計特點(diǎn)，提出一種用于高維胖樹葉交換機(jī)故障的容錯路由算法VTFTR。該算法對容錯虛通道的需求較小、容錯跳步較少，且適用于多節(jié)點(diǎn)故障與實(shí)時突發(fā)故障的情況。本文的模擬推論都是基于二維胖樹，在更高維度的胖樹中可以推廣使用，從而為高維胖樹中容錯路由的設(shè)計與選擇提供新思路。下一步考慮從微結(jié)構(gòu)入手，將胖樹中的多軌結(jié)構(gòu)［32］或泛樹結(jié)構(gòu)［33］應(yīng)用于高維胖樹，并針對這些結(jié)構(gòu)設(shè)計容錯算法，從而為高維胖樹中的容錯、故障修復(fù)等可靠性問題提供解決方案。