可靠传输协议- 校招VIP

文章声明：转载来源：https://blog.csdn.net/pshizhsysu/article/details/44963101

所谓可靠传输协议，通俗一点说，就是发送方给接收方发送数据，接收方保证能正确接收到数据。
一个可靠传输协议一般需要有三个性质：ACK、超时重传、序列号（数据包的序列号与ACK的序列号）。

ACK肯定不用说必须有，否则如果没有ACK， A 给 B 发送数据包，A都不知道B到底有没有收到。

再说超时重传，先看最简单的情况，A每次只能发送一个数据包给B，而且要收到ACK后才能发送下一个数据包。

假设A发送数据包P1给B，A收不到ACK有可能是P1丢失了，也有可能是ACK丢失了。
由于A无法判断是哪一种情况，所以只要没收到ACK，必须重传。
但关键是，发送一个数据包后，A需要等多久，才开始重传呢。
如果等待时间过短，说不定重传后就接收到了”迟到“的ACK。

那么换句话说，A发送一个包P1后，等待多长时间，能够保证之后不会再收到P1的ACK。
我们假设一个包在网络中的最大生存时间为MST（也就是说，经过MST时间后，如果该包还在网络中，就应该把它丢弃），思考一下，发现A的等待时间应该设为 2*MST。
等待这个时间后，A是肯定收不到ACK的。

通过上面的分析发现，每次发送一个包时，即使没有序列号也能保证数据包之间传输的可靠性。没错，情况就是这样的。

接下来我们分析如果每次能发送多个包的情况，为了更直观分析，就两个吧。

假设
A给B发送两个数据包P1、P2（假设如果没有丢包，那么先发送的包先到达），如果B收到P2后，P1丢失了，那下次收到重传的P1时，岂不是重组数据时把P2放到了P1的前面（因为如果包没有序列号，只能是谁先到，重组的时候谁放在前面）.
所以数据包一定要有序列号。

假设
ACK没有序列号，当A发送了两个数据包，丢失了一个包，A只收到了一个没有序列号的ACK，那么A该如何判断是哪个包丢失了呢；
所以呢，ACK的序列号也是必需的。
通过以上的分析发现，在A可以同时传多个数据包时（实际上就是滑动窗口大于1），数据包与ACK都必须要有序列号。

接下来我们要分析，当接收方收到不按顺序到达的数据包时该如何处理。

假设
P0已经被正确接收，P1还没有收到，当收到P2时，接收方该如何处理这个包呢？
丢失它？还是先把它缓存起来然后等P1正确接收后再交给上层协议？

所以这时就有两种选择：
（1）数据包不按顺序到达时，接收方同样正确接收，然后把它们缓存起来。
当然，接收方不可能缓存无数多个包，所以要指定一个大小，也就是所谓的接收窗口大小。

假设接收窗口的大小为N（即最多能缓存N个数据包）且最后一个按顺序接收的包为P(k)（按顺序接收到的包会立即交给上层协议，所以P(0)到P(k)已经交给了上层协议）。
那么如果此时收到P(k+1)就把P(k+1)交给上层协议，如果此时收到的不是P(k+1)而是P(k+2)到P(k+N)中的若干个，
不妨假设为P(k+1)和P(k+N)两个，则把它们都缓存起来，若之后收到P(k+1)就把P(k+1)和P(k+2)交给上层协议，然后又可以开始缓存P(k+3)到P(k+N+2)的数据包。

（2）数据包不按顺序到达时，就把包丢掉。
这种情况我们说，接收窗口的大小为1。

以上可以看出，发送窗口大小为N的实质就是当P(k)被确认后，P(k+1)到P(k+N)可以按顺序发送出去，P(k+N)不需要等到P(k+1)到P(k+N-1)被确认。接收窗口大小为N的实质就是每次能缓存N个数据包。

Selective Repeat
选择重传协议就是上面对应的情况（1），它的发送窗口大小和接收窗口大小都为N。

SR协议中，由于不按顺序到达的包也能够被正常接收，所以接收方收到包P(k)时，应该回复ACK(k)。

超时重传体现在哪里呢？超时重传体现在，每个包都有自己独立的计时器，当一个包P(k)发送出去后，经过2MST后如果没有收到ACK(k)，就重新发送这个包。
这个网站上有很多协议的动画模拟，非常棒
http://wps.pearsoned.com/ecs_kurose_compnetw_6/216/55463/14198700.cw/index.html

以下是一个模拟
在当前时刻，P0已经被确认，那么可以顺序发送P1到P5

当P2的计时器超时时，重传P2（没截图，因为模拟动画的等待时间太长了）

Go-Back-N
GBN对应的是上面的情况（2），发送窗口大小为N，接收窗口大小为1，每次只能按顺序接收包。现在我们分析其该如何回复ACK。

假设P(k)已经被正确接收，交给了上层协议，此时等待接收P(k+1)，如果P(k+1)到达，则回复ACK(k+1)，然后把P(k+1)交给上层协议，继续等待接收P(k+2)；

但如果P(k+1)没有接收到，收到了P(k+2)，怎么办？由于P(k+2)不能交给上层协议，那我们可以做的选择是缓存它，或者丢弃它；
如果我们把P(k+2)缓存起来，那么接收窗口就不能缓存其他数据包了，当P(k+1)到达时，还是要把P(k+2)丢弃掉，用来缓存P(k+1)（每个数据包都要通过缓存交给上层协议）；

综上分析，我们只有一个选择，就是把P(k+2)丢弃掉。
既然把P(k+2)丢弃了，我们就不能回复ACK(k+2)，也不能回复ACK(k+1)，所以只能回复ACK(k)，表示最后一个正确接收的包为P(k)。

接下来我们看发送方收到ACK时如何处理。有两种情况：
（a）收到重复的ACK -- ACK(k)已经收到，不久后又收到了ACK(k)
（b）ACK序号不连续 -- ACK(k)已经收到，ACK(k+1)没有收到，却收到了ACK(k+2)

对于情况（a），GBN的做法是，不理会它。
对于情况（b），当收到ACK(k+2)时怎么办呢？丢掉还是用来确认数据包P(k+2)还是其他？
我们来分析一下收到ACK(k+2)可能的情况，当收到ACK(k+2)时，表示P(k+2)已经被接收方正确接收了，所以P(k+1)也肯定已经被正确接收了，那么ACK(k+2)能同时确认P(k+1)和P(k+2)。

接下来讨论超时重传的问题，如何计时呢？
假设发送方依次发送了P(k+1)到P(k+N)，发送P(k+1)的时间点为t(k+1)，发送P(k+N)的时间点为t(k+N)，在t(k+1+2MST)时刻，如果还没有收到ACK(k+1)，说明永远收不到ACK(k+1)了.
但是，有可能收到ACK(k+2)到ACK(k+N)。

所以，理论上来说，我们应该把计时器设给最后一个发送的包。

But，However，该协议并没有这么做，它把计时器设给了第一个发送的数据包。为什么要这样呢？
原因是当发送第一个包时，协议不知道应用层什么时候会给它第二个数据包的数据，所以当发送第一个数据包时，就要开始计时。
下面是发送方的代码，该代码说的就是对第一个包计时：

rdt_send(data)
{
	if (nextseqnum < base + N) // base = 1, nextseqnum = 1, base is the first package to send
	{
		sndpkt[nextseqnum] = make_pkt(nextseqnum, data, checksum);
		udt_send(sndpkt[nextseqnum]);
		if (nextseqnum == base)
			start_timer;
		nextseqnum++;
	}
	else
		refuse_data(data);
}

但是问题又来了，当第一个包的ACK收到了之后，计时器应该如何调整呢？
在动画模拟的log输出中个人分析出，当第一个包的ACK收到后，重置计时器，对第二个包开始计时，如此向下类推。

下面是动画模拟图
发送P1到P5，但是P1丢失了

此时，当我们收到ACK0时，知道P1包丢失了，但是如果收到四个ACK0，说明P2到P5被接收了啊，重传P1不行么？
答案是不行。因为当接收到第一个ACK0时，我们不知道后面还有几个ACK0，而且当接收到第一个ACK0时，发送方就要反应，所以只能把其丢弃掉。

后续探索
上面讨论的SR是N-N，GBN是N-1模型，当发送窗口与接收窗口的大小不一样，比如发送窗口为5，接收窗口为3时呢？
比如说发送方发送了P1到P5，但是接收方只能接收P1到P3，假如P1到P3刚好丢失，收到了P4和P5，如何处理？
一种解决方案是采用GBN的模式，丢弃P4和P5，回复ACK0，表示P0是最后一个正确接收的包。
但是，如果P1丢失，P2和P3收到了呢？还是把它们丢弃，回复ACK0？
如果这样子的话，它和GBN协议完全没区别了，浪费了接收窗口的两个缓存。
在这种情况下，其实可以回复ACK2和ACK3，把P2和P3缓存起来，发送方收到ACK2和ACK3后知道这两个被正确接收，选择重传P1即可，如果这样的话那么还是每个数据包一个单独的计时器。个人把这种模型暂时称为N-M模型

TCP传输协议
TCP的发送窗口是会变化的，所以它不是单纯的SR协议或者GBN协议，其实我们用上面的N-M模型就可以了（没错，本文最后有提到这种模型，而且还是后面提出的对TCP的一个修改）。但是，刚开始TCP并没有使用这种模型。

我们先来说TCP的一点改进。

我们知道，在现实网络中，应用层给下层协议的数据一般时间间隔一般会很短。

比如：T时刻应用层给一部分数据给下层协议，发送方立即发送一个数据包P1，0.1秒后应用层又给了一部分数据给下层协议，发送方立即发送一个数据包P2。
理想状态下，接收方收到P1，P2的时间间隔很短。接收方接收到一个包就立即回复一个ACK，会使得ACK的数量过多，加重网络的负担。

可不可以接收到P1后稍微的等待一会儿呢，就一会儿，看还有没有其他的包，等待时间结束后，如果收到了P1和P2，只回复一个ACK2，表示ACK2及其以前的包都正确接收了？
哈哈，没错，TCP就是这么干的。

接下来用简单的例子来说明TCP的工作过程。

假设A为发送方，B为接收方，开始时，A先后发送了0-999和1000-1999两个包给B，B接收到0-999后等待0.5秒，发现这0.5秒内还收到了1000-1999，于是回复一个累积ACK，ACK的序号为2000。
注意：这里与GBN和SR不同，ACK2000表示字节2000以前的包都已经正确接收，下一个期望接收的包为2000字节开始的。

A接收到ACK2000该怎么处理呢？哦，它知道接收方是累积确认，也就知道虽然没有收到ACK1000，但是0-999和1000-1999都已经被正确接收了。

刚过不久，应用层又来新的数据了，这时A继续发送，假设发送了2000-2999，3000-3999这两个包，但是不幸的是，2000-2999丢失了，TCP只收到了3000-3999，这个时候B怎么办呢？
丢弃这个包，然后回复ACK2000，表示我想要的包是2000字节开始的？
由于TCP是累积ACK，回复ACK2000是没错的，但是如果把3000-3999丢弃了，岂不是浪费了自己接收窗口的缓存。

于是，TCP就把它缓存起来，回复一个ACK2000。当发送方接收到ACK2000，发现它已经接收过了一次。

那么TCP如何对待重复的ACK呢？两种做法：
（a）不管它
（b）立即重传
在最初的TCP标准中，采用方案a，等待超时。

假设采取方案a，等待一段时间后，就会发生超时。那么问题来了，给哪个包计时呢？还是给整个窗口计时呢？如果整个窗口计时，那么3000-3999也要重传一次，然而接收方已经缓存了这个数据，所以根本没必要。于是，TCP的做法是，给第一个未被确认的包计时，这里也就是2000-2999，当超时后，TCP的发送方只重传这一个包。当接收方收到了2000-2999后，由于缓存中有3000-3999，于是就回复一个ACK4000，表示字节4000以前的数据包都正确接收了。
以下是TCP发送方的伪代码（对于Duplicated ACK，采用方案a）

loop (forever){
	switch (event)
		event : data received from application above
			create TCP segment with sequence number NextSeqNum
			if(timer currently not running)
				start timer
			pass segment to IP
			NextSeqNum += length(data)
			break;
		event : timer timeout
			retransmit not-yet-acknowledged segment with samllest sequence number
			start timer
			break;
		event : ACK received, with ACK field value of y
			if(y > SendBase)
			{
				SendBase = y
				if(there are currently any not-yet-acknowledged segments)
					start timer
			}
			break;
}

现在我们来总结下TCP的工作机制

ACK --- 累积确认
超时重传 --- 给未被确认的发送时间最早的那个包计时

TCP看起来有点像GBN，回复最后一个按序接收到的包，但又与SR有点像，因为它会缓存无序的包，所以，它是一个混血儿。

TCP的一点修改（N-M模型）
在RFC2018中，提出了对TCP的一点修改，就是所谓的selective acknowledgement。就是说，接收方在收到无序数据包的时候，对这些数据包分别回复对应的ACK，当然，这种情况下TCP使用的就不是累积ACK了。惟一的一个缺点就是不能等待0.5秒发送累积ACK。