软件定义下的CCN缓存算法研究

任乐源 王俊芳 张学敏

摘 要：为了解决内容中心网络（CCN）中存在的缓存问题，在内容中心网络和软件定义网络（SDN）的融合架构下，充分利用控制层全局感知和集中控制的优势，提出了一种软件定义下的CCN缓存决策方法。考虑了中介中心度、内容流行度、节点边缘度和缓存节点存储容量的有限性，引入了控制节点和通信节点的概念，通过控制器缓存决策，使得请求内容在不同的节点进行合理缓存。同时，根据控制节点距离缓存节点和服务器的跳数，找到返回用户请求的最短路径，采用ndnSIM进行仿真实验。结果表明，相比ALWAYS，LCD两种传统缓存决策策略，该方案可以明显提高缓存命中率，降低路径延展率和缓存替换数，达到了提高CCN缓存效率的目的，有利于内容中心网络及未来网络的发展。

关键词：通信网络技术；内容中心网络；软件定义网络；缓存；集中控制

中图分类号：TN9159 文献标志码：A

文章编号：1008-1542（2018）05-0455-07

随着网络用户和通信量的急剧增长，传统网络逐渐暴露出安全性、移动性、可靠性等问题，另外IPv4地址空间不足和路由表的可扩展性问题都制约了网络的发展[1]，网络带宽和网络性能的发展无法跟上用户需求不断增长的脚步[2]。当今互联网已经无法满足未来网络的发展需求，急需一种新的网络体系架构来解决传统网络的弊端。

在未来互联网研究项目中，最引人注目的是内容中心网络[3]（content centric networking，CCN），CCN以内容为中心并在路由节点内置缓存功能，实现了缓存功能的泛在化和透明化[4]。内容中心网络引入唯一的命名作为网络内容标识，实现内容数据和位置、应用、存储以及传输方式的分离，并通过对网络中内容的直接感知和保护，减少了网络中的信息冗余，提高了网络通信的安全性和保密性。

对于CCN缓存网络的研究目前尚处于起步阶段，无论是理论模型、路由机制、优化缓存策略等关键技术，还是它们的应用业务，都有大量的问题亟待研究解决[5]。CCN缓存的泛在化使得网络拓扑结构不再是简单的树型拓扑或线性拓扑，增加了数学建模的难度[6]。另外，节点独立作出缓存决策[7]，没有一个中心节点能对整个网络的缓存作出有效的管理和决策，这样会增加交换节点的负担并降低缓存的命中率和有效性，所以笔者将软件定义网络（software defined networking，SDN）控制与转发解耦的思想应用到CCN中[8]。SDN控制器是整个网络的核心[9]，通过南向接口OpenFlow协议与基础设施层的网络设备进行通信[10]，通过北向接口与应用层的防火墙、拥塞控制等业务进行通信。引入SDN技术后，可以根据SDN控制器掌握的全网资源对缓存决策策略进行优化[11]，将路由决策过程放到控制层面，由控制器给出内容返回时最佳的缓存节点[12]，而交换层面仅需根据下发的命令进行数据的转发[13]。

笔者在SDN和CCN融合的架构下，提出了一种对内容进行集中缓存决策的算法，即选择网络中最合适的节点来缓存相应的内容。该方法将缓存节点分为控制节点和通信节点，先将内容缓存在中介中心度[14]最大的控制節点处，为防止该节点的内容被很快替换掉，控制器通过掌握的全网资源作出缓存决策，将控制节点内容流行度高的内容转移到中介中心度高、节点边缘度大的通信节点上，将控制节点内容流行度低的内容转移到中介中心度低、节点边缘度小的通信节点上，在交换层根据下发的命令进行数据转发的过程中，选择较短的路径，这样的缓存决策策略可以提高缓存命中率，降低路径延展率和缓存替换数，既可以利用SDN逻辑中心化[15]和集中控制的优势，又可以体现CCN在内容获取上的优势。

1 基于SDN的CCN集中控制缓存决策方法

1.1 相关定义

定义1（中介中心度） 由于缓存节点在网络拓扑结构中位置的不同，会导致节点在网络中缓存价值不同，因此需要中介中心度来衡量各个节点的缓存概率和重要程度。若中介中心度高，说明经过该节点的最短路径数目多，则内容在该节点被命中的概率大。用B（Ry）表示节点Ry处的中介中心度，可表示为

1.2 控制节点及通信节点

将兴趣包请求路径中中介中心度最大的点定义为控制节点，针对不同的业务请求，需要确定不同的控制节点，对于同一业务请求，如果在兴趣包经过的节点中没有缓存过该内容并且没有具有控制功能的节点，则需要确定此路径中的控制节点。控制节点除了具有控制功能，还能通过比较其距离通信节点和服务器的跳数，来选择合适的数据包返回路线，若控制节点距离通信节点的跳数小于距离服务器的跳数，则将兴趣包传送至通信节点，这样数据返回用户的路线较短。

由于网络中内容数量巨大，缓存在控制节点的内容会被频繁地替换掉。为了防止这一现象，要将控制节点处的内容转移到内容请求路径中合适的节点处，这个节点为通信节点，根据式（2）和式（3）来确定通信节点。根据控制器作出的缓存决策，将控制节点内容流行度高的内容缓存在中介中心度高、节点边缘度大的通信节点上，将控制节点内容流行度低的内容缓存在中介中心度低、节点边缘度小的通信节点上。

1.3 CCN节点结构

内容中心网络中传输的报文由数据包（data packet）和兴趣包（interest packet）组成。用户终端请求内容时发送兴趣包，兴趣包携带所请求内容的内容名。数据包包含数据命名和被请求内容的内容数据[16]。

内容中心网络中每个节点都具有缓存的功能，CCN节点包含CS（content store，内容存储器）、PIT（pending interest table，待定请求表）和FIB（forwarding information base，转发信息库）。其中，CS代表内容缓存区； FIB为节点提供兴趣包的下一跳转发信息；PIT用于记录兴趣包的来源信息，方便数据包返回时找到返回路径[17]。

1.4 缓存决策流程

在整个缓存过程中，数据层中的交换机实时地对路由信息进行统计，控制层中的控制器收集数据层的缓存信息并作出缓存决策，SDN控制器和CCN节点之间通过OpenFlow协议进行通信，通过流表下发的方式告知CCN节点缓存决策的结果，然后由数据层执行缓存决策后数据的转发。

缓存决策的流程如图1所示，当数据层的交换机接收到兴趣包时，首先对兴趣包中的内容名进行判断，若内容名标记为已记录缓存决策结果，则读取缓存决策结果，若结果中包含自身节点，则缓存该内容，若不包含，则继续传送该兴趣包；若内容名中没有已记录的缓存决策结果，则交换机向控制器发送包含该内容名的缓存决策请求。

假设开始时，请求内容k只缓存在服务器中，路由中没有该内容。当用户3请求内容k时，会沿着R1→R2→R3→R4的路线传递兴趣包，最后在服务器命中；因为是首次请求，服务器会向控制器发送请求决策信息，控制器将缓存决策结果及控制节点的下游节点信息返回给服务器，服务器将该内容标记为已记录，并将缓存结果封装到该内容名中；处理完毕后，将数据包发出，沿原路径返回，节点R4，R3，R2，R1依次读取缓存决策结果，若内容名中包含自身节点，则缓存该内容并读取下游节点信息，然后继续传输，反之则不缓存，继续传送数据包，最终将该请求内容返回给用户3。

假设在这一过程中将内容缓存在中介中心度最大的路由R3中，但是考虑到内容在R3处命中的概率大，并且节点容量远小于内容的数量，R3中的内容很容易被替换，笔者根据下发的缓存结果将内容转移到控制节点附近合适的通信节点中。假设内容转移到R2，R3就会成为控制节点，记录缓存内容的信息。

当用户3再次请求内容k时会沿着路线R1→R2传送兴趣包，当R2收到兴趣包时检测到它的CS中存在该内容，则将数据包沿原路线返回给用户，这样比用户3首次请求时，路径跳数减少了一半；当用户2请求内容k时会沿着路线R14→R6→R5→R3传送兴趣包，当R3收到兴趣包却没有在它的CS中检测到缓存内容时，则要求它的BCP表来判断它是否是控制节点，如果是控制节点，比较R3的BCP表中SOURCE和HOP的值，如果HOP小于SOURCE，則将兴趣包输送给R2，R2读取CS中的数据包，将内容k沿路线R2→R3→R5→R6→R14返回给用户2。

2 仿真实验结果分析

2.1 仿真环境及参数指标

使用C++实现SDN和CCN融合架构的内容传输模型，采用ndnSIM仿真工具完成仿真实验。ndnSIM是NS-3中的一个实现NDN通信模型的模块，与CCNx比较，它具有更清晰和可扩展的内部结构。试验中设置的节点数和内容数远远少于实际数量，更大规模的仿真可以借鉴天地一体化网络，构建安全技术仿真与实验平台来支撑安全测试任务。

为验证本算法可以达到预期效果，选择了CCN算法中具有代表性的ALWAYS和LCD两种算法进行比较，仿真参数的设置如表1所示，在互联网中，内容流量的热度分布遵从Zipf分布，缓存替换策略采用默认的LRU（最近最少使用替换策略）为网页类内容的流行度分布，设置值为0.7，缓存替换算法采用默认的最近最少使用替换策略LRU。

ALWAYS采用处处缓存的方式，将请求内容缓存到沿途传输的所有节点中，使网络内产生了大量的缓存冗余[18]，由于节点缓存容量有限，

会导致频繁发生缓存替换和节点上的内容更新，此算法对缓存空间的利用率低，并且当用户请求量较大时，用户体验不佳。LCD缓存策略是在命中节点的下一跳节点进行缓存，缓存内容沿请求路径逐渐靠近网络边缘，但内容向网络边缘移动的速度比较慢，需要多个访问周期。与ALWAYS相比，此算法减少了冗余副本，但是没有考虑对不同流行度的内容和不同重要度的节点进行区分。

2.2 性能评价指标

1）缓存命中率[19]（CHR） 缓存命中率表示用户请求能够得到响应的概率，其值越高，缓存响应用户请求的概率越大，这样可以提高缓存系统的效率和缓存资源的利用率，降低网络负载。若用n表示用户请求在缓存节点得到响应的次数，N表示用户请求内容的总次数。CHR可表示为

2）路径延展率（PS） 路径延展率与用户获取请求内容的平均跳数有关，其值越低，表示响应用户请求内容所在的节点离用户越近，这样能够有效降低用户访问时延，并能够改善网络负载。若用d表示用户获取内容的平均跳数，[AKd-]表示用户到源服务器的平均跳数。PS可表示为

3）缓存替换数[20] 内容中心网络中缓存节点的缓存容量有限，其值远远小于内容的大小，所以会产生大量的替换操作，节点缓存的内容会不断地更新，频繁的替换操作会导致缓存内容副本在节点的存活时间太短，从而影响缓存命中率，所以缓存替换数越少越有利于缓存命中率的提升。

4）能耗 整个CCN的能耗主要由四部分组成：传输能耗、缓存能耗、计算能耗、通信能耗。

2.3 结果及分析

在实验中设置节点缓存容量分别是10，30，50，70，90，110，130，150，单位为块（chunk），随节点缓存容量的不断增加，观察3种缓存策略的源服务器命中率（见图2）、用户请求平均跳数（见图3）和缓存替换数（见图4）3个指标的变化情况。

如图2所示，纵坐标是内容源服务器命中率，其值越低，表示节点缓存命中率越高，随着节点缓存容量的不断增加，3种缓存算法的缓存命中率都不断提高，而本文算法的缓存命中率明显高于其他2种算法。如图3所示，纵坐标是用户请求平均跳数，其值越低，表示路径延展率越低，随着节点缓存容量的增加，3种缓存算法的路径延展率都不断降低，本文算法的路径延展率最低，可以更有效地降低用户请求时延。ALWAYS算法和LCD算法没有实现节点之间的协同，没有对不同流行度的内容和不同重要度的节点进行区分，而本文算法对传统缓存算法进行了优化和改进，考虑了用户访问体验的因素，因此在缓存命中率和路径延展率上都得到了更好的结果。

分别观察节点R4和重要节点R2节点处的缓存替换数，当节点缓存容量不断增加时，3种缓存策略的缓存替换数都不断减少。由于网络中内容数量远大于节点缓存容量，ALWAYS处缓存会导致每个节点都会有大量的替换操作，LCD算法需要多个访问周期才能将内容移动到边缘节点，所以不能有效降低缓存替换数，本文算法根据内容流行度、节点重要度和节点边缘度选择缓存节点，能够对内容在节点上进行合理的布局，有效地减少内容的替换和更新。在节点R2和R4缓存容量一样的情况下，本文算法的缓存替换数远小于其他2种算法的缓存替换数。

缓存能耗是CCN每个节点提供缓存功能带来的开销，本文算法仅在特定的节点处缓存，所以大大减少了缓存能耗，并且通过减少内容获取的平均跳数和消除网络中重复的内容传输，减少了传输能耗，但是会比传统算法增加计算能耗和通信能耗。

3 结 语

本研究基于传统的网内缓存算法，充分利用了SDN全局感知和集中控制的优势，结合中介中心度、内容流行度和节点边缘度的概念，得到内容的最佳缓存节点。将网络中缓存节点分为控制节点和通信节点，在沿途传送兴趣包的过程中，根据控制节点距离通信节点和服务器的跳数选择合适的数据包返回路线。

目前，常用的CCN缓存算法有ALWAYS，LCD等。在本文实验条件下，相比于ALWAYS算法，本文算法源服务器命中率最多可降低24%，平均跳数最多可减少50%，重要节点的缓存替换数也可以降低到250以下。本研究在提高缓存替换率、减少用户访问时延、降低缓存替换更新等方面，都表现出了更好的缓存性能，但也可能会产生更多的能耗。如何在不影响性能的情况下，将能耗降到最低是下一步优化算法的主要工作内容。SDN与CCN结合的网络架构和软件定义下的CCN缓存算法，是未来网络研究的一个重要方向，对内容中心网络乃至未来网络的发展都具有重要的科学意义。

参考文献/References：

[1] FELDMANN A. Internet clean-slate design： What and why[J]. ACM SIGCOMM Computer Communication Review， 2007， 37（3）： 59-64.

[2] 周鑫.基于內容流行度和节点缓存寿命的内容中心网络缓存技术[D].南京：南京大学，2017.

ZHOU Xin. Popularity and Life-Span Based Cache Scheme for Content-Centric Network [D]. Nanjing： Nanjing University， 2017.

[3] DIRK T， MIKKO S， KAREN S. Arguments for an information-centric internet working architecture[J]. ACM Computer Communication Review， 2010， 40（4）： 26-33.

[4] 崔现东.内容中心网络网内缓存策略研究[D].北京：北京邮电大学，2014.

CUI Xiandong. Research on In-Network Caching Schemes for Content Centric Networking[D]. Beijing： Beijing University of Posts and Telecommunications， 2014.

[5] KOPONEN T， CHAWLA M， CHUN B G， et al. A data-oriented （and beyond） network architecture[J]. Acm Sigcomm Computer Communication Review， 2007， 37（4）： 181-192.

[6] ZHANG G Q， YANG L I， TAO L， et al. Survey of in-network caching techniques in information-centric networks[J]. Journal of Software， 2014， 25（1）： 154-175.

[7] LIU D， DONG M， GU B， et al. Impact of item popularity and chunk popularity in CCN caching management[C]// Network Operations and Management Symposium. Pacific： IEEE Press， 2016： 2-5.

[8] MCKEOMN N， ANDERSON T， BALAKRISHNAN H， et al. OpenFlow： Enabling innovation in campus networks[J]. Acm Sigcomm Computer Communication Review， 2008， 38（2）： 69-74.

[9] GUDE N， KOPONEN T， PETTIT J， et al. NOX： Towards an operating systems for networks[J]. Acm Sigcomm Computer Communication Review， 2008， 38（3）： 105-110.

[10]王宁.基于SDN的内容中心网络架构设计及缓存机制研究[D].北京：北京邮电大学，2015.

WANG Ning. Design and Research in Content Centric Networking Based on SDN[D]. Beijing： Beijing University of Posts and Telecommunications， 2015.

[11]曲樺，李岩松，刘军，等.一种基于SDN 的CCN 集中控制缓存决策方法[J].电信科学学报，2017， 33（5）： 2-7.

QU Hua， LI Yansong， LIU Jun， et al. A method of CCN centralized control cache decision based on SDN[J]. Journal of Telecommunications Science， 2017， 33（5）： 2-7.

[12]CUI Y F， ZHAO M， WU M Q. A centralized control caching strategy based on popularity and betweenness centrality in CCN[C]// Wireless Communication Systems. Poland： IEEE Press， 2016： 286-289.

[13]张国强，李杨，林涛，等.信息中心网络的内置缓存技术研究[J].软件学报，2014，25（1）：154-175.

ZHANG Guoqiang， LI Yang， LIN Tao， et al. Survey of in-network caching techniques in information-centric networks[J]. Software Journal， 2014， 25（1）：154-175.

[14]WEI K C， DILIANG H， IOANNIS P， et al. “Less for more” Caching in The Information-Centric Networks [M]. Berlin： Springer Berlin Heidelberg， 2012.

[15]SUN Q， WANG W， HU Y， et al. SDN-based autonomic CCN traffic management[C]// Globecom Workshop. Austin： IEEE Press， 2015： 183-187.

[16]LIU W， YU S， GAO Y， et al. Caching efficiency of information-centric networking[J]. IET Networks， 2013， 2（2）： 53-62.

[17]BARI M F， CHOWDHURY S， AHMED R， et al. A survey of naming and routing in information-centric networks[J]. IEEE Communication， 2012， 50（12）： 44-53.

[18]刘涛.内容中心网络访问时延优化技术研究[D].郑州：解放军信息工程大学，2013.

LIU Tao. Research on Optimization of Access Delay in Content Centric Networks[D]. Zhengzhou： The PLA Information Engineering University， 2013.

[19]FANG C， HUANG T， LIU J， et al. Fast convergence caching replacement algorithm based on dynamic classification for content-centric networks[J]. The Journal of China Universities of Posts and Telecommunications， 2013， 20（5）： 45-50.

[20]CUI X D， HUANG T， LIU J， et al. Design of in-network caching scheme in CCN based on grey relational analysis[J]. The Journal of China Universities of Posts and Telecommunications， 2014， 21（2）： 1-8.