Resource allocation algorithms in stochastic systems

Abstract

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.