Back to Search
Start Over
The chord version for SONET ADMs minimization
- Source :
- Theoretical Computer Science. (3):337-346
- Publisher :
- Elsevier B.V.
-
Abstract
- We consider a problem which arises in optical routing. WDM/SONET rings are a network architecture used by telecommunications carriers for traffic streams. The dominant cost factor in such networks is the total number of add-drop multiplexers (ADMs) used. A list of traffic streams to be routed between pairs of nodes is given. In this paper we consider the problem where we need to assign a route and a wavelength to each traffic stream, minimizing the total number of used SONET ADMs. This is called the chord version of the SONET ADMs minimization problem, to denote the fact that the routing is not given a priori. The best previously known approximation algorithms for this problem have the performance guarantee of 32. We present an improved algorithm with performance guarantee of exactly 107≈1.42857. Moreover, we study some natural heuristics for this problem, and give tight analysis of their approximation ratios.
- Subjects :
- Network architecture
General Computer Science
Synchronous optical networking
ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS
Approximation algorithm
Topology
Multiplexer
Approximation algorithms
Theoretical Computer Science
SONET/WDM
Wavelength-division multiplexing
Optical networks
Minification
Chord (peer-to-peer)
Heuristics
Algorithm
Computer Science(all)
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Issue :
- 3
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....ef0a8e7997bc065adb6518aaa5c92fe7
- Full Text :
- https://doi.org/10.1016/j.tcs.2005.07.040