数据链路层¶

约 5053 个字预计阅读时间 25 分钟

功能¶

数据链路层利用物理层提供的位流服务，向网络层提供了明确的服务接口。其主要功能如下：

<1> 封装成帧
- 在一段数据前后添加首部和尾部，构成 Frame，是数据链路层的 PDU
<2> 差错检测
- 因为信道噪声等原因，帧在传输过程中可能出现错误
- 1) 位错: 帧中某些位出现差错
- 2) 帧错: 帧丢失、帧重复或帧失序等，属于传输差错
<3> 流量控制
- 链路两端的工作速率和缓存空间存在差异，可能存在发送方的发送能力大于接收方的接收能力，因此流量控制通过某种反馈机制限制发送方的发送速率

封装成帧¶

发送方依据一定规则，将网络层递交下来的分组封装成帧。组帧主要需要解决帧定界、帧同步、透明传输等问题。

实现组帧的方法主要有以下四种：

字节计数法 Byte Count

字节计数法在帧首部设置一个计数字段，记录该帧含有的字节数（包括计数字段本身占用的 1 字节）。当接收方读取帧首部的字节计数值时，就知道后面跟随的字节数从而确定结束位置。

但是如果传输过程中出现差错，例如计数字段错误，则帧边界划分依据被破坏，造成灾难性的后果：

字节填充定界符法 Flag bits with Byte Stuffing

使用特定字节 SOH 表示帧的开始，EOT 表示帧的结束。为了确保数据本身出现的特殊字符不被误判位首尾定界符，我们在特殊字符前填充转义字符 ESC 来加以区分。

若转义字符 ESC 也出现在数据中，则在其前面再添加一个 ESC 即可

比特填充定界符法 Flag bits with Bit Stuffing

比特填充法使用一个特定的比特串 01111110 (0x7E) 标志一个帧的开始和结束。为了不使数据字段中出现的比特流被误判为首尾标志，发送方会先扫描整个数据字段，每遇到 5 个连续的 1 就自动在后面插入一个 0，保证数据字段中不会出现 6 个连续的 1。

比特填充更容易被硬件实现，其性能由于字节填充。

物理层编码违例 Physical layer conding violations

物理层编码违例确保选择的定界符不会在数据部分出现。

例如对于物理层选用了 4B/5B 编码方案，则 5-bit 编码中有一半码字（16）未使用，可以用作帧定界符。

对于曼彻斯特编码/差分曼彻斯特编码，持续的高电平/低电平为违例码，也可以用作定界符。

违例编码法不采用任何填充计数就实现了数据的透明传输，但只适用于冗余编码的环境

差错控制¶

比特在传输过程中可能出现差错，我们通常利用编码技术来进行差错控制，可分为检错编码和纠错编码。

此处，码字（code word）指一个包含 \(m\) 个数据位和 \(r\) 个校验位的 \(n=m+r\) 位单元，描述为 \((n,m)\) 码。

码率即为码字中不含冗余部分所占的比率，可以用 \(m/n\) 来计算。

检错编码¶

为了实现检错，我们必须在传输时增加冗余校验信息。接收方根据收到的码字是否符合规则来判断传输是否发生错误。

奇偶校验码

奇偶校验码是一种最基本的检错码，它由 n-1 位数据和 1 位检验位组成：

奇检验码: 附加一个检验位后，n 位码字中 1 的个数为奇数
偶检验码: 附加一个检验位后，n 位码字中 1 的个数为偶数

奇偶校验码可以检测奇数位错误，即如果存在 1, 3, 5,... 个比特位传输错误，则可以发现错误。

循环冗余码

Cyclic Redundancy Code, CRC 是数据链路层广泛使用的检错技术。

<1> 发送方依据一个约定的多项式 \(G(x)\) 和待发送的数据，计算冗余码，将冗余码附加到数据后面一起发送
<2> 接收方收到数据和冗余码后通过 \(G(x)\) 计算数据和冗余码是否产生差错，做除法运算，若余数为 0，则未检测出错误

CRC 有四个国际标准生成式 \(G(x)\)，其中以太网、无线局域网均采用 CRC-32 生成多项式

对于一个待传送的 \(m\) 位数据，CRC 运算产生一个 \(r\) 位的冗余码，这样形成的帧长度为 \(m+r\) 位。

CRC 的检错能力很强，对于小于 \(r\) 位的错误，一定能够检测出；对于大于 \(r\) 位的错误，能检测出的概率为 \(1-2^{-r}\)，这个值非常接近于 1。

CRC 其实也具有纠错功能，但数据链路层只是用了它的检错功能

纠错编码¶

海明码是最常见的纠错编码，其特点是将有效信息和检验位分配到几个奇偶校验组中，若某一位出错，会引起有关的几个检验位改变，从而找出错位所在的位置。

海明距离（Hamming Distance）是两个码字之间对应比特不同的数目，例如 00001111 和 00000000 的海明距离为 4。

如果两个码字的海明距离为 \(d\)，则我们需要 \(d\) 个比特错误才可以把一个码字转换成另一个码字。据此，我们有理论：

为了检查出 \(d\) 个比特错，我们可以使用海明距离为 \(d+1\) 的编码
为了纠正 \(d\) 个错，我们可以使用海明距离为 \(2d+1\) 的编码

检错纠错

假设有 \(m\) 个信息位，\(r\) 个校验位，为了设计一个可以纠正单比特错误的纠错码，我们需要考虑码字可以表示的有效信息个数。

\(m\) 个信息位对应了 \(2^m\) 个有效信息，对于每个有效信息，共有 \(n\) 个与其距离为 1 的可纠错非法码字，再加上它自己共 \(n+1\) 个位模式。

我们需要保证码字的可表示的信息 \(2^n\) 大于所有位模式个数之和，即有 \((n+1)2^m \le 2^n\)。又 \(n=m+r\)，我们有不等式：

\[ (m+r+1) \le 2^r \]

即在已知 \(m\) 的前提下可以计算纠错单比特错误校验位数 \(r\) 的下界。

如果要纠错两比特错误，则共有 \(C_n^2\) 个距离为 2 的可纠错非法码字

为了理解海明码编码过程，我们以 \((15,11)\) 海明码为例，它设置了如下奇偶校验组：

图中已经填入数据位 01011001101，根据设置的校验组计算校验位的值如上，得到最后的码字 100110101001101。

那么此时如果有 1 bit 数据发生错误，那么我们根据这四组校验可以确定该位处于哪一列哪一行，从而实现纠错。

PPT 中还讲了 Reed-Solomon Code，此处暂时不写

流量控制¶

流量控制是由接收方控制发送方的发送速率，使接收方有足够缓冲空间来接收每个帧。

停止-等待协议

停止-等待协议是一种简单的流量控制方法，发送方每次只允许发送一个帧，发送后暂停，等待确认到达后发送下一帧；接收方接收到一帧后，需要恢复确认接收。

确认帧也被称为哑帧 dummy frame

一个帧在传输过程中损坏，此时接收方可以通过差错控制检测；但一个帧也有可能在传输过程中丢失，为了解决这个问题，发送方需要增加超时机制，在计时器达到一定时间后仍然没有收到确认时，自动重发该帧。

有了超时机制，就可能出现接收方多次收到同一个帧的情况，此时我们需要在帧头部设置序列号 SEQ，以判断这个是新帧还是应该丢弃的重复帧。

在这个协议中，唯一不明确的地方只有相邻两个帧的比对，因此此处只需要使用 1-bit 的序列号即可。

滑动窗口协议

数据链路层和传输层在流量控制上均用到了滑动窗口协议，它们区别如下

数据链路层控制的是相邻节点之间的流量；而传输层控制的是端到端的流量
数据链路层的控制手段是接收方收不下时就不返回确认；传输层的控制手段是接收方通过确认报文段中的窗口值来调整发送方的发送窗口

滑动窗口流量控制是一种更高效的流量控制方法，发送方维护一组连续的允许发送帧的序号，称为发送窗口，大小为 \(W_T\)；接收方维护一组连续的允许接收帧的序号，称为接收窗口，大小为 \(W_R\)。

发送方每收到一个按序确认的确认帧，就将发送窗口向前滑动一个位置。序号落入发送窗口内的数据帧可以继续发送，当窗口内全是已发送但还未收到确认的帧时，发送方就停止发送。

接收方只允许接收接收窗口之内的帧，并且每收到一个序号落入接收窗口的数据帧时，就将接收窗口向前滑动一个位置，并为该帧发回一个确认。

据此，只有接收方发送了确认，接收窗口向前滑动后，发送窗口才能向前滑动

根据滑动窗口的大小不同，我们设计了不同的可靠传输方案：

停止-等待协议: 发送窗口 \(W_T=1\)，接收窗口 \(W_R=1\)
后退N帧协议: 发送窗口 \(W_T\gt 1\)，接收窗口 \(W_R=1\)
选择重传协议: 发送窗口 \(W_T\gt 1\)，接收窗口 \(W_R\gt 1\)

可靠传输¶

可靠传输指发送方发送的数据都能被接收方正确接收，通常采用确认和超时重传两个机制完成，这种协议也被称为自动重传请求（ARQ）。

在 ARQ 协议中，数据帧和确认帧都需要编号，以区分数据帧和确认帧的对应关系。

停止-等待协议 S-W

从滑动窗口角度来看，停止等待协议的发送窗口和接收窗口大小均为 1。

正如上面所说，停止等待协议每发送一个帧就等待，我们只需要保证连续的两个帧序号不同即可，采用 1-bit 来编码，发送帧交替使用 0 和 1 标识，确认帧交替使用 ACK0 和 ACK1 标识。

若连续出现两个相同序号的数据帧，则说明发送方进行了超时重传；若连续出现两个相同序号的确认帧，则说明接收方收到了重复帧。

发送方和接收方都起码有一个帧大小的帧缓冲区，以保存可能需要重传的帧副本

后退 N 帧协议 GBN

后退 N 帧指发送方发送 N 个数据帧后，若发现这 N 个数据帧的前一个数据帧在超时后仍未收到确认，则该帧被判出错或丢失，此时发送方需要重传该帧以及其后的 N 帧。

接收方仍然必须按顺序接收帧，但是 GBN 协议中还允许接收方进行累积确认，即允许接收方在连续收到多个正确数据帧后，只对最后一个数据帧返回确认，表示该帧及之前的帧均已正确收到。

GBN 协议中，发送窗口 \(W_T\) 的大小不应该超过帧编号的总个数，否则接收方有可能无法分辨新旧数据帧。例如如果采用 n-bit 帧编号，则发送窗口大小应该满足 \(1\le W_T \le 2^n-1\)。

选择重传协议 SR

选择重传协议进一步允许接收方乱序接收帧，此时接收方可以先确认失序但正确到达并且序号仍在接收窗口的数据帧，但此时并不递交给网络层。等到缺失的数据帧到达后，再将其及之后已确认的帧一并送交。

为了使发送方仅重传出错的帧，接收方不能再采用累积确认，只能对每个数据帧逐一确认。接收方还需要设置大小与接收窗口大小相当的帧缓冲区，以暂存那些失序的数据帧。

SR 协议还设置了一个更有效的重传策略，当接收方检测到某个数据帧出错，就立即向发送方发送一个否定帧 NAK，要求发送方立即重传指定的数据帧，而不用等超时。（注意上图的 10 号帧的处理）

对于 n-bit 帧编号，我们要求以下两点：

\(W_R + W_T \le 2^n\)
\(W_R\le W_T\)
- 否则接收窗口永远不会填满，多出的空间无意义

一般情况下会设置 \(W_R=W_T\le 2^{n-1}\)。

MAC 子层¶

在 OSI 参考模型下，数据链路层实际分为两个子层：

MAC 子层：介质访问
LLC 子层：承上启下

因此本节要讲的其实是介质访问控制相关的问题。

如果令 \(D_0\) 表示网络空闲时的时延，\(D\) 表示网络的当前时延，那么在适当的假定条件下，可以用如下公式表示 \(D,D_0\) 和网络利用率 \(U\) 的关系：

\[ D= \frac{D_0}{1-U} \]

假定 \(D_0\) 是一个微小的非零值，根据函数特性，我们知道：当网络利用率达到 50% 时，时延就要加倍；当网络利用率超过 50% 时，时延急剧增大。

因此，我们需要设计一些优秀的介质访问控制协议，以更好地满足需求，提高信道利用率。

三大类多路访问协议

随机访问协议¶

ALOHA 协议

纯 ALOHA 协议的基本思想是，当总线形网络中的任何站点需要发送数据时，可以不进行任何检测就发送数据。若在一段时间内未收到确认，则认为传输过程中发生冲突，此时发送站点在等待随机时间后重新发送数据，直到成功。

总线形网络

只要两个帧在相同时间试图占用信道，就会发生冲突。冲突的帧被完全破坏，因此接收方不会返回确认。

纯 ALOHA 协议吞吐量很低，因此产生了时隙 ALOHA 协议，它同步了各站点的时间，将时间划分为一段段等长的时隙，时隙的长度大于等于一帧的传输时间，规定各站点只能在每个时隙开始时才能发送帧。

因此，冲突只可能发生在时隙的起点，冲突发生时只浪费一个时隙，此时冲突双方都等待随机时间后进行重传。

CSMA 协议

CSMA 的全称为载波监听多路访问 Carrier Sense Multiple Access，意指让每个站点在发送数据前都先对公用信道进行监听，确保信道此时空闲后再发送。

根据监听方式和监听到信道忙后的处理方式不同，CSMA 协议分为三种：

协议类型	信道空闲时行为	信道忙时行为	特点总结
1-持续 CSMA	立即发送	持续监听，并等待空闲后马上发送	如果两个以上的站在等待发送，一旦介质空闲就必定发生冲突
p-持续 CSMA	概率 p 发送，概率 1-p 推迟到下一个时隙	持续监听，直到空闲再按概率决策发送	只适用于时分信道
非持续 CSMA	立即发送	等待随机事件，再次监听	冲突可能性较低，但是延迟较高

从 1-持续到非持续，访问控制逐渐从激进变得保守

CSMA/CD (CSMA with Collision Detection) 是 CSMA 协议的改进方案，同时也属于 1-持续 CSMA，适用于总线形网络或半双工网络环境。

其中冲突检测指的是站点在发数据过程中也要持续检测信道，若检测到冲突，则立即停止发送数据，并等待随机时间后再次发送。

假设端到端传播时延为 \(\tau\)，那么一个站在发送数据后经过 \(2\tau\) 才能确定没有发生冲突，因此端到端往返传播时延 \(2\tau\) 称为争用期。以太网在发送数据时，如果争用期内没有发生冲突，则后续的数据就不会发生冲突，因此争用期内可发送的数据长度被规定为最短帧长，计算公式为：

\[ \text{最短帧长}=\text{最大单向传播时延} \times 2 \times \text{数据传输速率} \]

对于 10Mbps，争用期长度为 51.2\(\mu s\) 的以太网，最短帧长为 64B

那么，在检测到冲突后，重发等待的随机时间具体怎么确定？CSMA/CD 使用二进制指数退避算法来确定冲突后重传的时机：

确定基本退避时间，一般取 \(2\tau\)
从离散集合 \([0,1,...,2^k-1]\) 中随机取一个数，记为 \(r\)，重传推迟时间即为 \(2\tau \times r\)
- 其中参数 \(k\) 取 \(\min [\text{重传次数},10]\)，即当重传次数超过 10 后，\(k\) 就一直取 10
当重传 16 次仍不成功，则认为该帧永远不会正确发出，抛弃该帧并向上层报告出错

以太网就采用了 CSMA/CD 协议：

吞吐量: 比 ALOHA 高，比 p-持续 CSMA 低
冲突率: 比 ALOHA 少，比 p-持续 CSMA 高

受控访问协议¶

位图协议 / 预留协议

TODO

令牌传递协议

令牌是一个特殊的控制帧，仅用作控制信道使用，它会沿着环形总线在各站之间依次传递。

当环上的一个站希望发送帧时，必须等待令牌。站点只有取得令牌后才能发送帧，因为令牌只有一个，所有信道上不会发送冲突。站点发送完一帧后，应释放令牌，以便让其他站使用。

当网络空闲时，环路中只有令牌帧在循环传递。
当令牌传递到有数据要发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附加自己需要传输的数据，将令牌变成一个数据帧，然后将这个数据帧发送出去。
数据帧沿着环路传输，接收到的站点一边转发数据，一边查看帧的目的地址。若目的地址和自己的地址相同，则接收站就复制该数据帧，以便进一步处理。
数据帧沿着环路传输，直到到达该帧的源站点，源站点收到自己发出去的帧后便不再转发。同时，通过检验返回的帧来查看数据传输过程中是否出错，若出错，则重传。
源站点传送完数据后，重新产生一个令牌，并传递给下一站点，交出信道控制权。

二进制倒计数协议

TODO

有限竞争协议：自适应树¶

TODO

Comments: