Paper:Sail_paper.pdf  Slide:Sail_slide.ppt  Source Code: Sail

总结：

本文总结：本文的出发点是两个：第一，片上访问速度是片外的十倍，因此要尽可能片上查找；第二，FIB表不断增加，如何确保算法的低片上内存消耗及较少片上访问次数不受影响。作者的观察是大部分地址都是0-24前缀，基于这一观察提出了二次划分算法SAIL，第一划分是将查找过程分为两部分，即前缀查找（0-24前缀在片上查找）与下一跳查找（片外查找）；第二划分是路由表划分为0-24前缀（片上查找）与25-32前缀（片外查找）。对于0-24前缀的片上查找，作者提出了为每一层使用比特数组来做指示（根节点1个bit，下一层2个bit，再下一层4个bit…8个bit,16个bit,32个bit…16777216个bit，所有比特数组加起来约4M），查找过程分为两部分，第一部分是匹配结果在0-24的前缀的，查找从最后一个比特数组（24层）依次向上查找（取相应层的IP地址位作为比特数组查找索引），只要发现IP地址与相应索引值对应位指示值为1，意味着匹配成功，根据LPM原则这就是最佳匹配结果，然后去片外对应层的下一跳数组取出下一跳即可；第二部分是匹配结果在25-32的前缀的，则片外采用连续数组即可；这是SAIL Basic算法，最坏要25次片上访存。为了消除上述两部分查找（地址落在0-24的前缀和25-32的前缀），作者提出了pivot push改进，即将第24层的非叶子节点信息下移，从而通过第24层的一次对比就可以知道最佳前缀是在0-24的前缀部分和25-32的前缀部分。为了改进算法性能，作者将SAIL Basic算法一次划层（第24层）改为了两次划层（第16层和第24层，处理方式类似），实现了最坏两次片上访存。

本文思考：1、比特数组是个好东西，内存占用小且可一次访问得到结果，低内存设计神器，sigcomm15的poptrie就是例子；2、单次映射存在内存或性能问题可以考虑多次映射，RFC就是一个例子；3、本文的pivot push进行信息下移有点意思，后续可以思考能不能借鉴借鉴！