命名数据网络中缓存优化策略的研究*

李庆敏 高全力 王西汉 胡发丽

（1.西安工程大学计算机科学学院 西安 710048）（2.新型网络智能信息服务国家地方联合工程中心 西安 710048）

1 引言

根据思科（Cisco）公布的思科视觉网络指数（VNI）［1］预测，2022年将会创造出比互联网诞生至2016年的总流量更多的网络流量，世界范围内的网民数量将会达到48亿，比2017年整整多了14亿。海量的数据流量不仅催生出大量的新型应用，还造成传统的TCP/IP网络出现IP地址耗竭等问题。在此背景下，研究人员提出了信息中心网络［2～3］（Information-Centric Networking，ICN）。

ICN以内容为核心不同于TCP/IP网络以IP地址为核心，这项特性使得ICN的实施部署成为了如今的主流。其中，命名数据网络［4］（Named Data Networking，NDN）是信息中心网络的一种新的演化。NDN网络使用的是名称寻址和路由节点缓存功能。与基于TCP/IP的网络相比，NDN对于网络中的信息命名使用的是名称前缀而不是IP前缀，每条内容都有一个唯一的名称。用户通过向NDN网络发送内容名称唯一标识的兴趣包来获取内容，每个中间路由节点都能实现缓存功能，可以独立地执行缓存策略。因此，从源服务器端返回的携带请求内容的数据包可以缓存在途径的路由节点上。如果下一次有用户发送相同的内容请求，则该路由节点就可以立即做出响应回传数据包，而无需再将请求向源服务器转发。因此，合理的缓存策略是影响NDN网络服务效率的关键因素，也是当前的研究热点之一。

缓存策略包括路由节点判断是否将到达的数据包缓存的缓存放置策略和在路由节点中的缓存内容的更新与清除的缓存替换策略。NDN网络常见的放置策略有LCE［5］、LCD［6］、Prob［7］等。其中，LCE（Leave Copy Everywhere）策略对所有数据包全网节点缓存。LCD（Leave Copy Down）策略只将数据包缓存到发生缓存命中的中间路由节点的下游节点。Prob（Copy with Probability）策略中所有的路由节点都使用概率P缓存数据包。这些策略计算复杂度低，易于执行，但存在两个问题使得NDN网络性能受限：1）数据冗余，大量具有相同内容的数据包在回溯路径上多次重复缓存，浪费了节点的有限缓存容量；2）内容无差别处理，所有的内容都缓存在路径上所有节点内，缺乏针对不同类别的内容提供差异化的缓存服务。而且以上策略主要从单一因素考虑缓存，无法做到客观的、正确的缓存决策。为了解决此类问题，国内外学者们提出了考虑多因素的缓存放置策略。

ProbCache策略［8］认为缓存取决于节点与用户的距离和节点的剩余缓存容量。因此越靠近用户或剩余容量越多的节点越容易缓存。但是边缘路由节点之间会出现缓存竞争，导致高替换率。文献［9～10］提出在具有最高中心性的路由节点上缓存内容，但是这将增加路由器的负载并导致缓存替换的频率增大。文献［11～12］同时考虑了内容受欢迎程度和路由节点级别。Betw策略［13］提出将介数概念用于一个复杂的网络环境，将数据包缓存在回溯路径上具有最大介数的路由节点中，减少了网络中的缓存冗余，但也会导致路由节点出现高替换率的问题。以上综合考虑多因素的缓存放置策略各有优缺点，虽然减少了缓存冗余但还存在高替换率和对所有内容提供无差别服务的问题。

考虑到上述问题，受IP网络中的IntServ模型启发，对NDN网络中的请求内容正确合理分类，同时考虑路由节点的重要度，不同重要度的节点缓存不同类别的内容，更符合NDN网络提出的初衷和未来的发展场景。因此本文提出一种基于节点重要度和内容类别的缓存放置策略（Cache Placement Strategy Based on Node Importance and Content Category，NICC）。该策略根据不同服务的QoS需求，将命名数据网络中的内容划分为不同的类别，且提供不同的缓存判决条件。同时考虑NDN网络中的路由节点的重要度，节点重要度的度量为介数，介数越大则有更多的内容转发路径要经过此路由节点，然后在节点重要度高的路由节点优先考虑处理高优先级和高QoS需求的缓存。实验结果显示，相较于NDN网络中现有的缓存放置策略，NICC策略在平均缓存命中率、平均请求时延、服务器命中率方面有较大的改善。

2 NICC缓存放置策略

NICC策略整体工作流程如图1所示，其设计思想是在请求的路径上，节点重要度是做缓存决策的重要判决条件之一。当源服务器返回数据包时，在数据包相应字段做类别标记，该类别标记也是缓存决策的重要判决条件之一。数据包还需统计沿途经过的路由节点跳数总和视为请求代价。路由节点对请求缓存的数据包，先依据数据包携带的类别标识，判断是否有必要缓存，如果不需要缓存，则依据转发策略直接转发；否则将进一步查看类别标识，当该节点的节点重要度匹配内容类别时，节点根据数据包的内容类别标记、节点重要度和请求代价三个指标数值计算缓存概率，最后依据此缓存概率进行数据包缓存的判定。

图1 NICC策略整体工作流程

2.1 节点重要度

文献［14］中提出，可以使用介数来表达一个节点的重要性。因此，本文选取了介数中心性［15］来度量节点的重要性，介数B(νi)由式（1）确定：

本文模拟的网络拓扑模型是由无向图G=（V，E）来描述的，其中集合V=｛v1，v2，v3，…，vn｝代表n个网络节点，集合E=｛e1，e2，e3，…，em｝代表m组网络路径，节点x和y是不同于节点vi的另外两个节点，ηx，y为从节点x至y的最短路径的总和，ηx，y（vi）为从节点x至节点y的最短路径上经过节点vi的路径数目。本文统计最短路径使用Dijkstra算法［16］。为了消除实验外不相关因素的影响，本文采用的介数均为离线计算，介数实验开始前已计算完毕并存入各自对应的路由节点中。

2.2 内容类别定义

根据内容的共享程度、时延需求、带宽消耗等特点，将NDN网络中的内容分为4个类别：无需缓存类（No Cache，NC）、尽力而为类（Do Best，DB）、质量保证类（Quality Assurance，QA）、可控负载类（Controllable Load，CL），如图2所示。对于NC类，例如即时通信、在线游戏、邮件等，该类内容时效性强，过期快，与其他用户的共享程度低，中间路由节点无需浪费有限的缓存资源对其缓存；对于QA类，例如游戏直播、赛事直播、网络电视等，该类内容后续可能会被其他用户重复请求，且请求时延要求较高，将其优先考虑缓存在节点重要度最高，即介数最大的核心路由节点上能更好地提供低延时服务，且不会频繁的使用带宽资源；对于CL类，例如离线下载资源，包括音频、视频、图片等，该类内容占用空间较大，对时延的要求低于QA类，且对带宽资源要求大，遂将此类内容优先考虑缓存在节点重要度小于QA类的的路由节点上，既能避免占用解决时延要求高的核心路由节点，也能避免网络带宽的无端占用；对于DB类，例如网页、共享文件、低优先级内容等，该类内容占用空间小，带宽要求较低，可容忍延迟时间较长，将其优先考虑缓存在节点重要度均小于QA类和CL类的路由节点上。

图2 NICC策略中NDN网络的内容类别

2.3 包格式拓展

为了支持数据传输过程中路由节点能根据内容的类别提供不同的缓存放置服务，在保持了NDN网络数据包的原始数据结构的前提下，拓展了其格式。如图3所示，数据包增加ContentCategory和RequestCost字段，其中ContentCategory用于标识数据包携带的内容类别，包括NC、DB、QA、CL4种内容；RequestCost记录的是数据包沿着回溯路径传输到某一路由节点距离源服务器端的经过其他路由节点的跳数，即请求代价。

图3 NICC策略拓展的数据包格式

2.4 放置描述

为了方便内容类别和路由节点的匹配，先将上文提到的介数B(νi)进行归一化处理：

在NICC策略中，当数据包沿请求路径传输时，沿途路由节点先判断数据包的内容类别，即ContentCategory字段的标识，按照以下4种方法计算数据包的缓存概率：

1）若ContentCategory=NC，则路由节点不进行缓存决策，并对数据包按照规定的转发策略进行处理。

2）若ContentCategory=QA，且节点的介数nb（vi）大于0.6，则在该节点计算缓存概率P，并依据概率P进行缓存决策。

3）若ContentCategory=CL，且节点的介数nb（vi）大于0.3且小于或等于0.6，则在该节点计算缓存概率P，并依据概率P进行缓存决策。

4）若ContentCategory=DB，且节点的介数nb（vi）小于或等于0.3且大于0，则在该节点计算缓存概率P，并依据概率P进行缓存决策。

在NICC策略中，每个内容i在路由节点j上的缓存概率Pi，j计算公式为

式中，各参数含义与取值如下：

1）nb（j）表示NDN网络中路由节点的节点重要度，用介数值表示。文中所用的介数都是离线运算，在实验开始前已计算完毕并存入各自对应的路由节点中。

2）cci是内容i对应的内容权值，不同内容类别对应不同的权值，路由节点查询数据包的Content-Category字段获得。权值的设置参考Cisco的VNI报告中对于未来几年的IP网络流量预测，视频流量占IP总流量的82%［1］。

3）rci，j表示内容i在路由节点j的请求代价，即数据包回溯路径上经过的其他路由节点的总跳数。为了便于计算比较，对请求代价进行归一化处理后通过式（1）～（4）确定rci，j：

式中：Hj为数据包携带的RequestCost字段的值；Tcount n为网络拓扑中路由节点的总数，设计实验网络拓扑时给定，仿真开始前存入中间路由节点中。

4）α、β、γ是各项的权重因子，三者之和为1。

缓存内容类别权值如图4所示。

图4 NICC策略内容类别权值表

NICC策略伪代码如下：

Algorithm NICC

Init Data package：Tagging ContentCategory，Request-Cost=0

1：Node vi receive Data package j

2：if ContentCategory=NC then

3：Forword this data package to next node

4：RequestCost++

5：else

6：if nb（vi）＞0.6&&ContentCategory=QA then

7： Calcalate Pj，i=α×nb（vi）+β×ccj+γ×rcj，i

8： Cache this data package according to Pj，i

9：end if

10：if 0.3＜nb（vi）＜=0.6&&ContentCategory=CL then

11： Calcalate Pj，i=α×nb（vi）+β×ccj+γ×rcj，i

12： Cache this data package according to Pj，i

13：end if

14：if 0.0＜nb（vi）＜=0.3&&ContentCategory=DB then

15： Calcalate Pj，i=α×nb（vi）+β×ccj+γ×rcj，i

16： Cache this data package according to Pj，i

17：end if

18：end if

2.5 数据包缓存放置流程

如图5所示，当数据包到达路由节点时，执行4个步骤。

图5 包转发和缓存放置流程

步骤1：路由节点查询数据包中的ContentCategory字段的内容类别信息，如果是ContentCategory=NC，则依据既定的转发策略来转发数据包，且数据包中的RequestCost字段的值加1；如果是除了NC之外的其他内容类别信息，则执行步骤2；

步骤2：根据该路由节点的节点重要度，查询数据包中的ContentCategory字段的内容类别信息，判断节点重要度是否与数据包的内容类别相对应，如果不对应，则依据既定的转发策略转发数据包，且数据包中的RequestCost字段的值加1；如果相对应，则执行步骤3；

步骤3：结合该节点的节点重要度、数据包的内容类别的权值和数据包的请求代价三方面的信息根据算式计算缓存概率P，执行步骤4；

步骤4：根据缓存概缓存数据包。

3 实验仿真和结果分析

为了验证NICC缓存放置策略在NDN网络中的实际部署效果和效率，在基于NS-3［17］的网络仿真平台ndnSIM［18～19］上对NICC机制进行模拟实验，选取NDN网络中的LCE、LCD、Betw、Probability缓存放置策略作为实验对比，设置Probability策略的缓存概率为0.7。

3.1 仿真环境与参数配置

所有仿真作业均在本地计算机上进行，操作系统 及 版 本 为Ubuntu18.04.64-bit；CPU为Intel（R）Core（TM）i7-9700K CPU@3.60GHz；实验平台为ndnSIM，版本控制在2.7；实验分配内存为10 GB，硬盘100GB，处理器数量为8个。

实验的网络拓扑采用文献［20］提出的网络拓扑模型，该模型能反映出网络的真正特性，包含30个节点，37条链路，该模型如图6所示。

图6 NICC策略仿真拓扑图

假设该拓扑中包含13个用户，13个路由节点，4个源服务器，分别处理4种不同类别的数据包。为了模拟不同的内容类别的业务请求，分别设置NC类、DB类、CL类、QA类对应的内容前缀名为“qqmail.com”“youku.com”“dance.com”“huyatv.com”，后缀为随机数。在用户端，兴趣包请求产生的平均速率遵循10个/s的泊松分布。在源服务器端，设置类别为NC的内容产生服从均匀分布，均匀分布的特点使得NC类别的内容很少出现重复的情况；类别为QA、CL、DB的内容产生服从Zipf分布，Zipf参数取值为0.8。每个类别数据包的大小为1024B，总数为1000个，内容序号以1～1000排序。路由节点的缓存空间容量相同，可容纳数据包数量取值范围为10个～100个，缓存伊始不包含任何内容。实验预设的缓存替换策略为LRU。在转发策略选择上，采用NDN默认的转发策略，即最佳路由策略BestRoute。在NICC策略缓存概率P的计算公式中，α值为0.5，β值为0.3，γ值为0.2。其他设置：链路带宽为100 Mbis/s，链路时延为10ms，仿真时长为120s。

3.2 性能评价指标

1）平均缓存命中率Hr：平均缓存命中率是指在实验时间内中间路由节点命中的兴趣包数与各用户发出的请求兴趣包的总数的比值，其能反映路由节点减少源服务器的工作量［21］。如：

式中：N表示用户发送的请求兴趣包的总数，hi表示用户请求兴趣包在路由节点vi得到响应的次数［20］。

2）平均请求时延：平均请求时延是指用户发出请求兴趣包到接收响应数据包的时间，单位为ms，该值越大，用户得到反馈越慢，平均请求时延可以用来衡量用户体验好坏［21］。

3）服务器命中率：服务器命中率定义为网络内的请求数量在源服务器端命中的数量占请求总数量的比值，该值越大，说明大量请求在兴趣包传输路径的路由节点中没能被满足，需要到源服务器请求，增大了源服务器的工作量。当该值过大时，可能会导致网络延迟。

3.3 实验结果分析

如图7是NICC、Probability、LCE、LCD和Betw五种缓存放置策略，用户的平均缓存命中率与缓存容量相关性实验结果曲线图。可以看出，五种不同的缓存放置策略，其平均缓存命中率会随路由节点的缓存容量的增加而增加，且NICC策略远远优于NDN网络默认的缓存放置策略LCE。当缓存容量为10时，LCE策略具有最低的平均缓存命中率，NICC策略较之提高了3.2%的命中率。当缓存容量为100时，NICC策略较Probability、LCE、LCD、Betw四种策略分别提高了2.9%、4.1%、15.1%、2.7%。NICC策略的平均缓存命中率增幅达2.5倍。NICC策略在不同节点重要度的路由节点考虑处理不同优先级和不同QoS需求的内容，避免了个别节点的高替换率，因此可以有效地增加缓存资源的利用率，并能有效地提高缓存的平均命中。

图7 平均缓存命中率与缓存容量相关性实验结果

图8是NICC、Probability、LCE、LCD和Betw五种缓存放置策略，用户平均请求时延与路由节点的缓存容量相关性实验结果曲线图。从图中可以看出，当路由节点的缓存容量增加时，五种缓存放置策略的平均请求时延都在减小。LCE策略在节点缓存容量最小时拥有最大的平均请求时延。当缓存容量小于40时，LCD策略略优，但是随着缓存容量的增大，NICC策略表现逐渐优于LCD策略和其他三种缓存放置策略。整体来看NICC策略有更好的性能。

图8 平均请求时延与缓存容量相关性实验结果

图9是NICC、Probability、LCE、LCD和Betw五种缓存放置策略，服务器命中率与路由节点的缓存容量相关性实验结果曲线图。

从图9可以看出，随着路由节点的缓存容量增加，五种策略下服务器命中率逐渐降低，因为有更多的请求被中间路由节点满足，所以源服务器收到的请求逐渐减少，即服务器命中率逐渐降低。在缓存容量最大时，对比NICC、Probability、LCE、LCD、Betw，前者相比于后四者，服务器命中率分别降低了近3.5%、4.3%、15.5%、3.4%，其中NICC策略较LCE策略的降幅最大。整体来看NICC策略在降低服务器命中率方面具有更好的表现。

图9 服务器命中率与缓存容量相关性实验结果

4 结语

为了提高NDN网络中缓存的命中率，降低平均请求时延和服务器命中率，本文提出了基于节点重要度和内容类别的缓存放置策略NICC。该策略将优先级高、QoS高的内容和优先级低、QoS低的内容区分对待，结合节点重要度的概念，提供节点不同的缓存判决条件。NICC策略充分利用了缓存资源，以满足不同内容缓存的需要。通过仿真实验，发现NICC策略在平均缓存命中率、平均请求时延等方面都比NDN网络中常见的Probability、LCE、LCD、Betw四种放置策略更好。

下一步的研究将考虑更加细化的内容分类方法，使之能够更好地适应网络内容多样化的趋势。另外将考虑在不同的网络拓扑结构中进行实验，以符合网络复杂多样的发展趋势。