Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs

摘要

SONET ADMs are the dominant cost factor in the WDM SONET rings. Recently several articles (Belvaux et al., European J. Oper. Res. 108 (1) (1998) 26-35; Calinescu and Wan, Traffic partition in WDM SONET rings to minimize SONET ADMs, submitted for publication; Gerstel et al., Proc. IEEE INFOCOM'98, vol.1, pp.94-101; Liu et al., Proc. INFOCOM, vol. 2, 2000, pp. 1020-1025; Sutter et al., Oper. Res. 46 (5) (1998) 719-728) proposed a number of heuristics for traffic partition so as to use as few SONET ADMs as possible. Most of these heuristics assumes wavelength-continuity, i.e., the same wavelength is allocated on all of the links in the path established for a traffic stream. It was first observed and argued by Gerstel et al. that the number of ADMs can be potentially reduced by allowing a traffic stream to be locally transferred from one ADM in a wavelength to another ADM in a different wavelength at any intermediate node, in other words, the traffic streams are splittable. In this paper, we study two variations of this minimum ADM problem with splittable traffic streams; all traffic streams have prespecified routings, and all traffic streams have no prespecified routings respectively. Both variations are shown to be NP-hard. For the former variation, a heuristic with approximation ratio at most 5/4 is proposed. For the latter variation, a similar heuristic with approximation ratio 3 2 is proposed.