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

5 Scopus citations

Abstract

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
Pages21-31
Number of pages11
DOIs
StatePublished - Mar 28 2011
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

Other

Other12th International Conference on Passive and Active Measurement, PAM 2011
CountryUnited States
CityAtlanta, GA
Period03/20/1103/22/11

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this