由於WDM技術的研發，使光纖網路的頻寬與日俱增。當實體的光纖網路受到人為破壞(道路施工、設備操作失當)或者自然災害(地震、海纜斷裂)的影響，而造成連線中斷將導致龐大的資料損失，因此光纖網路的保護(protection)是一個重要的議題。FIPP保護環(Failure-Independent Path Protecting p-cycle, FIPP p-cycle)為鏈路保護環(span p-cycle)的延伸，主要用於提供WDM網路下光路徑(lightpath)的一種端對端的保護機制。由於具備預先建立備用路徑的特性，當工作路徑發生鏈路毀損時，能夠在端點即時將中斷的連線需求切換到保護路徑上，使受影響的工作路徑得以從鏈路毀損中存活。在此我們討論當網路連續發生多次單一鏈路毀損時，如何維持FIPP保護環對工作路徑的保護能力，使經過連續鏈路毀損之後，維持多數工作路徑仍能被剩餘之FIPP保護環保護，可抵抗後續的鏈路毀損。
本篇論文主要貢獻在於當光纖網路發生連續鏈路毀損時，藉由適當的恢復策略使受影響的工作路徑有能力抵抗連續的鏈路毀損，直到網路資源耗盡而無法進行調整為止。論文中提出二種恢復策略：保護環恢復策略(Cycle Recovery Policy)、路徑恢復策略(Path Recovery Policy)，並且藉由保護環調整(Cycle-Adjust)程序加強恢復策略的成功率，同時針對已知固定的連線需求(static)與不斷產生新的連線需求(dynamic)兩種環境進行實驗分析比較。經由模擬實驗顯示，保護環恢復策略與路徑恢復策略在不同規模的網路拓樸下表現出的恢復效果類似，若為中小型規模之網路拓樸則兩種恢復策略均有理想的恢復效果，在大型規模的網路拓樸下且考慮每次恢復策略所耗費的恢復時間，保護環恢復策略將是最佳的選擇。

As the wavelength division multiplexing (WDM) technology is developed to handle the increasing bandwidth request in optical network, the protection for optical network becomes as an important issue. This is because that lots of data will lose when human made (like uncorrected operation) or natural disaster (like earthquake) accidents leads to fiber cut. The FIPP p-cycle (Failure-independent path protecting p-cycle) is an extension of the span p-cycle which is an end-to-end path protection scheme and can be used to protect lightpaths in WDM network. In the FIPP p-cycle scheme, the backup paths are pre-established, when the working paths are affected by failure of link, they can be switched to backup paths at end nodes immediately. Though, the connection requests through the failed link can be survived. In this dissertation, we focus on how to recover the protecting capabilities of FIPP p-cycles to against the multiple link failures in WDM network.
In this dissertation, after recover the working paths affected by the failure of link, two recovering policies are designed to recover the protecting capabilities of the FIPP p-cycles if possible, unless there is no sufficient network resources. They are Cycle Recovery Policy (CRP) and Path Recovery Policy (PRP). Additionally, a new Cycle-Adjust (CA) algorithm is proposed and used to increase the success ratio of recovery policy. During the experiment, two situations are considered, one only has static connections and the other has both static and dynamic connections. Simulations show that both CRP and PRP have same recovering performance in small network. But in network with medium sizes, the CRP can perform the backup re-provisioning more quickly.

中文摘要 I
ABSTRACT II
致 謝 III
目錄 IV
圖目錄 VI
表目錄 VIII
第一章 導論 1
1.1 前言 1
1.2 分波多工網路簡介 1
1.3 存活性(survivability) 3
1.4 故障獨立路徑保護環 4
1.5 研究動機 5
1.6 研究問題與主要貢獻 6
1.7 後續章節介紹 6
第二章 問題定義 7
2.1 前提假設與已知項目 7
2.2 符號及相關參數 7
2.3 評估標準 8
2.3.1 波長效能比率 8
2.3.2 可恢復連線需求率與可恢復機率 9
2.3.3 重新供給成功率 9
2.3.4 阻斷率 9
2.3.5 恢復時間 9
2.4 研究限制與目標 10
第三章 文獻探討與分析 11
3.1 存活性(survivability) 11
3.1.1 恢復機制(restoration) 11
3.1.2 保護機制(protection) 11
3.2 保護環(p-Cycle) 12
3.3 故障獨立路徑保護環(FIPP p-Cycle) 13
3.3.1 概念 14
3.3.2 FIPP保護環相關研究 16
3.4 多重實體鏈路毀損 19
3.5 備用重新供給(backup re-provisioning) 21
3.6 FIPP保護環與連續實體鏈路毀損 25
第四章 研究方法 27
4.1 基本概念 27
4.2 恢復策略簡介 27
4.3 預先處理與相關演算法 29
4.4 保護環恢復策略(Cycle Recovery Policy, CRP) 37
4.4.1 演算法 38
4.5 路徑恢復策略(Path Recovery Policy, PRP) 46
4.5.1 演算法 46
4.6 保護環調整(Cycle-Adjust, CA) 53
4.6.1 演算法 53
第五章 實驗結果 60
5.1 節點分支度、連線需求數與波長數對恢復效能之影響 60
5.1.1 不同節點分支度(degree)下之恢復策略效能比較 60
5.1.1.1 實驗目的 60
5.1.1.2 實驗環境 60
5.1.1.3 實驗結果 60
5.1.2 連線需求與波長數量對恢復策略效能比較 69
5.1.2.1 實驗目的 69
5.1.2.2 實驗環境 70
5.1.2.3 實驗結果 70
5.1.3 綜合分析 75
5.2 恢復策略之恢復效果比較 76
第六章 結論與後續研究 86
6.1 結論 86
6.2 後續研究 87
6.2.1 保護關係全域與局部重新調整 87
6.2.2 DRS組成與調整 87
參考文獻 88

圖目錄
圖 1-1：具備光放大器之4通道點對點WDM傳輸系統[1] 2
圖 1-2：光塞取多工器(WADM)[1] 2
圖 1-3：實體拓樸與虛擬拓樸 3
圖 1-4：DRS與FIPP保護環 4
圖 3-1：鏈路保護環操作示意圖 12
圖 3-2：FIPP保護環操作示意圖 14
圖 4-1：保護環恢復策略 (a)修復前, (b)修復後 28
圖 4-2：路徑恢復策略 (a)修復前 (b)修復後 28
圖 4-3：以最大流量概念尋找鏈路不重疊路徑示意圖 29
圖 4-4：初始程序 30
圖 4-5：發生實體鏈路毀損時之恢復程序 31
圖 4-6：NCCF演算法 34
圖 4-7：NCPF演算法 35
圖 4-8：RGP演算法 36
圖 4-9：保護環恢復策略流程圖 39
圖 4-10：保護環恢復策略演算法 41
圖 4-11：CRP Step 2.2.1 – 2.3 42
圖 4-12：CRP Step 2.4 43
圖 4-13：CRP Step 3 44
圖 4-14：CRP Step 4 45
圖 4-15：路徑恢復策略流程圖 47
圖 4-16：路徑恢復策略演算法 49
圖 4-17：PRP Step 2.1.1 – 2.2 50
圖 4-18：PRP Step 3 51
圖 4-19：PRP Step 4 52
圖 4-20：保護環調整流程圖 54
圖 4-21：保護環調整演算法 55
圖 4-22：CA Step 2 56
圖 4-23：CA Step 3 57
圖 4-24：CA Step 4.1-4.3.4 58
圖 4-25：CA Step 4.4 59
圖 5-1：CRP平均可恢復連線率與節點分支度之比較 62
圖 5-2：PRP平均可恢復連線率與節點分支度之比較 62
圖 5-3：可恢復連線需求率與節點分支度之比較 63
圖 5-4：CRP平均可恢復機率與節點分支度之比較 64
圖 5-5：PRP平均可恢復機率與節點分支度之比較 64
圖 5-6：可恢復機率與節點分支度之比較 65
圖 5-7：CRP平均重新供給成功率與節點分支度之比較 66
圖 5-8：PRP平均重新供給成功率與節點分支度之比較 66
圖 5-9：CRP平均阻斷率與節點分支度之比較 68
圖 5-10：PRP 平均阻斷率與節點分支度之比較 68
圖 5-11：阻斷率與節點分支度之比較 69
圖 5-12：連線數量與波長數量之平均可恢復連線率比較(不產生新連線需求) 71
圖 5-13：連線數量與波長數量之平均可恢復連線率比較(產生新連線需求) 71
圖 5-14：連線需求數量與波長數量之平均可恢復機率比較(不產生新連線需求) 72
圖 5-15：連線需求數量與波長數量之平均可恢復機率比較(產生新連線需求) 72
圖 5-16：連線數量與波長數量之平均重新供給成功率比較(不產生新連線需求) 73
圖 5-17：連線數量與波長數量之平均重新供給成功率比較(產生新連線需求) 73
圖 5-18：連線數量與波長數量之平均恢復時間比較(不產生新連線需求) 74
圖 5-19：連線數量與波長數量之平均恢復時間比較(產生新連線需求) 74
圖 5-20：恢復策略在N1與N2網路中之平均波長效能比率比較 78
圖 5-21：恢復策略在N1與N2網路中之可恢復連線需求率比較 78
圖 5-22：恢復策略在N1與N2網路中之可恢復機率比較 79
圖 5-23：恢復策略在N1與N2網路中之重新供給成功率比較 79
圖 5-24：恢復策略在N1與N2網路中之阻斷率比較 80
圖 5-25：恢復策略在N1與N2網路中之恢復時間比較 80
圖 5-26：恢復策略在N3與N4網路中之波長效能比率比較 82
圖 5-27：恢復策略在N3與N4網路中之可恢復連線需求率比較 82
圖 5-28：恢復策略在N3與N4網路中之可恢復機率比較 83
圖 5-29：恢復策略在N3與N4網路中之重新供給成功率比較 83
圖 5-30：恢復策略在N3與N4網路中之阻斷率比較 84
圖 5-31：恢復策略在N3與N4網路中之恢復時間比較 84

表目錄
表1：不同種類之保護環對鏈路和節點毀損的保護能力 13
表2：實驗網路拓樸內容統計表 77

[1] Biswanath Mukherjee, Optical WDM Networks, Springer press, 2006.
[2] W.D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking, Prentice Hall PTR press, 2003.
[3] L. Guo, J. Cao, H. Yu and L. Li, “Path-based routing provisioning with mixed shared protection in WDM mesh networks,” Journal of Lightwave Technology, Vol. 24, Issue 3, pp. 1129-1141, Mar. 2006.
[4] G. Conte, M. Listanti, M. Settembre, R. Sabella, “Strategy for protection and restoration of optical paths in WDM backbone networks for next-generation Internet infrastructures,” Journal of Lightwaave Technology, Vol. 20, Issue 8, pp. 1264-1276, Aug. 2002.
[5] S. Kini, M. Kodialam, T. V. Laksham, S. Sengupta, and C. Villamizar, Shared backup label switched path restoration. http://search.ietf.org/internet-drafts/draft-kini-restoration
-shared-backup-01.txt
[6] W.D. Grover and D. Stamatelakis, “Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration,” IEEE International Conference on Communication, Atlanta, GA, USA ,Vol. 1, pp. 537-543, Jun. 7-11, 1998.
[7] A. Kodian and W.D. Grover, “Failure-independent path-protecting p-cycles: efficient and simple fully pre-connected optical path protection,” Journal of Lightwave Technology, Vol. 23, Issue 10, pp. 3241-3259, Oct. 2005.
[8] W.D. Grover and A. Kodian, “Failure-Independent path protection with p-Cycles: efficient, fast and simple protection for transparent optical networks,” Proceeding of International Conference on Transparent Optical Networks, Vol.1, pp 363-369, Jul. 2005.
[9] A. Kodian and W. D. Grover, “A disjoint route sets approach to design of failure-independent path-protecting p-cycle networks,” The 5th International Workshop on Design of Reliable Communication Networks (DRCN) 2005, Island of Ischia, Naples, Italy, pp. 231-238, July 2005.
[10] B. Jaumard, C. Rocha, W.D. Grover, “A column generation approach for design of networks using path-protecting p-Cycles,” Sixth International Workshop on Design of Reliable Communication Networks (DRCN) 2007, La Rochelle, France, Oct. 7-10, 2007.
[11] C. Ge, N. Bai, X. Sun, and M. Zhang, “Iterative joint design approach for failure-independent path-protecting p-cycle networks,” Journal of Optical Networking, Vol. 6, Issue 12, pp. 1329-1339 , Dec. 2007.
[12] D. Baloukov, W.D. Grover, and A. Kodian, “Toward jointly optimized design of failure-independent path-protecting p-cycle networks,” Journal of Optical Networking, Vol. 7, Issue 1, pp. 62-79, Jan. 2008.
[13] Boost Graph Library, URL:http://www.boost.org
[14] S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks. II. restoration,” IEEE International Conference on Communications, Vancouver, BC, Canada, Vol. 3, pp. 2023-2030, Jun. 6-10, 1999.
[15] S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks. part I-protection,” Proceeding of IEEE Conference of Computer and Communication Societies, New work, USA, Vol. 2, pp. 744-751, Mar. 21-25, 1999.
[16] Stamatelakis, W.D. Grover, “IP layer restoration and network planning based on virtual protection cycles,” IEEE Journal on Selected Areas in Communication, Vol. 18, Issue 10, pp. 1938-1949, Oct. 2000.
[17] H. Huang, J. A. Copeland, “Hamiltonian cycle protection: a novel approach to mesh WDM optical network protection,” Proceeding IEEE Workshop on High Performance Switching and Routing (HPSR) 2001, Dallas, Texas, USA, pp. 31-35, May 29-31, 2001.
[18] 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 Communication., Vol. 21, Issue 8, pp. 1306-1319, Oct. 2003.
[19] C. C. Sue, M. S. Shieh, and C. Y. Huang, “Dependable WDM networks with reconfigurable edge-disjoint p-Cycles,” Proceeding 3rd IEEE International Conference on Information Technology: Research and Education (ITRE 2005), Hsinchu, Taiwan, Jun. 27-30, 2005.
[20] W.D. Grover, “Path protecting p-Cycles and the protected working capacity envelope concept: addressing the needs of dynamic transparent optical networks,” Proceeding of International Society for Optical Engineering, Vol. 5970, pp. 1-15, Oct. 2005.
[21] D.A. Schupke, “The tradeoff between the number of deployed p-cycles and the survivability to dual fiber duct failures,” Proceeding of IEEE Internationa Conference on Communication, Vol. 2, pp. 1428-1432, May 2003.
[22] D.A. Schupke, “Multiple failure survivability in WDM networks with p-cycles,” Proceeding of IEEE International Symposium on Circuits and Systems, Bangkok, Thailand,Vol. 3, pp. 866-869, May 25-28, 2003.
[23] D.A. Schupke, W.D. Grover and M. Clouqueur, “Strategies for enhanced dual failure restorability with static or reconfigurable p-Cycle networks,” Proceeding of IEEE International Conference on Communications, Paris, France, Vol 3, pp. 1628-1633, Jun. 20-24, 2004.
[24] H. Wang and H.T. Mouftah, “P-cycles in multi-failure network survivability,” Proceeding of International Conference on Transparent Optical Networks, Barcelona, Catalonia, Spain, Vol. 1, pp. 381-384, Jul. 3-7, 2005.
[25] A. Kodian and W.D. Grover, “Multiple-quality of protection classes including dual-failure survivable services in p-cycle networks,” International Conference on Broadband Networks, Vol. 1, pp. 231-240, Oct. 3-7, 2005.
[26] D.S. Mukherjee, C. Assi and A. Agarwal, “Alternate strategies for dual failure restoration using p-cycles,” IEEE International Conference on Communications, Istanbul, Turkey, Vol. 6, pp. 2477-2482, Jun. 11-15, 2006.
[27] G.V. Kaigala, W.D. Grover, “On the efficacy of GMPLS auto-reprovisioning as a mesh-network restoration mechanism,” IEEE Global Telecommunications Conference, Vol. 7, pp. 3797-3801, Dec. 1-5, 2003.
[28] R. Ramamurthy, A. Akyamac, J-F. Laourdette, and s. Chaudhuri, “Pre-emptive reprovisioning in mesh optical networks,” Optical Fiber Communications Conference, Vol. 2, pp. 785-787, Mar. 23-28, 2003.
[29] Jing Zhang, Keyao Zhu, and Biswanath Mukherjee, “A comprehensive study on backup reprovisioning to remedy the effect of multiple-link failures in WDM mesh networks,” IEEE International Conference on Communications, Paris, France, Vol. 3, pp. 1654-1658, Jun. 20-24, 2004.
[30] C. Assi, W. Huo, A. Shami , and N. Ghani, “Analysis of capacity re-provisioning in optical mesh networks,” IEEE Communication Letters, Vol. 9, pp. 658-660, Jul. 2005.
[31] C. Assi, W. Huo, “On the benefits of lightpath re-provisioning in optical mesh networks,” IEEE International Conference on Communications, Seoul, Korea, Vol. 3, pp. 1746-1750, May 16-20, 2005.
[32] Jing Zhang, Keyao Zhu, and Biswanath Mukherjee, “Backup reprovisioning to remedy the effect of multiple link failures in WDM mesh networks,” IEEE Journal on Selected Areas in Communications, Vol. 24, pp. 57-67, Aug. 2006.
[33] Lei Song, Jing Zhang, and Biswanath Mukherjee, “The advantages of backup reprovisioning after failure repair(and failure arrival) in telecom mesh networks,” IEEE International Conference on Communications, Istanbul, Turkey, Vol. 6, pp. 2501-2505, Jun. 11-15, 2006.
[34] Lei Song, Jing Zhang, and Biswanath Mukherjee, “Backup reprovisioning after network-state updates in survivable mesh networks,” Optical Fiber Communication Conference, Anaheim, California, Mar. 5-10, 2006.
[35] Xu Shao, Luying Zhou, and Yixin Wang, “Backup reprovisioning after shared risk link group(SRLG) failures in survivable WDM mesh networks,” Optical Fiber Communicaion Conference, Anaheim, CA, Mar. 25-29, 2007.
[36] Lei Guo, “Heuristic survivable routing algorithm for multiple failures in WDM networks,” IEEE Broandband Convergence Networks, Munich , May 21, 2007
[37] Wenda Ni, Xiaoping Zheng, Chunlei Zhu, Yili Guo, Yanhe Li, and Hanyi Zhang, “An improved approach for online backup reprovisioning against double near-simultaneous link failures in survivable WDM mesh networks,” IEEE Global Telecommunications Conference, pp. 2304-2309, Nov. 26-30, 2007.
[38] J.E. Baker, “A distributed link restoration algorithm with robust preplanning,” IEEE Global Telecommunications Conference, Phoenix, AZ, USA, Vol. 1, pp. 306-311, Dec. 2-5, 1991.