Traffic Grooming on the Path

Jean-Claude Bermond 1 Laurent Braud 2 David Coudert 1, *
* Corresponding author
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In a WDM network, routing a request consists in assigning it a route in the physical network and a wavelength. If each request uses at most 1/C of the bandwidth of the wavelength, we will say that the grooming factor is C. That means that on a given edge of the network we can groom (group) at most C requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add Drop Multiplexers (shortly ADM) used in the network (related to the cost of the nodes). We consider here the case where the network is a path on N nodes, P_N. Thus the routing is unique. For a given grooming factor C minimizing the number of wavelengths is an easy problem, well known and related to the load problem. But minimizing the number of ADM's is NP-complete for a general set of requests and no results are known. Here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where C=2 and where we have a static uniform all-to-all traffic (one request for each pair of vertices).
Liste complète des métadonnées

https://hal.inria.fr/inria-00308716
Contributor : David Coudert <>
Submitted on : Thursday, July 31, 2008 - 9:17:52 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM
Document(s) archivé(s) le : Thursday, June 3, 2010 - 5:27:27 PM

File

BBC-to-tcsa.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Claude Bermond, Laurent Braud, David Coudert. Traffic Grooming on the Path. Theoretical Computer Science, Elsevier, 2007, Structural Information and Communication Complexity (SIROCCO 2005), 384 (2-3), pp.139-151. ⟨10.1016/j.tcs.2007.04.028⟩. ⟨inria-00308716⟩

Share

Metrics

Record views

274

Files downloads

635