draft-ietf-babel-rfc6126bis-02.txt   draft-ietf-babel-rfc6126bis-03.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 May 24, 2017 Intended status: Standards Track July 3, 2017
Expires: November 25, 2017 Expires: January 4, 2018
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-02 draft-ietf-babel-rfc6126bis-03
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 November 25, 2017. This Internet-Draft will expire on January 4, 2018.
Copyright Notice Copyright Notice
Copyright (c) 2017 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
skipping to change at page 2, line 11 skipping to change at page 2, line 11
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . 5
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 . . . . . . . . . . . . . . . . . 7
2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 9 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10
2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11
3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 11 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12
3.1. Message Transmission and Reception . . . . . . . . . . . 12 3.1. Message Transmission and Reception . . . . . . . . . . . 12
3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12
3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . 16 3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . 16
3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 16 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17
3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 18 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 19
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 22 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 23 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 24
3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 25 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 27
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 29 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 30
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 29 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 31
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 30 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 32
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 31 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 33
4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 31 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 33
4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 32 4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 34
4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 33 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 34
4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 43 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 45
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 43 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46
6. Security Considerations . . . . . . . . . . . . . . . . . . . 44 6. Security Considerations . . . . . . . . . . . . . . . . . . . 46
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 44 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 46
7.1. Normative References . . . . . . . . . . . . . . . . . . 44 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.2. Informative References . . . . . . . . . . . . . . . . . 44 8.1. Normative References . . . . . . . . . . . . . . . . . . 46
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 45 8.2. Informative References . . . . . . . . . . . . . . . . . 47
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 45 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 47
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 46 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 48
A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 47 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 49
Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 48 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 50
Appendix C. Considerations for protocol extensions . . . . . . . 49 A.4. Properties of Multicast and Unicast Hellos . . . . . . . 51
Appendix D. Simplified Implementations . . . . . . . . . . . . . 50 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 51
Appendix E. Software Availability . . . . . . . . . . . . . . . 50 Appendix C. Considerations for protocol extensions . . . . . . . 52
Appendix F. Changes from previous versions . . . . . . . . . . . 51 Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 53
F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 51 Appendix E. Software Availability . . . . . . . . . . . . . . . 54
F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 51 Appendix F. Changes from previous versions . . . . . . . . . . . 54
F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 51 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 54
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 52 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 55
F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 55
F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 55
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 56
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.
1.1. Features 1.1. Features
skipping to change at page 4, line 35 skipping to change at page 4, line 37
updates when the network topology changes. In such networks, updates when the network topology changes. In such networks,
protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced
Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more
suitable. suitable.
Second, Babel does impose a hold time when a prefix is retracted Second, Babel does impose a hold time when a prefix is retracted
(Section 3.5.5). While this hold time does not apply to the exact (Section 3.5.5). While this hold time does not apply to the exact
prefix being retracted, and hence does not prevent fast reconvergence prefix being retracted, and hence does not prevent fast reconvergence
should it become available again, it does apply to any shorter prefix should it become available again, it does apply to any shorter prefix
that covers it. Hence, if a previously deaggregated prefix becomes that covers it. Hence, if a previously deaggregated prefix becomes
aggregated, it will be unreachable for a few minutes. This makes aggregated, it will be unreachable for a few hundred milliseconds up
Babel unsuitable for use in mobile networks that implement automatic to a few minutes, depending on the implementation. This may make
prefix aggregation. some implementations of Babel unsuitable for use in networks that
implement automatic prefix aggregation.
1.3. Specification of Requirements 1.3. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. document are to be interpreted as described in [RFC2119].
2. Conceptual Description of the Protocol 2. Conceptual Description of the Protocol
Babel is a mostly loop-free distance vector protocol: it is based on Babel is a mostly loop-free distance vector protocol: it is based on
skipping to change at page 5, line 26 skipping to change at page 5, line 34
Given a route between any two nodes, the metric of the route is the Given a route between any two nodes, the metric of the route is the
sum of the costs of all the edges along the route. The goal of the sum of the costs of all the edges along the route. The goal of the
routing algorithm is to compute, for every source S, the tree of the routing algorithm is to compute, for every source S, the tree of the
routes of lowest metric to S. routes of lowest metric to S.
Costs and metrics need not be integers. In general, they can be Costs and metrics need not be integers. In general, they can be
values in any algebra that satisfies two fairly general conditions values in any algebra that satisfies two fairly general conditions
(Section 3.5.2). (Section 3.5.2).
A Babel node periodically broadcasts Hello messages to all of its A Babel node periodically sends Hello messages to all of its
neighbours; it also periodically sends an IHU ("I Heard You") message neighbours; it also periodically sends an IHU ("I Heard You") message
to every neighbour from which it has recently heard a Hello. From to every neighbour from which it has recently heard a Hello. From
the information derived from Hello and IHU messages received from its the information derived from Hello and IHU messages received from its
neighbour B, a node A computes the cost C(A, B) of the link from A to neighbour B, a node A computes the cost C(A, B) of the link from A to
B. B.
2.2. The Bellman-Ford Algorithm 2.2. The Bellman-Ford Algorithm
Every node A maintains two pieces of data: its estimated distance to Every node A maintains two pieces of data: its estimated distance to
S, written D(A), and its next-hop router to S, written NH(A). S, written D(A), and its next-hop router to S, written NH(A).
skipping to change at page 11, line 38 skipping to change at page 11, line 47
After a route fails, it is not correct in general to switch to a After a route fails, it is not correct in general to switch to a
route that subsumes the failed route. Consider for example the route that subsumes the failed route. Consider for example the
following configuration: following configuration:
1 1 1 1
::/0 -- A --- B --- C ::/0 -- A --- B --- C
Suppose that node C fails. If B forwards packets destined to C by Suppose that node C fails. If B forwards packets destined to C by
following the default route, a routing loop will form, and persist following the default route, a routing loop will form, and persist
until A learns of B's retraction of the direct route to C. Babel until A learns of B's retraction of the direct route to C. B avoids
avoids this pitfall by maintaining an "unreachable" route for a few this pitfall by installing an "unreachable" route after a route is
minutes after a route is retracted; the time for which such a route retracted; this route is maintained until it can be guaranteed that
must be maintained should be the worst-case propagation time of the the former route has been retracted by all of B's neighbours.
retraction of the route to C.
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.
We suggest that router-ids should be assigned in modified EUI-64 We suggest that router-ids should be assigned in modified EUI-64
format [ADDRARCH]. (As a matter of fact, the protocol encoding is format [ADDRARCH]. (As a matter of fact, 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.) as the IPv6 layer assigns host IDs.)
3.1. Message Transmission and Reception 3.1. Message Transmission and Reception
Babel protocol packets are sent in the body of a UDP datagram. Each Babel protocol packets are sent in the body of a UDP datagram. Each
Babel packet consists of zero or more TLVs. Most TLVs may contain Babel packet consists of zero or more TLVs. Most TLVs may contain
sub-TLVs. sub-TLVs.
The source address of a Babel packet is always a unicast address, The source address of a Babel packet is always a unicast address,
link-local in the case of IPv6. Babel packets may be sent to a well- link-local in the case of IPv6. Babel packets may be sent to a well-
known (link-local) multicast address (this is the usual case) or to a known (link-local) multicast address or to a (link-local) unicast
(link-local) unicast address. In normal operation, a Babel speaker address. In normal operation, a Babel speaker sends both multicast
sends both multicast and unicast packets to its neighbours. and unicast packets to its neighbours.
With the exception of Hello TLVs and acknowledgements, all Babel TLVs With the exception of Hello TLVs and acknowledgements, all Babel TLVs
can be sent to either unicast or multicast addresses, and their can be sent to either unicast or multicast addresses, and their
semantics does not depend on whether the destination was a unicast or semantics does not depend on whether the destination was a unicast or
multicast address. Hence, a Babel speaker does not need to determine multicast address. Hence, a Babel speaker does not need to determine
the destination address of a packet that it receives in order to the destination address of a packet that it receives in order to
interpret it. interpret it.
A moderate amount of jitter is applied to packets sent by a Babel A moderate amount of jitter may be applied to packets sent by a Babel
speaker: outgoing TLVs are buffered and SHOULD be sent with a small speaker: outgoing TLVs are buffered and SHOULD be sent with a small
random delay. This is done for two purposes: it avoids random delay. This is done for two purposes: it avoids
synchronisation of multiple Babel speakers across a network [JITTER], synchronisation of multiple Babel speakers across a network [JITTER],
and it allows for the aggregation of multiple TLVs into a single and it allows for the aggregation of multiple TLVs into a single
packet. packet.
The exact delay and amount of jitter applied to a packet depends on The exact delay and amount of jitter applied to a packet depends on
whether it contains any urgent TLVs. Acknowledgement TLVs MUST be whether it contains any urgent TLVs. Acknowledgement TLVs MUST be
sent before the deadline specified in the corresponding request. The sent before the deadline specified in the corresponding request. The
particular class of updates specified in Section 3.7.2 MUST be sent particular class of updates specified in Section 3.7.2 MUST be sent
skipping to change at page 13, line 37 skipping to change at page 13, line 47
A node increments its sequence number (modulo 2^16) whenever it A node increments its sequence number (modulo 2^16) whenever it
receives a request for a new sequence number (Section 3.8.1.2). A receives a request for a new sequence number (Section 3.8.1.2). A
node SHOULD NOT increment its sequence number (seqno) spontaneously, node SHOULD NOT increment its sequence number (seqno) spontaneously,
since increasing seqnos makes it less likely that other nodes will since increasing seqnos makes it less likely that other nodes will
have feasible alternate routes when their selected routes fail. have feasible alternate routes when their selected routes fail.
3.2.3. The Interface Table 3.2.3. The Interface Table
The interface table contains the list of interfaces on which the node The interface table contains the list of interfaces on which the node
speaks the Babel protocol. Every interface table entry contains the speaks the Babel protocol. Every interface table entry contains the
interface's Hello seqno, a 16-bit integer that is sent with each interface's outgoing Multicast Hello seqno, a 16-bit integer that is
Hello TLV on this interface and is incremented (modulo 2^16) whenever sent with each Multicast Hello TLV on this interface and is
a Hello is sent. (Note that an interface's Hello seqno is unrelated incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note
to the node's seqno.) that an interface's Multicast Hello seqno is unrelated to the node's
seqno.)
There are two timers associated with each interface table entry -- There are two timers associated with each interface table entry --
the Hello timer, which governs the sending of periodic Hello and IHU the multicast hello timer, which governs the sending of scheduled
packets, and the update timer, which governs the sending of periodic Multicast Hello and IHU packets, and the update timer, which governs
route updates. the sending of periodic route updates.
3.2.4. The Neighbour Table 3.2.4. The Neighbour Table
The neighbour table contains the list of all neighbouring interfaces The neighbour table contains the list of all neighbouring interfaces
from which a Babel packet has been recently received. The neighbour from which a Babel packet has been recently received. The neighbour
table is indexed by pairs of the form (interface, address), and every table is indexed by pairs of the form (interface, address), and every
neighbour table entry contains the following data: neighbour table entry contains the following data:
o the local node's interface over which this neighbour is reachable; o the local node's interface over which this neighbour is reachable;
o the address of the neighbouring interface; o the address of the neighbouring interface;
o a history of recently received Hello packets from this neighbour; o a history of recently received Multicast Hello packets from this
this can, for example, be a sequence of n bits, for some small neighbour; this can, for example, be a sequence of n bits, for
value n, indicating which of the n hellos most recently sent by some small value n, indicating which of the n hellos most recently
this neighbour have been received by the local node; sent by this neighbour have been received by the local node;
o a history of recently received Unicast Hello packets from this
neighbour;
o the "transmission cost" value from the last IHU packet received o the "transmission cost" value from the last IHU packet received
from this neighbour, or FFFF hexadecimal (infinity) if the IHU from this neighbour, or FFFF hexadecimal (infinity) if the IHU
hold timer for this neighbour has expired; hold timer for this neighbour has expired;
o the neighbour's expected Hello sequence number, an integer modulo o the neighbour's expected incoming Multicast Hello sequence number,
2^16. an integer modulo 2^16.
There are two timers associated with each neighbour entry -- the o the neighbour's expected incoming Unicast Hello sequence number,
hello timer, which is initialised from the interval value carried by an integer modulo 2^16.
Hello TLVs, and the IHU timer, which is initialised to a small
multiple of the interval carried in IHU TLVs. o the neighbour's outgoing Unicast Hello sequence number, an integer
modulo 2^16 that is sent with each Unicast Hello TLV to this
neighbour and is incremented (modulo 2^16) whenever a Unicast
Hello is sent. (Note that a neighbour's outgoing Unicast Hello
seqno is distinct from the interface's outgoing Multicast Hello
seqno.)
There are three timers associated with each neighbour entry -- the
multicast hello timer, which is initialised from the interval value
carried by scheduled Multicast Hello TLVs, the unicast hello timer,
which is initialised from the interval value carried by scheduled
Unicast Hello TLVs, and the IHU timer, which is initialised to a
small multiple of the interval carried in IHU TLVs.
Note that the neighbour table is indexed by IP addresses, not by Note that the neighbour table is indexed by IP addresses, not by
router-ids: neighbourship is a relationship between interfaces, not router-ids: neighbourship is a relationship between interfaces, not
between nodes. Therefore, two nodes with multiple interfaces can between nodes. Therefore, two nodes with multiple interfaces can
participate in multiple neighbourship relationships, a fairly common participate in multiple neighbourship relationships, a fairly common
situation when wireless nodes with multiple radios are involved. situation when wireless nodes with multiple radios are involved.
3.2.5. The Source Table 3.2.5. The Source Table
The source table is used to record feasibility distances. It is The source table is used to record feasibility distances. It is
skipping to change at page 15, line 36 skipping to change at page 16, line 10
There is one timer associated with each route table entry -- the There is one timer associated with each route table entry -- the
route expiry timer. It is initialised and reset as specified in route expiry timer. It is initialised and reset as specified in
Section 3.5.4. Section 3.5.4.
Of course, the data structure described above is conceptual: actual Of course, the data structure described above is conceptual: actual
implementations will likely use a different data structure, for implementations will likely use a different data structure, for
example a table of installed routes and a set of redundant ones, or example a table of installed routes and a set of redundant ones, or
some more complicated data structure. some more complicated data structure.
3.2.7. The Table of Pending Requests Note that there are two distinct (seqno, metric) pairs associated to
each route: the route's distance, which is stored in the route table,
and the feasibility distance, stored in the source table and shared
between all routes with the same source.
The table of pending requests contains a list of seqno requests that 3.2.7. The Table of Pending Seqno Requests
the local node has sent (either because they have been originated
locally, or because they were forwarded) and to which no reply has The table of pending seqno requests contains a list of seqno requests
been received yet. This table is indexed by prefixes, and every that the local node has sent (either because they have been
entry in this table contains the following data: originated locally, or because they were forwarded) and to which no
reply has been received yet. This table is indexed by prefixes and
router-ids, and every entry in this table contains the following
data:
o the prefix, router-id, and seqno being requested; o the prefix, router-id, and seqno being requested;
o the neighbour, if any, on behalf of which we are forwarding this o the neighbour, if any, on behalf of which we are forwarding this
request; request;
o a small integer indicating the number of times that this request o a small integer indicating the number of times that this request
will be resent if it remains unsatisfied. will be resent if it remains unsatisfied.
There is one timer associated with each pending request; it governs There is one timer associated with each pending seqno request; it
both the resending of requests and their expiry. governs both the resending of requests and their expiry.
3.3. Acknowledged Packets 3.3. Acknowledged Packets
A Babel speaker may request that any neighbour receiving a given A Babel speaker may request that any neighbour receiving a given
packet reply with an explicit acknowledgement within a given time. packet reply with an explicit acknowledgement within a given time.
While the use of acknowledgement requests is optional, every Babel While the use of acknowledgement requests is optional, every Babel
speaker MUST be able to reply to such a request. speaker MUST be able to reply to such a request.
An acknowledgement MUST be sent to a unicast destination. On the An acknowledgement MUST be sent to a unicast destination. On the
other hand, acknowledgement requests may be sent to either unicast or other hand, acknowledgement requests may be sent to either unicast or
multicast destinations, in which case they request an acknowledgement multicast destinations, in which case they request an acknowledgement
from all of the receiving nodes. from all of the receiving nodes.
When to request acknowledgements is a matter of local policy; the When to request acknowledgements is a matter of local policy; the
simplest strategy is to never request acknowledgements and to rely on simplest strategy is to never request acknowledgements and to rely on
periodic updates to ensure that any reachable routes are eventually periodic updates to ensure that any reachable routes are eventually
propagated throughout the routing domain. For increased efficiency, propagated throughout the routing domain. For increased efficiency,
we suggest that acknowledged packets should be used in order to send acknowledged packets MAY be used in order to send urgent updates
urgent updates (Section 3.7.2) when the number of neighbours on a (Section 3.7.2) when the number of neighbours on a given interface is
given interface is small. Since Babel is designed to deal gracefully small. Since Babel is designed to deal gracefully with packet loss
with packet loss on unreliable media, sending all packets with on unreliable media, sending all packets with acknowledgement
acknowledgement requests is not necessary, and not even recommended, requests is not necessary, and NOT RECOMMENDED, as the
as the acknowledgements cause additional traffic and may force acknowledgements cause additional traffic and may force additional
additional Address Resolution Protocol (ARP) or Neighbour Discovery Address Resolution Protocol (ARP) or Neighbour Discovery exchanges.
exchanges.
3.4. Neighbour Acquisition 3.4. Neighbour Acquisition
Neighbour acquisition is the process by which a Babel node discovers Neighbour acquisition is the process by which a Babel node discovers
the set of neighbours heard over each of its interfaces and the set of neighbours heard over each of its interfaces and
ascertains bidirectional reachability. On unreliable media, ascertains bidirectional reachability. On unreliable media,
neighbour acquisition additionally provides some statistics that may neighbour acquisition additionally provides some statistics that may
be useful for link quality computation. be useful for link quality computation.
Before it can exchange routing information with a neighbour, a Babel Before it can exchange routing information with a neighbour, a Babel
node MUST create an entry for that neighbour in the neighbour table. node MUST create an entry for that neighbour in the neighbour table.
When to do that is an implementation detail; suitable strategies When to do that is implementation-specific; suitable strategies
include creating an entry when any Babel packet is received, or include creating an entry when any Babel packet is received, or
creating an entry when a Hello TLV is parsed. Similarly, in order to creating an entry when a Hello TLV is parsed. Similarly, in order to
conserve system resources, an implementation SHOULD discard an entry conserve system resources, an implementation SHOULD discard an entry
when it has been unused for long enough; suitable strategies include when it has been unused for long enough; suitable strategies include
dropping the neighbour after a timeout, and dropping a neighbour when dropping the neighbour after a timeout, and dropping a neighbour when
the associated Hello history becomes empty (see Appendix A.2). the associated Hello histories become empty (see Appendix A.2).
3.4.1. Reverse Reachability Detection 3.4.1. Reverse Reachability Detection
Every Babel node sends periodic Hellos over each of its interfaces. Every Babel node sends Hello TLVs to its neighbours to indicate that
Each Hello TLV carries an increasing (modulo 2^16) sequence number it is alive, at regular or irregular intervals. Each Hello TLV
and the interval between successive periodic packets sent on this carries an increasing (modulo 2^16) sequence number and the time
particular interface. interval until the next Hello of the same type (see below). If the
time interval is set to 0, then the Hello TLV does not establish a
new promise -- the timeout carried by the previous Hello of the same
type still applies to the next Hello. We say that a Hello is
scheduled if it has a non-zero interval, and unscheduled otherwise.
In addition to the periodic Hello packets, a node MAY send There are two kinds of Hellos: Multicast Hellos, which use a per-
unscheduled Hello packets, e.g., to accelerate link cost estimation interface Hello counter, and Unicast Hellos, which use a per-
when a new neighbour is discovered, or when link conditions have neighbour counter. A Multicast Hellos with a given seqno MUST be
suddenly changed. sent to all neighbours on a given interface, either by sending it to
a multicast address or by sending it to one unicast address per
neighbour. A Unicast Hello with given seqno should normally be sent
to just one neighbour (over unicast), since the sequence numbers of
different neighbours are not necessarily synchronised.
A node MAY change its Hello interval. The Hello interval MAY be Multicast Hellos sent over multicast can be used for node discovery;
decreased at any time; it SHOULD NOT be increased, except immediately hence, a node SHOULD send periodic (scheduled) Multicast Hellos. A
before sending a Hello packet. (Equivalently, a node SHOULD send an node MAY send Unicast Hellos or unscheduled Hellos of either kind for
unscheduled Hello immediately after increasing its Hello interval.) any reason, such as reducing the amount of multicast traffic or
improving reliability on link technologies with poor support for
link-layer multicast.
A node MAY send a scheduled Hello ahead of time. A node MAY change
its scheduled Hello interval. The Hello interval MAY be decreased at
any time; it MAY be increased immediately before sending a Hello TLV,
but SHOULD NOT be increased at other times. (Equivalently, a node
SHOULD send an extra scheduled Hello immediately after increasing its
Hello interval.)
How to deal with received Hello TLVs and what statistics to maintain How to deal with received Hello TLVs and what statistics to maintain
are considered local implementation matters; typically, a node will are considered local implementation matters; typically, a node will
maintain some sort of history of recently received Hellos. A maintain some sort of history of recently received Hellos. A useful
possible algorithm is described in Appendix A.1. algorithm is described in Appendix A.1.
After receiving a Hello, or determining that it has missed one, the After receiving a Hello, or determining that it has missed one, the
node recomputes the association's cost (Section 3.4.3) and runs the node recomputes the association's cost (Section 3.4.3) and runs the
route selection procedure (Section 3.6). route selection procedure (Section 3.6).
3.4.2. Bidirectional Reachability Detection 3.4.2. Bidirectional Reachability Detection
In order to establish bidirectional reachability, every node sends In order to establish bidirectional reachability, every node sends
periodic IHU ("I Heard You") TLVs to each of its neighbours. Since periodic IHU ("I Heard You") TLVs to each of its neighbours. Since
IHUs carry an explicit interval value, they MAY be sent less often IHUs carry an explicit interval value, they MAY be sent less often
than Hellos in order to reduce the amount of routing traffic in dense than Hellos in order to reduce the amount of routing traffic in dense
networks; in particular, they SHOULD be sent less often than Hellos networks; in particular, they SHOULD be sent less often than Hellos
over links with little packet loss. While IHUs are conceptually over links with little packet loss. While IHUs are conceptually
unicast, they SHOULD be sent to a multicast address in order to avoid unicast, they MAY be sent to a multicast address in order to avoid an
an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs ARP or Neighbour Discovery exchange and to aggregate multiple IHUs in
in a single packet. a single packet.
In addition to the periodic IHUs, a node MAY, at any time, send an In addition to the periodic IHUs, a node MAY, at any time, send an
unscheduled IHU packet. It MAY also, at any time, decrease its IHU unscheduled IHU packet. It MAY also, at any time, decrease its IHU
interval, and it MAY increase its IHU interval immediately before interval, and it MAY increase its IHU interval immediately before
sending an IHU. sending an IHU, but SHOULD NOT increase it at any other time.
(Equivalently, a node SHOULD send an extra IHU immediately after
increasing its Hello interval.)
Every IHU TLV contains two pieces of data: the link's rxcost Every IHU TLV contains two pieces of data: the link's rxcost
(reception cost) from the sender's perspective, used by the neighbour (reception cost) from the sender's perspective, used by the neighbour
for computing link costs (Section 3.4.3), and the interval between for computing link costs (Section 3.4.3), and the interval between
periodic IHU packets. A node receiving an IHU updates the value of periodic IHU packets. A node receiving an IHU updates the value of
the sending neighbour's txcost (transmission cost), from its the sending neighbour's txcost (transmission cost), from its
perspective, to the value contained in the IHU, and resets this perspective, to the value contained in the IHU, and resets this
neighbour's IHU timer to a small multiple of the value received in neighbour's IHU timer to a small multiple of the value received in
the IHU. the IHU.
skipping to change at page 18, line 33 skipping to change at page 19, line 28
history, which may be combined with other data, such as statistics history, which may be combined with other data, such as statistics
maintained by the link layer. The rxcost is sent to a neighbour in maintained by the link layer. The rxcost is sent to a neighbour in
each IHU. each IHU.
How the txcost and rxcost are combined in order to compute a link's How the txcost and rxcost are combined in order to compute a link's
cost is a matter of local policy; as far as Babel's correctness is cost is a matter of local policy; as far as Babel's correctness is
concerned, only the following conditions MUST be satisfied: concerned, only the following conditions MUST be satisfied:
o the cost is strictly positive; o the cost is strictly positive;
o if no hellos were received recently, then the cost is infinite; o if no Hello TLVs of either kind were received recently, then the
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 Note that while this document does not constrain cost computation any
further, not all cost computation strategies will give good results. further, not all cost computation strategies will give good results.
We give a few examples of strategies for computing a link's cost that See Appendix A.2 for examples of strategies for computing a link's
are known to work well in practice in Appendix A.2. 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 19, line 18 skipping to change at page 20, line 12
satisfied, the update is either ignored or treated as a retraction, satisfied, the update is either ignored or treated as a retraction,
depending on some other conditions (Section 3.5.4). If the depending on some other conditions (Section 3.5.4). If the
feasibility condition is satisfied, then the update cannot possibly feasibility condition is satisfied, then the update cannot possibly
cause a routing loop, and the update is accepted. cause a routing loop, and the update is accepted.
3.5.1. The Feasibility Condition 3.5.1. The Feasibility Condition
The feasibility condition is applied to all received updates. The The feasibility condition is applied to all received updates. The
feasibility condition compares the metric in the received update with feasibility condition compares the metric in the received update with
the metrics of the updates previously sent by the receiving node; the metrics of the updates previously sent by the receiving node;
updates with finite metrics large enough to cause a loop are updates that fail the feasibility condition, and therefore have
discarded. metrics large enough to cause a routing loop, are either discarded or
prevent the resulting route from being selected.
A feasibility distance is a pair (seqno, metric), where seqno is an A feasibility distance is a pair (seqno, metric), where seqno is an
integer modulo 2^16 and metric is a positive integer. Feasibility integer modulo 2^16 and metric is a positive integer. Feasibility
distances are compared lexicographically, with the first component distances are compared lexicographically, with the first component
inverted: we say that a distance (seqno, metric) is strictly better inverted: we say that a distance (seqno, metric) is strictly better
than a distance (seqno', metric'), written than a distance (seqno', metric'), written
(seqno, metric) < (seqno', metric') (seqno, metric) < (seqno', metric')
when when
seqno > seqno' or (seqno = seqno' and metric < metric') seqno > seqno' or (seqno = seqno' and metric < metric')
where sequence numbers are compared modulo 2^16. where sequence numbers are compared modulo 2^16.
Given a source (p, plen, router-id), a node's feasibility distance Given a source (prefix, plen, router-id), a node's feasibility
for this source is the minimum, according to the ordering defined distance for this source is the minimum, according to the ordering
above, of the distances of all the finite updates ever sent by this defined above, of the distances of all the finite updates ever sent
particular node for the prefix (p, plen) and the given router-id. by this particular node for the prefix (prefix, plen) and the given
Feasibility distances are maintained in the source table; the exact router-id. Feasibility distances are maintained in the source table;
procedure is given in Section 3.7.3. the exact procedure is given in Section 3.7.3.
A received update is feasible when either it is a retraction (its A received update is feasible when either it is a retraction (its
metric is FFFF hexadecimal), or the advertised distance is strictly metric is FFFF hexadecimal), or the advertised distance is strictly
better, in the sense defined above, than the feasibility distance for better, in the sense defined above, than the feasibility distance for
the corresponding source. More precisely, a route advertisement the corresponding source. More precisely, a route advertisement
carrying the quintuple (prefix, plen, router-id, seqno, metric) is carrying the quintuple (prefix, plen, router-id, seqno, metric) is
feasible if one of the following conditions holds: feasible if one of the following conditions holds:
o metric is infinite; or o metric is infinite; or
skipping to change at page 21, line 10 skipping to change at page 22, line 7
updates; hence, some care has been given to encoding them updates; hence, some care has been given to encoding them
efficiently. An Update TLV itself only contains the prefix, seqno, efficiently. An Update TLV itself only contains the prefix, seqno,
and metric, while the next hop is derived either from the network- and metric, while the next hop is derived either from the network-
layer source address of the packet or from an explicit Next Hop TLV layer source address of the packet or from an explicit Next Hop TLV
in the same packet. The router-id is derived from a separate Router- in the same packet. The router-id is derived from a separate Router-
Id TLV in the same packet, which optimises the case when multiple Id TLV in the same packet, which optimises the case when multiple
updates are sent with the same router-id. updates are sent with the same router-id.
Additionally, a prefix of the advertised prefix can be omitted in an Additionally, a prefix of the advertised prefix can be omitted in an
Update TLV, in which case it is copied from a previous Update TLV in Update TLV, in which case it is copied from a previous Update TLV in
the same packet -- this is known as address compression [PACKETBB]. the same packet -- this is known as address compression
(Section 4.6.9).
Finally, as a special optimisation for the case when a router-id 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.6. The encoding of updates is described in detail in Section 4.6.
3.5.4. Route Acquisition 3.5.4. Route Acquisition
When a Babel node receives an update (router-id, prefix, seqno, When a Babel node receives an update (router-id, prefix, seqno,
metric) from a neighbour neigh with a link cost value equal to cost, metric) from a neighbour neigh with a link cost value equal to cost,
it checks whether it already has a routing table entry indexed by it checks whether it already has a routing table entry indexed by
(neigh, router-id, prefix). (neigh, 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 MAY be 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 of a route
is ignored; we do not know about), the update 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,
router-id, prefix), with seqno equal to seqno and an advertised prefix), with source equal to (router-id, prefix), seqno equal to
metric equal to the metric carried by the update. seqno and an advertised 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 selected, the update is unfeasible, and
then the behaviour depends on whether the router-ids of the two the router-id of the update is equal to the router-id of the
entries match. If the router-ids are different, the update is entry, then the update MAY be silently ignored;
treated as though it were a retraction (i.e., as though the metric
were FFFF hexadecimal). If the router-ids are equal, the update
is ignored;
o otherwise (i.e., if either the update is feasible or the entry is o otherwise, the entry's sequence number, advertised metric, metric,
not currently installed), then the entry's sequence number, and router-id are updated and, if the advertised metric is not
advertised metric, metric, and router-id are updated and, unless infinite, the route's expiry timer is reset to a small multiple of
the advertised metric is infinite, the route's expiry timer is the Interval value included in the update. If the update is
reset to a small multiple of the Interval value included in the unfeasible, then the (now unfeasible) entry MUST be immediately
update. unselected, and, if the update caused the router-id of the entry
to change, an update (possibly a retraction) MUST be sent in a
timely manner (see Section 3.7.2).
Note that the route table may contain unfeasible routes, either
because they were created by an unfeasible update or due to a metric
fluctuation. Such routes are never selected, since they are not
known to be loop-free; should all the feasible routes become
unusable, however, the unfeasible routes can be made feasible by
sending requests along them (see Section 3.8.2).
When a route's expiry timer triggers, the behaviour depends on When a route's expiry timer triggers, the behaviour depends on
whether the route's metric is finite. If the metric is finite, it is whether the route's metric is finite. If the metric is finite, it is
set to infinity and the expiry timer is reset. If the metric is set to infinity and the expiry timer is reset. If the metric is
already infinite, the route is flushed from the route table. already infinite, the route is flushed from the route table.
After the routing table is updated, the route selection procedure After the routing table is updated, the route selection procedure
(Section 3.6) is run. (Section 3.6) is run.
3.5.5. Hold Time 3.5.5. Hold Time
When a prefix p is retracted, because all routes are unfeasible, too When a prefix P is retracted, because all routes are unfeasible or
old, or have an infinite metric, and a shorter prefix p' that covers have an infinite metric (whether due to the expiry timer or to other
p is reachable, p' cannot in general be used for routing packets reasons), and a shorter prefix P' that covers P is reachable, P'
destined to p without running the risk of creating a routing loop cannot in general be used for routing packets destined to P without
(Section 2.8). running the risk of creating a routing loop (Section 2.8).
To avoid this issue, whenever a prefix is retracted, a routing table To avoid this issue, whenever a prefix P is retracted, a routing
entry with infinite metric is maintained as described in table entry with infinite metric is inserted as described in
Section 3.5.4 above, and packets destined for that prefix MUST NOT be Section 3.5.4 above. As long as this entry is maintained, packets
forwarded by following a route for a shorter prefix. The infinite destined to an address within P MUST NOT be forwarded by following a
metric entry is maintained until it is superseded by a feasible route for a shorter prefix. This entry is removed as soon as a
update; if no such update arrives within the route hold time, the finite-metric update for prefix P is received and the resulting route
entry is flushed. selected. If no such update is forthcoming, the infinite metric
entry MUST be maintained at least until it is guaranteed that no
neighbour has selected the current node as next-hop for prefix P.
This can be achieved by either:
o waiting until the route's expiry timer has expired (Section 3.5.4)
o sending a retraction with an acknowledgement request (Section 3.3)
to every neighbour that has not explicitly retracted prefix P and
waiting for all acknowledgements.
The former option is simpler and ensures that at that point, any
routes for prefix P pointing at the current node have expired.
However, since the expiry time can be as high as a few minutes, doing
that prevents automatic aggregation by creating spurious black-holes
for aggregated routes. The latter option is RECOMMENDED as it
reduces convergence time.
3.6. Route Selection 3.6. Route Selection
Route selection is the process by which a single route for a given Route selection is the process by which a single route for a given
prefix is selected to be used for forwarding packets and to be re- prefix is selected to be used for forwarding packets and to be re-
advertised to a node's neighbours. advertised to a node's neighbours.
Babel is designed to allow flexible route selection policies. As far Babel is designed to allow flexible route selection policies. As far
as the protocol's correctness is concerned, the route selection as the protocol's correctness is concerned, the route selection
policy MUST only satisfy the following properties: policy MUST only satisfy the following properties:
skipping to change at page 25, line 36 skipping to change at page 27, line 17
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.
Split horizon SHOULD NOT be applied to an interface unless the Split horizon SHOULD NOT be applied to an interface unless the
interface is known to be symmetric and transitive; in particular, interface is known to be symmetric and transitive; in particular,
split horizon is not applicable to decentralised wireless link split horizon is not applicable to decentralised wireless link
technologies (e.g., IEEE 802.11 in ad hoc mode). technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates
are sent over multicast.
3.8. Explicit Route Requests 3.8. Explicit Route Requests
In normal operation, a node's routing table is populated by the In normal operation, a node's routing table is populated by the
regular and triggered updates sent by its neighbours. Under some regular and triggered updates sent by its neighbours. Under some
circumstances, however, a node sends explicit requests to cause a circumstances, however, a node sends explicit requests to cause a
resynchronisation with the source after a mobility event or to resynchronisation with the source after a mobility event or to
prevent a route from spuriously expiring. prevent a route from spuriously expiring.
The Babel protocol provides two kinds of explicit requests: route The Babel protocol provides two kinds of explicit requests: route
requests, which simply request an update for a given prefix, and requests, which simply request an update for a given prefix, and
seqno requests, which request an update for a given prefix with a seqno requests, which request an update for a given prefix with a
specific sequence number. The former are never forwarded; the latter specific sequence number. The former are never forwarded; the latter
are forwarded if they cannot be satisfied by a neighbour. are forwarded if they cannot be satisfied by the receiver.
3.8.1. Handling Requests 3.8.1. Handling Requests
Upon receiving a request, a node either forwards the request or sends Upon receiving a request, a node either forwards the request or sends
an update in reply to the request, as described in the following an update in reply to the request, as described in the following
sections. If this causes an update to be sent, the update is either sections. If this causes an update to be sent, the update is either
sent to a multicast address on the interface on which the request was sent to a multicast address on the interface on which the request was
received, or to the unicast address of the neighbour that sent the received, or to the unicast address of the neighbour that sent the
update. update.
skipping to change at page 27, line 5 skipping to change at page 28, line 34
request's hop count is 2 or more, and the node has a route (not request's hop count is 2 or more, and the node has a route (not
necessarily a feasible one) for the requested prefix that does not necessarily a feasible one) for the requested prefix that does not
use the requestor as a next hop, the node MUST forward the request if use the requestor as a next hop, the node MUST forward the request if
it has a feasible route to the requested prefix and it is advertising it has a feasible route to the requested prefix and it is advertising
this prefix to neighbours, and SHOULD forward the request if it has a this prefix to neighbours, and SHOULD forward the request if it has a
(not necessarily feasible) route to the requested prefix. It does so (not necessarily feasible) route to the requested prefix. It does so
by decreasing the hop count and sending the request in a unicast by decreasing the hop count and sending the request in a unicast
packet destined to a neighbour that advertises the given prefix and packet destined to a neighbour that advertises the given prefix and
that is not the neighbour from which the request was received. that is not the neighbour from which the request was received.
A node SHOULD maintain a list of recently forwarded requests and A node SHOULD maintain a list of recently forwarded seqno requests
forward the reply (an update with a sufficiently large seqno) in a and forward the reply (an update with a sufficiently large seqno) in
timely manner. A node SHOULD compare every incoming request against a timely manner. A node SHOULD compare every incoming seqno request
its list of recently forwarded requests and avoid forwarding it if it against its list of recently forwarded seqno requests and avoid
is redundant. forwarding it if it is redundant (i.e., if it has recently sent a
request with the same prefix, router-id and a seqno that is not
smaller).
Since the request-forwarding mechanism does not necessarily obey the Since the request-forwarding mechanism does not necessarily obey the
feasibility condition, it may get caught in routing loops; hence, feasibility condition, it may get caught in routing loops; hence,
requests carry a hop count to limit the time for which they remain in requests carry a hop count to limit the time for which they remain in
the network. However, since requests are only ever forwarded as the network. However, since requests are only ever forwarded as
unicast packets, the initial hop count need not be kept particularly unicast packets, the initial hop count need not be kept particularly
low, and performing an expanding horizon search is not necessary. A low, and performing an expanding horizon search is not necessary. A
request MUST NOT be forwarded to a multicast address, and it MUST NOT single request MUST NOT be duplicated: it MUST NOT be forwarded to a
be forwarded to multiple neighbours. multicast address, and it MUST NOT be forwarded to multiple
neighbours. However, if a seqno request is resent, the subsequent
copies MAY be sent to a different neighbour than the initial one. If
the route corresponding to a seqno request is unselected between
retransmissions, the node SHOULD stop retransmitting requests for it.
3.8.2. Sending Requests 3.8.2. Sending Requests
A Babel node MAY send a route or seqno request at any time, to a A Babel node MAY send a route or seqno request at any time, to a
multicast or a unicast address; there is only one case when multicast or a unicast address; there is only one case when
originating requests is required (Section 3.8.2.1). originating requests is required (Section 3.8.2.1).
3.8.2.1. Avoiding Starvation 3.8.2.1. Avoiding Starvation
When a route is retracted or expires, a Babel node usually switches When a route is retracted or expires, a Babel node usually switches
skipping to change at page 29, line 48 skipping to change at page 31, line 38
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. A router-id MUST NOT consist of A router-id is an arbitrary 8-octet value. A router-id MUST NOT
either all zeroes or all ones. Router-ids SHOULD be assigned in consist of either all zeroes or all ones. Router-ids SHOULD be
modified EUI-64 format [ADDRARCH]. 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 (Section 4.6.9).
Address encodings: Address encodings:
o AE 0: wildcard address. The value is 0 octets long. o AE 0: wildcard address. The value is 0 octets long.
o AE 1: IPv4 address. Compression is allowed. 4 octets or less. o AE 1: IPv4 address. Compression is allowed. 4 octets or less.
o AE 2: IPv6 address. Compression is allowed. 16 octets or less. o AE 2: IPv6 address. Compression is allowed. 16 octets or less.
o AE 3: link-local IPv6 address. The value is 8 octets long, a o AE 3: link-local IPv6 address. Compression is not allowed. The
prefix of fe80::/64 is implied. value is 8 octets long, a prefix of fe80::/64 is implied.
The address family of an address is either IPv4 or IPv6; it is The address family of an address is either IPv4 or IPv6; it is
undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3.
4.1.4. Prefixes 4.1.4. Prefixes
A network prefix is encoded just like a network address, but it is A network prefix is encoded just like a network address, but it is
stored in the smallest number of octets that are enough to hold the stored in the smallest number of octets that are enough to hold the
significant bits (up to the prefix length). significant bits (up to the prefix length).
skipping to change at page 32, line 37 skipping to change at page 34, line 24
updating the parser state by a Router-ID, Next-Hop or Update TLV, see updating the parser state by a Router-ID, Next-Hop or Update TLV, see
Section 4.6.7, Section 4.6.8, and Section 4.6.9). Section 4.6.7, Section 4.6.8, and Section 4.6.9).
4.5. Parser state 4.5. Parser state
Babel uses a stateful parser: a TLV may refer to data from a previous Babel uses a stateful parser: a TLV may refer to data from a previous
TLV. Babel's parser state consists of the following pieces of data: TLV. Babel's parser state consists of the following pieces of data:
o for each address encoding that allows compression, the current o for each address encoding that allows compression, the current
default prefix; this is undefined at the start of the packet, and default prefix; this is undefined at the start of the packet, and
is updated by an Update TLV with flag 80 hexadecimal set is updated by an Update TLV with the PREFIX flag set
(Section 4.6.9); (Section 4.6.9);
o for each address family (IPv4 or IPv6), the current next-hop; this o for each address family (IPv4 or IPv6), the current next-hop; this
is the source address of the enclosing packet for the matching is the source address of the enclosing packet for the matching
address family at the start of a packet, and is updated by the address family at the start of a packet, and is updated by the
Next-Hop TLV (Section 4.6.8); Next-Hop TLV (Section 4.6.8);
o the current router-id; this is undefined at the start of the o the current router-id; this is undefined at the start of the
packet, and is updated by both the Router-ID TLV (Section 4.6.7) packet, and is updated by both the Router-ID TLV (Section 4.6.7)
and the Update TLV with flag 40 hexadecimal set. and the Update TLV with ROUTER-ID flag set.
Since the parser state is separate from the bulk of Babel's state, Since the parser state is separate from the bulk of Babel's state,
and for correct parsing must be identical across implementations, it and for correct parsing must be identical across implementations, it
is updated before checking for mandatory TLVs: parsing a TLV updates is updated before checking for mandatory TLVs: parsing a TLV updates
the parser state even if the TLV is otherwise ignored due to an the parser state even if the TLV is otherwise ignored due to an
unknown mandatory sub-TLV. unknown mandatory sub-TLV.
4.6. Details of Specific TLVs 4.6. Details of Specific TLVs
4.6.1. Pad1 4.6.1. Pad1
skipping to change at page 35, line 10 skipping to change at page 36, line 42
Since nonce values are not globally unique, this TLV MUST be sent to Since nonce values are not globally unique, this TLV MUST be sent to
a unicast address. a unicast address.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.5. Hello 4.6.5. Hello
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 4 | Length | Reserved | | Type = 4 | Length | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Interval | | Seqno | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV is used for neighbour discovery and for determining a link's This TLV is used for neighbour discovery and for determining a
reception cost. neighbour's reception cost.
Fields : Fields :
Type Set to 4 to indicate a Hello TLV. Type Set to 4 to indicate a Hello TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body, exclusive of the Type and Length
fields. fields.
Reserved Sent as 0 and MUST be ignored on reception. Flags The individual bits of this field specify special handling
of this TLV (see below).
Seqno The value of the sending node's Hello seqno for this Seqno If the UNICAST flag is set, this is the value of the
interface. sending node's outgoing Unicast Hello seqno for this
neighbour. Otherwise, it is the sending node's outgoing
Multicast Hello seqno for this interface.
Interval An upper bound, expressed in centiseconds, on the time Interval If non-zero, this is an upper bound, expressed in
after which the sending node will send a new Hello TLV. centiseconds, on the time after which the sending node will
This MUST NOT be 0. send a new scheduled Hello TLV with the same setting of the
UNICAST flag. If this is 0, then this Hello represents an
unscheduled Hello, and doesn't carry any new information
about times at which Hellos are sent.
Since there is a single seqno counter for all the Hellos sent by a The Flags field is interpreted as follows:
given node over a given interface, this TLV MUST be sent to a
multicast destination. In order to avoid large discontinuities in +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
link quality, multiple Hello TLVs SHOULD NOT be sent in the same |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
packet. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
In the description below, a bit being 'set' means its value is '1',
while 'cleared' means its value is '0'. 'X' bits MUST be cleared
when sending and MUST be ignored on receipt. Every node MUST be able
to interpret the UNICAST flag.
o U (UNICAST) flag (8000 hexadecimal): if set, then this Hello
represents a Unicast Hello, otherwise it represents a Multicast
Hello.
Every time a Hello is sent, the corresponding seqno counter MUST be
incremented. Since there is a single seqno counter for all the
Multicast Hellos sent by a given node over a given interface, if the
UNICAST flag is not set, this TLV MUST be sent to all neighbors on
this link, which can be achieved by sending to a multicast
destination, or repeatedly sending unicast to all known neighbours.
Similarly, if the UNICAST flag is set, this TLV MUST be sent to a
single neighbour, which can achieved by sending to a unicast
destination. In order to avoid large discontinuities in link
quality, multiple Hello TLVs SHOULD NOT be sent in the same packet.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.6. IHU 4.6.6. IHU
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 5 | Length | AE | Reserved | | Type = 5 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 36, line 37 skipping to change at page 38, line 50
Interval An upper bound, expressed in centiseconds, on the time Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new IHU; this MUST after which the sending node will send a new IHU; this MUST
NOT be 0. The receiving node will use this value in order NOT be 0. The receiving node will use this value in order
to compute a hold time for this symmetric association. to compute a hold time for this symmetric association.
Address The address of the destination node, in the format Address The address of the destination node, in the format
specified by the AE field. Address compression is not specified by the AE field. Address compression is not
allowed. allowed.
Conceptually, an IHU is destined to a single neighbour. However, IHU Conceptually, an IHU is destined to a single neighbour. However, IHU
TLVs contain an explicit destination address, and it SHOULD be sent TLVs contain an explicit destination address, and it MAY be sent to a
to a multicast address, as this allows aggregation of IHUs destined multicast address, as this allows aggregation of IHUs destined to
to distinct neighbours into a single packet and avoids the need for distinct neighbours into a single packet and avoids the need for an
an ARP or Neighbour Discovery exchange when a neighbour is not being ARP or Neighbour Discovery exchange when a neighbour is not being
used for data traffic. used for data traffic.
IHU TLVs with an unknown value for the AE field MUST be silently IHU TLVs with an unknown value for the AE field MUST be silently
ignored. ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.7. Router-Id 4.6.7. Router-Id
0 1 2 3 0 1 2 3
skipping to change at page 39, line 6 skipping to change at page 41, line 13
Fields : Fields :
Type Set to 8 to indicate an Update TLV. Type Set to 8 to indicate an Update TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body, exclusive of the Type and Length
fields. fields.
AE The encoding of the Prefix field. AE The encoding of the Prefix field.
Flags The individual bits of this field specify special handling Flags The individual bits of this field specify special handling
of this TLV (see below). Every node MUST be able to of this TLV (see below).
interpret the flags with values 80 and 40 hexadecimal;
unknown flags MUST be silently ignored.
Plen The length of the advertised prefix. Plen The length of the advertised prefix.
Omitted The number of octets that have been omitted at the Omitted The number of octets that have been omitted at the
beginning of the advertised prefix and that should be taken beginning of the advertised prefix and that should be taken
from a preceding Update TLV with the flag with value 80 from a preceding Update TLV with the PREFIX flag set.
hexadecimal set.
Interval An upper bound, expressed in centiseconds, on the time Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new update for after which the sending node will send a new update for
this prefix. This MUST NOT be 0 and SHOULD NOT be less this prefix. This MUST NOT be 0 and SHOULD NOT be less
than 10. The receiving node will use this value to compute than 10. The receiving node will use this value to compute
a hold time for this routing table entry. The value FFFF a hold time for this routing table entry. The value FFFF
hexadecimal (infinity) expresses that this announcement hexadecimal (infinity) expresses that this announcement
will not be repeated unless a request is received will not be repeated unless a request is received
(Section 3.8.2.3). (Section 3.8.2.3).
skipping to change at page 39, line 37 skipping to change at page 41, line 41
Metric The sender's metric for this route. The value FFFF Metric The sender's metric for this route. The value FFFF
hexadecimal (infinity) means that this is a route hexadecimal (infinity) means that this is a route
retraction. retraction.
Prefix The prefix being advertised. This field's size is (Plen/8 Prefix The prefix being advertised. This field's size is (Plen/8
- Omitted) rounded upwards. - Omitted) rounded upwards.
The Flags field is interpreted as follows: The Flags field is interpreted as follows:
o if the bit with value 80 hexadecimal is set, then this Update +-+-+-+-+-+-+-+-+
|P|R|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+
In the description below, a bit being 'set' means its value is '1',
while 'cleared' means its value is '0'. 'X' bits MUST be cleared
when sending and MUST be ignored on receipt. Every node MUST be able
to interpret the PREFIX and ROUTER-ID flags.
o P (PREFIX) flag (80 hexadecimal): if set, then this Update
establishes a new default prefix for subsequent Update TLVs with a establishes a new default prefix for subsequent Update TLVs with a
matching address encoding within the same packet, even if this TLV matching address encoding within the same packet, even if this TLV
is otherwise ignored due to an unknown mandatory sub-TLV; is otherwise ignored due to an unknown mandatory sub-TLV;
o if the bit with value 40 hexadecimal is set, then this TLV o R (ROUTER-ID) flag (40 hexadecimal): if set, then this TLV
establishes a new default router-id for this TLV and subsequent establishes a new default router-id for this TLV and subsequent
Update TLVs in the same packet, even if this TLV is otherwise Update TLVs in the same packet, even if this TLV is otherwise
ignored due to an unknown mandatory sub-TLV. This router-id is ignored due to an unknown mandatory sub-TLV. This router-id is
computed from the first address of the advertised prefix as computed from the first address of the advertised prefix as
follows: follows:
* if the length of the address is 8 octets or more, then the new * if the length of the address is 8 octets or more, then the new
router-id is taken from the 8 last octets of the address; router-id is taken from the 8 last octets of the address;
* if the length of the address is smaller than 8 octets, then the * if the length of the address is smaller than 8 octets, then the
new router-id consists of the required number of zero octets new router-id consists of the required number of zero octets
followed by the address, i.e., the address is stored on the followed by the address, i.e., the address is stored on the
right of the router-id. For example, for an IPv4 address, the right of the router-id. For example, for an IPv4 address, the
router-id consists of 4 octets of zeroes followed by the IPv4 router-id consists of 4 octets of zeroes followed by the IPv4
address. address.
The prefix being advertised by an Update TLV is computed as follows: The prefix being advertised by an Update TLV is computed as follows:
o the first Omitted octets of the prefix are taken from the previous o the first Omitted octets of the prefix are taken from the previous
Update TLV with flag 80 hexadecimal set and the same address Update TLV with the PREFIX flag set and the same address encoding,
encoding, even if it was ignored due to an unknown mandatory sub- even if it was ignored due to an unknown mandatory sub-TLV;
TLV;
o the next (Plen/8 - Omitted) rounded upwards octets are taken from o the next (Plen/8 - Omitted) rounded upwards octets are taken from
the Prefix field; the Prefix field;
o the remaining octets are set to 0. o the remaining octets are set to 0. If AE is 3 (link-local IPv6),
Omitted MUST be 0)
If the Metric field is finite, the router-id of the originating node If the Metric field is finite, the router-id of the originating node
for this announcement is taken from the prefix advertised by this for this announcement is taken from the prefix advertised by this
Update if the bit with value 40 hexadecimal is set in the Flags Update if the ROUTER-ID flag is set, computed as described above.
field, computed as described above. Otherwise, it is taken either Otherwise, it is taken either from the preceding Router-Id packet, or
from the preceding Router-Id packet, or the preceding Update packet the preceding Update packet with the ROUTER-ID flag set, whichever
with flag 40 hexadecimal set, whichever comes last, even if that TLV comes last, even if that TLV is otherwise ignored due to an unknown
is otherwise ignored due to an unknown mandatory sub-TLV. mandatory sub-TLV.
The next-hop address for this update is taken from the last preceding The next-hop address for this update is taken from the last preceding
Next Hop TLV with a matching address family (IPv4 or IPv6) in the Next Hop TLV with a matching address family (IPv4 or IPv6) in the
same packet even if it was otherwise ignored due to an unknown same packet even if it was otherwise ignored due to an unknown
mandatory sub-TLV; if no such TLV exists, it is taken from the mandatory sub-TLV; if no such TLV exists, it is taken from the
network-layer source address of this packet. network-layer source address of this packet.
If 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 current router-id and the Seqno are retraction. In that case, the current router-id and the Seqno are
not used. AE MAY then be 0, in which case this Update retracts all not used. AE MAY then be 0, in which case this Update retracts all
of the routes previously advertised on this interface. of the routes previously advertised on this interface. If the metric
is finite, AE MUST NOT be 0. If the metric is infinite and AE is 0,
Plen and Omitted MUST both be 0.
Update TLVs with an unknown value for the AE field MUST be silently Update TLVs with an unknown value for the AE field MUST be silently
ignored. ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.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 routing table dump. given prefix, or a full routing table dump.
skipping to change at page 44, line 30 skipping to change at page 46, line 35
location with reasonable precision. The privacy issues that this location with reasonable precision. The privacy issues that this
causes can be mitigated somewhat by using randomly chosen router-ids causes can be mitigated somewhat by using randomly chosen router-ids
and randomly chosen IP addresses, and changing them periodically. and randomly chosen IP addresses, and changing them periodically.
When carried over IPv6, Babel packets are ignored unless they are When carried over IPv6, Babel packets are ignored unless they are
sent from a link-local IPv6 address; since routers don't forward sent from a link-local IPv6 address; since routers don't forward
link-local IPv6 packets, this provides protection against spoofed link-local IPv6 packets, this provides protection against spoofed
Babel packets being sent from the global Internet. No such natural Babel packets being sent from the global Internet. No such natural
protection exists when Babel packets are carried over IPv4. protection exists when Babel packets are carried over IPv4.
7. References 7. Acknowledgments
7.1. Normative References A number of people have contributed text and ideas to this
specification. I am particularly indebted to Matthieu Boutier,
Gwendoline Chouasne, Toke Hoiland-Jorgensen, and especially David
Schinazi. The address compression technique was inspired by
[PACKETBB].
8. References
8.1. Normative References
[ADDRARCH] [ADDRARCH]
Hinden, R. and S. Deering, "IP Version 6 Addressing Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 4291, February 2006. Architecture", RFC 4291, February 2006.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997. Requirement Levels", RFC 2119, March 1997.
7.2. Informative References 8.2. Informative References
[DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-
Sequenced Distance-Vector Routing (DSDV) for Mobile Sequenced Distance-Vector Routing (DSDV) for Mobile
Computers", ACM SIGCOMM'94 Conference on Communications Computers", ACM SIGCOMM'94 Conference on Communications
Architectures, Protocols and Applications 234-244, 1994. Architectures, Protocols and Applications 234-244, 1994.
[DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing
Computations", IEEE/ACM Transactions on Networking 1:1, Computations", IEEE/ACM Transactions on Networking 1:1,
February 1993. February 1993.
skipping to change at page 45, line 42 skipping to change at page 48, line 5
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 gives a few strategies on different interface types. This section gives a few
examples of such strategies. examples of such strategies.
The sample implementation of Babel maintains statistics about the The sample implementation of Babel sends periodic Multicast Hellos,
last 16 received Hello TLVs (Appendix A.1), computes costs by using and never sends Unicast Hellos. It maintains statistics about the
the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX last 16 received Multicast Hello TLVs of each kind (Appendix A.1),
(Appendix A.2.2) on wireless links. It uses an additive algebra for computes costs by using the 2-out-of-3 strategy (Appendix A.2.1) on
metric computation (Appendix A.3.1). wired links, and ETX (Appendix A.2.2) on wireless links. It uses an
additive algebra for metric computation (Appendix A.3.1).
A.1. Maintaining Hello History A.1. Maintaining Hello History
For each neighbour, the sample implementation of Babel maintains a For each neighbour, the sample implementation of Babel maintains two
Hello history and an expected sequence number. The Hello history is sets of Hello history, one for each kind of Hello, and an expected
a vector of 16 bits, where a 1 value represents a received Hello, and sequence number, one for Multicast and one for Unicast Hellos. Each
a 0 value a missed Hello. The expected sequence number, written ne, Hello history is a vector of 16 bits, where a 1 value represents a
is the sequence number that is expected to be carried by the next received Hello, and a 0 value a missed Hello. For each kind of
received hello from this neighbour. Hello, the expected sequence number, written ne, is the sequence
number that is expected to be carried by the next received Hello from
this neighbour.
Whenever it receives a Hello packet from a neighbour, a node compares Whenever it receives a Hello packet of a given kind from a neighbour,
the received sequence number nr with its expected sequence number ne. a node compares the received sequence number nr for that kind of
Depending on the outcome of this comparison, one of the following Hello with its expected sequence number ne. Depending on the outcome
actions is taken: of this comparison, one of the following actions is taken:
o if the two differ by more than 16 (modulo 2^16), then the sending o if the two differ by more than 16 (modulo 2^16), then the sending
node has probably rebooted and lost its sequence number; the node has probably rebooted and lost its sequence number; the whole
associated neighbour table entry is flushed; associated neighbour table entry is flushed and a new one created;
o otherwise, if the received nr is smaller (modulo 2^16) than the o otherwise, if the received nr is smaller (modulo 2^16) than the
expected sequence number ne, then the sending node has increased expected sequence number ne, then the sending node has increased
its Hello interval without our noticing; the receiving node its Hello interval without us noticing; the receiving node removes
removes the last (ne - nr) entries from this neighbour's Hello the last (ne - nr) entries from this neighbour's Hello history (we
history (we "undo history"); "undo history");
o otherwise, if nr is larger (modulo 2^16) than ne, then the sending o otherwise, if nr is larger (modulo 2^16) than ne, then the sending
node has decreased its Hello interval, and some Hellos were lost; node has decreased its Hello interval, and some Hellos were lost;
the receiving node adds (nr - ne) 0 bits to the Hello history (we the receiving node adds (nr - ne) 0 bits to the Hello history (we
"fast-forward"). "fast-forward").
The receiving node then appends a 1 bit to the neighbour's Hello The receiving node then appends a 1 bit to the Hello history, resets
history, resets the neighbour's Hello timer, and sets ne to (nr + 1). the neighbour's hello timer, and sets ne to (nr + 1). If the
It then resets the neighbour's Hello timer to 1.5 times the value Interval field of the received Hello is not zero, it resets the
advertised in the received Hello (the extra margin allows for the neighbour's hello timer to 1.5 times the advertised Interval (the
delay due to jitter). extra margin allows for delay due to jitter).
Whenever the Hello timer associated to a neighbour expires, the local Whenever either Hello timer associated to a neighbour expires, the
node adds a 0 bit to this neighbour's Hello history, and increments local node adds a 0 bit to this neighbour's Hello history, and
the expected Hello number. If the Hello history is empty (it increments the expected Hello number. If both Hello histories are
contains 0 bits only), the neighbour entry is flushed; otherwise, it empty (they contain 0 bits only), the neighbour entry is flushed;
resets the neighbour's Hello timer to the value advertised in the otherwise, the neighbour's hello timer is reset to the value
last Hello received from this neighbour (no extra margin is necessary advertised in the last Hello of that kind received from this
in this case). neighbour (no extra margin is necessary in this case, since jitter
was already taken into 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.
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 K >= j, such that 0 < k <= j, and the nominal link cost, a constant K >=
1. A node keeps a history of the last j hellos; if k or more of 1. A node keeps a history of the last j hellos; if k or more of
those have been correctly received, the link is assumed to be up, and those have been correctly received, the link is assumed to be up, and
the rxcost is set to K; otherwise, the link is assumed to be down, the rxcost is set to K; otherwise, the link is assumed to be down,
and the rxcost is set to infinity. and the rxcost is set to infinity.
The cost of such a link is defined as Since Babel supports two kinds of Hellos, a Babel node performs k-
out-of-j twice for each neighbour, once on the Unicast and once on
the Multicast Hello history. If either of the instances of k-out-
of-j indicates that the link is up, then the link is assumed to be
up, and the rxcost is set to K; if both instances indicate that the
link is down, then the link is assumed to be down, and the rxcost is
set to infinity. In other words, the resulting rxcost is the minimum
of the rxcosts yielded by the two instances of k-out-of-j link
sensing.
The cost of a link performing k-out-of-j link sensing is defined as
follows:
o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;
o cost = txcost otherwise. o cost = txcost otherwise.
A.2.2. ETX A.2.2. ETX
The Estimated Transmission Cost metric [ETX] estimates the number of Unlike wired links, which are bimodal (either up or down), wireless
times that a unicast frame will be retransmitted by the IEEE 802.11 links exhibit continuous variation of the link quality. Naive
MAC, assuming infinite persistence. application of hop-count routing in networks that use wireless links
for transit tends to select long, lossy links in preference to
shorter, lossless links, which can dramatically reduce throughput.
A node uses a neighbour's Hello history to compute an estimate, For that reason, it is essential that a routing protocol designed to
written beta, of the probability that a Hello TLV is successfully support wireless links perform some form of link-quality estimation.
received. The rxcost is defined as 256/beta.
ETX [ETX] is a simple link-quality estimation algorithm that is
designed to work well with the IEEE 802.11 MAC. The IEEE 802.11 MAC
performs ARQ and rate adaptation on unicast frames, but not on
multicast frames, which are sent at a fixed rate with no ARQ;
therefore, measuring the loss rate of multicast frames yields a
useful estimate of a link's quality.
A node performing ETX link quality estimation uses a neighbour's
Multicast Hello history to compute an estimate, written beta, of the
probability that a Hello TLV is successfully received. Beta can be
simply computed as the fraction of 1 bits within a small number (say,
6) of the most recent entries in the Multicast Hello history, or it
can be an exponential average, or some combination of both
approaches.
Let alpha be MIN(1, 256/txcost), an estimate of the probability of Let alpha be MIN(1, 256/txcost), an estimate of the probability of
successfully sending a Hello TLV. The cost is then computed by successfully sending a Hello TLV. The cost is then computed by
cost = 256/(alpha * beta) cost = 256/(alpha * beta)
or, equivalently, or, equivalently,
cost = (MAX(txcost, 256) * rxcost) / 256. cost = (MAX(txcost, 256) * rxcost) / 256.
Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast
frames do not provide a useful measure of link quality, and therefore
ETX ignores the Unicast Hello history. Thus, a node performing ETX
link-quality estimation will not route through nodes unless they send
periodic Multicast Hellos (possibly in addition to Unicast Hellos).
A.3. Metric Computation A.3. Metric Computation
As described in Section 3.5.2, the metric advertised by a neighbour
is combined with the link cost to yield a metric.
A.3.1. Additive Metrics A.3.1. Additive Metrics
The simplest approach for obtaining a monotonic, isotonic metric is The simplest approach for obtaining a monotonic, isotonic metric is
to define the metric of a route as the sum of the costs of the 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 component links. More formally, if a neighbour advertises a route
with metric m over a link with cost c, then the resulting route has with metric m over a link with cost c, then the resulting route has
metric M(c, m) = c + m. metric M(c, m) = c + m.
A multiplicative metric can be converted to an additive one by taking A multiplicative metric can be converted to an additive one by taking
the logarithm (in some suitable base) of the link costs. the logarithm (in some suitable base) of the link costs.
skipping to change at page 48, line 13 skipping to change at page 51, line 19
as the monetary cost of a link, the node's battery status, CPU load, as the monetary cost of a link, the node's battery status, CPU load,
etc. This can be done by adding to every route's metric a value k etc. This can be done by adding to every route's metric a value k
that depends on the external data. For example, if a battery-powered that depends on the external data. For example, if a battery-powered
node receives an update with metric m over a link with cost c, it node receives an update with metric m over a link with cost c, it
might compute a metric M(c, m) = k + c + m, where k depends on the might compute a metric M(c, m) = k + c + m, where k depends on the
battery status. battery status.
In order to preserve strict monotonicity (Section 3.5.2), the value k In order to preserve strict monotonicity (Section 3.5.2), the value k
must be greater than -c. must be greater than -c.
A.4. Properties of Multicast and Unicast Hellos
While Multicast and Unicast Hellos can be used together by
implementations, how their timers differ is a local matter. On
reliable wired links, a node may choose to only use Multicast Hellos,
as they are sufficient for discovery and reachability detection, and
Unicast Hellos offer close to no benefits in those scenarios. On
unreliable wireless links where multicast has worse performance than
unicast, a node may rely more on Unicast Hellos and send them
alongside every unicast IHU it sends; it may also use a higher
Multicast Hello Interval as they are no longer necessary for
reachability detection but still allow discovery of new neighbours.
Appendix B. Constants Appendix B. Constants
The choice of time constants is a trade-off between fast detection of The choice of time constants is a trade-off between fast detection of
mobility events and protocol overhead. Two implementations of Babel mobility events and protocol overhead. Two implementations of Babel
with different time constants will interoperate, although the with different time constants will interoperate, although the
resulting convergence time will most likely be dictated by the resulting convergence time will most likely be dictated by the
slowest of the two implementations. slowest of the two implementations.
Experience with the sample implementation of Babel indicates that the Experience with the sample implementation of Babel indicates that the
Hello interval is the most important time constant: a mobility event Hello interval is the most important time constant: a mobility event
is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance
on triggered updates and explicit requests, the Update interval only on triggered updates and explicit requests, the Update interval only
has an effect on the time it takes for accurate metrics to be has an effect on the time it takes for accurate metrics to be
propagated after variations in link costs too small to trigger an propagated after variations in link costs too small to trigger an
unscheduled update. unscheduled update or in the presence of packet loss.
At the time of writing, the sample implementation of Babel uses the At the time of writing, the sample implementation of Babel uses the
following default values: following default values:
Hello Interval: 4 seconds on wireless links, 20 seconds on wired Multicast Hello Interval: 4 seconds.
links.
IHU Interval: the advertised IHU interval is always 3 times the IHU Interval: the advertised IHU interval is always 3 times the
Hello interval. IHUs are actually sent with each Hello on lossy Multicast Hello interval. IHUs are actually sent with each Hello
links (as determined from the Hello history), but only with every on lossy links (as determined from the Hello history), but only
third Hello on lossless links. with every third Multicast Hello on lossless links.
Update Interval: 4 times the Hello interval. Unicast Hello Interval: the sample implementation never sends
scheduled Unicast Hellos;
Update Interval: 4 times the Multicast Hello interval.
IHU Hold Time: 3.5 times the advertised IHU interval. IHU Hold Time: 3.5 times the advertised IHU interval.
Route Expiry Time: 3.5 times the advertised update interval. Route Expiry Time: 3.5 times the advertised update interval.
Source GC time: 3 minutes. Source GC time: 3 minutes.
The amount of jitter applied to a packet depends on whether it The amount of jitter applied to a packet depends on whether it
contains any urgent TLVs or not. Urgent triggered updates and urgent contains any urgent TLVs or not. Urgent triggered updates and urgent
requests are delayed by no more than 200ms; other TLVs are delayed by requests are delayed by no more than 200ms; other TLVs are delayed by
no more than one-half the Hello interval. no more than one-half the Multicast Hello interval.
Appendix C. Considerations for protocol extensions Appendix C. Considerations for protocol extensions
Babel is an extensible protocol, and this document defines a number Babel is an extensible protocol, and this document defines a number
of mechanisms that can be used to extend the protocol in a backwards of mechanisms that can be used to extend the protocol in a backwards
compatible manner: compatible manner:
o increasing the version number in the packet header; o increasing the version number in the packet header;
o defining new TLVs; o defining new TLVs;
o defining new sub-TLVs (with the mandatory bit set or not); 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.
New versions of the Babel protocol should only be defined if the new New versions of the Babel protocol should only be defined if the new
version is not backwards compatible with the original protocol. version is not backwards compatible with the original 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, or by adding a sub-TLV to the Update TLV. TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by
adding a mandatory TLV.
The two encodings are treated differently by implementations that do The various encodings are treated differently by implementations that
not understand the extension. In the case of a new TLV, the whole do not understand the extension. In the case of a new TLV or of a
unknown TLV is ignored by an implementation of the original protocol, sub-TLV with the mandatory bit set, the whole TLV is ignored by
while in the case of a new sub-TLV, the TLV is parsed and acted upon, implementations that do not implement the extension, while in the
and the unknown sub-TLV is silently ignored. Therefore, a sub-TLV case of a non-mandatory sub-TLV, the TLV is parsed and acted upon,
should be used by extensions that extend the Update in a compatible and only the unknown sub-TLV is silently ignored. Therefore, a non-
manner (the extension data may be silently ignored), while a new TLV mandatory sub-TLV should be used by extensions that extend the Update
must be used by extensions that make incompatible extensions to the in a compatible manner (the extension data may be silently ignored),
meaning of the TLV (the whole TLV must be thrown away if the while a mandatory sub-TLV or a new TLV must be used by extensions
extension data is not understood). that make incompatible extensions to the meaning of the TLV (the
whole TLV must be thrown away if the extension data is not
understood).
Experience shows that additional data tends to crop up in the most
unexpected places. Hence, it is recommended that extensions should
define self-terminating TLVs, and allow attaching sub-TLVs to them.
Adding a new AE is essentially equivalent to adding a new TLV: Update Adding a new AE is essentially equivalent to adding a new TLV: Update
TLVs with an unknown AE are ignored, just like unknown TLVs. TLVs with an unknown AE are ignored, just like unknown TLVs.
However, adding a new AE is often more involved than adding a new However, adding a new AE is often more involved than adding a new
TLV, since it creates a new set of compression state. Additionally, TLV, since it creates a new set of compression state. Additionally,
since the Next Hop TLV creates state specific to a given address since the Next Hop TLV creates state specific to a given address
family, as opposed to a given AE. A similar issue arises with Update family, as opposed to a given AE, a new AE for a previously defined
TLVs with unknown AEs establishing a new router-id (flag 40 address family must not be used in the Next Hop TLV if backwards
hexadecimal). Therefore, defining new AEs must be done with care if compatibility is required. A similar issue arises with Update TLVs
with unknown AEs establishing a new router-id (with ROUTER-ID flag
set). Therefore, defining new AEs must be done with care if
compatibility with unextended implementations is required. compatibility with unextended implementations is required.
The packet trailer -- the space after the declared length of the The packet trailer -- the space after the declared length of the
packet but within the payload of the UDP datagram -- was originally packet but within the payload of the UDP datagram -- was originally
intended to carry a cryptographic signature. However, at this time intended to carry a cryptographic signature. However, at this time
no extension has used it, and therefore we refrain from making any no extension has used it, and therefore we refrain from making any
recommendations about its use due to the lack of implementation recommendations about its use due to the lack of implementation
experience. experience.
Appendix D. Simplified Implementations Appendix D. Stub Implementations
Babel is a fairly economic protocol. Route updates take between 12 Babel is a fairly economic protocol. Updates take between 12 and 40
and 40 octets per destination, depending on how successful octets per destination, depending on the address family and how
compression is; in a double-stack mesh network, an average of less successful compression is; in a double-stack flat network, an average
than 24 octets is typical. The route table occupies about 35 octets of less than 24 octets per destination is typical. The route table
per IPv6 entry. To put these values into perspective, a single full- occupies about 35 octets per IPv6 entry. To put these values into
size Ethernet frame can carry some 65 route updates, and a megabyte perspective, a single full-size Ethernet frame can carry some 65
of memory can contain a 20000-entry routing table and the associated route updates, and a megabyte of memory can contain a 20000-entry
source table. routing table and the associated source table.
Babel is also a reasonably simple protocol. The sample Babel is also a reasonably simple protocol. The sample
implementation consists of less than 8000 lines of C code, and it implementation consists of less than 12 000 lines of C code, and it
compiles to less than 60 kB of text on a 32-bit CISC architecture. compiles to less than 120 kB of text on a 32-bit CISC architecture;
about half of this figure is due to protocol extensions and user-
interface code.
Nonetheless, in some very constrained environments, such as PDAs, Nonetheless, in some very constrained environments, such as PDAs,
microwave ovens, or abacuses, it may be desirable to have subset microwave ovens, or abacuses, it may be desirable to have subset
implementations of the protocol. implementations of the protocol.
A parasitic implementation is one that uses a Babel network for There are many different definitions of a stub router, but for the
routing its packets but does not announce any of the routes that it needs of this section a stub implementation of Babel is one that
has learnt from its neighbours. (This is slightly more than a announces one or more directly attached prefixes into a Babel network
passive implementation, which doesn't even announce routes to but doesn't reannounce any routes that it has learnt from its
itself.) It may either maintain a full routing table or simply neighbours. It may either maintain a full routing table, or simply
select a gateway amongst any one of its neighbours that announces a select a default gateway amongst any one of its neighbours that
default route. Since a parasitic implementation never forwards announces a default route. Since a stub implementation never
packets, it cannot possibly participate in a routing loop; hence, it forwards packets except from or to directly attached links, it cannot
need not evaluate the feasibility condition, and need not maintain a possibly participate in a routing loop, and hence it need not
source table. evaluate the feasibility condition or maintain a source table.
A parasitic implementation MUST answer acknowledgement requests and No matter how primitive, a stub implementation MUST parse sub-TLVs of
MUST participate in the Hello/IHU protocol. Finally, it MUST be able all the TLVs that it understands and check for the mandatory bit. It
to reply to seqno requests for routes that it announces and SHOULD be MUST answer acknowledgement requests and MUST participate in the
able to reply to route requests. Hello/IHU protocol (it MUST parse both Unicast and Multicast Hellos,
and SHOULD send scheduled Hellos, preferably over multicast in order
to make it discoverable). It MUST also be able to reply to seqno
requests for routes that it announces and SHOULD be able to reply to
route requests.
Experiments show that an IPv6-only stub implementation of Babel can
be written in less than 1000 lines of C code and compile to 13 kB of
text on 32-bit CISC architecture.
Appendix E. Software Availability Appendix E. 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/>. <https://www.irif.fr/~jch/software/babel/>.
Appendix F. Changes from previous versions Appendix F. Changes from previous versions
F.1. Changes since RFC 6126 F.1. Changes since RFC 6126
o Changed UDP port number to 6696. o Changed UDP port number to 6696.
o Consistently use router-id rather than id. o Consistently use router-id rather than id.
o Clarified that the source garbage collection timer is reset after o Clarified that the source garbage collection timer is reset after
skipping to change at page 52, line 5 skipping to change at page 55, line 42
o Clarified how router-ids are computed when bit 0x40 is set in o Clarified how router-ids are computed when bit 0x40 is set in
Updates. Updates.
o Relaxed the conditions for sending requests, and tightened the o Relaxed the conditions for sending requests, and tightened the
conditions for forwarding requests. conditions for forwarding requests.
o Clarified that neighbours should be acquired at some point, but it o Clarified that neighbours should be acquired at some point, but it
doesn't matter when. doesn't matter when.
F.4. Changes since draft-ietf-babel-rfc6126bis-02
o Added Unicast Hellos.
o Added unscheduled (interval-less) Hellos.
o Changed Appendix A to consider Unicast and unscheduled Hellos.
o Changed Appendix B to agree with the reference implementation.
o Added optional algorithm to avoid the hold time.
o Changed the table of pending seqno requests to be indexed by
router-id in addition to prefixes.
o Relaxed the route acquisition algorithm.
o Replaced minimal implementations by stub implementations.
o Added acknowledgements section.
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@irif.fr Email: jch@irif.fr
 End of changes. 101 change blocks. 
291 lines changed or deleted 507 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/