徐佳慶，萬(wàn) 文，蔡?hào)|京，唐付橋，何 杰，張 磊

0 引言

近年來(lái)，高性能計(jì)算技術(shù)的高速發(fā)展，高性能計(jì)算系統(tǒng)已被廣泛應(yīng)用于人類的科研和生產(chǎn)的各個(gè)領(lǐng)域。為了滿足科研和生產(chǎn)活動(dòng)對(duì)更高計(jì)算能力的需求，高性能計(jì)算系統(tǒng)規(guī)模(計(jì)算能力)仍在持續(xù)增長(zhǎng)。高性能互連網(wǎng)絡(luò)是高性能計(jì)算系統(tǒng)中重要的子系統(tǒng)，該子系統(tǒng)負(fù)責(zé)高性能計(jì)算系統(tǒng)中計(jì)算系統(tǒng)、存儲(chǔ)系統(tǒng)與I/O設(shè)備間的連接通信，是影響系統(tǒng)性能與可擴(kuò)展性提升的關(guān)鍵因素。盡管單個(gè)互連器件的故障概率很低，但是隨著互連系統(tǒng)的規(guī)模和復(fù)雜性的增加，整個(gè)互連系統(tǒng)出現(xiàn)故障的概率將會(huì)不斷上升，給高性能計(jì)算系統(tǒng)的可靠性帶來(lái)巨大的挑戰(zhàn)。

根據(jù)某個(gè)實(shí)際高性能計(jì)算系統(tǒng)的統(tǒng)計(jì)，互連網(wǎng)絡(luò)器件的平均故障概率約為2．4E－8，在只計(jì)算互連故障、排除其他故障影響的情況下，6．4萬(wàn)個(gè)進(jìn)程通信規(guī)模作業(yè)的平均無(wú)故障時(shí)間約74 d，作業(yè)的平均出錯(cuò)概率為1．3%;而當(dāng)作業(yè)的規(guī)模增加至32萬(wàn)個(gè)進(jìn)程通信時(shí)，作業(yè)的平均無(wú)故障時(shí)間將驟減至3 d以內(nèi)，同時(shí)作業(yè)的出錯(cuò)概率也將猛增至33．66%。目前，互連系統(tǒng)的故障診斷與恢復(fù)已成為各大超算中心日常系統(tǒng)運(yùn)維中的重要環(huán)節(jié)。當(dāng)互連故障發(fā)生時(shí)，如何協(xié)助系統(tǒng)運(yùn)維人員快速地定位和排除互連故障，盡可能地縮小互連故障的影響范圍是互連子系統(tǒng)運(yùn)維過(guò)程中亟需解決的重要問(wèn)題。

根據(jù)長(zhǎng)期積累互連網(wǎng)絡(luò)運(yùn)維經(jīng)驗(yàn)，針對(duì)系統(tǒng)的拓?fù)浼安捎玫穆酚刹呗栽O(shè)計(jì)一套高效的互連容錯(cuò)策略是應(yīng)對(duì)互連故障的有效手段。在文獻(xiàn)［1］中，我們實(shí)現(xiàn)了一種適用于普通胖樹(shù)拓?fù)湎到y(tǒng)的分布式動(dòng)態(tài)路由容錯(cuò)方法，該方法針對(duì)不同類型的互連故障定義了一套路由容錯(cuò)算法，當(dāng)互連故障發(fā)生時(shí)，互連監(jiān)控軟件能夠及時(shí)偵測(cè)故障，并調(diào)用路由容錯(cuò)算法提供一條健康的路徑對(duì)數(shù)據(jù)進(jìn)行路由以避開(kāi)故障路徑。

K-Ary N-Bridge拓?fù)?又稱高維胖樹(shù))是一種新型的胖樹(shù)拓?fù)浣Y(jié)構(gòu)［2］，該拓?fù)浣Y(jié)構(gòu)由國(guó)防科技大學(xué)天河互連團(tuán)隊(duì)首次提出并應(yīng)用于實(shí)際高性能計(jì)算系統(tǒng)的構(gòu)建，相較于其他拓?fù)浣Y(jié)構(gòu)，該拓?fù)淇梢蕴峁└玫木W(wǎng)絡(luò)擴(kuò)展性和更高的網(wǎng)絡(luò)性能。本文對(duì)于這種新型拓?fù)涞幕ミB故障進(jìn)行了分析，并提出了一套適用于高維胖樹(shù)拓?fù)涞拇_定性路由容錯(cuò)策略。實(shí)驗(yàn)表明，該路由容錯(cuò)策略在實(shí)際的高維胖樹(shù)拓?fù)湎到y(tǒng)中取得了預(yù)期的容錯(cuò)效果，減少了互連故障的影響范圍，提高了系統(tǒng)的可維性和可用性。

1 相關(guān)工作

目前在高性能計(jì)算的互連領(lǐng)域，主要存在著以Ethernet為代表的通用網(wǎng)絡(luò)和以InfiniBand為代表的專用網(wǎng)絡(luò)兩大類。Ethernet是采用簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議(Simple Network Management Protocol，SNMP)來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)管理，該協(xié)議是J．D．Case等在1990年提出的，通過(guò)網(wǎng)絡(luò)端口之間周期性地發(fā)送雙向轉(zhuǎn)發(fā)檢測(cè)(Bidirectional Forwarding Detection，BFD)報(bào)文來(lái)檢查端口狀態(tài)，若幾個(gè)周期之內(nèi)沒(méi)有收到對(duì)端報(bào)文，則認(rèn)為該端口處于“Down”狀態(tài)，然后規(guī)避該端口，并重新發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)洌?］。而InfiniBand則增加了一層子網(wǎng)管理層，子網(wǎng)管理器通過(guò)子網(wǎng)管理代理來(lái)感知整個(gè)互連網(wǎng)絡(luò)的狀態(tài)，當(dāng)發(fā)生互連故障時(shí)，子網(wǎng)管理器將啟動(dòng)拓?fù)浒l(fā)現(xiàn)，并根據(jù)當(dāng)前的互連拓?fù)渲匦掠?jì)算并配置路由表［4］。

當(dāng)前，互連網(wǎng)絡(luò)的容錯(cuò)研究已成為高性能互連網(wǎng)絡(luò)領(lǐng)域亟需解決的熱點(diǎn)問(wèn)題之一，具有很高的實(shí)用價(jià)值?；ミB網(wǎng)絡(luò)容錯(cuò)的硬件基礎(chǔ)是源節(jié)點(diǎn)到目的節(jié)點(diǎn)有多條路徑冗余，而B(niǎo)utterfly等拓?fù)渲挥袉我宦窂剑ǔＰ枰ㄟ^(guò)增加鏈路或者交換機(jī)來(lái)提供容錯(cuò)能力［5－6］，這種方法實(shí)現(xiàn)簡(jiǎn)單，但增加了硬件開(kāi)銷。誤路由(misrouting)是另一種常被使用的路由容錯(cuò)方法，該方法使用更長(zhǎng)的路徑來(lái)避開(kāi)互連故障［7］，增加了數(shù)據(jù)的傳輸延遲。文獻(xiàn)［8］將以上兩種容錯(cuò)方法相結(jié)合，提出了一種混合容錯(cuò)方法，該方法可以獲得更好的容錯(cuò)性能，但同時(shí)增加了硬件代價(jià)和數(shù)據(jù)傳輸延遲。

胖樹(shù)拓?fù)涫钱?dāng)前高性能計(jì)算中使用較多的一種拓?fù)浣Y(jié)構(gòu)，該結(jié)構(gòu)在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間有多條通信路徑，具有良好的互連容錯(cuò)支持能力，為動(dòng)態(tài)路由容錯(cuò)方法的實(shí)現(xiàn)提供了基礎(chǔ)。文獻(xiàn)［9］提出了一種由并行胖樹(shù)構(gòu)成并且對(duì)應(yīng)交換機(jī)由鏈路相連的拓?fù)湟詫?shí)現(xiàn)容錯(cuò)。該方法具有良好的靜態(tài)容錯(cuò)性能，但在動(dòng)態(tài)容錯(cuò)的情況下只能容忍一條故障鏈路。文獻(xiàn)［10］提出在胖樹(shù)中通過(guò)局部誤路由的方式實(shí)現(xiàn)動(dòng)態(tài)容錯(cuò)，該方法增加了數(shù)據(jù)的路徑長(zhǎng)度，增加了網(wǎng)絡(luò)延時(shí)。文獻(xiàn)［11］采用了包含排除區(qū)間的區(qū)間路由方法來(lái)實(shí)現(xiàn)胖樹(shù)動(dòng)態(tài)容錯(cuò)，該方法的缺點(diǎn)是健康路徑可能被犧牲。文獻(xiàn)［12］采用集中式的網(wǎng)絡(luò)管理來(lái)維護(hù)網(wǎng)絡(luò)配置、監(jiān)測(cè)鏈路狀態(tài)、傳播網(wǎng)絡(luò)失效和路由信息，以實(shí)現(xiàn)胖樹(shù)中的動(dòng)態(tài)容錯(cuò)。該方法具有很好的靈活性，但由于管理節(jié)點(diǎn)需要和網(wǎng)絡(luò)中的所有交換機(jī)相連并通信，其系統(tǒng)的擴(kuò)展性受到很大的限制。文獻(xiàn)［13］針對(duì)采用源路由的胖樹(shù)網(wǎng)絡(luò)，提出了一種端節(jié)點(diǎn)動(dòng)態(tài)容錯(cuò)路由實(shí)現(xiàn)方法，相較于分布式路由，其擴(kuò)展能力有限。文獻(xiàn)［14］則提出了一種分布式動(dòng)態(tài)容錯(cuò)路由方法，通過(guò)引入了鏈路失效消息傳播機(jī)制和動(dòng)態(tài)容錯(cuò)路由算法來(lái)實(shí)現(xiàn)胖樹(shù)網(wǎng)絡(luò)的分布式動(dòng)態(tài)容錯(cuò)，該方法的優(yōu)點(diǎn)是無(wú)需增加硬件代價(jià)和路徑長(zhǎng)度，但該方法只是停留于理論研究，并未實(shí)際應(yīng)用。

2 高維胖樹(shù)系統(tǒng)及其優(yōu)越性

構(gòu)建高性能計(jì)算(High Performance Computing，HPC)系統(tǒng)時(shí)首當(dāng)其沖需要考慮的問(wèn)題是系統(tǒng)采用何種拓?fù)浣Y(jié)構(gòu)?？v觀新一屆TOP500(June，2017)榜單中排名前十的系統(tǒng)，除排名第一的“Sunway TaihuLight”采用了商用的Mellanox InfiniBand互連外，其余9臺(tái)系統(tǒng)均采用了定制的互連系統(tǒng)。根據(jù)系統(tǒng)所采用的拓?fù)浣Y(jié)構(gòu)可將TOP10的系統(tǒng)分為以下三類:第一類是以“Sequoia”“Mira”和“K computer”為代表的 K-Ary N-Cube拓?fù)浣Y(jié)構(gòu);第二類是“Piz Daint”“Cori”“Trinity”三臺(tái) Cray XC系統(tǒng)所采用的Dragonfly拓?fù)浣Y(jié)構(gòu);第三類則是以“Tianhe-2”為代表的Fat Tree拓?fù)浣Y(jié)構(gòu)。

K-Ary N-Bridge是近年來(lái)涌現(xiàn)出了一種新型的拓?fù)浣Y(jié)構(gòu)，該拓?fù)渚C合了K-Ary N-Cube和Fat Tree拓?fù)涓髯缘膬?yōu)點(diǎn)，因而展現(xiàn)出了更好的可擴(kuò)展性和網(wǎng)絡(luò)性能，目前該拓?fù)湟言趯?shí)際系統(tǒng)中得到了應(yīng)用。在介紹K-Ary N-Bridge拓?fù)淝?，本文將首先?duì)K-Ary N-Cube和Fat Tree拓?fù)溥M(jìn)行簡(jiǎn)單的介紹。

2．1 K-Ary N-Cube拓?fù)?/h3>

K-Ary N-Cube拓?fù)?，又稱為N維Torus。K-Ary N-Cube是由K個(gè)K-Ary(N－1)-Cube網(wǎng)絡(luò)通過(guò)連接第N維來(lái)構(gòu)成。標(biāo)準(zhǔn)的K-Ary N-Cube拓?fù)渲邪琄N個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)中總的鏈路數(shù)為N×KN，網(wǎng)絡(luò)直徑為KN/2，在網(wǎng)絡(luò)流量均勻分布的模式下，每個(gè)報(bào)文的平均跳步數(shù)為 KN/4，網(wǎng)絡(luò)的二分鏈路數(shù)4KN－1。8-Ary 1-Cube和8-Ary 2-Cube拓?fù)浣Y(jié)構(gòu)分別如圖1(a)和1(b)所示。

圖1 K-Ary N-Cube拓?fù)銯ig．1 K-Ary N-Cube topology

2．2 Fat Tree拓?fù)?/h3>

Fat Tree拓?fù)涫歉咝阅苡?jì)算系統(tǒng)中一種常用拓?fù)浣Y(jié)構(gòu)，其基本結(jié)構(gòu)如圖2所示。對(duì)N層Fat Tree而言:其最多可連接2(K/2)N個(gè)節(jié)點(diǎn);最大跳步數(shù)為2N－1;二分帶寬為2(K/2)N。

2．3 K-Ary N-Bridge拓?fù)涞亩x

在高階路由器的支持下，可以考慮將Torus網(wǎng)絡(luò)中每維的所有節(jié)點(diǎn)通過(guò)一個(gè)高階路由器進(jìn)行連接，即成了一個(gè)K-Ary 1-Bridge拓?fù)?，如圖3(a)所示。再將K-Ary 1-Bridge拓?fù)渫呔S擴(kuò)展，就形成了K-Ary N-Bridge拓?fù)洌瑥亩行p少網(wǎng)絡(luò)跳步數(shù)和降低網(wǎng)絡(luò)延遲。K-Ary N-Bridge拓?fù)溆蓛深惤粨Q機(jī)構(gòu)成，其中直接與節(jié)點(diǎn)相連的交換機(jī)稱為葉交換機(jī)，連接不同葉交換機(jī)的交換機(jī)稱為根交換機(jī)，其規(guī)模為KN－1×KN－2×… ×Ki×… ×K1×K0，其中Ki表示第i維上葉交換機(jī)的數(shù)量，i∈{0，1，…，N－1}。葉交換機(jī)連接每個(gè)維度的端口數(shù)均為Q，則其總的上行端口數(shù)為N×Q;在每個(gè)維度上，葉交換機(jī)分別與Q個(gè)根交換機(jī)相連，形成Q-port上行、Ki-port下行的非標(biāo)準(zhǔn)胖樹(shù)結(jié)構(gòu)，該維度上的根交換機(jī)稱為i維根交換機(jī)。葉交換機(jī)用LSW(jN－1，jN－2，…，j1，j0) 表示，其中 ji∈{0，1，…，Ki－1}，ji標(biāo)示葉交換機(jī)在陣列中所處的位置。第i維根交換機(jī)為RSW(i，jN－1，…，jm，…，ji+1，ji－1，…，j0，p)，其中 jm∈ {0，1，…，Km－1}，p∈{0，1，…，Q －1}，i表示根交換機(jī)所在維度，jm表示第i維根交換機(jī)所在的位置，p表示交換機(jī)的編號(hào)。特別地當(dāng)N=2時(shí)，如圖3(b)所示，用RSW(0，k)表示0維中第k個(gè)根交換機(jī)，RSW(1，k)表示1維中第 k個(gè)根交換機(jī)，用LSW(i，j)表示葉交換機(jī)在二維陣列中的坐標(biāo)。

圖2 兩級(jí)胖樹(shù)拓?fù)銯ig．2 2-level fat tree topology

圖3 高維胖樹(shù)拓?fù)銯ig．3 K-Ary N-Bridge topology

2．4 K-Ary N-Bridge拓?fù)涞膬?yōu)越性

與K-Ary N-Cube拓?fù)浣Y(jié)構(gòu)相比，K-Ary N-Bridge結(jié)構(gòu)具有以下三點(diǎn)優(yōu)勢(shì):

1)可擴(kuò)展性更高:K-Ary N-Bridge網(wǎng)絡(luò)可以方便地?cái)U(kuò)展網(wǎng)絡(luò)規(guī)模。當(dāng)節(jié)點(diǎn)的端口數(shù)和路由器的端口數(shù)固定時(shí)，仍可以通過(guò)用交換機(jī)替換維度上的路由器方式來(lái)擴(kuò)展網(wǎng)絡(luò)規(guī)模。如假設(shè)路由器設(shè)計(jì)為K個(gè)端口，使用若干個(gè)路由器構(gòu)成2K個(gè)端口的交換機(jī)，替代K-Ary N-Bridge中的路由器來(lái)構(gòu)造網(wǎng)絡(luò)，即可構(gòu)建更大規(guī)模的網(wǎng)絡(luò)。

2)網(wǎng)絡(luò)直徑更小:同等規(guī)模下，K-Ary N-Bridge拓?fù)涞奶綌?shù)僅為2N;而K-Ary N-Cube拓?fù)涞奶綌?shù)則為KN/4;顯然K-Ary N-Bridge拓?fù)淇梢垣@得更小的網(wǎng)絡(luò)延遲。

3)網(wǎng)絡(luò)性能更高:在同等規(guī)模下，當(dāng)K≥8時(shí)，K-Ary N-Cube網(wǎng)絡(luò)的吞吐率將會(huì)下降;而K-Ary N-Bridge拓?fù)溆捎谑褂妙愃茦?shù)形的結(jié)構(gòu)，網(wǎng)絡(luò)吞吐率不會(huì)隨K的增大而下降，因而可以獲得更高的網(wǎng)絡(luò)性能。

而相較于Fat Tree拓?fù)浣Y(jié)構(gòu)，K-Ary N-Bridge結(jié)構(gòu)具有以下兩點(diǎn)優(yōu)勢(shì):

1)K-Ary N-Bridge拓?fù)涫褂脝蝹€(gè)路由器來(lái)連接單個(gè)維度上的所有節(jié)點(diǎn)，完全擺脫高密度交換機(jī)的設(shè)計(jì)限制，可構(gòu)建大規(guī)模的互連網(wǎng)絡(luò)。而Fat Tree網(wǎng)絡(luò)則嚴(yán)重依賴高密度的交換機(jī)來(lái)擴(kuò)展規(guī)模;

2)二分帶寬與Fat Tree網(wǎng)絡(luò)相當(dāng)，而且隨網(wǎng)絡(luò)規(guī)模線性增長(zhǎng)。

3 互連故障分類及其影響范圍

互連故障是高性能計(jì)算機(jī)中一類重要的故障。與節(jié)點(diǎn)故障不同的是，單條鏈路或單個(gè)交換機(jī)故障往往會(huì)影響多個(gè)甚至全系統(tǒng)所有節(jié)點(diǎn)間的通信。在高維胖樹(shù)系統(tǒng)中常見(jiàn)的互連故障包括鏈路故障、交換芯片故障和交換機(jī)故障三大類。

其中，鏈路故障可根據(jù)其嚴(yán)重程度分為連通性故障和穩(wěn)定性故障。當(dāng)出現(xiàn)連通性故障時(shí)，報(bào)文無(wú)法將通過(guò)該鏈路;當(dāng)出現(xiàn)穩(wěn)定性故障時(shí)，報(bào)文可以通過(guò)多次重傳，到達(dá)對(duì)端交換機(jī)，但會(huì)影響報(bào)文的傳輸效率。根據(jù)實(shí)際經(jīng)驗(yàn)，鏈路的穩(wěn)定性故障若不得到及時(shí)的處理往往會(huì)惡化成鏈路的連通性故障。

交換芯片和交換機(jī)故障通常表現(xiàn)為掉電，若交換芯片或交換機(jī)的上電復(fù)位電路發(fā)生故障，則有可能引發(fā)交換芯片或交換機(jī)故障。若發(fā)生此類故障，則會(huì)導(dǎo)致通過(guò)該交換芯片或交換機(jī)所有節(jié)點(diǎn)或服務(wù)器的通信受阻。按照交換機(jī)的位置可以分為葉交換機(jī)和根交換機(jī)故障，其中根交換機(jī)故障僅會(huì)影響其所在維的通信，而葉交換機(jī)故障則會(huì)影響該葉交換機(jī)所在位置上不同維度間葉交換機(jī)的通信。以圖4中二維胖樹(shù)為例，當(dāng)葉交換機(jī)LSW(i，j)發(fā)生故障時(shí)，葉交換機(jī)LSW(a，j)與LSW(i，b)間的節(jié)點(diǎn)通信均會(huì)受阻，其中0≤a≤K1－1，0≤b≤K0－1(在圖中用實(shí)線框表示)，由于葉交換機(jī)故障影響范圍大，是高維胖樹(shù)拓?fù)渲兴赜械幕ミB故障類型，因此本文將重點(diǎn)研究此類互連故障的路由容錯(cuò)策略。

圖4 二維胖樹(shù)拓?fù)渲械娜~交換機(jī)故障Fig．4 Leaf switch fault in K-Ary 2-Bridge topology

4 高維胖樹(shù)系統(tǒng)的路由容錯(cuò)策略設(shè)計(jì)與實(shí)現(xiàn)

當(dāng)交換芯片發(fā)生故障時(shí)，由于無(wú)法更換單個(gè)交換芯片，通常需要將芯片所在的交換機(jī)斷電后更換，因此在日常的互連維護(hù)中，可將交換芯片故障視同于交換機(jī)故障來(lái)處理。對(duì)于鏈路故障和根交換機(jī)的故障，其影響范圍及路由容錯(cuò)策略與標(biāo)準(zhǔn)胖樹(shù)拓?fù)浠鞠嗤谖墨I(xiàn)［1］中已有詳盡的描述，本文將僅作簡(jiǎn)要介紹。而葉交換機(jī)由于涉及不同維度之間的通信，屬于高維胖樹(shù)拓?fù)渲兴赜械墓收项愋?，需要設(shè)計(jì)新的路由容錯(cuò)方案。

從 葉 交 換 機(jī) LSW(xN－1，xN－2，…，x1，x0) 到 葉 交 換 機(jī)LSW(yN－1，yN－2，…，y1，y0) 需要依次經(jīng)過(guò) LSW(yN－1，xN－2，…，x1，x0)，LSW(yN－1，yN－2，…，x1，x0)，…，LSW(yN－1，yN－2，…，y1，x0)以及連接這些葉交換機(jī)的根交換機(jī)。當(dāng)葉交換機(jī)LSW(yN－1，yN－2，…，yz，…，x1，x0) 出現(xiàn)故障時(shí)，鏈路中斷，且無(wú)冗余路徑，此時(shí)需要通過(guò)誤路由來(lái)實(shí)現(xiàn)容錯(cuò)(公共路徑用點(diǎn)劃線表示，正常路徑用虛線表示，經(jīng)誤路由后的容錯(cuò)路徑用實(shí)線表示)，具體方法如圖5所示:由于圖中選取的截面內(nèi)不涉及 z和 z － 1 維之外的坐標(biāo)，可將 LSW(yN－1，yN－2，…，xz，xz－1，…，x1，x0) 記為 LSW(xz，xz－1)，以 z維中由于葉交換機(jī)故障而斷開(kāi)的任意一條鏈路p為例，首先通過(guò)修改該故障鏈路所連接根交換機(jī)RSW(z，xz－1，p) 到葉交換機(jī)的路由表項(xiàng)，使原本第2跳到的故障葉交換機(jī)LSW(yz，xz－1)的報(bào)文傳遞到與z維的相鄰葉交換機(jī)LSW((yz+1)%Kz，xz－1) 上(用數(shù)字2表示)，然后通過(guò)增加此葉交換機(jī)和z－1維根交換機(jī)RSW(z－1，(yz+1)%Kz，p)的路由表項(xiàng)的方式使得報(bào)文到達(dá)z－1維的相鄰葉交換機(jī) LSW((yz+1)%Kz，(xz－1+1)%Kz－1)(用數(shù)字3、4表示)，將故障的葉交換機(jī)避開(kāi)后，即可通過(guò)正常路由的方式依次到達(dá) LSW(yN－1，yN－2，…，yz，(xz－1+1)%Kz－1，…，x1，x0)，LSW(yN－1，yN－2，…，yz，yz－1，…，x1，x0)，…，LSW(yN－1，yN－2，…，y1，x0) 最 終 到 達(dá) 目 標(biāo) 葉 交 換 機(jī) LSW(yN－1，yN－2，…，y1，y0)。由于第3和4跳路徑對(duì)正常路由不造成影響，故可將該路由表項(xiàng)事先配置到所有葉交換機(jī)的交換芯片中，當(dāng)葉交換機(jī)故障發(fā)生時(shí)，僅需修改與之相連的根交換機(jī)RSW(z，yN－1，yN－2，…，yz，xz－1，…，x1，x0，p) 的相關(guān)路由配置(圖中第 2 跳路徑)，即可完成誤路由修改，從而可以快捷地完成葉交換機(jī)的容錯(cuò)處理。

圖5 葉交換機(jī)容錯(cuò)原理Fig．5 Fault-tolerance strategy for leaf switch fault

偽代碼如下所示:

BEGIN:

/*from leaf-switch LSW(xN－1，xN－2，…，x1，x0)to leaf-switch

LSW(yN－1，yN－2，…，y1，y0)*/

For each z dimension root switch do{

S1:if(the first different dimension of dest ID and local ID is z)then{

output port is to the leaf-switch LSW(yN－1，yN－2，…，yz，xz－1，

…，x1，x0)} //shortest path

S2:else{

output port is to the leaf-switch LSW(yN－1，yN－2，…，(xz+

1)%Kz，xz－1，…，x1，x0)} //misrouting for fault-tolerant

S3:if(in the S1 case but next leaf-switch is going wrong)then{

output port is to the leaf-switch LSW(yN－1，yN－2，…，yz，(xz－1

+1)%Kz－1，…，x1，x0)} /*misrouting for fault-tolerant

and need to be changed by shell script*/

}

For each leaf-switch do{

S1:if(input port link to j dimension root-switch the first different

dimension of dest ID and local ID is i and i≠j)then{

output port is the port link to i dimension root-switch}

//shortest path

S2:else{

output port is the port link to(i－1)dimension root-switch}

//misrouting for fault-tolerant

}

END

5 驗(yàn)證實(shí)驗(yàn)

由于高維胖樹(shù)拓?fù)渲墟溌饭收?包括上行鏈路與下行鏈路)和根交換機(jī)故障的路由容錯(cuò)策略與標(biāo)準(zhǔn)胖樹(shù)拓?fù)渲械穆酚扇蒎e(cuò)策略基本相同，且文獻(xiàn)［1］中已有詳盡的說(shuō)明以及實(shí)驗(yàn)驗(yàn)證，本文僅對(duì)葉交換機(jī)的路由容錯(cuò)策略進(jìn)行驗(yàn)證。

本次實(shí)驗(yàn)在一個(gè)實(shí)際的HPC系統(tǒng)上進(jìn)行，該系統(tǒng)采用了33×6的二維胖樹(shù)拓?fù)?。葉交換機(jī)的路由容錯(cuò)策略通過(guò)Shell腳本實(shí)現(xiàn)(config_err_board．sh)，該腳本有兩個(gè)輸入?yún)?shù)，第一個(gè)參數(shù)為交換機(jī)的坐標(biāo)信息，第二個(gè)參數(shù)表示屏蔽(error)還是恢復(fù)(renew)該葉交換機(jī)，如圖6(d)和6(e)所示。實(shí)驗(yàn)使用了AlltoAll通信測(cè)試程序來(lái)檢測(cè)節(jié)點(diǎn)列表內(nèi)所有節(jié)點(diǎn)間的連通性，該程序的通信模式為節(jié)點(diǎn)集合內(nèi)每一個(gè)節(jié)點(diǎn)周期性地向其他節(jié)點(diǎn)發(fā)送一定規(guī)模的測(cè)試數(shù)據(jù)塊，同時(shí)該節(jié)點(diǎn)周期性地接收來(lái)自其他節(jié)點(diǎn)的數(shù)據(jù)塊。實(shí)驗(yàn)步驟如下:

1)選定葉交換機(jī)LSW(13，2)為目標(biāo)葉交換機(jī)，選取與葉交換機(jī) LSW(a，2) 與 LSW(13，b)，(其中0≤ a≤32，a≠13，0≤b≤5，b≠2)相連的節(jié)點(diǎn)為節(jié)點(diǎn)列表，運(yùn)行AlltoAll通信測(cè)試程序，結(jié)果如圖6(a)所示。

2)假設(shè)互連監(jiān)控軟件檢測(cè)到葉交換機(jī)LSW(13，2)發(fā)生了故障，此時(shí)通過(guò)路由容錯(cuò)腳本來(lái)屏蔽該葉交換機(jī)，如圖6(d)所示。

3)對(duì)葉交換機(jī)LSW(13，2)進(jìn)行切電，AlltoAll通信測(cè)試程序仍可正常運(yùn)行，如圖6(b)所示。

4)運(yùn)行一段時(shí)間后，重新對(duì)目標(biāo)葉交換機(jī)加電后再利用路由容錯(cuò)腳本來(lái)恢復(fù)該葉交換機(jī)，如圖6(e)所示。

5)再次觀察AlltoAll通信測(cè)試程序，測(cè)試程序正常運(yùn)行未受任何影響，如圖6(c)。

6)由容錯(cuò)原理可知，配置容錯(cuò)路由后，跳步數(shù)增加了4跳，經(jīng)測(cè)試發(fā)現(xiàn)配置前的平均延遲為4．98 μs，而配置容錯(cuò)路由后，平均延遲為 5．47 μs，增加了 0．49 μs;點(diǎn)點(diǎn)帶寬在配置前后基本保持不變。

圖6 葉交換機(jī)屏蔽和恢復(fù)實(shí)驗(yàn)Fig．6 Shield and recover experiments for leaf switch fault

實(shí)驗(yàn)表明，針對(duì)葉交換機(jī)的路由容錯(cuò)策略達(dá)到預(yù)期目標(biāo)，可以快速實(shí)現(xiàn)對(duì)目標(biāo)葉交換機(jī)的屏蔽與恢復(fù)。目前，該路由容錯(cuò)策略已應(yīng)用于實(shí)際系統(tǒng)的日常運(yùn)維中，取得了良好的容錯(cuò)效果。

6 結(jié)語(yǔ)

本文研究了高維胖樹(shù)這一新型拓?fù)渲谢ミB故障的類型及其故障影響范圍，鑒于高維胖樹(shù)拓?fù)渲腥~交換機(jī)故障影響范圍大這一特點(diǎn)，采用誤路由的思想，設(shè)計(jì)了針對(duì)此類故障的路由容錯(cuò)策略。實(shí)驗(yàn)表明，利用該路由容錯(cuò)策略可以有效減少葉交換機(jī)故障在系統(tǒng)中的影響范圍，便于運(yùn)維人員及時(shí)更換和維修葉交換機(jī)。目前，本文所提出的路由容錯(cuò)策略已用于實(shí)際系統(tǒng)的運(yùn)維并達(dá)到了快速屏蔽故障葉交換的預(yù)期效果。下一步工作計(jì)劃將該路由容錯(cuò)策略集成到自主研發(fā)的互連監(jiān)控軟件中，使得高維胖樹(shù)系統(tǒng)中互連故障的監(jiān)測(cè)和屏蔽完全自動(dòng)化。