论文阅读翻译笔记—On the Complexity of Optimal Request Routing and Content Caching in Heterogeneous Cache Net

论文名称：异构缓存网络中最优请求路由和内容缓存的复杂性研究（On the Complexity of Optimal Request Routing and Content Caching in Heterogeneous Cache Networks）

论文地址：https://ieeexplore.ieee.org/document/7797148

---

文章目录

• @[toc]
• 一、全文基本研究内容
• 1.研究的主要问题
• 2.研究目标
• 3.本文主要贡献
• 4.文章组织结构
• 5.研究结论
• 二、使用的网络模型
• 三、问题公式化说明
• 四、对拥塞不敏感的未缓存路径
• 1. 一般情况下的难度
• 2. 特殊情况：每个用户一个文件
• 3. 特殊情况：具有两个缓存的网络
• 4. 复杂性讨论
• 五、对拥塞敏感的未缓存路径
• 1. 一般情况下的难度
• 2. 单个缓存情况下的难度
• 六、 近似算法
• 七、 性能评估
• 1. p-LRU
• 2. 网络设置
• 3. 数值评估
• 4. 跟踪驱动的模拟
• 八、 附录（略）

一、全文基本研究内容

1.研究的主要问题

如何在支持网络内缓存的网络中开发最优联合路由和缓存策略，以最小化预期的内容访问延迟。

考虑了问题的两种情况：

1. 假设延迟与所有路径上的流量负载无关，称为不受拥塞影响的情况
2. 假设到后端服务器的延迟取决于流量负载，称为拥塞敏感情况

2.研究目标

本文研究目标有两个

1. 搞清楚联合缓存和路由问题的计算复杂度（即一般问题能否在多项式时间内得到最优解。如果不能，是否有可处理的问题实例以及是什么原因导致一般问题难以处理）
2. 对实际中运行良好的联合缓存和路由问题，寻找有效的近似解

3.本文主要贡献

作者主要做了四项工作贡献：

1. 对于联合缓存和路由问题的拥堵不敏感和拥堵敏感两种模型，提供了一个统一的优化公式，并且证明了在这两种情况下，该问题都是NP完全的。
2. 证明和发现了三个结论：
   1. 对于不受拥塞影响的非连通路径模型，作者证明了如果每个内容只被一个用户请求，或者当网络中缓存的数目最多为两个时，就可以在多项式时间内找到最优解；
   2. 确定了在一般情况下问题复杂性的根本原因是：在表示用户和缓存之间连接的二分图中，用户和缓存的循环中数量为奇数；
   3. 对于拥塞敏感的非缓存路径模型，作者发现即使网络中只有一个缓存且每个内容只由一个用户请求，问题仍然是NP-完全的。
3. 设计一个贪婪的缓存和路由算法,它能达到一种平均延迟，该延迟在最优解的(1−1 / e)因子和有较低复杂性的第二个贪婪算法之间
4. 通过数值计算和跟踪驱动仿真，对贪婪算法、最优解法(通过bruteforce搜索)和基于LRU的标准解进行对比评估。数值结果表明，贪心算法在计算最优解可行的情况下性能接近最优。仿真结果表明，与传统的LRU缓存策略相比，贪心算法在性能上有显著的提高。

4.文章组织结构

第二节描述了使用的网络模型；

第三节描述了研究的最优联合缓存和路由的问题；

第四五节分别说明了阻塞不敏感模型和阻塞敏感延迟模型的复杂性结果；

第六节解释了近似算法；

第七节展示了仿真结果

5.研究结论

作者将到后端服务器的路径建模为对拥塞不敏感的恒定延迟路径，并通过凸延迟率函数对对拥塞敏感的路径进行建模。

1. 提供的基本的复杂度结果，表明联合缓存和路由问题在两种情况下都是NP完全的。

2. 开发了一种贪婪算法，该算法可保证最优解决方案的$(1−1 / e)$(1−1/e)性能以及较低的复杂度启发式算法，同时根据经验发现，较低复杂度的启发式算法在优化的传统LRU缓存的情况下，平均延迟性能在最佳值的1％以内（对于小问题的情况），并且显着降低了平均内容访问延迟。

3. 对特殊情况场景的研究——拥塞不敏感的多缓存单文件感兴趣的情况（我们演示了一个最优多项式时间解）和拥塞敏感的单缓存单文件感兴趣的情况（我们证明仍然是NP完备的），这些都帮助阐明了使该问题在一般情况下“困难”的原因

二、使用的网络模型

该网络中$N$N个用户为一组单位大小的$K$K个独立文件$F={f_1, f_2, ... , f_K}$F=f1​,f2​,...,fK​生成请求，网络中有$M$M个缓存可以为用户请求提供服务.

令$C_m$Cm​表示第$m$m个缓存的存储容量，该存储容量由它所能存储的文件的最大数量来度量。如果用户$i$i请求文件$j$j并且它存在于缓存中，那么请求将立即被处理，我们将此事件称为缓存命中。但是如果内容$j$j没有出现在缓存中，那么缓存会将请求转发到后端服务器，从后端服务器下载文件$j$j并将其转发给用户，我们将此事件称为缓存丢失，因为需要从后端服务器下载内容以满足请求。注意，如果缓存丢失，缓存可以决定是否保留下载的内容。

用户$i$i根据聚集速率$\lambda_i$λi​的泊松过程生成对F中文件的请求，所有用户的总请求率是$\lambda$λ。我们假设独立参考模型（IRM），用$q_{ij}$qij​来表示用户$i$i生成针对文件$j$j的请求的概率（称为文件流行度）。

三、问题公式化说明

联合的缓存和路由问题，目的是最大程度地减少所有用户对所有文件的请求的平均内容访问延迟。要解决此问题，需要解决两个密切相关的问题：

1. 如何管理缓存内容，应将哪些文件保留在缓存中，以及应使用哪种缓存替换策略？
2. 用户应如何在缓存路径和未缓存路径之间路由他们的请求？

定义二进制变量$x_{jm}\in\{0, 1\}$xjm​∈{0,1}来表示内容在缓存中的位置，其中$x_{jm}=1$xjm​=1表示文件$j$j存储在缓存$m$m中，而$x_{jm}=0$xjm​=0表示不存在。

四、对拥塞不敏感的未缓存路径

1. 一般情况下的难度

2. 特殊情况：每个用户一个文件

考虑图1中所示的网络，但是假设每个用户只对一个文件感兴趣，即$q_{ij}=1$qij​=1并且$q_{ij}=0$qij​=0，其中$i\ne j$i​=j。在这种情况下，基于最大加权匹配问题的解，可以在多项式时间内找到联合缓存和路由问题的最优解。

注意，在这种情况下，文件的数量等于用户的数量，即$N=K$N=K，为了避免琐碎性，我们假设用户数量大于网络中每个缓存的容量，即$C_m\lt N$Cm​<N，$\forall m$∀m。

3. 特殊情况：具有两个缓存的网络

当网络中只有两个缓存时，联合缓存和路由问题的最优解可以在多项式时间内找到。更具体地，作者证明了当网络中存在两个缓存时，整数程序(1)的解可以在多项式时间内找到。

4. 复杂性讨论

考虑一个有三个用户和三个缓存的网络，如图3所示。每个用户连接到两个缓存时，可以看到用户和缓存的连接形成一个循环，如图4a所示。假设从用户到缓存的所有路径都有相同的命中延迟和未命中延迟。另外，假设每个缓存都有存储一个文件的能力，并且所有三个用户都对两个文件感兴趣，这里用绿色和红色表示。

五、对拥塞敏感的未缓存路径

考虑这样一种情况:在未缓存路径上的请求延迟和缓存丢失的请求延迟依赖于此类请求的负载。也就是说，我们分别使用凸函数$d_b(\cdot)$db​(⋅)和$d_c(\cdot)$dc​(⋅)计算非缓存路径和从缓存到后端服务器的路径上的延迟。我们分别处理未缓存路径上的请求和缓存丢失的请求的原因是，这些路径可以使用不同的基础设施到达后端服务器。例如，来自移动用户的请求通过未缓存的路径可以使用LTE基础设施，而来自部署在WiFi接入点的缓存的未命中请求可以使用有线宽带连接。

1. 一般情况下的难度

注意，我们可以将拥塞不敏感延迟模型看作是$d_b(\cdot)=d_c(\cdot)=0$db​(⋅)=dc​(⋅)=0的拥塞敏感模型的特例。因此，这个问题通常是NP完备的。然而,在本部分的余下篇幅中,我们将证明联合缓存和路由问题在拥塞敏感的情况下仍然是NP完全的，即使网络中只有一个缓存，并且对每个内容感兴趣的用户都不会超过一个。

2. 单个缓存情况下的难度

六、 近似算法

这一节中，作者展示了联合缓存和路由问题(对于拥堵不敏感和拥堵敏感的延迟模型)可以被表述为受矩阵约束的单调子模函数的最大值，这使我们能够设计具有可证明的近似保证算法。

七、 性能评估

在这一节中，我们通过离散事件模拟来评估近似算法的性能。我们这里的目标是评估1)贪婪算法的解与最优解的比较(当计算最优解是可行的)，以及2)贪婪算法的解与基线标准产生解的比较。

在这里，我们考虑一个对阻塞敏感的模型，在这个模型中，未缓存路径上的请求将经历一个以M/M/1队列为模型的排队延迟，而对缓存未命中的请求将经历一个持续的延迟。对于我们的标准，我们将近似算法与我们称之为p-LRU的以下算法得到的延迟进行比较。

1. p-LRU

2. 网络设置

3. 数值评估

4. 跟踪驱动的模拟

八、 附录（略）