Review & Abstract
我有一个真实数据，我希望只需要算出它的一些统计特性给别人，别人用这些统计特性就能估计出接近真实的cache表现，该怎么办？
如何对cache表现做接近真实的评估？存储系统常用到independent reference model（IRM）。这个模型认为对每个内容的请求概率就是trace中对这个内容的请求频率，然后进行计算
考虑一个简单的例子：两个轨道A和B，每个在15分钟内有1,000个I / O。
考虑以下两种情况：
- （I）磁盘首先接收并响应轨道A上的所有1,000个I / O请求，然后响应所有1,000个轨道B的I / O。
- （II）磁盘交换地接收并响应来自不同轨道的I / O请求：首先A，然后B，然后A再次交替，A / B多达1000次。
IRM计算出的miss次数将是1000次（不关心具体过程），实际上（1）是最佳情况，miss2次；（2）是最差情况，miss2000次。可以证明，最差情况下的miss次数最多是IRM算出的期望的一半：这是IRM的保守性
IRM假设：1、popularity不随时间改变；2、新的请求跟过去无关。然而，现实中会有时间局部性，即请求突然暴涨
我们需要一个既能处理时间局部性又保持简易性的模型
本文研究了一个60k规模的具体网络，说明了普通caching估算得过于保守
本文的两个新奇的贡献：1、一个评估函数：切片和切片内部打乱来将时间局部性模块化，来表现其对caching的影响。2、建模，在数学简易性（simplicity）和实际契合之间折中
本文提出的Shot Noise Model（SNM）这个模型基于泊松分布中的Shot Noise，这是第一次将shot noise应用到视频等内容的cache
评价：这是一个新颖的模型。以前为了简易性，一直盲目使用IRM。此外，本文模型对实际的数据集应用了成熟的分析。不足之处：LRU策略已经有很多不足了，本文仍对所有请求应用LRU，显得不够实际、缺乏惊喜；另外，本文只讨论了小规模cache和low hit probability.
本文对cascade-based requests引入了数值分析，具体阐释详见参考文献
1、INTRODUCTION
很多地方都要用到cache：Information Centric Networking (ICN) [1, 2], resource management in cellular networks [3, 4], energy efficient networking [5], massively geographically distributed CDNs [6] and ISP-assisted CDNs [7].
研究方法通常是trace-driven的：对于未解决的问题，要收集相关的实际数据作为trace，对它们做模拟[3, 4, 6, 7, 8]. 这样做的问题：1、需要庞大的数据集，同时数据的偏差会使研究者受限；2、死的数据无法用来研究尚未发生的、潜在的变化。我们需要能评估过大的／无法获得的／尚未出现的数据，尤其对于Video- on-Demand (VoD) systems. 因此需要建模，靠参数就能模拟出数据
本文将说明IRM的假设存在的问题，以及提出SNM模型
关于时间局部性已有研究工作：[14, 15, 16, 17]。但是，它们相比今天的Video-on-Demand traffic 都没有考虑popularity的长期的特性、对一个内容请求的分布、和连续请求
- THE STANDARD APPROACH
IRM用到了Zipf law：对一些内容，请求the nth most popular item的概率恒定为1/n^alpha，不随时间变化。IRM简单而高效，但是相对于现实仍然太过于死板：它基于一个假定：“相对cache churn的变化，内容popularity的变化慢”，才算是一个可接受的近似
考虑到了时间相关性的延伸工作一般关注别的应用，而不是视频方面[22, 23, 17]；而且，这些工作还是认为内容的总集不变，并且应用stationary process (either a renewal process, or a Markov or Semi-Markov Modulated Poisson process).
以下说明IRM的假设存在的问题。本文采用的数据规模：In total, we recorded almost 10 million transactions, accounting for approximately 227 TB of delivered content.
*Zipf law是由多种实际数据支持的，建模方面的参数化不很明显
有一个常见的陷阱：一有大量的数据，就直接套进根据长期的评估而建立的模型。有时可以认为“相对cache churn的变化，内容popularity的变化慢”，然而内容popularity的瞬时变化还是可以跟长期变化有很大差距
使用Trace 1说明使用长期测量得到分布会产生的影响。将trace按时间顺序分成K slices、每个slice都含有相同数量的请求，计算每个slice中内容的相对popularity（将slice中的请求总数归一化）
根据Fig 1，slice分得越细（即k越大），每个slice里面流行内容的访问比例越高（即alpha越大），即流行内容越集中——这反映了时间局部性。这说明时序（time-scale）分得越细，越难得出一个可靠的——这里说的应该是忽略了时间相关性且长期测量得出的那种——popularity分布
根据Fig 2，先按照给定的K切片，每个slice内部再shuffle：对象不变，但时间相关性／时间局部性被破坏了，且各个请求相互独立。结果：对采用LRU的cache，越使用长期测量得到的分布（即K越小），hit概率越低（使用LRU是review提到的本文不足之处之一）：低估了cache策略
如果要继续使用IRM，同时也矫正时间相关性问题，该怎么办呢？
首先确定一个evaluation interval——它描述内容popularity的变化，其大小达到cache的变化的数量级（comparable）。然后，认为同一个interval内内容popularity的变化可以忽略，对这些请求计算一个修正的popularity分布（记得这里分母从整个trace变成了一个slice，要归一化）
另外，因为trace长度有限，需要限制cache size，使得eviction time（从上次请求的时刻到从cache中被删除的时刻之间的间隔时间）明显比整个trace要短。（the average eviction time is 2-3 days for cache size in the order of 50, 000 objects, which is the maximum considered in our experiments. ）因此本文研究的hit概率都<=0.25，很低——这是review提到的本文不足之处之一
结果1、IRM严重高估了所需的cache size，specially when the hit probability is low. 2、K越增加，数据就越接近原顺序，所需的cache size也越接近原顺序
根据图像，是不是切片细到每一天为一个slice就够精确了？这样做仍有不足：
1、根据Fig 1，因为随机扰动，从太短的时间尺度难以得到popularity的分布
2、更难以确定的是，内容popularity的变化是否可以忽略。尤其是对最不popular的内容，因为样本太少
3、实践中，evaluation interval也要与cache变化相适应，这涉及到several factors (aggregate requests arrival rate, cache size, caching policy, etc.) 不同情况下得重新计算一个不同的popularity的分布
4、而cache的变化又依赖popularity分布，会陷入相互依赖的循环
5、有些时候内容popularity的变化相对cache的变化是可观的、不可以忽略（当且仅当在请求数相对cache大小显得特别少时），IRM就不准确了
综上所述，IRM还是难以改良，应该另谋出路
- TOWARDS A NEW MODEL
对于内容请求的pattern的研究：
实际中观察到的内容请求会变化的2个主要因素：请求集合的每天的arrival rate（参见Fig 3）；对单个内容请求的arrival rate之间差别非常大（参见Fig 4）
跟常见的认识[25]不同，每天的变化对cache表现几乎没有影响。原因：各种cache策略中，hit概率都只与进入cache的顺序有关，而不是发出请求的时间；只要请求之间顺序一定，间隔时间变化，hit概率也不变
根据Fig 3，对Trace 3的研究发现，每一天内（按两个小时划窗口）波动很大，但是每天的变化曲线都相似
根据Fig 4，对Trace 2的研究发现（只统计了视频的生命周期中请求的数量——最初和最后曲线基本持平的阶段未画出来）：对YouTube视频，请求的分布很不均匀（heterogeneous）、时间局部性极强。观察到，growth pattern很复杂，有些视频几天后就消失了，有些在整个trace的时间跨度里内却长盛不衰，这反映出用户的兴趣的多样性
建模：对内容m，设置两个参数：总请求数Vm、内容的有效生命周期lm（累计请求数到达0.1Vm和到达0.9Vm两个时刻之间的时间长度，不取完整个0～Vm是为了排除特异点，比如很久以后偶尔又请求某视频一次）；因为准确值难以统计，通过统计trace，得到Vm和lm的估计值Vm^和lm^。它们会比真实值小：视频的真实生命周期比trace长度长
根据Fig 5：Vm^ – lm^分布密度图很不均匀。（只取了Vm^>=10的视频）
7～10%的视频的lm^<=5（2%的视频的Vm^>=10）但对它们的请求占了27%（对各个trace都是如此）。这说明应该关注生命周期短但涉及请求占比多的视频，对它们准确建模
根据Fig 4，growth pattern很复杂，仅靠Vm和lm建模还不完全。recent studies [26, 27, 28] ，reveal that the popularity of different contents, including videos, follow a limited number of “archetypal” temporal profiles, which essentially depend on the nature of the content and on the way it becomes popular. 但是还是Vm和lm主要，while the shape of the popularity profile has only a second-order effect. （二阶影响）
- SHOT NOISE TRAFFIC MODEL
目标：保持IRM的一般性和灵活性（flexibility）、不太提升复杂度地提高准确性总体的请求是各个独立部分的叠加（superposition）。这是一个非齐次泊松过程（lambda不是定值而是一个函数），内容m用三个参数来刻画
tau m（τ：tau，符号不好打就写成tau了）表示内容进入系统、可以被用户请求的时刻
Vm表示对一个内容的总体请求数（几个trace取平均）
lambda m（λ：lambda，符号不好打就写成lambda了）表示popularity profile：对给定的对象m的请求比率（request rate）
lambda m是一个t的函数，它恒大于等于0，t小于0时为0，从0开始的无穷积分为1
给出fertility function：在时刻t，t-tau m为时间间隔，代入lambda函数表示当前时刻应收到请求的比例，再乘以Vm表示当前时刻应收到请求的数目
在时间区间[tau m, t]内的请求数目成泊松分布，参数为这个总乘积的积分
可以认为是一个泊松shot-noise process[29] 。SNM模型因此得名
参见Fig 6，图中的两个”shot”对应的内容不同，参数也不同：V1<V2，L1>L2，因此曲线形状也不同
这些假设是为了分析上易处理（analytical tractability），同时也由trace证明了其合理性：根据Fig 2，如果trace 2被切的足够细，每个slice都是短时间（比如不长于6小时），slice内不考虑时间相关性没有显著影响：说明了使用泊松模型的合理性
另外，we don’t need to take into account possibly complex correlations in the
arrival process of requests such as might be induced by popularity cascades [27, 30, 31]：尽管有这种现象（具体怎么回事？？？），但在本文用到的trace中没有观察到
其他cache建模：参照[32]
关于计算lambda函数本身的麻烦：没有必要精确确定lambda函数的形状：根据一阶近似（first-order approximate：泰勒展开到一阶余项）就足够作出准确预测了。参见Fig 7，相对于IRM，Trace 4中，SNM的四条曲线彼此都很接近
考虑内容的不均匀性：对每个新内容，安排一个lm，再取一个典型相关（？？？）的Vm
4.1 Parameter Fitting
先把内容根据Vm^和lm^分为6组，编号Class 0~5
Class 0的Vm^<10，表示无法准确估计lm的内容：因为对它们的请求太少了。85%的内容都属于Class 0，但是因为数据少得完全不足以分析它们的分布，不得不放弃对它们的时间局部性的研究，对它们使用IRM
Class 1～5的Vm^>=10，Class1中l<=2，Class2中2<l<=5，……参见Table 2（单位为天）
Class 1的内容<=4%，对其请求的比例却占到约10%
这样的分类下，四个trace导出的参数值都相近，因为这个分类抓到了traffic中某些不变的属性（说明它们就是trace的关键参数，足以模拟一个trace）
本文用到的trace历时只有一个月，因此还无法归纳出一般的结论，尤其对于周期长的视频。尤其对于lm>13天的Class 5的视频，其生命周期已经达到整个trace长度的相同数量级了，其真实的lm应该大大被低估了。因此对Class 5的视频，也按照popularity不随时间变化处理（跟IRM一样）
Class 1～4中的内容如下产生：1、Table 2中的Video一栏描述了每个class中新内容的产生速率；2、认为所有内容的lm都是trace统计出的该class的E(lm^)，同时弥补对lm的低估3、根据V-l的密度图，选择一个合适的Vm；4、根据不均匀泊松过程和fertility function，进行计算[33]
四条曲线中的两条给出了表达式：exponential，uniform，都以E(lm^)为参数；这些曲线之间差别不大的原因：见上文，它们以t为变量，而cache表现跟时间无关，只与请求顺序有关
4.2 Model Validation
模拟出一个trace，按三种方式1、分6个class；2、完全保留原顺序；3、完全打乱（跟IRM一样），对其实行LRU，测量popularity分布
参见Fig 7，相对于IRM，Trace 4中，SNM的四条曲线彼此都很接近，离IRM更远。这说明有些lm短的内容对cache表现的影响确实不容忽视
关于day/night两条曲线：说明了日期变化对缓存性能有微小的影响
4.3 Computational cost
使用SNM生成模拟轨迹的计算成本仅略高于IRM的成本
当来了一个将具有参数Vm和lm的新内容时，可以首先根据Vm平均值的泊松分布生成对此内容的请求总数，然后提前准备：每个请求的到达时间根据内容的时间特征（取决于lm），将其记录到一个或多个有序的数据结构（如堆）中，作为一个动态模拟器
设未来会出现的请求数为M，插入新请求的时间复杂度：IRM为O（1），SNM为O（logM）
最坏情况下，M为trace长度；实际上M会小的多，因为它与落入shot的平均请求数量相关，即M = O（E（Vm lm））？？？）。根据经验，它小得微不足道