推断持久的域间拥塞

本文为SIGCOMM 2018会议论文。
笔者翻译和总结了该论文的主要部分。由于时间仓促，且笔者英文能力有限，错误之处在所难免；欢迎读者批评指正。
本文及翻译版本仅用于学习使用。如果有任何不当，请联系笔者删除。
如需转载，请联系笔者。

摘要

技术和政策社区对持续的域间拥塞的程度、范围和客户损害有着重要的兴趣。我们通过开发一种测量数千个域间链路上的拥塞而无需直接访问它们的系统和方法，从而为讨论域间拥塞提供经验基础。我们实现了一个基于时间序列延迟探测（Time Series Latency Probes, TSLP）技术的系统，该技术可以识别具有反复拥塞（暗示了链路配置不足）的证据的链路。我们在全球86个有利位置部署我们的系统，并显示我们的轻量级TSLP方法推断的拥塞与其他互连性能损害指标相关。我们使用我们的方法研究了2016年3月至2017年12月期间八家大型美国宽带接入提供商的域间链接，并使用两家提供商的真实流量统计数据验证了我们的推断。在我们收集测量的时间段内，我们没有发现接入ISP与直接连接的中转和内容提供商之间的域间链路上广泛流行的拥塞的证据，尽管一些此类链路表现出反复出现的拥塞模式。我们描述了限制、开放挑战以及大规模第三方使用此方法监控互联网互连生态系统的途径。

我们的兴趣在于由于安装容量与实际流量之间的长期不匹配导致的持续拥塞，特别是在网络之间的互连点处。 在这种情况下，拥塞表现为数据包传送延迟的增加，这是由于数据包在路由器缓存中的等待时间，并且可能丢弃数据包，这本身是一种损害，但也会导致发送者减慢其发送速率，并对用户体验质量（QoE）构成风险。 虽然多年来一直受到美国监管机构的关注[37]，但迄今为止还没有能够从边缘执行轻量级测量的任何方法或工具，从而检测到这种类型的拥塞。

时间序列延迟探测方法 图1概述了我们为操作TSLP方法并大规模执行它而构建的测量系统。 该系统利用一系列有利位置(Vantage Points, VP)来执行各种测量：TSLP(§3.1)和bdrmap(§3.2)测量(这两种测量形成该方法的核心)，以及三个独立的测量工作，以验证TSLP方法并提供关于拥塞的可测量影响的上下文：高频丢包测量(§3.3)，吞吐量测量(§3.4)和视频流性能测试(§3.5)。 后端系统负责维护最新的TSLP探测状态和管理时间序列数据(使用InfluxDB [2])。 我们已经建立了一个Grafana [1]前端，通过Web浏览器提供我们数据的交互式可视化。

图1：用于域间链路发现、主动测量和拥塞推断的系统。

时间序列延迟探测(TSLP)方法[48]建立在基本直觉的基础上：如果链路上的负载接近(或超过)链路容量，则数据包被缓存，导致通过该链路的测量延迟增加。 给定网络内部的有利位置(VP)，我们使用ICMP探测器来测量已识别的域间链路的两端的延迟(近端和远端，图2中的BR #A和BR #B)。

图2：时间序列延迟探测(TSLP)方法发送在边缘路由器#A和#B过期的TTL受限的数据包，从而测量链路延迟模式。

如果链路远端的延迟升高但近端的延迟不升高，那么延迟增加的可能原因是域间链路拥塞。 由于直接发送到路由器的数据包的处理方式与通过它们发送的数据包的处理方式不同(例如，在优化程度较低的代码路径中)，因此TSLP将ICMP探测包发送到目标链路后面的目的地，使用TTL使得数据包在近端接口和远端接口过期。对于每条测量的链路，TSLP使用所有三个目的地每隔五分钟探测链路的两个端点。为了最大限度地减少VP主机上的负载，每个VP将其整体探测TSLP速率限制为每秒100个数据包(pps)。

bdrmap: 识别探测链路 每个VP运行bdrmap [49]以推断主机网络和从VP可见的邻居网络之间的域间链路。bdrmap推断的域间链接表示主机网络的边界路由器和邻居网络的边界路由器之间的IP级链路。

丢包测量 与TSLP延迟测量一样，丢包测量模块向域间链路的近端和远端发送TTL受限的ICMP回声探测，设置为在目标接口到期。

吞吐量测量 我们使用网络诊断工具(NDT)来测量上传和下载到M-Lab NDT服务器的TCP吞吐量[3]。

YouTube流测量 我们使用YouTube-test工具[8]下载YouTube视频来衡量YouTube流媒体效果。

我们使用两种时间序列分析方法：level-shift(分析每周跨度的块中的时间序列以查找延迟升高的事件)和使用autocorrelation的第二种方法。

与丢包率的相关性 图3显示了2017年12月7日至9日期间Verizon与谷歌之间的链路的TSLP和丢失率测量结果。远端的延迟模式在每天的高峰时段都有所提升，而我们的autocorrelation方法在这段时间(黑色阴影)内将链路标记为拥塞。 图3的下图显示了在拥塞和不拥塞的时间间隔内的丢包率(以5分钟为间隔计算)。 我们观察到a)在拥塞时期，远端的丢包率高于非拥塞时期; b)在拥塞期间，远端的损失率高于近端的丢包率。

图3：2017年12月7日到9日，Verizon和Google之间的域间链路的TSLP延迟的时间序列(上图)和丢包百分比(下图)。推断的拥塞期间使用灰色阴影显式。

与YouTube性能的相关性 图4a显示了所选域间链路上测量的ON-period吞吐量的CDF。在拥塞期间，吞吐量中位数从12.4Mbps降至9.2Mbps，下降25.4％。启动延迟的CDF(图4b)显示，在拥塞时期，启动延迟的中位数降低了20.0％。

图4：拥塞和非拥塞期间YouTube流性能指标的CDFs。

图5显示除SamKnows VP 36外，在拥塞期间失败率通常较高。

图5：Ark (A)和SamKnows (S) VP的流失败率的中位数。

总之，我们发现TSLP推断的域间拥塞与较低的ON吞吐量，较高的启动延迟和较高的YouTube测试失败率相关，所有这些都可以验证我们的拥塞推断。

与NDT吞吐量的相关性 总而言之，在我们推断为拥塞的期间，NDT吞吐量的下降为我们的推断提供了额外的验证。 我们注意到一些与NDT和TSLP测量相关的附加说明。 首先，超出域间链路拥塞的因素可能会影响端到端吞吐量，例如家庭网络拥塞、服务器负载以及端到端路径上其他地方的拥塞[65]。 因此，我们不使用NDT吞吐量来推断域间链路拥塞。 第二个挑战是寻找正确的VP和NDT服务器集以测试拥塞链路。 尽管服务器footprint很大，但M-lab覆盖了美国大型接入ISP的一小部分域间链路[65]，并且频繁运行吞吐量测量会导致VP网络拥塞。

图6：TSLP延迟和NDP吞吐量的时间序列。