Lib.rs

vivaldi

维瓦尔第算法的实现，用于高效地使用 n 维欧几里得模型进行 RTT 延迟估计。

• 完全去中心化
• 准确预测模型中任意两个节点之间的 RTT（± ~11%）
• 低开销 - O(n) 内存使用，用于 n^2 网络路径
• 快速适应节点间由于重新路由等原因引起的延迟变化

算法

维瓦尔第算法由 Frank Dabek、Russ Cox、Frans Kaashoek 和 Robert Morris 于 2004 年提出，后续在 后续论文 中由其他人提出了改进。

大多数人认为互联网是由一系列管道组成的。的确，他们似乎错了——它是由弹簧组成的。

作者描述了他们开发的一种算法，将节点之间的通信延迟映射到 N 维欧几里得空间中的坐标，两点之间的距离大致等于两个节点之间的 RTT。

该算法将 RTT 视为遵循胡克定律（我认为这很酷）的自然弹簧长度，每个弹簧的势能作为估计误差的类似物。最小化系统中弹簧的势能可以最小化模型的估计误差。论文中描述了对收敛时间和精度的改进。它是个好东西，你应该读一读！

使用它

此实现是针对原始论文中描述的算法——没有更新过滤器（这需要在每个节点上存储更多状态）或后续文本中提出的重力。调用者负责存储每个节点的最后一个已知坐标，以便稍后推导任何一对节点之间的 RTT 估计。

维瓦尔第算法通常在您的正常应用程序网络消息上运行，坐标嵌入在请求数据和响应元数据中。应用程序测量请求的 RTT 并使用它以及远程发送的坐标来更新本地的 Model。

维度

尽管此实现通用于任意数量的维度，但作者的主成分分析表明，超过 3 个维度的好处很小，如果要将开销保持在最低，则 2 个维度就足够了。