运输层-可靠数据传输(rdt)
rdt协议简介
可靠数据传输（Reliable Data Transfer，RDT）是一种可靠的数据传输协议，它在传输层、应用层和数据链路层都很重要。
特点：不出错、不重复、不失序、不丢失，是计算机网络Top10的问题之一。
TCP实现了可靠数据传输。
rdt的使命：在下层依赖提供的服务不可靠的情况下，为上层提供可靠的服务。
其中涉及了一个封装和解封装的过程。 上半部分是应用层，下面是rdt提供的可靠的信道（尽管下层是不可靠的）。
在上图中，rdt_send和deliver_data()都是单向的通道，但是udt_send和rdt_rec是双向的通道。我们只考虑单向的信息传输（发送方发给接收方），其实两个相反的单向就是双向的。
我们常用有限状态机（Finite State Machine，FSM）来描述rdt协议。箭头上的文字，横线上方是引起状态变迁的事件，下方是活动。
使用渐进式的方式进行研究，因此从rdt1.0开始，从完全可信到逐渐不可信（接近真实情况）进行研究。
rdt1.0
可靠信道上的可靠数据传输
1.0假定底层信道完全可靠，不会丢弃分组。但是不可能存在这种信道。
在rdt1。0中，由于我们认为下层信道完全可信，因此我们的rdt信道只需要进行封装和解封装操作，如左边的图，当调用时，创建一个rdt_send状态，这个状态包含下面的活动：将数据封装打包，然后通过udt发送出去（实际上，这个时候的udt我们认为是可信的），接着就等待下次的调用。在右边的接收端，由于我们认为数据完全不会丢失，所以我们只创建一个rcv状态，进行数据包的解封装，然后把数据传给应用层，再等待下次数据送达。
rdt2.0
产生位错误的信道上的可靠数据传输
此时的下层信道就不再可信了，但是它只可能产生位错误，即0变1、1变0，它不可能产生乱序和丢包。
如何从错误中恢复？
确认机制（Acknowledgement，ACK），接收方显式地告知发送方分组已经接收。
NAK：接收方显式地告知发送方分组有错误。
发送方收到NAK后重传分组。
Pardon！（没听清！请再说一遍）就是现实生活中的一种重传机制。
差错检验（校验和）、序列号、控制消息的反馈（ACK）、重传
::: theorem 2.0的缺陷
2.0致命的缺陷是并没有考虑到如果ACK和NAK出错了怎么办，这样的话，就会导致整个传输过程的错误，进入死锁。
方法：可以给ACK和NAK增加校验和，检错并纠错（难度高），添加额外的控制消息（但是控制消息也可能会坏），一旦ACK和NAK错了就重传（比较简单，但是如果本身被正确接收那么再重传会接收重复分组）。这个问题将在下面得到解决.
:::
rdt2.1
给每个分组增加序列号(SYN)，解决上面的2.0缺陷
在rdt下，状态数量翻倍。
接收方需要记住当前状态。
在rdt2.0的基础之上，发送方在打包数据包时添加了0或者1编号，同样ACK,NAK字段上也添加了0，1字段，表示0.1号字段的确认或者否定。发送方就有了2种状态发送0号数据包，1号数据包，接收方也有了2种状态等待0号数据包和等待1号数据包。现在假设情景发送方向接收方发送0号数据包，如果接收方接收到0号数据包，返回ACK，但是ACK出现翻转，接收方处于等待1号数据状态，发送方重复发送0号数据，接收方会拒绝0号数据，避免重复。如果接收方接收到0号数据包出现错误，返回NAK，但是NAK出现翻转，接收方处于等待0号数据状态，发送方继续发送1号数据，接收方会拒绝1号数据，避免错序。
rdt2.2
取消NAK消息，只使用ACK消息进行确认。在ACK消息中显式加入被确认的分组的序列号。发送方在收到重复ACK之后，采取与NAK消息一样的操作，重传当前分组。
我们在ACK的信息上加上了期望的顺序号，现在假设情景发送方向接收方发送0号数据包，如果接收方接收到0号数据包，返回（ACK，1），发送方接着发送1号数据包。如果接收方接收到0号数据包出现错误，返回（ACK，0），发送方重传0号数据包。
也就是说，如果我发送为0，你接收正确，那么你必须发送1，之后我开始发下一个数据包（1），如果你发送0给我，那么我就要把0号数据包重传给你。
rdt2.x实际上只考虑了错位的发生，却没有考虑丢包。这个问题留给rdt3.0去解决。
rdt3.0
如果A发送了一个分组，但是中途丢失，那么B就不会有任何反应，A也会一直等下去，那么就会崩溃。
解决方法：等待合理的时间之后没有收到ACK就重传。但是出现了这样的问题：在合理时间之后才到达，那么会发生重复，不过可以使用序列号解决。
Details
rdt3.0能正常工作但是性能很差
1Gbps的链路，15ms的端到端传播延迟，1KB的分组。
Details
流水线和滑动窗口机制
为了解决rdt3.0的缺陷，我们需要一个滑动窗口机制。利用流水线机制，我们连续发多个分组（例如三个），然后再进入等待状态。这样上面的利用率U=0.00027乘以3就会变成0.0008.在这种情况下，我们需要更大的序列号范围。发送方和接收方需要更大的存储空间来缓存分组。
Details
滑动窗口协议（Sliding-Window Protocol）
窗口：允许使用的序列号范围。
窗口尺寸N：最多有N个待确认的分组。
在图中，窗口尺寸为14，即最多有14个待确认的分组。窗口不断往右边挪动进行确认。
GBN协议（回退重传协议，Go-Back-N Protocol）
1.分组头部包含k-bit序列号。
2.窗口尺寸为N，即最多允许N个待确认的分组。
send-base:最小的序列号
nextsequence:下一个待确认的分组序列号
3.累计确认ACK（n），确认到序列号n（包含n）的分组均被正确接收。可以收到重复ACK。（接收者仅仅发送累计的确认，如果中间有数据损失则不予确认。
4.为传输分组设置计时器（timer），若超时Timeout事件：如果n这个序列号发生了超时事件那么就要重传序列号大于等于n且还未收到ACK的所有分组(n+1、n+2、n+3····),可能会造成资源浪费。
发送方扩展FSM：
接收方扩展FSM：
接收方发送拥有最高序列号的、已经被正确接收的分组ACK。GBN的接收方不存在缓存，它只需要记住唯一的expectedSequnce。可能产生重复的ACK。对于乱序的分组，全部丢弃并重新确认序列号最大的、按序到达的分组。如果我期望的分组的序列号是5，但是此时收到了7，则确认序列号4，将5、7丢弃。
Details
窗口大小为4，发送方发送数据包0，1，2，3，然后进入等待状态，其中数据包2丢失，接收方返回Ack0，1，窗口滑动继续发送包4，5，此时包2计时超时，默认数据包2没有收到，按照GBN，发送方重新发送数据包2，3，4，5。这里可以看出数据包重复了。
数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为0～7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是多少？分别是那几个帧？
Details
SR协议(选择重传协议，Selective Repeat)
GBN使用累计确认机制，重传时导致很多重传，造成资源浪费，因此SR协议使用单独确认机制，设置了缓存机制，缓存乱序到达的分组，为每一个分组设置单独的计时器。此时，发送方和接收方均使用滑动窗口了。
从上层接收的数据：
如果窗口有空位，发送数据包。
如果第n帧超时：
重发n数据包，重启n的定时器。
如果收到n的ACK：
标记n帧为已完成。如果n为最小的没被接收的帧，那么在接收到ACKn后，窗口向前滑动。
收到分组n：
如果在（recevbase，recevbase+N-1）内，那么表示n是期望收到的，发送确认ACK，如果收到的是乱序的分组，那么缓存下来（buffer），如果是正常按序到达的，那么交付给上层并滑动窗口。
如果收到的分组在(recevbase-N,recevbase-1)范围内：
这说明之前正确接收分组时发送的ACK丢失了，没有正确到达发送端，因此要再次确认ACK（n）。
其他时候：
忽略。
上图发完5之后不发了，是因为必须要等2交付。
因为接收方不能“看见发送方”采取的动作。接收方所能观察到的是它从信道中收到的以及它向信道中发出的报文序列。就其关注而言，上图的情况时等同的。显然，窗口长度比序列号空间小1时协议无法工作。序列号空间大小与窗口尺寸要满足：
Ns+Nr<=2^k，Ns表示发送方的窗口大小，Nr表示接收方的窗口大小，k表示序列号位数。
比较GBN和SR
