臺灣博碩士論文加值系統

　　隨著網際網路用戶的快速成長、網路服務的多樣化，整合語音、數據及影像的多媒體資訊傳輸的需求與日劇增，寬頻網路的發展刻不容緩，而光纖通訊技術的發展，為寬頻網路多媒體時代帶來了巨大的效益，已成為解決頻寬不足的最佳選擇和必要的途徑，當中，又以多波長分波多工光纖網路為近年來發展與研究的重點。無論是在長途骨幹網路或是接取區域網路間的都會光纖網路，考量整體性網路備援容錯的環境需求，提供有效率並且保證不間斷的服務品質，是重要的議題。在光纖鏈結發生錯誤的情況下，要建構一個可靠的多波長分波多工網路，過去的議題大多著重在環狀網路與網狀網路的架構下。環狀網路擁有快速的錯誤回覆速度，但是要建構一個100%的容錯環境，欲付出的成本會不符合經濟效益;網狀網路擁有較低的成本效益，但無法提供即時的錯誤回覆，進而無法提供不間斷的連結，降低了用戶端所要求的網路品質;欲提供即時的錯誤回覆，並同時擁有環的回覆速度與網狀網路的成本效益，在國外，這方面的研究已經日漸被受重視，最有名的即是事先組態保護環(p-Cycles)，經由我們的研究，發現這種架構與過去鋪設容錯環境的架構有著相同的弊端，當光纖鏈結錯誤在相依的保護鏈結上，並且在此錯誤被修復前，與此鏈結相依的保護環無法再容忍更多錯誤的發生，因而降低了作為分散式容錯環境的保護能力，本論文針對多波長分波多工光纖網路提出一個分散式的容錯設計，我們稱之為相異邊保護環，在分散式的保護環機制下，此設計能減少相依的保護鏈結數目，避免錯誤發生在相依的保護鏈結上，並顧及資源成本上的因素，在探討使用資源的多寡方面，我們進一步修改過去於保護環上所探討的數學分析式子，使其能適合我們所需要鋪設的保護環數目，避免過高的保護資源成本及保留保護環原有的特性，我們分析在不同的網路拓譜結構下，用此容錯機制設計相對應的容錯環境，並與過去相關的容錯研究作效能上的分析與比較所需要付出相對的代價為何，結果顯示此設計可以有效率的回覆錯誤的發生，及提供較低的保護資源成本，然而在這些研究中，我們也發現同時雙重的鏈結錯誤或是過多的鏈結錯誤都會使容錯的設計失去保護的能力，因此我們更進一步在我們的設計下提供了一個重組態的機制，當網路在分散式的保護環境下，當某個保護單元範圍的保護機制癱瘓，該如何重新組態容錯的環境並回覆該範圍的保護機制，在重新組態的機制下，我們分析該如何調整備援的鏈結資源，才能夠減少重新分配資源的數目、加速保護環的復原，使其網路持續擁有容錯的能力，為了達到改變較少的備援鏈結，我們盡可能以最短的路徑當作新的備援鏈結，與過去相關的研究作比較，我們亦能快速回覆網路中失去保護能力的範圍，並保證不錯的回覆率，更進而能提供一個真正既有效率又符合成本效益的容錯環境。

　Fault tolerant in all optical WDM network is an important issue. Network traffic in all optical WDM networks is required to offer connection oriented property and real time service. Without fault tolerant mechanism, all network traffic will guarantee to offer only best-effort service. Ring-based and mesh-based Protection which recovers network traffic due to link failure is the most familiar fault tolerant mechanism in all optical WDM networks. Beside, a fascinating protection mechanism called preconfigured protection cycles (p-Cycles) becomes a focus point in recent years.

　First, we propose a fault tolerant mechanism on the optical network design with Edge-Disjoint p-Cycles (EDPC). EDPC is a special type of traditional p-Cycles, that is, no common edges are allowed to exist between any two p-Cycles. Previously published schemes for computing p-Cycles are time consuming and do not survive multiple link failures when p-Cycles have common edges. Instead of using the complex ILP, a heuristic method based on link state routing which is compatible to the traditional open shortest path first (OSPF) network protocol is proposed to speed up the construction of EDPC. The results show that the EDPC method can tolerate more link failures and improve the restoration efficiency for traditional p-Cycles with the decrease of two working units for every two p-Cycles.

　Second, we propose a reconfigurable mechanism for dependable optical WDM network design with our proposal Edge-Disjoint p-Cycles (EDPCs) based protection. One p-cycle provides guaranteed protection against single link failure, but it can not protect against multiple link failures on one p-cycle. All working links protected by a p-cycle will crumble down if simultaneous double link-failures happen on the p-cycle. For such double-links failure, the objective of our reconfiguration focuses on using the least spare links to protect more working links and avoiding blocking the whole network to reconfigure. We call such mechanism as local reconfiguration and also implement it on our proposed EDPCs. Local reconfiguration will search reconfigurable links to take reconfiguration in the first step, and secondly take rerouting to search a degenerated p-cycle when reconfigurable links can not be found in first step. The results show that the local reconfiguration method can speed up the recovering time in-stead of time consuming scheme which blocks the whole network and take successful reconfiguration when double-link failure occurs. Furthermore, the double-link failure restorability in EDPCs with local reconfiguration is higher than that in the original EPDCs.

Contents

中文摘要 i
Abstract iii
Acknowledgement v
List of Tables viii
List of Figures ix

1 Introduction 1
1.1 Motivations 1
1.2 Organization 3
2 p-Cycles Mechanism in WDM Network 4
2.1 The Concept of p-Cycles 4
2.2 The Development of p-Cycles 7
2.3 Summary of p-Cycles Design Models 11
3 Dependable WDM Network with Edge-Disjoint p-Cycles 12
3.1 Introduction 12
3.2 Preliminary for Edge-Disjoint p-Cycles 14
3.2.1 Disjoint Edges and Overlap Nodes 14
3.2.2 Analysis for number of Overlap Node 16
3.3 Heuristic Method 17
3.3.1 Partition Formula Definition 18
3.3.2 Number of Partitions Setting 20
3.3.3 Routing Table State 22
3.3.4 Heuristic Algorithm 23
3.4 Summary 26
4 Local Reconfiguration for p-Cycles Based Protection 27
4.1 Introduction 27
4.2 Preliminary for Local Reconfiguration 30
4.2.1 Reconfiguration Classification 30
4.2.2 Additional Spares Analysis for Reconfiguration 31
4.2.3 Special failed cases in Local Reconfiguration 36
4.3 Heuristic Method 38
4.3.1 Heuristic Algorithm 39
4.3.2 Local Reconfiguration example 43
4.3.3 Some Necessary Condition for Local Reconfiguration 45
4.4 Time Complexity Analysis 48
4.5 Summary 49
5 Performance Analysis and Improvement of EDPCs 51
5.1 Introduction 51
5.2 EDPCs and Reconfigurable EDPCs 52
5.3 Implementaion Scenario 52
5.3.1 Probability Definition of EDPC Fault model 54
5.3.2 Mean Time to Failure and Fairness Factor 55
5.4 Evaluation and Discussion 57
5.5 Summary 62
6 Conclusions and Future Works 63
6.1 Conclusions 63
6.2 Future Works 64

Bibliography 66

[1] W.D. Grover and D. Stamatelakis, “Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration,” Proc. IEEE International Conf. Commun., pp. 537-543, June 1998.

[2] D. Stamatelakis and W.D. Grover, “IP layer restoration and network planning based on virtual protection cycles,” IEEE JSAC Special Issue on Protocols and Architectures for Next Generation Optical WDM Networks, vol.18, no.10, pp. 1938 – 1949, October 2000.

[3] G. Ellinas, G. Halemariam, and T. Stern, “Protection cycle in mesh WDM network,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, pp. 1924-1937, Oct. 2000.

[4] P.-H Ho and H. T. Mouftah, “A framework for service-guaranteed shared protection in WDM mesh network,” IEEE Communications Magazine, Vol. 40, No. 2, pp. 97–103, 2002,.

[5] G. L Xue and R. V Gottapu, “Efficient Construction of Virtual p-Cycles Protecting All Cycle-Protectable Working Links,” Workshop on High Performance Switching and Routing, pp. 305 – 309, June 2003.

[6] A. Sack and W. D. Grover, “Hamiltonian p-Cycles for Fiber-Level Protection in Homogeneous and Semi-Homogeneous Optical Networks,” IEEE Network, Special Issue on Protection, Restoration, and Disaster Recovery, vol.49-56, 2004

[7] W. D. Grover, J. Doucette, M. Clouqueur, D. Leung, and D. Stamatelakis, "New Options and Insights for Survivable Transport Networks," IEEE Communications Magazine, vol. 40, no. 1, pp. 34-41, January 2002

[8] Muriel Médard, Richard A. Barry, Steven G. Finn, Wenbo He, and Steven S. Lumetta, ”Generalized Loop-Back Recovery in Optical Mesh Networks,” IEEE Trans. Networking, vol. 10, pp.153-164, 2002.

[9] Muriel Medard, Steven G. Finn, Richard A. Barry, and Robert G. Gallager, ”Redundant Trees for Prepalnned Recovery in Arbitrary Vertex-Redundant Graphs,” IEEE/ACM Transactions on Networking, vol. 7, no. 5, pp. 641-652, Oct. 1999.
[10]. R.E. Tarjan, “Depth First Search and linear graph algorithm,” SIAM Journal on Computing, vol. 1, pp. 146-160, 1972.

[11] C.Qiao and D.Xu, “Distributed partial information management (DPIM) schemes for survivable network,” IEEE INFOCOM, pp.301-311, 2002.

[12] S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks, Restoration”, ICC, pp.2023-2030, 1999.

[13] L. Sahasrabuddhe, S. Ramamurthy and B. Mukherjee, “Fault management in IP-over-WDM network: WDM protection versus IP restoration,” IEEE Journal on Selected Areas in Commuications, vol. 20, pp 21 – 33, Jan. 2002.

[14]. W. D. Grover and D. Stamatelakis, “Bridging the ring-mesh dichotomy with p-Cycles,” in Proc. of DRCN 2000, pp. 92-104.

[15]. D. A. Schupke, C. Gruber, and A. Autenrieth, “Optimal configuration of p-Cycles in WDM networks,” in Proc. of ICC, 2002, pp. 2761-2765.

[16]. W. D. Grover, “p-Cycles,” Chapter 10 in Mesh-based Survivable Networks: Options for Optical, MPLS, SONET and ATM Networking, Prentice-Hall, Aug. 2003.

[17]. C. C Sue, Y. C Chen, M. S Shieh, and S. Y Kuo, “Dependable WDM Networks with Edge-Disjoint P-cycle”, IEEE 2nd International Symposium on Parallel and Distributed Processing and Applications, Dec. 2004.

[18]. M. Clouqueur and W. D. Grover, “Availability analysis of link restorable mesh networks,” IEEE JSAC, May 2002, pp. 810-821.

[19]. D. A. Schupke, A. Autenrieth, and T. Fischer, “Survivability of multiple fiber duct failures,” In Proceedings of the 2001 Int'l Workshop on the Design of Reliable Communication Networks (DRCN), October, 2001, pp.213-219.

[20]. D. A. Schupke, W. D. Grover, M. Clouqueur, “Strategies for enhanced dual failure restorability with static or reconfigurable p-cycle networks,” Proc. IEEE International Conference on Communications (ICC), Jun. 2004, pp. 1628-1633.

[21]. D. A. Schupke, “The tradeoff between the number of deployed p-Cycles and the survivability to dual fiber duct failures,” in Proc. of ICC 2003, pp. 1428-1432.

[22]. C. G. Gruber and D. A. Schupke, “Capacity-efficient planning of resilient networks with p-Cycles,” in Proc. of Networks 2002, pp. 389-396.

[23]. D. A. Schupke, M. Jaeger, and R. Huelsermann, “Comparison of resilience mechanisms for dynamic services in intelligent optical Networks,” in Proc. of DRCN 2003, pp. 106-113.

[24] G. Shen, W. D. Grover, “Extending the p-Cycle Concept to Path-Segment Protection for Span and Node Failure Recovery,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 8, Oct. 2003, pp. 1306-1319.

[25] D. Stamatelakis, Theory & Algorithms for Preconfiguration of Spare Capacity in Mesh Restorable Networks, M.Sc. Thesis, Univ. Alberta, Canada, 1997.

[26] D. Stamatelakis, W.D. Grover, “Theoretical Underpinnings for the Efficiency of Restorable Networks using Pre-configured Cycles (“p-Cycles”),” IEEE Transaction on Communications, vol. 48, no.8, Aug. 2000, pp. 1262-65.

[27] D. Stamatelakis, W.D. Grover, “OPNET Simulation of Self-organizing Restorable SONET Mesh Transport Networks,” in OPNETWORKS '98, Apr. 1998, paper 04.

[28] W. D. Grover, J. E. Doucette, “Advances in Optical Network Design with p-Cycles: Joint Optimization and Pre-selection of Candidate p-Cycles,” in IEEE-LEOS Topical Meetings, July 2002.

[29] W. D. Grover, D. Y. Li, “The Forcer Concept and Express Route Planning in Mesh-survivable Networks,” Journal of Network and Systems Management, vol. 7, no. 2, Jun. 1999, pp. 199-223.

[30] G. Shen, W. D. Grover, “Exploiting Forcer Structure to Serve Uncertain Demands and Minimize Redundancy of p-Cycle Networks,” OptiComm’03, October 2003, pp. 59-70.

[31] W. D. Grover, “The Protected Working Capacity Envelope Concept: An Alternate Paradigm for Automated Service Provisioning,” IEEE Communications Magazine (Special Issue on Management of Optical Networks), vol. 42, no. 1, Jan. 2004, pp. 62-69.