在IP-over-WDM網路中，給定一邏輯拓樸和一實體拓樸，找尋邏輯拓樸上的
邊對於實體拓樸的映對使得任一實體節點或實體鏈結斷裂時，不會使得邏輯拓樸
不連通，我們稱之為一個存活性映對問題。由於找尋是否有存活性映射的存在是
一個NP-Complete問題，有許多的啟發式演算法被提出來。前人的研究中顯示出
針對鏈結或節點的啟發式演算法是可以被設計出來的，在本篇論文當中，我們將
設計一個啟發式的演算法可以有效的容忍一個節點的斷裂。我們的演算法分成兩
個部分，藉由鬆散漢米爾頓迴圈演算法包含所有的邏輯節點以及二分節點映對迴
路轉換確保其連通性，以增加映對的存活性。實驗結果顯示出我們所提出的演算
法對於解決存活性映對問題皆有不錯的效能。

In an IP-over-WDM networks with logical graph GL and physical graph GP , a surviv-
able mapping problem is to find a mapping in physical layer so that any failure (node or
link) in physical topology doesn’t break down the logical topology’s connection. It is a
NP-complete problem to determine whether a survivable mapping exists or not, so many
heuristic algorithms have been proposed. Previous works shows they can protect link
failure or node failure. In this paper, an heuristic mapping design strategy is proposed
to let the lightpaths endure node failure more efficiently. It uses relaxed hamiltonian
cycle algorithm to cover all of the logical nodes. After that it uses bipartite node disjoint
mapping and cycle transformation iteratively in order to guarantee the connectivity and
improve the survivability. The simulation shows that our proposed algorithm can have a
better performance for providing survivable mapping in IP-over-WDM networks.

[1] SNDlib http://sndlib.zib.de/home.action
[2] J. Armitage, O. Crochat, and J. Y. Le Boudec., ”Design of a Survivable WDM
Photonic Network”. Proceedings of IEEE INFOCOM 97, April 1997
[3] Bhandari, Ramesh , ”Suurballe’s disjoint pair algorithms”, Survivable Networks: Algorithms for Diverse Routing, Springer-Verlag, pp. 86-91, 1999.
[4] O. Crochat, J. Boudec, and O. Gerstel, ”Protection Interoperability for WDM Optical Networks,” IEEE/ACM Trans. on Networking, vol. 8, no. 3, June 2000.
[5] G. Calinescu, O. Frieder, and P.J. Wan, ”Minimizing Electronic Line Terminals for Automatic Ring Protection in General WDM Optical Networks”, IEEE Journal on Selected Areas in Communications,vol. 20, no. 1,pp.183-189, Jan.2002.
[6] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, ”Dijkstra’s algorithm”, Introduction to Algorithms, Section 24.3, pp. 595 − 601, 2001.
[7] Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford, ”Johnson’s algorithm for sparse graphs”, Introduction to Algorithms, Section 25.3, pp. 636
- 640, 2001.
[8] Ashay Dharwadker, ”A New Algorithm for finding Hamiltonian Circuits” Proceedings of the Institute of Mathematics, Amazon Books, 2004.
[9] F. Ducatelle and L. Gambardella, ”FastSurv: A New Efficient Local Search Algorithm for Survivable Routing in WDM Networks” , IEEE Globecom, pp. 1925-1929, 2004.
[10] Q. Deng, G. Sasaki, and C.-F. Su, ”Survivable IP over WDM: an efficient mathematical programming problem formulation,” Proc. Allerton Conference on Communication, Control and Computing 2002.
[11] A. Fumagalli and L.Valcarenghi, ”IP Restoration vs. WDM protection: Is There an Optimal Choice?” IEEE Network, Iss. 6, Vol.14, pp. 34–41, 2000.
[12] J. Gross and J. Yellen. ”Graph Theory and its Applications.” CRC Press, 1999.
[13] M. Kurant and P. Thiran, ”Survivable Mapping Algorithm by Ring Trimming(SMART) for Large IP-over-WDM Networks”, Broadband Networks, pp. 44-53, 2004.
[14] M. Kurant and P. Thiran, ”Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction”, IEEE Journal on Selected Areas in Communications
, Vol. 25, No. 5, pp. 922-933, 2007.
[15] Jonathan L Gross, Jay Yellen, ”Graph Theory and its applications, second edition”, 2006.
[16] C. Liu and L. Ruan, ”A new survivable mapping problem in IP-over-WDM networks,” IEEE Journal on Selected Areas in Communications, vol. 25, pp. 2534, 2007.
[17] A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C-N. Chuah, and C. Diot., ”Characterization of Failures in an IP Backbone.” Proc. of IEEE INFOCOM04, 2004.
[18] E. Modiano and A. Narula-Tam, ”Survivable Lightpath Routing: A New Approach to the Design of WDM-based Networks”, IEEE Journal on Selected Areas in Communications, Vol. 20, No. 4, pp. 800-809, 2002.
[19] Bakhe Nleya, Emmanuel Nyakwende, ”Survivability: Wavelength Recovery for Node and Link Failure in All Optical Networks”, IEEE 2008 Third International Conference on Broadband Communications, Information Technology and Biomedical Applications, pp. 492 - 498, 2008.
[20] Y. Perl and Y. Shiloach, ”Finding two disjoint paths between two pairs of vertices in a graph”, Journal of the ACM , Vol. 25, No.1, pp. 1-9, Jan. 1978.
[21] Norbert Radics, Lajos Bajzik, and Zsolt Lakatos,”Survivable Mapping of Virtual Topologies for Double-Node Failure,” IEEE/ACM TRANSACTIONS ON NETWORKING, pp. 1-14, 2014.
[22] S. Ramamuthy and B. Mukherjee, ”Survivable WDM mesh networks: Part IProtection”, Infocom99, New York, Mar. 1999.
[23] S. Ramamuthy and B. Mukherjee, ”SurvivableWDM mesh networks: Part IIRestoration,” ICC99 , Vancouver, CA, June 1999.
[24] Arunabha Sen, Bin Hao, and Bao Hong Shen, Survivable routing in WDM networks, Seventh International Symposium on Computers and Communications, pp. 726-731, July 2002.
[25] K. Thulasiraman and M. N. S. Swamy, Graphs: Theory and Algorithms, Wiley, 1992.
[26] K. Thulasiraman, M. S. Javed, and G. Xue, ”Circuits/ Cutsets duality and a unified algorithmic framework for survivable logical topology design in IP-over-WDM optical
networks,” IEEE INFOCOM, 2009.
[27] K. Thulasiraman, M. Javed, and G. Xue, ”Primal meets dual: A generalized theory of logical topology survivability in IP-over-WDM optical networks,” Second International Conference on Communication Systems and Networks, 2010.
[28] K. Thulasiraman, T. Lin, M. Javed, and G. Xue, ”Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,”
Optical Switching and Networking, pp. 206214, 2010.
[29] K. Thulasiraman, T. Lin, Z. Zhou, S. Sahni, and G. Xue, ”Unified Mathematical Programming Frameworks for Survivable Logical Topology Routing in IP-over-WDM Optical Networks,” Optical Communication and Networking, pp. 190202, 2014.
[30] D. West, Introduction to Graph Theory, Prentice Hall, 1996.
[31] J.Y. Wei, ”Advances in the management and control of optical Internet,” IEEE Journal on Selected Areas in Communications, Vol. 20, No. 4, pp. 768-785, May 2002.
[32] L. Zhang and N. Zhang, ”Survivable virtual topology design for single node failure,” Proc. IEEE ICCRD, 2009, pp. 465−467.