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

Abstract

top
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.

How to cite

top

Brauner, 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
  1. 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).  
  2. 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/
  3. 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/
  4. V. Chvátal, A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res.4 (1979) 233-235 .  Zbl0443.90066
  5. ETSI. ETSI - Telecom Standards.  URIhttp://www.etsi.org
  6. 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.  
  7. 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.  
  8. B. Fortz, P. Soriano and C. Wynants, A Tabu Search Algorithm for Self-Healing Ring Network Design. Eur. J. Oper. Res.151 (2003).  Zbl1053.90020
  9. M.R. Garey and D.S. Johnson, Computers and Intractability (A Guide to the Theory of NP-Completeness). W.H. Freeman And Company (1979).  Zbl0411.68039
  10. F. Glover and M. Laguna, Modern Heuristic Techniques for Combinatorial Problems, Chapter 3: Tabu Search. C.R. Reeves, Blackwell Scientific Publications edition (1993).  
  11. F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, London (1997).  
  12. O. Goldschmidt, D.S. Hochbaum, A. Levin and E.V. Olinick, The SONET Edge-Partition Problem. Networks41 (2003) 13-23 .  Zbl1026.90076
  13. O. Goldschmidt, A. Laugier and E.V. Olinick, SONET/SDH Ring Assignment with Capacity Constraints. Discrete Appl. Math.129 (2003) 99-128 .  Zbl1023.68003
  14. I. Holyer, The NP-completeness of some edge-partition problems. SIAM J. Comput.4 (1981) 713-717.  Zbl0468.68069
  15. 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 .  Zbl0297.68028
  16. S. Khanna, A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem. Bell Labs Technical Journal (1997) 36-41.  
  17. M. Laguna, Clustering for the Design of SONET Rings in Interoffice Telecommunications. Manage. Sci.40 (1994) 1533-1541.  Zbl0823.90040
  18. 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 .  Zbl0985.90093
  19. P. Lemaire, Optimisation de réseaux SONET/SDH : éléments théoriques et résolution pratique (juin 2001). Mémoire de DEA.  
  20. S. Masuyama and T. Ibaraki, Chain Packing in Graphs. Algorithmica6 (1991) 826-839 .  Zbl0731.68088
  21. D. Mili, Self-Healing Ring Architectures for SONET Network Applications.  URIhttp://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol2/dm9/article2.html
  22. A. Schrijver, P. Seymour and P. Winkler, The Ring Loading Problem. SIAM J. Discrete Math.11 (1998) 1-14 .  Zbl0910.90135
  23. A. Sutter, F. Vanderbeck and L.A. Wolsey, Optimal Placement of Add/Drop Multiplexers: Heuristic and Exact Algorithms. Oper. Res.46 (1998) 719-728.  Zbl0987.90014
  24. T.-H. Wu, Fiber Network Service Survivability. Artech House, Inc. (1992).  
  25. The SONET Home Page.  URIhttp://www.sonet.com

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.