## Expand description

`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
- License
- 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 `f64`

s. 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 `f64`

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

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.

### 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.

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

## Re-exports

`pub use heap::VecD;`

## Modules

- This module defines the
`Result<T>`

type alias and internal`Error`

type - heap
`alloc`

Defines the`VecD`

coordinate vector that does use heap allocation - Defines the
`VecD`

coordinate vector that does not use any heap allocation

## Structs

- Tunables that affect how
`Node`

s handle coordinates and updates - A network coordinate consisting of a dimensional vector, and some metadata
- 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

- The abstraction over coordinate vectors