可靠传输协议
网络情况错综复杂, 并不能确保每一份数据都能准确地送达. 但是某些应用确实需要可靠的数据传输. 因此在不可靠的信道上建立可靠的传输是有必要探究的.
Reliable Data Transfer 可靠数据传输协议 RDT 为此诞生. RDT 并不是传输层独有的, 它更像是一种设计思想, 任何类似情况都可以使用这种设计思想. 所以 RDT 本身可能有一些不完善或者不完美的地方, 这是正常的.
首先应该明确发送方和接收方 rdt 这一层应该做什么.
发送方应该是上层将信息传递给 RDT, RDT 经过包装后交给下层运输.
对于接收方就是反过来, RDT 从下层获取数据, 处理后交给上层.
rdt1.0
先假定一个最理想的情况, 信道是完全可靠的, 永远不丢失或传输错误, 并且发送方的发送速度和接收方的接收速度是相同的.
这种情况就很简单了, 发送方上层调用时 rdt 包装好发给接收方, 接收方从下层接收数据后, rdt 处理数据并传给上层, 因为信道是可靠的, 不需要跟发送方说收到没有, 一定收到了.
双方的状态及状态转移
此时双方 rdt 层都只有一个状态：
- 发送方：等待上层调用
- 接收方：等待下层调用
这里可以把它们当作是一个 有限状态机 (FSM).
有限状态机（英语：finite-state machine, 缩写：FSM）又称有限状态自动机（英语：finite-state automaton, 缩写：FSA）, 简称状态机, 是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型. -- wiki
有限状态机的相关概念可以查阅wiki
在这里只需要简单了解就行, 有限状态机有一个有限数量的状态集合, 并且可以根据外部输入进行状态的转移. 此外, 还有动作, 类似事件监听, 在进入/退出某状态等执行某个操作, 动作有很多类型, 这只是一个例子.
rdt1.0 的状态迁移是比较简单的：
状态集合
发送方：等待上层调用
接收方：等待下层调用
状态转移
发送方
- 等待上层调用状态
发送方接收到上层调用, 接收并处理数据后将数据交给下层发送, 然后继续等待上层调用状态
接收方
- 等待下层调用状态
接收方接收到下层调用, 接收并处理数据后将数据交给上层使用, 然后继续等待下层调用状态
rdt1.0 是不考虑并发调用的.
rdt2.0
自动重传请求协议
在实际的网络环境中, 是很有可能发生错误的. 简单点的可能就是某一位或者某几位出错了, 严重点可能整个包都丢了.
rdt2.0 中假设信道有可能发生比特出错, 但是数据包依旧是有序发送并接收.
为了让接收方知道数据包错了, 发送方需要在数据包里加上校验和让接收方校验或者通过别的差错检测技术, 在这里不讨论, 只需知道接收方有办法判断有无出错.
这里假设一个简单的现实场景, 一个人在信号不好的地方打电话点外卖：
顾客：“汉堡”
店长：“好的”
顾客：“xx”
店长：“你说什么”
顾客：“可乐”
在这个场景中, 店长听到顾客的信息就回复, 不管有没有听错.
如果没听错：回复好的, 然后顾客继续说
如果听错了：回复你说什么, 然后顾客重复上一句话
在 rdt2.0 中, 要求接收方接收到了信息就一定要回应, 不管信息有没有损坏.
没有损坏, 回复 ACK, 然后发送方继续发送
损坏了, 回复 NAK, 然后发送方重复发送上一份信息
这里的 ACK 是肯定确认, NAK 是否定确认. 在计算机网络环境中, 基于这样的重传机制的可靠数据传输协议叫 自动重传请求(ABQ)协议 .
ABQ 协议依赖这三种协议功能：
- 差错检测
需要一种机制来让接收方知道数据有没有错
- 接收方反馈
接收方需要让发送方知道是继续发还是重复发
- 重传
接收方收到有错误的分组, 发送方将重传该分组
双方的状态及状态转移
状态集合
再来看发送方和接收方的状态, 可以发现
发送方：等待上层调用、等待 ACK/NAK
接收方：等待下层调用
接收方的状态还是只有一种, 发送方的状态多了一个等待 ACK/NAK.
状态转移
发送方
- 等待上层调用
发送方在等待上层调用状态中, 接收到上层调用, 然后处理数据并交给下层发送, 进入等待 ACK/NAK 状态
- 等待 ACK/NAK
发送方接收到 ACK/NCK, 如果是 ACK, 那么进入等待上层调用状态；如果是 NAK, 那么将上一份数据交给下层发送, 进入等待 ACK/NAK 状态
接收方
跟 rdt1.0 一致
停等协议
注意这里当且仅当发送方处于等待上层调用时, 上层才能调用. 因此, 在等待 ACK/NAK 状态时, 是不可能有新数据发送的, 直到发送方确认接收方已经正确接收当前分组. 由于这种行为, rdt2.0 这样的协议被称为 停等协议 .
停等协议无疑是低效的, 因为它一次只能发送一次数据, 要发送新数据就只能等上一次发送完成. 跟 HTTP/1.1 类似, 会有队头阻塞的情况.
rdt2.1
rdt2.0 为了确保接收端能接收到正确的信息引入了 ACK/NAK, 要求接收端发送. 那么如果接收端发送的 ACK/NAK 也出错了呢？这就是 rdt2.1 讨论的情况.
假如说 ACK/NAK 的发送也采用重传的话, 那么就会遇到这种情况.
顾客：“可乐”
店长：“**”
顾客：“你说什么”
店长：“好的”
作为人类来看好像没什么问题, 但是对于接收方它是不知道这个好的, 是说店长听到了“我要可乐”, 还是说店长听到了“你说什么”；同时店长也不知道顾客说的“你说什么”是不是要点的菜, 说不定店长确实有这道菜.
有一个解决办法是这样的, 只要顾客听到的不是好的, 就继续说.
顾客：“可乐”
店长：“**”
顾客：“可乐”
店长：“你说什么”
顾客：“可乐”
店长：“好的”
不过这样依旧存在一个问题. 如果第一个可乐店长听清了, 回复好的但是顾客没听到, 继续要可乐, 那么店长很有可能觉得顾客要两杯可乐. 于是我们可以给顾客每一句话都编号. 对于停等协议来说 0 和 1 就够了, 每个数据编号交替. 大概长这样：
顾客：“可乐 0”
店长：“**” // 实际回答 好的 0
顾客：“可乐 0”
店长：“好的 0” // 此时店长知道是上一份数据, 于是回复好的 0 并把这个多余的数据(这个多余的数据叫 冗余分组 )丢掉.
在这里其实店长的话不需要编号, 发送方知道一定是这一个数据的回复(因为现在是停等协议, 并且假定分组不丢失)
rdt2.1 的实现跟上面这个类似, 在数据分组中加了一个新字段来让发送方对其数据分组编号, 将数据分组的序号放在这个字段里. 这样接收方就知道这个数据是重传还是新数据了. 几乎所有现有的数据传输协议都采用了这种方法.
双方的状态及状态转移
状态集合
对于停等协议的 rdt2.1 中, 发送方和接收方的状态又有了变化：
发送方：等待上层的调用 0, 等待 ACK0/NAK0, 等待上层的调用 1, 等待 ACK1/NAK1
接收方：等待下层的调用 0, 等待下层的调用 1
状态转移
发送方
- 等待上层调用 0
接收上层调用, 处理数据(给数据分组编号 0)并交给下层发送, 进入等待 ACK0/NAK0 状态
- 等待 ACK0/NAK0
接收响应, 如果是 ACK0, 那么进入等待上层调用 1 状态；如果是 NAK0, 那么重传.
注意这里如果是 ACK1 或者 NAK1, 那么认为是 ACK/NAK 出错了, 也是重传. 所以这里是只要不是 ACK0, 就进行重传.
- 等待上层调用 1
与 0 类似
- 等待 ACK1/NAK1
与 0 类似
接收方
- 等待下层调用 0
if 数据错误 {
丢弃数据
发送NAK
continue
}
// 这里数据正确了
if 分组编号 != 0 {
/// 冗余分组
发送ACK1 // 发送上一个ACK
continue
}
发送ACK0- 等待下层调用 1
与 0 类似
rdt2.2
在之前的状态及状态转移分析中, 应该可以发现, 只要不是预期的 ACK+序号, 那么就重传. 假如预期是 ACK0, 那接收到的不是 ACK0 就重传, 那 NAK 就没什么用了, 干脆用 ACK1 来表示错误. rdt2.2 就做了这个改变.
rdt2.1 可以不检验 ACK 的序号, rdt2.2 就需要了. 接收端只需要发送 ACK, 不再发送 NAK, 如果接收端发送的是上一个数据分组的 ACK, 那么就表示否定确认；这一个数据分组的 ACK, 那么就表示肯定确认.
关于第一个分组错误的问题, 个人感觉既然序号只有 0 和 1, 那么直接发送另一个序号就可以了. 书上没写, 搜也没搜出来.
rdt3.0
rdt3.0 讨论的是丢包的情况. 在 rdt2.2 中, 如果丢包了发送端是一直在等待 ACK 的, 永远也发送不了新数据, 因此必须及时转移状态.
最简单的方法就是设置一个超时时间和定时器, 定时中断发生时, 重传数据并重置定时器. 不管是数据分组丢了, 还是 ACK 丢了, 又或者是谁谁谁晚来了, 反正中断发生了就重传.
双方的状态及状态转移
rdt3.0 的状态跟 2.2 是类似的, 不过发送方的状态转移多了一些操作.
状态转移
- 等待上层调用 0
接收上层数据, 进行数据处理(设置数据分组编号 0), 将数据交给下层并开启定时器, 然后进入等待 ACK0 状态
- 等待 ACK0
定时器中断, 重传数据并重置定时器, 继续等待 ACK0 状态
接收响应, 如果是 ACK0, 那么进入等待上层调用 1 状态.
这里接收 ACK1 会做什么个人感觉有点问题, 感觉上应该要重传
- 等待上层调用 1
与 0 类似
- 等待 ACK1
与 0 类似
这里等待 ACK0 涉及一个问题, 那就是过早超时.
假设发送方发送了一个分组 0 并设置定时器, 然后进入等待 ACK0 状态；定时器发生中断, 发送方重传, 继续等待 ACK0 状态；
此时发送方发送了两个分组 0
现在接收方校验了第一个分组 0, 发送 ACK0；发送方接收到 ACK0, 进入等待上层调用 1；发送方发送分组 1 并设置定时器, 然后进入等待 ACK1 状态；
此时还有一个分组 0 在路上或者已经到达
接收方又接收到分组 0, 冗余分组丢弃并发送 ACK0；发送方接收到 ACK0：此时发送方应该做什么？
此时还有一个分组 1 在路上或者已经到达
假如说发送方认为是分组 1 出错, 那么重传分组 1；
此时发送方发送了两个分组 1
至此, 跟前面的情况一样了. 假设第一次或者期间某一次发生了过早超时, 之后都不发生, 后面消耗的时间基本是正常的两倍. 如果之后还会发生过早超时可能情况会更复杂一些.
就如之前所说, rdt 只是一种设计思想, 便于学习后面的协议.
在计算机网络：自顶向下方法（原书第 8 版）中, 发送方接收到这个 ACK0 是 ignore, 什么都不做；不过我搜了一个国外的 ppt 上面是重传.
我个人认为是需要重传的, 不过我对 rdt 也不太了解, 如果 ignore 的话那发送方应该有办法判断是过早超时还是需要重传.
流水线可靠数据传输协议
在停等协议那里应该有说停等协议是低效的. 在一些不在意性能的情况下没什么所谓, 不过总是有需要性能的地方的.
既然之前是一个数据包必须等待上一个数据包完成, 现在的话干脆不等了, 拿几个数据包一起发出去.
这里我们从接收方视角来看. 因为对于发送方来说是一起发送的, 但是对于接收方来说依旧是一个一个接收的, 先讨论接收方会更简单一些.
接收方的状态应该有：等待下层调用 i(i 为序号)
当一个数据从下层传递过来时, 检验数据是否正确, 错误发送上一次接收成功的分组序号 ACK. 接着检验编号是否为 i, 如果是, 那么应该发送一个 ACKi, 进入等待下层调用 i+1；如果不是, 那么发送上一次接收成功的分组.
那么如果正在处理数据的时候, 又有数据过来呢？难道要丢掉吗？当然可以, 更好的做法应该是维护一个队列作为缓冲区, 将新来的数据按序放进去. 处理好旧数据后再从缓冲区里取出数据, 继续处理.
滑动窗口协议
接收方大概就这样子, 那么发送方呢.
假设发送方一次最多发送 N 个数据分组. 在真实网络环境中我们不太可能不对 N 设限制, 这样几乎必定导致丢包重传, 因为接收方接受能力有限.
处理发送与确认
为了可靠的数据传输, 每一个数据分组都应该像 rdt2.x 那样需要确认, 因此我们不能发了就不管了, 发送方应该维护一个队列, 将已发送但是未确认的数据分组放进队列里. 这个队列至少要保有 N 个位置留给发送但是没有确认的分组(因为这些分组都有可能需要重传), 这 N 个位置就是 发送窗口 , 要么是已经发送了没确认的, 要么是准备发送的, 反正都是未来有可能要发送的分组. 其中, N 叫做窗口长度.
先来看一个分组被确认的情况. 在之前对接收方的讨论我们应该可以得到, 接收方当且仅当数据正确且数据编号正确才会发送肯定确认. 也就是说, 假如发送方接收到 ACKi, 那么 i 以及 i 之前的分组都是接收成功的, 只是 ACKi 来的比较早, 其它都迟到了.
接收方是按序接收的, 如果是乱序就直接丢弃(跟序号不匹配).
那么当发送窗口里的分组都被确认了, 我们该对这些分组做什么？我们可以把这个队列写一下
[1, 1, 1, 1, 1, 1, x, x, x, x, x, x, x, x] // 1表示发送且确认, 0表示发送但没有确认, x表示不可用
| |
---------------- // 发送窗口如果做过滑动窗口相关的算法题的话应该挺眼熟的. 在这里其实就相当于双指针, 我们只需要同时移动这两个指针就可以了.
[1, 1, 1, 1, 1, 1, n, n, n, n, n, n, x, x] // n 表示空
| |
----------------这里需要注意, 协议规定只有发送窗口里所有分组都被确认, 才能移动窗口.
这里其实个人感觉也可以直接丢弃, 相当于把 1 设成 x, 然后移动窗口. 不过其实没有意义, 这个队列长度确认了就不会改变了, 因为需要根据这个长度进行编号. 而未来滑动窗口到队列尾部也是需要回来的, 到时候还会再写一次数据, 也相当于把先前的分组丢弃了.
处理错误
处理错误还是比较简单的, 只管重传就好. 在之前讨论接收方, 如果数据出错的话那么就发送上一次成功分组的 ACK, 发送方接收到这个 ACK 时就会将发送窗口中所有未确认数据分组按序重传. 发送方不知道是发送窗口里未确认的哪个包丢了, 但是也不需要知道. 因为丢包就几乎一定会产生乱序(除非是最后一个分组或者网络环境奇特), 因此直接全部重传是最简单的.
还有一个丢包错误, 这里处理跟 rdt3.0 类似, 每次发送数据时启用一个定时器.
定时中断, 重传整个发送窗口并重置定时器
否定确认, 重传整个发送窗口并重置定时器
肯定确认, 如果还有未确认数据, 重置定时器；否则关闭定时器
这里的滑动窗口协议可能写的并不完美, 我一直在想要怎么合理地从需要一次发送多个分组推断得到这些结论, 大抵还是不完美吧.
总结(书)
回退 N 步(GBN)协议也叫滑动窗口协议 , 允许发送方发送多个分组而不需要等待确认.
下面展示 GBN 协议的序号范围
[a, a, a, 1, 1, 1, 0, 0, 0, x, x, x, x]
| |
---------------- // 窗口长度N可以将序号范围分割成 4 段, a 段是已发送并且已确认的分组, 1 是已发送但没确认的分组, 0 是未发送的分组, x 表示不可用.
发送方必须响应的三个事件
- 上层调用
当上层调用时, 发送方需要检查发送窗口是否已满. 如果没满, 那么产生一个分组并发送, 然后加入发送窗口；如果满了, 发送方只需要将数据返回给上层, 上层就知道发送窗口满了. 在实际实现中, 发送方更有可能缓存这些数据分组, 等可用时再发送；或者使用同步机制允许上层当且仅当窗口不满才调用.
- 收到一个 ACK
GBN 采用的是对序号为 n 的分组的确认采取 累积确认 的方式, 表明接收方已正确收到序号为 n 的分组以及以前的所有分组.
- 超时事件
如果出现超时, 那么发送方重传所有已发送但还未确认的分组. 如果收到一个 ACK, 但仍有已发送但未确认的分组, 则重置定时器；如果没有, 停止定时器.
在 GBN 协议中, 接收方丢弃所有失序分组.
存在的问题
相信大家应该也能发现一个问题, 接收方在看到编号不一对就直接丢弃了, 无论是否正确. 假如我窗口长度比较大, 发送 0 号分组时路线非常非常卡, 但是到了之后的分组又很顺畅, 这样就会导致 1 号及以后的分组会全部失败, 造成大量的资源浪费. 很多不需要重传的分组都重传了.
选择重传
选择重传(SR) 就是为了解决这个问题.
选择重传也是使用类似滑动窗口的队列, 要求发送方维护一个发送窗口, 接收方维护一个接收窗口.
跟滑动窗口协议不同的是, SR 接收方接收到一个分组不会管他是不是按序的, 只要检验正确就会发送肯定确认. 失序的分组会被缓存起来, 直到所有丢失分组(这个失序分组前面的丢失分组)都收到了, 才把数据交给上层.
这里的肯定确认是对单个分组的肯定, 不再是累计确认了. 发送方在接收到这个肯定确认后, 如果分组序号在窗口里, 那就会把这个分组标记成已接收；如果分组序号是当前窗口的第一个序号(send_base), 则窗口右移, 直到第一个窗口分组未确认.
窗口移动后, 如果窗口里有未发送分组, 那就发送这些分组.
超时重传也不一样, 发送方需要为每一个分组都设定一个定时器.
对于接收方, 接收到一个正确的分组(不管有没有失序), 发送 ACK. 如果此前没有接收过这个分组(即这次不是重传), 那么缓存这个分组. 如果这个分组刚好是接收窗口的第一个, 那么从这个分组开始, 将连续的所有分组一起交给上层(从这个分组开始的所有连续分组), 然后接收窗口右移, 直到未接收.
要注意的是, 只要接收到的分组在接收窗口里, 不管是不是重传, 此前有没有接收过, 只要正确那就发送 ACK(如果是重传, 那之前发送的 ACK 可能没有及时送达导致超时, 此时发送方对该分组是未确认的状态).
其它情况接收方都会忽略接收的分组.
这里书上没有讲分组错误该怎么做, 一次传输使用到的协议不一定只有一种, 选择重传只是其中一种. 对于错误的分组解决办法还挺多的, 比如 NAK, 连续多次 ACK 等.