Independent Submission J. Chroboczek Request for Comments: 6126 PPS, University of Paris 7 Category: Experimental April 2011 ISSN: 2070-1721 The Babel Routing Protocol
AbstractBabel is a loop-avoiding distance-vector routing protocol that is robust and efficient both in ordinary wired networks and in wireless mesh networks. Status of This Memo This document is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation. This document defines an Experimental Protocol for the Internet community. This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6126. Copyright Notice Copyright (c) 2011 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Specification of Requirements . . . . . . . . . . . . . . 4 2. Conceptual Description of the Protocol . . . . . . . . . . . . 4 2.1. Costs, Metrics, and Neighbourship . . . . . . . . . . . . 5 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . . 5 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . . 6 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . . 10 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . . 11 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 11 3.1. Message Transmission and Reception . . . . . . . . . . . . 11 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12 3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . . 15 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 15 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 17 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 27 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . . 30 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 6. Security Considerations . . . . . . . . . . . . . . . . . . . 39 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 40 7.1. Normative References . . . . . . . . . . . . . . . . . . . 40 7.2. Informative References . . . . . . . . . . . . . . . . . . 40 Appendix A. Cost and Metric Computation . . . . . . . . . . . . . 41 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 41 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . . 42 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . . 43 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . . 43 Appendix C. Simplified Implementations . . . . . . . . . . . . . 44 Appendix D. Software Availability . . . . . . . . . . . . . . . . 45
RIP], it strongly limits the frequency and duration of 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 many cases, this operation requires no packet exchanges at all. Babel then slowly converges, in a time on the scale of minutes, to an optimal configuration. This is achieved by using sequenced routes, a technique pioneered by Destination- Sequenced Distance-Vector routing [DSDV]. 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 (GC) time) will the routers involved participate in a routing loop for the same prefix; o assuming reasonable packet loss rates, 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, for example, on measured packet loss. 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 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. OSPF], IS-IS [IS-IS], or the Enhanced Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more suitable. Second, Babel does impose a hold time when a prefix is retracted (Section 3.5.5). While this hold time does not apply to the exact 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. RFC2119]. RIP], but includes a number of refinements that either prevent loop formation altogether, or ensure that a loop disappears in a timely manner and doesn't form again. Conceptually, Bellman-Ford is executed in parallel for every source of routing information (destination of data traffic). In the following discussion, we fix a source S; the reader will recall that the same algorithm is executed for all sources.
Section 3.5.2). A Babel node periodically broadcasts Hello messages to all of its neighbours; it also periodically sends an IHU ("I Heard You") message to every neighbour from which it has recently heard a Hello. From the information derived from Hello and IHU messages received from its neighbour B, a node A computes the cost C(A, B) of the link from A to B.
Many different feasibility conditions are possible. For example, BGP can be modelled as being a distance-vector protocol with a (rather drastic) feasibility condition: a routing update is only accepted when the receiving node's AS number is not included in the update's AS-Path attribute (note that BGP's feasibility condition does not ensure the absence of transitory "micro-loops" during reconvergence). Another simple feasibility condition, used in Destination-Sequenced Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand Distance Vector (AODV) routing, stems from the following observation: a routing loop can only arise after a router has switched to a route with a larger metric than the route that it had previously selected. Hence, one could decide that a route is feasible only when its metric at the local node would be no larger than the metric of the currently selected route, i.e., an announcement carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this constraint, then the metric at every router is nonincreasing, and the following invariant is always preserved: if A has selected B as its successor, then D(B) < D(A), which implies that the forwarding graph is loop-free. Babel uses a slightly more refined feasibility condition, used in EIGRP [DUAL]. Given a router A, define the feasibility distance of A, written FD(A), as the smallest metric that A has ever advertised for S to any of its neighbours. An update sent by a neighbour B of A is feasible when the metric D(B) advertised by B is strictly smaller than A's feasibility distance, i.e., when D(B) < FD(A). It is easy to see that this latter condition is no more restrictive than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; then D(A) is nonincreasing, hence at all times D(A) <= FD(A). Suppose now that A receives a DSDV-feasible update that advertises a metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). To see that it is strictly less restrictive, consider the following diagram, where A has selected the route through B, and D(A) = FD(A) = 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible for A, although its metric C(A, C) + D(C) = 5 is larger than that of the currently selected route: B 1 / \ 1 / \ S A \ / 1 \ / 4 C
To show that this feasibility condition still guarantees loop- freedom, recall that at the time when A accepts an update from B, the metric D(B) announced by B is no smaller than FD(B); since it is smaller than FD(A), at that point in time FD(B) < FD(A). Since this property is preserved when A sends updates, it remains true at all times, which ensures that the forwarding graph has no loops.
equally recent and the metric is strictly smaller. More formally, if FD(A) = (s, m), then an update carrying the distance (s', m') is feasible when either s' > s, or s = s' and m' < m. Assuming the sequence number of S is 137, the diagram above becomes: A | | FD(A) = (137, 1) S |1 \ | D(B) = (137, 2) 2 \| FD(B) = (137, 2) B After S increases its sequence number, and the new sequence number is propagated to B, we have: A | | FD(A) = (137, 1) S |1 \ | D(B) = (138, 2) 2 \| FD(B) = (138, 2) B at which point the route through B becomes feasible again. Note that while sequence numbers are used for determining feasibility, they are not necessarily used in route selection: a node will normally ignore the sequence number when selecting a route (Section 3.6).
Note that after a change in network topology not all such requests will, in general, reach the source, as some will be sent over links that are now broken. However, if the network is still connected, then at least one among the nodes suffering from spurious starvation has an (unfeasible) route to the source; hence, in the absence of packet loss, at least one such request will reach the source. (Resending requests a small number of times compensates for packet loss.) Since requests are forwarded with no regard to the feasibility condition, they may, in general, be caught in a forwarding loop; this is avoided by having nodes perform duplicate detection for the requests that they forward.
In effect, the routing loop disappears at the latest when routing information has gone around the loop. Since this process can be delayed by lost packets, Babel makes certain efforts to ensure that updates are sent reliably after a router-id change. Additionally, after the routers have advertised the two routes, both sources will be in their source tables, which will prevent them from ever again participating in a routing loop involving routes from S and S' (up to the source GC time, which, available memory permitting, can be set to arbitrarily large values). 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.)
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 (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 TLVs and acknowledgements, all Babel TLVs 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 packets sent by a Babel speaker: outgoing TLVs 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 it allows for the aggregation of multiple TLVs into a single packet. The exact delay and amount of jitter applied to a packet depends on whether it contains any urgent TLVs. Acknowledgement TLVs MUST be sent before the deadline specified in the corresponding request. The particular class of updates specified in Section 3.7.2 MUST be sent in a timely manner. The particular class of request and update TLVs specified in Section 3.8.2 SHOULD be sent in a timely manner. Section 220.127.116.11). 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.
Hello TLV on this interface and is incremented (modulo 2^16) whenever a Hello 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.
o the prefix (prefix, plen), where plen is the prefix length, that this entry applies to; o the router-id of a router originating this prefix; o 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. Section 3.5.4.
o the neighbour, if any, on behalf of 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; it governs both the resending of requests and their expiry. Section 3.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 Address Resolution Protocol (ARP) or Neighbour Discovery exchanges.
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 immediately before sending a Hello packet. (Equivalently, a node SHOULD send an unscheduled 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. A possible 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). Section 3.4.3), and the interval between periodic IHU packets. A node receiving an IHU updates the value of the sending neighbour's txcost (transmission cost), from its perspective, to the value contained in the IHU, and resets this neighbour's IHU timer to a small multiple of the value received in the IHU. When a neighbour's IHU timer expires, its 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). Appendix A.2. 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 treated as a retraction, depending on some other conditions (Section 3.5.4). If the feasibility condition is satisfied, then the update cannot possibly cause a routing loop, and the update is accepted.
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: 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 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. Appendix A.3, we give a number of examples of strictly monotonic, isotonic routing metrics that are known to work well in practice. 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 4.4. Section 3.6) is run.
Section 2.8). To avoid this issue, whenever a prefix is retracted, a routing table entry with infinite metric is maintained as described in Section 3.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.
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 3.7.2) and requests (Section 3.8.2) are sent. Section 3.5.2. Section 3.7.2), this full dump only needs to happen infrequently.
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 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 3.8).
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.
low, and performing an expanding horizon search is not necessary. A request MUST NOT be forwarded to a multicast address, and it MUST be forwarded to a single neighbour only. Section 18.104.22.168). Section 3.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 is "good enough", i.e., that would lead to the received route becoming selected were it feasible. Section 22.214.171.124), this will usually result in either the route being refreshed or a retraction being received.
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 TLVs into large packets, a Babel node MUST buffer every TLV and delay sending a UDP packet 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. ADDRARCH]. 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.
Fields : Type The type of the TLV. 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 TLV, any extra data MUST be silently ignored. Body The TLV body, the interpretation of which depends on the type. TLVs with an unknown type value MUST be silently ignored.
Nonce Set to the Nonce value of the Acknowledgement Request that prompted this Acknowledgement. Since nonce values are not globally unique, this TLV MUST be sent to a unicast address.
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 TLVs with an unknown value for the AE field MUST be silently ignored.
Fields : Type Set to 7 to indicate a Next Hop TLV. 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 Sent as 0 and MUST be ignored on reception. Next hop The next-hop address advertised by subsequent Update TLVs, for this address family. When the address family matches the network-layer protocol that this packet is transported over, a Next Hop TLV is not needed: in that case, the next hop is taken to be the source address of the packet. Next Hop TLVs with an unknown value for the AE field MUST be silently ignored.
Flags The individual bits of this field specify special handling of this TLV (see below). Every node MUST be able to interpret the flags with values 80 and 40 hexadecimal; unknown flags MUST be silently ignored. Plen 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 TLV with the flag with value 80 hexadecimal 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 FFFF hexadecimal (infinity) expresses that this announcement will not be repeated unless a request is received (Section 126.96.36.199). Seqno The originator's sequence number for this update. Metric The sender's metric for this route. The value FFFF hexadecimal (infinity) means that this is a route retraction. Prefix The prefix being advertised. This field's size is (Plen/8 - Omitted) rounded upwards. The Flags field is interpreted as follows: o if the bit with value 80 hexadecimal is set, then this Update establishes a new default prefix for subsequent Update TLVs with a matching address family within the same packet; o if the bit with value 40 hexadecimal is set, then the low-order 8 octets of the advertised prefix establish a new default router-id for this TLV and subsequent Update TLVs in the same packet. The prefix being advertised by an Update TLV is computed as follows: o the first Omitted octets of the prefix are taken from the previous Update TLV with flag 80 hexadecimal 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. If the Metric field is finite, the router-id of the originating node for this announcement is taken from the low-order 8 octets of the prefix advertised by this Update if the bit with value 40 hexadecimal is set in the Flags field. Otherwise, it is taken either from the preceding Router-Id packet, or the preceding Update packet with flag 40 hexadecimal set, whichever comes last. The next-hop address for this update is taken from the last preceding Next Hop TLV with a matching address family in the same packet; if no such TLV exists, it is taken from the network-layer source address of this packet. If the metric field is FFFF hexadecimal, this TLV specifies a retraction. In that case, the current router-id and the Seqno are not used. AE MAY then be 0, in which case this Update retracts all of the routes previously advertised on this interface. Update TLVs with an unknown value for the AE field MUST be silently ignored.
Prefix The prefix being requested. This field's size is Plen/8 rounded upwards. A Request TLV 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). A Request may be sent to a unicast address if it is destined to a single node, or to a multicast address if the request is destined to all of the neighbours of the sending interface.
Prefix The prefix being requested. This field's size is Plen/8 rounded upwards. A Seqno Request TLV prompts the receiving node to send an Update for the prefix specified by the AE, Plen, and Prefix fields, with either a router-id different from what is specified by the Router-Id field, or a Seqno no less than 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 188.8.131.52. While a Seqno Request MAY be sent to a multicast address, it MUST NOT be forwarded to a multicast address and MUST NOT be forwarded to more than one neighbour. A request MUST NOT be forwarded if its Hop Count field is 1.
[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", BCP 14, RFC 2119, March 1997. [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] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A high-throughput path metric for multi-hop wireless networks", Proc. MobiCom 2003, 2003. [IS-IS] "Information technology -- Telecommunications and information exchange between systems -- Intermediate System to Intermediate System intra-domain routeing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode network service (ISO 8473)", ISO/IEC 10589:2002. [JITTER] Floyd, S. and V. Jacobson, "The synchronization of periodic routing messages", IEEE/ACM Transactions on Networking 2, 2, 122-136, April 1994. [OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [PACKETBB] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009. [RIP] Malkin, G., "RIP Version 2", STD 56, RFC 2453, November 1998.
3.4.3 and 3.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 maintains statistics about the last 16 received Hello TLVs (Appendix A.1), computes costs by using the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX [ETX] on wireless links. It uses an additive algebra for metric computation (Appendix A.3.1).
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 received Hello (the extra margin allows for the delay due to jitter). Whenever the Hello timer associated to a neighbour expires, the local 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 received from this neighbour (no extra margin is necessary in this case). 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, written beta, of the probability that a Hello TLV 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 TLV. The cost is then computed by
cost = 256/(alpha * beta) or, equivalently, cost = (MAX(txcost, 256) * rxcost) / 256. Section 3.5.2), the value k must be greater than -c.
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 a packet depends on whether it contains any urgent TLVs or not. Urgent triggered updates and urgent requests are delayed by no more than 200 ms; other TLVs are delayed by no more than one-half the Hello interval.
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. http://www.pps.jussieu.fr/~jch/software/babel/>.