*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Resource Allocation Algorithms in Stochastic Systems
Advisor: Dr. Ton Dieker
Committee members:
Dr. David Goldberg
Dr. Steve Hackman
Dr. Arkadi Nemirovski
Dr. Jinwoo Shin (School of Electric Engineering, Korea Advanced Institute of Science and Technology)
Location: Groseclose 402
Date and Time: Friday, November 11, 10:00 AM
Summary:
My dissertation work examines resource allocation algorithms in stochastic systems. I use applied probability methodology to investigate large-scaled stochastic systems. Specifically, my research focuses on proposing and analyzing stochastic algorithms in large systems. A brief outline is below.
The first topic is randomized scheduling in a many-buffer regime. The goal of this research is to analyze the performance of the randomized longest-queue-first scheduling algorithm in parallel-queueing systems. Our model consists of n buffers and a server. Tasks arrive to each buffer independently and have independent and identically distributed (i.i.d.) exponential service requirements. To complete the description of the model, we need to specify a scheduling algorithm for determining how and when the server allocates service to tasks. We are interested in the asymptotic regime n goes to infinity and networks with a large number of buffers are related to mean-field models in physics. This asymptotic regime could be called the many-buffer regime. In this research task, we aim to investigate the influence of the scheduling algorithms on quality of service in the many-buffer regime.
Second, we propose a low-complexity and high-performance scheduling scheme in constrained queueing networks. Scheduling of resources among various entities con- tending for their access is one of the fundamental problems in operations research and our goal is to design a scheduling algorithm with high performance and low complexity for large-scale networks. In the network we are interested in, packets arrive at buffers and packets in buffers are served according to interference restrictions. Since Tassiulas and Ephremides proposed the maximum weight algorithm of through-put optimality, extensive research efforts have been expended for mitigating its high complexity by studying various types of scheduling algorithms. In this research, we develop a generic framework to design scheduling algorithms of high throughput and low complexity. Our algorithm updates current schedules under the interactions with a given oracle system which solves a combinatorial optimization problem in a finite number of steps. Our algorithm using any such oracle is throughput optimal for general combinatorial resource allocation problems including wireless networks and input queued switch networks.
