針對可擴展交換網絡的頑健性評價方法

楊光輝，吳建平，趙有健，孫書韜

(1. 清華大學 計算機科學與技術系，北京 100084；2. 中國傳媒大學 計算機學院，北京 100024)

1 引言

隨著規模和用戶持續高速增長，互聯網已經演變成為一個全球性通用網絡。互聯網技術也因受到需求的驅動得到了長足的發展，各種應運而生的新型業務和協議已經在互聯網中大規模的部署。互聯網中的流量正以指數級別的速率增長。這些狀況對互聯網核心路由器提出了許多新的要求，包括提供更多更高速的端口設備以及更大的交換容量等。目前互聯網的核心路由器一般采用集中式體系結構。這種體系結構雖然便于對需要轉發的數據流量進行調度，但限制了路由器交換容量的擴展以及端口的數量增長[1]。為了解決這一問題，基于分布式體系結構的可擴展路由器被提出并得到越來越多的關注和研究[2]。

交換網絡是路由器的關鍵部件。目前大多數商用路由器中，交換網絡被設計為固定專用部件，擴展性較差。例如，共享總線交換結構中各個端口所共享的總線帶寬是擴展的瓶頸。基于交叉開關（crossbar）的交換結構的擴展受到crossbar規模限制，擴展代價較大，接近于O(N2)級別（N為交換結構的端口數量）。交換網絡的擴展性直接決定了路由器的擴展性，具備較好規模擴展能力的交換網絡稱為可擴展交換網絡。可擴展交換網絡可以分為多級互連網絡[3,4]（MIN, multistage interconnection network）、直連交換網絡[5～7]（DN, direct switch network）、以及混合交換網絡[8]。由于混合交換網絡結構復雜，在路由器實際設計中少有采用，因此在本文中可擴展交換網絡特指MIN和DN 2類。

無論MIN或DN都可抽象為連接圖。連接圖是將一定數量的節點（交換單元）通過邊（鏈路）連接起來的抽象圖。下文中將邊和節點視為連接圖的組件。MIN抽象圖和 DN抽象圖存在一定區別。MIN抽象圖中的節點可以分為2類：一類為輸入/輸出端口節點（簡稱端口節點），另一類為交換單元節點。外部數據流量通過輸入端口節點注入路由器交換網絡，再通過交換單元節點轉發到輸出端口節點。與MIN抽象圖不同，DN抽象圖中的每個節點既是端口節點，又是交換單元節點。DN節點可以接收目的是本節點的數據流量，也可將目的是其他節點的數據流量根據策略進行轉發。隨著組件數量的不斷增大，整個交換網絡的聯合故障概率必然會隨著規模擴展而不斷變大。因此可擴展交換網絡的設計必須考慮可能發生的組件故障對交換網絡的影響。

故障對網絡的影響一般采用基于頑健性的評價指標。對于一個網絡，頑健性是當部分網絡拓撲組件發生故障后，該網絡保持基本功能的能力。根據基本功能的不同，頑健性評價方法可以分為2類[9]：一類方法的評價指標關注圖的連通性，另一類的評價指標關注節點間距離的變化。可擴展交換網絡的拓撲不僅可以決定一個交換網絡的吞吐率、延遲等性能的上限，其頑健性也直接決定著可擴展路由器可靠性[10]。因此，合適的評價方法可以區別出不同可擴展交換網絡頑健性差別，這對于可擴展交換網絡的設計具有重要意義。

MIN類可擴展交換網絡的頑健性適宜采用基于連通性指標的評價方法；DN類可擴展交換網絡的頑健性則更適合采用基于距離指標的評價方法。目前研究中基于距離的評價指標多采用直徑以及直徑變化[11]等全局信息，這些指標應用于DN的頑健性評價存在以下問題：第一，直徑類評價方法不能在少數組件隨機發生故障的情況下對DN進行頑健性評價；第二，現有評價方法的算法復雜度較高。可擴展交換網絡的頑健性評估需要根據評估的規模重復運行評估算法，此時評價方法的復雜度問題尤其突出。

本文內容安排如下。第2節中研究可擴展交換網絡的拓撲特點以及隨機故障模型，并建立模型比較DN在不同故障模型下的頑健性差別。提出一種新的基于故障影響（failure influence）的頑健性評價方法，故障影響包含的2種評價指標:故障影響范圍（FIS, failure influence scope）和故障影響強度（FII,failure influence intensity）。第3節提出故障評價方法的優化算法。第4節分析和對比一些主流可擴展交換網絡的故障影響屬性。第5節是結束語。

2 針對可擴展直連網絡故障影響的頑健性評價方法

失效、故障和錯誤的概念在容錯計算領域中有著詳細的區分。失效是指各種物理現象，如鏈路中的高斯噪聲、導體中的電子遷移、供電系統異常等現象。故障是失效的表現形式[12]，如供電異常（失效）導致某寄存器無法保存數據，則這種行為定義為寄存器故障。這個故障致使計算機無法使用該寄存器導致計算結果偏離正常，最終表現為計算機錯誤。本文的研究主要針對組件層面（交換節點、鏈路等），以下統一采用故障進行表述。針對可擴展交換網絡的頑健性評估方法必須考慮2個問題：首先，評價方法必須基于可擴展交換網絡的應用場景；其次，評價方法必須可以區別不同可擴展交換網絡頑健性的差別。

2.1 可擴展直連交換網絡頑健性評價的需求分析

2.1.1 隨機故障模型

故障模型對故障產生的類型、故障持續的長短和故障在系統中的分布以及系統中設備出現故障所服從的統計規律等進行具體的規定[13]。可擴展交換網絡在運行過程中可能產生多種故障，例如硬件故障，軟件運行時出現的漏洞導致的異常，流量導致的緩存溢出異常等。這些來源不同的故障從抽象圖的角度可以歸納為節點故障、邊故障、混合故障（邊故障和節點故障同時存在）。根據故障持續時間可以劃分為瞬態故障、永久故障、間歇型故障等。如果在故障產生后不能利用設備的冗余資源進行恢復，那么值守人員對該故障進行人工恢復的時間一般為小時級別甚至更長，這種故障定義為永久故障。

2類最常使用的故障模型包括界限模型（bounded model）和概率模型（probabilistic model）[14]。界限模型設定了發生故障的節點/邊的上界值，以最壞情況進行分析。概率模型中故障的發生概率是隨機且相互獨立的。本文針對的隨機故障模型屬于概率模型。在隨機故障模型中假設基于嚴格正交拓撲的可擴展交換網絡抽象圖中的節點或邊發生故障的概率是相同的，并且各個節點或邊的故障概率相互獨立。隨機故障模型常用于可擴展交換網絡的頑健性研究中[9]。系統的一次隨機故障記為f(i)，其中，i為故障組件的數量。根據發生故障的組件不同，隨機故障模型又可分為隨機節點故障模型（記為fv(i)）、隨機邊故障模型（記為fe(i)）、隨機混合故障模型（記為fh(i)）。隨著微電子技術的進步以及路由器的廣泛應用，路由設備專用芯片已經非常成熟，多個組件同一時刻發生故障的概率非常小。因此，小規模的組件同時發生故障的情況在可擴展交換網絡隨機故障模型中占主要地位。

2.1.2 DN和MIN頑健性評價方法的區別

將DN和MIN抽象為連接圖，二者最大的不同在于DN的交換單元和輸入輸出端口結合并采用嚴格正交拓撲連接，而 MIN的輸入輸出端口則分離且其交換單元以分級方式連接。DN和MIN在頑健性方面也有明顯的差別。以24節點Benes（MIN，圖1(a))和25節點2D-Torus (DN，圖1(b))為例。該Benes網絡的交換單元節點分為6級，每一個輸入輸出端口對之間都存在多條路徑。例如，如果有數據分組需要從C0(6)轉發到C6(7)，圖1(a)存在8條路徑可選。如果節點G1(2)發生故障（在圖1(a)中以矩形陰影表示），那么仍有其他長度為 6的路徑可選。對于MIN，只要輸入輸出端口對是可達的，從源到目的節點的路徑長度將不受影響。因此，基于連通指標的評價方法相比于基于路徑長度指標的頑健性評價方法更適用于MIN。通過觀察易得，DN的任意端口對間的路徑數目遠大于MIN，這使得少量的故障很難對DN的連通性產生影響。但由于路徑長度是不等的，因此基于路徑長度指標的頑健性評價方法更適宜于DN。

基于連通性指標的頑健性評價方法的研究成果較多，例如文獻[8,15]中提出了適用于MIN的連通性評價指標。而基于路徑長度指標的頑健性評價方法較少，下文將分析現有基于路徑長度指標是否適用于可擴展交換網絡的頑健性評價。網絡的頑健性依賴于故障模型，不同故障模型會對網絡的頑健性產生不同的影響。根據本文的調研，現有文獻中較少結合隨機故障模型對DN進行頑健性分析。下文將通過定義和證明來分析DN在隨機故障模型下的頑健性。

定義1 在圖G(V,E)中，V為節點集合，E為邊的集合。圖G(V,E)的K子集定義為G中任意的K個節點，且K個節點之間有邊連接，亦稱為G的K子圖。Vk是G中非K子集節點且與K子集的節點有邊連接的節點數目，亦稱為K子集的鄰居節點數。Sk是G中K子集的總數。如果G中所有節點的度等于δ，且滿足對任意1＜K＜N/2存在VK-δ≥2，那么圖G稱為一個δ-規則圖。

定義2 圖G為非連通圖當且僅當圖中存在子集被從G中隔離開。其中幾種事件的概率如下。

P(i)：圖G中發生i個組件故障后變成非連通圖的概率。

Q(i)：在i-1個故障時是連通圖，然后移除一個節點后，變為非連通圖的概率。

Qk(i)：圖G在i-1個故障時是連通圖，產生任意一個節點故障，在i個故障后從G中隔離出一個K子圖概率。

上述幾種概率滿足以下 2個關系：①P(i)=，這個公式的含義是在發生第i個故障后變為非連通圖的概率等于發生1到i-1個故障都不會變成非連通圖的概率和第i個故障后正好變成非連通圖概率的乘積。這個公式的含義是在第i個故障后變為非連通圖的概率等于在第i個故障后隔離出所有可能的K子圖概率之和，其中，Max代表在i故障下K子圖所有可能值。

圖1 以Benes網和2D-Torus網舉例說明MIN和DN

分別記只有節點發生隨機故障、只有邊發生隨機故障以及邊和節點都發生隨機故障的C(G)為Cv(G)、Ce(G)以及Ch(G)。假設圖G的節點數N遠大于δ，首先分析Cv(G)。在只有節點發生隨機故障時，在N遠大于δ的假設下，利用斯特林公式對上式中的階乘進行化簡。可以得出從定義2分析可以得出：Sk是O(N)級別的數，而Vk是O(δ)級別的數，可以推出Sk遠大于Vk。當K＞1時，可得：

由定義2可知，VK-δ≥2，且N遠大于δ，將式(1)代入Cv(G)可以得到：

根據式(1)可知，在隨機節點故障模型下Cv(G)隨著N增大而增大，G的連通性也隨之增強。因此，隨著規模增大，連通性指標對于δ-規則圖的評價效果逐漸變差。下面的分析主要針對Ce(G)和Ch(G)，化簡中用到的技巧與式(1)的推導過程類似，為了節省篇幅，下文中簡要給出Ce(G)和Ch(G)的分析過程。

Ce(G)推導中采用隨機邊故障模型，因此式(2)中加入組合數CδNδ，表示從所有的Nδ個邊中選取δ個邊，代表單個節點被隔離的情況。K子圖被隔離的情況與式(1)中表述相同。應用VK-δ≥2和N遠大于δ，易得出。采用類似式(1)的化簡過程，將式(2)代入Ce(G)中，可以得出Ce(G) ＞Cv(G) ＞N。

在混合故障模型下產生故障的組件既有節點也有邊。式(4)表示l個邊故障，其中，通過組合數之間的比較很容易得出式(5)，在此不再做詳細的證明。

考慮到混合隨機故障模型的定義，其中，故障應包含所有邊故障和節點故障的組合，則由式(4)和式(5)可得式(6)。

結合式(4)和式(5)，利用和推導式(2)相同的化簡方法，可得Cv(G)＜Ch(G)＜Ce(G)。根據式(2)、式(4)和式(6)可以得出：無論在隨機邊故障模型、隨機節點故障模型還是隨機混合故障模型，上述證明說明隨機節點故障模型對頑健性的影響最大，隨機混合故障模型次之，隨機邊故障模型對δ-規則圖的頑健性影響最小。這說明圖的頑健性研究只需基于隨機節點故障模型和隨機邊故障模型，這2種模型下的頑健性評價效果將是混合故障模型下評價效果的上下界。

2.1.3 現有評價尺度對于DN的不足

在節點規模相同情況下，MIN任意輸入輸出端口對間的路徑數量遠小于 DN。采用已有文獻[8,15]提出的評價方法，例如網絡可靠性、終端可靠性和廣播可靠性等基于連通指標的頑健性評價方法能夠很好地對MIN類的網絡進行評價。已有研究中針對 DN的頑健性評價一般采用直徑類指標。直徑為圖G中任意節點對之間距離的最大值。直徑類指標的評價效果依賴于故障模型。在以一定故障數來產生最大破壞能力的界限模型下，直徑類指標能夠較好顯示出頑健性的變化[11]。但如果在隨機故障模型下，直徑類指標并不能對δ-規則圖進行有效的頑健性評價。

以2種典型的DN即2D-Torus和3D-Torus為例，在隨機故障模型下驗證直徑增量指標的評價效果。由 2.1.2節的證明可知混合故障模型的頑健性處于隨機節點故障模型和隨機邊故障模型之間，因此只選擇后2種故障模型進行研究。圖2(a)和圖2(b)分別說明了2D-Torus在隨機邊故障模型和隨機節點模型下直徑的變化。在節點規模達到100的時候，直徑隨著故障數量增加的變化非常小。這種趨勢在3D-Torus上更加明顯（如圖2(c)和圖2(d)所示）直徑變化趨勢已經成為水平直線。上述實驗結果表明直徑類指標無法對DN進行頑健性評價。因此必需在隨機故障模型下設計一種有效的DN頑健性評價方法。

2.2 基于故障影響頑健性評價方法

2.2.1 故障影響評價方法的設計動機

目前，研究和應用較多的DN包括n維全連接網絡、鏈形網絡、回環網絡(torus)和超立方網絡等。DN一般采用嚴格正交拓撲，原因在于：首先，當網絡規模持續增大時，嚴格正交拓撲易于保持固有的良好屬性。其次，統一設備規格可以使制造、維護以及更新設備的成本大大降低。少量故障對 DN造成大規模節點被隔離的概率非常低。更可能的情況是，少量組件故障只是某些節點對間的最短路徑長度增加，這類似于一場地震。地震會對地面建筑或人員造成較大的破壞，距離震中越近的區域這種破壞效果越明顯。地震可以用等震線在地圖中表示，這種方法可以較為清晰地顯示一場地震的破壞力及其影響范圍。

借鑒地震破壞力的評價方法，本文針對基于DN的可擴展交換網絡提出了一種新的頑健性評價方法，命名為故障影響。這種方法較直徑類的評價方法不同之處在于評價指標的選取。直徑類指標關注于發生故障后圖的某種全局特征的變化。但少量組件故障很可能難以導致全局特征的變化。故障影響評價方法將故障抽象視為震中，并評價該故障對于整個網絡產生的破壞力。與震級和等震線的概念類似，故障影響包含2種不同評價指標：故障影響強度(FII, fault influence intensity)和故障影響范圍(FIS, fault influence scope)。下文將對故障影響的評價指標進行描述。

圖2 多種規模Torus網絡在隨機故障下的直徑變化趨勢

2.2.2 故障影響評價方法的基本定義

針對隨機故障模型，在文中采用fe(G,k)代表圖G中同時產生故障的k個邊。同理，fv(G,k)代表圖G中同時產生故障的k個節點，fh(G,k)代表圖G中同時產生故障的k個節點或邊，f(G,k)代表圖G中同時產生的k個任意來源故障。在δ-規則圖G(V,E)中，當發生一次k規模故障f(G,k)后，G′為從G移去故障節點和邊后的圖。

定義3 節點的級和邊的級。在δ-規則圖G(V,E)中，任選一個節點v0作為起始節點，v0的級定義為 0，記為Nl(v0)=0。假設vi(i≠0,vi∈V)距離v0的最短路徑長度為k，則vi的級為k，記為Nl(vk)=k。圖G(V,E)中所有級為k的節點組成的集合記為。G(V,E)中的va和vb之間如果存在一條邊，那么這條邊記為eab，eab的級記為El(eab)，El(eab)=max(Nl(va),Nl(vb))。所有級為l的邊組成的邊的集合記為圖1(c)以虛線框標識了

定義4 最短路徑長度矩陣 (OM, one to all shortest path matrix)。在δ-規則圖G(V,E)中，節點vi到G中其余所有節點vj(i≠j,vj∈V)的最短路徑的長度值形成N-1個元素的一維向量，記為OM(G,vi)。假設當G(V,E)中產生故障f(G,k)后拓撲變為圖G'(V',E')，對于vi(vi∈V，vi∈V)，如OM(G,vi)≠OM(G′,vi)，則vi定義為G中被故障f(G,k)影響的節點。其中，OM(G,vi)和OM(G',vi)只比較vi到正常節點的距離變化。

定義5 在δ-規則圖G(V，E)中，當發生一次k規模故障f(G,k)后，G的拓撲變為G'。G'中被故障f(G,k)影響的節點的最大數量稱為f(G,k)的故障影響范圍，記為FFIS(f(G,k))。

定義6'

G中被故障f(G,k)影響的節點集合記為對于為2個N-1個元素的一維矩陣差值中的最大值，記為Mmax(G′,vi)。其中，OM(G,vi)和OM(G′,vi)只比較vi到正常節點的距離變化。FFII(f(G,k) )的值為

以圖3為例，節點15在某一時刻產生了故障，即fv(G,1)={15}。由于節點的規模較小，通過觀察就可以得出在其余節點中，節點最短路徑長度矩陣發生變化的節點是{v4,v7,v8,v9,v14}。根據定義5，FIS(fv(G，1))=5。{v4,v7,v8,v9,v14}這些受影響點的Mmax(G',vi)值則分別為{1,1,1,1,1}。因此FFII(f(G,k) ) = 1 。

圖3 網絡故障

2.2.3 評價方法的算法簡化

圖的頑健性評價算法一般具有很高的復雜度，其中，大部分評估算法都不具備多項式級別的評估算法。如 Minimumm-Degree[16]、Fragmentation[17]、Persistence[18]等評價估算法，在文獻[9]中已經歸納并證明了多數頑健性評價尺度的評估算法是 NP-hard難度。在實際的網絡運營環境中，運營商會根據需要變更可擴展路由器的規模。規模擴展的靈活性要求頑健性評價方法應能評價頑健性隨規模變化的趨勢，這需要對可能應用到的規模都運行評價算法進行頑健性分析，此時算法復雜度的重要性更加凸顯。因此，簡化評價算法復雜性非常重要。

FIS和FII都是基于距離的評價指標。如果基于經典最短距離算法Dijsktra，節點的OM算法的復雜度應為O(N4)。考慮所有可能的節點規模，OM算法的復雜度增加為O(N5)。FIS和 FII都是針對δ-規則圖設計的。文獻[11]證明，在一個嚴格正交的網絡中，故障對其鄰居節點集合(記為VN(f(G,k)))的連通性產生最大的影響。這個結論可以應用于簡化FII，如式(7)所示。假設VN(f(G,k))＜＜N，FII的評價算法的復雜度可以降低為O(N4)。

3 直連交換網絡的故障影響分析

3.1 幾種流行的直連網絡

常用的流行直連交換網絡包括：環型拓撲、星型拓撲、立方體型（cubes）、回環圖型等。首先對結構相對簡單的環型和回環型拓撲進行隨機單故障模型的故障影響分析。從定義1可以得出，雖然環型拓撲是點對稱的，但因為VK-δ＜0，所以環型不屬于δ-規則圖。環型和回環型的故障影響分析由于其拓撲特征而具有相似性，環型拓撲或回環拓撲中的環可以按照節點個數的奇偶性分為2類：偶環和奇環。通過觀察和歸納易得出環的邊故障影響范圍。為節省篇幅，下文直接給環型和回環型的單邊故障影響的研究結果，如表1所示。

表1 環型拓撲和回環型拓撲的FIS和FII屬性

文獻[19]對嚴格正交拓撲進行分析后得出結論：在嚴格正交連接網絡中，如果節點的度固定且內部鏈路帶寬固定，則其吞吐率將隨節點規模增大而最終下降。這個結論說明，如果要實現理論意義上的規模無限可擴展，節點度必然需要隨著節點規模擴大而增長，否則內部帶寬將成為吞吐率增長瓶頸；另一方面，節點的度不能過大，否則將導致擴展成本增大。為了平衡這對矛盾，本文前期工作在文獻[1]中提出了漸進最小度擴展的可擴展交換網絡P2i。P2i具有直徑小、靈活擴展粒度、等分帶寬較大等優點。

3.2 P2i的故障影響分析

3.2.1 拓撲概述

P2i可以抽象為連接圖G=(V,E)。設N為節點的總數，所有節點從0至N-1編號。編號v的節點擁有條入邊。節點v的各條出邊依次稱為0維邊至1δ-維邊。i維邊（記為i-dim）連接編號為(v+2i)modN的節點。1δ-維邊亦記為HD邊，其余出邊記為non-HD邊。圖4為8節點和9節點的P2i。

定義7 跨度(span)：在一個N節點的P2i中，如果在va和vb之間存在一條邊eab，則eab的跨度記為dspan(eab)，且dspan(eab)=((b-a)+N)modN。va和vb間如存在一條最短路徑P，則va和vb的跨度記為dspan(va,vb)，并且

定義8 在N節點的P2i中，va和vb之間的最短路徑如果只包含non-HD邊，那么這種最短路徑記為NHSP。如果只包含HD邊，那么這類最短路徑記為 HDSP。如果最短路徑中既有 HD邊又有non-HD邊，則記為HYSP。HYSP的路徑長度應大于等于2。如果va和vb間存在多于2條的最短路徑，那么這些路徑互相稱為對稱路徑。

圖4 一個8節點P2i和一個9節點P2i

3.2.2 P2i故障影響的相關結論

結論1 任取一個N節點的P2i中的節點v0，從v0到其他節點的一條最短路徑中，跨度為2i(i＜δ-1)的邊最多只能包含一次。

結論 2 可以通過反證法來證明。當路徑長度為1的時候，結論顯然成立。跨度為2i(i＜δ-1)的邊屬于non-HD。當路徑長度大于2的時候，如果跨度為2i(i＜δ-1)的邊出現了2次，則必然能找到一條跨度為dspan((i+1)-dim)=2，dspan(i-dim)的i+1維邊將代替兩條i維邊，形成一條新的最短路徑P'，并且P'的路徑長度小于P，則P為最短路徑的假設不成立。據此，結論1得證。

結論3 在一個N節點P2i中，假設從va到vb存在一條路徑長度大于1的最短路徑P，并且P是NHSP或者HYSP中的任一種，則P必然存在一條對稱路徑P'，并且P'和P是邊不相交的。

在一個N節點規模的P2i中的最短路徑，如圖4(a)的 8節點 P2i中，從v0到v3的一條最短路徑v0→v2→v3，這條路徑可以用一個節點序列表示為(v0,v2,v3)，也可以表示為一個邊的序列(e0,2,e2,3)或者一個跨度值的序列(1,0)。如果P為NHSP并且P的路徑長度大于1，則跨度值序列至少有2個位置的元素必然是不同的。在上述例子中跨度值的序列(1,0)，必然還存在著另外一種跨度值的序列(0,1)。路徑長度越大，跨度值的排列越多，這意味著對稱路徑的數量也就越多。由于跨度值排列數不同，則節點序列不同，因此邊的序列也是不相同的，即為邊不相交的。結論2得證。

結論4 在一個N節點P2i中，non-HD的隨機單邊故障的故障影響范圍為1，P2i的隨機單邊故障的故障影響范圍等于HD邊的單邊隨機故障的影響范圍。

任取一個N節點P2i中的節點v0。在隨機單故障模型下，如果故障發生在v0的1級邊，則OM(v0)必然會改變。如果故障邊為非1級邊，則故障邊可以分為2種：HD邊和non-HD邊。如果故障邊為non-HD邊，根據結論2，OM(v0)不會變化。則non-HD邊在隨機單故障模型下故障影響范圍為 1。如果在故障邊為HD邊的情況下，由于P2i邊的不對稱性，HD邊的故障影響范圍大于等于 1。因此，根據定義6可知P2i的隨機單邊故障的故障影響范圍等于HD邊的故障影響范圍。

結論5 不失一般性，任取一個N節點P2i中的節點v0，HD邊故障只可能會影響到v0到其他節點的HDSP最短路徑的長度。

v0到其他節點的最短路徑中包含HD邊的只可能是HDSP和HYSP二者之一。假設從v0到vb存在一條HYSP最短路徑P。顯然HYSP的路徑長度大于等于2，根據結論2，P存在一條對稱路徑P'，OM(v0)不會改變，因此結論4得證。

3.2.3 P2i故障影響的優化算法

任取一個N節點P2i的節點v0，存在一個正整數k，當HDSP的路徑長度大于或等于k+1時，v0通過這條HDSP路徑連接了vk，則v0到vk必然存在一條長度小于等于k+1的NHSP，k稱為P2i的閾值。根據結論3可知閾值就是P2i在單隨機故障模型下的FIS值。據此只需采用啟發式算法求得P2i中的閾值即可得到該P2i的FIS值。上述啟發式算法可以由以下的偽代碼進行描述。其中，SPF(vs,vd)表示從vs到vd最短路徑的長度，vs,HD表示vs第1δ-維邊所連接的節點。k是一個初始值為0的變量，FIS的初值為0。

4 實驗結果及比較

在第 2節中提到，頑健性評價方法首先必須基于可擴展交換網絡的應用場景；其次，該方法必須可以區別不同可擴展交換網絡的頑健性差別。本節將通過 3個實驗來檢驗故障影響評價方法是否滿足上述2個標準。根據2.1.1節的論述，本節所有實驗都基于隨機故障模型以符合可擴展交換網絡的應用場景。下文首先通過敏感性實驗來檢驗故障影響評價方法是否能在隨機故障模型下對大規模可擴展交換網絡進行頑健性評價。其次，用單故障實驗和相近連接網絡故障屬性實驗來檢驗故障影響評價方法能否區別不同可擴展交換網絡的頑健性差別。

4.1 敏感性實驗結果及分析

實驗采用隨機從所有組件中選取故障組件的方式。為了近似地實現隨機性，實驗中采用隨機故障分布模式。例如，假設節點的隨機故障概率為1%，在1 000個節點規模時，應有10個節點發生故障。隨機從1 000個節點中選取10個節點，稱為一次故障分布模式。第4節所有實驗均隨機選取10 000種故障分布。本節實驗只選取Edge-FIS評價指標對不同種類DN進行分析，目的在于對比故障影響評價指標和直徑類評價指標在少量組件故障下能否敏感反映頑健性的變化。

圖5(a)的實驗分別選擇了27節點（記為3D-27橫坐標采用 log坐標）、125節點、343節點、729節點的3D-Torus。在發生故障的組件逐漸增加的情況下對比直徑的增量和 Edge-FIS指標的變化。圖5(a)中各條虛線為直徑增量評價結果。實驗結果表明，直徑類指標幾乎毫無變化，在圖5(a)中顯示為近似水平直線，顯然無法反映網絡頑健性的變化。相反地，從圖5(a)中可以看出，即使網絡規模增大到 729，故障影響指標的變化依舊明顯。這表明故障影響指標能夠敏感的反映大規模可擴展交換網絡頑健性的變化。

圖5 直徑與故障影響方法的敏感性對比以及不同網絡的故障影響對比

圖5(b)的實驗（橫坐標采用log坐標）采用與圖5(a)相同的故障模型，以3D-Toru和P2i為例，對邊故障影響范圍進行對比。實驗選擇了27、125、343、729節點規模。圖5(b)中各條虛線為P2i各個節點規模下的邊故障影響屬性。即使在發生故障的邊從2逐漸增加到20后，P2i的邊故障影響屬性依然遠優于相應規模的 3D-Torus。尤其值得注意的是，各個規模P2i的邊故障影響屬性(圖5(b)中虛線)密集在一起。這說明即使節點規模擴大后，大規模P2i擁有與小規模P2i近似的邊故障影響屬性。從故障影響指標來看，P2i非常適宜進行規模擴展。

4.2 單故障實驗結果及分析

單故障是指在某一時刻只有一個組件發生故障。這種故障模型在實際應用中較為常見，如對某個節點的維護和升級等情況。由于DN采用嚴格正交拓撲，點對稱特性使得DN的單故障模型等同于隨機單故障模型。在單故障模型下，故障影響評價方法包括單邊故障影響范圍和強度、單節點故障影響范圍和強度等評價指標。本節實驗在DN中選擇了2D-Torus、3D-Torus和P2i 3種典型的網絡，節點規模的最大值設為1 000。

實驗結果如圖 6所示，它們分別給出了不同DN的單邊故障影響范圍、單節點故障影響范圍、單邊故障影響強度、單節點故障影響強度隨節點規模的變化情況。由圖6(a)和圖6(b)可以看出，在單隨機故障模型下，P2i在大多數規模下擁有較3D-Torus更好的單邊故障影響范圍和單節點故障影響范圍屬性，且遠優于2D-Torus。圖6(b)說明，在隨機單節點故障模型下，P2i擁有非常良好的故障影響范圍屬性。這意味著如果P2i規模增加或減少一個節點，對整個交換網絡的影響較小，這種性質非常利于交換網絡進行平滑的規模擴展。3DTorus的故障影響強度屬性遠優于 2D-Torus，且在節點規模小于500的情況下，擁有較P2i更好的單邊故障影響強度屬性和單節點故障影響強度屬性。其原因可能主要源于P2i并非邊對稱結構，某些維度的邊故障在特殊規模下對故障影響強度屬性的影響更大。

4.3 相近連接網絡的故障屬性實驗及分析

P2i和Torus連接和擴展方式不同。Torus的節點度固定，而P2i的節點度隨著規模增大而漸增。通過4.1節和4.2節的實驗可知兩者的故障影響屬性區別明顯。P2i和 Hypercube具有相似的拓撲。它們具有近似的直徑和節點度并且節點度都會隨著規模而變化。本節實驗以這2種相近連接網絡為例，在隨機故障模型下，使用故障影響強度指標FII對這對相似交換網絡進行頑健性評價及對比。

圖6 在單節點和單邊故障下的不同網絡的故障影響屬性對比

表2 P2i和Hypercube的平均邊故障影響（AFII）和最大的邊故障影響（MFII）比較

表3 P2i和Hypercube的平均節點故障影響（AFII）和最大的節點故障影響（MFII）比較

表2和表3是在隨機邊故障和隨機節點故障模型下，64節點和128節點規模的P2i和Hypercube的FII屬性。FII_E和FII_V分別表示發生故障的邊和節點的個數。在隨機故障模型下，FII的最大值和平均值分別記為 MFII、AFII。例如，64節點Hypercube的 MFII和 AFII分別記為 H64-MFII和H64-AFII。類似地，64節點 P2i的相關參數記為P64-AFII和P64-AFII。從表2和表3中的數據可以得出，P2i的 AFII屬性優于 Hypercube，而 MFII屬性較Hypercube差。這種差別可能緣于P2i邊的不對稱特性。P2i各維度的邊跨度不同，0維邊故障的影響強度高于其他維度的邊。如果采用節點度和拓撲直徑的概念，則無法對P2i和Hypercube的頑健性進行區分。而表2和表3的實驗結果則表明，故障影響指標可以有效評價P2i和Hypercube的頑健性的區別。

5 結束語

可擴展交換網絡的頑健性評價是可擴展路由器研究中的一個重要問題。基于DN的嚴格正交網絡具備良好的擴展性并被廣泛應用到可擴展交換網絡的設計中。在隨機故障模型下，現有頑健性評價方法不能有效地對DN頑健性進行評價。本文總結了基于DN的可擴展交換網絡的拓撲特征，將圖論中的頑健性評價方法引入可擴展交換網絡的頑健性評價方法中，提出了基于故障影響的頑健性評價方法。這種方法包括2種評價指標，即故障影響范圍和故障影響強度。實驗和分析表明，在隨機故障模型下，基于故障影響的頑健性評價方法可以有效地對DN的頑健性進行評價，并可以對相似拓撲的頑健性進行區分。

[1] LIU Z, ZHANG X, ZHAO Y,et al. An asymptotically minimal node-degree topology for load-balanced architectures[A]. Proc of the IEEE GLOBECOM 2008[C]. New Orleans: IEEE, 2008. 1-6.

[2] TSE H. Switch fabric design for high performance IP routers: a survey[J]. Journal of Systems Architecture, 2004, 51(10):571-601.

[3] KESLASSY I, CHUANG S, YU K,et al. Scaling internet routers using optics[A]. Proc of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications[C]. Karlsruhe, Germany, ACM, 2003. 189-200.

[4] SUDAN R, MUKAI W. Introduction to the Cisco CRS-1 Carrier Routing System[R]. Cisco Systems California: Cisco Inc, Jan 1994.

[5] DALLY W. Performance analysis ofk-aryn-cube interconnection networks[J]. IEEE Transactions on Computer, 1990, (39): 775-785.

[6] DALLY W. Scalable Switching Fabrics for Internet Routers[R]. Computer Systems Lab, Stanford University: Stanford University and Avici Inc, 1999.

[7] ZHAO Y, YUE Z, WU J. Research on next-generation scalable Routers implemented with H-Torus topology[J]. Journal of Computer Science and Technol, 2008, 23: 684-693.

[8] DUATO J, YALAMANCHILI S, Ni M. Interconnection Networks:An Engineering Approach[M]. San Francisco, USA: Morgan Kaufmann, 2003.

[9] BRANDES U, ERLEBACH T. Network Analysis: Methodological Foundations[M]. New York, USA: Springer-Verlag, 2005.

[10] DALLY W, TOWLES B. Principles and Practices of Interconnection Networks[M]. San Francisco, USA: Morgan Kaufmann, 2003.

[11] KRISHNAMOORTHY V, THULASIRAMAN K, SWAMY M N S.Incremental distance and diameter sequences of a graph: new measures of network performance[J]. IEEE Trans Computer, 1990, 39: 230-237.

[12] GARTNER F C. Fundamentals of fault-tolerant distributed computing in asynchronous environments[J]. ACM Computer Survey, 1999, 31: 1-26.

[13] KOREN I, KRISHNA M. Fault Tolerant Systems[M]. San Francisco,USA: Morgan Kaufmann, 2007.

[14] ZHANG Z P. Fault Tolerant Routing Algorithms of Regular Networks and Reliable Multicast[D]. Changsha: Central South University, 2005.

[15] CHENG X, IBE O C. Reliability of a class of multistage interconnection networks[J]. IEEE Trans Parallel Distribute System, 1992, 3:241-246.

[16] BOESCH F, THOMAS R. On graphs of invulnerable communication nets[J]. IEEE Transactions on Circuits Theory, 1970, 17: 183-192.

[17] TANGMUNARUNKIT H, GOVINDAN R, JAMIN S,et al. Network topologies, power laws, and hierarchy[J]. ACM Sigcomm Computer Communication Review, 2002, 32: 76-76.

[18] BOESCH F T, HARARY F, KABELL J. Graphs as models of communication network vulnerability: connectivity and persistence[J].Networks, 1981, (11): 57-63.

[19] ZHANG X P, LIU Z H, ZHAO Y J,et al. Scalable router[J]. Journal of Software, 2008, 19(6): 1452-1464.