vivaldi-nc - Vivaldi 网络坐标

• vivaldi-nc - Vivaldi 网络坐标
  • 简介
    • 解决缺点
  • 用法
    • 入门指南
    • Cargo 功能
    • 示例
  • 依赖关系
  • 设计目标与替代方案
    • 其他 Vivaldi NC 实现
    • 其他 NC 算法
  • 获取帮助或贡献
  • 许可证

简介

网络坐标 (NC) 是一种表示网络延迟空间中节点位置的方法。延迟（ping 或往返时间）低的节点彼此靠近。延迟高的节点彼此远离。

这是 Vivaldi 网络坐标的实现，它是一种特定的 NC 算法，具有简单的接口和少量依赖项。Vivaldi 坐标通常用于分布式网络应用程序，如 p2p 网络。它允许网络中的每个节点以分布式方式估计其在延迟空间中的位置，无需中央权威。这使得节点可以了解系统内任何其他节点的估计延迟。

根据维基百科上的 Vivaldi 坐标文章

Vivaldi 网络坐标建立了一个虚拟定位系统，该系统在网络中具有主要用途。系统背后的算法使用分布式技术来估计网络中对等体之间的传播时间。

通过此方案，可以利用网络拓扑意识来调整网络行为，以更有效地分配数据。例如，在点对点网络中，可以实现更响应的标识和内容交付。在 Azureus 应用程序中，Vivaldi 用于提高分布式哈希表（该表便于查询匹配）的性能。

优点

• Vivaldi 是一个完全分布的方案，具有很好的可扩展性。
• Vivaldi 算法简单，易于实现。

缺点

• Vivaldi 基于欧几里得距离模型，要求预测的距离遵循三角不等式。然而，互联网上存在许多违反三角不等式（TIV）的情况。
• 缺乏安全设计，恶意节点进行各种攻击非常容易。

引用：Frank Dabek, Russ Cox, Frans Kaashoek, Robert Morris (2004)。"Vivaldi：一个去中心化的网络坐标系统" (PDF)。数据通信特别兴趣组（SIGCOMM'04）年度会议论文集。

解决缺点

关于上文提到的维基百科文章的两个缺点

• 欧几里得距离：原始论文提出了一种高度向量模型，该模型优于欧几里得距离。此crate实现了高度向量模型。这提供了合理的准确性和收敛性，同时易于实现。
• 缺乏安全性：此crate没有解决这个问题。在网络中的节点间共享网络坐标时，应使用适当的加密。

用法

入门指南

将crate添加到您的项目中

cargo add vivaldi-nc

网络中的每个节点应创建一个 NetworkCoordinate (NC)。节点使用此结构来跟踪其在整个网络中的延迟位置。

use vivaldi_nc::NetworkCoordinate;

// create a 2-dimensional NetworkCoordinate to track my position
let mut my_position = NetworkCoordinate::<2>::new();

通常2或3维足够。更高的维度可能会增加一些准确性，但不足以弥补额外成本。

每个节点偶尔会将其NC发送到其他节点。在收到远程节点发送的NC后，使用对该节点实际测量的ping时间更新本地节点的位置。

my_position.update(&remote_position, Duration::from_millis(measured_rtt));

随着时间的推移，您的NC将变得越来越准确，因为它会根据网络中更多的节点进行更新。

您可以使用收到的任何其他NC来估计您的ping时间，即使它是间接转发给您。

let rtt_estimate = my_position.estimate_rtt(&remote_position);

这就是创建和迭代更新NCs的全部接口。

如果您想保存/恢复NCs，或通过网络发送/接收它们，您需要序列化/反序列化它们。NetworkCoordinate默认支持Serde。Serde支持许多格式，包括文本格式，如JSON，以及紧凑的二进制格式，如bincode和MessagePack。

有关更详细的用法示例，请参阅模块文档。

Cargo 功能

默认情况下，内部数据结构和操作都使用f64，这在现代架构上略快。如果您想使用f32，可以将其作为cargo功能启用。

[dependencies]
vivaldi-nc = { version = "(version)", features = ["f32"] }

示例

存储库中包含一个示例，该示例从PlanetLab加载了490个节点的N-to-N延迟样本，并对NetworkCoordinate迭代，直到达到足够低的平均误差。输出是一个包含NC的位置、其高度（或干线延迟估计）和其估计误差（越低越好）的JSON数组。

{
  "position": [
    5.563593,
    -2.332495,
    7.3957834
  ],
  "height": 55.56651,
  "error": 3.241348
}

对这三个字段添加一些细节

• position：估计此节点（或NetworkCoordinate）在网络核心的位置。将其视为节点进入互联网骨干的端点。这是一个多维度延迟空间（在这种情况下为3D）中的笛卡尔坐标，以毫秒为单位。
• height：估计的干线时间，即从节点本身到骨干的时间。例如，这可能表示您的节点实际位置（例如您的家）与进入互联网最高速核心部分的点的延迟。高度有助于调整三角不等式违反，这在互联网上很常见。
• error：当前position和height的估计误差。越低越好。

要运行示例，首先在本地克隆存储库

git clone https://git.sr.ht/~swaits/vivaldi-nc

然后 cd 到本地克隆目录并运行示例

cd vivaldi-nc
cargo run --example planetlab

依赖关系

这个crate的设计目标之一是尽量减少依赖。当需要依赖项时，我会非常谨慎地选择（关于膨胀和许可）。这个crate依赖于

• rand：我开始使用 nanorand；然而，由于使用了 rand::thread_rng()，这使得它更快；而使用 nanorand 时，我们最终需要通过类似 lazy_static! 加上 Mutex 的方式来实现相同的功能，这对提高几个百分点的性能来说并不值得。
• num-traits：一个出色的crate，它使得在泛型中操作数字变得更加容易；例如，使用 Float 作为泛型类型的约束。它的便利性超过了它的成本。
• serde：我认为网络坐标（NC）通常意味着要在网络中共享。这需要序列化和反序列化，而serde是此任务的最佳选择。它可能很大，但效率很高。
• serde_with：因为内部 Vector<T,N> 使用了const泛型长度，所以我们使用这个crate来帮助推导 Deserialize。
• array-init：使得内部 Vector 的数组操作更加简洁。一旦我们有了 feature(array_zip) 稳定下来，我们就可以使用它了。在此之前，这个crate与零性能影响很好地协同工作。
• cfg-if：一个仅在编译时使用的宏，它使得在代码中使用 cfg 参数变得更加方便。

设计目标与替代方案

在此之前，已有几个crate实现了Vivaldi NC。那么，为什么还需要另一个呢？

我有几个设计目标，这些现有的crate无法满足，按照优先级排序

1. 提供尽可能简单的接口。我只是想有一个某种形式的Coordinate结构体，能够更新它，然后使用它来估计往返时间（即ping时间）。
2. 不需要消费者自带向量或线性代数库。这个crate需要的线性代数非常简单。我希望它能直接工作，而无需我注入一个大型、大部分未被使用的库。
3. 默认可序列化和反序列化。这些特性对于通过网络发送非常有用。意图是能够无需繁琐操作就完成这些操作。默认支持 serde 特性。
4. 良好的文档。良好的测试。这在现有的crate中有所不同。
5. 性能。虽然这是一个较低优先级的目标，但它应该是合理的。在我的Macbook Pro（Intel i7-9750H（12）@ 2.60GHz）上，该库每毫秒大约执行10,000次 NetworkCoordinate::update() 调用。

其他 Vivaldi NC 实现

所有这些话都说了，其他rust实现可能更适合您。以下是我今天知道的一些实现

• netloc
• violin
• vivaldi

其他 NC 算法

Vivaldi是现有分布式NC算法中最简单的一个。这种简单性与它合理的性能相结合，是它受欢迎的原因之一。

但远不止如此。以下是一些其他NC算法的链接

• Pharos
• Phoenix

在您最喜欢的科研论文索引中搜索“网络坐标”，您将找到更多。

获取帮助或贡献

要获取帮助或讨论此软件包，请提交工单或在该链接vivaldi-nc-discuss@发帖。

与开发或补丁提交相关的讨论应发送到vivaldi-nc-devel@。

如果您想直接贡献代码改进或修复，您应在Sourcehut上创建一个免费账户，克隆存储库，然后使用UI发送补丁。

否则，您可以通过git-send-email或通过sr.ht UI（在我看来最简单）发送补丁集。

提交补丁的人默示同意他们提交的所有贡献都符合MIT许可。

许可证

MIT许可

版权所有（c）2023 Stephen Waits

特此授予任何获得此软件及其相关文档文件（以下简称“软件”）副本的任何人免费使用软件的权利，包括但不限于使用、复制、修改、合并、发布、分发、再许可和/或销售软件副本的权利，并允许向软件提供的人以这种方式行事，前提是遵守以下条件

上述版权声明和本许可声明应包含在软件的所有副本或主要部分中。

软件按“原样”提供，不提供任何明示或暗示的保证，包括但不限于适销性、特定用途适用性和非侵权性保证。在任何情况下，作者或版权所有者均不对任何索赔、损害或其他责任负责，无论这些责任源于合同、侵权或其他方式，无论这些责任是否与软件或其使用或其他方式有关。