Table Of Contents

在实际的网络传输中，channel（信道）是不可靠的，在其上传输的数据分组可能丢失，损坏，或者失序。因此需要一个可靠的数据传输协议，来保证从发送端发送的数据能够按序无损地交付给接收端。图中，应用层将传输协议视为可靠的；而在传输层中，通过可靠数据传输协议，在不可靠的网络层信道上，实现了数据的可靠传输。下面开始讲解可靠数据传输协议的完善过程。

1. 经完全可靠信道的可靠数据传输 rdt 1.0

假设信道完全可靠，从发送端发送的数据会按序，无损，不丢失地交付到接收端。

在发送端：

  1. rdt_send(data) 接受来自高层的数据
  2. make_pkt(data) 将数据分组
  3. udt_send(packet) 将分组发送到信道

在接受端：

  1. rdt_rcv(packet) 从信道接受数据分组
  2. extract(packet ,data) 从分组中取出数据
  3. deliver_data(data) 将数据上传给较高层

在这种情况下，接受端不需要反馈任何信息给发送端，因为数据一定会按序无损到达。

2. 经具有比特容差错信道的可靠数据传输 rdt 2.0

底层信道更为实际的模型是分组中的比特可能受损，我们假定即使数据受损，分组也会不丢失地到达。

在这种情况下，由于信道会造成数据差错，为了使分组能无差错、按序传输，则需要

  • 差错检测：接收端需要检测出数据在哪里出错了，比如在分组首部中加入校验和字段
  • 接收方反馈：接收端要告诉发送端，某个分组的数据在传输过程中出错了。数据没错就发送ACK(肯定确认)，数据错了就发送NAK(否定确认)
  • 重传：发送端收到接受端的反馈后，要将出错的分组重传

我们假设，接收方反馈的信息，ACK 或 NAK 只需要 1 bit大小，而且在传输过程中不会损坏，丢失。也就是说，发送方一定会按序收到正确的反馈。

在发送端：

  1. rdt_send(data) 接受来自高层的数据
  2. make_pkt(data,checksum) 将数据分组并将用于差错检测的校验和信息写入分组首部
  3. udt_send(sndpkt) 将分组发送到信道
  4. rdt_rcv(rcvpkt) 接收从接收方发来的反馈信息。若为肯定确认isACK(rcvpkt)，则本次传输完成，继续等待上层的调用；若为否定确认isNAK(rcvpkt)，则说明数据出错，因此要重传数据，然后等待反馈结果，即重复本步骤。

在接收端

  1. rdt_rcv(rcvpkt) 接收分组，然后判断数据是否损坏
  2. corrupt(rcvpkt)若数据损坏，则通过make_pkt(NAK)生成否定的反馈信息sndpkt
  3. uncorrupt(rcvpkt)若数据未损坏，则extract(packet ,data) 从分组中取出数据，然后deliver_data(data) 将数据上传给较高层。并则通过make_pkt(ACK)生成肯定的反馈信息sndpkt
  4. 发送反馈信息udt_send(sndpkt)

2.1 经具有比特容差错信道的可靠数据传输 rdt 2.1 （解决ACK或NAK受损）

这样貌似可以解决数据受损问题了，然而，我们还没有考虑到ACK 或者 NAK 数据受损的情况。问题的根源在于，如果一个ACK 或 NAK分组受损，发送方就无法知道接收方是否正确接收了上一次发送的分组。面对受损分组时，假若发送方重传之前的分组，那么当受损分组为ACK时，会造成分组冗余；假若将其视为ACK，接着发送下一个分组，倘若受损分组为NAK，又会造成分组缺失。那么遇到受损反馈分组时，发送方应当怎样处理呢？

有这样一个方法：发送方遇到受损反馈分组时，一律重传；在接收端判断该分组是否已经成功接收。那么接收端该怎么判断呢？

我们假定信道不丢失分组，只会发生分组受损情况，分组能不丢失地到达接收端。为了保证分组无损坏、按序传输，我们在分组中添加一个新的字段，让发送方对其数据进行编号（0,1,0,1交替进行编号）。这样，接收方就能通过分组的编号来判断收到的分组是属于上一个分组的重传（编号与上一个分组的编号相同），还是下一个新的分组（编号与上一个分组的编号不同）。

发送方有限状态机描述图：

过程如下：

  1. 等待并接受上层调用，在数据分组首部添加编号0，(make_pkt(0,data,checksum))。并将分组发入信道
  2. 等待接收方的反馈信息，收到反馈信息后
    • 若信息受损或者是NAK，则按照原编号重传分组，回到步骤2
    • 若是ACK，进入步骤3。
  3. 等待并接受上层调用，在数据分组首部添加编号1，(make_pkt(1,data,checksum))。并将分组发入信道.
  4. 等待接收方的反馈信息，收到反馈信息后
    • 若信息受损或者是NAK，则按照原编号重传分组，回到步骤4
    • 若是ACK，进入步骤1。

接收方有限状态机描述图：

过程如下：

  1. 等待编号为0的分组到达。接受分组，抽取出数据以及编号
    • 若分组损坏，发送NAK，重复步骤1
    • 若编号为1，发送ACK，重复步骤1
    • 若编号为0，则将数据发给上层，发送ACK，进入步骤2
  2. 等待编号为1的分组到达。接受分组，抽取出数据以及编号
    • 若分组损坏，发送NAK，重复步骤2
    • 若编号为0，发送ACK，重复步骤2
    • 若编号为1，则将数据发给上层，发送ACK，进入步骤1

接收端接收到冗余分组时，仍要发送ACK，以便于发送端发送下一个分组。但是接受到的冗余数据会被舍弃，并不会再次传给上层。

2.2 经具有比特容差错信道的可靠数据传输 rdt 2.2 （无NAK）

NAK 只在接受端遇到受损分组时发送，其实我们可以舍弃NAK。利用分组的编号，在遇到受损分组时，发送ACK，并附带上一次成功接受的分组对应的序号。发送端接受ACK后，将其序号与当前要发送的分组序号相比，就知道要重传还是发送新的分组了。

发送方有限状态机描述图：

过程如下:

  1. 等待并接受上层调用，在数据分组首部添加编号0，并将分组发入信道。
  2. 等待接收方的反馈信息，收到反馈信息后，提取出对应的编号。
    • 若信息受损或者是ACK 1，则按照原编号重传分组，回到步骤2
    • 若是ACK 0，进入步骤3。
  3. 等待并接受上层调用，在数据分组首部添加编号1，并将分组发入信道。
  4. 等待接收方的反馈信息，收到反馈信息后，提取出对应的编号
    • 若信息受损或者是ACK 0，则按照原编号重传分组，回到步骤4
    • 若是ACK 1，进入步骤1。

接收方有限状态机描述图：

  1. 等待编号为0的分组到达。接受分组，抽取出数据以及编号
    • 若分组损坏，或若编号为1，发送ACK1，重复步骤1
    • 若编号为0，则将数据发给上层，发送ACK 0，进入步骤2
  2. 等待编号为1的分组到达。接受分组，抽取出数据以及编号
    • 若分组损坏，或若编号为0，发送ACK0，重复步骤2
    • 若编号为1，则将数据发给上层，发送ACK1，进入步骤1

3. 经具有比特差错的丢包信道的可靠数据传输 rdt 3.0

上述分析中，我们假设信道可以出现比特差错，但是分组会不丢失地到达接收方。而在实际情况中，发送方发送的分组可能会丢失（比如被路由器丢弃），下面分析怎么监测到分组的丢失，以及怎么重传丢失的分组。

当分组丢失时，发送方会一直等待接收方的反馈信息，而接收方也会一直等待新的分组到来，这样以来，系统就没办法工作了。因此，我们可以在发送方设置一个定时器，估计一下发送方与接收方之间数据的往返时延，每当发送一个分组时，就启动定时器，若超过预定的时间值，发送方则重传分组。对于发送方，不知道是发送的数据丢失还是ACK丢失，那么重传就是万能灵药了；对于接收方，不管数据有没有丢失，收到冗余分组时丢弃即可。

发送方有限状态机描述图：（接收方与rdt 2.2 相同）

过程如下:

  1. 等待并接受上层调用，在数据分组首部添加编号0，并将分组发入信道，启动定时器。
  2. 等待接收方的反馈信息。
    • 若超时，则按照原编号重传分组，启动定时器，回到步骤2。
    • 若未超时，收到反馈信息后，提取出对应的编号。
      • 若信息受损或者是ACK 1，则按照原编号重传分组，回到步骤2
      • 若是ACK 0，关闭定时器，进入步骤3。
  3. 等待并接受上层调用，等待过程中可能还会收到接收方发来的数据，忽略之。接受上层发来的数据后，在数据分组首部添加编号1，并将分组发入信道，启动定时器。
  4. 等待接收方的反馈信息。
    • 若超时，则按照原编号重传分组，启动定时器，回到步骤4。
    • 若未超时，收到反馈信息后，提取出对应的编号。
      • 若信息受损或者是ACK 0，则按照原编号重传分组，回到步骤4
      • 若是ACK 1，关闭定时器，进入步骤5。
  5. 等待并接受上层调用，等待过程中可能还会收到接收方发来的数据，忽略之。在数据分组首部添加编号0，并将分组发入信道，启动定时器，进入步骤2。

发送方只要在发送分组时就会启动定时器，只有接受到正确的ACK时才会关闭定时器。

为什么在等待上层调用时还会收到接收方的反馈信息呢？因为接收方在超时后发送了冗余分组，这些分组并没有丢失，而是延迟到达接收方。

基于rdt 3.0协议的数据传输运行示意图：

4. 流水线可靠数据传输协议

我们从rdt 1.0一步步演变到rdt 3.0, 已经实现了一个经具有比特差错的丢包信道的可靠数据传输协议，此协议已经可以在现实生活中真实的信道上面运行了。然而由于该协议是停等协议，也就是必须成功接收到接收方的反馈信息，才能传递下一个分组（不论是传递新分组还是重传）。这样虽然能很好地保证分组能按序到达接收端，但是数据传输效率十分低下，每次传输都至少要等待一个往返时延（Round-Trip Time）。那么怎么才能加快传输速率呢？

可以使用流水线技术，也就是发送端可以同时发送多个分组到信道中，不需要依次等待上一个分组确认到达之后再发送下一个分组。当然，万事有利也有弊，尽管改善了传输速率，但是也有一些弊端：

  • rdt 3.0的比特交替分组编号方式不再合适，要增加编号范围。
  • 分组可能会失序到达，双方都需要建立缓冲区。由于会有多个分组同时在信道中传输，分组很可能会失序到达接收方，因此接收方要缓存失序到达的分组；分组也很可能会失序地要求重传，故发送方也需要缓存已发送但未确认的分组。

那么，在流水线情况下，怎么处理数据的丢失、损坏、失序和超时到达呢？目前有退回N步（Go Back N）和选择重传（Selective Repeat）两种处理方式。

4.1 退回N步(Go Back N)

发送的分组会被依次编号，发送端会记录哪些分组已经被成功接收。对于分组序号的管理如下：

最早未确认的分组编号为base，最小未使用序号为nextseqnum，将所有分组分为四个区段：

  • [0, base-1] 表示已经发送并被确认的分组
  • [base, nextseqnum-1] 表示已发送但是未确认
  • [nextseqnum, base+N-1] 表示能用于那些要立即被发送的分组
  • 大于base+N 的分组不能用，因为未被确认的分组数最多为N。

当base对应的分组被确认之后，窗口才会向右移动。N被称为窗口长度。限制窗口长度是要进行流量控制与拥塞控制。

序号怎么分配确定之后，序号的范围怎么定呢？一般序号会承载在分组首部的一个固定的字段中，序号范围由字段大小k进行确定，为[0,2k-1]。当序号用完之后，进行取模运算，从头开始编号。

发送端的有限状态机描述图

初始情况下，base=1, nextseqnum=1。发送方要响应三个事件：

  1. 上层的调用。此时要检查窗口是否已满，也就是比较nextseqnum与base+N
    • 若已满，则将数据返回给上层，表示窗口已满，然后上层会等会儿再试。在实际过程中，发送方更可能会缓存这些数据，或者使用同步机制，只允许上层在窗口未满时才调用rdt_send()
    • 若未满，则产生一个分组，并发送到信道。然后递增nextseqnum。若此时只有该分组未确认，则开启定时器。
  2. 收到发送方反馈。若反馈受损，则什么都不用做，继续等待反馈。若收到一个序号为K的ACK，由于接收方采用累计确认，则表示K以及其之前的分组以及成功被接收。故把base置为K+1，若此时base=nextseqnum则表示所有分组都已经确认了，那么就关掉定时器，等待上层调用发送数据。若还有分组未确认，则重启定时器。整个过程中只使用了一个定时器，它被视为最早的已发送但未被确认的分组的定时器。
  3. 超时事件。当超时时间发生时，GBN协议会重传所有已发送但未被确认的分组。协议的名字退回N步就是来源于此。

对于接收方，有限状态机描述图

接收方采用累计确认，数据要按序交付。它会丢弃到所有的失序分组，比如它期待接受序号为k的分组，而序号为k+1的分组却先到达了，此时接收方会丢弃该分组（或者缓存），并发送ACK k。所以当它发送ACK N时，则表示N以前的分组都已经成功接收。累计确认由expectedseqnum进行控制。接收方不需要维护接收缓冲区，只需要丢弃到失序分组即可。此方法虽然简单，但是会导致更多的分组重传。

GBN传输示意图

4.2 选择重传(Selective Repeat)

GBN协议虽然使用流水线提高了传输速率，但是仍会引起一些性能问题。当窗口长度与信道时延都比较大时，一旦信道中的某个分组丢失或者超时，则会引起大量分组重传。而接收方的累计确认机制，也会丢弃很多有用的分组而造成重传。

选择重传是对退回N步协议的改进，即发送方只会重传那些它怀疑在接收方出错（丢失或受损）的分组从而避免不必要的重传。同时，接收方也不会盲目地丢失失序的分组，而是将其缓存起来。

发送方的事件与动作：

  1. 从上层接收到数据。当从上层接收到数据之后，发送方判断窗口是否已满，若未满就将数据打包发送；若已满，则像GBN一样，要么将数据缓存，要么将其返回给上层。
  2. 超时。SR中，每个分组都会有一个独立的定时器，因为超时发送之后，只会重传一个分组。
  3. 收到反馈信息。若反馈信息受损，则丢弃之。未受损，则从中提取出分组序号。若分组序号在发送窗口内，则将该分组标记为已确认。若该分组刚好是send_base，则将窗口移动到最小号的未确认分组处。如果窗口移动了，而且有待发送的分组（缓存的）落在窗口内，则发送之。

SR的接收方与GBN不同，当接收到未受损的失序分组时，会将其缓存起来。直到缺失的分组到来，与之形成一个连续的分组序列，才将整个序列按序交付给上层。接收方的事件与动作如下：

  1. 在[rcv_base, rcv_base+N-1]内的分组被正确接收，此时会返回对应序号的ACK给发送方。若该分组未之前未接收，则缓存之；若已接收，则丢弃之。若该分组恰好为rcv_base，则按序依次交付已确认的分组给上层，并同时移动rcv_base,在未确认的分组处停下。
  2. 在[rcv_base-N , rcv_base-1]内的分组被正确接收，必须返回一个对应序号的ACK
  3. 其它情况,直接丢弃之。

为啥在第二部还要发送已经确认过的分组对应过的ACK呢？还有，为什么是当前窗口左侧N个分组需要确认，而更久以前的不需要呢？考虑这种情况：

大量的分组成功地从发送方无损到达接收方，接收方也发送了对应的ACK。然而由于从接收方到发送方的信道丢包严重，导致大量的ACK都没有成功到达发送方。超时之后，发送方只好重传分组。极端情况下，接受方已经确认了所有N个分组，然而接受方却连一个无损的ACK都没有收到。此时，rcv_base-send_base=N，之后，发送方重传的分组到达了，要是不再次发送对应的ACK，那么发送方就会永远重传下去了。故发送方需要从当前窗口左侧N个分组处开始重复确认成功接受的分组。

结合上图以及上述示例，可以发现，发送方与接收方的窗口并不是同步的。因为ACK也会在信道中出错。

4.3 窗口长度与分组序号空间的关系

窗口长度为3，序号空间为[0,3]

上图的两种情况，发送方发送的最后一个分组到达接收方后，接收方都无法分辨这是第一个分组重传的数据还是第五个分组的初次重传。导致混乱的原因是，窗口长度与序号空间太接近了，序号空间很快就用完并回到起点，这时窗口中会有冲突序号。

对SR协议而言，窗口长度必须小于或等于序号空间大小的一半。

5. 总结

  • rdt1.0: 假设分组按序、无错、无丢失到达。不需要接收端反馈。
  • rdt2.0: 假设分组无丢失到达，可能会出现错误。接收端使用ACK与NAK来进行错误恢复，假设ACK与NAK分组不会出错。停等，保证按序到达。
    • rdt2.1: ACK与NAK可能出错。发送方遇到受损反馈分组时，一律重传；对分组交替编号，接收端根据编号判断是否为重传分组。
    • rdt2.2: 不使用NAK。接收端用ACK+编号代替NAK，发送端根据编号识别是否需要重传。
  • rdt3.0: 假设分组可能丢失、出错。发送方使用定时器来处理丢失，丢失后则重传。
  • 流水线协议：同时发送多个分组，不采用停等协议。需要解决分组失序问题。
    • 退回N步：接收端采用累积确认避免失序，发送端维护发送窗口，只使用一个定时器，超时则全部重传未确认分组。
    • 选择重传：发送端、接收端分别维护一个窗口；每个分组都有一个独立的定时器，单个确认。