通过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比特的掩码。
我们对查找键和
路由表项的掩码进行逻辑与运算，假设得到的值与该路由表项的目的地址同样。则称该路由表项是匹配的。对于某个给定的
查找键，我们会从路由表中找到多条这种匹配路由。
下图给出了上面路由表的内部结构。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
标有end的两个阴影框是该书结构中带有特殊标志的叶节点，该标志代表树的端点。左边的那个拥有一个全0键。而右边的
拥有一个全1键，左边的两个标有end和default的框叠在一起，这两个框有特殊的意义，它们与反复键有关。
方角框被称为内部结点或简称为结点，圆角框被称为叶子。每个内部结点相应于測试查找键的一个比特位，其左右各有
一个分支。
每个叶子相应于一个主机地址或者相应于一个网络地址。假设在叶子以下有一个十六进制数，那么这个叶子
就相应于一个网络地址，该十六进程数就是叶子的网络掩码。假设在叶子以下没有十六进制的掩码。那么这个叶子就是一个
主机地址。其隐含的掩码是0xffffffff。
有一些内部节点也含有网络掩码，这些掩码在回溯过程中使用。
比特比較式运用在插口地址结构上的，因此，在上图给出的比特位置是从插口地址结构中的起始位置開始算的。下图给出了
sockaddr_in结构中的比特位置。
下图为路由表中各个IP地址的比特表示形式。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
以下举一些样例来说明路由表的查找过程是怎样完毕的。
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的叶子处结束。路由表的键值和查找keyword
并不相等。而且该路由表项不包括网络掩码，因此要进行回溯。
回溯向上移动一层，达到63相应的节点，节点含有掩码0xff000000(假设没有掩码则继续往上回溯)，因此对查找键和该掩码
进行逻辑与运算，产生一个新的查找键224.0.0.0。再从这个结点開始一次新的查找。
在新的查找键中63为0，于是沿左分支
到达标有224.0.0.0的叶子。这个路由表键和逻辑与运算得到的查找键相匹配，因此这个路由表项是匹配的。
该路由表设置了克隆标志。因此，以224.0.0.5为地址创建一个新的叶子。新的路由表项是：
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
下图从比特35相应的结点開始。给出了上面路由表树右边部分的新的排列。
不管何时向树中加入新的叶子。都须要两个结点：
一个作为叶子，还有一个作为測试某一位比特的内部结点。新创建的表项就返回给查找225.0.0.5的调用者。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
下图描写叙述了全部涉及到的数据结构。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
我们解释下图中的几个要点。
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字段。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
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仅初始
化当中的四个指针，剩下的未被使用。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
下图给出了组成树中结点的radix_node结构。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
前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结构。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
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结构。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
在TCP中会使用该结构中的六个成员。在ARP中会使用rmx_expire作为每个ARP路由项的定时器。
6.初始化：route_init和rtable_init函数
下图给出了各协议族中与domain结构相关的字段。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
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比特反复键的结点。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVE9ERDkxMQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
图中最上面的结点即为路由树的顶点。
接下来的两个结点是叶子（他们的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.回溯。