数据链路层协议需要解决的三个重要问题：

1. 封装成帧和透明传输
2. 差错检测
3. 可靠传输

3.2.1 封装成帧和透明传输

1. 封装成帧

封装成帧 (framing)：给网络层交付下来的分组添加一个首部和一个尾部，构成一个帧。帧的首部和尾部包含重要的控制信息，如帧开始符、源地址、目的地址、帧校验序列和帧结束符。接收方根据帧首部和尾部进行帧定界。

2. 透明传输

透明传输：数据链路层对上层交付的协议数据单元（PDU）的内容没有任何限制。

当帧的数据载荷部分出现帧定界符时，需要采取措施，使接收方数据链路层能够正确进行帧定界。

实现透明传输的方法：

1) 字节填充

字节填充：当使用面向字节的物理链路时，发送方在数据载荷中出现帧定界符的前面，插入一个转义字符 “ESC”（十六进制编码是 1B）。如果转义字符自身也出现在数据载荷中，则在转义字符的前面也插入一个转义字符。接收方在把数据载荷向上交付网络层之前，删除发送方插入的转义字符。

2) 比特填充

比特填充：当使用面向比特的物理链路时，发送方扫描数据载荷，只要出现 5 个连续的比特 1，就在其后填入一个比特 0。接收方在把数据载荷向上交付网络层之前，对数据载荷进行扫描，每当发现 5 个连续的比特 1 时，就把其后的一个比特 0 删除。

2013 年 题 37

HDLC 协议对 0111110001111110 组帧后对应的比特串为 ( ) 。

A. 011111000011111010

B. 01111100011111010111110

C. 01111100011111010

D. 01111100011111001111101

解析

高级数据链路控制协议 (High-level Data Link Control, HDLC) 采用帧首部和帧尾部中的标志字段作为帧定界符，其值为 01111110。

HDLC 为了实现“透明传输”，采用“零比特填充法”，即每五个连续的比特 1 后面插入一个比特 0。

因此答案为 A 。

并不是每一种数据链路层协议的帧都包含有帧定界标志。以太网的数据链路层协议没有采用字符填充法或比特填充法来实现透明传输。实际上，以太网的数据链路层封装好以太网帧后，将其交付给物理层。物理层还会在以太网前添加 8 字节的前导码，包含前同步码（前 7 个字节）和帧开始符（后 1 个字节），尾部没有帧结束符。

另外，以太网规定帧间间隔时间为 96 比特的发送时间。

3.2.2 差错检测

实际的通信链路会产生失真，导致比特在传输过程中产生差错。误码率 (Bit Error Rate, BER) 是衡量链路质量的指标。为了检测帧在传输过程中是否出现误码，需要采用差错检测措施。发送方的数据链路层根据帧的内容计算出检错码，填入帧尾部的帧检验序列（Frame Check Sequence, FCS）。接收方的数据链路层从帧尾部取出检错码，采用与发送方相同的检错技术，检测出帧在传输过程中是否出现了误码。

常用的检错技术如下。

1. 奇偶检验

奇偶校验：在待发送的数据后面添加 1 个校验位，使整个数据（包括所添加的校验位在内）中 “1” 的个数为奇数（奇校验）或偶数（偶校验）。

奇偶校验可以检测出奇数个位的误码，但无法检测出偶数个位的误码，也就是漏检。如下面的例子所示：

2. 循环冗余检验

循环冗余校验 (Cyclic Redundancy Check, CRC)：收发双方约定好一个生成多项式 $G(X)$。发送方基于待发送的数据和生成多项式 $G(X)$，计算出差错检测码，即冗余码，将冗余码添加到待发送数据的后面一起传输。接收方收到数据和冗余码后，通过生成多项式 $G(X)$ 来计算收到的数据和冗余码是否产生了误码。具体步骤如下：

• 发送方使用 CRC 的操作：采用二进制模 2 除法来计算余数，余数就是所计算出的冗余码。

  

• 接收方使用 CRC 的操作：采用二进制模 2 除法来计算余数，如果余数为 0，就可判定数据和冗余码中未出现误码；如果余数不为 0，则可判定数据或冗余码中出现了误码。

  

常用的生成多项式 $G(X)$ 有：CRC-16、CRC-CCITT 和 CRC-32。循环冗余校验码是检错码，而不是纠错码。

3.2.3 可靠传输

1. 可靠传输的相关基本概念

使用差错检测技术，接收方可以检测出帧在传输过程中是否产生了误码。取决于数据链路层提供的服务类型，对检测出的误码有不同的处理方式。如果数据链路层提供的是不可靠传输服务，则丢弃有误码的帧即可；如果提供的是可靠传输服务，则需要通过某种机制实现发送方发送什么，接收方就能收到什么。可靠传输的实现比较复杂，开销也比较大，是否需要可靠传输服务取决于应用需求。

在 TCP/IP 四层体系结构中，各层提供的可靠或不可靠传输服务的情况如图所示。

• 网络接口层：如果使用信道易受干扰的 802.11 无线局域网，那么其数据链路层必须实现可靠传输；如果使用信道质量好的以太网，那么其数据链路层不要求实现可靠传输。
• 网际层：IP 向其上层提供的是无连接、不可靠传输服务。
• 运输层：TCP 向其上层提供的是面向连接的可靠传输服务，而 UDP 向其上层提供的是无连接、不可靠传输服务。

实现可靠传输的三种机制：

• 停止 - 等待协议
• 回退 N 帧协议
• 选择重传协议

2. 停止 - 等待协议

1) 停止 - 等待协议的实现原理

停止 - 等待协议：发送方每发送完一个数据分组就必须停下来，等待接收方发来的确认（ACK）或否认（NAK）分组。如果接收方收到没有误码的数据分组，就发送 ACK 分组；如果存在误码，就丢弃该数据分组，并发送 NAK 分组。发送方收到 NAK 分组后就会重传出现误码的这个数据分组。

仅有确认、否认和重传机制的停止 - 等待协议无法实现可靠传输。例如，当出现数据分组丢失的情况时，发送方将不可能收到接收方的确认分组或否认分组。因此，发送方在每发送完一个数据分组时，应启动一个超时计时器。

若到了超时重传时间（RTO）但发送方仍未收到接收方的 ACK 分组或 NAK 分组，就重传之前已发送过的这个数据分组。RTO 应设置为略大于收发双方的平均往返时间 RTT。

在给停止 - 等待协议补充超时重传机制后，就可以不使用否认机制了。然而，使用否认机制也有其好处：使发送发在计时器超时前就尽快重传。

有了确认、否认、重传和超时重传机制的停止 - 等待协议仍然不能完全实现可靠传输。例如，当确认分组丢失时，接收方会收到两个相同的数据分组。如果接收方不能识别出所接收的数据分组与前一次接收的数据分组是重复的，则会导致分组重复这种传输差错。为了解决该问题，发送方必须给每个数据分组带上不同的序号，每发送一个新的数据分组就把它的序号加 1，以便接收方识别重复的分组。

对于停止 - 等待协议，使用 1 个比特编号就足够了，即可用序号有 0 和 1 这两个。

既然数据分组需要编序号，那么确认分组是否需要编序号呢？

下图给出了确认分组迟到的情况：为了使发送方能够判断收到的确认分组是否重复，应当给确认分组编序号。发送方收到重复的确认分组后，将其丢弃即可。

对于数据链路层，由于其点对点的往返时间 RTT 比较固定，一般不会出现确认分组迟到的情况，因此在数据链路层实现停止 - 等待协议时可以不对确认分组编序号。

2) 停止等待协议的信道利用率

为了简化起见，假设收发双方之间通过一条直连链路传送分组。发送方发送数据分组产生的发送时延为 $T_D$，数据分组正确到达接收方，接收方对数据分组的处理时间可忽略不计，立即给发送方发送确认分组，接收方发送确认分组产生的发送时延为 $T_A$，发送方对确认分组的处理时间也可忽略不计，收发双方之间的往返时间为 $RTT$。

因此，发送方在经过时间 $(T_D + RTT + T_A)$ 后，就可以发送下一个新的数据分组。由于仅仅是在 $T_D$ 内才用来发送数据分组，因此停止一等待协议的信道利用率 $U$ 的计算公式如下所示：

$$U = \frac{T_D}{T_D + RTT + T_A}$$

2018 年 题 36

主机甲采用停 - 等协议向主机乙发送数据，数据传输速率是 3kbps，单向传播延时是 200ms，忽略确认帧的传输延时。当信道利用率等于 40% 时，数据帧的长度为 ()。

A. 240 比特

B. 400 比特

C. 480 比特

D. 800 比特

解析

由于

$$\text{信道利用率} = \frac{\text{数据帧的发送时延}}{\text{数据帧的发送时延} + \text{单程传播时延} \times 2}$$

代入数据，得到：

$$40\% = \frac{\frac{x \text{ b}}{3000 \text{ b/s}}}{\frac{x \text{ b}}{3000 \text{ b/s}} + 200\text{ ms} \times 2}$$

解得 $x = 800 \text{ b}$。因此，数据帧的长度为 800 比特。

3. 回退 N 帧协议

回退 N 帧协议：采用流水线传输方式，并利用发送窗口来限制发送方连续发送数据分组的数量，属于连续 ARQ 协议。

发送窗口和接收窗口：发送方需要维护一个发送窗口，在未收到接收方确认分组的情况下，发送方可将序号落入发送窗口内的所有数据分组连续发送出去。接收方需要维护一个接收窗口，只有正确到达接收方且序号落入接收窗口内的数据分组才被接收方接收。

发送窗口和接受窗口的滑动情况如下：

• 接收方每正确收到一个序号落入接收窗口的数据分组，就将接收窗口向前滑动一个位置，这样就有一个新的序号落入接收窗口。与此同时，接收方还要给发送方发送针对该数据分组的确认分组。
• 发送方每收到一个按序确认的确认分组，就将发送窗口向前滑动一个位置，这样就有一个新的序号落入发送窗口，序号落入发送窗口内的数据分组可继续被发送。

在回退 N 帧协议的工作过程中，发送方的发送窗口和接收方的接收窗口按上述规则不断向前滑动。因此，这类协议又称为滑动窗口协议。

下面通过几个例子来说明回退 N 帧协议的工作过程。

回退 N 帧协议的工作过程举例 1 （正常情况）：

1. 发送方将序号落入发送窗口内的 0 ~ 4 号数据分组连续发送出去。
2. 0 ~ 4 号数据分组按序正确到达接收方。
3. 接收方按序接收 0 ~ 4 号数据分组。每接收到一个数据分组，接收窗口就向前滑动一个位置，并且给发送方发送相应的确认分组。接收窗口当前滑动到序号 5，接收方给发送方发送了 0 ~ 4 号确认分组。
4. 0 ~ 4 号确认分组按序正确到达发送方。
5. 发送方按序接收 0 ~ 4 号确认分组。每接收到一个确认分组，发送窗口就向前滑动一个位置，这样就有新的序号 5 ~ 1 落入发送窗口中。

发送方应将发送缓存中已收到确认的数据分组的副本删除，而接收方应当从接收缓存中尽快取走已正确接收的数据分组。

在无传输差错的情况下，回退 N 帧协议的信道利用率比停止 - 等待协议的信道利用率有显著提高。提高的程度取决于发送窗口的大小。

回退 N 帧协议的工作过程举例 2（超时重传，回退 N 帧）：

1. 发送方将序号落入发送窗口内的 0~4 号数据分组连续发送出去，其中 2 号数据分组在传输过程中出现误码。接收方按序接收 0~1 号数据分组并给发送方发送 0~1 号确认分组，接收窗口向前滑动两个位置，序号 2 落入接收窗口内。
2. 接收方通过 2 号数据分组中的检错码，检测出了 2 号数据分组中有误码，因此将其丢弃。发送方收到接收方发来的 0~1 号数据分组后，将发送窗口向前滑动两个位置，这样就有新的序号 5~6 落入发送窗口中。
3. 接收方丢弃序号未落入接收窗口内的 3~4 号数据分组，并给发送方发送针对最近已按序接收的 1 号数据分组的确认分组，即 1 号确认分组。发送方将序号落入发送窗口内的 5~6 号数据分组发送出去。
4. 发送方收到针对 1 号数据分组的 2 个重复确认，忽略即可。接收方收到序号未落入接收窗口内的 5~6 号数据分组，将其丢弃，并给发送方发送针对最近已按序接收的 1 号数据分组的确认分组，即 1 号确认分组。
5. 发送方收到针对 1 号数据分组的 2 个重复确认，忽略即可。已发送的 2 号数据分组出现了超时，于是发送方将序号落入发送窗口内的、超时的 2 号数据分组和其后已发送的 3~6 号数据分组全部重传。尽管 3~6 号数据分组并未出现误码，但是接收方只能接收按序到达的数据分组，因此一旦 2 号数据分组出现差错，其后连续发送的 3~6 号数据分组都要被重传。这就是回退 N 帧协议名称的由来，即一旦出错就需要退回去重传已发送过的 N 个数据分组。

一个数据分组的差错就可能引起大量数据分组的重传。在信道质量较差（容易出现误码）的情况下，回退 N 帧协议的信道利用率并不比停止 - 等待协议的信道利用率高。

回退 N 帧协议的接收方采用累积确认的方式。

• 接收方对序号为 n 的数据分组的确认，就表明接收方已正确接收序号到 n 为止的所有数据分组。
• 接收方不必对收到的每一个数据分组都发送一个相应的确认分组，而是可以在收到几个序号连续的数据分组后，对按序到达的最后一个数据分组发送确认分组。
• 接收方何时发送累积确认分组，由具体实现决定。

回退 N 帧协议的工作过程举例 3（累积确认）：

1. 发送方将序号落入发送窗口内的 0~4 号数据分组连续发送给接收方。
2. 接收方按序正确接收 0 号和 1 号数据分组，并给发送方发送累积确认，确认号为 1，表明已正确接收序号到 1 为止的所有数据分组。接收方将接收窗口向前滑动两个位置，序号 2 落入接收窗口内。
3. 接收方按序正确接收 2~4 号数据分组，并给发送方发送累积确认，确认号为 4，表明已正确接收序号到 4 为止的所有数据分组。接收方将接收窗口向前滑动，序号 5 落入接收窗口内。
4. 1 号累积确认分组在传输过程中丢失了，而 4 号累积确认分组正确到达发送方。
5. 发送方收到 4 号累积确认分组后，将发送窗口向前滑动 5 个位置，这样就使得已获得累积确认的 0~4 号数据分组的序号移出了发送窗口，而新序号 5~1 落入了发送窗口。

由该例可以看出，

• 累积确认的优点：
  • 减少向网络中注入确认分组的数量。
  • 即使确认分组丢失，也可能不必重传数据分组。
• 累积确认的缺点：
  • 不能向发送方及时准确地反映出接收方已正确接收的所有数据分组的数量。

下面简单介绍一下回退 N 帧协议的发送窗口尺寸 ${W}_{T}$ 和接收窗口尺寸 ${W}_{R}$ 。

回退 N 帧协议规定：${W}_R = 1, 1 < {W}_T \leq {2}^{n} - 1$ 。其中，$n$ 是用来给数据分组编序号的比特数量。如果从滑动窗口协议的角度来看停止一等待协议，其 ${W}_{T}$ 和 ${W}_{R}$ 的取值都固定为 1 。对于回退 N 帧协议，其 ${W}_{R}$ 与停止 - 等待协议的相同 (都为 1 )，但其 ${W}_{T}$ 应该大于 1 且不能超过其范围上限，否则可能会造成接收方无法分辨新、旧数据分组的情况，下面举例说明这种情况。

回退 N 帧协议的工作过程举例 4 （发送窗口尺寸超越其上限）：

假设采用 3 个比特给数据分组编序号，则有 0~7 共 8 个序号可供循环重复使用。 ${W}_{T}$ 的最大值为 7 （即 ${2}^{2} - 1$），若令 ${W}_{T} = 8$ 来超越其范围上限，思考出现怎样的情况。

1. 发送方将序号落入发送窗口内的 0~7 号数据分组，并连续发送给接收方。
2. 接收方按序正确接收 0~7 号数据分组，并向发送方发送累积确认，确认号为 7，表明已正确接收序号到 7 为止的所有数据分组。接收方将接收窗口向前滑动 8 个位置，序号 0 落入接收窗口内。
3. 累积确认分组在传输过程中丢失。
4. 已发送的 0 号数据分组出现超时，发送方将序号落入发送窗口内的、超时的 0 号数据分组及其后已发送的 1~7 号数据分组全部重传。
5. 发送方重传的 0~7 号数据分组按序正确到达接收方，但此时接收方并不知道这 8 个数据分组之前就已经被正确接收过了，因此还会接收这些数据分组，这就造成了分组重复的传输差错。

2009 年题 35

在数据链路层使用后退 N 帧 (GBN) 协议的情况下，发送方已经发送了编号为 0~7 的帧。当计时器超时时，如果发送方只收到了 0、2、3 号帧的确认，那么发送方需要重发的帧数是多少？

A. 2

B. 3

C. 4

D. 5

解析

在回退 N 帧协议中，发送方在超时前没有收到部分帧的确认，发送方会重新发送所有未被确认的帧，从丢失的第一帧开始。由题意可知：

• 编号为 0、1、2、3 的帧已经确认，无需重新发送。
• 编号为 4、5、6、7 的帧未收到确认，需要重新发送。 因此，未确认的帧编号为：4、5、6、7（共 4 个帧）。

2014 年题 36

主机甲与主机乙之间使用后退 N 帧（GBN）协议传输数据，甲的发送窗口尺寸为 1000，数据帧长为 1000 字节，信道带宽为 100Mbps，乙每收到一个数据帧就立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间的单向传播延迟是 50ms，则甲可以达到的最大平均数据传输速率约为 ()。

A. 10Mbps

B. 20Mbps

C. 80Mbps

D. 100Mbps

解析

单个数据帧的传输时间为：

$$T_{\text{传输}} = \frac{\text{数据帧长度}}{\text{信道带宽}} = \frac{8000 \text{ b}}{100 \times 10^6 \text{b/s}} = 8 \times 10^{-5} \text{ s}$$

单向传播延迟为 50 ms，因此往返时间（RTT）为：

$$\text{RTT} = 2 \times 50 \text{ ms} = 0.1 \text{ s}$$

因此，最大平均数据传输速率为：

$$\text{最大平均传输速率} = \frac{\text{窗口内总数据量}}{T_{\text{传输}}+\text{RTT}} = \frac{1000 \times 8000 \text{ b}}{8 \times 10^{-5} \text{ s} + 0.1 \text{ s}} \approx 80 \text{ Mbps}$$

4. 选择重传协议

选择重传协议：为了进一步提高信道利用率，只重传出现差错的数据分组，接收窗口的尺寸大于 1，以便先收下失序但正确到达接收方且序号落入接收窗口内的数据分组，等到所缺数据分组收齐后再一并送交上层。

为了使发送方仅重传出现差错的数据分组，接收方不能再采用累积确认，而需要对每一个正确接收的数据分组进行逐一确认。显然，选择重传协议比回退 N 帧协议复杂，并且接收方需要有足够的缓存空间，来暂存失序但正确到达接收方且序号落入接收窗口内的数据分组。

选择重传协议的 $W_T$ 和 $W_R$ 都大于 1。若采用 $n$ 个比特给数据分组编序号，为了保证接收方的接收窗口向前移动后，接收窗口内的新序号与之前的旧序号没有重叠（也就是不会造成接收方无法分辨新、旧数据分组的情况），需要满足条件：$W_T + W_R \le 2^n$。另外，$W_R$ 不应超过 $W_T$ （否则没有意义），因此 $W_R$ 不应超过序号范围的一半，即 $W_R \le 2^{n-1}$。当 $W_R$ 取其最大值 $2^{n-1}$ 时，$W_T$ 能取到的最大值也只能为 $2^{n-1}$。一般情况下，在选择重传协议中，$W_T$ 和 $W_R$ 是相同的。

下面说明选择重传协议的工作过程。假设采用 3 个比特给数据分组编序号，则有 0~7 共 8 个序号可供循环重复使用。 $W_R$ 取其最大值 4 ，则 $W_T$ 的最大值也只能取为 4。

1. 发送方将序号落入发送窗口内的 0~3 号数据分组连续发送给接收方。其中 0 号数据分组在传输过程中出现误码，接收方将其丢弃。
2. 接收方将失序但正确到达接收方且序号落入接收窗口内的 1~3 号数据分组进行缓存，并给发送方发送相应的 1~3 号确认分组。缓存的 1~3 号数据分组暂时不能交付给上层。由于还未收到序号落入接收窗口内的 0 号数据分组，因此接收窗口不能向前滑动。
3. 发送方收到失序的 1~3 号确认分组后并不能向前滑动发送窗口，但要记录 1~3 号数据分组已被确认，因此只有 0 号数据分组被超时重传。0 号数据分组正确到达接收方。
4. 接收方正确接收序号落入接收窗口内的 0 号数据分组，并给发送方发送 0 号确认分组，0 号确认分组正确到达发送方。接收方将接收窗口向前滑动 4 个位置，序号 4~7 落入接收窗口内。
5. 发送方收到期盼已久的 0 号确认分组后，将发送窗口向前滑动 4 个位置，序号 4~7 落入发送窗口内。现在，接收方可以接收序号落入接收窗口内的 4~7 号数据分组，而发送方可以将序号落入发送窗口内的 4~7 号数据分组连续发送出去。

2011 年 题 35

数据链路层采用选择重传协议 (SR) 传输数据，发送方已发送了 0~3 号数据帧，现已收到 1 号帧的确认，而 0、2 号帧依次超时，则此时需要重传的帧数是 ()。

A. 1

B. 2

C. 3

D. 4

解析

与回退 N 帧协议不同，选择重传协议不采用累积确认，接收方需要对每一个正确接收的数据分组进行逐一确认。

发送方仅重传未收到确认而超时的数据帧，因此重传 0 号和 2 号这两个数据帧。