关于停止等待ARQ通信协议的几种分析方法

第一种分析方法

stop-wait流量控制是最简单的流量控制形式，其工作原理如下。一个源端实体发送一个帧，目的端实体收到后就发回一个对收到帧的确认来表示它愿意接收下一帧。源端在发送下一帧之前必须等到直到收到这一确认。目的端因此仅仅通过不发确认就可以让数据流停下来。
stop-wait方法必须考虑到两类差错。首先，到达目的端的帧可能有损坏，也就是一个或多个位变了。为了使接收端检测出这种差错，链路控制帧包含了一个帧校验序，通常用的是冗余校验。如果检测到差错，则接收端就丢弃这一帧。为了考虑到这种可能性看，源站设置了一个定时器，发完一帧后，源站就等待确认。如果定时器到时间了还没有接收到确认，那么就将同一帧再发一次。注意这种方法要求发送端要保留一个发送帧的副本，直到它收到了该帧的确认。
第二类差错是确认（ACK）坏了。考虑到下列情形。站A发送一帧，该帧被站B正确接收到了，因此它就向源站就送一个确认（ACK）。这个ACK在传输过程中损坏了而使A站无法辨认出来。A站因此超时并重传这一帧。这个重复的帧到达站B并被接收下来。站B因此就收到了同一帧的两个副本，就像收到两个单独的帧一样。为了避免这个问题，数据帧被用0和1交替标记，而确认则有ACK0和ACK1两种形式。ACK0对编号为1的帧做出确认，准备接收编号为0的帧；ACK1对编号为0的帧做出确认，准备接收编号为1的帧。
差错检测、定时器、确认及重传的使用称为自动重传请求（ARQ，Automatic Repeat reQuest），因此我们正在讨论的协议称为停止等待ARQ。
图2-1给出了一个ARQ的例子。他表示从源A到B的传输一系列的情形，这是一个垂直的时间序列图。图中示出了前边描述的两类差错。站点A发送的第三个帧丢失或者损坏了，因此B没有发回ACK。A超时并重传这一帧。后来A发送了一个编号为1的帧，但对方为此返回的ACK丢失了。A超时并重传这同一帧。当B收到连续两帧有相同编号时，它就将第二个帧丢掉但对每个收到的帧都发回一个确认。

图2-1 停止等待ARQ
我们将上述stop-wait协议模型的一系列参数定义如下：
T_frame：传送一帧的时间；
T_prop：A和B之间的传播时延；
T_proc：每个站对一个到来事件的反应处理时间；
T_ack：传送确认信号的时间；
我们可以把反应处理时间忽略掉，因为确认帧比数据帧要小得多。假定每一帧是定长的，现在我们将数据以每T秒一帧的速率传送，则

现在定义吞吐量，为了方便比较，我们将表达式归一化。若一帧在T_frame的时间内传送完，那么归一化吞吐量S的表达式为：

其中参数a定义为：

若现在一个帧丢失或者ACK丢了，那么需要重新传送一次。帧的传送时间为：

现在将超时时间值设为两倍的传播时延值（忽略掉目的端处理时间），所以成功发送一个帧的平均时间为：

若一个帧发送成功之前经历了x-1次失败，那么定义N_x为每个帧的平均传输次数，所以成功传送一个帧的平均时间为：

那么归一化的吞吐量为：

假设单个帧丢失的概率为P，经过公式推导可以得到吞吐量：

通过上面理论推导的式子，可以看出信息丢失的概率P和参数a对系统的吞吐量有着直接的影响。因此在OMNET++构建的ARQ停等协议仿真模型中，主要研究信息丢失的概率P和参数a对系统吞吐量的影响。

第二种分析方法

停等ARQ协议是一种非常简单的传输协议。信息帧的传播时间和ack返回传播时间的和为2τ_p，这比信息帧的传输时间τ_t要小得多。τ_p的计算公式为：

其中c为光速，d为发送方和接收方之间的距离。传输时延τ_t的计算公式为：

其中L是每个信息帧的比特数量，λ是比特的传输速率。
因此，ARQ协议在2τ_p≪τ_t这个条件下的效率是非常高的。如果不满足上面的不等式，那么就应该使用前向纠错(FEC)技术。
当发送端发送一个信息时，接收端会检查它是否有错。如果没有错误，接收端会返回一个ACK信号，这种情况下，发送端就会发送下一个信息帧。如果接收到的信息帧存在错误，接收端返回一个NAK信号，发送端就会重新发送一次上一个帧。如果发送端没有接收到ACK或者NAK，接收端会等待一个固定的timeout时间段，之后发端就会重新发送这个信息帧。
基于上面的讨论，我们可以总结出传播的时间为2τ_p，τ_p为单向传播的时延。
下图为停等ARQ协议的模型。随着ACK信号的返回，说明第1帧信息正确发送，并开始发送第2帧信息。第2帧信息传输错误，返回NAK信号，Transmitter重新发送第2帧信息。由于一些原因，Transmitter没有接收到ACK，Transmitter把第2帧发送课第3次。

Transmitter接收到ACK信号说明第2帧信息正确传输，之后传输第3帧信息。

图2-3 停等ARQ协议模型
下面我们用马尔科夫链来分析停等协议的算法，我们对停等ARQ做出下面的假设：
1.每个帧的平均长度为n比特；
2.发端信道有一个随机噪声，每个比特的错误概率为ε（BER）；
3.假设返回端没有噪声，ACK信号总是能返回到发送端；
4.发送端在接收到ACK信号之前都会一直保存刚刚发送的这个信息帧。
发送端的是否发送下一个信息帧的状态取决于刚刚发送的信息帧。我们可以用马尔科夫链来分析发送端的状态：
1.马尔科夫链的状态i表示发送端第i次发送这个信息帧。状态0表示正确传输；
2.状态数是无限的，因为重传次数是没有限制的；
3.每次成功发送多需要的时间为传输时间和两次传播时间的和T=2τ_p+τ_t;
停等ARQ协议的图像如图9.2所示。e代表的是传输信息帧发生错误的概率，定义方式如下：

下图为停等ARQ协议状态图

对于无差错传播信道来说，ε为0，e也为0。当一个帧中的错误数量非常小时，我们可以认为

上面的式子假设没有前向纠错。那么状态向量可以表述如下

s_i表示第i次传输这个信息，s_0表示没有重传这个信号。
那么信道的相关传输矩阵如下所示：

在平衡状态下，通过求解两个方程得到分布矢量：


上面两个方程的解也非常的简单，得到的s向量组的解如式（2-17）所示：

一个帧的平均重传次数为：

对于一个无噪声信道来说，e为0，那么重传次数也为0。这就说明每个帧都能一次性传输成功。
对于一般信道来说，e大约等于ϵn，远远小于1。那么每个信息帧的重传次数大约为

我们把停等ARQ协议的效率定义为传输总次数的倒数，其中包括第一次的传输。在这种情况下，传输效率η的计算公式为：

对于无差错信道来说，N_t为0，η就为1。对于一个普通信道来说

这就表明传输效率和每个比特的错误概率或者与每个信息帧的长度成反比。因此，系统的性能会随着每个信息帧的长度增加与每个信息帧的错误传输概率增加而降低。
因此，发送方的吞吐量可以表示为:

因此，对于无差错传输信道，每个信息帧都可以保证一次传输成功。我们可以通过估计发送端传输后的状态来计算系统的吞吐量

通过以上对停等ARQ的吞吐量的理论分析可以得知，系统吞吐量与每个信息帧的长度和信道的错误传输概率有关。信道的错误传输概率一定的情况下，信息帧的长度越长，系统的吞吐量就越低。在信息帧长度确定的情况下，信道的错误传输概率越高，系统的吞吐量就越低。

这两种分析方法虽然最后的式子不同，但是最终都是对系统的吞吐量做分析。
最后补充一下，系统的吞吐量是指单位时间内接收或者发送的数据量，一些英文文献中使用的单位是frame/time step.