Better bounds for minimizing SONET ADMs. (English) Zbl 1181.68023
Summary: SONET Add-Drop Multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. Following previous work, we consider the problem where the route of each traffic stream is given as input, and we need to assign wavelengths so as to minimize the total number of used SONET ADMs. This problem is known to be NP-hard, and the best known approximation algorithm for this problem has a performance guarantee of \(\frac{3}{2}\). We improve this result, and present a \(\frac{98}{69}\approx 1.42029\)-approximation algorithm. We also study some of the previously proposed algorithms for this problem, and give either tight or tighter analysis of their approximation ratio.
References:
| [1] | Cǎlinescu, G.; Frieder, O.; Wan, P.-J., Minimizing electronic line terminals for automatic ring protection in general WDM optical networks, IEEE J. Selected Area Communications, 20, 183-189 (2002) |
| [2] | Cǎlinescu, G.; Wan, P.-J., Traffic partition in WDM/SONET rings to minimize SONET ADMs, J. Comb. Optim., 6, 425-453 (2002) · Zbl 1046.90012 |
| [3] | Eilam, T.; Moran, S.; Zaks, S., Lightpath arrangement in survivable rings to minimize the switching cost, IEEE J. Selected Area Communications, 20, 172-182 (2002) |
| [4] | L. Epstein, A. Levin, Better bounds for minimizing SONET ADMs, in: Proc. of the 2nd Workshop on Approximation and online Algorithms (WAOA2004), 2004, pp. 281-294; L. Epstein, A. Levin, Better bounds for minimizing SONET ADMs, in: Proc. of the 2nd Workshop on Approximation and online Algorithms (WAOA2004), 2004, pp. 281-294 · Zbl 1124.90321 |
| [5] | O. Gerstel, P. Lin, G. Sasaki, Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings, in: Proc. INFOCOM 1998, 1, 1998, pp. 94-101; O. Gerstel, P. Lin, G. Sasaki, Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings, in: Proc. INFOCOM 1998, 1, 1998, pp. 94-101 |
| [6] | L. Liu, X. Li, P.-J. Wan, O. Frieder, Wavelength assignment in WDM rings to minimize SONET ADMs, in: Proc. INFOCOM 2000, 2, 2000, pp. 1020-1025; L. Liu, X. Li, P.-J. Wan, O. Frieder, Wavelength assignment in WDM rings to minimize SONET ADMs, in: Proc. INFOCOM 2000, 2, 2000, pp. 1020-1025 |
| [7] | Orlin, J. B., A faster strongly polynomial minimum cost flow algorithm, Oper. Res., 41, 338-350 (1993) · Zbl 0781.90036 |
| [8] | Schrijver, A., Combinatorial Optimization Polyhedra and Efficiency (2003), Springer-Verlag · Zbl 1041.90001 |
| [9] | M. Shalom, S. Zaks, A \(10 / 7 + \operatorname{\\(\#\#\#\#\\)} \); M. Shalom, S. Zaks, A \(10 / 7 + \operatorname{\\(\#\#\#\#\\)} \) |
| [10] | Wan, P.-J.; Cǎlinescu, G.; Liu, L.; Frieder, O., Grooming of arbitrary traffic in SONET/WDM BLSRs, IEEE J. Selected Area Communications, 18, 1995-2003 (2000) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
