赵占旭的博客

Linux内核报文收发-路由

版本说明


Linux版本: 3.10.103
网卡驱动: ixgbe

路由


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

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

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

路由实现


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

  • 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/2410.1.2.0/24)划分 (struct fib_node)。
  • 第四层是一个路由表项(struct fib_info) ,因为不同的子网可能是对应着同一个下一跳,所以fib_nodefib_info是多对一的关系。

avatar
avatar

LC-Trie树路由算法

avatar

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

1
2
3
4
5
6
7
8
9
10
11
12
CheckNode{
    int pos;
    int bits;
    Node children[1<<bits];
}
union Node{
    Leaf entry;
    CheckNode node;
}
//Pos表示位置
//Bits表示位数
//Children表示子节点

avatar

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

avatar
avatar
avatar
avatar
avatar

注意:所有文章非特别说明皆为原创。为保证信息与源同步,转载时请务必注明文章出处!谢谢合作 :-)

原始链接:http://zhaozhanxu.com/2016/07/15/Linux/2016-07-15-Linux-Kernel-Pkts_Processing4/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。