班樣網路的錯誤診斷與容錯設計

Abstract

前人已提出一種可以有效率的診斷班樣網路之錯誤的方法。然而此種方法 只適用於具有狀態控制線的班樣網路。加上狀態控制線不僅使班樣網路的 線路變得複雜，也因錯誤有可能發生在這些控制線上，而降低其可靠度。 在此篇論文中，吾人提出一種不具狀態控制線的錯誤診斷的方法。此法分 為兩個測試階段。在第一和第二測試階段中，分別以適當的尋徑向量 (Routing Vector)使網路中的每一個交換元件被設定在平行狀態與交叉狀 態下。研究結果顯示，經由這兩個測試階段可以完全診斷出大部分的單一 錯誤(Single Faults)。但是其中有六種情況需要進一步以二元搜尋( Bina ry Search)法來找出錯誤之交換元件之位置。另外仍有四種發生在 交換元件上的錯誤與接線錯誤是無法辨別的。以上方法只適用於離線之班 樣網路的錯誤診斷。然而，原本無錯的班樣網路也可能在操作時發生錯誤 。尤其在高速的通訊網路中，儘早發現交換結構中的錯誤是很重要的。我 們提出了針對操作中的班樣網路作錯誤檢測(Detection) 及定位某些種錯 誤的內建電路。此種設計可在錯誤影響到正常輸出之時或之前檢測出任何 單一錯誤。最後，我們提出了一種增強網路容錯能力之交換結構。此種結 構乃是以班樣網路為基本架構而設計的。它非常簡單，只需在班樣網路的 每一中間級加上一額外的交換元件，並每一交換元件的輸入與輸出端分別 加上3: 2與2:3的選擇器(selector)即可。當錯誤發生時，錯誤的交換元 件可由同級額外的交換元件所取代，而達到容錯的目的。一般班樣網路所 用的錯誤診斷方法，也可以適用於此種容錯交換網路。 Efficient and effective fault diagnosis procedures for banyan networks had been proposed previously. However, the procedures are useful only for banyan networks with state control lines. Adding state control lines not only complicates the circuit design but also reduces the reliability of a banyan network because faults may occur at those control lines. In this thesis we present an efficient fault diagnosis procedure for banyan networks without state control lines. Our diagnosis procedure consists of two phases. In phases I and II, all switching elements are set respectively to be in the direct or the cross state. To achieve this, appropriate routing tags are applied to the inlets. We show that most of the single faults can be diagnosed in two phases. A binary search is required to locate the faulty switching element and identify its functional state for six cases. However, there are still four switching element faults which result in ambiguity and cannot be distinguished from the link stuck fault. A fault-free banyan network may also become faulty during its operation. In a high-speed network, it is important to detect the existence of faults as early as possible. We design a built- in fault detection and location (for some types of faults) circuit for banyan networks. Our circuit can detect any single switching element fault before or at the first time it affects normal output. We also propose a fault tolerant switching fabric based on network. It has the capability of tolerating single faults in the network. Only a redundant switching element is added for each intermediate stage. Besides, each switching element in the proposed fault- tolerant network has 3:2 and 2:3 selectors at its input and output, respectively. Once a fault occurs, the faulty switching element can be replaced by the redundant one in the same stage. The fault diagnosis scheme proposed in this thesis is also valid for the fault-tolerant switching network.