Abstract

In future transparent (all-optical) WDM networks, the signal quality of transmission (QoT) will degrade due to physical layer impairments. In this paper, we propose two genetic algorithms for solving the static impairment-aware RWA (IA-RWA) problem by accounting for the impact of physical impairments in the optimization process when searching for the optimum routing path and wavelength channel. The first algorithm indirectly considers the physical impairments through the insertion of the path length and the number of common hops in the search process, using classical multiobjective optimization (MOO) strategies. The second algorithm is a single-objective genetic algorithm (GA) that uses the Q factor for the evaluation of the feasibility of the selected RWA solution. The Q factor is used in each iteration of the algorithm in a self-learning mode in order to evaluate the fitness of each solution to the RWA problem and trigger the evolution of the population. Performance results have shown that considering path length and number of common hops for indirectly handling impairments provide an efficient solution to the IA-RWA problem.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. Mukherjee, Optical Communication Networks. McGraw-Hill, 1997.
  2. S. Yan, M. Ali, J. Deogun, “Route optimization of multicast sessions in sparse light-splitting optical networks,” in IEEE Globecom, 2001, pp. 2134–2138.
  3. B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
    [Crossref]
  4. N. Banerjee, V. Mehta, S. Pandey, “A genetic algorithm approach for solving the routing and wavelength assignment problem in WDM networks,” in Proc. of Int. Conf. on Networking, 2004.
  5. L. Zong, B. Ramamurthy, “Optimization of amplifier placement in switch-based optical network,” in Proc. of IEEE ICC, 2001, vol. 1, pp. 224–228.
  6. B. Ramamurthy, D. Datta, H. Feng, J. P. Heritage, B. Mukherjee, “Impact of transmission impairments on the teletraffic performance of wavelength routed optical networks,” J. Lightwave Technol., vol. 17, no. 10, pp. 1713–1723, 1999.
    [Crossref]
  7. T. Deng, S. Subramaniam, “Adaptive QoS routing in dynamic wavelength-routed optical networks,” in Proc. of Broadnets, 2005, vol. 1, pp. 184–193.
  8. J. He, M. Brandt-Pearce, Y. Pointurier, S. Subramaniam, “QoT-aware routing in impairment-constrained optical networks,” in Proc. of Globecom, 2007, pp. 26–30.
  9. D. Monoyios, K. Vlachos, M. Aggelou, I. Tomkos, “On the use of multi-objective optimization algorithms for solving the impairment aware-RWA problem,” in Proc. of ICC, 2009.
  10. C. M. Fonseca, P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—part I: a unified formulation,” IEEE Trans. Syst. Man Cybern., vol. 28, no. 1, pp. 26–37, 1998.
    [Crossref]
  11. D. Brelaz, “New methods to color the vertices of a graph,” Commun. ACM, vol. 22, pp. 251–256, 1979.
    [Crossref]
  12. http://www.vpisystems.com/.
  13. R. Kumar, P. Rockett, “Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm,” Evol. Comput., vol. 10, no. 3, pp. 283–314, 2002.
    [Crossref] [PubMed]

2002 (1)

R. Kumar, P. Rockett, “Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm,” Evol. Comput., vol. 10, no. 3, pp. 283–314, 2002.
[Crossref] [PubMed]

1999 (1)

1998 (2)

C. M. Fonseca, P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—part I: a unified formulation,” IEEE Trans. Syst. Man Cybern., vol. 28, no. 1, pp. 26–37, 1998.
[Crossref]

B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
[Crossref]

1979 (1)

D. Brelaz, “New methods to color the vertices of a graph,” Commun. ACM, vol. 22, pp. 251–256, 1979.
[Crossref]

Aggelou, M.

D. Monoyios, K. Vlachos, M. Aggelou, I. Tomkos, “On the use of multi-objective optimization algorithms for solving the impairment aware-RWA problem,” in Proc. of ICC, 2009.

Ali, M.

S. Yan, M. Ali, J. Deogun, “Route optimization of multicast sessions in sparse light-splitting optical networks,” in IEEE Globecom, 2001, pp. 2134–2138.

Banerjee, N.

N. Banerjee, V. Mehta, S. Pandey, “A genetic algorithm approach for solving the routing and wavelength assignment problem in WDM networks,” in Proc. of Int. Conf. on Networking, 2004.

Brandt-Pearce, M.

J. He, M. Brandt-Pearce, Y. Pointurier, S. Subramaniam, “QoT-aware routing in impairment-constrained optical networks,” in Proc. of Globecom, 2007, pp. 26–30.

Brelaz, D.

D. Brelaz, “New methods to color the vertices of a graph,” Commun. ACM, vol. 22, pp. 251–256, 1979.
[Crossref]

Datta, D.

De Turck, F.

B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
[Crossref]

Demeester, P. M.

B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
[Crossref]

Deng, T.

T. Deng, S. Subramaniam, “Adaptive QoS routing in dynamic wavelength-routed optical networks,” in Proc. of Broadnets, 2005, vol. 1, pp. 184–193.

Deogun, J.

S. Yan, M. Ali, J. Deogun, “Route optimization of multicast sessions in sparse light-splitting optical networks,” in IEEE Globecom, 2001, pp. 2134–2138.

Feng, H.

Fleming, P. J.

C. M. Fonseca, P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—part I: a unified formulation,” IEEE Trans. Syst. Man Cybern., vol. 28, no. 1, pp. 26–37, 1998.
[Crossref]

Fonseca, C. M.

C. M. Fonseca, P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—part I: a unified formulation,” IEEE Trans. Syst. Man Cybern., vol. 28, no. 1, pp. 26–37, 1998.
[Crossref]

He, J.

J. He, M. Brandt-Pearce, Y. Pointurier, S. Subramaniam, “QoT-aware routing in impairment-constrained optical networks,” in Proc. of Globecom, 2007, pp. 26–30.

Heritage, J. P.

Kumar, R.

R. Kumar, P. Rockett, “Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm,” Evol. Comput., vol. 10, no. 3, pp. 283–314, 2002.
[Crossref] [PubMed]

Mehta, V.

N. Banerjee, V. Mehta, S. Pandey, “A genetic algorithm approach for solving the routing and wavelength assignment problem in WDM networks,” in Proc. of Int. Conf. on Networking, 2004.

Monoyios, D.

D. Monoyios, K. Vlachos, M. Aggelou, I. Tomkos, “On the use of multi-objective optimization algorithms for solving the impairment aware-RWA problem,” in Proc. of ICC, 2009.

Mukherjee, B.

Pandey, S.

N. Banerjee, V. Mehta, S. Pandey, “A genetic algorithm approach for solving the routing and wavelength assignment problem in WDM networks,” in Proc. of Int. Conf. on Networking, 2004.

Pointurier, Y.

J. He, M. Brandt-Pearce, Y. Pointurier, S. Subramaniam, “QoT-aware routing in impairment-constrained optical networks,” in Proc. of Globecom, 2007, pp. 26–30.

Ramamurthy, B.

Rockett, P.

R. Kumar, P. Rockett, “Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm,” Evol. Comput., vol. 10, no. 3, pp. 283–314, 2002.
[Crossref] [PubMed]

Subramaniam, S.

T. Deng, S. Subramaniam, “Adaptive QoS routing in dynamic wavelength-routed optical networks,” in Proc. of Broadnets, 2005, vol. 1, pp. 184–193.

J. He, M. Brandt-Pearce, Y. Pointurier, S. Subramaniam, “QoT-aware routing in impairment-constrained optical networks,” in Proc. of Globecom, 2007, pp. 26–30.

Tomkos, I.

D. Monoyios, K. Vlachos, M. Aggelou, I. Tomkos, “On the use of multi-objective optimization algorithms for solving the impairment aware-RWA problem,” in Proc. of ICC, 2009.

Van Caenegem, B.

B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
[Crossref]

Van Parys, W.

B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
[Crossref]

Vlachos, K.

D. Monoyios, K. Vlachos, M. Aggelou, I. Tomkos, “On the use of multi-objective optimization algorithms for solving the impairment aware-RWA problem,” in Proc. of ICC, 2009.

Yan, S.

S. Yan, M. Ali, J. Deogun, “Route optimization of multicast sessions in sparse light-splitting optical networks,” in IEEE Globecom, 2001, pp. 2134–2138.

Zong, L.

L. Zong, B. Ramamurthy, “Optimization of amplifier placement in switch-based optical network,” in Proc. of IEEE ICC, 2001, vol. 1, pp. 224–228.

Commun. ACM (1)

D. Brelaz, “New methods to color the vertices of a graph,” Commun. ACM, vol. 22, pp. 251–256, 1979.
[Crossref]

Evol. Comput. (1)

R. Kumar, P. Rockett, “Improved sampling of the Pareto-front in multiobjective genetic optimizations by steady-state evolution: a Pareto converging genetic algorithm,” Evol. Comput., vol. 10, no. 3, pp. 283–314, 2002.
[Crossref] [PubMed]

IEEE J. Sel. Areas Commun. (1)

B. Van Caenegem, W. Van Parys, F. De Turck, P. M. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
[Crossref]

IEEE Trans. Syst. Man Cybern. (1)

C. M. Fonseca, P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—part I: a unified formulation,” IEEE Trans. Syst. Man Cybern., vol. 28, no. 1, pp. 26–37, 1998.
[Crossref]

J. Lightwave Technol. (1)

Other (8)

T. Deng, S. Subramaniam, “Adaptive QoS routing in dynamic wavelength-routed optical networks,” in Proc. of Broadnets, 2005, vol. 1, pp. 184–193.

J. He, M. Brandt-Pearce, Y. Pointurier, S. Subramaniam, “QoT-aware routing in impairment-constrained optical networks,” in Proc. of Globecom, 2007, pp. 26–30.

D. Monoyios, K. Vlachos, M. Aggelou, I. Tomkos, “On the use of multi-objective optimization algorithms for solving the impairment aware-RWA problem,” in Proc. of ICC, 2009.

N. Banerjee, V. Mehta, S. Pandey, “A genetic algorithm approach for solving the routing and wavelength assignment problem in WDM networks,” in Proc. of Int. Conf. on Networking, 2004.

L. Zong, B. Ramamurthy, “Optimization of amplifier placement in switch-based optical network,” in Proc. of IEEE ICC, 2001, vol. 1, pp. 224–228.

B. Mukherjee, Optical Communication Networks. McGraw-Hill, 1997.

S. Yan, M. Ali, J. Deogun, “Route optimization of multicast sessions in sparse light-splitting optical networks,” in IEEE Globecom, 2001, pp. 2134–2138.

http://www.vpisystems.com/.

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

Fig. 1
Fig. 1

Pseudocode of the Q-learning GA algorithm.

Fig. 2
Fig. 2

DTAG/T-Systems National Core Network.

Fig. 3
Fig. 3

Blocking probability versus load (number of active source–destination pairs). The tags next to the points indicate the number of wavelengths required.

Fig. 4
Fig. 4

Intrapopulation ranking histogram displaying the ratio of a certain rank of genes between two successive generations.

Fig. 5
Fig. 5

Interrank histogram of two merged optimal solutions on several experiments with different parameters.

Fig. 6
Fig. 6

(a) Population evolution towards convergence against the number of hops and the path length for the MOGA1 algorithm for the DTnet and 60 lightpath requests. (b) The converged optimal Pareto front.

Fig. 7
Fig. 7

Blocking ratio, number of wavelengths, and execution time versus connection requests for the MOGA and the Q-learning schemes.

Tables (1)

Tables Icon

Table 1 Simulation Parameters

Equations (4)

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

c s d = l p F l , p P s d and p Ch .
h s d = n p F n , p P s d and p Ch .
F ( Ch ) = { f 1 ( Ch ) , f 2 ( Ch ) , f 3 ( Ch ) } ,
F ( Ch ) = B Eval ( WA ( Ch ) ) + W ,