通信网络/错误控制、流量控制、MAC

简介

数据链路层是OSI模型中的第二层。它负责相邻网络节点之间的通信。它处理通过物理层进出数据。它还为网络层提供了一个定义明确的服务。数据链路层分为两个子层。媒体访问控制 (MAC) 和逻辑链路控制 (LLC)。

数据链路层确保已建立初始连接，将输出数据划分为数据帧，并处理接收方确认数据已成功到达。它还通过分析帧中特殊位置的位模式来确保已成功接收传入数据。

在以下部分中，讨论了数据链路层的功能 - 错误控制和流量控制。之后解释了 MAC 层。在 MAC 层部分解释了多路访问协议。

错误控制

网络负责将数据从一台设备传输到另一台设备。从发送应用程序到接收应用程序的端到端数据传输涉及许多步骤，每个步骤都可能发生错误。通过错误控制过程，我们可以确信传输和接收的数据是相同的。数据在传输过程中可能会损坏。为了可靠的通信，必须检测和纠正错误。

错误控制是检测和纠正位级和数据包级错误的过程。

错误类型

单比特错误

单比特错误是指数据单元中只有一位从 1 变为 0 或从 0 变为 1。

突发错误

突发错误是指数据单元中两位或多位发生了改变。突发错误也称为数据包级错误，其中存在数据包丢失、重复、乱序等错误。

错误检测

错误检测是在发送方和接收方之间传输过程中检测错误的过程。

错误检测类型

奇偶校验
循环冗余校验 (CRC)
校验和

冗余

冗余允许接收方检查接收到的数据在传输过程中是否已损坏。这样他就可以请求重新传输。冗余是在错误检测中使用额外位的概念。如图所示，发送方将冗余位 (R) 添加到数据单元并发送到接收方，当接收方获取位流并通过校验函数时。如果没有错误，则数据单元的数据部分被接受，冗余位被丢弃。否则请求重新传输。

奇偶校验

奇偶校验添加一位表示前一个数据中 1 位的数量是奇数还是偶数。如果传输过程中更改了一位，则消息将更改奇偶校验，并且此时可以检测到错误。奇偶校验并不十分健壮，因为如果更改的位数是偶数，则校验位将无效，并且不会检测到错误。

单比特奇偶校验
二维奇偶校验

此外，奇偶校验不会指示哪个位包含错误，即使它可以检测到错误。数据必须完全丢弃并从头开始重新传输。在嘈杂的传输介质上，成功传输可能需要很长时间，甚至永远不会发生。然而，奇偶校验的优势在于它是使用一位空间的最佳代码。

循环冗余校验

CRC 是一种非常有效的冗余校验技术。它基于数据单元的二进制除法，其余数 (CRC) 添加到数据单元并发送到接收方。接收方用相同的除数除以数据单元。如果余数为零，则数据单元被接受并传递到协议栈的上一层，否则它被认为在传输过程中已损坏，并且数据包被丢弃。

CRC 的顺序步骤如下。

发送方遵循以下步骤。

数据单元由比除数少一个的 0 的数量组成。
然后使用二进制除法技术除以预定义的除数。余数称为 CRC。CRC 附加到数据单元并发送到接收方。

接收方遵循以下步骤。

当数据单元后跟 CRC 到达时，它被相同的除数除以，该除数用于找到 CRC（余数）。
如果此除法过程中的余数结果为零，则它就是无错误数据，否则它已损坏。

图显示了 CRC 过程的工作方式。

[a] 发送方 CRC 生成器 [b] 接收方 CRC 校验器

校验和

校验和是错误检测机制的第三种方法。校验和用于上层，而奇偶校验和 CRC 用于物理层。校验和也是基于冗余的概念。

在校验和机制中，要执行两个操作。

校验和生成器

发送方使用校验和生成器机制。首先将数据单元划分为 n 位的相等段。然后使用 1 的补码将所有段加在一起。然后再次对其进行一次补码。它成为校验和并与数据单元一起发送。

Exp

如果要将 16 位 10001010 00100011 发送到接收方。

因此校验和被添加到数据单元并发送到接收方。最终数据单元为 10001010 00100011 01010000。

校验和校验器

接收方接收数据单元并将其划分为相同大小的段。使用 1 的补码将所有段加在一起。结果再次进行一次补码。如果结果为零，则数据将被接受，否则将被拒绝。

Exp

如果最终数据非零，则它将被拒绝。

错误纠正

这种类型的错误控制允许接收方在传输过程中数据损坏时重建原始信息。

汉明码

它是一种使用冗余位的单比特错误纠正方法。

在这种方法中，冗余位与原始数据一起包含在内。现在，将位排列起来，以便不同的错误位产生不同的错误结果，并且可以识别损坏的位。一旦识别到位，接收方就可以反转其值并纠正错误。汉明码可以应用于任何长度的数据单元，并且使用数据和冗余位之间的关系。

算法

奇偶校验位位于 2 的幂次 (2 r) 处。
其余位置由原始数据填充。
每个奇偶校验位将负责代码中的位。
最终代码将发送到接收方。

在上面的示例中，我们计算了各种位组合的偶校验。每个组合的值是相应 r（冗余）位的的值。r1 将负责位 1、3、5、7、9、11。它根据偶校验位的总和进行设置。其余奇偶校验位的相同方法。

如果错误发生在第 7 位，该位从 1 变为 0，则接收方会重新计算发送方使用的相同位集。通过这种方式，我们可以识别错误发生的精确位置。一旦识别到位，接收方就可以反转其值并纠正错误。

流量控制

流量控制是数据链路层的一个重要设计问题，它控制发送方和接收方之间的数据流。

在通信中，发送方和接收方之间有通信介质。当发送方将数据发送到接收方时，以下情况可能会出现问题

1) 发送方以更高的速率发送数据，而接收方过于迟缓而无法支持该数据速率。

为了解决上述问题，流量控制被引入数据链路层。它也适用于几个更高层。流量控制的主要概念是在计算机网络中引入效率。

流量控制方法

基于反馈的流量控制
基于速率的流量控制

Feed back based Flow Control is used in Data Link Layer and Rate based Flow Control is used in Network Layer.

基于反馈的流量控制

在基于反馈的流量控制中，在发送方收到接收方的反馈之前，它不会发送下一条数据。

基于反馈的流量控制类型

A. 停止-等待协议

B. 滑动窗口协议

A 一位滑动窗口协议
A 使用后退 N 的协议
A 使用选择性重复的协议

A. 单工停止-等待协议

在这个协议中，我们做了以下假设

它提供从发送方到接收方的数据单向流。
通信信道被认为是无错误的。

在这个协议中，发送方只需发送数据并等待接收方的确认。这就是它被称为停止-等待协议的原因。

这种类型效率不高，但它是流量控制最简单的方法。

在这种方案中，我们将通信信道视为无错误的，但如果信道存在一些错误，则接收方将无法从发送方获取正确的数据，因此发送方将无法发送下一条数据（因为它不会从接收方获取确认）。因此，它将结束通信，为了解决这个问题，引入了两个新概念。

计时器，如果发送方在特定时间内无法获取确认，则它会再次将缓冲数据发送到接收方。当发送方开始发送数据时，它会启动计时器。
序列号，通过此序列号，发送方将数据与特定的序列号一起发送，因此在接收数据后，接收方将以该序列号发送数据，并且在此处，发送方也希望以相同的序列号获得确认。

这种类型的方案称为带有重传的肯定确认 (PAR)。

B. 滑动窗口协议

停止-等待协议的问题 在最后几个协议中，发送方必须等待接收方的肯定确认或超时才能将下一帧发送到接收方。因此，如果发送方已准备好发送新数据，则它无法发送。发送方依赖于接收方。以前的协议只提供单向流，这意味着只有发送方发送数据，接收方只是确认它，因此使用了双倍带宽。

为了解决上述问题，引入了滑动窗口协议。

在其中，发送方和接收方都使用缓冲区，其大小相同，因此无需等待发送方发送第二条数据，它可以依次发送，而无需等待接收方的确认。

它还解决了带宽使用过多的问题，因为在这个方案中，发送方和接收方都使用信道发送数据，接收方只用它想发送给发送方的信息来发送确认信息，所以没有专门的带宽用于确认信息，因此节省了带宽，整个过程被称为PIGGYBACKING。

滑动窗口协议类型

i. 一位滑动窗口协议

ii. 使用 Go Back N 的协议

iii. 使用选择重传的协议

i. 一位滑动窗口协议

此协议的缓冲区大小为一位，因此发送方和接收方发送和接收数据包的可能性仅为 0 和 1。此协议包含序列号、确认号和数据包编号。它使用全双工信道，因此有两种可能性

发送方首先开始发送数据，接收方在收到数据后开始发送数据。
接收方和发送方都同时开始发送数据包。

第一种情况很简单，并且运行良好，但第二种情况会出现错误。该错误可能类似于数据包重复，而没有任何传输错误。

ii. 使用 Go Back N 的协议

流水线的问题是，如果发送方发送 10 个数据包，但第 8 个数据包出现问题，则需要重新发送所有数据。因此，引入了 Go Back N 和选择重传协议来解决此问题。在这个协议中，接收方有两个可能性，它可能具有较大的窗口大小，也可能具有一个窗口大小。

接收方端的窗口大小可能很大，也可能只有一个。在接收方窗口大小为一个的情况下，如图 (a) 所示，如果发送方要发送从 1 到 10 的数据包，但假设第 2 个数据包出现错误，那么发送方将从零、一、二等开始。这里我们假设发送方具有 8 的超时间隔。因此，超时将在 8 个数据包后发生，在此之前它不会等待确认。在这种情况下，接收方端的第 2 个数据包出现错误，其他直到第 8 个数据包都被接收方丢弃。因此，在这种情况下，数据丢失更多。

而在接收方端具有较大窗口大小的情况下，如图 (b) 所示，如果第 2 个数据包出现错误，接收方将接受第 3 个数据包，但它会向发送方发送第 2 个数据包的 NAK，并缓冲第 3 个数据包。接收方对第 4 和第 5 个数据包执行相同的操作。当发送方收到第 2 个数据包的 NAK 时，它会立即将第 2 个数据包发送给接收方。收到第 2 个数据包后，接收方发送第 5 个数据包的 ACK，表示它已收到前 5 个数据包。因此，不需要再次发送第 3、第 4 和第 5 个数据包，它们在接收方端被缓冲。

iii. 使用选择重传的协议

使用 Go Back N 的协议在错误很少发生时效果很好，但如果线路很差，它会在重新传输的帧上浪费大量带宽。因此，为了提供可靠性，引入了选择重传协议。在这个协议中，发送方以 0 开始其窗口大小，并增长到某个预定义的最大值。接收方的窗口大小是固定的，等于发送方窗口大小的最大值。接收方有一个缓冲区，为其固定窗口内的每个序列号保留。

每当一个帧到达时，其序列号就会被函数检查，以查看它是否在窗口内，如果是，并且它还没有被收到，它就会被接受并存储。无论网络层是否预期，都会执行此操作。

这里发送方和接收方的缓冲区大小为 7，如图 (a) 所示，发送方向接收方发送 7 个帧，并启动计时器。当接收方收到帧时，它会将 ACK 发送回发送方，并将帧传递给网络层。完成此操作后，接收方清空其缓冲区，增加序列号，并预期序列号为 7、0、1、2、3、4、5。但是，如果 ACK 丢失，发送方将不会收到 ACK。因此，当计时器到期时，发送方会将原始帧 0 到 6 重新传输给接收方。在这种情况下，接收方会接受帧 0 到 5（这些帧是重复的），并将其传递给网络层。在这种情况下，协议失败。

为了解决重复问题，发送方和接收方的缓冲区大小应为 (MAX SEQ + 1)/2，即要发送的帧数量的一半。如图 (c) 所示，发送方发送帧 0 到 3，因为它的窗口大小为 4。接收方接受帧，并将确认发送给发送方，并将帧传递给网络层，并将预期序列号从 4 增加到 7。如果 ACK 丢失，发送方将再次将 0 到 3 发送给接收方，但接收方期望 4 到 7，因此它不会接受。这样就解决了重复问题。

MAC

数据链路层分为两个子层：媒体访问控制 (MAC) 层和逻辑链路控制 (LLC) 层。MAC 子层控制网络上的计算机如何获得数据访问权限并获得传输数据的许可。LLC 层控制帧同步、流量控制和错误检查。

Mac 层是构成 OSI 参考模型数据链路层的子层之一。

MAC 层负责将数据包从一个网络接口卡 NIC 移动到另一个网络接口卡，穿过共享信道。

MAC 子层使用 MAC 协议来确保从不同站点通过相同信道发送的信号不会发生冲突。

不同的共享网络使用不同的协议，例如以太网、令牌环、令牌总线和 WAN。

1. ALOHA

ALOHA 是一种简单的通信方案，其中网络中的每个源在有帧要发送时都会发送其数据，而不检查是否有其他站点处于活动状态。每个站点在发送帧后都会等待隐式或显式确认。如果帧成功到达目的地，则发送下一帧。如果帧未能到达目的地，则会再次发送。

纯 ALOHA ALOHA 是多路访问中最简单的技术。这种机制的基本思想是用户可以随时传输数据。如果数据成功传输，则不会出现问题。但如果发生冲突，则站点将再次传输。如果发送方没有收到接收方的确认，则可以检测到冲突。

在 ALOHA 中，冲突概率相当高。ALOHA 适合流量较少的网络。理论上证明，ALOHA 的最大吞吐量为 18%。

                     P (success by given node) = P(node transmits) . P(no other node transmits in [t0-1,t0] . P(no other node transmits in [t0,t0 +1] 
                                               = p . (1-p)N-1 . (1-p)N-1

                 P (success by any of N nodes) = N . p . (1-p) N-1 . (1-p)N-1 
                                               … Choosing optimum p as N -->  infinity...
                                               = 1 / (2e) = .18 
                                               =18%

时隙 ALOHA

在 ALOHA 中，新发射的数据包可能会与正在进行的数据包发生冲突。如果所有数据包的长度相同，并且传输需要 L 个时间单位，那么很容易看出，一个数据包会在 2L 长度的时窗内与任何其他数据包发生冲突。如果以某种方式缩短这个时窗，那么冲突的数量就会减少，吞吐量就会增加。这种机制用于时隙 ALOHA 或 S-ALOHA。时间被划分为长度为 L 的相等时隙。当一个站点想要发送数据包时，它会等到下一个时隙的开始。

时隙 ALOHA 的优点

单个活动节点可以以信道的全速率连续传输
高度分散：仅节点中的时隙需要同步
简单

时隙 ALOHA 的缺点

冲突，浪费时隙
空闲时隙
时钟同步

时隙 ALOHA 的效率

假设有 N 个节点，它们有许多帧要发送。每个节点将帧发送到时隙的概率为 p。
节点 1 成功获得时隙的概率为 p.(1-p)N-1
每个节点都成功的概率为 N.p.(1-p)N-1
为了最大限度地提高 N 个节点的效率，找到使 Np(1-p)N-1 最大化的 p*。
对于许多节点，当 N 趋于无穷大时，求 Np*(1-p*)N-1 的极限，得到 1/e = .37

时隙 ALOHA 的明显优势是更高的吞吐量。但由于需要时间同步，它会增加站点的复杂性和带宽开销。

2. 载波侦听多路访问协议 (CSMA)

对于时隙 ALOHA，可以实现的最佳信道利用率为 1/e。为了提高性能，开发了多种协议。

侦听载波并相应地采取行动的协议称为载波侦听协议。载波侦听允许站点检测介质当前是否正在使用。使用载波侦听电路的方案统称为载波侦听多路访问或 CSMA 方案。CSMA 有两种变体：CSMA/CD 和 CSMA/CA

最简单的 CSMA 方案是，如果介质空闲，站点会侦听介质，立即发送数据包。如果站点等待介质空闲，则称为持续的，否则称为非持续的。

a. 持续

当一个站点有数据要发送时，它首先会侦听信道，以检查是否有人在传输数据。如果它检测到信道空闲，站点开始传输数据。如果它检测到信道繁忙，它会等到信道空闲。当一个站点检测到信道空闲时，它会以概率 P 传输其帧。这就是为什么这个协议被称为p-持续 CSMA。此协议适用于时隙信道。当一个站点发现信道空闲时，如果它以概率 1 传输帧，则该协议被称为1-持续。1-持续协议是最积极的协议。

b. 非持续

非持续 CSMA 比 P 持续协议不那么积极。在这个协议中，在发送数据之前，站点会侦听信道，如果信道空闲，它会开始传输数据。但如果信道繁忙，站点不会持续侦听，而是等待随机的时间，并重复算法。这里的算法可以提高信道利用率，但也导致比 1-持续更长的延迟。

CSMA/CD

载波侦听多路访问/冲突检测是一种用于多路访问协议的技术。如果没有传输正在进行，则特定站点可以传输。如果两个站点试图同时传输，这会导致冲突，所有参与的站点都会检测到冲突。在随机时间间隔后，发生冲突的站点会尝试再次传输。如果再次发生冲突，则选择随机等待时间的时间间隔会逐步增加。这被称为指数退避。

指数退避算法

适配器获取数据报并创建帧
如果适配器检测到信道空闲（9.6 微秒），它将开始传输帧。如果检测到信道繁忙，则等待信道空闲，然后传输。
如果适配器在未检测到其他传输的情况下传输了整个帧，则适配器已完成帧传输！
如果适配器在传输过程中检测到其他传输，则中止并发送阻塞信号。
中止后，适配器进入指数退避：在第 m 次冲突后，适配器从 {0,1,2,…,2m-1} 中随机选择一个 K。适配器等待 K*512 位时间（即时隙）并返回步骤 2。
在第 10 次重试后，随机数停止在 1023。在第 16 次重试后，系统停止重试。

CSMA/CA

CSMA/CA 是载波侦听多路访问/冲突避免。在这种多路访问协议中，站点在传输帧之前侦听介质。该协议旨在提高 CSMA 的性能。CASMA/CA 用于基于 802.11 的无线局域网。在无线局域网中，在传输时无法监听介质。因此，冲突检测不可行。

在 CSMA/CA 中，当站点检测到冲突时，它会等待随机时间。然后，在传输数据包之前，它会监听介质。如果站点检测到介质空闲，它将开始传输数据包。如果检测到介质繁忙，它会等待信道空闲。

当 A 想要向 B 传输数据包时，首先它会向 B 发送 30 字节的 RTS（请求发送）数据包，其中包含长度 L。如果 B 空闲，它会用 CTS（允许发送）数据包向 A 发送响应。这里，任何监听 CTS 数据包的设备都将在 L 持续时间内保持静默。当 A 收到 CTS 时，它会向 B 发送长度为 L 的数据。

该协议存在一些问题。

隐藏站点问题
暴露站点问题

1. 隐藏站点问题（图 a）

当一个站点向另一个站点/接收器发送数据包时，一些不在发送方范围内的其他站点可能会开始向同一个接收器发送数据包。这将导致数据包冲突。这个问题将在下面更详细地解释。

假设 A 正在向 B 发送数据包。现在，同时 D 也想向 B 发送数据包。这里 D 无法听到 A。因此，D 也会将数据包发送到 B。因此会发生冲突。

2. 暴露站点问题（图 b）

当 A 正在发送数据包时，C 也会听到。因此，如果站点想发送数据包到 D，它仍然不会发送。这将降低协议的效率。这个问题称为暴露站点问题。

为了解决这些问题，802.11 支持两种操作。

DCF（分布式协调功能）
PCF（点协调功能）

DCF

DCF 不使用中央控制。它使用 CSMA/CA 协议。它使用物理信道感知和虚拟信道感知。这里，当一个站点想要发送数据包时，它首先会感知信道。如果信道空闲，则立即开始传输。在传输过程中，它不会感知信道，但会发出整个帧。如果接收器已开始传输，则该帧可能会在接收器端被破坏。在这种情况下，如果发生冲突，发生冲突的站点会使用二进制指数退避算法等待随机时间，并稍后尝试再次传输。

下面给出的图解释了虚拟感知。

这里，A 想要向 B 发送数据包。站点 C 在 A 的范围内。站点 D 在 B 的范围内，但不在 A 的范围内。当 A 想向 B 发送数据包时，它首先会向 B 发送 RTS（30 字节）数据包，请求发送数据包的许可。在响应中，如果 B 想要授予许可，它会向 A 发送 CTS 数据包，允许 A 发送数据包。当 A 收到其帧时，它会启动 ACK 定时器。当帧成功传输时，B 会发送 ACK 帧。这里，如果 A 的 ACK 时间在收到 B 的 ACK 帧之前过期，则整个过程将再次运行。这里，对于站点 C 和 D，当站点 A 向站点 B 发送 RTS 时，RTS 也将被 C 接收。通过查看 RTS 中提供的信息，C 会意识到有人正在发送数据包，以及整个序列将持续多长时间，包括最终的 ACK。因此，C 会自行断言一种虚拟信道繁忙状态（如图所示，由 NAV（网络分配向量）指示）。在特定时间内保持静默。站点 D 不会收到 RTS，但会收到来自 B 的 CTS。因此，B 也会为自己断言 NAV 信号。

如果信道噪声太大，当 A 向 B 发送帧并且帧太大时，则帧被损坏的可能性更大，因此帧将被重新传输。C 和 D 两个站点也会保持静默，直到整个帧成功传输。为了解决噪声信道的问题，802.11 允许将帧分割成更小的片段。一旦使用 CTS 和 RTS 获取了信道，就可以连续发送多个段。段的序列称为碎片突发。碎片化通过将重传限制在损坏的片段而不是整个帧来提高吞吐量。

PCF

PCF 机制使用基站来控制其小区中的所有活动。基站轮询其他站点，询问它们是否有要发送的帧。在 PCF 中，由于它是集中式的，因此不会发生冲突。在轮询机制中，基站定期（每秒 10 到 100 次）广播信标帧。信标帧包含系统参数，例如跳频序列、驻留时间、时钟同步等。它还会邀请新站点注册。所有已注册的站点都有保证可以获得一定比例的带宽。因此，在 PCF 中，服务质量得到保证。

所有实现都必须支持 DCF，但 PCF 是可选的。PCF 和 DCF 可以共存于一个小区内。分布式控制和集中式控制可以使用帧间时间间隔同时运行。定义了四个间隔。下面给出的图显示了这四个间隔。

SIFS - 短帧间间隔
PIFS - PCF 帧间间隔
DIFS - DCF 帧间间隔
EIFS - 扩展帧间间隔

More about this has been explained in section 3 of Data Link Layer.

轮流 MAC 协议

轮询

在轮询中，主节点邀请从节点轮流传输。单点故障（主节点故障）、轮询开销、延迟是轮询中的问题。

位图保留

在位图保留中，站点提前预留竞争时隙。轮询开销和延迟是该协议中的问题。

令牌传递

在这个协议中，令牌按顺序从一个节点传递到下一个节点。单点故障（令牌）、令牌开销、延迟是令牌传递中的问题。

问题

解释隐藏站点和暴露站点问题。
解释二进制指数退避算法。
两个 CSMA/C 站点正在尝试传输长文件。每发送一个帧后，它们使用二进制指数退避算法竞争信道。连接在第 k 轮结束的概率是多少？
在 CRC 中，如果数据单元为 101100，除数为 1010，余数为 110，则接收器处的被除数是什么？（答案：）

进一步阅读

维基百科对此主题有更多内容。

OSI 模型

串行编程：错误校正方法