软件学报  2014, Vol. 25 Issue (1): 154-175   PDF    
信息中心网络中的内置缓存技术研究
张国强1,3, 李 杨2, 林 涛2, 唐 晖2    
1(南京师范大学 计算机科学与技术学院,江苏 南京 210046 )
2(中国科学院 声学研究所 高性能网络实验室,北京 100190)
3(中国科学院 计算技术研究所,北京 100190)
摘要:互联网的应用方式正从以面向主机的点对点通信为主转向以海量内容获取为主.为适应这一转变,研究界提出了多种以信息/内容为中心的新型网络架构.这类网络架构中最重要的特征之一是利用网络内置缓存提高接收者驱动的内容获取的传输效率和网络资源的利用率.与传统的Web缓存、CDN缓存等相比,ICN缓存系统呈现了缓存透明化、泛在化和细粒度化等新特征,对缓存系统的建模、行为理解和优化方法都提出了新的挑战.在介绍了ICN缓存系统的新特征及带来的挑战后,首先从多方面着重阐述和比较了缓存网络的优化方法,之后对缓存网络系统的理论模型研究现状加以阐述,然后分析了仍待解决的关键问题和未来的研究方向.
关键词信息中心网络     内容中心网络     缓存     缓存协同     缓存网络    
Survey of In-Network Caching Techniques in Information-Centric Networks
ZHANG Guo-Qiang1,3, LI Yang2, LIN Tao2, TANG Hui2    
1(School of Computer Science and Technology, Nanjing Normal University, Nanjing 210046, China)
2(High Performance Network Laboratory, Institute of Acoustics, The Chinese Academy of Sciences, Beijing 100190, China)
3(Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China)
Abstract: Internet usage has dramatically transformed from host-centric end-to-end communication to content retrieval. In order to adapt to this change, several new information/content centric networking (ICN) architectures have been proposed. One common and important feature of these architectures is to leverage built-in network caches to improve the transmission efficiency of receiver-driven content retrieval and network resource utilization. Compared with traditional Web cache and CDN cache systems, ICN cache takes on several new characteristics: Transparency, ubiquity, and fine granularity, which put new challenges on the modeling, understanding and optimization of the networked cache system. In this paper, new features of ICN as well as their ensuing challenges are introduced, mechanisms to optimize the performance of cache network are analyzed and compared from various angles, and analytical models for the cache system are also presented. The study concludes with a discussion on some key issues and future research directions.
Key words: information-centric networking     content-centric networking     caching     coordinated caching     cache network    

据Cisco公司统计,全球IP流量在过去的5年中增长了4倍.2012年~2017年期间,IP流量仍将以23%的年均复合增长率高速增长[1].其中,大部分流量都将源自内容获取类应用.预计到2016年,仅视频类流量就将占到所有IP流量的86%.而随着用户生成内容(UGC)、时移电视和高清VoD的需求,用户驱动的数字视频内容产生的流量在未来几年仍将高速增长[2].

为了适应互联网应用由发送者驱动的端对端通信模式向接收者驱动的海量内容获取模式的转变,从网络体系架构层面(而非以网络中间件方式)提供对可扩展和高效内容获取的原生支持,同时增强网络对移动性和安全性的支持,研究界近年来提出了一类以信息/内容(为方便起见,本文将不区分内容和信息,而将这类网络架构统称为以信息为中心的网络(information-centric networking,简称ICN))为中心的新型网络体系架构[3, 4, 5, 6, 7, 8, 9],典型的如DONA[4],CCN[5],NetInf[8],PSIRP[9].有兴趣的读者可以进一步参考相应的综述文献[10, 11, 12].

在这类ICN网络中,用户并不关心内容的位置(即where),而只关心内容本身(what).网络对内容进行统一标识,基于内容进行定位、路由和传输,将内容提升为网络中的“一等公民”.为了缓解网络流量的快速增长对网络带宽造成的严峻压力,这类网络架构普遍提供透明化、泛在化的网络内置缓存以加速内容的分发,提高网络资源的利用率[10].虽然缓存也是目前互联网用于提高资源利用率的重要手段之一,但是由于缓存系统的相对封闭性以及对象缺乏统一的标识机制等原因,导致缓存的潜能无法得以充分发挥.例如,作为Web对象标识的URL同时也作为其定位符.当相同的对象被置于不同内容提供商的服务器时,将会使用不同的URL对其进行标识和访问.因此,Web缓存会将其识别为不同的对象.

虽然缓存理论及相关的优化技术已经在Web,CDN和P2P中得到了较为广泛的研究,但ICN中的缓存具有独特性,其所呈现出来的缓存透明化、泛在化和细粒度化等新的发展趋势致使传统的缓存理论、模型和方法均无法直接无缝地移植到ICN的缓存系统中.得益于全球各国对未来网络体系架构研究的支持,近年来,许多研究人员都致力于ICN中的缓存网络研究,在理论、模型和优化方法等多个研究领域都进行了开拓性的探索,并提出了创造性的研究成果.本文正是以此为背景,对ICN缓存网络的现有研究成果加以评述,对相关的研究思路进行溯源和比较,并指出未来的研究方向.

本文第1节对ICN缓存研究加以概述,重点分析ICN缓存所呈现的新特征以及由此带来的新问题.第2节主要评述优化ICN缓存网络系统性能的方法.第3节对ICN缓存网络的模型和理论研究成果加以阐述.第4节分析ICN缓存的未来研究方向和前景.最后,第5节对全文进行总结.

1 ICN缓存研究概述

在ICN中,缓存呈现出不同于传统的Web,P2P,CDN等封闭缓存系统的新特征,对传统的缓存理论、模型和优化方法均提出了新的挑战.概言之,ICN中缓存网络的新特征主要体现在缓存透明化、缓存泛在化和缓存细粒度化.下面首先从这3个角度分析ICN中缓存系统的新特征及其对缓存理论模型和优化方法带来的挑战,然后简要概述ICN缓存系统研究的主要内容.

1.1 ICN缓存的新特征及研究挑战
1.1.1 缓存透明化

传统的缓存针对单一的流量类型,通常以专用封闭系统的形式而存在,如Web,CDN,P2P等缓存系统.Web缓存系统虽然基于开放的HTTP协议,但是Web内容基于域自主命名,相同的对象无法被一致标识,表现为对象在逻辑上的按域隔离.P2P应用一般采用私有协议,使得每个P2P应用都表现为封闭的系统,难以实现缓存空间的共享.为了克服上述缺陷,P2P也在向缓存透明化的方向努力,如最近IETF在DECADE工作组开展的工作[13, 14]. DECADE旨在提供共享的缓存基础设施,让每个应用能够独立地管理缓存空间.但是,由于缺乏命名一致性,DECADE依然难以实现不同应用间缓存对象的共享.上述问题主要源自于两个原因:一是通信协议的封闭性;二是命名方式的不一致性.ICN很好地解决了上述两个问题:首先,ICN对内容进行全局唯一标识,实现了命名的一致性.通常,命名还具有可自验证的特点[4, 7, 8, 9, 10, 15],简化了内容的安全性检测;其次,ICN依据统一的一致性内容标识进行内容路由和存储决策.网络层感知内容标识的做法彻底实现了缓存与应用无关,使其成为通用的、开放的、对上层应用透明的基础服务.

缓存透明化带来了一系列的挑战,主要包括:

· 缓存目标不一致

传统缓存系统的目标较为单一,例如:Web缓存针对Web流量,以降低网络流量和用户访问延迟为主要目标;P2P缓存主要针对大文件分发,以降低网络流量为主要目标[16].而ICN作为一种新型的网络基础设施,其所服务的网络流量类型多样化,包括Web、VoD、文件共享等多种应用类型都将直接运行于ICN之上.不同类型的流量缓存的目标不尽相同,ICN应合理地确定整个缓存系统的缓存目标.

· 缓存资源的跨应用竞争性共享

不同的应用面向的内容对象具有高度异质性,典型的如Web对象、用户产生内容(UGC)、Vod对象和文件共享对象.这些对象在空间的规模、对象大小、对象流行度方面有着天壤之别[17].例如:Web对象空间的规模较大,数以10亿计,但对象大小一般都较小;而VoD对象空间规模较小,在105级别(受限于人类电影/电视剧制作的速度,全球VoD的数量级在可预计的未来不会发生突变),但每个对象都较大.流量类型所呈现出来的这种高度异构性对传统的单一、封闭的缓存系统提出了挑战,要求 ICN应能在不同的应用类型之间有效地共享缓存资源,实现预期的缓存目标.

· 缓存的线速执行要求

透明化的网络内置缓存对缓存的执行速度提出了新的要求,即要求ICN中的缓存以线速执行,这与传统的基于硬盘类存储的缓存相比,差异非常明显[18],对缓存的管理提出了新的挑战.传统的基于硬盘类的缓存可以采用大型数据库的“软件管理”模式,工作在应用层,无线速要求,存储容量的瓶颈取决于软件自身的运维和管理能力,存储管理算法可以较为复杂.而ICN中的缓存是工作在网络层的串联设备,要求以线速执行,存储容量的瓶颈在于内存访问速度,要求缓存管理策略简单、有效[19].

1.1.2 缓存泛在化

在传统的缓存研究中,缓存点的位置一般是确定的,缓存的网络结构是较为规则的树状层次结构,缓存之间的协同和内容放置可以基于先验的流量需求知识和缓存结构建立相应的数学模型,并求得最优解.而在ICN中,缓存呈现泛在化、网络化的新特征,缓存点不再固定,缓存的拓扑结构需用任意图的网状结构来描述,节点之间的上下游关系不再明确,这些均增加了数学建模和分析的难度,也使显式的缓存协同变得更为困难.

缓存的泛在化也对缓存内容对象的可用性(availability)提出了新的挑战.在传统的Web缓存或CDN缓存中,缓存对象对请求的可用性较为明晰.在CDN网络中,可以依据预知的访问需求和网络结构主动地对内容对象进行推送和复制,由重定向或DNS解析等机制来保证副本对象的全局可用性.在分层的Web缓存中,对于给定的对象请求,只有位于被请求点至Web缓存的根节点路径上所缓存的对象对该请求才是可用的,而位于该路径之外的节点所缓存的对象对该请求均不可用.但在ICN中,缓存的泛在性和对象被缓存时间的短暂性使得系统呈现高度动态性.如果通过全局解析系统或路由系统来向所有节点通告每个网络内置缓存节点所缓存对象的存在性, 则更新消息的规模会对系统的可扩展性形成严峻的挑战.同时,系统的高度动态性也使得维持系统状态的一致性变得尤为困难.如何在高度动态的泛在网络内置缓存环境下保持适度的对象可用性、优化对象的获取代价,是缓存网络亟需解决的一个问题.

1.1.3 缓存细粒度化

传统的缓存一般以文件或文件的可变段为单元进行对象的存储和替换等操作[16, 20, 21].但是,由于ICN需要以线速工作[22, 23],以文件为单元进行缓存的读写开销较大,难以满足线速执行的要求.因此,ICN大多将文件划分成独立可标识的更小数据块(chunk),并以数据块为缓存单元[5, 22, 24].这一缓存粒度的改变直接导致了下述变化:

· 流行度的变化

针对文件粒度的访问流行度研究较为成熟,例如,Web中的对象流行度服从Zipf分布[25],P2P中的对象流行度服从mandelbrot-zipf分布[21].但文件粒度的访问流行度并不能简单拓展到chunk粒度的访问流行度.同一个文件的不同chunk,其被访问的频率并不相同.例如,用户在观看视频时,通常会观看开头的一部分,以决定是否继续观看下去,从而导致视频文件的不同chunk具有不同的访问流行度.迄今为止,chunk粒度的访问流行度还缺乏详细的理论模型和实证研究.

· 独立参考模型的失效

传统的以文件为粒度的缓存模型通常基于请求遵从独立参考模型(independent reference model)这一假设,即某个对象被请求的概率仅与对象的流行度相关,而与先前的请求序列无关.但是,同一文件的不同chunk之间存在关联性,用户对chunk的请求一般以线性顺序产生.请求服从独立参考模型假设的失效,直接导致了许多缓存理论分析方法不再适用于chunk粒度的缓存系统分析.

· 缓存空间利用更有效

将大文件划分为更小的chunk后,同一文件的不同部分可以从不同的网络节点获得,丰富了获取途径的多样性.同时,替换某个或某些chunk,而非替换整个文件可能会提升缓存的效率.当然,以chunk为单位进行缓存,也使得某些基于文件对象大小的缓存替换算法不再适用.

1.2 ICN缓存研究的主要内容

ICN缓存研究主要可以分为两类:一类是缓存网络系统的性能优化方法,这类研究偏向于具体的技术方案,从不同的方面着手优化缓存系统的整体性能;另一类是对缓存网络进行适度抽象和简化,建立相应的理论模型并进行解析分析,为理解缓存系统的行为提供理论支撑.图1给出了ICN缓存中的主要研究内容.

Fig.1 Research topics of ICN cache network图1 ICN缓存网络研究内容

(1) 缓存系统性能优化方法

由于缓存是实现ICN的主要目标之一——提供可扩展和高效内容获取的原生支持——的最重要保障,优化ICN缓存服务的性能变得尤为重要.但是,ICN缓存呈现出的透明化、泛在化和细粒度化使得原有针对Web, CDN和P2P等封闭缓存系统的性能优化方法无法简单地无缝移植到ICN缓存系统之中.在由泛在、透明化的网络内置缓存构成的缓存网络中,影响整个系统性能的因素是多样化的.这些因素有些相互独立,有些则存在依赖关系.优化缓存性能的途径主要包括:缓存网络中各个缓存节点的大小设置、每个缓存节点上缓存资源在不同的应用类型之间共享的方式、确定在哪些节点缓存对象的缓存决策策略、决定替换哪些对象的缓存替换算法、缓存对象对请求的可用性以及缓存网络的拓扑优化.目前,除了优化缓存网络的拓扑结构尚处于研究空白以外,其他方面均已有不同程度的研究,其中,尤以缓存决策策略和对象可用性受到的关注度最高.这些研究方案一般都是优化其中的一个或几个方面,通过优化缓存资源的配置、提高缓存资源的共享度、降低缓存的冗余度,最终实现提升缓存系统整体效用的目的.

(2) 缓存系统建模与分析

正如排队论对理解包交换网络的行为起到至关重要的作用一样,缓存网络的理论建模和分析对理解缓存网络的行为也不可或缺.缓存系统的建模通常需要考虑对象的流行度、缓存网络的拓扑结构、缓存管理策略、每个节点上对象的外生(exogenous)请求到达速率、请求之间的关联性等诸多因素,并最终对建立的缓存数学模型进行理论分析.缓存网络建模的一个难点在于上述多种因素需要放在任意图网络拓扑的上下文中同时考虑,节点之间存在复杂的联动关系.

相较于传统的层次化缓存模型,目前在ICN缓存网络的理论模型方面所做的研究工作仅拓展了缓存网络拓扑模型的类型,即引入了网状任意图结构,并解决了由此而衍生的缓存节点上下游关系不确定性问题.然而在其他方面,目前的理论模型依然沿用了层次化缓存模型中的假设,例如对象流行度服从zipf分布、外生请求到达服从泊松分布、请求服从独立参考模型、基于LCE(leave copy everywhere)的缓存决策策略等.在第1.1节中我们已经看到,由于ICN缓存具有透明化、泛在化和细粒度化特征,这些假设大多已经不成立或需要重新考证.总体来看,ICN缓存网络的理论模型目前还处于研究的早期阶段,相关研究工作也较少.

2 ICN缓存的性能优化方法

ICN中的缓存服务是实现高效内容获取的基石,因而,优化其性能变得尤为重要.ICN缓存所呈现出来的透明化、泛在化和细粒度化等新特征,对传统缓存机制提出挑战的同时也带来了新的机遇.目前,缓存网络的性能优化方法是ICN缓存的研究重点.总结现有的研究,基本可以分为缓存大小规划、缓存空间共享机制、缓存决策策略、缓存替换算法、缓存对象可用性这5个方面.

2.1 缓存大小规划

缓存存储空间的大小无疑会影响整个缓存系统的性能.当系统的其他设置相同时,缓存空间越大,能够缓存的对象也越多,整个系统的缓存命中率也将越高.当然,缓存空间越大,查询单个缓存空间的开销也越大.由于ICN要求节点以线速执行,这限制了ICN中节点能够支持的缓存空间大小.从缓存大小角度出发优化缓存网络的性能,主要需要解决下述两个问题:

其一是需要多大的缓存空间才能使缓存系统具有实质性的性能提升?

与传统的Web缓存中缓存可以无限大不同,线速执行的要求限制了ICN中节点的缓存大小.但同时,ICN预计承载的流量将涵盖互联网的全部内容传输,比整个Web的内容总和更大,因此,节点的缓存空间太小可能无法达到预期的效果.这就要求可依据路由器的性能差异(如核心路由器和边缘路由器的处理速度存在差别)来配置缓存的大小,满足线速执行的要求.为此,需要对各种存储器材质的访问速度、最大可允许的大小、单位存储价格以及功耗等有清楚的了解,作为ICN不同的功能部分进行存储器选择时的决策依据[19].例如,在CCN中, 假设线速为100Gbps,若每个请求在PIT保存的时间为80ms,那么PIT大小约为14Mbits~1.4Gbits,应考虑选用RLDRAM;相反,如果选用SRAM,则太小.

其二是缓存资源在不同节点的分配,即在给定的资源投入限定下,应为哪些节点分配更多的缓存,才能使缓存系统的整体性能更好?

这实际上是一个在给定预算下的网络规划问题.缓存大小分配应主要考虑缓存网络的拓扑结构和网络的流量需求两个因素.Rossi等人认为,依据网络拓扑的中心性为节点分配缓存对网络性能提升有限,基于简单的节点度中心性的分配方案就能达到与基于更为复杂的中心性指标分配方案几乎相同的效果.而Psaras等人则认为,分配缓存空间对提高网络性能是有益的,为边缘而非核心节点增加缓存容量对提升性能更有益[18].这表明:在考虑网络拓扑的影响时,不应简单地基于网络的一些中心性指标,而应更多地考虑缓存节点与用户的距离以及所服务用户群体的大小.同时,由于简单的缓存资源异构并不能取得理想的效果,有必要考虑将缓存资源的分配与内容的放置策略和内容查询(路由)策略相结合.另一方面,网络的拓扑信息是一种先验知识,并不能反映网络流量的真实情况,缓存资源应依据实际的流量分布来进行配置.例如,Rossi等人指出:网络的流量分布呈现locality特性,即网络的流量在短期内会呈现一定的波动;但从更长的时间尺度来观察,一个区域的流量是稳定的[26],这为依据流量分布的先验知识来指导缓存资源的分配提供了理论依据.

2.2 缓存空间共享优化

缓存透明化的一个直接后果是不同的流量/应用类型需要竞争使用有限的缓存资源.由于不同的应用/流量类型具有不同的流量特征,其缓存目标也不尽相同,如何在不同的应用/流量类型之间共享有限的缓存资源,并提供差异化服务,成为ICN中的缓存系统亟需解决的问题.

2.2.1 缓存差异化服务

基于缓存提供差异化服务一直都具有重要意义.文献[27]提出了利用缓存提供差异化服务的3个出发点:

· 从终端用户角度看,缓存对接入速度快的用户更重要,也更有益.若网络的瓶颈在核心网,则缓存可大幅降低传输时延;反之,若网络瓶颈在边缘,则缓存所发挥的作用并不明显.因此,缓存应该优先服务于具有更快接入速度的用户.这要求不同的接入方式有不同的访问协议(如无线访问的WML语言),使得网络能够对此予以识别和区分,从而提供差异化的服务;

· 从内容角度看,优先缓存用户易于察觉的内容对提高用户感知的性能更有益.例如,浏览Web时,用户感知的访问延迟更多地取决于下载HTML页面的时间,而非内嵌对象的下载时间.因此,缓存系统应该优先服务HTML页面.这要求系统能够区分对象的类别;

· 从内容提供者角度看,ISP可能与不同的内容提供商具有不同的契约,为某些内容提供商提供更优质的服务.这要求系统能够区分内容提供者.例如,可以通过URL或内容网络中的主体标识等实现对内容提供者的识别和区分.

2.2.2 缓存的共享方式

为了实现基于缓存的差异化服务,需要有相应的缓存资源竞争性共享机制作为支撑.共享缓存的方式可以分为固定划分和动态共享两种.

(1) 基于固定划分的共享

固定划分是指为不同的应用/流量类型划分固定的缓存空间大小.为每类应用/流量分配的缓存空间仅服务于该应用/流量类型,因此,每种应用/流量类型不会干扰其他应用/流量类型的性能.固定缓存空间划分依然存在两个问题:

一是划分的比例应该是多少比较合适?

二是每个节点按相同的比例划分空间,亦或不同的节点可以采用不同的划分比例?

针对前者,文献[27]提出采用不同应用/流量类型期望的缓存命中率来刻画整个缓存系统服务质量的差异性,并基于控制理论提出了一种动态反馈机制,能够自适应地调整划分的比例,从而使得不同类别应用的命中率之比可满足事前约定.图2给出了该动态反馈机制的工作机理.针对后者,文献[17]指出:VoD类应用能够通过较小的缓存获得较高的命中率,而UGC、文件共享和Web类应用则需要大得多的缓存空间才能获得同样的命中率.基于此,文献[1]建议可将第1层缓存专用于 VoD类应用,而非无区别地对待所有流量,即不同的节点采用不同的划分方式更为合适.

Fig.2 Self-Adaptive cache space partitioning based on dynamic feedback图2 基于动态反馈机制的自适应缓存空间划分机制

固定分配虽然易于实现,但无法有效地使缓存资源在不同应用类型之间实现动态共享.缓存系统通常会为被缓存对象设置TTL,究其原因主要有两点:其一,内容可能会过时,如实时流媒体的数据几秒钟后便不再有用,因而无需长时间缓存数据;其二,基于TTL的机会缓存可以在不具备显式缓存协同的前提下提高缓存可扩展性.当然,TTL的设置可以依据不同的应用而变.但一旦设置了TTL,则缓存中与某种应用相关的有效数据量则大约等于它的到达率乘以其TTL.因而,若采用固定分配方式,则某些应用类型可能不会在所有时间段都耗尽为其分配的缓存空间,而另一些应用/流量类型在某些时间段内则可能会出现缓存空间不足的情形,从而降低缓存资源的效用.

(2) 动态共享

缓存空间的动态共享则在一类应用不占用缓存资源时允许另一类应用占用,实现了缓存空间的统计复用.动态共享策略用于指定不同类型的应用共享缓存的方式.常用的两种策略包括基于优先级的共享策略和基于加权公平的共享策略[28].基于优先级的共享策略的目的是给予某些应用更高的服务优先级.实现优先级共享策略需首先根据应用需求对应用进行优先级划分,当某个需要被缓存的对象(由缓存决策策略决定)到达缓存节点但缓存没有足够空间容纳该对象时,从缓存系统中删除比该对象所属应用类型的优先级更低或相等的对象(优先级相同时,由缓存替换策略决定删除哪个对象),直至能够容纳该对象为止.与固定划分类似,加权公平共享策略也旨在能够根据预先设定的权重在不同的应用之间共享缓存资源.但与固定划分不同,加权公平共享可保证

资源被充分使用.设N个应用{Ai} ,其对应的预设服务权重为{Wi},并记xi表示应用Ai实际占用的缓存空间,

则当某个需要被缓存的对象到达缓存节点且缓存没有足够空间容纳该对象时,选择xi/wi(i=1,…,N)最大的应用类型,然后依据缓存替换算法删除属于该应用类型的对象,直至能容纳待缓存对象为止.

2.3 缓存决策策略

缓存决策策略是指应在缓存系统的哪些节点缓存哪些对象的决策算法.在传统的Web缓存和CDN缓存中,某些时候可以通过先验的拓扑和流量知识以及线下的计算实现缓存对象的预先放置,也可以通过在线交互各个缓存节点的状态,实时计算出最优的对象缓存位置[2, 29, 30, 31, 32].上述方式通常被称为显式的缓存协同决策.但在ICN中,缓存节点不再是固定的,缓存的流量类型是多样化的,缓存的操作要求是线速的,因此,显式协同决策算法由于其复杂度高、通信需求大而不适用于ICN,ICN需要研究简单的缓存决策策略.

LCE(leave copy everywhere)是许多ICN中(如CCN)的默认缓存决策策略,即当对象返回时,沿途的所有节点都缓存对象,但这种方式容易造成缓存冗余,即相同的对象在多个节点同时存有副本,降低了缓存系统所能缓存内容的多样性.为了提高缓存的整体效用,需要做到:

(1) 将流行度高的对象快速复制到边缘缓存节点,减小用户下载的平均时延,提高网络资源的利用率;

(2) 提高整个网络缓存系统的缓存多样性,特别地,需要提高同一运营商(自治系统)的内容路由器所缓存的对象的多样性,尽量使得用户请求由同一运营商(自治系统)内的缓存节点予以满足,从而大幅降低域间流量[33, 34].

降低缓存冗余、提高系统的缓存多样性,需要缓存节点之间进行简单而有效的协同.依据协同的复杂性,大致可将现有方案分为两类:显式协同和隐式协同.依据协同决策点的不同,又可分为集中式决策和分布式决策.

2.3.1 显式协同缓存决策

显式协同机制需要以访问模式、缓存结构和每个缓存节点的状态为基础,通过复杂的计算确定对象的放置.参与显式协同的缓存节点的范围可以不一,一般可以分为全局协同、路径协同、邻域协同这3类.

集中式的全局显式协同在CDN中较为常见.在已知缓存节点集合、缓存节点相互之间的网络距离、每个缓存节点产生的对于每个对象的访问速率等前提下,运营商需要确定对象在缓存系统的最佳放置位置,以最小化用户的访问代价[29].全局显式协同还可以是分布式的,例如文献[2]所提出的机制.在该文中,作者为每个对象n和节点i构成的二元组定义了一个效用值u(n,i),表示对象n存储在节点i的效用.基于此,提出了一种局部贪婪的协同算法:选择任意的二元组(n,i),若n当前未存储在节点i,且存在对象m,使得u(n,i)>u(m,i),则将m替换为n.在ICN中也提出了基于哈希的全局显式协同[35, 36],由于缓存效率限制,这类方案只是简单地基于内容名计算出一个哈希值,当内容达到时,依据哈希值将其缓存在负责该哈希值的缓存节点上,而当请求抵达时,则直接依据哈希值先查询负责该哈希值的缓存节点.基于哈希的全局显式协同避免了CDN中的复杂的协同算法,最大程度地提高了缓存的多样性,但是对于流行度高的对象来说,在整个域内仅缓存一份拷贝,会增加用户的访问延迟.

路径显式协同指的是在对象从命中节点到请求节点的传输路径上进行是否缓存对象的协同决策,如协同沿路径缓存(cooperative en-route Web caching,简称CERC)[30, 31].这类方法在请求时将途经缓存节点的状态、对象的请求频率等信息都携带在请求报文里.当请求抵达命中节点后,命中节点依据请求报文所携带的路径上所有节点的状态信息,通过动态线性规划,计算出最优的对象缓存位置,同时也计算出在这些位置需要替换的对象集,使得在这些节点缓存对象所得到的收益值要大于因此而替换掉的对象的损失值.Shen等人对上述工作进行了扩展,从而使其能够适应多服务器的情况[32].

邻域显式协同则是在一个节点的邻域范围内显式地进行缓存放置位置的协作.文献[34]提出了一种基于Hash的邻域显式协同机制CINC(cooperative in-network caching).当某个chunk对象到达一个缓存节点时,该缓存节点通过一个Hash函数决定应该由它的哪个邻居节点(包括它自身)来缓存该chunk.具体地,如图3所示,假设邻域包含k个节点,编号为0,1,…,k-1,那么对于每个编号为x的chunk,由编号为i=x mod k的节点来缓存该chunk.该方法避免了同一chunk在邻域范围内的重复存储,提高了缓存多样性.然而,该方案需要一种智能的节点标号算法,使得每个节点和与之协作的k-1个节点之间的网络距离之和最小.当某个节点失效时,恢复也较为复杂.文献[37]也提到了另外两种邻域显式协同方案:(1) 当节点收到一个对象时,仅当该节点的所有邻居节点都没有该对象的缓存副本时,才在该节点缓存该对象;替换时,优先替换邻居节点中存在副本的对象;(2) 当节点收到一个对象时,仅当该节点到源节点路径上的父节点不存在上述对象的副本时,才在该节点缓存该对象,在替换时,优先替换父节点存在的缓存对象.文献[38]也提出了一种邻域范围内进行缓存协同的方法,该方法并不是在对象到达时进行协同,而是运行一个降低邻域范围内缓存冗余的后台程序,当某个事件发生(如邻域范围的冗余度超过某个阈值)或定期地清理邻域范围内的冗余缓存对象.

Fig.3 Hash-Based explicit neighboring cache coordination图3 基于Hash的邻域显式协同机制

全局协同、路径协同和邻域协同分别降低了对象在全局范围、路径范围和邻域范围的缓存冗余度,增强了缓存多样性,有益于提高缓存的整体效用.但是无论哪种显式协同方案,都需要预知网络缓存节点的状态信息和用户对对象的请求频率等信息,且需通过复杂的信息交互和计算才能做出决策,这对于要求线速执行的ICN来说,无疑过于复杂.

2.3.2 隐式协同缓存决策

与显式协同不同,在基于隐式协同的缓存决策中,每个缓存节点无需知道其他节点的信息或仅需交互很少的信息,便能自主地决定是否需要对对象进行缓存.

层次化缓存是隐式缓存的一个例子.这种特殊的网络结构使得边缘网络节点能够识别流行度高的请求,从而将流行度高的内容对象缓存在边缘网络节点.而由于过滤效果(filtering effect)的存在,高层次的缓存将会缓存流行度适中/较低的对象,从而实现了一定程度的协同.但是ICN中缓存拓扑结构呈现出网络化特征,缓存节点之间的层次关系难以界定.此外,外生请求也可能在任何缓存节点产生.因此上述机制在ICN中不再有效.

LCD[39, 40],MCD[39, 40],Prob[39],WAVE[41],CATT[42],CLS[43]以及文献[18, 44]等均提出了不同的隐式协同方案,试图改进LCE中的缓存冗余性问题.这也是目前ICN研究的一个重点方向.图4给出了几种典型的隐式缓存协同决策策略:

· LCE(leave copy everywhere):在对象传输的沿途节点都缓存该对象.这是许多缓存系统的默认方案,本质上没有协同机制;

· LCD(leave copy down):当缓存命中时,仅在命中节点的下游节点缓存该对象,避免了同一对象的大量复制,并且需要多次对某一对象的请求才会将该对象复制到靠近客户端的地方,潜在地考虑了对象的访问频率;

· MCD(move copy down):当缓存命中时,将缓存对象从命中节点移动到命中节点的下游节点,而将其从命中节点的缓存中删除.与LCD相比,MCD进一步减少了对象的复制次数;

· Prob(copy with probability):每个沿途节点都以概率p缓存对象,而以概率1-p不缓存对象,p的值可以依据缓存情况进行调整.该方法可以认为是LCE的一般化,当p=1时,即退化为LCE;

· RCOne[42]:在对象返回的沿途节点中随机地选择一个节点缓存对象.对于层数为l的层次化缓存来说,该方法基本等价于p=1/l的Prob方法.与Prob方法类似,随机化的缓存决策易于实现,但并未考虑对象的访问频率;

· ProbCache[18]:一种基于加权概率的缓存机制.返回路径中的沿途节点缓存对象的概率与节点和请求者之间的距离成反比.该方法旨在提高内容在距离请求者更近的节点被缓存的概率,快速地将对象复制到距离请求者更近的网络边缘,提升共享路径节点的效用.但是,由于未考虑复制对象的访问频率,会增加不同对象在边缘缓存节点的竞争.

Fig.4 Some typical implicit cache coordination schemes 图4 几种典型的隐式缓存协同决策机制
2.3.3 缓存决策时机

上述缓存决策均着眼于新对象是否应该缓存在给定的节点,从而降低缓存的冗余度,提高缓存的可用性方面,即缓存决策时机是在新对象到达时.但缓存决策的时机同样可以发生在缓存替换时.如我们最近提出在缓存替换时并非简单地将对象删除,而是将对象上推一跳至网络的核心[43].在Web缓存中,也有类似的工作,如Demote[45]. Demote在替换对象时,将要替换的对象发送到层次化缓存的上一层节点,在上层节点中把该对象移动到LRU列表的表头.此外,替换对象时,可能不仅依据自身的缓存状态,还依据整个路径或邻域的缓存状态,将引发缓存不命中代价最低的对象或邻域节点中已有副本的对象剔除,从而增加整个缓存系统的效用[30, 31].

2.3.4 缓存决策的关联性

上述研究大都是对每个数据块独立地做出是否缓存该对象的决策决定,但ICN中的chunk存在相关性,因此决策过程也应具备相关性,可以称为关联决策.WAVE[41]在关联决策方面进行了初步探索,该方法依据文件的流行度调整每个节点缓存该文件的chunk数目,当以文件为单位的访问次数增加时,以指数速度增加该文件被缓存的chunk数,从而更快地对文件的chunk进行扩散.在WAVE中,内容路由器通过显式地设置缓存建议标记(如在CCN中的数据报头),使得下游一跳的内容路由器能够缓存被标记的chunk.一旦chunk被缓存,则缓存建议标记清零.这类似于LCD的做法,即每次仅将对象下推一跳.与LCD不同的是,WAVE按文件为单元统计其被访问的次数.文件被第1次访问时,将第1个chunk置缓存建议标记;当文件被再次访问时,将两个chunk置缓存建议标记;当文件被第n次访问时,将2n个chunk置缓存建议标记.从而, 如果一个文件访问频率较高,则整个文件将加速在缓存系统中扩散;而如果文件访问频率低,则所占用的缓存资源很小.图5示意了WAVE的简单工作过程.

Fig.5 Illustration of how WAVE works 图5 WAVE的工作方式示意图
2.3.5 分析和比较

缓存决策策略是目前ICN缓存网络研究的一大重点,表1从缓存的协同方式、决策时机、决策依据、是否具备关联性、缓存冗余度、对象复制到边缘的速度这6个方面对不同的缓存决策策略进行了比较.

Table 1 Comparison between different cache decision policies 表1 不同的缓存决策策略比较
2.4 缓存替换算法

缓存替换算法在传统的Web缓存中已经得到了广泛的研究,可参考Podlipnig等人发表在ACM Computing Surveys上的综述文章[46].但ICN中的缓存要求线速执行,因此复杂的缓存替换算法并不适合.总体来看,缓存替换算法并不是ICN中研究的一个重点,ICN对缓存替换算法简单性的要求胜于缓存替换算法之于缓存系统性能提升(如命中率)的要求.最近的研究[42, 47]也表明,在ICN中采用简单的随机替换算法基本上就能达到LRU替换算法的性能.

2.5 对象可用性(availability)

对象的可用性是指对象如何为请求消息所感知,从而对其可用,达到提高缓存效用的目的.对象可用性由对象的可见性(visibility)和对象查询策略两方面动态作用决定.对象可见性是指一个节点存储的对象为网络中其他节点的感知程度,而对象查询策略则指的是依据对象可见性信息采用的对象查询算法.对象可见性包含两个极端:一个极端是缓存对象仅为该缓存节点所见,另一个极端是缓存对象为网络中所有节点所见.而在这两个极端之间,则是缓存对象为部分节点所感知,存在广阔的设计空间.对象被节点所感知的程度也有差别.例如,可以直接维护缓存对象和缓存节点的映射关系,也可以仅维护被缓存对象的路由建议或索引摘要等信息.依据对象的可见性不同,可以采用不同的对象查询策略,使缓存对象对请求具有不同范围的可用性.例如,当对象仅为该缓存节点可见时,如果采用洪泛的对象查询策略,则可以使对象对请求具备全局可用性;而如果仅将请求路由至源节点,则对象对请求仅具备路径可用性.

一般来说,对象的可见性范围越大,则请求消息能够更精确地被路由到合适的缓存节点.但是,提高对象可见性需要付出额外的代价:

· 一方面,需要在更大的范围内通告对象的存在性信息,而由于网络内置缓存节点上的对象动态性较高,需要以较高的频率更新对象的存在性信息,这会引起存在性通告信息的泛滥;

· 另一方面,高度的动态性也会增加保持系统状态一致性的难度.

按照对象可用性的范围,一般可以将现有的研究分为下述3类:路径可用、全局可用、局部可用.

2.5.1 路径可用

在一般的Web缓存和大部分ICN研究中,请求消息都是以最短路径或anycast的方式向对象源节点进行路由,直至路由过程中缓存命中为止[4, 5, 30, 31, 48, 49, 50].在这种En-route方式的缓存匹配机制下,只有位于路径节点中的缓存对象对请求消息具备可用性.

上述模式下,即便路径上某个节点的毗邻节点缓存了所请求的对象,且该毗邻节点与请求节点之间的网络代价要远小于对象源节点和请求节点之间的网络代价,但只要路径上的节点不包含请求的对象,请求依然会被路由至源节点,这降低了缓存的效用.因此,一个普遍的共识是:在ICN中,应通过路由协议或注册系统,使得缓存的对象对于不经过该节点的请求也具备可用性[10].

2.5.2 全局可用

CDN中,所有的内容副本都是按需放置的,这些副本的存在性向全局解析系统进行注册,从而所有的副本对象对请求都是可用的,由具体的解析机制决定使用哪个副本.除了通过全局解析系统进行可用性注册外,还可以通过全局路由系统进行存在性通告,保证副本内容的全局可用性.ICN中也可以通过全局路由系统或注册系统通告源对象的全局可用性,如CCN[5]和DONA[4],但是并不通告网络内置缓存中被缓存对象的全局可用性.因此,网络内置缓存中的缓存对象本质上对请求依然只具有路径可用性.

由于ICN中缓存内容变化快、缓存数量大,因此一般不可能把网络内置缓存中被缓存的对象向集中的解析系统注册,或通过路由系统进行全局通告,这样做的代价过于高昂,会降低系统的可扩展性.但是,仅依赖于路径可用性则无法有效地利用缓存的性能.因此在泛在网络缓存中,如何平衡缓存对象对请求的可用性范围以及由此所付出的代价,是ICN网络缓存需要研究的一个重要问题.

2.5.3 局部可用

解决上述矛盾的一种方案是让网络内置缓存中存储的非持久性对象在网络中的局部可见,从而在可用性和可扩展性之间获得有效的折中,这也是目前ICN缓存研究的热点之一.具体地,存在下述几种方式:

· 缓存查询

当缓存不命中时,通过缓存查询协议,如ICP[51],向邻居节点发送查询请求[50].但无的放矢的查询会大幅度地增加所需带宽和感知的延迟.

· 缓存索引

每个节点存储邻域节点缓存内容的索引.当缓存不命中时,继而查询邻域节点的缓存对象索引表.该方法在分布式缓存、P2P缓存已得到广泛的研究[50, 52, 53, 54, 55],但在ICN中刚得到重视[34, 56].CONIC[56]中,内容存放在终端节点上,索引存放在内容路由器上,可将其看成是介于纯P2P和纯内容中心网络之间的一种折中方案.而在文献[34]所提的CINC方案中,内容和索引都存放在内容路由器上,通过Hash函数确定每个邻居路由器负责的chunk号,避免同一个chunk在邻域范围内的重复存储.

· 路由建议

每个节点依据对象转发的历史或对象通告消息建立路由信息表.当缓存不命中时,将请求依据路由信息表转发给相应的邻居节点,并由邻居决定是否继续转发给其邻居节点.ICN中,以Breadcrumb[37, 57]和CATT[42]为代表.类似的思想可以追溯到P2P网络中的对象复制与查找,如Routing Indices[58]和Freenet[59].Routing Indices在每个节点维护一张路由建议表,用于指出通过每个节点能够获取的属于某个话题的对象数(以及可选的路由跳数).当接收到一个请求时,依据请求的话题和该路由建议表选择一个最优的邻居进行请求转发.Freenet则依据对象的Hash键值对文件进行统一标识,每个节点都包含一个Conten t Store和一张路由表.路由表维持了该节点所知的文件标识和文件源的映射.当请求到达时,节点首先查找自身的Content Store.若缓存不命中,则依据文件标识应用“最陡梯度爬山查询法”进行查找,即每次都将查询发往路由表中与该文件标识最相近的文件标识所在的节点.当最终文件命中时,对象沿请求路径返回,并在每个请求节点缓存,同时,路由表记录下文件标识和文件源的映射.Breadcrumb是一种根据数据转发的历史行为建立路由建议表的机制,并不显式通过控制层来生成路由建议表.在对象返回时,不仅沿途缓存对象,还在返回路径留下一条轨迹信息,用于记录缓存对象的转发方向和经过的时间信息.具体地,Breadcrumb通过一个五元组(FID,NIDfrom,NIDto,Tpass,Treq)来记录相关信息.其中, FID是对象全局唯一的标识,NIDfrom表示对象到达的上游节点ID,NIDto表示对象转发的下游节点ID,Tpass表示对象最近经过该节点的时刻,Treq表示节点最近收到该对象请求的时刻.当一个新的请求到达时,如果缓存命中,则直接返回该对象;如果缓存未命中,则依据轨迹信息决定是将查询沿着某条轨迹向下游转发,还是沿着原来的方向向对象的源节点转发.如果沿着轨迹转发导致查询失败,则节点仍会把请求发往源节点.因此,路由建议只是作为一种优化措施,该方法因此被称为尽力而为的内容查找(best effort content search,简称BECONS). Breadcrumb提出了可以将请求沿着轨迹信息向下游节点转发 的两条准则.假设t时刻查询qf到达缓存节点C,

且对象f并未缓存在C,则对Tf,,节点C仅在下述两个条件之一得到满足时,才将qf向下游节点转发:

(1) 在[t-Tf,t]时间内,文件fC节点被缓存过或者有成功的请求消息更新过该踪迹信息;

(2) 在[t-,t]时间内,存在qfC发送往下游节点.

CATT提出了一种基于势的内容路由(potential based routing,简称PBR),需要事先通过控制层面的信息扩散建立路由表.对于给定的文件c,给定的节点n,给定的缓存有c的节点nc,定义了n受到nc的势能影响.势的取值与nnc之间的距离成反比,而与缓存文件的质量成正比.这里,质量可以解释为nc的带宽和处理能力等.节点n所受的势能影响则定义为所有缓存有c的节点对n的势能影响之和.当对文件c的请求到达节点n,且n无法满足请求时,选择与n的势能差最大的邻居节点,并将请求转发给该邻居节点.

为了解决可用性和网络动态适应性之间的矛盾,CATT定义了两类势场:

第1类是持久性势场(permanent potential field,简称PPF).对于那些在内容源节点的对象,可在整个域中广播对象的存在性,由于这些对象的稳定性较高,因此无需经常更新其存在性信息;

第2类是非持久性势场(volatile potential field,简称VPF).对于在网络内置缓存中的对象,经常会被替换,稳定性较差,只在有限范围内广播其存在性,这样可以避免由于经常更新而导致的可扩展性问题.

实际的系统采用上述两种势场的组合,从而有效地平衡了对象可用性和系统可扩展性.

对于大部分采用缓存对象局部可用的方案,缓存节点都需要额外增加一个内容索引表或路由建议表.进而,请求的处理过程也需要增加查询邻域节点内容索引表或路由建议表的步骤:

(1) 查询自身的Content Store;

(2) 若Content Store查询失败,则依据可用性信息进行缓存对象的定位;

(3) 若无法定位到缓存节点,则通过传统的路由机制向源节点转发请求.

以CCN为例,需要在转发引擎中增加一个路由建议表或索引表(如图6所示),当对某个对象的请求无法由本地缓存满足时,依据路由建议表或索引表转发请求,使得网络内对该请求可用缓存对象得到响应请求的机会.

Fig.6 Original and enhanced CCN forwarding engine图6 原始的CCN转发引擎和改进的CCN转发引擎
2.5.4 分析与比较

对象可用性主要解决的是网络内置缓存中所存储的非持久性对象对请求的可用性.对于稳定的对象源来说,一般都由路由机制或映射机制保证其全局可用性.因此,我们在这里仅比较不同缓存网络方案中网络内置缓存所存储的非持久性对象的可用性,详见表2.

Table 2 Comparison of content availability between different cache schemes 表2 不同的缓存网络方案中网络内置缓存对象的可用性比较
3 ICN缓存的理论模型

缓存网络建模的目的是对缓存系统进行适度的抽象和简化,建立相应的理论模型并进行解析分析,为理解其行为提供理论支撑.早期的缓存理论分析针对单个缓存[60],Web缓存出现以后,缓存网络的建模一般面向特殊的网络拓扑结构,如线性的级联网络结构或层次的树状结构[48, 49, 50].这类网络结构的特殊性降低了节点间联动关系的复杂性,简化了理论模型的建立和解析.因此,即便是最近的ICN缓存建模研究,也从层次化网络结构开始探

[24, 61, 62, 63].但是,真实的ICN缓存网络拓扑不再能简化为层次结构,而需要用网状结构的任意图来描述.最近, Rosenswei等人在这个方向迈出了坚实的一步,建立了任意拓扑缓存网络的近似理论模型,并给出了缓存网络能够达到稳态的几个充分条件[64].

下面分别从网络结构模型、外生请求到达模型、实际请求到达率和系统的稳态分析这4个方面对现有的缓存网络建模研究工作予以分析和阐述.

3.1 缓存网络的拓扑结构

缓存网络建模针对的拓扑结构可以大致分为线性级联结构、层次结构、任意图结构,如图7所示.

在级联缓存或层次化缓存中,缓存是一个封闭的系统,用户请求首先由位于最低层的缓存节点服务,当请求无法得以满足(即缓存不命中)时,缓存系统将请求转发给上层的缓存节点,若仍不命中,则继续向上层缓存节点转发,直至根节点.如果根节点依然无法满足请求,则根节点将请求路由到缓存系统之外的源节点,并从源节点获得所请求对象.对象沿着请求路径逆向返回,并在整个缓存系统中进行沿途复制.在这两种拓扑结构中,逻辑上数据源只与缓存的根节点相连(这里的相连并非指物理上直接相连,而是指通过路由系统可达),缓存系统独立于路由系统.

而在任意图网络的缓存中,请求可以从任何一个节点到达,数据源也可以和任何一个缓存节点相连.网络不存在明确的层次结构,当缓存不命中时,请求的转发取决于具体的路由算法.因此,对于某个对象,缓存A可能是缓存B的父节点;而对于另一个对象,缓存A则可能是缓存B的子节点.

Fig.7 Topological structures of cache system图7 缓存系统的拓扑结构
3.2 外生请求到达模型

对给定的缓存节点而言,其外生请求是指源自于缓存系统之外的请求,不包括由于邻居节点缓存不命中而向其转发的请求.一般来说,每个节点的外生到达速率可以按照泊松过程予以模拟[24, 48, 50, 61, 62, 63, 64].为了方便起见,表3给出了缓存网络模型描述和分析中用到的符号及其含义.将每个节点v的平均外生请求达到速率记为lv.细化至每个对象fi,节点v观测到的对fi的请求到达速率li,v同样也遵从泊松分布 ,有li,v=lvqi,其中,qi表示被请求的对象是fi的概率,满足 .在现有的建模研究中,均假设请求遵从独立参考模型.

Table 3 Symbols with their meanings used in cache network modelling 表3 缓存网络理论建模中用到的符号及其含义

在线性级联和层次结构的缓存系统中,一般假设外生请求只产生于最低层的缓存节点,其他上层的缓存节点均没有外生请求,而只有下一级缓存由于缓存不命中而转发至此的请求.但在ICN的缓存网络建模中,一般假设任何节点均会有外生请求到达(在实际的网络中,一般只有网络的边缘节点有外生请求到达,而核心节点则没有外生请求到达.假设任何节点均会有外生请求到达是作了最普适的假设,如果核心节点没有外生请求到达,则可以将其到达率设为0).

3.3 实际请求到达速率

在缓存网络中,每个节点观测到的实际请求可以分为两类:其一是外生的请求,其二是邻居节点由于请求不命中而向其转发的请求.对于线性级联结构和层次结构,节点的上下游关系是明确的,相互之间的联动关系较为简单.设节点v实际请求到达速率为rv,缓存不命中速率为mv,则显见,下述关系成立:

细化至每个对象fi,其实际请求到达速率ri,v满足:

其中,mi,v表示缓存节点v上之于对象fi的请求不命中速率.

但是对于网络化内置缓存,节点的上下游关系不再是固定不变的,而是由文件源的位置和路由算法动态确定.记为从节点v到文件对象fi的源服务器vs的一条最短路径,记表示路径上的第j个节点,满足是初始节点v的下一跳节点.给定两个节点v,v'ÎV,定义,即R(v,v')中的每个文件对象索引号i都满足如下条件:v'是从节点v到存放文件对象fi的服务器之间的最短路径上v的后继节点.也就是说,一旦缓存节点v无法满足对于对象fi的请求,则该请求将被转发给v'.基于上述定义,ri,v满足下列关系:

3.4 缓存系统的状态分析
3.4.1 层次结构缓存网络的稳态分析

建模的目的是为了分析缓存网络在高度动态情形下的行为,一般地,这类研究均关注系统进入稳定状态后的缓存命中率(这里,稳态指的是在外生请求以稳定速率和分布特征到达的前提下,系统经过了初始的预热阶段后,每个节点的缓存命中率等统计指标趋于稳定的状态).然而,对缓存系统进行稳态分析具有很大的挑战性,即便是对单个缓存亦是如此.文献[24, 48, 61]对级联和层次结构的缓存系统进行了解析,给出了稳态情况下不同流行度的对象在不同缓存层次的不命中概率,具体结论如下:

(1) 流行度排名为k的对象在最低层的缓存中的不命中概率pk(1)为

其中,qk=ck-a表示流行度排名为k的对象被请求的概率,服从Zipf分布;x1表示第1层缓存的大小;g满足为对象平均大小.

(2) 对第i层的缓存,流行度排名为k的对象不命中的概率pk(i)可由下式递推得到:

3.4.2 任意图结构缓存网络的稳态分析

Rosensweig等人给出了任意图的缓存系统稳态分析方法[64, 65].记表示稳态情况下某个缓存节点v观测到的对象请求分布.对于单个缓存,当缓存空间大小和对象请求概率已知时,LRU替换算法可以看成是一个以对象请求分布和缓存空间大小为变量的已知函数是任何时刻每个对象为缓存节点v所存储的概率所构成的矢量.在请求服从独立参考模型的前提下,有:mi,v= ri,v×(1-hi,v)[60].Rosensweig等人将上述结论推广到了任意图的缓存网络[64],有:

可以采用迭代的方法对上述模型进行求解.迭代开始时,假设所有的mi,v=0,直到达到某个精度为止.

3.4.3 基于马尔可夫模型的稳态分析方法

稳态分析的一种常用方法是基于马尔可夫模型对系统进行分析.Psaras等人采用马尔可夫模型来为单个缓存建模,通过理论分析给出了一个给定的内容对象在路径中任何缓存节点存在的时间[62].它输出了给定的内容对象(PoI)不被系统缓存的时间百分比,本质上反映了给定内容对象的缓存不命中率**.

在文献[65]中,作者考虑了初始状态(即系统初始化时,每个缓存节点存储的文件对象排列)对缓存网络达到稳态的影响.缓存网络可以通过马尔可夫过程来建模,其状态空间为Ω0.系统的状态s=(s[1],s[2],…,s[n])为n个矢量的联合,矢量s[j](1≤jn)的元素个数为|vj|,其第i个分量表示缓存节点vj中第i个位置的文件对象.当所有节点的缓存大小都相同时,状态空间的基是.若对象在缓存中的顺序是无关紧要的,则状态空间的状态数为.每个文件请求序列和随之产生的缓存替换会引起状态的转换.文献[65]指出,在某些情况下,系统 的最终状态与系统的初始态有关,并给出了3个缓存网络是遍历态的充分条件.

3.5 小 结

目前,针对ICN缓存网络的建模和理论分析的研究工作仍然较少.Rosensweig等人在这方面的开拓性工作将缓存网络的拓扑结构延伸到了任意图网络,并进行了相关的理论分析,为进一步研究奠定了基础.但其模型解析仍有待进一步完善,有必要进一步探索该模型中系统存在稳态的充要条件.

更为重要的是,现有的网络理论模型依然延用层次网络模型中的诸多假设,其中大部分假设在ICN缓存中并不成立或需要重新考证,因此,基于更真实假设的模型研究工作尚待开展.

此外,目前的网络理论模型一般基于LCE的缓存决策策略和基于确定性路由的沿路径对象查询机制,并未考虑其他的缓存决策策略和对象查询策略.但是,从第2节可以看到,现有ICN网络性能优化的研究重点却恰恰在于缓存决策策略和对象可用性方面.因此,建立在其他缓存决策策略和对象查询策略假设下的缓存网络理论模型并予以解析,可能更具实际意义.到目前为止,这方面的研究尚为空白.

4 ICN缓存的未来研究方向与挑战

自2009年以来,ICN缓存网络的研究取得了一定的进展,目前仍然是一个充满挑战和机遇的新兴研究领域,可以进行开拓式创新或继承式研究并取得成果的方向有很多,主要包括:

(1) Chunk级别的对象流行度

对象的流行度是影响缓存效率的主要因素之一,也是缓存建模的重要一环.在ICN中,需要考虑chunk级别的流行度,而非对象级别的流行度.但至目前为止,尚未有chunk级别流行度分析的相关研究工作.这方面的研究可以从理论模型和实证分析两方面展开:

· 理论模型方面,可以依据现有文件级别的对象流行度服从Zipf分布、对象大小的分布等既有知识,并对用户访问chunk的行为作合理的假设,进而从理论上建立chunk级别对象的流行度分布;

· 实证研究方面,由于目前还不存在大规模的纯ICN网络及应用,可以间接通过PPLive等直播系统统计每个chunk(而非整个对象)的访问流行度,并以此作为ICN中chunk级别对象流行度的参考.当然,P2P中的chunk大小和ICN中的chunk大小并不一致,但至少请求的行为是类似的,结果具有可比性.

(2) 适合ICN网络的网络拓扑结构

在传统的互联网端对端传输的模式下,由于HOT模型[66]可最大化网络的端对端传输能力而被认为是最优的网络拓扑结构.但是ICN改变了网络传输以端对端为主的模式,因此,一个值得思考的问题是:什么样的网络拓扑结构适合ICN网络?Fayazbakhsh等人在SIGCOMM 2013上的一篇文章[67]通过简单的仿真实验指出,泛在化的缓存所获得的性能提升是有限的,因此,相比于其所付出的代价是得不偿失的.但是,这篇文章仿真实验所用的接入网拓扑是树状结构的,该文中的图5甚至出现了在同一个接入网获得内容要比从远端网络获取内容代价更高的情形.实际上,树状的网络拓扑图并不适合具有 泛在缓存的ICN.目前,这方面的研究尚处于空白状态,对于适合ICN网络的网络拓扑结构的探索可为未来ICN缓存网络提供设计指导.

(3) 缓存网络的建模及解析

虽然Rosensweig等人建立了基于任意图拓扑的缓存网络理论模型,但该模型仍需进一步加以完善,以使其更贴近ICN网络的假设.例如,需要摒弃请求遵从独立参考模型的假设,需要建立chunk级别对象的流行度并将其应用到网络建模中,等等.

此外,现有的网络理论模型一般都基于LCE的缓存决策策略和基于确定性路由的沿路径对象查询机制,未考虑其他的缓存决策策略和对象查询策略.然而,现有ICN网络性能优化的研究重点却在于缓存决策策略和对象可用性方面,通过自主的隐式协同和智能的查询算法提高缓存系统的整体效用.因此,以相应的更具实用价值的缓存决策策略和对象查询策略为基础建立缓存网络理论模型并予以解析,可能更具实际意义.到目前为止,这方面的研究尚为空白.

(4) 请求关联性分析及基于关联性的决策策略

基于chunk的缓存导致了请求遵从独立参考模型假设的失效,但目前的缓存理论模型尚未突破这一假设.如何建立请求之间的关联性模型,并据此优化缓存的决策策略,是能够有效提升缓存系统整体性能的潜在途径.目前,一般认为chunk之间的请求存在按序的关联性,但具体的数学模型和实证研究依然缺乏.WAVE[41]通过简单的策略验证了基于chunk之间请求的关联性设计缓存策略能够提升缓存性能这一事实,为进一步的研究开拓了广阔的空间.

(5) 低复杂度的缓存协同机制

智能的缓存决策策略降低了缓存冗余性,增加了缓存对象的多样性.但这种多样性要发挥作用需要有相应的缓存定位机制为辅,使之能够充分利用缓存对象的多样性.如何在ICN网络中以低复杂度实现隐式的缓存协同决策和智能的缓存定位,同时适应网络内置缓存的高度动态性,仍然是未来研究的一个重要方向.

此外,目前缓存协同研究大部分集中于单个自治域,但是未来的内容网络可能依然是由多个自治系统互联而成,形成缓存网络的网络.每个缓存网络都有各自的缓存协同机制,而自治系统之间需要以某种机制进行协商,以便能够利用邻居缓存网络的资源.Pacifici等人提出的方案[68]要求每个自治系统内部有一个节点具有本域内的所有缓存节点的实时状态信息,并与邻居网络进行信息交换,这在真实网络环境下很难实现.简单、灵活、可扩展的域间的协同机制和协议,将是ICN缓存在全网部署所必须解决的问题.

(6) 多路径转发

某些内容中心网络(如CCN)支持多径路由,即对同一内容前缀的请求可以同时通过多条路径并行在网络中传输,请求可能会被发往所有匹配的前缀发布者.多径转发有助于解决移动性和多宿主等问题.同时,多径转发和沿路径缓存也为高度动态网络环境下的通信提供了可靠的保障,如DTN网络[69].此外,多径转发也有助于ISP或用户监视、衡量和对比每条路径的性能,进而动态调整下一次的相同请求的转发路径.

但是,多径转发使更多的节点“除旧迎新”,增加了节点处缓存空间的竞争,造成以chunk为单元的命中率下降和网络流量增加,同时降低了带宽利用率和缓存多样性[70].因此,需要考虑竞争协同的多径转发策略与缓存决策策略.目前,这方面的研究基本上还处于空白状态.文献[47]首次通过仿真验证了内容中心网络中多径转发对系统性能的影响,得出了多径转发过程中“缓存污染”抵消了缓存副本带来的好处的结论.但是上述结论是基于简单的LCE缓存决策策略做出的,未考虑更智能的缓存决策策略的影响.上述问题类似于传统IP网络中自治域内流量工程与覆盖网络独立路由之间的矛盾[71] .传统IP网络中已有许多解决这一矛盾的方法,如基于非合作博弈的方法[72]、基于领导者优先策略的方法[73, 74]等,均可予以借鉴.

最近有研究指出:将网络编码与ICN有机地结合,能够简单、有效地发挥网络多径的优势,同时达到缩短传输时间和提高网络资源利用率的目的[75, 76].网络编码是一种新型的网络传输机制,网络节点不仅可以对数据包进行存储、复制、转发,还可以对数据包进行任意的编码操作.研究表明:网络编码对于内容分发大有裨益,能够有效地利用多径传输,简化调度算法[77, 78].但是,基于网络编码的信息中心网络中的内容命名、缓存机制和安全性考虑等诸多因素还有待研究.

5 总 结

随着互联网应用从以面向主机的端到端通信为主转向以接收者驱动的海量内容获取为主,研究界近年来提出了多种以信息/内容为中心的新型网络体系架构,旨在从体系架构层面支持高效可扩展的内容获取应用模式,解决互联网面临的流量爆炸问题.在这类网络架构中,透明化、泛在化的网络内置缓存是实现高效内容传输的根本保障,缓存网络的建模和性能优化也因此而成为近期的热门研究领域.本文对近年来国际上在该领域的主要研究成果进行了回顾与总结,分析了ICN缓存网络的新特征带来的挑战,综述了ICN缓存网络中若干主要问题的研究现状,包括缓存大小规划、应用无关的缓存空间共享机制、缓存决策策略、网络内置缓存对象的可用性以及缓存网络的理论模型等,并进行了深入的分析和对比,同时指出可能的设计选择空间.总的来说,对ICN缓存网络的研究处于起步阶段,具有广阔的研究空间,无论在理论模型还是性能优化方法方面都有大量 关键问题需要进行开拓性的探索和深入细致的研究.这些问题的解决和完善,对于规划、设计和运营未来的ICN网络具有重要的理论价值和实践指导意义.

参考文献
[1] Cisco visual networking index: Forecast and methodology: 2012~2017. 2013. http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_c11-481360_ns827_Networking_Solutions_White_Paper.html
[2] Borst S, Gupta V, Walid A. Distributed caching algorithms for content distribution networks. In: Proc. of the IEEE INFOCOM. 2010. 1-9 .
[3] Cheriton DR, Gritter M. TRIAD: A new next-generation Internet architecture. Technical Report, Stanford: Computer Science Department, Stanford University, 2000. http://www-dsg.stanford.edu/triad/triad.ps.gz
[4] Koponen T, Chawla M, Chun BG, Ermolinskiy A, Kim KH, Shenker S, Stoica I. A data-oriented (and beyond) network architecture. In: Proc. of the ACM SIGCOMM. 2007. 181-192 .
[5] Jacobson V, Smetters DK, Thornton JD, Plass MF, Briggs NH, Braynard RL. Networking named content. In: Proc. of the 5th Int’l Conf. on Emerging Networking Experiments and Technologies (CoNEXT 2009). New York: ACM, 2009. 1-12.
[6] Zhang L, Estrin D, Burke J, Jacobson V, Thornton JD, Smetters DK, Zhang BC, Tsndik G, Claffy KC, Krioukov D, Massey D, Papadopoulos C, Abdelzaher T, Wang L, Crowley P, Yeh E. Named data networking (NDN) project. 2010. http://www.named-data.net/techreport/TR001ndn-proj.pdf
[7] Anand A, Dogar F, Han D, Li B, Lim H, Machado M, Wu W, Akella A, Anderson DG, Byers JW. XIA: An architecture for an evolvable and trustworthy Internet. In: Proc. of the 10th ACM Workshop on Hot Topics on Networks (Hotnets 2011). New York: ACM, 2011.
[8] Ahlgren B, D’Ambrosio M, Dannewitz C, et al. Second NetInf architecture description. 4WARD EU FP7 Project, Deliverable D-6.2 v2.0, FP7-ICT-2007-1-216041-4WARD/D-6.2. 2010. http://www.4ward-project.eu/
[9] Ain M, Trossen D, Nikander P, et al. PSIRP D2.3-Architecture definition, component descriptions, and requirements. In: Proc. of the PSIRP 7th FP EU-Funded Project. 2009. http://www.psirp.org/files/Deliverables/FP7-INFSO-ICT-216173-PSIRP-D2.3_ArchitectureDefinition.pdf
[10] Ahlgren B, Dannewitz C, Imbrenda C, Kutscher D, Ohlman B. A survey of information-centric networking. IEEE Communications Magazine, 2012,50(7):26-36 .
[11] Paul S, Pan J, Jain R. Architectures for the future networks and the next generation Internet: A survey. Computer Communications, 2011,34(1):2-42 .
[12] Choi J, Han J, Cho E, et al. A survey on content-oriented networking for efficient content delivery. IEEE Communications Magazine, 2011,49(3):121-127 .
[13] DECADE Working Group. 2010. https://datatracker.ietf.org/wg/decade
[14] Song H, Zhong N, Yang Y, et al. Decoupled application data ENROUTE (DECADE) problem statement. IETF draft: draft-ietf- decade-problem-statement-00.txt. 2010.
[15] Ghodsi A, Koponen T, Rajahalme J, Sarolahti P, Shenker S. Naming in content-oriented architectures. In: Proc. of the ACM SIGCOMM Workshop on Information-Centric Networking (ICN 2011). 2011. 1-6 .
[16] Zhang GQ, Tang MD, Cheng SQ, et al. P2P traffic optimization. Science China Information Sciences, 2012,55(7):1475-1492.
[17] Fricker C, Robert P, Roberts J, Sbihi N. Impact of traffic mix on caching performance in a content-centric network. In: Proc. of the IEEE INFOCOM Workshop on NOMEN. 2012. 310-315 .
[18] Psaras I, Chai WK, Pavlou G. Probabilistic in-network caching for information-centric networks. In: Proc. of the 2nd ICN Workshop on Information-Centric Networking. 2012. 55-60 .
[19] Perino D, Varvello M. A reality check for content centric networking. In: Proc. of the ACM SIGCOMM Workshop on Information- Centric Networking (ICN 2011). 2011. 44-49 .
[20] Wierzbicki A, Leibowitz N, Ripeanu M, et al. Cache replacement policies revisited: The case of P2P traffic. In: Proc. of the 4th Int’l Workshop on Global and Peer-to-Peer Computing (GP2P 2004). Chicago: IEEE, 2004. 182-189.
[21] Hefeeda M, Saleh O. Traffic modeling and proportional partial caching for peer-to-peer systems. IEEE/ACM Trans. on Networking, 2008,16(6):1447-1460 .
[22] Arianfar A, Nikander P. Packet-Level caching for information-centric networking. In: Proc. of the Re-Architecting the Internet Workshop (ReArch 2010). 2010. http://users.piuha.net/blackhawk/contug/cache.pdf
[23] Arianfar S, Nikander P, Ott J. On content-centric router design and Implications. In: Proc. of the Re-Architecting the Internet Workshop (ReArch 2010). New York: ACM, 2010.
[24] Carofiglio G, Gallo M, Muscariello L. Bandwidth and storage sharing performance in information centric networking. In: Proc. of the ACM SIGCOMM Workshop on Information-Centric Networking (ICN 2011). New York: ACM, 2011. 26-31.
[25] Breslau L, Cao P, Fan L, Phillips G, Shenker S. Web caching and Zipf-like distributions: Evidence and implications. In: Proc. of the IEEE INFOCOM’99. 1999. 126-134 .
[26] Rossi D, Rossini G. On sizing CCN content stores by exploiting topological information. In: Proc. of the IEEE INFOCOM Workshop on NOMEN. 2012. 280-285 .
[27] Lu Y, Abdelzaher FT, Saxena A. Design, implementation and evaluation of differentiated caching services. IEEE Trans. on Parallel and Distributed Systems, 2004,15(5):440-452 .
[28] Carofiglio G, Gehlen V, Perino D. Experimental evaluation of memory management in content-centric networking. In: Proc. of the 2011 Int’l Conf. on Communications (ICC). Kyoto, 2011. 1-6 .
[29] Koruolu MR, Dahlin M. Coordinated placement and replacement for large-scale distributed caches. IEEE Trans. on Knowledge and Data Engineering, 2002,14(6):1317-1329 .
[30] Tang X, Chanson ST. Coordinated en-route Web caching. IEEE Trans. on Computers, 2002,51(6):595-607 .
[31] Jiang AX, Bruck J. Optimal content placement for en-route web caching. In: Proc. of the 2nd IEEE Int’l Symp. on Network Computing and Applications. Los Alamitos: IEEE, 2003. 9-16.
[32] Shen H, Xu S. Coordinated en-route Web caching in multi-server networks. IEEE Trans. on Computers, 2009,58(5):605-619.
[33] Tyson G, Kaune S, Miles S, EI-Khatib Y, Mauthe A, Taweel A. A trace-driven analysis of caching in content-centric networks. In: Proc. of the 21st Int’l Conf. on Computer Communications and Networks (ICCCN). 2012. 1-7 .
[34] Li Z, Simon G. Time-Shifted TV in content centric networks: The case for cooperative in-network caching. In: Proc. of the 2011 IEEE Int’l Conf. on Communications (ICC). 2011.1-6 .
[35] Saino L, Psaras I, Pavlou G. Hashing routing schemes for information-centric networking. In: Proc. of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking (ICN 2013). 2013. 27-32 .
[36] Wang S, Bi J, Wu JP. Collaborative caching based on hash-routing for information-centric networking. In: Proc. of the ACM SIGCOMM. 2013. 535-536 .
[37] Rosensweig EJ, Kurose J. Breadcrumbs: Efficient, best-effort content location in cache networks. In: Proc. of the IEEE INFOCOM. 2009. 2631-2635 .
[38] Wang JM, Zhang J, Bensaou B. Intra-AS cooperative caching for content-centric networks. In: Proc. of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking (ICN 2013). 2013. 61-66 .
[39] Laoutaris N, Syntila S, Stavrakakis I. Meta algorithms for hierarchical Web caches. In: Proc. of the 2004 IEEE Int’l Performance, Computing and Communications Conf. 2004. 445-452 .
[40] Laoutaris N, Che H, Stavrakakis I. The LCD interconnection of LRU caches and its analysis. Performance Evaluation, 2006,63(7): 609-634 .
[41] Cho K, Lee M, Park K, Kwon TT, Choi Y, Pack S. WAVE: Popularity-Based and collaborative in-network caching for content- oriented networks. In: Proc. of the IEEE INFOCOM Workshop on NOMEN. 2012 .
[42] Eum S, Nakauchi K, Murata M, Shoji Y, Nishinaga N. CATT: Potential based routing with content caching for ICN. In: Proc. of the 2nd ICN Workshop on Information-Centric Networking. 2012. 49-54.
[43] Li Y, Lin T, Tang H, Sun P. A chunk caching location and searching scheme in content-centric networking. In: Proc. of the 2012 Int’l Conf. on Communications (ICC). IEEE, 2012. 2655-2659.
[44] Ming Z, Xu M, Wang D. Age-Based cooperative caching in information-centric network. In: Proc. of the IEEE INFOCOM Workshop on NOMEN. 2012. 268-273 .
[45] Wong TM, Wilkes J. My cache or yours? Making storage more exclusive. In: Proc. of the General Track of the Annual Conf. on USENIX Annual Technical Conf. Berkeley: USENIX Association, 2002. 161-175.
[46] Podlipnig S, Böszörmenyi L. A survey of Web cache replacement strategies. ACM Computing Surveys, 2003,35(4):374-398 .
[47] Rossi D, Rossini G. Caching performance of content centric networks under multi-path routing (and more). Technical Report, Telecom ParisTech, 2011. http://perso.telecom-paristech.fr/~drossi/paper/rossi11ccn-techrep1.pdf
[48] Che H, Tung Y, Wang Z. Hierarchical Web caching systems: Modeling, design and experimental results. IEEE Journal on Selected Areas in Communications, 2002,20(7):1305-1314 .
[49] Rodriguez P, Spanner C, Biersack EW. Web caching architectures: Hierarchical and distributed caching. In: Proc. of the 4th Int’l Caching Workshop. 1999. http://workshop99.ircache.net/Papers/rodriguez-abstract.html
[50] Rodriguez P, Spanner C, Biersack EW. Analysis of Web caching architectures: Hierarchical and distributed caching. IEEE/ACM Trans. on Networking, 2001,9(4):404-418 .
[51] Wessels D, Claffy K. Application of Internet cache protocol (ICP) version 2. IETF draft: draft-wessels-icp-v2-appl-00, 1997.
[52] Tewari R, Dahlin M, Vin HM. Design considerations for distributed caching on the Internet. In: Proc. of the 19th IEEE Int’l Conf. on Distributed Computing Systems (ICDCS). 1999. 273-284 .
[53] Chawathe Y, Ratnasamy S, Breslau L. Making Gnutella-like P2P systems scalable. In: Proc. of the ACM SIGCOMM 2003. 2003. 407-418 .
[54] Lv Q, Cao P, Cohen E, Li K, Shenker S. Search and replication in unstructured peer-to-peer networks. In: Proc. of the 16th Int’l Conf. on Supercomputing (ICS 2002). 2002. 84-95 .
[55] Yang B, Garcia-Molina H. Efficient search in peer-to-peer networks. In: Proc. of the Int’l Conf. on Distributed Computing Systems (ICDCS). 2002.
[56] Zhu Y, Chen M, Nakao A. Conic: Content-Oriented network with indexed caching. In: Proc. of the IEEE INFOCOM Workshops. 2010. 1-6 .
[57] Tsutsui T, Urabayashi H, Yamamoto M, Rosensweig E, Kurose JF. Performance evaluation of partial deployment of breadcrumbs in content oriented networks. In: Proc. of the 5th Int’l Workshop on the Network of the Future (in Conjunction with ICC). IEEE, 2012. 5828-5832.
[58] Crespo A, Molina HG. Routing indices for peer-to-peer systems. In: Proc. of the Int’l Conf. on Distributed Computing Systems (ICDCS). 2002. 23-32 .
[59] Clarke I, Sandberg O, Wiley B, Hong TW. Freenet: A distributed anonymous information storage and retrieval system. Lecture Notes in Computer Science, 2001,2009:46-66 .
[60] Dan A, Towsley DF. An approximate analysis of the LRU and FIFO buffer replacement schemes. Proc. of the ACM SIGMETRICS, 1990,18(1):143-152 .
[61] Carofiglio G, Gallo M, Muscariello L, Perino D. Modeling data transfer in content-centric networking. In: Proc. of the23rd Int’l Conf. on Teletraffic Congress. San Francisco: ITCP, 2010. 111-118. http://dl.acm.org/citation.cfm?id=2043487
[62] Psaras I, Clegg RG, Landa R, Chai WK, Pavlou G. Modelling and evaluation of CCN-caching trees. In: Proc. of the 10th Int’l IFIP TC 6 Conf. on Networking (Networking 2011). Berlin, Heidelberg: Springer-Verlag, 2011. 78-91.
[63] Ardelius J, Grönvall B, Westberg L, Arvidsson A. On the effects of caching in access aggregation networks. In: Proc. of the 2nd ICN Workshop on Information-Centric Networking (ICN 2012). 2012. 67-72 .
[64] Rosensweig EJ, Kurose J, Towsley D. Approximate models for general cache networks. In: Proc. of the IEEE INFOCOM. 2010. 1-9 .
[65] Rosensweig EJ, Menasche DS, Kurose J. On the steady-state of cache networks. In: Proc. of the IEEE INFOCOM. IEEE, 2012. 863-871.
[66] Alderson D, Li L, Willinger W, Doyle JC. Understanding Internet topology: Principles, models, and validation. IEEE/ACM Trans. on Networking, 2005,13(6):1205-1218 .
[67] Fayazbakhsh SK, Lin Y, Tootoonchian A, et al. Less pain, most of the gain: Incrementally deployable ICN. In: Proc. of the ACM SIGCOMM. 2013 .
[68] Pacifici V, Dán G. Content-Peering dynamics of autonomous caches in a content-centric network. In: Proc. of the IEEE INFOCOM. 2013. 1079-1087 .
[69] Farrell S, Cahill V. Delay- and Disruption-Tolerant Networking. Artech House Publishers, 2006.
[70] Rossini G, Rossi D. A dive into the caching performance of content centric networking. In: Proc. of the IEEE 17th Int’l Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD 2012). 2012 .
[71] DiPalantino D, Johari R. Traffic engineering vs. content distribution: A game theoretic perspective. In: Proc. of the IEEE INFOCOM 2009. 2009. 540-548 .
[72] Liu Y, Zhang H, Gong W, Towsley D. On the interaction between overlay routing and underlay routing. In: Proc. of the IEEE INFOCOM. 2005. 2543-2553 .
[73] Seetharaman S, Ammar M. On the interact ion between dynamic routing in native and overlay layers. In: Proc. of the IEEE INFOCOM. 2006. 1-12 .
[74] Seetharaman S, Hilt V, Hofmann M, Ammar M. Preemptive strategies to improve routing performance of native and overlay layers. In: Proc. of the IEEE INFOCOM. 2007. 463-471 .
[75] Montpetit MJ, Westphal C, Trossen D. Network coding meets information-centric networking: An architectural case for information dispersion through native network coding. In: Proc. of the 1st ACM Workshop on Emerging Name-Oriented Mobile Networking Design-Architecture, Algorithms, and Applications (NoM 2012). 2012. 31-36 .
[76] Wu QH, Li ZY, Xie GG. CodingCache: Multipath-Aware CCN cache with network coding. In: Proc. of the 3rd ACM SIGCOMM Workshop on Information-Centric Networking. 2013. 41-42 .
[77] Magli E, Wang M, Frossard P, Markopoulou A. Network coding meets multimedia: A review. IEEE Trans. on Multimedia, 2013, 15(5):1195-1212 .
[78] Zhang GQ, Cheng SQ, Zhang GQ. LANC: Locality-Aware network coding for better P2P traffic localization. Computer Networks, 2011,55(6):1242-1256 .