Abstract

The survivable logical topology routing problem in an IP-over-WDM optical network is to map each link (u,v) in the logical topology (at the IP layer) into a lightpath between the nodes u and v in the physical topology (at the optical layer) such that failure of a physical link does not cause the logical topology to become disconnected. It is assumed that both the physical and logical topologies are at least two-edge connected. For this problem, two lines of investigation have been pursued in the literature: one pioneered by Modiano and Narula-Tam [Proc. IEEE INFOCOM, 2001, p. 348] and the other pioneered by Kurant and Thiran [Proc. Int. Conf. on Broadband Networks (BROADNETS), 2004, p. 44]. Since then there has been a great deal of research on this problem. Most of the works have not considered limitations imposed on the routings by physical capacity limits and other metrics in addition to survivability. In this paper, we first introduce two concepts: weakly survivable routing and strongly survivable routing. We then provide mathematical programming formulations for two problems. The first problem is to design a survivable lightpath routing that maximizes the logical demand satisfaction before and after a physical link failure. The second problem is to add spare capacities to the physical links to guarantee routability of all logical link demands before and after a physical link failure. We conclude with heuristics that mitigate the computational complexity of the mathematical programming formulations and with simulation results comparing these heuristics with the mathematical programming formulations.

© 2014 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.
  2. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003.
    [CrossRef]
  3. N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,” IEEE Commun. Mag., vol.  38, no. 3, pp. 72–84, 2000.
    [CrossRef]
  4. T. Lin, Z. Zhou, and K. Thulasiraman, “Logical topology survivability in IP-over-WDM networks: Survivable lightpath routing for maximum logical topology capacity and minimum spare capacity requirements,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Krakow, 2011, pp. 1–8.
  5. R. M. Karp, Reducibility Among Combinatorial Problems.New York: Plenum, 1972, ch. 8, pp. 85–103.
  6. E. Modiano and A. Narula-Tam, “Survivable routing of logical topologies in WDM networks,” in Proc. IEEE INFOCOM, Anchorage, AK, 2001, pp. 348–357.
  7. A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 6, pp. 63–69, 2007.
    [CrossRef]
  8. J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Commun. Mag., vol.  39, no. 2, pp. 81–87, 2001.
    [CrossRef]
  9. K. Lee and E. Modiano, “Cross-layer survivability in WDM-based networks,” in Proc. IEEE INFOCOM, April 2009, pp. 1017–1025.
  10. D. D.-J. Kan, A. Narula-Tam, and E. Modiano, “Lightpath routing and capacity assignment for survivable IP-over-WDM networks,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Washington, DC, 2009, pp. 37–44.
  11. M. Kurant and P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. Int. Conf. on Broadband Networks (BROADNETS), Oct. 2004, pp. 44–53.
  12. S. Lee, J.-C. Liu, and Y. Chen, “An ear-decomposition based approach for survivable routing in WDM networks,” in Proc. Int. Conf. on Advanced Information Networking and Applications (AINA), March 2005, pp. 459–464.
  13. M. S. Javed, K. Thulasiraman, M. A. Gaines, and G. Xue, “Survivability aware routing of logical topologies: On Thiran-Kurant approach, enhancements and evaluation,” in Proc. IEEE Global Communication Conf. (GLOBECOM), San Francisco, CA, 2006.
  14. M. Javed, K. Thulasiraman, and G. Xue, “Lightpaths routing for single link failure survivability in IP-over-WDM networks,” J. Opt. Commun. Netw., vol.  9, no. 4, pp. 394–401, 2007.
    [CrossRef]
  15. 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,” in Proc. IEEE INFOCOM, Rio de Janeiro, 2009, pp. 1026–1034.
  16. K. Thulasiraman, M. Javed, and G. Xue, “Primal meets dual: A generalized theory of logical topology survivability in IP-over-WDM optical networks,” in Proc. Int. Conf. on Communication Systems and Networks (COMSNETS), Bangalore, 2010, pp. 128–137.
  17. K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
    [CrossRef]
  18. C. Liu and L. Ruan, “A new survivable mapping problem in IP-over-WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 3, pp. 25–34, 2007.
    [CrossRef]
  19. H. Kerivin, D. Nace, and T.-T.-L. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Netw., vol.  13, no. 2, pp. 248–261, 2005.
    [CrossRef]
  20. D. Rajan and A. Atamtürk, Survivable Network Design: Routing of Flows and Slacks, 1st ed. Kluwer Academic, 2003, pp. 65–81.
  21. D. Rajan and A. Atamtürk, “A directed cycle-based column-and-cut generation method for capacitated survivable network design,” Networks, vol.  43, no. 4, pp. 201–211, 2004.
    [CrossRef]
  22. Y. Liu, D. Tipper, and K. Vajanapoom, “Spare capacity allocation in two-layer networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 5, pp. 974–986, 2007.
    [CrossRef]
  23. A. Haque and P. H. Ho, “A study on the design of survivable optical virtual private networks (o-VPN),” IEEE Trans. Reliab., vol.  55, no. 3, pp. 516–524, 2006.
    [CrossRef]
  24. C. Cavdar, A. Yayimli, and B. Mukherjee, “Multi-layer resilient design for layer-1 VPNs,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), San Diego, CA, 2008, pp. 1–3.
  25. Q. Deng, G. Sasaki, and C.-F. Su, “Survivable IP over WDM: an efficient mathematical programming problem formulation,” in Proc. 40th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, 2002.
  26. L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, “Fault management in IP-over-WDM networks: WDM protection versus IP restoration,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 21–33, 2002.
    [CrossRef]
  27. “Library for efficient modeling and optimization in networks (LEMON)” [Online]. Available: http://lemon.cs.elte.hu/trac/lemon .
  28. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.
  29. K. S. Ho and K. W. Cheung, “Generalized survivable network,” IEEE/ACM Trans. Netw., vol.  15, no. 4, pp. 750–760, 2007.
    [CrossRef]
  30. “SNDlib” [Online]. Available: http://sndlib.zib.de/ .

2010

K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
[CrossRef]

2007

C. Liu and L. Ruan, “A new survivable mapping problem in IP-over-WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 3, pp. 25–34, 2007.
[CrossRef]

A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 6, pp. 63–69, 2007.
[CrossRef]

M. Javed, K. Thulasiraman, and G. Xue, “Lightpaths routing for single link failure survivability in IP-over-WDM networks,” J. Opt. Commun. Netw., vol.  9, no. 4, pp. 394–401, 2007.
[CrossRef]

Y. Liu, D. Tipper, and K. Vajanapoom, “Spare capacity allocation in two-layer networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 5, pp. 974–986, 2007.
[CrossRef]

K. S. Ho and K. W. Cheung, “Generalized survivable network,” IEEE/ACM Trans. Netw., vol.  15, no. 4, pp. 750–760, 2007.
[CrossRef]

2006

A. Haque and P. H. Ho, “A study on the design of survivable optical virtual private networks (o-VPN),” IEEE Trans. Reliab., vol.  55, no. 3, pp. 516–524, 2006.
[CrossRef]

2005

H. Kerivin, D. Nace, and T.-T.-L. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Netw., vol.  13, no. 2, pp. 248–261, 2005.
[CrossRef]

2004

D. Rajan and A. Atamtürk, “A directed cycle-based column-and-cut generation method for capacitated survivable network design,” Networks, vol.  43, no. 4, pp. 201–211, 2004.
[CrossRef]

2003

2002

L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, “Fault management in IP-over-WDM networks: WDM protection versus IP restoration,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 21–33, 2002.
[CrossRef]

2001

J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Commun. Mag., vol.  39, no. 2, pp. 81–87, 2001.
[CrossRef]

2000

N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,” IEEE Commun. Mag., vol.  38, no. 3, pp. 72–84, 2000.
[CrossRef]

Ahuja, R. K.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.

Atamtürk, A.

D. Rajan and A. Atamtürk, “A directed cycle-based column-and-cut generation method for capacitated survivable network design,” Networks, vol.  43, no. 4, pp. 201–211, 2004.
[CrossRef]

D. Rajan and A. Atamtürk, Survivable Network Design: Routing of Flows and Slacks, 1st ed. Kluwer Academic, 2003, pp. 65–81.

Cavdar, C.

C. Cavdar, A. Yayimli, and B. Mukherjee, “Multi-layer resilient design for layer-1 VPNs,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), San Diego, CA, 2008, pp. 1–3.

Chen, Y.

S. Lee, J.-C. Liu, and Y. Chen, “An ear-decomposition based approach for survivable routing in WDM networks,” in Proc. Int. Conf. on Advanced Information Networking and Applications (AINA), March 2005, pp. 459–464.

Cheung, K. W.

K. S. Ho and K. W. Cheung, “Generalized survivable network,” IEEE/ACM Trans. Netw., vol.  15, no. 4, pp. 750–760, 2007.
[CrossRef]

Chiu, A. L.

J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Commun. Mag., vol.  39, no. 2, pp. 81–87, 2001.
[CrossRef]

Deng, Q.

Q. Deng, G. Sasaki, and C.-F. Su, “Survivable IP over WDM: an efficient mathematical programming problem formulation,” in Proc. 40th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, 2002.

Dixit, S.

N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,” IEEE Commun. Mag., vol.  38, no. 3, pp. 72–84, 2000.
[CrossRef]

Gaines, M. A.

M. S. Javed, K. Thulasiraman, M. A. Gaines, and G. Xue, “Survivability aware routing of logical topologies: On Thiran-Kurant approach, enhancements and evaluation,” in Proc. IEEE Global Communication Conf. (GLOBECOM), San Francisco, CA, 2006.

Ghani, N.

N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,” IEEE Commun. Mag., vol.  38, no. 3, pp. 72–84, 2000.
[CrossRef]

Haque, A.

A. Haque and P. H. Ho, “A study on the design of survivable optical virtual private networks (o-VPN),” IEEE Trans. Reliab., vol.  55, no. 3, pp. 516–524, 2006.
[CrossRef]

Ho, K. S.

K. S. Ho and K. W. Cheung, “Generalized survivable network,” IEEE/ACM Trans. Netw., vol.  15, no. 4, pp. 750–760, 2007.
[CrossRef]

Ho, P. H.

A. Haque and P. H. Ho, “A study on the design of survivable optical virtual private networks (o-VPN),” IEEE Trans. Reliab., vol.  55, no. 3, pp. 516–524, 2006.
[CrossRef]

Ishihara, K.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Javed, M.

K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
[CrossRef]

M. Javed, K. Thulasiraman, and G. Xue, “Lightpaths routing for single link failure survivability in IP-over-WDM networks,” J. Opt. Commun. Netw., vol.  9, no. 4, pp. 394–401, 2007.
[CrossRef]

K. Thulasiraman, M. Javed, and G. Xue, “Primal meets dual: A generalized theory of logical topology survivability in IP-over-WDM optical networks,” in Proc. Int. Conf. on Communication Systems and Networks (COMSNETS), Bangalore, 2010, pp. 128–137.

Javed, M. S.

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,” in Proc. IEEE INFOCOM, Rio de Janeiro, 2009, pp. 1026–1034.

M. S. Javed, K. Thulasiraman, M. A. Gaines, and G. Xue, “Survivability aware routing of logical topologies: On Thiran-Kurant approach, enhancements and evaluation,” in Proc. IEEE Global Communication Conf. (GLOBECOM), San Francisco, CA, 2006.

Kan, D. D.-J.

D. D.-J. Kan, A. Narula-Tam, and E. Modiano, “Lightpath routing and capacity assignment for survivable IP-over-WDM networks,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Washington, DC, 2009, pp. 37–44.

Karp, R. M.

R. M. Karp, Reducibility Among Combinatorial Problems.New York: Plenum, 1972, ch. 8, pp. 85–103.

Kawakami, H.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Kerivin, H.

H. Kerivin, D. Nace, and T.-T.-L. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Netw., vol.  13, no. 2, pp. 248–261, 2005.
[CrossRef]

Kobayashi, T.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Kurant, M.

M. Kurant and P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. Int. Conf. on Broadband Networks (BROADNETS), Oct. 2004, pp. 44–53.

Lee, K.

K. Lee and E. Modiano, “Cross-layer survivability in WDM-based networks,” in Proc. IEEE INFOCOM, April 2009, pp. 1017–1025.

Lee, S.

S. Lee, J.-C. Liu, and Y. Chen, “An ear-decomposition based approach for survivable routing in WDM networks,” in Proc. Int. Conf. on Advanced Information Networking and Applications (AINA), March 2005, pp. 459–464.

Lin, T.

K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
[CrossRef]

T. Lin, Z. Zhou, and K. Thulasiraman, “Logical topology survivability in IP-over-WDM networks: Survivable lightpath routing for maximum logical topology capacity and minimum spare capacity requirements,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Krakow, 2011, pp. 1–8.

Liu, C.

C. Liu and L. Ruan, “A new survivable mapping problem in IP-over-WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 3, pp. 25–34, 2007.
[CrossRef]

Liu, J.-C.

S. Lee, J.-C. Liu, and Y. Chen, “An ear-decomposition based approach for survivable routing in WDM networks,” in Proc. Int. Conf. on Advanced Information Networking and Applications (AINA), March 2005, pp. 459–464.

Liu, Y.

Y. Liu, D. Tipper, and K. Vajanapoom, “Spare capacity allocation in two-layer networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 5, pp. 974–986, 2007.
[CrossRef]

Magnanti, T. L.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.

Masuda, H.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Matsuura, A.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Miyamoto, T.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Modiano, E.

K. Lee and E. Modiano, “Cross-layer survivability in WDM-based networks,” in Proc. IEEE INFOCOM, April 2009, pp. 1017–1025.

D. D.-J. Kan, A. Narula-Tam, and E. Modiano, “Lightpath routing and capacity assignment for survivable IP-over-WDM networks,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Washington, DC, 2009, pp. 37–44.

E. Modiano and A. Narula-Tam, “Survivable routing of logical topologies in WDM networks,” in Proc. IEEE INFOCOM, Anchorage, AK, 2001, pp. 348–357.

Mukherjee, B.

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003.
[CrossRef]

L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, “Fault management in IP-over-WDM networks: WDM protection versus IP restoration,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 21–33, 2002.
[CrossRef]

C. Cavdar, A. Yayimli, and B. Mukherjee, “Multi-layer resilient design for layer-1 VPNs,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), San Diego, CA, 2008, pp. 1–3.

Nace, D.

H. Kerivin, D. Nace, and T.-T.-L. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Netw., vol.  13, no. 2, pp. 248–261, 2005.
[CrossRef]

Narula-Tam, A.

D. D.-J. Kan, A. Narula-Tam, and E. Modiano, “Lightpath routing and capacity assignment for survivable IP-over-WDM networks,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Washington, DC, 2009, pp. 37–44.

E. Modiano and A. Narula-Tam, “Survivable routing of logical topologies in WDM networks,” in Proc. IEEE INFOCOM, Anchorage, AK, 2001, pp. 348–357.

Orlin, J. B.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.

Pham, T.-T.-L.

H. Kerivin, D. Nace, and T.-T.-L. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Netw., vol.  13, no. 2, pp. 248–261, 2005.
[CrossRef]

Rajan, D.

D. Rajan and A. Atamtürk, “A directed cycle-based column-and-cut generation method for capacitated survivable network design,” Networks, vol.  43, no. 4, pp. 201–211, 2004.
[CrossRef]

D. Rajan and A. Atamtürk, Survivable Network Design: Routing of Flows and Slacks, 1st ed. Kluwer Academic, 2003, pp. 65–81.

Ramamurthy, B.

A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 6, pp. 63–69, 2007.
[CrossRef]

Ramamurthy, S.

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003.
[CrossRef]

L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, “Fault management in IP-over-WDM networks: WDM protection versus IP restoration,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 21–33, 2002.
[CrossRef]

Ruan, L.

C. Liu and L. Ruan, “A new survivable mapping problem in IP-over-WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 3, pp. 25–34, 2007.
[CrossRef]

Sahasrabuddhe, L.

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003.
[CrossRef]

L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, “Fault management in IP-over-WDM networks: WDM protection versus IP restoration,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 21–33, 2002.
[CrossRef]

Sano, A.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Sasaki, G.

Q. Deng, G. Sasaki, and C.-F. Su, “Survivable IP over WDM: an efficient mathematical programming problem formulation,” in Proc. 40th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, 2002.

Strand, J.

J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Commun. Mag., vol.  39, no. 2, pp. 81–87, 2001.
[CrossRef]

Su, C.-F.

Q. Deng, G. Sasaki, and C.-F. Su, “Survivable IP over WDM: an efficient mathematical programming problem formulation,” in Proc. 40th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, 2002.

Thiran, P.

M. Kurant and P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. Int. Conf. on Broadband Networks (BROADNETS), Oct. 2004, pp. 44–53.

Thulasiraman, K.

K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
[CrossRef]

M. Javed, K. Thulasiraman, and G. Xue, “Lightpaths routing for single link failure survivability in IP-over-WDM networks,” J. Opt. Commun. Netw., vol.  9, no. 4, pp. 394–401, 2007.
[CrossRef]

K. Thulasiraman, M. Javed, and G. Xue, “Primal meets dual: A generalized theory of logical topology survivability in IP-over-WDM optical networks,” in Proc. Int. Conf. on Communication Systems and Networks (COMSNETS), Bangalore, 2010, pp. 128–137.

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,” in Proc. IEEE INFOCOM, Rio de Janeiro, 2009, pp. 1026–1034.

T. Lin, Z. Zhou, and K. Thulasiraman, “Logical topology survivability in IP-over-WDM networks: Survivable lightpath routing for maximum logical topology capacity and minimum spare capacity requirements,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Krakow, 2011, pp. 1–8.

M. S. Javed, K. Thulasiraman, M. A. Gaines, and G. Xue, “Survivability aware routing of logical topologies: On Thiran-Kurant approach, enhancements and evaluation,” in Proc. IEEE Global Communication Conf. (GLOBECOM), San Francisco, CA, 2006.

Tipper, D.

Y. Liu, D. Tipper, and K. Vajanapoom, “Spare capacity allocation in two-layer networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 5, pp. 974–986, 2007.
[CrossRef]

Tkach, R.

J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Commun. Mag., vol.  39, no. 2, pp. 81–87, 2001.
[CrossRef]

Todimala, A.

A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 6, pp. 63–69, 2007.
[CrossRef]

Vajanapoom, K.

Y. Liu, D. Tipper, and K. Vajanapoom, “Spare capacity allocation in two-layer networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 5, pp. 974–986, 2007.
[CrossRef]

Wang, T.-S.

N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,” IEEE Commun. Mag., vol.  38, no. 3, pp. 72–84, 2000.
[CrossRef]

Xue, G.

K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
[CrossRef]

M. Javed, K. Thulasiraman, and G. Xue, “Lightpaths routing for single link failure survivability in IP-over-WDM networks,” J. Opt. Commun. Netw., vol.  9, no. 4, pp. 394–401, 2007.
[CrossRef]

K. Thulasiraman, M. Javed, and G. Xue, “Primal meets dual: A generalized theory of logical topology survivability in IP-over-WDM optical networks,” in Proc. Int. Conf. on Communication Systems and Networks (COMSNETS), Bangalore, 2010, pp. 128–137.

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,” in Proc. IEEE INFOCOM, Rio de Janeiro, 2009, pp. 1026–1034.

M. S. Javed, K. Thulasiraman, M. A. Gaines, and G. Xue, “Survivability aware routing of logical topologies: On Thiran-Kurant approach, enhancements and evaluation,” in Proc. IEEE Global Communication Conf. (GLOBECOM), San Francisco, CA, 2006.

Yamanaka, S.

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

Yayimli, A.

C. Cavdar, A. Yayimli, and B. Mukherjee, “Multi-layer resilient design for layer-1 VPNs,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), San Diego, CA, 2008, pp. 1–3.

Zhou, Z.

T. Lin, Z. Zhou, and K. Thulasiraman, “Logical topology survivability in IP-over-WDM networks: Survivable lightpath routing for maximum logical topology capacity and minimum spare capacity requirements,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Krakow, 2011, pp. 1–8.

IEEE Commun. Mag.

N. Ghani, S. Dixit, and T.-S. Wang, “On IP-over-WDM integration,” IEEE Commun. Mag., vol.  38, no. 3, pp. 72–84, 2000.
[CrossRef]

J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Commun. Mag., vol.  39, no. 2, pp. 81–87, 2001.
[CrossRef]

IEEE J. Sel. Areas Commun.

A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 6, pp. 63–69, 2007.
[CrossRef]

Y. Liu, D. Tipper, and K. Vajanapoom, “Spare capacity allocation in two-layer networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 5, pp. 974–986, 2007.
[CrossRef]

C. Liu and L. Ruan, “A new survivable mapping problem in IP-over-WDM networks,” IEEE J. Sel. Areas Commun., vol.  25, no. 3, pp. 25–34, 2007.
[CrossRef]

L. Sahasrabuddhe, S. Ramamurthy, and B. Mukherjee, “Fault management in IP-over-WDM networks: WDM protection versus IP restoration,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 21–33, 2002.
[CrossRef]

IEEE Trans. Reliab.

A. Haque and P. H. Ho, “A study on the design of survivable optical virtual private networks (o-VPN),” IEEE Trans. Reliab., vol.  55, no. 3, pp. 516–524, 2006.
[CrossRef]

IEEE/ACM Trans. Netw.

H. Kerivin, D. Nace, and T.-T.-L. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Netw., vol.  13, no. 2, pp. 248–261, 2005.
[CrossRef]

K. S. Ho and K. W. Cheung, “Generalized survivable network,” IEEE/ACM Trans. Netw., vol.  15, no. 4, pp. 750–760, 2007.
[CrossRef]

J. Lightwave Technol.

J. Opt. Commun. Netw.

M. Javed, K. Thulasiraman, and G. Xue, “Lightpaths routing for single link failure survivability in IP-over-WDM networks,” J. Opt. Commun. Netw., vol.  9, no. 4, pp. 394–401, 2007.
[CrossRef]

Networks

D. Rajan and A. Atamtürk, “A directed cycle-based column-and-cut generation method for capacitated survivable network design,” Networks, vol.  43, no. 4, pp. 201–211, 2004.
[CrossRef]

Opt. Switching Networking

K. Thulasiraman, T. Lin, M. Javed, and G. Xue, “Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks,” Opt. Switching Networking, vol.  7, no. 4, pp. 206–214, 2010.
[CrossRef]

Other

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,” in Proc. IEEE INFOCOM, Rio de Janeiro, 2009, pp. 1026–1034.

K. Thulasiraman, M. Javed, and G. Xue, “Primal meets dual: A generalized theory of logical topology survivability in IP-over-WDM optical networks,” in Proc. Int. Conf. on Communication Systems and Networks (COMSNETS), Bangalore, 2010, pp. 128–137.

C. Cavdar, A. Yayimli, and B. Mukherjee, “Multi-layer resilient design for layer-1 VPNs,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), San Diego, CA, 2008, pp. 1–3.

Q. Deng, G. Sasaki, and C.-F. Su, “Survivable IP over WDM: an efficient mathematical programming problem formulation,” in Proc. 40th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, 2002.

K. Lee and E. Modiano, “Cross-layer survivability in WDM-based networks,” in Proc. IEEE INFOCOM, April 2009, pp. 1017–1025.

D. D.-J. Kan, A. Narula-Tam, and E. Modiano, “Lightpath routing and capacity assignment for survivable IP-over-WDM networks,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Washington, DC, 2009, pp. 37–44.

M. Kurant and P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. Int. Conf. on Broadband Networks (BROADNETS), Oct. 2004, pp. 44–53.

S. Lee, J.-C. Liu, and Y. Chen, “An ear-decomposition based approach for survivable routing in WDM networks,” in Proc. Int. Conf. on Advanced Information Networking and Applications (AINA), March 2005, pp. 459–464.

M. S. Javed, K. Thulasiraman, M. A. Gaines, and G. Xue, “Survivability aware routing of logical topologies: On Thiran-Kurant approach, enhancements and evaluation,” in Proc. IEEE Global Communication Conf. (GLOBECOM), San Francisco, CA, 2006.

T. Lin, Z. Zhou, and K. Thulasiraman, “Logical topology survivability in IP-over-WDM networks: Survivable lightpath routing for maximum logical topology capacity and minimum spare capacity requirements,” in Proc. Int. Workshop on Design of Reliable Communication Networks (DRCN), Krakow, 2011, pp. 1–8.

R. M. Karp, Reducibility Among Combinatorial Problems.New York: Plenum, 1972, ch. 8, pp. 85–103.

E. Modiano and A. Narula-Tam, “Survivable routing of logical topologies in WDM networks,” in Proc. IEEE INFOCOM, Anchorage, AK, 2001, pp. 348–357.

“SNDlib” [Online]. Available: http://sndlib.zib.de/ .

A. Sano, T. Kobayashi, S. Yamanaka, A. Matsuura, H. Kawakami, T. Miyamoto, K. Ishihara, and H. Masuda, “102.3  Tb/s (224×548  Gb/s) C- and extended L-band all-Raman transmission over 240  km using PDM-64QAM single carrier FDM with digital pilot tone,” in Proc. Optical Fiber Communication Conf. (OFC/NFOEC), Los Angeles, CA, 2012, pp. 1–3.

D. Rajan and A. Atamtürk, Survivable Network Design: Routing of Flows and Slacks, 1st ed. Kluwer Academic, 2003, pp. 65–81.

“Library for efficient modeling and optimization in networks (LEMON)” [Online]. Available: http://lemon.cs.elte.hu/trac/lemon .

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (9)

Fig. 1.
Fig. 1.

Unsurvivable and survivable mappings for logical topology.

Fig. 2.
Fig. 2.

Capacitated survivability and demand satisfaction against single failure.

Fig. 3.
Fig. 3.

G6 [29].

Fig. 4.
Fig. 4.

NOBEL-GERMANY [30].

Fig. 5.
Fig. 5.

Norway [30].

Fig. 6.
Fig. 6.

DFN [30].

Fig. 7.
Fig. 7.

PDH [30].

Fig. 8.
Fig. 8.

Comparison of demand satisfaction for weak survivability (after failure).

Fig. 9.
Fig. 9.

Comparison of total spare capacities for strong survivability (after failure).

Tables (16)

Tables Icon

TABLE I Parameters and Variables Used in MILP Formulations

Tables Icon

Algorithm 1 Single-Stage Weakly Survivable Routing Design Under Capacity Constraints (WSRD-CC-SS)

Tables Icon

Algorithm 2 WSRD-CC (First Stage of Problem 1)

Tables Icon

Algorithm 3 Weakly Survivable Routing Design with Maximum Logical Capacity (MAXCAP-WSRD) (Second Stage of Problem 1)

Tables Icon

Algorithm 4 MILP for Stage 2 of Strongly Survivable Routing

Tables Icon

Algorithm 5 Stage I. Survivable Lightpath Generation by Augmentation

Tables Icon

Algorithm 6 Stage II. Find Maximal Demand Satisfaction

Tables Icon

TABLE II Physical Topologies Information

Tables Icon

TABLE III Logical Topologies Information

Tables Icon

TABLE IV Scalability of MILP Formulations for Weak Survivability

Tables Icon

TABLE V Computational Time and Performance of MILP Formulations for Weak Survivability

Tables Icon

TABLE VI Scalability of MILP Formulations for Strong Survivability

Tables Icon

TABLE VII Computational Time and Performance of MILP Formulations for Strong Survivability

Tables Icon

TABLE VIII Comparison of MILP and Heuristic Results on Demand Satisfaction After Failure (Weakly Survivable)

Tables Icon

TABLE IX Comparison of Minimum Spare Capacity Requirement Calculated by MILP and Heuristics (Strongly Survivable)

Tables Icon

TABLE X Computational Results of MILPs and Heuristics for Large Size Problem

Equations (41)

Equations on this page are rendered with MathJax. Learn more.

(i,j)EPyijst(j,i)EPyjist={1,ifi=s,1,ifi=t,0,ifi{s,t},iVP,(s,t)EL,
yijst+yjist1,(i,j)EP,(s,t)EL,
(i,j),(j,i)EP(yijst+yjist)2,iVP,(s,t)EL.
(i,j)EPfijst(j,i)EPfjist={ρst,ifi=s,ρst,ifi=t,0,ifi{s,t},iVP,(s,t)EL,
ρstdst,(s,t)EL.
fijstMyijstandfjistMyjist,(i,j)EP,(s,t)EL.
(s,t)EL(fijst+fjist)cij,(i,j)EP.
(s,t)ELrstij(t,s)ELrtsij={1,ifs=v1,1|VL|1,ifsv1,v1VL,(i,j)EP,
0rstij1(yijst+yjist),(i,j)EP,(s,t)EL,
0rtsij1(yijst+yjist),(i,j)EP,(s,t)EL.
(k,)EP{(i,j)}zkijst(,k)EP{(i,j)}zkijst={pijst,ifk=s,pijst,ifk=t,0,ifk{s,t},kVP,(s,t)EL,(i,j)EP,
zkijst+zkijst1,(i,j)EP,(k,)EP{(i,j)},(s,t)EL,
(k,),(,k)EP{(i,j)}(zkijst+zkijst)2,kVP,(i,j)EP,(s,t)EL,
zkijst+zkijstyijst+yjist,(i,j)EP,(k,)EP{(i,j)},(s,t)EL,
pijstyijst+yjist,(i,j)EP,(s,t)EL.
(k,)EP{(i,j)}xkijst(,k)EP{(i,j)}xkijst={λijst,ifk=s,λijst,ifk=t,0,ifk{s,t},kVP,(i,j)EP,(s,t)EL,
λijstdst,(s,t)EL,(i,j)EP.
(s,t)EL(xkijst+xkijst)ck(s,t)EL(ηkijst+ηkijst),(i,j),(k,)EP,(k,)(i,j),
xkijstMzkijst,xkijstMzkijst,(s,t)EL,(i,j)EP,(k,)EP{(i,j)}.
ηkijstM[1(yijst+yjist)],(i,j),(k,),(,k)EP,(k,),(,k)(i,j),(s,t)EL,
ηkijstfkstM(yijst+yjist),(i,j),(k,),(,k)EP,(k,),(,k)(i,j),(s,t)EL,
ηkijstfkst+M(yijst+yjist),(i,j),(k,),(,k)EP,(k,),(,k)(i,j),(s,t)EL,
ηkijst,λijst,xkijst0,zkijst{0,1},(s,t)EL,(i,j)EP,(k,)EP{(i,j)}.
max(s,t)ELρst+(s,t)EL(i,j)EPλijst
max(s,t)ELρst
(k,)EP{(i,j)}zkijst(,k)EP{(i,j)}zkijst={1,ifk=s,1,ifk=t,0,ifk{s,t},kVP,(s,t)Rij,(i,j)EP,
zkijst+zkijst1,(k,)EP{(i,j)},(s,t)Rij,(i,j)EP,
(k,),(,k)EP{(i,j)}(zkijst+zkijst)2,kVP,(s,t)Rij,(i,j)EP.
(s,t)Rij(xkijst+xkijst)ck(u,v)ELRijρuv*(ykuv*+ykuv*),(k,)EP{(i,j)},(i,j)EP,
xkijstMzkijst,xkijstMzkijst,(s,t)Rij,(k,)EP{(i,j)},(i,j)EP,
(k,)EP{(i,j)}xkijst(,k)EP{(i,j)}xkijst={λijst,ifk=s,λijst,ifk=t,0,ifk{s,t},kVP,(s,t)Rij,(i,j)EP,
λijstdst,(s,t)Rij,(i,j)EP.
max(i,j)EP(s,t)Rijλijst
ηkijst,λijst,xkijst0,zkijst{0,1},(s,t)Rij,(i,j)EP,(k,)EP{(i,j)}.
(s,t)EL(fijst+fjist)cij+ηij(1),(i,j)EP.
min(i,j)EPηij(1).
min(i,j)EPηij(2)
(s,t)Rijdst(zkijst+zkijst)ck+ηk(1)(s,t)ELRijdst(ykst+ykst)+ηkij,(i,j)EP,(k,)EP{(i,j)},
ηk(2)ηkij,(i,j)EP,(k,)EP{(i,j)}.
O(|EL||EP|2+(i,j)EPRij(|EP|+|VP|))
O(|EL||EP|2+(i,j)EPRij(|EP|+|VP|))