可靠数据传输 rdt 学习

0x00前言

各种新的研究都刚刚开始,没东西发了,就来说说rdt的内容吧,rdt全称为可靠数据传输协议(Reliable Data Transfer)。可靠数据传输的实现问题不仅在运输层出现,也会在链路层以及应用层出现,但是可靠数据传输协议的下层协议也许是不可靠的,因此这也是一项困难的任务。

 

0x01 经完全可靠信道的可靠数据传输 rdt 1.0

我们考虑最简单的情况,即第层信道是完全可靠的,我们称协议为rdt1.0,该协议本身是简单的。图中显示了rdt1.0发送方和接受方的有限状态机(Finite-Sate Machine,FSM)的定义。图中的sender中的FSM定义了发送方的操作。发送方和接受方有各自的FSM。图中的发送方和接收方的FSM每个都只有一个状态。FSM描述图中的箭头指示了协议从一个状态变迁到另一个状态.(因为图中每个FSM都只有一个状态,因此变迁必定是从一个状态返回到自身)。引起变迁的时间显示在表示变迁的横线上方,时间发生时所采取的动作显示在横线下方。如果对一个时间没有动作,或没有事件发生而采取了一个动作,我们将在横线上方或下方使用符号 Λ ,以分别明确地表示缺少的动作。FSM的初始状态用虚线表示。

rdt的发送端只通过rdt_send(data)时间接受来自较高层的数据,产生一个包含该数据的分组(经由make_pkt(data)动作),并将分组发送到信道中。实际上,rdt_send(data)事件是由较高层应用的过程调用产生的,例如(rdt_send())。

在接收端,rdt通过rdt_rcv(packet)事件从底层信道接受一个分组,从分组中取出数据(经由extract(packet, data)动作),并将数据上传给较高层(通过deliver_data(data)动作)。实际上, rdt_rcv(packet)事件是由较底层协议的过程调用产生的(例如,rdt_rcv())。

在这个简单协议当中,一个单元数据与一个分组没差别。而且,所有分组是从发送方流向接受方;有了完全可靠的信道,接收端就不需要提供任何反馈信息给发送方,因为不必担心出差错。但同时注意到我们也已经假定了接受方接受数据的速率能够与发送方发送的速率一样快,因此,接受方没有比要请求发送方慢一点。

 

0x02 经具有比特差错信道的可靠数据传输: rdt2.0

底层信道更为实际的模型是分组中的比特可能受损的模型。在分组传输、传播或缓存的过程,这种比特差错通常会出现在网络的物理部件中。在研发一种经这种信道进行可靠信道的协议之前,首先考虑一下如何处理这类的情景。通常情况下报文接收者在听到、理解并借下每句话之后可能会说"OK"。如果报文接收者听到一句含糊不清的话时,他可能要求你重复那句容易误解的话。这种口述报文协议使用了肯定确认(positive acknowlegment)("OK")与否定确认(negative acknowlegment)("请重复一遍")。这些控制报文使得接收方可以让发送方知道哪些内容被正确接收,哪些内容接受有误并因此需要重复。在计算机网络环境中,基于这样的重传机制的可靠数据传输协议称为自动重传请求(Automatic Repeat reQuest,ARQ)协议.

同时,ARQ协议中还需要另外三种协议功能来处理存在比特差错的情况:

  • 差错检验。首先,需要一种机制以使接收方检测到何时出现了比特差错。
  • 接收方反馈。因为发送方和接收方通常在不同的系统上执行,可能相隔数千英里,发送方要了解接收方情况(此时为分组是否被正确接收)的唯一途径就是让接收方提供明确的反馈信息给发送方。理论上,这些分组只需要一个比特长;如用0表示NAK,用1表示ACK
  • 重传。接收方收到有差错的分组时,发送方将重传该分组文。

图中说明了rdt2.0的FSM,该数据协议采用了差错检测,肯定确认与否定确认。

rdt2.0的发送端有两个状态。在最左边的的状态中,发送端协议正在等待来自上层下来的数据。当rdt_send(data)事件出现时,发送方将产生一个包含待发送数据的分组,带有检验和,然后经由udt_send(sndpkt)操作发送该分组。在最右边的状态中,发送方协议等待来自接收方的ACK或NAK分组。如果收到一个ACK(符号rdt_rcv(rcvpkt)&&isACK(rcvpkt)对应事件),则发送方知道最近发送的分组已经被正确接收,因此协议返回到等待来自上层的数据的状态。如果收到一个NAK分组,该协议重传上一个分组并等待接收方为响应重传分组而回收的ACK或NAK。

当发送方处于等待ACK或NAK的状态时,它不能从上层获得更多的数据;这就是说,rdt_send()事件不可能出现;仅当接收到ACK并离开该状态的时才能发生这样的事件。因此,发送方将不会发送一块新的数据,除非发送方确信接收方已正确接收当前的分组。由于这种行为,rdt2.0这样的协议被称为停等协议

rdt2.0接收方的FSM仍然只有单一状态。当分组达到时,接收方要么回答一个ACK,要么回答一个NAK,这取决于收到的分组是否受损。图中符号rdt_rcv(rcvpkt)&&corrupt(rcvpkt)对于应于收到一个分组并发现有错的事件。但此时,rdt2.0存在一个致命问题,我们没有考虑到ACK和NAK分组受损的可能性,如果一个ACK或者NAK分组受损,发送方无法知道接收方是否正确接收了上一块发送的数据。

处理受损的ACK和NAK可能有如下的3中可能性:

  1. 考虑在口述报文情况下人可能的做法。如果说话者不理解来自接收方回答的"OK"或"请重复一遍",说话者将可能问"你说什么?"。接收方则将复述其回答。但是如果说话者的"你说什么?"产生差错,接收者不明白那句混淆的话是口述内容的一部分还是一个要求重复上次回答的请求,很可能回一句"你说什么?"。于是,该回答可能含糊不清了。
  2. 增加足够的检验和比特,是发送方不仅可以检测差错,还可以恢复差错。对于会产生差错但不丢失分组的信道,这就可以直接解决问题。
  3. 当发送方收到含糊不清的ACK或NAK分组时,只需要重传当前数据分组即可。然而,这种方法在发送方到接收方的信道中引入了冗余分组(duplicate packet)。冗余分组的根本困难在于接收方不知道它上次所发送的ACK或NAK是否被发送方正确地收到。因此它无法事先知道接收到地分组是新地还是一次重传!

因此我们的解决方法实在数据分组中添加一新字段,让发送方对其数据分组编号,即将发送数据分组的序号(sequence number)放在该字段。于是,接收方只需要检查序号既可确定收到的分组是否是一次重传。对于停等协议这种简单的情况,1比特组后了,因为它可以让接收方知道发送方是否正在重传前一个发送分组(接收到的分组序号与最近收到的分组序号相同),或是一个新分组(序号变化了,用模2运算“前向移动”)。因为如果假定信道不丢分组,ACK和NAK分组本身不需要指明他们要确认的分组序号。发送方知道所接受到的ACK和NAK分组是为响应其最近发送的数据分组二生成的

0x03 更准确的rdt2.0:rdt2.1

rdt2.1的发送方和接收方FSM的状态数都是以前的两倍。因为协议状态此时必须反应出目前(有发送方)正发送的分组或(在接收方)希望接收的分组的序号是0还是1.发送或期望接收0号分组的状态中的动作与发送或期望接收1号分组的状态中的动作与发送或期望接收1号分组的状态中的动作是相似的;唯一的不同是序号处理的方法不同。

rdt2.1使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时,接收方对所接收的的分组发送一个肯定确认。如果收到受损的分组,则接收方将发送一个否定确认。如果不发送NAK,而是对上次正确接受的分组发送一个ACK,我们也能实现与NAK一样的效果。发送方接收到对同一个分组的两个ACK(即接收冗余ACK(dunplicate ACK))后,就知道接收方没有正确接收到分在被确认两次的分组后面的分组。

0x04 具有确认分组序号的rdt2.1:rdt2.2

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

0x05经具有比特差错的丢包信道的可靠数据传输:rdt3.0

现在假定除了比特受损之外,底层信道还会丢包,协议现在必须处理另外相关的两个问题:怎样检测丢包以及发生丢包后该做些什么,这里让发送方负责检测和恢复丢包工作。假定发送方传输一个数据分组,该分组或直接接受该分组的ACK发生了丢失。在这种情况下,发送方都收不到应当到来的接收方的响应。如果发送方愿意等待足够长的事件以便确定分组已丢失,则它只需要重传该数据分组即可。

发送方至少需要等待这样长的时间,即发送方与接收方之间的一个往返时延(可能会包括在中间路由器的缓冲时延)加上接收方处理一个分组所需的时间。确定的因素非常多,等待一个最坏情况的时延可能意味着要等待一个较长的时间,知道启动差错恢复为止。因此,发送方一般采取选择一个时间值,以判定可能发生了丢包(尽量不能确保)。如果在这个时间内没有收到ACK,则重传该分组。注意到如果一个分组经历了一个特别大的时延,发送方可能重传该分组,即使该数据分组及其ACK都没有丢失,这就在发送方到接收方的信道中引入了冗余数据分组(duplicate data packet)的可能性。

为了实现基于时间的重传机制,需要设置一个倒计时定时器(dountdown timer),在一个给定的时间量过期之后,可中断发送方。因此发送方需要做到:

  1. 每次发送一个分组(包括第一次分组和重传分组)时,便启动一个定时器。
  2. 响应定时器中断(采取适当的动作)。
  3. 终止定时器

图中给出了rdt3.0的发送方FSM,这是一个在可能出错和丢包的信道上可靠数据传输的协议。

 

在下图中,时间从图的顶部朝底部移动;注意到一个分组的接收时间必定迟于一个分组的发送时间,这是因为发送时延于传播时延之故。在b~d中,发送方括号部分报名了定时器的设置时刻以及随后的超时。因为分组序号在0和1之间交替,因此rdt3.0有时被称为比特交替协议(alternating-bit protocol)

现在在检验和、序号、定时器、肯定和否定确认分组这些技术中,每种机制都在协议的运行中起到了必不可少的作用。至此,我们得到了一个可靠数据传输。

Reference

  • 计算机网络(自顶向下)第7版