networking

Summary cache: a scalable wide-area web cache sharing protocol. Li Fan, Pei Cao, Jussara Almeida, Andrei Z. Broder. SIGCOMM 98.
Introduces the idea of a counting Bloom filter, to support dynamic insertions and deletions in a Bloom filter. This usage is a special case of the Count-Min sketch, but the algorithm for the maintaining the sketch is quite similar.
Robust Aggregation in Sensor Networks. George Kollios, John Byers, Jeffrey Considine, Marios Hadjieleftheriou, and Feifei Li. IEEE Data Eng Bull, 28(1), 05.

Combines Count-Min sketch with approximate distinct element counters to allow summaries to be merged multiple times and count only the number of distinct occurrences.
"We show how the Count-Min sketch can be made duplicate-insensitive for exploiting multi-path routing in sensor networks. Even though other frequency counting techniques have been proposed in the past, the Count-Min sketch is robust, small in size, and provides error guarantees."

Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications. Yin Zhang , Sumeet Singh, Subhabrata Sen, Nick Duffield, Carsten Lund. 4th ACM SIGCOMM conference on Internet measurement, Taormina, Sicily, Italy 2004
Uses sketch summaries to find the "hierarchical heavy hitters" (HHHs): items within a hierarchy with a significant frequency after removing descendant HHHs.

Statistical Approaches for Network Anomaly Detection. Christian CALLEGARI
Tutorial on anomaly detection, shows how to use sketches to identify heavy flows and hierarchical heavy hitters in flow and packet data.

A Novel Approach for Anomaly Detection over High-Speed Networks. Osman Salem, Sandrine Vaton, Annie Gravey.

Uses sketch techniques to identify (volume) anomalies in network data. "Our proposed framework is based on 2 data summary architecture: a Multi-Layer Reversible Sketch (MLRS) and a Count-Min Sketch (CMS)..."

Synopsis Diffusion for Robust Aggregation in Sensor Networks. Suman Nath, Phillip Gibbons, Srinivasan Seshan and Zachary Anderson. Conference On Embedded Networked Sensor Systems, 2004.

Proposes a framework for sharing summaries within a sensor network (when summaries may be duplicated, retransmitted, or travel along multiple paths to the destination), and observes that Count-Min sketch can be applied in this setting:
"Although the Count-Min Sketch has been proposed in the context of a single stream, it can be extended to be used in the synopsis diffusion framework by re-placing the duplicate-sensitive counter of each array cell with an ODI Sum synopsis..."

Tracking Long Duration Flows in Network Traffic. Aiyou Chen, Yu Jiny, Jin Ca0, Li Erran Li. INFOCOM 2010.

"Our online flow duration estimation is similar to the Count-Min sketch devised by [2] for heavy hitter detection (minimum value of the hashed entries), but our (Bloom Filter) update uses the
maximum of its current hash entry and an estimate from past, which is different from Count-Min sketch and standard CBF."

Secure Distributed Data Mining and Its Application to Large Scale Network Measurements. Matthew Roughan and Yin Zhang. ACM SIGCOMM Computer Communication Review 2006.

Defines techniques for private computation of complex statistics, based on private computation of sums and counts, and argues that since Count-Min sketch is based on such primitives, the whole structure can be used as part of private computations.

Anomaly Detection Approaches for Communication Networks. Marina Thottan, Guanglei Liu, Chuanyi Ji. In "Algorithms for Next Generation Networks", Springer 2010.
Survey chapter on anomaly detection techniques, including Count-Min sketch as a prime example.

Untangling the Braid: Finding Outliers in a Set of Streams. Chiranjeeb Buragohain, Luca Foschini, Subhash Suri. ALENEX, 2010.

Uses sketch data structures within an algorithm to identify network users with the largest deviation from the norm: "Within the bucket, we use a sketch, such as the Count-Min sketch, to keep track of the number of items belonging to different streams."

Outlier Detection: Principles, Techniques and Applications. Sanjay Chawla and Pei Sun. Tutorial. PAKDD 06.

Finding Hierarchical Heavy Hitters with the Count Min Sketch. Pascal Cheung-Mon-Chan, Fabrice Clérot [Slides]
Applies sketch techniques to identify Hierarchical Heavy Hitters in high speed network data streams.
A fast and compact method for unveiling significant patterns in high speed networks. Tian Bu, Jin Cao, Aiyou Chen, and Patrick Lee. IEEE INFOCOM, 2007.
Uses essentially the hierarchical Count-Min sketch approach to find "heavy changers": IP addresses whose traffic volume changes significantly. Argues that this approach will work well when changers are randomly distributed within the address space.
A scalable, efficient and informative approach for anomaly-based intrusion detection systems: theory and practice
Osman Salem, Sandrine Vaton, Annie Gravey. International Journal of Network Management,
Volume 20 Issue 5, September 2010.
Describes a solution for anomaly detection making extensive use of sketch techniques. "In this paper, we present the design and implementation of a new approach for anomaly detection and classification over high speed networks... The good properties of the Count Min Sketch in terms of resistance to collisions make it possible to check the accuracy of the information about the ongoing attack."

Comments