内容中心网络碎片化内容访问的统计机制研究

雷 凯,邢 捷,汪 漪,李可可,林 栋

(1.北京大学深圳研究生院 互联网研发中心，广东 深圳 518055; 2.南方科技大学，广东 深圳 518055;3.华为技术有限公司，广东 深圳 518129)

0 引 言

互联网起源之初，主要的应用需求是计算资源的共享，而经过50多年的发展，互联网的使用已经发生了巨大的变化，现在互联网主要使用的需求是内容的获取和分发，基于端到端连接的TCP/IP存在着明显的不足，如大量重复传输相同的内容造成资源浪费等。作为新型的网络架构，内容中心网络(content centric networking,CCN)更加关注内容的本身，不再关心内容的存储位置[1],其通信过程不再基于“端到端”的连接，而是基于“请求内容-获得内容”的模式。CCN中的每个路由节点都具有数据包缓存的功能，这种特点能够让用户所请求的数据不仅仅来源于原始的内容服务器，也可以来源于网络内任意缓存该数据的节点。一旦其他用户请求同一内容数据，中间路由节点即可返回相应的数据，这增加了网络内数据的共享程度，同时能够使用户更快地获得请求的数据，提升用户的体验。因此，CCN受到了广泛的关注，其应用前景良好。

但是，CCN设计的缓存机制也会带来一个问题。在CCN中，多个路由器可以缓存相同的内容，一个内容的各个部分也可能分布在多个路由器中。这种内容的碎片化分布在提高网络效率、降低网络流量的同时，也会导致作为原始数据来源的内容提供商只能收到部分用户的访问内容请求，从而无法准确地获得其提供的内容的整体访问情况。但内容的整体访问统计数据，决定了内容的流行程度，是目前CCN中内容提供商的业务模式的关键指标。一方面，内容提供商需要内容的访问统计信息进行内容的定价收费服务。由于缺乏内容的整体访问统计数据，当热门内容的实际访问频率改变时，内容提供商无法实时地调整内容的收费策略来增加其利益；另一方面，内容提供商需要付费使用路由器提供商的缓存，缺少内容的访问统计信息，内容提供商就无法进行类似内容分发网络(content delivery network,CDN)[2]操作,将热门的内容放置到最合适的位置。

虽然有很多研究已经开始着手保证内容提供商的利益，但他们的研究都是基于这样一个前提：所有的网络设备都已经提前知道所有的内容的访问统计信息,即内容的流行度信息。但实际上，目前CCN无法提供这个前提条件。文献[3]提出了一种在CCN中基于内容受欢迎程度的缓存放置策略，越热门的内容其缓存位置离用户越近。文献[4-5]假定内容的流行程度符合广义Zipf分布，然后为运输网络、内容提供商等设计了一种基于博弈理论模型的缓存和定价策略，路由器通过设定一个价格阈值来决定是否进行内容缓存。文献[6]为内容提供商设计了一种基于缓存占用时间和内容流行程度的内容定价策略，当缓存成本随着缓存状态的变化而变化时，缓存策略和定价策略也能够进行动态的调整。文献[7]研究了信息中心网络(information centric networking,ICN)中多个内容提供商之间缓存资源分配的问题，并提出了一种有用的缓存分区方法，这种方法通过最大化各个提供商的效益总和来提高缓存的收益率，并且该方法支持差异化的服务。此外，文献[7]还提出了广泛的公平概念，并建立了可行的缓存市场经济模式。

在获取内容流行度方面，文献[8]基于局部的内容流行程度，提出了一种服务内容在传输路径上的缓存分配策略，主要关注在给定网络缓存位置的情况下，存储哪些服务内容能够使网络性能达到最优。文献[9]重新设计了缓存结构，并提出了基于缓存内容流行度动态变化的内容管理策略，具有高流行度的内容将延长该内容的缓存驻留时间，减少被替换掉的概率。但这些研究只是在局部获取了内容访问数据，而没有考虑到全局的优化以及提高内容提供商的感知能力等。

内容的整体访问统计数据决定了内容的流行度，内容的流行度信息在网络缓存和定价策略中起着一个非常重要的作用。对于CCN来说，在路由器的缓存存在成本前提下这是一个必不可少的要素。但是目前仍没有关于内容提供商如何获得其内容访问统计信息的研究，因此，内容提供商获取访问统计信息成了一个急需解决的问题。

为了消除CCN中缓存机制带来的问题以及让内容提供商准确地获得内容的访问统计数据，会有如下的3点挑战。

1)如何在中间路由设备中获取用户访问的内容信息；

2)如何将内容的访问统计信息经济、准确地存储在中间路由设备上。这要求该机制是轻量级的，可以和本地的CCN无缝结合；

3)如何将中间路由设备里的相关内容访问统计信息回传给内容提供商，从而内容提供商能够及时的获取内容的流行度情况。

本文提出了一种基于计数的内容访问统计机制来处理以上挑战。①当兴趣包或者数据包内容到达中间路由设备时，分析这些包的名字来获得用户所请求的内容；②为中间路由器中的缓存表的每个条目添加一个计数器，可以使用计数器来记录用户的请求次数；③中间路由器可以在指定时间通过类似用户操作来构造特殊兴趣包，并以这种形式将内容计数统计数据回传给内容提供商。

本机制的主要过程是当兴趣包到达中间路由设备时，中间路由设备通过分析兴趣包的名称以获得用户请求的内容，如果缓存表命中或者转发请求表命中，路由设备会根据需求进行计数操作。然后当满足一定条件时，中间路由设备会构建特殊的兴趣包，其名字包含待回传的内容的计数统计信息。然后，路由器可以模拟用户请求内容的方式，将该特殊兴趣包发送给内容提供商。内容提供商接收到这些特殊兴趣包后，分析请求内容名称,从而可以获得其内容的用户请求计数信息以及内容的流行度，制定合理的缓存策略和定价策略，保证内容提供商的利益。

1 背景与动机

1.1 CCN中的转发和缓存机制

CCN中的兴趣包和数据包有着不同的转发机制，路由器通过内容仓库(content storage,CS)、转发请求表(pending interest table,PIT)和转发信息表(forwarding information base,FIB)这3种逻辑结构来实现这2种类型的包的转发。CS是CCN节点的数据存储部件，其主要作用是提供数据缓存，PIT记录的是已经转发过的兴趣包的名字以及这些兴趣包所对应的接口信息，FIB记录了节点之间的转发规则，它是数据路由转发的主要依据。具体机制如图1所示。

当路由器收到兴趣包时，根据名字的最长公共前缀匹配算法在CS表中查找对应的数据，如果存在，就直接返回数据给用户，然后丢弃该兴趣包；如果CS表中不存在对应数据，则在PIT表中进行查找。如果找到对应的表项，说明路由器之前已经接收并转发过相同的请求，但尚未获得返回结果，所以在对应的PIT表项的接口列表中添加收到该兴趣包的端口号，并丢弃该兴趣包，不再转发；反之，则需要将该名字新增到PIT表中，并记录接收端口号，然后在FIB表中查找对应的转发端口。当FIB表中存在可以转发的端口时，则进行数据包转发，相反，如未查找到，则丢弃或返回请求包。

数据包作为兴趣包的响应，本身并不需要进行路由转发，只需要简单地沿着兴趣包被传输的相反路径返回。当路由器接收到数据包时，根据数据包携带的名字在PIT表中进行搜索，获取到转发端口列表，然后把数据包通过转发端口列表中的端口转发出去，并在CS表中缓存；如果没有搜寻到对应的PIT表项，或者PIT表项中记录同样内容的数据已经转发过，那么直接丢弃该数据包。

在CCN中，路由器通过CS表对数据包进行缓存，实现了相同数据的复用，提高了数据的可用性，改善了数据分发，提高了网络数据传输的效率。

1.2 转发和缓存机制的问题

网络拓扑图如图2所示。图2中，假设编号为16-31的叶子节点为用户，而编号为1的根节点为内容提供商。

图2 网络拓扑图Fig.2 Network topology

在原有的机制中，如果编号为16的用户发送了一个内容为A的兴趣请求，由于16→8→4→2→1这条路径中沿路的节点均没有存储内容为A的缓存，最终内容提供商会响应这请求并回复一个数据包。此时，内容提供商会记录到内容A有一次网络请求的操作。此后，当编号为17的用户请求同样的内容A时，其能够在编号为8的路由器中找到内容A的缓存，并由此路由器返回用户所请求的内容A。因此，由于网络缓存对兴趣包的截留，虽然提高了网络的通信效率，但同时导致了内容提供商缺失了编号为17的用户对内容A的网络请求信息，从而无法准确地判断内容A的流行度和价值。

在仿真100 s的实验中，16个用户一共发出了16 052次内容请求，由于中间路由器完成了用户的大部分请求回应，导致内容提供商实际上只进行了2 532次的请求应答，远远少于用户的请求次数，让内容提供商无法正确掌握其内容的网络访问情况。

因此，在CCN中，内容提供商需要借助某种机制来实现对其提供的内容的掌控，了解用户对内容的实际需求情况。

2 方案设计

为了解决CCN缓存机制带来的问题，本文提出了一种能够帮助内容提供商准确统计其内容访问情况的机制。该机制的统计方案主要分为3步：①在缓存的内容响应用户的请求，或者通过PIT表返回数据的同时，缓存计数器更新该内容的访问次数；②当内容的计数器数值达到阈值、或者缓存中内容被替换、过期时，路由器提取该内容的访问次数信息；③路由器通过构造带特殊名字的兴趣包，将内容的访问次数反馈给内容提供商。

通过这种内容访问统计机制，即使用户的请求在中间路由器上就被满足，内容提供商依然能够感知到这次请求的内容信息。

本机制的整体框架如图3所示，具体描述如下。

图3 整体框架图Fig.3 Overall Framework

1)当用户1向路由器 1发送内容为A的请求，路由器1会搜索其CS表，发现并没有内容A的缓存，则该请求会继续向上传递直到到达内容提供商Server处，然后数据沿请求路径反向返回。如步骤1和2(见图3)，此时沿路的路由器会缓存内容A，并且路由器1，2和内容提供商由状态0变为状态1；

2)当用户2请求同样的内容A时，兴趣包到达路由器1时，发现其有缓存内容A，此时，路由器1就会将内容A直接返回给用户2。如步骤3和4(见图3)，路由器1由状态1变为状态2，内容A的计数值增加；

3)路由器根据特定的算法，在内容A的访问频率变化后，将内容A的访问信息发送给内容提供商，如步骤5(见图3)；

4)内容提供商在更新内容A的访问频率后，可以制定关于内容A的收费策略以及缓存策略等，并在随后将这些策略随内容A一起发送，如步骤6和7(见图3)。

通过以上的步骤，内容提供商可以充分了解到用户对内容的实际需求情况，确定内容的流行度和价值，从而能够更好地服务用户。

2.1 路由器的访问统计操作

为了能够正确反映内容的网络访问情况，并经济、准确地将访问统计信息存储在中间路由器上，本机制在路由器的CS结构中的每个条目添加一个计数器，如图3左上所示，记录内容的访问次数，在满足一定的触发条件时，路由器就会将内容的访问情况发送给内容提供商。如果兴趣包直接被路由器丢弃，则这个数据包不参与统计。具体计数统计操作以及反馈统计信息给内容提供商的流程伪代码如算法1所示。

在CCN中，当路由器的CS表中没有相应兴趣包的缓存而PIT表中有该兴趣包的转发记录时，该兴趣包会聚合到已有的表项中。由于PIT表项聚合的特性，在统计内容访问次数时，需要将PIT的表项聚合次数也考虑在计数器中，以保证统计的准确性，因此，本机制在数据包到来时也会有相应的统计操作。综上所述，内容的计数信息可以表达为计数总和=CS命中次数(路由器)+PIT命中次数(路由器)+CP提供次数(内容提供商)。

算法1内容统计的算法。

Algorithm.1Algorithm for content statistics

1: while receive interest A do

2: if cache hit then

3: CS.A.counter←CS.A.counter+1

4: if CS.A.counter.value up to Threshold then

5: Make special interest of A to CP

6: CS.A.counter←0

7: end if

8: else if PIT hit then

9: {pit.A.facelist}←{pit.A.facelist}+interest A.face

10: drop interest A

11: else:

12: forward by FIB

13: end if

14: end while

15:

17: if old content B be replaced then

18: make specinal interest of B to CP

19: end if

20: if PIT. A facelist.size>1 then

21: CS.A.counter←CS.A.counter+PIT.A.facelist.size

22: end if

23: end while

24:

25: while CS.A.FreshnessPeriod is timeout do

26: Make special interest of A to CP

27: end while

2.2 路由反馈统计信息的条件

在2.1节中描述了路由器统计访问次数的方法，本节则具体说明路由器反馈统计信息的触发条件。当CS表满足以下3个条件之一时，路由器就需要构造特殊的兴趣包，将统计信息反馈给内容提供商。

2.2.1 CS表中内容被替换

当CS的容量已满，而又有新的内容到达路由器时，某个旧的内容就会被替换出去。此时，为了获得被替换内容的访问信息，就需要将被替换内容的具体计数值构造特殊兴趣包放入到网络中。内容提供商是特殊兴趣包对应的数据的唯一提供者，中间路由器没有该兴趣包对应数据，因此，内容提供商会接收到这个特殊兴趣包并获得被替换内容的计数信息。

2.2.2 CS表中内容计数值达到阈值

热门内容可能会被消费者频繁地访问，从而在路由器的CS表中长时间存储，如果只在这些热门内容被替换出CS表时才反馈内容统计信息给内容提供商，那么内容提供商无法及时获得热门内容的访问情况，因此，需要对计数器设定一定的阈值。每当CS表中某一内容的值超过阈值时，路由器可以将这个热门内容的计数信息构造兴趣包并回传给内容提供商，同时重置这热门内容的计数器的值。这样内容提供商就能够及时的获得热门内容的访问信息。同时，阈值可以根据内容的流行度进行动态的调整以适应网络的变化。

2.2.3 CS表中内容生存时间到期

当用户访问频率很低时，CS表中的内容可能既不被替换，其计数器的值也达不到设定的阈值。当这部分内容的生存时间到期时，它们会从CS表中清空，而这部分内容的访问情况也要回传给内容提供商。因此，当CS表中内容的有效期过期时，路由器要将这个过期的内容的计数信息构造兴趣包回传给内容提供商。

2.3 特殊兴趣包反馈方法

当路由器构造完具有特殊名字的兴趣包后，会进行类似用户请求内容的操作，路由器构造具有独特名字的计数兴趣包，这个特殊名字包含着计数信息以及特殊标记等内容，然后将此兴趣包放入网络中，由于在建立路由表项时会在每个路由器的FIB表中预先配置这些兴趣包的转发路径，这些带有计数信息的兴趣包会一步一步地转发到内容提供商，来获取到相应的数据包(这个数据包为空包，用于消除路径上的PIT表项)。同时内容提供商可以根据这个兴趣包的名字来获取到路由器所反馈的内容的计数信息，从而达到统计网络中内容的访问情况的目的。

3 实验说明

实验使用ndnSIM[10](基于NS3的模拟器)来评估本机制的性能。CCN与传统的网络架构不同，每个节点都具有缓存数据的功能，消费者的请求很有可能在中间节点就被满足而无需到达内容提供商，而内容提供商主要关心的也是这部分内容的统计信息，因此，评价本机制需要如下的指标。

1)准确率。计算用户发送请求次数以及内容提供商获得的实际内容使用次数的比率。理想情况下两者应该相同，内容提供商能够完全了解用户的需求情况。但由于网络拥塞、丢包等情况的存在，这两者仍有不可避免的差异。

2)效用。由于CCN的缓存机制，内容提供商接收到的用户请求会比用户实际发出的请求少。在这种情况下，本文将原始机制中内容提供商收到的请求数与本机制中内容提供商收到的请求统计数进行对比，以获得本机制的实用性。

3)额外开销。本机制的额外开销以路由器发送特殊兴趣包的个数来衡量。实验评估了不同的缓存容量和缓存生存时间对额外开销的影响。

3.1 实验设置

实验使用图2中的树形拓扑结构进行测试。服务内容的请求服从Zipf-Mandelbrot[11]分布，服务的内容数量为100，其数据报文大小完全相同。用户请求报文的到达过程符合泊松过程，每秒钟用户发出10次内容请求。同时每个路由具有相同的缓存容量大小，并使用LRU的缓存替换策略。计数器的阈值初始值设为20，且可以随着内容访问频率的改变而动态的变化。

设置实验进行1 200 s的仿真。消费者在0～1 000 s内请求内容，并在1 000～1 200 s内停止请求。然后，路由器根据数据反馈条件，将缓存数据的计数信息构造特殊兴趣数据包，并回传给内容提供商。通过这种方式，内容提供商可以接收到消费者请求的完整统计信息，以确保实验的准确性。

在实验中需要观察CS表容量和缓存生存时间对实验的准确性、效用和额外开销的影响。理论上CS表容量越小，缓存的生存时间越短，则缓存越容易被替换，路由器需要回传计数信息的时间间隔越短，其额外开销越大。

3.2 实验结果

3.2.1 CS容量的影响

实验用不同的缓存容量来进行试验对比。通过选取缓存容量占总内容的10%～50%进行测试，比较不同容量对评价指标的影响，同时固定路由器中每个缓存的生存时间为10 s。在1 000 s的仿真实验中，用户一共发出了160 410次请求，CCN中原始的缓存机制可以帮助内容提供商分流请求来降低内容提供商的压力，实验结果如图4所示。在图4中，随着缓存容量大小的增加，原始机制中内容提供商能够直接接收到来自用户的请求数量越来越少，导致内容提供商无法准确地获取其提供的内容的访问信息。例如，在缓存容量为40%的情况下，内容提供商只能够直接接收到25 688次用户的请求，远远小于用户的实际请求数量，从而造成了应有利益的损失。

图4 内容提供商在不同缓存容量下接收到的用户请求统计Fig.4 Requests statistics received by CP with different cache sizes

相反，通过本文机制可以稳定有效地统计99.9%以上的用户的请求并回传给内容提供商，同时其效用从1.35X～9.69X，会随着缓存容量的增加而不断地提高。路由器的额外开销(如图5所示)，则会随着缓存容量的增加而不断地降低。

3.2.2 缓存生存时间的影响

实验主要考虑缓存的生存时间对本机制的性能的影响。当路由器中的缓存到达生存时间时，路由器会主动删除此内容缓存来释放空间。实验设置缓存的生存时间为10～50 s，缓存的容量设置为总内容的40%，其余条件与之前实验一致。实验结果如图6所示。

图5 内容提供商在不同缓存容量下的额外开销Fig.5 Extra overhead for CP with different cache sizes

图6 内容提供商在缓存不同生存时间下接收到的用户请求统计Fig.6 Requests statistics received by CP with different life cycles of cache

在原始的CCN机制中，内容提供商只能接收到约15%左右的用户请求，并且随着缓存的生存时间的增加，内容提供商能够直接收到的请求会越来越少。而在本机制中，无论缓存的生存时间有多长，内容提供商都能够准确地获得用户实际的访问内容次数，准确率在99.9%以上，而路由器的额外开销如图7所示，也会随着缓存的生存时间的增加而降低。

总的来说，路由器的缓存容量越大，缓存的内容越不容易被替换，那么内容被替换而回传发生的概率越小，额外开销越低；缓存的生存时间越长，发生内容因超时而回传的概率越小，同样路由器的额外开销越低。同时，本机制的准确率与路由器和缓存配置参数基本无关，能够达到99.9%以上，其效用比原始机制更好。

4 总结

本文探讨了CCN中原始的转发和缓存机制会导致内容碎片化分布的问题，只有部分内容请求可以到达内容提供商，从而内容提供商难以准确获得其内容的访问次数并制定合适的定价策略。针对这一问题，本文提出了一种基于计数的内容访问次数的统计机制，在该机制中，路由器对消费者访问的内容进行计数统计操作，并在满足计数器达到阈值、缓存内容替换或过期条件时将内容统计信息回传给内容提供商，从而使内容提供商可以准确及时地获得其内容的访问次数。ndnSIM中的仿真实验表明，在该机制下，内容提供商获得其内容的访问频次的准确率高达99.9%。同时本机制进行了实际的测试，获得了良好的效果。

本文在研究如何将消费者访问的内容信息反馈给内容提供商的问题。内容提供商得知内容的访问统计数据后，可以更好地生产内容、对内容进行收费和管理，以提高其收益和对内容的感知能力。并且内容提供商还可以在网络设备有限的缓存空间中存储收益更高的内容，实现最优的缓存分配策略。

[1] XYLOMENOS G, VERVERIDIS C N, SIRIS V A,et al.A Survey of Information-Centric Networking Research[J].IEEE Communications Surveys & Tutorials,2013(99):1-26.

[2] PENG G.CDN:content distribution network[EB/OL].(2004-11-18)[2016-09-01].http://arxiv.org/abs/cs/0411069v1.

[3] ZHZNG G.An Optimal Cache Placement Strategy Based on Content Popularity in Content Centric Network[J].Journal of Information Computational Science,2014,11(8):2759-2769.

[4] HAJIMIRSADEGHI M, MANDAYAM N B, REZNIK A.Joint Caching and Pricing Strategies for Information Centric Networks[C]//2015 IEEE Global Communications Conference(GLOBECOM).San Diego,CA:IEEE,2015:1-6.

[5] HAJIMIRSADEGHI M, MANDAYAM N B, REZNIK A.Joint Caching and Pricing Strategies for Popular Content in Information Centric Networks[J].IEEE Journal on Selected Areas in Communications,2017,35(3):654-667.

[6] MA R T B, TOWSEY D. Cashing in on caching: on-demand contract design with linear pricing[C]//ACM Conference on Emerging NETWORKING Experiments and Technologies.Heidelberg,Germany:ACM,2015:1-6.

[7] CHU W, DEHGHAN M, TOWSLEY D, et al. On Allocating Cache Resources to Content Providers[C]//ACM ICN. Kyoto, Japan: ACM, 2016:154-159.

[8] 冯博昊,周华春,张宏科,等.智慧协同网络服务内容在传输路径上的缓存分配策略[J].通信学报,2016,37(3):129-138.

FENG B H, ZHOU H C, ZHANG H K, et al. Cache allocation policy of service contents along delivery paths for the smart collaborative network[J]. Tongxin Xuebao journal on Communication, 2016, 37(3):129-138.

[9] 张果,汪斌强,张震,等.基于节点动态内容流行度的缓存管理策略[J].电子学报,2016,44(11):2704-2712.

ZHANG G,WANG B Q,ZHANG Z,et al.A Strategy Based on Dynamical Content Popularity for Cache Management[J].Acta Electronica Sinica,2016，44(11):2704-2712.

[10] MASTORAKIS S, AFANASYEV A, MOISEENKO I, et al. NdnSIM 2:An updated NDN simulator for NS-3[EB/OL].[2016-04-13].http://ndnsim.net/2.4/.

[11] POWERS D M W. Applications and Explanations of Zipf’s Law[J]. Advances in Neural Information Processing Systems, 1998, 5(4):595-599.

(编辑：刘 勇)