Bianchi, Giuseppe and Duffy, Ken R. and Leith, Douglas J. and Shneer, Vsevolod
(2012)
Modeling Conservative Updates in Multi-Hash
Approximate Count Sketches.
In:
Proceedings of the 2012 24th International Teletraffic Congress (ITC 24).
ITCP, pp. 17-24.
ISBN 978-0-9836283-4-7
Abstract
Multi-hash-based count sketches are fast and memory
efficient probabilistic data structures that are widely used
in scalable online traffic monitoring applications. Their accuracy
significantly improves with an optimization, called conservative
update, which is especially effective when the aim is to discriminate
a relatively small number of heavy hitters in a traffic stream
consisting of an extremely large number of flows. Despite its
widespread application, a thorough understanding of the conservative
update operation has lagged behind, perhaps because
of the significant modeling complexity involved. In this work
we attempt to fill this gap. Our proposed modeling approach
builds on a practically important empirical finding: simulation
results (as well as experimental ones over real traffic traces)
obtained for skewed load scenarios exhibit a sharp waterfall-type
behaviour. That is, the approximate count provided by the sketch
response remains accurate until an “error floor” is reached.
Flows below this error flow level are on average approximated
by the same error floor count value, irrespective of their exact
count. The error floor itself appears to be maximal in the case
of uniform load. Leveraging the simplifications made possible
when the load is uniform, we derive an analytic model capable
of accurately predicting the transient growth behavior of the
(tightly correlated) counters deployed in the data structure and
obtain an upper bound on the error floor level.
| Item Type: |
Book Section
|
| Keywords: |
cryptography; data models; data structures; optimisation; probability; |
| Academic Unit: |
Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: |
5986 |
| Depositing User: |
Dr Ken Duffy
|
| Date Deposited: |
24 Mar 2015 16:55 |
| Publisher: |
ITCP |
| Refereed: |
Yes |
| URI: |
|
| Use Licence: |
This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available
here |
Repository Staff Only(login required)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric