下载掌阅APP，畅读海量书库
立即打开
由于物理线路（信道）的不可靠，发送端发送的数据在经过物理线路传输过程中有可能出错。接收端可以通过CRC码（或其他检错码）检测收到的数据是否有错。如果接收端检测到数据有错，则接收端会丢弃数据。
虽然可以通过引入纠错码来纠正数据在经过物理线路传输时出现的差错，但是采用纠错码开销太大，因此必须采用某些机制，以实现在不可靠物理线路上的可靠数据传输。需要强调的是，可靠数据传输的含义包括：数据不出错，不丢失，不乱序，不重复。
一般情况下，可靠数据传输是通过确认和重传机制来实现的。所谓确认机制，是指接收端每收到一个正确的数据，必须返回一个ACK给发送端。如果发送端在发送完数据的一段时间后还没有收到接收端返回的ACK，发送端就会超时并重传该数据。通过确认和重传机制，可以实现在不可靠的物理线路上进行可靠数据传输。
接收端对发送端的确认可以通过两种方式实现。一种方式是接收端每收到一个正确数据，就给发送端返回一个ACK，我们称这种方式为专门确认；但是更多的情况下，接收端也有反向数据要发送给发送端，这时ACK就可以顺便搭载在反向数据中，我们称这种方式为捎带（piggybacking）确认。
最简单的可靠传输协议就是停-等（stop-and-wait）协议。停-等协议的思想非常简单：发送端发送一个数据帧后就停止下来，等待接收端返回确认帧ACK；如果经过一段时间后，发送端还没有收到确认帧（定时器超时），就重传该数据帧。
图3-6给出了停-等协议的4种不同的情况。在图3-6中，左侧表示发送端，右侧表示接收端。另外，图3-6中使用时间轴，这是描述协议行为的一种常用方法。
图3-6a表示发送端在定时器超时前收到确认帧的情况，在这种情况下，发送端发送一个新帧。图3-6b表示数据帧丢失的情况，在这种情况下，由于接收端不会返回发送端ACK帧，发送端只有等到定时器超时，然后重传前面的帧。图3-6c表示确认帧丢失的情况，在这种情况下，发送端仍然会超时，并重传前面的帧。图3-6d表示发送端定时器设置过短，从而引起超时过快，导致不必要的重传。
在停-等协议中，还有一个重要的细节。假设发送端发送了一个数据帧，接收端正确接收该帧，并且返回发送端ACK帧。这时，有可能出现两种情况：一是该确认帧丢失，如图3-6c所示的情况；二是该确认帧迟到了，如图3-6d所示的情况。在这两种情况下，发送端都会超时并且重发前面的帧。但是，如果接收端把重发的帧当作新帧接收下来并且交给高层，则会导致重复帧的问题。为了解决这个问题，在停-等协议中必须分别对数据帧和确认帧进行编号。由于在停-等协议中接收端只需要能够区分出接收到的帧是新帧还是重复帧，因此采用1比特对数据帧和确认帧进行编号即可。这样，当发送端重发一个数据帧时，接收端可以通过数据帧中的编号来确定它是新帧还是重复帧。如果接收端接收到的是重复帧，接收端不再将该帧交给上层协议，但是仍然返回一个带序号的确认帧给发送端。
图3-6 停-等协议的4种不同情况
停-等协议的主要缺点是：在某些情况下，协议效率非常低，从而造成物理线路的利用率非常低。例如，考虑一条数据传输率为2Mbit/s的卫星链路（卫星为同步轨道卫星）。从发送端地面站发送一帧到接收端地面站，然后接收端返回ACK到发送端的往返时间（Round Trip Time，RTT）为500ms。由于采用停-等协议，因此发送端在每个RTT时间内只能发送1帧，假设数据帧的大小为8000比特，发送端每发送1帧的发送时间（transmission time）为8000b/2Mbit/s，等于4ms。由此可得卫星链路的最大利用率为4ms/(500ms+4ms)，约等于0.8%。也就是说，由于采用停-等协议，卫星链路的实际利用率只有0.8%。
为了充分利用卫星链路，发送端可以在等待接收端返回的第1个ACK之前最多连续发送 N 个帧，这就要采用下面将要介绍的滑动窗口协议。
所谓滑动窗口协议，是指发送端一次连续发送多个帧，在这个过程中协议的发送端和接收端就需要引入滑动窗口（slide window）机制。在滑动窗口协议中，发送端维持一个发送窗口（sending window），发送窗口随着发送端不断地发送数据帧和接收ACK帧而变动；同样地，接收端维持一个接收窗口（receiving window），接收窗口也随着接收端接收数据帧的情况而变动。下面介绍后退 N 帧协议和选择重传协议两种滑动窗口机制。
在后退 N 帧（Go-Back-N, GBN）协议中，发送端可以连续发送多个帧之后等待ACK。
图3-7给出了后退 N 帧协议中发送端序号的范围。我们将未确认帧中的最小序号记为基序号（base），将最小未使用序号（即下一个待发送帧的序号）记为下一个序号（nextseqnum），则可以将发送端将序号范围分为4部分。序号落在[0，base-1]范围的帧对应于已经发送并且收到应答的帧，序号落在[base，nextseqnum-1]范围内的帧对应已经发送出去但尚未收到应答的帧（也称为outstanding帧），序号落在[nextseqnum，base+ N -1]范围内的帧是指可以立即发送的帧。另外，序号大于或等于base+ N 的帧不存在，必须等到发送窗口向前移动（序号为base的帧收到应答后，发送窗口就会朝前移动）。
图3-7 在后退 N 帧协议中发送端序号的范围
如图3-7所示，可以将那些已经发送但还未收到应答的帧加上可用帧的序号范围看作一个大小为 N 的窗口。随着后退 N 帧协议的运行，发送窗口在序号空间内向前滑动。
在数据链路层协议中，数据帧和确认帧 序号 往往是帧头的一个字段。假设序号字段的长度是 k 比特，则帧的序号空间是[0，2 k -1]。在一个有限的序号空间中，所有涉及 序号 的运算必须使用模2 k 运算，即序号空间被认为是一个大小为2 k 的环，序号2 k -1的后面紧接着是0。
在后退 N 帧协议中，接收端的动作非常简单，如果一个序号为 n 的帧被接收端正确接收，并且是接收端期望的，接收端将帧交给上层则并且返回ACK n 。如果接收端接收到一个不是接收端期望接收的无错帧，接收端仍然返回ACK给发送端，但是接收端不会将该帧交给上层。
在后退 N 帧协议中，接收端只需要1个缓存区，并且接收端只能顺序接收帧，并丢弃所有乱序到达的帧。假设现在接收端期望接收帧 n 而实际上接收到帧 n +1，则根据后退 N 帧协议，接收端将丢弃帧 n +1。发送端必须维持发送窗口的上下边界及nextseqnum在该窗口中的位置，而接收端只需要维护期望接收帧的序号（expectedseqnum）这个变量。
图3-8给出了一个发送窗口为4的后退 N 帧协议的例子。发送端连续发送0～3号数据帧，停止发送，然后等待确认帧。发送端收到ACK（如ACK 0 ），则发送窗口便向前滑动，此时发送端可以发送帧4；发送端收到ACK 1 ，则发送端继续向前滑动窗口，可以发送帧5。如果接收端没有正确接收到帧2（或者由于帧2出错，或者由于帧2丢失），尽管帧3、帧4和帧5都正确到达接收端，但由于帧3、帧4和帧5都不是接收端期望接收的帧（因为现在接收端期望接收的是帧2），于是接收端丢弃帧3、帧4和帧5。
图3-8 后退 N 帧协议示例
对于后退 N 帧协议来说，可以采用累计应答（cumulative acknowledgement）。所谓累计应答，是指当接收端连续接收到正确的数据帧后，如数据帧 n -2、 n -1、 n ，则接收端依次返回ACK n -2 、ACK n -1 、ACK n ，假如ACK n -2 和ACK n -1 在返回发送端途中出错或者丢失，即发送端没有正确接收到ACK n -2 和ACK n -1 ，但是只要发送端正确接收到ACK n ，那么发送端也知道所有序号小于等于 n 的数据帧都已经被接收端正确接收到。
下面我们来考察一个非常有意思的问题。对于后退 N 帧协议，假定序号是3比特，这样帧的 序号 就分别为0, 1, 2, …, 7，即帧的序号范围是[0，2 3 -1]。那么对于后退 N 帧协议，发送窗口的最大尺寸是7（2 3 -1）而不是8（2 3 ），这意味着发送端能够一次发送未应答的帧的最大数目是7。
为了说明这个问题，考察下面的情形。假设在上述情况下，发送端连续发送8个帧，分别是帧0～7，并且假设这8个帧全部正确无误地到达接收端。按照后退 N 帧协议的规则，接收端将依次返回ACK 0 ～ACK 7 给发送端。现在假设只有ACK 0 ～ACK 7 正确返回发送端，于是发送端将发送8个新帧，帧的编号仍然为0～7。假设经过一段时间后，发送端只接收到ACK 7 （假设ACK 0 ～ACK 6 都出错或丢失）。现在的问题是，发送端如何根据第2次收到的ACK 7 判断出第2次发送的8个帧是全部正确到达接收端还是全部丢失了呢？因为在这两种情况下，接收端都会返回确认帧ACK 7 （读者可以想一想这是为什么），从而造成后退 N 帧协议失败。如果后退 N 帧协议的发送窗口的最大尺寸限制在7（2 3 -1）之内，即发送端一次连续发送的帧数量小于等于7（2 3 -1），则就能保证后退 N 帧协议在任何情况下都不会出现差错。
与停-等协议相比，后退 N 帧协议提高了信道的利用率，但后退 N 帧协议必须重传出错帧以后的所有帧，从而造成信道带宽的浪费。因此，有必要对后退 N 帧协议进行一些改进，以提高信道的利用率，这就是下面要阐述的选择重传（Selective Repeat，SR）协议。
选择重传协议通过让发送端仅仅重传那些接收端没有正确接收到的帧（这些帧出错或丢失），从而避免发送端一些不必要的重传，以便提高信道利用率。为此，选择重传协议要求接收端必须对正确接收的帧进行逐个应答，而不能采用后退 N 帧协议中所采用的累计应答。
选择重传协议仍然用窗口尺寸 N 来限制流水线中已发送但未收到确认的帧、已发送且已收到确认的帧以及正要发送的帧的数目。图3-9显示了选择重传协议中发送端和接收端的序号空间。
图3-9 选择重传协议中发送端和接收端的序号空间
对于选择重传协议，当发送端收到某个ACK时，发送端将该ACK中序号所对应的帧标记为已接收。如果此帧的序号等于发送基序号（sendbase），则发送窗口的基序号指针向前移动到指向具有最小序号的未确认帧处。如果发送窗口基序号指针移动后还有序号落到发送窗口内的未发送帧，则发送这些帧。
对于接收端，如果接收到的帧的序号在[rcvbase，rcvbase+ N -1]内，即落入接收窗口，则接收端接收该帧，同时返回一个ACK帧给发送端以确认该帧。如果该帧的序号等于接收窗口的基序号（图3-9中的rcvbase），则该帧和接收端缓存帧（这些缓存的帧的序号必须和接收帧的序号连续）一起交付给上层，然后接收窗口序号指针根据交付的帧的数量向前移动。考虑图3-10的例子，当接收端收到一个序号为2（假设刚好接收窗口的rcvbase也为2）的帧时，首先接收端返回ACK 2 ，其次接收端将帧2与帧3、帧4、帧5（帧3、帧4、帧5已经在接收端的缓存中）一起交付给上层，最后接收端将接收窗口指针移到指向6、7、0和1。
如果接收到的帧的序号 n 在[rcvbase -N , rcvbase-1]内（即接收窗口之外），也返回该编号的ACK n 。也就是说，对于选择重传协议接收端，只要它正确接收一个帧，不管是否落入接收窗口，接收端都返回该帧的ACK。对于图3-10给出的选择重传协议发送端和接收端序号空间，如果发送端没有收到带发送基序号的ACK帧（图3-10中，sendbase小于rcvbase），则发送端最终将重传序号为sendbase的帧，即便接收端已经正确接收该帧。发送端只有收到序号为发送基序号的ACK帧时，发送窗口才会向前移动。这说明对于选择重传协议来说，哪些帧已经被接收且正确，哪些帧还没有接收，发送端和接收端看到的情形是不一样的，这意味着对于选择重传协议，发送窗口和接收窗口并不总是一样。图3-10给出了选择重传协议发送窗口和接收窗口的一个例子。
图3-10 选择重传协议示例
对于选择重传协议，同样假设帧序号字段长度为3比特，如果按照后退 N 帧协议的方式设定发送窗口的最大尺寸为7，那么接收窗口的最大尺寸也为7。发送端和接收端的窗口初始状态如图3-11a所示。现在假设发送端连续发送序号为0～6的7个帧并全部正确到达接收端，由于接收端的接收窗口正好为0～6，因此接收端将全部接收这7帧，同时发送ACK 0 ～ACK 6 确认帧给发送端。然后接收端将接收窗口旋转到7～5，意味着接收端准备接收编号为7、0、1、2、3、4、5的帧，如图3-11b所示。
图3-11 选择重传协议发送窗口和接收窗口为7的情形
假设接收端返回的ACK 0 ～ACK 6 全部丢失，发送端最终会因超时而重发前面的0～6号帧。当帧0～6到达接收端时，接收端查看这些帧是否落入接收窗口，很不幸，序号为0、1、2、3、4、5的帧正好落入接收窗口，因此接收端将帧0～5接收下来（此时协议已经出错）。而且由于接收端到目前为止一直没有收到帧7，因此接收端返回的确认帧一直为ACK 6 ，表明接收端希望发送端发送帧7。
当发送端接收到ACK 6 后，发送端立即将发送窗口前移为7～5，并依次发送编号为7、0、1、2、3、4、5的帧。
假设发送端发送的帧7～5都正确到达接收端。接收端首先接收帧7，然后扫描接收缓存区，发现帧0、1、2、3、4、5已经在接收缓存区中，接收端于是将帧7、0、1、2、3、4、5组装好交给上层（其中的0、1、2、3、4、5为重复帧），协议失败。
协议失败的关键原因是接收端在移动窗口前后得到的新旧窗口有重叠，导致接收端在接收帧时，不能区分这一帧是重复帧，还是新帧。
解决这一问题的方法是保证接收端在移动窗口后，新旧窗口之间没有任何重叠。为此，在选择重传协议中，发送窗口和接收窗口的最大尺寸 N 只能为2 k -1（其中 k 为序号的比特长度）。对于序号为3位的情形，发送窗口和接收窗口的最大尺寸为4。对于发送端而言，这也就意味着最多只允许有4个未应答的帧等待应答，如图3-12所示。而对于接收端，则意味着一次可以接收帧的个数不能超过4个。这样一来，如果接收端刚刚接收了帧0～3，并移动接收窗口，下次允许接收的帧只能是帧4～7。这样接收端就可以分辨出到来的帧是重复帧（序号为0～3）还是新帧（序号4～7）。
图3-12 发送和接收窗口为4的情况
一个有趣的问题是，接收端必须设置多少个缓存区呢？从上面的分析可以知道，接收端所需的缓存区数量等于接收窗口的最大尺寸。对于3比特序号的选择重传协议，接收端只需要4个缓存区即可。
同样的道理，对于发送端来说，发送窗口的最大尺寸相当于发送端可以一次连续发送的帧的个数。因此，发送端所需的发送缓存区个数与接收端的缓存区个数是相等的，因而发送端所需要的定时器个数等于发送窗口的大小。一个定时器对应一个缓存区，当定时器超时，发送端重传缓存区里的帧。
选择重传协议还使用了比后退 N 帧协议更有效的策略来处理帧出错的情形。在选择重传协议中，一旦接收端接收到一个错误帧，就会返回一个 否定确认帧 （ Negative AcKnowledge，NAK ）给发送端，发送端马上重传指定的帧而不需要等待超时，这样可以加快发送端的重传速度，从而提高信道利用率。