Approximation algorithms for the design of SDH/SONET networks
Nadia Brauner; Yves Crama; Gerd Finke; Pierre Lemaire; Christelle Wynants
RAIRO - Operations Research (2010)
- Volume: 37, Issue: 4, page 235-247
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topBrauner, Nadia, et al. "Approximation algorithms for the design of SDH/SONET networks." RAIRO - Operations Research 37.4 (2010): 235-247. <http://eudml.org/doc/105293>.
@article{Brauner2010,
abstract = {
In this paper, a graph partitioning problem that arises in the design of
SONET/SDH networks is defined and formalized. Approximation algorithms with
performance guarantees are presented. To solve this problem efficiently in
practice, fast greedy algorithms and a tabu-search method are proposed and
analyzed by means of an experimental study.
},
author = {Brauner, Nadia, Crama, Yves, Finke, Gerd, Lemaire, Pierre, Wynants, Christelle},
journal = {RAIRO - Operations Research},
keywords = {Graph partitioning; approximations; heuristics; tabu; SONET/SDH networks.; graph partitioning; SONET/SDH networks},
language = {eng},
month = {3},
number = {4},
pages = {235-247},
publisher = {EDP Sciences},
title = {Approximation algorithms for the design of SDH/SONET networks},
url = {http://eudml.org/doc/105293},
volume = {37},
year = {2010},
}
TY - JOUR
AU - Brauner, Nadia
AU - Crama, Yves
AU - Finke, Gerd
AU - Lemaire, Pierre
AU - Wynants, Christelle
TI - Approximation algorithms for the design of SDH/SONET networks
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 4
SP - 235
EP - 247
AB -
In this paper, a graph partitioning problem that arises in the design of
SONET/SDH networks is defined and formalized. Approximation algorithms with
performance guarantees are presented. To solve this problem efficiently in
practice, fast greedy algorithms and a tabu-search method are proposed and
analyzed by means of an experimental study.
LA - eng
KW - Graph partitioning; approximations; heuristics; tabu; SONET/SDH networks.; graph partitioning; SONET/SDH networks
UR - http://eudml.org/doc/105293
ER -
References
top- R. Aringhieri and M. Dell'Amico, A Variable-Neighborhood Variable-Objective Tabu Search Algorithm for the SONET Ring Assignment with Capacity Constraints. DISMI, Università di Modena e Reggio Emilia, 10 (2001).
- N. Brauner, Y. Crama, P. Lemaire and C. Wynants, Complexité et approximation pour la conception de réseaux SONET/SDH. Technical Report 61, Les Cahiers du Laboratoire Leibniz-IMAG, (October 2002). URIhttp://www-leibniz.imag.fr/LesCahiers/
- N. Brauner and P. Lemaire, A Set-Covering Approach for SONET Network Design. Technical Report 62, Les Cahiers du Laboratoire Leibniz-IMAG (October 2002). URIhttp://www-leibniz.imag.fr/LesCahiers/
- V. Chvátal, A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res.4 (1979) 233-235 .
- ETSI. ETSI - Telecom Standards. URIhttp://www.etsi.org
- ETSI. Transmission and Multiplexing (TM); Synchronous Digital Hierarchy (SDH); Network protection schemes; Rings and other schemes. Technical specification (November 1997). ref: TS 101 010 v1.1.1.
- ETSI. Transmission and Multiplexing (TM); Synchronous Digital Hierarchy (SDH); Network protection schemes; Types and characteristics. Technical specification (November 1997). ref: TS 101 009 v1.1.1.
- B. Fortz, P. Soriano and C. Wynants, A Tabu Search Algorithm for Self-Healing Ring Network Design. Eur. J. Oper. Res.151 (2003).
- M.R. Garey and D.S. Johnson, Computers and Intractability (A Guide to the Theory of NP-Completeness). W.H. Freeman And Company (1979).
- F. Glover and M. Laguna, Modern Heuristic Techniques for Combinatorial Problems, Chapter 3: Tabu Search. C.R. Reeves, Blackwell Scientific Publications edition (1993).
- F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, London (1997).
- O. Goldschmidt, D.S. Hochbaum, A. Levin and E.V. Olinick, The SONET Edge-Partition Problem. Networks41 (2003) 13-23 .
- O. Goldschmidt, A. Laugier and E.V. Olinick, SONET/SDH Ring Assignment with Capacity Constraints. Discrete Appl. Math.129 (2003) 99-128 .
- I. Holyer, The NP-completeness of some edge-partition problems. SIAM J. Comput.4 (1981) 713-717.
- D.S. Johnson, A. Demers, J.D. Ullman, M.R. Garey and R.L. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput.3 (1974) 299-325 .
- S. Khanna, A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem. Bell Labs Technical Journal (1997) 36-41.
- M. Laguna, Clustering for the Design of SONET Rings in Interoffice Telecommunications. Manage. Sci.40 (1994) 1533-1541.
- Y. Lee, H.D. Sherali, J. Han and S. Kim, A branch-and-cut algorithm for solving an intraring synchronous optical network design problem. Networks35 (2000) 223-232 .
- P. Lemaire, Optimisation de réseaux SONET/SDH : éléments théoriques et résolution pratique (juin 2001). Mémoire de DEA.
- S. Masuyama and T. Ibaraki, Chain Packing in Graphs. Algorithmica6 (1991) 826-839 .
- D. Mili, Self-Healing Ring Architectures for SONET Network Applications. URIhttp://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol2/dm9/article2.html
- A. Schrijver, P. Seymour and P. Winkler, The Ring Loading Problem. SIAM J. Discrete Math.11 (1998) 1-14 .
- A. Sutter, F. Vanderbeck and L.A. Wolsey, Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms. Oper. Res.46 (1998) 719-728.
- T.-H. Wu, Fiber Network Service Survivability. Artech House, Inc. (1992).
- The SONET Home Page. URIhttp://www.sonet.com
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.