draft-ietf-babel-rfc6126bis-00.txt   draft-ietf-babel-rfc6126bis-01.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
Intended status: Standards Track August 1, 2016 Intended status: Standards Track January 31, 2017
Expires: February 2, 2017 Expires: August 4, 2017
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-00 draft-ietf-babel-rfc6126bis-01
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. mesh networks.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
skipping to change at page 1, line 32 skipping to change at page 1, line 32
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 http://datatracker.ietf.org/drafts/current/. Drafts is at http://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 2, 2017. This Internet-Draft will expire on August 4, 2017.
Copyright Notice Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the Copyright (c) 2017 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
(http://trustee.ietf.org/license-info) in effect on the date of (http://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 . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Specification of Requirements . . . . . . . . . . . . . . 4 1.3. Specification of Requirements . . . . . . . . . . . . . . 4
2. Conceptual Description of the Protocol . . . . . . . . . . . 4 2. Conceptual Description of the Protocol . . . . . . . . . . . 4
2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5
2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 5 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 5
2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6
2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 6 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 6
2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 9 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 9
skipping to change at page 2, line 36 skipping to change at page 2, line 36
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22
3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 27 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 27
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 28 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 28
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 29 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 29
4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . 30 4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . 30
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39
6. Security Considerations . . . . . . . . . . . . . . . . . . . 39 6. Security Considerations . . . . . . . . . . . . . . . . . . . 39
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 39 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.1. Normative References . . . . . . . . . . . . . . . . . . 40 7.1. Normative References . . . . . . . . . . . . . . . . . . 40
7.2. Informative References . . . . . . . . . . . . . . . . . 40 7.2. Informative References . . . . . . . . . . . . . . . . . 40
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 41 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 41
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 41 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 41
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 42 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 42
A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 43 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 43
Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 43 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 43
Appendix C. Simplified Implementations . . . . . . . . . . . . . 44 Appendix C. Simplified Implementations . . . . . . . . . . . . . 44
Appendix D. Software Availability . . . . . . . . . . . . . . . 45 Appendix D. Software Availability . . . . . . . . . . . . . . . 45
Appendix E. Changes from previous versions . . . . . . . . . . . 45
E.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 45
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 45 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 45
1. Introduction 1. Introduction
Babel is a loop-avoiding distance-vector routing protocol that is Babel is a loop-avoiding distance-vector routing protocol that is
designed to be robust and efficient both in networks using prefix- designed to be robust and efficient both in networks using prefix-
based routing and in networks using flat routing ("mesh networks"), based routing and in networks using flat routing ("mesh networks"),
and both in relatively stable wired networks and in highly dynamic and both in relatively stable wired networks and in highly dynamic
wireless networks. wireless networks.
skipping to change at page 18, line 27 skipping to change at page 18, line 27
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 (p, plen, id), a node's feasibility distance for this Given a source (p, plen, router-id), a node's feasibility distance
source is the minimum, according to the ordering defined above, of for this source is the minimum, according to the ordering defined
the distances of all the finite updates ever sent by this particular above, of the distances of all the finite updates ever sent by this
node for the prefix (p, plen) carrying the router-id id. Feasibility particular node for the prefix (p, plen) and the given router-id.
distances are maintained in the source table; the exact procedure is Feasibility distances are maintained in the source table; the exact
given in Section 3.7.3. 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 o metric is infinite; or
o no entry exists in the source table indexed by (id, prefix, plen); o no entry exists in the source table indexed by (router-id, prefix,
or plen); or
o an entry (prefix, plen, router-id, seqno', metric') exists in the o 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
skipping to change at page 20, line 14 skipping to change at page 20, line 14
Finally, as a special optimisation for the case when a router-id Finally, as a special optimisation for the case when a router-id
coincides with the interface-id part of an IPv6 address, the router- coincides with the interface-id part of an IPv6 address, the router-
id can optionally be derived from the low-order bits of the id can optionally be derived from the low-order bits of the
advertised prefix. advertised prefix.
The encoding of updates is described in detail in Section 4.4. The encoding of updates is described in detail in Section 4.4.
3.5.4. Route Acquisition 3.5.4. Route Acquisition
When a Babel node receives an update (id, prefix, seqno, metric) from When a Babel node receives an update (router-id, prefix, seqno,
a neighbour neigh with a link cost value equal to cost, it checks metric) from a neighbour neigh with a link cost value equal to cost,
whether it already has a routing table entry indexed by (neigh, id, it checks whether it already has a routing table entry indexed by
prefix). (neigh, router-id, prefix).
If no such entry exists: If no such entry exists:
o if the update is unfeasible, it is ignored; o if the update is unfeasible, it is ignored;
o if the metric is infinite (the update is a retraction), the update o if the metric is infinite (the update is a retraction), the update
is ignored; is ignored;
o otherwise, a new route table entry is created, indexed by (neigh, o otherwise, a new route table entry is created, indexed by (neigh,
id, prefix), with seqno equal to seqno and an advertised metric router-id, prefix), with seqno equal to seqno and an advertised
equal to the metric carried by the update. metric equal to the metric carried by the update.
If such an entry exists: If such an entry exists:
o if the entry is currently installed and the update is unfeasible, o if the entry is currently installed and the update is unfeasible,
then the behaviour depends on whether the router-ids of the two then the behaviour depends on whether the router-ids of the two
entries match. If the router-ids are different, the update is entries match. If the router-ids are different, the update is
treated as though it were a retraction (i.e., as though the metric treated as though it were a retraction (i.e., as though the metric
were FFFF hexadecimal). If the router-ids are equal, the update were FFFF hexadecimal). If the router-ids are equal, the update
is ignored; is ignored;
skipping to change at page 24, line 8 skipping to change at page 24, line 8
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; o if seqno > seqno', then seqno' := seqno, metric' := metric;
o if seqno = seqno' and metric' > metric, then metric' := metric; o if seqno = seqno' and metric' > metric, then metric' := metric;
o otherwise, nothing needs to be done. o otherwise, nothing needs to be done.
The garbage-collection timer for the modified entry is then reset. The garbage-collection timer for the entry is then reset. Note that
Note that the garbage-collection timer is not reset when a retraction the garbage-collection timer is not reset when a retraction is sent.
is sent.
3.7.4. Split Horizon 3.7.4. Split Horizon
When running over a transitive, symmetric link technology, e.g., a When running over a transitive, symmetric link technology, e.g., a
point-to-point link or a wired LAN technology such as Ethernet, a point-to-point link or a wired LAN technology such as Ethernet, a
Babel node SHOULD use an optimisation known as split horizon. When Babel node SHOULD use an optimisation known as split horizon. When
split horizon is used on a given interface, a routing update is not split horizon is used on a given interface, a routing update is not
sent on this particular interface when the advertised route was sent on this particular interface when the advertised route was
learnt from a neighbour over the same interface. learnt from a neighbour over the same interface.
skipping to change at page 25, line 31 skipping to change at page 25, line 31
If a selected route for the given prefix exists, and either the If a selected route for the given prefix exists, and either the
router-ids are different or the router-ids are equal and the entry's router-ids are different or the router-ids are equal and the entry's
sequence number is no smaller than the requested sequence number, it sequence number is no smaller than the requested sequence number, it
MUST send an update for the given prefix. MUST send an update for the given prefix.
If the router-ids match but the requested seqno is larger than the If the router-ids match but the requested seqno is larger than the
route entry's, the node compares the router-id against its own route entry's, the node compares the router-id against its own
router-id. If the router-id is its own, then it increases its router-id. If the router-id is its own, then it increases its
sequence number by 1 and sends an update. A node MUST NOT increase sequence number by 1 and sends an update. A node MUST NOT increase
its sequence number by more than 1 in response to a route request. its sequence number by more than 1 in response to a seqno request.
If the requested router-id is not its own, the received request's hop If the requested router-id is not its own, the received request's hop
count is 2 or more, and the node has a route (not necessarily a count is 2 or more, and the node has a route (not necessarily a
feasible one) for the requested prefix that does not use the feasible one) for the requested prefix that does not use the
requestor as a next hop, the node SHOULD forward the request. It requestor as a next hop, the node SHOULD forward the request. It
does so by decreasing the hop count and sending the request in a does so by decreasing the hop count and sending the request in a
unicast packet destined to a neighbour that advertises the given unicast packet destined to a neighbour that advertises the given
prefix (not necessarily the selected neighbour) and that is distinct prefix (not necessarily the selected neighbour) and that is distinct
from the neighbour from which the request was received. from the neighbour from which the request was received.
skipping to change at page 28, line 25 skipping to change at page 28, line 25
4.1.1. Interval 4.1.1. Interval
Relative times are carried as 16-bit values specifying a number of Relative times are carried as 16-bit values specifying a number of
centiseconds (hundredths of a second). This allows times up to centiseconds (hundredths of a second). This allows times up to
roughly 11 minutes with a granularity of 10ms, which should cover all roughly 11 minutes with a granularity of 10ms, which should cover all
reasonable applications of Babel. reasonable applications of Babel.
4.1.2. Router-Id 4.1.2. Router-Id
A router-id is an arbitrary 8-octet value. Router-ids SHOULD be A router-id is an arbitrary 8-octet. A router-id MUST NOT consist of
assigned in modified EUI-64 format [ADDRARCH]. either all zeroes or all ones. Router-ids SHOULD be assigned in
modified EUI-64 format [ADDRARCH].
4.1.3. Address 4.1.3. Address
Since the bulk of the protocol is taken by addresses, multiple ways Since the bulk of the protocol is taken by addresses, multiple ways
of encoding addresses are defined. Additionally, a common subnet of encoding addresses are defined. Additionally, a common subnet
prefix may be omitted when multiple addresses are sent in a single prefix may be omitted when multiple addresses are sent in a single
packet -- this is known as address compression [PACKETBB]. packet -- this is known as address compression [PACKETBB].
Address encodings: Address encodings:
skipping to change at page 34, line 33 skipping to change at page 34, line 33
Fields : Fields :
Type Set to 6 to indicate a Router-Id TLV. Type Set to 6 to indicate a Router-Id TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body, exclusive of the Type and Length
fields. 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 TLVs. This MUST NOT consist of all zeroes or all ones.
4.4.8. Next Hop 4.4.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...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
skipping to change at page 38, line 49 skipping to change at page 38, line 49
AE The encoding of the Prefix field. This MUST NOT be 0. AE The encoding of the Prefix field. This MUST NOT be 0.
Plen The length of the requested prefix. Plen The length of the requested prefix.
Seqno The sequence number that is being requested. Seqno The sequence number that is being requested.
Hop Count The maximum number of times that this TLV may be forwarded, Hop Count The maximum number of times that this TLV may be forwarded,
plus 1. This MUST NOT be 0. plus 1. This MUST NOT be 0.
Reserved Sent as 0 and MUST be ignored on reception.
Router Id The Router-Id that is being requested. This MUST NOT
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 an Update for A Seqno Request TLV prompts the receiving node to send an Update for
the prefix specified by the AE, Plen, and Prefix fields, with either the prefix specified by the AE, Plen, and Prefix fields, with either
a router-id different from what is specified by the Router-Id field, a router-id different from what is specified by the Router-Id field,
or a Seqno no less than what is specified by the Seqno field. If or a Seqno no less than what is specified by the Seqno field. If
this request cannot be satisfied locally, then it is forwarded this request cannot be satisfied locally, then it is forwarded
according to the rules set out in Section 3.8.1.2. according to the rules set out in Section 3.8.1.2.
While a Seqno Request MAY be sent to a multicast address, it MUST NOT 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.
5. IANA Considerations 5. IANA Considerations
IANA has registered the UDP port number 6697, 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:0:0:0:0:0:1:6 and IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and
the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. the IPv4 multicast group 224.0.0.111 for use by the Babel protocol.
6. Security Considerations 6. Security Considerations
As defined in this document, Babel is a completely insecure protocol. As defined in this document, Babel is a completely insecure protocol.
Any attacker can attract data traffic by advertising routes with a Any attacker can attract data traffic by advertising routes with a
low metric. This particular issue can be solved either by lower- low metric. This particular issue can be solved either by lower-
skipping to change at page 45, line 17 skipping to change at page 45, line 20
A parasitic implementation MUST answer acknowledgement requests and A parasitic implementation MUST answer acknowledgement requests and
MUST participate in the Hello/IHU protocol. Finally, it MUST be able MUST participate in the Hello/IHU protocol. Finally, it MUST be able
to reply to seqno requests for routes that it announces and SHOULD be to reply to seqno requests for routes that it announces and SHOULD be
able to reply to route requests. able to reply to route requests.
Appendix D. Software Availability Appendix D. Software Availability
The sample implementation of Babel is available from The sample implementation of Babel is available from
<http://www.pps.univ-paris-diderot.fr/~jch/software/babel/>. <http://www.pps.univ-paris-diderot.fr/~jch/software/babel/>.
Appendix E. Changes from previous versions
E.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.
Author's Address Author's Address
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@pps.univ-paris-diderot.fr Email: jch@irif.fr
 End of changes. 19 change blocks. 
29 lines changed or deleted 54 lines changed or added

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