Network Working Group J. Chroboczek
Internet-Draft PPS, University of Paris 7
Intended status: Experimental April 30, 2009
Expires: November 1, 2009
The Babel Routing Protocol
draft-chroboczek-babel-routing-protocol-01
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on November 1, 2009.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Chroboczek Expires November 1, 2009 [Page 1]
Internet-Draft The Babel Routing Protocol April 2009
Abstract
Babel is a loop-free distance vector routing protocol that is robust
and efficient both in ordinary wired networks and in wireless mesh
networks.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Specification of Requirements . . . . . . . . . . . . . . 4
2. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Message Transmission and Reception . . . . . . . . . . . . 5
2.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 5
2.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . . 8
2.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 8
2.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 11
2.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 15
2.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 15
2.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 18
3. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 22
3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 23
3.3. Message Format . . . . . . . . . . . . . . . . . . . . . . 24
3.4. Details of Specific Messages . . . . . . . . . . . . . . . 24
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35
5. Security Considerations . . . . . . . . . . . . . . . . . . . 36
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.1. Normative References . . . . . . . . . . . . . . . . . . . 37
6.2. Informative References . . . . . . . . . . . . . . . . . . 37
Appendix A. Cost and Metric Computation . . . . . . . . . . . . . 38
A.1. Cost Computation . . . . . . . . . . . . . . . . . . . . . 38
A.2. Metric computation . . . . . . . . . . . . . . . . . . . . 39
Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . . 40
Appendix C. Simplified Implementations . . . . . . . . . . . . . 41
Appendix D. Software Availability . . . . . . . . . . . . . . . . 42
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 43
Chroboczek Expires November 1, 2009 [Page 2]
Internet-Draft The Babel Routing Protocol April 2009
1. Introduction
Babel is a sequenced distance vector routing protocol, inspired by
DSDV [DSDV], that is designed to be robust and efficient both in
networks using prefix-based routing and in networks using flat
routing (``mesh networks''), and both in relatively stable wired
networks and in highly dynamic wireless networks.
1.1. Features
The main property that makes Babel suitable for unstable networks is
that, unlike naive distance-vector routing protocols [RIP], it does
not cause routing pathologies such as routing loops and black-holes
during reconvergence. Even after a mobility event is detected, a
Babel network usually remains loop-free. Babel then quickly
reconverges to a configuration that preserves the loop-freedom and
connectedness of the network, but is not necessarily optimal; in most
cases, this operation requires no packet exchanges at all, and in the
worst case takes a number of packet exchanges that is proportional to
the diameter of the network. Babel then slowly converges, in a time
on the scale of minutes, to an optimal configuration.
More precisely, Babel has the following properties:
o when every prefix is originated by at most one router, Babel never
suffers from routing loops;
o when a prefix is originated by multiple routers, Babel may
occasionally create a transient routing loop for this particular
prefix; this loop disappears in a time proportional to its
diameter, and never again (up to an arbitrary garbage-collection
time) will the routers involved participate in a routing loop for
the same prefix;
o any routing black-holes that may appear after a mobility event are
corrected in a time at most proportional to the network's
diameter.
Babel has provisions for link quality estimation and for fairly
arbitrary metrics. When configured suitably, Babel can implement
shortest-path routing, or it may use a metric based e.g. on packet
loss statistics.
Babel nodes will successfully establish an association even when they
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 intervals, etc.) than a node that has access to wall
power. Conversely, a node that detects high levels of mobility may
Chroboczek Expires November 1, 2009 [Page 3]
Internet-Draft The Babel Routing Protocol April 2009
choose to use smaller time constants. The ability to build such
heterogeneous networks makes Babel particularly adapted to the
wireless environment.
Finally, Babel is a hybrid routing protocol, in the sense that it can
carry routes for multiple network-layer protocols (IPv4 and IPv6)
whichever protocol the Babel packets are themselves being carried
over.
1.2. Limitations
Babel has two limitations that make it unsuitable for use in some
environments. First, Babel relies on periodic routing table updates
rather than using a reliable transport; hence, in large, stable
networks it generates more traffic than protocols that only ever send
updates when the network topology changes. In such networks,
protocols such as OSPF [OSPF] or EIGRP [EIGRP] might be more
suitable.
Second, Babel does impose a hold time when a prefix is retracted
(Section 2.5.5). While this hold time does not apply to the exact
prefix being retracted, and hence does not prevent fast reconvergence
should it become available again, it does apply to any shorter prefix
that covers it; hence, if a previously deaggregated prefix becomes
aggregated, it will be unreachable for a few minutes. This makes
Babel unsuitable for use in mobile networks that implement automatic
prefix aggregation.
1.3. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
Chroboczek Expires November 1, 2009 [Page 4]
Internet-Draft The Babel Routing Protocol April 2009
2. Protocol Operation
Every Babel speaker is assigned a router-id, which is an arbitrary
string of 8 octets that is assumed unique across the routing domain.
We suggest that router-ids should be assigned in modified EUI-64
format [ADDRARCH]. (As a matter of fact, the protocol encoding is
slightly more compact when router-ids are assigned in the same manner
as the IPv6 layer assigns host ids.)
2.1. Message Transmission and Reception
Babel speakers exchange Babel protocol messages. One or more Babel
messages are appended to form a Babel packet, which is sent in a
single UDP datagram.
The source address of a Babel packet is always a link-local unicast
address. Babel packets may be sent to a well-known link-local
multicast address (this is the usual case) or to a (link-local)
unicast address. In normal operation, a Babel speaker sends both
multicast and unicast packets to its neighbours.
With the exception of Hello messages and acknowledgements, all Babel
messages can be sent to either unicast or multicast addresses, and
their semantics does not depend on whether the destination was a
unicast or multicast address. Hence, a Babel speaker does not need
to determine the destination address of a packet that it receives in
order to interpret it.
A moderate amount of jitter is applied to messages sent by a Babel
speaker: outgoing messages are buffered, and SHOULD be sent with a
small random delay. This is done for two purposes: it avoids
synchronisation of multiple Babel speakers across a network [JITTER],
and allows for the aggregation of multiple messages into a single
packet.
The exact delay and amount of jitter applied to a message depends on
whether a message is urgent or not. Acknowledgement messages MUST be
sent before the deadline specified in the corresponding request. The
particular class of update messages specified in Section 2.7.2 MUST
be sent in a timely manner. The particular class of request and
update messages specified in Section 2.8.2 SHOULD be sent in a timely
manner.
2.2. Data Structures
Every Babel speaker maintains a number of data structures.
Chroboczek Expires November 1, 2009 [Page 5]
Internet-Draft The Babel Routing Protocol April 2009
2.2.1. Sequence Number
A node's sequence number is a 16-bit integer that is included in
route updates sent for routes originated by this node. A node
increments its sequence number (modulo 2^16) whenever it receives a
request for a new sequence number (Section 2.8.1.2).
2.2.2. The Interface Table
The interface table contains the list of interfaces on which the node
speaks the Babel protocol. Every interface table entry contains the
interface's Hello seqno, a 16-bit integer that is sent with each
Hello message on this interface and is incremented (modulo 2^16)
whenever a Hello message is sent. (Note that an interface's Hello
seqno is unrelated to the node's seqno.)
There are two timers associated with each interface table entry, the
hello timer, which governs the sending of periodic Hello and IHU
packets, and the update timer, which governs the sending of periodic
route updates.
2.2.3. The Neighbour Table
The neighbour table contains the list of all neighbouring interfaces
over which a Babel packet has been recently received. The neighbour
table is indexed by pairs of the form (interface, address), and every
neighbour table entry contains the following data:
o the local node's interface over which this neighbour is reachable;
o the link-local address of the neighbouring interface;
o a history of recently received Hello packets from this neighbour;
this is a sequence of n bits, for some small value n, indicating
which of the n hellos most recently sent by this neighbour have
been received by the local node;
o the ``transmission cost'' value from the last IHU packet received
from this neighbour, or 0xFFFF (infinity) if the IHU hold timer
for this neighbour has expired;
o the neighbour's expected hello sequence number, an integer modulo
2^16.
There are two timers associated with each neighbour entry, the hello
timer, which is initialised from the interval value carried by Hello
messages, and the IHU timer, which is initialised to a small multiple
of the interval carried in IHU messages.
Chroboczek Expires November 1, 2009 [Page 6]
Internet-Draft The Babel Routing Protocol April 2009
Note that the neighbour table is indexed by IP addresses, not by
router-ids: neighbourship is a relationship between interfaces, not
between nodes. Therefore, two nodes with multiple interfaces can
participate in multiple neighbourship relationships, a common
situation for multi-radio wireless nodes.
2.2.4. The Source Table
The source table is indexed by triples of the form (prefix, plen,
router-id), and every source table entry contains the following data:
o the prefix (prefix, plen) that this entry applies to;
o the router-id of a router originating this prefix;
o a pair (seqno, metric), known as this source's reference distance.
There is one timer associated with each entry in the source table,
the source garbage collection timer. It is initialised to a time on
the order of minutes, and reset as specified in Section 2.7.3.
2.2.5. The Route Table
The route table is indexed by triples of the form (prefix, plen,
neighbour), and every route table entry contains the following data:
o the advertised prefix (prefix, plen);
o the neighbour that advertised this route;
o the metric with which this route was advertised by the neighbour,
known as the route's reference metric, or 0xFFFF (infinity) for a
recently retracted route;
o the sequence number with which this route was advertised;
o the next hop address of this route;
o a flag indicating whether this route is selected, i.e. whether it
is currently being used for forwarding and being advertised.
There is one timer associated with each route table entry, the route
expiry timer. It is initialised and reset as specified in
Section 2.5.4.
Chroboczek Expires November 1, 2009 [Page 7]
Internet-Draft The Babel Routing Protocol April 2009
2.2.6. The Table of Pending Requests
The table of pending requests contains a list of seqno requests 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 received yet. This table is indexed by triples of the form
(neigh, seqno, neighbour), and every pending request contains the
following data:
o the router-id and seqno being requested;
o the neighbour, if any, for which we are forwarding this request.
o a small integer indicating the number of times that this request
will be resent if it remains unsatisfied.
There is one timer associated with each pending request, which
governs both the resending of requests and their expiry.
2.3. Acknowledged Packets
A Babel speaker may request that any neighbour receiving a given
packet reply with an explicit acknowledgement within a given time.
While the use of acknowledgement requests is optional, every Babel
speaker MUST be able to reply to such a request.
An acknowledgement MUST be sent to a unicast destination. On the
other hand, acknowledgement requests may be sent to either unicast or
multicast destinations, in which case they request an acknowledgement
from all of the receiving nodes.
When to request acknowledgements is a matter of local policy; the
simplest strategy is to never request acknowledgements, and rely on
the periodic updates to ensure that any reachable routes are
eventually propagated throughout the routing domain. For increased
efficiency, we suggest that acknowledged packets should be used in
order to send urgent updates (Section 2.7.2) when the number of
neighbours on a given interface is small. Since Babel is designed to
deal gracefully with packet loss on unreliable media, sending all
packets with acknowledgement requests is not necessary, and not even
recommended, as the acknowledgements cause additional traffic and may
force additional ARP or Neighbour Discovery exchanges.
2.4. Neighbour Acquisition
Neighbour acquisition is the process by which a Babel node discovers
the set of neighbours heard over each of its interfaces and
ascertains bidirectional reachability. On unreliable media,
Chroboczek Expires November 1, 2009 [Page 8]
Internet-Draft The Babel Routing Protocol April 2009
neighbour acquisition additionally provides enough statistics to
perform link quality computation.
2.4.1. Reverse Reachability Detection
Every Babel node sends periodic Hello packets over each of its
interfaces. Each Hello packet carries an increasing (modulo 2^16)
sequence number, and the interval between successive periodic packets
sent on this particular interface.
In addition to the periodic Hello packets, a node MAY send
unscheduled Hello packets, e.g. to accelerate link cost estimation
when a new neighbour is discovered, or when link conditions have
suddenly changed.
A node MAY change its Hello interval. The Hello interval MAY be
decreased at any time; it SHOULD NOT be increased, except just before
sending a Hello packet. (Equivalently, a node SHOULD send an
unscheduled Hello packet just after increasing its Hello interval.)
For each neighbour, a Babel node maintains in its neighbour table an
expected Hello sequence number and a history of recently received
Hello packets. Whenever it receives a Hello packet from a neighbour,
a node compares the received sequence number nr with its expected
sequence number ne. Depending on the outcome of this comparison, one
of the following actions is taken:
o if the two differ by more than 16 (modulo 2^16), then the sending
node has probably rebooted and lost its sequence number; the
associated neighbour table entry is flushed;
o otherwise, if the received nr is smaller (modulo 2^16) than ne,
the sending node has increased its hello interval without our
noticing; the receiving node removes the last (ne - nr) entries
from this neighbour's hello history (we ``undo history'');
o otherwise, if nr is larger (modulo 2^16) than ne, then the sending
node has decreased its hello interval, and some hellos were lost;
the receiving node adds (nr - ne) 0 bits to the hello history (we
``fast-forward'').
The receiving node then appends a 1 bit to the neighbour's hello
history, resets the neighbour's hello timer, and sets ne to (nr + 1).
It then resets the neighbour's hello timer to 1.5 times the value
advertised in the Hello message (the extra margin allows for the
delay due to message jitter).
Whenever the Hello timer associated to a neighbour expires, the local
Chroboczek Expires November 1, 2009 [Page 9]
Internet-Draft The Babel Routing Protocol April 2009
node adds a 0 bit to this neighbour's hello history, and increments
the expected hello number. If the hello history is empty (it
contains 0 bits only), the neighbour entry is flushed; otherwise, it
resets the neighbour's hello timer to the value advertised in the
last Hello message received from this neighbour (no extra margin is
necessary in this case).
After updating the history table, the node recomputes the
association's cost (Section 2.4.3) and runs the route selection
procedure (Section 2.6).
2.4.2. Bidirectional Reachability Detection
In order to establish bidirectional reachability, every node sends
periodic IHU (``I Heard You'') messages to each of its neighbours.
Since IHU messages carry an explicit interval value, they MAY be sent
with each Hello message, but MAY also be sent less often. While IHU
packets are conceptually unicast, they SHOULD be sent to a multicast
address in order to avoid an ARP or Neighbour Discovery exchange, and
to aggregate multiple such messages in a single packet.
In addition to the periodic IHU messages, a node MAY, at any time,
send an unscheduled IHU packet. In addition, it MAY, at any time,
decrease its IHU interval, and MAY increase its IHU interval
immediately before sending an IHU.
Every IHU message contains two pieces of data: the sender's rxcost
(Section 2.4.3), and the interval between periodic IHU packets. A
node receiving an IHU message updates the sending neighbour's txcost
value to the value contained in the message, and resets this
neighbour's IHU timer to a small multiple of the value received in
the IHU message.
When a neighbour's IHU timer expires, its txcost is set to infinity.
After updating a neighbour's txcost, the receiving node recomputes
the neighour's cost (Section 2.4.3) and runs the route selection
procedure (Section 2.6).
2.4.3. Cost Computation
A neighbourship association's link cost is computed from the values
maintained in the neighbour table, namely the neighbour's hello
history and its txcost.
For every neighbour, a Babel node computes a value known as this
neighbour's reception cost, written rxcost. This value is usually
derived from the hello history, which may be combined with other
Chroboczek Expires November 1, 2009 [Page 10]
Internet-Draft The Babel Routing Protocol April 2009
data, such as statistics maintained by the link layer. The rxcost is
sent to a neighbour in each IHU message.
How a 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
concerned, only the following conditions MUST be satisfied:
o the cost is strictly positive;
o if the hello history is empty, then the cost is infinite;
o if the txcost is infinite, then the cost is infinite.
We give a few examples of reasonable strategies for computing a
link's cost in Appendix A.1.
2.5. Routing Table Maintenance
Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
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 update, seqno is this announcement's sequence
number, a non-decreasing (modulo 2^16) integer that is defined by the
originating router, and metric is the announced metric.
Before being accepted, an update is checked against the feasibility
condition (Section 2.5.1), a condition that ensures that the route
does not create a routing loop [DUAL]. If the feasibility condition
is not satisfied, the update is either ignored or treated as a
retraction, depending on some other conditions (Section 2.5.4). If
the feasibility condition is satisfied, then the update cannot
possibly cause a routing loop, and the update is accepted.
Before advertising a route, a Babel node updates its source table
with information that will be needed in order to evaluate its
feasibility condition (Section 2.7.3).
2.5.1. The Feasibility Condition
A feasibility distance, or distance for short, is a pair (seqno,
metric), where seqno is an integer modulo 2^16 and metric is a
positive integer. Feasibility distances are compared
lexicographically, with the first component inverted. In other
words, we say that a distance (seqno, metric) is strictly better than
a distance (seqno', metric'), written
(seqno, metric) < (seqno', metric')
Chroboczek Expires November 1, 2009 [Page 11]
Internet-Draft The Babel Routing Protocol April 2009
when
seqno > seqno' or (seqno = seqno' and metric < metric')
where sequence numbers are compared modulo 2^16.
A node's reference distance for a given source is the minimum,
according to the ordering defined above, of the distances of all the
updates ever sent for that source by this particular node. Reference
distances are maintained in the source table; the exact procedure is
given in Section 2.7.3.
An update is feasible when the advertised distance is strictly
better, in the sense defined above, than the reference distance for
the corresponding source; additionally, retractions are always
feasible. More precisely, a route advertisement carrying the
quintuple (prefix, plen, router-id, seqno, metric) is feasible if one
of the following conditions holds:
o metric is infinite; or
o no entry exists in the source table indexed by (id, prefix, plen);
or
o an entry (prefix, plen, router-id, seqno', metric') exists in the
source table, and either
* seqno' < seqno or
* seqno = seqno' and metric < metric'.
Note that the feasibility condition considers a route's reference
metric, not the route's metric; hence, a fluctuation in a neighbour's
cost cannot render a selected route unfeasible.
2.5.2. Metric Computation
A route's metric is computed from its reference metric -- the metric
that the neighbour advertised &mdash, and the advertising neighbour's
link cost. Just like link computation, metric computation is
considered a local policy matter; as far as Babel is concerned, the
function M(c, m) used for computing a metric from a neighour's cost
and a route's reference metric MUST only satisfy the following
conditions:
o if c is infinite, then M(c, m) is infinite;
Chroboczek Expires November 1, 2009 [Page 12]
Internet-Draft The Babel Routing Protocol April 2009
o M is strictly monotonic: M(c, m) > m.
Additonally, the metric SHOULD satisfy the following condition:
o M is isotonic: if m <= m' then M(c, m) <= M(c, m').
Note that while strict monotonicity is essential to the integrity of
the network (persistent routing loops may appear if it is not
satisfied), isotonicity is not: if it is not satisfied, Babel will
still converge to a locally optimal routing table, but migh not reach
a global optimum (in fact, such a global optimum may not even exist).
We give a number of examples of strictly monotonic, isotonic routing
metrics in Appendix A.2.
2.5.3. Encoding of Updates
In a large network, the bulk of Babel traffic consists of route
updates; hence, some care has been given to encoding them
efficiently. An update message itself only contains the prefix,
seqno and metric, while the next hop is derived either from the
network-layer source address of the packet, or from an explicit Next
Hop message in the same packet. The router-id is derived from a
separate Router-Id message in the same packet, which optimises the
case when multiple updates are sent with the same router-id.
Additionally, a prefix of the advertised prefix can be omitted in an
Update message, in which case it is copied from a previous Update
message in the same packet -- this is known as address compression
[PACKETBB].
Finally, as a special optimisation for the case when a router-id
coincides with the interface-id part of an IPv6 address, the
router-id can optionally be derived from the low-order bits of the
advertised prefix.
The encoding of updates is described in detail in Section 3.4.
2.5.4. Route Acquisition
When a Babel node receives an update (id, prefix, seqno, metric) from
a neighbour neigh with a link cost value equal to cost, it checks
whether it already has a routing table entry indexed by (neigh, id,
prefix).
If no such entry exists:
Chroboczek Expires November 1, 2009 [Page 13]
Internet-Draft The Babel Routing Protocol April 2009
o if the update is unfeasible, it is ignored;
o if the metric is infinite (the update is a retraction), the update
is ignored;
o otherwise, a new route table entry is created, indexed by (neigh,
id, prefix), with seqno seqno and a reference metric equal to the
metric carried by the update.
If such an entry exists:
o if the update is unfeasible, then the behaviour depends on whether
the router-ids of the two entries match. If the router-ids are
different, the update is treated as though it were a retraction
(i.e. as though the metric were 0xFFFF). If the router-ids are
equal, the update is ignored;
o if the update is feasible, then the entry's sequence number,
reference metric and metric are updated and, unless the advertised
metric is infinite, the route's expiry timer is reset to a small
multiple of the Interval value included in the update.
When a route's expiry timer triggers, the behaviour depends on
whether the route's metric is finite. If the metric is finite, it is
set to infinity and the expiry timer is reset. If the metric is
already infinite, the route is flushed from the route table.
After the routing table is updated, the route selection procedure
(Section 2.6) is run.
2.5.5. Hold Time
When a prefix p is retracted, because all routes are unfeasible, too
old, or have an infinite metric, 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 creating a routing loop.
To avoid this issue, whenever a prefix is retracted, a routing table
entry with infinite metric is maintained as described in
Section 2.5.4 above, and packets destined for that prefix MUST NOT be
forwarded by following a route for a shorter prefix. The infinite
metric entry is maintained until it is superseded by a feasible
update; if no such update arrives within the route hold time, the
entry is flushed.
Chroboczek Expires November 1, 2009 [Page 14]
Internet-Draft The Babel Routing Protocol April 2009
2.6. Route Selection
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
readvertised to a node's neighbours.
Babel is designed to allow flexible route selection policies. As far
as the protocol's correctness is concerned, the route selection
policy MUST only satisfy the following properties:
o a route with infinite metric is never selected;
o an unfeasible route is never selected.
Note, however, that Babel does not naturally guarantee the stability
of routing, and configuring conflicting route selection policies on
different routers may lead to persistent route oscillation.
Defining a good route selection policy for Babel is an open research
problem. Route selection can take into account multiple mutually
contradictory criteria; in roughly decreasing order of importance,
these are:
o routes with a small metric should be preferred over routes with a
large metric;
o switching router-ids should be avoided;
o routes through stable neighbours should be preferred over routes
through unstable ones;
o stable routes should be preferred over unstable ones;
o switching next hops should be avoided.
A simple strategy is to choose the feasible route with the smallest
metric, with a small amount of hysteresis applied to avoid switching
router-ids.
After the route selection procedure is run, triggered updates
(Section 2.7.2) and requests (Section 2.8.2) are sent.
2.7. Sending Updates
A Babel speaker advertises to its neighbours its set of selected
routes. Normally, this is done by sending one or more multicast
packets containing Update messages on all of its connected
interfaces; however, on link technologies where multicast is
Chroboczek Expires November 1, 2009 [Page 15]
Internet-Draft The Babel Routing Protocol April 2009
significantly more expensive than unicast, a node MAY choose to send
multiple copies of updates in unicast packets when the number of
neighbours is small.
Additionally, in order to ensure that any black-holes are reliably
cleared in a timely manner, a Babel node sends retractions (updates
with an infinite metric) for any recently retracted prefixes.
If an update is for a route injected into the Babel domain by the
local node (e.g. the address of a local interface, the prefix of a
directly attached network, or redistributed from a different routing
protocol), the router-id is set to the local id, the metric is set to
some arbitrary finite value (typically 0), and the seqno is set to
the local router's sequence number.
If an update is for a route learned from another Babel speaker, the
router-id and sequence number are copied from the routing table
entry, and the metric is computed as specified in Section 2.5.2.
2.7.1. Periodic Updates
Every Babel speaker periodically advertises all of its selected
routes on all of its interfaces, including any recently retracted
routes. Since Babel doesn't suffer from routing loops (there is no
``counting to infinity'') and relies heavily on triggered updates
(Section 2.7.2), this full dump only needs to happen infrequently.
2.7.2. Triggered Updates
In addition to the periodic routing updates, a Babel speaker sends
unscheduled, or triggered updates in order to inform its neighbours
of a significant change in the network topology.
A change of router-id for the selected route to a given prefix may be
indicative of a routing loop in formation; hence, a node MUST send a
triggered update in a timely manner whenever it changes the selected
router-id for a given destination. Additionally, it SHOULD make a
reasonable attempt at ensuring that all neighbours receive this
update.
There are two strategies for ensuring that. If the number of
neighbours is small, then it is reasonable to send the update
together with an acknowledgement request; the update is resent until
all neighbours have acknowledged the packet, up to some number of
times. If the number of neighbours is large, however, requesting
acknowledgements from all of them 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 times (say, 5 for
Chroboczek Expires November 1, 2009 [Page 16]
Internet-Draft The Babel Routing Protocol April 2009
wireless and 2 for wired links).
A route retraction is somewhat less worrying: if the route retraction
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 route is retracted, a node SHOULD send a triggered
update, and SHOULD make a reasonable attempt at ensuring that all
neighbours receive this retraction.
Finally, a node MAY send a triggered update when the metric for a
given prefix changes in a significant manner, either due to a
received update or because a link cost has changed. A node SHOULD
NOT send triggered updates for other reasons, such as when there is a
minor fluctuation in a route's metric, when the selected next hop
changes, or to propagate a new sequence number (except to satisfy a
request, as specified in Section 2.8).
2.7.3. Maintaining Reference Distances
Before sending an update (prefix, plen, router-id, seqno, metric)
with finite metric (i.e. not a route retraction), a Babel node
updates the reference distance maintained in the source table. This
is done as follows.
If no entry indexed by (prefix, plen, router-id) exists in the source
table, then one is created with value (prefix, plen, router-id,
seqno, metric).
If an entry (prefix, plen, router-id, seqno', metric') exists, then
it is updated as follows:
o if seqno > seqno', then seqno' := seqno, metric' := metric;
o if seqno = seqno' and metric' > metric, then metric' := metric;
o otherwise, nothing needs to be done.
The garbage collection timer for the modified entry is then reset.
Note that the garbage collection timer is not reset when a retraction
is sent.
2.7.4. Split Horizon
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 node SHOULD use an optimisation known as split horizon. When
split horizon is used on a given interface, a routing update is not
sent on this particular interface when the advertised route was
Chroboczek Expires November 1, 2009 [Page 17]
Internet-Draft The Babel Routing Protocol April 2009
learnt from a neighbour over the same interface.
Since Babel does not suffer from routing loops, split horizon with
poison reverse SHOULD NOT be used.
Split horizon SHOULD NOT be applied to an interface unless the
interface is known to be symmetric and transitive; in particular,
split horizon is not applicable to decentralised wireless link
technologies (e.g. IEEE 802.11 in ad-hoc mode).
2.8. Explicit Route Requests
In normal operation, a node's routing table is populated by the
regular and triggered updates sent by its neighbours. Under some
circumstances, however, a node sends explicit requests to cause a
resynchronisation with the source after a mobility event, and to
prevent a route from spuriously expiring.
The Babel protocol provides two kinds of explicit requests: route
requests, which simply request an update for a given prefix, and
seqno requests, which request an update for a given prefix with a
specific sequence number. The former are never forwarded; the latter
are forwarded if they cannot be satisfied by a neighbour.
2.8.1. Handling Requests
Upon receiving a request, a node either forwards the request or sends
an update in reply to the request, as described in the following
sections. If this causes an update to be sent, the update is either
sent to a multicast address on the interface on which the request was
received, or to the unicast address of the neighbour that sent the
update.
The exact behaviour is different for route requests and seqno
requests.
2.8.1.1. Route Requests
When a node receives a route request for a prefix (prefix, plen), it
checks its route table for a selected route to this exact prefix. If
such a route exists, it MUST send an update; if it is not, it MUST
send a retraction for that prefix.
When a node receives a wildcard route request, it SHOULD send a full
routing table dump.
Chroboczek Expires November 1, 2009 [Page 18]
Internet-Draft The Babel Routing Protocol April 2009
2.8.1.2. Seqno Requests
When a node receives a seqno request for a given router-id and
sequence number, it checks whether its routing table contains a
selected entry for that prefix; if no such entry exists, or the entry
has infinite metric, it ignores the request.
If a selected route for the given prefix exists, and either the
router-ids are different or the router-ids are equal and the entry's
sequence number is no smaller than the requested sequence number, it
MUST send an update for the given prefix.
If the router-ids match but the requested seqno is larger than the
route entry's, the node compares the router-id against its own
router-id. If the router-id is its own, then it increases its
sequence number by 1 and sends an update. A node MUST NOT increase
its sequence number by more than 1 in response to a route request.
If the requested router-id is not its own, the received requests's
hop count is 2 or more, and the node has a route (not necessarily a
feasible one) for the requested prefix that does not use the
requestor as a next-hop, the node SHOULD forward the request. It
does so by decreasing the hop count and sending the request in a
unicast packet destined to a neighbour that advertises the given
prefix (not necessarily the selected neighbour) and that is distinct
from the neighbour from which the request was received.
A node SHOULD maintain a list of recently forwarded requests, and
forward the reply in a timely manner. A node SHOULD compare every
incoming request against its list of recently forwarded requests and
avoid forwarding it if it is redundant.
Since the request forwarding mechanism does not necessarily obey the
feasibility condition, it may get caught into routing loops; hence,
requests carry a hop count to limit the time for which they remain in
the network. However, since requests are only ever forwarded as
unicast packets, the initial hop count need not be kept particularly
low, and performing an expanding horizon search is not necessary. A
request MUST NOT be forwarded to a multicast address, and it MUST NOT
be forwarded more than once.
2.8.2. Sending Requests
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 requests is required (Section 2.8.2.1).
Chroboczek Expires November 1, 2009 [Page 19]
Internet-Draft The Babel Routing Protocol April 2009
2.8.2.1. Avoiding Starvation
When a route is retracted or expires, a Babel node usually switches
to another feasible route for the same prefix. It may be the case,
however, that no such routes are available.
A node that has lost all feasible routes to a given destination MUST
send a seqno request. The router-id of the request is set to the
router-id of the route it has just lost, and the requested seqno is
the value contained in the source table, plus 1.
Such a request SHOULD be multicast over all of the node's attached
interfaces. The request will be forwarded by neighbouring nodes up
to the source; if the network is connected, and there is no packet
loss, this will result in a route being advertised with a new
sequence number.
In order to compensate for packet loss, a node SHOULD repeat such a
request a small number of times if no route becomes feasible within a
short time.
2.8.2.2. Dealing with Unfeasible Updates
When a route's metric increases, a node might receive an unfeasible
update for a route that it has currently selected. As specified in
Section 2.5.1, the receiving node will either ignore the update or
retract the route.
In order to keep routes from spuriously expiring because they have
become unfeasible, a node SHOULD send a unicast seqno request
whenever it receives an unfeasible update for a route that is
currently selected. The requested sequence number is computed from
the source table as above.
Additionally, a node SHOULD send a unicast seqno request whenever it
receives an unfeasible update from a currently unselected neighbour
that would lead to the advertised route becoming selected if it were
feasible.
2.8.2.3. Preventing Routes From Expiring
In normal operation, a route's expiry timer should never trigger:
since a route's hold time is computed from an explicit interval
included in Update messages, a new update should arrive in time to
prevent a route from expiring.
In the presence of packet loss, however, it may be the case that no
update is successfully received for an extended period of time,
Chroboczek Expires November 1, 2009 [Page 20]
Internet-Draft The Babel Routing Protocol April 2009
causing 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 to the neighbour that advertised this route;
since nodes always send retractions in response to non-wildcard route
requests (Section 2.8.1.1), this will usually result in either the
route being refreshed, or a retraction being received.
Chroboczek Expires November 1, 2009 [Page 21]
Internet-Draft The Babel Routing Protocol April 2009
3. Protocol Encoding
A Babel packet is sent as the body of a UDP datagram, with network-
layer hop count set to 1, destined to a well-known link-local
multicast address or to a link-local unicast address, over IPv4 or
IPv6. Both the source and destination UDP port are set to a well-
known port number. A Babel packet MUST be silently ignored unless
its source address is either a link-local IPv6 address, or an IPv4
address belonging to the local network, and its source port is the
well-known Babel port. Babel packets MUST NOT be sent as IPv6
Jumbograms.
In order to minimise the number of packets being sent while avoiding
lower-layer fragmentation, a Babel node SHOULD attempt to maximise
the size of the packets it sends, up to the outgoing interface's MTU
adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets
for UDP/IPv6). It MUST NOT send packets larger than the attached
interface's MTU (adjusted for lower-layer headers) or 512 octets,
whichever is larger, but not exceeding 2^16 - 1 adjusted for lower-
layer headers. Every Babel speaker MUST be able to receive packets
that are as large as any attached interface's MTU (adjusted for
lower-layer headers) or 512 octets, whichever is larger.
In order to avoid global synchronisation of a Babel network and to
aggregate multiple messages into large packets, a Babel node MUST
buffer every message and delay sending it by a small, randomly chosen
delay [JITTER]. In order to allow accurate computation of packet
loss rates, this delay MUST NOT be larger than half the advertised
Hello interval.
3.1. Data Types
3.1.1. Interval
Relative times are carried as 16-bit values specifying a number of
centiseconds (hundredths of a second). This allows times up to
roughly 11 minutes with a granularity of 10ms, which should cover all
reasonable applications of Babel.
3.1.2. Router-Id
A router-id is an arbitrary 8-octet value. Router-ids SHOULD be
assigned in modified EUI-64 format [ADDRARCH].
3.1.3. Address
Since the bulk of the protocol is taken by addresses, multiple ways
of encoding addresses are defined. Additionally, a common subnet
Chroboczek Expires November 1, 2009 [Page 22]
Internet-Draft The Babel Routing Protocol April 2009
prefix may be omitted when multiple addresses are sent in a single
packet -- this is known as address compression [PACKETBB].
Address encodings:
o AE 0: wildcard address. The value is 0 octets long.
o AE 1: IPv4 address. Compression is allowed. 4 octets or less.
o AE 2: IPv6 address. Compression is allowed. 16 octets or less.
o AE 3: link-local IPv6 address. The value is 8 octets long, a
prefix of fe80::/64 is implied.
The address family of an address is either IPv4 or IPv6; it is
undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3.
3.1.4. Prefixes
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
significant bits (up to the prefix length).
3.2. Packet Format
A Babel packet consists of a four-octet header, followed by a
sequence of Babel messages.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Magic | Version | Body length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Body ...
+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields :
Magic The arbitrary but carefully chosen value 42; packets with a
first octet different from 42 MUST be silently ignored.
Version This document specifies version 2 of the Babel protocol.
Packets with a second octet different from 2 MUST be
silently ignored.
Chroboczek Expires November 1, 2009 [Page 23]
Internet-Draft The Babel Routing Protocol April 2009
Body length The length in octets of the body following the packet
header.
Body The packet body, a sequence of messages.
Any data following the body MUST be silently ignored.
3.3. Message Format
With the exception of Pad1, all messages have the following
structure:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields :
Type This field specifies the kind of message.
Length The length of the body, exclusive of the Type and Length
fields. If the body is longer than the expected length of
a given type of message, any extra data MUST be silently
ignored.
Body This is the message body, the interpretation of which
depends on the message type.
Unknown message types MUST be silently ignored.
3.4. Details of Specific Messages
3.4.1. Pad1
0
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
| Type = 0 |
+-+-+-+-+-+-+-+-+
Fields :
Type Set to 0 to indicate a Pad1 message.
This message is silently ignored on reception.
Chroboczek Expires November 1, 2009 [Page 24]
Internet-Draft The Babel Routing Protocol April 2009
3.4.2. PadN
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 1 | Length | MBZ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Fields :
Type Set to 1 to indicate a PadN message.
Length The length of the body, exclusive of the Type and Length
fields.
MBZ This field is set to 0 on transmission.
This message is silently ignored on reception.
3.4.3. Acknowledgment Request
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 2 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nonce | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This message requests that the receiver send an Acknowledgement
message within the number of centiseconds specified by the Interval
field.
Fields :
Type Set to 2 to indicate an Acknowledgment Request message.
Length The length of the body, exclusive of the Type and Length
fields.
Reserved This field is sent as 0, and MUST be ignored on reception.
Nonce This is an arbitrary value which will be echoed in the
receiver's Acknowledgment message
Chroboczek Expires November 1, 2009 [Page 25]
Internet-Draft The Babel Routing Protocol April 2009
Interval This field expresses a time interval in centiseconds after
which the sender will assume that this packet has been
lost. This MUST NOT be 0. The receiver MUST send an
acknowledgement before this time has elapsed (with a margin
allowing for propagation time).
3.4.4. Acknowledgment
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 3 | Length | Nonce |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This message is sent by a node upon receiving an Acknowledgment
Request.
Fields :
Type Set to 3 to indicate an Acknowledgment message.
Length The length of the body, exclusive of the Type and Length
fields.
Nonce This is set to the Nonce value of the Acknowledgement
Request that prompted this message.
Since nonce values are not globally unique, this message MUST be sent
to a unicast address.
3.4.5. Hello
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 4 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This message is used for neighbour discovery and determining a link's
reception cost.
Fields :
Chroboczek Expires November 1, 2009 [Page 26]
Internet-Draft The Babel Routing Protocol April 2009
Type Set to 4 to indicate a Hello message.
Length The length of the body, exclusive of the Type and Length
fields.
Reserved This field is sent as 0, and MUST be ignored on reception.
Seqno The value of the sending node's hello seqno for this
interface.
Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new Hello message.
This MUST NOT be 0.
Since there is a single seqno counter for all the hellos sent by a
given node over a given interface, this message MUST be sent to a
multicast destination. In order to avoid large discontinuities in
link quality, multiple Hello messages SHOULD NOT be sent in the same
packet.
3.4.6. IHU
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 5 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Txcost | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address...
+-+-+-+-+-+-+-+-+-+-+-+-
An IHU (``I Heard You'') message is used for confirming bidirectional
reachability and carrying a link's transmission cost.
Fields :
Type Set to 5 to indicate an IHU message.
Length The length of the body, exclusive of the Type and Length
fields.
AE The encoding of the Address field. This should be 1 or 3
in most cases. As an optimisation, it MAY be 0 if the
message is 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 the Babel
protocol.
Chroboczek Expires November 1, 2009 [Page 27]
Internet-Draft The Babel Routing Protocol April 2009
Reserved This field is sent as 0, and MUST be ignored on reception.
Txcost The txcost according to the sending node of the interface
whose address is specified in the Address field. The value
0xFFFF indicates that this interface is unreachable.
Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new IHU message;
this MUST NOT be 0. The receiving node will use this value
in order to compute a hold time for this symmetric
association.
Address The address of the destination node, in the format
specified by the AE field. Address compression is not
allowed.
Conceptually, an IHU message is destined to a single neighbour.
However, IHU messages contain a destination address, and SHOULD be
sent to a multicast address; this allows aggregation of IHU messages
destined to 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 traffic.
IHU messages with an unknown value for the AE field MUST be silently
ignored.
3.4.7. Router-Id
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 6 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Router-Id +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A Router-Id message establishes a router-id that is implied by
subsequent Update messages.
Fields :
Type Set to 6 to indicate a Router-Id message.
Chroboczek Expires November 1, 2009 [Page 28]
Internet-Draft The Babel Routing Protocol April 2009
Length The length of the body, exclusive of the Type and Length
fields.
Reserved This field is sent as 0, and MUST be ignored on reception.
Router-Id This field contains the router-id for routes advertised in
subsequent Update messages
3.4.8. Next Hop
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 7 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next hop...
+-+-+-+-+-+-+-+-+-+-+-+-
A Next Hop message establishes a next hop address for a given address
family (IPv4 or IPv6) that is implied by subsequent Update messages.
Fields :
Type Set to 7 to indicate a Next Hop message.
Length The length of the body, exclusive of the Type and Length
fields.
AE The encoding of the Address field. This SHOULD be 1 or 3,
and MUST NOT be 0.
Reserved This field is sent as 0, and MUST be ignored on reception.
Next hop The next hop address advertised by subsequent Update
messages, for this address family.
When the address family matches the network-layer protocol that this
packet is transported over, a Next Hop message is not needed: in that
case, the next hop is taken to be the source address of the packet.
When a next hop message with an unknown value for the AE field is
encountered, all subsequent Update messages in the same packet MUST
be silently ignored.
Chroboczek Expires November 1, 2009 [Page 29]
Internet-Draft The Babel Routing Protocol April 2009
3.4.9. Update
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 8 | Length | AE | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Plen | Omitted | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix...
+-+-+-+-+-+-+-+-+-+-+-+-
An Update message advertises or retracts a route. As an
optimisation, it can also have the side effect of establishing a new
implied router-id, and a new default prefix.
Fields :
Type Set to 8 to indicate an Update message.
Length The length of the body, exclusive of the Type and Length
fields.
AE The encoding of the Prefix field. If this is 0, then
Metric MUST be 0xFFFF, in which case this message retracts
all the routes previously advertised by the sender on this
interface.
Flags The individual bits of this field specify special handling
of this message (see below). Every node MUST be able to
interpret flags 0x80 and 0x40; unknown flags MUST be
silently ignored.
Plen This is the length of the advertised prefix.
Omitted The number of octets that have been omitted at the
beginning of the advertised prefix, and that should be
taken from a preceding Update message with flag 0x80 set.
Interval An upper bound, expressed in centiseconds, on the time
after which the sending node will send a new update for
this prefix. This MUST NOT be 0, and SHOULD NOT be less
than 10. The receiving node will use this value to compute
a hold time for this routing table entry. The value 0xFFFF
(infinity) expresses that this announcement will not be
repeated unless a request is received (Section 2.8.2.3).
Chroboczek Expires November 1, 2009 [Page 30]
Internet-Draft The Babel Routing Protocol April 2009
Seqno The originator's sequence number for this update.
Metric The sender's metric for this route. The value 0xFFFF
(infinity) means that this is a route retraction.
Prefix This field, of size (Plen/8 - Omitted) rounded upwards,
specifies the prefix being advertised.
The Flags field is interpreted as follows:
o if bit 0x80 is set, then this Update message establishes a new
default prefix for subsequent Update messages with a matching
address family within the same packet;
o if bit 0x40 is set, then the low-order 8 octets of the advertised
prefix establish a new default router-id for this message and
subsequent Update messages in the same packet.
The router-id of the originating node for this announcement is taken
from the low-order 8 octets of the prefix advertised by this message
if bit 0x40 is set in the Flags field. Otherwise, it is taken either
from the preceding Router-Id packet, or the preceding Update packet
with flag 0x40 set, whichever comes last.
The next hop address for this update is taken from the last preceding
Next Hop message with a matching address family in the same packet;
if no such message exists, it is taken from the network-layer source
address of this packet.
The prefix being advertised by an Update message is computed as
follows:
o the first Omitted octets of the prefix are taken from the previous
Update message with flag 0x80 set and the same address family;
o the next (Plen/8 - Omitted) (rounded upwards) octets are taken
from the Prefix field;
o the remaining octets are set to 0.
Update messages with an unknown value for the AE field MUST be
silently ignored.
Chroboczek Expires November 1, 2009 [Page 31]
Internet-Draft The Babel Routing Protocol April 2009
3.4.10. Route Request
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 9 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix...
+-+-+-+-+-+-+-+-+-+-+-+-
A Route Request message prompts the receiver to send an update for a
given prefix, or a full routing table dump.
Fields :
Type Set to 9 to indicate a Route Request message.
Length The length of the body, exclusive of the Type and Length
fields.
AE The encoding of the Prefix field. The value 0 specifies
that this is a request for a full routing table dump (a
wildcard request).
Plen This is the length of the requested prefix.
Prefix This field, of size Plen/8 rounded upwards, specifies the
prefix being requested.
This message prompts the receiving node to send an update message for
the prefix specified by the AE, Plen and Prefix fields, or a full
dump of its routing table if AE is 0 (in which case Plen MUST be 0
and Prefix is of length 0). This message may be sent using unicast
if it is destined to a single node, or multicast if the request is
destined to all of the neighbours of the sending interface.
Chroboczek Expires November 1, 2009 [Page 32]
Internet-Draft The Babel Routing Protocol April 2009
3.4.11. Seqno Request
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 10 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Hop Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Router-Id +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix...
+-+-+-+-+-+-+-+-+-+-+
A Seqno Request message prompts the receiver to send an update for a
given prefix with a given sequence number, or to forward the request
further if it cannot be satisfied locally.
Fields :
Type Set to 10 to indicate a Seqno Request message.
Length The length of the body, exclusive of the Type and Length
fields.
AE The encoding of the Prefix field. This MUST NOT be 0.
Plen This is the length of the requested prefix.
Seqno The sequence number that is being requested.
Hop Count The maximum number of times that this message may be
forwarded, plus 1. This MUST NOT be 0.
Prefix This field, of size Plen/8 rounded upwards, specifies the
prefix being requested.
This message prompts the receiving node to send an update message 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 field, or
a sequence number equal or larger to what is specified by the Seqno
field. If this request cannot be satisfied locally, then it is
forwarded according to the rules set out in Section 2.8.1.2.
While a Seqno Request MAY be sent to a multicast address, it MUST NOT
be forwarded to a multicast address, and MUST NOT be forwarded more
Chroboczek Expires November 1, 2009 [Page 33]
Internet-Draft The Babel Routing Protocol April 2009
than once. A request MUST NOT be forwarded if its Hop Count field is
1.
Chroboczek Expires November 1, 2009 [Page 34]
Internet-Draft The Babel Routing Protocol April 2009
4. IANA Considerations
IANA has registered the UDP port number TBD, called "babel", for use
by the Babel protocol.
IANA has registered the IPv6 multicast group TBD and the IPv4
multicast group TBD for use by the Babel protocol.
Chroboczek Expires November 1, 2009 [Page 35]
Internet-Draft The Babel Routing Protocol April 2009
5. Security Considerations
As defined in this document, Babel is a completely insecure protocol.
Any attacker can attract data traffic by advertising routes with a
low metric. This particular issue can be solved either by lower-
layer security mechanisms (e.g. IPSec or link-layer security), or by
appending a cryptographic key to Babel packets; the provision of
ignoring any data contained within a Babel packet beyond the body
length declared by the header is designed for just such a purpose.
The information that a Babel node announces to the whole routing
domain is often sufficient to determine a mobile node's physical
location with reasonable precision. The privacy issues that this
causes can be mitigated somewhat by using randomly chosen router-ids,
randomly chosen IP addresses, and changing them periodically.
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 IPv6 packets, this provides protection against spoofed
Babel packets being sent from the global Internet. No such natural
protection exists when Babel packets are carried over IPv4.
Chroboczek Expires November 1, 2009 [Page 36]
Internet-Draft The Babel Routing Protocol April 2009
6. References
6.1. Normative References
[ADDRARCH]
Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 4291, February 2006.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997.
6.2. Informative References
[DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-
Sequenced Distance-Vector Routing (DSDV) for Mobile
Computers", ACM SIGCOMM'94 Conference on Communications
Architectures, Protocols and Applications 234-244, 1994.
[DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing
Computations", IEEE/ACM Transactions on Networking 1:1,
February 1993.
[EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle,
"EIGRP -- a Fast Routing Protocol Based on Distance
Vectors", Proc. Interop 94, 1994.
[ETX] Defcouto, D., Aguayo, D., Bicket, J., and R. Morris, "A
high-throughput path metric for multi-hop wireless
networks", Proc. MobiCom 2003, 2003.
[JITTER] Floyd, S. and V. Jacobson, "The synchronization of
periodic routing messages", IEEE/ACM Trans. Netw. 2, 2,
122-136, April 1994.
[OSPF] Moy, J., "OSPF Version 2", RFC 2328, STD 0054, April 1998.
[PACKETBB]
Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, 2009.
[RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998.
Chroboczek Expires November 1, 2009 [Page 37]
Internet-Draft The Babel Routing Protocol April 2009
Appendix A. Cost and Metric Computation
The strategy for computing link costs and route metrics is a local
matter; Babel itself only requires that it comply with the conditions
given in Section 2.4.3 and Section 2.5.2. Different nodes MAY use
different strategies in a single network, and MAY use different
strategies on different interface types. This section gives a few
examples of such strategies.
The sample implementation of Babel computes costs by using the 2-out-
of-3 strategy (Appendix A.1.1) on wired links, and ETX
(Appendix A.1.2) on wireless links. It uses an additive algebra for
metric computation (Appendix A.2.1).
A.1. Cost Computation
A.1.1. k-out-of-j
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 they drop all packets.
The k-out-of-j strategy is parameterised by two small integers k and
j, such that 0 < k <= j, and the nominal link cost, a constant K >=
1. A node keeps a history of the last j hellos; if k or more of
those have been correctly received, the link is assumed to be up, and
the rxcost is set to K; otherwise, the link is assumed to be down,
and the rxcost is set to infinity.
The cost of such a link is defined as
o cost = 0xFFFF if rxcost = 0xFFFF;
o cost = txcost otherwise.
A.1.2. ETX
The Estimated Transmission Cost metric [ETX] estimates the number of
times that a unicast frame will be retransmitted by the IEEE 802.11
MAC, assuming infinite persistence.
A node uses a neighbour's hello history to compute an estimate beta
of the probability that a Hello message is successfully received.
The rxcost is defined as 256/beta.
Let alpha be MIN(1, 256/txcost), an estimate of the probability of
successfully sending a Hello message. The cost is then computed by
Chroboczek Expires November 1, 2009 [Page 38]
Internet-Draft The Babel Routing Protocol April 2009
cost = 256/(alpha * beta)
or, equivalently,
cost = (MAX(txcost, 256) * rxcost) / 256.
A.2. Metric computation
A.2.1. Additive Metrics
The simplest approach for obtaining a monotonic, isotonic metric is
to define the metric of a route as the sum of the costs of the
component links. More formally, if a neighbour advertises a route
with metric m over a link with cost c, then the resulting route has
metric M(c, m) = c + m.
A multiplicative metric can be converted to an additive one by taking
the logarithm (in some suitable base) of the link costs.
A.2.2. External Sources of Willingness
A node may want to vary its willingness to forward packets by taking
into account information that is external to the Babel protocol, such
as the monetary cost of a link, the node's battery status, CPU load,
etc. This can be done by adding a value k that depends on the
external data to every route's metric. For example, battery-powered
node receives an update with metric m over a link with cost c, it
might compute a metric M(c, m) = k + c + m, where k depends on the
battery status.
In order to preserve strict monotonicity (Section 2.5.2), the value k
must be greater than -c.
Chroboczek Expires November 1, 2009 [Page 39]
Internet-Draft The Babel Routing Protocol April 2009
Appendix B. Constants
The choice of time constants is a trade-off between fast detection of
mobility events and protocol overhead. Two implementations of Babel
with different time constants will interoperate, although the
resulting convergence time will most likely be dictated by the
slowest of the two implementations.
Experience with the sample implementation of Babel indicates that the
Hello interval is the most important time constant: a mobility event
is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance
on triggered updates and explicit requests, the Update interval only
has an effect on the time it takes for accurate metrics to be
propagated after variations in link costs too small to trigger an
unscheduled update.
At the time of writing, the sample implementation of Babel uses the
following default values:
Hello Interval: 4 seconds on wireless links, 20 seconds on wired
links.
IHU Interval: the advertised IHU interval is always 3 times the
Hello interval. IHUs are actually sent with each Hello on lossy
links (as determined from the Hello history), but only with every
third Hello on lossless links.
Update Interval: 4 times the Hello interval.
IHU Hold Time: 3.5 times the advertised IHU interval.
Route Expiry Time: 3.5 times the advertised update interval.
Source GC time: 3 minutes.
The amount of jitter applied to messages depends on whether they are
urgent or not. Urgent triggered updates and urgent requests are
delayed by no more than 200ms; other messages are delayed by no more
than one-half the Hello interval.
Chroboczek Expires November 1, 2009 [Page 40]
Internet-Draft The Babel Routing Protocol April 2009
Appendix C. Simplified Implementations
Babel is a very economic protocol. Route updates take between 12 and
40 octets per destination, depending on how successful compression
is; in a double-stack mesh network, an average of less than 24 octets
is typical. The route table occupies about 35 octets 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 can
contain a 20000-entry routing table and the associated source table.
Babel is also a reasonably simple protocol. The sample
implementation consists of less than 7000 lines of C code, and
compiles to less than 60 kB of text on a 32-bit CISC architecture.
Nonetheless, in some very constrained environments, such as PDAs,
microwave ovens or abacuses, it may be desirable to have subset
implementations of the protocol.
A parasitic implementation is one that uses a Babel network for
routing its packets but does not announce any of the routes that it
has learnt from its neighbours. (This is slightly more than a
passive implementation, which doesn't even announce routes to
itself.) It may either maintain a full routing table, or simply
select a gateway amongst any one of its neighbours that announces a
default route. Since a parasitic implementation never forwards
packets, it cannot possibly participate in a routing loop; hence, it
need not evaluate the feasibility condition, and need not maintain a
source table.
A parasitic implementation MUST answer acknowledgement requests, and
MUST participate in the Hello/IHU protocol. Finally, it MUST be able
to reply to seqno requests for routes that it announces, and SHOULD
be able to reply to route requests.
Chroboczek Expires November 1, 2009 [Page 41]
Internet-Draft The Babel Routing Protocol April 2009
Appendix D. Software Availability
The sample implementation of Babel is available from
<http://www.pps.jussieu.fr/~jch/software/babel/>.
Chroboczek Expires November 1, 2009 [Page 42]
Internet-Draft The Babel Routing Protocol April 2009
Author's Address
Juliusz Chroboczek
PPS, University of Paris 7
Case 7014
75205 Paris Cedex 13,
France
Email: jch@pps.jussieu.fr
Chroboczek Expires November 1, 2009 [Page 43]