draft-ietf-babel-rfc6126bis-12.txt   draft-ietf-babel-rfc6126bis-13.txt 
Network Working Group J. Chroboczek Network Working Group J. Chroboczek
Internet-Draft IRIF, University of Paris-Diderot Internet-Draft IRIF, University of Paris-Diderot
Obsoletes: 6126,7557 (if approved) D. Schinazi Obsoletes: 6126,7557 (if approved) D. Schinazi
Intended status: Standards Track Google LLC Intended status: Standards Track Google LLC
Expires: February 8, 2020 August 7, 2019 Expires: February 11, 2020 August 10, 2019
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-12 draft-ietf-babel-rfc6126bis-13
Abstract Abstract
Babel is a loop-avoiding distance-vector routing protocol that is Babel is a loop-avoiding distance-vector routing protocol that is
robust and efficient both in ordinary wired networks and in wireless robust and efficient both in ordinary wired networks and in wireless
mesh networks. This document describes the Babel routing protocol, mesh networks. This document describes the Babel routing protocol,
and obsoletes RFCs 6126 and 7557. and obsoletes RFCs 6126 and 7557.
Status of This Memo Status of This Memo
skipping to change at page 1, line 34 skipping to change at page 1, line 34
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on February 8, 2020. This Internet-Draft will expire on February 11, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 24 skipping to change at page 2, line 24
2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6
2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 7 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 7
2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10
2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11
3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12
3.1. Message Transmission and Reception . . . . . . . . . . . 12 3.1. Message Transmission and Reception . . . . . . . . . . . 12
3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 13 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 13
3.3. Acknowledgments and acknowledgment requests . . . . . . . 17 3.3. Acknowledgments and acknowledgment requests . . . . . . . 17
3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 18
3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 20 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 20
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25
3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28 3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 32 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 32
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34
4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 35 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 34
4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 35 4.5. Parser state and encoding of updates . . . . . . . . . . 35
4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 36 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 36
4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 47 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 47
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48
6. Security Considerations . . . . . . . . . . . . . . . . . . . 49 6. Security Considerations . . . . . . . . . . . . . . . . . . . 51
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 49 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 52
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 50 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 52
8.1. Normative References . . . . . . . . . . . . . . . . . . 50 8.1. Normative References . . . . . . . . . . . . . . . . . . 52
8.2. Informative References . . . . . . . . . . . . . . . . . 50 8.2. Informative References . . . . . . . . . . . . . . . . . 53
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 51 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 54
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 51 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 55
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 52 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 56
A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 54 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 57
Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 54 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 58
Appendix C. Considerations for protocol extensions . . . . . . . 55 Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 59
Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 57 Appendix D. Considerations for protocol extensions . . . . . . . 60
Appendix E. Software Availability . . . . . . . . . . . . . . . 58 Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 61
Appendix F. Changes from previous versions . . . . . . . . . . . 58 Appendix F. Changes from previous versions . . . . . . . . . . . 62
F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 58 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 62
F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 58 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 62
F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 58 F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 63
F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 59 F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 63
F.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 59 F.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 64
F.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 60 F.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 64
F.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 60 F.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 64
F.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 60 F.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 65
F.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 60 F.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 65
F.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 60 F.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 65
F.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 60 F.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 65
F.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 61 F.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 65
F.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 61 F.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 65
F.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 61 F.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 65
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 61 F.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 65
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 66
1. Introduction 1. Introduction
Babel is a loop-avoiding distance-vector routing protocol that is Babel is a loop-avoiding distance-vector routing protocol that is
designed to be robust and efficient both in networks using prefix- designed to be robust and efficient both in networks using prefix-
based routing and in networks using flat routing ("mesh networks"), based routing and in networks using flat routing ("mesh networks"),
and both in relatively stable wired networks and in highly dynamic and both in relatively stable wired networks and in highly dynamic
wireless networks. wireless networks. This document describes the Babel routing
protocol, and obsoletes [RFC6126] and [RFC7557].
1.1. Features 1.1. Features
The main property that makes Babel suitable for unstable networks is The main property that makes Babel suitable for unstable networks is
that, unlike naive distance-vector routing protocols [RIP], it that, unlike naive distance-vector routing protocols [RIP], it
strongly limits the frequency and duration of routing pathologies strongly limits the frequency and duration of routing pathologies
such as routing loops and black-holes during reconvergence. Even such as routing loops and black-holes during reconvergence. Even
after a mobility event is detected, a Babel network usually remains after a mobility event is detected, a Babel network usually remains
loop-free. Babel then quickly reconverges to a configuration that loop-free. Babel then quickly reconverges to a configuration that
preserves the loop-freedom and connectedness of the network, but is preserves the loop-freedom and connectedness of the network, but is
skipping to change at page 4, line 27 skipping to change at page 4, line 28
are configured with different parameters. For example, a mobile node are configured with different parameters. For example, a mobile node
that is low on battery may choose to use larger time constants (hello 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 and update intervals, etc.) than a node that has access to wall
power. Conversely, a node that detects high levels of mobility may power. Conversely, a node that detects high levels of mobility may
choose to use smaller time constants. The ability to build such choose to use smaller time constants. The ability to build such
heterogeneous networks makes Babel particularly adapted to the heterogeneous networks makes Babel particularly adapted to the
unmanaged and wireless environment. unmanaged and wireless environment.
Finally, Babel is a hybrid routing protocol, in the sense that it can Finally, Babel is a hybrid routing protocol, in the sense that it can
carry routes for multiple network-layer protocols (IPv4 and IPv6), carry routes for multiple network-layer protocols (IPv4 and IPv6),
whichever protocol the Babel packets are themselves being carried regardless of which protocol the Babel packets are themselves being
over. carried over.
1.2. Limitations 1.2. Limitations
Babel has two limitations that make it unsuitable for use in some Babel has two limitations that make it unsuitable for use in some
environments. First, Babel relies on periodic routing table updates environments. First, Babel relies on periodic routing table updates
rather than using a reliable transport; hence, in large, stable rather than using a reliable transport; hence, in large, stable
networks it generates more traffic than protocols that only send networks it generates more traffic than protocols that only send
updates when the network topology changes. In such networks, updates when the network topology changes. In such networks,
protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced
Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more
suitable. suitable.
Second, unless the optional algorithm described in Section 3.5.5 is Second, unless the optional algorithm described in Section 3.5.4 is
implemented, Babel does impose a hold time when a prefix is implemented, Babel does impose a hold time when a prefix is
retracted. While this hold time does not apply to the exact prefix retracted. While this hold time does not apply to the exact prefix
being retracted, and hence does not prevent fast reconvergence should being retracted, and hence does not prevent fast reconvergence should
it become available again, it does apply to any shorter prefix that it become available again, it does apply to any shorter prefix that
covers it. This may make those implementations of Babel that do not covers it. This may make those implementations of Babel that do not
implement the optional algorithm described in Section 3.5.5 implement the optional algorithm described in Section 3.5.4
unsuitable for use in networks that implement automatic prefix unsuitable for use in networks that implement automatic prefix
aggregation. aggregation.
1.3. Specification of Requirements 1.3. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP "OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
2. Conceptual Description of the Protocol 2. Conceptual Description of the Protocol
Babel is a loop-avoiding distance vector protocol: it is based on the Babel is a loop-avoiding distance vector protocol: it is based on the
Bellman-Ford protocol, just like the venerable RIP [RIP], but Bellman-Ford algorithm, just like the venerable RIP [RIP], but
includes a number of refinements that either prevent loop formation includes a number of refinements that either prevent loop formation
altogether, or ensure that a loop disappears in a timely manner and altogether, or ensure that a loop disappears in a timely manner and
doesn't form again. doesn't form again.
Conceptually, Bellman-Ford is executed in parallel for every source Conceptually, Bellman-Ford is executed in parallel for every source
of routing information (destination of data traffic). In the of routing information (destination of data traffic). In the
following discussion, we fix a source S; the reader will recall that following discussion, we fix a source S; the reader will recall that
the same algorithm is executed for all sources. the same algorithm is executed for all sources.
2.1. Costs, Metrics and Neighbourship 2.1. Costs, Metrics and Neighbourship
skipping to change at page 7, line 33 skipping to change at page 7, line 33
Many different feasibility conditions are possible. For example, BGP Many different feasibility conditions are possible. For example, BGP
can be modelled as being a distance-vector protocol with a (rather can be modelled as being a distance-vector protocol with a (rather
drastic) feasibility condition: a routing update is only accepted drastic) feasibility condition: a routing update is only accepted
when the receiving node's AS number is not included in the update's 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 AS-Path attribute (note that BGP's feasibility condition does not
ensure the absence of transient "micro-loops" during reconvergence). ensure the absence of transient "micro-loops" during reconvergence).
Another simple feasibility condition, used in the Destination- Another simple feasibility condition, used in the Destination-
Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the
Ad hoc On-Demand Distance Vector (AODV) protocol, stems from the Ad hoc On-Demand Distance Vector (AODV) protocol [RFC3561], stems
following observation: a routing loop can only arise after a router from the following observation: a routing loop can only arise after a
has switched to a route with a larger metric than the route that it router has switched to a route with a larger metric than the route
had previously selected. Hence, one could decide that a route is that it had previously selected. Hence, one may define that a route
feasible only when its metric at the local node would be no larger is feasible when its metric at the local node would be no larger than
than the metric of the currently selected route, i.e., an the metric of the currently selected route, i.e., an announcement
announcement carrying a metric D(B) is accepted by A when C(A, B) + carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A).
D(B) <= D(A). If all routers obey this constraint, then the metric If all routers obey this constraint, then the metric at every router
at every router is nonincreasing, and the following invariant is is nonincreasing, and the following invariant is always preserved: if
always preserved: if A has selected B as its successor, then D(B) < A has selected B as its next hop, then D(B) < D(A), which implies
D(A), which implies that the forwarding graph is loop-free. that the forwarding graph is loop-free.
Babel uses a slightly more refined feasibility condition, derived Babel uses a slightly more refined feasibility condition, derived
from EIGRP [DUAL]. Given a router A, define the feasibility distance from EIGRP [DUAL]. Given a router A, define the feasibility distance
of A, written FD(A), as the smallest metric that A has ever 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 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 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) < strictly smaller than A's feasibility distance, i.e., when D(B) <
FD(A). FD(A).
It is easy to see that this latter condition is no more restrictive It is easy to see that this latter condition is no more restrictive
skipping to change at page 12, line 14 skipping to change at page 12, line 14
1 1 1 1
::/0 -- A --- B --- C ::/0 -- A --- B --- C
Suppose that node C fails. If B forwards packets destined to C by Suppose that node C fails. If B forwards packets destined to C by
following the default route, a routing loop will form, and persist following the default route, a routing loop will form, and persist
until A learns of B's retraction of the direct route to C. B avoids until A learns of B's retraction of the direct route to C. B avoids
this pitfall by installing an "unreachable" route after a route is this pitfall by installing an "unreachable" route after a route is
retracted; this route is maintained until it can be guaranteed that retracted; this route is maintained until it can be guaranteed that
the former route has been retracted by all of B's neighbours the former route has been retracted by all of B's neighbours
(Section 3.5.5). (Section 3.5.4).
3. Protocol Operation 3. Protocol Operation
Every Babel speaker is assigned a router-id, which is an arbitrary Every Babel speaker is assigned a router-id, which is an arbitrary
string of 8 octets that is assumed unique across the routing domain. string of 8 octets that is assumed unique across the routing domain.
For example, router-ids could be assigned randomly, or they could be For example, router-ids could be assigned randomly, or they could be
derived from a link-layer address. (The protocol encoding is derived from a link-layer address. (The protocol encoding is
slightly more compact when router-ids are assigned in the same manner slightly more compact when router-ids are assigned in the same manner
as the IPv6 layer assigns host IDs, see the definition of the "R" as the IPv6 layer assigns host IDs, see the definition of the "R"
flag in Section 4.6.9.) flag in Section 4.6.9.)
skipping to change at page 13, line 6 skipping to change at page 13, line 6
and unicast packets to its neighbours. and unicast packets to its neighbours.
With the exception of acknowledgments, all Babel TLVs can be sent to With the exception of acknowledgments, all Babel TLVs can be sent to
either unicast or multicast addresses, and their semantics does not either unicast or multicast addresses, and their semantics does not
depend on whether the destination is a unicast or a multicast depend on whether the destination is a unicast or a multicast
address. Hence, a Babel speaker does not need to determine the address. Hence, a Babel speaker does not need to determine the
destination address of a packet that it receives in order to destination address of a packet that it receives in order to
interpret it. interpret it.
A moderate amount of jitter may be applied to packets sent by a Babel A moderate amount of jitter may be applied to packets sent by a Babel
speaker: outgoing TLVs are buffered and SHOULD be sent with a small speaker: outgoing TLVs are buffered and SHOULD be sent with a random
random delay. This is done for two purposes: it avoids delay. This is done for two purposes: it avoids synchronisation of
synchronisation of multiple Babel speakers across a network [JITTER], multiple Babel speakers across a network [JITTER], and it allows for
and it allows for the aggregation of multiple TLVs into a single the aggregation of multiple TLVs into a single packet.
packet.
The exact delay and amount of jitter applied to a packet depends on The maximum amount of delay a TLV can be subjected to depends on the
whether it contains any urgent TLVs. Acknowledgment TLVs MUST be TLV. When the protocol description specifies that a TLV is urgent
sent before the deadline specified in the corresponding request. The (as in Section 3.7.2 and Section 3.8.2), then the TLV MUST be sent
particular class of updates specified in Section 3.7.2 MUST be sent within a short time known as the urgent timeout (see Appendix B for
in a timely manner. The particular class of request and update TLVs recommended values). When the TLV is governed by a timeout
specified in Section 3.8.2 SHOULD be sent in a timely manner. explicitly included in a previous TLV, (such as in the case of
Acknowledgements Section 4.6.4), Updates (Section 3.7 and IHUs
(Section 3.4.2), then the TLV MUST be sent early enough to meet the
explicit deadline (with a small margin to allow for propagation
delays). In all other cases, the TLV SHOULD be sent out within one-
half of the Multicast Hello interval.
In order to avoid packet drops (either at the sender or at the
receiver), a delay SHOULD be introduced between successive packets
sent out on the same interface, within the constraints of the
previous paragraph.
3.2. Data Structures 3.2. Data Structures
In this section, we give a description of the data structures that In this section, we give a description of the data structures that
every Babel speaker maintains. This description is conceptual: a every Babel speaker maintains. This description is conceptual: a
Babel speaker may use different data structures as long as the Babel speaker may use different data structures as long as the
resulting protocol is the same as the one described in this document. resulting protocol is the same as the one described in this document.
For example, rather than maintaining a single table containing both For example, rather than maintaining a single table containing both
selected and unselected (fallback) routes, as described in selected and unselected (fallback) routes, as described in
Section 3.2.6 below, an actual implementation would probably use two Section 3.2.6 below, an actual implementation would probably use two
tables, one with selected routes and one with fallback routes. tables, one with selected routes and one with fallback routes.
3.2.1. Sequence number arithmetic 3.2.1. Sequence number arithmetic
Sequence numbers (seqnos) appear in a number of Babel data Sequence numbers (seqnos) appear in a number of Babel data
structures, and they are interpreted as integers modulo 2^16. For structures, and they are interpreted as integers modulo 2^16. For
the purposes of this document, arithmetic on sequence numbers is the purposes of this document, arithmetic on sequence numbers is
defined as follows. defined as follows.
Given a seqno s and an integer n, the sum of s and n is defined by Given a seqno s and a non-negative integer n, the sum of s and n is
defined by
s + n (modulo 2^16) = (s + n) MOD 2^16 s + n (modulo 2^16) = (s + n) MOD 2^16
or, equivalently, or, equivalently,
s + n (modulo 2^16) = (s + n) AND 65535 s + n (modulo 2^16) = (s + n) AND 65535
where MOD is the modulo operation yielding a non-negative integer and where MOD is the modulo operation yielding a non-negative integer and
AND is the bitwise conjunction operation. AND is the bitwise conjunction operation.
Given two sequence numbers s and s', the relation s is less than s' Given two sequence numbers s and s', the relation s is less than s'
(s < s') is defined by (s < s') is defined by
s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768
skipping to change at page 14, line 30 skipping to change at page 14, line 39
3.2.3. The Interface Table 3.2.3. The Interface Table
The interface table contains the list of interfaces on which the node The interface table contains the list of interfaces on which the node
speaks the Babel protocol. Every interface table entry contains the speaks the Babel protocol. Every interface table entry contains the
interface's outgoing Multicast Hello seqno, a 16-bit integer that is interface's outgoing Multicast Hello seqno, a 16-bit integer that is
sent with each Multicast Hello TLV on this interface and is sent with each Multicast Hello TLV on this interface and is
incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note
that an interface's Multicast Hello seqno is unrelated to the node's that an interface's Multicast Hello seqno is unrelated to the node's
seqno.) seqno.)
There are two timers associated with each interface table entry -- There are two timers associated with each interface table entry. The
the multicast hello timer, which governs the sending of scheduled periodic Multicast Hello timer governs the sending of scheduled
Multicast Hello and IHU packets, and the update timer, which governs Multicast Hello and IHU packets (Section 3.4. The periodic Update
the sending of periodic route updates. timer governs the sending of periodic route updates (Section 3.7.1).
See Appendix B for suggested time constants.
3.2.4. The Neighbour Table 3.2.4. The Neighbour Table
The neighbour table contains the list of all neighbouring interfaces The neighbour table contains the list of all neighbouring interfaces
from which a Babel packet has been recently received. The neighbour from which a Babel packet has been recently received. The neighbour
table is indexed by pairs of the form (interface, address), and every table is indexed by pairs of the form (interface, address), and every
neighbour table entry contains the following data: neighbour table entry contains the following data:
o the local node's interface over which this neighbour is reachable; o the local node's interface over which this neighbour is reachable;
skipping to change at page 15, line 23 skipping to change at page 15, line 35
neighbour, an integer modulo 2^16. neighbour, an integer modulo 2^16.
o the outgoing Unicast Hello sequence number for this neighbour, an o the outgoing Unicast Hello sequence number for this neighbour, an
integer modulo 2^16 that is sent with each Unicast Hello TLV to integer modulo 2^16 that is sent with each Unicast Hello TLV to
this neighbour and is incremented (modulo 2^16) whenever a Unicast this neighbour and is incremented (modulo 2^16) whenever a Unicast
Hello is sent. (Note that the outgoing Unicast Hello seqno for a Hello is sent. (Note that the outgoing Unicast Hello seqno for a
neighbour is distinct from the interface's outgoing Multicast neighbour is distinct from the interface's outgoing Multicast
Hello seqno.) Hello seqno.)
There are three timers associated with each neighbour entry -- the There are three timers associated with each neighbour entry -- the
multicast hello timer, which is initialised from the interval value multicast hello timer, which is set to the interval value carried by
carried by scheduled Multicast Hello TLVs, the unicast hello timer, scheduled Multicast Hello TLVs sent by this neighbour, the unicast
which is initialised from the interval value carried by scheduled hello timer, which is set to the interval value carried by scheduled
Unicast Hello TLVs, and the IHU timer, which is initialised to a Unicast Hello TLVs, and the IHU timer, which is set to a small
small multiple of the interval carried in IHU TLVs. multiple of the interval carried in IHU TLVs (see "IHU Hold time" in
Appendix B for suggested values).
Note that the neighbour table is indexed by IP addresses, not by Note that the neighbour table is indexed by IP addresses, not by
router-ids: neighbourship is a relationship between interfaces, not router-ids: neighbourship is a relationship between interfaces, not
between nodes. Therefore, two nodes with multiple interfaces can between nodes. Therefore, two nodes with multiple interfaces can
participate in multiple neighbourship relationships, a situation that participate in multiple neighbourship relationships, a situation that
can notably arise when wireless nodes with multiple radios are can notably arise when wireless nodes with multiple radios are
involved. involved.
3.2.5. The Source Table 3.2.5. The Source Table
The source table is used to record feasibility distances. It is The source table is used to record feasibility distances. It is
indexed by triples of the form (prefix, plen, router-id), and every indexed by triples of the form (prefix, plen, router-id), and every
source table entry contains the following data: source table entry contains the following data:
o the prefix (prefix, plen), where plen is the prefix length, that o the prefix (prefix, plen), where plen is the prefix length in
this entry applies to; bits, that this entry applies to;
o the router-id of a router originating this prefix; o the router-id of a router originating this prefix;
o a pair (seqno, metric), this source's feasibility distance. o a pair (seqno, metric), this source's feasibility distance.
There is one timer associated with each entry in the source table -- 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 source garbage-collection timer. It is initialised to a time on
the order of minutes and reset as specified in Section 3.7.3. the order of minutes and reset as specified in Section 3.7.3.
3.2.6. The Route Table 3.2.6. The Route Table
skipping to change at page 16, line 29 skipping to change at page 16, line 46
o the sequence number with which this route was advertised; o the sequence number with which this route was advertised;
o the next-hop address of this route; o the next-hop address of this route;
o a boolean flag indicating whether this route is selected, i.e., o a boolean flag indicating whether this route is selected, i.e.,
whether it is currently being used for forwarding and is being whether it is currently being used for forwarding and is being
advertised. advertised.
There is one timer associated with each route table entry -- the There is one timer associated with each route table entry -- the
route expiry timer. It is initialised and reset as specified in route expiry timer. It is initialised and reset as specified in
Section 3.5.4. Section 3.5.3.
Note that there are two distinct (seqno, metric) pairs associated to Note that there are two distinct (seqno, metric) pairs associated to
each route: the route's distance, which is stored in the route table, each route: the route's distance, which is stored in the route table,
and the feasibility distance, stored in the source table and shared and the feasibility distance, stored in the source table and shared
between all routes with the same source. between all routes with the same source.
3.2.7. The Table of Pending Seqno Requests 3.2.7. The Table of Pending Seqno Requests
The table of pending seqno requests contains a list of seqno requests The table of pending seqno requests contains a list of seqno requests
that the local node has sent (either because they have been that the local node has sent (either because they have been
skipping to change at page 17, line 26 skipping to change at page 17, line 43
other hand, acknowledgment requests may be sent to either unicast or other hand, acknowledgment requests may be sent to either unicast or
multicast destinations, in which case they request an acknowledgment multicast destinations, in which case they request an acknowledgment
from all of the receiving nodes. from all of the receiving nodes.
When to request acknowledgments is a matter of local policy; the When to request acknowledgments is a matter of local policy; the
simplest strategy is to never request acknowledgments and to rely on simplest strategy is to never request acknowledgments and to rely on
periodic updates to ensure that any reachable routes are eventually periodic updates to ensure that any reachable routes are eventually
propagated throughout the routing domain. In order to improve propagated throughout the routing domain. In order to improve
convergence speed and reduce the amount of control traffic, convergence speed and reduce the amount of control traffic,
acknowledgment requests MAY be used in order to reliably send urgent acknowledgment requests MAY be used in order to reliably send urgent
updates (Section 3.7.2) and retractions (Section 3.5.5), especially updates (Section 3.7.2) and retractions (Section 3.5.4), especially
when the number of neighbours on a given interface is small. Since when the number of neighbours on a given interface is small. Since
Babel is designed to deal gracefully with packet loss on unreliable Babel is designed to deal gracefully with packet loss on unreliable
media, sending all packets with acknowledgment requests is not media, sending all packets with acknowledgment requests is not
necessary, and NOT RECOMMENDED, as the acknowledgments cause necessary, and NOT RECOMMENDED, as the acknowledgments cause
additional traffic and may force additional Address Resolution additional traffic and may force additional Address Resolution
Protocol (ARP) or Neighbour Discovery (ND) exchanges. Protocol (ARP) or Neighbour Discovery (ND) exchanges.
3.4. Neighbour Acquisition 3.4. Neighbour Acquisition
Neighbour acquisition is the process by which a Babel node discovers Neighbour acquisition is the process by which a Babel node discovers
skipping to change at page 19, line 35 skipping to change at page 19, line 50
(Equivalently, a node SHOULD send an extra IHU immediately after (Equivalently, a node SHOULD send an extra IHU immediately after
increasing its Hello interval.) increasing its Hello interval.)
Every IHU TLV contains two pieces of data: the link's rxcost Every IHU TLV contains two pieces of data: the link's rxcost
(reception cost) from the sender's perspective, used by the neighbour (reception cost) from the sender's perspective, used by the neighbour
for computing link costs (Section 3.4.3), and the interval between for computing link costs (Section 3.4.3), and the interval between
periodic IHU packets. A node receiving an IHU sets the value of the periodic IHU packets. A node receiving an IHU sets the value of the
txcost (transmission cost) maintained in the neighbour table to the txcost (transmission cost) maintained in the neighbour table to the
value contained in the IHU, and resets the IHU timer associated to value contained in the IHU, and resets the IHU timer associated to
this neighbour to a small multiple of the interval value received in this neighbour to a small multiple of the interval value received in
the IHU. When a neighbour's IHU timer expires, the neighbour's the IHU (see "IHU Hold time" in Appendix B for suggested values).
txcost is set to infinity.
When a neighbour's IHU timer expires, the neighbour's txcost is set
to infinity.
After updating a neighbour's txcost, the receiving node recomputes After updating a neighbour's txcost, the receiving node recomputes
the neighbour's cost (Section 3.4.3) and runs the route selection the neighbour's cost (Section 3.4.3) and runs the route selection
procedure (Section 3.6). procedure (Section 3.6).
3.4.3. Cost Computation 3.4.3. Cost Computation
A neighbourship association's link cost is computed from the values A neighbourship association's link cost is computed from the values
maintained in the neighbour table: the statistics kept in the maintained in the neighbour table: the statistics kept in the
neighbour table about the reception of Hellos, and the txcost neighbour table about the reception of Hellos, and the txcost
skipping to change at page 20, line 42 skipping to change at page 21, line 11
seqno, metric), where (prefix, plen) is the prefix for which a route seqno, metric), where (prefix, plen) is the prefix for which a route
is being advertised, router-id is the router-id of the router is being advertised, router-id is the router-id of the router
originating this update, seqno is a nondecreasing (modulo 2^16) originating this update, seqno is a nondecreasing (modulo 2^16)
integer that carries the originating router seqno, and metric is the integer that carries the originating router seqno, and metric is the
announced metric. announced metric.
Before being accepted, an update is checked against the feasibility Before being accepted, an update is checked against the feasibility
condition (Section 3.5.1), which ensures that the route does not condition (Section 3.5.1), which ensures that the route does not
create a routing loop. If the feasibility condition is not create a routing loop. If the feasibility condition is not
satisfied, the update is either ignored or prevents the route from satisfied, the update is either ignored or prevents the route from
being selected, as described in Section 3.5.4. If the feasibility being selected, as described in Section 3.5.3. If the feasibility
condition is satisfied, then the update cannot possibly cause a condition is satisfied, then the update cannot possibly cause a
routing loop. routing loop.
3.5.1. The Feasibility Condition 3.5.1. The Feasibility Condition
The feasibility condition is applied to all received updates. The The feasibility condition is applied to all received updates. The
feasibility condition compares the metric in the received update with feasibility condition compares the metric in the received update with
the metrics of the updates previously sent by the receiving node; the metrics of the updates previously sent by the receiving node;
updates that fail the feasibility condition, and therefore have updates that fail the feasibility condition, and therefore have
metrics large enough to cause a routing loop, are either ignored or metrics large enough to cause a routing loop, are either ignored or
skipping to change at page 22, line 11 skipping to change at page 22, line 29
neighbour's cost cannot render a selected route unfeasible. Note neighbour's cost cannot render a selected route unfeasible. Note
further that retractions (updates with infinite metric) are always further that retractions (updates with infinite metric) are always
feasible, since they cannot possibly cause a routing loop. feasible, since they cannot possibly cause a routing loop.
3.5.2. Metric Computation 3.5.2. Metric Computation
A route's metric is computed from the metric advertised by the A route's metric is computed from the metric advertised by the
neighbour and the neighbour's link cost. Just like cost computation, neighbour and the neighbour's link cost. Just like cost computation,
metric computation is considered a local policy matter; as far as metric computation is considered a local policy matter; as far as
Babel is concerned, the function M(c, m) used for computing a metric 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 from a locally computed link cost c and the metric m advertised by a
neighbour MUST only satisfy the following conditions: neighbour MUST only satisfy the following conditions:
o if c is infinite, then M(c, m) is infinite; o if c is infinite, then M(c, m) is infinite;
o M is strictly monotonic: M(c, m) > m. o M is strictly monotonic: M(c, m) > m.
Additionally, the metric SHOULD satisfy the following condition: Additionally, the metric SHOULD satisfy the following condition:
o M is left-distributive: if m <= m', then M(c, m) <= M(c, m'). o M is left-distributive: if m <= m', then M(c, m) <= M(c, m').
Note that while strict monotonicity is essential to the integrity of Note that while strict monotonicity is essential to the integrity of
the network (persistent routing loops may arise if it is not the network (persistent routing loops may arise if it is not
satisfied), left distributivity is not: if it is not satisfied, Babel satisfied), left distributivity is not: if it is not satisfied, Babel
will still converge to a loop-free configuration, but might not reach will still converge to a loop-free configuration, but might not reach
a global optimum (in fact, a global optimum may not even exist). a global optimum (in fact, a global optimum may not even exist).
As with cost computation, not all strategies for computing route As with cost computation, not all strategies for computing route
metrics will give good results. In particular, some metrics are more metrics will give good results. In particular, some metrics are more
likely than others to lead to routing instabilities (route flapping). likely than others to lead to routing instabilities (route flapping).
In Appendix A.3, we give a number of examples of strictly monotonic, In Appendix A.3, we give an number of examples of strictly monotonic,
left-distributive routing metrics that are known to work well in left-distributive routing metrics that are known to work well in
practice. practice. See also Appendix C, which describes a useful way to make
the metric computation configurable by a network administrator.
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
(Section 4.6.9).
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.6.
3.5.4. Route Acquisition 3.5.3. Route Acquisition
When a Babel node receives an update (prefix, plen, router-id, seqno, When a Babel node receives an update (prefix, plen, router-id, seqno,
metric) from a neighbour neigh with a link cost value equal to cost, metric) from a neighbour neigh, it checks whether it already has a
it checks whether it already has a route table entry indexed by route table entry indexed by (prefix, plen, neigh).
(prefix, plen, neigh).
If no such entry exists: If no such entry exists:
o if the update is unfeasible, it MAY be ignored; o if the update is unfeasible, it MAY be ignored;
o if the metric is infinite (the update is a retraction of a route o if the metric is infinite (the update is a retraction of a route
we do not know about), the update is ignored; we do not know about), the update is ignored;
o otherwise, a new entry is created in the route table, indexed by o otherwise, a new entry is created in the route table, indexed by
(prefix, plen, neigh), with source equal to (prefix, plen, router- (prefix, plen, neigh), with source equal to (prefix, plen, router-
skipping to change at page 23, line 37 skipping to change at page 23, line 32
If such an entry exists: If such an entry exists:
o if the entry is currently selected, the update is unfeasible, and o if the entry is currently selected, the update is unfeasible, and
the router-id of the update is equal to the router-id of the the router-id of the update is equal to the router-id of the
entry, then the update MAY be ignored; entry, then the update MAY be ignored;
o otherwise, the entry's sequence number, advertised metric, metric, o otherwise, the entry's sequence number, advertised metric, metric,
and router-id are updated and, if the advertised metric is not and router-id are updated and, if the advertised metric is not
infinite, the route's expiry timer is reset to a small multiple of infinite, the route's expiry timer is reset to a small multiple of
the Interval value included in the update. If the update is the Interval value included in the update (see "Route Hold time"
unfeasible, then the (now unfeasible) entry MUST be immediately in Appendix B for suggested values). If the update is unfeasible,
unselected. If the update caused the router-id of the entry to then the (now unfeasible) entry MUST be immediately unselected.
change, an update (possibly a retraction) MUST be sent in a timely If the update caused the router-id of the entry to change, an
manner (see Section 3.7.2). update (possibly a retraction) MUST be sent in a timely manner as
described in Section 3.7.2.
Note that the route table may contain unfeasible routes, either Note that the route table may contain unfeasible routes, either
because they were created by an unfeasible update or due to a metric because they were created by an unfeasible update or due to a metric
fluctuation. Such routes are never selected, since they are not fluctuation. Such routes are never selected, since they are not
known to be loop-free; should all the feasible routes become known to be loop-free; should all the feasible routes become
unusable, however, the unfeasible routes can be made feasible and unusable, however, the unfeasible routes can be made feasible and
therefore possible to select by sending requests along them (see therefore possible to select by sending requests along them (see
Section 3.8.2). Section 3.8.2).
When a route's expiry timer triggers, the behaviour depends on 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 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 set to infinity and the expiry timer is reset. If the metric is
already infinite, the route is flushed from the route table. already infinite, the route is flushed from the route table.
After the route table is updated, the route selection procedure After the route table is updated, the route selection procedure
(Section 3.6) is run. (Section 3.6) is run.
3.5.5. Hold Time 3.5.4. Hold Time
When a prefix P is retracted, because all routes are unfeasible or When a prefix P is retracted, because all routes are unfeasible or
have an infinite metric (whether due to the expiry timer or to other have an infinite metric (whether due to the expiry timer or to other
reasons), and a shorter prefix P' that covers P is reachable, P' reasons), and a shorter prefix P' that covers P is reachable, P'
cannot in general be used for routing packets destined to P without cannot in general be used for routing packets destined to P without
running the risk of creating a routing loop (Section 2.8). running the risk of creating a routing loop (Section 2.8).
To avoid this issue, whenever a prefix P is retracted, a route table To avoid this issue, whenever a prefix P is retracted, a route table
entry with infinite metric is maintained as described in entry with infinite metric is maintained as described in
Section 3.5.4 above. As long as this entry is maintained, packets Section 3.5.3 above. As long as this entry is maintained, packets
destined to an address within P MUST NOT be forwarded by following a destined to an address within P MUST NOT be forwarded by following a
route for a shorter prefix. This entry is removed as soon as a route for a shorter prefix. This entry is removed as soon as a
finite-metric update for prefix P is received and the resulting route finite-metric update for prefix P is received and the resulting route
selected. If no such update is forthcoming, the infinite metric selected. If no such update is forthcoming, the infinite metric
entry SHOULD be maintained at least until it is guaranteed that no entry SHOULD be maintained at least until it is guaranteed that no
neighbour has selected the current node as next-hop for prefix P. neighbour has selected the current node as next-hop for prefix P.
This can be achieved by either: This can be achieved by either:
o waiting until the route's expiry timer has expired o waiting until the route's expiry timer has expired
(Section 3.5.4); (Section 3.5.3);
o sending a retraction with an acknowledgment request (Section 3.3) o sending a retraction with an acknowledgment request (Section 3.3)
to every reachable neighbour that has not explicitly retracted to every reachable neighbour that has not explicitly retracted
prefix P and waiting for all acknowledgments. prefix P, and waiting for all acknowledgments.
The former option is simpler and ensures that at that point, any The former option is simpler and ensures that at that point, any
routes for prefix P pointing at the current node have expired. routes for prefix P pointing at the current node have expired.
However, since the expiry time can be as high as a few minutes, doing However, since the expiry time can be as high as a few minutes, doing
that prevents automatic aggregation by creating spurious black-holes that prevents automatic aggregation by creating spurious black-holes
for aggregated routes. The latter option is RECOMMENDED as it for aggregated routes. The latter option is RECOMMENDED as it
dramatically reduces the time for which a prefix is unreachable in dramatically reduces the time for which a prefix is unreachable in
the presence of aggregated routes. the presence of aggregated routes.
3.6. Route Selection 3.6. Route Selection
Route selection is the process by which a single route for a given 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- prefix is selected to be used for forwarding packets and to be re-
advertised to a node's neighbours. advertised to a node's neighbours.
Babel is designed to allow flexible route selection policies. As far Babel is designed to allow flexible route selection policies. As far
as the protocol's correctness is concerned, the route selection as the algorithm's correctness is concerned, the route selection
policy MUST only satisfy the following properties: policy MUST only satisfy the following properties:
o a route with infinite metric (a retracted route) is never o a route with infinite metric (a retracted route) is never
selected; selected;
o an unfeasible route is never selected. o an unfeasible route is never selected.
Note, however, that Babel does not naturally guarantee the stability Note, however, that Babel does not naturally guarantee the stability
of routing, and configuring conflicting route selection policies on of routing, and configuring conflicting route selection policies on
different routers may lead to persistent route oscillation. different routers may lead to persistent route oscillation.
skipping to change at page 25, line 39 skipping to change at page 25, line 35
o stable routes should be preferred to unstable ones; o stable routes should be preferred to unstable ones;
o switching next hops should be avoided. o switching next hops should be avoided.
Route selection MUST NOT take seqnos into account: a route MUST NOT Route selection MUST NOT take seqnos into account: a route MUST NOT
be preferred just because it carries a higher (more recent) seqno. be preferred just because it carries a higher (more recent) seqno.
Doing otherwise would cause route oscillation while a new seqno Doing otherwise would cause route oscillation while a new seqno
propagates through the network, possibly following multiple paths of propagates through the network, possibly following multiple paths of
different latency, and might even create persistent blackholes if the different latency, and might even create persistent blackholes if the
metric being used is not left-distributive Section 3.5.2. metric being used is not left-distributive (Section 3.5.2).
A simple but useful strategy is to choose the feasible route with the A simple but useful strategy is to choose the feasible route with the
smallest metric, with a small amount of hysteresis applied to avoid smallest metric, with a small amount of hysteresis applied to avoid
switching router-ids too often. switching router-ids too often.
After the route selection procedure is run, triggered updates After the route selection procedure is run, triggered updates
(Section 3.7.2) and requests (Section 3.8.2) are sent. (Section 3.7.2) and requests (Section 3.8.2) are sent.
3.7. Sending Updates 3.7. Sending Updates
A Babel speaker advertises to its neighbours its set of selected A Babel speaker advertises to its neighbours its set of selected
routes. Normally, this is done by sending one or more multicast routes. Normally, this is done by sending one or more multicast
packets containing Update TLVs on all of its connected interfaces; packets containing Update TLVs on all of its connected interfaces;
however, on link technologies where multicast is significantly more however, on link technologies where multicast is significantly more
expensive than unicast, a node MAY choose to send multiple copies of expensive than unicast, a node MAY choose to send multiple copies of
updates in unicast packets, especially when the number of neighbours updates in unicast packets, especially when the number of neighbours
is small. is small.
Additionally, in order to ensure that any black-holes are reliably Additionally, in order to ensure that any black-holes are reliably
cleared in a timely manner, a Babel node sends retractions (updates cleared in a timely manner, a Babel node may send retractions
with an infinite metric) for any recently retracted prefixes. (updates with an infinite metric) for any recently retracted
prefixes.
If an update is for a route injected into the Babel domain by the If an update is for a route injected into the Babel domain by the
local node (e.g., it carries the address of a local interface, the local node (e.g., it carries the address of a local interface, the
prefix of a directly attached network, or a prefix redistributed from prefix of a directly attached network, or a prefix redistributed from
a different routing protocol), the router-id is set to the local a different routing protocol), the router-id is set to the local
node's router-id, the metric is set to some arbitrary finite value node's router-id, the metric is set to some arbitrary finite value
(typically 0), and the seqno is set to the local router's sequence (typically 0), and the seqno is set to the local router's sequence
number. number.
If an update is for a route learned from another Babel speaker, the If an update is for a route learned from another Babel speaker, the
router-id and sequence number are copied from the route table entry, router-id and sequence number are copied from the route table entry,
and the metric is computed as specified in Section 3.5.2. and the metric is computed as specified in Section 3.5.2.
3.7.1. Periodic Updates 3.7.1. Periodic Updates
Every Babel speaker periodically advertises all of its selected Every Babel speaker MUST advertise each of its selected routes on
routes on all of its interfaces, including any recently retracted every interface, at least once every Update interval. Since Babel
routes. Since Babel doesn't suffer from routing loops (there is no doesn't suffer from routing loops (there is no "counting to
"counting to infinity") and relies heavily on triggered updates infinity") and relies heavily on triggered updates (Section 3.7.2),
(Section 3.7.2), this full dump only needs to happen infrequently. this full dump only needs to happen infrequently (see Appendix B for
suggested intervals).
3.7.2. Triggered Updates 3.7.2. Triggered Updates
In addition to periodic routing updates, a Babel speaker sends In addition to periodic routing updates, a Babel speaker sends
unscheduled, or triggered, updates in order to inform its neighbours unscheduled, or triggered, updates in order to inform its neighbours
of a significant change in the network topology. of a significant change in the network topology.
A change of router-id for the selected route to a given prefix may be 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 indicative of a routing loop in formation; hence, whenever it changes
triggered update in a timely manner whenever it changes the selected the selected router-id for a given destination, a node MUST send an
router-id for a given destination. Additionally, it SHOULD make a update as an urgent TLV (as defined in Section 3.1). Additionally,
reasonable attempt at ensuring that all reachable neighbours receive it SHOULD make a reasonable attempt at ensuring that all reachable
this update. neighbours receive this update.
There are two strategies for ensuring that. If the number of There are two strategies for ensuring that. If the number of
neighbours is small, then it is reasonable to send the update neighbours is small, then it is reasonable to send the update
together with an acknowledgment request; the update is resent until together with an acknowledgment request; the update is resent until
all neighbours have acknowledged the packet, up to some number of all neighbours have acknowledged the packet, up to some number of
times. If the number of neighbours is large, however, requesting times. If the number of neighbours is large, however, requesting
acknowledgments from all of them might cause a non-negligible amount acknowledgments from all of them might cause a non-negligible amount
of network traffic; in that case, it may be preferable to simply of network traffic; in that case, it may be preferable to simply
repeat the update some reasonable number of times (say, 5 for repeat the update some reasonable number of times (say, 3 for
wireless and 2 for wired links). wireless and 2 for wired links). The number of copies MUST NOT
exceed 5, and the copies SHOULD be separated by a small delay, as
described in Section 3.1.
A route retraction is somewhat less worrying: if the route retraction A route retraction is somewhat less worrying: if the route retraction
doesn't reach all neighbours, a black-hole might be created, which, doesn't reach all neighbours, a black-hole might be created, which,
unlike a routing loop, does not endanger the integrity of the unlike a routing loop, does not endanger the integrity of the
network. When a route is retracted, a node SHOULD send a triggered network. When a route is retracted, a node SHOULD send a triggered
update and SHOULD make a reasonable attempt at ensuring that all update and SHOULD make a reasonable attempt at ensuring that all
neighbours receive this retraction. neighbours receive this retraction.
Finally, a node MAY send a triggered update when the metric for a Finally, a node MAY send a triggered update when the metric for a
given prefix changes in a significant manner, due to a received given prefix changes in a significant manner, due to a received
skipping to change at page 29, line 6 skipping to change at page 29, line 6
3.8.1.1. Route Requests 3.8.1.1. Route Requests
When a node receives a route request for a given prefix, it checks When a node receives a route request for a given prefix, it checks
its route table for a selected route to this exact prefix. If such a its route table for a selected route to this exact prefix. If such a
route exists, it MUST send an update (over unicast or over route exists, it MUST send an update (over unicast or over
multicast); if such a route does not exist, it MUST send a retraction multicast); if such a route does not exist, it MUST send a retraction
for that prefix. for that prefix.
When a node receives a wildcard route request, it SHOULD send a full When a node receives a wildcard route request, it SHOULD send a full
route table dump. Full route dumps MAY be rate-limited, especially route table dump. Full route dumps SHOULD be rate-limited,
if they are sent over multicast. especially if they are sent over multicast.
3.8.1.2. Seqno Requests 3.8.1.2. Seqno Requests
When a node receives a seqno request for a given router-id and When a node receives a seqno request for a given router-id and
sequence number, it checks whether its route table contains a sequence number, it checks whether its route table contains a
selected entry for that prefix. If a selected route for the given selected entry for that prefix. If a selected route for the given
prefix exists, it has finite metric, and either the router-ids are prefix exists, it has finite metric, and either the router-ids are
different or the router-ids are equal and the entry's sequence number different or the router-ids are equal and the entry's sequence number
is no smaller (modulo 2^16) than the requested sequence number, the is no smaller (modulo 2^16) than the requested sequence number, the
node MUST send an update for the given prefix. If the router-ids node MUST send an update for the given prefix. If the router-ids
match but the requested seqno is larger (modulo 2^16) than the route match but the requested seqno is larger (modulo 2^16) than the route
entry's, the node compares the router-id against its own router-id. 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 If the router-id is its own, then it increases its sequence number by
1 (modulo 2^16) and sends an update. A node MUST NOT increase its 1 (modulo 2^16) and sends an update. A node MUST NOT increase its
sequence number by more than 1 in response to a seqno request. sequence number by more than 1 in reaction to a single seqno request.
Otherwise, if the requested router-id is not its own, the received Otherwise, if the requested router-id is not its own, the received
request's hop count is 2 or more, and the node is advertising the node consults the hop count field of the request. If the hop count
prefix to its neighbours, the node selects a neighbour to forward the is 2 or more, and the node is advertising the prefix to its
request to as follows: neighbours, the node selects a neighbour to forward the request to as
follows:
o if the node has one or more feasible routes toward the requested o if the node has one or more feasible routes toward the requested
prefix with a next hop that is not the requesting node, then the prefix with a next hop that is not the requesting node, then the
node MUST forward the request to the next hop of one such route; node MUST forward the request to the next hop of one such route;
o otherwise, if the node has one or more (not necessarily feasible) o otherwise, if the node has one or more (not feasible) routes to
routes to the requested prefix with a next hop that is not the the requested prefix with a next hop that is not the requesting
requesting node, then the node SHOULD forward the request to the node, then the node SHOULD forward the request to the next hop of
next hop of one such route. one such route.
In order to actually forward the request, the node decrements the hop In order to actually forward the request, the node decrements the hop
count and sends the request in a unicast packet destined to the count and sends the request in a unicast packet destined to the
selected neighbour. selected neighbour. The forwarded request SHOULD be sent as an
urgent TLV (as defined in Section 3.1).
A node SHOULD maintain a list of recently forwarded seqno requests A node SHOULD maintain a list of recently forwarded seqno requests
and forward the reply (an update with a seqno sufficiently large to and forward the reply (an update with a seqno sufficiently large to
satisfy the request) in a timely manner. A node SHOULD compare every satisfy the request) as an urgent TLV (as defined in Section 3.1). A
incoming seqno request against its list of recently forwarded seqno node SHOULD compare every incoming seqno request against its list of
requests and avoid forwarding it if it is redundant (i.e., if it has recently forwarded seqno requests and avoid forwarding it if it is
recently sent a request with the same prefix, router-id and a seqno redundant (i.e., if it has recently sent a request with the same
that is not smaller modulo 2^16). prefix, router-id and a seqno that is not smaller modulo 2^16).
Since the request-forwarding mechanism does not necessarily obey the Since the request-forwarding mechanism does not necessarily obey the
feasibility condition, it may get caught in routing loops; hence, feasibility condition, it may get caught in routing loops; hence,
requests carry a hop count to limit the time during which they remain requests carry a hop count to limit the time during which they remain
in the network. However, since requests are only ever forwarded as in the network. However, since requests are only ever forwarded as
unicast packets, the initial hop count need not be kept particularly unicast packets, the initial hop count need not be kept particularly
low, and performing an expanding horizon search is not necessary. A low, and performing an expanding horizon search is not necessary. A
single request MUST NOT be duplicated: it MUST NOT be forwarded to a single request MUST NOT be duplicated: it MUST NOT be forwarded to a
multicast address, and it MUST NOT be forwarded to multiple multicast address, and it MUST NOT be forwarded to multiple
neighbours. However, if a seqno request is resent by its originator, neighbours. However, if a seqno request is resent by its originator,
skipping to change at page 30, line 30 skipping to change at page 30, line 34
When a route is retracted or expires, a Babel node usually switches 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, to another feasible route for the same prefix. It may be the case,
however, that no such routes are available. however, that no such routes are available.
A node that has lost all feasible routes to a given destination but A node that has lost all feasible routes to a given destination but
still has unexpired unfeasible routes to that destination MUST send a still has unexpired unfeasible routes to that destination MUST send a
seqno request; if it doesn't have any such routes, it MAY still send seqno request; if it doesn't have any such routes, it MAY still send
a seqno request. The router-id of the request is set to the router- 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 id of the route that it has just lost, and the requested seqno is the
value contained in the source table plus 1. value contained in the source table plus 1. The request carries a
hop count, which is used as a last-resort mechanism to ensure that it
eventually vanishes from the network; it MAY be set to any value that
is larger than the diameter of the network (64 is a suitable default
value).
If the node has any (unfeasible) routes to the requested destination, If the node has any (unfeasible) routes to the requested destination,
then it MUST send the request to at least one of the next-hop then it MUST send the request to at least one of the next-hop
neighbours that advertised these routes, and SHOULD send it to all of neighbours that advertised these routes, and SHOULD send it to all of
them; in any case, it MAY send the request to any other neighbours, them; in any case, it MAY send the request to any other neighbours,
whether they advertise a route to the requested destination or not. whether they advertise a route to the requested destination or not.
A simple implementation strategy is therefore to unconditionally A simple implementation strategy is therefore to unconditionally
multicast the request over all interfaces. multicast the request over all interfaces.
Similar requests will be sent by other nodes that are affected by the Similar requests will be sent by other nodes that are affected by the
route's loss. If the network is still connected, and assuming no route's loss. If the network is still connected, and assuming no
packet loss, then at least one of these requests will be forwarded to packet loss, then at least one of these requests will be forwarded to
the source, resulting in a route being advertised with a new sequence the source, resulting in a route being advertised with a new sequence
number. (Due to duplicate suppression, only a small number of such number. (Due to duplicate suppression, only a small number of such
requests will actually reach the source.) requests will actually reach the source.)
In order to compensate for packet loss, a node SHOULD repeat such a 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 request a small number of times if no route becomes feasible within a
short time. In the presence of heavy packet loss, however, all such short time (see "Request Timeout" in Appendix B for suggested
values). In the presence of heavy packet loss, however, all such
requests might be lost; in that case, the mechanism in the next requests might be lost; in that case, the mechanism in the next
section will eventually ensure that a new seqno is received. section will eventually ensure that a new seqno is received.
3.8.2.2. Dealing with Unfeasible Updates 3.8.2.2. Dealing with Unfeasible Updates
When a route's metric increases, a node might receive an unfeasible When a route's metric increases, a node might receive an unfeasible
update for a route that it has currently selected. As specified in 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 Section 3.5.1, the receiving node will either ignore the update or
unselect the route. unselect the route.
skipping to change at page 31, line 41 skipping to change at page 32, line 5
In the presence of packet loss, however, it may be the case that no In the presence of packet loss, however, it may be the case that no
update is successfully received for an extended period of time, update is successfully received for an extended period of time,
causing a route to expire. In order to avoid such spurious expiry, causing a route to expire. In order to avoid such spurious expiry,
shortly before a selected route expires, a Babel node SHOULD send a shortly before a selected route expires, a Babel node SHOULD send a
unicast route request to the neighbour that advertised this route; unicast route request to the neighbour that advertised this route;
since nodes always send either updates or retractions in response to since nodes always send either updates or retractions in response to
non-wildcard route requests (Section 3.8.1.1), this will usually non-wildcard route requests (Section 3.8.1.1), this will usually
result in the route being either refreshed or retracted. result in the route being either refreshed or retracted.
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. Note however that doing that
carelessly can cause serious congestion when a whole network is
rebooted, especially on link layers with high per-packet overhead
(e.g., IEEE 802.11).
4. Protocol Encoding 4. Protocol Encoding
A Babel packet MUST be sent as the body of a UDP datagram, with A Babel packet MUST be sent as the body of a UDP datagram, with
network-layer hop count set to 1, destined to a well-known multicast 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 address or to a unicast address, over IPv4 or IPv6; in the case of
IPv6, these addresses are link-local. Both the source and IPv6, these addresses are link-local. Both the source and
destination UDP port are set to a well-known port number. A Babel 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 packet MUST be silently ignored unless its source address is either a
link-local IPv6 address or an IPv4 address belonging to the local link-local IPv6 address or an IPv4 address belonging to the local
network, and its source port is the well-known Babel port. It MAY be network, and its source port is the well-known Babel port. It MAY be
silently ignored if its destination address is a global IPv6 address. silently ignored if its destination address is a global IPv6 address.
In order to minimise the number of packets being sent while avoiding In order to minimise the number of packets being sent while avoiding
lower-layer fragmentation, a Babel node SHOULD attempt to maximise lower-layer fragmentation, a Babel node SHOULD maximise the size of
the size of the packets it sends, up to the outgoing interface's MTU the packets it sends, up to the outgoing interface's MTU adjusted for
adjusted for lower-layer headers (28 octets for UDP over IPv4, 48 lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP
octets for UDP over IPv6). It MUST NOT send packets larger than the over IPv6). It MUST NOT send packets larger than the attached
attached interface's MTU adjusted for lower-layer headers or 512 interface's MTU adjusted for lower-layer headers or 512 octets,
octets, whichever is larger, but not exceeding 2^16 - 1 adjusted for whichever is larger, but not exceeding 2^16 - 1 adjusted for lower-
lower-layer headers. Every Babel speaker MUST be able to receive layer headers. Every Babel speaker MUST be able to receive packets
packets that are as large as any attached interface's MTU adjusted that are as large as any attached interface's MTU adjusted for lower-
for lower-layer headers or 512 octets, whichever is larger. Babel layer headers or 512 octets, whichever is larger. Babel packets MUST
packets MUST NOT be sent in IPv6 Jumbograms. NOT be sent in IPv6 Jumbograms.
In order to avoid global synchronisation of a Babel network and to
aggregate multiple TLVs into large packets, a Babel node SHOULD
buffer every TLV and delay sending a 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. Data Types
4.1.1. Interval 4.1.1. Interval
Relative times are carried as 16-bit values specifying a number of Relative times are carried as 16-bit values specifying a number of
centiseconds (hundredths of a second). This allows times up to centiseconds (hundredths of a second). This allows times up to
roughly 11 minutes with a granularity of 10ms, which should cover all roughly 11 minutes with a granularity of 10ms, which should cover all
reasonable applications of Babel. reasonable applications of Babel.
4.1.2. Router-Id 4.1.2. Router-Id
A router-id is an arbitrary 8-octet value. A router-id MUST NOT A router-id is an arbitrary 8-octet value. A router-id MUST NOT
consist of either all binary zeroes (0000000000000000 hexadecimal) or consist of either all binary zeroes (0000000000000000 hexadecimal) or
all binary ones ones (FFFFFFFFFFFFFFFF hexadecimal). all binary ones (FFFFFFFFFFFFFFFF hexadecimal).
4.1.3. Address 4.1.3. Address
Since the bulk of the protocol is taken by addresses, multiple ways Since the bulk of the protocol is taken by addresses, multiple ways
of encoding addresses are defined. Additionally, a common subnet of encoding addresses are defined. Additionally, within Update TLVs
prefix may be omitted when multiple addresses are sent in a single a common subnet prefix may be omitted when multiple addresses are
packet -- this is known as address compression (Section 4.6.9). sent in a single packet -- this is known as address compression
(Section 4.6.9).
Address encodings: Address encodings:
o AE 0: wildcard address. The value is 0 octets long. 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 1: IPv4 address. Compression is allowed. 4 octets or less.
o AE 2: IPv6 address. Compression is allowed. 16 octets or less. o AE 2: IPv6 address. Compression is allowed. 16 octets or less.
o AE 3: link-local IPv6 address. Compression is not allowed. The o AE 3: link-local IPv6 address. Compression is not allowed. The
skipping to change at page 33, line 37 skipping to change at page 33, line 28
4.1.4. Prefixes 4.1.4. Prefixes
A network prefix is encoded just like a network address, but it is 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 stored in the smallest number of octets that are enough to hold the
significant bits (up to the prefix length). significant bits (up to the prefix length).
4.2. Packet Format 4.2. Packet Format
A Babel packet consists of a 4-octet header, followed by a sequence A Babel packet consists of a 4-octet header, followed by a sequence
of TLVs (the packet body), optionally followed by a second sequence of TLVs (the packet body), optionally followed by a second sequence
of TLVs (the packet trailer). of TLVs (the packet trailer). The format is designed to be
extensible; see Appendix D for extensibility considerations.
0 1 2 3 0 1 2 3
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 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 | | Magic | Version | Body length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Body ... | Packet Body ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Packet Trailer... | Packet Trailer...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
skipping to change at page 34, line 30 skipping to change at page 34, line 22
The packet body and trailer are both sequences of TLVs. The packet The packet body and trailer are both sequences of TLVs. The packet
body is the normal place to store TLVs; the packet trailer only body is the normal place to store TLVs; the packet trailer only
contains specialised TLVs that do not need to be protected by contains specialised TLVs that do not need to be protected by
cryptographic security mechanisms. When parsing the trailer, the cryptographic security mechanisms. When parsing the trailer, the
receiver MUST ignore any TLV unless its definition explicitly states receiver MUST ignore any TLV unless its definition explicitly states
that it is allowed to appear there. Among the TLVs defined in this that it is allowed to appear there. Among the TLVs defined in this
document, only Pad1 and PadN are allowed in the trailer; since these document, only Pad1 and PadN are allowed in the trailer; since these
TLVs are ignored in any case, an implementation MAY silently ignore TLVs are ignored in any case, an implementation MAY silently ignore
the packet trailer without even parsing it, unless it implements at the packet trailer without even parsing it, unless it implements at
least one extension that defines TLVs that are allowed to appear in least one protocol extension that defines TLVs that are allowed to
the trailer. appear in the trailer.
4.3. TLV Format 4.3. TLV Format
With the exception of Pad1, all TLVs have the following structure: With the exception of Pad1, all TLVs have the following structure:
0 1 2 3 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 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Payload... | Type | Length | Payload...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields : Fields :
Type The type of the TLV. Type The type of the TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. If the body is longer than the expected length of Length fields.
a given type of TLV, any extra data MUST be silently
ignored.
Payload The TLV payload, which consists of a body and, for selected Payload The TLV payload, which consists of a body and, for selected
TLV types, an optional list of sub-TLVs. TLV types, an optional list of sub-TLVs.
TLVs with an unknown type value MUST be silently ignored. TLVs with an unknown type value MUST be silently ignored.
4.4. Sub-TLV Format 4.4. Sub-TLV Format
Every TLV carries an explicit length in its header; however, most Every TLV carries an explicit length in its header; however, most
TLVs are self-terminating, in the sense that it is possible to TLVs are self-terminating, in the sense that it is possible to
determine the length of the body without reference to the explicit determine the length of the body without reference to the explicit
Length field. If a TLV has a self-terminating format, then it MAY Length field. If a TLV has a self-terminating format, then the space
allow a sequence of sub-TLVs to follow the body. between the natural size of the TLV and the size announced in the
Length field may be used to store a sequence of sub-TLVs.
Sub-TLVs have the same structure as TLVs. With the exception of Sub-TLVs have the same structure as TLVs. With the exception of
PAD1, all TLVs have the following structure: Pad1, all TLVs have the following structure:
0 1 2 3 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 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... | Type | Length | Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields : Fields :
Type The type of the sub-TLV. Type The type of the sub-TLV.
Length The length of the body, in octets, exclusive of the Type Length The length of the body in octets, exclusive of the Type and
and Length fields. Length fields.
Body The sub-TLV body, the interpretation of which depends on Body The sub-TLV body, the interpretation of which depends on
both the type of the sub-TLV and the type of the TLV within both the type of the sub-TLV and the type of the TLV within
which it is embedded. which it is embedded.
The most-significant bit of the sub-TLV type (the bit with value 80 The most-significant bit of the sub-TLV type (the bit with value 80
hexadecimal), called the mandatory bit, indicates how to handle hexadecimal), is called the mandatory bit; in other words, sub-TLV
unknown sub-TLVs. If the mandatory bit is not set, then an unknown types 128 through 255 have the mandatory bit set. This bit indicates
sub-TLV MUST be silently ignored, and the rest of the TLV is how to handle unknown sub-TLVs. If the mandatory bit is not set,
processed normally. If the mandatory bit is set, then the whole then an unknown sub-TLV MUST be silently ignored, and the rest of the
enclosing TLV MUST be silently ignored (except for updating the TLV is processed normally. If the mandatory bit is set, then the
parser state by a Router-Id, Next-Hop or Update TLV, see whole enclosing TLV MUST be silently ignored (except for updating the
Section 4.6.7, Section 4.6.8, and Section 4.6.9). parser state by a Router-Id, Next-Hop or Update TLV, as described in
the next section).
4.5. Parser state 4.5. Parser state and encoding of updates
Babel uses a stateful parser: a TLV may refer to data from a previous In a large network, the bulk of Babel traffic consists of route
TLV. The parser state consists of the following pieces of data: updates; hence, some care has been given to encoding them
efficiently. The data conceptually contained in an update
(Section 3.5) is split into three pieces:
o the prefix, seqno and metric are contained in the Update TLV
itself (Section 4.6.9);
o the router-id is taken from Router-Id TLV that precedes the Update
TLV, and may be shared among multiple Update TLVs (Section 4.6.7);
o the next hop is taken either from the source-address of the
network-layer packet that contains the Babel packet, or from an
explicit Next-Hop TLV (Section 4.6.8).
In addition to the above, an Update TLV can omit a prefix of the
prefix being announced, which is then extracted from the preceding
Update TLV in the same address family (IPv4 or IPv6). Finally, as a
special optimisation for the case when a router-id coincides with the
interface-id part of an IPv6 address, Router-ID TLV itself may be
omitted and the router-id derived derived from the low-order bits of
the advertised prefix (Section 4.6.9).
In order to implement these compression techniques, Babel uses a
stateful parser: a TLV may refer to data from a previous TLV. The
parser state consists of the following pieces of data:
o for each address encoding that allows compression, the current o for each address encoding that allows compression, the current
default prefix; this is undefined at the start of the packet, and default prefix; this is undefined at the start of the packet, and
is updated by each Update TLV with the Prefix flag set is updated by each Update TLV with the Prefix flag set
(Section 4.6.9); (Section 4.6.9);
o for each address family (IPv4 or IPv6), the current next-hop; this o for each address family (IPv4 or IPv6), the current next-hop; this
is the source address of the enclosing packet for the matching is the source address of the enclosing packet for the matching
address family at the start of a packet, and is updated by each address family at the start of a packet, and is updated by each
Next-Hop TLV (Section 4.6.8); Next-Hop TLV (Section 4.6.8);
o the current router-id; this is undefined at the start of the o the current router-id; this is undefined at the start of the
packet, and is updated by each Router-ID TLV (Section 4.6.7) and packet, and is updated by each Router-ID TLV (Section 4.6.7) and
by each Update TLV with Router-Id flag set. by each Update TLV with Router-Id flag set.
Since the parser state must be identical across implementations, it Since the parser state must be identical across implementations, it
is updated before checking for mandatory TLVs: parsing a TLV MUST is updated before checking for mandatory sub-TLVs: parsing a TLV MUST
update the parser state even if the TLV is otherwise ignored due to update the parser state even if the TLV is otherwise ignored due to
an unknown mandatory sub-TLV. an unknown mandatory sub-TLV.
None of the TLVs that modify the parser state are allowed in the None of the TLVs that modify the parser state are allowed in the
packet trailer; hence, an implementation may choose to use a packet trailer; hence, an implementation may choose to use a
dedicated stateless parser to parse the packet trailer. dedicated stateless parser to parse the packet trailer.
4.6. Details of Specific TLVs 4.6. Details of Specific TLVs
4.6.1. Pad1 4.6.1. Pad1
skipping to change at page 37, line 4 skipping to change at page 37, line 18
This TLV is silently ignored on reception. It is allowed in the This TLV is silently ignored on reception. It is allowed in the
packet trailer. packet trailer.
4.6.2. PadN 4.6.2. PadN
0 1 2 3 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 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... | Type = 1 | Length | MBZ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields : Fields :
Type Set to 1 to indicate a PadN TLV. Type Set to 1 to indicate a PadN TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
MBZ Must be zero, set to 0 on transmission. MBZ Must be zero, set to 0 on transmission.
This TLV is silently ignored on reception. It is allowed in the This TLV is silently ignored on reception. It is allowed in the
packet trailer. packet trailer.
4.6.3. Acknowledgment Request 4.6.3. Acknowledgment Request
0 1 2 3 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 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
skipping to change at page 37, line 33 skipping to change at page 37, line 48
| Nonce | Interval | | Nonce | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV requests that the receiver send an Acknowledgment TLV within This TLV requests that the receiver send an Acknowledgment TLV within
the number of centiseconds specified by the Interval field. the number of centiseconds specified by the Interval field.
Fields : Fields :
Type Set to 2 to indicate an Acknowledgment Request TLV. Type Set to 2 to indicate an Acknowledgment Request TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Nonce An arbitrary value that will be echoed in the receiver's Nonce An arbitrary value that will be echoed in the receiver's
Acknowledgment TLV. Acknowledgment TLV.
Interval A time interval in centiseconds after which the sender will Interval A time interval in centiseconds after which the sender will
assume that this packet has been lost. This MUST NOT be 0. assume that this packet has been lost. This MUST NOT be 0.
The receiver MUST send an Acknowledgment TLV before this The receiver MUST send an Acknowledgment TLV before this
time has elapsed (with a margin allowing for propagation time has elapsed (with a margin allowing for propagation
skipping to change at page 38, line 19 skipping to change at page 38, line 30
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 3 | Length | Nonce | | Type = 3 | Length | Nonce |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV is sent by a node upon receiving an Acknowledgment Request. This TLV is sent by a node upon receiving an Acknowledgment Request.
Fields : Fields :
Type Set to 3 to indicate an Acknowledgment TLV. Type Set to 3 to indicate an Acknowledgment TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
Nonce Set to the Nonce value of the Acknowledgment Request that Nonce Set to the Nonce value of the Acknowledgment Request that
prompted this Acknowledgment. prompted this Acknowledgment.
Since nonce values are not globally unique, this TLV MUST be sent to Since nonce values are not globally unique, this TLV MUST be sent to
a unicast address. a unicast address.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.5. Hello 4.6.5. Hello
skipping to change at page 38, line 47 skipping to change at page 39, line 9
| Seqno | Interval | | Seqno | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV is used for neighbour discovery and for determining a This TLV is used for neighbour discovery and for determining a
neighbour's reception cost. neighbour's reception cost.
Fields : Fields :
Type Set to 4 to indicate a Hello TLV. Type Set to 4 to indicate a Hello TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
Flags The individual bits of this field specify special handling Flags The individual bits of this field specify special handling
of this TLV (see below). of this TLV (see below).
Seqno If the Unicast flag is set, this is the value of the Seqno If the Unicast flag is set, this is the value of the
sending node's outgoing Unicast Hello seqno for this sending node's outgoing Unicast Hello seqno for this
neighbour. Otherwise, it is the sending node's outgoing neighbour. Otherwise, it is the sending node's outgoing
Multicast Hello seqno for this interface. Multicast Hello seqno for this interface.
Interval If non-zero, this is an upper bound, expressed in Interval If non-zero, this is an upper bound, expressed in
skipping to change at page 40, line 21 skipping to change at page 40, line 26
| Address... | Address...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
An IHU ("I Heard You") TLV is used for confirming bidirectional An IHU ("I Heard You") TLV is used for confirming bidirectional
reachability and carrying a link's transmission cost. reachability and carrying a link's transmission cost.
Fields : Fields :
Type Set to 5 to indicate an IHU TLV. Type Set to 5 to indicate an IHU TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
AE The encoding of the Address field. This should be 1 or 3 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 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 is sent to a unicast address, if the association is over a
point-to-point link, or when bidirectional reachability is point-to-point link, or when bidirectional reachability is
ascertained by means outside of the Babel protocol. ascertained by means outside of the Babel protocol.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Rxcost The rxcost according to the sending node of the interface Rxcost The rxcost according to the sending node of the interface
skipping to change at page 41, line 23 skipping to change at page 41, line 27
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 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 | | Type = 6 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Router-Id + + Router-Id +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A Router-Id TLV establishes a router-id that is implied by subsequent A Router-Id TLV establishes a router-id that is implied by subsequent
Update TLVs. This TLV sets the router-id even if it is otherwise Update TLVs, as described in Section 4.5. This TLV sets the router-
ignored due to an unknown mandatory sub-TLV. id even if it is otherwise ignored due to an unknown mandatory sub-
TLV.
Fields : Fields :
Type Set to 6 to indicate a Router-Id TLV. Type Set to 6 to indicate a Router-Id TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Router-Id The router-id for routes advertised in subsequent Update Router-Id The router-id for routes advertised in subsequent Update
TLVs. This MUST NOT consist of all zeroes or all ones. TLVs. This MUST NOT consist of all zeroes or all ones.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.8. Next Hop 4.6.8. Next Hop
0 1 2 3 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 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 | | Type = 7 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next hop... | Next hop...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
A Next Hop TLV establishes a next-hop address for a given address A Next Hop TLV establishes a next-hop address for a given address
family (IPv4 or IPv6) that is implied in subsequent Update TLVs. family (IPv4 or IPv6) that is implied in subsequent Update TLVs, as
described in Section 4.5. This TLV sets up the next-hop for
This TLV sets up the next-hop for subsequent Update TLVs even if it subsequent Update TLVs even if it is otherwise ignored due to an
is otherwise ignored due to an unknown mandatory sub-TLV. unknown mandatory sub-TLV.
Fields : Fields :
Type Set to 7 to indicate a Next Hop TLV. Type Set to 7 to indicate a Next Hop TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
AE The encoding of the Address field. This SHOULD be 1 (IPv4) AE The encoding of the Address field. This SHOULD be 1 (IPv4)
or 3 (link-local IPv6), and MUST NOT be 0. or 3 (link-local IPv6), and MUST NOT be 0.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Next hop The next-hop address advertised by subsequent Update TLVs, Next hop The next-hop address advertised by subsequent Update TLVs,
for this address family. for this address family.
When the address family matches the network-layer protocol that this When the address family matches the network-layer protocol that this
skipping to change at page 42, line 49 skipping to change at page 43, line 18
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Plen | Omitted | Interval | | Plen | Omitted | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Metric | | Seqno | Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix... | Prefix...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
An Update TLV advertises or retracts a route. As an optimisation, it An Update TLV advertises or retracts a route. As an optimisation, it
can optionally have the side effect of establishing a new implied can optionally have the side effect of establishing a new implied
router-id and a new default prefix. router-id and a new default prefix, as described in Section 4.5.
Fields : Fields :
Type Set to 8 to indicate an Update TLV. Type Set to 8 to indicate an Update TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
AE The encoding of the Prefix field. AE The encoding of the Prefix field.
Flags The individual bits of this field specify special handling Flags The individual bits of this field specify special handling
of this TLV (see below). of this TLV (see below).
Plen The length of the advertised prefix. Plen The length in bits of the advertised prefix. If AE is 3
(link-local IPv6), Omitted MUST be 0.
Omitted The number of octets that have been omitted at the Omitted The number of octets that have been omitted at the
beginning of the advertised prefix and that should be taken beginning of the advertised prefix and that should be taken
from a preceding Update TLV in the same address family with from a preceding Update TLV in the same address family with
the Prefix flag set. the Prefix flag set.
Interval An upper bound, expressed in centiseconds, on the time Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new update for after which the sending node will send a new update for
this prefix. This MUST NOT be 0. The receiving node will this prefix. This MUST NOT be 0. The receiving node will
use this value to compute a hold time for the route table use this value to compute a hold time for the route table
skipping to change at page 44, line 26 skipping to change at page 44, line 48
router-id consists of 4 octets of zeroes followed by the IPv4 router-id consists of 4 octets of zeroes followed by the IPv4
address. address.
o X: all other bits MUST be sent as 0 and silently ignored on o X: all other bits MUST be sent as 0 and silently ignored on
reception. reception.
The prefix being advertised by an Update TLV is computed as follows: 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 o the first Omitted octets of the prefix are taken from the previous
Update TLV with the Prefix flag set and the same address encoding, Update TLV with the Prefix flag set and the same address encoding,
even if it was ignored due to an unknown mandatory sub-TLV; even if it was ignored due to an unknown mandatory sub-TLV; if
Omitted is not zero and there is no such TLV, then this Update
MUST be ignored;
o the next (Plen/8 - Omitted) rounded upwards octets are taken from o the next (Plen/8 - Omitted) rounded upwards octets are taken from
the Prefix field; the Prefix field;
o the remaining octets are set to 0. If AE is 3 (link-local IPv6), o if Plen is not a multiple of 8, then any bits beyond Plen (i.e.,
Omitted MUST be 0) the low-order (8 - Plen MOD 8) bits of the last octet) are
cleared;
o the remaining octets are set to 0.
If the Metric field is finite, the router-id of the originating node If the Metric field is finite, the router-id of the originating node
for this announcement is taken from the prefix advertised by this for this announcement is taken from the prefix advertised by this
Update if the Router-Id flag is set, computed as described above. Update if the Router-Id flag is set, computed as described above.
Otherwise, it is taken either from the preceding Router-Id packet, or Otherwise, it is taken either from the preceding Router-Id TLV, or
the preceding Update packet with the Router-Id flag set, whichever the preceding Update TLV with the Router-Id flag set, whichever comes
comes last, even if that TLV is otherwise ignored due to an unknown last, even if that TLV is otherwise ignored due to an unknown
mandatory sub-TLV. mandatory sub-TLV; if there is no suitable TLV, then this update is
ignored.
The next-hop address for this update is taken from the last preceding The next-hop address for this update is taken from the last preceding
Next Hop TLV with a matching address family (IPv4 or IPv6) in the Next Hop TLV with a matching address family (IPv4 or IPv6) in the
same packet even if it was otherwise ignored due to an unknown same packet even if it was otherwise ignored due to an unknown
mandatory sub-TLV; if no such TLV exists, it is taken from the mandatory sub-TLV; if no such TLV exists, it is taken from the
network-layer source address of this packet. network-layer source address of this packet if it belongs to the same
address family as the prefix being announced; otherwise, this Update
MUST be ignored.
If the metric field is FFFF hexadecimal, this TLV specifies a If the metric field is FFFF hexadecimal, this TLV specifies a
retraction. In that case, the router-id, next-hop and seqno are not retraction. In that case, the router-id, next-hop and seqno are not
used. AE MAY then be 0, in which case this Update retracts all of used. AE MAY then be 0, in which case this Update retracts all of
the routes previously advertised by the sending interface. If the the routes previously advertised by the sending interface. If the
metric is finite, AE MUST NOT be 0. If the metric is infinite and AE metric is finite, AE MUST NOT be 0; Update TLVs with finite metric
and AE equal to 0 MUST be ignored. If the metric is infinite and AE
is 0, Plen and Omitted MUST both be 0. is 0, Plen and Omitted MUST both be 0.
Update TLVs with an unknown value in the AE field MUST be silently Update TLVs with an unknown value in the AE field MUST be silently
ignored. ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.10. Route Request 4.6.10. Route Request
0 1 2 3 0 1 2 3
skipping to change at page 45, line 21 skipping to change at page 46, line 4
4.6.10. Route Request 4.6.10. Route Request
0 1 2 3 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 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 | | Type = 9 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix... | Prefix...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
A Route Request TLV prompts the receiver to send an update for a A Route Request TLV prompts the receiver to send an update for a
given prefix, or a full route table dump. given prefix, or a full route table dump.
Fields : Fields :
Type Set to 9 to indicate a Route Request TLV. Type Set to 9 to indicate a Route Request TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
AE The encoding of the Prefix field. The value 0 specifies AE The encoding of the Prefix field. The value 0 specifies
that this is a request for a full route table dump (a that this is a request for a full route table dump (a
wildcard request). wildcard request).
Plen The length of the requested prefix. Plen The length in bits of the requested prefix.
Prefix The prefix being requested. This field's size is Plen/8 Prefix The prefix being requested. This field's size is Plen/8
rounded upwards. rounded upwards.
A Request TLV prompts the receiver to send an update message A Request TLV prompts the receiver to send an update message
(possibly a retraction) for the prefix specified by the AE, Plen, and (possibly a retraction) for the prefix specified by the AE, Plen, and
Prefix fields, or a full dump of its route table if AE is 0 (in which Prefix fields, or a full dump of its route table if AE is 0 (in which
case Plen MUST be 0 and Prefix is of length 0). case Plen MUST be 0 and Prefix is of length 0).
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
skipping to change at page 46, line 29 skipping to change at page 47, line 7
+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+
A Seqno Request TLV prompts the receiver to send an Update for a 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 given prefix with a given sequence number, or to forward the request
further if it cannot be satisfied locally. further if it cannot be satisfied locally.
Fields : Fields :
Type Set to 10 to indicate a Seqno Request TLV. Type Set to 10 to indicate a Seqno Request TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body in octets, exclusive of the Type and
fields. Length fields.
AE The encoding of the Prefix field. This MUST NOT be 0. AE The encoding of the Prefix field. This MUST NOT be 0.
Plen The length of the requested prefix. Plen The length in bits of the requested prefix.
Seqno The sequence number that is being requested. Seqno The sequence number that is being requested.
Hop Count The maximum number of times that this TLV may be forwarded, Hop Count The maximum number of times that this TLV may be forwarded,
plus 1. This MUST NOT be 0. plus 1. This MUST NOT be 0.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Router-Id The Router-Id that is being requested. This MUST NOT Router-Id The Router-Id that is being requested. This MUST NOT
consist of all zeroes or all ones. consist of all zeroes or all ones.
skipping to change at page 47, line 43 skipping to change at page 48, line 22
0 1 2 3 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 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... | Type = 1 | Length | MBZ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields : Fields :
Type Set to 1 to indicate a PadN sub-TLV. Type Set to 1 to indicate a PadN sub-TLV.
Length The length of the body, in octets, exclusive of the Type Length The length of the body in octets, exclusive of the Type and
and Length fields. Length fields.
MBZ Must be zero, set to 0 on transmission. MBZ Must be zero, set to 0 on transmission.
This sub-TLV is silently ignored on reception. It is allowed within This sub-TLV is silently ignored on reception. It is allowed within
any TLV that allows sub-TLVs. any TLV that allows sub-TLVs.
5. IANA Considerations 5. IANA Considerations
IANA has registered the UDP port number 6696, called "babel", for use IANA has registered the UDP port number 6696, called "babel", for use
by the Babel protocol. by the Babel protocol.
IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4 IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4
multicast group 224.0.0.111 for use by the Babel protocol. multicast group 224.0.0.111 for use by the Babel protocol.
IANA has created a registry called "Babel TLV Types". The values in IANA has created a registry called "Babel TLV Types". The allocation
this registry are not changed by this specification. policy for this registry is Specification Required [RFC8126] for
Types 0-223, and Experimental Use for Types 224-254. The values in
IANA has created a registry called "Babel sub-TLV Types". Due to the this registry are as follows:
addition of a Mandatory bit to the Babel protocol, the values in the
"Babel sub-TLV Types" registry are amended as follows:
+---------+-----------------------------------------+---------------+ +---------+-----------------------------------------+---------------+
| Type | Name | Reference | | Type | Name | Reference |
+---------+-----------------------------------------+---------------+ +---------+-----------------------------------------+---------------+
| 0 | Pad1 | this document | | 0 | Pad1 | this document |
| | | | | | | |
| 1 | PadN | this document | | 1 | PadN | this document |
| | | | | | | |
| 112-126 | Reserved for Experimental Use | this document | | 2 | Acknowledgment Request | this document |
| | | | | | | |
| 127 | Reserved for expansion of the type | this document | | 3 | Acknowledgment | this document |
| | space | |
| | | | | | | |
| 240-254 | Reserved for Experimental Use | this document | | 4 | Hello | this document |
| | | |
| 5 | IHU | this document |
| | | |
| 6 | Router-Id | this document |
| | | |
| 7 | Next Hop | this document |
| | | |
| 8 | Update | this document |
| | | |
| 9 | Route Request | this document |
| | | |
| 10 | Seqno Request | this document |
| | | |
| 11 | TS/PC | [RFC7298] |
| | | |
| 12 | HMAC | [RFC7298] |
| | | |
| 13 | Source-specific Update | [BABEL-SS] |
| | | |
| 14 | Source-specific Request | [BABEL-SS] |
| | | |
| 15 | Source-specific Seqno Request | [BABEL-SS] |
| | | |
| 16 | HMAC | [BABEL-HMAC] |
| | | |
| 17 | PC | [BABEL-HMAC] |
| | | |
| 18 | Challenge Request | [BABEL-HMAC] |
| | | |
| 19 | Challenge Reply | [BABEL-HMAC] |
| | | |
| 20-223 | Unassigned | |
| | | |
| 224-254 | Reserved for Experimental Use | this document |
| | | | | | | |
| 255 | Reserved for expansion of the type | this document | | 255 | Reserved for expansion of the type | this document |
| | space | | | | space | |
+---------+-----------------------------------------+---------------+ +---------+-----------------------------------------+---------------+
Existing assignments in the "Babel sub-TLV Types" registry in the IANA has created a registry called "Babel TLV Types". The allocation
range 2 to 111 are not changed by this specification. The values 224 policy for this registry is Specification Required for Types 0-111
through 239, previously reserved for Experimental Use, are now and 128-239, and Experimental Use for Types 112-126 and 240-254. The
unassigned. values in this registry are as follows:
IANA has created a registry called "Babel Flags Values". IANA is +---------+-------------------------------------+-------------------+
instructed to rename this registry to "Babel Update Flags Values", | Type | Name | Reference |
with its contents unchanged. +---------+-------------------------------------+-------------------+
| 0 | Pad1 | this document |
| | | |
| 1 | PadN | this document |
| | | |
| 2 | Diversity | [BABEL-DIVERSITY] |
| | | |
| 3 | Timestamp | [BABEL-RTT] |
| | | |
| 4-111 | Unassigned | |
| | | |
| 112-126 | Reserved for Experimental Use | this document |
| | | |
| 127 | Reserved for expansion of the type | this document |
| | space | |
| | | |
| 128 | Source Prefix | [BABEL-SS] |
| | | |
| 129-239 | Unassigned | |
| | | |
| 240-254 | Reserved for Experimental Use | this document |
| | | |
| 255 | Reserved for expansion of the type | this document |
| | space | |
+---------+-------------------------------------+-------------------+
IANA has created a registry called "Babel Flags Values". The
allocation policy for this registry is Specification Required. IANA
is instructed to rename this registry to "Babel Update Flags Values".
The values in this registry are as follows:
+-----+-------------------+---------------+
| Bit | Name | Reference |
+-----+-------------------+---------------+
| 0 | Default prefix | this document |
| | | |
| 1 | Default Router-ID | this document |
| | | |
| 2-7 | Unassigned | |
+-----+-------------------+---------------+
IANA is instructed to create a new registry called "Babel Hello Flags IANA is instructed to create a new registry called "Babel Hello Flags
Values". The allocation policy for this registry is Specification Values". The allocation policy for this registry is Specification
Required [RFC8126]. The initial values in this registry are as Required. The initial values in this registry are as follows:
follows:
+------+------------+---------------+ +------+------------+---------------+
| Bit | Name | Reference | | Bit | Name | Reference |
+------+------------+---------------+ +------+------------+---------------+
| 0 | Unicast | this document | | 0 | Unicast | this document |
| | | | | | | |
| 1-15 | Unassigned | | | 1-15 | Unassigned | |
+------+------------+---------------+ +------+------------+---------------+
IANA is instructed to replace all references to RFCs 6126 and 7557 in IANA is instructed to replace all references to RFCs 6126 and 7557 in
all of the registries mentioned above by references to this document. all of the registries mentioned above by references to this document.
6. Security Considerations 6. Security Considerations
As defined in this document, Babel is a completely insecure protocol. As defined in this document, Babel is a completely insecure protocol.
Any attacker can misdirect data traffic by advertising routes with a Without additional security mechanisms, Babel trusts any information
low metric or a high seqno. This issue can be solved either by a it receives in plaintext UDP datagrams and acts on it. An attacker
lower-layer security mechanism (e.g., link-layer security or IPsec), that is present on the local network can impact Babel operation in a
or by deploying a suitable authentication mechanism within Babel variety of ways, for example they can:
itself. There are currently two such mechanisms: Babel over DTLS
[BABEL-DTLS] and HMAC-based authentication [BABEL-HMAC]. Both
mechanisms ensure integrity of messages and prevent message replay,
but only DTLS supports asymmetric keying and message confidentiality.
HMAC is simpler and does not depend on DTLS, and therefore its use is
RECOMMENDED whenever both mechanisms are applicable.
The information that a Babel node announces to the whole routing o spoof a Babel packet, and redirect traffic by announcing a route
domain is often sufficient to determine a mobile node's physical with a smaller metric, a larger sequence number, or a longer
location with reasonable precision. The privacy issues that this prefix;
causes can be mitigated somewhat by using randomly chosen router-ids
and randomly chosen IP addresses, and changing them periodically. o spoof a malformed packet, which could cause an insufficiently
robust implementation to crash or interfere with the rest of the
network;
o replay a previously captured Babel packet, which could cause
traffic to be redirected or otherwise interfere with the network.
When carried over IPv6, Babel packets are ignored unless they are When carried over IPv6, Babel packets are ignored unless they are
sent from a link-local IPv6 address; since routers don't forward sent from a link-local IPv6 address; since routers don't forward
link-local IPv6 packets, this provides protection against spoofed link-local IPv6 packets, this mitigates the attacks outlined above by
Babel packets being sent from the global Internet. No such natural restricting them to on-link attackers. No such natural protection
protection exists when Babel packets are carried over IPv4. exists when Babel packets are carried over IPv4.
These issues can be solved by providing a means for Babel to ensure
datagrams are fresh and originated from a trusted node. This can be
achieved either by a lower-layer security mechanism (e.g., link-layer
security or IPsec), or by deploying a suitable authentication
mechanism within Babel itself. There are currently two such
mechanisms:
o Babel over DTLS [BABEL-DTLS] runs the majority of Babel traffic
over DTLS, and leverages DTLS to authenticate nodes and provide
confidentiality and integrity protection;
o HMAC-based authentication [BABEL-HMAC] appends a message
authentication code to all Babel datagrams to prove they
originated from a node that possesses a shared secret.
Both mechanisms allow nodes to ignore packets generated by attackers
without the proper credentials. They also ensure integrity of
messages and prevent message replay. However, only DTLS supports
asymmetric keying and message confidentiality. HMAC is simpler and
does not depend on DTLS, and therefore its use is RECOMMENDED when
the target deployment does not require confidentiality or asymmetric
keying.
The information that a mobile 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 often
enough.
7. Acknowledgments 7. Acknowledgments
A number of people have contributed text and ideas to this A number of people have contributed text and ideas to this
specification. The authors are particularly indebted to Matthieu specification. The authors are particularly indebted to Matthieu
Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke
Hoiland-Jorgensen, Joao Sobrinho and Martin Vigoureux. Earlier Hoiland-Jorgensen, Joao Sobrinho and Martin Vigoureux. Earlier
versions of this document greatly benefited from the input of Joel versions of this document greatly benefited from the input of Joel
Halpern. The address compression technique was inspired by Halpern. The address compression technique was inspired by
[PACKETBB]. [PACKETBB].
8. References 8. References
8.1. Normative References 8.1. Normative References
[BABEL-HMAC]
Do, C., Kolodziejak, W., and J. Chroboczek, "HMAC
authentication for the Babel routing protocol", Internet
Draft draft-ietf-babel-hmac-07, June 2019.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997. DOI 10.17487/RFC2119, March 1997.
[RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for
Writing an IANA Considerations Section in RFCs", BCP 26,
RFC 8126, June 2017.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017. May 2017.
8.2. Informative References 8.2. Informative References
[BABEL-DIVERSITY]
Chroboczek, J., "Diversity Routing for the Babel Routing
Protocol", draft-chroboczek-babel-diversity-routing-01
(work in progress), February 2016.
[BABEL-DTLS] [BABEL-DTLS]
Decimo, A., Schinazi, D., and J. Chroboczek, "Babel Decimo, A., Schinazi, D., and J. Chroboczek, "Babel
Routing Protocol over Datagram Transport Layer Security", Routing Protocol over Datagram Transport Layer Security",
Internet Draft draft-ietf-babel-dtls-07, July 2019. Internet Draft draft-ietf-babel-dtls-07, July 2019.
[BABEL-HMAC] [BABEL-RTT]
Do, C., Kolodziejak, W., and J. Chroboczek, "HMAC Jonglez, B. and J. Chroboczek, "Delay-based Metric
authentication for the Babel routing protocol", Internet Extension for the Babel Routing Protocol", draft-ietf-
Draft draft-ietf-babel-hmac-07, June 2019. babel-rtt-extension-00 (work in progress), April 2019.
[BABEL-SS]
Boutier, M. and J. Chroboczek, "Source-Specific Routing in
Babel", draft-ietf-babel-source-specific-05 (work in
progress), April 2019.
[DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-
Sequenced Distance-Vector Routing (DSDV) for Mobile Sequenced Distance-Vector Routing (DSDV) for Mobile
Computers", ACM SIGCOMM'94 Conference on Communications Computers", ACM SIGCOMM'94 Conference on Communications
Architectures, Protocols and Applications 234-244, 1994. Architectures, Protocols and Applications 234-244, 1994.
[DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing
Computations", IEEE/ACM Transactions on Networking 1:1, Computations", IEEE/ACM Transactions on Networking 1:1,
February 1993. February 1993.
skipping to change at page 51, line 16 skipping to change at page 54, line 23
periodic routing messages", IEEE/ACM Transactions on periodic routing messages", IEEE/ACM Transactions on
Networking 2, 2, 122-136, April 1994. Networking 2, 2, 122-136, April 1994.
[OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998.
[PACKETBB] [PACKETBB]
Clausen, T., Dearlove, C., Dean, J., and C. Adjih, Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009. Format", RFC 5444, February 2009.
[RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Writing an IANA Considerations Section in RFCs", BCP 26, Demand Distance Vector (AODV) Routing", RFC 3561,
RFC 8126, June 2017. DOI 10.17487/RFC3561, July 2003,
<https://www.rfc-editor.org/info/rfc3561>.
[RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126,
DOI 10.17487/RFC6126, April 2011.
[RFC7298] Ovsienko, D., "Babel Hashed Message Authentication Code
(HMAC) Cryptographic Authentication", RFC 7298,
DOI 10.17487/RFC7298, July 2014.
[RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing
Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015.
[RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998.
Appendix A. Cost and Metric Computation Appendix A. Cost and Metric Computation
The strategy for computing link costs and route metrics is a local The strategy for computing link costs and route metrics is a local
matter; Babel itself only requires that it comply with the conditions matter; Babel itself only requires that it comply with the conditions
given in Section 3.4.3 and Section 3.5.2. Different nodes may use given in Section 3.4.3 and Section 3.5.2. Different nodes may use
different strategies in a single network and may use different different strategies in a single network and may use different
strategies on different interface types. This section describes the strategies on different interface types. This section describes a
strategies used by the sample implementation of Babel. set of stragies that have been found to work well in actual networks.
The sample implementation of Babel sends periodic Multicast Hellos, In summary, a node maintains per-neighbour statistics about the last
and never sends Unicast Hellos. It maintains statistics about the 16 received Hello TLVs of each kind (Appendix A.1), it computes costs
last 16 received Hello TLVs of each kind (Appendix A.1), computes by using the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and
costs by using the 2-out-of-3 strategy (Appendix A.2.1) on wired ETX (Appendix A.2.2) on wireless links. It uses an additive algebra
links, and ETX (Appendix A.2.2) on wireless links. It uses an for metric computation (Appendix A.3.1).
additive algebra for metric computation (Appendix A.3.1).
A.1. Maintaining Hello History A.1. Maintaining Hello History
For each neighbour, the sample implementation of Babel maintains two For each neighbour, a node maintains two sets of Hello history, one
sets of Hello history, one for each kind of Hello, and an expected for each kind of Hello, and an expected sequence number, one for
sequence number, one for Multicast and one for Unicast Hellos. Each Multicast and one for Unicast Hellos. Each Hello history is a vector
Hello history is a vector of 16 bits, where a 1 value represents a of 16 bits, where a 1 value represents a received Hello, and a 0
received Hello, and a 0 value a missed Hello. For each kind of value a missed Hello. For each kind of Hello, the expected sequence
Hello, the expected sequence number, written ne, is the sequence number, written ne, is the sequence number that is expected to be
number that is expected to be carried by the next received Hello from carried by the next received Hello from this neighbour.
this neighbour.
Whenever it receives a Hello packet of a given kind from a neighbour, Whenever it receives a Hello packet of a given kind from a neighbour,
a node compares the received sequence number nr for that kind of a node compares the received sequence number nr for that kind of
Hello with its expected sequence number ne. Depending on the outcome Hello with its expected sequence number ne. Depending on the outcome
of this comparison, one of the following actions is taken: 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 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 whole node has probably rebooted and lost its sequence number; the whole
associated neighbour table entry is flushed and a new one is associated neighbour table entry is flushed and a new one is
created; created;
skipping to change at page 52, line 28 skipping to change at page 55, line 45
the receiving node adds (nr - ne) 0 bits to the Hello history (we the receiving node adds (nr - ne) 0 bits to the Hello history (we
"fast-forward"). "fast-forward").
The receiving node then appends a 1 bit to the Hello history and sets The receiving node then appends a 1 bit to the Hello history and sets
ne to (nr + 1). If the Interval field of the received Hello is not ne to (nr + 1). If the Interval field of the received Hello is not
zero, it resets the neighbour's hello timer to 1.5 times the zero, it resets the neighbour's hello timer to 1.5 times the
advertised Interval (the extra margin allows for delay due to advertised Interval (the extra margin allows for delay due to
jitter). jitter).
Whenever either Hello timer associated to a neighbour expires, the Whenever either Hello timer associated to a neighbour expires, the
local node adds a 0 bit to this neighbour's Hello history, and local node adds a 0 bit to the corresponding Hello history, and
increments the expected Hello number. If both Hello histories are increments the expected Hello number. If both Hello histories are
empty (they contain 0 bits only), the neighbour entry is flushed; empty (they contain 0 bits only), the neighbour entry is flushed;
otherwise, the relevant hello timer is reset to the value advertised otherwise, the relevant hello timer is reset to the value advertised
in the last Hello of that kind received from this neighbour (no extra in the last Hello of that kind received from this neighbour (no extra
margin is necessary in this case, since jitter was already taken into margin is necessary in this case, since jitter was already taken into
account when computing the timeout that has just expired). account when computing the timeout that has just expired).
A.2. Cost Computation A.2. Cost Computation
This section discusses how to compute costs based on Hello history. This section discusses how to compute costs based on Hello history.
skipping to change at page 53, line 24 skipping to change at page 56, line 41
The cost of a link performing k-out-of-j link sensing is defined as The cost of a link performing k-out-of-j link sensing is defined as
follows: follows:
o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;
o cost = txcost otherwise. o cost = txcost otherwise.
A.2.2. ETX A.2.2. ETX
Unlike wired links, which are bimodal (either up or down), wireless Unlike wired links which are bimodal (either up or down), wireless
links exhibit continuous variation of the link quality. Naive links exhibit continuous variation of the link quality. Naive
application of hop-count routing in networks that use wireless links application of hop-count routing in networks that use wireless links
for transit tends to select long, lossy links in preference to for transit tends to select long, lossy links in preference to
shorter, lossless links, which can dramatically reduce throughput. shorter, lossless links, which can dramatically reduce throughput.
For that reason, a routing protocol designed to support wireless For that reason, a routing protocol designed to support wireless
links must perform some form of link-quality estimation. links must perform some form of link-quality estimation.
ETX [ETX] is a simple link-quality estimation algorithm that is ETX [ETX] is a simple link-quality estimation algorithm that is
designed to work well with the IEEE 802.11 MAC. By default, the designed to work well with the IEEE 802.11 MAC. By default, the
IEEE 802.11 MAC performs ARQ and rate adaptation on unicast frames, IEEE 802.11 MAC performs ARQ and rate adaptation on unicast frames,
but not on multicast frames, which are sent at a fixed rate with no but not on multicast frames, which are sent at a fixed rate with no
ARQ; therefore, measuring the loss rate of multicast frames yields a ARQ; therefore, measuring the loss rate of multicast frames yields a
useful estimate of a link's quality. useful estimate of a link's quality.
A node performing ETX link quality estimation uses a neighbour's A node performing ETX link quality estimation uses a neighbour's
Multicast Hello history to compute an estimate, written beta, of the Multicast Hello history to compute an estimate, written beta, of the
probability that a Hello TLV is successfully received. Beta can be probability that a Hello TLV is successfully received. Beta can be
computed as the fraction of 1 bits within a small number (say, 6) of computed as the fraction of 1 bits within a small number (say, 6) of
the most recent entries in the Multicast Hello history, or it can be the most recent entries in the Multicast Hello history, or it can be
an exponential average, or some combination of both approaches. an exponential average, or some combination of both approaches. Let
rxcost be 256 / beta.
Let alpha be MIN(1, 256/txcost), an estimate of the probability of Let alpha be MIN(1, 256/txcost), an estimate of the probability of
successfully sending a Hello TLV. The cost is then computed by successfully sending a Hello TLV. The cost is then computed by
cost = 256/(alpha * beta) cost = 256/(alpha * beta)
or, equivalently, or, equivalently,
cost = (MAX(txcost, 256) * rxcost) / 256. cost = (MAX(txcost, 256) * rxcost) / 256.
Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast
frames do not provide a useful measure of link quality, and therefore frames do not provide a useful measure of link quality, and therefore
ETX ignores the Unicast Hello history. Thus, a node performing ETX ETX ignores the Unicast Hello history. Thus, a node performing ETX
link-quality estimation will not route through neighbouring nodes link-quality estimation will not route through neighbouring nodes
unless they send periodic Multicast Hellos (possibly in addition to unless they send periodic Multicast Hellos (possibly in addition to
Unicast Hellos). Unicast Hellos).
A.3. Metric Computation A.3. Metric Computation
skipping to change at page 54, line 46 skipping to change at page 58, line 16
node receives an update with metric m over a link with cost c, it 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 might compute a metric M(c, m) = k + c + m, where k depends on the
battery status. battery status.
In order to preserve strict monotonicity (Section 3.5.2), the value k In order to preserve strict monotonicity (Section 3.5.2), the value k
must be greater than -c. must be greater than -c.
Appendix B. Constants Appendix B. Constants
The choice of time constants is a trade-off between fast detection of The choice of time constants is a trade-off between fast detection of
mobility events and protocol overhead. Two implementations of Babel mobility events and protocol overhead. Two instances of Babel
with different time constants will interoperate, although the running with different time constants will interoperate, although the
resulting convergence time will most likely be dictated by the slower resulting worst-case convergence time will be dictated by the slower
of the two. of the two.
Experience with the sample implementation of Babel indicates that the The Hello interval is the most important time constant: an outage or
Hello interval is the most important time constant: a mobility event a mobility event is detected within 1.5 to 3.5 Hello intervals. Due
is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance to Babel's use of a redundant route table, and due to its reliance on
on triggered updates and explicit requests, the Update interval only triggered updates and explicit requests, the Update interval has
has an effect on the time it takes for accurate metrics to be little influence on the time needed to reconverge after an outage: in
propagated after variations in link costs too small to trigger an practice, it only has a significant effect on the time needed to
unscheduled update or in the presence of packet loss. acquire new routes after a mobility event.
At the time of writing, the sample implementation of Babel uses the The following values are recommended in a network with little
following default values: mobility, and where occasional outages of up to 14 seconds are
acceptable:
Multicast Hello Interval: 4 seconds. Multicast Hello Interval: 4 seconds.
Unicast Hello Interval: infinite (no Unicast Hellos are sent).
IHU Interval: the advertised IHU interval is always 3 times the IHU Interval: the advertised IHU interval is always 3 times the
Multicast Hello interval. IHUs are actually sent with each Hello Multicast Hello interval. IHUs are actually sent with each Hello
on lossy links (as determined from the Hello history), but only on lossy links (as determined from the Hello history), but only
with every third Multicast Hello on lossless links. with every third Multicast Hello on lossless links.
Unicast Hello Interval: the sample implementation never sends
scheduled Unicast Hellos;
Update Interval: 4 times the Multicast Hello interval. Update Interval: 4 times the Multicast Hello interval.
IHU Hold Time: 3.5 times the advertised IHU interval. IHU Hold Time: 3.5 times the advertised IHU interval.
Route Expiry Time: 3.5 times the advertised update interval. Route Expiry Time: 3.5 times the advertised update interval.
Source GC time: 3 minutes.
Request timeout: initially 2 seconds, doubled every time a request Request timeout: initially 2 seconds, doubled every time a request
is resent, up to a maximum of three times. is resent, up to a maximum of three times.
The amount of jitter applied to a packet depends on whether it Urgent timeout: 0.2 seconds.
contains any urgent TLVs or not (Section 3.1). Urgent triggered
updates and urgent requests are delayed by no more than 200ms;
acknowledgments, by no more than the associated deadline; and other
TLVs by no more than one-half the Multicast Hello interval.
Appendix C. Considerations for protocol extensions Source GC time: 3 minutes.
The following values are recommended in a network where reconvergence
within 2 seconds after a mobility event is desired:
Multicast Hello Interval: 0.5 seconds.
Unicast Hello Interval: infinite (no Unicast Hellos are sent).
IHU Interval, Update Interval, IHU Hold Time, and Route Expiry
Time: computed as in the first case above.
Request Timeout: initially 0.5 seconds, doubled every time a
request is resent, up to a maximum of three times.
Urgent timeout: 0.2 seconds.
Source GC time: 3 minutes.
Appendix C. Route filtering
Route filtering is a procedure where an instance of a routing
protocol either discards some of the routes announced by its
neighbours, or learns them with a metric that is higher than what
would be expected. Like all distance-vector protocols, Babel has the
ability to apply arbitrary filtering to the routes it learns, and
implementations of Babel that apply different sets of filtering rules
will interoperate without causing routing loops. The protocol's
ability to perform route filtering is a consequence of the latitude
given in Section 3.5.2: Babel can use any metric that is strictly
monotonic, including one that assigns an infinite metric to a
selected subset of routes. (See also Section 3.8.1, where requests
for nonexistent routes are treated in the same way as requests for
routes with infinite metric.)
It is not in general correct to learn a route with a metric smaller
than the one it was announced with, or to replace a route's
destination prefix with a more specific (longer) one. Doing either
of these may cause persistent routing loops.
Route filtering is a useful tool, since it allows fine-grained tuning
of the routing decisions made by the routing protocol. Accordingly,
some implementations of Babel implement a rich configuration language
that allows applying filtering to sets of routes defined, for
example, by incoming interface and destination prefix.
In order to limit the consequences of misconfiguration, Babel
implementations provide a reasonable set of default filtering rules
even when they don't allow configuration of filtering by the user.
At a minimum, they discard routes with a destination prefix in
fe80::/64, ff00::/8, 127.0.0.1/32, 0.0.0.0/32 and 224.0.0.0/8.
Appendix D. Considerations for protocol extensions
Babel is an extensible protocol, and this document defines a number Babel is an extensible protocol, and this document defines a number
of mechanisms that can be used to extend the protocol in a backwards of mechanisms that can be used to extend the protocol in a backwards
compatible manner: compatible manner:
o increasing the version number in the packet header; o increasing the version number in the packet header;
o defining new TLVs; o defining new TLVs;
o defining new sub-TLVs (with or without the mandatory bit set); o defining new sub-TLVs (with or without the mandatory bit set);
o defining new AEs; o defining new AEs;
o using the packet trailer. o using the packet trailer.
This appendix is intended to guide designers of protocol extensions This appendix is intended to guide designers of protocol extensions
in chosing a particular encoding. in chosing a particular encoding.
The version number in the Babel header should only be increased if The version number in the Babel header should only be increased if
skipping to change at page 57, line 17 skipping to change at page 61, line 32
The packet trailer is intended to carry cryptographic signatures that The packet trailer is intended to carry cryptographic signatures that
only cover the packet body; storing the cryptographic signatures in only cover the packet body; storing the cryptographic signatures in
the packet trailer avoids clearing the signature before computing a the packet trailer avoids clearing the signature before computing a
hash of the packet body, and makes it possible to check a hash of the packet body, and makes it possible to check a
cryptographic signature before running the full, stateful TLV parser. cryptographic signature before running the full, stateful TLV parser.
Hence, only TLVs that don't need to be protected by cryptographic Hence, only TLVs that don't need to be protected by cryptographic
security protocols should be allowed in the packet trailer. Any such security protocols should be allowed in the packet trailer. Any such
TLVs should be easy to parse, and in particular should not require TLVs should be easy to parse, and in particular should not require
stateful parsing. stateful parsing.
Appendix D. Stub Implementations Appendix E. Stub Implementations
Babel is a fairly economic protocol. Updates take between 12 and 40 Babel is a fairly economic protocol. Updates take between 12 and 40
octets per destination, depending on the address family and how octets per destination, depending on the address family and how
successful compression is; in a double-stack flat network, an average successful compression is; in a double-stack flat network, an average
of less than 24 octets per update is typical. The route table of less than 24 octets per update is typical. The route table
occupies about 35 octets per IPv6 entry. To put these values into occupies about 35 octets per IPv6 entry. To put these values into
perspective, a single full-size Ethernet frame can carry some 65 perspective, a single full-size Ethernet frame can carry some 65
route updates, and a megabyte of memory can contain a 20000-entry route updates, and a megabyte of memory can contain a 20000-entry
route table and the associated source table. route table and the associated source table.
Babel is also a reasonably simple protocol. The sample Babel is also a reasonably simple protocol. One complete
implementation consists of less than 12 000 lines of C code, and it implementation consists of less than 12 000 lines of C code, and it
compiles to less than 120 kB of text on a 32-bit CISC architecture; compiles to less than 120 kB of text on a 32-bit CISC architecture;
about half of this figure is due to protocol extensions and user- about half of this figure is due to protocol extensions and user-
interface code. interface code.
Nonetheless, in some very constrained environments, such as PDAs, Nonetheless, in some very constrained environments, such as PDAs,
microwave ovens, or abacuses, it may be desirable to have subset microwave ovens, or abacuses, it may be desirable to have subset
implementations of the protocol. implementations of the protocol.
There are many different definitions of a stub router, but for the There are many different definitions of a stub router, but for the
needs of this section a stub implementation of Babel is one that needs of this section a stub implementation of Babel is one that
announces one or more directly attached prefixes into a Babel network announces one or more directly attached prefixes into a Babel network
but doesn't reannounce any routes that it has learnt from its but doesn't reannounce any routes that it has learnt from its
neighbours. It may either maintain a full routing table, or simply neighbours, and always prefers the direct route to a directly
select a default gateway amongst any one of its neighbours that attached prefix to a route learned over the Babel protocol, even when
announces a default route. Since a stub implementation never the prefixes are the same. It may either maintain a full routing
forwards packets except from or to directly attached links, it cannot table, or simply select a default gateway through any one of its
possibly participate in a routing loop, and hence it need not neighbours that announces a default route. Since a stub
evaluate the feasibility condition or maintain a source table. implementation never forwards packets except from or to a directly
attached link, it cannot possibly participate in a routing loop, and
hence it need not evaluate the feasibility condition or maintain a
source table.
No matter how primitive, a stub implementation MUST parse sub-TLVs No matter how primitive, a stub implementation must parse sub-TLVs
attached to any TLVs that it understands and check the mandatory bit. attached to any TLVs that it understands and check the mandatory bit.
It MUST answer acknowledgment requests and MUST participate in the It must answer acknowledgment requests and must participate in the
Hello/IHU protocol. It MUST also be able to reply to seqno requests Hello/IHU protocol. It must also be able to reply to seqno requests
for routes that it announces and SHOULD be able to reply to route for routes that it announces and, and it should be able to reply to
requests. route requests.
Experience shows that an IPv6-only stub implementation of Babel can Experience shows that an IPv6-only stub implementation of Babel can
be written in less than 1000 lines of C code and compile to 13 kB of be written in less than 1000 lines of C code and compile to 13 kB of
text on 32-bit CISC architecture. text on 32-bit CISC architecture.
Appendix E. Software Availability
The sample implementation of Babel is available from
<https://www.irif.fr/~jch/software/babel/>.
Appendix F. Changes from previous versions Appendix F. Changes from previous versions
F.1. Changes since RFC 6126 F.1. Changes since RFC 6126
o Changed UDP port number to 6696. o Changed UDP port number to 6696.
o Consistently use router-id rather than id. o Consistently use router-id rather than id.
o Clarified that the source garbage collection timer is reset after o Clarified that the source garbage collection timer is reset after
sending an update even if the entry was not modified. sending an update even if the entry was not modified.
skipping to change at page 58, line 45 skipping to change at page 63, line 11
F.2. Changes since draft-ietf-babel-rfc6126bis-00 F.2. Changes since draft-ietf-babel-rfc6126bis-00
o Added security considerations. o Added security considerations.
F.3. Changes since draft-ietf-babel-rfc6126bis-01 F.3. Changes since draft-ietf-babel-rfc6126bis-01
o Integrated the format of sub-TLVs. o Integrated the format of sub-TLVs.
o Mentioned for each TLV whether it supports sub-TLVs. o Mentioned for each TLV whether it supports sub-TLVs.
o Added Appendix C. o Added Appendix D.
o Added a mandatory bit in sub-TLVs. o Added a mandatory bit in sub-TLVs.
o Changed compression state to be per-AF rather than per-AE. o Changed compression state to be per-AF rather than per-AE.
o Added implementation hint for the routing table. o Added implementation hint for the routing table.
o Clarified how router-ids are computed when bit 0x40 is set in o Clarified how router-ids are computed when bit 0x40 is set in
Updates. Updates.
skipping to change at page 61, line 18 skipping to change at page 65, line 38
F.13. Changes since draft-ietf-babel-rfc6126bis-10 F.13. Changes since draft-ietf-babel-rfc6126bis-10
o Editorial changes only. o Editorial changes only.
F.14. Changes since draft-ietf-babel-rfc6126bis-11 F.14. Changes since draft-ietf-babel-rfc6126bis-11
o Added recommendation that control traffic should be carried over o Added recommendation that control traffic should be carried over
IPv6 only. IPv6 only.
F.15. Changes since draft-ietf-babel-rfc6126bis-12
o Removed appendix about software availability.
o Expanded appendix about recommended values and added more
references to it in the body of the document.
o Added appendix about route filtering.
o Clarified definition of mandatory bit.
o Added recommendations for packet pacing.
o Made time limiting of full updates a SHOULD.
o Normative language in a few more places.
o Removed normative language from stub implementations.
o Added requirement to clear the undefined bits in an Update.
o Added error checking requirements.
o Reworked security considerations.
o Added "in octets" and "in bits" in random places.
o Inserted full IANA registries.
o Editorial changes.
Authors' Addresses Authors' Addresses
Juliusz Chroboczek Juliusz Chroboczek
IRIF, University of Paris-Diderot IRIF, University of Paris-Diderot
Case 7014 Case 7014
75205 Paris Cedex 13 75205 Paris Cedex 13
France France
Email: jch@irif.fr Email: jch@irif.fr
 End of changes. 126 change blocks. 
357 lines changed or deleted 584 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/