接《IP之routing（一）》

Two-level hashing(fib structure)

Routing cache的数据结构叫做rt_hash_table，它是rt_hash_bucket的一个数组，它中的每个数组元素都指向rtable的list，而rt_hash()的参数有3个：source ip、destination ip、服务类型。

如果发生routing cache miss，则Forwarding Information dataBase (FIB)将被search。Linux中可以存在多张routing table，而每个routing table被存放在叫做fib_table（如上图）的数据结构中。该结构中的tb_data指向fh_hash，它包含了一个hash数组fn_zones和一个指向fn_zone的指针fn_zone_list。fn_zones是一个长度为33的数组，fn_zones中的index表示前缀的长度，如fn_zones[16]表示fn_zones指向一个前缀为16的fn_zone结构。所有的fn_zone都被fn_zone_list链在一起，按照最长匹配的顺序来连接，即匹配最长的放在最前面。

fib_lookup()会调用每个talbe的tb_lookup()来search routing table，默认的tb_lookup()函数是fn_hash_lookup() (在 src/net/ipv4/fib_hash.c ),它会通过fn_zone_list来顺序的搜索routing table，如果匹配成功，则一定就是longest matching。

数组fn_zones的每一项都指向一个叫做fn_zone的结构，该结构包还一个指针fz_next(用于链接所有的fn_zone)和一个hash table，fz_hash。fz_hash的每一项是一个指向fib_node结构的指针。每个fib_node对应唯一一个子网，fn_key是子网的前缀，而output device 和 the next-hop router包含在fib_info中。

IP之routing（二）