ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (7): 1533-1543.doi: 10.7544/issn1000-1239.2021.20200672

• 系统结构 • 上一篇    下一篇

一种面向工业边缘计算应用的缓存替换算法

张雷1,李琳1,陈鸿龙2,Daniel,Bovensiepen3   

  1. 1(南京邮电大学物联网学院 南京 210009);2(中国石油大学(华东)控制科学与工程学院 山东青岛 266580);3(西门子中国研究院 北京 100102) (lei.z@njupt.edu.cn)
  • 出版日期: 2021-07-01
  • 基金资助: 
    国家自然科学基金项目(61772551)

A Cache Replacement Algorithm for Industrial Edge Computing Application

Zhang Lei1, Li Lin1, Chen Honglong2, Daniel Bovensiepen3   

  1. 1(College of Internet of Things, Nanjing University of Posts and Telecommunications, Nanjing 210009);2(College of Control Science and Engineering, China University of Petroleum, Qingdao, Shandong 266580);3(Corporate Technology, Siemens China Ltd., Beijing 100102)
  • Online: 2021-07-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61772551).

摘要: 工业应用对数据传输的确定性有严格要求,有必要通过合理的缓存策略保障工业边缘网络的实时服务性能保障.首先面向工业边缘计算应用场景阐述了边缘缓存问题模型.然后分析了工业应用中用户请求的动态性特点,结合工业用户请求的特征属性,给出用户请求内容流行度变化的预测方法.在此基础上提出了基于属性特征流行度预测的缓存替换(combing periodic popularity prediction and size caching strategy, PPPS)算法,根据最近周期窗口内主导属性特征的热度预测值,和尺寸参数一起确定缓存内容价值.实验结果表明:与MPC(most-popular content)、贪婪双尺寸(greedy dual size, GDS)、最近最久未使用(least recently used, LRU)、最近最少访问频次(least frequently used, LFU)、先进先出(first in first out, FIFO)这5种经典算法相比,提出的PPPS算法在缓存命中率和平均延迟2种性能指标下,在不同的用户请求模型、内容大小分布、内容种类参数下均取得最优性能,有效提升了边缘缓存的命中率,提高了缓存利用效率,降低了用户请求内容的延迟.

关键词: 工业应用, 边缘计算, 缓存替换算法, 散粒噪声模型, 流行度预测

Abstract: Industrial applications usually have strict requirements of data transmission certainty. It is therefore essential for industrial edge computing applications to deploy a proper caching strategy at edge nodes, in order to ensure the real-time performance guarantee. The cache optimization problem is formulized considering the specific requirements of industrial applications. The content request is modeled as shot noise model (SNM) to reflect the dynamic characteristics of popularity. A scheme of popularity prediction is then proposed by defining a feature similarity function of the requested content set in the latest periodic time window. Based on it, a new cache replacement algorithm called combing periodic popularity prediction and size caching strategy (PPPS) is proposed. The value of each cache content is determined together with the popularity, size and time updates parameters. The content with minimum value will be deleted with the highest priority when content replacement happens. The experimental results show that the proposed PPPS algorithm outperforms all the 5 baseline algorithms, which are the most popular content (MPC), greedy dual size (GDS), least recently used (LRU), least frequently used (LFU), and FIFO algorithm. PPPS algorithm obtains the best performance of hit rate and the average delay in all the testing cases with different parameter settings on user request models, content size distributions, and content types.

Key words: industrial application, edge computing, cache replacement algorithm, shot noise model (SNM), popularity prediction

中图分类号: