IPv6 FIB路由查找及更新之挑战和测试原则

darktom168

内容概况：IPv6 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） 性能不恒定。对没有嵌套路由性能最好，对嵌套层数多的路由性能严重变差。这里的性能包括数据平面转发性能和控制平面刷新性能，因为路由插入时也需要App查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最长匹配查表的本质特征。按三原则进行具体分析如下：

	原则一IPv6离散性	原则二不同掩码长度	原则三Prefix嵌套和分支	Search Tree视角	建楼房视角	点评
用例A+1递增路由	不满足	满足	不满足	多果椰子树	联排	性能和容量测试不准确
用例B随机路由	满足	满足	不满足	单果椰子树	别墅	容量较好，性能测试不准确

。
如果将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容量未满）
上述算法只是个参考例子，实际使用时还可以进一步优化。