Evolution of Cache Replacement Policies to Track Heavy-Hitter Flows

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. © 2011 Springer-Verlag.


Editor(s):
Spring, Neil
Riley, George F.
Published in:
Passive and Active Measurement, 6579, 21-31
Presented at:
Passive and Active Measurement, Atlanta, GA, USA, March 20-22, 2011
Year:
2011
Publisher:
Berlin, Heidelberg, Springer Berlin Heidelberg
Laboratories:




 Record created 2012-01-03, last modified 2018-09-13

Postprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)