数据链路层

基本概念

数据链路层通常分为两个子层：

逻辑链路控制 (Logical Link Control, LLC)：负责逻辑链路控制（如帧同步、差错控制等）。
介质访问控制 (Media Access Control, MAC)：负责控制设备对物理介质的访问（如以太网、Wi-Fi 中的冲突避免、帧的寻址等）。

下面分别讨论数据链路层的设计方法和工作逻辑。

封装成帧

相较于物理层的比特流，数据链路层的基本单位是帧 (Frame)，其中包含一些字段。而封装成帧的根本目的是为了检错与纠错。

如上图所示，数据链路层的一个帧的结构由帧首部、帧的数据部分和帧尾部三个部分组成。其中数据部分有长度限制，即最大传送单元 (Maximum Transfer Unit, MTU)，规定了所能传送的帧的数据部分长度上限。

*注：由于数据链路层的帧主要和 MAC 相关，其对应的帧也都称为 MAC 帧。

透明传输

当然不管是什么本质上都是 01 比特数据，关键在于如何设计一种机制使得机器可以识别出比特流中帧开始和帧结束的地方。有以下几种：

物理层编码违例 (Physical layer coding violations)；
字节计数法 (Byte count)；
带字节填充的定界符法 (Flag bytes with byte stuffing)。使用 FLAG 字节标记作为帧边界。为了避免误识别，发送方：给帧头的前面、帧尾的后面加一个 FLAG 字符标记，然后将数据中的所有 FLAG 前面加上 ESC 的转义标记；接收方：遇到 ESC 就跳过后一个字节，否则遇到 FLAG 就表示读到了帧的边界；
带比特填充的定界符法 (Flag bits with bit stuffing)。使用 0x7E 作为帧边界，即 \(01111110\)。为了避免误识别，发送方就需要每 5 个 1 就在其后插入一个 0；接收方就删除 5 个 1 后面的那个 0。

可靠传输

由于传输信道存在噪声，从而导致各种数据传输问题，例如：

差错：数据发生错误；
丢失：接收方未收到；
乱序：先发后到，后发先到；
重复：一次发送，多次接收。

而为了解决这些问题实现可靠传输，数据链路层通过「差错纠正」和「差错检测并确认重传」两种机制来实现。具体地：

确认：接收方校验数据（差错检测），一旦发现错误就让发送方重发（确认重传），防止差错；
定时器：发送方启动定时器，防止丢失；
顺序号：接收方检查序号，防止乱序递交、重复递交。

数据在传输的过程中，比特位发生错误的比例被称为误码率 (Bit Error Rate, BER)。「差错纠正」机制可以通过传输三份数据后，给每一个出现不一致情况的比特位取众数来实现，但是这种方法效率很低并且不能保证数据的绝对正确，我们主要讨论「差错检测并确认重传」机制。

差错检测主要有三种：

奇偶校验；
校验和：把所有字段求和并取反。例如：网络层的 IP 协议、传输层的 UDP/TCP 协议；
循环冗余校验 (Cyclic Redundancy Check, CRC)：假设要产生 n 位的 CRC 校验码，首先人为定义一个 n+1 位的二进制模式（也叫生成多项式），例如 \(x^3+x+1\) 对应的二进制模式就是 \(1011\)，然后将原始数据左移 n 位后和二进制模式进行类似于除法的异或运算，取余数的后 n 位作为 CRC 校验码。

CRC 计算示例

假设原始数据为 \(101110\)，生成多项式为 \(x^3+1\)，那么 CRC 校验码的计算流程如下图所示：

确认重传主要有两种：

反馈重发 (Automatic Request for Repeat, ARQ)：发送端计算出发送数据的检错码，与数据一起发送给接收端，同时在储存器中保留发送数据的副本；接收端接收到数据后，进行检错，若接收数据无错，则向发送端发送传输正确 ACK 信息，否则，向发送端发送传输错误 NAK 信息；如果发送端接收收到 NAK 信息，则将储存器中保留的数据副本提出再次发送，直至对方正确接收为止；
超时重发 (Timeout Retransmission)：发送端计算出发送数据的检错码，与数据一起发送给接收端，同时在储存器中保留数据的副本并启动一个定时器，定时器时间一般不低于从发完数据帧到收到 ACK 确认帧所需的平均时间；接收端接收到数据后，进行检错，若数据无错，则向发送端发送传输正确 ACK 信息，否则，丢弃出错数据；发送端若在定时器超时时没有收到 ACK 信息，则将储存器中保留的数据副本提出再次发送，直至对方正确接收为止。

点对点链路

PPP 帧分析

如上图所示，PPP 帧由三部分组成：

首部：含有 4 个字段。帧首由一个字节的 0x7E 组成，协议字段占 2 个字节，有三种协议：0x0021 表示当前存储的是 IP 数据报，0x8021 表示当前存储的是网络控制协议 (Network Control Protocol, NCP) 数据报，0xC021 表示当前存储的是链路控制协议 (Link Control Protocol, LCP) 数据报；
数据部分：即 IP 数据报，不超过数据链路的 MTU，即 1500 字节；
尾部：含有 2 个字段。

PPP 协议

这里我们介绍点对点协议 (Point-to-Point Protocol, PPP)。PPP 链路初始化过程如下：

用户拨号接入 ISP 后，就建立了一条从用户个人电脑到 ISP 的物理连接；
用户个人电脑向 ISP 发送一系列的链路控制协议 LCP 分组（封装成多个 PPP 帧），以便建立 LCP 连接；
之后进行网络层配置。网络控制协议 NCP 给新接入的用户个人电脑分配一个临时的 IP 地址；
当用户通信完毕时，NCP 释放网络层连接，收回原来分配出去的 IP 地址。LCP 释放数据链路层连接。最后释放物理层的连接。

有线局域网

有线局域网 (Local Area Network, LAN) 是指以双绞线、光纤等有线介质传输数据的计算机网络，采用 IEEE 802.3 标准协议。

*注：人们习惯于将 IEEE 802.3 标准协议称作以太网 (Ethernet II) 协议，这是因为 IEEE 802.3 是基于 Ethernet II 定制的。Ethernet II 是美国企业先闯出来的实际可行的协议，IEEE 802.3 是在其基础之上制定的官方标准。

IEEE 802.3 帧分析

具体地：

前 8 个字节为额外部分，一般忽略不计；
第 3 个字段和第 4 个字段即目的 MAC 地址和源 MAC 地址；
第 5 个字段为 Type 时表示 Ethernet II 帧，为 Length 时，表示 IEEE 802.3 帧；
第 6 个字段即数据字段；
第七个字段即校验和字段。

所以出了数据以外，Ethernet II 或 IEEE 802.3 的最小帧长为 64 字节。至于为什么要设置最小帧长，继续往下看。

CSMA/CD 机制

曾经，有线局域网采用的是冲突避免式的载波侦听多路访问 (Carrier Sense Multiple Access with Collision Detection, CSMA/CD) 机制。属共享型以太网。

CSMA/CD 的基本原理是：先听后发、边发边听、冲突停发、退避重发。具体地：

终端始终侦听信道，如果信道空闲，就立即发送数据；
如果侦听到了信道繁忙（收到了信道占用的数据帧），则继续侦听，一旦空闲立即发送数据；
如果发生冲突（已经发送了数据但还没收到确认收到的回复，却侦听到哦了信道繁忙），则等待一个随机时间后再重复步 1。

最小帧长。由于 CSMA/CD 机制没有帧的顺序信息，因此重传必须要在「发送方还在发送数据时收到了信道繁忙消息」时触发，否则发送方会误认为帧已成功发送，而实际上发生了冲突，但未能触发重传机制，导致数据丢失。因此就需要有一个最小帧长确保发送方数据发送完成前能侦听到其他终端发送的信道繁忙的消息。

显然，最小帧长就是 RTT 时间下，终端发送的数据量。传统有线局域网（以太网）的最大网络跨度为 2500 米，信号在信道（铜缆）中的传播速度约 \(2\times 10^8\) 米每秒，那么 RTT 就是 \(2\times \frac{2500}{2\times 10^8} = 2.5\times 10^{-5}\) 秒，为了覆盖中继器等设备的额外延迟，IEEE 802.3 将冲突窗口增加到了 \(5.12 \times 10^{-5}\) 秒。由于以太网的数据传输速率为 \(10\text{ Mbps}\)，那么最小帧长就可以表示为 \(5.12\times 10^{-5}\times 10\times 10^6\text{ (bit)}\)，即 512 比特，即 64 字节。

冲突退让。采用截断式二进制指数后退 (Truncated Binary Exponential Backoff) 法。假设当前是第 \(k\) 次重传，那么终端等待 \(r\times \text{RTT}\) 个时间后进行重传，其中 r 为 \([0,2^k-1]\) 中的某一个数。当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。例如：

第 1 次冲突重传时：\(k = 1\)，\(r\) 为 \(\{0,1\}\) 集合中的任何一个数；
第 2 次冲突重传时：\(k = 2\)，\(r\) 为 \(\{0,1,2,3\}\) 集合中的任何一个数；
第 3 次冲突重传时：\(k = 3\)，\(r\) 为 \(\{0,1,2,3,4,5,6,7\}\) 集合中的任何一个数。

全双工交换机制

后来，有线局域网开始采用全双工交换机机制。属交换型以太网。对比如下图所示：

交换机具有并行性，能同时连通多对接口，使多对主机能同时通信。相互通信的主机都独占传输介质，无碰撞地传输数据。

交换机可以自适应学习各个 MAC 帧及其对应的转发端口，更新算法如下图所示：

上述算法会出现信号闭环的「广播风暴」，为了避免这种情况，需要利用生成树协议 (Spanning Tree Protocol, STP) 将带有环的网络结构简化为树状结构。

虚拟局域网 VLAN

虚拟局域网 (Virtual Local Area Network, VLAN) 是一个在物理网络上根据用途、工作组、应用等逻辑来划分的局域网络，与用户的物理位置没有关系。根本目的是为了隔绝同一个局域网下的不同用户。一般都是基于交换机的端口进行虚拟局域网划分。

无线局域网

无线局域网 (Wireless Local Area Network, WLAN) 是指以无线信道作为传输介质的计算机局域网。采用 IEEE 802.11 标准协议。

*注：人们习惯于将符合 IEEE 802.11 标准的无线局域网技术称作 Wi-Fi，这是因为 Wi-Fi 联盟（商业组织）对通过其兼容性认证的 802.11 设备授予 Wi-Fi 商标。IEEE 802.11 是官方标准，而 Wi-Fi 是确保设备互操作性的商业品牌。

IEEE 802.11 帧分析

具体地：

帧控制：具有多种用途；
- 协议版本：通常为 0；
- 类型和子类型：如果子类型的最后一位设置为 1，表示是 QoS 数据帧；
- 更多段(分片）：于长帧被分段的情况，1 表示不是最后一段；
- 重传：表明当前帧是以前帧的重传；
- 电源管理：1 表示节能模式；0 表示活跃状态；
- 更多数据：指明有更多的数据要发送（缓存）；
- 安全保护：1 表明采用 802.11 标准的安全机制，对数据进行保护；
- 顺序：1 指示接收者必须严格按照顺序处理。
持续时间：下一个要发送帧可能持续的时间（NAV）或关联 ID（AID）；
地址 1~地址 4：每个地址的含义基于“去往 DS”和“来自 DS”域段确定；
顺序控制：过滤掉重复帧，或用于分片组合；
QoS 控制域段：存放数据流的 QoS 信息（802.11e 中扩展）；
数据：包含任意长度的数据（0-2312 字节）；
CRC 校验：802.11 采用 4 个字节的校验码。

CSMA/CA 机制

采用载波侦测多址接入与冲突避免 (Carrier Sense Multiple Access with Collision Avoid, CSMA/CA) 机制。

CSMA/CA 与 CSMA/CD 共同之处：

都采用分布式控制主机共享通信信道争用问题的思路，无中心控制节点，随机接入；
MAC 层协议与物理层协议均由网卡实现；
网卡结构、与计算机主板接口的实现方法，以及驱动程序的编程方法上均相同。

CSMA/CA 与 CSMA/CD 的区别：

发送数据帧的时机：

CSMA/CD：监听到总线空闲时立即开始发送帧；

CSMA/CA：除第一帧外，无线信道从“忙”转到“闲”时，执行退避算法。
退避算法：

802.3 采用“截止二进制指数退避算法”，帧重发的最大次数为 16；

802.11 采用“二进制指数退避算法”，帧重发的最大次数为 6。
信道侦听：

802.3：物理侦听，结点通过检测信道上的信号强度判断是否有其他设备在传输；

802.11：虚拟侦听，结点通过解析数据帧中的持续时间字段，维护一个网络分配向量 (NAV) 作为倒计时器，在此期间结点会推迟访问信道。
判断帧是否发送成功：

802.3：冲突检测；

802.11：停止等待接收方确认。

下面给出有线局域网和无线局域网在 CSMA 扩展机制上的区别

比较项目	IEEE 802.3 有线局域网 (Ethernet)	IEEE 802.11 无线局域网 (Wi-Fi)
使用机制	CSMA/CD	CSMA/CA
要发送数据时检测到信道空闲	立即发送数据	推后一段帧间间隔 DIFS，再根据情况，立即发送或执行退避算法
执行退避算法的时机	仅在检测到碰撞后要进行重传时	信道忙推迟接入，进行争用期；未收到确认进行重传；发送后续帧。
发送数据的过程中	边发送边检测信道，检测到碰撞中止发送	发送过程中不能检测碰撞，不能中止发送，必须把整个数据帧发完
收到正确的帧	不发送确认	要发送确认
传输媒体	有线，必须是有线接入	无线，接入很方便
当一个站发送数据	局域网内所有站都能检测到	局域网内并非所有站都能检测到
目前常用速率	1 Gbit/s	1 Gbit/s
是否需要接入点 AP	不需要	必须使用接入点 AP
安全性	很好	不如有线局域网好