Network Working Group J. Chroboczek Internet-Draft University of Paris 7 Intended status: Experimental April 7, 2009 Expires: October 9, 2009 The Babel routing protocol draft-chroboczek-babel-routing-protocol-00 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 October 9, 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. Abstract Babel is a loop-free distance vector routing protocol that is designed to be robust and efficient both in ordinary wired networks and in wireless mesh networks. Chroboczek Expires October 9, 2009 [Page 1] Internet-Draft The Babel routing protocol April 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 2. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Message Transmission and Reception . . . . . . . . . . . . 4 2.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 5 2.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . . 7 2.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 7 2.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 9 2.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 12 2.7. Sending updates . . . . . . . . . . . . . . . . . . . . . 13 2.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 15 3. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 18 3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 19 3.3. Message format . . . . . . . . . . . . . . . . . . . . . . 19 3.4. Details of Specific Messages . . . . . . . . . . . . . . . 20 4. Security Considerations . . . . . . . . . . . . . . . . . . . 27 5. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Appendix A. Cost and metric computation . . . . . . . . . . . . . 29 A.1. Cost computation . . . . . . . . . . . . . . . . . . . . . 29 A.2. Metric computation . . . . . . . . . . . . . . . . . . . . 30 A.3. Cross-layer approaches . . . . . . . . . . . . . . . . . . 30 Appendix B. Simplified implementations . . . . . . . . . . . . . 31 B.1. The simplified feasibility condition . . . . . . . . . . . 31 B.2. Parasitic implementations . . . . . . . . . . . . . . . . 32 Appendix C. Software availability . . . . . . . . . . . . . . . . 32 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 32 Chroboczek Expires October 9, 2009 [Page 2] Internet-Draft The Babel routing protocol April 2009 1. Introduction Babel is a distance vector routing protocol 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 blackholes, 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 create a transient routing loop for this particular prefix; this loop disappears in a time proportional to its diameter, and never again (up to a configurable 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 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 choose to use smaller time constants. The ability to build heterogeneous networks makes Babel particularly adapted to the wireless environment. Finally, Babel is a hybrid routing protocol, in the sense that it can Chroboczek Expires October 9, 2009 [Page 3] Internet-Draft The Babel routing protocol April 2009 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 subsumes 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. 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 [RFC3513]. (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; a Babel speaker MUST silently discard any packets whose source address is not either an IPv6 unicast link-local address, or an IPv4 address belonging to the local network. 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. With the exception of Hello messages and acknowledgements, all Babel messages can be sent to either unicast or multicast addresses, and Chroboczek Expires October 9, 2009 [Page 4] Internet-Draft The Babel routing protocol April 2009 their semantics does not depend on whether the destination was unicast or multicast. Hence, a Babel speaker does not need to determine the destination address of a packet that it receives in order to interpret it. Hello messages MUST NOT be sent to a unicast address. Acknowledgement messages MUST NOT be sent to a multicast address. A moderate amount of jitter is applied to messages sent by a Babel speaker: outgoing messages are buffered, and MUST 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 amouont 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.1 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 2.2.1. Sequence number A node's sequence number is a 16-bit integer that is included in route updates sent for routes exported by this node. A node increments its sequence number (modulo 2^16) whenever it receives an explicit 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.) 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 Chroboczek Expires October 9, 2009 [Page 5] Internet-Draft The Babel routing protocol April 2009 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 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. An entry in the neighbour table is flushed whenever the hello history for this neighbour becomes empty. Note that the neighbour table is indexed by IP addresses, not by router-ids; thus, neighbourship is a relationship between interfaces, not between nodes. Therfore, two nodes with multiple interfaces can participate in multiple neighbourship relationships, which is particularly common with 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 the advertised prefix and prefix length; o a pair (seqno, metric), known as this source's reference distance. A source table entry SHOULD be garbage collected a few minutes after the last advertisement for this source has been sent, in order to deal gracefully with sources rebooting and loosing their sequence number. The exact behaviour of the source garbage collection timer is specified in Section 2.7.2. 2.2.5. The Route Table The route table is indexed by triples of the form (prefix, plen, neigh), and every routing 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; o the sequence number with which this route was advertised; Chroboczek Expires October 9, 2009 [Page 6] Internet-Draft The Babel routing protocol April 2009 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. 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 neighbour that originated the route being requested; o the seqno being requested; o the neighbour, if any, for which we are forwarding this request. 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 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. We suggest that acknowledged packets should be used in order to send urgent updates (Section 2.7.1) 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 of each of its interfaces and ascertains bidirectional reachability. On unreliable media, neighbour acquisition additionally provides enough statistics to perform link cost computation. Chroboczek Expires October 9, 2009 [Page 7] Internet-Draft The Babel routing protocol April 2009 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 sending interface's Hello interval, the interval between successive periodic packets. 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, a history of recently received Hello packets as well as a timer that expires whenever a periodic Hello is due. 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 computation, 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; the receiving node adds (nr - ne) 0 bits to the hello history (we ``fast-forward''). The receiving node then appends one 1 bit to the neighbour's hello history, resets the neighbour's hello timer, and sets ne to (nr + 1). Whenever the Hello timer associated to a neighbour expires, the local node increases the expected hello number, and adds a 0 bit to this neighbour's hello history. 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. 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. Chroboczek Expires October 9, 2009 [Page 8] Internet-Draft The Babel routing protocol April 2009 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, change its IHU interval. 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 packet updates the sending neighbour's txcost value to the value contained in the packet, and resets this neighbour's IHU flush timer to a value derived from the value received in the IHU packet. When the neighbour's IHU flush timer expires, the neighbour's txcost is set to infinity. 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 data, such as statistics maintained by the link layer. The rxcost is sent to a neighbour in each IHU message. How the txcost and the 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 two conditions MUST be satisfied: if the hello history is empty, then the cost is infinite; 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) [DUAL], a condition that 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 Chroboczek Expires October 9, 2009 [Page 9] Internet-Draft The Babel routing protocol April 2009 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.2). 2.5.1. The Feasibility Condition A feasibility distance, or distance for short, is a pair (seqno, metric), where metric is a positive integer and seqno is an integer modulo 2^16. Feasibility distances are compared lexicographically, with the first element inverted. In other words, we say that a distance (seqno, metric) is better than a distance (seqno', metric'), written (seqno, metric) < (seqno', metric') 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 reference distances of all the updates ever sent for that source. For every source that it has ever advertised, a Babel node maintains its reference distance; the exact procedure is given in Section 2.7.2. An update is feasible when the advertised distance is better, in the sense defined above, than the reference distance for the corresponding source; additionally, all retractions are feasible. More precisely, a route advertisement (prefix, plen, router-id, seqno, metric) is feasible if the following condition holds: o metric is infinite; or o no entry exists in the source table for the triple (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'. 2.5.2. Metric Computation A route's metric is computed from its reference metric -- the metric that the neighbour advertised, 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 link's cost and a reference metric MUST only satisfy the following conditions: Chroboczek Expires October 9, 2009 [Page 10] Internet-Draft The Babel routing protocol April 2009 if c is infinite or m is infinite, then M(c, m) is inifinite; M is strictly monotonous: M(c, m) > m; Additonally, the metric SHOULD satisfy the following condition: M is isotonous: 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, particular care has been given to encoding them efficiently. The 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 an explicit Router Id message in the same packet. 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 &mdash this is known as address compression [PACKETBB]. Finally, as a special optimisation for the case when router-ids are assigned so as to coincide with the host id part of IPv6 addresses, 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 indexed by (neigh, id, prefix). If no such entry exists: o if the update is unfeasible, it is ignored; o if the metric is infinite (the update is a retraction), the update is ignored; Chroboczek Expires October 9, 2009 [Page 11] Internet-Draft The Babel routing protocol April 2009 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. carried an infinite metric. 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 metric is infinite, the garbage collection timer for the route is reset. 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 subsumes 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 MUST be maintained, 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 a few minutes, the entry is garbage-collected normally. 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. 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: Chroboczek Expires October 9, 2009 [Page 12] Internet-Draft The Babel routing protocol April 2009 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 routes should be avoided; o routes with a large seqno should be preferred over routes with a small seqno. 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. 2.7. Sending updates A Babel speaker periodically advertises its set of selected routes to its neighbours. Normally, this is done by sending one or more packets containing update messages on all of its connected interfaces; however, on link layers where multicast is 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 speedily clear any black-holes, 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, while the metric is computed as specified in Section 2.5.2. 2.7.1. Triggered Updates In addition to the normal, periodic routing updates, a Babel speaker sometimes sends unscheduled, or triggered updates in order to inform its neighbours of a significant change in the routing topology. A change of router-id for the selected route to a given prefix may be indicative of a routing loop; hence, a node MUST speedily send a triggered update whenever it changes the selected router-id for a given destination. Additionally, it SHOULD make a reasonable attempt Chroboczek Expires October 9, 2009 [Page 13] Internet-Draft The Babel routing protocol April 2009 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 significant 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 less worrying: if the route retraction doesn't reach all neighbours, a blackhole might be created, which, unlike a routing loop, does not endanger the integrity of the network. When a route is retracted, a node SHOULD speedily send a triggered update, and SHOULD make a reasonable attempt at ensuiring 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. 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.2. Maintaining Reference Distances Before sending an update (prefix, 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, id) exists in the source table, then one is created with value (prefix, id, seqno, metric). If an entry (prefix, 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 be done. The garbage collection timer for the modified entry is then reset. (Note that the garbage collection timer need not be reset when a retraction is sent.) Chroboczek Expires October 9, 2009 [Page 14] Internet-Draft The Babel routing protocol April 2009 2.7.3. Split Horizon When run over a transitive, symmetric link technology, e.g. a wired LAN technology such as Ethernet, a Babel node SHOULD use an optimisation known as split horizon. When split horizon is used, a routing update is not sent on a given interface when the route was 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 used 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 MUST send explicit requests to cause a resynchronisation with the source after a mobility event, and SHOULD send explicit requests 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 SHOULD be 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. If an update is sent, it MUST be sent on the interface on which the request was received. In order to be productive for other nodes on the same link, an update SHOULD be sent to a multicast address, but MAY be sent to the unicast address of the requestor. 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 this exact prefix; if it is present, it sends an update; if it is not, it sends an explicit retraction for that prefix. Chroboczek Expires October 9, 2009 [Page 15] Internet-Draft The Babel routing protocol April 2009 When a node receives a wildcard route request, it sends a full routing table dump on the interface where the request was received. 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, it ignores the request. If an entry for the given prefix exists, and either the router-ids mis-match or the router-ids match and the entry's sequence number is no smaller than the requested sequence number, it sends 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 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. A node SHOULD maintain a list of recently forwarded requests, and forward the reply speedily. 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 their propagation. However, since requests are only ever forwarded as unicast packets, the initial hop count need not be kept particularly low, and 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 a node MUST send a request (Section 2.8.2.1). Chroboczek Expires October 9, 2009 [Page 16] 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 on all of the node's attached interfaces. This 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. 2.8.2.2. Dealing with unfeasible updates When a link's cost increases, a node may 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 of unfeasible updates, a node SHOULD send a seqno request whenever it receives an unfeasible update for a route that is currently selected. The requested sequence number is derived from the source table as above. Additionally, a node SHOULD send a 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 update's interval, a new update or an explicit route retraction should arrive in time to prevent a route from expiring. In the presence of heavy packet loss, however, a route may spuriously expire. In orther to avoid such spurious expiry, a Babel node SHOULD send a unicast route request to the route's next hop shortly before it expires it. Chroboczek Expires October 9, 2009 [Page 17] Internet-Draft The Babel routing protocol April 2009 3. Protocol Encoding A Babel packet is sent as the body of a UDP datagram destined to a link-local multicast or a unicast address, over IPv4 or IPv6. Babel packets MUST NOT be sent as IPv6 Jumbograms. The body of a Babel packet is a sequence of one or more Babel messages. 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 interfaces 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 router MUST be able to receive packets that are as large as any attached interface's MTU or 512, whichever is larger. In order to avoid global synchronisation of a Babel network, a Babel node MUST buffer every packet and delay sending it by a small, randomly chosen delay [JITTER]. By default, the sample implementation of Babel uses the IPv6 multicast address ff02::cca6:c0f9:e182:5373 and UDP port 8475. 3.1. Data Types 3.1.1. Interval Relative times are carried as two-octet 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 [RFC3513]. 3.1.3. Address Since the bulk of the protocol is taken by addresses, three address encodings are defined. Additionally, a common subnet prefix may be omitted from adresses -- this is known as address compression [PACKETBB]. Address encodings: Chroboczek Expires October 9, 2009 [Page 18] Internet-Draft The Babel routing protocol April 2009 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. 8 octets long, a prefix of fe80::/64 is implied. 3.1.4. Prefixes A network prefix is encoded just like a network address, but it is encoded using the smallest number of octets that are enough to encode 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 This octet has an arbitrary but carefully chosen value's 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. Body length This is 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... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Chroboczek Expires October 9, 2009 [Page 19] Internet-Draft The Babel routing protocol April 2009 Fields : Type This octet 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. 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. Chroboczek Expires October 9, 2009 [Page 20] Internet-Draft The Babel routing protocol April 2009 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 sender send an Acknowledgement message within a 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 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. Chroboczek Expires October 9, 2009 [Page 21] Internet-Draft The Babel routing protocol April 2009 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 establishing reverse reachability and determining a link's reception cost. Fields : 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 counter for this interface. Interval An upper bound, expressed in centiseconds, on the time after which the sending node will send a new Hello message. Note that 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... +-+-+-+-+-+-+-+-+-+-+-+- The IHU (``I Heard You'') message is used for confirming bidirectional reachability and carrying a link's transmission cost. Fields : Chroboczek Expires October 9, 2009 [Page 22] Internet-Draft The Babel routing protocol April 2009 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 a special optimisation, it MAY be 0 if the message is sent to a unicast address, if the association is over a point-to-point link, when bidirectional reachability is ascertained by means outside of the Babel protocol, or when the advertised cost is 0xFFFF (infinity). 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. The sending node SHOULD use this value in order to compute a hold value 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 node. However, IHU messages contain a destination address so that they MAY be sent to a multicast address; this avoids the need for an ARP or Neighbour Discovery exchange when a neighbour is not used for data traffic, and allows aggregation of IHU messages destined to distinct neighbours into a single packet. 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 : Chroboczek Expires October 9, 2009 [Page 23] Internet-Draft The Babel routing protocol April 2009 Type Set to 6 to indicate a Router Id 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. 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 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 address family that this packet is transported over, a Next Hop message is not needed: in that case, the default next hop is the source address of this packet. 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 a route. It can also establish a new Chroboczek Expires October 9, 2009 [Page 24] Internet-Draft The Babel routing protocol April 2009 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 routes previously advertised 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 MAY use this value to compute a hold time for this routing table entry. The value 0xFFFF expresses that this announcement might not be repeated. 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 this message's prefix 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 previous Next Hop message for 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. Chroboczek Expires October 9, 2009 [Page 25] Internet-Draft The Babel routing protocol April 2009 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; o the next (Plen/8 - Omitted) (rounded upwards) octets are taken from the Prefix field; o the remaining octets are set to 0. 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... +-+-+-+-+-+-+-+-+-+-+-+- 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 is 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 neighbours of the sending interface. Chroboczek Expires October 9, 2009 [Page 26] 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... +-+-+-+-+-+-+-+-+-+-+ 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. The value 0 specifies that this is a request for a full table dump. 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, minus 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, but the receiving node has a neighbour N other than the sending node that advertises a route (feasible or not) for the given prefix, this request SHOULD be forwarded to N after decrementing the Hop Count field. While a Seqno Request MAY be sent to a multicast address, it MUST NOT be forwarded to a multicast address. A request MUST NOT be forwarded if its Hop Count field is 1. 4. Security Considerations As defined in this document, Babel is a completely insecure protocol. Any attacker can attract arbitrary data traffic by advertising routes with a low metric. This particular issue can be solved either by Chroboczek Expires October 9, 2009 [Page 27] Internet-Draft The Babel routing protocol April 2009 applying 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 by using randomly chosen router ids, randomly chosen IP addresses, and changing them periodically. 5. 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. [EGP] Mills, D., "Exterior Gateway Protocol formal specification", RFC 904, April 1984. [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. [RFC3513] Hinden, R. and S. Deering, "Internet Protocol Version 6 (IPv6) Addressing Architecture", RFC 3513. Chroboczek Expires October 9, 2009 [Page 28] Internet-Draft The Babel routing protocol April 2009 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. Appendix A. Cost and metric computation The strategy for computing the 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 uses ETX (Appendix A.1.2) on wireless links, and 2-out-of-3 (Appendix A.1.1) on wired 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 link technologies such as wired links, that are either on or off but on which a packet may occasionally be lost. It was first used in the EGP [EGP] external routing protocol. 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 cost = MAX(rxcost, txcost). A.1.2. ETX The Estimated Transmission Cost metric [ETX] computes the cost by estimating the number of times that a unicast frame will need to be retransmitted using the IEEE 802.11 MAC. A node obeying ETX computes an exponentially decaying average beta of the probability that a Hello message is successfully received. The rxcost is defined as 1/beta. Let alpha be MAX(1, 1/txcost), an estimate of the probability of successfully sending a Hello message. The cost is then computed by Chroboczek Expires October 9, 2009 [Page 29] Internet-Draft The Babel routing protocol April 2009 cost = 1/(alpha * beta) or, equivalently, cost = MAX(txcost, 1) * rxcost. A.2. Metric computation A.2.1. Additive metrics The simplest approach for obtaining a monotonic, isotonic metric is to define the metric as the sum of the links of the component costs. 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. Note that a multiplicative metric can be converted to an additive one by simply 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, or the local node's battery status, CPU load, etc. A simple way of dealing with such external data is to add a value k that depends on the external data to every route's metric. For example, if a node with a low battery receives an update with metric m over a link with cost m', it may use for the resulting route 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. A.3. Cross-layer approaches A lot of thought has been given by a lot of smart people to using link-layer information in order to estimate link quality. Common approaches include: o discarding neighbour relationships when the link is down; o using physical layer information, such as the signal/noise ratio of a wireless link; o using the modulation rate used by the MAC sublayer as input to the link cost computation. At the current time, however, the published results on the effectiveness of such ``cross-layer'' approaches appear to yield contradictory data; hence, their use should be considered as experimental. Chroboczek Expires October 9, 2009 [Page 30] Internet-Draft The Babel routing protocol April 2009 Appendix B. 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 hybrid network, an average of 17 octets is typical. The route table takes about 50 octets per IPv6 entry. To put these values into perspective, a single full-size Ethernet frame can carry some 90 route updates, and a megabyte of memory can contain a 20000- entry routing table. Babel is also a fairly 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. However, in some very constrained environments, such as PDAs, microwave ovens or abacuses, it may be desirable to have subset implementations of the protocol. In order not to prevent convergence of the rest of the network, a simplified implementation of Babel MUST be able to participate in the Acknowledgement protocol and the Hello/ IHU protocol. Additionally, a Babel node that advertises routes other than those that it exports itself MUST be able to evaluate either the feasibility condition, or a stronger condition. Finally, a Babel node MUST be able to reply to seqno requests, and SHOULD be able to reply to route requests. The following sections give two examples of such implementations that do not endanger the integrity of the network. B.1. The simplified feasibility condition The feasibility condition described in Section 2.5.1 requires maintaining a table of sources. The following describes a feasibility condition, DSDV-feasibility [DSDV], that is strictly stronger than the feasibility condition in 2.3.1. An update (id, prefix, seqno', metric') is DSDV-feasible when o either there is no route with source (id, prefix) in the route table; or o there is a route (id, prefix, seqno', metric', nexthop) in the route table, and either * seqno > seqno'; or * seqno = seqno' and metric < metric'. Since there is no table of sources, the correctness of this condition is dependent on the fact that retracted routes are not garbage collected too early. In other words, an implementation that uses DSDV-feasibility MUST keep a route table entry for a route for at least a few minutes after it is retracted. Chroboczek Expires October 9, 2009 [Page 31] Internet-Draft The Babel routing protocol April 2009 B.2. Parasitic implementations 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 stronger than a passive implementation, which does not even advertise routes to itself). A parasitic implementation MUST answer acknowledgement requests and participate in the Hello/IHU protocol. It may either maintain a full routing table, or simply select a default gateway amongst any one of its neighbours that announces a default route. Since a parasitic implementation cannot possibly participate in a routing loop, it need not evaluate the feasibility condition, and can instead consider all routes as feasible. It MUST, however, be able to reply to seqno requests, and SHOULD be able to reply to route requests. Appendix C. Software availability The sample implementation of Babel is available from . Author's Address Juliusz Chroboczek University of Paris 7 175 Rue du Chevaleret 75013 Paris, France Email: jch@pps.jussieu.fr Chroboczek Expires October 9, 2009 [Page 32]