In-network Caching of Internet-of-Things Data
作者Serdar Vural, Ning Wang
单位Centre for Communication Systems Research, University of Surrey, Guildford, Surrey, GU2 7XH, UK
Key Word: Cache policy，不考虑节能、路由
（A）Motivation：
1、应用场景
整个互联网范围内，为了获取实时股票、天气等信息，数十亿个物联网终端向少量的源请求数据。因此不能靠源主动push；路由认为是最简单的形式：一条多跳的链路；选择分布式策略。
2、详细说明：
是这数十亿个终端直接构成一个ICN网络、每个终端都可以cache东西吗？不是。
一个家庭/地域的IoT是有网关的。是由M2M网关进行cache、而不是终端。（M2M是Machine-to-Machine/Man的简称）
网关的意义：终端是碎片化的，网关对它们进行整合。比如很多个终端都通过网关向外请求天气数据，那么网关可以整合这些请求、只对外请求一次；
一个家庭的IoT内每个终端的确不需要cache，它们到网关只需要一跳。不需要研究终端之间作为一个ICN网络。
数据需要新鲜度，比如实时股票交易。
3、Cache的必要性：
如果是终端直接向源请求，可能因为它资源有限而做不好；但现在我们知道，是靠网关向源请求。那还为什么需要cache呢？不能让网关像一个普通的客户端一样，每次向源请求数据呢？
因为网关太多、请求的频率远比普通客户端频繁。“尽管每个物联网流量的速率都很低，但全世界范围的总负载预计很大，甚至有可能中断正常的数据流量。”（？）体现在互联网层面，是需要降低冗余流量；体现在本文，就是要降低通信成本：总负载太大的话，延迟就大，而比如股票交易又需要快速反应，如果每次都向源发送请求，则通信延迟会很大。
4、Cache的可行性：
让步：IoT对获取数据的新鲜度有要求，同时也没有到达实时视频那样的地步。
很多时候请求的内容形如“过去10分钟内位置X处的平均温度”，或者“最近一小时内位置Y处的最大风速”。这种情况下回复cache数据也没事。另外，Cache数据的特色：一般的路由器cache的多媒体文件的体积很大、永远不会变化；IoT的数据的体积很小、有新鲜度的要求，Cache是装的下的。
（B）Problem：新鲜度和通信成本需要折衷；如何折衷
（C）Idea：
1、建模计算出了一个“新鲜数据hit率”的公式；公式说明要提高新鲜数据hit率需要降低“缓存寿命”（即提前进行缓存的时长），因此又需要增大通信成本
给定链路上的一跳：
设Pe为新鲜数据在这一跳上hit的概率，那么Pe等于多少呢？
设收到的数据请求接收频率r[in]，涉及popularity
设接收到数据后，该跳把它cache住的概率为Pc。缓存策略是选择性缓存，Pc会动态调整，以此来达到新鲜度和通信之间的平衡。比如如果非常需要新鲜度而不在意通信，那缓存就是不必要的。
推导出了一个关键的公式：Pe = r[in]Pc / (1/Tres + r[in]Pc)。具体推导过程参见下文具体细节部分
原文认为，这个公式说明：（1）如果传入请求率r[in]较高，则更有可能在缓存中找到数据项;（2）如果路由器选择更频繁地缓存项目（即选择更高的Pc），会增加在其缓存中找到该项目的可能性。我认为还说明了：（3）为了新鲜hit率，需要1/Tres小 = Tres大（新鲜） = 降低缓存时间；但为此又会提高通信成本CC。也就是证明了Problem的存在；新鲜度和通信之间的确是存在矛盾、需要折衷的。
2、以缓存寿命为自变量，定量计算出了新鲜度损失和通信成本，并提出了一个通过参数自适应在两者之间动态权衡的算法：动态调整随机缓存的概率
因为是on-path cache，认为只有一条一维的链路。节点0是最内侧节点、节点N是producer。
设第i跳的通信成本为CC(i)，新鲜度成本为FC(i)，总成本为C(i)。关于两者的具体值的计算，参见下文具体细节部分。
本文认为C(i) = αCC(i) + (1 − α)FC(i)，下游节点拿到数据时的总损失；展开后与α、Pe有关：其中α是经验值，而Pc的调整则是定量的：根据paper中的公式（28），大致意思是：
当Pe(i)的系数大于0时，减小Pc（某个事先给定的步长）
当Pe(i)的系数小于0时，增大Pc
然后，每个节点i的初始Pc(i)为0
调整Pc(i)，也就调整了当前节点的Pe(i)
所以，导火索是一个节点处的popularity变化，导致它的Pc变化；
上游节点的Pc先变化，然后下游节点Pc跟着变化。
以一个极端为例：对一个内容，只需要新鲜度，完全不需要考虑通信，因此可以全部从producer取而不需要缓存。于是设置α=0。从第N跳处开始慢慢推进，各处的Pc都将被调整成0。
（D）具体细节：
一、建模公式计算
新鲜度的概念：
考虑一个关键的时间数据属性：数据项生存期（data item lifetime），过期的数据不能使用、被cache丢弃，以此来维护数据的新鲜度。
关于内容的定义：
可能有很多数据包data描述同一个内容（比如温度是一个内容，每秒都会测一次温度，就有了很多个data）。本文给予每个内容一个唯一的静态内容标识符，称为CID。对于一个内容的请求，会跟所有data的CID匹配。
一个data含有CID、时间戳字段，其中包含它生成的时间点t[gen]、有效期T。每种内容的T一般不同
设dataage = t[arr] – t[gen]，Tres = T – dataage
Freshness = (T-dataage)/T = Tres / whole lifetime
注意：当data在某一跳上被cache住时，Tres会在其上累计，但是本文只考虑放在cache中时流逝的时间，而不考虑发送请求和数据传输时的用时。
给定链路上的一跳：
设Pe为新鲜数据在这一跳上hit的概率，那么Pe等于多少呢？
设收到的数据请求接收频率r[in]，涉及popularity
设接收到数据后，该跳把它cache住的概率为Pc。缓存策略是选择性缓存，Pc会动态调整，以此来达到新鲜度和通信之间的平衡。比如如果非常需要新鲜度而不在意通信，那缓存就是不必要的。
P.S. Pc是拿到data后马上存入缓存的概率，有可能缓存不够大又把它剔除出去了。Paper也提到了缓存的剔除策略：
“提出的缓存机制的另一个重要方面是每个路由器的缓存中最多只能有一个关于给定内容的数据项
需要一个单独的计时器来跟踪缓存中哪个项到期，否则需要定期将需要扫描缓存空间来监视剩余项目的生命周期。
为了避免这种情况，必须仅在需要时才应用高速缓存逐出，即当新的新鲜物品到达时。
当未到期的数据项目X到达路由器并且已经为该项目做出高速缓存决定时，如果以下条件之一成立，则另一个数据项目Y从高速缓存中被驱逐出去：
1）缓存空间已满并且项目Y（X和Y是否具有相同的内容）已经过期，
2）缓存空间已满，Y（无论X和Y的内容是否相同）没有过期，但是Y是缓存中最不新鲜的项目（称为LFS）驱逐策略，
3）缓存未满，项目X和Y的内容相同。当X是更新的值时，情况就是这样，因此它比Y更新鲜。”
然后，推导出了一个关键的公式：Pe = r[in]Pc / (1/Tres + r[in]Pc)
原文的推导思路有些乱，我这里用另一种方式证明这是对的：
设一个内容的当前的剩余寿命为t；起初，t = 0
按照期望，每过1/r[in]的时间，会收到一个请求
此时，更新当前data的t-=1/r[in]，然后判断：
1、若上次的data还新鲜：即t>0；此时返回上次的data，t不变（P.S：原文有个问题，并不是只要t大于0，data就一定存在于cache中。实际上有可能被剔除出去了！）
2、若上次的data已经过期，即t<=0
此时对外发出请求，并马上（如前所述，这里不考虑通信的用时，通信方面的目标只是尽量减少跳数）得到了返回的data
情况（1），有1-Pc的概率，没有缓存下来
此时更新t = 0
情况（2），有Pc的概率，缓存下来了
此时更新t = 这个data对应的Tres，这会是一个常数（可以先感性的认识一下，如果整个链路的结构、上游每一跳的Pc和r[in]都不变，那么会达到平衡，一条链路上的第i跳处的Tres就会是一个常量，设这个常量为G(i+1)，下文会推导它的值）
那么，在这个流程之下，按照几何分布，连续miss了1/Pc次；然后又hit了Tres*r[in]次。这整个过程会不断的循环。因此，Pe = hit次数 / (hit次数+miss次数) = Tres*r[in] / (Tres*r[in] + 1/Pc) = r[in]Pc / (1/Tres + r[in]Pc)
原文认为，这个公式说明：（1）如果传入请求率r[in]较高，则更有可能在缓存中找到数据项;（2）如果路由器选择更频繁地缓存项目（即选择更高的Pc），会增加在其缓存中找到该项目的可能性。我认为还说明了：（3）为了新鲜hit率，需要1/Tres小 = Tres大（新鲜） = 降低缓存时间；但为此又会提高通信成本CC。也就是证明了Problem的存在；新鲜度和通信之间的确是存在矛盾、需要折衷的。
P.S. 实际上，新鲜data在cache中的存在概率应该是Pc乘一个比例因子，因此公式中的每一个Pc处都应该乘一个比例因子。不过以上的推导看的只是一个单增/单减的趋势，因此还是正确的
二、动态权衡的算法中，FC和CC的求解
节点i可能存的也是上游节点（编号大于i）cache来的东西，得到的caching age要累加。以下用E[CA(i)]表示在第i跳上的总缓存时间
E[CA(i)] = 第i跳接受data时的已有CA + 在i-1跳向第i跳请求前在第i跳上的附加CA，= G(i + 1) + _CA_(i)
求解对象：FC(i) = G(i)/T
1、G(i+1)（要求的其实是它）
节点i发出请求，收到的是节点j的cache内容的概率为
P(节点j有) * P(i+1~j-1都没有) （5）；是否cache都是独立的
（5）*E(CA(j))，再求和，得到G(i+1) =第i跳接受data时的已有CA
发现G(i)可以递推求解，G(i) = Pe(i)E[CA(i)] + (1 − Pe(i))G(i + 1).
化简得G(i) = Pe(i)._CA_(i) + G(i + 1). (18)
2、_CA_(i)，一般等于1/r[in]（P.S有例外）
r[in]大的话，CA一般会比较大，FC也就大
（简单来说可以这么理解：如果r[in]（popularity）大的话，平均请求接收时间短，此时可以牺牲新鲜度、多进行缓存、优先满足通信，Pe也会高）
popularity的统计：开一个窗口，只考虑最近W个请求
（我的问题：应该考虑数据稀疏的情况，具体怎么办还没想好）
3、计算新鲜度损失FC(i)：
FC(i) = G(i)/T，就可以求解了
递推式包含Pe(i)和_CA(i)_，即涉及自己与上游每个点的Pe、popularity
类似的计算跳数CC，只是跳数不像寿命一样会累积
_h_(i)：
节点i发出请求，收到的是节点j的cache内容的概率为
P(节点j有) * P(i+1~j-1都没有) （5）；是否cache都是独立的
（5）*(j-i)，再求和，得到_h_(i) =第i跳接受data时的平均跳数
同样可以递推求解：_h_(i) = (1 − Pe(i)) h(i + 1) + 1 . (23)
CC(i) = _h_(i)/N，就可以求解了
递推式包含Pe(i)，即涉及每个点的Pe
（递推所需的数据放在data里面传递）