任意平面交換網絡容錯設計

李鍶鍶

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

關鍵詞：任意平面；交換網絡；容錯設計

中圖分類號：TP393 文獻標識碼：A

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

1 交換網絡架構的容錯設計

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

2 交換網絡架構容錯設計

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

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

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

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

3 容錯設計的分析

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

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

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

結語

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

參考文獻

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

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