Abstract

This paper investigates the problem of dynamic survivable lightpath provisioning in optical mesh networks employing wavelength-division multiplexing (WDM). In particular, we focus on shared-path protection because it is resource efficient due to the fact that backup paths can share wavelength links when their corresponding working paths are mutually diverse. Our main contributions are as follows. 1) First, we prove that the problem of finding an eligible pair of working and backup paths for a new lightpath request requiring shared-path protection under the current network state is NP-complete. 2) Then, we develop a heuristic, called CAFES, to compute a feasible solution with high probability. 3) Finally, we design another heuristic, called OPT, to optimize resource consumption for a given solution. The merits of our approaches are that they capture the essence of shared-path protection and approach to optimal solutions without enumerating paths. We evaluate the effectiveness of our heuristics and the results are found to be promising.

© 2004 IEEE

PDF Article

References

  • View by:
  • |

  1. E. Bouillet, J.-F. Labourdette, G. Ellinas, R. Ramamurthy and S. Chaudhuri, "Stochastic approaches to compute shared mesh restored lightpaths in optical network architectures", in Proc. IEEE INFOCOM, June 2002, pp. 801-807.
  2. E. Bouillet, J.-F. Labourdette, R. Ramamurthy and S. Chaudhuri, "Enhanced algorithm cost model to control tradeoffs in provisioning shared mesh restored lightpaths", in Proc. OFC, Mar. 2002, p. ThW2.
  3. T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, New York: McGraw-Hill, 1990.
  4. O. Crochat, J.-Y. Le Boudec and O. Gerstel, "Protection interoperability for WDM optical networks", IEEE/ACM Trans. Networking, vol. 8, pp. 384-395, June 2000.
  5. B. T. Doshi, S. Dravida, P. Harshavardhana, O. Hauser and Y. Wang, "Optical network design and restoration", Bell Labs Tech. J., vol. 4, pp. 58-84, Jan.-Mar. 1999.
  6. D. Dunn, W. Grover and M. MacGregor, "Comparison of k-shortest paths and maximum flow routing for network facility restoration", IEEE J. Select. Areas Commun., vol. 12, pp. 88-99, Jan. 1994.
  7. D. Elie-Dit-Cosaque, M. Ali and L. Tancevski, "Informed dynamic shared path protection", in Proc. OFC, Mar. 2002, p. ThO4.
  8. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , New York: W. H. Freeman, 1979 .
  9. J. Iness and B. Mukherjee, "Sparse wavelength conversion in wavelength-routed WDM networks", J. Photonic Network Commun., vol. 1, pp. 183-205, Nov. 1999.
  10. M. Kodialam and T. V. Lakshman, "Dynamic routing of bandwidth guaranteed tunnels with restoration", in Proc. IEEE INFOCOM, vol. 2, Mar. 2000, pp. 902-911.
  11. M. Kodialam and T. V. Lakshman, "Dynamic routing of locally restorable bandwidth guaranteed tunnels using aggregated link usage information", in Proc. IEEE INFOCOM, vol. 1, Apr. 2001, pp. 376-385.
  12. G. Li, D. Wang, C. Kalmanek and R. Doverspike, "Efficient distributed path selection for shared restoration connections", in Proc. IEEE INFOCOM , June 2002, pp. 140-149.
  13. Y. Liu, D. Tipper and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing", in Proc. IEEE INFOCOM , vol. 2, Apr. 2001, pp. 699-708.
  14. S. S. Lumetta, M. Medard and Y.-C. Tseng, "Capacity versus robustness: a tradeoff for link restoration in mesh networks", J. Lightwave Technol., vol. 18, pp. 1765-1775, Dec. 2000.
  15. E. Modiano and A. Narula-Tam, "Survivable lightpath routing: A new approach to the design of WDM-based networks", IEEE J. Selected Areas in Communications , vol. 20, pp. 800-809, May 2002.
  16. G. Mohan, C. S. R. Murthy and A. K. Somani, "Efficient algorithms for routing dependable connections in WDM optical networks", IEEE/ACM Trans. Networking , vol. 9, pp. 553-566, Oct. 2001.
  17. C. Qiao and D. Xu, "Distributed Partial Information Management (DPIM) schemes for survivable networks-Part I", in Proc. IEEE INFOCOM, June 2002, pp. 302-311.
  18. R. Ramamurthy, Z. Bogdanowicz, S. Samieian, D. Saha, B. Rajagopalan, S. Sengupta, S. Chaudhuri and K. Bala, "Capacity performance of dynamic provisioning in optical networks", J. Lightwave Technol., vol. 19, pp. 40-48, Jan. 2001.
  19. S. Ramamurthy, L. Sahasrabuddhe and B. Mukherjee, "Survivable WDM mesh networks", J. Lightwave Technol., vol. 21, pp. 870-883, Apr. 2003.
  20. C. Su and X. Su, "Protection path routing on WDM networks", in Proc. OFC, vol. 2, Mar. 2001, pp. TuO2-T1-TuO2-T3.
  21. X. Su and C. Su, "An online distributed protection algorithm in WDM networks", in Proc. IEEE ICC, vol. 5, June 2001, pp. 1571-1575.
  22. J. W. Suurballe and R. E. Tarjan, "A quick method for finding shortest pairs of disjoint paths", Networks, no. 14, pp. 325-336, 1984.
  23. B. Van Caenegem, W. Van Parys, F. De Turck and P. Demeester, "Dimensioning of survivable WDM networks", IEEE J. Select. Areas Commun., vol. 16, pp. 1146-1157, Sept. 1998.
  24. C. Xin, Y. Ye, S. Dixit and C. Qiao, "A joint working and protection path selection approach in WDM optical networks", in Proc. IEEE Globecom , vol. 4, 2001, pp. 2165-2168.
  25. Y. Xiong, D. Xu and C. Qiao, "Achieving fast and bandwidth-efficient shared-path protection", IEEE J. Lightwave Technology, vol. 21, pp. 365 -371, Feb. 2003.

J. Lightwave Technol. (3)

Other (22)

E. Modiano and A. Narula-Tam, "Survivable lightpath routing: A new approach to the design of WDM-based networks", IEEE J. Selected Areas in Communications , vol. 20, pp. 800-809, May 2002.

G. Mohan, C. S. R. Murthy and A. K. Somani, "Efficient algorithms for routing dependable connections in WDM optical networks", IEEE/ACM Trans. Networking , vol. 9, pp. 553-566, Oct. 2001.

C. Qiao and D. Xu, "Distributed Partial Information Management (DPIM) schemes for survivable networks-Part I", in Proc. IEEE INFOCOM, June 2002, pp. 302-311.

C. Su and X. Su, "Protection path routing on WDM networks", in Proc. OFC, vol. 2, Mar. 2001, pp. TuO2-T1-TuO2-T3.

X. Su and C. Su, "An online distributed protection algorithm in WDM networks", in Proc. IEEE ICC, vol. 5, June 2001, pp. 1571-1575.

J. W. Suurballe and R. E. Tarjan, "A quick method for finding shortest pairs of disjoint paths", Networks, no. 14, pp. 325-336, 1984.

B. Van Caenegem, W. Van Parys, F. De Turck and P. Demeester, "Dimensioning of survivable WDM networks", IEEE J. Select. Areas Commun., vol. 16, pp. 1146-1157, Sept. 1998.

C. Xin, Y. Ye, S. Dixit and C. Qiao, "A joint working and protection path selection approach in WDM optical networks", in Proc. IEEE Globecom , vol. 4, 2001, pp. 2165-2168.

Y. Xiong, D. Xu and C. Qiao, "Achieving fast and bandwidth-efficient shared-path protection", IEEE J. Lightwave Technology, vol. 21, pp. 365 -371, Feb. 2003.

E. Bouillet, J.-F. Labourdette, G. Ellinas, R. Ramamurthy and S. Chaudhuri, "Stochastic approaches to compute shared mesh restored lightpaths in optical network architectures", in Proc. IEEE INFOCOM, June 2002, pp. 801-807.

E. Bouillet, J.-F. Labourdette, R. Ramamurthy and S. Chaudhuri, "Enhanced algorithm cost model to control tradeoffs in provisioning shared mesh restored lightpaths", in Proc. OFC, Mar. 2002, p. ThW2.

T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, New York: McGraw-Hill, 1990.

O. Crochat, J.-Y. Le Boudec and O. Gerstel, "Protection interoperability for WDM optical networks", IEEE/ACM Trans. Networking, vol. 8, pp. 384-395, June 2000.

B. T. Doshi, S. Dravida, P. Harshavardhana, O. Hauser and Y. Wang, "Optical network design and restoration", Bell Labs Tech. J., vol. 4, pp. 58-84, Jan.-Mar. 1999.

D. Dunn, W. Grover and M. MacGregor, "Comparison of k-shortest paths and maximum flow routing for network facility restoration", IEEE J. Select. Areas Commun., vol. 12, pp. 88-99, Jan. 1994.

D. Elie-Dit-Cosaque, M. Ali and L. Tancevski, "Informed dynamic shared path protection", in Proc. OFC, Mar. 2002, p. ThO4.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , New York: W. H. Freeman, 1979 .

J. Iness and B. Mukherjee, "Sparse wavelength conversion in wavelength-routed WDM networks", J. Photonic Network Commun., vol. 1, pp. 183-205, Nov. 1999.

M. Kodialam and T. V. Lakshman, "Dynamic routing of bandwidth guaranteed tunnels with restoration", in Proc. IEEE INFOCOM, vol. 2, Mar. 2000, pp. 902-911.

M. Kodialam and T. V. Lakshman, "Dynamic routing of locally restorable bandwidth guaranteed tunnels using aggregated link usage information", in Proc. IEEE INFOCOM, vol. 1, Apr. 2001, pp. 376-385.

G. Li, D. Wang, C. Kalmanek and R. Doverspike, "Efficient distributed path selection for shared restoration connections", in Proc. IEEE INFOCOM , June 2002, pp. 140-149.

Y. Liu, D. Tipper and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing", in Proc. IEEE INFOCOM , vol. 2, Apr. 2001, pp. 699-708.

Cited By

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