架构

应用层调用rdt_send()->传输层调用udt_send()，指在不可靠的协议上传输（IP协议）->接受方的传输层调用rdt_rcv()->受放的传输层调用deliver_data()将可靠数据发给接收方的应用层

如下图所示：

RDT

RDT 1.0

可靠信道上的可靠数据传输，这是理想信道，不可能实现。

FSM状态

由于是可靠信道，所以发送方和接收方是独立的。

SENDER(发送方)

  • [status]Wait for call from above: 等待上层调用(应用层)
    • [events]rdt_send(data): 上层调用会产生一个rdt_send(data)事件
    • [actions]packet = make_pkt(data): 创建一个packet
    • [actions]udt_send(packet): 发送这个packet

RECEIVER(接收方)

  • [status]Wait for call from below: 等待下层调用(网络层)
    • [events]rdt_rcv(packet)
    • [actions]extract(packet, data): 将packet的数据提取出来
    • [actions]deliver_data(data)

RDT 2.0

在不可靠的信道上的可靠传输。RDT2.0主要解决的位错误，如0翻转为1的错误。主要的手段是校验和(checksum)。所以重点在于如何从错误中恢复过来。

相比于RDT 1.0

  • 差错检测
  • 接收方反馈控制消息: ACK/NAK
  • 重传机制

从错误中恢复

  • 确认机制(Acknowledgements, ACK): 接受方告诉发送方分组正确接受
  • NAK: 接受方告诉发送方分组有误
  • 发送方收到NAK则重传

FSM状态

SENDER(发送方)

  • [status]Wait for call from above: 等待上层调用(应用层)
    • [events]rdt_send(data): 上层调用会产生一个rdt_send(data)事件
    • [actions]snkpkt = make_pkt(data, checksum): 创建一个snkpkt，额外加入校验和
    • [actions]udt_send(snkpkt): 发送这个packet
  • [status]Wait for ACK or NAK: 等待ACK或NAK
    • [events]rdt_rcv(rcvpkt) && isNAK(rcvpkt): 接受接收方发来的消息，并检测到发生了错误
    • [events]rdt_rcv(rcvpkt) && isACK(rcvpkt): 全部正确

RECEIVER(接收方)

  • [status]Wait for call from below: 等待下层调用(网络层)
    • [events]rdt_rcv(rcvpkt) && corrupt(rcvpkt): 接收到分组并且有错误发生
  • [actions] udt_send(NAK): 发送错误消息
    • [events]rdt_rcv(rcvpkt) && uncorrupt(rcvpkt): 接收到分组并且有错误发生
    • [actions]extract(rcvpkt, data): 将packet的数据提取出来
    • [actions]deliver_data(data)
    • [actions]udt_send(ACK)

RDT 2.1

RDT 2.0的缺陷是在ACK和NCK在传输中被破坏的情况下会出现死锁。所以使用分组重传来解决，但是如果上一次ACK被破坏，重传后也被正确接收了，这就会产生分组重复问题，所以需要增加序列号。

相比于RDT 2.0

  • 发送方
    • 为每个分组增加了序列号
    • 需要校验ACK和NAK是否发生错误
    • 状态数量翻倍（由于引入了两个分组）
  • 接收方
    • 需要判断分组是否重复

FSM状态

SENDER(发送方)

现在分组有两个编号0和1

  • [status]Wait for call 0 from above: 等待上层对0分组的调用
    • [actions]sndpkt = make_pkt(0, data, checksum): 加上序号0，其余不变
  • [status]Wait for ACK or NAK 0: 等待分组0的ACK和NAK消息
    • [events]rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt)): 接收到接收方的返回分组并且损坏或者发送错误的情况
    • [actions]udt_send(sndpkt): 重传
    • [events]rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt): 全部正确则转向下一个状态
  • [status]以下与分组0相同 所以省略

RECEIVER(接收方)

  • [status]Wait for 0 from below: 等待下方调用分组0
    • [events]rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && has_seq0(rcvpkt): 收到了分组并且没有被破坏并且就是分组0（完全理想的情况）
    • [actions]sndpkt = make_pkt(ACK, checksum): 返回带有校验和的ACK
    • [events]rdt_rcv(rcvpkt) && currupt(rcvpkt): 分组坏掉
    • [actions]sndpkt = make_pkt(NAK, checksum): 返回带有校验和的NAK
    • [events]rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && has_seq1(rcvpkt): 收到了分组并且没有被破坏但是分组为1
    • [actions]sndpkt = make_pkt(ACK, checksum): 发送ACK

RDT 2.2

取消NAK，在ACK显式的加入最后一个被正确接受的分组序号，所以发送方接收到重复的ACK之后就对应原先的NAK。

FSM状态

RDT 3.0

在RDT 2.0假设的基础上加入可能丢失分组的假设。如果丢失分组就有可能发生死锁，接收方和发送方互相等待，所以这时候可以考虑在等待一定时间后进行重传。

FSM状态

SENDER(发送方)

所有在使用udt_send(pkt)之后都需要执行start_timer来启动定时器，并在下一个状态中增加一个事件timeout，并且在全部正确的情况下增加一个stop_timer来停止定时器的执行。

  • [status]Wait for call X from above
    • [events]rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isACK(rcvpkt, 1)): 接受错误就什么都不做直到过期后重发
    • [events]timeout: 超时
    • [status]udt_send(sndpkt): 重发
    • [status]start_timer: 启动定时器
  • [status]Wait for ACK X
    • [events]rdt_rcv(rcvpkt): 接受到信息

RECEIVER(接收方)

接收方不需要做任何变动。

RDT协议瓶颈

主要瓶颈在于停等上，如下图

传输时延为L/R, 传播时延为RTT, 最终利用率为0.00027, 所以可以看出停等协议的效率很差。

流水线机制

思想：一次多发点。靠滑动窗口协议实现。

要求

  • 更大的序列号
  • 接收方和接收方需要更大的存储区域作为缓存

概要

  • 窗口
    1. 允许使用的序列号范围
    2. 窗口尺寸为N代表最多有N个等待确认的消息
  • 滑动窗口
    随着协议的进行，窗口在序列号空间内向前滑动。
  • 滑动窗口协议
    • GBN
    • SR

GBN(GO-BACK-N)

  • 分组头部包含kbit的序列号，相当于说这里面最大有2^k个序号
  • 窗口尺寸为N，最多允许N个分组没有被ACK确认
  • 当收到ACK(n)说明序列号N及以前的序列号全部被正确接收(1, 2, ..., n-1, n都成功接收了)
  • Timeout(n)重传序号大于等于n并且没有收到ACK确认的全部分组，潜在的会造成资源的浪费

SENDER

针对第6个问题请参见RECEIVER的设计，它每次返回的是被正确接受的最高的序号

RECEIVER

这要求必须顺序到达，如果乱序到达的话会被丢弃。比如expectedseqnum为5，发过来的是7，应该返回的ACK序号为4。

练习

Q: 数据链路层采用后退 N 帧（GBN）协议，发送方已经发送了编号为 0~7 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认。则发送方需要重发的帧数是多少？分别是那几个帧？

A: 根据 GBN 协议工作原理，GBN 协议的确认是累积确认，所以此时发送端需要重发的帧数是 4 个，依次分别是 4、5、6、7 号帧。

SR(Selective Repeat)

GBN的缺陷在于累计确认机制会重复发送很多分组，所以SR就是在GBN的基础上添加了单独确认和缓存。发送方没有什么变化，接收方增加了一个不与发送方窗口同步的窗口。

SENDER

  • data from above: 如果窗口内还有空闲位置，则发送pkt，并且start_timer(n)
  • timeout(n): 重发pkt n, 并且restart_timer(n)
  • ack(n) in [sendbase, sendbase+N]: 如果是现在窗口中最小的序列号，则base移动到下一个unACK的序列号上；如果不是最小的序列号，则仅标记为被接受

RECEIVER

  • pkt n in [rcvbase, rcvbase+N-1]: send_ack(n)。如果是乱序到达的就缓存；如果正常到达就移动到下一个没有被确认的序列号处。
  • pkt n in [rcvbase-N, rcvbase-1]: 这说明在发送ACK的过程中可能没有接收到，发送方timer超时重发造成的，此时只需要send_ack(n)
  • 其他情况忽略即可

问题

在序列号和窗口的长度过于相近的话，可能会造成识别问题，所以在窗口尺寸上需要做验证。假设现在序列号共有k个，发送方窗口为Ns，接收方窗口为Nr，则应满足Ns+Nr<=2^k