前言
Rdt1.0、Rdt2.0、Rdt2.1、Rdt2.2、Rdt3.0、流水线协议、滑动窗口协议。
一、Rdt
- rdt在应用层、传输层和数据链路层都很重要，是网络Top10问题之一。
- 信道的不可靠特点决定了可靠数据传输协议（rdt）的复杂性
下面我们只考虑单向数据传输（但是控制信息是双向流动的），双向数据传输实际上就是两个单向数据传输问题的综合，所以我们只考虑单向。下面将会用有限状态机（FSM）来描述发送方和接收方。
1.Rdt1.0
在可靠信道上的可靠数据传输
- 下层的信道是完全可靠的
- 没有比特出错
- 没有分组丢失
- 发送方和接收方的FSM
- 发送方将数据发送到下层信道
- 接收方从下层信道接收数据
2.Rdt2.0
具有比特差错的信道
- 下层信道可能会出错:将分组中的比特翻转
- 用校验和来检测比特差错
- 问题：怎样从差错中恢复
- 确认(ACK):接收方显式地告诉发送方分组已被正确接收
- 否定确认(NAK):接收方显式地告诉发送方分组发生了差错
- 发送方收到NAK后，发送方重传分组
- rdt2.0中的新机制：采用差错控制编码进行差错检测
- 发送方差错控制编码、缓存
- 接收方使用编码检错
- 接收方的反馈：控制报文(ACK，NAK)：接收方→发送方
- 发送方收到反馈相应的动作
FSM描述
- 根据上图，可以看到：发送方一直等待上层调用，接收方一直在等待下层调用；当上层调用发送方时，发送方将packet（将发送数据封装，带有差错检测信息的数据包（data，checksum））调用函数发送（udt_send），发送后进入等待ACK或NAK确认的状态，并且此状态一直在检测信息NACK还是ACK，如果是NACK就重新调用函数发送packet，如果是ACK就转为等待上层调用的状态。而接收方，如果有差错时（corrupt），调用函数（udt_send）发送NAK信息，没有差错就调用函数发送ACK信息。
- 接收方差错检测是通过比较发送方带来的checksum（校验和）和自己的校验和结果，一样说明未出错，不一样则为出错。
checksum //校验和 rdt_rcv(rcvpkt) //对于sender是确认信息 //对于receiver是分组 isACK(rcvpkt) //确认信息为ACK isNAK(rcvpkt) //确认信息为NAK corrupt(rcvpkt) //根据校验和发现有差错 notcorrupt(rcvpkt) //根据校验和发现没有差错
思考：
- 如果ACK/NAK出错?（发送方接收的不是ACK也不是NAK）
- 发送方不知道接收方发生了什么事情!
- 发送方如何做?
- 重传?可能重复
- 不重传?可能死锁(或出错)
- 需要引入新的机制
- 序号
- 处理重复：
- 发送方在每个分组中加入序号
- 如果ACK/NAK出错，发送方重传当前分组
- 接收方丢弃（不发给上层）重复分组
等停协议发送方发送一个分组，然后等待接收方的应答
3.Rdt2.1
发送方处理出错的ACK/NAK
发送方：
接收方：
- 发送方：
- 在分组中加入序列号
- 两个序列号(0，1）就足够了
- 一次只发送一个未经确认的分组
- 必须检测ACK/NAK是否出错（需要EDC)
- 状态数变成了两倍
- 必须记住当前分组的序列号为0还是1
- 接收方：
- 必须检测接收到的分组是否是重复的
- 状态会指示希望接收到的分组的序号为0还是1
- 注意：接收方并不知道发送方是否正确收到了其ACK/NAK
- 没有安排确认的确认
- 具体解释见下面
4.Rdt2.2
无NAK的协议
- 功能同rdt2.l，但只使用ACK(ack要编号)
- 接收方对最后正确接收的分组发ACK，以替代NAK
- 接收方必须显式地包含被正确接收分组的序号
- 当收到重复的ACK（如:再次收到ack0）时，发送方与收到NAK采取相同的动作：重传当前分组
- 为后面的一次发送多个数据单位做一个准备
- 一次能够发送多个
- 每一个的应答都有：ACK，NACK;麻烦
- 使用对前一个数据单位的ACK，代替本数据单位的nako确认信息减少一半，协议处理简单
5.Rdt3.0
具有比特差错和分组丢失的信道
- 新的假设：下层信道可能会丢失分组（数据或ACK）
- 会死锁
- 机制还不够处理这种状况:
- 检验和
- 序列号
- ACK
- 重传
- 方法：发送方等待ACK一段合理的时间
- 发送端超时重传：如果到时没有收到ACK-→重传
- 问题：如果分组（或ACK）只是被延迟了:
- 重传将会导致数据重复，但利用序列号已经可以处理这个问题
- 接收方必须指明被正确接收的序列号
- 需要一个倒计数定时器
链路层的timeout时间确定的传输层timeout时间是适应式的；
链路层的超时时间确定的传输层超时时间是适应式的。
Rdt3.0性能
Rdt3.0停等操作：
二、流水线协议
提高链路利用率，提高Rdt3.0性能瓶颈
- 流水线：允许发送方在未得到对方确认的情况下一次发送多个分组
- 必须增加序号的范围：用多个bit表示分组的序号
- 在发送方/接收方要有缓冲区
- 发送方缓冲：未得到确认，可能需要重传;
- 接收方缓存：上层用户取用数据的速率 ≠ 接收到的数据速率;接收到的数据可能乱序，排序交付(可靠)
- 两种通用的流水线协议：回退N步(GBN)和选择重传(SR)
sending window = 1，receving window = 1 --> S-W 停等协议 流水线协议： sending window > 1，receving window = 1 --> GBN sending window > 1，receving window > 1 --> SR
1.滑动窗口（slide window）协议
发送窗口
- 发送缓冲区
- 形式：内存中的一个区域，落入缓冲区的分组可以发送
- 功能：用于存放已发送，但是没有得到确认的分组
- 必要性：需要重发时可用
- 发送缓冲区的大小：一次最多可以发送多少个未经确认的分组
- 停止等待协议 = 1
- 流水线协议 > 1，合理的值，不能很大，链路利用率不能够超100%
- 发送缓冲区中的分组
- 未发送的：落入发送缓冲区的分组，可以连续发送出去;
- 已经发送出去的、等待对方确认的分组：发送缓冲区的分组只有得到确认才能删除
- 发送窗口:发送缓冲区内容的一个范围
- 那些已发送但是未经确认分组的序号构成的空间
- 发送窗口的最大值<=发送缓冲区的值
- 一开始:没有发送任何一个分组
- 后沿=前沿
- 之间为发送窗口的尺寸 = 0
- 每发送一个分组，前沿前移一个单位
- 发送窗口前沿移动的极限：不能够超过发送缓冲区
- 发送窗口后沿移动
- 条件：收到老分组的确认
- 结果：发送缓冲区罩住新的分组，来了分组可以发送
- 移动的极限：不能够超过前沿
发送窗口滑动过程——相对表示法
- 采用相对移动方式表示，分组不动
- 可缓冲范围移动，代表一段可以发送的权力
绿色是滑动窗口，粉红色表示已发送未得到确认，浅蓝色表示得到确认
接收窗口
- 接收窗口(receiving window)=接收缓冲区
- 接收窗口用于控制哪些分组可以接收;
- 只有收到的分组序号落入接收窗口内才允许接收
- 若序号在接收窗口之外，则丢弃;
- 接收窗口尺寸Wr = l，则只能顺序接收;
- 接收窗口尺寸Wr > l，则可以乱序接收
- 但提交给上层的分组，要按序
- 例子: Wr=l，在0的位置;只有0号分组可以接收;向前滑动一个，罩在1的位置，如果来了第2号分组，则丢弃;
- 接收窗口的滑动和发送确认
- 滑动：
- 低序号的分组到来，接收窗口移动;
- 高序号分组乱序到，缓存但不交付（因为要实现rdt，不允许失序）），不滑动
- 发送确认:
- 接收窗口尺寸=1 ;发送连续收到的最大的分组确认（累计确认，GBN）
- 接收窗口尺寸>1;收到分组，发送那个分组的确认（非累计确认，SR）
正常情况下的2个窗口互动
- 发送窗口
- 1.有新的分组落入发送缓冲区范围，发送->前沿滑动
- 4.来了老的低序号分组的确认->后沿向前滑劫->新的分组可以落入发送缓冲区的范围
- 接收窗口
- 2.收到分组，落入到接收窗口范围内，接收
- 3.是低序号，发送确认给对方
- 发送端上面来了分组->发送窗口滑动->接收窗口滑动->发确认
异常情况下GBN的2个窗口互动
- 发送窗口
- 1.新分组落入发送缓冲区范围，发送->前沿滑动
- 5.超时重发机制让发送端将发送窗口中的所有分组发送出去
- 4.来了老分组的重复确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围(此时如果发送缓冲区有新的分组可以发送)
- 接收窗口
- 2.收到乱序分组，没有落入到接收窗口范界内，抛弃
- 3.（重复）发送老分组的确认，累计确认；
异常情况下SR的2窗口互动
- 发送窗口
- 1.新分组落入发送缓冲区范围，发送->前沿滑动
- 5.超时重发机制让发送端将超时的分组重新发送出去
- 4.来了乱序分组的确认->后沿不向前滑动->新的分组无法落入发送缓冲区的范围（此时如果发送缓冲区有新的分组可以发送）
- 接收窗口
- 2.收到乱序分组，落入到接收窗口范围内，接收
- 3.发送该分组的确认，单独确认；
每发送一个分组，发送方就会启动一个超时计时器
GBN协议和SR协议的异同
- 相同之处
- 发送窗口>1
- 一次能够可发送多个未经确认的分组
- 不同之处
- GBN：接收窗口尺寸 = 1
- 接收端：只能顺序接收
- 发送端：从表现来看，一旦一个分组没有发成功，如：0,1,2,3,4;假如1未成功，234都发送出去了，要返回1再重新发送（234也重发）
- SR:接收窗口尺寸 > 1
- 接收端：可以乱序接收
- 发送端：发送0,1,2,3,4，一旦1未成功，2,3,4,已发送，无需重发，选择性发送1
2.小结
Go-back-N：
- 客户端最多再流水线中有N个未确认的分组
- 接收端只是发送累计已确认cumulative ack
- 接收端如果发现gap,不确认新到来的分组
- 发送端拥有对最老的未确认的定时器
- 只需设置一个定时器
- 当定时器到时时，重传所有未确认分组
Selective repea：
- 发送端最多在流水线中有N个未确认的分组
- 接收方对每个到来的分组确认individual ack(非累计确认)
- 发送方为每个未确认的分组保持一个定时器
- 当超时定时器到时，只是重发到时的未确认分组
对比GBN和SR
适用范围：
- 出错率低:比较适合GBN，出错非常罕见，没有必要用复杂的SR，为罕见的事件做日常的准备和复杂处理
- 链路容量大（延迟大、带宽大）:比较适合SR而不是GBN，一点出错代价太大
窗口最大尺寸
总结
以上就是Rdt和流水协议（窗口滑动）的详细讲解
