MURAL - Maynooth University Research Archive Library



    Modeling Conservative Updates in Multi-Hash Approximate Count Sketches


    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

    [img]
    Preview
    Download (2MB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year