Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic
We consider the problem of scheduling in a single-hop switched network with a mix of heavy-tailed and light-tailed traffic and analyze the impact of heavy-tailed traffic on the performance of Max-Weight scheduling. As a performance metric, we use the delay stability of traffic flows: A traffic flow...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115167 https://orcid.org/0000-0003-1469-7729 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1826211476110573568 |
|---|---|
| author | Markakis, Michail Modiano, Eytan H Tsitsiklis, John N |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Markakis, Michail Modiano, Eytan H Tsitsiklis, John N |
| author_sort | Markakis, Michail |
| collection | MIT |
| description | We consider the problem of scheduling in a single-hop switched network with a mix of heavy-tailed and light-tailed traffic and analyze the impact of heavy-tailed traffic on the performance of Max-Weight scheduling. As a performance metric, we use the delay stability of traffic flows: A traffic flow is delay-stable if its expected steady-state delay is finite, and delay-unstable otherwise. First, we show that a heavy-tailed traffic flow is delay-unstable under any scheduling policy. Then, we focus on the celebrated Max-Weight scheduling policy and show that a light-tailed flow that conflicts with a heavy-tailed flow is also delay-unstable. This is true irrespective of the rate or the tail distribution of the light-tailed flow or other scheduling constraints in the network. Surprisingly, we show that a light-tailed flow can become delay-unstable, even when it does not conflict with heavy-tailed traffic. Delay stability in this case may depend on the rate of the light-tailed flow. Finally, we turn our attention to the class of Max-Weight-α scheduling policies. We show that if the α-parameters are chosen suitably, then the sum of the α-moments of the steady-state queue lengths is finite. We provide an explicit upper bound for the latter quantity, from which we derive results related to the delay stability of traffic flows, and the scaling of moments of steady-state queue lengths with traffic intensity. |
| first_indexed | 2024-09-23T15:06:32Z |
| format | Article |
| id | mit-1721.1/115167 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:06:32Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1151672022-10-02T00:37:43Z Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic Markakis, Michail Modiano, Eytan H Tsitsiklis, John N Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Markakis, Michail Modiano, Eytan H Tsitsiklis, John N We consider the problem of scheduling in a single-hop switched network with a mix of heavy-tailed and light-tailed traffic and analyze the impact of heavy-tailed traffic on the performance of Max-Weight scheduling. As a performance metric, we use the delay stability of traffic flows: A traffic flow is delay-stable if its expected steady-state delay is finite, and delay-unstable otherwise. First, we show that a heavy-tailed traffic flow is delay-unstable under any scheduling policy. Then, we focus on the celebrated Max-Weight scheduling policy and show that a light-tailed flow that conflicts with a heavy-tailed flow is also delay-unstable. This is true irrespective of the rate or the tail distribution of the light-tailed flow or other scheduling constraints in the network. Surprisingly, we show that a light-tailed flow can become delay-unstable, even when it does not conflict with heavy-tailed traffic. Delay stability in this case may depend on the rate of the light-tailed flow. Finally, we turn our attention to the class of Max-Weight-α scheduling policies. We show that if the α-parameters are chosen suitably, then the sum of the α-moments of the steady-state queue lengths is finite. We provide an explicit upper bound for the latter quantity, from which we derive results related to the delay stability of traffic flows, and the scaling of moments of steady-state queue lengths with traffic intensity. National Science Foundation (U.S.) (Grant CNS-0915988) National Science Foundation (U.S.) (Grant CCF-0728554) United States. Air Force. Office of Scientific Research. Multidisciplinary University Research Initiative (Grant W911NF-08- 1-0238) 2018-05-02T16:44:42Z 2018-05-02T16:44:42Z 2013-03 2018-04-06T11:49:14Z Article http://purl.org/eprint/type/JournalArticle 1063-6692 1558-2566 http://hdl.handle.net/1721.1/115167 Markakis, Mihalis G., et al. “Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic.” IEEE/ACM Transactions on Networking, vol. 22, no. 1, Feb. 2014, pp. 257–70. https://orcid.org/0000-0003-1469-7729 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 http://dx.doi.org/10.1109/TNET.2013.2246869 IEEE/ACM Transactions on Networking Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Markakis, Michail Modiano, Eytan H Tsitsiklis, John N Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic |
| title | Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic |
| title_full | Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic |
| title_fullStr | Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic |
| title_full_unstemmed | Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic |
| title_short | Max-Weight Scheduling in Queueing Networks With Heavy-Tailed Traffic |
| title_sort | max weight scheduling in queueing networks with heavy tailed traffic |
| url | http://hdl.handle.net/1721.1/115167 https://orcid.org/0000-0003-1469-7729 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT markakismichail maxweightschedulinginqueueingnetworkswithheavytailedtraffic AT modianoeytanh maxweightschedulinginqueueingnetworkswithheavytailedtraffic AT tsitsiklisjohnn maxweightschedulinginqueueingnetworkswithheavytailedtraffic |