RFC 6126
The Babel Routing Protocol
RFC 6126: The Babel Routing Protocol 🦋
Okay bestie, so this is RFC 6126, and it's called The Babel Routing Protocol ✨. It's an Independent Submission by J. Chroboczek from PPS, University of Paris 7. It's in the Experimental category, dated April 2011, with ISSN 2070-1721. The header doesn't list anything it obsoletes or updates, so no drama there 💅.
Abstract 💜
Babel is a loop-avoiding distance-vector routing protocol that's robust and efficient in ordinary wired networks and in wireless mesh networks 🌸.
Status of This Memo 📜
Not gonna lie, this one isn't an Internet Standards Track spec. It's out here for examination, experimental implementation, and evaluation 🔬. It defines an Experimental Protocol for the Internet community. It's a contribution to the RFC Series, independent of any other RFC stream. The RFC Editor chose to publish it at their discretion and makes no statement about its value for implementation or deployment. Docs the RFC Editor approves for publication aren't a candidate for any level of Internet Standard, see Section 2 of RFC 5741 🙈.
Info about the current status, any errata, and how to give feedback lives at http://www.rfc-editor.org/info/rfc6126 ✨.
Copyright Notice ©️
Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, because they describe your rights and restrictions with respect to this document 🫶.
Table of Contents 🗺️
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Specification of Requirements . . . . . . . . . . . . . . 4
2. Conceptual Description of the Protocol . . . . . . . . . . . . 4
2.1. Costs, Metrics, and Neighbourship . . . . . . . . . . . . 5
2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . . 5
2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6
2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . . 6
2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . . 10
2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . . 11
3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 11
3.1. Message Transmission and Reception . . . . . . . . . . . . 11
3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12
3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . . 15
3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 15
3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 17
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22
3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 27
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . . 30
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39
6. Security Considerations . . . . . . . . . . . . . . . . . . . 39
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.1. Normative References . . . . . . . . . . . . . . . . . . . 40
7.2. Informative References . . . . . . . . . . . . . . . . . . 40
Appendix A. Cost and Metric Computation . . . . . . . . . . . . . 41
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 41
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . . 42
A.3. Metric Computation . . . . . . . . . . . . . . . . . . . . 43
Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . . 43
Appendix C. Simplified Implementations . . . . . . . . . . . . . 44
Appendix D. Software Availability . . . . . . . . . . . . . . . . 451. Introduction ✨
Babel is a loop-avoiding distance-vector routing protocol, and it's built to be robust and efficient in both prefix-based routing networks and flat routing networks ("mesh networks") 🕸️. It works in relatively stable wired networks and in highly dynamic wireless networks, so it's super versatile, periodt 💖.
1.1. Features
Here's the main thing that makes Babel slay in unstable networks 💅. Naive distance-vector protocols [RIP] are kinda chaotic, but Babel strongly limits how often and how long routing pathologies like routing loops and black-holes happen during reconvergence. Even after a mobility event is detected, a Babel network usually stays loop-free 🧚. Babel then quickly reconverges to a configuration that keeps the network loop-free and connected, though it's not necessarily optimal. In lots of cases, this needs zero packet exchanges 🤯. Then Babel slowly converges, on a scale of minutes, to an optimal configuration. The trick behind all this is sequenced routes, a technique pioneered by Destination-Sequenced Distance-Vector routing [DSDV] 👑.
More precisely, Babel has these properties:
- when every prefix is originated by at most one router, Babel never suffers from routing loops;
- when a prefix is originated by multiple routers, Babel may occasionally create a transient routing loop for that particular prefix. This loop disappears in a time proportional to its diameter, and never again (up to an arbitrary garbage-collection (GC) time) will the routers involved participate in a routing loop for the same prefix 🔄;
- assuming reasonable packet loss rates, any routing black-holes that may appear after a mobility event are corrected in a time at most proportional to the network's diameter 🩹.
Babel also has provisions for link quality estimation and for pretty much arbitrary metrics 📊. When it's configured suitably, Babel can implement shortest-path routing, or it may use a metric based on something like measured packet loss.
Babel nodes will successfully establish an association even when they're configured with different parameters 🫂. For example, a mobile node that's low on battery may choose larger time constants (hello and update intervals, etc.) than a node that has access to wall power 🔋. On the flip side, a node that detects high levels of mobility may choose smaller time constants. Being able to build these heterogeneous networks is what makes Babel especially adapted to the wireless environment, iykyk 🌈.
Last but not least, Babel is a hybrid routing protocol, meaning it can carry routes for multiple network-layer protocols (IPv4 and IPv6), whichever protocol the Babel packets are themselves being carried over 🌍.
1.2. Limitations
Babel has two limitations that make it unsuitable for some environments, so let's be real about that 🥺. First, Babel relies on periodic routing table updates instead of a reliable transport. So in large, stable networks, it generates more traffic than protocols that only send updates when the topology changes. In those networks, protocols like OSPF [OSPF], IS-IS [IS-IS], or the Enhanced Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be a better fit 💼.
Second, Babel does impose a hold time when a prefix is retracted (Section 3.5.5) ⏳. That 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 if a previously deaggregated prefix becomes aggregated, it'll be unreachable for a few minutes 😭. This is why Babel is unsuitable for mobile networks that implement automatic prefix aggregation.
1.3. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] 📖.
2. Conceptual Description of the Protocol 🧠
Babel is a mostly loop-free distance vector protocol. It's based on Bellman-Ford, just like the venerable RIP [RIP], but it adds a bunch of refinements that either stop loops from forming at all, or make sure a loop disappears quickly and doesn't come back 🔁.
Conceptually, Bellman-Ford runs in parallel for every source of routing information (destination of data traffic). In this discussion, we fix a source S. Just remember the same algorithm runs for all sources 🫶.
2.1. Costs, Metrics, and Neighbourship
Like many routing algorithms, Babel computes costs of links between any two neighbouring nodes. These are abstract values attached to the edges between two nodes. We write C(A, B) for the cost of the edge from node A to node B 💸.
Given a route between any two nodes, the metric of the route is the sum of the costs of all the edges along the route. The goal of the routing algorithm is to compute, for every source S, the tree of the routes with the lowest metric to S 🌳.
Costs and metrics don't need to be integers! In general, they can be values in any algebra that satisfies two fairly general conditions (Section 3.5.2) 🤓.
A Babel node periodically broadcasts Hello messages to all of its neighbours. It also periodically sends an IHU ("I Heard You") message to every neighbour it has recently heard a Hello from 👋. From the information derived from Hello and IHU messages received from its neighbour B, a node A computes the cost C(A, B) of the link from A to B. Main character energy 👑.
2.2. The Bellman-Ford Algorithm
Every node A keeps track of two pieces of data. One is its estimated distance to S, written D(A). The other is its next-hop router to S, written NH(A) 📍. Initially, 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. This is a message containing D(B) 📣. When a neighbour A of B receives the route update, it checks whether B is its selected next hop. If that's the case, then NH(A) is set to B, and D(A) is set to C(A, B) + D(B). If that's not the case, then A compares C(A, B) + D(B) to its current value of D(A). If that value is smaller, meaning the received update advertises a route that's better than the currently selected route, then NH(A) is set to B, and D(A) is set to C(A, B) + D(B) 🏆.
There are a few refinements to this algorithm, and Babel uses them 🛠️. In particular, convergence speed may increase by sending unscheduled "triggered updates" whenever a major change in the topology is detected, in addition to the regular, scheduled updates ⚡. Also, a node may maintain a number of alternate routes, which are being advertised by neighbours other than its selected neighbour. These can be used immediately if the selected route were to fail 🦋.
2.3. Transient Loops in Bellman-Ford 🌀
okay so it's well known that just naively slapping Bellman-Ford onto distributed routing can cause transient loops after a topology change 😭 picture this:
B
1 /|
1 / |
S --- A |1
\ |
1 \|
CAfter convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.
Now suppose the link between S and A fails:
B
1 /|
/ |
S A |1
\ |
1 \|
CWhen A detects the failure, it switches its next hop to B (which is still advertising a route to S with metric 2), advertises a metric equal to 3, and then advertises a new route with metric 3. This keeps going, with nodes swapping selected neighbours and bumping up their metric, until the advertised metric reaches "infinity", a value larger than all the metrics the routing protocol is able to carry. 💀
2.4. Feasibility Conditions 🎀
Bellman-Ford is seriously robust ✨ its convergence properties still hold even when routers delay route acquisition or discard some updates. Babel routers toss received route announcements unless they can prove that accepting them cannot possibly cause a routing loop 🙅
More formally, we define a condition over route announcements called the feasibility condition, which guarantees there are no routing loops whenever all routers ignore route updates that don't satisfy it. Basically this turns Bellman-Ford into a whole family of routing algorithms, parameterised by the feasibility condition 🧚
There are lots of possible feasibility conditions. For example, 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 (note that BGP's feasibility condition does not ensure the absence of transitory "micro-loops" during reconvergence).
Another simple one, used in Destination-Sequenced Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand Distance Vector (AODV) routing, comes from this observation: a routing loop can only arise after a router has switched to a route with a larger metric than the route it had previously selected. So you could decide a route is feasible only when its metric at the local node would be no larger than the metric of the currently selected route. In other words, an announcement carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this constraint, the metric at every router is nonincreasing, and this invariant is always preserved: if A has selected B as its successor, then D(B) < D(A), which implies the forwarding graph is loop-free 🔁
Babel uses a slightly more refined feasibility condition, used in 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's easy to see 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), hence D(B) < D(A), and since D(A) <= FD(A), we get D(B) < FD(A).
To see that it's strictly less restrictive, consider the following diagram, where 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
CTo show this feasibility condition still guarantees loop-freedom, recall that at the time A accepts an update from B, the metric D(B) announced by B is no smaller than FD(B). Since it's smaller than FD(A), at that point in time FD(B) < FD(A). This property is preserved when A sends updates, so it remains true at all times, which ensures the forwarding graph has no loops 🌈
2.5. Solving Starvation: Sequencing Routes ⭐
Obviously, the feasibility conditions defined above cause starvation when a router runs out of feasible routes 😩 Consider the following 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
BNow suppose the link between A and S breaks:
A
|
| FD(A) = 1
S |1
\ | D(B) = 2
2 \| FD(B) = 2
BThe only route available from A to S, the one through B, is not feasible: A suffers from a spurious starvation 💔
At this point, the whole network would have to be rebooted to solve the starvation. This is basically what EIGRP does when it performs a global synchronisation of all the routers in the network with the source (the "active" phase of EIGRP) 😵💫
Babel reacts to starvation in a much less drastic way, by using sequenced routes, a technique introduced by DSDV and adopted by AODV ✨ Every route carries a sequence number in addition to a metric. This is a nondecreasing integer that is 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 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)
BAfter S increases its sequence number, and the new one is propagated to B, we have:
A
|
| FD(A) = (137, 1)
S |1
\ | D(B) = (138, 2)
2 \| FD(B) = (138, 2)
Bat which point the route through B becomes feasible again 🦋
Note that while sequence numbers are used for determining feasibility, they are not necessarily used in route selection: a node will normally ignore the sequence number when selecting a route (Section 3.6) 🙈
2.6. Requests 🙋♀️
In DSDV, the sequence number of a source is increased periodically. A route only becomes feasible again after the source increases its sequence number and the new one gets propagated through the network, which may take a significant amount of time 🐢
Babel takes a different approach. When a node detects it's suffering from a potentially spurious starvation, it sends an explicit request to the source for a new sequence number. This request is forwarded hop by hop to the source, with no regard to the feasibility condition. When the source receives the request, it 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 get 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 may 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 above discussion assumes every 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 🌐
Synchronising sequence numbers between distinct routers is problematic, so 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 aren't 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. But 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 diagram, 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' -- ::/0Suppose 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 updates are sent reliably after a router-id change 🛡️
Additionally, after the routers have advertised the two routes, both sources will be in their source tables. This 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 🧚
So far we've assumed all prefixes are disjoint, as is the case in flat ("mesh") routing. In practice, though, prefixes may 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 for example the following configuration:
1 1
::/0 -- A --- B --- CSuppose 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 😱
Babel avoids this pitfall by maintaining an "unreachable" route for a few minutes after a route is retracted. The time for which such a route must be maintained should be the worst-case propagation time of the retraction of the route to C ⏰
3. Protocol Operation ✨
okay bestie, every Babel speaker gets a router-id, which is an arbitrary string of 8 octets that has to be unique across the whole routing domain 🆔 the spec suggests formatting router-ids in modified EUI-64 format [ADDRARCH] 💅 (fun fact from the spec: the encoding is a teeny bit more compact if you assign them the same way IPv6 assigns host IDs 🧚)
3.1. Message Transmission and Reception 📬
Babel packets ride inside the body of a UDP datagram 🎁, and each Babel packet is made of one or more TLVs.
The source address of a Babel packet is always a unicast address, link-local if we're talking IPv6 🔗. Babel packets can go to a well-known (link-local) multicast address (the usual vibe) or to a (link-local) unicast address. In normal operation, a Babel speaker sends both multicast and unicast packets to its neighbours.
Except for Hello TLVs and acknowledgements, every Babel TLV can be sent to a unicast or multicast address, and what it means doesn't change depending on which one it went to. So a Babel speaker doesn't have to figure out the destination address of a packet it receives in order to interpret it 🧠✨
Outgoing TLVs get buffered and SHOULD be sent with a small random delay 🌀 that's the jitter, and it's on purpose for two reasons: it stops multiple Babel speakers across a network from syncing up [JITTER] 🙅 and it lets you bundle several TLVs into one packet 📦.
How much delay and jitter you get depends on whether the packet has any urgent TLVs 🚨 Acknowledgement TLVs MUST be sent before the deadline in the matching request. The particular class of updates in Section 3.7.2 MUST be sent in a timely manner. The particular class of request and update TLVs in Section 3.8.2 SHOULD be sent in a timely manner.
3.2. Data Structures 🗂️
Every Babel speaker keeps a bunch of data structures 💁
3.2.1. Sequence Number 🔢
A node's sequence number is a 16-bit integer that rides along in route updates for routes this node originated. A node bumps 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 bigger seqnos make it less likely that other nodes have feasible alternate routes when their selected routes fail. ngl the logic is iconic.
3.2.2. The Interface Table 🔌
This is the list of interfaces the node speaks Babel on. Each entry holds the interface's Hello seqno, a 16-bit integer that gets sent with every Hello TLV on that interface and is bumped (modulo 2^16) every time a Hello goes out. (Heads up: an interface's Hello seqno has nothing to do with the node's seqno 🙃)
Each entry has two timers: the Hello timer, which governs periodic Hello and IHU packets, and the update timer, which governs periodic route updates ⏰.
3.2.3. The Neighbour Table 👯
The neighbour table is the list of all neighbouring interfaces a Babel packet has been recently received from. It's indexed by (interface, address) pairs, and every entry contains:
- the local node's interface over which this neighbour is reachable;
- the address of the neighbouring interface;
- a history of recently received 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 most recent hellos this neighbour sent were received by the local node;
- the "transmission cost" value from the last IHU packet received from this neighbour, or
FFFFhexadecimal (infinity) if the IHU hold timer for this neighbour has expired; - the neighbour's expected Hello sequence number, an integer modulo
2^16.
Each neighbour entry has two timers: the hello timer, which is initialised from the interval value carried by Hello TLVs, and the IHU timer, which is initialised to a small multiple of the interval carried in IHU TLVs.
The neighbour table is indexed by IP addresses, not router-ids, because neighbourship is a relationship between interfaces, not between nodes 🧩 So two nodes with multiple interfaces can be in multiple neighbourship relationships at once, which is pretty common with wireless nodes that have multiple radios 📡
3.2.4. The Source Table 🗃️
The source table records feasibility distances. It's indexed by (prefix, plen, router-id) triples, and every entry contains:
- the prefix (prefix, plen), where plen is the prefix length, 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 entry, the source garbage-collection timer. It's initialised to a time on the order of minutes and reset as specified in Section 3.7.3 ⏳
3.2.5. The Route Table 🛣️
The route table holds the routes this node knows about. It's indexed by (prefix, plen, neighbour) triples, and every entry contains:
- the source (prefix, plen, router-id) for which this route is advertised;
- the neighbour that advertised this route;
- the metric with which this route was advertised by the neighbour, or
FFFFhexadecimal (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 entry has one timer, the route expiry timer, which is initialised and reset as specified in Section 3.5.4 🕰️
3.2.6. The Table of Pending Requests 📮
This table lists the seqno requests the local node has sent (either originated locally or forwarded) that haven't been answered yet. It's indexed by prefixes, and every entry contains:
- the prefix, 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 request has one timer, and it governs both the resending of requests and their expiry ⏲️
3.3. Acknowledged Packets 🤝
A Babel speaker may ask any neighbour that receives a given packet to reply with an explicit acknowledgement within a given time. Using acknowledgement requests is optional, but every Babel speaker MUST be able to reply to such a request.
An acknowledgement MUST be sent to a unicast destination. Acknowledgement requests, on the other hand, can go to unicast or multicast destinations, and in the multicast case they request an acknowledgement from all of the receiving nodes.
When to request acknowledgements is a matter of local policy 🧭 The simplest strategy is to never request them and to rely on periodic updates to eventually get any reachable routes spread throughout the routing domain. For more efficiency, the spec suggests using acknowledged packets to send urgent updates (Section 3.7.2) when the number of neighbours on a given interface is small. Since Babel is designed to deal gracefully with packet loss on unreliable media, sending every packet with an acknowledgement request isn't necessary, and it's not even recommended, because the acknowledgements add traffic and may force extra Address Resolution Protocol (ARP) or Neighbour Discovery exchanges 🙅
3.4. Neighbour Acquisition 👋
Neighbour acquisition is the process where a Babel node discovers the set of neighbours it hears over each of its interfaces and checks that bidirectional reachability is actually there. On unreliable media, it also gives you some statistics that MAY be used in link quality computation 📊
3.4.1. Reverse Reachability Detection 🔁
Every Babel node sends periodic Hellos over each of its interfaces. Each Hello TLV carries an increasing (modulo 2^16) sequence number and the interval between successive periodic packets sent on that particular interface.
Besides the periodic Hellos, a node MAY send unscheduled Hello packets, e.g., to speed up link cost estimation when a new neighbour is discovered, or when link conditions have suddenly changed ⚡
A node MAY change its Hello interval. The Hello interval MAY be decreased at any time; it SHOULD NOT be increased, except immediately before sending a Hello packet. (Equivalently, a node SHOULD send an unscheduled Hello immediately after increasing its Hello interval.)
How you deal with received Hello TLVs and which statistics you keep are local implementation matters. Typically a node keeps some sort of history of recently received Hellos. A possible algorithm is described in Appendix A.1 📚
After receiving a Hello, or determining that 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 in order to reduce the amount of routing traffic in dense networks; in particular, they SHOULD be sent less often than Hellos over links with little packet loss. While IHUs are conceptually unicast, they SHOULD be sent to a multicast address in order to avoid an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs in a single packet.
In addition to the periodic IHUs, a node MAY, at any time, send an unscheduled IHU packet. It MAY also, at any time, decrease its IHU interval, and it MAY increase its IHU interval immediately before sending an IHU.
Every IHU TLV contains two pieces of data: the link's rxcost (reception cost) from the sender's perspective, which the neighbour uses to compute link costs (Section 3.4.3), and the interval between periodic IHU packets. A node that receives an IHU updates the sending neighbour's txcost (transmission cost), from its perspective, to the value contained in the IHU, and resets this neighbour's IHU timer to a small multiple of the value received in the IHU.
When a neighbour's IHU timer expires, its txcost is set to infinity ♾️
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 ✨
okay bestie, so a link's cost is built from stuff already sitting in the neighbour table 🧠 we've got the statistics about which Hellos we've been receiving, plus the txcost we work out from received IHU packets 💌
every neighbour gets its own rxcost from the node that's computing it 🦋 usually it comes from that neighbour's Hello history, but it can be mixed with other data too, like stats the link layer keeps. then the rxcost gets sent to the neighbour in each IHU, so they know how we're hearing them 💜
how the txcost and rxcost get combined into a link's cost is totally a local policy thing 🎀 babel's correctness only cares about these conditions, and they MUST be satisfied:
- the cost is strictly positive;
- if no hellos were received recently, then the cost is infinite;
- if the txcost is infinite, then the cost is infinite.
ngl the spec doesn't restrict cost computation any further, but not every strategy gives good results 🙈 Appendix A.2 has a few examples that are known to work well in practice, so go check those out 🌸
3.5. Routing Table Maintenance 🌈
3.5. Routing Table Maintenance 🌈
okay here's the big picture 💅 a babel update is a quintuple: (prefix, plen, router-id, seqno, metric). the (prefix, plen) is the prefix being advertised, router-id is the router-id of whoever originated this update, seqno is a nondecreasing (modulo 2^16) integer carrying the originating router's seqno, and metric is the announced metric 🫶
before an update gets accepted, it has to pass the feasibility condition (Section 3.5.1) 🚦 that's what makes sure the route can't create a routing loop 😭 if it fails, the update is either ignored or treated as a retraction, depending on some other conditions (Section 3.5.4). if it passes, then it literally cannot cause a routing loop, so it gets accepted ✨
3.5.1. The Feasibility Condition 🦋
okay this is the core of the whole vibe 👑 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, and any update with a finite metric that's large enough to cause a loop gets thrown out 💀
a feasibility distance is a pair (seqno, metric), where seqno is an integer modulo 2^16 and metric is a positive integer 🍓 distances get compared lexicographically, but the first component is inverted, so we say a distance (seqno, metric) is strictly better than (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 (p, plen, id), a node's feasibility distance for that source is the minimum (using the ordering from above) of the distances of all the finite updates that node has ever sent for the prefix (p, plen) carrying the router-id id 🧚 feasibility distances live in the source table, and the exact procedure is in Section 3.7.3 🌸
a received update is feasible when it's a retraction (its metric is FFFF hexadecimal), or when the advertised distance is strictly better, in the sense we just defined, than the feasibility distance for the matching source 💖 more precisely, a route advertisement carrying the quintuple (prefix, plen, router-id, seqno, metric) is feasible if one of these holds:
- metric is infinite; or
- no entry exists in the source table indexed by
(id, prefix, plen); or - an entry
(prefix, plen, router-id, seqno', metric')exists in the source table, and eitherseqno' < seqnoorseqno = seqno'andmetric < metric'.
hot tip (it's not a tip, it's a fact 💅): the feasibility condition looks at the metric the neighbour advertised, not the route's metric. so if a neighbour's cost fluctuates, that can't make a selected route unfeasible 🙈
3.5.2. Metric Computation 🎀
so a route's metric is computed from the metric the neighbour advertised plus the neighbour's link cost 💜 metric computation is also a local policy matter 🌈 but as far as babel is concerned, the function M(c, m) (used for computing a metric from a locally computed link cost and the metric advertised by a neighbour) MUST only satisfy these conditions:
- if
cis infinite, thenM(c, m)is infinite; Mis strictly monotonic:M(c, m) > m.
on top of that, the metric SHOULD satisfy this one too:
Mis isotonic: ifm <= m', thenM(c, m) <= M(c, m').
ngl strict monotonicity is the important one 😭 persistent routing loops can show up without it. isotonicity is different: if it's not satisfied, babel still converges to a locally optimal routing table, but it might not hit a global optimum (and that global optimum might not even exist) 🦋
same deal as cost computation: not every metric strategy gives good results 🙈 some are more likely than others to cause routing instabilities (route flapping). Appendix A.3 has a bunch of examples of strictly monotonic, isotonic routing metrics that are known to work well in practice 💅
3.5.3. Encoding of Updates 🍓
in a big network, most babel traffic is route updates, so the encoding got some serious care to be efficient 🧁 an Update TLV only holds the prefix, seqno, and metric. the next hop comes either from the network-layer source address of the packet or from an explicit Next Hop TLV in that same packet 🌸 the router-id comes from a separate Router-Id TLV in the same packet, which is optimised for when a bunch of updates share the same router-id ✨
there's also address compression [PACKETBB] 🫶 a prefix of the advertised prefix can be left out of an Update TLV, and then it gets copied from a previous Update TLV in the same packet 💜
and as a special optimisation 👑 when a router-id matches the interface-id part of an IPv6 address, the router-id can optionally be derived from the low-order bits of the advertised prefix 🧚
the full encoding details are in Section 4.4 🎀
3.5.4. Route Acquisition 💖
here's how a babel node handles an incoming update 🦋 when it gets an update (id, prefix, seqno, metric) from a neighbour neigh with a link cost equal to cost, it checks whether it already has a routing table entry indexed by (neigh, id, prefix) 👀
if there's no such entry:
- if the update is unfeasible, it is ignored;
- if the metric is infinite (the update is a retraction), the update is ignored;
- otherwise, a new route table entry gets created, indexed by
(neigh, id, prefix), with seqno equal toseqnoand an advertised metric equal to the metric carried by the update ✨
if such an entry exists:
- if the entry is currently installed and the update is unfeasible, then it depends on whether the router-ids of the two entries match 💀 if they're different, the update is treated as though it were a retraction (i.e., as though the metric were FFFF hexadecimal). if they're equal, the update is ignored;
- otherwise (i.e., if either the update is feasible or the entry is not currently installed), the entry's sequence number, advertised metric, metric, and router-id get updated. and unless the advertised metric is infinite, the route's expiry timer is reset to a small multiple of the Interval value included in the update ⏰
when a route's expiry timer triggers 😭 it depends on whether the route's metric is finite. if it is, the metric gets set to infinity and the expiry timer is reset. if the metric is already infinite, the route gets flushed from the route table 🗑️
after the routing table has been updated, the route selection procedure (Section 3.6) runs 🌈
3.5.5. Hold Time 🌙
okay this one's a little spicy 🌶️ when a prefix p gets retracted, because all its routes are unfeasible, too old, or have an infinite metric, and there's a shorter prefix p' that covers p and is reachable, then p' generally can't be used for routing packets destined to p without risking a routing loop (Section 2.8) 😬
so to avoid that mess 💅 whenever a prefix gets retracted, a routing table entry with infinite metric is maintained as described in Section 3.5.4 above. packets destined for that prefix MUST NOT be forwarded by following a route for a shorter prefix 🙅♀️ that infinite metric entry sticks around until a feasible update supersedes it. if no such update shows up within the route hold time, the entry gets flushed 🧹
3.6. Route Selection 💜
3.6. Route Selection 💜
route selection is how babel picks a single route for a given prefix, to use for forwarding packets and to re-advertise to a node's neighbours 🦋 babel is built to allow flexible route selection policies 🎀 for the protocol's correctness, the route selection policy MUST only satisfy these properties:
- a route with infinite metric (a retracted route) is never selected;
- an unfeasible route is never selected.
heads up though: babel doesn't naturally guarantee routing stability 🙈 and if different routers are running conflicting route selection policies, that can lead to persistent route oscillation 😵💫
defining a good route selection policy for babel is an open research problem 🔬 route selection can juggle multiple mutually contradictory criteria. in roughly decreasing order of importance, they are:
- routes with a small metric should be preferred over routes with a large metric;
- switching router-ids should be avoided;
- routes through stable neighbours should be preferred over routes through unstable ones;
- stable routes should be preferred over unstable ones;
- switching next hops should be avoided.
a simple strategy is to choose the feasible route with the smallest metric, with a small amount of hysteresis applied to avoid switching router-ids 💖
once the route selection procedure has run, triggered updates (Section 3.7.2) and requests (Section 3.8.2) get sent 📨
3.7. Sending Updates 🚀
3.7. Sending Updates 🚀
a Babel speaker advertises its set of selected routes to its neighbours 📣 normally, it does this by sending one or more multicast packets containing Update TLVs on all of its connected interfaces. but on link technologies where multicast is way more expensive than unicast, a node MAY choose to send multiple copies of updates in unicast packets when the number of neighbours is small 🌸
also, to make sure any black-holes get cleared reliably and in a timely manner 🕳️, a Babel node sends 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 (for example, the address of a local interface, the prefix of a directly attached network, or something redistributed from a different routing protocol), then the router-id is set to the local 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 learned from another Babel speaker, the router-id and sequence number are copied from the routing table entry, and the metric is computed as specified in Section 3.5.2 🦋
3.7.1. Periodic Updates 🌸
Every Babel speaker regularly shares all of its selected routes on every interface, including routes it has recently taken back. 💌 Babel never hits routing loops (no "counting to infinity" drama, bestie), and it leans hard on triggered updates (Section 3.7.2), so this full dump only needs to happen every so often. 🫶
3.7.2. Triggered Updates ⚡
Besides the regular updates, a Babel speaker also sends unscheduled, or triggered, updates to let its neighbours know about a big change in the network topology. 🦋
Okay, this part is so important. If the router-id for the selected route to a given prefix changes, that could be the start of a routing loop forming 😭, so a node MUST send a triggered update in a timely manner whenever it changes the selected router-id for a given destination. 🚨 It SHOULD also make a reasonable attempt to make sure that all of its neighbours get that update. 💅
There are two ways to make sure of that. 🎀 If the node has only a few neighbours, it's reasonable to send the update along with an acknowledgement request, and keep resending until every neighbour has acknowledged the packet, up to some number of tries. If the node has lots of neighbours, though, asking every single one for an acknowledgement could make a non-negligible amount of traffic, so it could be nicer to just repeat the update a reasonable number of times (say, 5 for wireless and 2 for wired links). 🧚
Route retractions are a little less scary. 🙈 If a retraction doesn't reach all neighbours, a black-hole might appear, but unlike a routing loop, that doesn't threaten the integrity of the network. 🍓 When a route is retracted, a node SHOULD send a triggered update and SHOULD make a reasonable attempt to make sure all of its neighbours receive that retraction. ✨
Finally, a node MAY send a triggered update when the metric for a given prefix changes significantly, whether that's because of a received update or because a link cost changed. 🔥 A node SHOULD NOT send triggered updates for other reasons, like a tiny wobble in a route's metric, the selected next hop changing, or just to pass along a new sequence number (except to satisfy a request, as specified in Section 3.8). 💀 Main character energy means not spamming updates, periodt. 👑
3.7.3. Maintaining Feasibility Distances 💜
Before a Babel node sends an update (prefix, plen, router-id, seqno, metric) with a finite metric (so, not a route retraction), it updates the feasibility distance kept in the source table. 🧠 Here's how it works, iykyk:
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', thenseqno' := seqno,metric' := metric; - if
seqno = seqno'andmetric' > metric, thenmetric' := metric; - otherwise, nothing needs to be done. 🫧
After that, the garbage-collection timer for the modified entry gets reset. 🔄 Just note that the garbage-collection timer does NOT get reset when a retraction is sent. 🙅♀️
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 technology such as Ethernet, a Babel node SHOULD use an optimisation called split horizon. 🎀 With split horizon turned on for an interface, a routing update is NOT sent out that interface if the advertised route was learnt from a neighbour over that same interface. 🙃
Split horizon SHOULD NOT be applied to an interface unless that interface is known to be symmetric and transitive. 🚫 Especially, split horizon doesn't work for decentralised wireless link technologies (e.g., IEEE 802.11 in ad hoc mode). 📡
3.8. Explicit Route Requests 🫶
Normally, a node's routing table fills up from 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 expiring out of nowhere. 🙏
Babel has two kinds of explicit requests. 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, but seqno requests get forwarded if a neighbour can't satisfy them. 🔁
3.8.1. Handling Requests 🎀
When a node gets a request, it either forwards it or sends an update in reply, as described in the sections below. 💅 If that leads to an update being sent, the update goes either to a multicast address on the interface where the request came in, or to the unicast address of the neighbour that sent the update. 🧚
The exact behaviour is different for route requests and seqno requests. 🦋
3.8.1.1. Route Requests 🌸
When a node receives a route request for a prefix (prefix, plen), it checks its route table for a selected route to that exact prefix. 🔍 If the route exists, the node MUST send an update. 🫡 If it doesn't, the node MUST send a retraction for that prefix. 🙅♀️
When a node receives a wildcard route request, it SHOULD send a full routing table dump. 💖
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 routing table has a selected entry for that prefix. 🕵️♀️ If there's no such entry, or the entry has infinite metric, it ignores the request. 🙈
If a selected route for the given prefix exists, and either the router-ids are different, or the router-ids are equal and the entry's sequence number is no smaller than the requested one, the node MUST send an update for the given prefix. ✅
If the router-ids match but the requested seqno is bigger than the route entry's, the node compares the router-id against its own. 🪞 If it's its own router-id, the node increases its sequence number by 1 and sends an update. 🆙 A node MUST NOT increase its sequence number by more than 1 in response to a route request. 🛑
If the requested router-id is NOT its own, the received request's hop count is 2 or more, and the node has a route (not necessarily a feasible one) for the requested prefix that doesn't use the requestor as a next hop, the node SHOULD forward the request. 🔀 It does this by decreasing the hop count and sending the request in a unicast packet to a neighbour that advertises the given prefix (not necessarily the selected neighbour), as long as that neighbour is different from the one the request came from. 📬
A node SHOULD keep a list of recently forwarded requests and forward the reply in a timely manner. 🗂️ A node SHOULD also compare every incoming request against that list and avoid forwarding it if it's redundant. 🧼
Here's the tea ☕: the request-forwarding mechanism doesn't necessarily obey the feasibility condition, so 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. 🕰️ Since requests are only ever forwarded as unicast packets, the initial hop count doesn't have to be kept particularly low, and an expanding horizon search isn't necessary. 🙌 A request MUST NOT be forwarded to a multicast address, and it MUST be forwarded to a single neighbour only. 🫵
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 (Section 3.8.2.1). 🎯
3.8.2.1. Avoiding Starvation 🥺
When a route is retracted or expires, a Babel node usually switches over to another feasible route for the same prefix. 🔄 But sometimes there just aren't any such routes available. 😩
A node that has lost all feasible routes to a given destination MUST send a seqno request. 🆘 The router-id of the request is set to the router-id of the route it just lost, and the requested seqno is the value in the source table, plus 1. ➕
That request SHOULD be multicast over all of the node's attached interfaces. 📡 Other nodes affected by the route's loss will send similar requests, and neighbouring nodes will forward them up to the source. 🌊 If the network is connected and there's no packet loss, this results in a route being advertised with a new sequence number. 🎉 (Note that, thanks to duplicate suppression, only a small number of these requests will actually reach the source. 🧠)
To make up for packet loss, a node SHOULD repeat such a request a small number of times if no route becomes feasible within a short time. 🔁 Under heavy packet loss, though, all of those requests could get lost. 😭 In that case, the second mechanism in the next section will eventually make sure a new seqno gets received. 🫶
3.8.2.2. Dealing with Unfeasible Updates 🙅♀️
When a route's metric goes up, 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 retract the route. 🫣
To keep routes from spuriously expiring because they've become unfeasible, a node SHOULD send a unicast seqno request whenever it receives an unfeasible update for a route that's currently selected. 🛟 The requested sequence number is computed from the source table, just like above. 🧮
A node SHOULD also send a unicast seqno request whenever it receives an unfeasible update from a currently unselected neighbour that is "good enough", i.e., one that would make the received route selected if it were feasible. 🥇
3.8.2.3. Preventing Routes from Expiring ⏳
Normally, a route's expiry timer should never go off, lol. 🙃 Since a route's hold time is computed from an explicit interval included in Update TLVs, a new update should show up in time to keep the route from expiring. 💕
With packet loss, though, it can happen that no update gets through for a long stretch of time, and then the route expires. 😱 To avoid that spurious expiry, a Babel node SHOULD, shortly before a selected route expires, send a unicast route request to the neighbour that advertised the route. 📩 Since nodes always send retractions in response to non-wildcard route requests (Section 3.8.1.1), this will usually end with either the route being refreshed or a retraction coming in. ✨
3.8.2.4. Acquiring New Neighbours 🤝
To speed up convergence after a mobility event, a node MAY send a unicast wildcard request after acquiring a new neighbour. 🚀 A node MAY also send a small number of multicast wildcard requests shortly after booting. 🥳
4. Protocol Encoding ✨
okay bestie, this is where we get into how Babel packets actually look on the wire 🧚 A Babel packet rides 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 a unicast address, over IPv4 or IPv6. For IPv6, those addresses are link-local. The source and destination UDP ports are both set to a well-known port number 🎀 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. And Babel packets MUST NOT be sent as IPv6 Jumbograms, no exceptions 🙅♀️
Now the size stuff 🌸 We want to send as few packets as possible without triggering lower-layer fragmentation, so a Babel node SHOULD try to make its packets as big as it can, up to the outgoing interface's MTU minus the lower-layer headers (28 octets for UDP/IPv4, 48 octets for UDP/IPv6). A node MUST NOT send packets bigger than the attached interface's MTU (adjusted for lower-layer headers) or 512 octets, whichever is larger, but never more than 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. Receiving has to keep up, bestie 💅
To avoid whole-network synchronisation and to cram lots of TLVs into big packets ✨, a Babel node MUST buffer every TLV and delay sending each UDP packet by a small, randomly chosen delay [JITTER]. And here's the twist: so the packet loss rates can be computed accurately 📊, this delay MUST NOT be larger than half the advertised Hello interval. Iconic restraint 👑
4.1. Data Types
4.1.1. Interval
Relative times are carried as 16-bit values giving a number of centiseconds (hundredths of a second) ⏱️ That gets you times up to roughly 11 minutes, with a granularity of 10 ms. Honestly that should cover all the reasonable stuff Babel gets used for 🦋
4.1.2. Router-Id
A router-id is an arbitrary 8-octet value 🍓 Router-ids SHOULD be assigned in modified EUI-64 format [ADDRARCH]. Very organised, very clean, very much giving neat little labels 🫶
4.1.3. Address
Okay so addresses take up most of the protocol, which is why there are several different ways to encode them 💜 On top of that, a common subnet prefix can be left out when multiple addresses get sent in one packet. That trick is called address compression [PACKETBB]. Main character energy for saving bytes 😭
Here are the address encodings:
- 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. The value is 8 octets long, and a prefix of
fe80::/64is implied.
The address family of an address is either IPv4 or IPv6 🌈 It's undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. Simple, but you gotta keep track 🧚
4.1.4. Prefixes
A network prefix is encoded just like a network address, except it's stored in the smallest number of octets that can hold the significant bits (up to the prefix length) 🌸 Tiny and efficient, bestie 💅
4.2. Packet Format
A Babel packet is a 4-octet header followed by a sequence of TLVs 🎀
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 ...
+-+-+-+-+-+-+-+-+-+-+-+-+-The fields are:
Magic: the arbitrary but carefully picked value 42 (decimal). Packets whose first octet is anything other than 42 MUST be silently ignored 🙈Version: this document describes version 2 of the Babel protocol. Packets whose second octet is anything other than 2 MUST be silently ignored 💀Body length: the length in octets of the body that follows the packet header 📏Body: the packet body, which is a sequence of TLVs 🧁
Any data following the body MUST be silently ignored. Extra stuff at the end? Not our problem 💅
4.3. TLV Format
Except for Pad1, every TLV has the following 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 | Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-The fields are:
Type: the type of the TLV 🍓Length: the length of the body, not counting the Type and Length fields. If the body is longer than the expected length for that TLV type, any extra data MUST be silently ignored 📦Body: the TLV body, and how it gets read depends on the type 🌈
TLVs with an unknown type value MUST be silently ignored 🙅♀️ Not in our bestie circle, not in our protocol 💅
4.4. Details of Specific TLVs
4.4.1. Pad1
0
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
| Type = 0 |
+-+-+-+-+-+-+-+-+The field is:
Type: set to 0 to indicate a Pad1 TLV 🧚
This TLV is silently ignored on reception. Just vibes, no effect 🫶
4.4.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...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-The fields are:
Type: set to 1 to indicate a PadN TLV 💜Length: the length of the body, not counting the Type and Length fields 📏MBZ: set to 0 on transmission 🍓
This TLV is silently ignored on reception. Padding that just chills 🌸
4.4.3. Acknowledgement 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nonce | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+This TLV asks the receiver to send back an Acknowledgement TLV within the number of centiseconds given by the Interval field 🙋♀️
The fields are:
Type: set to 2 to indicate an Acknowledgement Request TLV 💖Length: the length of the body, not counting the Type and Length fields 📏Reserved: sent as 0, and MUST be ignored on reception 🌸Nonce: an arbitrary value that gets echoed back in the receiver's Acknowledgement TLV 🔁Interval: a time interval in centiseconds, after which the sender will assume this packet has been lost. This MUST NOT be 0. The receiver MUST send an acknowledgement before this time has elapsed, with a margin that allows for propagation time ⏳ Gotta be quick, bestie 🏃♀️
4.4.4. Acknowledgement
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 | Nonce |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+A node sends this TLV the moment it gets an Acknowledgement Request 🎀
The fields are:
Type: set to 3 to indicate an Acknowledgement TLV 🧁Length: the length of the body, not counting the Type and Length fields 📏Nonce: set to the Nonce value of the Acknowledgement Request that prompted this Acknowledgement 🔁
Nonce values aren't globally unique, so this TLV MUST be sent to a unicast address. No sending it to the whole neighbourhood 🙅♀️
4.4.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 | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+This TLV handles neighbour discovery and figures out a link's reception cost 👀
The fields are:
Type: set to 4 to indicate a Hello TLV 🌈Length: the length of the body, not counting the Type and Length fields 📏Reserved: sent as 0, and MUST be ignored on reception 🌸Seqno: the sending node's Hello seqno for this interface 🔢Interval: an upper bound, in centiseconds, on how long until the sending node sends a new Hello TLV. This MUST NOT be 0. ⏰
Each node has a single seqno counter for all the Hellos it sends over a given interface. So this TLV MUST be sent to a multicast destination 📣 And to avoid big jumps in link quality 📉, multiple Hello TLVs SHOULD NOT be sent in the same packet. Keep it smooth, bestie ✨
4.4.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...
+-+-+-+-+-+-+-+-+-+-+-+-An IHU ("I Heard You") TLV confirms bidirectional reachability and carries a link's transmission cost 🫶 It's basically a "yes I see you" 💖
The fields are:
Type: set to 5 to indicate an IHU TLV 🦋Length: the length of the body, 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 how long until the sending node sends a new IHU. This MUST NOT be 0. The receiving node uses this value to work out 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 goes to a single neighbour. But IHU TLVs carry an explicit destination address anyway 🧚 It SHOULD be sent to a multicast address, because that lets IHUs for different neighbours get bundled into one packet, and it skips the need for an ARP or Neighbour Discovery exchange when a neighbour isn't being used for data traffic. Efficiency is everything 💅
IHU TLVs with an unknown value in the AE field MUST be silently ignored. Unknown AE? Ghosted 👻
4.4.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 +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+okay so a Router-Id TLV sets up a router-id 🦋 that all the later Update TLVs just inherit. no need to repeat it every time, it's giving efficiency 💅
Fields:
Type: set to 6, which marks it as a Router-Id TLV 🎀Length: the length of the body, 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 the Update TLVs that come after it 👑
4.4.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 is how you set a next-hop address for one address family (IPv4 or IPv6), and the later Update TLVs use it. so cute, right? 🥰
Fields:
Type: set to 7, which marks it as a Next Hop TLV 🍓Length: the length of the body, not counting the Type and Length fields 📏AE: the encoding of the Address field. This SHOULD be 1 or 3 and MUST NOT be 0. ✨Reserved: sent as 0, and MUST be ignored on reception 🌸Next hop: the next-hop address that the later Update TLVs use, for this address family 🦋
when the address family matches the network-layer protocol this packet rides on, you don't need a Next Hop TLV at all! the next hop is just the packet's source address. easy peasy 💖
Next Hop TLVs with an unknown value for the AE field MUST be silently ignored. no drama, just vibes 🙈
4.4.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...
+-+-+-+-+-+-+-+-+-+-+-+-the Update TLV is the main character 👑 it either advertises a route or takes one back. as a bonus it can also set up a new implied router-id and a new default prefix, which is a very smart shortcut ✨
Fields:
Type: set to 8, which marks it as an Update TLV 🎀Length: the length of the body, not counting the Type and Length fields 📏AE: the encoding of the Prefix field 🌈Flags: the individual bits say how this TLV gets special handling (more on that below). Every node MUST be able to interpret the flags with values 80 and 40 hexadecimal, and unknown flags MUST be silently ignored. 🔥Plen: the length of the advertised prefix 🦋Omitted: the number of octets left out at the start of the advertised prefix. Those should be taken from a preceding Update TLV with the flag with value 80 hexadecimal set. 🧚Interval: an upper bound, in centiseconds, on how long the sending node waits before it sends a new update for this prefix. This MUST NOT be 0 and SHOULD NOT be less than 10. The receiving node uses this number to work out a hold time for this routing table entry. The value FFFF hexadecimal (infinity) means this announcement won't be repeated unless somebody asks for it (Section 3.8.2.3). ⏳Seqno: the originator's sequence number for this update 🔢Metric: the sender's metric for this route. The value FFFF hexadecimal (infinity) means this is a route retraction. 💀Prefix: the prefix being advertised. Its size is (Plen/8 - Omitted) rounded upwards. 🌸
The Flags field works like this:
- if the bit with value 80 hexadecimal is set, then this Update establishes a new default prefix for later Update TLVs with a matching address family in the same packet 💜
- if the bit with value 40 hexadecimal is set, then the low-order 8 octets of the advertised prefix establish a new default router-id for this TLV and the later Update TLVs in the same packet 🌈
Here's how the prefix gets built:
- the first Omitted octets come from the previous Update TLV with flag 80 hexadecimal set and the same address family 🧩
- the next (Plen/8 - Omitted) (rounded upwards) octets come from the Prefix field ✨
- the remaining octets are set to 0 🫶
Figuring out the router-id: if the Metric field is finite, the router-id of the originating node for this announcement comes from the low-order 8 octets of the prefix advertised by this Update, but only if the bit with value 40 hexadecimal is set in the Flags field. Otherwise, it comes either from the preceding Router-Id packet, or from the preceding Update packet with flag 40 hexadecimal set, whichever came last. 🔍
Finding the next hop: the next-hop address for this update comes from the last preceding Next Hop TLV with a matching address family in the same packet. If there isn't one, it's taken from the network-layer source address of this packet. 🧭
Retractions: if the Metric field is FFFF hexadecimal, this TLV is a retraction. The current router-id and the Seqno are not used in that case. AE MAY then be 0, and in that case this Update retracts all of the routes previously advertised on this interface. bye bye routes 👋🙈
Update TLVs with an unknown value for the AE field MUST be silently ignored. ignore it and move on, bestie 💅
4.4.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 basically you asking "hey, can I get an update on this prefix?" or "send me your whole table please" 🥺💖
Fields:
Type: set to 9, which marks it as a Route Request TLV 🎀Length: the length of the body, not counting the Type and Length fields 📏AE: the encoding of the Prefix field. The value 0 means this is a request for a full routing table dump, aka a wildcard request. 🌟Plen: the length of the requested prefix 🦋Prefix: the prefix being requested. Its size is Plen/8 rounded upwards. 🧩
so a Route Request TLV tells the receiver to send an update for the prefix given by the AE, Plen, and Prefix fields. if AE is 0, it means a full dump of their routing table instead (and in that case Plen MUST be 0, and Prefix is of length 0). 🍓
a Request can go to a unicast address if it's only for one node, or to a multicast address if it's for all the neighbours of the sending interface 📡
4.4.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 asks the receiver to send an Update for a given prefix with a given sequence number. if they can't do it locally, they pass the request along instead. it's giving teamwork 🫶
Fields:
Type: set to 10 to indicate a Seqno Request message 🎀Length: the length of the body, not counting the Type and Length fields 📏AE: the encoding of the Prefix field. This MUST NOT be 0. 🌈Plen: the length of the requested prefix 🦋Seqno: the sequence number being requested 🔢Hop Count: the maximum number of times this TLV may be forwarded, plus 1. This MUST NOT be 0. 🔁Prefix: the prefix being requested. Its size is Plen/8 rounded upwards. 🧩
a Seqno Request TLV tells the receiving node to send an Update for the prefix given by the AE, Plen, and Prefix fields. The Update should have either a router-id different from the one in the Router-Id field, or a Seqno no less than the one in the Seqno field. If the node can't satisfy this locally, it forwards the request according to the rules in Section 3.8.1.2. 🚀
a Seqno Request MAY be sent to a multicast address. but it MUST NOT be forwarded to a multicast address, and it MUST NOT be forwarded to more than one neighbour. A request MUST NOT be forwarded if its Hop Count field is 1. no infinite loops here, babe 🙅♀️💜
5. IANA Considerations 🌸
IANA has registered the UDP port number 6697, called "babel", for use by the Babel protocol. 🎀
IANA has also registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. 📡
6. Security Considerations 🔒
okay, this part is serious bestie, so listen up 😭
As defined in this document, Babel is a completely insecure protocol. Any attacker can attract data traffic by advertising routes with a low metric. 💀 This particular issue can be solved either by lower-layer security mechanisms (e.g., IPsec or link-layer security), or by appending a cryptographic key to Babel packets. The provision of ignoring any data contained within a Babel packet beyond the body length declared by the header is designed for just such a purpose. 🔐
The information that a Babel node announces to the whole routing domain is often enough to figure out a mobile node's physical location with reasonable precision. 📍😱 The privacy issues this causes can be eased somewhat by using randomly chosen router-ids and randomly chosen IP addresses, and by changing them periodically. 🦋🌈
When carried over IPv6, Babel packets are ignored unless they're sent from a link-local IPv6 address. Routers don't forward link-local IPv6 packets, so this protects against spoofed Babel packets coming in from the global Internet. 🛡️ No such natural protection exists when Babel packets are carried over IPv4. 🙈
7. References 📚
The reference list wasn't included in this part of the text, so there's nothing to list here yet. 🧚
7.1. Normative References 📚✨
okay so these are the must-read docs bestie, the ones the spec leans on so hard you can't skip them 💅
[ADDRARCH]Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, February 2006.[RFC2119]Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
7.2. Informative References 🦋
these are the extra reading if you wanna go down the rabbit hole, totally optional but lowkey iconic 🌸
[DSDV]Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers", ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications 234-244, 1994.[DUAL]Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing Computations", IEEE/ACM Transactions on Networking 1:1, February 1993.[EIGRP]Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, "EIGRP -- a Fast Routing Protocol Based on Distance Vectors", Proc. Interop 94, 1994.[ETX]De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A high-throughput path metric for multi-hop wireless networks", Proc. MobiCom 2003, 2003.[IS-IS]"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.[JITTER]Floyd, S. and V. Jacobson, "The synchronization of periodic routing messages", IEEE/ACM Transactions on Networking 2, 2, 122-136, April 1994.[OSPF]Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.[PACKETBB]Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009.[RIP]Malkin, G., "RIP Version 2", STD 56, RFC 2453, November 1998.
Appendix A. Cost and Metric Computation 🧮💜
okay so how links get their costs and routes get their metrics is totally a local decision, babe. Babel only cares that it follows the rules in Sections 3.4.3 and 3.5.2 🫶 Different nodes MAY use different strategies in one network, and MAY even switch strategies between interface types. Here are a few examples to vibe with ✨
The sample implementation of Babel keeps stats on the last 16 received Hello TLVs (Appendix A.1), uses the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and uses ETX [ETX] on wireless links. For metric math it's got an additive algebra (Appendix A.3.1). Iconic behaviour 👑
A.1. Maintaining Hello History 🗂️
so each neighbour gets its own Hello history and an expected sequence number. The history is a vector of 16 bits: a 1 means a Hello came in, a 0 means one got missed. The expected sequence number, written ne, is what the next Hello from that neighbour should be carrying.
Whenever a node gets a Hello packet, it compares the received sequence number nr with ne, and then 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 associated neighbour table entry is flushed;
- otherwise, if the received
nris smaller (modulo 2^16) than the expected sequence numberne, then the sending node has increased its Hello interval without our noticing; the receiving node removes the last (ne - nr) entries from this neighbour's Hello history (we "undo history"); - otherwise, if
nris larger (modulo 2^16) thanne, 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").
Then the receiving node appends a 1 bit to the neighbour's Hello history, resets the neighbour's Hello timer, and sets ne to (nr + 1). It then resets the neighbour's Hello timer to 1.5 times the value advertised in the received Hello (the extra margin allows for the delay due to jitter). 🕰️
Whenever the Hello timer for a neighbour expires, the local node adds a 0 bit to this neighbour's Hello history and increments the expected Hello number. If the Hello history is empty (it contains 0 bits only), the neighbour entry is flushed; otherwise, it resets the neighbour's Hello timer to the value advertised in the last Hello received from this neighbour (no extra margin is necessary in this case).
A.2. Cost Computation 💸
A.2.1. k-out-of-j 🔌
K-out-of-j link sensing is suitable for wired links that are either up, in which case they only occasionally drop a packet, or down, in which case they drop all packets.
The k-out-of-j strategy is parameterised by two small integers k and j, such that 0 < k <= j, and the nominal link cost, a constant K >= 1. A node keeps a history of the last j hellos; if k or more of those have been correctly received, the link is assumed to be up, and the rxcost is set to K; otherwise, the link is assumed to be down, and the rxcost is set to infinity.
The cost of such a link is defined as:
cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;cost = txcost otherwise.
A.2.2. ETX 📡
The Estimated Transmission Cost metric [ETX] estimates the number of times that a unicast frame will be retransmitted by the IEEE 802.11 MAC, assuming infinite persistence.
A node uses a neighbour's Hello history to compute an estimate, written beta, of the probability that a Hello TLV is successfully received. The rxcost is defined as:
256/betaLet alpha be MIN(1, 256/txcost), an estimate of the probability of successfully sending a Hello TLV. The cost is then computed by:
cost = 256/(alpha * beta)or, equivalently:
cost = (MAX(txcost, 256) * rxcost) / 256A.3. Metric Computation 🧠
A.3.1. Additive Metrics ➕
The simplest approach for obtaining a monotonic, isotonic metric is to define the metric of a route as the sum of the costs of the component links. More formally, if a neighbour advertises a route with metric m over a link with cost c, then the resulting route has metric M(c, m) = c + m.
A multiplicative metric can be converted to an additive one by taking the logarithm (in some suitable base) of the link costs.
A.3.2. External Sources of Willingness 🔋
A node may want to vary its willingness to forward packets by taking into account information that is external to the Babel protocol, such as the monetary cost of a link, the node's battery status, CPU load, etc. This can be done by adding to every route's metric a value k that depends on the external data. For example, if a battery-powered node receives an update with metric m over a link with cost c, it might compute a metric M(c, m) = k + c + m, where k depends on the battery status.
In order to preserve strict monotonicity (Section 3.5.2), the value k must be greater than -c.
Appendix B. Constants ⏱️🎀
the time constants are a trade-off between catching mobility events fast and not spamming the network with overhead. Two Babel implementations with different time constants will still interoperate, though the convergence time will most likely be dictated by the slower of the two 🐢
From experience with the sample implementation, the Hello interval is the most important time constant: a mobility event is detected within 1.5 to 3 Hello intervals. Because Babel leans on triggered updates and explicit requests, the Update interval only affects how long it takes for accurate metrics to propagate after link cost changes that are too small to trigger an unscheduled update.
At the time of writing, the sample implementation uses these default values:
- Hello Interval: 4 seconds on wireless links, 20 seconds on wired links.
- IHU Interval: the advertised IHU interval is always 3 times the Hello interval. IHUs are actually sent with each Hello on lossy links (as determined from the Hello history), but only with every third Hello on lossless links.
- Update Interval: 4 times the Hello interval.
- IHU Hold Time: 3.5 times the advertised IHU interval.
- Route Expiry Time: 3.5 times the advertised update interval.
- Source GC time: 3 minutes.
The amount of jitter applied to a packet depends on whether it contains any urgent TLVs or not. Urgent triggered updates and urgent requests are delayed by no more than 200 ms; other TLVs are delayed by no more than one-half the Hello interval. 🌈
Appendix C. Simplified Implementations 🍓
Babel is a fairly economic protocol, bestie 💖 Route updates take between 12 and 40 octets per destination, depending on how successful compression is; in a double-stack mesh network, an average of less than 24 octets 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 20000-entry routing table and the associated source table.
Babel is also a reasonably simple protocol. The sample implementation consists of less than 8000 lines of C code, and it compiles to less than 60 kB of text on a 32-bit CISC architecture.
Nonetheless, in some very constrained environments, such as PDAs, microwave ovens, or abacuses, it may be desirable to have subset implementations of the protocol. 🧮
A parasitic implementation is one that uses a Babel network for routing its packets but does not announce any of the routes that it has learnt from its neighbours. (This is slightly more than a passive implementation, which doesn't even announce routes to itself.) It may either maintain a full routing table or simply select a gateway amongst any one of its neighbours that announces a default route. Since a parasitic implementation never forwards packets, it cannot possibly participate in a routing loop; hence, it need not evaluate the feasibility condition and need not maintain a source table. 🙈
A parasitic implementation MUST answer acknowledgement requests and MUST participate in the Hello/IHU protocol. Finally, it MUST be able to reply to seqno requests for routes that it announces and SHOULD be able to reply to route requests. 💅
Appendix D. Software Availability 💾
The sample implementation of Babel is available from <http://www.pps.jussieu.fr/~jch/software/babel/>. 🦋
Author's Address 🎀
Juliusz Chroboczek
PPS, University of Paris 7
Case 7014
75205 Paris Cedex 13,
France
EMail: jch@pps.jussieu.fr📦 where this page comes from
- ietf: rfc6126 2011-04
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms