首页 > 代码库 > 路由表学习笔记
路由表学习笔记
路由子系统的核心是转发信息库(Forwarding Information Base,FIB),即路由表。路由表是用来存储这样一些信息的：一是用以确定输入数据是应该上传给本机的上层协议还是继续转发的信息；二是如果需要转发，为转发数据报提供所需要信息；三是输出数据报应该从哪个具体的网络设备输出的信息
路由表项的维护以及查找涉及以下文件：
include/net/ip_fib.h 定义路由表等结构、宏和函数原型
net/ipv4/fib_lookup.h 定义路由查找的相关函数原型
net/ipv4/fib_hash.c 实现路由表的查找和维护
net/ipv4/fib_frontend.c 实现操作路由表的接口函数和通知
net/ipv4/route.c 实现路由缓存项的操作函数
路由要素：
(1)路由表
路由表是一个由路由表项组成的数据库，并为诸如IPv4等其他子系统提供了多种接口，其中最重要的接口就是路由查找
(2)作用范围
IP地址和路由都有作用范围，用于说明它们在哪些情况下是有意义并可以被使用的。IP地址的作用范围表示该IP地址距离本地主机由多远，而路由的作用范围表示到目的网络的距离。
IP地址的作用范围 描述
Host 当一个地址只用于主机自身内部通信时，作用范围为Host,该地址在主机以外不可知 并且不能被使用。例如环回地址127.0.0.1
Link 当一个地址只在一个局域网(即每台计算机通过链路层互联的一个网络)内有意义且只 在局域网内使用时，该地址的作用范围为Link。例如子网的广播地址。子网内一台主 机发送到子网广播地址的数据报被送给同一子网内的其他主机
Universe 当一个地址可以在任何地方使用时作用范围为universe，这是大多数地址的默认 scope
路由的作用范围 描述
Host 当一条路由使目的地址为本地主机时，作用范围为host
Link 当一条路由使目的地址为本地网络是，作用范围为Link
Universe 当一条路由使目的地址超过一跳时，作用范围为universe
(3)默认网关
默认网关通常是指0.0.0.0/0路由，当到一个目的地址不存在明确的路由项时使用该路由。
(4)特殊路由
当主机收到一个数据报后，路由子系统需要决定将它上传给本地上层协议还是继续转发出去。因此在路由子系统中，有两张特殊的路由表：
一张表用于本地地址，存储了所有的本地地址，如果在该表中能查到匹配表项，则表明数据报是发给本机的
一张表用于所有其他的路由，路由表项由用户手工静态配置或由路由协议动态配置
在路由查找时先扫描本地路由表，只有当查找该表未果的情况下，才会去查找另一路由表，以确定是否可以转发。
路由缓存
一个路由表中的路由项数量，在一般的主机中可能只是几条而已，而在路由器中，这个数目可以达到数十万条。因此很显然，在这种情况下维护一张更小的表来缓存路由查找结果是非常有必要的
路由缓存分为两部分：一部分是与协议(如IPv4等三层协议)相关的缓存，这就是缓存框架部分，每个元素被定义为一个由具体协议字段组成的集合；另一部分是与协议无关的缓存，通常被称为DST，嵌套在缓存框架中，只存储与协议无关的信息
路由表和路由缓存除了容量和结构不同之外，对象粒度也不同。路由表使用连续地址的集合，即子网，而缓存项与单个IP地址相关联。因此，路由表和路由缓存使用的查找算法也不同。
路由表结构
fib_table结构
对每个路由表实例创建一个fib_table结构，这个结构主要由一个路由表标识和管理该路由表的一组函数指针组成
struct fib_table {
struct hlist_node tb_hlist;
u32 tb_id;
int tb_default;
int (*tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res);
int (*tb_insert)(struct fib_table *, struct fib_config *);
int (*tb_delete)(struct fib_table *, struct fib_config *);
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];
};struct hlist_node tb_hlist;用来将各个路由表链接成一个双向链表
u32 tb_id;
路由表标识。在支持策略路由的情况下，系统中最多可以有256个路由表，枚举类型rt_class_t定义了保留的路由路由表ID
unsigned char tb_data[0];
路由表项的散列表起始地址。在FIB_HASH算法中指向fn_hash结构，而在FIB_TRIE算法中则指向trie结构
fn_zone结构
一个zone是一组有着相同目的地址掩码长度的路由表项的散列表
struct fn_zone {
struct fn_zone *fz_next; /* Next not empty zone */
struct hlist_head *fz_hash; /* Hash table pointer */
int fz_nent; /* Number of entries */
int fz_divisor; /* Hash divisor */
u32 fz_hashmask; /* (fz_divisor - 1) */
#define FZ_HASHMASK(fz) ((fz)->fz_hashmask)
int fz_order; /* Zone order */
__be32 fz_mask;
#define FZ_MASK(fz) ((fz)->fz_mask)
};struct fn_zone*fz_next;将活动的(路由表项不为空)zone链接在一起的指针，该链表的头部存储在fn_hash数据结构的fn_zone_list字段中。
struct hlist_head *fz_hash;
指向存储该zone中路由项的散列表。
int fz_nent;
在该zone的散列表中fib_node实例的数目，用于检查是否需要改变散列表的容量。
int fz_divisor;
表示散列表fz_hash的容量，以及散列表桶的数目。
u32 fz_hashmask;
其值为fz_divisor - 1，用来计算散列表的关键值
int fz_order;
网络掩码的长度，255.255.255.0的网络掩码长度为24
__be32fz_mask;
网络掩码
fib_node结构
fib_node实例代表每一个唯一的目的网络的路由表项，即同一个子网中所有路由表项所共享的信息。目的网络相同但其他配置参数不同的路由表项共享同一个fib_node实例，因此一个fib_node实例上存在着一个或多个路由表项。
struct fib_node {
struct hlist_node fn_hash;
struct list_head fn_alias;
__be32 fn_key;
struct fib_alias fn_embedded_alias;
};struct list_head fn_alias;
fn_alias指向一个或多个fib_alias结构实例构成的链表
__be32fn_key;
由IP地址和路由项的netmask与操作后得到，被用作查找路由表时的搜索条件
fib_alias结构
fib_alias实例代表一条路由表项，目的地址相同但其他配置参数不同的表项共享fib_node实例
struct fib_alias {
struct list_head fa_list;
struct fib_info *fa_info;
u8 fa_tos;
u8 fa_type;
u8 fa_scope;
u8 fa_state;
#ifdef CONFIG_IP_FIB_TRIE
struct rcu_head rcu;
#endif
};struct list_head fa_list;将共享同一个fib_node实例的所有fib_alias实例链接在一起
struct fib_info*fa_info;
指针指向一个fib_info实例，该实例存储着如何处理与该路由相匹配数据报的信息
u8 fa_tos;
路由的服务类型比特位字段
u8 fa_type;
路由表项的类型，如RTN_UNICAST、RTN_LOCAL等
u8 fa_scope;
路由表项的作用范围
u8 fa_state;
一些标志的位图
fib_info结构
fib_node结构和fib_alias结构的组合用于标识一条路由表项，同时存储相关信息，更多信息，比如下一跳网关等重要的路由信息则存储在fib_info结构中
struct fib_info {
struct hlist_node fib_hash;
struct hlist_node fib_lhash;
struct net *fib_net;
int fib_treeref;
atomic_t fib_clntref;
int fib_dead;
unsigned fib_flags;
int fib_protocol;
__be32 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
struct fib_nh fib_nh[0];
#define fib_dev fib_nh[0].nh_dev
};路由表学习笔记