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

李鍶鍶

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

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

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

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

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

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

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

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

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

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

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

3 容錯(cuò)設(shè)計(jì)的分析

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

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

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

結(jié)語

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

參考文獻(xiàn)

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

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