vivaldi-nc - Vivaldi Network Coordinates

Introduction

Network Coordinates (NC) are a way to represent a node's position in a network's latency space. Nodes with low latency (ping or round trip time) between each other will be close to each other. Nodes with high latency between them will be far from each other.

This is an implementation of Vivaldi Network Coordinates, a specific NC algorithm, with a simple interface and few dependencies. Vivaldi coordinates are typically used in distributed networking applications, like p2p networks. They allow each node in the network to estimate its position in a latency space in a distributed way, with no central authority. This enables nodes to understand estimated latency to any other node in the system.

According to the Vivaldi coordinates article on Wikipedia:

Vivaldi Network Coordinates establish a virtual positioning system that has a prime use in networking. The algorithm behind the system uses a distributed technique to estimate propagation times between peers in the network.

Through this scheme, network topology awareness can be used to tune the network behaviour to more efficiently distribute data. For example, in a peer-to-peer network, more responsive identification and delivery of content can be achieved. In the Azureus application, Vivaldi is used to improve the performance of the distributed hash table that facilitates query matches.

Advantages

• Vivaldi is a fully distributed scheme, which achieves good scalability.
• The Vivaldi algorithm is simple and easy to implement.

Drawbacks

• Vivaldi is based on the Euclidean distance model, which requires the predicted distances to obey the triangle inequality. However, there are many triangle inequality violations (TIVs) on the Internet.
• Lack of security design, very easy for malicious nodes to conduct various attacks.

Citation: Frank Dabek, Russ Cox, Frans Kaashoek, Robert Morris (2004). "Vivaldi: A Decentralized Network Coordinate System" (PDF). Proc. of the annual conference of the Special Interest Group on Data Communication (SIGCOMM'04).

Addressing the Drawbacks

Regarding the two drawbacks mentioned by the Wikiepedia article, quoted above:

• Euclidean distance: The original paper proposed a height vector model which is superior to the Euclidean distance. This crate implements the height vector model. This provides reasonable accuracy and convergence while remaining simple to implement.
• Lack of security: This is not addressed by this crate. Anyone sharing network coordinates among nodes in a network should use appropriate cryptography.

Usage

Getting Started

Add the crate to your project:

bash cargo add vivaldi-nc

Each node in the network should create a NetworkCoordinate (NC). The node uses this structure to track its latency position in the entire network.

```rust use vivaldinc::networkcoordinate::NetworkCoordinate;

// create a 2-dimensional NetworkCoordinate to track my position let mut my_position = NetworkCoordinate::<2>::new(); ``` Normally 2 or 3-dimensions is plenty. Higher dimensions may add some accuracy, but not enough to be worth the extra costs.

Each node occasionally sends its NC to other nodes. Upon receiving a NC from a remote node, update your local node's position with the actual measured ping time to that node.

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

Over time your NC will get more and more accurate as it's updated against more nodes in the network.

You can estimate your ping time with any other NC you receive, even if it was forwarded to you indirectly.

rust let rtt_estimate = my_position.estimate_rtt(&remote_position);

That's the entire interface for creating and iteratively updating NCs.

If you want to save/restore NCs, or send/receive them over a network, you'll want to serialize/deserialize them. NetworkCoordinate supports Serde by default. Many formats are supported by Serde, including text formats like JSON and compact binary formats like bincode and MessagePack.

Features

Examples

Dependencies

One design goal of this crate is to minimize dependencies. When dependencies are required, I try to be very selective about them (re: bloat and licensing). This crate depends on:

• nanorand: A fast PRNG based on WyRand. It pulls in getrandom as a portable source of entropy. I chose this over the more commonly used, but heavyweight rand because it's significantly smaller and does just what I need, and not much more.
• num-traits: A brilliant crate which makes it easier to operate on numbers in generics; like using Float as a constraint on a generic type. Its convenience outweighs its cost.
• serde: I think NCs are usually meant to be shared across a network. That requires serialization/deserialization and serde is the choice for that. It might be big, but it's efficient.
• serde_with: Because the inner Vector<T,N> uses a const generic length, we use this to help derive Deserialize.

Alternative implementations

Several crates implemented Vivaldi NC before this one. So, why another?

I had several design goals which the existing crates didn't satisfy:

1. Provide the simplest interface possible. I just want to have some sort of Coordinate struct and be able to update it, and then use it to estimate round trip times (ie ping times).
2. Don't require the consumer to bring their own vector or linear algebra library. The linear algebra required by this is extraordinarily simple. I want it to just work without me needing to inject some large, mostly-unused library.
3. Serializable/Deserializable by default. These things are useful for sending across networks. The intent is to be able to do that without a bunch of rigamarole. Support serde traits by default.
4. Well documented. Well tested. This varies by the crates.

All of that said, those other rust implementations might work best for you. Here are the ones I know of today:

• netloc
• violin
• vivaldi

Other Algorithms

Vivaldi is about the simplest distributed NC algorithm out there. That simplicity combined with its reasonably good performance is a reason why it's popular.

But it's far from the only choice. Here are links to other NC algorithms:

• TODO: list algorithms
• TODO: list algorithms
• TODO: list algorithms