课程报告：重新思考BBR拥塞控制算法的速率估计

苏波:BBR拥塞控制算法的速率估计5重新思考BBR拥塞控制算法的速率估计苏波摘 要:压缩的ACK使BBR的带宽估计不够准确，这导致了在低丢包率环境下的高排队时延。额外的排队时延会影响一些交互式应用的体验，例如Skype。为了解决上述问题，本文提出了一个新颖的方法，即CBE，通过它去修正带宽的估计值。CBE可以精确地检测到不真实反映带宽大小的ACK速率，并且广泛的仿真实验证明了CBE的有效性。关键词:带宽估计; BBR; 排队时延Rethinking the Rate Estimation of BBR Congestion Control Su BoAbstract: The ACK compression makes the available bandwidth estimation in BBR inaccurate which result in the high queuing delay under low packet loss rate environments. The additional queuing delay affects the user experience of interactive applications like Skype. To solve the above-mentioned issue, this letter presents a novel method, named CBE, to calibrate the bandwidth estimation. The CBE can detect the implausible ACK rates accurately and the extensive simulation prove the effectiveness of CBE.Key words: bandwidth estimation; BBR; queuing delay1 引言在现今网络结构的多样化快速发展和不断增长的应用需求下，TCP的拥塞控制算法仍然是当今的研究热点12。由于只在拥塞时才降低拥塞窗口，传统的以拥塞窗口为基础的TCP在大缓存下会遭受bufferblot的问题3，并且在高丢包率环境下，其带宽利用率低下4。不同于传统的以时延为基础和以丢包为基础的拥塞控制算法，BBR5是一个以速率为基础的算法，它的拥塞窗口只作为已发出数据包的上限。不再采用丢包作为拥塞控制信号，不再使用ACK时钟去控制数据包的发送，BBR通过计算反映可用带宽大小的ACK速率和探测最小来回时延(RTT)解决了上述问题。在蜂窝、Wi-Fi和有线带宽网络下，为了避免延迟和聚集的ACK6使带宽探测引擎失速，BBR通过将拥塞窗口设置为2倍的带宽时延积（BDP）来持续地以估计的带宽大小发送数据包。有时候压缩的ACK会导致过大的ACK速率，BBR通过简单地比较数据包发送速率和ACK的接受速率并取其小的方法过滤掉不真实反映带宽大小的ACK速率。然而，这个简单的方法不能完全过滤掉不真实的ACK速率7。因此，BBR会因为2倍BDP设置的拥塞窗口而造成额外的排队时延。BBR会持续占据1个BDP大小的中间链路缓存。直到探索最小RTT的阶段，BBR才会排空缓存队列中的数据包，如此循环。通过分析BBR的ACK速率测量机制和服务器端发送ACK的行为，我们在本文中提出一个更为精确的可用带宽测量方法CBE。我们的主要贡献在于展现了整体上发现不真实反应实际带宽的ACK速率的可能性。与原来的BBR相比较，这个修正带宽估计算法CBE在0%-5%的低丢包环境下可以实现更低的队列时延，并且保持高带宽利用率，与BBR相比只有略微的下降。2 相关工作在BBR之前，TCP WestWood8算法就采用了类似的带宽估计算法。WestWood算法控制的是在快速恢复阶段退出时的拥塞窗口值，这是一个不包括队列缓存在内的带宽时延积，即一个大小BDP。标准的WestWood算法在估计带宽时十分粗糙，它将一个TCP连接的生命周期分解为一段一段的采样周期，通过每个采样周期内采集的ACK字节数，除以采样周期的间隔，最后将得到的结果做指数移动平均。在WestWood阶段，TCP的拥塞控制框架限制了带宽估计的精准性，在BBR出现后，google团队修改了Linux内核的拥塞控制框架，引入了struct rate_sample参数，以实现更为精确的带宽估计。在新的TCP控制框架中，对于每个ACK，提供估计的带宽大小和是应用层限制了发送速率的指示，其中具体的带宽估计机制由下文给出。3 研究动机BBR将被接收端计算的ACK速率作为估算可用带宽的指示器。正如图1所示，蓝线的斜率代表了ACK速率（Arate），他被计算为，,其中，Dacked代表在测量期间内被确认数据包的数量，,其中Dd和Pd分别表示在数据包D和P被确认时所有已经被确认的数据包数量。Aelapsed表示测量间隔：,其中Dat是数据包D的确认时间，此时数据包P正在发送，Pat则代表了数据包P的确认时间。图1：BRR的带宽测量算法然而，上述方法在ACK大量消失、聚集、压缩的路径下面临挑战6。在这种情况下，ACK可以短期内以超过瓶颈带宽的速率快速到达。为了过滤掉上述不真实的ACK速率，BBR考虑数据包发送速率Srate9，,其中Pst是数据包P发出的时间，Dst是数据包D的发出时间，BBR选择估计瓶颈带宽速率Erate，。然而上述方法也不能完全过滤掉不真实的ACK速率。当BBR在探索带宽阶段时，BBR的发送速率可以达到瓶颈带宽速率的1.25倍。因此，即使ACK速率没有超过数据包的发送速率，BBR仍然会采用过估计的速率并且保持10个RTT的时间，导致额外的队列时延。正如图2所示，在低丢包率环境下，随着RTT的不断增加，BBR会产生更多的额外队列时延。随着丢包率的增加，带宽的过估计问题会被缓解。图2：不同丢包率和RTT下，BBR的平均队列时延4 具体方案算法 1 CBE 根据图1所示的BBR速率估计算法，只有在数据包D的ACK被延迟发送并且之后的数据包ACK被聚集或者消灭的情况下，数据包才会在短时间内显示出比瓶颈链路带宽更高的传输速率。如果聚集的ACK出现在测量间隔的中间或者后面，这对瓶颈链路带宽的估计没有影响。我们抓住下述特征：只有聚集ACK出现在测量间隔开头才会导致不真实ACK速率；一小段时间后，聚集的ACK从测量间隔中向后移动，这会导致带宽估计速率的剧烈下降。正如算法1所示的伪代码那样，我们在每个ACK到来时，计算比较当前的ACK速率Erate与上一次计算的ACK速率Erate（bwlast）。如果当前的ACK速率Erate降低超过阈值T1，那么我们立刻更新这个Erate到BBR的带宽估计中。否则，我们延迟更新这个Erate，并且假定它是假的带宽估计值，在每个ACK使cntspurious值加1。如果在每次比较中Erate值的下降程度都没有超过T1，并且cntspurious的值超过T2，我们就将Erate的值更新到BBR。5 实验与分析我们使用仿真工具mahimahi10，它可以模拟传播时延，丢包率和瓶颈链路带宽。正如图3所示，我们创建了一个简单的拓扑，发送端通过mahimahi与接收端相连。所有实验我们只设置了一条BBR流。图3：一个客户端通过mahimahi连接服务器端的简单拓扑在第一个场景中，我们设置了50Mbps的瓶颈链路带宽、300ms双向传播时延和0.1%的丢包率。图4表明，通过合理的检测阈值，CBE相较于BBR可以更好地过滤掉不真实的ACK速率并且在大多数时间保持低队列时延。由于BBR在探索带宽阶段会以125%的带宽估计速率发包，因此产生了图4中的曲线尖峰。图4：BBR和CBE随着时间变化的队列时延在第二个场景中，为了比较CBE和BBR在不同RTT下的的性能表现，我们设置了50Mbps的瓶颈链路带宽和0.001%的丢包率，并且让RTT从10ms变化到310ms。从图5可以看出，CBE可以实现低队列延迟并且它合理的延迟更新阈值使它保持高带宽利用率。随着RTT的增加，对比BBR不断上升的平均队列延迟，CBE可以仍然保持住低排队时延。图5：不同RTT下CBE与BBR的带宽利用率（BUR）和平均队列时延（AQD）第三个场景中，我们在0.001%-10%丢包率场景下评估CBE的性能。我们同样设置瓶颈链路带宽为50Mbps，设置双向传播时延为300ms。正如图6所示，BBR带宽过估计的问题随着丢包率的增加而被缓解。当丢包率到达0.1%，BBR只有40ms的平均队列时延。然而，CBE不论丢包率怎样，总能保持低的队列时延和高的带宽利用率。图6：不同丢包率下CBE与BBR的带宽利用率（BUR）和平均队列时延（AQD）6 结论展望本文提出了一个更为精确的带宽速率估计算法，叫做CBE，它基于延迟更新和不真实ACK速率检测机制。CBE可以实现低队列延迟并且保持高带宽利用率。此外，该算法很容易部署在当前的BBR当中。在以后的研究中，我们将把文中固定的阈值通过动态调整的方式进行更新，使该算法能有更广的适用范围和更精确的带宽估计。References:1 G. Fairhurst, B. Trammell, and M. Kuehlewind, Services Provided by IETF Transport Protocols and Congestion Control Mechanisms, RFC 8095, IETF, Mar. 2017.2 D. Papadimitriou, M. Welzl, M. Scharf, and B. Briscoe, Open Research Issues in Internet Congestion Control, RFC 6077, IETF, Feb. 2011.3 J. Gettys and K. Nichols, Bufferbloat: Dark Buffers in the Internet, ACM Queue, vol. 9, no. 11, pp. 40-54, Nov. 2011.4 A. Ghaffari, Congestion control mechanisms in wireless sensor networks, Academic Press Ltd. textbf52, pp. 101-115, Appl. 2015.5 N. Cardwell, Y. Cheng, C. S. Gunn, S. H. Yeganeh, and V. Jacobson, BBR: Congestion-Based Congestion Control, ACM Queue, vol. 14, no. 5, pp. 50:20-50:53, Oct. 2016.6 Abrahamsson, M. 2015. TCP ACK suppression. IETF AQM mailing list; /mail-archive/web/aqm/ current/msg01480.html.7 -, BBR Congestion Control, Presentation in ICCRG at IETF 99th meeting, July. 2017. Online. Available: /proceedings/99/slides/slides-99-iccrg-iccrg-presentation-2-00.pdf8 S. Mascolo, C. Casetti, M. Gerla, et al. TCP westwood:Bandwidth estimation for enhanced transport over wireless linksC/ International Conference on Mobile