Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization
Lyapunov drift is a powerful tool for optimizing stochastic queueing networks subject to stability. However, the most convenient drift conditions often provide results in terms of a time average expectation, rather than a pure time average. This paper provides an extended drift-plus-penalty result t...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/831909 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832567685187108864 |
|---|---|
| author | Michael J. Neely |
| author_facet | Michael J. Neely |
| author_sort | Michael J. Neely |
| collection | DOAJ |
| description | Lyapunov drift is a powerful tool for optimizing stochastic queueing networks subject to stability. However, the most convenient drift conditions often provide results in terms of a time average expectation, rather than a pure time average. This paper provides an extended drift-plus-penalty result that ensures stability with desired time averages with probability 1. The analysis uses the law of large numbers for martingale differences. This is applied to quadratic and subquadratic Lyapunov methods for minimizing the time average of a network penalty function subject to stability and to additional time average constraints. Similar to known results for time average expectations, this paper shows that pure time average penalties can be pushed arbitrarily close to optimality, with a corresponding tradeoff in average queue size. Further, in the special case of quadratic Lyapunov functions, the basic drift condition is shown to imply all major forms of queue stability. |
| format | Article |
| id | doaj-art-c9766bfaf3834cb5a95779a8dfb97ad0 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-c9766bfaf3834cb5a95779a8dfb97ad02025-02-03T01:00:54ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/831909831909Stability and Probability 1 Convergence for Queueing Networks via Lyapunov OptimizationMichael J. Neely0Electrical Engineering Department, University of Southern California, 3740 McClintock Avenue, Room 500, Los Angeles, CA 90089-2565, USALyapunov drift is a powerful tool for optimizing stochastic queueing networks subject to stability. However, the most convenient drift conditions often provide results in terms of a time average expectation, rather than a pure time average. This paper provides an extended drift-plus-penalty result that ensures stability with desired time averages with probability 1. The analysis uses the law of large numbers for martingale differences. This is applied to quadratic and subquadratic Lyapunov methods for minimizing the time average of a network penalty function subject to stability and to additional time average constraints. Similar to known results for time average expectations, this paper shows that pure time average penalties can be pushed arbitrarily close to optimality, with a corresponding tradeoff in average queue size. Further, in the special case of quadratic Lyapunov functions, the basic drift condition is shown to imply all major forms of queue stability.http://dx.doi.org/10.1155/2012/831909 |
| spellingShingle | Michael J. Neely Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization Journal of Applied Mathematics |
| title | Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization |
| title_full | Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization |
| title_fullStr | Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization |
| title_full_unstemmed | Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization |
| title_short | Stability and Probability 1 Convergence for Queueing Networks via Lyapunov Optimization |
| title_sort | stability and probability 1 convergence for queueing networks via lyapunov optimization |
| url | http://dx.doi.org/10.1155/2012/831909 |
| work_keys_str_mv | AT michaeljneely stabilityandprobability1convergenceforqueueingnetworksvialyapunovoptimization |