路由器中的最长前缀匹配

什么是转发？ 转发是将传入的数据包移动到适当的接口。路由器使用转发表来决定哪个传入数据包应该转发到哪个下一跳。

什么是 IP前缀？ IP前缀是IP地址的前缀。同一网络上的所有计算机都有相同的IP前缀。例如，在192.24.0.0/18中，18是前缀的长度，前缀是地址的前18位。

转发是如何工作的？ 路由器基本上会查看目的地址的IP前缀，搜索转发表中的匹配项，然后将数据包转发到转发表中相应的下一跳。

如果前缀重叠怎么办？ 由于前缀可能重叠（这是可能的，因为到处都使用无类寻址），因此传入IP的前缀可能与表中的多个IP条目匹配。 例如，考虑下面的转发表

在上表中，192.24.12.0到192.24.15.255之间的地址重叠，即与表中的两个条目匹配。 为了处理上述情况，路由器使用 最长前缀匹配 规则规则是在一个表中找到与传入数据包的目标IP匹配的前缀最长的条目，并将数据包转发到相应的下一个IP。 在上面的示例中，重叠范围（192.24.12.0到192.24.15.255）中的所有数据包都被转发到下一跳B，因为B具有更长的前缀（22位）。

例1： 路由器使用转发表条目转发数据包。传入分组的网络地址可以匹配多个条目。路由器如何解决这个问题？ （A） 将其转发给条目与传入数据包的最长前缀匹配的路由器 （B） 将数据包转发到网络地址匹配的所有路由器。 （C） 扔掉这个包。 （D） 将其转发给条目与传入数据包的最长后缀匹配的路由器

答复: （A） 在转发表中，不同条目的网络地址可能重叠。路由器将传入数据包转发给路由器，路由器对与传入数据包匹配的最长前缀进行哈希运算。

例2： 无类别域间路由（CIDR）接收地址为131.23.151.76的数据包。路由器的路由表有以下条目：（GATE CS 2015）

Prefix           Output Interface Identifier131.16.0.0/12              3131.28.0.0/14              5131.19.0.0/16              2131.22.0.0/15              1 

将在其上转发此数据包的输出接口的标识符为____。

答复: “1”. 我们需要首先找到地址为“131.23.151.76”的传入数据包的匹配表项。该地址与两个条目“131.16.0.0/12”和“131.22.0.0/15”匹配（我们分别通过匹配前12位和15位发现）。 那么，数据包应该发送到接口3还是接口1？我们使用最长前缀匹配来决定两者之间的匹配。最具体的匹配表条目用作接口。由于“131.22.0.0/15”是最具体的，因此数据包将发送到接口1。

运动 考虑路由器的以下路由表。

考虑下面的三个IP地址。

1. 192.24.6.0
2. 192.24.14.32
3. 192.24.54.0