2021, Vol. 47
2. 中国科学技术大学 先进技术研究院, 合肥 230088
2. Institute of Advanced Technology, University of Science and Technology of China, Hefei 230088, China
随着移动互联网的快速发展，现有的网络体系在可扩展性、移动性和安全性等方面逐渐出现性能瓶颈。为了适应互联网的需求变化，一种新的网络体系架构——信息中心网络（Information Centric Networks，ICN）[1]应运而生，而命名数据网络（Named Data Networks，NDN）[2]作为ICN架构的一种具体网络实现，受到研究人员的广泛关注。在NDN中，用户通过内容名称去获取内容，而无需关心内容从何而来，同时，在返回内容的过程中会在沿路根据缓存策略进行缓存。
近年来，考虑到NDN的优越性能，研究人员开始将NDN和移动自组织网络（Mobile Ad hoc Networks，MANET）相结合并进行分析[3-5]。传统的MANET基于TCP/IP协议进行通信，但是由于MANET中节点移动而引起了网络拓扑动态变化，导致其难以建立稳定的端到端链路，这不仅使得网络较难实现高效的数据传输，同时也阻碍了MANET的实际应用。由于MANET中多数通信是“以内容为中心”的信息共享，而不关心数据承载在哪个终端以及某个数据是由哪个终端产生，因此NDN适用于MANET[6-8]，其比“以主机为中心”的IP路由协议更有利于数据传输。
命名数据无线移动自组织网络（NDMANET）的研究起步较晚，许多问题亟待解决。其中，缓存策略是NDN中的一个关键技术[9-11]，由于MANET中节点的移动性、网络的动态性以及网络所呈现出的分布式特性，使得现有NDN中的缓存机制可能不再适用于NDMANET。因此，如何在节点空间资源有限、网络节点自由移动的MANET中有效保证数据的可用性，提高更高优先级内容的命中率，加快请求的响应速度，降低数据冗余，是NDMANET数据缓存机制研究中的关键问题。
不同于有线环境下可以扩展较大的缓存容量，无线环境下移动节点的缓存容量大小受限，因此，对缓存替换策略的研究显得尤为重要。目前，缓存替换策略主要包括先进先出（FIFO）、最近最少使用（LRU）[12]和最少经常使用（LFU）[13]。这些策略多数是从现有网络中演变而来，通常存在两点缺陷，一方面，它们没有考虑内容本身的特性，例如内容优先级、内容的访问频率等，另一方面，未考虑MANET应用场景下节点自由移动时重要节点脱离网络时引发重要内容不可用的问题。因此，上述策略并不适用于NDMANET这种新型网络架构。
本文分析NDN的特性，根据内容本身所传达的信息，如内容优先级、内容访问频率等指标，提出一种基于内容优先级的缓存替换策略PFC。通过向数据包添加新的TLV字段“priority”，设计决策函数实现缓存内容的替换，以在保证平均缓存命中率的同时提高重要内容的缓存命中率和可用性。
1 相关工作缓存机制包括缓存放置策略、缓存替换策略和缓存一致性维护策略等。缓存替换策略在缓存已满而需要缓存新对象时，决定如何替换出缓存中的一些旧对象，从而为新对象腾出空间。在NDMANET中，有限的缓存空间使缓存替换策略更具挑战性。NDMANET的缓存研究包括MANET和NDN 2个方面。
在MANET的相关缓存研究中，学者们提出了各种缓存技术。文献[14]提出一种SQUIRREL缓存软件，该软件可以集成到Internet的节点中，允许区域内的多个节点共享其缓存。文献[15]提出CachePath、CacheData和HybridCache 3种缓存方案，CachePath存储数据的位置和路径信息，CacheData通过存储数据而非路径来节省时间，HybridCache是一种混合方案。上述MANET缓存策略均基于TCP/IP网络，需要存储与内容对应的IP地址，因此，并不适用于NDN网络。
在NDN的相关缓存研究中，多数使用LRU、FIFO、LFU和Random策略作为缓存替换策略。为了提高NDN的性能，研究人员也为其设计了很多缓存算法。文献[11]提供了有关信息中心网络中缓存机制的调查结果，其分析不同的参数（如缓存时间、内容本身、内容相关性以及缓存中的生存期）对ICN缓存性能的影响。文献[16]提出一种ICN的缓存替换策略，其将内容的流行度视为替换指标，此外，还考虑网络中的全局流行度。但是，该策略不适用于NDMANET，一方面，对于NDMANET而言，全局内容流行度并不现实，而且还会对CS管理造成更多的负担；另一方面，该策略会延长缓存检索时间。文献[17]提出一种基于流行度的细粒度缓存替换策略FGPC，但是，FGPC仅使用请求频率来决定内容的替换。文献[18]提出一种基于层次流行度的缓存替换策略，其将内容流行度分为5个层次，每个数据包都属于一个流行度级别，当缓存已满时，将替换缓存中流行度最低的数据包。但是，该策略也导致一个问题，一些重要内容不一定是流行内容，仅通过流行度去决定缓存替换，对于一些特定内容将不合适。文献[19]提出一种通用缓存替换策略，节点可以通过各项指标，包括请求频率、节点距离、节点可达性等，综合决定替换内容，但是，该策略中的内容度量系统CMS的权重系数是根据节点和网络中心的距离来确定的，对于MANET这种去中心化的网络而言显然不合理。文献[20]将节点的位置加入到缓存替换决策中，但是，其决策函数考虑的因素较多，计算复杂度较高，从而提高了替换时的计算代价与响应时间。
从已有文献可以看出，MANET缓存研究是基于IP网络的，不适用于NDMANET网络，针对NDN的缓存替换策略也不适合NDMANET，原因是它们没有考虑节点的移动性、网络的去中心化等NDMANET的特性。此外，多数缓存策略并未考虑内容本身的优先级。因此，本文从内容的优先级出发，同时兼顾内容的请求频率，提出一种缓存替换策略PFC。
2 基于内容优先级的缓存替换策略有效的缓存替换策略可以提高缓存命中率，从而提升内容分发性能。但是，现有研究一方面未考虑NDMANET不同于传统NDN网络的3个特点：1）分布式控制，没有中心节点；2）节点的自由移动导致网络拓扑变化以及某些节点可能会“掉线”的情况；3）节点的资源有限。另一方面，现有缓存策略仅考虑内容的流行度而忽略了内容本身的优先级，这会导致重要内容的可用性降低，一旦重要节点离开网络，可能出现请求无响应的情况。
2.1 NDN缓存机制NDN的通信模型由消费者驱动，消费者发送兴趣包（Interest Packet）请求相应的数据包（Data Packet）。节点在收到兴趣包后，其内容缓存CS（Content Store）中如果有匹配的内容，则会返回数据包；否则，节点先查询未决兴趣表PIT，查看是否有记录，若无记录，兴趣包将根据转发信息表FIB在网络中进一步转发。在接收到数据包后，节点首先检查相关请求是否在PIT中，如果对该数据的请求仍然没有得到响应，则将数据进一步转发到网络中的下游，否则将丢弃该数据。同时，节点根据适当的缓存决策方案将数据存储在CS中，如果CS达到其最大容量，则根据缓存替换策略进行内容替换。NDN的通信流程如图 1所示。
|
Download:
|
| 图 1 NDN通信流程 Fig. 1 NDN communication procedure | |
在NDMANET中，内容的可用性指在网络中一部分节点出现故障后，网络整体是否还能响应消费者的请求。在一些实际的NDMANET应用场景，如军事活动、救援行动中，由于环境的复杂性，可能经常发生节点脱离网络的情况。如果该节点缓存了重要内容，可能会导致重要内容不可用。因此，对于NDMANET而言，节点可用性的重要程度不低于命中率、响应延时等指标。
常用的保证可用性的方法是在多处保留内容副本，对于NDN架构而言，其每个节点所带有的缓存能力可以很好地解决该问题，但是，这些是建立在缓存容量足够大的情况下。在移动场景中，大缓存意味着低移动性，为保证节点的移动性，高可用性需要与缓存替换策略相结合。因为难以提高所有内容的可用性，所以本文的目标是提高重要内容的可用性。根据节点内容对可用性的不同需求，本文对内容优先级进行划分，即一个内容很重要，在网络中需要很高的可用性，则其优先级相应很高。
在本文模型中，通过对数据包添加新的TLV字段“priority”来区分内容的优先级，priority值越大，内容优先级就越高。
2.3 缓存替换策略缓存替换决策函数所含的参数如下：
1）内容优先级。
2）节点的请求频率。本文期望在引入内容优先级后对全局平均命中率并不会产生太大影响，因为NDN缓存的本质就是为后续请求提供内容副本从而提高网络性能，包括请求的响应时间、吞吐量和网络负载等，如果仅考虑优先级，则会对全局性能造成影响，一些较为流行的内容可能因为没有被标记为重要内容而被替换，因此，本文引入节点的请求频率，请求频率度量内容在当前节点的CS中被请求的次数，在某种程度上可以反映一个内容是否流行，如果是流行内容，其请求频率会相对较大。
3）内容大小。考虑到移动自组织网络节点缓存容量的限制，本文将内容大小也作为一个衡量指标。
根据以上分析，对于每一个到达CS的内容k而言，都需要计算一个如式（1）所示的函数：
| $ R(k) = P(k) \times \frac{{{c_f}F\left( k \right)}}{{{c_s}S\left( k \right)}} $ | (1) |
其中，P(k)表示内容k的优先级，F(k)表示内容k在当前CS中的请求频率，S(k)表示内容k的大小，cf是F(k)的标准化系数，cs是S(k)的标准化系数。
从式（1）可以看出，R(k)随着F(k)线性增长，即当有很多节点对同一个内容k发起请求时，R(k)可能会变得很大，但是如果在接下来一段时间内没有节点请求内容k，k也会一直被缓存在CS中，因为没有较大的R(j)来替换它。为了解决这一问题，本文在替换策略中考虑内容的生成周期，每次新内容到达后CS会检测缓存中是否有内容过期，如果有，则删除该内容，以腾出缓存空间。
基于内容优先级的缓存替换策略PFC的伪代码如算法1所示，其步骤为：当一个内容k到达CS时，先检查该内容是否已经在缓存中，如果已经在缓存中，则更新R(k)的值；否则，检测缓存空间是否已满，若缓存未满，则缓存该内容，如果缓存已满，则计算R(k)值，并与CS其他内容的R值进行比较，淘汰R值最小的内容，最后，清空过期的内容。
算法1 基于内容优先级的缓存替换策略PFC
1.while incoming data C（k）reach CS do
2.if Cache hit for C（k）then
3.Update R（k）
4.else if CS has enough space for C（k）
5.Cache the data C（k）in CS
6.else if R（k）≤min{R（j），j∈CS}
7.No replacement happens
8.else
9.Find minj {R(j)}
10.Replace data C（k）with C（j）
11.end if
12.Discard the data which out of time
13.end while
3 实验结果与分析本文选取比较常用的缓存策略LRU和FIFO作为对照组，通过模拟仿真来分析基于内容优先级的缓存替换策略的缓存性能。
3.1 实验环境使用ndnSIM仿真平台进行实验，网状拓扑共包含50个节点，每个节点既是内容生产者（Producer）也是内容消费者（Consumer），实验参数设置如表 1所示。不同生产者产生的内容有不同的优先级标记，为了方便分析，本文将内容分为重要内容和普通内容2种，其中，10%是重要内容，其余是普通内容，所有的内容流行度服从Zipf-mandelbrot分布，消费者节点对内容的请求服从泊松分布，请求速率为10 req/s。此外，为了模拟移动网络的情景，在仿真进行到5 min时，通过改变节点的通断关系来改变网络拓扑。
|
下载CSV 表 1 实验环境的参数设置 Table 1 Parameters setting of experimental environment |
缓存命中率是到达缓存节点时命中的请求数与到达缓存节点的请求总数之比。图 2所示为不同缓存替换策略下缓存命中率与缓存大小的关系，从图 2可以看出，随着缓存容量的增加，各策略的内容命中率都提高，原因是缓存容量增加，可以缓存的内容副本数也随之增加，导致内容的命中率提高。
|
Download:
|
| 图 2 平均缓存命中率随缓存容量的变化情况 Fig. 2 The change of average cache hit rate with cache capacity | |
图 3所示为重要内容命中率随缓存容量的变化情况，从图 3可以看出，各策略的重要内容命中率也随缓存容量的增大而提升，且本文内容优先级缓存策略对于重要内容的缓存命中率有显著提高，特别是在缓存容量较小时，缓存命中率较其他2种策略而言提升幅度更大。这是因为缓存大小有限时，内容优先级缓存策略优先保留内容优先级较高的内容，即淘汰相对不重要的内容。随着缓存容量的增加，可以缓存更多的内容副本，内容优先级缓存策略对于重要内容的缓存命中率仍然高于其他缓存替换策略。
|
Download:
|
| 图 3 重要内容缓存命中率随缓存容量的变化情况 Fig. 3 The change of important content cache hit rate with cache capacity | |
图 4所示为重要内容缓存占比随缓存容量的变化情况，从图 4可以看出，在缓存容量较小时，重要内容在缓存中占比最高，此时缓存的都是较为重要且请求较多的内容，随着缓存容量的增加，重要内容缓存占比开始减小。图 4中开始阶段本文策略的重要内容缓存占比达到1是因为缓存较小，而重要内容的数量大于缓存容量，因此本文策略将重要内容全部缓存从而替换不重要的内容。其他策略的重要内容缓存占比基本保持不变，即它们并不区分重要内容与普通内容。
|
Download:
|
| 图 4 重要内容缓存占比随缓存容量的变化情况 Fig. 4 The change of important content cache proportion with cache capacity | |
图 5所示为平均响应跳数随缓存容量的变化情况，从图 5可以看出，缓存可以降低请求的平均响应跳数，随着缓存容量的增加，响应跳数减少，内容请求者可以更快地获取内容，原因是随着用户的不断请求，其感兴趣的内容被缓存在离用户近的节点，响应跳数随之降低。
|
Download:
|
| 图 5 平均响应跳数随缓存容量的变化情况 Fig. 5 The change of average response hops with cache capacity | |
为了验证本文缓存策略PFC在提高内容可用性方面的性能，设计一个简单的包含10个节点的小型拓扑，网络中有2个节点产生重要内容，在仿真进行到3 min时分别不断开、断开1个和2个重要节点与网络的连接，然后计算10 s后的内容命中率，以反映重要内容的可用性。实验结果如图 6所示，其中，100%-topo表示2个节点都不断开，50%-topo表示1个节点断开，0%-topo表示2个节点均断开。从图 6可以看出，在没有节点断开时，3种缓存策略的命中率相差不多，随着重要节点的断开，命中率下降，这是因为内容生产者节点断开连接后，用户需要去向其他潜在内容拥有者请求，原有路由可能请求不到内容，造成命中率下降。但是，本文策略命中率下降幅度比较缓慢，这是因为该策略优先缓存重要内容，在整个网络中重要内容副本更多，所以更容易命中。
|
Download:
|
| 图 6 缓存命中率随拓扑结构的变化情况 Fig. 6 The change of cache hit rate with topology | |
本文提出一种基于内容优先级的缓存替换策略。根据节点内容对可用性的不同需求划分内容优先级，将优先级作为缓存替换的参考因子进行缓存替换决策。实验结果表明，该策略能够提高NDMANET网络的缓存命中率，缩短响应时间，提升网络的抗毁性。本文的内容优先级划分方式较简单，今后将通过更精确的方法，如根据生产者节点之间的博弈以及一些经济指标来决定缓存内容的优先级，从而使本文策略更具可靠性。
| [1] |
AHLGREN B, DANNEWITZ C, IMBRENDA C, et al. A survey of information-centric networking[J]. IEEE Communications Magazine, 2012, 50(7): 26-36. DOI:10.1109/MCOM.2012.6231276 |
| [2] |
ZHANG L X, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Com-munication Review, 2014, 44(3): 66-73. DOI:10.1145/2656877.2656887 |
| [3] |
MEISEL M, PAPPAS V, ZHANG L X.Ad hoc networking via named data[C]//Proceedings of the 5th ACM International Workshop on Mobility in the Evolving Internet Architecture.New York, USA: ACM Press, 2010: 3-8.
|
| [4] |
ALUBADY R, AL-SAMMAN M, HASSAN S, et al.Internet protocol MANET vs named data MANET: a critical evaluation[C]//Proceedings of the 4th International Conference on Internet Applications, Protocols and Services.Washington D.C., USA: IEEE Press, 2015: 159-168.
|
| [5] |
CUI Bo.Research on data forwarding and storage mechanism in named data wireless mobile ad hoc network[D].Hohhot: Inner Mongolia University, 2017.(in Chinese) 崔波. 命名数据无线移动自组织网络中数据转发与存储机制的研究[D]. 呼和浩特: 内蒙古大学, 2017. |
| [6] |
SOURLAS V, ASCIGIL O, PSARAS I, et al. Enhancing information resilience in disruptive information-centric networks[J]. IEEE Transactions on Network and Service Management, 2018, 15(2): 746-760. DOI:10.1109/TNSM.2018.2811944 |
| [7] |
TYSON G, BIGHAM J, BODANESE E.Towards an information-centric delay-tolerant network[C]//Proceedings of 2013 IEEE Conference on Computer Communications Workshops.Washington D.C., USA: IEEE Press, 2013: 156-193.
|
| [8] |
ZHANG Xinming, YAN Long, ZHANG Hui, et al. A concurrent transmission based broadcast scheme for urban VANETs[J]. IEEE Transactions on Mobile Computing, 2019, 18(1): 1-12. |
| [9] |
DIN I U, HASSAN S, KHAN M K, et al. Caching in information-centric networking: strategies, challenges, and future research directions[J]. IEEE Communications Surveys & Tutorials, 2018, 20(2): 1443-1474. |
| [10] |
JACOBSON V, SMETTERS D K, THORNTON J D, et al.Networking named content[C]//Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies.New York, USA: ACM Press, 2009: 1-12.
|
| [11] |
ABDULLAHI I, ARIF S, HASSAN S. Survey on caching approaches in information centric networking[J]. Journal of Network and Computer Applications, 2015, 56: 48-59. DOI:10.1016/j.jnca.2015.06.011 |
| [12] |
LAOUTARIS N, CHE H, STAVRAKAKIS I. The LCD interconnection of LRU caches and its analysis[J]. Performance Evaluation, 2006, 63(7): 609-634. DOI:10.1016/j.peva.2005.05.003 |
| [13] |
SHAILENDRA S, SENGOTTUVELAN S, RATH H K, et al.Performance evaluation of caching policies in NDN-an ICN architecture[C]//Proceedings of 2016 IEEE Region Conference.Washington D.C., USA: IEEE Press, 2016: 1117-1121.
|
| [14] |
IYER S, ROWSTRON A, DRUSCHEL P.Squirrel: a decentralized peer-to-peer Web cache[C]//Proceedings of the 21st Annual Symposium on Principles of Distributed Computing.New York, USA: ACM Press, 2002: 213-222.
|
| [15] |
YIN L Z, CAO G H. Supporting cooperative caching in ad hoc networks[J]. IEEE Transactions on Mobile Computing, 2006, 5(1): 77-89. DOI:10.1109/TMC.2006.15 |
| [16] |
LAL K N, KUMAR A. A cache content replacement scheme for information centric network[J]. Procedia Computer Science, 2016, 89: 73-81. DOI:10.1016/j.procs.2016.06.011 |
| [17] |
ONG M D, CHEN M, TALEB T, et al.FGPC: fine-grained popularity-based caching design for content centric networking[C]//Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems.New York, USA: ACM Press, 2014: 295-302.
|
| [18] |
LI Y Q, YU M J, LI R.A cache replacement strategy based on hierarchical popularity in NDN[C]//Proceedings of 2018 International Conference on Ubiquitous and Future Networks.Washington D.C., USA: IEEE Press, 2018: 159-161.
|
| [19] |
PANIGRAHI B, SHAILENDRA S, RATH H K, et al. Universal caching model and Markov-based cache analysis for information centric networks[J]. Photonic Network Communications, 2015, 30(3): 428-438. DOI:10.1007/s11107-015-0570-7 |
| [20] |
OSTROVSKAYA S, SURNIN O, HUSSAIN R, et al.Towards multi-metric cache replacement policies in vehicular named data networks[C]//Proceedings of 2018 IEEE Annual International Symposium on Personal, Indoor and Mobile Radio Communications.Washington D.C., USA: IEEE Press, 2018: 1-7.
|