Parallel and Distributed Frugal Tracking of a Quantile

In this paper we deal with the problem of monitoring network latency. Indeed, latency is a key network metric related to bothnetwork performance and Quality of Service, since it directly impacts on the overall user’s experience. High latency leads to unacceptably slow response times of network services, and may increase network congestion and reduce the throughput, in turn disrupting communications and the user’s experience. A common approach to monitoring network latency takes into account the frequently skewed distribution of latency values, and therefore specific quantiles are monitored, such asthe95th,98th,and 99thpercentiles. We present a parallel, message-passing based version of the Frugal algorithm that can be used for monitoring network latency quickly and accurately. A distributed version is also discussed.