Abstract

The problem of placing optical amplifiers (OAs) in wavelength-routing mesh networks has been studied in the literature in two contexts: network provisioning [1] and connections provisioning [2]. In this paper, we introduce optimal and heuristic solutions for the network provisioning problem. The solution is based on constructing a multicast forest for each multicast connection with the goal of minimizing the total number of OAs needed in the network, hence reducing its cost. The optimal solution is formulated as a mixed integer linear program (MILP). On the other hand, the heuristic solution is obtained by dividing the problem into subproblems and solving them separately while taking the interdependency between these subproblems into consideration. The results obtained from both solutions are compared and they are found to be a good match.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Hamad, A. Kamal, “Optimal power-aware design of all-optical multicasting in wavelength routed networks,” in Proc. IEEE ICC ’04, vol. 3, June 2004, pp. 1796–1800.
  2. A. Hamad, A. Kamal and , “Routing and wavelength assignment with power aware multicasting in WDM networks,” in Proc. IEEE Broadnets ’05, vol. 1, Oct. 2005, pp. 31–40.
  3. H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” SPIE Opt. Networks Mag., vol. 1, no. 1, Jan. 2000.
  4. A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
    [CrossRef]
  5. G. Rouskas, “Optical layer multicast: rationale, building blocks, and challenges,” IEEE Network, vol. 17, no. 1, pp. 60–65, Jan.–Feb. 2003.
    [CrossRef]
  6. L. 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]
  7. B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the unequally powered wavelengths case,” IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 755–767, Dec. 1998.
    [CrossRef]
  8. A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.
  9. B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the equally powered-wavelengths case,” J. Lightwave Technol., vol. 16, no. 9, pp. 1560–1569, Sept. 1998.
    [CrossRef]
  10. J. W. K. Wu, C. Yang, “Multicast routing with power consideration in sparse splitting WDM networks,” in Proc. IEEE Int. Conf. on Communication (ICC01), 2001, pp. 513–517.
  11. X. Yufeng, G. Rouskas, “Multicast routing under optical layer constraints,” in Proc. IEEE INFOCOM ’04, 2004.
  12. R. Ramaswami, K. N. Sivarajan, Optical Networks: A Practical Perspective, 2nd ed. Morgan Kaufmann, 2002.
  13. X. Zhang, J. Y. Wei, C. Qiao, “Constrained multicast routing in WDM networks with sparse light splitting,” J. Lightwave Technol., vol. 18, no. 12, pp. 1917–1927, Dec. 2000.
    [CrossRef]
  14. Http://www.ilog.com/products/cplex/.

2006 (1)

A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
[CrossRef]

2003 (1)

G. Rouskas, “Optical layer multicast: rationale, building blocks, and challenges,” IEEE Network, vol. 17, no. 1, pp. 60–65, Jan.–Feb. 2003.
[CrossRef]

2000 (2)

X. Zhang, J. Y. Wei, C. Qiao, “Constrained multicast routing in WDM networks with sparse light splitting,” J. Lightwave Technol., vol. 18, no. 12, pp. 1917–1927, Dec. 2000.
[CrossRef]

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” SPIE Opt. Networks Mag., vol. 1, no. 1, Jan. 2000.

1999 (1)

L. 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]

1998 (2)

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the unequally powered wavelengths case,” IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 755–767, Dec. 1998.
[CrossRef]

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the equally powered-wavelengths case,” J. Lightwave Technol., vol. 16, no. 9, pp. 1560–1569, Sept. 1998.
[CrossRef]

Balestra, G.

A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.

Hamad, A.

A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
[CrossRef]

A. Hamad, A. Kamal and , “Routing and wavelength assignment with power aware multicasting in WDM networks,” in Proc. IEEE Broadnets ’05, vol. 1, Oct. 2005, pp. 31–40.

A. Hamad, A. Kamal, “Optimal power-aware design of all-optical multicasting in wavelength routed networks,” in Proc. IEEE ICC ’04, vol. 3, June 2004, pp. 1796–1800.

Iness, J.

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the unequally powered wavelengths case,” IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 755–767, Dec. 1998.
[CrossRef]

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the equally powered-wavelengths case,” J. Lightwave Technol., vol. 16, no. 9, pp. 1560–1569, Sept. 1998.
[CrossRef]

John, M.

A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.

Jue, J.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” SPIE Opt. Networks Mag., vol. 1, no. 1, Jan. 2000.

Kamal, A.

A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
[CrossRef]

A. Hamad, A. Kamal and , “Routing and wavelength assignment with power aware multicasting in WDM networks,” in Proc. IEEE Broadnets ’05, vol. 1, Oct. 2005, pp. 31–40.

A. Hamad, A. Kamal, “Optimal power-aware design of all-optical multicasting in wavelength routed networks,” in Proc. IEEE ICC ’04, vol. 3, June 2004, pp. 1796–1800.

Mukherjee, B.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” SPIE Opt. Networks Mag., vol. 1, no. 1, Jan. 2000.

L. 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]

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the equally powered-wavelengths case,” J. Lightwave Technol., vol. 16, no. 9, pp. 1560–1569, Sept. 1998.
[CrossRef]

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the unequally powered wavelengths case,” IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 755–767, Dec. 1998.
[CrossRef]

Qiao, C.

X. Zhang, J. Y. Wei, C. Qiao, “Constrained multicast routing in WDM networks with sparse light splitting,” J. Lightwave Technol., vol. 18, no. 12, pp. 1917–1927, Dec. 2000.
[CrossRef]

A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.

Ramamurthy, B.

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the unequally powered wavelengths case,” IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 755–767, Dec. 1998.
[CrossRef]

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the equally powered-wavelengths case,” J. Lightwave Technol., vol. 16, no. 9, pp. 1560–1569, Sept. 1998.
[CrossRef]

Ramaswami, R.

R. Ramaswami, K. N. Sivarajan, Optical Networks: A Practical Perspective, 2nd ed. Morgan Kaufmann, 2002.

Rouskas, G.

G. Rouskas, “Optical layer multicast: rationale, building blocks, and challenges,” IEEE Network, vol. 17, no. 1, pp. 60–65, Jan.–Feb. 2003.
[CrossRef]

X. Yufeng, G. Rouskas, “Multicast routing under optical layer constraints,” in Proc. IEEE INFOCOM ’04, 2004.

Sahasrabuddhe, L.

L. 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]

Sivarajan, K. N.

R. Ramaswami, K. N. Sivarajan, Optical Networks: A Practical Perspective, 2nd ed. Morgan Kaufmann, 2002.

Somani, A.

A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
[CrossRef]

Umagalli, A.

A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.

Valcarenghi, L.

A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.

Wei, J. Y.

Wu, J. W. K.

J. W. K. Wu, C. Yang, “Multicast routing with power consideration in sparse splitting WDM networks,” in Proc. IEEE Int. Conf. on Communication (ICC01), 2001, pp. 513–517.

Wu, T.

A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
[CrossRef]

Yang, C.

J. W. K. Wu, C. Yang, “Multicast routing with power consideration in sparse splitting WDM networks,” in Proc. IEEE Int. Conf. on Communication (ICC01), 2001, pp. 513–517.

Yufeng, X.

X. Yufeng, G. Rouskas, “Multicast routing under optical layer constraints,” in Proc. IEEE INFOCOM ’04, 2004.

Zang, H.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” SPIE Opt. Networks Mag., vol. 1, no. 1, Jan. 2000.

Zhang, X.

Computer Networks (1)

A. Hamad, T. Wu, A. Kamal, A. Somani, “Multicasting protocols for wavelength routing networks,” Computer Networks, vol. 50, no. 16, pp. 3105–3164, Nov. 2006.
[CrossRef]

IEEE Commun. Mag. (1)

L. 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 Network (1)

G. Rouskas, “Optical layer multicast: rationale, building blocks, and challenges,” IEEE Network, vol. 17, no. 1, pp. 60–65, Jan.–Feb. 2003.
[CrossRef]

IEEE/ACM Trans. Netw. (1)

B. Ramamurthy, J. Iness, B. Mukherjee, “Optimizing amplifier placements in a multiwavelength optical LAN/MAN: the unequally powered wavelengths case,” IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 755–767, Dec. 1998.
[CrossRef]

J. Lightwave Technol. (2)

SPIE Opt. Networks Mag. (1)

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” SPIE Opt. Networks Mag., vol. 1, no. 1, Jan. 2000.

Other (7)

A. Umagalli, G. Balestra, L. Valcarenghi, M. John, C. Qiao, “Optimal amplifier placement in multi-wavelength optical networks based on simulated annealing,” in SPIE Proceedings Series–International Society for Optical Engineering Proceedings Series, vol. 3531, 1998, pp. 268–279.

J. W. K. Wu, C. Yang, “Multicast routing with power consideration in sparse splitting WDM networks,” in Proc. IEEE Int. Conf. on Communication (ICC01), 2001, pp. 513–517.

X. Yufeng, G. Rouskas, “Multicast routing under optical layer constraints,” in Proc. IEEE INFOCOM ’04, 2004.

R. Ramaswami, K. N. Sivarajan, Optical Networks: A Practical Perspective, 2nd ed. Morgan Kaufmann, 2002.

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

A. Hamad, A. Kamal, “Optimal power-aware design of all-optical multicasting in wavelength routed networks,” in Proc. IEEE ICC ’04, vol. 3, June 2004, pp. 1796–1800.

A. Hamad, A. Kamal and , “Routing and wavelength assignment with power aware multicasting in WDM networks,” in Proc. IEEE Broadnets ’05, vol. 1, Oct. 2005, pp. 31–40.

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

Fig. 1
Fig. 1

Basic operation of the OP algorithm.

Fig. 2
Fig. 2

Tree construction module.

Fig. 3
Fig. 3

Tree placement module.

Fig. 4
Fig. 4

Six nodes mesh network.

Fig. 5
Fig. 5

NSFNET.

Fig. 6
Fig. 6

Impact of using alternative routing on the number of OAs for the fixed routing scheme at different traffic loads. The notation T i ( F ) indicates that the system traffic load ( T ) is i sessions for the fixed ( F ) scheme.

Fig. 7
Fig. 7

Impact of using alternative routing on the number of OAs for the adaptive routing scheme at different traffic loads. The notation T i ( R ) indicates that the system traffic load ( T ) is i sessions for the adaptive (or Rerouting, R) scheme.

Fig. 8
Fig. 8

Maximum number of used channels ( ψ ) at different traffic loads for the fixed scheme and the adaptive scheme when the number of alternative paths is 1.

Fig. 9
Fig. 9

Number of used links ( Ł ) at different traffic loads for the fixed scheme and the adaptive scheme when the number of alternative paths is 1.

Fig. 10
Fig. 10

Network bandwidth utilization (NBU) achieved at various traffic loads by the fixed scheme and adaptive scheme when one alternative path is used.

Fig. 11
Fig. 11

Comparison of the network bandwidth utilization (NBU) achieved with different alternative paths when the fixed scheme is used at various traffic loads.

Fig. 12
Fig. 12

Comparison of the network bandwidth utilization (NBU) achieved with different alternative paths when adaptive scheme is used at various traffic loads.

Tables (4)

Tables Icon

Table 1 Typical Values for the System Parameters

Tables Icon

Table 2 Comparison of OA Numbers Obtained by CPLEX ( O A C ) and the Heuristic ( O A i , Where i = 1 , 2 , 3 , 4 Represents the Number of Alternative Paths) for the 6-Mesh Network. k and Λ Represent the Number of Sessions and Available Lambda, Respectively

Tables Icon

Table 3 Comparison of Used Network Resources for the 6-Mesh Network. ψ C ( Ł C ) and ψ i ( Ł i ) Represent the Maximum Number of Wavelengths (Number of Links) Used by CPLEX, and the OP Heuristic, Respectively. i = 1 , 2 , 3 , 4 Represents the Number of Alternative Paths, While k and λ Represent the Number of Sessions and Available Lambda, Respectively

Tables Icon

Table 4 The Relative Performance of Using the Adaptive Method Alone With Respect to Alternative Routing at Different Traffic Loads

Equations (57)

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

G ( P in ) = MIN { G 0 , ( P MAX P in ) } ,
Minimize e ( i , j ) E n i , j .
I i a , λ j , j i , e ( i , j ) E T i , j a , λ M
i N ; 0 a < K ; λ Λ ,
I i a , λ j , j i , e ( i , j ) E T i , j a , λ
i N ; 0 a < K ; λ Λ ,
Υ i a λ Λ I i a , λ M
i N ; 0 a < K ; λ Λ ,
Υ i a λ Λ I i a , λ
i N ; 0 a < K ; λ Λ :
i , i s r c a , e ( i , s r c a ) E λ Λ T i , s r c a a , λ = 0 0 a < K :
λ Λ I i a , λ = λ Λ k , k i , e ( k , i ) E T k , i a , λ { Γ i a ( 1 Υ i a ) }
i N ; i s r c a ; 0 a < K :
k , k i , e ( k , i ) E T k , i a , λ 1
i N ; i s r c a ; 0 a < K ; λ Λ :
0 a < K , e ( k , i ) E T i , j a , λ 1 i , j N ; i j ; λ Λ :
j , i j , e ( i , j ) E T i , j a , λ M α i + 1
i N ; i s r c a ; 0 a < K ; λ Λ :
j , j i , e ( j , i ) E T j , i a , λ k , k i , e ( i , k ) E T i , k a , λ M
i N ; i s r c a ; 0 a < K :
i α i S i N :
H s r c a a , λ = 0 0 a < K ; λ Λ :
1 T i , j a , λ H i a , λ + 1 H j a , λ M 0
e ( i , j ) E ; 0 a < K ; λ Λ ,
Γ i a + H i a , λ ( N 1 ) M 1
e ( i , j ) E ; 0 a < K ; λ Λ :
P i , j Ω , a , λ P Sen T i , j a , λ + P 1 ( 1 T i , j a , λ )
e ( i , j ) E ; Ω { beg , end } ; 0 a < K ; λ Λ ,
P i , j Ω , a , λ P Max K T i , j a , λ + P 2 ( 1 T i , j a , λ )
e ( i , j ) E ; Ω { beg , end } ; 0 a < K ; λ Λ :
P i , j beg , a , λ 1 P i , j beg , b , λ 2 = 3 × M × ( T i , j a , λ 1 T i , j b , λ 2 )
e ( i , j ) ; 0 a , b < K ; λ 1 , λ 2 , Λ , λ 1 λ 2 :
( 1 T i , j a , λ ) M + P i , j end , a , λ = ( 1 T i , j a , λ ) ( M ) + P i , j beg , a , λ + L G i , j β L i , j
e ( i , j ) E ; 0 a < K ; λ Λ :
( 1 T i , j a , λ ) v + P i , j end , a , λ S L j a , λ γ ( 1 T j , k a , λ ) w + P j , k beg , a , λ
e ( i , j ) , e ( j , k ) E ; 0 a < K ; λ Λ ,
( 1 T i , j a , λ ) w + P i , j end , a , λ S L j a , λ γ
( 1 T j , k a , λ ) v + P j , k beg , a , λ
e ( i , j ) , e ( j , k ) E ; 0 a < K ; λ Λ :
S L i a , λ M α i i N ; 0 a < K ; λ Λ :
j , j s r c a , e ( i , j ) E T i , j a , λ f + δ M A f
i N ; 0 a < K ; λ Λ ; 2 f < Out i ,
A f { 10 log 10 f } S L i a , λ
i N ; 0 a < K ; λ Λ ; 2 f < Out i ,
S L i a , λ 0 i N ; 0 a < K ; λ Λ .
L G i , j g max × n i , j e ( i , j ) ,
L G i , j > g max × ( n i , j 1 ) e ( i , j ) :
S L i , j a , λ = 10 log 10 S R i , j a , λ ,
( 1 T i , j a , λ ) v + P i , j end , a , λ S L j , k a , λ γ ( 1 T j , k a , λ ) w + P j , k beg , a , λ
e ( i , j ) , e ( j , k ) E ; 0 a < K ; λ Λ ,
( 1 T i , j a , λ ) w + P i , j end , a , λ S L j , k a , λ γ ( 1 T j , k a , λ ) v + P j , k beg , a , λ
e ( i , j ) , e ( j , k ) E ; 0 a < K ; λ Λ .
S i a , λ e ( i , j ) E T i , j a , λ M i N ; 0 a < K ; λ Λ ,
S i a , λ e ( i , j ) E T i , j a , λ i N ; 0 a < K ; λ Λ :
e ( i , j ) E S R i , j a , λ = S i a , λ i N ; 0 a < K ; λ Λ ,
S L i , j a , λ = 10 log 10 S R i , j a , λ
e ( i , j ) ; 0 a < K ; λ Λ :