如何实现一个靠谱的协议

TCP协议为了保证顺序性,每个包都有一个ID。在建立连接的时候,会商定其实的ID是什么,然后按照哪个ID一个个发送。为了保证不丢包,对于发送的包都要应答,但是应答也不是一个一个来,而是会答应某个之前的ID,表示都收到了,这种模式称为 累计确认 或者 累计应答

为了记录所有发送的包和接收的包,TCP也需要发送端和接收端分别都有缓存来保存这些记录。发送端的缓存里是按照包的ID一个个排列的,根据处理的情况分成四个部分。

第一部分:发送了并且已经确认的。

第二部分:发送了并且尚未确认的。

第三部分:没有发送,但是已经等待发送的。

第四部分:没有发送,并且暂时还不会发送的。

在TCP里,接收端会给发送端报一个窗口的大小,叫Advertised window。这个窗口的大小应该等于上面的第二部分加上第三部分,就是已经交代了没做完的加上马上要交代的。超过这个窗口的,接收端做不过来,就不能发送了。

于是,发送端需要保持下面的数据结构。

  • LastByteAcked:第一部分和第二部分的分界线
  • LastByteSent:第二部分和第三部分分界线
  • LastByteAcked+AdvertisedWindow:第三部分和第四部分的分界线

对于接收端来讲,它的缓存里记录的内容要简单一些。

第一部分:接收并且确认过的。

第二部分:还没接收,但是马上就能接收的

第三部分:还没接收,也没法接收的

对应的数据结构就像这样。

  • MaxRcvBuffer:最大缓存的量;
  • LastByteRead:之后是已经接收了,但是还没被应用层读取的;
  • NextByteExpected :第一部分和第二部分的分界线;

第二部分的窗口有多大呢?

NextByteExpected 和 LastByteRead的差其实是还没被应用层读取的部分占用掉的MaxRcvBuffer的量,我们定义为A。

AdvertisedWindow 其实是MaxRcvBuffer 减去 A。

也就是:AdvertisedWindow = MaxRcvBuffer - ((NextByteExpected-1)- LastButeRead)。

那第二部分和第三部分的分界线在哪里呢?NextByteExpected 加 AdvertisedWindow 就是第二部分和第三部分的分界线,其实也就是 LastByteRead 加上 MaxRcvBuffer。

其中第二部分里面,由于受到的包可能不是顺序的,会出现空挡,只有和第一部分连续的,可以马上进行回复,中间空着的部分需要等待,哪怕后面的已经来了。

顺序问题与丢包问题

还是刚才的图,在发送端来看,1、2、3已经发送并确认;4、5、6、7、8、9都是发送了还没确认;10、11、12是还没发出的;13、14、15是接收方没有空间,不准备发的。

在接收端来看,1、2、3、4、5 是已经完成ACK,但是还没读取的;6、7是等待接收的;8、9是已经接收,但是没有ACK。

发送端和接收端当前状态如下:

  • 1、2、3没有问题,双方达成了一致。
  • 4、5接收方说ACK了,但是发送方还没收到,有可能丢了,有可能在路上。
  • 6、7、8、9肯定都发了,但是8、9已经到了,但是6、7没到,出现了乱序,缓存着但是没办法ACK。

根据这个例子,我们可以知道,顺序问题和丢包问题都有可能发生,所以我们先来看确认与重发机制

假设4的确认到了,不幸的是,5的ACK丢了,6、7的数据包丢了,这该怎么办呢?

一种方法就是超时重试,也即对每一个发送了,但是没有ACK的包,都有设一个定时器,超过一定时间。就重新尝试。但是这个超时的时间如何评估呢?这个时间不宜过短,时间必须大于往返时间RTT,否则会引起不必要的重传。也不宜过长,这样超时时间变长,访问就变慢了。

估计往返时间,需要TCP通过采样RTT的时间,然后进行加权平均,算出一个值,而且这个还是要不断变化的,因为网络状态不断地变化。除了采样RTT,还要采样RTT的波动范围,计算出一个估计的超时时间。由于重传时间是不断变化的,我们称为自适应重传算法

如果过一段时间,5、6、7都超时了,就会重新发送。接收方发现5原来接收过,于是丢弃5;6收到了,发送ACK,要求下一个是7,7不幸又丢了。当7再次超时的时候,有需要重传的时候,TCP的策略是超时间隔加倍。每当遇到一次超时重传的时候,都会将下一次超时时间间隔设为先前值的两倍。两次超时,就说明网络环境差,不宜频繁反复发送。

超时出发重传存在的问题是,超时周期可能相对较长。那是不是可以有更快的方式呢?

有一个可以快速重传的机制,当接收方收到一个序号大于下一个所期望的报文时,就检测到了数据六种的一个间隔,于是发送三个冗余的ACK,客户端收到后,就在定时器过期之前,重传丢失的报文。

例如,接收方发现6、8、9都已经接受了,就是7没来,那肯定是丢了,于是发送三个6的ACK,要求下一个是。客户端收到3个,就会发现7的确又丢了,不等超时,马上重发。

还有一种方式称为Selective Acknowledgment (SACK)。这种方式需要在TCP头里加上一个SACK的东西,可以将缓存的地图发送给发送方,例如可以发送ACK6,SACK8、SACK9,有了地图,发送方一下子就能看出来是7丢了。

流量控制问题

在对于包的确认中,同时会携带一个窗口的大小。

先假设窗口不变的情况,窗口始终为9。4的确认来的时候,会右移一个,这时候第13个包也可以发送了。

这个时候,假设发送端发送过猛,会将第三部分的10、11、12、13全部发送完毕,之后就停止发送了,未发送可发送部分为0。

当对于包5的确认到达的时候,在客户端相当于窗口在滑动了一格,这个时候,才可以有更多的包可以发送了,例如第14个包才可以发送。

如果发送给方是在处理的太慢,导致缓存中没有空间了,可以通过确认消息修改窗口的大小,甚至可以设置为0,则发送方将暂时停止发送。

我们假设一个极端情况,接收端的应用一直步读取缓存中的数据,当数据包6确认后,窗口大小就不能在是9了,就要缩小一个变为8。

这个新的窗口8通过6的确认消息达到发送时候,你会发现窗口没有平行右移,而是仅仅左面的边右移了,窗口的大小从9改成8。

如果接收端还是一直不处理数据,则随着确认的包越来越多,窗口越来越小,直到为0。

但这个窗口通过包14的确认到达发送端的时候,发送端的窗口也调整为0,停止发送。

如果这样的话,发送方肯定会定时发送窗口探测数据包,看是否有机会调整窗口大小。当接受方比较慢的时候,要防止低能窗口综合征,别空出一个字节来就赶快告诉发送方,然后马上又填满了,可以当窗口太小时候,不更新窗口,直到达到一定大小,或者缓冲区一半为空,才更新窗口。

这就是我们常说的流量控制

拥塞控制

拥塞控制的问题,也是通过窗口的大小来控制的,前面的滑动窗口rwnd是怕发送方把接收方缓存塞满,而拥塞控制窗口cwnd,是怕把网络塞满。

这里有一个公式LastByteSent - LastByteAcked <= min{cwnd,rwnd},是拥塞窗口和滑动窗口共同控制发送的速度。

那发送方怎么判断网络是不是满呢?着其实是个挺难的事情,因为对于TCP协议来讲,他压根不知道整个网络路径都会经历什么,对他来讲就是一个黑盒。TCP发送包常被比喻为往一个水管里面灌水,而TCP的拥塞控制就是再不堵塞,不丢包的情况下,尽量发挥宽带。

水管有粗细,网络有带宽,也即每秒钟能够发送多少数据;水管有长度,端到端有延时。在理想状态下,水管里面的水的量 = 水管的粗细 × 水管长度。对于到网络上,通道的容量= 带宽 × 往返延时。

如果我们设置发送窗口,使得发送但未确认的包为通道的容量,就能够盛满整个管道。

如图所示,假设往返时间为8s,去4s,回4s,每秒发送一个包,每个包1024byte。已经过去了8s,则8个包都发出去了,其中4个包已经到达接收端,但是ACK还没有返回,不能算发送成功。5-8后四个包还在路上,还没被接收,整个管道正好撑满,在发送端,已发送未确认的为8个包,正好等于带宽,也即每秒发送1个包,乘以来回时间8s。

如果我们在这个基础上再调大窗口,使得单位时间内更多的包可以发送,会出现什么现象呢?

我们来想,原来发送一个包,从一端到达另一端,假设一共经过四个设备,每个设备处理一个包时间耗费1s,所以到达另外一端需要耗费4s,如果发送的更加快速,则单位时间内,会有更多的包到达这写中间设备,这些设备还是只能每秒处理一个包的话,多出来的包就会被丢弃,这时我们不想看到的。

这个时候,我们可以想其他的办法,例如这个四个设备本来每秒处理一个包,但是我们在这些设备上加上缓存,处理不过来的在队列里面排着,这样包就不会丢失,但是缺点是会增加时延,这个缓存的包,4s肯定达到不了接收端,如果时延达到一定程度,就会超时重传,也是我们不想看到的。

于是TCP的拥塞控制主要来避免两种现象,包丢失超时重传。一旦出现了这些想象就说明,发送的速度太快了,要慢一点。但是一开始我怎么知道速度多块呢,我怎么知道应该把窗口调整到多大呢?

如果我们通过漏斗往瓶子里灌满水,我们就知道,不能一桶水一下子倒进去,肯定会溅出来,要一开始慢慢倒,然后发现总能够倒进去,就可以越倒越快。这就叫做慢启动。

一条TCP连接开始,cwnd设置为一个报文段,一次只能发送一个;当收到这一个确认的时候,cwnd加一,于是一次能够发送两个;当这两个的确认到来的时候,每个确认cwnd加一,两个确认cwnd加二,于是一次能够发送四个;当这四个确认到来的时候,每个确认cwnd加一,四个确认cwnd加四,于是一次能够发送八个。可以看出这时指数性的增长

涨到什么时候是个头呢?有个值为ssthresh为65535个字节,当超过这个值的时候,就要小心一点了,不能倒这么快了,可能快慢了,再慢下来。

每收到一个确认后,cwnd增加为1/cwnd,我们接着上面的过程来,一次发送八个,当八个确认到来的时候,每个确认增加1/8,八个确认一共cwnd增加1,于是一次能够发送九个,变成了线性增长。

但是线性增长还是增长,还是越来越多,知道有一天,水满则溢,出现了拥塞,这时候一般就会一下子降低倒水的速度,等待溢出的水慢慢渗下去。

拥塞的一种表现形式是丢包,需要超时重传,这个时候,将sshresh设置为cwnd/2,将cwnd设为1,重新开始慢启动。这真是一旦超时重传,马上回到解放前。但是这种方式太激进了,将一个高速的传输速度一下子停了下来,会造成网络卡顿。

前面说过快速重传算法。当接收端发现丢了一个中间包的时候,发送三次前一个包的ACK,于是发送端就会快速的重传,不必等待超时再重传。TCP认为这种情况不严重,因为大部分没丢,只丢了一小部分,cwnd减半为cwnd/2,然后将sshthresh=cwnd,当前三个包返回的时候,cwnd = sshthresh+3,也就是没有一夜回到解放前,而是还在比较高的值,成线性增长。

就像前面说的一样,正是这种知进退,使得时延很重要的情况下,反而降低了速度。但是如果你仔细想以下,TCP的拥塞控制主要来避免的两个想象都是有问题的。

第一个问题是丢包并不代表着通道满了,也可能是管本来就漏水。例如公网上的带宽不满也会丢包,这个时候就认为拥塞了,退缩了,其实是不对的。

第二个问题是TCP的拥塞控制要等到讲中间设备都填满了,才发送丢包,从而降低速度,这时候已经玩了。其实TCP只要填满管道就可以了,不应该接着填,知道连缓存也填满。

为了优化这两个问题,后来有了TTCP BBR算法。它企图找到一个平衡点,就是通过不断地加快发送速度,将管道填满,但是不要填满中间设备的缓存,因为这样时延会增加,在这个平衡点可以很好的达到高大宽和低延时的平衡。