Paper Info
Title
Online Spread Estimation with Non-duplicate Sampling
Abstract
Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real time and produces spread estimation with much better accuracy. By storing traffic data in off-chip memory, our new design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. The experiment results based on real Internet traffic traces show that our estimator reduces the mean relative and absolute error by around one order of magnitude, and achieves both space-efficiency and accuracy-efficiency in flow classification for small flows compared to the prior art.
Year
DOI
Venue
2020
10.1109/INFOCOM41043.2020.9155525
IEEE INFOCOM 2020 - IEEE Conference on Computer Communications
Keywords
DocType
ISSN
Traffic measurement,sampling,spread estimation.
Conference
0743-166X
ISBN
Citations 
PageRank 
978-1-7281-6413-7
0
0.34
References 
Authors
16
6
Name
Order
Citations
PageRank
Yu-e Sun1337.07
He Huang282965.14
Chaoyi Ma300.34
Shiping Chen419025.84
Yang Du5146.47
Qingjun Xiao629122.32