[Lemei Huang-Notes] On Broadcast-based Self-Learning in Named Data Networking

2017-10-10

Posted by 黄乐玫

Issue

在NDN里使用Self-learning的方式来维护FIB表，应用场景是wired LAN

Problem

在NDN里使用broadcast-learning方式的方法没有关注的问题，一是prefix粒度问题，二是安全问题，三是off-path cache的利用问题

prefix粒度的问题

prefix粒度问题。

prefix粒度问题：比如一个/A/B/C的Intrest被广播然后返回对应内容，Data包返回的时候需要建立相应FIB entry，那到底是建立/（粒度大）、/A、/A/B、/A/B/C（粒度小）里哪个呢？

  • 粒度选择太小，会让producer失去很多本来能在它处命中的Interest；粒度选择太大，会出现Interest路由到指定producer后miss

  • 有三种解决方式：

    1. k-shorter：固定剪掉尾巴上k个component。缺点是k不好界定，取决于application

    2. FIB Aggregtion：router根据自己FIB里的表项合并一些表项。缺点是聚合算法需要时间，并且每级的内容数是无限的，合并出现Interest miss时还需要解聚合。

      比如，FIB里/A/B和/A/C都通过接口i，于是被合并成/A-i了，但是新来一个/A/D，可能会走/A-i，就可能找不到。

    3. prefix anouncement：即将建立的FIB entry的prefix放在数据包里。

安全问题

安全问题主要是producer spoofing。

ARP spoofing：ARP是链路层把IP地址对应到MAC地址的协议，它采用的方法是广播询问，等对应的回应它。ARP协议很单纯，只要接到回应就把它当成真的，所以存在有坏人使用假回应使数据传到别的MAC地址上的可能，称为ARP spoofing。

producer spoofing：同理，NDN的broadcast-learning也存在有人假装返回一个对应的Data包，然后让FIB建立假entry的可能。
解决的思路是，需要确保：

  1. 这个Data包里的prefix anouncement一定是被可靠的producer塞进去的。
  2. 这个prefix anouncement里指定的prefix一定是最初被可靠producer塞进去的那个。
  3. 1和2确保了prefix anouncement是合法的。此外，还需要确定发布这个prefix anouncement的Data包一定是对应了一个Interest请求的Data包【而不是别人用合法prefix anouncement伪造返回的】。

off-path cache

broadcast-learning能建立点-点之间的route，Interest和Data都沿着路由路径走，所以只利用到了on-path的cache，如何在broadcast-learning法下利用off-path的cacche。

相关工作

在传统IP网络里的broadcast-learning

主要在两个场景下使用：交换以太网和AD HOC路由

交换以太网

见《计算机网络》4.8.2节

  • 后向学习：如果A收到一个从i来C发出的包，它就学习到【可以从i去C】
  • 以太网交换机如果已经学习到具体接口，就向学习到的接口转发；否则泛洪。
  • 为了适应网络变化，每个学习到的表项有一个expire time

Bridge Loop

交换机无法判断帧是否相同，因此当A,B之间有多条链路时（假设2条），从A-1-B的帧会被泛洪从B-2-A返回，由于A没有学习到记录，该帧又会被泛洪从A-1-B到B，如此循环。

  • 交换以太网里使用生成树，直接ban掉冗余链路：1. 确定一个根 2. 广播到根的距离，确定生成树，有点像DV算法

AODV（Ad hoc按需距离矢量）

见《计算机网络》5.2.11节

主动发路由请求找路径，根据路由应答学习。

  • 按需：只有要发消息的时候才找路径
  • 在覆盖范围内的节点都能通信，相当于有边相连
  • 要发信息的节点先发【路由请求】包，目标节点返回【路由应答】包，请求包泛洪，应答包单播返回。

    大型网络中可以设置TTL，减少泛洪包：先设为1，没有返回再设为2……

  • 维护：周期性地发送HELLO包，【HELLO包没有响应】或者【发送数据包没有响应】=》link failure，然后删除自己路由表里要走这条link的表项，再通知它的活跃邻居也删除，活跃邻居再通知活跃邻居……
  • 快收敛：维护一个序号，目标节点每发送一个路由应答就增加一次序号。节点只采用更高序号的路由，或者相同序号下更少跳的。路由请求里带一个【它认为的】【当前已有的】【最高】序号，如果存在序号更高的路由就停止广播这个请求。
  • 路由请求也可以被聚合，由已有路由记录的中间节点返回路由应答。

NDN里的broadcast-learning

分两类：

  1. on-demand：泛洪的是Interest
  2. not-on-demand：泛洪的是其它消息，只是使用self-learning来建立路由（为什么不用第1种？是因为建立路由的消息比Interest小吗？）

LFBL

参考自AODV和CSMA

  • 应用：动态无线网
  • 学习好了就点对点单播，没学习好或者学习好的信息失效了就广播发Interest【无线网里就是在范围内的都发给它】
  • 每个节点收到请求时：
    1. 判断自己：是否距离目标，比发来请求那个点更近
    2. 如果是，等一会，看是否有其它节点响应，每个节点的等待时间不一样，根据情况调节。（随机/分组随机/Distance-Variance-Random）
    3. 如果没有节点响应，自己响应

sCDN

  • 应用：MANET，背景是空间站之间的AD HOC，self-learning的算法sCDN是它们提出的框架的一部分
  • sCDN：先使用self-learning建立一个DAG（即路由的routes），然后按DAG路由内容请求。

RONR

  • 应用：IOT
  • 广播Interest，根据Data返回的路径来学习，返回建立路径的时候固定剪掉一个component。

使用prefix anouncement的相关工作

  • 提到上上次讨论的那个车辆网络，它的prefix anouncement是由Consumer放在Interest里的。
  • 这是因为车辆网络的应用是特别的，节点知道命名规则，所以它的Consumer知道它要取得的内容的prefix。比如说，如果consumer需要/A/B和/A/C，节点是能够知道只要取/A就好，它就把/A放在Interest里。
  • 这个方法的问题:普适网络里命名规则不统一，consumer不会知道producer的prefix。

安全问题的相关工作

使用routing protocol的NDN协议里的安全认证

就是NLSR的trust model。
主要在于LSA的认证，采用分层认证的方式：network root-sites-operators-routers-NLSR进程。上一层给下一层加签名，下一层由上一层认证。
举例子，每个NLSR进程发出的LSA，都有NLSR进程的签名，为了验证这个签名，需要NLSR进程的key，而NLSR进程的key是由这个NLSR进程所属的router签过名的，因此为了知道获得的key是不是合法key，还要得到router的key，……逐层验证，最后由network root验证。

对应用数据的安全认证

  1. challenge-response：在Interest里加上随机码，返回的Data包里的prefix anouncement要与这个随机码匹配。
    缺点在于：合法的Data包只能从prefix处返回了。因为Cache里缓存下来的Data包的prefix anouncement里的那个随机码对应的是它自己的那个Interest，如果有新的Interest命中这个Data包，随机码肯定对不上。
  2. trust schema：主要思想是建立一系列trust rules，把data name和相应的key name对应起来，trust rules建立的认证链最后归结到trust anchor上。也就是data name+trust rules=》key name，得到key name之后可以获取key，得到key之后就可以认证了。

off-path cache的相关工作

两种都是类似于记录downstream接口的，这是off-path的一种，大概分类上可以算【off-path×implict×traffic redundancy】这类的吧。

面包屑

很久之前看过这篇，Data包返回时留下面包屑，即Data经过中间节点A，由接口i向consumer返回时，A记录下i也可能可以找到Data这个信息，同时这条信息有个时间戳。
与本文的区别是：Interest是走FIB还是走面包屑去cache里找，面包屑是通过判断该接口时间戳是否够近，而本文是判断在Data向该接口走去后有多少其他Data也向该接口走去了。

D-FIB

D-FIB也是记录下downstream接口。
与面包屑和本文不同的是：它同时走FIB和downstream，同时设置一个计数器记录到FIB上终点的距离，作为走downstream的Interest的TTL，省得那些Interest从离source更远的地方获得内容。

本文

  1. prefix粒度使用prefix anouncement解决
  2. 使用的anouncement认证：与routing-based类似，producer发布prefix的时候需要由它的operator向网络管理者请求一个证书，producer会利用这个证书给它的prefix anouncement签名。收到prefix anouncement的节点，则可以如同routing-based那样层层验证。
    此外，router的证书与它发布的prefix有关，也就是每个[router,prefix]一个证书，验证的时候还要验证证书是不是对应prefix anouncement里的prefix的。
  3. 使用的应用数据认证：使用trust schema，把对prefix anouncement宣称的prefix下的所有Data包的认证的trust rules放在prefix anouncement里。
    • 如果prefix anouncement是合法的，但是Data是假的，通过prefix anouncement的rules就能验证出来
    • 如果在Cache里被hit中，返回的Data包既有名字也有trust rules，很容易就能验证是合法的。
  4. FIB建立：broadcast-learning
  5. FIB维护：类似于AODV的一直发HELLO message的机制来检测link failure。
    • 有nonce，不需要像以太网那样使用生成树来避免循环。
    • 只有consumer决定是否广播，而不是每个节点都能决定广播，减少广播的包数量。
  6. off-path cache优化：记录下每个内容的Data包的下一跳接口集合，这些接口方向的cache里可能会找到对应内容。然后也记录下每个接口在这个Data包去过之后又有多少Data包去，设该值为n，n越小，后来的Interest越可能转道去找off-path的内容。

实验

比较了三个对象：

  1. broadcast：只广播不学习，没有off-path cache优化
  2. RONR：使用的prefix粒度处理是1-shorter，且无off-path cache优化
  3. Ethernet方式：FIB建立完全使用Ethernet的方法，区别在于这个方法有生成树，并且也没有off-path优化。

问题与思考

  1. 为什么把场景设成wired LAN？
    我的理解是：

    • wired：没有复杂的移动，感觉是不是面包屑这种在mobility强的时候就不好用了；带宽相对较高，丢包和拥塞都较少，条件比较理想。
    • LAN：为了统一管理prefix anouncement的key；为了体现off-path cache对域外流量减小的支持；且LAN网络小，拓扑简单。

  2. 感觉实验设计有些问题
    感觉变量控制得不是很好？off-path cache那部分和broadcast-learning那部分是两个模块
    比如说，跟1比，比1好，到底是学习好，还是off-path cache好？
    跟2比，到底是它的self-learning粒度处理得好，还是off-path好？
    跟3比，到底是它的nonce方式好，还是off-path cache好？

    • 它在比forwarding metrics的时候没有说它的NDN-self-learning是不是带off-path cache优化这个版本的，而它在比cache性能的时候就没有比较对象了，也没跟他提到的两个相关工作比。

最后，我怎么觉得把IP里的各种东西想办法套到NDN里就是一篇文章……