Abstract

One of the most important issues in optical network design is ensuring its resilience. In this paper, we propose using nature-inspired heuristics to find a resilient mapping of a given virtual topology with minimum resource usage. Evolutionary algorithms and ant colony optimization algorithms are applied to the problem after a set of parameter tuning tests. To assess the performance of the proposed algorithms, we compare the experimental results with those obtained through integer linear programming. The results show that both of our algorithms can solve the problem even for large-scale network topologies for which a feasible solution cannot be found using integer linear programming. Moreover, the CPU time and the memory used by the nature-inspired heuristics is much lower. The solution quality and the CPU time usage results prove that both of our nature-inspired heuristics can easily be applied to real-world applications.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. Mukherjee, Optical WDM Networks. New York: Springer, 2006.
  2. E. Modiano, A. Narula-Tam, “Survivable lightpath routing: a new approach to the design of WDM-based networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 800–809, 2002.
    [CrossRef]
  3. J. Armitage, O. Crochat, J. Y. Le Boudec, “Design of a survivable WDM photonic network,” in Proc. IEEE INFOCOM, 1997, pp. 244–252.
  4. A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.
  5. F. Ducatelle, L. M. Gambardella, “A scalable algorithm for survivable routing in IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 54–63.
  6. M. Kurant, P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 44–53.
  7. N. Banerjee, S. Sharan, “An evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks,” in Proc. of ICISIP, 2004, pp. 13–18.
  8. M. Saha, I. Sengupta, “A genetic algorithm based approach for static virtual topology design in optical networks,” in Proc. of INDICON, 2005, pp. 392–395.
  9. F. C. Ergin, A. Yayımlı, Ş. Uyar, “An evolutionary algorithm for survivable virtual topology mapping in optical WDM networks,” in EvoWorkshops09, LNCS 5484, 2009, pp. 31–40.
  10. G. N. Varela, M. C. Sinclair, “Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation,” in Congr. on Evolutionary Computation, 1999, vol. 3, pp. 1809–1816.
  11. R. M. Garlick, R. S. Barr, “Dynamic wavelength routing in WDM networks via ant colony optimization,” in 3rd Int. Workshop on Ant Algorithms, LNCS 2463, 2002, vol. 3, pp. 250–255.
  12. S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, pp. 39–48, 2006.
    [CrossRef]
  13. S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
    [CrossRef]
  14. A. Hassan, C. Phillips, J. Pitts, “Dynamic routing and wavelength assignment using hybrid particle swarm optimization,” in EPSRC PGNet, 2007.
  15. E. Kaldırım, F. C. Ergin, Ş. Uyar, A. Yayımlı, “Ant colony optimization for survivable virtual topology mapping in optical WDM networks,” in Proc. of ISCIS, 2009, pp. 334–339.
  16. A. Todimala, B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 63–69, 2007.
    [CrossRef]
  17. H. H. Hoos, T. Stutzle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2005.
  18. A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing. Springer Verlag, 2003.
    [CrossRef]
  19. M. Dorigo, T. Stutzle, Ant Colony Optimization. Cambridge, MA: Massachusetts Institute of Technology, 2004.
    [CrossRef]
  20. M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., vol. 26, pp. 29–41, 1996.
    [CrossRef]
  21. M. Dorigo, T. Stutzle, “The ant colony optimization metaheuristics: algorithms, applications, and advances,” in Handbook of Metaheuristics (International Series in Operations Research and Management Science 57), 2002, pp. 251–285.
  22. T. Stutzle, Ant Colony Optimization Source Code, 2004. Available: http://www.aco-metaheuristic.org/aco-code.
  23. ILOG CPLEX 6.5 User’s Manual, 2000.

2007

A. Todimala, B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 63–69, 2007.
[CrossRef]

2006

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, pp. 39–48, 2006.
[CrossRef]

S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
[CrossRef]

2002

E. Modiano, A. Narula-Tam, “Survivable lightpath routing: a new approach to the design of WDM-based networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 800–809, 2002.
[CrossRef]

1996

M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., vol. 26, pp. 29–41, 1996.
[CrossRef]

Armitage, J.

J. Armitage, O. Crochat, J. Y. Le Boudec, “Design of a survivable WDM photonic network,” in Proc. IEEE INFOCOM, 1997, pp. 244–252.

Banerjee, N.

N. Banerjee, S. Sharan, “An evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks,” in Proc. of ICISIP, 2004, pp. 13–18.

Barr, R. S.

R. M. Garlick, R. S. Barr, “Dynamic wavelength routing in WDM networks via ant colony optimization,” in 3rd Int. Workshop on Ant Algorithms, LNCS 2463, 2002, vol. 3, pp. 250–255.

Colorni, A.

M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., vol. 26, pp. 29–41, 1996.
[CrossRef]

Crainic, T.

A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.

Crochat, O.

J. Armitage, O. Crochat, J. Y. Le Boudec, “Design of a survivable WDM photonic network,” in Proc. IEEE INFOCOM, 1997, pp. 244–252.

Dorigo, M.

M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., vol. 26, pp. 29–41, 1996.
[CrossRef]

M. Dorigo, T. Stutzle, Ant Colony Optimization. Cambridge, MA: Massachusetts Institute of Technology, 2004.
[CrossRef]

M. Dorigo, T. Stutzle, “The ant colony optimization metaheuristics: algorithms, applications, and advances,” in Handbook of Metaheuristics (International Series in Operations Research and Management Science 57), 2002, pp. 251–285.

Ducatelle, F.

F. Ducatelle, L. M. Gambardella, “A scalable algorithm for survivable routing in IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 54–63.

Eiben, A. E.

A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing. Springer Verlag, 2003.
[CrossRef]

Ergin, F. C.

F. C. Ergin, A. Yayımlı, Ş. Uyar, “An evolutionary algorithm for survivable virtual topology mapping in optical WDM networks,” in EvoWorkshops09, LNCS 5484, 2009, pp. 31–40.

E. Kaldırım, F. C. Ergin, Ş. Uyar, A. Yayımlı, “Ant colony optimization for survivable virtual topology mapping in optical WDM networks,” in Proc. of ISCIS, 2009, pp. 334–339.

Gambardella, L. M.

F. Ducatelle, L. M. Gambardella, “A scalable algorithm for survivable routing in IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 54–63.

Garlick, R. M.

R. M. Garlick, R. S. Barr, “Dynamic wavelength routing in WDM networks via ant colony optimization,” in 3rd Int. Workshop on Ant Algorithms, LNCS 2463, 2002, vol. 3, pp. 250–255.

Hassan, A.

A. Hassan, C. Phillips, J. Pitts, “Dynamic routing and wavelength assignment using hybrid particle swarm optimization,” in EPSRC PGNet, 2007.

Hoos, H. H.

H. H. Hoos, T. Stutzle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2005.

Horiguchi, S.

S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
[CrossRef]

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, pp. 39–48, 2006.
[CrossRef]

Jiang, X.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, pp. 39–48, 2006.
[CrossRef]

S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
[CrossRef]

Kaldirim, E.

E. Kaldırım, F. C. Ergin, Ş. Uyar, A. Yayımlı, “Ant colony optimization for survivable virtual topology mapping in optical WDM networks,” in Proc. of ISCIS, 2009, pp. 334–339.

Kurant, M.

M. Kurant, P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 44–53.

Le, V.

S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
[CrossRef]

Le Boudec, J. Y.

J. Armitage, O. Crochat, J. Y. Le Boudec, “Design of a survivable WDM photonic network,” in Proc. IEEE INFOCOM, 1997, pp. 244–252.

Leonardi, E.

A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.

Maniezzo, V.

M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., vol. 26, pp. 29–41, 1996.
[CrossRef]

Marsan, M. A.

A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.

Modiano, E.

E. Modiano, A. Narula-Tam, “Survivable lightpath routing: a new approach to the design of WDM-based networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 800–809, 2002.
[CrossRef]

Mukherjee, B.

B. Mukherjee, Optical WDM Networks. New York: Springer, 2006.

Narula-Tam, A.

E. Modiano, A. Narula-Tam, “Survivable lightpath routing: a new approach to the design of WDM-based networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 800–809, 2002.
[CrossRef]

Ngo, S. H.

S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
[CrossRef]

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, pp. 39–48, 2006.
[CrossRef]

Nucci, A.

A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.

Phillips, C.

A. Hassan, C. Phillips, J. Pitts, “Dynamic routing and wavelength assignment using hybrid particle swarm optimization,” in EPSRC PGNet, 2007.

Pitts, J.

A. Hassan, C. Phillips, J. Pitts, “Dynamic routing and wavelength assignment using hybrid particle swarm optimization,” in EPSRC PGNet, 2007.

Ramamurthy, B.

A. Todimala, B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 63–69, 2007.
[CrossRef]

Saha, M.

M. Saha, I. Sengupta, “A genetic algorithm based approach for static virtual topology design in optical networks,” in Proc. of INDICON, 2005, pp. 392–395.

Sanso, B.

A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.

Sengupta, I.

M. Saha, I. Sengupta, “A genetic algorithm based approach for static virtual topology design in optical networks,” in Proc. of INDICON, 2005, pp. 392–395.

Sharan, S.

N. Banerjee, S. Sharan, “An evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks,” in Proc. of ICISIP, 2004, pp. 13–18.

Sinclair, M. C.

G. N. Varela, M. C. Sinclair, “Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation,” in Congr. on Evolutionary Computation, 1999, vol. 3, pp. 1809–1816.

Smith, J. E.

A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing. Springer Verlag, 2003.
[CrossRef]

Stutzle, T.

T. Stutzle, Ant Colony Optimization Source Code, 2004. Available: http://www.aco-metaheuristic.org/aco-code.

M. Dorigo, T. Stutzle, “The ant colony optimization metaheuristics: algorithms, applications, and advances,” in Handbook of Metaheuristics (International Series in Operations Research and Management Science 57), 2002, pp. 251–285.

M. Dorigo, T. Stutzle, Ant Colony Optimization. Cambridge, MA: Massachusetts Institute of Technology, 2004.
[CrossRef]

H. H. Hoos, T. Stutzle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2005.

Thiran, P.

M. Kurant, P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 44–53.

Todimala, A.

A. Todimala, B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 63–69, 2007.
[CrossRef]

Uyar, S.

F. C. Ergin, A. Yayımlı, Ş. Uyar, “An evolutionary algorithm for survivable virtual topology mapping in optical WDM networks,” in EvoWorkshops09, LNCS 5484, 2009, pp. 31–40.

E. Kaldırım, F. C. Ergin, Ş. Uyar, A. Yayımlı, “Ant colony optimization for survivable virtual topology mapping in optical WDM networks,” in Proc. of ISCIS, 2009, pp. 334–339.

Varela, G. N.

G. N. Varela, M. C. Sinclair, “Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation,” in Congr. on Evolutionary Computation, 1999, vol. 3, pp. 1809–1816.

Yayimli, A.

E. Kaldırım, F. C. Ergin, Ş. Uyar, A. Yayımlı, “Ant colony optimization for survivable virtual topology mapping in optical WDM networks,” in Proc. of ISCIS, 2009, pp. 334–339.

F. C. Ergin, A. Yayımlı, Ş. Uyar, “An evolutionary algorithm for survivable virtual topology mapping in optical WDM networks,” in EvoWorkshops09, LNCS 5484, 2009, pp. 31–40.

IEEE J. Sel. Areas Commun.

E. Modiano, A. Narula-Tam, “Survivable lightpath routing: a new approach to the design of WDM-based networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 800–809, 2002.
[CrossRef]

A. Todimala, B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 63–69, 2007.
[CrossRef]

IEEE Trans. Syst., Man, Cybern., Part B: Cybern.

M. Dorigo, V. Maniezzo, A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., vol. 26, pp. 29–41, 1996.
[CrossRef]

J. Supercomput.

S. H. Ngo, X. Jiang, V. Le, S. Horiguchi, “Ant-based survivable routing in dynamic WDM networks with shared backup paths,” J. Supercomput., vol. 36, no. 3, pp. 297–307, 2006.
[CrossRef]

Photonic Network Commun.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, pp. 39–48, 2006.
[CrossRef]

Other

B. Mukherjee, Optical WDM Networks. New York: Springer, 2006.

A. Hassan, C. Phillips, J. Pitts, “Dynamic routing and wavelength assignment using hybrid particle swarm optimization,” in EPSRC PGNet, 2007.

E. Kaldırım, F. C. Ergin, Ş. Uyar, A. Yayımlı, “Ant colony optimization for survivable virtual topology mapping in optical WDM networks,” in Proc. of ISCIS, 2009, pp. 334–339.

H. H. Hoos, T. Stutzle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2005.

A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing. Springer Verlag, 2003.
[CrossRef]

M. Dorigo, T. Stutzle, Ant Colony Optimization. Cambridge, MA: Massachusetts Institute of Technology, 2004.
[CrossRef]

J. Armitage, O. Crochat, J. Y. Le Boudec, “Design of a survivable WDM photonic network,” in Proc. IEEE INFOCOM, 1997, pp. 244–252.

A. Nucci, B. Sanso, T. Crainic, E. Leonardi, M. A. Marsan, “Design of fault-tolerant logical topologies in wavelength-routed optical IP networks,” in Proc. of IEEE Globecom, 2001, pp. 2098–2103.

F. Ducatelle, L. M. Gambardella, “A scalable algorithm for survivable routing in IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 54–63.

M. Kurant, P. Thiran, “Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks,” in Proc. of Int. Conf. on Broadband Networks, 2004, pp. 44–53.

N. Banerjee, S. Sharan, “An evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks,” in Proc. of ICISIP, 2004, pp. 13–18.

M. Saha, I. Sengupta, “A genetic algorithm based approach for static virtual topology design in optical networks,” in Proc. of INDICON, 2005, pp. 392–395.

F. C. Ergin, A. Yayımlı, Ş. Uyar, “An evolutionary algorithm for survivable virtual topology mapping in optical WDM networks,” in EvoWorkshops09, LNCS 5484, 2009, pp. 31–40.

G. N. Varela, M. C. Sinclair, “Ant colony optimisation for virtual-wavelength-path routing and wavelength allocation,” in Congr. on Evolutionary Computation, 1999, vol. 3, pp. 1809–1816.

R. M. Garlick, R. S. Barr, “Dynamic wavelength routing in WDM networks via ant colony optimization,” in 3rd Int. Workshop on Ant Algorithms, LNCS 2463, 2002, vol. 3, pp. 250–255.

M. Dorigo, T. Stutzle, “The ant colony optimization metaheuristics: algorithms, applications, and advances,” in Handbook of Metaheuristics (International Series in Operations Research and Management Science 57), 2002, pp. 251–285.

T. Stutzle, Ant Colony Optimization Source Code, 2004. Available: http://www.aco-metaheuristic.org/aco-code.

ILOG CPLEX 6.5 User’s Manual, 2000.

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

Fig. 1
Fig. 1

(a) Physical topology, (b) virtual topology, (c) survivable mapping, (d) unsurvivable mapping.

Tables (8)

Tables Icon

Table 1 Four Different Shortest Paths for the Lightpaths of the Example VT Given in Fig. 1(b)

Tables Icon

Table 2 Default [18] and Tested Range of Values (RoV) for EA Parameters To Be Fine-Tuned

Tables Icon

Table 3 Default [22] and Tested Range of Values (RoV) for ACO Parameters To Be Fine-Tuned

Tables Icon

Table 4 Success Rates (SR) and Average Resource Usages (RU) for 24-node Topology and VTs Having 3 Different Connectivity Degrees (3, 4, 5), Solved With 3 Different Numbers of Shortest Paths (SPs) (5, 10, 15)

Tables Icon

Table 5 Success Rates (SR) and Average Resource Usages (RU) for 48-node Topology and VTs Having 3 Different Connectivity Degrees (3, 4, 5), Solved With 3 Different Numbers of Shortest Paths (SP) (10, 15, 20)

Tables Icon

Table 6 Percentage of Feasible Solutions for 24-node Topology and VTs of 3 Different Connectivity Degrees (3, 4, 5)

Tables Icon

Table 7 Percentage of Optimum Solutions for 24-node Topology and VTs of 3 Different Connectivity Degrees (3, 4, 5)

Tables Icon

Table 8 Running Time Averages (in s) of EA and ACO for 24-node and 48-node Physical Topologies and VTs Having 3 Different Connectivity Degrees (3, 4, 5)

Equations (2)

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

Minimize ( i , j ) ϵ E , ( s , t ) ϵ E L f i j s t .
f i = total number of wavelength links in network + penalty factor 1 × wavelength capcity violation + penalty factor 2 × ( u s i ) .