隨著科技進步，我們對頻寬的需求的日益增加，光纖技術也越趨成熟。ISP 業
者所提供的服務，不但要滿足大眾的需求，更要要求可靠性。然而要求可靠性勢必
要提供預備的資源以保護網路的正常運作。WDM 網路從 OC-36、OC-48 到 OC-192，
傳輸的速度也進步到了 10G bps。
有很多關於 survival network 的研究與方法,如 P-Cycle、Loop-Back Recovery…
等等。本篇論文主要貢獻在於提出一個對網路做分割的演算法，稱為 Star-Block。
在論文中除了介紹該演算法之外，尚針對 Loop-Back 回復協定，說明該架構能更有
效地節省預備頻寬以節省成本。此外，考慮被 Star-Block 切割過的拓墣，我們也提
出一個提供兩層的 回復協定，讓較高優先權的光波長能更快的回復。

Recently the requirement of bandwidth increases as technology improvement and the optical technology are maturer than before. An Internet Service Provider (ISP) provides not only the requirement of capacity for clients but also reliability. However, the problem between reliability and cost is trade-off. In order to protect the network from shutdown when failing, the network must be provided spare resource. For the case of WDM network, bandwidth of a fiber grows with the changes of specification from OC-36, OC-48 to OC-192, and the transmission rate of OC-192 rises up to 10Gbps.

There are lots of researches and protection schemes about survival network, such as P-Cycle, Loop-Back recovery, etc. The main contribution of this thesis is that we propose an algorithm which can decompose the network topology into several small sub-topologies, called as Star-Block. This thesis not only introduces implementation of the algorithm but also explains the architecture of star block how to save more spare resource than the one of pure Loop-Back recovery without decomposing topology. In addition considering the decomposed topology, we propose a protocol supporting priority recovery, so that the wavelengths set to be high priority can be recovered faster than the one set to be low priority.

[1] Bensong Chen, George N. Rouskas, Senior, and Rudra Dutta,“ On Hierarchical Traffic Grooming in WDM Networks”, IEEE/ACM TRANSACTIONS ON NETWORKING
[2] M.Sumathil and P.T.Vanathi,“ Priority Based Dynamic Reconfiguration of Lightpath in WDMNetworks”, IEEE - ICSCN2007, MITCampus, Anna University, Chennai, India. Feb. 22-24, 2007. pp.250-252.
[3] Kwok Shing Ho and Kwok Wai Cheung,“Generalized Survivable Network”, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 4, AUGUST 2007
[4] Andrew Zalesky, Hai Le Vu, and Moshe Zukerman, Senior, “Reducing Spare Capacity Through Traffic Splitting”, IEEE COMMUNICATIONS LETTERS, VOL. 8, NO. 9, SEPTEMBER 2004
[5] Canhui (Sam) Ou, Hui Zang Narendra K. Singhal, Keyao Zhu, Laxman H. Sahasrabuddhe, Robert A. MacDonald, and Biswanath Mukherjee, “Subpath Protection for Scalability and Fast Recovery in Optical WDM Mesh Networks”, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 22, NO. 9, NOVEMBER 2004
[6] S. Ramamurthy, Laxman Sahasrabuddhe, and Biswanath Mukherjee, “Survivable WDM Mesh Networks”, JOURNAL OF LIGHTWAVE TECHNOLOGY, VOL. 21, NO. 4, APRIL 2003
[7] John Doucetteli, Donna He, Wayne D. Grover, Oliver Yang TRLabs, “Algorithmic Approaches for Efficient Enumeration of Candidate p-Cycles and Capacitated p-Cycle Network Design”, Design of Reliable Communication Networks (DRCN) 2003, Banff, Alberta, Canada, October 19-22,2003
[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/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 1, FEBRUARY 2002
[9] Wayne D. Grover, Demetrios Stamatelakis, TRLabs c/o Dept. of Electrical and Computer Engineering, University of Alberta “Cycle-Oriented Distributed Preconfiguration: Ring-like Speed with Mesh-like Capacity for Self-planning Network Restoration”
[10] Arnold Farkas, Janos Szigeti, “P-Cycle Based Protection Schemes forMulti-Domain Networks”
[11] Hiroaki Higaki Department of Computers and Systems Engineering Tokyo Denki University,” Wavelength Priority Assignment for Reconfigurable WDM Networks”
[12] Muriel MCdard, Steven S. Lumetta, Yung-Ching Tseng, “Capacity-Efficient Restoration for Optical Networks”
[13] DOUGLAS B.WEST,”INTRODUCTION TO GRAPH THEORY”, second edition
[14] Chuan-Ching Sue, Jing-Ying Yeh,” Utilize 100% redundancy to offer higher-level multiple fault restoration in WDM networks without wavelength conversion,” Computer Networks 53 (2009) 691–705
[15] Chuan-Ching Sue‚, Jun-Ying Yeh‚, Yung-Chiao Chen and Chin-Yu HuangÁ ” Tolerating Multiple Faults in WDM Networks without Wavelength Conversion,”
[16] G. N. Brown, W. D. Grover, J. B. Slevinsky, and M. H. MacGregor,“An architecture for efficient survivable networks,” in Proc. IEEE GLOBECOM, vol. 2, 1994, pp. 471–477.
[17] D.A. Schupke, C.G. Gruber, A. Autenrieth, “Optimal Configuration of p-Cycles in WDM Networks.”
[18] G. Fan, “Covering graphs by cycles,” SIAM J. Comput., vol. 5, pp. 491–496, Nov. 1992.
[19] K. Murakami, H. S. Kim, “Comparative Study on Res-toration Schemes of Survivable ATM Networks,” Pro-ceedings of IEEE Conference on Computer Communi-cations (INFOCOM 1997), Kobe, Japan, pp. 345-352, 7-12 April 1997.
[20] L. Goddyn, “A girth requirement for the double cycle cover conjecture,” in Cycles in Graphs, Annals of Discrete Mathematics. Amsterdam, The Netherlands: North-Holland, 1985, vol. 115, pp. 13–26.
[21] W. D. Grover and D. Stamatelakis, “Cycle-oriented distributed precon- figuration: Ring-like speed with mesh-like capacity for self-planning network reconfiguration,” in Proc. IEEE Int. Conf. Commun., vol. 2,1998, pp. 537–543.
[22] A. Itai, R. J. Lipton, C. H. Papadimitriou, and M. Rodeh, “Covering graphs with simple circuits,” SIAM J. Comput., vol. 10, pp. 746–750,1981.
[23] M. Médard, S. S. Lumetta, and Y. C. Tseng, “Capacity-efficient restora-
tion for optical networks,” in Proc. Opt. Fiber Commun. Conf., 2000,
pp. 207–209.
[24] M. H. MacGregor, R. R. Iraschko, and W. D. Grover, “Optimal capacity placement for path restoration in STM or ATM mesh-survivable net-works,” IEEE/ACM Trans. Networking, vol. 6, pp. 325–336, June 1988.
[25] O. J. Wasem, “An algorithm for designing rings for survivable fiber net-
works,” IEEE Trans. Rel., vol. 40, pp. 428–432, Oct. 1991.
[26] T. H. Wu, R. H. Caldwell, and M. Boyden, “A multi-period design model for survivable network architecture selection for SDH/SONET interof-fice networks,” IEEE Trans. Rel., vol. 40, pp. 417–432, Oct. 1991.
[27] T. H. Wu and S. F. Habiby, “Strategies and technologies for planning a cost-effective survivable network architecture using optical switches,” IEEE Trans. Rel., vol. 8, pp. 152–159, Feb. 1991.
[28] T. H. Wu, D. J. Kolar, and R. H. Cardwell, “Survivable network archi-tectures for broad-band fiber optic networks: Model and performance comparison,” IEEE J. Lightwave Commun., vol. 6, pp. 1698–1709, Nov.1988.
[29] P. D. Seymour, “Sums of circuits,” in Graph Theory and Related Topics, U. S. R. Murty and J. A. Bondy, Eds. New York: Academic, 1979, pp. 341–355.
[30] H. Huang and J. A. Copeland, “A series of Hamiltonian cycle based solutions to provide simple and scalable mesh optical network resilience,” IEEE Communica-tions Magazine, vol. 40, no. 11, pp. 46-51, November 2002.
[31] G. Szekeres, “Polyhedral decomposition of cubic graphs,” J. Australian Math. Soc., vol. 8, pp. 367–387, 1973.
[32] Chlamtac, I., Ganz, A. and Karimi, G., “Purely Optical Net-works for Terabit Communication,” Proceedings of the 8th IEEE INFOCOM, pp. 887–896 (1989).
[33] Hashiguchi, T., Wang, X., Morikawa, H. and Aoyama, T.,“Performance Evaluation of Distributed Wavelength As-signment in WDM Optical Network,” Network Architec-tures, Management and Applications, Vol. 5282, pp. 480–491 (2004).
[34] Li, L. and Somani, A. K., “Dynamic Wavelength Rout-ing Using Congestion and Neighborhood Information,” Pro-ceedings of the IEEE/ACM Transactions on Networking, No. 5, Vol. 7, pp. 779–786 (1999).
[35] Subramaniam, S. and Barry, A., “Wavelength Assignment in Fixed Routing WDM Networks,” Proceedings of the IEEE International Conference on Communications, pp. 406–410(1997).
[36] H. Choi, S. Subramaniam, H.-A. Choi, “Loopback recovery from double-link failures in optical mesh networks,” IEEE/ACM Transactions on Networking 12 (6) (2004) 1119–1130.
[37] W. He, A.K. Somani, “Path-based protection for surviving double-link failures in mesh-restorable optical networks,” IEEE Globecom (2003) 2558–2563.
[38] D. Schupke, “R. Prinz, Performance of path protection and rerouting for WDM networks subject to dual failures,” IEEE Optical Fiber Conference 1 (2003) 209–210.
[39] D. Schupke, R. Prinz, “Capacity efficiency and restorability of path protection and rerouting in WDM networks subject to dual failures,” Photonic Network Communications 8 (2) (2004) 191–207.
[40] J. Zhang et al, “A comprehensive study on backup reprovisioning to remedy the effect of multiple-link failures in WDM mesh networks,” IEEE Int. Conf. on Communications (2004) 1654–1658.