计算机网络：原理、协议和实践，第三版 第 1 部分：原则 1 连接两台主机

• 连接两台主机
  • 物理层
  • 数据链路层
    • 框架
    • 从传输错误中恢复
    • 在不完美链路之上实现可靠的数据传输
      • 回溯 n 和选择性重复

构建网络（甚至是 Internet 等全球网络）的第一步是将两台主机连接在一起。如下图所示。

将两台主机连接在一起

为了使两台主机能够交换信息，它们需要通过某种物理介质链接在一起。计算机网络已经使用各种类型的物理介质来交换信息，特别是：

• 电缆。信息可以通过不同类型的电缆传输。最常见的是双绞线（用于电话网络，但也用于企业网络）和同轴电缆（仍在有线电视网络中使用，但不再用于企业网络）。某些网络技术通过经典电缆运行。
• 光纤。当通信设备之间的距离大于一公里时，光纤经常用于公共和企业网络。光纤主要有两种类型：多模和单模。多模比单模光纤便宜得多，因为LED可用于通过多模光纤发送信号，而单模光纤必须由激光驱动。由于光的传播模式不同，多模光纤仅限于几公里的距离，而单模光纤可以在几十公里以上的距离上使用。在这两种情况下，中继器都可用于在光纤的一个端点处再生光信号，以通过另一根光纤发送。
• 无线。在这种情况下，无线电信号用于对通信设备之间交换的信息进行编码。许多类型的调制技术用于通过无线信道发送信息，并且该领域每年都有很多创新，并且每年都会出现新技术。虽然大多数无线网络依赖于无线电信号，但有些使用激光将光脉冲发送到远程探测器。这些光学技术允许创建点对点链路，而基于无线电的技术可用于构建包含分布在小地理区域的设备的网络。

一旦这些信息被转换为合适的电信号，这些物理介质就可以用来交换信息。整个电信课程和教科书都致力于将模拟或数字信息转换为电信号的问题，以便可以通过给定的物理链路传输。在本书中，我们只考虑两种非常简单的方案，它们允许通过电缆传输信息。这使我们能够突出通过物理链路传输信息时的关键问题。我们只对允许通过有线传输数字信息的技术感兴趣。在这里，我们将重点介绍位的传输，即0或1。

注意

比特率 (Bit rate)

在计算机网络中，物理层的比特率始终以每秒比特数表示。1 Mbps 是每秒 100 万位，1 Gbps 是 10 亿位/秒。这与通常以字节(bytes)（8 位(bits)）、千字节（1024 字节(bytes)）或兆字节（1048576 字节(bytes)）表示的内存规格形成鲜明对比。通过 1 Mbps 链路传输 1 MByte 可持续 8.39 秒。

Bit rate | Bits per second

1 Kbps | 10^3

1 Mbps | 10^6

1 Gbps | 10^9

1 Tbps | 10^12

为了理解信息物理传输背后的一些原理，让我们考虑一下用于传输位的电线的简单情况。假设两个通信主机想要每秒传输一千位。要传输这些位，两个主机可以就以下规则达成一致：

• 在发送方：
• +5V 在一毫秒内将电线上的电压设置为以传输设置为1的位
• 在一毫秒内将电线上的电压设置-5V为传输位设置为0
• 在接收器侧：
  • 每毫秒，记录施加在电线上的电压。如果电压设置为+5V，记录位1的接收。否则，记录位0的接收

这种传输方案已经在一些早期的网络中使用。我们使用它作为了解主机如何通信的基础。从计算机科学的角度来看，处理电压是不寻常的。计算机科学家经常依赖模型，使他们能够推理他们面临的问题，而无需考虑所有实施细节。上述物理传输方案可以用时序图来表示。

时序图描述了通信主机之间的交互。按照惯例，通信主机在图的左右部分表示，而电气链路位于图的中间。在这样的时序图中，时间从图的顶部流向底部。一位信息的传输由三个箭头表示。从左边开始，第一个水平箭头表示传输一位信息的请求。该请求由可以被视为一种过程调用的原语表示。该原语有一个参数（被传输的位）和一个名称（在本例中为DATA.request）。按照惯例，所有被命名的原语something.request对应于传输一些信息的请求。虚线箭头表示相应电信号在导线上的传输。电和光信号不会瞬间传播。对角虚线箭头表示电信号从主机 A传输到主机 B需要一些时间。接收到电信号后，主机 B的网络接口上的电子设备会检测电压并将其转换为位。该位作为DATA.indication原语提供。所有名为something.indication的原语对应于一些信息的接收。虚线还表示两个（或多个）基元之间的关系。这样的时序图提供了有关不同基元排序的信息，但两个基元之间的距离并不代表精确的时间量。

当试图理解给定通信方案的特征时，时序图很有用。在考虑上述传输方案时，评估该方案是否允许两个通信主机可靠地交换信息是有用的。当主机传输的位序列在线路的另一端被正确接收时，数字传输被认为是可靠的。在实践中，使用上述方案传输信息时很难实现完美的可靠性。这种传输方案可能会出现几个问题。

第一个问题是电传输会受到电磁干扰的影响。干扰可能有多种来源，包括自然现象（如雷暴、磁场变化……）以及其他电信号（例如来自相邻电缆的干扰、来自相邻天线的干扰……）。由于这些不同类型的干扰，不幸的是，无法保证当主机在线传输一个比特时，另一端会接收到相同的比特。如下图所示，左侧主机上的DATA.request(0)导致右侧主机上的Data.indication(1)。

使用上述传输方案，通过在一段时间内将电缆上的电压设置为特定值来传输比特。我们已经看到，由于电磁干扰，接收器测量的电压可能与发射器设置的电压不同。这是传输错误的主要原因。但是，这不是唯一可能发生的问题类型。除了定义位0和1的电压，上述传输方案还规定了每个比特的持续时间。如果每秒发送一百万位，则每个位持续 1 微秒。在每个主机上，每个位的传输（或接收）由具有 1 MHz 频率的本地时钟触发。当通过线路传输位时，这些时钟是第二个问题来源。尽管这两个时钟具有相同的规格，但它们在不同的主机上运行，可能在不同的温度和不同的能源下运行。在实践中，两个时钟可能不会以完全相同的频率运行。假设发送主机的时钟正好工作在 1000000 Hz，而接收时钟工作在 999999 Hz。这是两个时钟之间的一个非常小的差异。然而，当使用时钟传输比特时，这种差异很重要。凭借其 1000000 Hz 的时钟，发送主机将在一秒钟内生成一百万位。在同一时期，接收主机将感应线路 999999 次，因此接收到的比特比最初传输的比特少。时钟频率的这种微小差异意味着位在电缆上传输期间可能会“消失”。如下图所示。

当发送主机的时钟比接收主机的时钟慢时，类似的推理也适用。在这种情况下，接收方将感知到比发送方已发送的比特更多的比特。下图说明了这一点，其中右侧接收到的第二个位未由左侧主机发送。

从计算机科学的角度来看，通过电线进行的信息物理传输通常被认为是一个允许传输比特的黑匣子。这个黑匣子通常被称为物理层服务，使用前面介绍的DATA.request和DATA.indication原语来表示。这种物理层服务通过将比特实际传输中涉及的技术细节抽象为电磁信号来促进比特的发送和接收。但是，重要的是要记住，物理层服务是不完善的，具有以下特点：

• 物理层服务可能会改变，例如由于电磁干扰，正在传输的比特的值
• 物理层服务向接收方传递的比特可能比发送方发送的比特多
• 物理层服务向接收方传递的比特可能比发送方发送的比特少

许多其他类型的编码已被定义为通过电缆传输信息。所有物理层都能够发送和接收表示值0和1的物理符号。然而，由于本章范围之外的各种原因，几个物理层也交换了其他物理符号。例如，多个物理层中使用的曼彻斯特编码可以发送四个不同的符号。曼彻斯特编码是一种差分编码方案，其中时间被划分为固定长度的周期。每个周期分为两半，可以施加两个不同的电压电平。要发送符号，发送者必须在每个半周期内设置这两个电压电平之一。发送一个1 (resp. 0)，发送方必须在周期的前半段设置高（或低）电压，在后半段设置低（或高）电压。这种编码确保在每个周期的中间会有一个转换，并允许接收者将其时钟与发送者的时钟同步。除了0和1的编码，曼彻斯特编码还支持两个附加符号：InvH和InvB ，其中两个半周期使用相同的电压电平。根据定义，这两个符号不能出现在仅由0和1组成的框架内。一些技术使用这些特殊符号作为帧开始或结束的标记。

曼彻斯特编码

物理层

与通过有线（或无线链路）进行物理传输或信息有关的所有功能通常称为物理层. 因此，物理层允许直接连接到同一传输介质的两个或多个实体交换比特。能够交换比特很重要，因为实际上任何信息都可以编码为比特序列。电气工程师习惯于处理比特流，但计算机科学家通常更喜欢处理更高层次的概念。文件存储也会出现类似的问题。诸如硬盘之类的存储设备也存储比特流。有一些硬件设备可以处理硬盘产生的比特流，但是计算机科学家已经设计了文件系统来允许应用程序轻松访问这些存储设备。这些文件系统通常也分为几层。硬盘存储 512 字节或更多的扇区。Unix 文件系统将扇区分组为更大的块，这些块可以包含数据或表示文件系统结构的inode 。最后，应用程序操作文件和目录，这些文件和目录由操作系统以块、扇区和最终位的形式进行转换。

计算机网络使用类似的方法。每一层都提供了一个构建在底层之上的服务，并且更接近应用程序的需求。数据链路层建立在物理层提供的服务之上。我们将看到它还包含几个功能。

• 从计算机科学的角度来看，通过电线进行的信息物理传输通常被认为是一个允许传输比特的黑匣子。这个黑匣子通常被称为物理层服务
• 与通过有线（或无线链路）进行物理传输或信息有关的所有功能通常称为物理层

计算机科学家通常对在两个主机之间交换位不感兴趣。他们更喜欢编写处理更大数据块的软件，以便传输消息或完整的文件。由于物理层服务，可以在两台主机之间发送连续的比特流。这个比特流可以包含逻辑数据块，但我们需要能够从比特流中提取每个数据块，尽管物理层存在缺陷。在许多网络中，两个直接连接的主机之间交换信息的基本单位通常称为帧。帧可以定义为具有特定语法或结构的位序列。我们将在本章后面看到此类框架的示例。

为了实现帧的发送/接收，首先要解决的问题是如何将帧编码为比特序列，以便接收器可以轻松地恢复接收到的帧，而不受物理层的限制。

如果物理层是完美的，问题就很简单了。我们只需要定义如何将每个帧编码为一系列连续位。然后，接收器将能够轻松地从接收到的位中提取帧。不幸的是，物理层的缺陷使这个成帧问题稍微复杂一些。已经提出了几种解决方案，并在不同的网络技术中实际使用。

• 数据链路层建立在物理层提供的服务之上
• 两个直接连接的主机之间交换信息的基本单位通常称为帧。帧可以定义为具有特定语法或结构的位序列。
• 成帧问题可以定义为：“发送方如何对帧进行编码，以便接收方可以有效地从它从物理层接收到的比特流中提取它们”。
• 一个运行在物理层服务之上的可靠数据链路协议。
• 数据链路层旨在代表用户发送和接收帧
• 除了成帧之外，数据链路层还包括检测传输错误，有时甚至从传输错误中恢复的机制。

成帧问题可以定义为：“发送方如何对帧进行编码，以便接收方可以有效地从它从物理层接收到的比特流中提取它们”。

这个问题的第一个解决方案是要求物理层在每帧传输后保持空闲一段时间。这些空闲时段可以被接收器检测到，并用作描绘帧边界的标记。不幸的是，由于两个原因，这种解决方案是不可接受的。首先，一些物理层不能保持空闲并且总是需要传输比特。其次，在帧之间插入空闲周期会降低可以达到的最大比特率。

笔记

比特率和带宽

比特率和带宽经常被用来表征物理服务的传输能力。韦伯斯特词典中列出的带宽的原始定义是由调制载波占用的无线电频率范围，分配给服务或设备可以在其上运行。该定义对应于给定传输介质或接收器的特性。例如，人耳能够解码大约 0-20 KHz 频率范围内的声音。通过扩展，带宽也用于表示通信系统的容量，以比特/秒为单位。例如，千兆以太网链路理论上能够每秒传输 10 亿比特。

鉴于不能由所有物理层使用多符号编码，因此需要一种通用解决方案，该解决方案可以与任何能够仅发送和接收比特 0 和 1 的物理层一起使用。这种通用解决方案称为填充，存在两种变体：位填充和字符填充。为了使接收器能够轻松描绘帧边界，这两种技术保留特殊位串作为帧边界标记并对帧进行编码，使这些特殊位串不会出现在帧内。

位填充保留 01111110 位串作为帧边界标记，确保一个帧内永远不会有六个连续的1符号由物理层传输。使用比特填充，帧被发送如下。首先，发送者发送标记，即 01111110。然后，它发送帧的所有位，并在每个连续五个1位的序列之后插入一个设置为0的附加位。这确保了发送的帧永远不会包含设置为1的六个连续位的序列. 因此，标记图案不能出现在发送的帧内。标记也被发送以标记帧的结束。接收器执行相反的操作来解码接收到的帧。由于 01111110 标记，它首先检测到帧的开始。然后，它处理接收到的位并计算设置为1的连续位的数量。如果0跟在设置为1的五个连续位之后，则该位被删除，因为它是由发送者插入的。如果1后面有五个连续的位设置为1，则如果它后面跟着一个设置为0的位，则表示标记。下表说明了位填充对某些帧的应用。

例如，考虑 0110111111111111111110010 的传输。发送者将首先发送 01111110 标记，然后发送 011011111。在这五个连续的位设置为 1 之后，它插入一个设置为0的位，后跟 11111 。插入一个新的 0，然后是 11111 。插入一个新的 0，然后是帧110010的结尾和 01111110 标记。

• 分析一下表格第二行的传输帧：
• 原文：0110111111111111111110010
• 传输帧：01111110011011111011111011111011001001111110
• 传输帧2：01111110 0110111110111110111110110010 01111110
• 传输帧3：01111110 011011111 0111110111110110010 01111110
• 传输帧4：01111110 011011111 0 111110111110110010 01111110
• 传输帧5：01111110 011011111 0 11111 0 111110110010 01111110
• 传输帧6：01111110 011011111 0 11111 0 11111 0 110010 01111110
• 在每个连续五个 1 位的序列之后插入一个设置为 0 的附加位。这确保了发送的帧永远不会包含设置为1的六个连续位的序列

位填充增加了传输每帧所需的位数。位填充的最坏情况当然是在帧内将一长串位设置为1 。如果发生传输错误，填充位或标记可能出错。在这些情况下，受错误影响的帧和可能的下一帧将不会被接收器正确解码，但它能够在下一个有效标记处重新同步自身。

位填充可以很容易地在硬件中实现。然而，鉴于在软件中执行位操作的复杂性，在软件中实现它是困难的。软件实现更喜欢处理字符而不是位，基于软件的数据链路层通常使用字符填充。该技术适用于包含整数个字符的帧。在计算机网络中，字符通常依靠 ASCII 表进行编码。该表将各种字母数字字符的编码定义为位序列。RFC 20提供了 Internet 上许多协议使用的 ASCII 表。例如，该表定义了以下二进制表示：

• A : 1000011 b
• 0 : 0110000 b
• z : 1111010 b
• @ : 1000000 b
• space : 0100000 b

此外，ASCII 表还定义了几个不可打印或控制字符。这些字符旨在允许应用程序控制打印机或终端。这些控制字符包括用于终止行的 CR 和 LF 以及使终端发出声音的 BEL 字符。

• NUL: 0000000 b
• BEL: 0000111 b
• CR : 0001101 b
• LF : 0001010 b
• DLE: 0010000 b
• STX: 0000010 b
• ETX: 0000011 b

一些字符用作标记来描绘帧边界。许多字符填充技术使用 ASCII 字符集的 DLE、STX 和 ETX 字符。DLE STX (resp. DLE ETX ) 用于标记帧的开始（结束）。发送帧时，发送方在每个发送的 DLE 字符后添加一个DLE字符。这确保没有任何标记出现在传输的帧内。接收器在接收到两个连续的DLE字符时检测帧边界并移除第二个DLE 。例如，传输帧1 2 3 DLE STX 4，发送者将首先发送DLE STX作为标记，然后发送1 2 3 DLE。然后，发送方发送一个附加的DLE字符，后跟STX 4和DLE ETX标记。

字符填充与位填充一样，会增加传输帧的长度。对于字符填充，最差帧是包含许多DLE字符的帧。当发生传输错误时，接收器可能会错误地解码一帧或两帧（例如，如果错误出现在标记中）。但是，它将能够与下一个正确接收的标记重新同步。

位填充和字符填充允许从位或字节流中恢复帧。这种成帧机制提供了比物理层更丰富的服务。通过成帧服务，可以发送和接收完整的帧。这个成帧服务也可以通过使用DATA.request和DATA.indication原语来表示。下图说明了这一点，假设假设帧包含四个有用位和一个帧，出于图形原因。

我们现在可以在成帧机制的基础上允许主机交换包含整数位或字节的帧。一旦解决了成帧问题，我们就可以专注于设计一种允许可靠地交换帧的技术。

在本节中，我们开发了一个运行在物理层服务之上的可靠数据链路协议。为了设计这个协议，我们首先假设物理层提供了完善的服务。然后，我们将开发解决方案以从传输错误中恢复。

数据链路层旨在代表用户发送和接收帧。我们使用 DATA.req 和 DATA.ind 原语对这些交互进行建模。然而，为了简化表示并避免数据链路层实体的用户发布的 DATA.req 原语与数据链路层实体本身发布的 DATA.req 之间的混淆，我们将使用以下术语：

• 用户和数据链路层实体之间的交互使用经典的 DATA.req 和 DATA.ind 原语表示
• 数据链路层实体和成帧子层之间的交互使用 send 代替 DATA.req 和 recvd 代替 DATA.ind 来表示

当在完美的成帧子层之上运行时，数据链路实体可以在DATA.req(SDU)[1] 到达时简单地发出 send(SDU)。类似地，接收器在收到 recvd(SDU) 时发出 DATA.ind(SDU)。当发送单个 SDU 时，这样一个简单的协议就足够了。如下图所示

不幸的是，这并不总是足以确保 SDU 的可靠交付。考虑客户端向服务器发送数十个 SDU 的情况。如果服务器比客户端快，它将能够接收和处理客户端发送的所有帧并将其内容传递给其用户。但是，如果服务器比客户端慢，则可能会出现问题。数据链路实体包含用于存储已作为 Data.request 接收的 SDU 的缓冲区但尚未发送。如果应用程序比物理链路快，则缓冲区可能已满。此时，操作系统暂停应用程序，让数据链路实体清空其传输队列。数据链路实体还使用缓冲区来存储接收到的尚未由应用程序处理的帧。如果应用程序处理数据的速度很慢，这个缓冲区可能会溢出，数据链路实体将无法接受任何额外的帧。数据链路实体的缓冲区大小有限，如果溢出，到达的帧将被丢弃，即使它们是正确的。

为了解决这个问题，一个可靠的协议必须包括一个反馈机制，允许接收者通知发送者它已经处理了一个帧并且可以发送另一个帧。即使没有传输错误，也需要此反馈。为了包含这样的反馈，我们可靠的协议必须处理两种类型的帧：

• 携带 SDU 的数据帧
• 带有确认的控制帧，表明之前的帧已被正确处理

这两种类型的帧可以通过将帧分为两部分来区分：

• 包含一位在数据帧中设置为0并在控制帧中设置为1的标头
• 包含应用程序提供的 SDU 的有效负载

然后可以将数据链路实体建模为有限状态机，其中包含接收器的两个状态和发送器的两个状态。下图提供了这个状态机的图形表示，上面是发送者，下面是接收者。

最简单可靠协议的有限状态机（发送者在上面，接收者在下面）

上面的 FSM 表明发送方必须等待接收方的确认才能发送下一个 SDU。下图说明了两台主机之间的几个帧的交换。

笔记

服务和协议

在学习计算机网络之前要了解的一个重要方面是服务和协议之间的区别. 为此，从现实世界的例子开始很有用。传统的 Post 提供一种邮递员向收件人投递信件的服务。The Post 精确定义了使用标准邮件服务可以递送哪些类型的信件（大小、重量等）。此外，还指定了信封的格式（发件人和收件人地址的位置、邮票的位置）。想要寄信的人必须将信件放在邮局或其中一个专用邮箱内。然后将收集这封信并将其交付给最终收件人。请注意，对于常规服务，邮政通常不保证每封特定信件的递送。有些信件可能会丢失，有些信件会被送错邮箱。如果一封信很重要，然后发件人可以使用注册的服务来确保信件将交付给收件人。一些邮政服务还提供比常规服务更快的确认服务或特快专递服务。

数据链路层必须处理传输错误。在实践中，我们主要要处理数据链路层的两类错误：

• 帧可能因传输错误而损坏
• 可能会丢失帧或出现意外帧

乍一看，在单个链接上丢失帧可能看起来很奇怪。但是，如果我们考虑成帧，传输错误会影响帧描述机制，使帧不可读。出于同样的原因，在发送者发送一个帧之后，接收者可能会收到两个（可能是无效的）帧。

为了处理这些类型的缺陷，可靠的协议依赖于不同类型的机制。第一个问题是传输错误。物理链路上的数据传输可能会受到以下错误的影响：

• 由于传输错误而修改了单个位的值的随机隔离错误
• 随机突发错误，其中n个连续位的值由于传输错误而改变
• 由于传输错误而添加或删除位的，随机位创建和随机位删除

防止传输错误的唯一解决方案是向发送的帧添加冗余。信息论定义了两种机制，可用于在受随机错误影响的传输通道上传输信息。这两种机制为传输的信息添加了冗余，以允许接收器检测或有时甚至纠正传输错误。对这些机制的详细讨论超出了本章的范围，但考虑一个简单的机制来理解其操作及其局限性是有用的。

信息论定义了编码方案。有不同类型的编码方案，但让我们专注于对二进制字符串进行操作的编码方案。编码方案是将编码为m位字符串的信息映射到n位字符串的函数。最简单的编码方案是（偶）奇偶编码。此编码方案采用m位源字符串并生成m+1位编码字符串，其中编码字符串的前m位是源字符串的位，并且选择编码字符串的最后一位，以便编码字符串将始终包含设置为 1 的偶数位。例如 ：

• 1001编码为10010
• 1101编码为11011

这种奇偶校验方案已用于某些 RAM 以及对通过串行线路发送的字符进行编码。很容易表明，这种编码方案允许接收器检测到单个传输错误，但无法纠正它。然而，如果两个或更多位出错，接收器可能并不总是能够检测到错误。

一些编码方案允许接收器纠正一些传输错误。例如，考虑如下编码每个源比特的编码方案：

• 1编码为111
• 0编码为000

例如，考虑发送 111 的发件人。如果有一位错误，接收器可能会收到 011 或 101 或110 。在这三种情况下，接收器会将接收到的位模式解码为1 ，因为它包含设置为1的大多数位。如果有两位错误，接收器将无法再从传输错误中恢复。

这种简单的编码方案强制发送方为每个源比特传输三个比特。但是，它允许接收器纠正单位错误。允许从错误中恢复的更高级的编码系统用于多种类型的物理层。

除了成帧之外，数据链路层还包括检测传输错误，有时甚至从传输错误中恢复的机制。为了让接收方注意到传输错误，发送方必须在发送的帧中添加一些冗余信息作为错误检测代码。此错误检测代码由发送方在其传输的帧上计算。当接收器接收到带有错误检测码的帧时，它会重新计算它并验证接收到的错误检测码是否与计算出的错误检测码匹配. 如果它们匹配，则认为该帧是有效的。存在许多错误检测方案，并且已经就该主题编写了整本书。对这些技术的详细讨论超出了本书的范围，我们将仅讨论一些示例来说明关键原则。

为了理解错误检测代码，让我们考虑两个交换包含N位的位串的设备。为了让接收方检测传输错误，发送方将每个N位串转换为N+r位串。通常，r个冗余位被添加在传输位串的开头或结尾，但有些技术将冗余位与原始位交织在一起。错误检测代码可以定义为一个函数，它计算对应于每个 N 字符串的r个冗余位位。最简单的错误检测代码是奇偶校验位。有两种奇偶校验方案：偶校验和奇校验。使用偶数（或奇数）奇偶校验方案，选择冗余位，以便在发送的N+r位的位串中将偶数（或奇数）位设置为1。接收器可以轻松地重新计算每个接收到的比特串的奇偶校验，并丢弃具有无效奇偶校验的字符串。交换 7 位字符时经常使用奇偶校验方案。在这种情况下，第八位通常是奇偶校验位。下表显示了为包含三位的位串计算的奇偶校验位。

奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。 假设存储的数据用位标示为1、1、1、0、0、1、0、1，那么把每个位相加（1+1+1+0+0+1+0+1=5），结果是奇数。对于偶校验，校验位就定义为1；对于奇校验，则相反。

观察上面示例：

1 出现 偶数次时，奇校验指是 1

1 出现 奇数次时，奇校验指是 0

奇偶校验位允许接收器检测已发送的N+r位中的单个位的传输错误。如果有两个或更多位错误，则接收器可能不一定能够检测到传输错误。已经定义了更强大的错误检测方案。循环冗余校验 (CRC) 广泛用于数据链路层协议。N 位 CRC 可以检测影响传输帧中少于 N 位的突发的所有传输错误以及影响奇数位的所有传输错误。更多关于 CRC 的细节可以在Williams1993中找到。

还可以设计一种代码，允许接收器纠正传输错误。最简单的纠错码是三重模冗余（TMR）。为了发送设置为1的位（对应0），发送方发送111（对应000）。当没有传输错误时，接收器可以将111解码为1。如果传输错误影响了单个位，则接收器执行多数表决，如下表所示。该方案允许接收器纠正影响单个比特的所有传输错误。

已经提出了其他更强大的纠错码并在某些应用中使用。汉明码是奇偶校验位的巧妙组合，可提供错误检测和纠正功能。

可靠协议使用错误检测方案，但广泛使用的可靠协议都不依赖纠错方案。为了检测错误，帧通常分为两部分：

• 包含可靠协议使用的字段以确保可靠传递的标头。标头包含校验和或循环冗余校验 (CRC) [Williams1993]，用于检测传输错误
• 包含用户数据的有效负载

一些报头还包括一个长度字段，它指示帧的总长度或有效载荷的长度。

最简单的错误检测方案是校验和。校验和基本上是组成帧的所有字节的算术和。有不同类型的校验和。例如，可以将八位校验和计算为帧（头和尾）所有字节的算术和。校验和由发送方在发送帧之前计算，接收方在接收帧时验证校验和。接收器丢弃接收到的带有无效校验和的帧。校验和可以很容易地在软件中实现，但它们的错误检测能力是有限的。循环冗余校验 (CRC) 具有更好的错误检测能力[SGP98]，但在软件中实现时需要更多 CPU。

笔记

校验和，CRC，…

TCP/IP 协议族中的大多数协议都依赖于简单的 Internet 校验和，以验证接收到的数据包没有受到传输错误的影响。尽管 Internet 校验和很受欢迎且易于实施，但它并不是唯一可用的校验和机制。循环冗余校验 ( CRC ) 是非常强大的错误检测方案，主要用于磁盘、许多数据链路层协议和文件格式（例如zip或png. 它们可以很容易地在硬件中有效地实现，并且比 Internet 校验和具有更好的错误检测能力[SGP98]. 然而，CRC 有时被认为对于软件实现来说 CPU 过于密集，因此首选其他校验和机制。TCP/IP 社区选择了 Internet 校验和，OSI 社区选择了 Fletcher 校验和[Sklower89]。现在有有效的技术可以在软件中快速计算 CRC [Feldmeier95]。

由于接收方在收到每个数据帧后都会发送确认，因此处理丢失的最简单解决方案是使用重传计时器。当发送者发送一个帧时，它会启动一个重传定时器。这个重传定时器的值应该大于往返时间，即数据帧的传输和相应确认的接收之间的延迟。当重传定时器超时时，发送方认为数据帧已经丢失并重传。如下图所示。

不幸的是，仅重传定时器不足以从丢失中恢复。作为一个例子，让我们考虑下面描述的确认丢失的情况。在这种情况下，发送方重新发送尚未确认的数据帧。但是，如下图所示，接收方将重传视为必须将其有效载荷传递给其用户的新帧。

为了解决这个问题，数据链路协议将序列号关联到每个数据帧。该序列号是数据帧头中的字段之一。我们使用符号D(x,…)来表示序列号字段设置为值x的数据帧。确认还包含一个序列号，指示它正在确认的数据帧。我们使用OKx来表示确认接收到D(x,…)的确认帧。序列号被编码为固定长度的位串。最简单可靠的协议是交替比特协议 (ABP)。

交替位协议使用单个位来编码序列号。它可以很容易地实现。发送者（分别是接收者）只需要一个四态（分别是三态）有限状态机。

交替位协议：发送方 FSM

发送者的初始状态是等待 D(0,…)。在这种状态下，发送者等待Data.request。它发送的第一个数据帧使用序列号0。发送此帧后，发送方等待OK0确认。在重传定时器到期或收到带有不正确序列号的确认时重传帧。

接收者首先等待D(0,…)。如果帧包含正确的CRC，它将 SDU 传递给它的用户并发送OK0。如果帧包含无效的 CRC，则立即丢弃。然后，接收方等待D(1,…)。在这种状态下，它可能会收到一个重复的D(0,…)或带有无效 CRC 的数据帧。在这两种情况下，它都会返回一个OK0帧，以允许发送方从可能丢失的前一个OK0帧中恢复。

交替位协议：接收器 FSM

笔记

处理损坏的帧

交替比特协议的接收器 FSM 丢弃所有包含无效 CRC 的帧。这是最安全的方法，因为接收到的帧可能与远程主机发送的帧完全不同。接收器不应尝试从损坏的帧中提取信息，因为它无法知道帧的哪个部分已受到错误的影响。

下图说明了交替位协议的操作。

交替位协议可以从数据或控制帧的丢失中恢复。这在下面的两个图中进行了说明。第一个图显示了一个数据帧的丢失。

第二个图说明了主机如何处理一个控制帧的丢失。

交替位协议可以从传输错误和帧丢失中恢复。然而，它有一个重要的缺点。考虑通过具有 250 毫秒传播延迟的 50 Kbits/sec 卫星链路直接连接的两台主机。如果这些主机发送 1000 比特帧，那么交替比特协议可以实现的最大吞吐量是每帧一帧。20 + 250 + 250 = 520 如果我们忽略确认的传输时间，则为毫秒。这小于 2 Kbits/sec ！

为了克服交替比特协议的性能限制，可靠的协议依赖于流水线。这种技术允许发送方发送几个连续的帧，而不必在每个帧之后等待确认。每个数据帧都包含一个编码为n位字段的序列号。

流水线允许发送方以更高的速率传输帧。然而，这种较高的传输速率可能会使接收器过载。在这种情况下，发送方发送的帧将不会被其最终目的地正确接收。依赖于流水线的可靠协议允许发送方在被迫等待接收实体的确认之前传输W个未确认的帧。

这是通过使用滑动窗口来实现的。滑动窗口是发送方在发送帧时可以使用的一组连续序列号，而无需强制等待确认。下图显示了一个包含五个帧（6、7、8、9和10）的滑动窗口。这些序列号中的两个（6和7）已用于发送帧，只有三个序列号（8、9和10 ）保留在滑动窗口中。一旦包含在滑动窗口中的所有序列号都已被使用，则称滑动窗口关闭。

下图说明了滑动窗口的操作。它使用三个框架的滑动窗口。因此，发送者可以在被迫等待确认之前发送三个帧。滑动窗口在收到每个确认后移动到更高的序列号。当收到第一个确认 ( OK0 ) 时，它使发送方能够将其滑动窗口向右移动，并且序列号3变为可用。此序列号稍后用于传输包含d的帧。

实际上，由于帧头包含一个n位字段来编码序列号，因此只有0 和2^n - 1 可以使用。这意味着，在长传输期间，相同的序列号将用于不同的帧，并且滑动窗口将换行。下图说明了这一点，假设使用2位对帧头中的序列号进行编码。请注意，在收到 OK1后，发送方会滑动其窗口并可以再次使用序列号0。

不幸的是，帧丢失并没有消失，因为可靠的协议使用滑动窗口。为了从损失中恢复，滑动窗口协议必须定义：

• 检测帧丢失的启发式方法
• 重传丢失帧的重传策略

最简单的滑动窗口协议使用go-back-n恢复。直观地说，go-back-n 的操作如下。go-back-n接收器尽可能简单。它只接受按顺序到达的帧。go-back-n接收器丢弃它接收到的任何无序帧。当go-back-n接收到一个数据帧时，它总是返回一个确认，其中包含它接收到的最后一个有序帧的序列号。据说这种确认是累积的。当一个go-back-n接收器发送一个对序列号x的确认时，它隐式地确认所有序列号早于x的帧的接收。这些累积确认的一个关键优势是很容易从确认丢失中恢复。例如，考虑接收帧1、2和3的返回 n接收器。它发送了OK1、OK2和OK3。不幸的是，OK1和OK2丢失了。由于累积确认，当发送方收到OK3时，它知道所有三个帧都已正确接收。

下图显示了一个简单的go-back-n接收器的 FSM。该接收器使用两个变量：lastack和next。next是下一个预期的序列号，而lastack是已确认的最后一个数据帧的序列号。接收方只接受按顺序接收的帧。maxseq是不同序列号的数量（）。

go-back-n 发件人也很简单。它使用可以存储帧的整个滑动窗口的发送缓冲区[2]。帧以递增的序列号（模maxseq）发送。一旦发送缓冲区已满，发送者必须等待确认。当go-back-n发送方接收到确认时，它会从发送缓冲区中删除所有确认的帧，并使用重传计时器来检测帧丢失。一个简单的 go-back-n发送者为每个连接维护一个重传计时器。该定时器在发送第一帧时启动。当go-back-n 发件人收到确认后，仅当其发送缓冲区中仍有未确认的帧时，它才重新启动重传计时器。当重传计时器到期时，返回-n发送方假定当前存储在其发送缓冲区中的所有未确认帧都已丢失。因此，它重传缓冲区中所有未确认的帧并重新启动其重传计时器。

go-back-n 的操作如下图所示。在该图中，请注意，在接收到失序帧D(2,c)时，接收器返回一个累积确认C(OK,0)，它确认已按顺序接收到的所有帧。丢失的帧在重传定时器到期时被重传。

go-back-n 的主要优点是可以很容易地实现，并且在只有几帧丢失的情况下也能提供很好的性能。但是，当损失很多时，go-back-n 的性能会迅速下降，原因有两个：

• go-back-n 接收器不接受乱序帧
• go-back-n 发送方在检测到丢失后重新传输所有未确认的帧

选择性重复是从损失中恢复的更好策略。直观地说，选择性重复允许接收器接受失序帧。此外，当选择性重复发送端检测到丢失时，它只重传已经丢失的帧，而不重传已经正确接收的帧。

选择性重复接收器维护W帧的滑动窗口，并将其接收到的无序帧存储在缓冲区中。下图显示了已经接收到帧7和9的接收器上的五帧接收窗口。

选择性重复接收器丢弃所有具有无效 CRC 的帧，并保持变量 lastack 作为它接收到的最后一个按序帧的序列号。接收方总是在它发送的确认中包含 lastack 的值。一些协议还允许选择性重复接收器确认它已接收到的失序帧。例如，这可以通过将正确接收但无序帧的列表与 lastack 值一起放在确认中来完成。

选择性重复接收端接收到数据帧时，首先验证数据帧是否在其接收窗口内。 如果是，则将帧放入接收缓冲区。如果不是，则丢弃接收到的帧，并向发送方发送包含 lastack 的确认。然后，接收器从接收缓冲区中删除从 lastack 开始的所有连续帧（如果有的话）。这些帧的有效载荷被传递给用户，更新 lastack 和接收窗口，并发送确认按顺序接收到的最后一个帧的确认。

选择性重复发送器维护一个发送缓冲区，最多可以存储W个未确认的帧。只要发送缓冲区未满，就会发送这些帧。选择性重复发送器的几种实现方式是可能的。一个简单的实现将一个重传定时器与每一帧相关联。发送帧时启动定时器，并在接收到覆盖该帧的确认时取消定时器。当重传定时器超时时，相应的帧被重传并且这个重传定时器被重新启动。当接收到确认时，所有被此确认覆盖的帧都从发送缓冲区中删除，并更新滑动窗口。

下图说明了丢帧时选择性重复的操作。在该图中，C(OK,x)用于指示所有帧，包括序列号x都已正确接收。

纯累积确认适用于go-back-n策略。然而，仅通过累积确认，选择性重复发送方无法轻易确定在数据帧丢失后哪些帧已正确接收。例如，在上图中，第二个C(OK,0)没有明确通知发送方接收到D(2,c)，发送方可以重新发送该帧，尽管它已经收到。提高选择性重复性能的可能解决方案是在接收方返回的确认中提供有关接收到的帧的附加信息。例如，接收方可以在返回的确认中添加已经接收到的所有帧的序列号列表。这种确认有时称为选择性确认。如上图所示。

在上图中，当发送方接收到C(OK,0,[2])时，它知道直到并包括D(0,…)的所有帧都已正确接收。它还知道已经接收到帧D(2,…) ，并且可以取消与该帧关联的重传计时器。但是，在接收到覆盖该帧的累积确认（上图中的C(OK,2)）之前，不应从发送缓冲区中删除该帧。

笔记

go-back-n 和选择性重复的最大窗口大小

使用 n 位对其序列号进行编码的可靠协议最多可以发送 2^n 连续的帧。但是，为了确保可靠地传递帧，返回 n 和选择性重复不能使用发送窗口 2^n 帧。首先考虑 go-back-n 并假设发送者发送 2^n 帧。这些帧由目的地按顺序接收，但所有返回的确认都丢失了。发送方将重新传输所有帧。这些帧都将被接收者接受并再次发送给用户。很容易看出，如果发送窗口的最大尺寸为 2^n - 1 帧。选择性重复也会出现类似的问题。然而，当接收方接受失序帧时，发送窗口为 2^n - 1 帧不足以确保可靠的交付。很容易证明，为了避免这个问题，选择性重复发送者不能使用大于 2^n / 2 帧。

可靠的协议通常需要双向发送数据。为了减少由确认引起的开销，大多数可靠的协议都使用捎带。多亏了这种技术，数据链路实体可以将它为数据流的相反方向通告的确认和接收窗口放置在它发送的数据帧的标头内。捎带的主要优点是它减少了开销，因为不需要发送完整的帧来携带确认。下图说明了这一点，其中确认号在数据帧中带有下划线。仅当数据双向流动时才使用捎带。如图底部所示，当接收方不向相反方向发送数据时，接收方将生成纯确认。

[1] SDU 是服务数据单元的首字母缩写。我们用它作为一个通用术语来表示协议传输的数据。

[2] 对于给定的协议，滑动窗口的大小可以是固定的，也可以在连接建立阶段协商。一些协议允许在数据传输期间更改最大窗口大小。稍后我们将使用真实的协议来解释这些技术。