CCN路由的缓存机制研究

汤红　李涛　宋哲

摘  要：CCN网络通过待定请求表（Pending Interest Table， PIT）请求源端数据是一个零散的过程，对于首次访问的所有数据必然会带来峰值带宽问题，基于此场景提出一种内容存储（Content Store， CS）数据模型，包括频繁度模型、支持度模型、置信度模型和关联度模型，通过该模型在网络空闲状态下提前在对应路由器设备上来预存储原始数据的关联数据，从而实现精准化预缓存网络数据。仿真实验结果表明，此机制可以实现节省网络带宽，有效降低网络拥塞的目的。

关键词：预缓存；置信度模型；缓存老化；关联度模型

中图分类号：TP393  文献标识码：A  文章编号：2096-4706（2023）12-0078-04

Research on Caching Mechanism of CCN Routing

TANG Hong1， LI Tao2， SONG Zhe3

（1.ZTE Nanjing R&D Center， Nanjing  210012， China; 2.Purple Mountain Laboratories， Nanjing  211111， China;

3.Yancheng Branch of China Mobile Communications Corporation， Yancheng  224399， China）

Abstract： CCN network requests source data through Pending Interest Table is a fragmented process. All data accessed for the first time will inevitably bring peak bandwidth problems. Based on this scenario， a Content Store data model is proposed， including frequency model， support model， confidence model and correlation model， Through this model， the associated data of the original data is pre-stored on the corresponding router device in advance when the network is idle， so as to achieve accurate pre-cache of network data. The simulation experimental results show that this mechanism can achieve the goal of saving network bandwidth and effectively reducing network congestion.

Keywords： precache; confidence model; cache aging; correlation model

0  引  言

在CCN中有三個数据结构[1]，分别是待定请求表（Pending Interest Table， PIT）、内容缓存（Content Store， CS）、路由转发表（Forwarding Information Base， FIB）。CCN请求报文生成PIT表，然后根据FIB进行数据的路由和请求，对于数据的回复会沿途进行CS存储，保证下次请求的本地化和快速化。网络通信模型CCN的一大特色就是缓存CS能力，即根据用户的请求就近进行路由器存储内容，等下次请求时，可以快速将数据传输给用户，从而节省网络带宽[2，3]。对于本地存储空间未满，时间长没有请求的数据，将根据策略选择性地进行老化删除[4]，对于本地存储空间满了，将根据请求频次、热度等方式进行替换。而对于大多数CS未满的存储空间如何有效地利用，目前的研究主要是根据热度排名[5]，将热度排名高的数据提前存储到缓存CS中，这在一定程度上可以提高用户下次命中的概率，但是热度的概念其实是针对全网所有用户的加权值，不能准确预测某个用户或者某个域的数据需求，特别是用户移动会导致当前网络内预缓存失效[6]。文献[7]对目前CS缓存策略进行了分析和概述，提出了基于用户偏好的缓存差异化策略研究，即考虑用户对不同内容类型的喜好，并结合内容流行度作为用户偏好度指标，实现高质量缓存内容的选择，但是他只考虑了用户大的方向偏好，比如音乐、美术等，未考虑偏好之间的关联关系；文献[8]提出了一种基于业务类型进行差异化分类的数据分发模式，实现了业务的分类数据分发，但是也带来了CCN体系颠覆和复杂度变更，不利于工程应用的推广。

在如上研究的基础上，提出了数据关联度的缓存机制，即基于用户在现在的网络请求中，某个用户请求数据之间或者某个域内请求数据之间的关联关系，针对性进行网络预缓存，避免峰值带宽浪费。例如用户请求A数据后，通过关联关系计算有90%以上的概率下次会请求C数据，即使C数据的热度很低或者即使C数据不是用户的偏好数据，按照该网络模型也会提前下发命令让请求端路由器发起对C数据的兴趣报文请求，然后存储在本地，实现数据的预测和提前精准化存储。

1  预缓存研究

如图1所示，整个预缓存机制包括SDN控制器设备、CCN路由器设备两个部分组成，其中控制器设备包括如下功能：

1）数据收集与挖掘功能，主要是四大模型的计算，即FP-growth（FP）模型[9]、支持度模型、置信度模型、关联度模型的计算。

2）控制下发模块，主要完成预缓存PIT下发、缓存老化与更新等功能下发。

3）信息接收模块，完成信息上报功能接收、缓存老化与替换等功能收集与上报。另外CCN路由器设备主要包括数据的预缓存模块和信息采集上报两大模块。预缓存模块完成本地CCN路由器的预缓存操作，包括添加和老化删除操作，信息采集模块主要完成预缓存关联数据的采集、老化数据的采集等功能。

基于如上模块和设备划分分析可知，预缓存机制主要包括三大功能，分别是信息收集功能、数据收集与挖掘功能、缓存老化与替换功能。其中信息收集功能主要由CCN路由器的信息采集模块和控制器的信息接收模块组成，完成CCN数据的收集和上报，由CCN路由器采集数据进入控制器的信息接收模块；数据收集和挖掘模块主要由控制器的关联度模型、置信度模型、支持度模型、FP模型、控制下发模块、CCN路由的预缓存模块组成，完成基于上报的信息数据进行数据关联度的挖掘计算，根据计算结果指导相应的设备完成关联数据的预缓存；缓存老化和替换功能是数据收集和挖掘功能和信息收集功能的逆向功能，主要由CCN路由器设备元数据删除触发上报控制器信息，进而由控制器基于现有的依赖模型完成关联数据的监控和删除回收，指导CCN路由器预缓存模块进行信息的删除，保证网络数据信息的一致性。整个预缓存机制通过用户上送的已有请求的数据进行大数据分析，计算基于各种数据请求的关联度并建立其模型，该模型作为已有模型，与用户即时缓存CS数据结合，推算出与缓存CS模型数据相关度高的数据模型，然后在网络空闲状态时，在对应路由器设备上发送关联数据的兴趣报文，来预存储关联相关数据，从而实现精准化预缓存网络通信模型CCN数据，避免数据峰值的带宽占用，有效地降低网络拥塞，同时对于已经老化删除的数据同步删除其关联数据，并触发控制器的四大模型的逆向删除操作。

1.1  信息收集功能

信息收集模块位于各个CCN路由器上，传统CCN路由器在收到数据报文后，首先查找兴趣请求表PIT，如果没有兴趣请求表PIT，直接丢弃该数据报文，如果有兴趣请求表PIT，按照兴趣请求表PIT的入接口转发数据报文。信息上报模块在CCN路由器上转发数据报文后即进行检查兴趣请求表PIT的入接口数量，然后提取内容信息外加兴趣请求表PIT的入接口数量来组成数据信息头上报控制器，内容信息包括内容名称（URL content资源）、设备信息（设备CPU、内存等资源）、接口信息（目前实际物理接口类型、数量、接口所属设备信息等）和设备所属的域信息等。SDN控制器由信息接收模块完成数据的收发与缓存。

1.2  数据收集与挖掘功能

如图2所示的数据收集与挖掘流程，控制器的收发包模块收到设备上送的数据信息后，需要对信息进行存储和汇总，首先解析获取数据信息的子信息，主要包括内容名称、设备信息、接口信息、域信息和兴趣请求表PIT的入接口数量等信息。以数据信息的子信息为基础开始建立FP-Growth模型[10]，FP-Growth采取分治策略，只需要扫描原始数据2次，便可以将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree）中，但仍保留项集关联信息[11]。FP-Tree是一种特殊的前缀树，由频繁项头表和项前缀树构成，因此FP-Growth算法可以加快整个数据构建和挖掘过程。本设计中即是根据FP-Tree计算出相应的频繁项的集合，其中，基于接口信息、域信息和全局资源数据这样的数据信息的子信息为基础开始建立FP-Growth模型，该模型首先针对每一个子信息构造FP-Tree，然后迭代FP-Tree的构造和投影过程，算出了频繁项集合。

在频繁项集合的基础上，计算各个频繁项集合的支持度模型：支持度模型由基于频繁项的集合的数量占比的计算方式而得，即该频繁项的集合在相应集合集中的数量占比，集合集为已有的算出来的所有集合。例如，以CCN命名url为基础建立的{url1、url2}集合共使用10次，整个集合有100条记录，那么{url1、url2}的支持度就是10/100 = 0.1。

在支持度模型的基础上，选取具有包含关系的集合全集，计算相应包含关系集合的置信度模型，在一个实施例中，假设相应包含关系集合中的集合一与集合二为包含与被包含的关系，使得所述置信度模型的计算公式为：（集合tmp = 集合1减去集合2） = 集合1的支持度/集合2的支持度×置信度影响因子；其中置信度影响因子默认为1，根据不同场景可以更改置信度因子。全部包含关系的集合与被包含关系的集合的置信度值都可以算出来，然后将所有值加权后取平均值；根据场景不同置信度因子算法：a = l / d×cs，其中l表示场景值，默认l，cs是当前要下发CCN路由器设备剩余存储空间百分比，剩余越小，置信度a越小，d是域信息，域离的越远，置信度越小。可见不同场景下置信度因子不同，其受缓冲CS剩余存储空间、域信息等因子影响。公式中集合tmp是一个临时的集合，是计算的中间值。下文具体说明置信度模型的计算实例：假设集合1 = {url1，url2，url3}，集合2 = {url1，url2}，那么url3为置信度集合tmp，整个集合有100条记录，其中集合1共使用了10次，集合1的支持度为10/100 = 0.1，集合2共使用12次，集合2的支持度为：12/100 = 0.12，因此tmp的置信度模型为：集合tmp = url3 = 0.1/0.12 = 0.83，即假如使用集合2的情況下，有83%置信概率会用到集合1，也即用到{url1、url2}情况下，有83%概率会用到url3，按照优先级认为83%概率满足要求，则控制器可以向集合1所在的CCN路由器设备发送一个PIT指令，指示该路由器发送url3的PIT请求，将url3内容信息提前存储在集合1所在的CCN路由器设备上。

但是不能所有的tmp都下发PIT请求，这样会导致大量的资源浪费，因此就需要建立关联度模型，即基于置信度模型集合数值tmp，选取最终下发设备的最优集合作为关联度模型，然后在网络通信模型CCN的路由器上基于所有关联度模型数值发起相应的兴趣报文然后根据数据报文进行CS中的预缓存。本设计中设计了三大关联度模型，即接口信息tmp关联度模型、域信息关联度模型和全局数据关联度模型，同时选取置信度模型tmp的50%作为下发候选，在下发候选中选取置信度超过60%的tmp作为最终关联度模型tmp进行下发，指导相应的CCN路由器设备进行数据的提前缓存。

1.3  缓存老化与更新功能

缓存老换及替换模块主要是由设备端完成CCN设备缓存CS监控，关联数据的删除等功能，然后上报控制器端完成元数据的增删，触发增删数据的重计算，然后下发预缓存数据。根据置信度模型因子的公式可知，在不更改既有的网络通信模型CCN替换及老化策略的前提下，只有在缓存CS的存储空间有剩余时才会触发对关联度最高的数据进行提前的PIT请求和数据缓存，因此缓存老化及替换模块主要功能有：

1）缓存CS中数据的删除需要上报控制器，CCN路由器的预缓存模块监控CS中数据老化删除、人为删除等事件，上报控制器收发模块从而触发控制器的关联度模型的删除与重新计算，并下发新的关联度数据。例如url1因为老化触发删除，CCN设备感知到该事件后上报控制器模块，主要包括内容名、内容大小等信息，控制器感知后，即对该集合关联的url3发起删除；或者对于url1删除后，需要计算url3的置信度模型，触发了重新计算；并且下发相应的与删除数据关联的预缓存数据，控制器通过全局控制通道，下发控制报文，对某台CCN路由器进行单点数据删除。

2）新的缓存CS中数据的添加也需要上报控制器，与1相同，该模块感知到CS中新数据的添加后上报控制器后，控制器基于新数据计算其内容关联度模型，选取与新数据的关联度模型置信度较高的预缓存数据下发控制命令，触发网络通信模型CCN的路由器发送兴趣报文来预缓存数据，例如某台CCN设备有新的数据url4的内容缓存到了设备上，控制器感知后，计算针对url4的置信度模型、关联度模型，然后选取关联度最高的作为url资源的url5，然后向设备发送控制报文，设备收到控制报文后，发起针对url5的PIT兴趣报文，来预缓存url5数据。

2  仿真实验

基于如上CCN模型，建立1 000个CCN网络数据URL资源集合，分别是url1～url1 000，按照集合组合随机原则建立url集合10 000个，然后对比方案如下：CCN路由器首次分别获取url1，url2，…，url1 000所需要的时间，选取50个url为一组，计算获取数据的平均时间；然后采用本文所用方案后获取url组所对应数据的时间。

如图3所示即为采用本方案前后的对比图，由图中可见采用本方案后在前30个大样本周期内效率优化明显，随着采样样本的增加，触发与样本相关的url提前预存储，使得请求数据的效率得到较大提升。后续随着传统CCN网络存储能力的提现，优化后与优化前效率相当。

3  结  论

综上所述，本文在研究了目前CCN各种缓存技术的基础上，结合理论实践，提出了CCN路由的预缓存技术，对预缓存技术涉及的信息收集模块、收据收集与挖掘模块、缓存老化与更新模块进行了详细的介绍与研究，通过信息上报模块进行CCN路由器信息的收集与上报，通过数据收集与挖掘模块进行大数据关联度计算，并对于关联度较高的模型结合CS存储情况提前发起预缓存，通过缓存老化与替换模块完成关联数据的回收。实验仿真结果表明，预缓存技术不但保留了CCN网络结构的经济性、便捷性、易扩展性的特点，而且还具有可以有效地节省网络峰值带宽的巨大价值。将其应用到现有的CCN网络系统中，不仅可有效保证数据传输的及时性和可靠性，而且还能大幅度提升网络宽带利率。

参考文献：

[1] AHLGREN B，DANNEWITZ C，IMBRENDA C，et al. A survey of information-centric networking [J].IEEE Communications Magazine，2012，50（7）：26-36.

[2] CHOI J，HAN J，CHO E，et al. A Survey on content-oriented networking for efficient content delivery [J].IEEE Communications Magazine，2011，49（3）：121-127.

[3] JACOBSON V，SMETTERS D K，THORNTON J D，et al. Networking named content [J].Communications of the ACM，2012，55（101）：117-124.

[4] 劉外喜，余顺争，胡晓，等.CCN中选择性缓存机制的研究 [J].计算机学报，2014，37（2）：275-288.

[5] 唐红，韩健，段洁，等.基于内容流行度的移动CCN缓存策略研究 [J].重庆邮电大学学报：自然科学版，2018，30（1）：119-126.

[6] 霍如，刘江，鄂新华，等.一种融合CCN的移动网络内容预缓存方法：CN201811233306.6 [P].2019-01-18.

[7] 李朋明.面向用户的内容中心网络缓存策略研究 [D].重庆：重庆邮电大学，2019.

[8] 葛国栋，郭云飞，刘彩霞，等.CCN中基于业务类型的多样化内容分发机制 [J].电子学报，2016，44（5）：1124-1131.

[9] 罗晓霞，陈君.一种FP-growth的改进算法 [J].西安科技大学学报，2009，29（4）：491-494+504.

[10] 于红，王秀坤，孟军.用有序FP-tree挖掘最大频繁项集 [J].控制与决策，2007（5）：520-524.

[11] 颜跃进，李舟军，陈火旺.基于FP-Tree有效挖掘最大频繁项集 [J].软件学报，2005（2）：215-222.

作者简介：汤红（1985－），女，汉族，江苏宿迁人，中级职称，硕士，研究方向：CCN网络、设备驱动网络；李涛（1983－），男，汉族，江苏连云港人，高级职称，硕士，主要研究方向：CCN网络、未来网络；宋哲（1984—），男，汉族，江苏盐城人，中级职称，硕士，研究方向：CCN网络。