NDN中基于蚁群替换算法的邻居协作缓存管理策略*
2014-09-29董利利董永强
董利利 ，王 勇 ，董永强 ,2，杨 鹏 ,2
（1.东南大学计算机科学与工程学院 南京 211189；2.东南大学计算机网络和信息集成教育部重点实验室 南京211189）
1 引言
以内容为中心的命名数据网络[1]（named data networking，NDN）的重要特征之一，是利用网络内置缓存机制提高用户获取内容资源的效率和网络资源的利用率。在NDN中，路由节点依靠报文中携带的内容名字转发数据内容，同时每个路由节点都具有缓存本地转发过的数据内容的能力，以便后续相同请求到达时可利用缓存副本直接响应该请求，从而提高响应效率。研究设计高效的缓存管理机制对提升NDN的整体性能具有重要意义。
传统的缓存管理策略有LRU（least recently used）、LFU（least frequently used）、FIFO（first in first out）以及 SIZE 替换算法等。其中，LRU[2]将数据内容最近被访问的时间点作为判断依据，在必要时将缓存内容中最近最少访问的数据内容替换出缓存；LFU[3]统计缓存内容在过去一段时间内被访问的次数（即访问频率），将访问频率最低的内容替换出去；FIFO[4]缓存管理策略，基于简单的排队规则，根据缓存内容存储的先后顺序依次进行缓存替换；SIZE[5]替换算法则将数据内容的大小作为缓存替换的主要因素，优先替换缓存中占用空间较大的数据内容。参考文献[6]提出了一种基于内容热度的NDN缓存替换策略。在保留NDN中CS、PIT以及 FIB结构的基础上新增了一张 CPT（content popularity table），用来保存缓存内容的命中率、历史及当前热度，热度值按计时周期进行加权平均，在缓存替换过程中选择热度最小的内容进行替换。
以上缓存替换策略都是基于单个节点的，并没有将网络当作一个整体来考虑。考虑到NDN中每个路由节点都具有缓存内容的能力，为提高网络整体的缓存价值，相关研究提出了节点间协作的缓存管理策略。根据关注重点、协作决策点的不同，可将节点间协作的缓存管理分为全局协作、路径协作以及邻域协作[7]。
全局协作根据当前的网络拓扑、节点间的网络距离以及各个节点的访问速率等信息，提前规划好数据内容在网络中的最佳存储位置，使得用户访问内容的“代价”最低。参考文献[8]提出了一种基于内容流行度以及网络拓扑的协作缓存策略，主要思路是根据数据报文距离内容提供端的跳数和数据的流行度，确定报文的生存期以及报文存储的位置，但并没有给出流行度的计算方法以及网络拓扑图的更新方式。
路径协作指数据内容的命中节点到请求节点之间的路由节点，在转发过程中判断是否缓存该内容的协作决策方法。参考文献[9]提出在转发兴趣报文的过程中记录沿途经过的节点信息（如节点状态、请求频率等），命中节点根据请求报文携带的路径上所有节点的状态信息，利用动态线性规划，计算出最优的内容缓存位置。这种方法具有中心处理方式的弊端，在决策节点的计算开销也不小。参考文献[10]考虑避免复杂的决策算法，在转发内容报文的过程中随机地选择一个节点作为存储内容的路由节点。这种缓存策略易于实现，但未考虑内容的访问热度以及节点的缓存状况。
邻域协作是指在一个节点的邻域范围（经过有限跳数可达的节点，也称邻居节点）内，显式地对缓存放置的位置进行决策，通过协调邻域范围内节点之间的缓存内容，降低网络中数据的冗余度，提高整体的缓存利用率。参考文献[11]提出利用布鲁曼滤波器（bloom filter）技术，根据节点设定的缓存内容时间把内容目录广播给一定区域内的其他节点，设定的保存时间越长，广播的距离越远。该方法没有给出具体的缓存内容时间计算方法，也未通过实验验证其有效性。参考文献[12]提出的邻域协作缓存管理方法主要针对如何降低节点之间的冗余度问题，在后台运行一个降低邻域范围内缓存冗余的程序，定期清理邻域范围内的冗余缓存对象。这种方法可以有效地降低数据的冗余度，但未考虑数据内容本身的信息，会导致某些热门资源在网络存储的副本数量有限，不能很好地满足用户请求。
为充分利用NDN中路由节点的缓存信息，本文针对现有缓存替换策略的不足，基于邻域协作的思想，提出了一种基于蚁群替换算法的邻居协作缓存管理（ACNCM）策略。在单节点的缓存替换中，将自定义的内容缓存价值引入具有较高执行效率和优化求解结果的蚁群替换算法（ACCR）中，提高单个节点的缓存价值；在协作缓存替换中引入协作替换参数，协调不同节点之间的内容缓存价值，从而提高NDN整体缓存价值。
2 基于邻居协作的NDN缓存管理框架
2.1 邻居协作模型与协议交互机制
如图1所示，基于邻居协作的NDN缓存管理框架在现有CS、PIT以及FIB结构的基础上，新添加了邻居信息结构NIB。NIB的主要功能有：在节点计算缓存内容价值时提供邻居副本信息，支持缓存替换算法的运行；在节点执行协作缓存决策过程中提供邻居节点信息，作为判断是否执行协作缓存的一个主要因素；在处理用户发起的兴趣报文过程中，可以优先获取邻居节点中存储的内容，提高响应效率。
邻居信息结构NIB通过邻居缓存信息表 （NCT）（见表1）和邻居缓存状态表（NST）（见表2）记录给定邻居深度范围内的所有邻居节点的缓存状态信息，其中邻居深度表
图1 基于邻居协作的NDN缓存管理框架
示该条信息的发送者距接收者的路由跳数，初始值为1，在转发过程中逐跳增加。
表1 NCT
表2 NST
采用ACNCM策略的节点在接收到兴趣报文时，先检查CS和PIT中是否有相应记录，若有则按NDN标准流程处理；如果都没有，则检查NIB以判断邻居节点中是否已有相应的数据内容。如果NIB中有相应记录，则将兴趣报文转发给该邻居节点，否则检查FIB，将兴趣报文通过相应端口转发给上游节点。
为便于路由节点间进行协同缓存，充分利用新增邻居缓存结构中的信息，设计了两种新的报文：NIB更新报文和协作缓存报文。
（1）NIB 更新报文
NIB更新报文用于路由节点向其他节点通告本地缓存信息，其结构如图2所示。其中，节点标识是节点的唯一性身份标识；最大转发跳数用于限定NIB报文在网络中的传输范围；本地缓存是否已满与平均内容缓存价值是判断是否执行协作缓存的两个重要指标，供报文接收端在执行协作缓存策略时采用；缓存内容名字列表记录本地缓存内容的名字，用于告知邻居节点本地缓存空间存储了哪些内容，供邻居节点执行缓存替换算法以及转发兴趣报文时参考。每个路由节点会根据给定的协作邻居深度以及更新间隔时间定期向外发出NIB更新报文。当路由节点接收到NIB更新报文时，根据报文中携带的信息更新NST中对应的表项；并判断最大转发跳数是否大于1，若是则将最大转发跳数减1，并通过当前节点的所有端口转发，否则丢弃该报文。
图2 NIB更新报文结构
（2）协作缓存报文
路由节点选出需要替换出缓存的数据内容后，由协作缓存管理策略决定是否对该内容执行协作缓存，如果需要则向选中的邻居协作节点发送包含该内容的报文，称为协作缓存报文，其格式如图3所示，其中协作节点标识即协作缓存节点的身份标识，协作邻居深度代表节点选中的协作邻居节点距离本节点的跳数，内容数据即需要协作存储的内容本身。邻居节点收到协作缓存报文后，会首先根据内容缓存价值判断是否应该存储收到的内容，然后根据判断结果处理报文。如果该处理引发了协作邻居节点执行缓存替换，则不再对替换出的数据内容继续执行协作缓存处理，而是直接删除新替换出的内容，以降低不必要的网络开销。
2.2 ACNCM缓存管理的基本思想
ACNCM缓存管理主要包括两部分，具体介绍如下。
（1）单节点的缓存替换机制
将缓存替换问题建模为0/1背包问题（knapsack problem，KP），在单个节点内需要进行缓存替换时，利用基于蚁群优化算法的缓存替换机制选择需要替换出去的数据内容。在蚁群算法计算选择缓存内容的概率时综合考虑以下因素：信息素浓度、数据到达的时间、访问次数和数据的大小以及邻居节点中是否存储有相同内容的副本。
（2）邻域协作缓存管理机制
在协作缓存管理中引入协作替换参数，对于单个节点中将要被替换出去的数据内容，计算出各个邻居节点的协作替换参数，然后选择具有最小协作替换参数的邻居节点作为该数据内容的存储节点。在计算协作替换参数时，主要考虑邻居节点的平均缓存价值以及访问时延。
3 ACNCM缓存替换与邻居协作算法
3.1 单节点缓存替换问题建模
给定一个缓存空间有限的网络节点，当剩余空间不足以存储新到来的数据时，需要从现有缓存中替换出一些价值相对低的数据内容，为新到达的数据腾出空间。该问题本质上等同于传统的0/1背包问题，即在给定的约束条件下，求最大可能组合的优化问题。这是一类典型的NP完全问题，其一般描述为：给定一个能承受最大重量为W的背包和n个物品，物品i的重量用wi来表示，vi表示物品i的价值，如何选择总价值尽可能高的物品放入背包中，并且物品的总重量不能超过背包的容量。
基于此认识，缓存替换问题可描述为：节点缓存空间最大容量为S，当前存储了n个数据内容，数据内容i的大小记为si，对应的内容缓存价值记为vi，待存入缓存的新到达数据内容的大小为sx。需要找出一种存储方案，使得在数据内容总大小不超过最大可用缓存空间S的情况下，缓存空间中保留的数据内容的缓存价值总和最大。
其形式化描述：设 S>0，0
3.2 数据内容的缓存价值计算
数据内容的缓存价值与背包问题中的物品价值相对应，是对节点缓存空间中存储的数据内容的价值估量。由于网络中数据内容请求的随机性，无法直接确定数据内容的缓存价值，只能根据数据内容在缓存中以往的效用来判断内容的价值。本文定义内容i的缓存价值如式（1）所示。
其中，si表示内容i的体积，也即占用的缓存空间，数据内容的体积越大，其缓存价值越小。t表示当前时间，ti表示内容被存储的时间，hitcouti表示内容在时间段(t-ti)内被访问的次数，hitcouti/(t-ti)表示内容在该时间段内的访问频率，它反映数据内容在过去一段时间的热度，故缓存价值与其成正比。neibordeepi表示本节点到存储内容i副本的邻居节点的跳数，如果没有邻居节点存储该内容，则其值为网络设定的最大协作邻居深度值加1。邻居深度越大，从邻居节点获取数据内容的开销越大，在本节点就更有存储的价值，所以邻居深度与缓存价值成正比。
3.3 基于蚁群算法的单节点缓存替换机制
求解0/1背包问题有很多种方法，包括图论法、动态规划法、分支限界法等精确求解方法以及蚁群算法、遗传算法、模拟退火算法等启发式求解方法。在这些算法中，蚁群算法具有结果精确度高、计算时间短等优点，参考文献[13]给出了一种求解0/1背包问题的快速蚁群算法（KPACA）。考虑到NDN缓存对象的属性信息满足蚁群算法的计算要求，本文借鉴蚁群算法的主要思想，提出一种新的基于蚁群算法的缓存替换机制（ACCR）。
3.3.1 蚁群信息素的计算
在蚁群算法中，信息素是蚂蚁群体选择和演化过程的一种体现，信息素随着选择的蚂蚁数量的增多而增加，同时也会随着时间的增长而逐渐挥发。但与求解传统TSP旅行商问题的蚁群算法不同，在求解0/1背包问题的蚁群算法模型中，信息素积累在蚂蚁选过的物品上而不是走过的路径上。本文参照MMAS算法[14]中信息素的更新方式，在执行完一轮选择后仅对蚂蚁找出的最优解中包含的数据内容进行信息素的增加修改，其余没有被最优解选中的数据内容信息素相应地减少。蚁群信息素τi(t)的更新如式（2）所示。
其中，ρ∈(0,1)为信息素的挥发系数，(1-ρ)表示信息素的残余因子；Δτi表示在时间段p内信息素的增量，初始值为 0。信息素增量 Δτi如式（3）所示。
式（3）中考虑到体积大的内容占用的缓存空间也大，当内容没有被蚂蚁最优解选中时，会根据内容的大小增加它的挥发程度。
3.3.2 选择概率的计算
在蚁群算法中，每个物品都有它被蚂蚁选中的概率，称为选择概率，记为。参考KPACA[13]，本文中蚂蚁k在一轮执行过程中选择缓存对象i的概率(t)如式（4）所示。
其中，τi(t)为物品i上的蚁群信息素，ηi(t)为启发式函数；α、β为信息素因子和期望启发式因子，分别反映蚂蚁在选择内容时信息素和缓存内容属性对选择结果的影响，α值越大，表示蚂蚁更倾向于依赖之前蚂蚁的选择结果；β值越大，则表示蚂蚁独自判断选择的能力越大。pitchedk表示蚂蚁已经判断过，不能再选择的内容的集合。
启发式函数ηi(t)表示蚂蚁选择缓存对象i的期望程度，启发式函数根据数据内容自身的属性决定蚂蚁对缓存内容的选择概率。在选择概率中加入启发式函数，一方面可以帮助蚂蚁加快选择出最优解的速度，另一方面也是结合数据内容的实际使用情况，将缓存内容自身的信息作为选择判断的重要因素。参考文献[13]中把启发式函数定义为物品单位体积的价值，认为物品单位体积的价值越高，选择该物品的期望就越高。由于本文在内容缓存价值计算中已经考虑了内容体积大小对缓存价值的影响，所以选择内容缓存价值作为期望启发式信息，即ηi(t)=Vali(t)。因此，缓存内容价值越大，留在缓存空间的期望就越大；相反，缓存价值低的数据内容应尽早替换出去。
3.3.3 基于蚁群算法的缓存替换机制
当路由节点的缓存空间不足以存储新内容时，根据ACCR算法进行内容替换，使得节点中缓存的数据保持较高的内容价值。ACCR过程描述如下。
（1）当节点收到存储内容请求时，根据报文内容创建并初始化缓存数据对象。访问命中次数hitcounti初始化为1，存储时间记录为当前时间。
（2）计算剩余缓存空间是否能够存储该数据内容。如果空闲缓存空间能够容纳该内容，则直接存储内容，结束；否则，转步骤（3）。
（3）初始化蚁群替换算法参数，设各内容对象的信息素τi(t)为一固定值τ0。设定算法参数α、β和ρ，设定时间 t为系统当前时间。设定最大迭代次数loopmax，模拟蚂蚁的个数ma。初始化每个蚂蚁的禁忌表pitchedk和解集resultk。
（4）让每只蚂蚁k根据式（4）计算出缓存内容被选择的概率(t)，蚂蚁k根据该概率值选择下一个缓存内容i，并将该内容加入禁忌表pitchedk中，表示该内容已经被选择过。然后试着将该内容放入解集resultk中，如果该解集的内容总体积小于节点最大缓存容量S，则把该内容并入解集resultk中作为可行解的一部分。循环上述过程，直到ma只蚂蚁都做完了对所有缓存的选择判断，并构造出各自的解集。
（5）找出本轮循环结束后所有蚂蚁的解集中缓存价值最大的解集resultmax，如果该解集的总缓存价值大于当前最优解，则替换当前最优解。如果迭代次数小于最大迭代次数并且不满足结束条件，则更新信息素并转至步骤（4）；否则，转至步骤（6）。
（6）如果新到达的数据内容在最优解中，则将新到达内容存入本地缓存，不在最优解中的缓存内容替换出去；否则，不存储新到来的数据内容。缓存替换执行结束。
3.4 基于蚁群替换算法的邻居协作缓存管理策略
缓存替换算法找出需要替换的内容之后，启用协作缓存机制查询邻居节点是否存储了该内容的副本，若是，则直接删除该内容不做协作缓存处理；否则，根据邻居节点的缓存状态信息，计算协作替换参数，选择合适的协作缓存节点。节点e的邻居节点j的协作替换参数计算如下：
其中，delayj为对邻居节点j的访问时延为邻居节点j的平均内容缓存价值。由于两个相邻节点之间的通信状况不好，会导致将来从该邻居节点获取缓存数据时花费较高的时间成本，所以在选择缓存协作节点时，考虑了邻居节点之间的通信时延。此外，由于平均内容缓存价值可以反映一个节点存储的数据内容的整体质量，因此应选择平均缓存价值较低的邻居节点作为协作节点，以提高邻居节点的整体缓存价值。
节点协作缓存模块的处理流程如图4所示。
4 实验仿真与性能分析
4.1 实验环境构建
为验证本文提出的缓存管理策略的可行性和有效性，对ACNCM策略进行了模拟实验。采用C++及MATLAB语言模拟以事件为驱动的协作缓存管理系统。
首先模拟实验过程中的数据输入，依据现实生活中用户对互联网内容资源的访问特征，实验中设定用户发起的请求序列符合柏拉图定律，即80%的请求报文对应于20%的内容。用户对内容请求的时间间隔服从指数分布。然后实现ACNCM的逻辑处理部分，这是整个实验的核心部分，用来模拟缓存替换算法以及基于邻居协作的缓存管理过程。
网络拓扑规模根据GT-ITM拓扑生成工具生成一个节点数为10的随机网络拓扑图，其中任意两个节点之间存在直达路径的概率为0.4。从随机生成的拓扑图的边缘节点中选择一个节点作为内容提供节点，选取两个边缘节点作为客户端节点。相邻路由节点之间的时延设为20 ms，NIB报文的最大转发跳数设为5。实验中算法的相关参数α、β、ρ的取值分别为0.4、0.3和0.7，协作邻居深度设定为1。模拟实验的具体参数配置见表3。
表3 实验参数
4.2 缓存替换算法ACCR的性能分析
图4 协作缓存流程
首先考察单节点缓存替换算法ACCR的性能。在相同的实验环境下，针对路由节点的缓存容量为50 MB和80 MB两种情况，分别进行ACCR算法、LRU算法和FIFO算法的实验，运行结果如图5、图6所示。
图5 缓存空间为50 MB时的缓存命中率
图6 缓存空间为80 MB时的缓存命中率
由图5和图6可以看出，ACCR的缓存命中率高于LRU算法和FIFO算法。分析其原因，ACCR在执行缓存替换时综合考虑了缓存对象自身的属性信息，如缓存数据的大小、访问次数、邻居副本因素、存储时间等，同时结合蚁群信息素的正反馈机制，使得缓存中保留了那些缓存价值较高的数据内容。
4.3 协作缓存策略ACNCM的性能分析
引入邻居协作缓存机制，考察在相同的实验环境下，FIFO、LRU、ACCR和ACNCM 4种缓存管理策略的报文开销和平均时延。报文开销定义为网络报文总数与用户得到的响应报文的比值。如图7所示，FIFO缓存管理策略产生的报文开销最大，LRU缓存管理策略次之；ACCR的效果比LRU好，但是相比于ACNCM性能又相对较差。说明ACNCM能有效降低全网络的报文数量，降低网络总开销。
如图8所示的实验结果表明，ACNCM的平均时延要优于其他缓存管理策略，这主要是由于邻居协作缓存管理策略充分利用了邻居节点的缓存功能。通过协作存储内容使得邻居节点之间作为一个整体，存储了缓存价值较高的缓存内容，更高效地利用了整体的缓存空间。当用户请求到达时，ACNCM可以更快地响应用户请求，提高用户对内容资源请求的响应效率，降低了响应时延。
图7 报文开销比较
图8 平均时延比较
5 结束语
针对NDN缓存利用效率问题，本文根据数据内容自身的属性信息以及邻居节点的存储状态信息，提出一种基于邻居协作的缓存管理（ACNCM）策略。本文的主要工作包括：定义了缓存数据的内容价值属性，结合邻居节点的缓存信息，为节点缓存替换决策提供重要参考；将缓存替换问题建模为0/1背包问题，利用蚁群优化算法，结合蚁群信息素和缓存内容自身的属性信息，对节点的缓存空间进行替换管理；采用邻域协作思想，依据内容缓存价值和邻居缓存信息，选择合适的邻居节点作为协作缓存节点，提升邻居节点间整体缓存利用率。
实验结果表明，ACNCM机制在缓存的命中率、用户请求的响应时延以及网络整体开销等方面，相比现有缓存管理方法都有不同程度的优化。进一步的研究工作包括探讨与协作替换参数相关的邻居属性，优化NIB更新报文，实现更准确的节点间协作开销估算。此外，增加更多同类算法的对比也是未来要完成的工作之一。
1 Zhang L,Estrin D,Burke J,et al.Named Data Networking(NDN)Project.Technical Report NDN-0001,Xerox Palo Alto Research Center-PARC,2010
2 Willick D L,Eager D L,Bunt R B.Disk cache replacement policies for network fileservers.Proceedings of the Distributed Computing Systems,California,USA,1993:2～11
3 张震波,杨鹤标,马振华.基于LRU算法的Web系统缓存机制.计算机工程,2006,32(19):68～70
4 Chrobak M,Noga J.LRU is better than FIFO.Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,San Francisco,California,USA,1998:78～81
5 Abrams M,Standridge C R,Abdulla G,et al.Removal policies in network caches for world-wide web documents.Proceedings of the ACM SIGCOMM,Stanford,CA,USA,1996:293～305
6 李韬,李玉宏.一种基于内容热度的NDN缓存替换算法.中国科技论文在线,2012
7 张国强,李杨,林涛等.信息中心网络中的内置缓存技术研究.软件学报,2014,25(1):154～175
8 Ming Z,Xu M,Wang D.Age-based cooperative caching in information-centric networks. Proceedings of the IEEE INFOCOM WKSHPS,Orlando,FL,USA,2012:268～273
9 刘外喜,余顺争,蔡君等.ICN中的一种协作缓存机制.软件学报,2013,24(8):1947～1962
10 Eum S,Nakauchi K,Murata M,et al.CATT:potential based routing with content caching for ICN.Proceedings of the Second Edition of the ICN Workshop on Information-Centric Networking,Istanbul,Turkey,2012:49～54
11 Wang Y,Lee K,Venkataraman B,et al.Advertising cached contents in the control plane: necessity and feasibility.Proceedings of the IEEE INFOCOM WKSHPS,Orlando,FL,USA,2012:286～291
12 Wang J M,Zhang J,Bensaou B.Intra-AS cooperative caching for content-centric networks.Proceedings of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking,Santa Barbara,CA,2013:61～66
13 王会莹,贾瑞玉,章义刚等.一种求解0/1背包问题的快速蚁群算法.计算机技术与发展,2007,17(1):104～106
14 Stutzle T,Holger H H.Max-min ant system.Future Generation Computer System,2000,16(8):889～914
