Linux 内核版本：5.4
1. 路由表 RIB 与转发表 FIB
在每一个路由器设备中，通常都维护了两张比较相似的表，分别为：
- 路由信息表（Routing Information Base），简称为RIB表、路由表
- 转发信息表（Forwarding Information Base）， 简称为FIB表、转发表
RIB 对每一种运行在该路由器的路由协议，他都会维护一张对应的 RIB，路由协议综合自己从其他节点获取的信息维护这张路由表。FIB 则用于配合路由器转发功能工作，将会综合所有路由协议的 RIB，根据设定的路由策略，选择一条最优路由。
当有数据包到该路由器的时候，会根据 FIB 的信息决定转发地址。而网络拓扑的改变会导致 RIB 的改变，再影响 FIB 的内容。
在 Linux 中不区分 FIB 与 RIB。
2. Linux路由子系统简介
2.1 路由子系统初始化
ipv4 路由代码的初始化从net/ipv4/route.c文件中的ip_rt_init开始，它在系统启动时被net/ipv4/ip_output.c文件中初始化 IP 子系统的ip_init调用。下图展示了如何调用主要的路由初始函数。
int __init ip_rt_init(void)
{
int cpu;
ip_idents = kmalloc_array(IP_IDENTS_SZ, sizeof(*ip_idents),
GFP_KERNEL);
if (!ip_idents)
panic("IP: failed to allocate ip_idents\n");
prandom_bytes(ip_idents, IP_IDENTS_SZ * sizeof(*ip_idents));
ip_tstamps = kcalloc(IP_IDENTS_SZ, sizeof(*ip_tstamps), GFP_KERNEL);
if (!ip_tstamps)
panic("IP: failed to allocate ip_tstamps\n");
for_each_possible_cpu(cpu) {
struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
INIT_LIST_HEAD(&ul->head);
spin_lock_init(&ul->lock);
}
#ifdef CONFIG_IP_ROUTE_CLASSID
ip_rt_acct = __alloc_percpu(256 * sizeof(struct ip_rt_acct), __alignof__(struct ip_rt_acct));
if (!ip_rt_acct)
panic("IP: failed to allocate ip_rt_acct\n");
#endif
ipv4_dst_ops.kmem_cachep =
kmem_cache_create("ip_dst_cache", sizeof(struct rtable), 0,
SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
ipv4_dst_blackhole_ops.kmem_cachep = ipv4_dst_ops.kmem_cachep;
if (dst_entries_init(&ipv4_dst_ops) < 0)
panic("IP: failed to allocate ipv4_dst_ops counter\n");
if (dst_entries_init(&ipv4_dst_blackhole_ops) < 0)
panic("IP: failed to allocate ipv4_dst_blackhole_ops counter\n");
ipv4_dst_ops.gc_thresh = ~0;
ip_rt_max_size = INT_MAX;
devinet_init();
ip_fib_init();
if (ip_rt_proc_init())
pr_err("Unable to create route proc files\n");
#ifdef CONFIG_XFRM
xfrm_init();
xfrm4_init();
#endif
rtnl_register(PF_INET, RTM_GETROUTE, inet_rtm_getroute, NULL,
RTNL_FLAG_DOIT_UNLOCKED);
#ifdef CONFIG_SYSCTL
register_pernet_subsys(&sysctl_route_ops);
#endif
register_pernet_subsys(&rt_genid_ops);
register_pernet_subsys(&ipv4_inetpeer_ops);
return 0;
}
void __init ip_fib_init(void)
{
fib_trie_init();
register_pernet_subsys(&fib_net_ops);
register_netdevice_notifier(&fib_netdev_notifier);
register_inetaddr_notifier(&fib_inetaddr_notifier);
rtnl_register(PF_INET, RTM_NEWROUTE, inet_rtm_newroute, NULL, 0);
rtnl_register(PF_INET, RTM_DELROUTE, inet_rtm_delroute, NULL, 0);
rtnl_register(PF_INET, RTM_GETROUTE, NULL, inet_dump_fib, 0);
}
2.2 路由表组织
在默认情况下，Linux 使用两张路由表：
- 一张用于本地地址（local）。从该表中查找成功表明交给主机自己。
- 一张表用于所有其他路由（main）。其数据项可由用户手工配置或由路由协议动态插入。
早期 Linux 使用哈希表来组织路由表，但是随着互联网规模的扩大，哈希表的性能已经越来越不稳定，且难以支持大规模的地址检索。后来 Linux 采用 FIB-trie（基于 LC-trie 的数据结构）组织的数据结构代替哈希表来存储 IP 地址，这个数据结构可以快速的查询和匹配 IP 地址。在 Linux 内核版本 3.1 中该结构被引入，现在 Linux 内核版本 5.4 已经完全放弃哈希表而采用 FIB-trie 结构。
2.3 高级路由
策略路由就是根据配置策略查找路由表，早期的 Linux 版本是不支持策略路由的，默认的查找策略就是先查找local表，找不到再继续查找main表。当支持策略路由功能时，内核最多可以配置255个路由表，这时候根据先匹配策略，匹配后再去查找该策略指定的路由表，内核最多支持32768张策略表，初始化的时候创建了local表、main表和default表。策略表按照优先级从高到低的顺序挂在一张链表上，优先级范围0~32767，数值越低优先级越高。
关于 Linux 策略路由及其他高级路由，待完成…
2.4 路由缓存
Linux 内核版本 3.6，移除了路由缓存，修改为下一跳缓存。
移除路由缓存，主要由于以下问题：
- 面临针对哈希算法的
ddos问题。 - 缓存出口设备是
p2p设备的路由项会降低性能。
在移除路由缓存以后，所有的数据包要想发送出去，必须查找路由表。过程可能会变成以下的逻辑：
dst = lookup_fib_table(skb);
dst_nexthop = alloc_entry(dst);
neigh = bind_neigh(dst_nexthop);
neigh.output(skb);
release_entry(dst_nexthop);
这种逻辑在协议栈的实现层面，出现了新的问题，即alloc/release会带来巨大的内存抖动。为此，从Linux 内核版本 3.6 开始，路由缓存不再缓存整个路由项，而是缓存路由表查找结果的下一跳，伪代码如下：
dst = lookup_fib_table(skb);
dst_nexthop = lookup_nh_cache(dst);
if dst_nexthop == NULL;
then
dst_nexthop = alloc_entry(dst);
if dst_nexthop.cache == true;
then
insert_into_nh_cache(dst_nexthop);
endif
endif
neigh = bind_neigh(dst_nexthop);
neigh.output(skb);
if dst_nexthop.cache == false
then
release_entry(dst_nexthop);
endif
值得注意的是，下一跳缓存并没有减少路由查找的开销，而是减少了内存分配/释放的开销。这是因为一个数据包在发送过程中，必须在路由查找结束后绑定一个下一跳结构体，然后绑定一个邻居，路由表只是一个静态表，数据通道没有权限修改它，它只是用来查找，协议栈必须用查找到的路由项信息来构造一个下一跳结构体，这个时候就体现了缓存下一跳的重要性，因为它减少了构造的开销。
