NDLI: Bitmap algorithms for counting active flows on high speed links

Please wait, while we are loading the content...

BGP beacons

System capability effects on algorithms for network bandwidth measurement

An analysis of Internet chat systems

Best-path vs. multi-path overlay routing

Constructing internet coordinate system based on delay measurement

Bitmap algorithms for counting active flows on high speed links

Merging logical topologies using end-to-end measurements

Inverting sampled traffic

On the correspondency between TCP acknowledgment packet and data packet

On the correlation between route dynamics and routing loops

On inferring and characterizing internet routing policies

A measurement study of available bandwidth estimation tools

Measuring and modelling the group mmbership in the internet

An empirical evaluation of wide-area internet bottlenecks

Virtual landmarks for the internet

Space-code bloom filter for efficient traffic flow measurement

On the number of distributed measurement points for network tomography

Sketch-based change detection: methods, evaluation, and applications

Is the round-trip time correlated with the number of packets in flight?

Network performance monitoring at small time scales

Some findings on the network performance of broadband hosts

Inferring relative popularity of internet applications by actively querying DNS caches

Model-based identification of dominant congested links

Identifying frequent items in sliding windows over on-line packet streams

Simple network performance tomography

Traffic engineering with estimated traffic matrices

Variability in TCP round-trip times

Source-level IP packet bursts: causes and effects

Predicting resource usage and estimation accuracy in an IP flow measurement collection infrastructure

Tomography-based overlay network monitoring

On the performance of middleboxes

In search of path diversity in ISP networks

Bitmap algorithms for counting active flows on high speed links

Content Provider	ACM Digital Library
Author	Estan, Cristian Varghese, George Fisk, Mike
Abstract	This paper presents a family of bitmap algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high speed link. Such counting can be used to detect DoS attacks and port scans, and to solve measurement problems. Counting is especially hard when processing must be done within a packet arrival time (8 nsec at OC-768 speeds) and, hence, must require only a small number of accesses to limited, fast memory. A naive solution that maintains a hash table requires several Mbytes because the number of flows can be above a million. By contrast, our new probabilistic algorithms take very little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we replaced the port scan detection component of the popular intrusion detection system Snort with one of our new algorithms. This reduced memory usage on a ten minute trace from 50 Mbytes to 5.6 Mbytes while maintaining a 99.77% probability of alarming on a scan within 6 seconds of when the large-memory algorithm would. The best known prior algorithm (probabilistic counting) takes 4 times more memory on port scan detection and 8 times more on a measurement application. Fundamentally, this is because our algorithms can be customized to take advantage of special features of applications such as a large number of instances that have very small counts or prior knowledge of the likely range of the count.
Starting Page	153
Ending Page	166
Page Count	14
File Format	PDF
ISBN	1581137737
DOI	10.1145/948205.948225
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-10-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Counting flows Network traffic measurement
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bitmap algorithms for counting active flows on high speed links

Bitmap algorithms for counting active flows on high-speed links

Bitmap algorithms for counting active flows on high speed links

Bitmap Algorithms for Counting Active Flows on High-Speed Links

Bitmap algorithms for counting active flows on high speed links (2003)

Counting flows over sliding windows in high speed networks.

Bitmap Algorithms for Counting Active Flows on High Speed Links (2003)

Bitmap algorithms for counting active flows on high speed links.

Bitmap algorithms for counting active flows on high.

Bitmap algorithms for counting active flows on high speed links

Similar Documents

Bitmap algorithms for counting active flows on high speed links

Bitmap algorithms for counting active flows on high-speed links

Bitmap algorithms for counting active flows on high speed links

Bitmap Algorithms for Counting Active Flows on High-Speed Links

Bitmap algorithms for counting active flows on high speed links (2003)

Counting flows over sliding windows in high speed networks.

Bitmap Algorithms for Counting Active Flows on High Speed Links (2003)

Bitmap algorithms for counting active flows on high speed links.

Bitmap algorithms for counting active flows on high.

Bitmap algorithms for counting active flows on high speed links