任意平面交換網(wǎng)絡(luò)容錯設(shè)計

李鍶鍶

摘 要：交換網(wǎng)絡(luò)（Switching Network）被廣泛應(yīng)用在計算器通訊、平行處理、階層交換及積體電路繞線等領(lǐng)域中。在各領(lǐng)域之間會因為性質(zhì)及對象的不同，對于交換網(wǎng)絡(luò)的效能亦會有所不同的要求，為使系統(tǒng)提高效能、增加交換能力以及減少交換的時間，一般采用無阻塞交換網(wǎng)絡(luò)（Non-Blocking Switching Network），然而，交換能力愈好往往代表其須使用數(shù)量較多的交換元（Switch Element）以及采用較復(fù)雜的連線架構(gòu)，此舉卻會使得交換網(wǎng)絡(luò)的成本增加。

關(guān)鍵詞：任意平面；交換網(wǎng)絡(luò)；容錯設(shè)計

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A

分析任意平面交換網(wǎng)絡(luò)及其組成規(guī)則，經(jīng)此規(guī)則所組成的交換網(wǎng)絡(luò)皆為無阻塞交換網(wǎng)絡(luò)，（Unrestrained Planar Switching Network）簡稱為UPSN，對于一個n輸入的UPSN，存在有（n-1）種平面交換網(wǎng)絡(luò)；若將UPSN中的交換元視為比較器，則每個UPSN可作為平面排序網(wǎng)絡(luò)使用。本論文將針對所組合出的平面交換網(wǎng)絡(luò)設(shè)計自由路（Self-routing）演算法以及適用于所有UPSN的連線建立算法，經(jīng)由算法可使每個輸入埠的封包正確送達(dá)其所要求的輸出埠。最后，將針對所有UPSN架構(gòu)設(shè)計其相對應(yīng)的容錯設(shè)計，此容錯設(shè)計可容許UPSN中有任意一個交換元損壞，對于一n輸入的UPSN，于交換網(wǎng)絡(luò)中放置備用交換元，最佳只需n-1個，而最差僅需2n-4個備用交換元，則可使得有任何一個交換元損壞時，經(jīng)由適當(dāng)?shù)倪x取算法選取備用交換元后，回復(fù)原本無阻塞交換網(wǎng)絡(luò)的特性并符合UPSN的組成規(guī)則。

1 交換網(wǎng)絡(luò)架構(gòu)的容錯設(shè)計

組成各種交換網(wǎng)絡(luò)的交換元，由于交換網(wǎng)絡(luò)架構(gòu)及連線算法的不同，可能造成某些特定交換元使用頻率偏高，這些使用頻率較高的交換元，其壽命相對較短，交換網(wǎng)絡(luò)架構(gòu)設(shè)計上皆盡可能精簡交換元數(shù)目，以求得在硬件花費上的最佳表現(xiàn)，若因些許交換元損壞而喪失交換網(wǎng)絡(luò)的交換能力與其原本的特性（無阻塞交換網(wǎng)絡(luò)不在具有無阻塞特性），則會造成交換網(wǎng)絡(luò)的維護(hù)更加困難，成本愈高，是如何設(shè)計容錯架構(gòu)的問題。

2 交換網(wǎng)絡(luò)架構(gòu)容錯設(shè)計

以Spanke-BenesNetwork為列，Spanke-BenesNetwork屬于平面交換網(wǎng)路，所有平面交換網(wǎng)路皆可以任意平面交換網(wǎng)絡(luò)UPSN表示。當(dāng)Spanke-BenesNetwork其中一個交換元損壞時，則會喪失原本具有的無阻塞交換網(wǎng)絡(luò)的特性，我們提出一種稱為FaultTolerantSpanke-BenesNetwork，簡稱FT-Spanke-Benes，對于一n輸入的Spanke-BenesNetwork，只需將n-1個額外的交換元放置到特定位置，即可針對此交換網(wǎng)絡(luò)中任何一個交換元損壞時，仍維持Spanke-BenesNetwork無阻塞交換的特性。

圖1（左）所示為一6輸入的Spanke-BenesNetwork，可以UPSN的1，3，5，4，2表示，圖1（右）則為其容錯設(shè)計，紅色部分為額外放置的備用交換元。

我們將說明當(dāng)Spanke-BenesNetwork中有任何一個交換元損壞時，如何選取備用交換元來進(jìn)行其架構(gòu)的重組。例如當(dāng)ROW3有任一交換元損壞（BAD）時，我們將整條ROW3的交換元全部設(shè)定為不動作（Straight），即狀態(tài)0，等同于移除了ROW3所有交換元，此時可以發(fā)現(xiàn)，當(dāng)有任何一個ROW的交換元個數(shù)比ROW3小時，則必須將備用交換元取出使用（包括交換元個數(shù)為0的ROW5）。而ROW3的交換元個數(shù)為4，可知ROW0、ROW1、ROW4及ROW5須將備用交換元取出使用。所以最后的重組結(jié)果為（2，4，5，3，1），仍是一無阻塞交換網(wǎng)路。

我們以上述的范例可以發(fā)現(xiàn)以下規(guī)則：當(dāng)交換元損壞時，損壞的ROW中有i個交換元時，則需取出i個額外備用交換元使用，才能使其形成符合UPSN組成規(guī)則的無阻塞交換網(wǎng)絡(luò)。

3 容錯設(shè)計的分析

在一n輸入的UPSN中，當(dāng)有一交換元損壞時，則將此交換元所在的Row所有交換元設(shè)為狀態(tài)0，亦即若有多個交換元損壞時，若其都在同一層Row中，則最大可容許n-1個交換元損壞，最少則為1個。

于容錯架構(gòu)設(shè)計中，我們也可知，于不同的UPSN架構(gòu)中，所需的備用交換元數(shù)量皆不相同，對于一個n輸入輸出的UPSN，其最佳的情況，例如于Triangle-Type架構(gòu)及Spanke-BenesNetwork架構(gòu)下，其所需備用交換元個數(shù)僅需要n-1個，意即每層Row僅需準(zhǔn)備一備用交換元，最差的情況則時交換元個數(shù)恰好為最多及第二多，其所需備用交換元個數(shù)為2n-4，相當(dāng)于需為每層Row準(zhǔn)備兩個備用交換元。

容錯設(shè)計的備用交換元個數(shù)與交換元總數(shù)的比率圖，藍(lán)色部分為備用交換元個數(shù)除以交換元總數(shù)的比率，橘色為最佳備用交換元個數(shù)除以總數(shù)，而灰色則為最差交換元個數(shù)除以總數(shù)，橫軸為交換網(wǎng)絡(luò)輸入數(shù)，介于2～1000，縱軸為其比率，由此圖可以知道，當(dāng)一UPSN架構(gòu)的輸入輸出數(shù)n愈大時，其所需的備用交換元個數(shù)愈趨近于最差，然而，其備用交換元個數(shù)與交換元總個數(shù)1＼2相比，其級數(shù)上明顯較少。

結(jié)語

連線建立算法是以C++程序語言所撰寫，目的在于驗證此連線算法的正確性，用戶可以任意決定UPSN的輸入數(shù)、交換元放置方式以及目的端所要求的輸出端，或者由程序自行亂數(shù)產(chǎn)生，程序有兩種結(jié)束方式，其一為當(dāng)有輸入端經(jīng)由Right-to-Left連線建力算法建立連線后，其到達(dá)的目的地為錯誤的輸出端，此時可以知道此種算法有錯誤，程序?qū)Y(jié)束，其二為所有連線皆建立完畢且所有輸入端皆到達(dá)正確的輸出端，代表此次UPSN，Right-to-Left連線建立算法為正確，程序?qū)Y(jié)束。

參考文獻(xiàn)

[1]富弘毅，楊學(xué)軍.大規(guī)模并行計算機系統(tǒng)硬件故障容錯技術(shù)綜述[J].計算機工程與科學(xué)，2010（10） .

[2]張祖平.規(guī)則網(wǎng)絡(luò)容錯路由算法及可靠組播的研究[D].中南大學(xué)，2005.