可靠数据传输（rdt）的原理★★ ★ ★ ★
background：
rdt在应用层、传输层和数据链路层都很重要
是网络Top 10问题之一
信道的不可靠特点决定了可靠数据传输协议（ rdt ）的复杂性
rdt所要面临的问题(也是人面临的问题) ：
==在下层提供的服务不可靠的情况下， 本层的协议机制、协议实体要通过哪些时空资源的安排、要靠哪些机制的安排，要向上层提供可靠的服务。==
可靠数据传输： 问题描述
图片中的
rdt_send() 和 deliver_data( ) 是本层和上层的接口
udt_send() 和 udt_rcv( ) 是本层协议实体 跟下层的原语的形式
原语：上层使用下层服务的形式
底层的可靠性与否决定了上层rdt的复杂性。
逻辑的理解过程：
- 渐增式地开发可靠数据传输协议（ rdt ）的发送方和接收方
- 只考虑单向数据传输 - 但控制信息是双向流动的！
- 双向的数据传输问题实际上是2个单向数据传输问题的综合
- 使用有限状态机 (FSM) [描述协议工作状态的转移之类的]来描述发送方和接收方
Rdt1.0： 在可靠信道上的可靠数据传输
1.下层的信道是完全可靠的
- 没有比特出错
- 没有分组丢失
1.发送方和接收方的FSM
- 发送方将数据发送到下层信道
- 接收方从下层信道接收数据
1.发送方发送package
2.接收方接收后，校验是否出错， 如果不出错那么就发送一个控制报文（ACK），发送方就不用做什么了
3.如果出错， 那么就发送一个控制报文（NCK）, 然后发送方再将副本传输过去（检错重传）
Rdt2.0：具有比特差错的信道
Rdt1.0 的问题 ：
- 下层信道可能会出错：将分组中的比特翻转 。可以用校验和来检测比特 差错
- 怎样从差错中恢复：
Rdt2.0 的改进：
采用差错控制编码进行差错检测
- 发送方差错控制编码、缓存
- 接收方使用编码检错
- 接收方的反馈：控制报文（ACK，NAK）：接收方->发送方
- 发送方收到反馈相应的动作
有限状态机（FSM）描述：
1.发送方发送package
2.接收方接收后，校验是否出错， 如果不出错那么就发送一个控制报文（ACK），发送方就不用做什么了
3.如果出错， 那么就发送一个控制报文（NCK）, 然后发送方再将副本传输过去（检错重传）
Rdt2.0： 没有差错时的操作
rdt2.0：有差错时
rdt2.0的致命缺陷！-> rdt2.1
如果ACK/NAK出错？发送方该如何？
发送方不知道接收方发 生了什么事情！ 然后也不知道如果操作
如何处理：
引入新的机制 ： 序号 （有点麻烦，因为要发送两次确认是否重复）
- 发送方在每个分组中加 入序号
- 如果ACK/NAK出错，发送方重传当前分组
- 接收方丢弃（不发给上 层）重复分组
如果发送方出错 ：
停止等待协议： 发送方发送一个分组， 然后等待接收方的关于这个分组的应答
如果ACK/NAK出错，接收方如何处理？
必须检测接收到的分组 是否是重复的
注意：接收方并不知道 发送方是否正确收到了 其ACK/NAK
发送方：
- 在分组中加入序列号
- 两个序列号（0，1）就 足够了
- 一次只发送一个未经确认的分组
- 必须检测ACK/NAK是否 出错（需要EDC ）
- 状态数变成了两倍
- 必须记住当前分组的序列 号为0还是1
接收方：
- 必须检测接收到的分组 是否是重复的
状态会指示希望接收到的 分组的序号为0还是1
注意：接收方并不知道 发送方是否正确收到了 其ACK/NAK
没有安排确认的确认
如果说本次发送出错了 。然后接收方就给出 nak， 但是发送方没有停止等待继续发送错误的，因为要实现重复校验， 所以发送方将下一次的data发送过去了 ，结果就是接收方需要0 ， 但是你发送了个1。
所以 上述的问题还是难以解决。我们就需要引入2.2
rdt2.1的运行
接收方不知道它最后发送的ACK/NAK是否被正确地收到
- 发送方不对收到的ack/nak给确认，没有所谓的确认的确认；
- 接收方发送ack，如果后面接收方收到的是：
- 老分组p0？则ack 错误
下一个分组？P1，ack正确
rdt2.2：无NAK的协议
- *功能同rdt2.1，但只使用ACK(ack 要编号）*
- 接收方对最后正确接收的分组发ACK，以替代NAK
- 接收方必须显式地包含被正确接收分组的序号
- 当收到复的ACK（如：再次收到ack0）时，发送 方与收到NAK采取相同的动作：重传当前分组
- 为后面的一次发送多个数据单位做一个准备
- 一次能够发送多个
每一个的应答都有：ACK，NACK；麻烦
使用对前一个数据单位的ACK，代替本数据单位的nak
确认信息减少一半，协议处理简单
==就相当于如果出现错误， 接收方不返回NCK， 而是返回上一次的ACK。(你要这次的结果， 但是这次的结果是出错的。 所以我只能返回你上一次的正确结果咯。 所以由于停止等待协议， 这次的结果没有返回，那么就得重新放， 知道返回本次得ACK)==
rdt2.2的运行
rdt2.2bug：发送方和接收方片断
rdt3.0：具有比特差错和分组丢失的信道
新的假设：下层信道可 能会丢失分组（数据 或ACK）
- 会死锁
- 机制还不够处理这种 状况： • 检验 和 • 序列号 • ACK • 重传
超时重传机制：
方法：发送方等待ACK一段 合理的时间
链路层的timeout时间确定的 传输层timeout时间是适应式的
- 发送端超时重传：如果到时没有 收到ACK->重传
- 问题：如果分组（或ACK ）只 是被延迟了：
- 重传将会导致数据重复，但 利用序列号已经可以处理这 个问题
接收方必须指明被正确接收 的序列号
- 需要一个倒计数定时器
之前得2.0 我们知道
(你要这次的结果， 但是这次的结果是出错的。 所以我只能返回你上一次的正确结果咯。 所以由于停止等待协议， 这次的结果没有返回，那么就得重新放， 知道返回本次得ACK)
对于3.0 来说 ，他不会立马就重放本次结果， 他会等待不同（等着超时定时器的启动） 。超时定时器启动之后就会将再一个时间段内重放本次。
相对2.0 来说就是反应慢了点而已，其他没啥了
rdt3.0的运行
（c）超时定时器丢失
（d）情况就是超时计数器设置不合理
rdt3.0的性能
rdt3.0可以工作，但链路容量比较大的情况下，性能很差
- 链路容量比较大，一次发一个PDU 的不能够充分利用链路的传输能力
例题
上述也就是 99%的时间都是空的 ， 只有 0.00027%的时间才是在干正事。可想而知利用率是非常非常低的。
停等操作
停止等待协议 在局域网的场景下（往返反应是比较低 ，容量较小）一次发一个。
但是如果是长途的链路（链路容量非常大），此时一次只发送一个那么就是杀鸡用牛刀，且非常低效。那么就需要一次发送多个未经确认的分组。而且需要对这个分组做一个长比特的编号。 （这样才能区分不同的分组）。—-这种能一次发送多个未确认分组的协议叫流水线协议
流水线：提高链路利用率
流水线协议—（提高链路利用率）
作为一个缓冲区：
目的是 发送方 发送的速率 和 接收方接收的速率是不一致的。
需要有一个缓冲来对抗这两者的速度不一致性。（就像从高速公路到市里的路段 需要过一个安检口一样）
我们把一次能够发送多个未经确认分组的协议叫做流水线协议
流水线：允许发送方在未得到对方确认的情况下一次发送多个 分组
- 必须增加序号的范围:用多个bit表示分组的序号
- 在发送方/接收方要有缓冲区
• 发送方缓冲：未得到确认，可能需要重传；
• 接收方缓存：上层用户取用数据的速率≠接收到的数据速率；接收到的数据可 能乱序，排序交付（可靠）
两种通用的流水线协议：回退N步(GBN)和选择重传(SR)
通用：滑动窗口(slide window)协议
发送方和接收方的窗口不一致。
1.发送缓冲区
- 形式：内存中的一个区域，落入缓冲区的分组可以发送
- 功能：用于存放已发送，但是没有得到确认的分组
- 必要性：需要超时重发时可用
1.发送缓冲区的大小：一次最多可以发送多少个未经确认的分组（上限）
- 停止等待协议=1
- 流水线协议 > 1，合理的值，不能很大，链路利用率不能够超100%
1.发送缓冲区中的分组
- 未发送的：落入发送缓冲区的分组，可以连续发送出去；
- 已经发送出去的、等待对方确认的分组：发送缓冲区的分组只有得到确认 才能删除
发送窗口滑动过程-相对表示方法
- 采用相对移动方式表示，分组不动
- 可缓冲范围移动，代表一段可以发送的权力
图中的粉红色就是一个已发送但是未确认的窗口，两三个连在一块就构成了这个发送缓冲窗口的范围。
- ==发送窗口==：发送缓冲区内容的一个范围
- ==那些已发送但是未经确认分组的序号构成的空间==
- 发送窗口的最大值<=发送缓冲区的值
- 一开始：没有发送任何一个分组
- 后沿=前沿
- 之间为发送窗口的尺寸=0
- 每发送一个分组，前沿前移一个单位
发送窗口前沿移动的极限：不能够超过发送缓冲区
发送窗口后沿移动 就是发送窗口的移动
条件：收到老分组的确认
结果：发送缓冲区罩住新的分组，来了分组可以发送
移动的极限：不能够超过前沿
发送窗口的滑动
还得多听几遍：
1.发送滑动窗口
接收窗口 (receiving window)=接收缓冲区
接收窗口用于控制哪些分组可以接收；
• 只有收到的分组序号落入接收窗口内才允许接收
• 若序号在接收窗口之外，则丢弃；
接收窗口尺寸Wr=1，则只能顺序接收；
接收窗口尺寸Wr>1 ，则可以乱序接收
• 但提交给上层的分组，要按序
接收滑动窗口
接收窗口的滑动和发送确认
滑动：
• 低序号的分组到来，接收窗口移动；
• 高序号分组乱序到，缓存但不交付（因为要实现rdt，不允许失序），不滑动
发送确认：
• 接收窗口尺寸=1 ； 发送连续收到的最大的分组确认（累计确认）
• 接收窗口尺寸>1 ； 收到分组，发送那个分组的确认（非累计确认
正常情况下的2个窗口互动
发送窗口
有新的分组落入发送缓冲区范围，发送->前沿滑动
来了老的低序号分组的确认->后沿向前滑动->新的分组可以落入发送缓冲区的范围
接收窗口
- 收到分组，落入到接收窗口范围内，接收
- 由于是低序号 ，所以发送确认给对方
发送端上面来了分组->发送窗口滑动->接收窗口滑动->发确认
异常情况下GBN(一种协议)的2窗口互动
异常情况的说明：
- 传输的分组在传输过程中出现了错误或者丢失
- 接收方给的ACK 确认没有给到发送方
发送窗口
- 新分组落入发送缓冲区范围，发送->前沿滑动
- 超时重发机制让发送端将发送窗口中的所有分组发送出去
- 来了老分组的重复确认->后沿不向前滑动->新的分组无法 落入发送缓冲区的范围（此时如果发送缓冲区有新的分组 可以发送）
接收窗口
收到乱序分组，没有落入到接收窗口范围内，抛弃
（重复）发送老分组的确认，累计确认；
异常情况下SR（一种协议）的2窗口互动
异常说明 ：
分组是乱序的到达接收方。
发送窗口
每发送一个，发送方就需要启动一个超时定时器， 哪个倒是就重新发送那个
- 新分组落入发送缓冲区范围，发送->前沿滑动
- 超时重发机制让发送端将超时的分组重新发送出去
- 来了乱序分组的确认->后沿不向前滑动->新的分组无法落 入发送缓冲区的范围（此时如果发送缓冲区有新的分组可 以发送）
接收窗口
- 收到乱序分组，落入到接收窗口范围内，接收。 然后关闭定时超时计数器
- 发送该分组的确认，单独确认；
- GBN协议和SR协议的异同
不同之处：
- ==SR协议 大致就是那个分组超时了 ， 就单独发送那个分组。而GBN协议 则是， 如果某个分组超时了， 会将它的滑动窗口中的所有已发送、未发送的分组全部重新发送一边==
相同之处:
- 发送窗口>1
- 一次能够可发送多个 未经确认的分组
流水线协议：总结★★★★
Go-back-N 协议：
- 发送端最多在流水线 中有N个未确认的分 组
- 接收端只是发送累计 型确认cumulative ack
- 接收端如果发现gap， 不确认新到来的分组
- 发送端拥有对最老的 未确认分组的定时器
- 只需设置一个定时器
- 当定时器到时时，重 传所有未确认分组
GBN：发送方扩展的FSM
GBN：接收方扩展的FSM
只发送ACK：对顺序接收的最高序号的分组
- 可能会产生重复的ACK
- 只需记住expectedseqnum；接收窗口=1
• 只一个变量就可表示接收窗口
对乱序的分组：
- 丢弃（不缓存）
- 在接收方不被缓存！
- 对顺序接收的最高序号的分组进行确认-累计确认
运行中的GBN★★★★★★
这个图再加上老师的讲解 基本可以透彻的理解一丝了。
选择重传
Selective Repeat 协议
- 发送端最多在流水线中 有N个未确认的分组
- 接收方对每个到来的分 组单独确认individual ack（非累计确认）
- 发送方为每个未确认的 分组保持一个定时器
- 当超时定时器到时，只是 重发到时的未确认分组
选择重传SR
1.接收方对每个正确接收的分组，分别发送 ACKn（非累积确认）
- 接收窗口>1 • 可以缓存乱序的分组
- 最终将分组按顺序交付给上层
1.发送方只对那些没有收到ACK的分组进行重 发-选择性重发
- 发送方为每个未确认的分组设定一个定时器
1.发送窗口的最大值（发送缓冲区）限制发送 未确认分组的个数
选择重传SR的运行★★★★★★
这个图再加上老师的讲解 基本也可以透彻的理解一丝了。
对比GBN和SR
适用范围
- 出错率低：比较适合GBN，出错非常罕见，没有必 要用复杂的SR，为罕见的事件做日常的准备和复杂 处理
- 链路容量大（延迟大、带宽大）：比较适合SR而不 是GBN，一点出错代价太大
