Flow caching effectiveness in packet forwarding applications

Maciej Jakub Czekaj, Ernest Jamro


Routing algorithms are known to be a potential bottleneck for packet processing. Network flow caching can function as a genneral acceleration technique for packet processing workloads. The goal of this article is to evaluate the effectiveness of packet flow caching techniques in high-speed networks. The area of focus is data distribution characteristics that lead to effectiveness of caching of network flows (connections). Based on statistical analysis and simulations the article sets necessary conditions for effective use of caches in packet forwarding applications.
Public domain network traces were examined and measured for data locality.
Software simulations show a strong correlation between flow packet distance metric and cache hit rate.


computer networks, caching, SDN

Full Text:



git.kernel.org, ipv4: Delete routing cache.URL https://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git/commit/?id=89aef8921bfbac22f00e04f8450f6e447db13e42.

LBNL/ICSI Enterprise Tracing Project. URL http://www.icir.org/enterprise-tracing/download.html

Napoli University traffic traces, Trace 1 14th June 2004 11:00-12:00. URL http://traffic.comics.unina.it/Traces/ttraces.php.

Security Architecture for the Internet Protocol. URL https://tools.ietf.org/html/rfc430.

WIDE project. URL http://mawi.wide.ad.jp/mawi/.

WITS: Waikato Internet Traffic Storage. URL https://wand.net.nz/wits/.

IEEE Standard for Information Technology- Telecommunications and Informa-tion Exchange Between Systems- Local and Metropolitan Area Networks- Spe-cific Requirements Part 3: Carrier Sense Multiple Access With Collision Detec-tion (CSMA/CD) Access Method and Physical Layer Specifications Amendment:Media Access Control (MAC) Parameters, Physical Layers, and Management Pa-rameters for 10 Gb/S Operation. In: IEEE Std 802.3ae-2002 (Amendment toIEEE Std 802.3-2002), pp. 271–272, 2002. URL http://dx.doi.org/10.1109/IEEESTD.2002.94131.

Network Traffic Characteristics of Data Centers in the Wild.Association for Computing Machinery, Inc.,2010.URLhttps://www.microsoft.com/en-us/research/publication/network-traffic-characteristics-of-data-centers-in-the-wild/.

Adamic L., Huberman B.: Zipfs law and the internet. In: Glottometrics, vol. 3,pp. 143–150, 2002.

Al-Zoubi H., Milenkovic A., Milenkovic M.: Performance evaluation of cachereplacement policies for the SPEC CPU2000 benchmark suite. In: Proceedingsof the 42nd annual Southeast regional conference, pp. 267–272. ACM, 2004.

Asai H., Ohara Y.: Poptrie: A Compressed Trie with Population Count for Fastand Scalable Software IP Routing Table Lookup. 2015. URL http://dx.doi.org/10.1145/2785956.2787474.

Beckmann N., Sanchez D.: Talus: A simple way to remove cliffs in cacheperformance. In: 2015 IEEE 21st International Symposium on High Perfor-mance Computer Architecture (HPCA), pp. 64–75. 2015. ISSN 1530-0897. URLhttp://dx.doi.org/10.1109/HPCA.2015.7056022.

Borgnat P., Dewaele G., Fukuda K., Abry P., Cho K.: Seven Years and OneDay: Sketching the Evolution of Internet Traffic. In: IEEE INFOCOM 2009, pp.711–719. 2009. ISSN 0743-166X. URL http://dx.doi.org/10.1109/INFCOM.2009.5061979.

Ciflikli C., Gezer A., Tuncay Ozsahin A.: Packet traffic features of IPv6 andIPv4 protocol traffic. In: Turkish Journal of Electrical Engineering and Com-puter Sciences, vol. 20, pp. 727–749, 2012. URL http://dx.doi.org/10.3906/elk-1008-696.

Congdon P.T., Mohapatra P., Farrens M., Akella V.: Simultaneously reducinglatency and power consumption in openflow switches. In: IEEE/ACM Transac-tions on Networking (TON), vol. 22(3), pp. 1007–1020, 2014.

Feldmeier D.C.: Improving Gateway Performance with a Routing-Table Cache.2019/02/21; 17:04str.16/18In: Proc. IEEE Infocom?88. 1988.

Gupta P., McKeown N.: Algorithms for packet classification. In: IEEE Network,vol. 15(2), pp. 24–32, 2001. ISSN 0890-8044. URL http://dx.doi.org/10.1109/65.912717.

Katta N., Alipourfard O., Rexford J., Walker D.: Rule-caching algorithms forsoftware-defined networks. In: Techical Report, Princeton University, 2014.

Kim G., Crovella M.: On the Effect of Traffic Self-Similarity on Network Perfor-mance. In: , 1997.

Kim N., Jean S., Kim J., Yoon H.: Cache replacement schemes for data-drivenlabel switching networks. In: 2001 IEEE Workshop on High PerformanceSwitching and Routing (IEEE Cat. No.01TH8552), pp. 223–227. 2001. URLhttp://dx.doi.org/10.1109/HPSR.2001.923636.

McKeown N., Anderson T., Balakrishnan H., Parulkar G., Peterson L., RexfordJ., Shenker S., Turner J.: OpenFlow: Enabling Innovation in Campus Networks.In: SIGCOMM Comput. Commun. Rev., vol. 38(2), pp. 69–74, 2008. ISSN 0146-4833. URL http://dx.doi.org/10.1145/1355734.1355746.

Okuno M., Nishimura S., Ishida S.i., Nishi H.: Cache-based network processorarchitecture: Evaluation with real network traffic. In: IEICE transactions onelectronics, vol. 89(11), pp. 1620–1628, 2006.

Paxson V.: Bro: A System for Detecting Network Intruders in Real-time. In:Comput. Netw., vol. 31(23-24), pp. 2435–2463, 1999. ISSN 1389-1286. URLhttp://dx.doi.org/10.1016/S1389-1286(99)00112-7.

Pfaff B., Pettit J., Koponen T., Jackson E., Zhou A., Rajahalme J., Gross J.,Wang A., Stringer J., Shelar P., Amidon K., Casado M.: The Design and Im-plementation of Open vSwitch. In: 12th USENIX Symposium on NetworkedSystems Design and Implementation (NSDI 15), pp. 117–130. USENIX Associa-tion, Oakland, CA, 2015. ISBN 978-1-931971-218. URL https://www.usenix.org/conference/nsdi15/technical-sessions/presentation/pfaff.

Powell M.D., Agarwal A., Vijaykumar T., Falsafi B., Roy K.: Reducing set-associative cache energy via way-prediction and selective direct-mapping. In:Proceedings of the 34th annual ACM/IEEE international symposium on Microar-chitecture, pp. 54–65. IEEE Computer Society, 2001.

Sikdar B., Vastola K.S.: The Effect of TCP on the Self-Similarity of NetworkTraffic. In: In Proc. of the 35th Conf. on Information Sciences and Systems, pp.21–23. 2001.

Su C.L., Despain A.M.: Cache design trade-offs for power and performance opti-mization: a case study. In: Proceedings of the 1995 international symposium onLow power design, pp. 63–68. ACM, 1995.

DOI: https://doi.org/10.7494/csci.2019.20.2.3185


  • There are currently no refbacks.