© 2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Networking
Volume 9 Number 1, February 2001

Table of Contents for this issue

Complete paper in PDF format

On the Wavelength Assignment Problem in Multifiber WDM Star and Ring Networks

Guangzhi Li, Member, IEEE and Rahul Simha Member, IEEE

Page 60.

Abstract:

This paper studies the off-line wavelength assignment problem in star and ring networks that deploy multiple fibers between nodes and use wavelength division multiplexing (WDM) for transmission. The results in this paper show that the ability to switch between fibers increases wavelength utilization. In particular, sharper per-fiber bounds on the number of required wavelengths are derived for the multifiber version of the assignment problem in star and ring networks. Additionally, the complexity of the problem is studied and several constrained versions of the problem are also considered for star and ring networks. A summary of contributions is provided in the first section.

References

  1. A. Acampora, "The scalable lightwave network", IEEE Commun. Mag., pp.  36-42, Dec.  1994.
  2. R. A. Barry and P. A. Humblet, "Models of blocking probability in all optical networks with and without wavelength changers", IEEE J. Select. Areas Commun., vol. 14, pp.  858-867, June  1996.
  3. B. Beauquier, J. C. Bermond, L. Gargano, P. Hell, S. Perennes and U. Vaccaro, "Graph problems arising from wavelength routing in all optical networks", in Proc. 2nd Workshop Optics and Computer Science, Apr. 1997.
  4. A. Blum, "Algorithms for approximate graph coloring", J. ACM, vol. 41, no. 4, pp.  630-647, July  1994.
  5. X. Zhang, C. Qiao and L. Zhao, "Scheduling all-to-all connections in wdm rings", in SPIE Proc. All Optical Communication Systems: Architecture, Control and Network Issues, vol. 2919, 1996, pp.  218- 229. 
  6. H. Choi, H-A. Choi and M. Azizoglu, "Efficient scheduling of transmissions in optical broadcast networks", IEEE/ACM Trans. Networking, vol. 4, pp.  913-920,  Dec.  1996.
  7. T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithm, New York: McGraw-Hill, 1994, p.  56. 
  8. T. Erlebach and K. Jansen, "The complexity of call-scheduling in trees, rings and meshes", in 30th Hawaii Int. Conf. System Sciences, Mar. 1997.
  9. M. Garey, D. Johnson, G. Miller and C. Papadimitriou, "The complexity of coloring circular arcs and chords", SIAM J. Disc. Math., vol. 1, no. 2, pp.  216-227, June  1980.
  10. O. Gerstel, R. Ramaswami and G. Sasaki, "Dynamic channel assignment for wdm optical networks with little or no wavelength conversion", in Proc. 1996 Allerton Conf., 1996.
  11. E. J. Harder, "Routing and wavelength assignment in all-optical WDM wavelength-routed networks", Ph.D. dissertation, George Washington University, Washington, D.C., May 1998.
  12. G. Jeong and E. Ayanoglu, "Comparison of wavelength-interchanging and wavelength-selective cross-connects in multiwavelength all-optical networks", in Proc. IEEE INFOCOM, vol. 1, Mar. 1996, pp.  156-163. 
  13. G. Li and R. Simha, "On bounds for the wavelength assignment problem in optical ring networks", J. High-Speed Networks, vol. 8, pp.  303-309, 1999.
  14. G. Li and R. Simha, "New results for the wavelength assignment problem in tree and ring networks", in ACM-SouthEast, Mobile, AL, 1999.
  15. D. Matula, G. Marble and J. Isaacson, "Graph-coloring algorithms", 1972.
  16. B. Mukherjee, "WDM-based local lightwave networks-Part II: Multihop systems", IEEE Network Mag., pp.  20-31, July  1992.
  17. B. Mukherjee, Optical Communication Networks, New York: McGraw-Hill, 1997.
  18. T. Nishizeki and K. Kashiwagi, "On the 1.1 edge-coloring of multigraphs", SIAM J. Disc. Math., vol. 3, no. 3, pp.  391-410, August  1990.
  19. P. Raghavan and E. Upfal, "Efficient routing in all-optical networks", in Proc. 26th ACM Symp. Theory of Computing, 1994, pp.  134-143. 
  20. R. Ramaswami and G. Sasaki, "Multiwavelength optical networks with limited wavelength conversion", in Proc. IEEE INFOCOM, 1997, pp.  489-498. 
  21. R. Ramaswami and K. N. Sivarajan, "Routing and wavelength assignment in all-optical networks", IEEE/ACM Trans. Networking, vol. 3, pp.  489-500,  Oct.  1995.
  22. R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective, San Mateo, CA: Morgan-Kaufman, 1998 .
  23. S. Subramaniam, M. Azizoglu and A. K. Somani, "All optical networks with sparse wavelength conversion", IEEE/ACM Trans. Networking, vol. 4, pp.  544-557,  Aug.  1996.
  24. S. Subramaniam and R. Barry, "Wavelength assignment in fixed routing WDM networks", in Proc. IEEE Int. Conf. Communications, May 1997, pp.  406-410. 
  25. A. Tucker, "Coloring a family of circular arcs", SIAM J. Appl. Math., vol. 29, no. 3, pp.  493-502, Nov.  1975.