计算机网络基础（三） 网络层之IP地址、ARP协议、ICMP协议和IP协议详解

01 网络层概述和IP地址

为什么需要网络层

数据链路层解决了同⼀局域⽹计算机间帧的传输问题，但还需要网络层解决不同网络间的主机通信的问题（跨局域网的通信）。

网络层提供的服务

网络层只提供简单高效的、无连接的、尽最大努力交付（不可靠传输）的数据报服务。

⽹络层不提供可靠服务指所传送的分组可能出错、丢失、重复和失序（不按序到达终点），当然也不保证分组传送的时限。

这里的分组就是指IP数据报，一个IP数据报可能会被分割为多个分片。

网络层的两个层面

网络层可以抽象的划分为 数据层面和控制层面 。

一个网络内的两个主机（直接网络）可以无需通过路由器直接通信，而两个跨网络主机的通信需要经过一个或多个路由器的转发才能让数据报到达目的地。路由器的转发功能依赖于查询路由表实现，路由表是由网络中许多的路由器按照共同选定的
路由选择协议 ，经过多次的相互交换路由信息而得到的。

因此路由器之间传送的信息有以下两⼤类：

第⼀类：转发主机之间所传送的用户数据包，这属于路由器数据层面的职责。

第⼆类：多个路由器间传送路由信息，这属于路由器控制层面的职责。

数据层⾯：

每个路由器独立工作，根据收到IP分组 的目的 地址，按转发表转发⾄下⼀跳路由器； 转发通过硬件实现，速度快（纳秒数量级，10−9秒）。

控制层⾯：

路由器间合作工作，交换路由信息。

运⾏路由选择协议，⽣成和更新路由表，路由选择算法的执行通过软件实现，耗时长，秒级；

数据层的工作比较简单，只需独立地根据路由表转发分组；而控制层面的实现要难得多，需要多个路由器协调工作。
在制造路由器时，路由选择的通信模块就被嵌入路由器中。

IP地址

IP地址是一个主机的虚拟地址，含义是指 哪个网络的哪个主机（或路由器）。 它包含了两个信息，主机所在的网络 和
主机在这个网络中的具体地址 。

IP地址长32位，采用了两级结构，由两个字段组成：n位的网络号（标识主机所在的网络） 和 32-n位的主机号（标识主机在该网络中的唯一地址或标识）。
一个IP地址的网络号表明，如果一个主机不连网，那么就没有IP地址。

IP地址的传统分类

在传统意义上，IP地址根据 n位网络号 的长度划分了5类IP地址：A~E类地址，每个类的地址都有一个开头的类别位。

A类地址：8位网络号，类别位是0；

B类地址：16位网络号，类别位是10；

C类地址：24位网络号，类别位是0；

D类地址：多播地址；

E类地址：保留地址；

A~C是单播地址（一对一通信的地址），D是多播地址。

32位的IP地址空间有2^32（接近43亿）个地址。A类地址的主机数量占了50%。

IP地址中网络号为127的地址保留作为本地软件测试本机进程和进程之间通信的用途（如127.0.0.1），不会指派，也不会把数据发送到任何网络中。网络号和主机号全0的IP用于表示默认网关，不会指派。

网络地址和主机地址

一个IP地址可能是一个网络地址 或者 主机地址 或者 广播地址。

主机号比特位全为0或者1的地址不指派给某个主机。主机号全为0的IP地址表示某个网络，是一个网络地址。主机号全为1的IP地址表示这个网络所有的主机，是一个广播地址，访问这个地址相当于向这个网络内所有主机广播。

这个规则对CIDR编址的网址也有效。

例如：5.6.7.8是一个A类地址，是一个主机M的主机地址。5.0.0.0是主机M所在的网络的网络地址，5.255.255.255是一个主机M所在网络的广播地址。

无分类编址CIDR

传统的IP地址分类是按照每8位网络号递增来划分的。

CIDR依旧根据划分网络号和主机号来对IP编址，但不要求网络号的位数n是固定的位数，而是可以为任意的位数（0~32）。

CIDR使用斜线记法，就是在IP地址后加一个 /n。n表示这个IP地址的网络号（又称网络前缀）的位数。CIDR 把⽹络前缀都相同的所有连续的 IP
地址组成“CIDR 地址块”，一个地址块就是一个网络，可以通过把一个主机地址的主机号全置为0的方式来表示这个地址块（地址块也是网络地址）；

例如：

128.14.35.7是IP地址，但未指明⽹络前缀⻓度，因此不知道⽹络地址是什么；

128.14.35.7/20是IP地址，同时指明了⽹络前缀为20位。如下：

128.14.35.7/20 = 10000000 00001110 00100011 00000111

其中加粗部分就是 128.14.35.7/20 这个主机地址的网络号。因此这个主机的网络地址如下，下面将主机号全部置为0，即红色部分：

10000000 00001110 0010 0000 00000000 = 128.14.32.0/20

由此可导出其网络地址为 128.14.32.0/20。

地址掩码（子网掩码）

计算机无法识别斜线记法，如果计算机想要知道一个主机地址的网络地址，需要使用子网掩码辅助计算。子网掩码就是网络号位全为1，主机号位全为0的32位串。斜线后面的数字就是地址掩码。

例如 128.14.32.0/20的子网掩码是：

111111111 11111111 1111 0000 00000000 = 255.255.240.0

子网掩码 & 主机地址 = 网络地址 ，这就是计算机计算网络地址的方式。

一个网络号 128.14.32.0/20 就是一个网络，里面包含的主机有 2^(32-20) - 2= 2^16 -
2台主机，这些IP地址范围在128.14.32.0~128.14.47.255之间。

这个范围内的IP中，左右两边界不能作为主机地址，也就是说128.14.32.0（网络地址）和128.14.47.255（广播地址）不能作为主机地址，其他都可以作为主机地址。

特殊的地址块

前缀 n = 32，即32位IP地址都是网络号，没有主机号。这其实就是⼀个主机的IP地址。这个特殊地址⽤于 主机路由 ；

前缀 n = 31，这个地址块中只有两个IP地址，其主机号分别为0
和1，分别是广播地址和网络地址。这个地址块⽤于点对点链路（即两个路由器直接连接，这两个路由器之间没有任何主机）；

前缀 n = 0，即0.0.0.0/0。这⽤于默认路由。

IP地址采用两级结构的好处

1、IP 地址管理机构在分配 IP 地址时只分配⽹络号， ⽽剩下的主机号则由得到该⽹络号的单位⾃⾏分配。这样就⽅便了 IP 地址的管理；

2、路由器仅根据⽬的主机所连接的⽹络号来转发分组
⽽不考虑⽬的主机号，这样就可以使路由表中的行数⼤幅度减少（即路由表的目标地址字段只记录网络号不记录具体IP地址），从⽽减⼩了路由表所占的存储空间。

子网划分

一个网络地址就代表一个网络或者说一个局域网，一个局域网内包含0个或多个路由器。

一个局域网里的所有主机的网络号都是相同的。每一个 不再划分 的局域网（最小单位的局域网）中含有0个路由器。每个局域网和局域网之间通过路由器连接。

一个大的网络地址可以划分为多个小的网络地址（通过把网络号的位数变长），这样就可以将一个大的局域网划分为多个小的局域网，称为 子网划分 。

互联网中的某个ISP（网路运营商）可看做是一个庞大的局域网，它的网络地址是206.0.64.0/18，内含主机（和路由器）数量为 2^14 - 2个。

现在某大学需要800个IP，ISP就将 206.0.64.0/18这个大的网络切一个小的网络206.0.68.0/22
（包含2^10=1024）给它用，这个学校有4个学院，每个学院的网络需要隔离开来，于是学校又将 206.0.68.0/22 这个网络划分为以下子网：

206.0.68.0/23

206.0.70.0/24

206.0.71.0/25

206.0.71.128/25

某个IP
206.0.71.111它既是三院局域网的主机（206.0.71.111/25），也可以是大学局域网的主机（206.0.71.111/24），也可以是该ISP局域网的主机（206.0.71.111/18），但是最能精准描述该主机所处局域网的IP是
206.0.71.111/25。

使用CIDR编址的好处是，需要划分子网的时候，可以根据每个区域或主体（例如学校，公司，家庭）所需的主机数量灵活的分配网络大小和IP数量。

总结IP地址重要特点

每⼀个IP地址都由⽹络前缀（网络号）和主机号两部分组成：IP地址管理机构只分配⽹络前缀，主机号由得到该⽹络前缀单位⾃⾏分配；

路由器根据⽬的主机所连接的⽹络前缀转发分组；

⽤集线器或交换机连接起来的多个机器集合是⼀个⽹络，因此这些机器都具有同样的⽹络前缀；

用路由器连接起来的多个主机集合是多个网络（多个局域网），一个网络连向路由器的一个接口，这个路由器有多少个接口就连着多少个网络。

一个设备必须连接入一个网络才会有一个该网络分配给它的IP地址，如果没有连接网络的设备或主机就没有IP地址，而如果连接了多个网络（比如路由器，或者一些连接多个网络的主机）就会被分配多个IP地址。

所有分配到⽹络前缀的⽹络，⽆论是范围很⼩的局域⽹，还是可能覆盖很⼤地理 范围的⼴域⽹，都是平等的。

如下图所示：

图中是一个大局域网，划分为了6个小局域网，红色是3个，灰色是3个，每个灰色的链路是路由器直接相连的，不含任何主机的局域网，也就是前面说的点对点链路。

图中每个路由器总是具有两个或两个以上的IP地址，并且每⼀个接口都有⼀个不同网络号的IP地址。

两个路由器直接相连的两个端口可以分配IP也可以不分配IP（就可以省下2个IP），如果不分配IP，则这两个路由器间的网络又称 匿名网络 。

02 ARP协议和ICMP协议

地址解析协议 ARP

ARP协议是一个根据目标IP获得去往目标主机的路途中下一个路由器的MAC地址的网络层协议。

计算机通信时会使用IP地址（逻辑地址）和MAC地址（物理地址），假如主机H1要发送一个网络包给另一个网络里的主机H2，这个网络包内的IP地址和MAC地址如何变化？

如下图所示：

1、一个MAC地址只能够在一个局域网内工作，属于局域网A的MAC地址在局域网B内是无法被识别的（因为局域网B的广播无法到达局域网A的MAC地址）；

2、因此 MAC帧要在不同局域网之间传输，MAC帧首部的源MAC地址和目标MAC地址会不断发生改变；

3、上图中2个路由器R1和R2连接，R1因为同时连接到2个局域网因此他有两个MAC地址；

ARP是解决同⼀个局域⽹上的主机或路由器的IP地址和MAC地址的映射问题。 ARP报文无法跨局域网 。

ARP工作原理和流程：

0、 每个主机或路由器都保存着一个路由表和一个ARP缓存表 。
路由表记录着目标IP地址的下一跳IP地址。ARP缓存表保存同一局域网内的IP地址和它们对应的MAC地址。

1、H1从自己的路由表找到下一跳的IP为R1路由器，H1在 自己的 ARP 缓存表中查看有⽆ R1 的 IP/MAC 地址映射：

2、如有，就可查出其对应的MAC地址，再将其写⼊ MAC 帧头部，然后通过局域⽹将该 MAC 帧发往R1；

3、如没有，H1的 ARP 进程在局域⽹内⼴播发送⼀个 ARP 请求分组。H1会收到R1的 ARP 响应分组，将得到的 R1的IP/MAC
地址映射写⼊自己的ARP ⾼速缓存。知道了R1的MAC地址后，H1就可以封装用户数据的MAC帧给R1，由R1发往下一个网络。

ARP请求报文如下：

ARP请求报文和响应报文也是封装在MAC帧中传输的。

ARP请求报文的目标MAC地址是ff:ff:ff:ff:ff:ff（全部为1表示广播地址），源MAC地址是H1的MAC地址。

ARP请求广播后，只有R1才会接受到，其他设备会丢弃，因为ARP头部已经写明目标IP是R1。之后R1会回复一个ARP响应报文。

ARP响应报文的目标MAC地址是H1的MAC地址，而源MAC地址则是R1的地址。ARP请求报文会广播，而ARP响应报文会直接一对一单播给R1。

ARP缓存表可以减少 ARP 广播的数量。

注意点：

ARP协议不能穿透路由器：

ARP ⽤于解决同⼀个局域⽹上的 IP 地址和MAC地址的映射问题；

ARP缓存表的每一行都有一个生存时间，过了生存时间会自动删除。

互联网控制协议 ICMP

ICMP ⽤于IP 协议中发送控制消息。因为 IP 协议现在有两类版本：IPv4 和 IPv6 ，所以 ICMP 也有两个版本：ICMPv4 和
ICMPv6。

ICMP 的功能

1. 确认 IP 包是否能够成功到达⽬标地址，当两个设备通过互联⽹相连时，任意⼀个设备发送给另⼀个设备的 IP 包如果没有交付成功，就会⽣成 ICMP
数据包发送给设备共享。

2. ⽹络诊断 ，经常使⽤ ICMP 数据包的两个终端程序是 ping 和 traceroute ， traceroute
程序⽤于显示两台互联⽹设备之间可能的路径并测量数据包在 IP ⽹络上的时延。

ping 程序是 traceroute 的简化版本。

ICMP报文有两种类型： 差错报告报文和询问报文 。

ICMP报文是作为数据被封装在IP数据报内部的，但ICMP是网络层的协议。

ICMP报文的格式：

ICMP差错报告报文共4种：

1 终点不可达：例如目标进程没启动、主机没开机等；

2 时间超过：当TTL=0时IP数据报被路由器丢弃，此时丢弃包的路由器会发送一个时间超过的ICMP报文给源主机；

3 参数问题：当路由器或目的主机收到数据报首部字段不正确（例如目标IP和接收方IP不一致）会丢弃该数据报，并向源主机发送一个参数问题报文；

4 重定向：路由器把改变路由报文发送给主机，告诉主机下次应该将报文发送给另外的路由器（找到了更好的路由）。

举个例子：某个网络N0里的主机A要发送一个IP包给网络N1的主机B，N0与路由器R1和R2连接，R1与N1连接，R2与N2连接。主机A的默认路由是R2，因此IP包会交给R2转发到网络N2中，但R1和R2交换路由信息，R2发现让R1转发这个包可以更快到达主机B。因此R2会发送一个重定向的ICMP给A，A就会在路由表加一行：当B为目的主机时，下一跳应该选R1。

其中17和18已废弃。

ICMP 差错报告报文的数据内容是什么

假设主机A向主机B发送一个IP数据报，这个数据报就是图中第一行的数据报。该数据报由于出错没有到达主机B，路由器C发送一个ICMP报文给A。该ICMP报文的数据部分是A的IP报文的首部+它的数据的前8个字节。然后改ICMP报文作为数据封装到路由器C要发送的IP数据报中。

ICMP数据字段为什么需要加上原始出错IP中的数据字段前8个字 节？

因为这8个字节是TCP或UDP报文段的目的端口和源端口以及序号，这样就能告诉发送端是哪⼀个进程发送的IP数据报出错。

不应发送ICMP的情况

对 ICMP 差错报告报⽂不再发送 ICMP 差错报告报⽂

对数据报第⼀个分⽚发 送 ICMP报文，剩下的分片都不发 送 ICMP 差错报告报⽂。

对具有多播地址的数据报都不发送 ICMP 差错报告报⽂。

具有特殊地址（如127.0.0.0 或 0.0.0.0）的数据报不发 送 ICMP 差错报告报⽂。

ICMP询问报文有两种

1、回送请求/回答报文：请求type=8，回答type=0

该类报文用于测试目的主机是否可到达。ping用的就是这种ICMP报文。

2、时间戳请求/回答报文：请求type=13，回答type=14

该类报文用于计算报文的RTT（网络时延），请求报文会记录发送时间，回答报文会记录接收时间。

询问报文和差错报告报文的区别在于，前者一定包括请求和回答2个一对的报文，会有响应。

traceroute命令的原理

traceroute进程从源主机向目标主机发送一连串的IP数据报，里面封装的是无法交付的UDP报文（例如目的端口使用了目标主机不存在的进程端口）。

源主机发送的第一个数据报P1设置其生存时间TTL=1，P1到达第一个路由器R1就被丢弃（TTL减1等于0），并向源主机发送一个ICMP时间超过差错报告。

源主机又发送第二个数据报P2，TTL=2，该报文会经过2个路由器，然后被第二个路由器发送ICMP时间超过差错报告。

重复上述过程，一直到最后一个数据报刚好到达目的主机，TTL刚好减剩为1，主机不再对TTL减1。但由于ICMP包里的目的端口指定的进程不存在，因此目的主机会向源主机发送终点不可达的ICMP报文。

这样源主机就可以知道从源主机出发到目标主机所经过的每一个路由器的IP（由ICMP的发送方IP可知）和RTT，从而知道源主机到目的主机的路径和时延。

03 IP协议

IP数据报

IP数据报由首部和数据两部分组成：

⾸部的前⼀部分是固定⻓度，共 20 字节；

⾸部的后一部分是⼀些可选字段，其⻓度是可变的。

下面是IP首部的字段介绍：

版本：占 4 位，指 IP 协议的版 本。⽬前的 IP 协议版本号为 4 (即 IPv4)。

⾸部⻓度：占 4 位，可表示的最 ⼤数值是 15 个单位(⼀个单位为 4 字节)。IP 的⾸部⻓度的最⼤值 是 60 字节。⼀般IP⾸部仅有固
定部分20字节。

区分服务：指明期望获得哪种类型的服务（该字段一直未被使用过）。

总⻓度：占 16 位，⾸部 + 数据，单位为字节，数据报的最⼤⻓度 为 65535
字节。但实际上总长度不会超过数据链路中的MTU。如果发生IP数据报分片，则总长度字段等于每个分片的首部长度和数据长度的总和。

标识：是⼀个计数器，⽤来产⽣ IP数据报标识。一个IP数据报可能分成多个分片，所有IP分⽚的标 识与原始IP标识⼀致，便于接收 方还原原始IP数据报。

标志：占3位，最⾼位⽆意义。

中间位DF（Don’t Fragment）：

• DF=1，不允许分⽚；

• DF=0，允许分⽚。

最低位MF（More Fragment）：

• MF=1，后⾯还有分⽚；

• MF=0，这是最后⼀⽚。

⽚偏移：占13位，某⽚在原始IP中的 相对位置，以8字节为单位。

⽣存时间：占8 位，记为 TTL (Time To Live)，指示数据报在⽹络中可通
过的路由器数的最大次数（称为跳数），TTL是为了防止无法交付的数据报无限制的在互联网中兜圈子，白白消耗网络资源。路由器收到
IP数据报后，将TTL减1，减1之后 TTL值若变为0，路由器丢弃该IP数
据报。并向源端报超时错误。默认最大跳数为255。若报文的初始TTL设为1，表示该IP数据包只能在本局域网中传输。

协议：占8 位，指出此数据报携带的 数据使⽤何种协议（TCP或UDP），以便⽬的主机 的 IP 层将数据部分，上交给那个处 理过程。

⾸部检验和：占16 位，只检验数据报的 ⾸部，不检验数据部分。这⾥不采⽤ CRC 检验码⽽采⽤简单的计算⽅法（即首部分为多个16位串求和取反）。

地址：源地址和⽬的地址都各占 4 字节。

IP数据报分片

MTU（链路层的最大传输单元）是由局域网的链路决定的，一个局域网内的MTU相同，不同网络的MTU可能不同。

下面是一个数据包经过多个链路的分片过程：

一个数据报长6558字节，链路1的MTU = 1480，主机A对数据报分片情况如下：

分片1~4到达路由器M后，由于它们的长度超过了路由器M到路由器N之间的链路的 MTU = 800，所以路由器M 在输出链路之前还要对分片1~4再分片。

IP层转发分组过程

路由器转发遵循2个原则： 基于终点转发、最长前缀匹配 。

基于终点转发

路由表是根据数据报首部的目的IP地址查路由表找到下一跳的接口进行转发的。

为了压缩路由表的行数，路由表不记录所有目标（全球范围）的主机地址，而是记录目标的网络地址。查路由表不直接查目的主机，而是查目的网络。

举一个例子：

主机H1发送一个数据报给H2会发生如下事情。

1、判断H2的IP是否在本网络中，具体做法：通过将H1所在网络N1的网络地址（128.1.2.0/26
）的子网掩码（255.255.255.192）与H2的IP地址（128.1.2.132）进行&运算。

如果得到的结果res 等于
N1的网络号，说明H2和H1在同一个网络里面，此时无需经过路由器转发，只需要H1使用ARP协议询问到H2的MAC地址，然后H1封装包含数据的MAC帧，由交换机转发给同一链路的H2即可。

2、一个网络的默认网关是这个网络相连的众多路由器中的一个，这里假定N1的默认网关路由器是路由器R1（128.1.2.1）。

H1通过ARP获取 128.1.2.1这个IP的MAC地址。报文通过交换机传到R1。

3、R1根据报文的目的IP与它路由表里的每一行记录的网络号（网络前缀）一一匹配，所谓的匹配其实还是用目的IP与这些网络号的掩码一一做&运算得到res，看res是否等于这行网络号。每行的网络号就代表一个网络，每行都做&运算相当于在问每个网络，这个目的IP在不在你们这些网络里。

目的IP是 128.1.2.132。

与第一行匹配

128.1.2.132 & 255.255.255.192 = 128.1.2.128 ≠ 128.1.2.0

与第二行匹配

128.1.2.132 & 255.255.255.128 = 128.1.2.128 = 128.1.2.128

所以与第二行匹配成功，第二行的下一跳没有，是直接交付接口1，即R1的接口1是连着128.1.2.128/25这个网络的。R1将报文交付给H2（ARP广播找到H2的MAC地址，更换原报文的目标MAC地址，交给交换机转发该报文给H2）。

4、假如H1是要发送数据给H3而不是H2呢？那么报文到达R1之后，查路由表发现第3行匹配。于是报文转发给128.1.2.254这个路由器R2转发。

两个问题：

如果路由表匹配结果有多个怎么办？（答：使用最长前缀匹配原则）

一个都没匹配到怎么办？（答：走默认路由）

最长前缀匹配

在查找路由表时可能会得到不⽌⼀个匹配结果：

应当从匹配结果中选择具有最⻓⽹络前缀的路由，⽹络前缀越⻓，其地址块就越⼩，因⽽路由就越具体 。

下面是一个最长匹配的实例：

目标地址 206.0.71.130 和 两个路由网络地址206.0.68.0/22、206.0.71.128/25 都能成功匹配，此时应该选择
206.0.71.128/25 这个路由作为下一跳，因为它的网络号长25位，比206.0.68.0/22的网络号长。

其实不是说走 206.0.68.0/22这个路由到不了目的主机，但是要多经过几条链路和路由器的转发，因为206.0.68.0/22这个网络的范围更大。

为了更加迅速的查找转发表，可以按照前缀的长短排序，长的放前面，前缀最长的排在第一行，只要匹配到就肯定是最精确的，无需再往下匹配。

主机路由

前面我们说，路由表索引字段记录的都是网络号，根据网络号给目标IP匹配下一跳。

其实索引字段也可以是特定的某一个主机（即/32的IP地址），这样的路由称为主机路由（特定主机路由）。如下所示，红色的就是主机路由，黑色部分是网络路由：

采⽤特定主机路由有2个用途(知道即可，不是重点）：

1、测试这条⽹络链路能够走通，以及性能如何。

R2到目标主机10.0.0.10/32可能有5条链路，但我就希望R2选择下一跳为20.0.0.1这条链路，测试一下这条链路的性能。

2、考虑某种安全问题时采⽤这种特定主机路由。

怕报文走其他链路会被拦截和攻击，因此指定 10.0.0.10/32这个主机只走下一跳为20.0.0.1这条更安全的链路。

默认路由

默认路由是 0.0.0.0/0，每一个路由器的路由表都会有一个默认路由。

默认路由的出现是为了减少路由表的行数
，毕竟路由表不可能记录全世界所有网络的网络地址，只能记住本路由器邻近的多个网络地址。当路由器A根据目的地址的网络号检索不到它所知道的网络地址时，就可以交给默认路由，这个默认路由的下一跳是默认的一个路由器B，交给这个路由器B转发，如果B也找不到，则再交给B的默认路由C，以此类推。

综上，路由器分组转发算法如下：

有结构的路由表

为了进⾏更加有效的查找，通常是将路由表存放在二叉搜索树中。

如果直接使用表格存储路由表，匹配路由的时候需要一行行的匹配，假如路由表有1万行，而目的地址只能匹配到最后一行的默认路由，就需要匹配1万次。

路由表中IP地址存⼊⼆叉树的规则：对于路由表里的每一行，先检查IP地址左边的第⼀位，如为 0，则第⼀层的节点在根节点的左下⽅；如为 1，则在右下⽅。

然后再检查地址的第⼆位，构造出第⼆层的节点。依此类推，直到网络地址的最后⼀位。

叶子节点记录下一跳的地址。

假设路由表中有如下5行：

假设目的IP是 0110xxxx…，则查找过程为：左节点 -> 右节点 -> 右节点（到达叶子节点），匹配成功。

假设目的IP是 110xxx…，则查找过程为：右节点-> 没有右节点了，由于 没有到达叶子节点就结束了，说明路由表没有匹配的路由，走默认路由 。

树的最大高度就是IP地址的位数，对于IPv4而言树的高度就是32，这么一来查找的复杂度从O(n）降到了O(1)，因为无论路由表里面有多少条路由，最多只需查找32次。