流量控制与可靠传输

本文在数据链路层下进行讨论。对于链路层传输的数据被称为帧。

流量控制

由于收发双方各自的工作速率和缓存空间的差异，可能出现发送方的发送能力大于接收方的接受能力的现象，如果此时不对发送方的发送速率进行限制，那么接收方可能会被后面不断发送来的数据“淹没”，造成帧的丢失而出错。流量控制实际上就是限制发送方的数据流量，使其发送速率不超过接收方的接收能力。

可靠传输机制

数据链路层的可靠传输机制通常使用确认和超时重传两种机制完成。确认是一种无数据的控制帧，这种控制帧使得接收方可以让发送方知道哪些内容被正确接收（有些情况下为了提高传输效率，将确认捎带在一个回复帧中，称为捎带确认）。
超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一定时间内如果没有得到发送的数据帧的确认帧，就重新发送该数据帧，直到发送成功为止。

自动重传请求（Auto Repeat reQuest，ARQ）通过接收方请求发送方重传出错的数据帧来恢复出错的帧。传统自动重传请求分为三种，停止-等待（Stop-and-wait）ARQ、后退N帧（Go-Back-N）ARQ和选择性重传（Selective Repeat）ARQ。后两种协议是滑动窗口技术与请求重发技术的结合，由于窗口尺寸开到足够大时，帧在线路上可以连续地流动，因此也称其为连续ARQ协议。在数据链路层中流量控制机制和可靠传输机制时交织在一起的。

滑动窗口流量控制基本原理

在任意时刻，发送方都维持一组连续的允许发送的帧的序号，称为发送窗口；同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。发送窗口用来对发送方进行流量控制，而发送窗口的大小 W_T 代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。
同理，在接收方设置接收窗口是为了控制可以接收哪些数据帧和不可以接收哪些帧。在接收方，只有收到的数据帧的序号落入按收窗口内时，才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丟弃。

发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口内没有可以发送的帧（即窗口内的帧全部是己发送但未收到确认的帧）时，发送方就会停止发送，直到收到接收方发送的确认帧使窗口移动，窗口内有可以发送的帧后，才开始继续发送。
接收方收到数据帧后，将窗口向前移一个位置，并发回确认帧，若收到的数据帧落在接收窗口之外，则一律丢弃。

滑动窗口重要特征

1. 只有接收窗口向前滑动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动。
2. 从滑动窗口的概念看，停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所差別：
   • 停止-等待协议：发送窗口大小 = 1，接收窗口大小 = 1。
   • 后退N帧协议：发送窗口大小 > 1，接收窗口大小 = 1。
   • 选择重传协议：发送窗口大小 > 1，接收窗口大小 = 1。
3. 接收窗口的大小为 1 时，可保证帧的有序接收。
4. 数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的。

三种可靠传输协议

停止-等待协议

在停止-等待协议中，发送方发送单个帧后必须等待接收方的确认字符（Acknowledge character，ACK），在发送方收到确认之前不能发送其他的数据帧。从滑动窗口机制的角度来看，停止-等待协议相当于发送窗口和接收窗口的大小都是1的滑动窗口协议。

在停止-等待协议中，除数据帧丢失外，还可能出现以下两种差错。
到达接收方的帧可能已遭到破坏，接收方利用差错检测技术检出过，简单地将该帧丢弃。为了对付这种可能发生的情况，发送方装备了计时器。在一个帧发送之后，发送方等待确认，如果在计时器记满时仍未收到确认，那么就再次发送相同的帧。如此重复，直到该数据帧无错误的到达为止。

另一种可能的差错是数据帧正确而确认帧被破坏，此时接收方已收到正确的数据帧，但发送方收不到确认帧，因此发送方会重传已被接收的数据帧，接收方收到同样的数据帧时会丢弃该帧，并重传一个该帧对应的确认帧。
发送的帧交替的用 0 和 1 来标识，肯定确认分别用 ACK0 和 ACK1 来表示，收到的确认有误时，重传已发送的帧。对于停止-等待协议，由于每发送一个数据帧就停止并等待，因此用 1bit 来编号就已足够。在停止-等待协议中，若连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧时，表明接收方收到了重复帧。
此外，为了超时重发和判定重复帧的需要，发送方和接收方都须设置一个帧缓冲区。发送端在发送完数据帧时，必须在其发送缓存中保留此数据帧的副本，这样才能在出差错时进行重传。只有在收到对方发来的确认帧 ACK 时，方可清除此副本。

停止-等待协议通信信道的利用率很低。为了克服这一缺点，就产生了另外两种协议，后退N帧协议和选择重传协议。

信道的效率，也称信道利用率。可从不同的角度来定义信道的效率，这里给出一种从时间角度的定义：信道效率是对发送方而言的，是指发送方在一个发送周期的时间内，有效地发送数据所需要的时间占整个发送周期的比率。
例如，发送方从开始发送数据到收到第一个确认帧为止，称为一个发送周期，设为 T，发送方在这个周期内共发送 L 比特的数据，发送方的数据传输速率为 C，则发送方用于发送有效数据的时间为 L/C，在这种情况下，信道的利用率为 (L/C)/T。
信道吞吐率 = 信道利用率 × 发送方的发送速率。

后退N帧协议

在后退 N 帧式 ARQ 中，发送方无须在收到上一个帧的 ACK 后才能开始发送下一帧，布是可以连续发送帧。当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了 N 个帧后，若发现该 N 个帧的前一个帧在计时器超时后仍末返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重传该出错帧及随后的 N 个帧。换句话说，接收方只允许按顺序接收帧。
如图所示，发送方向目的站发送数据帧。当发送方发完 0 号帧后，可以继续发送后续的 1 号帧、2 号帧等。发送方每发送完一帧就要为该帧设置超时计时器。由于连续发送了许多帧，所以确认帧必须要指明是对哪一帧进行确认。为了减少开销，GBN 协议还规定接收方不一定每收到 1 个正确的数据帧就必须立即发回一个确认帧，而可以在连续收到好几个正确的数据帧后，才对最后一个数据帧发确认信息，或者可在自己有数据要发送时才将对以前正确收到的帧加以捎带确认。这就是说，对某一数据帧的确认就表明该数据帧和此前所有的数据帧均已正确无误地收到。
在图中，ACKn 表示对第 n 号帧的确认，表示接收方已正确收到第 1 号帧及以前的所有帧，下一次期望收到第 n＋1 号帧（也可能是第 0 号帧）。接收方只按序接收数据帧。虽然在有差错的 2 号帧之后按着又收到了正确的 6 个数据帧，但按收端都必须将这些帧丢弃。接收方虽然丢弃了这些不按序的无差错帧，但应重复发送已发送的最后一个确认帧 ACK1（这是为了防止已发送的确认帧 ACK1 丢失）。
后退 N 帧协议的接收窗口为 1，可以保证按序接收数据帧。若采用 n 比特对帧编号，则其发送窗口的 W_T 下应满足 1 ≤ W_T ≤ 2ⁿ-1。若发送窗口的尺寸大于 2ⁿ-1，则会造成按收方无法分辦新帧和旧帧。
从图中不难看出，后退 N 帧协议一方面因连续发送数据帧而提高了信道的利用率，另一方面在重传时又必须把原来已传送正确的数据帧进行重传（仅因这些数据帧的前面有一个数据帧出了错），这种做法又使传送效率降低。由此可见，若信道的传输质量很差导致误码率较大时，后退帧协议不一定优于停止-等待协议。

选择重传协议

为进一步提高信道的利用率，可设法只重传出现差错的数据帧或计时器超时的数据帧，但此时必须加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。这就是选择重传 ARQ 协议。
在选择重传协议中，每个发送缓冲区对应一个计时器，当计时器超时时，缓冲区的帧就会重传。另外，该协议使用了比上述其他协议更有效的差错处理策略，即一旦接收方怀疑帧出错，就会发一个否定帧 NAK 给发送方，要求发送方对 NAK 中指定的帧进行重传。
选择重传协议的接收窗口尺寸 W_R 和发送窗口尺寸 W_T 都大于 1，一次可以发送或接收多个帧。若采用 n 比特对帧编号，为了保证接收方向前移动窗口后，新窗口序号与旧窗口序号没有重叠部分，需要满足条件：接收窗口 W_R + 发送窗口 W_T ≤ 2ⁿ。假定仍然采用累计确认的方法，并且接收窗口 W_R 显然不应超过发送窗口 W_T（否则无意义），那么接收窗口尺寸不应超过序号范围的一半，即 W_R ≤ 2^n-1。接收窗口为最大值时，W_Tmax = W_Rmax = 2^n-1。

选择重传协议可以避免重复传送那些本已正确到达接收方的数据帧，但在按收端要设置具有相当容量的缓冲区来缓存那些未按序正确收到的帧。接收方不能接收窗口下界以下或窗口上界以上的序号的帧，因此所需缓冲区的数目等于窗口的大小，而不是序号数目。