On deciding stability of constrained random walks and queueing systems
Authors: Gamarnik David 
Published: January 2007

We consider in this paper two types of queueing systems which
operate under a specific and fixed scheduling policy. The first
system consists of a single server and several buffers in which
arriving jobs are stored. We assume that arriving parts may require
several stages of processing in which case each stage corresponds
to a different buffer. The second system is a communication type
queueing network given by a graph. The arriving jobs (packets)
request a simple path along which they need to be processed. In
both models the jobs arrive in a completely deterministic fashion:
the interarrival times are fixed and known. All the processing
times are also deterministic. A scheduling policy specifies a rule
using which arriving parts are processed in the queueing
system.
A scheduling policy is defined to be stable if there is a finite
uniform upper bound on the total number of parts in the system at
all times. A necessary condition for stability of any work
conserving policy is that the traffic intensity of the station (of
each link in the graph in the communication model) is not bigger
than one. Many results have demonstrated that this condition is not
sufficient for stability. The results were obtained primarily in
the context of stochastic networks ([24],[20],[5],[6],[10]),
deterministic fluid networks ([6],[9],[7],[8],[2]), deterministic
adversarial networks ([4],[1],[14],[12]).
One of the earliest result in the area were obtained by Rybko
and Stolyar [24] and Lu and Kumar [20]. They showed that a simple
priority policy can lead to instability in some queueing networks.
Bramson [5] and Seidman [25] showed that even FIFO policy can be
unstable in stochastic networks. Instability of FIFO was later
demonstrated in an adversarial queueing setting by Andrews et. al.
[1]. Dai [6] established that stability of a fluid deterministic
queueing network implies stability of a stochastic queueing
network. A similar result was established by Gamarnik [12], which
connects stability of fluid and adversarial queueing networks. A
complete characterization of two-station fluid networks which are
stable under any work conserving policy was established by
Bertsimas, Gamarnik and Tsitsiklis [2] and Dai and Vande Vate [7].
Goel [14] constructed a complete characterization of adversarial
queueing networks which are stable under the usual load condition.
The result is extended by Gamarnik [13].

Motivated by a queueing network model stability of homogeneous
random walks in a nonnegative orthant was considered in several
papers: Malyshev [21], Menshikov [23], Fayolle [11], Ignatyuk and
Malyshev [18], Malyshev [22]. Such random walks
Q
(
t
),
t
= 0, 1, 2,¡­ have
Z
+

d

as a state space
(
Z
+
is the set of nonnegative integers). The
transition vectors ¦¤ have deterministically bounded
length in max norm and the transition probability
p
(¦«, ¦¤) along the direction
¦¤ depends only on the face ¦« that the
random walk is currently on (the transition probabilities depend
only on which coordinates of the current state are positive and
which are zero). Such a random walk is defined to be stable if it
is positive recurrent. We will also consider deterministic walks,
for which
p
(¦«, ¦¤) is always
zero or one (the transition deterministically depends on the face
that the walk is currently on).

A complete characterization of stable homogeneous random walks
in
Z
+

d

for
d
¡Ü 4 was obtained in Malyshev [21], Menshikov [23] and
Ignatyuk and Malyshev [18], but no extension of this classification
to higher dimensions has been obtained. Malyshev in [22]
establishes a connection between homogeneous random walks and
general dynamical systems on compact manifolds and shows that the
difficulty of classifying stable random walks is of the same nature
as the difficulty of understanding the dynamics of these dynamical
systems. Specifically, the complicated dynamics precludes obtaining
classification of stable random walks for
d
= 5.

Thus despite many efforts the classification of stable random
walks for general dimensions is not known. Likewise classification
of stable policies in queueing systems is an open problem.