Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2011-08-02
2011-08-02
Pham, Chi H (Department: 2471)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000, C370S408000
Reexamination Certificate
active
07990982
ABSTRACT:
Methods and apparatus to bound network traffic estimation error for multistage measurement sampling and aggregation are disclosed. An example method disclosed herein comprises determining a hierarchical sampling topology representative of multiple data sampling and aggregation stages, the hierarchical sampling topology comprising a plurality of nodes connected by a plurality of edges, each node corresponding to at least one of a data source and a data aggregation operation, and each edge corresponding to a data sampling operation characterized by a generalized sampling threshold, selecting a first generalized sampling threshold from a set of generalized sampling thresholds associated with a respective set of edges originating at a respective set of descendent nodes of a target node undergoing network traffic estimation, and transforming a measured sample of network traffic into a confidence interval for a network traffic estimate associated with the target node using the first generalized sampling threshold and an error parameter.
REFERENCES:
patent: 6829220 (2004-12-01), Thorup et al.
patent: 6850488 (2005-02-01), Wesley et al.
patent: 6873600 (2005-03-01), Duffield et al.
patent: 6944673 (2005-09-01), Malan et al.
patent: 7080136 (2006-07-01), Duffield et al.
patent: 7299283 (2007-11-01), Duffield et al.
patent: 7363371 (2008-04-01), Kirkby et al.
patent: 7653007 (2010-01-01), Kodialam et al.
patent: 7724660 (2010-05-01), Segel
patent: 7729269 (2010-06-01), Nucci et al.
patent: 2003/0130819 (2003-07-01), Stewart
patent: 2007/0016666 (2007-01-01), Duffield et al.
patent: 2009/0161570 (2009-06-01), Duffield et al.
Alon et al., “Estimating Arbitrary Subset Sums with Few Probes,” pp. 317-325, Symposium on Principles of Database Systems, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, held in Baltimore, USA, on Jun. 13-15, 2005 (9 pages).
Brauckhoff et al., “Impact of Packet Sampling on Anomaly Detection Metrics,” pp. 159-164, Internet Measurement Conference, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, held in Rio de Janeiro, Brazil, on Oct. 25-27, 2006 (6 pages).
Cisco Systems, Inc., “NetFlow Services and Applications,” Copyrighted in 1999 (27 pages).
Claffy et al., “Application of Sampling Methodologies to Network Traffic Characterization,” pp. 194-203, vol. 23, Issue 4, ACM SIGCOMM Computer Communication Review, Oct. 1993 (10 pages).
Cohen et al., “Sketching Unaggregated Data Streams for Subpopulation-Size Queries,” pp. 253-262 Symposium on Principles of Database Systems, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, held in Beijing, China, on Jun. 11-14, 2007 (10 pages).
Cohen et al., “Processing Top-k Queries from Samples,” Article No. 7, International Conference on Emerging Networking Experiments and Technologies, Proceedings of the 2006 ACM CoNext Conference, held in Lisboa, Portugal, 2006 (30 pages).
Duffield et al., “Trajectory Sampling with Unreliable Reporting,” pp. 37-50, vol. 16, Issue 1, IEEE/ACM Transactions on Networking (TON), Feb. 2008 (12 pages).
Duffield et al., “Predicting Resource Usage and Estimation Accuracy in an IP Flow Measurement Collection Infrastructure,” pp. 179-191, Internet Measurement Conference, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, held in Miami Beach, USA, on Oct. 27-29, 2003 (13 pages).
Duffield et al., “Charging from Sampled Network Usage,” pp. 245-256, Internet Measurement Conference, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, held in San Francisco, USA, 2001 (12 pages).
Duffield et al., “Flow Sampling Under Hard Resource Constraints,” pp. 85-96, vol. 32, Issue 1, ACM SIGMETRICS Performance Evaluation Review, Jun. 2004 (13 pages).
Duffield et al., “Estimating Flow Distributions from Sampled Flow Statistics,” SIGCOMM'03 held in Karlsruhe, Germany on Aug. 25-29, 2003 (12 pages).
Duffield et al., “Optimal Combination of Sampled Network Measurements,” Internet Measurement Conference, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, held in Berkeley, USA, 2005 (14 pages).
Duffield et al., “Trajectory Sampling for Direct Traffic Observation,” pp. 280-292, vol. 9, Issue 3, IEEE/ACM Transactions on Networking (TON), Jun. 2001 (14 pages).
Estan et al., “Building a Better NetFlow,” pp. 245-256, Applications, Technologies, Architectures, and Protocols for Computer Communication, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, held in Portland, USA, on Aug. 30-Sep. 3, 2004 (12 pages).
Estan et al., “New Directions in Traffic Measurement and Accounting,” pp. 323-336, vol. 32, Issue 4, ACM SIGCOMM Computer Communication Review, Proceedings of the 2002 SIGCOMM Conference, held in Pittsburgh, USA, on Aug. 19-23, 2002 (14 pages).
Gibbons et al., “New Sampling-Based Summary Statistics for Improving Approximate Query Answers,” pp. 331-342, International Conference on Management of Data, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, held in Seattle, USA, 1998 (12 pages).
Jedwab et al., “Traffic Estimation for the Largest Sources on a Network, using Packet Sampling with Limited Storage,” Technical Report HPL-92-3, HP Laboratories, Bristol, retrieved from http://www.hpl.hp.com/techreports/92/HPL-92-35.html, Mar. 1992 (13 pages).
Johnson et al., “Sampling Algorithms in a Stream Operator,” pp. 1-12, International Conference on Management of Data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, held in Baltimore, USA, 2005 (12 pages).
Keys et al., “A Robust System for Accurate Real-Time Summaries of Internet Traffic,” pp. 85-96, vol. 33, Issue 1, ACM SIGMETRICS Performance Evaluation Review, held in Banff, Canada, on Jun. 6-10, 2005 (12 pages).
Kompella et al., “The Power of Slicing in Internet Flow Measurement,” Internet Measurement Conference, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, held in Berkeley, USA, 2005 (14 pages).
Mai et al., “Is Sampled Data Sufficient for Anomaly Detection?” pp. 165-176, Internet Measurement Conference, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, held in Rio de Janeiro, Brazil, on Oct. 25-27, 2006 (12 pages).
Phaal et al., “InMon Corporation's sFlow: A Method for Monitoring Traffic in Switched and Routed Networks,” Internet Request for Comments: 3176, Sep. 2001 (31 pages).
Reves et al., “Traffic Monitoring with Packet-Based Sampling for Defense against Security Threats,” Proceedings of Passive and Active Measurement Workshop (PAM 2002), held in Fort Collins, USA, on Mar. 25-26, 2002 (9 pages).
Szegedy, Mario, “Near Optimality of the Priority Sampling Procedure,” Electronic Colloquium on Computational Complexity Report TR05-001, Apr. 12, 2005 (14 pages).
Szegedy et al., “On the Variance of Subset Sum Estimation,” Lecture Notes in Computer Science, 2007 (20 pages).
Turian et al., “Computational Challenges in Parsing by Classification,” Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing, 2006 (8 pages).
Zseby, Tanja, “Deployment of Sampling Methods for SLA Validation with Non-Intrusive Measurements,” Proceedings of Passive and Active Measurement Workshop (PAM 2002), held in Fort Collins, USA, on Mar. 25-26, 2002 (11 pages).
Duffield et al., “Priority Sampling Estimating Arbitrary Subset Sums,” Computer Science—Data Structures and Algorithms, submitted on Sep. 9, 2005 (26 pages).
Thorup, Mikkel, “Confidence Intervals for Priority Sampling,” pp. 252-263, vol. 34, Issue 1, AC
Cohen Edith
Duffield Nicholas
Lund Carsten
Thorup Mikkel
AT&T Intellectual Property I L.P.
Faroul Farah
Hanley, Flight & Zimmerman
Pham Chi H
LandOfFree
Methods and apparatus to bound network traffic estimation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus to bound network traffic estimation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus to bound network traffic estimation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2725281