Stability and Approximation of Queueing Networks

Antonios Dimakis

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-131
October 16, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-131.pdf

Motivated by applications in communication networks, we consider three different models of resource sharing.

We first study the stability of Longest Queue First (LQF), a greedy and low complexity scheduling policy, encountered in packet switching and wireless networks. Contrary to other common policies, the stability of LQF depends on the variance of the arrival processes in addition to their intensities. We identify new sufficient conditions for LQF to be throughput optimal for i.i.d. arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize it in this case. We combine properties of the sample paths over different time-scales to obtain a sharper characterization.

The second part is motivated by the presence of variations in channel quality and traffic demand. For a stable Markov chain whose transition matrix is controlled by a general stationary jump process, we provide a framework for approximating the stationary distribution, similar to the constant and linear terms obtained by singular perturbation analysis (SPA). However, SPA is only applicable to Markovian controlling processes. To extend to the non-Markovian case, we follow a non-algebraic approach based on light-traffic analysis of stationary point processes. Jackson networks with slowly varying service and arrival rates and fixed routing are dealt with in this framework.

In the third part, we consider the congestion arising from coexistence of data and voice flows in a single internet link. Voice flows are rejected and leave the system if on arrival, the total number of flows is above a certain threshold. We obtain deterministic equations describing the population dynamics for each type of flow. These equations arise as the limit of a large stochastic system. Next, we study the behavior near the voice cut-off threshold. While there is no "hard" boundary as in a purely loss system, admissions and rejections of voice flows result in a similar averaging along a "soft" boundary, where temporary overloads are possible during transient periods.

Advisor: Jean Walrand


BibTeX citation:

@phdthesis{Dimakis:EECS-2006-131,
    Author = {Dimakis, Antonios},
    Title = {Stability and Approximation of Queueing Networks},
    School = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-131.html},
    Number = {UCB/EECS-2006-131},
    Abstract = {Motivated by applications in communication networks, we consider three different models of resource sharing.

We first study the stability of Longest Queue First (LQF), a greedy and low complexity scheduling policy, encountered in packet switching and wireless networks. Contrary to other common policies, the stability of LQF depends on the variance of the arrival processes in addition to their intensities. We identify new sufficient conditions for LQF to be throughput optimal for i.i.d. arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize it in this case. We combine properties of the sample paths over different time-scales to obtain a sharper characterization.

The second part is motivated by the presence of variations in channel quality and traffic demand. For a stable Markov chain whose transition matrix is controlled by a general stationary jump process, we provide a framework for approximating the stationary distribution, similar to the constant and linear terms obtained by singular perturbation analysis (SPA). However, SPA is only applicable to Markovian controlling processes. To extend to the non-Markovian case, we follow a non-algebraic approach based on light-traffic analysis of stationary point processes. Jackson networks with slowly varying service and arrival rates and fixed routing are dealt with in this framework.

In the third part, we consider the congestion arising from coexistence of data and voice flows in a single internet link. Voice flows are rejected and leave the system if on arrival, the total number of flows is above a certain threshold. We obtain deterministic equations describing the population dynamics for each type of flow. These equations arise as the limit of a large stochastic system. Next, we study the behavior near the voice cut-off threshold. While there is no "hard" boundary as in a purely loss system, admissions and rejections of voice flows result in a similar averaging along a "soft" boundary, where temporary overloads are possible during transient periods.}
}

EndNote citation:

%0 Thesis
%A Dimakis, Antonios
%T Stability and Approximation of Queueing Networks
%I EECS Department, University of California, Berkeley
%D 2006
%8 October 16
%@ UCB/EECS-2006-131
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-131.html
%F Dimakis:EECS-2006-131