Intelligent Grooming Of Traffic In SONET/WDM Ring Networks

Traffic grooming in SONET/WDM optical ring networks is one of the most important and hot problems in the area of optical network. It is also a relatively new research topic with high scientific and commercial values. High efficient grooming of traffic can effectively reduce the network cost. Hence, it has aroused much attention from the researchers in both research and business institutes since its appearance in 1998. Due to the NP-hard property of this problem, the research on it is mainly focused on ring networks with various heuristics.We systematically investigated the grooming problems in both unidirectional and bidirectional SONET/WDM rings with static and dynamic traffic requirements in this thesis. We formulated these problems as a set of mathematic programming equations and proposed genetic algorithms and tabu search approaches to deal with them. The major contributions of this thesis include: 1) To formulate a set of multi-objective integer nonlinear programming (MOINLP) equations to the general grooming problems in SONET/WDM rings with both static and dynamically changing traffics; 2) To classify the blocking properties of the grooming problems with dynamic traffic in detail; and 3) To propose the genetic algorithms and tabu search approaches along with local heuristics to deal with a variety of grooming problems in rings. We realized the algorithms, gave out the grooming results and made some detailed discussions on them. Some of the minor contributions of this thesis are: 1) To device the Order-Mapped Crossover operator and put forward the concept of Adaptive Chromosome in genetic algorithm; 2) To derive tighter theoretical lower and upper bounds on both the numbers of ADM's and wavelengths; and 3) To present some parameters that are useful in evaluating the grooming results with both static and dynamic traffic requirements.The main content of this thesis is as follows.As it is important to describe the grooming problems with mathematics, we formulated the grooming problems in SONET/WDM rings as a set of MOINLP equations for the first time. This set of equations is general in the sense that it can be used to the optimizations of either the number of ADM's or the number of wavelengths or both of them simultaneously; to the cases with or without traffic split in both rings; to the situations with fixed route or the route of each traffic optimized concurrently with the optimizations of the objectives. It exerts no constraint on the traffic requirements. When there is only one set of traffic requirement on the ring, it is suitable for the grooming problems with static traffic; when multiple traffic requirements are considered, it is adapted to those with dynamic traffic with various blocking properties. We also showed that they could be reduced to linear ones if fixed route was assigned to each traffic beforegrooming. In a word, this set of equations redounds to the formal description of the grooming problems in rings.For dynamic grooming problems, we first classified them in terms of blocking properties detailedly. We showed that in all-to-all traffic requirement with no split, there are only strictly and rearrangeably nonblocking groomings but no wide-sense nonblocking grooming. In strictly nonblocking grooming, the same traffic request in different traffic requirements must be assigned to the same wavelength, but in rearrangeable one it is allowed to be assigned to different wavelength. We also showed that in partial traffic requirement or in those with split traffic, there exists wide-sense nonblocking grooming class. This classification is useful for designing different grooming algorithms for different blocking properties.We derived the theoretical lower and upper bounds on the number of wavelengths in both rings with both static and dynamic traffics. Two lower and upper bounds on the number of AMD's were also derived and the tighter ones were obtained. Computer simulation results showed that sometimes the lower bounds are the infimum of the problem.To solve to grooming proble...