IP转发与最长前缀匹配

形式陈述

IP转发接收一份IP数据报和当前转发表，输出下一跳、出接口，或丢弃结果。路由计算负责学习并选择路径、生成表项；转发负责对当前数据报查表。查表正确不意味着路由协议已经收敛，也不保证沿途没有环。

以IPv4为例，把目的地址 $d$ 当作32位无符号数。前缀 $p/\ell$ 的长度满足 $0\le\ell\le32$ ， $p$ 的低 $32-\ell$ 位为零；掩码 $M_\ell$ 的前 $\ell$ 位为1。该表项匹配当且仅当

d\mathbin{\&}M_\ell=p.

在所有匹配项中选取最大 $\ell$ 。同长度的多个下一跳如何取舍，交由已声明的策略；本页假定每个前缀仅有一个已选定出口。没有匹配项则报告无路由，不能随意找“最接近”的地址。

直接扫描含 $n$ 项的表，保存目前最长的匹配项，耗时 $O(n)$ 、额外空间 $O(1)$ 。循环不变量是：处理前 $k$ 项后，候选恰为这 $k$ 项中最长匹配。也可用二进制前缀树从最高位向下走，并记住最近的有路由标记节点；最多检查32位，树的存储与更新成本另计。

最长前缀只负责本次选择。真实转发还须检查首部、TTL、接口、下一跳可达性以及出链路MTU；任一阶段都可失败。IPv4路由器递减TTL，耗尽则丢弃并在规范条件允许时产生ICMP错误；该错误也可能未到达发送方。

直觉

前缀越长，覆盖范围越小。默认路由像“其余目的地从这里走”，而更具体的一条说明可以覆盖这个默认选择。先出现还是后出现无关，除非实现错误地把最长匹配写成第一条匹配。

一张转发表是当前决策的快照。即使每台路由器都严格执行最长匹配，它们的快照也可能互相指向对方。TTL限制这种转发的寿命，却不会自动修正路径。

例子与边界

固定五项：0.0.0.0/0→A；10.0.0.0/8→B；10.2.0.0/16→C；10.2.3.0/24→D；10.2.3.128/25→E。

目的10.2.3.200匹配全部五项，其中最后一字节200的最高位为1，因此匹配/25，选E。10.2.3.20不在该/25内，却匹配/24，选D。10.2.4.1选C；10.9.0.1选B；203.0.113.9只匹配/0，选A。删除默认项后，最后一个目的无路由。

对10.2.3.200，/25掩码最后一字节是128， $200\mathbin{\&}128=128$ ；对10.2.3.20，结果为0。这个按位计算比“十进制数字开头看起来一样”可靠：前缀长度不必落在8位字节边界。

另一条数据报即使成功查到E，若到达时TTL=1，也不能继续转发。设R1和R2的默认路由互指，初始TTL=3；经过两次转发后剩1，下一台路由器丢弃。有限寿命说明循环最终止住，不说明包到达了正确终点。

推论与应用

聚合前缀可以减小表，但新增更具体前缀会改变部分目的地址的出口。检查配置变更时，应挑选“聚合内且例外内”“聚合内且例外外”和“聚合外”三类地址，不能只测一个成功样本。

路由表项的数量、每包查找成本、收敛时间和端到端可达性是四笔不同账。最短路或路由协议可生成表，最长匹配并不重新解一遍全网最短路问题。

参考资料

RFC 1812，1995，§5.2.4.3，基本匹配与最长匹配；§5.3.1，TTL。
Peterson、Davie，Computer Networks: A Systems Approach，在线6.2-dev版，§§3.3.4–3.3.5，转发、子网与CIDR；2026-10-08实读。