Frequency Estimation of Internet Packet Streams with Limited Space

    Erik D. Demaine
    MIT

    What can we learn about network traffic patterns by instrumenting a router
    in the Internet backbone?  This question is important for building better
    models of network traffic, which has applications in network routing,
    caching, prefetching, delivery, and planning.  A major difficulty is that
    there is simply too much data passing through the router to be recorded for
    later analysis, on the order of gigabytes a second.  The central problem
    addressed in this work is how to use the limited amount of space available
    in the router to determine essential features of the packet stream.
    Specifically, we consider the difficult problem of estimating the k
    most-frequently-occuring destination addresses, which is useful in
    particular for billing.  We give matching algorithms and lower bounds on
    how common a packet must be in order to be reported with high probability,
    in both the worst-case and stochastic models of network traffic.

    This is joint work with Alejandro Lopez-Ortiz and J. Ian Munro.