数据链路层

2023-12-12

第3章数据链路层

基本概念与功能
差错检测和纠正
- 纠错码
- 检错码
基本数据链路层协议
滑动窗口协议
- 回退N协议(出错全部重发协议)
- 选择重传协议
数据链路层协议实例
- 高级数据链路控制(HDLC)
  - HDLC 帧格式
- 点到点协议(PPP)
  - PPP 帧格式
  - 与HDLC比较

基本概念与功能

基本概念

链路：连接相邻节点的通信信道，中间没有任何其他的交换节点。 - 点对点链路：链路的两端都只有一个节点，一个节点发送，另一个节点接收，带宽独占。 - 点对多点链路（广播链路，共享链路）：链路上有多个节点，带宽共享，需要媒体访问控制(MAC)机制来控制多个用户对信道的访问。

通信方式： - 单工通信：指消息只能单方向传输的工作方式。 - 半双工通信：指数据可以沿两个方向传送，但同一时刻一个信道只允许单方向传送。 - 全双工通信：指在通信的任意时刻，两个节点间可以同时双向传输信号。
TDD(时分双工)是移动通信中上下行在同一频段上按照时间分配交叉进行传输。
FDD(频分双工)是指上下行在不同频段同时进行传输。

功能

数据链路层使用物理层提供的服务在通信信道上发送和接收比特。
1. 向网络层提供一个定义良好的服务接口。
2. 将物理层的比特流编成帧。 3. 处理传输错误。（差错控制）
4. 调节数据流，确保慢速的接收方不会被快速的发送方淹没。（流量控制）

提供给网络层的服务

无确认的无连接服务
源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。eg. 以太网
适用于错误率很低的场合及实时通信。
有确认的无连接服务
数据链路层仍然没有使用逻辑连接，但发送的每一帧都需要单独确认。eg. 802.11
适用于不可靠信道，如无线系统。
有确认的有连接服务
常用于广域网，如帧中继等。
数据传输经过三个阶段：
- 建立连接，双方初始化各种变量和计数器；
- 传输一个或多个数据帧，每一个帧都被编号，保证传送的帧被对方收到，且只收到一次；
- 释放连接。

成帧

将比特流拆分成多个离散的帧，为每个帧计算一个校验和，并将该校验和放在帧中一起传输。

字节计数法
利用头部中的一个字段来标识该帧中的字符数。

缺点：出错之后无法重新同步。
字节填充的标志字节法
在帧的起始和结尾用特殊的字节标志，这些特殊字节称为标志字节。

当标志字节出现在数据中时，发送方在出现的每个标志字节前插入一个特殊的转义字节，接收方的数据链路层在将数据传递给网路层之前删除转义字节。
如果转义字节出现在数据中，即用另一个转义字节填充。在接收方值删除第一个转义字节。

缺点：只能使用8比特的字节。
比特填充的标志比特法（位标志）
用特殊的位序列表示帧的起始和结尾，如01111110或0x7E。
每当发送方的数据链路层在数据中遇到连续5个1，就自动在输出的比特流中填入一个0。
当接收方看到5个连续入境的比特1，并且后面紧跟着一个比特0，就自动剔除这个比特0。

原始数据发送数据接收方存储数据

011011111110 0110111110110 011011111110

优点：确保了转换的最小密度，有助于物理层保持同步。eg. USB
缺点：和字节填充一样，受标志字节出现数量的影响，帧的长度取决于它所携带的数据内容。
物理层编码
在物理层用1.5或2个物理位表示一个数据位来表示帧的起始与结尾。

原始数据	发送数据	接收方存储数据
011011111110	0110111110110	011011111110

差错控制

要求接收方发回特殊的控制帧，在控制帧中对它所接收到的帧进行肯定或否定的确认。

当发送方发出一帧时，启动一个计时器。该计时器的超时值设置得足够长，保证在正常情况下该帧能够到达接收方，并且在接收方进行处理后再将确认返回到发送方。计时器超时后，发送方重新发送该帧。

发送方给发出去的帧分配序号，以便接收方根据序号来有效区分原始帧和重传帧。

流量控制

基于反馈的流量控制：接收方给发送方返回信息。
基于速率的流量控制：存在内置的机制，能限制发送方传输数据的速率，无需反馈信息。

差错检测和纠正

纠错码

一帧由 m 个数据位（信息）和 r 个冗余位（校验）组成。
块码：r 个校验位由与之相关的 m 个数据位的函数计算获得。
系统码：直接发送 m 个数据位，然后发出 r 个校验位。
线性码：r 个校验位是作为 m 个数据位的线性函数被计算出来的。

令数据块的总长度为 n，即 n = m + r。
n 位码字：一个包含了数据位和校验位的n位单元。
码率：码字中不包含冗余部分所占的比例，即 m/n。

海明码

海明距离：两个码字中不相同的位的个数。
码字集合的海明距离：码字集合中任意两个有效码字间的最小海明距离。

如果两个码字的海明距离为 d，则需要 d 个一位错误才能将一个码字转变成另一个。
为了可靠地检测d个错误，需要一个距离为 d+1 的编码方案（相邻码字的距离为 d+1）。
为了纠正 d 个错误，需要一个距离为 2d+1 的编码方案。

在给定 m 的情况下，纠正单个错误所需要的校验位数下界：
\[ (m + r + 1) \leq 2^r \]

以传输 1000001 为例：

发送方：

数据位为 7 位，计算 \((7 + r + 1) \leq 2^r\)，解得 r = 4，故编码共有 11 位。
海明码中，所有位从左到右由1开始依次编号，其中2的幂次方位是校验位，其余为数据位。
在本例中，第 1、2、4、8 位为校验位。
在校验位中先填上 0，其余位依次填充 1000001，即 00100000001。

将位的序号改写成 2 的幂次之和，即换算成二进制形式。校验位覆盖二进制形式序号对应位为 1 的数据位。
即第 1 位校验第 (1, 3, 5, 7, 9, 11) 位，第 2 位校验第 (2, 3, 6, 7, 10, 11) 位，第 4 位校验第 (4, 5, 6, 7) 位，第 8 位校验第 (8, 9, 10, 11) 位。

将每个校验位所覆盖的位对应的值逐一异或，即可得到该校验位应该填入的值:
第 1 位: \(0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0\)
第 2 位: \(0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0\)
第 4 位: \(0 \oplus 0 \oplus 0 \oplus 0 = 0\)
第 8 位: \(0 \oplus 0 \oplus 0 \oplus 1 = 1\)

序号	二进制形式 8421	计算前的值	发送的值
1	0001	0	0
2	0010	0	0
3 = 1+2	0011	1	1
4	0100	0	0
5 = 1+4	0101	0	0
6 = 2+4	0110	0	0
7 = 1+2+4	0111	0	0
8	1000	0	1
9 = 1+8	1001	0	0
10 = 2+8	1010	0	0
11 = 1+2+8	1011	1	1

故发送的码字为 00100001001。

接收方：
- 假设传输过程中发生错误，收到的码字为 00101001001。
- 重新计算校验位：
  第 1 位: \(0 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \oplus 1 = 1\)
  第 2 位: \(0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0\)
  第 4 位: \(0 \oplus 1 \oplus 0 \oplus 0 = 1\)
  第 8 位: \(0 \oplus 0 \oplus 0 \oplus 1 = 1\)
- 将重新计算得到的校验位与收到码字中的校验位比较（位数从高到低排列）。
  即将 1101 与 1000 按位异或，得到 0101 (即二进制形式的 5)。
  这意味着同时被第 1、4 位覆盖的位发生了错误，即第 5 位发生了错误。
  将该位反转可以得到正确的码字：00100001001。

from zy：

海明码的编码距离为 3。
海明码可以检出所有\(\leq 2\) 比特的错误，且可以纠正 1 比特错误。

卷积码

编码器有内存，处理一个输入位序列并生成一个输出位序列。
约束长度：决定当前输出的以前输入位数。
卷积码由它们的速率和约束长度来标识。

里德所罗门码

线性块码，往往也是系统码。

基于m位符号（1位错误和m位突发错误都只作为一个出错的符号处理）。
加入2t个冗余符号后，能够纠正传输符号中的任意t个错误。

低密度奇偶校验码(LDPC)

线性块码。

每个输出位由一小部分的输入位形成。接收到的码字通过一个近似算法解码获得。

检错码

以下检错码均为线性的系统块码。

奇偶

奇校验/偶校验：将所有位逐一异或，得出结果为 0 说明该码字中共有偶数个 1；偶校验则再填入一个 0，奇校验则再填入一个 1。
可以检出1位错误。

plus版：将发送的每个数据块作为一个n位宽和k位高的长方形矩阵来处理。
交错检验：以不同于数据位发送的次序来计算校验位。

为n列中的每列计算校验位，按k行发送全部的数据位，发送次序是从上到下发送每一行，行内数据位通常按从左到右的次序发送，在最后一行发送n个校验位。
这种方法对于nk长度的数据块使用了n个校验位，可以检出一个长度小于等于n的突发错误。

校验和

通常指与信息相关的一组校验位。

Internet校验和
按16位字计算得出的消息位总和，后续的 IP 头中包含有具体计算方法。
缺点：检测不到0数据的增加或删除；检测不出消息中被替换的部分；对两个数据包拼接起来的消息只有弱保护作用。
Fletcher校验和
包括一个位置组件，将数据和其位置的乘积添加到总和中。

循环冗余校验码(CRC) / 多项式编码

将位串看作系数是0或1的多项式。一个k位帧看作是一个k-1次多项式，从\(x^{k-1}\)到\(x^0\)。

运算规则：加法和减法都等同于异或。

假设一帧有m位，对应于多项式\(M(x)\)
生成多项式：\(G(x)\)

计算CRC的算法：
- 假设\(G(x)\)的阶为r。在帧的低位端加上r个0位，对应多项式\(x^r M(x)\)。
- 利用模2除法，用对应于\(x^r M(x)\)的位串除以对应于\(G(x)\)的位串。
- 利用模2减法（实际上就是异或），从对应于\(x^r M(x)\)的位串中加上余数。结果就是将被传输的带校验和的帧，其多项式记为\(T(x)\)。
- 如果收到的多项式可以除尽生成多项式，则证明传输正确。

eg.
帧：1101011111 对应多项式 \(M(x) = x^9 + x^8 + x^6 + x^4 + x^3 + x^2 + x + 1\)
生成多项式：10011 对应 \(G(x) = x^4 + x + 1\)
用 \(x^4 M(x) \div G(x)\)，得到商为 1100001110、余数为 10。
发出的帧对应多项式 \(T(x) = x^4 M(x) + x\)，即发送的帧为 11010111110010。
此时 \(T(x)\) 可以被 \(G(x)\) 整除。

带r个校验位的多项式编码可以检测到所有长度小于等于r的突发错误。
当突发错误的长度为r+1时，通过检测的概率是\(\dfrac{1}{2^{r-1}}\)。
当突发错误的长度大于r+1或者几个短突发错误发生时，通过检测的概率为\(\dfrac{1}{2^r}\)。

eg. 几乎所有的局域网（以太网/802.11）和点到点链接（SONET上的数据包）。

基本数据链路层协议

无限制的单工协议

理想条件：
- 数据单向传输，收发双方的网络层一直处于就绪状态。
- 处理时间可忽略不计，接收缓冲空间无限大（无需任何流量控制）。
- 信道不会损坏或丢失帧（无需任何差错控制）。

发送过程：运行在源机器的数据链路层上。
- 从（总是就绪的）网络层获取一个数据包。
- 构造一个出境帧。
- 通过物理层发送该帧。

接收过程：运行在目标机器的数据链路层上。
- 等待事件（到达了一个完好无损的帧）发生。
- 帧到达后，将新到达的帧从硬件缓冲区中删除，并放到一个变量中。
- 将该帧的数据部分传递到网络层。

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

停-等式协议：发送方发送一帧，等待对方确认到达后才能继续发送。

条件：与理想条件不同的是，接收端需要一定的接收处理时间，接收缓冲只能存放一个帧。

为了防止发送快于接收而造成数据丢失，发送端发送一帧后必须停止发送，等待接收端发回的反馈确认。
接收端在收到一个帧并发送网络层后，需向发送端发一反馈确认短帧，表示可发新帧。
由于需要反馈，且帧的发送和反馈是严格交替进行的，所以相当于采用半双工信道。

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

自动重复请求(ARQ) / 带有重传的肯定确认(PAR)：发送方在前移到下一个数据之前必须等待一个肯定确认的协议。

条件：与无错信道上的条件不同的是，通信信道可能会出错，帧可能被损坏，也可能完全被丢失。

增加一个计时器。
应保证超时值足够长，确保帧到达接收方，按照最坏的情形被接收方所处理，然后确认帧被返回发送方所需要的全部操作时间。
增加一位序号。

发送过程： - 发送方在发出一帧后启动计时器。如果计时器已经在运行，则将它重置。 - 发送方等待相关事件发生。 - 如果到达了一个有效的确认帧，则发送方从它的网络层获取下一个数据包，并将它放入缓冲区覆盖掉原来的数据包，同时递增（0变1，1变0）帧的序号。
- 如果到达了一个受损的确认帧，或者计时器超时，则缓冲区和序号都不做任何改变。
- 发送缓冲区的内容。

接收过程：
- 一个有效帧到达时，接收方检查它的序号，确认是否为重复数据包。
- 如果不是重复数据包，则接收该数据包并传给网络层，然后生成一个确认帧。
- 如果是重复帧或受损帧，则不传递给网络层，且重复发送最后一个正确接收到的数据帧的确认。

滑动窗口协议

允许发送站连续发送多个帧而不需等待确认的做法称作管道化，属于一种窗口机制。

捎带确认：暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术。
当一个按正常次序发送的数据帧到达接收方后，接收方启动一个辅助计时器。如果在计时器超时前，没有出现需要发送的反向流量，则发送一个单独的确认帧。
辅助计时器的超时间隔应明显短于与数据帧关联的计时器间隔。

累计确认：当n号帧的确认到达，n-1号帧/n-2号帧等都会被自动确认。
因此再实际网络中，ACK = n 一般表示现在期望接收第 n 号帧。

发送窗口尺寸：允许连续发送的帧的数量。
如果最大窗口为n，则发送方需要n个缓冲区来存放未被确认的帧，以满足可能的重传需要。

发送窗口：发送端允许不等确认而连续发送的帧的序号表。
当发送端收到发送窗口下沿帧的肯定确认时，将发送窗口整体向前滑动一个序号，并从输出缓冲区中将相应的数据帧副本删除。

接收窗口：接收端允许接收的帧的序号表。
- 对于落在窗口外面的帧：丢弃。 - 对于在窗口内但不是接收窗口下沿的帧：暂存在输入缓冲区
- 对于接收窗口下沿帧：将其连同后面连续的若干个检验过的正确帧按顺序交给网络层，在发回确认帧的同时将接收窗口向前滑动相应的数量。

发送窗口和接收窗口不必有相同的上下界，也不必有相同的大小。

带宽-延迟乘积：
\[ BD = 单向延迟 \times 带宽 \]
单项延迟的单位为s，带宽单位为bps，将乘积除以一帧对应的比特数，从而得到 BD 的单位为帧。

假设发射窗口为 w（帧）：
\[ 链路利用率 \leq \dfrac{w}{2BD + 1} \]

回退N协议(出错全部重发协议)

发送窗口的尺寸大于1，接收窗口的尺寸等于1。
发送端需要为每个待确认的帧都各自设置一个定时计数器。

接收端只能按顺序接受数据帧。
不在接收窗口内的帧到达时直接丢弃，不返回确认。
最终发送方超时并重新发送所有未被确认的帧。

如果帧序号用 n 位编码，则发送窗口尺寸为 \(MAX\_SEQ \leq 2^n - 1\)，即存在 \(MAX\_SEQ + 1\) 个不同的序号。否则会造成接收端无法分辨新旧数据帧。

出错全部重发协议只要求发送端保持一定数量的缓存来保存没有确认的数据帧，对接收端没有缓存的要求。但在误码率高的情况下，会大大降低信道的利用率。

选择重传协议

发送和接收窗口的尺寸都大于1。

非顺序接收。接收端可存储坏帧之后的其它数据帧（落在接收窗口），接收端对错帧发否定确认帧 (NAK)，因此发送端只需重发出错的帧，而不需重发其后的所有后续帧。接收端正确收到重发的帧后，可对其后连续的已接收的正确帧作一次总体确认（累计确认），并交送网络层。

接收窗口的尺寸不能超过 \(2^{n-1}\) (n 同样表示编码位数)，即序号空间的一半，否则可能造成帧的重叠。
发送窗口的尺寸一般和接收窗口的尺寸相同（两者相加 \(\leq 2^n\)）。

接收方所需缓冲区的数量等于窗口的大小。假设有n号缓冲区，当第i号帧到达时，它被放到 (i mod n) 号缓冲区中。
发送端为每一个输出缓存区设置一个定时计数器，需要定时器的数量等于缓冲区的数量。定时器一旦超时，相应输出缓存区中的帧就被重发。