传统的缓存针对单一的流量类型,通常以专用封闭系统的形式而存在,如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对象空间规模较小,在10⁵级别(受限于人类电影/电视剧制作的速度,全球VoD的数量级在可预计的未来不会发生突变),但每个对象都较大.流量类型所呈现出来的这种高度异构性对传统的单一、封闭的缓存系统提出了挑战,要求 ICN应能在不同的应用类型之间有效地共享缓存资源,实现预期的缓存目标.

· 缓存的线速执行要求

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

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

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

传统的缓存一般以文件或文件的可变段为单元进行对象的存储和替换等操作^{[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为单位进行缓存,也使得某些基于文件对象大小的缓存替换算法不再适用.

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

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

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

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

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

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

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

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

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

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

图2

Fig. 2

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

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

(2) 动态共享

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

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

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

显式协同机制需要以访问模式、缓存结构和每个缓存节点的状态为基础,通过复杂的计算确定对象的放置.参与显式协同的缓存节点的范围可以不一,一般可以分为全局协同、路径协同、邻域协同这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]也提出了一种邻域范围内进行缓存协同的方法,该方法并不是在对象到达时进行协同,而是运行一个降低邻域范围内缓存冗余的后台程序,当某个事件发生(如邻域范围的冗余度超过某个阈值)或定期地清理邻域范围内的冗余缓存对象.

图3

Fig. 3

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

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

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

层次化缓存是隐式缓存的一个例子.这种特殊的网络结构使得边缘网络节点能够识别流行度高的请求,从而将流行度高的内容对象缓存在边缘网络节点.而由于过滤效果(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]:一种基于加权概率的缓存机制.返回路径中的沿途节点缓存对象的概率与节点和请求者之间的距离成反比.该方法旨在提高内容在距离请求者更近的节点被缓存的概率,快速地将对象复制到距离请求者更近的网络边缘,提升共享路径节点的效用.但是,由于未考虑复制对象的访问频率,会增加不同对象在边缘缓存节点的竞争.

图4

Fig. 4

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

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

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

图5

Fig. 5

Fig.5 Illustration of how WAVE works 图5 WAVE的工作方式示意图

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

表1(Table 1)

Table 1 Comparison between different cache decision policies 表1 不同的缓存决策策略比较 协同方式 决策时机 决策依据 是否具备关联性 缓存冗余度 对象复制到边缘的速度 LCE 无协同 对象返回时 无 否 高 快 CERC[30, 31] 路径显式协同 对象返回时 缓存收益 否 低 快 CINC[34] 邻域显式协同 对象返回时 Chunk标识 否 低 快 LCD[39, 40] 隐式协同 对象返回时 对象流行度 否 中 慢 MCD[39, 40] 隐式协同 对象返回时 对象流行度 否 低 慢 Prob[39] 隐式协同 对象返回时 随机决策 否 与概率p有关 与概率p有关 RCOne[42] 隐式协同 对象返回时 随机决策 否 低 慢 ProbCache[18] 隐式协同 对象返回时 缓存节点与 请求点的距离 否 中 快 CLS[43] 隐式协同 对象返回 和替换时 对象流行度 否 低 慢 Demote[45] 隐式协同 对象返回 和替换时 对象流行度 否 低 慢 WAVE[41] 隐式协同 对象返回时 对象流行度 是 中 慢

Table 1 Comparison between different cache decision policies 表1 不同的缓存决策策略比较

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

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

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

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

解决上述矛盾的一种方案是让网络内置缓存中存储的非持久性对象在网络中的局部可见,从而在可用性和可扩展性之间获得有效的折中,这也是目前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,NID_from,NID_to,T_pass,T_req)来记录相关信息.其中, FID是对象全局唯一的标识,NID_from表示对象到达的上游节点ID,NID_to表示对象转发的下游节点ID,T_pass表示对象最近经过该节点的时刻,T_req表示节点最近收到该对象请求的时刻.当一个新的请求到达时,如果缓存命中,则直接返回该对象;如果缓存未命中,则依据轨迹信息决定是将查询沿着某条轨迹向下游转发,还是沿着原来的方向向对象的源节点转发.如果沿着轨迹转发导致查询失败,则节点仍会把请求发往源节点.因此,路由建议只是作为一种优化措施,该方法因此被称为尽力而为的内容查找(best effort content search,简称BECONS). Breadcrumb提出了可以将请求沿着轨迹信息向下游节点转发 的两条准则.假设t时刻查询q_f到达缓存节点C,

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

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

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

CATT提出了一种基于势的内容路由(potential based routing,简称PBR),需要事先通过控制层面的信息扩散建立路由表.对于给定的文件c,给定的节点n,给定的缓存有c的节点n_c,定义了n受到n_c的势能影响.势的取值与n到n_c之间的距离成反比,而与缓存文件的质量成正比.这里,质量可以解释为n_c的带宽和处理能力等.节点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所示),当对某个对象的请求无法由本地缓存满足时,依据路由建议表或索引表转发请求,使得网络内对该请求可用缓存对象得到响应请求的机会.

图6

Fig. 6

Fig.6 Original and enhanced CCN forwarding engine图6 原始的CCN转发引擎和改进的CCN转发引擎

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

表2(Table 2)

Table 2 Comparison of content availability between different cache schemes 表2 不同的缓存网络方案中网络内置缓存对象的可用性比较 网络内置缓存 对象的可见范围 对象查询策略 可用性 需额外存储信息量 DONA[4] 仅节点可见 沿路查询 路径可用 无 CCN[5] 仅节点可见 沿路查询 路径可用 无 CERC[30, 31] 仅节点可见 沿路查询 路径可用 无 CONIC[56] 邻域节点可见 依据CONIC路由器的 对象索引表转发查询 局部可用 邻域节点的对象索引表 CINC[34] 邻域节点可见 基于Hash函数转发查询 局部可用 邻域节点标号 RI[58] 全局可见 依据基于语义的 路由建议表转发查询 全局可用 基于语义的路由建议表, 大小与语义类别数成正比 Freenet [59] 部分节点可见 依据历史转发信息建立的对象 与源节点的映射表转发查询; 若失败,则基于最陡梯度爬山法 选择邻居转发查询 局部可用 对象标识与节点标识的映射 信息以及邻居节点的标识信息 Breadcrumb[37] 部分节点可见 依据历史转发信息建立的 路由建议表向下游转发 局部可用 某个时间段经过该节点的 对象构成的五元组集合 CATT[42] 邻域可见 依据势场差转发 局部可用 每个对象的势场值, 与对象个数成正比

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

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

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

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

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

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

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

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

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