| RFC 8966 | The Babel Routing Protocol | January 2021 |
| Chroboczek & Schinazi | Standards Track | [Page] |
Babel is a loop-avoiding, distance-vector routing protocol that isrobust and efficient both in ordinary wired networks and in wireless meshnetworks. This document describes the Babel routing protocol andobsoletes RFC 6126 and RFC 7557.¶
This is an Internet Standards Track document.¶
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 7841.¶
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained athttps://www.rfc-editor.org/info/rfc8966.¶
Copyright (c) 2021 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.¶
Babel is a loop-avoiding distance-vector routing protocol that isdesigned to be robust and efficient both in networks using prefix-basedrouting and in networks using flat routing ("mesh networks"), and both inrelatively stable wired networks and in highly dynamic wireless networks.This document describes the Babel routing protocol and obsoletes[RFC6126] and[RFC7557].¶
The main property that makes Babel suitable for unstable networks isthat, unlike naive distance-vector routing protocols[RIP],it strongly limits the frequency and duration of routing pathologies suchas routing loops and black-holes during reconvergence. Even aftera mobility event is detected, a Babel network usually remains loop-free.Babel then quickly reconverges to a configuration that preserves theloop-freedom and connectedness of the network, but is not necessarilyoptimal; in many cases, this operation requires no packet exchanges atall. Babel then slowly converges, in a time on the scale of minutes, toan optimal configuration. This is achieved by using sequenced routes,a technique pioneered by Destination-Sequenced Distance-Vector routing[DSDV].¶
More precisely, Babel has the following properties:¶
Babel has provisions for link quality estimation and for fairlyarbitrary metrics. When configured suitably, Babel can implementshortest-path routing, or it may use a metric based, for example, onmeasured packet loss.¶
Babel nodes will successfully establish an association even when theyare configured with different parameters. For example, a mobile node thatis low on battery may choose to use larger time constants (hello and updateintervals, etc.) than a node that has access to wall power. Conversely, anode that detects high levels of mobility may choose to use smaller timeconstants. The ability to build such heterogeneous networks makes Babelparticularly adapted to the unmanaged or wireless environment.¶
Finally, Babel is a hybrid routing protocol, in the sense that it cancarry routes for multiple network-layer protocols (IPv4 and IPv6),regardless of which protocol the Babel packets are themselves beingcarried over.¶
Babel has two limitations that make it unsuitable for use in someenvironments. First, Babel relies on periodic routing table updatesrather than using a reliable transport; hence, in large, stable networksit generates more traffic than protocols that only send updates when thenetwork topology changes. In such networks, protocols such as OSPF[OSPF], IS-IS[IS-IS], or the Enhanced InteriorGateway Routing Protocol (EIGRP)[EIGRP] might be moresuitable.¶
Second, unless the second algorithm described inSection 3.5.4is 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 availableagain, it does apply to any shorter prefix that covers it. This may makethose implementations of Babel that do not implement the optionalalgorithm described inSection 3.5.4 unsuitable for use innetworks that implement automatic prefix aggregation.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14[RFC2119][RFC8174] when, and only when, they appear in all capitals, as shown here.¶
Babel is a loop-avoiding distance-vector protocol: it is based on theBellman-Ford algorithm, just like the venerable RIP[RIP],but includes a number of refinements that either prevent loop formationaltogether, or ensure that a loop disappears in a timely manner anddoesn't form again.¶
Conceptually, Bellman-Ford is executed in parallel for every source ofrouting information (destination of data traffic). In the followingdiscussion, we fix a source S; the reader will recall that the samealgorithm is executed for all sources.¶
For every pair of neighbouring nodes A and B, Babel computes anabstract value known as the cost of the link from A to B, writtenC(A, B). Given a route between any two (not necessarilyneighbouring) nodes, the metric of the route is the sum of the costs ofall the links along the route. The goal of the routing algorithm is tocompute, for every source S, the tree of routes of lowest metric to S.¶
Costs and metrics need not be integers. In general, they can be valuesin any algebra that satisfies two fairly general conditions(Section 3.5.2).¶
A Babel node periodically sends Hello messages to all of itsneighbours; it also periodically sends an IHU ("I Heard You") message toevery neighbour from which it has recently heard a Hello. From theinformation derived from Hello and IHU messages received from its neighbourB, a node A computes the cost C(A, B) of the link from A to B.¶
Every node A maintains two pieces of data: its estimated distance to S,written D(A), and its next-hop router to S, written NH(A). Initially, D(S)= 0, D(A) is infinite, and NH(A) is undefined.¶
Periodically, every node B sends to all of its neighbours a routeupdate, a message containing D(B). When a neighbour A of B receives theroute update, it checks whether B is its selected next hop; if that is thecase, then NH(A) is set to B, and D(A) is set to C(A, B) + D(B). If thatis not the case, then A compares C(A, B) + D(B) to its current value ofD(A). If that value is smaller, meaning that the received updateadvertises a route that is better than the currently selected route, thenNH(A) is set to B, and D(A) is set to C(A, B) + D(B).¶
A number of refinements to this algorithm are possible, and are used byBabel. In particular, convergence speed may be increased by sendingunscheduled "triggered updates" whenever a major change in the topology isdetected, in addition to the regular, scheduled updates. Additionally,a node may maintain a number of alternate routes, which are beingadvertised by neighbours other than its selected neighbour, and which canbe used immediately if the selected route were to fail.¶
It is well known that a naive application of Bellman-Ford to distributedrouting can cause transient loops after a topology change. Consider forexample the following topology:¶
B 1 /| 1 / |S --- A |1 \ | 1 \| C¶
After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.¶
Suppose now that the link between S and A fails:¶
B 1 /| / |S A |1 \ | 1 \| C¶
When it detects the failure of the link, A switches its next hop toB (which is still advertising a route to S with metric 2), and advertisesa metric equal to 3, and then advertises a new route with metric 3. Thisprocess of nodes changing selected neighbours and increasing their metriccontinues until the advertised metric reaches "infinity", a value largerthan all the metrics that the routing protocol is able to carry.¶
Bellman-Ford is a very robust algorithm: its convergence propertiesare preserved when routers delay route acquisition or when theydiscard some updates. Babel routers discard received routeannouncements unless they can prove that accepting them cannotpossibly cause a routing loop.¶
More formally, we define a condition over route announcements, known asthe "feasibility condition", that guarantees the absence of routing loopswhenever all routers ignore route updates that do not satisfy thefeasibility condition. In effect, this makes Bellman-Ford into a familyof routing algorithms, parameterised by the feasibility condition.¶
Many different feasibility conditions are possible. For example, BGPcan be modelled as being a distance-vector protocol with a (ratherdrastic) feasibility condition: a routing update is only accepted when thereceiving node's AS number is not included in the update's AS_PATHattribute (note that BGP's feasibility condition does not ensure theabsence of transient "micro-loops" during reconvergence).¶
Another simple feasibility condition, used in the Destination-SequencedDistance-Vector (DSDV) routing protocol[DSDV] and in theAd hoc On-Demand Distance Vector (AODV) protocol[RFC3561],stems from the following observation: a routing loop can only arise aftera router has switched to a route with a larger metric than the route thatit had previously selected. Hence, one may define that a route isfeasible when its metric at the local node would be no larger thanthe metric of the currently selected route, i.e., an announcement carryinga metric D(B) is accepted by A when C(A, B) + D(B) <= D(A). If allrouters obey this constraint, then the metric at every router isnonincreasing, and the following invariant is always preserved: if A hasselected B as its next hop, then D(B) < D(A), which implies that theforwarding graph is loop-free.¶
Babel uses a slightly more refined feasibility condition, derived fromEIGRP[DUAL]. Given a router A, define the feasibilitydistance of A, written FD(A), as the smallest metric that A has everadvertised for S to any of its neighbours. An update sent by a neighbourB of A is feasible when the metric D(B) advertised by B is strictlysmaller than A's feasibility distance, i.e., when D(B) < FD(A).¶
It is easy to see that this latter condition is no more restrictive thanDSDV-feasibility. Suppose that node A obeys DSDV-feasibility; then D(A) isnonincreasing, hence at all times D(A) <= FD(A). Suppose now thatA receives a DSDV-feasible update that advertises a metric D(B). Since theupdate is DSDV-feasible, C(A, B) + D(B) <= D(A), hence D(B) < D(A),and since D(A) <= FD(A), D(B) < FD(A).¶
To see that it is strictly less restrictive, consider the followingdiagram, 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 thecurrently selected route:¶
B1 / \ 1 / \S A \ /1 \ / 4 C¶
To show that this feasibility condition still guarantees loop-freedom,recall that at the time when A accepts an update from B, the metric D(B)announced by B is no smaller than FD(B); since it is smaller than FD(A),at that point in time FD(B) < FD(A). Since this property is preservedwhen A sends updates and also when it picks a different next hop, itremains true at all times, which ensures that the forwarding graph has noloops.¶
Obviously, the feasibility conditions defined above cause starvationwhen a router runs out of feasible routes. Consider the following diagram,where both A and B have selected the direct route to S:¶
A1 /| D(A) = 1 / | FD(A) = 1S |1 \ | D(B) = 22 \| FD(B) = 2 B¶
Suppose now that the link between A and S breaks:¶
A | | FD(A) = 1S |1 \ | D(B) = 22 \| FD(B) = 2 B¶
The only route available from A to S, the one that goes through B, isnot feasible: A suffers from spurious starvation. At that point, thewhole subtree suffering from starvation must be reset, which isessentially what EIGRP does when it performs a global synchronisation ofall the routers in the starving subtree (the "active" phase of EIGRP).¶
Babel reacts to starvation in a less drastic manner, by using sequencedroutes, a technique introduced by DSDV and adopted by AODV. In addition toa metric, every route carries a sequence number, a nondecreasing integerthat is propagated unchanged through the network and is only everincremented by the source; a pair (s, m), where s is a sequence number andm a metric, is called a distance.¶
A received update is feasible when either it is more recent than thefeasibility distance maintained by the receiving node, or it is equallyrecent and the metric is strictly smaller. More formally, if FD(A) =(s, m), then an update carrying the distance (s', m') is feasiblewhen either s' > s, or s = s' and m' < m.¶
Assuming the sequence number of S is 137, the diagram above becomes:¶
A | | FD(A) = (137, 1)S |1 \ | D(B) = (137, 2)2 \| FD(B) = (137, 2) B¶
After S increases its sequence number, and the new sequence number ispropagated to B, we have:¶
A | | FD(A) = (137, 1)S |1 \ | D(B) = (138, 2)2 \| FD(B) = (138, 2) B¶
at which point the route through B becomes feasible again.¶
Note that while sequence numbers are used for determining feasibility,they are not used in route selection: a node ignores the sequence numberwhen selecting the best route to a given destination(Section 3.6). Doing otherwise would causeroute oscillation while a sequence number propagates through the network,and might even cause persistent black-holes with some exotic metrics.¶
In DSDV, the sequence number of a source is increased periodically.A route becomes feasible again after the source increases its sequencenumber, and the new sequence number is propagated through the network,which may, in general, require a significant amount of time.¶
Babel takes a different approach. When a node detects that it issuffering from a potentially spurious starvation, it sends an explicitrequest to the source for a new sequence number. This request is forwardedhop by hop to the source, with no regard to the feasibility condition.Upon receiving the request, the source increases its sequence number andbroadcasts an update, which is forwarded to the requesting node.¶
Note that after a change in network topology not all such requestswill, in general, reach the source, as some will be sent over links thatare now broken. However, if the network is still connected, then at leastone among the nodes suffering from spurious starvation has an (unfeasible)route to the source; hence, in the absence of packet loss, at least onesuch request will reach the source. (Resending requests a small number oftimes compensates for packet loss.)¶
Since requests are forwarded with no regard to the feasibilitycondition, they may, in general, be caught in a forwarding loop; this isavoided by having nodes perform duplicate detection for the requests thatthey forward.¶
The above discussion assumes that each prefix is originated by a singlerouter. In real networks, however, it is often necessary to have a singleprefix originated by multiple routers: for example, the default route willbe originated by all of the edge routers of a routing domain.¶
Since synchronising sequence numbers between distinct routers isproblematic, Babel treats routes for the same prefix as distinct entitieswhen they are originated by different routers: every route announcementcarries the router-id of its originating router, and feasibility distancesare not maintained per prefix, but per source, where a source is a pair ofa router-id and a prefix. In effect, Babel guarantees loop-freedom for theforwarding graph to every source; since the union of multiple acyclicgraphs is not in general acyclic, Babel does not in general guaranteeloop-freedom when a prefix is originated by multiple routers, but anyloops will be broken in a time at most proportional to the diameter of theloop -- as soon as an update has "gone around" the routing loop.¶
Consider for example the following topology, where A has selected thedefault route through S, and B has selected the one through S':¶
1 1 1::/0 -- S --- A --- B --- S' -- ::/0¶
Suppose that both default routes fail at the same time; then nothingprevents A from switching to B, and B simultaneously switching to A.However, as soon as A has successfully advertised the new route to B, theroute through A will become unfeasible for B. Conversely, as soon asB will have advertised the route through A, the route through B willbecome unfeasible for A.¶
In effect, the routing loop disappears at the latest when routinginformation has gone around the loop. Since this process can be delayed bylost packets, Babel makes certain efforts to ensure that updates are sentreliably after a router-id change (Section 3.7.2).¶
Additionally, after the routers have advertised the two routes, bothsources will be in their source tables, which will prevent them from everagain participating in a routing loop involving routes from S and S' (up tothe source GC time, which, available memory permitting, can be set toarbitrarily large values).¶
In the above discussion, we have assumed that all prefixes are disjoint,as is the case in flat ("mesh") routing. In practice, however, prefixesmay overlap: for example, the default route overlaps with all of the routespresent in the network.¶
After a route fails, it is not correct in general to switch to a routethat subsumes the failed route. Consider for example the followingconfiguration:¶
1 1::/0 -- A --- B --- C¶
Suppose that node C fails. If B forwards packets destined to C byfollowing the default route, a routing loop will form, and persist untilA learns of B's retraction of the direct route to C. B avoids thispitfall by installing an "unreachable" route after a route is retracted;this route is maintained until it can be guaranteed that the former routehas been retracted by all of B's neighbours (Section 3.5.4).¶
Every Babel speaker is assigned a router-id, which is an arbitrarystring of 8 octets that is assumed unique across the routing domain. Forexample, router-ids could be assigned randomly, or they could be derivedfrom a link-layer address. (The protocol encoding is slightly morecompact when router-ids are assigned in the same manner as the IPv6 layerassigns host IDs; see the definition of the "R" flag inSection 4.6.9.)¶
Babel protocol packets are sent in the body of a UDP datagram (asdescribed inSection 4). Each Babel packetconsists of zero or more TLVs. Most TLVs may contain sub-TLVs.¶
Babel's control traffic can be carried indifferently over IPv6or over IPv4, and prefixes of either address family can be announced overeither protocol. Thus, there are at least two natural deployment models:using IPv6 exclusively for all control traffic, or running two distinctprotocol instances, one for each address family. The exclusive use ofIPv6 for all control traffic isRECOMMENDED, since using both protocols atthe same time doubles the amount of traffic devoted to neighbour discoveryand link quality estimation.¶
The source address of a Babel packet is always a unicast address,link-local in the case of IPv6. Babel packets may be sent to a well-known(link-local) multicast address or to a (link-local) unicast address. Innormal operation, a Babel speaker sends both multicast and unicast packetsto its neighbours.¶
With the exception of acknowledgments, all Babel TLVscan be sent to either unicast or multicast addresses, and their semanticsdoes not depend on whether the destination is a unicast or a multicastaddress. Hence, a Babel speaker does not need to determine the destinationaddress of a packet that it receives in order to interpret it.¶
A moderate amount of jitter may be applied to packets sent by a Babelspeaker: outgoing TLVs are buffered andSHOULD be sent with a randomdelay. This is done for two purposes: it avoids synchronisation ofmultiple Babel speakers across a network[JITTER], and itallows for the aggregation of multiple TLVs into a single packet.¶
The maximum amount of delay a TLV can be subjected to depends on theTLV. When the protocol description specifies that a TLV is urgent (as inSection 3.7.2 andSection 3.8.1),then the TLVMUST be sent within a short time known as the urgent timeout(seeAppendix B for recommended values). When the TLV isgoverned by a timeout explicitly included in a previous TLV, such as inthe case of Acknowledgments (Section 4.6.4),Updates (Section 3.7), and IHUs(Section 3.4.2), then the TLVMUST be sentearly enough to meet the explicit deadline (with a small margin to allowfor propagation delays). In all other cases, the TLVSHOULD be sent outwithin one-half of the Multicast Hello interval.¶
In order to avoid packet drops (either at the sender or at thereceiver), a delaySHOULD be introduced between successive packets sentout on the same interface, within the constraints of the previousparagraph. Note, however, that such packet pacing might impair the abilityof some link layers (e.g., IEEE 802.11[IEEE802.11])to perform packet aggregation.¶
In this section, we describe the data structures thatevery Babel speaker maintains. This description is conceptual: a Babelspeaker may use different data structures as long as the resultingprotocol is the same as the one described in this document. For example,rather than maintaining a single table containing both selected andunselected (fallback) routes, as described inSection 3.2.6, an actual implementation would probably use two tables, one withselected routes and one with fallback routes.¶
Sequence numbers (seqnos) appear in a number of Babel data structures,and they are interpreted as integers modulo 216. For the purposes ofthis document, arithmetic on sequence numbers is defined as follows.¶
Given a seqno s and a non-negative integer n, the sum of s and n isdefined by the following:¶
s + n (modulo 216) = (s + n) MOD 216¶
or, equivalently,¶
s + n (modulo 216) = (s + n) AND 65535¶
where MOD is the modulo operation yielding a non-negative integer, and AND isthe bitwise conjunction operation.¶
Given two sequence numbers s and s', the relation s is less than s'(s < s') is defined by the following:¶
s < s' (modulo 216) when 0 < ((s' - s) MOD 216) < 32768¶
or, equivalently,¶
s < s' (modulo 216) when s /= s' and ((s' - s) AND 32768) = 0.¶
A node's sequence number is a 16-bit integer that is included in routeupdates sent for routes originated by this node.¶
A node increments its sequence number (modulo 216) whenever itreceives a request for a new sequence number (Section 3.8.1.2). A nodeSHOULD NOT increment itssequence number (seqno) spontaneously, since increasing seqnos makes itless likely that other nodes will have feasible alternate routes whentheir selected routes fail.¶
The interface table contains the list of interfaces on which the nodespeaks the Babel protocol. Every interface table entry contains theinterface's outgoing Multicast Hello seqno, a 16-bit integer that is sentwith each Multicast Hello TLV on this interface and is incremented (modulo216) whenever a Multicast Hello is sent. (Note that an interface'sMulticast Hello seqno is unrelated to the node's seqno.)¶
There are two timers associated with each interface table entry.The periodic multicast hello timer governs the sending of scheduledMulticast Hello and IHU packets (Section 3.4).The periodic Update timer governs the sending of periodic route updates(Section 3.7.1). SeeAppendix B forsuggested time constants.¶
The neighbour table contains the list of all neighbouring interfacesfrom which a Babel packet has been recently received. The neighbour tableis indexed by pairs of the form (interface, address), and every neighbour tableentry contains the following data:¶
There are three timers associated with each neighbour entry -- themulticast hello timer, which is set to the interval value carried byscheduled Multicast Hello TLVs sent by this neighbour, the unicast hellotimer, which is set to the interval value carried by scheduled UnicastHello TLVs, and the IHU timer, which is set to a small multiple of theinterval carried in IHU TLVs (see "IHU Hold time" inAppendix B for suggested values).¶
Note that the neighbour table is indexed by IP addresses, not byrouter-ids: neighbourship is a relationship between interfaces, not betweennodes. Therefore, two nodes with multiple interfaces can participate inmultiple neighbourship relationships, a situation that can notably arisewhen wireless nodes with multiple radios are involved.¶
The source table is used to record feasibility distances. It is indexedby triples of the form (prefix, plen, router-id), and every source tableentry contains the following data:¶
There is one timer associated with each entry in the source table-- the source garbage-collection timer. It is initialised to a timeon the order of minutes and reset as specified inSection 3.7.3.¶
The route table contains the routes known to this node. It is indexedby triples of the form (prefix, plen, neighbour), and every route tableentry contains the following data:¶
There is one timer associated with each route table entry -- theroute expiry timer. It is initialised and reset as specified inSection 3.5.3.¶
Note that there are two distinct (seqno, metric) pairs associated with each route: the route's distance, which is stored in the route table, andthe feasibility distance, which is stored in the source table and shared betweenall routes with the same source.¶
The table of pending seqno requests contains a list of seqno requeststhat the local node has sent (either because they have been originatedlocally, or because they were forwarded) and to which no reply has beenreceived yet. This table is indexed by triples of the form (prefix, plen,router-id), and every entry in this table contains the following data:¶
There is one timer associated with each pending seqno request; it governsboth the resending of requests and their expiry.¶
A Babel speaker may request that a neighbour receiving a given packetreply with an explicit acknowledgment within a given time. While the useof acknowledgment requests is optional, every Babel speakerMUST be ableto reply to such a request.¶
An acknowledgmentMUST be sent to a unicast destination. On the otherhand, acknowledgment requests may be sent to either unicast or multicastdestinations, in which case they request an acknowledgment from all of thereceiving nodes.¶
When to request acknowledgments is a matter of local policy; thesimplest strategy is to never request acknowledgments and to rely onperiodic updates to ensure that any reachable routes are eventuallypropagated throughout the routing domain. In order to improve convergencespeed and to reduce the amount of control traffic, acknowledgment requestsMAY be used in order to reliably send urgent updates (Section 3.7.2) and retractions (Section 3.5.4),especially when the number of neighbours on a given interface is small.Since Babel is designed to deal gracefully with packet loss on unreliablemedia, sending all packets with acknowledgment requests is not necessaryandNOT RECOMMENDED, as the acknowledgments cause additional traffic andmay force additional Address Resolution Protocol (ARP) or NeighbourDiscovery (ND) exchanges.¶
Neighbour acquisition is the process by which a Babel node discovers theset of neighbours heard over each of its interfaces and ascertainsbidirectional reachability. On unreliable media, neighbour acquisitionadditionally provides some statistics that may be useful for link qualitycomputation.¶
Before it can exchange routing information with a neighbour, a BabelnodeMUST create an entry for that neighbour in the neighbour table. Whento do that is implementation-specific; suitable strategies includecreating an entry when any Babel packet is received, or creating an entrywhen a Hello TLV is parsed. Similarly, in order to conserve systemresources, an implementationSHOULD discard an entry when it has beenunused for long enough; suitable strategies include dropping the neighbourafter a timeout, and dropping a neighbour when the associated Hellohistories become empty (seeAppendix A.2).¶
Every Babel node sends Hello TLVs to its neighbours, at regular or irregular intervals, to indicate that itis alive. Each Hello TLV carries anincreasing (modulo 216) sequence number and an upper bound on the timeinterval until the next Hello of the same type (see below). If the timeinterval 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 appliesto the next Hello (if the most recent scheduled Hello of the right kindwas received at time t0 and carried interval i, then the previous promiseof sending another Hello before time t0 + i still holds). Wesay that a Hello is "scheduled" if it carries a nonzero interval, and"unscheduled" otherwise.¶
There are two kinds of Hellos: Multicast Hellos, which usea per-interface Hello counter (the Multicast Hello seqno), and UnicastHellos, which use a per-neighbour counter (the Unicast Hello seqno).A Multicast Hello with a given seqnoMUST be sent to all neighbours ona given interface, either by sending it to a multicast address or bysending it to one unicast address per neighbour (hence, the term"Multicast Hello" is a slight misnomer). A Unicast Hello carrying a givenseqno should normally be sent to just one neighbour (over unicast), sincethe sequence numbers of different neighbours are not in generalsynchronised.¶
Multicast Hellos sent over multicast can be used for neighbourdiscovery; hence, a nodeSHOULD send periodic (scheduled) Multicast Hellosunless neighbour discovery is performed by means outside of the Babelprotocol. A nodeMAY send Unicast Hellos or unscheduled Hellos of eitherkind for any reason, such as reducing the amount of multicast traffic orimproving reliability on link technologies with poor support forlink-layer multicast.¶
A nodeMAY send a scheduled Hello ahead of time. A nodeMAY change itsscheduled Hello interval. The Hello intervalMAY be decreased at anytime; itMAY be increased immediately before sending a Hello TLV, butSHOULD NOT be increased at other times. (Equivalently, a nodeSHOULD senda scheduled Hello immediately after increasing its Hello interval.)¶
How to deal with received Hello TLVs and what statistics to maintainare considered local implementation matters; typically, a node willmaintain some sort of history of recently received Hellos. An example ofa suitable algorithm is described inAppendix A.1.¶
After receiving a Hello, or determining that it has missed one, the noderecomputes the association's cost (Section 3.4.3) andruns the route selection procedure (Section 3.6).¶
In order to establish bidirectional reachability, every node sendsperiodic IHU ("I Heard You") TLVs to each of its neighbours. Since IHUscarry an explicit interval value, theyMAY be sent less often than Hellosin order to reduce the amount of routing traffic in dense networks; inparticular, theySHOULD be sent less often than Hellos over links withlittle packet loss. While IHUs are conceptually unicast, theyMAY besent to a multicast address in order to avoid an ARP or Neighbour Discoveryexchange and to aggregate multiple IHUs into a single packet.¶
In addition to the periodic IHUs, a nodeMAY, at any time, send anunscheduled IHU packet. ItMAY also, at any time, decrease its IHUinterval, and itMAY increase its IHU interval immediately before sendingan IHU, butSHOULD NOT increase it at any other time. (Equivalently,a nodeSHOULD send an extra IHU immediately after increasing its Hellointerval.)¶
Every IHU TLV contains two pieces of data: the link's rxcost (receptioncost) from the sender's perspective, used by the neighbour for computinglink costs (Section 3.4.3), and the interval betweenperiodic IHU packets. A node receiving an IHU sets the value of thetxcost (transmission cost) maintained in the neighbour table to the valuecontained in the IHU, and resets the IHU timer associated to thisneighbour to a small multiple of the interval value received in the IHU(see "IHU Hold time" inAppendix B for suggested values).When a neighbour's IHU timer expires, the neighbour's txcost is set toinfinity.¶
After updating a neighbour's txcost, the receiving node recomputes theneighbour's cost (Section 3.4.3) and runs the routeselection procedure (Section 3.6).¶
A neighbourship association's link cost is computed from the valuesmaintained in the neighbour table: the statistics kept in the neighbourtable about the reception of Hellos, and the txcost computed from receivedIHU packets.¶
For every neighbour, a Babel node computes a value known as thisneighbour's rxcost. This value is usually derived from the Hello history,which may be combined with other data, such as statistics maintained bythe link layer. The rxcost is sent to a neighbour in each IHU.¶
Since nodes do not necessarily send periodic Unicast Hellos but dousually send periodic Multicast Hellos (Section 3.4.1),a nodeSHOULD use an algorithm that yields a finite rxcost when onlyMulticast Hellos are received, unless interoperability with nodes thatonly send Multicast Hellos is not required.¶
How the txcost and rxcost are combined in order to compute a link'scost is a matter of local policy; as far as Babel's correctness isconcerned, only the following conditionsMUST be satisfied:¶
SeeAppendix A.2 forRECOMMENDEDstrategies for computing a link's cost.¶
Conceptually, a Babel update is a quintuple (prefix, plen, router-id,seqno, metric), where (prefix, plen) is the prefix for which a route isbeing advertised, router-id is the router-id of the router originating thisupdate, seqno is a nondecreasing (modulo 216) integer that carries theoriginating router seqno, and metric is the announced metric.¶
Before being accepted, an update is checked against the feasibilitycondition (Section 3.5.1), which ensures that theroute does not create a routing loop. If the feasibility condition is notsatisfied, the update is either ignored or prevents the route from beingselected, as described inSection 3.5.3. If thefeasibility condition is satisfied, then the update cannot possibly causea routing loop.¶
The feasibility condition is applied to all received updates. Thefeasibility condition compares the metric in the received update with themetrics of the updates previously sent by the receiving node; updates thatfail the feasibility condition, and therefore have metrics large enough tocause a routing loop, are either ignored or prevent the resulting routefrom being selected.¶
A feasibility distance is a pair (seqno, metric), where seqno is aninteger modulo 216 and metric is a positive integer. Feasibilitydistances are compared lexicographically, with the first componentinverted: we say that a distance (seqno, metric) is strictly better thana distance (seqno', metric'), written¶
(seqno, metric) < (seqno', metric')¶
when¶
seqno > seqno' or (seqno = seqno' and metric < metric')¶
where sequence numbers are compared modulo 216.¶
Given a source (prefix, plen, router-id), a node's feasibility distancefor this source is the minimum, according to the ordering defined above,of the distances of all the finite updates ever sent by this particularnode for the prefix (prefix, plen) and the given router-id. Feasibilitydistances are maintained in the source table, the exact procedure is giveninSection 3.7.3.¶
A received update is feasible when either it is a retraction (its metricis FFFF hexadecimal), or the advertised distance is strictly better, in thesense defined above, than the feasibility distance for the correspondingsource. More precisely, a route advertisement carrying the quintuple(prefix, plen, router-id, seqno, metric) is feasible if one of thefollowing conditions holds:¶
an entry (prefix, plen, router-id, seqno', metric') exists in the source table, and either¶
Note that the feasibility condition considers the metric advertised bythe neighbour, not the route's metric; hence, a fluctuation ina neighbour's cost cannot render a selected route unfeasible. Notefurther that retractions (updates with infinite metric) are alwaysfeasible, since they cannot possibly cause a routing loop.¶
A route's metric is computed from the metric advertised by the neighbourand the neighbour's link cost. Just like cost computation, metriccomputation is considered a local policy matter; as far as Babel isconcerned, the function M(c, m) used for computing a metric froma locally computed link cost c and the metric m advertised by a neighbourMUST only satisfy the following conditions:¶
Additionally, the metricSHOULD satisfy the following condition:¶
While strict monotonicity is essential to the integrity of the network(persistent routing loops may arise if it is not satisfied), left-distributivity is not: if it is not satisfied, Babel will still convergeto a loop-free configuration, but might not reach a global optimum (infact, a global optimum may not even exist).¶
The conditions above are easily satisfied by using the additive metric,i.e., by defining M(c, m) = c + m. Since the additivemetric is useful with a large range of cost computation strategies, it istheRECOMMENDED default. See alsoAppendix C, whichdescribes a technique that makes it possible to tweak the values ofindividual metrics without running the risk of creating routing loops.¶
When a Babel node receives an update (prefix, plen, router-id, seqno,metric) from a neighbour neigh, it checks whether it already has a routetable entry indexed by (prefix, plen, neigh).¶
If no such entry exists:¶
If such an entry exists:¶
Note that the route table may contain unfeasible routes, either becausethey were created by an unfeasible update or due to a metric fluctuation.Such routes are never selected, since they are not known to be loop-free.Should all the feasible routes become unusable, however, the unfeasibleroutes can be made feasible and therefore possible to select by sendingrequests along them (seeSection 3.8.2).¶
When a route's expiry timer triggers, the behaviour depends on whetherthe route's metric is finite. If the metric is finite, it is set toinfinity and the expiry timer is reset. If the metric is already infinite,the route is flushed from the route table.¶
After the route table is updated, the route selection procedure(Section 3.6) is run.¶
When a prefix P is retracted (because all routes are unfeasible or havean infinite metric, whether due to the expiry timer or for other reasons),and a shorter prefix P' that covers P is reachable, P' cannot in generalbe used for routing packets destined to P without running the risk ofcreating a routing loop (Section 2.8).¶
To avoid this issue, whenever a prefix P is retracted, a route tableentry with infinite metric is maintained as described inSection 3.5.3. As long as this entry is maintained,packets destined to an address within PMUST NOT be forwarded by followinga route for a shorter prefix. This entry is removed as soon asa finite-metric update for prefix P is received and the resulting routeselected. If no such update is forthcoming, the infinite metric entrySHOULD be maintained at least until it is guaranteed that no neighbour hasselected the current node as next hop for prefix P. This can be achievedby either:¶
The former option is simpler and ensures that, at that point, any routesfor prefix P pointing at the current node have expired. However, sincethe expiry time can be as high as a few minutes, doing that preventsautomatic aggregation by creating spurious black-holes for aggregatedroutes. The latter option isRECOMMENDED as it dramatically reduces thetime for which a prefix is unreachable in the presence of aggregatedroutes.¶
Route selection is the process by which a single route for a givenprefix is selected to be used for forwarding packets and to bere-advertised to a node's neighbours.¶
Babel is designed to allow flexible route selection policies. As far as the algorithm's correctness is concerned, the route selection policyMUST only satisfy the following properties:¶
Babel nodes using different route selection strategies will interoperateand will not create routing loops as long as these two properties hold.¶
Route selectionMUST NOT take seqnos into account: a routeMUST NOT bepreferred just because it carries a higher (more recent) seqno. Doingotherwise would cause route oscillation while a new seqno propagatesacross the network, and might create persistent black-holes if the metricbeing used is not left-distributive (Section 3.5.2).¶
The obvious route selection strategy is to pick, for every destination,the feasible route with minimal metric. When all metrics are stable, thisapproach ensures convergence to a tree of shortest paths (assuming thatthe metric is left-distributive, seeSection 3.5.2).There are two reasons, however, why this strategy may lead to instabilityin the presence of continuously varying metrics. First, if two parallelroutes oscillate around a common value, then the smallest metric strategywill keep switching between the two. Second, the selection of a route increases congestion along it, which might increase packet loss, which in turn could cause its metric to increase; this kind of feedback loop is prone to causing persistent oscillations.¶
In order to limit these kinds of instabilities, a route selectionstrategySHOULD include some form of hysteresis, i.e., be sensitive toa route's history: the strategy should only switch from the currently selected routeto a different route if the latter has beenconsistently good for some period of time. ARECOMMENDED hysteresisalgorithm is given inAppendix A.3.¶
After the route selection procedure is run, triggered updates(Section 3.7.2) and requests(Section 3.8.2) are sent.¶
A Babel speaker advertises to its neighbours its set of selectedroutes. Normally, this is done by sending one or more multicast packetscontaining Update TLVs on all of its connected interfaces; however, onlink technologies where multicast is significantly more expensive thanunicast, a nodeMAY choose to send multiple copies of updates in unicastpackets, especially when the number of neighbours is small.¶
Additionally, in order to ensure that any black-holes are reliablycleared in a timely manner, a Babel node may send retractions (updateswith an infinite metric) for any recently retracted prefixes.¶
If an update is for a route injected into the Babel domain by the localnode (e.g., it carries the address of a local interface, the prefix ofa directly attached network, or a prefix redistributed from a differentrouting protocol), the router-id is set to the local node's router-id, themetric is set to some arbitrary finite value (typically 0), and the seqnois set to the local router's sequence number.¶
If an update is for a route learnt from another Babel speaker, therouter-id and sequence number are copied from the route table entry, andthe metric is computed as specified inSection 3.5.2.¶
Every Babel speakerMUST advertise each of its selected routes on everyinterface, at least once every Update interval. Since Babel doesn'tsuffer from routing loops (there is no "counting to infinity") and reliesheavily on triggered updates (Section 3.7.2), thisfull dump only needs to happen infrequently (seeAppendix Bfor suggested intervals).¶
In addition to periodic routing updates, a Babel speaker sendsunscheduled, or triggered, updates in order to inform its neighbours ofa significant change in the network topology.¶
A change of router-id for the selected route to a given prefix may beindicative of a routing loop in formation; hence, whenever it changes theselected router-id for a given destination, a nodeMUST send an update asan urgent TLV (as defined inSection 3.1).Additionally, itSHOULD make a reasonable attempt at ensuring that allreachable neighbours receive this update.¶
There are two strategies for ensuring that. If the number of neighboursis small, then it is reasonable to send the update together with anacknowledgment request; the update is resent until all neighbours haveacknowledged the packet, up to some number of times. If the number ofneighbours is large, however, requesting acknowledgments from all of themmight cause a non-negligible amount of network traffic; in that case, itmay be preferable to simply repeat the update some reasonable number oftimes (say, 3 for wireless and 2 for wired links). The number of copiesMUST NOT exceed 5, and the copiesSHOULD be separated by a small delay, asdescribed inSection 3.1.¶
A route retraction is somewhat less worrying: if the route retractiondoesn't reach all neighbours, a black-hole might be created, which, unlikea routing loop, does not endanger the integrity of the network. When aroute is retracted, a nodeSHOULD send a triggered update andSHOULD makea reasonable attempt at ensuring that all neighbours receive thisretraction.¶
Finally, a nodeMAY send a triggered update when the metric for a givenprefix changes in a significant manner, due to a received update, becausea link's cost has changed or because a different next hop has beenselected. A nodeSHOULD NOT send triggered updates for other reasons,such as when there is a minor fluctuation in a route's metric, when theselected next hop changes without inducing a significant change to theroute's metric, or to propagate a new sequence number (except to satisfya request, as specified inSection 3.8).¶
Before sending an update (prefix, plen, router-id, seqno, metric) withfinite metric (i.e., not a route retraction), a Babel node updates thefeasibility distance maintained in the source table. This is done asfollows.¶
If no entry indexed by (prefix, plen, router-id) exists in the sourcetable, then one is created with value (prefix, plen, router-id, seqno,metric).¶
If an entry (prefix, plen, router-id, seqno', metric') exists, then itis updated as follows:¶
The garbage-collection timer for the entry is then reset. Note thatthe feasibility distance is not updated and the garbage-collection timeris not reset when a retraction (an update with infinite metric) issent.¶
When the garbage-collection timer expires, the entry is removed fromthe source table.¶
When running over a transitive, symmetric link technology, e.g.,a point-to-point link or a wired LAN technology such as Ethernet, a BabelnodeSHOULD use an optimisation known as split horizon. When splithorizon is used on a given interface, a routing update for prefix P is notsent on the particular interface over which the selected route towardsprefix P was learnt.¶
Split horizonSHOULD NOT be applied to an interface unless the interfaceis known to be symmetric and transitive; in particular, split horizon isnot applicable to decentralised wireless link technologies(e.g., IEEE 802.11 in ad hoc mode) when routing updates are sent overmulticast.¶
In normal operation, a node's route table is populated by the regularand triggered updates sent by its neighbours. Under some circumstances,however, a node sends explicit requests in order to cause a resynchronisationwith the source after a mobility event or to prevent a route fromspuriously expiring.¶
The Babel protocol provides two kinds of explicit requests: routerequests, which simply request an update for a given prefix, and seqnorequests, which request an update for a given prefix with a specificsequence number. The former are never forwarded; the latter are forwardedif they cannot be satisfied by the receiver.¶
Upon receiving a request, a node either forwards the request or sends anupdate in reply to the request, as described in the following sections. Ifthis causes an update to be sent, the update is either sent to a multicastaddress on the interface on which the request was received, or to theunicast address of the neighbour that sent the request.¶
The exact behaviour is different for route requests and seqno requests.¶
When a node receives a route request for a given prefix, it checks itsroute table for a selected route to this exact prefix. If such a routeexists, itMUST send an update (over unicast or over multicast); if sucha route does not exist, itMUST send a retraction for that prefix.¶
When a node receives a wildcard route request, itSHOULD send a fullroute table dump. Full route dumpsSHOULD be rate-limited, especially ifthey are sent over multicast.¶
When a node receives a seqno request for a given router-id and sequencenumber, it checks whether its route table contains a selected entry forthat prefix. If a selected route for the given prefix exists and hasfinite metric, and either the router-ids are different or the router-idsare equal and the entry's sequence number is no smaller (modulo 216) thanthe requested sequence number, the nodeMUST send an update for the givenprefix. If the router-ids match, but the requested seqno is larger (modulo216) than the route entry's, the node compares the router-id against itsown router-id. If the router-id is its own, then it increases itssequence number by 1 (modulo 216) and sends an update. A nodeMUST NOTincrease its sequence number by more than 1 in reaction to a single seqnorequest.¶
Otherwise, if the requested router-id is not its own, the received nodeconsults the Hop Count field of the request. If the hop count is 2 ormore, and the node is advertising the prefix to its neighbours, the nodeselects a neighbour to forward the request to as follows:¶
In order to actually forward the request, the node decrements the hopcount and sends the request in a unicast packet destined to the selectedneighbour. The forwarded requestSHOULD be sent as an urgent TLV (asdefined inSection 3.1).¶
A nodeSHOULD maintain a list of recently forwarded seqno requests andforward the reply (an update with a seqno sufficiently large to satisfythe request) as an urgent TLV (as defined inSection 3.1). A nodeSHOULD compare everyincoming seqno request against its list of recently forwarded seqnorequests and avoid forwarding the request if it is redundant (i.e., if the node hasrecently sent a request with the same prefix, router-id, and a seqno thatis not smaller modulo 216).¶
Since the request-forwarding mechanism does not necessarily obey thefeasibility condition, it may get caught in routing loops; hence, requestscarry a hop count to limit the time during which they remain in the network.However, since requests are only ever forwarded as unicast packets, theinitial hop count need not be kept particularly low, and performing anexpanding horizon search is not necessary. A single requestMUST NOT beduplicated: itMUST NOT be forwarded to a multicast address, and itMUST NOT be forwarded to multiple neighbours. However, if a seqno request isresent by its originator, the subsequent copies may be forwarded toa different neighbour than the initial one.¶
A Babel nodeMAY send a route or seqno request at any time to amulticast or a unicast address; there is only one case when originatingrequests is required (Section 3.8.2.1).¶
When a route is retracted or expires, a Babel node usually switches toanother feasible route for the same prefix. It may be the case, however,that no such routes are available.¶
A node that has lost all feasible routes to a given destination butstill has unexpired unfeasible routes to that destinationMUST senda seqno request; if it doesn't have any such routes, itMAY still senda seqno request. The router-id of the request is set to the router-id ofthe route that it has just lost, and the requested seqno is the valuecontained in the source table plus 1. The request carries a hop count,which is used as a last-resort mechanism to ensure that it eventuallyvanishes from the network; itMAY be set to any value that is larger thanthe diameter of the network (64 is a suitable default value).¶
If the node has any (unfeasible) routes to the requested destination,then itMUST send the request to at least one of the next-hop neighboursthat advertised these routes, andSHOULD send it to all of them; in anycase, itMAY send the request to any other neighbours, whether theyadvertise a route to the requested destination or not. A simpleimplementation strategy is therefore to unconditionally multicast therequest over all interfaces.¶
Similar requests will be sent by other nodes that are affected by theroute's loss. If the network is still connected, and assuming no packetloss, 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 toduplicate suppression, only a small number of such requests are expectedto actually reach the source.)¶
In order to compensate for packet loss, a nodeSHOULD repeat sucha request a small number of times if no route becomes feasible withina short time (see "Request timeout" inAppendix B forsuggested values). In the presence of heavy packet loss, however, allsuch requests might be lost; in that case, the mechanism in the nextsection will eventually ensure that a new seqno is received.¶
When a route's metric increases, a node might receive an unfeasibleupdate for a route that it has currently selected. As specified inSection 3.5.1, the receiving node will eitherignore the update or unselect the route.¶
In order to keep routes from spuriously expiring because they havebecome unfeasible, a nodeSHOULD send a unicast seqno request when itreceives an unfeasible update for a route that is currently selected. Therequested sequence number is computed from the source table as inSection 3.8.2.1.¶
Additionally, since metric computation does not necessarily coincidewith the delay in propagating updates, a node might receive an unfeasibleupdate from a currently unselected neighbour that is preferable to thecurrently selected route (e.g., because it has a much smaller metric); inthat case, the nodeSHOULD send a unicast seqno request to the neighbourthat advertised the preferable update.¶
In normal operation, a route's expiry timer never triggers: sincea route's hold time is computed from an explicit interval included inUpdate TLVs, a new update (possibly a retraction) should arrive in time toprevent a route from expiring.¶
In the presence of packet loss, however, it may be the case that noupdate is successfully received for an extended period of time, causinga route to expire. In order to avoid such spurious expiry, shortly beforea selected route expires, a Babel nodeSHOULD send a unicast route requestto the neighbour that advertised this route; since nodes always sendeither updates or retractions in response to non-wildcard route requests(Section 3.8.1.1), this will usually result inthe route being either refreshed or retracted.¶
A Babel packetMUST be sent as the body of a UDP datagram, withnetwork-layer hop count set to 1, destined to a well-known multicastaddress 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 portare set to a well-known port number. A Babel packetMUST be silentlyignored unless its source address is either a link-local IPv6 address oran IPv4 address belonging to the local network, and its source port is thewell-known Babel port. ItMAY be silently ignored if its destinationaddress is a global IPv6 address.¶
In order to minimise the number of packets being sent while avoidinglower-layer fragmentation, a Babel nodeSHOULD maximise the size of thepackets it sends, up to the outgoing interface's MTU adjusted forlower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP overIPv6). ItMUST NOT send packets larger than the attached interface's MTUadjusted for lower-layer headers or 512 octets, whichever is larger, butnot exceeding 216 - 1 adjusted for lower-layer headers. Every BabelspeakerMUST be able to receive packets that are as large as any attachedinterface's MTU adjusted for lower-layer headers or 512 octets, whicheveris larger. Babel packetsMUST NOT be sent in IPv6 jumbograms[RFC2675].¶
All multi-octet fields that represent integers are encoded with themost significant octet first (in Big-Endian format[IEN137],also called network order). The base protocol only carries unsignedvalues; if an extension needs to carry signed values, it will need tospecify their encoding (e.g., two's complement).¶
Relative times are carried as 16-bit values specifying a number ofcentiseconds (hundredths of a second). This allows times up to roughly 11minutes with a granularity of 10 ms, which should cover all reasonableapplications of Babel (see alsoAppendix B).¶
A router-id is an arbitrary 8-octet value. A router-idMUST NOTconsist of either all binary zeroes (0000000000000000 hexadecimal) or allbinary ones (FFFFFFFFFFFFFFFF hexadecimal).¶
Since the bulk of the protocol is taken by addresses, multiple ways ofencoding addresses are defined. Additionally, within Update TLVs a commonsubnet prefix may be omitted when multiple addresses are sent in a singlepacket -- this is known as address compression (Section 4.6.9).¶
Address encodings (AEs):¶
The address family associated with an address encoding is either IPv4 orIPv6: it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 and3.¶
A network prefix is encoded just like a network address, but it isstored in the smallest number of octets that are enough to hold thesignificant bits (up to the prefix length).¶
A Babel packet consists of a 4-octet header, followed by a sequence ofTLVs (the packet body), optionally followed by a second sequence of TLVs(the packet trailer). The format is designed to be extensible; seeAppendix D for extensibility considerations.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Magic | Version | Body length |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Packet Body...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| Packet Trailer...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-¶
Fields:¶
The packet body and trailer are both sequences of TLVs. The packetbody is the normal place to store TLVs; the packet trailer only containsspecialised TLVs that do not need to be protected by cryptographicsecurity mechanisms. When parsing the trailer, the receiverMUST ignoreany TLV unless its definition explicitly states that it is allowed toappear there. Among the TLVs defined in this document, only Pad1 and PadNare allowed in the trailer; since these TLVs are ignored in any case, animplementationMAY silently ignore the packet trailer without even parsingit, unless it implements at least one protocol extension that defines TLVsthat are allowed to appear in the trailer.¶
With the exception of Pad1, all TLVs have the following structure:¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type | Length | Payload...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-¶
Fields:¶
TLVs with an unknown type valueMUST be silently ignored.¶
Every TLV carries an explicit length in its header; however, most TLVsare self-terminating, in the sense that it is possible to determine thelength of the body without reference to the explicit Length field. Ifa TLV has a self-terminating format, then the space between the naturalsize of the TLV and the size announced in the Length field may be used tostore a sequence of sub-TLVs.¶
Sub-TLVs have the same structure as TLVs. With the exception of Pad1,all TLVs have the following structure:¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type | Length | Body...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-¶
Fields:¶
The most significant bit of the sub-TLV type (the bit with value 80hexadecimal), is called the mandatory bit; in other words, sub-TLV types128 through 255 have the mandatory bit set. This bit indicates how tohandle unknown sub-TLVs. If the mandatory bit is not set, then an unknownsub-TLVMUST be silently ignored, and the rest of the TLV is processednormally. If the mandatory bit is set, then the whole enclosing TLVMUSTbe silently ignored (except for updating the parser state by a Router-Id,Next Hop, or Update TLV, as described in the next section).¶
In a large network, the bulk of Babel traffic consists of routeupdates; hence, some care has been given to encoding them efficiently.The data conceptually contained in an update (Section 3.5)is split into three pieces:¶
In addition to the above, an Update TLV can omit a prefix of the prefixbeing announced, which is then extracted from the preceding Update TLVin the same address family (IPv4 or IPv6). Finally, as a specialoptimisation for the case when a router-id coincides with the interface-idpart of an IPv6 address, the Router-Id TLV itself may be omitted, and therouter-id is derived from the low-order bits of the advertised prefix(Section 4.6.9).¶
In order to implement these compression techniques, Babel usesa stateful parser: a TLV may refer to data from a previous TLV. Theparser state consists of the following pieces of data:¶
Since the parser state must be identical across implementations, it isupdated before checking for mandatory sub-TLVs: parsing a TLVMUST updatethe parser state even if the TLV is otherwise ignored due to an unknownmandatory sub-TLV or for any other reason.¶
None of the TLVs that modify the parser state are allowed in the packettrailer; hence, an implementation may choose to use a dedicated statelessparser to parse the packet trailer.¶
0 0 1 2 3 4 5 6 7+-+-+-+-+-+-+-+-+| Type = 0 |+-+-+-+-+-+-+-+-+¶
Fields:¶
This TLV is silently ignored on reception. It is allowed in the packettrailer.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 1 | Length | MBZ...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-¶
Fields:¶
This TLV is silently ignored on reception. It is allowed in the packettrailer.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 2 | Length | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Opaque | Interval |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+¶
This TLV requests that the receiver send an Acknowledgment TLVwithin the number of centiseconds specified by the Interval field.¶
Fields:¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 3 | Length | Opaque |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+¶
This TLV is sent by a node upon receiving an Acknowledgment Request TLV.¶
Fields:¶
Since Opaque values are not globally unique, this TLVMUST be sent toa unicast address.¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 4 | Length | Flags |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Seqno | Interval |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+¶
This TLV is used for neighbour discovery and for determining aneighbour's reception cost.¶
Fields:¶
The Flags field is interpreted as follows:¶
0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+|U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+¶
Every time a Hello is sent, the corresponding seqno counterMUST beincremented. Since there is a single seqno counter for all the MulticastHellos sent by a given node over a given interface, if the Unicast flag isnot set, this TLVMUST be sent to all neighbours on this link, which can beachieved by sending to a multicast destination or by sending multiplepackets to the unicast addresses of all reachable neighbours. Conversely,if the Unicast flag is set, this TLVMUST be sent to a single neighbour,which can achieved by sending to a unicast destination. In order to avoidlarge discontinuities in link quality, multiple Hello TLVsSHOULD NOT besent in the same packet.¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 5 | Length | AE | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Rxcost | Interval |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Address...+-+-+-+-+-+-+-+-+-+-+-+-¶
An IHU ("I Heard You") TLV is used for confirming bidirectionalreachability and carrying a link's transmission cost.¶
Fields:¶
Conceptually, an IHU is destined to a single neighbour. However, IHUTLVs contain an explicit destination address, andMAY be sent toa multicast address, as this allows aggregation of IHUs destined todistinct neighbours into a single packet and avoids the need for an ARP orNeighbour Discovery exchange when a neighbour is not being used for datatraffic.¶
IHU TLVs with an unknown value in the AE fieldMUST be silentlyignored.¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 6 | Length | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| |+ Router-Id +| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+¶
A Router-Id TLV establishes a router-id that is implied by subsequentUpdate TLVs, as described inSection 4.5. This TLV setsthe router-id even if it is otherwise ignored due to an unknown mandatorysub-TLV.¶
Fields:¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 7 | Length | AE | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Next hop...+-+-+-+-+-+-+-+-+-+-+-+-¶
A Next Hop TLV establishes a next-hop address for a given addressfamily (IPv4 or IPv6) that is implied in subsequent Update TLVs, asdescribed inSection 4.5. This TLV sets up the next hopfor subsequent Update TLVs even if it is otherwise ignored due to anunknown mandatory sub-TLV.¶
Fields:¶
When the address family matches the network-layer protocol over which thispacket is transported, a Next Hop TLV is not needed: in the absenceof a Next Hop TLV in a given address family, the next-hop address is takento be the source address of the packet.¶
Next Hop TLVs with an unknown value for the AE fieldMUST be silentlyignored.¶
This TLV is self-terminating, and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 8 | Length | AE | Flags |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Plen | Omitted | Interval |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Seqno | Metric |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Prefix...+-+-+-+-+-+-+-+-+-+-+-+-¶
An Update TLV advertises or retracts a route. As an optimisation, itcan optionally have the side effect of establishing a new impliedrouter-id and a new default prefix, as described inSection 4.5.¶
Fields:¶
The Flags field is interpreted as follows:¶
0 1 2 3 4 5 6 7+-+-+-+-+-+-+-+-+|P|R|X|X|X|X|X|X|+-+-+-+-+-+-+-+-+¶
if set, then this TLV establishesa new default router-id for this TLV and subsequent Update TLVs in thesame packet, even if this TLV is otherwise ignored due to an unknownmandatory sub-TLV. This router-id is computed from the first address ofthe advertised prefix as follows:¶
The prefix being advertised by an Update TLV is computed as follows:¶
If the Metric field is finite, the router-id of the originating nodefor this announcement is taken from the prefix advertised by this Updateif the Router-Id flag is set, computed as described above. Otherwise, itis taken either from the preceding Router-Id TLV, or the precedingUpdate TLV with the Router-Id flag set, whichever comes last, even ifthat TLV is otherwise ignored due to an unknown mandatory sub-TLV; ifthere is no suitable TLV, then this update is ignored.¶
The next-hop address for this update is taken from the last precedingNext Hop TLV with a matching address family (IPv4 or IPv6) in the samepacket even if it was otherwise ignored due to an unknown mandatorysub-TLV; if no such TLV exists, it is taken from the network-layer sourceaddress of this packet if it belongs to the same address family as theprefix being announced; otherwise, this UpdateMUST be ignored.¶
If the metric field is FFFF hexadecimal, this TLV specifiesa retraction. In that case, the router-id, next hop, and seqno are notused. AEMAY then be 0, in which case this Update retracts all of theroutes previously advertised by the sending interface. If the metric isfinite, AEMUST NOT be 0; Update TLVs with finite metric and AE equal to0MUST be ignored. If the metric is infinite and AE is 0, Plen andOmittedMUST both be 0; Update TLVs that do not satisfy this requirementMUST be ignored.¶
Update TLVs with an unknown value in the AE fieldMUST be silentlyignored.¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 9 | Length | AE | Plen |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Prefix...+-+-+-+-+-+-+-+-+-+-+-+-¶
A Route Request TLV prompts the receiver to send an update for a givenprefix, or a full route table dump.¶
Fields:¶
A Request TLV prompts the receiver to send an update message (possiblya 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 be0 and Prefix is of length 0). A Request TLV with AE set to 0 and Plen notset to 0MUST be ignored.¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 10 | Length | AE | Plen |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Seqno | Hop Count | Reserved |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| |+ Router-Id +| |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Prefix...+-+-+-+-+-+-+-+-+-+-+¶
A Seqno Request TLV prompts the receiver to send an Update for a givenprefix with a given sequence number, or to forward the request further ifit cannot be satisfied locally.¶
Fields:¶
A Seqno Request TLV prompts the receiving node to send a finite-metricUpdate for the prefix specified by the AE, Plen, and Prefix fields, witheither a router-id different from what is specified by the Router-Idfield, or a Seqno no less (modulo 216) than what is specified by theSeqno field. If this request cannot be satisfied locally, then it isforwarded according to the rules set out inSection 3.8.1.2.¶
While a Seqno RequestMAY be sent to a multicast address, itMUST NOT beforwarded to a multicast address andMUST NOT be forwarded to more thanone neighbour. A requestMUST NOT be forwarded if its Hop Count field is1.¶
This TLV is self-terminating and allows sub-TLVs.¶
0 1 2 3 4 5 6 7+-+-+-+-+-+-+-+-+| Type = 0 |+-+-+-+-+-+-+-+-+¶
Fields:¶
This sub-TLV is silently ignored on reception. It is allowed withinany TLV that allows sub-TLVs.¶
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Type = 1 | Length | MBZ...+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-¶
Fields:¶
This sub-TLV is silently ignored on reception. It is allowed withinany TLV that allows sub-TLVs.¶
IANA has registered the UDP port number 6696, called "babel", for useby the Babel protocol.¶
IANA has registered the IPv6 multicast group ff02::1:6 and theIPv4 multicast group 224.0.0.111 for use by the Babel protocol.¶
IANA has created a registry called "Babel TLV Types". The allocationpolicy for this registry is Specification Required[RFC8126]for Types 0-223 and Experimental Use for Types 224-254. The values inthis registry are as follows:¶
| Type | Name | Reference |
|---|---|---|
| 0 | Pad1 | RFC 8966 |
| 1 | PadN | RFC 8966 |
| 2 | Acknowledgment Request | RFC 8966 |
| 3 | Acknowledgment | RFC 8966 |
| 4 | Hello | RFC 8966 |
| 5 | IHU | RFC 8966 |
| 6 | Router-Id | RFC 8966 |
| 7 | Next Hop | RFC 8966 |
| 8 | Update | RFC 8966 |
| 9 | Route Request | RFC 8966 |
| 10 | Seqno Request | RFC 8966 |
| 11 | TS/PC | [RFC7298] |
| 12 | HMAC | [RFC7298] |
| 13 | Reserved | |
| 14 | Reserved | |
| 15 | Reserved | |
| 224-254 | Reserved for Experimental Use | RFC 8966 |
| 255 | Reserved for expansion of the type space | RFC 8966 |
IANA has created a registry called "Babel Sub-TLV Types". The allocationpolicy for this registry is Specification Required for Types 0-111 and128-239, and Experimental Use for Types 112-126 and 240-254. The valuesin this registry are as follows:¶
| Type | Name | Reference |
|---|---|---|
| 0 | Pad1 | RFC 8966 |
| 1 | PadN | RFC 8966 |
| 2 | Diversity | [BABEL-DIVERSITY] |
| 3 | Timestamp | [BABEL-RTT] |
| 4-111 | Unassigned | |
| 112-126 | Reserved for Experimental Use | RFC 8966 |
| 127 | Reserved for expansion of the type space | RFC 8966 |
| 128 | Source Prefix | [BABEL-SS] |
| 129-239 | Unassigned | |
| 240-254 | Reserved for Experimental Use | RFC 8966 |
| 255 | Reserved for expansion of the type space | RFC 8966 |
IANA has created a registry called "Babel AddressEncodings". The allocation policy for this registry is SpecificationRequired for Address Encodings (AEs) 0-223, and Experimental Use for AEs224-254. The values in this registry are as follows:¶
| AE | Name | Reference |
|---|---|---|
| 0 | Wildcard address | RFC 8966 |
| 1 | IPv4 address | RFC 8966 |
| 2 | IPv6 address | RFC 8966 |
| 3 | Link-local IPv6 address | RFC 8966 |
| 4-223 | Unassigned | |
| 224-254 | Reserved for Experimental Use | RFC 8966 |
| 255 | Reserved for expansion of the AE space | RFC 8966 |
IANA has renamed the registry called "Babel Flags Values" to "Babel Update Flags Values". The allocation policy for this registry is Specification Required. The values in this registry are as follows:¶
| Bit | Name | Reference |
|---|---|---|
| 0 | Default prefix | RFC 8966 |
| 1 | Default router-id | RFC 8966 |
| 2-7 | Unassigned |
IANA has created a new registry called "Babel Hello FlagsValues". The allocation policy for this registry is SpecificationRequired. The initial values in this registry are as follows:¶
| Bit | Name | Reference |
|---|---|---|
| 0 | Unicast | RFC 8966 |
| 1-15 | Unassigned |
IANA has replaced all references to RFCs 6126 and 7557in all of the registries mentioned above with references to this document.¶
As defined in this document, Babel is a completely insecure protocol.Without additional security mechanisms, Babel trusts any information itreceives in plaintext UDP datagrams and acts on it. An attacker that ispresent on the local network can impact Babel operation in a variety ofways; for example they can:¶
When carried over IPv6, Babel packets are ignored unless they are sentfrom a link-local IPv6 address; since routers don't forward link-localIPv6 packets, this mitigates the attacks outlined above by restrictingthem to on-link attackers. No such natural protection exists when Babelpackets are carried over IPv4, which is one of the reasons why it isrecommended to deploy Babel over IPv6(Section 3.1).¶
It is usually difficult to ensure that packets arriving at a Babel nodeare trusted, even in the case where the local link is believed to besecure. For that reason, it isRECOMMENDED that all Babel traffic beprotected by an application-layer cryptographic protocol. There arecurrently two suitable mechanisms, which implement different trade-offsbetween implementation simplicity and security:¶
Both mechanisms enable nodes to ignore packets generated by attackerswithout the proper credentials. They also ensure integrity of messagesand prevent message replay. While Babel-DTLS supports asymmetric keyingand ensures confidentiality, Babel-MAC has a much more limited scope (seeSections1.1,1.2, and7 of[RFC8967]). Since Babel-MACis simpler and more lightweight, it is recommended in preference toBabel-DTLS in deployments where its limitations are acceptable, i.e., whensymmetric keying is sufficient and where the routing information is notconsidered confidential.¶
Every implementation of BabelSHOULD implement BABEL-MAC.¶
One should be aware that the information that a mobile Babel nodeannounces to the whole routing domain is sufficient to determine the mobilenode's physical location with reasonable precision, which might causeprivacy concerns even if the control traffic is protected fromunauthenticated attackers by a cryptographic mechanism such as Babel-DTLS.This issue may be mitigated somewhat by using randomly chosen router-idsand randomly chosen IP addresses, and changing them often enough.¶
The strategy for computing link costs and route metrics is a localmatter; Babel itself only requires that it comply with the conditions giveninSection 3.4.3 andSection 3.5.2.Different nodes may use different strategies in a single network and mayuse different strategies on different interface types. This section describesa set of strategies that have been found to work well in actual networks.¶
In summary, a node maintains per-neighbour statistics about the last 16received Hello TLVs of each kind (Appendix A.1),it computes costs by using the 2-out-of-3 strategy (Appendix A.2.1) onwired links and Expected Transmission Cost (ETX) (Appendix A.2.2) on wireless links. It uses anadditive algebra for metric computation (Section 3.5.2).¶
For each neighbour, a node maintains two sets of Hello history, one foreach kind of Hello, and an expected sequence number, one for Multicast andone for Unicast Hellos. Each Hello history is a vector of 16 bits, wherea 1 value represents a received Hello, and a 0 value a missed Hello. Foreach kind of Hello, the expected sequence number, written ne, is thesequence number that is expected to be carried by the next received Hellofrom this neighbour.¶
Whenever it receives a Hello packet of a given kind from a neighbour,a node compares the received sequence number nr for that kind of Hellowith its expected sequence number ne. Depending on the outcome of thiscomparison, one of the following actions is taken:¶
The receiving node then appends a 1 bit to the Hello history and sets neto (nr + 1). If the Interval field of the received Hello is not zero, itresets the neighbour's hello timer to 1.5 times the advertised Interval(the extra margin allows for delay due to jitter).¶
Whenever either hello timer associated with a neighbour expires, thelocal node adds a 0 bit to the corresponding Hello history, and incrementsthe expected Hello number. If both Hello histories are empty (theycontain 0 bits only), the neighbour entry is flushed; otherwise, therelevant hello timer is reset to the value advertised in the last Hello ofthat kind received from this neighbour (no extra margin is necessary inthis case, since jitter was already taken into account when computing thetimeout that has just expired).¶
This section describes two algorithms suitable for computing costs(Section 3.4.3) based on Hello history.Appendix A.2.1 applies to wired links andAppendix A.2.2 towireless links.RECOMMENDED default values of the parameters that appearin these algorithms are given inAppendix B.¶
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 casethey drop all packets.¶
The k-out-of-j strategy is parameterised by two small integers k and j,such that 0 < k <= j, and the nominal link cost, a constant C >= 1.A node keeps a history of the last j hellos; if k or more of those havebeen correctly received, the link is assumed to be up, and the rxcost isset to C; otherwise, the link is assumed to be down, and the rxcost is setto infinity.¶
Since Babel supports two kinds of Hellos, a Babel node performsk-out-of-j twice for each neighbour, once on the Unicast Hello history and once on theMulticast Hello history. If either of the instances of k-out-of-jindicates that the link is up, then the link is assumed to be up, and therxcost is set to C; if both instances indicate that the link is down, thenthe link is assumed to be down, and the rxcost is set to infinity. Inother words, the resulting rxcost is the minimum of the rxcosts yielded bythe two instances of k-out-of-j link sensing.¶
The cost of a link performing k-out-of-j link sensing is defined asfollows:¶
Unlike wired links which are bimodal (either up or down), wirelesslinks exhibit continuous variation of the link quality. Naive applicationof hop-count routing in networks that use wireless links for transit tendsto select long, lossy links in preference to shorter, lossless links,which can dramatically reduce throughput. For that reason, a routingprotocol designed to support wireless links must perform some form oflink quality estimation.¶
The Expected Transmission Cost algorithm, or ETX[ETX],is a simple link quality estimation algorithm that is designed to workwell with the IEEE 802.11 MAC[IEEE802.11]. Bydefault, the IEEE 802.11 MAC performs Automatic Repeat Query (ARQ)and rate adaptation on unicast frames, but not on multicast frames, whichare sent at a fixed rate with no ARQ; therefore, measuring the loss rateof multicast frames yields a useful estimate of a link's quality.¶
A node performing ETX link quality estimation uses a neighbour'sMulticast Hello history to compute an estimate, written beta, of theprobability that a Hello TLV is successfully received. Beta can becomputed as the fraction of 1 bits within a small number (say, 6) of themost recent entries in the Multicast Hello history, or it can be anexponential average, or some combination of both approaches. Let rxcostbe 256/beta.¶
Let alpha be MIN(1, 256/txcost), an estimate of the probability ofsuccessfully sending a Hello TLV. The cost is then computed by¶
cost = 256/(alpha * beta)¶
or, equivalently,¶
cost = (MAX(txcost, 256) * rxcost) / 256.¶
Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicastframes do not provide a useful measure of link quality, and therefore ETXignores the Unicast Hello history. Thus, a node performing ETXlink quality estimation will not route through neighbouring nodes unlessthey send periodic Multicast Hellos (possibly in addition to UnicastHellos).¶
Route selection (Section 3.6) is the process bywhich a node selects a single route among the routes that it has availabletowards a given destination. With Babel, any route selection procedurethat only ever chooses feasible routes with a finite metric will yielda set of loop-free routes; however, in the presence of continuouslyvariable metrics such as ETX (Appendix A.2.2), a naive routeselection procedure might lead to persistent oscillations. Suchoscillations can be limited or avoided altogether by implementinghysteresis within the route selection algorithm, i.e., by making the routeselection algorithm sensitive to a route's history. Any reasonablehysteresis algorithm should yield good results; the following algorithmis simple to implement and has been successfully deployed in a variety ofenvironments.¶
For every route R, in addition to the route's metric m(R), maintaina smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R) as anexponentially smoothed average (seeSection 3.7 of [RFC793])of m(R) with a time constant equal to the Hello interval multiplied bya small number such as 3). If no route to a given destination is selected,then select the route with the smallest metric, ignoring the smoothedmetric. If a route R is selected, then switch to a route R' only whenboth m(R') < m(R) and ms(R') < ms(R).¶
Intuitively, the smoothed metric is a long-term estimate of the qualityof a route. The algorithm above works by only switching routes when boththe instantaneous and the long-term estimates of the route's qualityindicate that switching is profitable.¶
The choice of time constants is a trade-off between fast detection ofmobility events and protocol overhead. Two instances of Babel runningwith different time constants will interoperate, although the resultingworst-case convergence time will be dictated by the slower of the two.¶
The Hello interval is the most important time constant: an outage ora mobility event is detected within 1.5 to 3.5 Hello intervals. Due toBabel's use of a redundant route table, and due to its reliance ontriggered updates and explicit requests, the Update interval has littleinfluence on the time needed to reconverge after an outage: in practice,it only has a significant effect on the time needed to acquire new routesafter a mobility event. While the protocol allows intervals as low as10 ms, such low values would cause significant amounts of protocol trafficfor little practical benefit.¶
The following values have been found to work well in a variety ofenvironments and are thereforeRECOMMENDED default values:¶
Route filtering is a procedure where an instance of a routing protocoleither discards some of the routes announced by its neighbours or learnsthem with a metric that is higher than what would be expected. Like alldistance-vector protocols, Babel has the ability to apply arbitraryfiltering to the routes it learns, and implementations of Babel that applydifferent sets of filtering rules will interoperate without causingrouting loops. The protocol's ability to perform route filtering isa consequence of the latitude given inSection 3.5.2:Babel can use any metric that is strictly monotonic, including one thatassigns an infinite metric to a selected subset of routes. (See alsoSection 3.8.1, where requests for nonexistent routesare treated in the same way as requests for routes with infinite metric.)¶
It is not in general correct to learn a route with a metric smallerthan the one it was announced with, or to replace a route's destinationprefix with a more specific (longer) one. Doing either of these may causepersistent routing loops.¶
Route filtering is a useful tool, since it allows fine-grained tuningof the routing decisions made by the routing protocol. Accordingly, someimplementations of Babel implement a rich configuration language thatallows applying filtering to sets of routes defined, for example, byincoming interface and destination prefix.¶
In order to limit the consequences of misconfiguration, Babelimplementations provide a reasonable set of default filtering rules evenwhen they don't allow configuration of filtering by the user. Ata minimum, they discard routes with a destination prefix in fe80::/64,ff00::/8, 127.0.0.1/32, 0.0.0.0/32, and 224.0.0.0/8.¶
Babel is an extensible protocol, and this document defines a number ofmechanisms that can be used to extend the protocol in a backwardscompatible manner:¶
This appendix is intended to guide designers of protocol extensions inchoosing a particular encoding.¶
The version number in the Babel header should only be increased if thenew version is not backwards compatible with the original protocol.¶
In many cases, an extension could be implemented either by defininga new TLV or by adding a new sub-TLV to an existing TLV. For example, anextension whose purpose is to attach additional data to route updates canbe implemented either by creating a new "enriched" Update TLV, by addinga nonmandatory sub-TLV to the Update TLV, or by adding a mandatorysub-TLV.¶
The various encodings are treated differently by implementations thatdo not understand the extension. In the case of a new TLV or of a sub-TLVwith the mandatory bit set, the whole TLV is ignored by implementationsthat do not implement the extension, while in the case of a nonmandatorysub-TLV, the TLV is parsed and acted upon, and only the unknown sub-TLV issilently ignored. Therefore, a nonmandatory sub-TLV should be used byextensions that extend the Update in a compatible manner (the extensiondata may be silently ignored), while a mandatory sub-TLV or a new TLV mustbe used by extensions that make incompatible extensions to the meaning ofthe TLV (the whole TLV must be thrown away if the extension data is notunderstood).¶
Experience shows that the need for additional data tends to crop up inthe most unexpected places. Hence, it is recommended that extensions thatdefine new TLVs should make them self-terminating and allow attachingsub-TLVs to them.¶
Adding a new AE is essentially equivalent to adding a new TLV: UpdateTLVs 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 createsa new set of compression state. Additionally, since the Next Hop TLVcreates state specific to a given address family, as opposed to a givenAE, a new AE for a previously defined address family must not be used inthe Next Hop TLV if backwards compatibility is required. A similar issuearises with Update TLVs with unknown AEs establishing a new router-id (dueto the Router-Id flag being set). Therefore, defining new AEs must bedone with care if compatibility with unextended implementations isrequired.¶
The packet trailer is intended to carry cryptographic signatures thatonly cover the packet body; storing the cryptographic signatures in thepacket trailer avoids clearing the signature before computing a hash ofthe packet body, and makes it possible to check a cryptographic signaturebefore running the full, stateful TLV parser. Hence, only TLVs that don'tneed to be protected by cryptographic security protocols should be allowedin the packet trailer. Any such TLVs should be easy to parse and, inparticular, should not require stateful parsing.¶
Babel is a fairly economic protocol. Updates take between 12 and 40octets per destination, depending on the address family and how successfulcompression is; in a dual-stack flat network, an average of less than 24octets per update is typical. The route table occupies about 35 octetsper IPv6 entry. To put these values into perspective, a single full-sizeEthernet frame can carry some 65 route updates, and a megabyte of memorycan contain a 20,000-entry route table and the associated source table.¶
Babel is also a reasonably simple protocol. One complete implementationconsists of less than 12,000 lines of C code, and it compiles to lessthan 120 KB of text on a 32-bit CISC architecture; about half of thisfigure is due to protocol extensions and user-interface code.¶
Nonetheless, in some very constrained environments, such as PDAs,microwave ovens, or abacuses, it may be desirable to have subsetimplementations of the protocol.¶
There are many different definitions of a stub router, but for theneeds of this section, a stub implementation of Babel is one that announcesone or more directly attached prefixes into a Babel network but doesn'tre-announce any routes that it has learnt from its neighbours, and alwaysprefers the direct route to a directly attached prefix to a route learntover the Babel protocol, even when the prefixes are the same. It mayeither maintain a full routing table or simply select a default gatewaythrough any one of its neighbours that announces a default route. Sincea stub implementation never forwards packets except from or to a directlyattached link, it cannot possibly participate in a routing loop, and henceit need not evaluate the feasibility condition or maintain a sourcetable.¶
No matter how primitive, a stub implementation must parse sub-TLVsattached to any TLVs that it understands and check the mandatory bit.It must answer acknowledgment requests and must participate in theHello/IHU protocol. It must also be able to reply to seqno requests forroutes that it announces, and it should be able to reply to routerequests.¶
Experience shows that an IPv6-only stub implementation of Babel can bewritten in less than 1,000 lines of C code and compile to 13 KB oftext on 32-bit CISC architecture.¶
The protocol defined in this document is a successor to the protocoldefined in[RFC6126] and[RFC7557]. Whilethe two protocols are not entirely compatible, the new protocol has beendesigned so that it can be deployed in existing RFC 6126 networks withoutrequiring a flag day.¶
There are three optional features that make this protocolincompatible with its predecessor. First of all, RFC 6126 did not defineUnicast Hellos (Section 3.4.1), and animplementation of RFC 6126 will misinterpret a Unicast Hello fora Multicast one; since the sequence number space of Unicast Hellos isdistinct from the sequence number space of Multicast Hellos, sending a UnicastHello to an implementation of RFC 6126 will confuse its link qualityestimator. Second, RFC 6126 did not define unscheduled Hellos, and animplementation of RFC 6126 will mis-parse Hellos with an interval equal to0. Finally, RFC 7557 did not define mandatory sub-TLVs (Section 4.4), and thus an implementation of RFCs 6126 and7557 will not correctly ignore a TLV that carries an unknown mandatorysub-TLV; depending on the sub-TLV, this might cause routing pathologies.¶
An implementation of this specification that never sends Unicast orunscheduled Hellos and doesn't implement any extensions that use mandatorysub-TLVs is safe to deploy in a network in which some nodes implement theprotocol described in RFCs 6126 and 7557.¶
Two changes need to be made to an implementation of RFCs 6126 and 7557so that it can safely interoperate in all cases with implementations ofthis protocol. First, it needs to be modified either to ignore or to processUnicast and unscheduled Hellos. Second, it needs to be modified to parsesub-TLVs of all the TLVs that it understands and that allow sub-TLVs, andto ignore the TLV if an unknown mandatory sub-TLV is found. It is notnecessary to parse unknown TLVs, as these are ignored in any case.¶
There are other changes, but these are not of a nature to preventinteroperability:¶
A number of people have contributed text and ideas to thisspecification. The authors are particularly indebted toMatthieu Boutier,Gwendoline Chouasne,Margaret Cullen,Donald Eastlake,Toke Høiland-Jørgensen,Benjamin Kaduk,Joao Sobrinho, andMartin Vigoureux.The previous version of this specification[RFC6126] greatly benefited from the input ofJoel Halpern. The address compressiontechnique was inspired by[PACKETBB].¶