面向网络流量的缓存替换算法比较与分析

doi:10.3969/j.issn.1006-2475.2019.08.010

计算机与现代化

面向网络流量的缓存替换算法比较与分析

(1. 中国科学院声学研究所国家网络新媒体工程技术研究中心，北京100190；
2. 中国科学院大学电子电气与通信工程学院，北京100049)

收稿日期:2018-11-21 出版日期:2019-08-15 发布日期:2019-08-16
作者简介:曹作伟(1991-)，男，湖南安乡人，博士研究生，研究方向：软件定义网络，可编程数据平面，E-mail: caozw@dsp.ac.cn；陈晓(1964-)，男，研究员，硕士,研究方向:网络通信,新媒体技术；倪宏(1964-)，男，研究员，硕士，研究方向:网络通信,新媒体技术。
基金资助:
国家科技重大专项资助项目(2017ZX03001019)

Comparison and Analysis of Cache Replacement Algorithms for Network Traffic

(1. National Network New Media Engineering Research Center, Institute of Acoustics,
Chinese Academy of Sciences, Beijing 100190, China; 2. School of Electronic, Electrical and Communication
Engineering, University of Chinese Academy of Sciences, Beijing 100049, China)

Received:2018-11-21 Online:2019-08-15 Published:2019-08-16

摘要/Abstract

摘要： 缓存替换算法对优化网络处理应用的性能起到关键作用，但目前面向网络流量的缓存替换算法研究主要集中在算法设计和领域应用方面，较少有文献对现有的缓存替换算法在网络环境下的性能进行分析比较。对此，本文针对主要的6种缓存替换算法进行分析和比较。通过分析网络流量的新近度与频度特征，为基于最近最少使用(Least Recently Used, LRU)和最近最不常使用(Least Frequently Used, LFU)的缓存替换算法给出实际依据。对仿真环境和实际系统的实验结果表明，类LRU算法较LFU算法更适用于网络流量，而缓存空间较大时，随机替换算法较LRU算法更适用于多核环境。

关键词: 网络流量特征, 缓存替换算法, LRU算法, LFU算法

Abstract: The cache replacement algorithm plays a key role in optimizing the performance of network processing applications. The research on cache replacement algorithms for network traffic is mainly concentrated on the design and application of cache replacement algorithm. Yet analysis and comparative study for the performance of the existing cache replacement algorithm in the network environment are fewer. This paper analyzes and compares six major cache replacement algorithms. By analyzing the recency and frequency characteristics of network traffic, the practical basis for the cache replacement algorithm based on Least Recently Used (LRU) and Least Frequently Used (LFU) is given. The experimental results of the simulation environment and the actual system show that the LRU-like algorithm is more suitable for network traffic than the LFU algorithm, and the random replacement algorithm is more suitable for the multi-core environment than the LRU algorithm.

Key words: network traffic characteristics, cache replacement algorithm, LRU algorithm, LFU algorithm

中图分类号:

TP393.04

曹作伟1,2,陈晓1,倪宏1 . 面向网络流量的缓存替换算法比较与分析[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.08.010.

CAO Zuo-wei1,2,CHEN Xiao1,NI Hong1 . Comparison and Analysis of Cache Replacement Algorithms for Network Traffic[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.08.010.

参考文献

［1］ CLAFFY K C. Internet Traffic Characterization［D］. San Diego： University of California, 1994. ［2］ FELDMEIER D C. Improving gateway performance with a routing-table cache［C］// Proceedings of IEEE International Conference on Computer Communications. 1988:298-307. ［3］ TALBOT B, SHERWOOD T, LIN B. IP caching for terabit speed routers［C］// IEEE Global Telecommunications Conference. 1999,2:1565-1569. ［4］ LIU H. Routing prefix caching in network processor design［C］// Proceedings of the 10th International Conference on Computer Communications and Networks. 2001:18-23. ［5］ AKHBARIZADEH M J, NOURANI M. Efficient prefix cache for network processors［C］// Proceedings of the 12th Annual IEEE Symposium on High Performance Interconnects. 2004:41-46. ［6］ HUANG Z, LIU G, PEIR J-K. Greedy prefix cache for IP routing lookups［C］// 2009 10th IEEE International Symposium on Pervasive Systems, Algorithms, and Networks. 2009:92-97. ［7］ XU J, SINGHAL M, DEGROAT J. A novel cache architecture to support layer-four packet classification at memory access speeds［C］// Proceedings of IEEE International Conference on Computer Communications. 2000,3:1445-1454. ［8］ DONG Q, BANERJEE S, WANG J, et al. Wire speed packet classification without Tcams: A few more registers (and a bit of logic) are enough［C］// Proceedings of 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 2007:253-264. ［9］ PFAFF B, PETTIT J, KOPONEN T, et al. The design and implementation of open vSwitch［C］// The 12th USENIX Symposium on Networked Systems Design and Implementation. 2015:117-130. ［10］JACKSON E J, WALLS M, PANDA A, et al. Softflow: A middlebox architecture for open vSwitch［C］// 2016 USENIX Annual Technical Conference. 2016:15-28. ［11］JOHNSON T, SHASHA D. 2Q: A low overhead high performance buffer management replacement algorithm［C］// Proceedings of VLDB-94. 1994:439-450. ［12］YU M, REXFORD J, FREEDMAN M J, et al. Scalable flow-based networking with DIFANE［C］// Proceedings of ACM SIGCOMM 2010 Conference. 2010:351-362. ［13］ZADNIK M, CANINI M. Evolution of cache replacement policies to track heavy-hitter flows［C］// 2010 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. 2010:1-2. ［14］PAN T, GUO X, ZHANG C, et al. ALFE: A replacement policy to cache elephant flows in the presence of mice flooding［C］// 2012 IEEE International Conference on Communications. 2012:2961-2965. ［15］LEE B S, KANAGAVELU R, AUNG K M M. An efficient flow cache algorithm with improved fairness in software-defined data center networks［C］// 2013 IEEE 2nd International Conference on Cloud Networking. 2013:18-24. ［16］NARAYANA S, SIVARAMAN A, NATHAN V, et al. Language-directed hardware design for network performance monitoring［C］// Proceedings of ACM Special Interest Group Conference on Data Communication. 2017:85-98. ［17］KATTA N, ALIPOURFARD O, REXFORD J, et al. Infinite cache flow in software-defined networks［C］// Proceedings of the 3rd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. 2014:175-180. ［18］SHELLY N, JACKSON E J, KOPONEN T, et al. Flow caching for high entropy packet fields［C］// Proceedings of the 3rd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. 2014:151-156. ［19］李平,王雷. 融合SDN的信息中心网络研究综述［J］. 网络新媒体技术, 2017(6):11-18. ［20］SHAH K, MITRA A, MATANI D. An O(1) algorithm for implementing the LFU cache eviction scheme［EB/OL］. (2010-08-16)［2018-09-27］. https:// dhruvbird.com/lfu.pdf. ［21］CAIDA. The CAIDA Anonymized Internet Traces 2016 Dataset［EB/OL］. ［2018-01-03］. http://www.caida.org/data/passive/passive_2016_dataset.xml. ［22］SONG H. Protocol-oblivious forwarding: Unleash the power of SDN through a future-proof forwarding plane［C］// Proceedings of the 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. 2013:127-132. ［23］曹作伟,陈晓,倪宏,等. 应用于协议无感知转发交换机的流缓存方法［J］. 电子与信息学报, 2018,40(11):2772-2778.

[1]	曹文君，薛善良. AODV协议路由维护改进方案[J]. 计算机与现代化, 2016, 0(8): 86-90+96.
[2]	郝平. 基于混沌映射组播技术的无线移动自组织网络路由研究[J]. 计算机与现代化, 2015, 0(12): 62-.
[3]	唐忠;徐芳媛. IEEE 802.15.4簇树网络实时通信中的冲突避免[J]. 计算机与现代化, 2012, 198(2): 124-127.
[4]	何刚;田森平;田辉平. 基于SIP的移动即时通讯系统[J]. 计算机与现代化, 2010, 1(01): 70-72.
[5]	李永明;. 基于P2P的即时通信系统的研究[J]. 计算机与现代化, 2009, 8(8): 34-39.

面向网络流量的缓存替换算法比较与分析

Comparison and Analysis of Cache Replacement Algorithms for Network Traffic

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价