构造可靠数据传输

rdt（reliable data transfer protocol，可靠数据传输协议）

什么是可靠？

不错、不丢、不乱

1.rdt1.0：可靠信道上的可靠数据传输

最简单的情况即为底层信道是完全可靠的，则该协议非常简单。

下图显示了rdt1.0发送方和接收方的有限状态机（Finite-State Machine, FSM）。

因为底层信道完全可靠，所以发送方和接收方只要能正确接收数据即可。

2.rdt2.0：产生位错误的信道

底层信道更为实际的模型是分组中的比特可能受损的模型。

当出现位错误的时候，因为纠正错误的实现难度和代价都比较大，因此实际中都是采用直接重传的方式。

如何从错误中恢复？

• 肯定确认（acknowledgement, ACK）：接收方显式地告知发送方分组已正确接收
• 否定确认（negative acknowledgement, NAK）：接收方显式地告知发送方分组有错误
• 发送方收到NAK后，重传对应的分组

基于以上重传机制的rdt协议称为自动重传请求（Automatic Repeat reQuest, ARQ）协议。

rdt2.0引入的新机制：差错检测、ACK/NAK、重传。

发送方：

“wait for call from above”的状态，收到数据后，将数据（带有检验和）打包发送出去，然后进入到“wait for ACK or NAK”的状态。

“wait for ACK or NAK”的状态，若收到来自接收方的数据并且收到了NAK，则重传之前发送的数据；若收到来自接收方的数据并且收到了ACK，则直接进入到“wait for call from above”的状态。

接收方：

若收到来自发送方的数据并且检验没有出现差错，则拆包并且发送ACK给发送方；若收到来自发送方的数据并且检验出错了，则直接发送NAK给发送方。

3.rdt2.1：发送方, 应对ACK/NAK破坏

rdt2.0的问题有：ACK/NAK可能出错，并且接收方无法确定发送方发过来是新的报文还是因为ACK出错而重传过来的，因此需要给报文编写序号。

发送方：

“wait for call from above 0”的状态，收到数据后，将0和数据（带有校验和）打包发送，然后进入到“wait for ACK or NAK 0”的状态。

“wait for ACK or NAK 0”的状态，收到来自接收方的数据后，若数据检验出错了或者是NAK，则重传序号为0的数据；若检验没有出错且为ACK，则直接进入到“wait for call from above 1”的状态。

“wait for call from above 1”的状态，收到数据后，将1和数据（带有校验和）打包发送，然后进入到“wait for ACK or NAK 1”的状态。

“wait for ACK or NAK 1”的状态，收到来自接收方的数据后，若数据检验出错了或者是NAK，则重传序号为1的数据；若检验没有出错且为ACK，则直接进入到“wait for call from above 0”的状态。

接收方：

“wait for 0 from below”的状态，收到数据后，若检验没有出错且序号为0，则拆包并且对所接收的分组发送ACK（序号为0），进入到“wait for 1 from below”的状态；若检验出错了，则对上次接收的分组发送NAK（序号为1）；若检验没有出错但是序号为1，则对上次接收的分组发送ACK（序号为1），以便发送方进入下一个状态实现双方的同步。

“wait for 1 from below”的状态，收到数据后，若检验没有出错且序号为1，则拆包并且对所接收的分组发送ACK（序号为1），进入到“wait for 0 from below”的状态；若检验出错了，则对上次接收的分组发送NAK（序号为0）；若检验没有出错但是序号为0，则对上次接收的分组发送ACK（序号为0），以便发送方进入下一个状态实现双方的同步。

Rdt 2.1 vs. Rdt 2.0

发送方：

• 为每个分组增加了序列号
• 两个序列号(0, 1)就够用，为什么？因为rdt采用的是停等协议，因此接收方可以通过这一位知道发送方是否正在重传前一个发送的分组，或是一个新的分组，即双方都只知道新的1个和前1个共2个分组。
• 需校验ACK/NAK消息是否发生错误
• 状态数量翻倍
• 状态必须“记住”“当前”的分组序列号

接收方:

• 需判断分组是否是重复
• 当前所处状态提供了期望收到分组的序列号
• 注意：接收方无法知道ACK/NAK是否被发送方正确收到

4.rdt2.2：无NAK消息协议

rdt2.2是在有比特差错信道上实现的一个无NAK的可靠数据传输协议。rdt2.1和rdt2.2之间的细微变化在于，接收方此时必须包括由一个ACK报文所确认的分组序号（通过接收方FSM中，在make_pkt()中包括参数ACK 0或ACK 1来实现），发送方此时必须检查接收到的ACK报文中被确认的分组序号（通过发送方FSM中，在isACK()中包括参数0或1来实现）。

发送方：

“wait for call from above 0”的状态，收到数据后，将0和数据（带有校验和）打包发送，然后进入到“wait for ACK 0”的状态。

“wait for ACK 0”的状态，收到来自接收方的数据后，若数据检验出错了或者是ACK 1，则重传序号为0的数据；若检验没有出错且为ACK 0，则直接进入到“wait for call from above 1”的状态。

“wait for call from above 1”的状态，收到数据后，将1和数据（带有校验和）打包发送，然后进入到“wait for ACK 1”的状态。

“wait for ACK 1”的状态，收到来自接收方的数据后，若数据检验出错了或者是ACK 0，则重传序号为1的数据；若检验没有出错且为ACK 1，则直接进入到“wait for call from above 0”的状态。

接收方：

“wait for 0 from below”的状态，收到数据后，若检验没有出错且为ACK 0，则拆包并且对所接收的分组发送ACK 0，进入到“wait for 1 from below”的状态；若检验出错或者是ACK 1，则对上次接收的分组发送ACK 1。

“wait for 1 from below”的状态，收到数据后，若检验没有出错且为ACK 1，则拆包并且对所接收的分组发送ACK 1，进入到“wait for 0 from below”的状态；若检验出错或者是ACK 0，则对上次接收的分组发送ACK 0。

5.rdt3.0

rdt3.0中考虑了丢包和延迟分组的情况，因此引入了定时器的机制。

发送方：

“wait for call from above 0”的状态，收到数据后，将0和数据（带有校验和）打包发送，开启计时，然后进入到“wait for ACK 0”的状态；若收到来自接收方的数据，则不做处理。

“wait for ACK 0”的状态，收到来自接收方的数据后，若数据检验出错了或者是ACK 1，则不做任何处理，等待超时（因为定时器设置的时间一般都很短，因此可以简化操作）；若超时，则重新发送序号为0的数据，并重新计时；若检验没有出错且为ACK 0，则停止计时，并进入到“wait for call from above 1”的状态。

“wait for call from above 1”的状态，收到数据后，将1和数据（带有校验和）打包发送，开启计时，然后进入到“wait for ACK 1”的状态；若收到来自接收方的数据，则不做处理。

“wait for ACK 1”的状态，收到来自接收方的数据后，若数据检验出错了或者是ACK 0，则不做任何处理，等待超时（因为定时器设置的时间一般都很短，因此可以简化操作）；若超时，则重新发送序号为1的数据，并重新计时；若检验没有出错且为ACK 1，则停止计时，并进入到“wait for call from above 0”的状态。

接收方：和rdt2.2的接收方一样

流水线可靠数据传输协议

rdt3.0性能问题的核心在于它是一个停等协议。

由上图可以看出，发送方的利用率（即实际用于传输的时间占总时间的比例）非常小，这就造成了极大的资源浪费。

这种特殊的性能问题的一个简单解决方法是：不以停等方式运行，允许发送方发送多个分组而无需等待确认，即采用流水线的方式发送数据。

如果采用流水线的方式则：

1. 必须增加序号范围，因为每个输送中的分组（不计算重传的）必须有一个唯一的序号，且也许有多个在输送中的未确认报文。
2. 协议的发送方和接收方两端也许不得不缓存多个分组。发送方最低限度应该能缓冲那些已发送但没有确认的分组，接收方或许也需要缓冲那些已正确接收的分组。
3. 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。解决流水线的差错恢复有两种基本方法：回退N步（Go-Back-N，GBN）和选择重传（Selective Repeat，SR）。

GBN

发送方：

首先进行初始化，即base=0，nextseqnum=0。

收到数据后，会依次发送N条数据信息，其中，这N个数据只启动了一个计时器，即发送第一个数据后启动计时器（因为数据的传输时间很短，所以只要计时器的时间设置的合理，是完全没有问题的），若发送的数据量达到N以后，会拒绝发送数据，即refuse_data(data)。

若计时器超时，则重新启动计时器，并重新发送从base起至nextseqnum-1的所有数据。

若收到来自接收方发送的数据，并且数据出错了，则为了简化操作，不用做任何处理，等待超时。

若收到来自接收方发送的数据，并且数据没有出错，则base的序号会变成收到的数据包序号+1，若是此时的base=nextseqnum，则说明发送出去的N个数据包都已被接收方正确接收，就可以停止计时器了，否则说明还有数据包没有回来，那么考虑到网络发送的延时问题，就重新启动一个计时器，若超时之后还没回来，则认为回不来了，则将这些已发送但未被确认的分组重新发送一遍，其中窗口位置没有变，即nextseqnum没有改变，必须等到N个数据包都被正确接收后才可以变。注意：GBN协议中，对序号为n的分组的确认采取的是累积确认的方式，即虽然接收了n个ACK的确认，但只要确认第n个数据包没问题，就说明第1个到第n个的数据都没有问题。因此发送方需要按序发送，而接收方需要按序接收。

接收方：

首先进行初始化，即expectedseqnum=0（发送方和接受方的序号要一致，否则将会出现错误），发送一个确认包，与发送方校对序号。

当收到发送方发来的数据，且数据检验没有出错，且数据包的序号和expectedsuqnum是一致的（即是按序接收的），则发送对应序号的ACK，并且expectedseqnum+1。注意：由于网络延时的问题，数据包到达接收方的顺序可能不一样，因此若expectedseqnum=n，来的数据包的序号为n+1的时候，该数据包会直接被丢弃掉，接收方不会缓存，接收方会继续等序号n，若等到了，则n之前的数据包都可以确认。

评价

优点：接收缓存简单，即接收方不需要缓存任何失序分组。

缺点：因为可能只是中间的某一个数据包出了问题，导致后面的所有正确的数据包都需要重传，可能出现某些正确的数据包重传多次的现象，这就浪费了网络传输的资源，且影响了信道的利用率。

SR

结合上图可以看出，发送方的窗口只有当接收方发来顺序的序号之后才会发生移动，而接收方的窗口只有当检验好顺序的序号之后才会移动，但是若不是顺序的序号且该序号在窗口中，也可以被接收方接收，但不会移动窗口位置，且不会发送逆序序号的ACK，所以发送方和接收方的窗口并不总是一致的。如上图所示，因为2号丢失，接收方没有发送2号之后正确接收的数据包序号，等到发送方对应的2号数据包计时器超时后，发送方再次发送2号数据包，被接收方正确接收后，2、3、4、5号的数据包的ACK都被接收方发送出去，接收方的窗口直接移动到6号开始的位置，这就大大地节省了网络传输的资源，且提高了信道的利用率。

问题：序列号空间大小与窗口尺寸需满足什么关系？

$$N_S+N_R<=2^k$$

其中，左边为接收方和发送方两者的窗口尺寸相加，右边的k为序列号的数量。

以上为笔者阅读《计算机网络：自顶向下方法》中rdt部分的心得笔记，如有错误，烦请指出