RFC 8966

The Babel Routing Protocol

📅 published January 2021, from ietf

The Babel Routing Protocol 🦋 (Part 1 of 13)

okay bestie, this is RFC 8966 and it's giving main character energy 💅. It's a Standards Track doc from January 2021 (ISSN 2070-1721) by J. Chroboczek at IRIF, University of Paris-Diderot, and D. Schinazi at Google LLC. It obsoletes RFC 6126 and RFC 7557 🌸.

Abstract ✨

Babel is a loop-avoiding, distance-vector routing protocol that's robust and efficient in ordinary wired networks and in wireless mesh networks 🕸️. This document describes the Babel routing protocol and obsoletes RFC 6126 and RFC 7557.

Status of This Memo 📜

This is an Internet Standards Track document, so it's an official standard 👑.

It's a product of the Internet Engineering Task Force (IETF) and it represents the consensus of the IETF community. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). More info on Internet Standards is in Section 2 of RFC 7841.

For the current status, any errata, and how to give feedback, check https://www.rfc-editor.org/info/rfc8966 🔗.

Copyright Notice 🌈

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. Code Components pulled from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License ⚖️.

Table of Contents 🗂️

1.  Introduction
  1.1.  Features
  1.2.  Limitations
  1.3.  Specification of Requirements
2.  Conceptual Description of the Protocol
  2.1.  Costs, Metrics, and Neighbourship
  2.2.  The Bellman-Ford Algorithm
  2.3.  Transient Loops in Bellman-Ford
  2.4.  Feasibility Conditions
  2.5.  Solving Starvation: Sequencing Routes
  2.6.  Requests
  2.7.  Multiple Routers
  2.8.  Overlapping Prefixes
3.  Protocol Operation
  3.1.  Message Transmission and Reception
  3.2.  Data Structures
  3.3.  Acknowledgments and Acknowledgment Requests
  3.4.  Neighbour Acquisition
  3.5.  Routing Table Maintenance
  3.6.  Route Selection
  3.7.  Sending Updates
  3.8.  Explicit Requests
4.  Protocol Encoding
  4.1.  Data Types
  4.2.  Packet Format
  4.3.  TLV Format
  4.4.  Sub-TLV Format
  4.5.  Parser State and Encoding of Updates
  4.6.  Details of Specific TLVs
  4.7.  Details of specific sub-TLVs
5.  IANA Considerations
6.  Security Considerations
7.  References
  7.1.  Normative References
  7.2.  Informative References
Appendix A.  Cost and Metric Computation
  A.1.  Maintaining Hello History
  A.2.  Cost Computation
  A.3.  Route Selection and Hysteresis
Appendix B.  Protocol Parameters
Appendix C.  Route Filtering
Appendix D.  Considerations for Protocol Extensions
Appendix E.  Stub Implementations
Appendix F.  Compatibility with Previous Versions
Acknowledgments
Authors' Addresses

1. Introduction 🎀

Babel is a loop-avoiding distance-vector routing protocol, and it's built to be robust and efficient in networks that use prefix-based routing and in networks that use flat routing ("mesh networks") 🕸️. It works in relatively stable wired networks and in super dynamic wireless ones too. This document describes the Babel routing protocol and obsoletes [RFC6126] and [RFC7557].

1.1. Features 💖

The big reason Babel handles unstable networks so well is that, unlike naive distance-vector protocols [RIP], it really limits how often and how long routing pathologies like routing loops and black-holes show up during reconvergence 🙌. Even after a mobility event is detected, a Babel network usually stays loop-free. Then it quickly reconverges to a setup that keeps the network loop-free and connected, even though it might not be optimal. In lots of cases this doesn't need any packet exchanges at all ✨. After that, Babel slowly converges, over minutes, to an optimal configuration. The trick is sequenced routes, a technique first used by Destination-Sequenced Distance-Vector routing [DSDV] 🧠.

Here's what Babel guarantees, more precisely:

when every prefix is originated by at most one router, Babel never suffers from routing loops 🙅‍♀️;
when a single prefix is originated by multiple routers, Babel may occasionally create a transient routing loop for that prefix. The loop disappears in time proportional to its diameter, and the routers involved never again (up to an arbitrary garbage-collection (GC) time) take part in a routing loop for the same prefix 🔁;
assuming bounded packet loss rates, any routing black-holes that may show up after a mobility event get fixed in a time at most proportional to the network's diameter 🩹.

Babel also has provisions for link quality estimation and for pretty arbitrary metrics. When it's configured suitably, Babel can do shortest-path routing, or it can use a metric based on something like measured packet loss 📶.

Babel nodes will still set up an association even when they're configured with different parameters 🤝. For example, a mobile node that's low on battery might pick larger time constants (hello and update intervals, etc.) than a node plugged into wall power 🔋. On the flip side, a node that notices lots of mobility might pick smaller ones. Being able to build these mixed-config networks is why Babel fits the unmanaged or wireless world so well 🌸.

Last but not least, Babel is a hybrid routing protocol. It can carry routes for multiple network-layer protocols (IPv4 and IPv6), no matter which protocol the Babel packets themselves travel over 🌍.

1.2. Limitations 🙈

Okay, real talk: Babel has two limitations that make it a bad fit for some environments 😬.

First, Babel relies on periodic routing table updates instead of a reliable transport. So in large, stable networks it creates more traffic than protocols that only send updates when the topology changes. For those networks, protocols like OSPF [OSPF], IS-IS [IS-IS], or the Enhanced Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be a better choice 💁‍♀️.

Second, unless the second algorithm described in Section 3.5.4 is implemented, Babel does impose a hold time when a prefix is retracted. The hold time doesn't apply to the exact prefix being retracted, so it doesn't stop fast reconvergence if that prefix comes back. But it does apply to any shorter prefix that covers it. So implementations that skip the optional algorithm described in Section 3.5.4 might not be great in networks that do automatic prefix aggregation 🚫.

1.3. 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 read as described in BCP 14 [RFC2119] [RFC8174], but only when they show up in all capitals, exactly like that 🫶.

2. Conceptual Description of the Protocol 🧩

Okay so Babel is a loop-avoiding distance-vector protocol. It's based on the Bellman-Ford algorithm, just like the legendary RIP [RIP] 👑, but it adds a bunch of refinements that either stop loops from forming at all, or make sure a loop goes away quickly and doesn't come back 🔥.

Bellman-Ford actually runs in parallel for every source of routing information (basically, every destination of data traffic). In the rest of this part we'll fix one source S. Just remember the same algorithm runs for all sources ✨.

2.1. Costs, Metrics, and Neighbourship 💸

For every pair of neighbouring nodes A and B, Babel computes an abstract value called the cost of the link from A to B, written C(A, B). For any route between two nodes (not necessarily neighbours), the metric of that route is the sum of the costs of all the links along it. The routing algorithm's goal is to compute, for every source S, the tree of routes with the lowest metric to S 🌳.

Costs and metrics don't have to be integers. In general they can be values from any algebra that meets two pretty general conditions (Section 3.5.2) 🤓.

Every Babel node periodically sends Hello messages to all of its neighbours. It also periodically sends an IHU ("I Heard You") message to every neighbour it has heard a Hello from recently 👋. From the info in the Hello and IHU messages it gets from neighbour B, node A works out the cost C(A, B) of the link from A to B 💅.

2.2. The Bellman-Ford Algorithm 🧮

Every node A keeps two pieces of data: its estimated distance to S, written D(A), and its next-hop router to S, written NH(A). At the start, D(S) = 0, D(A) is infinite, and NH(A) is undefined 🌱.

Periodically, every node B sends a route update to all of its neighbours. That update is a message containing D(B) 📣. When a neighbour A of B gets the route update, it checks whether B is its selected next hop. If it is, then NH(A) is set to B and D(A) is set to C(A, B) + D(B). If it isn't, A compares C(A, B) + D(B) to its current D(A). If that value is smaller, meaning the update advertises a route that beats the one currently selected, then NH(A) is set to B and D(A) is set to C(A, B) + D(B) 🏆.

There are a bunch of refinements to this that Babel uses. The big one: convergence can get faster by sending unscheduled "triggered updates" whenever a major topology change is detected, on top of the regular scheduled updates ⚡. Also, a node can keep several alternate routes that other neighbours (not its selected one) are advertising, so it can switch to one right away if the selected route fails 🛟.

2.3. Transient Loops in Bellman-Ford 🌀

Here's the tea ☕: a naive use of Bellman-Ford in distributed routing can cause transient loops after a topology change. Check out this topology:

         B
      1 /|
   1   / |
S --- A  |1
       \ |
      1 \|
         C

After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.

Now say the link between S and A fails:

         B
      1 /|
       / |
S     A  |1
       \ |
      1 \|
         C

When A detects the failure, it switches its next hop to B (which is still advertising a route to S with metric 2). It advertises a metric equal to 3, and then advertises a new route with metric 3. This keeps going, with nodes swapping selected neighbours and raising their metric again and again, until the advertised metric hits "infinity" 💀. That's a value bigger than every metric the routing protocol can carry.

2.4. Feasibility Conditions ✨

okay so Bellman-Ford is honestly such a robust algorithm bestie 💅 its convergence properties still hold even when routers delay learning routes or just straight up throw away some updates 🫶 that's the whole vibe! So Babel routers toss out received route announcements unless they can prove that accepting them cannot possibly create a routing loop 🔥

More formally, we define a condition over route announcements called the "feasibility condition" 🎀 If every router ignores route updates that don't satisfy it, then routing loops are guaranteed to be absent ✨ It's giving Bellman-Ford becomes a whole family of routing algorithms, each one parameterised by its own feasibility condition 🌈

There are SO many possible feasibility conditions 😭 For instance, BGP can be modelled as a distance-vector protocol with a (rather drastic) feasibility condition: a routing update is only accepted when the receiving node's AS number is not included in the update's AS_PATH attribute 💀 (ngl, BGP's feasibility condition does not stop transient "micro-loops" during reconvergence 🙈)

Another simple one is used in the Destination-Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the Ad hoc On-Demand Distance Vector (AODV) protocol [RFC3561] 🦋 The big observation here is that a routing loop can only show up after a router has switched to a route with a larger metric than the route it had previously selected 👑 So a route counts as feasible when its metric at the local node would be no larger than the metric of the currently selected route. Put simply, an announcement carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A) 💖 If every router obeys this, the metric at every router is nonincreasing, and this invariant always holds: if A has selected B as its next hop, then D(B) < D(A), which means the forwarding graph is loop-free 🧚

Babel uses a slightly more refined feasibility condition, borrowed from EIGRP [DUAL] 🌸 Given a router A, define the feasibility distance of A, written FD(A), as the smallest metric that A has ever advertised for S to any of its neighbours ⭐ An update sent by a neighbour B of A is feasible when the metric D(B) advertised by B is strictly smaller than A's feasibility distance, i.e., when D(B) < FD(A) 🫶

It is easy to see that this latter condition is no more restrictive than DSDV-feasibility 💅 Suppose node A obeys DSDV-feasibility; then D(A) is nonincreasing, so at all times D(A) <= FD(A) ✨ Now suppose A receives a DSDV-feasible update that advertises a metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= D(A), so D(B) < D(A), and since D(A) <= FD(A), we get D(B) < FD(A) 🎀

To see that it is strictly less restrictive, check out this diagram 🦋 A has selected the route through B, and D(A) = FD(A) = 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible for A, even though its metric C(A, C) + D(C) = 5 is larger than that of the currently selected route 😭

   B
1 / \ 1
 /   \
S     A
 \   /
1 \ / 4
   C

To show that this feasibility condition still guarantees loop-freedom, recall that when A accepts an update from B, the metric D(B) announced by B is no smaller than FD(B) 🌈 Since it is smaller than FD(A), at that point FD(B) < FD(A) 💜 This property is preserved when A sends updates and also when it picks a different next hop, so it stays true at all times, which ensures the forwarding graph has no loops 👑

2.5. Solving Starvation: Sequencing Routes ✨

Okay so the feasibility conditions above can cause starvation 😭 That happens when a router runs out of feasible routes. Check out this diagram where both A and B have selected the direct route to S 🦋

   A
1 /|        D(A) = 1
 / |       FD(A) = 1
S  |1
 \ |        D(B) = 2
2 \|       FD(B) = 2
   B

Now suppose the link between A and S breaks 💀

   A
   |
   |       FD(A) = 1
S  |1
 \ |        D(B) = 2
2 \|       FD(B) = 2
   B

The only route A has left to S, the one through B, is not feasible, so A suffers from spurious starvation 🙈 At that point the whole subtree suffering from starvation has to be reset, which is basically what EIGRP does when it does a global synchronisation of all the routers in the starving subtree (the "active" phase of EIGRP) 😬

Babel handles starvation in a way that's way less drastic 🫶 It uses sequenced routes, a technique introduced by DSDV and adopted by AODV ✨ Every route carries a sequence number on top of its metric. This is a nondecreasing integer that gets propagated unchanged through the network and is only ever incremented by the source 🌸 A pair (s, m), where s is a sequence number and m is a metric, is called a distance 💖

A received update is feasible when either it's more recent than the feasibility distance maintained by the receiving node, or it's equally recent and the metric is strictly smaller 👑 More formally, if FD(A) = (s, m), then an update carrying the distance (s', m') is feasible when either s' > s, or s = s' and m' < m 🎀

Assuming the sequence number of S is 137, the diagram above becomes:

   A
   |
   |       FD(A) = (137, 1)
S  |1
 \ |        D(B) = (137, 2)
2 \|       FD(B) = (137, 2)
   B

After S increases its sequence number, and the new one gets propagated to B, we have:

   A
   |
   |       FD(A) = (137, 1)
S  |1
 \ |        D(B) = (138, 2)
2 \|       FD(B) = (138, 2)
   B

and at that point the route through B becomes feasible again 🦋

Note that sequence numbers are used for determining feasibility, but they are not used in route selection 💅 A node ignores the sequence number when selecting the best route to a given destination (Section 3.6) 🧚 Doing otherwise would cause route oscillation while a sequence number propagates through the network, and might even cause persistent black-holes with some exotic metrics 😭

2.6. Requests 🎀

In DSDV, the sequence number of a source is increased periodically 🌸 A route becomes feasible again after the source increases its sequence number and the new one is propagated through the network, which may, in general, take a significant amount of time ⭐

Babel takes a different approach 👑 When a node detects that it's suffering from a potentially spurious starvation, it sends an explicit request to the source for a new sequence number ✨ This request gets forwarded hop by hop to the source, with no regard to the feasibility condition 💖 Upon receiving the request, the source increases its sequence number and broadcasts an update, which is forwarded to the requesting node 🫶

Note that after a change in network topology, not all such requests will necessarily reach the source, since some will be sent over links that are now broken 🙈 However, if the network is still connected, then at least one of the nodes suffering from spurious starvation has an (unfeasible) route to the source 🔥 So, in the absence of packet loss, at least one such request will reach the source 🦋 (Resending requests a small number of times compensates for packet loss 💅)

Since requests are forwarded with no regard to the feasibility condition, they can, in general, get caught in a forwarding loop 😭 This is avoided by having nodes perform duplicate detection for the requests they forward 🧚

2.7. Multiple Routers 🌈

The discussion above assumes that each prefix is originated by a single router 🫶 In real networks, though, it's often necessary to have a single prefix originated by multiple routers 👑 For example, the default route will be originated by all of the edge routers of a routing domain 💅

Since synchronising sequence numbers between distinct routers is problematic, Babel treats routes for the same prefix as distinct entities when they're originated by different routers ✨ Every route announcement carries the router-id of its originating router, and feasibility distances are not maintained per prefix but per source, where a source is a pair of a router-id and a prefix 🌸 In effect, Babel guarantees loop-freedom for the forwarding graph to every source 💖 Since the union of multiple acyclic graphs is not in general acyclic, Babel does not in general guarantee loop-freedom when a prefix is originated by multiple routers 😬 Any loops will be broken in a time at most proportional to the diameter of the loop, as soon as an update has "gone around" the routing loop 🔥

Consider for example the following topology, where A has selected the default route through S, and B has selected the one through S' 🦋

           1     1     1
::/0 -- S --- A --- B --- S' -- ::/0

Suppose both default routes fail at the same time. Then nothing prevents A from switching to B, and B simultaneously switching to A 💀 However, as soon as A has successfully advertised the new route to B, the route through A becomes unfeasible for B 🙈 Conversely, as soon as B has advertised the route through A, the route through B becomes unfeasible for A 🫶

In effect, the routing loop disappears at the latest when routing information has gone around the loop ✨ Since this process can be delayed by lost packets, Babel makes certain efforts to ensure that updates are sent reliably after a router-id change (Section 3.7.2) 💅

Additionally, after the routers have advertised the two routes, both sources will be in their source tables 👑 That prevents them from ever again participating in a routing loop involving routes from S and S' (up to the source GC time, which, available memory permitting, can be set to arbitrarily large values) 🌈

2.8. Overlapping Prefixes 💖

Up until now we've assumed that all prefixes are disjoint, as is the case in flat ("mesh") routing 🧚 In practice, though, prefixes can overlap: for example, the default route overlaps with all of the routes present in the network 😭

After a route fails, it's not correct in general to switch to a route that subsumes the failed route 🙈 Consider this configuration:

           1     1
::/0 -- A --- B --- C

Suppose node C fails 💀 If B forwards packets destined to C by following the default route, a routing loop will form and persist until A learns of B's retraction of the direct route to C 😬 B avoids this pitfall by installing an "unreachable" route after a route is retracted 🔥 This route is maintained until it can be guaranteed that the former route has been retracted by all of B's neighbours (Section 3.5.4) 🦋

3. Protocol Operation ✨

Every Babel speaker is assigned a router-id 🫶 It's an arbitrary string of 8 octets that is assumed to be unique across the routing domain 💅 For example, router-ids could be assigned randomly, or they could be derived from a link-layer address 🌸 (The protocol encoding is slightly more compact when router-ids are assigned in the same manner as the IPv6 layer assigns host IDs; see the definition of the "R" flag in Section 4.6.9 👑)

3.1. Message Transmission and Reception 💌

okay so Babel packets ride inside the body of a UDP datagram (see Section 4) 📦 Each packet is made of zero or more TLVs, and most TLVs can have sub-TLVs tucked inside them 🧚

Babel's control traffic can be carried over IPv6 or IPv4, and prefixes from either address family can be announced over either protocol 🦋 That gives us at least two main deployment vibes: use IPv6 for ALL control traffic, or run two separate protocol instances, one per address family. Using IPv6 exclusively for all control traffic is RECOMMENDED 💅 because running both protocols at once doubles the traffic spent on neighbour discovery and link quality estimation. Not the move 😭

The source address of a Babel packet is always a unicast address, and for IPv6 it's link-local 🌸 Babel packets can go to a well-known (link-local) multicast address or to a (link-local) unicast address. In normal operation, a Babel speaker sends both multicast and unicast packets to its neighbours 🫶

Except for acknowledgments, every Babel TLV can be sent to either a unicast or a multicast address, and what it means doesn't change based on which one it's sent to ✨ So a Babel speaker doesn't need to figure out the destination address of a packet it receives before it can interpret it. Iconic efficiency 👑

A moderate amount of jitter may be applied to packets sent by a Babel speaker. Outgoing TLVs get buffered and SHOULD be sent with a random delay 🎀 There are two reasons for this: it stops multiple Babel speakers across a network from syncing up [JITTER] 🌈, and it lets several TLVs get bundled into a single packet 📦

How long a TLV can be held depends on the TLV itself 🧚 When the spec says a TLV is urgent (like in Section 3.7.2 and Section 3.8.1), then the TLV MUST be sent within a short time called the urgent timeout (see Appendix B for recommended values) 🚨 When a TLV is governed by a timeout set in an earlier TLV, like Acknowledgments (Section 4.6.4), Updates (Section 3.7), and IHUs (Section 3.4.2), then the TLV MUST be sent early enough to meet the explicit deadline (with a small margin for propagation delays) ⏰ In every other case, the TLV SHOULD be sent out within one-half of the Multicast Hello interval 💜

To avoid packet drops (at the sender or at the receiver), a delay SHOULD be introduced between successive packets sent out on the same interface, as long as it still fits the rules in the paragraph above 🍓 Heads up though: that kind of packet pacing might get in the way of some link layers (for example IEEE 802.11 [IEEE802.11]) doing packet aggregation 🙈

3.2. Data Structures 🗂️

In this section we go over the data structures every Babel speaker keeps 💖 This is a conceptual description, so a Babel speaker can use different data structures as long as the protocol that comes out is the same one this document describes ✨ For example, instead of keeping one table with both selected and unselected (fallback) routes, as described in Section 3.2.6, a real implementation would probably use two tables: one for selected routes and one for fallback routes 🌸

3.2.1. Sequence Number Arithmetic 🔢

Sequence numbers (seqnos) show up in a bunch of Babel data structures, and they're treated as integers modulo 2^(16) 🦋 For this document, arithmetic on sequence numbers works like this.

Given a seqno s and a non-negative integer n, the sum of s and n is defined by the following:

   s + n (modulo 2^(16)) = (s + n) MOD 2^(16)

or, equivalently,

   s + n (modulo 2^(16)) = (s + n) AND 65535

where MOD is the modulo operation yielding a non-negative integer, and AND is the bitwise conjunction operation.

Given two sequence numbers s and s', the relation s is less than s' (s < s') is defined by the following:

   s < s' (modulo 2^(16)) when 0 < ((s' - s) MOD 2^(16)) < 32768

or, equivalently,

   s < s' (modulo 2^(16)) when s /= s' and ((s' - s) AND 32768) = 0.

3.2.2. Node Sequence Number 🌟

A node's sequence number is a 16-bit integer that gets included in route updates for routes this node originates 💖

A node increments its sequence number (modulo 2^(16)) whenever it gets a request for a new sequence number (Section 3.8.1.2). A node SHOULD NOT increment its sequence number (seqno) spontaneously 🙅‍♀️ because bumping seqnos makes it less likely that other nodes will have feasible alternate routes when their selected routes fail 💀

3.2.3. The Interface Table 🔌

The interface table lists the interfaces this node speaks the Babel protocol on 📋 Every entry has the interface's outgoing Multicast Hello seqno: a 16-bit integer that goes out with each Multicast Hello TLV on this interface and gets incremented (modulo 2^(16)) every time a Multicast Hello is sent 🎀 (Heads up, this interface seqno has nothing to do with the node's seqno 🙃)

Each interface table entry has two timers 🧚 The periodic multicast hello timer controls when scheduled Multicast Hello and IHU packets get sent (Section 3.4). The periodic Update timer controls when periodic route updates get sent (Section 3.7.1). See Appendix B for suggested time constants ⏱️

3.2.4. The Neighbour Table 🤝

The neighbour table lists all the neighbouring interfaces a Babel packet has been recently received from 🫶 It's indexed by (interface, address) pairs, and every neighbour table entry holds the following data:

the local node's interface over which this neighbour is reachable;
the address of the neighbouring interface;
a history of recently received Multicast Hello packets from this neighbour; this can, for example, be a sequence of n bits, for some small value n, indicating which of the n hellos most recently sent by this neighbour have been received by the local node;
a history of recently received Unicast Hello packets from this neighbour;
the "transmission cost" value from the last IHU packet received from this neighbour, or FFFF hexadecimal (infinity) if the IHU hold timer for this neighbour has expired;
the expected incoming Multicast Hello sequence number for this neighbour, an integer modulo 2^(16).
the expected incoming Unicast Hello sequence number for this neighbour, an integer modulo 2^(16).
the outgoing Unicast Hello sequence number for this neighbour, an integer modulo 2^(16) that is sent with each Unicast Hello TLV to this neighbour and is incremented (modulo 2^(16)) whenever a Unicast Hello is sent. (Note that the outgoing Unicast Hello seqno for a neighbour is distinct from the interface's outgoing Multicast Hello seqno.)

Each neighbour entry has three timers 🕰️ the multicast hello timer, which is set to the interval value carried by scheduled Multicast Hello TLVs sent by this neighbour; the unicast hello timer, which is set to the interval value carried by scheduled Unicast Hello TLVs; and the IHU timer, which is set to a small multiple of the interval carried in IHU TLVs (see "IHU Hold time" in Appendix B for suggested values).

Note that the neighbour table is indexed by IP addresses, not by router-ids 🧐 Neighbourship is a relationship between interfaces, not between nodes. So two nodes with multiple interfaces can be in multiple neighbourship relationships at once, which can totally happen with wireless nodes that have multiple radios 📡✨

3.2.5. The Source Table 🗃️

The source table records feasibility distances 💜 It's indexed by (prefix, plen, router-id) triples, and every source table entry holds the following data:

the prefix (prefix, plen), where plen is the prefix length in bits, that this entry applies to;
the router-id of a router originating this prefix;
a pair (seqno, metric), this source's feasibility distance.

There's one timer per source table entry: the source garbage-collection timer ⏳ It starts at a time on the order of minutes and gets reset as specified in Section 3.7.3.

3.2.6. The Route Table 🛣️

The route table holds the routes this node knows about 🗺️ It's indexed by (prefix, plen, neighbour) triples, and every route table entry holds the following data:

the source (prefix, plen, router-id) for which this route is advertised;
the neighbour (an entry in the neighbour table) that advertised this route;
the metric with which this route was advertised by the neighbour, or FFFF hexadecimal (infinity) for a recently retracted route;
the sequence number with which this route was advertised;
the next-hop address of this route;
a boolean flag indicating whether this route is selected, i.e., whether it is currently being used for forwarding and is being advertised.

Each route table entry has one timer, the route expiry timer 🕒 It gets initialised and reset as specified in Section 3.5.3.

Quick heads up: each route has two distinct (seqno, metric) pairs 👀 One is the route's distance, which lives in the route table. The other is the feasibility distance, which lives in the source table and is shared by all routes with the same source 💅

3.2.7. The Table of Pending Seqno Requests 📮

This table holds the seqno requests the local node has sent (either because it originated them or because it forwarded them) that haven't gotten a reply yet 💌 It's indexed by (prefix, plen, router-id) triples, and every entry holds the following data:

the prefix, plen, router-id, and seqno being requested;
the neighbour, if any, on behalf of which we are forwarding this request;
a small integer indicating the number of times that this request will be resent if it remains unsatisfied.

Each pending seqno request has one timer, and it handles both resending the request and expiring it ⏰🦋

3.3. Acknowledgments and Acknowledgment Requests ✨

okay so a Babel speaker can ask a neighbour to send back an explicit acknowledgment for a packet, within a given time 🎀 Asking is totally optional, but every Babel speaker MUST be able to reply when someone asks. 🫶

An acknowledgment MUST be sent to a unicast destination. Acknowledgment requests are a different story: they can go to unicast or multicast destinations, and when they go multicast, they're asking every receiving node to reply 📣

When to request acknowledgments is up to local policy 🤷‍♀️ The simplest strategy is to never request them at all, and just rely on periodic updates to eventually spread any reachable routes around the whole routing domain. But if you want faster convergence and less control traffic, acknowledgment requests MAY be used to send urgent updates (Section 3.7.2) and retractions (Section 3.5.4) reliably, especially when there are only a few neighbours on an interface 💖

Babel is built to handle packet loss on unreliable media like a queen 👑 so sending every packet with an acknowledgment request is not necessary and NOT RECOMMENDED. The acknowledgments add extra traffic and can trigger additional Address Resolution Protocol (ARP) or Neighbour Discovery (ND) exchanges, which is just extra drama nobody needs 🙄

3.4. Neighbour Acquisition 🦋

Neighbour acquisition is how a Babel node finds out who it's neighbouring over each of its interfaces and double-checks that the connection goes both ways. On unreliable media, it also collects some stats that are useful for working out link quality 📊

Before a Babel node can swap routing info with a neighbour, it MUST create an entry for that neighbour in the neighbour table 🗂️ When to do this is implementation-specific. Two popular vibes: create the entry when any Babel packet shows up, or create it when a Hello TLV gets parsed. To save system resources, an implementation SHOULD discard an entry that's been unused for long enough. Suitable strategies include dropping the neighbour after a timeout, or dropping it once the associated Hello histories are empty (see Appendix A.2) 🧹

3.4.1. Reverse Reachability Detection 💅

Every Babel node sends Hello TLVs to its neighbours at regular or irregular intervals, basically saying "hey, I'm still alive!" 👋 Each Hello TLV carries an increasing sequence number (modulo 2^(16)) and an upper bound on how long until the next Hello of the same type (see below).

Here's the tea ☕ If the interval is set to 0, that Hello doesn't make a new promise. Instead, the deadline from the previous Hello of the same type still applies to the next one. Like, if the most recent scheduled Hello of the right kind arrived at time t0 and carried interval i, then the old promise of sending another Hello before time t0 + i still holds 🕰️ We call a Hello "scheduled" if it has a nonzero interval, and "unscheduled" otherwise.

There are two kinds of Hellos 🧚 Multicast Hellos use a per-interface counter (the Multicast Hello seqno), and Unicast Hellos use a per-neighbour counter (the Unicast Hello seqno). A Multicast Hello with a given seqno MUST be sent to all neighbours on a given interface, either by hitting a multicast address or by sending one unicast copy per neighbour. (Yes, so "Multicast Hello" is a slight misnomer, we know 😭) A Unicast Hello carrying a given seqno should normally go to just one neighbour over unicast, since different neighbours' sequence numbers aren't generally synchronised 🙃

Multicast Hellos sent over multicast are useful for neighbour discovery, so a node SHOULD send periodic (scheduled) Multicast Hellos unless neighbour discovery is handled by means outside of Babel 🔍 A node MAY send Unicast Hellos or unscheduled Hellos of either kind for any reason. For example, it might want to cut down on multicast traffic, or improve reliability on link technologies that don't do link-layer multicast very well 🌈

Timing-wise, a node MAY send a scheduled Hello ahead of time, and MAY change its scheduled Hello interval. The Hello interval MAY be decreased at any time. It MAY be increased immediately before sending a Hello TLV, but SHOULD NOT be increased at other times. (Equivalently, a node SHOULD send a scheduled Hello immediately after increasing its Hello interval.) ⏰

How to handle received Hello TLVs and what statistics to keep are local implementation matters. Typically, a node keeps some kind of history of recently received Hellos. An example of a suitable algorithm is in Appendix A.1 📚

After receiving a Hello, or deciding it has missed one, the node recomputes the association's cost (Section 3.4.3) and runs the route selection procedure (Section 3.6) 🔁

3.4.2. Bidirectional Reachability Detection 🌸

To establish bidirectional reachability, every node sends periodic IHU ("I Heard You") TLVs to each of its neighbours 🫡 Since IHUs carry an explicit interval value, they MAY be sent less often than Hellos to reduce routing traffic in dense networks. In particular, they SHOULD be sent less often than Hellos over links with little packet loss. IHUs are conceptually unicast, but they MAY be sent to a multicast address to skip an ARP or Neighbour Discovery exchange and to bundle multiple IHUs into a single packet 📦

On top of the periodic IHUs, a node MAY, at any time, send an unscheduled IHU packet. It MAY also, at any time, decrease its IHU interval. It MAY increase its IHU interval immediately before sending an IHU, but SHOULD NOT increase it at any other time. (Equivalently, a node SHOULD send an extra IHU immediately after increasing its Hello interval.) 💫

Every IHU TLV has two chunks of data: the link's rxcost (reception cost) from the sender's point of view, which the neighbour uses to compute link costs (Section 3.4.3), and the interval between periodic IHU packets. When a node receives an IHU, it sets the txcost (transmission cost) in its neighbour table to the value in the IHU, and resets the IHU timer for that neighbour to a small multiple of the interval value received in the IHU (see "IHU Hold time" in Appendix B for suggested values). When a neighbour's IHU timer expires, that neighbour's txcost is set to infinity 💀

If the IHU timer runs out, the txcost goes to infinity. That's the link being ghosted, no cap.

After updating a neighbour's txcost, the receiving node recomputes the neighbour's cost (Section 3.4.3) and runs the route selection procedure (Section 3.6) 🔥

3.4.3. Cost Computation 🧮

A neighbourship association's link cost is computed from the values in the neighbour table: the statistics kept about reception of Hellos, and the txcost computed from received IHU packets 💅

For every neighbour, a Babel node computes a value called that neighbour's rxcost. This is usually derived from the Hello history, which can be mixed with other data, like statistics the link layer keeps. The rxcost gets sent to the neighbour in each IHU 📨

Nodes don't necessarily send periodic Unicast Hellos, but they usually do send periodic Multicast Hellos (Section 3.4.1). So a node SHOULD use an algorithm that yields a finite rxcost when only Multicast Hellos are received, unless interoperability with nodes that only send Multicast Hellos isn't required 🫶

How the txcost and rxcost get combined into a link's cost is a matter of local policy 🎛️ As far as Babel's correctness goes, though, only the following conditions MUST be satisfied:

the cost is strictly positive;
if no Hello TLVs of either kind were received recently, then the cost is infinite;
if the txcost is infinite, then the cost is infinite.

See Appendix A.2 for RECOMMENDED strategies for computing a link's cost 🌟

3.5. Routing Table Maintenance 🌈

Conceptually, a Babel update is a quintuple (prefix, plen, router-id, seqno, metric) 🎀 Here, (prefix, plen) is the prefix the route is being advertised for, router-id is the router-id of the router that originated the update, seqno is a nondecreasing integer (modulo 2^(16)) that carries the originating router's seqno, and metric is the announced metric.

Before an update gets accepted, it's checked against the feasibility condition (Section 3.5.1). This is the bit that makes sure the route doesn't create a routing loop 🔄 If the feasibility condition isn't satisfied, the update is either ignored or prevents the route from being selected, as described in Section 3.5.3. And if the feasibility condition is satisfied, the update cannot possibly cause a routing loop ✨

3.5.1. The Feasibility Condition 🔥

The feasibility condition gets applied to all received updates. It compares the metric in the received update with the metrics of the updates the receiving node has previously sent. Updates that fail it, meaning they have metrics large enough to cause a routing loop, are either ignored or prevent the resulting route from being selected 🚫

A feasibility distance is a pair (seqno, metric), where seqno is an integer modulo 2^(16) and metric is a positive integer 💜 Feasibility distances get compared lexicographically, but with the first component inverted. So we say a distance (seqno, metric) is strictly better than a distance (seqno', metric'), written like this:

(seqno, metric) < (seqno', metric')

when

seqno > seqno' or (seqno = seqno' and metric < metric')

and sequence numbers are compared modulo 2^(16).

Given a source (prefix, plen, router-id), a node's feasibility distance for that source is the minimum (using the ordering above) of the distances of all the finite updates this particular node has ever sent for the prefix (prefix, plen) and the given router-id. Feasibility distances live in the source table, and the exact procedure is in Section 3.7.3 🗃️

A received update is feasible when either it's a retraction (its metric is FFFF hexadecimal), or the advertised distance is strictly better, in the sense defined above, than the feasibility distance for the corresponding source. More precisely, a route advertisement carrying the quintuple (prefix, plen, router-id, seqno, metric) is feasible if one of these conditions holds:

metric is infinite; or
no entry exists in the source table indexed by (prefix, plen, router-id); or
an entry (prefix, plen, router-id, seqno', metric') exists in the source table, and either
- seqno' < seqno or
- seqno = seqno' and metric < metric'.

Note that the feasibility condition looks at the metric the neighbour advertised, not the route's own metric. So a wobble in a neighbour's cost can't make a selected route unfeasible 🥹 Also, retractions (updates with infinite metric) are always feasible, since they can't possibly cause a routing loop 💅

3.5.2. Metric Computation 🧮✨

okay so a route's metric is worked out from two things: the metric the neighbour advertised, and the neighbour's link cost. 💅 Just like cost computation, metric computation is a local policy matter, so you get to pick how you do it. As far as Babel is concerned, the function M(c, m) (which takes a locally computed link cost c and the metric m advertised by a neighbour) MUST only satisfy the following conditions:

if c is infinite, then M(c, m) is infinite;
M is strictly monotonic: M(c, m) > m.

Additionally, the metric SHOULD satisfy the following condition:

M is left-distributive: if m <= m', then M(c, m) <= M(c, m').

strict monotonicity is essential to the integrity of the network 🚨 (persistent routing loops may show up if it isn't satisfied), but left-distributivity is not. If it isn't satisfied, Babel will still converge to a loop-free configuration, it just might not reach a global optimum (in fact, a global optimum may not even exist). 🫶

The conditions above are easily satisfied by using the additive metric, i.e., by defining M(c, m) = c + m. Since the additive metric works with a large range of cost computation strategies, it is the RECOMMENDED default. ✨ See also Appendix C, which describes a technique that makes it possible to tweak the values of individual metrics without running the risk of creating routing loops. 🦋

3.5.3. Route Acquisition 📥

When a Babel node receives an update (prefix, plen, router-id, seqno, metric) from a neighbour neigh, it checks whether it already has a route table entry indexed by (prefix, plen, neigh). 👀

If no such entry exists:

if the update is unfeasible, it MAY be ignored;
if the metric is infinite (the update is a retraction of a route we do not know about), the update is ignored;
otherwise, a new entry is created in the route table, indexed by (prefix, plen, neigh), with source equal to (prefix, plen, router-id), seqno equal to seqno, and an advertised metric equal to the metric carried by the update.

If such an entry exists:

if the entry is currently selected, the update is unfeasible, and the router-id of the update is equal to the router-id of the entry, then the update MAY be ignored;
otherwise, the entry's sequence number, advertised metric, metric, and router-id are updated, and if the advertised metric is not infinite, the route's expiry timer is reset to a small multiple of the interval value included in the update (see "Route Expiry time" in Appendix B for suggested values). If the update is unfeasible, then the (now unfeasible) entry MUST be immediately unselected. If the update caused the router-id of the entry to change, an update (possibly a retraction) MUST be sent in a timely manner as described in Section 3.7.2. 🚦

Note that the route table may contain unfeasible routes, either because they were created by an unfeasible update or due to a metric fluctuation. 🙈 Such routes are never selected, since they are not known to be loop-free. Should all the feasible routes become unusable, however, the unfeasible routes can be made feasible and therefore possible to select by sending requests along them (see Section 3.8.2). 🔁

When a route's expiry timer triggers, the behaviour depends on whether the route's metric is finite. If the metric is finite, it is set to infinity and the expiry timer is reset. If the metric is already infinite, the route is flushed from the route table. 🧹

After the route table is updated, the route selection procedure (Section 3.6) is run. 💖

3.5.4. Hold Time ⏳

When a prefix P is retracted (because all routes are unfeasible or have an infinite metric, whether due to the expiry timer or for other reasons), and a shorter prefix P' that covers P is reachable, P' cannot in general be used for routing packets destined to P without running the risk of creating a routing loop (Section 2.8). 😭

To avoid this issue, whenever a prefix P is retracted, a route table entry with infinite metric is maintained as described in Section 3.5.3. As long as this entry is maintained, packets destined to an address within P MUST NOT be forwarded by following a route for a shorter prefix. This entry is removed as soon as a finite-metric update for prefix P is received and the resulting route selected. If no such update is forthcoming, the infinite metric entry SHOULD be maintained at least until it is guaranteed that no neighbour has selected the current node as next hop for prefix P. This can be achieved by either:

waiting until the route's expiry timer has expired (Section 3.5.3); or
sending a retraction with an acknowledgment request (Section 3.3) to every reachable neighbour that has not explicitly retracted prefix P, and waiting for all acknowledgments.

The former option is simpler and ensures that, at that point, any routes for prefix P pointing at the current node have expired. 🧐 However, since the expiry time can be as high as a few minutes, doing that prevents automatic aggregation by creating spurious black-holes for aggregated routes. 🕳️ The latter option is RECOMMENDED as it dramatically reduces the time for which a prefix is unreachable in the presence of aggregated routes. 🏆

3.6. Route Selection 🎯

Route selection is the process by which a single route for a given prefix is selected to be used for forwarding packets and to be re-advertised to a node's neighbours. 🗺️

Babel is designed to allow flexible route selection policies. As far as the algorithm's correctness is concerned, the route selection policy MUST only satisfy the following properties:

a route with infinite metric (a retracted route) is never selected;
an unfeasible route is never selected.

Babel nodes using different route selection strategies will interoperate and will not create routing loops as long as these two properties hold. 🤝

Route selection MUST NOT take seqnos into account: a route MUST NOT be preferred just because it carries a higher (more recent) seqno. 🙅‍♀️ Doing otherwise would cause route oscillation while a new seqno propagates across the network, and might create persistent black-holes if the metric being used is not left-distributive (Section 3.5.2). 💀

The obvious route selection strategy is to pick, for every destination, the feasible route with minimal metric. When all metrics are stable, this approach ensures convergence to a tree of shortest paths (assuming that the metric is left-distributive, see Section 3.5.2). 🌳 There are two reasons, however, why this strategy may lead to instability in the presence of continuously varying metrics. First, if two parallel routes oscillate around a common value, then the smallest metric strategy will keep switching between the two. 🙃 Second, the selection of a route increases congestion along it, which might increase packet loss, which in turn could cause its metric to increase; this kind of feedback loop is prone to causing persistent oscillations. 🎢

In order to limit these kinds of instabilities, a route selection strategy SHOULD include some form of hysteresis, i.e., be sensitive to a route's history: the strategy should only switch from the currently selected route to a different route if the latter has been consistently good for some period of time. 🧘‍♀️ A RECOMMENDED hysteresis algorithm is given in Appendix A.3. ✨

After the route selection procedure is run, triggered updates (Section 3.7.2) and requests (Section 3.8.2) are sent. 📤

3.7. Sending Updates ✉️

A Babel speaker advertises to its neighbours its set of selected routes. Normally, this is done by sending one or more multicast packets containing Update TLVs on all of its connected interfaces; however, on link technologies where multicast is significantly more expensive than unicast, a node MAY choose to send multiple copies of updates in unicast packets, especially when the number of neighbours is small. 📬

Additionally, in order to ensure that any black-holes are reliably cleared in a timely manner, a Babel node may send retractions (updates with an infinite metric) for any recently retracted prefixes. 🧽

If an update is for a route injected into the Babel domain by the local node (e.g., it carries the address of a local interface, the prefix of a directly attached network, or a prefix redistributed from a different routing protocol), the router-id is set to the local node's router-id, the metric is set to some arbitrary finite value (typically 0), and the seqno is set to the local router's sequence number. 🏠

If an update is for a route learnt from another Babel speaker, the router-id and sequence number are copied from the route table entry, and the metric is computed as specified in Section 3.5.2. 🧮

3.7.1. Periodic Updates 🔄

Every Babel speaker MUST advertise each of its selected routes on every interface, at least once every Update interval. Since Babel doesn't suffer from routing loops (there is no "counting to infinity") and relies heavily on triggered updates (Section 3.7.2), this full dump only needs to happen infrequently (see Appendix B for suggested intervals). 🥱✨

3.7.2. Triggered Updates 🚨

In addition to periodic routing updates, a Babel speaker sends unscheduled, or triggered, updates in order to inform its neighbours of a significant change in the network topology. 📣

A change of router-id for the selected route to a given prefix may be indicative of a routing loop in formation; hence, whenever it changes the selected router-id for a given destination, a node MUST send an update as an urgent TLV (as defined in Section 3.1). Additionally, it SHOULD make a reasonable attempt at ensuring that all reachable neighbours receive this update. 🫨

There are two strategies for ensuring that. If the number of neighbours is small, then it is reasonable to send the update together with an acknowledgment request; the update is resent until all neighbours have acknowledged the packet, up to some number of times. If the number of neighbours is large, however, requesting acknowledgments from all of them might cause a non-negligible amount of network traffic; in that case, it may be preferable to simply repeat the update some reasonable number of times (say, 3 for wireless and 2 for wired links). The number of copies MUST NOT exceed 5, and the copies SHOULD be separated by a small delay, as described in Section 3.1. 🎀

A route retraction is somewhat less worrying: if the route retraction doesn't reach all neighbours, a black-hole might be created, which, unlike a routing loop, does not endanger the integrity of the network. 🕳️ When a route is retracted, a node SHOULD send a triggered update and SHOULD make a reasonable attempt at ensuring that all neighbours receive this retraction. 💅

Finally, a node MAY send a triggered update when the metric for a given prefix changes in a significant manner, due to a received update, because a link's cost has changed or because a different next hop has been selected. A node SHOULD NOT send triggered updates for other reasons, such as when there is a minor fluctuation in a route's metric, when the selected next hop changes without inducing a significant change to the route's metric, or to propagate a new sequence number (except to satisfy a request, as specified in Section 3.8). 🙅‍♀️🌸

3.7.3. Maintaining Feasibility Distances ✨

Okay bestie, before a Babel node sends an update of the form (prefix, plen, router-id, seqno, metric) with a finite metric (so not a route retraction 🙅‍♀️), it has to update the feasibility distance in the source table 💅. Here's how:

If there's no entry indexed by (prefix, plen, router-id) in the source table yet, the node makes one with the value (prefix, plen, router-id, seqno, metric) 🌸.

If an entry (prefix, plen, router-id, seqno', metric') already exists, it gets updated like this:

if seqno > seqno', then seqno' := seqno, metric' := metric;
if seqno = seqno' and metric' > metric, then metric' := metric;
otherwise, nothing needs to be done.

After that, the garbage-collection timer for the entry gets reset ⏰. Note that the feasibility distance is not updated and the garbage-collection timer is not reset when a retraction (an update with infinite metric) is sent. Retractions don't count, periodt 🫶.

When the garbage-collection timer expires, the entry is removed from the source table 🗑️.

3.7.4. Split Horizon 🍓

When you're running over a transitive, symmetric link technology, like a point-to-point link or a wired LAN such as Ethernet, a Babel node SHOULD use an optimisation called split horizon 🧠. With split horizon on an interface, a routing update for prefix P does not get sent out the same interface where the selected route to P was learnt. It's giving "don't echo it back to where it came from" 🔁.

Split horizon SHOULD NOT be applied to an interface unless the interface is known to be symmetric and transitive 🙅‍♀️. In particular, split horizon is not applicable to decentralised wireless link technologies (for example IEEE 802.11 in ad hoc mode) when routing updates are sent over multicast 📡. Wireless ad hoc is a whole vibe, and split horizon just doesn't fit it 🥲.

3.8. Explicit Requests 🙋‍♀️

Normally, a node's route table gets filled by the regular and triggered updates its neighbours send 📬. Sometimes, though, a node sends explicit requests to force a resync with the source after a mobility event, or to keep a route from spuriously expiring 🧯.

Babel has two kinds of explicit request. Route requests just ask for an update for a given prefix. Seqno requests ask for an update for a given prefix with a specific sequence number. Route requests are never forwarded, while seqno requests get forwarded if the receiver can't satisfy them 🦋.

3.8.1. Handling Requests 🎀

When a request comes in, a node either forwards it or sends an update in reply, as the next sections explain. If that causes an update to go out, it's sent either to a multicast address on the interface the request arrived on, or to the unicast address of the neighbour that sent the request 💌.

The exact behaviour is different for route requests and seqno requests, so let's split them up 👯‍♀️.

3.8.1.1. Route Requests 🗺️

When a node gets a route request for a given prefix, it checks its route table for a selected route to that exact prefix. If one exists, it MUST send an update (over unicast or over multicast). If there isn't one, it MUST send a retraction for that prefix. Simple, but it's the rule 💅.

When a node receives a wildcard route request, it SHOULD send a full route table dump 📚. Full route dumps SHOULD be rate-limited, especially if they're sent over multicast, because nobody wants a flood 🌊.

3.8.1.2. Seqno Requests 🔢

When a node receives a seqno request for a given router-id and sequence number, it checks whether its route table has a selected entry for that prefix. If a selected route for the given prefix exists and has finite metric, and either the router-ids are different, or the router-ids are equal and the entry's sequence number is no smaller (modulo 2^(16)) than the requested sequence number, the node MUST send an update for the given prefix 🙌.

If the router-ids match but the requested seqno is larger (modulo 2^(16)) than the route entry's, the node compares the router-id against its own router-id. If the router-id is its own, it increases its sequence number by 1 (modulo 2^(16)) and sends an update 📈. A node MUST NOT increase its sequence number by more than 1 in reaction to a single seqno request. One bump per request, no drama 💁‍♀️.

Otherwise, if the requested router-id is not its own, the node looks at the Hop Count field of the request. If the hop count is 2 or more, and the node is advertising the prefix to its neighbours, it picks a neighbour to forward the request to like this:

if the node has one or more feasible routes towards the requested prefix with a next hop that is not the requesting node, then the node MUST forward the request to the next hop of one such route;
otherwise, if the node has one or more (not feasible) routes to the requested prefix with a next hop that is not the requesting node, then the node SHOULD forward the request to the next hop of one such route.

To actually forward the request, the node decrements the hop count and sends the request in a unicast packet to the selected neighbour 📬. The forwarded request SHOULD be sent as an urgent TLV (as defined in Section 3.1) 🚨.

A node SHOULD maintain a list of recently forwarded seqno requests, and forward the reply (an update with a seqno big enough to satisfy the request) as an urgent TLV (as defined in Section 3.1) 🏃‍♀️. A node SHOULD compare every incoming seqno request against that list, and avoid forwarding the request if it's redundant. That means the node has recently sent a request with the same prefix, router-id, and a seqno that is not smaller (modulo 2^(16)) 🧹.

Since the request-forwarding mechanism doesn't necessarily obey the feasibility condition, it can get caught in routing loops 🌀. That's why requests carry a hop count, to limit how long they stick around in the network ⏳. However, since requests only ever get forwarded as unicast packets, the initial hop count doesn't need to be kept particularly low, and an expanding horizon search isn't necessary 🙅‍♀️.

A single request MUST NOT be duplicated. It MUST NOT be forwarded to a multicast address, and it MUST NOT be forwarded to multiple neighbours. No copies, no multicast, no spray. Full stop 🛑.

If a seqno request is resent by its originator, though, the later copies may be forwarded to a different neighbour than the first one 🔁.

3.8.2. Sending Requests 📤

A Babel node MAY send a route or seqno request at any time, to either a multicast or a unicast address 🎉. There's only one case where originating requests is required, and that's covered in Section 3.8.2.1 🫶.

3.8.2.1. Avoiding Starvation 🍽️

When a route is retracted or expires, a Babel node usually switches to another feasible route for the same prefix 🔄. Sometimes, though, there are no such routes available 😬.

A node that has lost all feasible routes to a given destination, but still has unexpired unfeasible routes to that destination, MUST send a seqno request. If it doesn't have any such routes, it MAY still send a seqno request anyway 🙏. The request's router-id is set to the router-id of the route the node has just lost, and the requested seqno is the value in the source table plus 1 ➕.

The request carries a hop count, which is a last-resort mechanism to make sure it eventually vanishes from the network 👋. It MAY be set to any value larger than the diameter of the network (64 is a suitable default value) 🔢.

If the node has any (unfeasible) routes to the requested destination, then it MUST send the request to at least one of the next-hop neighbours that advertised those routes, and SHOULD send it to all of them 📣. In any case, it MAY send the request to any other neighbours, whether they advertise a route to the requested destination or not 🤷‍♀️. A simple implementation strategy is therefore to unconditionally multicast the request over all interfaces 💫.

Similar requests will be sent by other nodes that are affected by the route's loss 🌐. If the network is still connected, and assuming no packet loss, at least one of these requests will be forwarded to the source. That gets a route advertised with a new sequence number 🎊. (Thanks to duplicate suppression, only a small number of such requests are expected to actually reach the source 🧼.)

To compensate for packet loss, a node SHOULD repeat such a request a small number of times if no route becomes feasible within a short time. (See "Request timeout" in Appendix B for suggested values ⏱️.) In the presence of heavy packet loss, though, all of these requests might get lost. If that happens, the mechanism in the next section will eventually make sure a new seqno is received 🫠.

3.8.2.2. Dealing with Unfeasible Updates 🙃

When a route's metric increases, a node might receive an unfeasible update for a route it has currently selected 📈. As specified in Section 3.5.1, the receiving node will either ignore the update or unselect the route 🙈.

To keep routes from spuriously expiring just because they've become unfeasible, a node SHOULD send a unicast seqno request when it receives an unfeasible update for a route that is currently selected 💖. The requested sequence number is computed from the source table, as in Section 3.8.2.1 🧮.

Also, metric computation doesn't necessarily line up with the delay in propagating updates. So a node might get an unfeasible update from a currently unselected neighbour that's preferable to the selected route (for example, because it has a much smaller metric) 👀. In that case, the node SHOULD send a unicast seqno request to the neighbour that advertised the preferable update 💌.

3.8.2.3. Preventing Routes from Expiring ⏰

In normal operation, a route's expiry timer never actually triggers 🙌. A route's hold time is computed from an explicit interval included in Update TLVs, so a new update (possibly a retraction) should arrive in time to stop the route from expiring ✨.

With packet loss in the mix, though, it can happen that no update gets successfully received for an extended period of time, and the route expires anyway 😭. To avoid that spurious expiry, a Babel node SHOULD send a unicast route request to the neighbour that advertised the route, shortly before the selected route expires 🏃‍♀️. Nodes always send either updates or retractions in response to non-wildcard route requests (Section 3.8.1.1), so this will usually result in the route being either refreshed or retracted 💅🌸.

4. Protocol Encoding 🎀

okay so bestie, this is where we get into the actual bytes 🧚 A Babel packet MUST be sent as the body of a UDP datagram, with the network-layer hop count set to 1. It goes to a well-known multicast address or to a unicast address, over IPv4 or IPv6. For IPv6, those addresses are link-local. Both the source and destination UDP ports are set to a well-known port number.

Receivers are picky too 💅 A Babel packet MUST be silently ignored unless its source address is either a link-local IPv6 address or an IPv4 address on the local network, and its source port is the well-known Babel port. It MAY be silently ignored if its destination address is a global IPv6 address.

We also want packets to be efficient without getting chopped up at the lower layers 📦 So a Babel node SHOULD maximise the size of the packets it sends, up to the outgoing interface's MTU minus the lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP over IPv6). It MUST NOT send packets larger than the attached interface's MTU adjusted for lower-layer headers or 512 octets, whichever is larger, but not exceeding 2^(16) - 1 adjusted for lower-layer headers. Every Babel speaker MUST be able to receive packets as large as any attached interface's MTU adjusted for lower-layer headers or 512 octets, whichever is larger. And no, Babel packets MUST NOT be sent in IPv6 jumbograms [RFC2675]. Not even a little bit 🙈

4.1. Data Types

4.1.1. Representation of Integers

All multi-octet fields that represent integers are encoded with the most significant octet first. This is Big-Endian format [IEN137], also called network order 🌸 The base protocol only carries unsigned values. If an extension needs signed values, it'll have to specify how they're encoded (for example, two's complement).

4.1.2. Interval

Relative times are carried as 16-bit values that count centiseconds (hundredths of a second) ⏱️ That gets you times up to roughly 11 minutes, with a granularity of 10 ms. Honestly, that covers every reasonable use of Babel (see also Appendix B) ✨

4.1.3. Router-Id

A router-id is an arbitrary 8-octet value 🦋 A router-id MUST NOT be all binary zeroes (0000000000000000 in hexadecimal) or all binary ones (FFFFFFFFFFFFFFFF in hexadecimal). Those two are off-limits, periodt 🚫

4.1.4. Address

Addresses take up most of the protocol, so there are several ways to encode them 💖 On top of that, inside Update TLVs, a common subnet prefix can be left out when multiple addresses get sent in one packet. This is called address compression (Section 4.6.9) 🫶

Here are the address encodings (AEs):

AE 0: Wildcard address. The value is 0 octets long.
AE 1: IPv4 address. Compression is allowed. 4 octets or less.
AE 2: IPv6 address. Compression is allowed. 16 octets or less.
AE 3: Link-local IPv6 address. Compression is not allowed. The value is 8 octets long, and a prefix of fe80::/64 is implied. 🌈

The address family tied to an address encoding is either IPv4 or IPv6. It's undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 and 3 🧚

4.1.5. Prefixes

A network prefix is encoded just like a network address, except it's stored in the smallest number of octets that can hold its significant bits (up to the prefix length) 💜

4.2. Packet Format

A Babel packet is a 4-octet header, followed by a sequence of TLVs (that's the packet body), optionally followed by a second sequence of TLVs (the packet trailer) 🎀 The format is built to be extensible. See Appendix D for extensibility considerations.

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Magic     |    Version    |        Body length            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          Packet Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
|         Packet Trailer...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

Fields:

Magic: The arbitrary but carefully chosen value 42 (decimal). Packets with a first octet different from 42 MUST be silently ignored. 🔥
Version: This document specifies version 2 of the Babel protocol. Packets with a second octet different from 2 MUST be silently ignored.
Body length: The length in octets of the body following the packet header. This excludes the Magic, Version, and Body length fields, and it also excludes the packet trailer.
Packet Body: The packet body, which is a sequence of TLVs.
Packet Trailer: The packet trailer, which is another sequence of TLVs.

Both the packet body and trailer are sequences of TLVs. The packet body is the normal home for TLVs. The packet trailer only holds specialised TLVs that don't need to be protected by cryptographic security mechanisms 🔐 When parsing the trailer, the receiver MUST ignore any TLV unless its definition explicitly says it's allowed to appear there. Of the TLVs defined in this document, only Pad1 and PadN are allowed in the trailer. Since those get ignored anyway, an implementation MAY silently ignore the packet trailer without even parsing it, unless it implements at least one protocol extension that defines TLVs that are allowed in the trailer 💅

4.3. TLV Format

Except for Pad1, every TLV has this structure:

 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      |    Length     |     Payload...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

Fields:

Type: The type of the TLV.
Length: The length of the body in octets, not counting the Type and Length fields.
Payload: The TLV payload. It's made up of a body and, for some TLV types, an optional list of sub-TLVs 🧩

TLVs with an unknown type value MUST be silently ignored. No drama, just skip 🌸

4.4. Sub-TLV Format

Every TLV carries an explicit length in its header. Most TLVs are self-terminating, though, which means you can work out the length of the body without looking at the explicit Length field 🧠 If a TLV is self-terminating, the space between its natural size and the size announced in the Length field can be used to store a sequence of sub-TLVs.

Sub-TLVs have the same structure as TLVs. Except for Pad1, every one of them 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      |    Length     |     Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

Fields:

Type: The type of the sub-TLV.
Length: The length of the body in octets, not counting the Type and Length fields.
Body: The sub-TLV body. How it's interpreted depends on both the sub-TLV's type and the type of the TLV it's embedded in.

The most significant bit of the sub-TLV type (the bit with value 80 in hexadecimal) is called the mandatory bit. In other words, sub-TLV types 128 through 255 have the mandatory bit set. This bit tells you how to handle unknown sub-TLVs ⚠️ If the mandatory bit is not set, an unknown sub-TLV MUST be silently ignored, and the rest of the TLV is processed normally. If the mandatory bit is set, the whole enclosing TLV MUST be silently ignored. The one exception is updating the parser state with a Router-Id, Next Hop, or Update TLV, which is covered in the next section.

The mandatory bit is the difference between "ignore this little bit and keep going" and "ignore the whole TLV, no exceptions." Don't mix those up, bestie 🚨

4.5. Parser State and Encoding of Updates

In a big network, most Babel traffic is route updates. That's why so much care went into encoding them efficiently 🚀 The data an update conceptually contains (Section 3.5) gets split into three pieces:

The prefix, seqno, and metric live in the Update TLV itself (Section 4.6.9).
The router-id comes from the Router-Id TLV that precedes the Update TLV. That one can be shared among several Update TLVs (Section 4.6.7).
The next hop comes either from the source address of the network-layer packet carrying the Babel packet, or from an explicit Next Hop TLV (Section 4.6.8).

On top of that, an Update TLV can leave out part of the prefix being announced. The missing part is pulled from the preceding Update TLV in the same address family (IPv4 or IPv6) ✂️ There's also a special optimisation for when a router-id matches the interface-id part of an IPv6 address. In that case, the Router-Id TLV itself can be left out, and the router-id gets derived from the low-order bits of the advertised prefix (Section 4.6.9).

To make all this compression work, Babel uses a stateful parser. A TLV can refer to data from a previous TLV 🧩 The parser state has these pieces:

For each address encoding that allows compression, the current default prefix. It's undefined at the start of the packet, and it gets updated by each Update TLV with the Prefix flag set (Section 4.6.9).
For each address family (IPv4 or IPv6), the current next hop. At the start of a packet, this is the source address of the enclosing packet for the matching address family. It gets updated by each Next Hop TLV (Section 4.6.8).
The current router-id. It's undefined at the start of the packet, and it gets updated by each Router-Id TLV (Section 4.6.7) and by each Update TLV with the Router-Id flag set.

The parser state has to match across every implementation, so it gets updated before checking for mandatory sub-TLVs. Parsing a TLV MUST update the parser state, even if the TLV is otherwise ignored because of an unknown mandatory sub-TLV or for any other reason 🫶

None of the TLVs that change the parser state are allowed in the packet trailer. That means an implementation can choose to use a dedicated stateless parser for the trailer ✨

4.6. Details of Specific TLVs

4.6.1. Pad1

 0
 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|   Type = 0    |
+-+-+-+-+-+-+-+-+

Fields:

Type: Set to 0 to indicate a Pad1 TLV.

This TLV is silently ignored on reception. It is allowed in the packet trailer 🍓

4.6.2. PadN

 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 = 1   |    Length     |      MBZ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

Fields:

Type: Set to 1 to indicate a PadN TLV.
Length: The length of the body in octets, not counting the Type and Length fields.
MBZ: Must be zero, set to 0 on transmission.

This TLV is silently ignored on reception. It is allowed in the packet trailer 💜

4.6.3. Acknowledgment Request ✨

    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 = 2   |    Length     |          Reserved             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Opaque            |          Interval             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

okay so this TLV is basically the sender going "hey, please reply to me with an Acknowledgment TLV within this many centiseconds" 🫶 The Interval field is the deadline, and the receiver has to beat it, with a little margin for propagation time. 🦋

Fields:

Type: set to 2 to say "this is an Acknowledgment Request TLV" 💖
Length: the length of the body in octets, not counting the Type and Length fields 📏
Reserved: sent as 0, and MUST be ignored on reception 🙈
Opaque: an arbitrary value that gets echoed back in the receiver's Acknowledgment TLV 🎀
Interval: a time interval in centiseconds. After this long, the sender assumes the packet got lost 💀 This MUST NOT be 0. The receiver MUST send an Acknowledgment TLV before this time has elapsed, with a margin for propagation time ⏰

This TLV is self-terminating and allows sub-TLVs. ✨

4.6.4. Acknowledgment ✨

    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     |           Opaque              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

This is the reply 💌 A node sends this when it gets an Acknowledgment Request TLV, so it's basically the "got it bestie" moment. 🫶

Fields:

Type: set to 3 to say "this is an Acknowledgment TLV" 💖
Length: the length of the body in octets, not counting the Type and Length fields 📏
Opaque: set to the Opaque value of the Acknowledgment Request that prompted this Acknowledgment 🎀

Here's the lowkey important bit 👀 Opaque values aren't globally unique, so this TLV MUST be sent to a unicast address. No shouting it into the multicast void, the reply has to go to one specific address. 🔥

This TLV is self-terminating and allows sub-TLVs. ✨

4.6.5. Hello ✨

    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 = 4   |    Length     |            Flags              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Seqno              |          Interval             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The Hello TLV is the neighbour discovery queen 👑 It's used for finding neighbours and figuring out a neighbour's reception cost. Main character energy, honestly. 🌈

Fields:

Type: set to 4 to say "this is a Hello TLV" 💖
Length: the length of the body in octets, not counting the Type and Length fields 📏
Flags: the individual bits here control special handling of this TLV (more on that below) 🦋
Seqno: if the Unicast flag is set, this is the sending node's outgoing Unicast Hello seqno for this neighbour. Otherwise, it's the sending node's outgoing Multicast Hello seqno for this interface. 🔢
Interval: if nonzero, this is an upper bound, in centiseconds, on the time after which the sending node will send a new scheduled Hello TLV with the same setting of the Unicast flag. If it's 0, then this Hello is an unscheduled Hello and doesn't carry any new info about when Hellos get sent. ⏳

The Flags field works like this:

    0                   1
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

U (Unicast) flag (8000 hexadecimal): if set, this Hello is a Unicast Hello. Otherwise, it's a Multicast Hello. 💜
X: all other bits MUST be sent as 0 and silently ignored on reception. 🙈

Every time a Hello gets sent, the matching seqno counter MUST be incremented. 🔁 There's a single seqno counter for all the Multicast Hellos a given node sends over a given interface. So if the Unicast flag is not set, this TLV MUST be sent to all neighbours on this link. You can do that with a multicast destination, or by sending multiple packets to the unicast addresses of all reachable neighbours. 📨 On the flip side, if the Unicast flag is set, this TLV MUST be sent to a single neighbour, which you can do by sending to a unicast destination. 🎯 To avoid big jumps in link quality, multiple Hello TLVs SHOULD NOT be sent in the same packet. 🫧

This TLV is self-terminating and allows sub-TLVs. ✨

4.6.6. IHU ✨

    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 = 5   |    Length     |       AE      |    Reserved   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Rxcost             |          Interval             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       Address...
   +-+-+-+-+-+-+-+-+-+-+-+-

IHU stands for "I Heard You" 🥹 and this TLV is how you confirm bidirectional reachability and share a link's transmission cost. It's the "yes I see you too" text of routing. 💌

Fields:

Type: set to 5 to say "this is an IHU TLV" 💖
Length: the length of the body in octets, not counting the Type and Length fields 📏
AE: the encoding of the Address field. This should be 1 or 3 in most cases. As an optimisation, it MAY be 0 if the TLV is sent to a unicast address, if the association is over a point-to-point link, or when bidirectional reachability is ascertained by means outside of the Babel protocol. ⚡
Reserved: sent as 0, and MUST be ignored on reception 🙈
Rxcost: the rxcost according to the sending node of the interface whose address is in the Address field. The value FFFF hexadecimal (infinity) means this interface is unreachable. 🚫
Interval: an upper bound, in centiseconds, on the time after which the sending node will send a new IHU. This MUST NOT be 0. The receiving node uses this value to compute a hold time for this symmetric association. ⏳
Address: the address of the destination node, in the format given by the AE field. Address compression is not allowed. 🏠

Conceptually, an IHU is destined to a single neighbour. 💁 But IHU TLVs carry an explicit destination address, and they MAY be sent to a multicast address. That lets you bundle IHUs for different neighbours into one packet, and skip the ARP or Neighbour Discovery exchange when a neighbour isn't being used for data traffic. Smart, right? 🧠✨

IHU TLVs with an unknown value in the AE field MUST be silently ignored. 🙅‍♀️

This TLV is self-terminating and allows sub-TLVs. ✨

4.6.7. Router-Id ✨

    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 = 6   |    Length     |          Reserved             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                           Router-Id                           +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A Router-Id TLV sets up a router-id that subsequent Update TLVs just assume, as described in Section 4.5. 🪪 Even if this TLV gets ignored because of an unknown mandatory sub-TLV, it still sets the router-id. Iconic. 👑

Fields:

Type: set to 6 to say "this is a Router-Id TLV" 💖
Length: the length of the body in octets, not counting the Type and Length fields 📏
Reserved: sent as 0, and MUST be ignored on reception 🙈
Router-Id: the router-id for routes advertised in subsequent Update TLVs. This MUST NOT consist of all zeroes or all ones. 🚫

This TLV is self-terminating and allows sub-TLVs. ✨

4.6.8. Next Hop ✨

    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 = 7   |    Length     |      AE       |   Reserved    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       Next hop...
   +-+-+-+-+-+-+-+-+-+-+-+-

A Next Hop TLV sets up a next-hop address for a given address family (IPv4 or IPv6). Subsequent Update TLVs then imply that address, as described in Section 4.5. 🗺️ Like the Router-Id one, this TLV still sets up the next hop for those Updates even when it's ignored because of an unknown mandatory sub-TLV. 💅

Fields:

Type: set to 7 to say "this is a Next Hop TLV" 💖
Length: the length of the body in octets, not counting the Type and Length fields 📏
AE: the encoding of the Address field. This SHOULD be 1 (IPv4) or 3 (link-local IPv6), and MUST NOT be 0. 🧭
Reserved: sent as 0, and MUST be ignored on reception 🙈
Next hop: the next-hop address advertised by subsequent Update TLVs for this address family 🦋

When the address family matches the network-layer protocol this packet is carried over, you don't need a Next Hop TLV. Without one for a given address family, the next-hop address is taken to be the source address of the packet. 📬

Next Hop TLVs with an unknown value for the AE field MUST be silently ignored. 🙅‍♀️

This TLV is self-terminating, and allows sub-TLVs. ✨

4.6.9. Update ✨

    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 = 8   |    Length     |       AE      |    Flags      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Plen      |    Omitted    |            Interval           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Seqno             |            Metric             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Prefix...
   +-+-+-+-+-+-+-+-+-+-+-+-

An Update TLV is the one that's like "here's a route, or bye bye route" 💅 As an optimisation, it can optionally have the side effect of establishing a new implied router-id and a new default prefix, as described in Section 4.5. Iconic multitasking 🦋

Fields:

Type: Set to 8 to indicate an Update TLV 🎀
Length: The length of the body in octets, exclusive of the Type and Length fields.
AE: The encoding of the Prefix field.
Flags: The individual bits of this field specify special handling of this TLV (see below).
Plen: The length in bits of the advertised prefix. If AE is 3 (link-local IPv6), the Omitted field MUST be 0. Non-negotiable, bestie 🙅‍♀️
Omitted: The number of octets that have been omitted at the beginning of the advertised prefix and that should be taken from a preceding Update TLV in the same address family with the Prefix flag set.
Interval: An upper bound, expressed in centiseconds, on the time after which the sending node will send a new update for this prefix. This MUST NOT be 0. The receiving node will use this value to compute a hold time for the route table entry. The value FFFF hexadecimal (infinity) expresses that this announcement will not be repeated unless a request is received (Section 3.8.2.3). So FFFF is the "I'm not repeating myself unless you ask" flex 💀
Seqno: The originator's sequence number for this update. ✨
Metric: The sender's metric for this route. The value FFFF hexadecimal (infinity) means that this is a route retraction. Bye, route 😭
Prefix: The prefix being advertised. This field's size is (Plen/8 - Omitted) rounded upwards.

The Flags field is interpreted as follows:

 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|P|R|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+

P (Prefix) flag (80 hexadecimal): if set, then this Update TLV establishes a new default prefix for subsequent Update TLVs with a matching address encoding within the same packet, even if this TLV is otherwise ignored due to an unknown mandatory sub-TLV. Main character prefix energy 👑

R (Router-Id) flag (40 hexadecimal): if set, then this TLV establishes a new default router-id for this TLV and subsequent Update TLVs in the same packet, even if this TLV is otherwise ignored due to an unknown mandatory sub-TLV. This router-id is computed from the first address of the advertised prefix as follows:

if the length of the address is 8 octets or more, then the new router-id is taken from the 8 last octets of the address;
if the length of the address is smaller than 8 octets, then the new router-id consists of the required number of zero octets followed by the address, i.e., the address is stored on the right of the router-id. For example, for an IPv4 address, the router-id consists of 4 octets of zeroes followed by the IPv4 address. 🌸

X: all other bits MUST be sent as 0 and silently ignored on reception. Leftover bits are just vibes, so don't touch them 🫶

The prefix being advertised by an Update TLV is computed as follows:

the first Omitted octets of the prefix are taken from the previous Update TLV with the Prefix flag set and the same address encoding, even if it was ignored due to an unknown mandatory sub-TLV; if the Omitted field is not zero and there is no such TLV, then this Update MUST be ignored;
the next (Plen/8 - Omitted) rounded upwards octets are taken from the Prefix field;
if Plen is not a multiple of 8, then any bits beyond Plen (i.e., the low-order (8 - Plen MOD 8) bits of the last octet) are cleared;
the remaining octets are set to 0.

If the Metric field is finite, the router-id of the originating node for this announcement is taken from the prefix advertised by this Update if the Router-Id flag is set, computed as described above. Otherwise, it is taken either from the preceding Router-Id TLV, or the preceding Update TLV with the Router-Id flag set, whichever comes last, even if that TLV is otherwise ignored due to an unknown mandatory sub-TLV; if there is no suitable TLV, then this update is ignored. Lots of tracking the receipts 🧾

The next-hop address for this update is taken from the last preceding Next Hop TLV with a matching address family (IPv4 or IPv6) in the same packet even if it was otherwise ignored due to an unknown mandatory sub-TLV; if no such TLV exists, it is taken from the network-layer source address of this packet if it belongs to the same address family as the prefix being announced; otherwise, this Update MUST be ignored. 🚫

If the metric field is FFFF hexadecimal, this TLV specifies a retraction. In that case, the router-id, next hop, and seqno are not used. AE MAY then be 0, in which case this Update retracts all of the routes previously advertised by the sending interface. If the metric is finite, AE MUST NOT be 0; Update TLVs with finite metric and AE equal to 0 MUST be ignored. If the metric is infinite and AE is 0, Plen and Omitted MUST both be 0; Update TLVs that do not satisfy this requirement MUST be ignored. Being a retraction is a whole mood 😭🌈

Update TLVs with an unknown value in the AE field MUST be silently ignored. ✨

This TLV is self-terminating and allows sub-TLVs. 💖

4.6.10. Route Request 🦋

    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 = 9   |    Length     |      AE       |     Plen      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Prefix...
   +-+-+-+-+-+-+-+-+-+-+-+-

A Route Request TLV is the "bestie, pls send me that route" move. It prompts the receiver to send an update for a given prefix, or a full route table dump. 🍓

Fields:

Type: Set to 9 to indicate a Route Request TLV.
Length: The length of the body in octets, exclusive of the Type and Length fields.
AE: The encoding of the Prefix field. The value 0 specifies that this is a request for a full route table dump (a wildcard request). Ask for everything, iykyk 👑
Plen: The length in bits of the requested prefix.
Prefix: The prefix being requested. This field's size is Plen/8 rounded upwards.

A Request TLV prompts the receiver to send an update message (possibly a retraction) for the prefix specified by the AE, Plen, and Prefix fields, or a full dump of its route table if AE is 0 (in which case Plen must be 0 and Prefix is of length 0). A Request TLV with AE set to 0 and Plen not set to 0 MUST be ignored. That's a no-cap rule, so don't mix the two 🙅‍♀️

This TLV is self-terminating and allows sub-TLVs. 🧚

4.6.11. Seqno Request 🌸

    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 = 10  |    Length     |      AE       |    Plen       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Seqno             |  Hop Count    |   Reserved    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                          Router-Id                            +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Prefix...
   +-+-+-+-+-+-+-+-+-+-+

A Seqno Request TLV is the "send me a fresher one of these, pretty please" TLV 🥺 It prompts the receiver to send an Update for a given prefix with a given sequence number, or to forward the request further if it cannot be satisfied locally.

Fields:

Type: Set to 10 to indicate a Seqno Request TLV.
Length: The length of the body in octets, exclusive of the Type and Length fields.
AE: The encoding of the Prefix field. This MUST NOT be 0.
Plen: The length in bits of the requested prefix.
Seqno: The sequence number that is being requested.
Hop Count: The maximum number of times that this TLV may be forwarded, plus 1. This MUST NOT be 0. Hop count is basically a little passport stamp 🛂
Reserved: Sent as 0 and MUST be ignored on reception.
Router-Id: The Router-Id that is being requested. This MUST NOT consist of all zeroes or all ones.
Prefix: The prefix being requested. This field's size is Plen/8 rounded upwards.

A Seqno Request TLV prompts the receiving node to send a finite-metric Update for the prefix specified by the AE, Plen, and Prefix fields, with either a router-id different from what is specified by the Router-Id field, or a Seqno no less (modulo 2^(16)) than what is specified by the Seqno field. If this request cannot be satisfied locally, then it is forwarded according to the rules set out in Section 3.8.1.2. Passing the request along like a group project 📚

While a Seqno Request MAY be sent to a multicast address, it MUST NOT be forwarded to a multicast address and MUST NOT be forwarded to more than one neighbour. A request MUST NOT be forwarded if its Hop Count field is 1. Forwarding has limits, bestie, don't be extra 🙅‍♀️💅

This TLV is self-terminating and allows sub-TLVs. 💜

4.7. Details of specific sub-TLVs 🌈

4.7.1. Pad1 🧸

 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|   Type = 0    |
+-+-+-+-+-+-+-+-+

Fields:

Type: Set to 0 to indicate a Pad1 sub-TLV.

This sub-TLV is silently ignored on reception. It is allowed within any TLV that allows sub-TLVs. Literally just a little filler, zero drama 🫧

4.7.2. PadN 🫶

    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 = 1   |    Length     |      MBZ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

Fields:

Type: Set to 1 to indicate a PadN sub-TLV.
Length: The length of the body in octets, exclusive of the Type and Length fields.
MBZ: Must be zero, set to 0 on transmission.

This sub-TLV is silently ignored on reception. It is allowed within any TLV that allows sub-TLVs. PadN is the bigger padding cousin, same energy, just longer 💖✨

5. IANA Considerations 🎀

okay so IANA (the folks who keep the official lists for the Internet) has a bunch of Babel stuff set up, and I'm about to spill it all 💅

IANA has registered the UDP port number 6696, called babel, for use by the Babel protocol. 🦋

IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. 🌸

IANA has created a registry called "Babel TLV Types". The allocation policy for this registry is Specification Required [RFC8126] for Types 0-223 and Experimental Use for Types 224-254. The values in this registry are as follows: ✨

    +=========+==========================================+===========+
    | Type    | Name                                     | Reference |
    +=========+==========================================+===========+
    | 0       | Pad1                                     | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 1       | PadN                                     | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 2       | Acknowledgment Request                   | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 3       | Acknowledgment                           | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 4       | Hello                                    | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 5       | IHU                                      | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 6       | Router-Id                                | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 7       | Next Hop                                 | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 8       | Update                                   | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 9       | Route Request                            | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 10      | Seqno Request                            | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 11      | TS/PC                                    | [RFC7298] |
    +---------+------------------------------------------+-----------+
    | 12      | HMAC                                     | [RFC7298] |
    +---------+------------------------------------------+-----------+
    | 13      | Reserved                                 |           |
    +---------+------------------------------------------+-----------+
    | 14      | Reserved                                 |           |
    +---------+------------------------------------------+-----------+
    | 15      | Reserved                                 |           |
    +---------+------------------------------------------+-----------+
    | 224-254 | Reserved for Experimental Use            | RFC 8966  |
    +---------+------------------------------------------+-----------+
    | 255     | Reserved for expansion of the type space | RFC 8966  |
    +---------+------------------------------------------+-----------+

                                 Table 1

IANA has created a registry called "Babel Sub-TLV Types". The allocation policy for this registry is Specification Required for Types 0-111 and 128-239, and Experimental Use for Types 112-126 and 240-254. The values in this registry are as follows: 💖

      +=========+===============================+===================+
      | Type    | Name                          | Reference         |
      +=========+===============================+===================+
      | 0       | Pad1                          | RFC 8966          |
      +---------+-------------------------------+-------------------+
      | 1       | PadN                          | RFC 8966          |
      +---------+-------------------------------+-------------------+
      | 2       | Diversity                     | [BABEL-DIVERSITY] |
      +---------+-------------------------------+-------------------+
      | 3       | Timestamp                     | [BABEL-RTT]       |
      +---------+-------------------------------+-------------------+
      | 4-111   | Unassigned                    |                   |
      +---------+-------------------------------+-------------------+
      | 112-126 | Reserved for Experimental Use | RFC 8966          |
      +---------+-------------------------------+-------------------+
      | 127     | Reserved for expansion of the | RFC 8966          |
      |         | type space                    |                   |
      +---------+-------------------------------+-------------------+
      | 128     | Source Prefix                 | [BABEL-SS]        |
      +---------+-------------------------------+-------------------+
      | 129-239 | Unassigned                    |                   |
      +---------+-------------------------------+-------------------+
      | 240-254 | Reserved for Experimental Use | RFC 8966          |
      +---------+-------------------------------+-------------------+
      | 255     | Reserved for expansion of the | RFC 8966          |
      |         | type space                    |                   |
      +---------+-------------------------------+-------------------+

                                  Table 2

IANA has created a registry called "Babel Address Encodings". The allocation policy for this registry is Specification Required for Address Encodings (AEs) 0-223, and Experimental Use for AEs 224-254. The values in this registry are as follows: 🧚

     +=========+========================================+===========+
     | AE      | Name                                   | Reference |
     +=========+========================================+===========+
     | 0       | Wildcard address                       | RFC 8966  |
     +---------+----------------------------------------+-----------+
     | 1       | IPv4 address                           | RFC 8966  |
     +---------+----------------------------------------+-----------+
     | 2       | IPv6 address                           | RFC 8966  |
     +---------+----------------------------------------+-----------+
     | 3       | Link-local IPv6 address                | RFC 8966  |
     +---------+----------------------------------------+-----------+
     | 4-223   | Unassigned                             |           |
     +---------+----------------------------------------+-----------+
     | 224-254 | Reserved for Experimental Use          | RFC 8966  |
     +---------+----------------------------------------+-----------+
     | 255     | Reserved for expansion of the AE space | RFC 8966  |
     +---------+----------------------------------------+-----------+

                                 Table 3

IANA has renamed the registry called "Babel Flags Values" to "Babel Update Flags Values". The allocation policy for this registry is Specification Required. The values in this registry are as follows: 🌈

                  +=====+===================+===========+
                  | Bit | Name              | Reference |
                  +=====+===================+===========+
                  | 0   | Default prefix    | RFC 8966  |
                  +-----+-------------------+-----------+
                  | 1   | Default router-id | RFC 8966  |
                  +-----+-------------------+-----------+
                  | 2-7 | Unassigned        |           |
                  +-----+-------------------+-----------+

                                  Table 4

IANA has created a new registry called "Babel Hello Flags Values". The allocation policy for this registry is Specification Required. The initial values in this registry are as follows: 🍓

                     +======+============+===========+
                     | Bit  | Name       | Reference |
                     +======+============+===========+
                     | 0    | Unicast    | RFC 8966  |
                     +------+------------+-----------+
                     | 1-15 | Unassigned |           |
                     +------+------------+-----------+

                                  Table 5

IANA has replaced all references to RFCs 6126 and 7557 in all of the registries mentioned above with references to this document. 🫶

6. Security Considerations 🔐

okay bestie, this part is SERIOUS 😭 As defined in this document, Babel is a completely insecure protocol. Without additional security mechanisms, Babel trusts any information it receives in plaintext UDP datagrams and acts on it. An attacker that is present on the local network can impact Babel operation in a variety of ways; for example they can: 💀

spoof a Babel packet, and redirect traffic by announcing a route with a smaller metric, a larger sequence number, or a longer prefix;
spoof a malformed packet, which could cause an insufficiently robust implementation to crash or interfere with the rest of the network;
replay a previously captured Babel packet, which could cause traffic to be redirected, black-holed, or otherwise interfere with the network.

When carried over IPv6, Babel packets are ignored unless they are sent from a link-local IPv6 address. Since routers don't forward link-local IPv6 packets, this mitigates the attacks outlined above by restricting them to on-link attackers. No such natural protection exists when Babel packets are carried over IPv4, which is one of the reasons why it is recommended to deploy Babel over IPv6 (Section 3.1). 🌸

It is usually difficult to ensure that packets arriving at a Babel node are trusted, even in the case where the local link is believed to be secure. For that reason, it is RECOMMENDED that all Babel traffic be protected by an application-layer cryptographic protocol. There are currently two suitable mechanisms, which implement different trade-offs between implementation simplicity and security: ✨

Babel over DTLS [RFC8968] runs the majority of Babel traffic over DTLS and leverages DTLS to authenticate nodes and provide confidentiality and integrity protection;
MAC authentication [RFC8967] appends a message authentication code (MAC) to every Babel packet to prove that it originated at a node that knows a shared secret, and includes sufficient additional information to prove that the packet is fresh (not replayed).

Both mechanisms enable nodes to ignore packets generated by attackers without the proper credentials. They also ensure integrity of messages and prevent message replay. While Babel-DTLS supports asymmetric keying and ensures confidentiality, Babel-MAC has a much more limited scope (see Sections 1.1, 1.2, and 7 of [RFC8967]). Since Babel-MAC is simpler and more lightweight, it is recommended in preference to Babel-DTLS in deployments where its limitations are acceptable, i.e., when symmetric keying is sufficient and where the routing information is not considered confidential. 🔥

Every implementation of Babel SHOULD implement BABEL-MAC. 👑

One should be aware that the information that a mobile Babel node announces to the whole routing domain is sufficient to determine the mobile node's physical location with reasonable precision, which might cause privacy concerns even if the control traffic is protected from unauthenticated attackers by a cryptographic mechanism such as Babel-DTLS. This issue may be mitigated somewhat by using randomly chosen router-ids and randomly chosen IP addresses, and changing them often enough. 🙈

7. References 📚

7.1. Normative References ✨

okay so these are the must-read docs 📚 the spec literally leans on, and the key words thing is [RFC2119] + [RFC8174] 💅

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

[RFC793]   Postel, J., "Transmission Control Protocol", STD 7,
           RFC 793, DOI 10.17487/RFC0793, September 1981,
           <https://www.rfc-editor.org/info/rfc793>.

[RFC8126]  Cotton, M., Leiba, B., and T. Narten, "Guidelines for
           Writing an IANA Considerations Section in RFCs", BCP 26,
           RFC 8126, DOI 10.17487/RFC8126, June 2017,
           <https://www.rfc-editor.org/info/rfc8126>.

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

[RFC8967]  Dô, C., Kolodziejak, W., and J. Chroboczek, "MAC
           Authentication for the Babel Routing Protocol", RFC 8967,
           DOI 10.17487/RFC8967, January 2021,
           <https://www.rfc-editor.org/info/rfc8967>.

7.2. Informative References 🧠

these are the extra reading if you want the whole story, the history, the side quests, and the sources behind the ideas 🌸

[BABEL-DIVERSITY]
           Chroboczek, J., "Diversity Routing for the Babel Routing
           Protocol", Work in Progress, Internet-Draft, draft-
           chroboczek-babel-diversity-routing-01, 15 February 2016,
           <https://tools.ietf.org/html/draft-chroboczek-babel-
           diversity-routing-01>.

[BABEL-RTT]
           Jonglez, B. and J. Chroboczek, "Delay-based Metric
           Extension for the Babel Routing Protocol", Work in
           Progress, Internet-Draft, draft-ietf-babel-rtt-extension-
           00, 26 April 2019, <https://tools.ietf.org/html/draft-
           ietf-babel-rtt-extension-00>.

[BABEL-SS] Boutier, M. and J. Chroboczek, "Source-Specific Routing in
           Babel", Work in Progress, Internet-Draft, draft-ietf-
           babel-source-specific-07, 28 October 2020,
           <https://tools.ietf.org/html/draft-ietf-babel-source-
           specific-07>.

[DSDV]     Perkins, C. and P. Bhagwat, "Highly dynamic Destination-
           Sequenced Distance-Vector routing (DSDV) for mobile
           computers", ACM SIGCOMM '94: Proceedings of the conference
           on Communications architectures, protocols and
           applications, 234-244, DOI 10.1145/190314.190336, October
           1994, <https://doi.org/10.1145/190314.190336>.

[DUAL]     Garcia Luna Aceves, J. J., "Loop-free routing using
           diffusing computations", IEEE/ACM Transactions on
           Networking, 1:1, DOI 10.1109/90.222913, February 1993,
           <https://doi.org/10.1109/90.222913>.

[EIGRP]    Albrightson, B., Garcia Luna Aceves, J. J., and J. Boyle,
           "EIGRP -- a Fast Routing Protocol Based on Distance
           Vectors", Proc. Networld/Interop 94, 1994.

[ETX]      De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A
           high-throughput path metric for multi-hop wireless
           networks", MobiCom '03: Proceedings of the 9th annual
           international conference on Mobile computing and
           networking, 134-146, DOI 10.1145/938985.939000, September
           2003, <https://doi.org/10.1145/938985.939000>.

[IEEE802.11]
           IEEE, "IEEE Standard for Information technology--
           Telecommunications and information exchange between
           systems Local and metropolitan area networks--Specific
           requirements Part 11: Wireless LAN Medium Access Control
           (MAC) and Physical Layer (PHY) Specifications",
           IEEE 802.11-2012, DOI 10.1109/ieeestd.2012.6178212, April
           2012, <https://doi.org/10.1109/ieeestd.2012.6178212>.

[IEN137]   Cohen, D., "On Holy Wars and a Plea for Peace", IEN 137, 1
           April 1980.

[IS-IS]    International Organization for Standardization,
           "Information technology -- Telecommunications and
           information exchange between systems -- Intermediate
           System to Intermediate System intra-domain routeing
           information exchange protocol for use in conjunction with
           the protocol for providing the connectionless-mode network
           service (ISO 8473)", ISO/IEC 10589:2002, 2002.

[JITTER]   Floyd, S. and V. Jacobson, "The Synchronization of
           Periodic Routing Messages", IEEE/ACM Transactions on
           Networking, 2, 2, 122-136, DOI 10.1109/90.298431, April
           1994, <https://doi.org/10.1109/90.298431>.

[OSPF]     Moy, J., "OSPF Version 2", STD 54, RFC 2328,
           DOI 10.17487/RFC2328, April 1998,
           <https://www.rfc-editor.org/info/rfc2328>.

[PACKETBB] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
           "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
           Format", RFC 5444, DOI 10.17487/RFC5444, February 2009,
           <https://www.rfc-editor.org/info/rfc5444>.

[RFC2675]  Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms",
           RFC 2675, DOI 10.17487/RFC2675, August 1999,
           <https://www.rfc-editor.org/info/rfc2675>.

[RFC3561]  Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
           Demand Distance Vector (AODV) Routing", RFC 3561,
           DOI 10.17487/RFC3561, July 2003,
           <https://www.rfc-editor.org/info/rfc3561>.

[RFC6126]  Chroboczek, J., "The Babel Routing Protocol", RFC 6126,
           DOI 10.17487/RFC6126, April 2011,
           <https://www.rfc-editor.org/info/rfc6126>.

[RFC7298]  Ovsienko, D., "Babel Hashed Message Authentication Code
           (HMAC) Cryptographic Authentication", RFC 7298,
           DOI 10.17487/RFC7298, July 2014,
           <https://www.rfc-editor.org/info/rfc7298>.

[RFC7557]  Chroboczek, J., "Extension Mechanism for the Babel Routing
           Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015,
           <https://www.rfc-editor.org/info/rfc7557>.

[RFC8968]  Décimo, A., Schinazi, D., and J. Chroboczek, "Babel
           Routing Protocol over Datagram Transport Layer Security",
           RFC 8968, DOI 10.17487/RFC8968, January 2021,
           <https://www.rfc-editor.org/info/rfc8968>.

[RIP]      Malkin, G., "RIP Version 2", STD 56, RFC 2453,
           DOI 10.17487/RFC2453, November 1998,
           <https://www.rfc-editor.org/info/rfc2453>.

Appendix A. Cost and Metric Computation 💖

okay so how you work out link costs and route metrics is basically your call 🎀 Babel only cares that you follow the conditions in Section 3.4.3 and Section 3.5.2. Different nodes can use different strategies in the same network, and even different strategies on different interface types. This appendix just lists a few strategies that have been found to work well in real networks ✨

the quick version: every node keeps stats on the last 16 received Hello TLVs of each kind (Appendix A.1). It computes costs with the 2-out-of-3 strategy (Appendix A.2.1) on wired links and Expected Transmission Cost (ETX) (Appendix A.2.2) on wireless links. And it uses an additive algebra for metric computation (Section 3.5.2) 🧮💅

A.1. Maintaining Hello History 📜

for each neighbour, a node keeps two sets of Hello history, one for each kind of Hello, plus an expected sequence number, one for Multicast and one for Unicast Hellos. Each Hello history is a vector of 16 bits, where a 1 means a Hello was received and a 0 means one was missed. For each kind of Hello, the expected sequence number, written ne, is the sequence number the next received Hello from that neighbour is expected to carry 🫶

whenever a node gets a Hello packet of a given kind from a neighbour, it compares the received sequence number nr for that kind with its expected sequence number ne. Depending on how that comparison goes, one of these happens:

if the two differ by more than 16 (modulo 2^(16)), then the sending node has probably rebooted and lost its sequence number 💀; the whole associated neighbour table entry gets flushed and a brand new one gets made;
otherwise, if the received nr is smaller (modulo 2^(16)) than the expected ne, then the sending node has increased its Hello interval without us noticing; the receiving node removes the last (ne - nr) entries from this neighbour's Hello history (we "undo history") ⏪;
otherwise, if nr is larger (modulo 2^(16)) than ne, then the sending node has decreased its Hello interval, and some Hellos were lost 😭; the receiving node adds (nr - ne) 0 bits to the Hello history (we "fast-forward") ⏩.

the receiving node then appends a 1 bit to the Hello history and sets ne to (nr + 1) ✨. If the Interval field of the received Hello isn't zero, it resets the neighbour's hello timer to 1.5 times the advertised Interval (that extra margin is there for delay caused by jitter 🌈).

whenever either hello timer tied to a neighbour expires, the local node adds a 0 bit to the matching Hello history and increments the expected Hello number. If both Hello histories are empty (meaning they only contain 0 bits), the neighbour entry gets flushed 🗑️. Otherwise, the relevant hello timer is reset to the value advertised in the last Hello of that kind received from this neighbour. No extra margin is needed here, because jitter was already accounted for when the timeout that just expired was computed 🧠

A.2. Cost Computation 🧮

this section describes two algorithms that are good for computing costs (Section 3.4.3) based on Hello history. Appendix A.2.1 is for wired links and Appendix A.2.2 is for wireless links. RECOMMENDED default values for the parameters in these algorithms are given in Appendix B 🎀

A.2.1. k-out-of-j 🔌

k-out-of-j link sensing is great for wired links, which are either up (where they only occasionally drop a packet) or down (where they drop all packets) 💅

the k-out-of-j strategy takes two small integers, k and j, where 0 < k <= j, plus the nominal link cost, a constant C >= 1. A node keeps a history of the last j Hellos. If k or more of those were correctly received, the link is assumed to be up and the rxcost is set to C. Otherwise, the link is assumed to be down and the rxcost is set to infinity 🙈

since Babel supports two kinds of Hellos, a Babel node runs k-out-of-j twice for each neighbour: once on the Unicast Hello history and once on the Multicast Hello history 👯. If either instance says the link is up, then the link is assumed to be up and the rxcost is set to C. If both instances say it's down, then the link is assumed to be down and the rxcost is set to infinity. In other words, the resulting rxcost is the minimum of the rxcosts yielded by the two instances of k-out-of-j link sensing 🫧

the cost of a link doing k-out-of-j link sensing is defined like this:

cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;
cost = txcost otherwise.

A.2.2. ETX 📡

okay bestie, wired links are totally bimodal: they're either up or down 💡. wireless links are more like a dimmer that keeps shifting 🌸. so if you naively do hop-count routing over wireless transit, it'll pick long, lossy links over shorter, lossless ones 🙈, and throughput can absolutely tank 💀. that's why a routing protocol built for wireless links must do some form of link quality estimation ✨.

the Expected Transmission Cost algorithm, aka ETX [ETX], is a simple link quality estimator that's designed to vibe with the IEEE 802.11 MAC [IEEE802.11] 💅. by default, the 802.11 MAC does ARQ (Automatic Repeat Query) and rate adaptation on unicast frames, but not on multicast frames. multicast frames get sent at a fixed rate with no ARQ, so measuring the loss rate of multicast frames gives you a useful estimate of a link's quality 🎯.

a node doing ETX estimation uses a neighbour's Multicast Hello history to compute an estimate, called beta, of the probability that a Hello TLV gets received successfully 🫶. beta can be the fraction of 1 bits in the small number (say, 6) of most recent entries in that history, or an exponential average, or some combo of both. let rxcost be 256/beta.

let alpha be MIN(1, 256/txcost), an estimate of the probability of successfully sending a Hello TLV. then the cost is computed by:

      cost = 256/(alpha * beta)

or, equivalently:

      cost = (MAX(txcost, 256) * rxcost) / 256.

since the 802.11 MAC does ARQ on unicast frames, unicast frames don't give a useful measure of link quality 🙄. so ETX ignores the Unicast Hello history. that means a node doing ETX won't route through neighbouring nodes unless they send periodic Multicast Hellos (possibly in addition to Unicast Hellos) 🌈.

A.3. Route Selection and Hysteresis 🦋

route selection (Section 3.6) is how a node picks one route out of all the routes it has toward a given destination 🗺️. with Babel, any route selection procedure that only ever chooses feasible routes with a finite metric gives you a set of loop-free routes ✅. but with continuously variable metrics like ETX (Appendix A.2.2), a naive selection procedure might lead to persistent oscillations 😵‍💫. those can be limited or avoided altogether by adding hysteresis to the selection algorithm, i.e., making selection sensitive to a route's history. any reasonable hysteresis algorithm should yield good results. the one below is simple to implement and has been successfully deployed in a bunch of environments 🍓.

for every route R, in addition to its metric m(R), keep a smoothed version of m(R) written ms(R). we RECOMMEND computing ms(R) as an exponentially smoothed average (see Section 3.7 of [RFC793]) of m(R), with a time constant equal to the Hello interval multiplied by a small number such as 3. if no route to a given destination is selected, then select the route with the smallest metric, ignoring the smoothed metric. if a route R is selected, then switch to a route R' only when both m(R') < m(R) and ms(R') < ms(R).

intuitively, the smoothed metric is a long-term estimate of a route's quality 🧠. the algorithm only switches routes when both the instantaneous and the long-term estimates say switching is worth it. no drama, just vibes 💜.

Appendix B. Protocol Parameters ✨

the choice of time constants is a trade-off between fast detection of mobility events and protocol overhead ⏱️. two instances of Babel running with different time constants will still interoperate, but the worst-case convergence time gets dictated by the slower of the two 🐢.

the Hello interval is the MVP 👑: an outage or a mobility event gets detected within 1.5 to 3.5 Hello intervals. because Babel uses a redundant route table and relies on triggered updates and explicit requests, the Update interval has little influence on how long reconvergence takes after an outage. in practice, it mostly matters for how fast new routes get acquired after a mobility event 🦋. the protocol allows intervals as low as 10 ms, but values that low would cause a ton of protocol traffic for very little practical benefit 🙅‍♀️.

the following values have been found to work well in a variety of environments, so they're RECOMMENDED default values 🎀:

Multicast Hello interval:  4 seconds.

Unicast Hello interval:  infinite (no Unicast Hellos are sent).

Link cost:  estimated using ETX on wireless links; 2-out-of-3 with
          C=96 on wired links.

IHU interval:  the advertised IHU interval is always 3 times the
          Multicast Hello interval.  IHUs are actually sent with each
          Hello on lossy links (as determined from the Hello
          history), but only with every third Multicast Hello on
          lossless links.

Update interval:  4 times the Multicast Hello interval.

IHU Hold time:  3.5 times the advertised IHU interval.

Route Expiry time:  3.5 times the advertised update interval.

Request timeout:  initially 2 seconds, doubled every time a request
          is resent, up to a maximum of three times.

Urgent timeout:  0.2 seconds.

Source GC time:  3 minutes.

Appendix C. Route Filtering 🧹

route filtering is when an instance of a routing protocol either discards some of the routes its neighbours announce, or learns them with a metric higher than what you'd expect 🙃. like all distance-vector protocols, Babel can apply arbitrary filtering to the routes it learns, and implementations applying different filtering rules will still interoperate without causing routing loops 🔁. this works because of the latitude in Section 3.5.2: Babel can use any metric that is strictly monotonic, including one that assigns an infinite metric to a selected subset of routes. (see also Section 3.8.1, where requests for nonexistent routes get treated the same way as requests for routes with infinite metric.)

it is not in general correct to learn a route with a metric smaller than the one it was announced with, or to replace a route's destination prefix with a more specific (longer) one. doing either of these may cause persistent routing loops 🌀.

route filtering is a super useful tool, since it allows fine-grained tuning of routing decisions. so some implementations of Babel ship a rich configuration language that lets you apply filtering to sets of routes defined by, for example, incoming interface and destination prefix 💁‍♀️.

to limit the consequences of misconfiguration, Babel implementations provide a reasonable set of default filtering rules even when they don't allow the user to configure filtering. at a minimum, they discard routes with a destination prefix in fe80::/64, ff00::/8, 127.0.0.1/32, 0.0.0.0/32, and 224.0.0.0/8 🛡️.

Appendix D. Considerations for Protocol Extensions 🧩

Babel is an extensible protocol, and this document defines a number of mechanisms you can use to extend it in a backwards compatible manner 🌈:

increasing the version number in the packet header;
defining new TLVs;
defining new sub-TLVs (with or without the mandatory bit set);
defining new AEs;
using the packet trailer.

this appendix is here to guide designers of protocol extensions in choosing a particular encoding 🧭.

the version number in the Babel header should only be increased if the new version is not backwards compatible with the original protocol.

in lots of cases, an extension could be implemented either by defining a new TLV or by adding a new sub-TLV to an existing TLV. for example, an extension whose purpose is to attach extra data to route updates could be done as a new "enriched" Update TLV, by adding a nonmandatory sub-TLV to the Update TLV, or by adding a mandatory sub-TLV 🎁.

the different encodings get treated differently by implementations that don't understand the extension 👀. with a new TLV, or a sub-TLV with the mandatory bit set, the whole TLV is ignored by implementations that don't implement the extension. with a nonmandatory sub-TLV, the TLV is parsed and acted upon, and only the unknown sub-TLV is silently ignored. so a nonmandatory sub-TLV should be used by extensions that extend the Update in a compatible manner (the extension data may be silently ignored), while a mandatory sub-TLV or a new TLV must be used by extensions that make incompatible extensions to the meaning of the TLV (the whole TLV must be thrown away if the extension data is not understood) 💀.

experience shows that the need for additional data tends to crop up in the most unexpected places 😭. hence, it is recommended that extensions defining new TLVs make them self-terminating and allow attaching sub-TLVs to them ✨.

adding a new AE is basically equivalent to adding a new TLV: Update TLVs with an unknown AE are ignored, just like unknown TLVs. however, it's more involved than adding a new TLV, since it creates a new set of compression state. also, since the Next Hop TLV creates state specific to a given address family (as opposed to a given AE), a new AE for a previously defined address family must not be used in the Next Hop TLV if backwards compatibility is required. a similar issue arises with Update TLVs with unknown AEs establishing a new router-id (due to the Router-Id flag being set). therefore, defining new AEs must be done with care if compatibility with unextended implementations is required 🫣.

the packet trailer is intended to carry cryptographic signatures that only cover the packet body. storing the signatures in the packet trailer avoids clearing the signature before computing a hash of the packet body, and makes it possible to check a cryptographic signature before running the full, stateful TLV parser 🔐. hence, only TLVs that don't need to be protected by cryptographic security protocols should be allowed in the packet trailer. any such TLVs should be easy to parse and, in particular, should not require stateful parsing 🎀.

Appendix E. Stub Implementations 🧚

okay so Babel is giving very economical 💅 Updates take between 12 and 40 octets per destination, depending on the address family and how successful compression is. In a dual-stack flat network, an average of less than 24 octets per update is typical. The route table occupies about 35 octets per IPv6 entry. To put that in perspective, a single full-size Ethernet frame can carry some 65 route updates, and a megabyte of memory can hold a 20,000-entry route table and the associated source table. 🤯

Babel is also reasonably simple 🎀 One complete implementation is less than 12,000 lines of C code, and it compiles to less than 120 KB of text on a 32-bit CISC architecture. About half of that figure is protocol extensions and user-interface code, so the core is even slimmer 🦋

Nonetheless, in some very constrained environments, like PDAs, microwave ovens, or abacuses, it may be desirable to have subset implementations of the protocol 🍓

There are lots of definitions of a stub router, but for this section, a stub implementation of Babel is one that announces one or more directly attached prefixes into a Babel network. It doesn't re-announce any routes it has learnt from its neighbours, and it always prefers the direct route to a directly attached prefix over a route learnt over the Babel protocol, even when the prefixes are the same. It may either maintain a full routing table or simply select a default gateway through any one of its neighbours that announces a default route. Since a stub implementation never forwards packets except from or to a directly attached link, it cannot possibly participate in a routing loop. So it need not evaluate the feasibility condition or maintain a source table. Lowkey genius, honestly 🧠✨

No matter how primitive, a stub implementation MUST parse sub-TLVs attached to any TLVs that it understands, and it MUST check the mandatory bit. It MUST answer acknowledgment requests and MUST participate in the Hello/IHU protocol. It MUST also be able to reply to seqno requests for routes that it announces, and it SHOULD be able to reply to route requests. These are the non-negotiables, bestie 🫶

Experience shows that an IPv6-only stub implementation of Babel can be written in less than 1,000 lines of C code and compile to 13 KB of text on a 32-bit CISC architecture. Tiny but mighty 💖

Appendix F. Compatibility with Previous Versions 🦋

The protocol defined in this document is a successor to the protocol defined in [RFC6126] and [RFC7557]. The two protocols are not entirely compatible, but the new protocol was designed so that it can be deployed in existing RFC 6126 networks without needing a flag day. Smooth transition era 😌

There are three optional features that make this protocol incompatible with its predecessor. First of all, RFC 6126 did not define Unicast Hellos (Section 3.4.1). An implementation of RFC 6126 will misinterpret a Unicast Hello for a Multicast one. Since the sequence number space of Unicast Hellos is distinct from the sequence number space of Multicast Hellos, sending a Unicast Hello to an implementation of RFC 6126 will confuse its link quality estimator 🙈 Second, RFC 6126 did not define unscheduled Hellos, and an implementation of RFC 6126 will mis-parse Hellos with an interval equal to 0. Finally, RFC 7557 did not define mandatory sub-TLVs (Section 4.4). So an implementation of RFCs 6126 and 7557 will not correctly ignore a TLV that carries an unknown mandatory sub-TLV. Depending on the sub-TLV, this might cause routing pathologies 💀

An implementation of this specification that never sends Unicast or unscheduled Hellos, and doesn't implement any extensions that use mandatory sub-TLVs, is safe to deploy in a network where some nodes implement the protocol described in RFCs 6126 and 7557. Green flag 🌈

Two changes need to be made to an implementation of RFCs 6126 and 7557 so that it can safely interoperate in all cases with implementations of this protocol. First, it needs to be modified to either ignore or process Unicast and unscheduled Hellos. Second, it needs to be modified to parse sub-TLVs of all the TLVs that it understands and that allow sub-TLVs, and to ignore the TLV if an unknown mandatory sub-TLV is found. It is not necessary to parse unknown TLVs, since these are ignored in any case 🧚

There are other changes too, but none of them are the kind that prevent interoperability:

the conditions on route acquisition (Section 3.5.3) have been relaxed;
route selection should no longer use the route's sequence number (Section 3.6);
the format of the packet trailer has been defined (Section 4.2);
router-ids with a value of all-zeros or all-ones have been forbidden (Section 4.1.3);
the compression state is now specific to an address family rather than an address encoding (Section 4.5);
packet pacing is now RECOMMENDED (Section 3.1).

Acknowledgments 💜

A number of people have contributed text and ideas to this specification. The authors are particularly indebted to Matthieu Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke Høiland-Jørgensen, Benjamin Kaduk, Joao Sobrinho, and Martin Vigoureux 🫶 The previous version of this specification [RFC6126] greatly benefited from the input of Joel Halpern. And the address compression technique was inspired by [PACKETBB]. Everyone involved is a whole vibe ✨

Authors' Addresses 🌸

Juliusz Chroboczek
IRIF, University of Paris-Diderot
Case 7014
75205 Paris CEDEX 13
France

Email: jch@irif.fr


David Schinazi
Google LLC
1600 Amphitheatre Parkway
Mountain View, California 94043
United States of America

Email: dschinazi.ietf@gmail.com

📦 where this page comes from

ietf: rfc8966 2021-01
💖 girlified by claude-haiku-5-5 on 2026-10-18: a language model's rewrite of the original, under its terms