We study the problem of routing and scheduling requests of limited durations in all-optical networks with restrictions on the number of available wavelengths on each link. The task is servicing the requests, assigning each of them a route from source to destination, a starting time and a wavelength with the goal of minimizing the overall time needed to serve all requests. We study the relationship between this problem and minimum path coloring and we show how to exploit known results on path coloring to derive approximation scheduling algorithms for meshes, trees and nearly-Eulerian, uniformly high-diameter graphs. We also propose different approximation algorithms for stars, trees and in trees of rings. © 2004 Elsevier B.V. All rights reserved.

Approximating call-scheduling makespan in all-optical networks / Becchetti, Luca; Miriam Di, Ianni; MARCHETTI SPACCAMELA, Alberto. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 2:4(2004), pp. 501-515. (Intervento presentato al convegno The 26th International Workshop on Graph-Theoretic Concepts tenutosi a Konstanz nel 15 June 2000 through 17 June 2000) [10.1016/j.jda.2004.04.008].

Approximating call-scheduling makespan in all-optical networks

BECCHETTI, Luca;MARCHETTI SPACCAMELA, Alberto
2004

Abstract

We study the problem of routing and scheduling requests of limited durations in all-optical networks with restrictions on the number of available wavelengths on each link. The task is servicing the requests, assigning each of them a route from source to destination, a starting time and a wavelength with the goal of minimizing the overall time needed to serve all requests. We study the relationship between this problem and minimum path coloring and we show how to exploit known results on path coloring to derive approximation scheduling algorithms for meshes, trees and nearly-Eulerian, uniformly high-diameter graphs. We also propose different approximation algorithms for stars, trees and in trees of rings. © 2004 Elsevier B.V. All rights reserved.
2004
optical networks; rings; scheduling
01 Pubblicazione su rivista::01a Articolo in rivista
Approximating call-scheduling makespan in all-optical networks / Becchetti, Luca; Miriam Di, Ianni; MARCHETTI SPACCAMELA, Alberto. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 2:4(2004), pp. 501-515. (Intervento presentato al convegno The 26th International Workshop on Graph-Theoretic Concepts tenutosi a Konstanz nel 15 June 2000 through 17 June 2000) [10.1016/j.jda.2004.04.008].
File allegati a questo prodotto
File Dimensione Formato  
VE_2004_11573-234735.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 179.12 kB
Formato Adobe PDF
179.12 kB Adobe PDF   Contatta l'autore

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: https://hdl.handle.net/11573/234735
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact