Repository files navigation

A Rustno_std noalloc implementation of theVivaldi algorithm(PDF)for a network coordinate system.

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

• Violin - The Pitch
• Violin - The Anti-Pitch
• Compile from Source
• Usage
• Benchmarks
  • Notes onno_std Performance
• License
  • Contribution
• Related Papers and Research

Violin is an implementation of Vivaldi network coordinates that works inno_std and noalloc environments. Each coordinate is small consisting of adimensional vector made up of an array off64s. The arrays use constgenerics, 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 toadjust their coordinates in space.

The real power comes from being able to calculate distance between a remotecoordinate without ever having done a real latency check. For example nodeAmeasures against nodeOrigin, nodeB does the same. ThenA can be giventhe coordinates toB and accurately estimate the latency without ever havingmeasuredB directly.

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

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

Ensure you have aRust toolchain installed, and have cloned the repository locally.

RUSTFLAGS='-Ctarget-cpu=native' cargo build --release

NOTE: TheRUSTFLAGS can be omitted. However, if on a recent CPU thatsupports SIMD instructions, and the code will be run on the same CPU it'scompiled for, including this flag can improve performance.

See theexamples/ directory in this repository for complete details, althoughat quick glance creating three coordinates (origin,a andb) and updatinga andb'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();letmut a =Node::<VecD<4>>::rand();letmut 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 directlyprintln!("a's estimate to b: {:.2}ms", a.distance_to(&b.coordinate()).as_millis());

A set of benchmarks are included using 8D, 4D, and 2D coordinates both usingheap::VecD (requires thealloc feature) andheapless::VecD.

The benchmarks measure both the higher levelNode as well as a lower levelCoord abstractions.

To measure we create 10,000 coordinates and the coordinates areupdate 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 asfollows:

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

Theno_std version ismuch slower because it cannot use platform intrinsicsfor square roots, floating point rounding, etc. Instead these functions had tobe hand written.

Additionally, theno_std square root functions round up to 8 decimals ofprecision.

One should realistically only use theno_std version when there is a goodreason to do so, such as an embedded device that absolutely does not supportstd.

A single Vivaldi calculation only requires one square root calculation perdistance estimate. So pragmatically, it should be rare where such a device isalso 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 (althoughonlyheapless::VecD), still 1,000,000 updates:

Again, it should be rare for a low power device to need to do1,000,000 updates rapidly and not have the ability to usestd.

This crate is licensed under either of

• Apache License, Version 2.0
• MIT license

at your option.

Unless you explicitly note otherwise, any contribution intentionally submittedfor inclusion in the work by you, as defined in the Apache-2.0 license, shall bedual licensed as above, without any additional terms or conditions.

• 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)