黄小华的个人网站
熬过无人问津的日子才有诗和远方!
可靠数据传输(rdt)实现的底层原理

可靠数据传输对于应用层、传输层、链路层都很重要 由于网络层提供的尽力而为服务是不可靠的
所以在传输层就要有可靠数据传输协议来确保可靠

什么是可靠?

1.传输的数据包没有错误
2.传输的数据包不丢失
3.传输的数据包顺序要正确

一 停等协议(SW):

发送完一个分组就停止发送,等待对方的确认。在收到确认后再发送下一个分组。

数据在传送过程中会发生哪些损坏?

1.比特差错:数据包的部分比特从0变成了1或者从1变成了0。
2.分组丢失:分组到达一个中转的路由器时,路由器的输入队列已经满了,此时分组就会溢出,即被丢弃。
3.分组乱序:分组没有按照发送的顺序到达接收方。

第一种情况rdt1.0:底层信道完全可信

现在假设底层信道完全可信,即上面笔者所说的三种分组损坏情况都不会发生,那么分组只要直接从发送方通过底层信道送往接收方
接收方也不需要给发送方回应,因为分组准确地到达并且不会发生任何差错

第二种情况rdt2.0:底层信道中分组可能出现比特差错

传输中出现比特差错是非常常见的 因此,发送方需要接收方的确认信息来告诉发送方传送的分组数据是否有差错。当数据无误的时,接收方
发送一个ACK(肯定确认)的回应表示数据没有问题,如果数据错误,则发送一个NAK(否定确认)回应表示数据有问题需要重传。
如何判断数据是否有错:
发送方在发送分组的时候需要为分组计算一个检验和,当分组到达以后,接收方用同样的计算方法对分组进行计算。
将得到的检验和与发送方的检验和进行核对以检验分组数据是否传输出错。

流程如下:

上层通知发送方发送分组数据,发送方将分组数据计算以后得到检验和并放置在头部之中,在发送完分组以后,发送方处于等待接受方回应的状态中。
接收方收到了分组(注意,在该种情况下已经假设分组不会中途丢失,因此接收方一定会接收到分组),检验数据以后:
数据正确则返回ACK。
数据错误则返回NAK。
发送方收到了接收方的反馈信息,此时有两种情况:
接收到了NAK,表明数据有错,因此发送方重传该数据,并处于等待接收方回应的状态中。
接收到了ACK,表明数据正确,发送方继续等待上层的下一次调用通知。

在发送方与接收方的交互中,可以看到使用了差错检测,接收方反馈,重传这三个功能,基于这三个功能以及还有超时功能的可靠数据传输协议被称为ARQ协议

rdt2.1:发送方应对接收方发送的ACK或者NAK出现比特差错

我们看rdt2.0有什么问题,我们知道确认信号也需要通过信道传播,那么如果ACK/NAK的信号发生了错误呢?发送方应该怎么处理?
显然发生了错误,我们就应该重传
但是这里又有一个问题,接收方怎么知道发送方这次传过来的是新的报文段还是因为ack出错而重传的报文段呢?
显然我们需要区分,上一个报文段和当前的报文段,我们给报文段编写好序号就可以了,而且只需要0,1两个序号
一个表示上次的报文段,一个表示新接受的。这样接收方如果收到0,就知道这次不是新的报文段,可能是上次ack出错了
发送方无法确认,就重传了上次的报文段,所以接收方需要丢掉这个报文段,然后再次传一次ack确认信号
如果收到的是序号为1的报文段,则接收方直接接受就可以了。
对比2.0要多做的工作
发送方:
1.为每个分组增加了序列号
2.两个序列号(0, 1)就够用,为什么?
3.需校验ACK/NAK消息是否发生错误
4.状态数量翻倍
5.状态必须“记住”“当前”的分组序列号
接收方:
1.需判断分组是否是重复
2.当前所处状态提供了期望收到分组的序列号
3.注意:接收方无法知道ACK/NAK是否被发送方正确收到

rdt2.2:无NAK消息协议

我们考虑一下我们真的需要两个确认信号ack和nck么? 与rdt 2.1功能相同,但是只使用ACK如何实现?
1.接收方通过ACK告知最后一个被正确接收的分组
2.在ACK消息中显式地加入被确认分组的序列号
3.发送方收到重复ACK之后,采取与收到NAK消息相同的动作重传当前分组

第三种情况rdt3.0:底层信道中出现分组丢失

假设分组有可能被发送方与接收方之间的中转路由器丢弃了,而此时发送方与接收方根本不知道分组被丢弃了,导致双方都陷入了一个死循坏的等待中。
因此,一个简单的解决方法是,发送方需要设置一个定时器,当发送分组的时候开始计时,如果在一定时间内(传播时延+接收方处理分组时间)
没有收到接收方的回馈分组,则重传当前分组。
需要注意的是,由于发送方使用了计时器,所以当发送方收到了当前分组的上一个分组的ACK的时候(即当前分组传输损坏)或者回馈分组损坏的时候
(这两个操作都不会重置计时器),并不会立即发送当前分组,而是等到计时器超时才重新发送当前分组。

二 流水线可靠数据传输协议

在解决了上面三种分组数据损坏的问题后,得到的的确是一个可靠的数据传输协议,但是,上述的可靠数据传输协议采用的是停等协议
这必然造成了效率的低下,不能对链路带宽充分的利用。因此,有没有方法使发送方不断的发送分组,而无需等待发送分组的确认呢?

实现流水线发送分组而无需确认分组,需要做到:

1.增加分组的序号范围,不能简单的使用0和1来作为分组的序号(顺便一提在TCP中分组序号是按照数据的字节顺序给的,并非按照分组排序)。  
2.发送方与接收方都需要有缓存用来存储分组。  
3.提供当分组数据出错,超时,重传的处理方法:选择重传(SR)协议以及回退N步(GBN)协议。  

1.回退N步协议(GBN)

假设在序号空间内,划分一个长度为N的子区间,这个区间内包含了已经被发送但未收到确认的分组的序号以及可以被立即发送的分组的序号
这个区间的长度就被称为窗口长度。(随着发送方方对ACK的接收,窗口不断的向前移动,并且窗口的大小是可变的,因此GBN协议也被称为滑动窗口协议

当上层调用发生时,发送方根据窗口情况变化: 1.如果窗口内已经被发送但未收到确认的分组数目已经达到了窗口长度(此时就没有可以被立即发送的分组的序号了),发送方可以把上层的数据缓存起来或者告诉上层隔一段时间以后再来调用。 2.如果窗口内还有可以分配的立即被发送的分组序号,则为上层的数据分配分组序号并立即发送,更新可以被立即发送的分组序号。

那么,为什么要限制窗口长度为N,而不直接设置窗口长度为整个发送方的缓存长度呢?这是为了给TCP协议提供流量控制的功能(注意,流量控制与差错控制要区分)。

GBN协议还采取了累积确认,当发送方收到一个对分组n的ACK的时候,即表明接收方对于分组n以及分组n之前的分组全部都收到了。

对于超时的触发,GBN协议会将当前所有已发送但未被确认的分组重传,换句话说,如果当前窗口内都是已发送但未被确认的分组
一旦定时器发现窗口内的第一个分组超时,则窗口内所有分组都要被重传。每次当发送方收到一个ACK的时候,定时器都会被重置。

GBN协议对于接收方则相对比较简单,接收方只需要按序接收分组,对于比当前分组序号还要大的分组则直接丢弃。假设接收方正在等待接收分组n,而分组n+1却已经到达了,于是,分组n+1被直接丢弃,正是因为这种处理,所以发送方并不会出现在连续发送分组n,分组n+1之后,而分组n+1的ACK却比分组n的ACK更早到达发送方的情况。 那么,GBN协议对超前到达的分组直接丢弃的做法会不会有点过于浪费呢?大家可以注意一下GBN的超时机制,即使分组n+1已经预先到达了接收方,但只要分组n没有到达接收方,则很有可能导致发送方的定时器超时,而一旦定时器超时,则所有已发送但未被确认的分组都会被重传,其中就包括了分组n+1,因此,接收方只要简单的丢弃提前到达的分组n+1就可以了。

2.选择重传协议(SR)

在了解了GBN协议之后,或许有人对GBN的超时重传机制感到困惑,有必要因为一个分组的超时而重传所有的已发送而未被确认的分组么?
SR协议允许接收方对于超前分组的到达返回ACK,则发送方就会出现在收到分组n的ACK之前接收到分组n+1的ACK的情况。

对于SR协议来说,发送方需要做到:

1.为每一个已发送但未被确认的分组都需要设置一个定时器,当定时器超时的时候只发送它对应的分组。
2.当发送方收到ACK的时候,如果是窗口内的第一个分组,则窗口需要一直移动到已发送但未未确认的分组序号。

接收方需要做到:

1.维护一个接收窗口(注意,在之前的协议之中,接收方都只需要维护当前分组的序号即可)。
2.当分组序号在接收窗口之内的时候,返回该分组的ACK并视情况移动接收窗口,而如果分组序号在分组之前(冗余分组),返回该分组的ACK。

需要注意的是,接收窗口内不能出现两个分组的相同序号,否则接收方无法辨认需要对一个冗余分组的ACK还是对一个新的分组的ACK,
因此,接受窗口长度必须小于或者等于序号空间的一半。