Skip to content

数据链路层

:material-circle-edit-outline: 约 2985 个字 :material-clock-time-two-outline: 预计阅读时间 10 分钟

网络中的主机、路由器等都必须实现数据链路层

image-20241010170536575

数据链路层信道类型

image-20241010170609855

使用点对点信道的数据链路层 - 数据链路和帧

  • 链路 (link) /物理链路
    • 一条无源的点到点的 物理线路段，中间没有任何其他的交换结点
  • 数据链路 (data link)/逻辑链路
    • 把实现控制数据传输的协议的硬件和软件加到链路上，就构成了数据链路，比如网卡

数据链路层协议数据单元：帧 frame

image-20241010171119312

  • 封装成帧 (framing)：在一段数据的前后分别添加首部和尾部，构成一个帧。
    • 首部和尾部的一个重要作用就是进行帧定界（即确定帧的界限）

数据链路层还需要处理传输中的差错，控制发送速率不大于接收方的处理速率

分组 (packet) 与 帧(frame)的关系

image-20241011104938747

成帧（framing）的方式

如何标识一个帧的开始？帧同步或帧定界问题

字节计数法（ Byte count ）

image-20241011105228634

如果某个计数字节出错会破坏帧的边界，导致一连串帧的错误

带字节填充的定界符法( byte-stuffing)

定界符（FLAG）：一个特殊的字节，比如 01111110，即 0x7E，用于区分前后两个不同的帧

image-20241011105423512

为避免有效载荷出现与 FLAG 一样的比特串导致错误，我们定义所谓的转义字节 ESC，并在 framing 时，在有效载荷里 进行以下填充操作：

  • 原来的 FLAG 前加一个 ESC
  • 原来的 ESC 前加一个 ESC

image-20241011105803892

接收方的逐个检查收到的每一个字节：

  • 收到 ESC 则后一字节无条件成为有效载荷，不予检查
  • 收到 FLAG 则为帧的边界

这种方法过于冗余了

带比特填充的定界符法(bit stuffing)

定界符：两个 0 比特之间夹进 6 个 1 比特，即 01111110，0x7E

image-20241011110152844

  • 发送方检查有效载荷，若在有效载荷中出现连续 5 个 1，则直接在末尾插入 1 个 0

image-20241011110311193

  • 接收方的处理时，若出现连续 5 个 1
    • 若下一比特为 0，则为有效载荷，直接丢弃 0
    • 若下一比特为 1，则连同后一比特的 0，构成定界符，一帧结束

image-20241011110509618

透明传输

透明指某一个实际存在的事物看起来却好像不存在一样。

“在数据链路层透明传送数据” 表示：无论发送什么样的比特组合的数据，这些数据都能够 按照原样 没有差错地通过这个数据链路层。

差错检测和纠正

保证一定差错检测和纠错能力的前提下，减少冗余信息量

两种主要策略

  • 检错码（error-detecting code）
    • 增加冗余信息，只能使接收方推断是否发生错误，但不能推断哪发生错误，接收方可以请求发送方重传数据
  • 纠错码（error-correcting code)
    • 接收方能够判断接收到的数据是否有错，并能纠正错误（定位出错的位置）

新概念

  • 码字 (code word)：一个包含 m 个数据位和 r 个校验位的 n 位单元
    • 描述为 (n, m) 码，n = m+r
  • 码率 (code rate)：码字中不含冗余部分所占的比例，可以用 m/n 表示
  • 海明距离 (Hamming distance)：两个码字 对应位置 bit 不一样 的数目
    • 0000000000 与 0000011111 的海明距离为 5
    • 如果两个码字的海明距离为 d，则需要最少 d 个单比特错就可以把一个码字转换成另一个码字

检错码（error-detecting code）

奇偶校验 (Parity Check)

1 位奇偶校验：增加 1 位校验位，可以检查奇数位错误

image-20241011112759815

校验和 (Checksum)

image-20241011112949015

发送方将两个 16 bit 相加，再加 1，再取反，作为校验和

接收方将两个 16 bit 相加，再加 1，再加上校验和，结果全 1 就说明这 32 bit 没问题

循环冗余检验 CRC (Cyclic Redundancy Check) 原理

在发送端，先把数据划分为组。假定每组 k 个比特。

CRC 运算在每组 M 后面再添加供差错检测用的 n 位冗余码，然后构成一个帧发送出去，一共发送 (k + n) 位

image-20241010172746386

CRC 冗余码的计算

CRC 冗余码用的除法是模 2 除法，就是每个 bit 进行异或运算，不是减法运算卧槽

  1. 在原始数据 M 后面添加 n 个 0。
  2. 除以事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q ，余数是 R
    • 注意到余数 R 比除数 P 少 1 位，即 R 是 n 位。
  3. 将余数 R 作为冗余码拼接在数据 M 后面，一起发送出去。

image-20241010172856089

接受方将接受的数据除以 P，余数为 0 则没问题

用循环冗余检验 CRC 差错检测技术能做到无差错接受 (accept)，即凡是接收端数据链路层接受的帧均无差错。

纠错码（error-correcting code)

纠正单比特错误校验位数的下界

什么鬼玩意儿

m 个信息位，r 个校验位，纠正单比特错，对 \(2^m\) 个有效信息中任何一个，有 n 个与其距离为 1 的无效码字

以考虑将该信息对应的合法码字的 n 位逐个取反，得到 n 个距离为 1 的非法码字，需要 n+1 个位模式来标识

因此有：\((n + 1) 2^m \le 2^n\)

利用 \(n = m + r\)，得到 \((m + r + 1) \le 2^r\)

在给定 m 的情况下，利用该式可以得出纠正单比特错误校验位数的下界

海明码

以奇偶校验为基础，如何找到出错位置，提供 1 位纠错能力

以 (15, 11)海明码为例，11 比特的数据 01011001101 按顺序放入数据位

校验位：2 的幂次方位（记为 p1, p2, p4, p8），每个校验位对自己负责的数据子集做奇偶校验，缩小定位错误的范围

image-20241011120434037

各校验位负责的自己如下图所示（浅紫色）

image-20241011120546529

如果发送过程中第 7 位出现差错，从 1 变成 0

组 1 和组 2 的校验结果可定位错误位于第 4 列

image-20241011121310114

组 3 和组 4 的校验结果可定位错误位于第 2 行

image-20241011121302378

[!NOTE] even-parity & odd-parity

Hamming 码可以分为两种类型：even-parity Hamming code 和 odd-parity Hamming code

在 even-parity Hamming code 中，校验位将被设置为使得包括它自己的所有位的 1 的个数是偶数，如果数据位中已经有偶数个 1，校验位就设为 0；如果数据位中有奇数个 1，校验位就设为 1

在 odd-parity Hamming code 中，校验位将被设置为使得包括它自己的所有位的1的个数是奇数。如果数据位中已经有奇数个 1，校验位就设为 0；如果数据位中有偶数个 1，校验位就设为 1

基本的数据链路层协议

乌托邦式单工协议

  • 假设：乌托邦，完美但不现实的协议
  • 单工（Simplex）协议：数据单向传输
  • 不处理任何流量控制或纠错工作

无错信道上的停等式协议

  • 假设：通信信道不会出错（Error-Free）
  • 假设：数据传输保持单向, 但是需要双向传输链路（半双工物理信道）
  • 停-等式协议（stop-and-wait）
    • 发送方发送一帧后暂停，等待确认（Acknowldgement）到达后发送下一帧
    • 接收方完成接收后，回复哑帧（dummy frame）确认接收

有错信道上的单工停等式协议

  • 假设：通信信道可能会出错，帧会损坏但接收方能检测出来，帧会丢失
  • 发送方增加一个 计时器(timer)，等待 ACK，超时重发
  • 序号（SEQ：sequence number）
    • 发送方在帧头放一个序号，接收方由此判断这是个新帧还是应该被丢弃的重复帧。
    • ACK 丢失时，会超时重发重复帧，以此解决

效率的评估

一周总结(二) | ChangL-Blog

  • 基础信息

    • F = frame size (bits)
    • R = channel capacity (Bandwidth in bits/second)
    • I = propagation delay + processor service time (second)

  • 指标

    • 每帧发送时间 (Time to transmit a single frame) = F/R
    • 总延迟 (Total Delay) = D = 2I
    • 停止等待协议的发送工作时间是 F/C，空闲时间是 D
    • 信道利用率 (line utilization)= \(\frac{F}{F+RD}\)
      • 当 F < D 时：信道利用率 < 50%

例如，每一帧的发送时间是 1 毫秒 ( 1000 bits/(1,000,000 bits/sec）)

由于传播延迟较长，发送者在 541 毫秒之后才能收到确认，信道利用率 1/541

一种提高效率的方法：使用更大的帧，但在传输中出错的概率越高，将导致更多的重传

滑动窗口协议

stop-and-wait 机制降低了信道利用率，我们寻找更高效的协议

改进思路：流水线协议/管道协议，即允许发送方在没收到确认前连续发送多个帧

窗口机制：发送方和接收方都具有一定容量的缓冲区，即窗口，发送端在收到确认前可发送多个帧

  • 滑动窗口协议
    • 对可以连续发出的最多帧数（已发出但未确认的帧）作限制
    • 循环重复使用有限的帧序号
    • 接收窗口驱动发送窗口的转动
      • 发送窗口：其大小记作 \(W_T\)，表示在收到对方确认的信息之前，可以连续发出的最多数据帧数
      • 接收窗口：其大小记作 \(W_R\) ，为可以连续接收的最多数据帧数
    • 累计确认：不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认

image-20241017102750246

image-20241017102803198

下面为一些具体的滑动窗口协议

回退 N 协议 go back N

接收窗口为 1 的情况，即只能按顺序接收帧

思路：一个出错全部重发

  • 当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，且不为这些帧发送确认
  • 发送端超时后，重传所有未被确认的帧

当发送方发送了 N 个帧后，若发现该 N 帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就重新发送出错帧及其后的 N 帧。

image-20241017103238659

出错全部重发时，若帧序号为 n 位，接收窗口 \(W_R=1\)，发送窗口 \(W_T ≤ 2^n－1\)

发送窗口收到 ACK 后移动，始终保持窗口里有 \(W_T\) 个 PDU 未确认

发现错误时整个窗口重发，超时也全部重发

  • 如果发送包丢失，接收方会把同一窗口下丢失包后面的所有包的 ACK 改成丢失包前一个已收到的包的 ACK，表示丢失包丢失了
  • 如果是 ACK 丢失，但丢失的 ACK 后面的 ACK 都是正常的，那说明接收方没有丢失，就不用管

选择重传协议(Selective Repeat)

若发送方发出连续的若干帧后，收到对其中某一帧的否认帧，或某一帧的定时器超时， 则只重传该出错帧或计时器超时的数据帧

接收方窗口可以大于 1，帧出错要发否认帧 NAK，NAK 让发送方重发帧

帧丢失处理流程如下

  • 如果发送帧丢失，无对应的 ACK 返回，而发送窗口后端必须在接受 ACK 后才移动，这样丢失的包会卡住发送窗口，最后超时重发
  • ACK 丢失，处理流程一致，超时重发，然后 ACK 重发

发送窗口的尺寸：\(W_T ≤2^{n-1}\), 发送窗口应等于或小于序号空间的一半

maximum number of outstanding sending frames =

*3.5 数据链路协议实例

PPP 协议 (Point-to-Point Protocol)

image-20241017110611559

11:16