Evolution of cache replacement policies to track heavy-hitter flows

Martin Zadnik*, Marco Canini

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations


Several important network applications cannot easily scale to higher data rates without requiring focusing just on the large traffic flows. Recent works have discussed algorithmic solutions that trade-off accuracy to gain efficiency for filtering and tracking the so-called "heavy-hitters". However, a major limit is that flows must initially go through a filtering process, making it impossible to track state associated with the first few packets of the flow. In this paper, we propose a different paradigm in tracking the large flows which overcomes this limit. We view the problem as that of managing a small flow cache with a finely tuned replacement policy that strives to avoid evicting the heavy-hitters. Our scheme starts from recorded traffic traces and uses Genetic Algorithms to evolve a replacement policy tailored for supporting seamless, stateful traffic-processing. We evaluate our scheme in terms of missed heavy-hitters: it performs close to the optimal, oracle-based policy, and when compared to other standard policies, it consistently outperforms them, even by a factor of two in most cases.

Original languageEnglish (US)
Title of host publicationPassive and Active Measurement - 12th International Conference, PAM 2011, Proceedings
Number of pages11
StatePublished - 2011
Externally publishedYes
Event12th International Conference on Passive and Active Measurement, PAM 2011 - Atlanta, GA, United States
Duration: Mar 20 2011Mar 22 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6579 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th International Conference on Passive and Active Measurement, PAM 2011
Country/TerritoryUnited States
CityAtlanta, GA


  • Network traffic measurement
  • genetic algorithms
  • replacement policy
  • scalability
  • tracking heavy-hitter flows

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Evolution of cache replacement policies to track heavy-hitter flows'. Together they form a unique fingerprint.

Cite this