Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations
We consider a single-hop switched queueing network with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and light-tailed traffic, and study the delay performance of the Max-Weight policy, known for its throughput optimality and asymptotic delay optimality properties. Classical...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114642 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826199932625747968 |
|---|---|
| author | Markakis, Mihalis G. Tsitsiklis, John N. Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Markakis, Mihalis G. Tsitsiklis, John N. Modiano, Eytan H |
| author_sort | Markakis, Mihalis G. |
| collection | MIT |
| description | We consider a single-hop switched queueing network with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and light-tailed traffic, and study the delay performance of the Max-Weight policy, known for its throughput optimality and asymptotic delay optimality properties. Classical results in queueing theory imply that heavy-tailed queues are delay unstable, i.e., they experience infinite expected delays in steady state. Thus, we focus on the impact of heavy-tailed traffic on the light-tailed queues, using delay stability as performance metric. Recent work has shown that this impact may come in the form of subtle rate-dependent phenomena, the stochastic analysis of which is quite cumbersome. Our goal is to show how fluid approximations can facilitate the delay analysis of the Max-Weight policy under heavy-tailed traffic. More specifically, we show how fluid approximations can be combined with renewal theory in order to prove delay instability results. Furthermore, we show how fluid approximations can be combined with stochastic Lyapunov theory in order to prove delay stability results. We illustrate the benefits of the proposed approach in two ways: (i) analytically, by providing a sharp characterization of the delay stability regions of networks with disjoint schedules, significantly generalizing previous results; (ii) computationally, through a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions. |
| first_indexed | 2024-09-23T11:28:06Z |
| format | Article |
| id | mit-1721.1/114642 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:28:06Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | mit-1721.1/1146422022-09-27T19:45:52Z Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations Markakis, Mihalis G. Tsitsiklis, John N. Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Modiano, Eytan H We consider a single-hop switched queueing network with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and light-tailed traffic, and study the delay performance of the Max-Weight policy, known for its throughput optimality and asymptotic delay optimality properties. Classical results in queueing theory imply that heavy-tailed queues are delay unstable, i.e., they experience infinite expected delays in steady state. Thus, we focus on the impact of heavy-tailed traffic on the light-tailed queues, using delay stability as performance metric. Recent work has shown that this impact may come in the form of subtle rate-dependent phenomena, the stochastic analysis of which is quite cumbersome. Our goal is to show how fluid approximations can facilitate the delay analysis of the Max-Weight policy under heavy-tailed traffic. More specifically, we show how fluid approximations can be combined with renewal theory in order to prove delay instability results. Furthermore, we show how fluid approximations can be combined with stochastic Lyapunov theory in order to prove delay stability results. We illustrate the benefits of the proposed approach in two ways: (i) analytically, by providing a sharp characterization of the delay stability regions of networks with disjoint schedules, significantly generalizing previous results; (ii) computationally, through a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions. 2018-04-09T19:51:28Z 2018-04-09T19:51:28Z 2018-04-09 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-3410-2 978-1-4799-3409-6 http://hdl.handle.net/1721.1/114642 Markakis, Mihalis G., et al. "Delay Analysis of the Max-Weight Policy under Heavy-Tailed Traffic via Fluid Approximations." 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2-4 October, 2013, Monticello, Illinois, IEEE, 2013, pp. 436–44. https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/Allerton.2013.6736557 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Prof. Modiano |
| spellingShingle | Markakis, Mihalis G. Tsitsiklis, John N. Modiano, Eytan H Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations |
| title | Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations |
| title_full | Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations |
| title_fullStr | Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations |
| title_full_unstemmed | Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations |
| title_short | Delay analysis of the Max-Weight policy under heavy-tailed traffic via fluid approximations |
| title_sort | delay analysis of the max weight policy under heavy tailed traffic via fluid approximations |
| url | http://hdl.handle.net/1721.1/114642 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT markakismihalisg delayanalysisofthemaxweightpolicyunderheavytailedtrafficviafluidapproximations AT tsitsiklisjohnn delayanalysisofthemaxweightpolicyunderheavytailedtrafficviafluidapproximations AT modianoeytanh delayanalysisofthemaxweightpolicyunderheavytailedtrafficviafluidapproximations |