Scheduling in Parallel Queues with Randomly Varying Connectivity and Switchover Delay

Abstract:

We consider a dynamic server control problem for two parallel queues with randomly varying connectivity and server switchover delay between the queues. At each time slot the server decides either to stay with the current queue or switch to the other queue based on the current connectivity and the queue length information. The introduction of switchover time is a new modeling component of this problem, which makes the problem much more challenging. We develop a novel approach to characterize the stability region of the system by using state-action frequencies, which are stationary solutions to a Markov Decision Process (MDP) formulation of the corresponding saturated system. We characterize the stability region explicitly in terms of the connectivity parameters and develop a frame-based dynamic control (FBDC) policy that is shown to be throughput-optimal. In fact, the FBDC policy provides a new framework for developing throughput-optimal network control policies using state-action frequencies. Furthermore, we develop simple Myopic policies that achieve more than 96% of the stability region. Finally, simulation results show that the Myopic policies may achieve the full stability region and are more delay efficient than the FBDC policy in most cases.

Biography:

Güner Celik is a Ph.D. student and research assistant in the Department of Electrical and Engineering and Computer Science (EECS) at Massachusetts Institure of Technology (MIT). He is working with Prof. Eytan Modiano at the Laboratory for Information and Decision Systems (LIDS). He received his M.S. degree in EECS from MIT in 2007 and his B.S. degree in Electrical and Electronics Engineering from the Middle East Technical University (METU), Ankara, Turkey with second highest ranking in 2005. In August 2010, he was a visiting researcher at Bell Labs in Mathematics of Networks and Complex Systems Research Group in NJ and in summer 2007, he joined Microsoft Research (MSR) Systems and Networking Group in Camrbidge, UK as a research intern. His research interests are in wireless network control, queuing theory and communication theory. In particular, he is currently working on scheduling, routing and resource allocation for network control and optimization, dynamic server scheduling in queuing systems and trajectory control for data gathering in mobile wireless networks.