以下全文为《计算机网络 自顶向下方法》(第8版) 3.4小节的总结。
rdt: reliable data transfer
udt: unreliable data transfer
下方有限状态机图片中横线上方表示事件event,下方表示操作action。
因信道可靠,所以发送方只有一个状态:等待来自上层的调用。当发生rdt_send(data)事件时,即被上层调用时,将数据分组并发送。
同样地,接收方只有一个状态:等待来自下层的调用。当发生rdt_rcv(data)事件时,即被下层调用时,将数据提取出来,并传输给上层。
考虑底层信道会出现比特差错的情况,即传输过程中0变成1,1变成0这种错误。此时,接收方会给发送方发送一条确认信息。如果接收到的数据是正确的,则发送ACK,如果是错误的,则发送NAK。如果发送方接收到NAK,则重发这个数据。在计算机网络环境中,基于这样重传机制的可靠数据传输协议称为自动重传请求协议(Automatic Repeat reQuest, ARQ)。ARQ协议需要另外三种协议功能来处理存在比特差错的情况:差错检测、接收方反馈、重传。
如下图所示,此时发送方有两种状态:等待上层调用和等待ACK或者NAK。假设初始状态为等待上层调用。那么当发生rdt_send(data)事件时,发送方将数据分组,此时报文中还添加了检验和(checksum),然后将报文发送。然后发送方的状态转移到等待ACK或NAK。在这个状态下,如果发生rdt_rcv(rcvpkt)事件,并且rcvpkt中包含NAK,那么重新发送报文,并停留在该状态,直到接收到的rcvpkt中包含ACK,使得状态转移回等待上层调用。此时不进行任何操作,因此横线下方用Λ表示。
值得注意的是,当发送方处于等待ACK或NAK状态时,不接受来自上层的调用。因此rdt2.0被称为停等协议(stop-and-wait)。
此时,接收方还是只有一个状态:等待来自下层的调用。当发生rdt_rcv(data)事件,并且接收到的报文有差错,则发送NAK。如果接收到的报文没有差错,则提取数据并向上传输,以及发送ACK。
rdt2.0存在一个致命的缺陷:如果接收方发送给发送方的ACK或者NAK受损,怎么办呢?假设发送方接收到不明确的ACK的话也重传,那么对于接收方而言,它分不清接收到的数据是重传(它发送过ACK确认的)还是新的数据。
处理这个问题的一种简单方法是在数据分组中添加一个新字段,让发送方对其数据分组编号。将数据分组的序号也一起发送过去。通过序号,接收方就可以分得清数据是重传的还是新的。
对于停等协议,1bit序号就足够了。下图是rdt2.1发送方的状态机。因为加上了1bit序号,因此发送方有四种状态。假设等待来自上层调用0是初始状态,当rdt_send(data)事件发生时,将数据分组,并且此时除了检验和之外,还加入了序号0,然后发送报文。发送方状态转移到等待0的ACK或者NAK状态。在此状态下,当rdt_rcv(rcvpkt)事件发生,并且接收到的数据受损或者数据中包含NAK,则重传数据,并停留在该状态。如果接收到的数据没有受损并且其中包含ACK,则转移到等待来自上层调用1的状态。其余状态和事件同理。
下图是rdt2.1接收方的状态机。接收方有两种状态:等待下层调用0和等待下层调用1。以等待下层调用0为例,当rdt_rcv(rcvpkt)事件发生,并且rcvpkt没有受损以及rcvpkt中有序号0,那么提取数据,并传输给上层,给发送方返回ACK和检验和,接收方状态转移为等待下层调用1。
此外,在等待下层调用0状态时,当rdt_rcv(rcvpkt)事件发生,并且rcvpkt受损了,那么给发送方给回NCK和检验和,状态停留在这里。
当rdt_rcv(rcvpkt)事件发生,并且rcvpkt没有受损以及rcvpkt中有序号1,那么意味着不是接收方想要的数据,仍停留在这个状态,给发送方返回ACK和检验和。
从上面的分析可见,在rdt2.1中,序号和ACK/NAK其实是冗余的,只要有ACK和序号就够了,不需要有NAK。因此rdt2.2就把NAK去掉了。其发送方和接收方的状态机如下图所示。
除比特受损外,底层信道还会丢包。针对丢包问题,引入一个定时器。发送方做到:
- 每次发送一个分组(包括第一次分组和重传分组)时,启动一个定时器;
- 响应定时器中断;
- 终止定时器。
rdt3.0的发送方的状态机如下图所示。与rdt2.2一样有四种状态。当处于等待上层调用0的状态时,发生rdt_send(data)事件,那么发送方将数据分组,加入序号0和检验和。然后将分组发送,并启动定时器。状态转移到等待ACK0。但是如果在等待上层调用0的状态时,发生rdt_rcv(rcvpkt)事件,则不进行任何操作,因为是停等协议。
当处于等待ACK0的状态时,发生rdt_rcv(rcvpkt)事件,并且rcvpkt有损坏或者其中包含序号1的ACK,则仍停留在这个状态,不进行任何操作。如果发生超时事件(timeout),则重传报文并重新启动定时器。但仍停留在该状态。如果发生rdt_rcv(rcvpkt)事件,并且报文没有损坏以及其中包含序号0的ACK,那么停止定时器,并转移到等待上层调用1的状态。
其他两个状态同理。
rdt3.0的接收方的状态机与rdt2.2接收方的状态机相同。
停等协议会严重降低信道的利用率,因为大部分时间发送方都处于等待ACK的状态。解决问题的方法是不以停等方式运行,允许发送方发送多个分组而无须等待确认。这种技术被称为流水线。流水线技术对可靠数据传输协议带来如下影响:
- 必须增加序号范围,因为每个输送中的分组(不计算重传的)必须有一个唯一的序号,而且也许有多个在输送中的未确认报文。
- 协议的发送方和接收方两端也许不得不缓存多个分组。发送方最低限度应当能缓冲那些已发送但没有确认的分组。接收方也需要缓存那些已正确接收的分组。
- 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。解决流水线的差错恢复有两种基本方法:回退N步和选择重传。
关于GBN,可以先看两个动图。
GBN1
GBN2
可见,通过基序号(base)、下一个序号(nextseqnum)和窗口长度N,将发送方的缓存划分为四个部分,如下图所示。GBN也因为被称为滑动窗口协议。
GBN发送方的FSM状态图如下图所示。当上层调用rdt_send(data)时,发送方首先检查发送窗口是否已满:if(nextseqnum < base + N)。如果窗口已满,发送方只需将数据返回给上层,隐式地指示上层该窗口已满。如果窗口未满,则产生一个分组并将其发送,并相应地更新变量。
当收到一个ACK时,在GBN协议中,对序号为n的分组的确认采用累积确认的方式。表明接收方已正确接收到序号n及前面的所有分组了。如果收到一个ACK,但仍有已发送但未被确认的分组,则定时器被重新启动。如果没有已发送但未被确认的分组,则停止该定时器。
当发生超时事件,发送方重传所有已发送但还未被确认的分组。
GBN接收方的FSM状态图如下图所示。如果一个序号为n的分组被正确接收到,并且是按序接收的,则接收方为分组n发送一个ACK,并将该分组中的数据部分交付给上层。除此之外,接收方丢弃该分组,并为最近按序接收的分组重新发送ACK。此处值得注意的是,如果分组k被正确收到,意味着分组k前面的分组都已经被正确接收了。
3.4.4 选择重传(selective repeat, SR)
可先通过以下两个动图,对比着观察GBN的问题,以及SR的特点
GBN
SR
可以发现,GBN会导致单个分组的差错引起重传大量分组,许多分组根本没必要重传。随着信道差错率的增加,流水线可能会被这些不必要重传的分组所充斥。而SR仅让发送方重传那些它怀疑在接收方出错的分组,从而避免了不必要的重传。
首先来看下SR接收方做了哪些改变,如下图所示。SR接收方将确认一个正确接收的分组而不管其是否有序。失序的分组将被缓存直到所有丢失分组(即序号更小的分组)皆被收到为止,这时才将一批分组按序交付给上层。
因此,接收方的事件与操作如下:
- 当序号在[rcv_base, rcv_base+N-1]内的分组被正确接收时,一个选择ACK返回给发送方。如果该分组以前没有收到过,则缓存该分组。如果该分组的序号等于接收窗口的基序号,则该分组以及前面缓存的序号连续的分组交付给上层。
- 当序号在[rcv_base-N, rcv_base-1]内的分组被正确接收时,一个选择ACK返回给发送方。
- 除上述外的其他事件,都忽略该分组。
发送方的事件与操作如下:
- 当从上层接收到数据时,检查下一个可用于该分组的序号。如果序号位于发送方的窗口内,则将数据打包并发送;否则将数据返回给上层或缓存起来。
- 当发生超时事件时,现在每个分组都有其自己的定时器了,因此超时事件发生后,单独重传这个分组。
- 当接收到ACK时,若该分组的序号在窗口内,则将这个分组标记为已接收。如果该分组的序号等于send_base,则窗口滑动到具有最小序号的未确认分组处,如果窗口移动后,窗口内有未发送的分组,则发送这些分组。
关于SR,值得注意的是,窗口长度必须小于或等于序号空间的一半。即如果窗口长度是N,序号空间是M,那么N<M/2,否则会发生接收方不知道发送方发送的是前一个序号K的分组,还是后一个序号K的分组。
标签:重传,ACK,可靠,发送,3.4,分组,序号,数据传输,接收 From: https://www.cnblogs.com/larissa-0464/p/18501493