Transmission Scheduling in WDM Optical Networks

		        Michael A. Palis 
                 Department of Computer Science
                       Rutgers University
                        Camden, NJ 08102


Wavelength division multiplexing is a promising approach to
utilize the enormous bandwidth of optical fiber and offers the
capability of building very large wide-area networks consisting of 
thousands of nodes with per-node throughputs in the 
gigabits-per-second range.

In a wavelength-division multiplexed (WDM) optical network, messages
are carried over non-interfering wavelength channels. To transmit or 
receive messages on a particular channel, an optical transmitter
or receiver must first be "tuned" to the channel's wavelength.
An important parameter in the design of such networks is the
tuning delay, which is the amount of time required for a transmitter 
and/or receiver to tune from one wavelength to another. Current WDM 
networks have large tuning delays, which can be in the order of 
milliseconds for transmitters/receivers with wide tuning ranges.
Consequently, algorithms for scheduling message transmissions 
in WDM networks must explicitly take into account the effect of 
tuning delay on performance.

This talk discusses the problem of scheduling message transmissions 
in WDM networks. Unlike previous work which assumes that all packets 
are known in advance (off-line scheduling), we consider the on-line 
case in which packets may arrive at any time. An on-line algorithm 
is presented that achieves a competitive ratio of 3 with respect to 
the optimal off-line algorithm. This talk also presents an improved 
algorithm for off-line scheduling. Specifically, for the case when 
there are two wavelength channels, an approximation algorithm is 
presented which is within a factor 1.4142136 of the optimal solution. 
The previously best known algorithm for this case has a performance
ratio of 2.

The talk concludes with several interesting open problems in
transmission scheduling for WDM optical networks.

===================================================================

Michael A. Palis is Associate Professor and Founding Chair of the 
Department of Computer Science, Rutgers University in 
Camden, New Jersey. He received the Ph.D. in Computer Science 
from the University of Minnesota. His research interests are in the
areas of high-performance computing, high-speed communications,
resource management and scheduling, and parallel and distributed
algorithms. He is currently on the editorial boards of the IEEE 
Transactions on Parallel and Distributed Systems and the Journal 
of Parallel and Distributed Computing. From 1993-1997, he served 
on the editorial board of the IEEE Transactions on Computers. He 
has also served on the program committees of numerous conferences
in parallel and distributed processing, including the recently
concluded 1998 Joint IPPS/SPDP Symposium and the forthcoming
ISPAN'99, in which he is Conference Vice-Chair. Dr. Palis a senior 
member of the IEEE, and member of the ACM and the New York 
Academy of Sciences.

Dr. Palis has held visiting appointments with industrial and 
government research laboratories, including the GE Aerospace 
Advanced Technology Laboratories in Moorestown, New Jersey 
(now part of Lockheed Martin) and the Army High Performance 
Computing Research Center (AHPCRC) in Minneapolis, Minnesota.