VTFTR：高維胖樹(shù)中的無(wú)死鎖容錯(cuò)路由算法

劉博陽(yáng)，胡舒凱，施得君，盧宏生

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

0 概述

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

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

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

1 相關(guān)工作

1.1 容錯(cuò)路由算法

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

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

1.2 高維胖樹(shù)

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

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

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

2）尋找性能優(yōu)于胖樹(shù)的新拓?fù)浣Y(jié)構(gòu)，如第一臺(tái)使用Hyperx 結(jié)構(gòu)［12］的超算，其某些方面的性能優(yōu)于等規(guī)模的胖樹(shù)結(jié)構(gòu)［13］，LIANG等［14］提出一種在部分通信模式下性能高于三層胖樹(shù)的均等拓?fù)洌琖ANG等［15］結(jié)合胖樹(shù)與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ò)對(duì)交換機(jī)與鏈路在數(shù)量上的需求。

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

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

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

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

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

2 VTFTR 算法

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

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

2.1 算法說(shuō)明

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

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

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

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

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

圖3 VTFTR 容錯(cuò)路徑Fig.3 Fault-tolerant path in VTFTR

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

算法1Routing in fig.3

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

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

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

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

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

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

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

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

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

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

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

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

2.3 VTFTR 無(wú)死鎖推論

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

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

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

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

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

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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