violin

A Rust no_std no alloc implementation of the Vivaldi algorithm(PDF) for a network coordinate system.

A network coordinate system allows nodes to accurately estimate network latencies by merely exchanging coordinates.

• Violin - The Pitch
• Violin - The Anit-Pitch
• Compile from Source
• Usage
• Benchmarks
  • Notes on no_std Performance
• License
  • Contribution
• Related Papers and Research

Violin - The Pitch

Violin is an implementation of Vivaldi network coordinates that works in no_std and no alloc environments. Each coordinate is small consisting of a dimensional vector made up of an array of f64s. The arrays use const generics, so they can be as small as a single f64 or large as one needs. Although above a certain dimension there are diminishing returns.

Nodes can measure real latencies between an origin node, or each-other to adjust their coordinates in space.

The real power comes from being able to calculate distance between a remote coordinate without ever having done a real latency check. For example node A measures against node Origin, node B does the same. Then A can be given the coordinates to B and accurately estimate the latency without ever having measured B directly.

Violin - The Anit-Pitch

Vivaldi isn't a magic bullet and still requires measuring real latencies to adjust the coordinates. In a naive implementation, conducting a latency check prior to a coordinate calculation is not much better than just using the latency check directly as the answer. However, this is not how it's supposed to be used.

Transferring a Violin coordinate in practice can be comparable data to a small set of ICMP messages. For example an 8-Dimension coordinate (plus three additional f64s of metadata) is 88 bytes. However, unlike ICMP messages, the Violin coordinates are a single transmission and only need to be re-transmitted on significant change. Work could even be done to only transmit deltas as well.

Compile from Source

Ensure you have a Rust toolchain installed.

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

NOTE: The RUSTFLAGS can be omitted. However, if on a recent CPU that supports SIMD instructions, and the code will be run on the same CPU it's compiled for, including this flag can improve performance.

Usage

See the examples/ directory in this repository for complete details, although at quick glance creating three coordinates (origin, a and b) and updating a and b's coordinate from experienced real latency would look like this:

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());

Benchmarks

A set of benchmarks are included using 8D, 4D, and 2D coordinates both using heap::VecD (requires the alloc feature) and heapless::VecD.

The benchmarks measure both the higher level Node as well as a lower level Coord abstractions.

To measure we create 10,000 coordinates and the coordinates are update for each coordinate 100 times, totaling 1,000,000 updates.

On my 8 core AMD Ryzen 7 5850U laptop with 16GB RAM the benchmarks look as follows:

To run the benchmarks yourself use RUSTFLAGS='-Ctarget-cpu=native' cargo bench.

Notes on no_std Performance

The no_std version is much slower because it cannot use platform intrinsics for square roots, floating point rounding, etc. Instead these functions had to be hand written.

Additionally, the no_std square root functions round up to 8 decimals of precision.

One should realistically only use the no_std version when there is a good reason to do so, such as an embedded device that absolutely does not support std.

A single Vivaldi calculation only requires one square root calculation per distance estimate. So pragmatically, it should be rare where such a device is also needing to calculate thousands of square root operations per second.

But I still hear you, how much slower you ask? Here is the same table (although only heapless::VecD), still 1,000,000 updates:

Again, it should be rare for a low power device to need to do 1,000,000 updates rapidly and not have the ability to use std.

License

This crate is licensed under either of

• Apache License, Version 2.0
• MIT license

at your option.

Contribution

Unless you explicitly Node otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Related Papers and Research

• Vivaldi - A Decentralized Network Coordinate System(PDF)
• Network Coordinates in the Wild(PDF)
• Towards Network Triangle Inequality Violation Aware Distributed Systems(PDF)
• On Suitability of Euclidean Embedding for Host-based Network Coordinate Systems(PDF)
• Practical, Distributed Network Coordinates(PDF)
• Armon Dadgar on Vivaldi: Decentralized Network Coordinate System(Video)