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

　　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等算法。这些算法在当前路由设备中比较常见。