idnits 2.17.1 draft-chroboczek-babel-routing-protocol-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 25, 2010) is 4925 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Chroboczek 3 Internet-Draft PPS, University of Paris 7 4 Intended status: Experimental October 25, 2010 5 Expires: April 28, 2011 7 The Babel Routing Protocol 8 draft-chroboczek-babel-routing-protocol-05 10 Abstract 12 Babel is a mostly loop-free distance vector routing protocol that is 13 robust and efficient both in ordinary wired networks and in wireless 14 mesh networks. 16 Status of this Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on April 28, 2011. 33 Copyright Notice 35 Copyright (c) 2010 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 51 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 53 1.3. Specification of Requirements . . . . . . . . . . . . . . 4 54 2. Conceptual Description of the Protocol . . . . . . . . . . . . 5 55 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . . 5 56 2.2. The Bellman-Ford algorithm . . . . . . . . . . . . . . . . 5 57 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 58 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . . 7 59 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 60 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . . 10 61 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . . 10 62 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . . 11 63 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 12 64 3.1. Message Transmission and Reception . . . . . . . . . . . . 12 65 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12 66 3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . . 15 67 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 15 68 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 17 69 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21 70 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22 71 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24 72 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 28 73 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 28 74 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29 75 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . . 30 76 4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . . 30 77 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 41 78 6. Security Considerations . . . . . . . . . . . . . . . . . . . 42 79 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 43 80 7.1. Normative References . . . . . . . . . . . . . . . . . . . 43 81 7.2. Informative References . . . . . . . . . . . . . . . . . . 43 82 Appendix A. Cost and Metric Computation . . . . . . . . . . . . . 45 83 A.1. Maintaining Hello history . . . . . . . . . . . . . . . . 45 84 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . . 46 85 A.3. Metric computation . . . . . . . . . . . . . . . . . . . . 47 86 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . . 48 87 Appendix C. Simplified Implementations . . . . . . . . . . . . . 49 88 Appendix D. Software Availability . . . . . . . . . . . . . . . . 50 89 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 51 91 1. Introduction 93 Babel is a sequenced distance vector routing protocol, inspired by 94 DSDV [DSDV], that is designed to be robust and efficient both in 95 networks using prefix-based routing and in networks using flat 96 routing (``mesh networks''), and both in relatively stable wired 97 networks and in highly dynamic wireless networks. 99 1.1. Features 101 The main property that makes Babel suitable for unstable networks is 102 that, unlike naive distance-vector routing protocols [RIP], it 103 strongly limits the frequency and duration of routing pathologies 104 such as routing loops and black-holes during reconvergence. Even 105 after a mobility event is detected, a Babel network usually remains 106 loop-free. Babel then quickly reconverges to a configuration that 107 preserves the loop-freedom and connectedness of the network, but is 108 not necessarily optimal; in many cases, this operation requires no 109 packet exchanges at all. Babel then slowly converges, in a time on 110 the scale of minutes, to an optimal configuration. 112 More precisely, Babel has the following properties: 114 o when every prefix is originated by at most one router, Babel never 115 suffers from routing loops; 117 o when a prefix is originated by multiple routers, Babel may 118 occasionally create a transient routing loop for this particular 119 prefix; this loop disappears in a time proportional to its 120 diameter, and never again (up to an arbitrary garbage-collection 121 time) will the routers involved participate in a routing loop for 122 the same prefix; 124 o assuming reasonable packet loss rates, any routing black-holes 125 that may appear after a mobility event are corrected in a time at 126 most proportional to the network's diameter. 128 Babel has provisions for link quality estimation and for fairly 129 arbitrary metrics. When configured suitably, Babel can implement 130 shortest-path routing, or it may use a metric based e.g. on packet 131 loss statistics. 133 Babel nodes will successfully establish an association even when they 134 are configured with different parameters. For example, a mobile node 135 that is low on battery may choose to use larger time constants (hello 136 and update intervals, etc.) than a node that has access to wall 137 power. Conversely, a node that detects high levels of mobility may 138 choose to use smaller time constants. The ability to build such 139 heterogeneous networks makes Babel particularly adapted to the 140 wireless environment. 142 Finally, Babel is a hybrid routing protocol, in the sense that it can 143 carry routes for multiple network-layer protocols (IPv4 and IPv6) 144 whichever protocol the Babel packets are themselves being carried 145 over. 147 1.2. Limitations 149 Babel has two limitations that make it unsuitable for use in some 150 environments. First, Babel relies on periodic routing table updates 151 rather than using a reliable transport; hence, in large, stable 152 networks it generates more traffic than protocols that only send 153 updates when the network topology changes. In such networks, 154 protocols such as OSPF [OSPF], IS-IS [IS-IS] or EIGRP [EIGRP] might 155 be more suitable. 157 Second, Babel does impose a hold time when a prefix is retracted 158 (Section 3.5.5). While this hold time does not apply to the exact 159 prefix being retracted, and hence does not prevent fast reconvergence 160 should it become available again, it does apply to any shorter prefix 161 that covers it. Hence, if a previously deaggregated prefix becomes 162 aggregated, it will be unreachable for a few minutes. This makes 163 Babel unsuitable for use in mobile networks that implement automatic 164 prefix aggregation. 166 1.3. Specification of Requirements 168 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 169 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 170 document are to be interpreted as described in [RFC2119]. 172 2. Conceptual Description of the Protocol 174 Babel is a mostly loop-free distance vector protocol: it is based on 175 the Bellman-Ford protocol, just like the venerable RIP [RIP], but 176 includes a number of refinements that either prevent loop formation 177 altogether, or ensure that a loop disappears in a timely manner and 178 doesn't form again. 180 Conceptually, Bellman-Ford is executed in parallel for every source 181 of routing information (destination of data traffic). In the 182 following discussion, we fix a source S; the reader will recall that 183 the same algorithm is executed for all sources. 185 2.1. Costs, Metrics and Neighbourship 187 As many routing algorithms, Babel computes costs of links between any 188 two neighbouring nodes, abstract values attached to the edges between 189 two nodes. We write C(a, b) for the cost of the edge from node A to 190 node B. 192 Given a route between any two nodes, the metric of the route is the 193 sum of the costs of all the edges along the route. The goal of the 194 routing algorithm is to compute, for every source S, the tree of the 195 routes of lowest metric to S. 197 Costs and metrics need not be integers. In general, they can be 198 values in any algebra that satisfies two fairly general conditions 199 (Section 3.5.2). 201 A Babel node periodically broadcasts Hello packets to all of its 202 neighbours; it also periodically sends an IHU ("I Heard You") packets 203 to every neighbour from which it has recently heard a Hello. From 204 the information derived from Hello and IHU messages received from its 205 neighbour B, a node A computes the cost C(A,B) of the link from A to 206 B. 208 2.2. The Bellman-Ford algorithm 210 Every node A maintains two pieces of data: its estimated distance to 211 S, written D(A), and its next-hop router to S, written NH(A). 212 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 214 Periodically, every node B sends to all of its neighbours a route 215 update, a message containing D(B). When a neighbour A of B receives 216 the route update, it checks whether B is its selected next hop; if 217 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 218 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 219 its current value of D(A). If that value is smaller, meaning that 220 the received update advertises a route that is better than the 221 currently selected route, then NH(A) is set to B, and D(A) is set to 222 C(A, B) + D(B). 224 A number of refinements to this algorithm are possible, and are used 225 by Babel. In particular, convergence speed may be increased by 226 sending unscheduled "triggered updates" whenever a major change in 227 the topology is detected, in addition to the regular, scheduled 228 updates. Additionally, a node may maintain a number of alternate 229 routes, which are being advertised by neighbours other than its 230 selected neighbour, and which can be used immediately if the selected 231 route were to fail. 233 2.3. Transient Loops in Bellman-Ford 235 It is well known that a naive application of Bellman-Ford to 236 distributed routing can cause transient loops after a topology 237 change. Consider for example the following diagram: 239 B 240 1 /| 241 1 / | 242 S --- A |1 243 \ | 244 1 \| 245 C 247 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 249 Suppose now that the link between S and A fails: 251 B 252 1 /| 253 / | 254 S A |1 255 \ | 256 1 \| 257 C 259 When it detects the failure of the link, A switches its next hop to B 260 (which is still advertising a route to S with metric 2), and 261 advertises a metric equal to 3, and then advertises a new route with 262 metric 3. This process of nodes changing selected neighbours and 263 increasing their metric continues until the advertised metric reaches 264 "infinity", a value larger than all the metrics that the routing 265 protocol is able to carry. 267 2.4. Feasibility Conditions 269 Bellman-Ford is a very robust algorithm: its convergence properties 270 are preserved when routers delay route acquisition or when they 271 discard some updates. Babel routers discard received route 272 announcements unless they can prove that accepting them cannot 273 possibly cause a routing loop. 275 More formally, we define a condition over route announcements, known 276 as the feasibility condition, that guarantees the absence of routing 277 loops whenever all routers ignore route updates that do not satisfy 278 the feasibility condition. In effect, this makes Bellman-Ford into a 279 family of routing algorithms, parameterised by the feasibility 280 condition. 282 Many different feasibility conditions are possible. For example, the 283 BGP protocol can be modelled as being a distance-vector protocol with 284 a (rather drastic) feasibility condition: a routing update is only 285 accepted when the receiving node's AS number is not included in the 286 update's AS-Path attribute (note that BGP's feasibility condition 287 does not ensure the absence of transitory "micro-loops" during 288 reconvergence). 290 Another simple feasibility condition, used in DSDV and AODV, stems 291 from the following observation: a routing loop can only arise after a 292 router has switched to a route with a larger metric than the route 293 that it had previously selected. Hence, one could decide that a 294 route is feasible only when its metric at the local node would be no 295 larger than the metric of the currently selected route, i.e. an 296 announcement carrying a metric D(B) is accepted by A when C(A, B) + 297 D(B) <= D(A). If all routers obey this constraint, then the metric 298 at every router is nonincreasing, and the following invariant is 299 always preserved: if A has selected B as its successor, then D(B) < 300 D(A), which implies that the forwarding graph is loop-free. 302 Babel uses a slightly more refined feasibility condition, used in 303 EIGRP [DUAL]. Given a router A, define the feasibility distance of 304 A, written FD(A), as the smallest metric that A has ever advertised 305 for S to any of its neighbours. An update sent by a neighbour B of A 306 is feasible when the metric D(B) advertised by B is strictly smaller 307 than A's feasibility distance, i.e. when D(B) < FD(A). 309 It is easy to see that this latter condition is no more restrictive 310 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 311 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 312 Suppose now that A receives a DSDV-feasible update that advertises a 313 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 314 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 316 To see that it is strictly less restrictive, consider the following 317 diagram, where A has selected the route through B, and D(A) = FD(A) = 318 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 319 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 320 the currently selected route: 322 B 323 1 / \ 1 324 / \ 325 S A 326 \ / 327 1 \ / 4 328 C 330 To show that this feasibility condition still guarantees loop- 331 freeness, recall that at the time when A accepts an update from B, 332 the metric D(B) announced by B is no smaller than FD(B); since it is 333 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 334 property is preserved when A sends updates, it remains true at all 335 times, which ensures that the forwarding graph has no loops. 337 2.5. Solving Starvation: Sequencing Routes 339 Obviously, the feasibility conditions defined above cause starvation 340 when a router runs out of feasible routes. Consider the following 341 diagram, where both A and B have selected the direct route to S: 343 A 344 1 /| D(A) = 1 345 / | FD(A) = 1 346 S |1 347 \ | D(B) = 2 348 2 \| FD(B) = 2 349 B 351 Suppose now that the link between A and S breaks: 353 A 354 | 355 | FD(A) = 1 356 S |1 357 \ | D(B) = 2 358 2 \| FD(B) = 2 359 B 361 The only route available from A to S, the one that goes through B, is 362 not feasible: A suffers from a spurious starvation. 364 At this point, the whole network must be rebooted in order to solve 365 the starvation; this is essentially what EIGRP does, when it performs 366 a global synchronisation of all the routers in the network with the 367 source (the "active" phase of EIGRP). 369 Babel reacts to starvation in a less drastic manner, by using 370 sequenced routes, a technique introduced by DSDV and adopted by AODV. 371 In addition to a metric, every route carries a sequence number, a 372 nondecreasing integer that is propagated unchanged through the 373 network, and is only ever incremented by the source; a pair (s, m), 374 where s is a sequence number and m a metric, is called a distance. 376 A received update is feasible when either it is more recent than the 377 feasibility distance maintained by the receiving node, or it is 378 equally recent and the metric is strictly smaller. More formally, if 379 FD(A) = (s, m), then an update carrying the distance (s', m') is 380 feasible when either s' > s, or s = s' and m' < m. 382 Assuming the sequence number of S is 137, the diagram above becomes: 384 A 385 | 386 | FD(A) = (137, 1) 387 S |1 388 \ | D(B) = (137, 2) 389 2 \| FD(B) = (137, 2) 390 B 392 After S increases its sequence number, and the new sequence number is 393 propagated to B, we have: 395 A 396 | 397 | FD(A) = (137, 1) 398 S |1 399 \ | D(B) = (138, 2) 400 2 \| FD(B) = (138, 2) 401 B 403 at which point the route through B becomes feasible again. 405 Note that while sequence numbers are used for determining 406 feasibility, they are not necessarily used in route selection: a node 407 will normally ignore the sequence number when selecting a route 408 (Section 3.6). 410 2.6. Requests 412 In DSDV, the sequence number of a source is increased periodically. 413 A route becomes feasible again after the source increases its 414 sequence number, and the new sequence number is propagated through 415 the network, which may, in general, require a significant amount of 416 time. 418 Babel takes a different approach. When a node detects that it is 419 suffering from a potentially spurious starvation, it sends an 420 explicit request to the source for a new sequence number. This 421 request is forwarded hop by hop to the source, with no regard to the 422 feasibility condition. Upon receiving the request, the source 423 increases its sequence number, and broadcasts an update, which is 424 forwarded to the requesting node. 426 Note that after a change in network topology not all such requests 427 will, in general, reach the source, as some will be sent over links 428 which are now broken. However, if the network is still connected, 429 then at least one among the nodes suffering from spurious starvation 430 has an (unfeasible) route to the source; hence, in the absence of 431 packet loss, at least one such request will reach the source. 432 (Packet loss is compensated for by resending requests a small number 433 of times.) 435 Since requests are forwarded with no regard to the feasibility 436 condition, they may, in general, be caught in a forwarding loop; this 437 is avoided by having nodes perform duplicate detection for the 438 requests that they forward. 440 2.7. Multiple Routers 442 The above discussion assumes that every prefix is originated by a 443 single router. In real networks, however, it is often necessary to 444 have a single prefix originated by multiple routers; for example, the 445 default route will be originated by all of the edge routers of a 446 routing domain. 448 Since synchronising sequence numbers between distinct routers is 449 problematic, Babel treats routes for the same prefix as distinct 450 entities when they are originated by different routers: every route 451 announcement carries the router-id of its originating router, and 452 feasibility distances are not maintained per-prefix, but per source, 453 where a source is a pair of a router-id and a prefix. In effect, 454 Babel guarantees loop-freedom for the forwarding graph to every 455 source; since the union of multiple acyclic graphs is not in general 456 acyclic, Babel does not in general guarantee loop-freeness when a 457 prefix is originated by multiple routers, but any loops will be 458 broken in a time at most proportional to the diameter of the loop -- 459 as soon as an update has "gone around" the routing loop. 461 Consider for example the following diagram, where A has selected the 462 default route through S, and B has selected the one through S': 464 1 1 1 465 ::/0 -- S --- A --- B --- S' -- ::/0 467 Suppose that both default routes fail at the same time; then nothing 468 prevents A from switching to B, and B simultaneously switching to A. 469 However, as soon as A has successfully advertised the new route to B, 470 the route through A will become unfeasible for B. Conversely, as soon 471 as B will have advertised the route through A, the route through B 472 will become unfeasible for A. 474 In effect, the routing loop disappears at the latest when routing 475 information has gone around the loop. Since this process can be 476 delayed by lost packets, Babel makes certain efforts to ensure that 477 updates are sent reliably after a router-id change. 479 Additionally, after the routers have advertised the two routes, both 480 sources will be in their source tables, which will prevent them from 481 ever again participating in a routing loop involving routes from S 482 and S' (up to the source GC time, which, available memory permitting, 483 can be set to arbitrarily large values). 485 2.8. Overlapping Prefixes 487 In the above discussion, we have assumed that all prefixes are 488 disjoint, as is the case in flat ("mesh") routing. In practice, 489 however, prefixes may overlap: for example, the default route 490 overlaps with all of the routes present in the network. 492 After a route fails, it is not correct in general to switch to a 493 route that subsumes the failed route. Consider for example the 494 following configuration: 496 1 1 497 ::/0 -- A --- B --- C 499 Suppose that node C fails. If B forwards packets destined to C by 500 following the default route, a routing loop will form, and persist 501 until A learns of B's retraction of the direct route to C. Babel 502 avoids this pitfall by maintaining an "unreachable" route for a few 503 minutes after a route is retracted; the time for which such a route 504 must be maintained should be the worst-case propagation time of the 505 retraction for the route to C. 507 3. Protocol Operation 509 Every Babel speaker is assigned a router-id, which is an arbitrary 510 string of 8 octets that is assumed unique across the routing domain. 511 We suggest that router-ids should be assigned in modified EUI-64 512 format [ADDRARCH]. (As a matter of fact, the protocol encoding is 513 slightly more compact when router-ids are assigned in the same manner 514 as the IPv6 layer assigns host ids.) 516 3.1. Message Transmission and Reception 518 Babel protocol packets are sent in the body of a UDP datagram. Each 519 Babel packet consists of one or more TLVs. 521 The source address of a Babel packet is always a unicast address, 522 link-local in the case of IPv6. Babel packets may be sent to a well- 523 known (link-local) multicast address (this is the usual case) or to a 524 (link-local) unicast address. In normal operation, a Babel speaker 525 sends both multicast and unicast packets to its neighbours. 527 With the exception of Hello TLVs and acknowledgements, all Babel TLVs 528 can be sent to either unicast or multicast addresses, and their 529 semantics does not depend on whether the destination was a unicast or 530 multicast address. Hence, a Babel speaker does not need to determine 531 the destination address of a packet that it receives in order to 532 interpret it. 534 A moderate amount of jitter is applied to packets sent by a Babel 535 speaker: outgoing TLVs are buffered, and SHOULD be sent with a small 536 random delay. This is done for two purposes: it avoids 537 synchronisation of multiple Babel speakers across a network [JITTER], 538 and allows for the aggregation of multiple TLVs into a single packet. 540 The exact delay and amount of jitter applied to a packet depends on 541 whether it contains any urgent TLVs. Acknowledgement TLVs MUST be 542 sent before the deadline specified in the corresponding request. The 543 particular class of updates specified in Section 3.7.2 MUST be sent 544 in a timely manner. The particular class of request and update TLVs 545 specified in Section 3.8.2 SHOULD be sent in a timely manner. 547 3.2. Data Structures 549 Every Babel speaker maintains a number of data structures. 551 3.2.1. Sequence Number 553 A node's sequence number is a 16-bit integer that is included in 554 route updates sent for routes originated by this node. A node 555 increments its sequence number (modulo 2^16) whenever it receives a 556 request for a new sequence number (Section 3.8.1.2). 558 A node SHOULD NOT increment its seqno number spontaneously, since 559 increasing seqnos makes it less likely that other nodes will have 560 feasible alternate routes when their selected routes fail. 562 3.2.2. The Interface Table 564 The interface table contains the list of interfaces on which the node 565 speaks the Babel protocol. Every interface table entry contains the 566 interface's Hello seqno, a 16-bit integer that is sent with each 567 Hello TLV on this interface and is incremented (modulo 2^16) whenever 568 a Hello is sent. (Note that an interface's Hello seqno is unrelated 569 to the node's seqno.) 571 There are two timers associated with each interface table entry, the 572 hello timer, which governs the sending of periodic Hello and IHU 573 packets, and the update timer, which governs the sending of periodic 574 route updates. 576 3.2.3. The Neighbour Table 578 The neighbour table contains the list of all neighbouring interfaces 579 from which a Babel packet has been recently received. The neighbour 580 table is indexed by pairs of the form (interface, address), and every 581 neighbour table entry contains the following data: 583 o the local node's interface over which this neighbour is reachable; 585 o the address of the neighbouring interface; 587 o a history of recently received Hello packets from this neighbour; 588 this can, for example, be a sequence of n bits, for some small 589 value n, indicating which of the n hellos most recently sent by 590 this neighbour have been received by the local node; 592 o the ``transmission cost'' value from the last IHU packet received 593 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 594 hold timer for this neighbour has expired; 596 o the neighbour's expected hello sequence number, an integer modulo 597 2^16. 599 There are two timers associated with each neighbour entry, the hello 600 timer, which is initialised from the interval value carried by Hello 601 TLVs, and the IHU timer, which is initialised to a small multiple of 602 the interval carried in IHU TLVs. 604 Note that the neighbour table is indexed by IP addresses, not by 605 router-ids: neighbourship is a relationship between interfaces, not 606 between nodes. Therefore, two nodes with multiple interfaces can 607 participate in multiple neighbourship relationships, a fairly common 608 situation when wireless nodes with multiple radios are involved. 610 3.2.4. The Source Table 612 The source table is used to record feasibility distances. It is 613 indexed by triples of the form (prefix, plen, router-id), and every 614 source table entry contains the following data: 616 o the prefix (prefix, plen) that this entry applies to; 618 o the router-id of a router originating this prefix; 620 o a pair (seqno, metric), this source's feasibility distance. 622 There is one timer associated with each entry in the source table, 623 the source garbage collection timer. It is initialised to a time on 624 the order of minutes, and reset as specified in Section 3.7.3. 626 3.2.5. The Route Table 628 The route table contains the routes known to this node. It is 629 indexed by triples of the form (prefix, plen, neighbour), and every 630 route table entry contains the following data: 632 o the source (prefix, plen, router-id) for which this route is 633 advertised; 635 o the neighbour that advertised this route; 637 o the metric with which this route was advertised by the neighbour, 638 or FFFF hexadecimal (infinity) for a recently retracted route; 640 o the sequence number with which this route was advertised; 642 o the next hop address of this route; 644 o a boolean flag indicating whether this route is selected, i.e. 645 whether it is currently being used for forwarding and is being 646 advertised. 648 There is one timer associated with each route table entry, the route 649 expiry timer. It is initialised and reset as specified in 650 Section 3.5.4. 652 3.2.6. The Table of Pending Requests 654 The table of pending requests contains a list of seqno requests that 655 the local node has sent (either because they have been originated 656 locally, or because they were forwarded) and to which no reply has 657 been received yet. This table is indexed by prefixes, and every 658 entry in this table contains the following data: 660 o the prefix, router-id and seqno being requested; 662 o the neighbour, if any, on behalf of which we are forwarding this 663 request; 665 o a small integer indicating the number of times that this request 666 will be resent if it remains unsatisfied. 668 There is one timer associated with each pending request, which 669 governs both the resending of requests and their expiry. 671 3.3. Acknowledged Packets 673 A Babel speaker may request that any neighbour receiving a given 674 packet reply with an explicit acknowledgement within a given time. 675 While the use of acknowledgement requests is optional, every Babel 676 speaker MUST be able to reply to such a request. 678 An acknowledgement MUST be sent to a unicast destination. On the 679 other hand, acknowledgement requests may be sent to either unicast or 680 multicast destinations, in which case they request an acknowledgement 681 from all of the receiving nodes. 683 When to request acknowledgements is a matter of local policy; the 684 simplest strategy is to never request acknowledgements, and rely on 685 periodic updates to ensure that any reachable routes are eventually 686 propagated throughout the routing domain. For increased efficiency, 687 we suggest that acknowledged packets should be used in order to send 688 urgent updates (Section 3.7.2) when the number of neighbours on a 689 given interface is small. Since Babel is designed to deal gracefully 690 with packet loss on unreliable media, sending all packets with 691 acknowledgement requests is not necessary, and not even recommended, 692 as the acknowledgements cause additional traffic and may force 693 additional ARP or Neighbour Discovery exchanges. 695 3.4. Neighbour Acquisition 697 Neighbour acquisition is the process by which a Babel node discovers 698 the set of neighbours heard over each of its interfaces and 699 ascertains bidirectional reachability. On unreliable media, 700 neighbour acquisition additionally provides some statistics that MAY 701 be used in link quality computation. 703 3.4.1. Reverse Reachability Detection 705 Every Babel node sends periodic Hellos over each of its interfaces. 706 Each Hello TLV carries an increasing (modulo 2^16) sequence number, 707 and the interval between successive periodic packets sent on this 708 particular interface. 710 In addition to the periodic Hello packets, a node MAY send 711 unscheduled Hello packets, e.g. to accelerate link cost estimation 712 when a new neighbour is discovered, or when link conditions have 713 suddenly changed. 715 A node MAY change its Hello interval. The Hello interval MAY be 716 decreased at any time; it SHOULD NOT be increased, except immediately 717 before sending a Hello packet. (Equivalently, a node SHOULD send an 718 unscheduled Hello immediately after increasing its Hello interval.) 720 How to deal with received Hello TLVs, and what statistics to 721 maintain, is considered a local implementation matter; typically, a 722 node will maintain some sort of history of recently received Hellos. 723 A possible algorithm is described in Appendix A.1. 725 After receiving a Hello, or determining that it has missed one, the 726 node recomputes the association's cost (Section 3.4.3) and runs the 727 route selection procedure (Section 3.6). 729 3.4.2. Bidirectional Reachability Detection 731 In order to establish bidirectional reachability, every node sends 732 periodic IHU (``I Heard You'') TLVs to each of its neighbours. Since 733 IHUs carry an explicit interval value, they MAY be sent less often 734 than Hellos in order to reduce the amount of routing traffic in dense 735 networks; in particular, they SHOULD be sent less often than Hellos 736 over links with little packet loss. While IHUs are conceptually 737 unicast, they SHOULD be sent to a multicast address in order to avoid 738 an ARP or Neighbour Discovery exchange, and to aggregate multiple 739 IHUs in a single packet. 741 In addition to the periodic IHUs, a node MAY, at any time, send an 742 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 743 interval, and MAY increase its IHU interval immediately before 744 sending an IHU. 746 Every IHU TLV contains two pieces of data: the link's rxcost from the 747 sender's perspective, used by the neighbour for computing link costs 748 (Section 3.4.3), and the interval between periodic IHU packets. A 749 node receiving an IHU updates the sending neighbour's txcost (from 750 its perspective) value to the value contained in the IHU, and resets 751 this neighbour's IHU timer to a small multiple of the value received 752 in the IHU. 754 When a neighbour's IHU timer expires, its txcost is set to infinity. 756 After updating a neighbour's txcost, the receiving node recomputes 757 the neighbour's cost (Section 3.4.3) and runs the route selection 758 procedure (Section 3.6). 760 3.4.3. Cost Computation 762 A neighbourship association's link cost is computed from the values 763 maintained in the neighbour table, namely the statistics kept in the 764 neighbour table about the reception of Hellos, and the txcost 765 computed from received IHU packets. 767 For every neighbour, a Babel node computes a value known as this 768 neighbour's reception cost, written rxcost. This value is usually 769 derived from the hello history, which may be combined with other 770 data, such as statistics maintained by the link layer. The rxcost is 771 sent to a neighbour in each IHU. 773 How a the txcost and rxcost are combined in order to compute a link's 774 cost is a matter of local policy; as far as Babel's correctness is 775 concerned, only the following conditions MUST be satisfied: 777 o the cost is strictly positive; 779 o if no hellos were received recently, then the cost is infinite; 781 o if the txcost is infinite, then the cost is infinite. 783 Note that while this document does not constrain cost computation any 784 further, not all cost computation strategies will give good results. 785 We give a few examples of strategies for computing a link's cost that 786 are known to work well in practice in Appendix A.2. 788 3.5. Routing Table Maintenance 790 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 791 seqno, metric), where (prefix, plen) is the prefix for which a route 792 is being advertised, router-id is the router-id of the router 793 originating this update, seqno is a non-decreasing (modulo 2^16) 794 integer that carries the originating router seqno, and metric is the 795 announced metric. 797 Before being accepted, an update is checked against the feasibility 798 condition (Section 3.5.1), which ensures that the route does not 799 create a routing loop. If the feasibility condition is not 800 satisfied, the update is either ignored or treated as a retraction, 801 depending on some other conditions (Section 3.5.4). If the 802 feasibility condition is satisfied, then the update cannot possibly 803 cause a routing loop, and the update is accepted. 805 3.5.1. The Feasibility Condition 807 The feasibility condition is applied to all received updates. The 808 feasibility condition compares the metric in the received update with 809 the metrics of the updates previously sent by the receiving node; 810 updates with finite metrics large enough to cause a loop are 811 discarded. 813 A feasibility distance is a pair (seqno, metric), where seqno is an 814 integer modulo 2^16 and metric is a positive integer. Feasibility 815 distances are compared lexicographically, with the first component 816 inverted: we say that a distance (seqno, metric) is strictly better 817 than a distance (seqno', metric'), written 819 (seqno, metric) < (seqno', metric') 821 when 823 seqno > seqno' or (seqno = seqno' and metric < metric') 825 where sequence numbers are compared modulo 2^16. 827 Given a source (p, plen, id), a node's feasibility distance for this 828 source is the minimum, according to the ordering defined above, of 829 the distances of all the finite updates ever sent by this particular 830 node for the prefix (p, plen) carrying the router-id id. Feasibility 831 distances are maintained in the source table; the exact procedure is 832 given in Section 3.7.3. 834 A received update is feasible when either it is a retraction (its 835 metric is FFFF hexadecimal), or the advertised distance is strictly 836 better, in the sense defined above, than the feasibility distance for 837 the corresponding source. More precisely, a route advertisement 838 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 839 feasible if one of the following conditions holds: 841 o metric is infinite; or 843 o no entry exists in the source table indexed by (id, prefix, plen); 844 or 846 o an entry (prefix, plen, router-id, seqno', metric') exists in the 847 source table, and either 849 * seqno' < seqno or 851 * seqno = seqno' and metric < metric'. 853 Note that the feasibility condition considers the metric advertised 854 by the neighbour, not the route's metric; hence, a fluctuation in a 855 neighbour's cost cannot render a selected route unfeasible. 857 3.5.2. Metric Computation 859 A route's metric is computed from the metric advertised by the 860 neighbour and the neighbour's link cost. Just like cost computation, 861 metric computation is considered a local policy matter; as far as 862 Babel is concerned, the function M(c, m) used for computing a metric 863 from a locally computed link cost and the metric advertised by a 864 neighbour MUST only satisfy the following conditions: 866 o if c is infinite, then M(c, m) is infinite; 868 o M is strictly monotonic: M(c, m) > m. 870 Additionally, the metric SHOULD satisfy the following condition: 872 o M is isotonic: if m <= m' then M(c, m) <= M(c, m'). 874 Note that while strict monotonicity is essential to the integrity of 875 the network (persistent routing loops may appear if it is not 876 satisfied), isotonicity is not: if it is not satisfied, Babel will 877 still converge to a locally optimal routing table, but might not 878 reach a global optimum (in fact, such a global optimum may not even 879 exist). 881 As with cost computation, not all strategies for computing route 882 metrics will give good results. In particular, some metrics are more 883 likely than others to lead to routing instabilities (route flapping). 884 We give a number of examples of strictly monotonic, isotonic routing 885 metrics that are known to work well in practice in Appendix A.3. 887 3.5.3. Encoding of Updates 889 In a large network, the bulk of Babel traffic consists of route 890 updates; hence, some care has been given to encoding them 891 efficiently. An Update TLV itself only contains the prefix, seqno 892 and metric, while the next hop is derived either from the network- 893 layer source address of the packet, or from an explicit Next Hop TLV 894 in the same packet. The router-id is derived from a separate 895 Router-Id TLV in the same packet, which optimises the case when 896 multiple updates are sent with the same router-id. 898 Additionally, a prefix of the advertised prefix can be omitted in an 899 Update TLV, in which case it is copied from a previous Update TLV in 900 the same packet -- this is known as address compression [PACKETBB]. 902 Finally, as a special optimisation for the case when a router-id 903 coincides with the interface-id part of an IPv6 address, the 904 router-id can optionally be derived from the low-order bits of the 905 advertised prefix. 907 The encoding of updates is described in detail in Section 4.4. 909 3.5.4. Route Acquisition 911 When a Babel node receives an update (id, prefix, seqno, metric) from 912 a neighbour neigh with a link cost value equal to cost, it checks 913 whether it already has a routing table entry indexed by (neigh, id, 914 prefix). 916 If no such entry exists: 918 o if the update is unfeasible, it is ignored; 920 o if the metric is infinite (the update is a retraction), the update 921 is ignored; 923 o otherwise, a new route table entry is created, indexed by (neigh, 924 id, prefix), with seqno seqno and an advertised metric equal to 925 the metric carried by the update. 927 If such an entry exists: 929 o if the entry is currently installed and the update is unfeasible, 930 then the behaviour depends on whether the router-ids of the two 931 entries match. If the router-ids are different, the update is 932 treated as though it were a retraction (i.e. as though the metric 933 were FFFF hexadecimal). If the router-ids are equal, the update 934 is ignored; 936 o otherwise (i.e. if either the update is feasible or the entry is 937 not currently installed), then the entry's sequence number, 938 advertised metric, metric and router-id are updated and, unless 939 the advertised metric is infinite, the route's expiry timer is 940 reset to a small multiple of the Interval value included in the 941 update. 943 When a route's expiry timer triggers, the behaviour depends on 944 whether the route's metric is finite. If the metric is finite, it is 945 set to infinity and the expiry timer is reset. If the metric is 946 already infinite, the route is flushed from the route table. 948 After the routing table is updated, the route selection procedure 949 (Section 3.6) is run. 951 3.5.5. Hold Time 953 When a prefix p is retracted, because all routes are unfeasible, too 954 old, or have an infinite metric, and a shorter prefix p' that covers 955 p is reachable, p' cannot in general be used for routing packets 956 destined to p without running the risk of creating a routing loop 957 (Section 2.8). 959 To avoid this issue, whenever a prefix is retracted, a routing table 960 entry with infinite metric is maintained as described in 961 Section 3.5.4 above, and packets destined for that prefix MUST NOT be 962 forwarded by following a route for a shorter prefix. The infinite 963 metric entry is maintained until it is superseded by a feasible 964 update; if no such update arrives within the route hold time, the 965 entry is flushed. 967 3.6. Route Selection 969 Route selection is the process by which a single route for a given 970 prefix is selected to be used for forwarding packets and to be 971 readvertised to a node's neighbours. 973 Babel is designed to allow flexible route selection policies. As far 974 as the protocol's correctness is concerned, the route selection 975 policy MUST only satisfy the following properties: 977 o a route with infinite metric (a retracted route) is never 978 selected; 980 o an unfeasible route is never selected. 982 Note, however, that Babel does not naturally guarantee the stability 983 of routing, and configuring conflicting route selection policies on 984 different routers may lead to persistent route oscillation. 986 Defining a good route selection policy for Babel is an open research 987 problem. Route selection can take into account multiple mutually 988 contradictory criteria; in roughly decreasing order of importance, 989 these are: 991 o routes with a small metric should be preferred over routes with a 992 large metric; 994 o switching router-ids should be avoided; 996 o routes through stable neighbours should be preferred over routes 997 through unstable ones; 999 o stable routes should be preferred over unstable ones; 1001 o switching next hops should be avoided. 1003 A simple strategy is to choose the feasible route with the smallest 1004 metric, with a small amount of hysteresis applied to avoid switching 1005 router-ids. 1007 After the route selection procedure is run, triggered updates 1008 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1010 3.7. Sending Updates 1012 A Babel speaker advertises to its neighbours its set of selected 1013 routes. Normally, this is done by sending one or more multicast 1014 packets containing Update TLVs on all of its connected interfaces; 1015 however, on link technologies where multicast is significantly more 1016 expensive than unicast, a node MAY choose to send multiple copies of 1017 updates in unicast packets when the number of neighbours is small. 1019 Additionally, in order to ensure that any black-holes are reliably 1020 cleared in a timely manner, a Babel node sends retractions (updates 1021 with an infinite metric) for any recently retracted prefixes. 1023 If an update is for a route injected into the Babel domain by the 1024 local node (e.g. the address of a local interface, the prefix of a 1025 directly attached network, or redistributed from a different routing 1026 protocol), the router-id is set to the local id, the metric is set to 1027 some arbitrary finite value (typically 0), and the seqno is set to 1028 the local router's sequence number. 1030 If an update is for a route learned from another Babel speaker, the 1031 router-id and sequence number are copied from the routing table 1032 entry, and the metric is computed as specified in Section 3.5.2. 1034 3.7.1. Periodic Updates 1036 Every Babel speaker periodically advertises all of its selected 1037 routes on all of its interfaces, including any recently retracted 1038 routes. Since Babel doesn't suffer from routing loops (there is no 1039 ``counting to infinity'') and relies heavily on triggered updates 1040 (Section 3.7.2), this full dump only needs to happen infrequently. 1042 3.7.2. Triggered Updates 1044 In addition to the periodic routing updates, a Babel speaker sends 1045 unscheduled, or triggered updates in order to inform its neighbours 1046 of a significant change in the network topology. 1048 A change of router-id for the selected route to a given prefix may be 1049 indicative of a routing loop in formation; hence, a node MUST send a 1050 triggered update in a timely manner whenever it changes the selected 1051 router-id for a given destination. Additionally, it SHOULD make a 1052 reasonable attempt at ensuring that all neighbours receive this 1053 update. 1055 There are two strategies for ensuring that. If the number of 1056 neighbours is small, then it is reasonable to send the update 1057 together with an acknowledgement request; the update is resent until 1058 all neighbours have acknowledged the packet, up to some number of 1059 times. If the number of neighbours is large, however, requesting 1060 acknowledgements from all of them might cause a non-negligible amount 1061 of network traffic; in that case, it may be preferable to simply 1062 repeat the update some reasonable number of times (say, 5 for 1063 wireless and 2 for wired links). 1065 A route retraction is somewhat less worrying: if the route retraction 1066 doesn't reach all neighbours, a black-hole might be created, which, 1067 unlike a routing loop, does not endanger the integrity of the 1068 network. When a route is retracted, a node SHOULD send a triggered 1069 update, and SHOULD make a reasonable attempt at ensuring that all 1070 neighbours receive this retraction. 1072 Finally, a node MAY send a triggered update when the metric for a 1073 given prefix changes in a significant manner, either due to a 1074 received update or because a link cost has changed. A node SHOULD 1075 NOT send triggered updates for other reasons, such as when there is a 1076 minor fluctuation in a route's metric, when the selected next hop 1077 changes, or to propagate a new sequence number (except to satisfy a 1078 request, as specified in Section 3.8). 1080 3.7.3. Maintaining Feasibility Distances 1082 Before sending an update (prefix, plen, router-id, seqno, metric) 1083 with finite metric (i.e. not a route retraction), a Babel node 1084 updates the feasibility distance maintained in the source table. 1085 This is done as follows. 1087 If no entry indexed by (prefix, plen, router-id) exists in the source 1088 table, then one is created with value (prefix, plen, router-id, 1089 seqno, metric). 1091 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1092 it is updated as follows: 1094 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1096 o if seqno = seqno' and metric' > metric, then metric' := metric; 1098 o otherwise, nothing needs to be done. 1100 The garbage collection timer for the modified entry is then reset. 1101 Note that the garbage collection timer is not reset when a retraction 1102 is sent. 1104 3.7.4. Split Horizon 1106 When running over a transitive, symmetric link technology, e.g. a 1107 point-to-point link or a wired LAN technology such as Ethernet, a 1108 Babel node SHOULD use an optimisation known as split horizon. When 1109 split horizon is used on a given interface, a routing update is not 1110 sent on this particular interface when the advertised route was 1111 learnt from a neighbour over the same interface. 1113 Split horizon SHOULD NOT be applied to an interface unless the 1114 interface is known to be symmetric and transitive; in particular, 1115 split horizon is not applicable to decentralised wireless link 1116 technologies (e.g. IEEE 802.11 in ad-hoc mode). 1118 3.8. Explicit Route Requests 1120 In normal operation, a node's routing table is populated by the 1121 regular and triggered updates sent by its neighbours. Under some 1122 circumstances, however, a node sends explicit requests to cause a 1123 resynchronisation with the source after a mobility event, and to 1124 prevent a route from spuriously expiring. 1126 The Babel protocol provides two kinds of explicit requests: route 1127 requests, which simply request an update for a given prefix, and 1128 seqno requests, which request an update for a given prefix with a 1129 specific sequence number. The former are never forwarded; the latter 1130 are forwarded if they cannot be satisfied by a neighbour. 1132 3.8.1. Handling Requests 1134 Upon receiving a request, a node either forwards the request or sends 1135 an update in reply to the request, as described in the following 1136 sections. If this causes an update to be sent, the update is either 1137 sent to a multicast address on the interface on which the request was 1138 received, or to the unicast address of the neighbour that sent the 1139 update. 1141 The exact behaviour is different for route requests and seqno 1142 requests. 1144 3.8.1.1. Route Requests 1146 When a node receives a route request for a prefix (prefix, plen), it 1147 checks its route table for a selected route to this exact prefix. If 1148 such a route exists, it MUST send an update; if it is not, it MUST 1149 send a retraction for that prefix. 1151 When a node receives a wildcard route request, it SHOULD send a full 1152 routing table dump. 1154 3.8.1.2. Seqno Requests 1156 When a node receives a seqno request for a given router-id and 1157 sequence number, it checks whether its routing table contains a 1158 selected entry for that prefix; if no such entry exists, or the entry 1159 has infinite metric, it ignores the request. 1161 If a selected route for the given prefix exists, and either the 1162 router-ids are different or the router-ids are equal and the entry's 1163 sequence number is no smaller than the requested sequence number, it 1164 MUST send an update for the given prefix. 1166 If the router-ids match but the requested seqno is larger than the 1167 route entry's, the node compares the router-id against its own 1168 router-id. If the router-id is its own, then it increases its 1169 sequence number by 1 and sends an update. A node MUST NOT increase 1170 its sequence number by more than 1 in response to a route request. 1172 If the requested router-id is not its own, the received request's hop 1173 count is 2 or more, and the node has a route (not necessarily a 1174 feasible one) for the requested prefix that does not use the 1175 requestor as a next-hop, the node SHOULD forward the request. It 1176 does so by decreasing the hop count and sending the request in a 1177 unicast packet destined to a neighbour that advertises the given 1178 prefix (not necessarily the selected neighbour) and that is distinct 1179 from the neighbour from which the request was received. 1181 A node SHOULD maintain a list of recently forwarded requests, and 1182 forward the reply in a timely manner. A node SHOULD compare every 1183 incoming request against its list of recently forwarded requests and 1184 avoid forwarding it if it is redundant. 1186 Since the request forwarding mechanism does not necessarily obey the 1187 feasibility condition, it may get caught into routing loops; hence, 1188 requests carry a hop count to limit the time for which they remain in 1189 the network. However, since requests are only ever forwarded as 1190 unicast packets, the initial hop count need not be kept particularly 1191 low, and performing an expanding horizon search is not necessary. A 1192 request MUST NOT be forwarded to a multicast address, and MUST be 1193 forwarded to a single neighbour only. 1195 3.8.2. Sending Requests 1197 A Babel node MAY send a route or seqno request at any time, to a 1198 multicast or a unicast address; there is only one case when 1199 originating requests is required (Section 3.8.2.1). 1201 3.8.2.1. Avoiding Starvation 1203 When a route is retracted or expires, a Babel node usually switches 1204 to another feasible route for the same prefix. It may be the case, 1205 however, that no such routes are available. 1207 A node that has lost all feasible routes to a given destination MUST 1208 send a seqno request. The router-id of the request is set to the 1209 router-id of the route that it has just lost, and the requested seqno 1210 is the value contained in the source table, plus 1. 1212 Such a request SHOULD be multicast over all of the node's attached 1213 interfaces. Similar requests will be sent by other nodes that are 1214 affected by the route's loss, and will be forwarded by neighbouring 1215 nodes up to the source. If the network is connected, and there is no 1216 packet loss, this will result in a route being advertised with a new 1217 sequence number. (Note that due to duplicate suppression only a 1218 small number of such requests will actually reach the source.) 1220 In order to compensate for packet loss, a node SHOULD repeat such a 1221 request a small number of times if no route becomes feasible within a 1222 short time. Under heavy packet loss, however, all such requests may 1223 be lost; in that case, the second mechanism in the next section will 1224 eventually ensure that a new seqno is received. 1226 3.8.2.2. Dealing with Unfeasible Updates 1228 When a route's metric increases, a node might receive an unfeasible 1229 update for a route that it has currently selected. As specified in 1230 Section 3.5.1, the receiving node will either ignore the update or 1231 retract the route. 1233 In order to keep routes from spuriously expiring because they have 1234 become unfeasible, a node SHOULD send a unicast seqno request 1235 whenever it receives an unfeasible update for a route that is 1236 currently selected. The requested sequence number is computed from 1237 the source table as above. 1239 Additionally, a node SHOULD send a unicast seqno request whenever it 1240 receives an unfeasible update from a currently unselected neighbour 1241 that is "good enough", i.e. that would lead to the received route 1242 becoming selected were it feasible. 1244 3.8.2.3. Preventing Routes From Expiring 1246 In normal operation, a route's expiry timer should never trigger: 1247 since a route's hold time is computed from an explicit interval 1248 included in Update TLVs, a new update should arrive in time to 1249 prevent a route from expiring. 1251 In the presence of packet loss, however, it may be the case that no 1252 update is successfully received for an extended period of time, 1253 causing a route to expire. In order to avoid such spurious expiry, 1254 shortly before a selected route expires, a Babel node SHOULD send a 1255 unicast route request to the neighbour that advertised this route; 1256 since nodes always send retractions in response to non-wildcard route 1257 requests (Section 3.8.1.1), this will usually result in either the 1258 route being refreshed, or a retraction being received. 1260 3.8.2.4. Acquiring new neighbours 1262 In order to speed up convergence after a mobility event, a node MAY 1263 send a unicast wildcard request after acquiring a new neighbour. 1264 Additionally, a node MAY send a small number of multicast wildcard 1265 requests shortly after booting. 1267 4. Protocol Encoding 1269 A Babel packet is sent as the body of a UDP datagram, with network- 1270 layer hop count set to 1, destined to a well-known multicast address 1271 or to a unicast address, over IPv4 or IPv6; in the case of IPv6, 1272 these addresses are link-local. Both the source and destination UDP 1273 port are set to a well-known port number. A Babel packet MUST be 1274 silently ignored unless its source address is either a link-local 1275 IPv6 address, or an IPv4 address belonging to the local network, and 1276 its source port is the well-known Babel port. Babel packets MUST NOT 1277 be sent as IPv6 Jumbograms. 1279 In order to minimise the number of packets being sent while avoiding 1280 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1281 the size of the packets it sends, up to the outgoing interface's MTU 1282 adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets 1283 for UDP/IPv6). It MUST NOT send packets larger than the attached 1284 interface's MTU (adjusted for lower-layer headers) or 512 octets, 1285 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1286 layer headers. Every Babel speaker MUST be able to receive packets 1287 that are as large as any attached interface's MTU (adjusted for 1288 lower-layer headers) or 512 octets, whichever is larger. 1290 In order to avoid global synchronisation of a Babel network and to 1291 aggregate multiple TLVs into large packets, a Babel node MUST buffer 1292 every TLV and delay sending a UDP packet by a small, randomly chosen 1293 delay [JITTER]. In order to allow accurate computation of packet 1294 loss rates, this delay MUST NOT be larger than half the advertised 1295 Hello interval. 1297 4.1. Data Types 1299 4.1.1. Interval 1301 Relative times are carried as 16-bit values specifying a number of 1302 centiseconds (hundredths of a second). This allows times up to 1303 roughly 11 minutes with a granularity of 10ms, which should cover all 1304 reasonable applications of Babel. 1306 4.1.2. Router-Id 1308 A router-id is an arbitrary 8-octet value. Router-ids SHOULD be 1309 assigned in modified EUI-64 format [ADDRARCH]. 1311 4.1.3. Address 1313 Since the bulk of the protocol is taken by addresses, multiple ways 1314 of encoding addresses are defined. Additionally, a common subnet 1315 prefix may be omitted when multiple addresses are sent in a single 1316 packet -- this is known as address compression [PACKETBB]. 1318 Address encodings: 1320 o AE 0: wildcard address. The value is 0 octets long. 1322 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1324 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1326 o AE 3: link-local IPv6 address. The value is 8 octets long, a 1327 prefix of fe80::/64 is implied. 1329 The address family of an address is either IPv4 or IPv6; it is 1330 undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. 1332 4.1.4. Prefixes 1334 A network prefix is encoded just like a network address, but it is 1335 stored in the smallest number of octets that are enough to hold the 1336 significant bits (up to the prefix length). 1338 4.2. Packet Format 1340 A Babel packet consists of a four-octet header, followed by a 1341 sequence of TLVs. 1343 0 1 2 3 1344 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 1345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1346 | Magic | Version | Body length | 1347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1348 | Packet Body ... 1349 +-+-+-+-+-+-+-+-+-+-+-+-+- 1351 Fields : 1353 Magic The arbitrary but carefully chosen value 42 (decimal); 1354 packets with a first octet different from 42 MUST be 1355 silently ignored. 1357 Version This document specifies version 2 of the Babel protocol. 1358 Packets with a second octet different from 2 MUST be 1359 silently ignored. 1361 Body length The length in octets of the body following the packet 1362 header. 1364 Body The packet body, a sequence of TLVs. 1366 Any data following the body MUST be silently ignored. 1368 4.3. TLV Format 1370 With the exception of Pad1, all TLVs have the following structure: 1372 0 1 2 3 1373 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 1374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1375 | Type | Length | Body... 1376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1378 Fields : 1380 Type This field specifies the type of the TLV. 1382 Length The length of the body, exclusive of the Type and Length 1383 fields. If the body is longer than the expected length of 1384 a given type of TLV, any extra data MUST be silently 1385 ignored. 1387 Body This is the TLV body, the interpretation of which depends 1388 on the type. 1390 TLVs with an unknown type value MUST be silently ignored. 1392 4.4. Details of Specific TLVs 1394 4.4.1. Pad1 1396 0 1397 0 1 2 3 4 5 6 7 1398 +-+-+-+-+-+-+-+-+ 1399 | Type = 0 | 1400 +-+-+-+-+-+-+-+-+ 1402 Fields : 1404 Type Set to 0 to indicate a Pad1 TLV. 1406 This TLV is silently ignored on reception. 1408 4.4.2. PadN 1410 0 1 2 3 1411 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 1412 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1413 | Type = 1 | Length | MBZ... 1414 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1416 Fields : 1418 Type Set to 1 to indicate a PadN TLV. 1420 Length The length of the body, exclusive of the Type and Length 1421 fields. 1423 MBZ This field is set to 0 on transmission. 1425 This TLV is silently ignored on reception. 1427 4.4.3. Acknowledgement Request 1429 0 1 2 3 1430 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 1431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1432 | Type = 2 | Length | Reserved | 1433 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1434 | Nonce | Interval | 1435 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1437 This TLV requests that the receiver send an Acknowledgement TLV 1438 within the number of centiseconds specified by the Interval field. 1440 Fields : 1442 Type Set to 2 to indicate an Acknowledgement Request TLV. 1444 Length The length of the body, exclusive of the Type and Length 1445 fields. 1447 Reserved This field is sent as 0, and MUST be ignored on reception. 1449 Nonce This is an arbitrary value which will be echoed in the 1450 receiver's Acknowledgement TLV. 1452 Interval This field expresses a time interval in centiseconds after 1453 which the sender will assume that this packet has been 1454 lost. This MUST NOT be 0. The receiver MUST send an 1455 acknowledgement before this time has elapsed (with a margin 1456 allowing for propagation time). 1458 4.4.4. Acknowledgement 1460 0 1 2 3 1461 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 1462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1463 | Type = 3 | Length | Nonce | 1464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1466 This TLV is sent by a node upon receiving an Acknowledgement Request. 1468 Fields : 1470 Type Set to 3 to indicate an Acknowledgement TLV. 1472 Length The length of the body, exclusive of the Type and Length 1473 fields. 1475 Nonce This is set to the Nonce value of the Acknowledgement 1476 Request that prompted this Acknowledgement. 1478 Since nonce values are not globally unique, this TLV MUST be sent to 1479 a unicast address. 1481 4.4.5. Hello 1483 0 1 2 3 1484 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 1485 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1486 | Type = 4 | Length | Reserved | 1487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1488 | Seqno | Interval | 1489 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1491 This TLV is used for neighbour discovery and for determining a link's 1492 reception cost. 1494 Fields : 1496 Type Set to 4 to indicate a Hello TLV. 1498 Length The length of the body, exclusive of the Type and Length 1499 fields. 1501 Reserved This field is sent as 0, and MUST be ignored on reception. 1503 Seqno The value of the sending node's hello seqno for this 1504 interface. 1506 Interval An upper bound, expressed in centiseconds, on the time 1507 after which the sending node will send a new Hello TLV. 1508 This MUST NOT be 0. 1510 Since there is a single seqno counter for all the hellos sent by a 1511 given node over a given interface, this TLV MUST be sent to a 1512 multicast destination. In order to avoid large discontinuities in 1513 link quality, multiple Hello TLVs SHOULD NOT be sent in the same 1514 packet. 1516 4.4.6. IHU 1518 0 1 2 3 1519 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 1520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1521 | Type = 5 | Length | AE | Reserved | 1522 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1523 | Rxcost | Interval | 1524 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1525 | Address... 1526 +-+-+-+-+-+-+-+-+-+-+-+- 1528 An IHU (``I Heard You'') TLV is used for confirming bidirectional 1529 reachability and carrying a link's transmission cost. 1531 Fields : 1533 Type Set to 5 to indicate an IHU TLV. 1535 Length The length of the body, exclusive of the Type and Length 1536 fields. 1538 AE The encoding of the Address field. This should be 1 or 3 1539 in most cases. As an optimisation, it MAY be 0 if the TLV 1540 is sent to a unicast address, if the association is over a 1541 point-to-point link, or when bidirectional reachability is 1542 ascertained by means outside of the Babel protocol. 1544 Reserved This field is sent as 0, and MUST be ignored on reception. 1546 Rxcost The rxcost according to the sending node of the interface 1547 whose address is specified in the Address field. The value 1548 FFFF hexadecimal (infinity) indicates that this interface 1549 is unreachable. 1551 Interval An upper bound, expressed in centiseconds, on the time 1552 after which the sending node will send a new IHU; this MUST 1553 NOT be 0. The receiving node will use this value in order 1554 to compute a hold time for this symmetric association. 1556 Address The address of the destination node, in the format 1557 specified by the AE field. Address compression is not 1558 allowed. 1560 Conceptually, an IHU is destined to a single neighbour. However, IHU 1561 TLVs contain an explicit destination address, and SHOULD be sent to a 1562 multicast address, as this allows aggregation of IHUs destined to 1563 distinct neighbours into a single packet, and avoids the need for an 1564 ARP or Neighbour Discovery exchange when a neighbour is not being 1565 used for data traffic. 1567 IHU TLVs with an unknown value for the AE field MUST be silently 1568 ignored. 1570 4.4.7. Router-Id 1572 0 1 2 3 1573 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 1574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1575 | Type = 6 | Length | Reserved | 1576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1577 | | 1578 + Router-Id + 1579 | | 1580 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1582 A Router-Id TLV establishes a router-id that is implied by subsequent 1583 Update TLVs. 1585 Fields : 1587 Type Set to 6 to indicate a Router-Id TLV. 1589 Length The length of the body, exclusive of the Type and Length 1590 fields. 1592 Reserved This field is sent as 0, and MUST be ignored on reception. 1594 Router-Id This field contains the router-id for routes advertised in 1595 subsequent Update TLVs 1597 4.4.8. Next Hop 1599 0 1 2 3 1600 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 1601 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1602 | Type = 7 | Length | AE | Reserved | 1603 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1604 | Next hop... 1605 +-+-+-+-+-+-+-+-+-+-+-+- 1607 A Next Hop TLV establishes a next hop address for a given address 1608 family (IPv4 or IPv6) that is implied by subsequent Update TLVs. 1610 Fields : 1612 Type Set to 7 to indicate a Next Hop TLV. 1614 Length The length of the body, exclusive of the Type and Length 1615 fields. 1617 AE The encoding of the Address field. This SHOULD be 1 or 3, 1618 and MUST NOT be 0. 1620 Reserved This field is sent as 0, and MUST be ignored on reception. 1622 Next hop The next hop address advertised by subsequent Update TLV, 1623 for this address family. 1625 When the address family matches the network-layer protocol that this 1626 packet is transported over, a Next Hop TLV is not needed: in that 1627 case, the next hop is taken to be the source address of the packet. 1629 Next Hop TLVs with an unknown value for the AE field MUST be silently 1630 ignored. 1632 4.4.9. Update 1634 0 1 2 3 1635 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 1636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1637 | Type = 8 | Length | AE | Flags | 1638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1639 | Plen | Omitted | Interval | 1640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1641 | Seqno | Metric | 1642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1643 | Prefix... 1644 +-+-+-+-+-+-+-+-+-+-+-+- 1646 An Update TLV advertises or retracts a route. As an optimisation, 1647 this can also have the side effect of establishing a new implied 1648 router-id, and a new default prefix. 1650 Fields : 1652 Type Set to 8 to indicate an Update TLV. 1654 Length The length of the body, exclusive of the Type and Length 1655 fields. 1657 AE The encoding of the Prefix field. 1659 Flags The individual bits of this field specify special handling 1660 of this TLV (see below). Every node MUST be able to 1661 interpret the flags with values 80 and 40 hexadecimal; 1662 unknown flags MUST be silently ignored. 1664 Plen This is the length of the advertised prefix. 1666 Omitted The number of octets that have been omitted at the 1667 beginning of the advertised prefix, and that should be 1668 taken from a preceding Update TLV with the flag with value 1669 80 hexadecimal set. 1671 Interval An upper bound, expressed in centiseconds, on the time 1672 after which the sending node will send a new update for 1673 this prefix. This MUST NOT be 0, and SHOULD NOT be less 1674 than 10. The receiving node will use this value to compute 1675 a hold time for this routing table entry. The value FFFF 1676 hexadecimal (infinity) expresses that this announcement 1677 will not be repeated unless a request is received 1678 (Section 3.8.2.3). 1680 Seqno The originator's sequence number for this update. 1682 Metric The sender's metric for this route. The value FFFF 1683 hexadecimal (infinity) means that this is a route 1684 retraction. 1686 Prefix This field, of size (Plen/8 - Omitted) rounded upwards, 1687 specifies the prefix being advertised. 1689 The Flags field is interpreted as follows: 1691 o if the bit with value 80 hexadecimal is set, then this Update 1692 establishes a new default prefix for subsequent Update TLVs with a 1693 matching address family within the same packet; 1695 o if the bit with value 40 hexadecimal is set, then the low-order 8 1696 octets of the advertised prefix establish a new default router-id 1697 for this TLV and subsequent Update TLVs in the same packet. 1699 The prefix being advertised by an Update TLV is computed as follows: 1701 o the first Omitted octets of the prefix are taken from the previous 1702 Update TLV with flag 80 hexadecimal set and the same address 1703 family; 1705 o the next (Plen/8 - Omitted) (rounded upwards) octets are taken 1706 from the Prefix field; 1708 o the remaining octets are set to 0. 1710 If the Metric field is finite, the router-id of the originating node 1711 for this announcement is taken from the low-order 8 octets of the 1712 prefix advertised by this Update if the bit with value 40 hexadecimal 1713 is set in the Flags field. Otherwise, it is taken either from the 1714 preceding Router-Id packet, or the preceding Update packet with flag 1715 40 hexadecimal set, whichever comes last. 1717 The next hop address for this update is taken from the last preceding 1718 Next Hop TLV with a matching address family in the same packet; if no 1719 such TLV exists, it is taken from the network-layer source address of 1720 this packet. 1722 If the metric field is FFFF hexadecimal, this TLV specifies a 1723 retraction. In that case, the current router-id and the Seqno are 1724 not used. AE MAY then be 0, in which case this Update retracts all 1725 of the routes previously advertised on this interface. 1727 Update TLVs with an unknown value for the AE field MUST be silently 1728 ignored. 1730 4.4.10. Route Request 1732 0 1 2 3 1733 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 1734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1735 | Type = 9 | Length | AE | Plen | 1736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1737 | Prefix... 1738 +-+-+-+-+-+-+-+-+-+-+-+- 1740 A Route Request TLV prompts the receiver to send an update for a 1741 given prefix, or a full routing table dump. 1743 Fields : 1745 Type Set to 9 to indicate a Route Request TLV. 1747 Length The length of the body, exclusive of the Type and Length 1748 fields. 1750 AE The encoding of the Prefix field. The value 0 specifies 1751 that this is a request for a full routing table dump (a 1752 wildcard request). 1754 Plen This is the length of the requested prefix. 1756 Prefix This field, of size Plen/8 rounded upwards, specifies the 1757 prefix being requested. 1759 A Request TLV prompts the receiving node to send an update message 1760 for the prefix specified by the AE, Plen and Prefix fields, or a full 1761 dump of its routing table if AE is 0 (in which case Plen MUST be 0 1762 and Prefix is of length 0). A Request may be sent to a unicast 1763 address if it is destined to a single node, or to a multicast address 1764 if the request is destined to all of the neighbours of the sending 1765 interface. 1767 4.4.11. Seqno Request 1769 0 1 2 3 1770 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 1771 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1772 | Type = 10 | Length | AE | Plen | 1773 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1774 | Seqno | Hop Count | Reserved | 1775 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1776 | | 1777 + Router-Id + 1778 | | 1779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1780 | Prefix... 1781 +-+-+-+-+-+-+-+-+-+-+ 1783 A Seqno Request TLV prompts the receiver to send an Update for a 1784 given prefix with a given sequence number, or to forward the request 1785 further if it cannot be satisfied locally. 1787 Fields : 1789 Type Set to 10 to indicate a Seqno Request message. 1791 Length The length of the body, exclusive of the Type and Length 1792 fields. 1794 AE The encoding of the Prefix field. This MUST NOT be 0. 1796 Plen This is the length of the requested prefix. 1798 Seqno The sequence number that is being requested. 1800 Hop Count The maximum number of times that this TLV may be forwarded, 1801 plus 1. This MUST NOT be 0. 1803 Prefix This field, of size Plen/8 rounded upwards, specifies the 1804 prefix being requested. 1806 A Seqno Request TLV prompts the receiving node to send an Update for 1807 the prefix specified by the AE, Plen and Prefix fields, with either a 1808 router-id different from what is specified by the Router-Id field, or 1809 a Seqno no less than what is specified by the Seqno field. If this 1810 request cannot be satisfied locally, then it is forwarded according 1811 to the rules set out in Section 3.8.1.2. 1813 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 1814 be forwarded to a multicast address, and MUST NOT be forwarded to 1815 more than one neighbour. A request MUST NOT be forwarded if its Hop 1816 Count field is 1. 1818 5. IANA Considerations 1820 IANA has registered the UDP port number TBD, called "babel", for use 1821 by the Babel protocol. 1823 IANA has registered the IPv6 multicast group TBD and the IPv4 1824 multicast group TBD for use by the Babel protocol. 1826 6. Security Considerations 1828 As defined in this document, Babel is a completely insecure protocol. 1829 Any attacker can attract data traffic by advertising routes with a 1830 low metric. This particular issue can be solved either by lower- 1831 layer security mechanisms (e.g. IPSec or link-layer security), or by 1832 appending a cryptographic key to Babel packets; the provision of 1833 ignoring any data contained within a Babel packet beyond the body 1834 length declared by the header is designed for just such a purpose. 1836 The information that a Babel node announces to the whole routing 1837 domain is often sufficient to determine a mobile node's physical 1838 location with reasonable precision. The privacy issues that this 1839 causes can be mitigated somewhat by using randomly chosen router-ids, 1840 randomly chosen IP addresses, and changing them periodically. 1842 When carried over IPv6, Babel packets are ignored unless they are 1843 sent from a link-local IPv6 address; since routers don't forward 1844 link-local IPv6 packets, this provides protection against spoofed 1845 Babel packets being sent from the global Internet. No such natural 1846 protection exists when Babel packets are carried over IPv4. 1848 7. References 1850 7.1. Normative References 1852 [ADDRARCH] 1853 Hinden, R. and S. Deering, "IP Version 6 Addressing 1854 Architecture", RFC 4291, February 2006. 1856 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1857 Requirement Levels", RFC 2119, March 1997. 1859 7.2. Informative References 1861 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 1862 Sequenced Distance-Vector Routing (DSDV) for Mobile 1863 Computers", ACM SIGCOMM'94 Conference on Communications 1864 Architectures, Protocols and Applications 234-244, 1994. 1866 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 1867 Computations", IEEE/ACM Transactions on Networking 1:1, 1868 February 1993. 1870 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 1871 "EIGRP -- a Fast Routing Protocol Based on Distance 1872 Vectors", Proc. Interop 94, 1994. 1874 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 1875 high-throughput path metric for multi-hop wireless 1876 networks", Proc. MobiCom 2003, 2003. 1878 [IS-IS] "Information technology -- Telecommunications and 1879 information exchange between systems -- Intermediate 1880 System to Intermediate System intra-domain routeing 1881 information exchange protocol for use in conjunction with 1882 the protocol for providing the connectionless-mode network 1883 service (ISO 8473)", ISO/IEC 10589:2002. 1885 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 1886 periodic routing messages", IEEE/ACM Trans. Netw. 2, 2, 1887 122-136, April 1994. 1889 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, STD 0054, April 1998. 1891 [PACKETBB] 1892 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 1893 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 1894 Format", RFC 5444, 2009. 1896 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 1898 Appendix A. Cost and Metric Computation 1900 The strategy for computing link costs and route metrics is a local 1901 matter; Babel itself only requires that it comply with the conditions 1902 given in Section 3.4.3 and Section 3.5.2. Different nodes MAY use 1903 different strategies in a single network, and MAY use different 1904 strategies on different interface types. This section gives a few 1905 examples of such strategies. 1907 The sample implementation of Babel maintains statistics about the 1908 last 16 received Hello TLVs (Appendix A.1), computes costs by using 1909 the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX 1910 (Appendix A.2.2) on wireless links. It uses an additive algebra for 1911 metric computation (Appendix A.3.1). 1913 A.1. Maintaining Hello history 1915 For each neighbour, the sample implementation of Babel maintains a 1916 Hello history and an expected sequence number. The Hello history is 1917 a vector of 16 bits, where a 1 value represents a received Hello, and 1918 a 0 value a missed Hello. The expected sequence number, written ne, 1919 is the sequence number that is expected to be carried by the next 1920 received hello from this neighbour. 1922 Whenever it receives a Hello packet from a neighbour, a node compares 1923 the received sequence number nr with its expected sequence number ne. 1924 Depending on the outcome of this comparison, one of the following 1925 actions is taken: 1927 o if the two differ by more than 16 (modulo 2^16), then the sending 1928 node has probably rebooted and lost its sequence number; the 1929 associated neighbour table entry is flushed; 1931 o otherwise, if the received nr is smaller (modulo 2^16) than the 1932 expected sequence number ne, then the sending node has increased 1933 its hello interval without our noticing; the receiving node 1934 removes the last (ne - nr) entries from this neighbour's hello 1935 history (we ``undo history''); 1937 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 1938 node has decreased its hello interval, and some hellos were lost; 1939 the receiving node adds (nr - ne) 0 bits to the hello history (we 1940 ``fast-forward''). 1942 The receiving node then appends a 1 bit to the neighbour's hello 1943 history, resets the neighbour's hello timer, and sets ne to (nr + 1). 1944 It then resets the neighbour's hello timer to 1.5 times the value 1945 advertised in the received Hello (the extra margin allows for the 1946 delay due to jitter). 1948 Whenever the Hello timer associated to a neighbour expires, the local 1949 node adds a 0 bit to this neighbour's hello history, and increments 1950 the expected hello number. If the hello history is empty (it 1951 contains 0 bits only), the neighbour entry is flushed; otherwise, it 1952 resets the neighbour's hello timer to the value advertised in the 1953 last Hello received from this neighbour (no extra margin is necessary 1954 in this case). 1956 A.2. Cost Computation 1958 A.2.1. k-out-of-j 1960 K-out-of-j link sensing is suitable for wired links, that are either 1961 up, in which case they only occasionally drop a packet, or down, in 1962 which case they drop all packets. 1964 The k-out-of-j strategy is parametrised by two small integers k and 1965 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 1966 1. A node keeps a history of the last j hellos; if k or more of 1967 those have been correctly received, the link is assumed to be up, and 1968 the rxcost is set to K; otherwise, the link is assumed to be down, 1969 and the rxcost is set to infinity. 1971 The cost of such a link is defined as 1973 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 1975 o cost = txcost otherwise. 1977 A.2.2. ETX 1979 The Estimated Transmission Cost metric [ETX] estimates the number of 1980 times that a unicast frame will be retransmitted by the IEEE 802.11 1981 MAC, assuming infinite persistence. 1983 A node uses a neighbour's hello history to compute an estimate beta 1984 of the probability that a Hello TLV is successfully received. The 1985 rxcost is defined as 256/beta. 1987 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 1988 successfully sending a Hello TLV. The cost is then computed by 1990 cost = 256/(alpha * beta) 1992 or, equivalently, 1993 cost = (MAX(txcost, 256) * rxcost) / 256. 1995 A.3. Metric computation 1997 A.3.1. Additive Metrics 1999 The simplest approach for obtaining a monotonic, isotonic metric is 2000 to define the metric of a route as the sum of the costs of the 2001 component links. More formally, if a neighbour advertises a route 2002 with metric m over a link with cost c, then the resulting route has 2003 metric M(c, m) = c + m. 2005 A multiplicative metric can be converted to an additive one by taking 2006 the logarithm (in some suitable base) of the link costs. 2008 A.3.2. External Sources of Willingness 2010 A node may want to vary its willingness to forward packets by taking 2011 into account information that is external to the Babel protocol, such 2012 as the monetary cost of a link, the node's battery status, CPU load, 2013 etc. This can be done by adding a value k that depends on the 2014 external data to every route's metric. For example, battery-powered 2015 node receives an update with metric m over a link with cost c, it 2016 might compute a metric M(c, m) = k + c + m, where k depends on the 2017 battery status. 2019 In order to preserve strict monotonicity (Section 3.5.2), the value k 2020 must be greater than -c. 2022 Appendix B. Constants 2024 The choice of time constants is a trade-off between fast detection of 2025 mobility events and protocol overhead. Two implementations of Babel 2026 with different time constants will interoperate, although the 2027 resulting convergence time will most likely be dictated by the 2028 slowest of the two implementations. 2030 Experience with the sample implementation of Babel indicates that the 2031 Hello interval is the most important time constant: a mobility event 2032 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2033 on triggered updates and explicit requests, the Update interval only 2034 has an effect on the time it takes for accurate metrics to be 2035 propagated after variations in link costs too small to trigger an 2036 unscheduled update. 2038 At the time of writing, the sample implementation of Babel uses the 2039 following default values: 2041 Hello Interval: 4 seconds on wireless links, 20 seconds on wired 2042 links. 2044 IHU Interval: the advertised IHU interval is always 3 times the 2045 Hello interval. IHUs are actually sent with each Hello on lossy 2046 links (as determined from the Hello history), but only with every 2047 third Hello on lossless links. 2049 Update Interval: 4 times the Hello interval. 2051 IHU Hold Time: 3.5 times the advertised IHU interval. 2053 Route Expiry Time: 3.5 times the advertised update interval. 2055 Source GC time: 3 minutes. 2057 The amount of jitter applied to a packet depends on whether it 2058 contains any urgent TLVs or not. Urgent triggered updates and urgent 2059 requests are delayed by no more than 200ms; other TLVs are delayed by 2060 no more than one-half the Hello interval. 2062 Appendix C. Simplified Implementations 2064 Babel is a fairly economic protocol. Route updates take between 12 2065 and 40 octets per destination, depending on how successful 2066 compression is; in a double-stack mesh network, an average of less 2067 than 24 octets is typical. The route table occupies about 35 octets 2068 per IPv6 entry. To put these values into perspective, a single full- 2069 size Ethernet frame can carry some 65 route updates, and a megabyte 2070 of memory can contain a 20000-entry routing table and the associated 2071 source table. 2073 Babel is also a reasonably simple protocol. The sample 2074 implementation consists of less than 7000 lines of C code, and 2075 compiles to less than 60 kB of text on a 32-bit CISC architecture. 2077 Nonetheless, in some very constrained environments, such as PDAs, 2078 microwave ovens or abacuses, it may be desirable to have subset 2079 implementations of the protocol. 2081 A parasitic implementation is one that uses a Babel network for 2082 routing its packets but does not announce any of the routes that it 2083 has learnt from its neighbours. (This is slightly more than a 2084 passive implementation, which doesn't even announce routes to 2085 itself.) It may either maintain a full routing table, or simply 2086 select a gateway amongst any one of its neighbours that announces a 2087 default route. Since a parasitic implementation never forwards 2088 packets, it cannot possibly participate in a routing loop; hence, it 2089 need not evaluate the feasibility condition, and need not maintain a 2090 source table. 2092 A parasitic implementation MUST answer acknowledgement requests, and 2093 MUST participate in the Hello/IHU protocol. Finally, it MUST be able 2094 to reply to seqno requests for routes that it announces, and SHOULD 2095 be able to reply to route requests. 2097 Appendix D. Software Availability 2099 The sample implementation of Babel is available from 2100 . 2102 Author's Address 2104 Juliusz Chroboczek 2105 PPS, University of Paris 7 2106 Case 7014 2107 75205 Paris Cedex 13, 2108 France 2110 Email: jch@pps.jussieu.fr