An algorithm is proposed to detect elephant flows. It assumes the flow rates are under Pareto distribution and the algorithm is as follows:

  • Sample packet at probability
  • For each sampled packet, if the flow already exists in the counter array, increment the counter
  • If the flow doesn’t exists in the counter array, evict a counter if possible and put this flow into the counter, initialize to zero
  • A eviction pointer scans the counter array, whenever a new flow comes, it does following:
    • If the current counter greater than threshold, cut half
    • Repeat this until you see a counter below threshold, which you clear the counter for that new flow

In the paper, equation is proposed to find the relation between the sampling probability and eviction cycle .

Bibliographic data

@inproceedings{
   title = "ElephantTrap: A low cost device for identifying large flows",
   author = "Yi Lu and Mei Wang and Balaji Prabhakar and Flavio Bonomi",
   howpublished = "SHPI",
   booktitle = "Proc 15th IEEE Symposium on High-Performance Interconnects",
   year = "2007",
}