架构
应用层调用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, 所以可以看出停等协议的效率很差。
流水线机制
思想:一次多发点。靠滑动窗口协议实现。

要求
- 更大的序列号
- 接收方和接收方需要更大的存储区域作为缓存
概要
- 窗口
- 允许使用的序列号范围
- 窗口尺寸为N代表最多有N个等待确认的消息
- 滑动窗口
随着协议的进行,窗口在序列号空间内向前滑动。
- 滑动窗口协议
- GBN
- SR
GBN(GO-BACK-N)
- 分组头部包含
k
bit的序列号,相当于说这里面最大有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