DJ3-2 传输层(第二节课)
目录
一、如何实现可靠数据传输
1. 需要解决地问题
2. 使用的描述方法
二、rdt1.0:完全可靠信道上的可靠数据传输
1. 前提条件
2. 有限状态机 FSM
三、rdt2.0:仅具有 bit 错误的信道上的可靠数据传输
1. 前提条件
2. 有限状态机 FSM
3. 停等协议
4. rdt2.0 的致命缺陷
四、rdt2.1:发送方能够处理混淆的 ACK 和 NAK
1. 发送方的有限状态机 FSM
2. 接收方的有限状态机 FSM
五、rdt2.2:一个不需要 NAK 的协议
六、rdt3.0:具有出错和丢失的信道上的可靠数据传输
1. 前提条件
2. 发送方的有限状态机 FSM
3. 为什么要在超时后才进行重传?
4. rdt3.0 的性能
七、Go-Back-N
一、如何实现可靠数据传输
1. 需要解决地问题
分组交换限制了分组的大小
但是需要解决下述三大问题:
- 发送顺序和接收顺序可能不同:编号
- 数据可能出错:重传
- 分组可能丢失:发送方定时 + 接收方确认
2. 使用的描述方法
二、rdt1.0:完全可靠信道上的可靠数据传输
1. 前提条件
在完美可靠的信道上
- 没有 bit 错误
- 没有分组丢失
发送方和接收方的 FSMs:
- 发送方发送数据到下层信道
- 接收方从下层信道接收数据
2. 有限状态机 FSM
发送方的动作:
- 从应用层得到数据
- 在传输层封装数据和发送分组
接收方的动作:
- 从网络层接收分组
- 在传输层解封分组和传递数据
三、rdt2.0:仅具有 bit 错误的信道上的可靠数据传输
1. 前提条件
1)如何检测到错误
下层信道可能使传输分组中的 bit 受损
- 接收方将通过校验和检测到 bit 错误
2)如何从错误中恢复
接收方反馈:
- 确认(ACKs):接收方明确告诉发送方 “分组接收正确”
- 否认(NAKs):接收方明确告诉发送方 “分组接收出错”
发送方收到 NAK 后将会重传该分组。
3)rdt2.0 中的新机制(在 rdt1.0 中没有的)
- 差错检测
- 接收方反馈
接收方反馈给发送方控制信息(ACK,NAK)
2. 有限状态机 FSM
checksum //校验和rdt_rcv(rcvpkt) //对于sender是确认信息//对于receiver是分组isACK(rcvpkt) //确认信息为ACK
isNAK(rcvpkt) //确认信息为NAKcorrupt(rcvpkt) //根据校验和发现有差错
notcorrupt(rcvpkt) //根据校验和发现没有差错
1)没有错误时的操作
- 上层调用 sender,sender 发送完分组,转为等待反馈状态
- receiver 接收到正确的分组,处理分组递交上层,并反馈确认信息
- sender 收到确认信息,转为等待调用状态
2)错误场景中的操作
- 上层调用 sender,sender 发送完分组,转为等待反馈状态
- receiver 接收到错误的分组,直接反馈否认信息
- sender 收到否认信息,立即重传分组,且仍为等待反馈状态
- receiver 接收到正确的分组,处理分组递交上层,并反馈确认信息
- sender 收到确认信息,转为等待调用状态
3. 停等协议
停等协议:发送方发送一个报文,然后等待接受方的响应。
rdt2.0 的优点:因为必须保证上一个分组接收成功后才能发送下一个,所以不存在分组失序问题。
4. rdt2.0 的致命缺陷
1)ACK 和 NAK 可能出现混淆
发送方并不知道接收方发生了什么!
- 万能的做法是:重传,但是重传可能导致分组重复
- 并且接收方无法区分这是重传的分组还是下一个分组
2)如何解决分组重复
发送方给每个分组加一个序号
- 在 ACK 和 NAK 混淆时,发送方重传当前分组
- 接收方通过识别序号来丢弃重复的分组,并不向上传递
3)需要为停等协议设置多少个序号
答案:2 个,因此只需要一个 bit 。可以采用 0 号和 1 号来区分。
分析:由于采用停等协议,因此在 发送方发送当前分组 - 接收方接收分组并反馈 ACK - 发送方发送下一个分组 的过程中,只会涉及到两个相邻的分组:当前发送的分组和下一个发送的分组。如下图所示。
四、rdt2.1:发送方能够处理混淆的 ACK 和 NAK
1. 发送方的有限状态机 FSM
make_pkt(0, data, checksum) //封装有序号/数据/校验和corrupt(rcvpkt) //对于sender是确认信息出错//对于receiver是报文出错
2. 接收方的有限状态机 FSM
has_seq0(rcvpkt) //根据序号知道接收的是0号make_pkt(ACK, chksum) //封装校验和以便sender检测确认信息是否出错
分析右侧语句:
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) && has_seq0(rcvpkt)
-------------
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
此时 receiver 等待的是 1 号报文,但是 has_seq0(rcvpkt) 表示 sender 给 receiver 发的是 0 号报文,这种情况说明:receiver 的反馈信息 ack 1 出错导致 sender 不知道 receiver 是否正确接收了 1 号报文。因此,receiver 需要做的是:重传 ack 1 。
五、rdt2.2:一个不需要 NAK 的协议
同 rdt2.1一样的功能,但是只用 ACK 不用 NAK。如果当前分组接收正确,则接收方发送 ACK,并且 ACK 必须明确包含被确认的分组的序号。
如果发送方收到重复 ACK,则执行和 NAK一样的处理:重发当前分组。
六、rdt3.0:具有出错和丢失的信道上的可靠数据传输
1. 前提条件
1)存在的问题
下层信道除了 bit 出错还要丢失报文:包括数据和 ACK 。
校验和、序号、确认、重传将会有帮助,但是不够。
2)解决方法
方法:发送者等待 “合理的” 确认时间,如果在这个时间内没有收到确认就重传。
- 要求倒计时定时器
- 只有在定时器超时时才触发重传
如果报文只是延迟而没有丢失:
- 重发将导致重复,但是使用序号已经解决了这个问题
- 接受方必须指定被确认的报文序号
2. 发送方的有限状态机 FSM
分析右侧语句:
1)即使 sender 接收到的确认信息出错了或 receiver 说这个报文出错了,sender 也只在超时时重传当前报文。
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) || isACK(rcvpkt, 1))
-------------
//do no-optimeout
-------------
udt_send(sndpkt)
start_timer
2)sender 可能接收到上一个报文超时了很长时间的确认信息(甚至在重传报文的确认信息之后才到达),此时 sender 不做任何操作。
rdt_rcv(rcvpkt)
-------------
//do no-op
3. 为什么要在超时后才进行重传?
图一为 rdt3.0 中可能出现的问题,图二和图三为相应的解决方案。
图一中的问题:
- 第一个 pkt 0 的确认信息 ack 0 在确认时间内没有到达 sender
- 按照超时才重传原则,sender 在确认时间截止时重传第二个 pkt 0
- 第一个 pkt 0 的确认信息 ack 0 终于到达
- sender 认为 pkt 0 已接收完毕,开始传输 pkt 1
- 在 pkt 1 的确认信息 ack 1 到达之前,第二个 pkt 0 的确认信息 ack 0 到达了
- 由于重复的 ack 等价于 nak,因此 sender 需要重传 pkt 1
在这里有两种重传方案:
- (a) 直接重传:此时此刻立即重传 pkt 1
- (b) 超时才重传:当 pkt 1 的确认时间截止时才重传
方案 (a) 直接重传:
- sender 需要立即重传第二个 pkt 1
- 在第二个 pkt 1 的确认信息 ack 1 到达之前,第一个 pkt 1 的确认信息 ack 1 到达了
- sender 认为 pkt 1 已接收完毕,开始传输 pkt 0
- 在 pkt 0 的确认信息 ack 0 到达之前,第二个 pkt 1 的确认信息 ack 1 到达了
- 由于重复的 ack 等价于 nak,因此 sender 需要重传 pkt 0
- ...
可见,使用该方案会不断地出现需要重传的情况。我们需要做的是:让子弹多飞一会儿!
方案 (b) 超时才重传:
- sender 选择在第一个 pkt 1 的确认时间截止时才重传第二个 pkt 1
- 然而,在截止之前第一个 pkt 1 的确认信息 ack 1 到达了,sender 不需要重传了
- sender 认为 pkt 1 已接收完毕,开始传输 pkt 0
- ...
后续一切正常。
4. rdt3.0 的性能
网络利用率 = 发送时间/得到响应的时间。公式如下。
七、Go-Back-N
发送方需要做的:
- 在分组头中规定一个 k 位的序号
- 设置窗口:允许连续发送 N 个未被确认的报文
窗口里的报文的状态:
- 已发送但未确认
- 未发送
1. 一次性发送窗口内的 N 个报文
发完这 N 个报文,就停止发送。
2. 报文得到确认时
receiver 确认收到 1 号报文,sender 得到确认,窗口右移一格,sender 发送此前未发送的 5 号报文。
3. 报文丢失时
假设 2 号报文在传输过程中丢失了,那么即使 3 号报文到达了 receiver,receiver 也会拒绝接收它,更不用说反馈确认信息了。对于 4 号报文和 5 号报文也不例外。
4. 确认信息超时时
由于 receiver 是一个很专一的人,它拒绝除 2 号报文以外的所有报文,然而 2 号报文又丢失了,因此 receiver 无法反馈确认信息,从而导致 sender 长时间无法收到确认信息。
幸好有一个定时器在记录 2 号报文的确认时间,该 计时器 用于记录最早的未被确认报文的发送时间。它告诉 sender 超时了,于是 sender 重发窗口里的所有报文。
5. 确认信息丢失时
假设 receiver 接收了 2 号报文和 3 号报文,但是相应的确认信息在传输过程中丢失了。而之后 receiver 又接收了 4 号报文,并且其确认信息顺利传输给了 sender 。
sender 认为像 receiver 这样专一又负责的人,一定是已经接收到了 4 号报文之前的所有报文才会反馈 4 号报文的确认信息。因此 sender 放心的右移三次窗口,并且发送在窗口里出现的新报文。
- 暗示当前分组之前的所有分组都被正确接收了
- 窗口可以一次性右移多个位置