Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings

This work deals with wavelength assignment for lightpaths. We restrict our attention to the near term, in which WDM networks will be in the form of rings and higher level networks will be SONET/SDH self-healing rings. This view changes the goal of wavelength assignment (WLA) vs. previous work on the subject in a number of aspects. First, a pair of SONET add/drop multiplexers (ADMs) terminates each lightpath, These ADMs also terminate adjacent lightpaths to form rings, implying that the WLA has to support this type of sharing, Second, following [GRS98], we argue that the first-order optimization goal should be to minimize the overall network cost which is dominated by the number of required ADMs and not the number of wavelengths. We show that these two minimization problems are intrinsically different, and there exist cases where the two minima cannot be simultaneously achieved. We derive a simple lower bound to the number of ADMs. Depending on the given lightpaths, we show that this lower bound is not always achievable. Pie also show that adding wavelength converters to the system does not improve the cost but that splitting a lightpath and handling each part separately may reduce the total number of ADMs. We develop two heuristics to minimize the number of ADMs: Cut-First, and Assign-First. Both heuristics, using different approaches, attempt to use the smallest number of ADMs possible. We also show-that Cut-First always uses the minimum number of wavelengths, but because of the cut, may use more ADMs than necessary. However, the number of extra ADMs is proven to be bounded by the number of supported wavelengths and typically much less. We show instances where Cut-First performs better than Assign-First and vice versa, Finally, we present a set of transformations that take any WLA and improve its cost.