5.3.1可靠传输——第4版的第3章
第3章数据链路层
数据链路层的许多概念都是计算机网络的重要概念。本章在介绍数据链路层的基本概念后，就详细地讨论两个重要的协议：停止等待协议和连续ARQ协议，包括滑动窗口的概念。接着阐明面向比特的链路控制规程HDLC的要点。最后介绍因特网
3.1数据链路层的基本概念
我们已多次使用过“链路”和“数据链路”这两个术语。这里要强调一下，“链路”和“数据链路”并不是一回事。所谓链路(link)就是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。在进行数据通信时，两个计算机之间的通路往往是由许多的链路串接而成的。可见一条链路只是一条通路的一个组成部分。数据链路(datalink)则是另一个概念。这是因为当需要在一条线路上传送数据时，除了必须有一条物理线路外，还必须有一些必要的通信协议来控制这些数据的传输（这将在后面几节讨论）。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（在许多情况下适配器就是网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。
在讨论数据链路层的功能时，常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。虽然我们知道在物理层之间传送的是比特流，而在物理传输媒体上传送的是信号（电信号或光信号），但有时为了方便我们也常说，“在某条链路（而没有说数据链路）上传送数据帧”。其实这已经隐含地假定了我们是在数据链路层上来观察问题。如果没有数据链路层的协议，我们在物理层上就只能看见链路上传送的比特串，根本不能找出一个帧的起止比特，当然更无法识别帧的结构。有时我们也会不太严格地说，“在某条链路上传送分组或比特流”，但这显然是在网络层或物理层上讨论问题。
也有人采用另外的术语。这就是将链路分为物理链路和逻辑链路。物理链路就是上面所说的链路，而逻辑链路就是上面的数据链路，是物理链路加上必要的通信协议。这两种划分方法实质上是一样的。
早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。
数据链路层的主要功能如下（有些协议可以省略其中的一些）：
(1)链路管理当网络中的两个结点要进行通信时，数据的发方必须确知收方是否已经处在准备接收的状态。为此，通信的双方必须先要交换一些必要的信息。或者用我们的术语，必须先建立一条数据链路。同样地，在传输数据时要维持数据链路，而在通信完毕时要释放数据链路。数据链路的建立、维持和释放就叫做链路管理。
(2)帧定界在数据链路层，数据的传送单位是帧。数据一帧一帧地传送，就可以在出现差错时，将有差错的帧再重传一次，而避免了将全部数据都进行重传。帧定界是指收方应当能从收到的比特流中准确地区分出一帧的开始和结束在什么地方。帧定界也可称为帧同步。
(3)流量控制发方发送数据的速率必须使收方来得及接收。当收方来不及接收时，就必须及时控制发方发送数据的速率。这种功能称作流量控制(flowcontrol)。
(4)差错控制在计算机通信中，一般都要求有极低的比特差错率。为此，广泛地采用了编码技术。编码技术有两大类。一类是前向纠错，即收方收到有差错的数据帧时，能够自动将差错改正过来。这种方法的开销较大，不大适合于计算机通信。另一类是差错检测，即收方可以检测出收到的帧有差错(但并不知道是哪几个比特错了)。当检测出有差错的帧时就立即将它丢弃，但接下去有两种选择：一种方法不进行任何处理（要处理也是由高层进行），另一种方法则是由数据链路层负责重传丢弃的帧。这两种方法都是很常用的。
(5)将数据和控制信息区分开在许多情况下，数据和控制信息处于同一帧中。因此一定要有相应的措施使收方能够将它们区分开来。
(6)透明传输所谓透明传输就是不管所传数据是什么样的比特组合，都应当能够在链路上传送。当所传数据中的比特组合恰巧出现了与某一个控制信息完全一样时，必须有可靠的措施，使收方不会将这种比特组合的数据误认为是某种控制信息。只要能做到这点，数据链路层的传输就被称为是透明的。
(7)寻址必须保证每一帧都能送到正确的目的站。收方也应知道发方是哪个站。
当OSI确定了应当有一个数据链路层后，又出现了许多种采用不同媒体接入控制的局域网。这些局域网无法使用一种统一的数据链路层协议。于是局域网的数据链路层就分解为两个子层。本章实际上是讨论最基本的数据链路层协议，其基本概念对学习全课程都很重要。至于更为复杂的局域网的数据链路层协议将在第4章进行讨论。下面先讨论最简单的停止等待协议。
3.2停止等待协议
停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。很多有关协议的基本概念都可以从这个协议中学习到。我们先从最简单的情况讲起。
3.2.1完全理想化的数据传输
当两个主机进行通信时，应用进程要将数据从应用层逐层往下传，经物理层到达通信线路。通信线路将数据传到远端主机的物理层后，再逐层向上传，最后由应用层交给远程的应用进程。但现在为了把主要精力放在数据链路层的协议上，可以采用一个简化的模型(图3-1)，即把数据链路层以上的各层用一个主机来代替，而物理层和通信线路则等效成一条简单的数据链路。
在发方和收方的数据链路层分别有一个发送缓存和接收缓存。若进行全双工通信，则在每一方都要同时设有发送缓存和接收缓存。缓存就是一个存储空间，它是必不可少的。这是因为在通信线路上数据是以比特流的形式串行传输的，但在计算机内部数据的传输则是以字节(或若干个字节)为单位并行传输的。计算机在发送数据时，先以并行方式将数据写入发送缓存，然后以串行方式从发送缓存中按顺序读出比特，发送到通信线路上。在接收数据时，计算机先从通信线路上将串行传输的比特流按顺序存入接收缓存，然后再以并行方式按字节（或若干个字节）将数据从接收缓存读出。
图3-1所示的简化模型对于一个计算机网络中任意一条数据链路上的数据传输情况都是适用的。在网络内部，各交换结点的数据链路层的上面只有一个网络层。对于这种交换结点，网络层就相当于简化模型中的主机。
为了深入理解数据链路层的协议，我们先从一种假想的、完全理想化的数据传输过程开始讨论。为了和后面的讨论相衔接，我们假定数据传输是以帧为单位。
所谓完全理想化的数据传输就是基于以下两个假定：
假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。
假定2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。
图3-1两台计算机通过一条数据链路进行通信的简化模型
第一个假定很容易理解。对第二个假定则需加以解释。
我们假设主机A连续不断地向主机B发送数据。在收方，主机B的数据链路层也就将收到的数据逐帧交给主机B。在理想情况下，收方数据链路层的缓存每存满一帧就向主机B交付一帧。如果没有专门的流量控制协议，则收方并没有办法控制发方的发送速率，而收方也很难做到：向主机交付数据的速率永远不会低于发方发送数据的速率。若收方数据链路层向主机交付数据的速率略低于发方发送数据的速率，则收方的缓存中暂时存放的数据帧就会逐渐堆积起来，最后造成缓存溢出和数据帧丢失。因此，上述第二个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。
在这样理想化的条件下，数据的传输就非常简单（不需要有流量控制，也不需要有差错控制）。但下面我们要逐步去掉这些完全理想化的假定。
3.2.2具有最简单流量控制的数据链路层协议
现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机A向主机B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。
为了使收方的接收缓存在任何情况下都不会溢出，在最简单的情况下，就是发方每发送一帧就暂时停下来，等待收方的确接收完毕后再发送下一帧。收方收到数据帧后就交付给主机，然后发一信息给发方，表示接收的任务已经完成。这时，发方才再发送下一个数据帧。在这种情况下，收方的接收缓存的大小只要能够装得下一个数据帧即可。显然，用这样的方法收发双方能够同步得很好，发方发送的数据流受收方的控制。这里应强调一下，由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。
现将以上具有最简单流量控制的数据链路层协议写成算法如下：
假定：链路是理想的传输信道，即所传送的任何数据既不会出差错也不会丢失。
在发送结点：
(1)从主机取一个数据帧。
(2)将数据帧送到数据链路层的发送缓存。
(3)将发送缓存中的数据帧发送出去。
(4)等待。
(5)若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。
在接收结点：
(1)等待。
(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。
(3)将接收缓存中的数据帧上交主机。
(4)向发送结点发一信息，表示数据帧已经上交给主机。
(5)转到(1)。
图3-2是前面所述的两种情况的对比。图3-2(a)是不需要任何协议的理想化情况。主机A将数据帧(图中用DATA表示)连续发出，而不管发送速率有多快，收方总能够跟得上，收到一帧即交付给主机B。显然，这种完全理想化情况的传输效率是很高的。
图3-2(b)是由收方控制发方发送速率的情况。发方每发完一帧就必须停下来，等待收方的信息。这里要指出，由于假定了数据在传输过程中不会出差错，因此收方将数据帧交给主机B后向发方主机A发送的信息，不需要有任何具体的内容，即不需要说明所收到的数据是否是正确无误的。这相当于只要发回一个不需要装入任何信件的空信封就能起到流量控制的作用。
图3-2不需要任何数据链路层协议的数据传输(a)和具有最简单的流量控制的数据链路层协议(b)
3.2.3实用的停止等待协议
现在去掉前面的两个假定，讨论实用的数据链路层协议。这就是说，传输数据的信道不能保证使所传的数据不产生差错，并且还需要对数据的发送端进行流量控制。
图3-3(a)画的是数据在传输过程中不出差错的情况。收方在收到一个正确的数据帧后，即交付给主机B，同时向主机A发送一个确认帧ACK(ACKnowledgement)。当主机A收到确认帧ACK后才能发送一个新的数据帧。这样就实现了收方对发方的流量控制。
现在假定数据帧在传输过程中出现了差错。由于通常都在数据帧中加上了循环冗余检验CRC(CyclicRedundancyCheck)，所以结点B很容易用硬件检验出收到的数据帧是否有差错(使用循环冗余检验进行差错检测的原理在后面的3.2.4小节讨论)。当发现差错时，结点B就向主机A发送一个否认帧NAK(NegativeAcKnowlegement)，以表示主机A应当重传出现差错的那个数据帧。图3-3(b)画出了主机A重传数据帧。如多次出现差错，就要多次重传数据帧，直到收到结点B发来的确认帧ACK为止。为此，在发送端必须暂时保存已发送过的数据帧的副本。当通信线路质量太差时，则主机A在重传一定的次数后(如8次或16次，这要事先设定好)，即不再进行重传，而是将此情况向上一层报告。
有时链路上的干扰很严重，或由于其他一些原因，结点B收不到结点A发来的数据帧。这种情况称为帧丢失(图3-3(c))。发生帧丢失时结点B当然不会向结点A发送任何确认帧。如果结点A要等收到结点B的确认信息后再发送下一个数据帧，那么就将永远等待下去。于是就出现了死锁现象。同理，若结点B发过来的确认帧丢失，也会同样出现这种死锁现象。
要解决死锁问题，可在结点A发送完一个数据帧时，就启动一个超时计时器(timeouttimer)。计时器又称为定时器[MINGCI94]。若到了超时计时器所设置的重传时间tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧(见图3-3(c),(d))。如果在重传时间tout内收到确认，则将超时计时器清零并停止计时。显然，超时计时器设置的重传时间应仔细选择确定。若重传时间选得太短，则在正常情况下也会在对方的确认信息回到发送方之前就过早地重传数据。若重传时间选得太长，则往往要白白等掉许多时间。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。
图3-3数据帧在链路上传输的几种情况
然而现在问题并没有完全解决。当出现数据帧丢失时，超时重传的确是一个好办法。但是若丢失的是确认帧，则超时重传将使主机B收到两个同样的数据帧。由于主机B现在无法识别重复的数据帧，因而在主机B收到的数据中出现了另一种差错——重复帧。重复帧也是一种不允许出现的差错。
要解决重复帧的问题，必须使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。这时应当丢弃这重复帧，因为已经收到过同样的数据帧并且也交给了主机B。但应注意，此时结点B还必须向结点A发送一个确认帧ACK，因为结点B已经知道结点A还没有收到上一次发过去的确认帧ACK。
我们知道，任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。例如，当发送序号占用3bit时，就可组成8种不同的发送序号，从000到111。当数据帧的发送序号为111时，下一个发送序号就又是000。因此，要进行编号就要考虑序号到底要占用多少个比特。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可以有0和1两种不同的序号。这样，数据帧中的发送序号(以后记为N(S)，S表示发送)就以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。
从以上的讨论可以看出，虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就提供了可靠传输的服务。
3.2.4循环冗余检验的原理
在数据链路层传送的帧中，广泛使用了循环冗余检验CRC的检错技术。下面我们用一个具体的例子来说明循环冗余检验的原理。
假设待传送的数据M=1010001101（共kbit）。我们在M的后面再添加供差错检测用的nbit冗余码一起发送。在所要发送的数据后面增加一些冗余码，虽然增大了数据传输的开销，但却可以进行差错检测。在传输可能出现差错时，付出这种代价还是值得的。
这nbit冗余码是这样得出的。用二进制的模2运算①进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R，余数R比除数P至少要少1个比特。至于P是怎样选定的，下面还要介绍。在图3-4所示的例子中，n=5,P=110101，模2运算的结果是：商Q=1101010110，而余数R=01110。现在将得到的余数R就作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或2nM+R。
为检测差错而在数据后面添加上的冗余码常称为帧检验序列FCS(FrameCheckSequence)。帧检验序列就是要保证收到的数据和发送的数据完全相同。这里应当注意，循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码，它可以用CRC，但也不一定选用CRC这种方法。
图3-4循环冗余检验的原理说明
———————————
①注：用模2运算进行加法时不进位，例如，1111+1010=0101。减法和加法一样，按加法规则计算。
———————————
如果数据在传输过程中不产生误码，则接收端收到的应当是2nM+R。将这个数除以P（模2运算）后，得出的余数显然应当是0（读者可以自己进行类似图3-4的运算。被除数现在是101000110101110，而除数是P=110101，看余数是否为0）。若数据在传输过程中出现误码，则在接收端进行以上的运算后，一般就不会得出余数为0的结果。
一种较方便的方法是用多项式来表示循环冗余检验过程，即使用多项式相应的系数来表示上述二进制数字中的1和0。例如，可以用多项式P(X)=X5+X4+X2+1来表示上面的除数P（称为生成多项式）。因此，在接收端进行的运算就可以写为
只要得出的余数R不为0，就表示检测到了差错（注意：这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错），然后就丢弃这个出现差错的帧。
那么，能不能说只要得出的余数R是0，就一定没有出现差错呢？不行！因为在某种非常特殊的比特差错组合下，也可能非常碰巧地使得余数R恰好为0。但只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就可以是个极小的数值。现在广泛使用的P(X)有以下几种：
CRC-16=X16+X15+X2+1
CRC-CCITT=X16+X12+X5+1
CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1
应当注意，仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。所谓“无差错接受”就是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”，或更简单些，这是指“凡是接受的帧均无传输差错”（丢弃的帧都不属于接受的帧）。而要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。
3.2.5停止等待协议的算法
为了对上面所述的停止等待协议有一个完整而准确的理解，下面给出此协议的算法，读者应弄清算法中的每一个步骤。
在发送结点：
(1)从主机取一个数据帧。
(2)V(S)←0。{发送状态变量初始化}
(3)N(S)←V(S)；{将发送状态变量的数值写入发送序号}
将数据帧送交发送缓存。
(4)将发送缓存中的数据帧发送出去。
(5)设置超时计时器。{选择适当的超时重传时间tout}
(6)等待。{等待以下(7)~(9)这三个事件中最先出现的一个}
(7)若收到确认帧ACK，则：
从主机取一个新的数据帧；V(S)←[1(V(S)]；{更新发送状态变量，变为下一个序号}转到(3)。
(8)若收到否认帧NAK，则转到(4)。{重传数据帧}
(9)若超时计时器时间到，则转到(4)。{重传数据帧}
在接收结点：
(1)V(R)←0。{接收状态变量初始化，其数值等于欲接收的数据帧的发送序号}
(2)等待。
(3)当收到一个数据帧，就检查有无产生传输差错(如用CRC)。
若检查结果正确无误，则执行后续算法；否则转到(8)。
(4)若N(S)=V(R)，则执行后续算法；{收到发送序号正确的数据帧}否则丢弃此数据帧，然后转到(7)。
(5)将收到的数据帧中的数据部分送交主机。
(6)V(R)←[1(V(R)]。{更新接收状态变量，准备接收下一个数据帧}
(7)发送确认帧ACK，并转到(2)。
(8)发送否认帧NAK，并转到(2)。
从以上算法可知，停止等待协议中需要特别注意的地方，就是在收发两端各设置一个本地状态变量(仅占1bit)。状态变量的概念很重要，一定要弄清以下几点：
(1)每发送一个数据帧，都必须将发送状态变量V(S)的值(即0或1)写到数据帧的发送序号N(S)上。但只有收到一个确认帧ACK后，才更新发送状态变量V(S)一次(将1变成0，或0变成1)并发送新的数据帧。
(2)在接收端，每接收到一个数据帧，就要将发方在数据帧上设置的发送序号N(S)与本地的接收状态变量V(R)相比较。若二者相等就表明是新的数据帧，否则为重复帧。
(3)在接收端，若收到一个重复帧，则丢弃它(即不做任何处理)，且接收状态变量不变，但此时仍须向发送端发送一个确认帧ACK。
(4)在以上的算法中，我们假定接收结点在收到有差错的帧时就要向发送结点发送一个否认帧NAK。但这并不是必须的。实际上，许多实用的链路层协议是采用另一种做法，这就是在收到有差错的帧时，除丢弃该帧外，什么其他的动作都不做。发送结点只要在设定的某个时间内没有收到对方的确认帧，就重传已发送的帧。不发送否认帧的好处是可以简化数据链路层的协议。
发送端在发送完数据帧时，必须在其发送缓存中保留此数据帧的副本。这样才能在出差错时进行重传。只有在收到对方发来的确认帧ACK时，方可清除此副本。
由于发送端对出错的数据帧进行重传是自动进行的，所以这种差错控制体制常简称为ARQ(AutomaticRepeatreQuest)，直译是自动重传请求，但意思是自动请求重传。
3.2.6停止等待协议的定量分析
下面对停止等待协议进行定量分析(图3-5)。我们仍采用图3-1所示的半双工通信模型。我们设结点A向结点B发送数据帧。结点B只发送确认帧而不发送否认帧，也不发送自己的数据帧。全双工通信的定量分析要稍复杂些。
图3-5停止等待协议中数据帧和确认帧的发送时间关系
设tf是一个数据帧的发送时间，且数据帧的长度是固定不变的。显然，数据帧的发送时间tf是数据帧的长度lf(bit)与数据的发送速率C(bit/s)之比，即
tf=lf/C(s)(3-1)
发送时间tf也就是数据帧的发送时延。数据帧沿链路传到结点B还要经历一个传播时延tp，它是信号（电磁波）在物理链路上传播所造成的时延。结点B收到数据帧要花费时间进行处理，此时间称为处理时间tpr。结点B接着发送确认帧ACK，其发送时间为ta，传播时延为tp（我们设信道的双向传播时延都是一样的）。结点A收到确认帧后也要花费处理时间，我们设这个时间和处理数据帧的时间一样，都是tpr。然后才接着发送下一个数据帧。为方便起见，我们设重传时间为
tout=tp+tpr+ta+tp+tpr(3-2)
重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。为研究问题方便起见，我们设上式右端的处理时间tpr和确认帧的发送时间ta都远小于传播时延tp，这样就可简单地将重传时间取为两倍的传播时延，即
tout=2tp(3-3)
因此，两个发送成功的数据帧之间的最小时间间隔tT为
tT=tf+tout=tf+2tp(3-4)
如遇发生差错，则成功发送1个数据帧所需的时间显然要超过tT。
现在设数据帧出现差错(包括帧丢失)的概率为p，但假设确认帧不会出现差错(我们设确认帧很短，因而确认帧出差错的概率也就较小)。此外，允许重传的次数不受限制。这样，可以得出正确传送一个数据帧所需的平均时间tav来。推导的主要步骤如下：
tav=tT(1+一个帧的平均重传次数)
一帧的平均重传次数={1(P[重传次数为1]+2(P[重传次数为2]+3(P[重传次数为3]+…}
={1(P[第1次发送出错](P[第2次发送成功]
+2(P[第1,2次发送出错](P[第3次发送成功]
+3(P[第1,2,3次发送出错](P[第4次发送成功]+…}
=p(1–p)+2p2(1–p)+3p3(1–p)+…
这里P[X]是出现事件X的概率。这样就可得出正确传送一个数据帧所需的平均时间：
(3-5)
不难看出，当传输差错率增大时，tav也随之增大。当无差错时，p=0,tav=tT。
每秒成功发送的最大帧数就是链路的最大吞吐量(max。显然，
(max=1/tav=(1(p)/tT(3-6)
在发送端，设数据帧的实际到达率为((即每秒到达(个帧)，则(不应超过最大吞吐量(max，即
(((1(p)/tT(3-7)
用时间tf进行归一化，得出归一化的吞吐量(为
(((tf((1(p)/(<1(3-8)
其中参数(是tT的归一化时间：
((tT/tf(1(3-9)
当重传时间远小于发送时间时，((1，此时的归一化吞吐量
((1(p(3-10)
以上所讨论的停止等待协议ARQ的优点是：比较简单，但缺点是：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。为了克服这一缺点，就产生了另外两种协议，即连续ARQ和选择重传ARQ。这将在下面3.3和3.4节进一步讨论。
3.3连续ARQ协议
3.3.1连续ARQ协议的工作原理
我们先用图3-6所示的简单例子来讨论连续ARQ协议的工作原理。它的要点就是在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。
图3-6连续ARQ协议的工作原理：对出错数据帧的处理
如图3-6所示，结点A向结点B发送数据帧。当结点A发完0号帧后，不是停止等待，而是继续发送后续的1号帧、2号帧等。A每发送完一帧就要为该帧设置超时计时器。由于连续发送了许多帧，所以确认帧必须要指明是对哪一帧进行确认。在图3-6中，ACKn表示对第(n–1)号帧的确认。这表示对发送方说：“我已正确收到了第(n–1)号帧，下一次我期望收到第n号帧”。
结点B正确地收到了0号帧和1号帧，并送交其主机。现在设2号帧出了差错，于是结点B的CRC检验器就自动将有差错的2号帧丢弃，然后就等待发送端超时重传。
这里要注意以下三点：
(1)接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的3个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个2号帧还没有收到。接收端虽然丢弃了这些不按序的无差错帧，但应重复发送已经发送过的最后一个确认帧ACK2（这是防止已经发送过的确认帧ACK2丢失了）。
(2)ACK1表示确认0号帧DATA0，并期望下次收到1号帧；ACK2表示确认1号帧DATA1，并期望下次收到2号帧。依此类推。
(3)结点A在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间tout内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间tout到了而仍未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到2号帧的确认而重传2号数据帧时，虽然结点A已经发完了5号帧，但仍必须向回走，将2号帧及其以后的各帧全部进行重传。正因为如此，连续ARQ又称为Go-back-NARQ，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。
(4)以上讲述的仅仅是连续ARQ协议的工作原理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于N个独立的超时计时器的功能（见习题3-14）。
从这里不难看出，连续ARQ协议一方面因连续发送数据帧而提高了信道的利用率，但另一方面，在重传时又必须把原来已传送正确的数据帧进行重传(仅因这些数据帧的前面有一个数据帧出了错)，这种做法又使传送效率降低。由此可见，若传输信道的传输质量很差因而误码率较大时，连续ARQ协议不一定优于停止等待协议。
若2号数据帧不是出现差错而是丢失了，则情况也是类似的，读者可自行分析。
3.3.2连续ARQ协议的吞吐量
可以很方便地导出连续ARQ协议的吞吐量公式。
我们假定在不出现差错时，成功地发送一个数据帧所需的时间是tf(而不是像图3-5中所示的需时间tT)。当出现差错时，重传一个数据帧所需的时间设为tT。所以只要参照停止等待协议的公式(3-5)，就不难得出，在连续ARQ协议的情况下，正确传送一个数据帧所需的平均时间是：
(3-11)
这里参数(仍为比值tT/tf，tT略大于tf+tout。
在发送结点处于饱和状态下，吞吐量的最大值是：
(3-12)
而归一化的吞吐量为
(3-13)
我们应注意到，若传播时延、重传时间等都远小于一个数据帧的发送时间tf，则((1，这时(3-13)式将和(3-10)式一样。
下面是几个简单的例子。
[例1]若数据帧的差错率p=0.01，而参数(=4，则对于停止等待协议，((0.99/4，但对于连续ARQ协议，((0.96。故即使在数据帧的差错率高达0.01时，连续ARQ的效率也比停止等待协议的高。
[例2]考虑在广域网上传数据。设数据帧长为1200bit，线路传输速率为9.6kb/s。求出数据帧的发送时间tf=125ms。设链路长度为160km。若传播时延为1ms，它显然远小于数据帧的发送时间。若确认帧的发送时间和结点对数据帧和确认帧的处理时间都远小于125ms，则tout也应远小于tf。这时，停止等待协议与连续ARQ协议区别很小。
现在假定通信是全双工的。这时，结点B没有必要专门发送确认帧ACK或NAK。当结点B向结点A发送数据时，把确认信息捎带传过去即可。这样做可以提高效率。在这种情况下，发送端收到对方确认的最短时间是2tp+tf，这里tp是传播时延。为了防止不必要的超时重传，可以把tout取得稍大些，例如，取tout=2tp+2tf。于是得出
tT=tf+tout=2tp+3tf(=tT/tf=3+2tp/tf
在这种情况下，连续ARQ协议明显优于停止等待协议。
如果将线路速率从9.6kb/s提高到56kb/s，则对1200bit长的数据帧，
tf=1200/56000(21ms
对于1600km的线路，2tp约为20ms，而tout=2tp+2tf=62ms。此时(=1+62/21(4。在这种情况下，连续ARQ协议比停止等待协议强得多。
[例3]两个卫星地球站通过卫星进行通信。从发送站到接收站的传播时延一般在250(270ms之间，这里取传播时延tp=250ms。设数据帧长为1200bit，而线路速率为4.8kb/s。此时，tf=250ms。取tout=2tp+2tf，得出(=tT/tf=5。若线路速率为9.6kb/s，则tf=125ms，(=7。若线路速率再提高到48kb/s，则tf=25ms，(=23。很明显，在卫星通信时，由于传播时延很大，停止等待协议就很不适用。这时必须采用连续ARQ协议。
3.3.3滑动窗口的概念
在前面已经介绍了连续ARQ的概念。下面我们进行更深入的讨论。
在使用连续ARQ协议时，有以下两个问题要解决：
(1)当未被确认的数据帧的数目太多时，只要有一帧出了差错，就可能要有很多的数据帧需要重传，这必然就要白白花费较多的时间，因而增大开销。
(2)为了对所发送出去的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样又增加了一些不必要开销。
因此，在连续ARQ议中，应当将已发送出去但未被确认的数据帧的数目加以限制。这就是本节滑动窗口所要研究的内容。
我们从停止等待协议中已经得到了启发。在停止等待协议中，无论发送多少帧，只需使用1个比特来编号就足够了。发送序号循环使用0和1这两个序号。对于连续ARQ协议，也可采用同样的原理，即循环重复使用已收到确认的那些帧的序号。这时只需要在控制信息中用有限的几个比特来编号就够了。当然这还要加入适当的控制机制才行。这就是要在发送端和接收端分别设定所谓的发送窗口和接收窗口。下面先讨论发送窗口。
发送窗口用来对发送端进行流量控制，而发送窗口的大小WT代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。显然，停止等待协议的发送窗口大小是1，表明只要发送出去的某个数据帧未得到确认，就不能再发送下一个数据帧。发送窗口的概念最好用图形来说明。
我们现在设发送序号用3比特来编码，即发送序号可以有8个不同的序号，从0到7。又假定发送窗口WT=5，这表示在未收到对方确认信息的情况下，发送端最多可以发送出5个数据帧。发送窗口的规则归纳如下：
(1)发送窗口内的帧是允许发送的帧，而不考虑有没有收到确认。发送窗口右侧所有的帧都是不允许发送的帧。图3-7(a)说明了这一情况。
(2)每发送完一个帧，允许发送的帧数就减1。但发送窗口的位置不改变。图3-7(b)有三种不同的帧：已经发送了帧（最左边的0号帧）；允许发送的帧（共4个，左边的1号帧至4号帧）；以及不允许发送的帧（5号帧和以后的帧）。
(3)如果所允许发送的5个帧都发送完了，但还没有收到任何确认，那么就不能再发送任何帧了。图3-7(c)表示这种情况。这时，发送端就进入等待状态。
(4)每收到对一个帧的确认，发送窗口就向前（即向右方）滑动一个帧的位置。图3-7(d)表示收到了对前三个帧的确认，因此发送窗口可向右方滑动三个帧的位置。在图3-7(d)中共有四种不同的帧：已发送且已收到了确认的帧（最左边的0~2号帧）；已发送但未收到确认的帧（左边的3~4号帧）；还可以继续发送的帧（5~7号帧）；以及不允许发送的帧（右边的0号帧和以后的帧）。
为了减少开销，连续ARQ协议还规定接收端不一定每收到一个正确的数据帧就必须立即发回一个确认帧，而是可以在连续收到好几个正确的数据帧以后，才对最后一个数据帧发确认信息，或者可以在当自己有数据要发送时才将对以前正确收到的帧加以捎带确认。这就是说，对某一数据帧的确认就表明该数据帧和这以前所有的数据帧均已正确无误地收到了。这样做可以使接收端少发送一些确认帧，因而减少了开销。例如，在图3-7(d)中，接收端可以只发送一个对2号帧的确认，表示2号帧和它以前的0号和1号帧都已经正确收到了。
图3-7发送窗口控制发送端的发送速率：(a)允许发送0~4号共5个帧；
(b)允许发送1~4号共4个帧；(c)不允许发送任何帧；(d)允许发送5~7号共3个帧。
同理，在接收端设置接收窗口是为了控制可以接收哪些数据帧而不可以接收哪些帧。在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续ARQ协议中，接收窗口的大小WR=1。接收窗口的规则很简单，归纳如下：
(1)只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。
(2)每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时向发送端发送对该帧的确认。
图3-8(a)表明一开始接收窗口处于0号帧处，接收端准备接收0号帧。一旦收到0号帧，接收窗口即向前滑动一个帧的位置(图3-8(b))，准备接收1号帧，同时向发送端发送对0号帧的确认信息。当陆续收到1号至3号帧后，接收窗口的位置应如图3-8(c)所示。
不难看出，只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。发送端若没有收到该确认，发送窗口就不能滑动。
正因为收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于1时，就是我们最初讨论的停止等待协议。
下面讨论当数据帧的发送序号所占用的比特数一定时，发送窗口的最大值是多少。初看起来，问题好像很简单。例如用3比特可编出8个不同的序号，因而发送窗口的最大值似乎应为8。但实际上，设置发送窗口为8将使协议在某些情况下无法工作。现在我们就来说明这一点。
现在设发送窗口WT=8。设发送端发送完0~7号共8个数据帧。因发送窗口已满，发送暂停。假定这8个数据帧均已正确到达接收端，并且对每一个数据帧，接收端都发送出确认帧。下面考虑两种不同的情况。
图3-8接收窗口WR的意义：
(a)准备接收0号帧；(b)准备接收1号帧；(c)准备接收4号帧
第一种情况是：所有的确认帧都正确到达了发送端，因而发送端接着又发送8个新的数据帧，其编号应当是0~7。请注意，序号是循环使用的。所以序号虽然相同，但8个帧都是新的帧。
第二种情况是：所有的确认帧都丢失了。经过一段由超时计时器控制的时间后，发送端重传这8个旧的数据帧，其编号仍为0~7。
问题已经十分明显了。接收端第二次收到编号为0~7的8个数据帧时，无法判定：这是8个新的数据帧，或这是8个旧的、重传的数据帧。
因此，将发送窗口设置为8显然是不行的。像上述那样的证明方法很有用。这就是当我们要证明某个协议是错误时，只要设法找出一个具体例子说明该协议不能正确工作就算证明完毕。但反过来若要证明某个协议是正确的就很困难。就算能够举出1000个例子说明协议能正常工作也还不充分，因为很可能该协议用到第1001个例子就出现问题。
可以证明，当用n个比特进行编号时，若接收窗口的大小为1，则只有在发送窗口的大小时，连续ARQ协议才能正确运行(见习题3-9)。这就是说，当采用3bit编码时，发送窗口的最大值是7而不是8。这对一般的陆地链路已足够大了。但对于卫星链路，由于其传播时延很大，发送窗口也必须适当增大才能使信道利用率不致太低。这时常用7bit编码，因而发送窗口的大小可达127。在这种情况下，所有已发送出去的但尚未被确认的数据帧都必须保存在发送端的缓存中，以便在出差错时进行重传。当然，这就要占用相当大的存储器空间。相反，对于停止等待协议，发送窗口WT=1，发送端只要花费1个数据帧的存储空间即可。
顺便指出，上述的这种对已发送过的数据帧的保存，是使用一个先进先出的队列。发送端每发完一个新的数据帧就将该帧存入这个队列。当队列长度达到发送窗口大小WT时，即停止再发送新的数据帧。当按照协议进行重传(重传1帧或多帧)时，队列并不发生变化。只有当收到对应于队首的帧的确认时，才将队首的数据帧清除。若队列变空，则表明全部已发出的数据帧均已得到了确认。
3.3.4信道利用率
由于每个数据帧都必须包括一定的控制信息(如帧的序号、地址、同步信息以及其他的一些控制信息)，所以即使连续不停地发送数据帧，信道利用率(即扣除全部的控制信息后的数据率与信道容量之比)也不可能达到100%。当出现差错时(这是不可避免的)，数据帧的不断重传将进一步使信道利用率降低。
很明显，若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。但反过来，若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。
要定量地分析这问题，就必须知道链路的差错特性。对于卫星信道，每个比特的出错可视为独立的(因为差错主要是由卫星到地球的传输途径中的随机噪声引起的)。误比特率记为pb。设数据帧长为lf(即数据部分加上控制信息)，则数据帧的差错率或误帧率(即1帧中至少有1个比特出错的概率)为
(3-14)
对于很小的pb，上式可近似为
p(lfpb<<1(3-15)
上述的这种误码特性并不适用于陆地上的链路，因为对陆地上的链路，突发性误码是主要的。当发生突发性误码时，一连串的比特都要出错。但是，一些实验表明，在产生突发性误码时，误帧率与帧长成正比[BURT72]。这样，当差错率很低时，公式(3-15)既可用于卫星链路，又可用于陆地上的链路。
设发送端工作在饱和状态的发送速率为每秒发送(max帧。设每帧中数据为ldbit而控制信息为lhbit。由(3-12)式可求出平均有效数据率D(指最后交付给主机的平均数据率)为：
(3-16)
令tf(lf/C((ld(lh)/C，其中C为链路容量（也就是链路的带宽或链路的最高数据率），则可得出连续ARQ协议的单位信道容量的平均有效数据率，即通常所说的信道利用率U
(3-17)
公式(3-17)就是信道利用率与帧长的关系。信道利用率越接近于1，信道的利用就越充分。由于误帧率p以及参数a都与帧长有关，因此只有在近似的条件下信道利用率与帧长才能写成简单的数学表达式。
3.4选择重传ARQ协议
为进一步提高信道的利用率，可设法只重传出现差错的数据帧或者是计时器超时的数据帧。但这时必须加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。这就是选择重传ARQ协议。
使用选择重传ARQ协议可以避免重复传送那些本来已经正确到达接收端的数据帧。但我们付出的代价是在接收端要设置具有相当容量的缓存空间，这在许多情况下是不够经济的。正因如此，选择重传ARQ协议在目前就远没有连续ARQ协议使用得那么广泛。今后存储器芯片的价格会更加便宜，选择重传ARQ协议还是有可能受到更多的重视。
对于选择重传ARQ协议，接收窗口显然不应该大于发送窗口。若用n比特进行编号，则可以证明，接收窗口的最大值受下式的约束(见习题3-10)
WR(2n/2(3-18)
当接收窗口WR为最大值时，WT=WR=2n/2。例如在n=3时，可以算出WT=WR=4。
习题
3-01数据链路(即逻辑链路)与链路(即物理链路)有何区别？“电路接通了”与“数据链路接通了”的区别何在？
3-02数据链路层中的链路控制包括哪些功能？
3-03考察停止等待协议算法。在接收结点，当执行步骤(4)时，若将“否则转到(7)”改为“否则转到(8)”，将产生什么结果？
3-04试导出公式(3-5)。
3-05试导出停止等待协议的信道利用率公式。
3-06信道速率为4kb/s。采用停止等待协议。传播时延tp=20ms。确认帧长度和处理时间均可忽略。问帧长为多少才能使信道利用率达到至少50%？
3-07在停止等待协议中，确认帧是否需要序号？请说明理由。
3-08试写出连续ARQ协议的算法。
3-09试证明：当用n个比特进行编号时，若接收窗口的大小为1，则只有在发送窗口的大小WT(2n(1时，连续ARQ协议才能正确运行。
3-10试证明：对于选择重传ARQ协议，若用n比特进行编号，则接收窗口的最大值受公式(3-18)的约束。
3-11在选择重传ARQ协议中，设编号用3bit。再设发送窗口WT=6而接收窗口WR=3。试找出一种情况，使得在此情况下协议不能正确工作。
3-12在连续ARQ协议中，设编号用3bit，而发送窗口WT=8。试找出一种情况，使得在此情况下协议不能正确工作。
3-13在什么条件下，选择重传ARQ协议和连续ARQ协议在效果上完全一致？
3-14在连续ARQ协议中，若WT=7，则发送端在开始时可连续发送7个数据帧。因此，在每一帧发出后，都要置一个超时计时器。现在计算机里只有一个硬时钟。设这7个数据帧发出的时间分别为t0,t1,...,t6，且tout都一样大。试问如何实现这7个超时计时器(这叫软时钟法)？
3-15卫星信道的数据率为1Mb/s。取卫星信道的单程传播时延为0.25秒。每一个数据帧长都是2000bit。忽略误码率、确认帧长和处理时间。试计算下列情况下的信道利用率：
(1)停止等待协议。
(2)连续ARQ协议，WT=7。
(3)连续ARQ协议，WT=127。
(4)连续ARQ协议，WT=255。
3—13
1101010110←Q商除数P→110101101000110100000←2nM被除数11010111101111010111101011010111111011010110110011010111001011010101110←R余数ABDATADATAACK传播时延tp处理时间tpr确认帧发送时间ta传播时延tp处理时间tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout数据链路层主机A缓存主机B数据链路AP2AP1缓存发送方接收方帧高层帧ABDATADATADATADATA送主机B送主机B送主机B送主机B(a)ABDATA送主机BDATA送主机B(b)时间时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况ABDATA0NAKDATA0送主机ACK(b)数据帧出错ABDATA0DATA0送主机ACK(c)数据帧丢失ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失重传重传tout重传tout出错丢失！丢失！01234567012发送窗口WT不允许发送这些帧允许发送5个帧01234567012不允许发送这些帧还允许发送4个帧WT01234567012不允许发送这些帧WT已发送已发送01234567012不允许发送这些帧还允许发送3个帧WT已发送已发送并已收到确认(a)(b)(c)(d)不允许接收这些帧01234567012WR准备接收0号帧不允许接收这些帧01234567012WR准备接收1号帧不允许接收这些帧01234567012WR准备接收4号帧已收到已收到(a)(b)(c)DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK1确认DATA0ACK2确认DATA1DATA2出错，丢弃DATA3不按序，丢弃，重传ACK2DATA4不按序，丢弃，重传ACK2DATA5不按序，丢弃，重传ACK2ACK3ACK3确认DATA2ACK4确认DATA3ACK4重传DATA5重传DATA4超时重传时间ABtout送交主机送交主机…??ACK2ACK2ACK2 |
|
