Abstract

We consider off-line capacity assignment in wavelength-routed ring networks with path restoration under arbitrary traffic patterns. We present service and restoration wavelength-assignment (WA) algorithms under shortest-path routing and analyze their performance in terms of the wavelength requirement. We obtain bounds to the wavelength requirement, using a routing-independent traffic parameter, and we show that both the service wavelength requirement and the total wavelength requirement under these algorithms lie within a factor of 2 of the optimal that can be achieved by any routing and WA algorithm. These results are among the few analytical results regarding the wavelength requirement in rings without wavelength conversion. We also propose vertex-coloring-based WA algorithms and demonstrate their efficiency through performance bounds and simulations. Results also show that knowledge of which link failed provides little capacity savings, and hence our algorithm with failure-independent restoration WA offers an attractive solution to reduce the fault-monitoring costs and the restoration signaling complexity.

© 2002 Optical Society of America

PDF Article

References

  • View by:
  • |

  1. R. Ramaswami and G. H. Sasaki, “Multiwavelength optical networks with limited wavelength conversion,” in Proceedings of I.E.E.E. Infocom ’97: The Conference on Computer Communications (Institute of Electrical and Electronics Engineers, New York, 1997), pp. 490–499.
  2. J. Simmons, E. Goldstein, and A. Saleh, “On the value of wavelength add/drop in WDMrings with uniform traffic,” in Optical Fiber Communication Conference (OFC), Vol. 2 of 1998 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1998), pp. 361–362.
  3. R. A. Barry and S. Subramaniam, “The MAX-SUM wavelength assignment algorithm for WDM ring networks,” in Optical Fiber Communication Conference (OFC), Vol. 6 of 1997 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1997), pp. 121–122.
  4. T. Wu and R. C. Lau, “A class of self-healing ring architectures for SONET network applications,” in Proceedings of Globecom ’96: IEEE Global Telecommunications Conference (Institute of Electrical and Electronics Engineers, New York, 1990), pp. 403.2.1–403.2.8.
  5. O. Gerstel, R. Ramaswami, and G. H. Sasaki, “Fault tolerant multiwavelength optical rings with limited wavelength conversion,” IEEE J. Sel. Areas Commun. 14, 1166–1178 (1998).
  6. G. Ellinas, K. Bala, and G. K. Chang, “A novel wavelength assignment algorithm for 4-fiber WDM self-healing rings,” in Proceedings of the International Conference on Communications ’98 (Institute of Electrical and Electronics Engineers, New York, 1997), pp. 197–201.
  7. S. Baroni, P. Bayvel, R. Gibbens, and S. Korotky, “Analysis and design of resilient multifiber wavelength-routed optical transport networks,” IEEE J. Lightwave Technol. 17, 743–757 (1999).
  8. M. Garey, D. Johnson, G. Miller, and C. Papadimitiou, “The complexity of coloring circular arcs and chords,” SIAM (Soc. Ind. Appl. Math.) J. Disc. Math. 1, 216–227 (1980).
  9. A. Narula-Tam, P. Lin, and E. Modiano, “Efficient routing and wavelength assignment for reconfigurable WDM networks,” IEEE J. Sel. Areas Commun. 20, 75–88 (2002).
  10. G. Sahin and M. Azizoglu, “Optical layer survivability: single service-class case,” in OptiComm 2000: Optical Networking and Communications, I. Chlamtac, ed., Proc. SPIE 4233, 267–278 (2000).
  11. H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: end-to-end recovery using local failure information,” Tech. Rep., MIT Laboratory for Information and Decision Systems (September 2001), <a href= "http://truth.mit.edu/~modiano/papers/T5.pdf">http://truth.mit.edu/~modiano/papers/T5.pdf</a>.
  12. G. Sahin and M. Azizoglu, “An efficient wavelength assignment algorithm for service and restoration in WDM rings,” in Optical Fiber Communication Conference (OFC) (Optical Society of America, Washington, D.C., 2001), pp. TuO4-1–TuO4-2.
  13. G. Li and R. Simha, “On bounds for the wavelength assignment problem in optical ring networks,” J. High Speed Netw. 8, 303–309 (2001).
  14. M. Swamy and K. Thulasiraman, Graphs, Networks, and Algorithms (Wiley, New York, 1981).
  15. R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective (Morgan Kaufmann, Los Altos, Calif., 1998), pp. 371–372, 436–437.
  16. G. Sahin and M. Azizoglu, “Optical layer survivability for single and multiple service classes,” J. High Speed Netw. 10, 91–108, special issue on Survivable Optical Networks (2001).

IEEE J. Lightwave Technol. (1)

S. Baroni, P. Bayvel, R. Gibbens, and S. Korotky, “Analysis and design of resilient multifiber wavelength-routed optical transport networks,” IEEE J. Lightwave Technol. 17, 743–757 (1999).

IEEE J. Sel. Areas Commun. (2)

O. Gerstel, R. Ramaswami, and G. H. Sasaki, “Fault tolerant multiwavelength optical rings with limited wavelength conversion,” IEEE J. Sel. Areas Commun. 14, 1166–1178 (1998).

A. Narula-Tam, P. Lin, and E. Modiano, “Efficient routing and wavelength assignment for reconfigurable WDM networks,” IEEE J. Sel. Areas Commun. 20, 75–88 (2002).

J. Disc. Math. (1)

M. Garey, D. Johnson, G. Miller, and C. Papadimitiou, “The complexity of coloring circular arcs and chords,” SIAM (Soc. Ind. Appl. Math.) J. Disc. Math. 1, 216–227 (1980).

J. High Speed Netw. (2)

G. Li and R. Simha, “On bounds for the wavelength assignment problem in optical ring networks,” J. High Speed Netw. 8, 303–309 (2001).

G. Sahin and M. Azizoglu, “Optical layer survivability for single and multiple service classes,” J. High Speed Netw. 10, 91–108, special issue on Survivable Optical Networks (2001).

Other (10)

M. Swamy and K. Thulasiraman, Graphs, Networks, and Algorithms (Wiley, New York, 1981).

R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective (Morgan Kaufmann, Los Altos, Calif., 1998), pp. 371–372, 436–437.

G. Sahin and M. Azizoglu, “Optical layer survivability: single service-class case,” in OptiComm 2000: Optical Networking and Communications, I. Chlamtac, ed., Proc. SPIE 4233, 267–278 (2000).

H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: end-to-end recovery using local failure information,” Tech. Rep., MIT Laboratory for Information and Decision Systems (September 2001), <a href= "http://truth.mit.edu/~modiano/papers/T5.pdf">http://truth.mit.edu/~modiano/papers/T5.pdf</a>.

G. Sahin and M. Azizoglu, “An efficient wavelength assignment algorithm for service and restoration in WDM rings,” in Optical Fiber Communication Conference (OFC) (Optical Society of America, Washington, D.C., 2001), pp. TuO4-1–TuO4-2.

G. Ellinas, K. Bala, and G. K. Chang, “A novel wavelength assignment algorithm for 4-fiber WDM self-healing rings,” in Proceedings of the International Conference on Communications ’98 (Institute of Electrical and Electronics Engineers, New York, 1997), pp. 197–201.

R. Ramaswami and G. H. Sasaki, “Multiwavelength optical networks with limited wavelength conversion,” in Proceedings of I.E.E.E. Infocom ’97: The Conference on Computer Communications (Institute of Electrical and Electronics Engineers, New York, 1997), pp. 490–499.

J. Simmons, E. Goldstein, and A. Saleh, “On the value of wavelength add/drop in WDMrings with uniform traffic,” in Optical Fiber Communication Conference (OFC), Vol. 2 of 1998 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1998), pp. 361–362.

R. A. Barry and S. Subramaniam, “The MAX-SUM wavelength assignment algorithm for WDM ring networks,” in Optical Fiber Communication Conference (OFC), Vol. 6 of 1997 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1997), pp. 121–122.

T. Wu and R. C. Lau, “A class of self-healing ring architectures for SONET network applications,” in Proceedings of Globecom ’96: IEEE Global Telecommunications Conference (Institute of Electrical and Electronics Engineers, New York, 1990), pp. 403.2.1–403.2.8.

Cited By

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