计算机网络-可靠数据传输的原理

工程
Created At :
  1. rdt1.0: 可靠信道上的数据传输
  2. rdt2.0: 信道会出现比特差错
  3. rdt2.1: ACK/NAK出现差错
  4. rdt2.2: NAK-free
  5. rdt3.0: 分组/ACK可能出现丢失
  6. 流水线协议
    1. Go-back-N protocol
    2. Selective Repeat protocol

可靠数据传输算法是一个状态机算法.

rdt1.0: 可靠信道上的数据传输

rdt1.0假设下层信道完全可靠, 不会出现比特丢失/差错, 那么发送方与接收方的状态机表示如下:

rdt1.0

当上层调用接口rdt_send进行可靠数据传输时, Sender状态机会改变状态, 执行make_packet和udt_send.

接收方收到数据后, 会改变状态, 执行extract和deliver.

rdt2.0: 信道会出现比特差错

当下层信道会出现比特差错时, 状态机算法需要提供错误检测和恢复机制.

  • 错误检测可以通过checksum实现.
  • 恢复机制可以通过ACK机制实现.

描述该算法的FSM如下, 其中发送方有两个状态:

rdt2.0

0表示等待上层调用rdt_send接口, 1表示等待接收方发过来的ACK/NAK.

对于发送方, 当上层调用rdt_send接口时, 发送方会用make_packets和udt_send发送数据, 然后进入状态1等待接收方的ACK/NAK.

对于接收方, 它会把收到的数据进行一个检测, 如果成功就发ACK, 如果不成功就发NAK.

对于发送方, 如果收到ACK就转移到状态0, 等待上层再次调用, 如果收到NAK就再次发送数据.

rdt2.1: ACK/NAK出现差错

如果信道传输的ACK/NAK会出现差错, 那么FSM需要提供特殊的机制进行处理, 算法如下图所示:

rdt2.1

发送方的几个状态表示如下:

  • 0: 等待上层调用(此时发送的packet的序号是0).

  • 1: 等待ACK/NAK.

  • 2: 等待上层调用(此时发送的packet的序号时1).
  • 3: 等待ACK/NAK.

算法的简要描述如下:

当发送方发送packet后, 会等待ACK/NAK.

接收方接收到packet后, 会检查两件事:

  • packet本身有没有错, 如果有错, 就发NAK, 如果没错, 继续检查:
  • packet序号和自身状态编号是否符合, 如果不符合, 会发ACK (不符合的情况只会出现在: 发送方没有收到自己上一次发送的ACK, 这时候再发一次就好了, 让发送方知道自己已经收到了), 如果符合, 就会转移状态.

rdt2.2: NAK-free

在rdt2.1的基础上, 用上一个packet的ACK代替本次packet的NAK.

  • 也就是说, 假设编号是i的packet出错了, 接收方会发送ACK i-1, 来代替NAK i.

rdt3.0: 分组/ACK可能出现丢失

发送方再发送一个packet后会启动一个定时器timer, 如果超时会重新发送packet, 接受到packet后会重启timer.

状态机表示如下:

rdt3.0

其中, 发送方的状态表示为:

  • 0: 等待上层调用, packet编号为0.
  • 1: 等待ACK0.
  • 2: 等待上层调用, packet编号为1.
  • 3: 等待ACK1.

发送方发送packet0后, 会启动定时器, 然后等待ACK0.

如果收到了ACK0, 则进入状态2, 如果超时, ACK出现错误, 或者收到了ACK1, 那么就继续重发并重启定时器.

接收方如果收到了没有出错, 并且编号对的packet, 就发送对应的ACK, 否则就发送上一个packet的ACK表示自己没收到正确的packet.

流水线协议

上面的rdt协议都是停止等待协议(Stop-and-Wait protocol), 最典型的特征就是发送方发送packet后, 会进入等待ACK的状态.

流水线协议是指发送方在没得到接收方确认的情况下能一次发送多个packet的协议.

流水线协议有如下设置:

  • 发送方和接收方都有一个buffer, buffer的大小就表示一次性能发送的packet的个数.
  • 发送方缓冲区里有一个sliding window, 在sliding window里的元素是发送方发送了但是没确认的packet.
    • 每发送一个分组, 就把这个分组enqueue到sliding window中.
    • 每接收到一个分组的ACK, 就把这个分组dequeue出sliding window.
  • 接收方缓冲区里也有一个sliding window, 在sliding window中的元素表示接收方可以接收的packet.
    • 如果收到一个分组, 这个分组的编号在sliding window中, 返回对应的ACK.
      • 如果这个分组是sliding window的队头, 那么dequeue, 重复, 这个过程直到发送方没有收到队头的packet.

Go-back-N protocol

对于GBN协议, 发送方buffer大小大于1, 接收方buffer大小等于1.

假设接收方的sliding window指向了编号是i的packet, 那么只有正确收到了packet i, 接收方才能发送ACK i, 并且sliding window向后滑, 其他情况下需要发送ACK i-1.

核心: GBN协议是累积确认, 也就是说, 如果GBN协议给发送方ACK i, 证明i及其之前的packet都收到了.

Selective Repeat protocol

对于SR协议, 发送方buffer大小大于1, 接收方buffer大小大于1, 并且两个窗口默认大小相等.

SR协议是一个一个单独确认, 来一个packet, 如果在接收方sliding window中, 就直接发ACK.

SR协议虽然是乱序确认, 但是将数据交付上层是按照顺序的.

©2023 LiGaOg

Built with Hexo and 3-hexo theme