Delay stability of back-pressure policies in the presence of heavy-tailed traffic
We study scheduling and routing problems that arise in multi-hop wireline networks with a mix of heavy-tailed and light-tailed traffic. We analyze the delay performance of the widely studied class of Back-Pressure policies, known for their throughput optimality property, using as a performance crite...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/95984 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1826200722873516032 |
|---|---|
| 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 study scheduling and routing problems that arise in multi-hop wireline networks with a mix of heavy-tailed and light-tailed traffic. We analyze the delay performance of the widely studied class of Back-Pressure policies, known for their throughput optimality property, using as a performance criterion the notion of delay stability, i.e., whether the expected end-to-end delay in steady state is finite. First, by means of simple examples, we provide insights into how the network topology, the routing constraints, and the link capacities (relative to the arrival rates) may affect the delay stability of the Back-Pressure policy in the presence of heavy-tailed traffic. Next, we illustrate how fluid approximations facilitate the delay-stability analysis of multi-hop networks with heavy-tailed traffic. This approach allows us to derive analytical results that would have been hard to obtain otherwise, and also to build a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions. Finally, we show how one can achieve optimal performance, with respect to the delay stability criterion, by using a parameterized version of the Back-Pressure policy. |
| first_indexed | 2024-09-23T11:40:48Z |
| format | Article |
| id | mit-1721.1/95984 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:40:48Z |
| publishDate | 2015 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/959842022-10-01T05:12:24Z Delay stability of back-pressure policies in the presence of heavy-tailed traffic Markakis, Mihalis G. Tsitsiklis, John N. Modiano, Eytan H. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tsitsiklis, John N. Tsitsiklis, John N. Modiano, Eytan H. We study scheduling and routing problems that arise in multi-hop wireline networks with a mix of heavy-tailed and light-tailed traffic. We analyze the delay performance of the widely studied class of Back-Pressure policies, known for their throughput optimality property, using as a performance criterion the notion of delay stability, i.e., whether the expected end-to-end delay in steady state is finite. First, by means of simple examples, we provide insights into how the network topology, the routing constraints, and the link capacities (relative to the arrival rates) may affect the delay stability of the Back-Pressure policy in the presence of heavy-tailed traffic. Next, we illustrate how fluid approximations facilitate the delay-stability analysis of multi-hop networks with heavy-tailed traffic. This approach allows us to derive analytical results that would have been hard to obtain otherwise, and also to build a Bottleneck Identification algorithm, which identifies (some) delay unstable queues by solving the fluid model of the network from certain initial conditions. Finally, we show how one can achieve optimal performance, with respect to the delay stability criterion, by using a parameterized version of the Back-Pressure policy. National Science Foundation (U.S.) (Grant CNS-1217048) National Science Foundation (U.S.) (Grant CCF-0728554) National Science Foundation (U.S.) (CMMI-1234062) United States. Office of Naval Research (Grant N00014-12-1-0064) United States. Army Research Office. Multidisciplinary University Research Initiative (Grant W911NF-08-1-0238) 2015-03-12T16:25:19Z 2015-03-12T16:25:19Z 2014-02 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-3589-5 http://hdl.handle.net/1721.1/95984 Markakis, Mihalis G., Eytan Modiano, and John N. Tsitsiklis. “Delay Stability of Back-Pressure Policies in the Presence of Heavy-Tailed Traffic.” 2014 Information Theory and Applications Workshop (ITA) (February 2014). https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1109/ITA.2014.6804223 Proceedings of the 2014 Information Theory and Applications Workshop (ITA) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Tsitsiklis, John N. via Chris Sherratt |
| spellingShingle | Markakis, Mihalis G. Tsitsiklis, John N. Modiano, Eytan H. Delay stability of back-pressure policies in the presence of heavy-tailed traffic |
| title | Delay stability of back-pressure policies in the presence of heavy-tailed traffic |
| title_full | Delay stability of back-pressure policies in the presence of heavy-tailed traffic |
| title_fullStr | Delay stability of back-pressure policies in the presence of heavy-tailed traffic |
| title_full_unstemmed | Delay stability of back-pressure policies in the presence of heavy-tailed traffic |
| title_short | Delay stability of back-pressure policies in the presence of heavy-tailed traffic |
| title_sort | delay stability of back pressure policies in the presence of heavy tailed traffic |
| url | http://hdl.handle.net/1721.1/95984 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT markakismihalisg delaystabilityofbackpressurepoliciesinthepresenceofheavytailedtraffic AT tsitsiklisjohnn delaystabilityofbackpressurepoliciesinthepresenceofheavytailedtraffic AT modianoeytanh delaystabilityofbackpressurepoliciesinthepresenceofheavytailedtraffic |