Abstract

We develop a genetic algorithm for the topological design of survivable optical transport networks with minimum capital expenditure. Using the developed genetic algorithm we can obtain near-optimal topologies in a short time. The quality of the obtained solutions is assessed using an integer linear programming model. Two initial population generators, two selection methods, two crossover operators, and two population sizes are analyzed. Computational results obtained using real telecommunications networks show that by using an initial population that resembles real optical transport networks a good convergence is achieved.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. S. K. Korotky, “Network global expectation model: a statistical formalism for quickly quantifying network needs and costs,” J. Lightwave Technol., vol. 22, no. 3, pp. 703–722, 2004.
    [CrossRef]
  2. H. Kerivin, A. R. Mahjoub, “Design of survivable networks: a survey,” Networks, vol. 46, no. 1, pp. 1–21, 2005.
    [CrossRef]
  3. O. Klopfenstein, “Access network dimensioning with uncertain traffic forecasts,” in Proc. 13th Int. Telecommunications Network Strategy and Planning Symp., 2009, pp. 1–52.
  4. D. Jungnickel, Graphs, Networks and Algorithms. Springer, 2008.
    [CrossRef]
  5. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  6. S. Soni, R. Gupta, H. Pirkul, “Survivable network design: the state of the art,” Inf. Syst. Front., vol. 1, no. 3, pp. 303–315, 1999.
    [CrossRef]
  7. B. Caenegem, W. Parys, F. De Tuck, P. Demeester, “Dimensioning of survivable WDM networks,” IEEE J. Sel. Areas Commun., vol. 16, no. 7, pp. 1146–1157, 1998.
    [CrossRef]
  8. S. Soni, H. Pirkul, “Design of survivable networks with connectivity requirements,” Telecommun. Syst., vol. 20, no. 1, pp. 133–149, 2002.
    [CrossRef]
  9. A. Balakrishnan, T. L. Magnanti, P. Mirchandani, “Connectivity-splitting models for survivable network design,” Networks, vol. 43, no. 1, pp. 10–27, 2004.
    [CrossRef]
  10. A. Balakrishnan, P. Mirchandani, H. P. Natarajan, “Connectivity upgrade models for survivable network design,” Oper. Res., vol. 57, no. 1, pp. 170–186, 2009.
    [CrossRef]
  11. C. Pluntke, M. Menth, M. Duelli, “CAPEX-aware design of survivable DWDM mesh networks,” in Proc. IEEE Int. Conf. on Communications (ICC), 2009.
  12. M. Duelli, C. Pluntke, M. Menth, “Minimizing installation costs of survivable DWDM-mesh networks: a heuristic approach,” in Proc. Next Generation Internet Networks (NGI 2008), 2008, pp. 15–22.
  13. A. Jarray, B. Jaumard, A. C. Houle, “Minimum CAPEX/OPEX design of optical backbone networks,” in Proc. Int. Conf. on Ultra Modern Telecommunications & Workshops (ICUMT ’09), 2009, pp. 1–8.
  14. I. de Miguel, R. Vallejos, A. Beghelli, R. J. Durán, “Genetic algorithm for joint routing and dimensioning of dynamic WDM networks,” J. Opt. Commun. Netw., vol. 1, no. 7, pp. 608–621, 2010.
    [CrossRef]
  15. L. S. Buriol, M. G. C. Resende, M. Thorup, “Survivable IP network design with OSPF routing,” Networks, vol. 49, pp. 51–64, 2007.
    [CrossRef]
  16. D. A. R. Chaves, C. J. A. Bastos-Filho, J. F. Martins-Filho, “Multiobjective physical topology design of all-optical networks considering QoS and Capex,” in Optical Fiber Communication Conf., 2010, paper JThA45.
  17. J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
    [CrossRef]
  18. E. Bouillet, G. Ellinas, J. F. Labourdette, R. Ramamurthy, Path Routing in Mesh Optical Networks. Wiley, 2007.
    [CrossRef]
  19. S. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol. 21, no. 4, pp. 870–883, 2003.
    [CrossRef]
  20. S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
    [CrossRef]
  21. R. Batchellor, O. Gerstel, “Cost effective architectures for core transport networks,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf., 2006, paper PDP42.
  22. R. Ramaswami, K. N. Sivarajan, Optical Networks: A Practical Perspective. Morgan Kaufmann, 2002.
  23. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.
  24. C. Pavan, R. M. Morais, F. Rocha, A. N. Pinto, “Generating realistic optical transport network topologies,” J. Opt. Commun. Netw., vol. 2, no. 1, pp. 80–90, 2010.
    [CrossRef]
  25. B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617–1622, Dec. 1988.
    [CrossRef]
  26. M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1996.
  27. R. Huelsermann, M. Gunkel, C. Meusberger, D. A. Schupke, “Cost modeling and evaluation of capital expenditures in optical multilayer networks,” J. Opt. Netw., vol. 7, no. 9, pp. 814–833, 2008.
    [CrossRef]

2010 (2)

2009 (1)

A. Balakrishnan, P. Mirchandani, H. P. Natarajan, “Connectivity upgrade models for survivable network design,” Oper. Res., vol. 57, no. 1, pp. 170–186, 2009.
[CrossRef]

2008 (2)

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

R. Huelsermann, M. Gunkel, C. Meusberger, D. A. Schupke, “Cost modeling and evaluation of capital expenditures in optical multilayer networks,” J. Opt. Netw., vol. 7, no. 9, pp. 814–833, 2008.
[CrossRef]

2007 (1)

L. S. Buriol, M. G. C. Resende, M. Thorup, “Survivable IP network design with OSPF routing,” Networks, vol. 49, pp. 51–64, 2007.
[CrossRef]

2005 (2)

J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
[CrossRef]

H. Kerivin, A. R. Mahjoub, “Design of survivable networks: a survey,” Networks, vol. 46, no. 1, pp. 1–21, 2005.
[CrossRef]

2004 (2)

S. K. Korotky, “Network global expectation model: a statistical formalism for quickly quantifying network needs and costs,” J. Lightwave Technol., vol. 22, no. 3, pp. 703–722, 2004.
[CrossRef]

A. Balakrishnan, T. L. Magnanti, P. Mirchandani, “Connectivity-splitting models for survivable network design,” Networks, vol. 43, no. 1, pp. 10–27, 2004.
[CrossRef]

2003 (1)

2002 (1)

S. Soni, H. Pirkul, “Design of survivable networks with connectivity requirements,” Telecommun. Syst., vol. 20, no. 1, pp. 133–149, 2002.
[CrossRef]

1999 (1)

S. Soni, R. Gupta, H. Pirkul, “Survivable network design: the state of the art,” Inf. Syst. Front., vol. 1, no. 3, pp. 303–315, 1999.
[CrossRef]

1998 (1)

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

1988 (1)

B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617–1622, Dec. 1988.
[CrossRef]

Akyama, A. A.

J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
[CrossRef]

Azodomilky, S.

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

Balakrishnan, A.

A. Balakrishnan, P. Mirchandani, H. P. Natarajan, “Connectivity upgrade models for survivable network design,” Oper. Res., vol. 57, no. 1, pp. 170–186, 2009.
[CrossRef]

A. Balakrishnan, T. L. Magnanti, P. Mirchandani, “Connectivity-splitting models for survivable network design,” Networks, vol. 43, no. 1, pp. 10–27, 2004.
[CrossRef]

Bastos-Filho, C. J. A.

D. A. R. Chaves, C. J. A. Bastos-Filho, J. F. Martins-Filho, “Multiobjective physical topology design of all-optical networks considering QoS and Capex,” in Optical Fiber Communication Conf., 2010, paper JThA45.

Batchellor, R.

R. Batchellor, O. Gerstel, “Cost effective architectures for core transport networks,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf., 2006, paper PDP42.

Beghelli, A.

Bouillet, E.

J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
[CrossRef]

E. Bouillet, G. Ellinas, J. F. Labourdette, R. Ramamurthy, Path Routing in Mesh Optical Networks. Wiley, 2007.
[CrossRef]

Buriol, L. S.

L. S. Buriol, M. G. C. Resende, M. Thorup, “Survivable IP network design with OSPF routing,” Networks, vol. 49, pp. 51–64, 2007.
[CrossRef]

Caenegem, B.

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

Careglio, D.

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

Chaves, D. A. R.

D. A. R. Chaves, C. J. A. Bastos-Filho, J. F. Martins-Filho, “Multiobjective physical topology design of all-optical networks considering QoS and Capex,” in Optical Fiber Communication Conf., 2010, paper JThA45.

de Miguel, I.

De Tuck, F.

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

Demeester, P.

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

Duelli, M.

C. Pluntke, M. Menth, M. Duelli, “CAPEX-aware design of survivable DWDM mesh networks,” in Proc. IEEE Int. Conf. on Communications (ICC), 2009.

M. Duelli, C. Pluntke, M. Menth, “Minimizing installation costs of survivable DWDM-mesh networks: a heuristic approach,” in Proc. Next Generation Internet Networks (NGI 2008), 2008, pp. 15–22.

Durán, R. J.

Ellinas, G.

E. Bouillet, G. Ellinas, J. F. Labourdette, R. Ramamurthy, Path Routing in Mesh Optical Networks. Wiley, 2007.
[CrossRef]

Garey, M. R.

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

Gerstel, O.

R. Batchellor, O. Gerstel, “Cost effective architectures for core transport networks,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf., 2006, paper PDP42.

Goldberg, D. E.

D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

Gunkel, M.

Gupta, R.

S. Soni, R. Gupta, H. Pirkul, “Survivable network design: the state of the art,” Inf. Syst. Front., vol. 1, no. 3, pp. 303–315, 1999.
[CrossRef]

Houle, A. C.

A. Jarray, B. Jaumard, A. C. Houle, “Minimum CAPEX/OPEX design of optical backbone networks,” in Proc. Int. Conf. on Ultra Modern Telecommunications & Workshops (ICUMT ’09), 2009, pp. 1–8.

Huelsermann, R.

Jarray, A.

A. Jarray, B. Jaumard, A. C. Houle, “Minimum CAPEX/OPEX design of optical backbone networks,” in Proc. Int. Conf. on Ultra Modern Telecommunications & Workshops (ICUMT ’09), 2009, pp. 1–8.

Jaumard, B.

A. Jarray, B. Jaumard, A. C. Houle, “Minimum CAPEX/OPEX design of optical backbone networks,” in Proc. Int. Conf. on Ultra Modern Telecommunications & Workshops (ICUMT ’09), 2009, pp. 1–8.

Johnson, D. S.

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

Jungnickel, D.

D. Jungnickel, Graphs, Networks and Algorithms. Springer, 2008.
[CrossRef]

Kerivin, H.

H. Kerivin, A. R. Mahjoub, “Design of survivable networks: a survey,” Networks, vol. 46, no. 1, pp. 1–21, 2005.
[CrossRef]

Klinkowski, M.

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

Klopfenstein, O.

O. Klopfenstein, “Access network dimensioning with uncertain traffic forecasts,” in Proc. 13th Int. Telecommunications Network Strategy and Planning Symp., 2009, pp. 1–52.

Korotky, S. K.

Labourdette, J. F.

J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
[CrossRef]

E. Bouillet, G. Ellinas, J. F. Labourdette, R. Ramamurthy, Path Routing in Mesh Optical Networks. Wiley, 2007.
[CrossRef]

Magnanti, T. L.

A. Balakrishnan, T. L. Magnanti, P. Mirchandani, “Connectivity-splitting models for survivable network design,” Networks, vol. 43, no. 1, pp. 10–27, 2004.
[CrossRef]

Mahjoub, A. R.

H. Kerivin, A. R. Mahjoub, “Design of survivable networks: a survey,” Networks, vol. 46, no. 1, pp. 1–21, 2005.
[CrossRef]

Marin, E.

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

Martins-Filho, J. F.

D. A. R. Chaves, C. J. A. Bastos-Filho, J. F. Martins-Filho, “Multiobjective physical topology design of all-optical networks considering QoS and Capex,” in Optical Fiber Communication Conf., 2010, paper JThA45.

Menth, M.

C. Pluntke, M. Menth, M. Duelli, “CAPEX-aware design of survivable DWDM mesh networks,” in Proc. IEEE Int. Conf. on Communications (ICC), 2009.

M. Duelli, C. Pluntke, M. Menth, “Minimizing installation costs of survivable DWDM-mesh networks: a heuristic approach,” in Proc. Next Generation Internet Networks (NGI 2008), 2008, pp. 15–22.

Meusberger, C.

Mirchandani, P.

A. Balakrishnan, P. Mirchandani, H. P. Natarajan, “Connectivity upgrade models for survivable network design,” Oper. Res., vol. 57, no. 1, pp. 170–186, 2009.
[CrossRef]

A. Balakrishnan, T. L. Magnanti, P. Mirchandani, “Connectivity-splitting models for survivable network design,” Networks, vol. 43, no. 1, pp. 10–27, 2004.
[CrossRef]

Mitchell, M.

M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1996.

Morais, R. M.

Mukherjee, B.

Natarajan, H. P.

A. Balakrishnan, P. Mirchandani, H. P. Natarajan, “Connectivity upgrade models for survivable network design,” Oper. Res., vol. 57, no. 1, pp. 170–186, 2009.
[CrossRef]

Pareta, J. S.

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

Parys, W.

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

Pavan, C.

Pinto, A. N.

Pirkul, H.

S. Soni, H. Pirkul, “Design of survivable networks with connectivity requirements,” Telecommun. Syst., vol. 20, no. 1, pp. 133–149, 2002.
[CrossRef]

S. Soni, R. Gupta, H. Pirkul, “Survivable network design: the state of the art,” Inf. Syst. Front., vol. 1, no. 3, pp. 303–315, 1999.
[CrossRef]

Pluntke, C.

C. Pluntke, M. Menth, M. Duelli, “CAPEX-aware design of survivable DWDM mesh networks,” in Proc. IEEE Int. Conf. on Communications (ICC), 2009.

M. Duelli, C. Pluntke, M. Menth, “Minimizing installation costs of survivable DWDM-mesh networks: a heuristic approach,” in Proc. Next Generation Internet Networks (NGI 2008), 2008, pp. 15–22.

Ramamurthy, R.

J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
[CrossRef]

E. Bouillet, G. Ellinas, J. F. Labourdette, R. Ramamurthy, Path Routing in Mesh Optical Networks. Wiley, 2007.
[CrossRef]

Ramamurthy, S.

Ramaswami, R.

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

Resende, M. G. C.

L. S. Buriol, M. G. C. Resende, M. Thorup, “Survivable IP network design with OSPF routing,” Networks, vol. 49, pp. 51–64, 2007.
[CrossRef]

Rocha, F.

Sahasrabuddhe, L.

Schupke, D. A.

Sivarajan, K. N.

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

Soni, S.

S. Soni, H. Pirkul, “Design of survivable networks with connectivity requirements,” Telecommun. Syst., vol. 20, no. 1, pp. 133–149, 2002.
[CrossRef]

S. Soni, R. Gupta, H. Pirkul, “Survivable network design: the state of the art,” Inf. Syst. Front., vol. 1, no. 3, pp. 303–315, 1999.
[CrossRef]

Thorup, M.

L. S. Buriol, M. G. C. Resende, M. Thorup, “Survivable IP network design with OSPF routing,” Networks, vol. 49, pp. 51–64, 2007.
[CrossRef]

Tomkos, I.

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

Vallejos, R.

Waxman, B.

B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617–1622, Dec. 1988.
[CrossRef]

Comput. Netw. (1)

S. Azodomilky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw., vol. 53, no. 7, pp. 926–944, 2008.
[CrossRef]

IEEE J. Sel. Areas Commun. (2)

B. Waxman, “Routing of multipoint connections,” IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617–1622, Dec. 1988.
[CrossRef]

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

IEEE/ACM Trans. Netw. (1)

J. F. Labourdette, E. Bouillet, R. Ramamurthy, A. A. Akyama, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 906–917, 2005.
[CrossRef]

Inf. Syst. Front. (1)

S. Soni, R. Gupta, H. Pirkul, “Survivable network design: the state of the art,” Inf. Syst. Front., vol. 1, no. 3, pp. 303–315, 1999.
[CrossRef]

J. Lightwave Technol. (2)

J. Opt. Commun. Netw. (2)

J. Opt. Netw. (1)

Networks (3)

L. S. Buriol, M. G. C. Resende, M. Thorup, “Survivable IP network design with OSPF routing,” Networks, vol. 49, pp. 51–64, 2007.
[CrossRef]

H. Kerivin, A. R. Mahjoub, “Design of survivable networks: a survey,” Networks, vol. 46, no. 1, pp. 1–21, 2005.
[CrossRef]

A. Balakrishnan, T. L. Magnanti, P. Mirchandani, “Connectivity-splitting models for survivable network design,” Networks, vol. 43, no. 1, pp. 10–27, 2004.
[CrossRef]

Oper. Res. (1)

A. Balakrishnan, P. Mirchandani, H. P. Natarajan, “Connectivity upgrade models for survivable network design,” Oper. Res., vol. 57, no. 1, pp. 170–186, 2009.
[CrossRef]

Telecommun. Syst. (1)

S. Soni, H. Pirkul, “Design of survivable networks with connectivity requirements,” Telecommun. Syst., vol. 20, no. 1, pp. 133–149, 2002.
[CrossRef]

Other (12)

D. A. R. Chaves, C. J. A. Bastos-Filho, J. F. Martins-Filho, “Multiobjective physical topology design of all-optical networks considering QoS and Capex,” in Optical Fiber Communication Conf., 2010, paper JThA45.

E. Bouillet, G. Ellinas, J. F. Labourdette, R. Ramamurthy, Path Routing in Mesh Optical Networks. Wiley, 2007.
[CrossRef]

C. Pluntke, M. Menth, M. Duelli, “CAPEX-aware design of survivable DWDM mesh networks,” in Proc. IEEE Int. Conf. on Communications (ICC), 2009.

M. Duelli, C. Pluntke, M. Menth, “Minimizing installation costs of survivable DWDM-mesh networks: a heuristic approach,” in Proc. Next Generation Internet Networks (NGI 2008), 2008, pp. 15–22.

A. Jarray, B. Jaumard, A. C. Houle, “Minimum CAPEX/OPEX design of optical backbone networks,” in Proc. Int. Conf. on Ultra Modern Telecommunications & Workshops (ICUMT ’09), 2009, pp. 1–8.

O. Klopfenstein, “Access network dimensioning with uncertain traffic forecasts,” in Proc. 13th Int. Telecommunications Network Strategy and Planning Symp., 2009, pp. 1–52.

D. Jungnickel, Graphs, Networks and Algorithms. Springer, 2008.
[CrossRef]

M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1996.

R. Batchellor, O. Gerstel, “Cost effective architectures for core transport networks,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf., 2006, paper PDP42.

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

D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

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

Fig. 1
Fig. 1

Node architecture: bidirectional electrical tributary ports, bidirectional short-reach optical ports, electrical cross connect (EXC), and optical cross connect (OXC).

Fig. 2
Fig. 2

Transmission system architecture: transponders, WDM terminal, optical line amplifiers, and optical fiber.

Fig. 3
Fig. 3

Network topology with seven nodes.

Fig. 4
Fig. 4

Evolution of the gap for the best solution obtained for the nine reference networks in each iteration for initial populations generated with the (a) random topology generator [17] and (b) topology generator presented in [24].

Fig. 5
Fig. 5

Evolution of the best solution obtained in each iteration using the topology generator presented in [24] for the eight considered combinations and lower bound obtained using the ILP model (solid black line) for (a) the vBNS network (12 nodes) and (b) the SPAIN network (17 nodes).

Fig. 6
Fig. 6

Topologies obtained using the ILP model and the genetic algorithm for the node location of (a) the GERMANY network with the uniform demand matrix and (b) the RNP network with the nonuniform demand matrix. The dashed links differ in both solutions and the solid links are common.

Tables (6)

Tables Icon

Table 1 Example of the Single-Point Crossover

Tables Icon

Table 2 Example of the Uniform Crossover

Tables Icon

Table 3 Costs With the Transmission System [27]

Tables Icon

Table 4 Real-World Reference Networks [24]

Tables Icon

Table 5 Gap of the Best Solution Obtained With Each of the Eight Considered Combinations for Initial Populations Generated Using [24]

Tables Icon

Table 6 Computational Results Obtained Using the ILP Model and the Genetic Algorithm for Uniform and Nonuniform Demand Matrices

Equations (15)

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

F i j = ( c term + C i j span 1 c oa + C i j c f + M i j ) X i j ,
L i j = ( o , d ) D B o d Z i j o d ,
X i j = L i j K i j ,
O i j = c t L i j .
T c = { i , j } E ( F i j + O i j ) ,
P ( i , j ) = β exp C i j α L ,
[ g ] = [ 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 ] ,
1 1 0 0 0 0 | 1 0 0 1 0 | 1 1 0 1 | 0 0 1 | 1 1 | 0 .
minimize T c = { i , j } E ( F i j + O i j )
subject to
j V \ { o } Y i j o d j V \ { d } Y j i o d = { 2 , i = o 0 , i o , d 2 , i = d } ( o , d ) D , i V ,
( o , d ) D B o d ( Y i j o d + Y j i o d ) K i j X i j { i , j } E ,
X i j N 0 { i , j } E ,
Y i j o d , Y j i o d { 0 , 1 } ( o , d ) D { i , j } E .
gap = 100 ( b u b l ) b u ,