draft-ietf-babel-rfc6126bis-17.txt   draft-ietf-babel-rfc6126bis-18.txt 
Network Working Group J. Chroboczek Network Working Group J. Chroboczek
Internet-Draft IRIF, University of Paris-Diderot Internet-Draft IRIF, University of Paris-Diderot
Obsoletes: 6126,7557 (if approved) D. Schinazi Obsoletes: 6126,7557 (if approved) D. Schinazi
Intended status: Standards Track Google LLC Intended status: Standards Track Google LLC
Expires: August 8, 2020 February 05, 2020 Expires: February 3, 2021 August 2, 2020
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-17 draft-ietf-babel-rfc6126bis-18
Abstract Abstract
Babel is a loop-avoiding distance-vector routing protocol that is Babel is a loop-avoiding distance-vector routing protocol that is
robust and efficient both in ordinary wired networks and in wireless robust and efficient both in ordinary wired networks and in wireless
mesh networks. This document describes the Babel routing protocol, mesh networks. This document describes the Babel routing protocol,
and obsoletes RFCs 6126 and 7557. and obsoletes RFCs 6126 and 7557.
Status of This Memo Status of This Memo
skipping to change at page 1, line 34 skipping to change at page 1, line 34
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on August 8, 2020. This Internet-Draft will expire on February 3, 2021.
Copyright Notice Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 27 skipping to change at page 2, line 27
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 11 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 11
2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 12 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 12
3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12
3.1. Message Transmission and Reception . . . . . . . . . . . 12 3.1. Message Transmission and Reception . . . . . . . . . . . 12
3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 13 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 13
3.3. Acknowledgments and acknowledgment requests . . . . . . . 17 3.3. Acknowledgments and acknowledgment requests . . . . . . . 17
3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 18 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 18
3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 21 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 21
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 25 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 25
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 26
3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28 3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 31 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 32
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34
4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 34 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 35
4.5. Parser state and encoding of updates . . . . . . . . . . 35 4.5. Parser state and encoding of updates . . . . . . . . . . 35
4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 36 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 37
4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 47 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 48
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 49
6. Security Considerations . . . . . . . . . . . . . . . . . . . 51 6. Security Considerations . . . . . . . . . . . . . . . . . . . 52
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 52 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 53
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 53
8.1. Normative References . . . . . . . . . . . . . . . . . . 53 8.1. Normative References . . . . . . . . . . . . . . . . . . 53
8.2. Informative References . . . . . . . . . . . . . . . . . 53 8.2. Informative References . . . . . . . . . . . . . . . . . 54
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 55 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 56
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 55 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 56
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 56 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 57
A.3. Metric computation . . . . . . . . . . . . . . . . . . . 58 A.3. Route selection and hysteresis . . . . . . . . . . . . . 59
A.4. Route selection . . . . . . . . . . . . . . . . . . . . . 58
Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 59 Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 59
Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 60 Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 60
Appendix D. Considerations for protocol extensions . . . . . . . 61 Appendix D. Considerations for protocol extensions . . . . . . . 61
Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 62 Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 62
Appendix F. Compatibility with previous versions . . . . . . . . 63 Appendix F. Compatibility with previous versions . . . . . . . . 63
Appendix G. Changes from previous versions . . . . . . . . . . . 64 Appendix G. Changes from previous versions . . . . . . . . . . . 64
G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 64 G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 64
G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 65 G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 65
G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 65 G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 65
G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 65 G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 65
skipping to change at page 3, line 22 skipping to change at page 3, line 21
G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 67 G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 67
G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 67 G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 67
G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 67 G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 67
G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 67 G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 67
G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 67 G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 67
G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 67 G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 67
G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 67 G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 67
G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 67 G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 67
G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 68 G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 68
G.17. Changes since draft-ietf-babel-rfc6126bis-14 . . . . . . 68 G.17. Changes since draft-ietf-babel-rfc6126bis-14 . . . . . . 68
G.18. Changes since draft-ietf-babel-rfc6126bis-15 . . . . . . 68 G.18. Changes since draft-ietf-babel-rfc6126bis-15 . . . . . . 69
G.19. Changes since draft-ietf-babel-rfc6126bis-16 . . . . . . 69 G.19. Changes since draft-ietf-babel-rfc6126bis-16 . . . . . . 69
G.20. Changes since draft-ietf-babel-rfc6126bis-17 . . . . . . 69
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 69 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 69
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].
skipping to change at page 4, line 31 skipping to change at page 4, line 31
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
that is low on battery may choose to use larger time constants (hello that is low on battery may choose to use larger time constants (hello
and update intervals, etc.) than a node that has access to wall and update intervals, etc.) than a node that has access to wall
power. Conversely, a node that detects high levels of mobility may power. Conversely, a node that detects high levels of mobility may
choose to use smaller time constants. The ability to build such choose to use smaller time constants. The ability to build such
heterogeneous networks makes Babel particularly adapted to the heterogeneous networks makes Babel particularly adapted to the
unmanaged and wireless environment. unmanaged or wireless environment.
Finally, Babel is a hybrid routing protocol, in the sense that it can Finally, Babel is a hybrid routing protocol, in the sense that it can
carry routes for multiple network-layer protocols (IPv4 and IPv6), carry routes for multiple network-layer protocols (IPv4 and IPv6),
regardless of which protocol the Babel packets are themselves being regardless of which protocol the Babel packets are themselves being
carried over. carried over.
1.2. Limitations 1.2. Limitations
Babel has two limitations that make it unsuitable for use in some Babel has two limitations that make it unsuitable for use in some
environments. First, Babel relies on periodic routing table updates environments. First, Babel relies on periodic routing table updates
skipping to change at page 12, line 34 skipping to change at page 12, line 34
the former route has been retracted by all of B's neighbours the former route has been retracted by all of B's neighbours
(Section 3.5.4). (Section 3.5.4).
3. Protocol Operation 3. Protocol Operation
Every Babel speaker is assigned a router-id, which is an arbitrary Every Babel speaker is assigned a router-id, which is an arbitrary
string of 8 octets that is assumed unique across the routing domain. string of 8 octets that is assumed unique across the routing domain.
For example, router-ids could be assigned randomly, or they could be For example, router-ids could be assigned randomly, or they could be
derived from a link-layer address. (The protocol encoding is derived from a link-layer address. (The protocol encoding is
slightly more compact when router-ids are assigned in the same manner slightly more compact when router-ids are assigned in the same manner
as the IPv6 layer assigns host IDs, see the definition of the "R" as the IPv6 layer assigns host IDs; see the definition of the "R"
flag in Section 4.6.9.) flag in Section 4.6.9.)
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 below). Each Babel packet consists of zero or
more TLVs. Most TLVs may contain sub-TLVs. more TLVs. Most TLVs may contain sub-TLVs.
The protocol's control traffic can be carried indifferently over IPv6 The protocol's control traffic can be carried indifferently over IPv6
or over IPv4, and prefixes of either address family can be announced or over IPv4, and prefixes of either address family can be announced
skipping to change at page 13, line 29 skipping to change at page 13, line 29
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.2), 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 Acknowledgements (Section 4.6.4), Updates (Section 3.7) and IHUs
(Section 3.4.2), then the TLV MUST be sent early enough to meet the (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
skipping to change at page 21, line 5 skipping to change at page 21, line 5
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; o the cost is strictly positive;
o if no Hello TLVs of either kind were received recently, then the o 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. o if the txcost is infinite, then the cost is infinite.
Note that while this document does not constrain cost computation any See Appendix A.2 for RECOMMENDED strategies for computing a link's
further, not all cost computation strategies will give good results. cost.
See Appendix A.2 for examples of strategies for computing a link's
cost that are known to work well in practice.
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.
skipping to change at page 22, line 50 skipping to change at page 22, line 49
neighbour MUST only satisfy the following conditions: neighbour MUST only satisfy the following conditions:
o if c is infinite, then M(c, m) is infinite; o if c is infinite, then M(c, m) is infinite;
o M is strictly monotonic: M(c, m) > m. o M is strictly monotonic: M(c, m) > m.
Additionally, the metric SHOULD satisfy the following condition: Additionally, the metric SHOULD satisfy the following condition:
o M is left-distributive: if m <= m', then M(c, m) <= M(c, m'). o M is left-distributive: if m <= m', then M(c, m) <= M(c, m').
Note that while strict monotonicity is essential to the integrity of While strict monotonicity is essential to the integrity of the
the network (persistent routing loops may arise if it is not network (persistent routing loops may arise if it is not satisfied),
satisfied), left distributivity is not: if it is not satisfied, Babel left distributivity is not: if it is not satisfied, Babel will still
will still converge to a loop-free configuration, but might not reach converge to a loop-free configuration, but might not reach a global
a global optimum (in fact, a global optimum may not even exist). optimum (in fact, a global optimum may not even exist).
As with cost computation, not all strategies for computing route The conditions above are easily satisfied by using the additive
metrics will give good results. In particular, some metrics are more metric, i.e., by defining M(c, m) = c + m. Since the additive metric
likely than others to lead to routing instabilities (route flapping). is useful with a large range of cost computation strategies, it is
In Appendix A.3, we give an number of examples of strictly monotonic, the RECOMMENDED default. See also Appendix C, which describes a
left-distributive routing metrics that are known to work well in technique that makes it possible to tweak the values of individual
practice. See also Appendix C, which describes a useful way to make metrics without running the risk of creating routing loops.
the metric computation configurable by a network administrator.
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; o if the update is unfeasible, it MAY be ignored;
skipping to change at page 25, line 20 skipping to change at page 25, line 20
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 o a route with infinite metric (a retracted route) is never
selected; selected;
o an unfeasible route is never selected. o an unfeasible route is never selected.
Babel nodes using different route selection strategies will
interoperate and not create routing loops as long as these two
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 blackholes
if the metric being used is not left-distributive (Section 3.5.2). if the metric being used is not left-distributive (Section 3.5.2).
The obvious route selection strategy is to choose for each The obvious route selection strategy is to pick, for every
destination the feasible route with lowest metric. However, with destination, the feasible route with minimal metric. When all
continuously varying costs and metrics this simple strategy will in metrics are stable, this approach ensures convergence to a tree of
some cases lead to route oscillations. See Appendix A.4 for a shortest paths (assuming that the metric is left-distributive, see
discussion of the issues and suggested strategies for dealing with Section 3.5.2). There are two reasons, however, why this strategy
them. may lead to instability in the presence of continuously varying
metrics. First, if two parallel routes oscillate around a common
value, then the smallest metric strategy will keep switching between
the two. Second, when a route is selected, congestion along it
increases, which might increase packet loss, which in turn could
cause its metric to increase; this is a feedback loop, of the kind
that is prone to causing persistent oscillations.
In order to limit this kind of instabilities, a route selection
strategy SHOULD include some form of hysteresis, i.e., be sensitive
to a route's history: if a route is currently selected, then the
strategy should only switch to a different route if the latter has
been consistently good for some period of time. A RECOMMENDED
hysteresis 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 32, line 18 skipping to change at page 32, line 31
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. NOT be sent in IPv6 Jumbograms [RFC2675].
4.1. Data Types 4.1. Data Types
4.1.1. Interval 4.1.1. Interval
Relative times are carried as 16-bit values specifying a number of Relative times are carried as 16-bit values specifying a number of
centiseconds (hundredths of a second). This allows times up to centiseconds (hundredths of a second). This allows times up to
roughly 11 minutes with a granularity of 10ms, which should cover all roughly 11 minutes with a granularity of 10ms, which should cover all
reasonable applications of Babel. reasonable applications of Babel (see also Appendix B).
4.1.2. Router-Id 4.1.2. Router-Id
A router-id is an arbitrary 8-octet value. A router-id MUST NOT A router-id is an arbitrary 8-octet value. A router-id MUST NOT
consist of either all binary zeroes (0000000000000000 hexadecimal) or consist of either all binary zeroes (0000000000000000 hexadecimal) or
all binary ones (FFFFFFFFFFFFFFFF hexadecimal). all binary ones (FFFFFFFFFFFFFFFF hexadecimal).
4.1.3. Address 4.1.3. Address
Since the bulk of the protocol is taken by addresses, multiple ways Since the bulk of the protocol is taken by addresses, multiple ways
skipping to change at page 45, line 16 skipping to change at page 45, line 37
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. is 0, Plen and Omitted MUST both be 0; Update TLVs that do not
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.
skipping to change at page 46, line 8 skipping to change at page 46, line 34
wildcard request). wildcard request).
Plen The length in bits of the requested prefix. Plen The length in bits of the requested prefix.
Prefix The prefix being requested. This field's size is Plen/8 Prefix The prefix being requested. This field's size is Plen/8
rounded upwards. rounded upwards.
A Request TLV prompts the receiver to send an update message A Request TLV prompts the receiver to send an update message
(possibly a retraction) for the prefix specified by the AE, Plen, and (possibly a retraction) for the prefix specified by the AE, Plen, and
Prefix fields, or a full dump of its route table if AE is 0 (in which Prefix fields, or a full dump of its route table if AE is 0 (in which
case Plen must be 0 and Prefix is of length 0). case Plen must be 0 and Prefix is of length 0). A Request TLV with
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 53, line 22 skipping to change at page 53, line 45
[BABEL-MAC] [BABEL-MAC]
Do, C., Kolodziejak, W., and J. Chroboczek, "MAC Do, C., Kolodziejak, W., and J. Chroboczek, "MAC
authentication for the Babel routing protocol", Internet authentication for the Babel routing protocol", Internet
Draft draft-ietf-babel-hmac-10, August 2019. 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.
[RFC793] Postel, J., "Transmission Control Protocol", RFC 793,
DOI 10.17487/RFC0793, September 1981,
<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, June 2017.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017. May 2017.
8.2. Informative References 8.2. Informative References
skipping to change at page 55, line 5 skipping to change at page 55, line 33
periodic routing messages", IEEE/ACM Transactions on periodic routing messages", IEEE/ACM Transactions on
Networking 2, 2, 122-136, April 1994. Networking 2, 2, 122-136, April 1994.
[OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998.
[PACKETBB] [PACKETBB]
Clausen, T., Dearlove, C., Dean, J., and C. Adjih, Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009. Format", RFC 5444, February 2009.
[RFC2675] Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms",
RFC 2675, DOI 10.17487/RFC2675, August 1999.
[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.
[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,
skipping to change at page 55, line 29 skipping to change at page 56, line 12
[RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998.
Appendix A. Cost and Metric Computation Appendix A. Cost and Metric Computation
The strategy for computing link costs and route metrics is a local The strategy for computing link costs and route metrics is a local
matter; Babel itself only requires that it comply with the conditions matter; Babel itself only requires that it comply with the conditions
given in Section 3.4.3 and Section 3.5.2. Different nodes may use given in Section 3.4.3 and Section 3.5.2. Different nodes may use
different strategies in a single network and may use different different strategies in a single network and may use different
strategies on different interface types. This section describes a strategies on different interface types. This section describes a
set of stragies that have been found to work well in actual networks. set of strategies that have been found to work well in actual
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 ETX (Appendix A.2.2) on wireless links. It uses an additive algebra
for metric computation (Appendix A.3). 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.
skipping to change at page 56, line 38 skipping to change at page 57, line 22
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 discusses how to compute costs based on Hello history. This section describes two algorithms suitable for computing costs
(Section 3.4.3) based on Hello history. Appendix A.2.1 applies to
wired links, and Appendix A.2.2 to wireless links. RECOMMENDED
default values of the parameters that appear in these algorithms are
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
skipping to change at page 58, line 16 skipping to change at page 59, line 5
cost = (MAX(txcost, 256) * rxcost) / 256. cost = (MAX(txcost, 256) * rxcost) / 256.
Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast
frames do not provide a useful measure of link quality, and therefore frames do not provide a useful measure of link quality, and therefore
ETX ignores the Unicast Hello history. Thus, a node performing ETX ETX ignores the Unicast Hello history. Thus, a node performing ETX
link-quality estimation will not route through neighbouring nodes link-quality estimation will not route through neighbouring nodes
unless they send periodic Multicast Hellos (possibly in addition to unless they send periodic Multicast Hellos (possibly in addition to
Unicast Hellos). Unicast Hellos).
A.3. Metric computation A.3. Route selection and hysteresis
As described in Section 3.5.2, the metric advertised by a neighbour
is combined with the link cost to yield a metric.
The simplest approach for obtaining a monotonic, left-distributive
metric is to define the metric of a route as the sum of the costs of
the component links. More formally, if a neighbour advertises a
route with metric m over a link with cost c, then the resulting route
has metric M(c, m) = c + m.
A multiplicative metric can be converted into an additive one by
taking the logarithm (in some suitable base) of the link costs.
A.4. Route selection
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, not all route selection policies will loop-free routes; however, in the presence of continuously variable
yield good results. metrics such as ETX (Appendix A.2.2), a naive route selection
procedure might lead to persistent oscillations. Such oscillations
The obvious route selection procedure is to pick, for every can be limited or avoided altogether by implementing hysteresis
destination, the feasible route with minimal metric. When all within the route selection algorithm, i.e., by making the route
metrics are stable, this strategy ensures convergence to a tree of selection algorithm sensitive to a route's history. Any reasonable
shortest paths (assuming that the metric is left-distributive). hysteresis algorithm should yield good results ; the following
There are two reasons, however, why this strategy leads to algorithm is simple to implement and has been successfully deployed
instability in the presence of continously varying metrics such as in a variety of environments.
ETX (Appendix A.2.2). First, if two parallel routes oscillate around
a common value, then the smallest metric strategy will keep switching
between the two. Second, when a route is selected, congestion along
it increases, which might increase packet loss, which in turn could
cause its metric to increase; this is a feedback loop, of the kind
that is prone to causing persistent oscillations.
A simple strategy to avoid this kind of instabilities is to only
switch routes when the target route's metric is smaller by some
constant margin than the currently selected metric. However, this
approach is difficult to tune: if the constant is too small, then it
doesn't avoid oscillations, and if it is too large, then it leads to
sub-optimal routing; thus, a better strategy is to apply hysteresis
(sensitivity to a route's history) to the route selection algorithm.
The following hysteresis algorithm appears to yield good results with
a variety of metrics.
For every route R, in addition to the route's metric m(R), maintain a For every route R, in addition to the route's metric m(R), maintain a
smoothed version of m(R) written ms(R) (we suggest computing ms(R) as smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R)
an exponential average of m(R) with a time constant equal to a small as an exponentially smoothed average (see Section 3.7 of [RFC793]) of
multiple of the Hello interval). If no route to a given destination m(R) with a time constant equal to the Hello interval multiplied by a
is selected, then select the route with the smallest metric, ignoring small number such as 3). If no route to a given destination is
selected, then select the route with the smallest metric, ignoring
the smoothed metric. If a route R is selected, then switch to a 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 instananeous and the long-term estimate of the routes when both the instantaneous and the long-term estimate 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.
skipping to change at page 61, line 28 skipping to change at page 61, line 34
o defining new TLVs; o defining new TLVs;
o defining new sub-TLVs (with or without the mandatory bit set); o defining new sub-TLVs (with or without the mandatory bit set);
o defining new AEs; o defining new AEs;
o using the packet trailer. o using the packet trailer.
This appendix is intended to guide designers of protocol extensions This appendix is intended to guide designers of protocol extensions
in chosing a particular encoding. in 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 non-mandatory sub-TLV to the Update TLV, or by
skipping to change at page 64, line 40 skipping to change at page 64, line 45
o router-ids with a value of all-zeros or all-ones have been o router-ids with a value of all-zeros or all-ones have been
forbidden (Section 4.1.2); forbidden (Section 4.1.2);
o the compression state is now specific to an address family rather o 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). o packet pacing is now recommended (Section 3.1).
Appendix G. Changes from previous versions Appendix G. Changes from previous versions
[RFC Editor: Please delete this section before publication.]
G.1. Changes since RFC 6126 G.1. Changes since RFC 6126
o Changed UDP port number to 6696. o Changed UDP port number to 6696.
o Consistently use router-id rather than id. o Consistently use router-id rather than id.
o Clarified that the source garbage collection timer is reset after o Clarified that the source garbage collection timer is reset after
sending an update even if the entry was not modified. sending an update even if the entry was not modified.
o In section "Seqno Requests", fixed an erroneous "route request". o In section "Seqno Requests", fixed an erroneous "route request".
skipping to change at page 69, line 9 skipping to change at page 69, line 13
o Added some comments about packet pacing and low update intervals. o Added some comments about packet pacing and low update intervals.
G.18. Changes since draft-ietf-babel-rfc6126bis-15 G.18. Changes since draft-ietf-babel-rfc6126bis-15
o Implementing Babel-MAC is now recommended. o Implementing Babel-MAC is now recommended.
G.19. Changes since draft-ietf-babel-rfc6126bis-16 G.19. Changes since draft-ietf-babel-rfc6126bis-16
o Make the values in Appendix B normatively recommended defaults. 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.
Authors' Addresses Authors' Addresses
Juliusz Chroboczek Juliusz Chroboczek
IRIF, University of Paris-Diderot IRIF, University of Paris-Diderot
Case 7014 Case 7014
75205 Paris Cedex 13 75205 Paris Cedex 13
France France
Email: jch@irif.fr Email: jch@irif.fr
 End of changes. 36 change blocks. 
99 lines changed or deleted 109 lines changed or added

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