A 10/7 + ε approximation for minimizing the number of ADMs in SONET rings

Mordechai Shalom; Shmuel Zaks

1st Annual Conference on Broadband Networks

Research Article

A 10/7 + ε approximation for minimizing the number of ADMs in SONET rings

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/BROADNETS.2004.1,
    author={Mordechai Shalom and Shmuel Zaks},
    title={A 10/7 + ε approximation for minimizing the number of ADMs in SONET rings},
    proceedings={1st Annual Conference on Broadband Networks},
    publisher={IEEE},
    proceedings_a={BROADNETS},
    year={2004},
    month={12},
    keywords={},
    doi={10.1109/BROADNETS.2004.1}
}

Mordechai Shalom
Shmuel Zaks
Year: 2004
A 10/7 + ε approximation for minimizing the number of ADMs in SONET rings
BROADNETS
IEEE
DOI: 10.1109/BROADNETS.2004.1

Mordechai Shalom¹^,*, Shmuel Zaks^,*

1: Faculty of Computer Science, Technion, 32000 Haifa, Israel

*Contact email: cmshalom@cs.technion.ac.il, zaks@cs.technion.ac.il

Abstract

SONET ADMs are dominant cost factors in WDM/SONET rings. Whereas most previous papers on the topic concentrated on the number of wavelengths assigned to a given set of lightpaths, more recent papers argue that the number of ADMs is a more realistic cost measure. Some of these works discuss various heuristic algorithms for this problem, and the best known result is a 3/2 approximation in G. Calinescu and P.J. Wan (2001). Through the study of the relation between this problem and the problem of finding maximum disjoint rings in a given set of lightpaths we manage to shed more light onto this problem and to develop a 10/7 + ε approximation for it.

Published: 2004-12-13
Publisher: IEEE

: http://dx.doi.org/10.1109/BROADNETS.2004.1