计算机网络在传输层能在不同主机不同应用进程实现逻辑链接,其中有种可靠数据传输协议,能够保证数据分组无错,不乱,不丢。

先来声明接口:

  1. rtd_send(): 可靠数据传输的发送接口,也就是在“可靠”信道上传输
  2. rtd_rcv():可靠数据传输的接收接口
  3. udt_send():在底层不可靠信道上传输的接口

RDT 1.0

在rdt 1.0最初版本中,我们先假设底层信道完全可靠,那么我们只需要在发送方和接收方分别调用rdt_send()rdt_rcv()即可。

该版本的自动机如图:
RDT 1.0

RDT 2.0

可实际上底层信道会发生位翻转现象,这里我们就引入校验和重传机制,用来检测数据是否发生位错误。

我们可以在发送方计算附带checksum校验和,然后在接收方计算验证checksum,那么会有两种情况:

  1. 校验和正确,表示没有检测出错误(但是有可能发生错误,例如有两个位发生翻转,这种情况不讨论),那么向发送方发送ACK,表示我已经正确收到了。
  2. 校验和错误,说明检测出错误,那么向发送方发送NCK,表示我接收到的数据出错,发送方收到NCK后重传。

该版本的自动机如图:
RDT 2.0

RDT 2.1

如果接收方发送的ACKNCK也出错了怎么办?接收方收到错误消息无法判断,可以重传,可是重传会参数重复分组,那么这里引入序列号机制,接收方就可以丢弃重复分组。

这里定义两个序列号: 01

发送方首先发送序列号为0的分组,然后等待接收方的ACK或者NCK,收到NCK或者不确定的状态就重发,一旦收到ACK就发送序列号为1的分组,以此类推,0, 1序列号交替。

接收方首先接收发送方发送序列号为0的分组,如果接收的数据有错误,那么就发送NCK,如果接收到的数据无误,这里有两种情况:

  1. 接收到序列号为0的分组,将数据递交给上层并发送ACK
  2. 接收到序列号为1的分组,说明有重复(因为我现在就是需要0的分组,你给我发1的,我之前收到过了(因为序列号0, 1交替)),丢弃数据并发送ACK(为什么要发送ACK?因为发送NCK的话,发送方以为你没收到序列号为1的数据,将重发,而你此时又是收到序列号为1数据,然后又发NCK,死循环了,所以需要发送ACK并丢弃。)

在接收方正确接收到序列号为0的数据后,将等待接收序列号为1的数据,以此类推,交替循环。

该版本的自动机如图(图一为发送方,图二为接收方):

RDT 2.1 发送方RDT 2.1 接收方

RDT 2.2

RDT 2.1中变量过多,其实发送NCK是多余的,可以省略,我们可以这样改进:

接收方通过ACK告知最后一个被正确接收的分组,在ACK中加入被确认分组的序列号。

发送方收到重复的ACK后,采取动作和收到NCK一样。

具体过程如下:

发送方首先发送序列号为0的分组,然后等待接收方发送ACK 0,一旦收到ACK 0就发送序列号为1的分组,以此类推。若收到ACK 1或者不确定的状态就重发。

接收方首先接收序列号为0的分组,如果接收的数据有误,就发送ACK 1,如果正确收到数据,那么有两种情况:

  1. 收到序列号为0的分组,就发送ACK 0
  2. 收到序列号为1的分组,就发送ACK 1。这时候也表明数据发重了。

发现上述中,正确收到数据后,就发送对应序列号的ACK,是因为发送方发送序列号几,如果也收到ACK几,那么就会转移到发送下一个序列号的状态,否则就重发。

在接收方正确接收到序列号为0的数据后,将等待接收序列号为1的数据,以此类推,交替循环。

该版本的自动机如图:
RDT 2.2

RDT 3.0

如果信道发生丢失分组的情况,那么上述版本就不够用了。

想象一下这种情况,发送方在等待接收方的ACK时,如果ACK丢失了,那么发送方就会一直等下去,所以这里要引入计时器,在指定时间内如果没收到反馈信息,那么就重发。

具体过程和版本2.2差不多,这里给出几幅图说明情况。

RDT 3.0 example
RDT 3.0 example2

该版本的自动机(发送方)如图:
RDT 3.0

流水线机制

前面介绍的每发送一个分组,就要等待一个ACK,效率太低了。

引进流水线机制后,在收到ACK前可以发送多个分组,然后等待多个ACK返回。这样就需要更大的序号范围和存储空间以缓存分组。

管理这些分组就需要滑动窗口协议。

滑动窗口协议

窗口尺寸N,一次可以管理N个等待确定的分组,有分组确定后,就向后滑动以腾出空间存放下一个个分组。

滑动窗口协议有GBNSR,看动画(点击分组可丢失= =):