[NSDI'23] Scalable Tail Latency Estimation for Data Center Networks (Parsimon)

Paper: https://www.usenix.org/system/files/nsdi23-zhao-kevin.pdf

Codebase: https://github.com/netiken/parsimon

Presentation Video: https://www.youtube.com/watch?v=lqjbqH7tu5g

Homepage of Author: https://homes.cs.washington.edu/~kwzhao/

背景与问题

• 主题：大规模数据中心网络中尾时延的快速估计，通过反事实模拟（Counterfactual Simulation）。

• 网络尾延迟如何响应工作负载、拓扑或其他配置的变化？

• 如果网络架构演进了如何变化？

• 如果链路抖动 / 故障了如何变化？

• 现有方案：通过网络模拟器（Network Simulator），最知名的例如 ns-3。ns-3 可以回答许多问题，对各个性能指标的模拟都很精细，但是非常耗时。

• 问题：随着生产数据中心网络带宽的扩大和规模的扩大，网络仿真未能跟上步伐。

• 目标：快速、精准地估计流完成时间（FCT）的尾时延

• 相关工作

• MimicNet 需要对新的工作负载和网络配置进行长达数小时的 retraining，并且它只会加速在同等大小的机器集群中具有统一流量的统一 fat trees 模拟。

• DeepQueueNet 放宽了 MimicNet 的一些限制，但没有对拥塞控制进行建模，这可能是性能的 first-order 决定因素。

Parsimon

理论基础

作者的假设是：我们可以通过对沿各个路径的每个链接处的局部拥塞事件的频率和大小进行建模，来近似计算在大型网络上运行的特定工作负载的端到端流量性能分布。长流在其生命周期中当然会经历多次拥塞事件，但其中大部分会在不同时间沿路径的不同点发生。该假设与排队论（Queueing Theory）相关。

作者认为，单个队列的状态仅取决于它接收的流量而不是网络其余部分的状态。我们可以单独分析各个队列，并将结果组合起来以近似端到端网络行为。

Overview

本文介绍了一组快速、可扩展地估计数据中心网络中流量性能分布的方法。 这些技术在名为 Parsimon 的 prototype 中实现：

WorkFlow

输入：拓扑描述、工作负载

处理步骤：Decomposition → Clustering → Simulation → Aggregation

输出：流完成时间分布（FCT Distribution）

为了加速 FCT 估计，独立且并行地估计每个链路的效果。 然后整合结果，对整个网络进行预测。

具体设计

生成链路级工作负载｜Generating Link-Level Workloads

首先，Parsimon 将每个链路与通过它的流相关联。 由于链接是双向的，因此每个链接有两组流，因此有两个链接级模拟。Parsimon 通过流的路由用流来填充链路。对于每个链路和每个方向，关联的流构成链路级模拟的输入工作负载。 流的大小和到达时间未经修改地通过。

生成链路级拓扑｜Generating Link-Level Topologies

接下来我们生成链路级拓扑。我们认为每条链路都会对端到端 FCT 产生一定程度的延迟。对于每个链路和每个方向，我们生成一个拓扑并仅使用穿过该链路的流来执行模拟。 模拟完成后，通过获取观察到的 FCT 并移除该流量大小的理想 FCT 来计算由给定流量的链路引起的延迟。例如对于大小为 𝑠 的流穿过速度为 𝐶 和传播延迟为 𝑙 的链路，理想的 FCT 为 𝑠 / 𝐶 + 𝑙，这直观地捕获了由于排队、拥塞控制、带宽共享等在目标链路引起的所有延迟。

在生成每链路拓扑时，我们的目标是隔离和测量目标链路的预期延迟贡献。

为每个链路级模拟构建了一个拓扑结构，以反映性能和准确性之间的权衡，试图捕获最重要的影响以计算目标链路造成的延迟。以这种方式重写拓扑可确保数据包最多可以遍历三跳，而不管原始拓扑的大小如何。

• 建模往返时延｜Modeling round-trip delay

接下来，我们在每个构造的拓扑中设置链路延迟以匹配原始网络中的往返延迟。拥塞控制的角度，正确建模 RTT 对于正确建模队列动态也至关重要。

• 选择链路带宽｜Selecting link bandwidths

在某些情况下，人为地增加下行链路的带宽以确保它们不会人为地增加拥塞（图 A、B 中粗线条）。这是一种简化方法，可以减小存储和转发延迟以及核心链路对拥塞分析的影响。

• 纠正 ACK 流量｜Correcting for ACK traffic

调整每个模拟链路上的前向带宽。方法的关键思想是将链路上的前向带宽减少一个与链路上传输的 ACK 平均流量成正比的量，使得模拟结果更贴近实际网络环境中 ACK 的带宽消耗情况。

后处理链路级结果｜Post-Processing Link-Level Results

每个链路级仿真为链路级工作负载中的每个流生成一个 FCT，这些 FCT 用于计算延迟。 在对链路级结果进行后处理和构建这些分布时，我们的主要目标是支持对所有流量大小的准确估计。

• 分组归一化延迟｜Packet-normalized delay

问题：在处理 FCT 延迟时，如何通过对延迟进行归一化来解决不同流大小。

归一化方案：计算特定流的延迟后，我们可以将延迟除以流的数据包数量。将生成的度量称为数据包归一化延迟，它具有总结每个数据包流的平均延迟的直观解释。归一化实际上是根据流的数据包数量进行的。

• 桶分布处理｜Bucketing distributions

桶分布用于将不同大小的流分成不同的“桶”，以便更准确地为不同的流大小从合适的分布中选择样本。

Parsimon 使用了一种简单的分桶算法：

聚合链路级估计｜Aggregating Link-Level Estimates

在 Parsimon 中，为了估计端到端的延迟，需要对路径中每个链路的延迟分布进行聚合。

这里用的链路级模拟后端采用了一个自定义的最小模拟器，仅对工作负载、拓扑、队列和拥塞控制进行建模。

加速的主要来源｜Primary Source of Speedup

• 强扩展能力｜Strong Scalability

Parsimon 通过单独考虑每个链接的影响来加速大型网络模拟，允许它扩展模拟网络的大小和处理核心的数量。

• 聚类和修剪模拟｜Clustering and Pruning Simulations

贪婪的链路聚类方法将网络中的链路分组，从而在大规模数据中心网络分析中降低计算复杂度，与上述的桶分布有类似的效果，通过聚类来集合相同特征的链路，然后选择一个 representative 来代表这个 cluster。

错误的主要来源｜Primary Sources of Error

• 瓶颈扇入｜Bottleneck Fan-in

Parsimon 在模拟目标链路时，并没有模拟上游链路的实际情况。在实际数据中心网络中，这些拥塞和排队情况可能相对更轻。

• 缺乏流量平滑｜Lack of Traffic Smoothing

流量平滑是指在网络中，由于诸如链路传输速率、缓冲器限制、路由限制等因素，流量在从发射源到接收目标的传输过程中自然地被混合和分散，从而导致到达目标链路时不会同时产生巨大的突发流量。

包括 TCP 拥塞控制和其他流控制协议在内的很多网络协议能够提供各种程度的流量平滑。

• 链路级独立性｜Link-level Independence

一个更基本的近似是链路级模拟是独立处理的。这种技术可以实现大规模并行化，但其准确性取决于路径上各个跃点上的流量强度之间的相关性。 流量越相关，Parsimon 的方法产生的错误就越多。

• 同时间单瓶颈｜One Bottleneck at A Time

当拥塞是偶发的和临时的，在不同的时间出现在不同的链路上时，Parsimon 更准确，而当拥塞在给定路径的多个边缘和核心链路上持续存在时，Parsimon 的准确性较低。

实验及结果

Parsimon 的目标是快速估计各种大型数据中心网络和工作负载的尾部延迟。在评估 Parsimon 时，我们想评估：

1. Parsimon 在数千台主机规模上的准确性和性能。

2. 准确性如何受到工作负载和拓扑上的各种变量的影响。

实验设置

拓扑规模 & 超额订阅因子

仿照 Meta 的数据中心结构。

流量矩阵

流量大小分布 & 突发级别

最大负载级别

Parsimon 变体 & baseline

实验一：大规模网络分析

• 评估速度和准确性

• 384-rack，6144-host，超额订阅 2:1，矩阵 B，高突发性（𝜎 = 2），最大链路负载 50%

• 运行五秒的模拟时间

实验二：小规模敏感性分析

• 评估近 200 个拓扑和工作负载场景

• 256-host

不同最大负载下：

• 在所有场景下，85% 的时间中 Parsimon 的 p99 估计值在 ns-3 的估计值的 10% 以内，最差情况下高估了 52%。

• 在负载最高的一组场景中（最大链路负载在 56% 到 83% 之间）62% 的时间中 Parsimon 在 ns-3 的 10% 以内，平均误差约为 11%。

• 在最大链路负载介于 26% 和 41% 之间的场景中，Parsimon 在 100% 的时间内处于 ns-3 的 10% 以内。

• 在 3% 的场景中，Parsimon 低估了 p99 达 2%。

其他参数：

按流量矩阵、流大小分布、超额订阅和突发性分组的低负载场景的中值误差和误差分布作为 小提琴图｜Violin Plot。

• Max load ≤ 50%：这些参数的变化只产生了适度的影响

• Max load > 50%：矩阵 A 的错误分布、WebServer 流量大小分布和 4 比 1 超额订阅的尾部更长

实验三：一种配置分析

矩阵 A，Hadoop 流大小分布、低突发性、2:1 超额订阅和 68% 的最大负载（前 10% 的平均负载为 56%）的场景。

对于这种配置，Parsimon 对于小流量和低到中等最大链路利用率最为准确，这对于所有三种拥塞控制协议都是如此。 对于中低利用率的中小型流，DCTCP 的错误率略低。 对于较大的传输和较高的最大链路利用率，相对误差较高，不同协议的误差没有明确的模式。

总结

在这篇论文中，作者讨论了如何为大规模数据中心网络提供快速的流级尾部延迟估计。提出并评估了一种新方法 Parsimon。作者通过 Decomposition → Clustering → Simulation → Aggregation 四个步骤快速产生尾时延流级估计。单个多核服务器上的性能比 ns-3 高出 492 倍，延迟分布尾部的精度损失小于 9%。

• 优势：问题拆解、分析详细、优化手段多、实验完善

• 劣势：只可用于尾时延估计、是否能运用于工业界使用有待观察

相关知识补充

反事实模拟｜Counterfactual Simulation

反事实模拟（Counterfactual Simulation）是一种模拟分析方法，主要目的是在不改变实际环境的情况下，评估可能的事实或事件对实际结果的影响。这种方法通常应用于评估策略、决策或系统性能，并通过假设环境变量的改变来预测不同场景下可能出现的结果。

此类模拟可以帮助研究人员或决策者通过预测和评估潜在情景来优化现有系统及其部署。反事实模拟有助于发现已有策略或决策可能存在的问题，并预防现实环境中的风险。这可以用于各种场景，如经济政策研究、数据中心网络优化、供应链模型优化和市场策略评估等。

这是作者在文章开头提到的一个概念，其实就可以理解为网络模拟。

网络模拟器｜Network Simulator

一个网络模拟器，例如 NS-3，在工作时需要以下类型的输入：

1. 拓扑描述：定义网络的结构，包括节点（如路由器和主机）以及它们之间的连接（如链路和交换机）。拓扑描述还可能包括线路速度、传播延迟、丢包率等链路属性。

2. 协议栈配置：选择和配置各个节点上的网络协议栈，例如 IP、TCP、UDP、MAC 层协议等。这通常包括为协议分配参数，如窗口大小、超时值和最大传输次数等。

3. 流量模型：定义网络中的流量模式，如数据的发送者和接收者、数据传输速率、数据包大小、流的开始和结束时间等。流量模型可以是确定的，也可以是基于统计模型的随机流量生成。

4. 调度策略：如果涉及到资源分配或者流量调度，可以配置调度策略，例如流量控制算法、拥塞控制算法或负载平衡策略等。

5. 仿真配置：设置仿真所需的全局参数，如仿真持续时间、随机数种子、仿真分辨率等。此外，可以指定输出数据的格式和文件名，用于存储仿真结果。

6. 可选扩展模块：对于一些特定的网络场景，可能需要加载额外的模块或插件。例如，在无线网络模拟中，可能需要一个无线信道模型来考虑信号传播特性、干扰和衰落等因素。

这些输入参数将用于配置网络模拟，在整个模拟过程中控制和记录网络行为。根据输入参数的不同，网络模拟器可以表示各种网络环境和使用场景。

排队论｜Queueing Theory

排队论（Queueing Theory）是研究排队现象的数学理论，主要关注等待时间、排队长度、服务设施能力和阻塞等现象。在计算机网络领域，排队论被广泛应用于性能建模和分析。网络中的链路、路由器、交换机等可以被视为排队系统的组成部分，每个链路都有其输入队列和输出队列。数据包在链路之间传输时，需要根据网络设备的等待时间、处理时间和传输时间来调度。这些时间变量导致了流量拥塞。

在论文中，作者基于排队论提出了这个假设。通过研究每个链路的局部拥塞事件，可以找出潜在的网络瓶颈。为了估计端到端数据流性能，作者将问题分解为大量独立的单链路模拟。每个链路模型基于排队论来量化拥塞事件的频率和幅度，进而建立性能模型。然后，将这些带有局部拥塞信息的链路模型组合起来，以估算整个网络的端到端数据流性能分布。因此，排队论在这个假设中起到了关键作用，为研究网络拥塞现象以及预测端到端性能提供了理论基础。论文中的方法将排队论应用于实际场景，以解决计算速度慢的问题，并取得了一定程度的准确性。

蒙特卡洛采样｜Monte Carlo Sampling

蒙特卡洛采样（Monte Carlo Sampling）是一种随机抽样方法，用于估算复杂系统的性质。其基本思路是利用随机过程进行数值模拟，并通过大量实验或抽样次数，近似计算某个复杂问题的结果。蒙特卡洛采样广泛应用于多种领域，如物理学、工程学、金融学和计算机科学等。

蒙特卡洛采样的主要用途如下：

1. 数值积分和求解高维复杂问题：在某些情况下，传统的数值积分方法面临较高的计算成本或难以实现。而蒙特卡洛采样可以通过随机抽样，近似计算复杂高维积分。

2. 概率分布的分析：对于复杂概率分布或不易处理的联合概率分布，蒙特卡洛采样可以辅助分析这些分布的性质，例如通过生成随机样本来近似复杂分布的期望值、方差等统计量。

3. 运筹学和决策分析：蒙特卡洛采样可以在模拟和优化决策过程中发挥作用。它可以用于确定最佳策略、分析风险、估算不确定性和评估各种决策方案的概率。

4. 机器学习与模型优化：在机器学习领域，蒙特卡洛采样为优化算法提供了更多随机性。在蒙特卡洛树搜索（MCTS）中，它用于寻找决策空间的有希望区域。在马尔可夫链蒙特卡洛（MCMC）方法中，其构建随机马尔可夫链来近似概率分布。

通过蒙特卡洛采样，可以为复杂问题提供数值解和近似解。尽管在某些情况下精度可能不如解析解，但其优势在于对复杂问题和高维空间的适应性以及针对具有非常复杂结构的问题实现相对较快的近似求解。

桶分布｜Bucketing distributions

桶分布（Bucketing distributions）是一种数据分析方法，它将一组连续数据划分为几个范围或“桶”，以便更有效地分析数据的分布特征。数据分桶有助于更好地理解数据的概况和特征，而不需要关注每个数据点的细节。在计算机网络和流量管理中，桶分布通常用于分析不同流大小下的性能度量，如延迟和吞吐量等。

超额预订因子｜Oversubscription Factor

超额预订因子（又称超额订阅比率，Oversubscription Factor）是一种用于描述网络中不同层次之间带宽需求比例的度量。它常常用于数据中心网络和企业局域网等具有多层次网络拓扑结构的环境中。超额预订因子表示上层网络资源（如交换机、路由器等）的带宽与下层网络资源的带宽之间的比值。更具体地说，这个因子描述了如何在网络拓扑的不同层次之间共享和管理有限的网络带宽。

举个例子，假设数据中心中存在一组服务器，它们连接到一个二层交换机。与此同时，这个二层交换机又连接到一个上层的聚合交换机，形成多层次的拓扑。如果二层交换机到聚合交换机的链路总带宽是连接到所有服务器的链路总带宽的一半，那么超额预订因子就是 2:1。这意味着在给定时刻，该数据中心内部的服务器对上层网络资源的需求可能超过了实际可用的带宽。因此，在面临高速网络流量时，这种情况可能会导致链路拥塞和性能下降。

在网络设计和管理中，适当设置超额预订因子是很重要的，以确保不同层次之间带宽的合理分配和有效使用。研究人员和工程师需要权衡系统的成本、可扩展性以及不同业务和工作负载的需求，以便选择最佳的超额预订因子。

小提琴图｜Violin Plot

小提琴图是一种用于可视化数据分布的图表，它可以帮助我们快速了解数据的分布情况和趋势，同时也可以用于比较不同组数据的差异。

下面是小提琴图的一些基本元素，以及如何解读这些元素：

1. 对称的小提琴形状：小提琴图由多个对称的、有着不同宽度的小提琴形状组成，每个小提琴代表了数据的一个分布情况。小提琴的宽度表示数据出现的频率，越宽表示数据出现的频率越高。

2. 中间线：小提琴中间的粗线表示中位数，如果中位数的粗线偏离数轴中心线有明显偏移，则意味着数据分布的倾斜性。

3. 箱线图：小提琴图中的箱线图通常会绘制在小提琴中间，箱线图可以显示出数据的四分位数和异常值（指数据中相距正负一个标准差以外的离群点），箱子的上下边缘代表75%和25%的分位数，箱子中间的线是中位数，上下延伸的线是上下边界范围内未被视为离群值的观测值的最大值和最小值。

4. 多个小提琴组成的图形：小提琴图可以堆叠起来进行比较，一般用于不同样本或不同时间区间的比较。

总之，小提琴图除了显示数据的“中心位置”和分布情况，还能够很好地展示不同数据的离散程度和偏态等特征，这让它成为了一种重要可视化工具，帮助我们更好的理解数据。