基于流行度的数据命名网络的均衡分布缓存方法
基于流行度的数据命名网络的均衡分布缓存方法
【技术领域】
[0001] 本发明涉及一种数据命名网络的缓存技术领域，特别是涉及一种基于流行度的数 据命名网络的均衡分布缓存方法。
【背景技术】
[0002] 数据命名网络（NDN)是解决当前互联网不适应内容服务的众多方案中的一个。NDN着眼于目前互联网应用的特点，不再用IP地址该样标识内容属主的信息作为路由的索 弓I，提出按照内容的名字来查找和分发数据，并在分发数据经过的中间节点缓存数据。该样 数据请求可W不用到达数据源便能够被中间缓存节点应答。NDN的设计思想主要基于很多 网络用户或者应用只关注于内容本身、对于数据从哪里来的或者怎样来的并不关也的网络 应用事实。
[0003]NDN该种机制对于无线移动网络该样用户位置变化频繁的网络更为适应。当用户 移动到另外一个位置时，它可W使用数据名字从周围节点迅速请求或者重新请求到其所需 的内容，而不用像IP网络中为能够持续获得数据一定要保持同先前数据源节点的连接关 系W及与特定节点的邻接关系。而且，NDN不需要给每个节点分配IP地址，节点直接用应 用数据名字转发兴趣包和数据包，很好地避开了当前IP网络中移动节点的IP地址分配问 题。
[0004]但是，NDN网络结构要支持像Adhoc网络或者车载网络（C2C，不包括C2I)该样没 有基础设施的无线移动网络场景是有局限的，因为每个网络节点的存储能力是有限的。该 里我们将该样没有基础设施的、采用NDN基本机制构成的无线网络称为纯无线NDN网络。如 果对NDN机制不加W完善只采用基本的沿着数据经过的节点上缓存的方式，对于中间节点 来说，是很难支持的。为此，必须提供适当的缓存策略才能够满足无线网络的应用需要。
[0005]数据的流行度一个经常被缓存策略考虑的因素，但各种策略对请求计数的处理是 不一样的。比如，wave用文件请求计数的指数函数作为推荐下游节点缓存的文件子块数。 但在NDN网络中不具一般性，而且最终形成的数据分布还是比较集中，兀余度也比较高。还 有针对ISP(InternetServiceProvider)内部范围网络，要求各个节点维护树形的拓扑 结构，每个节点定期从其子树收集请求计数，对于计数小于阔值的数据则不予缓存。该算法 用复杂计算换取ISP外部流量的减少。不过算法真正实现起来限制比较大，而且只适合于 ISP内部，不适合计算能力比较弱、网络拓扑不规则且变化较快的纯移动NDN网络。该算法 还在每次请求命中的下一级节点上缓存数据，来让每个请求都将数据拉到离用户更近一些 的节点上。但该算法该样逐步拉近的做法对于数据离用户较远的情况还是会增加很多响应 时间。如果能在开始就将数据缓存到用户周围，那么就可W减少更多响应时间和网络流量。
[0006]另外在缓存节点的选择方面，NDN的基本方案是在应答数据途径的节点上缓存数 据。该样做的好处是可W梢带缓存，W最少的通信量达到最大可能的缓存。问题是可能占 用了过多的缓存空间，尤其是在纯移动NDN网络中移动节点缓存空间有限的情况下。也有 一些针对NDN的缓存策略，但因没有考虑到NDN无线环境的节点负载W及动态拓扑可能带 来的数据缓存集中。
【发明内容】
[0007] 针对上述问题中存在的不足之处，本发明提供一种基于流行度的数据命名网络的 均衡分布缓存方法，使其提高了响应速度、减少网络流量，同时又兼顾移动节点的缓存能 力、减少数据在网络中的兀余程度。
[0008]为了解决上述问题，本发明提供一种基于流行度的数据命名网络的均衡分布缓存 方法，包括如下步骤：
[0009] S10、中间节点要判断自己距离请求数据的节点的距离；
[0010] S20、在每个中间节点为每个数据记录其流行度；
[0011] S30、查询该节点中的PIT表，得到该数据包对应的跳数H;查询流行度表，得到该 数据包对应的流行度P;
[0012] S40、计算数据的缓存值，将该数据的缓存值与阔值进行比较，最终决定该节点是 否缓存到来的数据包。
[0013] 优选的，所述步骤S10中包括W下步骤：
[0014] S101、为了得到请求节点与中间节点的距离，在兴趣包中增加一个跳数字段；
[0015]S102、初始化NDN网络时，在PIT表中增加一个跳数项，记作h，对于PIT表中已有 该请求数据名字表项时，增加接口的同时，用新到来兴趣包中的跳数与原记录比较，记录更 新值为两者较大值；若PIT表中还没有该请求数据名字表项时，则增加表项，并直接用兴趣 包中的跳数填充该项。
[0016] 优选的，所述步骤S20中包括W下步骤：
[0017] S201、流行度表中的记录有固定的有效期，超过有效期的记录将被清除：即若数据 在一定时间内多次被请求，我们认为该数据比较流行，应该在中间节点缓存，否则认为缓存 的价值不大；
[0018]S202、找到数据包返回经过某个中间节点时，先考察该中间节点的存储能力，如果 缓存所需要的空间小于该节点的空闲空间的某个比例，就进行下一步判断，否则直接决定 不缓存。
[0019] 优选的，所述步骤S30中，在计算数据的缓存价值之前需要确定一个阔值，将数据 的缓存价值与阔值相比较。
[0020] 优选的，所述步骤S40中，缓存标志字段的设置是为了避免邻近节点的兀余存储 值的设置分为W下H种情况：
[0021] S401、如果计算出的缓存价值大于阔值，将缓存该数据包，但需在转发该数据包 时，将其数据包头中的缓存控制项设置为0;
[0022] S402、如果要转发数据的节点决定不缓存数据而只是转发数据，并且是因为上一 跳节点已经缓存而不再缓存，即数据包头中的缓存控制项为0时，将该缓存控制项设置为 1 ;
[0023]S403、如果该数据节点因为节点的空闲空间不够而不缓存，则将缓存控制项设置 为2。
[0024] 与现有技术相比，本发明具有W下优点：
[002引本发明为了让NDN网络能够支持Adhoc模式，对其缓存策略进行了研究，针对纯 无线NDN网络的特点，设计了一个缓存机制，让数据经过的中间节点综合考虑数据在网络 中的分布情况W及节点自身的缓存能力来决定是否在缓存该数据，该种缓存机制可W使数 据尽可能地接近需要的节点W提高响应速度、减少网络流量，但同时又兼顾移动节点的缓 存能力减少数据在网络中的兀余程度。
【附图说明】
[0026] 图1是本发明中实施例对兴趣包处理的流程图；
[0027] 图2是本发明中实施例对数据包处理的流程图；
[0028] 图3是本发明的实施例流程示意图。
【具体实施方式】
[0029] 为了使本发明的目的、技术方案及优点更加清楚明白，下面结合附图与实例对本 发明作进一步详细说明，但所举实例不作为对本发明的限定。
[0030] 如图1至图3所示，本发明的实施例包括如下步骤：
[0031] S10、中间节点要判断自己距离请求数据的节点的距离；
[0032] 为了得到请求节点与中间节点的距离，我们在兴趣包中增加一个跳数字段。该跳 数字段在兴趣包每次被转发时加一。
[0033] 此外在初始化NDN网络时，在PIT表中增加一个跳数项，记作h。对于PIT表中已 有该请求数据名字表项时，增加接口的同时，用新到来兴趣包中的跳数与原记录比较，记录 更新值为两者较大值巧P该跳数记录所有请求节点中最远的距离)。若PIT表中还没有该请 求数据名字表项时，则增加表项，并直接用兴趣包中的跳数填充该项。
[0034] S20、在每个中间节点为每个数据记录其流行度；
[0035] 该记录为一定时间内该节点收到的请求该数据的兴趣包的次数，该计数记做P。每 收到一个请求数据包该数据增加1。
[0036] 流行度表中的记录有固定的有效期，超过有效期的记录将被清除。即若数据在一 定时间内多次被请求，我们认为该数据比较流行，应该在中间节点缓存。否则认为缓存的价 值不大。
[0037] 在找到数据包返回经过某个中间节点时，先考察该中间节点的存储能力，如果缓 存所需要的空间小于该节点的空闲空间的某个比例，就进行下一步判断，否则直接决定不 缓存。
[0038] S30、查询该节点中的PIT表，得到该数据包对应的跳数H;查询流行度表，得到该 数据包对应的流行度P;
[0039] 在计算数据的缓存价值之前需要确定一个阔值，将数据的缓存价值与阔值相比 较。出于通用性的考虑，不管任何网络拓扑结构都将阔值设为2,其中流行度与跳数所占的 权值均为1。
[0040] S40、计算数据的缓存值，将该数据的缓存值与阔值进行比较，最终决定该节点是 否缓存到来的数据包。
[0041] 缓存价值Vi的计算公式如下：
[004引Vi=y(ah+目B。）（m〉=M)
[0043] 其中，h为查询PIT表中请求该数据的兴趣包的跳数，p为该数据的流行度，B为流 行度的基数(该里取2)。
[0044]a为跳数的权重系数，因为阔值中设定跳数的权重为1 =
T为某种拓扑结构，T长边可W为该拓扑结构的最长边长或者最长 路由路长，W长边的一半作为可缓存距离的参考值是为了实现网络中的均衡分布，因此可 得
[0045]目为流行度的权重系数。因为阔值中设定流行度的权重为
N为 某种拓扑结构中的节点个数，WN的十分之一作为可缓存流行度的参考值是为了使网络中 的缓存尽可能的缓存流行热 口的数据，因此可得
[0046]Y表示上一转发节点是否已经缓存过该数据，值为0、1、2中的一个，值来自于应 答数据包头中增加的缓存标志字段。
[0047] 缓存标志字段的设置是为了避免邻近节点的兀余存储，值的设置分为W下H种情 况：
[0048] ( 1)如果计算出的缓存价值大于阔值，将缓存该数据包，但需在转发该数据包时， 将其数据包头中的缓存控制项设置为0。
[0049] (2)如果要转发数据的节点决定不缓存数据而只是转发数据，并且是因为上一跳 节点已经缓存而不再缓存，即数据包头中的缓存控制项为0时，将该缓存控制项设置为1。 即Y值不影响下一跳节点对缓存价值的计算。
[0050] (3)如果该数据节点因为节点的空闲空间不够而不缓存，则将缓存控制项设置为 2。
[0051] 即Y值会使下一跳节点计算的缓存价值增加。原因是考虑按照远近和流行度，该 节点可能应该缓存数据，但是没有缓存，所W希望下一跳节点能够缓存数据，即使下一跳节 点已经离请求数据距离较近。
[0052] 本实施例中构建一个无线网络结构，拓扑结构可W不尽相同，本实施例中采取的 是8*8的拓扑结构，依此假设路由路径，从而详细说明。
[00閲具体流程
[0054] 1、在一个拓扑结构8*8的网络中节点nodeO发出兴趣包i，请求的数据命名为： vide(Vfilml/03/001,而node63 拥有该数据包。
[00巧]2、根据最优路由原则，选择的路由路径为=0-8-9-17-25-26-27-28-36-44-45-46-54-62-63。
[0056] 3、在兴趣包i被发出时，在兴趣包中增加一个跳数字段h。该跳数字段在兴趣包每 次被转发时加一。
[0057] 4、因为在初始化网络时，已经在PIT表中增加了记录跳数的数据项，记作h，因此 当该兴趣包到来时，检查PIT表中是否已有该请求数据名字表项。如果有，在增加接口的同 时，用新到来兴趣包中的跳数与原记录比较，记录更新值为两者较大值（即该跳数记录所有 请求节点中最远的距离)。如果PIT表中还没有该请求数据名字表项时，则增加表项，并直接 用兴趣包中的跳数填充该项。例如当兴趣包到达节点node9时，兴趣包的跳数为2,如果此 时P口表中还没有该数据数据名字表项，则在node9的P口表中添加video/filml/03/001 对应的跳数项，其值为2 ;如果已有该数据数据名字表项，则比较2与该值的大小，取两者中 的较大值。
[0058] 5、然后需要在收到兴趣包的节点上使用一个流行度表记录该请求对应的数据包 的流行度。该记录为一定时间内该节点收到的请求该数据的兴趣包的次数，该计数记做P。 每收到一个请求数据包该数据增加1。当兴趣包i到达节点node9时，该节点上的流行度表 如果已有该数据包相对应的表项，则将其P值加一；否则就会增加video/filml/03/001对 应的记录，且将P值初始化为1。
[0059] 6、对于流行度表的维护通过其固有的有效期进行，超过有效期的记录将被清除。 该有效期参考值可W设为t=lmin。
[0060] 7、找到数据包后返回经过某个中间节点时，先考察节点本身的空闲存储空间，记 作m。然后计算缓存所需空间的大小M与m的比值，若小于某个特定值(推荐设为70%，给该 节点本身运转留下存储空间，不影响该节点的运转性能)，缓存该数据；否则不缓存该数据。
[0061] 8、查询该节点中的PIT表，得到该数据包对应的跳数h;查询流行度表，得到该数 据包对应的流行度P，然后计算数据包的缓存价值Vi。
[0062] Vi= Y ( a h+目化）（m〉=M)
[006引其中，a=l/巧*0.W=0. 25,目=1/炒）> 0. 016。h为查询PIT表中请求该数据的 兴趣包的跳数，P为通过查找流行度表获得的该数据的流行度，B为流行度的基数(该里取 2)，目为其权重系数。Y表示上一转发节点是否已经缓存过该数据，值为0、1、2中的一个， 值来自于应答数据包头中增加的缓存标志字段。
[0064] 9、数据包video/filml/03/001的大小为M，假设节点node62的空闲存储空间为 m62,假设70%*m62小于M，则node62不缓存该数据包，且因为是空闲空间不足，则将数据包 头中的缓存标志字段Y设为2。
[0065] 10、当数据包到达节点node54时，得到数据包video/filml/03/001在该节点上的 跳数为h54=12,流行度为p54=5,且此时的缓存标志字段为2,则可W计算得到此时数据包 的价值为V54=2* (0. 25*1化0. 016*25)=7. 024,因为7. 024〉2,所W缓存该数据包，并将数据 包头中的缓存标志字段Y设为0。
[0066] 11、当数据包到达节点node46时，节点存储空间足够但因为此时的缓存标志字段 为0,因此不缓存该数据包，且将数据包头中的缓存标志字段Y设为1，然后转发数据包。
[0067] 12、当数据包到达节点node45时，假设其的存储空间足够，则计算该数据包在节 点node45 上的价值为V45=l* (0. 25*10+0. 016*25)=3. 012,因为 3. 012〉2,所W缓存该数据 包，并将数据包头中的缓存标志字段Y设为0。
[0068] 如上步骤后，网络中的节点{node54、node45、node36、node27、nodel7}将会缓存 数据，当其他节点再次请求数据包video/filml/03/001时就不一定要从节点node63中获 取，而是可W从刚才已缓存的节点中取得。
[0069]W上对本发明所提供的一种基于流行度的数据命名网络的均衡分布缓存方法进 行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，W上实施 例的说明只是用于帮助理解本发明的方法及其核也思想；同时，对于本领域的一般技术人 员，依据本发明的思想，在【具体实施方式】及应用范围上均会有改变之处，综上所述，本说明 书内容不应理解为对本发明的限制。
【主权项】
1. 一种基于流行度的数据命名网络的均衡分布缓存方法，其特征在于，包括如下步 骤： S10、中间节点要判断自己距离请求数据的节点的距离； S20、在每个中间节点为每个数据记录其流行度； S30、查询该节点中的PIT表，得到该数据包对应的跳数H;查询流行度表，得到该数据 包对应的流行度P; S40、计算数据的缓存价值，将该数据的缓存价值与阈值进行比较，最终决定该节点是 否缓存到来的数据包。2. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤SlO中包括以下步骤： 5101、 为了得到请求节点与中间节点的距离，在兴趣包中增加一个跳数字段； 5102、 初始化NDN网络时，在PIT表中增加一个跳数项，记作h，对于PIT表中已有该请 求数据名字表项时，增加接口的同时，用新到来兴趣包中的跳数与原记录比较，记录更新值 为两者较大值；若PIT表中还没有该请求数据名字表项时，则增加表项，并直接用兴趣包中 的跳数填充该项。3. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤S20中包括以下步骤： 5201、 流行度表中的记录有固定的有效期，超过有效期的记录将被清除：即若数据在一 定时间内多次被请求，我们认为该数据比较流行，应该在中间节点缓存，否则认为缓存的价 值不大； 5202、 找到数据包返回经过某个中间节点时，先考察该中间节点的存储能力，如果缓存 所需要的空间小于该节点的空闲空间的某个比例，就进行下一步判断，否则直接决定不缓 存。4. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤S30中，在计算数据的缓存价值之前需要确定一个阈值，将数据的缓存价值与 阈值相比较。5. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤S40中，缓存标志字段的设置是为了避免邻近节点的冗余存储值的设置分为 以下三种情况： 5401、 如果计算出的缓存价值大于阈值，将缓存该数据包，但需在转发该数据包时，将 其数据包头中的缓存控制项设置为〇 ; 5402、 如果要转发数据的节点决定不缓存数据而只是转发数据，并且是因为上一跳节 点已经缓存而不再缓存，即数据包头中的缓存控制项为0时，将该缓存控制项设置为1 ; 5403、 如果该数据节点因为节点的空闲空间不够而不缓存，则将缓存控制项设置为2。
【专利摘要】本发明提供一种基于流行度的数据命名网络的均衡分布缓存方法，涉及一种数据命名网络的缓存技术领域。该发明包括如下步骤：中间节点要判断自己距离请求数据的节点的距离；在每个中间节点为每个数据记录其流行度；查询该节点中的PIT表，得到该数据包对应的跳数H；查询流行度表，得到该数据包对应的流行度P；计算数据的缓存价值，将该数据的缓存价值与阈值进行比较，最终决定该节点是否缓存到来的数据包。本发明提高了响应速度、减少网络流量，同时又兼顾移动节点的缓存能力、减少数据在网络中的冗余程度。
【IPC分类】H04L29/08, H04L12/861, H04L12/803
【公开号】CN104901980
【申请号】CN201410078589
【发明人】张丽, 赵家彦, 陈玄, 毕帅
【申请人】北京工业大学
【公开日】2015年9月9日
【申请日】2014年3月5日
【技术领域】
[0001] 本发明涉及一种数据命名网络的缓存技术领域，特别是涉及一种基于流行度的数 据命名网络的均衡分布缓存方法。
【背景技术】
[0002] 数据命名网络（NDN)是解决当前互联网不适应内容服务的众多方案中的一个。NDN着眼于目前互联网应用的特点，不再用IP地址该样标识内容属主的信息作为路由的索 弓I，提出按照内容的名字来查找和分发数据，并在分发数据经过的中间节点缓存数据。该样 数据请求可W不用到达数据源便能够被中间缓存节点应答。NDN的设计思想主要基于很多 网络用户或者应用只关注于内容本身、对于数据从哪里来的或者怎样来的并不关也的网络 应用事实。
[0003]NDN该种机制对于无线移动网络该样用户位置变化频繁的网络更为适应。当用户 移动到另外一个位置时，它可W使用数据名字从周围节点迅速请求或者重新请求到其所需 的内容，而不用像IP网络中为能够持续获得数据一定要保持同先前数据源节点的连接关 系W及与特定节点的邻接关系。而且，NDN不需要给每个节点分配IP地址，节点直接用应 用数据名字转发兴趣包和数据包，很好地避开了当前IP网络中移动节点的IP地址分配问 题。
[0004]但是，NDN网络结构要支持像Adhoc网络或者车载网络（C2C，不包括C2I)该样没 有基础设施的无线移动网络场景是有局限的，因为每个网络节点的存储能力是有限的。该 里我们将该样没有基础设施的、采用NDN基本机制构成的无线网络称为纯无线NDN网络。如 果对NDN机制不加W完善只采用基本的沿着数据经过的节点上缓存的方式，对于中间节点 来说，是很难支持的。为此，必须提供适当的缓存策略才能够满足无线网络的应用需要。
[0005]数据的流行度一个经常被缓存策略考虑的因素，但各种策略对请求计数的处理是 不一样的。比如，wave用文件请求计数的指数函数作为推荐下游节点缓存的文件子块数。 但在NDN网络中不具一般性，而且最终形成的数据分布还是比较集中，兀余度也比较高。还 有针对ISP(InternetServiceProvider)内部范围网络，要求各个节点维护树形的拓扑 结构，每个节点定期从其子树收集请求计数，对于计数小于阔值的数据则不予缓存。该算法 用复杂计算换取ISP外部流量的减少。不过算法真正实现起来限制比较大，而且只适合于 ISP内部，不适合计算能力比较弱、网络拓扑不规则且变化较快的纯移动NDN网络。该算法 还在每次请求命中的下一级节点上缓存数据，来让每个请求都将数据拉到离用户更近一些 的节点上。但该算法该样逐步拉近的做法对于数据离用户较远的情况还是会增加很多响应 时间。如果能在开始就将数据缓存到用户周围，那么就可W减少更多响应时间和网络流量。
[0006]另外在缓存节点的选择方面，NDN的基本方案是在应答数据途径的节点上缓存数 据。该样做的好处是可W梢带缓存，W最少的通信量达到最大可能的缓存。问题是可能占 用了过多的缓存空间，尤其是在纯移动NDN网络中移动节点缓存空间有限的情况下。也有 一些针对NDN的缓存策略，但因没有考虑到NDN无线环境的节点负载W及动态拓扑可能带 来的数据缓存集中。
【发明内容】
[0007] 针对上述问题中存在的不足之处，本发明提供一种基于流行度的数据命名网络的 均衡分布缓存方法，使其提高了响应速度、减少网络流量，同时又兼顾移动节点的缓存能 力、减少数据在网络中的兀余程度。
[0008]为了解决上述问题，本发明提供一种基于流行度的数据命名网络的均衡分布缓存 方法，包括如下步骤：
[0009] S10、中间节点要判断自己距离请求数据的节点的距离；
[0010] S20、在每个中间节点为每个数据记录其流行度；
[0011] S30、查询该节点中的PIT表，得到该数据包对应的跳数H;查询流行度表，得到该 数据包对应的流行度P;
[0012] S40、计算数据的缓存值，将该数据的缓存值与阔值进行比较，最终决定该节点是 否缓存到来的数据包。
[0013] 优选的，所述步骤S10中包括W下步骤：
[0014] S101、为了得到请求节点与中间节点的距离，在兴趣包中增加一个跳数字段；
[0015]S102、初始化NDN网络时，在PIT表中增加一个跳数项，记作h，对于PIT表中已有 该请求数据名字表项时，增加接口的同时，用新到来兴趣包中的跳数与原记录比较，记录更 新值为两者较大值；若PIT表中还没有该请求数据名字表项时，则增加表项，并直接用兴趣 包中的跳数填充该项。
[0016] 优选的，所述步骤S20中包括W下步骤：
[0017] S201、流行度表中的记录有固定的有效期，超过有效期的记录将被清除：即若数据 在一定时间内多次被请求，我们认为该数据比较流行，应该在中间节点缓存，否则认为缓存 的价值不大；
[0018]S202、找到数据包返回经过某个中间节点时，先考察该中间节点的存储能力，如果 缓存所需要的空间小于该节点的空闲空间的某个比例，就进行下一步判断，否则直接决定 不缓存。
[0019] 优选的，所述步骤S30中，在计算数据的缓存价值之前需要确定一个阔值，将数据 的缓存价值与阔值相比较。
[0020] 优选的，所述步骤S40中，缓存标志字段的设置是为了避免邻近节点的兀余存储 值的设置分为W下H种情况：
[0021] S401、如果计算出的缓存价值大于阔值，将缓存该数据包，但需在转发该数据包 时，将其数据包头中的缓存控制项设置为0;
[0022] S402、如果要转发数据的节点决定不缓存数据而只是转发数据，并且是因为上一 跳节点已经缓存而不再缓存，即数据包头中的缓存控制项为0时，将该缓存控制项设置为 1 ;
[0023]S403、如果该数据节点因为节点的空闲空间不够而不缓存，则将缓存控制项设置 为2。
[0024] 与现有技术相比，本发明具有W下优点：
[002引本发明为了让NDN网络能够支持Adhoc模式，对其缓存策略进行了研究，针对纯 无线NDN网络的特点，设计了一个缓存机制，让数据经过的中间节点综合考虑数据在网络 中的分布情况W及节点自身的缓存能力来决定是否在缓存该数据，该种缓存机制可W使数 据尽可能地接近需要的节点W提高响应速度、减少网络流量，但同时又兼顾移动节点的缓 存能力减少数据在网络中的兀余程度。
【附图说明】
[0026] 图1是本发明中实施例对兴趣包处理的流程图；
[0027] 图2是本发明中实施例对数据包处理的流程图；
[0028] 图3是本发明的实施例流程示意图。
【具体实施方式】
[0029] 为了使本发明的目的、技术方案及优点更加清楚明白，下面结合附图与实例对本 发明作进一步详细说明，但所举实例不作为对本发明的限定。
[0030] 如图1至图3所示，本发明的实施例包括如下步骤：
[0031] S10、中间节点要判断自己距离请求数据的节点的距离；
[0032] 为了得到请求节点与中间节点的距离，我们在兴趣包中增加一个跳数字段。该跳 数字段在兴趣包每次被转发时加一。
[0033] 此外在初始化NDN网络时，在PIT表中增加一个跳数项，记作h。对于PIT表中已 有该请求数据名字表项时，增加接口的同时，用新到来兴趣包中的跳数与原记录比较，记录 更新值为两者较大值巧P该跳数记录所有请求节点中最远的距离)。若PIT表中还没有该请 求数据名字表项时，则增加表项，并直接用兴趣包中的跳数填充该项。
[0034] S20、在每个中间节点为每个数据记录其流行度；
[0035] 该记录为一定时间内该节点收到的请求该数据的兴趣包的次数，该计数记做P。每 收到一个请求数据包该数据增加1。
[0036] 流行度表中的记录有固定的有效期，超过有效期的记录将被清除。即若数据在一 定时间内多次被请求，我们认为该数据比较流行，应该在中间节点缓存。否则认为缓存的价 值不大。
[0037] 在找到数据包返回经过某个中间节点时，先考察该中间节点的存储能力，如果缓 存所需要的空间小于该节点的空闲空间的某个比例，就进行下一步判断，否则直接决定不 缓存。
[0038] S30、查询该节点中的PIT表，得到该数据包对应的跳数H;查询流行度表，得到该 数据包对应的流行度P;
[0039] 在计算数据的缓存价值之前需要确定一个阔值，将数据的缓存价值与阔值相比 较。出于通用性的考虑，不管任何网络拓扑结构都将阔值设为2,其中流行度与跳数所占的 权值均为1。
[0040] S40、计算数据的缓存值，将该数据的缓存值与阔值进行比较，最终决定该节点是 否缓存到来的数据包。
[0041] 缓存价值Vi的计算公式如下：
[004引Vi=y(ah+目B。）（m〉=M)
[0043] 其中，h为查询PIT表中请求该数据的兴趣包的跳数，p为该数据的流行度，B为流 行度的基数(该里取2)。
[0044]a为跳数的权重系数，因为阔值中设定跳数的权重为1 =
T为某种拓扑结构，T长边可W为该拓扑结构的最长边长或者最长 路由路长，W长边的一半作为可缓存距离的参考值是为了实现网络中的均衡分布，因此可 得
[0045]目为流行度的权重系数。因为阔值中设定流行度的权重为
N为 某种拓扑结构中的节点个数，WN的十分之一作为可缓存流行度的参考值是为了使网络中 的缓存尽可能的缓存流行热 口的数据，因此可得
[0046]Y表示上一转发节点是否已经缓存过该数据，值为0、1、2中的一个，值来自于应 答数据包头中增加的缓存标志字段。
[0047] 缓存标志字段的设置是为了避免邻近节点的兀余存储，值的设置分为W下H种情 况：
[0048] ( 1)如果计算出的缓存价值大于阔值，将缓存该数据包，但需在转发该数据包时， 将其数据包头中的缓存控制项设置为0。
[0049] (2)如果要转发数据的节点决定不缓存数据而只是转发数据，并且是因为上一跳 节点已经缓存而不再缓存，即数据包头中的缓存控制项为0时，将该缓存控制项设置为1。 即Y值不影响下一跳节点对缓存价值的计算。
[0050] (3)如果该数据节点因为节点的空闲空间不够而不缓存，则将缓存控制项设置为 2。
[0051] 即Y值会使下一跳节点计算的缓存价值增加。原因是考虑按照远近和流行度，该 节点可能应该缓存数据，但是没有缓存，所W希望下一跳节点能够缓存数据，即使下一跳节 点已经离请求数据距离较近。
[0052] 本实施例中构建一个无线网络结构，拓扑结构可W不尽相同，本实施例中采取的 是8*8的拓扑结构，依此假设路由路径，从而详细说明。
[00閲具体流程
[0054] 1、在一个拓扑结构8*8的网络中节点nodeO发出兴趣包i，请求的数据命名为： vide(Vfilml/03/001,而node63 拥有该数据包。
[00巧]2、根据最优路由原则，选择的路由路径为=0-8-9-17-25-26-27-28-36-44-45-46-54-62-63。
[0056] 3、在兴趣包i被发出时，在兴趣包中增加一个跳数字段h。该跳数字段在兴趣包每 次被转发时加一。
[0057] 4、因为在初始化网络时，已经在PIT表中增加了记录跳数的数据项，记作h，因此 当该兴趣包到来时，检查PIT表中是否已有该请求数据名字表项。如果有，在增加接口的同 时，用新到来兴趣包中的跳数与原记录比较，记录更新值为两者较大值（即该跳数记录所有 请求节点中最远的距离)。如果PIT表中还没有该请求数据名字表项时，则增加表项，并直接 用兴趣包中的跳数填充该项。例如当兴趣包到达节点node9时，兴趣包的跳数为2,如果此 时P口表中还没有该数据数据名字表项，则在node9的P口表中添加video/filml/03/001 对应的跳数项，其值为2 ;如果已有该数据数据名字表项，则比较2与该值的大小，取两者中 的较大值。
[0058] 5、然后需要在收到兴趣包的节点上使用一个流行度表记录该请求对应的数据包 的流行度。该记录为一定时间内该节点收到的请求该数据的兴趣包的次数，该计数记做P。 每收到一个请求数据包该数据增加1。当兴趣包i到达节点node9时，该节点上的流行度表 如果已有该数据包相对应的表项，则将其P值加一；否则就会增加video/filml/03/001对 应的记录，且将P值初始化为1。
[0059] 6、对于流行度表的维护通过其固有的有效期进行，超过有效期的记录将被清除。 该有效期参考值可W设为t=lmin。
[0060] 7、找到数据包后返回经过某个中间节点时，先考察节点本身的空闲存储空间，记 作m。然后计算缓存所需空间的大小M与m的比值，若小于某个特定值(推荐设为70%，给该 节点本身运转留下存储空间，不影响该节点的运转性能)，缓存该数据；否则不缓存该数据。
[0061] 8、查询该节点中的PIT表，得到该数据包对应的跳数h;查询流行度表，得到该数 据包对应的流行度P，然后计算数据包的缓存价值Vi。
[0062] Vi= Y ( a h+目化）（m〉=M)
[006引其中，a=l/巧*0.W=0. 25,目=1/炒）> 0. 016。h为查询PIT表中请求该数据的 兴趣包的跳数，P为通过查找流行度表获得的该数据的流行度，B为流行度的基数(该里取 2)，目为其权重系数。Y表示上一转发节点是否已经缓存过该数据，值为0、1、2中的一个， 值来自于应答数据包头中增加的缓存标志字段。
[0064] 9、数据包video/filml/03/001的大小为M，假设节点node62的空闲存储空间为 m62,假设70%*m62小于M，则node62不缓存该数据包，且因为是空闲空间不足，则将数据包 头中的缓存标志字段Y设为2。
[0065] 10、当数据包到达节点node54时，得到数据包video/filml/03/001在该节点上的 跳数为h54=12,流行度为p54=5,且此时的缓存标志字段为2,则可W计算得到此时数据包 的价值为V54=2* (0. 25*1化0. 016*25)=7. 024,因为7. 024〉2,所W缓存该数据包，并将数据 包头中的缓存标志字段Y设为0。
[0066] 11、当数据包到达节点node46时，节点存储空间足够但因为此时的缓存标志字段 为0,因此不缓存该数据包，且将数据包头中的缓存标志字段Y设为1，然后转发数据包。
[0067] 12、当数据包到达节点node45时，假设其的存储空间足够，则计算该数据包在节 点node45 上的价值为V45=l* (0. 25*10+0. 016*25)=3. 012,因为 3. 012〉2,所W缓存该数据 包，并将数据包头中的缓存标志字段Y设为0。
[0068] 如上步骤后，网络中的节点{node54、node45、node36、node27、nodel7}将会缓存 数据，当其他节点再次请求数据包video/filml/03/001时就不一定要从节点node63中获 取，而是可W从刚才已缓存的节点中取得。
[0069]W上对本发明所提供的一种基于流行度的数据命名网络的均衡分布缓存方法进 行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，W上实施 例的说明只是用于帮助理解本发明的方法及其核也思想；同时，对于本领域的一般技术人 员，依据本发明的思想，在【具体实施方式】及应用范围上均会有改变之处，综上所述，本说明 书内容不应理解为对本发明的限制。
【主权项】
1. 一种基于流行度的数据命名网络的均衡分布缓存方法，其特征在于，包括如下步 骤： S10、中间节点要判断自己距离请求数据的节点的距离； S20、在每个中间节点为每个数据记录其流行度； S30、查询该节点中的PIT表，得到该数据包对应的跳数H;查询流行度表，得到该数据 包对应的流行度P; S40、计算数据的缓存价值，将该数据的缓存价值与阈值进行比较，最终决定该节点是 否缓存到来的数据包。2. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤SlO中包括以下步骤： 5101、 为了得到请求节点与中间节点的距离，在兴趣包中增加一个跳数字段； 5102、 初始化NDN网络时，在PIT表中增加一个跳数项，记作h，对于PIT表中已有该请 求数据名字表项时，增加接口的同时，用新到来兴趣包中的跳数与原记录比较，记录更新值 为两者较大值；若PIT表中还没有该请求数据名字表项时，则增加表项，并直接用兴趣包中 的跳数填充该项。3. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤S20中包括以下步骤： 5201、 流行度表中的记录有固定的有效期，超过有效期的记录将被清除：即若数据在一 定时间内多次被请求，我们认为该数据比较流行，应该在中间节点缓存，否则认为缓存的价 值不大； 5202、 找到数据包返回经过某个中间节点时，先考察该中间节点的存储能力，如果缓存 所需要的空间小于该节点的空闲空间的某个比例，就进行下一步判断，否则直接决定不缓 存。4. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤S30中，在计算数据的缓存价值之前需要确定一个阈值，将数据的缓存价值与 阈值相比较。5. 如权利要求1所述的基于流行度的数据命名网络的均衡分布缓存方法，其特征在 于，所述步骤S40中，缓存标志字段的设置是为了避免邻近节点的冗余存储值的设置分为 以下三种情况： 5401、 如果计算出的缓存价值大于阈值，将缓存该数据包，但需在转发该数据包时，将 其数据包头中的缓存控制项设置为〇 ; 5402、 如果要转发数据的节点决定不缓存数据而只是转发数据，并且是因为上一跳节 点已经缓存而不再缓存，即数据包头中的缓存控制项为0时，将该缓存控制项设置为1 ; 5403、 如果该数据节点因为节点的空闲空间不够而不缓存，则将缓存控制项设置为2。
【专利摘要】本发明提供一种基于流行度的数据命名网络的均衡分布缓存方法，涉及一种数据命名网络的缓存技术领域。该发明包括如下步骤：中间节点要判断自己距离请求数据的节点的距离；在每个中间节点为每个数据记录其流行度；查询该节点中的PIT表，得到该数据包对应的跳数H；查询流行度表，得到该数据包对应的流行度P；计算数据的缓存价值，将该数据的缓存价值与阈值进行比较，最终决定该节点是否缓存到来的数据包。本发明提高了响应速度、减少网络流量，同时又兼顾移动节点的缓存能力、减少数据在网络中的冗余程度。
【IPC分类】H04L29/08, H04L12/861, H04L12/803
【公开号】CN104901980
【申请号】CN201410078589
【发明人】张丽, 赵家彦, 陈玄, 毕帅
【申请人】北京工业大学
【公开日】2015年9月9日
【申请日】2014年3月5日
最新回复(0)