Randomized Admission Policy for Efficient Top-k, Frequency, and Volume Estimation
| Autor: | Yaron Kassner, Roy Friedman, Ran Ben Basat, Gil Einziger, Xiaoqi Chen |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computer Networks and Communications
Network packet business.industry Computer science 020206 networking & telecommunications 02 engineering and technology Network monitoring Flow network Computer Science Applications Network management Identification (information) Computer engineering 0202 electrical engineering electronic engineering information engineering Electrical and Electronic Engineering business Software |
| Zdroj: | IEEE/ACM Transactions on Networking. 27:1432-1445 |
| ISSN: | 1558-2566 1063-6692 |
| DOI: | 10.1109/tnet.2019.2918929 |
| Popis: | Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) –a novel algorithm for the frequency , top-k , and byte volume estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives, for the frequency estimation problem, by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top- $k$ identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads’ skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. In Addition, we present d-way RAP , a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|