Zadnik, Martin
[Brno University of Technology]
Canini, Marco
[UCL]
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.
- Feldmann A., Greenberg A., Lund C., Reingold N., Rexford J., True F., Deriving traffic demands for operational IP networks: methodology and experience, 10.1109/90.929850
- Estan, C., Varghese, G.: New Directions in Traffic Measurement and Accounting: Focusing on the Elephants, Ignoring the Mice. Trans. Comp. Syst. 21(3) (2003)
- Bu T., Cao J., Chen A., Lee P. P. C., A Fast and Compact Method for Unveiling Significant Patterns in High Speed Networks, 10.1109/infcom.2007.220
- Ramachandran Anirudh, Seetharaman Srinivasan, Feamster Nick, Vazirani Vijay, Fast monitoring of traffic subpopulations, 10.1145/1452520.1452551
- Canini Marco, Li Wei, Zadnik Martin, Moore Andrew W., Experience with high-speed automated application-identification for network-management, 10.1145/1882486.1882539
- McKeown Nick, Anderson Tom, Balakrishnan Hari, Parulkar Guru, Peterson Larry, Rexford Jennifer, Shenker Scott, Turner Jonathan, OpenFlow : enabling innovation in campus networks, 10.1145/1355734.1355746
- Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston (1989)
- Kaufmann Paul, Plessl Christian, Platzner Marco, EvoCaches: Application-specific Adaptation of Cache Mappings, 10.1109/ahs.2009.26
- Karedla R., Love J.S., Wherry B.G., Caching strategies to improve disk system performance, 10.1109/2.268884
- Zadnik Martin, Canini Marco, Moore Andrew W., Miller David J., Li Wei, Tracking elephant flows in internet backbone traffic with an FPGA-based cache, 10.1109/fpl.2009.5272387
- Molina Maurizio, A scalable and efficient methodology for flow monitoring in the Internet, Providing Quality of Service in Heterogeneous Environments, Proceedings of the 18th International Teletraffic Congress - ITC-18 (2003) ISBN:9780444514554 p.271-280, 10.1016/s1388-3437(03)80172-5
- Shannon, C., et al.: The caida anonymized 2008 internet traces (2008), http://www.caida.org/data/passive/passive_2008_dataset.xml
Bibliographic reference |
Zadnik, Martin ; Canini, Marco. Evolution of Cache Replacement Policies to Track Heavy-hitter Flows.PAM '11In: Proceedings of the 12th Passive and Active Measurement Conference, 2011 |
Permanent URL |
http://hdl.handle.net/2078.1/139435 |