【计算机网络】第三章：数据链路层（上）-EW帮帮网

本篇笔记课程来源：王道计算机考研计算机网络

接下节：【计算机网络】第三章：数据链路层（下）

一、数据链路层的功能

1. 基本概念

使用物理层提供的 “比特传输” 服务
为网络层提供服务，将网络层的 IP 数据报（分组）封装成帧，传输给下一个相邻结点
物理链路：传输介质（0 层）+ 物理层（1 层）实现了相邻结点之间的物理链路。
逻辑链路：数据链路层需要基于物理链路，实现相邻结点之间逻辑上无差错的 “数据链路（逻辑链路）”

2. 功能总览

封装成帧（组帧）
- 帧定界：如何让接收方能够确定帧的界限
- 透明传输：接收方链路层要能从收到的帧内恢复原始 SDU（服务数据单元），让网络层感受不到将分组封装成帧的过程
差错控制，发现并解决一个帧内部的位错：
- 方案一：接收方发现比特错后丢弃帧，发送方重传帧（仅需采用 检错编码）
- 方案二：由接收方发现并纠正比特错误（需采用 纠错编码）
可靠传输，发现并解决帧错
- 帧丢失
- 帧重复
- 帧失序
流量控制：控制发送方发送帧的速率别太快，让接收方来得及接受
介质访问控制
- “广播信道” 需要实现此功能。广播信道在逻辑上是总线型拓扑，多个结点需争抢传输介质的使用权
- “点对点信道” 通常不需要实现此功能。点对点信道通常意味着两个结点之间有专属的传输介质，不用抢

二、组帧（封装成帧）

1. 主要实现

帧定界：如何让接收方能够确定帧的界限
透明传输：接收方要能够去除 “帧定界” 的附加信息，把帧 “恢复原貌”
帧由首部、数据部分、尾部构成：
- 首、尾主要是一些控制信息，如：帧定界信息、校验码、帧类型、帧序号等

2. 字符计数法

原理：在每个帧开头，用一个定长计数字段（比如 8 位二进制）表示帧长
帧长 = 计数字段长度 + 帧的数据部分长度
- 计数字段长度为 1 字节，数据部分长度为 6 字节，则帧长为 7 字节，计数字段为 00000111
最大缺点：任何一个计数字段出错，都会导致后续所有帧无法定界

3. 字节填充法

使用 ASCII 控制字符：
- SOH，Start of Header，报头开始，0x01
- EOT，End of Transmission，传输结束，0x04
- ESC，Escape，换码（转义、溢出），0x1B
如果帧的数据部分包含 “特殊字符”，则发送方需要在这些 “特殊字符” 前填充 “转义字符 ESC”（接收方要做逆处理）

4. 零比特填充法

使用特殊的比特串 0x7E 标记帧开始、帧结尾
发送方需要对帧的数据部分进行处理，每当遇到连续 5 个 1，就填充一个 0
接收方需要对帧的数据部分进行逆处理，每当遇到连续 5 个 1，就删掉后面的一个 0
HDLC、PPP 协议使用的是零比特填充法组帧

5. 违规编码法

使用违规信号，表示帧的开头和结尾，该方法需要物理层的配合
例如采用曼彻斯特编码时，使用 “中间不跳变” 作为 “违规信号”，标记帧的开头、结尾

三、差错控制

1. 主要实现

发现并解决一个帧内部的 “位错”
异或（模 2 加）运算：两比特相异时，结果为 1，否则为 0
- 0 ⊕ 0 = 0
- 0 ⊕ 1 = 1
- 1 ⊕ 0 = 1
- 1 ⊕ 1 = 0

2. 检错编码

接收方发现比特错后丢弃帧，并同志发送方重传帧

Ⅰ. 奇偶校验码

在这里插入图片描述

奇校验码：整个效验码（有效信息位和校验位）中 “1” 的个数为奇数
偶校验码：整个效验码（有效信息位和校验位）中 “1” 的个数为偶数。
- 发送方：所有位进行异或运算，得到的结果即为偶校验码。
- 接收方：所有位进行异或运算，若结果为 1 说明出错。
缺点：奇偶校验码仅能检测出奇数位错误，无纠错能力。

给出两个编码 1001101 和 1010111 的奇校验码和偶校验码
设最高位为校验位，余 7 位是信息位，则对应的奇偶检验码为：
奇校验：11001101、01010111
偶校验：01001101、11010111

Ⅱ. 循环冗余校验码

在这里插入图片描述

也叫 CRC 码（Cyclic Redundancy Check）
基本思想：数据发送、接收方约定一个 “除数”。 $K$ 个信息位 + $R$ 个检验位作为 “被除数”，添加校验位后需保证除法的余数为 0。接收方收到数据后，进行除法检查余数是否为 0，若余数非 0 说明出错，则进行重传或纠错。
如何构造

设生成多项式为 $G(x)=x^3+x^2+1$ ，信息码为 101001
1. 确定 $K 、 R$ ：
  $K$ = 信息码的长度 = 6， $R$ = 生成多项式最高次幂 = 3，校验码位数 $N = K + R = 9$
2. 确定生成多项式对应的二进制码
  生成多项式 $G(x)=1×x^3+1×x^2+0×x^1+1×x^0$ ，对应二进制码 1101
3. 移位
  信息码左移 $R$ 位，低位补 0
4. 相除
  对移位后的信息码，用生成多项式进行模2除法，产生（3 位 $R$ 位）余数 001。对应的 CRC 码为 101001 001。 $\begin{array}{r} 110101\\ 1101\overline{|101001000}\\ \underline{1101\;\,\quad\quad}\\ 1110\quad\;\;\;\,\\ \underline{1101\quad\;\;\,\,}\\ 0111\quad\;\,\\ \underline{0000\,\;\;\,\,\;}\\ 1110\quad\\ \underline{1101\;\;\,\,}\\ 0110\,\,\,\\ \underline{0000\,\,}\\ 1100\\ \underline{1101\!}\\ 001 \end{array}$

如何检错
- 接收方收到 101001001，用 1101 进行模 2 除，余数为 000，代表没有出错。余数非 0，代表出错。
- 可检测出所有奇数个错误
- 可检测出所有双比特的错误
- 可检测出所有小于等于检验位长度的连续错误

如何纠错
- 只用来检错，不会用来纠错，但是具有纠错能力
- $K$ 个信息位， $R$ 个检验位，若生成多项式选择得当，且 $2^R≥K+R+1$ ，则 CRC 码可纠正 1 位错

3. 纠错编码

由接收方发现并纠正比特错误

Ⅰ. 海明校验码

思路：将信息位分组进行偶校验，每个分组对应一个校验位，通过校验位标注出错位置。
纠错能力为 1 位，检错能力为 2 位。
需要多少校验位？
- 设信息位 $n$ 位，校验位 $k$ 位
- 由 $k$ 位校验位可表示 $2^k$ 种状态
- 则 $2^k≥n+k+1$ （一种正确状态）
n 1 2-4 5-11 12-26 27-57 58-120

k 2 3 4 5 6 7
有信息位 1010
- 已知 $n$ 为 4，由 $2^k≥n+k+1$ 可知， $k$ 为 3。

n	1	2-4	5-11	12-26	27-57	58-120
k	2	3	4	5	6	7

检验位的分布
- 检验位 $P_i$ 放在海明码位号为 $2^{i-1}$ 的位置
- 信息位按顺序放到其余位置
- 比如： $P_1$ 放在第 $2^{1-1}=1$ 的位置， $P_3$ 放在第 $2^{3-1}=4$ 的位置
由上可知，信息位 4 位 1010，校验位有 3 位。
- $P_1$ 放在位置 1， $P_2$ 放在位置 2， $P_3$ 放在位置 4
- $\begin{array}{|c|c|c|c|c|c|c|} \hline H_7 & H_6 & H_5 & H_4 & H_3 & H_2 & H_1 \\ \hline D_4 & D_3 & D_2 & P_3 & D_1 & P_2 & P_1 \\ \hline 1 & 0 &1 &&0 \\ \hline \end{array}$

求校验位值
- 将信息位的位置序号用 $k$ 位二进制数表示出来
- 检验位 $P_i$ 与位置序号二进制数第 $i$ 位为 1 的信息位归为同一组，进行偶校验
由上可知，信息位的位置序号有 3、5、6、7，转为二进制数为
3： 0    1    1
5： 1    0    1
6： 1    1    0
7： 1    1    1
      P₃ P₂ P₁
- $P_1=H_3⊕H_5⊕H_7=D_1⊕D_2⊕D_4=0⊕1⊕1=0$
- $P_2=H_3⊕H_6⊕H_7=D_1⊕D_3⊕D_4=0⊕0⊕1=1$
- $P_3=H_5⊕H_6⊕H_7=D_2⊕D_3⊕D_4=1⊕0⊕1=0$
- $\begin{array}{|c|c|c|c|c|c|c|} \hline H_7 & H_6 & H_5 & H_4 & H_3 & H_2 & H_1 \\ \hline D_4 & D_3 & D_2 & P_3 & D_1 & P_2 & P_1 \\ \hline 1 & 0 &1 &0&0&1&0 \\ \hline \end{array}$

求全校验位
- 为了区分是 1 位错还是 2 位错，需要对整体进行偶校验
由上可知，海明码为 1010010，加上全校验位后为 11010010
- $\begin{array}{|c|c|c|c|c|c|c|c|} \hline H_全&H_7 & H_6 & H_5 & H_4 & H_3 & H_2 & H_1 \\ \hline P_全& D_4 & D_3 & D_2 & P_3 & D_1 & P_2 & P_1 \\ \hline 1&1 & 0 &1 &0&0&1&0 \\ \hline \end{array}$

纠错
- 对 $P_1、P_2、P_3...$ 所属各分组进行异或（分组偶校验），求得 $S_1、S_2、S_3...$
- $S$ 全为 0 且全体偶校验成功，说明无错误
- $S$ 不全为 0 且全体偶校验失败，说明有 1 位错误，纠正即可
- $S$ 不全为 0 且全体偶校验成功，说明有 2 位错误，需要重传
- 海明码检错能力只有 2 位，因此如果位错 ≥ 3 则需另外讨论
已知正确的海明码为 11010010，若接收方接收到 11010000，然后进行检错和纠错：
- $S_1=P_1⊕D_1⊕D_2⊕D_4=0⊕0⊕1⊕1=0$
- $S_2=P_2⊕D_1⊕D_3⊕D_4=0⊕0⊕0⊕1=1$
- $S_3=P_3⊕D_2⊕D_3⊕D_4=0⊕1⊕0⊕1=0$
- 全体偶校验结果为 1
- 因此 $S_3S_2S_1$ 为 010，说明只有 1 处错误，第 2 位出错，纠正即可。

四、流量控制、可靠传输

1. 相关机制

Ⅰ. 滑动窗口机制

发送窗口（ $W_T$ ，Window Transmit）：发送方当前允许发送的帧。
- 发送窗口之外的帧，暂不允许发送
接收窗口（ $W_R$ ，Window Receive）：接收方当前允许接收的帧。
- 若收到接收窗口之外的帧，直接丢弃
由接收方通过 “确认机制” 控制发送方的窗口向前滑动，从而实现 “流量控制”
以下三种协议，本质上都是滑动窗口机制：
1. 停止-等待协议（S-W）：发送窗口 $W_T=1$ ，接收窗口 $W_R=1$
2. 后退 N 帧协议（GBN）：发送窗口 $W_T>1$ ，接收窗口 $W_R=1$
3. 选择重传协议（SR）：发送窗口 $W_T>1$ ，接收窗口 $W_R>1$

Ⅱ. 确认机制

确认帧（ $ACK_i$ ，Acknowledge）：若接收方收到 $i$ 号帧，且没有检测出 “差错”，需要给发送方返回确认帧 $ACK_i$
否认帧（ $NAK_i$ ，Negative-Acknowledge）：若接收方收到 $i$ 号帧，但检测出 $i$ 号帧有 “差错”，需要丢弃该帧，并给发送方返回否认帧 $NAK_i$ 。

Ⅲ. 重传机制

超时重传：若发送方超时未收到 $ACK_i$ ，则重传 $i$ 号帧
请求重传：若发送方收到 $NAK_i$ ，则重传 $i$ 号帧

Ⅳ. 帧编号

为了支持以上机制正确运行，至少需要用 $n$ bit 给帧编号
要求： $W_T+W_R≤2^n$
如果没有帧编号，接收方无法判别重复帧。

2. 停止-等待协议

停止-等待协议（S-W，Stop-Wait）
- 滑动窗口机制：发送窗口 $W_T=1$ ，接收窗口 $W_R=1$
- 确认机制：确认帧 $ACK_i$
- 重传机制：超时重传
- 帧编号：已知 $W_T+W_R≤2^n$ ，因此仅需 1 bit （0、1）给帧编号。
实现流量控制：
- 发送窗口向接收窗口发送帧，同时开启定时器用于超时重传
- 接收窗口收到帧向后滑动，同时给发送窗口返回确认帧
- 发送窗口收到确认帧后，发送窗口向后滑动
- 接收窗口控制了发送窗口滑动速度，从而实现流量控制
实现可靠传输
- 帧丢失：
  - 发送一个帧的同时，启动定时器，若定时器超时，则自动重传，并重置定时器
- 帧重复：
  - 发送窗口发送一个帧的同时，启动定时器
  - 接收窗口收到数据帧，并返回确认帧（返回途中丢失了），同时向后滑动
  - 发送窗口定时器超时，重传数据帧
  - 接收窗口对比帧编号，发现收到重复帧，此时丢弃重复帧，并返回重复帧的 ACK（此时没有丢失）
  - 发送窗口收到确认帧，向后滑动
- 帧出错：
  - 发送窗口发送一个帧的同时，启动定时器
  - 接收窗口收到数据帧，但检测出差错，将此帧丢弃，且不返回 ACK
  - 发送窗口定时器超时，自动重传
- 帧失序：由于接收窗口 $W_R=1$ ，因此接收窗口只会按顺序接收数据帧，不存在数据帧失序问题

3. 后退 N 帧协议

后退 N 帧协议（GBN，Go-Back-N）
- 滑动窗口机制：发送窗口 $W_T>1$ ，接收窗口 $W_R=1$
- 确认机制：
  - 接收方可以 “累积确认”。即连续收到多个数据帧时，可以仅返回最后一个帧的 ACK。
  - 此时确认帧 $ACK_i$ 表示接收方已收到 $i$ 号帧及其之前的所有帧。
- 重传机制：若发送方超时未收到 $ACK_i$ ，则重传 $i$ 号帧，及其之后的所有帧。
- 帧编号：已知 $W_T+W_R≤2^n$ ，为了支持以上机制，因此至少需要 n bit 给帧编号。
- 缺点：如果接收方接收帧的速度很慢，或在信道误码率很高的情况下，可能会导致发送方的发送进度经常需要后退，传输效率低下。
发送数据帧丢失（帧丢失、帧出错）：
- 若发送窗口中的某一帧丢失或被丢弃
- 当接收方收到下一个帧时，帧编号对比失败，就会像发送窗口返回目前已正确接收的最后一个帧的 ACK
- 发送方接收到 $ACK_i$ ，后退回 $i + 1$ 号帧重新发送
确认帧丢失（帧重复）：
- 发送方在发送帧的同时给每个帧都开启定时器
- 若确认帧丢失，则第一个帧的定时器会超时，会重传本次发送窗口中的所有数据帧
- 第二次发送数据帧，接收方检测到重复的帧（非法帧），返回目前已正确接收的最后一个帧的 ACK
总结：
- 收到一个 “非法帧” 时，接收方会将此帧丢弃，并返回目前已接收的最后一个正确帧的 $ACK_i$ ，以提醒发送方 “后退” 回 $i + 1$ 号帧重新发送
- “非法帧” 包括落在接收窗口之外的帧、检测出差错的帧

4. 选择重传协议

选择重传协议（SR，Selective Repeat）：
- 滑动窗口机制：发送窗口 $W_T>1$ ，接收窗口 $W_R>1$
- 确认机制：
  - 确认帧、否认帧
  - 接收方可以连续接收多个帧，但每个帧都需要返回 ACK
- 重传机制：超时重传、请求重传
- 帧编号：
  - 已知 $W_T+W_R≤2^n$ ，为了支持以上机制，因此至少需要 n bit 给帧编号。
  - 接收窗口不能大于发送窗口，即 $W_R≤W_T$ ，通常取 $W_R=W_T$
  - 发送窗口大小 $W_T=4$
  - 接收窗口大小 $W_R≤4$ ，取 $W_R=4$
  - 则 $n≥log_2(W_T+W_R)$ ， $n≥log_28$ ，取 $n = 3$
  综上：用 3 bit 给帧编号，分别为 0~7
帧丢失：采用超时重传机制，每个帧被发出时设置计时器，如果超时未收到对应的 ACK，就重传这个帧
帧出错：采用请求重传机制，如果接收方收到一个有差错的帧，就将此帧丢弃，并返回对应的否认帧 $NAK_i$ ，主动请求发送方重传 $i$ 号帧。
帧重复（确认帧丢失）：采用超时重传机制，若接收到重复帧，则再次返回 ACK

5. 信道利用率分析

数据帧传输时延记为 $T_D$ ，2倍单向传播时延（发送数据帧和接收确认帧）记为 $RTT$ ，确认帧传输时延记为 $T_A$ ，发送窗口大小记为 $N$
注意：信道利用率 ≤ 1
S-W 协议（ $N = 1$ ）的信道利用率，在理想情况下， $信道利用率=U=\frac{T_D}{T_D+RTT+T_A}$
假设：信道的数据传输速率 1 kbps，数据帧长度 4 kb，信道单向传播时延 7s。
- 若确认帧长度 1 kb，则 $U=\frac{4}{4+2×7+1}≈21\%$
- 若确认帧长度非常短，可忽略不计，则 $U=\frac{4}{4+2×7+0}≈22.2\%$
GBN、SR 协议的信道利用率，在理想情况下， $信道利用率=U=\frac{N×T_D}{T_D+RTT+T_A}$
假设：发送窗口大小为 4，信道的数据传输速率 1 kbps，数据帧长度 4 kb，信道单向传播时延 7s。
- 若确认帧长度 1 kb，则 $U=\frac{4×4}{4+2×7+1}≈84\%$
GBN 协议 $W_R=1$ ，SR 协议 $W_R>1$ ，因此同样用 $n$ bit 给帧编号，GBN 的发送窗口 $W_T$ 更大，因此 GBN 的信道利用率也会更高。

6. 其他术语

滑动窗口协议：
- S-W 协议虽然采用 “滑动窗口机制”，但不属于滑动窗口协议
- GBN、SR 协议属于滑动窗口协议
ARQ 协议
- 即 “自动重传请求” （ARQ，Automatic repeat request）协议
- 包含 S-W、GBN、SR 协议
连续 ARQ 协议
- 发送窗口均大于 1，可连续发送和重传数据帧
- 包含 GBN、SR 协议，不包含 S-W 协议

【计算机网络】第三章：数据链路层（上）

【计算机网络】第三章：数据链路层（上）

一、数据链路层的功能

1. 基本概念

2. 功能总览

二、组帧（封装成帧）

1. 主要实现

2. 字符计数法

3. 字节填充法

4. 零比特填充法

5. 违规编码法

三、差错控制

1. 主要实现

2. 检错编码

Ⅰ. 奇偶校验码

Ⅱ. 循环冗余校验码

3. 纠错编码

Ⅰ. 海明校验码

四、流量控制、可靠传输

1. 相关机制

Ⅰ. 滑动窗口机制

Ⅱ. 确认机制

Ⅲ. 重传机制

Ⅳ. 帧编号

2. 停止-等待协议

3. 后退 N 帧协议

4. 选择重传协议

5. 信道利用率分析

6. 其他术语

网站公告

今日签到

热门文章

最新发布