命名数据网络中一种基于流行度预测的协作缓存方法

摘要

本发明请求保护命名数据网络中一种基于流行度预测的协作缓存方法，命名数据网(Named Data Networking,NDN)中网内存储内容时，采用沿路径多处缓存策略或在重要节点缓存策略造成了网内节点数据高冗余度和缓存空间利用率低。本文采用了“部分协同缓存”的方式，首先对内容进行未来流行度预测后，每个节点分出最优比例的缓存空间充当本地缓存空间，来存储流行度高的内容。每个节点剩下的部分通过邻域协作方式来存储流行度比较低的内容。通过考虑兴趣包在网络中节点命中和服务器端请求命中经过的跳数来计算出最优的空间划分比例。这种方法和传统的缓存策略相比，增加了网内缓存空间利用率，降低网络中的缓存冗余量，提高网内节点缓存命中率，提升整个网络的性能。

说明书

技术领域

本发明是对命名数据网中缓存策略的研究，属于未来网络的技术领域。特别涉及到网络中内容流行度的预测机制、邻域节点间的协作缓存策略，节点缓存空间比例的划分方法。

背景技术

随着互联网技术与应用的飞速发展，“宽带化”、“内容化”与“个性化”已经成为网络发展的主旋律，人们对于数据内容的需求日益强烈，网络应用的主体逐步向内容请求和信息服务演进转移。据Cisco公司预测，到2016年互联网上所有内容相关的流量将占据超过97.5％的份额，传统以主机为中心的网络体系结构难以满足当前网络信息服务的发展要求。为此，信息中心网络(Information-Centric Networking,ICN)作为一种革命式的未来互联网设计思路，让数据内容本身成为网络通信的主体单元，将网络通信模式从关注“where”(地址、服务器)转变为关注“what”，即用户和应用通信的目的和意向，成为未来Internet设计的重要模式。其中，命名数据网络(Named Data Networking,NDN)作为典型的ICN网络体系结构，在中间层用命名数据取代IP，数据传输采用“发布-请求-响应”模式，直接以内容名字进行路由，实现点到多点的高效内容分发。

在NDN的设计中，采用网络内普遍缓存的方式，在兴趣包(interest packet)沿途转发路径(on-path)的所有节点上存储命中内容。在路由转发中，当节点收到兴趣包，依据内容名字依次在内容存储器(Content Store,CS)，待处理兴趣包列表(Pending Interest Table,PIT)和转发信息列表(Forwarding Information Base,FIB)中进行匹配查询。应答数据包(data packet)携带请求内容，依据节点PIT表项的记录，沿请求路径进行反向的逐跳传输。

对于NDN网络，合理的内容放置和缓存决策，是有效发挥网络性能的关键因素。关于NDN缓存的研究，在一开始提出内容中心网络的时候，基于其“缓存换带宽”基本思想，就着手研究网内缓存策略了。但由于NDN泛滥式的沿途全部缓存方式(Leave Cache Everywhere,LCE)，致使节点缓存内容趋于同质化，导致大量的缓存冗余。相继有研究进行改进提出了LCD、MCD、Prob、WAVE缓存策略，LCD在返回路径存储时，不再在所有节点进行存储备份，只在命中节点的下游单个节点进行存储。MCD与LCD相比，在下游节点缓存备份后，把命中节点的该内容删除，这样虽然大大降低了网内的缓存冗余度，但是每请求一次，请求的内容备份在网络中位置就会转移一次，增加了网络的流量开销。WAVE考虑了单个文件在网络中是分成若干个chunk数据块进行存储的特征，chunk数据块之间存在关联性，当用户以文件为单位进行请求时，随着请求次数的增多，在返回路径上按照指数增加网内的缓存备份。这样可以快速把请求多次的内容即流行度高的内容扩散到网络边缘。上述策略在缓存时，缺乏对于内容本身差异化特征的考虑，无法实现内容的优化存储。因此，为了有效发挥内容网内节点缓存的优势，高效缓存算法的设计就成为需要解决的关键问题。

现有策略并没有考虑到节点在网络拓扑结构中的位置对缓存带来的影响，Chai等人提出了Betw缓存策略，即当兴趣包在网内节点或服务器端命中，获取数据包后在返回路径上的介数(betweenness centrality)最高的节点处进行缓存备份。这种“less for more”思想是让尽量少的节点来满足尽量多的用户请求，但是上述策略并没有对返回的内容进行流行度高低的区分，导致介数高的节点缓存空间在短时间内被存满，流行度高的内容有可能短时间内被后续的流行度低的内容替换掉。当用户再次请求时，在网内节点不能命中，需要路由到服务器，增加了网络开销。基于此，崔现东等人在Betwe策略基础上进行了改进，考虑到Betwe策略中选取的节点中内容替换率过高，他们加入了替换率因素，选取介数高同时内容替换率比较低的节点作为缓存位置。上述策略只在少数的位置进行了内容不加区分地存储，其余位置不佳的节点空间将会被闲置，造成了网内缓存空间的浪费。在对请求频率高和频率低的内容没有区别对待时，分布拖尾比较长的低流行度内容挤占了需要被缓存的高流行度内容的空间。

发明内容

本发明所要解决的问题是：现有缓存策略一类是通过普遍缓存方式把内容快送推送到边缘节点，导致出现网内缓存数据高冗余度。一类是选取网络拓扑中重要节点集中缓存内容，导致网内存储空间大部分被空置浪费。为了对网内节点缓存空间的最大化利用，本发明对网络中的内容进行流行度预测，提出的策略既对网络中流行度高的内容实施多重备份，又对流行度低的内容实施协作缓存，保存少量备份，从而使得网内节点缓存空间充分被利用。提出一种既可以满足用户对高流行度内容的高频率请求，又可以满足用户在网内节点命中流行度低的内容，有效降低内容源端服务器的负载压力，降低用户的请求延时，同时提高请求在网内节点的命中率的命名数据网络中一种基于流行度预测的协作缓存方法。本发明的技术方案如下：

命名数据网络中一种基于流行度预测的协作缓存方法，其包括以下步骤：

101、流行度预测：根据命名数据网络中内容被访问的频率以及内容到请求端的距离，对内容进行流行度预测，得出未来流行度高的内容和流行度低的内容；把每个节点的缓存空间划分成两部分x和(c-x)，(c-x)用来缓存高流行度的内容，x用来缓存低流行度的内容；

102、对步骤101中流行度高的内容在返回路径上所有节点都缓存一个备份，而流行度低的内容在返回路径节点邻域上综合状态最优的节点进行协作缓存，只缓存单一备份。

进一步的，步骤101中流行度的预测除了考虑内容在单个节点内被访问的次数R_count，还考虑被用户请求时的平均跳数H_average，通过设定计数周期T来记录周期内被访问的次数R_count，通过兴趣包来记录每次请求命中的跳数，这样考虑内容在节点的本地流行度和在整个网络中的缓存位置远近，预测下一个周期的流行度。

进一步的，步骤101对内容进行流行度预测包括：计算在下一个计数周的流行度P(T_n+1)的：

$P\left(T_{n+1}\right)=\frac{1}{\alpha +1}\left(\frac{H_{average}*R_{count}}{T_n}\right)+\frac{\alpha }{\alpha +1}P\left(T_n\right),0<\alpha <1$

其中P(T_n)表示请求内容当前的流行度，H_average是在一个周期内数据每次被访问的平均跳数，R_count表示命中节点中该内容被请求的次数，T_n表示命中内容当前计数周期，α是调节常数，ΔP表示当前周期的预测流行度值和上一周期流行度的差值，ΔP＝P(T_n+1)-P(T_n)，若ΔP＞0，表明内容处于流行度上升阶段，缓存时在返回路径上每个节点都缓存；若ΔP＜0，表明该内容处于流行度下降阶段，在返回路径上和其他节点协作缓存。

进一步的，预测计算出内容流行度后，(1)当请求的内容k在网内节点或服务器端命中后，根据自身当前的流行度P(T_n)和兴趣包附给的转发跳数以及请求内容在命中节点被请求的次数计算出未来的流行趋势P(T_n+1)，再得出ΔP的正负；

(2)若ΔP＞0，内容k在返回路径上的所有节点进行存储,且不能超过节点存储划分出的c-x容量；如果节点缓存空间c-x已满，则启用单个节点内的缓存替换策略LRU；

(3)data k若处于流行度下降期，首先找出路径上最大CoP(v)值对应的节点，若有该内容k，说明在路由期间已经有其他节点请求过相同内容，并且根据缓存策略把data k存储在该点，此时直接丢弃；若没有该内容则和其表中的临近节点CoP(v)_n值做比较，找出CoP(v)最大值，存于对应节点。

进一步的，所述整个网络中存在三种存储方式：每个节点存储高流行度内容的存储空间(c-x)；每个节点存储低流行度内容的存储空间x；服务器存储原始数据备份的存储空间。

进一步的，步骤102中流行度低的内容在返回路径节点邻域上节点的综合状态用CoP(v)来表示节点的综合状态：设当前节点PIT中各个内容名字对应接口数量为D_name1，D_name2…，D_{name>，那么总的请求接口数为Dtotal(v)＝Dname1+Dname2+…Dname>，当前接口数可以直接反映节点被请求的速率，C(v)表述各个节点的连接性，公式如下：}

$CoP\left(v\right)=\frac{C\left(v\right)}{D_{total}\left(v\right)}$

CoP(v)值越大，表示该点连接性能好的前提下被访问的速率越慢。

本发明的优点及有益效果如下：

本发明通过对内容流行度的准确预测，区分出内容的流行度高低，在缓存时进行采取不同的策略，可以使流行度高的内容快速推送到边缘节点，使用户更快地在网内命中请求的内容。使流行度低的内容占用少量的存储空间，在节约存储空间的同时可以满足用户对其低频率的请求，即使不能在网内命中，可以路由到服务器端找到请求的内容，额外的开销也在容忍范围之内，对整个网络的开销影响较小。该新型缓存策略既可以满足用户对高流行度内容的高频率请求，又可以满足用户在网内节点命中流行度低的内容，有效降低内容源端服务器的负载压力，降低用户的请求延时，同时提高请求在网内节点的命中率。

附图说明

图1是本发明提供优选实施例内容流行度预测流程图；

图2为本发明中协作缓存策略流程图；

图3为本发明中确定节点空间划分比例流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。

1.如图1所示为内容流行度预测流程图。节点请求到达率一般采用泊松分布，而整个网络中的内容分布符合zipf分布。也即二八分布，网络中的排名次序前20％内容可以满足网络中80％的请求量。如下式所示：

C为常数

p(i)表示i对应内容出现的频率，i表示在所有内容排序中的次序，排序按照内容出现频率的高低，从高到低的次序排列。则总数为N个内容中排序为i的内容被请求的概率为：

$r(i;s,N)=\frac{1/i^s}{{\Sigma }_{j=1}^N(1/j^s)}=\frac{1/i^s}{H_{N,s}},i=1,2,\mathrm{...}(0<s<1,1<s<2)$

其中s越大，表示流行的内容越集中。排名前k个内容的概率分布为：

$F(i;s,N)=\underset{i=1}{\overset{k}{\Sigma }}r(i;s,N)=\frac{H_{k,s}}{H_{N,s}},k=1,2,\mathrm{...}$

除了服务器内存储的内容具有长期稳态性外，网内的内容处于高动态性，20％流行度高的内容也在不断更替，不断有高流行度内容退化成流行度低的部分，流行度低的内容也有部分在向流行度高进化。研究表明，网络中动态内容的流行度或热度都符合从低谷到达峰值，在经过一段时间后回落到低谷。所以我们设定计数周期，在兴趣包中添加一个计数位H_count和时间T_n，每转发一次计数加1，当命中后停止计数达到H_count，也即请求端到命中节点的总跳数，命中节点中该内容被请求一次也计数一次，用R_count表示，当到达周期T_n时停止计数。H_count可以间接反映该内容在整个网络中的备份位置，因为跳数越大，说明离请求端越远，R_count越大，说明对该内容请求越多，边缘节点没有足够的备份来满足请求。如果仅仅考虑内容在节点被请求的频率不能够预测对应内容在整个网络内的流行度，一般内容越靠近服务器端，被请求的次数相对就会越少，此时仅仅依靠在节点中内容被请求的次数，大多数内容将被判别为流行度低的内容。H_average是在一个周期内数据每次被访问的平均跳数，H_average*R_count的变化不仅可以反映内容在网内的流行度，也反映了该内容在该周期的网络开销，尤其是对靠近服务器的节点内容流行度的判断更加灵敏。计算在下一个计数周的流行度P(T_n+1)：

$P\left(T_{n+1}\right)=\frac{1}{\alpha +1}\left(\frac{H_{average}*R_{count}}{T_n}\right)+\frac{\alpha }{\alpha +1}P\left(T_n\right),0<\alpha <1$

其中P(T_n)表示请求内容当前的流行度，T_n表示命中内容当前计数周期，α是调节常数。上式展开得：

$P\left(T_{n+1}\right)=\frac{1}{\alpha +1}*\frac{H_{average}*R_{count}}{T_n}+\frac{\alpha }{{(\alpha +1)}^2}*\frac{H_{average}*R_{count}}{T_{n-1}}+\frac{{\alpha }^2}{{(\alpha +1)}^3}*\frac{H_{average}*R_{count}}{T_{n-2}}+\mathrm{...}$

越靠近当前周期的计数对未来的流行度预测占的比例越高，影响越大，距离当前周期越远，对内容的未来的流行度影响越弱。

ΔP＝P(T_n+1)-P(T_n)

若ΔP＞0，表明内容处于流行度上升阶段，缓存时在返回路径上每个节点都缓存。若ΔP＜0，表明该内容处于流行度下降阶段。在返回路径上和其他节点协作缓存。

2.如图2为协作缓存策略流程图。当ΔP＜0时，内容处于流行度下降期，采用协作缓存。协作缓存的节点根据每个节点的连接性C(v)好坏来选取。在此我们计算各个节点的连接性的方法如下：

$C\left(\nu \right)=\underset{n\in {\pi }_1\left(\nu \right)}{\Sigma }Q\left(v\right)=\underset{n\in {\pi }_1\left(\nu \right)}{\Sigma }\left(\beta \right|{\pi }_1\left(n\right)|+(1-\beta \left)\underset{\omega \in {\pi }_1\left(n\right)}{\Sigma }{c}_{\omega }\right)$

其中π₁(n)表示距离节点n为1的所有节点，π₁(v)表示距离节点v为1的所有节点。β是属于0到1之间的调节常数，其中

$c_{\omega }=\frac{2\left|\right\{e_{ij}:i,j\in {\pi }_1\left(\omega \right),i\ne j\left\}\right|}{C_D\left(\omega \right)\left(C_D\right(\omega )-1)}$

e_ij表示点i和点j连接的边，C_D(ω)表示和ω相连的所有节点数，C(v)越大，表示v点的紧密性越好。在上述方法中不仅仅考虑节点的半径范围r＝2的临近节点的个数，还考虑临近节点之间的联系度。这样可以更加准确筛选出紧密性更好的节点。只考虑节点连接性可能导致性能好的节点收敛速度过快，使内容快速向这些节点聚合，造成节点拥塞，为了缓解拥塞，减轻节点的负载，我们综合考虑节点连接性和节点被访问速度。PIT结构中含有{内容名字；请求接口}，我们设当前节点PIT中各个内容名字对应接口数量为D_name1，D_name2…，D_{name>，那么总的请求接口数为Dtotal(v)＝Dname1+Dname2+…Dname>。当前接口数可以直接反映节点被请求的速率。所以我们提出用CoP(v)来表示节点的综合状态：}

$CoP\left(v\right)=\frac{C\left(v\right)}{D_{total}\left(v\right)}$

CoP(v)值越大，表示该点连接性能好的前提下被访问的速率越慢，如果在该点缓存内容，既保证了后续请求能够快速请求到该点，又不会出现高的替换率和请求率，同时可以有效缓解节点的负载。

每个节点在原有的数据结构上增加一个新的数据结构，结构单元组包括{节点名称，对应CS中内容列表，对应PIT接口数目}，用来记录其周围距离为2的范围内节点的协作缓存内容列表和接入接口数。如若邻域节点有重复的内容条目，则只保留CoP(v)最高的节点处备份。

步骤：

(1)当请求的内容k在网内节点或服务器端命中后，根据自身当前的流行度P(T_n)和兴趣包附给的转发跳数以及请求内容在命中节点被请求的次数计算出未来的流行趋势P(T_n+1)，再得出ΔP的正负，

(2)若ΔP＞0，内容k在返回路径上的所有节点进行存储,且不能超过节点存储划分出的c-x容量；如果节点缓存空间c-x已满，则启用单个节点内的缓存替换策略LRU。

(3)data k若处于流行度下降期，首先找出路径上最大CoP(v)值对应的节点，若有该内容k，说明在路由期间已经有其他节点请求过相同内容，并且根据缓存策略把data k存储在该点，此时直接丢弃。若没有该内容则和其表中的临近节点CoP(v)_n值做比较，找出CoP(v)最大值，存于对应节点。

3.图3是节点缓存空间划分的流程。当存储流行度上升时期的内容时，在返回路径上每个节点划分的(c-x)部分进行缓存以保证更多的请求能够最快命中。划分合适比例的缓存空间采取相应的存储策略将变得十分重要，如果划分的(c-x)过少，则很快被存满，替换率过高，如果划分的太多，协作缓存效果将会降低，整体缓存策略几近退化为LCE缓存策略，对网络性能的提升非常有限。本文采用兴趣包从客户端发出到命中节点之间的跳数作为请求代价，在节点线性处理速度前提下，跳数也间接反映了请求延时。

在本文提出的策略中,内容在网络中存在三种存储方式，因此请求的内容在网络中命中的平均跳数也存在不同。假设interest包在节点的c-x部分命中，对应的跳数为h₁：

$h_1(x=x_j)=\underset{i=1}{\overset{n}{\Sigma }}\underset{k\in c-x}{\Sigma }{r}_{ik}{y}_{ik}{h}_{c-x}$

interest包在节点的协作缓存x空间内命中，对应的跳数为h₂：

$h_2(x=x_j)=\underset{i=1}{\overset{n}{\Sigma }}\underset{k\in x}{\Sigma }{r}_{ik}{y}_{ik}{h}_x$

假设没有在网络找到相应的内容，interest包路由到服务器，对应的跳数为h₃：

$h_3(x=x_j)=\underset{i=1}{\overset{n}{\Sigma }}\underset{k\in s}{\Sigma }{r}_{ik}{y}_{ik}{h}_s$

约束条件为：

0＜x_j＜c

0＜c-x_j＜c

y_ik∈{0,1}

其中n代表节点数，N代表chunk数据块数目，r_ik表示每个节点i观测到对内容k的请求速率，服从泊松分布。y_ik表示请求内容是否命中，命中y_ik＝1，否则y_ik＝0。h是命中以后请求路径的跳数。根据内容不同的缓存方式，用k∈c-x，k∈x，k∈s分别表示本地缓存内容，协作缓存内容和服务器缓存内容。如果x取0，相当于完全没有协作缓存，是处处缓存策略，导致节点空间快速存满，流行的内容也很快被替换掉，interest包在网络中间节点命中率很低，这样总的跳数必然会很大。x取c时，网络的缓存策略是所有节点的所有缓存空间进行协作缓存，这样会导致流行度高的内容在网络中的备份会减少，客户端请求的流行度高的内容和流行度低的内容的跳数基本一样，跳数也会很大。所以存在x∈(0,c)这样的一个点，使网络的总跳数最小。问题可以转化为如下描述:

Min(h₁+h₂+h₃)

$x^{*}=\arg \underset{x_j}{Min}(h_1+h_2+h_3)$

h表示整个网络的请求路由跳数。对于x的求解，我们对x进行从0到c枚举，求出最小的h对应的x，即作为x^*。进行归一化处理即是最优协同深度值ρ：

$\rho =\frac{x^{*}}{c},0<\rho <1$

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。