计算机网络学习笔记-3.1链路层-差错控制和传输协议

差错控制

在数据传输和存储过程中，数据可能会受到噪声或其他因素的干扰而发生错误。为了保证数据的可靠性，使用了各种纠错编码和检错编码技术。

纠错编码（Error Correction Codes）

纠错编码是一种通过在数据中添加冗余信息，使接收端不仅能够检测到数据错误，还可以自动纠正错误的编码方式。其目的是提高数据传输和存储的可靠性，使得即使在发生错误的情况下，数据也能够被恢复。

海明码（Hamming Code）

海明码（Hamming Code）是一种用于错误检测和纠正的编码方式。它通过添加冗余的校验位（parity bits）来实现对数据位的错误检测与纠正，能够有效地检测并纠正单比特错误。

海明码的基本原理

海明码的核心思想是，在数据中添加校验位，使得这些校验位能够覆盖不同的数据位。通过这些校验位，可以检测和纠正最多一个错误（即单比特错误）。为了实现这一点，海明码采用了一种特殊的方式来布置校验位，确保每个校验位检查特定的比特位置。流程根本看不懂，直接看过程。

示例

假设我们需要发送一个 4 位的数据：1011。我们可以使用海明码来进行编码，步骤如下：

1. 确定校验位的位置：我们需要3个校验位，数据位位置如下：

   • 位置 1：校验位 p 1 p_1 p1​
   • 位置 2：校验位 p 2 p_2 p2​
   • 位置 3：数据位 d 1 d_1 d1​
   • 位置 4：校验位 p 3 p_3 p3​
   • 位置 5：数据位 d 2 d_2 d2​
   • 位置 6：数据位 d 3 d_3 d3​
   • 位置 7：数据位 d 4 d_4 d4​

   所以，码字的格式是：p_1 p_2 d_1 p_3 d_2 d_3 d_4

2. 计算校验位的值：根据上面的规则：

   • 对于 p 1 p_1 p1​，它检查位置 1、3、5、7，所以 p 1 p_1 p1​ 应该使得这些位置的比特的奇偶性为偶数。
   • 对于 p 2 p_2 p2​，它检查位置 2、3、6、7，所以 p 2 p_2 p2​ 应该使得这些位置的比特的奇偶性为偶数。
   • 对于 p 3 p_3 p3​，它检查位置 4、5、6、7，所以 p 3 p_3 p3​ 应该使得这些位置的比特的奇偶性为偶数。

3. 计算结果：

   • 给定数据：1011
   • 填入数据：p_1 p_2 1 p_3 0 1 1
   • 根据规则计算校验位：
     • p 1 p_1 p1​ 需要使得位置 1、3、5、7 的比特总和为偶数：此时 p 1 = 0 p_1 = 0 p1​=0
     • p 2 p_2 p2​ 需要使得位置 2、3、6、7 的比特总和为偶数：此时 p 2 = 1 p_2 = 1 p2​=1
     • p 3 p_3 p3​ 需要使得位置 4、5、6、7 的比特总和为偶数：此时 p 3 = 0 p_3 = 0 p3​=0

   因此，最终编码结果是：0110101。

错误检测和纠正

当接收端接收到带有海明码的码字时，接收端会通过重新计算校验位来验证数据。如果校验位的计算结果不为零，说明发生了错误。

1. 如果错误位的校验位值不为零，接收端可以确定出错误位的位置。
2. 然后，接收端只需要翻转这个位置的比特，就能纠正单比特错误。

检错编码（Error Detection Codes）

检错编码是一种用于检测数据传输或存储过程中是否发生错误的编码，但无法纠正错误。其主要功能是通过在数据中加入校验位，使接收方能够检测数据传输过程中出现的错误，从而采取适当的措施（如重新发送数据）。

2. 常见的检错编码

• 奇偶校验（Parity Check）：最简单的检错方法，数据的每一行或每一列会增加一个奇偶校验位，使得其1的数量为奇数或偶数。如果接收到的数据不符合设定的奇偶性，就可以判断出错误的发生。
• 循环冗余校验（CRC，Cyclic Redundancy Check）：一种较复杂但非常有效的检错编码，广泛应用于网络通信和存储系统。
  • CRC利用多项式除法
  • 将校验值附加到数据后面
  • 接收端通过重新计算进行验证
• 校验和（Checksum）：一种简单的检错编码，通过将数据块的字节相加得到一个校验值，附加在数据之后进行传输，接收端通过重新计算比较校验值来检测错误。

停止等待协议

停止等待协议（Stop-and-Wait Protocol）是一种基本的面向连接的数据链路层传输协议。它是一种可靠的数据传输协议，常用于简单的网络通信中，通过引入确认（ACK）机制来确保数据包的正确接收。下面是该协议的核心概念和工作原理：

协议概述

在停止等待协议中，发送方发送一个数据包后，必须暂停并等待接收方的确认（ACK）到达，才能发送下一个数据包。如果在规定的超时时间内没有收到确认，发送方会重传当前数据包。

工作原理

1. 发送数据：发送方发送一个数据包，并启动定时器以等待确认。发送的时候必须要保留副本
2. 等待确认：发送方暂停发送，等待接收方发送确认（ACK）消息。
3. 接收确认：
   • 成功接收：如果发送方在超时时间内收到ACK，停止定时器并发送下一个数据包。接收方一定要编号，防止ACK丢失
   • 未接收到ACK：如果超时仍未收到确认，重传当前数据包。
4. 重复：重复上述过程，直到所有数据发送完毕。

协议的优点

• 简单实现：由于每次只发送一个数据包，发送方不需要维护复杂的窗口或缓冲区。
• 可靠性：通过确认和重传机制，能够确保数据在出现丢包时的可靠传输。

协议的缺点

• 低效率：每次发送一个数据包后必须等待确认，这会导致信道的利用率较低，尤其是在高延迟的网络中。
• 吞吐量受限：由于每次只能发送一个数据包，在网络延迟较大时，协议的吞吐量会受到显著影响。

吞吐量分析

停止等待协议的效率可以用以下公式分析：
效率 = 数据传输时间 数据传输时间 + 等待时间 \text{效率} = \frac{\text{数据传输时间}}{\text{数据传输时间} + \text{等待时间}} 效率=数据传输时间+等待时间数据传输时间​

如果传输时间为 T d a t a T_{data} Tdata​，RTT（往返时延）为 T R T T T_{RTT} TRTT​，协议的信道利用率可以表示为：
利用率 = T d a t a T d a t a + T R T T + T a c k \text{利用率} = \frac{T_{data}}{T_{data} + T_{RTT}+T_{ack}} 利用率=Tdata​+TRTT​+Tack​Tdata​​

当 T R T T T_{RTT} TRTT​ 远大于 T d a t a T_{data} Tdata​ 时，信道利用率会非常低。这表明在高延迟的网络环境中，停止等待协议效率低下。

后退 N 帧协议（Go-Back-N Protocol）

后退 N 帧协议是一种面向连接的、基于滑动窗口的传输协议，用于在网络通信中实现高效的可靠数据传输。它允许发送方在未收到确认（ACK）时继续发送多个数据包，但如果遇到错误或丢包，发送方必须回退并重新发送从错误数据包开始的所有未确认数据包。

协议概述

后退 N 帧协议是滑动窗口协议的一种实现，发送方维护一个发送窗口，接收方只需要发送对接收数据的确认。发送方可以在窗口内连续发送多个数据包而无需等待每个数据包的确认。当发送方收到一个确认时，它会将窗口向前滑动，以便发送新的数据包。

工作原理

1. 发送窗口：发送方可以在其窗口大小范围内连续发送多个数据包，无需等待每个数据包的确认。窗口大小通常为 N N N，即发送方可以在未收到 ACK 的情况下发送 N N N 个数据包。
2. 接收确认：接收方按序接收数据包，并对已按序接收的数据包发送累计确认（cumulative ACK）。接收方只会对最后一个正确接收的按序数据包发送确认。
3. 错误处理：
   • 如果接收方检测到数据包错误或顺序错误，只会丢弃该数据包及其后面的数据包，不会发送确认。
   • 发送方在超时后如果未收到某个数据包的确认，将回退到该数据包并重传该数据包及其后的所有数据包。

示例

假设发送窗口大小 N = 4 N = 4 N=4，发送方需要发送 1 到 10 号数据包：

1. 发送方发送数据包 1, 2, 3, 4。
2. 接收方成功接收 1, 2, 3，并发送 ACK 3（确认接收到 1 到 3）。
3. 发送方继续发送数据包 5, 6, 7, 8。
4. 接收方在接收数据包 4 时检测到错误，丢弃数据包 4 及其后续数据包（5, 6, 7, 8）。
5. 发送方在超时后未收到 ACK 4，回退并重新发送数据包 4, 5, 6, 7, 8。

窗口移动

发送窗口是动态滑动的，每当接收到一个确认时，窗口向前滑动一个位置，从而释放出新的空间用于发送新的数据包。窗口的大小 N N N 确定了在未收到确认之前，发送方最多可以发送的未确认数据包数量。

协议的优点

• 高效传输：相比于简单的停止等待协议，后退 N 帧协议允许在等待确认时发送更多的数据包，从而提高了信道利用率。
• 简化的接收方逻辑：接收方无需缓存未按序到达的数据包，只需按序接收并确认。

协议的缺点

• 重传代价高：如果遇到错误，发送方需要重新发送所有从错误数据包开始的未确认数据包，导致带宽浪费。
• 受窗口大小限制：窗口大小 N N N 的选择直接影响协议的性能和带宽利用率。

选择性重传协议

选择性重传协议（Selective Repeat Protocol，SR）是一种先进的滑动窗口协议，旨在提高数据传输的可靠性和效率。与后退 N 帧协议不同的是，选择性重传协议只会重传确实丢失或出错的特定数据包，而不是重传整个发送窗口内的数据包。这种机制减少了不必要的重传，提升了网络的吞吐量。

协议概述

选择性重传协议使用滑动窗口机制，允许发送方和接收方同时维护窗口。发送方可以在窗口大小内发送多个数据包，而接收方则能够缓存未按序到达的数据包，并对每个数据包分别发送确认（ACK）。发送方只会重传那些未收到确认的数据包。

工作原理

1. 发送窗口：发送方维护一个窗口，窗口的大小决定了在未收到确认之前能发送的未确认数据包数量。窗口滑动时，新的数据包可以被发送。
2. 接收窗口：接收方也维护一个窗口，可以接收并缓存未按序到达的数据包。接收方对每个接收到的数据包发送单独的确认。
3. 数据包确认：
   • 当接收方接收到一个正确的、按序到达的数据包时，向发送方发送 ACK，并向上层协议递交该数据包。
   • 当接收方接收到一个未按序到达的数据包时，缓存此数据包并发送 ACK，但不会递交给上层协议，直到所有前序数据包均已按序收到。
4. 重传机制：
   • 发送方在超时后，只会重传未收到 ACK 的数据包，而不会重传整个窗口内的数据包。

示例流程

假设发送窗口大小为 N = 4 N = 4 N=4，发送方需要发送 1 到 10 号数据包：

1. 发送方发送数据包 1, 2, 3, 4。
2. 接收方成功接收 1 和 2，发送 ACK 1 和 ACK 2。
3. 数据包 3 丢失，接收方接收到 4，并缓存 4，发送 ACK 4。
4. 发送方在超时后未收到 ACK 3，因此重传数据包 3。
5. 接收方接收数据包 3，向发送方发送 ACK 3。此时，接收方将缓存的包（即数据包 4）递交给上层。
   感觉这幅图讲的非常好：看懂这幅图，基本上就差不多了
   

协议的优点

• 高效性：相比于后退 N 帧协议，选择性重传只会重传那些确实丢失的数据包，从而减少了不必要的重传，节约了带宽。
• 更高的信道利用率：接收方能够缓存未按序到达的数据包，使得发送方无需因个别丢包而等待整个窗口重传，提高了整体效率。

协议的缺点

• 复杂性增加：接收方需要缓存未按序到达的数据包，并维护更多的逻辑来判断何时向上层协议递交数据。实现起来比后退 N 帧协议复杂。
• ACK 管理：发送方和接收方需要能够正确处理和跟踪多个独立 ACK，增加了实现难度。
• 发送窗口：大了会溢出，小了没意义。