rdt3.0 性能问题 ：停止等待协议 信道利用率低
因此 需要流水线技术
解决流水线的差错恢复的两种基本方法：
Go-Back-N(GBN 回退N步)
Selective Repeat(SR 选择重传)
- Slide Window 滑动窗口协议
- Sending Window = 1 , Receive Window = 1
- Go BY N 回退N步协议
- Sending Window > 1 , Receive Window = 1
- Selective Repeat 选择重传协议
- Sending Window > 1 , Receive Window > 1
- Sending Window > 1 的协议 称为流水线协议。
slide window 滑动窗口协议
发送窗口：[前沿,后沿]
发送窗口在发送缓冲区里面。是一段已经发送，但还没被确认的分组。
发送缓冲区中 除了发送窗口之外的，就是空闲的缓冲区，可以填入分组然后发送。
实际上 发送缓冲区不动，分组动。但为了便于观察，看成是缓冲区相对于分组移动。
发送缓冲区什么时候向前移动？
- 当发送窗口的后沿向前移动
- 发送窗口的后沿向前移动，意味着有已经发送的分组被确认了。那么，这个分组就没必要再缓存在缓冲区里了。（既然已经确认，发送方就没有再重发这个分组的可能。）
- 可以发现，发送窗口的最左端 一定 就是 发送缓冲区的最左端。因为发送窗口右移一定会导致发送缓冲区右移
接收缓冲区什么时候向前移动
- 当接收窗口的后沿向前移动
发送缓冲区
- 发送缓冲区
- 形式：内存中的一个区域，落入缓冲区的分组可以发送
- 功能：用于存放已发送，但是没有得到确认的分组
- 必要性：需要重发时可用
- 发送缓冲区的大小：发送方在未经接收方确认的情况下，最多可以发送多少个分组。
- 停止等待协议 的发送缓冲区大小 = 1
- 流水线协议 > 1
- 合理的值，不能很大，
- 因为链路利用率不能够超过100%
- 发送缓冲区中的分组
- 未发送的：落入发送缓冲区的分组，可以连续发送出去
- 已经发送的、等待对方确认的分组：发送缓冲区的分组只有得到确认才能删除
发送窗口
- 发送窗口：发送缓冲区内容的一个范围 那些已发送但是未经确认分组的序号构成的空间
- 发送窗口 <= 发送缓冲区
- 一开始：没有发送任何一个分组
- 后沿=前沿
- 之间为发送窗口的尺寸=0
- 每发送一个分组，前沿前移一个单位
前沿移动
- 发送窗口前沿极限：[后沿,前沿] <= 发送缓冲区
后沿移动
- 条件：收到老分组的确认
- 效果：发送缓冲区罩住了新的分组，来了分组可以发送
- 极限：后沿<=前沿
接收缓冲区
接收窗口
- 接收窗口 (receiving window)=接收缓冲区
- receive window 接收窗口 = 1
- receive window = 1 即为 GBN协议
- 返回ack 累计确认：接收方每次返回给发送方的就是最后接收到的正确的分组的ack。
- 对于不是顺序到达的分组，接收方丢弃，然后返回最后接收到的正确的分组的ack。
- 对于顺序到达的分组，接收方接收，返回该ack，并且移动接收窗口。
- 即，只能顺序接收
- 例子：Wr＝1，
- 在0的位置；只有0号分组可以接收；向前滑动一个，罩在1的位置，如果来了第2号分组，则丢弃；
- 在0的位置；只有0号分组可以接收；向前滑动一个，罩在1的位置，如果来了第2号分组，则丢弃；
- receive window 接收窗口 > 1
- receive window > 1 即为 SR协议
- 返回ack 非累计确认：接收方返回给发送方 本次接收到的分组的 ack。（前提：分组要落在接收窗口内）
- 对于不是顺序到达的分组（即高序号分组乱序到达），接收方可以接收。（只要该分组落在了接收窗口内）。
- 即 缓存，但不交付（因为要实现rdt，不允许失序），窗口也不滑动。
- 对于顺序到达的分组（即低序号分组），接收方接收，并且移动接收窗口。
- 即，可以乱序接收
GBN and SR 的窗口互动
正常情况
- 无论是GBN还是SR，其正常情况下的窗口互动都相同，如下
- 互动：即发送窗口和接收窗口如何推进
- 源动力：发送方向发送缓冲区内送入新分组
异常情况
- GBN和SR的区别在于receiving window的大小。
- 体现就是 异常情况下 GBN的接收方只能接收顺序、丢弃乱序，SR的接收方可以缓存乱序。
GBN
发送窗口
- 新分组落入发送缓冲区范围，发送。前沿向右滑动
- 超时重发机制让发送端将发送窗口中的所有分组发送出去
- 来了老分组的重复确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围
接收窗口
- 收到乱序分组，没有落入到接收窗口范围内，则抛弃。然后发送老分组的确认，累计确认；
为什么GBN的超时重发机制会将发送窗口中的所有分组发送出去？
- 原因如下
- GBN发送方是一个发送窗口用一个定时器（窗口内最老的分组的定时器）。一旦窗口中最早发送的分组超时，那么会把整个分组都重传。
- 因为发送方知道 接收方如果有一个已发送的分组没接收到，那么这个已发送分组之后的已发送分组，必然也没有接收到。
- 为什么接收方会这样？
- 因为接收方的接收窗口的大小只有1个分组。不可接受乱序分组。
- 为什么接收方会这样？
- 并且 发送方的发送窗口最左端 就是已被发送但还没被确认的第一个分组。因此，从滑动窗口最左端向右，即整个滑动窗口内的分组，都还没有被接收方接收。因此发送方要将滑动窗口内的所有分组全部重发。
SR
发送窗口
- 新分组落入发送缓冲区范围，发送->前沿滑动
- 超时重发机制让发送端将超时的分组重新发送出去
- 来了乱序分组的确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围
接收窗口
- 收到乱序分组，落入到接收窗口范围内，接收
- 发送该分组的确认，单独确认
SR协议，发送方对于每一个分组都有一个定时器；而非整个窗口使用一个定时器（GBN协议就是）。
- 如果接收方接收到乱序的分组（高序号分组），那么会缓存在缓冲区中（并不移动窗口），并且发送该分组的ACK给发送方。
- 发送方会接受返回的ACK，这些ACK使得发送方知道：发送窗口里的哪些分组已经被接收了。停止这些分组的定时器。这些分组没必要再重发，更没有必要继续缓存在窗口里，不过可惜，如果窗口后沿的分组没被确认，即使其他高序号被确认，窗口仍旧不能移动。
- 当发送方发生超时重传时，只需要重传发送窗口内没被确认的分组即可。不需要像GBN一样，全部重新发送。
GBN 和 SR协议的内容异同
相同
发送窗口>1
一次能够可发送多个未经确认的分组
发送端最多在流水线中有N个未确认的分组
不同
GBN : receiving window = 1
- 接收端：只能顺序接收
- 发送端：从表现来看，一旦一个分组没有发成功，如：发送窗口：0,1,2,3,4 ; 假如1未成功，234都发送出去了，要回退到1再发送；GO BACK TO 1
SR: receiving window > 1
- 接收端：可以乱序接收
- 发送端：发送窗口：0,1,2,3,4，一旦1未成功，2,3,4,已发送，无需重发234，只选择性重发1 : SELECT 1
receiving window的差异 带来了是【回退、重传窗口内所有分组】；【还是选择性重传】的差异
总结
GBN
发送端最多在流水线中有N个未确认的分组
- 发送窗口的最大值（发送缓冲区）限制发送未确认分组的个数
接收方发送累计型确认 cumulative ack
- 接收端如果发现乱序（高序号来了），不确认新到来的分组
发送端拥有最老的未确认的分组的定时器。
- 一个窗口只需设置一个定时器
- 若定时器到时，重传所有未确认分组，GBN中即重传窗口内所有分组。
发送方状态机
发送窗口[base,seqnum-1]
发送缓冲区[base,base+N-1]
接收方状态机
例子
SR
发送端最多在流水线中有N个未确认的分组
- 发送窗口的最大值（发送缓冲区）限制发送未确认分组的个数
发送方为每个未确认的分组保持一个定时器
- 每收到一个ack，就将相应的定时器关掉。
接收方对每个到来的分组单独确认individual ack 非累计确认
- 接收窗口>1
- 可以缓存乱序的分组
- 最终将分组按顺序交付给上层
- 接收窗口>1
如图
例子
状态机：略。有时间再搞。
窗口大小
如果用nbits来代表分组序号
- 那么序号空间为2^n 即[0,…2^n-1]
那么 对于SR协议，窗口长度必须<=序号空间大小的一半
- 即 SR协议的 窗口长度 <=2^(n-1)
- 原因：发送方和接收方之间的窗口缺乏同步，并不总是一致的。
- 见自顶向下P150
那么 对于GBN协议，窗口长度必须 <= 序号空间大小-1
- 即 GBN协议的 窗口长度 <=2^n - 1
分析
- 略。改天再搞。写密码学实验了该。