summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc6126.txt
diff options
context:
space:
mode:
authorThomas Voss <mail@thomasvoss.com> 2024-11-27 20:54:24 +0100
committerThomas Voss <mail@thomasvoss.com> 2024-11-27 20:54:24 +0100
commit4bfd864f10b68b71482b35c818559068ef8d5797 (patch)
treee3989f47a7994642eb325063d46e8f08ffa681dc /doc/rfc/rfc6126.txt
parentea76e11061bda059ae9f9ad130a9895cc85607db (diff)
doc: Add RFC documents
Diffstat (limited to 'doc/rfc/rfc6126.txt')
-rw-r--r--doc/rfc/rfc6126.txt2523
1 files changed, 2523 insertions, 0 deletions
diff --git a/doc/rfc/rfc6126.txt b/doc/rfc/rfc6126.txt
new file mode 100644
index 0000000..38b3b4e
--- /dev/null
+++ b/doc/rfc/rfc6126.txt
@@ -0,0 +1,2523 @@
+
+
+
+
+
+
+Independent Submission J. Chroboczek
+Request for Comments: 6126 PPS, University of Paris 7
+Category: Experimental April 2011
+ISSN: 2070-1721
+
+
+ The Babel Routing Protocol
+
+Abstract
+
+ Babel is a loop-avoiding distance-vector routing protocol that is
+ robust and efficient both in ordinary wired networks and in wireless
+ mesh networks.
+
+Status of This Memo
+
+ This document is not an Internet Standards Track specification; it is
+ published for examination, experimental implementation, and
+ evaluation.
+
+ This document defines an Experimental Protocol for the Internet
+ community. This is a contribution to the RFC Series, independently
+ of any other RFC stream. The RFC Editor has chosen to publish this
+ document at its discretion and makes no statement about its value for
+ implementation or deployment. Documents approved for publication by
+ the RFC Editor are not a candidate for any level of Internet
+ Standard; see Section 2 of RFC 5741.
+
+ Information about the current status of this document, any errata,
+ and how to provide feedback on it may be obtained at
+ http://www.rfc-editor.org/info/rfc6126.
+
+Copyright Notice
+
+ Copyright (c) 2011 IETF Trust and the persons identified as the
+ document authors. All rights reserved.
+
+ This document is subject to BCP 78 and the IETF Trust's Legal
+ Provisions Relating to IETF Documents
+ (http://trustee.ietf.org/license-info) in effect on the date of
+ publication of this document. Please review these documents
+ carefully, as they describe your rights and restrictions with respect
+ to this document.
+
+
+
+
+
+
+
+
+Chroboczek Experimental [Page 1]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+Table of Contents
+
+ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
+ 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . . 3
+ 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4
+ 1.3. Specification of Requirements . . . . . . . . . . . . . . 4
+ 2. Conceptual Description of the Protocol . . . . . . . . . . . . 4
+ 2.1. Costs, Metrics, and Neighbourship . . . . . . . . . . . . 5
+ 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . . 5
+ 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6
+ 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . . 6
+ 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8
+ 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . . 9
+ 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . . 10
+ 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . . 11
+ 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 11
+ 3.1. Message Transmission and Reception . . . . . . . . . . . . 11
+ 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12
+ 3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . . 15
+ 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 15
+ 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 17
+ 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21
+ 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22
+ 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24
+ 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 27
+ 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 28
+ 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29
+ 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . . 29
+ 4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . . 30
+ 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39
+ 6. Security Considerations . . . . . . . . . . . . . . . . . . . 39
+ 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 40
+ 7.1. Normative References . . . . . . . . . . . . . . . . . . . 40
+ 7.2. Informative References . . . . . . . . . . . . . . . . . . 40
+ Appendix A. Cost and Metric Computation . . . . . . . . . . . . . 41
+ A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 41
+ A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . . 42
+ A.3. Metric Computation . . . . . . . . . . . . . . . . . . . . 43
+ Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . . 43
+ Appendix C. Simplified Implementations . . . . . . . . . . . . . 44
+ Appendix D. Software Availability . . . . . . . . . . . . . . . . 45
+
+
+
+
+
+
+
+
+
+
+Chroboczek Experimental [Page 2]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+1. Introduction
+
+ Babel is a loop-avoiding distance-vector routing protocol that is
+ designed to be robust and efficient both in networks using prefix-
+ based routing and in networks using flat routing ("mesh networks"),
+ and both in relatively stable wired networks and in highly dynamic
+ wireless networks.
+
+1.1. Features
+
+ The main property that makes Babel suitable for unstable networks is
+ that, unlike naive distance-vector routing protocols [RIP], it
+ strongly limits the frequency and duration of routing pathologies
+ such as routing loops and black-holes during reconvergence. Even
+ after a mobility event is detected, a Babel network usually remains
+ loop-free. Babel then quickly reconverges to a configuration that
+ preserves the loop-freedom and connectedness of the network, but is
+ not necessarily optimal; in many cases, this operation requires no
+ packet exchanges at all. Babel then slowly converges, in a time on
+ the scale of minutes, to an optimal configuration. This is achieved
+ by using sequenced routes, a technique pioneered by Destination-
+ Sequenced Distance-Vector routing [DSDV].
+
+ More precisely, Babel has the following properties:
+
+ o when every prefix is originated by at most one router, Babel never
+ suffers from routing loops;
+
+ o when a prefix is originated by multiple routers, Babel may
+ occasionally create a transient routing loop for this particular
+ prefix; this loop disappears in a time proportional to its
+ diameter, and never again (up to an arbitrary garbage-collection
+ (GC) time) will the routers involved participate in a routing loop
+ for the same prefix;
+
+ o assuming reasonable packet loss rates, any routing black-holes
+ that may appear after a mobility event are corrected in a time at
+ most proportional to the network's diameter.
+
+ Babel has provisions for link quality estimation and for fairly
+ arbitrary metrics. When configured suitably, Babel can implement
+ shortest-path routing, or it may use a metric based, for example, on
+ measured packet loss.
+
+ Babel nodes will successfully establish an association even when they
+ are configured with different parameters. For example, a mobile node
+ that is low on battery may choose to use larger time constants (hello
+ and update intervals, etc.) than a node that has access to wall
+
+
+
+Chroboczek Experimental [Page 3]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ power. Conversely, a node that detects high levels of mobility may
+ choose to use smaller time constants. The ability to build such
+ heterogeneous networks makes Babel particularly adapted to the
+ wireless environment.
+
+ Finally, Babel is a hybrid routing protocol, in the sense that it can
+ carry routes for multiple network-layer protocols (IPv4 and IPv6),
+ whichever protocol the Babel packets are themselves being carried
+ over.
+
+1.2. Limitations
+
+ Babel has two limitations that make it unsuitable for use in some
+ environments. First, Babel relies on periodic routing table updates
+ rather than using a reliable transport; hence, in large, stable
+ networks it generates more traffic than protocols that only send
+ updates when the network topology changes. In such networks,
+ protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced
+ Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more
+ suitable.
+
+ Second, Babel does impose a hold time when a prefix is retracted
+ (Section 3.5.5). While this hold time does not apply to the exact
+ prefix being retracted, and hence does not prevent fast reconvergence
+ should it become available again, it does apply to any shorter prefix
+ that covers it. Hence, if a previously deaggregated prefix becomes
+ aggregated, it will be unreachable for a few minutes. This makes
+ Babel unsuitable for use in mobile networks that implement automatic
+ prefix aggregation.
+
+1.3. Specification of Requirements
+
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
+ document are to be interpreted as described in [RFC2119].
+
+2. Conceptual Description of the Protocol
+
+ Babel is a mostly loop-free distance vector protocol: it is based on
+ the Bellman-Ford protocol, just like the venerable RIP [RIP], but
+ includes a number of refinements that either prevent loop formation
+ altogether, or ensure that a loop disappears in a timely manner and
+ doesn't form again.
+
+ Conceptually, Bellman-Ford is executed in parallel for every source
+ of routing information (destination of data traffic). In the
+ following discussion, we fix a source S; the reader will recall that
+ the same algorithm is executed for all sources.
+
+
+
+Chroboczek Experimental [Page 4]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+2.1. Costs, Metrics, and Neighbourship
+
+ As many routing algorithms, Babel computes costs of links between any
+ two neighbouring nodes, abstract values attached to the edges between
+ two nodes. We write C(A, B) for the cost of the edge from node A to
+ node B.
+
+ Given a route between any two nodes, the metric of the route is the
+ sum of the costs of all the edges along the route. The goal of the
+ routing algorithm is to compute, for every source S, the tree of the
+ routes of lowest metric to S.
+
+ Costs and metrics need not be integers. In general, they can be
+ values in any algebra that satisfies two fairly general conditions
+ (Section 3.5.2).
+
+ A Babel node periodically broadcasts Hello messages to all of its
+ neighbours; it also periodically sends an IHU ("I Heard You") message
+ to every neighbour from which it has recently heard a Hello. From
+ the information derived from Hello and IHU messages received from its
+ neighbour B, a node A computes the cost C(A, B) of the link from A to
+ B.
+
+2.2. The Bellman-Ford Algorithm
+
+ Every node A maintains two pieces of data: its estimated distance to
+ S, written D(A), and its next-hop router to S, written NH(A).
+ Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined.
+
+ Periodically, every node B sends to all of its neighbours a route
+ update, a message containing D(B). When a neighbour A of B receives
+ the route update, it checks whether B is its selected next hop; if
+ that is the case, then NH(A) is set to B, and D(A) is set to C(A, B)
+ + D(B). If that is not the case, then A compares C(A, B) + D(B) to
+ its current value of D(A). If that value is smaller, meaning that
+ the received update advertises a route that is better than the
+ currently selected route, then NH(A) is set to B, and D(A) is set to
+ C(A, B) + D(B).
+
+ A number of refinements to this algorithm are possible, and are used
+ by Babel. In particular, convergence speed may be increased by
+ sending unscheduled "triggered updates" whenever a major change in
+ the topology is detected, in addition to the regular, scheduled
+ updates. Additionally, a node may maintain a number of alternate
+ routes, which are being advertised by neighbours other than its
+ selected neighbour, and which can be used immediately if the selected
+ route were to fail.
+
+
+
+
+Chroboczek Experimental [Page 5]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+2.3. Transient Loops in Bellman-Ford
+
+ It is well known that a naive application of Bellman-Ford to
+ distributed routing can cause transient loops after a topology
+ change. Consider for example the following diagram:
+
+ B
+ 1 /|
+ 1 / |
+ S --- A |1
+ \ |
+ 1 \|
+ C
+
+ After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.
+
+ Suppose now that the link between S and A fails:
+
+ B
+ 1 /|
+ / |
+ S A |1
+ \ |
+ 1 \|
+ C
+
+ When it detects the failure of the link, A switches its next hop to B
+ (which is still advertising a route to S with metric 2), and
+ advertises a metric equal to 3, and then advertises a new route with
+ metric 3. This process of nodes changing selected neighbours and
+ increasing their metric continues until the advertised metric reaches
+ "infinity", a value larger than all the metrics that the routing
+ protocol is able to carry.
+
+2.4. Feasibility Conditions
+
+ Bellman-Ford is a very robust algorithm: its convergence properties
+ are preserved when routers delay route acquisition or when they
+ discard some updates. Babel routers discard received route
+ announcements unless they can prove that accepting them cannot
+ possibly cause a routing loop.
+
+ More formally, we define a condition over route announcements, known
+ as the feasibility condition, that guarantees the absence of routing
+ loops whenever all routers ignore route updates that do not satisfy
+ the feasibility condition. In effect, this makes Bellman-Ford into a
+ family of routing algorithms, parameterised by the feasibility
+ condition.
+
+
+
+Chroboczek Experimental [Page 6]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Many different feasibility conditions are possible. For example, BGP
+ can be modelled as being a distance-vector protocol with a (rather
+ drastic) feasibility condition: a routing update is only accepted
+ when the receiving node's AS number is not included in the update's
+ AS-Path attribute (note that BGP's feasibility condition does not
+ ensure the absence of transitory "micro-loops" during reconvergence).
+
+ Another simple feasibility condition, used in Destination-Sequenced
+ Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand
+ Distance Vector (AODV) routing, stems from the following observation:
+ a routing loop can only arise after a router has switched to a route
+ with a larger metric than the route that it had previously selected.
+ Hence, one could decide that a route is feasible only when its metric
+ at the local node would be no larger than the metric of the currently
+ selected route, i.e., an announcement carrying a metric D(B) is
+ accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this
+ constraint, then the metric at every router is nonincreasing, and the
+ following invariant is always preserved: if A has selected B as its
+ successor, then D(B) < D(A), which implies that the forwarding graph
+ is loop-free.
+
+ Babel uses a slightly more refined feasibility condition, used in
+ EIGRP [DUAL]. Given a router A, define the feasibility distance of
+ A, written FD(A), as the smallest metric that A has ever advertised
+ for S to any of its neighbours. An update sent by a neighbour B of A
+ is feasible when the metric D(B) advertised by B is strictly smaller
+ than A's feasibility distance, i.e., when D(B) < FD(A).
+
+ It is easy to see that this latter condition is no more restrictive
+ than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility;
+ then D(A) is nonincreasing, hence at all times D(A) <= FD(A).
+ Suppose now that A receives a DSDV-feasible update that advertises a
+ metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <=
+ D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A).
+
+ To see that it is strictly less restrictive, consider the following
+ diagram, where A has selected the route through B, and D(A) = FD(A) =
+ 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible
+ for A, although its metric C(A, C) + D(C) = 5 is larger than that of
+ the currently selected route:
+
+ B
+ 1 / \ 1
+ / \
+ S A
+ \ /
+ 1 \ / 4
+ C
+
+
+
+Chroboczek Experimental [Page 7]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ To show that this feasibility condition still guarantees loop-
+ freedom, recall that at the time when A accepts an update from B, the
+ metric D(B) announced by B is no smaller than FD(B); since it is
+ smaller than FD(A), at that point in time FD(B) < FD(A). Since this
+ property is preserved when A sends updates, it remains true at all
+ times, which ensures that the forwarding graph has no loops.
+
+2.5. Solving Starvation: Sequencing Routes
+
+ Obviously, the feasibility conditions defined above cause starvation
+ when a router runs out of feasible routes. Consider the following
+ diagram, where both A and B have selected the direct route to S:
+
+ A
+ 1 /| D(A) = 1
+ / | FD(A) = 1
+ S |1
+ \ | D(B) = 2
+ 2 \| FD(B) = 2
+ B
+
+ Suppose now that the link between A and S breaks:
+
+ A
+ |
+ | FD(A) = 1
+ S |1
+ \ | D(B) = 2
+ 2 \| FD(B) = 2
+ B
+
+ The only route available from A to S, the one that goes through B, is
+ not feasible: A suffers from a spurious starvation.
+
+ At this point, the whole network must be rebooted in order to solve
+ the starvation; this is essentially what EIGRP does when it performs
+ a global synchronisation of all the routers in the network with the
+ source (the "active" phase of EIGRP).
+
+ Babel reacts to starvation in a less drastic manner, by using
+ sequenced routes, a technique introduced by DSDV and adopted by AODV.
+ In addition to a metric, every route carries a sequence number, a
+ nondecreasing integer that is propagated unchanged through the
+ network and is only ever incremented by the source; a pair (s, m),
+ where s is a sequence number and m a metric, is called a distance.
+
+ A received update is feasible when either it is more recent than the
+ feasibility distance maintained by the receiving node, or it is
+
+
+
+Chroboczek Experimental [Page 8]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ equally recent and the metric is strictly smaller. More formally, if
+ FD(A) = (s, m), then an update carrying the distance (s', m') is
+ feasible when either s' > s, or s = s' and m' < m.
+
+ Assuming the sequence number of S is 137, the diagram above becomes:
+
+ A
+ |
+ | FD(A) = (137, 1)
+ S |1
+ \ | D(B) = (137, 2)
+ 2 \| FD(B) = (137, 2)
+ B
+
+ After S increases its sequence number, and the new sequence number is
+ propagated to B, we have:
+
+ A
+ |
+ | FD(A) = (137, 1)
+ S |1
+ \ | D(B) = (138, 2)
+ 2 \| FD(B) = (138, 2)
+ B
+
+ at which point the route through B becomes feasible again.
+
+ Note that while sequence numbers are used for determining
+ feasibility, they are not necessarily used in route selection: a node
+ will normally ignore the sequence number when selecting a route
+ (Section 3.6).
+
+2.6. Requests
+
+ In DSDV, the sequence number of a source is increased periodically.
+ A route becomes feasible again after the source increases its
+ sequence number, and the new sequence number is propagated through
+ the network, which may, in general, require a significant amount of
+ time.
+
+ Babel takes a different approach. When a node detects that it is
+ suffering from a potentially spurious starvation, it sends an
+ explicit request to the source for a new sequence number. This
+ request is forwarded hop by hop to the source, with no regard to the
+ feasibility condition. Upon receiving the request, the source
+ increases its sequence number and broadcasts an update, which is
+ forwarded to the requesting node.
+
+
+
+
+Chroboczek Experimental [Page 9]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Note that after a change in network topology not all such requests
+ will, in general, reach the source, as some will be sent over links
+ that are now broken. However, if the network is still connected,
+ then at least one among the nodes suffering from spurious starvation
+ has an (unfeasible) route to the source; hence, in the absence of
+ packet loss, at least one such request will reach the source.
+ (Resending requests a small number of times compensates for packet
+ loss.)
+
+ Since requests are forwarded with no regard to the feasibility
+ condition, they may, in general, be caught in a forwarding loop; this
+ is avoided by having nodes perform duplicate detection for the
+ requests that they forward.
+
+2.7. Multiple Routers
+
+ The above discussion assumes that every prefix is originated by a
+ single router. In real networks, however, it is often necessary to
+ have a single prefix originated by multiple routers; for example, the
+ default route will be originated by all of the edge routers of a
+ routing domain.
+
+ Since synchronising sequence numbers between distinct routers is
+ problematic, Babel treats routes for the same prefix as distinct
+ entities when they are originated by different routers: every route
+ announcement carries the router-id of its originating router, and
+ feasibility distances are not maintained per prefix, but per source,
+ where a source is a pair of a router-id and a prefix. In effect,
+ Babel guarantees loop-freedom for the forwarding graph to every
+ source; since the union of multiple acyclic graphs is not in general
+ acyclic, Babel does not in general guarantee loop-freedom when a
+ prefix is originated by multiple routers, but any loops will be
+ broken in a time at most proportional to the diameter of the loop --
+ as soon as an update has "gone around" the routing loop.
+
+ Consider for example the following diagram, where A has selected the
+ default route through S, and B has selected the one through S':
+
+ 1 1 1
+ ::/0 -- S --- A --- B --- S' -- ::/0
+
+ Suppose that both default routes fail at the same time; then nothing
+ prevents A from switching to B, and B simultaneously switching to A.
+ However, as soon as A has successfully advertised the new route to B,
+ the route through A will become unfeasible for B. Conversely, as
+ soon as B will have advertised the route through A, the route through
+ B will become unfeasible for A.
+
+
+
+
+Chroboczek Experimental [Page 10]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ In effect, the routing loop disappears at the latest when routing
+ information has gone around the loop. Since this process can be
+ delayed by lost packets, Babel makes certain efforts to ensure that
+ updates are sent reliably after a router-id change.
+
+ Additionally, after the routers have advertised the two routes, both
+ sources will be in their source tables, which will prevent them from
+ ever again participating in a routing loop involving routes from S
+ and S' (up to the source GC time, which, available memory permitting,
+ can be set to arbitrarily large values).
+
+2.8. Overlapping Prefixes
+
+ In the above discussion, we have assumed that all prefixes are
+ disjoint, as is the case in flat ("mesh") routing. In practice,
+ however, prefixes may overlap: for example, the default route
+ overlaps with all of the routes present in the network.
+
+ After a route fails, it is not correct in general to switch to a
+ route that subsumes the failed route. Consider for example the
+ following configuration:
+
+ 1 1
+ ::/0 -- A --- B --- C
+
+ Suppose that node C fails. If B forwards packets destined to C by
+ following the default route, a routing loop will form, and persist
+ until A learns of B's retraction of the direct route to C. Babel
+ avoids this pitfall by maintaining an "unreachable" route for a few
+ minutes after a route is retracted; the time for which such a route
+ must be maintained should be the worst-case propagation time of the
+ retraction of the route to C.
+
+3. Protocol Operation
+
+ Every Babel speaker is assigned a router-id, which is an arbitrary
+ string of 8 octets that is assumed unique across the routing domain.
+ We suggest that router-ids should be assigned in modified EUI-64
+ format [ADDRARCH]. (As a matter of fact, the protocol encoding is
+ slightly more compact when router-ids are assigned in the same manner
+ as the IPv6 layer assigns host IDs.)
+
+3.1. Message Transmission and Reception
+
+ Babel protocol packets are sent in the body of a UDP datagram. Each
+ Babel packet consists of one or more TLVs.
+
+
+
+
+
+Chroboczek Experimental [Page 11]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ 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 (this is the usual case) or to a
+ (link-local) unicast address. In normal operation, a Babel speaker
+ sends both multicast and unicast packets to its neighbours.
+
+ With the exception of Hello TLVs and acknowledgements, all Babel TLVs
+ can be sent to either unicast or multicast addresses, and their
+ semantics does not depend on whether the destination was a unicast or
+ multicast address. Hence, a Babel speaker does not need to determine
+ the destination address of a packet that it receives in order to
+ interpret it.
+
+ A moderate amount of jitter is applied to packets sent by a Babel
+ speaker: outgoing TLVs are buffered and SHOULD be sent with a small
+ random delay. This is done for two purposes: it avoids
+ synchronisation of multiple Babel speakers across a network [JITTER],
+ and it allows for the aggregation of multiple TLVs into a single
+ packet.
+
+ The exact delay and amount of jitter applied to a packet depends on
+ whether it contains any urgent TLVs. Acknowledgement TLVs MUST be
+ sent before the deadline specified in the corresponding request. The
+ particular class of updates specified in Section 3.7.2 MUST be sent
+ in a timely manner. The particular class of request and update TLVs
+ specified in Section 3.8.2 SHOULD be sent in a timely manner.
+
+3.2. Data Structures
+
+ Every Babel speaker maintains a number of data structures.
+
+3.2.1. Sequence Number
+
+ A node's sequence number is a 16-bit integer that is included in
+ route updates sent for routes originated by this node. A node
+ increments its sequence number (modulo 2^16) whenever it receives a
+ request for a new sequence number (Section 3.8.1.2).
+
+ A node SHOULD NOT increment its sequence number (seqno)
+ spontaneously, since increasing seqnos makes it less likely that
+ other nodes will have feasible alternate routes when their selected
+ routes fail.
+
+3.2.2. The Interface Table
+
+ The interface table contains the list of interfaces on which the node
+ speaks the Babel protocol. Every interface table entry contains the
+ interface's Hello seqno, a 16-bit integer that is sent with each
+
+
+
+Chroboczek Experimental [Page 12]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Hello TLV on this interface and is incremented (modulo 2^16) whenever
+ a Hello is sent. (Note that an interface's Hello seqno is unrelated
+ to the node's seqno.)
+
+ There are two timers associated with each interface table entry --
+ the Hello timer, which governs the sending of periodic Hello and IHU
+ packets, and the update timer, which governs the sending of periodic
+ route updates.
+
+3.2.3. The Neighbour Table
+
+ The neighbour table contains the list of all neighbouring interfaces
+ from which a Babel packet has been recently received. The neighbour
+ table is indexed by pairs of the form (interface, address), and every
+ neighbour table entry contains the following data:
+
+ o the local node's interface over which this neighbour is reachable;
+
+ o the address of the neighbouring interface;
+
+ o a history of recently received Hello packets from this neighbour;
+ this can, for example, be a sequence of n bits, for some small
+ value n, indicating which of the n hellos most recently sent by
+ this neighbour have been received by the local node;
+
+ o the "transmission cost" value from the last IHU packet received
+ from this neighbour, or FFFF hexadecimal (infinity) if the IHU
+ hold timer for this neighbour has expired;
+
+ o the neighbour's expected Hello sequence number, an integer modulo
+ 2^16.
+
+ There are two timers associated with each neighbour entry -- the
+ hello timer, which is initialised from the interval value carried by
+ Hello TLVs, and the IHU timer, which is initialised to a small
+ multiple of the interval carried in IHU TLVs.
+
+ Note that the neighbour table is indexed by IP addresses, not by
+ router-ids: neighbourship is a relationship between interfaces, not
+ between nodes. Therefore, two nodes with multiple interfaces can
+ participate in multiple neighbourship relationships, a fairly common
+ situation when wireless nodes with multiple radios are involved.
+
+3.2.4. The Source Table
+
+ The source table is used to record feasibility distances. It is
+ indexed by triples of the form (prefix, plen, router-id), and every
+ source table entry contains the following data:
+
+
+
+Chroboczek Experimental [Page 13]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ o the prefix (prefix, plen), where plen is the prefix length, that
+ this entry applies to;
+
+ o the router-id of a router originating this prefix;
+
+ o a pair (seqno, metric), this source's feasibility distance.
+
+ There is one timer associated with each entry in the source table --
+ the source garbage-collection timer. It is initialised to a time on
+ the order of minutes and reset as specified in Section 3.7.3.
+
+3.2.5. The Route Table
+
+ The route table contains the routes known to this node. It is
+ indexed by triples of the form (prefix, plen, neighbour), and every
+ route table entry contains the following data:
+
+ o the source (prefix, plen, router-id) for which this route is
+ advertised;
+
+ o the neighbour that advertised this route;
+
+ o the metric with which this route was advertised by the neighbour,
+ or FFFF hexadecimal (infinity) for a recently retracted route;
+
+ o the sequence number with which this route was advertised;
+
+ o the next-hop address of this route;
+
+ o a boolean flag indicating whether this route is selected, i.e.,
+ whether it is currently being used for forwarding and is being
+ advertised.
+
+ There is one timer associated with each route table entry -- the
+ route expiry timer. It is initialised and reset as specified in
+ Section 3.5.4.
+
+3.2.6. The Table of Pending Requests
+
+ The table of pending requests contains a list of seqno requests that
+ the local node has sent (either because they have been originated
+ locally, or because they were forwarded) and to which no reply has
+ been received yet. This table is indexed by prefixes, and every
+ entry in this table contains the following data:
+
+ o the prefix, router-id, and seqno being requested;
+
+
+
+
+
+Chroboczek Experimental [Page 14]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ o the neighbour, if any, on behalf of which we are forwarding this
+ request;
+
+ o a small integer indicating the number of times that this request
+ will be resent if it remains unsatisfied.
+
+ There is one timer associated with each pending request; it governs
+ both the resending of requests and their expiry.
+
+3.3. Acknowledged Packets
+
+ A Babel speaker may request that any neighbour receiving a given
+ packet reply with an explicit acknowledgement within a given time.
+ While the use of acknowledgement requests is optional, every Babel
+ speaker MUST be able to reply to such a request.
+
+ An acknowledgement MUST be sent to a unicast destination. On the
+ other hand, acknowledgement requests may be sent to either unicast or
+ multicast destinations, in which case they request an acknowledgement
+ from all of the receiving nodes.
+
+ When to request acknowledgements is a matter of local policy; the
+ simplest strategy is to never request acknowledgements and to rely on
+ periodic updates to ensure that any reachable routes are eventually
+ propagated throughout the routing domain. For increased efficiency,
+ we suggest that acknowledged packets should be used in order to send
+ urgent updates (Section 3.7.2) when the number of neighbours on a
+ given interface is small. Since Babel is designed to deal gracefully
+ with packet loss on unreliable media, sending all packets with
+ acknowledgement requests is not necessary, and not even recommended,
+ as the acknowledgements cause additional traffic and may force
+ additional Address Resolution Protocol (ARP) or Neighbour Discovery
+ exchanges.
+
+3.4. Neighbour Acquisition
+
+ Neighbour acquisition is the process by which a Babel node discovers
+ the set of neighbours heard over each of its interfaces and
+ ascertains bidirectional reachability. On unreliable media,
+ neighbour acquisition additionally provides some statistics that MAY
+ be used in link quality computation.
+
+3.4.1. Reverse Reachability Detection
+
+ Every Babel node sends periodic Hellos over each of its interfaces.
+ Each Hello TLV carries an increasing (modulo 2^16) sequence number
+ and the interval between successive periodic packets sent on this
+ particular interface.
+
+
+
+Chroboczek Experimental [Page 15]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ In addition to the periodic Hello packets, a node MAY send
+ unscheduled Hello packets, e.g., to accelerate link cost estimation
+ when a new neighbour is discovered, or when link conditions have
+ suddenly changed.
+
+ A node MAY change its Hello interval. The Hello interval MAY be
+ decreased at any time; it SHOULD NOT be increased, except immediately
+ before sending a Hello packet. (Equivalently, a node SHOULD send an
+ unscheduled Hello immediately after increasing its Hello interval.)
+
+ How to deal with received Hello TLVs and what statistics to maintain
+ are considered local implementation matters; typically, a node will
+ maintain some sort of history of recently received Hellos. A
+ possible algorithm is described in Appendix A.1.
+
+ After receiving a Hello, or determining that it has missed one, the
+ node recomputes the association's cost (Section 3.4.3) and runs the
+ route selection procedure (Section 3.6).
+
+3.4.2. Bidirectional Reachability Detection
+
+ In order to establish bidirectional reachability, every node sends
+ periodic IHU ("I Heard You") TLVs to each of its neighbours. Since
+ IHUs carry an explicit interval value, they MAY be sent less often
+ than Hellos in order to reduce the amount of routing traffic in dense
+ networks; in particular, they SHOULD be sent less often than Hellos
+ over links with little packet loss. While IHUs are conceptually
+ unicast, they SHOULD be sent to a multicast address in order to avoid
+ an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs
+ in a single packet.
+
+ In addition to the periodic IHUs, a node MAY, at any time, send an
+ unscheduled IHU packet. It MAY also, at any time, decrease its IHU
+ interval, and it MAY increase its IHU interval immediately before
+ sending an IHU.
+
+ Every IHU TLV contains two pieces of data: the link's rxcost
+ (reception cost) from the sender's perspective, used by the neighbour
+ for computing link costs (Section 3.4.3), and the interval between
+ periodic IHU packets. A node receiving an IHU updates the value of
+ the sending neighbour's txcost (transmission cost), from its
+ perspective, to the value contained in the IHU, and resets this
+ neighbour's IHU timer to a small multiple of the value received in
+ the IHU.
+
+ When a neighbour's IHU timer expires, its txcost is set to infinity.
+
+
+
+
+
+Chroboczek Experimental [Page 16]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ After updating a neighbour's txcost, the receiving node recomputes
+ the neighbour's cost (Section 3.4.3) and runs the route selection
+ procedure (Section 3.6).
+
+3.4.3. Cost Computation
+
+ A neighbourship association's link cost is computed from the values
+ maintained in the neighbour table -- namely, the statistics kept in
+ the neighbour table about the reception of Hellos, and the txcost
+ computed from received IHU packets.
+
+ For every neighbour, a Babel node computes a value known as this
+ neighbour's rxcost. This value is usually derived from the Hello
+ history, which may be combined with other data, such as statistics
+ maintained by the link layer. The rxcost is sent to a neighbour in
+ each IHU.
+
+ How the txcost and rxcost are combined in order to compute a link's
+ cost is a matter of local policy; as far as Babel's correctness is
+ concerned, only the following conditions MUST be satisfied:
+
+ o the cost is strictly positive;
+
+ o if no hellos were received recently, then the cost is infinite;
+
+ o if the txcost is infinite, then the cost is infinite.
+
+ Note that while this document does not constrain cost computation any
+ further, not all cost computation strategies will give good results.
+ We give a few examples of strategies for computing a link's cost that
+ are known to work well in practice in Appendix A.2.
+
+3.5. Routing Table Maintenance
+
+ Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
+ seqno, metric), where (prefix, plen) is the prefix for which a route
+ is being advertised, router-id is the router-id of the router
+ originating this update, seqno is a nondecreasing (modulo 2^16)
+ integer that carries the originating router seqno, and metric is the
+ announced metric.
+
+ Before being accepted, an update is checked against the feasibility
+ condition (Section 3.5.1), which ensures that the route does not
+ create a routing loop. If the feasibility condition is not
+ satisfied, the update is either ignored or treated as a retraction,
+ depending on some other conditions (Section 3.5.4). If the
+ feasibility condition is satisfied, then the update cannot possibly
+ cause a routing loop, and the update is accepted.
+
+
+
+Chroboczek Experimental [Page 17]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+3.5.1. The Feasibility Condition
+
+ The feasibility condition is applied to all received updates. The
+ feasibility condition compares the metric in the received update with
+ the metrics of the updates previously sent by the receiving node;
+ updates with finite metrics large enough to cause a loop are
+ discarded.
+
+ A feasibility distance is a pair (seqno, metric), where seqno is an
+ integer modulo 2^16 and metric is a positive integer. Feasibility
+ distances are compared lexicographically, with the first component
+ inverted: we say that a distance (seqno, metric) is strictly better
+ than a distance (seqno', metric'), written
+
+ (seqno, metric) < (seqno', metric')
+
+ when
+
+ seqno > seqno' or (seqno = seqno' and metric < metric')
+
+ where sequence numbers are compared modulo 2^16.
+
+ Given a source (p, plen, id), a node's feasibility distance for this
+ source is the minimum, according to the ordering defined above, of
+ the distances of all the finite updates ever sent by this particular
+ node for the prefix (p, plen) carrying the router-id id. Feasibility
+ distances are maintained in the source table; the exact procedure is
+ given in Section 3.7.3.
+
+ A received update is feasible when either it is a retraction (its
+ metric is FFFF hexadecimal), or the advertised distance is strictly
+ better, in the sense defined above, than the feasibility distance for
+ the corresponding source. More precisely, a route advertisement
+ carrying the quintuple (prefix, plen, router-id, seqno, metric) is
+ feasible if one of the following conditions holds:
+
+ o metric is infinite; or
+
+ o no entry exists in the source table indexed by (id, prefix, plen);
+ or
+
+ o an entry (prefix, plen, router-id, seqno', metric') exists in the
+ source table, and either
+
+ * seqno' < seqno or
+
+ * seqno = seqno' and metric < metric'.
+
+
+
+
+Chroboczek Experimental [Page 18]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Note that the feasibility condition considers the metric advertised
+ by the neighbour, not the route's metric; hence, a fluctuation in a
+ neighbour's cost cannot render a selected route unfeasible.
+
+3.5.2. Metric Computation
+
+ A route's metric is computed from the metric advertised by the
+ neighbour and the neighbour's link cost. Just like cost computation,
+ metric computation is considered a local policy matter; as far as
+ Babel is concerned, the function M(c, m) used for computing a metric
+ from a locally computed link cost and the metric advertised by a
+ neighbour MUST only satisfy the following conditions:
+
+ o if c is infinite, then M(c, m) is infinite;
+
+ o M is strictly monotonic: M(c, m) > m.
+
+ Additionally, the metric SHOULD satisfy the following condition:
+
+ o M is isotonic: if m <= m', then M(c, m) <= M(c, m').
+
+ Note that while strict monotonicity is essential to the integrity of
+ the network (persistent routing loops may appear if it is not
+ satisfied), isotonicity is not: if it is not satisfied, Babel will
+ still converge to a locally optimal routing table, but might not
+ reach a global optimum (in fact, such a global optimum may not even
+ exist).
+
+ As with cost computation, not all strategies for computing route
+ metrics will give good results. In particular, some metrics are more
+ likely than others to lead to routing instabilities (route flapping).
+ In Appendix A.3, we give a number of examples of strictly monotonic,
+ isotonic routing metrics that are known to work well in practice.
+
+3.5.3. Encoding of Updates
+
+ In a large network, the bulk of Babel traffic consists of route
+ updates; hence, some care has been given to encoding them
+ efficiently. An Update TLV itself only contains the prefix, seqno,
+ and metric, while the next hop is derived either from the network-
+ layer source address of the packet or from an explicit Next Hop TLV
+ in the same packet. The router-id is derived from a separate
+ Router-Id TLV in the same packet, which optimises the case when
+ multiple updates are sent with the same router-id.
+
+ Additionally, a prefix of the advertised prefix can be omitted in an
+ Update TLV, in which case it is copied from a previous Update TLV in
+ the same packet -- this is known as address compression [PACKETBB].
+
+
+
+Chroboczek Experimental [Page 19]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Finally, as a special optimisation for the case when a router-id
+ coincides with the interface-id part of an IPv6 address, the
+ router-id can optionally be derived from the low-order bits of the
+ advertised prefix.
+
+ The encoding of updates is described in detail in Section 4.4.
+
+3.5.4. Route Acquisition
+
+ When a Babel node receives an update (id, prefix, seqno, metric) from
+ a neighbour neigh with a link cost value equal to cost, it checks
+ whether it already has a routing table entry indexed by (neigh, id,
+ prefix).
+
+ If no such entry exists:
+
+ o if the update is unfeasible, it is ignored;
+
+ o if the metric is infinite (the update is a retraction), the update
+ is ignored;
+
+ o otherwise, a new route table entry is created, indexed by (neigh,
+ id, prefix), with seqno equal to seqno and an advertised metric
+ equal to the metric carried by the update.
+
+ If such an entry exists:
+
+ o if the entry is currently installed and the update is unfeasible,
+ then the behaviour depends on whether the router-ids of the two
+ entries match. If the router-ids are different, the update is
+ treated as though it were a retraction (i.e., as though the metric
+ were FFFF hexadecimal). If the router-ids are equal, the update
+ is ignored;
+
+ o otherwise (i.e., if either the update is feasible or the entry is
+ not currently installed), then the entry's sequence number,
+ advertised metric, metric, and router-id are updated and, unless
+ the advertised metric is infinite, the route's expiry timer is
+ reset to a small multiple of the Interval value included in the
+ update.
+
+ When a route's expiry timer triggers, the behaviour depends on
+ whether the route's metric is finite. If the metric is finite, it is
+ set to infinity and the expiry timer is reset. If the metric is
+ already infinite, the route is flushed from the route table.
+
+ After the routing table is updated, the route selection procedure
+ (Section 3.6) is run.
+
+
+
+Chroboczek Experimental [Page 20]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+3.5.5. Hold Time
+
+ When a prefix p is retracted, because all routes are unfeasible, too
+ old, or have an infinite metric, and a shorter prefix p' that covers
+ p is reachable, p' cannot in general be used for routing packets
+ destined to p without running the risk of creating a routing loop
+ (Section 2.8).
+
+ To avoid this issue, whenever a prefix is retracted, a routing table
+ entry with infinite metric is maintained as described in
+ Section 3.5.4 above, and packets destined for that prefix MUST NOT be
+ forwarded by following a route for a shorter prefix. The infinite
+ metric entry is maintained until it is superseded by a feasible
+ update; if no such update arrives within the route hold time, the
+ entry is flushed.
+
+3.6. Route Selection
+
+ Route selection is the process by which a single route for a given
+ prefix is selected to be used for forwarding packets and to be
+ re-advertised to a node's neighbours.
+
+ Babel is designed to allow flexible route selection policies. As far
+ as the protocol's correctness is concerned, the route selection
+ policy MUST only satisfy the following properties:
+
+ o a route with infinite metric (a retracted route) is never
+ selected;
+
+ o an unfeasible route is never selected.
+
+ Note, however, that Babel does not naturally guarantee the stability
+ of routing, and configuring conflicting route selection policies on
+ different routers may lead to persistent route oscillation.
+
+ Defining a good route selection policy for Babel is an open research
+ problem. Route selection can take into account multiple mutually
+ contradictory criteria; in roughly decreasing order of importance,
+ these are:
+
+ o routes with a small metric should be preferred over routes with a
+ large metric;
+
+ o switching router-ids should be avoided;
+
+ o routes through stable neighbours should be preferred over routes
+ through unstable ones;
+
+
+
+
+Chroboczek Experimental [Page 21]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ o stable routes should be preferred over unstable ones;
+
+ o switching next hops should be avoided.
+
+ A simple strategy is to choose the feasible route with the smallest
+ metric, with a small amount of hysteresis applied to avoid switching
+ router-ids.
+
+ After the route selection procedure is run, triggered updates
+ (Section 3.7.2) and requests (Section 3.8.2) are sent.
+
+3.7. Sending Updates
+
+ A Babel speaker advertises to its neighbours its set of selected
+ routes. Normally, this is done by sending one or more multicast
+ packets containing Update TLVs on all of its connected interfaces;
+ however, on link technologies where multicast is significantly more
+ expensive than unicast, a node MAY choose to send multiple copies of
+ updates in unicast packets when the number of neighbours is small.
+
+ Additionally, in order to ensure that any black-holes are reliably
+ cleared in a timely manner, a Babel node sends retractions (updates
+ with an infinite metric) for any recently retracted prefixes.
+
+ If an update is for a route injected into the Babel domain by the
+ local node (e.g., the address of a local interface, the prefix of a
+ directly attached network, or redistributed from a different routing
+ protocol), the router-id is set to the local id, the metric is set to
+ some arbitrary finite value (typically 0), and the seqno is set to
+ the local router's sequence number.
+
+ If an update is for a route learned from another Babel speaker, the
+ router-id and sequence number are copied from the routing table
+ entry, and the metric is computed as specified in Section 3.5.2.
+
+3.7.1. Periodic Updates
+
+ Every Babel speaker periodically advertises all of its selected
+ routes on all of its interfaces, including any recently retracted
+ routes. Since Babel doesn't suffer from routing loops (there is no
+ "counting to infinity") and relies heavily on triggered updates
+ (Section 3.7.2), this full dump only needs to happen infrequently.
+
+3.7.2. Triggered Updates
+
+ In addition to the periodic routing updates, a Babel speaker sends
+ unscheduled, or triggered, updates in order to inform its neighbours
+ of a significant change in the network topology.
+
+
+
+Chroboczek Experimental [Page 22]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ A change of router-id for the selected route to a given prefix may be
+ indicative of a routing loop in formation; hence, a node MUST send a
+ triggered update in a timely manner whenever it changes the selected
+ router-id for a given destination. Additionally, it SHOULD make a
+ reasonable attempt at ensuring that all neighbours receive this
+ update.
+
+ There are two strategies for ensuring that. If the number of
+ neighbours is small, then it is reasonable to send the update
+ together with an acknowledgement request; the update is resent until
+ all neighbours have acknowledged the packet, up to some number of
+ times. If the number of neighbours is large, however, requesting
+ acknowledgements from all of them might cause a non-negligible amount
+ of network traffic; in that case, it may be preferable to simply
+ repeat the update some reasonable number of times (say, 5 for
+ wireless and 2 for wired links).
+
+ A route retraction is somewhat less worrying: if the route retraction
+ doesn't reach all neighbours, a black-hole might be created, which,
+ unlike a routing loop, does not endanger the integrity of the
+ network. When a route is retracted, a node SHOULD send a triggered
+ update and SHOULD make a reasonable attempt at ensuring that all
+ neighbours receive this retraction.
+
+ Finally, a node MAY send a triggered update when the metric for a
+ given prefix changes in a significant manner, either due to a
+ received update or because a link cost has changed. A node SHOULD
+ NOT send triggered updates for other reasons, such as when there is a
+ minor fluctuation in a route's metric, when the selected next hop
+ changes, or to propagate a new sequence number (except to satisfy a
+ request, as specified in Section 3.8).
+
+3.7.3. Maintaining Feasibility Distances
+
+ Before sending an update (prefix, plen, router-id, seqno, metric)
+ with finite metric (i.e., not a route retraction), a Babel node
+ updates the feasibility distance maintained in the source table.
+ This is done as follows.
+
+ If no entry indexed by (prefix, plen, router-id) exists in the source
+ table, then one is created with value (prefix, plen, router-id,
+ seqno, metric).
+
+ If an entry (prefix, plen, router-id, seqno', metric') exists, then
+ it is updated as follows:
+
+ o if seqno > seqno', then seqno' := seqno, metric' := metric;
+
+
+
+
+Chroboczek Experimental [Page 23]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ o if seqno = seqno' and metric' > metric, then metric' := metric;
+
+ o otherwise, nothing needs to be done.
+
+ The garbage-collection timer for the modified entry is then reset.
+ Note that the garbage-collection timer is not reset when a retraction
+ is sent.
+
+3.7.4. Split Horizon
+
+ When running over a transitive, symmetric link technology, e.g., a
+ point-to-point link or a wired LAN technology such as Ethernet, a
+ Babel node SHOULD use an optimisation known as split horizon. When
+ split horizon is used on a given interface, a routing update is not
+ sent on this particular interface when the advertised route was
+ learnt from a neighbour over the same interface.
+
+ Split horizon SHOULD NOT be applied to an interface unless the
+ interface is known to be symmetric and transitive; in particular,
+ split horizon is not applicable to decentralised wireless link
+ technologies (e.g., IEEE 802.11 in ad hoc mode).
+
+3.8. Explicit Route Requests
+
+ In normal operation, a node's routing table is populated by the
+ regular and triggered updates sent by its neighbours. Under some
+ circumstances, however, a node sends explicit requests to cause a
+ resynchronisation with the source after a mobility event or to
+ prevent a route from spuriously expiring.
+
+ The Babel protocol provides two kinds of explicit requests: route
+ requests, which simply request an update for a given prefix, and
+ seqno requests, which request an update for a given prefix with a
+ specific sequence number. The former are never forwarded; the latter
+ are forwarded if they cannot be satisfied by a neighbour.
+
+3.8.1. Handling Requests
+
+ Upon receiving a request, a node either forwards the request or sends
+ an update in reply to the request, as described in the following
+ sections. If this causes an update to be sent, the update is either
+ sent to a multicast address on the interface on which the request was
+ received, or to the unicast address of the neighbour that sent the
+ update.
+
+ The exact behaviour is different for route requests and seqno
+ requests.
+
+
+
+
+Chroboczek Experimental [Page 24]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+3.8.1.1. Route Requests
+
+ When a node receives a route request for a prefix (prefix, plen), it
+ checks its route table for a selected route to this exact prefix. If
+ such a route exists, it MUST send an update; if such a route does
+ not, it MUST send a retraction for that prefix.
+
+ When a node receives a wildcard route request, it SHOULD send a full
+ routing table dump.
+
+3.8.1.2. Seqno Requests
+
+ When a node receives a seqno request for a given router-id and
+ sequence number, it checks whether its routing table contains a
+ selected entry for that prefix; if no such entry exists, or the entry
+ has infinite metric, it ignores the request.
+
+ If a selected route for the given prefix exists, and either the
+ router-ids are different or the router-ids are equal and the entry's
+ sequence number is no smaller than the requested sequence number, it
+ MUST send an update for the given prefix.
+
+ If the router-ids match but the requested seqno is larger than the
+ route entry's, the node compares the router-id against its own
+ router-id. If the router-id is its own, then it increases its
+ sequence number by 1 and sends an update. A node MUST NOT increase
+ its sequence number by more than 1 in response to a route request.
+
+ If the requested router-id is not its own, the received request's hop
+ count is 2 or more, and the node has a route (not necessarily a
+ feasible one) for the requested prefix that does not use the
+ requestor as a next hop, the node SHOULD forward the request. It
+ does so by decreasing the hop count and sending the request in a
+ unicast packet destined to a neighbour that advertises the given
+ prefix (not necessarily the selected neighbour) and that is distinct
+ from the neighbour from which the request was received.
+
+ A node SHOULD maintain a list of recently forwarded requests and
+ forward the reply in a timely manner. A node SHOULD compare every
+ incoming request against its list of recently forwarded requests and
+ avoid forwarding it if it is redundant.
+
+ Since the request-forwarding mechanism does not necessarily obey the
+ feasibility condition, it may get caught in routing loops; hence,
+ requests carry a hop count to limit the time for which they remain in
+ the network. However, since requests are only ever forwarded as
+ unicast packets, the initial hop count need not be kept particularly
+
+
+
+
+Chroboczek Experimental [Page 25]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ low, and performing an expanding horizon search is not necessary. A
+ request MUST NOT be forwarded to a multicast address, and it MUST be
+ forwarded to a single neighbour only.
+
+3.8.2. Sending Requests
+
+ A Babel node MAY send a route or seqno request at any time, to a
+ multicast or a unicast address; there is only one case when
+ originating requests is required (Section 3.8.2.1).
+
+3.8.2.1. Avoiding Starvation
+
+ When a route is retracted or expires, a Babel node usually switches
+ to another feasible route for the same prefix. It may be the case,
+ however, that no such routes are available.
+
+ A node that has lost all feasible routes to a given destination MUST
+ send a seqno request. The router-id of the request is set to the
+ router-id of the route that it has just lost, and the requested seqno
+ is the value contained in the source table, plus 1.
+
+ Such a request SHOULD be multicast over all of the node's attached
+ interfaces. Similar requests will be sent by other nodes that are
+ affected by the route's loss and will be forwarded by neighbouring
+ nodes up to the source. If the network is connected, and there is no
+ packet loss, this will result in a route being advertised with a new
+ sequence number. (Note that, due to duplicate suppression, only a
+ small number of such requests will actually reach the source.)
+
+ In order to compensate for packet loss, a node SHOULD repeat such a
+ request a small number of times if no route becomes feasible within a
+ short time. Under heavy packet loss, however, all such requests may
+ be lost; in that case, the second mechanism in the next section will
+ eventually ensure that a new seqno is received.
+
+3.8.2.2. Dealing with Unfeasible Updates
+
+ When a route's metric increases, a node might receive an unfeasible
+ update for a route that it has currently selected. As specified in
+ Section 3.5.1, the receiving node will either ignore the update or
+ retract the route.
+
+ In order to keep routes from spuriously expiring because they have
+ become unfeasible, a node SHOULD send a unicast seqno request
+ whenever it receives an unfeasible update for a route that is
+ currently selected. The requested sequence number is computed from
+ the source table as above.
+
+
+
+
+Chroboczek Experimental [Page 26]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Additionally, a node SHOULD send a unicast seqno request whenever it
+ receives an unfeasible update from a currently unselected neighbour
+ that is "good enough", i.e., that would lead to the received route
+ becoming selected were it feasible.
+
+3.8.2.3. Preventing Routes from Expiring
+
+ In normal operation, a route's expiry timer should never trigger:
+ since a route's hold time is computed from an explicit interval
+ included in Update TLVs, a new update should arrive in time to
+ prevent a route from expiring.
+
+ In the presence of packet loss, however, it may be the case that no
+ update is successfully received for an extended period of time,
+ causing a route to expire. In order to avoid such spurious expiry,
+ shortly before a selected route expires, a Babel node SHOULD send a
+ unicast route request to the neighbour that advertised this route;
+ since nodes always send retractions in response to non-wildcard route
+ requests (Section 3.8.1.1), this will usually result in either the
+ route being refreshed or a retraction being received.
+
+3.8.2.4. Acquiring New Neighbours
+
+ In order to speed up convergence after a mobility event, a node MAY
+ send a unicast wildcard request after acquiring a new neighbour.
+ Additionally, a node MAY send a small number of multicast wildcard
+ requests shortly after booting.
+
+4. Protocol Encoding
+
+ A Babel packet is sent as the body of a UDP datagram, with network-
+ layer hop count set to 1, destined to a well-known multicast address
+ or to a unicast address, over IPv4 or IPv6; in the case of IPv6,
+ these addresses are link-local. Both the source and destination UDP
+ port are set to a well-known port number. A Babel packet MUST be
+ silently ignored unless its source address is either a link-local
+ IPv6 address, or an IPv4 address belonging to the local network, and
+ its source port is the well-known Babel port. Babel packets MUST NOT
+ be sent as IPv6 Jumbograms.
+
+ In order to minimise the number of packets being sent while avoiding
+ lower-layer fragmentation, a Babel node SHOULD attempt to maximise
+ the size of the packets it sends, up to the outgoing interface's MTU
+ adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets
+ for UDP/IPv6). It MUST NOT send packets larger than the attached
+ interface's MTU (adjusted for lower-layer headers) or 512 octets,
+ whichever is larger, but not exceeding 2^16 - 1 adjusted for lower-
+
+
+
+
+Chroboczek Experimental [Page 27]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ layer headers. Every Babel speaker MUST be able to receive packets
+ that are as large as any attached interface's MTU (adjusted for
+ lower-layer headers) or 512 octets, whichever is larger.
+
+ In order to avoid global synchronisation of a Babel network and to
+ aggregate multiple TLVs into large packets, a Babel node MUST buffer
+ every TLV and delay sending a UDP packet by a small, randomly chosen
+ delay [JITTER]. In order to allow accurate computation of packet
+ loss rates, this delay MUST NOT be larger than half the advertised
+ Hello interval.
+
+4.1. Data Types
+
+4.1.1. Interval
+
+ Relative times are carried as 16-bit values specifying a number of
+ centiseconds (hundredths of a second). This allows times up to
+ roughly 11 minutes with a granularity of 10 ms, which should cover
+ all reasonable applications of Babel.
+
+4.1.2. Router-Id
+
+ A router-id is an arbitrary 8-octet value. Router-ids SHOULD be
+ assigned in modified EUI-64 format [ADDRARCH].
+
+4.1.3. Address
+
+ Since the bulk of the protocol is taken by addresses, multiple ways
+ of encoding addresses are defined. Additionally, a common subnet
+ prefix may be omitted when multiple addresses are sent in a single
+ packet -- this is known as address compression [PACKETBB].
+
+ Address encodings:
+
+ o AE 0: wildcard address. The value is 0 octets long.
+
+ o AE 1: IPv4 address. Compression is allowed. 4 octets or less.
+
+ o AE 2: IPv6 address. Compression is allowed. 16 octets or less.
+
+ o AE 3: link-local IPv6 address. The value is 8 octets long, a
+ prefix of fe80::/64 is implied.
+
+ The address family of an address is either IPv4 or IPv6; it is
+ undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3.
+
+
+
+
+
+
+Chroboczek Experimental [Page 28]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+4.1.4. Prefixes
+
+ A network prefix is encoded just like a network address, but it is
+ stored in the smallest number of octets that are enough to hold the
+ significant bits (up to the prefix length).
+
+4.2. Packet Format
+
+ A Babel packet consists of a 4-octet header, followed by a sequence
+ of TLVs.
+
+ 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 ...
+ +-+-+-+-+-+-+-+-+-+-+-+-+-
+
+ Fields :
+
+ Magic The arbitrary but carefully chosen value 42 (decimal);
+ packets with a first octet different from 42 MUST be
+ silently ignored.
+
+ Version This document specifies version 2 of the Babel protocol.
+ Packets with a second octet different from 2 MUST be
+ silently ignored.
+
+ Body length The length in octets of the body following the packet
+ header.
+
+ Body The packet body; a sequence of TLVs.
+
+ Any data following the body MUST be silently ignored.
+
+4.3. TLV Format
+
+ With the exception of Pad1, all TLVs have the following structure:
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type | Length | Body...
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+
+
+
+
+
+
+Chroboczek Experimental [Page 29]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Fields :
+
+ Type The type of the TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields. If the body is longer than the expected length of
+ a given type of TLV, any extra data MUST be silently
+ ignored.
+
+ Body The TLV body, the interpretation of which depends on the
+ type.
+
+ TLVs with an unknown type value MUST be silently ignored.
+
+4.4. Details of Specific TLVs
+
+4.4.1. Pad1
+
+ 0
+ 0 1 2 3 4 5 6 7
+ +-+-+-+-+-+-+-+-+
+ | Type = 0 |
+ +-+-+-+-+-+-+-+-+
+
+ Fields :
+
+ Type Set to 0 to indicate a Pad1 TLV.
+
+ This TLV is silently ignored on reception.
+
+4.4.2. PadN
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 1 | Length | MBZ...
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+
+ Fields :
+
+ Type Set to 1 to indicate a PadN TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ MBZ Set to 0 on transmission.
+
+ This TLV is silently ignored on reception.
+
+
+
+Chroboczek Experimental [Page 30]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+4.4.3. Acknowledgement Request
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 2 | Length | Reserved |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Nonce | Interval |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ This TLV requests that the receiver send an Acknowledgement TLV
+ within the number of centiseconds specified by the Interval field.
+
+ Fields :
+
+ Type Set to 2 to indicate an Acknowledgement Request TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ Reserved Sent as 0 and MUST be ignored on reception.
+
+ Nonce An arbitrary value that will be echoed in the receiver's
+ Acknowledgement TLV.
+
+ Interval A time interval in centiseconds after which the sender will
+ assume that this packet has been lost. This MUST NOT be 0.
+ The receiver MUST send an acknowledgement before this time
+ has elapsed (with a margin allowing for propagation time).
+
+4.4.4. Acknowledgement
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 3 | Length | Nonce |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ This TLV is sent by a node upon receiving an Acknowledgement Request.
+
+ Fields :
+
+ Type Set to 3 to indicate an Acknowledgement TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+
+
+
+
+Chroboczek Experimental [Page 31]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Nonce Set to the Nonce value of the Acknowledgement Request that
+ prompted this Acknowledgement.
+
+ Since nonce values are not globally unique, this TLV MUST be sent to
+ a unicast address.
+
+4.4.5. Hello
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 4 | Length | Reserved |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Seqno | Interval |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ This TLV is used for neighbour discovery and for determining a link's
+ reception cost.
+
+ Fields :
+
+ Type Set to 4 to indicate a Hello TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ Reserved Sent as 0 and MUST be ignored on reception.
+
+ Seqno The value of the sending node's Hello seqno for this
+ interface.
+
+ Interval An upper bound, expressed in centiseconds, on the time
+ after which the sending node will send a new Hello TLV.
+ This MUST NOT be 0.
+
+ Since there is a single seqno counter for all the Hellos sent by a
+ given node over a given interface, this TLV MUST be sent to a
+ multicast destination. In order to avoid large discontinuities in
+ link quality, multiple Hello TLVs SHOULD NOT be sent in the same
+ packet.
+
+
+
+
+
+
+
+
+
+
+
+Chroboczek Experimental [Page 32]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+4.4.6. IHU
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 5 | Length | AE | Reserved |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Rxcost | Interval |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Address...
+ +-+-+-+-+-+-+-+-+-+-+-+-
+
+ An IHU ("I Heard You") TLV is used for confirming bidirectional
+ reachability and carrying a link's transmission cost.
+
+ Fields :
+
+ Type Set to 5 to indicate an IHU TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ AE The encoding of the Address field. This should be 1 or 3
+ in most cases. As an optimisation, it MAY be 0 if the TLV
+ is sent to a unicast address, if the association is over a
+ point-to-point link, or when bidirectional reachability is
+ ascertained by means outside of the Babel protocol.
+
+ Reserved Sent as 0 and MUST be ignored on reception.
+
+ Rxcost The rxcost according to the sending node of the interface
+ whose address is specified in the Address field. The value
+ FFFF hexadecimal (infinity) indicates that this interface
+ is unreachable.
+
+ Interval An upper bound, expressed in centiseconds, on the time
+ after which the sending node will send a new IHU; this MUST
+ NOT be 0. The receiving node will use this value in order
+ to compute a hold time for this symmetric association.
+
+ Address The address of the destination node, in the format
+ specified by the AE field. Address compression is not
+ allowed.
+
+ Conceptually, an IHU is destined to a single neighbour. However, IHU
+ TLVs contain an explicit destination address, and it SHOULD be sent
+ to a multicast address, as this allows aggregation of IHUs destined
+
+
+
+
+Chroboczek Experimental [Page 33]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ to distinct neighbours into a single packet and avoids the need for
+ an ARP or Neighbour Discovery exchange when a neighbour is not being
+ used for data traffic.
+
+ IHU TLVs with an unknown value for the AE field MUST be silently
+ ignored.
+
+4.4.7. Router-Id
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 6 | Length | Reserved |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | |
+ + Router-Id +
+ | |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+ A Router-Id TLV establishes a router-id that is implied by subsequent
+ Update TLVs.
+
+ Fields :
+
+ Type Set to 6 to indicate a Router-Id TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ Reserved Sent as 0 and MUST be ignored on reception.
+
+ Router-Id The router-id for routes advertised in subsequent Update
+ TLVs
+
+4.4.8. Next Hop
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 7 | Length | AE | Reserved |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Next hop...
+ +-+-+-+-+-+-+-+-+-+-+-+-
+
+ A Next Hop TLV establishes a next-hop address for a given address
+ family (IPv4 or IPv6) that is implied by subsequent Update TLVs.
+
+
+
+
+
+Chroboczek Experimental [Page 34]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Fields :
+
+ Type Set to 7 to indicate a Next Hop TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ AE The encoding of the Address field. This SHOULD be 1 or 3
+ and MUST NOT be 0.
+
+ Reserved Sent as 0 and MUST be ignored on reception.
+
+ Next hop The next-hop address advertised by subsequent Update TLVs,
+ for this address family.
+
+ When the address family matches the network-layer protocol that this
+ packet is transported over, a Next Hop TLV is not needed: in that
+ case, the next hop is taken to be the source address of the packet.
+
+ Next Hop TLVs with an unknown value for the AE field MUST be silently
+ ignored.
+
+4.4.9. Update
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 8 | Length | AE | Flags |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Plen | Omitted | Interval |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Seqno | Metric |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Prefix...
+ +-+-+-+-+-+-+-+-+-+-+-+-
+
+ An Update TLV advertises or retracts a route. As an optimisation,
+ this can also have the side effect of establishing a new implied
+ router-id and a new default prefix.
+
+ Fields :
+
+ Type Set to 8 to indicate an Update TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ AE The encoding of the Prefix field.
+
+
+
+Chroboczek Experimental [Page 35]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Flags The individual bits of this field specify special handling
+ of this TLV (see below). Every node MUST be able to
+ interpret the flags with values 80 and 40 hexadecimal;
+ unknown flags MUST be silently ignored.
+
+ Plen The length of the advertised prefix.
+
+ Omitted The number of octets that have been omitted at the
+ beginning of the advertised prefix and that should be taken
+ from a preceding Update TLV with the flag with value 80
+ hexadecimal set.
+
+ Interval An upper bound, expressed in centiseconds, on the time
+ after which the sending node will send a new update for
+ this prefix. This MUST NOT be 0 and SHOULD NOT be less
+ than 10. The receiving node will use this value to compute
+ a hold time for this routing table entry. The value FFFF
+ hexadecimal (infinity) expresses that this announcement
+ will not be repeated unless a request is received
+ (Section 3.8.2.3).
+
+ Seqno The originator's sequence number for this update.
+
+ Metric The sender's metric for this route. The value FFFF
+ hexadecimal (infinity) means that this is a route
+ retraction.
+
+ Prefix The prefix being advertised. This field's size is (Plen/8
+ - Omitted) rounded upwards.
+
+ The Flags field is interpreted as follows:
+
+ o if the bit with value 80 hexadecimal is set, then this Update
+ establishes a new default prefix for subsequent Update TLVs with a
+ matching address family within the same packet;
+
+ o if the bit with value 40 hexadecimal is set, then the low-order 8
+ octets of the advertised prefix establish a new default router-id
+ for this TLV and subsequent Update TLVs in the same packet.
+
+ The prefix being advertised by an Update TLV is computed as follows:
+
+ o the first Omitted octets of the prefix are taken from the previous
+ Update TLV with flag 80 hexadecimal set and the same address
+ family;
+
+ o the next (Plen/8 - Omitted) (rounded upwards) octets are taken
+ from the Prefix field;
+
+
+
+Chroboczek Experimental [Page 36]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ o the remaining octets are set to 0.
+
+ If the Metric field is finite, the router-id of the originating node
+ for this announcement is taken from the low-order 8 octets of the
+ prefix advertised by this Update if the bit with value 40 hexadecimal
+ is set in the Flags field. Otherwise, it is taken either from the
+ preceding Router-Id packet, or the preceding Update packet with flag
+ 40 hexadecimal set, whichever comes last.
+
+ The next-hop address for this update is taken from the last preceding
+ Next Hop TLV with a matching address family in the same packet; if no
+ such TLV exists, it is taken from the network-layer source address of
+ this packet.
+
+ If the metric field is FFFF hexadecimal, this TLV specifies a
+ retraction. In that case, the current router-id and the Seqno are
+ not used. AE MAY then be 0, in which case this Update retracts all
+ of the routes previously advertised on this interface.
+
+ Update TLVs with an unknown value for the AE field MUST be silently
+ ignored.
+
+4.4.10. Route Request
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 9 | Length | AE | Plen |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Prefix...
+ +-+-+-+-+-+-+-+-+-+-+-+-
+
+ A Route Request TLV prompts the receiver to send an update for a
+ given prefix, or a full routing table dump.
+
+ Fields :
+
+ Type Set to 9 to indicate a Route Request TLV.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ AE The encoding of the Prefix field. The value 0 specifies
+ that this is a request for a full routing table dump (a
+ wildcard request).
+
+ Plen The length of the requested prefix.
+
+
+
+
+Chroboczek Experimental [Page 37]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Prefix The prefix being requested. This field's size is Plen/8
+ rounded upwards.
+
+ A Request TLV prompts the receiving node to send an update message
+ for the prefix specified by the AE, Plen, and Prefix fields, or a
+ full dump of its routing table if AE is 0 (in which case Plen MUST be
+ 0, and Prefix is of length 0). A Request may be sent to a unicast
+ address if it is destined to a single node, or to a multicast address
+ if the request is destined to all of the neighbours of the sending
+ interface.
+
+4.4.11. Seqno Request
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type = 10 | Length | AE | Plen |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Seqno | Hop Count | Reserved |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | |
+ + Router-Id +
+ | |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Prefix...
+ +-+-+-+-+-+-+-+-+-+-+
+
+ A Seqno Request TLV prompts the receiver to send an Update for a
+ given prefix with a given sequence number, or to forward the request
+ further if it cannot be satisfied locally.
+
+ Fields :
+
+ Type Set to 10 to indicate a Seqno Request message.
+
+ Length The length of the body, exclusive of the Type and Length
+ fields.
+
+ AE The encoding of the Prefix field. This MUST NOT be 0.
+
+ Plen The length of the requested prefix.
+
+ Seqno The sequence number that is being requested.
+
+ Hop Count The maximum number of times that this TLV may be forwarded,
+ plus 1. This MUST NOT be 0.
+
+
+
+
+
+Chroboczek Experimental [Page 38]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ Prefix The prefix being requested. This field's size is Plen/8
+ rounded upwards.
+
+ A Seqno Request TLV prompts the receiving node to send an Update for
+ the prefix specified by the AE, Plen, and Prefix fields, with either
+ a router-id different from what is specified by the Router-Id field,
+ or a Seqno no less than what is specified by the Seqno field. If
+ this request cannot be satisfied locally, then it is forwarded
+ according to the rules set out in Section 3.8.1.2.
+
+ While a Seqno Request MAY be sent to a multicast address, it MUST NOT
+ be forwarded to a multicast address and MUST NOT be forwarded to more
+ than one neighbour. A request MUST NOT be forwarded if its Hop Count
+ field is 1.
+
+5. IANA Considerations
+
+ IANA has registered the UDP port number 6697, called "babel", for use
+ by the Babel protocol.
+
+ IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and
+ the IPv4 multicast group 224.0.0.111 for use by the Babel protocol.
+
+6. Security Considerations
+
+ As defined in this document, Babel is a completely insecure protocol.
+ Any attacker can attract data traffic by advertising routes with a
+ low metric. This particular issue can be solved either by lower-
+ layer security mechanisms (e.g., IPsec or link-layer security), or by
+ appending a cryptographic key to Babel packets; the provision of
+ ignoring any data contained within a Babel packet beyond the body
+ length declared by the header is designed for just such a purpose.
+
+ The information that a Babel node announces to the whole routing
+ domain is often sufficient to determine a mobile node's physical
+ location with reasonable precision. The privacy issues that this
+ causes can be mitigated somewhat by using randomly chosen router-ids
+ and randomly chosen IP addresses, and changing them periodically.
+
+ When carried over IPv6, Babel packets are ignored unless they are
+ sent from a link-local IPv6 address; since routers don't forward
+ link-local IPv6 packets, this provides protection against spoofed
+ Babel packets being sent from the global Internet. No such natural
+ protection exists when Babel packets are carried over IPv4.
+
+
+
+
+
+
+
+Chroboczek Experimental [Page 39]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+7. References
+
+7.1. Normative References
+
+ [ADDRARCH] Hinden, R. and S. Deering, "IP Version 6 Addressing
+ Architecture", RFC 4291, February 2006.
+
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", BCP 14, RFC 2119, March 1997.
+
+7.2. Informative References
+
+ [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-
+ Sequenced Distance-Vector Routing (DSDV) for Mobile
+ Computers", ACM SIGCOMM'94 Conference on Communications
+ Architectures, Protocols and Applications 234-244, 1994.
+
+ [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using
+ Diffusing Computations", IEEE/ACM Transactions on
+ Networking 1:1, February 1993.
+
+ [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle,
+ "EIGRP -- a Fast Routing Protocol Based on Distance
+ Vectors", Proc. Interop 94, 1994.
+
+ [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A
+ high-throughput path metric for multi-hop wireless
+ networks", Proc. MobiCom 2003, 2003.
+
+ [IS-IS] "Information technology -- Telecommunications and
+ information exchange between systems -- Intermediate
+ System to Intermediate System intra-domain routeing
+ information exchange protocol for use in conjunction with
+ the protocol for providing the connectionless-mode
+ network service (ISO 8473)", ISO/IEC 10589:2002.
+
+ [JITTER] Floyd, S. and V. Jacobson, "The synchronization of
+ periodic routing messages", IEEE/ACM Transactions on
+ Networking 2, 2, 122-136, April 1994.
+
+ [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
+
+ [PACKETBB] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
+ "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
+ Format", RFC 5444, February 2009.
+
+ [RIP] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
+ November 1998.
+
+
+
+Chroboczek Experimental [Page 40]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+Appendix A. Cost and Metric Computation
+
+ The strategy for computing link costs and route metrics is a local
+ matter; Babel itself only requires that it comply with the conditions
+ given in Sections 3.4.3 and 3.5.2. Different nodes MAY use different
+ strategies in a single network and MAY use different strategies on
+ different interface types. This section gives a few examples of such
+ strategies.
+
+ The sample implementation of Babel maintains statistics about the
+ last 16 received Hello TLVs (Appendix A.1), computes costs by using
+ the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX
+ [ETX] on wireless links. It uses an additive algebra for metric
+ computation (Appendix A.3.1).
+
+A.1. Maintaining Hello History
+
+ For each neighbour, the sample implementation of Babel maintains a
+ Hello history and an expected sequence number. The Hello history is
+ a vector of 16 bits, where a 1 value represents a received Hello, and
+ a 0 value a missed Hello. The expected sequence number, written ne,
+ is the sequence number that is expected to be carried by the next
+ received hello from this neighbour.
+
+ Whenever it receives a Hello packet from a neighbour, a node compares
+ the received sequence number nr with its expected sequence number ne.
+ Depending on the outcome of this comparison, one of the following
+ actions is taken:
+
+ o if the two differ by more than 16 (modulo 2^16), then the sending
+ node has probably rebooted and lost its sequence number; the
+ associated neighbour table entry is flushed;
+
+ o otherwise, if the received nr is smaller (modulo 2^16) than the
+ expected sequence number ne, then the sending node has increased
+ its Hello interval without our noticing; the receiving node
+ removes the last (ne - nr) entries from this neighbour's Hello
+ history (we "undo history");
+
+ o otherwise, if nr is larger (modulo 2^16) than ne, then the sending
+ node has decreased its Hello interval, and some Hellos were lost;
+ the receiving node adds (nr - ne) 0 bits to the Hello history (we
+ "fast-forward").
+
+
+
+
+
+
+
+
+Chroboczek Experimental [Page 41]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ The receiving node then appends a 1 bit to the neighbour's Hello
+ history, resets the neighbour's Hello timer, and sets ne to (nr + 1).
+ It then resets the neighbour's Hello timer to 1.5 times the value
+ advertised in the received Hello (the extra margin allows for the
+ delay due to jitter).
+
+ Whenever the Hello timer associated to a neighbour expires, the local
+ node adds a 0 bit to this neighbour's Hello history, and increments
+ the expected Hello number. If the Hello history is empty (it
+ contains 0 bits only), the neighbour entry is flushed; otherwise, it
+ resets the neighbour's Hello timer to the value advertised in the
+ last Hello received from this neighbour (no extra margin is necessary
+ in this case).
+
+A.2. Cost Computation
+
+A.2.1. k-out-of-j
+
+ K-out-of-j link sensing is suitable for wired links that are either
+ up, in which case they only occasionally drop a packet, or down, in
+ which case they drop all packets.
+
+ The k-out-of-j strategy is parameterised by two small integers k and
+ j, such that 0 < k <= j, and the nominal link cost, a constant K >=
+ 1. A node keeps a history of the last j hellos; if k or more of
+ those have been correctly received, the link is assumed to be up, and
+ the rxcost is set to K; otherwise, the link is assumed to be down,
+ and the rxcost is set to infinity.
+
+ The cost of such a link is defined as
+
+ o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;
+
+ o cost = txcost otherwise.
+
+A.2.2. ETX
+
+ The Estimated Transmission Cost metric [ETX] estimates the number of
+ times that a unicast frame will be retransmitted by the IEEE 802.11
+ MAC, assuming infinite persistence.
+
+ A node uses a neighbour's Hello history to compute an estimate,
+ written beta, of the probability that a Hello TLV is successfully
+ received. The rxcost is defined as 256/beta.
+
+ Let alpha be MIN(1, 256/txcost), an estimate of the probability of
+ successfully sending a Hello TLV. The cost is then computed by
+
+
+
+
+Chroboczek Experimental [Page 42]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ cost = 256/(alpha * beta)
+
+ or, equivalently,
+
+ cost = (MAX(txcost, 256) * rxcost) / 256.
+
+A.3. Metric Computation
+
+A.3.1. Additive Metrics
+
+ The simplest approach for obtaining a monotonic, isotonic metric is
+ to define the metric of a route as the sum of the costs of the
+ component links. More formally, if a neighbour advertises a route
+ with metric m over a link with cost c, then the resulting route has
+ metric M(c, m) = c + m.
+
+ A multiplicative metric can be converted to an additive one by taking
+ the logarithm (in some suitable base) of the link costs.
+
+A.3.2. External Sources of Willingness
+
+ A node may want to vary its willingness to forward packets by taking
+ into account information that is external to the Babel protocol, such
+ as the monetary cost of a link, the node's battery status, CPU load,
+ etc. This can be done by adding to every route's metric a value k
+ that depends on the external data. For example, if a battery-powered
+ node receives an update with metric m over a link with cost c, it
+ might compute a metric M(c, m) = k + c + m, where k depends on the
+ battery status.
+
+ In order to preserve strict monotonicity (Section 3.5.2), the value k
+ must be greater than -c.
+
+Appendix B. Constants
+
+ The choice of time constants is a trade-off between fast detection of
+ mobility events and protocol overhead. Two implementations of Babel
+ with different time constants will interoperate, although the
+ resulting convergence time will most likely be dictated by the
+ slowest of the two implementations.
+
+ Experience with the sample implementation of Babel indicates that the
+ Hello interval is the most important time constant: a mobility event
+ is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance
+ on triggered updates and explicit requests, the Update interval only
+ has an effect on the time it takes for accurate metrics to be
+ propagated after variations in link costs too small to trigger an
+ unscheduled update.
+
+
+
+Chroboczek Experimental [Page 43]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ At the time of writing, the sample implementation of Babel uses the
+ following default values:
+
+ Hello Interval: 4 seconds on wireless links, 20 seconds on wired
+ links.
+
+ IHU Interval: the advertised IHU interval is always 3 times the
+ Hello interval. IHUs are actually sent with each Hello on lossy
+ links (as determined from the Hello history), but only with every
+ third Hello on lossless links.
+
+ Update Interval: 4 times the Hello interval.
+
+ IHU Hold Time: 3.5 times the advertised IHU interval.
+
+ Route Expiry Time: 3.5 times the advertised update interval.
+
+ Source GC time: 3 minutes.
+
+ The amount of jitter applied to a packet depends on whether it
+ contains any urgent TLVs or not. Urgent triggered updates and urgent
+ requests are delayed by no more than 200 ms; other TLVs are delayed
+ by no more than one-half the Hello interval.
+
+Appendix C. Simplified Implementations
+
+ Babel is a fairly economic protocol. Route updates take between 12
+ and 40 octets per destination, depending on how successful
+ compression is; in a double-stack mesh network, an average of less
+ than 24 octets is typical. The route table occupies about 35 octets
+ per IPv6 entry. To put these values into perspective, a single full-
+ size Ethernet frame can carry some 65 route updates, and a megabyte
+ of memory can contain a 20000-entry routing table and the associated
+ source table.
+
+ Babel is also a reasonably simple protocol. The sample
+ implementation consists of less than 8000 lines of C code, and it
+ compiles to less than 60 kB of text on a 32-bit CISC architecture.
+
+ Nonetheless, in some very constrained environments, such as PDAs,
+ microwave ovens, or abacuses, it may be desirable to have subset
+ implementations of the protocol.
+
+ A parasitic implementation is one that uses a Babel network for
+ routing its packets but does not announce any of the routes that it
+ has learnt from its neighbours. (This is slightly more than a
+ passive implementation, which doesn't even announce routes to
+ itself.) It may either maintain a full routing table or simply
+
+
+
+Chroboczek Experimental [Page 44]
+
+RFC 6126 The Babel Routing Protocol April 2011
+
+
+ select a gateway amongst any one of its neighbours that announces a
+ default route. Since a parasitic implementation never forwards
+ packets, it cannot possibly participate in a routing loop; hence, it
+ need not evaluate the feasibility condition and need not maintain a
+ source table.
+
+ A parasitic implementation MUST answer acknowledgement requests and
+ MUST participate in the Hello/IHU protocol. Finally, it MUST be able
+ to reply to seqno requests for routes that it announces and SHOULD be
+ able to reply to route requests.
+
+Appendix D. Software Availability
+
+ The sample implementation of Babel is available from
+ <http://www.pps.jussieu.fr/~jch/software/babel/>.
+
+Author's Address
+
+ Juliusz Chroboczek
+ PPS, University of Paris 7
+ Case 7014
+ 75205 Paris Cedex 13,
+ France
+
+ EMail: jch@pps.jussieu.fr
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Chroboczek Experimental [Page 45]
+