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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
