[Sigcomm14] Guarantee IP lookup performance with FIB explosion

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进行信息下移有点意思,后续可以思考能不能借鉴借鉴!

Leave a Reply

Your email address will not be published.