计算机网络——链路层

链路层概述

链路层承担以下工作：

1. 封装成帧：每个网络层的数据报在经过物理链路传输之前，几乎所有链路层协议都会把它封装成帧（Frame）。
2. 链路接入：媒体访问控制（Medium Access Control，MAC）是链路层的一部分，规定了帧在链路上的传输规则。
   • 对点对点链路，通常使用简单的点对点协议（Point-to-Point Protocol，PPP），仅需在链路空闲时发送PPP帧即可；
   • 当多个节点共享单个广播链路时，各种问题就会出现，此时我们使用以太网，以太网的帧有时也叫MAC帧，这是本文的主要内容；
   • 如果需要使用以太网接入点对点网络（如ASDL），则使用以太网上点对点协议（PPP over Ethernet，PPPoE）将PPP帧封装在以太网帧中，在以太网中搭建点对点隧道。
3. 可靠交付：如同TCP一样，在多个节点之间移动链路层帧时，提供可靠交付服务的链路层协议保证不会产生差错。通常易出差错的链路（如无线链路）才提供这种服务，否则容易浪费性能。
4. 差错检测和纠正：链路层通常提供机制检测帧中的比特差错，以防止转发出现差错的帧。链路层的差错检测通常更加复杂且用硬件实现，有些时候还提供从差错中恢复的能力。差错检测和纠正只是可靠交付服务的一个子集，因此尽管许多链路层协议提供差错检测，其仍不提供可靠交付服务。

链路层的主体部分实现在网络适配器（Network Adapter，又称网络接口卡，Network Interface Card，NIC）上。 这是主板上的一块专用芯片，因此，许多链路层功能实际上是由硬件实现的。 早年间这块芯片还是通过物理上分离的一张连接到总线上的卡实现的，现在的网卡通常直接综合在主板上，形成局域网在主板（LAN on motherboard）配置。

当然，并非所有传输层功能都位于硬件上。 传输层硬件必须通过总线和CPU通信，而CPU必须能够寻址到网卡并接受网卡的中断。 链路层的软件组件实现了高层功能，发送时需填充地址信息并激活控制器硬件，接收时需响应中断并把数据报交给上层协议。 链路层就是网络协议栈中软件和硬件交接的地方。

差错检测与纠正

链路层可能需要实现比特级差错检测和纠正，因此，为了保护比特免受差错，链路层发送端会增加差错检测和修正比特（Error Detection and Correction，EDC）来保护数据$D$。 由于比特差错的问题，接收方接收的数据可能不同于发送的，接收方在只能接收到可能被修改的数据$D^\prime$和$EDC^\prime$的情况下，必须能够探测出比特差错。 需要注意的是，出现了差错不一定代表能够检测到这个差错，也可能出现未检出的比特差错（Undetected bit error），而优秀的差错检测与纠正算法必须使这种事件发生的概率足够小。

我们将介绍三种常见的差错检测技术。

奇偶校验

差错检测的最简单方式之一就是加入一个奇偶校验位（Parity bit）。 以偶校验方案为例，假设要发送的信息为$d$比特，那么偶校验方案为数据附加一位，使得这$d+1$比特中1的个数恰好为偶数。 如数据0111 0001 1010 1011的校验位就是1。 奇校验方案则反之。

这种校验方案非常简单，然而如果出现了偶数个差错，就会导致其不能检出。 如果我们假设比特差错的概率小，且之间是独立事件，那么多个比特同时出现差错的概率是非常小的。 不幸的是，研究表明，差错通常聚集在一起，而不是独立发生，因此只使用一位的奇偶校验方案的漏检率可以达到50%。

接下来我们研究二维奇偶校验。 我们把数据依次排列成$i$行$j$列的二维表格，然后为表格的每一行和每一列计算校验位，这样就能产生$i+j+1$个校验位。 注意我们也要为产生的校验位计算校验位，因此会产生一个额外的位。 比如对于数据101011111001110，我们把它排列成三行五列，然后计算校验位：

1 0 1 0 1 | 1
1 1 1 1 0 | 0
0 1 1 1 0 | 1
----------+---
0 0 1 0 1 | 0

这种校验位不仅可以检测，还可以修复数据和校验位的单个比特的差错。 其也能检测分组中任何两个比特差错的任意组合，但不能修复。

接收方不仅能检测，还能修复差错比特的能力称为前向纠错（Forward Error Correction，FEC）。 这种技术很有价值，因为其能在接收端自发修复错误以避免重发，避免两倍RTT的时延。 这对实时网络或长传播时延的网络（如深空通信链路）非常有用。

校验和

在校验和技术中，$d$比特序列被视作$\lceil d/k \rceil$个$k$比特无符号数字的序列。 把这些数字加起来就形成了校验和。

此前我们介绍的因特网检验和（Internet checksum）就是基于这种方法。

校验和方法的分组开销相对较小，但是其提供的差错保护相对较弱。 相较于此后介绍的、常用于链路层的CRC方法，这种方法可以用软件相对快速的实现，而链路层则可以时延硬件进行更加复杂的计算。

循环冗余检测

如今计算机网络中通常广泛使用循环冗余检测（Cyclic Redundancy Check，CRC）编码进行差错检测。 这种编码将所有数字看作模二多项式域（记为$\mathbb{Z}_2[X]$）上的一个多项式，然后在这个多项式域上进行运算。 比如二进制数11011就被转换成多项式$X^4 + X^3 + X + 1$，注意到这个多项式的次数比位数少一。

回忆一下，在这个域上的加法相当于按位异或，任何数的相反数为其自身，而乘法相当于按位与。 比如我们尝试计算$(X^2+X)(X+1)$： \((X^2 + X)(X + 1) \equiv X^3 + 2 X^2 + X \equiv X^3 + X \pmod 2\) 这相当于计算二进制乘法：110 * 11 = 1010，注意这和一般的二进制乘法不同，因为进位方式不同。

注意到这个是一个域，因此其上常用的带余除法仍然成立。 实际上循环冗余检测基于以下带余除法： \(M(X) \cdot X^n = Q(X) \cdot G(X) + R(X)\) 其中多项式$M(X)$就是原数据转化成的多项式，而$G(X)$称为生成多项式（Generator）。 显然，根据带余除法的性质，$\mathrm{deg}(R(X)) < \mathrm{deg}(G(X))$，这意味着余多项式代表的二进制数的位数一定小于生成多项式代表的二进制数的位数。 商多项式$Q(X)$没有实际用途。 让后我们进行移项： \(M(X) \cdot X^n - R(X) \equiv Q(X) \cdot G(X) \equiv 0 \pmod{G(X)}\) 我们又知道$\mathbb{Z}_2[X]$上任何数的相反数为其自身，因此有： \(M(X) \cdot X^n + R(X) \equiv 0 \pmod{G(X)}\) 出于计算上的简便，我们直接假设$n = \mathrm{deg}(G(X))$，这相当于直接把$n-1$位的余数附加到在原消息后。

我们通常使用CRC-n来表示一个CRC算法，这个表示法中的$n$和上式中的$n$相同。 由于附加的余数正好比运算多项式少一位，因此CRC-n使用一个$n$次生成多项式，实际上是一个$n+1$位的二进制数； 相对地余数是$n-1$次多项式，所以其对应的二进制数实际上是$n$位的。

发送方和接收方协商产生一个生成多项式，然后发送方先在消息后附加$n$个零，除以生成多项式计算余数$R(X)$，在余数前面填充$0$至$n-1$位然后直接替换附加的零。 接收方收到这个消息之后，直接把消息除以生成多项式$G(X)$，检查余数是否为零即可。 由于所有运算都和逻辑门对应，这个算法可以相对容易地用硬件计算。

链路层通常采用标准规定的CRC-32多项式，其二进制数表示为：

1 0000 0010 1100 0001 0001 1101 1011 0111

标准的CRC多项式经过精心选择，以探测出所有小于等于$n$位的连续差错。 此外，在适当的假设下，CRC能够以$1-\frac{1}{2^n}$的概率探测到更长的连续差错。 CRC还能探测出任何奇数个差错。

多路链路访问

对于广播链路（Broadcast link），一个至关重要的问题就是多路访问问题（Multiple access problem），即如何协调多个发送和接受信道的问题。 相对地，点对点链路（Point-to-point link）则不需要解决这些问题，因此相对简单。 计算机使用多路访问协议（Multiple access protocol）来协调解决这一问题。

这个问题的关键在于解决碰撞（collide）。 当多个节点同时发送帧时，从这个信道接受帧节点就会接收到多个混杂的帧，这通常导致没有一个接收端可以收到正常的帧，此时就称传输的帧在接收方处碰撞。 如果发生大量碰撞，则大量带宽将被浪费掉。

多路访问协议负责解决这种问题，我们通常将多路访问协议分为三种：信道划分协议（channel partitioning protocol）、随机接入协议（random access protocol）和轮流协议（taking-turns protocol）。

我们希望任何多路访问协议尽量满足以下要求：

1. 当仅有一个节点发送数据时，它应该利用整个信道的吞吐量；
2. 当$N$个节点发送数据时，一段较长时间内平均下来每个节点应该平分吞吐量；
3. 协议是分散的，即不会因为某一个节点的故障导致整个系统崩溃；
4. 协议是简单的，即不会花费大量性能。

信道划分协议

我们此前介绍电路交换时叙述的时分多路复用（TDM）和频分多路复用（FDM）都是信道划分协议。

时分多路复用将时间划分为等长的时间帧（time frame），然后把时间帧划分为时隙（Slot）。 每个节点分配一个时隙，然后仅在其时隙中发送信息。 时分多路复用非常公平且消除了碰撞，但是每个节点仅能使用自己的时隙，即使其他所有节点都不选择发送信息，从而造成大量的带宽浪费。

频分多路复用原理相似，只是其按照频率而非时间划分信道。 其优点和缺点都是相似的。

第三种信道划分协议是码分多址（Code Division Multiple Access，CDMA）。 这种协议为不同的节点分配不同的编码，然后每个节点使用唯一的编码来为其数据进行编码。 CDMA允许不同的节点同时传输，而相应的接收方，只要知道编码，就可以正确接收所有数据，而无论干扰如何。 这种方式曾经常用于军事，现在通常用于移动电话与蜂窝网络。

随机接入协议

在随机接入协议中，每个节点总是以全速发送，并在发生碰撞后重发信息。 当然，节点并不立刻重发该帧，而是等待一个随机时间再重发。

时隙ALOHA协议

我们先以最简单的随机接入协议：时隙ALOHA协议开始。

首先我们做下列假设：

1. 信道的速率为$R$，每一帧的长度为$L$；
2. 时间被划分为长度为$L/R$的时隙；
3. 节点仅在时隙开始时传输帧；
4. 每个节点都是同步的，即一个时隙同时开始，同时结束；
5. 节点在时隙结束前检测到碰撞。

这个协议的操作非常简单。 设$p \in (0,1)$：

1. 当节点有一个新帧等待发送时，在下一个时隙开始时立刻传输此帧；
2. 如果没有碰撞，则此帧成功传输；
3. 如果发生碰撞，则在此后每一帧以$p$的概率重传此帧，直到成功传输为止。每个节点的事件是独立的。

我们考虑计算这个协议的效率（efficiency），即当有大量活跃节点，每个节点有大量待传输数据时，在大量时间内成功传输的时隙占总时隙的比例。

我们只计算最大效率。 做一点简化，即假设$N$个节点都以$p$的概率发送帧，无论这个帧是新的还是重传的。 每个时隙一个节点传输而其他节点不传输时，这个时隙才能不出现碰撞而成功传输，因此一个节点成功传输的概率为$P = p(1-p)^{N-1}$，而$N$个节点成功的概率为： \(P(\text{成功})_N = \binom{N}{1} p (1-p)^{N-1} = Np(1-p)^{N-1}\) 简单研究一下这个函数。 我们先求一下导数： \(\frac{\mathrm{d} P_N}{\mathrm{d} p} = N(1 - p)^{N-2}(1-Np)\) 有两个零点：$p_0 = 1$和$p_1 = \frac{1}{N}$。 其在$\frac{1}{N}$处取极大值。 从而$\sup P_N = P_N(\frac{1}{N}) = (1-\frac{1}{N})^{N-1}$ 然后取极限： \(\lim_{N\to\infty} \sup P_N = \lim_{N\to\infty}(1 - \frac{1}{N})^{N-1} = \lim_{N\to\infty} \left( (1 + \frac{1}{-N})^{1-N} \right)^{-1} = \frac{1}{e}\) 因此，这个协议的最大效率只有约37%。

ALOHA

真正的ALOHA协议与时隙ALOHA协议不同，不使用时隙来同步不同节点的发送。 当一个链路层帧准备发送时，其立刻进行发送，如果在发送途中不经历碰撞则成功发送，否则等待一个帧传输时间，然后继续以$p$的概率重传此帧。

我们假设传输帧划分一个单位时间。 对单个节点，假设其在$t_0$时间开始传输，则在时间间隔$[t_0 - 1, t_0]$中其他节点不能开始传输； 相对地，在进行传输时，即在时间间隔$[t_0, t_0 + 1]$中，其他节点也不能开始传输。 因此，单个节点成功传输的概率为： \(P(\text{success}) = p (1-p)^{N-1} (1-p)^{N-1} = p (1-p)^{2(N-1)}\) 按相似的分析方法，其最大效率仅有$\frac{1}{2e}$。

载波侦听多路访问

载波侦听多路访问（Carrier Sense Multiple Access，CSMA）和具有碰撞检测的载波侦听多路访问（CSMA with Collision Detection，CSMA/CD）是一族协议，这些协议广泛应用于以太网中。 它们使用下面的规则防止碰撞：

1. 在传输前侦听信道，在没有其他帧发送时才进行发送，这个技术称为载波侦听（Carrier sensing）；
2. 如果在传输时发现其他节点也在发送，则停止发送，这个技术称为碰撞检测（Collision detection）。

即使进行了载波侦听，碰撞检测依然是必要的，这是因为信道传播时延（Channel propagation delay）。 一个端点发出帧后，另一个端点由于传播时延不能立刻收到这一帧，因此在时延中，其仍可能选择发出自己的帧。 如果这样，就会发生碰撞，因此碰撞检测仍然是必要的。

对于CSMA/DA协议，每个节点其依次进行以下步骤：

1. 从网络层获取数据报，封装成帧并放入网卡缓存中；
2. 侦听信道直到信道空闲，然后发送帧；
3. 在传输过程中保持侦听信道；
4. 如果没有发生碰撞，则传输完成；
5. 如果发生碰撞，则等待一个随机的时间量，然后返回步骤2。

如何选择这个时间量是值得讨论的话题，显然当碰撞节点较少时时间应比较短，反之则比较长。 在以太网和DOCIS中使用二进制指数回退（Binary exponential backoff）算法。 当某一帧经历$n$次碰撞后，其从$[\![ 0, 2^n-1]\!]$中选择一个自然数作为$K$值，然后等待512比特进行传输所需时间的$K$倍。 显然，发生碰撞的次数越多，等待时间的期望就越大，且以二的指数增大。

接下来我们尝试计算CSMA/CD的效率，假设不使用二进制指数回退，而是随机选择时间。

我们假设时间被分为两倍任意两个节点之间最大的传播时间的时隙。 通常这个时间足够小，因此假设分组总是在时隙开始时发送。 那么要么不发生碰撞而在在本时隙内成功完成传输，又因为时隙时间大于传播时间，因此时隙结束时所有节点都能发现此节点正在使用信道，所以其他端点不会进行发送，而整个发送都不会发生碰撞； 要么发生碰撞，由于时隙的时间为传播时间的两倍，到结束时发生碰撞的任何一方都能得知碰撞而停止发送，因此下一个时隙后信道又空出来了，所以我们以时隙作为等待时间的单位。

按照和时隙ALOHA相同的算法，其成功的最大概率为$\frac{1}{e}$，因此一个帧成功发送所需等待的时隙期望为$e$。 失败次数的期望为$e-1$，每次失败占用一个时隙，因此失败占用的时间为$2 (e-1) T_\text{传播}$。 相对地，即使传输成功，下一次传输仍然需要等到下一个时隙开始，由于传输时间随机，因此期望还要加上半个时隙的时间。 计算效率： \(\eta = \frac{T_\text{成功，占用}}{T_\text{失败} + T_\text{成功，总时间}} = \frac{T_\text{传输}}{2(e-1)T_\text{传播} + T_\text{传播} + T_\text{传输}} = \frac{1}{4.4\frac{T_\text{传播}}{T_\text{传输}} + 1}\)

轮流协议

以上介绍的协议都只符合期望中的第一点，而不符合第二点，即所有节点不能平分带宽，而轮流协议可以做到这一点。 轮流协议有许多种，其中大部分可分为两类：轮询协议和令牌传递协议。

轮询协议（Polling protocol）分配一个主节点，然后主节点向其他节点以轮询（Poll）的方式分配带宽。 其逐一告知节点每个节点能传输的最大帧的数量，等待其传输所有帧，然后向下一个节点发送数量，如此重复。 主节点还可以监听信道，如果发现信道上没有信号，则认为当前节点已经发送完了，而提前终止其发送。 这一协议消除了碰撞和空时隙，效率大大提高。 然而，这一协议也引入了额外的时延（主节点进行通知所需的时间），因此难以利用全部带宽； 此外，如果主节点出错，则整个信道就瘫痪了。 802.15协议（其中包含蓝牙协议）使用这种方法。

令牌传递协议（Token-passing protocol）则使用一个称为令牌（Token）的特殊帧通知一个节点可以发送其他帧。 当一个节点收到令牌后，其发送不超过最大数目的帧数，然后把令牌发送给下一个节点； 如果没有待发送的帧则直接转移令牌。 这种协议和轮询协议类似，也能提高信道的使用率，同时其还不需要主节点。 然而，这种协议必须解决诸如令牌丢失等问题。 光纤分布式数据接口（FDDI）协议和802.5令牌环协议使用这种方法。

数据经电缆服务接口规范

此前讲过，电缆接入网通常将数千个住宅中的调制解调器于一个电缆调制解调器端接系统（Cable Modem Termination System，CMTS）连接。 这种连接通过数据经电缆服务接口规范（Data-Over-Cable Service Interface Specification，DOCSIS）进行多路访问。 这个规范同时使用了上述三种解决方法。

DOCSIS为上行（从调制解调器到CMTS）和下行（从CMTS到调制解调器）网络段使用不同的协议。 首先，两个信道都使用FDM进行多路复用。 下行信道带宽为6MHz，吞吐量约为40Mbps； 上行信道带宽为6.4MHz，吞吐量约为30Mbps。

下行信道虽然也是广播信道，但由于只有一个发送端，因此不存在碰撞问题。

对上行信道，可能存在碰撞问题。 首先，上行信道被划分为时间间隔，每个时间间隔由微时隙组成（类似TDM），上行带宽使用这些微时隙进行传送。 CMTS通过向调制解调器发送MAP控制报文以通知每个调制解调器使用哪一段微时隙。 当调制解调器需要需要上传报文时，其向CMTS发送请求帧。 这个请求帧可能碰撞，因为CMTS可能尚未向调制解调器分配微时隙，或是通过MAP报文收回了原来分配的微时隙。 但调制解调器不能侦听上行信道，因此其只能通过CMTS返回的MAP报文得知是否发生碰撞。 如果在下一个下行控制报文中，调制解调器没有发现对自己请求的响应，那么它就认为发生了碰撞。 发生碰撞以后，调制解调器以二进制指数回退的方式重发请求帧。