violin
An Rust no_std no alloc implementation of the Vivaldi algorithm(PDF)
for a decentralized network coordinate system.
A network coordinate system allows nodes to accurately estimate network latencies by merely exchanging coordinates.
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.
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.
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.
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:
```rust use std::time::Duration; use violin::{heapless::VecD, Coord, Node};
fn main() {
// Create two nodes and an "origin" coordinate, all using a 4-Dimensional
// coordinate. VecD is a dimensional vector.
let origin = Coord::
// **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());
} ```
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.
This crate is licensed under either of
at your option.
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.