Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic
We investigate the asymptotic behavior of the steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, an...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/66953 https://orcid.org/0000-0003-1469-7729 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1826193452539314176 |
|---|---|
| author | Jagannathan, Krishna Prasanna 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 Jagannathan, Krishna Prasanna Markakis, Michail Modiano, Eytan H. Tsitsiklis, John N. |
| author_sort | Jagannathan, Krishna Prasanna |
| collection | MIT |
| description | We investigate the asymptotic behavior of the steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-α scheduling policies, and derive an exact asymptotic characterization of the steady-state queue length distributions. In particular, we show that the tail of the light queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail of the light queue distribution, among all non-idling policies. Motivated by the above `negative' result regarding the max-weight-α policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail, while still being throughput optimal. |
| first_indexed | 2024-09-23T09:39:27Z |
| format | Article |
| id | mit-1721.1/66953 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:39:27Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/669532022-09-26T12:51:41Z Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic Jagannathan, Krishna Prasanna 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 Tsitsiklis, John N. Jagannathan, Krishna Prasanna Markakis, Michail Modiano, Eytan H. Tsitsiklis, John N. We investigate the asymptotic behavior of the steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-α scheduling policies, and derive an exact asymptotic characterization of the steady-state queue length distributions. In particular, we show that the tail of the light queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also shows that the celebrated max-weight scheduling policy leads to the worst possible tail of the light queue distribution, among all non-idling policies. Motivated by the above `negative' result regarding the max-weight-α policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail, while still being throughput optimal. National Science Foundation (U.S.) (grant CNS-0626781) National Science Foundation (U.S.) (grant CNS-0915988) National Science Foundation (U.S.) (grant CCF-0728554) United States. Army Research Office (muri grant W911NF-08-1-0238) 2011-11-07T15:45:23Z 2011-11-07T15:45:23Z 2011-06 2011-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-9919-9 0743-166X INSPEC Accession Number: 12085842 http://hdl.handle.net/1721.1/66953 Jagannathan, Krishna et al. “Queue Length Asymptotics for Generalized Max-weight Scheduling in the Presence of Heavy-tailed Traffic.” 2011 Proceedings IEEE INFOCOM. Shanghai, China, 2011. 2318-2326. https://orcid.org/0000-0003-1469-7729 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1109/INFCOM.2011.5935049 2011 Proceedings IEEE INFOCOM Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers MIT web domain |
| spellingShingle | Jagannathan, Krishna Prasanna Markakis, Michail Modiano, Eytan H. Tsitsiklis, John N. Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic |
| title | Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic |
| title_full | Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic |
| title_fullStr | Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic |
| title_full_unstemmed | Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic |
| title_short | Queue length asymptotics for generalized max-weight scheduling in the presence of heavy-tailed traffic |
| title_sort | queue length asymptotics for generalized max weight scheduling in the presence of heavy tailed traffic |
| url | http://hdl.handle.net/1721.1/66953 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 jagannathankrishnaprasanna queuelengthasymptoticsforgeneralizedmaxweightschedulinginthepresenceofheavytailedtraffic AT markakismichail queuelengthasymptoticsforgeneralizedmaxweightschedulinginthepresenceofheavytailedtraffic AT modianoeytanh queuelengthasymptoticsforgeneralizedmaxweightschedulinginthepresenceofheavytailedtraffic AT tsitsiklisjohnn queuelengthasymptoticsforgeneralizedmaxweightschedulinginthepresenceofheavytailedtraffic |