ICN论坛观后感3——Routing in NDN & Speculative Forwarding: A Lightweight Name-based Packet Forwarding Architecture

文献读后感 netlab 54℃ 0评论

[wang lan]Routing in NDN

Ndn路由与IP路由的不同点,根本不同是IP中间节点是不可见的、不可以选择的、不可以衡量成功(measure success),Ndn可以,而且Ndn 路由是IP 路由的扩展集,因为:1.路由面向名字(地址是一种特殊的名字);2. ndn路由有多个下一跳选择3. 并不是每个下一跳都指向所有的数据(生产者可能没有全部数据,链路可能会失效,节点可能有移动)。所以,IP中的任何路由模式都可以用在ndn中,但是必须加以改进来适应ndn设计模式。Ndn设计要考虑命名、安全和同步机制的问题。

ndn路由存在scalability的问题,比如fib表的大小有限。另外,如何设计路由算法使产生更少的路由更新, 跟最短路由算法很接近的性能?

第一阶段测试了Geographic routing(GEO)和Hyperbolic routing(HR)路由策略,GEO把坐标提取出来,根据坐标转发,在很小的拓扑里可以工作,在大拓扑里效果下降很快。HR将网络拓扑嵌入到Hyperbolic  space,重要的节点定义在中心,根据坐标计算距离。大部分时候性能不错,但有时候存在sub-optimal path的问题,选择的路由方向delay会更高。

第二阶段提出一种结合HR和GEO的方法Geohyperbolic routing(GH),有三个坐标,经度、纬度、净坐标(节点越重要,值越小),实验发现效果很好,但会遇到问题:比如从柏林到纽约,本来可以直接走,但因为上海是个重要节点,因此路径是柏林-上海-纽约,路径变长delay变大。

第三阶段改进为regionalized  Geohyperbolic routing(RGH),设置一些local hubs,尽量从local次要的节点获取包。效果很好,命中比率(success ratio)接近1,stretch接近1(RTT / 最短路径的RTT,这个指标最好的值是1).

 

[嵩天]Speculative Forwarding V2_A Lightweight Name-based Packet Forwarding Architecture(1)

问题:用name做forwarding,fib表会变得非常大,随着FIB表大小从Millions到Billions级增长,用以前的最长前缀匹配(LPM)方法代价会非常大,为了满足高速的look up和转发,减少资源的消耗,需要对fib进行优化。在最长前缀匹配(LPM)方法的基础上进行优化,提出最长前缀分类LPC)方法,主要针对Core Forwarding(处理大规模的fib,与边缘网络、物联网相对),希望fib在增大时也能scalability

LPM: 首先是Patricia Trie,用字节来存储token等,消耗非常大,假设有n个prefix,需要有2n个结点;第二种是Binary Patricia Trie可以把任何一个fib的table变成二进制表示,然后进行匹配,存储容量减少了三倍。发现memory 1/3用来表示trie结构,2/3用来表示token(做verification),所以考虑优化token,提出最长前缀分类(LPC)方法。

LPC: 将中心节点从token换成discrimination bit positions,记录的是一个名字从前到后是第几个位置,在该位置检测是0还是1,如果是0就走左子树,1走右子树。问题1LPM = LPC + Verification,LPC去掉了Verification,当fib里没找到该前缀对应的转发接口时,LPM就会drop掉该包,但LPC就会持续转发下去,所以在Core Forwarding使用Speculative Forwarding,边缘网络用其他的Forwarding,存储效率在之前的基础上又提高了2.6倍。实质上总体提高了10倍多。问题2LPC会对核心的网络造成override,为了进一步优化,在树的每个节点上加一个checksum(false positive为0.1),loop的概率降的极低,额外的hops可以忽略不计。

 

点击阅读原文更多信息

转载请注明:命名数据网络(NDN)中文社区 » ICN论坛观后感3——Routing in NDN & Speculative Forwarding: A Lightweight Name-based Packet Forwarding Architecture

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址