Optimal Design of Delay-Bounded WDM Networks using a Genetic Algorithm

Abstract

We address the problem of real-time delay-bounded multicasting in wavelength-division multiplexed networks to avoid problems of synchronization between video and audio frames. We describe a genetic algorithm based technique to synthesize WDM network topologies that can, with a very high degree of confidence, assure that the multicast traffic is delivered in user-specified limits on time. Unlike existing approaches to WDM network design, we first find a virtual topology that can meet the delay constraints. An embedding of virtual links into physical links is then carried out, followed by an assignment of wavelengths to virtual links.

The problem of finding the virtual topology is difficult because of a large number of parameters. A number of heuristic approaches have been proposed to solve such optimization problems. In our approach we aim to explore the suitability of Genetic Algorithms to solve the WDM network design problem. A genetic algorithm can explore a far greater range of potential solutions to a problem than do conventional approaches. The advantage of a genetic algorithm, compared with other algorithms which use a single initial guess e.g. gradient, descent is to use more information of estimation region, and to decrease the probability of falling into local minimum. We describe quantitative and qualitative results obtained by using our software tool on several benchmark examples.

Indexing terms:

• Wavelength division multiplexing
• Network design
• Optical networks
• Genetic algorithm

Additional information

Notes on contributors

Meeta Sharma

Meeta Sharma is currently a Research Staff Member at IBM, India Research Labs, Delhi. Prior to this, she was a Member of Technical Staff at the Wireless Advanced Technologies Lab, Lucent Bell Labs from January 2001 to February 2002. She graduated with a Master of Science degree from the University of Southern California in Electrical Engineering in December 2000. She received her Bachelor of Technology degree from the Indian Institute of Technology, Delhi in Electrical Engineering in 1999. Her areas of interest include high-speed networks, wireless networks, distributed systems and protocol modeling and testing.

Prachi Jain

Prachi Jain received a BTech degree in Electrical Engineering from Indian Institute of Technology, Delhi in 1999. She received a MS degree from University of Southern California, Los Angeles in 2000. She is currently working in the Research and Development group at QualComm, San Diego. Her current research interests are wireless networks, and simulation and modeling of network protocols