《数据通信与网络》笔记--数据链路层的差错控制协议

《数据通信与网络》笔记--数据链路层的差错控制协议
 

下面介绍三个用于差错控制的协议。

1.停止等待自动重复请求协议（Stop-and-Wait ARQ）

下图就是停止等待自动重复请求的工作过程：

图中，Sn指向将要被发送的帧的编号，Rn指向期待下一次收到的帧的编号。

其中帧的编号是可以循环使用的，由编号字段的位长决定，如果编号字段为2位，则编号范围为0~3（0~2*2-1），上图中编号范围为0~1，所以编号字段为1（0~2-1）

处理的步骤如下：

1.发送方发送编号0的帧并启动定时器，接收方接收到后，期待下一次收到的帧的编号为1,并发送ACK1给发送方

2.发送方在定时器规定的时间内接收到ACK1，定时器停止，Sn指向1，即下一次发送编号为1的帧。

3.发送方发送编号1的帧并启动定时器，但是在传输途中丢失。

4.发送方侧定时器超时，再次发送编号为1的帧并启动定时器，接收方接收到后，期待下一次收到的帧的编号为0，并发送ACK0给发送方

5.发送方在定时器规定的时间内接收到ACK0，定时器停止，Sn指向0，即下一次发送编号为0的帧。

6.发送方发送编号0的帧并启动定时器，接收方接收到后，期待下一次收到的帧的编号为1，并发送ACK1给发送方

7.发送方在定时器规定时间内没有接收到ACK1，所以重新发送Sn指向的帧（编号为0），但是接收方期待的是编号为1的帧，编号为0的帧已经确认收到，所以丢弃编号为0的帧，然后发送ACK1给接收方。

 

以上就是停止等待自动重复请求协议的工作过程，但是，这个协议的效率十分低效，如果是我，绝对不会用。。。

 

2.回退N帧自动重发请求协议（Go-Back Automatic Repeat Request ）

在这个协议中，涉及到滑动窗口概念，滑动窗口时一个抽象的概念，用来定义发送方和接收方关心的序列范围，发送方关心的序列范围是发送滑动窗口，接收方关心的序列式接收滑动窗口。

在回退N帧自动重发请求协议中，发送滑动窗口的大小必须小于2^m（m是窗口的位长，原因等会再解释），接收滑动窗口大小为1，下面说明下协议，下图中，灰色部分为窗口的范围，编号的位段为2，所以发送窗口大小为2^2-1=3，接收滑动窗口大小为1。Sf为第一个要被确认的帧，Sn为接下来要被发送的帧。Rn为期待要被接收到的帧。

 

 

1.发送方第一个被发送的帧是0，第一个要被确认的帧是0.
2.发送方发送了帧0，下一个要被发送的帧变成1，接收方接收到帧0，下一个期待被接收的帧变成1，然后发送ACK1
3.发送方接收到ACK1，下一个要被确认的帧变成1
4.发送方发送帧1，下一个要被发送的帧变成2，接收方接收到帧1，下一个期待被接收到的帧变成2，然后发送ACK2，但是ACK2在传输途中丢失
5.发送方发送帧2，下一个要被发送的帧变成3，接收方接收到帧2，下一个期待被接收到的帧变成3，然后发送ACK3.
6.发送方发送帧3，下一个要被发送的帧变成4，接收方接收到帧3，下一个期待被接收到的帧变成4，然后发送ACK4.
7.发送方接收到ACK3，下一个要被确认的帧变成3，这边可能大家会有疑问，为什么发送方没有接收到ACK2,就能保证接收方已经接收到帧1了呢，大家想一想，如果接收方没有接收到帧2，Rn的值一直都是1，所以发送方接收到ACK3，表示帧2肯定已经被接收到了。
8.发送方接收到了ACK4，下一个要被确认的帧变成4

 

在这个协议中，我们只是用一个定时器，即当Sf == Sn的是用启动定时器，当定时器到时间时，如果Sn不等于Sf，那么就重发Sf到Sn之间的所有帧。

 

为什么窗口大小一定要小于2^m，请看下图：

1.发送方发送编号为0的帧，第一个要被确认的帧为0，接下来要被发送的帧为1，接收方期待接收的帧为0，但是发送的ACK丢失。

2.发送方没有接收到ACK，所以Sf依然为1，接下来继续发送编号为1的帧，Sn变为2，接收方期待接收的帧为1，但是发送的ACK丢失。

3.发送方没有接收到ACK，所以Sf依然为1，接下来继续发送编号为2的帧，Sn变为3，接收方期待接收的帧为2，但是发送的ACK丢失。

4.发送方没有接收到ACK，所以Sf依然为1，接下来继续发送编号为3的帧，Sn变为4，接收方期待接收的帧为3，但是发送的ACK丢失。

5.发送方始终都没有接收到编号为1的帧的ACK，此时定时器超时，发送方要依次发送Sf到Sn之间的所有帧，于是发送了编号为0的帧，此时接收方期待的帧编号也是1，于是本来接收方应该拒绝该帧，但是却被当接收了，导致了错误。

 

所以结论是：发送滑动窗口的大小必须小于2^m

 

回退N帧自动重发请求协议比停止等待自动重复请求协议有了一定的进步，但是定时器到时间是重发所有没有确认的帧还是降低了链路的使用率。

 

选择性自动重发请求协议（Selective Repeat ARQ）

选择性自动重发请求协议应该是对回退N帧自动重发请求协议的一个改进，在退N帧自动重发请求协议中接收滑动窗口的大小是1，但是在选择性自动重发请求协议中，接收滑动窗口的大小不是1，发送和接收窗口的大小最多是2^m/2（m是窗口为位长，原因等会再解释），下图说明了该协议的工作原理：

1.发送方第一个被发送的帧是0，第一个要被确认的帧是0.

2.发送方发送帧0，启动定时器，下一次发送的帧变成1，接收方接收到后，窗口向后滑动一个帧，下一个期待帧是1，并发送ACK1.

3.发送方接收到ACK1后，解除定时器，接下来第一个要被确认的帧加1，变成1。

4.发送方发送帧1，下一次发送的帧变成2，但是帧1在发送过程中丢失。

5.发送方发送帧2，下一次发送的帧变成3，并启动定时器，接收方接收到了帧2，因为帧2在接收窗口中，所以成功接收，但是此时Rn还是指向1，所以发送了NAK1

6.发送方发送帧3，下一次发送的帧变成4，并启动定时器，接收方接收到了帧3，因为帧2在接收窗口中，所以成功接收，但是此时Rn还是指向1，此时NAK1已经发送过了，所以没有再发送NAK1.

7.发送方接收到了NAK1，重新发送帧1，接收方接收到了帧1，此时接收方的窗口中的帧已经全部接收到，滑动窗口，并发送ACK4.

8.发送方接收到了NAK4，说明接收方的帧都已经接收完毕，窗口进行滑动，解除所有定时器

 

下面解释下为什么发送和接收窗口的大小最多是2^m/2，下图窗口大小大于2^(m-1)（m为2），即3.

1.发送方发送帧0，下一次发送的帧变成1，此时接收方下一个期待帧是0，接收到帧0后，Rn变成1，窗口进行滑动，再发送ACK1，但是ACK1在传输过程中丢失。

2.发送方发送帧1，下一次发送的帧变成1，此时接收方下一个期待帧是1，接收到帧1后，Rn变成2，窗口进行滑动，再发送ACK2，但是ACK2在传输过程中丢失。

3.发送方发送帧2，下一次发送的帧变成3，此时接收方下一个期待帧是2，接收到帧2后，Rn变成3，窗口进行滑动，再发送ACK3，但是ACK3在传输过程中丢失。

4.发送方Sn已经超过了窗口大小，所以无法进行发送，等到定时器超时，发送方重新发送了帧0，接收方窗口中包含帧0，所以帧0被接收方错误地接收了。

 

最后结论：发送和接收窗口的大小最多是2^m/2