1st Annual Conference on Broadband Networks

Research Article

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

  • @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 Shalom1,*, 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.