考频地图
| 考点 | 考频 | 常见问法 | 必须会的动作 |
|---|---|---|---|
| 组帧(比特/字节填充) | ★★★☆☆ | “填充后的比特串是” | 5 个 1 后插 0 |
| CRC | ★★★★☆ | “FCS 是多少” | 补 r 个 0,模 2 除 |
| 停等 / GBN / SR | ★★★★★ | “信道利用率”“至少需要几位序号”“重传几帧” | 周期 = Td + RTT |
| CSMA/CD | ★★★★★ | “最短帧长”“争用期”“退避时间” | 最短帧 = 2τ × R |
| CSMA/CA、802.11 地址 | ★★★☆☆ | “地址 1/2/3 分别是什么” | 看 To DS / From DS |
| 交换机、冲突域、广播域 | ★★★★☆ | “图中有几个冲突域” | 交换机每口一个冲突域,路由器每口一个广播域 |
组帧
物理层送上来的是一串连续的比特,数据链路层要在里面找到“一帧从哪开始、到哪结束”。难点是透明传输:如果数据里恰好出现了和帧定界符一样的比特组合,不能误判成帧结束。
| 方法 | 做法 | 问题 / 使用者 |
|---|---|---|
| 字符计数法 | 帧首部用一个字段说明本帧有多少字节 | 计数字段一出错,后面所有帧都乱套 |
| 字节填充(字符填充) | 用特殊字节(如 0x7E)定界;数据中出现定界符或转义符时,前面插入转义字符 | PPP(异步传输) |
| 零比特填充 | 帧定界符 01111110;发送方在数据中每遇到连续 5 个 1 就插入一个 0,接收方删掉 | HDLC、PPP(同步传输) |
| 违规编码 | 用物理层不会出现的码元(如曼彻斯特中“高-高”)表示帧边界 | 802 局域网 |
填充后,数据中最多只会出现连续 5 个 1,绝不会出现 6 个 1,因此不会被误认为帧界 01111110。PPP 字节填充规则:数据中的 0x7E → 0x7D 0x5E,0x7D → 0x7D 0x5D,小于 0x20 的控制字符前加 0x7D 并把它加 0x20。
差错控制:CRC 与海明码
一、检错编码
- 奇偶校验:加 1 位使 1 的个数为奇(偶)数。只能检测奇数个比特错,偶数个错检测不出来。
- 循环冗余校验 CRC:发送方和接收方约定一个 r 阶生成多项式 G(r + 1 位)。发送方在数据 M 后补 r 个 0,用模 2 除法除以 G,余数(r 位)就是帧检验序列 FCS,附在 M 后面发出。接收方把整个帧除以 G,余数为 0 就认为没错。
- CRC 在数据链路层只检错不纠错:检测到错误就丢弃,至于重传由上层或可靠传输协议负责。
- “无比特差错”不等于“可靠传输”:帧丢失、重复、失序靠的是序号、确认、重传机制,不是 CRC。
- 余数位数 = 生成多项式的阶数 r(= G 的位数 − 1),不足要在前面补 0,例如余数 1 写成 001。
二、纠错编码:海明码
在 k 位数据中插入 r 位校验位,使每一位出错都对应一个唯一的“错误位置”。要能纠正 1 位错,需要满足:
海明距离 d:两个合法码字之间不同比特数的最小值。检测 d 位错需要海明距离 d + 1;纠正 d 位错需要 2d + 1。海明码在组成原理第 2 章有完整计算,这里知道条件即可。
流量控制与可靠传输
流量控制:接收方处理不过来时让发送方慢一点。可靠传输:帧出错或丢了要重发。这两件事用同一套机制实现——滑动窗口 + 确认 + 超时重传(ARQ,自动重传请求)。
一、停止-等待:发一帧,等确认
发送窗口 = 接收窗口 = 1。为了区分“新帧”和“重传的帧”,帧要编号,1 位序号(0、1 交替)就够。问题是效率:发完一帧后整整一个 RTT 都在等。
二、连续 ARQ:在等确认的时候继续发
| 协议 | 发送窗口 WT | 接收窗口 WR | 确认方式 | 出错时 |
|---|---|---|---|---|
| 停止-等待 | 1 | 1 | 逐帧确认 | 超时重传该帧 |
| 后退 N 帧 GBN | 1 < WT ≤ 2ⁿ − 1 | 1 | 累积确认:ACK n 表示 n 及以前都已正确收到 | 从出错帧开始全部重传 |
| 选择重传 SR | WT ≤ 2ⁿ⁻¹ | WR ≤ 2ⁿ⁻¹(满足 WT + WR ≤ 2ⁿ) | 逐帧确认 | 只重传出错帧 |
为什么 GBN 发送窗口最多 2ⁿ − 1?以 n = 2(序号 0–3)为例,若 W = 4:发送方发 0、1、2、3,接收方全收到并发出确认,但确认全丢了。发送方超时重发旧的 0;而接收方此时期待的新帧序号也是 0,会把旧帧当新帧收下——出错。W = 3 时就不会混淆。SR 同理要求窗口不超过序号空间的一半。
- GBN 的接收窗口是 1,所以它不缓存失序帧;SR 的接收窗口 > 1,可以缓存。
- GBN 累积确认:收到 ACK 3 意味着 0–3 都到了,即使 ACK 1、ACK 2 丢了也没关系。
- GBN 重传几帧?从超时的那帧开始,到已发出的最后一帧为止全部重传。
- 算利用率时,题目若说“确认帧长度忽略不计”,周期就是 Td + 2Tp;若确认帧也有发送时延,还要加上。
介质访问控制
点对点链路上只有两个结点,不存在“抢”的问题。但在广播信道(总线、无线)上,多个站共用一个信道,同时发就会冲突。三大类解决办法:
| 类型 | 做法 | 代表 |
|---|---|---|
| 信道划分(静态) | 预先分好,各用各的,不会冲突 | FDM、TDM、WDM、CDM |
| 随机访问(动态) | 谁有数据谁发,冲突了再想办法 | ALOHA、CSMA、CSMA/CD、CSMA/CA |
| 轮询访问(动态) | 轮流获得发送权 | 令牌传递(令牌环) |
一、CSMA:先听后说
| 类型 | 信道空闲时 | 信道忙时 | 特点 |
|---|---|---|---|
| 1-坚持 | 立即发送 | 一直监听,空闲后立即发 | 多个站同时等待时,空闲一到必冲突 |
| 非坚持 | 立即发送 | 放弃监听,随机等一段时间再听 | 冲突少,但信道可能空闲着没人用 |
| p-坚持 | 以概率 p 发送,1 − p 推迟到下个时隙 | 持续监听 | 折中 |
二、CSMA/CD:边说边听,冲突就停(有线以太网)
“先听后说”仍可能冲突:A 发出的信号要经过传播时延 τ 才能到达 B,在这之前 B 听到的是“空闲”。所以还要边发送边检测,一旦检测到冲突就立即停止,并发送 32 bit 的人为干扰信号。
截断二进制指数退避:第 k 次重传前,从 {0, 1, …, 2k′ − 1} 中随机取 r,等待 r × 2τ,其中 k′ = min(k, 10)。重传 16 次仍失败就放弃并报告上层。冲突越多,等待的范围越大,自动适应负载。
CSMA/CD 只能半双工工作(发送时要同时听)。现代交换式以太网是全双工的,根本不会冲突,也就不需要 CSMA/CD。
三、CSMA/CA:尽量避免冲突(无线局域网 802.11)
① 无线信号衰减大,自己发送时信号强,很难检测到别人的弱信号;② 隐蔽站问题:A、C 都能和 AP 通信,但 A、C 互相听不到,都以为信道空闲,于是在 AP 处冲突。
① 信道空闲后还要等一段帧间间隔(DIFS),再随机退避;② 可选 RTS/CTS:发送前先发短的请求帧 RTS,AP 回 CTS,所有听到 CTS 的站都推迟发送(解决隐蔽站);③ 接收方收到数据帧后等 SIFS 回 ACK,没收到 ACK 就重传(链路层确认)。
帧间间隔:SIFS(最短,用于 ACK、CTS)< PIFS < DIFS(最长,用于普通数据帧开始竞争)。间隔越短优先级越高。
四、令牌传递
一个特殊的令牌帧在环上依次传递,只有拿到令牌的站才能发数据。不会冲突,负载重时效率高;但令牌丢失或站点故障要专门处理。
- 最短帧长和最大距离是同一个关系:帧长固定时,距离越大越可能检测不到冲突。题目问“最远距离”就用 L ÷ R = 2d ÷ v 反解 d。
- CSMA/CD 检测到冲突后发的是 32 bit 干扰信号,然后再退避。
- CSMA/CA 的 RTS/CTS 是可选的,用于数据帧较长时。
以太网、无线局域网与 PPP
一、以太网 MAC 帧(Ethernet V2)
- MAC 地址:48 位,固化在网卡中,前 24 位是厂商代码。全 1(FF-FF-FF-FF-FF-FF)为广播地址。网卡收到帧后检查目的地址,不是发给自己的就丢弃。
- 以太网提供无连接、不可靠的服务:不编号、不确认,出错帧直接丢弃,可靠性交给上层(TCP)。
- 常见标准:10BASE-T(双绞线、星形、集线器)、100BASE-T(快速以太网,可全双工)、吉比特、10 吉比特以太网(只用全双工,不再用 CSMA/CD)。
- VLAN:在源地址后插入 4 B 的 802.1Q 标记(其中 VID 12 位),帧最大长度变为 1522 B。同一 VLAN 内才能直接通信,VLAN 隔离广播域;不同 VLAN 间通信需要路由器(或三层交换机)。
二、802.11 无线局域网帧的地址
802.11 数据帧有 4 个地址字段(常用前 3 个),含义取决于帧是发往 AP 还是从 AP 发出:
| 场景 | To DS | From DS | 地址 1(接收者) | 地址 2(发送者) | 地址 3 |
|---|---|---|---|---|---|
| 站 A → AP(准备发往有线网的 R) | 1 | 0 | AP 的 MAC(BSSID) | A 的 MAC | 目的地址 R |
| AP → 站 B(来自有线网的 R) | 0 | 1 | B 的 MAC | AP 的 MAC(BSSID) | 源地址 R |
记法:地址 1 永远是“这一跳无线链路的接收者”,地址 2 永远是“这一跳的发送者”,地址 3 放“另一头真正的通信方”。
三、PPP 协议(点对点链路)
- 帧格式:标志 0x7E | 地址 0xFF | 控制 0x03 | 协议 2 B | 信息 ≤ 1500 B | FCS 2 B | 标志 0x7E。
- 组成:封装成帧的方法、链路控制协议 LCP(建立、配置、测试链路)、网络控制协议 NCP(为各种网络层协议配置,如分配 IP)。
- 不使用序号和确认,只保证无差错接收(CRC),不提供可靠传输;只支持点对点、全双工;面向字节。
交换机与冲突域
一、交换机的自学习
交换机(多端口网桥)工作在数据链路层,靠一张交换表(MAC 地址 → 端口)转发帧。表不是配置出来的,是“看”出来的:
- 存储转发:收完整帧、做 CRC 检查后再转发;可靠,可连接不同速率的端口,时延较大。
- 直通交换:只读完目的地址(前 6 B)就开始转发;时延小,但不检错。
- 交换机的每个端口独占带宽:10 Mbit/s 交换机接 10 台主机(全双工),每台都能用满 10 Mbit/s。
二、冲突域与广播域
| 设备 | 层次 | 隔离冲突域 | 隔离广播域 |
|---|---|---|---|
| 中继器、集线器 | 物理层 | ✗ | ✗ |
| 网桥、交换机 | 数据链路层 | ✓(每个端口一个) | ✗(VLAN 可以) |
| 路由器 | 网络层 | ✓ | ✓(每个接口一个) |
- 交换机学习用源 MAC,转发看目的 MAC,不要反过来。
- 交换机收到广播帧会向所有其他端口转发,所以它不隔离广播域。
- 交换机对主机是透明的:主机不知道交换机的存在,也不需要配置交换机地址。
真题与自测
一、真题问法
问法 1:“数据链路层采用 GBN,发送方已发送 0~7 号帧。计时器超时时只收到 0、2、3 号帧的确认,发送方需要重发几帧?”→ 累积确认:收到 ACK 3 说明 0–3 都到了,从 4 开始重发 4、5、6、7,共 4 帧。
问法 2:“主机甲乙之间信道速率 3 kbit/s,单向传播时延 200 ms,帧长 1000 B(可视为不计确认帧),采用 GBN 要使利用率最大,帧序号至少需要几位?”→ Td = 8000 / 3000 ≈ 2.67 s,周期 = 2.67 + 0.4 = 3.07 s,W ≥ 3.07 / 2.67 → 2 帧,GBN 需 2ⁿ − 1 ≥ 2 → n ≥ 2,至少 2 位。
问法 3:“CSMA/CD 网络,数据率 1 Gbit/s,电缆中信号传播速度 200 000 km/s,最短帧长减少 800 bit 时,最远两站之间的距离至少需要怎样变化?”→ 最短帧 = 2d/v × R,ΔL = 800 bit 对应 Δd = 800 × v / (2R) = 80 m,减少 80 m。
问法 4:“下图网络中有几个冲突域、几个广播域?”→ 交换机每端口一个冲突域,集线器整体一个,路由器每接口一个广播域。
二、折叠自测
1. 数据 1101011011,生成多项式 x⁴ + x + 1,FCS 是多少?
G = 10011,补 4 个 0 后模 2 除,余数为 1110。在 CRC 计算器中输入可验证全过程。
2. 3 位序号,GBN 和 SR 的最大发送窗口各是多少?
GBN:2³ − 1 = 7;SR:2³⁻¹ = 4(接收窗口也是 4)。
3. 停止-等待协议需要几位序号?为什么?
1 位就够。只需区分“这一帧”和“上一帧(重传)”,0、1 交替即可。
4. 10 Mbit/s 以太网争用期是多少?最短帧多长?
争用期 51.2 μs,最短帧 512 bit = 64 B。
5. 为什么无线局域网不用 CSMA/CD?
无线信号衰减大,发送时难以检测到其他站的弱信号;还存在隐蔽站问题,即使检测也检测不到。因此改用 CSMA/CA 尽量避免冲突,并用 ACK 确认。
6. 交换机收到一个目的 MAC 不在交换表中的帧怎么办?
除进入端口外,向所有其他端口泛洪;同时用该帧的源 MAC 更新交换表。
7. PPP 协议提供可靠传输吗?
不提供。PPP 只做 CRC 检错,出错帧丢弃,不编号、不确认、不重传。
三、考前速览
零比特填充:5 个 1 后插 0。
CRC 补 r 个 0,模 2 除,余数 r 位。
U = W·Td / (Td + RTT)。
GBN ≤ 2ⁿ − 1,SR ≤ 2ⁿ⁻¹。
最短帧 = 2τ × R。
① GBN 累积确认,接收窗口为 1。
② CRC 不纠错,也不保证可靠。
③ 交换机用源地址学习。
④ 交换机不隔离广播域。
⑤ 802.11 地址 1 是本跳接收者。