Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-12-29
Computer Science
Distributed, Parallel, and Cluster Computing
19 pages, 4 figures, Submitted to Journal of Parallel and Distributed Computing (JPDC) on June 22, 2011
Scientific paper
We consider the problem of scheduling communication on optical WDM (wavelength division multiplexing) networks using the light-trails technology. We seek to design scheduling algorithms such that the given transmission requests can be scheduled using minimum number of wavelengths (optical channels). We provide algorithms and close lower bounds for two versions of the problem on an $n$ processor linear array/ring network. In the {\em stationary} version, the pattern of transmissions (given) is assumed to not change over time. For this, a simple lower bound is $c$, the congestion or the maximum total traffic required to pass through any link. We give an algorithm that schedules the transmissions using $O(c+\log{n})$ wavelengths. We also show a pattern for which $\Omega(c+\log{n}/\log\log{n})$ wavelengths are needed. In the {\em on-line} version, the transmissions arrive and depart dynamically, and must be scheduled without upsetting the previously scheduled transmissions. For this case we give an on-line algorithm which has competitive ratio $\Theta(\log{n})$. We show that this is optimal in the sense that every on-line algorithm must have competitive ratio $\Omega(\log{n})$. We also give an algorithm that appears to do well in simulation (for the classes of traffic we consider), but which has competitive ratio between $\Omega(\log^2n/\log \log{n})$ and $O(\log^2n)$. We present detailed simulations of both our algorithms.
Pal Soumitra
Ranade Abhiram
No associations
LandOfFree
Scheduling Light-trails in WDM Rings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Scheduling Light-trails in WDM Rings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling Light-trails in WDM Rings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-728393