We study the problem of routing and scheduling requests of limited durations in all-optical net- works 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.

Becchetti, L., DI IANNI, M., Marchetti Spaccamela, A. (2004). Approximating call-scheduling makespan in all-optical networks. JOURNAL OF DISCRETE ALGORITHMS, 2(4), 501-515 [10.1016/j.jda.2004.04.008].

Approximating call-scheduling makespan in all-optical networks

DI IANNI, MIRIAM;
2004-01-01

Abstract

We study the problem of routing and scheduling requests of limited durations in all-optical net- works 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
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - INFORMATICA
English
Senza Impact Factor ISI
Optical networks; Scheduling; Approximation algorithms
Becchetti, L., DI IANNI, M., Marchetti Spaccamela, A. (2004). Approximating call-scheduling makespan in all-optical networks. JOURNAL OF DISCRETE ALGORITHMS, 2(4), 501-515 [10.1016/j.jda.2004.04.008].
Becchetti, L; DI IANNI, M; Marchetti Spaccamela, A
Articolo su rivista
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: https://hdl.handle.net/2108/58267
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact