Skip to content

Latest commit

 

History

History
205 lines (154 loc) · 7.91 KB

README.md

File metadata and controls

205 lines (154 loc) · 7.91 KB
Raw

violin

Rust Version crates.io Documentation Dependency Status

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 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 Anti-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, and have cloned the repository locally.

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:

Abstraction Memory Dimensions Time
Node heap 8 66.537 ms
Coord heap 8 55.402 ms
Node heapless 8 24.997 ms
Coord heapless 8 16.552 ms
Node heap 4 49.501 ms
Coord heap 4 39.163 ms
Node heapless 4 16.795 ms
Coord heapless 4 11.780 ms
Node heap 2 54.363 ms
Coord heap 2 46.001 ms
Node heapless 2 13.181 ms
Coord heapless 2 10.916 ms

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:

Abstraction Memory Dimensions Time
Node heapless 8 6.4303 s
Coord heapless 8 6.3707 s
Node heapless 4 6.5513 s
Coord heapless 4 6.4179 s
Node heapless 2 6.5722 s
Coord heapless 2 6.3005 s

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

at your option.

Contribution

Unless you explicitly note 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