Lightpath arrangement in survivable rings to minimize the switchingcost

摘要

This paper studies the design of low-cost survivablenwavelength-division-multiplexing (WDM) networks. To achievensurvivability, lightpaths are arranged as a set of rings. Arrangement innrings is also necessary to support SONET/SDH protection schemes such asn4FBLSR above the optical layer. This is expected to be the most commonnarchitecture in regional (metro) networks. We assume that we are given anset of lightpaths in an arbitrary network topology and aim at finding anpartition of the lightpaths to rings adding a minimum number ofnlightpaths to the original set. The cost measure that we considern(number of lightpaths) reflects the switching cost of the entirennetwork. In the case of a SONET/SDH higher layer, the number ofnlightpaths is equal to the number of add-drop multiplexers (ADMs) (sincentwo subsequent lightpaths in a ring can share an ADM at the commonnnode). We prove some negative results on the tractability andnapproximability of the problem and provide an approximation algorithmnwith a worst case approximation ratio of 8/5. We study some specialncases in which the performance of the algorithm is improved. A similarnproblem was introduced, motivated, and studied by Liu, Li, Wan andnFrieder (see Proc. INFOCOM 2000, p.1020-1025, 2000) Gerstel, Lin andnSasaki, (see Proc. IEEE INFOCOM '98, p. 94-101, 1998)(where it wasntermed minimum ADM problem). However, these two works focused on a ringntopology while we generalize the problem to an arbitrary networkntopology