High-speed traffic measurement and analysis methodologies...

Details High-speed traffic measurement and analysis methodologies... High-speed traffic measurement and analysis methodologies...

2008-07-08

2008-07-08

Nguyen, Chau (Department: 2619)

Multiplex communications

Diagnostic testing

Determination of communication parameters

Reexamination Certificate

active

10909908

ABSTRACT:
A network-wide traffic measurement/analysis problem is formulated as a series of set-cardinality-determination (SCD) problems, using probabilistic distinct sample counting techniques to compute network-wide traffic measurements of interest in a distributed manner via the exchange of light-weight traffic digests (TD's) amongst network nodes/routers. A TD for N packets uses only requires O(loglog N) bits of memory storage, making it possible to distribute nodal TD's to all routers within a domain by piggybacking them as opaque data objects inside existing control messages, such as OSPF link-state packets (LSPs) or I-BGP control messages. A router receiving the TD's can estimate the traffic measurements of interest for each of its local links by solving a series of set-cardinality-determination problems. The traffic measurements of interest are typically per-link, per-traffic-aggregate packet (or flow) counts, where an aggregate is defined by the group of packets sharing the same originating and/or destination nodes (or links) and/or some intermediate nodes (or links).

REFERENCES:
patent: 5999961 (1999-12-01), Manohar et al.
patent: 7146416 (2006-12-01), Yoo et al.
patent: 2002/0143929 (2002-10-01), Maltz et al.
patent: WO 03/075509 (2003-09-01), None
Lam, IEEE Transactions on Computers, vol. 40, No. 3, Mar. 1991.
Sarnath, IEEE Efficient parallel algorithms for selection and searchingon sorted matrices, 1992.
A. Medina et al., “Traffic Matrix Estimation: Existing Techniques And New Directions”,Proc. of ACM SIGCOMM'02, Aug. 19-23, 2002, Pittsburg, Pennsylvania.
Y. Zhang et al., “Fast Accurate Computation of Large-Scale IP Traffic Matrices From Link Loads”,Proc. of ACM SIGMETRICS'03, Jun. 10-14, San Diego, CA.
Y. Zhang et al., “An Information-Theoretic Approach to Traffic Matrix Estimation”,Proc. of ACM SIGCOMM'03, Aug. 25-29, 2003, Karlsr8he, Germany.
Cisco ISO Software Netflow, http://www.cisco.com/warp/public/732/Tech
mp
etflow/index.shtml.
N. G. Duffield et al., “Trajectory Sampling for Direct Traffic Observtion”,Proc. of ACM SIGCOMM'00, Stockholm, Sweden, Aug. 2000, pp. 271-282.
A. C. Snoeren et al., “Hash-Based IP Traceback”,Proc. of ACM SIGCOMM'01, Aug. 27,31, 2001, San Diego, California, pp. 3-14.
B. H. Bloom, “Space/Time Trade-offs In Hash Coding With Allowable Errors”,Commications of the ACM, vol. 13, No. 7, Jul. 1970, pp. 422-426.
A. Broder et al., “Network Applications of Bloom Filters: A Survey*”,Allerton Conference 2002, available at http://www.eecs.harvard.edu/˜michaelm.
J. Byers et al., “Informed Content Delivery Across Adaptive Overlay Networks”,Proc. of ACM SIGCOMM'02, Aug. 19-23, 2002, Pittsburg, Pennsylvania, pp. 47-60.
P. Flajolet et al., “Probabilistic Counting Algorithms for Data Base Applications”,Journal of Computer and System Sciences, vol. 31, No. 2, Oct. 1985, pp. 182-209.
M. Durand et al., “Loglog Counting of Large Cardinalities”, submitted toEuropean Symposium on Algorithms, ESAS'2003, Apr. 2003.
C. Estan et al., “Counting the Number of Active Flows On A High Speed Link”,ACM SIGCOMM Computer Communications Review, vol. 32, No. 3, Jul. 2002, p. 10.
P. B. Gibbons et al., “Estimating Simple Functions On The Union of Data Streams”,Proc. of ACM SPAA'01, Crete, Greece, 2001, pp. 281-290.
A. Z. Broder et al., “On the Resemblance And Containment of Documents”,Compression and Complexity of Sequences 1997 Proceedings, Positano, Italy, Jun. 1997.
Y. Vardi, “Network Tomography: Estimating Source-Destination Traffic Intensities From Link Data”,Journal of American Statistics Association, vol. 91, 1996, pp. 365-377.
J. Cao et al., “Time-Varying Network Tomography: Router Link Data”,Journal of American Statistics Association, vol. 95, 2000, pp. 1063-1075.
A. Z. Broder et al., “Min-Wise Independent Permutations”,Journal of Computer And System Sciences, vol. 60, No. 3, 2000, pp. 630-659.
W-M Lin et al., “Look-Ahead Traffic Distribution In wormhold-Routed Networks”,Proceedings of Seventeenth IEEE Symposium On Reliable Distributed Systems, Oct. 20-23, 1998, pp. 318-322.

Affiliated with

Also associated with

Rating

High-speed traffic measurement and analysis methodologies... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-speed traffic measurement and analysis methodologies..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed traffic measurement and analysis methodologies... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3935717