转发表：最长前缀匹配与路由聚合

基于目的地址的转发

路由器收到数据报后，要根据目的地址在转发表中查找输出链路接口。IPv4地址有$2^{32}$个，转发表不可能为每一个地址单独保存一个表项。因为同一个子网中的地址拥有相同的网络前缀，转发表中保存的是地址前缀（prefix）：只要目的地址的前若干位与某个前缀相同，就认为它与该表项匹配。

例如某路由器有4个链路接口，它的转发表如下（*表示不必比较的位）：

目的地址200.23.22.161（11001000 00010111 00010110 10100001）的前21位与第1个表项相同，因此从接口0转发。最后一行的前缀长度为0，能够匹配任何地址，称为默认路由（default route）：找不到其他匹配时就使用它。

最长前缀匹配

一个目的地址可能同时与多个表项匹配。例如200.23.24.170（11001000 00010111 00011000 10101010）的前24位与第2个表项相同，前21位又与第3个表项相同。此时路由器采用最长前缀匹配规则（longest prefix matching）：在所有匹配的表项中，选择前缀最长的那一项。因此该数据报从接口1转发。

更长的前缀描述的是更小、更具体的地址范围，所以最长前缀匹配就是“选择最具体的路由”。高速路由器必须在纳秒级完成查找，通常采用前缀树（trie）或三态内容寻址存储器（TCAM）等专门的数据结构和硬件，而不是逐项扫描整张表。

路由聚合

层次化的地址分配让转发表保持很小。假设一家ISP获得了地址块200.23.16.0/20，它把其中8个/23分配给8个组织：

这8个地址块的前20位完全相同，ISP只需向因特网的其余部分通告一条路由：“目的地址的前20位与200.23.16.0/20相同的数据报都发给我”。用一个前缀概括多个网络的做法称为路由聚合（route aggregation），也称为路由汇总。

若干个地址块能够聚合成一个前缀，需要满足三个条件：地址连续；块的个数是2的幂；第一个块的起始地址按聚合后的大小对齐。$2^k$个前缀长度为$x$的块聚合后，前缀长度为$x-k$。

如果组织1改用另一家ISP，会发生什么呢？新ISP可以通告更具体的路由200.23.18.0/23，原ISP继续通告200.23.16.0/20。发往组织1的数据报同时匹配这两条路由，按照最长前缀匹配，/23胜出，数据报被送到新ISP；发往其他组织的数据报只匹配/20，仍然送到原ISP。