基于ICN的未来媒体网络缓存放置策略

许 朝 谢人超,2 张亨洋 黄 韬,2 刘 江,2 杨 磊

1 北京邮电大学 网络与交换国家重点实验室 北京 100876

2 北京未来网络科技高精尖创新中心 北京 100124

3 中央电视台 北京 100020

引言

经过半个多世纪的发展，互联网已经成为当今社会发展与信息生活的重要基础设施，视频、音乐、图片等媒体内容的获取和分发成为当今互联网的主要模式。然而，随着全球数字媒体的深刻变革，媒体数据以惊人的速度快速增长，Cisco公司的统计预测数据表明，在过去五年当中，全球IP流量增长超过了4倍，并且在接下来的5年当中，全球IP流量还将会增加2倍。在2014年至2019年期间，全球的IP流量将以23%的年均复合增长率快速增长；到2019年，视频流量将占到互联网流量的80%[1]。网络流量的增长速度，特别是视频流量的增长远远超过了摩尔定律和路由性能提升的速度，现有的传输网络已经无法满足庞大媒体数据的高效传输。同时，大量新的业务形态与产业发展模式随着网络媒体深度融合如雨后春笋般涌起，更使得传统服务模式和产品面临严峻考验。

随着移动接入、普适计算、分布式信息处理、海量流媒体等新应用的发展，导致服务器负载过重，难以及时响应用户的请求。同时，受网络带宽和传输时延的限制，用户体验也受到一定程度的影响，传统TCP/IP体系结构的计算机网络性能已经开始趋于极限，成为阻碍当今网络中应用层发展的主要因素[2]。虽然“改良”式的发展解决了当今网络存在的大量问题，对网络性能的提高也起到很大作用，但其本质只是对网络结构“修补式”的循环，使网络结构变得越来越复杂，并同时带来一些新的问题[3]。在这种情况下，人们试图提出一种全新的网络体系结构来代替TCP/IP结构，在提出的各种未来网络体系结构方案中[4-10]，信息中心网络(Information-Centric Networking,ICN)成为当今研究的一个热点。

ICN是以信息为中心的网络概念[11]，让信息成为网络的发起者和主导者。相比传统网络，数据位置对于ICN网络而言已不再重要，用户需要关注的只是所要获取内容本身，而不再是网络中的终端和所要获取内容的具体位置；因此，在视频等媒体数据业务爆炸式增长的背景下，本文结合奇异值分解算法(Singular Value Decomposition,SVD)算法，提出了基于ICN网络的未来媒体网络缓存放置算法，旨在通过提高层次节点间的协作来减少互联网服务提供商之间的跨域传输，减小网络传输开销，通过降低网络中数据的传输时延和提高网络中的数据请求响应速率来优化用户体验。为深入分析ICN网络缓存放置算法，本文从较为成熟的NDN网络出发，对网络缓存放置算法进行仿真和分析。

本文后续章节主要包括以下内容。1)主要介绍ICN缓存放置策略。2)主要介绍基于ICN的未来媒体网络缓存放置策略的原理以及其与传统IP网络相比体现出的优势。3)将对NDN中CS结构进行简单修改，利用ndnSIM[12]对基于ICN的未来媒体网络缓存放置策略进行仿真和分析。4)将对仿真结果和基于ICN的未来媒体网络缓存放置策略做简单总结。

1 缓存放置策略

和传统的P2P、Web缓存相比，ICN网络缓存呈现出新的特征，这些新特征主要体现在缓存透明化、缓存泛在化和缓存细粒度化[13]。ICN缓存放置问题主要研究在ICN缓存大规模和动态自生长的背景下，各节点如何筛选缓存内容，优化性能指标，提高缓存鲁棒性等问题，主要包括缓存替换策略和缓存决定策略。缓存放置策略的优劣直接决定了网络的性能优劣，优化的缓存放置策略可以大大降低网络平均负载，降低网络运营成本并提高用户体验。不止对ICN网络，网络缓存放置问题的研究对于云网络、服务中心网络等都具有普适意义。

1.1 缓存替换策略

缓存替换策略主要研究在缓存空间已满的情况下将哪个内容替换出去的问题。目前，缓存替换策略主要有LRU(Least Recently Used)、LFU(Leave Frequently Used)、TTL(Time To Leave)和RAD(Random Replace Policy)。

LRU是根据内容到达的时间，将最新到达的内容缓存，替换最下面的内容，这种方法目前使用最多，但脱离于先验的流行性。LFU是缓存新到达的内容，将最不流行的内容替换掉。TTL是在内容到达时设定一个缓存时间，类似于生存时长，时间一到便替换内容。RAN是随机缓存替换，其优点是不需要查找现有缓存中是否已经存在该内容。

缓存替换策略在传统的Web缓存中已经得到广泛研究，详细内容可参考文献[14]。但ICN中的缓存要求线速执行，因此缓存替换策略应尽量简单。从整个网络研究内容来看，缓存替换算法并不是ICN研究的重点，ICN对缓存替换算法简单性的要求胜于缓存替换算法之于缓存系统性能提升(如命中率)的要求[15]。文献[16,17]的研究表明，在ICN中采用简单的随机替换算法基本上就能达到LRU替换算法的性能；因此，本文重点研究缓存放置策略中的缓存决定策略。

1.2 缓存决定策略

缓存决定策略主要研究在某个节点是否缓存某个内容。在集中式的管理架构中，集中管理节点可以通过全局信息来计算每个内容应该存放在哪个节点；而在分布式架构中，节点通过自身的信息来判断是否缓存内容。鉴于NDN网络分布式架构，本文主要研究分布式节点的缓存决定策略。

依据协同决策点的不同，分布式缓存策略又分为节点之间合作与不合作两种方式。其中不合作方式主要包括都缓存(Leave Copy Everywhere, LCE)和下一跳缓存(Leave Copy Down, LCD)[18]。其中，LCE是NDN默认的缓存决定策略，具体方法是在所经过路径的每个节点都缓存内容，其缺点是导致网络中产生大量的内容冗余。LCD则是只在命中节点的下一节点缓存内容，这使得内容流行度高的内容需要请求多次才能到达边缘节点，数据响应速率不高。

合作缓存决定策略主要是下移一跳缓存(Move Copy Down, MCD)[18]，MCD类似于LCD，也是在命中节点的下一跳缓存内容，主要区别是MCD需要删除内容命中节点的缓存(源服务器除外)。MCD存在的主要问题是，当请求用户来自不同的边缘网络时，会出现内容缓存节点的摇摆，增加网络开销。

结合上述三种决定策略的优缺点，我们可以从以下两方面出发，提高缓存的整体效用。一方面，可以在边缘缓存节点缓存流行度较高的内容，从而减小用户下载内容的平均时延和提高网络中资源的利用率。另一方面，可以提高整个网络缓存系统的缓存多样性，特别是同一自治系统内容路由器所缓存的对象的多样性，尽量使得用户请求由自治系统内的缓存节点予以满足，从而降低域间操作和域间流量[15]。

为更好地适应视频等媒体业务对于网络缓存机制的要求，本文从缓存决定策略的角度，结合SVD算法，提出基于ICN网络的未来媒体网络缓存放置算法。

2 基于ICN的未来媒体网络缓存放置策略

在传统IP网络下，用户获取内容需要从特定的主机获取，而在视频流量占据互联网大部分流量的情况下，这一机制必然造成相关链路、特别是靠近内容源的链路的堵塞。同时，由于处理时延、链路带宽等问题，同一主机上的内容请求也会相互影响，造成网络利用率下降，浪费网络资源。而ICN网络将数据与位置相分离，内容数据分布在整个网络当中，而非特定主机。当用户发起数据请求之后，在网络中查找数据，一方面减轻了内容源附近链路的负荷，另一方面对于合理利用带宽、提高网络利用率都具有重要意义。

ICN虽然解决了数据与位置绑定所带来的问题，但当数据不在本地网络中时，就需要进行域间操作，这必然引起较大的时延，对用户体验造成影响。为解决这一问题，本文结合SVD算法设计基于ICN的未来媒体网络缓存放置算法。该算法通过判断本地网络请求数据与其他网络数据的相似性来决定将缓存在本地网络中的内容。

这里的相似性概念是从用户的角度来看的，对于计算机而言，它只能进行计算。为了让计算机能够计算出网络中内容的相似性，可以将网络中的各个内容在不同网络中的请求次数定义为一个M行N列的矩阵，同一内容在不同网络的请求次数构成了一个M维向量。有了这些多维向量之后就可以利用式(1)，通过余弦相似度来判断内容之间的相似度，其中符号“g” 表示向量间的点积，“||”表示向量的欧氏长度，即向量的模。由定义可以看出，相似度介于0到1之间，越接近1表示相似度越高。

余弦相似度判断精度较高，但当N个内容两两之间的进行比较时，其复杂度为O(N2·M)，显然不适用于大规模数据的计算；因此，我们可以先利用SVD算法对之前的矩阵进行粗略处理，然后利用余弦相似性进行精确判断。

SVD算法的数学基础为，对于任何行数大于或等于列数的M×N矩阵A，均可分解为M×N的列正交矩阵U、元素大于或等于零的N×N的对角矩阵∑和N×N的正交矩阵V的转置的乘积，具体可表示为：

其中矩阵U的列称为A的左奇异向量，矩阵V的列称为A的右奇异向量，∑称为A的奇异值标准型，∑的对角元素被称为矩阵A的奇异值矩阵。其中，∑的每个对角元素非负，而且依次减小，在线性空间里，每个向量代表一个方向，所以特征值是代表该矩阵向着该特征值对应的特征向量的方向的变化权重，因此，可以取∑对角线上前k个元素为新的对角矩阵∑2，相应地，取U的前k列为U2，VT的前k行为VT2，A可近似表示为：

当k越大时，式(3)右边与左边越接近。

虽然SVD算法的复杂度与余弦相似度算法属于一个量级，但由于网络中大量低流行度内容的存在，可以利用矩阵的稀疏性大大缩短计算时间。在之后进行余弦相似度判断时，因为去除大部分流行度较低的内容，复杂度也将远小于O(N2·M)。两种方法的先后使用，充分利用二者的优势，既节省了计算时间，又获得了较高的精确度。

基于ICN的未来媒体网络可以采用IP与NDN混合网络结构，核心网保持传统的IP网络架构，为边缘网络提供服务，边缘网络则采用NDN，作为研究ICN网络的具体网络。继承IP协议对于第二层协议的宽松要求这一优点，NDN可以实施在任何的底层协议之上，甚至可以架构在IP层之上，保证了NDN网络对传统IP网络的兼容性。

NDN中提出三种重要的数据结构用来实现路由转发，这三者分别为待处理请求表(Pending Interest Table，PIT)、转发信息库(Forwarding Information Base，FIB)和内容存储库(Content Store，CS)。其中，PIT记录未响应兴趣包的内容名及其到达接口，FIB记录当前节点到达内容提供节点的下一跳接口，CS保存路由节点的缓存内容。

NDN网络中的通信由请求方(Consumer)驱动[12]，请求方请求数据时，首先广播兴趣包，当路由节点收到兴趣包后，先对内容名进行最大匹配查询，再依据查询结果进行操作，兴趣包一旦到达存储所需数据的节点时，就会将相应的数据包发送到请求者。我们以NDN已有数据结构为基础，在CS中加入新的条目“Count”，用来标记每个数据包的请求次数。Count初始化为0，每当返回一次数据，Count值加1，CS结构变为图1。

图1 加入Count条目的CS结构

通过CS统计每个NDN边缘网络中每个内容的请求次数构成Interest请求矩阵A，结构如表1所示。通过分解得到奇异向量VT，VT每行代表不同的特征，每列代表不同的数据对象，每个列向量表示每个数据对象对于各个特征所占的权重。

表1 Interest请求矩阵

根据这个结果将各个边缘网络请求数据中与本网络已缓存数据相似性度最高的内容缓存在本网络中，当用户请求该数据时，即可快速得到响应，而不需要进行跨域操作，同时，也提高了缓存命中率，减少了网络开销。

3 仿真结果

本次仿真通过ndnSIM[12]模拟3个NDN网络和核心网。每个NDN网络包括3个user节点和1个p节点，其中user节点作为请求节点，发出数据请求。三个网络通过Rtr节点实现通信并与IP核心网相连接。IP核心网中包括3个p节点。p缓存有数据包，用来响应来自本网络或其它他网络相应的数据请求。仿真拓扑如图2所示。

图2 仿真拓扑

本次仿真使用Packet-level trace helpers中的ndn::L3RateTracer获得每个节点转发的字节数和转发包的个数等信息。表1列出了10s时间内每个网络对各个内容发出的Interest包的个数。对Interest请求矩阵进行SVD分解后得到如表2所示的VT矩阵，取k=2，以VT第一行为横坐标，第二行为纵坐标，得到图3所示结果。

表2 SVD分解所得VT矩阵

图3 SVD仿真结果

利用余弦相似性可以判断p1与p5相似度最高，与p2、p3相似度最高的均为p6。根据该结果，每个边缘NDN网络可以选择缓存与本网络内容相似度最高的内容到本地p节点中。仿真结果给出了使用不同缓存决定策略时，3个NDN边缘网络中请求响应包的个数和请求命中率结果。图4表明，在相同时间内，请求确定数量的相同内容，基于SVD算法的ICN缓存决定策略得到的数据请求响应明显多于使用传统的LCE、LCD和MCD策略得到的数据请求响应，即降低了请求响应时间。图5表明，基于SVD算法的ICN缓存决定策略对提高缓存命中率有明显改善，LCE则优于MCD和LCD。其中，MCD与LCD命中率相同，其原因是二者的区别只是在于是否删除命中节点缓存，而二者都会在命中节点下一跳缓存内容，因此，不会影响到命中率。

图4 请求节点响应数据

图5 数据命中率

4 结束语

本文主要利用SVD算法，通过余弦相似度来分析不同网络中请求内容的相似性来决定每个网络的缓存内容，从而提高数据响应速率和网络缓存命中率。

由仿真结果可以看出，基于SVD算法的缓存策略在响应时间和缓存命中率方面要明显优于传统LCE、MCD和LCD策略。由于频率较高的请求内容都能在本网络中得到响应，即不需要经过网络之间的路由再去寻找数据源。所以基于SVD算法的缓存策略也起到了缩短平均请求响应时间的效果，减少了互联网服务提供商之间的跨域传输和传输开销，进而降低网络中数据的传输时延。对提高网络中的数据请求响应速率和优化用户体验都具有重要意义。

参考文献

[1] Cisco Visual Networking Index: Forecast and Methodology: 2014–2019[EB/OL].[2016-03-12]http://www.cisco.com/c/en/us/solutions/collateral/serviceprovider/ip-ngn-ip-next-generation-network/white_paper_c11-481360.html

[2] Feldmann A. Internet Clean-Slate Design:What and Why?[J].Computer Communication Review,2007,37(3):59-64

[3] 吴超,张尧学,周悦芝,等.信息中心网络发展研究综述[J]. 计算机学报,2015,03:455-471

[4] Dannewitz C, Pentikousis K, Rembarz R. Scenarios and research issues for a network of information[EB/OL].[2016-01-06].https://www.researchgate.net/publication/228941601_Scenarios_and_Research_Issues_for_a_Network_of_Information

[5] Ahlgren B,D’Ambrosio M,Dannewitz C,et al.Design considerations for a network of information[C]//Proceedings of First International Workshop on Re-Architecting the Internet. Madrid: [s. n.], 2008

[6] Ohlman B, Ahlgren B, Brunner M. First NetInf architecture description, FP7-ICT-2007-1-216041-4WARD/D-6.1[R].2009

[7] Jacobson V, Smetters D K, Thornton J D. Networking named content[A].New York,NY,USA:ACM,2009.1-12

[8] L. Zhang et al. Named data networking (ndn) project[R].Technical Report NDN-0001, October 2010

[9] Lagutin D, Visala K, Tarkoma S. Publish/Subscribe for Internet:PSIRP Perspective[C]. Towards the Future Internet - Emerging Trends from European Research,2010:77-82

[10] 张行功,牛童,郭宗明.未来网络之内容中心网络的挑战和应用[J].电信科学, 2013, 29(8):24-31

[11] Nelson T. Literary machines: the report on, and of,project Xanadu concerning word processing, electronic publishing, hypertext, thinkertoys, tomorrow' s intellectual revolution, and certain other topics including knowledge, education and freedom[M].Sausalito,California: Mindful Press,1981

[12] Afanasyev A, Moiseenko I, Zhang L, ndnSIM: NDN simulator for NS-3[EB/OL].[2016-01-06].http://nameddata.net/techreports.html

[13] 李军,陈震,石希.ICN体系结构与技术研究[J].信息网络安全,2012(4):75-80

[14] Podlipnig S, Böszörmenyi L. A survey of Web cache replacement strategies[J].ACM Computing Surveys,2003,35(4):374-398

[15] 张国强,李杨,林涛,等.信息中心网络中的内置缓存技术研究[J].软件学报,2014,25(1):154-175

[16] Eum S, Nakauchi K, Murata M, et al. CATT: Potential based routing with content caching for ICN[C]//the 2nd ICN Workshop on Information-Centric Networking.2012. 49-54

[17] Rossi D, Rossini G. Caching performance of content centric networks under multi-path routing (and more).Technical Report,Telecom ParisTech, 2011[EB/OL].[2016-01-06]http://perso.telecom-paristech.fr/～drossi/paper/rossi11ccn-techrep1.pdf

[18] Laoutaris N, Syntila S, Stavrakakis I. Meta algorithms for hierarchical web caches[C]//IEEE International Performance Computing and Communications Conference (IEEE IPCCC), Phoenix, April 15-17, 2004:445-452