Per-flow traffic measurement is critical for usage accounting, traffic
engineering, and anomaly detection. Previous methodologies are
either based on random sampling (e.g., Cisco¡¯s NetFlow), which
is inaccurate, or only account for the ¡°elephants¡±. Our paper introduces
a novel technique for measuring per-flow traffic approximately,
for all flows regardless of their sizes, at very high-speed
(say, OC192+). The core of this technique is a novel data structure
called Space Code Bloom Filter (SCBF). A SCBF is an approximate
representation of a multiset; each element in this multiset is
a traffic flow and its multiplicity is the number of packets in the
flow. SCBF employs a Maximum Likelihood Estimation (MLE)
method to measure the multiplicity of an element in the multiset.
Through parameter tuning, SCBF allows for graceful tradeoff between
measurement accuracy and computational and storage complexity.
SCBF also contributes to the foundation of data streaming
by introducing a new paradigm called blind streaming. We evaluated
the performance of SCBF on packet traces gathered from a
tier-1 ISP backbone and through mathematical analysis. Our preliminary
results demonstrate that SCBF achieves reasonable measurement
accuracy with very low storage and computational complexity.