计算机网络数据通信可靠传输机制：停等协议、滑动窗口、ARQ协议

计算机网络数据通信过程中，由于一些原因数据在信道传输过程中可能发生如比特差错（1001变为1000），乱序（数据块1、2、5、6、3、4），数据丢失（数据块1、2、5）等问题，那么为了能够使数据可以正确稳定的传输和接收，计算机网络制定了一些规则，即可靠传输机制。比如在数据链路层的可靠传输通常使用确认和重传两种机制来完成。

• 肯定应答：接收方对收到的数据帧校验无误后送回肯定应答信号ACK，它是一种无数据的控制帧，这种控制帧使得接收方可以让发送方知道哪些内容被正确接收，发送方可继续发送后续帧。

• 否定应答重传：接收方收到一个数据帧后经校验发现错误，则送回一个否定应答信号NAK，发送方必须重新发送出错帧。

• 超时重传：发送方在发送一个数据帧以后就开始一个计时器，在一定时间内如果没有得到关于该数据帧的应答信号，那么就重新发送该数据帧，直到发送成功为止。

我们首先讨论没有传输错误的流控技术，流控是一种协调发送站和接收站工作步调的技术，其目的是避免由于发送速度过快，使得接收站来不及处理而丢失数据。即传输过程中不会丢失帧，接收到的帧都是正确的，无须重传，并且所有发出的帧都能按顺序到达接收端。常见的流量控制方式有两种：停止-等待协议、滑动窗口协议。

停止-等待协议

停等协议的工作原理是每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。

停等协议的优点是简单，但是缺点是信道利用率太低。信道利用率为发送方在一个发送周期内有效地发送数据所需要的时间占整个发送周期的比率。而发送周期为发送方从开始发送数据到收到第一个确认帧ACK为止的时间。假设发送站为S1，接收站为S2，tp为传播延迟，tf为发送一帧的时间（称为一帧时），则发送一帧的时间即发送周期为：TFA=2tp+tf。

所以信道利用率：E=tf/(2tp+tf)，若定义a=tp/tf（传播时延与帧时之比）则E=1/(2a+1)。这是停等协议下信道的最高利用率，实际利用率会更低一些，因为还忽略了某些时间的开销，比如发送应答信号ACK的时间。那么在这里tp又可以理解为传播线路长度d和信号的传播速度v的比值，tf可以理解为帧长L和数据速率R的比值，所以又有a=（d/v）/（L/R）=（Rd/v）/L。

来看下面的例子。通常卫星信道的传播延迟是270ms，假设数据速率是64kbps，帧长是4000位。那么a=64*270/4000=4.32，卫星链路的利用率为E=1/(2a+1)=1/(2*4.32+1)=1/9.64=0.104。可见卫星链路的利用率仅为1/10左右，大量的时间用在等待应答信号上了。

滑动窗口协议

由于停等协议性能差、 信道利用率低，因此产生了流水线协议，最典型的流水线协议： 滑动窗口协议。滑动窗口协议的主要思想是允许连续发送多个数据帧而无须等待应答。窗口是指缓存中的一块区域，发送窗口是指要发送出去的这块存储区域，由发送方维持。如下图例（a），位于发送窗口内的五个帧都可以连续发送出去，不需要等待接收方的确认一个一个地发送，如此提高信道利用率。发送方每收到一个确认，就把发送窗口向前滑动一个帧的位置。图（b）表示发送方收到了对第1个帧的确认，于是把发送窗口向前移动一个帧的位置。若已经发送了前5个帧，那么现在就可以发送窗口内的第6个帧了。

接收方一般可采用累积确认的方式，即接收方不必对收到的数据帧逐个发送确认，而是在收到几个帧后，对按序到达的最后一个帧发送确认，表示到这个帧为止的前面的所有帧都已经收到了。

如下图，假设发送方S1与接收方S2进行通信，接收窗口（W收=5），发送窗口（W发=5）。为了使S2能够表示哪些帧已被成功接收，每个帧都给予一个顺序编号。如果帧编号字段为k位，则帧以2^k为模连续编号，下图k=3，可编8个序号帧。如发送端S1已发送最大数量5个数据帧，接收端S2则会发出一个应答信号ACKi，下图i=3，表明之前的0、1、2这三个帧已正确接收，发送端S1就可把窗口往右移3格，这里只要保证窗口是5格的，那么5，6，7这三个数据帧进入待发送状态。接下来的操作就是一样的了，确认包后，窗口往后移继续将未发送的包读进缓存，由于随着传送过程的进展窗口向前滑动，因而取名为滑动窗口协议。

那么根据前面的分析，从0号帧开始发送到ACK1到达S1的时间是2tp+tf，在这段时间内，S1可连续发送W个帧，它的工作时间是W*tf，所以滑动窗口协议的效率为：E=W*tf/（2tp+tf）=W/（2a+1）

差错控制ARQ协议

自动重传请求（Auto Repeat reQuest, ARQ），通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来差错的方法之一。结合前面的流控技术，可以组成3种形式的ARQ协议。即停等（Stop-and-Wait）ARQ、后退N帧（Go-Back-N）ARQ以及选择性重传（Selective Request）ARQ。前一种是停等流控技术和自动请求重传技术的结合。后两种协议是滑动窗口技术与自动请求重传技术的结合，由于窗口尺寸开到足够大，帧在线路上可以连续流动，因此又称为连续ARQ协议。

1.停等ARQ协议

根据停等ARQ协议，发送站发出一帧后必须等待应答信号，收到肯定应答信号ACK后继续发送下一帧；收到否定应答信号NAK后重发该帧；若在一定的时间间隔内没有收到应答信号也必须重发。没有收到应答信号的原因可能是帧丢失了，也可能是应答信号丢失了。无论哪一种原因，发送站都必须重新发送原来的帧。发送站必须有一个重发计时器，每发送一帧就开始计时，且计时长度不能小于信号在线路上一个来回的时间。下图表示出了各种可能的传送情况。

2.后退 N 帧ARQ协议

后退N帧ARQ协议就是从出错处重发已发送过的N个帧。如下图，后退 N 帧在接收端的接收窗口大小为 1，因而接收方必须按顺序接收，当第2帧出错时，2、3、4、5号帧都必须重发。其中，若采用k比特对帧编号，则应该满足发送窗口大小W≤ 2 ^k−1 。之所以这样做，是因为如果大于，那么无法区分新帧和旧帧。比如帧编号字段为2位，那么最大帧序号是 3 ，如果发送窗口为 6，那么会出现的发送帧序号是 0，1，2，3，0，1，那在返回帧1 的确认帧时，则会无法分辨确认的是哪个帧1了。

3.选择重传协议ARQ协议

在后退N帧ARQ协议中，接收方若发现错误帧就不再接收后续的帧，即使是正确到达的帧，这显然是一种浪费。由此诞生了选择重传协议ARQ协议，其工作原理是当接收方发现某帧出错后，其后继续送来的正确的帧存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以将已存于缓冲区中的其余帧一并按正确的顺序递交上一层网络层。

对于选择重传协议ARQ，窗口的大小也有一定的限制，窗口的最大值应为帧编号数的一半，即W发=W收≤2^(k-1)

我们来看这样一种情况，假设帧编号为3位。发送和接收窗口大小都是7。

1. 发送窗口和接收窗口中的帧编号都是0~6。

2. 发送站发出0~6号帧，但尚未得到肯定应答，窗口不能向前滑动。

3. 接收站正确地接收了0~6号帧，发出确认信号ACK7，接收窗口向前滑动，新窗口地帧编号为7、0、1、2、3、4、5。

4. 假设接收站发送给发送站确认信号ACK7丢失，那么发送站定时器超时后，需要重发0号帧。

5. 接收站接收到0号帧，看到帧编号落在接收窗口内，以为是新的0号帧而保存起来，这样协议就出错了。

所以避免这种错误的办法就是缩小窗口，使得接收窗口向前滑动最大距离后不再与旧的接收窗口重叠。显然，当窗口大小为帧编号数的一半时就可以达到这个效果。