Page 345 - 《软件学报》2021年第9期

刘嘉琦 等:一种基于两级缓存的协同缓存机制 2969

. xhit = . x hit ρ× t cur t− last + 1 (1)
其中,ρ(0<ρ<1)决定了内容命中次数随时间衰减的快慢,t cur 指当前时间,t last 指上次表项更新时间.与周期性进行
热度衰减的方法不同,我们采用基于命中的时间衰减方法,这种方法不需要周期性地更新内容热度,只需要在有
数据包到来的时候进行衰减操作,降低了更新的开销.当数据包到达时,首先利用时间衰变参数对历史的命中数
进行衰减,再将衰减操作后的值加 1,表示当前内容在节点中的热度,当前时间与上次表项更新时间间隔越久,历
史命中数对当前内容热度的影响越小.

Fig.2 Local hit table and popularity table
图 2 本地命中列表与热度统计表

当缓存内容在 RawCache 中发生替换时,首先根据 LHT 表中 hit 项判断其命中次数是否大于所设阈值,若满
足要求,则认为该内容应该被缓存至域内 HashCache 中,此时节点会将内容本身以及该内容在 LHT 表中的相关
信息一并发送至哈希映射所得节点.对应节点收到内容以后,除了存储内容本身以外,还会更新自身 PT 表项.更
新规则如下:若 PT 表中没有该项内容,则直接将内容的单节点命中次数作为内容热度,即 x.popularity=x.hit;若
PT 表中已存在该项内容,则使用下面的公式更新表项:
. x popularity θ =× . x hit + (1 θ − ) x× .popularity ρ × t cur t− last (2)
其中,θ(0<θ<1)是单节点内容命中次数在域内内容热度上的权重参数,ρ(0<ρ<1)决定了内容热度随时间衰减的
快慢,t cur 指当前时间,t last 指上次表项更新时间.为与 LHT 表的时间衰减保持一致,我们在 PT 表的热度更新中同
样引入时间衰减.通过哈希映射机制,域内各节点 RawCache 中替换出的同一内容会被发送到同一节点,目标节
点通过域内各个节点的局部命中次数不断更新该内容的 popularity,最终得到的 popularity 实际上是域内所有
节点命中次数共同作用的整体结果.PT 表中内容按照 popularity 由大到小排序,用以指导 HashCache 缓存哪些
内容.节点会记录 HashCache 中已缓存内容的 popularity 最小值,当要缓存新内容时,首先比较二者的 popularity:
若要缓存的内容的 popularity 大于该值,则进行缓存,并替换掉 popularity 最小的内容;否则不做缓存处理.
2.3 CSTC路由策略

本节假设我们提出的 CSTC 缓存机制运行在典型的 ICN 网络 NDN [12] 中,NDN 中共有两种数据类型:兴趣
分组(interest packet)和数据分组(data packet).用户发起的请求称为 Interest,响应请求返回的内容数据称为
Data.需要说明的是:HashCache 上采用的哈希映射机制的详细过程并不是 CSTC 关注的主要内容,就像我们并
不限制 RawCache 上必须采用某种 On-path 缓存策略一样.
表 1 中,当节点收到 Interest 请求时,首先会查找自身内容存储表(content store,CS)与待定请求表(pending
interest table,简称 PIT),看是否有内容命中.若都没有命中,则根据哈希映射得到目标节点,并向其转发(第 5 行).
若 Interest 到达目标节点后仍没有命中,则将 Interest 转发至内容源(第 3 行).