Record Details

Scheduling light-trails on WDM rings

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Scheduling light-trails on WDM rings
 
Creator PAL, S
RANADE, A
 
Subject Wavelength division multiplexing
WDM
Light-trail
Reconfigurable bus architecture
Scheduling
Routing
Wavelength assignment
Approximation
On-line
Algorithm
Simulation
IP CENTRIC COMMUNICATION
NETWORKS
EFFICIENT
BUS
ASSIGNMENT
ALGORITHM
ARRAY
 
Description 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 a 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 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 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 simulations (for the classes of traffic we consider), but which has competitive ratio between Omega(log(2) n/ log log n) and O(log(2) n). We present detailed simulations of both our algorithms. (C) 2012 Elsevier Inc. All rights reserved.
 
Publisher ACADEMIC PRESS INC ELSEVIER SCIENCE
 
Date 2014-10-15T13:50:28Z
2014-10-15T13:50:28Z
2012
 
Type Article
 
Identifier JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 72(10)1226-1236
http://dx.doi.org/10.1016/j.jpdc.2012.05.010
http://dspace.library.iitb.ac.in/jspui/handle/100/15029
 
Language en