Abstract

In this paper, we address the problem of traffic grooming in wavelength-division multiplexing rings with all-to-all and its generalization to many-to-many service by using network coding. We consider minimizing the number of line terminating equipment on two types of unidirectional rings, namely, single-hub and unhubbed rings, as our objective. In single-hub rings, we investigate the minimum cost provisioning of uniform all-to-all traffic in two cases: where network coding is used to linearly combine data, and where it is not used and data are transmitted without coding. We generalize the service mode to many-to-many and evaluate the cost of provisioning. In unhubbed ring, we propose a multihub approach to obtain the minimum cost provisioning in the case of all-to-all and many-to-many traffic. In each type of ring topology, two network scenarios are considered: first, the distinct communication groups in the ring are node-disjoint, and second, the different groups may have common member nodes. From our numerical results, we find that under many-to-many traffic pattern for both scenarios, network coding can reduce the network cost by 10%–20% in single-hub rings and 1%–5% in unhubbed rings in both network scenarios.

© 2009 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. A. L. Chiu, E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks," J. Lightw. Technol. 18, 2-12 (2000).
  2. J.-C. Bermond, D. Coudert, X. Munoz, "Traffic grooming in unidrirectional WDM ring networks: The all-to-all unitary case," Proc. IFIP Workshop on Opt. Netw. Des. Model. (2003) pp. 1135-1153.
  3. K. Zhu, B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).
  4. R. Dutta, G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
  5. R. Ahlswede, N. Cai, S.-Y. R. Li, R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory 46, 1204-1216 (2000).
  6. S. R. Li, R. W. Yeung, N. Cai, "Linear network coding," IEEE Trans. Inf. Theory 49, 371-381 (2003).
  7. S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, L. M. G. M. Tolhuizen, "Polynomial time algorithms for multicast network code construction," IEEE Trans. Inf. Theory 51, 1973-1982 (2005).
  8. T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, B. Leong, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory 52, 4413-4430 (2006).
  9. H. V. Madhyastha, G. V. Chowdhary, N. Srinivas, C. S. R. Murthy, "Grooming of multicast sessions in metropolitan WDM ring networks," Comput. Netw. 49, 561-579 (2005).
  10. X. Y. Li, L. Liu, P. J. Wan, O. Frieder, "Practical traffic grooming scheme for single-hub SONET/WDM rings," Proc. 25th IEEE Conf. Local Comput. Netw. (2000) pp. 1193-1200.
  11. J. Q. Hu, "Optimal traffic grooming for WDM rings with all-to-all uniform traffic," J. Opt. Netw. 1, 32-42 (2002).
  12. J. Wang, W. Cho, V. Vemuri, B. Mukherjee, "Improved approaches for cost-effective traffic grooming in WDM ring networks: ILP formulations and single-hop and multihop connections," J. Lightw. Technol. 19, 1645-1653 (2001).
  13. G. Feng, C. Siew, T.-S. Yum, "Architectural design and bandwidth demand analysis for multiparty videoconferenceing on SONET/ATM rings," IEEE J. Sel. Areas Commun. 20, 1580-1588 (2002).
  14. A. Rawat, R. La, S. Marcus, M. Shayman, "Grooming multicast traffic in unidirectional SONET/WDM rings," IEEE J. Sel. Areas Commun. 20, 70-83 (2007).
  15. A. E. Kamal, "Algorithms for multicast traffic grooming in WDM mesh networks," IEEE Commun. Mag. 44, 96-105 (2006).
  16. R. Ul-Mustafa, A. E. Kamal, "Many-to-one traffic grooming with aggregation in WDM networks," IEEE J. Sel. Areas Commun. 24, 68-81 (2006).
  17. R. Ul-Mustafa, A. E. Kamal, "Design and provisioning of WDM networks with multicast traffic grooming," IEEE J. Sel. Areas Commun. 24, 37-53 (2006).
  18. J. Q. Hu, B. Leida, "Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks," Proc. IEEE Infocom (2004) pp. 495-501.
  19. 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).
  20. O. Gerstel, R. Ramaswami, G. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).
  21. P.-J. Wan, G. Galinescu, L. Liu, O. Frieder, "Grooming of arbitrary traffic in SONET/WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
  22. M. Zhang, L. Wang, P. Ye, "All optical XOR logic gates: Technologies and experiment demonstrations," IEEE Commun. Mag. 43, s19-s24 (2005).
  23. E. D. Manley, J. S. Deogun, L. Xu, "Network coding for optical layer multicast," Proc. Broadnets (2008) pp. 452-459.
  24. T. Ho, B. Leong, Y. Chang, Y. Wen, R. Koetter, "Network monitoring in multicast networks using network coding," Proc. Int. Symp. Inf. Theory (ISIT) (2005) pp. 1977-1981.
  25. A. E. Kamal, "$1+{\rm N}$ network protection for mesh networks: Network coding-based protection using p-cycles," IEEE/ACM Trans. Netw. to appear in.
  26. O. Al-Kofahi, A. E. Kamal, "Network coding-based protection of many-to-one wireless flows," IEEE J. Sel. Areas Commun. 27, 797-813 (2009) to appear in.
  27. C. Gkantsidis, P. Rodriguez, "Network coding for large scale content distribution," Proc. IEEE Infocom (2005) pp. 2235-2245.
  28. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, "XORs in the air: Practical wireless network coding," presented at the SIGCOMM, Pisa, Italy, 2006 .
  29. E. G. Coffman, M. R. Garey, D. S. Johnson, Approximation Algorithms for NP-Hard Problems (PWS Publishing Company, 1997) pp. 46-93.
  30. J. M. V. de Carvalho, "Exact solution of bin packing problems using column generation and branch and bound," Ann. Oper. Res. 86, 629-659 (1999) No. 0.

2009 (1)

O. Al-Kofahi, A. E. Kamal, "Network coding-based protection of many-to-one wireless flows," IEEE J. Sel. Areas Commun. 27, 797-813 (2009) to appear in.

2007 (1)

A. Rawat, R. La, S. Marcus, M. Shayman, "Grooming multicast traffic in unidirectional SONET/WDM rings," IEEE J. Sel. Areas Commun. 20, 70-83 (2007).

2006 (4)

A. E. Kamal, "Algorithms for multicast traffic grooming in WDM mesh networks," IEEE Commun. Mag. 44, 96-105 (2006).

R. Ul-Mustafa, A. E. Kamal, "Many-to-one traffic grooming with aggregation in WDM networks," IEEE J. Sel. Areas Commun. 24, 68-81 (2006).

R. Ul-Mustafa, A. E. Kamal, "Design and provisioning of WDM networks with multicast traffic grooming," IEEE J. Sel. Areas Commun. 24, 37-53 (2006).

T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, B. Leong, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory 52, 4413-4430 (2006).

2005 (3)

H. V. Madhyastha, G. V. Chowdhary, N. Srinivas, C. S. R. Murthy, "Grooming of multicast sessions in metropolitan WDM ring networks," Comput. Netw. 49, 561-579 (2005).

S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, L. M. G. M. Tolhuizen, "Polynomial time algorithms for multicast network code construction," IEEE Trans. Inf. Theory 51, 1973-1982 (2005).

M. Zhang, L. Wang, P. Ye, "All optical XOR logic gates: Technologies and experiment demonstrations," IEEE Commun. Mag. 43, s19-s24 (2005).

2003 (1)

S. R. Li, R. W. Yeung, N. Cai, "Linear network coding," IEEE Trans. Inf. Theory 49, 371-381 (2003).

2002 (4)

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).

J. Q. Hu, "Optimal traffic grooming for WDM rings with all-to-all uniform traffic," J. Opt. Netw. 1, 32-42 (2002).

G. Feng, C. Siew, T.-S. Yum, "Architectural design and bandwidth demand analysis for multiparty videoconferenceing on SONET/ATM rings," IEEE J. Sel. Areas Commun. 20, 1580-1588 (2002).

2001 (1)

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

2000 (5)

R. Ahlswede, N. Cai, S.-Y. R. Li, R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory 46, 1204-1216 (2000).

A. L. Chiu, E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks," J. Lightw. Technol. 18, 2-12 (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. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).

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

1999 (1)

J. M. V. de Carvalho, "Exact solution of bin packing problems using column generation and branch and bound," Ann. Oper. Res. 86, 629-659 (1999) No. 0.

Ann. Oper. Res. (1)

J. M. V. de Carvalho, "Exact solution of bin packing problems using column generation and branch and bound," Ann. Oper. Res. 86, 629-659 (1999) No. 0.

Comput. Netw. (1)

H. V. Madhyastha, G. V. Chowdhary, N. Srinivas, C. S. R. Murthy, "Grooming of multicast sessions in metropolitan WDM ring networks," Comput. Netw. 49, 561-579 (2005).

IEEE J. Sel. Areas Commun. (1)

R. Ul-Mustafa, A. E. Kamal, "Design and provisioning of WDM networks with multicast traffic grooming," IEEE J. Sel. Areas Commun. 24, 37-53 (2006).

IEEE Commun. Mag. (1)

A. E. Kamal, "Algorithms for multicast traffic grooming in WDM mesh networks," IEEE Commun. Mag. 44, 96-105 (2006).

IEEE Commun. Mag. (1)

M. Zhang, L. Wang, P. Ye, "All optical XOR logic gates: Technologies and experiment demonstrations," IEEE Commun. Mag. 43, s19-s24 (2005).

IEEE J. Sel. Areas Commun. (2)

O. Al-Kofahi, A. E. Kamal, "Network coding-based protection of many-to-one wireless flows," IEEE J. Sel. Areas Commun. 27, 797-813 (2009) to appear in.

R. Ul-Mustafa, A. E. Kamal, "Many-to-one traffic grooming with aggregation in WDM networks," IEEE J. Sel. Areas Commun. 24, 68-81 (2006).

IEEE J. Sel. Areas Commun. (5)

G. Feng, C. Siew, T.-S. Yum, "Architectural design and bandwidth demand analysis for multiparty videoconferenceing on SONET/ATM rings," IEEE J. Sel. Areas Commun. 20, 1580-1588 (2002).

A. Rawat, R. La, S. Marcus, M. Shayman, "Grooming multicast traffic in unidirectional SONET/WDM rings," IEEE J. Sel. Areas Commun. 20, 70-83 (2007).

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).

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

IEEE Trans. Inf. Theory (1)

S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, L. M. G. M. Tolhuizen, "Polynomial time algorithms for multicast network code construction," IEEE Trans. Inf. Theory 51, 1973-1982 (2005).

IEEE Trans. Inf. Theory (3)

T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, B. Leong, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory 52, 4413-4430 (2006).

R. Ahlswede, N. Cai, S.-Y. R. Li, R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory 46, 1204-1216 (2000).

S. R. Li, R. W. Yeung, N. Cai, "Linear network coding," IEEE Trans. Inf. Theory 49, 371-381 (2003).

IEEE/ACM Trans. Netw. (1)

A. E. Kamal, "$1+{\rm N}$ network protection for mesh networks: Network coding-based protection using p-cycles," IEEE/ACM Trans. Netw. to appear in.

IEEE/ACM Trans. Netw. (2)

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. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).

J. Opt. Netw. (1)

J. Q. Hu, "Optimal traffic grooming for WDM rings with all-to-all uniform traffic," J. Opt. Netw. 1, 32-42 (2002).

J. Lightw. Technol. (2)

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

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

Other (8)

J.-C. Bermond, D. Coudert, X. Munoz, "Traffic grooming in unidrirectional WDM ring networks: The all-to-all unitary case," Proc. IFIP Workshop on Opt. Netw. Des. Model. (2003) pp. 1135-1153.

X. Y. Li, L. Liu, P. J. Wan, O. Frieder, "Practical traffic grooming scheme for single-hub SONET/WDM rings," Proc. 25th IEEE Conf. Local Comput. Netw. (2000) pp. 1193-1200.

J. Q. Hu, B. Leida, "Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks," Proc. IEEE Infocom (2004) pp. 495-501.

E. D. Manley, J. S. Deogun, L. Xu, "Network coding for optical layer multicast," Proc. Broadnets (2008) pp. 452-459.

T. Ho, B. Leong, Y. Chang, Y. Wen, R. Koetter, "Network monitoring in multicast networks using network coding," Proc. Int. Symp. Inf. Theory (ISIT) (2005) pp. 1977-1981.

C. Gkantsidis, P. Rodriguez, "Network coding for large scale content distribution," Proc. IEEE Infocom (2005) pp. 2235-2245.

S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, "XORs in the air: Practical wireless network coding," presented at the SIGCOMM, Pisa, Italy, 2006 .

E. G. Coffman, M. R. Garey, D. S. Johnson, Approximation Algorithms for NP-Hard Problems (PWS Publishing Company, 1997) pp. 46-93.

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.