基于eBPF和可编程交换机采集in-host和in-network的per-packet时间戳。在此基础上进行了一些针对burst的分析工作。

研究表明，traffic is bursty across a wide range of timescales in diverse contexts。然而，host networking对traffic burstiness的调节作用却很少被研究。本文希望能够填补这一空白。

我们要问的是，是什么原因导致what causes the traffic to emerge from hosts in bursts？ burstiness是否是流量的一个尺度不变的属性，也就是说，流量是否在广泛的时间尺度上保持其burstiness，或者microbursts在粗略的时间尺度上会变得平稳？传统的突发应对措施，如TCP pacing和数据包调度，是否能有效遏制bursts？当然，host network非常复杂，这让研究impact of host networking变得非常复杂。

Valinor由两个主要部分组成：

基于eBPF的in-host时间戳框架（Valinor-H），基本在软件栈处理的最后阶段收集出口数据包元数据
in-network数据包时间戳框架（Valinor-N），该框架在网卡之后立即在可编程交换机数据平面上捕捉数据包到达的时间戳，并将时间戳数据发送到离线服务器进行收集、存储和突发度分析

Background

self-similarity：自相似性
Hurst exponent
- 0.5 < H < 1：self-similar timeseries with long-term positive autocorrelations
- H = 0.5：completely uncorrelated series
- 0 < H < 0.5：mean-reverting timeseries，high value和low value交替

self-similarity的一些practical implications

排队性能和缓冲区的大小。自相似性对排队性能有很大影响。从排队论的角度来看，自相似性的决定性特征是，队列长度分布的衰减比短距离依赖性流量的衰减要慢得多（在短距离依赖性流量下，例如泊松过程，是多项式的，而不是指数式的）[66]。对于强自相似的流量，平均队列长度随着缓冲区大小而增加[54]。这意味着具有强自相似性流量的网络应该部署小的缓冲区来控制排队延迟。
吞吐量和延时的权衡。先前的工作表明，联合提供低延迟和高吞吐量会受到自相似性的不利影响。
流量预测和burst应对措施。自相似性流量中存在的相关结构可以被检测和利用，以预测大于RTT的时间尺度的未来流量。例如，具有大于RTT的控制循环的resource provisioning技术（如多尺度拥堵控制、重新路由和拓扑重布线）增强了自相似流量的性能。

Approaches to measuring traffic bursts

主要是讲采集per packet时间戳的design space。

Valinor measurement framework

设计目标

提供对主机网络流量的可见性，以及shape of the traffic on the wire
提供数据包到达的高分辨率时间戳，与不断增加的链路带宽和更快的数据包处理管道保持一致
提供对不同规模和时间范围内的流量形状和burst的洞察力

我们设计并实现了Valinor，这是一个测量框架，包括两个主要的时间戳，从主机和网络的角度研究数据包的到达。首先，我们设计了Valinor-H，通过选择tc eBPF钩来研究主机对其出口流量的看法。为了捕捉流量突发的外部情况，我们设计了Valinor-N，一个可编程结构的时间戳模块。

Valinor-H: burst measurement in hosts

Valinor-H提供了visibilty into the impact of the software stack on traffic, immediately before the traffic is passed to the NIC。框架包括两个部分

data plane：遵循一套严格的类似C语言的指令，每次sk_buff到达时，都会在tc qdisc执行
write handler：确定添加新的时间戳条目的正确位置并更新数据结构

通过主机内测量框架，网络操作人员可以验证发送方主机传输路径上的高层网络处理层的操作。在这个阶段，Valinor-H可以捕获进入网卡的流量，其中包括从qdiscos、跨端口层和应用程序输出的流量。为了捕捉网络核心中的流量行为，并以每包为单位，我们在下一节介绍Valinor-N。

Valinor-N: in-network burst measurement

主机中基于软件的测量与粗粒度的sk_buff到达量有关，并在NIC功能（即环形调度器和分段卸载）之前实现。因此，捕获的流量行为可能与on the wire的行为不一致。为了填补这一空白，引入了基于可编程交换机数据平面的Valinor网络内变体。

Valinor-N由三部分组成：

switch component
采集器数据平面
分析组件

Valinor-N能够

在关键路径之外，以零开销捕获每包到达的时间戳
收集和存储以线速到达的时间戳条目
对时间戳数据进行各种分析，以提供不同规模的流量burstiness的深入分析

Valinor交换机

交换机数据面程序使用PISA架构中的mirroring和timestamping功能。对于每一个符合用户定义的流量过滤器的数据包，Valinor-N将到达时间戳、排队延迟和原始数据包的大小以及它的l-4层头信息，append到一个具有预先定义的Valinor头的特殊IP数据包。然后，该数据包被发送到一个收集器服务器。部署在流量端点之间通信的关键路径之外的服务器机器，汇总时间戳信息并进行离线分析。

时间戳收集

采集器机器具有基于DPDK的用户空间数据包处理框架，它解析到达的数据包，并将时间戳信息与流量元数据一起存储到内存中的Redis实例。然后通过查询数据存储进行时间戳数据的分析。以线速度接收时间戳数据包并将其存储在持久性存储中，对收集器组件的设计提出了一些可扩展性的挑战。为了确保软件能够以线速度耗尽网卡缓冲区，我们指定了多个工作线程来读取和处理传入的数据包。在解析了时间戳头之后，工作线程提取了时间戳数据，并将它们发送给负责与Redis通信的其他工作线程。然后，分析框架检索存储的元数据，利用时间戳进行突发分析。

Valinor-N的Redis worker有一些优化。

离线时间戳处理

Valinor设计的最后一部分是离线时间戳分析框架，它查询Redis数据结构并对时间戳数据进行分析。它能够通过测量数据包的到达时间来报告流量突发性的各种统计数据。例如，在下一节中，论文报告了对scaling行为的发现，这是由sender机器中的各种数据包处理组件引起的。论文报告了以字节为单位的实际突发大小、到达间分布、排队延迟和各种突发时间序列分析。离线处理框架用Python实现。

Findings

我们部署了Valinor来分析各种工作负载和配置的突发性。我们的结果表明：

在先前的自我相似性研究中，主机网络在形成和抑制ursts中起着重要作用，这一点基本上被忽略了。
网络处理栈的较低层（如分段卸载和网卡调度）压缩了基于软件的流量整形和主动队列管理解决方案的有效性。
software pacing有很大的局限性。对于短流量和大流量混合的工作负载，网络处理堆栈的较低层掩盖了基于软件的流量调整的影响。对于具有非常短的流量的工作负载，软件步调可以减弱突发事件，但会导致RTT的大幅增加和吞吐量的大幅下降。
网卡驱动器的缓冲区大小和进程调度可以reshape bursts。