博客

IP地址为32位，当报文在网络上传输时，要在路由表中进行查找。IP地址的对应位如果能与路由表中保存的进行匹配，这些报文就会发送到路由指向的地址。如下面是一个路由表：

 Entry
    --------
0   0000
1   0001
2   00101
3   010
4   0110
5   0111
6   100
7   101000
8   101001
9   10101 
10  10110
11  10111
12  110
13  11101000
14  11101001

目标地址和路由表中的各项比较，如果有多个都能匹配，选择最长的那个，如果没有一个能匹配，使用默认路由。

在内核中，这个路由表由trie来表示：

左孩子表示0，右孩子表示1。这样比如010就会到达节点3的位置。

从图中看，有很多空的节点，并且高度太天，为提高效率，可使用路径压缩，这样就变成如下的形状：

每一个空节点都被移除了，在每个节点新增一个变量skip，保存被移除的空节点的个数。这样11101001从根节点开始，先到右边一个节点，再到右边一个节点，再到右边一个节点，这时要跳过4位，最后一位是1，到右边的节点，就到达14的位置。

再进行优化，对trie的层级进行压缩，就成为LC-tries，最后变成下面的形状：

一个节点，如果它只有两个节点且左右节点都存在，用两个子节点代替这个节点，如果节点的两个节点都为叶子节点，则停止替换。这个替换可在子树中进行重复。

linux下的实现：

构成树的节点的数据结构：

[  net/ipv4/fib_trie.c  ]

// 中间节点和叶子节点的抽象节点（前两个变量相同）
struct rt_trie_node {
	unsigned long parent;	// 父节点
	t_key key;	// 为地址
};

// 叶子节点(路由)
struct leaf {	
	unsigned long parent;	// 父节点
	t_key key;	// 地址
	struct hlist_head list;	// leaf_info列表
	struct rcu_head rcu;
};

// 路由信息
struct leaf_info {
	struct hlist_node hlist;	// 加入到leaf中
	int plen;	// 目标地址长度
	u32 mask_plen; 	// 根据目标地址长度计算出地址的有效位
	struct list_head falh;	// 路由列表(fib_alias)
	struct rcu_head rcu;
};

// 中间节点
struct tnode {
	unsigned long parent;	// 父节点
	t_key key;	// 地址
	unsigned char pos;		/* 2log(KEYLENGTH) bits needed, 有效位的开始位置 */
	unsigned char bits;		/* 2log(KEYLENGTH) bits needed, 有效位的位数 */
	unsigned int full_children;	/* KEYLENGTH bits needed */
	unsigned int empty_children;	/* KEYLENGTH bits needed */
	union {
		struct rcu