draft-ietf-babel-rfc6126bis-14.txt   draft-ietf-babel-rfc6126bis-15.txt 
Network Working Group J. Chroboczek Network Working Group J. Chroboczek
Internet-Draft IRIF, University of Paris-Diderot Internet-Draft IRIF, University of Paris-Diderot
Obsoletes: 6126,7557 (if approved) D. Schinazi Obsoletes: 6126,7557 (if approved) D. Schinazi
Intended status: Standards Track Google LLC Intended status: Standards Track Google LLC
Expires: February 18, 2020 August 17, 2019 Expires: April 20, 2020 October 18, 2019
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-14 draft-ietf-babel-rfc6126bis-15
Abstract Abstract
Babel is a loop-avoiding distance-vector routing protocol that is Babel is a loop-avoiding distance-vector routing protocol that is
robust and efficient both in ordinary wired networks and in wireless robust and efficient both in ordinary wired networks and in wireless
mesh networks. This document describes the Babel routing protocol, mesh networks. This document describes the Babel routing protocol,
and obsoletes RFCs 6126 and 7557. and obsoletes RFCs 6126 and 7557.
Status of This Memo Status of This Memo
skipping to change at page 1, line 34 skipping to change at page 1, line 34
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on February 18, 2020. This Internet-Draft will expire on April 20, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 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 . . . . . . . . . . . . . . . . . . . . . 26 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25
3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28 3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 32 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 31
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34
4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 35 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 34
4.5. Parser state and encoding of updates . . . . . . . . . . 35 4.5. Parser state and encoding of updates . . . . . . . . . . 35
4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 37 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 36
4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 47 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 47
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48
6. Security Considerations . . . . . . . . . . . . . . . . . . . 51 6. Security Considerations . . . . . . . . . . . . . . . . . . . 51
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 52 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 52
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 52 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 53
8.1. Normative References . . . . . . . . . . . . . . . . . . 53 8.1. Normative References . . . . . . . . . . . . . . . . . . 53
8.2. Informative References . . . . . . . . . . . . . . . . . 53 8.2. Informative References . . . . . . . . . . . . . . . . . 53
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 55 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 55
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 55 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 55
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 56 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 56
A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 57 A.3. Metric computation . . . . . . . . . . . . . . . . . . . 58
Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 58 A.4. Route selection . . . . . . . . . . . . . . . . . . . . . 58
Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 59 Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 59
Appendix D. Considerations for protocol extensions . . . . . . . 60 Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 60
Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 61 Appendix D. Considerations for protocol extensions . . . . . . . 61
Appendix F. Compatibility with previous versions . . . . . . . . 62 Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 62
Appendix G. Changes from previous versions . . . . . . . . . . . 63 Appendix F. Compatibility with previous versions . . . . . . . . 63
G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 63 Appendix G. Changes from previous versions . . . . . . . . . . . 64
G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 64 G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 64
G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 64 G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 65
G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 64 G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 65
G.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 65 G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 65
G.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 65 G.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 66
G.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 65 G.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 66
G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 66 G.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 66
G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 66 G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 67
G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 66 G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 67
G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 66 G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 67
G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 66 G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 67
G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 66 G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 67
G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 66 G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 67
G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 66 G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 67
G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 67 G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 67
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 67 G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 68
G.17. Changes since draft-ietf-babel-rfc6126bis-14 . . . . . . 68
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 13, line 39 skipping to change at page 13, line 39
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. previous paragraph. Note however that such packet pacing might
impair the ability of some link layers (e.g., IEEE 802.11) to perform
link 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 give a description of the data structures that
every Babel speaker maintains. This description is conceptual: a every Babel speaker maintains. This description is conceptual: a
Babel speaker may use different data structures as long as the Babel speaker may use different data structures as long as the
resulting protocol is the same as the one described in this document. resulting protocol is the same as the one described in this document.
For example, rather than maintaining a single table containing both For example, rather than maintaining a single table containing both
selected and unselected (fallback) routes, as described in selected and unselected (fallback) routes, as described in
Section 3.2.6 below, an actual implementation would probably use two Section 3.2.6 below, an actual implementation would probably use two
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.
Note, however, that Babel does not naturally guarantee the stability
of routing, and configuring conflicting route selection policies on
different routers may lead to persistent route oscillation.
Route selection is a difficult problem, since a good route selection
policy needs to take into account multiple mutually contradictory
criteria; in roughly decreasing order of importance, these are:
o routes with a small metric should be preferred to routes with a
large metric;
o switching router-ids should be avoided;
o routes through stable neighbours should be preferred to routes
through unstable ones;
o stable routes should be preferred to unstable ones;
o switching next hops should be avoided.
Route selection MUST NOT take seqnos into account: a route MUST NOT Route selection MUST NOT take seqnos into account: a route MUST NOT
be preferred just because it carries a higher (more recent) seqno. be preferred just because it carries a higher (more recent) seqno.
Doing otherwise would cause route oscillation while a new seqno Doing otherwise would cause route oscillation while a new seqno
propagates through the network, possibly following multiple paths of propagates through the network, possibly following multiple paths of
different latency, and might even create persistent blackholes if the different latency, and might even create persistent blackholes if the
metric being used is not left-distributive (Section 3.5.2). metric being used is not left-distributive (Section 3.5.2).
A simple but useful strategy is to choose the feasible route with the The obvious route selection strategy is to choose for each
smallest metric, with a small amount of hysteresis applied to avoid destination the feasible route with lowest metric. However, with
switching router-ids too often. continuously varying costs and metrics this simple strategy will in
some cases lead to route oscillations. See Appendix A.4 for a
discussion of the issues and suggested strategies for dealing with
them.
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 51, line 47 skipping to change at page 51, line 47
o spoof a Babel packet, and redirect traffic by announcing a route o 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 o 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 o replay a previously captured Babel packet, which could cause
traffic to be redirected or otherwise interfere with the network. traffic to be redirected, blackholed or otherwise interfere with
the network.
When carried over IPv6, Babel packets are ignored unless they are When carried over IPv6, Babel packets are ignored unless they are
sent from a link-local IPv6 address; since routers don't forward sent from a link-local IPv6 address; since routers don't forward
link-local IPv6 packets, this 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. exists when Babel packets are carried over IPv4.
These issues can be solved by providing a means for Babel to ensure If packets arriving at a Babel node cannot be trusted, either because
datagrams are fresh and originated from a trusted node. This can be it cannot be ensured that they originated on a local link, because
achieved either by a lower-layer security mechanism (e.g., link-layer the local link itself is not protected by a sufficiently strong
security or IPsec), or by deploying a suitable authentication lower-layer mechanism, or because it is not desirable to trust a
mechanism within Babel itself. There are currently two such lower-layer security mechanism, then the Babel control traffic must
mechanisms: be protected by an application-layer mechanism. There are currently
two such mechanisms, which implement different tradeoffs between
implementation simplicity and security:
o Babel over DTLS [BABEL-DTLS] runs the majority of Babel traffic o Babel over DTLS [BABEL-DTLS] runs the majority of Babel traffic
over DTLS, and leverages DTLS to authenticate nodes and provide over 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 o MAC authentication [BABEL-MAC] appends a message authentication
code to all Babel datagrams to prove they originated from a node code (MAC) to every Babel packet to prove that it originated at a
that possesses a shared secret. node that knows a shared secret, and includes sufficient
additional information to prove that the packet is fresh (not
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. However, only DTLS supports messages and prevent message replay. While Babel-DTLS supports
asymmetric keying and message confidentiality. MAC authentication is asymmetric keying and ensures confidentiality, Babel-MAC has a much
simpler and does not depend on DTLS, and therefore its use is more limited scope (see Sections 1.1, 1.2 and 7 of [BABEL-MAC]).
RECOMMENDED when the target deployment does not require Since Babel-MAC is simpler and more lightweight, it is recommended in
confidentiality or asymmetric keying. preference to Babel-DTLS in deployments where its limitations are
acceptable, i.e., when symmetric keying is sufficient and where the
routing information is not considered confidential.
The information that a mobile Babel node announces to the whole One should be aware that the information that a mobile Babel node
routing domain is often sufficient to determine a mobile node's announces to the whole routing domain is sufficient to determine a
physical location with reasonable precision. The privacy issues that mobile node's physical location with reasonable precision, which
this causes can be mitigated somewhat by using randomly chosen might cause privacy concerns even if the control traffic is protected
router-ids and randomly chosen IP addresses, and changing them often from unauthenticated attackers by Babel-DTLS. This issue may be
enough. mitigated somewhat by using randomly chosen router-ids and randomly
chosen IP addresses, and changing them often enough.
7. Acknowledgments 7. Acknowledgments
A number of people have contributed text and ideas to this A number of people have contributed text and ideas to this
specification. The authors are particularly indebted to Matthieu specification. The authors are particularly indebted to Matthieu
Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke
Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin
Vigoureux. Earlier versions of this document greatly benefited from Vigoureux. Earlier versions of this document greatly benefited from
the input of Joel Halpern. The address compression technique was the input of Joel Halpern. The address compression technique was
inspired by [PACKETBB]. inspired by [PACKETBB].
skipping to change at page 54, line 17 skipping to change at page 54, line 22
February 1993. February 1993.
[EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, [EIGRP] Albrightson, B., Garcia Luna Aceves, 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. 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", Proc. MobiCom 2003, 2003.
[IS-IS] "Information technology -- Telecommunications and [IS-IS] Standardization, I. O. F., "Information technology --
information exchange between systems -- Intermediate Telecommunications and information exchange between
System to Intermediate System intra-domain routeing systems -- Intermediate System to Intermediate System
information exchange protocol for use in conjunction with intra-domain routeing information exchange protocol for
the protocol for providing the connectionless-mode network use in conjunction with the protocol for providing the
service (ISO 8473)", ISO/IEC 10589:2002, 2002. connectionless-mode network 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, 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
skipping to change at page 55, line 18 skipping to change at page 55, line 23
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 stragies 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.1). for metric computation (Appendix A.3).
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 57, line 46 skipping to change at page 58, 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. Metric computation
As described in Section 3.5.2, the metric advertised by a neighbour As described in Section 3.5.2, the metric advertised by a neighbour
is combined with the link cost to yield a metric. is combined with the link cost to yield a metric.
A.3.1. Additive Metrics
The simplest approach for obtaining a monotonic, left-distributive 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 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 the component links. More formally, if a neighbour advertises a
route with metric m over a link with cost c, then the resulting route route with metric m over a link with cost c, then the resulting route
has metric M(c, m) = c + m. has metric M(c, m) = c + m.
A multiplicative metric can be converted into an additive one by A multiplicative metric can be converted into an additive one by
taking the logarithm (in some suitable base) of the link costs. 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
a single route among the routes that it has available towards a given
destination. With Babel, any route selection procedure that only
ever chooses feasible routes with a finite metric will yield a set of
loop-free routes; however, not all route selection policies will
yield good results.
The obvious route selection procedure is to pick, for every
destination, the feasible route with minimal metric. When all
metrics are stable, this strategy leads to convergence to a tree of
shortest paths (assuming that the metric is left-distributive).
There are two reasons, however, why this strategy leads to
instability in the presence of continously varying metrics such as
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 than the currently selected metric. However, this approach
is difficult to tune: if the constant is too small, then it fails to
avoid oscillations, and if it is too large, then it leads to sub-
optimal routing. 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
smoothed version of m(R) written ms(R) (we suggest computing ms(R) as
an exponential average of m(R) with a time constant equal to a small
multiple of the Hello interval). 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
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
quality of a route. The algorithm above works by only switching
routes when both the instananeous and the long-term estimate of the
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. acquire new routes after a mobility event. While the protocol allows
intervals as low as 10ms, such low values would cause significant
amounts of protocol traffic for little practical benefit.
The following values are recommended in a network with little The following values are recommended in a network with little
mobility, and where occasional outages of up to 14 seconds are mobility, and where occasional outages of up to 14 seconds are
acceptable: acceptable:
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
skipping to change at page 62, line 42 skipping to change at page 63, line 44
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 two optioal features that make the new protocol There are three optional features that make the new 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 mis-interpret a Unicast Hello for a Multicast one; since
the sequence number space of Unicast Hellos is distinct from the the sequence number space of Unicast Hellos is distinct from the
sequence space of Multicast Hellos, sending a Unicast Hello to an sequence 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 7557 did not define mandatory sub-TLVs (Section 4.4); Second, RFC 6126 did not define unscheduled Hellos, and an
thus, an implementation of RFCs 6126 and 7557 will not correctly implementation of RFC 6126 will mis-parse Hellos with an interval
ignore a TLV that carries an unknown mandatory sub-TLV; depending on equal to 0. Finally, RFC 7557 did not define mandatory sub-TLVs
the sub-TLV, this might cause routing pathologies. (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;
depending on the sub-TLV, this might cause routing pathologies.
An implementation of this specification that never sends Unicast An implementation of this specification that never sends Unicast or
Hellos and doesn't implement any extensions that use mandatory sub- unscheduled Hellos and doesn't implement any extensions that use
TLVs is safe to deploy in a network in which some nodes implement the mandatory sub-TLVs is safe to deploy in a network in which some nodes
old protocol. implement the old protocol.
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 to
either ignore or process Unicast Hellos. Second, it needs to be either ignore or process Unicast and unscheduled Hellos. Second, it
modified to parse sub-TLVs of all the TLVs that it understands and needs to be modified to parse sub-TLVs of all the TLVs that it
that allow sub-TLVs, and to ignore the TLV is an unknown mandatory understands and that allow sub-TLVs, and to ignore the TLV if an
sub-TLV is found. It is not necessary to parse unknown TLVs, since unknown mandatory sub-TLV is found. It is not necessary to parse
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 o 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 o 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); o 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 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
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.
skipping to change at page 67, line 37 skipping to change at page 68, line 41
o Replaced Babel-HMAC with Babel-MAC, consistent with the change in o Replaced Babel-HMAC with Babel-MAC, consistent with the change in
draft-ietf-babel-hmac. draft-ietf-babel-hmac.
o Removed section about external sources of willingness; filtering o Removed section about external sources of willingness; filtering
is a better approach. is a better approach.
o Added recommendation to use a cost of 96 on wired links. o Added recommendation to use a cost of 96 on wired links.
o Editorial changes. 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.
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 USA
Email: dschinazi.ietf@gmail.com Email: dschinazi.ietf@gmail.com
 End of changes. 30 change blocks. 
102 lines changed or deleted 156 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/