Abstract

Due to the impairments in optical fiber transmission, regeneration is needed in certain intermediate nodes for some lengthy lightpaths. This kind of optical networks is called translucent optical networks. Spare transceivers in the optical nodes can be used for regeneration. The problem of maximizing the number of established connections (NEC) in the translucent optical networks can be formulated as a mixed-integer linear programming (MILP) problem. This formulation can only be solvable for small networks but for large networks and large traffic matrix the MILP formulation is intractable. Hence an effective heuristic algorithm based on K-least-wavelength-weight-path routing and statistical method is proposed. For small networks, which can be handled by MILP, the results show that the heuristic algorithm also yields the optimal solutions in most cases. The ability of the heuristic algorithm to handle large networks makes it suitable for use in a route engine as well as in a network design tool.

© 2003 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. N. Wauters and P. Demeester, “Design of the optical path layer in multi-wavelength cross-connected networks,” IEEE J. Sel. Areas Commun. 14, 881–892 (1996)
    [Crossref]
  2. S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997)
    [Crossref]
  3. R. K. Pankaj and R. G. Gallager, “Wavelength requirements of all-optical networks,” IEEE/ACM Trans. Netw. 3, 269–280 (1995)
    [Crossref]
  4. Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
    [Crossref]
  5. R. Ramaswami and K. N. Sivarajan. “Routing and Wavelength Assignment in All-Optical Networks,” IEEE/ACM Trans. Netw. 3, 489–500 (1995)
    [Crossref]
  6. M. D. Swaminathan and K. N. Sivarajan, “Practical Routing and Wavelength Assignment Algorithms for All Optical Networks with Limited Wavelength Conversion,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp.2750–2755
  7. H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM Networks,” Opt. Netw. Mag. 1, 47–60, (2000).
  8. R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective (Morgan Kaufmann, 1998)
  9. H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
    [Crossref]
  10. L. Noirie, “The Road Towards All-Optical Networks,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Atlanta, GA, 2003), pp.615–616
  11. R. Sabella, E. Iannone, and M. Listanti, et al. “Impact of Transmission Performance on Path Routing in All-Optical Transport Networks,” J. Lightwave Technol. 16, 1965–1972 (1998)
    [Crossref]
  12. B. Ramamurthy, D. Data, and H. Feng, et al. “Impact of Transmission Impairments on the Teletraffic Performance of Wavelength-Routed Optical Networks,” J. Lightwave Technol. 17, 1713–1723 (1999)
    [Crossref]
  13. B. Ramamurthy, D. Datta, and H. Feng, et al. “Transparent vs. opaque vs. translucent wavelength-routed optical network,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 1999), pp. 59–61
  14. A.A.M Saleh, “Islands of Transparency-an Emerging Reality in Multiwave Optical Networking,” in Proceedings of 11th Annual Meeting IEEE lasers and Electro-Optics Society (Institute of Electrical and Electronics Engineering, New York, NY, 1998), p36
  15. G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)
  16. X. Yang and B. Ramamuthy, “Sparse Regeneration in a Translucent WDM Optical Network,” in Proceedings of APOC2001, Proc. SPIE4585, 61–70, (2001)
    [Crossref]
  17. B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent Optical WDM Networks for the Next-Generation Backbone Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, San Antonio, TX, 2001), pp. 60–64
  18. X. Yang and B. Ramamurthy, “Dynamic Routing in Translucent WDM Optical Networks,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp. 2796–2802
  19. M. Ali, B. Ramamurthy, and J. S. Deogun, “Routing and Wavelength Assignment (RWA) with Power Consideration in All-Optical Wavelength-Routed Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, Rio de Janeiro, Brazil, 1999), pp. 1433–1437
  20. J. Y. Yen, “Finding the K shortest loopless paths in a network,” Manag. Sci. 17, 712–716, (1971)
    [Crossref]

2002 (2)

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
[Crossref]

G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)

2000 (2)

H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM Networks,” Opt. Netw. Mag. 1, 47–60, (2000).

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

1999 (1)

1998 (1)

1997 (1)

S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997)
[Crossref]

1996 (1)

N. Wauters and P. Demeester, “Design of the optical path layer in multi-wavelength cross-connected networks,” IEEE J. Sel. Areas Commun. 14, 881–892 (1996)
[Crossref]

1995 (2)

R. K. Pankaj and R. G. Gallager, “Wavelength requirements of all-optical networks,” IEEE/ACM Trans. Netw. 3, 269–280 (1995)
[Crossref]

R. Ramaswami and K. N. Sivarajan. “Routing and Wavelength Assignment in All-Optical Networks,” IEEE/ACM Trans. Netw. 3, 489–500 (1995)
[Crossref]

1971 (1)

J. Y. Yen, “Finding the K shortest loopless paths in a network,” Manag. Sci. 17, 712–716, (1971)
[Crossref]

Ali, M.

M. Ali, B. Ramamurthy, and J. S. Deogun, “Routing and Wavelength Assignment (RWA) with Power Consideration in All-Optical Wavelength-Routed Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, Rio de Janeiro, Brazil, 1999), pp. 1433–1437

Baroni, S.

S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997)
[Crossref]

Bayvel, P.

S. Baroni and P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol. 15, 242–251 (1997)
[Crossref]

Bose, S. K.

G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)

Cheng, T. H.

G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)

Dai, W.

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Data, D.

Datta, D.

B. Ramamurthy, D. Datta, and H. Feng, et al. “Transparent vs. opaque vs. translucent wavelength-routed optical network,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 1999), pp. 59–61

Demeester, P.

N. Wauters and P. Demeester, “Design of the optical path layer in multi-wavelength cross-connected networks,” IEEE J. Sel. Areas Commun. 14, 881–892 (1996)
[Crossref]

Deogun, J. S.

M. Ali, B. Ramamurthy, and J. S. Deogun, “Routing and Wavelength Assignment (RWA) with Power Consideration in All-Optical Wavelength-Routed Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, Rio de Janeiro, Brazil, 1999), pp. 1433–1437

Feng, F.

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Feng, H.

B. Ramamurthy, D. Data, and H. Feng, et al. “Impact of Transmission Impairments on the Teletraffic Performance of Wavelength-Routed Optical Networks,” J. Lightwave Technol. 17, 1713–1723 (1999)
[Crossref]

B. Ramamurthy, D. Datta, and H. Feng, et al. “Transparent vs. opaque vs. translucent wavelength-routed optical network,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 1999), pp. 59–61

Gallager, R. G.

R. K. Pankaj and R. G. Gallager, “Wavelength requirements of all-optical networks,” IEEE/ACM Trans. Netw. 3, 269–280 (1995)
[Crossref]

Grover, W. D.

G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)

Huo, X.

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Iannone, E.

Jue, J. P.

H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM Networks,” Opt. Netw. Mag. 1, 47–60, (2000).

Listanti, M.

Liu, Z.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
[Crossref]

Mukherjee, B.

H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM Networks,” Opt. Netw. Mag. 1, 47–60, (2000).

Noirie, L.

L. Noirie, “The Road Towards All-Optical Networks,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Atlanta, GA, 2003), pp.615–616

Pankaj, R. K.

R. K. Pankaj and R. G. Gallager, “Wavelength requirements of all-optical networks,” IEEE/ACM Trans. Netw. 3, 269–280 (1995)
[Crossref]

Qin, H.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
[Crossref]

Qin, T.

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Ramamurthy, B.

B. Ramamurthy, D. Data, and H. Feng, et al. “Impact of Transmission Impairments on the Teletraffic Performance of Wavelength-Routed Optical Networks,” J. Lightwave Technol. 17, 1713–1723 (1999)
[Crossref]

X. Yang and B. Ramamurthy, “Dynamic Routing in Translucent WDM Optical Networks,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp. 2796–2802

M. Ali, B. Ramamurthy, and J. S. Deogun, “Routing and Wavelength Assignment (RWA) with Power Consideration in All-Optical Wavelength-Routed Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, Rio de Janeiro, Brazil, 1999), pp. 1433–1437

B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent Optical WDM Networks for the Next-Generation Backbone Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, San Antonio, TX, 2001), pp. 60–64

B. Ramamurthy, D. Datta, and H. Feng, et al. “Transparent vs. opaque vs. translucent wavelength-routed optical network,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 1999), pp. 59–61

Ramamuthy, B.

X. Yang and B. Ramamuthy, “Sparse Regeneration in a Translucent WDM Optical Network,” in Proceedings of APOC2001, Proc. SPIE4585, 61–70, (2001)
[Crossref]

Ramaswami, R.

R. Ramaswami and K. N. Sivarajan. “Routing and Wavelength Assignment in All-Optical Networks,” IEEE/ACM Trans. Netw. 3, 489–500 (1995)
[Crossref]

R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective (Morgan Kaufmann, 1998)

Sabella, R.

Saleh, A.A.M

A.A.M Saleh, “Islands of Transparency-an Emerging Reality in Multiwave Optical Networking,” in Proceedings of 11th Annual Meeting IEEE lasers and Electro-Optics Society (Institute of Electrical and Electronics Engineering, New York, NY, 1998), p36

Shen, G.

G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)

Sivarajan, K. N.

R. Ramaswami and K. N. Sivarajan. “Routing and Wavelength Assignment in All-Optical Networks,” IEEE/ACM Trans. Netw. 3, 489–500 (1995)
[Crossref]

R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective (Morgan Kaufmann, 1998)

M. D. Swaminathan and K. N. Sivarajan, “Practical Routing and Wavelength Assignment Algorithms for All Optical Networks with Limited Wavelength Conversion,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp.2750–2755

Swaminathan, M. D.

M. D. Swaminathan and K. N. Sivarajan, “Practical Routing and Wavelength Assignment Algorithms for All Optical Networks with Limited Wavelength Conversion,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp.2750–2755

Wauters, N.

N. Wauters and P. Demeester, “Design of the optical path layer in multi-wavelength cross-connected networks,” IEEE J. Sel. Areas Commun. 14, 881–892 (1996)
[Crossref]

Wen, A.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
[Crossref]

Yang, X.

X. Yang and B. Ramamuthy, “Sparse Regeneration in a Translucent WDM Optical Network,” in Proceedings of APOC2001, Proc. SPIE4585, 61–70, (2001)
[Crossref]

B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent Optical WDM Networks for the Next-Generation Backbone Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, San Antonio, TX, 2001), pp. 60–64

X. Yang and B. Ramamurthy, “Dynamic Routing in Translucent WDM Optical Networks,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp. 2796–2802

Yaragorla, S.

B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent Optical WDM Networks for the Next-Generation Backbone Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, San Antonio, TX, 2001), pp. 60–64

Ye, Y.

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Yen, J. Y.

J. Y. Yen, “Finding the K shortest loopless paths in a network,” Manag. Sci. 17, 712–716, (1971)
[Crossref]

Zang, H.

H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM Networks,” Opt. Netw. Mag. 1, 47–60, (2000).

Zhang, H.

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Zhang, S.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
[Crossref]

IEEE Commun. Lett. (1)

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and Wavelength Assignment Based on Genetic Algorithm,” IEEE Commun. Lett. 6, 455–457, (2002)
[Crossref]

IEEE J. Sel. Areas Commun. (1)

N. Wauters and P. Demeester, “Design of the optical path layer in multi-wavelength cross-connected networks,” IEEE J. Sel. Areas Commun. 14, 881–892 (1996)
[Crossref]

IEEE/ACM Trans. Netw. (2)

R. K. Pankaj and R. G. Gallager, “Wavelength requirements of all-optical networks,” IEEE/ACM Trans. Netw. 3, 269–280 (1995)
[Crossref]

R. Ramaswami and K. N. Sivarajan. “Routing and Wavelength Assignment in All-Optical Networks,” IEEE/ACM Trans. Netw. 3, 489–500 (1995)
[Crossref]

J. Lightwave Technol. (3)

J. Opt. Networking (1)

G. Shen, W. D. Grover, T. H. Cheng, and S. K. Bose, “Sparse placement of electronic switching nodes for low blocking in translucent optical networks,” J. Opt. Networking 1, 424–441, (2002)

Manag. Sci. (1)

J. Y. Yen, “Finding the K shortest loopless paths in a network,” Manag. Sci. 17, 712–716, (1971)
[Crossref]

Opt. Commun. (1)

Y. Ye, H. Zhang, T. Qin, W. Dai, F. Feng, and X. Huo “Statistic Study of Routing and Wavelength Assignment Algorithms in WDM all Optical Network,” Opt. Commun. 185, 315–320, (2000)
[Crossref]

Opt. Netw. Mag. (1)

H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-routed Optical WDM Networks,” Opt. Netw. Mag. 1, 47–60, (2000).

Other (9)

R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective (Morgan Kaufmann, 1998)

M. D. Swaminathan and K. N. Sivarajan, “Practical Routing and Wavelength Assignment Algorithms for All Optical Networks with Limited Wavelength Conversion,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp.2750–2755

X. Yang and B. Ramamuthy, “Sparse Regeneration in a Translucent WDM Optical Network,” in Proceedings of APOC2001, Proc. SPIE4585, 61–70, (2001)
[Crossref]

B. Ramamurthy, S. Yaragorla, and X. Yang, “Translucent Optical WDM Networks for the Next-Generation Backbone Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, San Antonio, TX, 2001), pp. 60–64

X. Yang and B. Ramamurthy, “Dynamic Routing in Translucent WDM Optical Networks,” in Proceeding of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New York, NY, 2002), pp. 2796–2802

M. Ali, B. Ramamurthy, and J. S. Deogun, “Routing and Wavelength Assignment (RWA) with Power Consideration in All-Optical Wavelength-Routed Networks,” In Proceeding of Global Telecommunications Conference, (Institute of Electrical and Electronics Engineering, Rio de Janeiro, Brazil, 1999), pp. 1433–1437

B. Ramamurthy, D. Datta, and H. Feng, et al. “Transparent vs. opaque vs. translucent wavelength-routed optical network,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Washington, D.C., 1999), pp. 59–61

A.A.M Saleh, “Islands of Transparency-an Emerging Reality in Multiwave Optical Networking,” in Proceedings of 11th Annual Meeting IEEE lasers and Electro-Optics Society (Institute of Electrical and Electronics Engineering, New York, NY, 1998), p36

L. Noirie, “The Road Towards All-Optical Networks,” in Proceeding of Optical Fiber Communication Conference, (Optical Society of America, Atlanta, GA, 2003), pp.615–616

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

The node model

Fig. 2.
Fig. 2.

The topology of 7-node random network

Fig. 3.
Fig. 3.

The topology of NSFNET

Fig. 4.
Fig. 4.

NECs vs. M for As, De and R order of lightpath arrangements. W=8, Ls=3000Km

Fig. 5.
Fig. 5.

NECs vs. Ls for As, De and R order of lightpath arrangements. W=8, M=4

Tables (3)

Tables Icon

Table 1. The traffic matrix for the 7-node random network and the 7-node ring network

Tables Icon

Table 2. The MNCEs obtained in the 7-node random network (W=4)

Tables Icon

Table 3. The MNCEs obtained in the 7-node ring network (W=4)

Equations (11)

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

Maximize s , d b s , d
i , j , q γ i , j , m , n q , w p m , n m , n , w
γ i , j , m , n q , w β i , j q , w i , j , m , n , q , w
i , j , q γ i , j , m , n q , w 1 m , n , w
n γ i , j , n , m q , w n γ i , j , m , n q , w = { β i , j q , w if i = m β i , j q , w if j = m i , j , q , m , w 0 otherwise
s , d , q λ i , j , q s , d q , w β i , j q , w i , j
q , i λ i , j , q s , d q , k λ j , k , q s , d = { b s , d if s = j b s , d if d = j s , d , j 0 otherwise
b s , d c s , d s , d
m , n γ i , j , m , n q , w × l m , n L s i , j , q , w
q , j β i , j q , w T i w i , w
q , j β i , j q , w R i w i , w

Metrics