计算机网络4——网络层2

一、地址解析协议ARP

在实际应用中，我们经常会遇到这样的问题:已经知道了一个机器(主机或路由器)的IP地址，需要找出其相应的MAC地址。地址解析协议 ARP就是用来解决这样的问题的。下图说明了协议ARP 的作用。

我们知道，网络层使用的是IP地址，但在实际网络的链路上传送数据时，最终还是必须使用链路层的 MAC地址。IP地址和下面链路层的 MAC地址之间由于格式不同而不存在简单的映射关系(例如，IP地址有32位，而链路层的MAC地址是48位)。此外，在一个网络上可能经常会有新的主机加入进来，或撤走一些主机。更换网络适配器也会使主机的MAC地址改变(请注意，主机的MAC地址实际上就是其网络适配器的MAC地址)。地址解析协议 ARP解决这个问题的方法是在主机的ARP高速缓存中存放一个从IP地址到 MAC地址的映射表，并且这个映射表还经常动态更新(新增或超时删除)。

每一台主机都设有一个 ARP高速缓存(ARP cache)，里面存有本局域网上的各主机和路由器的IP地址到 MAC地址的映射表，这些都是该主机目前知道的一些MAC地址。

主机A按以下步骤找出主机B的 MAC 地址。

• ARP进程在本局域网上广播发送一个ARP请求分组。(a)是主机A广播发送ARP请求分组的示意图。ARP请求分组的主要内容是:“我的IP地址是 209.0.0.5，MAC地址是 00-00-C0-15-AD-18。我想知道 IP 地址为209.0.0.6的主机的 MAC 地址。”
  
• 在本局域网上的所有主机上运行的ARP进程都收到此 ARP请求分组。
• 主机B的IP地址与 ARP 请求分组中要査询的IP地址一致，就收下这个 ARP 请求分组，并向主机 A 发送 ARP 响应分组，同时在这个 ARP 响应分组中写入自己的 MAC 地址。由于其余所有主机的IP地址都与 ARP请求分组中要査询的P地址不一致，因此都不理睬这个 ARP 请求分组，如图(b)所示。ARP响应分组的主要内容是:“我的IP地址是 209.0.0.6我的 MAC地址是 08-00-2B-00-EE-0A。”请注意:虽然 ARP请求分组是广播发送的，但 ARP响应分组是普通的单播，即从一个源地址发送到一个日的地址。
• 主机A收到主机B的ARP响应分组后，就在其ARP高速缓存中写入主机B的IP地址到 MAC 地址的映射。

当主机A向B发送数据报时，很可能以后不久主机B还要向A发送数据报，因而主机B也可能要向 A发送ARP请求分组。为了减少网络上的通信量，主机A在发送其 ARP 请求分组时，就把自己的IP地址到MAC地址的映射写入ARP请求分组。当主机B收到A的ARP请求分组时，就把主机A的这一地址映射写入主机B自己的ARP高速缓存中。以后主机B向A发送数据报时就很方便了。

可见 ARP高速缓存非常有用。如果不使用ARP高速缓存，那么任何一台主机只要进行一次通信，就必须在网络上用广播方式发送ARP请求分组，这就会使网络上的通信量大大增加。ARP把已经得到的地址映射保存在高速缓存中，这样就使得该主机下次再和具有同样目的地址的主机通信时，可以直接从高速缓存中找到所需的MAC地址而不必再用广播方式发送 ARP 请求分组。

ARP对保存在高速缓存中的每一个映射地址项目都设置生存时间(例如，10~20分钟)。凡超过生存时间的项目就从高速缓存中删除掉。设置这种地址映射项目的生存时间是很重要的。设想有一种情况:主机A和B通信。A的ARP高速缓存里保存有B的MAC地址，但B的网络适配器突然坏了，B立即更换了一块，因此B的MAC地址就改变了。

下面我们归纳出使用ARP的四种典型情况

• 发送方是主机(如H1)，要把IP 数据报发送到同一个网络上的另一台主机(如H2)。这时H1发送 ARP请求分组(在网络N1上广播)，找到目的主机H2的 MAC地址。
• 发送方是主机(如H1)，要把IP 数据报发送到另一个网络上的一台主机(如 H3或H4)。这时 H1发送 ARP 请求分组(在网络 N1上广播)，找到N1上的一个路由器R1的 MAC地址。剩下的工作由路由器R1来完成。R1要做的事情是下面的(3)或(4)。
• 发送方是路由器(如R1)，要把IP数据报转发到与R1连接在同一个网络 N2上的主机(如 H3)。这时 R1发送 ARP 请求分组(在 N2上广播)，找到目的主机 H3的 MAC地址。
• 发送方是路由器(如R1)，要把IP 数据报转发到网络 N3上的一台主机(如 H4)。H4与R1不是连接在同一个网络上的。这时R1发送ARP请求分组(在N2上广播)，找到连接在 N2上的一个路由器R2的 MAC 地址。剩下的工作由这个路由器 R2来完成。

既然在网络链路上传送的帧最终是按照MAC地址找到目的主机的，那么为什么我们还要使用两种地址(IP地址和MAC地址)，而不直接使用MAC地址进行通信?只用一个MAC地址进行通信似乎可以免除使用ARP。
由于全世界存在着各式各样的网络，它们使用不同的MAC地址。要使这些异构网络能够互相通信就必须进行非常复杂的 MAC地址转换工作，因此由用户或用户主机来完成这项工作几乎是不可能的事。即使是对分布在全世界的以太网MAC地址进行寻址，也是然而IP编址把这个复杂问题解决了。连接到互联网的主机只需各自拥有极其困难的。个IP地址，它们之间的通信就像连接在同一个网络上那样简单方便，即使必须多次调用ARP来找到 MAC地址，但这个过程都是由计算机软件自动进行的，对用户来说是看不见的。因此，在虚拟的IP网络上用IP地址进行通信给广大的计算机用户带来了很大的方便。

二、IP数据报格式

IP数据报的格式说明协议IP都具有什么功能。在协议IP的标准中,描述首部格式的宽度是32位(即4字节)。下图是IP数据报的完整格式

从图可看出，一个数据报由首部和数据两部分组成。首部的前一部分长度是固定的，共 20字节，是所有IP数据报必须具有的。在首部的固定部分的后面是一些可选字段其长度是可变的。下面介绍首部各字段的意义。

1、IP 数据报首部的固定部分中的各字段

• 版本：占4位，指协议IP的版本。通信双方使用的协议IP的版本必须一致。这里讨论的协议IP版本号为4(即IP4)。关于IPv6(即版本6的协议IP)，我们将在后面的4.5 节讨论。
• 首部长度：占4位，可表示的最大十进制数值是15。请注意，首部长度字段所表示数的单位是32位字长(1个32位字长是4字节)。因为IP首部的固定部分是20字节，因此首部长度字段的最小值是5(即二进制表示的首部长度是0101)。而当首部长度字段为最大值 1111时(即十进制的 15)，就表明首部长度达到最大值–15个32位字长，即60字节。当IP分组的首部长度不是4字节的整数倍时，必须利用最后的填充字段加以填充。因此IP数据报的数据部分永远在4字节的整数倍时开始，这样在实现协议IP时较为方便。首部长度限制为60字节的缺点是有时可能不够用，但这样做是希望用户尽量减少开销。最常用的首部长度是20字节，不使用任何可选字段。
• 区分服务：占8位，用来获得更好的服务。这个字段在旧标准中叫作服务类型但实际上一直没有被使用过。1998年IETF把这个字段改名为区分服务DS(DifferentiatedServices)。只有在使用区分服务时，这个字段才起作用(见8.4.4节)。
• 总长度：总长度指首部和数据之和的长度，单位为字节。总长度字段为16 位，因此数据报的最大长度为$2^{16}$-1=65535字节。 然而实际上传送这样长的数据报在现实中
  是极少遇到的。
  虽然使用尽可能长的IP数据报会使传输效率得到提高(这样每一个卫数据报中首部长度占数据报总长度的比例就会小些)，但数据报短些也有好处。IP数据报越短，路由器转发的速度就越快。为此，协议IP规定，在互联网中所有的主机和路由器必须能够接受长度不超过 576字节的数据报。这是假定上层交下来的数据长度有512字节(合理的长度)，加上最长的IP 首部 60 字节，再加上4字节的富余量，就得到 576 字节。当主机需要发送长度超过 576 字节的数据报时，应当先了解一下，目的主机能否接受所要发送的数据报长度。否则就要进行分片。
  进行分片时(见后面的“片偏移”字段)，数据报首部中的“总长度”字段是指分片后的每一个分片的首部长度与该分片的数据长度的总和。
• 标识：占16位。IP 软件在存储器中维持一个计数器，每产生一个数据报，计数器就加1，并将此值赋给标识字段。但这个“标识”并不是序号，因为P是无连接服务，数据报不存在按序接收的问题。当数据报由于长度超过网络的MTU而必须分片时，这个标识字段的值就被复制到所有的数据报片的标识字段中。相同的标识字段的值使分片后的各数据报片最后能正确地重装成为原来的数据报。
• 标志(flag)：占3位，但目前只有两位有意义。
  • 标志字段中的最低位记为MF(MoreFragment)。MF=1即表示后面“还有分片’的数据报。MF=0表示这已是若干数据报片中的最后一个。
  • 标志字段中间的一位记为 DF(Don’tFragment)，意思是“不能分片”。只有当 DF=0时才允许分片。
• 片偏移：占13位。片偏移指出:较长的分组在分片后，某片在原分组中的相对位置。也就是说，相对于用户数据字段的起点，该片从何处开始。片偏移以8个字节为偏移单位。这就是说，除最后一个数据报片外，其他每个分片的长度一定是8字节(64位)的整数倍。
• 生存时间：占8位，生存时间字段常用的英文缩写是TTL(Time To Live)，表明这是数据报在网络中的寿命。由发出数据报的源点设置这个字段。其目的是防止无法交付的数据报无限制地在互联网中兜圈子，因而白白消耗网络资源。最初的设计以秒作为TTL 值的单位。每经过一个路由器时，就把 TTL 减去数据报在路由器所消耗掉的一段时间。若数据报在路由器消耗的时间小于1秒，就把 TIL 值减 1。当 TTL值减为零时，就丢弃这个数据报。
  然而随着技术的进步，路由器处理数据报所需的时间不断在缩短，一般都远远小于1秒，后来就把 TTL 字段的功能改为“跳数限制”(但名称不变)。路由器在每次转发数据报之前就把 TTL 值减1。若 TTL 值减小到零，就丢弃这个数据报，不再转发。因此，现在TTL的单位不再是秒，而是跳数。TTL的意义是指明数据报在互联网中至多可经过多少个路由器。显然，数据报能在互联网中经过的路由器的最大数值是255。若把TTL的初始值设置为1，就表示这个数据报只能在本局域网中传送。因为这个数据报一传送到
• 协议占8位，协议字段指出此数据报携带的数据使用何种协议，以便使目的主机的 IP 层知道应将数据部分上交给哪个协议进行处理。
  
• 首部检验和：占16 位。这个字段只检验数据报的首部，但不包括数据部分。这是因为数据报每经过一个路由器，路由器都要重新计算一下首部检验和(一些字段，如生存时间、标志、片偏移等都可能发生变化)。不检验数据部分可减少计算的工作量。为了进一步减少计算检验和的工作量，IP首部的检验和不采用复杂的CRC检验码而采用下面的简单计算方法:在发送方，先把IP数据报首部划分为许多16位字的序列，并把检验和字段置零用反码算术运算把所有16位字相加后，将得到的和的反码写入检验和字段。接收方收到数据报后，把首部的所有16位字再使用反码算术运算相加一次。将得到的和取反码，即得出接收方检验和的计算结果。若首部未发生任何变化，则此结果必为0，于是就保留这个数据报;否则即认为出差错，并将此数据报丢弃。图下图说明了IP数据报首部检验和的计算过程。
  
• 源地址：占32位。发送IP数据报的主机的IP地址。
• 目的地址：占32位。接收IP数据报的主机的IP地址。

2、IP 数据报首部的可变部分

IP数据报首部的可变部分就是一个选项字段。选项字段用来支持排错、测量以及安全等措施，内容很丰富。此字段的长度可变，从1字节到40字节不等，取决于所选择的项目。某些选项项目只需要1字节，它只包括1字节的选项代码。而有些选项需要多个字节这些选项一个个拼接起来，中间不需要有分隔符，最后用全0的填充字段补齐为4字节的整数倍。

增加首部的可变部分是为了增加IP数据报的功能，但这同时也使得IP 数据报的首部长度成为可变的。这就增加了每一个路由器处理数据报的开销。实际上这些选项很少被使用。很多路由器都不考虑 IP 首部的选项字段，因此新的IP 版本IPv6 就把IP 数据报的首部长度做成固定的了。这里就不讨论这些选项的细节了。

三、IP 层转发分组的过程

1、流程

分组在互联网上传送和转发是基于分组首部中的目的地址的，因此这种转发方式称关基于终点的转发。因此，分组每到达一个路由器，路由器就根据分组中的终点(目的地址)查找转发表，然后就得知下一跳应当到哪一个路由器。

但是，路由器中的转发表却不是按目的IP地址来直接查出下一跳路由器的。这是因为互联网中的主机数目实在太大了。如果用目的地址直接查找转发表，那么这种结构的转发表就会非常庞大，使得查找过程非常之慢。这样的转发表也就没有实用价值了。因此必须想办法压缩转发表的大小。

我们知道，32位的IP地址是由两级组成的。前一部分是前缀，表示网络，后一部分表示主机。所以可以把查找目的主机的方法变通一下，即不是直接查找目的主机，而是先查找目的网络(网络前缀)，在找到了目的网络之后，就把分组在这个网络上直接交付目的主机由于互联网上的网络数远远小于主机数，这样就可以大大压缩转发表的大小，加速分组在路由器中的转发。这就是基于终点的转发过程。

当路由器收到一个待转发的分组，在从转发表得出下-跳路由器的IP地址后，不是把路层的网络接口软件。网络接口软件负责把下一跳这个地址填入分组首部，而是送交数据链须使用ARP)，并将此MAC地址放在链路层的路由器的IP地址转换成MAC地址(必业传送到下一跳路由器的链路层，再取出MAC帧MAC 帧的首部，然后利用这个MAC地发送一连串的分组时，上述的这种查找转发表、调的数据部分，交给网络层。由此可见，当写入 MAC 帧的首部等过程，都是必须做的(当然用ARP解析出MAC地址、把MAC地址都是由机器自动完成的)。

2、案例分析

主机 H 首先必须确定:目的主机是否连接在本网络上?如果是，那么问题很简单，就直接交付，根本不需要利用路由器;如果不是，就间接交付，把分组发送给连接在本网络上的路由器，以后要做的事情都由这个路由器来处理。

主机 H 先把要发送的分组的目的地址和本网络N,的子网掩码按位进行 AND 运算，得出运算结果。如果运算结果等于本网络N的前缀，就表明目的主机连接在本网络上;否则

就必须把分组发送到路由器R，由路由器R完成后续的任务。由于采用了 CIDR 记法，转发表中给出的都是网络前缀，而没有明显给出子网码。其实只要细心观察斜线后面的数字，就可知道相应的子网掩码。例如，126的子网掩码就是点分十进制的 255.255.255.192。现在，要发送的分组的目的地址是 128.1.2.132，本网络的掩码是26个1，后面有6个0。如图上图(a)所示，按位 AND 运算的结果是 128.1.2.128，不等于本网络N,的前缀。这说明目的主机没有连接在本网络上。源主机必须把分组发送给路中器R，让路由器R,根据其转发表来处理这个分组。

路由器R,的部分转发表已在上上图右上方给出了。转发表中第1列就是“前缀匹配”这是因为查找转发表的过程就是寻找前缀匹配的过程。

现在先检查路由器R的转发表中的第1行。

源主机 H 要发送的分组的目的地址是128.1.2.132。本网络128.1.2.192/26的前缀有 26位，因此本网络的掩码是26个1，后面是6个0。目的地址和子网掩码按位 AND运算的结果是 128.1.2.128/26。很明显，AND 运算结果与转发表第1行的前缀不匹配接着检查路由器 R1 的转发表中的第2行。运算结果是 128.1.2.128/26，如(b)所示这个结果和转发表第2行的前缀相匹配。因此按照转发表第2行指出的，在网络N,上进行分组的直接交付(通过路由器的接口1)。这时路由器R1调用 ARP，解析出目的主机 H的 MAC地址，再封装成链路层的帧，直接交付连接在本网络N,上的目的主机 H2。

如果按照同样的方法，检查路由器R1的转发表中的第3行，不难得出不匹配的结果。

3、最长前缀匹配

我们把进入路由器R,的分组的目的地址分别和路由器R,的转发表第1行、第2 行子网掩码进行按位 AND 运算。运算结果都是“匹配”(建议读者自行验算一下)。那么哪一个结果是正确的呢?现在就来分析这个问题。
网络前缀128.1.24.0/22可以划分为4个更小的/24前缀（下图）。其中的一个前缀128.1.24.0/24分配给公司A，另外3个前缀分配给公司B。公司B把得到的3个前缀聚合成一个更大的前缀 128.1.24.0/22，作为路由器R,的转发表中的一个项目。请注意，这个前缀和原来的前缀在形式上是一样的，但实际的区别是很大的:在图4-26左边的网络前缀中包含地址 128.1.24.1，但公司B的聚合后的网络前缀则不包含这个地址。因此在本例中，即分组应当从接口1转发到公司A。

那么为什么地址 128.1.24.1不在公司B的聚合前缀128.1.24.0/22中，但匹配运算的结果却是匹配呢?这是因为在转发表中的项目128.1.24.0/22并未说明是由哪几个子网聚合而成的。

十分明显，进入路由器R,的分组的目的地址128.1.24.1处于公司A拥有的地址范围中而不在公司B的地址范围内。分组应当通过接口1转发到公司A。为了减少路由器R,中的项目数，公司B采用了地址聚合，把三个地址块聚合为一个地址块 128.1.24.0/22。这个聚合后得出的前缀和图中左边所示的前缀在形式上是一样的。这样就导致图 4-26所示的出现和两个网络前缀都匹配的现象。

我们可以注意到，现在公司B三个地址块得出的聚合地址块是128.1.24.0/22，但如果公司B只分到两个地址块128.1.25.0/24和128.1.26.0/24，那么其聚合地址块仍然是128.1.24.0/22。如果把公司A和公司B的地址块都聚合起来，得出的聚合地址块还是128.1.24.0/22。这样的地址聚合可以发生在路由器R2中。

因此，在采用CIDR编址时，如果一个分组在转发表中可以找到多个匹配的前缀，那么就应当选择前缀最长的一个作为匹配的前缀。这个原则称为最长前缀匹配(longest prefixmatch)。网络前缀越长，其地址块就越小，因而路由就越具体(more specific)。为了更加迅速地查找转发表，可以按照前缀的长短，把前缀最长的排在第1行，然后按前缀长短的顺序往下排列。用这种方法从第1行前缀最长的开始查找，只要检查到匹配的，就不必再继续往下查找，可以立即结束查找。
实际的转发表有时还可能增加两种特殊的路由，就是主机路由和默认路由。

主机路由(host route)又叫作特定主机路由，这是对特定目的主机的IP地址专门指明的一个路由。采用特定主机路由可使网络管理人员更方便地控制网络和测试网络，同时也可在需要考虑某种安全问题时采用这种特定主机路由。在对网络的连接或转发表进行排错时，指明到某一台主机的特殊路由就一分有用。假定这个特定主机的点分十进制IP地址是 a.b.c.d那么在转发表中对应于主机路由的网络前缀就是 a.b.c.d/32。我们知道，/32 表示的子网掩码是32个1。实际的网络不可能使用32位的前缀，因为没有主机号的IP地址是没有实际意义的。但这个特殊的前缀却可以用在转发表中。不难看出，32个1的子网掩码和IP地址a.b.c.d 按位进行 AND 运算后，得出的结果必定是 a.b.c.d，也就是说，找到了匹配。这时就把收到的分组转发到转发表所指出的下一跳。主机路由在转发表中都放在最前面。

还有一种特殊路由是默认路由(default route)。这就是不管分组的最终目的网络在哪里，都由指定的路由器R来处理。这在网络只有很少的对外连接时非常有用。在实际的转发表中，用一个特殊前缀 0.0.0.0/0来表示默认路由。这个前缀的掩码是全0(/0 表示网络前缀是0位，因此掩码是32个0)。用全0的码和任何目的地址进行按位AND运算，结果一定是全0，即必然是和转发表中的 0.0.0.0/0相匹配的。这时就按照转发表的指示，把分组送交下一跳路由器R来处理(即间接交付)。

4、分组转发算法

综上所述，可归纳出分组转发算法如下(假定转发表按照前缀的长短排列，把前缀长的放在前面):
(1)从收到的分组的首部提取目的主机的IP地址 D(即目的地址)。

(2)若查找到有特定主机路由(目的地址为D)，就按照这条路由的下一跳转发分组否则从转发表中下一行(也就是前缀最长的一行)开始检查，执行(3)。

(3)把这一行的子网掩码与目的地址 D按位进行 AND 运算。

• 若运算结果与本行的前缀匹配，则查找结束，按照“下一跳”所指出的进行处理(或直接交付本网络上的目的主机，或通过指定接口发送到下一跳路由器)。
• 否则，若转发表还有下一行，则对下一行进行检查，重新执行(3)。
• 否则，执行(4)。

(4)若转发表中有一个默认路由，则按照指明的接口，把分组传送到指明的默认路由器否则，报告转发分组出错。

5、使用二叉线索查找转发表

使用CIDR后，由于不知道目的网络的前缀，使转发表的查找过程变得更加复杂了当转发表的项目数很大时，怎样设法缩短转发表的查找时间就成为一个非常重要的问题。例如，连接路由器的线路的速率为10Gbits，而分组的平均长度为2000bit，那么路由器就应当平均每秒钟能够处理500万个分组(常记为5Mpps)。或者说，路由器处理一个分组的平均时间只有200ns(1ns=$10^{-9}$s)。因此，查找每一个路由所需的时间是非常短的。

可见在转发表中必须使用很好的数据结构和先进的快速查找算法，这一直是人们积极研究
的热门课题。对无分类编址的转发表的最简单的查找算法就是对所有可能的前缀进行循环查找，从最长的前缀开始查找。例如，给定一个目的地址。对每一个可能的网络前缀，进行目的地址和子网掩码的按位 AND 运算，得出一个网络前缀，然后逐行查找转发表中的网络前缀。所找到的最长匹配就对应于要查找的路由。

这种最简单的算法的明显缺点就是查找的次数太多。最坏的情况是转发表中没有这个路由。在这种情况下，算法仍要进行32次(第1次用32位的前缀查找转发表中所有的行，第2次用31位的前缀查找所有的行，这样一直查找下去)。

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

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

从二叉线索的根节点自顶向下的深度最多有 32层，每一层对应于 IP 地址中的一位。个IP地址存入二叉线索的规则很简单:先检查IP地址左边的第一位，如为0，则第一层的节点就在根节点的左下方;如为1，则在右下方。然后再检查地址的第二位，构造出第二层的节点。依此类推，直到唯一前缀的最后一位。由于唯一前缀一般都小于 32 位，因此用唯一前缀构造的二叉线索的深度往往不到 32层。图中较粗的折线就是前缀 0101在这个二叉线索中的路径。二叉线索中的小圆圈是中间节点，而在路径终点的小方框是叶节点(也叫作外部节点)。每个叶节点代表一个唯一前缀。节点之间的连线旁边的数字表示这条边在唯一前缀中对应的比特是0或1。

假定有一个正地址是10011011 011110100000000000000000，需要查找该地址是否在此二叉线索中。我们从最左边查起。很容易发现，查到第三个字符(即前缀10后面的0)时，在二叉线索中就找不到匹配的，说明这个地址不在这个二叉线索中。

以上只是给出了二叉线索这种数据结构的用法，而并没有说明“与唯一前缀匹配”和“与网络前缀匹配”的关系。显然，要将二又线索用于转发表中，还必须使二叉线索中的每一个叶节点包含所对应的网络前缀和子网掩码。当搜索到一个叶节点时，就必须将寻找匹配的目的地址和该叶节点的子网掩码进行按位 AND运算，看结果是否与对应的网络前缀相匹配。若匹配，就按下一跳的接口转发该分组。否则，就丢弃该分组。总之，二叉线索只是提供了一种可以快速在转发表中找到匹配的叶节点的机制。但这是否和网络前缀匹配，还要和子网掩码进行一次逻辑 AND 运算。

为了提高二叉线索的查找速度，广泛使用了各种压缩技术。例如，在上图中的最后两个地址，其最前面的4位都是1011。因此，只要一个地址的前4位是1011，就可以跳过前面4位(即压缩了4个层次)而直接从第5位开始比较。这样就可以减少查找的时间。当然，制作经过压缩的二叉线索需要更多的计算，但由于每一次查找转发表时都可以提高查找速度，因此这样做还是值得的。