We consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2 ln(d · g) + o(ln(d · g)) for any fixed node degree bound d and grooming factor g, and 2 ln g + o(ln g) in unbounded degree directed trees, respectively. In the attempt to extend our results to general undirected trees, we completely characterize the complexity of the problem in star networks by providing polynomial time optimal algorithms for g <= 2 and proving the intractability of the problem for any fixed g > 2. While for general topologies, the problem was known to be NP-hard g not constant, the complexity for fixed values of g was still an open question.

Approximating the Traffic Grooming Problem in Tree and Star Networks

FLAMMINI, MICHELE
2008

Abstract

We consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2 ln(d · g) + o(ln(d · g)) for any fixed node degree bound d and grooming factor g, and 2 ln g + o(ln g) in unbounded degree directed trees, respectively. In the attempt to extend our results to general undirected trees, we completely characterize the complexity of the problem in star networks by providing polynomial time optimal algorithms for g <= 2 and proving the intractability of the problem for any fixed g > 2. While for general topologies, the problem was known to be NP-hard g not constant, the complexity for fixed values of g was still an open question.
Wavelength division multiplexing (WDM) - Tree ptical networks; Add-drop multiplexer (ADM); Traffic grooming
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/144
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact