计算机网络：数据链路层 - 可靠传输协议

可靠传输概念

如下所示，帧在传输过程中受到干扰，产生了误码。接收方的数据链路层，通过真伪中的真检验序列 FCS 字段的值，也就是检错码可以检测出帧中出现了比特差错。那么接下来该如何处理呢？

这取决于数据链路层向其上层提供的服务类型：

• 如果提供的是不可靠传输服务，则仅仅丢弃有误码的帧，其他什么也不做。
• 如果提供的是可靠传输服务，那就还要想办法实现发送端发送什么，接收端就收到什么

一般情况下，有线链路的雾码率比较低，为了减小开销，并不要求数据链路层向上提供可靠传输服务，即使出现了物码可靠传输的问题，由其上层处理。

然而，对于无线链路，由于其容易受到干扰，雾码率比较高，因此要求数据链路层必须向上层提供可靠传输服务。

最后要注意的是：可靠传输服务并不仅局限于数据链路层，其他各层均可选择实现可靠传输服务。

接下来本博客将讲解三种可靠传输协议，这三种可靠传输实现机制的基本原理并不仅限于数据链路层，可以应用到计算机网络体系结构的各层协议中。

停止-等待协议 SW

如图所示，收发双方基于互联网进行通信，纵坐标为时间，发送方给接收方发送数据分组：

接收方收到后对其进行差错检测，若没有误码，则接受该数据分组并给发送方发送确认。分组简称为ACK，发送方收到对所发送数据分组的确认分组后才能发送下一个数据分组。

假设这个数据分组在传输过程中出现了误码，接收方收到后对其进行差错检测，发现了误码，则丢弃该数据分组，并给发送方发送否认分组，简称为NAK：

发送方收到对所发送数据分组的否认NAK，分组后就知道了之前自己所发送的数据分组出现了差错而被接收方拒绝，于是立刻重传该数据分组。因此发送方每发送完一个数据分组后，并不能立刻将该数据分组从缓存中删除，只有在收到针对该数据分组的确认分组后，才能将其从缓存中删除。

发送方每发送完一个数据分组后，就停止发送下一个数据分组，等待来自接收方的确认分组或否认分组。

• 若收到确认分组，则可继续发送下一个数据分组
• 若收到否认分组，则重发之前发送的那个数据分组。

这样就实现了发送方发送什么，接收方最终都能收到什么，也就是所谓的可靠传输。

但实际情况远比我们想象的要复杂，来看这种情况，发送方给接收方发送数据分组，然而该数据分组在传输过程中丢失了。

需要说明的是，对于数据链路层点对点信道而言，不太容易出现这种情况，但对于多个网络通过多个路由器互联的复杂互联网环境而言，这种情况是会经常出现的。

对于这种情况，接收方既然收不到数据分组，那么也就不会无缘无故的发送确认或否认分组。如果不采取其他措施，发送方就会一直处于等待接收方确认或否认分组的状态。为了解决该问题，可以在发送方发送完一个数据分组时启动一个超时计时器。若到了超时计时器所设置的重传时间，而发送方仍收不到接收方的确认或否认分组，则重传原来的数据分组，这就叫做超时重传。一般可将重传时间选为略大于从发送方到接收方的平均往返时间。

如图所示，发送方超时重传之前所发送的数据分组：

接收方正确接收重传的数据分组后，给发送方发送确认分组。发送方收到确认分组后发送下一个数据分组。接收方正确接收该数据分组后给发送方发送确认分组。到目前为止貌似基于停止等待使用确认或否人分组，再加上超时重传的手段，就可以实现可靠传输了。

再来看这种情况，既然发送方发送的数据分组可能丢失，那么接收方发送的确认或否认分组就也有可能丢失。例如发送方发送了一个数据分组，接收方正确接收该数据分组后，给发送方发送确认分组，但该确认分组在传输过程中丢失了。这必然会造成发送方对之前所发送数据分组的超时重传：

假设这个重传的数据分组也正确到达了接收方，那么现在问题来了，接收方如何判断该数据分组是否是一个重复的分组呢？

为了避免分组重复这种传输错误，必须给每个数据分组带上序号。对于停止等待协议，由于每发送一个数据分组就进行停止等待，只要保证每发送一个新的数据分组，其序号与上次发送的数据分组的序号不同就可以了。因此用一个比特来编号就够了，记序号 0 和 1。

这样根据数据分组的序号接收方，就可以判断出该数据分组是否是重复的。接收方丢弃重复的数据分组，并给发送方发送针对该数据分组的确认分组，以免发送方对该数据分组的再次超时重传。

第一次接受方接收到了DATA0，然后往回传递ACK表示接收到了该分组。发送方没有受到ACK，触发超时重传。当接收方第二次接收到DATA0，就知道这和上一次是同一个分组，把它丢弃再重传一次ACK。当发送方收到ACK，就发送和上一次编号不一样的分组DATA1，接收方收到DATA1，发现和上一次不一样，于是正常接收该分组。

我们通过确认分组丢失的情况，引出了给数据分组编号的问题，请大家思考一下，既然数据分组需要编号，那么确认分组是否也需要编号呢？

来看这种情况：

发送方发送 0 号数据分组，接收方正确接收后给发送方发送确认分组，由于某些原因，该确认分组迟到了，这必然会导致发送方对 0 号数据分组的超时重传。

在重传的 0 号数据分组的传输过程中，发送方收到了迟到的确认分组，于是发送 1 号数据分组。接收方收到重传的 0 号数据分组后，发现这是一个重复的数据分组，将其丢弃，并针对该数据分组给发送方发送确认分组，以免发送方再次超时重传该数据分组。现在问题来了，我们可以非常清楚的看到，这是一个对 0 号数据分组的重复确认，但是发送方又如何知道这个ACK是 0 号数据的，而不是 1 号数据的呢？

如果不采取其他措施的话，发送方会误认为这是对 1 号数据分组的确认。如果对确认分组也进行编号，就可以使发送方避免这种误判。如图所示：

该确认分组的序号为0，发送方通过确认分组的序号知道这是一个重复的确认分组，忽略即可。这个过程叫做确认迟到。

我们用给确认分组编号的方法解决了确认迟到所导致的重复确认的问题。需要说明的是，对于数据链路层的点对点信道往返时间比较固定，不会出现确认迟到的情况。因此，如果只在数据链路层实现停止等待协议，可以不用给确认分组编号。

接下来我们对停止等待协议的一些注意事项进行一下小结：

• 接收端检测到数据分组有误码时，将其丢弃，并等待发送方的超时重传。
• 为了让接收方能够判断所收到的数据分组是否是重复的，需要给数据分组编号。由于停止等待协议的停等特性，只需一个比特编号就够了。记序号 0 和一。
• 为了让发送方能够判断所收到的确认分组是否是重复的，需要给确认分组编号。数据链路层一般不会出现确认分组迟到的情况，因此在数据链路层实现停止-等待协议，可以不用给确认分组编号。

接下来我们来看看停止等待协议的信道利用率，发送方发送完一个数据分组后就停止发送，并等待接收方对该数据分组的确认。当收到确认分组后，可以发送下一个数据分组：

• $T_D$：发送方发送数据分组所耗费的发送时延
• RTT：收发双方之间的往返时间
• $T_A$： 接收方发送确认分组所耗费的发送时延

途中忽略了接收方对数据分组的处理时延以及发送方对确认分组的处理时延。

总时间为：$T_D$ + RTT + $T_A$，因此信道的利用率 U 可以用下式来计算：

$$\text{ 信道利用率 }U=\frac{T_D}{T_D+RTT+T_A}$$

$T_A$一般都远小于$T_D$可以忽略，当 RTT 远大于$T_D$时，信道利用率会非常低。为了克服停止等待协议，信道利用率很低的缺点，就产生了另外两种协议，即后退N帧协议 GBN 和 选择重传协议。

回退N帧协议 GBN

我们刚介绍了停止等待协议，发送方每发送完一个数据分组，就要停止发送，并等待接收方的确认分组。当收到接收方的确认分组后，才能发送下一个数据分组，如此反复进行。可以看出，发送方每发送完一个数据分组，就至少要等待一个收发双方之间的往返时间。当往返时间较大时，例如卫星链路。停止等待协议的信道利用率很低。若出现超时重传，则信道利用率更低。如图所示，如果发送方在收到接收方的确认分组之前，可以连续发送多个数据分组，则可大大提高信道利用率：

回退N帧协议，该协议在以上传输的基础上，利用发送窗口来限制发送方可连续发送分组的个数。我们来举例说明，假设采用 3 个比特给分组编序号，因此序号的取值范围是 0- 7。如图所示：

这是收发双方各自的分组序号。当序号增加到7，下一个序号又从 0 开始。

发送方要维持一个发送窗口，序号落在发送窗口内的数据分组可被连续发送，而不必等收到接收方的相应确认分组后再发送：

发送窗口的尺寸记为$W_T$ 。对于本例，其取值范围是[0, 7]。本例取$W_T$ 的值为5。如果$W_T$ 的值取为 1，则是停止等待协议。如果$W_T$ 的值超过取值范围的上限，则会造成严重的错误，我们之后会举例详细说明。

序号落在发送窗口内的数据分组可以连续发送，而序号落在发送窗口外的数据分组不允许发送。

接收窗口的尺寸记为$W_R$ 对于回退N帧协议，其取值只能为 1，这一点与停止等待协议是相同的。如图所示：

序号落在接收窗口内的这个数据分组允许接收，而序号落在接收窗口外的数据分组不允许接收。

我们首先来看最简单的情况，也就是无差错的情况，发送方将序号落在发送窗口内的 0- 4 号数据分组依次连续发送出去：

他们经过互联网的传输，正确到达了接收方，也就是没有出现乱序和误码。接收方按序接收，他们每接收一个数据，接收窗口就向前滑动一个位置，并给发送方发送接收分组的确认分组：

发送方每接收一个确认分组，发送窗口就向前滑动一个位置，这样就有新的序号落入了发送窗口。发送方可以将收到确认的数据分组从缓存中删除了：

接下来我们来看累积确认的概念。使用回退N帧协议的接收方可以采用累积确认的方式，也就是说接收方不一定要对收到的数据分组逐个发送确认，而是可以在收到几个数据分组后，对按序到达的最后一个数据分组发送确认ACKn ，表示序号为 n 及以前的所有数据分组都已正确接收了。

我们来举例说明累计确认：

发送方将序号落在发送窗口内的 0- 4 号数据分组依次连续发送出去。他们经过互联网的传输，正确到达了接收方，按序接收。

当接收完 0 号和 1 号数据分组后，给发送方发送了一个累计确认ACK 1。当接收完 2- 4 号数据分组后，又给发送方发送了一个累计确认ACK4。假设ACK 1在传输过程中丢失了，而 ACK 4正确到达了发送方：

发送方接收ACK 4后就知道了序号为 4 及之前的数据分组已被接收方正确接收了，于是将发送窗口向前滑动 5 个位置。这样就有新的序号落入了发送窗口。从本例可以看出，使用累计确认的其中一个优点就是即使确认分组丢失，发送方也可能不必重传。例如本例中aACK 1丢失了，但并没有造成 1 号数据分组的超时重传。使用累计确认还有其他好处，例如可以减小接收方的开销，减少对网络资源的占用等。

接下来我们来看出现差错的情况，发送方将序号落在发送窗口内的这 5 个数据[5,6,7,0,1]分组依次连续发送出去。他们经过互联网的传输到达了接收方，假设他们在传输过程中受到了干扰，其中 5 号数据分组出现了误码：

接收方通过数据分组中的检错码发现了错误，于是丢弃该数据分组。而==后续到达的这四个数据分组的序号与接收窗口中的序号不匹配，接收方同样也不能接受他们，将他们丢弃：

然后对之前按序接收的最后一个数据分组进行确认，也就是发送ACK4，每丢弃一个数据分组就发送一个ACK4 ：

这四个ACK4经过互联网的传输到达了发送方。发送方之前就接收过ACK4，当收到这些重复的ACK4 时，就知道了之前所发送的数据分组出现了差错，于是可以不等超时计时器超时就立刻开始重传，至于收到几个重复确认就立刻重传，由具体实现来决定。

在本例中，尽管序号为 6701 的数据分组之前已经正确的到达接收方，但由于 5 号数据分组误码不被接受，他们也受到牵连而不被接受发送方还要重传这些数据分组，这就是所谓的 go back N，也就是回退N帧。可见当通信线路质量不好时，回退N帧协议的信道利用率并不比停止等待协议高。

为了减少开销，接收方不一定每收到一个按序到达且无误码的数据分组，就给发送方发回一个确认分组，而是可以在连续收到好几个按序到达且无误码的数据分组后，才针对最后一个数据分组发送确认分组，这称为累积确认。

选择重传协议 SR

刚刚我们介绍了回退N帧协议。回退N帧协议的接收窗口尺寸$W_T$ 能等于一，因此接收方只能按序接收正确到达的数据分组。一个数据分组的误码就会导致其后续多个数据分组不能被接收方按序接收而丢弃，尽管他们没有误码。这必然会造成发送方对这些数据分组的超时重传，显然，这是对通信资源的极大浪费。

为了进一步提高性能，可设法只重传出现误码的数据分组。因此，接收窗口的尺寸$W_R$不应再等于一，而应大于一，以便接收方先收下失序到达但无误码，并且序号落在接收窗口内的那些数据分组，等到所缺分组收齐后再一并送交上层。这就是本节课所要介绍的选择重传协议。

需要注意的是，选择重传协议，为了使发送方仅重传出现差错的数据，分组接收方不能再采用累积确认，而需要对每个正确接收到的数据分组进行逐一确认。

下面我们来举例说明选择重传协议的工作原理。假设采用 3 个比特给分组编序号，因此序号的取值范围是 0- 7。如图所示：

• 发送窗口的尺寸$W_T$的取值范围是[1,7]，本例取$W_T$的值为4。序号落在发送窗口内的这 4 个数据分组可以连续发送。而序号落在发送窗口外的数据分组不允许发送
• 接收窗口的尺寸$W_R$的取值一般情况下可与发送窗口的尺寸$W_T$的取值相同，在本例中，其值为4。序号落在接收窗口内的这 4 个数据分组允许接收，而序号落在接收窗口外的数据分组不允许接收。

发送方将序号落在发送窗口内的这四个数据分组依次连续发送出去。他们经过互联网的传输陆续到达接收方，但其中的 2 号数据分组丢失了：

只要序号落入接收窗口内且无误码的数据分组，接收方都会接收， 先接受0 号和 1 号数据分组，并发送 0 号和 1 号确认分组，接收窗口向前滑动两个位置：

这样就有 4 和 5 这两个新的序号落入接收窗口。接收方接收 3 号数据分组并发送 3 号确认分组：

但接收窗口不能向前滑动，因为 3 号数据分组是未按需到达的数据分组。

发送方每按序收到一个确认分组发送窗口就向前滑动一个位置。发送方接收 0 号和 1 号确认分组，发送窗口向前滑动两个位置，这样就有 4 和 5 这两个新的序号落入发送窗口，发送方将序号落入发送窗口的 4 号和 5 号数据分组发送出去：

发送方接收 3 号确认分组，但发送窗口不能向前滑动，因为这是一个未按序到达的确认分组。发送方还未收到 3 之前的 2 号确认分组。不过需要记录 3 号数据分组已收到确认，这样该数据分组就不会超时重发：

4 号和 5 号数据分组到达接收方，接收他们并发送 4 号和 5 号确认分组，但接收窗口不能向前滑动，因为他们是未按序到达的数据分组，接收方还未收到他们之前的 2 号数据分组：

假设在 4 号和 5 号确认分组的传输过程中，发送方针对 2 号数据分组的重传计时器超时了，发送方重传 2 号数据分组：

4 号和 5 号确认分组陆续到达发送方接收他们，但发送窗口不能向前滑动，因为他们是未按序到达的确认分组，发送方还未收到他们之前的 2 号确认分组，不过需要记录 4 号和 5 号数据。分组已收到确认，这样他们就不会超时重发：

发送方之前重传的 2 号数据。分组到达接收方，接收方接收该数据分组并发送 2 号确认。分组接受窗口现在可以向前滑动四个位置，这样就有 6701 这四个新的序号落入接收窗口：

2 号确认分组经过互联网的传输到达发送方接收，该确认分组发送窗口现在可以向前滑动四个位置，这样就有 6701 这四个新的序号落入发送窗口。发送方现在就可以继续将这四个序号的数据分组依次发送出去了：

可见，选择重传协议是对回退N帧协议的优化，将接收窗口扩大，哪怕数据不是按照顺序发送的，也可以接收。这样就可以避免对一些已经正常传递的数据的重发，提升效率。