The Classical Occupancy Problem and the Dimensioning of Wavelength Converters for an Optical Packet Switch

Bell Laboratories
Lucent Technologies
700 Mountain Av.
Murray Hill, NJ 07974-0636

Friday, March 1st, 3:00 PM, ENS 637

Abstract

Urn models find wide application in computer science, engineering, biology, physics and statistics. One of the most well known is the classical occupancy problem, in which there are n urns and r balls and the problem is to determine the distribution of empty urns with the balls being thrown independently and at random (see Probability Theory and its Applications, Volume 1 W.Feller, Urn Models and their Applications, Johnson and Kotz.) In this talk we show that this problem arises in the dimensioning of a proposed optical packet switch which uses a pool of wavelength converters to reduce contention between packets at the fiber output.

The switch operates by providing wavelength converters as a pool at an extended switch output which allows packets to be redirected to their destination fiber after conversion. In this way contention between packets with the same wavelength and output fiber is reduced whilst a limited number of converters are used. The switch consists of passive optical devices, the core component being a space switch which interconnects the input and output ports (fiber, frequency). Further ports on the space switch are used to allow access to a pool of fully tuneable wavelength converters (any wavelength to any wavelength). They need to be rapidly tunable for this application. Control is effected by bleeding optical power from incoming packets, which data is used to set up the space switch and tune the input/output wavelengths of the converters.

Packet losses as low as 10^{-10} (or lower) may be required in such a switch and exhaustion of the wavelength converter pool is a primary contribution to this loss. As we show an urn model allows us to evaluate this probability. ``Exact methods'' for obtaining it, however, can prove numerically intractable because of rounding error and the need for taking the convolution of the converter requirements over the wavelengths being used by the switch. Large deviations represents an alternative approach and, as we show, the rate function for classical occupancy can be obtained directly from a sum of independent (but not identically distributed) geometric random variables. Determination of the exponent for converter exhaustion then leads to a tradeoff between the component for packets being routed to fewer fibers than average and the component for an above average number of arrivals. This then allows an asymptotic upper bound on packet loss to be obtained as we describe. Numerical results are presented to illustrate the accuracy of the approximations and extensions to the dimensioning problem are discussed.

Biography

Phil Whiting received his BA degree from the University of Oxford, his MSc from the University of London and his Ph. D. was in queuing theory from the University of Strathclyde. After a post-doc at the University of Cambridge, Phil's interests centered on wireless. In 1993 Phil participated in the Telstra trial of Qualcomm CDMA in South Eastern Australia. He then joined the Mobile Research Center at the University of South Australia Adelaide. Since 1997 he has been with Bell Labs.

His main interests are the mathematics of wireless networks, particularly stochastic models for resource allocation and information theory. Phil's current research include large deviations asymptotics for balls and urns models (with no wireless applications found yet!) and the application of stochastic control to scheduling in wireless data networks.

A list of Telecommunications and Signal Processing Seminars is available at from the ECE department Web pages under "Seminars". The Web address for the Telecommunications and Signal Processing Seminars is http://signal.ece.utexas.edu/seminars