The Impact of Queue Length Information on Buffer Overflow in Parallel Queues
We consider a system consisting of N parallel queues, served by one server. Time is slotted, and the server serves one of the queues in each time slot, according to some scheduling policy. We first characterize the exponent of the buffer overflow probability and the most likely overflow trajectories...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115238 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826206884986617856 |
|---|---|
| author | Modiano, Eytan H Jagannathan, Krishna Prasanna |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Modiano, Eytan H Jagannathan, Krishna Prasanna |
| author_sort | Modiano, Eytan H |
| collection | MIT |
| description | We consider a system consisting of N parallel queues, served by one server. Time is slotted, and the server serves one of the queues in each time slot, according to some scheduling policy. We first characterize the exponent of the buffer overflow probability and the most likely overflow trajectories under the Longest Queue First (LQF) scheduling policy. Under statistically identical arrivals to each queue, we show that the buffer overflow exponents can be simply expressed in terms of the total system occupancy exponent of $m$ parallel queues, for some m ≤ N. We next turn our attention to the rate of queue length information needed to operate a scheduling policy, and its relationship to the buffer overflow exponents. It is known that queue length blind policies such as processor sharing and random scheduling perform worse than the queue aware LQF policy, when it comes to buffer overflow probability. However, we show that the overflow exponent of the LQF policy can be preserved with arbitrarily infrequent queue length updates. |
| first_indexed | 2024-09-23T13:39:47Z |
| format | Article |
| id | mit-1721.1/115238 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:39:47Z |
| publishDate | 2018 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1152382024-06-27T14:24:56Z The Impact of Queue Length Information on Buffer Overflow in Parallel Queues Modiano, Eytan H Jagannathan, Krishna Prasanna Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Operations Research Center Modiano, Eytan H Jagannathan, Krishna Prasanna We consider a system consisting of N parallel queues, served by one server. Time is slotted, and the server serves one of the queues in each time slot, according to some scheduling policy. We first characterize the exponent of the buffer overflow probability and the most likely overflow trajectories under the Longest Queue First (LQF) scheduling policy. Under statistically identical arrivals to each queue, we show that the buffer overflow exponents can be simply expressed in terms of the total system occupancy exponent of $m$ parallel queues, for some m ≤ N. We next turn our attention to the rate of queue length information needed to operate a scheduling policy, and its relationship to the buffer overflow exponents. It is known that queue length blind policies such as processor sharing and random scheduling perform worse than the queue aware LQF policy, when it comes to buffer overflow probability. However, we show that the overflow exponent of the LQF policy can be preserved with arbitrarily infrequent queue length updates. National Science Foundation (U.S.) (Grant CNS-0626781) National Science Foundation (U.S.) (Grant CNS0915988) United States. Army Research Office. Multidisciplinary University Research Initiative 2018-05-07T14:18:00Z 2018-05-07T14:18:00Z 2013-06 2018-04-06T12:46:47Z Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 http://hdl.handle.net/1721.1/115238 Jagannathan, Krishna, and Eytan Modiano. “The Impact of Queue Length Information on Buffer Overflow in Parallel Queues.” IEEE Transactions on Information Theory 59, no. 10 (October 2013): 6393–6404. https://orcid.org/0000-0001-8238-8130 http://dx.doi.org/10.1109/TIT.2013.2268926 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT Web Domain |
| spellingShingle | Modiano, Eytan H Jagannathan, Krishna Prasanna The Impact of Queue Length Information on Buffer Overflow in Parallel Queues |
| title | The Impact of Queue Length Information on Buffer Overflow in Parallel Queues |
| title_full | The Impact of Queue Length Information on Buffer Overflow in Parallel Queues |
| title_fullStr | The Impact of Queue Length Information on Buffer Overflow in Parallel Queues |
| title_full_unstemmed | The Impact of Queue Length Information on Buffer Overflow in Parallel Queues |
| title_short | The Impact of Queue Length Information on Buffer Overflow in Parallel Queues |
| title_sort | impact of queue length information on buffer overflow in parallel queues |
| url | http://hdl.handle.net/1721.1/115238 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT modianoeytanh theimpactofqueuelengthinformationonbufferoverflowinparallelqueues AT jagannathankrishnaprasanna theimpactofqueuelengthinformationonbufferoverflowinparallelqueues AT modianoeytanh impactofqueuelengthinformationonbufferoverflowinparallelqueues AT jagannathankrishnaprasanna impactofqueuelengthinformationonbufferoverflowinparallelqueues |