spin_bit

status-badge Build status

Tiny C++ header implementation of spin bit based RTT measurements in network traffic.

This library is inspired by QUIC, and based on Piet De Vaere's master thesis (a copy can be found in the docs/ folder for archiving purposes).

Overview

The spin bit is a single bit that the client in a network connection sends, and the server reflects back. When the client receives a bit with the same value it has sent, it flips the bit for the next packet it sends. In this way, an observer in the middle can infer a round-trip and time it accordingly.

However, the spin bit mechanism is not robust in the face of packet re-ordering or outright loss. To mitigate this, the above master thesis introduces an additional two bits of Vector Edge Counter (VEC), the value of which permits determines whether an edge of a spin bit signal is valid.

This library implements the spin bit + VEC algorithm on the sender and receiver side, and provides a "generator" that additionally produces matching packet numbers. It also provides a basic observer, and a VEC-based observer for analysing round-trip times.

Note that this repository started as jfinkhaeuser/spin-bit, but has since diverged.

Usage

It's important for the usage to determine in which direction packets flow, e.g. either from client to server or in the opposite direction. Unfortunately, terminology for these directions differs depending on the point of view. For client and server both, packets are either incoming (ingress) or outgoing (egress). However, an egress packet on one side becomes an ingress packet on the other side. The basic usage uses such terminology.

For the observer, it is typically thought of as sitting in the middle between the two. For a packet sent from client to server, this packet travels upstream. The response packet from server to client travels downstream, instead. A full round-trip measurement is based on two half round-trip measurements, one upstream and one downstream.

It is perfectly possible for the observer to reside on the client or server directly. In this case, one of the two half measurements will be practically zero, while the other bears the full RTT time.

This library introduces a flow_direction enum to abstractly name these directions, which maps ingress/egress names to upstream/downstream names. It is important to highlight that this is just convenience to have a two-value direction enum; it is not a semantic mapping. An ingress packet on the server flows upstream, while an ingress packet on the client flows downstream. Users must take care of not confusing this.

Basic Usage

The first thing is to declare your state structure. You can use e.g. a bool as the spin bit flag, and an array of bool for the VEC, but also a std::bitset works. Finally, use an integer type as a packet number type. These types and the values held in the state do not need to be identical with what you send over the wire, of course, as long as you can unambiguously map from one to the other.

#include <spin_bit/state.h>
using state = spin_bit::state<
 bool, // spin bit itself
 bool [2], // VEC
 uint32_t // packet number
>;
state client_state; // or server_state, etc.

Next, two functions are used to either update the state, or generate values from the state. Incoming packets just update the state.

#include <spin_bit/packet.h>
auto ret = spin_bit::on_incoming_packet(client_state,
 spin_bit_from_packet,
 vec_from_packet,
 packet_number_from_packet);

The function returns if the state has been updated. It may not update the state if there is no need to according to the spin bit/VEC algorithms. This is not an error.

On the sending side, you need to generate a spin bit and a VEC from the current state. Here, it matters if your code is in client or server role. Remember, the client may flip the state bit, while the server reflects it.

#include <spin_bit/packet.h>
bool spin_bit_to_packet;
bool vec_to_packet[2];
spin_bit::on_outgoing_packet<true>(client_state,
 spin_bit_to_pcket, vec_to_packet,
 TIMEOUT);
// or

spin_bit::on_outgoing_packet<false>(server_state,
 spin_bit_to_pcket, vec_to_packet,
 TIMEOUT);

There is a TIMEOUT mentioned above. This is a value the VEC algorithm needs for determining whether an edge is delayed. It should be any reasonable value for an expected round-trip time for your use case.

Note that you might wish to adjust such a value dynamically based on RTTs you measure. Alternatively, your application might require some kind of real-time like behaviour, in which case these requirements should be used to derive a good timeout value from.

The TIMEOUT is in chrono units, e.g. std::chrono::milliseconds, etc.

That's the basic usage. If you send the VEC and spin bit generated here, the receiving side should be able to update statea appropriately.

Note, however, that the VEC algorithm relies on incrementing packet numbers.

Generator Usage

In order to better deal with handling the interconnection between the spin bit and VEC states and packet numbers, you can use the generator helper struct. It doesn't actually generate e.g. packet numbers itself, but offloads that to a function. However, it produces a matching set of spin bit, VEC and packet number per invocation.

#include <spin_bit/generator.h>
using client_generator = spin_bit::generator<state, true>;
client_generator client{
 TIMEOUT, // See above
 42, // Initial packet number
 [](uint32_t prev){ return prev + 1; } // Packet number function
};
auto [success, meta] = client.produce();
// success is a boolean flag
// meta contains the fields:
// - packet_number
// - spin_bit
// - vec

The function always returns true in client mode. In server mode, you cannot produce packet metainformation without having first received some incoming metainformation.

auto success = server.consume(spin_bit, vec, packet_number);

By contrast, the consume function returns true if state was updated, false if there was no need.

Observer Usage

Given client and server implementations such as above, a VEC observer is easy to place in the middle.

#include <spin_bit/observer.h>
using observer = spin_bit::vec_observer<state>;
observer obs;
auto [type, dir, duration] = obs.observe(direction, spin_bit, vec, packet_number);

Here, the direction fed to the observer is one of spin_bit::DIR_UPSTREAM or spin_bit::DIR_DOWNSTREAM, as discussed above. The other values are those observed in the passing packet.

The type result indicates what kind of measurement could be taken. This is one of the following values:

If any RTT was returned, it's in the duration value.

Note that the SAMPLE_ERROR_RESET result is not so much a hard error as an effect of the VEC observer giving up on a measurement. This is much preferable to providing a false measurement, as a simpler observer would return.

And that's it! That is what this library does.