Parallel and Distributed Frugal Tracking of a Quantile

In this paper, we deal with the problem of monitoring network latency. Indeed, latency isa key network metric related to both network performance and quality of service, since it directlyimpacts on the overall user’s experience. High latency leads to unacceptably slow response times ofnetwork services, and may increase network congestion and reduce the throughput, in turn disruptingcommunications and the user’s experience. A common approach to monitoring network latency takesinto account the frequently skewed distribution of latency values, and therefore specific quantilesare monitored, such as the 95th, 98th, and 99th percentiles. We present a comparative analysis of thespeed of convergence of the sequential FRUGAL-1U, FRUGAL-2U, and EASYQUANTILE algorithmsand the design and analysis of parallel, message-passing-based versions of these algorithms thatcan be used for monitoring network latency quickly and accurately. Distributed versions are alsodiscussed. Extensive experimental results are provided and discussed as well