计网——可靠数据传输原理

计网——可靠数据传输原理

最近也是用了几天时间读了一下top-down中运输层的可靠数据传输原理，之后看了一下科大的网课。其中的内容也是相当多，一节课的内容足足学了几天。在写这篇文章前，关于计网我从来没写过以书中知识为内容的博客，因为在之前的第一章总述以及应用层的学习中，计网都给我一种知识点很零碎的感觉，第一章相当于是把整本书的内容做了一个缩略的介绍，之后是应用层，应用层有很多协议，每个协议都有自己的知识点，所以没办法一条线把它们串起来。

但学到运输层给我的感觉就不一样了，先学了运输层的一个职责（把网络层主机到主机间的通信转换为不同主机上进程与进程之间的通信），接着又学习了多路复用和分解的技术，这是实现运输层职责的关键。至此，我们可以用多路复用和解复用技术完成运输层的一个基本职责。但是我们知道，网络层的IP协议向上层交付的数据是尽力而为的交付，也就是不可靠的服务，那么在应用层能否把不可靠的服务转变为可靠的服务呢？在学习这一章之前，我们在早期的学习中了解到这是TCP协议可以实现的功能，在学习TCP如何实现这些功能前，我们先来看如何来传输可靠的数据，即——可靠数据传输原理。

问题描述

在正式开始学习前，我们要写了解这个问题。我们知道，计算机网络的每一层都是接受下层的服务然后实现功能为上层提供服务。我们假设提供可靠数据传输(rdt)的是运输层（实际上rdt的实现也会在链路层以及应用层），图示说明了我们学习可靠数据传输的框架：为上层提供服务的抽象是：数据可以通过一条可靠的信道传输，借助与可靠信道，数据就不会损坏或丢失，且按顺序交付。

但刚刚提到过，网络层IP协议提供的是不可靠的服务，所以在运输层中，我们需要实现一些协议，来把不可靠的数据传输变为可靠的数据传输，这个协议就是可靠数据传输协议(rdt)。我们还是以应用层，运输层，网络层为例：

• 调用rdt_send()函数，上层可以调用rdt发送方，把要传输的数据交付给它
• rdt的发送方和接收方都需调用udt_send()发送分组给对方（udt为不可靠数据传输）
• 当分组通过信道到达接收方时，调用rdt_rcv()
• 通过deliver_data()，rdt向上层交付数据

研究方法

我们知道，一个可靠的数据传输协议可以使数据不受损，不丢失，不乱序。现在我们将一步步的研究rdt协议，先从最简单的情况考虑起，一步步构造一个完美、可靠的数据传输协议。在正式开始之前，我们要先知道：底层的可靠性决定了rdt协议实体的复杂度。什么意思呢？还是拿IP协议举例，如果IP自己就可以实现可靠的数据传输，那我运输层只需要做一个多路复用就可以了，此时的rdt协议便非常简单。所以我们先假设IP协议是一个完美无缺的可靠性数据传输协议，再一层层放开这个假设，最终使IP协议变为一个不可靠的（即现在的IP协议的样子），在此过程中，我们的rdt协议也将一点点复杂起来。此外，我们使用有限状态机（FSM)来描述发送方和接收方的状态。

rdt1.0（经完全可靠信道的可靠数据传输）

首先我们考虑最简单的情况，即底层信道是完全可靠的，没有比特出错，也没有分组丢失。那么此时发送方和接收方的FSM为：

• 发送方从上层拿到要方式的数据，将数据发送至下层信道
• 接收方从下层信道接收数据，将数据deliver到上层

rdt2.0（经有比特差错信道的可靠数据传输）

在rdt1.0中，我们假设底层信道是完全可靠的，现在我们放开一点这个条件，我们假设经底层信道传输的数据可能会出现比特差错，其余不可靠的情况不会出现。那么此时，rdt协议应如何设计呢？我们不妨来设想一个场景中的三种情况：

• 在课堂中，老师在课堂上提问你，这道题的答案是什么，在通常情况下，你回答了老师，老师会对你说“OK”，但如果你在回答的时候没有说清楚，老师可能会让你“重复一下你的回答”，人们是这样的，协议亦是如此。在接收方收到正确的分组时，它会告诉发送方一个肯定确认（ACK），相反就告诉发送方一个否定确认（NAK）。
• 现在再次回到我们的课堂场景，在老师向你提出“请重复一遍你的回答”后，你会再向老师说一遍这个答案。在协议中，如果接收方给发送方一个否定回答，那么发送方将会重传该分组，基于这样重传机制的可靠数据传输协议称为自动重传请求协议（ARQ）。
• 最后再来思考一个问题，老师可以辨别你答案是否清楚明确是因为老师有自己的判断机制，当你没说清楚时老师可以直接听出来。那么放在协议中，接收方怎么知道发送方传的分组是错的呢？还记得在学习UDP的时候，UDP校验和提供了差错检测功能，在rdt协议中，我们同样可以使用校验和来进行差错检测。

至此，针对经有比特差错信道的可靠数据传输，rdt也通过了上述三种功能来解决它，即差错检验、接收方反馈以及重传。以下为rdt2.0中发送方与接收方的FSM，我们分别来盘一下：

• 对于发送方：接收上层的数据后，封装好并设置好校验和，发送给接收方后，自身变为等待ACK或NAK的状态，若收到接收方的NAK，则重发分组；若收到接收方的ACK，发送方转变为等待上层调用的状态。
  • 需要注意的是，发送方在等待ACK或NAK状态时不能从上层获得更多的数据，即不会出现rdt_send()事件，发送方也不会发生新的数据，仅当接收到ACK离开此状态才会继续发送新的数据。这样的协议被称为停等协议。
• 对于接收方，接收分组后
  • 如果corrupt（腐败），代表没有通过校验，即发生了比特差错，则发送NAK给发送方。
  • 如果notcorrupt（未腐败），代表通过校验和，则发送ACK给发送方。

rdt2.1（解决rdt2.0的致命缺陷）

在刚刚的rdt2.0的假设中，我们只考虑到了分组在传输信道中受损的情况，如果接收方给ACK，发送方就传下一个分组，如果接收方给NAK，发送方就重传当前分组，但我们没有考虑到ACK或NAK分组受损的可能性。即如果接收方给发送方的ACK或NAK受损后变成了“乌拉乌拉”，那么2.0的发送方将直接懵比，所以为了解决这个问题，我们让发送方对其数据分组进行编号。而编号也并非需要很多序号，只需要0,1两个即可，分别表示前一个分组以及一个新分组两种状态。以下为rdt2.1中发送方和接收方的FSM，一眼看上去好像很复杂，我们一点点来看：

发送方

大概可以看出发送方的状态数变成了2倍，因为要区分0和1

• 上层通过rdt_send()调用后，打包分组，设置好校验和发送，这和rdt之前的版本无任何区别
• 发送分组0后，发送方转换为等待ACK或NAK0状态
  • 若接收方给出ACK，则转换为等待上层的调用1状态
  • 若接收方给出NAK0或接收方给出的确定受损，给出“乌拉乌拉”，则重发0号分组，直到收到ACK
• 发送1号分组以及等待ACK或NAK1两个状态和上面相同，不再说明。

接收方

通过大体的浏览这个图我们大概可以看出来接收方一个状态是有三个动作的，我们一个个来看，还是拿收到分组0来看，分组1原理相同

• 收到分组0，但corrupt（校验出错），发送NAK给发送方
• 收到分组0，校验没出错，发送ACK给发送方，自己转换到等1的状态
• 在等0的时候收到了1（左二行），则发送ACK给发送方，因为只有这样发送方才能发1

其中第三点需要注意一下，在等0的时候收到了1，就意味着接收方自己在上一次的分组确认受损了，导致发送方收到了乌拉呜啊，就重新把上一个分组发送了一遍，此时接收方要给出ACK确认该分组，使发送方发送下一个分组

为了方便理解，贴一张实际运行中可能出现的情景：

rdt2.2（无NAK)

rdt2.2在功能上和2.1无任何区别，只是把否定确认NAK变为对前一个分组的ACK，即如果收到1，校验失败，按照rdt2.1应发送NAK给发送方，在rdt2.2则直接发送ACK0即可，这样就可以实现一个无NAK的可靠数据传输协议。

这里还是带入一个生活中的例子，是中科大的郑老师在课堂上讲的，觉得很有意思，这里也分享出来。假设一个女生问你：我温柔吗？你觉得她很温柔，于是回答她：你很温柔。接着她问你：我漂亮吗？你觉得她在你心中不漂亮，于是你回答她：你很温柔。这就是rdt2.2，对本次分组的否定用对上一个分组的肯定来代替。如果按rdt2.1的逻辑来，你应该直接回她：你不漂亮。

所以rdt2.2发送方和接收方的FSM和2.1的区别就在于，等待ACK或NAK的状态变为等待ACK0（等0的情况）。

rdt3.0（经有比特差错的丢包信道的可靠数据传输）

在前面的讨论中我们主要针对比特差错进行了学习，但在数据传输时，除了数据可能会出差错外，丢包也是经常会出现的问题（丢包包括丢数据或丢确认信息），那么针对丢包，我们又该如何解决呢？解决步骤大概分为两步，第一步就是如何检验丢包，第二步就是检查出丢包后我们该做些什么。

我们令发送方负责检查和恢复丢包工作，采取的方法是让发送方选择一个时间值，如果在这个时间内没有收到确认信息，就判定发生了丢包。之后将重新传该分组。（一个分组如果经历了很长的时延，发送方可能会重新发送）

既然设置了一个时间值，我们就需要一个倒计数定时器来计时，如果timeout，则判定丢包，重发分组。所以发送方应做到：

• 每发送一个分组，启动一个倒计数 定时器
• 响应定时器中断
• 终止定时器

rdt3.0发送方的FSM：在分析是还是拿发送0来举例

• 收到上层调用后，打包分组，设置好校验和，启动计时器，发送后进入等待ACK0状态
• 若接收方给出ACK1或乌拉乌拉，重发0，这是rdt2.2的内容
• 若接收方校验成功，给出ACK给发送方，则发送方停止这个分组的计时器
• 若在等待ACK0状态中一直没有收到确认信息，等待超时后，重传该分组。

以上就是发送方的动作，接收方的动作和rdt2.2相同，因为解决丢包这事全是发送方干的。为了便于理解，这里还是贴一张实时运行中可能出现的情况，因为无丢包出现的时候流程和rdt2.2相同，所以这里只画出 出现丢包操作时的流程

流水线可靠数据传输协议

rdt3.0，在功能上已经是一个完备的协议，但它的性能并不高，原因就在于它是一个停等协议，发送一个分组时单独占用一个信道，后一个分组必须等前一个分组传完之后才能传，也就是说发送方一次只能发送一个数据，它的信道利用率是极低的，就像这样：

我们解决这个问题的一个方法就是不以停等的方式运行，允许发送方发送多个分组无需等待，即：

发送方一次发送多个分组的方式称为流水线（pipeline）技术 ，对于流水线技术，我们应该注意：

• 增加序号范围，每个在传输中的分组必须有唯一序号，可见之前的0和1已经不能满足流水线的需求。
• 发送方和接收方需要缓存多个分组。
• 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏以及延时大的分组。

其中第三点是摘抄的top-down原话，要很好的解释它，我们必须先引出滑动窗口的内容。

滑动窗口（Slide Window）协议

在了解什么是滑动窗口之前，我们先回忆一下之前的内容。rdt协议中，发送方一次发送一个分组，接收方一次接收一个分组。但是人们不满足rdt协议的性能，于是提出流水线技术，使发送方一次发送多个分组，所以发送方需要缓存多个分组，按照缓存区内分组的不同类型，我们大概可以分为以下几种：①已发送且被确认的分组 ②已发送但未被确认的分组 ③待发送的分组

我们把已发送但未确认的分组和待发送的分组的区域称为发送缓冲区，图中N即为缓冲区的大小

把已发送但未确认的分组构成的空间称为发送窗口。可以发现，发送窗口是发送缓冲区的一部分。

• 发送窗口的后沿等于发送缓冲区的后沿
• 发送窗口的前沿不超过发送缓冲区的前沿
• 之后讨论的移动是指发送窗口在移动，发送窗口在0-N之间变化

关于以上的内容在第一次写这篇文章时一直没想明白，就去科大底下提问了，郑老师也很好的解答了我的疑惑：

我们知道，rdt一次只能发送一个分组，所以sw = 1（send window我们简称为sw，接收窗口简称为rw），而流水线技术中，一次可以发送多个分组 ，所以sw > 1。而事实上，不仅是sw可以>1，接收窗口rw也可以>1，即一次接收确认多个分组。下面用一张表格来表示其中的关系：

至此，我们再次回到那就摘抄的话：所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏以及延时大的分组。这句话的后半句是：解决流水线的差错恢复有两种基本的方法：回退N步（GBN）和选择重传（SR）。下面我们就分别来看一下这两个协议。

回退N步（GBN）协议

首先我们来考虑，在正常情况下GBN协议中发送方和接收方两窗口的互动。对于发送窗口，可以参考上面的图。

其中有以下几点需要注意：

• 因为rw = 1，GBN协议一次只能确定接收1个分组
  • 所以GBN协议只能顺序接收，只有当收到最低序号的分组（代表顺序正确），才发送ACK给发送方

😴分割线——————————————————————————————————————————————————-

那么以上就是正常情况下GBN协议两窗口的互动，在开始讨论异常情况前，我们要先清楚，对于GBN，什么是异常情况？答案即为乱序以及丢失。在上面说到，GBN只能顺序接收，所以先收到乱序的分组，我们要有解决方法。而丢失就更不用说了。下面给出异常情况下GBN协议两窗口的互动情况：

• 收到乱序分组时，因为没有落入接收窗口的范围内，接收方只能丢弃。
• 重复发老分组的ACK给发送方后，发送方发后沿不移动，所以从上层新来的分组不能进入发送缓冲区。
• GBN只有一个计时器，这点是和rdt不同的，定时器的工作机制为
  • 如果收到一个ACK，此时还有已发送但未确认的分组，则定时器重新启动。
  • 如果收到一个ACK后，没有已发送但未确认的分组了，则停止该计时器。
• 当触发超时重传后，发送方将重传所有已发送但未被确认的分组，这就是所谓的回退N步。

这样的工作机制保证了该定时器可以当做最早发送但未被确认的分组的定时器

关于GBN异常情况我们这里举一个栗子🌰：

发送方发送0,1,2,3,4,5给接收方，我们假设分组2会丢失，由于接收方只能顺序接收，所以流程为：

• 收到0，回复ACK0，后沿向右移动
• 收到1，回复ACK1，后沿向右移动
• 未收到2,2在中途丢失
• 收到3，因为2没到来，所以接收方只能丢弃3并继续回复ACK1，此时发送发收到ACK且仍有已发送但未确定的分组（2），于是定时器启动。此时后沿不动
• 收到4，回复ACK1
• 收到5，回复ACK1
• 某一时刻，定时器timeout，发送方重新发送2,3,4,5

​

最后我们再来通过GBN协议中发送方和接收方的FSM来梳理一下GBN协议

发送方

• 发送窗口初始值为0（nextseqnum - base）
• 收到上层rdt_send()调用后，判断是否在可发送范围内
  • 在可发送范围内：发送，并启动定时器，前沿向右滑动
  • 在可发送范围外：没法发送（发送缓冲区用完）
• timeout超时：重新启动定时器，重传所有已发送但未确认的分组
• 收到确认：后沿向右滑动

选择重传（SR）协议

SR协议和GBN协议相同，都使用了流水线技术，使sw>1，SR和GBN的不同点在于，SR协议的RW>1，即SR协议可以接收确定多个分组。和发送窗口一样，SR协议也有接收窗口。

在正常情况下，SR协议的两窗口互动和GBN协议的相同，在之前我们也提到过，这两种的不同点在于处理异常情况的方式不同。因为SR的rw>1，可以确认接收多个分组，也就是说，如果收到乱序分组，不必抛弃，可以把它缓存起来。下面给出异常情况下SR协议两窗口互动：

除了接收窗口和GBN不同之外，SR协议为每个发送的分组都设置了一个定时器，不同于GBN协议只有一个定时器。这样在触发超时重传时，只需发送超时的那个分组即可。

这里拿GBN协议中举的栗子🌰继续看一下：

发送方发送0,1,2,3,4,5给接收方，我们假设分组2会丢失，流程为：

• 收到分组0，发送ACK0，后沿滑动
• 收到分组1，发送ACK1，后沿滑动
• 分组2在发送过程中丢失
• 收到分组3，发现是乱序，缓存起来，发送ACK3，后沿不滑动
• 收到分组4，发现是乱序，缓存起来，发送ACK4
• 收到分组5，，发现是乱序，缓存起来，发送ACK5
• 直到某个时刻，分组2的定时器timeout，重传分组2

​

对比GBN和SR

不难发现，GBN 和 SR 的优点和缺点是互相对应的，所以我们可以构想出它们的适用场景

• 出错率低时，适合GBN
• 链路容量大（延迟大，带宽大）时，适合SR，因为一旦出错GBN代价很大。

结语

那么以上，就是计算机网络——可靠传输原理 的内容，敲了大概一整天的时间，6000字，目前也是我写过字数最多的博客了。在这之后就要进入TCP的学习了，到时候如果感觉想写东西的话也许会写一篇tcp的长文。