IP层转发分组的过程

基于终点的转发

基于终点的转发：分组在互联网上传送和转发是基于分组首部中的目的地址的。

因此，分组每到达一个路由器，路由器就根据分组中的终点（目的地址）查找转发表，然后就得知下一跳应当到哪一个路由器。

但是，由于互联网中的主机数目实在太大。如果用目的地址直接查找转发表，路由器中的转发表不能按目的IP地址来直接查出下一跳路由器。因为这种结构的转发表就会非常庞大，使得查找过程非常之慢。

前面提到，32位的IP地址是由两级组成的。前一部分是前缀，表示网络；后一部分表示主机。所以可以把查找目的主机的方法变通一下，先查找目的网络（网络前缀），在找到了目的网络之后，就把分组在这个网络上直接交付目的主机。由于互联网上的网络数远远小于主机数，这样就可以大大压缩转发表的大小，加速分组在路由器中的转发。这就是基于终点的转发过程。

当路由器收到一个待转发的分组，在从转发表得出下一跳路由器的IP地址后，不是把这个地址填入分组首部，而是送交数据链路层的网络接口软件。网络接口软件负责把下一跳路由器的IP地址转换成MAC地址（必须使用ARP），并将此MAC地址放在链路层的MAC帧的首部，然后利用这个MAC地址传送到下一跳路由器的链路层，再取出MAC帧的数据部分，交给网络层。由此可见，当发送一连串的分组时，上述的这种查找转发表、调用ARP解析出MAC地址、把MAC地址写入MAC帧的首部等过程，都是必须做的。

下面用具体例子来说明分组的转发过程。

【例】下图中有三个子网通过两个路由器互连在一起。主机$H_1$发送出一个分组，其目的地址是128.1.2.132。现在源主机是$H_1$而目的主机是$H_2$。试讨论分组怎样从源主机传送到目的主机。

主机$H_1$首先必须确定：目的主机是否连接在本网络上？

• 如果是，那么问题很简单，就直接交付，根本不需要利用路由器；
• 如果不是，就间接交付，把分组发送给连接在本网络上的路由器，以后要做的事情都由这个路由器来处理。

那么怎么判断是否在本网络上呢？把要发送的分组的目的地址和本网络$N_1$的子网掩码按位进行AND运算，得出运算结果。

• 如果运算结果等于本网络$N_1$的前缀，就表明目的主机连接在本网络上；
• 否则，就必须把分组发送到路由器$R_1$，由路由器$R_1$完成后续的任务。

路由器$R_1$的部分转发表已在上图右上方给出了。转发表中第1列就是“前缀匹配”，这是因为查找转发表的过程就是寻找前缀匹配的过程。

现在先检查路由器$R_1$的转发表中的第1行。

• 源主机$H_1$要发送的分组的目的地址是128.1.2.132。本网络128.1.2.192/26的前缀有26位。将目的地址和子网掩码按位AND运算，很明显，AND运算结果与转发表第一行的前缀不匹配。
• 接着检查路由器R的转发表中的第2行。运算结果是128.1.2.128/26。这个结果和转发表第2行的前缀相匹配。因此按照转发表第2行指出的，在网络$N_2$上进行分组的直接交付。这时路由器$R_1$调用ARP，解析出目的主机$H_2$的MAC地址，再封装成链路层的帧，直接交付连接在本网络$N_2$上的目的主机$H_2$。
• 如果按照同样的方法，检查路由器$R_1$的转发表中的第3行，不难得出不匹配的结果。

从以上例子可看出，查找转发表的过程就是逐行寻找前缀匹配的过程。

最长前缀匹配

在采用CIDR编址时，如果一个分组在转发表中可以找到多个匹配的前缀，那么就应当选择前缀最长的一个作为匹配的前缀。这个原则称为最长前缀匹配(longest prefixmatch)。网络前缀越长，其地址块就越小，因而路由就越具体。

为了更加迅速地查找转发表，可以按照前缀的长短，把前缀最长的排在第1行，然后按前缀长短的顺序往下排列。用这种方法从第1行前缀最长的开始查找，只要检查到匹配的，就不必再继续往下查找，可以立即结束查找。

实际的转发表有时还可能增加两种特殊的路由，就是主机路由和默认路由。

• 主机路由(host route)，又叫作特定主机路由，这是对特定目的主机的IP地址专门指明的一个路由。采用特定主机路由可使网络管理人员更方便地控制网络和测试网络，同时也可在需要考虑某种安全问题时采用这种特定主机路由。在对网络的连接或转发表进行排错时，指明到某一台主机的特殊路由就十分有用。假定这个特定主机的点分十进制IP地址是a.b.c.d，那么在转发表中对应于主机路由的网络前缀就是a.b.c.d/32。实际的网络不可能使用32位的前缀，因为没有主机号的IP地址是没有实际意义的。但这个特殊的前缀却可以用在转发表中。不难看出，32个1的子网掩码和IP地址a.b.c.d 按位进行AND运算后，得出的结果必定是a.b.c.d，也就是说，找到了匹配。这时就把收到的分组转发到转发表所指出的下一跳。主机路由在转发表中都放在最前面。
• 还有一种特殊路由是默认路由(default route)。这就是不管分组的最终目的网络在哪里，都由指定的路由器$R$来处理。这在网络只有很少的对外连接时非常有用。在实际的转发表中，用一个特殊前缀0.0.0.0/0来表示默认路由。这个前缀的掩码是全0（/0表示网络前缀是0位，因此掩码是32个0）。用全0的掩码和任何目的地址进行按位AND运算，结果一定是全0，即必然是和转发表中的0.0.0.0/0相匹配的。这时就按照转发表的指示，把分组送交下一跳路由器R来处理（即间接交付）。

综上所述，可归纳出分组转发算法如下（假定转发表按照前缀的长短排列，把前缀长的放在前面）:

1. 从收到的分组的首部提取目的主机的IP地址D(即目的地址)。
2. 若查找到有特定主机路由（目的地址为D)，就按照这条路由的下一跳转发分组；否则从转发表中下一行（也就是前缀最长的一行）开始检查，执行(3)。
3. 把这一行的子网掩码与目的地址D按位进行AND运算。
   1. 若运算结果与本行的前缀匹配，则查找结束，按照“下一跳”所指出的进行处理（或直接交付本网络上的目的主机，或通过指定接口发送到下一跳路由器）。
   2. 否则，若转发表还有下一行，则对下一行进行检查，重新执行(3)。否则，执行(4)。
4. 若转发表中有一个默认路由，则按照指明的接口，把分组传送到指明的默认路由器；否则，报告转发分组出错。

使用二叉线索查找转发表

使用CIDR后，由于不知道目的网络的前缀，使转发表的查找过程变得更加复杂了。当转发表的项目数很大时，怎样设法缩短转发表的查找时间就成为一个非常重要的问题。

对无分类编址的转发表的最简单的查找算法就是对所有可能的前缀进行循环查找，从最长的前缀开始查找。例如，给定一个目的地址。对每一个可能的网络前缀，进行目的地址和子网掩码的按位AND运算，得出一个网络前缀，然后逐行查找转发表中的网络前缀。所找到的最长匹配就对应于要查找的路由。

这种最简单的算法的明显缺点就是查找的次数太多。最坏的情况是转发表中没有这个路由。

为了进行更加有效的查找，通常是把无分类编址的转发表存放在一种层次的数据结构中，然后自上而下地按层次进行查找。这里最常用的就是二叉线索(binary trie)，它是一种特殊结构的树。IP地址中从左到右的比特值决定了从根节点逐层向下层延伸的路径，而二叉线索中的各个路径就代表转发表中存放的各个地址。

下图用一个例子来说明二叉线索的结构。图中给出了5个IP地址。为了简化二叉线索的结构，可以先找出对应于每一个IP地址的唯一前缀(unique prefix)。所谓唯一前缀就是在表中所有的IP地址中，该前缀是唯一的。这样就可以用这些唯一前缀来构造二叉线索。在进行查找时，只要能够和唯一前缀相匹配就行了。

从二叉线索的根节点自顶向下的深度最多有32层，每一层对应于IP地址中的一位。一个IP地址存入二叉线索的规则很简单：

• 先检查IP地址左边的第一位，如为0，则第一层的节点就在根节点的左下方；如为 l，则在右下方。
• 然后再检查地址的第二位，构造出第二层的节点。
• 依此类推，直到唯一前缀的最后一位。

由于唯一前缀一般都小于32位，因此用唯一前缀构造的二叉线索的深度往往不到32层。图中较粗的折线就是前缀0101在这个二叉线索中的路径。二叉线索中的小圆圈是中间节点，而在路径终点的小方框是叶节点。每个叶节点代表一个唯一前缀。节点之间的连线旁边的数字表示这条边在唯一前缀中对应的比特是0或1。

显然，要将二叉线索用于转发表中，还必须使二叉线索中的每一个叶节点包含所对应的网络前缀和子网掩码。当搜索到一个叶节点时，就必须将寻找匹配的目的地址和该叶节点的子网掩码进行按位AND运算，看结果是否与对应的网络前缀相匹配。若匹配，就按下一跳的接口转发该分组。否则，就丢弃该分组。

总之，二叉线索只是提供了一种可以快速在转发表中找到匹配的叶节点的机制。但这是否和网络前缀匹配，还要和子网掩码进行一次逻辑AND运算。

为了提高二叉线索的查找速度，广泛使用了各种压缩技术。因此，只要一个地址的前$n$位是一样的，就可以跳过前面$n$位（即压缩了$n$个层次）而直接从第$n+1$位开始比较。这样就可以减少查找的时间。当然，制作经过压缩的二叉线索需要更多的计算，但由于每一次查找转发表时都可以提高查找速度，因此这样做还是值得的。