infocomm’18，香港科技大学
摘要
首先研究了不同类型的丢包对TCP性能的影响。结论为丢包大部分发生在短流的尾部或是流的突发时期。目前丢包恢复策略主要为等待超时重传，这对短流（要求低时延）的性能有很大的影响。本文提出了及时重传ACK（T-RACKs）的方案，在虚拟机层和主机网卡（服务器端）之间添加了中间层，运行T-RACKs算法，用来平衡数据中心中过长的RTO和数据包真实经历的较短的RTT。这种方法不用对TCP协议做任何修改，运行在发送端，容易部署。
简介
背景：分布式应用要求时延敏感的业务，业务完成时间由尾部流决定。较长的等待时间使得分布式应用性能相较于平均流完成时间下降了2到4个数量级。在私有的小数据中心中，CPU资源是影响业务性能的瓶颈，因此会采用流调度或任务管控分配的方式解决分布式应用的需求；在大型云数据中心中，所有资源都配置完善，但由于数据中心流量超出网络可承载量，这时网络性能-时延成为影响业务性能的瓶颈。
为解决这类问题，大公司例如微软、谷歌等采用专用架构的数据中心部署这些时延敏感的分布式应用。以多对一流量模式为主的数据中心虽然采取了各样的拥塞控制算法，但仍会引发等待时间的长尾分布行为。另外，虚拟化和频繁的上下文切换使得RTT的测量精度下降，从微秒级下降到毫秒级。
本文先探究了超时丢包的影响，然后从流粒度跟踪TCP流。根据收集的数据，从长短流的角度分析RTO（超时重传）和3-DUPACK（快重传）机制发生的频率。结果显示，RTO通常发生在流的尾部或是突发丢包，并且这种超时重传对长流影响很小，短流影响很大。本文提出了一种快速重传机制，主要思想为当发生丢包时，在RTO到期前触发快速重传机制。
主要贡献：（1）从TCP套接字层面研究了丢包现象，研究了各种重传机制（RTO，3-DUPACK）对TCP性能的影响。（2）提出了及时重传机制，不用修改用户主机内的TCP协议。（3）在仿真软件ns2和小型实验床上做了实验，与几种典型的重传机制做了性能对比，结果表明本方案使得短流的流完成时间下降了1个数量级。
问题和动机
RED（随机早期检测）的缺点：（1）在数据中心这样高带宽低缓存空间的环境下，控制排队时延的优势相对于总的FCT来说微不足道（2）丢包在TCP流中往往是发生拥塞的标志。
一些工作中将incast问题中FCT下降归结于超时重传机制的等待时间过长，因此提出的改进方案为减小minRTO值，使用微秒精度的计时器跟踪RTO。实验效果很好，很好的解决了incast问题。缺点有（1）需要修改TCP，在公有多租户数据中心环境中部署不合适。（2）不能找到一个完美的minRTO值适用所有场景。（数据中心内部通信，数据中心和互联网通信）
RFC提出了尾部丢失探针机制TLP。主要思想为设置了一个较短的PTO（与RTO作用类似）。在一个PTO内，发端没有收到ACK，则发端会发送TCP探针，探测网络状态。这种方案缺点为（1）需要改TCP协议（2）探测包也可能丢失（3）在incast场景下，探测包会加剧网络拥塞。
为了探究丢包对大象流和老鼠流的性能影响差异较大的原因，本文做了相关实验，搭建了套接字级的TCP流信息监测收集系统。使用自己搭建的流量发生器构造了web search流和data mining流。
具体实验内容为：（1）探究了使用RTO策略和FR策略（快重传）时的重传的数据包的大小（具体算法为最后一个重传包序号减去第一个重传包序号，再以拥塞窗口做归一化处理）（2）探究丢包的位置特征（记录重传的第一个包的序号，以拥塞窗口做归一化处理）。这两个实验得出结论，丢包的大小集中在30个拥塞窗口以内，但覆盖范围较广，不集中。丢包的位置集中为70以上，覆盖范围也较广，说明是尾部丢失概率较高。
由于FRR策略的拥塞窗口值较大，RTO策略的拥塞窗口值较小，为控制变量，探究了两种策略下，拥塞窗口大小与发生拥塞的概率之间的关系曲线，得出结论，在相同拥塞发生概率下，RTO所需的拥塞窗口比FRR小。实验中还探究了TLP策略，探究了使用TLP和不使用TLP情况下，两种业务模式的平均流完成时间，验证了TLP策略的低效（增加了FCT）。
接着从时延带宽积的角度分析了incast问题发生的原因，以及对短流的影响。因为短流几乎只持续几个RTT时间，发生丢包时，需要等待比RTT高2-4个数量级的时间才能重传，这大大增加了短流的FCT。
系统设计
系统设计的基础：TCP流的丢包是必然发生的，减小时延和抖动的关键不是避免丢包，而是发生丢包后如何避免较长的等待时间。
系统设计的目标：（1）提高时延敏感的短流的FCT（2）不会明显降低吞吐量敏感的长流的吞吐量（3）对所有已有的TCP协议和改进版本都兼容。也就是说本方案的修改是在虚拟机管理程序层，受DCN操作员控制，对TCP本身不做任何改动。（4）方案足够简洁，便于在真实的数据中心中部署。
设计思想：通过监测每条流的ACK数量，当推测出确认丢包时主动触发FRR机制，尽量在RTO到期前完成重传。这个方案是建立在大多数情况下（尤其对于短流），网络中没有足够的包去触发FRR机制，因为短流总共才持续几个RTT。所以本方案中提出“欺骗”ACK的概念，为每条流设置计时器，当超时但未收到ack时，就构造一个假的ACK触发FRR。关于计时器的设置在后续说明。
T-RACKs算法1
发送的包处理：（1）将包的四元组（sport，dport，sip，dip）做哈希，得到该流的标号（2）判断如果是syn包，或是该流静默时间过长进入不活跃阶段了，则将该流的信息重置，用发送包的信息更新该流的信息（3）判断如果是数据包，则记录包发送的最后序列号，更新流活跃时间
接收的包（ACK包）处理：（1）通过四元组哈希识别对应的流（2）若新ACK到达，则更新接收到的最后一个ACK序列号，更新时间，重置dupACK。若序号超出预设的值γ，则判定该流为大象流。此后将不对该流的包做处理。（3）若重复ACK到达，则更新DUPACK数量，丢掉重复ACK包。
算法2
计时器超时处理：每隔1ms运行一个超时处理函数。（1）取上一次发包时间和上一次收到ACK包时间的最大值为T，判断目前为止间隔时间是否大于β，若是，则组装一个ACK包发送到该主机的包接收处理程序。更新流的发送时间。（2）判断目前为止距离上次发送ACK包的时间间隔是否大于β，若是，则再次发送ACK。（3）判断目前为止距离上次收到ACK的时间间隔是否大于TCPminRTO，若是，则停止TRACK算法执行，使用RTO作为恢复机制。（4）判断目前为止距离上次发包时间是否大于1秒，若是，则判定该流处于静默状态，不做处理。
注：其中x（指数退避计数器）的作用不理解
当发生丢包，接收端收到足够的数据多的数据，足以触发DUPACK时，FRR机制平滑触发，此时不需要TRACKs算法的介入。只有当接收端收到的数据不足以发送足够多的DUPACK时，TRACKs才会介入，通过向发送端发送“欺骗”DUPACK，快速触发发送端的FRR机制，重传丢失的数据包，避免较长的RTO等待时间。
T-RACKs系统实现
（1）在hypervisor层实现，跟踪的流数和流状态也有限，记录的信息有四元组哈希值，每条流最后一个ACK序号，最后一个非DUPACK包的时间戳。
（2）在拦截ACK更新流状态信息时，会增加一些包处理的复杂度，但由于每个终端主机（即发送端）对ACK的操作不包含任何计算操作，因此不会对其增加负载压力和时延。而且该算法只记录老鼠流，因此总流数也不会很多，不会影响整体的TCP吞吐量。
（3）伪重传问题（即算法敏感度较高，没有发生丢包的情况下，就触发了FRR机制，使网络状态变得更差）。文章中分析这个问题与调整RTT大小所引起的问题类似，因此，在TRACKs的超时计时器β的设定上，采用公式（算法1中第5行），用于平衡快速触发FRR和伪重传引发拥塞之间的风险。
（4）超时重传β值设置：采用10倍的RTT值加上随机倍数的RTT值，作为超时重传β值。其中随机倍数选择使用指数退避算法
（5）重传同步问题：即不同主机上的不同VM同时发生丢包和重传，则又会引发类似incast拥塞现象。为避免此现象，在计算β值时，引入了随机时延。
（6）TCP头部操作：由于TCP不接受不连续时间戳的数据包，所以在发送假的ACK包时需要插入时间戳信息。不理解
（7）安全性问题：TCP协议中规定，当收到一个DUPACK，则拥塞窗口就增加一个MSS。这样容易引发伪ACK攻击。解决方案为当判定为DUPACK包时，更新相应流的状态信息，然后将该包丢弃。
（8）TCP语义：dupacks包应该代表丢失包之前的包已经到达，之后的包未到达。但网络中具有复制包的功能，因此用来触发FRR伪造的ACK包可能会被当做网络中复制的包处理，就不能达到触发FRR的功能。
仿真和实验床实验分析
仿真实验：在ns2实现，方案为DCTCP，DropTail（TCP-NewReno），RED（TCP-ECN）三种拥塞控制协议+TRACKs和不加TRACKs在两种流量模式下，平均流完成时间的差异。
实验床实验：测试了不同α值的影响
测试了在不含任何背景流量（即只有数据中心内部的流量）和包含背景流量情况下，一对多场景中Reno，Cubic，DCTCP三种TCP协议在添加TRACKs算法和不添加RACKs算法两种情况下的平均流完成时间，重传时间超过RTO（200ms）的概率。
不含背景流量：
包含背景流量：
多对多场景下短流的平均FCT：
