From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc8966.txt | 3060 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3060 insertions(+) create mode 100644 doc/rfc/rfc8966.txt (limited to 'doc/rfc/rfc8966.txt') diff --git a/doc/rfc/rfc8966.txt b/doc/rfc/rfc8966.txt new file mode 100644 index 0000000..8def1f1 --- /dev/null +++ b/doc/rfc/rfc8966.txt @@ -0,0 +1,3060 @@ + + + + +Internet Engineering Task Force (IETF) J. Chroboczek +Request for Comments: 8966 IRIF, University of Paris-Diderot +Obsoletes: 6126, 7557 D. Schinazi +Category: Standards Track Google LLC +ISSN: 2070-1721 January 2021 + + + The Babel Routing Protocol + +Abstract + + Babel is a loop-avoiding, distance-vector routing protocol that is + robust and efficient both 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. + + This document is a product of the Internet Engineering Task Force + (IETF). It represents the consensus of the IETF community. It has + received public review and has been approved for publication by the + Internet Engineering Steering Group (IESG). Further information on + Internet Standards is available in Section 2 of RFC 7841. + + Information about the current status of this document, any errata, + and how to provide feedback on it may be obtained at + https://www.rfc-editor.org/info/rfc8966. + +Copyright Notice + + Copyright (c) 2021 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents + (https://trustee.ietf.org/license-info) in effect on the date of + publication of this document. Please review these documents + carefully, as they describe your rights and restrictions with respect + to this document. Code Components extracted from this document must + include Simplified BSD License text as described in Section 4.e of + the Trust Legal Provisions and are provided 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 that is + designed to be robust and efficient both in networks using prefix- + based routing and in networks using flat routing ("mesh networks"), + and both in relatively stable wired networks and in highly dynamic + wireless networks. This document describes the Babel routing + protocol and obsoletes [RFC6126] and [RFC7557]. + +1.1. Features + + The main property that makes Babel suitable for unstable networks is + that, unlike naive distance-vector routing protocols [RIP], it + strongly limits the frequency and duration of routing pathologies + such as routing loops and black-holes during reconvergence. Even + after a mobility event is detected, a Babel network usually remains + loop-free. Babel then quickly reconverges to a configuration that + preserves the loop-freedom and connectedness of the network, but is + not necessarily optimal; in many cases, this operation requires no + packet exchanges at all. Babel then slowly converges, in a time on + the scale of minutes, to an optimal configuration. This is achieved + by using sequenced routes, a technique pioneered by Destination- + Sequenced Distance-Vector routing [DSDV]. + + More precisely, Babel has the following properties: + + * 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 this particular + prefix; this loop disappears in time proportional to the loop's + 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 bounded 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 has provisions for link quality estimation and for fairly + arbitrary metrics. When configured suitably, Babel can implement + shortest-path routing, or it may use a metric based, for example, on + measured packet loss. + + Babel nodes will successfully establish an association even when they + are configured with different parameters. For example, a mobile node + that is low on battery may choose to use larger time constants (hello + and update intervals, etc.) than a node that has access to wall + power. Conversely, a node that detects high levels of mobility may + choose to use smaller time constants. The ability to build such + heterogeneous networks makes Babel particularly adapted to the + unmanaged or wireless environment. + + Finally, Babel is a hybrid routing protocol, in the sense that it can + carry routes for multiple network-layer protocols (IPv4 and IPv6), + regardless of which protocol the Babel packets are themselves being + carried over. + +1.2. Limitations + + Babel has two limitations that make it unsuitable for use in some + environments. First, Babel relies on periodic routing table updates + rather than using a reliable transport; hence, in large, stable + networks it generates more traffic than protocols that only send + updates when the network topology changes. In such networks, + protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced + Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more + suitable. + + Second, unless the second algorithm described in Section 3.5.4 is + implemented, Babel does impose a hold time when a prefix is + retracted. While this hold time does not apply to the exact prefix + being retracted, and hence does not prevent fast reconvergence should + it become available again, it does apply to any shorter prefix that + covers it. This may make those implementations of Babel that do not + implement the optional algorithm described in Section 3.5.4 + unsuitable for use in 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", "NOT RECOMMENDED", "MAY", and + "OPTIONAL" in this document are to be interpreted as described in + BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all + capitals, as shown here. + +2. Conceptual Description of the Protocol + + Babel is a loop-avoiding distance-vector protocol: it is based on the + Bellman-Ford algorithm, just like the venerable RIP [RIP], but + includes a number of refinements that either prevent loop formation + altogether, or ensure that a loop disappears in a timely manner and + doesn't form again. + + Conceptually, Bellman-Ford is executed in parallel for every source + of routing information (destination of data traffic). In the + following discussion, we fix a source S; the reader will recall that + the same algorithm is executed for all sources. + +2.1. Costs, Metrics, and Neighbourship + + For every pair of neighbouring nodes A and B, Babel computes an + abstract value known as the cost of the link from A to B, written + C(A, B). Given a route between any two (not necessarily + neighbouring) nodes, the metric of the route is the sum of the costs + of all the links along the route. The goal of the routing algorithm + is to compute, for every source S, the tree of routes of lowest + metric to S. + + Costs and metrics need not 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 sends Hello messages to all of its + neighbours; it also periodically sends an IHU ("I Heard You") message + to every neighbour from which it has recently heard a Hello. 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. + +2.2. The Bellman-Ford Algorithm + + Every node A maintains two pieces of data: its estimated distance to + S, written D(A), and 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 to all of its neighbours a route + update, 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 is the case, then NH(A) is set to B, and D(A) is set to C(A, B) + + D(B). If that is not the case, then A compares C(A, B) + D(B) to + its current value of D(A). If that value is smaller, meaning that + the received update advertises a route that is better than the + currently selected route, then NH(A) is set to B, and D(A) is set to + C(A, B) + D(B). + + A number of refinements to this algorithm are possible, and are used + by Babel. In particular, convergence speed may be increased by + sending unscheduled "triggered updates" whenever a major change in + the topology is detected, in addition to the regular, scheduled + updates. Additionally, a node may maintain a number of alternate + routes, which are being advertised by neighbours other than its + selected neighbour, and which can be used immediately if the selected + route were to fail. + +2.3. Transient Loops in Bellman-Ford + + It is well known that a naive application of Bellman-Ford to + distributed routing can cause transient loops after a topology + change. Consider for example the following topology: + + B + 1 /| + 1 / | + S --- A |1 + \ | + 1 \| + C + + After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. + + Suppose now that the link between S and A fails: + + B + 1 /| + / | + S A |1 + \ | + 1 \| + C + + When it detects the failure of the link, A switches its next hop to B + (which is still advertising a route to S with metric 2), and + advertises a metric equal to 3, and then advertises a new route with + metric 3. This process of nodes changing selected neighbours and + increasing their metric continues until the advertised metric reaches + "infinity", a value larger than all the metrics that the routing + protocol is able to carry. + +2.4. Feasibility Conditions + + Bellman-Ford is a very robust algorithm: its convergence properties + are preserved when routers delay route acquisition or when they + discard some updates. Babel routers discard 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, known + as the "feasibility condition", that guarantees the absence of + routing loops whenever all routers ignore route updates that do not + satisfy the feasibility condition. In effect, this makes Bellman- + Ford into a family of routing algorithms, parameterised by the + feasibility condition. + + Many different feasibility conditions are possible. For example, BGP + can be modelled as being 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 transient "micro-loops" during reconvergence). + + Another simple feasibility condition, used in the Destination- + Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the + Ad hoc On-Demand Distance Vector (AODV) protocol [RFC3561], stems + from the following observation: a routing loop can only arise after a + router has switched to a route with a larger metric than the route + that it had previously selected. Hence, one may define that a route + is feasible when its metric at the local node would be no larger than + the metric of the currently selected route, i.e., 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, then the metric at every router + is nonincreasing, and the following invariant is always preserved: if + A has selected B as its next hop, then D(B) < D(A), which implies + that the forwarding graph is loop-free. + + Babel uses a slightly more refined feasibility condition, derived + 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 that node A obeys DSDV-feasibility; + then D(A) is nonincreasing, hence at all times D(A) <= FD(A). + Suppose now that 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), D(B) < FD(A). + + To see that it is 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, although 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 at the time 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 in time FD(B) < FD(A). Since this + property is preserved when A sends updates and also when it picks a + different next hop, it remains true at all times, which ensures that + 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 + B + + Suppose now that the link between A and S breaks: + + A + | + | FD(A) = 1 + S |1 + \ | D(B) = 2 + 2 \| FD(B) = 2 + B + + The only route available from A to S, the one that goes through B, is + not feasible: A suffers from spurious starvation. At that point, the + whole subtree suffering from starvation must be reset, which is + essentially what EIGRP does when it performs a global synchronisation + of all the routers in the starving subtree (the "active" phase of + EIGRP). + + Babel reacts to starvation in a less drastic manner, by using + sequenced routes, a technique introduced by DSDV and adopted by AODV. + In addition to a metric, every route carries a sequence number, 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 is more recent than the + feasibility distance maintained by the receiving node, or it is + 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 sequence number is + propagated to B, we have: + + A + | + | FD(A) = (137, 1) + S |1 + \ | D(B) = (138, 2) + 2 \| FD(B) = (138, 2) + B + + at which point the route through B becomes feasible again. + + Note that while sequence numbers are used for determining + feasibility, 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 sequence number is propagated through + the network, which may, in general, require a significant amount of + time. + + Babel takes a different approach. When a node detects that it is + 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. 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, in general, reach the source, as some will be sent over links + that are now broken. However, if the network is still connected, + then at least one among the nodes suffering from spurious starvation + has an (unfeasible) route to the source; hence, 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, in general, be caught in a forwarding loop; this + is avoided by having nodes perform duplicate detection for the + requests that they forward. + +2.7. Multiple Routers + + The above discussion assumes that each prefix is originated by a + single router. In real networks, however, it is 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 are 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, but 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 that 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 will become unfeasible for B. Conversely, as + soon as B will have advertised the route through A, the route through + B will become 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, which will prevent 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 + + In the above discussion, we have assumed that all prefixes are + disjoint, as is the case in flat ("mesh") routing. In practice, + however, prefixes may overlap: for example, the default route + overlaps with all of the routes present in the network. + + After a route fails, it is 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 --- C + + Suppose that 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, which is an arbitrary + string of 8 octets that is assumed 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 + + Babel protocol packets are sent in the body of a UDP datagram (as + described in Section 4). Each Babel packet consists of zero or more + TLVs. Most TLVs may contain sub-TLVs. + + Babel's control traffic can be carried indifferently over IPv6 or + over IPv4, and prefixes of either address family can be announced + over either protocol. Thus, there are at least two natural + deployment models: using IPv6 exclusively for all control traffic, or + running two distinct protocol instances, one for each address family. + The exclusive use of IPv6 for all control traffic is RECOMMENDED, + since using both protocols at the same time doubles the amount of + traffic devoted to neighbour discovery and link quality estimation. + + The source address of a Babel packet is always a unicast address, + link-local in the case of IPv6. Babel packets may be sent 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. + + With the exception of acknowledgments, all Babel TLVs can be sent to + either unicast or multicast addresses, and their semantics does not + depend on whether the destination is a unicast or a multicast + address. Hence, a Babel speaker does not need to determine the + destination address of a packet that it receives in order to + interpret it. + + A moderate amount of jitter may be applied to packets sent by a Babel + speaker: outgoing TLVs are buffered and SHOULD be sent with a random + delay. This is done for two purposes: it avoids synchronisation of + multiple Babel speakers across a network [JITTER], and it allows for + the aggregation of multiple TLVs into a single packet. + + The maximum amount of delay a TLV can be subjected to depends on the + TLV. When the protocol description specifies that a TLV is urgent + (as in Section 3.7.2 and Section 3.8.1), then the TLV MUST be sent + within a short time known as the urgent timeout (see Appendix B for + recommended values). When the TLV is governed by a timeout + explicitly included in a previous TLV, such as in the case of + 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 to allow for propagation + delays). In all other cases, the TLV SHOULD be sent out within one- + half of the Multicast Hello interval. + + In order to avoid packet drops (either at the sender or at the + receiver), a delay SHOULD be introduced between successive packets + sent out on the same interface, within the constraints of the + previous paragraph. Note, however, that such packet pacing might + impair the ability of some link layers (e.g., IEEE 802.11 + [IEEE802.11]) to perform packet aggregation. + +3.2. Data Structures + + In this section, we describe the data structures that every Babel + speaker maintains. This description is conceptual: a Babel speaker + may use different data structures as long as the resulting protocol + is the same as the one described in this document. For example, + rather than maintaining a single table containing both selected and + unselected (fallback) routes, as described in Section 3.2.6, an + actual implementation would probably use two tables, one with + selected routes and one with fallback routes. + +3.2.1. Sequence Number Arithmetic + + Sequence numbers (seqnos) appear in a number of Babel data + structures, and they are interpreted as integers modulo 2^(16). For + the purposes of this document, arithmetic on sequence numbers is + defined as follows. + + 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 is included in + route updates sent for routes originated by this node. + + A node increments its sequence number (modulo 2^(16)) whenever it + receives a request for a new sequence number (Section 3.8.1.2). A + node SHOULD NOT increment its sequence number (seqno) spontaneously, + since increasing 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 contains the list of interfaces on which the node + speaks the Babel protocol. Every interface table entry contains the + interface's outgoing Multicast Hello seqno, a 16-bit integer that is + sent with each Multicast Hello TLV on this interface and is + incremented (modulo 2^(16)) whenever a Multicast Hello is sent. + (Note that an interface's Multicast Hello seqno is unrelated to the + node's seqno.) + + There are two timers associated with each interface table entry. The + periodic multicast hello timer governs the sending of scheduled + Multicast Hello and IHU packets (Section 3.4). The periodic Update + timer governs the sending of periodic route updates (Section 3.7.1). + See Appendix B for suggested time constants. + +3.2.4. The Neighbour Table + + The neighbour table contains the list of all neighbouring interfaces + from which a Babel packet has been recently received. The neighbour + table is indexed by pairs of the form (interface, address), and every + neighbour table entry contains 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.) + + There are three timers associated with each neighbour entry -- 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. Therefore, two nodes with multiple interfaces can + participate in multiple neighbourship relationships, a situation that + can notably arise when wireless nodes with multiple radios are + involved. + +3.2.5. The Source Table + + The source table is used to record feasibility distances. It is + indexed by triples of the form (prefix, plen, router-id), and every + source table entry contains 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 is one timer associated with each entry in the source table -- + the source garbage-collection timer. It is initialised to a time on + the order of minutes and reset as specified in Section 3.7.3. + +3.2.6. The Route Table + + The route table contains the routes known to this node. It is + indexed by triples of the form (prefix, plen, neighbour), and every + route table entry contains 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. + + There is one timer associated with each route table entry -- the + route expiry timer. It is initialised and reset as specified in + Section 3.5.3. + + Note that there are two distinct (seqno, metric) pairs associated + with each route: the route's distance, which is stored in the route + table, and the feasibility distance, which is stored in the source + table and shared between all routes with the same source. + +3.2.7. The Table of Pending Seqno Requests + + The table of pending seqno requests contains a list of seqno requests + that the local node has sent (either because they have been + originated locally, or because they were forwarded) and to which no + reply has been received yet. This table is indexed by triples of the + form (prefix, plen, router-id), and every entry in this table + contains 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. + + There is one timer associated with each pending seqno request; it + governs both the resending of requests and their expiry. + +3.3. Acknowledgments and Acknowledgment Requests + + A Babel speaker may request that a neighbour receiving a given packet + reply with an explicit acknowledgment within a given time. While the + use of acknowledgment requests is optional, every Babel speaker MUST + be able to reply to such a request. + + An acknowledgment MUST be sent to a unicast destination. On the + other hand, acknowledgment requests may be sent to either unicast or + multicast destinations, in which case they request an acknowledgment + from all of the receiving nodes. + + When to request acknowledgments is a matter of local policy; the + simplest strategy is to never request acknowledgments and to rely on + periodic updates to ensure that any reachable routes are eventually + propagated throughout the routing domain. In order to improve + convergence speed and to reduce the amount of control traffic, + acknowledgment requests MAY be used in order to reliably send urgent + updates (Section 3.7.2) and retractions (Section 3.5.4), especially + 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 all packets with acknowledgment requests is not + necessary and NOT RECOMMENDED, as the acknowledgments cause + additional traffic and may force additional Address Resolution + Protocol (ARP) or Neighbour Discovery (ND) exchanges. + +3.4. Neighbour Acquisition + + Neighbour acquisition is the process by which a Babel node discovers + the set of neighbours heard over each of its interfaces and + ascertains bidirectional reachability. On unreliable media, + neighbour acquisition additionally provides some statistics that may + be useful for link quality computation. + + Before it can exchange routing information with a neighbour, a Babel + node MUST create an entry for that neighbour in the neighbour table. + When to do that is implementation-specific; suitable strategies + include creating an entry when any Babel packet is received, or + creating an entry when a Hello TLV is parsed. Similarly, in order to + conserve system resources, an implementation SHOULD discard an entry + when it has been unused for long enough; suitable strategies include + dropping the neighbour after a timeout, and dropping a neighbour when + the associated Hello histories become 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, to indicate that it is alive. Each Hello TLV + carries an increasing (modulo 2^(16)) sequence number and an upper + bound on the time interval until the next Hello of the same type (see + below). If the time interval is set to 0, then the Hello TLV does + not establish a new promise: the deadline carried by the previous + Hello of the same type still applies to the next Hello (if the most + recent scheduled Hello of the right kind was received at time t0 and + carried interval i, then the previous promise of sending another + Hello before time t0 + i still holds). We say that a Hello is + "scheduled" if it carries a nonzero interval, and "unscheduled" + otherwise. + + There are two kinds of Hellos: Multicast Hellos, which use a per- + interface Hello counter (the Multicast Hello seqno), and Unicast + Hellos, which 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 sending it to a multicast address or + by sending it to one unicast address per neighbour (hence, the term + "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a + given seqno should normally be sent to just one neighbour (over + unicast), since the sequence numbers of different neighbours are not + in general synchronised. + + Multicast Hellos sent over multicast can be used for neighbour + discovery; hence, a node SHOULD send periodic (scheduled) Multicast + Hellos unless neighbour discovery is performed by means outside of + the Babel protocol. A node MAY send Unicast Hellos or unscheduled + Hellos of either kind for any reason, such as reducing the amount of + multicast traffic or improving reliability on link technologies with + poor support for link-layer multicast. + + A node MAY send a scheduled Hello ahead of time. A node 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 deal with received Hello TLVs and what statistics to maintain + are considered local implementation matters; typically, a node will + maintain some sort of history of recently received Hellos. An + example of a suitable 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 + + In order 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 MAY be sent to a multicast address in order to avoid an + ARP or Neighbour Discovery exchange and to aggregate multiple IHUs + into 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, 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 contains two pieces of data: the link's rxcost + (reception cost) from the sender's perspective, used by the neighbour + for computing link costs (Section 3.4.3), and the interval between + periodic IHU packets. A node receiving an IHU sets the value of the + txcost (transmission cost) maintained in the neighbour table to the + value contained in the IHU, and resets the IHU timer associated to + this 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, the neighbour's 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 + + A neighbourship association's link cost is computed from the values + maintained in the neighbour table: the statistics kept in the + neighbour table about the reception of Hellos, and the txcost + computed from received IHU packets. + + For every neighbour, a Babel node computes a value known as this + neighbour's rxcost. This value is usually derived from the Hello + history, which may be combined with other data, such as statistics + maintained by the link layer. The rxcost is sent to a neighbour in + each IHU. + + Since nodes do not necessarily send periodic Unicast Hellos but do + usually send periodic Multicast Hellos (Section 3.4.1), 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 is not required. + + How the txcost and rxcost are combined in order to compute a link's + cost is a matter of local policy; as far as Babel's correctness is + concerned, 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), where (prefix, plen) is the prefix for which a route + is being advertised, router-id is the router-id of the router + originating this update, seqno is a nondecreasing (modulo 2^(16)) + integer that carries the originating router seqno, and metric is the + announced metric. + + Before being accepted, an update is checked against the feasibility + condition (Section 3.5.1), which ensures that the route does not + create a routing loop. If the feasibility condition is not + satisfied, the update is either ignored or prevents the route from + being selected, as described in Section 3.5.3. If the feasibility + condition is satisfied, then the update cannot possibly cause a + routing loop. + +3.5.1. The Feasibility Condition + + The feasibility condition is applied to all received updates. The + feasibility condition compares the metric in the received update with + the metrics of the updates previously sent by the receiving node; + updates that fail the feasibility condition, and therefore 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 are compared lexicographically, with the first component + inverted: we say that a distance (seqno, metric) is strictly better + than a distance (seqno', metric'), written + + (seqno, metric) < (seqno', metric') + + when + + seqno > seqno' or (seqno = seqno' and metric < metric') + + where sequence numbers are compared modulo 2^(16). + + Given a source (prefix, plen, router-id), a node's feasibility + distance for this source is the minimum, according to the ordering + defined above, of the distances of all the finite updates ever sent + by this particular node for the prefix (prefix, plen) and the given + router-id. Feasibility distances are maintained in the source table, + the exact procedure is given in Section 3.7.3. + + A received update is feasible when either it is 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 the following 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 considers the metric advertised + by the neighbour, not the route's metric; hence, a fluctuation in a + neighbour's cost cannot render a selected route unfeasible. Note + further that retractions (updates with infinite metric) are always + feasible, since they cannot possibly cause a routing loop. + +3.5.2. Metric Computation + + A route's metric is computed from the metric advertised by the + neighbour and the neighbour's link cost. Just like cost computation, + metric computation is considered a local policy matter; as far as + Babel is concerned, the function M(c, m) used for computing a metric + from 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'). + + While strict monotonicity is essential to the integrity of the + network (persistent routing loops may arise if it is not satisfied), + left-distributivity is not: if it is not satisfied, Babel will still + converge to a loop-free configuration, but 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 + is useful 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 + + Before sending an update (prefix, plen, router-id, seqno, metric) + with finite metric (i.e., not a route retraction), a Babel node + updates the feasibility distance maintained in the source table. + This is done as follows. + + If no entry indexed by (prefix, plen, router-id) exists in the source + table, then one is created with value (prefix, plen, router-id, + seqno, metric). + + If an entry (prefix, plen, router-id, seqno', metric') exists, then + it is updated as follows: + + * if seqno > seqno', then seqno' := seqno, metric' := metric; + + * if seqno = seqno' and metric' > metric, then metric' := metric; + + * otherwise, nothing needs to be done. + + The garbage-collection timer for the entry is then 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. + + When the garbage-collection timer expires, the entry is removed from + the source table. + +3.7.4. Split Horizon + + When running over a transitive, symmetric link technology, e.g., a + point-to-point link or a wired LAN technology such as Ethernet, a + Babel node SHOULD use an optimisation known as split horizon. When + split horizon is used on a given interface, a routing update for + prefix P is not sent on the particular interface over which the + selected route towards prefix P was learnt. + + 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 (e.g., IEEE 802.11 in ad hoc mode) when routing updates + are sent over multicast. + +3.8. Explicit Requests + + In normal operation, a node's route table is populated by the regular + and triggered updates sent by its neighbours. Under some + circumstances, however, a node sends explicit requests in order to + cause a resynchronisation with the source after a mobility event or + to prevent a route from spuriously expiring. + + The Babel protocol provides two kinds of explicit requests: route + requests, which simply request an update for a given prefix, and + seqno requests, which request an update for a given prefix with a + specific sequence number. The former are never forwarded; the latter + are forwarded if they cannot be satisfied by the receiver. + +3.8.1. Handling Requests + + Upon receiving a request, a node either forwards the request or sends + an update in reply to the request, as described in the following + sections. If this causes an update to be sent, the update is either + sent to a multicast address on the interface on which the request was + received, or to the unicast address of the neighbour that sent the + request. + + 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 given prefix, it checks + its route table for a selected route to this exact prefix. If such a + route exists, it MUST send an update (over unicast or over + multicast); if such a route does not exist, it MUST send a retraction + for that prefix. + + 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 are sent over multicast. + +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 contains 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, then 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. + + Otherwise, if the requested router-id is not its own, the received + node consults 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, the node selects a neighbour to forward the request to as + follows: + + * 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. + + In order to actually forward the request, the node decrements the hop + count and sends the request in a unicast packet destined 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 sufficiently large to + satisfy the request) as an urgent TLV (as defined in Section 3.1). A + node SHOULD compare every incoming seqno request against its list of + recently forwarded seqno requests and avoid forwarding the request if + it is redundant (i.e., if 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 does not necessarily obey the + feasibility condition, it may get caught in routing loops; hence, + requests carry a hop count to limit the time during which they remain + in the network. However, since requests are only ever forwarded as + unicast packets, the initial hop count need not be kept particularly + low, and performing an expanding horizon search is not 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. However, if a seqno request is resent by its originator, + the subsequent copies may be forwarded to a different neighbour than + the initial one. + +3.8.2. Sending Requests + + A Babel node MAY send a route or seqno request at any time to a + multicast or a unicast address; there is only one case when + 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 + to another feasible route for the same prefix. It may be the case, + however, that no such routes are 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. The router-id of the request is set to the router- + id of the route that it has just lost, and the requested seqno is the + value contained in the source table plus 1. The request carries a + hop count, which is used as a last-resort mechanism to ensure that it + eventually vanishes from the network; it MAY be set to any value that + is 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 these 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, then at least one of these requests will be forwarded to + the source, resulting in a route being advertised with a new sequence + number. (Due to duplicate suppression, only a small number of such + requests are expected to actually reach the source.) + + In order 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, however, all such + requests might be lost; in that case, the mechanism in the next + section will eventually ensure that 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 that it has currently selected. As specified in + Section 3.5.1, the receiving node will either ignore the update or + unselect the route. + + In order to keep routes from spuriously expiring because they have + 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. + + Additionally, since metric computation does not necessarily coincide + with the delay in propagating updates, a node might receive an + unfeasible update from a currently unselected neighbour that is + preferable to the currently selected route (e.g., 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 triggers: since a + route's hold time is computed from an explicit interval included in + Update TLVs, a new update (possibly a retraction) should arrive in + time to prevent a route from expiring. + + In the presence of packet loss, however, it may be the case that no + update is successfully received for an extended period of time, + causing a route to expire. In order to avoid such spurious expiry, + shortly before a selected route expires, a Babel node SHOULD send a + unicast route request to the neighbour that advertised this route; + since nodes always send either updates or retractions in response to + non-wildcard route requests (Section 3.8.1.1), this will usually + result in the route being either refreshed or retracted. + +4. Protocol Encoding + + A Babel packet MUST be sent as the body of a UDP datagram, with + network-layer hop count set to 1, destined to a well-known multicast + address or to a unicast address, over IPv4 or IPv6; in the case of + IPv6, these addresses are link-local. Both the source and + destination UDP port are 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 belonging to 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. + + In order to minimise the number of packets being sent while avoiding + lower-layer fragmentation, a Babel node SHOULD maximise the size of + the packets it sends, up to the outgoing interface's MTU adjusted for + 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 + that are as large as any attached interface's MTU adjusted for lower- + layer headers or 512 octets, whichever is larger. Babel packets MUST + NOT be sent in IPv6 jumbograms [RFC2675]. + +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 (in Big-Endian format [IEN137], also + called network order). The base protocol only carries unsigned + values; if an extension needs to carry signed values, it will need to + specify their encoding (e.g., two's complement). + +4.1.2. Interval + + Relative times are carried as 16-bit values specifying a number of + centiseconds (hundredths of a second). This allows times up to + roughly 11 minutes with a granularity of 10 ms, which should cover + all reasonable applications 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 + consist of either all binary zeroes (0000000000000000 hexadecimal) or + all binary ones (FFFFFFFFFFFFFFFF hexadecimal). + +4.1.4. Address + + Since the bulk of the protocol is taken by addresses, multiple ways + of encoding addresses are defined. Additionally, within Update TLVs + a common subnet prefix may be omitted when multiple addresses are + sent in a single packet -- this is known as address compression + (Section 4.6.9). + + 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, a prefix of fe80::/64 is implied. + + The address family associated with an address encoding is either IPv4 + or IPv6: it is 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, but it is + stored in the smallest number of octets that are enough to hold the + significant bits (up to the prefix length). + +4.2. Packet Format + + A Babel packet consists of a 4-octet header, followed by a sequence + of TLVs (the packet body), optionally followed by a second sequence + of TLVs (the packet trailer). The format is designed 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 (excluding the Magic, Version, and Body length + fields, and excluding the packet trailer). + + Packet Body The packet body; a sequence of TLVs. + + Packet Trailer The packet trailer; another sequence of TLVs. + + The packet body and trailer are both sequences of TLVs. The packet + body is the normal place to store TLVs; the packet trailer only + contains specialised TLVs that do not need to be protected by + cryptographic security mechanisms. When parsing the trailer, the + receiver MUST ignore any TLV unless its definition explicitly states + that it is allowed to appear there. Among the TLVs defined in this + document, only Pad1 and PadN are allowed in the trailer; since these + TLVs are ignored in any case, 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 to + appear in the trailer. + +4.3. TLV Format + + With the exception of Pad1, all TLVs have 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 | Payload... + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- + + Fields: + + Type The type of the TLV. + + Length The length of the body in octets, exclusive of the Type and + Length fields. + + Payload The TLV payload, which consists of a body and, for selected + TLV types, an optional list of sub-TLVs. + + TLVs with an unknown type value MUST be silently ignored. + +4.4. Sub-TLV Format + + Every TLV carries an explicit length in its header; however, most + TLVs are self-terminating, in the sense that it is possible to + determine the length of the body without reference to the explicit + Length field. If a TLV has a self-terminating format, then the space + between the natural size of the TLV and the size announced in the + Length field may be used to store a sequence of sub-TLVs. + + Sub-TLVs have the same structure as TLVs. With the exception of + Pad1, all TLVs have 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... + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- + + Fields: + + Type The type of the sub-TLV. + + Length The length of the body in octets, exclusive of the Type and + Length fields. + + Body The sub-TLV body, the interpretation of which depends on + both the type of the sub-TLV and the type of the TLV within + which it is embedded. + + The most significant bit of the sub-TLV type (the bit with value 80 + hexadecimal), is called the mandatory bit; in other words, sub-TLV + types 128 through 255 have the mandatory bit set. This bit indicates + how to handle unknown sub-TLVs. If the mandatory bit is not set, + then an unknown sub-TLV MUST be silently ignored, and the rest of the + TLV is processed normally. If the mandatory bit is set, then the + whole enclosing TLV MUST be silently ignored (except for updating the + parser state by a Router-Id, Next Hop, or Update TLV, as described in + the next section). + +4.5. Parser State and Encoding of Updates + + In a large network, the bulk of Babel traffic consists of route + updates; hence, some care has been given to encoding them + efficiently. The data conceptually contained in an update + (Section 3.5) is split into three pieces: + + * the prefix, seqno, and metric are contained in the Update TLV + itself (Section 4.6.9); + + * the router-id is taken from the Router-Id TLV that precedes the + Update TLV and may be shared among multiple Update TLVs + (Section 4.6.7); + + * the next hop is taken either from the source address of the + network-layer packet that contains the Babel packet or from an + explicit Next Hop TLV (Section 4.6.8). + + In addition to the above, an Update TLV can omit a prefix of the + prefix being announced, which is then extracted from the preceding + Update TLV in the same address family (IPv4 or IPv6). Finally, as a + special optimisation for the case when a router-id coincides with the + interface-id part of an IPv6 address, the Router-Id TLV itself may be + omitted, and the router-id is derived from the low-order bits of the + advertised prefix (Section 4.6.9). + + In order to implement these compression techniques, Babel uses a + stateful parser: a TLV may refer to data from a previous TLV. The + parser state consists of the following pieces of data: + + * for each address encoding that allows compression, the current + default prefix: this is undefined at the start of the packet and + is 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: this + is the source address of the enclosing packet for the matching + address family at the start of a packet, and it is updated by each + Next Hop TLV (Section 4.6.8); + + * the current router-id: this is undefined at the start of the + packet, and it is updated by each Router-Id TLV (Section 4.6.7) + and by each Update TLV with Router-Id flag set. + + Since the parser state must be identical across implementations, it + is updated before checking for mandatory sub-TLVs: parsing a TLV MUST + update the parser state even if the TLV is otherwise ignored due to + an unknown mandatory sub-TLV or for any other reason. + + None of the TLVs that modify the parser state are allowed in the + packet trailer; hence, an implementation may choose to use a + dedicated stateless parser to parse the packet 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, exclusive of 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + This TLV requests that the receiver send an Acknowledgment TLV within + the number of centiseconds specified by the Interval field. + + Fields: + + Type Set to 2 to indicate an Acknowledgment Request TLV. + + Length The length of the body in octets, exclusive of the Type and + Length fields. + + Reserved Sent as 0 and MUST be ignored on reception. + + Opaque An arbitrary value that will be echoed in the receiver's + Acknowledgment TLV. + + Interval A time interval in centiseconds after which the sender will + assume that this packet has been lost. This MUST NOT be 0. + The receiver MUST send an Acknowledgment TLV before this + time has elapsed (with a margin allowing 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 TLV is sent by a node upon receiving an Acknowledgment Request + TLV. + + Fields: + + Type Set to 3 to indicate an Acknowledgment TLV. + + Length The length of the body in octets, exclusive of the Type and + Length fields. + + Opaque Set to the Opaque value of the Acknowledgment Request that + prompted this Acknowledgment. + + Since Opaque values are not globally unique, this TLV MUST be sent to + a unicast 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + This TLV is used for neighbour discovery and for determining a + neighbour's reception cost. + + Fields: + + Type Set to 4 to indicate a Hello TLV. + + Length The length of the body in octets, exclusive of the Type and + Length fields. + + Flags The individual bits of this field specify special handling + of this TLV (see below). + + Seqno If the Unicast flag is set, this is the value of the + sending node's outgoing Unicast Hello seqno for this + neighbour. Otherwise, it is the sending node's outgoing + Multicast Hello seqno for this interface. + + Interval If nonzero, this is an upper bound, expressed 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 this is 0, then this Hello represents an + unscheduled Hello and doesn't carry any new information + about times at which Hellos are sent. + + The Flags field is interpreted as follows: + + 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, then this Hello + represents a Unicast Hello, otherwise it represents a + Multicast Hello; + + X: all other bits MUST be sent as 0 and silently ignored on + reception. + + Every time a Hello is sent, the corresponding seqno counter MUST be + incremented. Since there is a single seqno counter for all the + Multicast Hellos sent by a given node over a given interface, if the + Unicast flag is not set, this TLV MUST be sent to all neighbours on + this link, which can be achieved by sending to a multicast + destination or by sending multiple packets to the unicast addresses + of all reachable neighbours. Conversely, if the Unicast flag is set, + this TLV MUST be sent to a single neighbour, which can achieved by + sending to a unicast destination. In order to avoid large + discontinuities 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... + +-+-+-+-+-+-+-+-+-+-+-+- + + An IHU ("I Heard You") TLV is used for confirming bidirectional + reachability and carrying a link's transmission cost. + + Fields: + + Type Set to 5 to indicate an IHU TLV. + + Length The length of the body in octets, exclusive of 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 specified in the Address field. The value + FFFF hexadecimal (infinity) indicates that this interface + is unreachable. + + Interval An upper bound, expressed in centiseconds, on the time + after which the sending node will send a new IHU; this MUST + NOT be 0. The receiving node will use this value in order + to compute a hold time for this symmetric association. + + Address The address of the destination node, in the format + specified by the AE field. Address compression is not + allowed. + + Conceptually, an IHU is destined to a single neighbour. However, IHU + TLVs contain an explicit destination address, and MAY be sent to a + multicast address, as this allows aggregation of IHUs destined to + distinct neighbours into a single packet and avoids the need for an + ARP or Neighbour Discovery exchange when a neighbour is not being + used for data traffic. + + 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 establishes a router-id that is implied by subsequent + Update TLVs, as described in Section 4.5. This TLV sets the router- + id even if it is otherwise ignored due to an unknown mandatory sub- + TLV. + + Fields: + + Type Set to 6 to indicate a Router-Id TLV. + + Length The length of the body in octets, exclusive of 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 establishes a next-hop address for a given address + family (IPv4 or IPv6) that is implied in subsequent Update TLVs, as + described in Section 4.5. This TLV sets up the next hop for + subsequent Update TLVs even if it is otherwise ignored due to an + unknown mandatory sub-TLV. + + Fields: + + Type Set to 7 to indicate a Next Hop TLV. + + Length The length of the body in octets, exclusive of 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 over which + this packet is transported, a Next Hop TLV is not needed: in the + absence of a Next Hop TLV in 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 advertises or retracts a 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. + + 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. + + 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). + + 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. + + 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; + + 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. + + 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. + + 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. + + 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 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). + + 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. + + 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 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. + + 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. + + 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. + + 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. + +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. + +5. IANA Considerations + + 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 + + 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 + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, + DOI 10.17487/RFC2119, March 1997, + . + + [RFC793] Postel, J., "Transmission Control Protocol", STD 7, + RFC 793, DOI 10.17487/RFC0793, September 1981, + . + + [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, + . + + [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC + 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, + May 2017, . + + [RFC8967] Dô, C., Kolodziejak, W., and J. Chroboczek, "MAC + Authentication for the Babel Routing Protocol", RFC 8967, + DOI 10.17487/RFC8967, January 2021, + . + +7.2. Informative References + + [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, + . + + [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, . + + [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, + . + + [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, . + + [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, + . + + [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, . + + [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, . + + [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, . + + [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, + DOI 10.17487/RFC2328, April 1998, + . + + [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, + . + + [RFC2675] Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms", + RFC 2675, DOI 10.17487/RFC2675, August 1999, + . + + [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, + . + + [RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, + DOI 10.17487/RFC6126, April 2011, + . + + [RFC7298] Ovsienko, D., "Babel Hashed Message Authentication Code + (HMAC) Cryptographic Authentication", RFC 7298, + DOI 10.17487/RFC7298, July 2014, + . + + [RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing + Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015, + . + + [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, + . + + [RIP] Malkin, G., "RIP Version 2", STD 56, RFC 2453, + DOI 10.17487/RFC2453, November 1998, + . + +Appendix A. Cost and Metric Computation + + The strategy for computing link costs and route metrics is a local + matter; Babel itself only requires that it comply with the conditions + given in Section 3.4.3 and Section 3.5.2. Different nodes may use + different strategies in a single network and may use different + strategies on different interface types. This section describes a + set of strategies that have been found to work well in actual + networks. + + In summary, a node maintains per-neighbour statistics about the last + 16 received Hello TLVs of each kind (Appendix A.1), it computes costs + by using 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. + It uses an additive algebra for metric computation (Section 3.5.2). + +A.1. Maintaining Hello History + + For each neighbour, a node maintains two sets of Hello history, one + for each kind of Hello, and an expected sequence number, one for + Multicast and one for Unicast Hellos. Each Hello history is a vector + of 16 bits, where a 1 value represents a received Hello, and a 0 + value a missed Hello. For each kind of Hello, the expected sequence + number, written ne, is the sequence number that is expected to be + carried by the next received Hello from this neighbour. + + Whenever it receives a Hello packet of a given kind from a neighbour, + a node compares the received sequence number nr for that kind of + Hello with its expected sequence number ne. Depending on the outcome + of this comparison, one of the following actions is taken: + + * 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 is flushed and a new + one is created; + + * otherwise, if the received nr is smaller (modulo 2^(16)) than the + expected sequence number ne, 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 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 is not + zero, it resets the neighbour's hello timer to 1.5 times the + advertised Interval (the extra margin allows for delay due to + jitter). + + Whenever either hello timer associated with a neighbour expires, the + local node adds a 0 bit to the corresponding Hello history, and + increments the expected Hello number. If both Hello histories are + empty (they contain 0 bits only), the neighbour entry is 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 necessary in this case, since jitter was already taken into + account when computing the timeout that has just expired). + +A.2. Cost Computation + + This section describes two algorithms suitable for computing costs + (Section 3.4.3) based on Hello history. Appendix A.2.1 applies to + wired links and Appendix A.2.2 to wireless links. RECOMMENDED + default values of the parameters that appear in these algorithms are + given in Appendix B. + +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 C >= + 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 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 performs k- + out-of-j twice for each neighbour, once on the Unicast Hello history + and once on the Multicast Hello history. If either of the instances + of k-out-of-j indicates that the link is up, then the link is assumed + to be up, and the rxcost is set to C; if both instances indicate that + the link is 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 performing k-out-of-j link sensing is defined as + follows: + + * cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; + + * cost = txcost otherwise. + +A.2.2. ETX + + Unlike wired links which are bimodal (either up or down), wireless + links exhibit continuous variation of the link quality. Naive + application of hop-count routing in networks that use wireless links + for transit tends to select long, lossy links in preference to + shorter, lossless links, which can dramatically reduce throughput. + For that reason, a routing protocol designed to support wireless + links must perform some form of link quality estimation. + + The Expected Transmission Cost algorithm, or ETX [ETX], is a simple + link quality estimation algorithm that is designed to work well with + the IEEE 802.11 MAC [IEEE802.11]. By default, the IEEE 802.11 MAC + performs Automatic Repeat Query (ARQ) and rate adaptation on unicast + frames, but not on multicast frames, which are sent at a fixed rate + with no ARQ; therefore, measuring the loss rate of multicast frames + yields a useful estimate of a link's quality. + + A node performing ETX link quality estimation uses a neighbour's + Multicast Hello history to compute an estimate, written beta, of the + probability that a Hello TLV is successfully received. Beta can be + computed as the fraction of 1 bits within a small number (say, 6) of + the most recent entries in the Multicast Hello history, or it can be + an exponential average, or some combination of both approaches. Let + rxcost be 256/beta. + + Let 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) / 256. + + Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast + frames do not provide a useful measure of link quality, and therefore + ETX ignores the Unicast Hello history. Thus, a node performing ETX + link quality estimation will not 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 the process by which a node selects + a single route among the routes that it has available towards a given + destination. With Babel, any route selection procedure that only + ever chooses feasible routes with a finite metric will yield a set of + loop-free routes; however, in the presence of continuously variable + metrics such as ETX (Appendix A.2.2), a naive route selection + procedure might lead to persistent oscillations. Such oscillations + can be limited or avoided altogether by implementing hysteresis + within the route selection algorithm, i.e., by making the route + selection algorithm sensitive to a route's history. Any reasonable + hysteresis algorithm should yield good results; the following + algorithm is simple to implement and has been successfully deployed + in a variety of environments. + + For every route R, in addition to the route's metric m(R), maintain 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 the + quality of a route. The algorithm above works by only switching + routes when both the instantaneous and the long-term estimates of the + route's quality indicate that switching is profitable. + +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 interoperate, although the + resulting worst-case convergence time will be dictated by the slower + of the two. + + The Hello interval is the most important time constant: an outage or + a mobility event is detected within 1.5 to 3.5 Hello intervals. Due + to Babel's use of a redundant route table, and due to its reliance on + triggered updates and explicit requests, the Update interval has + little influence on the time needed to reconverge after an outage: in + practice, it only has a significant effect on the time needed to + acquire new routes after a mobility event. While the protocol allows + intervals as low as 10 ms, such low values would cause significant + amounts of protocol traffic for little practical benefit. + + The following values have been found to work well in a variety of + environments and are therefore 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 a procedure where an instance of a routing + protocol either discards some of the routes announced by its + neighbours or learns them with a metric that is higher than what + would be expected. Like all distance-vector protocols, Babel has the + ability to apply arbitrary filtering to the routes it learns, and + implementations of Babel that apply different sets of filtering rules + will interoperate without causing routing loops. The protocol's + ability to perform route filtering is a consequence of the latitude + given 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 are treated in 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 useful tool, since it allows fine-grained tuning + of the routing decisions made by the routing protocol. Accordingly, + some implementations of Babel implement a rich configuration language + that allows applying filtering to sets of routes defined, for + example, by incoming interface and destination prefix. + + In order to limit the consequences of misconfiguration, Babel + implementations provide a reasonable set of default filtering rules + even when they don't allow configuration of filtering by the user. + 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 that can be used to extend the protocol 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 intended 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 many 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 additional data to route + updates can be implemented either by creating a new "enriched" Update + TLV, by adding a nonmandatory sub-TLV to the Update TLV, or by adding + a mandatory sub-TLV. + + The various encodings are treated differently by implementations that + do not understand the extension. In the case of a new TLV or of a + sub-TLV with the mandatory bit set, the whole TLV is ignored by + implementations that do not implement the extension, while in the + case of a nonmandatory sub-TLV, the TLV is parsed and acted upon, and + only the unknown sub-TLV is silently ignored. Therefore, 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 that define new TLVs should make them self-terminating and + allow attaching sub-TLVs to them. + + Adding a new AE is essentially equivalent to adding a new TLV: Update + TLVs with an unknown AE are ignored, just like unknown TLVs. + However, adding a new AE is more involved than adding a new TLV, + since it creates a new set of compression state. Additionally, 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 cryptographic 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 + + Babel is a fairly economic protocol. 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 these values into + perspective, a single full-size Ethernet frame can carry some 65 + route updates, and a megabyte of memory can contain a 20,000-entry + route table and the associated source table. + + Babel is also a reasonably simple protocol. One complete + implementation consists of 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 this figure is due to protocol extensions and user- + interface code. + + Nonetheless, in some very constrained environments, such as PDAs, + microwave ovens, or abacuses, it may be desirable to have subset + implementations of the protocol. + + There are many different definitions of a stub router, but for the + needs of this section, a stub implementation of Babel is one that + announces one or more directly attached prefixes into a Babel network + but doesn't re-announce any routes that it has learnt from its + neighbours, and always prefers the direct route to a directly + attached prefix to 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, and + hence it need not evaluate the feasibility condition or maintain a + source table. + + No matter how primitive, a stub implementation must parse sub-TLVs + attached to any TLVs that it understands and 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. + + 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 32-bit CISC architecture. + +Appendix F. Compatibility with Previous Versions + + The protocol defined in this document is a successor to the protocol + defined in [RFC6126] and [RFC7557]. While the two protocols are not + entirely compatible, the new protocol has been designed so that it + can be deployed in existing RFC 6126 networks without requiring a + flag day. + + 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), and 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), and thus 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 in which some nodes + implement the protocol described in RFCs 6126 and 7557. + + 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 + either to ignore or to 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, as these are ignored in any case. + + There are other changes, but these are not of a nature to 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. The address + compression technique was inspired by [PACKETBB]. + +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 -- cgit v1.2.3