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 example, router-ids could be assigned randomly, or they could be derived 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 assigns host IDs; see the definition of the "R" flag in Section 4.6.9
Babel protocol packets are sent in the body of a UDP datagram (as described in Section 4
). Each Babel packet consists of zero or more TLVs. Most TLVs may contain sub-TLVs.
Babel's control traffic can be carried indifferently over IPv6 or over IPv4, and prefixes of either address family can be announced over either protocol. Thus, there are at least two natural deployment models: using IPv6 exclusively for all control traffic, or running two distinct protocol instances, one for each address family. The exclusive use of IPv6 for all control traffic is RECOMMENDED
, since using both protocols at the same time doubles the amount of traffic devoted to neighbour discovery and link quality estimation.
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) multicast address 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 acknowledgments, all Babel TLVs 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 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 may be applied to packets sent by a Babel speaker: outgoing TLVs are buffered and SHOULD
be sent with a random delay. This is done for two purposes: it avoids synchronisation of multiple Babel speakers across a network [JITTER
], and it allows for the aggregation of multiple TLVs into a single packet.
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 Section 3.7.2
and Section 3.8.1
), then the TLV MUST
be sent within a short time known as the urgent timeout (see Appendix B
for recommended values). When the TLV is governed by a timeout explicitly included in a previous TLV, such as in the case of Acknowledgments (Section 4.6.4
), Updates (Section 3.7
), and IHUs (Section 3.4.2
), then the TLV MUST
be sent 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 within one-half of the Multicast Hello interval.
In order to avoid packet drops (either at the sender or at the receiver), a delay SHOULD
be introduced between successive packets sent out on the same interface, within the constraints of the previous paragraph. Note, however, that such packet pacing might impair the ability of some link layers (e.g., IEEE 802.11 [IEEE802.11
]) to perform packet aggregation.
In this section, we describe the data structures that every Babel speaker maintains. This description is conceptual: a Babel speaker may use different data structures as long as the resulting protocol is the same as the one described in this document. For example, rather than maintaining a single table containing both selected and unselected (fallback) routes, as described in Section 3.2.6
, an actual implementation would probably use two tables, one with selected routes and one with fallback routes.
Sequence numbers (seqnos) appear in a number of Babel data structures, and they are interpreted as integers modulo 216
. For the purposes of this document, arithmetic on sequence numbers is defined as follows.
Given a seqno s and a non-negative integer n, the sum of s and n is defined by the following:
s + n (modulo 216
) = (s + n) MOD 216
s + n (modulo 216
) = (s + n) AND 65535
where MOD is the modulo operation yielding a non-negative integer, and AND is the bitwise conjunction operation.
Given two sequence numbers s and s', the relation s is less than s' (s < s') is defined by the following:
s < s' (modulo 216
) when 0 < ((s' - s) MOD 216
) < 32768
s < s' (modulo 216
) when s /= s' and ((s' - s) AND 32768) = 0.
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 216
) whenever it receives a request for a new sequence number (Section 184.108.40.206
). A node SHOULD NOT
increment its sequence number (seqno) spontaneously, since increasing seqnos makes it less likely that other nodes will have feasible alternate routes when their selected routes fail.
The interface table contains the list of interfaces on which the node speaks the Babel protocol. Every interface table entry contains the 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 216
) whenever a Multicast Hello is sent. (Note that an interface's Multicast Hello seqno is unrelated to the node's seqno.)
There are two timers associated with each interface table entry. The periodic multicast hello timer governs the sending of scheduled Multicast Hello and IHU packets (Section 3.4
). The periodic Update timer governs the sending of periodic route updates (Section 3.7.1
). See Appendix B
for suggested time constants.
The neighbour table contains the list of all neighbouring interfaces 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 entry contains the following data:
the local node's interface over which this neighbour is reachable;
the address of the neighbouring interface;
a history of recently received Multicast Hello packets from this 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 neighbour have been received by the local node;
a history of recently received Unicast Hello packets from this neighbour;
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 has expired;
the expected incoming Multicast Hello sequence number for this neighbour, an integer modulo 216.
the expected incoming Unicast Hello sequence number for this neighbour, an integer modulo 216.
the outgoing Unicast Hello sequence number for this neighbour, an integer modulo 216 that is sent with each Unicast Hello TLV to this neighbour and is incremented (modulo 216) whenever a Unicast Hello is sent. (Note that the outgoing Unicast Hello seqno for a neighbour is distinct from the interface's outgoing Multicast Hello seqno.)
There are three timers associated with each neighbour entry -- the multicast hello timer, which is set to the interval value carried by scheduled Multicast Hello TLVs sent by this neighbour, the unicast hello 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 interval carried in IHU TLVs (see "IHU Hold time" in Appendix B
for suggested values).
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 situation that can notably arise when wireless nodes with multiple radios are involved.
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 entry contains the following data:
the prefix (prefix, plen), where plen is the prefix length in bits, that this entry applies to;
the router-id of a router originating this prefix;
a pair (seqno, metric), this source's feasibility 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 3.7.3
The route table contains the routes known to this node. It is indexed by triples of the form (prefix, plen, neighbour), and every route table entry contains the following data:
the source (prefix, plen, router-id) for which this route is advertised;
the neighbour (an entry in the neighbour table) that advertised this route;
the metric with which this route was advertised by the neighbour, or FFFF hexadecimal (infinity) for a recently retracted route;
the sequence number with which this route was advertised;
the next-hop address of this route;
a boolean flag indicating whether this route is selected, i.e., whether it is currently being used for forwarding and is 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 3.5.3
Note that there are two distinct (seqno, metric) pairs associated with each route: the route's distance, which is stored in the route table, and the feasibility distance, which is stored in the source table and shared between all routes with the same source.
The table of pending seqno 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 (prefix, plen, router-id), and every entry in this table contains the following data:
the prefix, plen, router-id, and seqno being requested;
the neighbour, if any, on behalf of which we are forwarding this request;
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 seqno request; it governs both the resending of requests and their expiry.
A Babel speaker may request that a neighbour receiving a given packet reply with an explicit acknowledgment within a given time. While the use of acknowledgment requests is optional, every Babel speaker MUST
be able to reply to such a request.
An acknowledgment MUST
be sent to a unicast destination. On the other hand, acknowledgment requests may be sent to either unicast or multicast destinations, in which case they request an acknowledgment from all of the receiving nodes.
When to request acknowledgments is a matter of local policy; the simplest strategy is to never request acknowledgments and to rely on periodic updates to ensure that any reachable routes are eventually propagated throughout the routing domain. In order to improve convergence speed and to reduce the amount of control traffic, acknowledgment requests MAY
be used in order to reliably send urgent updates (Section 3.7.2
) and retractions (Section 3.5.4
), especially 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 acknowledgment requests is not necessary and NOT RECOMMENDED
, as the acknowledgments cause additional traffic and may force additional Address Resolution Protocol (ARP) or Neighbour Discovery (ND) exchanges.
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, neighbour acquisition additionally provides some statistics that may be useful for link quality computation.
Before it can exchange routing information with a neighbour, a Babel node MUST
create an entry for that neighbour in the neighbour table. When to do that is implementation-specific; suitable strategies include 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 resources, an implementation SHOULD
discard an entry when it has been unused for long enough; suitable strategies include dropping the neighbour after a timeout, and dropping a neighbour when the associated Hello histories become empty (see Appendix A.2
Every Babel node sends Hello TLVs to its neighbours, at regular or irregular intervals, to indicate that it is alive. Each Hello TLV carries an increasing (modulo 216
) sequence number and an upper bound on 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: 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 was received at time t0 and carried interval i, then the previous promise of sending another Hello before time t0 + i still holds). We say that a Hello is "scheduled" if it carries a nonzero interval, and "unscheduled" otherwise.
There are two kinds of Hellos: Multicast Hellos, which use a per-interface Hello counter (the Multicast Hello seqno), and Unicast 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 given interface, either by sending it to a multicast address or by sending it to one unicast address per neighbour (hence, the term "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a given seqno should normally be sent to just one neighbour (over unicast), since the sequence numbers of different neighbours are not in general synchronised.
Multicast Hellos sent over multicast can be used for neighbour discovery; hence, a node SHOULD
send periodic (scheduled) Multicast Hellos unless neighbour discovery is performed by means outside of the Babel protocol. A node MAY
send Unicast Hellos or unscheduled Hellos of either kind for any reason, such as reducing the amount of multicast traffic or improving reliability on link technologies with poor support for link-layer multicast.
A node MAY
send a scheduled Hello ahead of time. A node MAY
change its scheduled Hello interval. The Hello interval MAY
be decreased at any time; it MAY
be increased immediately before sending a Hello TLV, but SHOULD NOT
be increased at other times. (Equivalently, a node SHOULD
send a scheduled Hello immediately after increasing its Hello interval.)
How to deal with received Hello TLVs and what statistics to maintain are considered local implementation matters; typically, a node will maintain some sort of history of recently received Hellos. An example of a suitable algorithm is described in Appendix A.1
After receiving a Hello, or determining that it has missed one, the node recomputes the association's cost (Section 3.4.3
) and runs the route selection procedure (Section 3.6
In order to establish bidirectional reachability, every node sends 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 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 little packet loss. While IHUs are conceptually unicast, they MAY
be sent to a multicast address in order to avoid an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs into a single packet.
In addition to the periodic IHUs, a node MAY
, at any time, send an unscheduled IHU packet. It MAY
also, at any time, decrease its IHU interval, and it MAY
increase its IHU interval immediately before sending an IHU, but SHOULD NOT
increase it at any other time. (Equivalently, a node SHOULD
send an extra IHU immediately after increasing its Hello interval.)
Every IHU TLV contains two pieces of data: the link's rxcost (reception cost) from the sender's perspective, used by the neighbour for computing link costs (Section 3.4.3
), and the interval between periodic IHU packets. A node receiving an IHU sets the value of the txcost (transmission cost) maintained in the neighbour table to the value 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 (see "IHU Hold time" in Appendix B
for suggested values). When a neighbour's IHU timer expires, the neighbour's txcost is set to infinity.
After updating a neighbour's txcost, the receiving node recomputes the neighbour's cost (Section 3.4.3
) and runs the route selection procedure (Section 3.6
A neighbourship association's link cost is computed from the values maintained in the neighbour table: the statistics kept in the neighbour table about the reception of Hellos, and the txcost computed from received IHU packets.
For every neighbour, a Babel node computes a value known as this neighbour's rxcost. This value is usually derived from the Hello history, 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.
Since nodes do not necessarily send periodic Unicast Hellos but do usually send periodic Multicast Hellos (Section 3.4.1
), a node SHOULD
use an algorithm that yields a finite rxcost when only Multicast Hellos are received, unless interoperability with nodes that only send Multicast Hellos is not required.
How the txcost and rxcost are combined in order to compute a link's cost is a matter of local policy; as far as Babel's correctness is concerned, only the following conditions MUST
the cost is strictly positive;
if no Hello TLVs of either kind were received recently, then the cost is infinite;
if the txcost is infinite, then the cost is infinite.
See Appendix A.2
strategies for computing a link's cost.
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 a nondecreasing (modulo 216
) integer that carries the originating router seqno, and metric is the announced metric.
Before being accepted, an update is checked against the feasibility condition (Section 3.5.1
), which ensures that the 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 selected, as described in Section 3.5.3
. If the feasibility condition is satisfied, then the update cannot possibly cause a routing loop.
The feasibility condition is applied to all received updates. The feasibility condition compares the metric in the received update with the metrics of the updates previously sent by the receiving node; updates that fail the feasibility condition, and therefore have metrics large enough to cause a routing loop, are either ignored or prevent the resulting route from being selected.
A feasibility distance is a pair (seqno, metric), where seqno is an integer modulo 216
and metric is a positive integer. Feasibility distances are compared lexicographically, with the first component inverted: we say that a distance (seqno, metric) is strictly better than a distance (seqno', metric'), written
(seqno, metric) < (seqno', metric')
seqno > seqno' or (seqno = seqno' and metric < metric')
where sequence numbers are compared modulo 216
Given a source (prefix, plen, router-id), a node's feasibility distance 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 node for the prefix (prefix, plen) and the given router-id. Feasibility distances are maintained in the source table, the exact procedure is given in Section 3.7.3
A received update is feasible when either it is a retraction (its metric is FFFF hexadecimal), or the advertised distance is strictly better, in the sense defined above, than the feasibility distance for the corresponding source. More precisely, a route advertisement carrying the quintuple (prefix, plen, router-id, seqno, metric) is feasible if one of the following conditions holds:
metric is infinite; or
no entry exists in the source table indexed by (prefix, plen, router-id); or
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 the metric advertised by the neighbour, not the route's metric; hence, a fluctuation in a neighbour's cost cannot render a selected route unfeasible. Note further that retractions (updates with infinite metric) are always feasible, since they cannot possibly cause a routing loop.
A route's metric is computed from the metric advertised by the neighbour and the neighbour's link cost. Just like cost 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 locally computed link cost c and the metric m advertised by a neighbour MUST
only satisfy the following conditions:
if c is infinite, then M(c, m) is infinite;
M is strictly monotonic: M(c, m) > m.
Additionally, the metric SHOULD
satisfy the following condition:
M is left-distributive: if m <= m', then M(c, m) <= M(c, m').
While strict monotonicity is essential to the integrity of the network (persistent routing loops may arise if it is not satisfied), 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 fact, a global optimum may not even exist).
The conditions above are easily satisfied by using the additive metric, i.e., by defining M(c, m) = c + m. Since the additive metric is useful with a large range of cost computation strategies, it is the RECOMMENDED
default. See also Appendix C
, which describes a technique that makes it possible to tweak the values of individual metrics without running the risk of creating routing loops.
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 table entry indexed by (prefix, plen, neigh).
If no such entry exists:
if the update is unfeasible, it MAY be ignored;
if the metric is infinite (the update is a retraction of a route we do not know about), the update is ignored;
otherwise, a new entry is created in the route table, indexed by (prefix, plen, neigh), with source equal to (prefix, plen, router-id), seqno equal to seqno, and an advertised metric equal to the metric carried by the update.
If such an entry exists:
if the entry is currently selected, the update is unfeasible, and the router-id of the update is equal to the router-id of the entry, then the update MAY be ignored;
otherwise, the entry's sequence number, advertised metric, metric, and router-id are updated, and if the advertised metric is not infinite, the route's expiry timer is reset to a small multiple of the interval value included in the update (see "Route Expiry time" in Appendix B for suggested values). If the update is unfeasible, then the (now unfeasible) entry MUST be immediately 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 described in Section 3.7.2.
Note that the route table may contain unfeasible routes, either because they were created by an unfeasible update or due to a metric fluctuation. Such routes are never selected, since they are not known to be loop-free. Should all the feasible routes become unusable, however, the unfeasible routes can be made feasible and therefore possible to select by sending requests along them (see Section 3.8.2
When a route's expiry timer triggers, the behaviour depends on 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 route table is updated, the route selection procedure (Section 3.6
) is run.
When a prefix P is retracted (because all routes are unfeasible or have an infinite metric, whether due to the expiry timer or for other reasons), 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 (Section 2.8
To avoid this issue, whenever a prefix P is retracted, a route table entry with infinite metric is maintained as described in Section 3.5.3
. As long as this entry is maintained, packets destined to an address within P MUST NOT
be forwarded by following a route for a shorter prefix. This entry is removed as soon as a finite-metric update for prefix P is received and the resulting route selected. If no such update is forthcoming, the infinite metric entry SHOULD
be maintained at least until it is guaranteed that no neighbour has selected the current node as next hop for prefix P. This can be achieved by either:
waiting until the route's expiry timer has expired (Section 3.5.3); or
sending a retraction with an acknowledgment request (Section 3.3) to every reachable neighbour that has not explicitly retracted prefix P, and waiting for all acknowledgments.
The former option is simpler and ensures that, at that point, any routes for prefix P pointing at the current node have expired. However, since the expiry time can be as high as a few minutes, doing that prevents automatic aggregation by creating spurious black-holes for aggregated routes. The latter option is RECOMMENDED
as it dramatically reduces the time for which a prefix is unreachable in the presence of aggregated routes.
Route selection is the process by which a single route for a given prefix is selected to be used for forwarding packets and to be re-advertised to a node's neighbours.
Babel is designed to allow flexible route selection policies. As far as the algorithm's correctness is concerned, the route selection policy MUST
only satisfy the following properties:
a route with infinite metric (a retracted route) is never selected;
an unfeasible route is never selected.
Babel nodes using different route selection strategies will interoperate and will not create routing loops as long as these two properties hold.
Route selection MUST NOT
take seqnos into account: a route MUST NOT
be preferred just because it carries a higher (more recent) seqno. Doing otherwise would cause route oscillation while a new seqno propagates across the network, and might create persistent black-holes if the metric being used is not left-distributive (Section 3.5.2
The obvious route selection strategy is to pick, for every destination, the feasible route with minimal metric. When all metrics are stable, this approach ensures convergence to a tree of shortest paths (assuming that the metric is left-distributive, see Section 3.5.2
). There are two reasons, however, why this strategy may lead to instability in the presence of continuously varying metrics. First, if two parallel routes oscillate around a common value, then the smallest metric strategy will keep switching between the two. Second, the selection of a route increases congestion along it, which might increase packet loss, which in turn could cause its metric to increase; this kind of feedback loop is prone to causing persistent oscillations.
In order to limit these kinds of instabilities, a route selection strategy SHOULD
include some form of hysteresis, i.e., be sensitive to a route's history: the strategy should only switch from the currently selected route to a different route if the latter has been consistently good for some period of time. A RECOMMENDED
hysteresis algorithm is given in Appendix A.3
After the route selection procedure is run, triggered updates (Section 3.7.2
) and requests (Section 3.8.2
) are sent.
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 TLVs on all of its connected interfaces; however, on link technologies where multicast is significantly more expensive than unicast, a node MAY
choose to send multiple copies of updates in unicast packets, especially 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 may send 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., it carries the address of a local interface, the prefix of 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 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 learnt from another Babel speaker, the router-id and sequence number are copied from the route table entry, and the metric is computed as specified in Section 3.5.2
Every Babel speaker MUST
advertise each of its selected routes on every interface, at least once every Update interval. Since Babel doesn't suffer from routing loops (there is no "counting to infinity") and relies heavily on triggered updates (Section 3.7.2
), this full dump only needs to happen infrequently (see Appendix B
for suggested intervals).
In addition to 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, whenever it changes the selected router-id for a given destination, a node MUST
send an update as an urgent TLV (as defined in Section 3.1
). Additionally, it SHOULD
make a reasonable attempt at ensuring that all reachable 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 acknowledgment 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 acknowledgments 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, 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 described in Section 3.1
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, due to a received update, because 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, 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 route's metric, or to propagate a new sequence number (except to satisfy a request, as specified in Section 3.8
Before sending an update (prefix, plen, router-id, seqno, metric) with finite metric (i.e., not a route retraction), a Babel node updates the feasibility 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:
if seqno > seqno', then seqno' := seqno, metric' := metric;
if seqno = seqno' and metric' > metric, then metric' := metric;
otherwise, nothing needs to be done.
The garbage-collection timer for the entry is then reset. Note that the feasibility distance is not updated and the garbage-collection timer is not reset when a retraction (an update with infinite metric) is sent.
When the garbage-collection timer expires, the entry is removed from the source table.
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 for prefix P is not sent on the particular interface over which the selected route towards prefix P was learnt.
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) when routing updates are sent over multicast.
In normal operation, a node's route table is populated by the regular and triggered updates sent by its neighbours. Under some circumstances, 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 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 the receiver.
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 request.
The exact behaviour is different for route requests and seqno requests.
When a node receives a route request for a given prefix, it checks its 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 a route does not exist, it MUST
send a retraction for that prefix.
When a node receives a wildcard route request, it SHOULD
send a full route table dump. Full route dumps SHOULD
be rate-limited, especially if they are sent over multicast.
When a node receives a seqno request for a given router-id and sequence number, it checks whether its route table contains a selected entry for 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 are equal and the entry's sequence number is no smaller (modulo 216
) than the requested sequence number, the node MUST
send an update for the given prefix. If the router-ids match, but the requested seqno is larger (modulo 216
) 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 (modulo 216
) and sends an update. A node MUST NOT
increase its sequence number by more than 1 in reaction to a single seqno request.
Otherwise, if the requested router-id is not its own, the received node 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 selects a neighbour to forward the request to as follows:
if the node has one or more feasible routes towards the requested prefix with a next hop that is not the requesting node, then the node MUST forward the request to the next hop of one such route;
otherwise, if the node has one or more (not feasible) routes to the requested prefix with a next hop that is not the requesting node, then the node SHOULD forward the request to the next hop of one such route.
In order to actually forward the request, the node decrements the hop count and sends the request in a unicast packet destined to the selected neighbour. The forwarded request SHOULD
be sent as an urgent TLV (as defined in Section 3.1
A node SHOULD
maintain a list of recently forwarded seqno requests and forward the reply (an update with a seqno sufficiently large to satisfy the request) as an urgent TLV (as defined in Section 3.1
). A node SHOULD
compare every incoming seqno request against its list of recently forwarded seqno requests and avoid forwarding the request if it is redundant (i.e., if the node has recently sent a request with the same prefix, router-id, and a seqno that is not smaller modulo 216
Since the request-forwarding mechanism does not necessarily obey the 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. 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 single request MUST NOT
be duplicated: it MUST NOT
be forwarded to a multicast address, and it MUST NOT
be forwarded to multiple neighbours. However, if a seqno request is resent by its originator, the subsequent copies may be forwarded to a different neighbour than the initial one.
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 220.127.116.11
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 but still has unexpired unfeasible routes to that destination MUST
send a seqno request; if it doesn't have any such routes, it MAY
still send 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 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 vanishes from the network; it MAY
be set to any value that is larger than the diameter of the network (64 is a suitable default value).
If the node has any (unfeasible) routes to the requested destination, then it MUST
send the request to at least one of the next-hop neighbours that advertised these routes, and SHOULD
send it to all of them; in any case, it MAY
send the request to any other neighbours, whether they advertise a route to the requested destination or not. A simple implementation strategy is therefore to unconditionally multicast the request over all interfaces.
Similar requests will be sent by other nodes that are affected by the route's loss. If the network is still connected, and assuming no packet loss, then at least one of these requests will be forwarded to the source, resulting in a route being advertised with a new sequence number. (Due to duplicate suppression, only a small number of such requests are expected to actually reach the source.)
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 (see "Request timeout" in Appendix B
for suggested values). In the presence of heavy packet loss, however, all such requests might be lost; in that case, the mechanism in the next section will eventually ensure that a new seqno is received.
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 3.5.1
, the receiving node will either ignore the update or unselect the route.
In order to keep routes from spuriously expiring because they have become unfeasible, a node SHOULD
send a unicast seqno request when it receives an unfeasible update for a route that is currently selected. The requested sequence number is computed from the source table as in Section 18.104.22.168
Additionally, since metric computation does not necessarily coincide with the delay in propagating updates, a node might receive an unfeasible update from a currently unselected neighbour that is preferable to the 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 advertised the preferable update.
In normal operation, a route's expiry timer never triggers: since 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 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, 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 either updates or retractions in response to non-wildcard route requests (Section 22.214.171.124
), this will usually result in the route being either refreshed or retracted.