M.Sc Thesis

M.Sc StudentAsory Michal
SubjectOptimal Control of Queues In Asymptotic Regimes via
Minimality of the Skorokhod
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Rami Atar
Full Thesis textFull thesis text - English Version


This thesis deals with the minimality property of the multi-dimensional Skorokhod map and its use in solving queueing optimization problems.

We consider an open queuing network that consists of several servers with finite buffers. The routing is stochastic and the customers are homogeneous in terms of service time, arrival distribution and routing at each server. As assumed in many works dealing with queuing network models, the arrival processes are Poisson and the service times are exponential (as in a Jackson network). The idle times of the servers are controlled in order to avoid buffer overflow. This can be viewed as controlling the exit time from bounded set defined by the buffer sizes.

We observe the queueing system at the moderate deviation scale and use known results on moderate deviation principle for the Poisson processes namely the arrival and potential service. By earlier results it is to be expected that this model considered under the risk sensitive cost, will give rise to a differential game in the moderate deviation limits (However we do not prove this convergence but rather we analyze the game). A condition that we require in order to solve the problem is that each server is fed by at most one server. According to the policy that each server continues to serve as long as its buffer is not empty and all buffers which are fed by it are not full, a corresponding Skorokhod problem arises.

Our main result shows that the minimal control path is also the optimal one and it solves the specified Skorokhod problem. We worked at the moderate deviation regime but the result is also relevant to the heavy traffic regime.