一种面向内容中心网络中基于内容分类的类别流行度缓存替换方法

摘要

本发明涉及一种面向内容中心网络中基于内容分类的类别流行度缓存替换方法。本发明包括：先判断节点剩余的缓存空间是否能够容纳新的数据内容；如果有足够的缓存空间缓存新数据内容；根据指数加权移动平均计算标准计算节点中所有内容类别的流行度，选择流行度最小的内容类别；将流行度最小的内容类别中预定义时间内被请求次数最少的内容项移除节点缓存；提取新数据内容名字字符串特征并进行分类；将新到达的数据内容项存入节点中相应的内容类别中，更新类别热度表和日志。本发明按内容名字分类可以更好的管理CCN中节点的缓存，使网络在通信过程中从内容名入手对内容进行查找和替换，平衡节点缓存中内容的多样性，提高缓存替换的效率。

说明书

技术领域

本发明涉及一种面向内容中心网络中基于内容分类的类别流行度缓存替换方法。 

背景技术

随着互联网的持续发展，人们对网络中内容的需求越来越大。当前基于TCP/IP的网络架构在网络控制、资源分配等方面的问题日益突出，互联网的重心已经从主机与主机之间的通信转移到怎样从互联网快速获取所要请求的内容。基于这个原因，国内外学者着手研究新的下一代网络体系架构，并展开了多个相关项目课题的研究，推动了下一代网络的发展，具有跨时代的意义。本发明主要研究的是一种新型的未来网络体系架构“内容中心网络”。CCN抛弃了传统网络中以主机地址为核心的通信方式，而转为以命名的内容为中心的网络思想，同时构建了新的体系结构和通信机制来适应未来网络的发展。文献《内容中心网络CCN研究进展探析》综述了CCN的相关研究，介绍了CCN的工作机制，并调研了当前CCN的研究热点问题及其挑战，分析了CCN主要比较优势与存在的问题，最后通过实验测试床验证了CCN的工作模式。 

缓存替换策略是CCN研究的关键部分，它关系到网络的整体性能。在CCN中经常使用的缓存替换策略有最近最少使用策略和最少使用频率策略及其它们的改进策略。文献《Modeling data transfer in content-centric networking》提到的LRU缓存替换策略，具有算法简单、易于实现、方便部署等特点，但是它们并没有充分考虑CCN动态性的特点，因此具有很大程度的不适应性。 

本发明提出了一种基于内容名字分类的类别流行度缓存替换策略，该策略根据CCN中内容的命名方式和名字唯一性的特点，提出了all-gram和R-值相结合的方法对内容名字字符串进行特征提取并分类，使得每个节点中的缓存首先以类别为单位来进行管理。并且采用指数加权移动平均的思想来计算每个节点中类别的流行度，通过时间距离大小对每个类别在规定的时间里被访问的次数赋予不同的权值来反映实时的流行度情况。在缓存替换过程中，优先替换节点中流行度最低的内容类别中的内容项，然后根据分类判定方法将新的内容存入节点中所属的相应类别中。 

发明内容

本发明目的在于提供通过内容分类和动态计算流行度的方式来实现缓存替换，能够充分考虑网络内容最近的动态特性，提高网络内容分发效率，减少节点有限网络缓存浪费的一种内容中心网络中基于内容分类的类别流行度缓存替换方法。 

本发明的目的是这样实现的： 

(1)当有新的数据内容到达时，先判断节点剩余的缓存空间是否能够容纳新的数据内容；如果有足够的缓存空间缓存新数据内容，则直接执行步骤(4)；如果没有足够的缓存空间缓存数据内容，则执行步骤(2)，进行缓存替换； 

(2)根据指数加权移动平均计算标准计算节点中所有内容类别的流行度，选择流行度最小的内容类别； 

(3)将流行度最小的内容类别中预定义时间内被请求次数最少的内容项移除节点缓存； 

(4)提取新数据内容名字字符串特征并进行分类； 

(5)将新到达的数据内容项存入节点中相应的内容类别中，更新类别热度表和日志。 

步骤(1)中，在判断节点剩余的缓存空间是否能够容纳新的数据内容之前，先检查节点CS表，查看缓存中是否已缓存该新的数据内容。 

中包括根据all-gram和R-值相结合的方法提取新数据内容名字字符串特征并对内容进行分类：n-gram模型利用一个长度为n的滑动窗口来截取一系列的子字符串，滑动窗口每次滑动一个长度单位，将经过n-gram模型处理后的内容名字序列，分割成连续的长度都是n的子字符串。 

本发明具有的有益效果： 

本发明提出了一种基于内容分类的类别流行度的缓存替换算法，将内容分类有效地避免了在计算流行度的时候对所有的内容单独去处理，只需要计算出每个内容类的流行度。这样在需要执行缓存替换的时候，首先将节点中流行度最低的类别中的某一内容项替换出缓存，然后将新到达的内容数据按名字归入到节点缓存中的已有类别中，从而完成缓存替换过程。与传统的LRU替换方法不同，基于内容分类的类别流行度缓存替换方法，考虑到了内容类别流行度，可使流行度高的内容相对来说可长时间存储于网络节点中。区别于传统的选取最近最久未使用的内容块进行替换的LRU方法，本发明提出的方法在步骤2、3中选取类别流行度最低的内容进行替换。并且，在步骤4中提出了根据all-gram和R-值相结合的方法将内容进行分类的思想，按内容名字分类可以更好的管理CCN中节点的缓存，使网络在通信过程中从内容名入手对内容进行查找和替换，平衡节点缓存中内容的多样性，提高缓存替换的效率。仿真实验结果表明，本发明提出的基于内容名字分类的类别流行度缓存替换策略相比于其它经典的替换策略在性能上具有一定的优势。 

附图说明

图1是本发明的总流程图； 

图2是本发明的网络拓扑结构示意图； 

图3是本发明的实验仿真参数表示意图； 

图4是本发明的计算流行度示例示意图； 

图5是本发明的n-gram示例示意图； 

图6是本发明的all-gram计算r值提取特征组合方法流程图； 

图7是本发明的不同大小节点缓存空间下平均缓存命中率示意图； 

图8是本发明的不同数目存根域下的平均缓存命中率示意图； 

图9是本发明的缓存命中率的恢复能力示意图； 

图10是本发明的不同大小节点缓存下服务器平均负载示意图； 

图11是本发明的不同数目存根域下服务器平均负载示意图； 

图12是本发明的样本时间选择大小对缓存命中率和服务器负载的影响示意图。 

具体实施方式

下面结合附图举例对本发明做更详细地描述。 

1、一种面向内容中心网络中基于内容分类的类别流行度缓存替换方法，其特征在于： 

步骤1：当有新的数据内容到达时，先判断节点剩余的缓存空间是否能够容纳新的内容；如果有足够的缓存空间缓存新数据，则直接进入步骤4；如果没有足够的缓存空间缓存数据，则进入步骤2，进行缓存替换，以缓存新数据。 

步骤2：根据指数加权移动平均(EWMA)计算标准计算节点中所有内容类别的流行度，选择流行度最小的内容类别； 

步骤3：将流行度最小的内容类别中预定义时间内被请求次数最少的内容项移除节点缓存； 

步骤4：根据all-gram和R-值相结合的方法提取新内容名字字符串特征并进行分类； 

步骤5：将新到达的内容项存入节点中相应的内容类别中，更新类别热度表和日志。 

步骤1中，在判断是否有足够缓存空间缓存新数据之前，先检查节点CS表，查看缓存中是否已缓存该数据。CS表中存储了经过该节点且未被被该节点缓存的所有内容。 

步骤2中包括，提取新内容名字字符串特征并将内容进行分类，以及计算内容类别的流行度。 

根据all-gram和R-值相结合的方法提取新内容名字字符串特征并对内容进行分类：n-gram模型n-gram是利用一个长度为n的滑动窗口来截取一系列的子字符串，滑动窗口每次滑动一个长度单位。当一个内容名字序列经过n-gram模型处理后，就会被分割成若干个连续的长度都是n的子字符串。 

在分类过程中，分类的准确与否往往与n值的选择有很大的关系，n-gram算法中对于n 值的选择没有固定的方法，有时候可能是根据人为的经验去尝试然后再选出最终的值。如果n值太小，可能会忽略字符串的结构和顺序，若n取值太大，则会降低字符串之间的相似度，造成错误的分类结果。因此，本发明提出了一种all-gram的思想。不再使用某一固定的n值对名字字符串进行分割，而是使用一系列的n值来分割，通过这样的方式会生成不同长度的n-gram子串，一般的来讲这些子串肯定会囊括原字符串所包含的重要特征和关键字。这样的话，经过all-gram思想分割最后形成的特征向量空间可以通过学习对训练样本进行高效快速的分类，提高分类的准确性。 

本发明采用R-值的特征选择方法，这种方法可以根据计算出的R值来判断特征的特点并把特征进行排名，选择对更容易进行分类的特征集合，从而为分类提供了比较理想的标准。在这个方法中使用了一个r因子来平衡词频。如下公式所示： 

$R\left(t\right)=\frac{p\left(t\right|C)}{p\left(t\right|\bar{C})+r}*r$

其中t是一个特征，C是目标分类，是非目标分类。r是可调因子，取值范围为0到1之间。P(t|C)是t在C中的先验概率，是是t在中的先验概率，计算方法如下两公式所示： 

$P\left(t\right|C)=\frac{\left|C_t\right|}{\left|C\right|}$

$P\left(t\right|\bar{C})=\frac{\left|{\bar{C}}_t\right|}{\left|\bar{C}\right|}$

其中|C_t|和分别是C和在有t出现的文档的个数。|C|和分别是C和中的文档数。 

因子r的值是在0到1之间可调的，当r取值较小时计算出的特征t具有低频但区分度高的特点，而当r值取较大时计算出的特征t具有高频但区分度低的特点。 

通过对CCN中内容名使用all-gram和r值计算相结合的方法获取特征，从而达到将缓存中的内容进行分类的目的，具体流程如图1所示。 

根据指数加权移动平均(EWMA)计算标准计算节点中所有内容类别的流行度：内容类别流行度的计算使用指数加权移动平均(EWMA)作为衡量基础。移动平均是统计学中的重要原理方法，简称均线。所谓移动是指在计算过程中，被计算的数据对象是变化的，随着时 间的变化数据要进行更迭。移动平均是一种在时间序列上对数据进行分析的方法。 

在CCN中，由于网络的动态性的特点，节点中的缓存内容随时间不同流行度变化很大，那么在计算内容类流行度的时候，只可能计算其在某一时间段内的流行度值，而且时间越近越能反映内容类别当前的流行度，这就可以利用指数加权移动平均的思想，为每一个内容类创建一个跟踪日志用来记录在预定义的一段时间内被请求的次数。把这段时间再细分为很小的时间段，给距离当前最近的时间段被请求访问的次数值赋予较高的权值，较远时间段的请求访问次数值则赋予较小的权值。根据指数加权移动平均的公式可知，这样的EWMA值在一定程度上决定了内容类的流行度，它作为本文计算的标准，计算公式如下所示： 

$\mathrm{EWMA}=\frac{C_i\left[j\right]+(1-\alpha )C_i[j-1]+{(1-\alpha )}^2{C}_i[j-2]+...+{(1-\alpha )}^t{C}_i[j-t]}{1+(1-\alpha )+{(1-\alpha )}^2+...+{(1-\alpha )}^t}$

其中C_i[j]是类别i在第j个时间段内被请求的次数。公式中t为正整数，表示取样总时间。α表示权重，在这里定义为2/(t+1)。 

步骤3所述，当新数据到达节点需要被缓存时，若剩余缓存空间没有足够空间容纳新数据，则需要替换掉CS表中原有数据。 

本发明通过将CCN节点中缓存内容进行分类，计算每个内容分类的流行度，将流行度最小的内容类别中预定义时间内被请求次数最少的内容项移除节点缓存，腾出足够缓存空间以容纳新数据。在剔除旧数据缓存新数据时，选择了流行度最小内容分类中被请求次数最少的内容，考虑了网络中内容的流行度，使得热点内容可长时间驻留节点缓存中，提高了缓存命中率，并提升了网络性能。 

步骤4中包括，all-gram模型和R-值特征选择方法。 

通过对CCN中内容名使用all-gram和r值计算相结合的方法获取特征，从而达到将缓存中的内容进行分类的目的。按内容名字分类可以更好的管理CCN中节点的缓存，使网络在通信过程中从内容名入手对内容进行查找和替换，平衡节点缓存中内容的多样性，提高缓存替换的效率。 

步骤5中包括类别热度表。 

类别热度表用来记录各个内容类的命中次数以及流行度值。当被请求的内容在缓存节点中，就认为是请求命中，并且在类别热度表中增加命中内容所属类别的次数。每当节点中有内容被请求而且命中时，类别热度表就会更新，并且可以计算出任意时间段的内容类别的流 行度，反映了网络中内容流行度时刻变化的特点，适应网络的动态特性。 

本发明采用基于NS-3的ndnSIM网络模拟器对CCN进行模拟。通过模拟来评估本文提出在CCN中基于内容分类的类别流行度缓存替换策略的性能，并且和具有代表性的缓存替换策略LRU、LRU-K、LFU和LFU-Aging进行比较。采用GT-ITM生成一个如图2所示的Transit-Stub网络拓扑结构。图中的拓扑网络包括了若干个存根网络。由于存根网络只处理源和目标都在子网的通信，只有一部分主机与外界通信，只有一个边界路由器，所以每个存根网络相当于一个兴趣组，当它请求了外界一个自己感兴趣数据内容时，会在自己的存根域内进行传输，这样使得该数据内容流行度产生变化。 

由于模拟环境所限，在模拟时配置了10个内容类别，每个内容类别中有50个内容项，每个存根网络与外界通信的时间间隔为30秒，也就是说，当它请求得到自己感兴趣的内容30秒之后，才能进行下一次的内容请求，这样有助于模拟网络的动态性，使内容的流行度时刻发生变化。默认选择以7秒为单位计算一次内容类的流行度，也就是时间计算样本为7秒，在时间样本中，记录每秒内容类被访问的次数，并根据时间距离的远近对访问次数赋予一定的加权来计算内容类的流行度，仿真参数如图3所示。 

CCN中的每个节点都有缓存能力，在本次试验仿真中，本发明是按照节点与网络所有内容总量的相对大小来定义节点缓存大小的。一般的定义节点缓存大小为网络中内容总量的10％到30％之间。例如当定义节点缓存大小为10％且网络中一共有1000个内容项时，则每个节点最多能缓存100个内容项。当然，在现实网络中，节点的缓存能力相对于网络内容总量是非常有限的。由于仿真的网络规模很小，所以采用比例的形式来表示节点缓存大小。本发明包括： 

步骤1：当有新的数据内容到达时，先判断节点剩余的缓存空间是否能够容纳新的内容；如果有足够的缓存空间缓存新数据，则直接进入步骤4；如果没有足够的缓存空间缓存数据，则进入步骤2，进行缓存替换，以缓存新数据。 

步骤2：根据指数加权移动平均(EWMA)计算标准计算节点中所有内容类别的流行度，选择流行度最小的内容类别； 

步骤3：将流行度最小的内容类别中预定义时间内被请求次数最少的内容项移除节点缓存； 

步骤4：根据all-gram和R-值相结合的方法提取新内容名字字符串特征并进行分类； 

步骤5：将新到达的内容项存入节点中相应的内容类别中，更新类别热度表和日志。 

节点i设立类别热度表用来记录各个内容类的命中次数以及流行度值。 

节点i为内容中心网络中任一缓存节点。 

结合图1，对本发明的具体实施方案作详细描述。本发明一种面向内容中心网络中基于内容分类的类别流行度缓存替换方法，包括以下步骤： 

步骤1：当有新的数据内容到达时，先判断节点剩余的缓存空间是否能够容纳新的内容；如果有足够的缓存空间缓存新数据，则直接进入步骤4；如果没有足够的缓存空间缓存数据，则进入步骤2，进行缓存替换，以缓存新数据。 

步骤2：根据指数加权移动平均(EWMA)计算标准计算节点中所有内容类别的流行度，选择流行度最小的内容类别； 

下面的用一个例子来说明利用指数加权移动平均来计算内容类别流行度的过程。如图4所示，假设某个缓存节点中按内容分成10个类别，将预定义的时间分成7个小的时间段，如图4所示，图中每个时间段下面的数值表示在这个时间段内内容类别被请求的次数。在这个例子中可以看到在预定义的时间内，第一、九、十类别的内容被请求总次数相同，而在每个小的时间段内被请求次数变化很大，特别是第九类别和第十类别的内容被请求次数在单个的时间段内形成明显对比。如果只考虑各内容类别在预定义时间内被请求次数的平均值，则认为它们在这段时间内的流行度是相同的，但是这显然是不符合逻辑的，因为在CCN中，流行度在任意时刻都可能发生变化，在一段时间内进行平均的估计计算肯定是不准确的，应该对时间进行划分，划分的越细致越好，这样计算出的内容类别的流行度才能很好的反映真实的网络情况。利用指数加权移动平均的方法来动态计算内容类别的流行度，通过给最近的时间段内各内容类别被请求次数的值赋予较高的权值，其它的数值根据时间段的距离赋予的权值依次减小，计算出的结果如图4的右边部分所示，并且对计算出的流行度值按从高到低进行了排名。通过这种方式的计算，可以使得当新数据到达节点时能被有效的存储在缓存中，如果有新的数据到达时，节点的缓存剩余空间不足以容纳它，则要进行缓存替换过程，通过动态的对内容类别流行度的计算和排名，可以使缓存替换过程具有更高的效率。 

步骤3：将流行度最小的内容类别中预定义时间内被请求次数最少的内容项移除节点缓存； 

步骤4：根据all-gram和R-值相结合的方法提取新内容名字字符串特征并进行分类； 

n-gram模型实质是N-1阶马尔科夫模型，n-gram是利用一个长度为n的滑动窗口来截取一系列的子字符串，滑动窗口每次滑动一个长度单位。当一个内容名字序列经过n-gram模型处理后，就会被分割成若干个连续的长度都是n的子字符串。该模型是假设在一个由若干个词组成的具有一定长度的句子中，其中第n个词的出现只和前面n-1个词相关，与其它任何词都不相关，整句的概率就是各个词出现概率的乘积。数学模型可表述为：假设一个句子由m个 单词组成，定义W＝w₁，w₂，w₃，...，w_m，则认为单词w_i(1≤i≤m)的出现只与整个前文w₁w₂w₃...w_i-1有关，则句子W出现的概率为：p(W)＝p(w₁，w₂，w₃，...，w_m) 

＝p(w₁)p(w₂|w₁)p(w₃|w₁²)...p(w_m|w₁^m-1) 

公式中w₁^m-1表示w₁，w₂，w₃，...，w_m-1，p(w_m|w₁^m-1)表示在给定的前文信息w₁，w₂，w₃，...，w_m-1的情况下，词根w_m出现的概率。这些概率的计算可以通过语料中n个词同时出现的次数得到。但是在实际情况中，m的值常常会非常大，从而导致p(w_m|w₁^m-1)的计算十分复杂，而且需要更多存储空间。为了克服这个问题，可以进一步假设当前词根的出现只依赖于前面的n-1个词根。那么可以得到如下公式： 

p(W)＝p(w₁)p(w₂|w₁)p(w₂|w₁²)...p(w_n|w₁^n-1)...p(w_m|w_m-n+1^m-1) 

在上式中，w_m-n+1^m-1表示w_m-n+1w_m-n+2...w_m-1。 

n-gram在支持向量机分类器中运用非常广泛，通过将文本内容运用n-gram算法分割成一定长度的文本片段序列，然后进行过滤选择，保留频度较高的符合要求的片段序列形成文本内容的特征向量表。字符串同样可以看做文本的形式去处理分类。本发明主要是针对英文的内容名，假设CCN中所有的内容都是以英文形式进行分层命名，而且英文字母序列中的字母词语关联性不大，非常符合n-gram模型的假设条件。以内容名字sina.com.cn/myvideos/TigerT.mpg/_v<timverinfo>/seg2中的“myvideos”为例子，如图5所示。 

在分类过程中，分类的准确与否往往与n值的选择有很大的关系，n-gram算法中对于n值的选择没有固定的方法，有时候可能是根据人为的经验去尝试然后再选出最终的值。如果n值太小，可能会忽略字符串的结构和顺序，形如“software”这样的词通过4-gram得到的5个子串soft，oftw，ftwa，twar，ware，但是却没有一个与软件的意思是相关的，若n取值太大，则会降低字符串之间的相似度，造成错误的分类结果。比如“keyword”一词，通过6-gram所形成的字串却没有一个突出了原词的重要特征，使得分割没有意义。因此，本发明提出了一种all-gram的思想。不再使用某一固定的n值对名字字符串进行分割，而是使用一系列的n值来分割，通过这样的方式会生成不同长度的n-gram子串，一般的来讲这些子串肯定会囊括原字符串所包含的重要特征和关键字。这样的话，经过all-gram思想分割最后形成的特征向量空间可以通过学习对训练样本进行高效快速的分类，提高分类的准确性。 

通过对CCN中内容名使用all-gram和r值计算相结合的方法获取特征，从而达到缓存中 的内容进行分类的目的。具体流程如图6所示。首先对样本集进行训练，然后用all-gram的方法训练样本集进行特征提取，得到内容名字的特征集S，同时利用计算R值的方法对特征集S中的特征进行计算并排名，选择排名靠前的特征组成特征词典，最终形成特征集S1。根据特征集S1就可以进行分类实验，把CCN中缓存的内容按内容名进行分门别类。 

步骤5：将新到达的内容项存入节点中相应的内容类别中，更新类别热度表和日志。 

为了验证本发明中提出的基于内容分类的类别流行度缓存替换在性能上的优越性，将本发明方法与传统的缓存替换方法替换策略LRU，LRU-K，LFU，LFU-Aging进行实验对比。 

图7是不同大小节点缓存空间下平均缓存命中率示意图。从图7中可以看出在节点的缓存容量与网络内存总量的比值分别设为10％，20％和30％，存根网络的个数为5个，时间样本为7秒的情况下，本发明提出的内容分类的类别流行度策略在设定的节点容量大小不同的条件下，总是比其它的几种替换策略表现出更好的性能。相反的，LFU和LFU-Aging则表现出了较差的命中率。 

图8是不同数目存根域下的平均缓存命中率示意图。从图8中可以看出在每个节点的缓存大小设为网络内容总量的20％的情况下，随着存根域数目的增多，大多数替换策略在平均缓存命中率的性能上都有明显的降低。特别是LRU-K和LFU-Aging，这两个策略只在存根域数目是一个的时候，性能好于LRU和LFU。但是，基于分类的流行度策略至始至终性能没有发生太大的变化，这说明这种策略能够充分的适应网络中存根域数目的变化。 

图9的折线图说明了在网络出现瞬间中断并恢复以后三种缓存替换策略在缓存命中率方面的恢复能力。如图所示的红线，说明在第150秒时网络出现了中断，三种策略的缓存命中率都出现了下降的状态，当网络恢复以后，分类的流行度策略迅速的恢复到网络断开前的状态，具有很高的缓存命中率。相反的，其他两种策略则表现出了较差的性能，恢复缓慢而且不稳定，特别是LFU-Aging相比于其它两种策略表现出了非常糟糕的缓存命中率。 

图10和图11分别是在不同大小节点缓存和不同数目存根域的条件下测试的服务器平均负载情况。和前面关于平均缓存命中率的仿真结果类似，LFU和LFU-Aging策略在减少原始服务器的平均负载的性能上是最差的，如图10所示，当存根域数目为5，且节点缓存容量为网络内容总量的10％时，分类的流行度策略比LFU策略减少约39％的原始服务器负载量。当存根域数目为9时，分类的流行度策略大概是LFU策略的服务器负载量的65％。因此，本发明提出的基于内容分类的类别流行度的缓存替换策略可以很好地减少服务器的负载情况，缓解网络的压力。 

图12是关于计算内容类别流行度的样本时间大小选择对节点的平均缓存命中率和服务器平均负载的影响示意图。从图中可以看到，当时间样本选择为7秒时，节点的平均缓存命 中率达到最高值，此时服务器的平均负载也处在非常小的状况。样本时间选择太大或太小，都不能得到较好的仿真结果。