由IP完成的路由选择是一种选路机制，它通过搜索路由表来确定从哪个接口把分组发送出去，它与选路策略不一样，选路策略

是一组规则的集合，这些规则用来确定哪些路由可以编入到路由表中，Net/3内核实现选路机制，而选路守护进程，典型地如

routed或gated，实现选路策略。

1.路由表结构

下图是某主机上的路由表。

对于Flags列需要简单说明下。

G  该路由通向一个网关（路由器），这种路由被称为间接路由。如果没有设置本标志，则表明路由的目的地与本机直接相连，

称为直接路由。

H  该路由通往一台主机，也就是说，目的地址是一个完整的主机地址。如果没有设置本标志，则路由通往一个网络，目的地址

是一个网络地址：一个网络号，或一个网络号与子网号的组合。

S  该路由是静态的。

C  该路由可被克隆以产生新的路由。在本路由表中有两条路由设置了这个标志：一条是到本地以太网140.252.13.32的路由，

ARP通过克隆该路由创建到以太网中其他特定主机的路由；另一条是到多播组224的路由，克隆该路由可以创建到特定多播

组（如224.0.0.1）的路由。

L  该路由含有链路层地址。本标志应用于单播地址和多播地址。由ARP从以太网路由克隆而得到的所有主机路由都设置了本标志。

R  环回驱动器（为设有本标志的路由而设计的普通接口）将拒绝所有使用该路由的数据报。

Net/3路由表采用Patricia树结构来表示主机地址和网络地址。待查找的地址和树中的地址都看成比特序列。这样就可以用相同

的函数来查找和维护不同类型的数。

查找路由表的目的就是为了找到一个最能匹配给定目标的特定地址。我们称这个给定的目标位查找键（search key）。所谓

最能匹配的地址，也就是说，一个能够匹配的主机地址要优于一个能够匹配的网络地址；而一个能够匹配的网络地址要优于

默认地址。

每条路由表项都有一个对应的网络掩码，尽管在主机路由中没有存储掩码，但它隐含了一个全1比特的掩码。我们对查找键和

路由表项的掩码进行逻辑与运算，如果得到的值与该路由表项的目的地址相同，则称该路由表项是匹配的。对于某个给定的

查找键，我们会从路由表中找到多条这样的匹配路由。

下图给出了上面路由表的内部结构。

标有end的两个阴影框是该书结构中带有特殊标志的叶节点，该标志代表树的端点。左边的那个拥有一个全0键，而右边的

拥有一个全1键，左边的两个标有end和default的框叠在一起，这两个框有特殊的意义，它们与重复键有关。

方角框被称为内部结点或简称为结点，圆角框被称为叶子。每一个内部结点对应于测试查找键的一个比特位，其左右各有

一个分支。每一个叶子对应于一个主机地址或者对应于一个网络地址。如果在叶子下面有一个十六进制数，那么这个叶子

就对应于一个网络地址，该十六进程数就是叶子的网络掩码。如果在叶子下面没有十六进制的掩码，那么这个叶子就是一个

主机地址，其隐含的掩码是0xffffffff。

有一些内部节点也含有网络掩码，这些掩码在回溯过程中使用。

比特比较式运用在插口地址结构上的，因此，在上图给出的比特位置是从插口地址结构中的起始位置开始算的。下图给出了

sockaddr_in结构中的比特位置。

下图为路由表中各个IP地址的比特表示形式。

下面举一些例子来说明路由表的查找过程是如何完成的。

1.与主机地址匹配的例子

假定查找键是地址140.252.13.35。32为1，33为0，36为1，57为0，62为1，63为1。因此查找在140.252.13.35的叶子处

终止。查找键与路由表键完全匹配。

2.与网络地址匹配的例子

假定查找键是127.0.0.2。32为0，33为1，63为0，因此，查找在标有127.0.0.0的叶子处终止。查找键和路由表并没有完全

匹配，因此，需要进一步看它是不是一个能够匹配的网络地址。对查找键和网络掩码0xff000000进行逻辑与运算，得到的

结果与该路由表键相同，即认为该路由表项能够匹配。

3.与默认地址匹配的例子

假定查找键是10.1.2.3。32为0，33为0，因此，查找标有end和default并带有重复键的叶子处终止。在这两个叶子中重复的

路由表键是0.0.0.0。查找键与路由表键值没有完全匹配，因此，需要进一步看它是不是一个能够匹配的网络地址。这种匹配

运算要对每个含网络掩码的重复键都试一遍。第一个键没有网络掩码，可以跳过不查。第二个键有一个0x00000000的掩码。

查找键和这个掩码的逻辑与运算，所得结果和路由表键0相等，即认为该路由表项能够匹配。这样默认路由表就能用作匹配

路由。

3.带回溯和克隆、并与主机地址相匹配的例子

假定查找键是224.0.0.5。32为1,33为1,35为0,63为1，因此，查找在标有224.0.0.1的叶子处结束。路由表的键值和查找关键字

并不相等，并且该路由表项不包含网络掩码，因此要进行回溯。

回溯向上移动一层，达到63对应的节点，节点含有掩码0xff000000(如果没有掩码则继续往上回溯)，因此对查找键和该掩码

进行逻辑与运算，产生一个新的查找键224.0.0.0。再从这个结点开始一次新的查找。在新的查找键中63为0，于是沿左分支

到达标有224.0.0.0的叶子。这个路由表键和逻辑与运算得到的查找键相匹配，因此这个路由表项是匹配的。

该路由表设置了克隆标志，因此，以224.0.0.5为地址创建一个新的叶子。新的路由表项是：

下图从比特35对应的结点开始，给出了上面路由表树右边部分的新的排列。无论何时向树中添加新的叶子，都需要两个结点：

一个作为叶子，另一个作为测试某一位比特的内部结点。新创建的表项就返回给查找225.0.0.5的调用者。

下图描述了所有涉及到的数据结构。

我们解释下图中的几个要点。

rf_tables是指向radix_node_head结构的指针数组。每一个地址族都有一个数组与之对应。rt_tables[AF_INET]指向Internet

路由表树的顶点。

radix_node_head结构包含三个radix_node结构。这三个结构式在初始化路由树时创建的，中间的是树的顶点。它对于上面

路由树的bit32的结点框。三个radix_node结构中的第一个是路由树中最左边的叶子（与默认路由共享的重复），第三个结构

是最右边的叶子。在一个空的路由表中，就只包含三个radix_node结构。

全局变量mask_rnhead也指向一个radix_node_head结构。它是包含了所有掩码的一棵独立树的首部结构。上面的路由树给出

了八个掩码可知，有一个掩码重复了四次，有两个掩码重复了一次。通过把掩码放在一棵单独的树中，可以做到对每一个掩码

只需要维护它的一个备份即可。

路由表树是用rtentry结构创建的，上图中有两个rtentry结构。每一个rtentry结构包含两个radix_node结构，因为每次向树中插入

一个新的路由时，都需要两个结点：一个是内部结点，对应于某一位测试比特；另一个是叶子，对应于一个主机路由或一个网络

路由。

存在于每一个UDP和TCP插口中的协议控制块PCB中包含了一个指向rtentry结构的route结构。每次发送一个IP数据报时，UDP

和TCP输出函数都传递一个指向PCB中route结构的指针，作为调用ip_output的参数。使用相同路由的PCB都指向相同的路由

表项。

2.选路插口

下图给出了12种不同类型的选路消息。消息类型位于rt_msghdr结构中的rtm_type字段。

3.函数调用

下图显示了各选路函数之间的关系。

rtalloc函数是由Internet协议调用的，用于查找到达指定目的地的路由。图中还给出了在选路域中创建插口的五个典型程序。

arp处理ARP高速缓存，该ARP高速缓存被存储在Net/3的IP路由表中。

gated和routed是选路守护进程，他们与其他路由器进行通信，当选路环境发生变化时，对内核的路由表进行操作。

route通常是由启动脚本或系统管理员执行的一个程序，用于添加或删除路由。

rwhod在启动时会调用一个选路sysctl来测定连接的接口。

4.Radix结点数据结构

每一个路由表的表头都是一个radix_node_head结构，而选路数中所有的节点都是radix_node结构。radix_node_head结构如

下图所示：

rnh_treetop指向路由数顶端的radix_node结构，可以看到radix_node_head结构的最后一项分配了三个radix_node结构，

其中中间的那个被初始化为树的顶点。

从rnh_addaddr到rnh_walktree是七个函数指针，它们所指向的函数被调用以完成对树的操作。下图中，rn_inithead仅初始

化其中的四个指针，剩下的未被使用。

下图给出了组成树中结点的radix_node结构。

前5个成员是内部结点和叶子结点都有的成员，后面是一个union：如果结点是叶子，那么它定义了三个成员；如果是内部

结点，那么它定义了另外不同的三个成员。

rn_mklist是该节点掩码链表的表头。

rn_p指向该节点的父结点。

如果rn_b值大于等于0，那么该结点为内部结点，否则为叶子。对于内部结点来说，rn_b就是要测试的比特位置。对于叶子

结点来说，rn_b是负的，它的值等于-1减去网络掩码索引。该索引是指压那么中出现的第一个零的比特位置。下图给出了

掩码的索引。

内部结点rn_bmask是个单字节的掩码，用于检测相应的比特位是0还是1。在叶子中它的值为0

下图给出了rn_flags的三个值。

对于叶子而言，rn_key指向插口地址结构，rn_mask指向保存掩码的插口地址结构。如果rn_mask为空，则其掩码为隐含的

全1值（即，该路由指向某个主机而不是某个网络）。

5.选路结构

访问内核路由信息的关键之处是：

1.rtalloc函数，用于查找通往目的地的路由。

2.route结构，它的值由rtalloc函数填写。

3.route结构所指向的rtentry结构。

在UDP和TCP中使用的协议控制块（PCB），其中包含了一个route结构。

ro_dst被定义成一个一般的插口地址结构，但对于internet协议而言，它就是一个sockaddr_in结构。

下图给出了rtentry结构的定义。

结构中包含了两个radix_node结构，每次向路由树中添加一个新叶子的同时也要添加一个内部结点，rt_nodes[0]为叶子，

rt_nodes[1]为内部结点。

下图给出了存储在rt_flags中各种常量以及netstat输出的相应Flags字符。

如果设置了RTF_GATEWAY标志，那么rt_gateway所含的插口地址结构的指针就指向网络的地址。同样，rt_gwroute就指向

该网关的rtentry。

rt_refcnt是一个计数器，保存正在包含该结构的引用数目。

当分配该结构存储空间时，rt_use被初始化为0，每次利用该路由输出一份IP数据报时，其值会随之递增。

rt_ifp和rt_ifa分别指接口结构和接口地址结构。

rt_llinfo指针允许链路层协议在路由表中存储该协议专用的结构指针。在介绍ARP时会描述如何使用该指针。

下图给出了rtentry结构中含有的rt_metrics结构。

在TCP中会使用该结构中的六个成员。在ARP中会使用rmx_expire作为每一个ARP路由项的定时器。

6.初始化：route_init和rtable_init函数

下图给出了各协议族中与domain结构相关的字段。

PF_ROUTE域是唯一具有初始化函数的域。同样，只有那些需要路由表的域才有dom_rtattach函数，并且该函数总是rn_inithead。

选路域和Unix域并不需要路由表。

dom_rtoffset成员是以比特为单位的选路过程中被检测的第一个比特的偏移量（从域的插口地址结构的起始处开始计算）。

dom_maxrtkey给出了该结构的字节长度。

下图列出了路由表初始化过程所包含的步骤。

在系统初始化时，内核的main函数将调用一次domaininit函数，ADDDOMAIN宏用于创建一个domain结构的链表，并调用

每个域的dom_init函数。

7.初始化：rn_init和rn_inithead函数

函数rn_init只被route_init调用一次，用于初始化radix函数使用的一些全局变量。

调用rn_inithead，初始化地址掩码路由树的首部，并使全局变量mask_rnhead指向radix_node_head结构。

下图为Internet协议创建的radix_node_head结构。

这三个radix_node结构组成了一棵树：中间的结构是树的顶点，第一个结构式树的最左边的叶子，左后一个结构是树的最

右边的叶子，这三个结点的父指针都指向中间的那个结点。

最左边结点的键是全0（rn_zeros），最右边结点的键是全1（rn_ones）。

这三个结点都设置了RNF_ROOT标志，这说明它们都是构成树的原始结点之一。它们也是唯一具有该标志的结点。

8.重复键和掩码列表

下面介绍radix_node结构中的两个字段：一个是rn_dupedkey，它构成了附加的含重复键的radix_node结构链表；另一个

是rn_mklist，它是含网络掩码的radix_mask结构链表的开始。在上面的路由树中最左边标有end和default两个框，这就是

重复键。最左边设有RNF_ROOT标志的结点有一个为全0比特的键，但是它和默认路由的键相同。

下图给出了两个具有全0比特重复键的结点。

图中最上面的结点即为路由树的顶点。接下来的两个结点是叶子（他们的rn_b为负值），其中第一个叶子的rn_dupedkey

成员指向第二个结点。

第一个叶子是rnh_nodes[0]结构，该结构是树的左边标有end的结点，它设有RNF_ROOT标志。它的键被rn_inithead设为

rn_zeros。

第二个叶子是默认路由表项。它的rn_key指向0.0.0.0的sockaddr_in结构，并具有一个全0的掩码。

最后一个是radix_mask结构，树的顶结点和默认路由对应的叶子都指向这个结构，这个列表时树的顶结点的掩码列表，在

查找网络掩码时，回溯算法将使用它。radix_mask结构列表和内部结点一起确定了运用于从该结点开始的子树的掩码。

应该注意：具有相同值得掩码之间可以共享，但是具有相同值的键之间不能共享。

9.rn_match函数

在Internet协议中，它被称为rnh_matchaddr函数。它将被rtallocl函数调用（而rtallocl函数将被rtalloc函数调用），具体

算法如下：

1.从树的顶端开始搜索，直到到达与查找键比特相应的叶子，检测该叶子，看能够得到一个精确的匹配。

2.检测该叶节点，看是否能够得到匹配的网络地址。

3.回溯。

《TCP/IP详解卷2：实现》笔记--Radix树路由表