KEYWORDS
Off-path caching; Content discovery, Routing, Management.
1 INTRODUCTION
背景：内容发现机制可以利用AS内的分布式缓存系统来本地检索内容，而不是来自可能的外部内容源。这需要AS间通信。
目的：在ICN中减少代价高昂的AS间通信、降低检索延迟（即QoS）
方法：
1、在机会性内容发现机制中，沿着最短路径（或指定路径on-path）向内容源头机会性地搜索内容。这种方法有一个非常有限的搜索范围（只有路径上的节点），因此收益有限，但不需要节点之间的协调或通信。
2、在协调的内容发现方法中，请求被转发到某个可能保存这个内容的指定缓存中[3,20,22]。这些技术可以以额外的协调和通信开销（例如，更新协议或signaling）为代价获得显着更高的增益
3、本文的方法：
对于临时存储的内容，设置一个“临时（ephemeral）转发状态”。在该路径上的每个节点处，由它机会性地建立处理数据包：靠临时（ephemeral）转发状态来定位临时存储的内容。传输data时，它在这条路径上的每个节点处机会性地启动。保证：通过AS间链路检索的内容沿着AS内部传输（delivery）路径仅被缓存一次，以最大化网络存储利用率。
这种方法有协调，同时每个路由器只跟踪少量的状态，因此不需要signaling或更新协议。使用一个名为Ephemeral Forwarding Information Base（EFIB）的新组件来增强NDN路由架构，该组件追踪数据块最近被缓存的方向（下一跳）。EFIB中的条目是通过返回的数据包机会性地创建的，它包括原interest的路径（trail），来追踪缓存了该内容的cache，所有路由器的表项整体构成了被cache的内容的路径。（这样挺好的，把两种转发表分开来考虑，别混在一起）
EFIB表使用Content Store容量的一小部分作为LRU缓存进行维护。
*举例：Figure 1:曾经请求过某data，data从Ri, Rk, Rp, Rm, Ru的路径到达用户。根据放置策略，在这条off-path上也被且仅被缓存在Rp处，EFIB表都指向Rp方向的下一跳。这样，转发interest可以同时使用FIB（AS之间，towards producer）和EFIB（AS之内，towards cache）。PS：考虑到cache也可能在on-path上，其实转发策略的选择并没有那么多。
相应的新的转发策略：本文提出了一个“基于预算”的多播转发策略（见第4节）。其中每个interest都有一个“转发预算”花费上限（在中间路由器上）。路由器可以选择将花费所有预算来寻找附近的off-path（EFIB），也可以搜索less aggressively的on-path，最后找到producer。
2 RELATED WORK
Off-path机制需要把请求对应到附近的（也可能不在附近）节点。
1、通常的方法：每个节点对应到静态的、预定好的一个节点集合（e.g., [3, 17, 20, 22, 26].）这方面的代表性提案是[8]，[12]，[14]和[19]。这个方法需要通信
2、使用控制层来协调（在[7]，[21]和[29]中提出的策略）来放置内容、重定向请求。对请求进行元请求来发现内容位置（就是新内容主动声明自己的位置）。还可以涉及到散列路由。
3、修改Breadcrumbs的机制：在转发data的时候，记录的不是来的方向（cache的方向），而是去的方向（用户的方向）。这本来该是PIT表相关的东西，但是注意到：最近请求过它的用户的附近也可能cache了该内容。
但是这个方案中，节点采取leave-copy-everywhere（LCE：在对象传输的沿途节点都缓存该对象。这是许多缓存系统的默认方案，没有协同机制）的内容放置策略，来保证请求一定能在cache处成功返回。
本文在3的基础上，研究一个更复杂的转发策略、更好的放置方案。每次有一个用户请求内容，这条off-path上就恰多存一次cache，不多也不少。
3 OPPORTUNISTIC CONTENT DISCOVERY
1、临时FIB表（EFIB）
在NDN内容路由器设计中添加了一个临时FIB（EFIB）表。剩余的NDN路由器组件，即内容存储（CS），待定兴趣表（PIT）和转发信息库（FIB）的功能保持不变。
FIB记录producer的方向，EFIB记录cache的方向。
FIB使用路由协议，这些传输层协议都是使用带外数据（out-of-band，OOB）来发送数据（FIB不是本地填写的么？）
EFIB表使用从转发的data收集的本地可用信息来机会性地（见下文）填充
*类似于FIB和PIT条目，EFIB条目也遵循NDN的分层内容命名方案，其中内容项被分割成块并且每个块被唯一地识别（例如，音乐/艺术家/歌曲/块ID）；返回的数据包“携带”上述项目的任何组块（例如音乐/艺术家/歌曲/块ID / CID1）将触发相同形式的相应路由器的EFIB中的条目。
2、放置策略
从LCE到概率缓存。假设每个数据包在传递路径上只被缓存一次。缓存点是根据路径的缓存能力和给定路由器在网络中的相应位置决定的，类似于[13]。本文认为，多份复制是冗余的，而对interest进行的基于概率的搜索命中的概率很高、同时额外延迟很小。
3、data转发策略
每个data有一个PL flag，如果它是从AS外部producer处而来，则AS的边缘路由器将PL设置成0；如果它是从AS内部cache而来，则PL为1
当一个路由器R接收到一个data D时，路由器创建一个列表 = 该data对应的PIT表的所有请求面的并集 \ 该data到达面的并集（所有对R传递过interest for D而尚未返回、R又不曾对它发送过D的，这样的节点的集合）（需要刨去后半部分吗？前后两个集合不是交集始终为空么……）
具体流程图参见Figure 2
首先，路由器总会向列表中的每个节点发送data。
（1）若data的PL=1，即它是从一个cache返回的。发送data的同时，PIT条目被删除，并创建一个新的EFIB条目指向data来源的cache方向。本节点不会缓存它（因为不能重复缓存）。
（2）若data的PL=0，即它是从producer返回的，则相应的路由器根据ProbCache决定是否缓存该分组。还是向在请求列表中的每个节点发送该data。
- 如果路由器决定缓存数据包，则将PL设置为1，但是，路由器不会添加任何EFIB条目，因为它是缓存数据包的路由器，且一个根据EFIB或FIB表寻路的、路过的匹配的interest在这里能找到data，相应的EFIB路径（上行或下行）将在此路由器上终止。
- 如果决定不缓存数据包，PL设置为0。发送data的同时，创建一个新的EFIB条目指向data去往的用户方向：于是这个节点可能产生很多EFIB条目，描述同一个data，却指向不同的方向。
为了保证至少有一个节点cache了data，假设沿传递路径的最后一个路由器（即，用户发布interest的路由器所附着的路由器）总是缓存数据分组，即使它的PL等于0
4、interest转发策略
在Interest中引入一个Off-path Forwarding Flag（OFF）位。当它跟随FIB条目追踪producer时，设置OFF=0（on-path）；当它跟随经过的路由器的EFIB条目追踪cache时，设置OFF=1（off-path）。
具体流程图参见Figure 3
用户发出interest时，OFF默认值为0
（1）经过一个路由器时，如果找到匹配的data，返回data（PL=1），丢弃interest
（2）如果找不到匹配的data，但有匹配的PIT条目，则沿着PIT路径转发interest
（3）如果也没有匹配的PIT条目，但在EFIB表中有匹配条目，则移除相关的EFIB表项（因为cache返回data的时候又会经过这里，会创建新的EFIB表项，改成指向interest来的方向），设置OFF=1，沿着这些表项的方向发送多个off-path interest。
（4）或者在FIB表中有相关条目，像普通NDN一样找producer
注意到，如果完全多播，OFF=0、发往producer的interest将恰有一个
（这个机制能解决内容更新的问题吗？？？）
对于off-path interest（OFF=1）
步骤完全相同，只是不再搜索FIB表，因为不可能有相关条目；同时对于匹配的EFIB条目，不能再选择多播（多播的选择只有一次，防止interest泛滥）
（4）EFIB表也没有，则直接丢弃interest（还是有可能interest得不到返回）。这种情况的发生说明已经跟着EFIB表的路径走到了尽头（这时候不保证尽头一定有cache的内容了？），或者在interest到达之前匹配的条目已被替换/失效（参见第4.2节）。
（3）中发送多个off-path interest的策略可以是：同时给FIB和EFIB的所有项多播（优先保证interest能得到返回，开销大）；停-等地一个一个发，先发EFIB再发FIB（优先保证返回的是off-path）；本文的方法是两者的折中。
[28]还提出了范围化泛洪（scoped flooding）的方法，但是从NRR（Nearest Replica Routing）性能可以看出，平均需要6跳才能找到内容，所以泛洪范围应该小到6跳以内。除非在网络中放的data足够多，否则发的interest就太多了（我还没看这篇paper，先mark一下？？？）
4 MULTICAST STRATEGIES USING FORWARDING BUDGET
1、OFF=1的interest，对于匹配的EFIB条目，不能再选择多播（多播的选择只有一次，防止interest泛滥）
2、用预算来限制OFF=0的interest多播的上限数量
在interest中引入一个Total Forwarding Budget (TFB)
假设节点根据PIT表、FIB表、EFIB表知道距目标producer／cache的距离（可以按照跳数计算）。要转发interest，需要TFB>=节点对应EFIB。每产生一个off-path interest并发出、或转发interest的时候，TFB减去某个值（当然初始值足够减）
1、静态cost
为了避免协调，每个路由器能给予的TFB初值设置成常数，每产生一个off-path interest时，TFB减去一个常数b；off-path转发不需要消耗TFB，而on-path每转发一跳，TFB-=1。不考虑内容popularity或EFIB表项的新鲜度（即它在EFIB表中的位置）。实际上，popularity低的内容需要高的TFB值，也需要带外协调了解路由器的拓扑结构，分配不同的TFB初值。
假设距离producer为h跳，新创建的on-path interest的TFB初值为t=h+a，那么它最多可以创建[t/b]个off-path interest，给自己留的的TFB=0。最多的可行方案是创建[a/b]个off-path interest，给自己留够TFB=h。
本文中，不失一般性，允许中间节点根据最新鲜的EFIB表项，至多初始化一个off-path interest（开始说off-path interest转发不需要消耗TFB，但是现在强行改成重新创建一个最新鲜的EFIB表项的版本，所以又需要扣除TFB了？），即：进一步限制最多方案是创建[h/b]个off-path interest，给自己留TFB=a。（怎么算的？？？）
2、动态cost
即使是非常小的TFB值（即最短路径长度加上1或2的额外配额）仍然可以产生显著的开销和重复的响应。动态方案会考虑popularity
*参考AIMD原则：加性增大、乘性减小。这个方案中，找到EFIB表项说明内容越来越近了、线性增大cost；NACK说明内容还很远，乘性减小cost
路由器r的EFIB的每个索引i（是索引而不是索引的对应值，因为记录内容名称的开销太大）最初被分配了默认的cost=b[I,r]
每当由于在路由器r的索引i处找到匹配的EFIB条目而创建off-path interest时，索引i的cost增加了附加值d[I,r]。
后来传来的、由相同路由器的相同index的EFIB表项创建的off-path interest，其cost也会增加d[I,r]
假设一个路由器在EFIB表路线的尽头，它会返回对应的data或一个NACK。无效的情况下，中间路由器：（1）将在其EFIB中查找特定的内容名称，并将通过乘法参数e[I,r]降低匹配的EFIB索引的计费成本，然后沿着PIT表进一步转发NACK。（2）相应的EFIB条目将被移除（即，下面的EFIB条目将被移位一个更高的位置）
EFIB cost可能大于TFB值，动态方案认为，只要TFB大于0，最后一次总是够减的；减完以后TFB变成0，此后才不能再创建新的interest了
路径末端很可能返回NACK，几次乘法以后，cost会很快变得过小。要给cost设置一个lower-bound = 初始的b[I,r]
5 PERFORMANCE EVALUATION
Evaluation Setup and Metrics, EFIB capacity, AS Cache Capacity, Content Popularity, Forwarding Budget, the Additive Component
考察的指标
1、发现率：能够在用完转发预算之前发现内容的interest ／ 总interest
2、延迟：每次成功获取内容时的平均往返时间延迟
3、开销：第一个开销是每个interest对应的data副本的平均数量（理想值是1，本文认为，为了发布的兴趣检索额外的data副本是多余的）。第二个开销是平均兴趣跳数（这跟延迟是不是有点重复呢？）
转发参数设计：TFB = h+2, b = 1, b[I,r] = 1, d[I, r] = 1, e[I, r] = 2。这样设置的话，动态比起静态的差别就是多了乘性减小的环节。其他的可以参见Table 1.
效果：比起NDN默认的on-path机制，本文提出的基于预算的转发策略导致本地（即，内部AS）内容发现的性能增加了三倍以上，而多出的开销很小。另外，所提出的预算机制为用户实现了良好的QoS（即低延迟）。
本文认为，其总体性能非常接近于理论上最优的转发策略。