和传统的基于网络协议(IP，Internet protocol)的网络体系不同，信息中心网络(ICN，information-centric networks)是一种全新的基于命名数据的通信体系结构^[1]. 近年来，对命名网络的研究取得了不少研究成果，提出了内容中心网络协议. ICN中缓存放置策略的研究已经有不少成果，目前主要的缓存策略有处处缓存(LCE，leave copy everywhere)^[2]、基于相关性概率的信息中心网络协作缓存策略^[3]、基于内容流行度和节点中心度匹配的信息中心网络缓存策略^[4]等. 其中LCE策略作为默认策略，复杂度比较低，但会带来较大缓存冗余，缓存资源得不到充分利用. 度高速缓存(DC，degree cache)策略采用的是选择最大度节点缓存放置策略，Random策略采用的是等概率缓存放置策略. 在路由转发方面，最早做出路由转发和内容发现的是基于开放式最短路径优先的命名数据网络路由协议(OSPFN，an open shortest path first based routing protocol for named data networking)策略^[5]，增加了对内容前缀的支持，并周期性地进行内容发现和路由更新.

为了进一步优化路由转发策略和缓存放置策略，使路由节点能更好地完成报文的转发和内容的缓存工作，笔者提出了一种基于缓存价值的路由转发和缓存放置策略(RCCVI，routing forwarding and cache placement strategy based on cache value in information center network). 该策略引入联盟博弈理论，根据路径时延和繁忙度来衡量下一跳节点缓存价值(CV，cache value)，由夏普利值计算出下一跳转发路由，并根据请求节点设置的Scope参数，结合数据包回传跳数来决定缓存放置. 仿真结果表明，该策略有较高的缓存命中率，与DC策略、Random策略相比较，减少了平均请求跳数；其中DC策略采用的是全转发路由策略和沿途选择最大度节点缓存放置策略，Random策略采用的是全转发路由策略和沿途等概率缓存放置策略.

1 基于夏普利值的缓存价值的转发和放置策略评估与分析 1.1 联盟博弈和夏普利值

在博弈理论中，定义二元组$G\triangleq \langle N,V\rangle $为联盟参与者集合N上的联盟博弈，若v为在N的所有子集形成的2^N集合上的映射，且满足

1) $V\left( \varnothing \right)=0$；

2) 对所有的子集，只要S∩W=$\varnothing $，那么则有V(S∪W)≥V(S)+V(W)，并称相应集合的映射V为特征函数，称N的所有任意非空子集为联盟.

当N给定时，在N上的联盟博弈$\Gamma \triangleq \{V|\left\langle N,V \right\rangle $集合上存在唯一映射$\varphi :\text{ }\Gamma \to {{R}^{N}}$，其中φ=(φ₁,φ₂,…,φ_n)满足有效性、对称性和可加性. 其中，φ_i的表达式为

${{\varphi }_{i}}\left[ V \right]=\sum\limits_{S\subset N}{\frac{\left( \left| S \right|-1 \right)!\left( n-|S| \right)!}{n!}}{{\Delta }_{i}}\left( S \right)$

(1)

其中：${{\nabla }_{i}}\left( S \right)=V\left( S \right)-V\left( S\backslash \{i\} \right)i=1,2,\cdots ,n$.

称映射φ为夏普利值向量映射，并称$\varphi \left[ V \right]=({{\varphi }_{1}}\left[ V \right],{{\varphi }_{2}}\left[ V \right],\ldots ,{{\varphi }_{n}}\left[ V \right])$为合作博弈的夏普利值，其中每一个分量都为一个夏普利值指数. S为博弈〈N,V〉的联盟，|S|为集合S中含有的元素数量.

1.2 缓存价值定义

在定义路由节点缓存价值时，只考虑2个约束因素：路径时延和节点繁忙度，并由这2个因素构造出缓存价值公式. 为了便于表述，节点i使用v_i表示，节点i和j之间的链路用e_ij表示.

1) 路径时延. 从节点v_i到节点v_j的e_ij路径(v_i,v_j)上的时延${{t}_{ij}}=\sum\limits_{{{e}_{ij}}}{{{w}_{ij}}~}$，其中w_ij为转发到链路e_ij的内容请求时延. 路径时延会潜在地考虑缓存因素，平均缓存命中率越高，平均时延越小.

2) 节点繁忙度. 节点v_i的繁忙度b_i=p_i/h_i，p_i为单位时间内才到达节点的数据量，h_i为节点v_i的吞吐量. 该指标主要考虑路由节点负载.

节点v_i决定缓存在节点v_j获得的收益为

${{p}_{ij}}=({{b}_{0}}-{{b}_{j}}~)({{t}_{0}}-{{t}_{ij}})\text{ }$

(2)

其中：b₀为请求节点允许的最大繁忙度，t₀为请求节点允许的最大延迟.

显然，期望收益p_ij满足如下性质：

1) 节点v_i到v_j的路径时延越小，节点v_i获得的收益越大；反之亦然.

2) 节点v_j的繁忙度越低，则v_i收益越高；反之亦然.

联盟的定义：网络中一个联盟${{S}_{ij}}=\{{{v}_{j}}|{{e}_{ij}}~|\le 1\}$. 其中，v_i为当前请求节点，v_j为v_i的相邻节点.

特征函数定义：V(S)为联盟参与者形成局部联盟的表征. V(S)由p_ij决定，p_ij越大，则缓存的权值越大. 最终用于计算转发概率的夏普利值则是将式(3)代入式(1)中计算所得.

$V\left( S \right)=\sum\limits_{j\in S}{{{p}_{ij}}}$

(3)

综合1.1节和1.2节所述，参考OSPFN策略设计思想，该转发策略需要周期地采集下一跳路由节点的繁忙度和路径时延，并选择1条或多条路径，进行转发.

1.3 缓存放置策略设计

笔者设计依托转发策略，设计如下的缓存放置策略：在缓存未命中情况下，内容源根据请求包的生存时间(TTL，time-to-live)字段确定.

具体策略为

$\begin{align} & D=T-C \\ & P\left( i \right)=1,D=0 \\ & P\left( i \right)=0,\text{else} \\ \end{align}$

(4)

其中：P(i)为节点i是否缓存副本，P(i)=1表示该路由节点缓存副本的概率为1；P(i)=0表示该路由节点缓存副本的概率为0. D为数据包中的DFlag字段，该字段是笔者添加的，D值为TTL字段T与Scope字段C的差，C值为策略给定；由Scope字段可知，当C→T时，该缓存放置策略即非全转发下的LCE策略；当C→0时，该缓存放置策略即noCache策略.

2 RCCVI策略设计

RCCVI策略从路由状态信息出发，建立基于夏普利值的路由转发和缓存放置策略，旨在增加缓存命中率，减少平均跳数. 笔者将RCCVI、LCE、Random和DC策略进行比较.

2.1 主要改进

主要工作如下.

1) 周期探测，获取下一跳路由节点的节点繁忙度和路径时延，计算缓存价值，更新缓存价值表(CVT，cache value table)，以便于转发.

2) 在距离请求节点的路由跳数小于等于Scope的节点中，缓存内容副本. 通过修改请求包和数据包中的标记，最终实现在缓存价值高的路径的节点上有选择地缓存数据.

为了完成上述2方面的工作，RCCVI策略在内容存储库(CS，content store)、待定信息表(PIT，pending interest table)和转发信息表(FIB，forwarding information base)的基础上，进行修改，并增加了CVT，用于保存下一跳路由节点的缓存价值信息. CVT主要内容如表 1所示.

CVT保存了转发的内容前缀、接口号、缓存价值和时间戳. 通过前缀匹配决定转发接口，一个前缀可能有多个接口能与之匹配，匹配到的每个接口都有一个缓存价值，此价值用于确定转发路径. 同时，在时间戳中记录此表行项和更新时间.

2.2 报文设计

为了方便实现2.1节工作，笔者策略需要在报文上添加新字段.

在探测阶段，保留原有ICN报文字段的基础上主要添加了Scope、IFlag和DFlag字段，设计的报文具体如图 1所示.

在2类报文中都包含Type、Prefix和TimeStamp字段，分别代表报文的类型、内容前缀和时间戳. TimeStamp用于判断当前包的时效性. 在请求包中Scope代表缓存放置的范围，若为0则不缓存，否则缓存放置在距离请求节点Scope的范围内；在数据包中Length用于记录数据的长度，Data用于放置数据.

Scope和DFlag为配合完成在指定节点缓存的2个字段. 在转发数据包时，内容源节点构造数据包，根据TTL和Scope修改数据包中DFlag字段；途经节点判断DFlag后，作减1处理，直到DFlag减小到0，此后节点缓存副本. IFlag记录请求包发出的时间，会随数据包返回，用于探测阶段统计路径时延. 具体请求和缓存的详细描述如图 2所示.

3 仿真分析

为了分析笔者提出的路由转发和缓存放置策略的性能，下面将主要从2个角度进行分析，缓存命中率和平均请求跳数，并讨论Scope的值对上述指标的影响.

3.1 拓扑环境

采用文献[6]方法仿真环境模拟RCCVI策略. 在仿真中添加了报文结构，编写路由转发策略代码，根据不同的标记作相应的收发处理. 在仿真中，网络拓扑采用深度为4的满四叉树. 其中，满四叉树的根节点做生产者，消费者则和叶子节点直接相连，每个叶子节点可连接多个消费者，该仿真中叶子节点连接消费者数目为1～6不等，而消费者只连接1个路由节点，且消费者之间不直接连接. 设置网络请求块的数目为Q=10 000. 为了计算跳数和时延的关系，设置直接相连的路由节点之间的延迟为1~3 ms，带宽为10 Mbit/s，仿真时间为100 s. 在仿真中，客户端节点发送的Interest报文满足分布，数据流类型为固定码率(CBR，constant bit rate)，且设置每秒请求内容数为100，频率为100. 设定路由节点的缓存表的大小为100，即路由能缓存100个内容. 缓存表的缓存替换策略为近期最少使用算法(LRU，least recently used).

3.2 仿真结果

1) 在实验1中，给出RCCVI策略，在不同深度节点的缓存命中率，图 3中的不同线表示不同的深度，深度1、2、3、4依次位于从叶子节点到根节点的不同层上，横轴表示Scope参数的范围，纵轴表示平均缓存命中率. 如图 3所示，考虑到拓扑结构，Scope的范围设置在0～6之间，随着Scope值的增加，不同深度节点的缓存命中率变化明显. 在ICN网络中，中间路由节点缓存命中率的提高，在一定程度上对请求时延的减少有帮助，也会减少网络中请求包和数据包的数量. 但抛开具体拓扑而言，若综合考虑Scope对缓存范围和缓存命中情况，Scope可考虑2或3，因为在没有大幅减小部分消费者的网络请求缓存命中率的情况下，2缩小了缓存的范围，在一定程度上会减小近数据源节点缓存换出的频率，这有利于近数据源节点服务其他消费者.

2) 实验2给出了在整个仿真时间下RCCVI、LCE、DC和Random缓存放置策略的请求平均跳数，在实验2中，RCCVI的Scope值设置为3，如图 4所示，在仿真中，Random、DC和RCCVI策略比较接近，但没有RCCVI策略优. RCCVI策略在缓存放置方面，考虑到缓存放置范围，比LCE减少缓存冗余和缓存替换频率的平均请求跳数更少；与DC和Random策略比较，RCCVI策略能保证缓存副本数量，尽可能地将缓存放置在距离请求节点较近的路由节点上，确定性更好；由图 4可以看出，DC、Random和RCCVI策略相差不大，但RCCVI策略更优，主要原因为RCCVI策略优化了转发策略，引入联盟博弈理论，选择更优的链路去转发. 值得说明的是，笔者仅考虑了有限的缓存大小情况，没有证明缓存无限大的情景，但DC策略会在缓存大小趋于无限情况下获得更佳的效果^[7]，RCCVI策略将内容副本缓存在边缘，相信在缓存容量大小趋于无穷的情况下，平均请求跳数也十分理想.

4 结束语

从路由转发和缓存放置策略出发，设计了ICN中的一种基于缓存价值的路由转发和缓存放置策略. 该策略在LCE策略的基础上，引入夏普利值合作博弈理论，并根据路由信息作出相应的路由转发和缓存放置决策. 经过实验表明，该策略能充分利用ICN中路由节点的缓存能力，使整个网络有效缓存内容的数量增加，同时在平均请求跳数和缓存命中率上能保持较好的效果.

未来的研究工作包括请求节点根据请求内容自定义Scope参数的值，使缓存副本的数量和请求的内容数目或重要性有更多的关系，从而达到不同级别的内容有不同缓存放置范围的效果，最终能使网络性能更佳，用户体验更好；未来的研究还包括增加指标后对夏普利值时间复杂性和转发效率的影响.