Abstract

We investigate the problem of routing a large number of scheduled lightpath demands (SLDs) on a wavelength-division-multiplexing (WDM) transport network. SLDs are connection demands for which the startup and tear-down dates may be planned. Existing SLD routing algorithms are able to process only a limited number of demands. So, to process a large set of SLDs, we adopt a divide-and-reassembly approach. The set of SLDs is partitioned on the physical network into different subsets so that the number of demands of each can be processed with the existing routing algorithms. The solutions of the subsets are then assembled to form a global solution for the original set of SLDs. We evaluate the gain in terms of computation time, obtained by solution of smaller instances of the routing problem, and the performance of this approach in terms of WDM resources devoted to the routing solution on the basis of partitioning the set of demands.

© 2003 Optical Society of America

PDF Article

References

  • View by:
  • |

  1. H. J. R. Dutton, Understanding Optical Communications (Prentice Hall, Engelwood Cliffs, N. J., 1998).
  2. B. Mukherjee, Optical Communication Networks (McGraw-Hill, New York, 1998).
  3. R. Ramaswami and K. N. Savarajan, 'Design of logical topology for wavelength routed optical networks,' in IEEE Infocom '95 (Institute of Electrical and Electronics Engineers, New York, 1995).
  4. J. Kuri, N. Puech, M. Gagnaire, and E. Dotaro, 'Routing and wavelength assignment of scheduled lightpath demands in a WDM optical transport network,' in Proceedings on the International Conference on Optical Communications and Networks (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 270-273.
  5. R. Ramaswami and K. N. Savarajan, Optical Networks:  A Practical Perspective (Morgan Kaufmann, Los Altos, Calif., 1998).
  6. J. Kuri, N. Puech, M. Gagnaire, and E. Dotaro, 'Routing foreseeable lightpath demands using a tabu search meta-heuristic,' in Proceedings of GLOBECOM 2002 (Institute of Electrical and Electronics Engineers, New York, 2002).
  7. R. Ramaswami, 'Multiwavelength lightwave networks for computer communications,' IEEE Commun. 31, 78-88 (1993).
  8. R. Ramaswami and K. N. Savarajan, 'Routing and wavelength assignment in all-optical networks,' IEEE/ACM Trans. Network. 3 489-500 (1995).
  9. J. Clausen, 'Branch and bound algorithms-principles and examples' (Department of Computer Science, University of Copenhagen, Copenhagen, Denmark), available online at <a href="http://www.imm.dtu.dk/~jha/">http://www.imm.dtu.dk/~jha/<?Pub Caret?></a>.
  10. F. Glover and M. Laguna, Tabu Search (Kluwer Academic, Dordrecht, The Netherlands, 1997).
  11. P. Klein and N. Young, Approximation Algorithms for Np-Hard Optimization Problems (CRC Press, Boca Raton, Fla., 1999).
  12. D. W. Matula, 'k-Components, clusters, and slicings in graphs,' SIAM (Soc. Ind. Appl. Math.) J. Appl. Math. 22, 459-480 (1972).
  13. F. Glover, E. Taillard, D. de Werra, 'A user's guide to Tabu search,' Ann. Operations Res. 41, 3-28 (1993).

Ann. Operations Res. (1)

F. Glover, E. Taillard, D. de Werra, 'A user's guide to Tabu search,' Ann. Operations Res. 41, 3-28 (1993).

GLOBECOM 2002 (1)

J. Kuri, N. Puech, M. Gagnaire, and E. Dotaro, 'Routing foreseeable lightpath demands using a tabu search meta-heuristic,' in Proceedings of GLOBECOM 2002 (Institute of Electrical and Electronics Engineers, New York, 2002).

ICOCN 2002 (1)

J. Kuri, N. Puech, M. Gagnaire, and E. Dotaro, 'Routing and wavelength assignment of scheduled lightpath demands in a WDM optical transport network,' in Proceedings on the International Conference on Optical Communications and Networks (Institute of Electrical and Electronics Engineers, New York, 2002), pp. 270-273.

IEEE Commun. (1)

R. Ramaswami, 'Multiwavelength lightwave networks for computer communications,' IEEE Commun. 31, 78-88 (1993).

IEEE Infocom '95 (1)

R. Ramaswami and K. N. Savarajan, 'Design of logical topology for wavelength routed optical networks,' in IEEE Infocom '95 (Institute of Electrical and Electronics Engineers, New York, 1995).

IEEE/ACM Trans. Network. (1)

R. Ramaswami and K. N. Savarajan, 'Routing and wavelength assignment in all-optical networks,' IEEE/ACM Trans. Network. 3 489-500 (1995).

J. Appl. Math. (1)

D. W. Matula, 'k-Components, clusters, and slicings in graphs,' SIAM (Soc. Ind. Appl. Math.) J. Appl. Math. 22, 459-480 (1972).

Other (6)

J. Clausen, 'Branch and bound algorithms-principles and examples' (Department of Computer Science, University of Copenhagen, Copenhagen, Denmark), available online at <a href="http://www.imm.dtu.dk/~jha/">http://www.imm.dtu.dk/~jha/<?Pub Caret?></a>.

F. Glover and M. Laguna, Tabu Search (Kluwer Academic, Dordrecht, The Netherlands, 1997).

P. Klein and N. Young, Approximation Algorithms for Np-Hard Optimization Problems (CRC Press, Boca Raton, Fla., 1999).

R. Ramaswami and K. N. Savarajan, Optical Networks:  A Practical Perspective (Morgan Kaufmann, Los Altos, Calif., 1998).

H. J. R. Dutton, Understanding Optical Communications (Prentice Hall, Engelwood Cliffs, N. J., 1998).

B. Mukherjee, Optical Communication Networks (McGraw-Hill, New York, 1998).

Cited By

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