Title: ESTIMATING TRAFFIC RATES BY COUNTING COINCIDENCES

Per-flow network traffic measurement is needed for effective traffic management,
performance assessment, and detection of anomalous network events such as
incipient DoS attacks. Explicit measurement of per-flow traffic statistics is
difficult in backbone networks because tracking the possibly hundreds of
thousands of flows needs correspondingly large high-speed memory as well as
increased per-arrival processing. 
To reduce the measurement overhead, many previous papers have proposed the use
of random sampling and this is also used in commercial routers
(Cisco's NetFlow).
Our goal is to develop methodology that has very low memory requirements and
has quick convergence to within a pre-specified accuracy.
We achieve this by use of a novel approach based on counting coincidences in
the traffic stream. (A flow has a coincidence when two consecutive samples
belong to the same flow). Sampling coincidences automatically biases the
samples towards the larger flows thereby making the estimation of these sources
more accurate. This biased sampling leads to significantly smaller memory
requirement compared to random sampling schemes.
We show that the scheme is close to optimal both in terms of memory requirement
as well as estimation time. The scheme is very simple to implement and performs
extremely well both on synthetic and trace data.