2. 北京邮电大学 网络体系架构与融合北京市重点实验室, 北京 100876
信息中心网络(ICN)的节点缓存功能有助于海量内容的高效分发, 缓解链路拥塞并减少流量冗余.传统的缓存策略不利于提高全网缓存的内容多样性和缓存节点的平均命中率, 现有研究能在一定程度上解决这些问题, 实现了公平的内容流复用, 但没有充分考虑节点之间的协作, 导致节点缓存的利用率不均.为了解决上述问题, 从当前节点缓存状态对其他节点的影响入手, 提出一种基于相关性概率的ICN协作缓存策略, 根据路径及相邻节点信息做出本节点的缓存判断, 从而有效控制缓存冗余.仿真结果表明, 该方法可以减轻服务器负载, 丰富全网内容多样性, 有利于提高交错复杂网络节点的命中率和利用率, 减少请求跳数.
2. Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China
The in-network caching of information centric networking (ICN) can offer help to the massive contents distributions efficiently, the ease link congestion and the traffic redundancy reductions. Traditional caching policies are not conducive to raise content diversity of the whole network and average hit rate of cache nodes. The existing research can solve the problems to some extent, and achieve fair content flow multiplexing, however, almost no consideration of collaboration between nodes is adopted, which directly results in uneven utilization of cache nodes. To solve these problems, study on influence of caching status between neighbor nodes was made, and a cooperative caching strategy based on correlation probability in ICN was presented. Cache node will make caching decision based on the information of path and its neighbor node, so it can control the caching redundancy. Simulation shows that this method can ease the server load, and enrich the content diversity of the whole network. It is of benefit to improve the hit rate of nodes in complex network, and reduce the number of hops.
今天互联网的使用主要是内容的产生和消耗，且用户仅关心内容本身而不是内容源的位置.传统的端到端通信网络已经不能很好地满足这种海量数据内容的请求和分发.因此，业内学者对未来网络展开了研究，其中一种有前景的网络架构信息中心网络(ICN，information centric networking)的核心思想是以用户和应用需要的内容为中心，改变传统网络协议(IP，Internet protocol)双重语义，定义新的协议栈和包格式，且路由器节点具有缓存功能.
ICN的节点缓存功能不但能减轻内容服务器的负载压力，还能减少用户请求跳数，极大提高用户的服务质量和体验质量以及网络资源的利用率和能源效率[1].关于缓存的设计，包括硬件方面的缓存大小和存取速度等性能因素；还包括缓存策略方面的“怎么存、存在哪里、存什么内容”的设计，利于改善和提升系统的整体性能.
Jacobson等[2]提出在回传路径的每个节点缓存返回的内容，虽易实现，但缓存冗余严重，缓存节点平均命中率低等导致不必要的开销且缓存系统效率低[3]. Chai等[4]考虑了全网的静态信息(如拓扑连接、网络规模)，选择最重要的节点来缓存内容, 一定程度上减少全网缓存替除率并增加平均命中率，但增加了重要节点的负担. Psaras等[5]考虑网络状况的实际变化情况设计概率缓存内容，减少缓存冗余并实现路径的公平复用，但仅考虑单个节点的缓存概率，故节点利用率不均且系统缓存冗余得不到有效消除.
为了进一步改善缓存策略效率，提升分布式存储系统性能，提出了基于相关性概率的协作缓存策略，根据路径和相邻节点以及节点本身的信息，为每个节点计算一个动态的缓存概率，前一个节点若缓存某一内容则后一个节点缓存该内容的概率减小，反之亦然，同时通过Matlab仿真验证该方案在减少缓存冗余和提高内容分发性能方面的优势.
1 系统模型描述假设拓扑如图 1所示，一个内容源服务器Server和一个终端Client之间连接有N个路由器Ri(i=1, 2, …, N).每个Ri的缓存大小为Si，则从Client到Server的这条路径上的总缓存容量为
|
图 1 系统模型示意图 |
|
表 1 模型符号注释表 |
根据分布式ICN的通信协议设计，Client发送的兴趣包(Interest Packet)的Header中包含Hup字段，表示Interest Packet经过的跳数，它在Interest Packet请求的路径上随着路由器节点跳数的增加而逐一增加；而回传路径上的数据包(Data Packet)的Header中包含3组值〈Li, yi, Xi〉，文中Source指存有请求内容的节点(Server或Ri).
2 基于相关性概率的ICN协作缓存策略网内缓存是为了有效地减少流量冗余，而在网络中的不同位置缓存内容会导致缓存冗余，因此内容放置采用怎样的缓存策略成为研究重点.
此策略从内容副本在传输路径上应该缓存多少、缓存在哪里、缓存决定的相关性等几个角度出发.首先考虑路径缓存容量，评估一条路径能缓存副本的能力，即能缓存多少内容副本，则路径越长，缓存副本的数量越多，从而保证内容在路径上命中的可靠性. Client发出的Interest Packet记录Hup值并标记在Header中.获取到内容后，Source生成的Data Packet Header标记3组值〈Li, yi, Xi〉，分别用式(1)~式(3) 表示.对于Server而言，P0=1(Server存储该请求内容的概率必为1)，〈L0, y0, X0〉=〈5, 0, 1〉.
|
(1) |
|
(2) |
|
(3) |
由于Ri的缓存可以采用同构部署(所有Si相同)也可以采用异构部署(所有Si不等)，因此设置一个因子C描述内容回传路径中正在处理数据包的节点及之后将经过节点的总缓存容量相对于Source到Client之间路由器的总缓存容量的剩余能力，剩余能力越大则缓存概率越大，表示为
|
(4) |
研究结果表明，内容越靠近用户端缓存越不容易被替换出去，因此设计另一个权重因子W，用来决定内容缓存在哪里，使得越靠近用户端的路由器缓存内容的概率越大，如式(5) 所示.但是考虑到路径的公平复用问题，即源端方向的路径可以有部分路径被其他Client公用，所以策略设计时综合考虑了C(随着i增大而减小)和W(随着i增大而增大)2个因子，从而保证内容存在路径中间节点的概率最大，确保共用一段路径的一条长路径和一条短路径可以公平地使用共有路径，即共有路径尽量留给较短的路径用于缓存内容.
|
(5) |
为了进一步加强节点间的协作，增强节点之间缓存决定的相关性，设计了第3个相关性影响因子F.如果对于某内容Xi-1=0，则节点Ri缓存该内容的概率Pi增大，即节点Ri-1的内容缓存概率Pi-1将对节点Ri的内容缓存概率Pi起到正反馈的作用；反之Xi-1=1，则节点Ri缓存该内容的概率Pi减小，即节点Ri-1的内容缓存概率Pi-1将对节点Ri的内容缓存概率Pi起到负反馈的作用，表示为
|
(6) |
综合考虑以上3个因子，设计了式(7) 来计算节点缓存内容的概率.虽然邻居节点之间进行简单的信息交互会带来一定的通信开销，但是可以使路径所有节点的缓存概率曲线存在多个分散的峰值，从而降低缓存节点替换率，提高节点的利用率，保证全网缓存内容的丰富多样，满足请求在缓存节点命中的可靠性和有效性.
|
(7) |
ICN相比传统的边缘网络缓存，进一步将缓存部署在了骨干网中，带来3个明显的效果：1) 通常情况用户要通过骨干网到远端Server获取内容，因此在网内缓存内容，可以明显减少内容分发的延迟；2) 相比传统TCP/IP网络大量内容请求都只能在Server命中，这种普遍存在的网内缓存减轻了服务器负载；3) 减少内容传输链路数量，降低不同用户对相同内容请求的重复流量及网络拥塞.因此设置2个性能评价参数：a)服务器命中率(Server-Hit)，描述网络中所有用户的请求在Server命中的数目比例；b)归一化的内容命中平均跳数Hratio，表征内容命中需要经过几跳的归一化值，如式(8) 所示，其中i表示用户j发出的请求，Hj(i)表示用户j发送请求i到达Server所需跳数，hj(i)表示用户j发送请求i到达Source所经历的跳数，对于非缓存网络或者缓存没有在路由器节点命中，则有hj(i)=Hj(i),
|
(8) |
基于相关性概率的协作缓存策略(correlation)旨在减少网内缓存冗余，降低缓存替除率，提高网内缓存内容多样性，使网络中每个节点的缓存都被充分利用；故仿真中还增加了另外2个性能评价参数：c)网内缓存的内容种类数(Content-Population)，用于统计稳定状态下全网路由器缓存不同内容的数目，评价内容多样性指标；d)节点命中率(Node-Hit)，统计稳定状态下全网缓存节点对不同用户内容请求的命中次数，表征全网缓存节点的利用率.
通过Matlab仿真软件模拟ICN通信模式，其中缓存替换策略仍然采用经典的最近最少使用算法，综合考虑用户请求的内容种类数与节点数目和路由器节点缓存大小满足合适的关系，使用7个节点的线型拓扑，其中1个服务器Server，1个用户Client，另外5个为具有内容中心网络协议栈的路由器节点Router.生成的内容请求服从Zipf分布
如图 2所示，采用不加选择的缓存(CEE，cache everything everywhere)、P(0.3)、P(0.7)、Random 4种策略获取的Server-Hit均随节点缓存大小的增大而平滑减小，由于CEE使得回传路径的全部节点都缓存内容，节点利用率低且替换频繁，网内内容多样性差，故较后3种策略性能略差.而correlation算法随着缓存大小的增大，其Server-Hit相比其他策略明显下降，能有效减轻服务器的压力.由于仿真采用基本的线型拓扑且节点数量有限，当缓存较小时，有选择缓存数量有限，故correlation策略在0.02的情况下性能优势较小，而ProbCache策略只在路径中间缓存概率稍大，从而导致缓存数量更有限，故性能不优.但是随着网络规模的扩大，则可以进一步突出correlation策略的性能优势.在图中0.2的情况下，correlation策略中10万种请求只有7 000多个请求是直接在Server命中的，其他请求均在网络中的Router命中.
|
图 2 服务器命中率性能 |
如图 3所示，通常CEE策略使节点命中率主要集中在靠近用户端的缓存节点，而其他缓存节点的命中率相对较小，大部分内容命中在Server端，故其Hratio虽然和P(0.3)、P(0.7)、Random相似，但随着缓存大小的增大其性能稍差. ProbCache算法的节点命中率则主要集中在路径的中间节点.由于correlation策略考虑了相邻节点存与不存互相之间的影响，其节点命中率会是路径中的任一节点，当全网缓存大小有限时，CEE在第一跳缓存节点的命中率会很高，而correlation策略在每个缓存节点都有一定的命中率，因此相对来说请求跳数稍多.而当全网缓存充足时，correlation策略的Hop-Ratio有突出的优势，也就是说在实际复杂交错的网络中，多条请求路径一定会存在交点或公共路径，它可以在有效提高节点命中率的同时减少请求跳数.
|
图 3 归一化的内容命中平均跳数性能 |
尽管硬件存储能力在不断提升，而价格在不断降低，但考虑到目前网络的发展情况，硬件的发展速度远远赶不上内容的增长速度.因此为了更符合实际状况，选择节点缓存大小/用户请求的内容种类数为0.05(其他条件不变)时统计Content-Population，如图 4所示.可以看出，correlation策略在保证全网内容多样性方面明显优于其他策略，因此在实际部署中能保证网内包含更加多样的内容，进一步减少用户在Server请求内容，增强骨干网中缓存资源的利用率.
|
图 4 当节点缓存大小/用户请求的内容种类数为0.05时，不同缓存策略下网络中的内容多样性 |
为了更进一步说明各策略在每个节点的命中率，仿真统计了当节点缓存大小/用户请求的内容种类数为0.05时，不同缓存策略下的Node-Hit，如图 5所示. correlation策略使每个节点的缓存命中率都很平均，ProbCache算法除第一个节点外在中间节点也有一定的命中率，而其他算法都是基本只在第一跳和Server有命中率，CEE最明显.对于复杂交错的网络，correlation策略有明显优势，由于节点间相关性的影响，使得一条路径中所有节点都各自缓存不同内容，故很多来自其他路径的请求都可以直接在这些中间节点命中.
|
图 5 当节点缓存大小/用户请求的内容种类数为0.05时，不同缓存策略下的节点命中率 |
虽然硬件缓存发展迅速，目前可以以很便宜的价格获得存储容量很大的缓存，但是随着网络用户的不断增加，硬件的大小还是不能满足海量内容的增长速度.因此如何减少缓存冗余，高效利用网络的缓存资源是本研究的主要问题.为了解决上述问题，提出了基于相关性概率的ICN协作缓存策略，每条内容回传路径中所有节点都根据计算的概率决定是否缓存该内容，该概率不仅考虑了路径的存储能力，平衡了多条路径共有路径的公平复用，还考虑了相邻节点之间是否缓存的相互影响，相邻一跳距离的两个节点，前一个节点缓存了内容，则后一节点没必要一定缓存该内容，节省的存储空间可以留给其他内容的缓存.仿真结果表明，该策略极大地提高了每个节点的平均命中率，丰富了骨干网中内容的多样性，有效地降低了服务器命中率，减少了缓存替除率，消除网络中流量冗余的同时还减少了内容冗余，更加有利于内容的高效分发.
| [1] | Llorca J, Tulino A M, Guan K, et al. Dynamic in-network caching for energy efficient content delivery[C]//INFOCOM, 2013 Proceedings IEEE. Turin: IEEE, 2013: 245-249. |
| [2] | Jacobson V, Smetters D K, Thornton J D, et al. Networking named content[J].Communications of the ACM, 2012, 55(1): 117–124. doi: 10.1145/2063176 |
| [3] | Wang J M, Zhang Jun, Bensaou B. Intra-AS cooperative caching for content-centric networks[C]//Proceedings of the 3rd ACM SIGCOMM Workshop on Information-centric Networking. NY, USA: ACM, 2013: 61-66. |
| [4] | Chai W K, He Diliang, Psaras I, et al. Cache "less for more" in information-centric networks[C]//IFIP 12 Proceedings of the 11th International IFIP TC 6 Conference on Networking. Berlin, Heidelberg: Springer-Verlag, 2012: 27-40. |
| [5] | Psaras I, Chai W K, Pavlou G. Probabilistic in-network caching for information-centric networks[C]//Proceedings of the Second Edition of the ICN Workshop on Information-centric Networking. NY, USA: ACM, 2012: 55-60. |