停止等待协议

停止等待协议停止等待（stop－and－wait）协议是最简单但也是最基本的数据链路层协议。很多有关协议的基本概念都可以从这个协议中学习到。我们先从最简单的情况讲起。一、不需要数据链路层协议的数据传输当两个主机进行通信时，应用进程要将数据从应用层逐层往下传，经物理层到达通信线路。通信线路将数据传到远端主机的物理层后，再逐层向上传，最后由应用层交给远程的应用进程。但现在为了把主要精力放在数据链路层的协议上，可以采用一个简化的模型（见下图），即把数据链路层以上的各层用一个主机来代替，而物理层和通信线路则等效成一条简单的链路。数据链路层也可简称为链路层。在发方和收方的链路层分别有一个发送缓冲区和接收缓冲区。若进行全双工通信，则在每一方都要同时设有发送缓冲区和接收缓冲区。缓冲区是必不可少的。这是因为在通信线路上数据是以比特流的形式串行传输的，但在计算机内部数据的传输则是以字节（或若干个字节）为单位并行传输的。因此，必须在计算机的内存中设置一定容量的缓冲区，以便解决数据传输速率不一致的矛盾。下图所示的简化模型对于一个计算机网络中任意一条链路上的数据传输情况都是适用的。在网络内部，各交换结点的数据链路层的上面只有一个网络层。对于这种交换结点，网络层就相当于简化模型中的主机。图4-10两台计算机通过一条链路通信的简化模型为了深入理解数据链路层的协议，我们先从一种假想的、完全理想化的数据传输过程开始讨论。下面即可看出，对于这种完全理想化的数据传输，数据链路层协议是根本不需要的。为了和后面的讨论相衔接，我们假定数据传输是以帧为单位。假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。第一个假定很容易理解。对第二个假定则需加以解释。我们假设主机A连续不断地向主机B发送数据。在收方，主机B的链路层也就将收到的数据一帧接一帧地交给主机B。在理想情况下，收方链路层的缓冲区每存满一帧就向主机B交付一帧。如果没有专门的流量控制协议，则收方并没有办法控制发方的发送速率，而收方也很难做到和发方绝对精确同步。当收方链路层向主机交付数据的速率略低于发方发送数据的速率时，缓冲区暂时存放的数据帧就会逐渐堆积起来，最后造成缓冲区溢出和数据帧丢失。因此，上述第二个假定就相当于认为：（1）接收缓冲区的容量为无限大而永远不会溢出；或（2）接收速率与发送速率绝对精确相等。在这样理想化的条件下，数据链路层当然就不需要任何协议就可以保证数据传输的正确。二、具有最简单流量控制的数据链路层协议去掉上述第二个假定，保留第一个假定，即主机A向主机B传输数据的信道仍然是无差错的理想信道。为了使收方的接收缓冲区在任何情况下都不会溢出，在最简单的情况下，就是发方每发送一帧就暂时停下来。收方收到数据帧后就交付给主机，然后发一信息给发方，表示接收的任务已经完成。这时，发方才再发送下一个数据帧。在这种情况下，收方的接收缓冲区的大小只要能够装得下一个数据帧即可。显然，用这样的方法收发双方能够同步得很好，发方发送数据的流量受收方的控制。由收方控制发方的数据流量，乃是计算机网络中流量控制（flowcontrol）的一个基本方法。具有最简单流量控制的数据键路层协议如下：在发送结点：(1）从主机取一个数据帧；（2）将数据帧送到数据链路层的发送缓冲区；（3）将发送缓冲区中的数据帧发送出去；（4）等待；（5）若收到由接收结点发过来的信息（此信息的格式与内容可由双方事先商定好），则从主机取一个新的数据帧，然后转到（2）。在接收结点：（l）等待；（2）若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓冲区；（3）将接收缓冲区中的数据帧上交主机；（4）向发送结点发一信息，表示数据帧已经上交给主机；（5）转到（l）。下图是前面所述的两种情况的对比。图（a）是不需要任何协议的理想化情况。主机A将数据帧（图中用DATA表示）连续发出，而不管发送速率有多快，收方总能够跟得上，收到一帧即交付给主机B。显然，这种完全理想化情况的传输效率是很高的。图（b）是由收方控制发方发送速率的情况。发方每发完一帧就必须停下来，等待收方的信息。由于假定了数据在传输过程中不会出差错，因此收方将数据帧交给主机B后向发方主机A发送的信息，不需要有任何具体的内容，即不需要说明所收到的数据是否是正确无误的。这相当于只要发回一个不需要装入任何信件的空信封就能起到流量控制的作用。图（a）不需要任何数据键路层协议的数据传输（b）具有最简单流量控制的数据键路层协议三、实用的停止等待协议去掉前面的两个假定，讨论实用的数据链路层协议。这就是说，传输数据的信道不是可靠的（即不能保证所传的数据不产生差错），并且还需要对数据的发送端进行流量控制。1不出差错的情况下图（a）是数据在传输过程中不出差错的情况。收方在收到一个正确的数据帧后，即交付给主机B，同时向主机A发送一个确认帧ACK（ACKnowledgment）。当主机A收到确认帧ACK后才能发送一个新的数据帧。这样就实现了收方对发方的流量控制。2数据帧出错现在假定数据帧在传输过程中出现了差错。由于通常都在数据帧中加上了循环冗余校验CRC（CyclicRedundancyCheck），所以结点B很容易检验出收到的数据帧是否有差错（一般用硬件检验）。当发现差错时，结点B就向主机A发送一个否认帧NAK(NegativeACK)，以表示主机A应当重发出现差错的那个数据帧。下图（b）画出了主机A重发数据帧。如多次出现差错，就要多次重发数据帧，直到收到结点B发来的确认帧ACK为止。为此，在发送端必须暂时保存已发送过的数据帧的副本。当通信线路质量太差时，则主机A在重发一定的次数后（如8次或16次，这要事先设定好），即不再进行重发，而是将此情况向上一层报告。3帧丢失有时链路上的干扰很严重，结点B收不到结点A发来的数据帧。这种情况称为帧丢失（图（c））。发生帧丢失时结点B当然不会向结点A发送任何应答帧。图4-12数据帧在键路上传输的几种情况如果结点A要等收到结点B的应答信息后再发送下一个数据帧，那么就将永远等待下去。于是就出现了死锁现象。同理，若结点B发过来的应答帧丢失，也会同样出现这种死锁现象。要解决死锁问题，可在结点A发送完一个数据帧时，就启动一个超时定时器。若到了超时定时器所设立的重发时间tout。而仍收不到结点B的任何应答帧，则结点A就重传前面所发送的这一数据帧（见图4-12（c）,（d））。显然，超时定时器设置的重发时间应仔细选择确定。若重发时间选得太短，则在正常情况下也会在对方的应答信息回到发送方之前就过早地重发数据。若重发时间选得太长，则会浪费时间。一般可将重发时间选为略大于“从发完数据帧到收到应答帧所需的平均时间”。4．重复帧还有问题：若丢失的是应答帧，则超时重发将使主机B收到两个同样的数据帧。由于主机B现在无法识别重复的数据帧，因而在主机B收到的数据中出现了另一种差错——重复帧。要解决重复帧的问题，必须使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。这时应当丢弃这重复帧，因为已经收到过同样的数据帧并且也交给了主机B。但应注意，此时结点B还必须向结点A发送一个确认帧ACK，因为结点B已经知道结点A还没有收到上一次发过去的确认帧ACK。序号所占用的比特数是有限的。因此，经过一段时间后，发送序号就会重复。例如，当发送序号占用3个比特时，就可组成共有8个不同的发送序号，从000到111。当数据帧的发送序号为111时，下一个发送序号就又是000。因此，要进行编号就要考虑序号到底要占用多少个比特。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。一个比特可以有0和1两种不同的序号。这样，数据帧中的发送序号（以后记为N（S），S表示发送）就以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重发的数据帧了。四、停止等待协议的算法为了对上面所述的停止等待协议有一个完整而准确的理解，下面给出此协议的算法。V（S）：发送状态变量V（R）：接收状态变量N(S)：发送序号图停止等待协议在发送结点：（1）从主机取一个数据帧。（2）V（S）←0。（发送状态变量初始化）（3）N（S）←V（S）；（将发送状态变量的数值写入发送序号），将数据帧送交发送缓冲区。（4）将发送缓冲区中的数据帧发送出去。（5）设置超时定时器。（选择适当的超时重发时间tout）（6）等待。(等待以下3个事件中最先出现的一个)（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），则执行后续算法；（收到发送序号正确的数据帧）HOSTL层的用户HOSTL层的用户L层实体L层实体N(S)N(S)V(S）V(R)（R）否则丢弃此数据帧，然后转到（7）。（5）将收到的数据帧中的数据部分送交主机。（6）V（R）←[1－V（R）］。（更新接收状态变量，准备接收下一个数据帧）（7）发送确认帧ACK，并转到（2）。（8）发送否认帧NAK，并转到（2）。从以上算法可知，停止等待协议中需要特别注意的地方，就是在收发两端各设置一个本地状态变量（仅占1个比特）。对于状态变量需要注意以下几点：（l）每发送一个数据帧，都必须将发送状态变量V（S）的值（0或1）写到数据帧的发送序号N（S）上。但只有收到一个确认帧ACK后，才更新发送状态变量V（S）一次（将1变成0或0变成1）并发送新的数据帧。（2）在接收端，每接收到一个数据帧，就要将发方在数据帧上设置的发送序号N（S）与本地的接收状态变量V（R）相比较。若二者相等就表明是新的数据顿，否则为重复帧。（3）在接收端，若收到一个重复帧，则丢弃之（即不做任何处理），且接收状态变量不变，但此时仍须向发送端发送一个确认帧ACK。我们还应注意到，发送端在发送完数据帧时，必须在其发送缓冲区中保留此数据帧的副本。这样才能在出差错时进行重发。只有在收到对方发来的确认帧ACK时，方可清除此副本。由于发送端对出错的数据帧进行重发是自动进行的，所以这种差错控制体制常简称为ARQ（AutomaticRepeatreQuest）,称为自动重发请求或自动请求重发。作业：修改停等协议算法，当出错的时候，接收方不作任何响应。五、停止等待协议的定量分析采用半双工通信模型，横坐标为时间。设结点A向结点B发送数据帧。结点B只发送应答信息而不发送数据帧。全双工通信的定量分析要稍复杂些。图4-14停止等待协议中数据帧和应答帧的发送时间关系数据帧的发送时间(发送时延)tf(s)是数据帧的长度lf（bit）与数据的发送速率C(bit/s)之比tf＝lf／C(s)（4-l）数据帧沿链路传到结点B还要经历一个传播时延(电信号在物理链路上传播所造成的时延)tp。结点B处理收到的数据帧的时间（处理时间）tpr。结点B发送确认帧ACK的时间为ta（意义同tf），传播时延为tp（设信道的双向传播时延都是一样的）。结点A收到确认帧后也要花费处理时间，我们设这个时间和处理数据帧的时间一样，都是tpr。设重发时间（超时定时器所设置的重发时间）为tout＝2tp＋2tpr＋ta（4-2）为研究问题方便起见，我们设上式右端的处理时间tpr和确认帧的发送时间ta都远小于传播时延tp，这样就将重发时间取为两倍的传播时延，即：tout＝2tp（4-3）因此，两个发送成功的数