<?xmlversion="1.0" encoding="US-ASCII"?>version='1.0' encoding='utf-8'?> <!DOCTYPE rfc SYSTEM"rfc2629.dtd" []> <?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?> <?rfc toc="yes"?> <?rfc tocdepth="2"?> <?rfc symrefs="yes"?> <?rfc sortrefs="yes" ?> <?rfc compact="no" ?>"rfc2629-xhtml.ent"> <rfc xmlns:xi="http://www.w3.org/2001/XInclude" category="std" docName="draft-ietf-babel-rfc6126bis-20" number="8966" ipr="trust200902"obsoletes="6126,7557">obsoletes="6126,7557" updates="" submissionType="IETF" consensus="true" xml:lang="en" tocInclude="true" tocDepth="2" symRefs="true" sortRefs="true" version="3"> <!-- xml2rfc v2v3 conversion 3.0.0 --> <front> <title>The Babel Routing Protocol</title> <seriesInfo name="RFC" value="8966"/> <author fullname="Juliusz Chroboczek" initials="J." surname="Chroboczek"> <organization>IRIF, University of Paris-Diderot</organization> <address> <postal> <street>Case 7014</street><city>75205 Paris Cedex<city>Paris CEDEX 13</city><region></region> <code></code><code>75205</code> <country>France</country> </postal> <email>jch@irif.fr</email> </address> </author> <authorfullname='David Schinazi' surname='Schinazi' initials='D.'>fullname="David Schinazi" surname="Schinazi" initials="D."> <organization>Google LLC</organization> <address> <postal> <street>1600 Amphitheatre Parkway</street> <city>Mountain View</city> <region>California</region> <code>94043</code><country>USA</country><country>United States of America</country> </postal> <email>dschinazi.ietf@gmail.com</email> </address> </author> <dateday="25" month="August" year="2020"/>month="January" year="2021"/> <keyword>Bellman-Ford</keyword> <keyword>IGP</keyword> <keyword>loop-avoidance</keyword> <keyword>mesh network</keyword> <abstract> <t>Babel is aloop-avoidingloop-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 routingprotocol,protocol and obsoletesRFCsRFC 6126 and RFC 7557.</t> </abstract> </front> <middle> <sectiontitle="Introduction">numbered="true" toc="default"> <name>Introduction</name> <t>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 routingprotocol,protocol and obsoletes <xreftarget="RFC6126"/>target="RFC6126" format="default"/> and <xreftarget="RFC7557"/>.</t>target="RFC7557" format="default"/>.</t> <sectiontitle="Features">numbered="true" toc="default"> <name>Features</name> <t>The main property that makes Babel suitable for unstable networks is that, unlike naive distance-vector routing protocols <xreftarget="RIP"/>,target="RFC2453" format="default"/>, 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 <xreftarget="DSDV"/>.</t>target="DSDV" format="default"/>.</t> <t>More precisely, Babel has the following properties:<list style="symbols"> <t>when</t> <ul spacing="normal"> <li>when every prefix is originated by at most one router, Babel never suffers from routingloops;</t> <t>whenloops;</li> <li>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 sameprefix;</t> <t>assumingprefix;</li> <li>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'sdiameter.</t> </list> </t>diameter.</li> </ul> <t>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.</t> <t>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.</t> <t>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.</t> </section> <sectiontitle="Limitations">numbered="true" toc="default"> <name>Limitations</name> <t>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 <xreftarget="OSPF"/>,target="RFC2328" format="default"/>, IS-IS <xreftarget="IS-IS"/>,target="IS-IS" format="default"/>, or the Enhanced Interior Gateway Routing Protocol (EIGRP) <xreftarget="EIGRP"/>target="EIGRP" format="default"/> might be more suitable.</t> <t>Second, unless the second algorithm described in <xreftarget="hold-time"/>target="hold-time" format="default"/> 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 <xreftarget="hold-time"/>target="hold-time" format="default"/> unsuitable for use in networks that implement automatic prefix aggregation.</t> </section> <sectiontitle="Specificationnumbered="true" toc="default"> <name>Specification ofRequirements"> <t>TheRequirements</name> <t> The key words"MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY","<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>", "<bcp14>REQUIRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>", "<bcp14>RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>", "<bcp14>MAY</bcp14>", and"OPTIONAL""<bcp14>OPTIONAL</bcp14>" in this document are to be interpreted as described inBCP 14BCP 14 <xreftarget="RFC2119"/>target="RFC2119" format="default"/> <xreftarget="RFC8174"/>target="RFC8174" format="default"/> when, and only when, they appear in all capitals, as shownhere.</t>here. </t> </section> </section> <sectiontitle="Conceptualnumbered="true" toc="default"> <name>Conceptual Description of theProtocol">Protocol</name> <t>Babel is a loop-avoidingdistance vectordistance-vector protocol: it is based on the Bellman-Ford algorithm, just like the venerable RIP <xreftarget="RIP"/>,target="RFC2453" format="default"/>, 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.</t> <t>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.</t> <sectiontitle="Costs, Metricsnumbered="true" toc="default"> <name>Costs, Metrics, andNeighbourship">Neighbourship</name> <t>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.</t> <t>Costs and metrics need not be integers. In general, they can be values in any algebra that satisfies two fairly general conditions (<xreftarget="metric-computation"/>).</t>target="metric-computation" format="default"/>).</t> <t>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.</t> </section> <sectiontitle="Thenumbered="true" toc="default"> <name>The Bellman-FordAlgorithm">Algorithm</name> <t>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.</t> <t>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).</t> <t>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.</t> </section> <sectiontitle="Transientnumbered="true" toc="default"> <name>Transient Loops inBellman-Ford">Bellman-Ford</name> <t>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:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ B 1 /| 1 / | S --- A |1 \ | 1 \| C]]></artwork></figure>]]></artwork> <t> After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.</t> <t>Suppose now that the link between S and A fails:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ B 1 /| / | S A |1 \ | 1 \| C]]></artwork></figure> </t>]]></artwork> <t>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.</t> </section> <sectiontitle="Feasibility Conditions">numbered="true" toc="default"> <name>Feasibility Conditions</name> <t>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.</t> <t>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.</t> <t>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'sAS-PathAS_PATH attribute (note that BGP's feasibility condition does not ensure the absence of transient "micro-loops" during reconvergence).</t> <t>Another simple feasibility condition, used in the Destination-Sequenced Distance-Vector (DSDV) routing protocol <xreftarget="DSDV"/>target="DSDV" format="default"/> and in the Ad hoc On-Demand Distance Vector (AODV) protocol <xreftarget="RFC3561"/>,target="RFC3561" format="default"/>, 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.</t> <t>Babel uses a slightly more refined feasibility condition, derived from EIGRP <xreftarget="DUAL"/>.target="DUAL" format="default"/>. 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).</t> <t>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).</t> <t>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:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ B 1 / \ 1 / \ S A \ / 1 \ / 4 C]]></artwork></figure> </t>]]></artwork> <t>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 preservedbothwhen 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.</t> </section> <sectiontitle="Solvingnumbered="true" toc="default"> <name>Solving Starvation: SequencingRoutes">Routes</name> <t>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:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ A 1 /| D(A) = 1 / | FD(A) = 1 S |1 \ | D(B) = 2 2 \| FD(B) = 2 B]]></artwork></figure> </t>]]></artwork> <t>Suppose now that the link between A and S breaks:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ A | | FD(A) = 1 S |1 \ | D(B) = 2 2 \| FD(B) = 2 B]]></artwork></figure> </t>]]></artwork> <t>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).</t> <t>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.</t> <t>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.</t> <t>Assuming the sequence number of S is 137, the diagram above becomes:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ A | | FD(A) = (137, 1) S |1 \ | D(B) = (137, 2) 2 \| FD(B) = (137, 2) B]]></artwork></figure> </t>]]></artwork> <t>After S increases its sequence number, and the new sequence number is propagated to B, we have:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ A | | FD(A) = (137, 1) S |1 \ | D(B) = (138, 2) 2 \| FD(B) = (138, 2) B]]></artwork></figure>]]></artwork> <t> at which point the route through B becomes feasible again.</t> <t>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 (<xreftarget="route-selection"/>).target="route-selection" format="default"/>). Doing otherwise would cause route oscillation while a sequence number propagates through the network, and might even cause persistentblackholesblack-holes with some exotic metrics.</t> </section> <sectiontitle="Requests">numbered="true" toc="default"> <name>Requests</name> <t>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.</t> <t>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.</t> <t>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.)</t> <t>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.</t> </section> <sectiontitle="Multiple Routers">numbered="true" toc="default"> <name>Multiple Routers</name> <t>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.</t> <t>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.</t> <t>Consider for example the following topology, where A has selected the default route through S, and B has selected the one through S':<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ 1 1 1 ::/0 -- S --- A --- B --- S' -- ::/0]]></artwork></figure> </t>]]></artwork> <t>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.</t> <t>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 (<xreftarget="triggered-updates"/>).</t>target="triggered-updates" format="default"/>).</t> <t>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).</t> </section> <sectiontitle="Overlapping Prefixes" anchor="overlapping-prefixes">anchor="overlapping-prefixes" numbered="true" toc="default"> <name>Overlapping Prefixes</name> <t>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.</t> <t>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:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ 1 1 ::/0 -- A --- B --- C]]></artwork></figure> </t>]]></artwork> <t>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 (<xreftarget="hold-time"/>).</t>target="hold-time" format="default"/>).</t> </section> </section> <sectiontitle="Protocol Operation">numbered="true" toc="default"> <name>Protocol Operation</name> <t>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 <xreftarget="update"/>.)</t>target="update" format="default"/>.)</t> <sectiontitle="Messageanchor="transmission-reception" numbered="true" toc="default"> <name>Message Transmission andReception" anchor="transmission-reception">Reception</name> <t>Babel protocol packets are sent in the body of a UDP datagram (as described in <xreftarget="protocol-encoding"/> below).target="protocol-encoding" format="default"/>). Each Babel packet consists of zero or more TLVs. Most TLVs may contain sub-TLVs.</t><t>The protocol's<t>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 isRECOMMENDED,<bcp14>RECOMMENDED</bcp14>, since using both protocols at the same time doubles the amount of traffic devoted to neighbour discovery and link quality estimation.</t> <t>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.</t> <t>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.</t> <t>A moderate amount of jitter may be applied to packets sent by a Babel speaker: outgoing TLVs are buffered andSHOULD<bcp14>SHOULD</bcp14> be sent with a random delay. This is done for two purposes: it avoids synchronisation of multiple Babel speakers across a network <xreftarget="JITTER"/>,target="JITTER" format="default"/>, and it allows for the aggregation of multiple TLVs into a single packet.</t> <t>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 <xreftarget="triggered-updates"/>target="triggered-updates" format="default"/> and <xreftarget="sending-requests"/>),target="handling-requests" format="default"/>), then the TLVMUST<bcp14>MUST</bcp14> be sent within a short time known as the urgent timeout (see <xreftarget="parameters"/>target="parameters" format="default"/> for recommended values). When the TLV is governed by a timeout explicitly included in a previous TLV, such as in the case ofAcknowledgementsAcknowledgments (<xreftarget="ack"/>),target="ack" format="default"/>), Updates (<xreftarget="sending-updates"/>)target="sending-updates" format="default"/>), and IHUs (<xreftarget="bidirectional-reachability"/>),target="bidirectional-reachability" format="default"/>), then the TLVMUST<bcp14>MUST</bcp14> be sent early enough to meet the explicit deadline (with a small margin to allow for propagation delays). In all other cases, the TLVSHOULD<bcp14>SHOULD</bcp14> be sent out within one-half of the Multicast Hello interval.</t> <t>In order to avoid packet drops (either at the sender or at the receiver), a delaySHOULD<bcp14>SHOULD</bcp14> be introduced between successive packets sent out on the same interface, within the constraints of the previous paragraph.Note howeverNote, however, that such packet pacing might impair the ability of some link layers (e.g., IEEE 802.11 <xreftarget="IEEE802.11"/>)target="IEEE802.11" format="default"/>) to perform packet aggregation.</t> </section> <sectiontitle="Data Structures">numbered="true" toc="default"> <name>Data Structures</name> <t>In this section, wegive a description ofdescribe 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 <xreftarget="route-table"/> below,target="route-table" format="default"/>, an actual implementation would probably use two tables, one with selected routes and one with fallback routes.</t> <sectiontitle="Sequence number arithmetic" anchor="sequence-number">anchor="sequence-number" numbered="true" toc="default"> <name>Sequence Number Arithmetic</name> <t>Sequence numbers (seqnos) appear in a number of Babel data structures, and they are interpreted as integers modulo2^16.2<sup>16</sup>. For the purposes of this document, arithmetic on sequence numbers is defined as follows.</t> <t>Given a seqno s and a non-negative integer n, the sum of s and n is defined by<list style="empty"> <t>sthe following: </t> <t indent="3">s + n (modulo2^16)2<sup>16</sup>) = (s + n) MOD2^16</t> </list>2<sup>16</sup></t> <t> or, equivalently,<list style="empty"> <t>s</t> <t indent="3">s + n (modulo2^16)2<sup>16</sup>) = (s + n) AND 65535</t></list><t> where MOD is the modulo operation yielding a non-negativeintegerinteger, and AND is the bitwise conjunction operation.</t> <t>Given two sequence numbers s and s', the relation s is less than s' (s < s') is defined by<list style="empty"> <t>sthe following: </t> <t indent="3">s < s' (modulo2^16)2<sup>16</sup>) when 0 < ((s' - s) MOD2^16)2<sup>16</sup>) < 32768 </t></list> or equivalently <list style="empty"> <t>s<t> or, equivalently, </t> <t indent="3">s < s' (modulo2^16)2<sup>16</sup>) when s /= s' and ((s' - s) AND 32768) = 0.</t></list></t></section> <sectiontitle="Nodenumbered="true" toc="default"> <name>Node SequenceNumber">Number</name> <t>A node's sequence number is a 16-bit integer that is included in route updates sent for routes originated by this node.</t> <t>A node increments its sequence number (modulo2^16)2<sup>16</sup>) whenever it receives a request for a new sequence number (<xreftarget="handling-seqno-requests"/>).target="handling-seqno-requests" format="default"/>). A nodeSHOULD NOT<bcp14>SHOULD NOT</bcp14> 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.</t> </section> <sectiontitle="Thenumbered="true" toc="default"> <name>The InterfaceTable">Table</name> <t>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 (modulo2^16)2<sup>16</sup>) whenever a Multicast Hello is sent. (Note that an interface's Multicast Hello seqno is unrelated to the node's seqno.)</t> <t>There are two timers associated with each interface table entry. The periodicMulticast Hellomulticast hello timer governs the sending of scheduled Multicast Hello and IHU packets (<xreftarget="neighbour-acquisition"/>.target="neighbour-acquisition" format="default"/>). The periodic Update timer governs the sending of periodic route updates (<xreftarget="periodic-updates"/>).target="periodic-updates" format="default"/>). See <xreftarget="parameters"/>target="parameters" format="default"/> for suggested time constants.</t> </section> <sectiontitle="Thenumbered="true" toc="default"> <name>The NeighbourTable">Table</name> <t>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:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the local node's interface over which this neighbour isreachable;</t> <t>thereachable;</li> <li>the address of the neighbouringinterface;</t> <t>ainterface;</li> <li>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 localnode;</t> <t>anode;</li> <li>a history of recently received Unicast Hello packets from thisneighbour;</t> <t>theneighbour;</li> <li>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 hasexpired;</t> <t>theexpired;</li> <li>the expected incoming Multicast Hello sequence number for this neighbour, an integer modulo2^16.</t> <t>the2<sup>16</sup>.</li> <li>the expected incoming Unicast Hello sequence number for this neighbour, an integer modulo2^16.</t> <t>the2<sup>16</sup>.</li> <li>the outgoing Unicast Hello sequence number for this neighbour, an integer modulo2^162<sup>16</sup> that is sent with each Unicast Hello TLV to this neighbour and is incremented (modulo2^16)2<sup>16</sup>) whenever a Unicast Hello is sent. (Note that the outgoing Unicast Hello seqno for a neighbour is distinct from the interface's outgoing Multicast Helloseqno.)</t> </list> </t>seqno.)</li> </ul> <t>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 <xreftarget="parameters"/>target="parameters" format="default"/> for suggested values).</t> <t>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.</t> </section> <sectiontitle="Thenumbered="true" toc="default"> <name>The SourceTable">Table</name> <t>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:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the prefix (prefix, plen), where plen is the prefix length in bits, that this entry appliesto;</t> <t>theto;</li> <li>the router-id of a router originating thisprefix;</t> <t>aprefix;</li> <li>a pair (seqno, metric), this source's feasibilitydistance.</t> </list> </t>distance.</li> </ul> <t>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 <xreftarget="maintaining-fd"/>.</t>target="maintaining-fd" format="default"/>.</t> </section> <sectiontitle="Theanchor="route-table" numbered="true" toc="default"> <name>The RouteTable" anchor="route-table">Table</name> <t>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:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the source (prefix, plen, router-id) for which this route isadvertised;</t> <t>theadvertised;</li> <li>the neighbour (an entry in the neighbour table) that advertised thisroute;</t> <t>theroute;</li> <li>the metric with which this route was advertised by the neighbour, or FFFF hexadecimal (infinity) for a recently retractedroute;</t> <t>theroute;</li> <li>the sequence number with which this route wasadvertised;</t> <t>theadvertised;</li> <li>the next-hop address of thisroute;</t> <t>aroute;</li> <li>a boolean flag indicating whether this route is selected, i.e., whether it is currently being used for forwarding and is beingadvertised.</t> </list> </t>advertised.</li> </ul> <t>There is one timer associated with each route table entry—-- the route expiry timer. It is initialised and reset as specified in <xreftarget="route-acquisition"/>.</t>target="route-acquisition" format="default"/>.</t> <t>Note that there are two distinct (seqno, metric) pairs associatedtowith 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.</t> </section> <sectiontitle="Thenumbered="true" toc="default"> <name>The Table of Pending SeqnoRequests">Requests</name> <t>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:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the prefix, plen, router-id, and seqno beingrequested;</t> <t>therequested;</li> <li>the neighbour, if any, on behalf of which we are forwarding thisrequest;</t> <t>arequest;</li> <li>a small integer indicating the number of times that this request will be resent if it remainsunsatisfied.</t> </list> </t>unsatisfied.</li> </ul> <t>There is one timer associated with each pending seqno request; it governs both the resending of requests and their expiry.</t> </section> </section> <sectiontitle="Acknowledgmentsanchor="acknowledgments" numbered="true" toc="default"> <name>Acknowledgments andacknowledgment requests" anchor="acknowledgments">Acknowledgment Requests</name> <t>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 speakerMUST<bcp14>MUST</bcp14> be able to reply to such a request.</t> <t>An acknowledgmentMUST<bcp14>MUST</bcp14> 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.</t> <t>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 requestsMAY<bcp14>MAY</bcp14> be used in order to reliably send urgent updates (<xreftarget="triggered-updates"/>)target="triggered-updates" format="default"/>) and retractions (<xreftarget="hold-time"/>),target="hold-time" format="default"/>), 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 notnecessary,necessary andNOT RECOMMENDED,<bcp14>NOT RECOMMENDED</bcp14>, as the acknowledgments cause additional traffic and may force additional Address Resolution Protocol (ARP) or Neighbour Discovery (ND) exchanges.</t> </section> <sectiontitle="Neighbour Acquisition" anchor="neighbour-acquisition">anchor="neighbour-acquisition" numbered="true" toc="default"> <name>Neighbour Acquisition</name> <t>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.</t> <t>Before it can exchange routing information with a neighbour, a Babel nodeMUST<bcp14>MUST</bcp14> 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 implementationSHOULD<bcp14>SHOULD</bcp14> 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 <xreftarget="cost-computation-examples"/>).</t>target="cost-computation-examples" format="default"/>).</t> <sectiontitle="Reverseanchor="reverse-reachability" numbered="true" toc="default"> <name>Reverse ReachabilityDetection" anchor="reverse-reachability">Detection</name> <t>Every Babel node sends Hello TLVs to itsneighboursneighbours, at regular or irregular intervals, to indicate that it isalive, at regular or irregular intervals.alive. Each Hello TLV carries an increasing (modulo2^16)2<sup>16</sup>) 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 anon-zerononzero interval, and "unscheduled" otherwise.</t> <t>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 seqnoMUST<bcp14>MUST</bcp14> 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.</t> <t>Multicast Hellos sent over multicast can be used for neighbour discovery; hence, a nodeSHOULD<bcp14>SHOULD</bcp14> send periodic (scheduled) Multicast Hellos unless neighbour discovery is performed by means outside of the Babel protocol. A nodeMAY<bcp14>MAY</bcp14> 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.</t> <t>A nodeMAY<bcp14>MAY</bcp14> send a scheduled Hello ahead of time. A nodeMAY<bcp14>MAY</bcp14> change its scheduled Hello interval. The Hello intervalMAY<bcp14>MAY</bcp14> be decreased at any time; itMAY<bcp14>MAY</bcp14> be increased immediately before sending a Hello TLV, butSHOULD NOT<bcp14>SHOULD NOT</bcp14> be increased at other times. (Equivalently, a nodeSHOULD<bcp14>SHOULD</bcp14> send a scheduled Hello immediately after increasing its Hello interval.)</t> <t>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 <xreftarget="hello-history"/>.</t>target="hello-history" format="default"/>.</t> <t>After receiving a Hello, or determining that it has missed one, the node recomputes the association's cost (<xreftarget="cost-computation"/>)target="cost-computation" format="default"/>) and runs the route selection procedure (<xreftarget="route-selection"/>).</t>target="route-selection" format="default"/>).</t> </section> <sectiontitle="Bidirectionalanchor="bidirectional-reachability" numbered="true" toc="default"> <name>Bidirectional ReachabilityDetection" anchor="bidirectional-reachability">Detection</name> <t>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, theyMAY<bcp14>MAY</bcp14> be sent less often than Hellos in order to reduce the amount of routing traffic in dense networks; in particular, theySHOULD<bcp14>SHOULD</bcp14> be sent less often than Hellos over links with little packet loss. While IHUs are conceptually unicast, theyMAY<bcp14>MAY</bcp14> 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.</t> <t>In addition to the periodic IHUs, a nodeMAY,<bcp14>MAY</bcp14>, at any time, send an unscheduled IHU packet. ItMAY<bcp14>MAY</bcp14> also, at any time, decrease its IHU interval, and itMAY<bcp14>MAY</bcp14> increase its IHU interval immediately before sending an IHU, butSHOULD NOT<bcp14>SHOULD NOT</bcp14> increase it at any other time. (Equivalently, a nodeSHOULD<bcp14>SHOULD</bcp14> send an extra IHU immediately after increasing its Hello interval.)</t> <t>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 (<xreftarget="cost-computation"/>),target="cost-computation" format="default"/>), 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 <xreftarget="parameters"/>target="parameters" format="default"/> for suggested values). When a neighbour's IHU timer expires, the neighbour's txcost is set to infinity.</t> <t>After updating a neighbour's txcost, the receiving node recomputes the neighbour's cost (<xreftarget="cost-computation"/>)target="cost-computation" format="default"/>) and runs the route selection procedure (<xreftarget="route-selection"/>).</t>target="route-selection" format="default"/>).</t> </section> <sectiontitle="Cost Computation" anchor="cost-computation">anchor="cost-computation" numbered="true" toc="default"> <name>Cost Computation</name> <t>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.</t> <t>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.</t> <t>Since nodes do not necessarily send periodic Unicast Hellos but do usually send periodic Multicast Hellos (<xreftarget="reverse-reachability"/>),target="reverse-reachability" format="default"/>), a nodeSHOULD<bcp14>SHOULD</bcp14> 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.</t> <t>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 conditionsMUST<bcp14>MUST</bcp14> be satisfied:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the cost is strictlypositive;</t> <t>ifpositive;</li> <li>if no Hello TLVs of either kind were received recently, then the cost isinfinite;</t> <t>ifinfinite;</li> <li>if the txcost is infinite, then the cost isinfinite.</t> </list></t>infinite.</li> </ul> <t>See <xreftarget="cost-computation-examples"/>target="cost-computation-examples" format="default"/> forRECOMMENDED<bcp14>RECOMMENDED</bcp14> strategies for computing a link's cost.</t> </section> </section> <sectiontitle="Routinganchor="route-maintenance" numbered="true" toc="default"> <name>Routing TableMaintenance" anchor="route-maintenance">Maintenance</name> <t>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 (modulo2^16)2<sup>16</sup>) integer that carries the originating router seqno, and metric is the announced metric.</t> <t>Before being accepted, an update is checked against the feasibility condition (<xreftarget="feasibility-condition"/>),target="feasibility-condition" format="default"/>), 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 <xreftarget="route-acquisition"/>.target="route-acquisition" format="default"/>. If the feasibility condition is satisfied, then the update cannot possibly cause a routing loop.</t> <sectiontitle="Theanchor="feasibility-condition" numbered="true" toc="default"> <name>The FeasibilityCondition" anchor="feasibility-condition">Condition</name> <t>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.</t> <t>A feasibility distance is a pair (seqno, metric), where seqno is an integer modulo2^162<sup>16</sup> 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<list style="empty"> <t>(seqno,</t> <t indent="3">(seqno, metric) < (seqno', metric')</t></list><t> when<list style="empty"> <t>seqno</t> <t indent="3">seqno > seqno' or (seqno = seqno' and metric < metric')</t></list><t> where sequence numbers are compared modulo2^16.</t>2<sup>16</sup>.</t> <t>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 <xreftarget="maintaining-fd"/>.</t>target="maintaining-fd" format="default"/>.</t> <t>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:<list style="symbols"> <t>metric</t> <ul spacing="normal"> <li>metric is infinite;or</t> <t>noor</li> <li>no entry exists in the source table indexed by (prefix, plen, router-id);or</t>or</li> <li> <t>an entry (prefix, plen, router-id, seqno', metric') exists in the source table, and either<list style="symbols"> <t>seqno'</t> <ul spacing="normal"> <li>seqno' < seqnoor</t> <t>seqnoor</li> <li>seqno = seqno' and metric <metric'.</t> </list> </t> </list> </t>metric'.</li> </ul> </li> </ul> <t>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.</t> </section> <sectiontitle="Metric Computation" anchor="metric-computation">anchor="metric-computation" numbered="true" toc="default"> <name>Metric Computation</name> <t>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 neighbourMUST<bcp14>MUST</bcp14> only satisfy the following conditions:<list style="symbols"> <t>if</t> <ul spacing="normal"> <li>if c is infinite, then M(c, m) isinfinite;</t> <t>Minfinite;</li> <li>M is strictly monotonic: M(c, m) >m.</t> </list>m.</li> </ul> <t> Additionally, the metricSHOULD<bcp14>SHOULD</bcp14> satisfy the following condition:<list style="symbols"> <t>M</t> <ul spacing="normal"> <li>M is left-distributive: if m≤<= m', then M(c, m)≤<= M(c,m').</t> </list>m').</li> </ul> <t> While strict monotonicity is essential to the integrity of the network (persistent routing loops may arise if it is not satisfied),left distributivityleft-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).</t> <t>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 theRECOMMENDED<bcp14>RECOMMENDED</bcp14> default. See also <xreftarget="filtering"/>,target="filtering" format="default"/>, which describes a technique that makes it possible to tweak the values of individual metrics without running the risk of creating routing loops.</t> </section> <sectiontitle="Route Acquisition" anchor="route-acquisition">anchor="route-acquisition" numbered="true" toc="default"> <name>Route Acquisition</name> <t>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).</t> <t>If no such entry exists:<list style="symbols"> <t>if</t> <ul spacing="normal"> <li>if the update is unfeasible, itMAY<bcp14>MAY</bcp14> beignored;</t> <t>ifignored;</li> <li>if the metric is infinite (the update is a retraction of a route we do not know about), the update isignored;</t> <t>otherwise,ignored;</li> <li>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 toseqnoseqno, and an advertised metric equal to the metric carried by theupdate.</t> </list>update.</li> </ul> <t> If such an entry exists:<list style="symbols"> <t>if</t> <ul spacing="normal"> <li>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 updateMAY<bcp14>MAY</bcp14> beignored;</t> <t>otherwise,ignored;</li> <li>otherwise, the entry's sequence number, advertised metric, metric, and router-id areupdated and,updated, and if the advertised metric is not infinite, the route's expiry timer is reset to a small multiple of theIntervalinterval value included in the update (see "RouteHoldExpiry time" in <xreftarget="parameters"/>target="parameters" format="default"/> for suggested values). If the update is unfeasible, then the (now unfeasible) entryMUST<bcp14>MUST</bcp14> be immediately unselected. If the update caused the router-id of the entry to change, an update (possibly a retraction)MUST<bcp14>MUST</bcp14> be sent in a timely manner as described in <xreftarget="triggered-updates"/>.</t> </list>target="triggered-updates" format="default"/>.</li> </ul> <t> 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 beloop-free; shouldloop-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 <xreftarget="sending-requests"/>).</t>target="sending-requests" format="default"/>).</t> <t>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.</t> <t>After the route table is updated, the route selection procedure (<xreftarget="route-selection"/>)target="route-selection" format="default"/>) is run.</t> </section> <sectiontitle="Hold Time" anchor="hold-time">anchor="hold-time" numbered="true" toc="default"> <name>Hold Time</name> <t>When a prefix P isretracted, becauseretracted (because all routes are unfeasible or have an infinitemetric (whethermetric, whether due to the expiry timer ortofor 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 (<xreftarget="overlapping-prefixes"/>).</t>target="overlapping-prefixes" format="default"/>).</t> <t>To avoid this issue, whenever a prefix P is retracted, a route table entry with infinite metric is maintained as described in <xreftarget="route-acquisition"/> above.target="route-acquisition" format="default"/>. As long as this entry is maintained, packets destined to an address within PMUST NOT<bcp14>MUST NOT</bcp14> 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 entrySHOULD<bcp14>SHOULD</bcp14> be maintained at least until it is guaranteed that no neighbour has selected the current node asnext-hopnext hop for prefix P. This can be achieved by either:<list style="symbols"> <t>waiting</t> <ul spacing="normal"> <li>waiting until the route's expiry timer has expired (<xreftarget="route-acquisition"/>);</t> <t>sendingtarget="route-acquisition" format="default"/>); or</li> <li>sending a retraction with an acknowledgment request (<xreftarget="acknowledgments"/>)target="acknowledgments" format="default"/>) to every reachable neighbour that has not explicitly retracted prefix P, and waiting for allacknowledgments.</t> </list>acknowledgments.</li> </ul> <t> The former option is simpler and ensuresthatthat, 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 isRECOMMENDED<bcp14>RECOMMENDED</bcp14> as it dramatically reduces the time for which a prefix is unreachable in the presence of aggregated routes.</t> </section> </section> <sectiontitle="Route Selection" anchor="route-selection">anchor="route-selection" numbered="true" toc="default"> <name>Route Selection</name> <t>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.</t> <t>Babel is designed to allow flexible route selection policies. As far as the algorithm's correctness is concerned, the route selection policyMUST<bcp14>MUST</bcp14> only satisfy the following properties:<list style="symbols"> <t>a</t> <ul spacing="normal"> <li>a route with infinite metric (a retracted route) is neverselected;</t> <t>anselected;</li> <li>an unfeasible route is neverselected.</t> </list>selected.</li> </ul> <t> Babel nodes using different route selection strategies will interoperate and will not create routing loops as long as these two properties hold.</t> <t>Route selectionMUST NOT<bcp14>MUST NOT</bcp14> take seqnos into account: a routeMUST NOT<bcp14>MUST NOT</bcp14> 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 persistentblackholesblack-holes if the metric being used is not left-distributive (<xreftarget="metric-computation"/>).</t>target="metric-computation" format="default"/>).</t> <t>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 <xreftarget="metric-computation"/>).target="metric-computation" format="default"/>). 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,whenthe selection of a routeis selected,increases congestion alongit increases,it, which might increase packet loss, which in turn could cause its metric to increase; thisis a feedback loop, of thekindthatof feedback loop is prone to causing persistent oscillations.</t> <t>In order to limit these kinds of instabilities, a route selection strategySHOULD<bcp14>SHOULD</bcp14> include some form of hysteresis, i.e., be sensitive to a route's history:if a route is currently selected, thenthe 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. ARECOMMENDED<bcp14>RECOMMENDED</bcp14> hysteresis algorithm is given in <xreftarget="route-selection-hysteresis"/>.</t>target="route-selection-hysteresis" format="default"/>.</t> <t>After the route selection procedure is run, triggered updates (<xreftarget="triggered-updates"/>)target="triggered-updates" format="default"/>) and requests (<xreftarget="sending-requests"/>)target="sending-requests" format="default"/>) are sent.</t> </section> <sectiontitle="Sending Updates" anchor="sending-updates">anchor="sending-updates" numbered="true" toc="default"> <name>Sending Updates</name> <t>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 nodeMAY<bcp14>MAY</bcp14> choose to send multiple copies of updates in unicast packets, especially when the number of neighbours is small.</t> <t>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.</t> <t>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.</t> <t>If an update is for a routelearnedlearnt 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 <xreftarget="metric-computation"/>.</t>target="metric-computation" format="default"/>.</t> <sectiontitle="Periodic Updates" anchor="periodic-updates">anchor="periodic-updates" numbered="true" toc="default"> <name>Periodic Updates</name> <t>Every Babel speakerMUST<bcp14>MUST</bcp14> 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 (<xreftarget="triggered-updates"/>),target="triggered-updates" format="default"/>), this full dump only needs to happen infrequently (see <xreftarget="parameters"/>target="parameters" format="default"/> for suggested intervals).</t> </section> <sectiontitle="Triggered Updates" anchor="triggered-updates">anchor="triggered-updates" numbered="true" toc="default"> <name>Triggered Updates</name> <t>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.</t> <t>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 nodeMUST<bcp14>MUST</bcp14> send an update as an urgent TLV (as defined in <xreftarget="transmission-reception"/>).target="transmission-reception" format="default"/>). Additionally, itSHOULD<bcp14>SHOULD</bcp14> make a reasonable attempt at ensuring that all reachable neighbours receive this update.</t> <t>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 copiesMUST NOT<bcp14>MUST NOT</bcp14> exceed 5, and the copiesSHOULD<bcp14>SHOULD</bcp14> be separated by a small delay, as described in <xreftarget="transmission-reception"/>.</t>target="transmission-reception" format="default"/>.</t> <t>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 nodeSHOULD<bcp14>SHOULD</bcp14> send a triggered update andSHOULD<bcp14>SHOULD</bcp14> make a reasonable attempt at ensuring that all neighbours receive this retraction.</t> <t>Finally, a nodeMAY<bcp14>MAY</bcp14> 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 haschanged,changed or because a different next hop has been selected. A nodeSHOULD NOT<bcp14>SHOULD NOT</bcp14> 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 <xreftarget="requests"/>).</t>target="requests" format="default"/>).</t> </section> <sectiontitle="Maintaininganchor="maintaining-fd" numbered="true" toc="default"> <name>Maintaining FeasibilityDistances" anchor="maintaining-fd">Distances</name> <t>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.</t> <t>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).</t> <t>If an entry (prefix, plen, router-id, seqno', metric') exists, then it is updated as follows:<list style="symbols"> <t>if</t> <ul spacing="normal"> <li>if seqno > seqno', then seqno' := seqno, metric' :=metric;</t> <t>ifmetric;</li> <li>if seqno = seqno' and metric' > metric, then metric' :=metric;</t> <t>otherwise,metric;</li> <li>otherwise, nothing needs to bedone.</t> </list></t>done.</li> </ul> <t>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.</t> <t>When the garbage-collection timer expires, the entry is removed from the source table.</t> </section> <sectiontitle="Split Horizon">numbered="true" toc="default"> <name>Split Horizon</name> <t>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 nodeSHOULD<bcp14>SHOULD</bcp14> 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.</t> <t>Split horizonSHOULD NOT<bcp14>SHOULD NOT</bcp14> 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.</t> </section> </section> <sectiontitle="Explicit Requests" anchor="requests">anchor="requests" numbered="true" toc="default"> <name>Explicit Requests</name> <t>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.</t> <t>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.</t> <sectiontitle="Handling Requests" anchor="handling-requests">anchor="handling-requests" numbered="true" toc="default"> <name>Handling Requests</name> <t>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.</t> <t>The exact behaviour is different for route requests and seqno requests.</t> <sectiontitle="Route Requests" anchor="handling-route-requests">anchor="handling-route-requests" numbered="true" toc="default"> <name>Route Requests</name> <t>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, itMUST<bcp14>MUST</bcp14> send an update (over unicast or over multicast); if such a route does not exist, itMUST<bcp14>MUST</bcp14> send a retraction for that prefix.</t> <t>When a node receives a wildcard route request, itSHOULD<bcp14>SHOULD</bcp14> send a full route table dump. Full route dumpsSHOULD<bcp14>SHOULD</bcp14> be rate-limited, especially if they are sent over multicast.</t> </section> <sectiontitle="Seqno Requests" anchor="handling-seqno-requests">anchor="handling-seqno-requests" numbered="true" toc="default"> <name>Seqno Requests</name> <t>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 prefixexists, itexists 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 (modulo2^16)2<sup>16</sup>) than the requested sequence number, the nodeMUST<bcp14>MUST</bcp14> send an update for the given prefix. If the router-idsmatchmatch, but the requested seqno is larger (modulo2^16)2<sup>16</sup>) 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 (modulo2^16)2<sup>16</sup>) and sends an update. A nodeMUST NOT<bcp14>MUST NOT</bcp14> increase its sequence number by more than 1 in reaction to a single seqno request.</t> <t>Otherwise, if the requested router-id is not its own, the received node consults thehop countHop 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:<list style="symbols"> <t>if</t> <ul spacing="normal"> <li>if the node has one or more feasible routestowardtowards the requested prefix with a next hop that is not the requesting node, then the nodeMUST<bcp14>MUST</bcp14> forward the request to the next hop of one suchroute;</t> <t>otherwise,route;</li> <li>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 nodeSHOULD<bcp14>SHOULD</bcp14> forward the request to the next hop of one suchroute.</t> </list>route.</li> </ul> <t> 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 requestSHOULD<bcp14>SHOULD</bcp14> be sent as an urgent TLV (as defined in <xreftarget="transmission-reception"/>).</t>target="transmission-reception" format="default"/>).</t> <t>A nodeSHOULD<bcp14>SHOULD</bcp14> 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 <xreftarget="transmission-reception"/>).target="transmission-reception" format="default"/>). A nodeSHOULD<bcp14>SHOULD</bcp14> compare every incoming seqno request against its list of recently forwarded seqno requests and avoid forwardingitthe request if it is redundant (i.e., ifitthe node has recently sent a request with the same prefix,router-idrouter-id, and a seqno that is not smaller modulo2^16).</t>2<sup>16</sup>).</t> <t>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 requestMUST NOT<bcp14>MUST NOT</bcp14> be duplicated: itMUST NOT<bcp14>MUST NOT</bcp14> be forwarded to a multicast address, and itMUST NOT<bcp14>MUST NOT</bcp14> 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.</t> </section> </section> <sectiontitle="Sending Requests" anchor="sending-requests">anchor="sending-requests" numbered="true" toc="default"> <name>Sending Requests</name> <t>A Babel nodeMAY<bcp14>MAY</bcp14> send a route or seqno request at anytime,time to a multicast or a unicast address; there is only one case when originating requests is required (<xreftarget="avoiding-starvation"/>).</t>target="avoiding-starvation" format="default"/>).</t> <sectiontitle="Avoiding Starvation" anchor="avoiding-starvation">anchor="avoiding-starvation" numbered="true" toc="default"> <name>Avoiding Starvation</name> <t>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.</t> <t>A node that has lost all feasible routes to a given destination but still has unexpired unfeasible routes to that destinationMUST<bcp14>MUST</bcp14> send a seqno request; if it doesn't have any such routes, itMAY<bcp14>MAY</bcp14> 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; itMAY<bcp14>MAY</bcp14> be set to any value that is larger than the diameter of the network (64 is a suitable default value).</t> <t>If the node has any (unfeasible) routes to the requested destination, then itMUST<bcp14>MUST</bcp14> send the request to at least one of the next-hop neighbours that advertised these routes, andSHOULD<bcp14>SHOULD</bcp14> send it to all of them; in any case, itMAY<bcp14>MAY</bcp14> 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.</t> <t>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.)</t> <t>In order to compensate for packet loss, a nodeSHOULD<bcp14>SHOULD</bcp14> repeat such a request a small number of times if no route becomes feasible within a short time (see "RequestTimeout"timeout" in <xreftarget="parameters"/>target="parameters" format="default"/> 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.</t> </section> <sectiontitle="Dealinganchor="request-unfeasible" numbered="true" toc="default"> <name>Dealing with UnfeasibleUpdates" anchor="request-unfeasible">Updates</name> <t>When a route's metric increases, a node might receive an unfeasible update for a route that it has currently selected. As specified in <xreftarget="feasibility-condition"/>,target="feasibility-condition" format="default"/>, the receiving node will either ignore the update or unselect the route.</t> <t>In order to keep routes from spuriously expiring because they have become unfeasible, a nodeSHOULD<bcp14>SHOULD</bcp14> 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 <xreftarget="avoiding-starvation"/> above.</t>target="avoiding-starvation" format="default"/>.</t> <t>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 nodeSHOULD<bcp14>SHOULD</bcp14> send a unicast seqno request to the neighbour that advertised the preferable update.</t> </section> <sectiontitle="Preventinganchor="request-expiring" numbered="true" toc="default"> <name>Preventing Routes fromExpiring" anchor="request-expiring">Expiring</name> <t>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.</t> <t>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 nodeSHOULD<bcp14>SHOULD</bcp14> 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 (<xreftarget="handling-route-requests"/>),target="handling-route-requests" format="default"/>), this will usually result in the route being either refreshed or retracted.</t> </section> </section> </section> </section> <sectiontitle="Protocol Encoding" anchor="protocol-encoding">anchor="protocol-encoding" numbered="true" toc="default"> <name>Protocol Encoding</name> <t>A Babel packetMUST<bcp14>MUST</bcp14> 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 packetMUST<bcp14>MUST</bcp14> 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. ItMAY<bcp14>MAY</bcp14> be silently ignored if its destination address is a global IPv6 address.</t> <t>In order to minimise the number of packets being sent while avoiding lower-layer fragmentation, a Babel nodeSHOULD<bcp14>SHOULD</bcp14> 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). ItMUST NOT<bcp14>MUST NOT</bcp14> send packets larger than the attached interface's MTU adjusted for lower-layer headers or 512 octets, whichever is larger, but not exceeding2^162<sup>16</sup> - 1 adjusted for lower-layer headers. Every Babel speakerMUST<bcp14>MUST</bcp14> 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 packetsMUST NOT<bcp14>MUST NOT</bcp14> be sent in IPv6Jumbogramsjumbograms <xreftarget="RFC2675"/>.</t> <section title="Data Types">target="RFC2675" format="default"/>.</t> <sectiontitle="Representationnumbered="true" toc="default"> <name>Data Types</name> <section numbered="true" toc="default"> <name>Representation ofintegers">Integers</name> <t>All multi-octet fields that represent integers are encoded with the most significant octet first (in Big-Endian format <xreftarget="IEN137"/>,target="IEN137" format="default"/>, also calledNetwork Order).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).</t> </section> <sectiontitle="Interval">numbered="true" toc="default"> <name>Interval</name> <t>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 of10ms,10 ms, which should cover all reasonable applications of Babel (see also <xreftarget="parameters"/>).</t>target="parameters" format="default"/>).</t> </section> <sectiontitle="Router-Id" anchor="router-id-def">anchor="router-id-def" numbered="true" toc="default"> <name>Router-Id</name> <t>A router-id is an arbitrary 8-octet value. A router-idMUST NOT<bcp14>MUST NOT</bcp14> consist of either all binary zeroes (0000000000000000 hexadecimal) or all binary ones (FFFFFFFFFFFFFFFF hexadecimal).</t> </section> <sectiontitle="Address">numbered="true" toc="default"> <name>Address</name> <t>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 (<xreftarget="update"/>).</t>target="update" format="default"/>).</t> <t>Addressencodings: <list style="symbols"> <t>AE 0: wildcardencodings (AEs): </t> <dl spacing="normal" indent="10"> <dt>AE 0:</dt><dd>Wildcard address. The value is 0 octetslong.</t> <t>AE 1: IPv4long.</dd> <dt>AE 1:</dt><dd>IPv4 address. Compression is allowed. 4 octets orless.</t> <t>AE 2: IPv6less.</dd> <dt>AE 2:</dt><dd>IPv6 address. Compression is allowed. 16 octets orless.</t> <t>AE 3: link-localless.</dd> <dt>AE 3:</dt><dd>Link-local IPv6 address. Compression is not allowed. The value is 8 octets long, a prefix of fe80::/64 isimplied.</t> </list> </t>implied.</dd> </dl> <t>The address family associatedtowith an address encoding is either IPv4 orIPv6;IPv6: it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 and 3.</t> </section> <sectiontitle="Prefixes">numbered="true" toc="default"> <name>Prefixes</name> <t>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).</t> </section> </section> <sectiontitle="Packet Format" anchor="packet-format">anchor="packet-format" numbered="true" toc="default"> <name>Packet Format</name> <t>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 <xreftarget="extensions"/>target="extensions" format="default"/> for extensibility considerations.</t><figure><artwork><![CDATA[<artwork name="" type="" align="left" alt=""><![CDATA[ 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PacketBody ...Body... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- | Packet Trailer... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Magic">The]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Magic</dt> <dd>The arbitrary but carefully chosen value 42 (decimal); packets with a first octet different from 42MUST<bcp14>MUST</bcp14> be silentlyignored.</t> <t hangText="Version">Thisignored.</dd> <dt>Version</dt> <dd>This document specifies version 2 of the Babel protocol. Packets with a second octet different from 2MUST<bcp14>MUST</bcp14> be silentlyignored.</t> <t hangText="Body length">Theignored.</dd> <dt>Body length</dt> <dd>The length in octets of the body following the packet header (excluding the Magic,VersionVersion, and Body length fields, and excluding the packettrailer).</t> <t hangText="Packet Body">Thetrailer).</dd> <dt>Packet Body</dt> <dd>The packet body; a sequence ofTLVs.</t> <t hangText="Packet Trailer">TheTLVs.</dd> <dt>Packet Trailer</dt> <dd>The packet trailer; another sequence ofTLVs.</t> </list></t>TLVs.</dd> </dl> <t>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 receiverMUST<bcp14>MUST</bcp14> 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 implementationMAY<bcp14>MAY</bcp14> 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.</t> </section> <sectiontitle="TLV Format">numbered="true" toc="default"> <name>TLV Format</name> <t>With the exception of Pad1, all TLVs have the following structure:</t><figure><artwork><![CDATA[<artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">The]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>The type of theTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="Payload">Thefields.</dd> <dt>Payload</dt> <dd>The TLV payload, which consists of a body and, for selected TLV types, an optional list ofsub-TLVs.</t> </list></t>sub-TLVs.</dd> </dl> <t>TLVs with an unknown type valueMUST<bcp14>MUST</bcp14> be silently ignored.</t> </section> <sectiontitle="Sub-TLV Format" anchor="sub-tlv-format">anchor="sub-tlv-format" numbered="true" toc="default"> <name>Sub-TLV Format</name> <t>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.</t> <t>Sub-TLVs have the same structure as TLVs. With the exception of Pad1, all TLVs have the following structure:</t><figure><artwork><![CDATA[<artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">The]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>The type of thesub-TLV.</t> <t hangText="Length">Thesub-TLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="Body">Thefields.</dd> <dt>Body</dt> <dd>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 isembedded.</t> </list></t>embedded.</dd> </dl> <t>Themost-significantmost 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-TLVMUST<bcp14>MUST</bcp14> be silently ignored, and the rest of the TLV is processed normally. If the mandatory bit is set, then the whole enclosing TLVMUST<bcp14>MUST</bcp14> be silently ignored (except for updating the parser state by a Router-Id,Next-HopNext Hop, or Update TLV, as described in the next section).</t> </section> <sectiontitle="Parser stateanchor="parser-state" numbered="true" toc="default"> <name>Parser State andencodingEncoding ofupdates" anchor="parser-state">Updates</name> <t>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 (<xreftarget="route-maintenance"/>)target="route-maintenance" format="default"/>) is split into three pieces:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the prefix,seqnoseqno, and metric are contained in the Update TLV itself (<xreftarget="update"/>);</t> <t>thetarget="update" format="default"/>);</li> <li>the router-id is taken from the Router-Id TLV that precedes the UpdateTLV,TLV and may be shared among multiple Update TLVs (<xreftarget="router-id"/>);</t> <t>thetarget="router-id" format="default"/>);</li> <li>the next hop is taken either from thesource-addresssource address of the network-layer packet that contains the Babelpacket,packet or from an explicitNext-HopNext Hop TLV (<xreftarget="next-hop"/>).</t> </list>target="next-hop" format="default"/>).</li> </ul> <t> 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,Router-IDthe Router-Id TLV itself may beomittedomitted, and the router-id is derived from the low-order bits of the advertised prefix (<xreftarget="update"/>).</t>target="update" format="default"/>).</t> <t>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:<list style="symbols"> <t>for</t> <ul spacing="normal"> <li>for each address encoding that allows compression, the current defaultprefix;prefix: this is undefined at the start of thepacket,packet and is updated by each Update TLV with the Prefix flag set (<xreftarget="update"/>);</t> <t>fortarget="update" format="default"/>);</li> <li>for each address family (IPv4 or IPv6), the currentnext-hop;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 eachNext-HopNext Hop TLV (<xreftarget="next-hop"/>);</t> <t>thetarget="next-hop" format="default"/>);</li> <li>the currentrouter-id;router-id: this is undefined at the start of the packet, and it is updated by eachRouter-IDRouter-Id TLV (<xreftarget="router-id"/>)target="router-id" format="default"/>) and by each Update TLV with Router-Id flagset.</t> </list></t>set.</li> </ul> <t>Since the parser state must be identical across implementations, it is updated before checking for mandatory sub-TLVs: parsing a TLVMUST<bcp14>MUST</bcp14> update the parser state even if the TLV is otherwise ignored due to an unknown mandatory sub-TLV or for any other reason.</t> <t>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.</t> </section> <sectiontitle="Detailsanchor="tlv-details" numbered="true" toc="default"> <name>Details of SpecificTLVs" anchor="tlv-details">TLVs</name> <sectiontitle="Pad1"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>Pad1</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 0 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ | Type = 0 | +-+-+-+-+-+-+-+-+]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 0 to indicate a Pad1TLV.</t> </list></t>TLV.</dd> </dl> <t>This TLV is silently ignored on reception. It is allowed in the packet trailer.</t> </section> <sectiontitle="PadN"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>PadN</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 1 to indicate a PadNTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="MBZ">Mustfields.</dd> <dt>MBZ</dt> <dd>Must be zero, set to 0 ontransmission.</t> </list></t>transmission.</dd> </dl> <t>This TLV is silently ignored on reception. It is allowed in the packet trailer.</t> </section> <sectiontitle="Acknowledgment Request"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>Acknowledgment Request</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+]]></artwork></figure>]]></artwork> <t>This TLV requests that the receiver send an Acknowledgment TLV within the number of centiseconds specified by the Interval field.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 2 to indicate an Acknowledgment RequestTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="Reserved">Sentfields.</dd> <dt>Reserved</dt> <dd>Sent as 0 andMUST<bcp14>MUST</bcp14> be ignored onreception.</t> <t hangText="Opaque">Anreception.</dd> <dt>Opaque</dt> <dd>An arbitrary value that will be echoed in the receiver's AcknowledgmentTLV.</t> <t hangText="Interval">ATLV.</dd> <dt>Interval</dt> <dd>A time interval in centiseconds after which the sender will assume that this packet has been lost. ThisMUST NOT<bcp14>MUST NOT</bcp14> be 0. The receiverMUST<bcp14>MUST</bcp14> send an Acknowledgment TLV before this time has elapsed (with a margin allowing for propagation time).</t> </list></t></dd> </dl> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="Acknowledgment" anchor="ack"> <figure><artwork><![CDATA[anchor="ack" numbered="true" toc="default"> <name>Acknowledgment</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+]]></artwork></figure>]]></artwork> <t>This TLV is sent by a node upon receiving an AcknowledgmentRequest.</t> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">SetRequest TLV.</t> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 3 to indicate an AcknowledgmentTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="Opaque">Setfields.</dd> <dt>Opaque</dt> <dd>Set to the Opaque value of the Acknowledgment Request that prompted thisAcknowledgment.</t> </list></t>Acknowledgment.</dd> </dl> <t>Since Opaque values are not globally unique, this TLVMUST<bcp14>MUST</bcp14> be sent to a unicast address.</t> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="Hello"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>Hello</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+]]></artwork></figure>]]></artwork> <t>This TLV is used for neighbour discovery and for determining a neighbour's reception cost.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 4 to indicate a HelloTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="Flags">Thefields.</dd> <dt>Flags</dt> <dd>The individual bits of this field specify special handling of this TLV (seebelow).</t> <t hangText="Seqno">Ifbelow).</dd> <dt>Seqno</dt> <dd>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 thisinterface.</t> <t hangText="Interval">If non-zero,interface.</dd> <dt>Interval</dt> <dd>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 unscheduledHello,Hello and doesn't carry any new information about times at which Hellos aresent.</t> </list></t>sent.</dd> </dl> <t>The Flags field is interpreted as follows:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ 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| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+]]></artwork></figure> <list style="symbols"> <t>U]]></artwork> <dl spacing="normal" indent="10"> <dt>U (Unicast) flag (8000hexadecimal): ifhexadecimal):</dt><dd>if set, then this Hello represents a Unicast Hello, otherwise it represents a MulticastHello;</t> <t>X: allHello;</dd> <dt>X:</dt><dd>all other bitsMUST<bcp14>MUST</bcp14> be sent as 0 and silently ignored onreception.</t> </list> </t>reception.</dd> </dl> <t>Every time a Hello is sent, the corresponding seqno counterMUST<bcp14>MUST</bcp14> 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 TLVMUST<bcp14>MUST</bcp14> be sent to allneighborsneighbours on this link, which can be achieved by sending to a multicastdestination,destination or by sending multiple packets to the unicast addresses of all reachable neighbours. Conversely, if the Unicast flag is set, this TLVMUST<bcp14>MUST</bcp14> 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 TLVsSHOULD NOT<bcp14>SHOULD NOT</bcp14> be sent in the same packet.</t> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="IHU"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>IHU</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure>]]></artwork> <t>An IHU ("I Heard You") TLV is used for confirming bidirectional reachability and carrying a link's transmission cost.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 5 to indicate an IHUTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="AE">Thefields.</dd> <dt>AE</dt> <dd>The encoding of the Address field. This should be 1 or 3 in most cases. As an optimisation, itMAY<bcp14>MAY</bcp14> 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 Babelprotocol.</t> <t hangText="Reserved">Sentprotocol.</dd> <dt>Reserved</dt> <dd>Sent as 0 andMUST<bcp14>MUST</bcp14> be ignored onreception.</t> <t hangText="Rxcost">Thereception.</dd> <dt>Rxcost</dt> <dd>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 isunreachable.</t> <t hangText="Interval">Anunreachable.</dd> <dt>Interval</dt> <dd>An upper bound, expressed in centiseconds, on the time after which the sending node will send a new IHU; thisMUST NOT<bcp14>MUST NOT</bcp14> be 0. The receiving node will use this value in order to compute a hold time for this symmetricassociation.</t> <t hangText="Address">Theassociation.</dd> <dt>Address</dt> <dd>The address of the destination node, in the format specified by the AE field. Address compression is notallowed.</t> </list></t>allowed.</dd> </dl> <t>Conceptually, an IHU is destined to a single neighbour. However, IHU TLVs contain an explicit destination address, andMAY<bcp14>MAY</bcp14> 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.</t> <t>IHU TLVs with an unknown value in the AE fieldMUST<bcp14>MUST</bcp14> be silently ignored.</t> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="Router-Id" anchor="router-id"> <figure><artwork><![CDATA[anchor="router-id" numbered="true" toc="default"> <name>Router-Id</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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 + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+]]></artwork></figure>]]></artwork> <t>A Router-Id TLV establishes a router-id that is implied by subsequent Update TLVs, as described in <xreftarget="parser-state"/>.target="parser-state" format="default"/>. This TLV sets the router-id even if it is otherwise ignored due to an unknown mandatory sub-TLV.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 6 to indicate a Router-IdTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="Reserved">Sentfields.</dd> <dt>Reserved</dt> <dd>Sent as 0 andMUST<bcp14>MUST</bcp14> be ignored onreception.</t> <t hangText="Router-Id">Thereception.</dd> <dt>Router-Id</dt> <dd>The router-id for routes advertised in subsequent Update TLVs. ThisMUST NOT<bcp14>MUST NOT</bcp14> consist of all zeroes or allones.</t> </list></t>ones.</dd> </dl> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="Next Hop" anchor="next-hop"> <figure><artwork><![CDATA[anchor="next-hop" numbered="true" toc="default"> <name>Next Hop</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure>]]></artwork> <t>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 <xreftarget="parser-state"/>.target="parser-state" format="default"/>. This TLV sets up thenext-hopnext hop for subsequent Update TLVs even if it is otherwise ignored due to an unknown mandatory sub-TLV.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 7 to indicate a Next HopTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="AE">Thefields.</dd> <dt>AE</dt> <dd>The encoding of the Address field. ThisSHOULD<bcp14>SHOULD</bcp14> be 1 (IPv4) or 3 (link-local IPv6), andMUST NOT<bcp14>MUST NOT</bcp14> be0.</t> <t hangText="Reserved">Sent0.</dd> <dt>Reserved</dt> <dd>Sent as 0 andMUST<bcp14>MUST</bcp14> be ignored onreception.</t> <t hangText="Next hop">Thereception.</dd> <dt>Next hop</dt> <dd>The next-hop address advertised by subsequent UpdateTLVs,TLVs for this addressfamily.</t> </list></t>family.</dd> </dl> <t>When the address family matches the network-layer protocolthatover which this packet istransported over,transported, a Next Hop TLV is not needed: in the absence of a Next Hop TLV in a given address family, thenext hopnext-hop address is taken to be the source address of the packet.</t> <t>Next Hop TLVs with an unknown value for the AE fieldMUST<bcp14>MUST</bcp14> be silently ignored.</t> <t>This TLV is self-terminating, and allows sub-TLVs.</t> </section> <sectiontitle="Update" anchor="update"> <figure><artwork><![CDATA[anchor="update" numbered="true" toc="default"> <name>Update</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure>]]></artwork> <t>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 <xreftarget="parser-state"/>.</t> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Settarget="parser-state" format="default"/>.</t> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 8 to indicate an UpdateTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="AE">Thefields.</dd> <dt>AE</dt> <dd>The encoding of the Prefixfield.</t> <t hangText="Flags">Thefield.</dd> <dt>Flags</dt> <dd>The individual bits of this field specify special handling of this TLV (seebelow).</t> <t hangText="Plen">Thebelow).</dd> <dt>Plen</dt> <dd>The length in bits of the advertised prefix. If AE is 3 (link-local IPv6), the OmittedMUSTfield <bcp14>MUST</bcp14> be0.</t> <t hangText="Omitted">The0.</dd> <dt>Omitted</dt> <dd>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 flagset.</t> <t hangText="Interval">Anset.</dd> <dt>Interval</dt> <dd>An upper bound, expressed in centiseconds, on the time after which the sending node will send a new update for this prefix. ThisMUST NOT<bcp14>MUST NOT</bcp14> 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 (<xreftarget="request-expiring"/>).</t> <t hangText="Seqno">Thetarget="request-expiring" format="default"/>).</dd> <dt>Seqno</dt> <dd>The originator's sequence number for thisupdate.</t> <t hangText="Metric">Theupdate.</dd> <dt>Metric</dt> <dd>The sender's metric for this route. The value FFFF hexadecimal (infinity) means that this is a routeretraction.</t> <t hangText="Prefix">Theretraction.</dd> <dt>Prefix</dt> <dd>The prefix being advertised. This field's size is (Plen/8 - Omitted) roundedupwards.</t> </list></t>upwards.</dd> </dl> <t>The Flags field is interpreted as follows:<figure><artwork><![CDATA[</t> <artwork name="" type="" align="left" alt=""><![CDATA[ 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ |P|R|X|X|X|X|X|X| +-+-+-+-+-+-+-+-+]]></artwork></figure> <list style="symbols"> <t>P]]></artwork> <dl spacing="normal" indent="10"> <dt>P (Prefix) flag (80hexadecimal): ifhexadecimal):</dt><dd>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 mandatorysub-TLV;</t> <t>Rsub-TLV;</dd> <dt>R (Router-Id) flag (40hexadecimal): ifhexadecimal):</dt><dd><t>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:<list> <t>if</t> <ul spacing="normal"> <li>if the length of the address is 8 octets or more, then the new router-id is taken from the 8 last octets of theaddress;</t> <t>ifaddress;</li> <li>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 IPv4address.</t> </list></t> <t>X: alladdress.</li> </ul> </dd> <dt>X:</dt><dd>all other bitsMUST<bcp14>MUST</bcp14> be sent as 0 and silently ignored onreception.</t> </list> </t>reception.</dd> </dl> <t>The prefix being advertised by an Update TLV is computed as follows:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>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 UpdateMUST<bcp14>MUST</bcp14> beignored;</t> <t>theignored;</li> <li>the next (Plen/8 - Omitted) rounded upwards octets are taken from the Prefixfield;</t> <t>iffield;</li> <li>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) arecleared;</t> <t>thecleared;</li> <li>the remaining octets are set to0.</t> </list> </t>0.</li> </ul> <t>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.</t> <t>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 UpdateMUST<bcp14>MUST</bcp14> be ignored.</t> <t>If the metric field is FFFF hexadecimal, this TLV specifies a retraction. In that case, the router-id,next-hopnext hop, and seqno are not used. AEMAY<bcp14>MAY</bcp14> then be 0, in which case this Update retracts all of the routes previously advertised by the sending interface. If the metric is finite, AEMUST NOT<bcp14>MUST NOT</bcp14> be 0; Update TLVs with finite metric and AE equal to 0MUST<bcp14>MUST</bcp14> be ignored. If the metric is infinite and AE is 0, Plen and OmittedMUST<bcp14>MUST</bcp14> both be 0; Update TLVs that do not satisfy this requirementMUST<bcp14>MUST</bcp14> be ignored.</t> <t>Update TLVs with an unknown value in the AE fieldMUST<bcp14>MUST</bcp14> be silently ignored.</t> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="Route Request"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>Route Request</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure>]]></artwork> <t>A Route Request TLV prompts the receiver to send an update for a given prefix, or a full route table dump.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 9 to indicate a Route RequestTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="AE">Thefields.</dd> <dt>AE</dt> <dd>The encoding of the Prefix field. The value 0 specifies that this is a request for a full route table dump (a wildcardrequest).</t> <t hangText="Plen">Therequest).</dd> <dt>Plen</dt> <dd>The length in bits of the requestedprefix.</t> <t hangText="Prefix">Theprefix.</dd> <dt>Prefix</dt> <dd>The prefix being requested. This field's size is Plen/8 roundedupwards.</t> </list></t>upwards.</dd> </dl> <t>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 0MUST<bcp14>MUST</bcp14> be ignored.</t> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> <sectiontitle="Seqno Request"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>Seqno Request</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+]]></artwork></figure>]]></artwork> <t>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.</t><t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set<t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 10 to indicate a Seqno RequestTLV.</t> <t hangText="Length">TheTLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="AE">Thefields.</dd> <dt>AE</dt> <dd>The encoding of the Prefix field. ThisMUST NOT<bcp14>MUST NOT</bcp14> be0.</t> <t hangText="Plen">The0.</dd> <dt>Plen</dt> <dd>The length in bits of the requestedprefix.</t> <t hangText="Seqno">Theprefix.</dd> <dt>Seqno</dt> <dd>The sequence number that is beingrequested.</t> <t hangText="Hop Count">Therequested.</dd> <dt>Hop Count</dt> <dd>The maximum number of times that this TLV may be forwarded, plus 1. ThisMUST NOT<bcp14>MUST NOT</bcp14> be0.</t> <t hangText="Reserved">Sent0.</dd> <dt>Reserved</dt> <dd>Sent as 0 andMUST<bcp14>MUST</bcp14> be ignored onreception.</t> <t hangText="Router-Id">Thereception.</dd> <dt>Router-Id</dt> <dd>The Router-Id that is being requested. ThisMUST NOT<bcp14>MUST NOT</bcp14> consist of all zeroes or allones.</t> <t hangText="Prefix">Theones.</dd> <dt>Prefix</dt> <dd>The prefix being requested. This field's size is Plen/8 roundedupwards.</t> </list></t>upwards.</dd> </dl> <t>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 (modulo2^16)2<sup>16</sup>) 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 <xreftarget="handling-seqno-requests"/>.</t>target="handling-seqno-requests" format="default"/>.</t> <t>While a Seqno RequestMAY<bcp14>MAY</bcp14> be sent to a multicast address, itMUST NOT<bcp14>MUST NOT</bcp14> be forwarded to a multicast address andMUST NOT<bcp14>MUST NOT</bcp14> be forwarded to more than one neighbour. A requestMUST NOT<bcp14>MUST NOT</bcp14> be forwarded if its Hop Count field is 1.</t> <t>This TLV isself-terminating,self-terminating and allows sub-TLVs.</t> </section> </section> <sectiontitle="Detailsnumbered="true" toc="default"> <name>Details of specificsub-TLVs">sub-TLVs</name> <sectiontitle="Pad1" anchor="pad1"> <figure><artwork><![CDATA[anchor="pad1" numbered="true" toc="default"> <name>Pad1</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ | Type = 0 | +-+-+-+-+-+-+-+-+]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 0 to indicate a Pad1sub-TLV.</t> </list></t>sub-TLV.</dd> </dl> <t>This sub-TLV is silently ignored on reception. It is allowed within any TLV that allows sub-TLVs.</t> </section> <sectiontitle="PadN"> <figure><artwork><![CDATA[numbered="true" toc="default"> <name>PadN</name> <artwork name="" type="" align="left" alt=""><![CDATA[ 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... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-]]></artwork></figure> <t>Fields : <list style="hanging" hangIndent="10"> <t hangText="Type">Set]]></artwork> <t>Fields: </t> <dl newline="false" spacing="normal" indent="10"> <dt>Type</dt> <dd>Set to 1 to indicate a PadNsub-TLV.</t> <t hangText="Length">Thesub-TLV.</dd> <dt>Length</dt> <dd>The length of the body in octets, exclusive of the Type and Lengthfields.</t> <t hangText="MBZ">Mustfields.</dd> <dt>MBZ</dt> <dd>Must be zero, set to 0 ontransmission.</t> </list></t>transmission.</dd> </dl> <t>This sub-TLV is silently ignored on reception. It is allowed within any TLV that allows sub-TLVs.</t> </section> </section> </section> <sectiontitle="IANA Considerations">numbered="true" toc="default"> <name>IANA Considerations</name> <t>IANA has registered the UDP port number 6696, called "babel", for use by the Babel protocol.</t> <t>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.</t> <t>IANA has created a registry called "Babel TLV Types". The allocation policy for this registry is Specification Required <xreftarget="RFC8126"/>target="RFC8126" format="default"/> for Types0-223,0-223 and Experimental Use for Types 224-254. The values in this registry are as follows:</t><texttable> <ttcol>Type</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <c>0</c><c>Pad1</c><c>this document</c> <c>1</c><c>PadN</c><c>this document</c> <c>2</c><c>Acknowledgment Request</c><c>this document</c> <c>3</c><c>Acknowledgment</c><c>this document</c> <c>4</c><c>Hello</c><c>this document</c> <c>5</c><c>IHU</c><c>this document</c> <c>6</c><c>Router-Id</c><c>this document</c> <c>7</c><c>Next Hop</c><c>this document</c> <c>8</c><c>Update</c><c>this document</c> <c>9</c><c>Route Request</c><c>this document</c> <c>10</c><c>Seqno Request</c><c>this document</c> <c>11</c><c>TS/PC</c><c><xref target="RFC7298"/></c> <c>12</c><c>HMAC</c><c><xref target="RFC7298"/></c> <c>13</c><c>Source-specific Update</c><c><xref target="BABEL-SS"/></c> <c>14</c><c>Source-specific Request</c><c><xref target="BABEL-SS"/></c> <c>15</c><c>Source-specific Seqno Request</c><c><xref target="BABEL-SS"/></c> <c>16</c><c>MAC</c><c><xref target="BABEL-MAC"/></c> <c>17</c><c>PC</c><c><xref target="BABEL-MAC"/></c> <c>18</c><c>Challenge Request</c><c><xref target="BABEL-MAC"/></c> <c>19</c><c>Challenge Reply</c><c><xref target="BABEL-MAC"/></c> <c>20-223</c><c>Unassigned</c><c></c> <c>224-254</c><c>Reserved<table align="center"> <thead> <tr> <th align="left">Type</th> <th align="left">Name</th> <th align="left">Reference</th> </tr> </thead> <tbody> <tr> <td align="left">0</td> <td align="left">Pad1</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">1</td> <td align="left">PadN</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">2</td> <td align="left">Acknowledgment Request</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">3</td> <td align="left">Acknowledgment</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">4</td> <td align="left">Hello</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">5</td> <td align="left">IHU</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">6</td> <td align="left">Router-Id</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">7</td> <td align="left">Next Hop</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">8</td> <td align="left">Update</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">9</td> <td align="left">Route Request</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">10</td> <td align="left">Seqno Request</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">11</td> <td align="left">TS/PC</td> <td align="left"> <xref target="RFC7298" format="default"/></td> </tr> <tr> <td align="left">12</td> <td align="left">HMAC</td> <td align="left"> <xref target="RFC7298" format="default"/></td> </tr> <tr> <td align="left">13</td> <td align="left">Reserved</td> <td align="left"></td> </tr> <tr> <td align="left">14</td> <td align="left">Reserved</td> <td align="left"></td> </tr> <tr> <td align="left">15</td> <td align="left">Reserved</td> <td align="left"></td> </tr> <tr> <td align="left">224-254</td> <td align="left">Reserved for ExperimentalUse</c><c>this document</c> <c>255</c><c>ReservedUse</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">255</td> <td align="left">Reserved for expansion of the typespace</c><c>this document</c> </texttable>space</td> <td align="left">RFC 8966</td> </tr> </tbody> </table> <t>IANA has created a registry called "Babelsub-TLVSub-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:</t><texttable> <ttcol>Type</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <c>0</c><c>Pad1</c><c>this document</c> <c>1</c><c>PadN</c><c>this document</c> <c>2</c><c>Diversity</c><c><xref target="BABEL-DIVERSITY"/></c> <c>3</c><c>Timestamp</c><c><xref target="BABEL-RTT"/></c> <c>4-111</c><c>Unassigned</c><c></c> <c>112-126</c><c>Reserved<table align="center"> <thead> <tr> <th align="left">Type</th> <th align="left">Name</th> <th align="left">Reference</th> </tr> </thead> <tbody> <tr> <td align="left">0</td> <td align="left">Pad1</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">1</td> <td align="left">PadN</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">2</td> <td align="left">Diversity</td> <td align="left"> <xref target="I-D.chroboczek-babel-diversity-routing" format="default"/></td> </tr> <tr> <td align="left">3</td> <td align="left">Timestamp</td> <td align="left"> <xref target="I-D.ietf-babel-rtt-extension" format="default"/></td> </tr> <tr> <td align="left">4-111</td> <td align="left">Unassigned</td> <td align="left"/> </tr> <tr> <td align="left">112-126</td> <td align="left">Reserved for ExperimentalUse</c><c>this document</c> <c>127</c><c>ReservedUse</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">127</td> <td align="left">Reserved for expansion of the typespace</c><c>this document</c> <c>128</c><c>Source Prefix</c><c><xref target="BABEL-SS"/></c> <c>129-239</c><c>Unassigned</c><c></c> <c>240-254</c><c>Reservedspace</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">128</td> <td align="left">Source Prefix</td> <td align="left"> <xref target="I-D.ietf-babel-source-specific" format="default"/></td> </tr> <tr> <td align="left">129-239</td> <td align="left">Unassigned</td> <td align="left"/> </tr> <tr> <td align="left">240-254</td> <td align="left">Reserved for ExperimentalUse</c><c>this document</c> <c>255</c><c>ReservedUse</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">255</td> <td align="left">Reserved for expansion of the typespace</c><c>this document</c> </texttable>space</td> <td align="left">RFC 8966</td> </tr> </tbody> </table> <t>IANAis instructed to createhas 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:</t><texttable> <ttcol>AE</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <c>0</c><c>Wildcard address</c><c>this document</c> <c>1</c><c>IPv4 address</c><c>this document</c> <c>2</c><c>IPv6 address</c><c>this document</c> <c>3</c><c>Link-local<table align="center"> <thead> <tr> <th align="left">AE</th> <th align="left">Name</th> <th align="left">Reference</th> </tr> </thead> <tbody> <tr> <td align="left">0</td> <td align="left">Wildcard address</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">1</td> <td align="left">IPv4 address</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">2</td> <td align="left">IPv6 address</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">3</td> <td align="left">Link-local IPv6address</c><c>this document</c> <c>4-223</c><c>Unassigned</c><c></c> <c>224-254</c><c>Reservedaddress</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">4-223</td> <td align="left">Unassigned</td> <td align="left"/> </tr> <tr> <td align="left">224-254</td> <td align="left">Reserved for ExperimentalUse</c><c>this document</c> <c>255</c><c>ReservedUse</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">255</td> <td align="left">Reserved for expansion of the AEspace</c><c>this document</c> </texttable>space</td> <td align="left">RFC 8966</td> </tr> </tbody> </table> <t>IANA hascreated arenamed the registry called "Babel Flags Values" to "Babel Update Flags Values". The allocation policy for this registry is Specification Required.IANA is instructed to rename this registry to "Babel Update Flags Values".The values in this registry are as follows:</t><texttable> <ttcol>Bit</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <c>0</c><c>Default prefix</c><c>this document</c> <c>1</c><c>Default Router-ID</c><c>this document</c> <c>2-7</c><c>Unassigned</c><c></c> </texttable><table align="center"> <thead> <tr> <th align="left">Bit</th> <th align="left">Name</th> <th align="left">Reference</th> </tr> </thead> <tbody> <tr> <td align="left">0</td> <td align="left">Default prefix</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">1</td> <td align="left">Default router-id</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">2-7</td> <td align="left">Unassigned</td> <td align="left"/> </tr> </tbody> </table> <t>IANAis instructed to createhas 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:</t><texttable> <ttcol>Bit</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <c>0</c><c>Unicast</c><c>this document</c> <c>1-15</c><c>Unassigned</c><c></c> </texttable><table align="center"> <thead> <tr> <th align="left">Bit</th> <th align="left">Name</th> <th align="left">Reference</th> </tr> </thead> <tbody> <tr> <td align="left">0</td> <td align="left">Unicast</td> <td align="left">RFC 8966</td> </tr> <tr> <td align="left">1-15</td> <td align="left">Unassigned</td> <td align="left"/> </tr> </tbody> </table> <t>IANAis instructed to replacehas replaced all references to RFCs 6126 and 7557 in all of the registries mentioned abovebywith references to this document.</t> </section> <sectiontitle="Security Considerations">numbered="true" toc="default"> <name>Security Considerations</name> <t>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:<list style="symbols"> <t>spoof</t> <ul spacing="normal"> <li>spoof a Babel packet, and redirect traffic by announcing a route with a smaller metric, a larger sequence number, or a longerprefix;</t> <t>spoofprefix;</li> <li>spoof a malformed packet, which could cause an insufficiently robust implementation to crash or interfere with the rest of thenetwork;</t> <t>replaynetwork;</li> <li>replay a previously captured Babel packet, which could cause traffic to be redirected,blackholedblack-holed, or otherwise interfere with thenetwork.</t> </list>network.</li> </ul> <t> 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 (<xreftarget="transmission-reception"/>).</t>target="transmission-reception" format="default"/>).</t> <t>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 isRECOMMENDED<bcp14>RECOMMENDED</bcp14> that all Babel traffic be protected by an application-layer cryptographic protocol. There are currently two suitable mechanisms, which implement differenttradeoffstrade-offs between implementation simplicity and security:<list style="symbols"> <t>Babel</t> <ul spacing="normal"> <li>Babel over DTLS <xreftarget="BABEL-DTLS"/>target="RFC8968" format="default"/> runs the majority of Babel traffic overDTLS,DTLS and leverages DTLS to authenticate nodes and provide confidentiality and integrityprotection;</t> <t>MACprotection;</li> <li>MAC authentication <xreftarget="BABEL-MAC"/>target="RFC8967" format="default"/> 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 (notreplayed).</t> </list>replayed).</li> </ul> <t> 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 Sections1.1, 1.2<xref target="RFC8967" section="1.1" sectionFormat="bare"/>, <xref target="RFC8967" section="1.2" sectionFormat="bare"/>, and7<xref target="RFC8967" section="7" sectionFormat="bare"/> of <xreftarget="BABEL-MAC"/>).target="RFC8967" format="default"/>). 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.</t> <t>Every implementation of BabelSHOULD<bcp14>SHOULD</bcp14> implement BABEL-MAC.</t> <t>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.</t> </section><section title="Acknowledgments"> <t>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 Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin Vigoureux. Earlier versions of this document greatly benefited from the input of Joel Halpern. The address compression technique was inspired by <xref target="PACKETBB"/>.</t> </section> </middle> <back> <references title="Normative References"> <reference anchor="RFC2119"><front> <title>Key words for use in RFCs to Indicate Requirement Levels</title> <author initials="S." surname="Bradner" fullname="S. Bradner"/> <date year="1997" month="March"/> </front> <seriesInfo name="BCP" value="14"/> <seriesInfo name="RFC" value="2119"/> <seriesInfo name="DOI" value="10.17487/RFC2119"/> </reference> <reference anchor="RFC8174"><front> <title>Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words</title> <author initials="B." surname="Leiba" fullname="B. Leiba"/> <date year="2017" month="May"/> </front> <seriesInfo name="BCP" value="14"/> <seriesInfo name="RFC" value="8174"/> <seriesInfo name="DOI" value="10.17487/RFC8174"/> </reference> <reference anchor="RFC8126"> <front> <title>Guidelines for Writing an IANA Considerations Section in RFCs</title> <author initials='M.' surname='Cotton' fullname='M. Cotton'></author> <author initials='B.' surname='Leiba' fullname='B. Leiba'></author> <author initials='T.' surname='Narten' fullname='T. Narten'></author> <date year='2017' month='June' /> </front> <seriesInfo name='BCP' value='26' /> <seriesInfo name='RFC' value='8126' /> </reference> <reference anchor="BABEL-MAC"><front> <title>MAC authentication for</middle> <back> <displayreference target="RFC0793" to="RFC793"/> <displayreference target="RFC2453" to="RIP"/> <displayreference target="RFC5444" to="PACKETBB"/> <displayreference target="RFC2328" to="OSPF"/> <displayreference target="I-D.chroboczek-babel-diversity-routing" to="BABEL-DIVERSITY"/> <displayreference target="I-D.ietf-babel-rtt-extension" to="BABEL-RTT"/> <displayreference target="I-D.ietf-babel-source-specific" to="BABEL-SS"/> <references> <name>References</name> <references> <name>Normative References</name> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.2119.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.8174.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.8126.xml"/> <reference anchor="RFC8967" target="https://www.rfc-editor.org/info/rfc8967"> <front> <title>MAC Authentication for the Babelrouting protocol</title>Routing Protocol</title> <author fullname="ClaraDo"Dô" initials="C."surname="Do"/>surname="Dô"> <organization/> </author> <author fullname="Weronika Kolodziejak" initials="W."surname="Kolodziejak"/>surname="Kolodziejak"> <organization/> </author> <author fullname="Juliusz Chroboczek" initials="J."surname="Chroboczek"/> <date month="August" year="2019"/></front> <seriesInfo name="Internet Draft" value="draft-ietf-babel-hmac-10"/> </reference> <reference anchor="RFC793" target="https://www.rfc-editor.org/info/rfc793"> <front> <title>Transmission Control Protocol</title> <author initials="J." surname="Postel" fullname="J. Postel"/>surname="Chroboczek"> <organization/> </author> <dateyear="1981" month="September"/>month="January" year="2021"/> </front> <seriesInfo name="RFC"value="793"/>value="8967"/> <seriesInfo name="DOI"value="10.17487/RFC0793"/>value="10.17487/RFC8967"/> </reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.0793.xml"/> </references><references title="Informative References"> <reference anchor="RFC6126"><front> <title>The Babel Routing Protocol</title> <author initials="J." surname="Chroboczek" fullname="J. Chroboczek"/> <date year="2011" month="April"/> </front> <seriesInfo name="RFC" value="6126"/> <seriesInfo name="DOI" value="10.17487/RFC6126"/> </reference> <reference anchor="RFC7557"><front> <title>Extension Mechanism for the Babel Routing Protocol</title> <author initials="J." surname="Chroboczek" fullname="J. Chroboczek"/> <date year="2015" month="May"/> </front> <seriesInfo name="RFC" value="7557"/> <seriesInfo name="DOI" value="10.17487/RFC7557"/> </reference><references> <name>Informative References</name> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.6126.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.7557.xml"/> <referenceanchor="BABEL-DTLS"><front>anchor="RFC8968" target="https://www.rfc-editor.org/info/rfc8968"> <front> <title>Babel Routing Protocol over Datagram Transport Layer Security</title> <author fullname="AntoninDecimo"Décimo" initials="A."surname="Decimo"/>surname="Décimo"> <organization/> </author> <author fullname="David Schinazi" initials="D."surname="Schinazi"/>surname="Schinazi"> <organization/> </author> <author fullname="Juliusz Chroboczek" initials="J."surname="Chroboczek"/>surname="Chroboczek"> <organization/> </author> <datemonth="June" year="2020"/></front>month="January" year="2021"/> </front> <seriesInfo name="RFC" value="8968"/> <seriesInfoname="Internet Draft" value="draft-ietf-babel-dtls-10"/>name="DOI" value="10.17487/RFC8968"/> </reference> <referenceanchor="JITTER"><front>anchor="JITTER"> <front> <title>ThesynchronizationSynchronization ofperiodic routing messages</title>Periodic Routing Messages</title> <author fullname="Sally Floyd" initials="S." surname="Floyd"/> <author fullname="Van Jacobson" initials="V." surname="Jacobson"/> <date month="April" year="1994"/> </front><seriesInfo name="IEEE/ACM<refcontent>IEEE/ACM Transactions onNetworking" value="2,Networking</refcontent> <refcontent>2, 2,122-136"/>122-136</refcontent> <seriesInfo name="DOI" value="10.1109/90.298431"/> </reference> <referenceanchor="DSDV"><front>anchor="DSDV"> <front> <title>HighlyDynamicdynamic Destination-Sequenced Distance-VectorRoutingrouting (DSDV) forMobile Computers</title>mobile computers</title> <author fullname="Charles E. Perkins" initials="C." surname="Perkins"/> <author fullname="Pravin Bhagwat" initials="P." surname="Bhagwat"/> <dateyear="1994"/>year="1994" month="October"/> </front><seriesInfo name="ACM SIGCOMM'94 Conference<refcontent>ACM SIGCOMM '94: Proceedings of the conference on CommunicationsArchitectures, Protocolsarchitectures, protocols andApplications" value="234-244"/> </reference> <reference anchor="RIP"><front> <title>RIP Version 2</title> <author fullname="G. Malkin" initials="G." surname="Malkin"/> <date month="November" year="1998"/> </front>applications</refcontent> <refcontent>234-244</refcontent> <seriesInfoname="RFC" value="2453"/>name="DOI" value="10.1145/190314.190336"/> </reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.2453.xml"/> <referenceanchor="DUAL"><front> <title>Loop-Free Routing Using Diffusing Computations</title>anchor="DUAL"> <front> <title>Loop-free routing using diffusing computations</title> <author fullname="J. J. Garcia Luna Aceves" initials="J. J." surname="Garcia Luna Aceves"/> <date month="February" year="1993"/> </front><seriesInfo name="IEEE/ACM<refcontent>IEEE/ACM Transactions onNetworking" value="1:1"/> </reference> <reference anchor="OSPF"><front> <title>OSPF Version 2</title> <author fullname="J. Moy" initials="J." surname="Moy"/> <date month="April" year="1998"/> </front>Networking</refcontent> <refcontent>1:1</refcontent> <seriesInfoname="RFC" value="2328"/>name="DOI" value="10.1109/90.222913"/> </reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.2328.xml"/> <referenceanchor="IS-IS"><front>anchor="IS-IS"> <front> <title>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)</title><author fullname="International<author> <organization>International Organization forStandardization"/>Standardization</organization> </author> <date year="2002"/> </front><seriesInfo name="ISO/IEC" value="10589:2002"/><refcontent>ISO/IEC 10589:2002</refcontent> </reference> <referenceanchor="EIGRP"><front>anchor="EIGRP"> <front> <title>EIGRP -- a Fast Routing Protocol Based on Distance Vectors</title> <author fullname="BobAlbrigtson"Albrightson" initials="B." surname="Albrightson"/> <author fullname="J. J. Garcia Luna Aceves" initials="J. J." surname="Garcia Luna Aceves"/> <author fullname="Joanne Boyle" initials="J." surname="Boyle"/> <date year="1994"/> </front><seriesInfo name="Proc. Interop" value="94"/><refcontent>Proc. Networld/Interop 94</refcontent> </reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.3561.xml"/> <referenceanchor="RFC3561" target="https://www.rfc-editor.org/info/rfc3561">anchor="ETX"> <front><title>Ad hoc On-Demand Distance Vector (AODV) Routing</title> <author initials="C." surname="Perkins" fullname="C. Perkins"/> <author initials="E." surname="Belding-Royer" fullname="E. Belding-Royer"/> <author initials="S." surname="Das" fullname="S. Das"/> <date year="2003" month="July"/> </front> <seriesInfo name="RFC" value="3561"/> <seriesInfo name="DOI" value="10.17487/RFC3561"/> </reference> <reference anchor="ETX"><front><title>A high-throughput path metric for multi-hop wireless networks</title> <author fullname="Douglas S. J. De Couto" initials="D." surname="De Couto"/> <author fullname="Daniel Aguayo" initials="D." surname="Aguayo"/> <author fullname="John Bicket" initials="J." surname="Bicket"/> <author fullname="Robert Morris" initials="R." surname="Morris"/> <dateyear="2003"/>year="2003" month="September"/> </front> <refcontent>MobiCom '03: Proceedings of the 9th annual international conference on Mobile computing and networking</refcontent> <refcontent>134-146</refcontent> <seriesInfoname="Proc. MobiCom" value="2003"/>name="DOI" value="10.1145/938985.939000"/> </reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.5444.xml"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.7298.xml"/> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D.ietf-babel-source-specific.xml"/> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D.ietf-babel-rtt-extension.xml"/> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D.chroboczek-babel-diversity-routing.xml"/> <referenceanchor="PACKETBB"><front> <title>Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format</title> <author fullname="T. Clausen" initials="T." surname="Clausen"/> <author fullname="C. Dearlove" initials="C." surname="Dearlove"/> <author fullname="J. Dean" initials="J." surname="Dean"/> <author fullname="C. Adjih" initials="C." surname="Adjih"/>anchor="IEEE802.11"> <front> <title>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</title> <author> <organization>IEEE</organization> </author> <datemonth="February" year="2009"/>month="April" year="2012"/> </front> <seriesInfoname="RFC" value="5444"/>name="IEEE" value="802.11-2012"/> <seriesInfo name="DOI" value="10.1109/ieeestd.2012.6178212"/> </reference> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.2675.xml"/> <referenceanchor="RFC7298"><front> <title>Babel Hashed Message Authentication Code (HMAC) Cryptographic Authentication</title>anchor="IEN137"> <front> <title>On Holy Wars and a Plea for Peace</title> <author initials="D."surname="Ovsienko" fullname="D. Ovsienko"/>surname="Cohen" fullname="Danny Cohen"/> <dateyear="2014" month="July"/> </front> <seriesInfo name="RFC" value="7298"/> <seriesInfo name="DOI" value="10.17487/RFC7298"/> </reference> <reference anchor="BABEL-SS"><front> <title>Source-Specific Routing in Babel</title> <author initials="M" surname="Boutier" fullname="Matthieu Boutier"/> <author initials="J" surname="Chroboczek" fullname="Juliusz Chroboczek"/> <date month="April" day="11" year="2019"/> </front> <seriesInfo name="Internet-Draft" value="draft-ietf-babel-source-specific-05" /> </reference> <reference anchor="BABEL-RTT"><front> <title>Delay-based Metric Extension for the Babel Routing Protocol</title> <author initials="B" surname="Jonglez" fullname="Baptiste Jonglez"/> <author initials="J" surname="Chroboczek" fullname="Juliusz Chroboczek"/> <date month="April" day="26" year="2019"/> </front> <seriesInfo name="Internet-Draft" value="draft-ietf-babel-rtt-extension-00" /> </reference> <reference anchor="BABEL-DIVERSITY"><front> <title>Diversity Routing for the Babel Routing Protocol</title> <author initials="J" surname="Chroboczek" fullname="Juliusz Chroboczek"/> <date month="February" day="15" year="2016"/> </front> <seriesInfo name="Internet-Draft" value="draft-chroboczek-babel-diversity-routing-01" /> </reference> <reference anchor="IEEE802.11"><front> <title>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</title> <author><organization>IEEE</organization></author> <date day="5" month="April" year="2012"/> </front> <seriesInfo name='IEEE' value='802.11-2012' /> <seriesInfo name='DOI' value='10.1109/ieeestd.2012.6178212' /> </reference> <reference anchor="RFC2675"><front> <title>IPv6 Jumbograms</title> <author initials="D." surname="Borman" fullname="D. Borman"/> <author initials="S." surname="Deering" fullname="S. Deering"/> <author initials="R." surname="Hinden" fullname="R. Hinden"/> <date year="1999" month="August"/> </front> <seriesInfo name="RFC" value="2675"/> <seriesInfo name="DOI" value="10.17487/RFC2675"/> </reference> <reference anchor="IEN137"><front> <title>On holy wars and a plea for peace</title> <author initials="D." surname="Cohen" fullname="Dany Cohen"/> <date day="1" month="April" year="1980"/>day="1" month="April" year="1980"/> </front> <seriesInfo name="IEN" value="137"/> </reference> </references> </references> <sectiontitle="Costnumbered="true" toc="default"> <name>Cost and MetricComputation">Computation</name> <t>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 <xreftarget="cost-computation"/>target="cost-computation" format="default"/> and <xreftarget="metric-computation"/>.target="metric-computation" format="default"/>. 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.</t> <t>In summary, a node maintains per-neighbour statistics about the last 16 received Hello TLVs of each kind (<xreftarget="hello-history"/>),target="hello-history" format="default"/>), it computes costs by using the 2-out-of-3 strategy (<xreftarget="k-j"/>)target="k-j" format="default"/>) on wiredlinks,links andETXExpected Transmission Cost (ETX) (<xreftarget="etx"/>)target="etx" format="default"/>) on wireless links. It uses an additive algebra for metric computation (<xreftarget="metric-computation"/>).</t>target="metric-computation" format="default"/>).</t> <sectiontitle="Maintaininganchor="hello-history" numbered="true" toc="default"> <name>Maintaining HelloHistory" anchor="hello-history">History</name> <t>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.</t> <t>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:<list style="symbols"> <t>if</t> <ul spacing="normal"> <li>if the two differ by more than 16 (modulo2^16),2<sup>16</sup>), then the sending node has probably rebooted and lost its sequence number; the whole associated neighbour table entry is flushed and a new one iscreated;</t> <t>otherwise,created;</li> <li>otherwise, if the received nr is smaller (modulo2^16)2<sup>16</sup>) than the expected sequence number ne, then the sending node has increased its Hello interval withoutusour noticing; the receiving node removes the last (ne - nr) entries from this neighbour's Hello history (we "undohistory");</t> <t>otherwise,history");</li> <li>otherwise, if nr is larger (modulo2^16)2<sup>16</sup>) 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").</t> </list>"fast-forward").</li> </ul> <t> 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).</t> <t>Whenever eitherHellohello timer associatedtowith 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).</t> </section> <sectiontitle="Cost Computation" anchor="cost-computation-examples">anchor="cost-computation-examples" numbered="true" toc="default"> <name>Cost Computation</name> <t>This section describes two algorithms suitable for computing costs (<xreftarget="cost-computation"/>)target="cost-computation" format="default"/>) based on Hello history. <xreftarget="k-j"/>target="k-j" format="default"/> applies to wiredlinks,links and <xreftarget="etx"/>target="etx" format="default"/> to wireless links.RECOMMENDED<bcp14>RECOMMENDED</bcp14> default values of the parameters that appear in these algorithms are given in <xreftarget="parameters"/>.</t>target="parameters" format="default"/>.</t> <sectiontitle="k-out-of-j" anchor="k-j">anchor="k-j" numbered="true" toc="default"> <name>k-out-of-j</name> <t>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.</t> <t>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.</t> <t>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.</t> <t>The cost of a link performing k-out-of-j link sensing is defined as follows:<list style="symbols"> <t>cost</t> <ul spacing="normal"> <li>cost = FFFF hexadecimal if rxcost = FFFFhexadecimal;</t> <t>costhexadecimal;</li> <li>cost = txcostotherwise.</t> </list> </t>otherwise.</li> </ul> </section> <sectiontitle="ETX" anchor="etx">anchor="etx" numbered="true" toc="default"> <name>ETX</name> <t>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 oflink-qualitylink quality estimation.</t> <t>The Expected Transmission Cost algorithm, or ETX <xreftarget="ETX"/>,target="ETX" format="default"/>, is a simplelink-qualitylink quality estimation algorithm that is designed to work well with the IEEE 802.11 MAC <xreftarget="IEEE802.11"/>.target="IEEE802.11" format="default"/>. 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.</t> <t>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 be256 / beta.</t>256/beta.</t> <t>Let alpha be MIN(1, 256/txcost), an estimate of the probability of successfully sending a Hello TLV. The cost is then computed by<list style="empty"><t>cost</t> <t indent="3">cost = 256/(alpha *beta)</t></list>beta)</t> <t> or, equivalently,<list style="empty"><t>cost</t> <t indent="3">cost = (MAX(txcost, 256) * rxcost) /256.</t></list> </t>256.</t> <t>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 ETXlink-qualitylink quality estimation will not route through neighbouring nodes unless they send periodic Multicast Hellos (possibly in addition to Unicast Hellos).</t> </section> </section> <sectiontitle="Route selectionanchor="route-selection-hysteresis" numbered="true" toc="default"> <name>Route Selection andhysteresis" anchor="route-selection-hysteresis">Hysteresis</name> <t>Route selection (<xreftarget="route-selection"/>)target="route-selection" format="default"/>) 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 (<xreftarget="etx"/>),target="etx" format="default"/>), 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.</t> <t>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 (seeSection 3.7 of<xreftarget="RFC793"/>)target="RFC0793" section="3.7" sectionFormat="of" format="default"/>) 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).</t> <t>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-termestimateestimates of the route's quality indicate that switching is profitable.</t> </section> </section> <sectiontitle="Protocol parameters" anchor="parameters">anchor="parameters" numbered="true" toc="default"> <name>Protocol Parameters</name> <t>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.</t> <t>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 as10ms,10 ms, such low values would cause significant amounts of protocol traffic for little practical benefit.</t> <t>The following values have been found to work well in a variety ofenvironments,environments and are thereforeRECOMMENDED<bcp14>RECOMMENDED</bcp14> default values:<list style="empty"> <t>Multicast Hello Interval: 4 seconds.</t> <t>Unicast</t> <dl spacing="normal" indent="10"> <dt>Multicast Hello interval:</dt><dd>4 seconds.</dd> <dt>Unicast HelloInterval: infiniteinterval:</dt><dd>infinite (no Unicast Hellos aresent).</t> <t>Link cost: estimatedsent).</dd> <dt>Link cost:</dt><dd>estimated using ETX on wireless links; 2-out-of-3 with C=96 on wiredlinks.</t> <t>IHU Interval: thelinks.</dd> <dt>IHU interval:</dt><dd>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 losslesslinks.</t> <t>Update Interval: 4links.</dd> <dt>Update interval:</dt><dd>4 times the Multicast Hellointerval.</t> <t>IHUinterval.</dd> <dt>IHU HoldTime: 3.5time:</dt><dd>3.5 times the advertised IHUinterval.</t> <t>Routeinterval.</dd> <dt>Route ExpiryTime: 3.5time:</dt><dd>3.5 times the advertised updateinterval.</t> <t>Request timeout: initiallyinterval.</dd> <dt>Request timeout:</dt><dd>initially 2 seconds, doubled every time a request is resent, up to a maximum of threetimes.</t> <t>Urgent timeout: 0.2 seconds.</t> <t>Sourcetimes.</dd> <dt>Urgent timeout:</dt><dd>0.2 seconds.</dd> <dt>Source GCtime: 3 minutes.</t> </list></t>time:</dt><dd>3 minutes.</dd> </dl> </section> <sectiontitle="Route filtering" anchor="filtering">anchor="filtering" numbered="true" toc="default"> <name>Route Filtering</name> <t>Route filtering is a procedure where an instance of a routing protocol either discards some of the routes announced by itsneighbours,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 <xreftarget="metric-computation"/>:target="metric-computation" format="default"/>: Babel can use any metric that is strictly monotonic, including one that assigns an infinite metric to a selected subset of routes. (See also <xreftarget="handling-requests"/>,target="handling-requests" format="default"/>, where requests for nonexistent routes are treated in the same way as requests for routes with infinite metric.)</t> <t>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.</t> <t>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.</t> <t>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/320.0.0.0/32, and 224.0.0.0/8.</t> </section> <sectiontitle="Considerationsanchor="extensions" numbered="true" toc="default"> <name>Considerations forprotocol extensions" anchor="extensions">Protocol Extensions</name> <t>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:<list style="symbols"> <t>increasing</t> <ul spacing="normal"> <li>increasing the version number in the packetheader;</t> <t>definingheader;</li> <li>defining newTLVs;</t> <t>definingTLVs;</li> <li>defining new sub-TLVs (with or without the mandatory bitset);</t> <t>definingset);</li> <li>defining newAEs;</t> <t>usingAEs;</li> <li>using the packettrailer.</t> </list></t>trailer.</li> </ul> <t>This appendix is intended to guide designers of protocol extensions in choosing a particular encoding.</t> <t>The version number in the Babel header should only be increased if the new version is not backwards compatible with the original protocol.</t> <t>In many cases, an extension could be implemented either by defining a newTLV,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 anon-mandatorynonmandatory sub-TLV to the Update TLV, or by adding a mandatory sub-TLV.</t> <t>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 anon-mandatorynonmandatory sub-TLV, the TLV is parsed and acted upon, and only the unknown sub-TLV is silently ignored. Therefore, anon-mandatorynonmandatory 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).</t> <t>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 themself-terminating,self-terminating and allow attaching sub-TLVs to them.</t> <t>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.</t> <t>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 toparse, andparse and, inparticularparticular, should not require stateful parsing.</t> </section> <sectiontitle="Stub Implementations">numbered="true" toc="default"> <name>Stub Implementations</name> <t>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 adouble-stackdual-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 a20000-entry20,000-entry route table and the associated source table.</t> <t>Babel is also a reasonably simple protocol. One complete implementation consists of less than12 00012,000 lines of C code, and it compiles to less than120 kB120 KB of text on a 32-bit CISC architecture; about half of this figure is due to protocol extensions and user-interface code.</t> <t>Nonetheless, in some very constrained environments, such as PDAs, microwave ovens, or abacuses, it may be desirable to have subset implementations of the protocol.</t> <t>There are many different definitions of a stub router, but for the needs of thissectionsection, a stub implementation of Babel is one that announces one or more directly attached prefixes into a Babel network but doesn'treannouncere-announce any routes that it has learnt from its neighbours, and always prefers the direct route to a directly attached prefix to a routelearnedlearnt over the Babel protocol, even when the prefixes are the same. It may either maintain a full routingtable,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.</t> <t>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 itannounces and,announces, and it should be able to reply to route requests.</t> <t>Experience shows that an IPv6-only stub implementation of Babel can be written in less than10001,000 lines of C code and compile to13 kB13 KB of text on 32-bit CISC architecture.</t> </section> <sectiontitle="Compatibilitynumbered="true" toc="default"> <name>Compatibility withprevious versions">Previous Versions</name> <t>The protocol defined in this document is a successor to the protocol defined in <xreftarget="RFC6126"/>target="RFC6126" format="default"/> and <xreftarget="RFC7557"/>.target="RFC7557" format="default"/>. 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.</t> <t>There are three optional features that make this protocol incompatible with its predecessor. First of all, RFC 6126 did not define UnicasthellosHellos (<xreftarget="reverse-reachability"/>),target="reverse-reachability" format="default"/>), and an implementation of RFC 6126 willmis-interpretmisinterpret 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 (<xreftarget="sub-tlv-format"/>),target="sub-tlv-format" format="default"/>), andthus,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.</t> <t>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.</t> <t>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 modifiedtoeither 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.</t> <t>There are other changes, but these are not of a nature to prevent interoperability:<list style="symbols"> <t>the</t> <ul spacing="normal"> <li>the conditions on route acquisition (<xreftarget="route-acquisition"/>)target="route-acquisition" format="default"/>) have beenrelaxed;</t> <t>routerelaxed;</li> <li>route selection should no longer use the route's sequence number (<xreftarget="route-selection"/>);</t> <t>thetarget="route-selection" format="default"/>);</li> <li>the format of the packet trailer has been defined (<xreftarget="packet-format"/>);</t> <t>router-idstarget="packet-format" format="default"/>);</li> <li>router-ids with a value of all-zeros or all-ones have been forbidden (<xreftarget="router-id-def"/>);</t> <t>thetarget="router-id-def" format="default"/>);</li> <li>the compression state is now specific to an address family rather than an address encoding (<xreftarget="parser-state"/>);</t> <t>packettarget="parser-state" format="default"/>);</li> <li>packet pacing is now recommended (<xreftarget="transmission-reception"/>).</t> </list></t>target="transmission-reception" format="default"/>).</li> </ul> </section> <sectiontitle="Changes from previous versions"> <t>[RFC Editor: Please delete this section before publication.]</t> <section title="Changes since RFC 6126"> <t><list style="symbols"> <t>Changed UDP portnumbered="false" toc="default"> <name>Acknowledgments</name> <t>A number of people have contributed text and ideas to6696.</t> <t>Consistently use router-id rather than id.</t> <t>Clarified that the source garbage collection timer is reset after sending an update even ifthis specification. The authors are particularly indebted to <contact fullname="Matthieu Boutier"/>, <contact fullname="Gwendoline Chouasne"/>, <contact fullname="Margaret Cullen"/>, <contact fullname="Donald Eastlake"/>, <contact fullname="Toke Høiland-Jørgensen"/>, <contact fullname="Benjamin Kaduk"/>, <contact fullname="Joao Sobrinho"/>, and <contact fullname="Martin Vigoureux"/>. The previous version of this specification <xref target="RFC6126" format="default"/> greatly benefited from theentryinput of <contact fullname="Joel Halpern"/>. The address compression technique wasnot modified.</t> <t>In section "Seqno Requests", fixed an erroneous "route request".</t> <t>In the description of the Seqno Request TLV, added the description of the Router-Id field.</t> <t>Made router-ids all-0 and all-1 forbidden.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-00"> <t><list style="symbols"> <t>Added security considerations.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-01"> <t><list style="symbols"> <t>Integrated the format of sub-TLVs.</t> <t>Mentioned for each TLV whether it supports sub-TLVs.</t> <t>Added <xref target="extensions"/>.</t> <t>Added a mandatory bit in sub-TLVs.</t> <t>Changed compression state to be per-AF rather than per-AE.</t> <t>Added implementation hint for the routing table.</t> <t>Clarified how router-ids are computed when bit 0x40 is set in Updates.</t> <t>Relaxed the conditions for sending requests, and tightened the conditions for forwarding requests.</t> <t>Clarified that neighbours should be acquired at some point, but it doesn't matter when.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-02"> <t><list style="symbols"> <t>Added Unicast Hellos.</t> <t>Added unscheduled (interval-less) Hellos.</t> <t>Changed Appendix A to consider Unicast and unscheduled Hellos.</t> <t>Changed Appendix B to agree with the reference implementation.</t> <t>Added optional algorithm to avoid the hold time.</t> <t>Changed the table of pending seqno requests to be indexed by router-id in addition to prefixes.</t> <t>Relaxed the route acquisition algorithm.</t> <t>Replaced minimal implementations by stub implementations.</t> <t>Added acknowledgments section.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-03"> <t><list style="symbols"> <t>Clarified that all the data structures are conceptual.</t> <t>Made sending and receiving Multicast Hellos a SHOULD, avoids expressing any opinion about Unicast Hellos.</t> <t>Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4).</t> <t>Made hold-time into a SHOULD rather than MUST.</t> <t>Clarified that Seqno Requests are for a finite-metric Update.</t> <t>Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV that allows sub-TLVs.</t> <t>Updated IANA Considerations.</t> <t>Updated Security Considerations.</t> <t>Renamed routing table back to route table.</t> <t>Made buffering outgoing updates a SHOULD.</t> <t>Weakened advice to use modified EUI-64 in router-ids.</t> <t>Added information about sending requests to Appendix B.</t> <t>A number of minor wording changes and clarifications.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-03"> <t>Minor editorial changes.</t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-04"> <t><list style="symbols"> <t>Renamed isotonicity to left-distributivity.</t> <t>Minor clarifications to unicast hellos.</t> <t>Updated requirements boilerplate to RFC 8174.</t> <t>Minor editorial changes.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-05"> <t><list style="symbols"> <t>Added information about the packet trailer, now that it is usedinspired bydraft-ietf-babel-hmac.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-06"> <t><list style="symbols"> <t>Added references to security documents.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-07"> <t><list style="symbols"> <t>Added list of obsoleted drafts to the abstract.</t> <t>Updated references.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-08"> <t><list style="symbols"> <t>Added recommendation that route selection should not take seqnos into account.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-09"> <t><list style="symbols"> <t>Editorial changes only.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-10"> <t><list style="symbols"> <t>Editorial changes only.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-11"> <t><list style="symbols"> <t>Added recommendation that control traffic should be carried over IPv6 only.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-12"> <t><list style="symbols"> <t>Removed appendix about software availability.</t> <t>Expanded appendix about recommended values and added more references to it in the body of the document.</t> <t>Added appendix about route filtering.</t> <t>Clarified definition of mandatory bit.</t> <t>Added recommendations for packet pacing.</t> <t>Made time limiting of full updates a SHOULD.</t> <t>Normative language in a few more places.</t> <t>Removed normative language from stub implementations.</t> <t>Added requirement to clear the undefined bits in an Update.</t> <t>Added error checking requirements.</t> <t>Reworked security considerations.</t> <t>Added "in octets" and "in bits" in random places.</t> <t>Inserted full IANA registries.</t> <t>Editorial changes.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-13"> <t><list style="symbols"> <t>Added a section about compatibility with 6126.</t> <t>Added AE registry to IANA considerations.</t> <t>Replaced Babel-HMAC with Babel-MAC, consistent with the change in draft-ietf-babel-hmac.</t> <t>Removed section about external sources of willingness; filtering is a better approach.</t> <t>Added recommendation to use a cost of 96 on wired links.</t> <t>Editorial changes.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-14"> <t><list style="symbols"> <t>Added unscheduled Hellos to compatibility considerations.</t> <t>Created new appendix about route selection.</t> <t>Reworked security considerations.</t> <t>Added some comments about packet pacing and low update intervals.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-15"> <t><list style="symbols"> <t>Implementing Babel-MAC is now recommended.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-16"> <t><list style="symbols"> <t>Make the values in Appendix B normatively recommended defaults.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-17"> <t><list style="symbols"> <t>Hysteresis in route selection is now RECOMMENDED.</t> <t>Additive metric algebra is now RECOMMENDED default.</t> <t>2-out-of-3 cost computation is now RECOMMENDED on LANs.</t> <t>Reference to RFC 793 Section 3.7 added as exponential smoothing example.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-18"> <t><list style="symbols"> <t>Reserved Address Encodings 224-254 for Experimental Use, and 255 for future expansion.</t> </list></t> </section> <section title="Changes since draft-ietf-babel-rfc6126bis-19"> <t><list style="symbols"> <t>Mention that multi-octet fields are in big-endian.</t> <t>Minor typos and clarifications.</t> </list></t> </section><xref target="RFC5444" format="default"/>.</t> </section> </back> </rfc>