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

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

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

1 引言

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

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

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

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

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

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

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

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

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

2.1.1 隨機故障模型

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

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

2.1.2 DN和MIN頑健性評價方法的區(qū)別

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

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

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

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

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

Q(i)：在i-1個故障時是連通圖，然后移除一個節(jié)點后，變?yōu)榉沁B通圖的概率。

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

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

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

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

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

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

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

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

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

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

2.1.3 現(xiàn)有評價尺度對于DN的不足

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

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

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

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

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

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

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

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

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

定義3 節(jié)點的級和邊的級。在δ-規(guī)則圖G(V,E)中，任選一個節(jié)點v0作為起始節(jié)點，v0的級定義為 0，記為Nl(v0)=0。假設vi(i≠0,vi∈V)距離v0的最短路徑長度為k，則vi的級為k，記為Nl(vk)=k。圖G(V,E)中所有級為k的節(jié)點組成的集合記為。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)。在δ-規(guī)則圖G(V,E)中，節(jié)點vi到G中其余所有節(jié)點vj(i≠j,vj∈V)的最短路徑的長度值形成N-1個元素的一維向量，記為OM(G,vi)。假設當G(V,E)中產生故障f(G,k)后拓撲變?yōu)閳DG'(V',E')，對于vi(vi∈V，vi∈V)，如OM(G,vi)≠OM(G′,vi)，則vi定義為G中被故障f(G,k)影響的節(jié)點。其中，OM(G,vi)和OM(G',vi)只比較vi到正常節(jié)點的距離變化。

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

定義6'

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

以圖3為例，節(jié)點15在某一時刻產生了故障，即fv(G,1)={15}。由于節(jié)點的規(guī)模較小，通過觀察就可以得出在其余節(jié)點中，節(jié)點最短路徑長度矩陣發(fā)生變化的節(jié)點是{v4,v7,v8,v9,v14}。根據定義5，F(xiàn)IS(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難度。在實際的網絡運營環(huán)境中，運營商會根據需要變更可擴展路由器的規(guī)模。規(guī)模擴展的靈活性要求頑健性評價方法應能評價頑健性隨規(guī)模變化的趨勢，這需要對可能應用到的規(guī)模都運行評價算法進行頑健性分析，此時算法復雜度的重要性更加凸顯。因此，簡化評價算法復雜性非常重要。

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

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

3.1 幾種流行的直連網絡

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

表1 環(huán)型拓撲和回環(huán)型拓撲的FIS和FII屬性

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

3.2 P2i的故障影響分析

3.2.1 拓撲概述

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

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

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

圖4 一個8節(jié)點P2i和一個9節(jié)點P2i

3.2.2 P2i故障影響的相關結論

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

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

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

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

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

任取一個N節(jié)點P2i中的節(jié)點v0。在隨機單故障模型下，如果故障發(fā)生在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節(jié)點P2i中的節(jié)點v0，HD邊故障只可能會影響到v0到其他節(jié)點的HDSP最短路徑的長度。

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

3.2.3 P2i故障影響的優(yōu)化算法

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

4 實驗結果及比較

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

4.1 敏感性實驗結果及分析

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

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

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

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

4.2 單故障實驗結果及分析

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

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

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

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

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

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

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

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

5 結束語

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

[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.