Approximation algorithms for the design of SDH/SONET networks

Nadia Brauner; Yves Crama; Gerd Finke; Pierre Lemaire; Christelle Wynants[1]

  • [1] Electrabel Quantitive Analysis, 8 boulevard du Régent, 1000 Brussels, Belgique

RAIRO - Operations Research - Recherche Opérationnelle (2003)

  • 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 - Recherche Opérationnelle 37.4 (2003): 235-247. <http://eudml.org/doc/245801>.

@article{Brauner2003,
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.},
affiliation = {Electrabel Quantitive Analysis, 8 boulevard du Régent, 1000 Brussels, Belgique},
author = {Brauner, Nadia, Crama, Yves, Finke, Gerd, Lemaire, Pierre, Wynants, Christelle},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {graph partitioning; approximations; heuristics; tabu; SONET/SDH networks},
language = {eng},
number = {4},
pages = {235-247},
publisher = {EDP-Sciences},
title = {Approximation algorithms for the design of SDH/SONET networks},
url = {http://eudml.org/doc/245801},
volume = {37},
year = {2003},
}

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 - Recherche Opérationnelle
PY - 2003
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
UR - http://eudml.org/doc/245801
ER -

References

top
  1. [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. [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). http://www-leibniz.imag.fr/LesCahiers/ 
  3. [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). http://www-leibniz.imag.fr/LesCahiers/ 
  4. [4] V. Chvátal, A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res. 4 (1979) 233-235. Zbl0443.90066MR539404
  5. [5] ETSI. ETSI – Telecom Standards. http://www.etsi.org 
  6. [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. [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. [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.90020MR2014077
  9. [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.68039MR519066
  10. [10] F. Glover and M. Laguna, Modern Heuristic Techniques for Combinatorial Problems, Chapter 3: Tabu Search. C.R. Reeves, Blackwell Scientific Publications edition (1993). MR1230642
  11. [11] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, London (1997). Zbl0930.90083MR1665424
  12. [12] O. Goldschmidt, D.S. Hochbaum, A. Levin and E.V. Olinick, The SONET Edge-Partition Problem. Networks 41 (2003) 13-23. Zbl1026.90076MR1946893
  13. [13] O. Goldschmidt, A. Laugier and E.V. Olinick, SONET/SDH Ring Assignment with Capacity Constraints. Discrete Appl. Math. 129 (2003) 99-128. Zbl1023.68003MR1989013
  14. [14] I. Holyer, The NP-completeness of some edge-partition problems. SIAM J. Comput. 4 (1981) 713-717. Zbl0468.68069MR635429
  15. [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.68028MR434396
  16. [16] S. Khanna, A Polynomial Time Approximation Scheme for the SONET Ring Loading Problem. Bell Labs Technical Journal (1997) 36-41. 
  17. [17] M. Laguna, Clustering for the Design of SONET Rings in Interoffice Telecommunications. Manage. Sci. 40 (1994) 1533-1541. Zbl0823.90040
  18. [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. Networks 35 (2000) 223-232. Zbl0985.90093MR1764882
  19. [19] P. Lemaire, Optimisation de réseaux SONET/SDH : éléments théoriques et résolution pratique (juin 2001). Mémoire de DEA. 
  20. [20] S. Masuyama and T. Ibaraki, Chain Packing in Graphs. Algorithmica 6 (1991) 826-839. Zbl0731.68088MR1134432
  21. [21] D. Mili, Self-Healing Ring Architectures for SONET Network Applications. http://www.doc.ic.ac.uk/ ∼ nd/surprise96/journal/vol2/dm9/article2.html 
  22. [22] A. Schrijver, P. Seymour and P. Winkler, The Ring Loading Problem. SIAM J. Discrete Math. 11 (1998) 1–14. Zbl0910.90135
  23. [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. [24] T.-H. Wu, Fiber Network Service Survivability. Artech House, Inc. (1992). 
  25. [25] The SONET Home Page. http://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.