article

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

Authors:

Mordechai Shalom,

Shmuel ZaksAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 15, Issue 6

Pages 1593 - 1602

https://doi.org/10.1109/TNET.2007.906638

Published: 01 December 2007 Publication History

Abstract

SONET add/drop multiplexers (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 Calinescu and Wan, 2002. 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.

References

[1]

{1} J.-C. Bérmond, L. Braud, and D. Coudert, "Traffic grooming on the path", presented at the 12th Colloq. Structural Information and Communication Complexity, Mont Saint-Michel, France, May 2005.

[2]

{2} J.-C. Bermond and D. Coudert, "Traffic grooming in unidirectional WDM ring networks using design theory," presented at the IEEE ICC, Anchorage, AK, May 2003.

[3]

{3} G. Calinescu, O. Frieder, and P.-J. Wan, "Minimizing electronic line terminals for automatic ring protection in general wdm optical networks," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 183-189, Jan. 2002.

[4]

{4} A. L. Chiu and E. H. Modiano, "Traffic grooming algorithms for reducing electronic multiplexing costs in wdm ring networks," J. Lightw. Technol., vol. 18, no. 1, pp. 2-12, Jan. 2000.

[5]

{5} G. Calinescu and P.-J. Wan, "Traffic partition in WDM/SONET rings to minimize SONET ADMs," J. Combin. Opt., vol. 6, no. 4, pp. 425-453, 2002.

[6]

{6} T. Eilam, "Cost vs. quality, tradeoffs in communication networks," Ph.D. dissertation, Faculty of Computer Science, Technion-Israel Inst. Technol., Haifa, Israel, Feb. 2000.

[7]

{7} L. Epstein and A. Levin, "Better bounds for minimizing sonet adms," presented at the 2nd Workshop on Approximation and Online Algorithms, Bergen, Norway, Sep. 2004.

[8]

{8} T. Eilam, S. Moran, and S. Zaks, "Lightpath arrangement in survivable rings to minimize the switching cost," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 172-182, Jan. 2002.

[9]

{9} M. Flammini, G. Monaco, L. Moscardelli, M. Shalom, and S. Zaks, "Approximating the traffic grooming problem in tree and star networks," presented at the WG 2006 Workshop, Bergen, Norway, Mar. 2006.

[10]

{10} M. Flammini, L. Moscardelli, M. Shalom, and S. Zaks, "Approximating the traffic grooming problem," presented at the 16th Symp. Algorithms and Computation (ISAAC 2005), Sanya, Hainan, China, Dec. 2005.

[11]

{11} O. Gerstel, P. Lin, and G. Sasaki, "Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings," in Proc. IEEE INFOCOM'98 , 1998, pp. 69-77.

[12]

{12} O. Gerstel, P. Lin, and G. Sasaki, "Combined WDM and SONET network design," in Proc. IEEE INFOCOM'99, 1999, vol. 2, pp. 734-43.

[13]

{13} O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," in Proc. IEEE INFOCOM'98, Mar. 1998, pp. 69-77.

[14]

{14} C. A. J. Hurkens and A. Schrijver, "On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems," SIAM J. Discrete Math., vol. 2, no. 1, pp. 68-722, Feb. 1989.

[15]

{15} S. Khanna, "A polynomial time approximation scheme for the SONET ring loading problem," Bell Labs Tech. J., pp. 36-41, Spring, 1997.

[16]

{16} L. Liu, X. Li, P.-J. Wan, and O. Frieder, "Wavelength assignment in a wdm rings to minimize sonet adms," in Proc. IEEE INFOCOM'2000, Tel-Aviv, Israel, 2000, pp. 1020-1025.

[17]

{17} P. J. Wan, G. Calinescu, L.-W. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET/WDM rings," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995-2003, Oct. 2000.

[18]

{18} G. Wilfong and P. Winkler, "Ring routing and wavelength translation," in Proc. 9th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA'98), San Francisco, CA, Jan. 1998, pp. 333-341.

[19]

{19} K. Zhu and B. Mukherjee, "A review of traffic grooming in WDM optical networks: Architecture and challenges," Opt. Netw. Mag., vol. 4, no. 2, pp. 55-64, Mar.-Apr. 2003.

Cited By

Shalom MWong PZaks S(2016)On-line maximum matching in complete multi-partite graphs with an application to optical networksDiscrete Applied Mathematics10.1016/j.dam.2014.10.040199:C(123-136)Online publication date: 30-Jan-2016
https://dl.acm.org/doi/10.1016/j.dam.2014.10.040
Gözüpek DShalom MAlagöz F(2015)A graph-theoretic approach to scheduling in cognitive radio networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.229744123:1(317-328)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2297441
Epstein LLevin A(2012)On Equilibria for ADM Minimization GamesAlgorithmica10.5555/3226239.322638363:1-2(246-273)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.5555/3226239.3226383
Show More Cited By

Index Terms

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

Recommendations

Minimization of the number of ADMs in SONET rings with maximum throughput with implications to the traffic grooming problem

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, recent papers argue that the number of ADMs is a more realistic cost ...
Minimizing the number of ADMs in SONET rings with maximum throughput
SIROCCO'05: Proceedings of the 12th international conference on Structural Information and Communication Complexity

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 ...
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; Clinescu and Wan, Traffic partition in WDM/SONET rings to minimize SONET ADMs, submitted for ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 15, Issue 6

December 2007

400 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2007

Published in TON Volume 15, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
133
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shalom MWong PZaks S(2016)On-line maximum matching in complete multi-partite graphs with an application to optical networksDiscrete Applied Mathematics10.1016/j.dam.2014.10.040199:C(123-136)Online publication date: 30-Jan-2016
https://dl.acm.org/doi/10.1016/j.dam.2014.10.040
Gözüpek DShalom MAlagöz F(2015)A graph-theoretic approach to scheduling in cognitive radio networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.229744123:1(317-328)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TNET.2013.2297441
Epstein LLevin A(2012)On Equilibria for ADM Minimization GamesAlgorithmica10.5555/3226239.322638363:1-2(246-273)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.5555/3226239.3226383
Shalom MWong PZaks S(2010)Optimal on-line colorings for minimizing the number of ADMs in optical networksJournal of Discrete Algorithms10.1016/j.jda.2009.02.0068:2(174-188)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.jda.2009.02.006
Epstein LLevin A(2009)On Equilibria for ADM Minimization GamesProceedings of the 2nd International Symposium on Algorithmic Game Theory10.1007/978-3-642-04645-2_31(347-358)Online publication date: 13-Oct-2009
https://dl.acm.org/doi/10.1007/978-3-642-04645-2_31

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents