Online Distributed Queue Length Estimation
By: Aditya Bhaskara , Sreenivas Gollapudi , Sungjin Im and more
Potential Business Impact:
Lets computers guess how many things are waiting.
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.
Similar Papers
Uncovering the topology of an infinite-server queueing network from population data
Probability
Helps understand how many people are waiting.
Geometric lower bounds for the steady-state occupancy of processing networks with limited connectivity
Probability
Makes computer networks handle more tasks faster.
A Stochastic Differential Equation Framework for Modeling Queue Length Dynamics Inspired by Self-Similarity
Systems and Control
Predicts traffic jams better for smarter roads.