RFC 9616

Delay-Based Metric Extension for the Babel Routing Protocol

📅 published September 2024, from ietf

RFC 9616 💖 Delay-Based Metric Extension for the Babel Routing Protocol

Okay bestie, this is RFC 9616, and it's giving Standards Track ✨ The title is "Delay-Based Metric Extension for the Babel Routing Protocol." It's an IETF document dated September 2024, written by B. Jonglez (ENS Lyon) and J. Chroboczek (IRIF, Université Paris Cité) 🎀 The ISSN is 2070-1721. The header doesn't list anything it obsoletes or updates, so there's no drama there 🌸

Abstract ✨

This doc adds an extension to the Babel routing protocol that measures the round-trip time (RTT) between routers, so you can prefer lower-latency links over higher-latency ones 🦋

Status of This Memo 👑

This is an Internet Standards Track document. It's a product of the Internet Engineering Task Force (IETF), it represents the consensus of the IETF community, it got public review, and the Internet Engineering Steering Group (IESG) approved it for publication. For more on Internet Standards, check Section 2 of RFC 7841. Info about the current status, any errata, and how to send feedback lives at https://www.rfc-editor.org/info/rfc9616 💅

Copyright Notice 🌈

Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as in effect on the date of publication. Please read these carefully, because they spell out your rights and restrictions for this document. Any Code Components pulled out of this document need to include Revised BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Revised BSD License 🔥

Table of Contents 🧚

1.  Introduction
  1.1.  Applicability
2.  Specification of Requirements
3.  RTT Sampling
  3.1.  Data Structures
  3.2.  Protocol Operation
  3.3.  Wrap-Around and Node Restart
  3.4.  Implementation Notes
4.  RTT-Based Route Selection
  4.1.  Smoothing
  4.2.  Cost Computation
  4.3.  Hysteresis
5.  Backwards and Forwards Compatibility
6.  Packet Format
  6.1.  Timestamp Sub-TLV in Hello TLVs
  6.2.  Timestamp Sub-TLV in IHU TLVs
7.  IANA Considerations
8.  Security Considerations
9.  References
  9.1.  Normative References
  9.2.  Informative References
Acknowledgements
Authors' Addresses

1. Introduction ✨

The Babel routing protocol [RFC8966] doesn't mandate a specific algorithm for computing metrics. Existing implementations use a packet-loss-based metric on wireless links and a simple hop-count metric on all other kinds of links. This works pretty well in lots of networks, but it fails to pick reasonable routes in some topologies that involve tunnels or VPNs 🙈

                   +------------+
                   | A (Paris)  +---------------+
                   +------------+                \
                  /                               \
                 /                                 \
                /                                   \
  +------------+                                     +------------+
  | B  (Paris) |                                     | C  (Tokyo) |
  +------------+                                     +------------+
                \                                   /
                 \                                 /
                  \                               /
                   +------------+                /
                   | D (Paris)  +---------------+
                   +------------+

             Figure 1: Four Routers in a Diamond Topology

Let's look at the topology in Figure 1. There are three routers, A, B, and D, all in Paris, and a fourth router, C, in Tokyo. They're connected through tunnels in a diamond shape. When traffic goes from A to D, it's obviously better to use the local route through B, since that's likely to give better service quality and lower monetary cost than the distant route through C. But the existing Babel implementations treat both routes as having the same metric, so they send the traffic through C in roughly half the cases 😭

In the first part of this document (Section 3), we specify an extension to Babel that produces a sequence of accurate round-trip time (RTT) measurements between two Babel neighbours. These measurements can't be used directly as input to Babel's route selection procedure, because they tend to be noisy and can cause a negative feedback loop, which might lead to frequent oscillations. In the second part (Section 4), we define an algorithm that maps the sequence of RTT samples to a link cost that route selection can actually use 💜

1.1. Applicability

The extension defined in Section 3 gives you a sequence of accurate but potentially noisy RTT samples. Since RTT is a symmetric measure of delay, this protocol only applies in environments where symmetric delay is a good predictor of whether a link should carry routed traffic. That might not be true in networks built over exotic link technologies 🛸

The extension asks very little of the nodes. In particular, it doesn't assume synchronised clocks, and it only requires that clock drift be negligible during the time interval between two Hello TLVs. That interval is on the order of a few seconds, so this requirement is met even with cheap crystal oscillators, like the ones in consumer electronics 🍓

The algorithm defined in Section 4 depends on a number of assumptions about the network. The one with the most severe consequences is that all links below a certain RTT (rtt-min in Section 4.2) can be grouped into a single category of "good" links. This holds in wide-area overlay networks, but it makes the algorithm inapplicable in networks where telling apart low-latency links matters 🌸

There are other assumptions, but they're less likely to limit the algorithm's applicability. The algorithm assumes that all links above a certain RTT (rtt-max in Section 4.2) are equally bad, and they'll only be used as a last resort. Also, to avoid oscillations, the algorithm is designed to react slowly to RTT variations, so routing can be suboptimal for seconds or even minutes after an RTT change. That's a desirable property in fixed networks, since it avoids excessive route oscillations, but it might be an issue in networks with high rates of node mobility 🚗

2. Specification of Requirements 📜

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

3. RTT Sampling 🦋

3.1. Data Structures

We assume that every Babel speaker keeps a local clock that counts microseconds from an arbitrary origin. We don't assume that clocks are synchronised, so clocks local to different nodes don't need to share a common origin. The protocol will eventually recover if the clock gets stepped, so clocks don't need to persist across node reboots ⏰

Every Babel speaker maintains a Neighbour Table, described in Section 3.2.4 of [RFC8966]. This extension adds the following data to every entry in the Neighbour Table:

the Origin Timestamp, a 32-bit timestamp (modulo 2^32) according to the neighbour's clock;
the Receive Timestamp, a 32-bit timestamp (modulo 2^32) according to the local clock.

Both values start out undefined 🫶

3.2. Protocol Operation ✨

okay so the RTT to a neighbour gets estimated with an algorithm from Mills [RFC891] 🦋. It was originally built for the HELLO routing protocol, and then NTP [RFC5905] picked it up too 💅.

A Babel speaker keeps sending Hello messages to its neighbours (Section 3.4.1 of [RFC8966]) 💖. On top of that, it now and then sends a set of IHU ("I Heard You") messages, with at most one per neighbour (Section 3.4.2 of [RFC8966]) 🫶.

   A          B
     |      |
  t1 +      |
     |\     |
     | \    |
     |  \   |  Hello(t1)
     |   \  |
     |    \ |
     |     \|
     |      + t1'
     |      |
     |      |               RTT = (t2 - t1) - (t2' - t1')
     |      |
     |      + t2'
     |     /|
     |    / |
     |   /  |
     |  /   |  Hello(t2')
     | /    |  IHU(t1, t1')
     |/     |
  t2 +      |
     |      |
     v      v

                      Figure 2: Mills' Algorithm

Okay, the big setup: in order to get RTTs at all, a node A MUST include, in every Hello that it sends, a timestamp t1 (according to A's local clock) 🕰️, as shown in Figure 2. When a node B receives A's timestamped Hello, it works out the time t1' at which that Hello arrived (according to B's local clock). Then it MUST record the value t1 in the Origin Timestamp field of the Neighbour Table entry for A, and the value t1' in the Receive Timestamp field of that same entry 📒.

When B sends an IHU to A, it checks whether both timestamps are defined in the Neighbour Table. If they are, then it MUST ensure that its IHU TLV is sent in a packet that also contains a timestamped Hello TLV (either a normally scheduled Hello or an unscheduled Hello, see Section 3.4.1 of [RFC8966]) 📦. It MUST include in the IHU both the Origin Timestamp and the Receive Timestamp stored in the Neighbour Table 💌.

When B's packet lands, A works out the time t2 (according to its local clock) at which it was received 🎯. Node A MUST then verify that the packet contains both a Hello TLV with timestamp t2' and an IHU TLV with two timestamps, t1 and t1'. If that checks out, A computes:

RTT = (t2 - t1) - (t2' - t1')

(where all computations are done modulo 2^32), and that gives a measurement of the RTT between A and B 📏. (A then stores the values t2' and t2 in its Neighbour Table, just like B did before 🔁.)

This algorithm has a bunch of desirable properties, and honestly they're iconic 👑:

The algorithm is symmetric: A and B use the same procedures for timestamping packets and computing RTT samples, and both nodes produce one RTT sample for each received (Hello, IHU) pair 🪞.
Since there is no requirement that t1' and t2' be equal, the protocol is asynchronous. The only change to Babel's message scheduling is the requirement that a packet containing an IHU also contain a Hello 🧚.
Since the algorithm only ever computes differences of timestamps according to a single clock, it does not require synchronised clocks ⏱️.
The algorithm requires very little additional state: a node only needs to store the two timestamps associated with the last hello received from each neighbour 🧠.
Since the algorithm only requires piggybacking one or two timestamps on each Hello and IHU TLV, it makes efficient use of network resources 🌱.

In principle, this algorithm is inaccurate in the presence of clock drift (i.e., when A's clock and B's clock are running at different frequencies) 😬. However, t2' - t1' is usually on the order of a few seconds, and significant clock drift is unlikely to happen on that time scale 🙈.

For RTT values to be consistent between implementations, timestamps need to be computed at roughly the same point in the network stack 🎀. Transmit timestamps SHOULD be computed just before the packet is passed to the network stack (i.e., before it is subjected to any queueing delays). Receive timestamps SHOULD be computed just after the packet is received from the network stack 🍓.

3.3. Wrap-Around and Node Restart 🌀

Timestamp values are a count of microseconds stored as a 32-bit unsigned integer. So they wrap around every 71 minutes or so 🕛. What's more, a node may occasionally reboot and restart its clock at an arbitrary origin 🔄. For these reasons, very old timestamps or nonsensical timestamps MUST NOT be used to yield RTT samples 🚫.

The following algorithm can be used to discard obsolete samples 🗑️. When a node receives a packet containing a Hello and an IHU, it compares the current local time t2 with the Origin Timestamp contained in the IHU. If the Origin Timestamp appears to be in the future, or if it is in the past by more than a time T (the value T = 3 minutes is recommended), then the timestamps are still recorded in the Neighbour Table, but they are not used for computation of an RTT sample 💫.

Similarly, the node compares the Hello's timestamp with the Receive Timestamp recorded in the Neighbour Table. If the Hello's timestamp appears to be older than the recorded timestamp, or if it appears to be more recent by an interval larger than the value T, then the timestamps are not used for computation of an RTT sample 🙅‍♀️.

3.4. Implementation Notes 🛠️

The accuracy of the computed RTT samples depends on two things. Transmit Timestamps should be computed as late as possible before a packet containing a Hello TLV is passed to the network stack, and Receive Timestamps should be computed as early as possible after a packet containing a (Hello, IHU) pair is received 🎯. We have found the following implementation strategy to be useful 💡.

When a Hello TLV is buffered for transmission, we insert a PadN sub-TLV (Section 4.7.2 of [RFC8966]) with a length of 4 octets within the TLV 🧩. When the packet is ready to be sent, we check whether it contains a 4-octet PadN sub-TLV. If that's the case, we overwrite the PadN sub-TLV with a Timestamp sub-TLV carrying the current time, and then send out the packet 🚀.

Conversely, when a packet is received, we immediately compute the current time and record it with the received packet. Then we process the packet as usual and use the recorded timestamp to compute an RTT sample 📸.

The protocol is designed to survive the clock being reset when a node reboots. On POSIX systems, this makes it possible to use the CLOCK_MONOTONIC clock for computing timestamps 🐧. If CLOCK_MONOTONIC is not available, CLOCK_REALTIME may be used, since the protocol is able to survive the clock being occasionally stepped 🌈.

4. RTT-Based Route Selection 🗺️

The protocol described above yields a series of RTT samples. These samples are fairly accurate, but they are not directly usable as an input to the route selection procedure, for at least three reasons 🙃:

In the presence of bursty traffic, routers experience transient congestion, which causes occasional spikes in the measured RTT. Thus, the RTT signal may be noisy and require smoothing before it can be used for route selection 📈.
Using the RTT signal for route selection gives rise to a negative feedback loop. When a route has a low RTT, it is deemed to be more desirable. This causes it to be used for more data traffic, which may lead to congestion, which in turn increases the RTT 🔁. Without some form of hysteresis, using RTT for route selection would lead to oscillations between parallel routes. Those oscillations would lead to packet reordering and negatively affect upper-layer protocols (such as TCP) 😱.
Even in the absence of congestion, the RTT tends to exhibit some variation. If the RTTs of two parallel routes oscillate around a common value, using the RTT as input to route selection will cause frequent routing oscillations. Again, that indicates the need for some form of hysteresis 🌊.

In this section, we describe an algorithm that integrates smoothing and hysteresis. It has been shown to behave well both in simulation and experimentally over the Internet [DELAY-BASED], and it is RECOMMENDED when RTT information is being used for route selection 👑. The algorithm is structured as follows ✨:

the RTT values are first smoothed in order to avoid instabilities due to outliers (Section 4.1);
the resulting smoothed samples are mapped to a cost using a bounded, non-linear mapping, which avoids instabilities at the lower and upper end of the RTT range (Section 4.2);
a hysteresis filter is applied in order to limit the amount of oscillation in the middle of the RTT range (Section 4.3).

4.1. Smoothing 🧼

The RTT samples provided by Mills' algorithm are fairly accurate, but noisy. Experiments indicate the occasional presence of individual samples that are much larger than the expected value 📊. Thus, some form of smoothing SHOULD be applied in order to avoid instabilities due to occasional outliers 🫧.

An implementation MAY use the exponential average algorithm. It's simple to implement and appears to yield good results in practice [DELAY-BASED] 💕. The algorithm is parameterised by a constant α, where 0 < α < 1, which controls the amount of smoothing being applied. For each neighbour, it maintains a smoothed value RTT, which is initially undefined 🫥. When the first sample RTT0 is measured, the smoothed value is set to the value of RTT0. At each new sample RTTn, the smoothed value is set to a weighted average of the previous smoothed value and the new sample 🧁:

    RTT := α RTT + (1 - α) RTTn

The smoothing constant α SHOULD be between 0.8 and 0.9. The value 0.836 is the RECOMMENDED default 🎀.

4.2. Cost Computation 💅

okay so the smoothed RTT from the last step still needs to get turned into a link cost 🧮 that the metric computation procedure can actually use (see Section 3.5.2 of [RFC8966]). the mapping has to be monotonic, meaning bigger RTTs mean bigger costs 📈. it also should flatten out past a certain point, because all the super-bad links are equally bad and we don't want congested links causing routing instability 🌪️. and it should stay constant near 0 too, so tiny wiggles in the RTT of already-fast links don't make routes flip-flop 🙃

     cost
       ^
       |
       |
       |                           C + max-rtt-penalty
       |                       +---------------------------
       |                      /.
       |                     / .
       |                    /  .
       |                   /   .
       |                  /    .
       |                 /     .
       |                /      .
       |               /       .
       |              /        .
       |             /         .
     C +------------+          .
       |            .          .
       |            .          .
       |            .          .
       |            .          .
     0 +---------------------------------------------------->
       0         rtt-min    rtt-max                          RTT

                  Figure 3: Mapping from RTT to Link Cost

Implementations SHOULD use the mapping shown in Figure 3 🎀, which is controlled by three knobs: rtt-min, rtt-max, and max-rtt-penalty. below rtt-min, the link cost is just the nominal cost C of a single hop 🍃. between rtt-min and rtt-max, the cost climbs in a straight line 📐. above rtt-max, the fixed max-rtt-penalty gets added on top of the nominal cost 🚧.

rtt-min should be a little bit bigger than the RTT of a local, uncongested link 🏠. rtt-max is the RTT past which a link should be avoided if possible, either because it's a long-distance link or because it's congested 🌍. lowering rtt-max makes things more stable 🧘‍♀️, but then the protocol can't tell apart the high-latency links anymore 😵‍💫. and max-rtt-penalty is basically how hard the protocol punishes long-distance links 🥊. the default values rtt-min = 10 ms, rtt-max = 120 ms, and max-rtt-penalty = 150 are RECOMMENDED 💖.

4.3. Hysteresis 🌀

even after you apply a bounded mapping from smoothed RTT to cost, the cost can still bounce around when a link's RTT sits between rtt-min and rtt-max 😩. so implementations SHOULD use a robust hysteresis algorithm, like the one in Appendix A.3 of [RFC8966] 🛡️.

5. Backwards and Forwards Compatibility 🤝

this extension stores the data it needs inside sub-TLVs of Babel's Hello and IHU TLVs 📦. as Appendix D of [RFC8966] explains, implementations that don't understand this extension will quietly ignore those sub-TLVs while they parse the rest of the TLVs 🙈. so you can build hybrid networks with extended and unextended routers together 🧩. the routing might be sub-optimal in those networks, but they won't end up with routing loops or other pathologies 🙌.

if a sub-TLV defined in this extension is longer than expected, the extra data just gets silently ignored 🫥. this is on purpose, so a future version of the protocol can add more data to the packet format, like high-precision or absolute timestamps ⏱️✨.

6. Packet Format 🎁

this extension defines the Timestamp sub-TLV, whose Type field has the value 3 🏷️. it can live inside a Hello sub-TLV, where it carries a single timestamp, or inside an IHU sub-TLV, where it carries two timestamps 👯.

timestamps are 32-bit unsigned integers (modulo 2^32), counted in microseconds from an arbitrary origin ⏲️. they wrap around every 4295 seconds, which is roughly 71 minutes (see also Section 3.3) 🌀.

6.1. Timestamp Sub-TLV in Hello TLVs 👋

when it's inside a Hello TLV, the Timestamp sub-TLV looks like this 👇:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Type = 3    |    Length     |      Transmit Timestamp       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          (continued)          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: set to 3 to say "this is a Timestamp sub-TLV" 🏷️.

Length: the length of the body in octets, not counting the Type and Length fields 📏.

Transmit Timestamp: the time the packet holding this sub-TLV was sent, according to the sender's clock 🕰️.

if the Length field is bigger than the expected 4 octets, the sub-TLV MUST be processed normally (the first 4 octets get read the way we just described) 🫶, and any extra data in it MUST be silently ignored 🤫. if the Length field is smaller than the expected 4 octets, then this sub-TLV MUST be ignored, and the rest of the enclosing TLV gets processed as usual 🚫.

6.2. Timestamp Sub-TLV in IHU TLVs 🔁

when it's inside an IHU TLV, the Timestamp sub-TLV looks like this 💅:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Type = 3    |    Length     |        Origin Timestamp       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          (continued)          |        Receive Timestamp      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          (continued)          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: set to 3 to say "this is a Timestamp sub-TLV" 🏷️.

Length: the length of the body in octets, not counting the Type and Length fields 📏.

Origin Timestamp: a copy of the Transmit Timestamp from the last Timestamp sub-TLV inside a Hello TLV that came from the node the enclosing IHU TLV is about 🪞.

Receive Timestamp: the time, according to the sender's clock, when the last timestamped Hello TLV arrived from the node the enclosing IHU TLV is about 📬.

if the Length field is bigger than the expected 8 octets, the sub-TLV MUST be processed normally (the first 8 octets get read the way we described) 💫, and any extra data in it MUST be silently ignored 🙊. if the Length field is smaller than the expected 8 octets, then this sub-TLV MUST be ignored, and the rest of the enclosing TLV gets processed as usual 🛑.

7. IANA Considerations 📋

IANA added the following entry to the "Babel Sub-TLV Types" registry 🗂️:

                 +======+===========+===========+
                 | Type | Name      | Reference |
                 +======+===========+===========+
                 | 3    | Timestamp | RFC 9616  |
                 +------+-----------+-----------+

                             Table 1

8. Security Considerations 🚨

okay, this part is serious bestie 😤. this extension adds timestamp data to two of the TLVs a Babel router sends 📡. by broadcasting the value of a reasonably accurate local clock, that extra data might make a node more susceptible to timing attacks ⚠️.

broadcasting an accurate time also raises privacy issues 🕵️‍♀️. the timestamps in this protocol have an arbitrary origin, so they don't leak a node's boot time or time zone 🙂. however, having access to accurate timestamps could let an attacker figure out the physical location of a node 📍😱. nodes that want to keep their location private can avoid this by not including Timestamp sub-TLVs in the TLVs they send 🫣, which makes their neighbours fall back to hop-count routing 🔙.

9. References 📚

9.1. Normative References 🧷

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, https://www.rfc-editor.org/info/rfc2119.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, https://www.rfc-editor.org/info/rfc8174.
[RFC8966] Chroboczek, J. and D. Schinazi, "The Babel Routing Protocol", RFC 8966, DOI 10.17487/RFC8966, January 2021, https://www.rfc-editor.org/info/rfc8966.

9.2. Informative References 🔍

[DELAY-BASED] Jonglez, B., Boutier, M., and J. Chroboczek, "A delay-based routing metric", DOI 10.48550/arXiv.1403.3488, March 2014, http://arxiv.org/abs/1403.3488.
[RFC891] Mills, D., "DCN Local-Network Protocols", STD 44, RFC 891, DOI 10.17487/RFC0891, December 1983, https://www.rfc-editor.org/info/rfc891.
[RFC5905] Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch, "Network Time Protocol Version 4: Protocol and Algorithms Specification", RFC 5905, DOI 10.17487/RFC5905, June 2010, https://www.rfc-editor.org/info/rfc5905.

Acknowledgements 🫶

the authors owe a big thank you to Jean-Paul Smets, who prompted the investigation that originally lead to this protocol 🌟. they're also grateful to Donald Eastlake, 3rd, Toke Høiland-Jørgensen, Maria Matejka, David Schinazi, Pascal Thubert, Steffen Vogel, and Ondřej Zajiček 💜.

Authors' Addresses 📮

Baptiste Jonglez
ENS Lyon
France
Email: baptiste.jonglez@ens-lyon.org

Juliusz Chroboczek
IRIF, Université Paris Cité
Case 7014
75205 Paris Cedex 13
France
Email: jch@irif.fr

📦 where this page comes from

ietf: rfc9616 2024-09
💖 girlified by claude-haiku-5-5 on 2026-10-19: a language model's rewrite of the original, under its terms