About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Lightpath arrangement in survivable rings to minimize the switching cost
Abstract
This paper studies the design of low-cost survivable wavelength-division-multiplexing (WDM) networks. To achieve survivability, lightpaths are arranged as a set of rings. Arrangement in rings is also necessary to support SONET/SDH protection schemes such as 4FBLSR above the optical layer. This is expected to be the most common architecture in regional (metro) networks [9]. We assume that we are given a set of lightpaths in an arbitrary network topology and aim at finding a partition of the lightpaths to rings adding a minimum number of lightpaths to the original set. The cost measure that we consider (number of lightpaths) reflects the switching cost of the entire network. In the case of a SONET/SDH higher layer, the number of lightpaths is equal to the number of add-drop multiplexers (ADMs) (since two subsequent lightpaths in a ring can share an ADM at the common node). We prove some negative results on the tractability and approximability of the problem and provide an approximation algorithm with a worst case approximation ratio of 8/5. We study some special cases in which the performance of the algorithm is improved. A similar problem was introduced, motivated, and studied in [9] and recently in [13] (where it was termed minimum ADM problem). However, these two works focused on a ring topology while we generalize the problem to an arbitrary network topology.