Genetic Algorithm Based Wavelength Division Multiplexing Networks Planning
This paper presents a new heuristic algorithm useful
for long-term planning of survivable WDM networks. A multi-period
model is formulated that combines network topology design and
capacity expansion. The ability to determine network expansion
schedules of this type becomes increasingly important to the
telecommunications industry and to its customers. The solution
technique consists of a Genetic Algorithm that allows generating
several network alternatives for each time period simultaneously and
shortest-path techniques to deduce from these alternatives a least-cost
network expansion plan over all time periods. The multi-period
planning approach is illustrated on a realistic network example.
Extensive simulations on a wide range of problem instances are
carried out to assess the cost savings that can be expected by
choosing a multi-period planning approach instead of an iterative
network expansion design method.
[1] K. Sato. Advances in Transport Network Technologies, Artech House,
Norwood, 1996.
[2] P. Lagasse, Photonic Technologies in Europe, Horizon - Infowin
(ACTS). Telenor AS R&D, 1998.
[3] A.Acampora, "The Scalable Lightwave Network", IEEE
Communications Magazine, Vol. 32, No. 12, pp. 36-42, 1994.
[4] P. Green, "Optical Networking Update", IEEE Journal on Selected
Areas in Communications, Vol. 14, No. 5, pp. 764-779, 1996.
[5] R. Ramaswami, K. Sivarajan, "Design of Logical Topologies for
Wavelength-Routed Optical Networks", IEEE Journal on Selected
Areas in Communications, Vol. 14, No. 5, pp. 840-851, 1996.
[6] B. Van Caenegem, W. Van Parys, F. De Turck, P. Demeester,
"Dimensioning of Survivable WDM Networks", IEEE Journal on
Selected Areas in Communications, Vol. 16, No. 7, pp. 1146-1157,
1998.
[7] S. Chang, B. Gavish, "Telecommunications Network Topological
Design and Capacity Expansion: Formulation and Algorithms",
Telecommunication Systems, Vol. 1, pp. 99-131, 1993.
[8] N. Zadeh, "On Building Minimum Cost Communication Networks over
Time", Networks, Vol. 4, pp. 19-34, 1974.
[9] N. Christofides, P. Brooker, "Optimal Expansion of an Existing
Network", Mathematical Programming, Vol. 6, pp. 197-211, 1974.
[10] P. Doulliez, R. Rao, "Optimal Network Capacity Planning: a Shortest
Path Scheme", Operations Research, Vol. 23, pp. 811-818, 1975.
[11] M. Minoux, "Network Synthesis and Dynamic Network Optimization",
Annals of Discrete Mathematics, Vol. 31, pp. 283-324, 1987.
[12] B. Garcia, P. Mahey, L. Leblanc, " Iterative Improvement Methods for a
Multi-Period Network Design Problem", European Journal of
Operations Research, Vol. 110, No.1, pp. 150-165, 1998.
[13] A. Balakrishnan, T. Magnanti, A. Shulman, R. Wong, "Models for
Planning Capacity Expansion in Local Access Telecommunication
Networks", Annals of Operations Research, Vol. 33, pp. 239-284, 1991.
[14] T. Wu, R. Cardwell, M. Boyden, "A Multi-Period Design Model for
Survivable Network Architecture Selection for SONET Interoffice
Networks", IEEE Transactions on Reliability, Vol. 40, No. 4, pp. 417-
427, 1991.
[15] S. Parrish, T. Cox, W. Kuehner, Y. Qiu, "Planning for Optimal
Expansion of Leased Line Communication Networks", Annals of
Operations Research, Vol. 36, pp. 347-364, 1992.
[16] T. Wu, "Emerging Technologies for Fiber Network Survivability",
IEEE Communications Magazine, Vol. 33, No. 2, pp. 58-74, 1995.
[17] M. Grötschel, C. Monma, M. Stoer, "Design of Survivable Networks",
In Handbooks of Operations Research and Management Science, Vol.7
(M. Ball, T. Magnanti, C. Monma, G. Nemhauser, Ed.). North-Holland,
Amsterdam, pp. 617-672, 1995.
[18] R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms
and Applications. Prentice Hall, Englewood Cliffs, New Jersey, 1993.
[19] M. Pickavet, F. Poppe, J. Luystermans, P. Demeester, "A Genetic
Algorithm for Solving the Capacitated Survivable Network Design
Problem", Fifth International Conference on Telecommunication
Systems, pp. 71-76, 1997.
[20] T. Almeida, "Optical Transport Networks - From Concepts towards an
International Field Trial", Seventh International Network Planning
Symposium Networks'96, pp. 711-716, 1996.
[1] K. Sato. Advances in Transport Network Technologies, Artech House,
Norwood, 1996.
[2] P. Lagasse, Photonic Technologies in Europe, Horizon - Infowin
(ACTS). Telenor AS R&D, 1998.
[3] A.Acampora, "The Scalable Lightwave Network", IEEE
Communications Magazine, Vol. 32, No. 12, pp. 36-42, 1994.
[4] P. Green, "Optical Networking Update", IEEE Journal on Selected
Areas in Communications, Vol. 14, No. 5, pp. 764-779, 1996.
[5] R. Ramaswami, K. Sivarajan, "Design of Logical Topologies for
Wavelength-Routed Optical Networks", IEEE Journal on Selected
Areas in Communications, Vol. 14, No. 5, pp. 840-851, 1996.
[6] B. Van Caenegem, W. Van Parys, F. De Turck, P. Demeester,
"Dimensioning of Survivable WDM Networks", IEEE Journal on
Selected Areas in Communications, Vol. 16, No. 7, pp. 1146-1157,
1998.
[7] S. Chang, B. Gavish, "Telecommunications Network Topological
Design and Capacity Expansion: Formulation and Algorithms",
Telecommunication Systems, Vol. 1, pp. 99-131, 1993.
[8] N. Zadeh, "On Building Minimum Cost Communication Networks over
Time", Networks, Vol. 4, pp. 19-34, 1974.
[9] N. Christofides, P. Brooker, "Optimal Expansion of an Existing
Network", Mathematical Programming, Vol. 6, pp. 197-211, 1974.
[10] P. Doulliez, R. Rao, "Optimal Network Capacity Planning: a Shortest
Path Scheme", Operations Research, Vol. 23, pp. 811-818, 1975.
[11] M. Minoux, "Network Synthesis and Dynamic Network Optimization",
Annals of Discrete Mathematics, Vol. 31, pp. 283-324, 1987.
[12] B. Garcia, P. Mahey, L. Leblanc, " Iterative Improvement Methods for a
Multi-Period Network Design Problem", European Journal of
Operations Research, Vol. 110, No.1, pp. 150-165, 1998.
[13] A. Balakrishnan, T. Magnanti, A. Shulman, R. Wong, "Models for
Planning Capacity Expansion in Local Access Telecommunication
Networks", Annals of Operations Research, Vol. 33, pp. 239-284, 1991.
[14] T. Wu, R. Cardwell, M. Boyden, "A Multi-Period Design Model for
Survivable Network Architecture Selection for SONET Interoffice
Networks", IEEE Transactions on Reliability, Vol. 40, No. 4, pp. 417-
427, 1991.
[15] S. Parrish, T. Cox, W. Kuehner, Y. Qiu, "Planning for Optimal
Expansion of Leased Line Communication Networks", Annals of
Operations Research, Vol. 36, pp. 347-364, 1992.
[16] T. Wu, "Emerging Technologies for Fiber Network Survivability",
IEEE Communications Magazine, Vol. 33, No. 2, pp. 58-74, 1995.
[17] M. Grötschel, C. Monma, M. Stoer, "Design of Survivable Networks",
In Handbooks of Operations Research and Management Science, Vol.7
(M. Ball, T. Magnanti, C. Monma, G. Nemhauser, Ed.). North-Holland,
Amsterdam, pp. 617-672, 1995.
[18] R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms
and Applications. Prentice Hall, Englewood Cliffs, New Jersey, 1993.
[19] M. Pickavet, F. Poppe, J. Luystermans, P. Demeester, "A Genetic
Algorithm for Solving the Capacitated Survivable Network Design
Problem", Fifth International Conference on Telecommunication
Systems, pp. 71-76, 1997.
[20] T. Almeida, "Optical Transport Networks - From Concepts towards an
International Field Trial", Seventh International Network Planning
Symposium Networks'96, pp. 711-716, 1996.
@article{"International Journal of Information, Control and Computer Sciences:49478", author = "S.Baskar and P.S.Ramkumar and R.Kesavan", title = "Genetic Algorithm Based Wavelength Division Multiplexing Networks Planning", abstract = "This paper presents a new heuristic algorithm useful
for long-term planning of survivable WDM networks. A multi-period
model is formulated that combines network topology design and
capacity expansion. The ability to determine network expansion
schedules of this type becomes increasingly important to the
telecommunications industry and to its customers. The solution
technique consists of a Genetic Algorithm that allows generating
several network alternatives for each time period simultaneously and
shortest-path techniques to deduce from these alternatives a least-cost
network expansion plan over all time periods. The multi-period
planning approach is illustrated on a realistic network example.
Extensive simulations on a wide range of problem instances are
carried out to assess the cost savings that can be expected by
choosing a multi-period planning approach instead of an iterative
network expansion design method.", keywords = "Wavelength Division Multiplexing, Genetic
Algorithm, Network topology, Multi-period reliable network
planning", volume = "3", number = "3", pages = "503-9", }
