violin

violin 是一个 Rust no_std 不 alloc 的 Vivaldi 算法（PDF）网络坐标系统的实现。

网络坐标系统允许节点通过仅交换坐标来精确估计网络延迟。

• violin - 简要介绍
• violin - 反面观点
• 从源代码编译
• 用法
• 基准测试
  • 关于 no_std 性能的注意事项
• 许可证
  • 贡献
• 相关论文和研究

violin - 简要介绍

violin 是一个在 no_std 和无 alloc 环境下工作的 Vivaldi 网络坐标实现。每个坐标都很小，由一个 f64 数组组成的维度向量组成。数组使用 const generics，因此可以小到只有一个 f64，也可以大到一个需要的大小。尽管超过一定维度后会有所减少。

节点可以测量原始节点之间或彼此之间的实际延迟，以调整它们在空间中的坐标。

真正的力量在于能够在不进行实际延迟检查的情况下计算远程坐标之间的距离。例如，节点 A 对节点 Origin 进行测量，节点 B 也这样做。然后 A 可以得到 B 的坐标，并准确估计延迟，而无需直接测量 B。

violin - 反面观点

Vivaldi 并非万能钥匙，仍然需要测量实际延迟来调整坐标。在简单的实现中，在坐标计算之前进行延迟检查并不比直接将延迟检查作为答案好多少。然而，这并非其预期用途。

在实际中传输 Violin 坐标可以与一小组 ICMP 消息相当。例如，一个 8 维度坐标（加上三个额外的 f64 元数据）是 88 字节。然而，与 ICMP 消息不同，Violin 坐标是单次传输，并且仅在发生重大变化时才需要重新传输。甚至可以工作在仅传输 delta 的基础上。

从源代码编译

请确保已安装 Rust 工具链。

$ git clone https://github.com/kbknapp/violin
$ cd violin
$ RUSTFLAGS='-Ctarget-cpu=native' cargo build --release

注意： 可以省略 RUSTFLAGS。然而，如果是在支持 SIMD 指令的较新 CPU 上，并且代码将在为该 CPU 编译的同一 CPU 上运行，包括此标志可以提高性能。

用法

请参阅此存储库中的 examples/ 目录以获取完整详细信息，尽管从快速浏览中，创建三个坐标（origin、a 和 b）以及从经验中的真实延迟更新 a 和 b 的坐标看起来像这样

use std::time::Duration;
use violin::{heapless::VecD, Coord, Node};

// Create two nodes and an "origin" coordinate, all using a 4-Dimensional
// coordinate. `VecD` is a dimensional vector.
let origin = Coord::<VecD<4>>::rand();
let mut a = Node::<VecD<4>>::rand();
let mut b = Node::<VecD<4>>::rand();

// **conduct some latency measurement from a to origin**
// let's assume we observed a value of `0.2` seconds...
//
// **conduct some latency measurement from b to origin**
// let's assume we observed a value of `0.03` seconds...

a.update(Duration::from_secs_f64(0.2), &origin);
b.update(Duration::from_secs_f64(0.03), &origin);

// Estimate from a to b even though we never measured them directly
println!("a's estimate to b: {:.2}ms", a.distance_to(&b.coordinate()).as_millis());

基准测试

包含了一组基准测试，使用 8D、4D 和 2D 坐标，这些坐标都使用 heap::VecD（需要 alloc 功能）和 heapless::VecD。

这些基准测试测量了高级别的 Node 以及低级别的 Coord 抽象。

为了进行测量，我们创建了 10,000 个坐标，并且每个坐标更新 100 次，总共 1,000,000 次更新。

在我的 8 核 AMD Ryzen 7 5850U 笔记本电脑上（16GB RAM），基准测试如下所示

要运行基准测试，请使用 RUSTFLAGS='-Ctarget-cpu=native' cargo bench。

关于 no_std 性能的注意事项

no_std 版本要慢得多，因为它无法使用平台内建函数进行平方根、浮点数舍入等操作。相反，必须手动编写这些函数。

此外，no_std 平方根函数向上取整到 8 位精度。

只有在有很好的理由时才应实际使用 no_std 版本，例如嵌入式设备完全不支持 std。

单个 Vivaldi 计算只需要对每个距离估计进行一次平方根计算。因此，这种设备每秒需要计算数千次平方根操作的情况应该是很少见的。

但我知道你在问多少慢，以下是一个表格（尽管只有 heapless::VecD），仍然是 1,000,000 次更新

再次强调，低功耗设备快速进行 1,000,000 次更新而不使用 std 的情况应该是很少见的。

许可证

此软件包的许可协议为 Apache License，版本 2.0 或 MIT 许可证，任选其一。

• Apache License，版本 2.0
• MIT 许可证

任选其一。

贡献

除非您明确表示不同意，否则您有意提交给作品以供包含的贡献，如 Apache-2.0 许可证中定义，应按上述方式双许可，不附加任何额外条款或条件。

相关论文和研究

• Vivaldi - 一个去中心化网络坐标系统(PDF)
• 野外的网络坐标(PDF)
• 向网络三角形不等式违反意识分布式系统迈进(PDF)
• 关于欧几里得嵌入对基于主机网络坐标系统的适用性(PDF)
• 实用的分布式网络坐标(PDF)
• Armon Dadgar 在 Vivaldi：去中心化网络坐标系统(视频)