计算机网络原理：网络层

todo

一、网络层服务

二、数据报网络与虚电路网络

三、网络互连与网络互连设备

四、网络层拥塞控制

五、Internet网络层

Internet是目前世界上最大、最重要的计算机网络。Internet 网络层主要包括网际协议(Internet Protocol, IP)、路由协议以及互联网控制报文协议（Internet Control Message Protocol, ICMP）等内容。

5.1、IPv4协议

IP目前主要有两个版本：IPv4和IPv6。到目前为止，Internet 仍然以IPv4为主，因此，在不加以特别说明的情况下，在提到IP时，就是指 IPv4。

IP协议定义了如何封装上层协议（如UDP、TCP等）的报文段，如何进行网络层寻址以及如何转发IP数据报等内容，是Internet网络层最核心的协议。

5.1.1、IP数据报格式

IPv4数据报的格式，如下图所示

一个IP数据报由首部和数据部分组成。首部的前20字节是固定部分，是所有IP数据报必须有的；固定部分的后面是一些可选字段，属于可变部分，其长度是可变的。下面介绍首部各字段的意义。

版本号字段，占4位，给出的是IP的版本号。主机根据该字段确定按哪个版本的IP来解析数据报。
首部长度字段，占4位，给出的是IP数据报的首部长度，包括可变部分，以4字节为单位。4位可表示的最大数值是15，因此IP数据报的首部长度的最大值是60字节。

版本号字段和首部长度字段分占一个字节的高4位与低4位，在实际IP数据报中对应一个字节。例如，一般情况下，一个IP数据报首部不包含选项字段（下面如无特殊说明，默认为这种情况），即IP数据报的第1个字节是 45H （十六进制），表示IPv4，首部长度为5x4=20 字节。

通常，路由器在解析IP数据报时，只需要对其首部进行解析，而首部长度却不是固定的，因为首部中可能包含了一些可选的首部选项，所以首部长度字段用来说明 IP 数据报的首部长度是多少，进而能告诉路由器从哪里开始是数据报中所承载的传输层数据（或其他协议报文）。
区分服务字段，占8位，在旧标准中称为服务类（Type Of Service, TOS）字段，用来指示期望获得哪种类型的服务。

该字段只有在网络提供区分服务（DiffServ）时才有效，提供区分服务的路由器根据该字段的不同取值，为IP数据报提供不同类型的服务。目前的 IP网络大部分情况下不使用该字段，即IP数据报的区分服务字段（IP数据报的第2个字节）的值为00H。
总长度字段，也称为数据报长度字段，占16位，给出 IP数据报的总字节数，包括首部和数据部分。

16位可以表示的最大IP数据报的总长度为65535字节，即最大的IP数据报可以封装65535-20=65515 字节的数据。实际上，IP数据报需要进一步封装到链路层数据帧中进行传输，几乎没有如此大 MTU（最大传输单元）的链路，因此实际网络中不会有这么大的IP数据报。
标识字段，占16位，用于标识一个IP数据报。IP协议使用一个计数器，每产生一个IP数据报计数器加1，作为该IP数据报的标识（ID）。

该字段容易被误解为是IP数据报的唯一标识，其实由于IP产生标识的机制，不同主机产生的IP数据报完全有可能具有相同的标识，所以单靠标识字段无法唯一标识一个IP数据报。实际上，IP是依靠标识字段、源IP地址、目的IP地址以及协议等字段共同唯一标识一个IP数据报。

标识字段最重要的用途是，在IP数据报分片和重组过程中，用于标识属于同一原IP数据报。
标志字段，占3位，其结构如下图所示，其中最高位保留，DF是禁止分片（Don’t Fragment)）标志，MF是更多分片（(More Fragments）标志。

DF=0表示允许路由器将IP数据报分片，DF=1表示禁止路由器将IP数据报分片。如果路由器在转发一个DF=1的IP数据报时，其总长度超过输出链路的MTU，路由器不会对该IP数据报进行分片，而是会丢弃该分组。

MF=0表示该IP数据报是一个未被分片的IP数据报或者是被分片IP数据报的最后一片，具体是哪种情况，要结合片偏移字段确定。MF=1表明该 IP数据报一定是一个IP数据报的分片，并且不是最后一个分片，同样，到底是哪个分片要结合片偏移字段确定。
片偏移字段，占13位，表示较长的原IP数据报分片后，某个分片在原IP数据报中的相对位置，即分片是从原IP数据报的哪个字节开始。

该字段以8字节为单位。值为0时，其含义还要结合MF标志位来确定，如果MF=0，表示这是一个未被分片的IP数据报；如果MF=1，则表示这是一个IP分片，且是第一个分片。
生存时间（Time-To-Live, TTL），字段占8位，表示 IP 数据报在网络中可以通过的路由器数（也称为跳数）。

该字段用来确保一个IP数据报不会永远在网络中游荡（例如路由择算法错误地为其选择了一个环形路由）。源主机在生成IP 数据报时设置 TTL 初值，每经过路由器转发一次TTL减1，如果 TTL=0，路由器就丢弃该IP数据报，并向源主机发送Type=11，Code=0的ICMP 报文。TTL字段占8位，因此，IPv4数据报最多能够经过256跳。

利用TTL可以实现一些有趣的应用，例如，Linux 操作系统中的traceroute命令，就利用了TTL实现数据传输路径的跟踪。
协议字段，占8位，指示该IP数据报封装的是哪个上层协议的报文段。例如，6为TCP，即封装的是TCP报文段；17为UDP，即封装的是 UDP 数据报。常用的一些协议和相应的协议字段值如下图所示。
首部校验和字段，占16位，利用校验和实现IP数据报首部的差错检测。

在计算校验和时，该字段置为全0，然后整个首部以16位对齐，采用与UDP校验和相同的计算方法，即采用反码算数求和运算（加的过程将最高位的进位“卷回”到和的最低位再加），将最后得到的和，取反码作为首部校验和字段。在接收IP数据分组时，将整个首部按同样算法求和，结果为16位1，表示无差错，只要有一位不为1，就表示首部有差错，丢弃该分组。

该字段在路由器每次转发分组时需要重新计算后重置，因为IP数据报首部中的某些字段（如TTL），在转发过程中会发生改变，必须重新计算首部校验和。所以，首部校验和是逐跳校验、逐跳计算的。
源IP地址字段，占32位，是发出IP数据报的源主机的IP地址。当网络中的某台主机接收到来自传输层的报文段后，需要在网络层对该报文段进行封装，在IPv4数据报中，需要将发送主机的IP地址填充至源IP地址字段。
目的IP地址字段，占32位，表示该IP数据报需要送达的目的地主机的IP地址，路由器将依据该地址检索路由表，决策如何转发该IP数据报。

用户在源主机上使用某网络应用时，或者直接给出目的主机的 IP 地址，或者给出目的主机的域名。如果是利用域名指定欲访问的目的主机，则源主机会通过 DNS来将目的主机域名解析成对应的IP地址，最后在封装IP数据报时，目的主机的IP地址被填入数据报的目的IP地址字段。
选项字段，长度可变，范围在1 ~ 40字节，取决于选项内容。选项字段用来对IP首部进行扩展，可以携带安全、源选路径、时间戳和路由记录等内容。

实际上，选项字段之后还可能有一个填充字段，长度为0~3字节，取值全0。填充字段的目的是补齐整个首部，使之符合32位对齐，即保证首部长度是4字节的倍数。绝大多数IP数据报的首部中没有选项字和填充字段。
数据字段。数据字段存放IP数据报所封装的传输层报文段，目的地主机会将其所承载的数据交付相应的上层协议（依据协议字段）。不过，IPv4 数据报承载的并总是来自所谓的上层协议报文段，也可能封装其他协议的报文，比如ICMP报文。

5.1.2、IP数据报分片

Internet是全球最大的互联网络，一个IP数据报从源主机到目的主机的传输过程中，可能会经过多个运行不同数据链路层协议的网络，如以太网、IEEE 802.1无线局域网等。不同数据链路层协议所能承载的网络层数据报的最大长度不尽相同，以太网帧可以承载的数据最大长度为1500字节，而有些数据链路层协议所能承载的数据最大长度远小于这个值。

数据链路层协议帧所能承载的最大数据量称为链路的最大传输单元（Maximun Transmissin Unit, MTU）。网络层数据报作为数据链路层协议帧的有效载荷，其总长度显然受数据链路的MTU限制，这就是为什么虽然IP数据报总长度最大可达65535字节，而实际IP数据报总长度很少超过1500 字节。

问题：当路由器要将一IP数据报转发至某个输出端口，而该数据报总长度大于该输出端口所连接链路的MTU时，路由器如何处理该IP数据报呢？

答案是路由器会对IP数据报分片(DF=0 时）或者将其丢弃(DF=1时）。接下来，介绍路由器如何对IP数据报分片。

由于同一IP数据报分出来的多个IP分片都属于同一个原IP数据报，因此这些IP分片的协议版本、标识、源IP地址、目的IP地址等直接继承原IP数据报对应字段的值即可。注意，路由器只负责 IP数据报分片，不进行IP分片重组，IP分片的重组任务由最终目的主机的 IP来完成。当IP分片陆续到达目的主机后，目的主机将这些分片重组后，还原成原IP数据报，并提取协议字段交给相应上层协议处理。目的主机重组分片的过程如下：

首先，根据各分片的首部标识字段，可以判断这些分片是否属于同一个IP数据报，即同一IP数据报分出来的IP分片具有相同的标识字段；
其次，根据各分片的首部标志字段（MF），可以判断某个分片是否是最后一个分片；
最后，根据各分片的首部片偏移字段，可以判断各IP分片的先后顺序，结合每个IP分片首部的数据报长度字段，还可以判断是否缺少IP分片（比如某个IP分片丢失）。

接下来，给出IP数据报分片的相关计算方法。假设，原IP数据报总长度为L字节，待转发链路的MTU为M字节。若L>M，且DF=0，则该IP数据报可以且需要分片。分片时每个分片的标识（ID）字段复制原IP数据报的标识字段；MF标志位，除了最后一个分片为0外，其他分片全部为1。通常，分片时会将原IP数据报分成尽可能少的IP分片，即除最后一个分片外，其他分片都分为 MTU 允许的最大分片。

一个分片最大可封装的数据字节数应该是8的倍数，因此，最大分片可封装的数据长度（字节）为

d=\left \lfloor \frac{M-20}{8} \right \rfloor * 8

式中，20表示IP数据报首部长度为20字节。需要的IP分片总数为

n = \left \lfloor \frac{L-20}{d} \right \rfloor

每个IP分片的总长度字段为

L_i = \left\{\begin{matrix} d+20, & 1 \le i \lt n \\ L - d(n-1), & i=n \end{matrix}\right.

每个IP分片的MF字段为

MF_i = \left\{\begin{matrix} 1, & 1 \le i \lt n \\ 0, & i=n \end{matrix}\right.

每个IP分片的片偏移字段取值为

F_i = \frac{d}{8} * (i-1), 1 \le i \le n

式中， $F_i$ 为第i个分片的偏移量。

下面，给出一个IP分片的实例。假设原IP数据报的总长度为3820字节，其数据部分长度为3800字节（使用固定首部），需要分片成长度不超过1420字节的数据报分片。由于固定首部长度为20字节，因此每个分片的数据部分长度不能超过1400字节。于是分为三个分片，其数据部分的长度分别为1400、1400和1000字节。原始数据报首部被复制为各分片的首部，但必须修改有关字段的值。下图所示为分片结果（请注意片偏移的数值）。

下表列出了上例中数据报首部中与分片有关的字段中的数值，其中标识字段的值是任意给定的（12345）。具有相同标识的数据报片在目的站就可无误地重装成原始数据报。

现在假定数据报片2经过某个网络时还需要再进行分片，即划分为数据报片2-1（携带数据800字节）和数据报片2-2（携带数据600字节）。那么这两个分片的总长度、标识、MF、DF和片偏移分别为：820，12345，1，0，175和620，12345，1，0，275。

5.2、IPv4编址

主机在发送应用层数据时，经过层层封装，在网络层会将源主机 IP 地址以及目的主机IP地址填充到 IP数据报的首部中。路由器依据目的IP地址查询转发表，转发IP数据报，最终将其送达目的主机。那么，一台主机只能有一个 IP地址吗？

答案是否定的，一台主机可能会同时具有多个IP地址。例如，某主机同时通过以太网和 IEEE802.11 无线局域网连接Internet，这台主机就可能同时具有两个不同的IP 地址。路由器通常有多个网络接口，每个接口都具有一个IP地址。因此，严格地说，IP地址是与接口相关联的，而并不是与某台主机或路由器一一对应。但考虑到很多主机（比如台式PC)，在通常情况下只有一个网络接口（即网卡）连接网络，也就只有这一个接口的IP地址，所以习惯上还是经常使用“某主机的IP地址”来叙述。

IPv4 地址长度为32位，共有 $2^{32}$ 个不同的IP地址，这个数目约为43亿（4 294 967 296）。IPv4 地址有3种常用的标记法，即：二进制标记法、点分十进制标记法、十六进制标记法，如下表所示。最常用的是点分十进制标记法，即将IPv4地址划分为4个8位组，每个8位组分别转换为十进制数，然后利用小数点分隔 4个十进制数。这是人们最熟悉IPv4地址形式。

标记方法	示例
二进制标记法	11000000 10100000 00000001 01100101
点分十进制标记法	192.168.1.101
十六进制标记法	0xC0A80165

因特网中的主机和路由器的网络接口都必须具有唯一的 IP地址。然而，这些IP地址不能随意或随机分配。

如下图所示的网络中，具有3个接口的路由器，通过两台交换机，互连了6台主机。可以注意到，左侧的3台主机以及与这3台主机所连接的路由器接口，其IP地址都具有203.1.1.xxx的形式，这3台主机以及与其相连的路由器接口组成了一个网络（不包含整个路由器），这个网络是通过一个交换机相连接组成的一个LAN。

将上图中，左侧互连的3台主机与路由器左侧接口的网络称为一个IP子网。在IP编址中，会为每一个IP子网分配一个子网地址，对应于上图中的左侧子网，其子网IP地址为203.1.1.0/24。其中，／24（即 24 位前缀，对应于子网掩码）对子网的地址进行了定义。子网203.1.1.0/24由3台主机（203.1.1.2、203.1.1.3、203.1.1.4）以及一个路由器接口（203.1.1.1）组成。

IP子网的概念相当于是为网络地址引入了层次。举个例子，每个人都有其户籍所在城市，在其户籍所在城市，如果要寻找某人，还需要更详细的住址才可以。对于IP地址来说也是如此，基于IP子网概念，可以将主机 IP 地址划分为两个部分：一部分是前缀（Prefix），即网络部分（NetlD），用于描述主机所归属的网络；另一部分是后缀（Postfix），即主机部分（HostID），用于表示主机在网络内的唯一地址。

对于用于表示主机所处网络的前缀，其长度可以是定长的，也可以是变长的。早期的IP地址被设计为定长前缀，这种方式被称作分类地址；而目前所使用的主流的方式则是无类地址，在无类地址中，网络前缀的长度是可变的。

5.2.1、分类地址

在因特网刚开始发展的时期，IPv4地址被设计为定长前缀，但考虑到不同组织所要使用到的地址数量是不同的，因此设计了3种长度的前缀，分别为8、16、24位，整个地址空间被分为5类，A、B、C、D和E类，并规定A、B、C三类可以分配给主机或路由器使用，D类地址作为组播地址，E类地址保留，该方案被称作分类寻址。具体分类方法是依次从最高比特位逐步“二分”，如下图所示。

分类寻址中，各类地址空间如下表所示。

类	前缀长度	前缀	首字节
A	8位	0xxxxxxx	0 ~ 127
B	16位	10xxxxxx xxxxxxxx	128 ~ 191
C	24位	110xxxxx xxxxxxxx xxxxxxxx	192 ~ 223
D	不可用	1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx	224 ~ 239
E	不可用	1111xxxx xxxxxxxx xxxxxxxx xxxxxxxx	240 ~ 255

对于A类地址，其前缀长度为8位，其中第一位为0，前缀中的后7位用来表示网络址址，即总共有 $2^7=128$ 个A类网络，每个A类网络的IP地址总数为 $2^{24}=16 777 216$ 。

对于B类地址，其前缀长度为16位，其中前两位为10，前缀中的后14位用来表示络地址，即总共有 $2^{14}=16 384$ 个B类网络，每个B类网络的IP地址总数为 $2^{16}=65 536$ 。

对于C类地址，其前缀长度为24位，其中前三位为110，前缀中的后21位用来表示络地址，即总共有 $2^{21}=2 097 152$ 个C类网络，每个C类网络的IP地址总数为 $2^8=256$ 。

5.2.2、特殊地址

A、B、C类地址可以用于标识网络中的主机或路由器，但并不是所有地址都可用，因为有些地址有特殊用途，不能分配给主机或路由器。网络中一些常见的特殊地址如下。

本地主机地址：0.0.0.0/32。当主机需要发送一个IP数据报时，需要将自己的地址为源地址，但是在某些情况下（比如，新加入到网络中还未通过 DHCP 协议获取到IP地址的主机），主机还不知道自己的IP地址，此时会用本地主机地址填充IP数据报的源地址字段。另外，在路由表中，0.0.0.0/0用于表示默认路由。
有限广播地址：255.255.255.255/32。当主机或路由器的某接口，需要向其所在网络中的所有设备发送数据报时，会用广播地址作为IP数据报的目的IP地址。但需要注意，使用有限广播地址的广播数据，只限于发送数据报的主机所在的子网范围内。
回送地址：127.0.0.0/8。如果IP数据报的目的地址（比如常见的127.0.0.1）位于这个地址块中，那么该数据报将不会被发送到源主机之外。

典型的特殊地址如下表所示：

NetID	HostID	作为源地址	作为目的地址	用途
全0	全0	可以	不可以	在本网范围内表示本机；在路由表中表示默认路由
全0	特定值	可以	不可以	本网内某个特定主机
全1	全1	不可以	可以	本网广播地址（路由器不转发）
特定值	全0	不可以	不可以	网络地址，表示一个网络
特定值	全1	不可以	可以	直接广播地址，对特定网络中的所有主机进行广播
127	非全0或非全1的任何数	可以	可以	用于本地软件环回测试，称为环回地址

除此之外，还存在一部分保留地址，用于内部网络，称为私有地址。这部分地址可以在内网使用，但不能在公共互联网上使用。以这部分地址作为目的地址的IP数据报出现在公共互联网上时，公共互联网会丢弃这些IP数据报，不进行转发。私有地址空间见下表：

私有地址类别	范围
A类	10.0.0.0 ~ 10.255.255.255 （或10.0.0.0/8）
B类	172.16.0.0 ~ 172.31.255.255 （或172.16.0.0/12）
C类	192.168.0.0 ~ 192.168.255.255 （或192.168.0.0/16）

在分类寻址方案中，A类地址网络数量少，但每个A类网络规模很大，如果将一个A类地址网络分配给一个组织使用，很容易导致IP地址浪费；C类地址网络数量大，但每个C 类地址网络规模却很小，往往一个组织分配一个C类地址又不满足需求。

事实上，由于IPv4 地址早期分配的粗放性，以及分类地址的固有不足，在早期 IP地址的分配和使用过程中存在很大的浪费，目前 IPv4 地址已经分配殆尽了。为了改善IPv4地址空间的利用率，缓解或应对IPv4地址空间不足问题，提出了一系列相关解决方案。

5.2.3、无类地址

为了彻底解决地址空间不足问题，可以增加IP地址的长度，这就是之后要讨论的 IPv6 的解决方案。但是，在Internet全面 IPv6化之前，32位的 IPv4地址还将长时间被使用，因此需要一些解决方案来提高IPv4地址的利用率，缓解或应对 IPv4地址空间不足问题。针对这一问题，首先被提出的就是无类地址。

在无类寻址方案中，不存在分类寻址中的网络类别，网络前缀不再被设计为定长的8位、16位、24位，而变成可以是0~32 位的任意值。在无类寻址中，网络地址形式为a.b.c.d/x，其中，a.b.c.d为点分十进制形式 IP地址，x为网络前缀长度，显然 $x \in [0,32]$ ，这种地址形式称为 CIDR (Classless Inter-Domain Routing，无类域间路由）地址。例如，前面提到过的192.168.1.0/24。

5.2.4、子网划分

为了缓解地址空间不足，提高IP 地址空间利用率，另外两种策略分别是子网化与超网化。

子网化就是指将一个较大的子网划分为多个较小子网的过程。较大子网具有较短的网络前缀，较小子网具有稍长的前缀。将较大子网划分为较小子网后，可以将较小子网分别分配给不同组织或网络，从而避免IP地址的浪费。例如，可以将一个A类地址网络划分为1024个子网，每个子网 IP地址总数为16 384，然后将一个子网分配给一个组织，这样在一定程度上提高了地址空间的利用率。当然，前提是某个组织（比如 ISP）愿意将其IP地址空间分给更多的组织来使用。
超网化是指将具有较长前缀的相对较小的子网合并为一个具有稍短缀的相对较大的子网，可见，超网化可以看作是子网化的逆过程。超网化在地址分配过程中的意义，在于可以将多个小的有类地址网络，合并为一个大的超网分配给某个组织。例如，4个地址连续的C类地址网络，可以合并为一个地址前缀为22的超网，该超网的IP地址总数为1024。

有了子网化与超网化概念后，如果单单给出一个子网的子网地址，是无法准确描述一个子网的规模的。例如，如果给出一个子网地址 213.111.0.0，这时是无法准确判断该子网的规模的。因此，在准确描述一个子网时，需要同时给出该子网的网络前缀或者该子网的子网掩码。例如，子网213.111.0.0/24，就是一个C 类地址网络，子网 213.111.0.0/23，就是一个超网，包括213.111.0.0/24 和213.111.1.0/24两个C类地址网络。

子网掩码同样可以用来定义一个子网的网络前缀长度，等价于 CIDR 地址中的前缀长度，但形式不同，子网掩码与 IP地址相同，也是一个32位数，其取值规则是：对应网络前缀，全部为1，其余位（主机部分）全部为0。常见的子网掩码也写成点分十进制形式。例如，子网213.111.0.0/24 的子网掩码是255.255.255.0，子网 213.111.0.0/23 的子网掩码是255.255.254.0。也就是说，子网"213.111.0.0/24"，等价于“子网地址为213.111.0.0，子网掩码是255.255.255.0"。可见，只有给出子网地址和子网掩码或网络前缀，才能准确描述一个子网的规模。这也是为什么计算机在 IP地址配置时，除了设置 IP地址外，还要设置子网掩码的原因。

当己知子网中的某主机的 IP地址和子网掩码，就可以计算出一个子网的网络地址、广播地址、IP地址总数和可分配 IP 地址数量等。例如，假设某子网内的一个地址为192.168.1.45，子网掩码为255.255.255.128，那么通过将该地址与子网掩码做按位与运算，就可以得到该子网的子网地址为192.168.1.0，或者说该子网为192.168.1.0/25。如果利用子网掩码的反码与该地址做按位或运算，就可以得到该子网的直接广播地址，即192.168.1.127。

例，假设某子网中的一个主机的IP地址是 203.123.1.135，子网掩码是255.255.255.192，那么该子网的子网地址是什么？直接广播地址是什么？该子网IP地址总数是多少？该子网的可分配IP地址数是多少？可分配IP地址范围是多少？

将203.123.1.135与255.255.255.192 按位与运算，得到：203.123.1.128，为该子网的子网地址，即该子网为203.123.1.128/26；该子网的直接广播地址是203.123.1.191；该子网IP地址总数是64；该子网的可分配 IP 地址数是64-2=62；可分配IP地址范围是：203.123.1.129 ~ 203.123.1.190。

上例中的可分配IP地址是指可以分配给主机或路由器接口使用的IP地址，因此要从子网的IP总数中减去子网地址和广播地址，这两个地址是不能分配给主机或路器接口的。

负责全球 Internet的IP 地址分配的机构，是因特网名称和编号分配组织（Internet Corporation for Assigned Names and Numbers, ICANN）。ICANN并不会为每一个网络中的每个用户分配地址，而是给一个因特网服务提供商（Internet Service Provider, ISP）分配一块较大的连续地址空间（即一个子网），再由 ISP 将其分配到的地址空间划分为相对更小的子网，再进一步分配给 ISP 的客户（比如某企业）。网络地址块的分配通常满足两个条件：地址块中的地址总数量是2的整数次幂；地址块中的地址是连续的。

下面给出子网划分的一般性方法。对于一个给定的IP网络a.b.c.d/x (IPv4 网络），如果需要将其划分为多个子网，可以利用其主机域（HostID）的（32-x）位中的部分位加以区分。如果利用r位划分子网（ $r \in [1, 30-x]$ ），则可以将原网络a.b.c.d/x划分为 $2^r$ 个等长的子网，每个子网 IP 地址空间（总数）为 $2^{32-x-r}$ ，其中每个子网中除了a.b.c.d/x的网络前缀的x位与区分子网的r位外，剩余位全为0和全为1的地址，分别作为对应子网的网络地址和子网直接广播地址，因此，每个子网可分配IP地址空间为 $(2^{32-x-r}-2)$ 。可见，r越大，可区分的子网数越多，但每个子网可分配 IP地址空间越小，即每个子网可分配给主机或路由器接口的 IP地址数越少。因此，究竟应该选择多大的r划分子网，要根据实际网络的子网数以及子网规模来定。另外，具体从（32-x）位中选择哪几位区分子网，理论上来讲，任选r位均可以，但是如果这r位随便选择，就可能导致划分出来的子网地址不连续，给网络管理、地址分配等带来极大的不便。因此，在实际划分子网时，会从（32-x）位中的高位连续选择r位。上述子网划分过程通常称为等长子网划分，划分出来的子网大小相同，即各子网的网络前缀相同，或者说各子网的子网掩码相同。如果需要将一个IP 网络划分为多个不同规模的子网，就需要进行不等长子网划分。基本方法就是先进行等长划分，然后再将划分出来的子网的其中一个或多个再进一步进行等长划分，从而可以得到多个不同规模的子网。

准确描述一个子网可以通过两种形式，一种是 CIDR形式，子网地址形如a’.b’.c’.d’/(x+r)，另一种形式就是子网地址（每个子网的(x+r)位前缀是特定值，剩分(32-x-r)位全位0的地址）加子网掩码。子网掩码的取值是对应子网的(x+r)位高位全取1，剩余（32-x-r）位全为0的地址。

例，请将 IP网络 12.34.56.0/24 划分为3个子网，要求：第一个子网的可分配 IP 地址不少于50个，第二个子网的可分配IP地址不少于60个，第三个子网的可分配IP地不少于120个。

采用不等长子网划分。网络 12.34.56.0/24 的可分配 IP地址数是 254，根据3个子网的可分配IP地址数的需求，首先将 12.34.56.0/24划分为2个子网，分别是12.34.56.0/25 和12.34.56.128/25。将12.34.56.128/25 作为第三个子网，则该子网的子网地址是12.34.56.128，子网掩码是255.255.255.128，广播地址是12.34.56.255，可分配 IP 地址数为126，可分IP 地址范围是：12.34.56.129/25 ~ 12.34.56.254/25，显然满足题目要求。

接下来，进一步将子网 12.34.56.0/25 再划分为2个子网，分别是 12.34.56.0/26 和12.34.56.64/26，并分别作为题目要求的第一个子网和第二个子网。于是，第—个子网的子网地址是 12.34.56.0，子网掩码是255.255.255.192，广播地址是12.34.56.63，可分配IP地址数位62，可分配 IP 地址范围是：12.34.56.1/26~12.34.56.62/26；第二个子网的子网地址是12.34.56.64，子网掩码是255.255.255.192，广播地址是12.34.56.127，可分配 IP地址数为62，可分配IP地址范围是：12.34.56.65/26 ~12.34.56.126/26，也满足题目要求。

5.2.5、路由聚合

通常子网划分后，会利用路由器等第三层网络互连设备互连这些子网，通过路由器实现子网间的IP数据报转发。路由器将路由信息存到转发表（即路由表）中，当收到IP数据报时，利用 IP数据报的目的IP地址匹配转发表的表项，并将IP数据报沿最优的匹配成功表项描述的路径进行转发。转发表包含的主要信息有网络地址、子网掩码、下一跳地址以及路由器接口，其中，网络地址和子网掩码可以分开给出，也可以合并以 CIDR 形式给出。

路由器中的转发模块在一个IP数据报到达后逐行查找转发表。将IP数据报的目的IP地址与路由表的每个路由表项的子网掩码按位与运算，再将结果与该路由表的网络地址进行匹配，如果相同，则匹配成功。如果整个路由表全部查找完毕，只匹配成功一条路由表项（默认路由除外），则选择该路由表项描述的路径转发IP数据报，即通过该路由表项中的路由器接口转发IP数据报；如果匹配成功的路由表项不止一条，则选择匹配成功的网络前缀最长的那条路由项，即最长前缀匹配优先原则；如果没有一条路由表项匹配成功，则通过默认路由表项描述的路径转发IP数据报。一个简单的例子如下图所示。

下图所示的路由器R1的路由表中，在到达子网1～4的路由表项中，下一跳地址为"-“，即“直接到达”。表示这些子网与路由器R1 直接相连，R1可以将到达这些子网的IP 数据报直接发送给目的主机，而无须再经由其他路由器转发。R1路由表的最后一项"0.0.0.0/0"，为默认路由，即网络地址为0.0.0.0，子网掩码为0.0.0.0 的路由表项就是默认路由。IP数据报的目的IP地址与路由表中除默认路由外，都匹配不成功的时候，就沿默认路由进行转发。在上图的例子中，默认路由0.0.0.0/0相当于到达Internet的路由。

接下来，仍然以上图所示的网络为例，进一步分析在路由器R2的路由表中，关于到达子网1~4的路由项是怎样的呢？很容易想到的是R2的路由表会像R1路由表一样，分别描述到达子网1～4的路由，如下图中聚合前的R2 路由表。虽然这样的路由表，在逻辑上并没有错误，但是表项较多，查找效率低。如果仔细观察这4条路由会发现，去往这4个子网的路由具有相同的下一跳地址和接口，而且这4个子网合在一起又刚好是一个大的子网15.65.154.0/24。于是，可以通过路由聚合将R2中关于4个子网的路由聚合为1条路由，得到聚合后的路由表，如下图所示。聚合后的路由表中的路由表项大幅缩减，可以大大提高路由表的查找效率。事实上，Internet 骨干网络上的路由器，利用路由聚合技术缩减了路由表的大小，有效提高路由表查找效率。

在上图中的路由聚合前，R2路由表中，到达子网1 ~ 4的4条路由刚好具有相同的下一跳地址和接口，聚合后的子网也刚好完整覆盖4个子网。如果 4个子网不都与 R1 相接，而是如下图所示那样，子网4与R2直接连接，那么这种情况下R2的路由表还能使用路由聚合技术吗？答案是肯定的。聚合后R2的路由表如下图所示。在聚合后的 R2路由表中，第一行网络地址描述的子网15.65.154.0/24，包含了子网 15.65.154.192/26。也就是说，当一个目的 IP地址在子网15.65.154.192/26内的IP数据报到达 R2时，R2 查找路由表，会匹配成功两条路由项（第一行和第二行），但是按着最长前缀匹配优先原则，R2 会选择第二行路由。因此，在这种情况不，并不会产生路由错误。

另外，如果在路由表中描述到达某个特定主机（该主机IP地址为 $a^*.b^*.c^*.d^*$ )的路由，则利用 $a^*.b^*.c^*.d^*/32$ 或（目的网络： $a^*.b^*.c^*.d^*$ ，子网掩码：255.255.255.255)来表示该特定主机。

综上所述，路由聚合是为了提高路由效率，减少路由表项数，尽可能将能够聚合在一起的子网聚合成一个大的子网。路由聚合可以视为是子网划分的逆过程，通常 $2^n$ 个前缀长度为x的子网，如果这些子网具有(x-n)位长度的共同网络前缀，则这些子网可以聚合为一个网络前缀长度为(x-n)的大子网。在路由表中，满足这个基本条件的子网是否要（或能）聚合为一个大子网，还要看它们是否有相同的路由“路径”，即“下一跳地址”和“接口”是否相同，相同才能聚合，否则不能聚合。

在路由聚合过程中，可能存在将一个聚合在一起的大子网中的某个（或某几个）小子网单独分出去的情况（例如上图所示情形），这样就会导致大子网不包含这些小子网的现象。为了充分利用路由聚合带来的高效路由，需要避免出现路由错误，可以在同一个路由器中并列关于到达大子网和小子网的路由。显然，小子网的网络前缀比大子网的网络前缀长。在这种情况下，在使用 CIDR 进行路由查找时，有可能会得到不止一个的匹配结果，这时根据最长前缀匹配优先原则，即可避免路由错误。

5.3、动态主机配置协议

5.4、网络地址转换

5.5、ICMP

5.6、IPv6

六、路由算法与路由协议

6.1、基本概念

6.1.1、理想的路由选择算法

路由选择协议的核心是路由选择算法，即用何种算法来获得路由表中的各项。一个理想的路由选择算法应具有如下一些特点。

算法必须是正确的和完整的。这里，“正确”的含义是，沿着各路由表所指引的路由，分组最终一定能够到达的目的网络和目的主机。
算法在计算上应简单。路由选择的计算不应使网络增加太多的额外开销。
算法应能适应通信量和网络拓扑的变化，也就是说，要有自适应性。当网络中的通信量发生变化时，算法能自适应地改变路由以均衡各链路的负载。当某个或某些结点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时地改变路由。
算法应具有稳定性。在网络通信量和网络拓扑相对稳定的情况下，路由选择算法应收敛于一个可以接受的解，而不应使得出的路由不停地变化。
算法应是公平的。路由选择算法应对所有用户（除对少数优先级高的用户）都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，却不考虑其他的广大用户，这就明显地不符合公平性的要求。
算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组平均时延最小而网络的吞吐量最大。虽然我们希望得到“最佳”的算法，但这并不总是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均时延或最大吞吐量更加重要。因此，所谓“最佳”只是在特定要求下得出的较为合理的选择。

一个实际的路由选择算法，应尽可能接近于理想的算法。在不同的应用条件下，对以上提出的6个方面也可有不同的侧重。

为了研究路由选择算法，经常会利用图论将计算机网络抽象为一个由若干结点和边组成的图（Graph）。如下图所示：结点表示路由器，而边表示路由器之间的链路，边的权值可用来表示费用、距离、时延、带宽等链路代价。路由选择算法的任务就是计算从某个结点到所有其他结点的最短路径。

应当指出，路由选择是个非常复杂的问题，因为它需要网络中的所有结点协调工作。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络中出了某些故障。此外，当网络发生拥塞时，就特别需要能缓解这种拥塞的路由选择策略，但恰在这种条件下，很难从网络中的各结点获得所需的路由选择信息。

6.1.2、路由选择算法的分类

随着计算机网络的发展，提出了很多路由选择算法。根据不同的分类标准，路由选择算法可以分为不同的类别。

根据路由算法是否基于网络全局信息计算路由，可以将路由选择算法分为分布式路由选择算法和全局式路由选择算法。

分布式路由选择算法。在分布式路由选择算法中，结点只需获知与其相连的链路的“费用”信息，以及邻居结点通告的到达其他结点的最短距离（估计）信息，经过不断的迭代计算，最终获知经由哪个邻居可以具有到达目的结点的最短距离。最具有代表性的分布式路由选择算法是距离向量路由选择算法，简称DV算法。
全局式路由选择算法。在全局式路由选择算法中，结点需要根据网络的完整信息（即完整的网络拓扑结构），来计算最短路径。全局式路由选择算法并不是说路由计算只在某个路由器上进行，而是指每个路由器在计算路由时，都要获取完整的网络拓扑信息。最具有代表性的全局式路由选择算法是链路状态路由选择算法，简称LS算法。

另一种分类标准是依据算法是静态的还是动态的来分类。

静态路由选择算法，通常是指由人工进行网络配置。当网络状况出现变化时，如果不进行人工干预，那么经过静态路由选择算法所选择的路由，是无法与当前网络中的状态相匹配的。
动态路由选择算法，能够在网络状态发生变化时，自动计算最佳路由，从而反映出网络变化，因此具有更好的自适应性。链路状态路由选择算法和距离向量路由选择算法都是动态路由选算法。

还有一种路由选择算法的分类标准是根据路由选择算法是否为负载敏感的来进行分类。

负载敏感的路由选择算法，能够较好地在网络发生拥塞时迅速地对路由做出调整；
负载迟钝的路由选择算法则无法对这种变化做出快速响应。

6.1.3、层次化路由选择

互联网采用的路由选择协议主要是自适应的（即动态的）层次化路由。互联网采用层次化路由选择主要有以下两个原因。

互联网的规模非常大，现在就已经有几百万个路由器互连在一起。如果让所有的路由器知道所有的网络应怎样到达，则路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使互联网的通信链路饱和。
许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到互联网上。

整个互联网被划分为许多较小的自治系统（Autonomous System，AS）。AS是在单一技术管理下的一组路由器，这些路由器使用一种AS内部的路由选择协议和共同的度量，以确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议，以确定分组在AS之间的路由。

在目前的互联网中，一个大的ISP就是一个自治系统。互联网把路由选择协议划分为两大类。

内部网关协议（Interior Gateway Protocol，IGP）：在一个自治系统内部使用的路由选择协议，与互联网中的其他自治系统选用什么路由选择协议无关。目前这类路由选择协议很多，如RIP和OSPF等。
外部网关协议（External Gateway Protocol，EGP）：若源主机和目的主机处在不同的自治系统中（这两个自治系统可能使用不同的内部网关协议），就需要在自治系统之间进行路由选择，使用一种协议将路由信息从一个自治系统传递到另一个自治系统中，这样的协议就是外部网关协议。目前互联网使用的外部网关协议就是BGP的版本4（BGP-4）。

自治系统之间的路由选择也叫作域间路由选择（Interdomain Routing），而自治系统内部的路由选择叫作域内路由选择（Intradomain Routing）。如下图，是两个自治系统互连在一起的示意图。每个自治系统自己决定在本自治系统内部运行哪一个内部路由选择协议（例如，可以是RIP，也可以是OSPF）。但每个自治系统都有一个或多个路由器（图中的路由器R1和R2），除了运行本系统的内部路由选择协议外，还要运行自治系统间的路由选择协议（BGP-4）。

综上所述，层次化路由选择将规模很大的互联网路由划分为两层：自治系统内路由选择和自治系统间路由选择。在层次化路由选择中，路由器的转发表由自治系统内的路由选择协议和自治系统间的路由选择协议共同设置。

在一个自治系统范围内，路由器基于所在自治系统采用的路由选择算法，计算到达自治系统内的目的网络的路由，并存储到转发表中。
每个自治系统的网关路由器，运行自治系统间的路由选择协议，负责与其他自治系统交换跨越自治系统的路由可达性信息，并基于自治系统间的路由选择协议，将跨自治系统的网络可达性信息，交换给其所在自治系统内的其他路由器，这些路由器进一步将这些路由信息也存储到转发表中。

这样，自治系统内的路由器，收到一个网络层分组时无论该分组去往的目的网络在自治系统内，还是在自治系统外，路由器都可以通过查找转表知道如何转发分组。

6.2、路由信息协议（RIP）

路由信息协议（Routing Information Protocol，RIP）是内部网关协议中最先得到广泛使用的协议之一（RFC 1058）。RIP是一种分布式的、基于距离向量的路由选择协议，是互联网的标准协议，其最大优点是简单。

6.2.1、距离向量路由选择算法

6.2.1.1、简介

在距离向量路由选择算法中，所有结点都没有掌握整个网络的完整信息。每个结点可以测得与所有邻居结点之间的直接链路代价，并将其到达每个目的结点的最短距离（可能是最短距离估计），以距离向量形式（目的，最短距离）交换给所有的邻居结点。每个结点基于其与邻居结点间的直接链路距离，以及邻居交换过来的距离向量，计算并更新其到达每个目的结点的最短距离，然后将新的距离向量再通告给其所有邻居，直到距离向量不再改变。

每个结点在刚开始工作时，只知道到相邻结点的距离。接着，每个结点也只和数目有限的相邻结点交换并更新路由信息。然而，经过若干次更新后，所有的结点最终都会知道到达任何一个结点的最短距离，即算法得到收敛（Convergence）。这里“收敛”就是通过多次迭代，所有结点都得到正确的路由选择信息的过程。

6.2.1.2、算法思想

距离向量路由选择算法的基础是 Bellman-Ford方程（简称B-F方程）。令 $d_x(y)$ 表示结点x到结点y 的路径最小费用（即广义最短距离），根据 Bellman-Ford 方程，有以下公式成立：

d_x(y)=min\{c(x,v)+d_v(y)\}

式中， c (x, v)为结点x与邻居结点v之间的直接链路距离（费用）， $d_v(y)$ 为邻居结点v通告给结点x的其到达结点y的最短距离。显然，从源结点x出发到达目的结点y的最短距离由两部分组成：从结点x到达相邻结点v的距离，以及结点v到目的结点y的最短距离。这是因为分组想要从结点x到达结点y，那么该分组就一定会先被转发给结点x的某个邻居（除非结点x与结点y是同一台设备），再从该个邻居出发经具有最小费用的路径到达结点y。

距离向量路由选择算法的基本思想是：

网络中的每个结点 x，估计从自己到网络中所有结点y的最短距离（注意这里只是估计），记为 $D_x(y)$ ，称为结点x的距离向量，即该向量维护了从结点x出发到网络中所有结点的最短距离（即最小费用）的估计；
每个结点向其邻居结点发送一份它的距离向量拷贝；
当结点收到来自邻居的一份距离向量（或者是观察到相连链路的费用发生变化），会根据 Bellman-Ford 方程对自己的距离向量进行计算更新；
如果结点的距离向量得到了更新，那么该结点会将更新后的距离向量发送给它的所有邻居结点。

实践表明，距离向量路由选择算法，可以使 $D_x(y)$ 最终收敛到真实的最短距离 $d_v(y)$ 。下图展示了一个基于距离向量路由选择算法，计算路由的例子。

初始状态时，结点x、y、z仅依据直接链路估计到达邻居的最短距离，得到初始距离向量(DV)。此时，邻居结点间还没有彼此交换DV。

邻居结点间彼此交换了距离向量后，结点x、y、z分别基于B-F方程计算到达每个结点的最短距离，结果是结点x的距离向量由（0，2，7）更新为（0，2，5），结点z的距离向量由（7，3，0）更新为（5，3，0），而结点y的距离向量未发生改变，因此结点x和结点z需要将新距离向量通告给各自的所有邻居结点，而结点y无须通告其距离向量。

接下来，结点 x、y、z都分别收到了邻居结点通告的新距离向量，因此需要再次基于B-F方程计算到达每个结点的最短距离，计算结果是各结点的距离向量均未发生改变，各结点均收敛。

至此，每个结点都获得了到达网络中其他结点的最短距离，并且知道具有最短距离的路径经由哪个邻居，于是基于这些信息各结点便可以更新设置各自的转发表。例如，结点x可以在其转发表中，设置去往结点z的路由的下一跳是结点y。

6.2.1.3、无穷计数问题

接下来，以下图为例，讨论距离向量路由选择算法的无穷计数问题。

在上图中，链路xy的费用变化之前， $D_y(x)=4$ ， $D_z(x)=5$ 。当链路xy的费用变为50时，结点y更新其到结点x的最低费用估计为 $D_y(x)=6$ ，因为在此之前结点y收到的结点z通告的距离向量中，结点z声明其到达结点x的最短距离是5，因此，基于B-F方程计算 $D_y(x)=min \{50, 1+5\}=6$ 。

由于结点y的距离向量发生了变化（结点y到结点x的最短距离估计由4变为6)，所以结点y将新的距离向量发送给邻居结点（包括结点z)。结点z收到结点y的新距离向量后，也会基于B-F方程计算 $D_z(x)=min \{40, 1+6\}=7$ 。进一步，结点z再将新的距离向量通告给它的邻居（包括结点y)，这样循环下去，直至循环34次后，结点z才会“意识”到选择直接链路z的费用更低。

显然，如果上图中的链路xz费用很大，链路xy费用也变得很大，那么在上述情景下，结点y、z在很长时间内都在使用虚假的到达结点x的“最佳”路由，这种现称为距离向量路由选择算法的无穷计数问题。

解决无穷计数问题的方案之一是毒性逆转技术。毒性逆转的基本思想是，如果一个结点x获得到达某目的结点y的最短距离估计 $D_x(y)$ ，利用了结点x的邻居结点v的距离向量值，那么结点x在向结点v交换距离向量时，声明 $D_x(y)=\infty$ ，从而“善意欺骗”结点v将来不要再反过来依赖自己。

仍以上图为例，链路xy费用在增长为50之前，结点z到达结点x的最短距离是通过结点y得到的，因此结点z在通告给结点y的距离向量中，会令 $D_z(x)=\infty$ 。这样，当链路xy费用由4变为50时，结点y基于B-F方程计算 $D_y(x)=min \{50, 1+\infty\}=50$ ，结点y的距离向量发生了变化，所以结点 y 将新的距离向量发送给结点z。

于是，结点z基于B-F方程计算 $D_z(x)=min \{40, 1+50\}=40$ ，结点z接下来将 $D_z(x)=40$ 交换给结点y（因为这个最短距离估计不是经过结点y得到的），结点y 则基于B-F 方程计算 $D_y(x)=min \{50, 1+40\}=41$ ，结点y更新其距离向量，并向结点z通告 $D_y(x)=\infty$ （因为结点y到达结点x的最短距离估计是通过结点z获得的）。至此，结点y、z均已收敛，并获得最佳路由，无穷计数问题得以避免。

除了毒性逆转技术之外，还可以通过定义最大有效费用度量值，来限制无穷计数问题的影响。例如，路由信息协议定义路径最大有效距离为15跳，16 即表示无穷大。这样，在基于距离向量路由选择算法(RIP)计算路由时，即便发生了无穷计数现象也会在有限时间内收敛。

6.2.2、RIP的基本原理

RIP将到某个网络的路径“距离”定义为该路径所经过的路由器数加1，即路由器到直接连接的网络的距离为1。

RIP的“距离”也称为“跳数”（Hop Count），因为每经过一个路由器，跳数就加1。RIP认为好的路由就是通过的路由器数目少，即“距离短”。RIP允许一条路径最多包含15个路由器。因此“距离”等于16即相当于不可达。可见RIP只适用于小型互联网。

RIP是一种迭代的分布式路由选择算法，每一个路由器都要不断地和其他路由器交换路由信息，其主要特点是：每个路由器仅向相邻路由器通告路由信息，通告的是每个路由器自己的路由表信息，并且要周期性（或当路由表发生变化时）通告。

RIP的基本工作过程如下。

路由器每隔大约30s周期性地向所有相邻路由器发送路由更新报文（包含到所有已知网络的距离和下一跳路由器），并接收所有相邻路由器发送过来的路由更新报文。
对地址为X的相邻路由器发来的路由更新报文，先修改此报文中的所有条目：把“下一跳”字段中的地址都改为X ，并把所有的“距离”字段的值加1。每一个条目都有三个关键数据，即目的网络N 、距离d 、下一跳路由器X 。
对修改后的路由更新报文中的每一个条目进行以下处理。
- 若路由表中没有目的网络N ，则把该条目添加到路由表中；否则，查看路由表中目的网络为N的表项的下一跳路由器地址。
- 若下一跳路由器地址是X ，则用收到的条目替换路由表中的条目；否则（即这个条目是到目的网络N ，但下一跳路由器不是X ）查看收到的条目的距离d 。
- 若收到的条目中的距离d小于路由表中的距离，则进行更新；否则什么也不做。
若一段时间（默认是180s）没有收到某条路由条目更新报文，则把该路由项目记为无效，即把距离置为16（距离为16表示不可达）；若再过一段时间，如120s，还没有收到该路由条目更新报文，则将该路由项目从路由表中删除。
当路由表发生变化时，不必等到周期更新时间，立即向所有相邻路由器发送路由更新报文（即触发更新）。

RIP让一个自治系统中的所有路由器都和自己的相邻路由器定期交换路由信息。路由器在刚刚开始工作时，只知道到直接连接的网络的距离。通过不断与相邻路由器交换路由信息并更新路由表，最终每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。

下图所示的简单例子说明了RIP的收敛过程。

各路由器开始仅知道到直接连接的网络的距离。接着，各路由器都向其相邻路由器广播RIP报文，即广播路由表中的信息。假定路由器R2先收到了路由器R1和R3的路由信息，然后就更新自己的路由表。更新后的路由表再发送给路由器R1和R3。路由器R1和R3分别再进行更新。这个例子非常简单，所以三个路由器中的路由表很快就全部更新完毕。实际的更新过程可能和上图有所不同，因为RIP报文的交互具有随机性，但最终都能收敛到同样的结果。

6.2.3、坏消息传播得慢

RIP有一个特点，就是当一个路由器发现了更短的路由时，这种更新信息传播得很快，但是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。

我们可以用一个简单例子来说明。如下图所示，三个网络通过两个路由器互连起来：路由器R1连接网络1和网络2，而路由器R2连接网络2和网络3。假定各路由器都已建立了各自的路由表。

现在假定路由器R1到网络1的链路出了故障。这时，网络2和网络3都无法通过R1 到达网络1。于是路由器R1 就把到网络1的距离改为16（表示网络1不可达），并把这个更新信息发送给R2 。但是，R2 收到这个更新信息之前可能已经将自己的路由表发送给了R1 ，其中有一个项目是“我可以经过R1到达网络1，距离是2”。得出这条项目的根据是R1到网络1的距离是1，而R2到R1的距离是1。

R1 收到R2 的更新报文后，误以为可经过R2 到达网络1，于是也错误地以为“我可以经过R2 到达网络1，距离是3”，然后把这个更新信息发送给R2 。

同理，R2 随后发布自己的路由更新信息：“我可以经过R1 到达网络1，距离是4。”这样不断更新下去，直到R1 和R2 到网络1的距离都增大到16时（如果RIP不定义16为无穷大，则该过程会一直进行下去），R1 和R2 才知道网络1是不可达的。RIP的这一特点叫作：好消息传播得快，而坏消息传播得慢。网络故障信息的传播往往需要较长的时间（如数分钟）。这是RIP的主要缺点之一。

该问题又称为循环路由问题或无穷计数问题，这是距离向量算法的一个固有问题。我们可以采取多种措施降低出现该问题的概率或减小该问题带来的危害。例如，限制最大距离为15（16表示不可达）；当路由表发生变化时就立即发送更新报文（即“触发更新”），而不仅是周期性发送；让路由器记录收到某特定路由信息的接口，不让同一路由信息再通过此接口向反方向传送（“水平分割”方法）等。但这些措施都无法彻底解决该问题，因为在距离向量算法中，每个路由器都缺少到目的网络的整个路径的完整信息，无法判断所选的路由是否出现了环路。

6.2.4、小结

RIP最大的优点就是实现简单，路由器开销较小。但RIP的缺点也较多：

首先，RIP限制了网络的规模，它能使用的最大距离为15（16表示不可达）；
其次，路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也会增加；
最后，“坏消息传播得慢”，使更新过程的收敛时间过长。因此，RIP只适用于规模较小的网络。

RIP的第二个版本RIP2（RFC 2453）支持可变长子网掩码和CIDR。此外，RIP2还提供简单的鉴别过程并使用多播
而不是广播向所有相邻路由器发送路由更新报文。

RIP和RIP2都使用运输层的UDP进行传送（使用的端口是520）。

6.3、开放最短路径优先（OSPF）

开放最短路径优先（Open Shortest Path First，OSPF）是为了克服RIP的缺点在1989年被开发出来的。

OSPF的基本原理很简单，但其具体实现却非常复杂。“开放”表明OSPF不是受某一家厂商控制，而是公开发的。“最短路径优先”是指使用了迪杰斯特拉（Dijkstra）提出的最短路径算法。OSPF的第二个版本OSPF2已成为互联网标准协议（RFC 2328）。

OSPF最主要的特征就是使用链路状态（Link State，LS）路由选择算法（简称链路状态算法），而不是像RIP那样的距离向量路由选择算法。

6.3.1、链路状态路由选择算法

6.3.1.1、简介

链路状态路由选择算法是一种全局式路由选择算法，每个路由器在计算路由时需构建出整个网络的拓扑图。为了构建整个网络的拓扑图，每个路由器周期性检测、收集与其直接相连链路的费用，以及与其直接相连的路由器ID等信息，构造链路状态分组并向全网广播扩散。

采用链路状态路由选择算法，网络中每个路由器，都会周期性地收到其他路由器广播的链路状态分组，并将链路状态信息存储到每个路由器的链路状态数据库中，当数据库中收集到足够的链路状态信息后，路由器就可以基于数据库中的链路状态信息，构建出网络拓扑图。

由于路由表是根据全网拓扑生成的，链路状态算法没有距离向量算法“坏消息传播得慢”的问题。

6.3.1.2、算法思想

链路状态算法既可以分布式实现，即每个路由器各自根据收集的全网拓扑生成自己的路由表，也可以采用集中方式，由专门的网络控制器收集全网拓扑生成路由表，再下发给各路由器。链路状态路由选择算法的要点如下：

每个路由器都能够感知它的本地“链路状态”，即本路由器都和哪些网络相连，与哪些路由器相邻，以及它们之间链路的“度量”（Metric）。这个“度量”作为链路的权值，可用来表示费用、距离、时延、带宽等链路代价。这些都由网络管理人员来决定，因此较为灵活。
当本地链路状态发生变化时，路由器用洪泛法向所有路由器广播该链路状态变化信息。洪泛法（Flooding）是指路由器通过输出端口向所有相邻的路由器发送信息，而每一个相邻路由器又再将此信息发往其所有的相邻路由器（但不再发送给刚刚发来信息的那个路由器）。这样，最终整个区域中所有的路由器都得到了这个信息的一个副本。
每个路由器都可以收到所有其他路由器广播的链路状态信息并建立全网的拓扑结构图（在OSPF中被称为链路状态数据库）。因此，每一个路由器都知道全网共有多少个网络和路由器，以及哪些路由器是相连的、链路的度量是多少，等等。然后使用Dijkstra算法计算到所有目的网络的最短路径（最低代价路径），并以此生成自己的路由表。

用Dijkstra算法求最短路径，需要记录以下信息：

D(v)：到本次迭代为止，源结点到目的结点v的当前路径距离。初始化时，如果结点v和源结点直接相连，那么D(v)就是其链路上的权值，否则就是 $\infty$ 。
P(v)：到本次迭代为止，在源结点到目的结点v的当前路径上，结点v的前序结点。
c(x, y)：结点x与结点y之间直接链路的费用，如果x和y之间没有直接链路相连，则 $c(x,y)=\infty$ 。
S：结点的集合，用于存储从源结点到该结点的最短路径已求出的结点集合，初始值只有源结点本身。

下图展示了结点x基于Dijkstra算法求最短路径的过程。

算法运行结束后，结点x便得到了到达网络中任意目的结点的最短路径，接下来结点x就可以以此为根据，构建转发表，如下表所示。

目的	链路
y	(x, y)
u	(x, v)
v	(x, v)
w	(x, v)

6.3.2、OSPF的基本原理

OSPF采用的是分布式链路状态算法，每个路由器各自收集全网拓扑并计算路由表。其基本要点如下：

在OSPF中，所有的路由器都需要维护一个链路状态数据库（Link-State Database），这个数据库实际上就是全网的拓扑结构图。这个拓扑结构图在全网范围内是一致的（这称为链路状态数据库的同步）。
一个路由器刚开始工作时，可以从相邻路由器批量快速获得初始的链路状态数据库，然后在网络运行的过程中，只要某个路由器的链路状态发生变化，它就用洪泛法向全网广播链路状态变化，因此OSPF的链路状态数据库能较快更新，OSPF的更新过程收敛得快是其重要优点。
为了保证协议的可靠性，除了链路状态发生变化时，OSPF路由器也会周期性地向自治系统中所有路由器洪泛链路状态信息，但周期要比RIP长得多（至少30min），更长的周期可确保洪泛不会在网络上产生太大的通信量。

OSPF具有许多优点，主要包括以下几个方面。

安全。所有 OSPF报文（如链路状态分组）都是经过认证的，这样可以预防恶意入侵者将不正确的路由信息注入到路由器的转发表中。
支持多条相同费用路径。OSPF 允许使用多条具有相同费用的路径，这样可以防止在具有多条从源到目的的费用相同的路径时，所有流量都发往其中一条路径。这一特性有利实现网络流量均衡。
支持区别化费用度量。OSPF支持对于同一条链路，根据IP数据报的 TOS不同，设置不同的费用度量，从而可以实现不同类型网络流量的分流。
支持单播路由与多播路由。OSPF综合支持单播路由与多播路由，多播路由只是对OSPF的简单扩展，使用 OSPF的链路状态数据库就可以计算多播路由。
分层路由。OSPF支持在大规模自治系统内进一步进行分层路由。

为了使OSPF能够用于规模很大的网络，OSPF可以把一个自治系统再划分为若干个更小的范围，即区域（Area），进行层次路由。

划分区域的好处就是把利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个自治系统，这就减少了整个网络上的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的完整网络拓扑。

下图所示的就是一个被划分为四个区域的自治系统，每一个区域都有一个32位的区域标识符（用点分十进制表示）。

为了使每一个区域能够和本区域以外的区域进行通信，OSPF使用层次结构的区域划分。在上层的区域叫作主干区域（Backbone Area）。主干区域的标识符规定为0.0.0.0。在主干区域内的路由器叫作主干路由器（Backbone Router），如R3 、R4 、R5 、R6 和R7 。有些主干路由器同时也是区域边界路由器（Area Border Router），如R3 、R4 和R7 。显然每一个区域至少应当有一个区域边界路由器。

主干区域的作用是连通非主干区域，所有非主干区域之间的通信必须经过主干区域。区域边界路由器要对非主干区域内的路由信息进行汇总（Summary），再通告到主干区域中。例如，路由器R3通过收集0.0.0.1区域的链路状态信息计算出到该区域中所有网络的最短路径及路径代价，然后将网络汇总链路状态信息（即到该区域所有网络的路径代价）洪泛到主干区域中，就好像这些网络直接连接在路由器R3上一样。这样，所有主干路由器虽然不知道0.0.0.1区域内部的具体网络拓扑，但能够计算出通过主干区域到该区域网络的最短路径。同样，R3也要把从主干区域获得的到其他区域的网络汇总链路状态信息通告到0.0.0.1区域的所有内部路由器。

主干区域内还要有一个路由器专门和本自治系统外的其他自治系统交换路由信息。这样的路由器叫作自治系统边界路由器（如上图中的R6 ）。

采用层次结构的区域划分使交换的信息种类增多了，同时也使OSPF更加复杂了。另外，即使两个非主干区域直接相连，它们之间的通信也必须经过主干区域。因此，区域划分可能导致协议不能在整个自治系统中获得最优路径。虽然如此，区域划分却能使每一个区域内部交换路由信息的流量大大减小，使OSPF能够用于规模很大的自治系统。

6.3.3、OSPF分组

OSPF分组不使用UDP而是直接用IP数据报传送（其IP数据报首部的协议字段值为89）。OSPF构成的IP数据报很短。这样做可减少路由信息的流量。数据报很短的另一好处是不必将长的数据报分片传送。分片传送的数据报只要丢失一个数据报片，就无法组装成原来的数据报，导致整个数据报必须重传。

OSPF共有以下五种分组类型：

问候（Hello）分组，发现和维持邻站的可达性。
数据库描述（Database Description）分组，向邻站给出自己的链路状态数据库中的所有链路状态摘要信息。
链路状态请求（Link State Request）分组，向对方请求发送某些链路状态项目的详细信息。
链路状态更新（Link State Update）分组，用洪泛法对全网更新链路状态。这种分组是最复杂的，也是OSPF的核心部分。路由器使用这种分组将其链路状态通知邻站。链路状态更新分组共有五种不同的链路状态（RFC 2328），这里从略。
链路状态确认（Link State Acknowledgment）分组，对链路更新分组的确认。

OSPF规定，两个相邻路由器每隔10s要交换一次问候分组。这样就能确知哪些邻站是可达的。对相邻路由器来说，“可达”是最基本的要求，因为只有可达邻站的链路状态信息才存入链路状态数据库（路由表就是根据链路状态数据库计算出来的）。在正常情况下，网络中传送的绝大多数OSPF分组都是问候分组。若有40s没有收到某个相邻路由器发来的问候分组，则可认为该相邻路由器是不可达的，应立即修改链路状态数据库，并重新计算路由表。

其他的四种分组都是用来进行链路状态数据库同步的。所谓同步就是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器叫作“完全邻接的 ”（Fully Adjacent）路由器。不是完全邻接的路由器表明它们虽然在物理上是相邻的，但其链路状态数据库并没有达到一致。

当一个路由器刚开始工作时，它只能通过问候分组得知它有哪些相邻的路由器在工作，以及到相邻路由器的链路代价。如果所有的路由器都把自己的本地链路状态信息对全网广播，那么各路由器只要将这些链路状态信息综合起来就可得出链路状态数据库。但这样做开销太大，因此OSPF采用下面的办法。

OSPF让每一个路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。链路状态摘要信息主要是指出有哪些路由器的链路状态信息（及其序号）已经写入了数据库。与相邻路由器交换数据库描述分组后，路由器就使用链路状态请求分组向对方请求发送自己所缺少的某些链路状态项目的详细信息。通过一系列的这种分组交换，全网同步的链路数据库就建立了。

在网络运行的过程中，只要一个路由器的链路状态发生变化，该路由器就要用洪泛法向全网广播链路状态更新
分组。OSPF使用的是可靠的洪泛法，其要点如下图所示。

设路由器R用洪泛法发出链路状态更新分组。图中用一些小的实心箭头表示该分组。第一次先发给相邻的三个路由器。这三个路由器将收到的分组再进行转发时，要将其上游路由器除外。可靠的洪泛法是在收到更新分组后要发送确认（确认并不洪泛，每个路由器仅向上游邻居发送确认）。图中的空心箭头表示确认分组。

为了确保链路状态数据库与全网的状态保持一致，OSPF还规定每隔一段时间，如30min，要刷新一次数据库中的链路状态。

由于一个路由器的链路状态只涉及与相邻路由器的连通状态，与整个互联网的规模并无直接关系，同时，将自治系统划分为小的区域可有效限制链路状态广播的范围，因此，当互联网规模很大时，OSPF要比RIP好得多。由于OSPF没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于100ms。

若N 个路由器连接在一个以太网上，则每个路由器要向其他(N -1)个路由器发送链路状态信息，因而共有 $(N -1)^2$ 个链路状态要在这个以太网上传送。OSPF对这种多点接入的局域网采用了指定路由器（Designated Router）的方法，使广播的信息量大大减少。指定路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

6.4、边界网关协议（BGP）

RIP和OSPF等IGP可以实现一个自治系统内的路由计算与路由选择。而实现跨自治系统的路由信息交换，则需要 EGP, BGP 就是Internet的标准EGP，目前典型版本为BGP4。每个AS可以通过 BGP实现如下功能。

从相邻AS获取某子网的可达信息。
向本AS内部的所有路由器传播跨AS的某子网可达信息。
基于某子网可达信息和AS路由策略，决定到达该子网的最佳路由。

6.4.1、为什么需要BGP

在不同AS之间的路由选择为什么不能使用前面讨论过的内部网关协议，如RIP或OSPF？

内部网关协议（如RIP或OSPF）主要是设法使数据报在一个AS中尽可能有效地从源站传送到目的站。在一个AS内部也不需要考虑其他方面的策略。然而BGP使用的环境与此不同。不使用内部网关协议主要有以下两个原因。

互联网的规模太大，使AS之间路由选择非常困难。连接在互联网主干网上的路由器，必须对任何有效的IP地址都能在路由表中找到匹配的目的网络。目前在互联网的主干网路由器中，一个路由表的项目数早已超过了5万个。例如，如果使用链路状态算法，则每一个路由器必须维持一个很大的链路状态数据库。对于这样大的主干网，用Dijkstra算法计算最短路径花费的时间也太长。另外，由于AS各自运行自己选定的内部路由选择协议，并使用本AS指明的路径度量，因此，当一条路径通过几个不同AS时，要想对这样的路径计算出有意义的代价是不太可能的。例如，对某AS来说，代价为1000可能表示路由比较长；但对另一AS来说，代价为1000却可能表示不可接受的坏路由。因此，对于AS之间的路由选择，要用“代价”作为度量来寻找最佳路由也是很不现实的。比较合理的做法是在AS之间交换可达性信息（即“可到达”或“不可到达”）。例如，告诉相邻路由器：“到达目的网络N 可经过ASx ”。
AS之间的路由选择必须考虑有关策略。由于相互连接的网络的性能相差很大，根据最短距离（即最少跳数）找出来的路径可能并不合适，还有的路径使用代价很高或很不安全。还有一种情况，如AS1 要发送数据报给AS2 ，本来最好是经过AS3 ，但AS3 不愿意让这些数据报通过自己的网络，因为“这是他们的事情，和我们没有关系”。但是，AS3 愿意让某些相邻AS的数据报通过自己的网络，特别是那些付了服务费的AS。因此，AS之间的路由选择协议应当允许使用多种路由选择策略。这些策略包含政治、安全或经济方面的考虑。例如，我国国内的站点在互相传送数据报时不应经过国外兜圈子，特别是，不要经过某些对我国的安全有威胁的国家。这些策略都是由网络管理人员对每一个路由器进行设置的，但这些策略并不是AS之间的路由选择协议本身。还可举出一些策略的例子，如“仅在到达下列这些地址时才经过ASx ”“ASx 和ASy 相比时应优先通过ASx ”等。显然，使用这些策略是为了找出较好的路径而不是最佳路径。

由于上述情况，BGP只是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由，重要的是能根据策略进行路由选择。

6.4.2、BGP的基本原理

BGP采用的是路径向量（Path Vector，PV）路由选择算法（简称路径向量算法）。该算法的基本思想是：相邻结点间互相通告自己到所有目的地的路径信息（路径经过的结点列表），各结点根据获得的路径信息选择一条到目的地经过结点数最少且不存在环路的路径。路径向量算法与距离向量算法非常相似，不同之处在于：通告的路由信息不是到目的地的距离而是到目的地的路径信息（路径向量），由于路径信息包含所经过的所有结点的标识，可以避免循环路由，因此没有距离向量算法“坏消息传播得慢”的问题。

在配置BGP时，每一个AS的管理员至少要选择一个路由器作为该AS的“BGP发言人”，BGP发言人往往配置在AS边界路由器上。BGP发言人负责在AS间交换路由信息。一个BGP发言人要想与其他AS的BGP发言人要交换路由信息，就要先建立TCP连接（端口号为179），然后在此连接上交换BGP报文以建立BGP会话（Session），利用BGP会话交换路由信息，如增加新的路由、撤销过时的路由，以及报告差错等。使用TCP连接交换路由信息的两个BGP发言人，彼此成为对方的邻居（Neighbor）或对等方（Peer）。这里需要注意的是，BGP对等方并不一定在物理上是相邻的（连接在同一个物理网络中）。

为了将BGP发言人获得的AS之外的网络可达性信息分发给AS内的所有路由器（包括同一AS内的其他BGP发言人），BGP发言人还需要通过BGP会话与AS内部的每个路由器进行通信，虽然OSPF或RIP等内部网关协议也可以完成这项工作，但BGP对话更加高效。为了区别两种不同用途的BGP会话，我们将两个AS之间的BGP会话称为外部BGP会话（external BGP Session，eBGP会话），而将同一AS内路由器之间的BGP会话称为内部BGP会话（internal BGP Session，iBGP会话）。

每一个BGP发言人除了必须运行BGP外，还必须运行该AS所使用的内部网关协议（如OSPF或RIP），内部网关协议为BGP发言人提供AS内部的路由信息。

如下图所示，是BGP发言人和AS的关系图，图中画出了三个AS中的五个BGP发言人。这里以R1为例进行说明，R1首先会使用eBGP获得的到其他AS的网络可达性信息，然后会通过iBGP将这些网络可达性信息发给AS1中的其他路由器（包括AS内的另一个边界路由器R4）。最后，AS内的各路由器会对所有的路由信息（通过iBGP获得的外部路由信息和通过内部网关协议得到的内部路由信息）进行合并生成最终的路由表。

各AS的BGP发言人所交换的网络可达性信息主要是，到达某个网络（用网络前缀表示）所要经过的一系列AS。BGP交换的路由信息主要包括：目的网络前缀、下一跳路由器（AS边界路由器），以及到达该目的网络所要经过的各个自治系统序列（路径向量）。

BGP支持CIDR。例如，某AS中有4个子网，分别是：156.12.32.0/24、156.12.33.0/24、156.12.34.0/24以及 156.12.35.0/24，那么该AS在向其他AS发送路由交换信息时，通告的网络是156.12.32.0/22（进行了地址聚合）。

在使用 BGP 的网络中，每个AS都有个全局唯一的自治系统号 ASN，作为该AS 标识。当一台路由器通过 BGP 会话向另一台路由器通告一个网络前缀时，前缀中还包含一些重要属性（在 BGP 术语中，包含属性的前缀通常被称为一条路由）。其中，比较重要的属性是AS-PATH和NEXT-HOP。

AS-PATH（AS路径）。是到达某个网络前缀需要经过的AS路径。当一条路由到达一个AS的网关路由器时，网关路由器就会将其所属AS的ASN，添加到这条路由的AS-PATH中。
NEXT-HOP。NEXT-HOP 是一个开始 AS-PATH 的路由器接口。假设图4.31中的AS3向AS1通告一条路由，那么这条路由中的NEXT-HOP，就是3c与1a 相连接的链路在3c一侧的接口地址。当这条路由到达AS1的网关路由器1a时，1a通过iBGP 会话，将该条路由传播到 AS1 内的所有路由器。当路由器1c得到了这条路由后，会在其转发表中建立相应的转发项，其中目的子网就是这条路由中所包含的前缀，而接口则是通过自治系统内部路由选择算法，所决定的1c去往1a的接口（路由器1c去往1a的最佳路径接口）。

当一条路由到达一台网关路由器后，网关路由器需要基于一定的策略，来决定是接受还是丢弃该路由。一般来说，网关路由器依次按下列规则对路由进行过滤

本地偏好值属性。这个属性由 AS 网络管理员来设定，具有最高偏好值的路由被选择。
若多条路由具有相同的本地偏好值，那么具有最短AS-PATH 的路由将被选择。
若多条路由具有相同的本地偏好值以及相同长度的 AS-PATH，那么具有最近NEXT-HOP的路由将被选择

下图给出了BGP发言人交换路径向量的例子。例如，AS2 的BGP发言人通知主干网的BGP发言人：“要到达网络N1 、N2 、N3 和N4 可经过AS2 ”。主干网BGP发言人收到该通知后，就发出通知：“要到达网络N1 、N2 、N3 和N4 可经过AS1 、AS2 ”。

在BGP发言人互相交换了网络可达性信息后，各BGP发言人就根据所采用的策略从收到的路由信息中找出到达各AS的较好路由。下图表示了上图AS1中的一个BGP发言人构造出的AS连通图，它是树形结构，不存在回路。

在BGP网络中，交换路由信息的结点数量级是自治系统数的量级，远小于整个互联网的网络数。因此要在许多自治系统之间寻找一条较好的路径不会耗费太多的时间。

由于使用了路径向量信息，因此很容易避免产生兜圈子的路由。如果一个BGP发言人收到了其他BGP发言人发来的路径通知，它就要检查一下本自治系统是否在此通知的路径中。如果在这条路径中，就不能采用这条路径（因为会兜圈子）。因此BGP很容易解决距离向量路由选择算法中的“坏消息传播得慢”这一问题。

由于路由信息包含经过的每个自治系统的标识符，策略的加入很方便。例如，选择不经过某个敌对国家自治系统的路径，不向某个自治系统通告到某个网络的路径，等等。

在BGP刚刚运行时，BGP对等方之间要交换整个BGP路由表，但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销都有好处。

6.4.3、BGP报文

BGP4使用了以下四种报文。

OPEN（打开）报文：用来与另一个BGP发言人建立对等关系，使通信初始化。
UPDATE（更新）报文：用来通告某条路由信息，以及列出要撤销的多条路由。
KEEPALIVE（保活）报文：用来周期性地证实对等方的连通性。
NOTIFICATION（通知）报文：用来发送检测到的差错。
ROUTE-REFRESH报文（在RFC 2918中增加）：用来请求对等方重新通告。

若一个BGP发言人想与另一个AS的BGP发言人建立对等关系，就需要向对方发送OPEN报文，如果对方接受这种对等关系，就用KEEPALIVE报文响应。这样，两个BGP发言人的对等关系就建立了。

一旦对等关系建立了，就要继续维持这种关系。双方中的每一方都需要确信对方是存在的，且一直在保持这种对等关系。为此，这两个BGP发言人彼此要周期性地交换KEEPALIVE报文（一般每隔30s）。KEEPALIVE报文只有19字节长，不会造成网络上太大的开销。

UPDATE报文是BGP的核心内容。BGP发言人可以用UPDATE报文撤销它以前曾经通知过的路由，也可以宣布增加新的路由。撤销路由可以一次撤销许多条，但增加新路由时，每个UPDATE报文只能增加一条。

七、参考

计算机网络教程（第6版·微课版）

计算机网络原理创新教程

计算机网络原理自考04741

网络

#计算机网络原理

计算机网络原理：网络层

https://kuberxy.github.io/2024/11/24/计算机网络原理04：网络层/

作者

Mr.x

发布于

2024年11月24日

许可协议

计算机网络原理：Internet路由选择协议上一篇

计算机网络原理：传输层下一篇