Abstract

Dynamic traffic grooming in optical mesh networks is one of the most important and practical problems for designing wavelength-division-multiplexing networks. Most of the previous work solves this problem by applying the Dijsktra's algorithm on an auxiliary graph. Although those algorithms may give a good performance since they have a global view of the whole network, they are very time consuming and thus cannot be applied in large networks. Therefore, to the best of our knowledge, for the first time, we propose a heuristic algorithm to reduce the required computations by minimizing the size of the graph. We compare our algorithm with existing algorithms by extensive simulations in a typical 24-node mesh networks. The results demonstrate that our algorithm can significantly reduce the computational complexity, typically by a few tens times. Despite its simplification, our algorithm outperforms existing algorithms by large margins since it can easily avoid lightpaths that consume a large amount of network resources.

© 2007 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. B. Mukherjee, Optical Communication Networks (McGraw-Hill, 1997).
  2. E. Modiano, P. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 39, 124-129 (2001).
  3. K. Zhu, B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).
  4. K. Zhu, B. Mukherjee, "A review of traffic grooming in WDM optical networks: Architectures and challenges," SPIE Opt. Netw. Mag. 4, 55-64 (2003).
  5. A. L. Chiu, E. H. Modiano, "Traffic grooming in algorithms for reducing electronic multiplexing costs in WDM ring networks ," J. Lightw. Technol. 18, 2-12 (2000).
  6. P. J. Wan, G. Calinescu, L. Liu, O. Frieder, "Grooming of arbitrary traffic in SONET/WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
  7. X. Zhang, C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, 608-617 (2000).
  8. O. Gerstel, R. Ramaswami, G. H. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).
  9. J. Simmons, E. Goldstein, A. Saleh, "Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent traffic," J. Lightw. Technol. 17, 48-57 (1999).
  10. R. Dutta, G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
  11. J. Wang, W. Cho, V. R. Vemuri, B. Mukherjee, "Improved approaches for cost-effective traffic grooming in WDM ring networks: ILP formulations and single-hop and multi-hop connections," J. Lightw. Technol. 19, 1645-1653 (2001).
  12. J. Wang, B. Mukherjee, "Interconnected WDM ring networks: Strategies for interconnection and traffic grooming ," SPIE Opt. Netw. Mag. 3, 10-20 (2002).
  13. R. Berry, E. Modiano, "Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic ," IEEE J. Sel. Areas Commun. 18, 1961-1971 (2000).
  14. V. R. Konda, T. Y. Chow, "Algorithm for traffic grooming in optical networks to minimize the number of transceivers ," Proc. IEEE HPSR (2001) pp. 218-221.
  15. M. Brunato, R. Battiti, "A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies ," Proc. IEEE ONDM (2002) pp. 417-430.
  16. S. Thaigaran, A. Somani, "Capacity fairness of WDM networks with grooming capabilities," SPIE Opt. Netw. Mag. 2, 24-31 (2001).
  17. R. Srinivasan, A. K. Somani, "A generalized framework for analyzing time-space switched optical networks," IEEE J. Sel. Areas Commun. 20, 202-215 (2002).
  18. K. Zhu, B. Mukherjee, "On-line approaches for provisioning connections of different bandwidth granularities in WDM mesh networks," Proc. IEEE OFC (2002) pp. 549-551.
  19. S. Thiagarajan, A. Somani, "Traffic grooming for survivable mesh networks," Proc. OPTICOMM (2001) pp. 54-65.
  20. L. A. Cox, J. Sanchez, "Cost savings from optimized packing and grooming of optical circuits: Mesh versus ring comparisons ," SPIE Opt. Netw. Mag. 2, 72-90 (2001).
  21. A. Lardies, R. Gupta, R. A. Patterson, "Traffic grooming in a multilayer network," SPIE Opt. Netw. Mag. 2, 91-99 (2001).
  22. H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "Dynamic traffic grooming in WDM mesh networks using a novel graph model," SPIE Opt. Netw. Mag. 4, 65-75 (2003).
  23. H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks ," IEEE/ACM Trans. Netw. 11, 285-299 (2003).
  24. H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "A comprehensive study on next-generation optical grooming switches," IEEE J. Sel. Areas Commun. 21, 1173-1186 (2003).

2003 (4)

K. Zhu, B. Mukherjee, "A review of traffic grooming in WDM optical networks: Architectures and challenges," SPIE Opt. Netw. Mag. 4, 55-64 (2003).

H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "Dynamic traffic grooming in WDM mesh networks using a novel graph model," SPIE Opt. Netw. Mag. 4, 65-75 (2003).

H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks ," IEEE/ACM Trans. Netw. 11, 285-299 (2003).

H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "A comprehensive study on next-generation optical grooming switches," IEEE J. Sel. Areas Commun. 21, 1173-1186 (2003).

2002 (4)

J. Wang, B. Mukherjee, "Interconnected WDM ring networks: Strategies for interconnection and traffic grooming ," SPIE Opt. Netw. Mag. 3, 10-20 (2002).

R. Srinivasan, A. K. Somani, "A generalized framework for analyzing time-space switched optical networks," IEEE J. Sel. Areas Commun. 20, 202-215 (2002).

K. Zhu, B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).

R. Dutta, G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).

2001 (5)

J. Wang, W. Cho, V. R. Vemuri, B. Mukherjee, "Improved approaches for cost-effective traffic grooming in WDM ring networks: ILP formulations and single-hop and multi-hop connections," J. Lightw. Technol. 19, 1645-1653 (2001).

E. Modiano, P. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 39, 124-129 (2001).

L. A. Cox, J. Sanchez, "Cost savings from optimized packing and grooming of optical circuits: Mesh versus ring comparisons ," SPIE Opt. Netw. Mag. 2, 72-90 (2001).

A. Lardies, R. Gupta, R. A. Patterson, "Traffic grooming in a multilayer network," SPIE Opt. Netw. Mag. 2, 91-99 (2001).

S. Thaigaran, A. Somani, "Capacity fairness of WDM networks with grooming capabilities," SPIE Opt. Netw. Mag. 2, 24-31 (2001).

2000 (5)

R. Berry, E. Modiano, "Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic ," IEEE J. Sel. Areas Commun. 18, 1961-1971 (2000).

A. L. Chiu, E. H. Modiano, "Traffic grooming in algorithms for reducing electronic multiplexing costs in WDM ring networks ," J. Lightw. Technol. 18, 2-12 (2000).

P. J. Wan, G. Calinescu, L. Liu, O. Frieder, "Grooming of arbitrary traffic in SONET/WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).

X. Zhang, C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, 608-617 (2000).

O. Gerstel, R. Ramaswami, G. H. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).

1999 (1)

J. Simmons, E. Goldstein, A. Saleh, "Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent traffic," J. Lightw. Technol. 17, 48-57 (1999).

IEEE Commun. Mag. (1)

E. Modiano, P. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 39, 124-129 (2001).

IEEE J. Sel. Areas Commun. (6)

K. Zhu, B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).

P. J. Wan, G. Calinescu, L. Liu, O. Frieder, "Grooming of arbitrary traffic in SONET/WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).

R. Dutta, G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).

R. Berry, E. Modiano, "Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic ," IEEE J. Sel. Areas Commun. 18, 1961-1971 (2000).

R. Srinivasan, A. K. Somani, "A generalized framework for analyzing time-space switched optical networks," IEEE J. Sel. Areas Commun. 20, 202-215 (2002).

H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "A comprehensive study on next-generation optical grooming switches," IEEE J. Sel. Areas Commun. 21, 1173-1186 (2003).

IEEE/ACM Trans. Netw. (3)

H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks ," IEEE/ACM Trans. Netw. 11, 285-299 (2003).

X. Zhang, C. Qiao, "An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings," IEEE/ACM Trans. Netw. 8, 608-617 (2000).

O. Gerstel, R. Ramaswami, G. H. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).

J. Lightw. Technol. (3)

J. Simmons, E. Goldstein, A. Saleh, "Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent traffic," J. Lightw. Technol. 17, 48-57 (1999).

A. L. Chiu, E. H. Modiano, "Traffic grooming in algorithms for reducing electronic multiplexing costs in WDM ring networks ," J. Lightw. Technol. 18, 2-12 (2000).

J. Wang, W. Cho, V. R. Vemuri, B. Mukherjee, "Improved approaches for cost-effective traffic grooming in WDM ring networks: ILP formulations and single-hop and multi-hop connections," J. Lightw. Technol. 19, 1645-1653 (2001).

SPIE Opt. Netw. Mag. (6)

J. Wang, B. Mukherjee, "Interconnected WDM ring networks: Strategies for interconnection and traffic grooming ," SPIE Opt. Netw. Mag. 3, 10-20 (2002).

L. A. Cox, J. Sanchez, "Cost savings from optimized packing and grooming of optical circuits: Mesh versus ring comparisons ," SPIE Opt. Netw. Mag. 2, 72-90 (2001).

A. Lardies, R. Gupta, R. A. Patterson, "Traffic grooming in a multilayer network," SPIE Opt. Netw. Mag. 2, 91-99 (2001).

H. Zhu, H. Zang, K. Zhu, B. Mukherjee, "Dynamic traffic grooming in WDM mesh networks using a novel graph model," SPIE Opt. Netw. Mag. 4, 65-75 (2003).

K. Zhu, B. Mukherjee, "A review of traffic grooming in WDM optical networks: Architectures and challenges," SPIE Opt. Netw. Mag. 4, 55-64 (2003).

S. Thaigaran, A. Somani, "Capacity fairness of WDM networks with grooming capabilities," SPIE Opt. Netw. Mag. 2, 24-31 (2001).

Other (5)

B. Mukherjee, Optical Communication Networks (McGraw-Hill, 1997).

K. Zhu, B. Mukherjee, "On-line approaches for provisioning connections of different bandwidth granularities in WDM mesh networks," Proc. IEEE OFC (2002) pp. 549-551.

S. Thiagarajan, A. Somani, "Traffic grooming for survivable mesh networks," Proc. OPTICOMM (2001) pp. 54-65.

V. R. Konda, T. Y. Chow, "Algorithm for traffic grooming in optical networks to minimize the number of transceivers ," Proc. IEEE HPSR (2001) pp. 218-221.

M. Brunato, R. Battiti, "A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies ," Proc. IEEE ONDM (2002) pp. 417-430.

Cited By

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

Alert me when this article is cited.