Genetic Algorithm Based Wavelength Division Multiplexing Networks Planning

Authors: S.Baskar, P.S.Ramkumar, R.Kesavan

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

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328144

References:

[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.