Crate violin

source ·
Expand description

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 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:

AbstractionMemoryDimensionsTime
Nodeheap866.537 ms
Coordheap855.402 ms
Nodeheapless824.997 ms
Coordheapless816.552 ms
Nodeheap449.501 ms
Coordheap439.163 ms
Nodeheapless416.795 ms
Coordheapless411.780 ms
Nodeheap254.363 ms
Coordheap246.001 ms
Nodeheapless213.181 ms
Coordheapless210.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.

License

This crate is licensed under either of

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.

Re-exports

Modules

  • error
    This module defines the Result<T> type alias and internal Error type
  • heapalloc
    Defines the VecD coordinate vector that does use heap allocation
  • heapless
    Defines the VecD coordinate vector that does not use any heap allocation

Structs

  • Config
    Tunables that affect how Nodes handle coordinates and updates
  • Coord
    A network coordinate consisting of a dimensional vector, and some metadata
  • Node
    A Node is a higher level construct that abstracts over using Vivaldi and includes things like maintaining adjustment calculations over a window of RTT measurements.

Traits

  • Vector
    The abstraction over coordinate vectors