（★★）代表非常重要的知识点，（★）代表重要的知识点。

一、网络层转发分组的过程

分组转发都是基于目的主机所在网络的，这是因为互联网上的网络数远小于主机数，这样可以极大地压缩转发表的大小。当分组到达路由器后，路由器根据目的 IP 地址的网络前缀来查找转发表，确定下一跳应当到哪个路由器。因此，在转发表中，每条路由必须有下面两条信息：
( 目的网络地址, 下一跳地址 )

【拓展】：一个实际的路由表还会有其他的一些信息。例如，标志、参考计数、使用情况以及接口等。
① “标志”可以设置多个字符以说明不同的意思。如 U 表示该路由是可用的， G 表示下一跳地址是一个路由器，因而是间接交付（如不设置 G, 则表示直接交付）， H 表示该路由是到一台主机（如不设置 H, 则表示该路由是到一个网络）。
② “参考计数”是给出正在使用该路由的 TCP 连接数。
③ “使用情况“显示出通过该路由的分组数。
④ “接口”是本地接口的名字，指出分组应当从哪一个接口转发。

以下举一个例子：应当注意到，图中的每一个路由器都有两个不同的 IP 地址。

由上图可知，可以根据目的网络地址来确定下一跳路由器，这样做能得出以下的结果：

• IP 数据报最终一定可以找到目的主机所在目的网络上的路由器（可能要通过多次的间接交付）。
• 只有到达最后一个路由器时，才试图向目的主机进行直接交付。

此外，在路由表中还可以增加两种特殊的路由：

• 特定主机路由：对特定目的主机的 IP 地址专门指明一个路由，以方便网络管理员控制和测试网络。若特定主机的 IP 地址是 a.b.c.d ，则转发表中对应项的目的网络是 a.b.c.d/32 。/32 表示的子网掩码没有意义，但这个特殊的前缀可以用在转发表中。

• 默认路由（default route）：用特殊前缀 0.0.0.0/0 表示默认路由，全 0 掩码和任何目的地址进行按位与运算，结果必然为全 0 ，即必然和前缀 0.0.0.0/0 相匹配。只要目的网络是其他网络（不在转发表中），就一律选择默认路由。默认路由通常用于路由器到互联网的路由，互联网包括无数的网络集合，不可能在路由表项中一一列出，因此只能采用默认路由的方式。

下图是路由器 R₁ 充当网络 N₁ 的默认路由器的示意图。

在 IP 数据报的首部中没有地方可以用来指明“下一跳路由器的 IP 地址”。在 IP 数据报的首部写上的 IP 地址是源 IP 地址和目的 IP 地址，而没有中间经过的路由器的 IP 地址。

【思考】既然 IP 数据报中没有下一跳路由器的 IP 地址，那么待转发的数据报又怎样能够找到下一跳路由器呢？

【答】当路由器收到一个待转发的数据报，在从路由表得出下一跳路由器的 IP 地址后，不是直接把这个地址填入待发送的 IP 数据报，而是送交数据链路层的网络接口软件。网络接口软件负责把下一跳路由器的 IP 地址转换成硬件地址（ MAC 地址 [通过 ARP] ），并将此硬件地址放在链路层的 MAC 帧的首部，然后根据这个硬件地址找到下一跳路由器。在不同网络中传送时，MAC 帧的源地址和目的地址要发生变化。
由此可见，当发送一连串的数据报时，上述的这种查找路由表、用 ARP 得到硬件地址、把硬件地址写入 MAC 帧的首部等过程，将不断地重复进行，造成了一定的开销。

【思考】那么，能不能在路由表中不使用 IP 地址而直接使用硬件地址呢？

【答】不行。使用抽象的 IP 地址，本来就是为了隐蔽各种底层网络的复杂性而便于分析和研究问题，这样就不可避免地要付出些代价，例如在选择路由时多了一些开销。但反过来，如果在路由表中直接使用硬件地址，那就会带来更多的麻烦。

综上所述，归纳出路由器执行的分组转发算法如下：

• 从数据报的首部提取目的主机的 IP 地址 D ， 得出目的网络地址为 N 。

• 若 N 就是与此路由器直接相连的某个网络地址，则进行直接交付，不需要再经过其他的路由器，直接把数据报交付目的主机（这里包括把目的主机地址 D 转换为具体的硬件地址，把数据报封装为 MAC 帧，再发送此帧）；否则就是间接交付，执行下一步。

• 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行下一步。

• 若路由表中有到达网络 N 的路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行下一步。

• 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则，执行下一步。

• 报告转发分组出错。

值得注意的是，转发表（或路由表）并没有给分组指明到某个网络的完整路径（即先经过哪个路由器，然后经过哪个路由器等）。转发表指出，到某个网络应当先到某个路由器（即下一跳路由器），到达下一跳路由器后，再继续查找其转发表，知道再下一步应当到哪个路由器。这样一步一步地查找下去，直到最后到达目的网络。

二、子网划分与子网掩码（★★）

1. 划分子网

1）子网的定义

在今天看来，在 ARPANET 的早期，IP 地址的设计确实不够合理。两级 IP 地址（即 IP 地址 : : = {<网络号>, <主机号>}）的缺点有如下几点：

• IP 地址空间的利用率有时很低；
• 给每个物理网络分配一个网络号会使路由表变得太大，进而使网络性能变坏；
• 两级 IP 地址不够灵活。

为了解决上述问题，从1985 年起，在 IP 地址中又增加了一个“子网号字段”，使两级 IP 地址变成了三级 IP 地址，这种做法称为划分子网（subnetting），或子网寻址或子网路由选择。划分子网已成为互联网的正式标准协议。

2）划分子网的基本思路

1. 一个拥有许多物理网络的单位，可将所属的物理网络划分为若干个子网（subnet）。划分子网纯属一个单位内部的事情。本单位以外的网络看不见这个网络是由多少个子网组成，因为这个单位对外仍然表现为一个网络。

2. 划分子网的方法是从网络的主机号借用若干位作为子网号（subnet-id），当然主机号也就相应减少了同样的位数。于是两级 IP 地址在本单位内部就变为三级 IP 地址：网络号、子网号和主机号。也可以用以下记法来表示：
   IP 地址 : : = {<网络号>, <子网号>, <主机号>}

3. 凡是从其他网络发送给本单位某台主机的 IP 数据报，路由器转发分组根据的仍然是 IP 数据报的目的网络号，本单位的路由器收到 IP 数据报后，再按目的网络号和子网号找到目的子网。最后把 IP 数据报交付给目的主机。

下面用例子说明划分子网的概念。下图表示某单位拥有一个 B 类 IP 地址，网络地址是 145.13.0.0 （网络号是 145.13 ) 。凡目的地址为 145.13.x.x 的数据报都被送到这个网络上的路由器 R₁ 。

现把上图的网络划分为三个子网（如下图所示) 。这里假定子网号占用 8 位，因此在增加了子网号后，主机号就只有 8 位。所划分的三个子网分别是：145.13.3.0 , 145.13.7.0 和 145.13.21.0 。在划分子网后，整个网络对外部仍表现为一个网络，其网络地址仍为 145.13.0.0 。但网络 145.13.0.0 上的路由器凡在收到外来的数据报后，再根据数据报的目的地址把它转发到相应的子网。

总之，当没有划分子网时， IP 地址是两级结构。划分子网后 IP 地址变成了三级结构。划分子网只是把 IP 地址的主机号这部分进行再划分，而不改变 IP 地址原来的网络号。

【注意】：
① 划分子网只是把 IP 地址的主机号部分进行再划分，而不改变 IP 地址原来的网络号。因此，从一个 IP 地址本身无法判断该主机所连接的网络是否进行了子网划分。
② 子网中的主机号全 0 或全 1 的地址不能被指派，其中主机号全 0 的地址为子网的网络地址，主机号全 1 的地址为子网的广播地址。
③ 划分子网增加了灵活性，但减少了能够连接在网络上的主机总数。

2. 子网掩码与默认网关

1）子网掩码

子网掩码（subnet mask）可用来指明分类 IP 地址的主机号部分被借用了多少位作为子网号。子网掩码是一个与 IP 地址相对应的、长 32 位的二进制串，它由一串 1 和跟随的一串 0 组成其中，1 对应于 IP 地址中的网络号及子网号，而 0 对应于主机号。主机或路由器只需将 IP 地址和其对应的子网掩码逐位 “与”（AND 运算），就可得出相应子网的网络地址。下图是 IP 地址的各字段和子网掩码（以 145.13.3.30 为例）。

使用子网掩码的好处就是：不管网络有没有划分子网，只要把子网掩码和 IP 地址进行逐位的 “与”运算（AND），就立即得出网络地址来。这样在路由器处理到来的分组时就可采用同样的算法。

【思考】在不划分子网时，既然没有子网，为什么还要使用子网掩码？
【回答】为了更便于查找路由表。

现在互联网的标准规定：所有的网络都必须使用子网掩码，同时在路由器的路由表中也必须有子网掩码这一栏。如果一个网络不划分子网，那么该网络的子网掩码就使用默认子网掩码。默认子网掩码中 1 的位置和 IP 地址中的网络号字段 net-id 正好相对应。A、B、C 类地址的默认子网掩码分别为：

• A 类地址的默认子网掩码是 255.0.0.0 或 0xFF000000 。
• B 类地址的默认子网掩码是 255.255.0.0 或 0xFFFF0000 。
• C 类地址的默认子网掩码是 255.255.255.0 或 0xFFFFFF00 。

下图是是这三类 IP 地址的网络地址和相应的默认子网掩码。

子网掩码是一个网络或一个子网的重要属性。在 RFC 950 成为互联网的正式标准后，路由器在和相邻路由器交换路由信息时，必须将自己所在网络（或子网）的子网掩码告诉相邻路由器。在路由器的路由表中的每一个项目，除了要给出目的网络地址外，还必须同时给出该网络的子网掩码。若一个路由器连接在两个子网上就拥有两个网络地址和两个子网掩码。

分组转发时，路由器将分组的目标地址和某网络的子网掩码按位相与，若结果与该网络地址一致，则路由匹配成功，路由器将分组转发至该网络。例如，某主机的 IP 地址为 192.168.5.56 ，子网掩码为 255.255.255.0 ，进行逐位 “与” 运算后，得出该主机所在子网的网络号为 192.168.5.0 。

【注意】：
① 一台主机在设置 IP 地址信息的同时，必须设置子网掩码。
② 同属于一个子网的所有主机及路由器的相应端口，必须设置相同的子网掩码。
③ 路由器的路由表中所包含的信息主要内容有目的网络地址、子网掩码、下一跳地址。

2）子网掩码示例

我们以一个 B 类地址为例，说明可以有多少种子网划分的方法。在采用固定长度子网时，所划分的所有子网的子网掩码都是相同的。如下图所示是使用固定长度子网的 B 类地址的子网划分选择。

在上图中，子网数是根据子网号（subnet-id）计算出来的。若 subnet-id 有 n 位，则共有 2ⁿ 种可能的排列。除去全 0 和全 1 这两种情况，就得出表中的子网数。

注意：表中的“子网号的位数”中没有 0, 1, 15 和 16 这四种情况，因为这没有意义。

需要注意，虽然根据已成为互联网标准协议的 RFC 950 文档，子网号不能为全 1 或全 0，但随着无分类域间路由选择 CIDR 的广泛使用，现在全 1 和全 0 的子网号也可以使用了，但一定要谨慎使用，要弄清你的路由器所用的路由选择软件是否支持全 0 或全 1 的子网号这种较新的用法。

我们可以看出，若使用较少位数的子网号，则每一个子网上可连接的主机数就较多。反之，若使用较多位数的子网号，则子网的数目较多但每个子网上可连接的主机数就较少。因此我们可根据网络的具体情况（一共需要划分多少个子网，每个子网中最多有多少台主机）来选择合适的子网掩码。通过简单的计算，不难得到这样的结论：划分子网增加了灵活性，但却减少了能够连接在网络上的主机总数。

3）默认网关

默认网关是子网与外部网络连接的设备，也就是连接本机或子网的路由器接口的 IP 地址。当主机发送数据时，根据所发送数据的目的 IP 地址，通过子网掩码来判定目的主机是否在子网中，若目的主机在子网中，则直接发送。若目的主机不在子网中，则将该数据发送到默认网关，由网关（路由器）将其转发到其他网络，进一步寻找目的主机。

3. 使用子网时的分组转发

1）使用子网时分组转发的步骤

在划分子网的情况下，分组转发的算法必须做相应的改动。我们应当注意到，使用子网划分后，路由表必须包含以下三项内容：目的网络地址、子网掩码和下一跳地址。

在划分子网的情况下，路由器转发分组的算法如下：

• 从收到的数据报的首部提取目的 IP 地址 D 。

• 先判断是否为直接交付。对路由器直接相连的网络逐个进行检查：用各网络的子网掩码和 D 逐位相 “与”（AND 操作），看结果是否和相应的网络地址匹配。若匹配，则把分组进行直接交付（当然还需要把 D 转换成物理地址，把数据报封装成帧发送出去），转发任务结束。否则就是间接交付，执行下一步。

• 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行下一步。

• 对路由表中的每一行（目的网络地址，子网掩码，下一跳地址），用其中的子网掩码和 D 逐位相“与”（AND 操作），其结果为 N 。若 N 与该行的目的网络地址匹配，则把数据报传送给该行指明的下一跳路由器；否则，执行下一步。

• 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则，执行下一步。

• 报告转发分组出错。

2）示例

下图有三个子网，两个路由器，以及路由器 R₁ 中的部分路由表。现在源主机 H₁ 向目的主机 H₂ 发送分组。试讨论 R₁ 收到 H₁ 向 H₂ 发送的分组后查找路由表的过程。

源主机 H₁ 向目的主机 H₂ 发送的分组的目的地址是 H₂ 的 IP 地址 128.30.33.138 。

源主机 H₁ 首先要进行的操作是要判断：发送的这个分组，是在本子网上进行直接交付还是要通过本子网上的路由器进行间接交付？

源主机 H₁ 把本子网的“子网掩码 255.255.255.128 ” 与目的主机 H₂ 的“ IP 地址 128.30.33.138 ”逐位相“与”（即逐位进行 AND 操作），得出 128.30.33.128 ，它不等于 H₁ 的网络地址（128.30.33.0) 。这说明 H₂ 与 H₁ 不在同一个子网上。因此 H₁ 不能把分组直接交付 H₂ ，而必须交给子网上的默认路由器 R₁ ，由 R₁ 来转发。

路由器 R₁ 在收到一个分组后，就在其路由表中逐行寻找有无匹配的网络地址。

先看 R₁ 路由表中的第一行。用这一行的“子网掩码 255.255.255.128 ”和收到的分组的“目的地址 128.30.33.138 ”逐位相 “与”（即逐位进行 AND 操作），得出 128.30.33.128 。然后和这一行给出的目的网络地址 128.30.33.0 进行比较。但比较的结果不一致（即不匹配）。

用同样方法继续往下找第二行。用第二行的“子网掩码 255.255.255.128 ”和该分组的“目的地址 128.30.33.138 ”逐位相 “与”（即逐位进行 AND 操作），结果也是 128.30.33.128 。这个结果和第二行的目的网络地址 128.30.33.128 相匹配，说明这个网络（子网 2) 就是收到的分组所要寻找的目的网络。于是不需要再继续查找下去。R₁ 把分组从接口 1 直接交付给主机 H₂（它们都在一个子网上）。

三、CIDR与路由聚合

1. 无分类编址 CIDR

1）CIDR 的概念

早在 1987 年， RFC 1009 就指明了在一个划分子网的网络中可同时使用几个不同的子网掩码。使用变长子网掩码 VLSM（Variable Length Subnet Mask）可进一步提高 IP 地址资源的利用率。在VLSM 的基础上又进一步研究出无分类编址方法，它的正式名字是无分类域间路由选择 CIDR（Classless Inter-Domain Routing）。

无分类域间路由选择 CIDR 是在变长子网掩码的基础上提出的一种消除传统 A、B、C 类地址及划分子网的概念。CIDR 使用网络前级的概念代替网络的概念，与传统分类 IP 地址最大的区别就是，网络前缀的位数不是固定的，可以任意选取。

2）CIDR 的特点与网络前缀

CIDR 最主要的特点有两个：

• CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而能更加有效地分配 IPv4 的地址空间，并且在新的 IPv6 使用之前容许互联网的规模继续增长。CIDR 把 32 位的 IP 地址划分为前后两个部分。前面部分是“网络前缀”（network-prefix）（或简称为“前缀”），用来指明网络（路由器根据 IP 地址的网络前缀来转发分组），后面部分则用来指明主机。因此 CIDR 使 IP 地址从三级编址（使用子网掩码）又回到了两级编址，但这已是无分类的两级编址。其记法是：
  IP 地址 : : = {<网络前缀>, <主机号>}
  CIDR 还使用“斜线记法”（slash notation），或称为 CIDR 记法，即在 IP 地址后面加上斜线“ / ”，然后写上网络前缀所占的位数（记为“ IP 地址 / 网络前缀所占的位数”）。

斜线记法的作用不仅仅是表示一个 IP 地址，还提供了其他一些重要信息。例如：这个地址块的网络前缀的位数、这个地址块可以包含的 IP 地址的个数、这个地址块的最小地址以及最大地址等。CIDR 记法还有有多种形式，例如：
① 地址块 10.0.0.0/10 可简写为 10/10，也就是把点分十进制中低位连续的 0 省略。
② 另一种简化表示方法是在网络前缀的后面加一个星号＊，如：00001010 00*。意思是：在星号＊之前是网络前缀，而星号＊表示 IP 地址中的主机号，可以是任意值。

• CIDR 把网络前缀都相同的连续的 IP 地址组成一个“CIDR 地址块”。因此只要知道 CIDR 地址块中的任何一个地址，就可以知道这个地址块的起始地址（即最小地址）和最大地址，以及地址块中的地址数。
  例如，已知 IP 地址 128.14.35.7/20 是某 CIDR 地址块中的一个地址，现在把它写成二进制表示。其中的前 20 位是网络前缀（用粗体表示），而前缀后面的 12 位是主机号：
  128.14.35.7/20 = 10000000 00001110 00100011 00000111
  这个地址所在的地址块中的最小地址和最大地址可以很方便地得出，如下图所示。

当然，以上这两个特殊地址的主机号是全 0 和全 1 的地址，一般并不使用。
① CIDR 地址块中主机号全 0 的地址（最小地址）代表整个地址块；
② CIDR 地址块中主机号全 1 的地址（最大地址）是该地址块的广播地址，也称为子网广播地址。
以上两个地址不能分配给主机使用，通常只使用在这两个特殊地址之间的地址。不难看出，这个地址块共有 2¹² 个地址。我们可以用地址块中的最小地址和网络前缀的位数指明这个地址块。
例如，上面的地址块可记为 128.14.32.0/20 。在不需要指出地址块的起始地址时，也可把这样的地址块简称为“ /20 地址块”。

【总结】CIDR 地址块中的地址数一定是 2 的整数次幂，实际可指派的地址数通常为 2^N - 2 ，其中 N 表示主机号的位数，主机号全 0 代表网络号，主机号全 1 为广播地址。网络前缀越短，其地址块包含的地址数就越多。而在三级结构的 IP 地址中，划分子网使网络前缀变长。

为了更方便地进行路由选择， CIDR 使用 32 位（即 4B）的地址掩码（address mask）。地址掩码由一串 1 和一串 0 组成，而 1 的个数就是网络前缀的长度。在 CIDR 中，使用掩码从 IP 地址中获取网络前缀（即 IP 地址与掩码做按位与运算）。
例如，/20 地址块的地址掩码是：11111111 11111111 11110000 00000000 (20 个连续的 1) 。斜线记法中，斜线后面的数字就是地址掩码中 1 的个数。如下图所示。

虽然 CIDR 不使用子网了，但由于目前仍有一些网络还使用子网划分和子网掩码，因此 CIDR 使用的地址掩码也可继续称为子网掩码，或简称为掩码。

需要注意的是： “CIDR 不使用子网”是指 CIDR 并没有在 32 位地址中指明若干位作为子网字段。但分配到一个 CIDR 地址块的单位，仍然可以在本单位内根据需要划分出一些子网。这些子网也都只有一个网络前缀和一台主机号字段，但子网的网络前缀比整个单位的网络前缀要长些。
例如，某单位分配到地址块 /20，就可以再继续划分为 8 个子网（即需要从主机号中借用 3 位来划分子网）。这时每一个子网的网络前缀就变成 23 位（原来的 20 位加上从主机号借来的 3 位），比该单位的网络前缀多了 3 位。

3）常用的 CIDR 地址块

下图给出了最常用的 CIDR 地址块。表中的 K 表示 2¹⁰ 即 1024 。网络前缀小于 13 或大于 27 都较少使用。在“包含的地址数”中没有把全 1 和全 0 的主机号除外。

从上图可看出，每一个 CIDR 地址块中的地址数一定是 2 的整数次幕。除最后几行外， CIDR 地址块都包含了多个 C 类地址（是一个 C 类地址的 2ⁿ 倍， n 是整数），这就是“构成超网”这一名词的来源。

使用 CIDR 的一个好处就是可以更加有效地分配 IPv4 的地址空间，可根据客户的需要分配适当大小的 CIDR 地址块。然而在分类地址的环境中，向一个部门分配 IP 地址，就只能以 /8, /16 或 /24 为单位来分配，这就很不灵活。

2. 路由聚合（构成超网）

1）路由聚合的概念

由于一个 CIDR 地址块中有很多地址，所以在路由表中就利用 CIDR 地址块来查找目的网络。这种地址的聚合常称为路由聚合（route aggregation），也称构成超网（supemetting），它使得路由表中的一个项目可以表示原来传统分类地址的很多个（例如上千个）路由。路由聚合有利于减少路由器之间的路由选择信息的交换，从而提高了整个互联网的性能。

路由聚合指将较小的 CIDR 地址块合并为较大的 CIDR 地址块。路由聚合的本质是缩短网络前缀。路由聚合后，一条路由信息可以覆盖更大的地址空间。

2）路由聚合的分析

在下图所示的网络中，若不使用路由聚合，则 R₁ 的路由表中需要分别有到网络 1 和网络 2 的路由表项。不难发现，网络 1 和网络 2 的网络前缀在二进制表示的情况下，前 16 位都是相同的，第 17 位分别是 0 和 1 ，并且从 R₁ 到网络 1 和网络 2 的路由的下一跳皆为 R₂ 。若使用路由聚合，则在 R₁ 看来，网络 1 和网络 2 可以构成一个更大的地址块 206.1.0.0/16 ，到网络 1 和网络 2 的两条路由就可聚合成一条到 206.1.0.0/16 的路由。

再举一个例子：

从上图可以得到结论：由于路由聚合要求在聚合前后，CIDR 地址块应包含相同的 IP 地址，因此当 2 个前缀长度为 n 位的地址块聚合时，其前 n - 1 位必须相同；4 个前缀长度为 n 位的地址块聚合时，其前 n - 2 位必须相同。

3. 最长前缀匹配

最长前缀匹配（longest-prefix matching, 又称最佳匹配、最长匹配）：使用 CIDR 时，路由表中的个项由“网络前缀”和“下一跳地址”组成。在查找路由表时可能会得到不止一个匹配结果。此时，应当从匹配结果中选择具有最长网前缀的路由，因为网络前缀越长，其地址块就越小，因此路由就越具体（more specific）。

CIDR 查找路由表的方法：为了更有效地查找最长前缀匹配，通常将无分类编址的路由表存放在一种层次式数据结构（通常采用二叉线索）中，然后自上而下地按层次进行查找。

CIDR 的优点在于网络前缀长度的灵活性。因为上层网络的前缀长度较短，所以相应的路由表的项目较少。而内部又可采用延长网络前缀的方法来灵活地划分子网。

4. 使用二叉线索查找路由表

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

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

假定有一个 IP 地址是 10011011 01111010 00000000 00000000 ，需要查找该地址是否在此二叉线索中。我们从最左边查起。很容易发现，查到第三个字符（即前缀 10 后面的 0）时，在二叉线索中就找不到匹配的，说明这个地址不在这个二叉线索中。总之，二叉线索只是提供了一种可以快速在路由表中找到匹配的叶节点的机制。但这是否和网络前缀匹配，还要和子网掩码进行一次逻辑与的运算。

5. 基于 CIDR 的子网划分（定长+变长）

基于 CIDR 的子网划分，指将大的 CIDR 地址块划分为较小的 CIDR 地址块。子网划分的本质是延长网络前缀。基于 CIDR 的子网划分又分为定长子网划分和变长子网划分：

• 定长子网划分：划分后的较小的 CIDR 地址块大小都相等；子网的网络前缀长度都相等。
• 变长子网划分：划分后的较小的 CIDR 地址块大小不尽相等；子网的网络前缀长度不尽相等。

1）定长子网划分

下面举一个例子：

可以得到定长子网划分的特点：

• 网络前缀延长 1 位，原网络（大地址块）可以划分为 2 个等长的子网（小地址块）。
• 网络前缀延长 n 位，原网络（大地址块）可以划分为 2ⁿ 个等长的子网（小地址块）。
• 网络前缀延长 n 位，划分后每个子网的子网号长度都是 n 位。

相关计算：
将地址块 222.22.64.0/20 划分为 8 个等长子网，因为 2³ = 8 ，所以网络前缀延长了 3 位。可以计算：
① 每个子网的网络前缀长度为 20 + 3 = 23 位，主机号为 32 - 23 = 9 位。
② 最大子网数为 2³ = 8 个，每个子网的最大可分配 IP 地址数为 2⁹ - 2 = 510 个。
③ 每个子网的子网号长度都是 3 位。
④ 8 个子网的网络地址分别是：222.22.64.0/23 , 222.22.66.0/23 , 222.22.68.0/23 , 222.22.70.0/23 , 222.22.72.0/23 , 222.22.74.0/23 , 222.22.76.0/23 , 222.22.78.0/23 。
⑤ 各子网广播地址：各子网主机号全 1 的地址。

2）变长子网划分

下面举一个例子：

① 第一种划分方法：

② 第二种划分方法：

③ 第三种划分方法：求最长的子网号长度。

可以得到变长子网划分的特点：

• 每个地址块中的地址数都是 2 的幂次，划分子网后，所有子网（小地址块）的地址数之和与原网络（大地址块）的地址数相等。
• 最小子网的子网号最长，即网络前缀延长最多。
• 若网络前缀最多延长 n 位，则最小子网的子网号长度为 n 位，所有子网的子网号长度都 ≤ n 位，得到的子网数 ≤ 2ⁿ 。
• 已 n + 1 为树高，画二叉树，可以找出子网号长度 ≤ n 位的变长子网的所有可能组合。

相关计算：
将地址块 222.22.64.0/20 划分为 5 个子网，因为 2² < 5 < 2³ ，所以网络前缀延长 3 位，才可以得到 5 个子网。画二叉树，划分子网后，可以计算：
① 各子网的网络前缀长度，各子网的主机号长度。
② 各子网的网络地址。
③ 各子网的最大可分配 IP 地址数。
④ 各子网广播地址。
提示：画图是解子网划分相关题目的有效手段。例如：给定子网数，最小子网的子网号长度，那么最长的子网号长度是多少呢？

6. 使用 CIDR 时的分组转发

采用 CIDR 编址时，若一个分组在转发表中可以找到多个匹配的前缀，则应当使用最长前缀匹配。为了更快地查找转发表，可以按照前缀的长短，将前缀最长的排在第 1 行，按前缀长度的降序排列。这样，从第 1 行最长的开始查找，只要检索到匹配的，就不必再继续查找。

路由器执行的分组转发算法如下：

• 从收到的 IP 分组的首部提取目的主机的 IP 地址 D（即目的地址）。

• 若查找到特定主机路由（目的地址为 D），则按照这条路由的下一跳转发分组；否则从转发表中的下一条（即按前缀长度的顺序）开始检查，执行步骤下一步。

• 将这一行的子网掩码与目的地址 D 逐位 “与”（AND 操作)。若运算结果与本行的前缀匹配，则查找结束，按照“下一跳”指出的进行处理（或者直接交付本网络上的目的主机，或通过指定接口发送到下一跳路由器）。否则，若转发表还有下一行，则对下一行进行检查，重新执行这一步。否则，执行下一步。

• 若转发表中有一个默认路由，则把分组传送给默认路由：否则，报告转发分组出错。