All writings

链路层和局域网

成帧、链路接入、差错检测与纠正、多路访问协议和局域网

Computer NetworkingLink Layer

通信链路通常可分为两类:点对点通信链路(如 PPP、HDLC,两端各为一个发送方与接收方)与广播信道。广播信道广泛用于有线局域网、卫星网以及混合光纤同轴电缆(HFC)接入网等多路共享介质中,需要依赖介质访问控制(MAC)协议来协调多个节点之间的帧传输。

链路层概述

在讨论链路层时,通常将运行链路层协议的任何网络设备(主机、路由器、交换机、WiFi AP 等)统称为节点(node),将沿着通信路径连接相邻节点的物理通信信道称为链路(link)。在传输过程中,发送节点将网络层交付的数据报封装进链路层帧(frame)中,并将其推送到物理链路上传输。

链路层提供的服务

链路层协议在相邻节点之间提供基本的数据传输服务,具体包括:

  • 成帧(Framing):在数据报经链路传送前,链路层协议用链路层帧将其封装起来。一个帧由一个数据字段(存放网络层数据报)和若干首部、尾部字段构成,其具体结构由链路层协议规范严格定义。
  • 链路接入(Link Access):媒体访问控制(Medium Access Control, MAC)协议规定了帧在物理介质上传输的规则。点对点链路在链路空闲时可直接发送;当多个节点共享广播信道时,MAC 协议负责协调各节点的发送时机,防止传输冲突。
  • 可靠交付(Reliable Delivery):通过确认和重传机制,保证无差错地在物理相邻节点间移动每个网络层数据报。链路层的可靠交付服务旨在本地(链路两端)快速发现并纠正差错,避免由运输层或应用层跨越长途端到端路径进行代价高昂的超时重传。
  • 差错检测和纠正(Error Detection and Correction):由于信号衰减与噪声干扰,比特可能发生翻转损伤。发送节点在帧首部或尾部附加差错检测比特,接收节点根据校验规则执行硬件校验与纠错。

链路层在何处实现

链路层的主体功能大多在网络适配器(Network Adapter) 中实现,即通常所说的网络接口卡(Network Interface Card, NIC)。网络适配器的核心是专用的链路层控制器芯片(包含专用硬件与固件)。

发送端主机的协议栈先由操作系统处理高层逻辑,将内存中的网络层数据报传递给适配器;适配器在硬件中完成装帧、计算校验码,并遵循链路接入规则将信号发送至通信介质中。接收端适配器收到物理信号后完成差错检验与解帧,再通过中断将数据报交付给主机操作系统。

Pasted image 20231130170308.png

差错检测和纠正技术

比特级差错检测和纠正(bit-level error detection and correction)主要检测物理链路上可能发生的比特翻转损伤。发送节点通过在原始数据 DD 之外附加差错检测和纠正比特(Error-Detection and-Correction, EDC)来增强保护,要保护的数据包括网络层数据报和链路帧的部分首部字段。

Pasted image 20231130173734.png

值得注意的是,即便利采用差错检测比特,理论上依然存在极小概率的未检出比特差错(undetected bit error)。工程中常见的三种差错检验技术为:奇偶校验、检验和方法以及循环冗余检测(CRC)。

奇偶校验

最简单的方案是一维奇偶校验:发送方在 dd 比特数据后追加一个校验比特,使得 d+1d+1 比特中数字 11 的总数为偶数(偶校验)或奇数(奇校验)。一维校验仅能检测出奇数个比特翻转,对偶数个比特翻转无能为力,且无法定位差错位置。

二维奇偶校验(Two-Dimensional Parity): 将 dd 个比特划分为 ii 行 jj 列的矩阵,分别对每行和每列计算奇偶校验比特,并在右下角附加全局校验比特。

Pasted image 20231130180250.png

二维校验不仅能检测出任意单比特与双比特差错,还能精准定位并纠正单个比特差错(行校验与列校验交叉点即为错误比特)。接收方直接检测并就地纠正差错的能力称为向前纠错(Forward Error Correction, FEC),可省去等待重传的往返时延开销。

检验和方法

检验和方法将数据视为由若干固定长度(如 16 比特)整数构成的序列。

  • 因特网检验和(Internet Checksum):将数据字节按 16 比特整数依次累加,并对最终累加和取反码,作为校验字段填入报文段首部。
  • 运输层(TCP/UDP)中因特网检验和通常由操作系统软件计算,仅占用 16 比特,开销低但检错保护相对较弱;相比之下,链路层差错校验通常由适配器硬件实现,能够快速执行更复杂的循环冗余检测(CRC)。

循环冗余检测(CRC)

循环冗余检测(Cyclic Redundancy Check, CRC)编码又称多项式编码(Polynomial Code),广泛应用于现代以太网和 WiFi 硬件中。CRC 将发送的比特串视作系数为 0 和 1 的多项式,所有运算均基于模 2 算术(不带进位的加法和借位的减法,等价于异或运算 ⊕\oplus)。

计算原理:

  1. 发送方与接收方预先协商一个 r+1r + 1 比特的生成多项式(Generator) GG(最高位必须为 1)。
  2. 对于给定的 dd 比特数据段 DD,发送方需要计算出 rr 个附加比特 RR,将其附加在 DD 之后构成 d+rd + r 比特的帧模式,使得该模式在模 2 算术下恰好能被 GG 整除。
Pasted image 20231201150249.png

校验码 RR 的推导:

  • 数据左移 rr 位并拼上 RR,数学上表示为 D⋅2r⊕R=nGD \cdot 2^r \oplus R = nG。
  • 等式两边同时异或 RR 得:D⋅2r=nG⊕RD \cdot 2^r = nG \oplus R。
  • 由模 2 算术除法可知,RR 即为 D⋅2rD \cdot 2^r 除以 GG 得到的余数: R=remainder(D⋅2rG)R = \text{remainder}\left(\frac{D \cdot 2^r}{G}\right)

工业界广泛采用 IEEE 定义的 CRC-32 标准,其生成多项式为: GCRC-32=1000001001100000100001110110110111G_{\text{CRC-32}} = 1000001001100000100001110110110111

多路访问链路和协议

在广播信道中,由于介质共享,当两个或多个节点同时发送帧时,信号会在信道上叠加破坏,导致接收方无法解析,这一现象称为碰撞(Collide),参与碰撞的所有帧均会损坏丢失。

如何协调多个并发节点对单一共享广播信道的接入,即为多路访问问题(Multiple Access Problem)。理想的多路访问协议通常希望满足两项特性:

  1. 当仅有 1 个节点活跃时,该节点独占信道,可享有全量带宽 RR bps。
  2. 当有 MM 个节点并发活跃时,各活跃节点的平均吞吐量接近 R/MR/M bps,公平且调度开销小。

多路访问协议主要分为三大类:信道划分协议、 随机接入协议与轮流协议。

信道划分协议

将信道资源划分为固定切片分给各节点,主要包括:

  • 时分多路复用(TDM):将时间划分为周期性时间帧,每个时间帧细分为若干等长时隙(Slot),节点在指定时隙内传输。
  • 频分多路复用(FDM):将总信道频带划分为若干更窄的子频带,各节点分配独立子信道并发传输。
  • 码分多址(CDMA):为每个节点分配正交编码,实现同频、同时并发传输。

随机接入协议

在随机接入协议中,传输节点以信道全速 RR 传输,不作固定时隙或频段独占;当发生碰撞时,各节点延迟随机时间后重试。

时隙 ALOHA(Slotted ALOHA)

模型假设:

  • 所有帧长度均为 LL 比特。
  • 时间被离散化为长度为 L/RL/R 秒的时隙,节点只能在时隙起始时刻开始发送。
  • 全网节点保持严格时钟同步。
  • 若发生碰撞,所有相关节点在该时隙结束前均能检测到碰撞事件。

运行机制:

  • 节点有新帧时,等待下一个时隙开始并发送全帧。
  • 若无碰撞,传输成功;若发生碰撞,节点在该时隙结束前检出,随后以概率 pp 在后续各时隙重传,直至成功。

信道效率推导: 协议效率定义为全网长期运行中成功时隙的占比。假设有 NN 个活跃节点,各节点在每个时隙以概率 pp 发送,则某一时隙恰好有 1 个节点发送(传输成功)的概率为: P(成功)=Np(1−p)N−1P(\text{成功}) = N p (1 - p)^{N-1} 对 pp 求导求极值,令 N→∞N \to \infty 时,最大利用率极限为: lim⁡N→∞Pmax⁡=1e≈0.37\lim_{N \to \infty} P_{\max} = \frac{1}{e} \approx 0.37 这意味着信道最多只能达到 37% 的有效吞吐。

纯 ALOHA(Pure ALOHA)

纯 ALOHA 不做时隙切分与全局同步。节点一旦有新帧到达,立即完整推入信道;若遭遇碰撞,节点立即以概率 pp 重新传输,或等待一个完整帧的传输时间后再次评估重传。

Pasted image 20240404134242.png

由于缺少时隙约束,易发生碰撞的危险窗口比时隙 ALOHA 扩大了一倍,最大效率仅为 1/(2e)≈0.181/(2e) \approx 0.18(待补充详细推导)。

CSMA(载波侦听多路访问)

为了提升随机接入效率,CSMA 引入了类似人类对话的两个基本规则:

  • 载波侦听(Carrier Sensing):“说话前先听”。节点在发送前先侦听信道,若检测到信道正忙,则推迟发送;若检测到信道持续空闲,才开始传输。
  • 碰撞检测(Collision Detection):“边说边听”。传输节点在发送自身数据的同时持续监控介质,一旦检测到来自其他节点的干扰电平,立即停止发送,并等待随机退避时间。

信道传播时延的影响: 即便有载波侦听,碰撞依然可能发生。原因是物理信号在介质上传播存在时延(以光速有限传播)。如下图所示,节点 B 开始发送后,信号尚未传播到节点 D,D 侦听信道仍为空闲并开始发送,最终导致两者的信号在介质中相撞。

Pasted image 20240404151417.png

CSMA/CD(带碰撞检测的 CSMA)

在经典以太网中采用 CSMA/CD。节点一旦检测到碰撞,立即中止当前帧的传输(避免在已损坏的帧上继续浪费信道时间),转而发送一个人为干扰信号(Jamming Signal)强化碰撞,然后执行退避算法。

[待补图]

二进制指数退避算法(Binary Exponential Backoff):

  • 当帧经历第 nn 次碰撞后,节点随机从集合 {0,1,2,…,2n−1}\{0, 1, 2, \dots, 2^n - 1\} 中选取一个整数 KK。
  • 以太网节点实际退避等待的时间量为 K×512K \times 512 比特时间(即在以太网上发送 512 比特所需的时间)。
  • nn 达到 10 之后,选择集合上限不再增加(维持在 1023);若连续碰撞 16 次则宣告传输失败并放弃。由于可选等待窗口随碰撞次数呈指数级翻倍,冲突剧烈时能迅速疏解信道竞争。

CSMA/CD 的信道效率: 设 dpropd_{prop} 为两节点间的最长单程传播时延,dtransd_{trans} 为传输一个最大帧的时间,当网络节点规模较大时,CSMA/CD 的长期运行效率渐近公式为:

效率=11+5dprop/dtrans\text{效率} = \frac{1}{1 + 5 d_{prop} / d_{trans}}

当传播时延 dprop→0d_{prop} \to 0(距离很短)或传输时延 dtransd_{trans} 很大(帧很大、传输速率慢)时,效率逼近 100%。

轮流协议(Taking-Turns Protocol)

轮流协议旨在兼顾轻载时的低时延与重载时的公平无碰撞:

轮询协议(Polling Protocol)

指定一个主节点,以轮询(Poll)方式依次询问每个从节点是否有数据待发。

  • 优点:彻底杜绝碰撞,重载效率高。
  • 缺点:引入轮询时延(主节点必须依次询问每个节点,即便空闲节点也需耗费轮询开销);存在单点故障风险(主节点宕机全网瘫痪)。

令牌传递协议(Token-Passing Protocol)

网络中没有集中式主节点,一个被称为 令牌(Token) 的控制帧在节点间按固定环路拓扑依次传递。

  • 节点收到令牌后,若有数据待发,最多发送预设上限数量的帧,随后必须把令牌转交至下一个节点;若无数据待发,立即向后传递令牌。
  • 缺点:同样存在令牌传递开销;若某个节点崩溃未转发令牌或令牌比特受损丢失,必须依赖复杂的恢复机制重建令牌环。
[ CLICK TO MIX THE FIRST DRINK ]