版本说明

Linux版本： 3.10.103
网卡驱动： ixgbe

路由

路由项通过两种途径加入内核：

通过用户态路由协议进程或者用户静态配置配置加入。
主机自动发现的路由。

自动发现的路由实际上是“发现了一个路由项和一个转发表”，其含义在主机某一个网卡启动的时候生效，比如eth0启动，那么系统生成下列路由表项/转发项：往eth0同一IP网段的包通过eth0发出。

路由实现

内核路由存在两种查找算法：

HASH算法(Linux之前默认)。
LC-trie算法(Linux现在默认，更适用在超大路由表的情况，它在这种情况提高查找效率的同时，大大地增加了算法本身的复杂性和内存的消耗)。

HASH路由算法

路由的性能很大程度上由路由表的设计决定，好的设计能减少系统资源的消耗，这两方面尤其体现在路由表的查找上。
Linux使用了多个路由表，一个用于上传给本地上层协议，另一个则用于转发，其他用于策略路由。不同策略的路由存放在不同的表中，有效地被免了查找庞大的路由表，在一定程度上提高了查找了效率。

HASH路由表由多个结构组合而成，是一个分层的结构组合：

第一层是指表头fib_table->tb_data指向fn_hash，里面包含了33个fn_zone。
第二层根据子网掩码(netmask)的长度(0~32)分成33个部分(struct fn_zone)。
第三层根据子网的不同(如10.1.1.0/24和10.1.2.0/24)划分 (struct fib_node)。
第四层是一个路由表项(struct fib_info) ，因为不同的子网可能是对应着同一个下一跳，所以fib_node和fib_info是多对一的关系。

LC-Trie树路由算法

trie树本质上是一棵检索树。

CheckNode{
    int pos;
    int bits;
    Node children[1<<bits];
}
union Node{
    Leaf entry;
    CheckNode node;
}
//Pos表示位置
//Bits表示位数
//Children表示子节点

RT_TABLE_LOCAL
优先级 0
选择器 = 匹配任何数据报
动作＝察看本地路由表(routing table local)，ID为255。
local表是保留路由表，包含了到本地和广播地址已及NAT地址的路由。
规则0是特殊的规则，由系统自动维护，不可被删除或修改。

RT_TABLE_MAIN
优先级 32766
选择器 = 匹配所有数据报
动作 = 察看主路由表(routing table main)， ID为254。
main路由表是默认的标准路由表，其包含所有非策略路由，main表是存放旧的路由命令(route命令)创建的路由。而且任何由ip route命令创建的没有明确指定路由表的路由都被加入到该路由表中。
该规则不能被删除和被其他规则覆盖。

RT_TABLE_DEFAULT
优先级 32767
选择器 = 匹配所有数据报
动作 = 察看默认路由表(routing table default)，ID为253。
default路由表是空的，为最后处理所预留，若前面的默认规则没有选择该数据报时保留用作最后的处理。
该规则可以被删除。

USER_DEFINE 策略路由
优先级 1-32765
选择器 = 自定义
动作 = 自动以

静态路由(LOCAL、MAIN、DEFAULT)
匹配字段：目的地址
操作：转发

策略路由(USER_DEFINE)
匹配字段：各个字段（常用五元组：源IP、目标IP、协议、源端口、目标端口）4操作：数据包任意操作
可以实现ACL的功能，不过这些功能目前的linux中用了更高效的nf-HiPAC，另外也可以了解一下ipset和nftables