数据链路层

• 帧
  • 定义
    • 按照一定的规则把数据流划分为若干段或恢复。
    • 数据链路层的传输以帧为单位。
  • 分类
    • 字符计数：每一帧的开头记录整个帧的长度。
    • 字节/字符填充：使用标志字节/字符划分边界，转义字符用于表示特殊字符本身。
    • 位填充：以 01111110 为边界，发送数据内容时遇到连续 5 个 1 就添加一个 0 强制区分。
    • 物理层编码违例：利用无效信号作为边界。
• 差错检测与纠正
  • 纠错码
    • 海明码
      • 一个帧内第 $2^i$ 位用于存储冗余校验位，其他按照顺序存储数据位。
      • 对于第 $2^i$ 位，其对应一个，其中的位置编号二进制分解包含 $2^i$。
      • 对于第 $2^i$ 位，其值为帧内位置组内的位的异或和。
      • 接收时，每一个组和校验位自身如果都满足偶校验，则没有错误。
        • 如果不满足，所有不满足校验的 $2^i$ 组的 $i$ 的和就是出错的位置。
      • 要纠正 $d$ 个错误，有效码字之间的海明距离必须大于等于 $2d + 1$，要检查，则大于等于 $d + 1$。
  • 检错码
    • 奇/偶校验
      • 帧内数据附加一个校验位，包括校验位的异或和为 $1$/$0$ 时没有错误。
      • 只能检测出现奇数个错误的情况。
    • 二维奇/偶校验
      • 每一帧仍然使用奇/偶校验，同时在帧之间插入校验帧，每一位为这段帧中相同位的校验和。
      • 1 位错误一定可以被校正，2 或 3 位错误一定可以被检测，更多位错误可能可以被检测。
    • CRC
      • 发送和接收者使用同一个 $n + 1$ 位二进制模式串 $a_n a_{n - 1} \dots a_1 a_0$，用 $n$ 次多项式表示 $G(x) = \displaystyle \sum_{i = 0}^n a_i x^i$。
      • 发送者发送数据时，需要给原始数据追加一个 CRC 后再发送，计算 CRC 过程：
        • 给数据 $x$ 追加 $n$ 个 $0$，追加后的串记作 $x^n M(n)$。
        • 计算 $x^n M(n)$ 除以 $G(x)$ 的余数：
          • 这里的二进制串加减法就是异或。
          • 部分余数足够除以除数的条件：部分余数位数大于等于除数位数、部分余数的第一位为 $1$。
        • 把 $n$ 位余数串追加到原始数据后发送。
      • 接收者接收数据时，把接收数据除以 $G(x)$，若余数不为全 $0$ 则有错误，否则接收数据。
• 差错控制
  • 停止等待
    • 原理
      • 发送者发送一个帧后，等待接收者接收并返回一个 ACK 后，再发送下一个帧。
      • 每个帧包括需要包括序列号用于定序。停止等待只需要 0/1。
      • ACK 也包括序列号，ACKn 表示 $n - 1$ 已接收，正在等待 $n$。
      • 发送过程：
        • 发送者发送帧，等待。
        • 确定接收到接收者的 ACK 后，再开始发送下一个帧。
        • 如果接收到的不是 ACK，则重新传输。或者按照接收者要求，进行其他动作，如结束传输。
        • 如果经过一定时间后没有收到任何回复，则重新传输。
        • 如果接收的 ACKn 与下一个真正要发送的 n 不匹配，则忽略此 ACK。
      • 接收过程：
        • 等待发送的帧，接收到后，根据序列号确认不是重复的帧、没有检测到错误，然后发送一个 ACK。
        • 如果接收到重复的帧，则重新传输前一个 ACK。
    • 计算
      • 。
      • 如果忽略处理时间、ACK 发送时间，利用率简化为 $\dfrac{t_{\text{trans}}}{t_{\text{trans}} + 2 t_{\text{prop}}} = \dfrac{t_{\text{trans}}}{t_{\text{trans}} + t_{\text{RTT}}} = \dfrac{1}{1 + 2\alpha}, \alpha = \dfrac{t_{\text{prop}}}{t_{\text{trans}}}$。
  • GBN
    • 原理
      • 发送者使用长度最大为 $2^n - 1$ 的滑动窗口，连续发送滑动窗口内的帧。接收者按顺序一次接收一个。
      • ACKn 使用累积语义，表示第 $n - 1$ 及之前的帧都确认，等待第 $n$ 帧。
      • 发送过程：
        • 顺序发送滑动窗口内的所有帧。
        • 如果接收到 ACKn，则推动滑动窗口到从 $n$ 开始，后面的部分也可以继续发送。
        • 如果接收任意 ACK 都超时，重新传输当前窗口的所有帧。
      • 接受过程：
        • 与停止等待类似，只等待一个序列号的帧，错误、顺序不正确的帧之间忽略，不发送任何回复。
    • 计算
      • 最大利用率为 $\dfrac{N}{1 + 2\alpha}$，在错误多时不高效。
  • SR
    • 原理
      • 发送者使用长度最大为 $2^{n - 1}$ 的滑动窗口，连续发送滑动窗口内的帧。接收者也同时接收一个滑动窗口内的帧。
      • 发送过程：
        • 顺序发送滑动窗口内的所有帧。
        • 如果接收到 ACKn，则推动滑动窗口到从 $n$ 开始，后面的部分也可以继续发送。
        • 如果接收任意 ACK 都超时，重新传输当前窗口的所有帧。
        • 如果接收的 ACKn 不是下一个要发送的帧，则重新传输第 $n$ 帧，然后恢复原来发送过程，继续发送后续帧。
      • 接受过程：
        • 接收到的帧的序列号如果在当前窗口内，则提前存储下来。
        • 如果第 $n - 1$ 个帧及其之前的帧都完全正确接收，则 ACK 的序列号为 $n$。
        • 一旦前面连续的帧都确认接收成功，就可以增加 ACKn 并推动窗口起始位置到 $n$。
• 介质访问控制
  • 控制多个主机在共享媒介上的信道接入，协调竞争。
  • 协议分类
    • 信道划分：将信道划分为时间/频率/码片，每块分给节点独占。公平但浪费带宽。
    • 随机接入：不划分信道，允许冲突，冲突后恢复。轻负载时低延迟，重负载时冲突严重。
    • 受控接入：节点轮流使用信道，无冲突。如令牌传递、轮询。
  • 随机接入协议
    • ALOHA
      • 纯 ALOHA：不施加任何限制，有数据就发，冲突后随机等待重发。
        • 易受冲突时间：$2T_{f r}$。
        • 信道负载 $G$：每毫秒内媒介上发送的帧数量。
        • 吞吐率 $S = G e^{-2G}$，$G = 0.5$ 时有 $S_{\max} = \dfrac{1}{2e} \approx 0.184$。
      • 时隙 ALOHA：时间划分为等长时隙，只能在时隙起点发送。
        • 易受冲突时间减半为 $T_{fr}$。
        • 吞吐率 $S = G e^{-G}$，$G = 1$ 时有 $S_{\max} = \dfrac{1}{e} \approx 0.368$。
    • CSMA
      • 先听后发：发送前检测信道，空闲则发，忙则等待。
      • 因传播延迟仍可能冲突，易受冲突时间为 $t_{prop}$。
      • 持续策略：
        • 1-persistent：持续监听，空闲立即发送。冲突概率高。
        • non-persistent：忙时随机等待后再监听。冲突少但延迟大。
        • p-persistent：持续监听，空闲时以概率 $p$ 发送，以概率 $1-p$ 等待一个 $t_{prop}$ 后再监听。
    • CSMA/CD
      • 即冲突检测。
      • 采用 1-persistent 策略：持续监听，空闲立即发送。
      • 边发边听：检测到冲突立刻停止并发 jam 信号。
      • 竞争期：最坏情况下检测冲突需要 $2\tau$，$\tau$ 为最大传播延迟。
      • 最小帧长：帧发送时间必须大于一个 $t_{\text{RTT}} = 2\tau$，否则发完才发现冲突。$L_{\min} = R \left( \dfrac{2d}{v} + T_{\text{phy}} \right)$。
      • 冲突后退避策略由具体标准规定。
      • 效率：$\dfrac{1}{1 + 5\alpha}$，$\alpha = t_{prop}/t_{trans}$。$\alpha$ 越大（速率高、距离远），效率越低。
    • CSMA/CA
      • 即冲突避免。
      • 用于无线网络，CSMA/CD 不适用：无线难以同时收发、存在隐藏终端问题、距离远信号衰减。
      • 隐藏终端问题：A 与 B、B 与 C 可通信，但 A 与 C 互相听不到。A 向 B 发送时 C 感知不到信道占用，也向 B 发送导致冲突。
      • 冲突避免机制：
        • IFS（帧间间隔）：检测到空闲后不立即发送，等待 IFS 让信号传播到其他节点。
        • 竞争窗口：等待 IFS 后随机选若干时隙倒计时，信道忙暂停、空闲继续。未收到 ACK 则加大窗口重试。
        • ACK 确认：接收方回复 ACK，未收到即视为冲突。
      • 基本 CSMA/CA 无法解决隐藏终端问题。
      • RTS/CTS 机制：发送方等 DIFS 后发 RTS，接收方等 SIFS 后回 CTS，发送方等 SIFS 后发数据，接收方等 SIFS 后回 ACK。CTS 广播使范围内所有节点得知信道占用，解决隐藏终端问题。SIFS 短于 DIFS，序列一旦开始不会被中断。
  • 以太网
    • 最广泛使用的有线 LAN 技术，基于 CSMA/CD，速率从 10 Mbps 到 10 Gbps。
    • 拓扑：总线、星型、环形、网状。
    • 帧格式：
      • 目的地址 6 B
      • 源地址 6 B
      • 类型 2 B
      • 数据 0–1500 B
      • PAD 0–46 B
      • CRC 4 B
      • 帧长范围 64–1518 B，数据不足 46 B 时填充 PAD 保证最小帧长。
    • MAC 地址：48 位物理地址，由 IEEE 分配并烧录在网卡上。分单播（单站）、组播（一组）、广播（全 1，FF:FF:FF:FF:FF:FF）。
    • 二进制指数退避：冲突后等待 $R \times \text{SlotTime}$，$R$ 从 $[0, 2^K)$ 中随机选取，$K = \min(\text{重传次数}, 10)$。16 次失败后放弃。
  • LAN 互连与交换
    • 互连设备
      • 集线器/中继器：物理层设备，信号转发到所有端口，不理解帧。所有端口共享一个冲突域和一个广播域。
      • 交换机/网桥：数据链路层设备，根据 MAC 地址转发帧。每个端口是独立的冲突域，所有端口共享一个广播域。
      • 路由器：网络层设备，根据 IP 地址转发包。每个接口是独立的冲突域和广播域。
    • 交换机自学习
      • 转发表条目：(MAC 地址, 端口, 老化时间)。
      • 收到帧时记录源 MAC 地址与入端口的映射。
      • 查表转发：找到且同端口则丢弃，找到且不同端口则转发，找不到则泛洪（向除入端口外所有端口转发）。
      • 表项过期自动删除。
    • 交换方式
      • 存储转发：接收完整帧后校验再转发，延迟大但保证完整性。
      • 直通交换：读取目的地址（前 6 B）后立即转发，延迟最小但无法检测错误。
      • 碎片隔离：检查前 64 B 后转发，过滤冲突产生的残帧，是两者的折中。
    • 生成树协议
      • 解决交换机环路导致的帧无限循环问题。
      • 交换机交换 BPDU 消息：选举根桥，计算到根桥的最短路径，确定根端口，每个 LAN 段选指定桥，不在生成树上的端口阻塞。
      • 物理拓扑保留冗余链路，逻辑拓扑为无环树，故障时重新计算。
    • VLAN
      • 在交换机上逻辑划分广播域，不受物理位置限制。
      • 作用：隔离广播流量、提高安全性、简化管理。
      • 划分方式：基于端口（最常见）、基于 MAC 地址、基于 IP 地址。
      • Trunk：单条链路承载多个 VLAN 流量，交换机之间通过 802.1Q 标签区分。
      • 802.1Q 标签：在源地址后插入 4 B（类型 0x8100 + TCI），VLAN ID 占 12 位，可用范围 1–4094（0 和 4095 保留）。标签由交换机添加和移除，主机无感知。
  • WLAN
    • 架构：
      • AP（接入点）：提供到分发系统的接入。
      • BSS（基本服务集）：一个 AP 与其关联的所有站点。
      • DS（分发系统）：连接多个 BSS 的骨干网络。
      • ESS（扩展服务集）：多个 BSS 通过 DS 互连形成的整体。
    • MAC 层协调功能：
      • DCF（分布式协调功能）：基于竞争，使用 CSMA/CA。
      • PCF（点协调功能）：无竞争，AP 轮询各站点。