基于负载状态的ICN 缓存替换算法研究

曾 理，倪 宏，韩 锐

（1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190；2.中国科学院大学，北京 100049）

泛在化缓存[1]决定了ICN（Information Centric Networking，信息中心网络）的性能优势，其可有效减少冗余数据的传输，缓解网络带宽的压力，降低传输时延[2]。缓存替换在ICN 路由器内部时刻都在发生，每一次替换过程都会对网络性能产生影响[3]。目前，ICN 缓存替换算法的研究集中在对内容未来流行度的预测[4-6]，或是根据拓扑信息和邻居节点缓存信息来优化缓存空间[7-9]，但这些研究在带来额外计算开销或控制开销的同时，相较于传统LRU（Least Recently Used,最近最少使用）替换算法，其性能并未得到明显改善[10]。

随着节点缓存容量和计算能力的限制被打破[11]，不同类型的流量竞争有限的带宽资源已成为ICN 路由器发生拥塞的主要原因之一[12]。针对这一问题，为了避免节点因高缓存命中率引发严重带宽竞争，该文提出一种基于节点负载状态的缓存替换算法，监测节点是否长期处于带宽竞争状态，并采用自适应替换窗口将一些较为流行的内容主动替换，减少带宽竞争的发生频率和持续时间，降低节点丢包率。

1 ICN路由器的带宽竞争

文献[12]认为ICN 中拥塞发生的原因除缓冲区溢出外，还可以进一步归纳为过度的带宽资源竞争。具体来说，假设请求报文以速率γ抵达路由器，τc是缓存服务所需的吞吐量(γ≤τc)，而对于ICN 路由器的实时转发吞吐量τf，某时刻很有可能出现来自外部流量的转发吞吐量与来自内部流量的缓存服务吞吐量之和大于端口带宽B，从而造成拥塞丢包，即τf+τc＞B。ICN 中每个数据报文都需要通过一个请求报文“拉”给用户[13]，因此可以通过来预测带宽竞争的发生（是数据报文的平均尺寸）。

2 算法设计与建模

2.1 算法设计

如果ICN 路由器在一段时间内持续处于带宽竞争状态，则可以认为节点应该主动替换一些流行度较高的内容，从而减少带宽竞争发生的频率和持续的时间。

节点带宽竞争状态随网络波动而动态变化，为了准确加以检测，算法采用时间间隔为T的开关信号对其进行采样。如图1 所示，如果采样时刻节点带宽竞争发生且请求到达速率高于阈值，则用1表示；如果采样时路由器尚有空闲的带宽，则用0 表示。由于固定时间窗偏移的方法容易忽视抽样信号前后窗口的相关性而造成误判，算法采用长度为W的滑动时间窗口（如图中W1,W2,…,Wn）来跟踪统计离散时间下的节点状态，W的值根据RTT（Round-Trip Time，往返时延）、路由器排队时延来决定。如果时间窗内带宽竞争出现次数大于，算法则判断节点处于持续的带宽竞争。滑动窗口监测考虑了请求报文之间的相关性，能够做出更精准的判断，但代价是增加了管理开销。

图1 基于滑动窗口抽样检测带宽竞争

对于内容流行度的评估，在最新的研究中，无论是通过多元线性回归方法[14]，还是通过数据块间的相关性[15]对内容未来请求规律进行预测，文献[10]都已经证明基于流行度的替换算法相比起LRU 替换算法的性能提升并不明显。因此所提算法仍使用LRU队列来筛选流行内容。

当检测到带宽竞争持续发生时，算法通过变长窗口替换队列首部的热门数据，这在一定程度上解决了LRU 时间新近性的问题。考虑到现实路由器中有多个端口，为了更精准地替换导致节点拥塞的数据块，算法将记录每个数据块被请求次数和请求报文到达端口的映射，当某个端口Bp被检测到带宽竞争持续发生，变长窗口仅会替换请求曾从该端口抵达的数据。如图2 所示，若端口1 持续发生带宽竞争，LRU 队列上仅第2、3、5、6 的数据被替换，第1 和4数据块的请求因未曾抵达过端口1 而被保留。假设替换窗口长度用L表示，当检测到带宽竞争发生时，替换窗口增加固定值a。当带宽竞争状态持续了Q个检测窗口，替换窗口将会成倍增长。a与Q的取值由路由器缓存容量（LRU 队列长度）来决定。

图2 可变窗口选择热门数据

2.2 替换窗口长度变化规则建模

基于带宽竞争监测的替换算法中，替换窗口长度变化的行为可以用一个离散马尔科夫过程来建模。

如图3 所示，S0代表窗口长度为0 的初始状态，此时不需要主动对流行内容进行替换；当监测到带宽竞争持续发生时，替换窗口长度将会增加固定值a并处于S1态；S2态代表带宽竞争状态持续了Q个时间窗口以上，窗口长度将会翻倍。因此可以看出，带宽竞争状态持续时间对于各状态之间的转换起着至关重要的作用。为了清晰地表达转移概率，首先定义函数f如式（1）所示：

图3 可变窗口的马尔科夫建模

因此，可以得到如式（2）的状态概率转移矩阵：

其中，p(n)是n时刻路由器抽样检测到带宽持续竞争的概率。

替换窗口变化过程可通过式（3）来建模：

n时刻LRU 队列的长度可以表示为：

3 实验与分析

3.1 实验设置

为了验证该文提出的缓存替换算法的性能，仿真实验采用Icarus 模拟器在GEANT 网络拓扑下与另外两种传统的替换算法LRU、FIFO（First Input First Output，先入先出）进行对比实验。Icarus 是一个轻量级的仿真软件，可以允许用户轻易地测试定制的ICN 缓存和路由策略。GEANT 是面向研究和教育团体的一个泛欧洲数据网络，总共包含40 个节点，其中8 个边缘请求者，13 个内容提供者，19 个ICN 路由器。仿真实验的各项设置参数如下：1）请求到达速率符合泊松分布；2）内容流行度符合α=0.8 的ZiPf分布；3）内容数据块总数量为1×105个；4）预热ICN缓存网络的请求数目为1×105个；5）实际用于测量统计的请求数目为2×105个；6）请求者发送请求的速率为80～100 个/s；7）节点采用的缓存策略：LCE（Leave Copy Everywhere，处处缓存）和一种基于介数中心性的缓存策略[16]；8）窗口持续阈值n=5。

假设路由器每个端口的处理能力为每秒处理150 个数据块，并且路由器为每个端口维护一条转发队列queuef和缓存响应队列queuec，当两条队列排队的待处理的数据块数目超过端口处理能力（带宽）时，则视为带宽竞争发生。抽样间隔T为0.2 s，监控窗口时长为2 s，当窗口中带宽竞争次数超过6 次时，视为一次持续带宽竞争。

ICN路由器缓存容量S作为变量参与实验对比，其取值为500、1 000、1 500、2 000、2 500、3 000、3 500、4 000，其中替换窗口每次增加的固定值a为0.002×S。实验中，ICN 传输协议将会在检测到用户请求超时后重新发出请求。同一场景下的各个实验独立运行5次，并以95%的置信区间对结果进行分析。

3.2 仿真结果分析

图4 显示了不同替换算法在部署了不同缓存策略的缓存系统中的平均缓存命中率。很明显，比起基于介数中心性的缓存策略，LCE 能帮助系统获得较高的缓存命中率。对于缓存替换算法，由于FIFO算法完全不考虑内容流行度，LRU 能获得较好的缓存命中率。在部署了基于介数中心性策略的缓存系统中，LRU 的性能表现最差，甚至与FIFO 接近，这是由于部分介数较高的节点承担了大量转发任务的同时，较高的缓存命中率使得请求并发响应增多，从而导致带宽竞争状态持续存在，丢包率上升，降低了整个系统的平均命中率。

图4 不同缓存策略系统采用不同替换算法的缓存命中率对比

另外，随着节点缓存容量的提高，采用LRU 算法的缓存命中率先是急剧提升，然后增速降缓。这说明单纯提高节点缓存容量对整体网络的性能改善有限。从图中可以看出，与LRU 相比，该文的优化算法有明显的性能改善，在采用基于介数中心性策略的缓存系统中提升最明显，缓存命中率最高能够提高14.3%。这是因为所提替换算法使介数较高的“中心节点”减少了带宽竞争持续时间，从而减少了丢包率。

为了进一步分析带宽竞争对网络性能的影响，实验观察了不同缓存系统中介数最高节点的丢包率（S=3 000）以及系统的瓶颈重传概率，结果如图5、6 所示；平均重传概率是用户发出的请求总数（包含重传请求）与测试请求数（200 000）的比值，其能在一定程度描述网络的拥塞情况。结果显示无论部署什么缓存策略，介数最高的路由器丢包率都要高于系统的平均重传概率，这证明在考虑带宽资源受限的约束下，“中心”路由器是网络性能的瓶颈。

图5 不同缓存策略系统中介数最高节点采用不同缓存替换算法的丢包率对比

而该文的替换算法极大改善了部署基于介数中心性策略的缓存系统中“中心节点”的丢包率，但在部署LCE 的缓存系统中改善却不明显，这是因为LCE 策略使得缓存系统的“中心”节点带宽竞争产生的主要原因是转发流量过多。

如图6 所示，LRU 算法总是能在系统中产生最高的重传概率，性能表现最差。与LRU 相比，该文的替换算法既有较好的缓存命中率，同时系统平均重传概率也比LRU 低，在基于介数中心性策略的系统中性能改善最高能达到34.9%，这是因为该算法减少了带宽竞争，进而减少了因丢包造成重传。

图6 不同缓存策略系统采用不同替换算法的重传概率对比

图7 对比了不同替换算法在不同缓存策略系统中用户内容下载时延。随着节点缓存容量增加、系统平均命中率的提高，用户下载时延在不断减少。对比其他两种缓存替换算法，该文的替换算法性能表现最好，这是因为其有效抑制了路由器带宽竞争持续的时间导致节点丢包率和重传概率减少，从而大幅度降低了用户内容下载平均时延。在基于介数中心性策略的系统中，与LRU 算法相比，内容下载时延最多可节省11.3%。

图7 不同缓存策略系统采用不同替换算法的内容下载时延对比

4 结论

该文针对ICN 缓存节点因持续处于带宽资源竞争状态导致网络拥塞加重的问题，提出了一种基于路由器负载状态的缓存替换算法。该算法通过监控持续带宽竞争状态来改善LRU 的性能，并在采用不同的策略（LCE，基于介数中心性的策略）的缓存系统中进行性能对比。实验结果表明，所提优化算法能够有效地改善LRU 算法的不足，并在内容下载时延、平均缓存命中率、重传率上都获得了较好的性能提升。