Chapter4 - 网络层

本章最重要的内容是：

虚拟互联网络的概念
IP地址与物理地址的关系
传统的分类的IP地址（包括子网掩码）和无分类域间路由选择CIDR
路由选择协议的工作原理

4.1 网络层提供的两种服务

在计算机网络领域，网络层应该向运输层提供怎样的服务？
- 两种选择：面向连接 or 无连接
- 争论焦点的实质：数据的可靠传输应该由网络还是端系统来负责？
面向连接的服务，即虚电路（virtual circuit）
- 通信双方在开始数据传输前，先由网络建立连接（在分组交换中是建立一条虚电路），之后的数据均通过该连接进行，由网络保证数据传输的可靠性
- 虚电路只是一种逻辑连接，分组沿着这条逻辑连接按照存储转发方式传送，而并不是真正建立了一条物理连接。这样分组的首部不需要填写完整的目的主机地址，而只需要填写这条虚电路的编号，因而减少了分组的开销。
- 这种通信方式如果再使用可靠的网络协议，就可使所发送的分组无差错按序到达终点。
- 支持方：以电信公司为代表的一派
无连接的服务，即数据报（datagram）
- 设计思路：网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。（这里数据报就是分组packet）
- 网络在发送分组时不需要先建立连接，每个分组独在网络中独立发送，与其前后的分组无关（不进行编号）。
- 网络层不提供服务质量的承诺。也就是说，分组可能出错、丢失、重复和失序，也不保证分组交付的时限。由网络主机中的运输层负责可靠传输（包括差错处理、流量控制）。
- 好处：网络造价大大降低，运行方式灵活，能够适应多种应用。
- 支持方：以Internet为代表的一派
TCP/IP采用数据报服务

4.2 网际协议

一、IP（Internet Protocol）简介

网际协议 IP 是 TCP/IP 体系中两个最主要的协议之一，也是最重要的互联网标准协议之一。
- 严格来说，这里所讲的 IP 其实是 IP 的第四个版本，即 IPv4。
- 由于网际协议 IP 是用来使互联起来的多个计算机网络能够进行通信的，因此 TCP/IP 体系中的网络层常常被称为网际层（Internet layer）。
与 IP 协议配套使用的还有四个
协议：
- 地址解析协议ARP (Address Resolution Protocol)
- 逆地址解析协议RARP (Reverse Address Resolution Protocol)~~(已淘汰)~~
- 网际控制报文协议ICMP (Internet Control Message Protocol)
- 网际组管理协议IGMP (Internet Group Management Protocol)
这几个协议之间的关系如下：
- ARP画在最下面，因为IP经常要使用这个协议。
- ICMP和IGMP画在这一层的上部，因为它们要使用IP协议。

实例 - Linux中接收/发送包的调用图

包接收：
1. 网络接口卡(NIC)收到帧后触发中断
2. 中断服务程序调用net_rx_action()接收帧
3. 调用网络层接口函数netif_receive_skb()将帧中数据交给网络层
4. 包被注册到sk_buff中以便后续处理
  - 如为IP协议包则调用ip_rcv()作协议处理
  - 如包是发给本机的，则调用ip_local_deliver()和ip_local_deliver_finish()将数据交给传输层
包发送：
1. 根据传输层协议不同，分别调用接口函数ip_append_data()、ip_append_page()或ip_queue_xmit()将数据交给传输层
2. 调用dst_output()，将包注册到sk_buff
  - 如为IP包，则调用ip_output()
  - 如不分片，则ip_finish_output2()调用net_tx_action()将包交给数据链路层
3. 调用网卡驱动程序接口函数发送帧，帧发送完毕后通常会产生中断通知上层
注：
- sk_buff是Linux中用于存储和处理包的数据结构，采用双向链表结构。通过使用sk_buff，无需在各层间和程序模块间复制数据，而只需传递指针。

二、虚拟互联网络

在讨论网际协议IP之前，必须了解什么是虚拟互连网络。

由于用户的需求是多种多样的，没有一种单一的网络能够适应所有用户的需求。另外，网络技术是不断发展的。因此在市场上总是有很多种不同性能、不同网络协议的网络，供不同的用户选用。

从一般的概念来讲，将网络互相连接起来要使用一些中间设备：
1. 物理层使用的中间设备叫做转发器（repeater）。
2. 数据链路层使用的中间设备叫做网桥或桥接器（bridge）。
3. 网路层使用的中间设备叫做路由器（router）。
4. 在网络层以上使用的中间设备叫做网关（gateway）。用网关连接两个不兼容的系统需要在高层进行协议的转换。
其中，网关由于比较复杂，目前使用得较少，因此目前的网络互连都是指用路由器进行网络互连和路由选择。
- 由于历史原因，许多有关 TCP/IP 的文献曾经把网络层使用的路由器称为网关。

下图(a)表示有许多计算机网络通过一些路由器进行互连。由于参加互连的计算机网络都是用相同的网际协议IP（Internet Protocol），因此可以把互连以后的计算机网络看成如图(b)所示的一个虚拟互连网络（Internet），也就是逻辑互联网络。

这种使用IP协议的虚拟互连网络可简称为IP网，下面看一个实例。

在如图所示的互联网中的源主机H1要把一个IP数据报发送给目的主机H2。
1. 主机H1先要查找自己的路由表，看目的主机是否在本网络上。
  - 如是，则不需要经过任何路由器而是直接交付；
  - 如不是，则必须把IP数据报发送给某个路由器（图中R1）。
2. R1在查找了自己的路由表后，知道应当把数据报转发给R2进行间接交付。
3. 这样一直转发下去，最后路由器R5知道自己是和H2连接在同一个网络上，于是把数据报直接交付给目的主机H2.
注意
- 主机的协议栈共有五层，而路由器的协议栈只有下三层。
- R4和R5之间使用了卫星链路，而R5所连接的是个无线局域网。
- R1到R4之间的三个网络可以使任意类型的，即互联网可以由多种异构网络互连组成。

三、分类的IP地址

在 TCP/IP 体系中，IP地址是一个最基本的概念，有关IP最重要的文档是互联网的正式标准 RFC 797。

1. IP地址及其表示方法

IP 地址
- 分配给主机或路由器的标识符，目前使用的IPv4为32位IP地址
- IP 地址的分配由ICANN (Internet Corporation for Assigned Names and Numbers)负责
IP地址的编址方法经历了三个阶段：（本节仅讨论 1.，后两种方法在4.3节讨论）
1. 分类的 IP 地址：最基本的编址方法，1981 年通过标准
2. 子网的划分：最基本编址方法的改进， 1985 年成为标准[RFC 950]
3. 构成超网：比较新的无分类编址方法，1993 年提出后很快得到应用
分类的IP地址
- IP地址被划分为若干个固定类，每一类地址都包含网络号(net-id)和主机号(host-id)两个字段。
  - 网络号标志主机（或路由器）所连接到的网络，一个网络号在整个互联网范围内必须是唯一的。
  - 主机号标志该主机（或路由器），一台主机号在它前面的网络号所指明的网络范围内必须是唯一的
  - 这种两级的IP地址可以记为：IP 地址 ::= { <网络号>, <主机号>}
- 不同类的IP地址区别主要是网络号、主机号的长度不同，下图给出了各种IP地址的网络号字段和主机号字段：
  - A类、B类和C类地址都是单播地址（一对一通信），最常用。
  - A类、B类和C类地址的网络字段号分别为1个、2个和3个字节长，而在网络号字段的最前面有 1~3 位的类别位，其数值分别规定为 0，10和110。
  - A类、B类和C类地址的主机号字段分别为3个、2个和1个字节长。
  - D类地址（前4位是1110）用于多播（一对多通信），4.6节讨论IP多播。
  - E类地址（前4位1111）保留为以后用。

IP地址的表示方法
- 点分十进制记法（dotted decimal notation），下图是一个B类IP地址的表示方法。

2. 常用的三种类别的IP地址

A类地址
- 网络号字段占1个字节，只有7位可供使用（第一位已固定为0），可指派的网络号为126个（即 $2^7 - 2$ 个）。减2的原因是：
  1. IP地址中的全0为保留地址，表示“本网络”。
  2. 网络号为127（即 01111111）保留作为本地软件环回测试（loopback test） 本主机的进程之间的通信之用。若主机发送一个目的地址为环回地址（例如 127.0.0.1）的IP数据报，则本主机中的协议软件仅处理数据，而不会将其发送到任何网络。
- 主机号字段占3个字节，最大主机数为 $2^{24} - 2$ 个（即 16777214个）。减2的原因是：
  1. 全0的主机号字段表示该IP地址是 “本主机”所连接到的单个网络地址 。例如，主机IP地址为 5.6.7.8，则该主机所在网络地址即为 5.0.0.0。
  2. 全1表示“所有的(all)**”，即该网络上的所有主机**。
- IP地址空间共有 $2^{32}$ 个地址，整个A类空间共有 $2^{31}$ 个地址，占整个IP地址空间的50%。
B类地址
- 网络号字段有2个字节，前两位（1 0）固定，只有14位可以分配。
  - 由于B类地址不可能出现整个2字节为全0或全1，因此不存在网络总数减2的问题。但实际上B类网络的128.0是不指派的，而可以指派的B类网络最小网络地址为 128.1 [COME06]，因此可指派的网络数为 $2^{14} - 1$ （即16383）。
- B类网络最大主机数为 $2^{16} - 2$ ，即65534。这里减2的原因是要扣除全0和全1的主机号。
- 整个B类地址空间共约有 $2^{30}$ 个地址，占整个IP地址空间的25%。
C类地址
- 网络号字段有3个字节，前面3位（1 1 0）固定，还有21位可以进行分配。
  - C类网络地址 192.0.0 也是不指派的，可以指派的C类最小网络地址是 192.0.1 [COME06]，因此可指派的网络总数是 $2^{21} - 1$，即2097151.
- 最大主机数为 $2^8 - 2$ ，即254。
- 整个C类地址空间共约有 $2^{29}$ 个地址，占整个IP地址空间的12.5%。
这样我们就可得出IP地址的指派范围，如下表所示：

IP地址的特点
1. IP地址是一种分等级的地址结构。好处是：第一，IP地址管理机构只分配网络号，而主机号由各网络单位自行分配；第二，路由器仅根据目的主机所连接的网络号来转发分组，而不考虑目的主机号，从而大大减少了路由表所占的存储空间以及查找路由表的时间。
2. 实际上IP地址是标志以太主机和一条链路的接口。当一台主机同时连接到两个网络上时，该主机必须同时拥有两个IP地址，这种称为多归属主机（multihomed host）。
3. 一个网络指具有相同网络号（net-id）的主机的集合，因此，用转发器或网桥连接起来的若干个局域网仍为同一个网络，具有不同网络号的局域网必须使用路由器进行互连。
4. 在IP地址中，所有网络都是平等的，即互联网同等对待每一个IP地址。

四、IP地址与硬件地址

物理地址
- 数据链路层和物理层使用的地址。
- 存放在数据链路层的MAC帧中。
IP地址
- 网络层和以上各层使用的地址，是一种逻辑地址。
- 存放在IP包头部

从不同层次上看IP地址和硬件地址
- 下图是用两个路由器连起来的三个局域网，现主机H1要和主机H2通信。

这里要强调以下几点：
1. 在IP层抽象的互联网上只能看到IP数据报。首部中的源地址和目的地址始终为IP1和IP2，而中间经过的两个路由表的IP地址并不出现在IP数据报的首部。
2. 在局域网的链路层，只能看见MAC帧。MAC帧在不同网络上传送时，其MAC帧首部的源地址和目的地址要发生变化。
3. 另外，虽然IP数据报首部有源站IP地址，但路由器只根据目的站的IP地址的网络号进行路由选择。

新的问题：
1. 主机或路由器是怎样知道应当在MAC帧的首部填入什么样的硬件地址？（见下一节ARP协议）
2. 路由器中的路由表是怎样得出的？（见4.5节路由选择协议）

五、地址解析协议ARP

ARP协议(Address Resolution Protocol)
- ARP协议的用途是为了从网络层使用的IP地址，解析出在数据链路层使用的硬件地址。
- 主机设有一个ARP高速缓存(ARP cache)，存有本地局域网上各主机和路由器的 IP 地址与硬件地址的映射表。且对保存在高速缓存中的每一个映射地址项目都设置生存时间，凡超过生存时间的项目就从高速缓存中删除。
- 当主机 A 欲向本局域网上的主机B发送IP包时
  1. 先在其ARP高速缓存中查看有无主机B的IP地址
  2. 如有，就可查出其对应的硬件地址，再将此硬件地址写入MAC帧，通过局域网发送
  3. 如无，则在本局域网中广播一个ARP请求分组。
  4. 当主机B收到ARP请求后，向主机A返回一个ARP响应分组（单播），告知自己的物理地址。
- ARP解决同一局域网中的主机或路由器的 IP 地址和硬件地址的映射问题。如果目的主机不在本局域网内，IP包需经由路由器转发。

六、IP数据报格式

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

英文版如下：

下面介绍首部各字段的意义。

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

版本（Version）
- 占4bit。指 IP 协议的版本，目前的 IP 协议版本号为 4 (即 IPv4)。
首部长度（IHL）
- 占4bit。指 IP 包头长度，最小5，最大15，单位为word(32bit)。因此 IP包头最长60 字节。
- 由于大部分IP数据报的可选字段为0，即首部长度为5个字（20字节），因此我们经常可以看到IP数据报由 4 5 开头。
- 当首部长度不是4字节的整数倍时，必须利用最后的填充字段加以填充。因此IP数据报的数据部分永远在4字节的整数倍时开始。
区分服务（Type of service）
- 占1字节，用来获得更好的服务。在旧标准中叫做服务类型，1998年IETF改名为区分服务DS（Differentiated Services）。在一般情况下都不使用这个字段。
总长度（Total length）
- 指首部和数据之和的长度。占2字节，因此IP包的最大长度为 64K（即65535）字节。然而实际上传送这样长的数据报在现实中极少遇到。
- 每一种数据链路层协议都规定了一个数据帧中的数据字段的最大长度，这称为最大传送单元MTU（Maximumm Transfer Unit）。当数据报的总长度超过 MTU 的值时，就必须把过长的数据报进行分片处理。
- 此时，该字段是指分片后的每一个分片的首部长度与该分片的数据长度的总和。
标识（identification）
- 占2字节。IP软件在存储器中维护一个计数器，每产生一个数据报，计数器就加1，并将此值赋给标识字段。
  - 注意这个“标识”并不是序号，因为IP是无连接服务，数据报不存在按序接收的问题。
- 当数据报由于长度超过 MTU 而必须分片时，分片的多个包标识字段相同，便于接收端重组。
标志（flag）
- 占3位，但目前只有两位有意义。
  - DF（Don’t Fragment）：不能分片，只有当 DF = 0 时才允许分片。
  - MF（More Fragment）：MF = 1 即表示后面“还有分片”；MF = 0 表示这是若干分片的最后一个。
片偏移（Fragment offset）
- 占13bit，指出较长的包在分片后，某片在原分组中的相对位置。也就是说，相对于用户数据字段的起点，该片从何处开始。
- 以8字节为偏移单位。也就是说，每个分片的长度一定是8字节的整数倍。

【分片举例】：一数据报总长度为3820字节，数据部分为3800字节长（使用固定首部），需要分片为长度不超过 1420字节的数据报片。于是数据部分长度分别为 1400，1400，1000字节，结果如下：

下表是本例中数据报首部与分片有关的字段中的数值，其中标识字段的值为任意给定的（12345）。

生存时间（Time to live）
- 占1字节，表明数据报在网络中可通过的路由器个数的最大值，因而后来又称为“跳数限制”。目的是防止无法交付的数据报无限制地在互联网中兜圈子。
- 路由器在每次转发数据报之前就把TTL值减1。若为0则丢弃，并向源主机发送一个告警包。
- 显然数据报在互联网中经过的路由器的最大数值为255。由源主机设定初始值，Windows操作系统一般为128，UNIX操作系统一般为255，Linux一般为64
协议（Protocol）
- 占8bit，指出此数据报携带的数据时何种协议，以便使目的主机的IP层知道应该将数据部分上交给哪个协议进行处理。
- 常用的一些协议和相应的协议字段值如下：

首部校验和（Header checksum）
- 占2字节。这个字段只检验数据报的首部，不包括数据部分。
- IP首部的校验和不采用复杂的CRC检验码而采用下面的简单计算方法：
- 在发送方，先把IP数据报首部划分为许多16位字的序列，并把检验和字段置零。用反码算数运算把所有16位字相加后，将得到的和的取反码写入检验和字段。
- 接收方收到数据报后，将首部的所有16位字再使用反码算数运算相加一次，将得到的和取反码，即得出接收方检验和的计算结果。若首部未发生任何变化，则结果必为0。否则认为出差错，丢弃该包。

【校验和举例】下图说明了IP数据报首部检验和的计算过程。

【问】IP包在网络中传输过程中，何时检查校验和？何时计算填写校验和？

【答】路由器在接收到IP数据报时，应先检验校验和，再令TTL 减1。最后将校验和字段置0后再重新计算一次校验和。

源地址（Source address）
- 占4字节，源IP地址。
目的地址（Destination address）
- 占4字节，目的IP地址。

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

可变部分就是一个选项字段，用来支持排错、测量以及安全等措施。此字段长度可变，从1个字节到40个字节不等，这就增加了路由器处理数据报的开销。因此实际上这些选项很少被使用。

七、IP层转发分组的流程

略，见教材P142。

4.3 划分子网和构造超网

一、划分子网

1. 从两级IP地址到三级IP地址

两级IP地址的缺点：
1. IP地址空间的利用率有时很低。
  - A类地址的主机数超过1000万，B类地址也超过6万
2. 给每一个物理网络分配一个网络号会使路由表变得太大因而使网络性能变坏。
3. 两级IP地址不够灵活。
1985年起，增加子网字段，形成三级IP地址。
- RFC 950: Internet Standard Subnetting Procedure
划分子网的基本思路如下：
1. 拥有多个物理网络的单位可按物理网络划分为若干个子网(subnet)
2. 划分方法为：从主机号借用若干位作为子网号（subnet-id），于是两级IP地址在本单位内部就变为了三级IP地址，记为：
  - IP地址 ::= {<网络号>, <子网号>, <主机号>}
3. 从其他网络发来的IP数据报，仍然根据IP数据报的目的网络号（net-id），找到本网络的路由器。此路由器收到IP数据报后，再按目的网络号（net-id）和子网号subnet-id找到目的子网。

【划分子网举例】

2. 子网掩码

子网掩码的提出
- 从IP数据报的首部无法看出源主机或目的主机所连接的网络是否进行了子网的划分。因此，提出了子网掩码（subnet mask）。
使用子网掩码的好处：
- 不管网络有没有划分子网，只要把子网掩码和IP地址执行“按位与”运算，即得到子网地址，见下图。

默认子网掩码：1的位置和IP地址中的网络号字段 net-id 正好相对应。
- A类地址的默认子网掩码是 255.0.0.0;
- B类地址的默认子网掩码是 255.255.0.0;
- C类地址的默认子网掩码是 255.255.255.0;
补充：
- 子网掩码是一个网络或一个子网的重要属性。
- 在RFC 950称为互联网的正式标准后，规定了所有网络都必须使用子网掩码。路由器的路由表中的每个表项除了包含目的网络地址外，还要有子网掩码栏目。
- 若一个路由器连接在两个子网上，就拥有两个网络地址和两个子网掩码。

【子网掩码举例】

2. 使用子网掩码的分组转发过程

在划分子网的情况下，路由表必须包含：目的网络地址、子网掩码和下一跳地址。路由器转发分组的算法的核心操作为：将目的IP地址与路由表中子网掩码“与”，并判断是否与目的网络匹配，具体步骤如下：

① 从收到的分组的首部提取目的IP地址D
② 先用与该路由器直接相连各网络的子网掩码和D逐位相“与”，看是否和相应
的网络地址匹配，若匹配，则将分组直接交付（当然还需要把D转换成物理地址，把数据报封装成帧发送出去），转发任务结束；否则就是间接交付，执行③
③ 若路由表中有目的地址为D的特定主机路由，则将分组传送给指明的下一跳路
由器；否则执行④
④ 对路由表中的每一行的子网掩码和 D 逐位相“与”，若其结果与该行的目的
网络地址匹配，则将分组传送给该行指明的下一跳路由器；否则执行⑤
⑤ 若路由表中有一个默认路由，则将分组传送给路由表中所指明的默认路由器
；否则执行⑥
⑥ 报告转发分组出错

注意：对于默认路由，其在路由表中的目的网络地址和子网掩码均为 0.0.0.0。

【举例】下图有三个子网，两个路由器，以及R1中的部分路由表。考虑主机H1向H2发送数据包后的转发过程。

【答】

源主机H1判断目的地址是否在本地子网。
- 源主机H1把本子网的“子网掩码 255.255.255.128” 与目的主机H2的 “IP地址 128.30.33.138” 做按位与运算，得出 128.30.33.128，它不等于H1的网络地址（128.30.33.0）。因此，H1不能把分组直接交付给H2，而必须交给子网上的默认路由器R1（也可能是进行了ARP查询），由R1来转发。

if ((目的地址 & subnet mask) == (主机地址 & subnet mask)) // &源主机网络地址
    目的地址在本地子网，直接交付
else
    数据包发往gateway，间接交付

路由器R1在收到一个分组后，在路由表中逐行寻找有无匹配的网络地址。
- 第二行“子网掩码 255.255.255.128” 与收到分组的目的主机H2的 “IP地址 128.30.33.138” 做按位与运算，得出 128.30.33.128，与目的网络地址相匹配，R1将数据报发往该表项的网络出口。

1 2	if ((目的地址 & subnet mask) == 目的网络地址) 数据包发往该表项的网络出口； // 或是下一跳路由，或是目的主机所在子网

在子网内直接交付给目的主机H2。

查找ARP缓存，是否有目的IP地址对应的MAC地址
if (目的MAC地址在ARP缓存中) 
    将IP数据包封装成帧后，在局域网内向目的MAC地址直接发送帧
else
    在子网内广播发送ARP请求，目的主机收到请求后返回ARP应答，由此 得知目的主机MAC地址

二、无分类编址 CIDR （构造超网）

1. 网络前缀

无分类域间路由CIDR(Classless Inter-Domain Routing， CIDR的读音是 “sider”) ，CIDR的最主要的两个特点：

CIDR消除了传统的A类、B类和C类地址以及划分子网的概念，而是使用各种长度的“网络前缀”(network-prefix)来代替分类地址中的网络号和子网号。
- IP地址从三级编址(使用子网掩码)又回到了两级编址
  - IP地址 ::= {<网络前缀>, <主机号>}
- CIDR还使用“斜线记法”(slash notation)，又称为CIDR记法，即在IP地址后加一个斜线“/”，后跟网络前缀所占的位数。
  - 例：128.14.35.7/20 表示该地址的高20位是网络前缀。
CIDR把网络前缀都相同的连续的IP地址组成一个“CIDR地址块”，只要知道CIDR地址块中的任何一个地址，就可以知道这个地址块的起始地址（即最小地址）和最大地址，以及地址块中的地址数。
- 例如，128.14.32.0/20表示的CIDR地址块共有 $2^{12}$ 个地址.
  - 地址块的起始地址：128.14.32.0
  - 地址块的最大地址：128.14.47.255

路由聚合(route aggregation)
- 一个 CIDR 地址块可以表示很多地址，这种地址的聚合称为路由聚合。
- 路由聚合的好处：路由表中的一个项目可以表示很多个(例如上千个)原来传统分类地址的路由，可以减少路由表中表项个数，并减少路由器间交换的路由信息量。
- 由于CIDR地址块大多包含多个C类地址，因此路由聚合也称为**构成超网(supernetting)**。
注意不能把没有的路由聚合进去——“路由黑洞”
关于地址掩码
- 为了更方便地进行路由选择，CIDR 使用 32位的地址掩码（address mask）。
  - 例：/20的地址掩码是：11111111 11111111 11110000 00000000

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

CIDR记法的其他形式
1. 省略点分十进制中低位连续的0。如 10.0.0.0/10 可简写为 10/10。
2. 网络前缀后跟星号 * 的表示方法。如 00001010 00，**星号 \ 之前为网络前缀，星号 * 为任意主机号**。

【CIDR地址块分配举例】

2. 最长前缀匹配

使用CIDR时，路由表中的表项中的“目的网络地址”由固定长度变成了变长的“网络前缀”，因此查找路由表时可能会得到不止一个匹配结果。
最长前缀匹配(longest-prefix matching)原则：
- 从匹配结果中选择具有最长网络前缀的路由。
- 网络前缀越长，其地址块就越小，因而路由就越具体(more specific)。
- 最长前缀匹配又称为最长匹配或最佳匹配。

【最长前缀匹配举例】

假定大学下属的四系希望ISP把转发给四系的数据报直接发到四系而不经过大学的路由器，则在ISP的路由器的路由表中，至少要有以下两个项目，即 206.0.68.0/22（大学）和 206.0.71.128/25（四系）。
假定ISP收到的数据报的目的地址 D = 206.0.71.130，把D分别和路由表中这两个项目的地址掩码进行按位与操作，如下：

根据最长前缀匹配的原理，应当选择后者，即选择两个匹配的地址中更具体的一个。

【考研题举例】

解答：
- 2010
  - 由子网掩码知，最后一个字节为 1111 1000，即只有3位可分配主机，最大可分配地址个数为 $2^3 -2 = 6$。
  - 又由IP地址知，网络前缀有24位，故子网分配5位，即 $2^5 = 32$ 个子网。
- 2011
  - 网络前缀占30位，因而只有2位分配给主机，则最大主机数为 $2^2 - 2 = 2$ 个。

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

略

4.4 网际控制报文协议 ICMP

一、ICMP简介

RFC 792: Internet Control Message Protocol
ICMP允许主机或路由器报告差错情况和提供有关异常情况的报告。
ICMP是IP层的协议，ICMP报文封装在IP数据报的数据部分，报文格式如下图所示。

二、ICMP报文的种类

ICMP报文的种类有两种，即ICMP差错报告报文和ICMP询问报文。
ICMP报文的前4个字节是统一格式的，接着的4个字节与ICMP的类型有关，共有9中格式，见下表：

【中文版】

差错报告报文
1. Destination unreachable：终点不可达，路由器或主机无法传输报文时向源主机发送此报文。
2. Time exceeded：超时，路由器收到TTL字段为0的报文时，向源主机发送此报文。
3. Parameter problem：参数问题，路由器或主机收到的报文中，头部有非法字段时，丢弃数据包，并向源主机发送此报文。
4. Redirect：重定向，路由器向主机发送此报文告知路由改变，主机下次发送数据报给另外的路由器。
5. Source quench：源点抑制，路由器或主机由于拥塞丢弃报文时，向源主机发送此报文，使其放慢发送速度。
询问报文
1. Echo request / reply：回声探测，用于测试网络连通性。
2. Timestamp request / reply：请求时间，可用于时间同步。

【对路由改变的简要解释】

我们知道，互联网中的主机也要有一个路由表。在互联网中，主机的数量远大于路由表的数量，因此出于效率的考虑，这些主机不和网络上的路由器定期交换路由信息。

在主机刚开始工作时，一般都在路由表中设置一个默认路由器的IP地址。不管数据报要发送到哪，都一律传送给这个默认路由，而这个默认路由器知道每一个目的网络的最佳路由（通过和其他路由器交换路由信息）。

如果默认路由器发现主机发往某个目的地址的数据包的最佳路由应当经过网络中的另一个路由器R时，就用改变路由报文把这个情况告诉主机。

于是，该主机就在其路由表中增加一个项目：到某某目的地址应经过路由器R。

三、ICMP应用举例

详见“第一章概述 - 附”。

PING

用来测试两个主机之间的连通性.
采用ICMP echo request / reply报文。
- 向目的主机发送ICMP echo request报文，对方收到后会回应ICMP echo reply，根据能否收到应答后判断两台主机之间是否连通。

Traceroute / Tracert

用来测试到另一台主机所经过的路由信息
采用ICMP超时报告报文
- 逐个发出UDP报文，其IP包头中的TTL字段分别设为1, 2, 3, …，直到到达目的主机。
- 报文路由路径上的路由器会返回ICMP超时报文，从该报文即可得知路由器IP地址。

4.5 路由算法及路由选择协议

一、有关路由选择协议的几个基本概念

1. 理想的路由算法

在网络中，路由器依据路由信息(路由表)转发分组，路由信息是路由协议生成的，路由算法是路由协议的基础和核心。
- 注意：路由协议是用来生成路由信息(路由表)的，不是转发分组的
理想的路由算法应具备的特性：
1. 必须是正确的和完整的：按照得出的路由能够进行正确寻址
2. 在计算上应简单：不增加过多开销
3. 有自适应性：能根据通信量和网络拓扑的变化调整路由
4. 应具有稳定性：通信量和拓扑稳定时，能快速收敛
5. 应是公平的：对所有用户公平
6. 应是最佳的：能找出最好的路由(时延最小、吞吐量最大)。
  - 所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
倘若从路由算法能否随网络的通信量或拓扑自适应地进行调整变化来划分，则只有两大类，即静态路由与动态路由
- 静态路由选择策略
  - 非自适应路由选择
  - 简单和开销较小，但不能及时适应网络状态的变化
  - 适用于小规模且变化较少的网络，由人工设置路由
- 动态路由选择策略
  - 自适应路由选择
  - 能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大
  - 适用于较大规模、频繁变化的网络，通过专门的算法和协议进行路由的计算
两类典型的动态路由算法
- 距离向量(distance vector)路由算法
- 链路状态(link state)路由算法

2. 分层次的路由选择协议

Internet采用分层次的路由，原因：
- Internet规模庞大，任何一台路由器都不可能获取和存储整个Internet的路由信息
- 接入Internet的众多网络(管理方)不希望外界了解自己网络的内部信息
自治系统(AS—Autonomous System)
- 定义：在单一的技术管理下的一组路由器，而这些路由器使用一种 AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由，同时还使用一种 AS 之间的路由选择协议用以确定分组在 AS之间的路由
- 一个 AS可使用多种内部路由选择协议和度量，但对其他 AS 表现出的是单一的和一致的路由选择策略
在自治系统背景下，Internet路由协议可以分为两类：
- 内部网关协议 IGP(Interior Gateway Protocol)
  - 自治系统内部使用的路由选择协议
  - 这类路由协议使用得最多，如 RIP 和 OSPF 协议
- 外部网关协议EGP(External Gateway Protocol)
  - 若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中，这样的协议就是外部网关协议 EGP。
  - 应用最为广泛的外部网关协议：BGP-4
自治系统之间的路由选择又称为域间路由选择(interdomain routing)，自治系统内部的路由选择又称为域内路由选择(intradomain routing)。

【自治系统互连示意图】

二、内部网关协议 RIP

1. RIP 协议的工作原理

RIP(Routing Information Protocol)
- 一种分布式的基于距离向量的路由选择协议
- RIP 要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离（也称为跳数）。
  - 从一路由器到直接连接的网络的距离定义为1；
  - 从一路由器到非直接连接的网络的距离定义为所经过的路由器数加1。
- RIP允许一条路径最多只能包含15个路由器，因此距离为16时表示不可达，可见 RIP 只适用于小型互联网。
对于本节讨论的 RIP 协议和下一节要讨论的 OSPF 协议，都是分布式路由选择协议。它们的共同特点就是每一个路由器都要不断地和其他一些路由器交换路由信息。因此，以下三个要点非常重要：
1. 和哪些路由器交换信息？
2. 交换什么信息？
3. 在什么时候交换信息？
RIP 协议的主要特征：
1. 仅和相邻路由器交换信息。
2. 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。
3. 按固定的时间间隔交换路由信息(典型值：每隔 30 秒)。

路由表中最重要的信息是：到某个网络的距离（即最短距离），以及应经过的下一跳地址。
路由表更新的原则就是找出每个目的网络的最短距离，这种更新算法又称为距离向量算法。

2. 距离向量算法

对每一个相邻路由器发送过来的 RIP 报文，进行以下步骤：
1. 对于地址为X的相邻路由器发来的报文，先修改此 RIP 报文中的所有项目：把 “下一跳”字段 中的地址都改为 X，并把所有的“距离”字段的值加 1。每个项目有三个关键数据：目的网络N、距离d、下一跳路由器X。
2. 对修改后的 RIP 报文中的每一个项目，重复以下步骤：
- 若路由表中没有目的网络N，则把该项目加到路由表中。
- 否则
  - 若下一跳字段给出的路由器地址是X，则用收到的项目替换原有项目。
  - 否则
    - 若收到项目中的距离d小于路由表中的距离，则进行更新，
    - 否则，什么也不做。
1. 若 3 分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不
  可达路由器，即将距离置为16（距离为16表示不可达）。
2. 返回。

上面给出的距离向量算法的基础就是【Bellman-Ford 算法】，其核心思想为：
- 设 X 是结点 A 到 B 的最短路径上的一个结点。若把路径 A → B 拆成两端路径 A → X 和 X → B，则每一端路径 A → X 和 X → B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径。
距离向量路由的无穷计算问题
- 算法的缺陷：对好消息反应迅速，对坏消息反应迟钝。
- 见下例

3. RIP 协议的报文格式

RIP协议使用运输层的用户数据报 UDP 进行传送，其报文格式如下：

RIP报文由首部和路由部分组成
RIP的首部占4个字节，其中的命令字段指出报文的意义。
例如，1表示请求路由信息，2表示对请求路由信息的相应或未被请求而发出的路由更新报文。首部后面的“必为0”是为了4字节的对齐。

三、内部网关协议 OSPF

1. OSPF 协议的工作原理

OSPF（Open Shortest Path First）协议简介
- 一种分布式的链路状态协议(link-state protocol)
- 优点：
  - 收敛速度快
    - 当链路状态发生变化时，结点会以洪泛(flooding)方式告知所有网络中其他所有结点
  - 适用于较大规模的网络
    - 仅在链路状态发生变化时发送洪泛信息，不会产生很大通信量
OSPF 协议的主要特征：
1. 以洪泛(flooding)**方式向本自治系统中所有路由器**发送信息。
  - 洪泛(flooding): 结点收到分组时，向除输入链路外的所有其他链路发送出去
2. 发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。
  - “链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的度量（metrix）。OSPF将这个度量用来表示费用、距离、时延、带宽等等，也称为代价。
  - 注意，对于RIP协议，发送的信息是：到所有网络的距离和下一跳路由器。
3. 只有当链路状态发生变化时，路由器才向所有路由器用洪泛法发送此信息。
  - 而不像RIP那样，定期交换路由表的信息。
由于各路由器之间频繁地交换链路状态信息，每个路由器都建立一个链路状态数库。
- 这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的(即链路状态数据库的同步)。
因此，各路由器根据网络拓扑使用Dijkstra算法计算从本路由器到其他结点的最佳路径，构成路由表

2. OSPF 的区域划分

为了管理大规模的网络，OSPF 将一个自治系统再划分为若干个区域(area)，每一个区域都有一个 32 位的区域标识符(用点分十进制表示)。在一个区域内的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑。
层次结构的区域划分：
- 上层的区域称为主干区域(backbone area)，主干区域的作用是用来连通其他在下层的区域，主干区域的标识符规定为0.0.0.0。
- 从其他区域来的信息都由区域边界路由器（area border router）进行概括，例如下图的R3，R4和R7。
- 在主干区域内的路由器叫做主干路由器（backbone router），例如下图中的R3，R4，R5，R6和R7。
- 在主干区域内还有一个路由器专门和本自治系统外的其他自治系统交换路由信息，叫做自治系统边界路由器。例如下图中的R6。

划分区域的好处：
- 利用洪泛法交换链路状态信息的范围局限于一个区域而不是整个的自治系统，大大减少了整个网络上的通信量，因而使 OSPF 协议能够用于规模很大的自治系统中。

3. OSPF 的分组结构

OSPF 不用 UDP 而是直接用 IP 数据报传送（其 IP 数据报首部的协议字段值为 89）。

OSPF 构成的数据报很短，这样不仅可以减少路由信息的通信量，另一个好处是不必将长的数据报分片传送。分配传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。

OSPF 首部各字段的意义
1. 版本：当前的版本号是2。
2. 类型：可以使五种类型分组中的一种。
3. 分组长度：包括OSPF首部在内的分组长度，以字节为单位。
4. 路由器标识符：标志发送该分组的路由器的接口的IP地址。
5. 区域标识符：分组属于的区域的标识符
6. 检验和：用来检测分组中的差错。
7. 鉴别类型：目前只有两种，0（不用）和1（口令）。
8. 鉴别：鉴别类型为0时就填入0，鉴别类型为1则填入8个字符的口令。

4. OSPF 的五种分组类型

OSPF 共有以下五种分组类型
1. 类型1：问候（Hello）分组，用来发现和维持邻站的可达性。
2. 类型2：数据库描述（Database Description）分组，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。
3. 类型3：链路状态请求（Link State Request）分组，向对方请求发送某些链路状态项目的详细信息。
4. 类型4：链路状态更新（Link State Update）分组，用洪泛法对全网更新链路状态。
  - 这种分组时最复杂，也是 OSPF 最核心的部分。
5. 类型5：链路状态确认（Link State Acknowledgment）分组，对链路更新分组的确认。

如果所有的路由器都把自己本地的链路状态信息读全网进行广播，这种开销太大，因此，OSPF 采用下面的方法来更新链路状态数据库：
1. OSPF 规定，每两个相邻路由器每隔 10s 就交换一次问候分组，以此来确定哪些邻站是可达的。
2. OSPF 让每一个路由器用数据库描述分组和相邻路由器交换本数据库汇总已有的链路状态摘要信息。
  - 摘要信息主要就是指出有哪些路由器的链路状态信息已经写入了数据库。
3. 之后，路由器使用链路状态请求分组，向对方请求发送自己所缺少的某些链路状态项目的详细信息。
4. 通过一系列这种分组交换，全网同步的链路数据库就建立了。

四、外部网关协议 BGP

首先我们应当弄清，在不同自治系统 AS 之间的路由选择为什么不能使用前面讨论过的内部网关协议，如 RIP 或 OSPF？有以下两个原因：

第一，互联网的规模太大，使得自治系统AS之间路由选择非常困难。

第二，自治系统AS之间的路由选择必须考虑有关策略。

具体参考教材 P164。

1. BGP 协议基本原理

BGP(Border Gateway Protocol)简介
- BGP是不同自治系统的路由器之间交换路由信息的协议
- BGP采用了路径向量（path vector）路由选择协议，它与距离向量协议（如RIP）和链路状态协议（如OSPF）都有很大的区别。
BGP使用环境的特殊性
- Internet的规模很大，AS之间的路由选择非常困难
  - Internet主干网路由器中的网络前缀达到数万条
  - 对于AS之间的路由选择，要寻找最佳路由是不现实的
  - 不同AS对路径度量标准各不相同
- AS之间的路由选择需考虑多种策略
  - 例1：AS1到AS2的数据报经过AS3在技术上最佳，但AS3可能不同意
  - 例2：出于国家安全的考虑，可能不希望数据报流经某些国家
- 由于上述情况，BGP难以找到最佳路由，只能寻找一条能够到达目的网络且比较好的路由(不能兜圈子)，而并非要寻找一条最佳路由。
BGP发言人(speaker)
- 每个AS要选择至少一个路由器作为“BGP speaker”
- 两个BGP发言人通过一个共享网络连接在一起
- BGP发言人一般是AS的边界路由器，但也可以不是
- BGP 发言人与其他自治系统中的BGP发言人交换路由信息
- 路由信息的交换通过TCP协议进行，两个发言人**在TCP连接上交换BGP报文以建立BGP会话(session)**，利用 BGP 会话交换路由信息
- BGP发言人除了运行BGP协议外，还要运行AS的内部网关路由协议

信息交换与路由生成
- BGP所交换的网络可达性的信息就是要到达某个网络所要经过的一系列 AS，称为路径向量(path vector)
- BGP 发言人互相交换了网络可达性的信息后，就根据所采用的策略从其中找出到达各 AS 的较好路由。

【示例】

AS2的BGP发言人通知主干网的BGP发言人：要到达网络 N1, N2, N3 和 N4 可经过 AS2
主干网还可发出通知：“要到达网络 N5, N6 和 N7 可沿路径(AS1, AS3)

2. BGP-4 使用的四种报文

在 RFC 4271 中规定了 BGP-4 的四种报文：
1. OPEN报文：用来与相邻的另一个BGP发言人建立关系
2. UPDATE报文：用来发送某一路由的信息，以及列出要撤消的多条路由
3. KEEPALIVE报文：用来确认打开报文和周期性地证实邻站关系
4. NOTIFICATION报文：用来发送检测到的差错
信息交换与路由生成
1. BGP发言人通过OPEN报文与另一发言人建立会话，对方如同意则回应KEEPALIVE报文。
2. 双方周期性交换KEEPALIVE报文，以确认会话未中断。
3. 路由信息变化时，发送UPDATE报文。

3. BGP 报文的格式

下图给出了 BGP 报文的格式。

四种类型的 BGP 报文具有同样的通用首部，其长度为19字节。通用首部分为三个字段。
1. 标记字段，占16字节，用来鉴别收到的BGP报文。
2. 长度字段，占2字节，指出包括首部在内的整个BGP报文的长度（以字节为单位），范围在 19~4096之间。
3. 类型字段，占1字节，值为1到4，分别对应四种BGP报文类型。
OPEN 报文共有6个字段，即版本、本自治系统号、保持时间、BGP标识符、可选参数长度和可选参数。
UPDATE报文共有5个字段，即不可行路由长度、撤销的路由、路径属性总长度、路径属性和网络层可达性信息。
KEEPALIVE报文只有BGP的19字节唱的通用首部。
NOTIFICATION报文由3个字段。即差错代码（1字节）、差错子代码（1字节）和差错数据（给出有关差错的诊断信息）。

五、路由器的构成

1. 路由器的结构

路由器是一种具有多个输入/输出端口的专用计算机，其任务是转发分组。
路由器组成：
1. 路由选择部分，也叫控制部分，其核心构件是路由选择处理机。
  
  路由选择处理机的任务是根据所选定的路由选择协议构造并维护路由表。
2. 分组转发部分，由三部分构成：交换结构（switching fabric）、一组输入端口和一组输出端口。
  
  交换结构根据转发表（forwarding table）进行分组的快速转发，转发表从路由表得到。

路由器设计的关键之一是分组的高速转发
- 决定报文转发速率的因素有：
  - 输入/输出端口的处理性能
  - 交换机构的性能
  - 线速(line speed 或 wire speed): 分组的处理速率能够达到线路上分组的传输速率
- 衡量路由器性能的指标：pps(packet per second)
  - 如oc-48链路(2.5Gb/s)，如分组长度256字节，则线速转发意味着每秒处理分组数>100万
输入和输出端口的处理
- 当一个分组正在查找转发表时，后面又仅跟着从这个输入端口收到另一个分组，那么这个后到的分组必须在队列中排队等待，因而产生了一定的时延。
- 输出端口从交换结构接收分组，然后把它们发送到路由器外面的线路上。在网络层的处理模块设有一个缓冲区，当交换结构传输过来的分组的速率超过输出链路的发送速率时，来不及发送的分组就必须暂存在队列中。
  - 注意：当排队的分组数量过多时，可能导致路由器内部缓冲区溢出丢包。

2. 交换结构

交换结构是路由器的关键构件，下面给出了三种常用的交换方法。

具体特点见教材P170。

4.6 IP 多播

一、IP 多播的基本概念

组播(multicast)又称为多播，用于实现一点对多点的数据传输。
- 有许多应用需要由一个源点发送到许多个终点。例如，实时信息的交付（新闻、股市行情），软件更新，交互式会议等。
与单播相比，在一对多通信中，组播可大大节约网络资源。
- 例如，视频服务器用单播方式向90台主机发送同样的视频节目，则需要90个副本（图a）。
- 如果视频服务器把视频分组当作多播数据报来发送，则只需要发送一次。R1在转发分组时，复制3个副本分别转发给R2、R3和R4。
- 当分组到达目的局域网时，由于局域网具有硬件多播的功能，因此不需要复制分组，在局域网上的多播组成员都能收到这个视频分组。

在互联网上进行多播就叫做 IP 多播，IP 多播所传送的分组需要使用多播 IP 地址。
- 问题：显然，这个多播数据报的目的地址不能写入IP地址，因为同一时间可能有成千上万台主机需要接受这个多播数据报。
- 解决方案：多播数据报的目的地址写入的是多播组的标识符，然后设法让加入这个多播组的主机的IP地址与多播组的标识符关联起来。
多播数据报
- 使用D类IP地址作为多播组的标识符。D类IP地址的前四位是 1110，因此地址范围为 224.0.0.0—239.255.255.255。
- 首部中的协议字段值为2，表明使用网际组管理协议（IGMP）。
- 多播地址只能用于目的地址，而不能用于源地址。
IP多播可以分为两种
1. 在局域网中的硬件多播。
- 将MAC地址中的特定地址段作为组播地址，并与IP组播地址形成对应关系。
1. 在Internet中的多播。
- 路由器需支持多播，即多播路由器
- 主机通过IGMP协议与多播路由器通信，加入/退出某个多播组
- 多播路由器之间通过多播路由协议实现多播数据报的传输

4.7 网络地址转换 NAT 和虚拟专用网 VPN

一、网络地址转换 NAT

专用地址(保留地址)
- RFC1918中定义了一系列专用地址(private address)
  1. 10.0.0.0 ～ 10.255.255.255 (CIDR记法: 10/8)
  2. 172.16.0.0 ～ 172.31.255.255 (CIDR记法: 172.16/12)
  3. 192.168.0.0 ～ 192.168.255.255 (CIDR记法: 192.168/16)
- 上面这些地址分别相当于1个A类网络、16个连续的B类网络和256个连续的C类网络，采用这些地址的网络称为专用互联网或本地互联网。
- Internet中的路由器不转发目的地址为专用地址的包
当内部网络使用专用地址时，与Internet的通信需要通过NAT(Network Address Translation)
- NAT路由器至少要有一个全球IP地址，才能和互联网互连。
- NAT路由器内部使用TCP/UDP端口号实现外网数据包向内网地址的转换（详见下一章 - 传输层）。

二、虚拟专用网 VPN

多个企业/机构的内部网络之间互连的实现方法
1. 租用专用线路，形成专用网。这种方法成本高昂，难于承受。
2. 基于公用网络(如Internet)，形成VPN（Virtual Private Network）。
VPN涉及的技术包括：隧道(tunnel)、加密、身份认证等。
基于Internet建立VPN的两种情形
1. 内部网络通过Internet互连
  - 可以采用IPSec的ESP隧道模式
2. 远程用户访问内部网(remote access VPN)
  - 拨号虚拟专用网(VPDN—Virtual Private Dialup Network)
  - 基于SSL的VPN技术，优点：客户端无须安装或配置软件