Delay-Based Metric Extension for the Babel Routing Protocol
Extracted elements (24)
Existing Babel implementations use packet-loss-based or hop-count metrics and fail to prefer lower-latency routes in topologies with tunnels or VPNs. In a diamond topology with three Paris routers and one Tokyo router, hop-count treats both paths as equal, routing half the traffic through Tokyo unnecessarily.
Raw RTT samples are not directly usable for route selection because: (1) bursty traffic causes transient congestion spikes, (2) using RTT directly creates a negative feedback loop that causes oscillations, and (3) even without congestion, small RTT variations between parallel routes would trigger frequent re-routing that disrupts TCP.
The extension requires only negligible clock drift within the Hello interval (a few seconds), not synchronized clocks. This requirement is met even by cheap crystal oscillators in consumer electronics, making the extension broadly deployable.
The protocol is explicitly applicable only where symmetric delay is a good predictor of link quality. It is inapplicable in networks that need to distinguish between very low-latency links (all below rtt-min are treated equally) or in networks with high node mobility, where the slow-reacting hysteresis causes prolonged suboptimal routing.
The protocol uses Mills' algorithm (originally from the HELLO routing protocol, later used in NTP) for RTT estimation because it does not require synchronized clocks—it only ever computes differences of timestamps from a single clock—and requires minimal state: just two timestamps per neighbour.
If a Timestamp sub-TLV is longer than expected, the additional data is silently ignored to allow future protocol versions to extend the format with additional data such as high-precision or absolute timestamps.
This extension stores data in sub-TLVs of Hello and IHU TLVs. Unextended Babel implementations silently ignore unknown sub-TLVs per RFC 8966 Appendix D, so hybrid networks of extended and unextended routers are possible; they may have sub-optimal routing but will not have routing loops.
A node MUST include a timestamp t1 (from its local clock) in every Hello that it sends, in order to enable RTT computation by the receiving neighbour.
Implementations SHOULD use a robust hysteresis algorithm (such as the one in Appendix A.3 of RFC 8966) to limit cost oscillation when a link's RTT falls between rtt-min and rtt-max.
Implementations SHOULD use the bounded piecewise-linear cost mapping: flat at nominal hop cost C below rtt-min, linear increase between rtt-min and rtt-max, flat at C + max-rtt-penalty above rtt-max. RECOMMENDED defaults: rtt-min=10ms, rtt-max=120ms, max-rtt-penalty=150.
Smoothing SHOULD be applied to RTT samples to avoid instabilities due to occasional outliers. An exponential moving average with constant α is RECOMMENDED, with α SHOULD be between 0.8 and 0.9 and the RECOMMENDED default being 0.836.
Transmit timestamps SHOULD be computed just before the packet is passed to the network stack (before queueing delays); receive timestamps SHOULD be computed just after the packet is received from the network stack.
Upon receiving B's packet, A MUST verify it contains both a Hello TLV with timestamp t2' and an IHU TLV with timestamps t1 and t1' before computing RTT = (t2 - t1) - (t2' - t1') modulo 2^32.
Very old timestamps or nonsensical timestamps MUST NOT be used to yield RTT samples. Timestamps appearing to be in the future or more than T=3 minutes in the past should be recorded but not used for RTT computation.
When a node B receives a timestamped Hello from A, it MUST record the Hello's timestamp as the Origin Timestamp and the local receipt time as the Receive Timestamp in the Neighbour Table entry for A.
When B sends an IHU to A and both timestamps are defined, B MUST ensure the IHU TLV is sent in a packet that also contains a timestamped Hello TLV, and MUST include both the Origin Timestamp and Receive Timestamp in the IHU.
Timestamps use an arbitrary origin, so they do not leak a node's boot time or time zone. However, accurate timestamps may allow an attacker to determine physical location. Nodes may omit Timestamp sub-TLVs to avoid location disclosure, at the cost of falling back to hop-count routing for their neighbours.
Implementation strategy for accurate timestamping: buffer a Hello TLV with a 4-octet PadN sub-TLV placeholder; overwrite it with the Timestamp sub-TLV containing the current time immediately before the packet is handed to the network stack. On receive, record the timestamp immediately upon reception before further processing.
The Neighbour Table entry is extended with two fields: Origin Timestamp (32-bit, neighbour's clock) and Receive Timestamp (32-bit, local clock). Both are initially undefined and are updated upon receiving a timestamped Hello from that neighbour.
Wrap-around detection: timestamps are 32-bit microsecond counters that wrap every ~71 minutes. On node restart the clock origin is arbitrary, so timestamps from before a reboot may appear as large forward jumps or nonsensical values and must be discarded.
IANA added Type 3 with name 'Timestamp' to the 'Babel Sub-TLV Types' registry, referencing RFC 9616.
Broadcasting a reasonably accurate local clock value in Hello and IHU TLVs may make a node more susceptible to timing attacks. An attacker with access to accurate timestamps could potentially determine the physical location of a node.
Timestamp sub-TLV in a Hello TLV: Type=3 (1 octet), Length (1 octet), Transmit Timestamp (32-bit unsigned integer, microseconds from arbitrary origin). Body length is 4 octets. If Length < 4, the sub-TLV MUST be ignored; if Length > 4, extra data MUST be silently ignored.
Timestamp sub-TLV in an IHU TLV: Type=3 (1 octet), Length (1 octet), Origin Timestamp (32-bit, copy of neighbour's Transmit Timestamp), Receive Timestamp (32-bit, local time of receipt). Body length is 8 octets. If Length < 8, MUST be ignored; if Length > 8, extra data MUST be silently ignored.