数据链路层

本节导读

大纲的「数据链路层」包括：功能；组帧；差错控制（检错编码、纠错编码）；流量控制与可靠传输（滑动窗口机制，停止-等待、后退 N 帧 GBN、选择重传 SR）；介质访问控制（信道划分、随机访问、轮询访问）；局域网（以太网与 IEEE 802.3、IEEE 802.11 无线局域网、VLAN）；广域网（PPP 协议）；以太网交换机及其工作原理。

计算集中在 CRC、信道利用率与窗口大小、CSMA/CD 的争用期与退避、码分多址的内积；交换机部分要会推自学习过程，会数冲突域和广播域的个数。

功能与组帧

数据链路层把网络层交下来的分组封装成帧，在相邻结点之间传送，主要功能有：组帧、透明传输、差错控制、流量控制、介质访问控制。组帧要让接收方能找出帧的开始和结束，并保证数据中出现与定界符相同的内容时不会被误判（透明传输）：

• 字符计数法：帧首部用一个计数字段说明帧长，计数字段出错就会「失步」；
• 字节填充法：用特殊字节作帧定界符，数据中出现定界符或转义字节时在前面加转义字节（如 PPP 异步传输中 7E 变成 7D、5E）；
• 零比特填充法：用 01111110 作帧标志，发送方在数据中每遇到连续 5 个 1 就插入一个 0，接收方每遇到连续 5 个 1 就删去后面的 0；
• 违规编码法：利用物理层编码中不会出现的信号（如曼彻斯特编码中「高-高」）来定界。

差错控制

检错编码有奇偶校验和循环冗余校验 CRC。CRC 的做法：生成多项式最高次为 r，在数据后面补 r 个 0，用模 2 除法（按位异或，不借位）除以生成多项式对应的比特串，得到的 r 位余数就是帧检验序列 FCS，附在数据后面发送。接收方把收到的整个帧除以同一个比特串，余数为 0 就认为没有差错。CRC 只能检错，链路层加上确认和重传才算可靠传输。

纠错编码以海明码为代表：k 位数据需要 r 位校验位，满足 2 的 r 次方 ≥ k + r + 1；校验位放在第 1、2、4、8……位上。编码集合中任意两个码字的最小距离叫码距：要检测出 d 位错误，码距至少为 d + 1；要纠正 d 位错误，码距至少为 2d + 1。

流量控制与可靠传输

协议	发送窗口	接收窗口	出错时的处理
停止-等待	1	1	超时重发这一帧
后退 N 帧 GBN	不超过 2 的 n 次方 − 1（n 为序号位数）	1	只按序接收、累积确认；某帧超时，重发它及其后已发出的所有帧
选择重传 SR	发送窗口 + 接收窗口 ≤ 2 的 n 次方，通常各为 2 的 n − 1 次方	大于 1	失序但正确的帧先缓存，逐帧确认，只重发出错的帧

设数据帧的发送时延为 T，往返时间为 RTT（确认帧的发送时延很小时可忽略），停止-等待的信道利用率为 T ÷ (T + RTT)。用发送窗口为 W 的连续发送时，利用率为 W × T ÷ (T + RTT) 与 1 中的较小者；要让信道一直忙，W 至少为 (T + RTT) ÷ T。

介质访问控制

信道划分：频分（FDM）、时分（TDM，统计时分可按需分配）、波分（WDM，光的频分）、码分（CDM）。码分多址中每个站有一个码片序列，各站的码片序列两两正交；站发送 1 时送出自己的码片序列，发送 0 时送出它的反码。接收方把收到的叠加信号与某站的码片序列做内积再除以码片数：结果为 1 表示该站发送了 1，为 −1 表示发送了 0，为 0 表示该站没有发送。

随机访问：

• ALOHA：想发就发，冲突后随机等待重发；时隙 ALOHA 只在时隙开始时发送，冲突的机会少一些；
• CSMA：先听后发，有 1-坚持、非坚持、p-坚持三种做法；
• CSMA/CD（以太网）：先听后发、边发边听、冲突停发、随机重发。端到端单程传播时延为 τ 时，发出 2τ 后还没检测到冲突就不会再冲突，2τ 叫争用期；最短帧长 = 争用期 × 数据率；冲突后用截断二进制指数退避：第 k 次冲突后从 0 至 2 的 min(k, 10) 次方 − 1 中随机取整数 r，等待 r 个争用期，16 次都失败就放弃；
• CSMA/CA（802.11 无线局域网）：无线站点发送时难以检测冲突，还有隐蔽站问题，所以改为冲突避免：信道空闲还要等一段帧间间隔，可用 RTS、CTS 预约信道，接收方正确收到后回 ACK。

轮询访问的典型是令牌传递：令牌在各站间依次传递，拿到令牌的站才能发送，没有冲突。

局域网与 PPP

局域网的基本概念与体系结构：局域网覆盖范围小（一个单位或一栋楼），一般为一个单位所有，数据率高、时延和误码率低。决定局域网特性的主要技术有三项：拓扑结构（总线形、星形、环形、树形）、传输介质（双绞线、同轴电缆、光纤、无线）和介质访问控制方法（以太网用 CSMA/CD、令牌环用令牌传递、802.11 用 CSMA/CA）。IEEE 802 标准把局域网的数据链路层拆成两个子层：逻辑链路控制 LLC 子层与传输介质无关；介质访问控制 MAC 子层与接入的传输介质有关，负责成帧、按 MAC 地址寻址和介质访问控制。TCP/IP 体系中的以太网多用 V2 帧，实际上很少用到 LLC 子层。