可靠数据传输——rdt

rdt在应用层、传输层和数据链路层都很重要

我们将：
渐增式地开发可靠数据传输协议（rdt）的发送方和接收方
只考虑单项数据传输（但控制信息是双向流动的）
双向的数据传输问题实际上是2个单向数据传输问题的综合
使用有限状态机（FSM）来描述发送方和接收方

Rdt1.0（在可靠信道上的可靠数据传输）

假设：下层的信道是完全可靠的
没有比特出错
没有分组丢失

发送方和接收方的FSM：
发送方将数据发送到下层信道
接收方从下层信道接收数据

Rdt1.0 什么都不做，只封装解封装

Rdt2.0（具有比特差错的信道）

下层信道可能会出错：将分组中的比特翻转
使用校验和来检测比特差错

如何从差错中恢复：

• 确认（ACK）：接收方显式地告诉发送方自己分组已被正确接收
• 否定确认（NAK）：接收方显式地告诉发送方分组发生了差错
  发送方收到NAK后，发送方重传分组

rdt2.0中的新机制：采用差错控制编码进行差错检测
发送方差错控制编码、缓存
接收方使用编码检错
接收方的反馈：控制报文（ACK，NAK）：接收方->发送方
发送方收到反馈相应的动作

rdt2.1（发送方处理出错的ACK/NAK）

如果ACK/NAK出错：发送方不知道接收方发生了什么事情。
需要引入新的机制——序号

处理重复：
发送方在每个分组中加入序号
如果ACK/NAK出错，发送方重传当前分组
接收方丢弃（不发给上层）重复分组

停等协议：
发送方发送一个分组，然后等待接收方的应答。

rdt2.2（无NAK协议）

功能同rdt2.1，但只使用ACK（不使用NAK）

接收方对最后正确接收的分组发ACK，以替代NAK（接收方必须显式地包含被正确接收分组的序号）

当收到重复的ACK（如，再次收到ACK0）时，发送方与收到NAK采取相同的动作：重传当前分组

为后面的一次发送多个数据单位做准备：
一次能够发送多个
每一个的应答都有：ACK，NACK——麻烦
使用对前一个数据单位的ACK，代替本数据单位的nak
确认信息减少一半，协议处理简单

rdt3.0（具有比特差错和分组丢失的信道）

下层信道可能会丢失分组（数据或ACK）：
会死锁；
机制还不够处理这种状况：检验和，序列号，ACK，重传

方法：发送方等待ACK一段合理的时间
发送端超时重传：如果到时没有收到ACK就重传
问题：如果分组（或ACK）只是被延迟了（重传将会导致数据重复，但利用序列号已经可以处理这个问题；接收方必须指明被正确接收的序列号）
需要一个倒计数定时器

rdt3.0的性能

rdt3.0 停-等操作

流水线——提高链路利用率

当发送窗口sw大于1，是流水线协议

流水线 协议：
允许发送方在未得到对方确认的情况下一次发送多个分组

• 必须增加序号的范围：用多个bit表示分组的序号
• 在发送方/接收方要有缓冲区
  发送方缓冲：未得到确认，可能需要重传
  接收方缓存：上层用户取用数据的速率 不等于 接收到的数据速率；接收到的数据可能乱序，排序交付（可靠）

有两种通用的流水线协议：

• 退回N步（GBN）——接收窗口rw = 1
• 选择重传（SR）——接收窗口rw > 1

滑动窗口协议

发送窗口

发送缓冲区：
形式：内容中的一个区域，落入缓冲区的分组可以发送
功能：用于存放已发送，但没有得到确认的分组
必要性：需要重发时可用

发送缓冲区的大小：一次最多可以发送多少个未经确认的分组
停止等待协议 = 1；
流水线协议>1，合理的值，不能很大，链路利用率不能够超过100%

发送缓冲区中的分组：
未发送的：落入发送缓冲区的分组，可以连续发送出去
已经发送出去的、等待对方确认的分组：发送缓冲区的分组只有得到确认才能删除

发送窗口是发送缓冲区的一个子集。
发送窗口的最大值<=发送缓冲区的值


发送窗口后沿移动：
条件——收到老分组的确认
结果——发送缓冲区罩住新的分组，来了新的分组可以发送
移动的极限——不能超过前沿

接收窗口

接收窗口尺寸wr = 1，只能顺序接收（GBN）
接收窗口尺寸wr < 1，可以乱序接收（SR）

落在接收窗口内的序号可以被接受；在窗口之外则被丢弃

GBN：累计确认（每次发送当前接收到的最大的ACK）
SR：非累计确认（只要落在窗口内，来一个，确认一个ACK）

滑动条件：
低序号分组到来，窗口滑动
高序号分组到来，缓存但不交付（不允许失序），不滑动

发送接收窗口互动

正常情况

异常情况GBN

超时，发送方把窗口中所有分组都发出去

异常情况SR

重新发送没有收到确认的分组本身

窗口的最大尺寸

例如：n = 2（n表示用几个比特位对发送数据序列编号，此处是0～3，所以可用2个比特位代表），序列号：0，1，2，3
可以得到
GBN = 3；
SR = 2；

GBN和SR对比

使用范围：
GBN：出错率低，出错罕见，没必要用复杂的方法
SR：链路容量大（延迟大、带宽大），容易出错