数据链路层

约 6386 个字 10 张图片 预计阅读时间 32 分钟

数据链路层（Data Link Layer）是OSI模型的第二层，主要负责在物理层提供的原始比特流上建立、维护和终止数据链路连接。它确保数据在网络节点之间可靠地传输，并处理错误检测和纠正。

链路、数据链路和帧

链路(Link)数据链路(Data Link)帧(Frame)

• 链路：链路是指连接两个网络设备（如计算机、路由器、交换机等）之间的通信路径。链路可以是有线的（如以太网电缆、光纤）或无线的（如Wi-Fi、蓝牙）。链路的主要作用是传输数据帧，确保数据在两个设备之间正确传递。

• 当真正进行通信时,两个设备之间的传输可能经过了许多链路

• 数据链路：数据链路可以说是链路加上一些软硬件.这些软硬件实现了传输数据必需的通信协议.

• 数据链路层的主要功能包括：

  • 帧的封装和解封装

  • 地址寻址

  • 错误检测和纠正

  • 流量控制

  • 链路管理

• 帧：帧是数据链路层传输的基本单位,是数据链路层的PDU(Protocol Data Unit,协议数据单元).帧通常包含以下几个部分:

  • 帧头(Header): 包含控制信息，如源地址、目的地址、类型字段等。

  • 数据部分(Payload): 包含实际传输的数据。

  • 帧尾(Trailer): 通常包含错误检测码，如循环冗余校验(CRC)码。

数据链路层的三个重要问题

封装成帧和透明传输

当数据链路层接收到来自网络层的数据包时,它需要将数据包封装成帧.封装成帧是指在一段数据的前后分别添加首部和尾部,构成帧.

封装成帧

以太网的帧格式如下:

前同步码	帧开始定界符	目的MAC地址	源MAC地址	类型/长度	数据	FCS(帧校验序列)
7字节	1字节	6字节	6字节	2字节	46~1500字节	4字节

• 前导码：用于接收端同步。

• 帧开始定界符：标志帧的开始。

• 目的/源MAC地址：标识收发双方。

• 类型/长度：指示上层协议类型或数据长度。

• 数据：实际传输的数据。

• FCS：用于差错检测的循环冗余校验码。位于尾部

标志字段	地址字段	控制字段	协议字段	信息字段	FCS(帧校验序列)	标志字段
1字节	1字节	1字节	2字节	0~1500字节	2字节	1字节

• 标志字段：帧的开始和结束标志，固定为0x7E。

• 地址字段：通常为0xFF，表示广播地址。

• 控制字段：通常为0x03，表示无编号信息帧。

• 协议字段：指示信息字段中封装的数据类型（如IP、LCP等）。

• 信息字段：实际传输的数据。

• FCS：帧校验序列，用于差错检测。位于帧的尾部。

从上面所示，可以发现，并不是每一种数据链路层协议的帧都包含有帧定界标志（即帧头和帧尾），比如以太网帧就没有。这是因为以太网帧采用了前导码来实现帧定界。

• 前导码：由前同步码加上帧开始定界符组成。其作用是让接收方能够识别出帧的开始位置，从而实现帧定界。

• 帧间间隔：以太网还有帧间间隔的概念，即两帧之间必须有一个最小的时间间隔（发送96比特需要的时间），以确保接收方能够正确识别出帧的边界。

为了提高传输效率，我们总是希望帧的数据载荷越大越好。但实际上，帧的数据载荷是有最大值限制的。这个限制就是最大传输单元(MTU,Maximum Transmission Unit)。不同的数据链路层协议有不同的MTU值。

---

另一方节点在接收到帧后，需要进行解封装，提取出数据包并交给网络层处理。解封装依靠的是帧头和帧尾中的控制信息。

这里存在一个问题：
如果数据部分中恰好包含了和帧头或帧尾相同的比特序列，接收方在解封装时就会误以为数据部分的内容是帧头或帧尾，从而导致解封装错误。

为了解决这个问题，数据链路层需要实现透明传输.透明传输是指数据链路层对上层交付下来的协议数据单元PDU没有任何限制，就好像数据链路层不存在一样。

一般使用类似于转义字符的机制来实现透明传输.对于PPP,我们使用字节填充(Byte Stuffing)来实现透明传输.

字节填充

而对于HDLC,我们使用比特填充(Bit Stuffing)来实现透明传输.

比特填充

在这个上图中，帧的开始和结束都使用了一个特殊的比特序列 01111110作为标志。

我们使用比特填充规则 (又称“零比特填充法”)：

• 发送端：在扫描整个数据载荷时，只要连续出现5个1，就立即在后面填充一个0。

• 接收端：在接收数据时，只要发现连续的5个1，就检查其后的第6个比特。

• 如果第6个比特是 0，则说明这个0是发送端填充的，将其删除，恢复原始数据。

• 如果第6个比特是 1，则继续向后检查第7个比特。若是0（即01111110），则表明这是一个帧定界符；否则表示出现了错误。

差错检测

在传输过程中，数据可能会因为噪声、干扰等原因发生错误。为了保证数据的完整性，数据链路层需要实现差错检测。

错误分为两种类型：

• 位错：单个比特发生错误，如0变1或1变0。
• 帧错：帧丢失或帧顺序错误。

---

为了实现差错检测，在帧尾部通常会有纠错码。常见的有以下几种：

• 奇偶校验：在数据中添加一个额外的比特，使得数据中1的个数为奇数或偶数。接收端通过检查1的个数来检测错误。

  • 奇校验：使得数据中1的个数为奇数。
  • 偶校验：使得数据中1的个数为偶数。
  • 很显然，出现偶数位的错误就无法检测。

• 循环冗余校验（CRC）：将数据视为一个二进制多项式，通过多项式除法计算出一个余数，将余数附加在数据后面作为校验码。接收端通过重新计算余数来检测错误。

CRC计算示例

设发送的数据为 101001000，生成多项式为 1101（即 \(x^3 + x^2 + 1\)）。

1. 在数据后面添加3个0（生成多项式的最高次幂），得到 101001000000。

2. 使用二进制除法对 101001000000 除以 1101，得到余数 001。

3.去掉第一步添加的0,将余数附加在数据后面，得到最终发送的帧 101001000001。

接收端收到帧后，对 101001000001 除以 1101，如果余数为0，则表示没有错误；否则表示有错误。

需要注意的是:

1. 多项式必须要有最低次项

2. 余数的位数应与生成多项式最高次数相同，如果位数不够，则在余数前补0来凑足位数

二进制除法

二进制除法与十进制除法类似，但只使用0和1进行计算。主要步骤如下：

1. 将被除数的前几位与除数对齐。

2. 如果被除数的当前位大于等于除数，则进行异或操作（相当于减法），并将结果写在下一行。

3. 将下一位下拉，继续与除数对齐，重复步骤2，直到处理完所有位。

4. 最终剩下的部分即为余数。

二进制除法示例

海明码

海明码（Hamming Code）是一种用于错误检测和纠正的编码方法。它通过在数据中添加冗余位来实现错误检测和纠正。海明码能够检测并纠正单个比特错误，适用于需要高可靠性的通信系统。

海明码的基本原理如下：

1. 位置编号：将数据位和冗余位的位置编号，从1开始。冗余位的位置是2的幂次方（即1, 2, 4, 8, ...）。

2. 冗余位计算：每个冗余位负责检查特定位置的数据位。具体来说，第i个冗余位检查所有位置编号中第i位为1的位置。例如，第1个冗余位检查位置1, 3, 5, 7, ...，第2个冗余位检查位置2, 3, 6, 7, ...，以此类推。

3. 奇偶校验：每个冗余位的值通过对其负责检查的数据位进行奇偶校验计算得出。如果数据位中1的个数为奇数，则冗余位设为1；否则设为0。

4. 错误检测和纠正：接收端通过重新计算冗余位来检测错误。如果某个冗余位的计算结果与接收到的冗余位不符，则说明对应的数据位发生了错误。通过组合所有冗余位的错误信息，可以确定具体哪个数据位出错，并进行纠正。例如,如果第1和第3个冗余位检测到错误，而第2个冗余位没有检测到错误，则说明错误位置为\(101_2=5_{10}\).

5. 例子以后再补

---

可靠传输

• 可靠传输: 实现无论发送方发送什么,接收方都能正确无误地接收到.可靠传输通常通过以下方法实现:

  • 确认和重传：接收方在成功接收到数据后,发送一个确认(ACK)给发送方.如果发送方在超时时间内没有收到确认,则重传数据.

  • 序列号：为每个数据帧分配一个唯一的序列号,接收方通过序列号来检测丢失或重复的帧.

  • 流量控制：防止发送方发送数据过快,使接收方来不及处理.常用的方法有滑动窗口协议.

• 不可靠传输: 直接丢弃有误码的帧,不进行重传.

在实际传输中,可能出现多种差错情况:

• 误码

• 分组丢失

• 分组重复

• 分组失序

其中误码出现在数据链路层及其下层,而分组丢失、分组重复和分组失序主要出现在网络层及其以上层次.

---

使用确认和重传这两种机制的可靠传输协议，通常被称为自动重传请求（ARQ, Automatic Repeat reQuest）。这里的“自动”意味着重传是由协议自动处理的，接收方无需显式地向发送方请求重传。

在ARQ协议中，数据帧和确认帧都必须进行编号。这样，接收方才能明确哪个确认帧对应哪个数据帧，发送方也才能知道哪些数据帧尚未被确认。

ARQ协议主要分为以下三种：

1. 停止-等待协议（Stop-and-Wait）

2. 后退N帧协议（Go-Back-N, GBN）

3. 选择重传协议（Selective Repeat, SR）

通用性

值得注意的是，这三种可靠传输协议的基本原理并不仅限于数据链路层，它们同样广泛应用于其上各层，尤其是传输层。

停止-等待协议(Stop-and-Wait)

停止-等待协议是最简单的ARQ协议。其工作原理如下：

1. 发送方发送一个数据帧后，停止发送，等待接收方的确认。

2. 接收方收到数据帧后，发送一个确认帧(ACK)给发送方。

3. 发送方收到确认帧后，发送下一个数据帧。

4. 如果发送方在超时时间内没有收到确认帧，或者接受到NAK(否定确认)，则重传该数据帧。

   • 相关的概念有RTO(重传超时时间,Retransmission Timeout),略大于往返时间RTT(Round Trip Time)

停止-等待协议

由于停止-等待协议“发一帧，等一帧”的特性，我们只需要区分当前帧与上一帧即可。因此，该协议采用1比特的序列号就足够了，这通常被称为自动重传请求（ARQ）的交替位协议（Alternating-Bit Protocol）。

• 帧编号：发送的帧交替使用序列号0和1来标识。

• 确认机制：确认帧（ACK）同样需要编号，以明确是对哪个数据帧的确认。例如，ACK0 表示对序列号为0的数据帧的确认，ACK1 则是对序列号为1的数据帧的确认。

通过这种简单的编号机制，协议可以有效处理异常情况：

• 处理重复帧：如果接收方连续收到两个序列号相同的数据帧，则表明发送方进行了超时重传。此时，接收方会丢弃重复的帧，并重新发送上一个确认帧。

• 处理重复或延迟的确认：如果发送方在发送 DATA1 后，收到了一个 ACK0，它就知道这是一个对先前 DATA0 的重复或延迟确认，应予以丢弃。

缓冲区的作用

为了实现超时重传，发送方必须设置一个发送缓冲区。

当发送方发送完一个数据帧后，它必须在发送缓存中保留该数据帧的副本。只有在明确收到了对方发来的、对应正确序列号的确认帧（ACK）后，发送方才能清空缓存中的这个副本，准备发送下一帧。

若假设传输数据的时间是Tt，往返时间是RTT，发送ACK的时间忽略不计，则信道利用率为:

\[ U = \frac{Tt}{Tt + RTT} \]

在Tt远小于RTT的情况下，信道利用率会非常低。这是停止-等待协议的一个主要缺点。

后退N帧协议(Go-Back-N, GBN)

后退N帧协议是一种改进的ARQ协议。其工作原理如下：

流水线传输

1. 发送方需要维护一个发送窗口，窗口大小为N。发送方可以连续发送N个数据帧，而不需要等待确认。

2. 在最开始,发送方发送窗口内的N个数据帧.接受方维护一个大小为1的接受窗口,只接受按顺序到达的帧.

3. 在成功接受到一个按序到达的帧后,接收方发送一个确认(ACK)给发送方,并将接受窗口向前滑动一位.

4. 发送方在收到确认后,将发送窗口向前滑动相应的位数,并发送新的数据帧.

5. 如果某个帧出现了误码或者超时,接受方会直接丢弃这个帧,并发送上一个按序到达帧的确认(ACK).发送方在收到这个确认后,会重传从该帧开始的所有未被确认的帧.

累计确认

累计确认(Cumulative Acknowledgment)机制意味着接受方不必对每一个收到的帧都发送一个ACK,而是可以在收到连续的几个正确帧后,只发送一个ACK,确认所有这些帧都已正确收到. 一个对序号为n的帧的确认（ACK n）就隐含地确认了在n之前的所有帧。

例如,如果发送方收到了ACK2,它就知道序列号为0,1,2的帧都已经被正确接收了.这时,发送窗口可以顺势向后滑动3个位置,并发送新的帧.

例子from Gemini

假设发送窗口大小为4,接收窗口大小为1.

后退N帧协议(GBN)示例

1. 发送: 发送方连续发送帧0, 1, 2, 3, 4.

2. 接收与确认:

   • 接收方正确收到帧0, 发送ACK0。(这是一个常见的实现策略,尽管它也可以等待后续帧一起确认)
   • 接着, 接收方正确收到帧1, 发送ACK1.
   • 关键点: ACK0在传输过程中丢失了, 但ACK1成功到达发送方.

3. 累计确认生效:

   • 发送方收到ACK1. 根据累计确认原则, 这意味着帧0和帧1都已被正确接收.
   • 发送方将发送窗口向前滑动到2 (新的窗口基址是2), 并继续发送帧5, 6.

4. 发生错误与重传:

   • 帧2在传输中丢失.
   • 接收方接下来收到了帧3. 由于它期望收到的是帧2 (其接收窗口基址仍为2), 它发现帧3是失序的, 于是丢弃帧3.
   • 为了告知发送方它仍在等待帧2, 接收方重新发送了对已收到的最后一个按序帧的确认, 即ACK1.

5. 超时与回退:

   • 发送方发送完帧6后, 一直没有收到ACK2或更高的确认.
   • 最终, 帧2的计时器超时.
   • 发送方执行后退N(Go-Back-N)操作, 将发送窗口重置回帧2, 并重传从帧2开始的所有已发送但未确认的帧, 即重传帧2, 3, 4, 5, 6.

发送窗口的最大尺寸

假设我们用n比特对数据帧进行编号,也即,序列号的取值范围是0到2^n-1.例如,对于n=3

序列号取值范围

为了避免序列号重复带来的歧义,发送窗口的最大尺寸N必须满足: $$ 1 < N \leq 2^{n-1} $$

这是因为,如果发送窗口的大小N超过了2^(n-1),那么在发送完N个帧后,序列号就会回绕到之前已经使用过的值,从而导致接收方无法区分这些帧是新的还是旧的.

例如,发送方一次性发送了8个帧(假设n=3,N=8),序列号从0到7.接受方每接受到一个帧,就发送一个确认(ACK).在全部成功接受后,接受方的窗口已经滑动到了8(即0).

但如果ACK全部在传输的过程中丢失了,发送方在超时后,会重传从0开始的8个帧.此时,接受方无法区分这些帧是新的(8-15)还是旧的(0-7),从而导致错误.

假设发送窗口的大小为\(n\),即发送方可以连续发送\(n\)个帧而不需要等待确认.则分情况讨论信道利用率:

1. \(n T_t < T_t +RTT + T_{ack}\)

   这种情况下,发送方在发送完\(n\)个帧后,还没有收到第一个帧的确认(ACK).此时,信道利用率为:

   \[ U = \frac{n T_t}{RTT + T_t + T_{ack}} \]

2. \(n T_t \geq T_t +RTT + T_{ack}\)

   这种情况下,发送方在发送完\(n\)个帧前,已经收到了第一个帧的确认(ACK),这时发送窗口已经向后滑动.此时,信道利用率为:

   \[ U = 1 \]

选择重传协议(Selective Repeat, SR)

后退N帧协议在出现错误时,需要重传从错误帧开始的所有未被确认的帧,这会导致大量不必要的重传,从而降低传输效率.

选择重传协议通过只重传那些确实丢失或损坏的帧来提高效率.

SR相比于GBN,最大的不同就是接受窗口现在可以接收多个帧,而不仅仅是一个帧.这意味着接收方可以同时接收并缓存多个帧,从而提高了传输效率.

假设接受方的窗口大小为\(W_r\),发送方的窗口大小为\(W_s\),一共用n比特对帧进行编号,则必须满足以下条件:

\begin{align}

1 < W_r \leq W_s

W_r + W_s \leq 2^n

\end{align}

一般我们取\(W_r = W_s = 2^{n-1}\).

---

由于SR协议有更大的接受缓存窗口,接受方在接受到一个帧时,如果该帧在接受窗口内,则无论是否按序到达,都将其缓存起来,并发送一个确认(ACK)给发送方.只有当该帧是接受窗口的基址时,接受方才将其交付给上层,并将接受窗口向前滑动.

SR协议工作流程示例 (窗口大小=4, 序列号范围=8)

时间	事件	发送方 (Sender) 动作 / 状态	接收方 (Receiver) 动作 / 状态	备注
T1	发送方发送	发送方连续发送其窗口内的所有帧： - 发送 Frame 0 (启动 Timer 0) - 发送 Frame 1 (启动 Timer 1) - 发送 Frame 2 (启动 Timer 2) - 发送 Frame 3 (启动 Timer 3) 状态: S_base=0, S_next=4, UnACKed={0,1,2,3}	(等待中...)	发送方把窗口打满了。
T2	网络传输	(等待 ACK 中...)	(数据在路上...)	关键事件: - Frame 0 正常到达。 - Frame 1 丢失！ - Frame 2 正常到达。 - Frame 3 正常到达。
T3	接收方处理	(等待 ACK 中...)	1. 收到 Frame 0 (是R_base=0): - 发送 ACK 0 - 交付 Frame 0 给上层 - 窗口滑动: R_base=1, 范围={1,2,3,4} 2. 收到 Frame 2 (非R_base): - 发送 ACK 2 - 缓冲 Frame 2, Buffer={Frame 2} 3. 收到 Frame 3 (非R_base): - 发送 ACK 3 - 缓冲 Frame 3, Buffer={Frame 2, Frame 3}	SR核心(1): 接收方逐个确认收到的帧 (ACK 2, ACK 3)，并缓冲所有乱序但合法的帧。R_base 保持为 1。
T4	发送方处理 ACKs	1. 收到 ACK 0: - 停止 Timer 0, 标记 Frame 0 已确认 - 窗口滑动: S_base=1, 范围={1,2,3,4} - 发送 Frame 4 (启动 Timer 4) 2. 收到 ACK 2: - 停止 Timer 2, 标记 Frame 2 已确认 3. 收到 ACK 3: - 停止 Timer 3, 标记 Frame 3 已确认 状态: S_base=1, UnACKed={1, 4}	(等待 Frame 1...) 状态: R_base=1, Buffer={Frame 2, Frame 3}	SR核心(2): 发送方窗口的滑动被最早的未确认帧 (Frame 1) 卡住了。即使 2 和 3 都被确认了，窗口也不能滑过 1。
T5	发送方超时	... Timer 1 超时！ ... 1. 检查发现 Frame 1 仍未被确认。 2. 只重传 Frame 1 3. 重启 Timer 1 状态: S_base=1, UnACKed={1, 4}	(等待 Frame 1...)	SR核心(3): 选择性重传！发送方只重传超时的那一个帧 (Frame 1)，而不是像 GBN 那样重传 1, 2, 3, 4。
T6	接收方最终解决	(等待 ACK 1 和 ACK 4...)	1. 收到重传的 Frame 1: - 它是 R_base=1，是期望的帧！ - 发送 ACK 1 2. 处理并交付: - 交付 Frame 1 - 检查 Buffer, 按序交付 Frame 2, 3 (假设 Frame 4 也已到并缓冲) 3. 窗口滑动: - R_base 滑动到 5, 范围={5,6,7,0} - Buffer 清空	接收方一旦收到缺失的 Frame 1，就能把缓存中的所有帧按顺序 "解锁" 并交付给上层。
T7	循环继续	1. 收到 ACK 1 (来自 T6): 停止 Timer 1 2. (假设也收到了 ACK 4): 停止 Timer 4 - 所有 {1,2,3,4} 均已确认。 - S_base 滑动到 5。 - 窗口范围 = {5, 6, 7, 0} - 发送 Frame 5, 6, 7, 0	(等待 Frame 5...)	协议恢复正常运行。

点对点协议

点对点协议（PPP, Point-to-Point Protocol）是一种用于在两个直接连接的节点之间传输数据的协议。

PPP是目前广泛使用的数据链路层协议，它主要应用于以下两种场景：

1. 用户接入互联网：当用户通过拨号或宽带连接到互联网服务提供商（ISP）时，其计算机与ISP之间通常使用PPP协议进行通信。
2. 路由器间连接：在广域网中，连接两个路由器的专用线路也常使用PPP协议。

PPP是数据链路层协议,它提供了封装成帧、差错检测和可靠传输等功能.

PPP协议的三个组成部分

PPP协议由三个主要部分组成：

1. 封装方法：定义了如何将IP数据报等网络层分组封装到串行链路中。IP数据报作为PPP帧的数据部分，其长度受最大传送单元（MTU）的限制。

2. 链路控制协议（LCP, Link Control Protocol）：负责建立、配置、测试和终止数据链路连接。LCP还用于协商各种链路参数，如MTU大小、压缩算法等。

3. 网络控制协议族（NCP, Network Control Protocol）：PPP支持多种网络层协议（如IP、IPX等）。每种网络层协议都有一个对应的NCP，负责在该网络层协议和PPP链路之间建立和配置逻辑连接。例如，IP控制协议（IPCP）就是用于配置IP地址等参数的。

PPP的格式在上面已经介绍过,形如:

标志字段	地址字段	控制字段	协议字段	信息字段	FCS(帧校验序列)	标志字段
1字节	1字节	1字节	2字节	0~1500字节	2字节	1字节

标志字段组成了帧的边界,为了实现PPP帧的透明传输,有两种做法:

1. 面向字节的异步链路使用字节填充

   • 将数据载荷中的每一个0x7E减去0x20,变成0x5E,并在其前面添加一个转义字符0x7D.

   • 若数据载荷中包含转义字符0x7D,则同样在其前面添加一个转义字符0x7D,并将其变成0x5D.

   • 对于所有ASCII值小于0x20的控制字符,加上0x20,并在其前面添加一个转义字符0x7D.

2. 面向比特的同步链路使用比特填充

   • 在数据载荷中每连续出现5个1后,填充一个0.

以太网

以太网(Ethernet)是一种局域网技术,它定义了数据链路层和物理层的标准.

网络适配器

就是我们一般说的网卡

网络适配器负责将计算机内部的数据转换成适合在以太网中传输的格式,并将接收到的以太网数据转换回计算机内部的数据格式.因此,它既要与cpu通信,又要与以太网物理介质通信.

实际上实现的是物理层与数据链路层的功能

MAC地址

如果信号是点对点的传输,也就是说只有两个节点直接连接,那么不需要地址.

但是在以太网这种广播式的网络中,一个节点可能连接着多个节点,因此需要使用地址来区分不同的节点.在数据链路层,我们使用MAC地址(Media Access Control Address)来标识网络中的每个节点.

MAC地址位于帧的首部,包含了源MAC地址和目的MAC地址.每个MAC地址都是一个48位的二进制数,通常表示为6个十六进制数,每个十六进制数占8位(即一个字节),用冒号或连字符分隔.

---

MAC地址一般固化在网络适配器的只读存储器(ROM)中,因此每个网络适配器都有一个唯一的MAC地址.这种MAC地址被称为硬件地址或物理地址.

在IEEE 802标准中,MAC地址的格式如下

MAC地址格式

其中第一字节的最低有效位(LSB,Least Significant Bit)用于区分单播地址和多播地址,0为单播地址,1为多播地址.

第一字节的次低有效位用于区分全局唯一地址和本地管理地址,0为全局唯一地址,1为本地管理地址.

它们排列组合,组成的情况如下表所示:

第1字节的 b1位	第1字节的 b0位	MAC地址类型	地址占比	地址数量
0	0	全局单播地址	1/4	2^46
0	1	本地单播地址	1/4	2^46
1	0	全局多播地址	1/4	2^46
1	1	本地多播地址	1/4	2^46

评论