日志
Fib表
|
FIB（fowarding information base）转发信息库
通过display fib命令显示信息为
Flag:
U:Usable G:Gateway H:Host B:Blackhole D:Dynamic S:Static
R:Reject E:Equal cost multi-path L:Generated by ARP or ESIS
Destination/Mask Nexthop Flag TimeStamp Interface
10.153.17.0/24 10.153.17.99 U t[0] Vlan-interface1
10.153.18.88/32 127.0.0.1 GHU t[0] InLoopBack0
10.153.18.0/24 10.153.18.88 U t[0] LoopBack0
10.153.17.99/32 127.0.0.1 GHU t[0] InLoopBack0
127.0.0.0/8 127.0.0.1 U t[0] InLoopBack0
fib表中各个字段分别为：
Destination/Mask ：目的地址和掩码
Nexthop ：下一跳地址，该地址是与路由器直连的地址。
Flag ：对该条转发信息性质描述
TimeStamp ：时间戳（这个不知道代表什么意思）？FIB项生成的时间。它不用于转发，但在分布式系统中可作为故障诊断与排错
时的参考信息，可以验证FIB项是否从主控板到I/O板定时刷新，同时还可以用于内部老化功能。
Interface ：转发的出接口
各个flag所代表的意思如下表：
表2-1 display fib命令显示信息表
|
字段 |
描述 |
|
Destination/Mask |
目的地址/掩码长度 |
|
Nexthop |
转发的下一跳地址 |
|
Flag |
标志： "U"——代表是路由UP，可用 "G"——代表是网关路由 "H"——代表是本机路由 "B"——代表是黑洞路由 "D"——代表是动态路由 "S"——代表是静态路由 "R"——代表是被拒绝的路由，不可用 “E”——代表是多路径等价路由 "L"——代表是由ARP或ESIS生成的路由 |
|
TimeStamp |
时间戳 |
|
Interface |
转发接口 |
路由器转发分组的关键是FIB表，在系统中报文转发时查找的是FIB表而非路由表。这是因为路由表表示所有的有效路由所形成的表现，并不指导转发，FIB表是网络层用来控制数据报发送的。
路由器转发分组的关键是FIB表，在系统中报文转发时查找的是FIB表而非路由表。这是因为路由表表示所有的有效路由所形成的表项，并不指导转发。FIB表是网络层用来控制数据报发送的。FIB中包含了路由器在转发报文时所必需的一组最小信息。
参考FIB详解：从数据结构方面来理解FIB表
宏CONFIG_IP_MULTIPLE_TABLES表示路由策略，当定义了该宏,也即意味着内核配置了“路由策略”。产生的最大的不同就是内核可以使用多达256张FIB。其实，这256张FIB在内核中的表示是一个全局数组：
struct fib_table *myfib_tables[RT_TABLE_MAX+1];
而宏RT_TABLE_MAX定义如下：
enum rt_class_t
{
RT_TABLE_UNSPEC=0,
RT_TABLE_DEFAULT=253,
RT_TABLE_MAIN=254,
RT_TABLE_LOCAL=255,
__RT_TABLE_MAX
};
#define RT_TABLE_MAX (__RT_TABLE_MAX - 1)
我们可以看到，虽然这张表多达256项，但枚举类型rt_class_t给出的表示最常用的也就三项，在系统初始化时，由内核配置生成的路由表只有RT_TABLE_MAIN，RT_TABLE_LOCAL两张。
main表中存放的是路由类型为RTN_UNICAST的所有路由项，即网关或直接连接的路由。在myfib_add_ifaddr函数中是这样添加
main表项的：对于某个网络设备接口的一个IP地址，如果目的地址的网络号不是零网络（网络号与子网号全为零），并且它是primary地址，同时，它
不是D类地址（网络号与子网号占32位）。最后一个条件是：它不是一个环回地址(device上有flag
IFF_LOOPBACK）。那么，就添加为main表项，如果是环回地址，则添加为local表的一个表项。
在我们的系统中，有两个已开启的网络设备接口eth0和lo，eth0上配置的primary
IP地址是172.16.48.2，所以，相应的，main表中就只有一项。为main表添加路由项的时候，该路由项的目的地址是子网内的所有主机（把主
机号部分字节清零），而对应于lo，在local表中也有一项，其类型为RTN_LOCAL(注：前一篇文章中的local表的hash
8中的路由项表述有误，类型应该是RTN_LOCAL，而不是RTN_BORADCAST)。
而其它的路由项全部归入local表，主要是广播路由项和本地路由项。在我们的系统环境下，local表共有7项，每个网络设备接口占三项。分别是本地地
址（源跟目的地址一致），子网广播地址（主机号全为1)，子网广播地址（主机号为零)。再加上一个lo的RTN_LOCAL项。
现在我们再来看myfib_add_ifaddr函数的路由添加策略。对于一个传入的ip地址（结构struct
in_ifaddr表示），如果它是secondary地址，首先要确保同一个网络设备接口上存在一个跟其同类型的primary地址(网络号与子网号完
全一致），因为，路由项的信息中的源地址全是primary的，secondary地址其实没有实际使用，它不会在路由表中产生路由项。然后，向
local表添加一项目的地址是它本身的，类型为RTN_LOCAL的路由项；如果该ip地址结构中存在广播地址，并且不是受限广播地址
(255.255.255.255)，那么向local表添加一个广播路由项；然后，对符合加入main表的条件进行判断，如果符合，除了加入main
表，最后，如果不是D类地址，还要加入两个广播地址（其实，已经跟前面有重叠，很多情况下不会实际触发加入的动作，只要记住，一个ip地址项对应最多有两
个广播地址就可以了）。
下面我们来看FIB的数据结构。一张FIB在内核中被表示为一个对象struct
fib_table，之所以说它是一个对象，而不是一个结构，是因为它不仅仅是一组数据集合，它还包含了定义在该对象之上的方法，包括表项的插入，查找，
删除，刷新等等。下面是其定义：
struct fib_table {
unsigned char tb_id;
unsigned tb_stamp;
int (*tb_lookup)(struct fib_table *tb,
const struct flowi *flp, struct fib_result *res);
int (*tb_insert)(struct fib_table *table, struct rtmsg *r,
struct kern_rta *rta, struct nlmsghdr *n,
struct netlink_skb_parms *req);
int (*tb_delete)(struct fib_table *table, struct rtmsg *r,
struct kern_rta *rta, struct nlmsghdr *n,
struct netlink_skb_parms *req);
int (*tb_dump)(struct fib_table *table, struct sk_buff *skb,
struct netlink_callback *cb);
int (*tb_flush)(struct fib_table *table);
void (*tb_select_default)(struct fib_table *table,
const struct flowi *flp, struct fib_result *res);
unsigned char tb_data[0];
};
这些成员函数我们在分析代码时都会提供其完整的实现，现在重点关注其数据成员。tb_id表明该表的用途(RT_TABLE_LOCAL，
RT_TABLE_MAIN等），同时也表明它在全局数组myfib_tables中的位置（RT_TABLE_LOCAL==255，
RT_TABLE_MAIN==254）。tb_data是一个很重要的数据成员，它包含了所在FIB的全部路由信息，可能会有点令人费>，因为它
的类型仅仅是一个unsigned char的数组而已，甚至更奇怪的是，它的长度是零，也就是说，根本不存在。看了下面的代码就可以明了：
struct fib_table *tb = kmalloc( sizeof(struct fib_table)
+ sizeof(struct fn_hash), GFP_KERNEL );
memset( tb->tb_data, 0, sizeof(struct fn_hash) );
所以，tb_data实际上是一个指向结构struct fn_hash的指针。下面是结构struct fn_hash的定义：
struct fn_hash{
struct fn_zone *fn_zones[33];
struct fn_zone *fn_zone_list;
};
在解释struct fn_hash之前，先看一下strut fn_zone：
struct fn_zone{
struct fn_zone *fz_next;
struct hlist_head *fz_hash;
int fz_nent;
int fz_divisor;
u32 fz_hashmask;
int fz_order;
u32 fz_mask;
};
这是一个区域，所有目的地址长度相同的路由项划入同一个区域，以链表的形式组织在fz_hash成员中，同时，fz_order记录目的地址长度，
fz_mask为目的地址掩码（比如：fz_order为24,则fz_mask为ffffff）。比如，在我们的系统配置环境中，两个网络设备接口有共
七个路由项。其中的6项，其目的地址长度为6，归入同一个zone中，放在fz_hash成员中。成员fz_nent表明该zone中的路由项的数量，为
6。fz_hash其实是一个哈项数组，共有fz_divisor项（初始为16），fz_hashmask为数组的掩码（初始为f)。路由项以目的IP
地址为主键，定位到数组的某一项。
对于ipv4来讲，目的地址不会超过32位，所以fz_order的取值范围是0-32。所以，struct
fn_hash中fn_zones被定义为一个具有33项的数组，对应33个区域。在我们的配置系统中，fn_zones[32]和fn_zones
[8]被用到了。同时，fn_zone_list把fn_zones中的已创建出来的zone按fz_order从大到小的顺序组织成一个链表。这些做法
都是出于效率的考虑。
所以，fn_hash是一个组织路由域的数据结构，同一个域里的fn_zone通过fz_next组织成一个链表。
同一个域中，所有的路由项组织在哈希表fz_hash中，一个路由项由结构struct fib_node表示。下面是该结构的定义：
struct fib_node {
struct hlist_node fn_hash;
struct list_head fn_alias;
u32 fn_key;
};
fn_hash用于在zone中组织链表，关于内核的一些基本数据结构，我们将专门进行分析，这里不再赘述。fn_key即目的地址IP，
fn_alias指向一个结构体struct fib_alias的链表，下面是结构struct fib_alias的定义：
struct fib_alias {
struct list_head fa_list;
struct rcu_head rcu;
struct fib_info *fa_info;
u8 fa_tos;
u8 fa_type;
u8 fa_scope;
u8 fa_state;
};
fa_tos表示服务类型，一般为0，即一般服务；fa_type的值在我们的系统中为RTN_LOCAL,
RTN_UNICAST和RTN_BORADCAST。fa_scope其实表示的是到目的地址的距离，对本地接收来说，就是
RT_SCOPE_HOST,对子网内广播和子网内其它地址来说，就是RT_SCOPE_LINK。fa_state只有在本地接收时，为
FA_S_ACCESSED，其它暂无定义。
fa_info作为struct fib_alias的成员，含有更为详细的路由项信息。下面是其定义：
struct fib_info {
struct hlist_node fib_hash;
struct hlist_node fib_lhash;
int fib_treeref;
atomic_t fib_clntref;
int fib_dead;
unsigned fib_flags;
int fib_protocol;
u32 fib_prefsrc;
u32 fib_priority;
u32 fib_metrics[RTAX_MAX];
#define fib_mtu fib_metrics[RTAX_MTU-1]
#define fib_window fib_metrics[RTAX_WINDOW-1]
#define fib_rtt fib_metrics[RTAX_RTT-1]
#define fib_advmss fib_metrics[RTAX_ADVMSS-1]
int fib_nhs;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int fib_power;
#endif
#ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
u32 fib_mp_alg;
#endif
struct fib_nh fib_nh[0];
#define fib_dev fib_nh[0].nh_dev
};
fib_treeref表示本路由信息项在struct
fib_table结构的整个树型结构中被引用的次数，而fib_clntref是另一个引用计数。fib_dead表示本项当前是否是活的。
fib_protocol表示该路由信息是通过什么途径建立起来的，其可能有取值有：
#define RTPROT_UNSPEC 0
#define RTPROT_REDIRECT 1 //该路由是由ICMP重定义安装的。
#define RTPROT_KERNEL 2 //该路由是由内核安装的。
#define RTPROT_BOOT 3 3 //该路由是在系统启动时安装的。
#define RTPROT_STATIC 4 //该路由是由管理员安装的。
除此之外，还有一些取值，不过是用于用户态的，我们当前在模块初始化过程中安装的路由都是RTPROT_KERNEL的。fib_prefsrc是我们的
local地址。最后，fib_nh是一个结构struct
fib_nh的的数组，数组的大小由fib_nhs决定。该结构表示路由中的下一跳，下面是其定义：
struct fib_nh {
struct net_device *nh_dev;
struct hlist_node nh_hash;
struct fib_info *nh_parent;
unsigned nh_flags;
unsigned char nh_scope;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int nh_weight;
int nh_power;
#endif
#ifdef CONFIG_NET_CLS_ROUTE
__u32 nh_tclassid;
#endif
int nh_oif;
u32 nh_gw;
};
1. 我想知道三层交换的交换过程。交换机接收到PCA发送过来的一个数据包，发现含有三层IP信息，于是发送给自己的路由模块，端口指向三层模块的端口，MAC地址也是三层模块的MAC地址。这是第一步，有错吗？
-----------------------------------
这一步没有错。只是一点要注意，其实交换机只有1个MAC地址，不管是三层模块还是什么都只有一个MAC。可能你在查接口的时候发现每个接口都有对应的MAC，但是那个只是用来区分端口的。实际机身MAC只有一个。
===============================================================
2.经过查看FIB表，不是已经知道了，要从哪个接口发出数据，发到什么MAC吗？
FIB表记录的主要是记录路由信息，在FIB表获取到下一跳地址，然后去邻接表是查找下一跳地址对应的MAC，进行rewrite
MAC地址，实现转发。这个过程其实很快的。也可以理解成FIB和ADJ表是同时运作。如果不理解你可以想想EIGRP的拓扑表和邻居表，OSPF的
Database和邻居表，也是这样的运作原理。
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等算法。这些算法在当前路由设备中比较常见。
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最长匹配查表的本质特征。按三原则进行具体分析如下：
| 原则一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容量未满）
上述算法只是个参考例子，实际使用时还可以进一步优化。
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当中来指导转发。
RIB表与FIB表、ARP表与FDB表
1.RIB与FIB的区别：
RIB：路由表
FIB：转发信息表
FIB 表更多是出现在需要快速转发的路由器上，这种路由器上的路由表条目通常都达成千上万条，如果按照传统的检索路由表进行转发的方式，其转发效率很低，FIB 表作为路由表的一种精简形式出现，通常只记录常用的表项。当需要选路时，先检索FIB表，如果找不到再检索路由表。
在大部分路由器中，RIB表现为路由表的形式， FIB则表现为高速缓存的形式，此在内容上是路由表的一个子集，是依靠路由表来生成的。
一般来说，FIB是进行高速查找而组织的数据结构（不是简单的把路由表中的内容复制出来，数据存储和检索方式等都不同于路由表的组成像是）。
RIB 就一个字：全，知道到所有的地方怎么走，但是速度慢。
FIB就一个字：快，只知道常走的路怎么走，速度快。
如果是分布式设备，通常FIB分布在LPU上，由LPU上的cpu实现快速选路，如果在LPU找不到路，才上到MPU处理，这里的RIB保存了最全的路由信息，可以提供不常用的选路结果。
2.ARP表和FDB表的区别：
ARP表：IP和MAC的对应关系；
FDB表：MAC+VLAN和PORT的对应关系；
两个最大的区别在于ARP是三层转发，FDB是用于二层转发。也就是说，就算两个设备不在一个网段或者压根没配IP，只要两者之间的链路层是连通的，就可以通过FDB表进行数据的转发！
FDB表的最主要的作用就是在于交换机二层选路，试想，如果仅仅有ARP表，没有FDB表，就好像只知道地名和方位，而不知道经过哪条路才能到达目的地，设备是无法正常工作的。FDB表的作用就在于告诉设备从某个端口出去就可以到某个目的MAC。
那么FDB表是怎么形成的呢？很简单，交换机会在收到数据帧时，提取数据帧中的源MAC、VLAN和接收数据帧的端口等组成FDB表的条目。当下次有到该VLAN中的该MAC的报文就直接从该端口丢出去就OK了。
当然，FDB表和ARP表一样，都有一个老化时间。
| 标题：TCAM表和FIB表有什么关系？ 作者：yeelone 时间：2010-12-12 19:52 | |
| [font=宋体,]我想问个问题，我一直对CAM表和TCAM表不太理解，CAM表是二层
的，TCAM表是三层，平常我们在二层交换机上不是查找ARP表吗？在三层交换机上不是查找FIB表吗？现在又说是查找TCAM表？所以，我想问的
是，CAM和ARP表有什么关系？TCAM表和FIB表有什么关系？ 关于TCAM，是不是交换机计算出了FIB表后，就用FIB的条目去填充TCAM内存表，然后TCAM还会加入一些ACL和QOS的控制信息。 不知道这样理解对不对？ 我就是有一点很不清楚，以前看书时是说，三层交换机是查找FIB表和ARP表来进行转发。学到后面又说是查找TCAM表。我就不明白两者之间是什么关系？要如何应用？[/font] |
|
| 标题： 作者：独钩寒江雪 时间：2010-12-12 22:43 | |
| 二层交换中catalyst交换机使用CAM(内容可描述内存)表，当帧到达交换机端口，交换机主动学习源MAC地址并
记录在CAM表中，同时记录了到达的端口号、VLAN和时间戳。如果在一个端口学习到的MAC地址到达了另一个端口，前一条CAM表中的记录会被删掉，新
增一条最近的记录。如果CAM表中已记录的MAC地址到达原来相同的端口，仅仅修改CAM表记录的时间戳。 交换机通常拥有很大的CAM表以便在帧转发时用来查询，然而，在大的网络上没有足够的空间来容纳所有可能的地址，为合理管理CAM表的空间，过时的条目会在一段时间后失效，默认情况下，如在300秒内没有相同源MAC的帧到达，CAM表中的条目会被删除。 当主机的MAC地址在交换机的端口被学习到，而后主机移动到另一个交换机端口去了，当新端口得知了这个地址，主机原先对应的CAM表条目会在300秒后超时失效，但为避免有重复的CAM条目，交换机会肃清先前的一个条目。因为MAC地址的唯一性，这是一种安全的猜测。 在传统的路由中，ACL能匹配、过滤或控制特定的数据流，ACL是由一或多个存取控制条目(ACE)或匹配语句组成的，根据ACL来检查可能占用额外的时间，增加转发数据包的延迟。 然而在多层交换机中，所有的ACL的匹配过程是通过硬件实现的，TCAM允许根据整个控制列表在一次简单的表查询中检查数据包，多数交换机都有多个的TCAM表以便可以同时根据多个ACL检查数据包，甚至允许二层和三层的转发决策完全并行地进行。 TCAM是CAM表概念的一种扩展，在CAM表中使用索引(或称为关键值、通常是MAC地址)查找结果值(通常是端口号或VLAN号)，TCAM同样使用 表查找操作，但被改进并可以完成更复杂的操作。TCAM条目由VALUE、MASK、RESULT(VMR)组成，帧或数据包头部的内容被放到TCAM 表，在TCAM表中根据值和掩码的组合来匹配产生结果。 CAM表 存贮着与VLAN相结合的物理端口上的有效的MAC地址 FIB表 是在MPLS中解释说的基于CEF所产生的路由表 T CAM表 主要用于快速查找ACL、路由等表项。它是从CAM的基础上发展而来的。 A R P表 实现通过IP地址得知其物理地址 |
/1 
eetop公众号
创芯大讲堂
创芯人才网