Abstract

A large number of network applications today allow several users to interact together using the many-to-many service mode. In many-to-many communication, also referred to as group communication, a session consists of a group of users (we refer to them as members), where each member transmits its traffic to all other members in the same group. In this paper, we address the problem of many-to-many traffic grooming in WDM mesh networks. In this problem, a set of many-to-many session requests, each with an arbitrary subwavelength traffic demand, is given and the objective is to provision the sessions on the WDM network with the minimum network cost. The cost of a WDM network is dominated by the cost of higher-layer electronic ports (we refer to them as transceivers). Therefore, our objective is to minimize the total number of transceivers used. We address the problem in both nonsplitting networks, where the nodes do not have optical splitting capabilities, and in splitting networks, where the nodes do have optical splitting capabilities. First, we formulate the problem in each of the two networks as a mixed integer linear program (MILP). Afterwards, based on observations from optimal solutions, we develop a heuristic approach for each network by relaxing and simplifying its corresponding MILP. Through extensive experiments, we verify the accuracy of our proposed heuristics and also show when each of the two networks is a more cost-effective choice for many-to-many traffic grooming.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. L. H. Sahasrabuddhe, B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength routed networks,” IEEE Commun. Mag., vol. 37, no. 2, pp. 67–73, Feb. 1999.
    [CrossRef]
  2. A. L. Chiu, E. H. Modiano, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol., vol. 18, no. 1, pp. 2–12, Jan. 2000.
    [CrossRef]
  3. C. Diot, W. Dabbous, J. Crowcroft, “Multipoint communication: a survey of protocols, functions, and mechanisms,” IEEE J. Sel. Areas Commun., vol. 15, pp. 277–290, 1997.
    [CrossRef]
  4. B. Quinn, K. Almeroth, “IP multicast applications: challenges and solutions,” IETF Request for Comments (RFC) 3170, Sept. 2001.
  5. O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
    [CrossRef]
  6. X. Zhang, C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 608–617, Oct. 2000.
    [CrossRef]
  7. K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
    [CrossRef]
  8. J. Q. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM’04, 2004, pp. 495–501.
  9. S. Antonakopoulos, L. Zhang, “Approximation algorithms for grooming in optical network design,” in Proc. IEEE INFOCOM’09, 2009, pp. 1548–1556.
  10. B. Chen, G. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
    [CrossRef]
  11. R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
    [CrossRef]
  12. P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
    [CrossRef]
  13. 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., vol. 11, no. 2, pp. 285–299, April 2003.
    [CrossRef]
  14. R. Dutta, S. Huang, G. N. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66–82, April 2006.
  15. H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
    [CrossRef]
  16. A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
    [CrossRef]
  17. R. Ul-Mustafa, A. E. Kamal, “Design and provisioning of WDM networks with multicast traffic grooming,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 37–53, April 2006.
  18. A. Billah, B. Wang, A. Awwal, “Multicast traffic grooming in WDM optical mesh networks,” in Proc. GLOBECOM’03, vol. 5, pp. 2755–2760, Dec. 2003.
  19. G. Chowdhary, C. S. R. Murthy, “Grooming of multicast sessions in WDM mesh networks,” in Workshop on Traffic Grooming, 2004.
  20. R. Ul-Mustafa, A. E. Kamal, “Many-to-one traffic grooming with aggregation in WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 68–81, Aug. 2006.
  21. A. E. Kamal, “Algorithms for multicast traffic grooming in WDM mesh networks,” IEEE Commun. Mag., vol. 44, no. 11, pp. 96–105, Nov. 2006.
    [CrossRef]
  22. M. Saleh, A. Kamal, “Many-to-many traffic grooming in WDM mesh networks,” in Proc. IEEE GLOBECOM’08, 2008, pp. 1–5.
  23. R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
    [CrossRef]
  24. http://www.ilog.com/products/cplex/

2008 (1)

B. Chen, G. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

2007 (1)

A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
[CrossRef]

2006 (4)

R. Ul-Mustafa, A. E. Kamal, “Design and provisioning of WDM networks with multicast traffic grooming,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 37–53, April 2006.

R. Ul-Mustafa, A. E. Kamal, “Many-to-one traffic grooming with aggregation in WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 68–81, Aug. 2006.

A. E. Kamal, “Algorithms for multicast traffic grooming in WDM mesh networks,” IEEE Commun. Mag., vol. 44, no. 11, pp. 96–105, Nov. 2006.
[CrossRef]

R. Dutta, S. Huang, G. N. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66–82, April 2006.

2005 (1)

H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
[CrossRef]

2003 (1)

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., vol. 11, no. 2, pp. 285–299, April 2003.
[CrossRef]

2002 (2)

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

2000 (5)

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

X. Zhang, C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 608–617, Oct. 2000.
[CrossRef]

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
[CrossRef]

A. L. Chiu, E. H. Modiano, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol., vol. 18, no. 1, pp. 2–12, Jan. 2000.
[CrossRef]

R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
[CrossRef]

1999 (1)

L. H. Sahasrabuddhe, B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength routed networks,” IEEE Commun. Mag., vol. 37, no. 2, pp. 67–73, Feb. 1999.
[CrossRef]

1997 (1)

C. Diot, W. Dabbous, J. Crowcroft, “Multipoint communication: a survey of protocols, functions, and mechanisms,” IEEE J. Sel. Areas Commun., vol. 15, pp. 277–290, 1997.
[CrossRef]

Ahlswede, R.

R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
[CrossRef]

Almeroth, K.

B. Quinn, K. Almeroth, “IP multicast applications: challenges and solutions,” IETF Request for Comments (RFC) 3170, Sept. 2001.

Antonakopoulos, S.

S. Antonakopoulos, L. Zhang, “Approximation algorithms for grooming in optical network design,” in Proc. IEEE INFOCOM’09, 2009, pp. 1548–1556.

Awwal, A.

A. Billah, B. Wang, A. Awwal, “Multicast traffic grooming in WDM optical mesh networks,” in Proc. GLOBECOM’03, vol. 5, pp. 2755–2760, Dec. 2003.

Billah, A.

A. Billah, B. Wang, A. Awwal, “Multicast traffic grooming in WDM optical mesh networks,” in Proc. GLOBECOM’03, vol. 5, pp. 2755–2760, Dec. 2003.

Cai, N.

R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
[CrossRef]

Calinescu, G.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
[CrossRef]

Chen, B.

B. Chen, G. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

Chiu, A. L.

Chowdhary, G.

H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
[CrossRef]

G. Chowdhary, C. S. R. Murthy, “Grooming of multicast sessions in WDM mesh networks,” in Workshop on Traffic Grooming, 2004.

Crowcroft, J.

C. Diot, W. Dabbous, J. Crowcroft, “Multipoint communication: a survey of protocols, functions, and mechanisms,” IEEE J. Sel. Areas Commun., vol. 15, pp. 277–290, 1997.
[CrossRef]

Dabbous, W.

C. Diot, W. Dabbous, J. Crowcroft, “Multipoint communication: a survey of protocols, functions, and mechanisms,” IEEE J. Sel. Areas Commun., vol. 15, pp. 277–290, 1997.
[CrossRef]

Diot, C.

C. Diot, W. Dabbous, J. Crowcroft, “Multipoint communication: a survey of protocols, functions, and mechanisms,” IEEE J. Sel. Areas Commun., vol. 15, pp. 277–290, 1997.
[CrossRef]

Dutta, R.

B. Chen, G. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

R. Dutta, S. Huang, G. N. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66–82, April 2006.

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

Frieder, O.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
[CrossRef]

Gerstel, O.

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

Hu, J. Q.

J. Q. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM’04, 2004, pp. 495–501.

Huang, S.

R. Dutta, S. Huang, G. N. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66–82, April 2006.

Kamal, A.

M. Saleh, A. Kamal, “Many-to-many traffic grooming in WDM mesh networks,” in Proc. IEEE GLOBECOM’08, 2008, pp. 1–5.

Kamal, A. E.

R. Ul-Mustafa, A. E. Kamal, “Many-to-one traffic grooming with aggregation in WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 68–81, Aug. 2006.

A. E. Kamal, “Algorithms for multicast traffic grooming in WDM mesh networks,” IEEE Commun. Mag., vol. 44, no. 11, pp. 96–105, Nov. 2006.
[CrossRef]

R. Ul-Mustafa, A. E. Kamal, “Design and provisioning of WDM networks with multicast traffic grooming,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 37–53, April 2006.

La, R.

A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
[CrossRef]

Leida, B.

J. Q. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM’04, 2004, pp. 495–501.

Li, S. R.

R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
[CrossRef]

Liu, L.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
[CrossRef]

Madhyastha, H.

H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
[CrossRef]

Marcus, S.

A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
[CrossRef]

Modiano, E. H.

Mukherjee, B.

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., vol. 11, no. 2, pp. 285–299, April 2003.
[CrossRef]

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

L. H. Sahasrabuddhe, B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength routed networks,” IEEE Commun. Mag., vol. 37, no. 2, pp. 67–73, Feb. 1999.
[CrossRef]

Murthy, C. S. R.

H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
[CrossRef]

G. Chowdhary, C. S. R. Murthy, “Grooming of multicast sessions in WDM mesh networks,” in Workshop on Traffic Grooming, 2004.

Qiao, C.

X. Zhang, C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 608–617, Oct. 2000.
[CrossRef]

Quinn, B.

B. Quinn, K. Almeroth, “IP multicast applications: challenges and solutions,” IETF Request for Comments (RFC) 3170, Sept. 2001.

Ramaswami, R.

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

Rawat, A.

A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
[CrossRef]

Rouskas, G.

B. Chen, G. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

Rouskas, G. N.

R. Dutta, S. Huang, G. N. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66–82, April 2006.

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

Sahasrabuddhe, L. H.

L. H. Sahasrabuddhe, B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength routed networks,” IEEE Commun. Mag., vol. 37, no. 2, pp. 67–73, Feb. 1999.
[CrossRef]

Saleh, M.

M. Saleh, A. Kamal, “Many-to-many traffic grooming in WDM mesh networks,” in Proc. IEEE GLOBECOM’08, 2008, pp. 1–5.

Sasaki, G.

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

Shayman, M.

A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
[CrossRef]

Srinivas, N.

H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
[CrossRef]

Ul-Mustafa, R.

R. Ul-Mustafa, A. E. Kamal, “Design and provisioning of WDM networks with multicast traffic grooming,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 37–53, April 2006.

R. Ul-Mustafa, A. E. Kamal, “Many-to-one traffic grooming with aggregation in WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 68–81, Aug. 2006.

Wan, P.-J.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
[CrossRef]

Wang, B.

A. Billah, B. Wang, A. Awwal, “Multicast traffic grooming in WDM optical mesh networks,” in Proc. GLOBECOM’03, vol. 5, pp. 2755–2760, Dec. 2003.

Yeung, R. W.

R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
[CrossRef]

Zang, H.

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., vol. 11, no. 2, pp. 285–299, April 2003.
[CrossRef]

Zhang, L.

S. Antonakopoulos, L. Zhang, “Approximation algorithms for grooming in optical network design,” in Proc. IEEE INFOCOM’09, 2009, pp. 1548–1556.

Zhang, X.

X. Zhang, C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 608–617, Oct. 2000.
[CrossRef]

Zhu, H.

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., vol. 11, no. 2, pp. 285–299, April 2003.
[CrossRef]

Zhu, K.

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., vol. 11, no. 2, pp. 285–299, April 2003.
[CrossRef]

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

Comput. Netw. (1)

H. Madhyastha, G. Chowdhary, N. Srinivas, C. S. R. Murthy, “Grooming of multicast sessions in metropolitan WDM ring networks,” Comput. Netw., vol. 49, pp. 561–579, 2005.
[CrossRef]

IEEE Commun. Mag. (2)

A. E. Kamal, “Algorithms for multicast traffic grooming in WDM mesh networks,” IEEE Commun. Mag., vol. 44, no. 11, pp. 96–105, Nov. 2006.
[CrossRef]

L. H. Sahasrabuddhe, B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength routed networks,” IEEE Commun. Mag., vol. 37, no. 2, pp. 67–73, Feb. 1999.
[CrossRef]

IEEE J. Sel. Areas Commun. (7)

A. Rawat, R. La, S. Marcus, M. Shayman, “Grooming multicast traffic in unidirectional SONET/WDM rings,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 70–83, Aug. 2007.
[CrossRef]

R. Ul-Mustafa, A. E. Kamal, “Design and provisioning of WDM networks with multicast traffic grooming,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 37–53, April 2006.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, pp. 1995–2003, 2000.
[CrossRef]

R. Dutta, S. Huang, G. N. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66–82, April 2006.

R. Ul-Mustafa, A. E. Kamal, “Many-to-one traffic grooming with aggregation in WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 68–81, Aug. 2006.

C. Diot, W. Dabbous, J. Crowcroft, “Multipoint communication: a survey of protocols, functions, and mechanisms,” IEEE J. Sel. Areas Commun., vol. 15, pp. 277–290, 1997.
[CrossRef]

K. Zhu, B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122–133, Jan. 2002.
[CrossRef]

IEEE Network (1)

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

IEEE Trans. Inf. Theory (1)

R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, July 2000.
[CrossRef]

IEEE/ACM Trans. Netw. (4)

B. Chen, G. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

X. Zhang, C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 608–617, Oct. 2000.
[CrossRef]

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., vol. 11, no. 2, pp. 285–299, April 2003.
[CrossRef]

J. Lightwave Technol. (1)

Other (7)

http://www.ilog.com/products/cplex/

M. Saleh, A. Kamal, “Many-to-many traffic grooming in WDM mesh networks,” in Proc. IEEE GLOBECOM’08, 2008, pp. 1–5.

A. Billah, B. Wang, A. Awwal, “Multicast traffic grooming in WDM optical mesh networks,” in Proc. GLOBECOM’03, vol. 5, pp. 2755–2760, Dec. 2003.

G. Chowdhary, C. S. R. Murthy, “Grooming of multicast sessions in WDM mesh networks,” in Workshop on Traffic Grooming, 2004.

B. Quinn, K. Almeroth, “IP multicast applications: challenges and solutions,” IETF Request for Comments (RFC) 3170, Sept. 2001.

J. Q. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM’04, 2004, pp. 495–501.

S. Antonakopoulos, L. Zhang, “Approximation algorithms for grooming in optical network design,” in Proc. IEEE INFOCOM’09, 2009, pp. 1548–1556.

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.


Figures (5)

Fig. 1
Fig. 1

A many-to-many session with members { A , B , C , D } , each with traffic denoted as a, b, c, and d, respectively.

Fig. 2
Fig. 2

Provisioning of a many-to-many session with a set of members { A , B , C , D } , each with traffic denoted as a, b, c, and d, respectively (grooming factor = 4 ), in (a) a nonsplitting network case where a, b, c, and d are one unit of traffic each; (b) a splitting network case where a, b, c, and d are one unit of traffic each ( hub = B ) ; (c) a nonsplitting network case where a, b, c, and d are two units of traffic each; and (d) a splitting network case where a, b, c, and d are two units of traffic each ( hub = B ) .

Fig. 3
Fig. 3

(a) LC for a session s k , where m s k = { A , B , C , D } , each with one traffic unit denoted as a, b, c, and d ( g = 3 , H s k = 1 ). (b) Provisioning of sessions s 1 and s 2 , where m s 1 = { A , B , C } , each with one traffic unit denoted as a, b 1 , and c 1 , and m s 2 = { B , C , D } , each with one traffic unit denoted as b 2 , c 2 , and d ( g = 4 ) . The order of the members in the LCs for s 1 and s 2 is A B C A and B C D B , respectively. (c) Same as (b) except that the order of the members in the LCs for s 1 and s 2 is A B C A and B D C B , respectively.

Fig. 4
Fig. 4

Networks used in the results.

Fig. 5
Fig. 5

Values of TR ¯ for t = 1 , 2 , , g on the Abilene network ( g = 16 ) .

Tables (9)

Tables Icon

Table 1 Sample Traffic Used in the Example

Tables Icon

Table 2 Many-to-Many Sessions Provisioning in the Nonsplitting Network Case

Tables Icon

Table 3 Many-to-Many Sessions Provisioning in the Splitting Network Case According to the Hub-Based Approach

Tables Icon

Table 4 Many-to-Many Sessions Provisioning in the Nonsplitting Network Case Using the Heuristic MILP

Tables Icon

Table 5 Many-to-Many Sessions Provisioning in the Splitting Network Case Using the Heuristic MILP

Tables Icon

Table 6 Average Running Time and Average Number of Transceivers for the Five Experiments Conducted on Each of the Six-Node, Abilene, and NSF Networks in the Nonsplitting Network Case

Tables Icon

Table 7 Average Running Time and Average Number of Transceivers for the Five Experiments Conducted on Each of the Six-Node, Abilene, and NSF Networks in the Splitting Network Case (Hub-Based Approach)

Tables Icon

Table 8 Comparison of Number of Transceivers on the Abilene Network With Nonuniform Traffic

Tables Icon

Table 9 Values of TR saved ¯ and TR saved ¯ TR ¯ for t = 1 , 2 , , g ( g = 16 ) on the Abilene Network

Equations (53)

Equations on this page are rendered with MathJax. Learn more.

Minimize : n TR n
TR i j : j i ( L i j + L j i ) i .
m : P m x = 1 F m x i j , w n : P x n = 1 F x n i j , w = { L i j w , if x = j L i j w , if x = i 0 , otherwise }
i , j , w , x V .
i j F m n i j , w 1 w , m , n : P m n = 1 .
i Z i x s k , p , q j Z x j s k , p , q = { 1 , if x = q 1 , if x = p 0 , otherwise }
s k , ( p , q ) m s k , x V .
Y i j s k , p q p Z i j s k , p , q Q s k , p m s k , i , j ,
Y i j s k , p q p Z i j s k , p , q s k , p m s k , i , j .
X i j s k = t s k p m s k Y i j s k , p s k , i , j .
L i j ( s k X i j s k ) g i , j .
Minimize : n TR n
TR i j : j i ( L i j + L j i ) + s k LT s k B i s k + s k : i m s k A i s k i .
A i s k Q I i s k Q + LT s k s k , i ,
A i s k LT s k s k , i .
s k , p m s k , h p , w :
n : P h n = 1 R h n s k , p , w LT s k w ( 1 I h s k ) Q ,
n : P h n = 1 R h n s k , p , w LT s k w + ( 1 I h s k ) Q .
m : P m p = 1 R m p s k , p , w LT s k w Q I p s k s k , p m s k , w ,
m : P m p = 1 R m p s k , p , w LT s k w + Q I p s k s k , p m s k , w .
s k , p m s k , w , x V ( x p ) :
m : P m x = 1 R m x s k , p , w n : P x n = 1 R x n s k , p , w ,
m : P m x = 1 R m x s k , p , w n : P x n = 1 R x n s k , p , w Q I x s k .
s k , ( p , q ) m s k , w :
m : P m p = 1 R m p s k , p , w m : P m q = 1 R m q s k , q , w ( I p s k + I q s k ) Q ,
m : P m p = 1 R m p s k , p , w m : P m q = 1 R m q s k , q , w + ( I p s k + I q s k ) Q .
R m n s k , w p m s k R m n s k , p , w Q s k , w , m , n : P m n = 1 ,
R m n s k , w p m s k R m n s k , p , w s k , w , m , n : P m n = 1 .
s k R m n s k , w + i j F m n i j , w 1 w , m , n : P m n = 1 .
h V I h s k = 1 s k .
E s l s k , h ( I h s k + I h s l ) 2 s k , s l , h ,
E s l s k , h I h s k + I h s l 1 s k , s l , h .
E s l s k h E s l s k , h Q s k , s l ,
E s l s k h E s l s k , h s k , s l .
i : i p D p i s k , p = 1 I p s k s k , p m s k .
i : i h D i h s k , p I h s k s k , p m s k , h p .
s k , p m s k , x V ( x p ) :
i : i x D i x s k , p = j : j ( x , p ) D x j s k , p + I x s k .
X i j s k = t s k p m s k D i j s k , p s k , i , j .
U s l s k E s l s k s k , s l .
s l : p m s l U s l s k 1 s k , p m s k .
T s l s k = U s l s k × ( N s k 1 ) × t s k s k , s l .
LT s k ( s l T s k s l ) g s k .
q p C p , q s k = q p C q , p s k = 1 s k , p m s k ,
s k , p ( m s k m s k [ 0 ] ) , q m s k ( q p ) :
u p s k u q s k + N s k C p , q s k N s k 1 ,
L i j s k ( N s k 1 ) t s k C i , j s k g i , j .
TR i j : j i ( L i j + L j i ) + s k LT s k B i s k i .
h m s k I h s k = 1 s k .
L i j ( s k t s k I j s k B i s k ) g i , j ( i j ) .
LT s k = H s k s k .
TR saved = s k N s k ( N s k t s k g ( N s k 1 ) t s k g ) .
t ¯ = s k N s k t s k s k N s k .