协作缓存及数学建模在CCN中的应用

李 伟，潘沛生

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

随着信息量的暴涨，当前网络架构已经不能满足用户的需求，对未来网络架构的研究开始变得愈发重要。近年来，学术界提出的CCN网络，成为未来网络架构领域中值得关注的热点[1]。目前，CCN有两种最基础的缓存策略，分别为处处缓存策略(leave cache everywhere,LCE)[2]和向下拷贝策略(leave copy down,LCD)[3]。这两种策略简单易行，但资源的利用率较低[4]。

为了解决节点之间完全独立的现状，对如何把自治系统的协作策略应用到CCN网络中进行了研究。能够实现自治系统内部各节点之间互相通信，使得节点收到请求之后，能够更加快速智能地选择存储该请求内容的节点，而不是直接使用最短路径优先策略来决定请求转发路线，从而以较少的跳数和较小的延时得到请求内容。对自治系统协作缓存策略(P-ASS)进行定性分析。在实现自治系统集中控制之前，通过将网络划分为自治系统来实现显式协作，减少缓存的冗余，提高缓存利用率和缓存命中率。在此策略下，同一AS中的节点相互合作，实现了CCN的缓存性能的增益。

为了使P-ASS更具普遍性，对P-ASS进行定量计算时，针对任意网络拓扑建立数学模型，而不是仅针对二叉树等几种较为普遍的拓扑图，使得仿真结果更具普遍性。最后计算并比较LCE、LCD及P-ASS的缓存命中率、平均跳数和延时时间，以验证P-ASS的性能。

1 自治系统协作缓存策略

1.1 基本思想

缓存策略对CCN的性能有决定性的影响。在传统的CCN中，数据包沿返回路径被缓存，并且只有传输路径上的缓存可以用于服务响应，缺乏节点之间必要的协作机制，使得系统缓存效率很低。此外，从相邻节点获取内容的成本比从源服务器获取它的成本便宜得多。而提出的协作缓存策略解决了节点之间缺乏有效协作的问题，使得缓存得到了更有效的利用，以达到提高系统缓存效率的目的。

1.2 P-ASS详述

1.2.1 AS的划分

在P-ASS中，缓存系统分为几个由控制节点集中控制的AS，如图1所示。自治系统内仍然使用OSPF协议[5]，利用最短路径优先算法决定请求路径。

图1 任意网络拓扑

1.2.2 控制节点的选择

控制节点的选择决定网络的性能，因此如何选择控制节点变化变得尤为重要。下面介绍一种使用基于节点的中间性和缓存替换率[6]来选择控制节点的方法。

CCN网络的拓扑结构可以表示为无向图G=(V,E)，其中V是CCN节点的集合，E是节点之间的边集。C(v)是与节点v(v∈V)相连接的节点个数。一旦网络建立，就很容易获得C(v)。Cnor(v)是C(v)的归一化，可以通过式1求得。

(1)

关于节点v，被替换的内容ki的大小由S(ki)表示，节点v的缓存大小由Ca(v)表示。m是单位时间内节点v的缓存内容替换次数。Re(v)是节点v的缓存替换率，见式2。

(2)

Re(v)归一化后的值表示为Renor(v)，见式3：

(3)

M(v)表示网络中每个节点作为控制节点的适应度情况，由式4求得。

(4)

1.2.3 流行度计算及对应策略

在P-ASS中，AS的控制节点需要具有计数内容的流行度[7]的能力。使用式5和式6计算每个内容的流行度。

(5)

[0,1]

(6)

其中，i表示请求内容的名称；Ri表示用户在时间段t内请求内容i的次数[8]；I(i∈I)表示时间间隔t期间的所有内容的集合。

实际上，Popu(i)是流行度，但是式6对Popu(i)进行归一化，得出Popularity(i)。Popularity(i)在以后更方便使用。

文中按照内容流行度参数将内容分为三类：高流行度内容、中等流行度内容和低流行度内容。不同类型的内容具有由控制节点确定的不同的缓存策略。如果Popularity(i)>0.5，则内容i是高流行度内容。它需要冗余的缓存来提高缓存命中率，因为许多用户会请求它。图1的内容A就是一个示例。如果0.2< Popularity(i)<0.5，这意味着内容i是中等流行度内容。中等流行度内容是减少冗余的主要部分。在P-ASS中，这些内容在同一AS中仅会被缓存一次，以减少内容缓存冗余。图1中的B是中等流行度内容。如果Popularity(i)<0.2，则内容i被称为低流行度内容。因为低流行度内容被请求的次数太少，容易被替换[9]，如图1中的C，所以它们通常不在AS中缓存。

1.3 AS中的节点详述

1.3.1 AS中各节点的结构

节点结构[10]如图2所示。

图2 CCN节点结构

在AS中有两种类型的节点，分别是控制节点和公共节点。AS中只有一个控制节点，而其他都是公共节点。控制节点的主要作用是控制整合该自治系统所有节点的存储内容，公共节点则定期向控制节点更新自己本地的信息。

下面是两种类型节点的具体作用：

(1)控制节点：除了传统的三个表[11](CS，PIT，FIB)之外，特别地，每个控制节点维护自己的缓存汇总表(CST)。它记录所属AS中各节点缓存的内容信息。每个节点周期性地向控制节点报告其本地缓存信息。控制节点周期性地将自己的CST通告给公共节点。同时，控制节点计算自己已经接收的每个内容的流行度以确定不同内容的缓存策略。

(2)公共节点：除了控制节点之外，AS中的其他节点是公共节点。公共节点保持四个表：CS，PIT，FIB和CST，用于记录内容的名称及其获得的位置。然而，LCST由控制节点发出。当新内容已被缓存时，公共节点向控制节点报告CS的信息。

1.3.2 通信包类型及作用

P-ASS是基于节点之间的相互通信提出的，则节点之间的通信内容也会有所不同。在该策略中定义了六种类型的通信包，供不同的消息类型使用。分别是：兴趣包、数据包、汇报包、更新包、探测包和确认包。

(1)兴趣包：兴趣包由用户发送，用于请求想要的网络资源等。

(2)数据包：数据包是当用户请求在网络中命中时，返回给用户的数据信息。

(3)汇报包：公共节点在更新存储的内容时，会发送汇报包给控制节点，通知控制节点更新汇总表记录。如果一定时间段内没有存储内容的更新，节点会定期发送汇报包，告诉控制节点，该节点还存在。

(4)更新包：控制节点周期性地将自己CST中的汇总信息同步给所属自治系统中的各个公共节点。如果请求在控制节点命中，则控制节点立刻将请求转发给相应的公共节点。

(5)探测包：当公共节点不能在自己的缓存中命中请求内容，则会将请求转发给控制节点，请求自己想要的内容。如果一定时间内，该节点没有收到控制节点的确认包或者数据包，则该节点会向控制节点发送探测包，以确认控制节点是否已收到该节点的请求。

(6)确认包：当控制节点收到请求包时，控制节点在自己的CS，PIT，FIB和CST中查看该内容。如果控制节点从请求该内容的节点处收到探测包，则会发送确认包，告诉该节点请求有没有命中。

1.3.3 基本通信过程

情况1：如果控制节点收到用户请求，首先计算该内容的流行度以确定哪些节点适于缓存该内容，以提高缓存利用率并增加缓存命中率。之后，作为传统的CCN，它应该依次查找CS、PIT、CST、FIB。如果缓存未命中，则控制节点将丢弃兴趣包并发送确认包以通知请求该内容的节点自己处理。

情况2：如果接收机是公共节点，则应当搜索其CS、PIT、LCST作为传统CCN来检查其是否具有内容。如果没有匹配，则公共节点将向控制节点转发兴趣包。然后控制节点将像情况1一样处理。公共节点在将兴趣包转发到控制节点之后等待数据包，如果等待超时，则公共节点将发送消息以确认内容是否命中。如果公共节点接收到控制节点的回复，并且被告知内容未命中，则公共节点将如传统CCN那样检查FIB。

此外，如果兴趣包能够匹配到CST中的内容，则说明内容已被AS中的节点缓存，则会将兴趣包转发到该节点以获得内容。

2 对任意网络拓扑建模

在提出新的缓存策略之后，本节将针对任意网络拓扑结构进行数学建模[12]。将网络的数据传输通过概率论原理，用数学表达式表述。考虑CCN网络的请求聚合能力，建立CCN在一般网络拓扑结构下，基于迭代方法的MMAT传输模型。然后将所列数学表达式进行迭代，直到未知量落入预先设定的误差范围终止。最后得到内容的平均未命中率和时延。在该模型上，先后使用LCE、LCD和P-ASS三种策略进行仿真。使用相同的计算模型，保证仿真数据更可靠，结论更客观。

符号及意义见表1。

表1 符号及意义

两相邻节点vi和vj之间获取的内容k的往返时延是：

(7)

其中，tp为相邻节点的传播时延；tq为请求传输时延；tc为内容传输时延。则节点v按照Pk,v在第j跳节点获取内容ck的往返时延表示为：

Tk,v,j=tv,Pk,v(2)+tPk,v(2),Pk,v(3)+…+tPk,v(j-1),Pk,v(j)

(8)

此时，便可得到VTk,v为Tk,v,j命中概率的加权。

下面对所提建模方案进行详细描述。设G(V,E)为一个CCN网络，将网络中的每个节点看作由CS、PIT、FIB这三个过滤器组成。则具体建模步骤如下：

第一步：节点v收到对内容k的请求率为：

(9)

第二步：计算请求在经过CS后的输出流。根据文献[13]可得请求内容在节点v处的概率为：

(10)

假设请求流服从泊松分布，根据文献[14]可得内容k的请求在节点v处未命中的概率为：

mk,v=Rk,v(1-qk,v)

(12)

第三步：请求通过CS到达PIT之后，PIT过滤被转发之后还未收到回复的请求。则节点v处请求的聚合概率取决于PIT中记录的生存时间T和VTk,v。当数据在CS中的缓存时间远远小于VTk,v时，到达PIT的请求也满足泊松分布，因此节点v请求内容k的聚合概率为：(1-e-mk,vΔk,v)，其中Δk,v=min(T,VTk,v)。

第四步：将式7～12联立,所有节点的CS和fk,v全部清零，然后迭代，直到两次相邻迭代的平均跳数、命中率和平均时延都小于所设定的阈值。

3 仿 真

为了分析P-ASS的性能，使用ccnSim平台[15]进行仿真。仿真网络中设有400个节点，两节点间带宽为20 Mbps,传播时延tp=5×10-4s，内容大小为1 kb。本次性能评估的主要内容是，不同的网络缓存大小对各种策略性能的影响。与CCN中的两种传统缓存策略(LCE、LCD)进行比较，结果如图3～5所示。

图3 命中率随缓存大小的变化

图4 平均往返时延随缓存大小的变化

图5 平均跳数随缓存大小的变化

通过数据对比可以看出，与基本的LCE、LCD策略相比，随着缓存大小的增长，P-ASS在平均跳数、命中率和平均时延三方面的变化更具备优越性。在缓存大小趋于无限大时，三种策略性能参数都趋于稳定，但P-ASS性能最佳。

4 结束语

文中对CCN的两种基本缓存策略进行调研，得出几种策略的不足之处，比如缓存冗余度高，只能沿单一路径请求内容，且节点之间相互独立，缺少必要的协作通信，等等。在此基础上，提出一种基于自治系统协作缓存的策略，使得相邻节点之间可以实现相互通信，比较智能地就近选择合适的节点，获取用户请求的内容，实现以较少的跳数实现内容的命中。三种策略在面向任意拓扑的同一传输模型上进行仿真实验，结果表明，与现有基本策略相比，P-ASS可以得到更好的网络性能参数，优化网络性能。未来网络架构还有很多方面值得研究，例如可以根据当前网络环境及内容存储的位置，更加智能地动态选择控制节点，以实现更好的性能增益，收获更好的用户体验。