一個具備成本效率之最小環覆蓋的演算法運用在光纖網路故障自動切換回復機制之研究

A Cost-effective Minimum Cycle Cover (MCC) Algorithm in WDM Networks with Automatic Protection Switching

林飛宏(Fei-Hung Lin)

指導教授 ： 黃依賢

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

摘要

隨著網際網路使用者快速成長，光纖網路已成為解決頻寬不足的最佳選擇，在考量建置備援容錯技術，提供使用者有效率且不間斷的服務品質成為一個重要的議題，但要建構一個100%的容錯環境，所要付出的成本是不符合經濟效益的，所以本論文提出一個新的演算法-MCC，它可容許同時多個網路連結故障，並結合APS的機制，快速即時切換至備援路徑，降低網路故障時的影響，另外本論文提出的是一個分散式保護環的架構，透過MCC演算法，減少相依保護環連結的數目，找出我們所需的保護環，避免浪費過高保護資源，並保留保護環的特性，如此可有效降低建置備援網路的成本，並使得傳輸的控管與維護更容易，與傳統研究比較，當連結錯誤時，我們能提供快速回復機制，更進而提供一個有效率且符合成本的容錯環境。

關鍵字

容錯 ； 保護環

並列摘要

In networks with planar topologies, this paper proposes a heuristic method based on routing which is the Minimum Cycle Cover (MCC) algorithm for performing Automatic Protection Switching (APS) in optical networks. The algorithm provide for restoration inherit many advantages of Double Cycle Cover (DCC). The protection process proposed is fast, full restoration, distributed, and autonomous. It restores the network in real time, without relying on a central manager or a centralized database, but the drawback of this DCC scheme needs constructing of fault tolerant environment cost is not accord with the economic benefits. Therefore, the MCC can establish an efficient construction of many decomposition cycles from the architecture of DCC. That can really protect single failure and multiple failures. The MCC algorithm of performance with single and two link faults are similar to DCC. Comparisons are made by introduction of metrics that measure a protection scheme’s effectiveness in handling link failures. The cost-effective of link fault obtained using MCC is higher than using DCC and the protection probability value is approximation between the two algorithms.

並列關鍵字

Automatic Protection Switching (APS), Double Cycle Cover (DCC)

參考文獻

[1]Robert G. Gallagert and Muriel Mhdardt, “Multicast Automatic Protection Switching in Arbitrary Redundant Graphs,” IEEE International Conference on Network Communications, June 1998 pp.640 – 644.

[2]G. Ellinas and T. Stern, “Automatic protection switching for link failures in optical networks with bi-directional links,” IEEE International Conference on Network Communications, Nov. 1996, pp. 152-156.

[3]S.G. Finn, M. Medard and R.A. Barry, “A new algorithm for bi-directional link self-healing for arbitrary redundant networks,” IEEE High Performance Switching and Routing, Feb. 1998, pp. 298-299.

[5]C. Ou and H. Zang, “Subpath protection for scalability and fast recovery in optical WDM mesh network,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 9, Nov. 2004, pp. 1859-1875.

[7]C.C. Sue and M.S. Shieh, “Dependable WDM networks with reconfigurable edge-disjoint p-cycles,” IEEE Conference on Computer Communications and Networks, May 2005, pp. 126-130.