高維胖樹系統中確定性路由容錯策略實現

徐佳慶，萬 文，蔡東京，唐付橋，何 杰，張 磊

0 引言

近年來，高性能計算技術的高速發展，高性能計算系統已被廣泛應用于人類的科研和生產的各個領域。為了滿足科研和生產活動對更高計算能力的需求，高性能計算系統規模(計算能力)仍在持續增長。高性能互連網絡是高性能計算系統中重要的子系統，該子系統負責高性能計算系統中計算系統、存儲系統與I/O設備間的連接通信，是影響系統性能與可擴展性提升的關鍵因素。盡管單個互連器件的故障概率很低，但是隨著互連系統的規模和復雜性的增加，整個互連系統出現故障的概率將會不斷上升，給高性能計算系統的可靠性帶來巨大的挑戰。

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

根據長期積累互連網絡運維經驗，針對系統的拓撲及采用的路由策略設計一套高效的互連容錯策略是應對互連故障的有效手段。在文獻［1］中，我們實現了一種適用于普通胖樹拓撲系統的分布式動態路由容錯方法，該方法針對不同類型的互連故障定義了一套路由容錯算法，當互連故障發生時，互連監控軟件能夠及時偵測故障，并調用路由容錯算法提供一條健康的路徑對數據進行路由以避開故障路徑。

K-Ary N-Bridge拓撲(又稱高維胖樹)是一種新型的胖樹拓撲結構［2］，該拓撲結構由國防科技大學天河互連團隊首次提出并應用于實際高性能計算系統的構建，相較于其他拓撲結構，該拓撲可以提供更好的網絡擴展性和更高的網絡性能。本文對于這種新型拓撲的互連故障進行了分析，并提出了一套適用于高維胖樹拓撲的確定性路由容錯策略。實驗表明，該路由容錯策略在實際的高維胖樹拓撲系統中取得了預期的容錯效果，減少了互連故障的影響范圍，提高了系統的可維性和可用性。

1 相關工作

目前在高性能計算的互連領域，主要存在著以Ethernet為代表的通用網絡和以InfiniBand為代表的專用網絡兩大類。Ethernet是采用簡單網絡管理協議(Simple Network Management Protocol，SNMP)來實現網絡管理，該協議是J．D．Case等在1990年提出的，通過網絡端口之間周期性地發送雙向轉發檢測(Bidirectional Forwarding Detection，BFD)報文來檢查端口狀態，若幾個周期之內沒有收到對端報文，則認為該端口處于“Down”狀態，然后規避該端口，并重新發現網絡拓撲［3］。而InfiniBand則增加了一層子網管理層，子網管理器通過子網管理代理來感知整個互連網絡的狀態，當發生互連故障時，子網管理器將啟動拓撲發現，并根據當前的互連拓撲重新計算并配置路由表［4］。

當前，互連網絡的容錯研究已成為高性能互連網絡領域亟需解決的熱點問題之一，具有很高的實用價值。互連網絡容錯的硬件基礎是源節點到目的節點有多條路徑冗余，而Butterfly等拓撲只有單一路徑，通常需要通過增加鏈路或者交換機來提供容錯能力［5－6］，這種方法實現簡單，但增加了硬件開銷。誤路由(misrouting)是另一種常被使用的路由容錯方法，該方法使用更長的路徑來避開互連故障［7］，增加了數據的傳輸延遲。文獻［8］將以上兩種容錯方法相結合，提出了一種混合容錯方法，該方法可以獲得更好的容錯性能，但同時增加了硬件代價和數據傳輸延遲。

胖樹拓撲是當前高性能計算中使用較多的一種拓撲結構，該結構在源節點和目的節點之間有多條通信路徑，具有良好的互連容錯支持能力，為動態路由容錯方法的實現提供了基礎。文獻［9］提出了一種由并行胖樹構成并且對應交換機由鏈路相連的拓撲以實現容錯。該方法具有良好的靜態容錯性能，但在動態容錯的情況下只能容忍一條故障鏈路。文獻［10］提出在胖樹中通過局部誤路由的方式實現動態容錯，該方法增加了數據的路徑長度，增加了網絡延時。文獻［11］采用了包含排除區間的區間路由方法來實現胖樹動態容錯，該方法的缺點是健康路徑可能被犧牲。文獻［12］采用集中式的網絡管理來維護網絡配置、監測鏈路狀態、傳播網絡失效和路由信息，以實現胖樹中的動態容錯。該方法具有很好的靈活性，但由于管理節點需要和網絡中的所有交換機相連并通信，其系統的擴展性受到很大的限制。文獻［13］針對采用源路由的胖樹網絡，提出了一種端節點動態容錯路由實現方法，相較于分布式路由，其擴展能力有限。文獻［14］則提出了一種分布式動態容錯路由方法，通過引入了鏈路失效消息傳播機制和動態容錯路由算法來實現胖樹網絡的分布式動態容錯，該方法的優點是無需增加硬件代價和路徑長度，但該方法只是停留于理論研究，并未實際應用。

2 高維胖樹系統及其優越性

構建高性能計算(High Performance Computing，HPC)系統時首當其沖需要考慮的問題是系統采用何種拓撲結構。縱觀新一屆TOP500(June，2017)榜單中排名前十的系統，除排名第一的“Sunway TaihuLight”采用了商用的Mellanox InfiniBand互連外，其余9臺系統均采用了定制的互連系統。根據系統所采用的拓撲結構可將TOP10的系統分為以下三類:第一類是以“Sequoia”“Mira”和“K computer”為代表的 K-Ary N-Cube拓撲結構;第二類是“Piz Daint”“Cori”“Trinity”三臺 Cray XC系統所采用的Dragonfly拓撲結構;第三類則是以“Tianhe-2”為代表的Fat Tree拓撲結構。

K-Ary N-Bridge是近年來涌現出了一種新型的拓撲結構，該拓撲綜合了K-Ary N-Cube和Fat Tree拓撲各自的優點，因而展現出了更好的可擴展性和網絡性能，目前該拓撲已在實際系統中得到了應用。在介紹K-Ary N-Bridge拓撲前，本文將首先對K-Ary N-Cube和Fat Tree拓撲進行簡單的介紹。

2．1 K-Ary N-Cube拓撲

K-Ary N-Cube拓撲，又稱為N維Torus。K-Ary N-Cube是由K個K-Ary(N－1)-Cube網絡通過連接第N維來構成。標準的K-Ary N-Cube拓撲中包含KN個節點，網絡中總的鏈路數為N×KN，網絡直徑為KN/2，在網絡流量均勻分布的模式下，每個報文的平均跳步數為 KN/4，網絡的二分鏈路數4KN－1。8-Ary 1-Cube和8-Ary 2-Cube拓撲結構分別如圖1(a)和1(b)所示。

圖1 K-Ary N-Cube拓撲Fig．1 K-Ary N-Cube topology

2．2 Fat Tree拓撲

Fat Tree拓撲是高性能計算系統中一種常用拓撲結構，其基本結構如圖2所示。對N層Fat Tree而言:其最多可連接2(K/2)N個節點;最大跳步數為2N－1;二分帶寬為2(K/2)N。

2．3 K-Ary N-Bridge拓撲的定義

在高階路由器的支持下，可以考慮將Torus網絡中每維的所有節點通過一個高階路由器進行連接，即成了一個K-Ary 1-Bridge拓撲，如圖3(a)所示。再將K-Ary 1-Bridge拓撲往高維擴展，就形成了K-Ary N-Bridge拓撲，從而有效減少網絡跳步數和降低網絡延遲。K-Ary N-Bridge拓撲由兩類交換機構成，其中直接與節點相連的交換機稱為葉交換機，連接不同葉交換機的交換機稱為根交換機，其規模為KN－1×KN－2×… ×Ki×… ×K1×K0，其中Ki表示第i維上葉交換機的數量，i∈{0，1，…，N－1}。葉交換機連接每個維度的端口數均為Q，則其總的上行端口數為N×Q;在每個維度上，葉交換機分別與Q個根交換機相連，形成Q-port上行、Ki-port下行的非標準胖樹結構，該維度上的根交換機稱為i維根交換機。葉交換機用LSW(jN－1，jN－2，…，j1，j0) 表示，其中 ji∈{0，1，…，Ki－1}，ji標示葉交換機在陣列中所處的位置。第i維根交換機為RSW(i，jN－1，…，jm，…，ji+1，ji－1，…，j0，p)，其中 jm∈ {0，1，…，Km－1}，p∈{0，1，…，Q －1}，i表示根交換機所在維度，jm表示第i維根交換機所在的位置，p表示交換機的編號。特別地當N=2時，如圖3(b)所示，用RSW(0，k)表示0維中第k個根交換機，RSW(1，k)表示1維中第 k個根交換機，用LSW(i，j)表示葉交換機在二維陣列中的坐標。

圖2 兩級胖樹拓撲Fig．2 2-level fat tree topology

圖3 高維胖樹拓撲Fig．3 K-Ary N-Bridge topology

2．4 K-Ary N-Bridge拓撲的優越性

與K-Ary N-Cube拓撲結構相比，K-Ary N-Bridge結構具有以下三點優勢:

1)可擴展性更高:K-Ary N-Bridge網絡可以方便地擴展網絡規模。當節點的端口數和路由器的端口數固定時，仍可以通過用交換機替換維度上的路由器方式來擴展網絡規模。如假設路由器設計為K個端口，使用若干個路由器構成2K個端口的交換機，替代K-Ary N-Bridge中的路由器來構造網絡，即可構建更大規模的網絡。

2)網絡直徑更小:同等規模下，K-Ary N-Bridge拓撲的跳步數僅為2N;而K-Ary N-Cube拓撲的跳步數則為KN/4;顯然K-Ary N-Bridge拓撲可以獲得更小的網絡延遲。

3)網絡性能更高:在同等規模下，當K≥8時，K-Ary N-Cube網絡的吞吐率將會下降;而K-Ary N-Bridge拓撲由于使用類似樹形的結構，網絡吞吐率不會隨K的增大而下降，因而可以獲得更高的網絡性能。

而相較于Fat Tree拓撲結構，K-Ary N-Bridge結構具有以下兩點優勢:

1)K-Ary N-Bridge拓撲使用單個路由器來連接單個維度上的所有節點，完全擺脫高密度交換機的設計限制，可構建大規模的互連網絡。而Fat Tree網絡則嚴重依賴高密度的交換機來擴展規模;

2)二分帶寬與Fat Tree網絡相當，而且隨網絡規模線性增長。

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

互連故障是高性能計算機中一類重要的故障。與節點故障不同的是，單條鏈路或單個交換機故障往往會影響多個甚至全系統所有節點間的通信。在高維胖樹系統中常見的互連故障包括鏈路故障、交換芯片故障和交換機故障三大類。

其中，鏈路故障可根據其嚴重程度分為連通性故障和穩定性故障。當出現連通性故障時，報文無法將通過該鏈路;當出現穩定性故障時，報文可以通過多次重傳，到達對端交換機，但會影響報文的傳輸效率。根據實際經驗，鏈路的穩定性故障若不得到及時的處理往往會惡化成鏈路的連通性故障。

交換芯片和交換機故障通常表現為掉電，若交換芯片或交換機的上電復位電路發生故障，則有可能引發交換芯片或交換機故障。若發生此類故障，則會導致通過該交換芯片或交換機所有節點或服務器的通信受阻。按照交換機的位置可以分為葉交換機和根交換機故障，其中根交換機故障僅會影響其所在維的通信，而葉交換機故障則會影響該葉交換機所在位置上不同維度間葉交換機的通信。以圖4中二維胖樹為例，當葉交換機LSW(i，j)發生故障時，葉交換機LSW(a，j)與LSW(i，b)間的節點通信均會受阻，其中0≤a≤K1－1，0≤b≤K0－1(在圖中用實線框表示)，由于葉交換機故障影響范圍大，是高維胖樹拓撲中所特有的互連故障類型，因此本文將重點研究此類互連故障的路由容錯策略。

圖4 二維胖樹拓撲中的葉交換機故障Fig．4 Leaf switch fault in K-Ary 2-Bridge topology

4 高維胖樹系統的路由容錯策略設計與實現

當交換芯片發生故障時，由于無法更換單個交換芯片，通常需要將芯片所在的交換機斷電后更換，因此在日常的互連維護中，可將交換芯片故障視同于交換機故障來處理。對于鏈路故障和根交換機的故障，其影響范圍及路由容錯策略與標準胖樹拓撲基本相同，在文獻［1］中已有詳盡的描述，本文將僅作簡要介紹。而葉交換機由于涉及不同維度之間的通信，屬于高維胖樹拓撲中所特有的故障類型，需要設計新的路由容錯方案。

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

圖5 葉交換機容錯原理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 驗證實驗

由于高維胖樹拓撲中鏈路故障(包括上行鏈路與下行鏈路)和根交換機故障的路由容錯策略與標準胖樹拓撲中的路由容錯策略基本相同，且文獻［1］中已有詳盡的說明以及實驗驗證，本文僅對葉交換機的路由容錯策略進行驗證。

本次實驗在一個實際的HPC系統上進行，該系統采用了33×6的二維胖樹拓撲。葉交換機的路由容錯策略通過Shell腳本實現(config_err_board．sh)，該腳本有兩個輸入參數，第一個參數為交換機的坐標信息，第二個參數表示屏蔽(error)還是恢復(renew)該葉交換機，如圖6(d)和6(e)所示。實驗使用了AlltoAll通信測試程序來檢測節點列表內所有節點間的連通性，該程序的通信模式為節點集合內每一個節點周期性地向其他節點發送一定規模的測試數據塊，同時該節點周期性地接收來自其他節點的數據塊。實驗步驟如下:

1)選定葉交換機LSW(13，2)為目標葉交換機，選取與葉交換機 LSW(a，2) 與 LSW(13，b)，(其中0≤ a≤32，a≠13，0≤b≤5，b≠2)相連的節點為節點列表，運行AlltoAll通信測試程序，結果如圖6(a)所示。

2)假設互連監控軟件檢測到葉交換機LSW(13，2)發生了故障，此時通過路由容錯腳本來屏蔽該葉交換機，如圖6(d)所示。

3)對葉交換機LSW(13，2)進行切電，AlltoAll通信測試程序仍可正常運行，如圖6(b)所示。

4)運行一段時間后，重新對目標葉交換機加電后再利用路由容錯腳本來恢復該葉交換機，如圖6(e)所示。

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

6)由容錯原理可知，配置容錯路由后，跳步數增加了4跳，經測試發現配置前的平均延遲為4．98 μs，而配置容錯路由后，平均延遲為 5．47 μs，增加了 0．49 μs;點點帶寬在配置前后基本保持不變。

圖6 葉交換機屏蔽和恢復實驗Fig．6 Shield and recover experiments for leaf switch fault

實驗表明，針對葉交換機的路由容錯策略達到預期目標，可以快速實現對目標葉交換機的屏蔽與恢復。目前，該路由容錯策略已應用于實際系統的日常運維中，取得了良好的容錯效果。

6 結語

本文研究了高維胖樹這一新型拓撲中互連故障的類型及其故障影響范圍，鑒于高維胖樹拓撲中葉交換機故障影響范圍大這一特點，采用誤路由的思想，設計了針對此類故障的路由容錯策略。實驗表明，利用該路由容錯策略可以有效減少葉交換機故障在系統中的影響范圍，便于運維人員及時更換和維修葉交換機。目前，本文所提出的路由容錯策略已用于實際系統的運維并達到了快速屏蔽故障葉交換的預期效果。下一步工作計劃將該路由容錯策略集成到自主研發的互連監控軟件中，使得高維胖樹系統中互連故障的監測和屏蔽完全自動化。