信息中心网络中一种基于内容热度的分区缓存替换方法_李远航.pdf

电子设计工程Electronic Design Engineering第31卷Vol.31第6期No.62023年3月Mar.2023收稿日期：2021-12-17稿件编号：202112111基金项目：中国科学院战略性先导科技专项课题（XDC02070100）作者简介：李远航（1994），男，瑶族，广西桂林人，博士研究生。研究方向：信息中心网络，网内缓存。信息中心网络（ICN）1-2架构致力于解决网络流量暴增的问题，并且能够适应各种新兴技术（如物联网技术3和5G技术4）。网内缓存是ICN的核心功能，可以降低内容的传输时延，减轻源服务器的负载5-6。在缓存空间有限的前提下设计高效的缓存替换算信息中心网络中一种基于内容热度的分区缓存替换方法李远航1，2，王劲林1，2，韩 锐1，2（1.中国科学院声学研究所，北京 100190；2.中国科学院大学，北京 100049）摘要：针对传统的LRU（Least Recently Used）替换策略在信息中心网络的缓存场景中存在难以持久缓存热门内容、缓存性能提升有限的问题，提出了一种基于内容热度的分区缓存替换方法。该方法将缓存空间分成热门区、中间区和冷门区，根据新内容的热度将其插入到对应分区，并在发生缓存替换时选择冷门区的低热度内容进行替换。通过与 LRU、先进先出（First Input First Output，FIFO）、随机替换（Random Replacement，RR）方法进行对比仿真实验，发现该文所提出的方法能够降低热门内容被替换的概率，并显著提高了缓存命中率，降低了内容获取时延。关键词：网内缓存；信息中心网络；缓存替换；LRU中图分类号：TP393.0文献标识码：A文章编号：1674-6236（2023）06-0133-06DOI：10.14022/j.issn1674-6236.2023.06.028A partition cache replacement method based on content popularity ininformationcentric networkingLI Yuanhang1，2，WANG Jinlin1，2，HAN Rui1，2（1.Insitute of Acoustics，Chinese Academy of Sciences，Beijing 100190，China；2.University of ChineseAcademy of Sciences，Beijing 100049，China）Abstract:Aiming at the problems that the traditional LRU(Least Recently Used)replacement strategy isdifficult to cache popular content for a long time and the cache performance is limitedin the cachescenario of informationcentric networks，a partition cache replacement method based on content popularity is proposed in this paper.In the proposed method，the cache space is divided into popular，middleand unpopular areas.New content is inserted into the corresponding partition according to the popularityof the new content，and the lowpopularity content in the unpopular area is selected for replacement whenthe cache replacement occurs.Compared with LRU，FIFO(First Input First Output)and RR(RandomReplacement)methods，the simulation results show that the proposed method can reduce the probabilityof popular content being replaced and significantly improve the cache hit ratio.The content acquisitiondelay is also reduced.Keywords:innetwork caching；informationcentric networking；cache replacement；LRU-133电子设计工程 2023年第6期法，从而提高缓存命中率，是保障信息中心网络缓存性能的关键7。目前的缓存替换方法难以持久缓存热门内容，对缓存性能提升有限。针对上述问题，该文提出了一种基于内容热度的分区缓存替换方法，将缓存空间进行分段，并根据内容的访问情况放置于不同的段中，以保存流行的内容和替换冷门的内容。仿真结果显示，该方法能够持续缓存热门的内容，提升缓存的性能。1相关工作LRU是ICN缓存中最常采用的替换方法，它使用一个链表结构维护所缓存的内容。当内容在缓存中被命中，或者新内容加入缓存时，将内容加入到链表首部；当缓存空间已满，则从链表尾部选出被替换的内容。FIFO是另一种常见的缓存替换方法，通过维护一个先进先出的列表，新内容加入列表首部，优先替换列表尾部的内容，但是 FIFO不能避免流行的内容被替换。随机替换方法（RR）通过随机选择某一内容进行替换，由于随机选取替换目标，导致该方法的性能不稳定。基于内容大小的缓存替换方法（SIZE）在缓存空间已满时，每次都选择占用空间最大的内容进行替换，当被替换的内容是流行的内容时，反而导致缓存命中率的降低。LFU方法选择访问频率最低的内容进行替换，但是由于需要频繁更新内容的访问频率，消耗了额外的计算资源和空间资源。部分研究人员尝试在上述经典替换算法的基础上，提出进一步的改进和优化。Ooka等人提出了一种低开销的缓存替换方法8，采用环形链表而不是双链表管理内容，通过只使用比传统替换方法（例如LRU）少一半以上的内存，达到了与之相接近的网络性能。Sun等人提出了一种优化的缓存替换方法9，计算每个内容的权重，缓存权重高的内容并替换权重低的内容。这种方法需要实时计算并比较内容的权重，需要消耗更多的计算资源。2基于内容热度的分区缓存替换方法传统 LRU 算法用链表结构维护缓存的内容，并默认将最新被访问的内容放到链表头部。当大量不流行的内容在近期被集中访问或者缓存时，会将之前流行的内容替换出去，从而导致缓存性能的下降。对于 LRU替换方法，最理想的状态是从链表头部到链表尾部，其记录内容的热度依次下降，可是LRU 无法保证流行的内容不被替换。在该文中，利用缓存路由器计算的内容热度信息，提出了一种基于内容热度的分区缓存替换方法，可以更好地保存流行的内容，替换不流行的内容。传统 LRU 缓存算法可以分为三种操作：1）插入新内容索引；2）更新内容索引；3）删除内容索引，其示意图如图1所示。图1传统LRU缓存方法在LRU中，当缓存路由器缓存一个新内容时，会触发操作 1；而当缓存空间已满时，执行操作 1会触发操作3；当内容的请求在缓存路由器的缓存中命中时，会触发操作 2。对于操作 1，由于不知道新缓存的内容是否在接下来是流行的，所以直接将内容索引添加到链表首部是不合适的。此外，LRU 此前已经缓存了部分内容，并且链表的索引顺序已经反应了一定的内容热度趋势，需要根据新缓存的内容的热度确定插入链表的具体位置。基于如上两个原因，执行操作 1时，应该根据新内容的热度信息来选择添加到缓存空间的位置，这就需要考虑对原有的缓存空间进行分区处理。对于操作 2，传统 LRU 算法会将被命中的内容索引移动到链表首部，而不考虑内容索引之前的状态信息，而由于在链表中的不同位置体现了内容索引不同的热度情况，所以可以根据链表位置的不同，对被命中的内容索引执行不同的操作。对于操作3，为了避免流行的内容被删除而不流行的内容被保留，可以在一个小的区间内根据内容的热度信息，选择热度低的内容进行替换。根据上述传统 LRU 的三个步骤进行优化，提出了基于内容热度的分区缓存替换方法，其示意图如图2所示。所提出的替换方法，其本质是让热门的内容尽量保存在缓存中，并且在发生缓存替换时，优先替换冷门的内容。首先，在LRU的链表结构的基础上，进一步分为相同大小的三段区域，依次称为热门区、中间区和冷门区，分别对应 LRU的链表首部、中部、尾部区域。将链表进行分区有几个明显的好处：首先，-134可以利用内容的热度信息，对内容进行分区管理。对于热门的内容，希望它能保存在热门区，而对于冷门的内容则反之。其次，在删除内容时可以在冷门区内进行检索，以删除合适的内容，并且减轻了全局搜索导致的开销。最后，内容索引的位置更新可以根据所在位置进行不同的操作，而不是不论内容是否流行都将其放到链表首部。进行如上操作需要缓存路由器统计缓存内容的热度，并且在缓存路由器缓存新内容时需要知道新内容的热度。缓存路由器可以通过记录内容的被请求数目，以此表示内容的热度。根据不同场景的需要，也可以采用更精确的热度预测算法10-11。当内容在缓存路由器被命中时，这个内容在传输时可以携带热度信息，交由路径上的缓存路由器缓存时使用；当内容在源服务器中被命中时，认为这类内容具有一个预先设置的初始热度。通过这种方式，缓存路由器之间进行了隐式的路径协同，下游从上游获取了传输内容的热度信息。基于上述分析，提出了基于内容热度的分区缓存替换方法。为了简便，在下文中称呼所提出的基于内容热度的分区缓存替换方法为PB-S（Popularity-based-Segmented）。当缓存路由器收到一个新的内容，不同于 LRU直接将内容索引放置在链表首部的操作，PB-S将比较该内容的热度和原有缓存内容的热度，根据比较结果确定将新内容放置在热门区、中间区或者冷门区。在该文中，记录当前状态下，热门区末端和中间区末端内容的热度。若新内容的热度高于热门区末端内容的热度，则将新内容插入到热门区首部；若新内容的热度低于热门区末端内容的热度但高于中间区末端内容的热度，则将新内容插入到中间区首部；若两次比较结果中新内容的热度都更低，则直接插入冷门区的首部。当内容索引在缓存中被请求命中时，根据内容所在的不同位置进行不同的操作：当内容索引在冷门区被命中时，PB-S将该内容移到中间区的首部；当内容索引在热门区或者中间区被命中时，PB-S将该内容索引直接移到热门区的首部。当缓存空间已满需要逐出内容时，PB-S从冷门区选择热度低的内容进行替换。目前的 ICN 路由器架构中，为了满足线速转发要求与大容量数据缓存的功能，多采用DRAM+SSD+HDD 的分级缓存系统。如何合理利用不同传输速度的存储介质也需要进一步考虑。通常情况下，缓存内容的索引信息会保存在 DRAM 中，以便于快速检索和管理。而流行的内容应该存储在高传输速度的存储介质中，以便于快速提供内容服务。因此在提出的分区缓存替换方法中，可以让热门区的内容存储在 DRAM 和 SSD 中，让中间区和冷门区的内容存储在HDD中，以此来减少内容服务的缓存响应时延。3仿真实验与分析3.1仿真实验与参数采用 Icarus12模拟器通过仿真实验进一步测试所提出的缓存替换方法的性能。Icarus是一个基于Python的ICN缓存模拟器，专门用于模拟评估ICN缓存场景下的缓存性能。采用 Zipf分布模拟请求数据流，根据文献13-14对于 web内容热度的分析，Zipf分布的值取值为 0.41.0 是合理的。内容的数量设置为 1 000，并且缓存空间比率（网络缓存空间与内容数量的比例）设置为从0.11。设置前10 000次内容请求作为系统的预热，并在之后的 20 000次请求开始正式测量。缓存策略采用LCE。网络拓扑采用了面向研究和教育团体的泛欧洲数据网络GEANT。3.2评价指标此次仿真实验采用缓存命中率以及内容平均获取时延进行性能评价，具体评价指标定义如下：1）内容替换比率是内容进入缓存后最终被替换的比率。可以定义为EvictedRadio=NumEvictedNumCached，其中，NumEvicted为某一内容从缓存中被替换的次数；NumCached为某一内容被缓存的次数。为了提升网络性能，对于流行的内容，希望其更持久地存在于缓存中，即希望流行内容的替换比率更低。2）缓存命中率是由缓存提供内容服务的比例。可以定义为CacheHitRatio=NumcachehitNum，其中，Numcachehit为从缓存路由器中获得内容的用户请求数；Num为用户总请求总数。缓存命中率越高，代表缓存的资源利用率越高，源服务器的负载也越低。图2基于内容热度的分区缓存替换方法李远航，等信息中心网络中一种基于内容热度的分区缓存替换方法-135电子设计工程 2023年第6期3）网络平均时延是用户从发出请求到收到内容的平均时间。网络平均时延越低，用户体验越好。3.3仿真结果分析1）热度机制有效性分析在上一节中，分析了在新内容插入以及内容替换时可以利用热度信息。具体来说，在新内容插入时，PB-S 利用新内容的热度判断新内容插入热门区、中间区还是冷门区；在内容替换时，PB-S搜索冷门区的内容，选择热度最低的内容进行替换。为了评价这两部分使用的热度信息是否有帮助，以及验证所提出方法中对应步骤的有效性，首先进行了对比实验，结果如图3所示。图3在缓存替换中使用热度信息分析的仿真结果图 3(a)、(b)分别表示 Zipf 分布参数变化时网络的缓存命中率和网络平均时延的变化情况，图 3(c)、(d)分 别 表 示 缓 存 空 间 比 率 变 化 时 网 络的 缓存命中率和网络平均时延的变化情况。其中，PB-S 是上文提出的缓存替换方法，PB-S(1)在插入新内容时直接插入到整个链表首部（即热门区首部），其他步骤与 PB-S 一致；PB-S(2)在发生内容替换时直接替换掉整个链表尾部的内容（即冷门区尾部内容），其他步骤与 PB-S 一致。实验结果表明，在不同的 Zipf 分布参数、不同的缓存空间比率下，PB-S(2)比 PB-S(1)的缓存命中率略高，网络平均时延略低，这代表选择热度低的内容进行替换带来了更大的好处。而 PB-S 在两个步骤都使用了热度信息，给网络性能带来了更明显的提升。2）内容排名与内容替换比率的关系为了验证所提方法能否持久缓存热门的内容，分析不同排名内容的替换比率。内容的排名越高，则更为热门，具有更高的热度。如果一个内容具有较低的替换比率，则意味着这个内容具有更高的概率持续留在缓存中。因此可以分析采用不同的缓存替换方法，对应的内容排名和内容替换比率的关系。理想的缓存替换方法，内容的排名越高，其替换比率应该越低。在仿真实验中，将内容 Zipf分布参数固定为 0.7，将缓存空间比率固定为 0.5，分析不同缓存替换方法下，内容的排名与内容替换比率的关系。在内容集里，将内容根据热度降序排列，得到内容的排名，排名为 1 的内容热度最高。统计了不同缓存替换方法下，排名前 1 000内容的替换比率，最终得到如图4所示的仿真结果。-136图4内容的排名与内容替换比率的关系从图4可以看出，在PB-S中，排名处于前列的内容具有明显更低的内容替换比率，并且随着内容的排名增加，其替换比率的增加幅度逐渐减小，可以看作是沿横坐标轴镜像的 Zipf 分布曲线。因此 PB-S较好地实现了将流行的内容保存在缓存中，并且将不流行的内容替换掉。相比之下，在 LRU、FIFO 和RR中，内容替换比率随着内容排名的改变的变化不大。在LRU中，对于最为流行的内容，其内容替换比率有些微的下降，但未与排名靠后的内容的替换比率有明显的区分，可能是因为 LRU会默认将新缓存的内容插入在链表首部，增大了流行的内容移动到链表尾部并被替换掉的概率。3）不同缓存替换方法的性能对比分别进行两组参数设置：首先将内容的缓存空间比率固定为 0.5，改变 Zipf分布参数；之后将内容的 Zipf 分布参数固定为 0.7，改变缓存空间比率，最终得到的仿真结果如图 5所示。其中，图 5(a)表示缓存命中率随变化的关系，图 5(b)表示网络平均时延随变化的关系。图 5(c)表示缓存命中率随缓存空间比率变化的关系，图 5(d)表示网络平均时延随缓存空间比率变化的关系。图5不同缓存替换方法的网络性能对比实验结果根据图 5(a)，增加时，所有的缓存替换方法都能得到更高的缓存命中率，这是因为请求都集中于少数流行的内容，而不同的替换方法都能够在一定程度内保留这些内容在缓存中。四种替换方法的变化趋势比较相似，而相对于其他方法，PB-S 在不同的值下都保持了更高的缓存命中率，体现了PB-S的有效性。通过图 5(b)可以发现，随着增加，不同替换方法的网络平均时延都得到了下降。PB-S 的平均时延明显低于其他缓存替换方法，因为PB-S通过分区李远航，等信息中心网络中一种基于内容热度的分区缓存替换方法-137电子设计工程 2023年第6期的方式，可以更好地避免流行的内容被不流行的内容替换，持久地将流行内容保留在缓存中。三种对比方法的平均时延比较接近，其中 LRU在更大时的优势更明显。从图 5(c)可以得到，当缓存空间比率增大时，所有的缓存替换方法的缓存命中率都得到了提升。这是因为缓存路由器配备了更大的缓存空间，因而缓存了更多的内容，最终使得更多请求在缓存内部被命中。而对比不同的缓存替换方法，PB-S都具有更高的缓存命中率，且比其他缓存替换方法高 0.1 左右。从这里能够看出来，基于内容热度的分区缓存替换方法对不同区间的内容执行不同的操作，能够更好地保存流行的内容，并替换掉不流行的内容。LRU 与随机替换（RR）的效果类似，并略好于 FIFO，这是随着更多新内容被缓存，之前流行的内容即使被多次命中，也必然随着入队的顺序出队。根据图 5(d)的结果，当缓存空间比率增大时，所有缓存替换方法的平均时延都得到了下降。PB-S相对于其他方法，保持了约 15 ms的优势，这意味着用户可以从更近的缓存路由器中获取内容。当缓存空间更大时，RR能够带来比LRU更低的平均时延。通过分析比较不同的 Zipf分布参数下以及不同的缓存空间比率各缓存替换方法的性能可以发现，PB-S 能带来更高的缓存命中率和更低的网络平均时延。这主要是由于PB-S通过分区的方式，将新缓存内容的索引根据热度放置在不同分区，而不是整个链表的首部，能避免不流行的内容将流行的内容挤出热门区，造成不流行的内容被缓存而流行的内容被替换。此外，PB-S 选择热度低的内容进行替换，进一步保障了热度高的内容留在缓存中。综上所述，PB-S 作为一个轻量级的缓存替换方法，适合部署于ICN实际场景中。4结论该文针对 ICN 网内缓存场景中的缓存替换问题，首先对比分析几种ICN缓存替换方法的优缺点，根据 LRU存在的问题，提出了一种基于内容热度的分区缓存替换方法。通过仿真实验，分析了利用热度信息进行缓存替换的有效性，并将提出的缓存替换方法与 LRU、FIFO、RR 进行了对比。实验结果表明，该文所提出的缓存替换方法能够缓存流行的内容，替换不流行的内容。在不同的内容热度分布、缓存空间配置的场景下，该文所提出的缓存替换方法都具有更高的缓存命中率和更低的内容获取时延。在之后的工作中，会进一步分析更多维度的信息，如网络拓扑信息15-19、转发流量信息等，应用于缓存替换方法中。参考文献：1 王劲林,程钢,尤佳莉,等.SEANet:一种现场、弹性、自治网络架构及技术J.网络新媒体技术,2020,9(6):1-8.2 黄韬,刘江,霍如,等.未来网络体系架构研究综述J.通信学报,2014,35(8):14.3 段洁,胡显静,林欢,等.面向物联网数据特征的信息中心网络缓存方案J.电子与信息学报,2021,43(8):2240-2248.4 戈丽平,周金和.面向5G-ICN切片的分层缓存策略EB/OL.2022-02-10.http:/ Lal N,Kumar S,Kadian G,et al.Caching methodo-logies in Content Centric Networking(CCN):a surveyJ.Computer Science Review,2019(31):39-50.6 张国强,李杨,林涛,等.信息中心网络中的内置缓存技术研究J.软件学报,2014,25(1):154-175.7 王永功,李振宇,武庆华,等.信息中心网络内缓存替换算法性能分析与优化J.计算机研究与发展,2015,52(9):2046-2055.8 Ooka A,Eum S,Ata S,et al.Compact CAR:low-overhead cache replacement policy for an ICNrouterJ.IEICE Transactions on Communications,2018,101(6):1366-1378.9 Sun X,Wang Z.An optimized cache replacement al-gorithm for information-centric networksC.IEEEInternational Conference on Smart City/socialcom/sustaincom.IEEE,2015:683-688.10武维,李泽平,杨华蔚,等.融合内容特征和时序信息的深度注意力视频流行度预测模型J.计算机应用,2021,41(7):1878-1884.11曹婍,沈华伟,高金华,等.基于深度学习的流行度预测研究综述J.中文信息学报,2021,35(2):1-18,32.12Saino L,Psaras I,Pavlou G.Icarus:a caching simulatorfor Information Centric Networking(ICN)C.Simu-Tools.ICST,2014:66-75.13Guillemin F,Kauffmann B,Moteau S,et al.Experi-（下转第143页）-138参考文献：1 袁静,李柯.移动社交媒体环境下用户信息焦虑行为研究进展J.图书情报工作,2020(11):135-146.2 郑东和,孟艳芳.人格特质、生活满意度、错失焦虑症对短视频依赖的关系研究J.新闻传播,2021(10):4-6.3 钱进.多粒度决策粗糙集模型研究J.郑州大学学报(理学版),2018(1):36-41.4 Widiantoro A D,Hendra Prasetya F,Harnadi B.Exa-mining the adoption of mobile payment service:Expectation confirmation model with trustC.2021Sixth International Conference on Informatics andComputing(ICIC),2021:1-5.5 Duanmu Z,Ma K,Wang Z.Quality-of-Experiencefor adaptive streaming videos:an expectation confi-rmation theory motivated approachJ.IEEE Trans-actions on Image Processing,2018(12):6135-6146.6 马志浩,葛进平,周翔.网络直播用户的持续使用行为及主观幸福感基于期望确认模型及准社会关系的理论视角J.新闻与传播评论,2020,73(2):29-46.7 邬阳阳,汤建国.大数据背景下粗糙集属性约简研究进展J.计算机工程与应用,2019(6):37-44,183.8 徐曼,吴肖,潘婷,等.内容类移动社交媒体环境下用户错失焦虑影响因素研究J.情报理论与实践,2021,44(4):153-161.9 骆公志,许鑫鑫.基于覆盖的多重代价粗糙决策分析方法J.计算机科学,2019(5):216-220.10陈家俊,徐华丽,魏赟.多重代价多粒度决策粗糙集模型研究J.计算机科学与探索,2018(5):163-174.11吴伟志.多粒度粗糙集数据分析研究的回顾与展望J.西北大学学报(自然科学版),2018(4):31-42.12侯成军,米据生,梁美社.基于局部可调节多粒度粗糙集的属性约简J.计算机科学,2020(3):95-99.13刘瑶瑶.面向不完备信息的局部粗糙集方法研究D.西安:西安石油大学,2020.14鞠恒荣.面向态势认知的粗糙集决策方法研究D.南京:南京大学,2019.15Pescaroli G,Velazquez O,Alcntara-Ayala I,et al.Alikert scale-based model for benchmarking oper-ational capacity,organizational resilience,and dis-asterriskreductionJ.InternationalJournalofDisaster Risk Science,2020(3):158-163.16Yao Y Y.The geometry of three-way decisionJ.Applied Intelligence,2021,51(9):6298-6325.(通信作者：鞠恒荣，)（上接第138页）mental analysis of caching efficiency for YouTubetraffic in an ISP networkC.Proceedings of the2013 25th International Teletraffic Congress(ITC).IEEE,2013:1-9.14SarrarN,UhligS,FeldmannA,etal.LeveragingZipfs law for traffic offloadingJ.ACM SIGCOMMComputer Communication Review,2012,42(1):16-22.15朱敬成,刘辉,王伦文,等.基于网络拓扑重合度的关键节点识别方法J.计算机应用研究,2021,38(12):3581-3585.16周任军,王文晶.基于深度神经网络的网络流量预测模型仿真J.计算机仿真,2021,38(6):475-479.16丁津津,谢民,高博,等.变电站多跳无线网络拓扑优化与通信可靠性控制研究J.电力信息与通信技术,2022(5):61-67.17朱显辉,于越,师楠,等.BP神经网络的分层优化研究及其在风电功率预测中的应用J.高压电器,2022,58(2):158-163,170.18刘文霞,黄钰辰,万海洋,等.复杂网络理论在能源互联网脆弱性与鲁棒性研究中的应用J.智慧电力,2021,49(1):14-21.19纪鹏志,董振,付开强,等.配电线路接点温度远程监测与预测系统J.工业仪表与自动化装置,2022(1):76-81.蔡天使，等基于多粒度粗糙集的微媒体错失焦虑分析研究-143