可靠数据传输的基本原理
# 可靠数据传输的基本原理
什么是可靠?
- 不错
- 不丢
- 不乱
可靠数据传输依靠可靠数据传输协议(rdt)
- 可靠数据传输对应用层、传输层、链路层都很重要
- 网络 Top-10 问题
- 信道的不可靠特性决定了可靠数据传输协议的复杂性
# 可靠数据传输协议
- 从服务提供者的角度来看
- 单向调用可靠数据传输协议即可
- 从服务实现的角度来看
- 在不可靠的信道上实现可靠的数据传输
- 需要双向控制数据的流动
- 在不可靠的信道上实现可靠的数据传输
🌟可靠数据传输协议基本结构:接口
示意图
后续研究过程
- 渐进地设计可靠数据传输协议的发送方和接收方
- 只考虑单向数据传输
- 但控制信息双向流动
- 利用有限状态机(Finite State Machine, FSM)刻画传输协议
状态机示意图
event
事件action
采取的行动
# Rdt1.0: 可靠信道上的可靠数据传输协议
底层信道完全可靠
- 不会发生错误(bit error)
- 不会丢弃分组
发送方和接收方的FSM独立
状态机示意图
sender
rdt_send
- 应用层调用,传送
data
- 应用层调用,传送
make_pkt
- 创建分组
udt_send
- 发送分组
receiver
deliver_data
- 向应用层传送
data
- 向应用层传送
# Rdt2.0
# Rdt2.0: 产生位错误的信道
底层信道可能翻转分组中的位(bit)
- 可以利用校验和检测位错误
- 具体会在第 5 章中介绍
如何从错误中恢复过来
- 确认机制(Acknowledgements,ACK)
- 接收方显式地告知发送方分组已正确接收
- NAK
- 接收方显式地告知发送方分组有错误
- 发送方收到 NAK 后,重传分组
基于这种重传机制的 rdt 协议称为 ARQ(Automatic Repeat reQuest) 协议
Rdt2.0 中引入的新机制
- 差错检测
- 接收方反馈控制消息: ACK/NAK
- 重传
# Rdt2.0: FSM规约
停--等协议
sender
示意图
- 需要对分组进行缓存
receiver
示意图
Rdt2.0 无错误场景
示意图
Rdt 2.0: 有错误场景
示意图
# Rdt2.1
Rdt2.0 的缺陷: ACK/NAK 消息发生错误/被破坏(corrupted)
- 解决方案
- 为 ACK/NAK 增加校验和,检错并纠错
- 纠错的难度高,有代价
- 发送方收到被破坏 ACK/NAK 时不知道接收方发生了什么,添加额外的控制消息
- 不能从根本上解决问题,因为额外的控制消息也可能发生错误
- 如果 ACK/NAK 坏掉,发送方重传
- 但是简单的重传会产生重复分组
- 如前一次传送成功,但
ACK
发送错误
- 如前一次传送成功,但
- 但是简单的重传会产生重复分组
- 为 ACK/NAK 增加校验和,检错并纠错
解决重复分组的方案
- 序列号(Sequence number):
- 发送方给每个分组增加序列号
- 接收方丢弃重复分组
发送方的 FSM
接收方的 FSM
Rdt2.1 Vs Rdt 2.0
- 发送方
- 为每个分组增加了序列号
- 由于采用了停-等协议,所以两个序列号(0, 1)就够用
- 需要校验ACK/NAK消息是否发生错误
- 状态数量翻倍
- 状态必须记住当前的分组序列号
- 接收方
- 需要判断分组是否重复
- 当前所处状态提供了期望收到分组的序列号
- 注意:接收方无法知道 ACK/NAK 是否被发送方正确收到
- 需要判断分组是否重复
# Rdt2.2
无 NAK 消息协议
实现方法
- 与rdt 2.1功能相同,但是只使用ACK
- 接收方
- 接收方通过ACK告知最后一个被正确接收的分组
- 在ACK消息中显式地加入被确认分组的序列号
- 发送方
- 发送方收到重复ACK之后,采取与收到NAK消息相同的动作
- 重传当前分组
- 发送方收到重复ACK之后,采取与收到NAK消息相同的动作
Rdt2.2 的 FSM
# Rdt 3.0
信道即可能发生错误,也可能丢失分组
- 校验和 + 序列号 + ACK + 重传 无法处理分组可能丢失的问题
解决方案
- 发送方等待合理时间
- 如果没收到ACK,重传
- 如果分组或ACK只是延迟而不是丢了
- 重传会产生重复,序列号机制能够处理
- 接收方需在ACK中显式告知所确认的分组
- 需要定时器
发送方 FSM
Rdt 3.0 工作的典型场景
- Operation with no loss
点击查看
- lost packet
点击查看
- lost ACK
点击查看
- premature timeout
点击查看
Rdt 3.0 的性能分析
- 软硬件协同设计
- 有效吞吐量为 267 kbps
# 流水线可靠数据传输协议
流水线机制
- 允许发送方在收到ACK之前连续发送多个分组
- 更大的序列号范围
- 发送方和/或接收方需要更大的存储空间以缓存分组
# 滑动窗口协议
- 滑动窗口协议: GBN, SR
# GBN(Go-Back-N) 协议
GBN: 扩展 FSM
- 发送方扩展 FSM
点击查看
- 接收方扩展 FSM
点击查看
GBN 示例
# SR(Selective Repeat) 协议
SR 协议的特点
- 接收方对每个分组单独进行确认
- 设置缓存机制,缓存乱序到达的分组
- 发送方只重传那些没收到 ACK 的分组
- 为每个分组设置定时器
- 发送方窗口
- N 个连续的序列号
- 限制已发送且未确认的分组
发送方/接收方窗口
SR 协议示例
SR 协议:困境
- 序列号空间大小与窗口尺寸需要满足:
k
为分组序号字段的比特数
编辑 (opens new window)