draft-ietf-babel-rfc6126bis-03.txt   draft-ietf-babel-rfc6126bis-04.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 July 3, 2017 Obsoletes: 6126,7557 (if approved) D. Schinazi
Expires: January 4, 2018 Intended status: Standards Track Apple Inc.
Expires: May 2, 2018 October 29, 2017
The Babel Routing Protocol The Babel Routing Protocol
draft-ietf-babel-rfc6126bis-03 draft-ietf-babel-rfc6126bis-04
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 33
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 January 4, 2018. This Internet-Draft will expire on May 2, 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 23 skipping to change at page 2, line 23
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 . . . . . . . . . . . . . . . . . 7 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 7
2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8
2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10 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 . . . . . . . . . . . . . . . . . . . . . 12 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. Acknowledgments and acknowledgment requests . . . . . . . 16
3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17
3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 19 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 20
3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24
3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 24 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25
3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 27 3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 27
4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 30 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 31
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 31 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32
4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 32 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33
4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 33 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 33
4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 33 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 34
4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 34 4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 35
4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 34 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 35
4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 45 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 46
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 47
6. Security Considerations . . . . . . . . . . . . . . . . . . . 46 6. Security Considerations . . . . . . . . . . . . . . . . . . . 48
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 46 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 48
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 46 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 48
8.1. Normative References . . . . . . . . . . . . . . . . . . 46 8.1. Normative References . . . . . . . . . . . . . . . . . . 49
8.2. Informative References . . . . . . . . . . . . . . . . . 47 8.2. Informative References . . . . . . . . . . . . . . . . . 49
Appendix A. Cost and Metric Computation . . . . . . . . . . . . 47 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 50
A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 48 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 50
A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 49 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 51
A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 50 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 52
A.4. Properties of Multicast and Unicast Hellos . . . . . . . 51 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 53
Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 51 Appendix C. Considerations for protocol extensions . . . . . . . 54
Appendix C. Considerations for protocol extensions . . . . . . . 52 Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 55
Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 53 Appendix E. Software Availability . . . . . . . . . . . . . . . 56
Appendix E. Software Availability . . . . . . . . . . . . . . . 54 Appendix F. Changes from previous versions . . . . . . . . . . . 56
Appendix F. Changes from previous versions . . . . . . . . . . . 54 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 56
F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 54 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 57
F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 55 F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 57
F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 55 F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 57
F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 55 F.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 58
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 56 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 58
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 3, line 38 skipping to change at page 3, line 38
packet exchanges at all. Babel then slowly converges, in a time on packet exchanges at all. Babel then slowly converges, in a time on
the scale of minutes, to an optimal configuration. This is achieved the scale of minutes, to an optimal configuration. This is achieved
by using sequenced routes, a technique pioneered by Destination- by using sequenced routes, a technique pioneered by Destination-
Sequenced Distance-Vector routing [DSDV]. Sequenced Distance-Vector routing [DSDV].
More precisely, Babel has the following properties: More precisely, Babel has the following properties:
o when every prefix is originated by at most one router, Babel never o when every prefix is originated by at most one router, Babel never
suffers from routing loops; suffers from routing loops;
o when a prefix is originated by multiple routers, Babel may o when a single prefix is originated by multiple routers, Babel may
occasionally create a transient routing loop for this particular occasionally create a transient routing loop for this particular
prefix; this loop disappears in a time proportional to its prefix; this loop disappears in a time proportional to its
diameter, and never again (up to an arbitrary garbage-collection diameter, and never again (up to an arbitrary garbage-collection
(GC) time) will the routers involved participate in a routing loop (GC) time) will the routers involved participate in a routing loop
for the same prefix; for the same prefix;
o assuming reasonable packet loss rates, any routing black-holes o assuming bounded packet loss rates, any routing black-holes that
that may appear after a mobility event are corrected in a time at may appear after a mobility event are corrected in a time at most
most proportional to the network's diameter. proportional to the network's diameter.
Babel has provisions for link quality estimation and for fairly Babel has provisions for link quality estimation and for fairly
arbitrary metrics. When configured suitably, Babel can implement arbitrary metrics. When configured suitably, Babel can implement
shortest-path routing, or it may use a metric based, for example, on shortest-path routing, or it may use a metric based, for example, on
measured packet loss. measured packet loss.
Babel nodes will successfully establish an association even when they Babel nodes will successfully establish an association even when they
are configured with different parameters. For example, a mobile node are configured with different parameters. For example, a mobile node
that is low on battery may choose to use larger time constants (hello that is low on battery may choose to use larger time constants (hello
and update intervals, etc.) than a node that has access to wall and update intervals, etc.) than a node that has access to wall
power. Conversely, a node that detects high levels of mobility may power. Conversely, a node that detects high levels of mobility may
choose to use smaller time constants. The ability to build such choose to use smaller time constants. The ability to build such
heterogeneous networks makes Babel particularly adapted to the heterogeneous networks makes Babel particularly adapted to the
wireless environment. unmanaged and wireless environment.
Finally, Babel is a hybrid routing protocol, in the sense that it can Finally, Babel is a hybrid routing protocol, in the sense that it can
carry routes for multiple network-layer protocols (IPv4 and IPv6), carry routes for multiple network-layer protocols (IPv4 and IPv6),
whichever protocol the Babel packets are themselves being carried whichever protocol the Babel packets are themselves being carried
over. over.
1.2. Limitations 1.2. Limitations
Babel has two limitations that make it unsuitable for use in some Babel has two limitations that make it unsuitable for use in some
environments. First, Babel relies on periodic routing table updates environments. First, Babel relies on periodic routing table updates
rather than using a reliable transport; hence, in large, stable rather than using a reliable transport; hence, in large, stable
networks it generates more traffic than protocols that only send networks it generates more traffic than protocols that only send
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, unless the optional algorithm described in Section 3.5.5 is
(Section 3.5.5). While this hold time does not apply to the exact implemented, Babel does impose a hold time when a prefix is
prefix being retracted, and hence does not prevent fast reconvergence retracted. While this hold time does not apply to the exact prefix
should it become available again, it does apply to any shorter prefix being retracted, and hence does not prevent fast reconvergence should
that covers it. Hence, if a previously deaggregated prefix becomes it become available again, it does apply to any shorter prefix that
aggregated, it will be unreachable for a few hundred milliseconds up covers it. This may make those implementations of Babel that do not
to a few minutes, depending on the implementation. This may make implement the optional algorithm described in Section 3.5.5
some implementations of Babel unsuitable for use in networks that unsuitable for use in networks that implement automatic prefix
implement automatic prefix aggregation. aggregation.
1.3. Specification of Requirements 1.3. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "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 loop-avoiding distance vector protocol: it is based on the
the Bellman-Ford protocol, just like the venerable RIP [RIP], but Bellman-Ford protocol, just like the venerable RIP [RIP], but
includes a number of refinements that either prevent loop formation includes a number of refinements that either prevent loop formation
altogether, or ensure that a loop disappears in a timely manner and altogether, or ensure that a loop disappears in a timely manner and
doesn't form again. doesn't form again.
Conceptually, Bellman-Ford is executed in parallel for every source Conceptually, Bellman-Ford is executed in parallel for every source
of routing information (destination of data traffic). In the of routing information (destination of data traffic). In the
following discussion, we fix a source S; the reader will recall that following discussion, we fix a source S; the reader will recall that
the same algorithm is executed for all sources. the same algorithm is executed for all sources.
2.1. Costs, Metrics and Neighbourship 2.1. Costs, Metrics and Neighbourship
As many routing algorithms, Babel computes costs of links between any As many routing algorithms, Babel computes costs of links between any
two neighbouring nodes, abstract values attached to the edges between two neighbouring nodes, abstract values attached to the edges between
two nodes. We write C(A, B) for the cost of the edge from node A to two nodes. We write C(A, B) for the cost of the edge from node A to
node B. node B.
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
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 sends 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
skipping to change at page 6, line 21 skipping to change at page 6, line 21
the topology is detected, in addition to the regular, scheduled the topology is detected, in addition to the regular, scheduled
updates. Additionally, a node may maintain a number of alternate updates. Additionally, a node may maintain a number of alternate
routes, which are being advertised by neighbours other than its routes, which are being advertised by neighbours other than its
selected neighbour, and which can be used immediately if the selected selected neighbour, and which can be used immediately if the selected
route were to fail. route were to fail.
2.3. Transient Loops in Bellman-Ford 2.3. Transient Loops in Bellman-Ford
It is well known that a naive application of Bellman-Ford to It is well known that a naive application of Bellman-Ford to
distributed routing can cause transient loops after a topology distributed routing can cause transient loops after a topology
change. Consider for example the following diagram: change. Consider for example the following topology:
B B
1 /| 1 /|
1 / | 1 / |
S --- A |1 S --- A |1
\ | \ |
1 \| 1 \|
C C
After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.
skipping to change at page 7, line 14 skipping to change at page 7, line 14
2.4. Feasibility Conditions 2.4. Feasibility Conditions
Bellman-Ford is a very robust algorithm: its convergence properties Bellman-Ford is a very robust algorithm: its convergence properties
are preserved when routers delay route acquisition or when they are preserved when routers delay route acquisition or when they
discard some updates. Babel routers discard received route discard some updates. Babel routers discard received route
announcements unless they can prove that accepting them cannot announcements unless they can prove that accepting them cannot
possibly cause a routing loop. possibly cause a routing loop.
More formally, we define a condition over route announcements, known More formally, we define a condition over route announcements, known
as the feasibility condition, that guarantees the absence of routing as the "feasibility condition", that guarantees the absence of
loops whenever all routers ignore route updates that do not satisfy routing loops whenever all routers ignore route updates that do not
the feasibility condition. In effect, this makes Bellman-Ford into a satisfy the feasibility condition. In effect, this makes Bellman-
family of routing algorithms, parameterised by the feasibility Ford into a family of routing algorithms, parameterised by the
condition. feasibility condition.
Many different feasibility conditions are possible. For example, BGP Many different feasibility conditions are possible. For example, BGP
can be modelled as being a distance-vector protocol with a (rather can be modelled as being a distance-vector protocol with a (rather
drastic) feasibility condition: a routing update is only accepted drastic) feasibility condition: a routing update is only accepted
when the receiving node's AS number is not included in the update's when the receiving node's AS number is not included in the update's
AS-Path attribute (note that BGP's feasibility condition does not AS-Path attribute (note that BGP's feasibility condition does not
ensure the absence of transitory "micro-loops" during reconvergence). ensure the absence of transient "micro-loops" during reconvergence).
Another simple feasibility condition, used in Destination-Sequenced Another simple feasibility condition, used in the Destination-
Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the
Distance Vector (AODV) routing, stems from the following observation: Ad hoc On-Demand Distance Vector (AODV) protocol, stems from the
a routing loop can only arise after a router has switched to a route following observation: a routing loop can only arise after a router
with a larger metric than the route that it had previously selected. has switched to a route with a larger metric than the route that it
Hence, one could decide that a route is feasible only when its metric had previously selected. Hence, one could decide that a route is
at the local node would be no larger than the metric of the currently feasible only when its metric at the local node would be no larger
selected route, i.e., an announcement carrying a metric D(B) is than the metric of the currently selected route, i.e., an
accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this announcement carrying a metric D(B) is accepted by A when C(A, B) +
constraint, then the metric at every router is nonincreasing, and the D(B) <= D(A). If all routers obey this constraint, then the metric
following invariant is always preserved: if A has selected B as its at every router is nonincreasing, and the following invariant is
successor, then D(B) < D(A), which implies that the forwarding graph always preserved: if A has selected B as its successor, then D(B) <
is loop-free. D(A), which implies that the forwarding graph is loop-free.
Babel uses a slightly more refined feasibility condition, used in Babel uses a slightly more refined feasibility condition, derived
EIGRP [DUAL]. Given a router A, define the feasibility distance of from EIGRP [DUAL]. Given a router A, define the feasibility distance
A, written FD(A), as the smallest metric that A has ever advertised of A, written FD(A), as the smallest metric that A has ever
for S to any of its neighbours. An update sent by a neighbour B of A advertised for S to any of its neighbours. An update sent by a
is feasible when the metric D(B) advertised by B is strictly smaller neighbour B of A is feasible when the metric D(B) advertised by B is
than A's feasibility distance, i.e., when D(B) < FD(A). strictly smaller than A's feasibility distance, i.e., when D(B) <
FD(A).
It is easy to see that this latter condition is no more restrictive It is easy to see that this latter condition is no more restrictive
than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility;
then D(A) is nonincreasing, hence at all times D(A) <= FD(A). then D(A) is nonincreasing, hence at all times D(A) <= FD(A).
Suppose now that A receives a DSDV-feasible update that advertises a Suppose now that A receives a DSDV-feasible update that advertises a
metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <=
D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A).
To see that it is strictly less restrictive, consider the following To see that it is strictly less restrictive, consider the following
diagram, where A has selected the route through B, and D(A) = FD(A) = diagram, where A has selected the route through B, and D(A) = FD(A) =
skipping to change at page 9, line 6 skipping to change at page 9, line 6
A A
| |
| FD(A) = 1 | FD(A) = 1
S |1 S |1
\ | D(B) = 2 \ | D(B) = 2
2 \| FD(B) = 2 2 \| FD(B) = 2
B B
The only route available from A to S, the one that goes through B, is The only route available from A to S, the one that goes through B, is
not feasible: A suffers from a spurious starvation. not feasible: A suffers from spurious starvation. At this point, the
whole network must be rebooted in order to solve the starvation; this
At this point, the whole network must be rebooted in order to solve is essentially what EIGRP does when it performs a global
the starvation; this is essentially what EIGRP does when it performs synchronisation of all the routers in the network with the source
a global synchronisation of all the routers in the network with the (the "active" phase of EIGRP).
source (the "active" phase of EIGRP).
Babel reacts to starvation in a less drastic manner, by using Babel reacts to starvation in a less drastic manner, by using
sequenced routes, a technique introduced by DSDV and adopted by AODV. sequenced routes, a technique introduced by DSDV and adopted by AODV.
In addition to a metric, every route carries a sequence number, a In addition to a metric, every route carries a sequence number, a
nondecreasing integer that is propagated unchanged through the nondecreasing integer that is propagated unchanged through the
network and is only ever incremented by the source; a pair (s, m), network and is only ever incremented by the source; a pair (s, m),
where s is a sequence number and m a metric, is called a distance. where s is a sequence number and m a metric, is called a distance.
A received update is feasible when either it is more recent than the A received update is feasible when either it is more recent than the
feasibility distance maintained by the receiving node, or it is feasibility distance maintained by the receiving node, or it is
skipping to change at page 9, line 51 skipping to change at page 9, line 50
| FD(A) = (137, 1) | FD(A) = (137, 1)
S |1 S |1
\ | D(B) = (138, 2) \ | D(B) = (138, 2)
2 \| FD(B) = (138, 2) 2 \| FD(B) = (138, 2)
B B
at which point the route through B becomes feasible again. at which point the route through B becomes feasible again.
Note that while sequence numbers are used for determining Note that while sequence numbers are used for determining
feasibility, they are not necessarily used in route selection: a node feasibility, they are not necessarily used in route selection: a node
will normally ignore the sequence number when selecting a route will normally ignore the sequence number when selecting the best
(Section 3.6). route to a given destination (Section 3.6).
2.6. Requests 2.6. Requests
In DSDV, the sequence number of a source is increased periodically. In DSDV, the sequence number of a source is increased periodically.
A route becomes feasible again after the source increases its A route becomes feasible again after the source increases its
sequence number, and the new sequence number is propagated through sequence number, and the new sequence number is propagated through
the network, which may, in general, require a significant amount of the network, which may, in general, require a significant amount of
time. time.
Babel takes a different approach. When a node detects that it is Babel takes a different approach. When a node detects that it is
skipping to change at page 10, line 39 skipping to change at page 10, line 39
Since requests are forwarded with no regard to the feasibility Since requests are forwarded with no regard to the feasibility
condition, they may, in general, be caught in a forwarding loop; this condition, they may, in general, be caught in a forwarding loop; this
is avoided by having nodes perform duplicate detection for the is avoided by having nodes perform duplicate detection for the
requests that they forward. requests that they forward.
2.7. Multiple Routers 2.7. Multiple Routers
The above discussion assumes that every prefix is originated by a The above discussion assumes that every prefix is originated by a
single router. In real networks, however, it is often necessary to single router. In real networks, however, it is often necessary to
have a single prefix originated by multiple routers; for example, the have a single prefix originated by multiple routers: for example, the
default route will be originated by all of the edge routers of a default route will be originated by all of the edge routers of a
routing domain. routing domain.
Since synchronising sequence numbers between distinct routers is Since synchronising sequence numbers between distinct routers is
problematic, Babel treats routes for the same prefix as distinct problematic, Babel treats routes for the same prefix as distinct
entities when they are originated by different routers: every route entities when they are originated by different routers: every route
announcement carries the router-id of its originating router, and announcement carries the router-id of its originating router, and
feasibility distances are not maintained per prefix, but per source, feasibility distances are not maintained per prefix, but per source,
where a source is a pair of a router-id and a prefix. In effect, where a source is a pair of a router-id and a prefix. In effect,
Babel guarantees loop-freedom for the forwarding graph to every Babel guarantees loop-freedom for the forwarding graph to every
source; since the union of multiple acyclic graphs is not in general source; since the union of multiple acyclic graphs is not in general
acyclic, Babel does not in general guarantee loop-freedom when a acyclic, Babel does not in general guarantee loop-freedom when a
prefix is originated by multiple routers, but any loops will be prefix is originated by multiple routers, but any loops will be
broken in a time at most proportional to the diameter of the loop -- broken in a time at most proportional to the diameter of the loop --
as soon as an update has "gone around" the routing loop. as soon as an update has "gone around" the routing loop.
Consider for example the following diagram, where A has selected the Consider for example the following topology, where A has selected the
default route through S, and B has selected the one through S': default route through S, and B has selected the one through S':
1 1 1 1 1 1
::/0 -- S --- A --- B --- S' -- ::/0 ::/0 -- S --- A --- B --- S' -- ::/0
Suppose that both default routes fail at the same time; then nothing Suppose that both default routes fail at the same time; then nothing
prevents A from switching to B, and B simultaneously switching to A. prevents A from switching to B, and B simultaneously switching to A.
However, as soon as A has successfully advertised the new route to B, However, as soon as A has successfully advertised the new route to B,
the route through A will become unfeasible for B. Conversely, as the route through A will become unfeasible for B. Conversely, as
soon as B will have advertised the route through A, the route through soon as B will have advertised the route through A, the route through
B will become unfeasible for A. B will become unfeasible for A.
In effect, the routing loop disappears at the latest when routing In effect, the routing loop disappears at the latest when routing
information has gone around the loop. Since this process can be information has gone around the loop. Since this process can be
delayed by lost packets, Babel makes certain efforts to ensure that delayed by lost packets, Babel makes certain efforts to ensure that
updates are sent reliably after a router-id change. updates are sent reliably after a router-id change Section 3.7.2.
Additionally, after the routers have advertised the two routes, both Additionally, after the routers have advertised the two routes, both
sources will be in their source tables, which will prevent them from sources will be in their source tables, which will prevent them from
ever again participating in a routing loop involving routes from S ever again participating in a routing loop involving routes from S
and S' (up to the source GC time, which, available memory permitting, and S' (up to the source GC time, which, available memory permitting,
can be set to arbitrarily large values). can be set to arbitrarily large values).
2.8. Overlapping Prefixes 2.8. Overlapping Prefixes
In the above discussion, we have assumed that all prefixes are In the above discussion, we have assumed that all prefixes are
skipping to change at page 11, line 50 skipping to change at page 11, line 50
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. B avoids until A learns of B's retraction of the direct route to C. B avoids
this pitfall by installing an "unreachable" route after a route is this pitfall by installing an "unreachable" route after a route is
retracted; this route is maintained until it can be guaranteed that retracted; this route is maintained until it can be guaranteed that
the former route has been retracted by all of B's neighbours. the former route has been retracted by all of B's neighbours
(Section 3.5.5).
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 For example, routers-ids could be assigned randomly, or they could
format [ADDRARCH]. (As a matter of fact, the protocol encoding is derived from a link-layer address. (The protocol encoding is
slightly more compact when router-ids are assigned in the same manner slightly more compact when router-ids are assigned in the same manner
as the IPv6 layer assigns host IDs.) 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 or to a (link-local) unicast known (link-local) multicast address or to a (link-local) unicast
address. In normal operation, a Babel speaker sends both multicast address. In normal operation, a Babel speaker 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 acknowledgments, 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 is a unicast or
multicast address. Hence, a Babel speaker does not need to determine a multicast address. Hence, a Babel speaker does not need to
the destination address of a packet that it receives in order to determine the destination address of a packet that it receives in
interpret it. order to interpret it.
A moderate amount of jitter may be applied to packets sent by a Babel A moderate amount of jitter may be applied to packets sent by a Babel
speaker: outgoing TLVs are buffered and SHOULD be sent with a 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. Acknowledgment 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
in a timely manner. The particular class of request and update TLVs in a timely manner. The particular class of request and update TLVs
specified in Section 3.8.2 SHOULD be sent in a timely manner. specified in Section 3.8.2 SHOULD be sent in a timely manner.
3.2. Data Structures 3.2. Data Structures
Every Babel speaker maintains a number of data structures. All of In this section, we give a description of the data structures that
these data structures consist of familiar data types -- integers, IP every Babel speaker maintains. This description is conceptual: a
addresses, etc. -- with the exception of sequence numbers. Babel speaker may use different data structures as long as the
resulting protocol is the same as the one described in this document.
For example, rather than maintaining a single table containing both
selected and unselected (fallback) routes, as described in
Section 3.2.6 belong, an actual implementation would probably use two
tables, one with selected routes and one with fallback routes.
3.2.1. Sequence number arithmetic 3.2.1. Sequence number arithmetic
Sequence numbers (seqnos) appear in a number of Babel data Sequence numbers (seqnos) appear in a number of Babel data
structures, and they are interpreted as integers modulo 2^16. For structures, and they are interpreted as integers modulo 2^16. For
the purposes of this document, arithmetic on serial numbers is the purposes of this document, arithmetic on sequence numbers is
defined as follows. defined as follows.
Given a seqno s and an integer n, the sum of s and n is defined by Given a seqno s and an integer n, the sum of s and n is defined by
s + n (modulo 2^16) = (s + n) MOD 2^16 s + n (modulo 2^16) = (s + n) MOD 2^16
or, equivalently, or, equivalently,
s + n (modulo 2^16) = (s + n) AND 65535 s + n (modulo 2^16) = (s + n) AND 65535
skipping to change at page 15, line 8 skipping to change at page 15, line 12
There are three timers associated with each neighbour entry -- the There are three timers associated with each neighbour entry -- the
multicast hello timer, which is initialised from the interval value multicast hello timer, which is initialised from the interval value
carried by scheduled Multicast Hello TLVs, the unicast hello timer, carried by scheduled Multicast Hello TLVs, the unicast hello timer,
which is initialised from the interval value carried by scheduled which is initialised from the interval value carried by scheduled
Unicast Hello TLVs, and the IHU timer, which is initialised to a Unicast Hello TLVs, and the IHU timer, which is initialised to a
small multiple of the interval carried in IHU TLVs. 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 situation that
situation when wireless nodes with multiple radios are involved. can notably arise 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
indexed by triples of the form (prefix, plen, router-id), and every indexed by triples of the form (prefix, plen, router-id), and every
source table entry contains the following data: source table entry contains the following data:
o the prefix (prefix, plen), where plen is the prefix length, that o the prefix (prefix, plen), where plen is the prefix length, that
this entry applies to; this entry applies to;
skipping to change at page 15, line 45 skipping to change at page 16, line 4
advertised; advertised;
o the neighbour that advertised this route; o the neighbour that advertised this route;
o the metric with which this route was advertised by the neighbour, o the metric with which this route was advertised by the neighbour,
or FFFF hexadecimal (infinity) for a recently retracted route; or FFFF hexadecimal (infinity) for a recently retracted route;
o the sequence number with which this route was advertised; o the sequence number with which this route was advertised;
o the next-hop address of this route; o the next-hop address of this route;
o a boolean flag indicating whether this route is selected, i.e., o a boolean flag indicating whether this route is selected, i.e.,
whether it is currently being used for forwarding and is being whether it is currently being used for forwarding and is being
advertised. advertised.
There is one timer associated with each route table entry -- the There is one timer associated with each route table entry -- the
route expiry timer. It is initialised and reset as specified in route expiry timer. It is initialised and reset as specified in
Section 3.5.4. Section 3.5.4.
Of course, the data structure described above is conceptual: actual
implementations will likely use a different data structure, for
example a table of installed routes and a set of redundant ones, or
some more complicated data structure.
Note that there are two distinct (seqno, metric) pairs associated to Note that there are two distinct (seqno, metric) pairs associated to
each route: the route's distance, which is stored in the route table, each route: the route's distance, which is stored in the route table,
and the feasibility distance, stored in the source table and shared and the feasibility distance, stored in the source table and shared
between all routes with the same source. between all routes with the same source.
3.2.7. The Table of Pending Seqno Requests 3.2.7. The Table of Pending Seqno Requests
The table of pending seqno requests contains a list of seqno requests The table of pending seqno requests contains a list of seqno requests
that the local node has sent (either because they have been that the local node has sent (either because they have been
originated locally, or because they were forwarded) and to which no originated locally, or because they were forwarded) and to which no
reply has been received yet. This table is indexed by prefixes and reply has been received yet. This table is indexed by triples of the
router-ids, and every entry in this table contains the following form (prefix, plen, router-id), and every entry in this table
data: 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 seqno request; it There is one timer associated with each pending seqno request; it
governs both the resending of requests and their expiry. governs both the resending of requests and their expiry.
3.3. Acknowledged Packets 3.3. Acknowledgments and acknowledgment requests
A Babel speaker may request that any neighbour receiving a given A Babel speaker may request that a neighbour receiving a given packet
packet reply with an explicit acknowledgement within a given time. reply with an explicit acknowledgment within a given time. While the
While the use of acknowledgement requests is optional, every Babel use of acknowledgment requests is optional, every Babel speaker MUST
speaker MUST be able to reply to such a request. be able to reply to such a request.
An acknowledgement MUST be sent to a unicast destination. On the An acknowledgment MUST be sent to a unicast destination. On the
other hand, acknowledgement requests may be sent to either unicast or other hand, acknowledgment requests may be sent to either unicast or
multicast destinations, in which case they request an acknowledgement multicast destinations, in which case they request an acknowledgment
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 acknowledgments is a matter of local policy; the
simplest strategy is to never request acknowledgements and to rely on simplest strategy is to never request acknowledgments and to rely on
periodic updates to ensure that any reachable routes are eventually periodic updates to ensure that any reachable routes are eventually
propagated throughout the routing domain. For increased efficiency, propagated throughout the routing domain. In order to improve
acknowledged packets MAY be used in order to send urgent updates convergence speed and reduce the amount of control traffic,
(Section 3.7.2) when the number of neighbours on a given interface is acknowledgment requests MAY be used in order to reliably send urgent
small. Since Babel is designed to deal gracefully with packet loss updates (Section 3.7.2) and retractions (Section 3.5.5), especially
on unreliable media, sending all packets with acknowledgement when the number of neighbours on a given interface is small. Since
requests is not necessary, and NOT RECOMMENDED, as the Babel is designed to deal gracefully with packet loss on unreliable
acknowledgements cause additional traffic and may force additional media, sending all packets with acknowledgment requests is not
Address Resolution Protocol (ARP) or Neighbour Discovery exchanges. necessary, and NOT RECOMMENDED, as the acknowledgments cause
additional traffic and may force additional Address Resolution
Protocol (ARP) or Neighbour Discovery (ND) exchanges.
3.4. Neighbour Acquisition 3.4. Neighbour Acquisition
Neighbour acquisition is the process by which a Babel node discovers Neighbour acquisition is the process by which a Babel node discovers
the set of neighbours heard over each of its interfaces and the set of neighbours heard over each of its interfaces and
ascertains bidirectional reachability. On unreliable media, ascertains bidirectional reachability. On unreliable media,
neighbour acquisition additionally provides some statistics that may neighbour acquisition additionally provides some statistics that may
be useful for link quality computation. be useful for link quality computation.
Before it can exchange routing information with a neighbour, a Babel Before it can exchange routing information with a neighbour, a Babel
skipping to change at page 17, line 32 skipping to change at page 17, line 37
creating an entry when a Hello TLV is parsed. Similarly, in order to creating an entry when a Hello TLV is parsed. Similarly, in order to
conserve system resources, an implementation SHOULD discard an entry conserve system resources, an implementation SHOULD discard an entry
when it has been unused for long enough; suitable strategies include when it has been unused for long enough; suitable strategies include
dropping the neighbour after a timeout, and dropping a neighbour when dropping the neighbour after a timeout, and dropping a neighbour when
the associated Hello histories become empty (see Appendix A.2). the associated Hello histories become empty (see Appendix A.2).
3.4.1. Reverse Reachability Detection 3.4.1. Reverse Reachability Detection
Every Babel node sends Hello TLVs to its neighbours to indicate that Every Babel node sends Hello TLVs to its neighbours to indicate that
it is alive, at regular or irregular intervals. Each Hello TLV it is alive, at regular or irregular intervals. Each Hello TLV
carries an increasing (modulo 2^16) sequence number and the time carries an increasing (modulo 2^16) sequence number and an upper
interval until the next Hello of the same type (see below). If the bound on the time interval until the next Hello of the same type (see
time interval is set to 0, then the Hello TLV does not establish a below). If the time interval is set to 0, then the Hello TLV does
new promise -- the timeout carried by the previous Hello of the same not establish a new promise: the deadline carried by the previous
type still applies to the next Hello. We say that a Hello is Hello of the same type still applies to the next Hello (if the most
scheduled if it has a non-zero interval, and unscheduled otherwise. recent scheduled Hello of the right kind was received at time t0 and
carried interval i, then the previous promise of sending another
Hello before time t0 + i still holds). We say that a Hello is
"scheduled" if it carries a non-zero interval, and "unscheduled"
otherwise.
There are two kinds of Hellos: Multicast Hellos, which use a per- There are two kinds of Hellos: Multicast Hellos, which use a per-
interface Hello counter, and Unicast Hellos, which use a per- interface Hello counter, and Unicast Hellos, which use a per-
neighbour counter. A Multicast Hellos with a given seqno MUST be neighbour counter. A Multicast Hello with a given seqno MUST be sent
sent to all neighbours on a given interface, either by sending it to to all neighbours on a given interface, either by sending it to a
a multicast address or by sending it to one unicast address per multicast address or by sending it to one unicast address per
neighbour. A Unicast Hello with given seqno should normally be sent neighbour (hence, the term "Multicast Hello" is a slight misnomer).
to just one neighbour (over unicast), since the sequence numbers of A Unicast Hello carrying a given seqno should normally be sent to
different neighbours are not necessarily synchronised. just one neighbour (over unicast), since the sequence numbers of
different neighbours are not in general synchronised.
Multicast Hellos sent over multicast can be used for node discovery; Multicast Hellos sent over multicast can be used for neighbour
hence, a node SHOULD send periodic (scheduled) Multicast Hellos. A discovery; hence, a node SHOULD send periodic (scheduled) Multicast
node MAY send Unicast Hellos or unscheduled Hellos of either kind for Hellos unless neighbour discovery is performed by means outside of
any reason, such as reducing the amount of multicast traffic or the Babel protocol. A node MAY send Unicast Hellos or unscheduled
improving reliability on link technologies with poor support for Hellos of either kind for any reason, such as reducing the amount of
link-layer multicast. 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 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 its scheduled Hello interval. The Hello interval MAY be decreased at
any time; it MAY be increased immediately before sending a Hello TLV, any time; it MAY be increased immediately before sending a Hello TLV,
but SHOULD NOT be increased at other times. (Equivalently, a node but SHOULD NOT be increased at other times. (Equivalently, a node
SHOULD send an extra scheduled Hello immediately after increasing its SHOULD send a scheduled Hello immediately after increasing its Hello
Hello interval.) 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 useful maintain some sort of history of recently received Hellos. An
algorithm is described in Appendix A.1. example of a suitable 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 MAY be sent to a multicast address in order to avoid an unicast, they MAY be sent to a multicast address in order to avoid an
ARP or Neighbour Discovery exchange and to aggregate multiple IHUs in ARP or Neighbour Discovery exchange and to aggregate multiple IHUs
a single packet. into 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, but SHOULD NOT increase it at any other time. sending an IHU, but SHOULD NOT increase it at any other time.
(Equivalently, a node SHOULD send an extra IHU immediately after (Equivalently, a node SHOULD send an extra IHU immediately after
increasing its Hello interval.) 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 sets the value of the
the sending neighbour's txcost (transmission cost), from its txcost (transmission cost) maintained in the neighbour table to the
perspective, to the value contained in the IHU, and resets this value contained in the IHU, and resets the IHU timer associated to
neighbour's IHU timer to a small multiple of the value received in this neighbour to a small multiple of the interval value received in
the IHU. the IHU. When a neighbour's IHU timer expires, the neighbour's
txcost is set to infinity.
When a neighbour's IHU timer expires, its txcost is set to infinity.
After updating a neighbour's txcost, the receiving node recomputes After updating a neighbour's txcost, the receiving node recomputes
the neighbour's cost (Section 3.4.3) and runs the route selection the neighbour's cost (Section 3.4.3) and runs the route selection
procedure (Section 3.6). procedure (Section 3.6).
3.4.3. Cost Computation 3.4.3. Cost Computation
A neighbourship association's link cost is computed from the values A neighbourship association's link cost is computed from the values
maintained in the neighbour table -- namely, the statistics kept in maintained in the neighbour table: the statistics kept in the
the neighbour table about the reception of Hellos, and the txcost neighbour table about the reception of Hellos, and the txcost
computed from received IHU packets. computed from received IHU packets.
For every neighbour, a Babel node computes a value known as this For every neighbour, a Babel node computes a value known as this
neighbour's rxcost. This value is usually derived from the Hello neighbour's rxcost. This value is usually derived from the Hello
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.
Since nodes do not necessarily send periodic Unicast Hellos but do
usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD
use an algorithm that yields a finite rxcost when only Multicast
Hellos are received, unless interoperability with nodes that only
send Multicast Hellos is not required.
How the txcost and rxcost are combined in order to compute a link's How the txcost and rxcost are combined in order to compute a link's
cost is a matter of local policy; as far as Babel's correctness is cost is a matter of local policy; as far as Babel's correctness is
concerned, only the following conditions MUST be satisfied: concerned, only the following conditions MUST be satisfied:
o the cost is strictly positive; o the cost is strictly positive;
o if no Hello TLVs of either kind were received recently, then the o if no Hello TLVs of either kind were received recently, then the
cost is infinite; cost is infinite;
o if the txcost is infinite, then the cost is infinite. o if the txcost is infinite, then the cost is infinite.
skipping to change at page 19, line 50 skipping to change at page 20, line 17
Conceptually, a Babel update is a quintuple (prefix, plen, router-id, Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
seqno, metric), where (prefix, plen) is the prefix for which a route seqno, metric), where (prefix, plen) is the prefix for which a route
is being advertised, router-id is the router-id of the router is being advertised, router-id is the router-id of the router
originating this update, seqno is a nondecreasing (modulo 2^16) originating this update, seqno is a nondecreasing (modulo 2^16)
integer that carries the originating router seqno, and metric is the integer that carries the originating router seqno, and metric is the
announced metric. announced metric.
Before being accepted, an update is checked against the feasibility Before being accepted, an update is checked against the feasibility
condition (Section 3.5.1), which ensures that the route does not condition (Section 3.5.1), which ensures that the route does not
create a routing loop. If the feasibility condition is not create a routing loop. If the feasibility condition is not
satisfied, the update is either ignored or treated as a retraction, satisfied, the update is either ignored or prevents the route from
depending on some other conditions (Section 3.5.4). If the being selected, as described in Section 3.5.4. If the feasibility
feasibility condition is satisfied, then the update cannot possibly condition is satisfied, then the update cannot possibly cause a
cause a routing loop, and the update is accepted. routing loop.
3.5.1. The Feasibility Condition 3.5.1. The Feasibility Condition
The feasibility condition is applied to all received updates. The The feasibility condition is applied to all received updates. The
feasibility condition compares the metric in the received update with feasibility condition compares the metric in the received update with
the metrics of the updates previously sent by the receiving node; the metrics of the updates previously sent by the receiving node;
updates that fail the feasibility condition, and therefore have updates that fail the feasibility condition, and therefore have
metrics large enough to cause a routing loop, are either discarded or metrics large enough to cause a routing loop, are either ignored or
prevent the resulting route from being selected. prevent the resulting route from being selected.
A feasibility distance is a pair (seqno, metric), where seqno is an A feasibility distance is a pair (seqno, metric), where seqno is an
integer modulo 2^16 and metric is a positive integer. Feasibility integer modulo 2^16 and metric is a positive integer. Feasibility
distances are compared lexicographically, with the first component distances are compared lexicographically, with the first component
inverted: we say that a distance (seqno, metric) is strictly better inverted: we say that a distance (seqno, metric) is strictly better
than a distance (seqno', metric'), written than a distance (seqno', metric'), written
(seqno, metric) < (seqno', metric') (seqno, metric) < (seqno', metric')
when when
seqno > seqno' or (seqno = seqno' and metric < metric') seqno > seqno' or (seqno = seqno' and metric < metric')
where sequence numbers are compared modulo 2^16. where sequence numbers are compared modulo 2^16.
Given a source (prefix, plen, router-id), a node's feasibility Given a source (prefix, plen, router-id), a node's feasibility
distance for this source is the minimum, according to the ordering distance for this source is the minimum, according to the ordering
defined above, of the distances of all the finite updates ever sent defined above, of the distances of all the finite updates ever sent
by this particular node for the prefix (prefix, plen) and the given by this particular node for the prefix (prefix, plen) and the given
router-id. Feasibility distances are maintained in the source table; router-id. Feasibility distances are maintained in the source table,
the exact procedure is given in Section 3.7.3. the exact procedure is given in Section 3.7.3.
A received update is feasible when either it is a retraction (its A received update is feasible when either it is a retraction (its
metric is FFFF hexadecimal), or the advertised distance is strictly metric is FFFF hexadecimal), or the advertised distance is strictly
better, in the sense defined above, than the feasibility distance for better, in the sense defined above, than the feasibility distance for
the corresponding source. More precisely, a route advertisement the corresponding source. More precisely, a route advertisement
carrying the quintuple (prefix, plen, router-id, seqno, metric) is carrying the quintuple (prefix, plen, router-id, seqno, metric) is
feasible if one of the following conditions holds: feasible if one of the following conditions holds:
o metric is infinite; or o metric is infinite; or
o no entry exists in the source table indexed by (router-id, prefix, o no entry exists in the source table indexed by (prefix, plen,
plen); or router-id); or
o an entry (prefix, plen, router-id, seqno', metric') exists in the o an entry (prefix, plen, router-id, seqno', metric') exists in the
source table, and either source table, and either
* seqno' < seqno or * seqno' < seqno or
* seqno = seqno' and metric < metric'. * seqno = seqno' and metric < metric'.
Note that the feasibility condition considers the metric advertised Note that the feasibility condition considers the metric advertised
by the neighbour, not the route's metric; hence, a fluctuation in a by the neighbour, not the route's metric; hence, a fluctuation in a
neighbour's cost cannot render a selected route unfeasible. neighbour's cost cannot render a selected route unfeasible. Note
further that retractions (updates with infinite metric) are always
feasible, since they cannot possibly cause a routing loop.
3.5.2. Metric Computation 3.5.2. Metric Computation
A route's metric is computed from the metric advertised by the A route's metric is computed from the metric advertised by the
neighbour and the neighbour's link cost. Just like cost computation, neighbour and the neighbour's link cost. Just like cost computation,
metric computation is considered a local policy matter; as far as metric computation is considered a local policy matter; as far as
Babel is concerned, the function M(c, m) used for computing a metric Babel is concerned, the function M(c, m) used for computing a metric
from a locally computed link cost and the metric advertised by a from a locally computed link cost and the metric advertised by a
neighbour MUST only satisfy the following conditions: neighbour MUST only satisfy the following conditions:
o if c is infinite, then M(c, m) is infinite; o if c is infinite, then M(c, m) is infinite;
o M is strictly monotonic: M(c, m) > m. o M is strictly monotonic: M(c, m) > m.
Additionally, the metric SHOULD satisfy the following condition: Additionally, the metric SHOULD satisfy the following condition:
o M is isotonic: if m <= m', then M(c, m) <= M(c, m'). o M is isotonic: if m <= m', then M(c, m) <= M(c, m').
Note that while strict monotonicity is essential to the integrity of Note that while strict monotonicity is essential to the integrity of
the network (persistent routing loops may appear if it is not the network (persistent routing loops may arise if it is not
satisfied), isotonicity is not: if it is not satisfied, Babel will satisfied), isotonicity is not: if it is not satisfied, Babel will
still converge to a locally optimal routing table, but might not still converge to a loop-free configuration, but might not reach a
reach a global optimum (in fact, such a global optimum may not even global optimum (in fact, a global optimum may not even exist).
exist).
As with cost computation, not all strategies for computing route As with cost computation, not all strategies for computing route
metrics will give good results. In particular, some metrics are more metrics will give good results. In particular, some metrics are more
likely than others to lead to routing instabilities (route flapping). likely than others to lead to routing instabilities (route flapping).
In Appendix A.3, we give a number of examples of strictly monotonic, In Appendix A.3, we give a number of examples of strictly monotonic,
isotonic routing metrics that are known to work well in practice. isotonic routing metrics that are known to work well in practice.
3.5.3. Encoding of Updates 3.5.3. Encoding of Updates
In a large network, the bulk of Babel traffic consists of route In a large network, the bulk of Babel traffic consists of route
skipping to change at page 22, line 19 skipping to change at page 22, line 36
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 (prefix, plen, router-id, 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 route table entry indexed by
(neigh, prefix). (prefix, plen, neigh).
If no such entry exists: If no such entry exists:
o if the update is unfeasible, it MAY be ignored; o if the update is unfeasible, it MAY be ignored;
o if the metric is infinite (the update is a retraction of a route o if the metric is infinite (the update is a retraction of a route
we do not know about), the update is ignored; we do not know about), the update is ignored;
o otherwise, a new route table entry is created, indexed by (neigh, o otherwise, a new entry is created in the route table, indexed by
prefix), with source equal to (router-id, prefix), seqno equal to (prefix, plen, neigh), with source equal to (prefix, plen, router-
seqno and an advertised metric equal to the metric carried by the id), seqno equal to seqno and an advertised metric equal to the
update. metric carried by the update.
If such an entry exists: If such an entry exists:
o if the entry is currently selected, the update is unfeasible, and o if the entry is currently selected, the update is unfeasible, and
the router-id of the update is equal to the router-id of the the router-id of the update is equal to the router-id of the
entry, then the update MAY be silently ignored; entry, then the update MAY be ignored;
o otherwise, the entry's sequence number, advertised metric, metric, o otherwise, the entry's sequence number, advertised metric, metric,
and router-id are updated and, if the advertised metric is not and router-id are updated and, if the advertised metric is not
infinite, the route's expiry timer is reset to a small multiple of infinite, the route's expiry timer is reset to a small multiple of
the Interval value included in the update. If the update is the Interval value included in the update. If the update is
unfeasible, then the (now unfeasible) entry MUST be immediately unfeasible, then the (now unfeasible) entry MUST be immediately
unselected, and, if the update caused the router-id of the entry unselected. If the update caused the router-id of the entry to
to change, an update (possibly a retraction) MUST be sent in a change, an update (possibly a retraction) MUST be sent in a timely
timely manner (see Section 3.7.2). manner (see Section 3.7.2).
Note that the route table may contain unfeasible routes, either Note that the route table may contain unfeasible routes, either
because they were created by an unfeasible update or due to a metric because they were created by an unfeasible update or due to a metric
fluctuation. Such routes are never selected, since they are not fluctuation. Such routes are never selected, since they are not
known to be loop-free; should all the feasible routes become known to be loop-free; should all the feasible routes become
unusable, however, the unfeasible routes can be made feasible by unusable, however, the unfeasible routes can be made feasible and
sending requests along them (see Section 3.8.2). therefore possible to select 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 route 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 or When a prefix P is retracted, because all routes are unfeasible or
have an infinite metric (whether due to the expiry timer or to other have an infinite metric (whether due to the expiry timer or to other
reasons), and a shorter prefix P' that covers P is reachable, P' reasons), and a shorter prefix P' that covers P is reachable, P'
cannot in general be used for routing packets destined to P without cannot in general be used for routing packets destined to P without
running the risk of creating a routing loop (Section 2.8). running the risk of creating a routing loop (Section 2.8).
To avoid this issue, whenever a prefix P is retracted, a routing To avoid this issue, whenever a prefix P is retracted, a route table
table entry with infinite metric is inserted as described in entry with infinite metric is maintained as described in
Section 3.5.4 above. As long as this entry is maintained, packets Section 3.5.4 above. As long as this entry is maintained, packets
destined to an address within P MUST NOT be forwarded by following a destined to an address within P MUST NOT be forwarded by following a
route for a shorter prefix. This entry is removed as soon as a route for a shorter prefix. This entry is removed as soon as a
finite-metric update for prefix P is received and the resulting route finite-metric update for prefix P is received and the resulting route
selected. If no such update is forthcoming, the infinite metric selected. If no such update is forthcoming, the infinite metric
entry MUST be maintained at least until it is guaranteed that no entry SHOULD be maintained at least until it is guaranteed that no
neighbour has selected the current node as next-hop for prefix P. neighbour has selected the current node as next-hop for prefix P.
This can be achieved by either: This can be achieved by either:
o waiting until the route's expiry timer has expired (Section 3.5.4) 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) o sending a retraction with an acknowledgment request (Section 3.3)
to every neighbour that has not explicitly retracted prefix P and to every reachable neighbour that has not explicitly retracted
waiting for all acknowledgements. prefix P and waiting for all acknowledgments.
The former option is simpler and ensures that at that point, any The former option is simpler and ensures that at that point, any
routes for prefix P pointing at the current node have expired. routes for prefix P pointing at the current node have expired.
However, since the expiry time can be as high as a few minutes, doing However, since the expiry time can be as high as a few minutes, doing
that prevents automatic aggregation by creating spurious black-holes that prevents automatic aggregation by creating spurious black-holes
for aggregated routes. The latter option is RECOMMENDED as it for aggregated routes. The latter option is RECOMMENDED as it
reduces convergence time. dramatically reduces the time for which a prefix is unreachable in
the presence of aggregated routes.
3.6. Route Selection 3.6. Route Selection
Route selection is the process by which a single route for a given Route selection is the process by which a single route for a given
prefix is selected to be used for forwarding packets and to be re- prefix is selected to be used for forwarding packets and to be re-
advertised to a node's neighbours. advertised to a node's neighbours.
Babel is designed to allow flexible route selection policies. As far Babel is designed to allow flexible route selection policies. As far
as the 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:
o a route with infinite metric (a retracted route) is never o a route with infinite metric (a retracted route) is never
selected; selected;
o an unfeasible route is never selected. o an unfeasible route is never selected.
Note, however, that Babel does not naturally guarantee the stability Note, however, that Babel does not naturally guarantee the stability
of routing, and configuring conflicting route selection policies on of routing, and configuring conflicting route selection policies on
different routers may lead to persistent route oscillation. different routers may lead to persistent route oscillation.
Defining a good route selection policy for Babel is an open research Route selection is a difficult problem, since a good route selection
problem. Route selection can take into account multiple mutually policy needs to take into account multiple mutually contradictory
contradictory criteria; in roughly decreasing order of importance, criteria; in roughly decreasing order of importance, these are:
these are:
o routes with a small metric should be preferred over routes with a o routes with a small metric should be preferred to routes with a
large metric; large metric;
o switching router-ids should be avoided; o switching router-ids should be avoided;
o routes through stable neighbours should be preferred over routes o routes through stable neighbours should be preferred to routes
through unstable ones; through unstable ones;
o stable routes should be preferred over unstable ones; o stable routes should be preferred to unstable ones;
o switching next hops should be avoided. o switching next hops should be avoided.
A simple strategy is to choose the feasible route with the smallest A simple but useful strategy is to choose the feasible route with the
metric, with a small amount of hysteresis applied to avoid switching smallest metric, with a small amount of hysteresis applied to avoid
router-ids. switching router-ids too often.
After the route selection procedure is run, triggered updates After the route selection procedure is run, triggered updates
(Section 3.7.2) and requests (Section 3.8.2) are sent. (Section 3.7.2) and requests (Section 3.8.2) are sent.
3.7. Sending Updates 3.7. Sending Updates
A Babel speaker advertises to its neighbours its set of selected A Babel speaker advertises to its neighbours its set of selected
routes. Normally, this is done by sending one or more multicast routes. Normally, this is done by sending one or more multicast
packets containing Update TLVs on all of its connected interfaces; packets containing Update TLVs on all of its connected interfaces;
however, on link technologies where multicast is significantly more however, on link technologies where multicast is significantly more
expensive than unicast, a node MAY choose to send multiple copies of expensive than unicast, a node MAY choose to send multiple copies of
updates in unicast packets when the number of neighbours is small. updates in unicast packets, especially when the number of neighbours
is small.
Additionally, in order to ensure that any black-holes are reliably Additionally, in order to ensure that any black-holes are reliably
cleared in a timely manner, a Babel node sends retractions (updates cleared in a timely manner, a Babel node sends retractions (updates
with an infinite metric) for any recently retracted prefixes. with an infinite metric) for any recently retracted prefixes.
If an update is for a route injected into the Babel domain by the If an update is for a route injected into the Babel domain by the
local node (e.g., the address of a local interface, the prefix of a local node (e.g., it carries the address of a local interface, the
directly attached network, or redistributed from a different routing prefix of a directly attached network, or a prefix redistributed from
protocol), the router-id is set to the local id, the metric is set to a different routing protocol), the router-id is set to the local
some arbitrary finite value (typically 0), and the seqno is set to node's router-id, the metric is set to some arbitrary finite value
the local router's sequence number. (typically 0), and the seqno is set to the local router's sequence
number.
If an update is for a route learned from another Babel speaker, the If an update is for a route learned from another Babel speaker, the
router-id and sequence number are copied from the routing table router-id and sequence number are copied from the route table entry,
entry, and the metric is computed as specified in Section 3.5.2. and the metric is computed as specified in Section 3.5.2.
3.7.1. Periodic Updates 3.7.1. Periodic Updates
Every Babel speaker periodically advertises all of its selected Every Babel speaker periodically advertises all of its selected
routes on all of its interfaces, including any recently retracted routes on all of its interfaces, including any recently retracted
routes. Since Babel doesn't suffer from routing loops (there is no routes. Since Babel doesn't suffer from routing loops (there is no
"counting to infinity") and relies heavily on triggered updates "counting to infinity") and relies heavily on triggered updates
(Section 3.7.2), this full dump only needs to happen infrequently. (Section 3.7.2), this full dump only needs to happen infrequently.
3.7.2. Triggered Updates 3.7.2. Triggered Updates
In addition to the periodic routing updates, a Babel speaker sends In addition to periodic routing updates, a Babel speaker sends
unscheduled, or triggered, updates in order to inform its neighbours unscheduled, or triggered, updates in order to inform its neighbours
of a significant change in the network topology. of a significant change in the network topology.
A change of router-id for the selected route to a given prefix may be A change of router-id for the selected route to a given prefix may be
indicative of a routing loop in formation; hence, a node MUST send a indicative of a routing loop in formation; hence, a node MUST send a
triggered update in a timely manner whenever it changes the selected triggered update in a timely manner whenever it changes the selected
router-id for a given destination. Additionally, it SHOULD make a router-id for a given destination. Additionally, it SHOULD make a
reasonable attempt at ensuring that all neighbours receive this reasonable attempt at ensuring that all reachable neighbours receive
update. this update.
There are two strategies for ensuring that. If the number of There are two strategies for ensuring that. If the number of
neighbours is small, then it is reasonable to send the update neighbours is small, then it is reasonable to send the update
together with an acknowledgement request; the update is resent until together with an acknowledgment request; the update is resent until
all neighbours have acknowledged the packet, up to some number of all neighbours have acknowledged the packet, up to some number of
times. If the number of neighbours is large, however, requesting times. If the number of neighbours is large, however, requesting
acknowledgements from all of them might cause a non-negligible amount acknowledgments from all of them might cause a non-negligible amount
of network traffic; in that case, it may be preferable to simply of network traffic; in that case, it may be preferable to simply
repeat the update some reasonable number of times (say, 5 for repeat the update some reasonable number of times (say, 5 for
wireless and 2 for wired links). wireless and 2 for wired links).
A route retraction is somewhat less worrying: if the route retraction A route retraction is somewhat less worrying: if the route retraction
doesn't reach all neighbours, a black-hole might be created, which, doesn't reach all neighbours, a black-hole might be created, which,
unlike a routing loop, does not endanger the integrity of the unlike a routing loop, does not endanger the integrity of the
network. When a route is retracted, a node SHOULD send a triggered network. When a route is retracted, a node SHOULD send a triggered
update and SHOULD make a reasonable attempt at ensuring that all update and SHOULD make a reasonable attempt at ensuring that all
neighbours receive this retraction. neighbours receive this retraction.
Finally, a node MAY send a triggered update when the metric for a Finally, a node MAY send a triggered update when the metric for a
given prefix changes in a significant manner, either due to a given prefix changes in a significant manner, due to a received
received update or because a link cost has changed. A node SHOULD update, because a link's cost has changed, or because a different
NOT send triggered updates for other reasons, such as when there is a next hop has been selected. A node SHOULD NOT send triggered updates
minor fluctuation in a route's metric, when the selected next hop for other reasons, such as when there is a minor fluctuation in a
changes, or to propagate a new sequence number (except to satisfy a route's metric, when the selected next hop changes, or to propagate a
request, as specified in Section 3.8). new sequence number (except to satisfy a request, as specified in
Section 3.8).
3.7.3. Maintaining Feasibility Distances 3.7.3. Maintaining Feasibility Distances
Before sending an update (prefix, plen, router-id, seqno, metric) Before sending an update (prefix, plen, router-id, seqno, metric)
with finite metric (i.e., not a route retraction), a Babel node with finite metric (i.e., not a route retraction), a Babel node
updates the feasibility distance maintained in the source table. updates the feasibility distance maintained in the source table.
This is done as follows. This is done as follows.
If no entry indexed by (prefix, plen, router-id) exists in the source If no entry indexed by (prefix, plen, router-id) exists in the source
table, then one is created with value (prefix, plen, router-id, table, then one is created with value (prefix, plen, router-id,
skipping to change at page 26, line 43 skipping to change at page 27, line 19
If an entry (prefix, plen, router-id, seqno', metric') exists, then If an entry (prefix, plen, router-id, seqno', metric') exists, then
it is updated as follows: it is updated as follows:
o if seqno > seqno', then seqno' := seqno, metric' := metric; o if seqno > seqno', then seqno' := seqno, metric' := metric;
o if seqno = seqno' and metric' > metric, then metric' := metric; o if seqno = seqno' and metric' > metric, then metric' := metric;
o otherwise, nothing needs to be done. o otherwise, nothing needs to be done.
The garbage-collection timer for the entry is then reset. Note that The garbage-collection timer for the entry is then reset. Note that
the garbage-collection timer is not reset when a retraction is sent. the feasibility distance is not updated and the garbage-collection
timer is not reset when a retraction (an update with infinite metric)
is sent.
When the garbage-collection timer expires, the entry is removed from When the garbage-collection timer expires, the entry is removed from
the source table. the source table.
3.7.4. Split Horizon 3.7.4. Split Horizon
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 for
sent on this particular interface when the advertised route was prefix P is not sent on the particular interface over which the
learnt from a neighbour over the same interface. selected route towards prefix P was learnt.
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) when routing updates technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates
are sent over multicast. are sent over multicast.
3.8. Explicit Route Requests 3.8. Explicit Requests
In normal operation, a node's routing table is populated by the In normal operation, a node's route table is populated by the regular
regular and triggered updates sent by its neighbours. Under some 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 in order to
resynchronisation with the source after a mobility event or to cause a resynchronisation with the source after a mobility event or
prevent a route from spuriously expiring. to 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 the receiver. 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. request.
The exact behaviour is different for route requests and seqno The exact behaviour is different for route requests and seqno
requests. requests.
3.8.1.1. Route Requests 3.8.1.1. Route Requests
When a node receives a route request for a prefix (prefix, plen), it When a node receives a route request for a given prefix, it checks
checks its route table for a selected route to this exact prefix. If its route table for a selected route to this exact prefix. If such a
such a route exists, it MUST send an update; if such a route does route exists, it MUST send an update (over unicast or over
not, it MUST send a retraction for that prefix. multicast); if such a route does not, it MUST send a retraction for
that prefix.
When a node receives a wildcard route request, it SHOULD send a full When a node receives a wildcard route request, it SHOULD send a full
routing table dump. route table dump. Full route dumps MAY be rate-limited, especially
if they are sent over multicast.
3.8.1.2. Seqno Requests 3.8.1.2. Seqno Requests
When a node receives a seqno request for a given router-id and When a node receives a seqno request for a given router-id and
sequence number, it checks whether its routing table contains a sequence number, it checks whether its route table contains a
selected entry for that prefix. If a selected route for the given selected entry for that prefix. If a selected route for the given
prefix exists, it has finite metric, and either the router-ids are prefix exists, it has finite metric, and either the router-ids are
different or the router-ids are equal and the entry's sequence number different or the router-ids are equal and the entry's sequence number
is no smaller than the requested sequence number, the node MUST send is no smaller (modulo 2^16) than the requested sequence number, the
an update for the given prefix. If the router-ids match but the node MUST send an update for the given prefix. If the router-ids
requested seqno is larger (modulo 2^16) than the route entry's, the match but the requested seqno is larger (modulo 2^16) than the route
node compares the router-id against its own router-id. If the entry's, the node compares the router-id against its own router-id.
router-id is its own, then it increases its sequence number by 1 and If the router-id is its own, then it increases its sequence number by
sends an update. A node MUST NOT increase its sequence number by 1 (modulo 2^16) and sends an update. A node MUST NOT increase its
more than 1 in response to a seqno request. sequence number by more than 1 in response to a seqno request.
Otherwise, if the requested router-id is not its own, the received Otherwise, if the requested router-id is not its own, the received
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 is advertising the
necessarily a feasible one) for the requested prefix that does not prefix to its neighbours, the node selects a neighbour to forward the
use the requestor as a next hop, the node MUST forward the request if request to as follows:
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 o if the node has one or more feasible routes toward the requested
(not necessarily feasible) route to the requested prefix. It does so prefix with a next hop that is not the requesting node, then the
by decreasing the hop count and sending the request in a unicast node MUST forward the request to the next hop of one such route;
packet destined to a neighbour that advertises the given prefix and
that is not the neighbour from which the request was received. o otherwise, if the node has one or more (not necessarily feasible)
routes to the requested prefix with a next hop that is not the
requesting node, then the node SHOULD forward the request to the
next hop of one such route.
In order to actually forward the request, the node decrements the hop
count and sends the request in a unicast packet destined to the
selected neighbour.
A node SHOULD maintain a list of recently forwarded seqno requests A node SHOULD maintain a list of recently forwarded seqno requests
and forward the reply (an update with a sufficiently large seqno) in and forward the reply (an update with a sufficiently large seqno) in
a timely manner. A node SHOULD compare every incoming seqno request a timely manner. A node SHOULD compare every incoming seqno request
against its list of recently forwarded seqno requests and avoid against its list of recently forwarded seqno requests and avoid
forwarding it if it is redundant (i.e., if it has recently sent a 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 request with the same prefix, router-id and a seqno that is not
smaller). smaller modulo 2^16).
Since the request-forwarding mechanism does not necessarily obey the Since the request-forwarding mechanism does not necessarily obey the
feasibility condition, it may get caught in routing loops; hence, feasibility condition, it may get caught in routing loops; hence,
requests carry a hop count to limit the time for which they remain in requests carry a hop count to limit the time during which they remain
the network. However, since requests are only ever forwarded as in the network. However, since requests are only ever forwarded as
unicast packets, the initial hop count need not be kept particularly unicast packets, the initial hop count need not be kept particularly
low, and performing an expanding horizon search is not necessary. A low, and performing an expanding horizon search is not necessary. A
single request MUST NOT be duplicated: it MUST NOT be forwarded to a single request MUST NOT be duplicated: it MUST NOT be forwarded to a
multicast address, and it MUST NOT be forwarded to multiple multicast address, and it MUST NOT be forwarded to multiple
neighbours. However, if a seqno request is resent, the subsequent neighbours. However, if a seqno request is resent by its originator,
copies MAY be sent to a different neighbour than the initial one. If the subsequent copies MAY be forwarded to a different neighbour than
the route corresponding to a seqno request is unselected between the initial one.
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
to another feasible route for the same prefix. It may be the case, to another feasible route for the same prefix. It may be the case,
however, that no such routes are available. however, that no such routes are available.
A node that has lost all feasible routes to a given destination but A node that has lost all feasible routes to a given destination but
still has unexpired unfeasible routes to that destination, MUST send still has unexpired unfeasible routes to that destination MUST send a
a seqno request; if it doesn't have any such routes, it MAY still seqno request; if it doesn't have any such routes, it MAY still send
send a seqno request. The router-id of the request is set to the a seqno request. The router-id of the request is set to the router-
router-id of the route that it has just lost, and the requested seqno id of the route that it has just lost, and the requested seqno is the
is the value contained in the source table, plus 1. value contained in the source table plus 1.
If the node has any (unfeasible) routes to the requested destination, If the node has any (unfeasible) routes to the requested destination,
then it MUST send the request to at least one of the next-hop then it MUST send the request to at least one of the next-hop
neighbours that advertised these routes, and SHOULD send it to all of neighbours that advertised these routes, and SHOULD send it to all of
them; in any case, it MAY send the request to any other neighbours, them; in any case, it MAY send the request to any other neighbours,
whether they advertise a route to the requested destination or not. whether they advertise a route to the requested destination or not.
A simple implementation strategy is therefore to unconditionally A simple implementation strategy is therefore to unconditionally
multicast the request over all attached interfaces. multicast the request over all interfaces.
Similar requests will be sent by other nodes that are affected by the Similar requests will be sent by other nodes that are affected by the
route's loss. If the network is still connected, and assuming no route's loss. If the network is still connected, and assuming no
packet loss, then at least one of these requests will be forwarded to packet loss, then at least one of these requests will be forwarded to
the source, resulting in a route being advertised with a new sequence the source, resulting in a route being advertised with a new sequence
number. (Note that, due to duplicate suppression, only a small number. (Due to duplicate suppression, only a small number of such
number of such requests will actually reach the source.) requests will actually reach the source.)
In order to compensate for packet loss, a node SHOULD repeat such a In order to compensate for packet loss, a node SHOULD repeat such a
request a small number of times if no route becomes feasible within a request a small number of times if no route becomes feasible within a
short time. Under heavy packet loss, however, all such requests short time. In the presence of heavy packet loss, however, all such
might be lost; in that case, the second mechanism in the next section requests might be lost; in that case, the mechanism in the next
will eventually ensure that a new seqno is received. section will eventually ensure that a new seqno is received.
3.8.2.2. Dealing with Unfeasible Updates 3.8.2.2. Dealing with Unfeasible Updates
When a route's metric increases, a node might receive an unfeasible When a route's metric increases, a node might receive an unfeasible
update for a route that it has currently selected. As specified in update for a route that it has currently selected. As specified in
Section 3.5.1, the receiving node will either ignore the update or Section 3.5.1, the receiving node will either ignore the update or
retract the route. unselect the route.
In order to keep routes from spuriously expiring because they have In order to keep routes from spuriously expiring because they have
become unfeasible, a node SHOULD send a unicast seqno request become unfeasible, a node SHOULD send a unicast seqno request when it
whenever it receives an unfeasible update for a route that is receives an unfeasible update for a route that is currently selected.
currently selected. The requested sequence number is computed from The requested sequence number is computed from the source table as in
the source table as above. Section 3.8.2.1 above.
Additionally, since metric computation does not necessarily coincide Additionally, since metric computation does not necessarily coincide
with the delay in propagating updates, a node might receive an with the delay in propagating updates, a node might receive an
unfeasible update from a currently unselected neighbour that is unfeasible update from a currently unselected neighbour that is
preferable to the currently selected route (e.g., because it has a preferable to the currently selected route (e.g., because it has a
much smaller metric); in that case, the node SHOULD send a unicast much smaller metric); in that case, the node SHOULD send a unicast
seqno request to the neighbour that advertised the preferable update. seqno request to the neighbour that advertised the preferable update.
3.8.2.3. Preventing Routes from Expiring 3.8.2.3. Preventing Routes from Expiring
In normal operation, a route's expiry timer should never trigger: In normal operation, a route's expiry timer never triggers: since a
since a route's hold time is computed from an explicit interval route's hold time is computed from an explicit interval included in
included in Update TLVs, a new update (possibly a retraction) should Update TLVs, a new update (possibly a retraction) should arrive in
arrive in time to prevent a route from expiring. time to prevent a route from expiring.
In the presence of packet loss, however, it may be the case that no In the presence of packet loss, however, it may be the case that no
update is successfully received for an extended period of time, update is successfully received for an extended period of time,
causing a route to expire. In order to avoid such spurious expiry, causing a route to expire. In order to avoid such spurious expiry,
shortly before a selected route expires, a Babel node SHOULD send a shortly before a selected route expires, a Babel node SHOULD send a
unicast route request to the neighbour that advertised this route; unicast route request to the neighbour that advertised this route;
since nodes always send retractions in response to non-wildcard route since nodes always send either updates or retractions in response to
requests (Section 3.8.1.1), this will usually result in either the non-wildcard route requests (Section 3.8.1.1), this will usually
route being refreshed or a retraction being received. result in the route being either refreshed or retracted.
3.8.2.4. Acquiring New Neighbours 3.8.2.4. Acquiring New Neighbours
In order to speed up convergence after a mobility event, a node MAY In order to speed up convergence after a mobility event, a node MAY
send a unicast wildcard request after acquiring a new neighbour. send a unicast wildcard request after acquiring a new neighbour.
Additionally, a node MAY send a small number of multicast wildcard Additionally, a node MAY send a small number of multicast wildcard
requests shortly after booting. Note that doing that carelessly can requests shortly after booting. Note however that doing that
cause serious congestion when a whole network is rebooted, especially carelessly can cause serious congestion when a whole network is
on link layers with high per-packet overhead (e.g., IEEE 802.11). rebooted, especially on link layers with high per-packet overhead
(e.g., IEEE 802.11).
4. Protocol Encoding 4. Protocol Encoding
A Babel packet is sent as the body of a UDP datagram, with network- A Babel packet is sent as the body of a UDP datagram, with network-
layer hop count set to 1, destined to a well-known multicast address layer hop count set to 1, destined to a well-known multicast address
or to a unicast address, over IPv4 or IPv6; in the case of IPv6, or to a unicast address, over IPv4 or IPv6; in the case of IPv6,
these addresses are link-local. Both the source and destination UDP these addresses are link-local. Both the source and destination UDP
port are set to a well-known port number. A Babel packet MUST be port are set to a well-known port number. A Babel packet MUST be
silently ignored unless its source address is either a link-local silently ignored unless its source address is either a link-local
IPv6 address, or an IPv4 address belonging to the local network, and IPv6 address or an IPv4 address belonging to the local network, and
its source port is the well-known Babel port. Babel packets MUST NOT its source port is the well-known Babel port. It MAY be silently
be sent as IPv6 Jumbograms. ignored if its destination address is a global IPv6 address.
In order to minimise the number of packets being sent while avoiding In order to minimise the number of packets being sent while avoiding
lower-layer fragmentation, a Babel node SHOULD attempt to maximise lower-layer fragmentation, a Babel node SHOULD attempt to maximise
the size of the packets it sends, up to the outgoing interface's MTU the size of the packets it sends, up to the outgoing interface's MTU
adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets adjusted for lower-layer headers (28 octets for UDP over IPv4, 48
for UDP/IPv6). It MUST NOT send packets larger than the attached octets for UDP over IPv6). It MUST NOT send packets larger than the
interface's MTU (adjusted for lower-layer headers) or 512 octets, attached interface's MTU adjusted for lower-layer headers or 512
whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- octets, whichever is larger, but not exceeding 2^16 - 1 adjusted for
layer headers. Every Babel speaker MUST be able to receive packets lower-layer headers. Every Babel speaker MUST be able to receive
that are as large as any attached interface's MTU (adjusted for packets that are as large as any attached interface's MTU adjusted
lower-layer headers) or 512 octets, whichever is larger. for lower-layer headers or 512 octets, whichever is larger. Babel
packets MUST NOT be sent in IPv6 Jumbograms.
In order to avoid global synchronisation of a Babel network and to In order to avoid global synchronisation of a Babel network and to
aggregate multiple TLVs into large packets, a Babel node MUST buffer aggregate multiple TLVs into large packets, a Babel node SHOULD
every TLV and delay sending a UDP packet by a small, randomly chosen buffer every TLV and delay sending a packet by a small, randomly
delay [JITTER]. In order to allow accurate computation of packet chosen delay [JITTER]. In order to allow accurate computation of
loss rates, this delay MUST NOT be larger than half the advertised packet loss rates, this delay MUST NOT be larger than half the
Hello interval. advertised Hello interval.
4.1. Data Types 4.1. Data Types
4.1.1. Interval 4.1.1. Interval
Relative times are carried as 16-bit values specifying a number of Relative times are carried as 16-bit values specifying a number of
centiseconds (hundredths of a second). This allows times up to centiseconds (hundredths of a second). This allows times up to
roughly 11 minutes with a granularity of 10ms, which should cover all roughly 11 minutes with a granularity of 10ms, which should cover all
reasonable applications of Babel. reasonable applications of Babel.
4.1.2. Router-Id 4.1.2. Router-Id
A router-id is an arbitrary 8-octet value. A router-id MUST NOT A router-id is an arbitrary 8-octet value. A router-id MUST NOT
consist of either all zeroes or all ones. Router-ids SHOULD be consist of either all zeroes or all ones.
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 (Section 4.6.9). 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. Compression is not allowed. The o AE 3: link-local IPv6 address. Compression is not allowed. The
value is 8 octets long, a prefix of fe80::/64 is implied. value is 8 octets long, a prefix of fe80::/64 is implied.
The address family of an address is either IPv4 or IPv6; it is The address family associated to an address encoding is either IPv4
undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. or IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 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).
4.2. Packet Format 4.2. Packet Format
A Babel packet consists of a 4-octet header, followed by a sequence A Babel packet consists of a 4-octet header, followed by a sequence
skipping to change at page 32, line 45 skipping to change at page 33, line 35
Magic The arbitrary but carefully chosen value 42 (decimal); Magic The arbitrary but carefully chosen value 42 (decimal);
packets with a first octet different from 42 MUST be packets with a first octet different from 42 MUST be
silently ignored. silently ignored.
Version This document specifies version 2 of the Babel protocol. Version This document specifies version 2 of the Babel protocol.
Packets with a second octet different from 2 MUST be Packets with a second octet different from 2 MUST be
silently ignored. silently ignored.
Body length The length in octets of the body following the packet Body length The length in octets of the body following the packet
header. header (excluding the Magic, Version and Body length
fields).
Body The packet body; a sequence of TLVs. Body The packet body; a sequence of TLVs.
Any data following the body MUST be silently ignored. Any data following the body MUST be silently ignored.
4.3. TLV Format 4.3. TLV Format
With the exception of Pad1, all TLVs have the following structure: With the exception of Pad1, all TLVs have the following structure:
0 1 2 3 0 1 2 3
skipping to change at page 33, line 34 skipping to change at page 34, line 22
Payload The TLV payload, which consists of a body and, for selected Payload The TLV payload, which consists of a body and, for selected
TLV types, an optional list of sub-TLVs. TLV types, an optional list of sub-TLVs.
TLVs with an unknown type value MUST be silently ignored. TLVs with an unknown type value MUST be silently ignored.
4.4. Sub-TLV Format 4.4. Sub-TLV Format
Every TLV carries an explicit length in its header; however, most Every TLV carries an explicit length in its header; however, most
TLVs are self-terminating, in the sense that it is possible to TLVs are self-terminating, in the sense that it is possible to
determine the length of the body without reference to the explicit determine the length of the body without reference to the explicit
TLV length. If a TLV has a self-terminating format, then it MAY Length field. If a TLV has a self-terminating format, then it MAY
allow a sequence of sub-TLVs to follow the body. allow a sequence of sub-TLVs to follow the body.
Sub-TLVs have the same structure as TLVs. With the exception of Sub-TLVs have the same structure as TLVs. With the exception of
PAD1, all TLVs have the following structure: PAD1, all TLVs have the following structure:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Body... | Type | Length | Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
skipping to change at page 34, line 14 skipping to change at page 34, line 50
Body The sub-TLV body, the interpretation of which depends on Body The sub-TLV body, the interpretation of which depends on
both the type of the sub-TLV and the type of the TLV within both the type of the sub-TLV and the type of the TLV within
which it is embedded. which it is embedded.
The most-significant bit of the sub-TLV, called the mandatory bit, The most-significant bit of the sub-TLV, called the mandatory bit,
indicates how to handle unknown sub-TLVs. If the mandatory bit is indicates how to handle unknown sub-TLVs. If the mandatory bit is
not set, then an unknown sub-TLV MUST be silently ignored, and the not set, then an unknown sub-TLV MUST be silently ignored, and the
rest of the TLV processed normally. If the mandatory bit is set, rest of the TLV processed normally. If the mandatory bit is set,
then the whole enclosing TLV MUST be silently ignored (except for then the whole enclosing TLV MUST be silently ignored (except for
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. The 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 the PREFIX flag set is updated by each Update TLV with the Prefix flag set
(Section 4.6.9); (Section 4.6.9);
o for each address family (IPv4 or IPv6), the current next-hop; this 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 each
Next-Hop TLV (Section 4.6.8); Next-Hop TLV (Section 4.6.8);
o the current router-id; this is undefined at the start of the 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 each Router-ID TLV (Section 4.6.7) and
and the Update TLV with ROUTER-ID flag set. by each 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 since for correct parsing it must be identical across
is updated before checking for mandatory TLVs: parsing a TLV updates implementations, it is updated before checking for mandatory TLVs:
the parser state even if the TLV is otherwise ignored due to an parsing a TLV MUST update the parser state even if the TLV is
unknown mandatory sub-TLV. otherwise ignored due to an unknown mandatory sub-TLV.
4.6. Details of Specific TLVs 4.6. Details of Specific TLVs
4.6.1. Pad1 4.6.1. Pad1
0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
skipping to change at page 35, line 28 skipping to change at page 36, line 15
Type Set to 1 to indicate a PadN TLV. Type Set to 1 to indicate a PadN 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.
MBZ Set to 0 on transmission. MBZ Set to 0 on transmission.
This TLV is silently ignored on reception. This TLV is silently ignored on reception.
4.6.3. Acknowledgement Request 4.6.3. Acknowledgment 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 = 2 | Length | Reserved | | Type = 2 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nonce | Interval | | Nonce | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV requests that the receiver send an Acknowledgement TLV This TLV requests that the receiver send an Acknowledgment TLV within
within the number of centiseconds specified by the Interval field. the number of centiseconds specified by the Interval field.
Fields : Fields :
Type Set to 2 to indicate an Acknowledgement Request TLV. Type Set to 2 to indicate an Acknowledgment Request TLV.
Length The length of the body, exclusive of the Type and Length Length The length of the body, exclusive of the Type and Length
fields. fields.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Nonce An arbitrary value that will be echoed in the receiver's Nonce An arbitrary value that will be echoed in the receiver's
Acknowledgement TLV. Acknowledgment TLV.
Interval A time interval in centiseconds after which the sender will Interval A time interval in centiseconds after which the sender will
assume that this packet has been lost. This MUST NOT be 0. assume that this packet has been lost. This MUST NOT be 0.
The receiver MUST send an acknowledgement before this time The receiver MUST send an Acknowledgment TLV before this
has elapsed (with a margin allowing for propagation time). time has elapsed (with a margin allowing for propagation
time).
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.4. Acknowledgement 4.6.4. Acknowledgment
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 3 | Length | Nonce | | Type = 3 | Length | Nonce |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This TLV is sent by a node upon receiving an Acknowledgement Request. This TLV is sent by a node upon receiving an Acknowledgment Request.
Fields : Fields :
Type Set to 3 to indicate an Acknowledgement TLV. Type Set to 3 to indicate an Acknowledgment 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.
Nonce Set to the Nonce value of the Acknowledgement Request that Nonce Set to the Nonce value of the Acknowledgment Request that
prompted this Acknowledgement. prompted this Acknowledgment.
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
skipping to change at page 37, line 11 skipping to change at page 38, line 5
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.
Flags The individual bits of this field specify special handling Flags The individual bits of this field specify special handling
of this TLV (see below). of this TLV (see below).
Seqno If the UNICAST flag is set, this is the value of the Seqno If the Unicast flag is set, this is the value of the
sending node's outgoing Unicast Hello seqno for this sending node's outgoing Unicast Hello seqno for this
neighbour. Otherwise, it is the sending node's outgoing neighbour. Otherwise, it is the sending node's outgoing
Multicast Hello seqno for this interface. Multicast Hello seqno for this interface.
Interval If non-zero, this is an upper bound, expressed in Interval If non-zero, this is an upper bound, expressed in
centiseconds, on the time after which the sending node will centiseconds, on the time after which the sending node will
send a new scheduled Hello TLV with the same setting of the send a new scheduled Hello TLV with the same setting of the
UNICAST flag. If this is 0, then this Hello represents an Unicast flag. If this is 0, then this Hello represents an
unscheduled Hello, and doesn't carry any new information unscheduled Hello, and doesn't carry any new information
about times at which Hellos are sent. about times at which Hellos are sent.
The Flags field is interpreted as follows: The Flags field is interpreted as follows:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
In the description below, a bit being 'set' means its value is '1', o U (Unicast) flag (8000 hexadecimal): if set, then this Hello
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 represents a Unicast Hello, otherwise it represents a Multicast
Hello. Hello;
o X: all other bits MUST be sent as 0 and silently ignored on
reception.
Every time a Hello is sent, the corresponding seqno counter MUST be Every time a Hello is sent, the corresponding seqno counter MUST be
incremented. Since there is a single seqno counter for all the incremented. Since there is a single seqno counter for all the
Multicast Hellos sent by a given node over a given interface, if the Multicast Hellos sent by a given node over a given interface, if the
UNICAST flag is not set, this TLV MUST be sent to all neighbors on Unicast flag is not set, this TLV MUST be sent to all neighbors on
this link, which can be achieved by sending to a multicast this link, which can be achieved by sending to a multicast
destination, or repeatedly sending unicast to all known neighbours. destination, or by sending multiple packets to the unicast addresses
Similarly, if the UNICAST flag is set, this TLV MUST be sent to a of all reachable neighbours. Conversely, if the Unicast flag is set,
single neighbour, which can achieved by sending to a unicast this TLV MUST be sent to a single neighbour, which can achieved by
destination. In order to avoid large discontinuities in link sending to a unicast destination. In order to avoid large
quality, multiple Hello TLVs SHOULD NOT be sent in the same packet. 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Rxcost | Interval | | Rxcost | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address... | Address...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
skipping to change at page 38, line 50 skipping to change at page 39, line 47
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 MAY be sent to a TLVs contain an explicit destination address, and MAY be sent to a
multicast address, as this allows aggregation of IHUs destined to multicast address, as this allows aggregation of IHUs destined to
distinct neighbours into a single packet and avoids the need for an distinct neighbours into a single packet and avoids the need for an
ARP or Neighbour Discovery exchange when a neighbour is not being ARP or Neighbour Discovery exchange when a neighbour is not being
used for data traffic. used for data traffic.
IHU TLVs with an unknown value for the AE field MUST be silently IHU TLVs with an unknown value in the AE field MUST be silently
ignored. ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.7. Router-Id 4.6.7. Router-Id
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 6 | Length | Reserved | | Type = 6 | Length | Reserved |
skipping to change at page 40, line 4 skipping to change at page 40, line 49
4.6.8. Next Hop 4.6.8. Next Hop
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 7 | Length | AE | Reserved | | Type = 7 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next hop... | Next hop...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
A Next Hop TLV establishes a next-hop address for a given address A Next Hop TLV establishes a next-hop address for a given address
family (IPv4 or IPv6) that is implied by subsequent Update TLVs. family (IPv4 or IPv6) that is implied in subsequent Update TLVs.
This TLV sets up the next-hop for subsequent Update TLVs even if it This TLV sets up the next-hop for subsequent Update TLVs even if it
is ignored due to an unknown mandatory sub-TLV. is otherwise ignored due to an unknown mandatory sub-TLV.
Fields : Fields :
Type Set to 7 to indicate a Next Hop TLV. Type Set to 7 to indicate a Next Hop TLV.
Length The length of the body, 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 Address field. This SHOULD be 1 or 3 AE The encoding of the Address field. This SHOULD be 1 or 3
and MUST NOT be 0. and MUST NOT be 0.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Next hop The next-hop address advertised by subsequent Update TLVs, Next hop The next-hop address advertised by subsequent Update TLVs,
for this address family. for this address family.
When the address family matches the network-layer protocol that this When the address family matches the network-layer protocol that this
packet is transported over, a Next Hop TLV is not needed: in that packet is transported over, a Next Hop TLV is not needed: in the
case, the next hop is taken to be the source address of the packet. absence of a Next Hop TLV in a given address family, the next hop
address is taken to be the source address of the packet.
Next Hop TLVs with an unknown value for the AE field MUST be silently Next Hop TLVs with an unknown value for the AE field MUST be silently
ignored. ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.9. Update 4.6.9. Update
0 1 2 3 0 1 2 3
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 = 8 | Length | AE | Flags | | Type = 8 | Length | AE | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Plen | Omitted | Interval | | Plen | Omitted | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Metric | | Seqno | Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix... | Prefix...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
An Update TLV advertises or retracts a route. As an optimisation, An Update TLV advertises or retracts a route. As an optimisation, it
this can also have the side effect of establishing a new implied can optionally have the side effect of establishing a new implied
router-id and a new default prefix. router-id and a new default prefix.
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). of this TLV (see below).
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 PREFIX flag set. from a preceding Update TLV in the same address family with
the Prefix flag set.
Interval An upper bound, expressed in centiseconds, on the time Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new update for after which the sending node will send a new update for
this prefix. This MUST NOT be 0 and SHOULD NOT be less this prefix. This MUST NOT be 0. The receiving node will
than 10. The receiving node will use this value to compute use this value to compute a hold time for the route table
a hold time for this routing table entry. The value FFFF entry. The value FFFF hexadecimal (infinity) expresses
hexadecimal (infinity) expresses that this announcement that this announcement will not be repeated unless a
will not be repeated unless a request is received request is received (Section 3.8.2.3).
(Section 3.8.2.3).
Seqno The originator's sequence number for this update. Seqno The originator's sequence number for this update.
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
- Omitted) rounded upwards. (Plen/8 - Omitted) rounded upwards.
The Flags field is interpreted as follows: The Flags field is interpreted as follows:
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
|P|R|X|X|X|X|X|X| |P|R|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
In the description below, a bit being 'set' means its value is '1', o P (Prefix) flag (80 hexadecimal): if set, then this Update
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 R (ROUTER-ID) flag (40 hexadecimal): if 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.
o X: all other bits MUST be sent as 0 and silently ignored on
reception.
The prefix being advertised by an Update TLV is computed as follows: The prefix being advertised by an Update TLV is computed as follows:
o the first Omitted octets of the prefix are taken from the previous o the first Omitted octets of the prefix are taken from the previous
Update TLV with the PREFIX flag set and the same address encoding, Update TLV with the Prefix flag set and the same address encoding,
even if it was ignored due to an unknown mandatory sub-TLV; even if it was ignored due to an unknown mandatory sub-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. If AE is 3 (link-local IPv6), o the remaining octets are set to 0. If AE is 3 (link-local IPv6),
Omitted MUST be 0) 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 ROUTER-ID flag is set, computed as described above. Update if the Router-Id flag is set, computed as described above.
Otherwise, it is taken either from the preceding Router-Id packet, or Otherwise, it is taken either from the preceding Router-Id packet, or
the preceding Update packet with the ROUTER-ID flag set, whichever the preceding Update packet with the Router-Id flag set, whichever
comes last, even if that TLV is otherwise ignored due to an unknown comes last, even if that TLV 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 router-id, next-hop and seqno are not
not used. AE MAY then be 0, in which case this Update retracts all used. AE MAY then be 0, in which case this Update retracts all of
of the routes previously advertised on this interface. If the metric the routes previously advertised by the sending interface. If the
is finite, AE MUST NOT be 0. If the metric is infinite and AE is 0, metric is finite, AE MUST NOT be 0. If the metric is infinite and AE
Plen and Omitted MUST both be 0. 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 in the AE field MUST be silently
ignored. ignored.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.10. Route Request 4.6.10. Route Request
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 9 | Length | AE | Plen | | Type = 9 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix... | Prefix...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
A Route Request TLV prompts the receiver to send an update for a A Route Request TLV prompts the receiver to send an update for a
given prefix, or a full routing table dump. given prefix, or a full route table dump.
Fields : Fields :
Type Set to 9 to indicate a Route Request TLV. Type Set to 9 to indicate a Route Request TLV.
Length The length of the body, 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. The value 0 specifies AE The encoding of the Prefix field. The value 0 specifies
that this is a request for a full routing table dump (a that this is a request for a full route table dump (a
wildcard request). wildcard request).
Plen The length of the requested prefix. Plen The length of the requested prefix.
Prefix The prefix being requested. This field's size is Plen/8 Prefix The prefix being requested. This field's size is Plen/8
rounded upwards. rounded upwards.
A Request TLV prompts the receiving node to send an update message A Request TLV prompts the receiver to send an update message
for the prefix specified by the AE, Plen, and Prefix fields, or a (possibly a retraction) for the prefix specified by the AE, Plen, and
full dump of its routing table if AE is 0 (in which case Plen MUST be Prefix fields, or a full dump of its route table if AE is 0 (in which
0 and Prefix is of length 0). A Request may be sent to a unicast case Plen MUST be 0 and Prefix is of length 0).
address if it is destined to a single node, or to a multicast address
if the request is destined to all of the neighbours of the sending
interface.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.6.11. Seqno Request 4.6.11. Seqno Request
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 10 | Length | AE | Plen | | Type = 10 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 44, line 49 skipping to change at page 45, line 49
plus 1. This MUST NOT be 0. plus 1. This MUST NOT be 0.
Reserved Sent as 0 and MUST be ignored on reception. Reserved Sent as 0 and MUST be ignored on reception.
Router Id The Router-Id that is being requested. This MUST NOT Router Id The Router-Id that is being requested. This MUST NOT
consist of all zeroes or all ones. consist of all zeroes or all ones.
Prefix The prefix being requested. This field's size is Plen/8 Prefix The prefix being requested. This field's size is Plen/8
rounded upwards. rounded upwards.
A Seqno Request TLV prompts the receiving node to send an Update for A Seqno Request TLV prompts the receiving node to send a finite-
the prefix specified by the AE, Plen, and Prefix fields, with either metric Update for the prefix specified by the AE, Plen, and Prefix
a router-id different from what is specified by the Router-Id field, fields, with either a router-id different from what is specified by
or a Seqno no less (modulo 2^16) than what is specified by the Seqno the Router-Id field, or a Seqno no less (modulo 2^16) than what is
field. If this request cannot be satisfied locally, then it is specified by the Seqno field. If this request cannot be satisfied
forwarded according to the rules set out in Section 3.8.1.2. locally, then it is forwarded according to the rules set out in
Section 3.8.1.2.
While a Seqno Request MAY be sent to a multicast address, it MUST NOT While a Seqno Request MAY be sent to a multicast address, it MUST NOT
be forwarded to a multicast address and MUST NOT be forwarded to more be forwarded to a multicast address and MUST NOT be forwarded to more
than one neighbour. A request MUST NOT be forwarded if its Hop Count than one neighbour. A request MUST NOT be forwarded if its Hop Count
field is 1. field is 1.
This TLV is self-terminating, and allows sub-TLVs. This TLV is self-terminating, and allows sub-TLVs.
4.7. Details of specific sub-TLVs 4.7. Details of specific sub-TLVs
skipping to change at page 45, line 28 skipping to change at page 46, line 29
0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Fields : Fields :
Type Set to 0 to indicate a Pad1 sub-TLV. Type Set to 0 to indicate a Pad1 sub-TLV.
This sub-TLV is silently ignored on reception. This sub-TLV is silently ignored on reception. It is allowed within
any TLV that allows sub-TLVs.
4.7.2. PadN 4.7.2. PadN
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 1 | Length | MBZ... | Type = 1 | Length | MBZ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields : Fields :
Type Set to 1 to indicate a PadN sub-TLV. Type Set to 1 to indicate a PadN sub-TLV.
Length The length of the body, in octets, exclusive of the Type Length The length of the body, in octets, exclusive of the Type
and Length fields. and Length fields.
MBZ Set to 0 on transmission. MBZ Set to 0 on transmission.
This sub-TLV is silently ignored on reception. This sub-TLV is silently ignored on reception. It is allowed within
any TLV that allows sub-TLVs.
5. IANA Considerations 5. IANA Considerations
IANA has registered the UDP port number 6696, called "babel", for use IANA has registered the UDP port number 6696, called "babel", for use
by the Babel protocol. by the Babel protocol.
IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4
the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. multicast group 224.0.0.111 for use by the Babel protocol.
IANA has created a registry called "Babel TLV Types". The values in
this registry are not changed by this specification.
IANA has created a registry called "Babel sub-TLV Types". Due to the
addition of a Mandatory bit to the Babel protocol, the values in the
"Babel sub-TLV Types" registry are amended as follows:
+---------+-----------------------------------------+---------------+
| Type | Name | Reference |
+---------+-----------------------------------------+---------------+
| 0 | Pad1 | this document |
| | | |
| 1 | PadN | this document |
| | | |
| 112-126 | Reserved for Experimental Use | this document |
| | | |
| 127 | Reserved for expansion of the type | this document |
| | space | |
| | | |
| 240-254 | Reserved for Experimental Use | this document |
| | | |
| 255 | Reserved for expansion of the type | this document |
| | space | |
+---------+-----------------------------------------+---------------+
Existing assignments in the "Babel sub-TLV Types" registry in the
range 2 to 111 are not changed by this specification. The values 224
through 239, previously reserved for Experimental Use, are now
unassigned.
IANA has created a registry called "Babel Flags Values". IANA is
instructed to rename this registry to "Babel Update Flags Values",
with its contents unchanged.
IANA is instructed to create a new registry called "Babel Hello Flags
Values". The allocation policy for this registry is Specification
Required [RFC5226]. The initial values in this registry are as
follows:
+------+------------+---------------+
| Bit | Name | Reference |
+------+------------+---------------+
| 0 | Unicast | this document |
| | | |
| 1-15 | Unassigned | |
+------+------------+---------------+
IANA is instructed to replace all references to RFCs 6126 and 7557 in
all of the registries mentioned above by references to this document.
6. Security Considerations 6. Security Considerations
As defined in this document, Babel is a completely insecure protocol. As defined in this document, Babel is a completely insecure protocol.
Any attacker can attract data traffic by advertising routes with a Any attacker can misdirect data traffic by advertising routes with a
low metric. This particular issue can be solved either by lower- low metric or a high seqno. This issue can be solved either by a
layer security mechanisms (e.g., IPsec or link-layer security), or by lower-layer security mechanism (e.g. link-layer security), or by
appending a cryptographic key to Babel packets; the provision of deploying a suitable authentication mechanism within Babel itself.
ignoring any data contained within a Babel packet beyond the body With the exception of Hello TLVs used for discovery, Babel control
length declared by the header is designed for just such a purpose. traffic can be carried over unicast, which makes it possible to
protect Babel traffic with a protocol that can only protect unicast
data, for example IPsec with IKEv2, or DTLS.
The information that a Babel node announces to the whole routing The information that a Babel node announces to the whole routing
domain is often sufficient to determine a mobile node's physical domain is often sufficient to determine a mobile node's physical
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. Acknowledgments 7. Acknowledgments
A number of people have contributed text and ideas to this A number of people have contributed text and ideas to this
specification. I am particularly indebted to Matthieu Boutier, specification. The authors are particularly indebted to Matthieu
Gwendoline Chouasne, Toke Hoiland-Jorgensen, and especially David Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake and
Schinazi. The address compression technique was inspired by Toke Hoiland-Jorgensen. The address compression technique was
[PACKETBB]. inspired by [PACKETBB].
8. References 8. References
8.1. Normative References 8.1. Normative References
[ADDRARCH]
Hinden, R. and S. Deering, "IP Version 6 Addressing
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.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 5226,
May 2008.
8.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 47, line 48 skipping to change at page 50, line 9
Clausen, T., Dearlove, C., Dean, J., and C. Adjih, Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009. Format", RFC 5444, February 2009.
[RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998.
Appendix A. Cost and Metric Computation Appendix A. Cost and Metric Computation
The strategy for computing link costs and route metrics is a local The strategy for computing link costs and route metrics is a local
matter; Babel itself only requires that it comply with the conditions matter; Babel itself only requires that it comply with the conditions
given in Section 3.4.3 and Section 3.5.2. Different nodes MAY use given in Section 3.4.3 and Section 3.5.2. Different nodes may use
different strategies in a single network and MAY use different different strategies in a single network and may use different
strategies on different interface types. This section gives a few strategies on different interface types. This section describes the
examples of such strategies. strategies used by the sample implementation of Babel.
The sample implementation of Babel sends periodic Multicast Hellos, The sample implementation of Babel sends periodic Multicast Hellos,
and never sends Unicast Hellos. It maintains statistics about the and never sends Unicast Hellos. It maintains statistics about the
last 16 received Multicast Hello TLVs of each kind (Appendix A.1), last 16 received Hello TLVs of each kind (Appendix A.1), computes
computes costs by using the 2-out-of-3 strategy (Appendix A.2.1) on costs by using the 2-out-of-3 strategy (Appendix A.2.1) on wired
wired links, and ETX (Appendix A.2.2) on wireless links. It uses an links, and ETX (Appendix A.2.2) on wireless links. It uses an
additive algebra for metric computation (Appendix A.3.1). 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 two For each neighbour, the sample implementation of Babel maintains two
sets of Hello history, one for each kind of Hello, and an expected sets of Hello history, one for each kind of Hello, and an expected
sequence number, one for Multicast and one for Unicast Hellos. Each sequence number, one for Multicast and one for Unicast Hellos. Each
Hello history is a vector of 16 bits, where a 1 value represents a Hello history is a vector of 16 bits, where a 1 value represents a
received Hello, and a 0 value a missed Hello. For each kind of received Hello, and a 0 value a missed Hello. For each kind of
Hello, the expected sequence number, written ne, is the sequence Hello, the expected sequence number, written ne, is the sequence
number that is expected to be carried by the next received Hello from number that is expected to be carried by the next received Hello from
this neighbour. this neighbour.
Whenever it receives a Hello packet of a given kind from a neighbour, Whenever it receives a Hello packet of a given kind from a neighbour,
a node compares the received sequence number nr for that kind of a node compares the received sequence number nr for that kind of
Hello with its expected sequence number ne. Depending on the outcome Hello with its expected sequence number ne. Depending on the outcome
of this comparison, one of the following actions is taken: of this comparison, one of the following actions is taken:
o if the two differ by more than 16 (modulo 2^16), then the sending 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 whole node has probably rebooted and lost its sequence number; the whole
associated neighbour table entry is flushed and a new one created; associated neighbour table entry is flushed and a new one is
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 us noticing; the receiving node removes its Hello interval without us noticing; the receiving node removes
the last (ne - nr) entries from this neighbour's Hello history (we the last (ne - nr) entries from this neighbour's Hello 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 Hello history, resets The receiving node then appends a 1 bit to the Hello history and sets
the neighbour's hello timer, and sets ne to (nr + 1). If the ne to (nr + 1). If the Interval field of the received Hello is not
Interval field of the received Hello is not zero, it resets the zero, it resets the neighbour's hello timer to 1.5 times the
neighbour's hello timer to 1.5 times the advertised Interval (the advertised Interval (the extra margin allows for delay due to
extra margin allows for delay due to jitter). jitter).
Whenever either Hello timer associated to a neighbour expires, the Whenever either Hello timer associated to a neighbour expires, the
local node adds a 0 bit to this neighbour's Hello history, and local node adds a 0 bit to this neighbour's Hello history, and
increments the expected Hello number. If both Hello histories are increments the expected Hello number. If both Hello histories are
empty (they contain 0 bits only), the neighbour entry is flushed; empty (they contain 0 bits only), the neighbour entry is flushed;
otherwise, the neighbour's hello timer is reset to the value otherwise, the relevant hello timer is reset to the value advertised
advertised in the last Hello of that kind received from this in the last Hello of that kind received from this neighbour (no extra
neighbour (no extra margin is necessary in this case, since jitter margin is necessary in this case, since jitter was already taken into
was already taken into account when computing the timeout that has account when computing the timeout that has just expired).
just expired).
A.2. Cost Computation A.2. Cost Computation
This section discusses how to compute costs based on Hello history. 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.
skipping to change at page 50, line 4 skipping to change at page 52, line 12
o cost = txcost otherwise. o cost = txcost otherwise.
A.2.2. ETX A.2.2. ETX
Unlike wired links, which are bimodal (either up or down), wireless Unlike wired links, which are bimodal (either up or down), wireless
links exhibit continuous variation of the link quality. Naive links exhibit continuous variation of the link quality. Naive
application of hop-count routing in networks that use wireless links application of hop-count routing in networks that use wireless links
for transit tends to select long, lossy links in preference to for transit tends to select long, lossy links in preference to
shorter, lossless links, which can dramatically reduce throughput. shorter, lossless links, which can dramatically reduce throughput.
For that reason, a routing protocol designed to support wireless
For that reason, it is essential that a routing protocol designed to links must perform some form of link-quality estimation.
support wireless links perform some form of link-quality estimation.
ETX [ETX] is a simple link-quality estimation algorithm that is 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 designed to work well with the IEEE 802.11 MAC. By default, the
performs ARQ and rate adaptation on unicast frames, but not on IEEE 802.11 MAC performs ARQ and rate adaptation on unicast frames,
multicast frames, which are sent at a fixed rate with no ARQ; but not on multicast frames, which are sent at a fixed rate with no
therefore, measuring the loss rate of multicast frames yields a ARQ; therefore, measuring the loss rate of multicast frames yields a
useful estimate of a link's quality. useful estimate of a link's quality.
A node performing ETX link quality estimation uses a neighbour's A node performing ETX link quality estimation uses a neighbour's
Multicast Hello history to compute an estimate, written beta, of the Multicast Hello history to compute an estimate, written beta, of the
probability that a Hello TLV is successfully received. Beta can be probability that a Hello TLV is successfully received. Beta can be
simply computed as the fraction of 1 bits within a small number (say, computed as the fraction of 1 bits within a small number (say, 6) of
6) of the most recent entries in the Multicast Hello history, or it the most recent entries in the Multicast Hello history, or it can be
can be an exponential average, or some combination of both an exponential average, or some combination of both approaches.
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 Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast
frames do not provide a useful measure of link quality, and therefore frames do not provide a useful measure of link quality, and therefore
ETX ignores the Unicast Hello history. Thus, a node performing ETX ETX ignores the Unicast Hello history. Thus, a node performing ETX
link-quality estimation will not route through nodes unless they send link-quality estimation will not route through neighbouring nodes
periodic Multicast Hellos (possibly in addition to Unicast Hellos). 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 As described in Section 3.5.2, the metric advertised by a neighbour
is combined with the link cost to yield a metric. is combined with the link cost to yield a metric.
A.3.1. Additive Metrics 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 into an additive one by
the logarithm (in some suitable base) of the link costs. taking the logarithm (in some suitable base) of the link costs.
A.3.2. External Sources of Willingness A.3.2. External Sources of Willingness
A node may want to vary its willingness to forward packets by taking A node may want to vary its willingness to forward packets by taking
into account information that is external to the Babel protocol, such into account information that is external to the Babel protocol, such
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 slower
slowest of the two implementations. of the two.
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 or in the presence of packet loss. 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
skipping to change at page 52, line 21 skipping to change at page 54, line 18
scheduled Unicast Hellos; scheduled Unicast Hellos;
Update Interval: 4 times the Multicast Hello interval. Update Interval: 4 times the Multicast Hello interval.
IHU Hold Time: 3.5 times the advertised IHU interval. IHU Hold Time: 3.5 times the advertised IHU interval.
Route Expiry Time: 3.5 times the advertised update interval. Route Expiry Time: 3.5 times the advertised update interval.
Source GC time: 3 minutes. Source GC time: 3 minutes.
Request timeout: initially 2 seconds, doubled every time a request
is resent, up to a maximum of three times.
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 (Section 3.1). Urgent triggered
requests are delayed by no more than 200ms; other TLVs are delayed by updates and urgent requests are delayed by no more than 200ms;
no more than one-half the Multicast Hello interval. acknowledgments, by no more than the associated deadline; and other
TLVs by 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 or without the mandatory bit set); o defining new sub-TLVs (with or without the mandatory bit set);
o defining new AEs; o defining new AEs;
o using the packet trailer. o using the packet trailer.
New versions of the Babel protocol should only be defined if the new This appendix is intended to guide designers of protocol extensions
version is not backwards compatible with the original protocol. in chosing a particular encoding.
The version number in the Babel header should only be increased if
the new 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, by adding a non-mandatory sub-TLV to the Update TLV, or by TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by
adding a mandatory TLV. adding a mandatory sub-TLV.
The various encodings are treated differently by implementations that The various encodings are treated differently by implementations that
do not understand the extension. In the case of a new TLV or of a do not understand the extension. In the case of a new TLV or of a
sub-TLV with the mandatory bit set, the whole TLV is ignored by sub-TLV with the mandatory bit set, the whole TLV is ignored by
implementations that do not implement the extension, while in the implementations that do not implement the extension, while in the
case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, case of a non-mandatory sub-TLV, the TLV is parsed and acted upon,
and only the unknown sub-TLV is silently ignored. Therefore, a non- and only the unknown sub-TLV is silently ignored. Therefore, a non-
mandatory sub-TLV should be used by extensions that extend the Update mandatory sub-TLV should be used by extensions that extend the Update
in a compatible manner (the extension data may be silently ignored), in a compatible manner (the extension data may be silently ignored),
while a mandatory sub-TLV or a new TLV must be used by extensions while a mandatory sub-TLV or a new TLV must be used by extensions
that make incompatible extensions to the meaning of the TLV (the that make incompatible extensions to the meaning of the TLV (the
whole TLV must be thrown away if the extension data is not whole TLV must be thrown away if the extension data is not
understood). understood).
Experience shows that additional data tends to crop up in the most Experience shows that the need for additional data tends to crop up
unexpected places. Hence, it is recommended that extensions should in the most unexpected places. Hence, it is recommended that
define self-terminating TLVs, and allow attaching sub-TLVs to them. extensions that define new TLVs should make them self-terminating,
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 more involved than adding a new TLV,
TLV, since it creates a new set of compression state. Additionally, since it creates a new set of compression state. Additionally, since
since the Next Hop TLV creates state specific to a given address the Next Hop TLV creates state specific to a given address family, as
family, as opposed to a given AE, a new AE for a previously defined opposed to a given AE, a new AE for a previously defined address
address family must not be used in the Next Hop TLV if backwards family must not be used in the Next Hop TLV if backwards
compatibility is required. A similar issue arises with Update TLVs compatibility is required. A similar issue arises with Update TLVs
with unknown AEs establishing a new router-id (with ROUTER-ID flag with unknown AEs establishing a new router-id (due to the Router-Id
set). Therefore, defining new AEs must be done with care if flag being set). Therefore, defining new AEs must be done with care
compatibility with unextended implementations is required. if 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
packet but within the payload of the UDP datagram -- was originally but within the payload of the UDP datagram) was originally intended
intended to carry a cryptographic signature. However, at this time to carry a cryptographic signature. However, no extension has used
no extension has used it, and therefore we refrain from making any it to date, and therefore we refrain from making any recommendations
recommendations about its use due to the lack of implementation about its use due to the lack of implementation experience.
experience.
Appendix D. Stub Implementations Appendix D. Stub Implementations
Babel is a fairly economic protocol. Updates take between 12 and 40 Babel is a fairly economic protocol. Updates take between 12 and 40
octets per destination, depending on the address family and how octets per destination, depending on the address family and how
successful compression is; in a double-stack flat network, an average successful compression is; in a double-stack flat network, an average
of less than 24 octets per destination is typical. The route table of less than 24 octets per update is typical. The route table
occupies about 35 octets per IPv6 entry. To put these values into occupies about 35 octets per IPv6 entry. To put these values into
perspective, a single full-size Ethernet frame can carry some 65 perspective, a single full-size Ethernet frame can carry some 65
route updates, and a megabyte of memory can contain a 20000-entry route updates, and a megabyte of memory can contain a 20000-entry
routing table and the associated source table. route 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 12 000 lines of C code, and it implementation consists of less than 12 000 lines of C code, and it
compiles to less than 120 kB of text on a 32-bit CISC architecture; compiles to less than 120 kB of text on a 32-bit CISC architecture;
about half of this figure is due to protocol extensions and user- about half of this figure is due to protocol extensions and user-
interface code. interface code.
Nonetheless, in some very constrained environments, such as PDAs, Nonetheless, in some very constrained environments, such as PDAs,
microwave ovens, or abacuses, it may be desirable to have subset microwave ovens, or abacuses, it may be desirable to have subset
implementations of the protocol. implementations of the protocol.
skipping to change at page 54, line 26 skipping to change at page 56, line 29
needs of this section a stub implementation of Babel is one that needs of this section a stub implementation of Babel is one that
announces one or more directly attached prefixes into a Babel network announces one or more directly attached prefixes into a Babel network
but doesn't reannounce any routes that it has learnt from its but doesn't reannounce any routes that it has learnt from its
neighbours. It may either maintain a full routing table, or simply neighbours. It may either maintain a full routing table, or simply
select a default gateway amongst any one of its neighbours that select a default gateway amongst any one of its neighbours that
announces a default route. Since a stub implementation never announces a default route. Since a stub implementation never
forwards packets except from or to directly attached links, it cannot forwards packets except from or to directly attached links, it cannot
possibly participate in a routing loop, and hence it need not possibly participate in a routing loop, and hence it need not
evaluate the feasibility condition or maintain a source table. evaluate the feasibility condition or maintain a source table.
No matter how primitive, a stub implementation MUST parse sub-TLVs of No matter how primitive, a stub implementation MUST parse sub-TLVs
all the TLVs that it understands and check for the mandatory bit. It attached to any TLVs that it understands and check the mandatory bit.
MUST answer acknowledgement requests and MUST participate in the It MUST answer acknowledgment requests and MUST participate in the
Hello/IHU protocol (it MUST parse both Unicast and Multicast Hellos, Hello/IHU protocol. It MUST also be able to reply to seqno requests
and SHOULD send scheduled Hellos, preferably over multicast in order for routes that it announces and SHOULD be able to reply to route
to make it discoverable). It MUST also be able to reply to seqno requests.
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 Experience shows that an IPv6-only stub implementation of Babel can
be written in less than 1000 lines of C code and compile to 13 kB of be written in less than 1000 lines of C code and compile to 13 kB of
text on 32-bit CISC architecture. 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
<https://www.irif.fr/~jch/software/babel/>. <https://www.irif.fr/~jch/software/babel/>.
Appendix F. Changes from previous versions Appendix F. Changes from previous versions
skipping to change at page 55, line 31 skipping to change at page 57, line 31
o Integrated the format of sub-TLVs. o Integrated the format of sub-TLVs.
o Mentioned for each TLV whether it supports sub-TLVs. o Mentioned for each TLV whether it supports sub-TLVs.
o Added Appendix C. o Added Appendix C.
o Added a mandatory bit in sub-TLVs. o Added a mandatory bit in sub-TLVs.
o Changed compression state to be per-AF rather than per-AE. o Changed compression state to be per-AF rather than per-AE.
o Added implementation hint for the route table. o Added implementation hint for the routing table.
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.
skipping to change at page 56, line 12 skipping to change at page 58, line 12
o Added optional algorithm to avoid the hold time. o Added optional algorithm to avoid the hold time.
o Changed the table of pending seqno requests to be indexed by o Changed the table of pending seqno requests to be indexed by
router-id in addition to prefixes. router-id in addition to prefixes.
o Relaxed the route acquisition algorithm. o Relaxed the route acquisition algorithm.
o Replaced minimal implementations by stub implementations. o Replaced minimal implementations by stub implementations.
o Added acknowledgements section. o Added acknowledgments section.
Author's Address F.5. Changes since draft-ietf-babel-rfc6126bis-03
o Clarified that all the data structures are conceptual.
o Made sending and receiving Multicast Hellos a SHOULD, avoids
expressing any opinion about Unicast Hellos.
o Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4).
o Made hold-time into a SHOULD rather than MUST.
o Clarified that Seqno Requests are for a finite-metric Update.
o Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV
that allows sub-TLVs.
o Updated IANA Considerations.
o Updated Security Considerations.
o Renamed routing table back to route table.
o Made buffering outgoing updates a SHOULD.
o Weakened advice to use modified EUI-64 in router-ids.
o Added information about sending requests to Appendix B.
o A number of minor wording changes and clarifications.
Authors' Addresses
Juliusz Chroboczek Juliusz Chroboczek
IRIF, University of Paris-Diderot IRIF, University of Paris-Diderot
Case 7014 Case 7014
75205 Paris Cedex 13 75205 Paris Cedex 13
France France
Email: jch@irif.fr Email: jch@irif.fr
David Schinazi
Apple Inc.
1 Infinite Loop
Cupertino, California 95014
US
Email: dschinazi@apple.com
 End of changes. 191 change blocks. 
507 lines changed or deleted 615 lines changed or added

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