目录

IP 层转发分组的过程

1.1  基于终点的转发

1.2 最长前缀匹配

转发表中的 2 种特殊的路由

主机路由 (host route)

默认路由 (default route)

路由器分组转发算法

 1.3 使用二叉线索查找转发表

---

IP 层转发分组的过程

1.1  基于终点的转发

·分组在互联网中是逐跳转发的。

·基于终点的转发：基于分组首部中的目的地址传送和转发。

·为了压缩转发表的大小， 转发表中最主要的路由是（目的网络地址，下一跳地址） ， 而不是（目的地址，下一跳地址）。

·查找转发表的过程就是逐行寻找前缀匹配。

主机 H1 发送出的、目的地址是 128.1.2.132 的分组是如何转发的？

·H1 首先检查 128.1.2.132 是否连接在本网络上。

        如果是，则直接交付；否则，就送交路由器 R1。

128.1.2.132 AND 255.255.255.192 = 128.1.2.128     不匹配!

·路由器 R1 收到分组后查找转发表。先检查第 1 行。

·路由器 R1 收到分组后查找转发表。接着检查第 2 行。

        128.1.2.132 AND 255.255.255.128 = 128.1.2.128     匹配!

        进行分组的直接交付（通过路由器 R1 的接口 1）。

1.2 最长前缀匹配

·使用 CIDR 时，在查找转发表时可能会得到不止一个匹配结果。

·最长前缀匹配 (longest-prefix matching) 原则：选择前缀最长的一个作为匹配的前缀。

·网络前缀越长，其地址块就越小，因而路由就越具体。

·可以把前缀最长的排在转发表的第 1 行。

路由器 R1 如何转发目的地址是 128.1.2.196 的分组？

·路由器 R1 收到分组后查找转发表。先检查第 1 行。

        128.1.2.196 AND 255.255.255.192 = 128.1.2.192     不匹配!

·路由器 R1 收到分组后查找转发表。接着检查第 2 行。

        128.1.2.196 AND 255.255.255.128 = 128.1.2.128     匹配!

·路由器 R1 收到分组后查找转发表。接着检查第 3 行。

        128.1.2.196 AND 255.255.255.192 = 128.1.2.192     匹配!

问题：R1 从哪个接口向外转发分组？

最长前缀匹配： 选择前缀最长的一个作为匹配的前缀。故选择 接口 0 。

·网络前缀越长，其地址块就越小，路由就越具体(more specific）。

·可以把前缀最长的排在转发表的第 1 行，以加快查表。

转发表中的 2 种特殊的路由

主机路由 (host route)

·又叫做特定主机路由。

·是对特定目的主机的 IP 地址专门指明的一个路由。

·网络前缀就是 a.b.c.d/32。

·放在转发表的最前面。

默认路由 (default route)

·不管分组的最终目的网络在哪里，都由指定的路由器 R 来处理。

·用特殊前缀 0.0.0.0/0 表示。

默认路由举例

只要目的网络不是 N1 和 N2，就一律选择默认路由，把 IP 数据报先间接交付默认路由器 R1，让 R1 再转发给下一个路由器。

路由器分组转发算法

 1.3 使用二叉线索查找转发表

·二叉线索 (binary trie)：一种特殊结构的树，可以快速在转发表中找到匹配的叶节点。

·从二叉线索的根节点自顶向下的深度最多有 32 层，每一层对应于 IP 地址中的一位。

·为简化二叉线索的结构，可以用唯一前缀 (unique prefix) 来构造二叉线索。

·为了提高二叉线索的查找速度，广泛使用了各种压缩技术。

用 5 个唯一前缀构成的二叉线索

规则：先检查 IP 地址左边的第一位，如为 0，则第一层的节点就在根节点的左下方；如为 1，则在右下方。然后再检查地址的第二位，构造出第二层的节点。依此类推，直到唯一前缀的最后一位。每个叶节点代表一个唯一前缀。 为检查网络前缀是否匹配，必须使二叉线索中的每一个叶节点包含所对应的网络前缀和子网掩码。

在二叉线索中查找 IP 地址

欢迎一起学习~