A Scheduling Algorithm For HDR/CDMA: The Exponential Rule

Electrical Engineering
University of Illinois at Urbana-Champaign

Thursday, April 4th, 11:00 AM, ENS 637

shakkott@comm.csl.uiuc.edu

Abstract

High Data Rate (HDR) technology has recently been proposed as a time division overlay to CDMA as a means of providing downlink packet data service to mobile users. In such a wireless system, each user has a time-varying channel, and the channel for each user is possibly different. From a networking perspective, the key feature of HDR technology is the availability of the channel-state to the scheduler at the base-station.

In this talk, we present a channel-state dependent, packet-scheduling algorithm called the exponential rule. We study its performance with respect to packet delays as well as average throughput. Simulations show that this algorithm compares favorably with various other scheduling algorithms.

Finally, using analytical techniques such as fluid limits and diffusion approximations, we show that this algorithm has several interesting properties such as throughput-optimality (i.e., this algorithm has the largest stability region) and path-wise optimality under a heavy traffic regime (i.e., it minimizes for each time, the maximum queue-length among the user queues at the base-station).

Biography

Sanjay Shakkottai received the Master of Engineering degree from the Indian Institute of Science in 1998, and a Ph.D. in Electrical Engineering from the University of Illinois at Urbana-Champaign in January 2002. He received the Samsung scholarship for graduate studies at the Indian Institute of Science, and the Nokia research scholarship as well as the Tellabs fellowship for graduate studies at the University of Illinois. He spent the summer of 2000 in the Mathematical Sciences Research Center at Bell Labs Lucent Technologies, Murray Hill, NJ.

His current research interests include congestion control in the Internet, scheduling and QoS for wireless and ad-hoc networks, and resource allocation for heterogeneous 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