Abstract
這篇論文提出一個非同步傳輸模式(ATM)網路交換機(switch)的容錯設計 ，Knockout-banyan 交換機具有自我繞徑的能力，其硬體成本低，且在均 勻交通負載下效率很高。但是，一旦交換機上有任何硬體錯誤發生，其效 能將降的非常快，為了使交換機具有較高的可靠度，我們必須為 Knockout-banyan交換機增加容錯的機構。Knockout-banyan交換機大致上 可分成三個部份(1)資料封包分配器(distributor) (2)擴張型banyan網 路 (dilated-banyan network) 及(3)輸出佇列(output queue)。由於 Banyan網路的特性，交換元件之間可加一些分享鏈路(shared-links)來分 享鏈路的頻寬。這種分享鏈路的設計大大的增加了交換機整體效能。這篇 論文更改Knockout-banyan交換機的這種共享鏈路架構，並在每個交換元 件內的集中器(concentrator)上加了額外的控制線。新的設計對任一輸出 入對提供了額外的通道來傳送資料封包，因此，當交換機有錯誤發生時， 藉由改變某些控制線的狀態，封包會繞過壞掉的元件，並繼續繞徑 (routing)的程序。由於新的分享鏈路設計與原設計有相同的特性，因此 容錯交換機在正常情形(無錯誤發生)下的效能與原Knockout-banyan交換 機相同，經由數學分析，我們導出網路在ｋ個錯誤發生時的存活機率數學 式，並藉以算出整個網路所能容忍的最多錯誤個數之期望值。在封包遺失 機率的分析上，是以電腦模擬方式，針對不同個數的錯誤及不同個數的分 享鏈路求其封包遺失機率。由分析的結果得知本論文所提出的容錯設計可 使交換機容忍單一錯誤及一些特定的多重錯誤，且當有錯誤發生時，交換 機的效能將降的非常緩和。 This thesis considers the problem of providing fault-tolerant capability for ATM (Asynchronous Transfer Mode) switching systems. The Knockout-banyan switch proposed by W. J. Cheng and W. T. Chen is self-routing, cost-effective, and very efficient at handling uniform traffic. However, any faults in links or switch elements may cause the performance of the switch degrades rapidly. To obtain a reliable and high-performance switching fabric, we add control lines to the switch element and modify the shared-links design of the Knockout-banyan switch to provide redundant paths from any source to any destination. The reliability of the proposed switch is analyzed. The analytical results show that the fault-tolerant design provides fault tolerance for any single failure and robust in the presence of multiple faults. A simulation study is also presented to evaluate the performance of the proposed architecture. It is shown that when faults occur, the performance of the Knockout-banyan switch will degrade gracefully.