Abstract

Light-trees can efficiently guarantee point-to-multipoint connection in optical networks for many widely used multicast applications, such as Internet protocol television (IPTV). The establishment of a light-tree requires the placement of 3R regenerators along the tree due to the wavelength continuity constraint and physical impairments. Thus, the problem is to establish a light-tree and to assign wavelengths such that the number of regenerators is minimized. We call this problem the efficient 3R regenerator placement (ERP) problem. If we fix the routing of the multicast tree, then how to place a minimum number of regenerators and assign wavelengths to links becomes a subproblem of ERP, which is named the wavelength assignment and regenerator placement (WARP) problem. We find that ERP is NP-hard, and then provide an approximation algorithm named SPT-ReWa, which has a subroutine named ReWa which can solve WARP optimally. We prove that ReWa can find an optimal solution for WARP, and we analyze the approximation ratio of SPT-ReWa for ERP. Finally, we illustrate several simulation scenarios to show the efficiency of SPT-ReWa.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.
  2. S. Sankaranarayanan and S. Subramaniam, "Comprehensive performance modeling and analysis of multicasting in optical networks," IEEE J. Sel. Areas Commun. 21, (9), 1399‒1413 (2003).
    [CrossRef]
  3. D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
    [CrossRef]
  4. T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
    [CrossRef]
  5. M. Hamad and A. E. Kamal, "Efficient power-aware network provisioning for all-optical multicasting in WDM mesh networks," Proc. of IEEE GLOBECOM, 2008, pp. 1‒5.
  6. M. Scheffel, "Regenerator allocation strategies for optical transparency domains considering transmission limitations," Proc. of IEEE ICC, 2005, pp. 1771‒1776.
  7. S. W. Kim, W. W. Seo, and S. C. Kim, "Regenerator placement algorithms for connection establishment in all-optical networks," Proc. of IEEE GLOBECOM, 2000, pp. 1205‒1209.
  8. G. Shen, W. D. Grover, T. H. Chen, and S. K. Bose, "Sparse placement of electronic switching nodes for low blocking in translucent optical networks," J. Opt. Netw. 1, (12), 424‒441 (2002).
  9. X. Yang and B. Ramamurthy, "Dynamic routing in translucent WDM optical networks: the intradomain case," J. Lightwave Technol. 23, (3), 955‒971 (2005).
    [CrossRef]
  10. B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM networks," IEEE J. Sel. Areas Commun. 20, (1), 97‒109 (2002).
    [CrossRef]
  11. I. Chlamtac, A. Farago, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, (5), 909‒913 (2003).
    [CrossRef]
  12. W. Liang and H. Shen, "Multicasting and broadcasting in large WDM networks," Proc. of IPPS/SPDP, 1998, pp. 516‒523.
  13. H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multihop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, (10), 1012‒1025 (1999).
    [CrossRef]
  14. T. F. Znati, T. Alrabiah, and R. Melhem, "Low-cost, delay-bounded point-to-point communication to support multicasting over WDM networks," Comput. Netw. 38, (4), 423‒445 (2002).
    [CrossRef]
  15. http://en.wikipedia.org/wiki/Power_budget
  16. R. Libeskind-Hadas, "Efficient collective communication in WDM networks with a power budget," Proc. of IEEE ICCCN, 2000, pp. 612‒616.
  17. Y. Xin and G. N. Rouskas, "Multicast routing under optical layer constraints," Proc. of IEEE INFOCOM, 2004, pp. 2731‒2742.
  18. R. Libeskind-Hadas and R. Melhem, "Multicast routing and wavelength assignment in multihop optical networks," IEEE/ACM Trans. Netw. 10, (5), 621‒629 (2002).
    [CrossRef]
  19. S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
    [CrossRef]
  20. X. D. Hu, T. P. Shuai, X. Jia, and M. H. Zhang, "Multicast routing and wavelength assignment in WDM networks with limited drops," Proc. of IEEE INFOCOM, 2004, pp. 487‒494.
  21. A. M. Hamad and A. E. Kamal, "Routing and wavelength assignment with power aware multicasting in WDM networks," Proc. of IEEE BROADNETS, 2005, pp. 31‒40.
  22. S. Pachnicke, T. Paschenda, and P. M. Krummrich, "Physical impairment based regenerator placement and routing in translucent optical networks," Proc. of OSA OFC/NFOEC, 2008, pp. 1‒3.
  23. Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
    [CrossRef]
  24. L. Sahasrabuddhe and B. Mukherjee, "Light trees: optical multicasting for improved performance in wavelength routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
    [CrossRef]
  25. Y. Yang, J. Wang, and C. Qiao, "Nonblocking WDM multicast switching networks," IEEE Trans. Parallel Distrib. Syst. 11, (12), 1274‒1287 (2000).
    [CrossRef]
  26. H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).
  27. Edward F. Moore, "The shortest path through a maze," Proc. of the Int. Symp. on the Theory of Switching, Vol. 2, 1959, pp. 285‒292.
  28. C. Y. Lee, "An algorithm for path connection and its applications," IRE Trans. Electron. Comput. 10, (3), 346‒365 (1961).
    [CrossRef]
  29. E. W. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, (1), 269‒271 (1959).
    [CrossRef]

2007 (1)

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

2005 (1)

2003 (2)

S. Sankaranarayanan and S. Subramaniam, "Comprehensive performance modeling and analysis of multicasting in optical networks," IEEE J. Sel. Areas Commun. 21, (9), 1399‒1413 (2003).
[CrossRef]

I. Chlamtac, A. Farago, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, (5), 909‒913 (2003).
[CrossRef]

2002 (4)

T. F. Znati, T. Alrabiah, and R. Melhem, "Low-cost, delay-bounded point-to-point communication to support multicasting over WDM networks," Comput. Netw. 38, (4), 423‒445 (2002).
[CrossRef]

R. Libeskind-Hadas and R. Melhem, "Multicast routing and wavelength assignment in multihop optical networks," IEEE/ACM Trans. Netw. 10, (5), 621‒629 (2002).
[CrossRef]

B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM networks," IEEE J. Sel. Areas Commun. 20, (1), 97‒109 (2002).
[CrossRef]

G. Shen, W. D. Grover, T. H. Chen, and S. K. Bose, "Sparse placement of electronic switching nodes for low blocking in translucent optical networks," J. Opt. Netw. 1, (12), 424‒441 (2002).

2001 (1)

S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
[CrossRef]

2000 (2)

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

Y. Yang, J. Wang, and C. Qiao, "Nonblocking WDM multicast switching networks," IEEE Trans. Parallel Distrib. Syst. 11, (12), 1274‒1287 (2000).
[CrossRef]

1999 (2)

L. Sahasrabuddhe and B. Mukherjee, "Light trees: optical multicasting for improved performance in wavelength routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multihop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, (10), 1012‒1025 (1999).
[CrossRef]

1994 (1)

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

1980 (1)

H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

1961 (1)

C. Y. Lee, "An algorithm for path connection and its applications," IRE Trans. Electron. Comput. 10, (3), 346‒365 (1961).
[CrossRef]

1959 (1)

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, (1), 269‒271 (1959).
[CrossRef]

Alrabiah, T.

T. F. Znati, T. Alrabiah, and R. Melhem, "Low-cost, delay-bounded point-to-point communication to support multicasting over WDM networks," Comput. Netw. 38, (4), 423‒445 (2002).
[CrossRef]

Bose, S. K.

Chen, B.

B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM networks," IEEE J. Sel. Areas Commun. 20, (1), 97‒109 (2002).
[CrossRef]

Chen, T. H.

Chin, F.

H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multihop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, (10), 1012‒1025 (1999).
[CrossRef]

Chlamtac, I.

I. Chlamtac, A. Farago, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, (5), 909‒913 (2003).
[CrossRef]

Dijkstra, E. W.

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, (1), 269‒271 (1959).
[CrossRef]

Du, X.

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

Durhuus, T.

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

Farago, A.

I. Chlamtac, A. Farago, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, (5), 909‒913 (2003).
[CrossRef]

Gao, S.

S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
[CrossRef]

Grover, W. D.

Hamad, A. M.

A. M. Hamad and A. E. Kamal, "Routing and wavelength assignment with power aware multicasting in WDM networks," Proc. of IEEE BROADNETS, 2005, pp. 31‒40.

Hamad, M.

M. Hamad and A. E. Kamal, "Efficient power-aware network provisioning for all-optical multicasting in WDM mesh networks," Proc. of IEEE GLOBECOM, 2008, pp. 1‒5.

Hasegawa, H.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

Hu, W.

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

Hu, X.

S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
[CrossRef]

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

Hu, X. D.

X. D. Hu, T. P. Shuai, X. Jia, and M. H. Zhang, "Multicast routing and wavelength assignment in WDM networks with limited drops," Proc. of IEEE INFOCOM, 2004, pp. 487‒494.

Jia, X.

S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
[CrossRef]

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

X. D. Hu, T. P. Shuai, X. Jia, and M. H. Zhang, "Multicast routing and wavelength assignment in WDM networks with limited drops," Proc. of IEEE INFOCOM, 2004, pp. 487‒494.

Jin, Y.

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

Jinno, M.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

Joergensen, C.

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

Kamal, A. E.

M. Hamad and A. E. Kamal, "Efficient power-aware network provisioning for all-optical multicasting in WDM mesh networks," Proc. of IEEE GLOBECOM, 2008, pp. 1‒5.

A. M. Hamad and A. E. Kamal, "Routing and wavelength assignment with power aware multicasting in WDM networks," Proc. of IEEE BROADNETS, 2005, pp. 31‒40.

Kim, S. C.

S. W. Kim, W. W. Seo, and S. C. Kim, "Regenerator placement algorithms for connection establishment in all-optical networks," Proc. of IEEE GLOBECOM, 2000, pp. 1205‒1209.

Kim, S. W.

S. W. Kim, W. W. Seo, and S. C. Kim, "Regenerator placement algorithms for connection establishment in all-optical networks," Proc. of IEEE GLOBECOM, 2000, pp. 1205‒1209.

Krummrich, P. M.

S. Pachnicke, T. Paschenda, and P. M. Krummrich, "Physical impairment based regenerator placement and routing in translucent optical networks," Proc. of OSA OFC/NFOEC, 2008, pp. 1‒3.

Lee, C. Y.

C. Y. Lee, "An algorithm for path connection and its applications," IRE Trans. Electron. Comput. 10, (3), 346‒365 (1961).
[CrossRef]

Li, D.

S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
[CrossRef]

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

Liang, W.

W. Liang and H. Shen, "Multicasting and broadcasting in large WDM networks," Proc. of IPPS/SPDP, 1998, pp. 516‒523.

Libeskind-Hadas, R.

R. Libeskind-Hadas and R. Melhem, "Multicast routing and wavelength assignment in multihop optical networks," IEEE/ACM Trans. Netw. 10, (5), 621‒629 (2002).
[CrossRef]

R. Libeskind-Hadas, "Efficient collective communication in WDM networks with a power budget," Proc. of IEEE ICCCN, 2000, pp. 612‒616.

Matsuyama, A.

H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Melhem, R.

T. F. Znati, T. Alrabiah, and R. Melhem, "Low-cost, delay-bounded point-to-point communication to support multicasting over WDM networks," Comput. Netw. 38, (4), 423‒445 (2002).
[CrossRef]

R. Libeskind-Hadas and R. Melhem, "Multicast routing and wavelength assignment in multihop optical networks," IEEE/ACM Trans. Netw. 10, (5), 621‒629 (2002).
[CrossRef]

Mikkelsen, B.

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

Moore, Edward F.

Edward F. Moore, "The shortest path through a maze," Proc. of the Int. Symp. on the Theory of Switching, Vol. 2, 1959, pp. 285‒292.

Morita, Y.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

Mukherjee, B.

L. Sahasrabuddhe and B. Mukherjee, "Light trees: optical multicasting for improved performance in wavelength routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

Pachnicke, S.

S. Pachnicke, T. Paschenda, and P. M. Krummrich, "Physical impairment based regenerator placement and routing in translucent optical networks," Proc. of OSA OFC/NFOEC, 2008, pp. 1‒3.

Pan, Y.

H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multihop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, (10), 1012‒1025 (1999).
[CrossRef]

Paschenda, T.

S. Pachnicke, T. Paschenda, and P. M. Krummrich, "Physical impairment based regenerator placement and routing in translucent optical networks," Proc. of OSA OFC/NFOEC, 2008, pp. 1‒3.

Pedersen, R. J. S.

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

Peng, Y.

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

Qiao, C.

Y. Yang, J. Wang, and C. Qiao, "Nonblocking WDM multicast switching networks," IEEE Trans. Parallel Distrib. Syst. 11, (12), 1274‒1287 (2000).
[CrossRef]

Ramamurthy, B.

Rouskas, G. N.

Y. Xin and G. N. Rouskas, "Multicast routing under optical layer constraints," Proc. of IEEE INFOCOM, 2004, pp. 2731‒2742.

Ruan, L.

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

Sahasrabuddhe, L.

L. Sahasrabuddhe and B. Mukherjee, "Light trees: optical multicasting for improved performance in wavelength routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

Sankaranarayanan, S.

S. Sankaranarayanan and S. Subramaniam, "Comprehensive performance modeling and analysis of multicasting in optical networks," IEEE J. Sel. Areas Commun. 21, (9), 1399‒1413 (2003).
[CrossRef]

Sato, K.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

Scheffel, M.

M. Scheffel, "Regenerator allocation strategies for optical transparency domains considering transmission limitations," Proc. of IEEE ICC, 2005, pp. 1771‒1776.

Seo, W. W.

S. W. Kim, W. W. Seo, and S. C. Kim, "Regenerator placement algorithms for connection establishment in all-optical networks," Proc. of IEEE GLOBECOM, 2000, pp. 1205‒1209.

Shen, G.

Shen, H.

H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multihop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, (10), 1012‒1025 (1999).
[CrossRef]

W. Liang and H. Shen, "Multicasting and broadcasting in large WDM networks," Proc. of IPPS/SPDP, 1998, pp. 516‒523.

Shuai, T. P.

X. D. Hu, T. P. Shuai, X. Jia, and M. H. Zhang, "Multicast routing and wavelength assignment in WDM networks with limited drops," Proc. of IEEE INFOCOM, 2004, pp. 487‒494.

Sone, Y.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

Stubkjaer, K. E.

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

Subramaniam, S.

S. Sankaranarayanan and S. Subramaniam, "Comprehensive performance modeling and analysis of multicasting in optical networks," IEEE J. Sel. Areas Commun. 21, (9), 1399‒1413 (2003).
[CrossRef]

Sun, W.

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

Takahashi, H.

H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Wang, J.

B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM networks," IEEE J. Sel. Areas Commun. 20, (1), 97‒109 (2002).
[CrossRef]

Y. Yang, J. Wang, and C. Qiao, "Nonblocking WDM multicast switching networks," IEEE Trans. Parallel Distrib. Syst. 11, (12), 1274‒1287 (2000).
[CrossRef]

Wang, X.

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

Xin, Y.

Y. Xin and G. N. Rouskas, "Multicast routing under optical layer constraints," Proc. of IEEE INFOCOM, 2004, pp. 2731‒2742.

Yamada, K.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

Yang, X.

Yang, Y.

Y. Yang, J. Wang, and C. Qiao, "Nonblocking WDM multicast switching networks," IEEE Trans. Parallel Distrib. Syst. 11, (12), 1274‒1287 (2000).
[CrossRef]

Zhang, M. H.

X. D. Hu, T. P. Shuai, X. Jia, and M. H. Zhang, "Multicast routing and wavelength assignment in WDM networks with limited drops," Proc. of IEEE INFOCOM, 2004, pp. 487‒494.

Zhang, T.

I. Chlamtac, A. Farago, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, (5), 909‒913 (2003).
[CrossRef]

Znati, T. F.

T. F. Znati, T. Alrabiah, and R. Melhem, "Low-cost, delay-bounded point-to-point communication to support multicasting over WDM networks," Comput. Netw. 38, (4), 423‒445 (2002).
[CrossRef]

Comput. Netw. (1)

T. F. Znati, T. Alrabiah, and R. Melhem, "Low-cost, delay-bounded point-to-point communication to support multicasting over WDM networks," Comput. Netw. 38, (4), 423‒445 (2002).
[CrossRef]

IEE Proc.-Commun. (1)

S. Gao, X. Jia, X. Hu, and D. Li, "Wavelength requirements and routing for multicast connections in lightpath and light-tree models of WDM networks with limited drops," IEE Proc.-Commun. 148, (6), 363‒367 (2001).
[CrossRef]

IEEE Commun. Mag. (1)

L. Sahasrabuddhe and B. Mukherjee, "Light trees: optical multicasting for improved performance in wavelength routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

IEEE J. Sel. Areas Commun. (3)

B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM networks," IEEE J. Sel. Areas Commun. 20, (1), 97‒109 (2002).
[CrossRef]

I. Chlamtac, A. Farago, and T. Zhang, "Lightpath (wavelength) routing in large WDM networks," IEEE J. Sel. Areas Commun. 14, (5), 909‒913 (2003).
[CrossRef]

S. Sankaranarayanan and S. Subramaniam, "Comprehensive performance modeling and analysis of multicasting in optical networks," IEEE J. Sel. Areas Commun. 21, (9), 1399‒1413 (2003).
[CrossRef]

IEEE Photon. Technol. Lett. (1)

T. Durhuus, C. Joergensen, B. Mikkelsen, R. J. S. Pedersen, and K. E. Stubkjaer, "All optical wavelength conversion by SOA’s in a Mach–Zehnder Configuration," IEEE Photon. Technol. Lett. 6, (1), 53‒55 (1994).
[CrossRef]

IEEE Trans. Parallel Distrib. Syst. (2)

H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multihop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, (10), 1012‒1025 (1999).
[CrossRef]

Y. Yang, J. Wang, and C. Qiao, "Nonblocking WDM multicast switching networks," IEEE Trans. Parallel Distrib. Syst. 11, (12), 1274‒1287 (2000).
[CrossRef]

IEEE/ACM Trans. Netw. (1)

R. Libeskind-Hadas and R. Melhem, "Multicast routing and wavelength assignment in multihop optical networks," IEEE/ACM Trans. Netw. 10, (5), 621‒629 (2002).
[CrossRef]

IRE Trans. Electron. Comput. (1)

C. Y. Lee, "An algorithm for path connection and its applications," IRE Trans. Electron. Comput. 10, (3), 346‒365 (1961).
[CrossRef]

J. Lightwave Technol. (1)

J. Opt. Netw. (1)

Math. Japonica (1)

H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Networks (1)

D. Li, X. Du, X. Hu, L. Ruan, and X. Jia, "Minimizing number of wavelengths in multicast routing trees in WDM networks," Networks 35, (4), 260‒265 (2000).
[CrossRef]

Numer. Math. (1)

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math. 1, (1), 269‒271 (1959).
[CrossRef]

Photonic Network Commun. (1)

Y. Peng, W. Hu, W. Sun, X. Wang, and Y. Jin, "Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing," Photonic Network Commun. 13, (1), 93‒102 (2007).
[CrossRef]

Other (12)

Edward F. Moore, "The shortest path through a maze," Proc. of the Int. Symp. on the Theory of Switching, Vol. 2, 1959, pp. 285‒292.

X. D. Hu, T. P. Shuai, X. Jia, and M. H. Zhang, "Multicast routing and wavelength assignment in WDM networks with limited drops," Proc. of IEEE INFOCOM, 2004, pp. 487‒494.

A. M. Hamad and A. E. Kamal, "Routing and wavelength assignment with power aware multicasting in WDM networks," Proc. of IEEE BROADNETS, 2005, pp. 31‒40.

S. Pachnicke, T. Paschenda, and P. M. Krummrich, "Physical impairment based regenerator placement and routing in translucent optical networks," Proc. of OSA OFC/NFOEC, 2008, pp. 1‒3.

Y. Morita, H. Hasegawa, K. Sato, Y. Sone, K. Yamada, and M. Jinno, "Optical multicast tree construction algorithm considering SNR constraint and 3R regeneration," Proc. of ECOC, 2008, pp. 1‒2.

M. Hamad and A. E. Kamal, "Efficient power-aware network provisioning for all-optical multicasting in WDM mesh networks," Proc. of IEEE GLOBECOM, 2008, pp. 1‒5.

M. Scheffel, "Regenerator allocation strategies for optical transparency domains considering transmission limitations," Proc. of IEEE ICC, 2005, pp. 1771‒1776.

S. W. Kim, W. W. Seo, and S. C. Kim, "Regenerator placement algorithms for connection establishment in all-optical networks," Proc. of IEEE GLOBECOM, 2000, pp. 1205‒1209.

W. Liang and H. Shen, "Multicasting and broadcasting in large WDM networks," Proc. of IPPS/SPDP, 1998, pp. 516‒523.

http://en.wikipedia.org/wiki/Power_budget

R. Libeskind-Hadas, "Efficient collective communication in WDM networks with a power budget," Proc. of IEEE ICCCN, 2000, pp. 612‒616.

Y. Xin and G. N. Rouskas, "Multicast routing under optical layer constraints," Proc. of IEEE INFOCOM, 2004, pp. 2731‒2742.

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 (9)

Fig. 1
Fig. 1

(Color online) Switch architecture illustration.

Fig. 2
Fig. 2

(Color online) Example for regenerator placement.

Fig. 3
Fig. 3

(Color online) Example for u with different roles for tree T.

Fig. 4
Fig. 4

Special network topology G ( V , E ) .

Fig. 5
Fig. 5

(Color online) Example of algorithm comparison.

Fig. 6
Fig. 6

Topology for simulation.

Fig. 7
Fig. 7

(Color online) Number of regenerators ( | R ( T ) | ) versus reachability ( R E = 1 2 log β H ).

Fig. 8
Fig. 8

(Color online) Number of regenerators ( | R ( T ) | ) versus number of nodes (N): R E = 1 2 log β H = 4 .

Fig. 9
Fig. 9

(Color online) Number of regenerators ( | R ( T ) | ) versus number of nodes (N): R E = 1 2 log β H = 8 .

Tables (3)

Tables Icon

Table I Symbol Definitions for the Network

Tables Icon

Table II Symbol Definitions for Power Issues

Tables Icon

Table III Comparison Between SPT-ReWa, MCP-ReWa, and Optimal Solution

Equations (13)

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

P i n ( v ) = P o u t ( u ) ( G a m p e α | u v | ) | u v | S = P o u t ( u ) Q | u v | ,
F ( u , v ) = P i n ( v ) = P o u t ( u ) Q | u v | .
F ( s ) = L O S W 1 L O S W 2 L MUX G o u t L t a p | C T s | P i n ( s ) ,
F ( u ) = L O S W 1 L MUX G o u t L t a p P i n ( s ) .
F ( u ) = P i n ( s ) β | C T s | .
F ( u ) = P o u t ( u ) = P i n ( u ) β 2 | C T s | ,
F ( u ) = P o u t ( u ) = P i n ( u ) β 2 .
F ( u ) = P o u t ( u ) = P i n ( u ) β .
F ( u ) = P o u t ( u ) = P i n ( u ) β 2 | C T u | + 1 .
F ( u ) = β | C T u | P i n ( s ) .
F ( u ) = β P i n ( s ) .
| R ( S P T ) | | R ( T ) | | R ( S P T ) | u p | R ( T ) | l o w | S P T | n log H β | S P T | n log H β .
γ = | R ( S P T ) | | R ( T ) | | S P T | n log H β 2 log β H = 4 R E ,