rfc8966xml2.original.xml   rfc8966.xml 
<?xml version="1.0" encoding="US-ASCII"?> <?xml version='1.0' encoding='utf-8'?>
<!DOCTYPE rfc SYSTEM "rfc2629.dtd" []> <!DOCTYPE rfc SYSTEM "rfc2629-xhtml.ent">
<?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?>
<?rfc toc="yes"?>
<?rfc tocdepth="2"?>
<?rfc symrefs="yes"?>
<?rfc sortrefs="yes" ?>
<?rfc compact="no" ?>
<rfc category="std" docName="draft-ietf-babel-rfc6126bis-20"
ipr="trust200902"
obsoletes="6126,7557">
<front>
<title>The Babel Routing Protocol</title>
<author fullname="Juliusz Chroboczek" initials="J." surname="Chroboczek">
<organization>IRIF, University of Paris-Diderot</organization>
<address>
<postal>
<street>Case 7014</street>
<city>75205 Paris Cedex 13</city>
<region></region>
<code></code>
<country>France</country>
</postal>
<email>jch@irif.fr</email>
</address>
</author>
<author fullname='David Schinazi' surname='Schinazi' initials='D.'>
<organization>Google LLC</organization>
<address>
<postal>
<street>1600 Amphitheatre Parkway</street>
<city>Mountain View</city>
<region>California</region>
<code>94043</code>
<country>USA</country>
</postal>
<email>dschinazi.ietf@gmail.com</email>
</address>
</author>
<date day="25" month="August" year="2020"/> <rfc xmlns:xi="http://www.w3.org/2001/XInclude"
category="std"
docName="draft-ietf-babel-rfc6126bis-20"
number="8966"
ipr="trust200902"
obsoletes="6126,7557"
updates=""
submissionType="IETF"
consensus="true"
xml:lang="en"
tocInclude="true"
tocDepth="2"
symRefs="true"
sortRefs="true"
version="3">
<!-- xml2rfc v2v3 conversion 3.0.0 -->
<front>
<abstract> <title>The Babel Routing Protocol</title>
<t>Babel is a loop-avoiding distance-vector routing protocol that is <seriesInfo name="RFC" value="8966"/>
<author fullname="Juliusz Chroboczek" initials="J." surname="Chroboczek">
<organization>IRIF, University of Paris-Diderot</organization>
<address>
<postal>
<street>Case 7014</street>
<city>Paris CEDEX 13</city>
<code>75205</code>
<country>France</country>
</postal>
<email>jch@irif.fr</email>
</address>
</author>
<author fullname="David Schinazi" surname="Schinazi" initials="D.">
<organization>Google LLC</organization>
<address>
<postal>
<street>1600 Amphitheatre Parkway</street>
<city>Mountain View</city>
<region>California</region>
<code>94043</code>
<country>United States of America</country>
</postal>
<email>dschinazi.ietf@gmail.com</email>
</address>
</author>
<date month="January" year="2021"/>
<keyword>Bellman-Ford</keyword>
<keyword>IGP</keyword>
<keyword>loop-avoidance</keyword>
<keyword>mesh network</keyword>
<abstract>
<t>Babel is a loop-avoiding, distance-vector routing protocol that is
robust and efficient both in ordinary wired networks and in wireless mesh robust and efficient both in ordinary wired networks and in wireless mesh
networks. This document describes the Babel routing protocol, and networks. This document describes the Babel routing protocol and
obsoletes RFCs 6126 and 7557.</t> obsoletes RFC 6126 and RFC 7557.</t>
</abstract> </abstract>
</front> </front>
<middle>
<middle> <section numbered="true" toc="default">
<name>Introduction</name>
<section title="Introduction"> <t>Babel is a loop-avoiding distance-vector routing protocol that is
<t>Babel is a loop-avoiding distance-vector routing protocol that is
designed to be robust and efficient both in networks using prefix-based designed to be robust and efficient both in networks using prefix-based
routing and in networks using flat routing ("mesh networks"), and both in routing and in networks using flat routing ("mesh networks"), and both in
relatively stable wired networks and in highly dynamic wireless networks. relatively stable wired networks and in highly dynamic wireless networks.
This document describes the Babel routing protocol, and obsoletes This document describes the Babel routing protocol and obsoletes
<xref target="RFC6126"/> and <xref target="RFC7557"/>.</t> <xref target="RFC6126" format="default"/> and <xref target="RFC7557" format="def
ault"/>.</t>
<section title="Features"> <section numbered="true" toc="default">
<name>Features</name>
<t>The main property that makes Babel suitable for unstable networks is <t>The main property that makes Babel suitable for unstable networks is
that, unlike naive distance-vector routing protocols <xref target="RIP"/>, that, unlike naive distance-vector routing protocols <xref target="RFC2453" form
at="default"/>,
it strongly limits the frequency and duration of routing pathologies such it strongly limits the frequency and duration of routing pathologies such
as routing loops and black-holes during reconvergence. Even after as routing loops and black-holes during reconvergence. Even after
a mobility event is detected, a Babel network usually remains loop-free. a mobility event is detected, a Babel network usually remains loop-free.
Babel then quickly reconverges to a configuration that preserves the Babel then quickly reconverges to a configuration that preserves the
loop-freedom and connectedness of the network, but is not necessarily loop-freedom and connectedness of the network, but is not necessarily
optimal; in many cases, this operation requires no packet exchanges at optimal; in many cases, this operation requires no packet exchanges at
all. Babel then slowly converges, in a time on the scale of minutes, to all. Babel then slowly converges, in a time on the scale of minutes, to
an optimal configuration. This is achieved by using sequenced routes, an optimal configuration. This is achieved by using sequenced routes,
a technique pioneered by Destination-Sequenced Distance-Vector routing a technique pioneered by Destination-Sequenced Distance-Vector routing
<xref target="DSDV"/>.</t> <xref target="DSDV" format="default"/>.</t>
<t>More precisely, Babel has the following properties:
<t>More precisely, Babel has the following properties: </t>
<list style="symbols"> <ul spacing="normal">
<t>when every prefix is originated by at most one router, Babel never <li>when every prefix is originated by at most one router, Babel never
suffers from routing loops;</t> suffers from routing loops;</li>
<t>when a single prefix is originated by multiple routers, Babel may <li>when a single prefix is originated by multiple routers, Babel may
occasionally create a transient routing loop for this particular prefix; occasionally create a transient routing loop for this particular prefix;
this loop disappears in time proportional to the loop's diameter, and never this loop disappears in time proportional to the loop's diameter, and never
again (up to an arbitrary garbage-collection (GC) time) will the routers again (up to an arbitrary garbage-collection (GC) time) will the routers
involved participate in a routing loop for the same prefix;</t> involved participate in a routing loop for the same prefix;</li>
<t>assuming bounded packet loss rates, any routing black-holes that <li>assuming bounded packet loss rates, any routing black-holes that
may appear after a mobility event are corrected in a time at most may appear after a mobility event are corrected in a time at most
proportional to the network's diameter.</t> proportional to the network's diameter.</li>
</list> </ul>
</t> <t>Babel has provisions for link quality estimation and for fairly
<t>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.</t> measured packet loss.</t>
<t>Babel nodes will successfully establish an association even when they
<t>Babel nodes will successfully establish an association even when they
are configured with different parameters. For example, a mobile node that are configured with different parameters. For example, a mobile node that
is low on battery may choose to use larger time constants (hello and update is low on battery may choose to use larger time constants (hello and update
intervals, etc.) than a node that has access to wall power. Conversely, a intervals, etc.) than a node that has access to wall power. Conversely, a
node that detects high levels of mobility may choose to use smaller time node that detects high levels of mobility may choose to use smaller time
constants. The ability to build such heterogeneous networks makes Babel constants. The ability to build such heterogeneous networks makes Babel
particularly adapted to the unmanaged or wireless environment.</t> particularly adapted to the unmanaged or wireless environment.</t>
<t>Finally, Babel is a hybrid routing protocol, in the sense that it can
<t>Finally, Babel is a hybrid routing protocol, in the sense that it can
carry routes for multiple network-layer protocols (IPv4 and IPv6), carry routes for multiple network-layer protocols (IPv4 and IPv6),
regardless of which protocol the Babel packets are themselves being regardless of which protocol the Babel packets are themselves being
carried over.</t> carried over.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Limitations</name>
<section title="Limitations"> <t>Babel has two limitations that make it unsuitable for use in some
<t>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 networks rather than using a reliable transport; hence, in large, stable networks
it generates more traffic than protocols that only send updates when the it generates more traffic than protocols that only send updates when the
network topology changes. In such networks, protocols such as OSPF <xref network topology changes. In such networks, protocols such as OSPF <xref target
target="OSPF"/>, IS-IS <xref target="IS-IS"/>, or the Enhanced Interior ="RFC2328" format="default"/>, IS-IS <xref target="IS-IS" format="default"/>, or
Gateway Routing Protocol (EIGRP) <xref target="EIGRP"/> might be more the Enhanced Interior
Gateway Routing Protocol (EIGRP) <xref target="EIGRP" format="default"/> might b
e more
suitable.</t> suitable.</t>
<t>Second, unless the second algorithm described in <xref target="hold-t
<t>Second, unless the second algorithm described in <xref target="hold-time"/> ime" format="default"/>
is implemented, Babel does impose a hold time when a prefix is retracted. is implemented, Babel does impose a hold time when a prefix is retracted.
While this hold time does not apply to the exact prefix being retracted, While this hold time does not apply to the exact prefix being retracted,
and hence does not prevent fast reconvergence should it become available and hence does not prevent fast reconvergence should it become available
again, it does apply to any shorter prefix that covers it. This may make again, it does apply to any shorter prefix that covers it. This may make
those implementations of Babel that do not implement the optional those implementations of Babel that do not implement the optional
algorithm described in <xref target="hold-time"/> unsuitable for use in algorithm described in <xref target="hold-time" format="default"/> unsuitable fo r use in
networks that implement automatic prefix aggregation.</t> networks that implement automatic prefix aggregation.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Specification of Requirements</name>
<section title="Specification of Requirements"> <t>
The key words "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>", "<bcp14>REQU
<t>The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", IRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>", "<bcp14>
"OPTIONAL" in this document are to be interpreted as described in BCP 14 RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
<xref target="RFC2119"/> <xref target="RFC8174"/> when, and only when, "<bcp14>MAY</bcp14>", and "<bcp14>OPTIONAL</bcp14>" in this document are to
they appear in all capitals, as shown here.</t> be interpreted as
described in BCP&nbsp;14 <xref target="RFC2119" format="default"/>
</section> <xref target="RFC8174" format="default"/> when, and only when,
they appear in all capitals, as shown here.
</section> </t>
</section>
<section title="Conceptual Description of the Protocol"> </section>
<section numbered="true" toc="default">
<t>Babel is a loop-avoiding distance vector protocol: it is based on the <name>Conceptual Description of the Protocol</name>
Bellman-Ford algorithm, just like the venerable RIP <xref target="RIP"/>, <t>Babel is a loop-avoiding distance-vector protocol: it is based on the
Bellman-Ford algorithm, just like the venerable RIP <xref target="RFC2453" forma
t="default"/>,
but includes a number of refinements that either prevent loop formation but 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.</t> doesn't form again.</t>
<t>Conceptually, Bellman-Ford is executed in parallel for every source of
<t>Conceptually, Bellman-Ford is executed in parallel for every source of
routing information (destination of data traffic). In the following routing information (destination of data traffic). In the following
discussion, we fix a source S; the reader will recall that the same discussion, we fix a source S; the reader will recall that the same
algorithm is executed for all sources.</t> algorithm is executed for all sources.</t>
<section numbered="true" toc="default">
<section title="Costs, Metrics and Neighbourship"> <name>Costs, Metrics, and Neighbourship</name>
<t>For every pair of neighbouring nodes A and B, Babel computes an
<t>For every pair of neighbouring nodes A and B, Babel computes an
abstract value known as the cost of the link from A to B, written abstract value known as the cost of the link from A to B, written
C(A,&nbsp;B). Given a route between any two (not necessarily C(A,&nbsp;B). Given a route between any two (not necessarily
neighbouring) nodes, the metric of the route is the sum of the costs of neighbouring) nodes, the metric of the route is the sum of the costs of
all the links along the route. The goal of the routing algorithm is to all the links along the route. The goal of the routing algorithm is to
compute, for every source S, the tree of routes of lowest metric to S.</t> compute, for every source S, the tree of routes of lowest metric to S.</t>
<t>Costs and metrics need not be integers. In general, they can be valu
<t>Costs and metrics need not be integers. In general, they can be values es
in any algebra that satisfies two fairly general conditions in any algebra that satisfies two fairly general conditions
(<xref target="metric-computation"/>).</t> (<xref target="metric-computation" format="default"/>).</t>
<t>A Babel node periodically sends Hello messages to all of its
<t>A Babel node periodically sends Hello messages to all of its
neighbours; it also periodically sends an IHU ("I Heard You") message to neighbours; it also periodically sends an IHU ("I Heard You") message to
every neighbour from which it has recently heard a Hello. From the every neighbour from which it has recently heard a Hello. From the
information derived from Hello and IHU messages received from its neighbour information derived from Hello and IHU messages received from its neighbour
B, a node A computes the cost C(A,&nbsp;B) of the link from A to B.</t> B, a node A computes the cost C(A,&nbsp;B) of the link from A to B.</t>
</section>
</section> <section numbered="true" toc="default">
<name>The Bellman-Ford Algorithm</name>
<section title="The Bellman-Ford Algorithm"> <t>Every node A maintains two pieces of data: its estimated distance to
S,
<t>Every node A maintains two pieces of data: its estimated distance to S,
written D(A), and its next-hop router to S, written NH(A). Initially, D(S) written D(A), and its next-hop router to S, written NH(A). Initially, D(S)
= 0, D(A) is infinite, and NH(A) is undefined.</t> = 0, D(A) is infinite, and NH(A) is undefined.</t>
<t>Periodically, every node B sends to all of its neighbours a route
<t>Periodically, every node B sends to all of its neighbours a route
update, a message containing D(B). When a neighbour A of B receives the update, a message containing D(B). When a neighbour A of B receives the
route update, it checks whether B is its selected next hop; if that is the route update, it checks whether B is its selected next hop; if that is the
case, then NH(A) is set to B, and D(A) is set to C(A, B) + D(B). If that case, then NH(A) is set to B, and D(A) is set to C(A, B) + D(B). If that
is not the case, then A compares C(A, B) + D(B) to its current value of is not the case, then A compares C(A, B) + D(B) to its current value of
D(A). If that value is smaller, meaning that the received update D(A). If that value is smaller, meaning that the received update
advertises a route that is better than the currently selected route, then advertises a route that is better than the currently selected route, then
NH(A) is set to B, and D(A) is set to C(A, B) + D(B).</t> NH(A) is set to B, and D(A) is set to C(A, B) + D(B).</t>
<t>A number of refinements to this algorithm are possible, and are used
<t>A number of refinements to this algorithm are possible, and are used by by
Babel. In particular, convergence speed may be increased by sending Babel. In particular, convergence speed may be increased by sending
unscheduled "triggered updates" whenever a major change in the topology is unscheduled "triggered updates" whenever a major change in the topology is
detected, in addition to the regular, scheduled updates. Additionally, detected, in addition to the regular, scheduled updates. Additionally,
a node may maintain a number of alternate routes, which are being a node may maintain a number of alternate routes, which are being
advertised by neighbours other than its selected neighbour, and which can advertised by neighbours other than its selected neighbour, and which can
be used immediately if the selected route were to fail.</t> be used immediately if the selected route were to fail.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Transient Loops in Bellman-Ford</name>
<section title="Transient Loops in Bellman-Ford"> <t>It is well known that a naive application of Bellman-Ford to distribu
ted
<t>It is well known that a naive application of Bellman-Ford to distributed
routing can cause transient loops after a topology change. Consider for routing can cause transient loops after a topology change. Consider for
example the following topology: example the following topology:
<figure><artwork><![CDATA[ </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
B B
1 /| 1 /|
1 / | 1 / |
S --- A |1 S --- A |1
\ | \ |
1 \| 1 \|
C C
]]></artwork></figure> ]]></artwork>
<t>
After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.</t> After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.</t>
<t>Suppose now that the link between S and A fails:
<t>Suppose now that the link between S and A fails: </t>
<figure><artwork><![CDATA[ <artwork name="" type="" align="left" alt=""><![CDATA[
B B
1 /| 1 /|
/ | / |
S A |1 S A |1
\ | \ |
1 \| 1 \|
C C
]]></artwork></figure> ]]></artwork>
</t> <t>When it detects the failure of the link, A switches its next hop to
<t>When it detects the failure of the link, A switches its next hop to
B (which is still advertising a route to S with metric 2), and advertises B (which is still advertising a route to S with metric 2), and advertises
a metric equal to 3, and then advertises a new route with metric 3. This a metric equal to 3, and then advertises a new route with metric 3. This
process of nodes changing selected neighbours and increasing their metric process of nodes changing selected neighbours and increasing their metric
continues until the advertised metric reaches "infinity", a value larger continues until the advertised metric reaches "infinity", a value larger
than all the metrics that the routing protocol is able to carry.</t> than all the metrics that the routing protocol is able to carry.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Feasibility Conditions</name>
<section title="Feasibility Conditions"> <t>Bellman-Ford is a very robust algorithm: its convergence properties
<t>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.</t> possibly cause a routing loop.</t>
<t>More formally, we define a condition over route announcements, known
<t>More formally, we define a condition over route announcements, known as as
the "feasibility condition", that guarantees the absence of routing loops the "feasibility condition", that guarantees the absence of routing loops
whenever all routers ignore route updates that do not satisfy the whenever all routers ignore route updates that do not satisfy the
feasibility condition. In effect, this makes Bellman-Ford into a family feasibility condition. In effect, this makes Bellman-Ford into a family
of routing algorithms, parameterised by the feasibility condition.</t> of routing algorithms, parameterised by the feasibility condition.</t>
<t>Many different feasibility conditions are possible. For example, BGP
<t>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 when the drastic) feasibility condition: a routing update is only accepted when the
receiving node's AS number is not included in the update's AS-Path receiving node's AS number is not included in the update's AS_PATH
attribute (note that BGP's feasibility condition does not ensure the attribute (note that BGP's feasibility condition does not ensure the
absence of transient "micro-loops" during reconvergence).</t> absence of transient "micro-loops" during reconvergence).</t>
<t>Another simple feasibility condition, used in the Destination-Sequenc
<t>Another simple feasibility condition, used in the Destination-Sequenced ed
Distance-Vector (DSDV) routing protocol <xref target="DSDV"/> and in the Distance-Vector (DSDV) routing protocol <xref target="DSDV" format="default"/> a
Ad hoc On-Demand Distance Vector (AODV) protocol <xref target="RFC3561"/>, nd in the
Ad hoc On-Demand Distance Vector (AODV) protocol <xref target="RFC3561" format="
default"/>,
stems from the following observation: a routing loop can only arise after stems from the following observation: a routing loop can only arise after
a router has switched to a route with a larger metric than the route that a router has switched to a route with a larger metric than the route that
it had previously selected. Hence, one may define that a route is it had previously selected. Hence, one may define that a route is
feasible when its metric at the local node would be no larger than feasible when its metric at the local node would be no larger than
the metric of the currently selected route, i.e., an announcement carrying the metric of the currently selected route, i.e., an announcement carrying
a metric D(B) is accepted by A when C(A, B) + D(B) &lt;= D(A). If all a metric D(B) is accepted by A when C(A, B) + D(B) &lt;= D(A). If all
routers obey this constraint, then the metric at every router is routers obey this constraint, then the metric at every router is
nonincreasing, and the following invariant is always preserved: if A has nonincreasing, and the following invariant is always preserved: if A has
selected B as its next hop, then D(B) &lt; D(A), which implies that the selected B as its next hop, then D(B) &lt; D(A), which implies that the
forwarding graph is loop-free.</t> forwarding graph is loop-free.</t>
<t>Babel uses a slightly more refined feasibility condition, derived fro
<t>Babel uses a slightly more refined feasibility condition, derived from m
EIGRP <xref target="DUAL"/>. Given a router A, define the feasibility EIGRP <xref target="DUAL" format="default"/>. Given a router A, define the feas
ibility
distance of A, written FD(A), as the smallest metric that A has ever distance of A, written FD(A), as the smallest metric that A has ever
advertised for S to any of its neighbours. An update sent by a neighbour advertised for S to any of its neighbours. An update sent by a neighbour
B of A is feasible when the metric D(B) advertised by B is strictly B of A is feasible when the metric D(B) advertised by B is strictly
smaller than A's feasibility distance, i.e., when D(B) &lt; FD(A).</t> smaller than A's feasibility distance, i.e., when D(B) &lt; FD(A).</t>
<t>It is easy to see that this latter condition is no more restrictive t
<t>It is easy to see that this latter condition is no more restrictive than han
DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; then D(A) is DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; then D(A) is
nonincreasing, hence at all times D(A) &lt;= FD(A). Suppose now that nonincreasing, hence at all times D(A) &lt;= FD(A). Suppose now that
A receives a DSDV-feasible update that advertises a metric D(B). Since the A receives a DSDV-feasible update that advertises a metric D(B). Since the
update is DSDV-feasible, C(A, B) + D(B) &lt;= D(A), hence D(B) &lt; D(A), update is DSDV-feasible, C(A, B) + D(B) &lt;= D(A), hence D(B) &lt; D(A),
and since D(A) &lt;= FD(A), D(B) &lt; FD(A).</t> and since D(A) &lt;= FD(A), D(B) &lt; FD(A).</t>
<t>To see that it is strictly less restrictive, consider the following
<t>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) = 2. diagram, where A has selected the route through B, and D(A) = FD(A) = 2.
Since D(C) = 1 &lt; FD(A), the alternate route through C is feasible for A, Since D(C) = 1 &lt; FD(A), the alternate route through C is feasible for A,
although its metric C(A, C) + D(C) = 5 is larger than that of the although its metric C(A, C) + D(C) = 5 is larger than that of the
currently selected route: currently selected route:
<figure><artwork><![CDATA[ </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
B B
1 / \ 1 1 / \ 1
/ \ / \
S A S A
\ / \ /
1 \ / 4 1 \ / 4
C C
]]></artwork></figure> ]]></artwork>
</t> <t>To show that this feasibility condition still guarantees loop-freedom
,
<t>To show that this feasibility condition still guarantees loop-freedom,
recall that at the time when A accepts an update from B, the metric D(B) recall that at the time when A accepts an update from B, the metric D(B)
announced by B is no smaller than FD(B); since it is smaller than FD(A), announced by B is no smaller than FD(B); since it is smaller than FD(A),
at that point in time FD(B) &lt; FD(A). Since this property is preserved at that point in time FD(B) &lt; FD(A). Since this property is preserved
both when A sends updates and when it picks a different next hop, it when A sends updates and also when it picks a different next hop, it
remains true at all times, which ensures that the forwarding graph has no remains true at all times, which ensures that the forwarding graph has no
loops.</t> loops.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Solving Starvation: Sequencing Routes</name>
<section title="Solving Starvation: Sequencing Routes"> <t>Obviously, the feasibility conditions defined above cause starvation
<t>Obviously, the feasibility conditions defined above cause starvation
when a router runs out of feasible routes. Consider the following diagram, when a router runs out of feasible routes. Consider the following diagram,
where both A and B have selected the direct route to S: where both A and B have selected the direct route to S:
<figure><artwork><![CDATA[ </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
A A
1 /| D(A) = 1 1 /| D(A) = 1
/ | 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
]]></artwork></figure> ]]></artwork>
<t>Suppose now that the link between A and S breaks:
</t> </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
<t>Suppose now that the link between A and S breaks:
<figure><artwork><![CDATA[
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
]]></artwork></figure> ]]></artwork>
</t> <t>The only route available from A to S, the one that goes through B, is
<t>The only route available from A to S, the one that goes through B, is
not feasible: A suffers from spurious starvation. At that point, the not feasible: A suffers from spurious starvation. At that point, the
whole subtree suffering from starvation must be reset, which is whole subtree suffering from starvation must be reset, which is
essentially what EIGRP does when it performs a global synchronisation of essentially what EIGRP does when it performs a global synchronisation of
all the routers in the starving subtree (the "active" phase of EIGRP).</t> all the routers in the starving subtree (the "active" phase of EIGRP).</t>
<t>Babel reacts to starvation in a less drastic manner, by using sequenc
<t>Babel reacts to starvation in a less drastic manner, by using sequenced ed
routes, a technique introduced by DSDV and adopted by AODV. In addition to routes, a technique introduced by DSDV and adopted by AODV. In addition to
a metric, every route carries a sequence number, a nondecreasing integer a metric, every route carries a sequence number, a nondecreasing integer
that is propagated unchanged through the network and is only ever that is propagated unchanged through the network and is only ever
incremented by the source; a pair (s, m), where s is a sequence number and incremented by the source; a pair (s, m), where s is a sequence number and
m a metric, is called a distance.</t> m a metric, is called a distance.</t>
<t>A received update is feasible when either it is more recent than the
<t>A received update is feasible when either it is more recent than the
feasibility distance maintained by the receiving node, or it is equally feasibility distance maintained by the receiving node, or it is equally
recent and the metric is strictly smaller. More formally, if FD(A) = recent and the metric is strictly smaller. More formally, if FD(A) =
(s,&nbsp;m), then an update carrying the distance (s',&nbsp;m') is feasible (s,&nbsp;m), then an update carrying the distance (s',&nbsp;m') is feasible
when either s' &gt; s, or s = s' and m' &lt; m.</t> when either s' &gt; s, or s = s' and m' &lt; m.</t>
<t>Assuming the sequence number of S is 137, the diagram above becomes:
<t>Assuming the sequence number of S is 137, the diagram above becomes: </t>
<figure><artwork><![CDATA[ <artwork name="" type="" align="left" alt=""><![CDATA[
A A
| |
| FD(A) = (137, 1) | FD(A) = (137, 1)
S |1 S |1
\ | D(B) = (137, 2) \ | D(B) = (137, 2)
2 \| FD(B) = (137, 2) 2 \| FD(B) = (137, 2)
B B
]]></artwork></figure> ]]></artwork>
</t> <t>After S increases its sequence number, and the new sequence number is
<t>After S increases its sequence number, and the new sequence number is
propagated to B, we have: propagated to B, we have:
<figure><artwork><![CDATA[ </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
A A
| |
| 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
]]></artwork></figure> ]]></artwork>
<t>
at which point the route through B becomes feasible again.</t> at which point the route through B becomes feasible again.</t>
<t>Note that while sequence numbers are used for determining feasibility
<t>Note that while sequence numbers are used for determining feasibility, ,
they are not used in route selection: a node ignores the sequence number they are not used in route selection: a node ignores the sequence number
when selecting the best route to a given destination when selecting the best route to a given destination
(<xref target="route-selection"/>). Doing otherwise would cause (<xref target="route-selection" format="default"/>). Doing otherwise would caus e
route oscillation while a sequence number propagates through the network, route oscillation while a sequence number propagates through the network,
and might even cause persistent blackholes with some exotic metrics.</t> and might even cause persistent black-holes with some exotic metrics.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Requests</name>
<section title="Requests"> <t>In DSDV, the sequence number of a source is increased periodically.
<t>In DSDV, the sequence number of a source is increased periodically.
A route becomes feasible again after the source increases its sequence A route becomes feasible again after the source increases its sequence
number, and the new sequence number is propagated through the network, number, and the new sequence number is propagated through the network,
which may, in general, require a significant amount of time.</t> which may, in general, require a significant amount of time.</t>
<t>Babel takes a different approach. When a node detects that it is
<t>Babel takes a different approach. When a node detects that it is
suffering from a potentially spurious starvation, it sends an explicit suffering from a potentially spurious starvation, it sends an explicit
request to the source for a new sequence number. This request is forwarded request to the source for a new sequence number. This request is forwarded
hop by hop to the source, with no regard to the feasibility condition. hop by hop to the source, with no regard to the feasibility condition.
Upon receiving the request, the source increases its sequence number and Upon receiving the request, the source increases its sequence number and
broadcasts an update, which is forwarded to the requesting node.</t> broadcasts an update, which is forwarded to the requesting node.</t>
<t>Note that after a change in network topology not all such requests
<t>Note that after a change in network topology not all such requests
will, in general, reach the source, as some will be sent over links that will, in general, reach the source, as some will be sent over links that
are now broken. However, if the network is still connected, then at least are now broken. However, if the network is still connected, then at least
one among the nodes suffering from spurious starvation has an (unfeasible) one among the nodes suffering from spurious starvation has an (unfeasible)
route to the source; hence, in the absence of packet loss, at least one route to the source; hence, in the absence of packet loss, at least one
such request will reach the source. (Resending requests a small number of such request will reach the source. (Resending requests a small number of
times compensates for packet loss.)</t> times compensates for packet loss.)</t>
<t>Since requests are forwarded with no regard to the feasibility
<t>Since requests are forwarded with no regard to the feasibility
condition, they may, in general, be caught in a forwarding loop; this is condition, they may, in general, be caught in a forwarding loop; this is
avoided by having nodes perform duplicate detection for the requests that avoided by having nodes perform duplicate detection for the requests that
they forward.</t> they forward.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Multiple Routers</name>
<section title="Multiple Routers"> <t>The above discussion assumes that each prefix is originated by a sing
le
<t>The above discussion assumes that each prefix is originated by a single
router. In real networks, however, it is often necessary to have a single router. In real networks, however, it is often necessary to have a single
prefix originated by multiple routers: for example, the default route will prefix originated by multiple routers: for example, the default route will
be originated by all of the edge routers of a routing domain.</t> be originated by all of the edge routers of a routing domain.</t>
<t>Since synchronising sequence numbers between distinct routers is
<t>Since synchronising sequence numbers between distinct routers is
problematic, Babel treats routes for the same prefix as distinct entities problematic, Babel treats routes for the same prefix as distinct entities
when they are originated by different routers: every route announcement when they are originated by different routers: every route announcement
carries the router-id of its originating router, and feasibility distances carries the router-id of its originating router, and feasibility distances
are not maintained per prefix, but per source, where a source is a pair of are not maintained per prefix, but per source, where a source is a pair of
a router-id and a prefix. In effect, Babel guarantees loop-freedom for the a router-id and a prefix. In effect, Babel guarantees loop-freedom for the
forwarding graph to every source; since the union of multiple acyclic forwarding graph to every source; since the union of multiple acyclic
graphs is not in general acyclic, Babel does not in general guarantee graphs is not in general acyclic, Babel does not in general guarantee
loop-freedom when a prefix is originated by multiple routers, but any loop-freedom when a prefix is originated by multiple routers, but any
loops will be broken in a time at most proportional to the diameter of the loops will be broken in a time at most proportional to the diameter of the
loop &mdash; as soon as an update has "gone around" the routing loop.</t> loop -- as soon as an update has "gone around" the routing loop.</t>
<t>Consider for example the following topology, where A has selected the
<t>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':
<figure><artwork><![CDATA[ </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
1 1 1 1 1 1
::/0 -- S --- A --- B --- S' -- ::/0 ::/0 -- S --- A --- B --- S' -- ::/0
]]></artwork></figure> ]]></artwork>
</t> <t>Suppose that both default routes fail at the same time; then nothing
<t>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, the However, as soon as A has successfully advertised the new route to B, the
route through A will become unfeasible for B. Conversely, as soon as route through A will become unfeasible for B. Conversely, as soon as
B will have advertised the route through A, the route through B will B will have advertised the route through A, the route through B will
become unfeasible for A.</t> become unfeasible for A.</t>
<t>In effect, the routing loop disappears at the latest when routing
<t>In effect, the routing loop disappears at the latest when routing
information has gone around the loop. Since this process can be delayed by information has gone around the loop. Since this process can be delayed by
lost packets, Babel makes certain efforts to ensure that updates are sent lost packets, Babel makes certain efforts to ensure that updates are sent
reliably after a router-id change (<xref target="triggered-updates"/>).</t> reliably after a router-id change (<xref target="triggered-updates" format="defa
ult"/>).</t>
<t>Additionally, after the routers have advertised the two routes, both <t>Additionally, after the routers have advertised the two routes, both
sources will be in their source tables, which will prevent them from ever sources will be in their source tables, which will prevent them from ever
again participating in a routing loop involving routes from S and S' (up to again participating in a routing loop involving routes from S and S' (up to
the source GC time, which, available memory permitting, can be set to the source GC time, which, available memory permitting, can be set to
arbitrarily large values).</t> arbitrarily large values).</t>
</section>
</section> <section anchor="overlapping-prefixes" numbered="true" toc="default">
<name>Overlapping Prefixes</name>
<section title="Overlapping Prefixes" anchor="overlapping-prefixes"> <t>In the above discussion, we have assumed that all prefixes are disjoi
nt,
<t>In the above discussion, we have assumed that all prefixes are disjoint,
as is the case in flat ("mesh") routing. In practice, however, prefixes as is the case in flat ("mesh") routing. In practice, however, prefixes
may overlap: for example, the default route overlaps with all of the routes may overlap: for example, the default route overlaps with all of the routes
present in the network.</t> present in the network.</t>
<t>After a route fails, it is not correct in general to switch to a rout
<t>After a route fails, it is not correct in general to switch to a route e
that subsumes the failed route. Consider for example the following that subsumes the failed route. Consider for example the following
configuration: configuration:
<figure><artwork><![CDATA[ </t>
<artwork name="" type="" align="left" alt=""><![CDATA[
1 1 1 1
::/0 -- A --- B --- C ::/0 -- A --- B --- C
]]></artwork></figure> ]]></artwork>
</t> <t>Suppose that node C fails. If B forwards packets destined to C by
<t>Suppose that node C fails. If B forwards packets destined to C by
following the default route, a routing loop will form, and persist until 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 this 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 retracted; pitfall by installing an "unreachable" route after a route is retracted;
this route is maintained until it can be guaranteed that the former route this route is maintained until it can be guaranteed that the former route
has been retracted by all of B's neighbours (<xref target="hold-time"/>).</t> has been retracted by all of B's neighbours (<xref target="hold-time" format="de
fault"/>).</t>
</section> </section>
</section>
</section> <section numbered="true" toc="default">
<name>Protocol Operation</name>
<section title="Protocol Operation"> <t>Every Babel speaker is assigned a router-id, which is an arbitrary
<t>Every Babel speaker is assigned a router-id, which is an arbitrary
string of 8 octets that is assumed unique across the routing domain. For string of 8 octets that is assumed unique across the routing domain. For
example, router-ids could be assigned randomly, or they could be derived example, router-ids could be assigned randomly, or they could be derived
from a link-layer address. (The protocol encoding is slightly more from a link-layer address. (The protocol encoding is slightly more
compact when router-ids are assigned in the same manner as the IPv6 layer compact when router-ids are assigned in the same manner as the IPv6 layer
assigns host IDs; see the definition of the "R" flag in assigns host IDs; see the definition of the "R" flag in
<xref target="update"/>.)</t> <xref target="update" format="default"/>.)</t>
<section anchor="transmission-reception" numbered="true" toc="default">
<section title="Message Transmission and Reception" <name>Message Transmission and Reception</name>
anchor="transmission-reception"> <t>Babel protocol packets are sent in the body of a UDP datagram (as
described in <xref target="protocol-encoding" format="default"/>). Each Babel p
<t>Babel protocol packets are sent in the body of a UDP datagram (as acket
described in <xref target="protocol-encoding"/> below). Each Babel packet
consists of zero or more TLVs. Most TLVs may contain sub-TLVs.</t> consists of zero or more TLVs. Most TLVs may contain sub-TLVs.</t>
<t>Babel's control traffic can be carried indifferently over IPv6
<t>The protocol's control traffic can be carried indifferently over IPv6
or over IPv4, and prefixes of either address family can be announced over or over IPv4, and prefixes of either address family can be announced over
either protocol. Thus, there are at least two natural deployment models: either protocol. Thus, there are at least two natural deployment models:
using IPv6 exclusively for all control traffic, or running two distinct using IPv6 exclusively for all control traffic, or running two distinct
protocol instances, one for each address family. The exclusive use of protocol instances, one for each address family. The exclusive use of
IPv6 for all control traffic is RECOMMENDED, since using both protocols at IPv6 for all control traffic is <bcp14>RECOMMENDED</bcp14>, since using both pro tocols at
the same time doubles the amount of traffic devoted to neighbour discovery the same time doubles the amount of traffic devoted to neighbour discovery
and link quality estimation.</t> and link quality estimation.</t>
<t>The source address of a Babel packet is always a unicast address,
<t>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-known 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 address. In (link-local) multicast address or to a (link-local) unicast address. In
normal operation, a Babel speaker sends both multicast and unicast packets normal operation, a Babel speaker sends both multicast and unicast packets
to its neighbours.</t> to its neighbours.</t>
<t>With the exception of acknowledgments, all Babel TLVs <t>With the exception of acknowledgments, all Babel TLVs
can be sent to either unicast or multicast addresses, and their semantics can be sent to either unicast or multicast addresses, and their semantics
does not depend on whether the destination is a unicast or a multicast does not depend on whether the destination is a unicast or a multicast
address. Hence, a Babel speaker does not need to determine the destination address. Hence, a Babel speaker does not need to determine the destination
address of a packet that it receives in order to interpret it.</t> address of a packet that it receives in order to interpret it.</t>
<t>A moderate amount of jitter may be applied to packets sent by a Babel
<t>A moderate amount of jitter may be applied to packets sent by a Babel speaker: outgoing TLVs are buffered and <bcp14>SHOULD</bcp14> be sent with a ran
speaker: outgoing TLVs are buffered and SHOULD be sent with a random dom
delay. This is done for two purposes: it avoids synchronisation of delay. This is done for two purposes: it avoids synchronisation of
multiple Babel speakers across a network <xref target="JITTER"/>, and it multiple Babel speakers across a network <xref target="JITTER" format="default"/ >, and it
allows for the aggregation of multiple TLVs into a single packet.</t> allows for the aggregation of multiple TLVs into a single packet.</t>
<t>The maximum amount of delay a TLV can be subjected to depends on the
<t>The maximum amount of delay a TLV can be subjected to depends on the
TLV. When the protocol description specifies that a TLV is urgent (as in TLV. When the protocol description specifies that a TLV is urgent (as in
<xref target="triggered-updates"/> and <xref target="sending-requests"/>), <xref target="triggered-updates" format="default"/> and <xref target="handling-r
then the TLV MUST be sent within a short time known as the urgent timeout equests" format="default"/>),
(see <xref target="parameters"/> for recommended values). When the TLV is then the TLV <bcp14>MUST</bcp14> be sent within a short time known as the urgent
timeout
(see <xref target="parameters" format="default"/> for recommended values). When
the TLV is
governed by a timeout explicitly included in a previous TLV, such as in governed by a timeout explicitly included in a previous TLV, such as in
the case of Acknowledgements (<xref target="ack"/>), the case of Acknowledgments (<xref target="ack" format="default"/>),
Updates (<xref target="sending-updates"/>) and IHUs Updates (<xref target="sending-updates" format="default"/>), and IHUs
(<xref target="bidirectional-reachability"/>), then the TLV MUST be sent (<xref target="bidirectional-reachability" format="default"/>), then the TLV <bc
p14>MUST</bcp14> be sent
early enough to meet the explicit deadline (with a small margin to allow early enough to meet the explicit deadline (with a small margin to allow
for propagation delays). In all other cases, the TLV SHOULD be sent out for propagation delays). In all other cases, the TLV <bcp14>SHOULD</bcp14> be s ent out
within one-half of the Multicast Hello interval.</t> within one-half of the Multicast Hello interval.</t>
<t>In order to avoid packet drops (either at the sender or at the
<t>In order to avoid packet drops (either at the sender or at the receiver), a delay <bcp14>SHOULD</bcp14> be introduced between successive packet
receiver), a delay SHOULD be introduced between successive packets sent s sent
out on the same interface, within the constraints of the previous out on the same interface, within the constraints of the previous
paragraph. Note however that such packet pacing might impair the ability paragraph. Note, however, that such packet pacing might impair the ability
of some link layers (e.g., IEEE&nbsp;802.11 <xref target="IEEE802.11"/>) of some link layers (e.g., IEEE&nbsp;802.11 <xref target="IEEE802.11" format="de
fault"/>)
to perform packet aggregation.</t> to perform packet aggregation.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Data Structures</name>
<section title="Data Structures"> <t>In this section, we describe the data structures that
<t>In this section, we give a description of the data structures that
every Babel speaker maintains. This description is conceptual: a Babel every Babel speaker maintains. This description is conceptual: a Babel
speaker may use different data structures as long as the resulting speaker may use different data structures as long as the resulting
protocol is the same as the one described in this document. For example, protocol is the same as the one described in this document. For example,
rather than maintaining a single table containing both selected and rather than maintaining a single table containing both selected and
unselected (fallback) routes, as described in <xref target="route-table"/> unselected (fallback) routes, as described in <xref target="route-table" format=
below, an actual implementation would probably use two tables, one with "default"/>,
an actual implementation would probably use two tables, one with
selected routes and one with fallback routes.</t> selected routes and one with fallback routes.</t>
<section anchor="sequence-number" numbered="true" toc="default">
<section title="Sequence number arithmetic" anchor="sequence-number"> <name>Sequence Number Arithmetic</name>
<t>Sequence numbers (seqnos) appear in a number of Babel data structur
<t>Sequence numbers (seqnos) appear in a number of Babel data structures, es,
and they are interpreted as integers modulo 2^16. For the purposes of and they are interpreted as integers modulo 2<sup>16</sup>. For the purposes of
this document, arithmetic on sequence numbers is defined as follows.</t> this document, arithmetic on sequence numbers is defined as follows.</t>
<t>Given a seqno s and a non-negative integer n, the sum of s and n is
<t>Given a seqno s and a non-negative integer n, the sum of s and n is defined by the following:
defined by </t>
<list style="empty"> <t indent="3">s + n (modulo 2<sup>16</sup>) = (s + n) MOD 2<sup>16</
<t>s + n (modulo 2^16) = (s + n) MOD 2^16</t> sup></t>
</list> <t>
or, equivalently, or, equivalently,
<list style="empty"> </t>
<t>s + n (modulo 2^16) = (s + n) AND 65535</t> <t indent="3">s + n (modulo 2<sup>16</sup>) = (s + n) AND 65535</t>
</list> <t>
where MOD is the modulo operation yielding a non-negative integer and AND is where MOD is the modulo operation yielding a non-negative integer, and AND is
the bitwise conjunction operation.</t> the bitwise conjunction operation.</t>
<t>Given two sequence numbers s and s', the relation s is less than s'
<t>Given two sequence numbers s and s', the relation s is less than s' (s&nbsp;&lt;&nbsp;s') is defined by the following:
(s&nbsp;&lt;&nbsp;s') is defined by </t>
<list style="empty"> <t indent="3">s &lt; s' (modulo 2<sup>16</sup>) when 0 &lt; ((s' - s
<t>s &lt; s' (modulo 2^16) when 0 &lt; ((s' - s) MOD 2^16) &lt; 32768 </t> ) MOD 2<sup>16</sup>) &lt; 32768 </t>
</list> <t>
or equivalently or, equivalently,
<list style="empty"> </t>
<t>s &lt; s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0.</t> <t indent="3">s &lt; s' (modulo 2<sup>16</sup>) when s /= s' and ((s
</list></t> ' - s) AND 32768) = 0.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Node Sequence Number</name>
<section title="Node Sequence Number"> <t>A node's sequence number is a 16-bit integer that is included in ro
ute
<t>A node's sequence number is a 16-bit integer that is included in route
updates sent for routes originated by this node.</t> updates sent for routes originated by this node.</t>
<t>A node increments its sequence number (modulo 2<sup>16</sup>) whene
<t>A node increments its sequence number (modulo 2^16) whenever it ver it
receives a request for a new sequence number (<xref receives a request for a new sequence number (<xref target="handling-seqno-reque
target="handling-seqno-requests"/>). A node SHOULD NOT increment its sts" format="default"/>). A node <bcp14>SHOULD NOT</bcp14> increment its
sequence number (seqno) spontaneously, since increasing seqnos makes it sequence number (seqno) spontaneously, since increasing seqnos makes it
less likely that other nodes will have feasible alternate routes when less likely that other nodes will have feasible alternate routes when
their selected routes fail.</t> their selected routes fail.</t>
</section>
</section> <section numbered="true" toc="default">
<name>The Interface Table</name>
<section title="The Interface Table"> <t>The interface table contains the list of interfaces on which the no
de
<t>The interface table contains the list of interfaces on which the node
speaks the Babel protocol. Every interface table entry contains the speaks the Babel protocol. Every interface table entry contains the
interface's outgoing Multicast Hello seqno, a 16-bit integer that is sent interface's outgoing Multicast Hello seqno, a 16-bit integer that is sent
with each Multicast Hello TLV on this interface and is incremented (modulo with each Multicast Hello TLV on this interface and is incremented (modulo
2^16) whenever a Multicast Hello is sent. (Note that an interface's 2<sup>16</sup>) whenever a Multicast Hello is sent. (Note that an interface's
Multicast Hello seqno is unrelated to the node's seqno.)</t> Multicast Hello seqno is unrelated to the node's seqno.)</t>
<t>There are two timers associated with each interface table entry.
<t>There are two timers associated with each interface table entry. The periodic multicast hello timer governs the sending of scheduled
The periodic Multicast Hello timer governs the sending of scheduled Multicast Hello and IHU packets (<xref target="neighbour-acquisition" format="de
Multicast Hello and IHU packets (<xref target="neighbour-acquisition"/>. fault"/>).
The periodic Update timer governs the sending of periodic route updates The periodic Update timer governs the sending of periodic route updates
(<xref target="periodic-updates"/>). See <xref target="parameters"/> for (<xref target="periodic-updates" format="default"/>). See <xref target="paramet ers" format="default"/> for
suggested time constants.</t> suggested time constants.</t>
</section>
</section> <section numbered="true" toc="default">
<name>The Neighbour Table</name>
<section title="The Neighbour Table"> <t>The neighbour table contains the list of all neighbouring interface
s
<t>The neighbour table contains the list of all neighbouring interfaces
from which a Babel packet has been recently received. The neighbour table from which a Babel packet has been recently received. The neighbour table
is indexed by pairs of the form (interface, address), and every neighbour table is indexed by pairs of the form (interface, address), and every neighbour table
entry contains the following data: entry contains the following data:
<list style="symbols"> </t>
<t>the local node's interface over which this neighbour is reachable;</t> <ul spacing="normal">
<t>the address of the neighbouring interface;</t> <li>the local node's interface over which this neighbour is reachabl
<t>a history of recently received Multicast Hello packets from this e;</li>
<li>the address of the neighbouring interface;</li>
<li>a history of recently received Multicast Hello packets from this
neighbour; this can, for example, be a sequence of n bits, for some small neighbour; this can, for example, be a sequence of n bits, for some small
value n, indicating which of the n hellos most recently sent by this value n, indicating which of the n hellos most recently sent by this
neighbour have been received by the local node;</t> neighbour have been received by the local node;</li>
<t>a history of recently received Unicast Hello packets from this neighbour;</t> <li>a history of recently received Unicast Hello packets from this n
<t>the "transmission cost" value from the last IHU packet received from eighbour;</li>
<li>the "transmission cost" value from the last IHU packet received
from
this neighbour, or FFFF hexadecimal (infinity) if the IHU hold timer for this neighbour, or FFFF hexadecimal (infinity) if the IHU hold timer for
this neighbour has expired;</t> this neighbour has expired;</li>
<t>the expected incoming Multicast Hello sequence number for this neighbour, <li>the expected incoming Multicast Hello sequence number for this n
an integer modulo 2^16.</t> eighbour,
<t>the expected incoming Unicast Hello sequence number for this neighbour, an integer modulo 2<sup>16</sup>.</li>
an integer modulo 2^16.</t> <li>the expected incoming Unicast Hello sequence number for this nei
<t>the outgoing Unicast Hello sequence number for this neighbour, an integer ghbour,
modulo 2^16 that is sent with each Unicast Hello TLV to this neighbour and an integer modulo 2<sup>16</sup>.</li>
is incremented (modulo 2^16) whenever a Unicast Hello is sent. (Note that <li>the outgoing Unicast Hello sequence number for this neighbour, a
n integer
modulo 2<sup>16</sup> that is sent with each Unicast Hello TLV to this neighbour
and
is incremented (modulo 2<sup>16</sup>) whenever a Unicast Hello is sent. (Note
that
the outgoing Unicast Hello seqno for a neighbour is distinct from the the outgoing Unicast Hello seqno for a neighbour is distinct from the
interface's outgoing Multicast Hello seqno.)</t> interface's outgoing Multicast Hello seqno.)</li>
</list> </ul>
</t> <t>There are three timers associated with each neighbour entry -- the
<t>There are three timers associated with each neighbour entry &mdash; the
multicast hello timer, which is set to the interval value carried by multicast hello timer, which is set to the interval value carried by
scheduled Multicast Hello TLVs sent by this neighbour, the unicast hello scheduled Multicast Hello TLVs sent by this neighbour, the unicast hello
timer, which is set to the interval value carried by scheduled Unicast timer, which is set to the interval value carried by scheduled Unicast
Hello TLVs, and the IHU timer, which is set to a small multiple of the Hello TLVs, and the IHU timer, which is set to a small multiple of the
interval carried in IHU TLVs (see "IHU Hold time" in interval carried in IHU TLVs (see "IHU Hold time" in
<xref target="parameters"/> for suggested values).</t> <xref target="parameters" format="default"/> for suggested values).</t>
<t>Note that the neighbour table is indexed by IP addresses, not by
<t>Note that the neighbour table is indexed by IP addresses, not by
router-ids: neighbourship is a relationship between interfaces, not between router-ids: neighbourship is a relationship between interfaces, not between
nodes. Therefore, two nodes with multiple interfaces can participate in nodes. Therefore, two nodes with multiple interfaces can participate in
multiple neighbourship relationships, a situation that can notably arise multiple neighbourship relationships, a situation that can notably arise
when wireless nodes with multiple radios are involved.</t> when wireless nodes with multiple radios are involved.</t>
</section>
</section> <section numbered="true" toc="default">
<name>The Source Table</name>
<section title="The Source Table"> <t>The source table is used to record feasibility distances. It is in
dexed
<t>The source table is used to record feasibility distances. It is indexed
by triples of the form (prefix, plen, router-id), and every source table by triples of the form (prefix, plen, router-id), and every source table
entry contains the following data: entry contains the following data:
<list style="symbols">
<t>the prefix (prefix, plen), where plen is the prefix length in bits,
that this entry applies to;</t>
<t>the router-id of a router originating this prefix;</t>
<t>a pair (seqno, metric), this source's feasibility distance.</t>
</list>
</t> </t>
<ul spacing="normal">
<t>There is one timer associated with each entry in the source table <li>the prefix (prefix, plen), where plen is the prefix length in bi
&mdash; the source garbage-collection timer. It is initialised to a time ts,
on the order of minutes and reset as specified in <xref target="maintaining-fd"/ that this entry applies to;</li>
>.</t> <li>the router-id of a router originating this prefix;</li>
<li>a pair (seqno, metric), this source's feasibility distance.</li>
</section> </ul>
<t>There is one timer associated with each entry in the source table
<section title="The Route Table" anchor="route-table"> -- the source garbage-collection timer. It is initialised to a time
on the order of minutes and reset as specified in <xref target="maintaining-fd"
<t>The route table contains the routes known to this node. It is indexed format="default"/>.</t>
</section>
<section anchor="route-table" numbered="true" toc="default">
<name>The Route Table</name>
<t>The route table contains the routes known to this node. It is inde
xed
by triples of the form (prefix, plen, neighbour), and every route table by triples of the form (prefix, plen, neighbour), and every route table
entry contains the following data: entry contains the following data:
<list style="symbols">
<t>the source (prefix, plen, router-id) for which this route is advertised;</t>
<t>the neighbour (an entry in the neighbour table) that advertised this
route;</t>
<t>the metric with which this route was advertised by the neighbour, or
FFFF hexadecimal (infinity) for a recently retracted route;</t>
<t>the sequence number with which this route was advertised;</t>
<t>the next-hop address of this route;</t>
<t>a boolean flag indicating whether this route is selected, i.e., whether
it is currently being used for forwarding and is being advertised.</t>
</list>
</t> </t>
<ul spacing="normal">
<t>There is one timer associated with each route table entry &mdash; the <li>the source (prefix, plen, router-id) for which this route is adv
ertised;</li>
<li>the neighbour (an entry in the neighbour table) that advertised
this
route;</li>
<li>the metric with which this route was advertised by the neighbour
, or
FFFF hexadecimal (infinity) for a recently retracted route;</li>
<li>the sequence number with which this route was advertised;</li>
<li>the next-hop address of this route;</li>
<li>a boolean flag indicating whether this route is selected, i.e.,
whether
it is currently being used for forwarding and is being advertised.</li>
</ul>
<t>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
<xref target="route-acquisition"/>.</t> <xref target="route-acquisition" format="default"/>.</t>
<t>Note that there are two distinct (seqno, metric) pairs associated w
<t>Note that there are two distinct (seqno, metric) pairs associated to ith
each route: the route's distance, which is stored in the route table, and each route: the route's distance, which is stored in the route table, and
the feasibility distance, stored in the source table and shared between the feasibility distance, which is stored in the source table and shared between
all routes with the same source.</t> all routes with the same source.</t>
</section>
</section> <section numbered="true" toc="default">
<name>The Table of Pending Seqno Requests</name>
<section title="The Table of Pending Seqno Requests"> <t>The table of pending seqno requests contains a list of seqno reques
ts
<t>The table of pending seqno requests contains a list of seqno requests
that the local node has sent (either because they have been originated that the local node has sent (either because they have been originated
locally, or because they were forwarded) and to which no reply has been locally, or because they were forwarded) and to which no reply has been
received yet. This table is indexed by triples of the form (prefix, plen, received yet. This table is indexed by triples of the form (prefix, plen,
router-id), and every entry in this table contains the following data: router-id), and every entry in this table contains the following data:
<list style="symbols">
<t>the prefix, plen, router-id, and seqno being requested;</t>
<t>the neighbour, if any, on behalf of which we are forwarding this
request;</t>
<t>a small integer indicating the number of times that this request will be
resent if it remains unsatisfied.</t>
</list>
</t> </t>
<ul spacing="normal">
<t>There is one timer associated with each pending seqno request; it governs <li>the prefix, plen, router-id, and seqno being requested;</li>
<li>the neighbour, if any, on behalf of which we are forwarding this
request;</li>
<li>a small integer indicating the number of times that this request
will be
resent if it remains unsatisfied.</li>
</ul>
<t>There is one timer associated with each pending seqno request; it g
overns
both the resending of requests and their expiry.</t> both the resending of requests and their expiry.</t>
</section>
</section> </section>
</section> <section anchor="acknowledgments" numbered="true" toc="default">
<name>Acknowledgments and Acknowledgment Requests</name>
<section title="Acknowledgments and acknowledgment requests" <t>A Babel speaker may request that a neighbour receiving a given packet
anchor="acknowledgments">
<t>A Babel speaker may request that a neighbour receiving a given packet
reply with an explicit acknowledgment within a given time. While the use reply with an explicit acknowledgment within a given time. While the use
of acknowledgment requests is optional, every Babel speaker MUST be able of acknowledgment requests is optional, every Babel speaker <bcp14>MUST</bcp14> be able
to reply to such a request.</t> to reply to such a request.</t>
<t>An acknowledgment <bcp14>MUST</bcp14> be sent to a unicast destinatio
<t>An acknowledgment MUST be sent to a unicast destination. On the other n. On the other
hand, acknowledgment requests may be sent to either unicast or multicast hand, acknowledgment requests may be sent to either unicast or multicast
destinations, in which case they request an acknowledgment from all of the destinations, in which case they request an acknowledgment from all of the
receiving nodes.</t> receiving nodes.</t>
<t>When to request acknowledgments is a matter of local policy; the
<t>When to request acknowledgments is a matter of local policy; the
simplest strategy is to never request acknowledgments 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. In order to improve convergence propagated throughout the routing domain. In order to improve convergence
speed and reduce the amount of control traffic, acknowledgment requests speed and to reduce the amount of control traffic, acknowledgment requests
MAY be used in order to reliably send urgent updates (<xref <bcp14>MAY</bcp14> be used in order to reliably send urgent updates (<xref targe
target="triggered-updates"/>) and retractions (<xref target="hold-time"/>), t="triggered-updates" format="default"/>) and retractions (<xref target="hold-ti
me" format="default"/>),
especially when the number of neighbours on a given interface is small. especially when the number of neighbours on a given interface is small.
Since Babel is designed to deal gracefully with packet loss on unreliable Since Babel is designed to deal gracefully with packet loss on unreliable
media, sending all packets with acknowledgment requests is not necessary, media, sending all packets with acknowledgment requests is not necessary
and NOT RECOMMENDED, as the acknowledgments cause additional traffic and and <bcp14>NOT RECOMMENDED</bcp14>, as the acknowledgments cause additional traf
fic and
may force additional Address Resolution Protocol (ARP) or Neighbour may force additional Address Resolution Protocol (ARP) or Neighbour
Discovery (ND) exchanges.</t> Discovery (ND) exchanges.</t>
</section>
</section> <section anchor="neighbour-acquisition" numbered="true" toc="default">
<name>Neighbour Acquisition</name>
<section title="Neighbour Acquisition" anchor="neighbour-acquisition"> <t>Neighbour acquisition is the process by which a Babel node discovers
the
<t>Neighbour acquisition is the process by which a Babel node discovers the
set of neighbours heard over each of its interfaces and ascertains set of neighbours heard over each of its interfaces and ascertains
bidirectional reachability. On unreliable media, neighbour acquisition bidirectional reachability. On unreliable media, neighbour acquisition
additionally provides some statistics that may be useful for link quality additionally provides some statistics that may be useful for link quality
computation.</t> computation.</t>
<t>Before it can exchange routing information with a neighbour, a Babel
<t>Before it can exchange routing information with a neighbour, a Babel node <bcp14>MUST</bcp14> create an entry for that neighbour in the neighbour tab
node MUST create an entry for that neighbour in the neighbour table. When le. When
to do that is implementation-specific; suitable strategies include to do that is implementation-specific; suitable strategies include
creating an entry when any Babel packet is received, or creating an entry creating an entry when any Babel packet is received, or creating an entry
when a Hello TLV is parsed. Similarly, in order to conserve system when a Hello TLV is parsed. Similarly, in order to conserve system
resources, an implementation SHOULD discard an entry when it has been resources, an implementation <bcp14>SHOULD</bcp14> discard an entry when it has been
unused for long enough; suitable strategies include dropping the neighbour unused for long enough; suitable strategies include dropping the neighbour
after a timeout, and dropping a neighbour when the associated Hello after a timeout, and dropping a neighbour when the associated Hello
histories become empty (see <xref target="cost-computation-examples"/>).</t> histories become empty (see <xref target="cost-computation-examples" format="def
ault"/>).</t>
<section title="Reverse Reachability Detection" anchor="reverse-reachability"> <section anchor="reverse-reachability" numbered="true" toc="default">
<name>Reverse Reachability Detection</name>
<t>Every Babel node sends Hello TLVs to its neighbours to indicate that it <t>Every Babel node sends Hello TLVs to its neighbours, at regular or
is alive, at regular or irregular intervals. Each Hello TLV carries an irregular intervals, to indicate that it
increasing (modulo 2^16) sequence number and an upper bound on the time is alive. Each Hello TLV carries an
increasing (modulo 2<sup>16</sup>) sequence number and an upper bound on the tim
e
interval until the next Hello of the same type (see below). If the time interval until the next Hello of the same type (see below). If the time
interval is set to 0, then the Hello TLV does not establish a new promise: interval is set to 0, then the Hello TLV does not establish a new promise:
the deadline carried by the previous Hello of the same type still applies the deadline carried by the previous Hello of the same type still applies
to the next Hello (if the most recent scheduled Hello of the right kind to the next Hello (if the most recent scheduled Hello of the right kind
was received at time t0 and carried interval i, then the previous promise was received at time t0 and carried interval i, then the previous promise
of sending another Hello before time t0&nbsp;+&nbsp;i still holds). We of sending another Hello before time t0&nbsp;+&nbsp;i still holds). We
say that a Hello is "scheduled" if it carries a non-zero interval, and say that a Hello is "scheduled" if it carries a nonzero interval, and
"unscheduled" otherwise.</t> "unscheduled" otherwise.</t>
<t>There are two kinds of Hellos: Multicast Hellos, which use
<t>There are two kinds of Hellos: Multicast Hellos, which use
a per-interface Hello counter (the Multicast Hello seqno), and Unicast a per-interface Hello counter (the Multicast Hello seqno), and Unicast
Hellos, which use a per-neighbour counter (the Unicast Hello seqno). Hellos, which use a per-neighbour counter (the Unicast Hello seqno).
A Multicast Hello with a given seqno MUST be sent to all neighbours on A Multicast Hello with a given seqno <bcp14>MUST</bcp14> be sent to all neighbou rs on
a given interface, either by sending it to a multicast address or by a given interface, either by sending it to a multicast address or by
sending it to one unicast address per neighbour (hence, the term sending it to one unicast address per neighbour (hence, the term
"Multicast Hello" is a slight misnomer). A Unicast Hello carrying a given "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a given
seqno should normally be sent to just one neighbour (over unicast), since seqno should normally be sent to just one neighbour (over unicast), since
the sequence numbers of different neighbours are not in general the sequence numbers of different neighbours are not in general
synchronised.</t> synchronised.</t>
<t>Multicast Hellos sent over multicast can be used for neighbour
<t>Multicast Hellos sent over multicast can be used for neighbour discovery; hence, a node <bcp14>SHOULD</bcp14> send periodic (scheduled) Multica
discovery; hence, a node SHOULD send periodic (scheduled) Multicast Hellos st Hellos
unless neighbour discovery is performed by means outside of the Babel unless neighbour discovery is performed by means outside of the Babel
protocol. A node MAY send Unicast Hellos or unscheduled Hellos of either protocol. A node <bcp14>MAY</bcp14> send Unicast Hellos or unscheduled Hellos o f either
kind for any reason, such as reducing the amount of multicast traffic or kind for any reason, such as reducing the amount of multicast traffic or
improving reliability on link technologies with poor support for improving reliability on link technologies with poor support for
link-layer multicast.</t> link-layer multicast.</t>
<t>A node <bcp14>MAY</bcp14> send a scheduled Hello ahead of time. A
<t>A node MAY send a scheduled Hello ahead of time. A node MAY change its node <bcp14>MAY</bcp14> change its
scheduled Hello interval. The Hello interval MAY be decreased at any scheduled Hello interval. The Hello interval <bcp14>MAY</bcp14> be decreased at
time; it MAY be increased immediately before sending a Hello TLV, but any
SHOULD NOT be increased at other times. (Equivalently, a node SHOULD send time; it <bcp14>MAY</bcp14> be increased immediately before sending a Hello TLV,
but
<bcp14>SHOULD NOT</bcp14> be increased at other times. (Equivalently, a node <b
cp14>SHOULD</bcp14> send
a scheduled Hello immediately after increasing its Hello interval.)</t> a scheduled Hello immediately after increasing its Hello interval.)</t>
<t>How to deal with received Hello TLVs and what statistics to maintai
<t>How to deal with received Hello TLVs and what statistics to maintain n
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. An example of maintain some sort of history of recently received Hellos. An example of
a suitable algorithm is described in <xref target="hello-history"/>.</t> a suitable algorithm is described in <xref target="hello-history" format="defaul
t"/>.</t>
<t>After receiving a Hello, or determining that it has missed one, the node <t>After receiving a Hello, or determining that it has missed one, the
recomputes the association's cost (<xref target="cost-computation"/>) and node
runs the route selection procedure (<xref target="route-selection"/>).</t> recomputes the association's cost (<xref target="cost-computation" format="defau
lt"/>) and
</section> runs the route selection procedure (<xref target="route-selection" format="defau
lt"/>).</t>
<section title="Bidirectional Reachability Detection" </section>
anchor="bidirectional-reachability"> <section anchor="bidirectional-reachability" numbered="true" toc="defaul
t">
<t>In order to establish bidirectional reachability, every node sends <name>Bidirectional Reachability Detection</name>
<t>In order to establish bidirectional reachability, every node sends
periodic IHU ("I Heard You") TLVs to each of its neighbours. Since IHUs periodic IHU ("I Heard You") TLVs to each of its neighbours. Since IHUs
carry an explicit interval value, they MAY be sent less often than Hellos carry an explicit interval value, they <bcp14>MAY</bcp14> be sent less often tha n Hellos
in order to reduce the amount of routing traffic in dense networks; in in order to reduce the amount of routing traffic in dense networks; in
particular, they SHOULD be sent less often than Hellos over links with particular, they <bcp14>SHOULD</bcp14> be sent less often than Hellos over links
little packet loss. While IHUs are conceptually unicast, they MAY be with
little packet loss. While IHUs are conceptually unicast, they <bcp14>MAY</bcp14
> be
sent to a multicast address in order to avoid an ARP or Neighbour Discovery sent to a multicast address in order to avoid an ARP or Neighbour Discovery
exchange and to aggregate multiple IHUs into a single packet.</t> exchange and to aggregate multiple IHUs into a single packet.</t>
<t>In addition to the periodic IHUs, a node <bcp14>MAY</bcp14>, at any
<t>In addition to the periodic IHUs, a node MAY, at any time, send an time, send an
unscheduled IHU packet. It MAY also, at any time, decrease its IHU unscheduled IHU packet. It <bcp14>MAY</bcp14> also, at any time, decrease its I
interval, and it MAY increase its IHU interval immediately before sending HU
an IHU, but SHOULD NOT increase it at any other time. (Equivalently, interval, and it <bcp14>MAY</bcp14> increase its IHU interval immediately before
a node SHOULD send an extra IHU immediately after increasing its Hello sending
an IHU, but <bcp14>SHOULD NOT</bcp14> increase it at any other time. (Equivalen
tly,
a node <bcp14>SHOULD</bcp14> send an extra IHU immediately after increasing its
Hello
interval.)</t> interval.)</t>
<t>Every IHU TLV contains two pieces of data: the link's rxcost (recep
<t>Every IHU TLV contains two pieces of data: the link's rxcost (reception tion
cost) from the sender's perspective, used by the neighbour for computing cost) from the sender's perspective, used by the neighbour for computing
link costs (<xref target="cost-computation"/>), and the interval between link costs (<xref target="cost-computation" format="default"/>), and the interva l between
periodic IHU packets. A node receiving an IHU sets the value of the periodic IHU packets. A node receiving an IHU sets the value of the
txcost (transmission cost) maintained in the neighbour table to the value txcost (transmission cost) maintained in the neighbour table to the value
contained in the IHU, and resets the IHU timer associated to this contained in the IHU, and resets the IHU timer associated to this
neighbour to a small multiple of the interval value received in the IHU neighbour to a small multiple of the interval value received in the IHU
(see "IHU Hold time" in <xref target="parameters"/> for suggested values). (see "IHU Hold time" in <xref target="parameters" format="default"/> for suggest ed values).
When a neighbour's IHU timer expires, the neighbour's txcost is set to When a neighbour's IHU timer expires, the neighbour's txcost is set to
infinity.</t> infinity.</t>
<t>After updating a neighbour's txcost, the receiving node recomputes
<t>After updating a neighbour's txcost, the receiving node recomputes the the
neighbour's cost (<xref target="cost-computation"/>) and runs the route neighbour's cost (<xref target="cost-computation" format="default"/>) and runs t
selection procedure (<xref target="route-selection"/>).</t> he route
selection procedure (<xref target="route-selection" format="default"/>).</t>
</section> </section>
<section anchor="cost-computation" numbered="true" toc="default">
<section title="Cost Computation" anchor="cost-computation"> <name>Cost Computation</name>
<t>A neighbourship association's link cost is computed from the values
<t>A neighbourship association's link cost is computed from the values
maintained in the neighbour table: the statistics kept in the neighbour maintained in the neighbour table: the statistics kept in the neighbour
table about the reception of Hellos, and the txcost computed from received table about the reception of Hellos, and the txcost computed from received
IHU packets.</t> IHU packets.</t>
<t>For every neighbour, a Babel node computes a value known as this
<t>For every neighbour, a Babel node computes a value known as this
neighbour's rxcost. This value is usually derived from the Hello history, neighbour's rxcost. This value is usually derived from the Hello history,
which may be combined with other data, such as statistics maintained by which may be combined with other data, such as statistics maintained by
the link layer. The rxcost is sent to a neighbour in each IHU.</t> the link layer. The rxcost is sent to a neighbour in each IHU.</t>
<t>Since nodes do not necessarily send periodic Unicast Hellos but do
<t>Since nodes do not necessarily send periodic Unicast Hellos but do usually send periodic Multicast Hellos (<xref target="reverse-reachability" form
usually send periodic Multicast Hellos (<xref target="reverse-reachability"/>), at="default"/>),
a node SHOULD use an algorithm that yields a finite rxcost when only a node <bcp14>SHOULD</bcp14> use an algorithm that yields a finite rxcost when o
nly
Multicast Hellos are received, unless interoperability with nodes that Multicast Hellos are received, unless interoperability with nodes that
only send Multicast Hellos is not required.</t> only send Multicast Hellos is not required.</t>
<t>How the txcost and rxcost are combined in order to compute a link's
<t>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 <bcp14>MUST</bcp14> be satisfied:
<list style="symbols"> </t>
<t>the cost is strictly positive;</t> <ul spacing="normal">
<t>if no Hello TLVs of either kind were received recently, then the cost <li>the cost is strictly positive;</li>
is infinite;</t> <li>if no Hello TLVs of either kind were received recently, then the
<t>if the txcost is infinite, then the cost is infinite.</t> cost
</list></t> is infinite;</li>
<li>if the txcost is infinite, then the cost is infinite.</li>
<t>See <xref target="cost-computation-examples"/> for RECOMMENDED </ul>
<t>See <xref target="cost-computation-examples" format="default"/> for
<bcp14>RECOMMENDED</bcp14>
strategies for computing a link's cost.</t> strategies for computing a link's cost.</t>
</section>
</section> </section>
<section anchor="route-maintenance" numbered="true" toc="default">
</section> <name>Routing Table Maintenance</name>
<t>Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
<section title="Routing Table Maintenance" anchor="route-maintenance">
<t>Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
seqno, metric), where (prefix, plen) is the prefix for which a route is seqno, metric), where (prefix, plen) is the prefix for which a route is
being advertised, router-id is the router-id of the router originating this being advertised, router-id is the router-id of the router originating this
update, seqno is a nondecreasing (modulo 2^16) integer that carries the update, seqno is a nondecreasing (modulo 2<sup>16</sup>) integer that carries th e
originating router seqno, and metric is the announced metric.</t> originating router seqno, and metric is the announced metric.</t>
<t>Before being accepted, an update is checked against the feasibility
<t>Before being accepted, an update is checked against the feasibility condition (<xref target="feasibility-condition" format="default"/>), which ensur
condition (<xref target="feasibility-condition"/>), which ensures that the es that the
route does not create a routing loop. If the feasibility condition is not route does not create a routing loop. If the feasibility condition is not
satisfied, the update is either ignored or prevents the route from being satisfied, the update is either ignored or prevents the route from being
selected, as described in <xref target="route-acquisition"/>. If the selected, as described in <xref target="route-acquisition" format="default"/>. If the
feasibility condition is satisfied, then the update cannot possibly cause feasibility condition is satisfied, then the update cannot possibly cause
a routing loop.</t> a routing loop.</t>
<section anchor="feasibility-condition" numbered="true" toc="default">
<section title="The Feasibility Condition" anchor="feasibility-condition"> <name>The Feasibility Condition</name>
<t>The feasibility condition is applied to all received updates. The
<t>The feasibility condition is applied to all received updates. The
feasibility condition compares the metric in the received update with the feasibility condition compares the metric in the received update with the
metrics of the updates previously sent by the receiving node; updates that metrics of the updates previously sent by the receiving node; updates that
fail the feasibility condition, and therefore have metrics large enough to fail the feasibility condition, and therefore have metrics large enough to
cause a routing loop, are either ignored or prevent the resulting route cause a routing loop, are either ignored or prevent the resulting route
from being selected.</t> from being selected.</t>
<t>A feasibility distance is a pair (seqno, metric), where seqno is an
<t>A feasibility distance is a pair (seqno, metric), where seqno is an integer modulo 2<sup>16</sup> 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 than inverted: we say that a distance (seqno, metric) is strictly better than
a distance (seqno', metric'), written a distance (seqno', metric'), written
<list style="empty"> </t>
<t>(seqno, metric) &lt; (seqno', metric')</t> <t indent="3">(seqno, metric) &lt; (seqno', metric')</t>
</list> <t>
when when
<list style="empty"> </t>
<t>seqno &gt; seqno' or (seqno = seqno' and metric &lt; metric')</t> <t indent="3">seqno &gt; seqno' or (seqno = seqno' and metric &lt; m
</list> etric')</t>
where sequence numbers are compared modulo 2^16.</t> <t>
where sequence numbers are compared modulo 2<sup>16</sup>.</t>
<t>Given a source (prefix, plen, router-id), a node's feasibility distance <t>Given a source (prefix, plen, router-id), a node's feasibility dist
ance
for this source is the minimum, according to the ordering defined above, for this source is the minimum, according to the ordering defined above,
of the distances of all the finite updates ever sent by this particular of the distances of all the finite updates ever sent by this particular
node for the prefix (prefix, plen) and the given router-id. Feasibility node for the prefix (prefix, plen) and the given router-id. Feasibility
distances are maintained in the source table, the exact procedure is given distances are maintained in the source table, the exact procedure is given
in <xref target="maintaining-fd"/>.</t> in <xref target="maintaining-fd" format="default"/>.</t>
<t>A received update is feasible when either it is a retraction (its m
<t>A received update is feasible when either it is a retraction (its metric etric
is FFFF hexadecimal), or the advertised distance is strictly better, in the is FFFF hexadecimal), or the advertised distance is strictly better, in the
sense defined above, than the feasibility distance for the corresponding sense defined above, than the feasibility distance for the corresponding
source. More precisely, a route advertisement carrying the quintuple source. More precisely, a route advertisement carrying the quintuple
(prefix, plen, router-id, seqno, metric) is feasible if one of the (prefix, plen, router-id, seqno, metric) is feasible if one of the
following conditions holds: following conditions holds:
<list style="symbols">
<t>metric is infinite; or</t>
<t>no entry exists in the source table indexed by (prefix, plen, router-id);
or</t>
<t>an entry (prefix, plen, router-id, seqno', metric') exists in the
source table, and either
<list style="symbols">
<t>seqno' &lt; seqno or</t>
<t>seqno = seqno' and metric &lt; metric'.</t>
</list>
</t>
</list>
</t> </t>
<ul spacing="normal">
<t>Note that the feasibility condition considers the metric advertised by <li>metric is infinite; or</li>
<li>no entry exists in the source table indexed by (prefix, plen, ro
uter-id);
or</li>
<li>
<t>an entry (prefix, plen, router-id, seqno', metric') exists in t
he
source table, and either
</t>
<ul spacing="normal">
<li>seqno' &lt; seqno or</li>
<li>seqno = seqno' and metric &lt; metric'.</li>
</ul>
</li>
</ul>
<t>Note that the feasibility condition considers the metric advertised
by
the neighbour, not the route's metric; hence, a fluctuation in the neighbour, not the route's metric; hence, a fluctuation in
a neighbour's cost cannot render a selected route unfeasible. Note a neighbour's cost cannot render a selected route unfeasible. Note
further that retractions (updates with infinite metric) are always further that retractions (updates with infinite metric) are always
feasible, since they cannot possibly cause a routing loop.</t> feasible, since they cannot possibly cause a routing loop.</t>
</section>
</section> <section anchor="metric-computation" numbered="true" toc="default">
<name>Metric Computation</name>
<section title="Metric Computation" anchor="metric-computation"> <t>A route's metric is computed from the metric advertised by the neig
hbour
<t>A route's metric is computed from the metric advertised by the neighbour
and the neighbour's link cost. Just like cost computation, metric and the neighbour's link cost. Just like cost computation, metric
computation is considered a local policy matter; as far as Babel is computation is considered a local policy matter; as far as Babel is
concerned, the function M(c,&nbsp;m) used for computing a metric from concerned, the function M(c,&nbsp;m) used for computing a metric from
a locally computed link cost c and the metric m advertised by a neighbour a locally computed link cost c and the metric m advertised by a neighbour
MUST only satisfy the following conditions: <bcp14>MUST</bcp14> only satisfy the following conditions:
<list style="symbols"> </t>
<t>if c is infinite, then M(c, m) is infinite;</t> <ul spacing="normal">
<t>M is strictly monotonic: M(c, m) &gt; m.</t> <li>if c is infinite, then M(c, m) is infinite;</li>
</list> <li>M is strictly monotonic: M(c, m) &gt; m.</li>
Additionally, the metric SHOULD satisfy the following condition: </ul>
<list style="symbols"> <t>
<t>M is left-distributive: if m &le; m', then M(c, m) &le; M(c, m').</t> Additionally, the metric <bcp14>SHOULD</bcp14> satisfy the following condition:
</list> </t>
<ul spacing="normal">
<li>M is left-distributive: if m &lt;= m', then M(c, m) &lt;= M(c, m
').</li>
</ul>
<t>
While strict monotonicity is essential to the integrity of the network While strict monotonicity is essential to the integrity of the network
(persistent routing loops may arise if it is not satisfied), left (persistent routing loops may arise if it is not satisfied),
distributivity is not: if it is not satisfied, Babel will still converge left-distributivity is not: if it is not satisfied, Babel will still converge
to a loop-free configuration, but might not reach a global optimum (in to a loop-free configuration, but might not reach a global optimum (in
fact, a global optimum may not even exist).</t> fact, a global optimum may not even exist).</t>
<t>The conditions above are easily satisfied by using the additive met
<t>The conditions above are easily satisfied by using the additive metric, ric,
i.e., by defining M(c,&nbsp;m)&nbsp;= c&nbsp;+&nbsp;m. Since the additive i.e., by defining M(c,&nbsp;m)&nbsp;= c&nbsp;+&nbsp;m. Since the additive
metric is useful with a large range of cost computation strategies, it is metric is useful with a large range of cost computation strategies, it is
the RECOMMENDED default. See also <xref target="filtering"/>, which the <bcp14>RECOMMENDED</bcp14> default. See also <xref target="filtering" forma t="default"/>, which
describes a technique that makes it possible to tweak the values of describes a technique that makes it possible to tweak the values of
individual metrics without running the risk of creating routing loops.</t> individual metrics without running the risk of creating routing loops.</t>
</section>
</section> <section anchor="route-acquisition" numbered="true" toc="default">
<name>Route Acquisition</name>
<section title="Route Acquisition" anchor="route-acquisition"> <t>When a Babel node receives an update (prefix, plen, router-id, seqn
o,
<t>When a Babel node receives an update (prefix, plen, router-id, seqno,
metric) from a neighbour neigh, it checks whether it already has a route metric) from a neighbour neigh, it checks whether it already has a route
table entry indexed by (prefix, plen, neigh).</t> table entry indexed by (prefix, plen, neigh).</t>
<t>If no such entry exists:
<t>If no such entry exists: </t>
<list style="symbols"> <ul spacing="normal">
<t>if the update is unfeasible, it MAY be ignored;</t> <li>if the update is unfeasible, it <bcp14>MAY</bcp14> be ignored;</
<t>if the metric is infinite (the update is a retraction of a route we li>
do not know about), the update is ignored;</t> <li>if the metric is infinite (the update is a retraction of a route
<t>otherwise, a new entry is created in the route table, indexed by (prefix, we
do not know about), the update is ignored;</li>
<li>otherwise, a new entry is created in the route table, indexed by
(prefix,
plen, neigh), with source equal to (prefix, plen, router-id), seqno plen, neigh), with source equal to (prefix, plen, router-id), seqno
equal to seqno and an advertised metric equal to the metric carried by equal to seqno, and an advertised metric equal to the metric carried by
the update.</t> the update.</li>
</list> </ul>
<t>
If such an entry exists: If such an entry exists:
<list style="symbols"> </t>
<t>if the entry is currently selected, the update is unfeasible, and the <ul spacing="normal">
<li>if the entry is currently selected, the update is unfeasible, an
d the
router-id of the update is equal to the router-id of the entry, then the router-id of the update is equal to the router-id of the entry, then the
update MAY be ignored;</t> update <bcp14>MAY</bcp14> be ignored;</li>
<t>otherwise, the entry's sequence number, advertised metric, metric, <li>otherwise, the entry's sequence number, advertised metric, metri
and router-id are updated and, if the advertised metric is not infinite, c,
the route's expiry timer is reset to a small multiple of the Interval and router-id are updated, and if the advertised metric is not infinite,
value included in the update (see "Route Hold time" in the route's expiry timer is reset to a small multiple of the interval
<xref target="parameters"/> for suggested values). If the update is value included in the update (see "Route Expiry time" in
unfeasible, then the (now unfeasible) entry MUST be immediately <xref target="parameters" format="default"/> for suggested values). If the up
date is
unfeasible, then the (now unfeasible) entry <bcp14>MUST</bcp14> be immediately
unselected. If the update caused the router-id of the entry to change, unselected. If the update caused the router-id of the entry to change,
an update (possibly a retraction) MUST be sent in a timely manner as an update (possibly a retraction) <bcp14>MUST</bcp14> be sent in a timely mann
described in <xref target="triggered-updates"/>.</t> er as
</list> described in <xref target="triggered-updates" format="default"/>.</li>
</ul>
<t>
Note that the route table may contain unfeasible routes, either because Note that the route table may contain unfeasible routes, either because
they were created by an unfeasible update or due to a metric fluctuation. they were created by an unfeasible update or due to a metric fluctuation.
Such routes are never selected, since they are not known to be loop-free; Such routes are never selected, since they are not known to be loop-free.
should all the feasible routes become unusable, however, the unfeasible Should all the feasible routes become unusable, however, the unfeasible
routes can be made feasible and therefore possible to select by sending routes can be made feasible and therefore possible to select by sending
requests along them (see <xref target="sending-requests"/>).</t> requests along them (see <xref target="sending-requests" format="default"/>).</t
>
<t>When a route's expiry timer triggers, the behaviour depends on whether <t>When a route's expiry timer triggers, the behaviour depends on whet
her
the route's metric is finite. If the metric is finite, it is set to 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 already infinite, infinity and the expiry timer is reset. If the metric is already infinite,
the route is flushed from the route table.</t> the route is flushed from the route table.</t>
<t>After the route table is updated, the route selection procedure
<t>After the route table is updated, the route selection procedure (<xref target="route-selection" format="default"/>) is run.</t>
(<xref target="route-selection"/>) is run.</t> </section>
<section anchor="hold-time" numbered="true" toc="default">
</section> <name>Hold Time</name>
<t>When a prefix P is retracted (because all routes are unfeasible or
<section title="Hold Time" anchor="hold-time"> have
an infinite metric, whether due to the expiry timer or for other reasons),
<t>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 reasons),
and a shorter prefix P' that covers P is reachable, P' cannot in general and a shorter prefix P' that covers P is reachable, P' cannot in general
be used for routing packets destined to P without running the risk of be used for routing packets destined to P without running the risk of
creating a routing loop (<xref target="overlapping-prefixes"/>).</t> creating a routing loop (<xref target="overlapping-prefixes" format="default"/>)
.</t>
<t>To avoid this issue, whenever a prefix P is retracted, a route table <t>To avoid this issue, whenever a prefix P is retracted, a route tabl
entry with infinite metric is maintained as described in <xref e
target="route-acquisition"/> above. As long as this entry is maintained, entry with infinite metric is maintained as described in <xref target="route-acq
packets destined to an address within P MUST NOT be forwarded by following uisition" format="default"/>.
As long as this entry is maintained,
packets destined to an address within P <bcp14>MUST NOT</bcp14> 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 a finite-metric update for prefix P is received and the resulting route
selected. If no such update is forthcoming, the infinite metric entry selected. If no such update is forthcoming, the infinite metric entry
SHOULD be maintained at least until it is guaranteed that no neighbour has <bcp14>SHOULD</bcp14> be maintained at least until it is guaranteed that no neig
selected the current node as next-hop for prefix P. This can be achieved hbour has
selected the current node as next hop for prefix P. This can be achieved
by either: by either:
<list style="symbols"> </t>
<t>waiting until the route's expiry timer has expired (<xref <ul spacing="normal">
target="route-acquisition"/>);</t> <li>waiting until the route's expiry timer has expired
<t>sending a retraction with an acknowledgment request (<xref (<xref target="route-acquisition" format="default"/>); or</li>
target="acknowledgments"/>) to every reachable neighbour that has not <li>sending a retraction with an acknowledgment request (<xref targe
explicitly retracted prefix P, and waiting for all acknowledgments.</t> t="acknowledgments" format="default"/>) to every reachable neighbour that has no
</list> t
The former option is simpler and ensures that at that point, any routes explicitly retracted prefix P, and waiting for all acknowledgments.</li>
</ul>
<t>
The former option is simpler and ensures that, at that point, any routes
for prefix P pointing at the current node have expired. However, since for prefix P pointing at the current node have expired. However, since
the expiry time can be as high as a few minutes, doing that prevents the expiry time can be as high as a few minutes, doing that prevents
automatic aggregation by creating spurious black-holes for aggregated automatic aggregation by creating spurious black-holes for aggregated
routes. The latter option is RECOMMENDED as it dramatically reduces the routes. The latter option is <bcp14>RECOMMENDED</bcp14> as it dramatically redu ces the
time for which a prefix is unreachable in the presence of aggregated time for which a prefix is unreachable in the presence of aggregated
routes.</t> routes.</t>
</section>
</section> </section>
<section anchor="route-selection" numbered="true" toc="default">
</section> <name>Route Selection</name>
<t>Route selection is the process by which a single route for a given
<section title="Route Selection" anchor="route-selection">
<t>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 prefix is selected to be used for forwarding packets and to be
re-advertised to a node's neighbours.</t> re-advertised to a node's neighbours.</t>
<t>Babel is designed to allow flexible route selection policies. As far
<t>Babel is designed to allow flexible route selection policies. As far as as
the algorithm's correctness is concerned, the route selection policy MUST the algorithm's correctness is concerned, the route selection policy <bcp14>MU
ST</bcp14>
only satisfy the following properties: only satisfy the following properties:
<list style="symbols"> </t>
<t>a route with infinite metric (a retracted route) is never selected;</t> <ul spacing="normal">
<t>an unfeasible route is never selected.</t> <li>a route with infinite metric (a retracted route) is never selected
</list> ;</li>
<li>an unfeasible route is never selected.</li>
</ul>
<t>
Babel nodes using different route selection strategies will interoperate Babel nodes using different route selection strategies will interoperate
and not create routing loops as long as these two properties hold.</t> and will not create routing loops as long as these two properties hold.</t>
<t>Route selection <bcp14>MUST NOT</bcp14> take seqnos into account: a r
<t>Route selection MUST NOT take seqnos into account: a route MUST NOT be oute <bcp14>MUST NOT</bcp14> be
preferred just because it carries a higher (more recent) seqno. Doing preferred just because it carries a higher (more recent) seqno. Doing
otherwise would cause route oscillation while a new seqno propagates otherwise would cause route oscillation while a new seqno propagates
across the network, and might create persistent blackholes if the metric across the network, and might create persistent black-holes if the metric
being used is not left-distributive (<xref target="metric-computation"/>).</t> being used is not left-distributive (<xref target="metric-computation" format="d
efault"/>).</t>
<t>The obvious route selection strategy is to pick, for every destination, <t>The obvious route selection strategy is to pick, for every destinatio
n,
the feasible route with minimal metric. When all metrics are stable, this the feasible route with minimal metric. When all metrics are stable, this
approach ensures convergence to a tree of shortest paths (assuming that approach ensures convergence to a tree of shortest paths (assuming that
the metric is left-distributive, see <xref target="metric-computation"/>). the metric is left-distributive, see <xref target="metric-computation" format="d efault"/>).
There are two reasons, however, why this strategy may lead to instability There are two reasons, however, why this strategy may lead to instability
in the presence of continuously varying metrics. First, if two parallel in the presence of continuously varying metrics. First, if two parallel
routes oscillate around a common value, then the smallest metric strategy routes oscillate around a common value, then the smallest metric strategy
will keep switching between the two. Second, when a route is selected, will keep switching between the two.
congestion along it increases, which might increase packet loss, which in Second, the selection of a route increases congestion along it,
turn could cause its metric to increase; this is a feedback loop, of the which might increase packet loss, which in turn could
kind that is prone to causing persistent oscillations.</t> cause its metric to increase; this kind of feedback loop
is prone to causing persistent oscillations.</t>
<t>In order to limit these kinds of instabilities, a route selection <t>In order to limit these kinds of instabilities, a route selection
strategy SHOULD include some form of hysteresis, i.e., be sensitive to strategy <bcp14>SHOULD</bcp14> include some form of hysteresis, i.e., be sensiti
a route's history: if a route is currently selected, then the strategy ve to
should only switch to a different route if the latter has been a route's history:
consistently good for some period of time. A RECOMMENDED hysteresis the strategy should only switch from the currently selected route
algorithm is given in <xref target="route-selection-hysteresis"/>.</t> to a different route if the latter has been
consistently good for some period of time. A <bcp14>RECOMMENDED</bcp14> hystere
<t>After the route selection procedure is run, triggered updates sis
(<xref target="triggered-updates"/>) and requests algorithm is given in <xref target="route-selection-hysteresis" format="default"
(<xref target="sending-requests"/>) are sent.</t> />.</t>
<t>After the route selection procedure is run, triggered updates
</section> (<xref target="triggered-updates" format="default"/>) and requests
(<xref target="sending-requests" format="default"/>) are sent.</t>
<section title="Sending Updates" anchor="sending-updates"> </section>
<section anchor="sending-updates" numbered="true" toc="default">
<t>A Babel speaker advertises to its neighbours its set of selected <name>Sending Updates</name>
<t>A Babel speaker advertises to its neighbours its set of selected
routes. Normally, this is done by sending one or more multicast packets routes. Normally, this is done by sending one or more multicast packets
containing Update TLVs on all of its connected interfaces; however, on containing Update TLVs on all of its connected interfaces; however, on
link technologies where multicast is significantly more expensive than link technologies where multicast is significantly more expensive than
unicast, a node MAY choose to send multiple copies of updates in unicast unicast, a node <bcp14>MAY</bcp14> choose to send multiple copies of updates in unicast
packets, especially when the number of neighbours is small.</t> packets, especially when the number of neighbours is small.</t>
<t>Additionally, in order to ensure that any black-holes are reliably
<t>Additionally, in order to ensure that any black-holes are reliably
cleared in a timely manner, a Babel node may send retractions (updates cleared in a timely manner, a Babel node may send retractions (updates
with an infinite metric) for any recently retracted prefixes.</t> with an infinite metric) for any recently retracted prefixes.</t>
<t>If an update is for a route injected into the Babel domain by the loc
<t>If an update is for a route injected into the Babel domain by the local al
node (e.g., it carries the address of a local interface, the prefix of node (e.g., it carries the address of a local interface, the prefix of
a directly attached network, or a prefix redistributed from a different a directly attached network, or a prefix redistributed from a different
routing protocol), the router-id is set to the local node's router-id, the routing protocol), the router-id is set to the local node's router-id, the
metric is set to some arbitrary finite value (typically 0), and the seqno metric is set to some arbitrary finite value (typically 0), and the seqno
is set to the local router's sequence number.</t> is set to the local router's sequence number.</t>
<t>If an update is for a route learnt from another Babel speaker, the
<t>If an update is for a route learned from another Babel speaker, the
router-id and sequence number are copied from the route table entry, and router-id and sequence number are copied from the route table entry, and
the metric is computed as specified in <xref target="metric-computation"/>.</t> the metric is computed as specified in <xref target="metric-computation" format=
"default"/>.</t>
<section title="Periodic Updates" anchor="periodic-updates"> <section anchor="periodic-updates" numbered="true" toc="default">
<name>Periodic Updates</name>
<t>Every Babel speaker MUST advertise each of its selected routes on every <t>Every Babel speaker <bcp14>MUST</bcp14> advertise each of its selec
ted routes on every
interface, at least once every Update interval. Since Babel doesn't interface, at least once every Update interval. Since Babel doesn't
suffer from routing loops (there is no "counting to infinity") and relies suffer from routing loops (there is no "counting to infinity") and relies
heavily on triggered updates (<xref target="triggered-updates"/>), this heavily on triggered updates (<xref target="triggered-updates" format="default"/
full dump only needs to happen infrequently (see <xref target="parameters"/> >), this
full dump only needs to happen infrequently (see <xref target="parameters" forma
t="default"/>
for suggested intervals).</t> for suggested intervals).</t>
</section>
</section> <section anchor="triggered-updates" numbered="true" toc="default">
<name>Triggered Updates</name>
<section title="Triggered Updates" anchor="triggered-updates"> <t>In addition to periodic routing updates, a Babel speaker sends
<t>In addition to periodic routing updates, a Babel speaker sends
unscheduled, or triggered, updates in order to inform its neighbours of unscheduled, or triggered, updates in order to inform its neighbours of
a significant change in the network topology.</t> a significant change in the network topology.</t>
<t>A change of router-id for the selected route to a given prefix may
<t>A change of router-id for the selected route to a given prefix may be be
indicative of a routing loop in formation; hence, whenever it changes the indicative of a routing loop in formation; hence, whenever it changes the
selected router-id for a given destination, a node MUST send an update as selected router-id for a given destination, a node <bcp14>MUST</bcp14> send an u
an urgent TLV (as defined in <xref target="transmission-reception"/>). pdate as
Additionally, it SHOULD make a reasonable attempt at ensuring that all an urgent TLV (as defined in <xref target="transmission-reception" format="defau
lt"/>).
Additionally, it <bcp14>SHOULD</bcp14> make a reasonable attempt at ensuring tha
t all
reachable neighbours receive this update.</t> reachable neighbours receive this update.</t>
<t>There are two strategies for ensuring that. If the number of neigh
<t>There are two strategies for ensuring that. If the number of neighbours bours
is small, then it is reasonable to send the update together with an is small, then it is reasonable to send the update together with an
acknowledgment request; the update is resent until all neighbours have acknowledgment request; the update is resent until all neighbours have
acknowledged the packet, up to some number of times. If the number of acknowledged the packet, up to some number of times. If the number of
neighbours is large, however, requesting acknowledgments from all of them neighbours is large, however, requesting acknowledgments from all of them
might cause a non-negligible amount of network traffic; in that case, it might cause a non-negligible amount of network traffic; in that case, it
may be preferable to simply repeat the update some reasonable number of may be preferable to simply repeat the update some reasonable number of
times (say, 3 for wireless and 2 for wired links). The number of copies times (say, 3 for wireless and 2 for wired links). The number of copies
MUST NOT exceed 5, and the copies SHOULD be separated by a small delay, as <bcp14>MUST NOT</bcp14> exceed 5, and the copies <bcp14>SHOULD</bcp14> be separa
described in <xref target="transmission-reception"/>.</t> ted by a small delay, as
described in <xref target="transmission-reception" format="default"/>.</t>
<t>A route retraction is somewhat less worrying: if the route retraction <t>A route retraction is somewhat less worrying: if the route retracti
on
doesn't reach all neighbours, a black-hole might be created, which, unlike doesn't reach all neighbours, a black-hole might be created, which, unlike
a routing loop, does not endanger the integrity of the network. When a a routing loop, does not endanger the integrity of the network. When a
route is retracted, a node SHOULD send a triggered update and SHOULD make route is retracted, a node <bcp14>SHOULD</bcp14> send a triggered update and <bc p14>SHOULD</bcp14> make
a reasonable attempt at ensuring that all neighbours receive this a reasonable attempt at ensuring that all neighbours receive this
retraction.</t> retraction.</t>
<t>Finally, a node <bcp14>MAY</bcp14> send a triggered update when the
<t>Finally, a node MAY send a triggered update when the metric for a given metric for a given
prefix changes in a significant manner, due to a received update, because prefix changes in a significant manner, due to a received update, because
a link's cost has changed, or because a different next hop has been a link's cost has changed or because a different next hop has been
selected. A node SHOULD NOT send triggered updates for other reasons, selected. A node <bcp14>SHOULD NOT</bcp14> send triggered updates for other rea
sons,
such as when there is a minor fluctuation in a route's metric, when the such as when there is a minor fluctuation in a route's metric, when the
selected next hop changes without inducing a significant change to the selected next hop changes without inducing a significant change to the
route's metric, or to propagate a new sequence number (except to satisfy route's metric, or to propagate a new sequence number (except to satisfy
a request, as specified in <xref target="requests"/>).</t> a request, as specified in <xref target="requests" format="default"/>).</t>
</section>
</section> <section anchor="maintaining-fd" numbered="true" toc="default">
<name>Maintaining Feasibility Distances</name>
<section title="Maintaining Feasibility Distances" anchor="maintaining-fd"> <t>Before sending an update (prefix, plen, router-id, seqno, metric) w
ith
<t>Before sending an update (prefix, plen, router-id, seqno, metric) with
finite metric (i.e., not a route retraction), a Babel node updates the finite metric (i.e., not a route retraction), a Babel node updates the
feasibility distance maintained in the source table. This is done as feasibility distance maintained in the source table. This is done as
follows.</t> follows.</t>
<t>If no entry indexed by (prefix, plen, router-id) exists in the sour
<t>If no entry indexed by (prefix, plen, router-id) exists in the source ce
table, then one is created with value (prefix, plen, router-id, seqno, table, then one is created with value (prefix, plen, router-id, seqno,
metric).</t> metric).</t>
<t>If an entry (prefix, plen, router-id, seqno', metric') exists, then
<t>If an entry (prefix, plen, router-id, seqno', metric') exists, then it it
is updated as follows: is updated as follows:
<list style="symbols"> </t>
<t>if seqno &gt; seqno', then seqno' := seqno, metric' := metric;</t> <ul spacing="normal">
<t>if seqno = seqno' and metric' &gt; metric, then metric' := metric;</t> <li>if seqno &gt; seqno', then seqno' := seqno, metric' := metric;</
<t>otherwise, nothing needs to be done.</t> li>
</list></t> <li>if seqno = seqno' and metric' &gt; metric, then metric' := metri
c;</li>
<t>The garbage-collection timer for the entry is then reset. Note that <li>otherwise, nothing needs to be done.</li>
</ul>
<t>The garbage-collection timer for the entry is then reset. Note tha
t
the feasibility distance is not updated and the garbage-collection timer the feasibility distance is not updated and the garbage-collection timer
is not reset when a retraction (an update with infinite metric) is is not reset when a retraction (an update with infinite metric) is
sent.</t> sent.</t>
<t>When the garbage-collection timer expires, the entry is removed fro
<t>When the garbage-collection timer expires, the entry is removed from m
the source table.</t> the source table.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Split Horizon</name>
<section title="Split Horizon"> <t>When running over a transitive, symmetric link technology, e.g.,
<t>When running over a transitive, symmetric link technology, e.g.,
a point-to-point link or a wired LAN technology such as Ethernet, a Babel 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 split node <bcp14>SHOULD</bcp14> use an optimisation known as split horizon. When spl it
horizon is used on a given interface, a routing update for prefix P is not horizon is used on a given interface, a routing update for prefix P is not
sent on the particular interface over which the selected route towards sent on the particular interface over which the selected route towards
prefix P was learnt.</t> prefix P was learnt.</t>
<t>Split horizon <bcp14>SHOULD NOT</bcp14> be applied to an interface
<t>Split horizon SHOULD NOT be applied to an interface unless the interface unless the interface
is known to be symmetric and transitive; in particular, split horizon is is known to be symmetric and transitive; in particular, split horizon is
not applicable to decentralised wireless link technologies not applicable to decentralised wireless link technologies
(e.g., IEEE 802.11 in ad hoc mode) when routing updates are sent over (e.g., IEEE 802.11 in ad hoc mode) when routing updates are sent over
multicast.</t> multicast.</t>
</section>
</section> </section>
<section anchor="requests" numbered="true" toc="default">
</section> <name>Explicit Requests</name>
<t>In normal operation, a node's route table is populated by the regular
<section title="Explicit Requests" anchor="requests">
<t>In normal operation, a node's route table is populated by the regular
and triggered updates sent by its neighbours. Under some circumstances, and triggered updates sent by its neighbours. Under some circumstances,
however, a node sends explicit requests in order to cause a resynchronisation however, a node sends explicit requests in order to cause a resynchronisation
with the source after a mobility event or to prevent a route from with the source after a mobility event or to prevent a route from
spuriously expiring.</t> spuriously expiring.</t>
<t>The Babel protocol provides two kinds of explicit requests: route
<t>The Babel protocol provides two kinds of explicit requests: route
requests, which simply request an update for a given prefix, and seqno requests, which simply request an update for a given prefix, and seqno
requests, which request an update for a given prefix with a specific requests, which request an update for a given prefix with a specific
sequence number. The former are never forwarded; the latter are forwarded sequence number. The former are never forwarded; the latter are forwarded
if they cannot be satisfied by the receiver.</t> if they cannot be satisfied by the receiver.</t>
<section anchor="handling-requests" numbered="true" toc="default">
<section title="Handling Requests" anchor="handling-requests"> <name>Handling Requests</name>
<t>Upon receiving a request, a node either forwards the request or sen
<t>Upon receiving a request, a node either forwards the request or sends an ds an
update in reply to the request, as described in the following sections. If update in reply to the request, as described in the following sections. If
this causes an update to be sent, the update is either sent to a multicast this causes an update to be sent, the update is either sent to a multicast
address on the interface on which the request was received, or to the address on the interface on which the request was received, or to the
unicast address of the neighbour that sent the request.</t> unicast address of the neighbour that sent the request.</t>
<t>The exact behaviour is different for route requests and seqno reque
<t>The exact behaviour is different for route requests and seqno requests.</t> sts.</t>
<section anchor="handling-route-requests" numbered="true" toc="default
<section title="Route Requests" anchor="handling-route-requests"> ">
<name>Route Requests</name>
<t>When a node receives a route request for a given prefix, it checks its <t>When a node receives a route request for a given prefix, it check
s its
route table for a selected route to this exact prefix. If such a route route table for a selected route to this exact prefix. If such a route
exists, it MUST send an update (over unicast or over multicast); if such exists, it <bcp14>MUST</bcp14> send an update (over unicast or over multicast);
a route does not exist, it MUST send a retraction for that prefix.</t> if such
a route does not exist, it <bcp14>MUST</bcp14> send a retraction for that prefix
<t>When a node receives a wildcard route request, it SHOULD send a full .</t>
route table dump. Full route dumps SHOULD be rate-limited, especially if <t>When a node receives a wildcard route request, it <bcp14>SHOULD</
bcp14> send a full
route table dump. Full route dumps <bcp14>SHOULD</bcp14> be rate-limited, espec
ially if
they are sent over multicast.</t> they are sent over multicast.</t>
</section>
</section> <section anchor="handling-seqno-requests" numbered="true" toc="default
">
<section title="Seqno Requests" anchor="handling-seqno-requests"> <name>Seqno Requests</name>
<t>When a node receives a seqno request for a given router-id and se
<t>When a node receives a seqno request for a given router-id and sequence quence
number, it checks whether its route table contains a selected entry for number, it checks whether its route table contains a selected entry for
that prefix. If a selected route for the given prefix exists, it has that prefix. If a selected route for the given prefix exists and has
finite metric, and either the router-ids are different or the router-ids finite metric, and either the router-ids are different or the router-ids
are equal and the entry's sequence number is no smaller (modulo 2^16) than are equal and the entry's sequence number is no smaller (modulo 2<sup>16</sup>)
the requested sequence number, the node MUST send an update for the given than
prefix. If the router-ids match but the requested seqno is larger (modulo the requested sequence number, the node <bcp14>MUST</bcp14> send an update for t
2^16) than the route entry's, the node compares the router-id against its he given
prefix. If the router-ids match, but the requested seqno is larger (modulo
2<sup>16</sup>) than the route entry's, the node compares the router-id against
its
own router-id. If the router-id is its own, then it increases its own router-id. If the router-id is its own, then it increases its
sequence number by 1 (modulo 2^16) and sends an update. A node MUST NOT sequence number by 1 (modulo 2<sup>16</sup>) and sends an update. A node <bcp14 >MUST NOT</bcp14>
increase its sequence number by more than 1 in reaction to a single seqno increase its sequence number by more than 1 in reaction to a single seqno
request.</t> request.</t>
<t>Otherwise, if the requested router-id is not its own, the receive
<t>Otherwise, if the requested router-id is not its own, the received node d node
consults the hop count field of the request. If the hop count is 2 or consults the Hop Count field of the request. If the hop count is 2 or
more, and the node is advertising the prefix to its neighbours, the node more, and the node is advertising the prefix to its neighbours, the node
selects a neighbour to forward the request to as follows: selects a neighbour to forward the request to as follows:
<list style="symbols"> </t>
<t>if the node has one or more feasible routes toward the requested prefix <ul spacing="normal">
with a next hop that is not the requesting node, then the node MUST <li>if the node has one or more feasible routes towards the reques
forward the request to the next hop of one such route;</t> ted prefix
<t>otherwise, if the node has one or more (not feasible) routes to the with a next hop that is not the requesting node, then the node <bcp14>MUST</bcp1
4>
forward the request to the next hop of one such route;</li>
<li>otherwise, if the node has one or more (not feasible) routes t
o the
requested prefix with a next hop that is not the requesting node, then 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.</t> node <bcp14>SHOULD</bcp14> forward the request to the next hop of one such route
</list> .</li>
</ul>
<t>
In order to actually forward the request, the node decrements the hop 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 count and sends the request in a unicast packet destined to the selected
neighbour. The forwarded request SHOULD be sent as an urgent TLV (as neighbour. The forwarded request <bcp14>SHOULD</bcp14> be sent as an urgent TLV
defined in <xref target="transmission-reception"/>).</t> (as
defined in <xref target="transmission-reception" format="default"/>).</t>
<t>A node SHOULD maintain a list of recently forwarded seqno requests and <t>A node <bcp14>SHOULD</bcp14> maintain a list of recently forwarde
d seqno requests and
forward the reply (an update with a seqno sufficiently large to satisfy forward the reply (an update with a seqno sufficiently large to satisfy
the request) as an urgent TLV (as defined in the request) as an urgent TLV (as defined in
<xref target="transmission-reception"/>). A node SHOULD compare every <xref target="transmission-reception" format="default"/>). A node <bcp14>SHOULD </bcp14> compare every
incoming seqno request against its list of recently forwarded seqno incoming seqno request against its list of recently forwarded seqno
requests and avoid forwarding it if it is redundant (i.e., if it has requests and avoid forwarding the request if it is redundant (i.e., if the node
recently sent a request with the same prefix, router-id and a seqno that has
is not smaller modulo 2^16).</t> recently sent a request with the same prefix, router-id, and a seqno that
is not smaller modulo 2<sup>16</sup>).</t>
<t>Since the request-forwarding mechanism does not necessarily obey the <t>Since the request-forwarding mechanism does not necessarily obey
the
feasibility condition, it may get caught in routing loops; hence, requests feasibility condition, it may get caught in routing loops; hence, requests
carry a hop count to limit the time during which they remain in the network. carry a hop count to limit the time during which they remain in the network.
However, since requests are only ever forwarded as unicast packets, the However, since requests are only ever forwarded as unicast packets, the
initial hop count need not be kept particularly low, and performing an initial hop count need not be kept particularly low, and performing an
expanding horizon search is not necessary. A single request MUST NOT be expanding horizon search is not necessary. A single request <bcp14>MUST NOT</bc
duplicated: it MUST NOT be forwarded to a multicast address, and it MUST p14> be
NOT be forwarded to multiple neighbours. However, if a seqno request is duplicated: it <bcp14>MUST NOT</bcp14> be forwarded to a multicast address, and
it <bcp14>MUST
NOT</bcp14> be forwarded to multiple neighbours. However, if a seqno request is
resent by its originator, the subsequent copies may be forwarded to resent by its originator, the subsequent copies may be forwarded to
a different neighbour than the initial one.</t> a different neighbour than the initial one.</t>
</section>
</section> </section>
<section anchor="sending-requests" numbered="true" toc="default">
</section> <name>Sending Requests</name>
<t>A Babel node <bcp14>MAY</bcp14> send a route or seqno request at an
<section title="Sending Requests" anchor="sending-requests"> y time to a
<t>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 originating multicast or a unicast address; there is only one case when originating
requests is required (<xref target="avoiding-starvation"/>).</t> requests is required (<xref target="avoiding-starvation" format="default"/>).</t
>
<section title="Avoiding Starvation" anchor="avoiding-starvation"> <section anchor="avoiding-starvation" numbered="true" toc="default">
<name>Avoiding Starvation</name>
<t>When a route is retracted or expires, a Babel node usually switches to <t>When a route is retracted or expires, a Babel node usually switch
es to
another feasible route for the same prefix. It may be the case, however, another feasible route for the same prefix. It may be the case, however,
that no such routes are available.</t> that no such routes are available.</t>
<t>A node that has lost all feasible routes to a given destination b
<t>A node that has lost all feasible routes to a given destination but ut
still has unexpired unfeasible routes to that destination MUST send still has unexpired unfeasible routes to that destination <bcp14>MUST</bcp14> se
a seqno request; if it doesn't have any such routes, it MAY still send nd
a seqno request; if it doesn't have any such routes, it <bcp14>MAY</bcp14> still
send
a seqno request. The router-id of the request is set to the router-id of a seqno request. The router-id of the request is set to the router-id of
the route that it has just lost, and the requested seqno is the value the route that it has just lost, and the requested seqno is the value
contained in the source table plus 1. The request carries a hop count, contained in the source table plus 1. The request carries a hop count,
which is used as a last-resort mechanism to ensure that it eventually which is used as a last-resort mechanism to ensure that it eventually
vanishes from the network; it MAY be set to any value that is larger than vanishes from the network; it <bcp14>MAY</bcp14> be set to any value that is lar ger than
the diameter of the network (64 is a suitable default value).</t> the diameter of the network (64 is a suitable default value).</t>
<t>If the node has any (unfeasible) routes to the requested destinat
<t>If the node has any (unfeasible) routes to the requested destination, ion,
then it MUST send the request to at least one of the next-hop neighbours then it <bcp14>MUST</bcp14> send the request to at least one of the next-hop nei
that advertised these routes, and SHOULD send it to all of them; in any ghbours
case, it MAY send the request to any other neighbours, whether they that advertised these routes, and <bcp14>SHOULD</bcp14> send it to all of them;
in any
case, it <bcp14>MAY</bcp14> send the request to any other neighbours, whether th
ey
advertise a route to the requested destination or not. A simple advertise a route to the requested destination or not. A simple
implementation strategy is therefore to unconditionally multicast the implementation strategy is therefore to unconditionally multicast the
request over all interfaces.</t> request over all interfaces.</t>
<t>Similar requests will be sent by other nodes that are affected by
<t>Similar requests will be sent by other nodes that are affected by the the
route's loss. If the network is still connected, and assuming no packet 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 the source, loss, then at least one of these requests will be forwarded to the source,
resulting in a route being advertised with a new sequence number. (Due to resulting in a route being advertised with a new sequence number. (Due to
duplicate suppression, only a small number of such requests are expected duplicate suppression, only a small number of such requests are expected
to actually reach the source.)</t> to actually reach the source.)</t>
<t>In order to compensate for packet loss, a node <bcp14>SHOULD</bcp
<t>In order to compensate for packet loss, a node SHOULD repeat such 14> 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 (see "Request Timeout" in <xref target="parameters"/> for a short time (see "Request timeout" in <xref target="parameters" format="default "/> for
suggested values). In the presence of heavy packet loss, however, all suggested values). In the presence of heavy packet loss, however, all
such requests might be lost; in that case, the mechanism in the next such requests might be lost; in that case, the mechanism in the next
section will eventually ensure that a new seqno is received.</t> section will eventually ensure that a new seqno is received.</t>
</section>
</section> <section anchor="request-unfeasible" numbered="true" toc="default">
<name>Dealing with Unfeasible Updates</name>
<section title="Dealing with Unfeasible Updates" anchor="request-unfeasible"> <t>When a route's metric increases, a node might receive an unfeasib
le
<t>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
<xref target="feasibility-condition"/>, the receiving node will either <xref target="feasibility-condition" format="default"/>, the receiving node will either
ignore the update or unselect the route.</t> ignore the update or unselect the route.</t>
<t>In order to keep routes from spuriously expiring because they hav
<t>In order to keep routes from spuriously expiring because they have e
become unfeasible, a node SHOULD send a unicast seqno request when it become unfeasible, a node <bcp14>SHOULD</bcp14> send a unicast seqno request whe
n it
receives an unfeasible update for a route that is currently selected. The receives an unfeasible update for a route that is currently selected. The
requested sequence number is computed from the source table as in <xref requested sequence number is computed from the source table as in <xref target="
target="avoiding-starvation"/> above.</t> avoiding-starvation" format="default"/>.</t>
<t>Additionally, since metric computation does not necessarily coinc
<t>Additionally, since metric computation does not necessarily coincide ide
with the delay in propagating updates, a node might receive an unfeasible with the delay in propagating updates, a node might receive an unfeasible
update from a currently unselected neighbour that is preferable to the update from a currently unselected neighbour that is preferable to the
currently selected route (e.g., because it has a much smaller metric); in currently selected route (e.g., because it has a much smaller metric); in
that case, the node SHOULD send a unicast seqno request to the neighbour that case, the node <bcp14>SHOULD</bcp14> send a unicast seqno request to the ne ighbour
that advertised the preferable update.</t> that advertised the preferable update.</t>
</section>
</section> <section anchor="request-expiring" numbered="true" toc="default">
<name>Preventing Routes from Expiring</name>
<section title="Preventing Routes from Expiring" anchor="request-expiring"> <t>In normal operation, a route's expiry timer never triggers: since
<t>In normal operation, a route's expiry timer never triggers: since
a route's hold time is computed from an explicit interval included in a route's hold time is computed from an explicit interval included in
Update TLVs, a new update (possibly a retraction) should arrive in time to Update TLVs, a new update (possibly a retraction) should arrive in time to
prevent a route from expiring.</t> prevent a route from expiring.</t>
<t>In the presence of packet loss, however, it may be the case that
<t>In the presence of packet loss, however, it may be the case that no no
update is successfully received for an extended period of time, causing update is successfully received for an extended period of time, causing
a route to expire. In order to avoid such spurious expiry, shortly before a route to expire. In order to avoid such spurious expiry, shortly before
a selected route expires, a Babel node SHOULD send a unicast route request a selected route expires, a Babel node <bcp14>SHOULD</bcp14> send a unicast rout e request
to the neighbour that advertised this route; since nodes always send to the neighbour that advertised this route; since nodes always send
either updates or retractions in response to non-wildcard route requests either updates or retractions in response to non-wildcard route requests
(<xref target="handling-route-requests"/>), this will usually result in (<xref target="handling-route-requests" format="default"/>), this will usually r esult in
the route being either refreshed or retracted.</t> the route being either refreshed or retracted.</t>
</section>
</section> </section>
</section>
</section> </section>
<section anchor="protocol-encoding" numbered="true" toc="default">
</section> <name>Protocol Encoding</name>
<t>A Babel packet <bcp14>MUST</bcp14> be sent as the body of a UDP datagra
</section> m, with
<section title="Protocol Encoding" anchor="protocol-encoding">
<t>A Babel packet MUST be sent as the body of a UDP datagram, with
network-layer hop count set to 1, destined to a well-known multicast network-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, address 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 port 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 silently are set to a well-known port number. A Babel packet <bcp14>MUST</bcp14> be sile ntly
ignored unless its source address is either a link-local IPv6 address or ignored unless its source address is either a link-local IPv6 address or
an IPv4 address belonging to the local network, and its source port is the an IPv4 address belonging to the local network, and its source port is the
well-known Babel port. It MAY be silently ignored if its destination well-known Babel port. It <bcp14>MAY</bcp14> be silently ignored if its destina tion
address is a global IPv6 address.</t> address is a global IPv6 address.</t>
<t>In order to minimise the number of packets being sent while avoiding
<t>In order to minimise the number of packets being sent while avoiding lower-layer fragmentation, a Babel node <bcp14>SHOULD</bcp14> maximise the size
lower-layer fragmentation, a Babel node SHOULD maximise the size of the of the
packets it sends, up to the outgoing interface's MTU adjusted for packets it sends, up to the outgoing interface's MTU adjusted for
lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP over lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP over
IPv6). It MUST NOT send packets larger than the attached interface's MTU IPv6). It <bcp14>MUST NOT</bcp14> send packets larger than the attached interfa ce's MTU
adjusted for lower-layer headers or 512 octets, whichever is larger, but adjusted for lower-layer headers or 512 octets, whichever is larger, but
not exceeding 2^16 - 1 adjusted for lower-layer headers. Every Babel not exceeding 2<sup>16</sup> - 1 adjusted for lower-layer headers. Every Babel
speaker MUST be able to receive packets that are as large as any attached speaker <bcp14>MUST</bcp14> be able to receive packets that are as large as any
attached
interface's MTU adjusted for lower-layer headers or 512 octets, whichever interface's MTU adjusted for lower-layer headers or 512 octets, whichever
is larger. Babel packets MUST NOT be sent in IPv6 Jumbograms is larger. Babel packets <bcp14>MUST NOT</bcp14> be sent in IPv6 jumbograms
<xref target="RFC2675"/>.</t> <xref target="RFC2675" format="default"/>.</t>
<section numbered="true" toc="default">
<section title="Data Types"> <name>Data Types</name>
<section numbered="true" toc="default">
<section title="Representation of integers"> <name>Representation of Integers</name>
<t>All multi-octet fields that represent integers are encoded with the
<t>All multi-octet fields that represent integers are encoded with the most significant octet first (in Big-Endian format <xref target="IEN137" format=
most significant octet first (in Big-Endian format <xref target="IEN137"/>, "default"/>,
also called Network Order). The base protocol only carries unsigned also called network order). The base protocol only carries unsigned
values; if an extension needs to carry signed values, it will need to values; if an extension needs to carry signed values, it will need to
specify their encoding (e.g., two's complement).</t> specify their encoding (e.g., two's complement).</t>
</section>
</section> <section numbered="true" toc="default">
<name>Interval</name>
<section title="Interval"> <t>Relative times are carried as 16-bit values specifying a number of
<t>Relative times are carried as 16-bit values specifying a number of
centiseconds (hundredths of a second). This allows times up to roughly 11 centiseconds (hundredths of a second). This allows times up to roughly 11
minutes with a granularity of 10ms, which should cover all reasonable minutes with a granularity of 10 ms, which should cover all reasonable
applications of Babel (see also <xref target="parameters"/>).</t> applications of Babel (see also <xref target="parameters" format="default"/>).</
</section> t>
</section>
<section title="Router-Id" anchor="router-id-def"> <section anchor="router-id-def" numbered="true" toc="default">
<t>A router-id is an arbitrary 8-octet value. A router-id MUST NOT <name>Router-Id</name>
<t>A router-id is an arbitrary 8-octet value. A router-id <bcp14>MUST
NOT</bcp14>
consist of either all binary zeroes (0000000000000000 hexadecimal) or all consist of either all binary zeroes (0000000000000000 hexadecimal) or all
binary ones (FFFFFFFFFFFFFFFF hexadecimal).</t> binary ones (FFFFFFFFFFFFFFFF hexadecimal).</t>
</section> </section>
<section numbered="true" toc="default">
<section title="Address"> <name>Address</name>
<t>Since the bulk of the protocol is taken by addresses, multiple ways
<t>Since the bulk of the protocol is taken by addresses, multiple ways of of
encoding addresses are defined. Additionally, within Update TLVs a common encoding addresses are defined. Additionally, within Update TLVs a common
subnet prefix may be omitted when multiple addresses are sent in a single subnet prefix may be omitted when multiple addresses are sent in a single
packet &mdash; this is known as address compression (<xref packet -- this is known as address compression (<xref target="update" format="de
target="update"/>).</t> fault"/>).</t>
<t>Address encodings (AEs):
<t>Address encodings:
<list style="symbols">
<t>AE 0: wildcard address. The value is 0 octets long.</t>
<t>AE 1: IPv4 address. Compression is allowed. 4 octets or less.</t>
<t>AE 2: IPv6 address. Compression is allowed. 16 octets or less.</t>
<t>AE 3: link-local IPv6 address. Compression is not allowed. The value
is 8 octets long, a prefix of fe80::/64 is implied.</t>
</list>
</t> </t>
<dl spacing="normal" indent="10">
<t>The address family associated to an address encoding is either IPv4 or <dt>AE 0:</dt><dd>Wildcard address. The value is 0 octets long.</dd
IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 and >
<dt>AE 1:</dt><dd>IPv4 address. Compression is allowed. 4 octets o
r less.</dd>
<dt>AE 2:</dt><dd>IPv6 address. Compression is allowed. 16 octets
or less.</dd>
<dt>AE 3:</dt><dd>Link-local IPv6 address. Compression is not allow
ed. The value
is 8 octets long, a prefix of fe80::/64 is implied.</dd>
</dl>
<t>The address family associated with an address encoding is either IP
v4 or
IPv6: it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 and
3.</t> 3.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Prefixes</name>
<section title="Prefixes"> <t>A network prefix is encoded just like a network address, but it is
<t>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).</t> significant bits (up to the prefix length).</t>
</section> </section>
</section> </section>
<section anchor="packet-format" numbered="true" toc="default">
<section title="Packet Format" anchor="packet-format"> <name>Packet Format</name>
<t>A Babel packet consists of a 4-octet header, followed by a sequence o
<t>A Babel packet consists of a 4-octet header, followed by a sequence of f
TLVs (the packet body), optionally followed by a second sequence of TLVs TLVs (the packet body), optionally followed by a second sequence of TLVs
(the packet trailer). The format is designed to be extensible; see (the packet trailer). The format is designed to be extensible; see
<xref target="extensions"/> for extensibility considerations.</t> <xref target="extensions" format="default"/> for extensibility considerations.</
t>
<figure><artwork><![CDATA[ <artwork name="" type="" align="left" alt=""><![CDATA[
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Magic | Version | Body length | | Magic | Version | Body length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Body ... | Packet Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Packet Trailer... | Packet Trailer...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>Fields :
<list style="hanging" hangIndent="10">
<t hangText="Magic">The arbitrary but carefully chosen value 42 (decimal);
packets with a first octet different from 42 MUST be silently ignored.</t>
<t hangText="Version">This document specifies version 2 of the Babel
protocol. Packets with a second octet different from 2 MUST be silently
ignored.</t>
<t hangText="Body length">The length in octets of the body following the
packet header (excluding the Magic, Version and Body length fields, and
excluding the packet trailer).</t>
<t hangText="Packet Body">The packet body; a sequence of TLVs.</t>
<t hangText="Packet Trailer">The packet trailer; another sequence of TLVs.</t>
</list></t>
<t>The packet body and trailer are both sequences of TLVs. The packet <t>Fields:
</t>
<dl newline="false" spacing="normal" indent="10">
<dt>Magic</dt>
<dd>The arbitrary but carefully chosen value 42 (decimal);
packets with a first octet different from 42 <bcp14>MUST</bcp14> be silently ign
ored.</dd>
<dt>Version</dt>
<dd>This document specifies version 2 of the Babel
protocol. Packets with a second octet different from 2 <bcp14>MUST</bcp14> be
silently
ignored.</dd>
<dt>Body length</dt>
<dd>The length in octets of the body following the
packet header (excluding the Magic, Version, and Body length fields, and
excluding the packet trailer).</dd>
<dt>Packet Body</dt>
<dd>The packet body; a sequence of TLVs.</dd>
<dt>Packet Trailer</dt>
<dd>The packet trailer; another sequence of TLVs.</dd>
</dl>
<t>The packet body and trailer are both sequences of TLVs. The packet
body is the normal place to store TLVs; the packet trailer only contains body is the normal place to store TLVs; the packet trailer only contains
specialised TLVs that do not need to be protected by cryptographic specialised TLVs that do not need to be protected by cryptographic
security mechanisms. When parsing the trailer, the receiver MUST ignore security mechanisms. When parsing the trailer, the receiver <bcp14>MUST</bcp14> ignore
any TLV unless its definition explicitly states that it is allowed to any TLV unless its definition explicitly states that it is allowed to
appear there. Among the TLVs defined in this document, only Pad1 and PadN appear there. Among the TLVs defined in this document, only Pad1 and PadN
are allowed in the trailer; since these TLVs are ignored in any case, an are allowed in the trailer; since these TLVs are ignored in any case, an
implementation MAY silently ignore the packet trailer without even parsing implementation <bcp14>MAY</bcp14> silently ignore the packet trailer without eve n parsing
it, unless it implements at least one protocol extension that defines TLVs it, unless it implements at least one protocol extension that defines TLVs
that are allowed to appear in the trailer.</t> that are allowed to appear in the trailer.</t>
</section>
</section> <section numbered="true" toc="default">
<name>TLV Format</name>
<section title="TLV Format"> <t>With the exception of Pad1, all TLVs have the following structure:</t
>
<t>With the exception of Pad1, all TLVs have the following structure:</t> <artwork name="" type="" align="left" alt=""><![CDATA[
<figure><artwork><![CDATA[
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 | Payload... | Type | Length | Payload...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">The type of the TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>The type of the TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="Payload">The TLV payload, which consists of a body and, for <dd>The length of the body in octets, exclusive of the
selected TLV types, an optional list of sub-TLVs.</t> Type and Length fields.</dd>
</list></t> <dt>Payload</dt>
<dd>The TLV payload, which consists of a body and, for
<t>TLVs with an unknown type value MUST be silently ignored.</t> selected TLV types, an optional list of sub-TLVs.</dd>
</dl>
</section> <t>TLVs with an unknown type value <bcp14>MUST</bcp14> be silently ignor
ed.</t>
<section title="Sub-TLV Format" anchor="sub-tlv-format"> </section>
<section anchor="sub-tlv-format" numbered="true" toc="default">
<t>Every TLV carries an explicit length in its header; however, most TLVs <name>Sub-TLV Format</name>
<t>Every TLV carries an explicit length in its header; however, most TLV
s
are self-terminating, in the sense that it is possible to determine the are self-terminating, in the sense that it is possible to determine the
length of the body without reference to the explicit Length field. If length of the body without reference to the explicit Length field. If
a TLV has a self-terminating format, then the space between the natural a TLV has a self-terminating format, then the space between the natural
size of the TLV and the size announced in the Length field may be used to size of the TLV and the size announced in the Length field may be used to
store a sequence of sub-TLVs.</t> store a sequence of sub-TLVs.</t>
<t>Sub-TLVs have the same structure as TLVs. With the exception of Pad1
<t>Sub-TLVs have the same structure as TLVs. With the exception of Pad1, ,
all TLVs have the following structure:</t> all TLVs have the following structure:</t>
<figure><artwork><![CDATA[ <artwork name="" type="" align="left" alt=""><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">The type of the sub-TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>The type of the sub-TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="Body">The sub-TLV body, the interpretation of which depends <dd>The length of the body in octets, exclusive of the
Type and Length fields.</dd>
<dt>Body</dt>
<dd>The sub-TLV body, the interpretation of which depends
on both the type of the sub-TLV and the type of the TLV within which it is on both the type of the sub-TLV and the type of the TLV within which it is
embedded.</t> embedded.</dd>
</list></t> </dl>
<t>The most significant bit of the sub-TLV type (the bit with value 80
<t>The most-significant bit of the sub-TLV type (the bit with value 80
hexadecimal), is called the mandatory bit; in other words, sub-TLV types hexadecimal), is called the mandatory bit; in other words, sub-TLV types
128 through 255 have the mandatory bit set. This bit indicates how to 128 through 255 have the mandatory bit set. This bit indicates how to
handle unknown sub-TLVs. If the mandatory bit is not set, then an unknown handle unknown sub-TLVs. If the mandatory bit is not set, then an unknown
sub-TLV MUST be silently ignored, and the rest of the TLV is processed sub-TLV <bcp14>MUST</bcp14> be silently ignored, and the rest of the TLV is proc
normally. If the mandatory bit is set, then the whole enclosing TLV MUST essed
normally. If the mandatory bit is set, then the whole enclosing TLV <bcp14>MUST
</bcp14>
be silently ignored (except for updating the parser state by a Router-Id, be silently ignored (except for updating the parser state by a Router-Id,
Next-Hop or Update TLV, as described in the next section).</t> Next Hop, or Update TLV, as described in the next section).</t>
</section>
</section> <section anchor="parser-state" numbered="true" toc="default">
<name>Parser State and Encoding of Updates</name>
<section title="Parser state and encoding of updates" anchor="parser-state"> <t>In a large network, the bulk of Babel traffic consists of route
<t>In a large network, the bulk of Babel traffic consists of route
updates; hence, some care has been given to encoding them efficiently. updates; hence, some care has been given to encoding them efficiently.
The data conceptually contained in an update (<xref target="route-maintenance"/> ) The data conceptually contained in an update (<xref target="route-maintenance" f ormat="default"/>)
is split into three pieces: is split into three pieces:
<list style="symbols"> </t>
<t>the prefix, seqno and metric are contained in the Update TLV itself <ul spacing="normal">
(<xref target="update"/>);</t> <li>the prefix, seqno, and metric are contained in the Update TLV itse
<t>the router-id is taken from Router-Id TLV that precedes the Update TLV, lf
and may be shared among multiple Update TLVs (<xref target="router-id"/>);</t> (<xref target="update" format="default"/>);</li>
<t>the next hop is taken either from the source-address of the <li>the router-id is taken from the Router-Id TLV that precedes the Up
network-layer packet that contains the Babel packet, or from an explicit date TLV
Next-Hop TLV (<xref target="next-hop"/>).</t> and may be shared among multiple Update TLVs (<xref target="router-id" format="d
</list> efault"/>);</li>
<li>the next hop is taken either from the source address of the
network-layer packet that contains the Babel packet or from an explicit
Next Hop TLV (<xref target="next-hop" format="default"/>).</li>
</ul>
<t>
In addition to the above, an Update TLV can omit a prefix of the prefix In addition to the above, an Update TLV can omit a prefix of the prefix
being announced, which is then extracted from the preceding Update TLV being announced, which is then extracted from the preceding Update TLV
in the same address family (IPv4 or IPv6). Finally, as a special in the same address family (IPv4 or IPv6). Finally, as a special
optimisation for the case when a router-id coincides with the interface-id optimisation for the case when a router-id coincides with the interface-id
part of an IPv6 address, Router-ID TLV itself may be omitted and the part of an IPv6 address, the Router-Id TLV itself may be omitted, and the
router-id derived from the low-order bits of the advertised prefix router-id is derived from the low-order bits of the advertised prefix
(<xref target="update"/>).</t> (<xref target="update" format="default"/>).</t>
<t>In order to implement these compression techniques, Babel uses
<t>In order to implement these compression techniques, Babel uses
a stateful parser: a TLV may refer to data from a previous TLV. The a stateful parser: a TLV may refer to data from a previous TLV. The
parser state consists of the following pieces of data: parser state consists of the following pieces of data:
<list style="symbols"> </t>
<t>for each address encoding that allows compression, the current <ul spacing="normal">
default prefix; this is undefined at the start of the packet, and is <li>for each address encoding that allows compression, the current
default prefix: this is undefined at the start of the packet and is
updated by each Update TLV with the Prefix flag set updated by each Update TLV with the Prefix flag set
(<xref target="update"/>);</t> (<xref target="update" format="default"/>);</li>
<t>for each address family (IPv4 or IPv6), the current next-hop; this is <li>for each address family (IPv4 or IPv6), the current next hop: this
is
the source address of the enclosing packet for the matching address the source address of the enclosing packet for the matching address
family at the start of a packet, and is updated by each Next-Hop TLV family at the start of a packet, and it is updated by each Next Hop TLV
(<xref target="next-hop"/>);</t> (<xref target="next-hop" format="default"/>);</li>
<t>the current router-id; this is undefined at the start of the packet, <li>the current router-id: this is undefined at the start of the packe
and is updated by each Router-ID TLV (<xref target="router-id"/>) t,
and by each Update TLV with Router-Id flag set.</t> and it is updated by each Router-Id TLV (<xref target="router-id" format="defa
</list></t> ult"/>)
and by each Update TLV with Router-Id flag set.</li>
<t>Since the parser state must be identical across implementations, it is </ul>
updated before checking for mandatory sub-TLVs: parsing a TLV MUST update <t>Since the parser state must be identical across implementations, it i
s
updated before checking for mandatory sub-TLVs: parsing a TLV <bcp14>MUST</bcp14
> update
the parser state even if the TLV is otherwise ignored due to an unknown the parser state even if the TLV is otherwise ignored due to an unknown
mandatory sub-TLV or for any other reason.</t> mandatory sub-TLV or for any other reason.</t>
<t>None of the TLVs that modify the parser state are allowed in the pack
<t>None of the TLVs that modify the parser state are allowed in the packet et
trailer; hence, an implementation may choose to use a dedicated stateless trailer; hence, an implementation may choose to use a dedicated stateless
parser to parse the packet trailer.</t> parser to parse the packet trailer.</t>
</section>
<section anchor="tlv-details" numbered="true" toc="default">
<name>Details of Specific TLVs</name>
</section> <section numbered="true" toc="default">
<name>Pad1</name>
<section title="Details of Specific TLVs" anchor="tlv-details"> <artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Pad1">
<figure><artwork><![CDATA[
0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 0 to indicate a Pad1 TLV.</t> <dt>Type</dt>
</list></t> <dd>Set to 0 to indicate a Pad1 TLV.</dd>
</dl>
<t>This TLV is silently ignored on reception. It is allowed in the packet <t>This TLV is silently ignored on reception. It is allowed in the pa
cket
trailer.</t> trailer.</t>
</section>
</section> <section numbered="true" toc="default">
<name>PadN</name>
<section title="PadN"> <artwork name="" type="" align="left" alt=""><![CDATA[
<figure><artwork><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 1 to indicate a PadN TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 1 to indicate a PadN TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="MBZ">Must be zero, set to 0 on transmission.</t> <dd>The length of the body in octets, exclusive of the
</list></t> Type and Length fields.</dd>
<dt>MBZ</dt>
<t>This TLV is silently ignored on reception. It is allowed in the packet <dd>Must be zero, set to 0 on transmission.</dd>
</dl>
<t>This TLV is silently ignored on reception. It is allowed in the pa
cket
trailer.</t> trailer.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Acknowledgment Request</name>
<section title="Acknowledgment Request"> <artwork name="" type="" align="left" alt=""><![CDATA[
<figure><artwork><![CDATA[
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Opaque | Interval | | Opaque | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>This TLV requests that the receiver send an Acknowledgment TLV
<t>This TLV requests that the receiver send an Acknowledgment TLV
within the number of centiseconds specified by the Interval field.</t> within the number of centiseconds specified by the Interval field.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 2 to indicate an Acknowledgment Request TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 2 to indicate an Acknowledgment Request TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="Reserved">Sent as 0 and MUST be ignored on <dd>The length of the body in octets, exclusive of the
reception.</t> Type and Length fields.</dd>
<t hangText="Opaque">An arbitrary value that will be echoed in the <dt>Reserved</dt>
receiver's Acknowledgment TLV.</t> <dd>Sent as 0 and <bcp14>MUST</bcp14> be ignored on
<t hangText="Interval">A time interval in centiseconds after which the reception.</dd>
sender will assume that this packet has been lost. This MUST NOT be 0. <dt>Opaque</dt>
The receiver MUST send an Acknowledgment TLV before this time has elapsed <dd>An arbitrary value that will be echoed in the
(with a margin allowing for propagation time). </t> receiver's Acknowledgment TLV.</dd>
</list></t> <dt>Interval</dt>
<dd>A time interval in centiseconds after which the
<t>This TLV is self-terminating, and allows sub-TLVs.</t> sender will assume that this packet has been lost. This <bcp14>MUST NOT</bcp14>
be 0.
</section> The receiver <bcp14>MUST</bcp14> send an Acknowledgment TLV before this time has
elapsed
<section title="Acknowledgment" anchor="ack"> (with a margin allowing for propagation time). </dd>
</dl>
<figure><artwork><![CDATA[ <t>This TLV is self-terminating and allows sub-TLVs.</t>
</section>
<section anchor="ack" numbered="true" toc="default">
<name>Acknowledgment</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
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 | Opaque | | Type = 3 | Length | Opaque |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>This TLV is sent by a node upon receiving an Acknowledgment Request
<t>This TLV is sent by a node upon receiving an Acknowledgment Request.</t> TLV.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 3 to indicate an Acknowledgment TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 3 to indicate an Acknowledgment TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="Opaque">Set to the Opaque value of the Acknowledgment Request <dd>The length of the body in octets, exclusive of the
that prompted this Acknowledgment.</t> Type and Length fields.</dd>
</list></t> <dt>Opaque</dt>
<dd>Set to the Opaque value of the Acknowledgment Request
<t>Since Opaque values are not globally unique, this TLV MUST be sent to that prompted this Acknowledgment.</dd>
</dl>
<t>Since Opaque values are not globally unique, this TLV <bcp14>MUST</
bcp14> be sent to
a unicast address.</t> a unicast address.</t>
<t>This TLV is self-terminating and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
<section numbered="true" toc="default">
</section> <name>Hello</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Hello">
<figure><artwork><![CDATA[
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 4 | Length | Flags | | Type = 4 | Length | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Interval | | Seqno | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>This TLV is used for neighbour discovery and for determining a
<t>This TLV is used for neighbour discovery and for determining a
neighbour's reception cost.</t> neighbour's reception cost.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 4 to indicate a Hello TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 4 to indicate a Hello TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="Flags">The individual bits of this field specify special <dd>The length of the body in octets, exclusive of the
handling of this TLV (see below).</t> Type and Length fields.</dd>
<t hangText="Seqno">If the Unicast flag is set, this is the value of the <dt>Flags</dt>
<dd>The individual bits of this field specify special
handling of this TLV (see below).</dd>
<dt>Seqno</dt>
<dd>If the Unicast flag is set, this is the value of the
sending node's outgoing Unicast Hello seqno for this neighbour. Otherwise, sending node's outgoing Unicast Hello seqno for this neighbour. Otherwise,
it is the sending node's outgoing Multicast Hello seqno for this interface.</t> it is the sending node's outgoing Multicast Hello seqno for this interface.</dd>
<t hangText="Interval">If non-zero, this is an upper bound, expressed in <dt>Interval</dt>
<dd>If nonzero, this is an upper bound, expressed in
centiseconds, on the time after which the sending node will send a new centiseconds, on the time after which the sending node will send a new
scheduled Hello TLV with the same setting of the Unicast flag. If this is scheduled Hello TLV with the same setting of the Unicast flag. If this is
0, then this Hello represents an unscheduled Hello, and doesn't carry any 0, then this Hello represents an unscheduled Hello and doesn't carry any
new information about times at which Hellos are sent.</t> new information about times at which Hellos are sent.</dd>
</list></t> </dl>
<t>The Flags field is interpreted as follows:
<t>The Flags field is interpreted as follows: </t>
<figure><artwork><![CDATA[ <artwork name="" type="" align="left" alt=""><![CDATA[
0 1 0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<list style="symbols"> <dl spacing="normal" indent="10">
<t>U (Unicast) flag (8000 hexadecimal): if set, then this Hello
represents a Unicast Hello, otherwise it represents a Multicast Hello;</t>
<t>X: all other bits MUST be sent as 0 and silently ignored on reception.</t>
</list>
</t>
<t>Every time a Hello is sent, the corresponding seqno counter MUST be <dt>U (Unicast) flag (8000 hexadecimal):</dt><dd>if set, then this H
ello
represents a Unicast Hello, otherwise it represents a Multicast Hello;</dd>
<dt>X:</dt><dd>all other bits <bcp14>MUST</bcp14> be sent as 0 and s
ilently ignored on reception.</dd>
</dl>
<t>Every time a Hello is sent, the corresponding seqno counter <bcp14>
MUST</bcp14> be
incremented. Since there is a single seqno counter for all the Multicast incremented. Since there is a single seqno counter for all the Multicast
Hellos sent by a given node over a given interface, if the Unicast flag is Hellos sent by a given node over a given interface, if the Unicast flag is
not set, this TLV MUST be sent to all neighbors on this link, which can be not set, this TLV <bcp14>MUST</bcp14> be sent to all neighbours on this link, wh
achieved by sending to a multicast destination, or by sending multiple ich can be
achieved by sending to a multicast destination or by sending multiple
packets to the unicast addresses of all reachable neighbours. Conversely, packets to the unicast addresses of all reachable neighbours. Conversely,
if the Unicast flag is set, this TLV MUST be sent to a single neighbour, if the Unicast flag is set, this TLV <bcp14>MUST</bcp14> be sent to a single nei ghbour,
which can achieved by sending to a unicast destination. In order to avoid which can achieved by sending to a unicast destination. In order to avoid
large discontinuities in link quality, multiple Hello TLVs SHOULD NOT be large discontinuities in link quality, multiple Hello TLVs <bcp14>SHOULD NOT</bc p14> be
sent in the same packet.</t> sent in the same packet.</t>
<t>This TLV is self-terminating and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
<section numbered="true" toc="default">
</section> <name>IHU</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="IHU">
<figure><artwork><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>An IHU ("I Heard You") TLV is used for confirming bidirectional
<t>An IHU ("I Heard You") TLV is used for confirming bidirectional
reachability and carrying a link's transmission cost.</t> reachability and carrying a link's transmission cost.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 5 to indicate an IHU TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 5 to indicate an IHU TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="AE">The encoding of the Address field. This should be 1 or 3 <dd>The length of the body in octets, exclusive of the
in most cases. As an optimisation, it MAY be 0 if the TLV is Type and Length fields.</dd>
<dt>AE</dt>
<dd>The encoding of the Address field. This should be 1 or 3
in most cases. As an optimisation, it <bcp14>MAY</bcp14> be 0 if the TLV is
sent to a unicast address, if the association is over a point-to-point sent to a unicast address, if the association is over a point-to-point
link, or when bidirectional reachability is ascertained by means outside of link, or when bidirectional reachability is ascertained by means outside of
the Babel protocol.</t> the Babel protocol.</dd>
<t hangText="Reserved">Sent as 0 and MUST be ignored on reception.</t> <dt>Reserved</dt>
<t hangText="Rxcost">The rxcost according to the sending node of the <dd>Sent as 0 and <bcp14>MUST</bcp14> be ignored on reception.</dd>
<dt>Rxcost</dt>
<dd>The rxcost according to the sending node of the
interface whose address is specified in the Address field. The value FFFF interface whose address is specified in the Address field. The value FFFF
hexadecimal (infinity) indicates that this interface is unreachable.</t> hexadecimal (infinity) indicates that this interface is unreachable.</dd>
<t hangText="Interval">An upper bound, expressed in centiseconds, on the <dt>Interval</dt>
time after which the sending node will send a new IHU; this MUST NOT be 0. <dd>An upper bound, expressed in centiseconds, on the
time after which the sending node will send a new IHU; this <bcp14>MUST NOT</bcp
14> be 0.
The receiving node will use this value in order to compute a hold time for The receiving node will use this value in order to compute a hold time for
this symmetric association.</t> this symmetric association.</dd>
<t hangText="Address">The address of the destination node, in the format <dt>Address</dt>
specified by the AE field. Address compression is not allowed.</t> <dd>The address of the destination node, in the format
</list></t> specified by the AE field. Address compression is not allowed.</dd>
</dl>
<t>Conceptually, an IHU is destined to a single neighbour. However, IHU <t>Conceptually, an IHU is destined to a single neighbour. However, I
TLVs contain an explicit destination address, and MAY be sent to HU
TLVs contain an explicit destination address, and <bcp14>MAY</bcp14> be sent to
a multicast address, as this allows aggregation of IHUs destined to a multicast address, as this allows aggregation of IHUs destined to
distinct neighbours into a single packet and avoids the need for an ARP or distinct neighbours into a single packet and avoids the need for an ARP or
Neighbour Discovery exchange when a neighbour is not being used for data Neighbour Discovery exchange when a neighbour is not being used for data
traffic.</t> traffic.</t>
<t>IHU TLVs with an unknown value in the AE field <bcp14>MUST</bcp14>
<t>IHU TLVs with an unknown value in the AE field MUST be silently be silently
ignored.</t> ignored.</t>
<t>This TLV is self-terminating and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
<section anchor="router-id" numbered="true" toc="default">
</section> <name>Router-Id</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Router-Id" anchor="router-id">
<figure><artwork><![CDATA[
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Router-Id + + Router-Id +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>A Router-Id TLV establishes a router-id that is implied by subseque
<t>A Router-Id TLV establishes a router-id that is implied by subsequent nt
Update TLVs, as described in <xref target="parser-state"/>. This TLV sets Update TLVs, as described in <xref target="parser-state" format="default"/>. Th
is TLV sets
the router-id even if it is otherwise ignored due to an unknown mandatory the router-id even if it is otherwise ignored due to an unknown mandatory
sub-TLV.</t> sub-TLV.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 6 to indicate a Router-Id TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 6 to indicate a Router-Id TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="Reserved">Sent as 0 and MUST be ignored on reception.</t> <dd>The length of the body in octets, exclusive of the
<t hangText="Router-Id">The router-id for routes advertised in subsequent Type and Length fields.</dd>
Update TLVs. This MUST NOT consist of all zeroes or all ones.</t> <dt>Reserved</dt>
</list></t> <dd>Sent as 0 and <bcp14>MUST</bcp14> be ignored on reception.</dd>
<dt>Router-Id</dt>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> <dd>The router-id for routes advertised in subsequent
Update TLVs. This <bcp14>MUST NOT</bcp14> consist of all zeroes or all ones.</d
</section> d>
</dl>
<section title="Next Hop" anchor="next-hop"> <t>This TLV is self-terminating and allows sub-TLVs.</t>
</section>
<figure><artwork><![CDATA[ <section anchor="next-hop" numbered="true" toc="default">
<name>Next Hop</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>A Next Hop TLV establishes a next-hop address for a given address
<t>A Next Hop TLV establishes a next-hop address for a given address
family (IPv4 or IPv6) that is implied in subsequent Update TLVs, as family (IPv4 or IPv6) that is implied in subsequent Update TLVs, as
described in <xref target="parser-state"/>. This TLV sets up the next-hop described in <xref target="parser-state" format="default"/>. This TLV sets up t he next hop
for subsequent Update TLVs even if it is otherwise ignored due to an for subsequent Update TLVs even if it is otherwise ignored due to an
unknown mandatory sub-TLV.</t> unknown mandatory sub-TLV.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 7 to indicate a Next Hop TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 7 to indicate a Next Hop TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="AE">The encoding of the Address field. This SHOULD be <dd>The length of the body in octets, exclusive of the
1 (IPv4) or 3 (link-local IPv6), and MUST NOT be 0.</t> Type and Length fields.</dd>
<t hangText="Reserved">Sent as 0 and MUST be ignored on reception.</t> <dt>AE</dt>
<t hangText="Next hop">The next-hop address advertised by subsequent Update <dd>The encoding of the Address field. This <bcp14>SHOULD</bcp14> b
TLVs, for this address family.</t> e
</list></t> 1 (IPv4) or 3 (link-local IPv6), and <bcp14>MUST NOT</bcp14> be 0.</dd>
<dt>Reserved</dt>
<t>When the address family matches the network-layer protocol that this <dd>Sent as 0 and <bcp14>MUST</bcp14> be ignored on reception.</dd>
packet is transported over, a Next Hop TLV is not needed: in the absence <dt>Next hop</dt>
of a Next Hop TLV in a given address family, the next hop address is taken <dd>The next-hop address advertised by subsequent Update
TLVs for this address family.</dd>
</dl>
<t>When the address family matches the network-layer protocol over whi
ch this
packet is transported, a Next Hop TLV is not needed: in the 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.</t> to be the source address of the packet.</t>
<t>Next Hop TLVs with an unknown value for the AE field <bcp14>MUST</b
<t>Next Hop TLVs with an unknown value for the AE field MUST be silently cp14> be silently
ignored.</t> ignored.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
<section anchor="update" numbered="true" toc="default">
</section> <name>Update</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Update" anchor="update">
<figure><artwork><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>An Update TLV advertises or retracts a route. As an optimisation,
<t>An Update TLV advertises or retracts a route. As an optimisation, it it
can optionally 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, as described in router-id and a new default prefix, as described in
<xref target="parser-state"/>.</t> <xref target="parser-state" format="default"/>.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 8 to indicate an Update TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 8 to indicate an Update TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="AE">The encoding of the Prefix field.</t> <dd>The length of the body in octets, exclusive of the
<t hangText="Flags">The individual bits of this field specify special Type and Length fields.</dd>
handling of this TLV (see below).</t> <dt>AE</dt>
<t hangText="Plen">The length in bits of the advertised prefix. If AE is <dd>The encoding of the Prefix field.</dd>
3 (link-local IPv6), Omitted MUST be 0.</t> <dt>Flags</dt>
<t hangText="Omitted">The number of octets that have been omitted at <dd>The individual bits of this field specify special
handling of this TLV (see below).</dd>
<dt>Plen</dt>
<dd>The length in bits of the advertised prefix. If AE is
3 (link-local IPv6), the Omitted field <bcp14>MUST</bcp14> be 0.</dd>
<dt>Omitted</dt>
<dd>The number of octets that have been omitted at
the beginning of the advertised prefix and that should be taken from a the beginning of the advertised prefix and that should be taken from a
preceding Update TLV in the same address family with the Prefix flag set.</t> preceding Update TLV in the same address family with the Prefix flag set.</dd>
<t hangText="Interval">An upper bound, expressed in centiseconds, on the <dt>Interval</dt>
<dd>An upper bound, expressed in centiseconds, on the
time after which the sending node will send a new update for this prefix. time after which the sending node will send a new update for this prefix.
This MUST NOT be 0. The receiving node will use this value to compute This <bcp14>MUST NOT</bcp14> be 0. The receiving node will use this value to co mpute
a hold time for the route table entry. The value FFFF hexadecimal a hold time for the route table entry. The value FFFF hexadecimal
(infinity) expresses that this announcement will not be repeated unless (infinity) expresses that this announcement will not be repeated unless
a request is received (<xref target="request-expiring"/>).</t> a request is received (<xref target="request-expiring" format="default"/>).</dd>
<t hangText="Seqno">The originator's sequence number for this update.</t> <dt>Seqno</dt>
<t hangText="Metric">The sender's metric for this route. The value FFFF <dd>The originator's sequence number for this update.</dd>
hexadecimal (infinity) means that this is a route retraction.</t> <dt>Metric</dt>
<t hangText="Prefix">The prefix being advertised. This field's size is <dd>The sender's metric for this route. The value FFFF
(Plen/8&nbsp;-&nbsp;Omitted) rounded upwards.</t> hexadecimal (infinity) means that this is a route retraction.</dd>
</list></t> <dt>Prefix</dt>
<dd>The prefix being advertised. This field's size is
<t>The Flags field is interpreted as follows: (Plen/8&nbsp;-&nbsp;Omitted) rounded upwards.</dd>
<figure><artwork><![CDATA[ </dl>
<t>The Flags field is interpreted as follows:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
|P|R|X|X|X|X|X|X| |P|R|X|X|X|X|X|X|
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<list style="symbols"> <dl spacing="normal" indent="10">
<t>P (Prefix) flag (80 hexadecimal): if set, then this Update
establishes a new default prefix for subsequent Update TLVs with a matching <dt>P (Prefix) flag (80 hexadecimal):</dt><dd>if set, then this Upda
te
TLV establishes a new default prefix for subsequent Update TLVs with a matching
address encoding within the same packet, even if this TLV is otherwise address encoding within the same packet, even if this TLV is otherwise
ignored due to an unknown mandatory sub-TLV;</t> ignored due to an unknown mandatory sub-TLV;</dd>
<t>R (Router-Id) flag (40 hexadecimal): if set, then this TLV establishes <dt>R (Router-Id) flag (40 hexadecimal):</dt><dd><t>if set, then t
his TLV establishes
a new default router-id for this TLV and subsequent Update TLVs in the a new default router-id for this TLV and subsequent Update TLVs in the
same packet, even if this TLV is otherwise ignored due to an unknown same packet, even if this TLV is otherwise ignored due to an unknown
mandatory sub-TLV. This router-id is computed from the first address of mandatory sub-TLV. This router-id is computed from the first address of
the advertised prefix as follows: the advertised prefix as follows:
<list> </t>
<t>if the length of the address is 8 octets or more, then the new <ul spacing="normal">
router-id is taken from the 8 last octets of the address;</t> <li>if the length of the address is 8 octets or more, then the n
<t>if the length of the address is smaller than 8 octets, then the new ew
router-id is taken from the 8 last octets of the address;</li>
<li>if the length of the address is smaller than 8 octets, then
the new
router-id consists of the required number of zero octets followed by the router-id consists of the required number of zero octets followed by the
address, i.e., the address is stored on the right of the router-id. For address, i.e., the address is stored on the right of the router-id. For
example, for an IPv4 address, the router-id consists of 4 octets of example, for an IPv4 address, the router-id consists of 4 octets of
zeroes followed by the IPv4 address.</t> zeroes followed by the IPv4 address.</li>
</list></t> </ul>
<t>X: all other bits MUST be sent as 0 and silently ignored on reception.</t> </dd>
</list> <dt>X:</dt><dd>all other bits <bcp14>MUST</bcp14> be sent as 0 and s
ilently ignored on reception.</dd>
</dl>
<t>The prefix being advertised by an Update TLV is computed as follows
:
</t> </t>
<ul spacing="normal">
<t>The prefix being advertised by an Update TLV is computed as follows: <li>the first Omitted octets of the prefix are taken from the previo
<list style="symbols"> us
<t>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; if Omitted is even if it was ignored due to an unknown mandatory sub-TLV; if the Omitted field
not zero and there is no such TLV, then this Update MUST be ignored;</t> is
<t>the next (Plen/8 - Omitted) rounded upwards octets are taken from the not zero and there is no such TLV, then this Update <bcp14>MUST</bcp14> be ignor
Prefix field;</t> ed;</li>
<t>if Plen is not a multiple of 8, then any bits beyond Plen (i.e., the <li>the next (Plen/8 - Omitted) rounded upwards octets are taken fro
low-order (8 - Plen MOD 8) bits of the last octet) are cleared;</t> m the
<t>the remaining octets are set to 0.</t> Prefix field;</li>
</list> <li>if Plen is not a multiple of 8, then any bits beyond Plen (i.e.,
</t> the
low-order (8 - Plen MOD 8) bits of the last octet) are cleared;</li>
<t>If the Metric field is finite, the router-id of the originating node <li>the remaining octets are set to 0.</li>
</ul>
<t>If the Metric field is finite, the router-id of the originating nod
e
for this announcement is taken from the prefix advertised by this Update for this announcement is taken from the prefix advertised by this Update
if the Router-Id flag is set, computed as described above. Otherwise, it if the Router-Id flag is set, computed as described above. Otherwise, it
is taken either from the preceding Router-Id TLV, or the preceding is taken either from the preceding Router-Id TLV, or the preceding
Update TLV with the Router-Id flag set, whichever comes last, even if Update TLV with the Router-Id flag set, whichever comes last, even if
that TLV is otherwise ignored due to an unknown mandatory sub-TLV; if that TLV is otherwise ignored due to an unknown mandatory sub-TLV; if
there is no suitable TLV, then this update is ignored.</t> there is no suitable TLV, then this update is ignored.</t>
<t>The next-hop address for this update is taken from the last precedi
<t>The next-hop address for this update is taken from the last preceding ng
Next Hop TLV with a matching address family (IPv4 or IPv6) in the same 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 mandatory packet even if it was otherwise ignored due to an unknown mandatory
sub-TLV; if no such TLV exists, it is taken from the network-layer source sub-TLV; if no such TLV exists, it is taken from the network-layer source
address of this packet if it belongs to the same address family as the address of this packet if it belongs to the same address family as the
prefix being announced; otherwise, this Update MUST be ignored.</t> prefix being announced; otherwise, this Update <bcp14>MUST</bcp14> be ignored.</
t>
<t>If the metric field is FFFF hexadecimal, this TLV specifies <t>If the metric field is FFFF hexadecimal, this TLV specifies
a retraction. In that case, the router-id, next-hop and seqno are not a retraction. In that case, the router-id, next hop, and seqno are not
used. AE MAY then be 0, in which case this Update retracts all of the used. AE <bcp14>MAY</bcp14> then be 0, in which case this Update retracts all o
f the
routes previously advertised by the sending interface. If the metric is routes previously advertised by the sending interface. If the metric is
finite, AE MUST NOT be 0; Update TLVs with finite metric and AE equal to finite, AE <bcp14>MUST NOT</bcp14> be 0; Update TLVs with finite metric and AE e
0 MUST be ignored. If the metric is infinite and AE is 0, Plen and qual to
Omitted MUST both be 0; Update TLVs that do not satisfy this requirement 0 <bcp14>MUST</bcp14> be ignored. If the metric is infinite and AE is 0, Plen a
MUST be ignored.</t> nd
Omitted <bcp14>MUST</bcp14> both be 0; Update TLVs that do not satisfy this requ
<t>Update TLVs with an unknown value in the AE field MUST be silently irement
<bcp14>MUST</bcp14> be ignored.</t>
<t>Update TLVs with an unknown value in the AE field <bcp14>MUST</bcp1
4> be silently
ignored.</t> ignored.</t>
<t>This TLV is self-terminating and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
<section numbered="true" toc="default">
</section> <name>Route Request</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Route Request">
<figure><artwork><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>A Route Request TLV prompts the receiver to send an update for a gi
<t>A Route Request TLV prompts the receiver to send an update for a given ven
prefix, or a full route table dump.</t> prefix, or a full route table dump.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 9 to indicate a Route Request TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 9 to indicate a Route Request TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="AE">The encoding of the Prefix field. The value 0 specifies <dd>The length of the body in octets, exclusive of the
Type and Length fields.</dd>
<dt>AE</dt>
<dd>The encoding of the Prefix field. The value 0 specifies
that this is a request for a full route table dump (a wildcard that this is a request for a full route table dump (a wildcard
request).</t> request).</dd>
<t hangText="Plen">The length in bits of the requested prefix.</t> <dt>Plen</dt>
<t hangText="Prefix">The prefix being requested. This field's size is <dd>The length in bits of the requested prefix.</dd>
Plen/8 rounded upwards.</t> <dt>Prefix</dt>
</list></t> <dd>The prefix being requested. This field's size is
Plen/8 rounded upwards.</dd>
<t>A Request TLV prompts the receiver to send an update message (possibly </dl>
<t>A Request TLV prompts the receiver to send an update message (possi
bly
a retraction) for the prefix specified by the AE, Plen, and Prefix fields, a retraction) for the prefix specified by the AE, Plen, and Prefix fields,
or a full dump of its route table if AE is 0 (in which case Plen must be or a full dump of its route table if AE is 0 (in which case Plen must be
0 and Prefix is of length 0). A Request TLV with AE set to 0 and Plen not 0 and Prefix is of length 0). A Request TLV with AE set to 0 and Plen not
set to 0 MUST be ignored.</t> set to 0 <bcp14>MUST</bcp14> be ignored.</t>
<t>This TLV is self-terminating and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
<section numbered="true" toc="default">
</section> <name>Seqno Request</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Seqno Request">
<figure><artwork><![CDATA[
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 10 | Length | AE | Plen | | Type = 10 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Hop Count | Reserved | | Seqno | Hop Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
+ Router-Id + + Router-Id +
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix... | Prefix...
+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>A Seqno Request TLV prompts the receiver to send an Update for a gi
<t>A Seqno Request TLV prompts the receiver to send an Update for a given ven
prefix with a given sequence number, or to forward the request further if prefix with a given sequence number, or to forward the request further if
it cannot be satisfied locally.</t> it cannot be satisfied locally.</t>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 10 to indicate a Seqno Request TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 10 to indicate a Seqno Request TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="AE">The encoding of the Prefix field. This MUST NOT be 0.</t> <dd>The length of the body in octets, exclusive of the
<t hangText="Plen">The length in bits of the requested prefix.</t> Type and Length fields.</dd>
<t hangText="Seqno">The sequence number that is being requested.</t> <dt>AE</dt>
<t hangText="Hop Count">The maximum number of times that this TLV may be <dd>The encoding of the Prefix field. This <bcp14>MUST NOT</bcp14>
forwarded, plus 1. This MUST NOT be 0.</t> be 0.</dd>
<t hangText="Reserved">Sent as 0 and MUST be ignored on reception.</t> <dt>Plen</dt>
<t hangText="Router-Id">The Router-Id that is being requested. This MUST <dd>The length in bits of the requested prefix.</dd>
NOT consist of all zeroes or all ones.</t> <dt>Seqno</dt>
<t hangText="Prefix">The prefix being requested. This field's size is <dd>The sequence number that is being requested.</dd>
Plen/8 rounded upwards.</t> <dt>Hop Count</dt>
</list></t> <dd>The maximum number of times that this TLV may be
forwarded, plus 1. This <bcp14>MUST NOT</bcp14> be 0.</dd>
<t>A Seqno Request TLV prompts the receiving node to send a finite-metric <dt>Reserved</dt>
<dd>Sent as 0 and <bcp14>MUST</bcp14> be ignored on reception.</dd>
<dt>Router-Id</dt>
<dd>The Router-Id that is being requested. This <bcp14>MUST
NOT</bcp14> consist of all zeroes or all ones.</dd>
<dt>Prefix</dt>
<dd>The prefix being requested. This field's size is
Plen/8 rounded upwards.</dd>
</dl>
<t>A Seqno Request TLV prompts the receiving node to send a finite-met
ric
Update for the prefix specified by the AE, Plen, and Prefix fields, with Update for the prefix specified by the AE, Plen, and Prefix fields, with
either a router-id different from what is specified by the Router-Id either a router-id different from what is specified by the Router-Id
field, or a Seqno no less (modulo 2^16) than what is specified by the field, or a Seqno no less (modulo 2<sup>16</sup>) than what is specified by the
Seqno field. If this request cannot be satisfied locally, then it is Seqno field. If this request cannot be satisfied locally, then it is
forwarded according to the rules set out in forwarded according to the rules set out in
<xref target="handling-seqno-requests"/>.</t> <xref target="handling-seqno-requests" format="default"/>.</t>
<t>While a Seqno Request <bcp14>MAY</bcp14> be sent to a multicast add
<t>While a Seqno Request MAY be sent to a multicast address, it MUST NOT be ress, it <bcp14>MUST NOT</bcp14> be
forwarded to a multicast address and MUST NOT be forwarded to more than forwarded to a multicast address and <bcp14>MUST NOT</bcp14> be forwarded to mor
one neighbour. A request MUST NOT be forwarded if its Hop Count field is e than
one neighbour. A request <bcp14>MUST NOT</bcp14> be forwarded if its Hop Count
field is
1.</t> 1.</t>
<t>This TLV is self-terminating and allows sub-TLVs.</t>
<t>This TLV is self-terminating, and allows sub-TLVs.</t> </section>
</section>
</section> <section numbered="true" toc="default">
</section> <name>Details of specific sub-TLVs</name>
<section anchor="pad1" numbered="true" toc="default">
<section title="Details of specific sub-TLVs"> <name>Pad1</name>
<artwork name="" type="" align="left" alt=""><![CDATA[
<section title="Pad1" anchor="pad1">
<figure><artwork><![CDATA[
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| Type = 0 | | Type = 0 |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
]]></artwork></figure> ]]></artwork>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 0 to indicate a Pad1 sub-TLV.</t> <dt>Type</dt>
</list></t> <dd>Set to 0 to indicate a Pad1 sub-TLV.</dd>
</dl>
<t>This sub-TLV is silently ignored on reception. It is allowed within <t>This sub-TLV is silently ignored on reception. It is allowed withi
n
any TLV that allows sub-TLVs.</t> any TLV that allows sub-TLVs.</t>
</section>
</section> <section numbered="true" toc="default">
<name>PadN</name>
<section title="PadN"> <artwork name="" type="" align="left" alt=""><![CDATA[
<figure><artwork><![CDATA[
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...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
]]></artwork></figure> ]]></artwork>
<t>Fields:
<t>Fields : </t>
<list style="hanging" hangIndent="10"> <dl newline="false" spacing="normal" indent="10">
<t hangText="Type">Set to 1 to indicate a PadN sub-TLV.</t> <dt>Type</dt>
<t hangText="Length">The length of the body in octets, exclusive of the <dd>Set to 1 to indicate a PadN sub-TLV.</dd>
Type and Length fields.</t> <dt>Length</dt>
<t hangText="MBZ">Must be zero, set to 0 on transmission.</t> <dd>The length of the body in octets, exclusive of the
</list></t> Type and Length fields.</dd>
<dt>MBZ</dt>
<t>This sub-TLV is silently ignored on reception. It is allowed within <dd>Must be zero, set to 0 on transmission.</dd>
</dl>
<t>This sub-TLV is silently ignored on reception. It is allowed withi
n
any TLV that allows sub-TLVs.</t> any TLV that allows sub-TLVs.</t>
</section>
</section> </section>
</section>
</section> <section numbered="true" toc="default">
<name>IANA Considerations</name>
</section> <t>IANA has registered the UDP port number 6696, called "babel", for use
<section title="IANA Considerations">
<t>IANA has registered the UDP port number 6696, called "babel", for use
by the Babel protocol.</t> by the Babel protocol.</t>
<t>IANA has registered the IPv6 multicast group ff02::1:6 and the
<t>IANA has registered the IPv6 multicast group ff02::1:6 and the
IPv4 multicast group 224.0.0.111 for use by the Babel protocol.</t> IPv4 multicast group 224.0.0.111 for use by the Babel protocol.</t>
<t>IANA has created a registry called "Babel TLV Types". The allocation
<t>IANA has created a registry called "Babel TLV Types". The allocation policy for this registry is Specification Required <xref target="RFC8126" format
policy for this registry is Specification Required <xref target="RFC8126"/> ="default"/>
for Types 0-223, and Experimental Use for Types 224-254. The values in for Types 0-223 and Experimental Use for Types 224-254. The values in
this registry are as follows:</t> this registry are as follows:</t>
<texttable> <table align="center">
<ttcol>Type</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <thead>
<c>0</c><c>Pad1</c><c>this document</c> <tr>
<c>1</c><c>PadN</c><c>this document</c> <th align="left">Type</th>
<c>2</c><c>Acknowledgment Request</c><c>this document</c> <th align="left">Name</th>
<c>3</c><c>Acknowledgment</c><c>this document</c> <th align="left">Reference</th>
<c>4</c><c>Hello</c><c>this document</c> </tr>
<c>5</c><c>IHU</c><c>this document</c> </thead>
<c>6</c><c>Router-Id</c><c>this document</c> <tbody>
<c>7</c><c>Next Hop</c><c>this document</c> <tr>
<c>8</c><c>Update</c><c>this document</c> <td align="left">0</td>
<c>9</c><c>Route Request</c><c>this document</c> <td align="left">Pad1</td>
<c>10</c><c>Seqno Request</c><c>this document</c> <td align="left">RFC 8966</td>
<c>11</c><c>TS/PC</c><c><xref target="RFC7298"/></c> </tr>
<c>12</c><c>HMAC</c><c><xref target="RFC7298"/></c> <tr>
<c>13</c><c>Source-specific Update</c><c><xref target="BABEL-SS"/></c> <td align="left">1</td>
<c>14</c><c>Source-specific Request</c><c><xref target="BABEL-SS"/></c> <td align="left">PadN</td>
<c>15</c><c>Source-specific Seqno Request</c><c><xref target="BABEL-SS"/></c> <td align="left">RFC 8966</td>
<c>16</c><c>MAC</c><c><xref target="BABEL-MAC"/></c> </tr>
<c>17</c><c>PC</c><c><xref target="BABEL-MAC"/></c> <tr>
<c>18</c><c>Challenge Request</c><c><xref target="BABEL-MAC"/></c> <td align="left">2</td>
<c>19</c><c>Challenge Reply</c><c><xref target="BABEL-MAC"/></c> <td align="left">Acknowledgment Request</td>
<c>20-223</c><c>Unassigned</c><c></c> <td align="left">RFC 8966</td>
<c>224-254</c><c>Reserved for Experimental Use</c><c>this document</c> </tr>
<c>255</c><c>Reserved for expansion of the type space</c><c>this document</c> <tr>
</texttable> <td align="left">3</td>
<td align="left">Acknowledgment</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">4</td>
<td align="left">Hello</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">5</td>
<td align="left">IHU</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">6</td>
<td align="left">Router-Id</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">7</td>
<td align="left">Next Hop</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">8</td>
<td align="left">Update</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">9</td>
<td align="left">Route Request</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">10</td>
<td align="left">Seqno Request</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">11</td>
<td align="left">TS/PC</td>
<td align="left">
<xref target="RFC7298" format="default"/></td>
</tr>
<tr>
<td align="left">12</td>
<td align="left">HMAC</td>
<td align="left">
<xref target="RFC7298" format="default"/></td>
</tr>
<tr>
<td align="left">13</td>
<td align="left">Reserved</td>
<td align="left"></td>
</tr>
<tr>
<td align="left">14</td>
<td align="left">Reserved</td>
<td align="left"></td>
</tr>
<tr>
<td align="left">15</td>
<td align="left">Reserved</td>
<td align="left"></td>
</tr>
<tr>
<td align="left">224-254</td>
<td align="left">Reserved for Experimental Use</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">255</td>
<td align="left">Reserved for expansion of the type space</td>
<td align="left">RFC 8966</td>
</tr>
</tbody>
</table>
<t>IANA has created a registry called "Babel sub-TLV Types". The allocation <t>IANA has created a registry called "Babel Sub-TLV Types". The allocati on
policy for this registry is Specification Required for Types 0-111 and policy for this registry is Specification Required for Types 0-111 and
128-239, and Experimental Use for Types 112-126 and 240-254. The values 128-239, and Experimental Use for Types 112-126 and 240-254. The values
in this registry are as follows:</t> in this registry are as follows:</t>
<texttable> <table align="center">
<ttcol>Type</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <thead>
<c>0</c><c>Pad1</c><c>this document</c> <tr>
<c>1</c><c>PadN</c><c>this document</c> <th align="left">Type</th>
<c>2</c><c>Diversity</c><c><xref target="BABEL-DIVERSITY"/></c> <th align="left">Name</th>
<c>3</c><c>Timestamp</c><c><xref target="BABEL-RTT"/></c> <th align="left">Reference</th>
<c>4-111</c><c>Unassigned</c><c></c> </tr>
<c>112-126</c><c>Reserved for Experimental Use</c><c>this document</c> </thead>
<c>127</c><c>Reserved for expansion of the type space</c><c>this <tbody>
document</c> <tr>
<c>128</c><c>Source Prefix</c><c><xref target="BABEL-SS"/></c> <td align="left">0</td>
<c>129-239</c><c>Unassigned</c><c></c> <td align="left">Pad1</td>
<c>240-254</c><c>Reserved for Experimental Use</c><c>this document</c> <td align="left">RFC 8966</td>
<c>255</c><c>Reserved for expansion of the type space</c><c>this document</c> </tr>
</texttable> <tr>
<td align="left">1</td>
<t>IANA is instructed to create a registry called "Babel Address <td align="left">PadN</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">2</td>
<td align="left">Diversity</td>
<td align="left">
<xref target="I-D.chroboczek-babel-diversity-routing" format="defa
ult"/></td>
</tr>
<tr>
<td align="left">3</td>
<td align="left">Timestamp</td>
<td align="left">
<xref target="I-D.ietf-babel-rtt-extension" format="default"/></td
>
</tr>
<tr>
<td align="left">4-111</td>
<td align="left">Unassigned</td>
<td align="left"/>
</tr>
<tr>
<td align="left">112-126</td>
<td align="left">Reserved for Experimental Use</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">127</td>
<td align="left">Reserved for expansion of the type space</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">128</td>
<td align="left">Source Prefix</td>
<td align="left">
<xref target="I-D.ietf-babel-source-specific" format="default"/></
td>
</tr>
<tr>
<td align="left">129-239</td>
<td align="left">Unassigned</td>
<td align="left"/>
</tr>
<tr>
<td align="left">240-254</td>
<td align="left">Reserved for Experimental Use</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">255</td>
<td align="left">Reserved for expansion of the type space</td>
<td align="left">RFC 8966</td>
</tr>
</tbody>
</table>
<t>IANA has created a registry called "Babel Address
Encodings". The allocation policy for this registry is Specification Encodings". The allocation policy for this registry is Specification
Required for Address Encodings (AEs) 0-223, and Experimental Use for AEs Required for Address Encodings (AEs) 0-223, and Experimental Use for AEs
224-254. The values in this registry are as follows:</t> 224-254. The values in this registry are as follows:</t>
<texttable> <table align="center">
<ttcol>AE</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <thead>
<c>0</c><c>Wildcard address</c><c>this document</c> <tr>
<c>1</c><c>IPv4 address</c><c>this document</c> <th align="left">AE</th>
<c>2</c><c>IPv6 address</c><c>this document</c> <th align="left">Name</th>
<c>3</c><c>Link-local IPv6 address</c><c>this document</c> <th align="left">Reference</th>
<c>4-223</c><c>Unassigned</c><c></c> </tr>
<c>224-254</c><c>Reserved for Experimental Use</c><c>this document</c> </thead>
<c>255</c><c>Reserved for expansion of the AE space</c><c>this document</c> <tbody>
</texttable> <tr>
<td align="left">0</td>
<t>IANA has created a registry called "Babel Flags Values". The <td align="left">Wildcard address</td>
allocation policy for this registry is Specification Required. IANA is <td align="left">RFC 8966</td>
instructed to rename this registry to "Babel Update Flags Values". The </tr>
values in this registry are as follows:</t> <tr>
<texttable> <td align="left">1</td>
<ttcol>Bit</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <td align="left">IPv4 address</td>
<c>0</c><c>Default prefix</c><c>this document</c> <td align="left">RFC 8966</td>
<c>1</c><c>Default Router-ID</c><c>this document</c> </tr>
<c>2-7</c><c>Unassigned</c><c></c> <tr>
</texttable> <td align="left">2</td>
<td align="left">IPv6 address</td>
<t>IANA is instructed to create a new registry called "Babel Hello Flags <td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">3</td>
<td align="left">Link-local IPv6 address</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">4-223</td>
<td align="left">Unassigned</td>
<td align="left"/>
</tr>
<tr>
<td align="left">224-254</td>
<td align="left">Reserved for Experimental Use</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">255</td>
<td align="left">Reserved for expansion of the AE space</td>
<td align="left">RFC 8966</td>
</tr>
</tbody>
</table>
<t>IANA has renamed the registry called "Babel Flags Values" to "Babel Upd
ate Flags Values". The allocation policy for this registry is Specification Req
uired.
The values in this registry are as follows:</t>
<table align="center">
<thead>
<tr>
<th align="left">Bit</th>
<th align="left">Name</th>
<th align="left">Reference</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left">0</td>
<td align="left">Default prefix</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">1</td>
<td align="left">Default router-id</td>
<td align="left">RFC 8966</td>
</tr>
<tr>
<td align="left">2-7</td>
<td align="left">Unassigned</td>
<td align="left"/>
</tr>
</tbody>
</table>
<t>IANA has created a new registry called "Babel Hello Flags
Values". The allocation policy for this registry is Specification Values". The allocation policy for this registry is Specification
Required. The initial values in this registry are as follows:</t> Required. The initial values in this registry are as follows:</t>
<texttable> <table align="center">
<ttcol>Bit</ttcol><ttcol>Name</ttcol><ttcol>Reference</ttcol> <thead>
<c>0</c><c>Unicast</c><c>this document</c> <tr>
<c>1-15</c><c>Unassigned</c><c></c> <th align="left">Bit</th>
</texttable> <th align="left">Name</th>
<th align="left">Reference</th>
<t>IANA is instructed to replace all references to RFCs&nbsp;6126 and 7557 </tr>
in all of the registries mentioned above by references to this document.</t> </thead>
<tbody>
</section> <tr>
<td align="left">0</td>
<section title="Security Considerations"> <td align="left">Unicast</td>
<td align="left">RFC 8966</td>
<t>As defined in this document, Babel is a completely insecure protocol. </tr>
<tr>
<td align="left">1-15</td>
<td align="left">Unassigned</td>
<td align="left"/>
</tr>
</tbody>
</table>
<t>IANA has replaced all references to RFCs&nbsp;6126 and 7557
in all of the registries mentioned above with references to this document.</t>
</section>
<section numbered="true" toc="default">
<name>Security Considerations</name>
<t>As defined in this document, Babel is a completely insecure protocol.
Without additional security mechanisms, Babel trusts any information it Without additional security mechanisms, Babel trusts any information it
receives in plaintext UDP datagrams and acts on it. An attacker that is receives in plaintext UDP datagrams and acts on it. An attacker that is
present on the local network can impact Babel operation in a variety of present on the local network can impact Babel operation in a variety of
ways; for example they can: ways; for example they can:
<list style="symbols"> </t>
<t>spoof a Babel packet, and redirect traffic by announcing a route with <ul spacing="normal">
a smaller metric, a larger sequence number, or a longer prefix;</t> <li>spoof a Babel packet, and redirect traffic by announcing a route wit
<t>spoof a malformed packet, which could cause an insufficiently robust h
implementation to crash or interfere with the rest of the network;</t> a smaller metric, a larger sequence number, or a longer prefix;</li>
<t>replay a previously captured Babel packet, which could cause traffic to <li>spoof a malformed packet, which could cause an insufficiently robust
be redirected, blackholed or otherwise interfere with the network.</t> implementation to crash or interfere with the rest of the network;</li>
</list> <li>replay a previously captured Babel packet, which could cause traffic
to
be redirected, black-holed, or otherwise interfere with the network.</li>
</ul>
<t>
When carried over IPv6, Babel packets are ignored unless they are sent When carried over IPv6, Babel packets are ignored unless they are sent
from a link-local IPv6 address; since routers don't forward link-local from a link-local IPv6 address; since routers don't forward link-local
IPv6 packets, this mitigates the attacks outlined above by restricting IPv6 packets, this mitigates the attacks outlined above by restricting
them to on-link attackers. No such natural protection exists when Babel them to on-link attackers. No such natural protection exists when Babel
packets are carried over IPv4, which is one of the reasons why it is packets are carried over IPv4, which is one of the reasons why it is
recommended to deploy Babel over IPv6 recommended to deploy Babel over IPv6
(<xref target="transmission-reception"/>).</t> (<xref target="transmission-reception" format="default"/>).</t>
<t>It is usually difficult to ensure that packets arriving at a Babel node
<t>It is usually difficult to ensure that packets arriving at a Babel node
are trusted, even in the case where the local link is believed to be are trusted, even in the case where the local link is believed to be
secure. For that reason, it is RECOMMENDED that all Babel traffic be secure. For that reason, it is <bcp14>RECOMMENDED</bcp14> that all Babel traffi c be
protected by an application-layer cryptographic protocol. There are protected by an application-layer cryptographic protocol. There are
currently two suitable mechanisms, which implement different tradeoffs currently two suitable mechanisms, which implement different trade-offs
between implementation simplicity and security: between implementation simplicity and security:
<list style="symbols"> </t>
<t>Babel over DTLS <xref target="BABEL-DTLS"/> runs the majority of Babel <ul spacing="normal">
traffic over DTLS, and leverages DTLS to authenticate nodes and provide <li>Babel over DTLS <xref target="RFC8968" format="default"/> runs the m
confidentiality and integrity protection;</t> ajority of Babel
<t>MAC authentication <xref target="BABEL-MAC"/> appends a message traffic over DTLS and leverages DTLS to authenticate nodes and provide
confidentiality and integrity protection;</li>
<li>MAC authentication <xref target="RFC8967" format="default"/> appends
a message
authentication code (MAC) to every Babel packet to prove that it authentication code (MAC) to every Babel packet to prove that it
originated at a node that knows a shared secret, and includes sufficient originated at a node that knows a shared secret, and includes sufficient
additional information to prove that the packet is fresh (not replayed).</t> additional information to prove that the packet is fresh (not replayed).</li>
</list> </ul>
<t>
Both mechanisms enable nodes to ignore packets generated by attackers Both mechanisms enable nodes to ignore packets generated by attackers
without the proper credentials. They also ensure integrity of messages without the proper credentials. They also ensure integrity of messages
and prevent message replay. While Babel-DTLS supports asymmetric keying and prevent message replay. While Babel-DTLS supports asymmetric keying
and ensures confidentiality, Babel-MAC has a much more limited scope (see and ensures confidentiality, Babel-MAC has a much more limited scope (see
Sections 1.1, 1.2 and 7 of <xref target="BABEL-MAC"/>). Since Babel-MAC Sections <xref target="RFC8967" section="1.1" sectionFormat="bare"/>,
<xref target="RFC8967" section="1.2" sectionFormat="bare"/>, and
<xref target="RFC8967" section="7" sectionFormat="bare"/> of
<xref target="RFC8967" format="default"/>). Since Babel-MAC
is simpler and more lightweight, it is recommended in preference to is simpler and more lightweight, it is recommended in preference to
Babel-DTLS in deployments where its limitations are acceptable, i.e., when Babel-DTLS in deployments where its limitations are acceptable, i.e., when
symmetric keying is sufficient and where the routing information is not symmetric keying is sufficient and where the routing information is not
considered confidential.</t> considered confidential.</t>
<t>Every implementation of Babel <bcp14>SHOULD</bcp14> implement BABEL-MAC
<t>Every implementation of Babel SHOULD implement BABEL-MAC.</t> .</t>
<t>One should be aware that the information that a mobile Babel node
<t>One should be aware that the information that a mobile Babel node
announces to the whole routing domain is sufficient to determine the mobile announces to the whole routing domain is sufficient to determine the mobile
node's physical location with reasonable precision, which might cause node's physical location with reasonable precision, which might cause
privacy concerns even if the control traffic is protected from privacy concerns even if the control traffic is protected from
unauthenticated attackers by a cryptographic mechanism such as Babel-DTLS. unauthenticated attackers by a cryptographic mechanism such as Babel-DTLS.
This issue may be mitigated somewhat by using randomly chosen router-ids This issue may be mitigated somewhat by using randomly chosen router-ids
and randomly chosen IP addresses, and changing them often enough.</t> and randomly chosen IP addresses, and changing them often enough.</t>
</section> </section>
</middle>
<section title="Acknowledgments"> <back>
<t>A number of people have contributed text and ideas to this
specification. The authors are particularly indebted to Matthieu Boutier,
Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke
Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin Vigoureux.
Earlier versions of this document
greatly benefited from the input of Joel Halpern. The address compression
technique was inspired by <xref target="PACKETBB"/>.</t>
</section>
</middle>
<back>
<references title="Normative References">
<reference anchor="RFC2119"><front>
<title>Key words for use in RFCs to Indicate Requirement Levels</title>
<author initials="S." surname="Bradner" fullname="S. Bradner"/>
<date year="1997" month="March"/>
</front>
<seriesInfo name="BCP" value="14"/>
<seriesInfo name="RFC" value="2119"/>
<seriesInfo name="DOI" value="10.17487/RFC2119"/>
</reference>
<reference anchor="RFC8174"><front>
<title>Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words</title>
<author initials="B." surname="Leiba" fullname="B. Leiba"/>
<date year="2017" month="May"/>
</front>
<seriesInfo name="BCP" value="14"/>
<seriesInfo name="RFC" value="8174"/>
<seriesInfo name="DOI" value="10.17487/RFC8174"/>
</reference>
<reference anchor="RFC8126">
<front>
<title>Guidelines for Writing an IANA Considerations Section in RFCs</title>
<author initials='M.' surname='Cotton' fullname='M. Cotton'></author>
<author initials='B.' surname='Leiba' fullname='B. Leiba'></author>
<author initials='T.' surname='Narten' fullname='T. Narten'></author>
<date year='2017' month='June' />
</front>
<seriesInfo name='BCP' value='26' />
<seriesInfo name='RFC' value='8126' />
</reference>
<reference anchor="BABEL-MAC"><front>
<title>MAC authentication for the Babel routing protocol</title>
<author fullname="Clara Do" initials="C." surname="Do"/>
<author fullname="Weronika Kolodziejak" initials="W." surname="Kolodziejak"/>
<author fullname="Juliusz Chroboczek" initials="J." surname="Chroboczek"/>
<date month="August" year="2019"/></front>
<seriesInfo name="Internet Draft" value="draft-ietf-babel-hmac-10"/>
</reference>
<reference anchor="RFC793" target="https://www.rfc-editor.org/info/rfc793">
<front>
<title>Transmission Control Protocol</title>
<author initials="J." surname="Postel" fullname="J. Postel"/>
<date year="1981" month="September"/>
</front>
<seriesInfo name="RFC" value="793"/>
<seriesInfo name="DOI" value="10.17487/RFC0793"/>
</reference>
</references>
<references title="Informative References">
<reference anchor="RFC6126"><front> <displayreference target="RFC0793" to="RFC793"/>
<title>The Babel Routing Protocol</title> <displayreference target="RFC2453" to="RIP"/>
<author initials="J." surname="Chroboczek" fullname="J. Chroboczek"/> <displayreference target="RFC5444" to="PACKETBB"/>
<date year="2011" month="April"/> <displayreference target="RFC2328" to="OSPF"/>
</front> <displayreference target="I-D.chroboczek-babel-diversity-routing" to="BABEL-DIVE
<seriesInfo name="RFC" value="6126"/> RSITY"/>
<seriesInfo name="DOI" value="10.17487/RFC6126"/> <displayreference target="I-D.ietf-babel-rtt-extension" to="BABEL-RTT"/>
</reference> <displayreference target="I-D.ietf-babel-source-specific" to="BABEL-SS"/>
<references>
<name>References</name>
<references>
<name>Normative References</name>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.2119.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.8174.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.8126.xml"/>
<reference anchor="RFC7557"><front> <reference anchor="RFC8967" target="https://www.rfc-editor.org/info/rfc8
<title>Extension Mechanism for the Babel Routing Protocol</title> 967">
<author initials="J." surname="Chroboczek" fullname="J. Chroboczek"/> <front>
<date year="2015" month="May"/> <title>MAC Authentication for the Babel Routing Protocol</title>
</front> <author fullname="Clara Dô" initials="C." surname="Dô">
<seriesInfo name="RFC" value="7557"/> <organization/>
<seriesInfo name="DOI" value="10.17487/RFC7557"/> </author>
</reference> <author fullname="Weronika Kolodziejak" initials="W." surname="Kolod
ziejak">
<organization/>
</author>
<author fullname="Juliusz Chroboczek" initials="J." surname="Chroboc
zek">
<organization/>
</author>
<date month="January" year="2021"/>
</front>
<seriesInfo name="RFC" value="8967"/>
<seriesInfo name="DOI" value="10.17487/RFC8967"/>
</reference>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.0793.xml"/>
</references>
<references>
<name>Informative References</name>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.6126.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.7557.xml"/>
<reference anchor="BABEL-DTLS"><front> <reference anchor="RFC8968" target="https://www.rfc-editor.org/info/rfc8
<title>Babel Routing Protocol over Datagram Transport Layer Security</title> 968">
<author fullname="Antonin Decimo" initials="A." surname="Decimo"/> <front>
<author fullname="David Schinazi" initials="D." surname="Schinazi"/> <title>Babel Routing Protocol over Datagram Transport Layer Security
<author fullname="Juliusz Chroboczek" initials="J." surname="Chroboczek"/> </title>
<date month="June" year="2020"/></front> <author fullname="Antonin Décimo" initials="A." surname="Décimo">
<seriesInfo name="Internet Draft" value="draft-ietf-babel-dtls-10"/> <organization/>
</reference> </author>
<author fullname="David Schinazi" initials="D." surname="Schinazi">
<organization/>
</author>
<author fullname="Juliusz Chroboczek" initials="J." surname="Chroboc
zek">
<organization/>
</author>
<date month="January" year="2021"/>
</front>
<seriesInfo name="RFC" value="8968"/>
<seriesInfo name="DOI" value="10.17487/RFC8968"/>
</reference>
<reference anchor="JITTER"><front> <reference anchor="JITTER">
<title>The synchronization of periodic routing messages</title> <front>
<author fullname="Sally Floyd" initials="S." surname="Floyd"/> <title>The Synchronization of Periodic Routing Messages</title>
<author fullname="Van Jacobson" initials="V." surname="Jacobson"/> <author fullname="Sally Floyd" initials="S." surname="Floyd"/>
<date month="April" year="1994"/> <author fullname="Van Jacobson" initials="V." surname="Jacobson"/>
</front> <date month="April" year="1994"/>
<seriesInfo name="IEEE/ACM Transactions on Networking" value="2, 2, 122-136"/> </front>
</reference> <refcontent>IEEE/ACM Transactions on Networking</refcontent>
<refcontent>2, 2, 122-136</refcontent>
<seriesInfo name="DOI" value="10.1109/90.298431"/>
</reference>
<reference anchor="DSDV"><front> <reference anchor="DSDV">
<title>Highly Dynamic Destination-Sequenced Distance-Vector Routing <front>
(DSDV) for Mobile Computers</title> <title>Highly dynamic Destination-Sequenced Distance-Vector routing
<author fullname="Charles Perkins" initials="C." surname="Perkins"/> (DSDV) for mobile computers</title>
<author fullname="Pravin Bhagwat" initials="P." surname="Bhagwat"/> <author fullname="Charles E. Perkins" initials="C." surname="Perkins
<date year="1994"/> "/>
</front> <author fullname="Pravin Bhagwat" initials="P." surname="Bhagwat"/>
<seriesInfo name="ACM SIGCOMM'94 Conference on Communications <date year="1994" month="October"/>
Architectures, Protocols and Applications" value="234-244"/> </front>
</reference> <refcontent>ACM SIGCOMM '94: Proceedings of the conference on
Communications architectures, protocols and applications</refcontent>
<refcontent>234-244</refcontent>
<seriesInfo name="DOI" value="10.1145/190314.190336"/>
</reference>
<reference anchor="RIP"><front> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<title>RIP Version 2</title> FC.2453.xml"/>
<author fullname="G. Malkin" initials="G." surname="Malkin"/>
<date month="November" year="1998"/>
</front>
<seriesInfo name="RFC" value="2453"/>
</reference>
<reference anchor="DUAL"><front> <reference anchor="DUAL">
<title>Loop-Free Routing Using Diffusing Computations</title> <front>
<author fullname="J. J. Garcia Luna Aceves" <title>Loop-free routing using diffusing computations</title>
initials="J. J." surname="Garcia Luna Aceves"/> <author fullname="J. J. Garcia Luna Aceves" initials="J. J." surname
<date month="February" year="1993"/> ="Garcia Luna Aceves"/>
</front> <date month="February" year="1993"/>
<seriesInfo name="IEEE/ACM Transactions on Networking" value="1:1"/> </front>
</reference> <refcontent>IEEE/ACM Transactions on Networking</refcontent>
<refcontent>1:1</refcontent>
<seriesInfo name="DOI" value="10.1109/90.222913"/>
</reference>
<reference anchor="OSPF"><front> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<title>OSPF Version 2</title> FC.2328.xml"/>
<author fullname="J. Moy" initials="J." surname="Moy"/>
<date month="April" year="1998"/>
</front>
<seriesInfo name="RFC" value="2328"/>
</reference>
<reference anchor="IS-IS"><front> <reference anchor="IS-IS">
<title>Information technology &mdash; Telecommunications and <front>
information exchange between systems &mdash; Intermediate System to <title>Information technology -- Telecommunications and
information exchange between systems -- Intermediate System to
Intermediate System intra-domain routeing information exchange protocol Intermediate System intra-domain routeing information exchange protocol
for use in conjunction with the protocol for providing the for use in conjunction with the protocol for providing the
connectionless-mode network service (ISO 8473)</title> connectionless-mode network service (ISO 8473)</title>
<author fullname="International Organization for Standardization"/> <author>
<date year="2002"/> <organization>International Organization for Standardization</orga
</front> nization>
<seriesInfo name="ISO/IEC" value="10589:2002"/> </author>
</reference> <date year="2002"/>
</front>
<reference anchor="EIGRP"><front> <refcontent>ISO/IEC 10589:2002</refcontent>
<title>EIGRP -- a Fast Routing Protocol Based on Distance Vectors</title> </reference>
<author fullname="Bob Albrigtson" initials="B." surname="Albrightson"/>
<author fullname="J. J. Garcia Luna Aceves"
initials="J. J." surname="Garcia Luna Aceves"/>
<author fullname="Joanne Boyle" initials="J." surname="Boyle"/>
<date year="1994"/>
</front>
<seriesInfo name="Proc. Interop" value="94"/>
</reference>
<reference anchor="RFC3561" target="https://www.rfc-editor.org/info/rfc3561">
<front>
<title>Ad hoc On-Demand Distance Vector (AODV) Routing</title>
<author initials="C." surname="Perkins" fullname="C. Perkins"/>
<author initials="E." surname="Belding-Royer" fullname="E. Belding-Royer"/>
<author initials="S." surname="Das" fullname="S. Das"/>
<date year="2003" month="July"/>
</front>
<seriesInfo name="RFC" value="3561"/>
<seriesInfo name="DOI" value="10.17487/RFC3561"/>
</reference>
<reference anchor="ETX"><front>
<title>A high-throughput path metric for multi-hop wireless networks</title>
<author fullname="Douglas S. J. De Couto" initials="D." surname="De Couto"/>
<author fullname="Daniel Aguayo" initials="D." surname="Aguayo"/>
<author fullname="John Bicket" initials="J." surname="Bicket"/>
<author fullname="Robert Morris" initials="R." surname="Morris"/>
<date year="2003"/>
</front>
<seriesInfo name="Proc. MobiCom" value="2003"/>
</reference>
<reference anchor="PACKETBB"><front>
<title>Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format</title>
<author fullname="T. Clausen" initials="T." surname="Clausen"/>
<author fullname="C. Dearlove" initials="C." surname="Dearlove"/>
<author fullname="J. Dean" initials="J." surname="Dean"/>
<author fullname="C. Adjih" initials="C." surname="Adjih"/>
<date month="February" year="2009"/>
</front>
<seriesInfo name="RFC" value="5444"/>
</reference>
<reference anchor="RFC7298"><front>
<title>Babel Hashed Message Authentication Code (HMAC) Cryptographic Authenticat
ion</title>
<author initials="D." surname="Ovsienko" fullname="D. Ovsienko"/>
<date year="2014" month="July"/>
</front>
<seriesInfo name="RFC" value="7298"/>
<seriesInfo name="DOI" value="10.17487/RFC7298"/>
</reference>
<reference anchor="BABEL-SS"><front> <reference anchor="EIGRP">
<title>Source-Specific Routing in Babel</title> <front>
<author initials="M" surname="Boutier" fullname="Matthieu Boutier"/> <title>EIGRP -- a Fast Routing Protocol Based on Distance Vectors</t
<author initials="J" surname="Chroboczek" fullname="Juliusz Chroboczek"/> itle>
<date month="April" day="11" year="2019"/> <author fullname="Bob Albrightson" initials="B." surname="Albrightso
</front> n"/>
<seriesInfo name="Internet-Draft" value="draft-ietf-babel-source-specific-05" /> <author fullname="J. J. Garcia Luna Aceves" initials="J. J." surname
</reference> ="Garcia Luna Aceves"/>
<author fullname="Joanne Boyle" initials="J." surname="Boyle"/>
<date year="1994"/>
</front>
<refcontent>Proc. Networld/Interop 94</refcontent>
</reference>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
FC.3561.xml"/>
<reference anchor="BABEL-RTT"><front> <reference anchor="ETX">
<title>Delay-based Metric Extension for the Babel Routing Protocol</title> <front>
<author initials="B" surname="Jonglez" fullname="Baptiste Jonglez"/> <title>A high-throughput path metric for multi-hop wireless networks
<author initials="J" surname="Chroboczek" fullname="Juliusz Chroboczek"/> </title>
<date month="April" day="26" year="2019"/> <author fullname="Douglas S. J. De Couto" initials="D." surname="De
</front> Couto"/>
<seriesInfo name="Internet-Draft" value="draft-ietf-babel-rtt-extension-00" /> <author fullname="Daniel Aguayo" initials="D." surname="Aguayo"/>
</reference> <author fullname="John Bicket" initials="J." surname="Bicket"/>
<author fullname="Robert Morris" initials="R." surname="Morris"/>
<date year="2003" month="September"/>
</front>
<refcontent>MobiCom '03: Proceedings of the 9th annual international
conference on Mobile computing and networking</refcontent>
<refcontent>134-146</refcontent>
<seriesInfo name="DOI" value="10.1145/938985.939000"/>
</reference>
<reference anchor="BABEL-DIVERSITY"><front> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<title>Diversity Routing for the Babel Routing Protocol</title> FC.5444.xml"/>
<author initials="J" surname="Chroboczek" fullname="Juliusz Chroboczek"/> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<date month="February" day="15" year="2016"/> FC.7298.xml"/>
</front> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D
<seriesInfo name="Internet-Draft" value="draft-chroboczek-babel-diversity-routin .ietf-babel-source-specific.xml"/>
g-01" /> <xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D
</reference> .ietf-babel-rtt-extension.xml"/>
<xi:include href="https://datatracker.ietf.org/doc/bibxml3/reference.I-D
.chroboczek-babel-diversity-routing.xml"/>
<reference anchor="IEEE802.11"><front> <reference anchor="IEEE802.11">
<title>IEEE Standard for Information technology--Telecommunications and <front>
<title>IEEE Standard for Information technology--Telecommunications
and
information exchange between systems Local and metropolitan area information exchange between systems Local and metropolitan area
networks--Specific requirements Part 11: Wireless LAN Medium Access networks--Specific requirements Part 11: Wireless LAN Medium Access
Control (MAC) and Physical Layer (PHY) Specifications</title> Control (MAC) and Physical Layer (PHY) Specifications</title>
<author><organization>IEEE</organization></author> <author>
<date day="5" month="April" year="2012"/> <organization>IEEE</organization>
</front> </author>
<seriesInfo name='IEEE' value='802.11-2012' /> <date month="April" year="2012"/>
<seriesInfo name='DOI' value='10.1109/ieeestd.2012.6178212' /> </front>
</reference> <seriesInfo name="IEEE" value="802.11-2012"/>
<seriesInfo name="DOI" value="10.1109/ieeestd.2012.6178212"/>
<reference anchor="RFC2675"><front> </reference>
<title>IPv6 Jumbograms</title> <xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.R
<author initials="D." surname="Borman" fullname="D. Borman"/> FC.2675.xml"/>
<author initials="S." surname="Deering" fullname="S. Deering"/>
<author initials="R." surname="Hinden" fullname="R. Hinden"/>
<date year="1999" month="August"/>
</front>
<seriesInfo name="RFC" value="2675"/>
<seriesInfo name="DOI" value="10.17487/RFC2675"/>
</reference>
<reference anchor="IEN137"><front>
<title>On holy wars and a plea for peace</title>
<author initials="D." surname="Cohen" fullname="Dany Cohen"/>
<date day="1" month="April" year="1980"/>
</front>
<seriesInfo name="IEN" value="137"/>
</reference>
</references>
<section title="Cost and Metric Computation"> <reference anchor="IEN137">
<front>
<title>On Holy Wars and a Plea for Peace</title>
<author initials="D." surname="Cohen" fullname="Danny Cohen"/>
<date day="1" month="April" year="1980"/>
</front>
<seriesInfo name="IEN" value="137"/>
</reference>
<t>The strategy for computing link costs and route metrics is a local </references>
</references>
<section numbered="true" toc="default">
<name>Cost and Metric Computation</name>
<t>The strategy for computing link costs and route metrics is a local
matter; Babel itself only requires that it comply with the conditions given matter; Babel itself only requires that it comply with the conditions given
in <xref target="cost-computation"/> and <xref target="metric-computation"/>. in <xref target="cost-computation" format="default"/> and <xref target="metric-c omputation" format="default"/>.
Different nodes may use different strategies in a single network and may Different nodes may use different strategies in a single network and may
use different strategies on different interface types. This section describes use different strategies on different interface types. This section describes
a set of strategies that have been found to work well in actual networks.</t> a set of strategies that have been found to work well in actual networks.</t>
<t>In summary, a node maintains per-neighbour statistics about the last 16
<t>In summary, a node maintains per-neighbour statistics about the last 16 received Hello TLVs of each kind (<xref target="hello-history" format="default"/
received Hello TLVs of each kind (<xref target="hello-history"/>), >),
it computes costs by using the 2-out-of-3 strategy (<xref target="k-j"/>) on it computes costs by using the 2-out-of-3 strategy (<xref target="k-j" format="d
wired links, and ETX (<xref target="etx"/>) on wireless links. It uses an efault"/>) on
additive algebra for metric computation (<xref target="metric-computation"/>).</ wired links and Expected Transmission Cost (ETX) (<xref target="etx" format="def
t> ault"/>) on wireless links. It uses an
additive algebra for metric computation (<xref target="metric-computation" forma
<section title="Maintaining Hello History" anchor="hello-history"> t="default"/>).</t>
<section anchor="hello-history" numbered="true" toc="default">
<t>For each neighbour, a node maintains two sets of Hello history, one for <name>Maintaining Hello History</name>
<t>For each neighbour, a node maintains two sets of Hello history, one f
or
each kind of Hello, and an expected sequence number, one for Multicast and each kind of Hello, and an expected sequence number, one for Multicast and
one for Unicast Hellos. Each Hello history is a vector of 16 bits, where one for Unicast Hellos. Each Hello history is a vector of 16 bits, where
a 1 value represents a received Hello, and a 0 value a missed Hello. For a 1 value represents a received Hello, and a 0 value a missed Hello. For
each kind of Hello, the expected sequence number, written ne, is the each kind of Hello, the expected sequence number, written ne, is the
sequence number that is expected to be carried by the next received Hello sequence number that is expected to be carried by the next received Hello
from this neighbour.</t> from this neighbour.</t>
<t>Whenever it receives a Hello packet of a given kind from a neighbour,
<t>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 Hello a node compares the received sequence number nr for that kind of Hello
with its expected sequence number ne. Depending on the outcome of this with its expected sequence number ne. Depending on the outcome of this
comparison, one of the following actions is taken: comparison, one of the following actions is taken:
<list style="symbols"> </t>
<t>if the two differ by more than 16 (modulo 2^16), then the sending <ul spacing="normal">
<li>if the two differ by more than 16 (modulo 2<sup>16</sup>), then th
e 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 is created;</t> associated neighbour table entry is flushed and a new one is created;</li>
<t>otherwise, if the received nr is smaller (modulo 2^16) than the <li>otherwise, if the received nr is smaller (modulo 2<sup>16</sup>) t
han the
expected sequence number ne, then the sending node has increased its expected sequence number ne, then the sending node has increased its
Hello interval without us noticing; the receiving node removes the last Hello interval without our noticing; the receiving node removes the last
(ne - nr) entries from this neighbour's Hello history (we "undo (ne - nr) entries from this neighbour's Hello history (we "undo
history");</t> history");</li>
<t>otherwise, if nr is larger (modulo 2^16) than ne, then the sending <li>otherwise, if nr is larger (modulo 2<sup>16</sup>) than ne, then t
he sending
node has decreased its Hello interval, and some Hellos were lost; the node has decreased its Hello interval, and some Hellos were lost; the
receiving node adds (nr - ne) 0 bits to the Hello history (we receiving node adds (nr - ne) 0 bits to the Hello history (we
"fast-forward").</t> "fast-forward").</li>
</list> </ul>
<t>
The receiving node then appends a 1 bit to the Hello history and sets ne The receiving node then appends a 1 bit to the Hello history and sets ne
to (nr + 1). If the Interval field of the received Hello is not zero, it to (nr + 1). If the Interval field of the received Hello is not zero, it
resets the neighbour's hello timer to 1.5 times the advertised Interval resets the neighbour's hello timer to 1.5 times the advertised Interval
(the extra margin allows for delay due to jitter).</t> (the extra margin allows for delay due to jitter).</t>
<t>Whenever either hello timer associated with a neighbour expires, the
<t>Whenever either Hello timer associated to a neighbour expires, the
local node adds a 0 bit to the corresponding Hello history, and increments local node adds a 0 bit to the corresponding Hello history, and increments
the expected Hello number. If both Hello histories are empty (they the expected Hello number. If both Hello histories are empty (they
contain 0 bits only), the neighbour entry is flushed; otherwise, the contain 0 bits only), the neighbour entry is flushed; otherwise, the
relevant hello timer is reset to the value advertised in the last Hello of relevant hello timer is reset to the value advertised in the last Hello of
that kind received from this neighbour (no extra margin is necessary in that kind received from this neighbour (no extra margin is necessary in
this case, since jitter was already taken into account when computing the this case, since jitter was already taken into account when computing the
timeout that has just expired).</t> timeout that has just expired).</t>
</section>
</section> <section anchor="cost-computation-examples" numbered="true" toc="default">
<name>Cost Computation</name>
<section title="Cost Computation" anchor="cost-computation-examples"> <t>This section describes two algorithms suitable for computing costs
(<xref target="cost-computation" format="default"/>) based on Hello history.
<t>This section describes two algorithms suitable for computing costs <xref target="k-j" format="default"/> applies to wired links and <xref target="e
(<xref target="cost-computation"/>) based on Hello history. tx" format="default"/> to
<xref target="k-j"/> applies to wired links, and <xref target="etx"/> to wireless links. <bcp14>RECOMMENDED</bcp14> default values of the parameters tha
wireless links. RECOMMENDED default values of the parameters that appear t appear
in these algorithms are given in <xref target="parameters"/>.</t> in these algorithms are given in <xref target="parameters" format="default"/>.</
t>
<section title="k-out-of-j" anchor="k-j"> <section anchor="k-j" numbered="true" toc="default">
<name>k-out-of-j</name>
<t>K-out-of-j link sensing is suitable for wired links that are either up, <t>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 which case in which case they only occasionally drop a packet, or down, in which case
they drop all packets.</t> they drop all packets.</t>
<t>The k-out-of-j strategy is parameterised by two small integers k an
<t>The k-out-of-j strategy is parameterised by two small integers k and j, d j,
such that 0 &lt; k &le; j, and the nominal link cost, a constant C &ge; 1. such that 0 &lt; k &lt;= j, and the nominal link cost, a constant C &gt;= 1.
A node keeps a history of the last j hellos; if k or more of those have A node keeps a history of the last j hellos; if k or more of those have
been correctly received, the link is assumed to be up, and the rxcost is been correctly received, the link is assumed to be up, and the rxcost is
set to C; otherwise, the link is assumed to be down, and the rxcost is set set to C; otherwise, the link is assumed to be down, and the rxcost is set
to infinity.</t> to infinity.</t>
<t>Since Babel supports two kinds of Hellos, a Babel node performs
<t>Since Babel supports two kinds of Hellos, a Babel node performs k-out-of-j twice for each neighbour, once on the Unicast Hello history and once
k-out-of-j twice for each neighbour, once on the Unicast and once on the on the
Multicast Hello history. If either of the instances of k-out-of-j Multicast Hello history. If either of the instances of k-out-of-j
indicates that the link is up, then the link is assumed to be up, and the indicates that the link is up, then the link is assumed to be up, and the
rxcost is set to C; if both instances indicate that the link is down, then rxcost is set to C; if both instances indicate that the link is down, then
the link is assumed to be down, and the rxcost is set to infinity. In the link is assumed to be down, and the rxcost is set to infinity. In
other words, the resulting rxcost is the minimum of the rxcosts yielded by other words, the resulting rxcost is the minimum of the rxcosts yielded by
the two instances of k-out-of-j link sensing.</t> the two instances of k-out-of-j link sensing.</t>
<t>The cost of a link performing k-out-of-j link sensing is defined as
<t>The cost of a link performing k-out-of-j link sensing is defined as
follows: follows:
<list style="symbols"> </t>
<t>cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;</t> <ul spacing="normal">
<t>cost = txcost otherwise.</t> <li>cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;</li>
</list> <li>cost = txcost otherwise.</li>
</t> </ul>
</section>
</section> <section anchor="etx" numbered="true" toc="default">
<name>ETX</name>
<section title="ETX" anchor="etx"> <t>Unlike wired links which are bimodal (either up or down), wireless
<t>Unlike wired links which are bimodal (either up or down), wireless
links exhibit continuous variation of the link quality. Naive application links exhibit continuous variation of the link quality. Naive application
of hop-count routing in networks that use wireless links for transit tends of hop-count routing in networks that use wireless links for transit tends
to select long, lossy links in preference to shorter, lossless links, to select long, lossy links in preference to shorter, lossless links,
which can dramatically reduce throughput. For that reason, a routing which can dramatically reduce throughput. For that reason, a routing
protocol designed to support wireless links must perform some form of protocol designed to support wireless links must perform some form of
link-quality estimation.</t> link quality estimation.</t>
<t>The Expected Transmission Cost algorithm, or ETX <xref target="ETX"
<t>The Expected Transmission Cost algorithm, or ETX <xref target="ETX"/>, format="default"/>,
is a simple link-quality estimation algorithm that is designed to work is a simple link quality estimation algorithm that is designed to work
well with the IEEE&nbsp;802.11 MAC <xref target="IEEE802.11"/>. By well with the IEEE&nbsp;802.11 MAC <xref target="IEEE802.11" format="default"/>.
By
default, the IEEE&nbsp;802.11 MAC performs Automatic Repeat Query (ARQ) default, the IEEE&nbsp;802.11 MAC performs Automatic Repeat Query (ARQ)
and rate adaptation on unicast frames, but not on multicast frames, which and rate adaptation on unicast frames, but not on multicast frames, which
are sent at a fixed rate with no ARQ; therefore, measuring the loss rate are sent at a fixed rate with no ARQ; therefore, measuring the loss rate
of multicast frames yields a useful estimate of a link's quality.</t> of multicast frames yields a useful estimate of a link's quality.</t>
<t>A node performing ETX link quality estimation uses a neighbour's
<t>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
computed as the fraction of 1 bits within a small number (say, 6) of the computed as the fraction of 1 bits within a small number (say, 6) of the
most recent entries in the Multicast Hello history, or it can be an most recent entries in the Multicast Hello history, or it can be an
exponential average, or some combination of both approaches. Let rxcost exponential average, or some combination of both approaches. Let rxcost
be 256 / beta.</t> be 256/beta.</t>
<t>Let alpha be MIN(1, 256/txcost), an estimate of the probability of
<t>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
<list style="empty"><t>cost = 256/(alpha * beta)</t></list> </t>
<t indent="3">cost = 256/(alpha * beta)</t>
<t>
or, equivalently, or, equivalently,
<list style="empty"><t>cost = (MAX(txcost, 256) * rxcost) / 256.</t></list> </t>
</t> <t indent="3">cost = (MAX(txcost, 256) * rxcost) / 256.</t>
<t>Since the IEEE&nbsp;802.11 MAC performs ARQ on unicast frames, unic
<t>Since the IEEE&nbsp;802.11 MAC performs ARQ on unicast frames, unicast ast
frames do not provide a useful measure of link quality, and therefore ETX frames do not provide a useful measure of link quality, and therefore ETX
ignores the Unicast Hello history. Thus, a node performing ETX ignores the Unicast Hello history. Thus, a node performing ETX
link-quality estimation will not route through neighbouring nodes unless link quality estimation will not route through neighbouring nodes unless
they send periodic Multicast Hellos (possibly in addition to Unicast they send periodic Multicast Hellos (possibly in addition to Unicast
Hellos).</t> Hellos).</t>
</section>
</section> </section>
<section anchor="route-selection-hysteresis" numbered="true" toc="default"
</section> >
<name>Route Selection and Hysteresis</name>
<section title="Route selection and hysteresis" <t>Route selection (<xref target="route-selection" format="default"/>) i
anchor="route-selection-hysteresis"> s the process by
<t>Route selection (<xref target="route-selection"/>) is the process by
which a node selects a single route among the routes that it has available which a node selects a single route among the routes that it has available
towards a given destination. With Babel, any route selection procedure towards a given destination. With Babel, any route selection procedure
that only ever chooses feasible routes with a finite metric will yield that only ever chooses feasible routes with a finite metric will yield
a set of loop-free routes; however, in the presence of continuously a set of loop-free routes; however, in the presence of continuously
variable metrics such as ETX (<xref target="etx"/>), a naive route variable metrics such as ETX (<xref target="etx" format="default"/>), a naive ro ute
selection procedure might lead to persistent oscillations. Such selection procedure might lead to persistent oscillations. Such
oscillations can be limited or avoided altogether by implementing oscillations can be limited or avoided altogether by implementing
hysteresis within the route selection algorithm, i.e., by making the route hysteresis within the route selection algorithm, i.e., by making the route
selection algorithm sensitive to a route's history. Any reasonable selection algorithm sensitive to a route's history. Any reasonable
hysteresis algorithm should yield good results; the following algorithm hysteresis algorithm should yield good results; the following algorithm
is simple to implement and has been successfully deployed in a variety of is simple to implement and has been successfully deployed in a variety of
environments.</t> environments.</t>
<t>For every route R, in addition to the route's metric m(R), maintain
<t>For every route R, in addition to the route's metric m(R), maintain
a smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R) as an a smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R) as an
exponentially smoothed average (see Section 3.7 of <xref target="RFC793"/>) exponentially smoothed average (see <xref target="RFC0793" section="3.7" section Format="of" format="default"/>)
of m(R) with a time constant equal to the Hello interval multiplied by of m(R) with a time constant equal to the Hello interval multiplied by
a small number such as 3). If no route to a given destination is selected, a small number such as 3). If no route to a given destination is selected,
then select the route with the smallest metric, ignoring the smoothed then select the route with the smallest metric, ignoring the smoothed
metric. If a route R is selected, then switch to a route R' only when metric. If a route R is selected, then switch to a route R' only when
both m(R')&nbsp;&lt;&nbsp;m(R) and ms(R')&nbsp;&lt;&nbsp;ms(R).</t> both m(R')&nbsp;&lt;&nbsp;m(R) and ms(R')&nbsp;&lt;&nbsp;ms(R).</t>
<t>Intuitively, the smoothed metric is a long-term estimate of the quali
<t>Intuitively, the smoothed metric is a long-term estimate of the quality ty
of a route. The algorithm above works by only switching routes when both of a route. The algorithm above works by only switching routes when both
the instantaneous and the long-term estimate of the route's quality the instantaneous and the long-term estimates of the route's quality
indicate that switching is profitable.</t> indicate that switching is profitable.</t>
</section>
</section> </section>
<section anchor="parameters" numbered="true" toc="default">
</section> <name>Protocol Parameters</name>
<t>The choice of time constants is a trade-off between fast detection of
<section title="Protocol parameters" anchor="parameters">
<t>The choice of time constants is a trade-off between fast detection of
mobility events and protocol overhead. Two instances of Babel running mobility events and protocol overhead. Two instances of Babel running
with different time constants will interoperate, although the resulting with different time constants will interoperate, although the resulting
worst-case convergence time will be dictated by the slower of the two.</t> worst-case convergence time will be dictated by the slower of the two.</t>
<t>The Hello interval is the most important time constant: an outage or
<t>The Hello interval is the most important time constant: an outage or
a mobility event is detected within 1.5 to 3.5 Hello intervals. Due to a mobility event is detected within 1.5 to 3.5 Hello intervals. Due to
Babel's use of a redundant route table, and due to its reliance on Babel's use of a redundant route table, and due to its reliance on
triggered updates and explicit requests, the Update interval has little triggered updates and explicit requests, the Update interval has little
influence on the time needed to reconverge after an outage: in practice, influence on the time needed to reconverge after an outage: in practice,
it only has a significant effect on the time needed to acquire new routes it only has a significant effect on the time needed to acquire new routes
after a mobility event. While the protocol allows intervals as low as after a mobility event. While the protocol allows intervals as low as
10ms, such low values would cause significant amounts of protocol traffic 10 ms, such low values would cause significant amounts of protocol traffic
for little practical benefit.</t> for little practical benefit.</t>
<t>The following values have been found to work well in a variety of
<t>The following values have been found to work well in a variety of environments and are therefore <bcp14>RECOMMENDED</bcp14> default values:
environments, and are therefore RECOMMENDED default values: </t>
<list style="empty"> <dl spacing="normal" indent="10">
<t>Multicast Hello Interval: 4 seconds.</t> <dt>Multicast Hello interval:</dt><dd>4 seconds.</dd>
<t>Unicast Hello Interval: infinite (no Unicast Hellos are sent).</t> <dt>Unicast Hello interval:</dt><dd>infinite (no Unicast Hellos are sent
<t>Link cost: estimated using ETX on wireless links; 2-out-of-3 with C=96 ).</dd>
on wired links.</t> <dt>Link cost:</dt><dd>estimated using ETX on wireless links; 2-out-of-3
<t>IHU Interval: the advertised IHU interval is always 3 times the with C=96
on wired links.</dd>
<dt>IHU interval:</dt><dd>the advertised IHU interval is always 3 times
the
Multicast Hello interval. IHUs are actually sent with each Hello on lossy Multicast Hello interval. IHUs are actually sent with each Hello on lossy
links (as determined from the Hello history), but only with every third links (as determined from the Hello history), but only with every third
Multicast Hello on lossless links.</t> Multicast Hello on lossless links.</dd>
<t>Update Interval: 4 times the Multicast Hello interval.</t> <dt>Update interval:</dt><dd>4 times the Multicast Hello interval.</dd>
<t>IHU Hold Time: 3.5 times the advertised IHU interval.</t> <dt>IHU Hold time:</dt><dd>3.5 times the advertised IHU interval.</dd>
<t>Route Expiry Time: 3.5 times the advertised update interval.</t> <dt>Route Expiry time:</dt><dd>3.5 times the advertised update interval.
<t>Request timeout: initially 2 seconds, doubled every time a request is </dd>
resent, up to a maximum of three times.</t> <dt>Request timeout:</dt><dd>initially 2 seconds, doubled every time a r
<t>Urgent timeout: 0.2 seconds.</t> equest is
<t>Source GC time: 3 minutes.</t> resent, up to a maximum of three times.</dd>
</list></t> <dt>Urgent timeout:</dt><dd>0.2 seconds.</dd>
<dt>Source GC time:</dt><dd>3 minutes.</dd>
</section> </dl>
</section>
<section title="Route filtering" anchor="filtering"> <section anchor="filtering" numbered="true" toc="default">
<name>Route Filtering</name>
<t>Route filtering is a procedure where an instance of a routing protocol <t>Route filtering is a procedure where an instance of a routing protocol
either discards some of the routes announced by its neighbours, or learns either discards some of the routes announced by its neighbours or learns
them with a metric that is higher than what would be expected. Like all them with a metric that is higher than what would be expected. Like all
distance-vector protocols, Babel has the ability to apply arbitrary distance-vector protocols, Babel has the ability to apply arbitrary
filtering to the routes it learns, and implementations of Babel that apply filtering to the routes it learns, and implementations of Babel that apply
different sets of filtering rules will interoperate without causing different sets of filtering rules will interoperate without causing
routing loops. The protocol's ability to perform route filtering is routing loops. The protocol's ability to perform route filtering is
a consequence of the latitude given in <xref target="metric-computation"/>: a consequence of the latitude given in <xref target="metric-computation" format= "default"/>:
Babel can use any metric that is strictly monotonic, including one that Babel can use any metric that is strictly monotonic, including one that
assigns an infinite metric to a selected subset of routes. (See also assigns an infinite metric to a selected subset of routes. (See also
<xref target="handling-requests"/>, where requests for nonexistent routes <xref target="handling-requests" format="default"/>, where requests for nonexist ent routes
are treated in the same way as requests for routes with infinite metric.)</t> are treated in the same way as requests for routes with infinite metric.)</t>
<t>It is not in general correct to learn a route with a metric smaller
<t>It is not in general correct to learn a route with a metric smaller
than the one it was announced with, or to replace a route's destination than the one it was announced with, or to replace a route's destination
prefix with a more specific (longer) one. Doing either of these may cause prefix with a more specific (longer) one. Doing either of these may cause
persistent routing loops.</t> persistent routing loops.</t>
<t>Route filtering is a useful tool, since it allows fine-grained tuning
<t>Route filtering is a useful tool, since it allows fine-grained tuning
of the routing decisions made by the routing protocol. Accordingly, some of the routing decisions made by the routing protocol. Accordingly, some
implementations of Babel implement a rich configuration language that implementations of Babel implement a rich configuration language that
allows applying filtering to sets of routes defined, for example, by allows applying filtering to sets of routes defined, for example, by
incoming interface and destination prefix.</t> incoming interface and destination prefix.</t>
<t>In order to limit the consequences of misconfiguration, Babel
<t>In order to limit the consequences of misconfiguration, Babel
implementations provide a reasonable set of default filtering rules even implementations provide a reasonable set of default filtering rules even
when they don't allow configuration of filtering by the user. At when they don't allow configuration of filtering by the user. At
a minimum, they discard routes with a destination prefix in fe80::/64, a minimum, they discard routes with a destination prefix in fe80::/64,
ff00::/8, 127.0.0.1/32, 0.0.0.0/32 and 224.0.0.0/8.</t> ff00::/8, 127.0.0.1/32, 0.0.0.0/32, and 224.0.0.0/8.</t>
</section>
</section> <section anchor="extensions" numbered="true" toc="default">
<name>Considerations for Protocol Extensions</name>
<section title="Considerations for protocol extensions" anchor="extensions"> <t>Babel is an extensible protocol, and this document defines a number of
<t>Babel is an extensible protocol, and this document defines a number of
mechanisms that can be used to extend the protocol in a backwards mechanisms that can be used to extend the protocol in a backwards
compatible manner: compatible manner:
<list style="symbols"> </t>
<t>increasing the version number in the packet header;</t> <ul spacing="normal">
<t>defining new TLVs;</t> <li>increasing the version number in the packet header;</li>
<t>defining new sub-TLVs (with or without the mandatory bit set);</t> <li>defining new TLVs;</li>
<t>defining new AEs;</t> <li>defining new sub-TLVs (with or without the mandatory bit set);</li>
<t>using the packet trailer.</t> <li>defining new AEs;</li>
</list></t> <li>using the packet trailer.</li>
</ul>
<t>This appendix is intended to guide designers of protocol extensions in <t>This appendix is intended to guide designers of protocol extensions in
choosing a particular encoding.</t> choosing a particular encoding.</t>
<t>The version number in the Babel header should only be increased if the
<t>The version number in the Babel header should only be increased if the
new version is not backwards compatible with the original protocol.</t> new version is not backwards compatible with the original protocol.</t>
<t>In many cases, an extension could be implemented either by defining
<t>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, an
a 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 updates can extension whose purpose is to attach additional data to route updates can
be implemented either by creating a new "enriched" Update TLV, by adding be implemented either by creating a new "enriched" Update TLV, by adding
a non-mandatory sub-TLV to the Update TLV, or by adding a mandatory a nonmandatory sub-TLV to the Update TLV, or by adding a mandatory
sub-TLV.</t> sub-TLV.</t>
<t>The various encodings are treated differently by implementations that
<t>The various encodings are treated differently by implementations that
do not understand the extension. In the case of a new TLV or of a sub-TLV 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 implementations with the mandatory bit set, the whole TLV is ignored by implementations
that do not implement the extension, while in the case of a non-mandatory that do not implement the extension, while in the case of a nonmandatory
sub-TLV, the TLV is parsed and acted upon, and only the unknown sub-TLV is sub-TLV, the TLV is parsed and acted upon, and only the unknown sub-TLV is
silently ignored. Therefore, a non-mandatory sub-TLV should be used by silently ignored. Therefore, a nonmandatory sub-TLV should be used by
extensions that extend the Update in a compatible manner (the extension extensions that extend the Update in a compatible manner (the extension
data may be silently ignored), while a mandatory sub-TLV or a new TLV must data may be silently ignored), while a mandatory sub-TLV or a new TLV must
be used by extensions that make incompatible extensions to the meaning of be used by extensions that make incompatible extensions to the meaning of
the TLV (the whole TLV must be thrown away if the extension data is not the TLV (the whole TLV must be thrown away if the extension data is not
understood).</t> understood).</t>
<t>Experience shows that the need for additional data tends to crop up in
<t>Experience shows that the need for additional data tends to crop up in
the most unexpected places. Hence, it is recommended that extensions that the most unexpected places. Hence, it is recommended that extensions that
define new TLVs should make them self-terminating, and allow attaching define new TLVs should make them self-terminating and allow attaching
sub-TLVs to them.</t> sub-TLVs to them.</t>
<t>Adding a new AE is essentially equivalent to adding a new TLV: Update
<t>Adding a new AE is essentially equivalent to adding a new TLV: Update
TLVs with an unknown AE are ignored, just like unknown TLVs. However, TLVs with an unknown AE are ignored, just like unknown TLVs. However,
adding a new AE is more involved than adding a new TLV, since it creates adding a new AE is more involved than adding a new TLV, since it creates
a new set of compression state. Additionally, since the Next Hop TLV a new set of compression state. Additionally, since the Next Hop TLV
creates state specific to a given address family, as opposed to a given creates state specific to a given address family, as opposed to a given
AE, a new AE for a previously defined address family must not be used in AE, a new AE for a previously defined address family must not be used in
the Next Hop TLV if backwards compatibility is required. A similar issue the Next Hop TLV if backwards compatibility is required. A similar issue
arises with Update TLVs with unknown AEs establishing a new router-id (due arises with Update TLVs with unknown AEs establishing a new router-id (due
to the Router-Id flag being set). Therefore, defining new AEs must be to the Router-Id flag being set). Therefore, defining new AEs must be
done with care if compatibility with unextended implementations is done with care if compatibility with unextended implementations is
required.</t> required.</t>
<t>The packet trailer is intended to carry cryptographic signatures that
<t>The packet trailer is intended to carry cryptographic signatures that
only cover the packet body; storing the cryptographic signatures in the only cover the packet body; storing the cryptographic signatures in the
packet trailer avoids clearing the signature before computing a hash of packet trailer avoids clearing the signature before computing a hash of
the packet body, and makes it possible to check a cryptographic signature the packet body, and makes it possible to check a cryptographic signature
before running the full, stateful TLV parser. Hence, only TLVs that don't before running the full, stateful TLV parser. Hence, only TLVs that don't
need to be protected by cryptographic security protocols should be allowed need to be protected by cryptographic security protocols should be allowed
in the packet trailer. Any such TLVs should be easy to parse, and in in the packet trailer. Any such TLVs should be easy to parse and, in
particular should not require stateful parsing.</t> particular, should not require stateful parsing.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Stub Implementations</name>
<section title="Stub Implementations"> <t>Babel is a fairly economic protocol. Updates take between 12 and 40
<t>Babel is a fairly economic protocol. Updates take between 12 and 40
octets per destination, depending on the address family and how successful octets per destination, depending on the address family and how successful
compression is; in a double-stack flat network, an average of less than 24 compression is; in a dual-stack flat network, an average of less than 24
octets per update is typical. The route table occupies about 35 octets octets per update is typical. The route table occupies about 35 octets
per IPv6 entry. To put these values into perspective, a single full-size per IPv6 entry. To put these values into perspective, a single full-size
Ethernet frame can carry some 65 route updates, and a megabyte of memory Ethernet frame can carry some 65 route updates, and a megabyte of memory
can contain a 20000-entry route table and the associated source table.</t> can contain a 20,000-entry route table and the associated source table.</t>
<t>Babel is also a reasonably simple protocol. One complete implementatio
<t>Babel is also a reasonably simple protocol. One complete implementation n
consists of less than 12&nbsp;000 lines of C code, and it compiles to less consists of less than 12,000 lines of C code, and it compiles to less
than 120&nbsp;kB of text on a 32-bit CISC architecture; about half of this than 120 KB of text on a 32-bit CISC architecture; about half of this
figure is due to protocol extensions and user-interface code.</t> figure is due to protocol extensions and user-interface code.</t>
<t>Nonetheless, in some very constrained environments, such as PDAs,
<t>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.</t> implementations of the protocol.</t>
<t>There are many different definitions of a stub router, but for the
<t>There are many different definitions of a stub router, but for the needs of this section, a stub implementation of Babel is one that announces
needs of this section a stub implementation of Babel is one that announces
one or more directly attached prefixes into a Babel network but doesn't one or more directly attached prefixes into a Babel network but doesn't
reannounce any routes that it has learnt from its neighbours, and always re-announce any routes that it has learnt from its neighbours, and always
prefers the direct route to a directly attached prefix to a route learned prefers the direct route to a directly attached prefix to a route learnt
over the Babel protocol, even when the prefixes are the same. It may over the Babel protocol, even when the prefixes are the same. It may
either maintain a full routing table, or simply select a default gateway either maintain a full routing table or simply select a default gateway
through any one of its neighbours that announces a default route. Since through any one of its neighbours that announces a default route. Since
a stub implementation never forwards packets except from or to a directly a stub implementation never forwards packets except from or to a directly
attached link, it cannot possibly participate in a routing loop, and hence attached link, it cannot possibly participate in a routing loop, and hence
it need not evaluate the feasibility condition or maintain a source it need not evaluate the feasibility condition or maintain a source
table.</t> table.</t>
<t>No matter how primitive, a stub implementation must parse sub-TLVs
<t>No matter how primitive, a stub implementation must parse sub-TLVs
attached to any TLVs that it understands and check the mandatory bit. attached to any TLVs that it understands and check the mandatory bit.
It must answer acknowledgment requests and must participate in the It must answer acknowledgment requests and must participate in the
Hello/IHU protocol. It must also be able to reply to seqno requests for Hello/IHU protocol. It must also be able to reply to seqno requests for
routes that it announces and, and it should be able to reply to route routes that it announces, and it should be able to reply to route
requests.</t> requests.</t>
<t>Experience shows that an IPv6-only stub implementation of Babel can be
<t>Experience shows that an IPv6-only stub implementation of Babel can be written in less than 1,000 lines of C code and compile to 13 KB of
written in less than 1000 lines of C code and compile to 13&nbsp;kB of
text on 32-bit CISC architecture.</t> text on 32-bit CISC architecture.</t>
</section>
</section> <section numbered="true" toc="default">
<name>Compatibility with Previous Versions</name>
<section title="Compatibility with previous versions"> <t>The protocol defined in this document is a successor to the protocol
defined in <xref target="RFC6126" format="default"/> and <xref target="RFC7557"
<t>The protocol defined in this document is a successor to the protocol format="default"/>. While
defined in <xref target="RFC6126"/> and <xref target="RFC7557"/>. While
the two protocols are not entirely compatible, the new protocol has been the two protocols are not entirely compatible, the new protocol has been
designed so that it can be deployed in existing RFC 6126 networks without designed so that it can be deployed in existing RFC 6126 networks without
requiring a flag day.</t> requiring a flag day.</t>
<t>There are three optional features that make this protocol
<t>There are three optional features that make this protocol
incompatible with its predecessor. First of all, RFC 6126 did not define incompatible with its predecessor. First of all, RFC 6126 did not define
Unicast hellos (<xref target="reverse-reachability"/>), and an Unicast Hellos (<xref target="reverse-reachability" format="default"/>), and an
implementation of RFC 6126 will mis-interpret a Unicast Hello for implementation of RFC 6126 will misinterpret a Unicast Hello for
a Multicast one; since the sequence number space of Unicast Hellos is a Multicast one; since the sequence number space of Unicast Hellos is
distinct from the sequence space of Multicast Hellos, sending a Unicast distinct from the sequence number space of Multicast Hellos, sending a Unicast
Hello to an implementation of RFC 6126 will confuse its link quality Hello to an implementation of RFC 6126 will confuse its link quality
estimator. Second, RFC 6126 did not define unscheduled Hellos, and an estimator. Second, RFC 6126 did not define unscheduled Hellos, and an
implementation of RFC 6126 will mis-parse Hellos with an interval equal to implementation of RFC 6126 will mis-parse Hellos with an interval equal to
0. Finally, RFC 7557 did not define mandatory sub-TLVs (<xref 0. Finally, RFC 7557 did not define mandatory sub-TLVs
target="sub-tlv-format"/>), and thus, an implementation of RFCs 6126 and (<xref target="sub-tlv-format" format="default"/>), and thus an implementation o
f RFCs 6126 and
7557 will not correctly ignore a TLV that carries an unknown mandatory 7557 will not correctly ignore a TLV that carries an unknown mandatory
sub-TLV; depending on the sub-TLV, this might cause routing pathologies.</t> sub-TLV; depending on the sub-TLV, this might cause routing pathologies.</t>
<t>An implementation of this specification that never sends Unicast or
<t>An implementation of this specification that never sends Unicast or
unscheduled Hellos and doesn't implement any extensions that use mandatory unscheduled Hellos and doesn't implement any extensions that use mandatory
sub-TLVs is safe to deploy in a network in which some nodes implement the sub-TLVs is safe to deploy in a network in which some nodes implement the
protocol described in RFCs 6126 and 7557.</t> protocol described in RFCs 6126 and 7557.</t>
<t>Two changes need to be made to an implementation of RFCs 6126 and 7557
<t>Two changes need to be made to an implementation of RFCs 6126 and 7557
so that it can safely interoperate in all cases with implementations of so that it can safely interoperate in all cases with implementations of
this protocol. First, it needs to be modified to either ignore or process this protocol. First, it needs to be modified either to ignore or to process
Unicast and unscheduled Hellos. Second, it needs to be modified to parse Unicast and unscheduled Hellos. Second, it needs to be modified to parse
sub-TLVs of all the TLVs that it understands and that allow sub-TLVs, and sub-TLVs of all the TLVs that it understands and that allow sub-TLVs, and
to ignore the TLV if an unknown mandatory sub-TLV is found. It is not to ignore the TLV if an unknown mandatory sub-TLV is found. It is not
necessary to parse unknown TLVs, as these are ignored in any case.</t> necessary to parse unknown TLVs, as these are ignored in any case.</t>
<t>There are other changes, but these are not of a nature to prevent
<t>There are other changes, but these are not of a nature to prevent
interoperability: interoperability:
<list style="symbols"> </t>
<t>the conditions on route acquisition (<xref target="route-acquisition"/>) <ul spacing="normal">
have been relaxed;</t> <li>the conditions on route acquisition (<xref target="route-acquisition
<t>route selection should no longer use the route's sequence number " format="default"/>)
(<xref target="route-selection"/>);</t> have been relaxed;</li>
<t>the format of the packet trailer has been defined <li>route selection should no longer use the route's sequence number
(<xref target="packet-format"/>);</t> (<xref target="route-selection" format="default"/>);</li>
<t>router-ids with a value of all-zeros or all-ones have been forbidden <li>the format of the packet trailer has been defined
(<xref target="router-id-def"/>);</t> (<xref target="packet-format" format="default"/>);</li>
<t>the compression state is now specific to an address family rather than <li>router-ids with a value of all-zeros or all-ones have been forbidden
an address encoding (<xref target="parser-state"/>);</t> (<xref target="router-id-def" format="default"/>);</li>
<t>packet pacing is now recommended <li>the compression state is now specific to an address family rather th
(<xref target="transmission-reception"/>).</t> an
</list></t> an address encoding (<xref target="parser-state" format="default"/>);</li>
<li>packet pacing is now recommended
</section> (<xref target="transmission-reception" format="default"/>).</li>
</ul>
<section title="Changes from previous versions"> </section>
<t>[RFC Editor: Please delete this section before publication.]</t>
<section title="Changes since RFC 6126">
<t><list style="symbols">
<t>Changed UDP port number to 6696.</t>
<t>Consistently use router-id rather than id.</t>
<t>Clarified that the source garbage collection timer is reset after
sending an update even if the entry was not modified.</t>
<t>In section "Seqno Requests", fixed an erroneous "route request".</t>
<t>In the description of the Seqno Request TLV, added the description of
the Router-Id field.</t>
<t>Made router-ids all-0 and all-1 forbidden.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-00">
<t><list style="symbols">
<t>Added security considerations.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-01">
<t><list style="symbols">
<t>Integrated the format of sub-TLVs.</t>
<t>Mentioned for each TLV whether it supports sub-TLVs.</t>
<t>Added <xref target="extensions"/>.</t>
<t>Added a mandatory bit in sub-TLVs.</t>
<t>Changed compression state to be per-AF rather than per-AE.</t>
<t>Added implementation hint for the routing table.</t>
<t>Clarified how router-ids are computed when bit 0x40 is set in Updates.</t>
<t>Relaxed the conditions for sending requests, and tightened the
conditions for forwarding requests.</t>
<t>Clarified that neighbours should be acquired at some point, but it
doesn't matter when.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-02">
<t><list style="symbols">
<t>Added Unicast Hellos.</t>
<t>Added unscheduled (interval-less) Hellos.</t>
<t>Changed Appendix A to consider Unicast and unscheduled Hellos.</t>
<t>Changed Appendix B to agree with the reference implementation.</t>
<t>Added optional algorithm to avoid the hold time.</t>
<t>Changed the table of pending seqno requests to be indexed by router-id
in addition to prefixes.</t>
<t>Relaxed the route acquisition algorithm.</t>
<t>Replaced minimal implementations by stub implementations.</t>
<t>Added acknowledgments section.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-03">
<t><list style="symbols">
<t>Clarified that all the data structures are conceptual.</t>
<t>Made sending and receiving Multicast Hellos a SHOULD, avoids expressing
any opinion about Unicast Hellos.</t>
<t>Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4).</t>
<t>Made hold-time into a SHOULD rather than MUST.</t>
<t>Clarified that Seqno Requests are for a finite-metric Update.</t>
<t>Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV that
allows sub-TLVs.</t>
<t>Updated IANA Considerations.</t>
<t>Updated Security Considerations.</t>
<t>Renamed routing table back to route table.</t>
<t>Made buffering outgoing updates a SHOULD.</t>
<t>Weakened advice to use modified EUI-64 in router-ids.</t>
<t>Added information about sending requests to Appendix B.</t>
<t>A number of minor wording changes and clarifications.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-03">
<t>Minor editorial changes.</t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-04">
<t><list style="symbols">
<t>Renamed isotonicity to left-distributivity.</t>
<t>Minor clarifications to unicast hellos.</t>
<t>Updated requirements boilerplate to RFC 8174.</t>
<t>Minor editorial changes.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-05">
<t><list style="symbols">
<t>Added information about the packet trailer, now that it is used by
draft-ietf-babel-hmac.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-06">
<t><list style="symbols">
<t>Added references to security documents.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-07">
<t><list style="symbols">
<t>Added list of obsoleted drafts to the abstract.</t>
<t>Updated references.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-08">
<t><list style="symbols">
<t>Added recommendation that route selection should not take seqnos into
account.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-09">
<t><list style="symbols">
<t>Editorial changes only.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-10">
<t><list style="symbols">
<t>Editorial changes only.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-11">
<t><list style="symbols">
<t>Added recommendation that control traffic should be carried over IPv6
only.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-12">
<t><list style="symbols">
<t>Removed appendix about software availability.</t>
<t>Expanded appendix about recommended values and added more references to
it in the body of the document.</t>
<t>Added appendix about route filtering.</t>
<t>Clarified definition of mandatory bit.</t>
<t>Added recommendations for packet pacing.</t>
<t>Made time limiting of full updates a SHOULD.</t>
<t>Normative language in a few more places.</t>
<t>Removed normative language from stub implementations.</t>
<t>Added requirement to clear the undefined bits in an Update.</t>
<t>Added error checking requirements.</t>
<t>Reworked security considerations.</t>
<t>Added "in octets" and "in bits" in random places.</t>
<t>Inserted full IANA registries.</t>
<t>Editorial changes.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-13">
<t><list style="symbols">
<t>Added a section about compatibility with 6126.</t>
<t>Added AE registry to IANA considerations.</t>
<t>Replaced Babel-HMAC with Babel-MAC, consistent with the change in
draft-ietf-babel-hmac.</t>
<t>Removed section about external sources of willingness; filtering is
a better approach.</t>
<t>Added recommendation to use a cost of 96 on wired links.</t>
<t>Editorial changes.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-14">
<t><list style="symbols">
<t>Added unscheduled Hellos to compatibility considerations.</t>
<t>Created new appendix about route selection.</t>
<t>Reworked security considerations.</t>
<t>Added some comments about packet pacing and low update intervals.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-15">
<t><list style="symbols">
<t>Implementing Babel-MAC is now recommended.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-16">
<t><list style="symbols">
<t>Make the values in Appendix B normatively recommended defaults.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-17">
<t><list style="symbols">
<t>Hysteresis in route selection is now RECOMMENDED.</t>
<t>Additive metric algebra is now RECOMMENDED default.</t>
<t>2-out-of-3 cost computation is now RECOMMENDED on LANs.</t>
<t>Reference to RFC 793 Section 3.7 added as exponential smoothing example.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-18">
<t><list style="symbols">
<t>Reserved Address Encodings 224-254 for Experimental Use, and 255 for
future expansion.</t>
</list></t>
</section>
<section title="Changes since draft-ietf-babel-rfc6126bis-19">
<t><list style="symbols">
<t>Mention that multi-octet fields are in big-endian.</t>
<t>Minor typos and clarifications.</t>
</list></t>
</section>
</section>
</back> <section numbered="false" toc="default">
<name>Acknowledgments</name>
<t>A number of people have contributed text and ideas to this
specification. The authors are particularly indebted to <contact fullname="Matt
hieu Boutier"/>,
<contact fullname="Gwendoline Chouasne"/>, <contact fullname="Margaret Cullen"/>
,
<contact fullname="Donald Eastlake"/>, <contact fullname="Toke Høiland-Jørgensen
"/>,
<contact fullname="Benjamin Kaduk"/>, <contact fullname="Joao Sobrinho"/>, and
<contact fullname="Martin Vigoureux"/>.
The previous version of this specification <xref target="RFC6126" format="defaul
t"/>
greatly benefited from the input of <contact fullname="Joel Halpern"/>. The add
ress compression
technique was inspired by <xref target="RFC5444" format="default"/>.</t>
</section>
</back>
</rfc> </rfc>
 End of changes. 426 change blocks. 
2266 lines changed or deleted 2285 lines changed or added

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