- 學位論文
光通訊網路之高效能故障管理方案研究
High Performance Fault Management Schemes for Photonic Networks
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
中文摘要 本論文提出列表法(tabular method)及網狀環搜尋法(mesh-ring search method)分別應用在光學多階交互網路(OMINs)及波長分割多工(WDM)網路上的故障管理機制的設計。首先，本論文對於先前使用啟發式(heuristic)演算法來診斷OMINs中串音故障所得到的結果並不滿意，因此提出了一種決定論式(deterministic)演算法，並稱為列表法，將所有可能的衝突路徑全部記錄在表格內，接著找出不相衝突並可以一起測試的組合。列表法的第一個應用是用在OMINs中的串音故障診斷，使用列表法可以快速地找出串音故障診斷中所有可能的測試組合，不論是執行偵測或是定位程序，這個方法都可得到最佳化的測試叢集。接著再利用所提出的列表法，應用於故障容錯機制的設計，這個機制稱為故障容錯排程演算法。本演算法是以最少連線回合(round)的次數，在DBN網路上建立任意輸入及輸出埠之間的連線，並避開已知的故障開關元件以達到容錯的目的。由於OMINs在WDM網路中，可作為交換光訊號的主要元件，例如，可應用為光塞取多工器(OADM)、光交接機(OXC)及星狀耦合器(star coupler)。若OMINs元件在WDM網路中惡化，整個系統效能就會降低。因此，WDM網路的容錯議題是本論文接下來探討的目標。WDM網路的故障回復(recovery)機制基本上可以分為故障保護(protection)及故障還原(restoration)這兩種方法。故障保護是指在新的連線建立時即會同時保留備用線路；而故障還原是指在故障發生後再動態地找尋備用線路。如果針對不同的故障保護需求，故障保護技術可以為專用(dedicated)網路資源或是共享(shared)網路資源的方式。如果從備用路徑的起始節點來分類，則故障回復技術可以分為鏈路(link)，路徑(path)及區段(segment)等三種回復方法。在過去的文獻中與WDM網路容錯有關的議題，主要為鏈路(link)和路徑(path)之故障回復的研究；只有極少數的研究是探討WDM網路中的區段(segment)故障回復。由於網路使用成長迅速，環狀網路已不敷使用，網狀網路使用愈趨普及，因此我們將重點放在網狀網路的區段故障回復的研究上。本論文考慮所提方法的務實性，並可將過去在環狀網路所使用的設備納入應用，本論文提出了一種分散式架構的網狀環搜尋法來找尋最適化的回復路徑，由網路上每個節點各自收集網狀環，這些網狀環經過計算後即可成為最適化的故障回復路徑。網狀環搜尋法的第一個應用是用在WDM網路的區段故障保護上，並有兩種方案，第一種方案稱之為動態共享區段保護演算法(DSSP)，這個演算法採用預先計算出的網狀環，經過所提出的演算法運算之後即可將工作路徑分割成數個區段，並預留頻寬資源來保護各區段。這種共享保護架構可以更有效地改善網路資源及提升保護的成功率，並可以應用於任意網狀網路。第二種方案是區段保護的實作方法，稱之為重疊區段保護演算法(OSP)及非重疊區段保護演算法(NOSP)。這種方案也是採用預先計算出的邏輯環，經過所提演算法運算後找出最適用的OSP及NOSP保護路徑。網狀環搜尋法的第二個應用是用在WDM網路的區段故障復原上，稱為動態多重環演算法(DMRA)，DMRA演算法在故障發生前先行計算出網狀環，當故障發生後，DMRA演算法會根據目前工作中的負載及沿著還原路徑可用的資源來作快速回復。網狀環搜尋法的第三個應用是整合上述兩種應用，提出故障回復品質保證機制(GQoR)，這個機制會依照顧客的需求將復原品質分為四種等級，而每一種等級會對映到適用的回復方式，這個機制保證顧客可以獲得包括回復時間及佔用網路資源等應有服務之需求。對上述幾種使用在光纖網路故障管理的方法，本論文除了說明及導引各種方法外，也對每種方法作了實際的模擬比較。從模擬結果得知本論文所提的方法是相當實用且有效。
並列摘要
ABSTRACT This dissertation proposes a tabular method and a mesh-ring search method for designing fault management mechanisms in Optical Multistage Interconnection Networks (OMINs) and Wavelength Division Multiplexing (WDM) networks, respectively. Limitations of previous literature are discussed, in which heuristic methods are adopted to diagnose crosstalk fault for OMINs. A deterministic algorithm called tabular method is then proposed to record all possible conflicting connections into a table; the connections are then assembled into several conflict-free test set. The first application is used to identify the optimal testing procedure from all possible solutions in the crosstalk fault diagnosis. Results of the proposed method always closely correspond to the optimal fault clusters or minimal test sets for crosstalk fault detection and location procedures. The second application of the tabular method is used to design a fault tolerant mechanism, which is called a fault-free connections scheduling algorithm in the Dilated Benes Network (DBN). The proposed algorithm establishes connections between arbitrary input/output pairs in a minimum number of rounds and averts faulty switches to increase system reliability in DBN. The OMINs can be utilized as major components in the WDM networks, including Optical Add-Drop Multiplexer (OADM), Optical Cross-Connect (OXC), and star coupler, to exchange optical signals. Once the OMINs components in the WDM networks have deteriorated, the entire system performance declines. This dissertation also designs a fault tolerant mechanism for WDM networks. The fault tolerant (commonly referred to as fault recovery) mechanism for WDM networks can be categorized as either protection or restoration. In the protection mechanism, each connection reserves backup paths statically during call setup. In the restoration mechanism, each connection that traverses a failed block discovers dynamically an adaptive backup route after failures occur. For various fault protection requests, the protection mechanism can be either a dedicated or shared facility. Depending on where a detour originates, the fault recovery mechanism can be classified into either link, path or segment recovery method. While previous studies addressing fault recovery issue in WDM networks largely focused on the link and path recovery, segment recovery in WDM networks has seldom been investigated. Networks have become increasingly complex given the accelerated demand for a larger bandwidth. Mesh networks are widely considered to be flexible, scalable, bandwidth-efficient, cost effective, and dynamic. Therefore, this dissertation investigates segment recovery schemes in the WDM mesh networks. To consider their feasibility, a mesh-ring search method is proposed to derive the adaptive recovery paths. Each node in the networks searches independently for its own mesh-rings; these mesh-rings then become adaptive recovery paths after calculation. The first application is used to design a segment protection mechanism in WDM networks, and then two schemes are presented. The first scheme in this application is called Dynamic Shared Segment Protection (DSSP). This algorithm uses pre-calculated mesh-rings to divide the working path into several working segments; resources are then reserved to protect these working segments. The proposed DSSP algorithm can utilize resources efficiently and increase the rate of successful protection, making it applicable in arbitrary mesh networks. The second scheme in this application is in the implementation perspective of segment protection, which is called Overlap Segment Protection (OSP) and Non-Overlap Segment Protection (NOSP). This scheme also applies pre-calculated mesh-rings to construct adaptive protection segments, which can or cannot overlap each other. The second application is used to design a fault restoration mechanism called Dynamic Multiple Ring Algorithm (DMRA) for the WDM mesh networks. DMRA pre-computes the mesh-ring architecture before faults occur enabling the proposed DMRA algorithm to recover quickly from failures and determine how to allocate recovered traffic loads based on the current traffic load and the network bandwidth along the restoration paths. The third application integrates previous applications to design a recovery mechanism called Guaranteed Quality of Recovery (GQoR). Four classes of priority for GQoR mechanism are applied based on the customer’s request, with each one mapped to the adaptive recovery method. The GQoR mechanism confirms that customers possess an efficient recovery time and sufficient backup resources. The above fault management methods in photonic networks are introduced, developed, and simulated herein. Simulation results demonstrate the feasibility of applying the proposed methods in real-world networks.
參考文獻
[Hwang03b] I.S. Hwang, H.C. Lin and S.N. Lee, “Θ(N5/6) time complexity of fault diagnosis algorithms in N×N dilated blocking photonic switching networks,” Journal of Information Science and Engineering, vol. 19, no. 4, pp. 653-665, July 2003.
[Clos53] C. Clos, “A study of nonblocking switching networks,” Bell Systems Technical Journal, vol. 32, no. 2, pp. 406-424, March 1953.
[Fumagalli99] A. Fumagalli, L.Valcarenghi, “Fast optimization of survivable WDM mesh networks based on multiple self-healing rings,” in Proceedings of SPIE Conference on All-Optical Networking, Boston, MA, vol. 3843, pp. 44-55, September 1999.
[Gadiraju01] P. Gadiraju and H.T. Mouftah, “Channel protection in WDM mesh networks,” in Proceedings of 2001 IEEE Workshop on High Performance Switching and Routing, pp. 26-30, May 2001.
[Grover98] W.D. Grover and D. Stamatelakis, “Cycle-oriented distributed preconfiguration: Ring-like speed with mesh-like capacity for self-planning network reconfiguration,” Communications, in Proceedings of ICC’98, vol. 1, pp. 537-543, June 1998.