命名数据网络中基于Dec-POMDP的缓存策略

姚进发

(锐捷网络股份有限公司 锐捷研究院，福建 福州350002）

0 引言

随着网络技术的发展以及互联网用户的快速增加，网络应用的主体正逐步向内容获取和信息服务演进。早期为解决端到端通信问题而设计的基于TCP/IP的体系架构对计算机网络性能的限制使得传统互联网难以满足海量的网络数据处理需求，这激发了人们对未来网络架构设计的重新思考与研究。信息中心网络(Information-Centric Networking，ICN）[1]作为一种“革命性”体系架构，其以内容为中心的特点无缝迎合了未来网络的发展趋势，因而受到研究学者的广泛关注。在ICN体系的诸多部署方案中，命 名 数据网络(Named Data Networks，NDN）因其先进的设计理念、灵活的路由转发机制以及分布式的网内缓存方式等良好特性已经成为ICN中的研究热点。

为了满足高效的内容分发与获取的需求，NDN在设计时通过引入网内缓存(in-network caching）机制来减少不必要的网络数据传输，从而提高数据传输效率，增强网络的可扩展性。在NDN中，每个网络节点都具有一个内容存储库(Content Store，CS），用于缓存经过本地节点的数据，从而为后续与数据对应的相关请求提供路径缓存服务。然而，与海量的数据相比，网络节点中CS的容量相当有限，因此如何合理地进行内容放置和缓存决策，是影响NDN性能的关键因素。

NDN在设计之初默认采用处处缓存(Cache Everything Everywhere，CEE）策 略[2]，但 该 方 法 会 导 致节点缓存内容趋于同质化，故无法充分发挥网内缓存效率。近年来，学术界围绕NDN缓存技术的研究已经取得了不少成果。文献[3]针对CEE策略的缓存冗余问题，提出只在请求命中节点的直接下一跳缓存数据(Leave Copy Down，LCD），一定程度上提高了网络缓存的利用率，但流行度高的内容需要被访问多次才能缓存到边缘节点上。文献[4]提出了一种基于内容流行度的协作缓存策略(WAVE），它根据内容请求次数以指数方式逐步增加沿途节点上所缓存的数据包个数，从而实现数据在空间存储位置上的差异化，但该方案并没有考虑内容请求序列的相关性。文献[5]通过估算路径的剩余存储能力来计算同一路径上的不同数据流在沿途各节点上的缓存概率，从而提出了一种兼顾不同数据流间存储公平性的概率缓存策略(ProbCache）。文献[6]提出了一种分布式沿途缓存策略，即最大增益网内缓存(MAGIC）。网络节点基于内容流行度和路由跳数来计算内容的缓存增益，并在数据传输路径上选择具有最大缓存增益的节点进行内容缓存，从而达到减少网络带宽消耗的目的。但该方案在进行缓存决策时需要重新计算各内容的流行度，因此计算量大，执行复杂度高。文献[7]提出了一种主动缓存策略，其主要思想是利用熵来衡量移动性预测的不确定性，并定位最佳的预取节点，从而降低服务器负载，并减少缓存冗余。

针对NDN的网络架构特性，本文提出了一种基于Dec-POMDP的NDN缓存策略。首先利用Dec-POMDP理论框架对NDN网络的缓存问题进行建模，该模型考虑了缓存节点间的相互协作，以实现降低缓存内容冗余度和内容优化存储的目的。在此基础上，通过限制节点的协作域的方法来避免引入过量的额外通信开销，进而降低模型求解的复杂度。最后，本文给出了一种基于强化学习的局部近似最优缓存策略的求解算法。仿真结果表明，该方法能够有效增加缓存内容的多样性，提升缓存命中率，进而减小用户请求内容的总跳数。

1 NDN工作原理

NDN网络中的数据传输采用基于用户驱动的“拉”模式数据获取方式。NDN中存在两种数据包类型 ： 兴 趣 包 (Interest Packet）和 数 据 包 (Data Packet）。用户通过发送包含内容名称的兴趣包来向网络请求数据，该请求兴趣包将被路由到存有对应数据的邻近节点或服务器节点；然后，携带该请求内容的数据包沿着兴趣包的反向路径被逐跳传送给数据请求者。

如图1所示，当请求兴趣包到达时，网络节点根据所请求的内容名字依次在内容存储库(Content Store，CS）、待定兴趣表(Pending Interest Table，PIT）和转发信息库(Forwarding Information Base，FIB）中进行匹配查询。若CS中存在与该请求对应的数据包则直接将数据传回给请求者；否则，如果PIT中含有与该请求对应的条目，则将该请求的进入接口添加到对应条目的接口列表中，然后将该请求抛弃；如果PIT也匹配失败，则新建一个PIT条目并查询节点的FIB，将请求转发到下一跳节点。

图1 NDN中请求包转发过程

当节点收到响应数据包时，节点根据对应的PIT表项中所记录的请求接口列表进行数据转发，并根据相应的存储策略将其存储在节点的CS中，如图2所示。

图2 NDN中数据包转发过程

2 基于Dec-POMDP的NDN缓存策略

考虑一个离散时间的Dec-POMDP动态系统。在每一个决策时刻，每个智能体首先从系统中获取在当前状态下各自的观测信息，然后做出决策并执行动作，系统根据状态转移函数转移到下一个状态，并获得一个即时回报，整个过程周而复始。因此，一个Dec-POMDP模型通常可以由一个7元组定义[8]：

其中，N={1，…，N}表示系统中所有智能体的集合。S={Si}表示一个有限的系统状态集合，其中Si表示智能体i的内部状态集。A={Ai}表示所有智能体的联合动作集，其中Ai表示智能体i的可用动作集。Ω={Ωi}表示系统联合观测的有限集，其中 Ωi为智能体 i的观测集。P：S×A→[0，1]表示系统的状态转移函数，p(s′|s，a）表示系统在状态 s下采取联合行动 a后转移到新状态 s′的概率。O：S×A×S→[0，1]表示系统的观测函 数。 O(o|s，a，s′）表示状态s中采取联合行动a后转移到新状态 s′时获得联合观测 o={o1，…，oN}∈Ω 的条件概率。 R：S×A→Z表示系统的效用函数。R(s，a）表示智能体集合在状态s中采取联合行动a后所获得的回报。H表示整个决策过程的总周期数，称为步数(Horizon）。下面给出关于NDN缓存问题的Dec-POMDP模型中各元组定义。

2.1 网络模型及相关假设

NDN网络模型如图3所示。网络由源服务器节点、路由节点以及用户节点构成。源服务器节点是内容数据的发布者，维护内容数据的一个永久副本。路由节点具备存储功能，可以缓存经过节点的部分数据。用户节点通过边缘路由节点向网络请求数据。用户请求被逐跳转发至拥有该请求内容的中间路由节点或源服务器节点，并触发相应数据包沿着请求兴趣包的反向路径传送给请求者。

在NDN中每个内容对象被划分成若干相同大小的数据块，并以数据块为单位进行存储。假设网络中共有M种不同的数据块对象，记为M，且都具有一个固定的数据源。考虑具有N个路由节点的网络，节点 n的缓存大小记为 Cn，且 Cn≪M；节点接收来自本地用户或相邻下游节点所转发的内容请求。节点n上的转发接口个数记为Fn。假设网络中的用户请求服从泊松分布，根据随机服务系统原理，服从泊松分布的输入流的输出也服从泊松分布，因此邻节点上未命中的请求序列也服从泊松分布。

图3 NDN网络模型

2.2 状态和状态空间

网络中的所有节点构成Dec-POMDP模型的智能体集合 N。记网络节点 n的状态为 sn=[xn，yn]，其中 xn=[x11，…，x1M，…，xFn1，…，xFnM]表示当前时刻节点n中各转发接口上待响应的内容请求的情况，xfnm表示节点n中第fn个接口上关于数据块m的待响应请求数量；yn=[yn1，…，ynM}表示当前时刻节点 n上 CS中的缓存情况，ynm∈{-1，0，1}表示数据块 m的缓存状态。ynm=-1表示节点n上不存在数据块m的副本；ynm=0表示节点n上拥有数据块m的临时副本，但数据块m不被存储于节点的CS中而是仅用于响应当前请求，且当数据转发完成后就会被立即删除；ynm=1表示数据块m被存储于节点n的CS中。各网络节点的状态构成当前决策时刻的网络状态，记为 s=[s1，…，sN]。

2.3 决策时刻

2.4 行动和行动空间

由NDN的工作原理可知，当收到响应数据包时，节点根据其CS中的存储剩余空间以及该内容被访问的情况来决定是否缓存该数据包的副本。因此，本文定义NDN节点接收到响应数据包的时刻为有效决策时刻。具体地，当事件或事件发生时节点不进行任何存储决策，此时节点n的行动记为an=。当事件发生时，(1）若节点 n的 CS具有剩余存储空间则直接缓存该数据包副本而不需要任何决策，也即采取行动an=；(2）若节点 n的 CS中无足够存储空间且节点需要存储该数据包，那么节点根据存储策略选择当前CS中的某个数据包 k(k∈{1， … ，M}）进 行 替 换 ，记为an=；(3）此外，令 an=表示节点n采取“不存储该数据副本”的行动。综上，网络节点n的行动空间An可以表示为：{-1，0，1，…，M}}。进而可得到所有网络节点的联合行动为 a=[a1，…，aN]，以及网络节点的联合动作

2.5 观测空间

在每个决策时刻，网络节点先获取当前网络状态的一个观测然后再进行存储决策。假设同一时刻只有一个事件e∈E发生。定义节点的观测表示当前决策时刻下该节点上CS中缓存内容的变化情况。具体地，当事件生，即节点接收到数据请求或完成数据请求服务时，定义节点 n的观测为 on=yn。 当事件生，即节点n接收到新响应数据包时，定义节点n的观测为 on=yn+2Bm，其中 Bi=(0，…，1，…，0）表示第i个元素为1的单位向量。根据上述定义可知，当Σon≤Cn时，节点不需要进行决策，当Σon=Cn+1时，节点需要根据存储策略删除CS中的某个数据块。进而各网络节点的本地观测on构成网络的一个联合观测 o={o1，…，oN}。

2.6 效用函数

网络性能分析是网络优化的基础，网络性能评价指标是判断网络优化效果的依据。常用的评价指标包括带宽、时延、吞吐量等。本文考虑以缓存命中率以及网络平均跳数作为联合策略的衡量标准。定义节点n的效用函数为：

如果对于任意联合策略向量ω(t），任意初始状态 s0，有 J(ω*(t），s0）≥J(ω(t），s0），那 么 策 略 ω*(t）为最优联合策略，其相应的最优性能值记为J*。

2.7 状态转移函数

由于当Σyn≤Cn时节点n采用贪婪存储策略，故不需要进行存储决策，仅考虑在Σyn=Cn+1的情况下，节点n在内部状态sn=[xn，yn]上采取行动an后转移到下一个状态的概率。

2.8 观测概率

定义M3={m|ynm=-1}表示不存在于节点n上的内容集合。根据节点观测状态的定义，可得到如下节点观测概率函数：

3 基于Dec-POMDP的分布式缓存协作策略搜索算法

Dec-POMDP模型最优策略的求解是一个NEXP-complete问题，即使是小规模的问题也往往需要在巨大策略空间上进行最优策略搜索，从而限制了其在较大规模实际问题中的运用。鉴于Dec-POMDP模型精确求解所要求的时间和空间复杂度高，因此不少学者致力于模型近似解的研究，通过利用动态规划或者启发式算法来搜索最优策略，以缓解模型求解过程的维度灾难和计算复杂度的问题。而Q学习算法作为经典的强化学习算法，近年来被广泛应用于多智能体系统体系结构模型的求解中[9-13]。此外，理想情况下，节点通过感知网络全局状态信息，并根据其他节点所采取的缓存策略进行缓存决策，从而实现网内缓存资源配置的全局最优化。然而，这种全域节点间的相互协作会带来大量的额外通信开销，因此实际中一般只考虑一定跳数范围内的节点协作方式。这里只考虑一跳的情况，即网络节点通过与相邻节点进行缓存协作逐渐达到整个网络的最优联合策略。基于上述考虑，本文采用一种近似的Q学习方法来求解局部最优策略。

定义节点n的邻居节点集合为Nn，根据文献[14]，假设网络状态满足状态转移独立性，则可以得到近似局部联合观测概率为：

4 数值仿真

为了评估本方案的性能，本文采用基于NS-3的ndnSIM[15]进行仿真。仿真拓扑共有100个节点，其中1个源服务器节点和20个客户端节点，其余为路由节点。源服务器节点中存储5 000个不同的数据，每个数据包的大小均为1 024 KB，数据包的流行度服从Zipf分布，实验中参数α的取值范围为0.7～1.3。除特殊说明外，实验中路由节点 CS的总容量设定为数据总数的10%，且初始为空。客户端通过边缘路由节点向网络请求数据，且请求到达率服从泊松分布。仿真时间为2 000 s，其余参数均为固定默认值。下面给出本文所提出的基于Dec-POMDP缓存算法与CEE、LCD缓存策略的实验结果对比分析。首先定义如下性能指标：

(1）平均缓存命中率：定义为由网内路由节点服务的请求数与总的用户请求数之比，即：

式中，Req_hitn表示在路由节点上命中的请求数量；Req_usern表示路由节点n上接收到的本地用户请求个数。

(2）平均跳数减少率：反映由于缓存系统的加入使用户请求内容跳数减少的比率，定义为：

式中，hop_csi表示缓存命中节点到请求用户间的跳数；hop_seri表示请求用户到源服务器节点间的跳数；R_count表示总的用户请求数。

图4为不同缓存策略下，用户请求在网内的平均缓存命中率随Zipf分布参数α变化的曲线。如图所示，相比于另外两种策略，基于Dec-POMDP的缓存策略能够显著提高用户请求的缓存命中率。这是由于Dec-POMDP模型中节点在进行缓存决策时考虑了邻居节点间的缓存协作，因此能够有效地减少缓存内容的冗余度，提升缓存利用率。此外，随着参数α的增大，三种策略的缓存命中率不断增大；当参数α大于1.1时，命中率增大的速率有所减缓，这主要是受限于网络路由节点的缓存容量。

图4 平均缓存命中率随参数α变化曲线

图5为不同缓存策略下，用户请求的平均跳数减少率随Zipf分布参数α变化的曲线。由于Dec-POMDP模型能够更好地刻画网络状态的不确定性和用户请求的随机性，因此Dec-POMDP策略能够更准确地预测请求内容的流行度并有选择性地缓存更有价值的内容，从而有效减少用户请求所需的跳数。

图5 平均跳数减少率随参数α变化曲线

图6为不同缓存策略下，用户请求在网内的平均缓存命中率随网内存储总容量变化的曲线。由图可知，在不同网内存储容量配置下，基于Dec-POMDP的缓存策略的性能均优于CEE和LCD，说明本文提出的缓存策略能更有效地利用缓存资源。此外，对于CEE和LCD两种缓存策略，当网内存储容量小于15%时，网内存储容量的增加对平均缓存命中率的提升效果并不明显；当网内存储容量继续增加直至达到35%时，网内请求的平均缓存命中率有显著提升；此后，网内存储容量继续增长，平均缓存命中率的增长速度逐渐变缓。这是因为这两种策略存在缓存冗余，因此无法充分利用网内缓存资源。而基于Dec-POMDP的缓存策略由于能够处理请求的动态变化，因此在不同网内存储容量下均能更有效地利用缓存资源。

图6 平均缓存命中率随网内存储容量变化曲线

图7为不同缓存策略下，用户请求的平均跳数减少率随网内存储总容量变化的曲线。从图中可看出，在不同网内存储容量条件下，三种缓存策略的平均跳数减少率性能曲线与图6中对应的曲线趋势相符。由于基于Dec-POMDP的缓存策略能够有效地利用缓存资源，因此在不同网内存储容量下，基于Dec-POMDP的缓存策略相对于CEE和LCD能够更有效减少用户请求所需的跳数；且随着网内存储容量的增加，基于Dec-POMDP的缓存策略与另两种策略间的性能差异越明显。

图7 平均跳数减少率随网内存储容量变化曲线

5 结论

NDN作为一个新型的网络体系架构，广泛存在的网内缓存是其最重要的特征之一。然而，必须合理地利用NDN中有限的网内缓存资源才能充分发挥NDN网络的性能。因此，本文将NDN中的网内缓存问题抽象为一个多智能体分布式协作的Dec-POMDP模型，并将其建模为一个多目标优化问题。基于缓存性能与网络通信开销的权衡，本文仅考虑有限跳数范围内的网内节点缓存协作并在该模型的基础上提出了一种近似Q学习的强化学习算法以求解局部最优缓存策略。仿真实验结果表明，基于Dec-POMDP缓存策略能够根据用户请求的动态变化更好地分配缓存资源，从而提高了用户请求的网内缓存命中率，有效地缓解了服务器压力。