FIB查表路由查找LPM算法及实现

　　address长度是128bit，Ipv4 address长度的32bit。就地址长度而言，扩大4倍。就容量而言，扩大了2^96倍。IPv6 Address Lookup对路由器设备的挑战有多大，是比IPv4难4倍还是难40倍?当前路由设备对IPv6 FIB查表的支持程度竟究如何?本文从三层转发长匹配(LPM)出发，对比分析IPv6对路由器设备的带来的挑战难度。同时，根据LPM的实现，提出对现有设备IPv6 Address lookup及IPv6 FIB支持情况的测试用例的三原则：IPv6地址离散性、不同掩码长度，IPv6 Prefix有嵌套和分叉。同时，根据这三个原则对国内选型测试中常用的两例IPv6测试进行分析，指出其优点改进方向。后提出一个满足上述四个原则的测试用例脚本。

　　1.迎接IPv6时代—Are the Boxes Ready?

　　全球的IPv4地址即将用完，尤其是的地址为紧缺。另一方面，概念的提出，对IP地址的需求成N倍增长。因此，IPv6地址即将走上舞台。政府已经将Ipv6的推进提到国家战略的高度。的各大运营商也对应Ipv6演进纷纷采取大动作，例如宣布成为全球首家认证通过的IPv6宽带接入运营商。

　　近年来，国内外各设备运营商纷纷对路由器设备展开IPv6 Address Lookup能力的测试，以期望这些设备能在未来的IPv6商用络中发挥正常作用。测试的内容，主要考核点：IPv6 FIB容量、IPv6路由刷新性能、IPv6转发性能。

　　由于全世界IPv6并未大规模商用，IPv6路由分布和地址分配都存在较大变数。另一方面，IPv6地址容量大得足以给地球上每一粒沙子分配一个地址;而当前设备能处理的IPv6地址和前缀容量很有限，相对IPv6整个容量而言只能算沧海中的一小粟。因此，如何设计一个具备代表性的测试用例，以客观地评价设备对未来商用络的支持情况，就变成一个非常重要的。

　　IPv6 address长度是128bit，Ipv4

　　address长度的32bit。就地址长度而言，扩大4倍。就容量而言，扩大了2^96倍。IPv6 Address

　　Lookup对路由器设备的挑战有多大，是比IPv4难4倍还是难40倍?当前路由设备对IPv6 Address

　　Lookup支持程度究竟如何?当前这方面的分析很少。

　　众所周知，三层转发查找远远比二层转发要难。难度差别来源于三层转发的一个本质特殊：长匹配LPM。

　　2 路由查找LPM算法及实现

　　2.1 什么是长匹配LPM?

　　长匹配(Longest Prefix Match)是指如果一个IPv4地址与FIB表中的多个路由前缀(prefix)匹配，则以掩码长度长的前缀为终匹配结果。例如，一个路由器中有4条路由：

　　1) 1.*.*.*/8

　　2) 1.2.*.*/16

　　3) 1.2.3.*/24

　　4) 1.2.3.4/32

　　一个IPv4地址1.2.3.5在上述路由表中查找时，会与前3项前缀匹配上，与第4项匹配不上。匹配上的3个前缀中，1.2.3.*/24的掩码长，所以它就是长匹配结果。

　　为什么需求长匹配?这是因为prefix有嵌套。为什么Prefix有嵌套?是因为IP地址的分配方式引起。其中一个例子是：一个Tier

　　1运营商申请到一个A类地址，它将其中划分一小块批发给Tier 2运营商; Tier 2运营又会继续再划出一小块，分配给Tier

　　3运营商。这样，就发生了“路由前缀嵌套”现象。

　　理论上，IPv4地址多会嵌套24层(从8bit A类地址开始计算);这就是说，在路由转发查表时，一个IPv4地址多可能同时与24个前缀匹配上，此时设备要从24个前缀中选择一个佳前缀(掩码长为佳)。

　　2.2 LPM长匹配实现算法

　　二层MAC转发?表可以使用Hash算法(请见小师的Hash表介绍)，三层IP转发查表要使用长匹配LPM算法。前者是精确匹配，一个地址只会与转发

　　表中一个表项比对上;后者却是，一个IP地址与转发表中的多个表项同时匹配命中，并在匹配命中的多个表项中选择一个佳表项。正是这个多项匹配，造成

　　LPM算法的实现难度远远大于Hash算法，这是常说三层转发难度高于二层转发的主要原因之一。例如，一个Broadcom的以太单芯片，可以轻松支持

　　64K MAC地址表，但IPv4转发表只有8K量级。

　　LPM算法的基本实现原理是用Tree-based search。即

　　1) 将众多路由前缀构造成一棵树(Tree);

　　2) 当查找IP地址时，从树的根开始往下查找，每到一个分支点，就可以判断是否已经匹配上。如果已经匹配上，就先记录下来;

　　3) 继续往下走，直到没有进一步的匹配，或者已经到达树的顶端(即叶子);

　　4) 在多个匹配中的节点中，选择掩码长的。一般而言，越往下的节点，其掩码越长。

　　下图是一个1-bit binary trie树算法的原理图。大家看看，是否长得象一棵Orange Tree(倒过来)?

　　如果输入IP地址1111110000，则在该Tree中走法是：首先从根开始，命中P1;第1bit为1，往右走，命中P2;第2bit为1，再往右

　　走;

　　第3bit为1，往右走，命中P5，第4bit为1，该往右走，但发现右边没有路了，故查找结束。此过程中，P5/P2/P1都命中，但P5掩码长，故

　　匹配结果为P5。

　　实际上，从P2到P5只需要一步就可以完成，而不是2步。这是因为路径上没有分叉，走向是唯一的，这叫SKIP。

　　在上述1-bit binary trie搜索树的原理上，可优化出Multi-bit trie，Treebimap等算法。这些算法在当前路由设备中比较常见。

　　2.3 用1bit Trie搜索树实现IPv6查表的难度分析

　　IPv4有32bit，故用它构造成一棵1-bit Trie树时，高有32层。IPv6地址有128bit，故用它构造一棵1-bit Trie树时，高有128层。

　　从Trie搜索树的形状可以看出，如果树的分支层数越多，则搜索难度越大。如果每次查1bit，32层高的IPv4搜索树，需要查找32次;128层高的IPv6搜索树，需要查找128次。

　　当前房地产是热门话题，在此借用一下。IPv4查表之难度，就如修建一个32层的住宅楼;IPv6查表之难度，就如修建一座128层的摩天大楼。后者工作量和难度是前者的多少倍?应该不止4倍。

　　2.4 Multi-bit Trie算法

　　用1bit trie实现IPv6查表时，坏情况下需要访问128次RAM。显然这在硬件实现上不太现实，故在NP的Data path中，一般采用其变种形式: Multi-bit trie算法。

　　Multi-bit Tree搜索树的原理，是在1bit

　　trie的基础上，由每一步搜索1bit改为每一步搜索8bit(也可以是其它数字如4、或16)。这样，IPv4地址就分成8-8-8-8共4个

　　8bit段，需要访问4次DDR2 SDRAM或RLDRAM。IPv6地址分成8-8-8…8-8共16个8bit段，需要访问16次DDR2

　　SDRAM或RLDRAM。Multi-bit Tri的算法示意图如下：

　　在上述基础上，如果树的某个搜索路径上没有分支(即路由没有重叠嵌套)，则可用采用SKIP方法直接跳过，这样可以少搜索次数。以IPv6为例，好情

　　况是所有路由都没有嵌套，访问2次-3次DRAM就能找到终找到终结果;坏情况是路由有很多级嵌套发生，需要查找16次DRAM才能找到终结果。

　　Multi-bit Trie算法的另一个特点是采用段页式管理DRAM，将片外DRAM划分成一个个Page，每个Page可以正好存放256条连续的路由(2^8=256)。如果路由不连续，则坏情况一个Page只能放一条路由，此时容量大大减小。

　　2.5 Multi-bit Trie算法的特点

　　Multi-bit Tire算法(以及其派生算法如Tree bitmap, LC-trie)具备下述两个特点：

　　1) 路由容量不恒定。对+1、+2的连续路由容量大，对随机产生的路由则容量严重变小;

　　2) 性能不恒定。对没有嵌套路由性能好，对嵌套层数多的路由性能严重变差。这里的性能包括平面转发性能和控制平面刷新性能，因为路由插入时也需要查FIB表。

　　如果是让设备商测试方法，则它一定会聪明地选择下述路由来测试设备：使用+1递增路由以使容量大;使用不嵌套路由以使转发和刷新性能好。

　　3. IPv6 Address Lookup测试用例设计原则

　　3.1 三个测试原则

　　由于IPv6 Address Lookup的难度比IPv4高4倍以上，那么使用什么的用例才能充分检验Router设备的查表性能、路由刷新性能、

　　根据Trie搜索树的原理，可以归纳出下述测试用例设计：

　　1) IPv6地址离散性

　　IPv6地址容量巨大有如浩瀚之海洋，故IPv6前缀的选择尽量离散，以求有更大代表性;

　　2) 不同掩码长度

　　同IPv4的一样，IPv6地址也采用了层次化的分配方式，而且未来的层次化是否会出现CIDR这样的更细粒度的层次化还未可知。这导致需要不同的IPv6前缀长度。所以，在测试中尽量多采用各种前缀长度来测试，以应付未来可能出现的IPv6地址分配需求。

　　3) IPv6 Prefix有嵌套和分叉

　　这其实是层次化地址分配方式造成的必然结果。从LPM算法的实现原理看，Prefix嵌套层次越多，则构造出的树层高越高，搜索难度也就越大。所以，在测试用例中一定要考虑充分的路由嵌套。

　　如果站在搜索树的角度，上述原则可保证由IPv6 prefix构造成一棵枝盛叶茂的参天大树;

　　如果站在个房子的视角，上述原则可保证由IPv6 prefix构造成一座摩天大楼;

　　3.2 两则IPv6 FIB测试用例分析

　　根据上述三原则，下面选择国内大运营商用过的二个测试用例进行分析：

　　1) 用例A：几种IPv6前缀长度，+1递增路由

　　a) 不同的前缀长度的路由数量按照一定的比例设置;

　　b) 同一个前缀长度内的路由+1递增

　　c) 共50万IPv6路由

　　d) 路由分布如下所示：

　　2)用例B：随机前缀，前缀长度可配

　　在测试仪中，使用随机函数产生IPv6路由前缀。路由前缀的长度可配置

　　上述两个测试用例的共同大不足点，就是路由prefix没有嵌套，在查找中始终只会匹配一个表项，而不会同时命中多个表项，失去了LPM长匹配查表的本质特征。按三原则进行具体分析如下：

　　。

　　如果将A的前缀分布构建成一棵树，其形状比奇特，树干上没有分支，树梢上挂了很多果实。很象一株椰子树，是吧?这种树的搜索很简单，以Multi-bit

　　trie为例，只需要访2-3次外部RLDRAM：第一次，从几棵树中选中一棵，并直接到达树梢(因为树干没有任何分叉);第二步，从树梢的成千上万个果

　　实中摘取一个。第二步是比较简单的，接近于线性查表，这是因为路由前缀全部是+1递增，很紧凑地放在一起，且没有多项同时匹配的问题。

　　显然，测试用例A路由没有很好地考察路由设备的数据平面的查表性能;

　　不能很好地测试路由设备控制平面的刷新性能，因为在插入新路由时控制平面也需要查RIB/FIB表。IPv6查表理论上需要访问16次片外

　　RLDRAM(用8-bit Multi-bit Trie)，而上述路由分布只需要约3次RLDRAM访问。

　　测试用例A的另一个问题是：它不能客观检测设备的FIB极限容量，它测试的是设备的best case下的能力，而不是worst

　　case下的能力。这是因为设备在实现Search Tree算法时，为了实现方便，需要采用“段页式方法”将片外的DDR2

　　SDRAM或RLDRAM划分成很多Page，每个Page可放下256条连续的路由。如果路由是离散的，则坏情况下一个Page只能放1条路由。

　　测试用例B相对于用例A而言，有很大的改进，这是因为它的路由分布更离散，检测的FIB容量比较接近于Worst case。

　　4. IPv6 FIB lookup测试用例脚本参考

　　我们希望测试用例的Prefix构造出一棵参天的Orange

　　Tree，有很多树叉与分支，而不是树干象光棍一样的椰子树;我们希望测试用例的Prefix构造出一座摩天大楼，而不是只有一层楼高的联排或别墅。这

　　样，才能测试设备在Worst Case情况下的FIB容量、路由刷新性能、数据平面查表转发性能。

　　根据测试用例三原则，一个测试脚本用例如下：

　　#define MaxMaskLen=64 //需要测试的大路由掩码长度，取值24-128

　　#define Step=8 //掩码变化步进值

　　do{

　　P=rand(128bit IPv6单播Address) //产生一个随机地址(原则一：离散性)

　　if ( P/24 在FIB中不存在) //去掉重复路由

　　{

　　for( j=24; j<=MaxMaskLen; j++=Step) //(原则二：多种掩码长度)

　　{

　　INSERT FIB(P/j); //表示插入值为P前缀长度为j的路由(原则三：散成嵌套)

　　Q=P + 1<<(128-j);

　　INSERT FIB(Q/j ); //表示插入值为Q前缀长度为j的路由(原则三：散成分支)

　　}

　　}

　　}while (FIBv6容量未满)

　　上述算法只是个参考例子，实际使用时还可以进一步优化。

　　NE80E通过命令display ip routing-table verbose能看到NextHop、RelyNextHop，他们的区别是什么?display ip routing-table verbose命令显示如下：

　　Destination: 0.0.0.0/0

　　Protocol: BGP Process ID: 0

　　Preference: 100 Cost: 0

　　NextHop: 202.97.32.243 Interface: Pos2/0/0

　　RelyNextHop: 222.83.17.5 Neighbour: 202.97.32.243

　　Tunnel ID: 0x0 Label: NULL

　　State: Active Adv Derived Age: 00h44m09s

　　Tag: 0

　　其中NextHop表示路由表项的下一跳，RelyNextHop表示fib表实际转发的下一跳!

　　首先路由表和FIB是不同实体，作用也不一样。路由是上层协议来用的，Display ip routing显示的是协议添加路由时设置的下一跳，在路由表中称之为原始下一跳，这个下一跳不一定直接可达。而FIB是用于指导转发的，它的下一跳必须是直接可达。路由管理模块通过对路由的原始下一跳进行迭代找到这个直接下一跳，并将其设置到FIB当中来指导转发。