Title: High Speed Elephant Flow Detection Under Partial Information,
Abstract: In this paper we introduce a new framework to detect elephant flows at very
high speed rates and under uncertainty. The framework provides exact
mathematical formulas to compute the detection likelihood and introduces a new
flow reconstruction lemma under partial information. These theoretical results
lead to the design of BubbleCache, a new elephant flow detection algorithm
designed to operate near the optimal tradeoff between computational scalability
and accuracy by dynamically tracking the traffic's natural cutoff sampling
rate. We demonstrate on a real world 100 Gbps network that the BubbleCache
algorithm helps reduce the computational cost by a factor of 1000 and the
memory requirements by a factor of 100 while detecting the top flows on the
network with very high probability.