Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
2008-06-10
2010-06-29
Vu, Huy D (Department: 2461)
Multiplex communications
Diagnostic testing
Determination of communication parameters
Reexamination Certificate
active
07746808
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.
REFERENCES:
patent: 5406495 (1995-04-01), Hill
patent: 5721896 (1998-02-01), Ganguly et al.
patent: 5870752 (1999-02-01), Gibbons et al.
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 7093056 (2006-08-01), Heighway et al.
patent: 7191181 (2007-03-01), Chaudhuri et al.
patent: 7193968 (2007-03-01), Kapoor et al.
patent: 7287020 (2007-10-01), Chaudhuri et al.
patent: 7293037 (2007-11-01), Chaudhuri et al.
patent: 7293086 (2007-11-01), Duffield et al.
patent: 2004/0059828 (2004-03-01), Hooper et al.
patent: 2005/0022180 (2005-01-01), Couturier
patent: 2007/0016666 (2007-01-01), Duffield et al.
Estan et al., “Building a Better NetFlow,” SIGCOMM'04, Aug. 30-Sep. 3, Portland, Oregon, USA, pp. 245-256, 2004.
Keys et al., “A Robust, System for Accurate Real-time Summaries of Internet raffic,” SIGMETRICS 05, Jun. 6-10, Banff, Alberta, Canada, pp. 85-96, 2005.
Cohen, “Size-Estimation Framework with Applications to Transitive Closure and Reachability,”Journal of Computer and System Sciences55:441-453, 1997.
Cohen et al., “Sketching Unaggregated Data Streams for Subpopulation-Size Queries,”Proc of the 2007 ACM Symp. On Principles of Database Systems, 2007.
Cohen et al., “Bottom-k Sketches: Better and More Efficient Estimation of Aggregates,”SIGMETRICS'07 Jun. 12-16, San Diego, CA, USA, 2007.
Cohen et al., “Spatially-Decaying Aggregation Over a Network: Model and Algorithms,”SIGMOD 2004, Jun. 13-18, Paris, France, pp. 707-718, 2004.
Cohen et al., “Summarizing Data Using Bottom-k Sketches,”PODC'07, Aug. 12-15, 2007 Portland, Oregon, USA, 2007.
Cranor et al., “Gigascope: A Stream Database for Network Applications,”SIGMOD2003, Jun. 9-12, San Diego, CA, pp. 647-651, 2003.
Estan et al., “Building a Better NetFlow,”SIGCOMM'04, Aug. 30-Sep. 3, Portland, Oregon, USA, pp. 245-256, 2004.
Estan et al., “New Directions in Traffic Measurement and Accounting,”SIGCOMM'02, Aug. 19-23, 2002 Pittsburgh, PA, USA, pp. 323-336, 2002.
Gibbons et al., “New Sampling-Based Summary Statistics for Improving Query Answers,”SIGMOD'98, Seattle, WA, USA, pp. 331-342, 1998.
Hellerstein et al., “Online Aggregation,”SIGMOD '97AZ, USA, pp. 171-182, 1997.
Hohn et al., “Inverting Sampled Traffic,”IMC '03Oct. 27-29, Miami Beach, FL, USA, 2003.
Keys et al., “A Robust System for Accurate Real-time Summaries of Internet Traffic,”SIGMETRICS'05, Jun. 6-10, Banff, Alberta, Canada, pp. 85-96, 2005.
Kumar, et al., “A Data Streaming Algorithm for Estimating Subpopulation Flow Size Distribution,”SIGMETRICS '05, Jun. 6-10, Banff, Alberta, Canada, pp. 61-72, 2005.
Ramabhadran et al., “Efficient Implementation of a Statistics Counter Architecture,”SIGMETRICS '03, Jun. 10-14, San Diego, CA, USA, 2003.
Ribeiro, et al., “Fisher Information of Sampled Packets: an Application to Flow Size Estimation,”IMC '06, Oct. 25-27, Rio de Janeiro, Brazil, 2006.
Shah et al., “Maintaining Statistics Counters in Router Line Cards,” 2002 IEEE, pp. 76-81.
Szegedy et al., “On the Variance of Subset Sum Estimation,” ESA 2007, LNCS 4698, pp. 75-86. 2007.
Cohen Edith
Duffield Nicholas
Kaplan Haim
Lund Carsten
Thorup Mikkel
AT&T Intellectual Property II L.P.
Duffy James P
Hoffman & Baron LLP
Vu Huy D
LandOfFree
Algorithms and estimators for summarization of unaggregated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Algorithms and estimators for summarization of unaggregated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms and estimators for summarization of unaggregated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4242204