Abstract
The increase in internet traffic amount becomes a serious problem for routers from the aspects of the packet processing throughput and the power consumption. Packet processing cache (PPC) is a promising approach to meet the requirements. PPC can reduce the number of accesses to ternary content addressable memory (TCAM), which accounts for a large percentage of the power consumption of a router, by storing the TCAM lookup results into a cache memory and reusing them. For PPC, the cache miss rate has significant impact on the throughput and the power consumption. Thus, reducing the number of cache misses is a main concern for PPC. In this study, we first analyze the elephant flows and mice flows in networks to reveal the packet behavior in PPC and propose a novel cache replacement policy based on the analysis. Hit dominance cache (HDC), proposed in this paper, gives high priority to the elephant flows and evicts the mice flows rapidly. Our simulation showed HDC can reduce the number of cache misses in PPC by up to 29.1% compared to conventional 4-way LRU PPC. In addition, we estimated the hardware cost of HDC by using Verilog-HDL and showed that it is comparable to those of 4-way LRU though HDC performs as if the cache was composed of 8-way set associative cache.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
The Ministry, “Tabulation and Estimation of Internet Traffic in Japan,” (2016). http://www.soumu.go.jp/main_content/000462459.pdf. Accessed 16 Mar 2017
METI, “Green IT Initiative in Japan”. http://www.meti.go.jp/english/policy/GreenITInitiativeInJapan.pdf. Accessed 16 Mar 2017
Fan, J., Hu, C., He, K., Jiang, J., Liuy, B.: Reducing power of traffic manager in routers via dynamic on/off-chip scheduling. In: 2012 Proceedings of IEEE INFOCOM, Orlando, FL, pp. 1925–1933 (2012)
Zheng, X., Wang, X.: Comparative study of power consumption of a NetFPGA-based forwarding node in publish–subscribe Internet routing. Comput. Commun. 44, 36–43 (2014)
Gamage, S., Pasqual, A.: High performance parallel packet classification architecture with popular rule caching. In: 2012 18th IEEE International Conference on Networks (ICON), Singapore, pp. 52–57 (2012)
Agrawal, B., Sherwood, T.: Ternary CAM power and delay model: extensions and uses. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 16(5), 554–564 (2008)
Nawa, M. et al.: Energy-efficient high-speed search engine using a multi-dimensional TCAM architecture with parallel pipelined subdivided structure. In: 2016 13th IEEE Annual Consumer Communications & Networking Conference (CCNC), Las Vegas, NV, pp. 309–314 (2016)
Hewlett-Packard Development Company: Energy Efficient Networking - Business white paper (2011). http://h17007.www1.hp.com/docs/mark/4AA3-3866ENW.pdf. Accessed 16 Mar 2017
Girish, C., Govindarajan, R.: Improving performance of digest caches in network processors. In: Proceedings of the 15th International Conference on High performance computing (HiPC 2008), India, pp. 6–17 (2008)
Agrawal, B., Sherwood, T.: Modeling TCAM power for next generation network devices. In: 2006 IEEE International Symposium on Performance Analysis of Systems and Software, pp. 120–129 (2006)
Belady, L.A.: A study of replacement algorithms for a virtual-storage computer. IBM Syst. J. 5(2), 78–101 (1966)
Chang, F., Feng, W.C., Li, K.: Efficient packet classification with digest caches. In: Proceedings of Third Workshop Network Processors and Applications (NP-3) (2005)
Ata, S., Murata, M., Miyahara, H.: Efficient cache structures of IP routers to provide policy-based services. In: IEEE International Conference on Communications (ICC 2001), Helsinki, vol. 5, pp. 1561–1565 (2001)
Li, K., Chang, F., Berger, D., Wu-chang, F.: Architectures for packet classification caching. In: The 11th IEEE International Conference on Networks (ICON2003), Sydney, pp. 111–117 (2003)
Kim, N., Jean, S., Kim, J., Yoon, H.: Cache replacement schemes for data-driven label switching networks. In: 2001 IEEE Workshop on High Performance Switching and Routing, Dallas, TX, pp. 223–227 (2001)
Yamaki, H., Nishi, H.: An improved cache mechanism for a cache-based network processor. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2012), Las Vegas, NV, pp. 1–7 (2012)
Yamaki, H., Nishi, H.: Line replacement algorithm for l1-scale packet processing cache. In: Adjunct Proceedings of the 13th International Conference on Mobile and Ubiquitous Systems: Computing Networking and Services (MOBIQUITOUS), Hiroshima, Japan, pp. 12–17 (2016)
Mori, T., Uchida, M., Kawahara, R., Pan, J., Goto, S.: Identifying elephant flows through periodically sampled packets. In: Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement (IMC 2004), pp. 115–120. ACM, New York (2004)
Okuno, M., Nishi, H.: Network-processor acceleration-architecture using header-learning cache and cache-miss handler. In: The 8th World Multi-Conference on Systemics, Cybernetics and Informatics (SCI2004), pp. 108–113
RIPE Network Coordination Centre: Réseaux IP Européens Network Coordination Centre RIPE NCC. http://www.ripe.net/. Accessed 16 Mar 2017
WIDE MAWI WorkingGroup: MAWI Working Group Traffic Archive. http://mawi.wide.ad.jp/mawi/. Accessed 17 Aug 2016
Karedla, R., Love, J.S., Wherry, B.G.: Caching strategies to improve disk system performance. Computer 27(3), 38–46 (1994)
North Carolina State University: FreePDK45:Contents. http://www.eda.ncsu.edu/wiki/FreePDK45:Contents. Accessed 1 Sept 2017
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Yamaki, H. (2019). Flow Characteristic-Aware Cache Replacement Policy for Packet Processing Cache. In: Arai, K., Kapoor, S., Bhatia, R. (eds) Advances in Information and Communication Networks. FICC 2018. Advances in Intelligent Systems and Computing, vol 886. Springer, Cham. https://doi.org/10.1007/978-3-030-03402-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-03402-3_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03401-6
Online ISBN: 978-3-030-03402-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)