Algorithms and estimators for summarization of unaggregated data streams Patent uri icon


  • The invention relates to streaming algorithms useful for obtaining summaries over unaggregated packet streams and for providing unbiased estimators for characteristics, such as, the amount of traffic that belongs to a specified subpopulation of flows. Packets are sampled from a packet stream and aggregated into flows and counted by implementation of Adaptive Sample-and-Hold (ASH) or Adaptive NetFlow (ANF), adjusting the sampling rate based on a quantity of flows to obtain a sketch having a predetermined size, the sampling rate being adjusted in steps; and transferring the count of aggregated packets from SRAM to DRAM and initializing the count in SRAM following adjustment of the sampling rate.

author list (cited authors)

  • Duffield, N., Cohen, E., Kaplan, H., Lund, C., & Thorup, M.

complete list of authors

  • Duffield, N||Cohen, E||Kaplan, H||Lund, C||Thorup, M

publication date

  • December 2009