Dynamic Traffic Grooming Algorithms for Reconfigurable SONET Over WDM Networks

The emergence of wavelength-division multiplexing (WDM) technology provides the capability for increasing the bandwidth of synchronous optical network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add–drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom the traffic, and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently. Moreover, the traffic pattern of the optical network changes from time to time. How to develop dynamic reconfiguration algorithms for traffic grooming is an important issue. In this paper, two cases (best fit and full fit) for handling reconfigurable SONET over WDM networks are proposed. For each approach, an integer linear programming model and heuristic algorithms (TS-1 and TS-2, based on the tabu search method) are given. The results demonstrate that the TS-1 algorithm can yield better solutions but has a greater running time than the greedy algorithm for the best fit case. For the full fit case, the tabu search heuristic yields competitive results compared with an earlier simulated annealing based method and it is more stable for the dynamic case.

Applications of Linear Programming to Coding Theory

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.