# Summary of Results for First 3 Lectures

We have followed Section 3.1 and 4.4 of the text [1].

I. DISCRETE TIME QUEUES AND STABILITY (SECTION 3.1 OF TEXT)

A. Discrete Time Queues

One- Step Dynamic Equation for Discrete Time Queues:

Sample path inequality :

B. Strong Stability

Definition 1: A discrete time queue with backlog process U(t) is strongly stable
if:

Definition 2: A network of discrete time queues is strongly stable if all
individual queues are strongly stable.

Lemma 1: Suppose that for all t (for
some finite bound ). Then if U(t) is strongly
stable, we

have:

Proof: The proof is beyond the scope of this course. The
interested reader can find the proof in the appendix

of [2].

We had definitions of and A(t) being
admissible with rates and
, respectively (given in Section 3.1 of

text). The assumption is part of
admissibility, and will be assumed to hold throughout this course.

Note that if is an i.i.d. sequence with a
bounded , then it is admissible. Likewise, if
is

an i.i.d. sequence with bounded first and second moments, then it is admissible.

Theorem 1: (Stability Theorem) If A(t) is admissible with rate
and is
admissible with rate , then:

(a) Strong Stability implies that (and
so is necessary for strong stability).

(b) implies strong stability (and so
is sufficient for strong stability).

Note there is a "singularity" between necessity and sufficiency for
. In this case, there are examples where

the queue is strongly stable, and there are other examples where the queue is
not strongly stable.

Proof: The proof of part (a) uses (2) together with the fact that (3) holds for
strongly stable queues. You are

expected to know the proof.

The proof of (b) was done in class for the i.i.d. case, using Lyapunov drift
theory. You are also expected to know

the proof for this i.i.d. case. The proof for the non-i.i.d. case is given in
Section 4.4 of the text using the idea of

T-slot Lyapunov drift.

Note that throughout this course we shall use the term "stability" to refer to
strong stability.

II. LYAPUNOV DRIFT (SECTION 4.4 OF TEXT)

Let represent a vector process of queue
backlogs that evolve in discrete time

. Let L(U) represent a non- negative function ,
called a Lyapunov function, of the queue backlog

vector. Define the one-step conditional Lyapunov drift as follows:

Theorem 2: (Lyapunov Drift) Suppose that U(t) evolves
according to some probability law , and suppose there

exists a non-negative function L(U) and constants B < ∞ and ε > 0 such that
for all timeslots t and all possible

values of U (t), we have:

Then the queueing network is strongly stable (i.e., all queues are strongly
stable), and:

Proof: You are expected to know the proof. The proof uses 2 main concepts:

1) Iterated Expectations:

2) Telescoping Sums :

A typical Lyapunov function that is very useful is the following quadratic
function :

A fact that is often useful in dealing with quadratic
Lyapunov functions: If then:

This fact is used together with the Lyapunov Drift Theorem to prove part (b) of
Theorem 1.

III. SOME COMMENTS ABOUT LYAPUNOV FUNCTIONS, DELAY, AND COMPLEXITY

Lyapunov drift for network stability is first used in [3] for multi-hop
networks, and in [4] for opportunistic

downlink scheduling. Related quadratic Lyapunov functions are used to make
stability and delay claims for N × N

packet switches in [5] and for multi-hop mobile networks in [6]. Non-quadratic
Lyapunov functions can sometimes

be used to make modified or improved statements about delay [7] [8] [9].
Alternative Lyapunov functions via queue

groupings can often lead to improved complexity and/or delay bounds, see [10]
[11] [12] [13].

Performance optimal Lyapunov networking will be a large part of this course and
will likely be useful for your

projects. However, we will not get to this for another few weeks. Students can
always read ahead in the text, and

are also referred to [2] for a writeup that emphasizes average power
minimization and virtual power queues, which

is not covered in as much detail in the text.

REFERENCES

[1] L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource allocation and
cross-layer control in wireless networks. Foundations and Trends

in Networking, vol. 1, no. 1, pp. 1-149, 2006.

[2] M. J. Neely. Energy optimal control for time varying wireless networks. IEEE
Transactions on Information Theory, vol. 52, no. 7, pp.

2915-2934, July 2006.

[3] L. Tassiulas and A. Ephremides. Stability properties of constrained queueing
systems and scheduling policies for maximum throughput

in multihop radio networks. IEEE Transacations on Automatic Control, vol. 37,
no. 12, pp. 1936-1949, Dec. 1992.

[4] L. Tassiulas and A. Ephremides. Dynamic server allocation to parallel queues
with randomly varying connectivity. IEEE Transactions

on Information Theory, vol. 39, pp. 466-478, March 1993.

[5] E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan. Bounds on average
delays and queue size averages and variances in

input-queued cell-based switches. Proc. IEEE INFOCOM, 2001.

[6] M. J. Neely, E. Modiano, and C. E Rohrs. Dynamic power allocation and
routing for time varying wireless networks. IEEE Journal

on Selected Areas in Communications, vol. 23, no. 1, pp. 89-103, January 2005.

[7] N. Kahale and P. E. Wright. Dynamic global packet routing in wireless
networks. Proc. IEEE INFOCOM, 1997.

[8] S. Shakkottai, R. Srikant, and A. Stolyar. Pathwise optimality of the
exponential scheduling rule for wireless channels. Advances in

Applied Probability, vol. 36, no. 4, pp. 1021-1045, Dec. 2004.

[9] M. J. Neely. Super-fast delay tradeoffs for utility optimal fair scheduling
in wireless networks. IEEE Journal on Selected Areas in

Communications, Special Issue on Nonlinear Optimization of Communication
Systems , vol. 24, no. 8, pp. 1489-1501, Aug. 2006.

[10] X. Wu, R. Srikant, and J. R. Perkins. Scheduling efficiency of distributed
greedy scheduling algorithms in wireless networks. IEEE

Transactions on Mobile Computing, June 2007.

[11] S. Deb, D. Shah, and S. Shakkottai. Fast matching algorithms for repetitive
optimization: An application to switch scheduling. Proc.

of 40th Annual Conference on Information Sciences and Systems (CISS), Princeton,
NJ, March 2006.

[12] M. J. Neely. Delay analysis for maximal scheduling in wireless networks
with bursty traffic. Proc. IEEE INFOCOM, April 2008.

[13] M. J. Neely. Order optimal delay for opportunistic scheduling in multi-user
wireless uplinks and downlinks. Proc. of Allerton Conf.

on Communication, Control, and Computing (invited paper), Sept. 2006.

Prev | Next |