Abstract

In this paper, we study shortest-path routing in wavelength-routed optical networks with an objective to optimize the average-case running time for path computation. Four fast routing algorithms are proposed for dynamically computing the shortest lightpaths or semilightpaths in a network with or without wavelength converters. To reduce the average-case running time for path computation, sequential search, backward routing, and informed search are used in the algorithm design. Simulation results show that the proposed algorithms can significantly reduce the average-case computational overhead for path computation as compared with existing algorithms.

© 2008 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. J. Zheng, H. T. Mouftah, Optical WDM Networks: Concepts and Design Principles (Wiley-IEEE, 2004).
  2. A. Girard, Routing and Dimensioning in Circuit-Switched Networks (Addison-Wesley, 1990).
  3. S. Ramamurthy, B. Mukherjee, "Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks," Proc. IEEE Globecom'98 (1998) pp. 2295-2302.
  4. J. P. Jue, G. Xiao, "An adaptive routing algorithm for wavelength-routed optical networks with a distributed control scheme," Proc. IEEE IC3N'00 (2000) pp. 192-197.
  5. P.-H. Ho, H. T. Mouftah, "An approach for enhancing fixed alternate routing in dynamic WDM-routed WDM networks," Proc. IEEE Globecom'02 (2001) pp. 2799-2804.
  6. B. Zhou, H. T. Mouftah, "Adaptive least loaded routing for multi-fiber WDM networks using approximate congestion information," Proc. IEEE ICC'02 (2002) pp. 2745-2749.
  7. X. Chu, J. Liu, "DLCR: A new adaptive routing scheme in WDM mesh networks," Proc. IEEE ICC'05 (2005) pp. 1797-1801.
  8. R. Ramaswami, A. Segall, "Distributed network control for optical networks," IEEE/ACM Trans. Netw. 5, 936-943 (1997).
  9. H. Zang, L. Sahasrabuddhe, J. P. Jue, S. Ramamurthy, B. Mukherjee, "Connection management for wavelength-routed WDM networks," Proc. IEEE GLOBECOM'99 (1999) pp. 1428-1432.
  10. A. Mokhtar, M. Azizoglu, "Adaptive wavelength routing in all-optical networks," IEEE/ACM Trans. Netw. 6, 197-206 (1998).
  11. I. Chlamtac, A. Farago, T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, 909-913 (1996).
  12. W. Liang, X. Shen, "Improved lightpath (wavelength) routing in large WDM networks," IEEE Trans. Commun. 48, 1571-1579 (2000).
  13. G. Xue, "Optimal lightpath routing and rerouting in WDM networks," Proc. IEEE GLOBECOM'01 (2001) pp. 2124-2128.
  14. P.-H. Ho, H. T. Mouftah, "Toward optimal routing of lightpaths in dynamic WDM networks," Proc. IEEE ISCC 2003 pp. 672-677.
  15. J. Zheng, H. T. Mouftah, "Distributed lightpath control based on destination routing for wavelength-routed WDM networks," SPIE Opt. Netw. Mag. 3, 38-46 (2002).
  16. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms (MIT Press, 2001).
  17. P. E. Hart, N. J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE Trans. Syst. Sci. Cybern. SSC-4, 100-107 (1968).
  18. G. Liu, K. G. Ramakrishnan, "A+ Prune: An algorithm for finding K shortest paths subject to multiple constraints," Proc. IEEE INFOCOM'01 (2001) pp. 743-749.
  19. C. Chen, S. Banerjee, "A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks," Proc. IEEE INFOCOM'96 (1996) pp. 164-171.

2002 (1)

J. Zheng, H. T. Mouftah, "Distributed lightpath control based on destination routing for wavelength-routed WDM networks," SPIE Opt. Netw. Mag. 3, 38-46 (2002).

2000 (1)

W. Liang, X. Shen, "Improved lightpath (wavelength) routing in large WDM networks," IEEE Trans. Commun. 48, 1571-1579 (2000).

1998 (1)

A. Mokhtar, M. Azizoglu, "Adaptive wavelength routing in all-optical networks," IEEE/ACM Trans. Netw. 6, 197-206 (1998).

1997 (1)

R. Ramaswami, A. Segall, "Distributed network control for optical networks," IEEE/ACM Trans. Netw. 5, 936-943 (1997).

1996 (1)

I. Chlamtac, A. Farago, T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, 909-913 (1996).

1968 (1)

P. E. Hart, N. J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE Trans. Syst. Sci. Cybern. SSC-4, 100-107 (1968).

IEEE J. Sel. Areas Commun. (1)

I. Chlamtac, A. Farago, T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, 909-913 (1996).

IEEE Trans. Commun. (1)

W. Liang, X. Shen, "Improved lightpath (wavelength) routing in large WDM networks," IEEE Trans. Commun. 48, 1571-1579 (2000).

IEEE Trans. Syst. Sci. Cybern. (1)

P. E. Hart, N. J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE Trans. Syst. Sci. Cybern. SSC-4, 100-107 (1968).

IEEE/ACM Trans. Netw. (2)

A. Mokhtar, M. Azizoglu, "Adaptive wavelength routing in all-optical networks," IEEE/ACM Trans. Netw. 6, 197-206 (1998).

R. Ramaswami, A. Segall, "Distributed network control for optical networks," IEEE/ACM Trans. Netw. 5, 936-943 (1997).

SPIE Opt. Netw. Mag. (1)

J. Zheng, H. T. Mouftah, "Distributed lightpath control based on destination routing for wavelength-routed WDM networks," SPIE Opt. Netw. Mag. 3, 38-46 (2002).

Other (13)

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms (MIT Press, 2001).

H. Zang, L. Sahasrabuddhe, J. P. Jue, S. Ramamurthy, B. Mukherjee, "Connection management for wavelength-routed WDM networks," Proc. IEEE GLOBECOM'99 (1999) pp. 1428-1432.

G. Liu, K. G. Ramakrishnan, "A+ Prune: An algorithm for finding K shortest paths subject to multiple constraints," Proc. IEEE INFOCOM'01 (2001) pp. 743-749.

C. Chen, S. Banerjee, "A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks," Proc. IEEE INFOCOM'96 (1996) pp. 164-171.

G. Xue, "Optimal lightpath routing and rerouting in WDM networks," Proc. IEEE GLOBECOM'01 (2001) pp. 2124-2128.

P.-H. Ho, H. T. Mouftah, "Toward optimal routing of lightpaths in dynamic WDM networks," Proc. IEEE ISCC 2003 pp. 672-677.

J. Zheng, H. T. Mouftah, Optical WDM Networks: Concepts and Design Principles (Wiley-IEEE, 2004).

A. Girard, Routing and Dimensioning in Circuit-Switched Networks (Addison-Wesley, 1990).

S. Ramamurthy, B. Mukherjee, "Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks," Proc. IEEE Globecom'98 (1998) pp. 2295-2302.

J. P. Jue, G. Xiao, "An adaptive routing algorithm for wavelength-routed optical networks with a distributed control scheme," Proc. IEEE IC3N'00 (2000) pp. 192-197.

P.-H. Ho, H. T. Mouftah, "An approach for enhancing fixed alternate routing in dynamic WDM-routed WDM networks," Proc. IEEE Globecom'02 (2001) pp. 2799-2804.

B. Zhou, H. T. Mouftah, "Adaptive least loaded routing for multi-fiber WDM networks using approximate congestion information," Proc. IEEE ICC'02 (2002) pp. 2745-2749.

X. Chu, J. Liu, "DLCR: A new adaptive routing scheme in WDM mesh networks," Proc. IEEE ICC'05 (2005) pp. 1797-1801.

Cited By

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