李鍶鍶（廣東省粵東商貿(mào)技工學校，廣東 梅州 514000）

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

李鍶鍶
（廣東省粵東商貿(mào)技工學校，廣東 梅州 514000）

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

任意平面；交換網(wǎng)絡；容錯設計

1 交換網(wǎng)絡架構的容錯設計

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

2 交換網(wǎng)絡架構容錯設計

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

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

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

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

3 容錯設計的分析

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

于容錯架構設計中，我們也可知，于不同的UPSN架構中，所需的備用交換元數(shù)量皆不相同，對于一個n輸入輸出的UPSN，其最佳的情況，例如于Triangle-Type架構及Spanke-BenesNetwork架構下，其所需備用交換元個數(shù)僅需要n-1個，意即每層Row僅需準備一備用交換元，最差的情況則時交換元個數(shù)恰好為最多及第二多，其所需備用交換元個數(shù)為2n-4，相當于需為每層Row準備兩個備用交換元。容錯設計的備用交換元個數(shù)與交換元總數(shù)的比率圖，藍色部分為備用交換元個數(shù)除以交換元總數(shù)的比率，橘色為最佳備用交換元個數(shù)除以總數(shù)，而灰色則為最差交換元個數(shù)除以總數(shù)，橫軸為交換網(wǎng)絡輸入數(shù)，介于2～1000，縱軸為其比率，由此圖可以知道，當一UPSN架構的輸入輸出數(shù)n愈大時，其所需的備用交換元個數(shù)愈趨近于最差，然而，其備用交換元個數(shù)與交換元總個數(shù)12相比，其級數(shù)上明顯較少。

結語

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

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

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

TP393

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