擴張型可重新排列光電開關網路串音偵錯之容錯排程演算法

Fault Tolerant Scheduling Algorithm for Diagnosing Crosstalk Faults in Dilated Re-arrangeable Network

張世昭(Shih-Chao Chang)

指導教授 ： 黃依賢

元智大學/資訊學院/資訊工程學系/碩士(2002年)

摘要

光學交換網路(Photonic switching network)能負載大量資料來提供高速的傳輸並避免重複的電光(electrical-to-optical)、光電(optical-to-electrical)訊號轉換。儼然已成為未來網路的主流趨勢。在擴張型光學多階交互網路(DOMINs)中， 光學交換器是最常使用的交換元件[1]、[2]，而串音錯誤(crosstalk　fault)則是光學多階交互網路經常出現的問題。其可能發生的原因是在光學交換器中不同的繞送路徑訊號會產生不預期的偶合效應，導致在交換器中少許的輸入埠訊號能量傳輸至非預期的交換器輸出埠。先前的研究[3]、[4]、[5]、[6]已經針對擴張型阻隔網路和擴張型可重新排列光電開關網路設計出錯誤交換器的偵測與定位演算法。其採用的錯誤列表法(Tabular methodology)可用在擴張型阻隔網路中找出錯誤偵測(fault detection)及錯誤定位(fault location)中的最佳錯誤叢集(optimal fault cluster)，錯誤叢集是錯誤開關診斷中一個獨立的測試組合。在本論文中我們同樣採用錯誤偵測與定位演算法找出在Dilated Benes Network (DBN)中發生錯誤的交換器，並利用錯誤列表法找出最佳錯誤叢集。藉由錯誤交換器資訊以及我們所提出的路徑產生演算法(Path Generation Algorithm)、無錯誤路徑產生演算法(Fault-free Path Generation Algorithm)及排程演算法(Scheduling Algorithm)來解決DBN中連結建立的排程問題。我們提出的方法能夠減少嘗試錯誤繞送的次數而加速連結的建立並能在硬體成本和傳輸效益上取得平衡[7]。最後我們以馬可夫模式(Markov model)分析非容錯的排程系統與我們提出之容錯排程系統之可靠度(Reliability)。實驗結果證明，我們提出的方法可在DBN上以最有效率的方式找出繞送路徑來建立連結並藉由多回繞送來達到容錯(fault tolerance)目的以提高系統之可靠度。
關鍵字：擴張型光學多階交互網路(DOMINs)，串音(crosstalk)，列表法(tabular methodology)，錯誤叢集(fault cluster)，光學交換器，容錯(fault tolerance)，可靠度(reliability)。

關鍵字

擴張型光學多階交互網路 ； 串音 ； 列表法 ； 錯誤叢集 ； 光學交換器 ； 容錯 ； 可靠度

並列摘要

Photonic switching networks providing high-speed transmission to avoid the repeated optical-to-electronic (O/E) and electronic-to-optical (E/O) signal conversions in high-speed communications has become a tendency to the future network. The electro-optical coupler[1]、[2] is a common switching elements in Dilated Optical Multistage Interconnection Networks (DOMINs). Optical crosstalk is a problem commonly found in DOMINs. Because of the undesirable coupling within optical switch, a portion of energy of input signal might be transmitted to the undesired output terminal in the switch. Previous works [3]、[4]、[5]、[6] have devised fault diagnosis algorithm for both dilated blocking network and dilated rearrangeable network. The method based on Tabular Methodology is able to find out the optimal fault cluster for fault detection and location in the dilated blocking network. In the paper, we adopt the same method to find out the optimal fault clusters in the Dilated Benes Network (DBN) that belongs to dilated rearrangeable network. By means of the faulty switch information and the proposed Path Generation Algorithm, Fault-free Path Generation Algorithm and Scheduling Algorithm, we can resolve the scheduling problem for establishing connections in the DBN. Our method can reduce the routing number to find out the proper routing paths for connections, speed up the establishment of connections, and reach a balance between hardware cost and transmission efficiency [7]. Finally, we use the Markov model to analyze system reliability of the traditional scheduling algorithm and the proposed scheduling algorithm. The experiment results show that our method is efficient to establish connections and to achieve fault tolerance to raise the system reliability by multiple rounds.

並列關鍵字

DOMINs ； crosstalk ； tabular methodology ； fault cluster ； optical switch ； fault tolerance ； reliability

參考文獻

[1] R.A. Spanke,“Architectures for Guided-Wave Optical Space Switching Systems”, IEEE Communications Magazine, Vol. 25, No. 5, pp. 42-48, May 1987.

[2] A. Jajszczyk, “A class of directional-coupler-based photonic switching networks”, IEEE Transactions on Communications, Vol. 41, No. 4, PP. 599-603, April 1993.

[3] I-Shyan Hwang and I-Feng Huang,“The Optimal Testing in Dilated Photonic Switching Networks Using Tabulation Methodology”, to appear at Information Science.

[4] I-Shyan Hwang and San-Nan Lee, ”Diagnosing Crosstalk Faults in A Class of Dilated Blocking Optical Multistage Interconnection Networks”, Information Sciences: An International Journal, Vol. 124, PP. 59-91, May 2000.

[5] I-Shyan Hwang, ”Diagnosing Crosstalk Faults In Dilated Benes Network”, Journal of the Chinese Institute of Electrical Engineering, Vol. 6, No.3, pp. 205-217, 1999.