发布于   更新于 计算机网络 可靠数据传输

附

  1. rdt_send()函数：上层可以调用数据传输协议的发送方。其中 rdt 为 reliable data transmission。

    它将要发送的数据交付给位于接收方的上层。

  2. rdt_rev() 函数：当数据被交付给接收方时，接收方调用这个函数。

  3. deliver_data() 函数：当接收方想要将数据交付给高层，利用此函数将数据交付给高层。

  4. 在本文中，仅考虑单向数据传输的情况，即数据从发送端到接收端。

构造可靠数据传输协议

让我们来从特殊到一般，一步步地从完全可靠的信道到不可靠的信道，最终得到一个完美的，可靠的数据传输协议。

经由完全可靠信道的可靠数据传输：rdt 1.0

这是最简单的情况，底层信道是完全可靠的。让我们称呼这个协议为rdt 1.0。

在这种情况下，所有数据包将会从发送方毫无错误地、不会改变顺序地发送给接收方。

这个协议中的发送方和接收方的状态如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* rdt 1.0 发送方
*/
/*
* 上层
*/
rdt_send(data)
——————————————
/*
* 下层
*/
packet = make_pkt(data)
udt_send(packet)

发送端只通过rdt_send(data)函数接受来自上层的数据，并产生一个分组，之后将分组发送给信道。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* rdt 1.0 接收方
*/
/*
* 从更下层接收数据
*/
rdt_rcv(packet)
———————————————
/*
* 下层
*/
extract(packet,data)
deliver(data)
———————————————
/*
* 上层接收
*/

rdt通过rdt_rcv(packet)从更下层接收接收分组，取出数据，并将其交付给上层deliver(data)。

在这个简单的协议中，一个单元数据和一个分组没有区别，而且所有分组都是从发送方到接收方。有了完全可信的信道，接收方不需要提供任何反馈给传送方（假定接收方和传送方接收数据的快慢是一样的），接收方也没有必要让发送方慢一点。

就像老师教学霸一样，教一点学霸都会了，而不必像给我们这帮子学渣讲课。

经具有比特差错的可靠数据传输：rdt 2.x

rdt 2.0

在这种情况下，底层信道在分组的传输、传播、分组的过程中，可能会有比特差错。但是所有数据包还是会从发送方不会改变顺序地发送给接收方。

就像我们在和别人交待一件很长的事情时，往往会在听清楚一件事情的时候回复一句ok，而当没有听清楚的时候，会让对方重述一遍之前说过的话；在tcp中同样采用了这种方式，其利用控制报文让发送方知道，哪些分组被正确接收，哪些分组有误并需要重复。基于这种机制的可靠数据传输协议被称为：自动重传请求（ARQ）协议。

而ARQ协议还需要另外几个功能来处理出现比特差错的情况：

  • 差错检测。这项技术需要额外的比特来做校验位，这些比特将被汇集在rdt2.0数据分组的分组检测和字段中。
  • 接收方反馈。反馈接收状况，如果
  • 重传。

这个协议中，发送方和接收方的状态情况如下：

发送方第一次发送数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* rdt 2.0 发送方
* 当第一次发送时
*/
/*
* 从上层接收data
*/
rdt_send(data)
——————————————
/*
* 使更下层接收分组
*/
sndpkt = make_pkt(data,checksum)
udt_send(sndpkt)
——————————————
/*
* 进入等待控制报文状态
*/

可以见到，rdt 2.0 中，发送方在第一次发送时与第一次发送的时候是几乎一样的，除了增加了一个checksum这个差错检测和。

发送方在发送完毕后，进入等待控制报文状态。

接收方接收数据

此时，接收方的状态为：

接收到正确的分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
* rdt 2.0 接收方
* 接收到正确的分组
*/
/*
* 从更下层接收数据
*/
rdt_rcv(rcvpkt)&&notcorrupt（rcvpkt)
———————————————
/*
* 下层
*/
extract(rcvpkt,data)
deliver(data)
———————————————
/*
* 上层接收data
*/
———————————————
/*
* 使更下层接收ACK分组
*/
sndpkt=make_pkt(ACK)
udt_send(sndpkt)
———————————————
/*
* 恢复等待下层调用状态
*/

当分组未受损的时候，接收方下层从更下层接收数据，通过校验确认数据没有比特差错，一边将data向上传输给上层，一边想更下层发送含有ACK的控制报文，来反馈接受情况。

接收到错误的分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* rdt 2.0 接收方
* 接收到错误的分组
*/
/*
* 从更下层接收数据
*/
rdt_rcv(rcvpkt)&&corrupt（rcvpkt)
———————————————
/*
* 更下层 接收NAK分组
*/
sndpkt=mak_pkt(NAK)
udt_send(sndpkt)
———————————————
  /*
  * 恢复等待下层调用状态
  */

当分组受损的时候，接收方下层从更下层接收数据，通过校验确认数据有比特差错，向更下层发送含有NAK的控制报文，来反馈接受情况。

发送方接收到控制报文

发送方处于等待控制报文时，它不可能从上层获取更多的数据；即rdt_send()事件当且仅当接收到ack并离开等待控制报文的状态时才能够发生。所以，rdt 2.0 协议为停等协议。

接收到ACK控制报文
1
2
3
4
5
6
7
8
9
10
11
12
/*
* rdt 2.0 发送方
* 当收到ACK
*/
/*
* 下层
*/
rdt_rcv(rcvpkt)&&isACK(rcvpkt)
———————————————
/*
* 等待从上层接收data
*/

收到一个ACK分组，发送方确认分组已被正确接收，回到等待调用状态。

接收到NAK控制报文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* rdt 2.0 发送方
* 当收到NAK
*/
/*
* 下层
*/
rdt_rcv(rcvpkt)&&isNAK(rcvpkt)
———————————————
/*
* 重传
* 更下层 接收重传分组
*/
udt_send(sndpkt)
———————————————
/*
* 进入等待控制报文状态
*/

收到一个NAK分组，发送方确认分组未被正确接收。重传上个分组，并重新进入等待控制报文状态。

太好了，我们终于在有比特差错的通信链路上建立了一个可靠传输协议，让我们来欢庆下吧！！

·······

等等，万一这些控制报文出错了，那该怎么办？1变成0，0变成1，具有比特差错的报文被发送方认为正确接收了，不具有比特差错的报文被发送方重传了，损害了可靠数据传输，也让效率变慢了！

不行，要想一个法子！

  • 检测差错
  • 纠正差错。

处理的方法如下：

  • 问接收方，你说啥？接收方说，我说这！并陷入无限循环。
  • 增加足够的校验位，使发送方不仅可以检验，还使得分组具有自纠错能力。
  • 要求接收方重传报文。

rdt2.1

解决这个新问题的一个方法是在数据分组中添加一个新的字段，即该分组的序号。于是接收方只需要检查序号就能够明白这个分组是不是重传的。

发送方发送数据 序号0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
* rdt 2.1 发送方
* 序号 0
* 当第一次发送时
*/
/*
* 从上层接收data
*/
rdt_send(data)
——————————————
/*
* 使更下层接收分组
*/

udt_send(sndpkt)
——————————————
/*
* 进入等待控制报文状态0
*/

在这个发送过程中，除了制造包的时候，多了一个序号（，其他的和rdt2.0相同。

接收方接收数据 序号0

ACK NAK分组无需序号。

接收到正确的分组 序号0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
* rdt 2.1 接收方
* 接收到正确的分组
* 序号 0
*/
/*
* 从更下层接收数据
*/
rdt_rcv(rcvpkt)&&notcorrupt（rcvpkt)&& has_seq0(rcvpkt)
———————————————
/*
* 下层
*/
extract(rcvpkt,data)
deliver(data)
———————————————
/*
* 上层接收data
*/
———————————————
/*
* 使更下层接收ACK分组
*/
sndpkt=make_pkt(ACK,checksum)
udt_send(sndpkt)
———————————————
/*
* 等待下层调用状态
* 序号 1
*/

注意到，回传的控制分组多了一个checksum使得发送方能够检验回传的分组是否受损。

接收到错误的分组 序号0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* rdt 2.1 接收方
* 接收到错误的分组
* 序号 0
*/
/*
* 从更下层接收数据
*/
rdt_rcv(rcvpkt)&&corrupt（rcvpkt)
———————————————
/*
* 更下层 接收NAK分组
*/
sndpkt=mak_pkt(NAK, checksum)
udt_send(sndpkt)
———————————————
  /*
  * 恢复等待下层调用状态
  * 序号 0
  */

发送方接收控制报文 序号0

接收到ACK控制报文 序号0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* rdt 2.1 发送方
* 当收到ACK
* 序号 0
*/
/*
* 下层
*/
rdt_rcv(rcvpkt)&&notcorrupt(rcvpkt)&&isACK(rcvpkt)
———————————————
/*
* 等待从上层接收data
* 序号 1
*/

收到一个ACK分组，发送方确认分组已被正确接收，回到等待调用状态。

接收到NAK控制报文 序号 0 接收到错误控制报文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
* rdt 2.1 发送方
* 当收到NAK
* 序号 0
*/
/*
* 下层
*/
rdt_rcv(rcvpkt)&&(isNAK(rcvpkt)&&corrupt(rcvpkt))
———————————————
/*
* 重传
* 更下层 接收重传分组
*/
udt_send(sndpkt)
———————————————
/*
* 进入等待控制报文状态
* 序号 0
*/

收到一个NAK分组，发送方确认分组未被正确接收。重传上个分组，并重新进入等待控制报文状态。

或收到一个错误报文，重传上个分组，并重新进入等待控制报文状态。

发送方发送数据 序号1

当发送方发送过一条数据，且接受到了来自接收方的ACK， 发送方和传送方进入序号1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
* rdt 2.1 发送方
* 序号 1
* 当第一次发送时
*/
/*
* 从上层接收data
*/
rdt_send(data)
——————————————
/*
* 使更下层接收分组
*/
sndpkt = make_pkt(1,data,checksum)
udt_send(sndpkt)
——————————————
/*
* 进入等待控制报文状态1
*/

在这个发送过程中，除了制造包的时候，将序号改为1，其他正常。

接收方接收数据 序号1

此时，须考虑数据分组是否有失序问题。为此比起rdt2.0，在判断包的是否正确时，需要对其序号进行校验，即

rdt_rcv(rcvpkt)&& notcorrupt（rcvpkt)&& has_seq1(rcvpkt)

若has_seq0(rcvpkt)判断为失序，回传ACK控制分组，并继续保持进入等待下层调用状态 序号1。

此处为整个协议的难点。在解释之前还需要再重申一遍，rdt2.1协议不会丢失分组，不会丢失分组，不会丢失分组。是停等协议，是停等协议，是停等协议。

那让我们假设一种情况。定义两个整型A,A+N。假设现在已经进行到了A+N轮传送序号为1，但是现在接收到A轮序号为0的分组。接收方接收到了，回传一个ACK，保持着0。发送方接收到ACK，发送序号为1的分组。你觉得这里就出错了？

拜托，在此之前，发送方就已经把A+N轮，序号为0的包发过来了，而且序号为0的分组肯定比序号为1的分组先到达，所以并不会丢失分组，放心好了。

如若正确，则回传一个ACK控制分组，进入等待下层调用状态 序号0。

rdt2.2

该协议仅使用确认ACK完全摒弃掉了NAK，在ACK报文中添加一个参数ACK0 ACK1。当收到0的时候，发送方改变序号并进入下个状态。收到1时，和NAK效果相同。

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

现在假定除了比特受损，底层信道还会丢包。所以协议需要处理另外两个问题：如何检测丢包，发生丢包后该做什么。在rdt2.2中使用的技术，如检测和、序号、ACK分组、重传。

在这里，我们让发送方来对于丢包进行检测，和恢复工作。假定发送方传输一个数据分组，该分组丢失或者接收方发送的ACK分组发生了丢失。发送方在等待一段时间后，认定该分组已丢失，它只需要重传该数据分组即可。 而有时因为时延过大，即使数据分组未丢失，发送方也需要重传分组，而这引入了冗余分组，所以发送方需要引入和rdt2.2中的序号，还有定时器技术。而定时器需要满足以下作用：

  1. 当发送一个数据分组时（无论第一次发送或是重传）都需要启动一个定时器。
  2. 发送方需要在定时器超时后，启动重传程序。
  3. 发送方需要在接收到具有合适序号的ACK时结束定时器。

由于分组的序号总是在0和1之间交替，rdt3.0有时又被人称为比特交替协议。

小结

我们从最特殊的情况rdt1.0出发，这个协议所依靠的是完全没有错误的乌托邦信道。

但现实是骨感的，为了纠正在现实中可能有的比特错误，我们在rdt2.0中引入了`控制报文、差错校验，对于出错的分组我们采用了重传的方法，解决了不少的问题。

我们接着为了解决接收方回传的控制报文可能有的比特差错，在控制报文中加入了校验和和序号字段，而这构成了rdt2.1协议。

rdt2.2协议在rdt2.1的基础上取消了否认确认，而是只选择肯定确认，并利用冗余ACK来代替否认确认的位置。

rdt3.0是建立在有错误还会丢包的信道上，在这里我们引入了倒数计时器，并能够响应计时器的中断。

至此，我们得到了一个可靠数据传输协议。

性能优化

但是不论是最初的协议也好，最终的协议也罢，它们都是一个停等协议，而这对不断追求快一点，再快一点在某些方面需要慢一点人们来说，这样的效率是致命的。

让我们假设一下，两个端系统分别位于美国的东海岸和西海岸，在这两个端系统间的光速传播RTT为30ms，假设彼此之间通过一条1Gbps的信道相连。包括首部行和数据的一个分组的大小为1000字节，发送一个分组进入链路的时延为：t = L/R = (8000b/pkt)/(10^9bps) = 8μs/pkt，这说明：发送端在 t = 0 时刻开始发送分组，则在 8μs 后，该分组全部进入了发送端信道。接着该分组经过1/2RTT=15ms 的旅途到达接收端，即该分组的最后 1 bit 在时刻 t = RTT/2 + L/R = 15.008ms 时到达接收端。假设 ACK 分组很小，可以忽略其发送时间，且接收端一旦收到一个数据分组的最后 1bit 后立刻发送 ACK，则 ACK 在时刻 t = RTT + L/R = 30.008ms 时回送到发送端。也就是说，经过 30.008ms 后发送端才可以发送下一个分组。

设发送端利用率为：发送端实际忙于将发送比特送进信道的那部分时间与发送时间之比。则

U_sender = (L/R) / (RTT + L/R) = 0.008 / 30.008 = 0.00027

可以看到，利用率极其低下，这是不可容忍的，所以我们需要改进性能。

而我们需要一种特殊的方法来提升协议。而这个方法便是我们的老朋友，流水线。

所以我们新的性能upup的协议必须带有一下功能：

  1. 增加序号范围。而且信道中可能还有其它没有被确认的分组，这些分组肯定不能被混淆，所以每个被输送的报文必须要有唯一的序号来确定其唯一性。而这需要增加序号字段的比特数。
  2. 发送方和接收方必须缓存更多的分组。发送方需要缓存那些已发送但未确认的分组，接收方也可能需要缓存一些已经正确接收的分组。
  3. 序号范围和缓冲的要求视如何处理丢失、损坏、高时延的分组而定。

解决流水线的差错恢复问题主要有两种方法：回退N步（GBN），选择重传（SR）。

回退N步（GBN）

对于gbn协议，我们允许发送方发送多个分组，而不需要等待确认，但它依然受到在流水线中未确认的分组数不能超过某个最大允许数N。

让我们假设一个队列q<pkt>，让我们定义这个队列中的一个基序号为base，而base前（不包含base）为已经发送的pkt，定义nextseqnum为该队列中的尚未发送的分组中的第一个分组，则base——nextseqnum-1为发送但待确认的。假设队列中从base开始到可用但未发送的分组数量为N，N被称为窗口长度。大于base+N的序号直到当前流水线中未得到确认的分组得到确认才可使用。

一个分组的序号长短取决于分组序号字段的比特数k，所有涉及到序号的运算必须模除2^k，就像环状队列一样。

对于接下来的讨论，我们都假定gbn协议只使用肯定确认。

对于发送方

gbn协议需要响应如下事件：

  • 当接收到上层的调用时：首先检测发送窗口是否已满：

    • 若未满，则产生一个分组并将其发送，并相应地更新变量。
    • 若已满，将数据返回给上层，隐式地指示上层该窗口已满。

  • 收到一个ACK：

    在 GBN 协议中，对序号为 n 的分组的确认采取累积确认（cumulative acknowledgment）的方式，表明接收方已正确接收到序号为 n 的以前且包括 n 在内的所有分组。

  • 超时事件：

    如果出现超时，发送方重传所有已发送但未被确认过的分组。(即base——nextseqnum-1)

对于接收方

假设接收方已经正确接收并确认了前M个分组（从0开始编号），如果此时接收到序号为M的分组，接收并回传ACK M，对于其他情况，接收但丢弃，并回传ACK M-1。

GBN协议的意义

虽然蠢但有意义。因为协议必须保证分组的按序交付，并且缓存未按序到达的分组并没有必要，因为GBN协议会在超时时重传所有发送但未确认的分组。

但：GBN仍然有它自己的性能问题，尤其是当窗口长度和带宽时延都很大的时，流水线中有很多分组时，任何单个分组的差错就能引起 GBN 协议重传大量分组，事实上是很多分组根本没必要重传。

选择重传（SR）

SR 协议在 GBN 协议的基础上进行了改进，它通过让发送方仅重传那些它怀疑在接收方出错（即丢失或受损）的分组而避免了不必要的重传。选择重传协议只重传真正丢失的分组。但这种个别的、按需的重传要求接收方逐个地i确认正确接收的分组。

对于发送方

发送方需要对以下事项进行响应：

  1. 从上层接收数据。发送方检查序号：
    1. 若在窗口内，则发送。
    2. 若不在，要么缓存，要么返回数据。
  2. 超时。但定时器被用于每一个被发送的数据分组，因为超时发生只重传一个分组。
  3. 收取ACK。假设ACK在窗口中，标记该序号为已接收。特别地，当ACK的序号等于send_base时，发送窗口将后移至序号最小的，且未确认分组处。如果窗口移动并且窗口内有未发送的分组，将对这些分组进行发送。

对于接收方

在SR中，接收方同样有接收窗口，其基序号为rcv_base窗口大小为N。接收方需要对以下事务进行响应：

  1. 假设分组的序号落在窗口内：

    若该分组是第一次被接收的，缓存，并回传带有该分组序号的ACK控制报文。特别地，假设该序号等于基序号，则该分组和该分组后的连续的分组将被上交。

    假设现在基序号为2，缓存的有：3、4、6，若收到序号为2的分组，则分组2、3、4将被上交。

  2. 假设分组序号落在接收窗口前：

    回传ACK。

    假设接收方不回传ACK，则发送方将一直向接收方传送该分组，并且发送窗口无法向前滑动，形成死锁。

  3. 其他情况。忽略。

对于SR窗口选择

选择重传协议的接受窗口尺寸rcv_window和发送窗口尺寸send_window都大于1，一次可以发送或接受多个。若采用n比特对分组编号，为了保证接收方向向前移动窗口后，新窗口序号与旧窗口序号没有重叠部分，窗口长度必须小于或等于序号空间大小的一半。

在这个例子中，有四个分组序号 0、1、2、3 且窗口长度为 3。假定发送了分组 0 至 2，并且接收方被正确接收且确认了。此时，接收方窗口落在 4、5、6 个分组上，其序号分别为 3、0、1.现在考虑两种情况：

  1. 如上图中的 a 图所示，对前 3 个分组的 ACK 丢失，因此发送方重传这些分组。因此，接收方下一步要接收序号为 0 的分组，即第一个发送分组的副本。

  2. 如上图中的 b 图所示，对前 3 个分组的 ACK 都被正确交付。因此发送方向前移动窗口并发送第 4、5、6 个分组，其序号分别为 3、0、1.序号为 3 的分组丢失，但序号为 0 的分组到达（一个包含新数据的分组）。

显然，接收方并不知道发送方那边出现了什么问题，对于接收方自己来说，上面两种情况是等价的。没有办法区分是第一个分组的重传还是第 5 个分组的初次传输。所以，窗口长度比序号空间小 1 时协议无法正常工作。但窗口应该有多小呢？

答案是：窗口长度必须小于或等于序号空间大小的一半。

存疑

总结

到了这里，我们终于构建出了性能强大并且可用的可靠数据传输服务了，我们可以重新开始在rdt2.0协议所停止的欢庆了。在现在可能随着后面的学习，你可能会产生一种思维定势：即我们所讨论的下层、较下层、上层，你会直接用运输层、网络层和应用层所替代，而所说的分组你可能直接将它认定成为报文段。但是请明白一件事情在tcp/ip五层协议栈的顶部四层实际上都可以依托我们刚才所讨论的东西来提供可靠数据传输服务的。

尾巴

这些东西是我在刚开学的时候看的，当时看有限状态机看的我一头雾水，网络上对于我的迷惑也没有很多的解答，当时真的是感觉糟糕透了，但是我还是硬着头皮往下看，看完之后利用winshark做了一些抓包，并分析了一下数据，再结合着mooc，算是解决了我不少的迷惑。但是在写博文的时候之前有一些迷惑还是重新浮上心头，比如冗余确认，再比如看SR协议有一种想要撕书的冲动（当然贫穷让我清醒），再比如到现在还是对于SR接收方窗口大小存在疑惑，但是问题既然出来我们就应当高兴，并且应当怀着高兴的心情去解决它，最后发表下感想（水博文）。

写这篇博文写了将近三天，到这里施工的总字数已经到达6300余字了，算是比较长的博文了。现在也是后半夜了，该洗洗刷刷睡觉了。

天黑了

星闪烁

大海静悄悄

宝宝乖，乖宝宝，快快睡觉

转啊转啊

一只小船漂浮在大海上，渐渐的越飘越远

收起小船帆

点亮小灯光

带你去和花园宝宝一起玩…….

相关文章
评论
分享
返回顶部
Please check the post_relate setting in config.yml of hexo-theme-Annie! You should make sure 'postsEnable == true' and the number of site posts greater than 1.
Please check the comment setting in config.yml of hexo-theme-Annie!