Online Distributed Queue Length Estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908337777410048 |
|---|---|
| author | Bhaskara, Aditya Gollapudi, Sreenivas Im, Sungjin Kollias, Kostas Munagala, Kamesh |
| author_facet | Bhaskara, Aditya Gollapudi, Sreenivas Im, Sungjin Kollias, Kostas Munagala, Kamesh |
| contents | Queue length monitoring is a commonly arising problem in numerous applications such as queue management systems, scheduling, and traffic monitoring. Motivated by such applications, we formulate a queue monitoring problem, where there is a FIFO queue with arbitrary arrivals and departures, and a server needs to monitor the length of a queue by using decentralized pings from packets in the queue. Packets can send pings informing the server about the number of packets ahead of them in the queue. Via novel online policies and lower bounds, we tightly characterize the trade-off between the number of pings sent and the accuracy of the server's real time estimates. Our work studies the trade-off under various arrival and departure processes, including constant-rate, Poisson, and adversarial processes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18503 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Distributed Queue Length Estimation Bhaskara, Aditya Gollapudi, Sreenivas Im, Sungjin Kollias, Kostas Munagala, Kamesh Data Structures and Algorithms Queue length monitoring is a commonly arising problem in numerous applications such as queue management systems, scheduling, and traffic monitoring. Motivated by such applications, we formulate a queue monitoring problem, where there is a FIFO queue with arbitrary arrivals and departures, and a server needs to monitor the length of a queue by using decentralized pings from packets in the queue. Packets can send pings informing the server about the number of packets ahead of them in the queue. Via novel online policies and lower bounds, we tightly characterize the trade-off between the number of pings sent and the accuracy of the server's real time estimates. Our work studies the trade-off under various arrival and departure processes, including constant-rate, Poisson, and adversarial processes. |
| title | Online Distributed Queue Length Estimation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.18503 |