draft-ietf-babel-rfc6126bis-20.txt   rfc8966.txt 
Network Working Group J. Chroboczek Internet Engineering Task Force (IETF) J. Chroboczek
Internet-Draft IRIF, University of Paris-Diderot Request for Comments: 8966 IRIF, University of Paris-Diderot
Obsoletes: 6126,7557 (if approved) D. Schinazi Obsoletes: 6126, 7557 D. Schinazi
Intended status: Standards Track Google LLC Category: Standards Track Google LLC
Expires: February 26, 2021 August 25, 2020 ISSN: 2070-1721 January 2021
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-20
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 RFC 6126 and RFC 7557.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This is an Internet Standards Track document.
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Engineering Task Force
and may be updated, replaced, or obsoleted by other documents at any (IETF). It represents the consensus of the IETF community. It has
time. It is inappropriate to use Internet-Drafts as reference received public review and has been approved for publication by the
material or to cite them other than as "work in progress." Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 7841.
This Internet-Draft will expire on February 26, 2021. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfc-editor.org/info/rfc8966.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2021 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
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction
1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Features
1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Limitations
1.3. Specification of Requirements . . . . . . . . . . . . . . 5 1.3. Specification of Requirements
2. Conceptual Description of the Protocol . . . . . . . . . . . 5 2. Conceptual Description of the Protocol
2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 2.1. Costs, Metrics, and Neighbourship
2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 6 2.2. The Bellman-Ford Algorithm
2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 2.3. Transient Loops in Bellman-Ford
2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 7 2.4. Feasibility Conditions
2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 2.5. Solving Starvation: Sequencing Routes
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10 2.6. Requests
2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 11 2.7. Multiple Routers
2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 12 2.8. Overlapping Prefixes
3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12 3. Protocol Operation
3.1. Message Transmission and Reception . . . . . . . . . . . 12 3.1. Message Transmission and Reception
3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 13 3.2. Data Structures
3.3. Acknowledgments and acknowledgment requests . . . . . . . 17 3.3. Acknowledgments and Acknowledgment Requests
3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 18 3.4. Neighbour Acquisition
3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 21 3.5. Routing Table Maintenance
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 25 3.6. Route Selection
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 26 3.7. Sending Updates
3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28 3.8. Explicit Requests
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 32 4. Protocol Encoding
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32 4.1. Data Types
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33 4.2. Packet Format
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34 4.3. TLV Format
4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 35 4.4. Sub-TLV Format
4.5. Parser state and encoding of updates . . . . . . . . . . 36 4.5. Parser State and Encoding of Updates
4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 37 4.6. Details of Specific TLVs
4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 48 4.7. Details of specific sub-TLVs
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 49 5. IANA Considerations
6. Security Considerations . . . . . . . . . . . . . . . . . . . 52 6. Security Considerations
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 53 7. References
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.1. Normative References
8.1. Normative References . . . . . . . . . . . . . . . . . . 53 7.2. Informative References
8.2. Informative References . . . . . . . . . . . . . . . . . 54 Appendix A. Cost and Metric Computation
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 56 A.1. Maintaining Hello History
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 56 A.2. Cost Computation
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 57 A.3. Route Selection and Hysteresis
A.3. Route selection and hysteresis . . . . . . . . . . . . . 59 Appendix B. Protocol Parameters
Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 60 Appendix C. Route Filtering
Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 61 Appendix D. Considerations for Protocol Extensions
Appendix D. Considerations for protocol extensions . . . . . . . 61 Appendix E. Stub Implementations
Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 63 Appendix F. Compatibility with Previous Versions
Appendix F. Compatibility with previous versions . . . . . . . . 64 Acknowledgments
Appendix G. Changes from previous versions . . . . . . . . . . . 65 Authors' Addresses
G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 65
G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 65
G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 65
G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 66
G.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 66
G.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 67
G.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 67
G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 67
G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 67
G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 67
G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 67
G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 68
G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 68
G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 68
G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 68
G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 69
G.17. Changes since draft-ietf-babel-rfc6126bis-14 . . . . . . 69
G.18. Changes since draft-ietf-babel-rfc6126bis-15 . . . . . . 69
G.19. Changes since draft-ietf-babel-rfc6126bis-16 . . . . . . 69
G.20. Changes since draft-ietf-babel-rfc6126bis-17 . . . . . . 69
G.21. Changes since draft-ietf-babel-rfc6126bis-18 . . . . . . 70
G.22. Changes since draft-ietf-babel-rfc6126bis-19 . . . . . . 70
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 70
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. This document describes the Babel routing wireless networks. This document describes the Babel routing
protocol, and obsoletes [RFC6126] and [RFC7557]. 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
not necessarily optimal; in many cases, this operation requires no not necessarily optimal; in many cases, this operation requires no
packet exchanges at all. Babel then slowly converges, in a time on packet exchanges at all. Babel then slowly converges, in a time on
the scale of minutes, to an optimal configuration. This is achieved the scale of minutes, to an optimal configuration. This is achieved
by using sequenced routes, a technique pioneered by Destination- by using sequenced routes, a technique pioneered by Destination-
Sequenced Distance-Vector routing [DSDV]. Sequenced Distance-Vector routing [DSDV].
More precisely, Babel has the following properties: More precisely, Babel has the following properties:
o when every prefix is originated by at most one router, Babel never * when every prefix is originated by at most one router, Babel never
suffers from routing loops; suffers from routing loops;
o when a single prefix is originated by multiple routers, Babel may * when a single prefix is originated by multiple routers, Babel may
occasionally create a transient routing loop for this particular occasionally create a transient routing loop for this particular
prefix; this loop disappears in time proportional to the loop's prefix; this loop disappears in time proportional to the loop's
diameter, and never again (up to an arbitrary garbage-collection diameter, and never again (up to an arbitrary garbage-collection
(GC) time) will the routers involved participate in a routing loop (GC) time) will the routers involved participate in a routing loop
for the same prefix; for the same prefix;
o assuming bounded packet loss rates, any routing black-holes that * assuming bounded packet loss rates, any routing black-holes that
may appear after a mobility event are corrected in a time at most may appear after a mobility event are corrected in a time at most
proportional to the network's diameter. proportional to the network's diameter.
Babel has provisions for link quality estimation and for fairly Babel has provisions for link quality estimation and for fairly
arbitrary metrics. When configured suitably, Babel can implement arbitrary metrics. When configured suitably, Babel can implement
shortest-path routing, or it may use a metric based, for example, on shortest-path routing, or it may use a metric based, for example, on
measured packet loss. measured packet loss.
Babel nodes will successfully establish an association even when they Babel nodes will successfully establish an association even when they
are configured with different parameters. For example, a mobile node are configured with different parameters. For example, a mobile node
skipping to change at page 5, line 16 skipping to change at line 179
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.4 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
14 [RFC2119] [RFC8174] when, and only when, they appear in all BCP 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 algorithm, 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
For every pair of neighbouring nodes A and B, Babel computes an For every pair of neighbouring nodes A and B, Babel computes an
abstract value known as the cost of the link from A to B, written abstract value known as the cost of the link from A to B, written
C(A, B). Given a route between any two (not necessarily C(A, B). Given a route between any two (not necessarily
neighbouring) nodes, the metric of the route is the sum of the costs neighbouring) nodes, the metric of the route is the sum of the costs
of all the links along the route. The goal of the routing algorithm of all the links along the route. The goal of the routing algorithm
is to compute, for every source S, the tree of routes of lowest is to compute, for every source S, the tree of routes of lowest
metric to S. metric to S.
Costs and metrics need not be integers. In general, they can be Costs and metrics need not be integers. In general, they can be
skipping to change at page 7, line 40 skipping to change at line 295
as the "feasibility condition", that guarantees the absence of as the "feasibility condition", that guarantees the absence of
routing loops whenever all routers ignore route updates that do not routing loops whenever all routers ignore route updates that do not
satisfy the feasibility condition. In effect, this makes Bellman- satisfy the feasibility condition. In effect, this makes Bellman-
Ford into a family of routing algorithms, parameterised by the Ford into a family of routing algorithms, parameterised by the
feasibility condition. feasibility condition.
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 [RFC3561], stems Ad hoc On-Demand Distance Vector (AODV) protocol [RFC3561], stems
from the following observation: a routing loop can only arise after a from the following observation: a routing loop can only arise after a
router has switched to a route with a larger metric than the route router has switched to a route with a larger metric than the route
that it had previously selected. Hence, one may define that a route that it had previously selected. Hence, one may define that a route
is feasible when its metric at the local node would be no larger than is feasible when its metric at the local node would be no larger than
the metric of the currently selected route, i.e., an announcement the metric of the currently selected route, i.e., an announcement
skipping to change at page 8, line 41 skipping to change at line 345
/ \ / \
S A S A
\ / \ /
1 \ / 4 1 \ / 4
C C
To show that this feasibility condition still guarantees loop- To show that this feasibility condition still guarantees loop-
freedom, recall that at the time when A accepts an update from B, the freedom, recall that at the time when A accepts an update from B, the
metric D(B) announced by B is no smaller than FD(B); since it is metric D(B) announced by B is no smaller than FD(B); since it is
smaller than FD(A), at that point in time FD(B) < FD(A). Since this smaller than FD(A), at that point in time FD(B) < FD(A). Since this
property is preserved both when A sends updates and when it picks a property is preserved when A sends updates and also when it picks a
different next hop, it remains true at all times, which ensures that different next hop, it remains true at all times, which ensures that
the forwarding graph has no loops. the forwarding graph has no loops.
2.5. Solving Starvation: Sequencing Routes 2.5. Solving Starvation: Sequencing Routes
Obviously, the feasibility conditions defined above cause starvation Obviously, the feasibility conditions defined above cause starvation
when a router runs out of feasible routes. Consider the following when a router runs out of feasible routes. Consider the following
diagram, where both A and B have selected the direct route to S: diagram, where both A and B have selected the direct route to S:
A A
skipping to change at page 10, line 23 skipping to change at line 421
2 \| FD(B) = (138, 2) 2 \| FD(B) = (138, 2)
B B
at which point the route through B becomes feasible again. at which point the route through B becomes feasible again.
Note that while sequence numbers are used for determining Note that while sequence numbers are used for determining
feasibility, they are not used in route selection: a node ignores the feasibility, they are not used in route selection: a node ignores the
sequence number when selecting the best route to a given destination sequence number when selecting the best route to a given destination
(Section 3.6). Doing otherwise would cause route oscillation while a (Section 3.6). Doing otherwise would cause route oscillation while a
sequence number propagates through the network, and might even cause sequence number propagates through the network, and might even cause
persistent blackholes with some exotic metrics. persistent black-holes with some exotic metrics.
2.6. Requests 2.6. Requests
In DSDV, the sequence number of a source is increased periodically. In DSDV, the sequence number of a source is increased periodically.
A route becomes feasible again after the source increases its A route becomes feasible again after the source increases its
sequence number, and the new sequence number is propagated through sequence number, and the new sequence number is propagated through
the network, which may, in general, require a significant amount of the network, which may, in general, require a significant amount of
time. time.
Babel takes a different approach. When a node detects that it is Babel takes a different approach. When a node detects that it is
skipping to change at page 12, line 40 skipping to change at line 533
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.)
3.1. Message Transmission and Reception 3.1. Message Transmission and Reception
Babel protocol packets are sent in the body of a UDP datagram (as Babel protocol packets are sent in the body of a UDP datagram (as
described in Section 4 below). Each Babel packet consists of zero or described in Section 4). Each Babel packet consists of zero or more
more TLVs. Most TLVs may contain sub-TLVs. TLVs. Most TLVs may contain sub-TLVs.
The protocol's control traffic can be carried indifferently over IPv6 Babel's control traffic can be carried indifferently over IPv6 or
or over IPv4, and prefixes of either address family can be announced over IPv4, and prefixes of either address family can be announced
over either protocol. Thus, there are at least two natural over either protocol. Thus, there are at least two natural
deployment models: using IPv6 exclusively for all control traffic, or deployment models: using IPv6 exclusively for all control traffic, or
running two distinct protocol instances, one for each address family. running two distinct protocol instances, one for each address family.
The exclusive use of IPv6 for all control traffic is RECOMMENDED, The exclusive use of IPv6 for all control traffic is RECOMMENDED,
since using both protocols at the same time doubles the amount of since using both protocols at the same time doubles the amount of
traffic devoted to neighbour discovery and link quality estimation. traffic devoted to neighbour discovery and link quality estimation.
The source address of a Babel packet is always a unicast address, The source address of a Babel packet is always a unicast address,
link-local in the case of IPv6. Babel packets may be sent to a well- link-local in the case of IPv6. Babel packets may be sent to a well-
known (link-local) multicast address or to a (link-local) unicast known (link-local) multicast address or to a (link-local) unicast
skipping to change at page 13, line 26 skipping to change at line 566
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 random speaker: outgoing TLVs are buffered and SHOULD be sent with a random
delay. This is done for two purposes: it avoids synchronisation of delay. This is done for two purposes: it avoids synchronisation of
multiple Babel speakers across a network [JITTER], and it allows for multiple Babel speakers across a network [JITTER], and it allows for
the aggregation of multiple TLVs into a single packet. the aggregation of multiple TLVs into a single packet.
The maximum amount of delay a TLV can be subjected to depends on the The maximum amount of delay a TLV can be subjected to depends on the
TLV. When the protocol description specifies that a TLV is urgent TLV. When the protocol description specifies that a TLV is urgent
(as in Section 3.7.2 and Section 3.8.2), then the TLV MUST be sent (as in Section 3.7.2 and Section 3.8.1), then the TLV MUST be sent
within a short time known as the urgent timeout (see Appendix B for within a short time known as the urgent timeout (see Appendix B for
recommended values). When the TLV is governed by a timeout recommended values). When the TLV is governed by a timeout
explicitly included in a previous TLV, such as in the case of explicitly included in a previous TLV, such as in the case of
Acknowledgements (Section 4.6.4), Updates (Section 3.7) and IHUs Acknowledgments (Section 4.6.4), Updates (Section 3.7), and IHUs
(Section 3.4.2), then the TLV MUST be sent early enough to meet the (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 explicit deadline (with a small margin to allow for propagation
delays). In all other cases, the TLV SHOULD be sent out within one- delays). In all other cases, the TLV SHOULD be sent out within one-
half of the Multicast Hello interval. half of the Multicast Hello interval.
In order to avoid packet drops (either at the sender or at the In order to avoid packet drops (either at the sender or at the
receiver), a delay SHOULD be introduced between successive packets receiver), a delay SHOULD be introduced between successive packets
sent out on the same interface, within the constraints of the sent out on the same interface, within the constraints of the
previous paragraph. Note however that such packet pacing might previous paragraph. Note, however, that such packet pacing might
impair the ability of some link layers (e.g., IEEE 802.11 impair the ability of some link layers (e.g., IEEE 802.11
[IEEE802.11]) to perform packet aggregation. [IEEE802.11]) to perform packet aggregation.
3.2. Data Structures 3.2. Data Structures
In this section, we give a description of the data structures that In this section, we describe the data structures that every Babel
every Babel speaker maintains. This description is conceptual: a speaker maintains. This description is conceptual: a Babel speaker
Babel speaker may use different data structures as long as the may use different data structures as long as the resulting protocol
resulting protocol is the same as the one described in this document. is the same as the one described in this document. For example,
For example, rather than maintaining a single table containing both rather than maintaining a single table containing both selected and
selected and unselected (fallback) routes, as described in unselected (fallback) routes, as described in Section 3.2.6, an
Section 3.2.6 below, an actual implementation would probably use two actual implementation would probably use two tables, one with
tables, one with selected routes and one with fallback routes. 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 a non-negative integer n, the sum of s and n is Given a seqno s and a non-negative integer n, the sum of s and n is
defined by defined by the following:
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 is the bitwise conjunction operation. and 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 the following:
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
or equivalently or, equivalently,
s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. s < s' (modulo 2^(16)) when s /= s' and ((s' - s) AND 32768) = 0.
3.2.2. Node Sequence Number 3.2.2. Node Sequence Number
A node's sequence number is a 16-bit integer that is included in A node's sequence number is a 16-bit integer that is included in
route updates sent for routes originated by this node. route updates sent for routes originated by this node.
A node increments its sequence number (modulo 2^16) whenever it A node increments its sequence number (modulo 2^(16)) whenever it
receives a request for a new sequence number (Section 3.8.1.2). A receives a request for a new sequence number (Section 3.8.1.2). A
node SHOULD NOT increment its sequence number (seqno) spontaneously, node SHOULD NOT increment its sequence number (seqno) spontaneously,
since increasing seqnos makes it less likely that other nodes will since increasing seqnos makes it less likely that other nodes will
have feasible alternate routes when their selected routes fail. have feasible alternate routes when their selected routes fail.
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.
that an interface's Multicast Hello seqno is unrelated to the node's (Note that an interface's Multicast Hello seqno is unrelated to the
seqno.) node's seqno.)
There are two timers associated with each interface table entry. The There are two timers associated with each interface table entry. The
periodic Multicast Hello timer governs the sending of scheduled periodic multicast hello timer governs the sending of scheduled
Multicast Hello and IHU packets (Section 3.4. The periodic Update Multicast Hello and IHU packets (Section 3.4). The periodic Update
timer governs the sending of periodic route updates (Section 3.7.1). timer governs the sending of periodic route updates (Section 3.7.1).
See Appendix B for suggested time constants. 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; * the local node's interface over which this neighbour is reachable;
o the address of the neighbouring interface; * the address of the neighbouring interface;
o a history of recently received Multicast Hello packets from this * a history of recently received Multicast Hello packets from this
neighbour; this can, for example, be a sequence of n bits, for neighbour; this can, for example, be a sequence of n bits, for
some small value n, indicating which of the n hellos most recently some small value n, indicating which of the n hellos most recently
sent by this neighbour have been received by the local node; sent by this neighbour have been received by the local node;
o a history of recently received Unicast Hello packets from this * a history of recently received Unicast Hello packets from this
neighbour; neighbour;
o the "transmission cost" value from the last IHU packet received * the "transmission cost" value from the last IHU packet received
from this neighbour, or FFFF hexadecimal (infinity) if the IHU from this neighbour, or FFFF hexadecimal (infinity) if the IHU
hold timer for this neighbour has expired; hold timer for this neighbour has expired;
o the expected incoming Multicast Hello sequence number for this * the expected incoming Multicast Hello sequence number for this
neighbour, an integer modulo 2^16. neighbour, an integer modulo 2^(16).
o the expected incoming Unicast Hello sequence number for this * the expected incoming Unicast Hello sequence number for this
neighbour, an integer modulo 2^16. neighbour, an integer modulo 2^(16).
o the outgoing Unicast Hello sequence number for this neighbour, an * 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
Hello is sent. (Note that the outgoing Unicast Hello seqno for a Unicast Hello is sent. (Note that the outgoing Unicast Hello
neighbour is distinct from the interface's outgoing Multicast seqno for a neighbour is distinct from the interface's outgoing
Hello seqno.) Multicast 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 set to the interval value carried by multicast hello timer, which is set to the interval value carried by
scheduled Multicast Hello TLVs sent by this neighbour, the unicast scheduled Multicast Hello TLVs sent by this neighbour, the unicast
hello timer, which is set to 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 set to a small Unicast Hello TLVs, and the IHU timer, which is set to a small
multiple of the interval carried in IHU TLVs (see "IHU Hold time" in multiple of the interval carried in IHU TLVs (see "IHU Hold time" in
Appendix B for suggested values). 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
skipping to change at page 16, line 20 skipping to change at line 706
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 in * the prefix (prefix, plen), where plen is the prefix length in
bits, that this entry applies to; bits, that this entry applies to;
o the router-id of a router originating this prefix; * the router-id of a router originating this prefix;
o a pair (seqno, metric), this source's feasibility distance. * 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
The route table contains the routes known to this node. It is The route table contains the routes known to this node. It is
indexed by triples of the form (prefix, plen, neighbour), and every indexed by triples of the form (prefix, plen, neighbour), and every
route table entry contains the following data: route table entry contains the following data:
o the source (prefix, plen, router-id) for which this route is * the source (prefix, plen, router-id) for which this route is
advertised; advertised;
o the neighbour (an entry in the neighbour table) that advertised * the neighbour (an entry in the neighbour table) that advertised
this route; this route;
o the metric with which this route was advertised by the neighbour, * the metric with which this route was advertised by the neighbour,
or FFFF hexadecimal (infinity) for a recently retracted route; or FFFF hexadecimal (infinity) for a recently retracted route;
o the sequence number with which this route was advertised; * the sequence number with which this route was advertised;
o the next-hop address of this route; * the next-hop address of this route;
o a boolean flag indicating whether this route is selected, i.e.,
* 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.3. 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
each route: the route's distance, which is stored in the route table, with each route: the route's distance, which is stored in the route
and the feasibility distance, stored in the source table and shared table, and the feasibility distance, which is stored in the source
between all routes with the same source. table and shared 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
originated locally, or because they were forwarded) and to which no originated locally, or because they were forwarded) and to which no
reply has been received yet. This table is indexed by triples of the reply has been received yet. This table is indexed by triples of the
form (prefix, plen, router-id), and every entry in this table form (prefix, plen, router-id), and every entry in this table
contains the following data: contains the following data:
o the prefix, plen, router-id, and seqno being requested; * the prefix, plen, router-id, and seqno being requested;
o the neighbour, if any, on behalf of which we are forwarding this * the neighbour, if any, on behalf of which we are forwarding this
request; request;
o a small integer indicating the number of times that this request * a small integer indicating the number of times that this request
will be resent if it remains unsatisfied. will be resent if it remains unsatisfied.
There is one timer associated with each pending seqno request; it There is one timer associated with each pending seqno request; it
governs both the resending of requests and their expiry. governs both the resending of requests and their expiry.
3.3. Acknowledgments and acknowledgment requests 3.3. Acknowledgments and Acknowledgment Requests
A Babel speaker may request that a neighbour receiving a given packet A Babel speaker may request that a neighbour receiving a given packet
reply with an explicit acknowledgment within a given time. While the reply with an explicit acknowledgment within a given time. While the
use of acknowledgment requests is optional, every Babel speaker MUST use of acknowledgment requests is optional, every Babel speaker MUST
be able to reply to such a request. be able to reply to such a request.
An acknowledgment MUST be sent to a unicast destination. On the An acknowledgment MUST be sent to a unicast destination. On the
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 to 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.4), 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
the set of neighbours heard over each of its interfaces and the set of neighbours heard over each of its interfaces and
ascertains bidirectional reachability. On unreliable media, ascertains bidirectional reachability. On unreliable media,
neighbour acquisition additionally provides some statistics that may neighbour acquisition additionally provides some statistics that may
be useful for link quality computation. be useful for link quality computation.
skipping to change at page 18, line 35 skipping to change at line 815
When to do that is implementation-specific; suitable strategies When to do that is implementation-specific; suitable strategies
include creating an entry when any Babel packet is received, or include creating an entry when any Babel packet is received, or
creating an entry when a Hello TLV is parsed. Similarly, in order to creating an entry when a Hello TLV is parsed. Similarly, in order to
conserve system resources, an implementation SHOULD discard an entry conserve system resources, an implementation SHOULD discard an entry
when it has been unused for long enough; suitable strategies include when it has been unused for long enough; suitable strategies include
dropping the neighbour after a timeout, and dropping a neighbour when dropping the neighbour after a timeout, and dropping a neighbour when
the associated Hello histories become empty (see Appendix A.2). the associated Hello histories become empty (see Appendix A.2).
3.4.1. Reverse Reachability Detection 3.4.1. Reverse Reachability Detection
Every Babel node sends Hello TLVs to its neighbours to indicate that Every Babel node sends Hello TLVs to its neighbours, at regular or
it is alive, at regular or irregular intervals. Each Hello TLV irregular intervals, to indicate that it is alive. Each Hello TLV
carries an increasing (modulo 2^16) sequence number and an upper carries an increasing (modulo 2^(16)) sequence number and an upper
bound on the time interval until the next Hello of the same type (see bound on the time interval until the next Hello of the same type (see
below). If the time interval is set to 0, then the Hello TLV does below). If the time interval is set to 0, then the Hello TLV does
not establish a new promise: the deadline carried by the previous not establish a new promise: the deadline carried by the previous
Hello of the same type still applies to the next Hello (if the most Hello of the same type still applies to the next Hello (if the most
recent scheduled Hello of the right kind was received at time t0 and recent scheduled Hello of the right kind was received at time t0 and
carried interval i, then the previous promise of sending another carried interval i, then the previous promise of sending another
Hello before time t0 + i still holds). We say that a Hello is Hello before time t0 + i still holds). We say that a Hello is
"scheduled" if it carries a non-zero interval, and "unscheduled" "scheduled" if it carries a nonzero interval, and "unscheduled"
otherwise. otherwise.
There are two kinds of Hellos: Multicast Hellos, which use a per- There are two kinds of Hellos: Multicast Hellos, which use a per-
interface Hello counter (the Multicast Hello seqno), and Unicast interface Hello counter (the Multicast Hello seqno), and Unicast
Hellos, which use a per-neighbour counter (the Unicast Hello seqno). Hellos, which use a per-neighbour counter (the Unicast Hello seqno).
A Multicast Hello with a given seqno MUST be sent to all neighbours A Multicast Hello with a given seqno MUST be sent to all neighbours
on a given interface, either by sending it to a multicast address or on a given interface, either by sending it to a multicast address or
by sending it to one unicast address per neighbour (hence, the term by sending it to one unicast address per neighbour (hence, the term
"Multicast Hello" is a slight misnomer). A Unicast Hello carrying a "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a
given seqno should normally be sent to just one neighbour (over given seqno should normally be sent to just one neighbour (over
skipping to change at page 20, line 46 skipping to change at line 920
Since nodes do not necessarily send periodic Unicast Hellos but do Since nodes do not necessarily send periodic Unicast Hellos but do
usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD
use an algorithm that yields a finite rxcost when only Multicast use an algorithm that yields a finite rxcost when only Multicast
Hellos are received, unless interoperability with nodes that only Hellos are received, unless interoperability with nodes that only
send Multicast Hellos is not required. send Multicast Hellos is not required.
How the txcost and rxcost are combined in order to compute a link's How the txcost and rxcost are combined in order to compute a link's
cost is a matter of local policy; as far as Babel's correctness is cost is a matter of local policy; as far as Babel's correctness is
concerned, only the following conditions MUST be satisfied: concerned, only the following conditions MUST be satisfied:
o the cost is strictly positive; * the cost is strictly positive;
o if no Hello TLVs of either kind were received recently, then the * if no Hello TLVs of either kind were received recently, then the
cost is infinite; cost is infinite;
o if the txcost is infinite, then the cost is infinite. * if the txcost is infinite, then the cost is infinite.
See Appendix A.2 for RECOMMENDED strategies for computing a link's See Appendix A.2 for RECOMMENDED strategies for computing a link's
cost. cost.
3.5. Routing Table Maintenance 3.5. Routing Table Maintenance
Conceptually, a Babel update is a quintuple (prefix, plen, router-id, Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
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.3. 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.
skipping to change at page 21, line 35 skipping to change at line 957
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
prevent the resulting route from being selected. prevent the resulting route from being selected.
A feasibility distance is a pair (seqno, metric), where seqno is an A feasibility distance is a pair (seqno, metric), where seqno is an
integer modulo 2^16 and metric is a positive integer. Feasibility integer modulo 2^(16) and metric is a positive integer. Feasibility
distances are compared lexicographically, with the first component distances are compared lexicographically, with the first component
inverted: we say that a distance (seqno, metric) is strictly better inverted: we say that a distance (seqno, metric) is strictly better
than a distance (seqno', metric'), written than a distance (seqno', metric'), written
(seqno, metric) < (seqno', metric') (seqno, metric) < (seqno', metric')
when when
seqno > seqno' or (seqno = seqno' and metric < metric') seqno > seqno' or (seqno = seqno' and metric < metric')
where sequence numbers are compared modulo 2^16. where sequence numbers are compared modulo 2^(16).
Given a source (prefix, plen, router-id), a node's feasibility Given a source (prefix, plen, router-id), a node's feasibility
distance for this source is the minimum, according to the ordering distance for this source is the minimum, according to the ordering
defined above, of the distances of all the finite updates ever sent defined above, of the distances of all the finite updates ever sent
by this particular node for the prefix (prefix, plen) and the given by this particular node for the prefix (prefix, plen) and the given
router-id. Feasibility distances are maintained in the source table, router-id. Feasibility distances are maintained in the source table,
the exact procedure is given in Section 3.7.3. the exact procedure is given in Section 3.7.3.
A received update is feasible when either it is a retraction (its A received update is feasible when either it is a retraction (its
metric is FFFF hexadecimal), or the advertised distance is strictly metric is FFFF hexadecimal), or the advertised distance is strictly
better, in the sense defined above, than the feasibility distance for better, in the sense defined above, than the feasibility distance for
the corresponding source. More precisely, a route advertisement the corresponding source. More precisely, a route advertisement
carrying the quintuple (prefix, plen, router-id, seqno, metric) is carrying the quintuple (prefix, plen, router-id, seqno, metric) is
feasible if one of the following conditions holds: feasible if one of the following conditions holds:
o metric is infinite; or * metric is infinite; or
o no entry exists in the source table indexed by (prefix, plen, * no entry exists in the source table indexed by (prefix, plen,
router-id); or router-id); or
o an entry (prefix, plen, router-id, seqno', metric') exists in the * an entry (prefix, plen, router-id, seqno', metric') exists in the
source table, and either source table, and either
* seqno' < seqno or - seqno' < seqno or
* seqno = seqno' and metric < metric'. - seqno = seqno' and metric < metric'.
Note that the feasibility condition considers the metric advertised Note that the feasibility condition considers the metric advertised
by the neighbour, not the route's metric; hence, a fluctuation in a by the neighbour, not the route's metric; hence, a fluctuation in a
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 c and the metric m 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; * if c is infinite, then M(c, m) is infinite;
o M is strictly monotonic: M(c, m) > m. * 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'). * M is left-distributive: if m <= m', then M(c, m) <= M(c, m').
While strict monotonicity is essential to the integrity of the While strict monotonicity is essential to the integrity of the
network (persistent routing loops may arise if it is not satisfied), network (persistent routing loops may arise if it is not satisfied),
left distributivity is not: if it is not satisfied, Babel will still left-distributivity is not: if it is not satisfied, Babel will still
converge to a loop-free configuration, but might not reach a global converge to a loop-free configuration, but might not reach a global
optimum (in fact, a global optimum may not even exist). optimum (in fact, a global optimum may not even exist).
The conditions above are easily satisfied by using the additive The conditions above are easily satisfied by using the additive
metric, i.e., by defining M(c, m) = c + m. Since the additive metric metric, i.e., by defining M(c, m) = c + m. Since the additive metric
is useful with a large range of cost computation strategies, it is is useful with a large range of cost computation strategies, it is
the RECOMMENDED default. See also Appendix C, which describes a the RECOMMENDED default. See also Appendix C, which describes a
technique that makes it possible to tweak the values of individual technique that makes it possible to tweak the values of individual
metrics without running the risk of creating routing loops. metrics without running the risk of creating routing loops.
3.5.3. 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, it checks whether it already has a metric) from a neighbour neigh, it checks whether it already has a
route table entry indexed by (prefix, plen, neigh). route table entry indexed by (prefix, plen, neigh).
If no such entry exists: If no such entry exists:
o if the update is unfeasible, it MAY be ignored; * if the update is unfeasible, it MAY be ignored;
o if the metric is infinite (the update is a retraction of a route * 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 * 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-
id), seqno equal to seqno and an advertised metric equal to the id), seqno equal to seqno, and an advertised metric equal to the
metric carried by the update. metric carried by the update.
If such an entry exists: If such an entry exists:
o if the entry is currently selected, the update is unfeasible, and * 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, * 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 (see "Route Hold time" the interval value included in the update (see "Route Expiry time"
in Appendix B for suggested values). If the update is unfeasible, in Appendix B for suggested values). If the update is unfeasible,
then the (now unfeasible) entry MUST be immediately unselected. then the (now unfeasible) entry MUST be immediately unselected.
If the update caused the router-id of the entry to change, an If the update caused the router-id of the entry to change, an
update (possibly a retraction) MUST be sent in a timely manner as update (possibly a retraction) MUST be sent in a timely manner as
described in Section 3.7.2. 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.4. 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 for 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.3 above. As long as this entry is maintained, packets Section 3.5.3. As long as this entry is maintained, packets destined
destined to an address within P MUST NOT be forwarded by following a to an address within P MUST NOT be forwarded by following a route for
route for a shorter prefix. This entry is removed as soon as a a shorter prefix. This entry is removed as soon as a finite-metric
finite-metric update for prefix P is received and the resulting route update for prefix P is received and the resulting route selected. If
selected. If no such update is forthcoming, the infinite metric no such update is forthcoming, the infinite metric entry SHOULD be
entry SHOULD be maintained at least until it is guaranteed that no maintained at least until it is guaranteed that no neighbour has
neighbour has selected the current node as next-hop for prefix P. selected the current node as next hop for prefix P. This can be
This can be achieved by either: achieved by either:
o waiting until the route's expiry timer has expired * waiting until the route's expiry timer has expired
(Section 3.5.3); (Section 3.5.3); or
o sending a retraction with an acknowledgment request (Section 3.3) * 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 algorithm'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 * a route with infinite metric (a retracted route) is never
selected; selected;
o an unfeasible route is never selected. * an unfeasible route is never selected.
Babel nodes using different route selection strategies will Babel nodes using different route selection strategies will
interoperate and not create routing loops as long as these two interoperate and will not create routing loops as long as these two
properties hold. properties hold.
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 across the network, and might create persistent blackholes propagates across the network, and might create persistent black-
if the metric being used is not left-distributive (Section 3.5.2). holes if the metric being used is not left-distributive
(Section 3.5.2).
The obvious route selection strategy is to pick, for every The obvious route selection strategy is to pick, for every
destination, the feasible route with minimal metric. When all destination, the feasible route with minimal metric. When all
metrics are stable, this approach ensures convergence to a tree of metrics are stable, this approach ensures convergence to a tree of
shortest paths (assuming that the metric is left-distributive, see shortest paths (assuming that the metric is left-distributive, see
Section 3.5.2). There are two reasons, however, why this strategy Section 3.5.2). There are two reasons, however, why this strategy
may lead to instability in the presence of continuously varying may lead to instability in the presence of continuously varying
metrics. First, if two parallel routes oscillate around a common metrics. First, if two parallel routes oscillate around a common
value, then the smallest metric strategy will keep switching between value, then the smallest metric strategy will keep switching between
the two. Second, when a route is selected, congestion along it the two. Second, the selection of a route increases congestion along
increases, which might increase packet loss, which in turn could it, which might increase packet loss, which in turn could cause its
cause its metric to increase; this is a feedback loop, of the kind metric to increase; this kind of feedback loop is prone to causing
that is prone to causing persistent oscillations. persistent oscillations.
In order to limit these kinds of instabilities, a route selection In order to limit these kinds of instabilities, a route selection
strategy SHOULD include some form of hysteresis, i.e., be sensitive strategy SHOULD include some form of hysteresis, i.e., be sensitive
to a route's history: if a route is currently selected, then the to a route's history: the strategy should only switch from the
strategy should only switch to a different route if the latter has currently selected route to a different route if the latter has been
been consistently good for some period of time. A RECOMMENDED consistently good for some period of time. A RECOMMENDED hysteresis
hysteresis algorithm is given in Appendix A.3. algorithm is given in Appendix A.3.
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
skipping to change at page 26, line 28 skipping to change at line 1188
prefixes. 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 learnt 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 MUST advertise each of its selected routes on Every Babel speaker MUST advertise each of its selected routes on
every interface, at least once every Update interval. Since Babel every interface, at least once every Update interval. Since Babel
doesn't suffer from routing loops (there is no "counting to doesn't suffer from routing loops (there is no "counting to
infinity") and relies heavily on triggered updates (Section 3.7.2), infinity") and relies heavily on triggered updates (Section 3.7.2),
this full dump only needs to happen infrequently (see Appendix B for this full dump only needs to happen infrequently (see Appendix B for
skipping to change at page 27, line 26 skipping to change at line 1235
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
update, because a link's cost has changed, or because a different update, because a link's cost has changed or because a different next
next hop has been selected. A node SHOULD NOT send triggered updates hop has been selected. A node SHOULD NOT send triggered updates for
for other reasons, such as when there is a minor fluctuation in a other reasons, such as when there is a minor fluctuation in a route's
route's metric, when the selected next hop changes without inducing a metric, when the selected next hop changes without inducing a
significant change to the route's metric, or to propagate a new significant change to the route's metric, or to propagate a new
sequence number (except to satisfy a request, as specified in sequence number (except to satisfy a request, as specified in
Section 3.8). Section 3.8).
3.7.3. Maintaining Feasibility Distances 3.7.3. Maintaining Feasibility Distances
Before sending an update (prefix, plen, router-id, seqno, metric) Before sending an update (prefix, plen, router-id, seqno, metric)
with finite metric (i.e., not a route retraction), a Babel node with finite metric (i.e., not a route retraction), a Babel node
updates the feasibility distance maintained in the source table. updates the feasibility distance maintained in the source table.
This is done as follows. This is done as follows.
If no entry indexed by (prefix, plen, router-id) exists in the source If no entry indexed by (prefix, plen, router-id) exists in the source
table, then one is created with value (prefix, plen, router-id, table, then one is created with value (prefix, plen, router-id,
seqno, metric). seqno, metric).
If an entry (prefix, plen, router-id, seqno', metric') exists, then If an entry (prefix, plen, router-id, seqno', metric') exists, then
it is updated as follows: it is updated as follows:
o if seqno > seqno', then seqno' := seqno, metric' := metric; * if seqno > seqno', then seqno' := seqno, metric' := metric;
o if seqno = seqno' and metric' > metric, then metric' := metric; * if seqno = seqno' and metric' > metric, then metric' := metric;
o otherwise, nothing needs to be done. * otherwise, nothing needs to be done.
The garbage-collection timer for the entry is then reset. Note that The garbage-collection timer for the entry is then reset. Note that
the feasibility distance is not updated and the garbage-collection the feasibility distance is not updated and the garbage-collection
timer is not reset when a retraction (an update with infinite metric) timer is not reset when a retraction (an update with infinite metric)
is sent. is sent.
When the garbage-collection timer expires, the entry is removed from When the garbage-collection timer expires, the entry is removed from
the source table. the source table.
3.7.4. Split Horizon 3.7.4. Split Horizon
skipping to change at page 29, line 22 skipping to change at line 1329
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 SHOULD be rate-limited, route table dump. Full route dumps SHOULD be rate-limited,
especially 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 and 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
entry's, the node compares the router-id against its own router-id. route entry's, the node compares the router-id against its own
If the router-id is its own, then it increases its sequence number by router-id. If the router-id is its own, then it increases its
1 (modulo 2^16) and sends an update. A node MUST NOT increase its sequence number by 1 (modulo 2^(16)) and sends an update. A node
sequence number by more than 1 in reaction to a single seqno request. MUST NOT increase its sequence number by more than 1 in reaction to a
single seqno request.
Otherwise, if the requested router-id is not its own, the received Otherwise, if the requested router-id is not its own, the received
node consults the hop count field of the request. If the hop count node consults the Hop Count field of the request. If the hop count
is 2 or more, and the node is advertising the prefix to its is 2 or more, and the node is advertising the prefix to its
neighbours, the node selects a neighbour to forward the request to as neighbours, the node selects a neighbour to forward the request to as
follows: follows:
o if the node has one or more feasible routes toward the requested * if the node has one or more feasible routes towards the requested
prefix with a next hop that is not the requesting node, then the 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 feasible) routes to * otherwise, if the node has one or more (not feasible) routes to
the requested prefix with a next hop that is not the requesting the requested prefix with a next hop that is not the requesting
node, then the node SHOULD forward the request to the next hop of node, then the node SHOULD forward the request to the 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. The forwarded request SHOULD be sent as an selected neighbour. The forwarded request SHOULD be sent as an
urgent TLV (as defined in Section 3.1). 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) as an urgent TLV (as defined in Section 3.1). A satisfy the request) as an urgent TLV (as defined in Section 3.1). A
node SHOULD compare every incoming seqno request against its list of node SHOULD compare every incoming seqno request against its list of
recently forwarded seqno requests and avoid forwarding it if it is recently forwarded seqno requests and avoid forwarding the request if
redundant (i.e., if it has recently sent a request with the same it is redundant (i.e., if the node has recently sent a request with
prefix, router-id and a seqno that is not smaller modulo 2^16). the same prefix, router-id, and a seqno that is not smaller modulo
2^(16)).
Since the request-forwarding mechanism does not necessarily obey the 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,
the subsequent copies may be forwarded to a different neighbour than the subsequent copies may be forwarded to a different neighbour than
the initial one. the initial one.
3.8.2. Sending Requests 3.8.2. Sending Requests
A Babel node MAY send a route or seqno request at any time, to a A Babel node MAY send a route or seqno request at any time to a
multicast or a unicast address; there is only one case when multicast or a unicast address; there is only one case when
originating requests is required (Section 3.8.2.1). originating requests is required (Section 3.8.2.1).
3.8.2.1. Avoiding Starvation 3.8.2.1. Avoiding Starvation
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
skipping to change at page 31, line 17 skipping to change at line 1421
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 are expected to actually reach the source.) requests are expected to 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 (see "Request Timeout" in Appendix B for suggested short time (see "Request timeout" in Appendix B for suggested
values). In the presence of heavy packet loss, however, all such 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.
In order to keep routes from spuriously expiring because they have In order to keep routes from spuriously expiring because they have
become unfeasible, a node SHOULD send a unicast seqno request when it become unfeasible, a node SHOULD send a unicast seqno request when it
receives an unfeasible update for a route that is currently selected. receives an unfeasible update for a route that is currently selected.
The requested sequence number is computed from the source table as in The requested sequence number is computed from the source table as in
Section 3.8.2.1 above. Section 3.8.2.1.
Additionally, since metric computation does not necessarily coincide Additionally, since metric computation does not necessarily coincide
with the delay in propagating updates, a node might receive an with the delay in propagating updates, a node might receive an
unfeasible update from a currently unselected neighbour that is unfeasible update from a currently unselected neighbour that is
preferable to the currently selected route (e.g., because it has a preferable to the currently selected route (e.g., because it has a
much smaller metric); in that case, the node SHOULD send a unicast much smaller metric); in that case, the node SHOULD send a unicast
seqno request to the neighbour that advertised the preferable update. seqno request to the neighbour that advertised the preferable update.
3.8.2.3. Preventing Routes from Expiring 3.8.2.3. Preventing Routes from Expiring
skipping to change at page 32, line 27 skipping to change at line 1480
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 maximise the size of lower-layer fragmentation, a Babel node SHOULD maximise the size of
the packets it sends, up to the outgoing interface's MTU adjusted for the packets it sends, up to the outgoing interface's MTU adjusted for
lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP
over IPv6). It MUST NOT send packets larger than the attached over IPv6). It MUST NOT send packets larger than the attached
interface's MTU adjusted for lower-layer headers or 512 octets, interface's MTU adjusted for lower-layer headers or 512 octets,
whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- whichever is larger, but not exceeding 2^(16) - 1 adjusted for lower-
layer headers. Every Babel speaker MUST be able to receive packets layer headers. Every Babel speaker MUST be able to receive packets
that are as large as any attached interface's MTU adjusted for lower- that are as large as any attached interface's MTU adjusted for lower-
layer headers or 512 octets, whichever is larger. Babel packets MUST layer headers or 512 octets, whichever is larger. Babel packets MUST
NOT be sent in IPv6 Jumbograms [RFC2675]. NOT be sent in IPv6 jumbograms [RFC2675].
4.1. Data Types 4.1. Data Types
4.1.1. Representation of integers 4.1.1. Representation of Integers
All multi-octet fields that represent integers are encoded with the All multi-octet fields that represent integers are encoded with the
most significant octet first (in Big-Endian format [IEN137], also most significant octet first (in Big-Endian format [IEN137], also
called Network Order). The base protocol only carries unsigned called network order). The base protocol only carries unsigned
values; if an extension needs to carry signed values, it will need to values; if an extension needs to carry signed values, it will need to
specify their encoding (e.g., two's complement). specify their encoding (e.g., two's complement).
4.1.2. Interval 4.1.2. 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 10 ms, which should cover
reasonable applications of Babel (see also Appendix B). all reasonable applications of Babel (see also Appendix B).
4.1.3. Router-Id 4.1.3. 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 (FFFFFFFFFFFFFFFF hexadecimal). all binary ones (FFFFFFFFFFFFFFFF hexadecimal).
4.1.4. Address 4.1.4. 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, within Update TLVs of encoding addresses are defined. Additionally, within Update TLVs
a common subnet prefix may be omitted when multiple addresses are a common subnet prefix may be omitted when multiple addresses are
sent in a single packet -- this is known as address compression sent in a single packet -- this is known as address compression
(Section 4.6.9). (Section 4.6.9).
Address encodings: Address encodings (AEs):
o AE 0: wildcard address. The value is 0 octets long. AE 0: Wildcard address. The value is 0 octets long.
o AE 1: IPv4 address. Compression is allowed. 4 octets or less. AE 1: IPv4 address. Compression is allowed. 4 octets or less.
o AE 2: IPv6 address. Compression is allowed. 16 octets or less. AE 2: IPv6 address. Compression is allowed. 16 octets or less.
o AE 3: link-local IPv6 address. Compression is not allowed. The AE 3: Link-local IPv6 address. Compression is not allowed. The
value is 8 octets long, a prefix of fe80::/64 is implied. value is 8 octets long, a prefix of fe80::/64 is implied.
The address family associated to an address encoding is either IPv4 The address family associated with an address encoding is either IPv4
or IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 or IPv6: it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2
and 3. and 3.
4.1.5. Prefixes 4.1.5. 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). The format is designed to be of TLVs (the packet trailer). The format is designed to be
extensible; see Appendix D for extensibility considerations. 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...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields : Fields:
Magic The arbitrary but carefully chosen value 42 (decimal); Magic The arbitrary but carefully chosen value 42 (decimal);
packets with a first octet different from 42 MUST be packets with a first octet different from 42 MUST be
silently ignored. silently ignored.
Version This document specifies version 2 of the Babel protocol. Version This document specifies version 2 of the Babel protocol.
Packets with a second octet different from 2 MUST be Packets with a second octet different from 2 MUST be
silently ignored. silently ignored.
Body length The length in octets of the body following the packet Body length The length in octets of the body following the packet
header (excluding the Magic, Version and Body length header (excluding the Magic, Version, and Body length
fields, and excluding the packet trailer). fields, and excluding the packet trailer).
Packet Body The packet body; a sequence of TLVs. Packet Body The packet body; a sequence of TLVs.
Packet Trailer The packet trailer; another sequence of TLVs. Packet Trailer The packet trailer; another sequence of TLVs.
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
skipping to change at page 35, line 11 skipping to change at line 1595
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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length fields. Length fields.
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.
skipping to change at page 35, line 41 skipping to change at line 1625
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 and Length The length of the body in octets, exclusive of the Type 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), is called the mandatory bit; in other words, sub-TLV hexadecimal), is called the mandatory bit; in other words, sub-TLV
types 128 through 255 have the mandatory bit set. This bit indicates types 128 through 255 have the mandatory bit set. This bit indicates
how to handle unknown sub-TLVs. If the mandatory bit is not set, how to handle unknown sub-TLVs. If the mandatory bit is not set,
then an unknown sub-TLV MUST be silently ignored, and the rest of the then an unknown sub-TLV MUST be silently ignored, and the rest of the
TLV is processed normally. If the mandatory bit is set, then the TLV is processed normally. If the mandatory bit is set, then the
whole enclosing TLV MUST be silently ignored (except for updating the whole enclosing TLV MUST be silently ignored (except for updating the
parser state by a Router-Id, Next-Hop or Update TLV, as described in parser state by a Router-Id, Next Hop, or Update TLV, as described in
the next section). the next section).
4.5. Parser state and encoding of updates 4.5. Parser State and Encoding of Updates
In a large network, the bulk of Babel traffic consists of route In a large network, the bulk of Babel traffic consists of route
updates; hence, some care has been given to encoding them updates; hence, some care has been given to encoding them
efficiently. The data conceptually contained in an update efficiently. The data conceptually contained in an update
(Section 3.5) is split into three pieces: (Section 3.5) is split into three pieces:
o the prefix, seqno and metric are contained in the Update TLV * the prefix, seqno, and metric are contained in the Update TLV
itself (Section 4.6.9); itself (Section 4.6.9);
o the router-id is taken from Router-Id TLV that precedes the Update * the router-id is taken from the Router-Id TLV that precedes the
TLV, and may be shared among multiple Update TLVs (Section 4.6.7); 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 * the next hop is taken either from the source address of the
network-layer packet that contains the Babel packet, or from an network-layer packet that contains the Babel packet or from an
explicit Next-Hop TLV (Section 4.6.8). explicit Next Hop TLV (Section 4.6.8).
In addition to the above, an Update TLV can omit a prefix of the In addition to the above, an Update TLV can omit a prefix of the
prefix being announced, which is then extracted from the preceding prefix being announced, which is then extracted from the preceding
Update TLV in the same address family (IPv4 or IPv6). Finally, as a 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 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 interface-id part of an IPv6 address, the Router-Id TLV itself may be
omitted and the router-id derived from the low-order bits of the omitted, and the router-id is derived from the low-order bits of the
advertised prefix (Section 4.6.9). advertised prefix (Section 4.6.9).
In order to implement these compression techniques, Babel uses a In order to implement these compression techniques, Babel uses a
stateful parser: a TLV may refer to data from a previous TLV. The stateful parser: a TLV may refer to data from a previous TLV. The
parser state consists of the following pieces of data: parser state consists of the following pieces of data:
o for each address encoding that allows compression, the current * 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 * 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 it 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 * 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 it is updated by each Router-Id TLV (Section 4.6.7)
by each Update TLV with Router-Id flag set. and 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 sub-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 or for any other reason. an unknown mandatory sub-TLV or for any other reason.
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
0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Fields : Fields:
Type Set to 0 to indicate a Pad1 TLV. Type Set to 0 to indicate a Pad1 TLV.
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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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.
skipping to change at page 38, line 21 skipping to change at line 1749
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 = 2 | Length | Reserved | | Type = 2 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Opaque | Interval | | Opaque | 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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length fields. Length fields.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Opaque An arbitrary value that will be echoed in the receiver's Opaque 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
time). time).
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating and allows sub-TLVs.
4.6.4. Acknowledgment 4.6.4. Acknowledgment
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 = 3 | Length | Opaque | | Type = 3 | Length | Opaque |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV is sent by a node upon receiving an Acknowledgment Request. This TLV is sent by a node upon receiving an Acknowledgment Request
TLV.
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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length fields. Length fields.
Opaque Set to the Opaque value of the Acknowledgment Request that Opaque Set to the Opaque value of the Acknowledgment Request that
prompted this Acknowledgment. prompted this Acknowledgment.
Since Opaque values are not globally unique, this TLV MUST be sent to Since Opaque 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
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 = 4 | Length | Flags | | Type = 4 | Length | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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 nonzero, this is an upper bound, expressed in
centiseconds, on the time after which the sending node will centiseconds, on the time after which the sending node will
send a new scheduled Hello TLV with the same setting of the send a new scheduled Hello TLV with the same setting of the
Unicast flag. If this is 0, then this Hello represents an Unicast flag. If this is 0, then this Hello represents an
unscheduled Hello, and doesn't carry any new information unscheduled Hello and doesn't carry any new information
about times at which Hellos are sent. about times at which Hellos are sent.
The Flags field is interpreted as follows: The Flags field is interpreted as follows:
0 1 0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
o U (Unicast) flag (8000 hexadecimal): if set, then this Hello U (Unicast) flag (8000 hexadecimal): if set, then this Hello
represents a Unicast Hello, otherwise it represents a Multicast represents a Unicast Hello, otherwise it represents a
Hello; Multicast Hello;
o X: all other bits MUST be sent as 0 and silently ignored on X: all other bits MUST be sent as 0 and silently ignored on
reception. reception.
Every time a Hello is sent, the corresponding seqno counter MUST be Every time a Hello is sent, the corresponding seqno counter MUST be
incremented. Since there is a single seqno counter for all the incremented. Since there is a single seqno counter for all the
Multicast Hellos sent by a given node over a given interface, if the Multicast Hellos sent by a given node over a given interface, if the
Unicast flag is not set, this TLV MUST be sent to all neighbors on Unicast flag is not set, this TLV MUST be sent to all neighbours on
this link, which can be achieved by sending to a multicast this link, which can be achieved by sending to a multicast
destination, or by sending multiple packets to the unicast addresses destination or by sending multiple packets to the unicast addresses
of all reachable neighbours. Conversely, if the Unicast flag is set, of all reachable neighbours. Conversely, if the Unicast flag is set,
this TLV MUST be sent to a single neighbour, which can achieved by this TLV MUST be sent to a single neighbour, which can achieved by
sending to a unicast destination. In order to avoid large sending to a unicast destination. In order to avoid large
discontinuities in link quality, multiple Hello TLVs SHOULD NOT be discontinuities in link quality, multiple Hello TLVs SHOULD NOT be
sent in the same packet. sent in the same packet.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating and allows sub-TLVs.
4.6.6. IHU 4.6.6. IHU
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 = 5 | Length | AE | Reserved | | Type = 5 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rxcost | Interval | | Rxcost | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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
skipping to change at page 41, line 40 skipping to change at line 1913
Conceptually, an IHU is destined to a single neighbour. However, IHU Conceptually, an IHU is destined to a single neighbour. However, IHU
TLVs contain an explicit destination address, and MAY be sent to a TLVs contain an explicit destination address, and MAY be sent to a
multicast address, as this allows aggregation of IHUs destined to multicast address, as this allows aggregation of IHUs destined to
distinct neighbours into a single packet and avoids the need for an distinct neighbours into a single packet and avoids the need for an
ARP or Neighbour Discovery exchange when a neighbour is not being ARP or Neighbour Discovery exchange when a neighbour is not being
used for data traffic. used for data traffic.
IHU TLVs with an unknown value in the AE field MUST be silently IHU 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.7. Router-Id 4.6.7. Router-Id
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 = 6 | Length | Reserved | | Type = 6 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Router-Id + + Router-Id +
skipping to change at page 42, line 4 skipping to change at line 1926
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 = 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, as described in Section 4.5. This TLV sets the router- Update TLVs, as described in Section 4.5. This TLV sets the router-
id even if it is otherwise ignored due to an unknown mandatory sub- id even if it is otherwise ignored due to an unknown mandatory sub-
TLV. 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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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, as 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 described in Section 4.5. This TLV sets up the next hop for
subsequent Update TLVs even if it is otherwise ignored due to an subsequent Update TLVs even if it 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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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 over which
packet is transported over, a Next Hop TLV is not needed: in the this packet is transported, a Next Hop TLV is not needed: in the
absence of a Next Hop TLV in a given address family, the next hop absence of a Next Hop TLV in a given address family, the next-hop
address is taken to be the source address of the packet. address is taken to be the source address of the packet.
Next Hop TLVs with an unknown value for the AE field MUST be silently Next Hop TLVs with an unknown value for 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.9. Update 4.6.9. Update
0 1 2 3 0 1 2 3
skipping to change at page 43, line 36 skipping to change at line 2005
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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, as described in Section 4.5. 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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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 in bits of the advertised prefix. If AE is 3 Plen The length in bits of the advertised prefix. If AE is 3
(link-local IPv6), Omitted MUST be 0. (link-local IPv6), the Omitted field 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 31 skipping to change at line 2049
Prefix The prefix being advertised. This field's size is Prefix The prefix being advertised. This field's size is
(Plen/8 - Omitted) rounded upwards. (Plen/8 - Omitted) rounded upwards.
The Flags field is interpreted as follows: The Flags field is interpreted as follows:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
|P|R|X|X|X|X|X|X| |P|R|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
o P (Prefix) flag (80 hexadecimal): if set, then this Update P (Prefix) flag (80 hexadecimal): if set, then this Update TLV
establishes a new default prefix for subsequent Update TLVs with a establishes a new default prefix for subsequent Update TLVs
matching address encoding within the same packet, even if this TLV with a matching address encoding within the same packet,
is otherwise ignored due to an unknown mandatory sub-TLV; even if this TLV is otherwise ignored due to an unknown
mandatory sub-TLV;
o R (Router-Id) flag (40 hexadecimal): if set, then this TLV R (Router-Id) flag (40 hexadecimal): if set, then this TLV
establishes a new default router-id for this TLV and subsequent establishes a new default router-id for this TLV and
Update TLVs in the same packet, even if this TLV is otherwise subsequent Update TLVs in the same packet, even if this TLV
ignored due to an unknown mandatory sub-TLV. This router-id is is otherwise ignored due to an unknown mandatory sub-TLV.
computed from the first address of the advertised prefix as This router-id is computed from the first address of the
follows: advertised prefix as follows:
* if the length of the address is 8 octets or more, then the new * if the length of the address is 8 octets or more, then
router-id is taken from the 8 last octets of the address; the new router-id is taken from the 8 last octets of the
address;
* if the length of the address is smaller than 8 octets, then the * if the length of the address is smaller than 8 octets,
new router-id consists of the required number of zero octets then the new router-id consists of the required number
followed by the address, i.e., the address is stored on the of zero octets followed by the address, i.e., the
right of the router-id. For example, for an IPv4 address, the address is stored on the right of the router-id. For
router-id consists of 4 octets of zeroes followed by the IPv4 example, for an IPv4 address, the router-id consists of
address. 4 octets of zeroes followed by the IPv4 address.
o X: all other bits MUST be sent as 0 and silently ignored on 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 * 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; if even if it was ignored due to an unknown mandatory sub-TLV; if the
Omitted is not zero and there is no such TLV, then this Update Omitted field is not zero and there is no such TLV, then this
MUST be ignored; Update MUST be ignored;
o the next (Plen/8 - Omitted) rounded upwards octets are taken from * the next (Plen/8 - Omitted) rounded upwards octets are taken from
the Prefix field; the Prefix field;
o if Plen is not a multiple of 8, then any bits beyond Plen (i.e., * if Plen is not a multiple of 8, then any bits beyond Plen (i.e.,
the low-order (8 - Plen MOD 8) bits of the last octet) are the low-order (8 - Plen MOD 8) bits of the last octet) are
cleared; cleared;
o the remaining octets are set to 0. * 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 TLV, or Otherwise, it is taken either from the preceding Router-Id TLV, or
the preceding Update TLV with the Router-Id flag set, whichever comes the preceding Update TLV with the Router-Id flag set, whichever 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; if there is no suitable TLV, then this update is mandatory sub-TLV; if there is no suitable TLV, then this update is
ignored. 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 if it belongs to the same network-layer source address of this packet if it belongs to the same
address family as the prefix being announced; otherwise, this Update address family as the prefix being announced; otherwise, this Update
MUST be ignored. 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; Update TLVs with finite metric 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 and AE equal to 0 MUST be ignored. If the metric is infinite and AE
is 0, Plen and Omitted MUST both be 0; Update TLVs that do not is 0, Plen and Omitted MUST both be 0; Update TLVs that do not
satisfy this requirement MUST be ignored. satisfy this requirement MUST be ignored.
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
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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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).
skipping to change at page 46, line 42 skipping to change at line 2159
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). A Request TLV with case Plen must be 0 and Prefix is of length 0). A Request TLV with
AE set to 0 and Plen not set to 0 MUST be ignored. AE set to 0 and Plen not set to 0 MUST be ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating and allows sub-TLVs.
4.6.11. Seqno Request 4.6.11. Seqno 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 = 10 | Length | AE | Plen | | Type = 10 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Hop Count | Reserved | | Seqno | Hop Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Router-Id + + Router-Id +
| | | |
skipping to change at page 47, line 22 skipping to change at line 2181
+ Router-Id + + Router-Id +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix... | Prefix...
+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+
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 in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type and
Length 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 in bits 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
plus 1. This MUST NOT be 0. forwarded, 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.
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 Seqno Request TLV prompts the receiving node to send a finite- A Seqno Request TLV prompts the receiving node to send a finite-
metric Update for the prefix specified by the AE, Plen, and Prefix metric Update for the prefix specified by the AE, Plen, and Prefix
fields, with either a router-id different from what is specified by fields, with either a router-id different from what is specified by
the Router-Id field, or a Seqno no less (modulo 2^16) than what is the Router-Id field, or a Seqno no less (modulo 2^(16)) than what is
specified by the Seqno field. If this request cannot be satisfied specified by the Seqno field. If this request cannot be satisfied
locally, then it is forwarded according to the rules set out in locally, then it is forwarded according to the rules set out in
Section 3.8.1.2. Section 3.8.1.2.
While a Seqno Request MAY be sent to a multicast address, it MUST NOT While a Seqno Request MAY be sent to a multicast address, it MUST NOT
be forwarded to a multicast address and MUST NOT be forwarded to more be forwarded to a multicast address and MUST NOT be forwarded to more
than one neighbour. A request MUST NOT be forwarded if its Hop Count than one neighbour. A request MUST NOT be forwarded if its Hop Count
field is 1. field is 1.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating and allows sub-TLVs.
4.7. Details of specific sub-TLVs 4.7. Details of specific sub-TLVs
4.7.1. Pad1 4.7.1. Pad1
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Fields : Fields:
Type Set to 0 to indicate a Pad1 sub-TLV. Type Set to 0 to indicate a Pad1 sub-TLV.
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.
4.7.2. PadN 4.7.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 sub-TLV. Type Set to 1 to indicate a PadN sub-TLV.
Length The length of the body in octets, exclusive of the Type and Length The length of the body in octets, exclusive of the Type 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.
skipping to change at page 49, line 15 skipping to change at line 2266
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 allocation IANA has created a registry called "Babel TLV Types". The allocation
policy for this registry is Specification Required [RFC8126] for policy for this registry is Specification Required [RFC8126] for
Types 0-223, and Experimental Use for Types 224-254. The values in Types 0-223 and Experimental Use for Types 224-254. The values in
this registry are as follows: this registry are as follows:
+---------+-----------------------------------------+---------------+ +=========+==========================================+===========+
| Type | Name | Reference | | Type | Name | Reference |
+---------+-----------------------------------------+---------------+ +=========+==========================================+===========+
| 0 | Pad1 | this document | | 0 | Pad1 | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 1 | PadN | this document | | 1 | PadN | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 2 | Acknowledgment Request | this document | | 2 | Acknowledgment Request | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 3 | Acknowledgment | this document | | 3 | Acknowledgment | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 4 | Hello | this document | | 4 | Hello | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 5 | IHU | this document | | 5 | IHU | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 6 | Router-Id | this document | | 6 | Router-Id | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 7 | Next Hop | this document | | 7 | Next Hop | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 8 | Update | this document | | 8 | Update | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 9 | Route Request | this document | | 9 | Route Request | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 10 | Seqno Request | this document | | 10 | Seqno Request | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 11 | TS/PC | [RFC7298] | | 11 | TS/PC | [RFC7298] |
| | | | +---------+------------------------------------------+-----------+
| 12 | HMAC | [RFC7298] | | 12 | HMAC | [RFC7298] |
| | | | +---------+------------------------------------------+-----------+
| 13 | Source-specific Update | [BABEL-SS] | | 13 | Reserved | |
| | | | +---------+------------------------------------------+-----------+
| 14 | Source-specific Request | [BABEL-SS] | | 14 | Reserved | |
| | | | +---------+------------------------------------------+-----------+
| 15 | Source-specific Seqno Request | [BABEL-SS] | | 15 | Reserved | |
| | | | +---------+------------------------------------------+-----------+
| 16 | MAC | [BABEL-MAC] | | 224-254 | Reserved for Experimental Use | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 17 | PC | [BABEL-MAC] | | 255 | Reserved for expansion of the type space | RFC 8966 |
| | | | +---------+------------------------------------------+-----------+
| 18 | Challenge Request | [BABEL-MAC] |
| | | |
| 19 | Challenge Reply | [BABEL-MAC] |
| | | |
| 20-223 | Unassigned | |
| | | |
| 224-254 | Reserved for Experimental Use | this document |
| | | |
| 255 | Reserved for expansion of the type | this document |
| | space | |
+---------+-----------------------------------------+---------------+
IANA has created a registry called "Babel sub-TLV Types". The Table 1
IANA has created a registry called "Babel Sub-TLV Types". The
allocation policy for this registry is Specification Required for allocation policy for this registry is Specification Required for
Types 0-111 and 128-239, and Experimental Use for Types 112-126 and Types 0-111 and 128-239, and Experimental Use for Types 112-126 and
240-254. The values in this registry are as follows: 240-254. The values in this registry are as follows:
+---------+-------------------------------------+-------------------+ +=========+===============================+===================+
| Type | Name | Reference | | Type | Name | Reference |
+---------+-------------------------------------+-------------------+ +=========+===============================+===================+
| 0 | Pad1 | this document | | 0 | Pad1 | RFC 8966 |
| | | | +---------+-------------------------------+-------------------+
| 1 | PadN | this document | | 1 | PadN | RFC 8966 |
| | | | +---------+-------------------------------+-------------------+
| 2 | Diversity | [BABEL-DIVERSITY] | | 2 | Diversity | [BABEL-DIVERSITY] |
| | | | +---------+-------------------------------+-------------------+
| 3 | Timestamp | [BABEL-RTT] | | 3 | Timestamp | [BABEL-RTT] |
| | | | +---------+-------------------------------+-------------------+
| 4-111 | Unassigned | | | 4-111 | Unassigned | |
| | | | +---------+-------------------------------+-------------------+
| 112-126 | Reserved for Experimental Use | this document | | 112-126 | Reserved for Experimental Use | RFC 8966 |
| | | | +---------+-------------------------------+-------------------+
| 127 | Reserved for expansion of the type | this document | | 127 | Reserved for expansion of the | RFC 8966 |
| | space | | | | type space | |
| | | | +---------+-------------------------------+-------------------+
| 128 | Source Prefix | [BABEL-SS] | | 128 | Source Prefix | [BABEL-SS] |
| | | | +---------+-------------------------------+-------------------+
| 129-239 | Unassigned | | | 129-239 | Unassigned | |
| | | | +---------+-------------------------------+-------------------+
| 240-254 | Reserved for Experimental Use | this document | | 240-254 | Reserved for Experimental Use | RFC 8966 |
| | | | +---------+-------------------------------+-------------------+
| 255 | Reserved for expansion of the type | this document | | 255 | Reserved for expansion of the | RFC 8966 |
| | space | | | | type space | |
+---------+-------------------------------------+-------------------+ +---------+-------------------------------+-------------------+
IANA is instructed to create a registry called "Babel Address
Encodings". The allocation policy for this registry is Specification
Required for Address Encodings (AEs) 0-223, and Experimental Use for
AEs 224-254. The values in this registry are as follows:
+---------+----------------------------------------+---------------+ Table 2
| AE | Name | Reference |
+---------+----------------------------------------+---------------+
| 0 | Wildcard address | this document |
| | | |
| 1 | IPv4 address | this document |
| | | |
| 2 | IPv6 address | this document |
| | | |
| 3 | Link-local IPv6 address | this document |
| | | |
| 4-223 | Unassigned | |
| | | |
| 224-254 | Reserved for Experimental Use | this document |
| | | |
| 255 | Reserved for expansion of the AE space | this document |
+---------+----------------------------------------+---------------+
IANA has created a registry called "Babel Flags Values". The IANA has created a registry called "Babel Address Encodings". The
allocation policy for this registry is Specification Required. IANA allocation policy for this registry is Specification Required for
is instructed to rename this registry to "Babel Update Flags Values". Address Encodings (AEs) 0-223, and Experimental Use for AEs 224-254.
The values in this registry are as follows: The values in this registry are as follows:
+-----+-------------------+---------------+ +=========+========================================+===========+
| Bit | Name | Reference | | AE | Name | Reference |
+-----+-------------------+---------------+ +=========+========================================+===========+
| 0 | Default prefix | this document | | 0 | Wildcard address | RFC 8966 |
| | | | +---------+----------------------------------------+-----------+
| 1 | Default Router-ID | this document | | 1 | IPv4 address | RFC 8966 |
| | | | +---------+----------------------------------------+-----------+
| 2-7 | Unassigned | | | 2 | IPv6 address | RFC 8966 |
+-----+-------------------+---------------+ +---------+----------------------------------------+-----------+
| 3 | Link-local IPv6 address | RFC 8966 |
+---------+----------------------------------------+-----------+
| 4-223 | Unassigned | |
+---------+----------------------------------------+-----------+
| 224-254 | Reserved for Experimental Use | RFC 8966 |
+---------+----------------------------------------+-----------+
| 255 | Reserved for expansion of the AE space | RFC 8966 |
+---------+----------------------------------------+-----------+
IANA is instructed to create a new registry called "Babel Hello Flags Table 3
Values". The allocation policy for this registry is Specification
Required. The initial values in this registry are as follows:
+------+------------+---------------+ IANA has renamed the registry called "Babel Flags Values" to "Babel
| Bit | Name | Reference | Update Flags Values". The allocation policy for this registry is
+------+------------+---------------+ Specification Required. The values in this registry are as follows:
| 0 | Unicast | this document |
| | | |
| 1-15 | Unassigned | |
+------+------------+---------------+
IANA is instructed to replace all references to RFCs 6126 and 7557 in +=====+===================+===========+
all of the registries mentioned above by references to this document. | Bit | Name | Reference |
+=====+===================+===========+
| 0 | Default prefix | RFC 8966 |
+-----+-------------------+-----------+
| 1 | Default router-id | RFC 8966 |
+-----+-------------------+-----------+
| 2-7 | Unassigned | |
+-----+-------------------+-----------+
Table 4
IANA has created a new registry called "Babel Hello Flags Values".
The allocation policy for this registry is Specification Required.
The initial values in this registry are as follows:
+======+============+===========+
| Bit | Name | Reference |
+======+============+===========+
| 0 | Unicast | RFC 8966 |
+------+------------+-----------+
| 1-15 | Unassigned | |
+------+------------+-----------+
Table 5
IANA has replaced all references to RFCs 6126 and 7557 in all of the
registries mentioned above with references to this document.
6. Security Considerations 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.
Without additional security mechanisms, Babel trusts any information Without additional security mechanisms, Babel trusts any information
it receives in plaintext UDP datagrams and acts on it. An attacker it receives in plaintext UDP datagrams and acts on it. An attacker
that is present on the local network can impact Babel operation in a that is present on the local network can impact Babel operation in a
variety of ways; for example they can: variety of ways; for example they can:
o spoof a Babel packet, and redirect traffic by announcing a route * spoof a Babel packet, and redirect traffic by announcing a route
with a smaller metric, a larger sequence number, or a longer with a smaller metric, a larger sequence number, or a longer
prefix; prefix;
o spoof a malformed packet, which could cause an insufficiently * spoof a malformed packet, which could cause an insufficiently
robust implementation to crash or interfere with the rest of the robust implementation to crash or interfere with the rest of the
network; network;
o replay a previously captured Babel packet, which could cause * replay a previously captured Babel packet, which could cause
traffic to be redirected, blackholed or otherwise interfere with traffic to be redirected, black-holed, or otherwise interfere with
the network. 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 mitigates the attacks outlined above by link-local IPv6 packets, this mitigates the attacks outlined above by
restricting them to on-link attackers. No such natural protection restricting them to on-link attackers. No such natural protection
exists when Babel packets are carried over IPv4, which is one of the exists when Babel packets are carried over IPv4, which is one of the
reasons why it is recommended to deploy Babel over IPv6 reasons why it is recommended to deploy Babel over IPv6
(Section 3.1). (Section 3.1).
It is usually difficult to ensure that packets arriving at a Babel It is usually difficult to ensure that packets arriving at a Babel
node are trusted, even in the case where the local link is believed node are trusted, even in the case where the local link is believed
to be secure. For that reason, it is RECOMMENDED that all Babel to be secure. For that reason, it is RECOMMENDED that all Babel
traffic be protected by an application-layer cryptographic protocol. traffic be protected by an application-layer cryptographic protocol.
There are currently two suitable mechanisms, which implement There are currently two suitable mechanisms, which implement
different tradeoffs between implementation simplicity and security: different trade-offs between implementation simplicity and security:
o Babel over DTLS [BABEL-DTLS] runs the majority of Babel traffic * Babel over DTLS [RFC8968] runs the majority of Babel traffic over
over DTLS, and leverages DTLS to authenticate nodes and provide DTLS and leverages DTLS to authenticate nodes and provide
confidentiality and integrity protection; confidentiality and integrity protection;
o MAC authentication [BABEL-MAC] appends a message authentication * MAC authentication [RFC8967] appends a message authentication code
code (MAC) to every Babel packet to prove that it originated at a (MAC) to every Babel packet to prove that it originated at a node
node that knows a shared secret, and includes sufficient that knows a shared secret, and includes sufficient additional
additional information to prove that the packet is fresh (not information to prove that the packet is fresh (not replayed).
replayed).
Both mechanisms enable nodes to ignore packets generated by attackers Both mechanisms enable nodes to ignore packets generated by attackers
without the proper credentials. They also ensure integrity of without the proper credentials. They also ensure integrity of
messages and prevent message replay. While Babel-DTLS supports messages and prevent message replay. While Babel-DTLS supports
asymmetric keying and ensures confidentiality, Babel-MAC has a much asymmetric keying and ensures confidentiality, Babel-MAC has a much
more limited scope (see Sections 1.1, 1.2 and 7 of [BABEL-MAC]). more limited scope (see Sections 1.1, 1.2, and 7 of [RFC8967]).
Since Babel-MAC is simpler and more lightweight, it is recommended in Since Babel-MAC is simpler and more lightweight, it is recommended in
preference to Babel-DTLS in deployments where its limitations are preference to Babel-DTLS in deployments where its limitations are
acceptable, i.e., when symmetric keying is sufficient and where the acceptable, i.e., when symmetric keying is sufficient and where the
routing information is not considered confidential. routing information is not considered confidential.
Every implementation of Babel SHOULD implement BABEL-MAC. Every implementation of Babel SHOULD implement BABEL-MAC.
One should be aware that the information that a mobile Babel node One should be aware that the information that a mobile Babel node
announces to the whole routing domain is sufficient to determine the announces to the whole routing domain is sufficient to determine the
mobile node's physical location with reasonable precision, which mobile node's physical location with reasonable precision, which
might cause privacy concerns even if the control traffic is protected might cause privacy concerns even if the control traffic is protected
from unauthenticated attackers by a cryptographic mechanism such as from unauthenticated attackers by a cryptographic mechanism such as
Babel-DTLS. This issue may be mitigated somewhat by using randomly Babel-DTLS. This issue may be mitigated somewhat by using randomly
chosen router-ids and randomly chosen IP addresses, and changing them chosen router-ids and randomly chosen IP addresses, and changing them
often enough. often enough.
7. Acknowledgments 7. References
A number of people have contributed text and ideas to this
specification. The authors are particularly indebted to Matthieu
Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke
Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin
Vigoureux. Earlier versions of this document greatly benefited from
the input of Joel Halpern. The address compression technique was
inspired by [PACKETBB].
8. References
8.1. Normative References
[BABEL-MAC] 7.1. Normative References
Do, C., Kolodziejak, W., and J. Chroboczek, "MAC
authentication for the Babel routing protocol", Internet
Draft draft-ietf-babel-hmac-10, August 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,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC793] Postel, J., "Transmission Control Protocol", RFC 793, [RFC793] Postel, J., "Transmission Control Protocol", STD 7,
DOI 10.17487/RFC0793, September 1981, RFC 793, DOI 10.17487/RFC0793, September 1981,
<https://www.rfc-editor.org/info/rfc793>. <https://www.rfc-editor.org/info/rfc793>.
[RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for
Writing an IANA Considerations Section in RFCs", BCP 26, Writing an IANA Considerations Section in RFCs", BCP 26,
RFC 8126, June 2017. RFC 8126, DOI 10.17487/RFC8126, June 2017,
<https://www.rfc-editor.org/info/rfc8126>.
[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, <https://www.rfc-editor.org/info/rfc8174>.
8.2. Informative References [RFC8967] Dô, C., Kolodziejak, W., and J. Chroboczek, "MAC
Authentication for the Babel Routing Protocol", RFC 8967,
DOI 10.17487/RFC8967, January 2021,
<https://www.rfc-editor.org/info/rfc8967>.
7.2. Informative References
[BABEL-DIVERSITY] [BABEL-DIVERSITY]
Chroboczek, J., "Diversity Routing for the Babel Routing Chroboczek, J., "Diversity Routing for the Babel Routing
Protocol", draft-chroboczek-babel-diversity-routing-01 Protocol", Work in Progress, Internet-Draft, draft-
(work in progress), February 2016. chroboczek-babel-diversity-routing-01, 15 February 2016,
<https://tools.ietf.org/html/draft-chroboczek-babel-
[BABEL-DTLS] diversity-routing-01>.
Decimo, A., Schinazi, D., and J. Chroboczek, "Babel
Routing Protocol over Datagram Transport Layer Security",
Internet Draft draft-ietf-babel-dtls-10, June 2020.
[BABEL-RTT] [BABEL-RTT]
Jonglez, B. and J. Chroboczek, "Delay-based Metric Jonglez, B. and J. Chroboczek, "Delay-based Metric
Extension for the Babel Routing Protocol", draft-ietf- Extension for the Babel Routing Protocol", Work in
babel-rtt-extension-00 (work in progress), April 2019. Progress, Internet-Draft, draft-ietf-babel-rtt-extension-
00, 26 April 2019, <https://tools.ietf.org/html/draft-
ietf-babel-rtt-extension-00>.
[BABEL-SS] [BABEL-SS] Boutier, M. and J. Chroboczek, "Source-Specific Routing in
Boutier, M. and J. Chroboczek, "Source-Specific Routing in Babel", Work in Progress, Internet-Draft, draft-ietf-
Babel", draft-ietf-babel-source-specific-05 (work in babel-source-specific-07, 28 October 2020,
progress), April 2019. <https://tools.ietf.org/html/draft-ietf-babel-source-
specific-07>.
[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: Proceedings of the conference
Architectures, Protocols and Applications 234-244, 1994. on Communications architectures, protocols and
applications, 234-244, DOI 10.1145/190314.190336, October
1994, <https://doi.org/10.1145/190314.190336>.
[DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing [DUAL] Garcia Luna Aceves, J. J., "Loop-free routing using
Computations", IEEE/ACM Transactions on Networking 1:1, diffusing computations", IEEE/ACM Transactions on
February 1993. Networking, 1:1, DOI 10.1109/90.222913, February 1993,
<https://doi.org/10.1109/90.222913>.
[EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, [EIGRP] Albrightson, B., Garcia Luna Aceves, J. J., and J. Boyle,
"EIGRP -- a Fast Routing Protocol Based on Distance "EIGRP -- a Fast Routing Protocol Based on Distance
Vectors", Proc. Interop 94, 1994. Vectors", Proc. Networld/Interop 94, 1994.
[ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A
high-throughput path metric for multi-hop wireless high-throughput path metric for multi-hop wireless
networks", Proc. MobiCom 2003, 2003. networks", MobiCom '03: Proceedings of the 9th annual
international conference on Mobile computing and
networking, 134-146, DOI 10.1145/938985.939000, September
2003, <https://doi.org/10.1145/938985.939000>.
[IEEE802.11] [IEEE802.11]
IEEE, "IEEE Standard for Information technology-- IEEE, "IEEE Standard for Information technology--
Telecommunications and information exchange between Telecommunications and information exchange between
systems Local and metropolitan area networks--Specific systems Local and metropolitan area networks--Specific
requirements Part 11: Wireless LAN Medium Access Control requirements Part 11: Wireless LAN Medium Access Control
(MAC) and Physical Layer (PHY) Specifications", (MAC) and Physical Layer (PHY) Specifications",
IEEE 802.11-2012, DOI 10.1109/ieeestd.2012.6178212, April IEEE 802.11-2012, DOI 10.1109/ieeestd.2012.6178212, April
2012. 2012, <https://doi.org/10.1109/ieeestd.2012.6178212>.
[IEN137] Cohen, D., "On holy wars and a plea for peace", IEN 137, [IEN137] Cohen, D., "On Holy Wars and a Plea for Peace", IEN 137, 1
April 1980. April 1980.
[IS-IS] Standardization, I. O. F., "Information technology -- [IS-IS] International Organization for Standardization,
Telecommunications and information exchange between "Information technology -- Telecommunications and
systems -- Intermediate System to Intermediate System information exchange between systems -- Intermediate
intra-domain routeing information exchange protocol for System to Intermediate System intra-domain routeing
use in conjunction with the protocol for providing the information exchange protocol for use in conjunction with
connectionless-mode network service (ISO 8473)", ISO/ the protocol for providing the connectionless-mode network
IEC 10589:2002, 2002. service (ISO 8473)", ISO/IEC 10589:2002, 2002.
[JITTER] Floyd, S. and V. Jacobson, "The synchronization of [JITTER] Floyd, S. and V. Jacobson, "The Synchronization of
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, DOI 10.1109/90.298431, April
1994, <https://doi.org/10.1109/90.298431>.
[OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<https://www.rfc-editor.org/info/rfc2328>.
[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, DOI 10.17487/RFC5444, February 2009,
<https://www.rfc-editor.org/info/rfc5444>.
[RFC2675] Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms", [RFC2675] Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms",
RFC 2675, DOI 10.17487/RFC2675, August 1999. RFC 2675, DOI 10.17487/RFC2675, August 1999,
<https://www.rfc-editor.org/info/rfc2675>.
[RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-
Demand Distance Vector (AODV) Routing", RFC 3561, Demand Distance Vector (AODV) Routing", RFC 3561,
DOI 10.17487/RFC3561, July 2003, DOI 10.17487/RFC3561, July 2003,
<https://www.rfc-editor.org/info/rfc3561>. <https://www.rfc-editor.org/info/rfc3561>.
[RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, [RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126,
DOI 10.17487/RFC6126, April 2011. DOI 10.17487/RFC6126, April 2011,
<https://www.rfc-editor.org/info/rfc6126>.
[RFC7298] Ovsienko, D., "Babel Hashed Message Authentication Code [RFC7298] Ovsienko, D., "Babel Hashed Message Authentication Code
(HMAC) Cryptographic Authentication", RFC 7298, (HMAC) Cryptographic Authentication", RFC 7298,
DOI 10.17487/RFC7298, July 2014. DOI 10.17487/RFC7298, July 2014,
<https://www.rfc-editor.org/info/rfc7298>.
[RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing [RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing
Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015. Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015,
<https://www.rfc-editor.org/info/rfc7557>.
[RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. [RFC8968] Décimo, A., Schinazi, D., and J. Chroboczek, "Babel
Routing Protocol over Datagram Transport Layer Security",
RFC 8968, DOI 10.17487/RFC8968, January 2021,
<https://www.rfc-editor.org/info/rfc8968>.
[RIP] Malkin, G., "RIP Version 2", STD 56, RFC 2453,
DOI 10.17487/RFC2453, November 1998,
<https://www.rfc-editor.org/info/rfc2453>.
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 a strategies on different interface types. This section describes a
set of strategies that have been found to work well in actual set of strategies that have been found to work well in actual
networks. networks.
In summary, a node maintains per-neighbour statistics about the last In summary, a node maintains per-neighbour statistics about the last
16 received Hello TLVs of each kind (Appendix A.1), it computes costs 16 received Hello TLVs of each kind (Appendix A.1), it computes costs
by using the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and by using the 2-out-of-3 strategy (Appendix A.2.1) on wired links and
ETX (Appendix A.2.2) on wireless links. It uses an additive algebra Expected Transmission Cost (ETX) (Appendix A.2.2) on wireless links.
for metric computation (Section 3.5.2). It uses an additive algebra for metric computation (Section 3.5.2).
A.1. Maintaining Hello History A.1. Maintaining Hello History
For each neighbour, a node maintains two sets of Hello history, one For each neighbour, a node maintains two sets of Hello history, one
for each kind of Hello, and an expected sequence number, one for for each kind of Hello, and an expected sequence number, one for
Multicast and one for Unicast Hellos. Each Hello history is a vector Multicast and one for Unicast Hellos. Each Hello history is a vector
of 16 bits, where a 1 value represents a received Hello, and a 0 of 16 bits, where a 1 value represents a received Hello, and a 0
value a missed Hello. For each kind of Hello, the expected sequence value a missed Hello. For each kind of Hello, the expected sequence
number, written ne, is the sequence number that is expected to be number, written ne, is the sequence number that is expected to be
carried by the next received Hello from this neighbour. carried by the next received Hello from 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 * if the two differ by more than 16 (modulo 2^(16)), then the
node has probably rebooted and lost its sequence number; the whole sending node has probably rebooted and lost its sequence number;
associated neighbour table entry is flushed and a new one is the whole associated neighbour table entry is flushed and a new
created; one is created;
o otherwise, if the received nr is smaller (modulo 2^16) than the * otherwise, if the received nr is smaller (modulo 2^(16)) than the
expected sequence number ne, then the sending node has increased expected sequence number ne, then the sending node has increased
its Hello interval without us noticing; the receiving node removes its Hello interval without our noticing; the receiving node
the last (ne - nr) entries from this neighbour's Hello history (we removes the last (ne - nr) entries from this neighbour's Hello
"undo history"); history (we "undo history");
o otherwise, if nr is larger (modulo 2^16) than ne, then the sending * otherwise, if nr is larger (modulo 2^(16)) than ne, then the
node has decreased its Hello interval, and some Hellos were lost; sending node has decreased its Hello interval, and some Hellos
the receiving node adds (nr - ne) 0 bits to the Hello history (we were lost; the receiving node adds (nr - ne) 0 bits to the Hello
"fast-forward"). history (we "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 with a neighbour expires, the
local node adds a 0 bit to the corresponding 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 describes two algorithms suitable for computing costs This section describes two algorithms suitable for computing costs
(Section 3.4.3) based on Hello history. Appendix A.2.1 applies to (Section 3.4.3) based on Hello history. Appendix A.2.1 applies to
wired links, and Appendix A.2.2 to wireless links. RECOMMENDED wired links and Appendix A.2.2 to wireless links. RECOMMENDED
default values of the parameters that appear in these algorithms are default values of the parameters that appear in these algorithms are
given in Appendix B. given in Appendix B.
A.2.1. k-out-of-j A.2.1. k-out-of-j
K-out-of-j link sensing is suitable for wired links that are either K-out-of-j link sensing is suitable for wired links that are either
up, in which case they only occasionally drop a packet, or down, in up, in which case they only occasionally drop a packet, or down, in
which case they drop all packets. which case they drop all packets.
The k-out-of-j strategy is parameterised by two small integers k and The k-out-of-j strategy is parameterised by two small integers k and
j, such that 0 < k <= j, and the nominal link cost, a constant C >= j, such that 0 < k <= j, and the nominal link cost, a constant C >=
1. A node keeps a history of the last j hellos; if k or more of 1. A node keeps a history of the last j hellos; if k or more of
those have been correctly received, the link is assumed to be up, and those have been correctly received, the link is assumed to be up, and
the rxcost is set to C; otherwise, the link is assumed to be down, the rxcost is set to C; otherwise, the link is assumed to be down,
and the rxcost is set to infinity. and the rxcost is set to infinity.
Since Babel supports two kinds of Hellos, a Babel node performs k- Since Babel supports two kinds of Hellos, a Babel node performs k-
out-of-j twice for each neighbour, once on the Unicast and once on out-of-j twice for each neighbour, once on the Unicast Hello history
the Multicast Hello history. If either of the instances of k-out- and once on the Multicast Hello history. If either of the instances
of-j indicates that the link is up, then the link is assumed to be of k-out-of-j indicates that the link is up, then the link is assumed
up, and the rxcost is set to C; if both instances indicate that the to be up, and the rxcost is set to C; if both instances indicate that
link is down, then the link is assumed to be down, and the rxcost is the link is down, then the link is assumed to be down, and the rxcost
set to infinity. In other words, the resulting rxcost is the minimum is set to infinity. In other words, the resulting rxcost is the
of the rxcosts yielded by the two instances of k-out-of-j link minimum of the rxcosts yielded by the two instances of k-out-of-j
sensing. link sensing.
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; * cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;
o cost = txcost otherwise. * 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.
The Expected Transmission Cost algorithm, or ETX [ETX], is a simple The Expected Transmission Cost algorithm, or ETX [ETX], is a simple
link-quality estimation algorithm that is designed to work well with link quality estimation algorithm that is designed to work well with
the IEEE 802.11 MAC [IEEE802.11]. By default, the IEEE 802.11 MAC the IEEE 802.11 MAC [IEEE802.11]. By default, the IEEE 802.11 MAC
performs Automatic Repeat Query (ARQ) and rate adaptation on unicast performs Automatic Repeat Query (ARQ) and rate adaptation on unicast
frames, but not on multicast frames, which are sent at a fixed rate frames, but not on multicast frames, which are sent at a fixed rate
with no ARQ; therefore, measuring the loss rate of multicast frames with no ARQ; therefore, measuring the loss rate of multicast frames
yields a useful estimate of a link's quality. yields a 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. Let an exponential average, or some combination of both approaches. Let
rxcost be 256 / beta. 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. Route selection and hysteresis A.3. Route Selection and Hysteresis
Route selection (Section 3.6) is the process by which a node selects Route selection (Section 3.6) is the process by which a node selects
a single route among the routes that it has available towards a given a single route among the routes that it has available towards a given
destination. With Babel, any route selection procedure that only destination. With Babel, any route selection procedure that only
ever chooses feasible routes with a finite metric will yield a set of ever chooses feasible routes with a finite metric will yield a set of
loop-free routes; however, in the presence of continuously variable loop-free routes; however, in the presence of continuously variable
metrics such as ETX (Appendix A.2.2), a naive route selection metrics such as ETX (Appendix A.2.2), a naive route selection
procedure might lead to persistent oscillations. Such oscillations procedure might lead to persistent oscillations. Such oscillations
can be limited or avoided altogether by implementing hysteresis can be limited or avoided altogether by implementing hysteresis
within the route selection algorithm, i.e., by making the route within the route selection algorithm, i.e., by making the route
skipping to change at page 59, line 48 skipping to change at line 2775
smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R) smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R)
as an exponentially smoothed average (see Section 3.7 of [RFC793]) of as an exponentially smoothed average (see Section 3.7 of [RFC793]) of
m(R) with a time constant equal to the Hello interval multiplied by a m(R) with a time constant equal to the Hello interval multiplied by a
small number such as 3). If no route to a given destination is small number such as 3). If no route to a given destination is
selected, then select the route with the smallest metric, ignoring selected, then select the route with the smallest metric, ignoring
the smoothed metric. If a route R is selected, then switch to a the smoothed metric. If a route R is selected, then switch to a
route R' only when both m(R') < m(R) and ms(R') < ms(R). route R' only when both m(R') < m(R) and ms(R') < ms(R).
Intuitively, the smoothed metric is a long-term estimate of the Intuitively, the smoothed metric is a long-term estimate of the
quality of a route. The algorithm above works by only switching quality of a route. The algorithm above works by only switching
routes when both the instantaneous and the long-term estimate of the routes when both the instantaneous and the long-term estimates of the
route's quality indicate that switching is profitable. route's quality indicate that switching is profitable.
Appendix B. Protocol parameters Appendix B. Protocol Parameters
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 instances of Babel mobility events and protocol overhead. Two instances of Babel
running with different time constants will interoperate, although the running with different time constants will interoperate, although the
resulting worst-case convergence time will be dictated by the slower resulting worst-case convergence time will be dictated by the slower
of the two. of the two.
The Hello interval is the most important time constant: an outage or The Hello interval is the most important time constant: an outage or
a mobility event is detected within 1.5 to 3.5 Hello intervals. Due a mobility event is detected within 1.5 to 3.5 Hello intervals. Due
to Babel's use of a redundant route table, and due to its reliance on to Babel's use of a redundant route table, and due to its reliance on
triggered updates and explicit requests, the Update interval has triggered updates and explicit requests, the Update interval has
little influence on the time needed to reconverge after an outage: in little influence on the time needed to reconverge after an outage: in
practice, it only has a significant effect on the time needed to practice, it only has a significant effect on the time needed to
acquire new routes after a mobility event. While the protocol allows acquire new routes after a mobility event. While the protocol allows
intervals as low as 10ms, such low values would cause significant intervals as low as 10 ms, such low values would cause significant
amounts of protocol traffic for little practical benefit. amounts of protocol traffic for little practical benefit.
The following values have been found to work well in a variety of The following values have been found to work well in a variety of
environments, and are therefore RECOMMENDED default values: environments and are therefore RECOMMENDED default values:
Multicast Hello Interval: 4 seconds. Multicast Hello interval: 4 seconds.
Unicast Hello Interval: infinite (no Unicast Hellos are sent). Unicast Hello interval: infinite (no Unicast Hellos are sent).
Link cost: estimated using ETX on wireless links; 2-out-of-3 with Link cost: estimated using ETX on wireless links; 2-out-of-3 with
C=96 on wired links. C=96 on wired links.
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
on lossy links (as determined from the Hello history), but only Hello on lossy links (as determined from the Hello
with every third Multicast Hello on lossless links. history), but only with every third Multicast Hello on
lossless links.
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.
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.
Urgent timeout: 0.2 seconds. Urgent timeout: 0.2 seconds.
Source GC time: 3 minutes. Source GC time: 3 minutes.
Appendix C. Route filtering Appendix C. Route Filtering
Route filtering is a procedure where an instance of a routing Route filtering is a procedure where an instance of a routing
protocol either discards some of the routes announced by its protocol either discards some of the routes announced by its
neighbours, or learns them with a metric that is higher than what neighbours or learns them with a metric that is higher than what
would be expected. Like all distance-vector protocols, Babel has the would be expected. Like all distance-vector protocols, Babel has the
ability to apply arbitrary filtering to the routes it learns, and ability to apply arbitrary filtering to the routes it learns, and
implementations of Babel that apply different sets of filtering rules implementations of Babel that apply different sets of filtering rules
will interoperate without causing routing loops. The protocol's will interoperate without causing routing loops. The protocol's
ability to perform route filtering is a consequence of the latitude 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 given in Section 3.5.2: Babel can use any metric that is strictly
monotonic, including one that assigns an infinite metric to a monotonic, including one that assigns an infinite metric to a
selected subset of routes. (See also Section 3.8.1, where requests selected subset of routes. (See also Section 3.8.1, where requests
for nonexistent routes are treated in the same way as requests for for nonexistent routes are treated in the same way as requests for
routes with infinite metric.) routes with infinite metric.)
skipping to change at page 61, line 36 skipping to change at line 2856
Route filtering is a useful tool, since it allows fine-grained tuning Route filtering is a useful tool, since it allows fine-grained tuning
of the routing decisions made by the routing protocol. Accordingly, of the routing decisions made by the routing protocol. Accordingly,
some implementations of Babel implement a rich configuration language some implementations of Babel implement a rich configuration language
that allows applying filtering to sets of routes defined, for that allows applying filtering to sets of routes defined, for
example, by incoming interface and destination prefix. example, by incoming interface and destination prefix.
In order to limit the consequences of misconfiguration, Babel In order to limit the consequences of misconfiguration, Babel
implementations provide a reasonable set of default filtering rules implementations provide a reasonable set of default filtering rules
even when they don't allow configuration of filtering by the user. even when they don't allow configuration of filtering by the user.
At a minimum, they discard routes with a destination prefix in 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. 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 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; * increasing the version number in the packet header;
o defining new TLVs; * defining new TLVs;
o defining new sub-TLVs (with or without the mandatory bit set); * defining new sub-TLVs (with or without the mandatory bit set);
o defining new AEs; * defining new AEs;
o using the packet trailer. * 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 choosing a particular encoding. in choosing 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
the new version is not backwards compatible with the original the new version is not backwards compatible with the original
protocol. protocol.
In many cases, an extension could be implemented either by defining a In many cases, an extension could be implemented either by defining a
new TLV, or by adding a new sub-TLV to an existing TLV. For example, new TLV or by adding a new sub-TLV to an existing TLV. For example,
an extension whose purpose is to attach additional data to route an extension whose purpose is to attach additional data to route
updates can be implemented either by creating a new "enriched" Update updates can be implemented either by creating a new "enriched" Update
TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by TLV, by adding a nonmandatory sub-TLV to the Update TLV, or by adding
adding a mandatory sub-TLV. a mandatory sub-TLV.
The various encodings are treated differently by implementations that The various encodings are treated differently by implementations that
do not understand the extension. In the case of a new TLV or of a do not understand the extension. In the case of a new TLV or of a
sub-TLV with the mandatory bit set, the whole TLV is ignored by sub-TLV with the mandatory bit set, the whole TLV is ignored by
implementations that do not implement the extension, while in the implementations that do not implement the extension, while in the
case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, case of a nonmandatory sub-TLV, the TLV is parsed and acted upon, and
and only the unknown sub-TLV is silently ignored. Therefore, a non- only the unknown sub-TLV is silently ignored. Therefore, a
mandatory sub-TLV should be used by extensions that extend the Update nonmandatory sub-TLV should be used by extensions that extend the
in a compatible manner (the extension data may be silently ignored), Update in a compatible manner (the extension data may be silently
while a mandatory sub-TLV or a new TLV must be used by extensions ignored), while a mandatory sub-TLV or a new TLV must be used by
that make incompatible extensions to the meaning of the TLV (the extensions that make incompatible extensions to the meaning of the
whole TLV must be thrown away if the extension data is not TLV (the whole TLV must be thrown away if the extension data is not
understood). understood).
Experience shows that the need for additional data tends to crop up Experience shows that the need for additional data tends to crop up
in the most unexpected places. Hence, it is recommended that in the most unexpected places. Hence, it is recommended that
extensions that define new TLVs should make them self-terminating, extensions that define new TLVs should make them self-terminating and
and allow attaching sub-TLVs to them. allow attaching sub-TLVs to them.
Adding a new AE is essentially equivalent to adding a new TLV: Update Adding a new AE is essentially equivalent to adding a new TLV: Update
TLVs with an unknown AE are ignored, just like unknown TLVs. TLVs with an unknown AE are ignored, just like unknown TLVs.
However, adding a new AE is more involved than adding a new TLV, However, adding a new AE is more involved than adding a new TLV,
since it creates a new set of compression state. Additionally, since since it creates a new set of compression state. Additionally, since
the Next Hop TLV creates state specific to a given address family, as the Next Hop TLV creates state specific to a given address family, as
opposed to a given AE, a new AE for a previously defined address opposed to a given AE, a new AE for a previously defined address
family must not be used in the Next Hop TLV if backwards family must not be used in the Next Hop TLV if backwards
compatibility is required. A similar issue arises with Update TLVs compatibility is required. A similar issue arises with Update TLVs
with unknown AEs establishing a new router-id (due to the Router-Id with unknown AEs establishing a new router-id (due to the Router-Id
flag being set). Therefore, defining new AEs must be done with care flag being set). Therefore, defining new AEs must be done with care
if compatibility with unextended implementations is required. if compatibility with unextended implementations is required.
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 E. 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 dual-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 20,000-entry
route table and the associated source table. route table and the associated source table.
Babel is also a reasonably simple protocol. One complete 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 re-announce any routes that it has learnt from its
neighbours, and always prefers the direct route to a directly neighbours, and always prefers the direct route to a directly
attached prefix to a route learned over the Babel protocol, even when attached prefix to a route learnt over the Babel protocol, even when
the prefixes are the same. It may either maintain a full routing the prefixes are the same. It may either maintain a full routing
table, or simply select a default gateway through any one of its table or simply select a default gateway through any one of its
neighbours that announces a default route. Since a stub neighbours that announces a default route. Since a stub
implementation never forwards packets except from or to a directly implementation never forwards packets except from or to a directly
attached link, it cannot possibly participate in a routing loop, and attached link, it cannot possibly participate in a routing loop, and
hence it need not evaluate the feasibility condition or maintain a hence it need not evaluate the feasibility condition or maintain a
source table. 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, and it should be able to reply to for routes that it announces, and it should be able to reply to route
route requests. 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 1,000 lines of C code and compile to 13 KB of
text on 32-bit CISC architecture. text on 32-bit CISC architecture.
Appendix F. Compatibility with previous versions Appendix F. Compatibility with Previous Versions
The protocol defined in this document is a successor to the protocol The protocol defined in this document is a successor to the protocol
defined in [RFC6126] and [RFC7557]. While the two protocols are not defined in [RFC6126] and [RFC7557]. While the two protocols are not
entirely compatible, the new protocol has been designed so that it entirely compatible, the new protocol has been designed so that it
can be deployed in existing RFC 6126 networks without requiring a can be deployed in existing RFC 6126 networks without requiring a
flag day. flag day.
There are three optional features that make this protocol There are three optional features that make this protocol
incompatible with its predecessor. First of all, RFC 6126 did not incompatible with its predecessor. First of all, RFC 6126 did not
define Unicast hellos (Section 3.4.1), and an implementation of RFC define Unicast Hellos (Section 3.4.1), and an implementation of RFC
6126 will mis-interpret a Unicast Hello for a Multicast one; since 6126 will misinterpret a Unicast Hello for a Multicast one; since the
the sequence number space of Unicast Hellos is distinct from the sequence number space of Unicast Hellos is distinct from the sequence
sequence space of Multicast Hellos, sending a Unicast Hello to an number space of Multicast Hellos, sending a Unicast Hello to an
implementation of RFC 6126 will confuse its link quality estimator. implementation of RFC 6126 will confuse its link quality estimator.
Second, RFC 6126 did not define unscheduled Hellos, and an Second, RFC 6126 did not define unscheduled Hellos, and an
implementation of RFC 6126 will mis-parse Hellos with an interval implementation of RFC 6126 will mis-parse Hellos with an interval
equal to 0. Finally, RFC 7557 did not define mandatory sub-TLVs equal to 0. Finally, RFC 7557 did not define mandatory sub-TLVs
(Section 4.4), and thus, an implementation of RFCs 6126 and 7557 will (Section 4.4), and thus an implementation of RFCs 6126 and 7557 will
not correctly ignore a TLV that carries an unknown mandatory sub-TLV; not correctly ignore a TLV that carries an unknown mandatory sub-TLV;
depending on the sub-TLV, this might cause routing pathologies. depending on the sub-TLV, this might cause routing pathologies.
An implementation of this specification that never sends Unicast or An implementation of this specification that never sends Unicast or
unscheduled Hellos and doesn't implement any extensions that use unscheduled Hellos and doesn't implement any extensions that use
mandatory sub-TLVs is safe to deploy in a network in which some nodes mandatory sub-TLVs is safe to deploy in a network in which some nodes
implement the protocol described in RFCs 6126 and 7557. implement the protocol described in RFCs 6126 and 7557.
Two changes need to be made to an implementation of RFCs 6126 and Two changes need to be made to an implementation of RFCs 6126 and
7557 so that it can safely interoperate in all cases with 7557 so that it can safely interoperate in all cases with
implementations of this protocol. First, it needs to be modified to implementations of this protocol. First, it needs to be modified
either ignore or process Unicast and unscheduled Hellos. Second, it either to ignore or to process Unicast and unscheduled Hellos.
needs to be modified to parse sub-TLVs of all the TLVs that it Second, it needs to be modified to parse sub-TLVs of all the TLVs
understands and that allow sub-TLVs, and to ignore the TLV if an that it understands and that allow sub-TLVs, and to ignore the TLV if
unknown mandatory sub-TLV is found. It is not necessary to parse an unknown mandatory sub-TLV is found. It is not necessary to parse
unknown TLVs, as these are ignored in any case. unknown TLVs, as these are ignored in any case.
There are other changes, but these are not of a nature to prevent There are other changes, but these are not of a nature to prevent
interoperability: interoperability:
o the conditions on route acquisition (Section 3.5.3) have been * the conditions on route acquisition (Section 3.5.3) have been
relaxed; relaxed;
o route selection should no longer use the route's sequence number * route selection should no longer use the route's sequence number
(Section 3.6); (Section 3.6);
o the format of the packet trailer has been defined (Section 4.2); * the format of the packet trailer has been defined (Section 4.2);
o router-ids with a value of all-zeros or all-ones have been * router-ids with a value of all-zeros or all-ones have been
forbidden (Section 4.1.3); forbidden (Section 4.1.3);
o the compression state is now specific to an address family rather * the compression state is now specific to an address family rather
than an address encoding (Section 4.5); than an address encoding (Section 4.5);
o packet pacing is now recommended (Section 3.1). * packet pacing is now recommended (Section 3.1).
Appendix G. Changes from previous versions
[RFC Editor: Please delete this section before publication.]
G.1. Changes since RFC 6126
o Changed UDP port number to 6696.
o Consistently use router-id rather than id.
o Clarified that the source garbage collection timer is reset after
sending an update even if the entry was not modified.
o In section "Seqno Requests", fixed an erroneous "route request".
o In the description of the Seqno Request TLV, added the description
of the Router-Id field.
o Made router-ids all-0 and all-1 forbidden.
G.2. Changes since draft-ietf-babel-rfc6126bis-00
o Added security considerations.
G.3. Changes since draft-ietf-babel-rfc6126bis-01
o Integrated the format of sub-TLVs.
o Mentioned for each TLV whether it supports sub-TLVs.
o Added Appendix D.
o Added a mandatory bit in sub-TLVs.
o Changed compression state to be per-AF rather than per-AE.
o Added implementation hint for the routing table.
o Clarified how router-ids are computed when bit 0x40 is set in
Updates.
o Relaxed the conditions for sending requests, and tightened the
conditions for forwarding requests.
o Clarified that neighbours should be acquired at some point, but it
doesn't matter when.
G.4. Changes since draft-ietf-babel-rfc6126bis-02
o Added Unicast Hellos.
o Added unscheduled (interval-less) Hellos.
o Changed Appendix A to consider Unicast and unscheduled Hellos.
o Changed Appendix B to agree with the reference implementation.
o Added optional algorithm to avoid the hold time.
o Changed the table of pending seqno requests to be indexed by
router-id in addition to prefixes.
o Relaxed the route acquisition algorithm.
o Replaced minimal implementations by stub implementations.
o Added acknowledgments section.
G.5. Changes since draft-ietf-babel-rfc6126bis-03
o Clarified that all the data structures are conceptual.
o Made sending and receiving Multicast Hellos a SHOULD, avoids
expressing any opinion about Unicast Hellos.
o Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4).
o Made hold-time into a SHOULD rather than MUST.
o Clarified that Seqno Requests are for a finite-metric Update.
o Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV
that allows sub-TLVs.
o Updated IANA Considerations.
o Updated Security Considerations.
o Renamed routing table back to route table.
o Made buffering outgoing updates a SHOULD.
o Weakened advice to use modified EUI-64 in router-ids.
o Added information about sending requests to Appendix B.
o A number of minor wording changes and clarifications.
G.6. Changes since draft-ietf-babel-rfc6126bis-03
Minor editorial changes.
G.7. Changes since draft-ietf-babel-rfc6126bis-04
o Renamed isotonicity to left-distributivity.
o Minor clarifications to unicast hellos.
o Updated requirements boilerplate to RFC 8174.
o Minor editorial changes.
G.8. Changes since draft-ietf-babel-rfc6126bis-05
o Added information about the packet trailer, now that it is used by
draft-ietf-babel-hmac.
G.9. Changes since draft-ietf-babel-rfc6126bis-06
o Added references to security documents.
G.10. Changes since draft-ietf-babel-rfc6126bis-07
o Added list of obsoleted drafts to the abstract.
o Updated references.
G.11. Changes since draft-ietf-babel-rfc6126bis-08
o Added recommendation that route selection should not take seqnos
into account.
G.12. Changes since draft-ietf-babel-rfc6126bis-09
o Editorial changes only.
G.13. Changes since draft-ietf-babel-rfc6126bis-10
o Editorial changes only.
G.14. Changes since draft-ietf-babel-rfc6126bis-11
o Added recommendation that control traffic should be carried over
IPv6 only.
G.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.
G.16. Changes since draft-ietf-babel-rfc6126bis-13
o Added a section about compatibility with 6126.
o Added AE registry to IANA considerations.
o Replaced Babel-HMAC with Babel-MAC, consistent with the change in
draft-ietf-babel-hmac.
o Removed section about external sources of willingness; filtering
is a better approach.
o Added recommendation to use a cost of 96 on wired links.
o Editorial changes.
G.17. Changes since draft-ietf-babel-rfc6126bis-14
o Added unscheduled Hellos to compatibility considerations.
o Created new appendix about route selection.
o Reworked security considerations.
o Added some comments about packet pacing and low update intervals.
G.18. Changes since draft-ietf-babel-rfc6126bis-15
o Implementing Babel-MAC is now recommended.
G.19. Changes since draft-ietf-babel-rfc6126bis-16
o Make the values in Appendix B normatively recommended defaults.
G.20. Changes since draft-ietf-babel-rfc6126bis-17
o Hysteresis in route selection is now RECOMMENDED.
o Additive metric algebra is now RECOMMENDED default.
o 2-out-of-3 cost computation is now RECOMMENDED on LANs.
o Reference to RFC 793 Section 3.7 added as exponential smoothing
example.
G.21. Changes since draft-ietf-babel-rfc6126bis-18
o Reserved Address Encodings 224-254 for Experimental Use, and 255
for future expansion.
G.22. Changes since draft-ietf-babel-rfc6126bis-19
o Mention that multi-octet fields are in big-endian. Acknowledgments
o Minor typos and clarifications. A number of people have contributed text and ideas to this
specification. The authors are particularly indebted to Matthieu
Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke
Høiland-Jørgensen, Benjamin Kaduk, Joao Sobrinho, and Martin
Vigoureux. The previous version of this specification [RFC6126]
greatly benefited from the input of Joel Halpern. The address
compression technique was inspired by [PACKETBB].
Authors' Addresses 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
David Schinazi David Schinazi
Google LLC Google LLC
1600 Amphitheatre Parkway 1600 Amphitheatre Parkway
Mountain View, California 94043 Mountain View, California 94043
USA United States of America
Email: dschinazi.ietf@gmail.com Email: dschinazi.ietf@gmail.com
 End of changes. 298 change blocks. 
893 lines changed or deleted 666 lines changed or added

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