网络工程师教程数据链路层

(3) 当收到一个数据帧，就检查有无产生传输差错(如用CRC)。 若检查结果正确无误，则执行后续算法； 否则转到(8)。

(4) 若 N(S) = V(R)，则执行后续算法； {收到发送序号正确的数据帧} 否则丢弃此数据帧，然后转到(7)。 (5) 将收到的数据帧中的数据部分送交主机。

(6) V(R)←[1 ? V(R)]。 {更新接收状态变量，准备接收下一个数据帧} (7) 发送确认帧 ACK，并转到(2)。 (8) 发送否认帧 NAK，并转到(2)。

从以上算法可知，停止等待协议中需要特别注意的地方，就是在收发两端各设置一个本地状态变量(仅占1 bit)。状态变量的概念很重要，一定要弄清以下几点：

(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 (Automatic Repeat reQuest)，直译是自动重传请求，但意思是自动请求重传。 3.2.6 停止等待协议的定量分析

下面对停止等待协议进行定量分析(图3-5)。我们仍采用图3-1所示的半双工通信模型。我们设结点A向结点B发送数据帧。结点B只发送确认帧而不发送否认帧，也不发送自己的数据帧。全双工通信的定量分析要稍复杂些。

3—9

A数据帧的tf发送时间两个成功发送的数据帧之间的最小时间间隔tT设置的重传时间toutDATAB传播时延tp处理时间tprACK确认帧发送时间ta传播时延tp处理时间tprDATA时间 图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—10

tav?tT?(1?p)?ipitT?tT/(1?p) (3-5)

i?1?不难看出，当传输差错率增大时，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协议的工作原理。它的要点就是在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。 AB超时重传时间toutDATA0DATA1DATA2??DATA3DATA4DATA5重传DATA2重传DATA3重传DATA4重传DATA5ACK1ACK2ACK2ACK2ACK2ACK3ACK4ACK1 确认DATA0送交主机ACK2 确认DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传ACK2DATA4 不按序，丢弃，重传ACK2DATA5 不按序，丢弃，重传ACK2ACK3 确认DATA2ACK4 确认DATA3送交主机图3-6 连续ARQ协议的工作原理：对出错数据帧的处理 如图3-6所示，结点A向结点B发送数据帧。当结点A发完0号帧后，不是停止等待，而是继续发送后续的1号帧、2号帧等。A每发送完一帧就要为该帧设置超时计时器。由于连续发送了许多帧，所以确认帧必须要指明是对哪一帧进行确认。在图3-6中，ACKn表示对第(n – 1)号帧的确认。这表示对发送方说：“我已正确收到了第(n – 1)号帧，下一次我期望收到第n号帧”。

结点B正确地收到了0号帧和1号帧，并送交其主机。现在设2号帧出了差错，于是

… 3—11

结点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-N ARQ，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。

(4) 以上讲述的仅仅是连续ARQ协议的工作原理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于N个独立的超时计时器的功能（见习题3-14）。 从这里不难看出，连续ARQ协议一方面因连续发送数据帧而提高了信道的利用率，但另一方面，在重传时又必须把原来已传送正确的数据帧进行重传(仅因这些数据帧的前面有一个数据帧出了错)，这种做法又使传送效率降低。由此可见，若传输信道的传输质量很差因而误码率较大时，连续ARQ协议不一定优于停止等待协议。

若2号数据帧不是出现差错而是丢失了，则情况也是类似的，读者可自行分析。 3.3.2 连续ARQ协议的吞吐量

可以很方便地导出连续ARQ协议的吞吐量公式。

我们假定在不出现差错时，成功地发送一个数据帧所需的时间是tf (而不是像图3-5中所示的需时间tT)。当出现差错时，重传一个数据帧所需的时间设为 tT。所以只要参照停止等待协议的公式(3-5)，就不难得出，在连续ARQ协议的情况下，正确传送一个数据帧所需的平均时间是：

?tav?tf?(1?p)?ipitT?tf[1?(??1)p]/(1?p) (3-11)

i?1这里参数?仍为比值tT / tf ，tT略大于tf + tout 。

在发送结点处于饱和状态下，吞吐量的最大值是：

?max?1/tav?(1?p)/tf[1?(??1)p] (3-12) 而归一化的吞吐量为

???tf?(1?p)/[1?(??1)p] (3-13)

我们应注意到，若传播时延、重传时间等都远小于一个数据帧的发送时间tf，则? ? 1，这时(3-13)式将和(3-10)式一样。 下面是几个简单的例子。

[例1] 若数据帧的差错率p = 0.01，而参数? = 4，则对于停止等待协议，? ? 0.99/4，但对于连续ARQ协议，? ? 0.96。故即使在数据帧的差错率高达0.01时，连续ARQ的效率也比停止等待协议的高。

3—12