Try our Free Online Math Solver!

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 noni.i.d. case is given in
Section 4.4 of the text using the idea of
Tslot 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 onestep conditional Lyapunov drift as follows:
Theorem 2: (Lyapunov Drift) Suppose that U(t) evolves
according to some probability law , and suppose there
exists a nonnegative 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 multihop
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 multihop mobile networks in [6]. Nonquadratic
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
crosslayer control in wireless networks. Foundations and Trends
in Networking, vol. 1, no. 1, pp. 1149, 2006.
[2] M. J. Neely. Energy optimal control for time varying wireless networks. IEEE
Transactions on Information Theory, vol. 52, no. 7, pp.
29152934, 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. 19361949, 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. 466478, March 1993.
[5] E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan. Bounds on average
delays and queue size averages and variances in
inputqueued cellbased 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. 89103, 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. 10211045, Dec. 2004.
[9] M. J. Neely. Superfast 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. 14891501, 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 multiuser
wireless uplinks and downlinks. Proc. of Allerton Conf.
on Communication, Control, and Computing (invited paper), Sept. 2006.
Prev  Next 