Invention Application
- Patent Title: Algorithms and Estimators for Summarization of Unaggregated Data Streams
- Patent Title (中): 用于汇总未分类数据流的算法和估计器
-
Application No.: US12136725Application Date: 2008-06-10
-
Publication No.: US20090303901A1Publication Date: 2009-12-10
- Inventor: Nicholas Duffield , Edith Cohen , Haim Kaplan , Carsten Lund , Mikkel Thorup
- Applicant: Nicholas Duffield , Edith Cohen , Haim Kaplan , Carsten Lund , Mikkel Thorup
- Assignee: AT&T LABORATORIES, INC.
- Current Assignee: AT&T LABORATORIES, INC.
- Main IPC: H04L12/26
- IPC: H04L12/26

Abstract:
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.
Public/Granted literature
- US07746808B2 Algorithms and estimators for summarization of unaggregated data streams Public/Granted day:2010-06-29
Information query