idnits 2.17.1 draft-ietf-babel-rfc6126bis-03.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 : ---------------------------------------------------------------------------- == There are 1 instance of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 1 instance of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to use 'NOT RECOMMENDED' as an RFC 2119 keyword, but does not include the phrase in its RFC 2119 key words list. -- The document date (July 3, 2017) is 2487 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 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 IRIF, University of Paris-Diderot 4 Intended status: Standards Track July 3, 2017 5 Expires: January 4, 2018 7 The Babel Routing Protocol 8 draft-ietf-babel-rfc6126bis-03 10 Abstract 12 Babel is a loop-avoiding 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 January 4, 2018. 33 Copyright Notice 35 Copyright (c) 2017 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 . . . . . . . . . . . . . . . . . . 16 67 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17 68 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 19 69 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24 70 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 24 71 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 27 72 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 30 73 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 31 74 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 32 75 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 33 76 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 33 77 4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 34 78 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 34 79 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 45 80 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46 81 6. Security Considerations . . . . . . . . . . . . . . . . . . . 46 82 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 46 83 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 46 84 8.1. Normative References . . . . . . . . . . . . . . . . . . 46 85 8.2. Informative References . . . . . . . . . . . . . . . . . 47 86 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 47 87 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 48 88 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 49 89 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 50 90 A.4. Properties of Multicast and Unicast Hellos . . . . . . . 51 91 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 51 92 Appendix C. Considerations for protocol extensions . . . . . . . 52 93 Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 53 94 Appendix E. Software Availability . . . . . . . . . . . . . . . 54 95 Appendix F. Changes from previous versions . . . . . . . . . . . 54 96 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 54 97 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 55 98 F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 55 99 F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 55 100 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 56 102 1. Introduction 104 Babel is a loop-avoiding distance-vector routing protocol that is 105 designed to be robust and efficient both in networks using prefix- 106 based routing and in networks using flat routing ("mesh networks"), 107 and both in relatively stable wired networks and in highly dynamic 108 wireless networks. 110 1.1. Features 112 The main property that makes Babel suitable for unstable networks is 113 that, unlike naive distance-vector routing protocols [RIP], it 114 strongly limits the frequency and duration of routing pathologies 115 such as routing loops and black-holes during reconvergence. Even 116 after a mobility event is detected, a Babel network usually remains 117 loop-free. Babel then quickly reconverges to a configuration that 118 preserves the loop-freedom and connectedness of the network, but is 119 not necessarily optimal; in many cases, this operation requires no 120 packet exchanges at all. Babel then slowly converges, in a time on 121 the scale of minutes, to an optimal configuration. This is achieved 122 by using sequenced routes, a technique pioneered by Destination- 123 Sequenced Distance-Vector routing [DSDV]. 125 More precisely, Babel has the following properties: 127 o when every prefix is originated by at most one router, Babel never 128 suffers from routing loops; 130 o when a prefix is originated by multiple routers, Babel may 131 occasionally create a transient routing loop for this particular 132 prefix; this loop disappears in a time proportional to its 133 diameter, and never again (up to an arbitrary garbage-collection 134 (GC) time) will the routers involved participate in a routing loop 135 for the same prefix; 137 o assuming reasonable packet loss rates, any routing black-holes 138 that may appear after a mobility event are corrected in a time at 139 most proportional to the network's diameter. 141 Babel has provisions for link quality estimation and for fairly 142 arbitrary metrics. When configured suitably, Babel can implement 143 shortest-path routing, or it may use a metric based, for example, on 144 measured packet loss. 146 Babel nodes will successfully establish an association even when they 147 are configured with different parameters. For example, a mobile node 148 that is low on battery may choose to use larger time constants (hello 149 and update intervals, etc.) than a node that has access to wall 150 power. Conversely, a node that detects high levels of mobility may 151 choose to use smaller time constants. The ability to build such 152 heterogeneous networks makes Babel particularly adapted to the 153 wireless environment. 155 Finally, Babel is a hybrid routing protocol, in the sense that it can 156 carry routes for multiple network-layer protocols (IPv4 and IPv6), 157 whichever protocol the Babel packets are themselves being carried 158 over. 160 1.2. Limitations 162 Babel has two limitations that make it unsuitable for use in some 163 environments. First, Babel relies on periodic routing table updates 164 rather than using a reliable transport; hence, in large, stable 165 networks it generates more traffic than protocols that only send 166 updates when the network topology changes. In such networks, 167 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 168 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 169 suitable. 171 Second, Babel does impose a hold time when a prefix is retracted 172 (Section 3.5.5). While this hold time does not apply to the exact 173 prefix being retracted, and hence does not prevent fast reconvergence 174 should it become available again, it does apply to any shorter prefix 175 that covers it. Hence, if a previously deaggregated prefix becomes 176 aggregated, it will be unreachable for a few hundred milliseconds up 177 to a few minutes, depending on the implementation. This may make 178 some implementations of Babel unsuitable for use in networks that 179 implement automatic prefix aggregation. 181 1.3. Specification of Requirements 183 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 184 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 185 document are to be interpreted as described in [RFC2119]. 187 2. Conceptual Description of the Protocol 189 Babel is a mostly loop-free distance vector protocol: it is based on 190 the Bellman-Ford protocol, just like the venerable RIP [RIP], but 191 includes a number of refinements that either prevent loop formation 192 altogether, or ensure that a loop disappears in a timely manner and 193 doesn't form again. 195 Conceptually, Bellman-Ford is executed in parallel for every source 196 of routing information (destination of data traffic). In the 197 following discussion, we fix a source S; the reader will recall that 198 the same algorithm is executed for all sources. 200 2.1. Costs, Metrics and Neighbourship 202 As many routing algorithms, Babel computes costs of links between any 203 two neighbouring nodes, abstract values attached to the edges between 204 two nodes. We write C(A, B) for the cost of the edge from node A to 205 node B. 207 Given a route between any two nodes, the metric of the route is the 208 sum of the costs of all the edges along the route. The goal of the 209 routing algorithm is to compute, for every source S, the tree of the 210 routes of lowest metric to S. 212 Costs and metrics need not be integers. In general, they can be 213 values in any algebra that satisfies two fairly general conditions 214 (Section 3.5.2). 216 A Babel node periodically sends Hello messages to all of its 217 neighbours; it also periodically sends an IHU ("I Heard You") message 218 to every neighbour from which it has recently heard a Hello. From 219 the information derived from Hello and IHU messages received from its 220 neighbour B, a node A computes the cost C(A, B) of the link from A to 221 B. 223 2.2. The Bellman-Ford Algorithm 225 Every node A maintains two pieces of data: its estimated distance to 226 S, written D(A), and its next-hop router to S, written NH(A). 227 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 229 Periodically, every node B sends to all of its neighbours a route 230 update, a message containing D(B). When a neighbour A of B receives 231 the route update, it checks whether B is its selected next hop; if 232 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 233 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 234 its current value of D(A). If that value is smaller, meaning that 235 the received update advertises a route that is better than the 236 currently selected route, then NH(A) is set to B, and D(A) is set to 237 C(A, B) + D(B). 239 A number of refinements to this algorithm are possible, and are used 240 by Babel. In particular, convergence speed may be increased by 241 sending unscheduled "triggered updates" whenever a major change in 242 the topology is detected, in addition to the regular, scheduled 243 updates. Additionally, a node may maintain a number of alternate 244 routes, which are being advertised by neighbours other than its 245 selected neighbour, and which can be used immediately if the selected 246 route were to fail. 248 2.3. Transient Loops in Bellman-Ford 250 It is well known that a naive application of Bellman-Ford to 251 distributed routing can cause transient loops after a topology 252 change. Consider for example the following diagram: 254 B 255 1 /| 256 1 / | 257 S --- A |1 258 \ | 259 1 \| 260 C 262 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 264 Suppose now that the link between S and A fails: 266 B 267 1 /| 268 / | 269 S A |1 270 \ | 271 1 \| 272 C 274 When it detects the failure of the link, A switches its next hop to B 275 (which is still advertising a route to S with metric 2), and 276 advertises a metric equal to 3, and then advertises a new route with 277 metric 3. This process of nodes changing selected neighbours and 278 increasing their metric continues until the advertised metric reaches 279 "infinity", a value larger than all the metrics that the routing 280 protocol is able to carry. 282 2.4. Feasibility Conditions 284 Bellman-Ford is a very robust algorithm: its convergence properties 285 are preserved when routers delay route acquisition or when they 286 discard some updates. Babel routers discard received route 287 announcements unless they can prove that accepting them cannot 288 possibly cause a routing loop. 290 More formally, we define a condition over route announcements, known 291 as the feasibility condition, that guarantees the absence of routing 292 loops whenever all routers ignore route updates that do not satisfy 293 the feasibility condition. In effect, this makes Bellman-Ford into a 294 family of routing algorithms, parameterised by the feasibility 295 condition. 297 Many different feasibility conditions are possible. For example, BGP 298 can be modelled as being a distance-vector protocol with a (rather 299 drastic) feasibility condition: a routing update is only accepted 300 when the receiving node's AS number is not included in the update's 301 AS-Path attribute (note that BGP's feasibility condition does not 302 ensure the absence of transitory "micro-loops" during reconvergence). 304 Another simple feasibility condition, used in Destination-Sequenced 305 Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand 306 Distance Vector (AODV) routing, stems from the following observation: 307 a routing loop can only arise after a router has switched to a route 308 with a larger metric than the route that it had previously selected. 309 Hence, one could decide that a route is feasible only when its metric 310 at the local node would be no larger than the metric of the currently 311 selected route, i.e., an announcement carrying a metric D(B) is 312 accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this 313 constraint, then the metric at every router is nonincreasing, and the 314 following invariant is always preserved: if A has selected B as its 315 successor, then D(B) < D(A), which implies that the forwarding graph 316 is loop-free. 318 Babel uses a slightly more refined feasibility condition, used in 319 EIGRP [DUAL]. Given a router A, define the feasibility distance of 320 A, written FD(A), as the smallest metric that A has ever advertised 321 for S to any of its neighbours. An update sent by a neighbour B of A 322 is feasible when the metric D(B) advertised by B is strictly smaller 323 than A's feasibility distance, i.e., when D(B) < FD(A). 325 It is easy to see that this latter condition is no more restrictive 326 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 327 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 328 Suppose now that A receives a DSDV-feasible update that advertises a 329 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 330 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 332 To see that it is strictly less restrictive, consider the following 333 diagram, where A has selected the route through B, and D(A) = FD(A) = 334 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 335 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 336 the currently selected route: 338 B 339 1 / \ 1 340 / \ 341 S A 342 \ / 343 1 \ / 4 344 C 346 To show that this feasibility condition still guarantees loop- 347 freedom, recall that at the time when A accepts an update from B, the 348 metric D(B) announced by B is no smaller than FD(B); since it is 349 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 350 property is preserved when A sends updates, it remains true at all 351 times, which ensures that the forwarding graph has no loops. 353 2.5. Solving Starvation: Sequencing Routes 355 Obviously, the feasibility conditions defined above cause starvation 356 when a router runs out of feasible routes. Consider the following 357 diagram, where both A and B have selected the direct route to S: 359 A 360 1 /| D(A) = 1 361 / | FD(A) = 1 362 S |1 363 \ | D(B) = 2 364 2 \| FD(B) = 2 365 B 367 Suppose now that the link between A and S breaks: 369 A 370 | 371 | FD(A) = 1 372 S |1 373 \ | D(B) = 2 374 2 \| FD(B) = 2 375 B 377 The only route available from A to S, the one that goes through B, is 378 not feasible: A suffers from a spurious starvation. 380 At this point, the whole network must be rebooted in order to solve 381 the starvation; this is essentially what EIGRP does when it performs 382 a global synchronisation of all the routers in the network with the 383 source (the "active" phase of EIGRP). 385 Babel reacts to starvation in a less drastic manner, by using 386 sequenced routes, a technique introduced by DSDV and adopted by AODV. 387 In addition to a metric, every route carries a sequence number, a 388 nondecreasing integer that is propagated unchanged through the 389 network and is only ever incremented by the source; a pair (s, m), 390 where s is a sequence number and m a metric, is called a distance. 392 A received update is feasible when either it is more recent than the 393 feasibility distance maintained by the receiving node, or it is 394 equally recent and the metric is strictly smaller. More formally, if 395 FD(A) = (s, m), then an update carrying the distance (s', m') is 396 feasible when either s' > s, or s = s' and m' < m. 398 Assuming the sequence number of S is 137, the diagram above becomes: 400 A 401 | 402 | FD(A) = (137, 1) 403 S |1 404 \ | D(B) = (137, 2) 405 2 \| FD(B) = (137, 2) 406 B 408 After S increases its sequence number, and the new sequence number is 409 propagated to B, we have: 411 A 412 | 413 | FD(A) = (137, 1) 414 S |1 415 \ | D(B) = (138, 2) 416 2 \| FD(B) = (138, 2) 417 B 419 at which point the route through B becomes feasible again. 421 Note that while sequence numbers are used for determining 422 feasibility, they are not necessarily used in route selection: a node 423 will normally ignore the sequence number when selecting a route 424 (Section 3.6). 426 2.6. Requests 428 In DSDV, the sequence number of a source is increased periodically. 429 A route becomes feasible again after the source increases its 430 sequence number, and the new sequence number is propagated through 431 the network, which may, in general, require a significant amount of 432 time. 434 Babel takes a different approach. When a node detects that it is 435 suffering from a potentially spurious starvation, it sends an 436 explicit request to the source for a new sequence number. This 437 request is forwarded hop by hop to the source, with no regard to the 438 feasibility condition. Upon receiving the request, the source 439 increases its sequence number and broadcasts an update, which is 440 forwarded to the requesting node. 442 Note that after a change in network topology not all such requests 443 will, in general, reach the source, as some will be sent over links 444 that are now broken. However, if the network is still connected, 445 then at least one among the nodes suffering from spurious starvation 446 has an (unfeasible) route to the source; hence, in the absence of 447 packet loss, at least one such request will reach the source. 448 (Resending requests a small number of times compensates for packet 449 loss.) 451 Since requests are forwarded with no regard to the feasibility 452 condition, they may, in general, be caught in a forwarding loop; this 453 is avoided by having nodes perform duplicate detection for the 454 requests that they forward. 456 2.7. Multiple Routers 458 The above discussion assumes that every prefix is originated by a 459 single router. In real networks, however, it is often necessary to 460 have a single prefix originated by multiple routers; for example, the 461 default route will be originated by all of the edge routers of a 462 routing domain. 464 Since synchronising sequence numbers between distinct routers is 465 problematic, Babel treats routes for the same prefix as distinct 466 entities when they are originated by different routers: every route 467 announcement carries the router-id of its originating router, and 468 feasibility distances are not maintained per prefix, but per source, 469 where a source is a pair of a router-id and a prefix. In effect, 470 Babel guarantees loop-freedom for the forwarding graph to every 471 source; since the union of multiple acyclic graphs is not in general 472 acyclic, Babel does not in general guarantee loop-freedom when a 473 prefix is originated by multiple routers, but any loops will be 474 broken in a time at most proportional to the diameter of the loop -- 475 as soon as an update has "gone around" the routing loop. 477 Consider for example the following diagram, where A has selected the 478 default route through S, and B has selected the one through S': 480 1 1 1 481 ::/0 -- S --- A --- B --- S' -- ::/0 483 Suppose that both default routes fail at the same time; then nothing 484 prevents A from switching to B, and B simultaneously switching to A. 485 However, as soon as A has successfully advertised the new route to B, 486 the route through A will become unfeasible for B. Conversely, as 487 soon as B will have advertised the route through A, the route through 488 B will become unfeasible for A. 490 In effect, the routing loop disappears at the latest when routing 491 information has gone around the loop. Since this process can be 492 delayed by lost packets, Babel makes certain efforts to ensure that 493 updates are sent reliably after a router-id change. 495 Additionally, after the routers have advertised the two routes, both 496 sources will be in their source tables, which will prevent them from 497 ever again participating in a routing loop involving routes from S 498 and S' (up to the source GC time, which, available memory permitting, 499 can be set to arbitrarily large values). 501 2.8. Overlapping Prefixes 503 In the above discussion, we have assumed that all prefixes are 504 disjoint, as is the case in flat ("mesh") routing. In practice, 505 however, prefixes may overlap: for example, the default route 506 overlaps with all of the routes present in the network. 508 After a route fails, it is not correct in general to switch to a 509 route that subsumes the failed route. Consider for example the 510 following configuration: 512 1 1 513 ::/0 -- A --- B --- C 515 Suppose that node C fails. If B forwards packets destined to C by 516 following the default route, a routing loop will form, and persist 517 until A learns of B's retraction of the direct route to C. B avoids 518 this pitfall by installing an "unreachable" route after a route is 519 retracted; this route is maintained until it can be guaranteed that 520 the former route has been retracted by all of B's neighbours. 522 3. Protocol Operation 524 Every Babel speaker is assigned a router-id, which is an arbitrary 525 string of 8 octets that is assumed unique across the routing domain. 526 We suggest that router-ids should be assigned in modified EUI-64 527 format [ADDRARCH]. (As a matter of fact, the protocol encoding is 528 slightly more compact when router-ids are assigned in the same manner 529 as the IPv6 layer assigns host IDs.) 531 3.1. Message Transmission and Reception 533 Babel protocol packets are sent in the body of a UDP datagram. Each 534 Babel packet consists of zero or more TLVs. Most TLVs may contain 535 sub-TLVs. 537 The source address of a Babel packet is always a unicast address, 538 link-local in the case of IPv6. Babel packets may be sent to a well- 539 known (link-local) multicast address or to a (link-local) unicast 540 address. In normal operation, a Babel speaker sends both multicast 541 and unicast packets to its neighbours. 543 With the exception of Hello TLVs and acknowledgements, all Babel TLVs 544 can be sent to either unicast or multicast addresses, and their 545 semantics does not depend on whether the destination was a unicast or 546 multicast address. Hence, a Babel speaker does not need to determine 547 the destination address of a packet that it receives in order to 548 interpret it. 550 A moderate amount of jitter may be applied to packets sent by a Babel 551 speaker: outgoing TLVs are buffered and SHOULD be sent with a small 552 random delay. This is done for two purposes: it avoids 553 synchronisation of multiple Babel speakers across a network [JITTER], 554 and it allows for the aggregation of multiple TLVs into a single 555 packet. 557 The exact delay and amount of jitter applied to a packet depends on 558 whether it contains any urgent TLVs. Acknowledgement TLVs MUST be 559 sent before the deadline specified in the corresponding request. The 560 particular class of updates specified in Section 3.7.2 MUST be sent 561 in a timely manner. The particular class of request and update TLVs 562 specified in Section 3.8.2 SHOULD be sent in a timely manner. 564 3.2. Data Structures 566 Every Babel speaker maintains a number of data structures. All of 567 these data structures consist of familiar data types -- integers, IP 568 addresses, etc. -- with the exception of sequence numbers. 570 3.2.1. Sequence number arithmetic 572 Sequence numbers (seqnos) appear in a number of Babel data 573 structures, and they are interpreted as integers modulo 2^16. For 574 the purposes of this document, arithmetic on serial numbers is 575 defined as follows. 577 Given a seqno s and an integer n, the sum of s and n is defined by 579 s + n (modulo 2^16) = (s + n) MOD 2^16 581 or, equivalently, 583 s + n (modulo 2^16) = (s + n) AND 65535 585 where MOD is the modulo operation yielding a non-negative integer and 586 AND is the bitwise conjunction operation. 588 Given two sequence numbers s and s', the relation s is less than s' 589 (s < s') is defined by 591 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 593 or equivalently 595 s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. 597 3.2.2. Node Sequence Number 599 A node's sequence number is a 16-bit integer that is included in 600 route updates sent for routes originated by this node. 602 A node increments its sequence number (modulo 2^16) whenever it 603 receives a request for a new sequence number (Section 3.8.1.2). A 604 node SHOULD NOT increment its sequence number (seqno) spontaneously, 605 since increasing seqnos makes it less likely that other nodes will 606 have feasible alternate routes when their selected routes fail. 608 3.2.3. The Interface Table 610 The interface table contains the list of interfaces on which the node 611 speaks the Babel protocol. Every interface table entry contains the 612 interface's outgoing Multicast Hello seqno, a 16-bit integer that is 613 sent with each Multicast Hello TLV on this interface and is 614 incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note 615 that an interface's Multicast Hello seqno is unrelated to the node's 616 seqno.) 617 There are two timers associated with each interface table entry -- 618 the multicast hello timer, which governs the sending of scheduled 619 Multicast Hello and IHU packets, and the update timer, which governs 620 the sending of periodic route updates. 622 3.2.4. The Neighbour Table 624 The neighbour table contains the list of all neighbouring interfaces 625 from which a Babel packet has been recently received. The neighbour 626 table is indexed by pairs of the form (interface, address), and every 627 neighbour table entry contains the following data: 629 o the local node's interface over which this neighbour is reachable; 631 o the address of the neighbouring interface; 633 o a history of recently received Multicast Hello packets from this 634 neighbour; this can, for example, be a sequence of n bits, for 635 some small value n, indicating which of the n hellos most recently 636 sent by this neighbour have been received by the local node; 638 o a history of recently received Unicast Hello packets from this 639 neighbour; 641 o the "transmission cost" value from the last IHU packet received 642 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 643 hold timer for this neighbour has expired; 645 o the neighbour's expected incoming Multicast Hello sequence number, 646 an integer modulo 2^16. 648 o the neighbour's expected incoming Unicast Hello sequence number, 649 an integer modulo 2^16. 651 o the neighbour's outgoing Unicast Hello sequence number, an integer 652 modulo 2^16 that is sent with each Unicast Hello TLV to this 653 neighbour and is incremented (modulo 2^16) whenever a Unicast 654 Hello is sent. (Note that a neighbour's outgoing Unicast Hello 655 seqno is distinct from the interface's outgoing Multicast Hello 656 seqno.) 658 There are three timers associated with each neighbour entry -- the 659 multicast hello timer, which is initialised from the interval value 660 carried by scheduled Multicast Hello TLVs, the unicast hello timer, 661 which is initialised from the interval value carried by scheduled 662 Unicast Hello TLVs, and the IHU timer, which is initialised to a 663 small multiple of the interval carried in IHU TLVs. 665 Note that the neighbour table is indexed by IP addresses, not by 666 router-ids: neighbourship is a relationship between interfaces, not 667 between nodes. Therefore, two nodes with multiple interfaces can 668 participate in multiple neighbourship relationships, a fairly common 669 situation when wireless nodes with multiple radios are involved. 671 3.2.5. The Source Table 673 The source table is used to record feasibility distances. It is 674 indexed by triples of the form (prefix, plen, router-id), and every 675 source table entry contains the following data: 677 o the prefix (prefix, plen), where plen is the prefix length, that 678 this entry applies to; 680 o the router-id of a router originating this prefix; 682 o a pair (seqno, metric), this source's feasibility distance. 684 There is one timer associated with each entry in the source table -- 685 the source garbage-collection timer. It is initialised to a time on 686 the order of minutes and reset as specified in Section 3.7.3. 688 3.2.6. The Route Table 690 The route table contains the routes known to this node. It is 691 indexed by triples of the form (prefix, plen, neighbour), and every 692 route table entry contains the following data: 694 o the source (prefix, plen, router-id) for which this route is 695 advertised; 697 o the neighbour that advertised this route; 699 o the metric with which this route was advertised by the neighbour, 700 or FFFF hexadecimal (infinity) for a recently retracted route; 702 o the sequence number with which this route was advertised; 704 o the next-hop address of this route; 706 o a boolean flag indicating whether this route is selected, i.e., 707 whether it is currently being used for forwarding and is being 708 advertised. 710 There is one timer associated with each route table entry -- the 711 route expiry timer. It is initialised and reset as specified in 712 Section 3.5.4. 714 Of course, the data structure described above is conceptual: actual 715 implementations will likely use a different data structure, for 716 example a table of installed routes and a set of redundant ones, or 717 some more complicated data structure. 719 Note that there are two distinct (seqno, metric) pairs associated to 720 each route: the route's distance, which is stored in the route table, 721 and the feasibility distance, stored in the source table and shared 722 between all routes with the same source. 724 3.2.7. The Table of Pending Seqno Requests 726 The table of pending seqno requests contains a list of seqno requests 727 that the local node has sent (either because they have been 728 originated locally, or because they were forwarded) and to which no 729 reply has been received yet. This table is indexed by prefixes and 730 router-ids, and every entry in this table contains the following 731 data: 733 o the prefix, router-id, and seqno being requested; 735 o the neighbour, if any, on behalf of which we are forwarding this 736 request; 738 o a small integer indicating the number of times that this request 739 will be resent if it remains unsatisfied. 741 There is one timer associated with each pending seqno request; it 742 governs both the resending of requests and their expiry. 744 3.3. Acknowledged Packets 746 A Babel speaker may request that any neighbour receiving a given 747 packet reply with an explicit acknowledgement within a given time. 748 While the use of acknowledgement requests is optional, every Babel 749 speaker MUST be able to reply to such a request. 751 An acknowledgement MUST be sent to a unicast destination. On the 752 other hand, acknowledgement requests may be sent to either unicast or 753 multicast destinations, in which case they request an acknowledgement 754 from all of the receiving nodes. 756 When to request acknowledgements is a matter of local policy; the 757 simplest strategy is to never request acknowledgements and to rely on 758 periodic updates to ensure that any reachable routes are eventually 759 propagated throughout the routing domain. For increased efficiency, 760 acknowledged packets MAY be used in order to send urgent updates 761 (Section 3.7.2) when the number of neighbours on a given interface is 762 small. Since Babel is designed to deal gracefully with packet loss 763 on unreliable media, sending all packets with acknowledgement 764 requests is not necessary, and NOT RECOMMENDED, as the 765 acknowledgements cause additional traffic and may force additional 766 Address Resolution Protocol (ARP) or Neighbour Discovery exchanges. 768 3.4. Neighbour Acquisition 770 Neighbour acquisition is the process by which a Babel node discovers 771 the set of neighbours heard over each of its interfaces and 772 ascertains bidirectional reachability. On unreliable media, 773 neighbour acquisition additionally provides some statistics that may 774 be useful for link quality computation. 776 Before it can exchange routing information with a neighbour, a Babel 777 node MUST create an entry for that neighbour in the neighbour table. 778 When to do that is implementation-specific; suitable strategies 779 include creating an entry when any Babel packet is received, or 780 creating an entry when a Hello TLV is parsed. Similarly, in order to 781 conserve system resources, an implementation SHOULD discard an entry 782 when it has been unused for long enough; suitable strategies include 783 dropping the neighbour after a timeout, and dropping a neighbour when 784 the associated Hello histories become empty (see Appendix A.2). 786 3.4.1. Reverse Reachability Detection 788 Every Babel node sends Hello TLVs to its neighbours to indicate that 789 it is alive, at regular or irregular intervals. Each Hello TLV 790 carries an increasing (modulo 2^16) sequence number and the time 791 interval until the next Hello of the same type (see below). If the 792 time interval is set to 0, then the Hello TLV does not establish a 793 new promise -- the timeout carried by the previous Hello of the same 794 type still applies to the next Hello. We say that a Hello is 795 scheduled if it has a non-zero interval, and unscheduled otherwise. 797 There are two kinds of Hellos: Multicast Hellos, which use a per- 798 interface Hello counter, and Unicast Hellos, which use a per- 799 neighbour counter. A Multicast Hellos with a given seqno MUST be 800 sent to all neighbours on a given interface, either by sending it to 801 a multicast address or by sending it to one unicast address per 802 neighbour. A Unicast Hello with given seqno should normally be sent 803 to just one neighbour (over unicast), since the sequence numbers of 804 different neighbours are not necessarily synchronised. 806 Multicast Hellos sent over multicast can be used for node discovery; 807 hence, a node SHOULD send periodic (scheduled) Multicast Hellos. A 808 node MAY send Unicast Hellos or unscheduled Hellos of either kind for 809 any reason, such as reducing the amount of multicast traffic or 810 improving reliability on link technologies with poor support for 811 link-layer multicast. 813 A node MAY send a scheduled Hello ahead of time. A node MAY change 814 its scheduled Hello interval. The Hello interval MAY be decreased at 815 any time; it MAY be increased immediately before sending a Hello TLV, 816 but SHOULD NOT be increased at other times. (Equivalently, a node 817 SHOULD send an extra scheduled Hello immediately after increasing its 818 Hello interval.) 820 How to deal with received Hello TLVs and what statistics to maintain 821 are considered local implementation matters; typically, a node will 822 maintain some sort of history of recently received Hellos. A useful 823 algorithm is described in Appendix A.1. 825 After receiving a Hello, or determining that it has missed one, the 826 node recomputes the association's cost (Section 3.4.3) and runs the 827 route selection procedure (Section 3.6). 829 3.4.2. Bidirectional Reachability Detection 831 In order to establish bidirectional reachability, every node sends 832 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 833 IHUs carry an explicit interval value, they MAY be sent less often 834 than Hellos in order to reduce the amount of routing traffic in dense 835 networks; in particular, they SHOULD be sent less often than Hellos 836 over links with little packet loss. While IHUs are conceptually 837 unicast, they MAY be sent to a multicast address in order to avoid an 838 ARP or Neighbour Discovery exchange and to aggregate multiple IHUs in 839 a single packet. 841 In addition to the periodic IHUs, a node MAY, at any time, send an 842 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 843 interval, and it MAY increase its IHU interval immediately before 844 sending an IHU, but SHOULD NOT increase it at any other time. 845 (Equivalently, a node SHOULD send an extra IHU immediately after 846 increasing its Hello interval.) 848 Every IHU TLV contains two pieces of data: the link's rxcost 849 (reception cost) from the sender's perspective, used by the neighbour 850 for computing link costs (Section 3.4.3), and the interval between 851 periodic IHU packets. A node receiving an IHU updates the value of 852 the sending neighbour's txcost (transmission cost), from its 853 perspective, to the value contained in the IHU, and resets this 854 neighbour's IHU timer to a small multiple of the value received in 855 the IHU. 857 When a neighbour's IHU timer expires, its txcost is set to infinity. 859 After updating a neighbour's txcost, the receiving node recomputes 860 the neighbour's cost (Section 3.4.3) and runs the route selection 861 procedure (Section 3.6). 863 3.4.3. Cost Computation 865 A neighbourship association's link cost is computed from the values 866 maintained in the neighbour table -- namely, the statistics kept in 867 the neighbour table about the reception of Hellos, and the txcost 868 computed from received IHU packets. 870 For every neighbour, a Babel node computes a value known as this 871 neighbour's rxcost. This value is usually derived from the Hello 872 history, which may be combined with other data, such as statistics 873 maintained by the link layer. The rxcost is sent to a neighbour in 874 each IHU. 876 How the txcost and rxcost are combined in order to compute a link's 877 cost is a matter of local policy; as far as Babel's correctness is 878 concerned, only the following conditions MUST be satisfied: 880 o the cost is strictly positive; 882 o if no Hello TLVs of either kind were received recently, then the 883 cost is infinite; 885 o if the txcost is infinite, then the cost is infinite. 887 Note that while this document does not constrain cost computation any 888 further, not all cost computation strategies will give good results. 889 See Appendix A.2 for examples of strategies for computing a link's 890 cost that are known to work well in practice. 892 3.5. Routing Table Maintenance 894 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 895 seqno, metric), where (prefix, plen) is the prefix for which a route 896 is being advertised, router-id is the router-id of the router 897 originating this update, seqno is a nondecreasing (modulo 2^16) 898 integer that carries the originating router seqno, and metric is the 899 announced metric. 901 Before being accepted, an update is checked against the feasibility 902 condition (Section 3.5.1), which ensures that the route does not 903 create a routing loop. If the feasibility condition is not 904 satisfied, the update is either ignored or treated as a retraction, 905 depending on some other conditions (Section 3.5.4). If the 906 feasibility condition is satisfied, then the update cannot possibly 907 cause a routing loop, and the update is accepted. 909 3.5.1. The Feasibility Condition 911 The feasibility condition is applied to all received updates. The 912 feasibility condition compares the metric in the received update with 913 the metrics of the updates previously sent by the receiving node; 914 updates that fail the feasibility condition, and therefore have 915 metrics large enough to cause a routing loop, are either discarded or 916 prevent the resulting route from being selected. 918 A feasibility distance is a pair (seqno, metric), where seqno is an 919 integer modulo 2^16 and metric is a positive integer. Feasibility 920 distances are compared lexicographically, with the first component 921 inverted: we say that a distance (seqno, metric) is strictly better 922 than a distance (seqno', metric'), written 924 (seqno, metric) < (seqno', metric') 926 when 928 seqno > seqno' or (seqno = seqno' and metric < metric') 930 where sequence numbers are compared modulo 2^16. 932 Given a source (prefix, plen, router-id), a node's feasibility 933 distance for this source is the minimum, according to the ordering 934 defined above, of the distances of all the finite updates ever sent 935 by this particular node for the prefix (prefix, plen) and the given 936 router-id. Feasibility distances are maintained in the source table; 937 the exact procedure is given in Section 3.7.3. 939 A received update is feasible when either it is a retraction (its 940 metric is FFFF hexadecimal), or the advertised distance is strictly 941 better, in the sense defined above, than the feasibility distance for 942 the corresponding source. More precisely, a route advertisement 943 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 944 feasible if one of the following conditions holds: 946 o metric is infinite; or 948 o no entry exists in the source table indexed by (router-id, prefix, 949 plen); or 951 o an entry (prefix, plen, router-id, seqno', metric') exists in the 952 source table, and either 953 * seqno' < seqno or 955 * seqno = seqno' and metric < metric'. 957 Note that the feasibility condition considers the metric advertised 958 by the neighbour, not the route's metric; hence, a fluctuation in a 959 neighbour's cost cannot render a selected route unfeasible. 961 3.5.2. Metric Computation 963 A route's metric is computed from the metric advertised by the 964 neighbour and the neighbour's link cost. Just like cost computation, 965 metric computation is considered a local policy matter; as far as 966 Babel is concerned, the function M(c, m) used for computing a metric 967 from a locally computed link cost and the metric advertised by a 968 neighbour MUST only satisfy the following conditions: 970 o if c is infinite, then M(c, m) is infinite; 972 o M is strictly monotonic: M(c, m) > m. 974 Additionally, the metric SHOULD satisfy the following condition: 976 o M is isotonic: if m <= m', then M(c, m) <= M(c, m'). 978 Note that while strict monotonicity is essential to the integrity of 979 the network (persistent routing loops may appear if it is not 980 satisfied), isotonicity is not: if it is not satisfied, Babel will 981 still converge to a locally optimal routing table, but might not 982 reach a global optimum (in fact, such a global optimum may not even 983 exist). 985 As with cost computation, not all strategies for computing route 986 metrics will give good results. In particular, some metrics are more 987 likely than others to lead to routing instabilities (route flapping). 988 In Appendix A.3, we give a number of examples of strictly monotonic, 989 isotonic routing metrics that are known to work well in practice. 991 3.5.3. Encoding of Updates 993 In a large network, the bulk of Babel traffic consists of route 994 updates; hence, some care has been given to encoding them 995 efficiently. An Update TLV itself only contains the prefix, seqno, 996 and metric, while the next hop is derived either from the network- 997 layer source address of the packet or from an explicit Next Hop TLV 998 in the same packet. The router-id is derived from a separate Router- 999 Id TLV in the same packet, which optimises the case when multiple 1000 updates are sent with the same router-id. 1002 Additionally, a prefix of the advertised prefix can be omitted in an 1003 Update TLV, in which case it is copied from a previous Update TLV in 1004 the same packet -- this is known as address compression 1005 (Section 4.6.9). 1007 Finally, as a special optimisation for the case when a router-id 1008 coincides with the interface-id part of an IPv6 address, the router- 1009 id can optionally be derived from the low-order bits of the 1010 advertised prefix. 1012 The encoding of updates is described in detail in Section 4.6. 1014 3.5.4. Route Acquisition 1016 When a Babel node receives an update (router-id, prefix, seqno, 1017 metric) from a neighbour neigh with a link cost value equal to cost, 1018 it checks whether it already has a routing table entry indexed by 1019 (neigh, prefix). 1021 If no such entry exists: 1023 o if the update is unfeasible, it MAY be ignored; 1025 o if the metric is infinite (the update is a retraction of a route 1026 we do not know about), the update is ignored; 1028 o otherwise, a new route table entry is created, indexed by (neigh, 1029 prefix), with source equal to (router-id, prefix), seqno equal to 1030 seqno and an advertised metric equal to the metric carried by the 1031 update. 1033 If such an entry exists: 1035 o if the entry is currently selected, the update is unfeasible, and 1036 the router-id of the update is equal to the router-id of the 1037 entry, then the update MAY be silently ignored; 1039 o otherwise, the entry's sequence number, advertised metric, metric, 1040 and router-id are updated and, if the advertised metric is not 1041 infinite, the route's expiry timer is reset to a small multiple of 1042 the Interval value included in the update. If the update is 1043 unfeasible, then the (now unfeasible) entry MUST be immediately 1044 unselected, and, if the update caused the router-id of the entry 1045 to change, an update (possibly a retraction) MUST be sent in a 1046 timely manner (see Section 3.7.2). 1048 Note that the route table may contain unfeasible routes, either 1049 because they were created by an unfeasible update or due to a metric 1050 fluctuation. Such routes are never selected, since they are not 1051 known to be loop-free; should all the feasible routes become 1052 unusable, however, the unfeasible routes can be made feasible by 1053 sending requests along them (see Section 3.8.2). 1055 When a route's expiry timer triggers, the behaviour depends on 1056 whether the route's metric is finite. If the metric is finite, it is 1057 set to infinity and the expiry timer is reset. If the metric is 1058 already infinite, the route is flushed from the route table. 1060 After the routing table is updated, the route selection procedure 1061 (Section 3.6) is run. 1063 3.5.5. Hold Time 1065 When a prefix P is retracted, because all routes are unfeasible or 1066 have an infinite metric (whether due to the expiry timer or to other 1067 reasons), and a shorter prefix P' that covers P is reachable, P' 1068 cannot in general be used for routing packets destined to P without 1069 running the risk of creating a routing loop (Section 2.8). 1071 To avoid this issue, whenever a prefix P is retracted, a routing 1072 table entry with infinite metric is inserted as described in 1073 Section 3.5.4 above. As long as this entry is maintained, packets 1074 destined to an address within P MUST NOT be forwarded by following a 1075 route for a shorter prefix. This entry is removed as soon as a 1076 finite-metric update for prefix P is received and the resulting route 1077 selected. If no such update is forthcoming, the infinite metric 1078 entry MUST be maintained at least until it is guaranteed that no 1079 neighbour has selected the current node as next-hop for prefix P. 1080 This can be achieved by either: 1082 o waiting until the route's expiry timer has expired (Section 3.5.4) 1084 o sending a retraction with an acknowledgement request (Section 3.3) 1085 to every neighbour that has not explicitly retracted prefix P and 1086 waiting for all acknowledgements. 1088 The former option is simpler and ensures that at that point, any 1089 routes for prefix P pointing at the current node have expired. 1090 However, since the expiry time can be as high as a few minutes, doing 1091 that prevents automatic aggregation by creating spurious black-holes 1092 for aggregated routes. The latter option is RECOMMENDED as it 1093 reduces convergence time. 1095 3.6. Route Selection 1097 Route selection is the process by which a single route for a given 1098 prefix is selected to be used for forwarding packets and to be re- 1099 advertised to a node's neighbours. 1101 Babel is designed to allow flexible route selection policies. As far 1102 as the protocol's correctness is concerned, the route selection 1103 policy MUST only satisfy the following properties: 1105 o a route with infinite metric (a retracted route) is never 1106 selected; 1108 o an unfeasible route is never selected. 1110 Note, however, that Babel does not naturally guarantee the stability 1111 of routing, and configuring conflicting route selection policies on 1112 different routers may lead to persistent route oscillation. 1114 Defining a good route selection policy for Babel is an open research 1115 problem. Route selection can take into account multiple mutually 1116 contradictory criteria; in roughly decreasing order of importance, 1117 these are: 1119 o routes with a small metric should be preferred over routes with a 1120 large metric; 1122 o switching router-ids should be avoided; 1124 o routes through stable neighbours should be preferred over routes 1125 through unstable ones; 1127 o stable routes should be preferred over unstable ones; 1129 o switching next hops should be avoided. 1131 A simple strategy is to choose the feasible route with the smallest 1132 metric, with a small amount of hysteresis applied to avoid switching 1133 router-ids. 1135 After the route selection procedure is run, triggered updates 1136 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1138 3.7. Sending Updates 1140 A Babel speaker advertises to its neighbours its set of selected 1141 routes. Normally, this is done by sending one or more multicast 1142 packets containing Update TLVs on all of its connected interfaces; 1143 however, on link technologies where multicast is significantly more 1144 expensive than unicast, a node MAY choose to send multiple copies of 1145 updates in unicast packets when the number of neighbours is small. 1147 Additionally, in order to ensure that any black-holes are reliably 1148 cleared in a timely manner, a Babel node sends retractions (updates 1149 with an infinite metric) for any recently retracted prefixes. 1151 If an update is for a route injected into the Babel domain by the 1152 local node (e.g., the address of a local interface, the prefix of a 1153 directly attached network, or redistributed from a different routing 1154 protocol), the router-id is set to the local id, the metric is set to 1155 some arbitrary finite value (typically 0), and the seqno is set to 1156 the local router's sequence number. 1158 If an update is for a route learned from another Babel speaker, the 1159 router-id and sequence number are copied from the routing table 1160 entry, and the metric is computed as specified in Section 3.5.2. 1162 3.7.1. Periodic Updates 1164 Every Babel speaker periodically advertises all of its selected 1165 routes on all of its interfaces, including any recently retracted 1166 routes. Since Babel doesn't suffer from routing loops (there is no 1167 "counting to infinity") and relies heavily on triggered updates 1168 (Section 3.7.2), this full dump only needs to happen infrequently. 1170 3.7.2. Triggered Updates 1172 In addition to the periodic routing updates, a Babel speaker sends 1173 unscheduled, or triggered, updates in order to inform its neighbours 1174 of a significant change in the network topology. 1176 A change of router-id for the selected route to a given prefix may be 1177 indicative of a routing loop in formation; hence, a node MUST send a 1178 triggered update in a timely manner whenever it changes the selected 1179 router-id for a given destination. Additionally, it SHOULD make a 1180 reasonable attempt at ensuring that all neighbours receive this 1181 update. 1183 There are two strategies for ensuring that. If the number of 1184 neighbours is small, then it is reasonable to send the update 1185 together with an acknowledgement request; the update is resent until 1186 all neighbours have acknowledged the packet, up to some number of 1187 times. If the number of neighbours is large, however, requesting 1188 acknowledgements from all of them might cause a non-negligible amount 1189 of network traffic; in that case, it may be preferable to simply 1190 repeat the update some reasonable number of times (say, 5 for 1191 wireless and 2 for wired links). 1193 A route retraction is somewhat less worrying: if the route retraction 1194 doesn't reach all neighbours, a black-hole might be created, which, 1195 unlike a routing loop, does not endanger the integrity of the 1196 network. When a route is retracted, a node SHOULD send a triggered 1197 update and SHOULD make a reasonable attempt at ensuring that all 1198 neighbours receive this retraction. 1200 Finally, a node MAY send a triggered update when the metric for a 1201 given prefix changes in a significant manner, either due to a 1202 received update or because a link cost has changed. A node SHOULD 1203 NOT send triggered updates for other reasons, such as when there is a 1204 minor fluctuation in a route's metric, when the selected next hop 1205 changes, or to propagate a new sequence number (except to satisfy a 1206 request, as specified in Section 3.8). 1208 3.7.3. Maintaining Feasibility Distances 1210 Before sending an update (prefix, plen, router-id, seqno, metric) 1211 with finite metric (i.e., not a route retraction), a Babel node 1212 updates the feasibility distance maintained in the source table. 1213 This is done as follows. 1215 If no entry indexed by (prefix, plen, router-id) exists in the source 1216 table, then one is created with value (prefix, plen, router-id, 1217 seqno, metric). 1219 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1220 it is updated as follows: 1222 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1224 o if seqno = seqno' and metric' > metric, then metric' := metric; 1226 o otherwise, nothing needs to be done. 1228 The garbage-collection timer for the entry is then reset. Note that 1229 the garbage-collection timer is not reset when a retraction is sent. 1231 When the garbage-collection timer expires, the entry is removed from 1232 the source table. 1234 3.7.4. Split Horizon 1236 When running over a transitive, symmetric link technology, e.g., a 1237 point-to-point link or a wired LAN technology such as Ethernet, a 1238 Babel node SHOULD use an optimisation known as split horizon. When 1239 split horizon is used on a given interface, a routing update is not 1240 sent on this particular interface when the advertised route was 1241 learnt from a neighbour over the same interface. 1243 Split horizon SHOULD NOT be applied to an interface unless the 1244 interface is known to be symmetric and transitive; in particular, 1245 split horizon is not applicable to decentralised wireless link 1246 technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates 1247 are sent over multicast. 1249 3.8. Explicit Route Requests 1251 In normal operation, a node's routing table is populated by the 1252 regular and triggered updates sent by its neighbours. Under some 1253 circumstances, however, a node sends explicit requests to cause a 1254 resynchronisation with the source after a mobility event or to 1255 prevent a route from spuriously expiring. 1257 The Babel protocol provides two kinds of explicit requests: route 1258 requests, which simply request an update for a given prefix, and 1259 seqno requests, which request an update for a given prefix with a 1260 specific sequence number. The former are never forwarded; the latter 1261 are forwarded if they cannot be satisfied by the receiver. 1263 3.8.1. Handling Requests 1265 Upon receiving a request, a node either forwards the request or sends 1266 an update in reply to the request, as described in the following 1267 sections. If this causes an update to be sent, the update is either 1268 sent to a multicast address on the interface on which the request was 1269 received, or to the unicast address of the neighbour that sent the 1270 update. 1272 The exact behaviour is different for route requests and seqno 1273 requests. 1275 3.8.1.1. Route Requests 1277 When a node receives a route request for a prefix (prefix, plen), it 1278 checks its route table for a selected route to this exact prefix. If 1279 such a route exists, it MUST send an update; if such a route does 1280 not, it MUST send a retraction for that prefix. 1282 When a node receives a wildcard route request, it SHOULD send a full 1283 routing table dump. 1285 3.8.1.2. Seqno Requests 1287 When a node receives a seqno request for a given router-id and 1288 sequence number, it checks whether its routing table contains a 1289 selected entry for that prefix. If a selected route for the given 1290 prefix exists, it has finite metric, and either the router-ids are 1291 different or the router-ids are equal and the entry's sequence number 1292 is no smaller than the requested sequence number, the node MUST send 1293 an update for the given prefix. If the router-ids match but the 1294 requested seqno is larger (modulo 2^16) than the route entry's, the 1295 node compares the router-id against its own router-id. If the 1296 router-id is its own, then it increases its sequence number by 1 and 1297 sends an update. A node MUST NOT increase its sequence number by 1298 more than 1 in response to a seqno request. 1300 Otherwise, if the requested router-id is not its own, the received 1301 request's hop count is 2 or more, and the node has a route (not 1302 necessarily a feasible one) for the requested prefix that does not 1303 use the requestor as a next hop, the node MUST forward the request if 1304 it has a feasible route to the requested prefix and it is advertising 1305 this prefix to neighbours, and SHOULD forward the request if it has a 1306 (not necessarily feasible) route to the requested prefix. It does so 1307 by decreasing the hop count and sending the request in a unicast 1308 packet destined to a neighbour that advertises the given prefix and 1309 that is not the neighbour from which the request was received. 1311 A node SHOULD maintain a list of recently forwarded seqno requests 1312 and forward the reply (an update with a sufficiently large seqno) in 1313 a timely manner. A node SHOULD compare every incoming seqno request 1314 against its list of recently forwarded seqno requests and avoid 1315 forwarding it if it is redundant (i.e., if it has recently sent a 1316 request with the same prefix, router-id and a seqno that is not 1317 smaller). 1319 Since the request-forwarding mechanism does not necessarily obey the 1320 feasibility condition, it may get caught in routing loops; hence, 1321 requests carry a hop count to limit the time for which they remain in 1322 the network. However, since requests are only ever forwarded as 1323 unicast packets, the initial hop count need not be kept particularly 1324 low, and performing an expanding horizon search is not necessary. A 1325 single request MUST NOT be duplicated: it MUST NOT be forwarded to a 1326 multicast address, and it MUST NOT be forwarded to multiple 1327 neighbours. However, if a seqno request is resent, the subsequent 1328 copies MAY be sent to a different neighbour than the initial one. If 1329 the route corresponding to a seqno request is unselected between 1330 retransmissions, the node SHOULD stop retransmitting requests for it. 1332 3.8.2. Sending Requests 1334 A Babel node MAY send a route or seqno request at any time, to a 1335 multicast or a unicast address; there is only one case when 1336 originating requests is required (Section 3.8.2.1). 1338 3.8.2.1. Avoiding Starvation 1340 When a route is retracted or expires, a Babel node usually switches 1341 to another feasible route for the same prefix. It may be the case, 1342 however, that no such routes are available. 1344 A node that has lost all feasible routes to a given destination but 1345 still has unexpired unfeasible routes to that destination, MUST send 1346 a seqno request; if it doesn't have any such routes, it MAY still 1347 send a seqno request. The router-id of the request is set to the 1348 router-id of the route that it has just lost, and the requested seqno 1349 is the value contained in the source table, plus 1. 1351 If the node has any (unfeasible) routes to the requested destination, 1352 then it MUST send the request to at least one of the next-hop 1353 neighbours that advertised these routes, and SHOULD send it to all of 1354 them; in any case, it MAY send the request to any other neighbours, 1355 whether they advertise a route to the requested destination or not. 1356 A simple implementation strategy is therefore to unconditionally 1357 multicast the request over all attached interfaces. 1359 Similar requests will be sent by other nodes that are affected by the 1360 route's loss. If the network is still connected, and assuming no 1361 packet loss, then at least one of these requests will be forwarded to 1362 the source, resulting in a route being advertised with a new sequence 1363 number. (Note that, due to duplicate suppression, only a small 1364 number of such requests will actually reach the source.) 1366 In order to compensate for packet loss, a node SHOULD repeat such a 1367 request a small number of times if no route becomes feasible within a 1368 short time. Under heavy packet loss, however, all such requests 1369 might be lost; in that case, the second mechanism in the next section 1370 will eventually ensure that a new seqno is received. 1372 3.8.2.2. Dealing with Unfeasible Updates 1374 When a route's metric increases, a node might receive an unfeasible 1375 update for a route that it has currently selected. As specified in 1376 Section 3.5.1, the receiving node will either ignore the update or 1377 retract the route. 1379 In order to keep routes from spuriously expiring because they have 1380 become unfeasible, a node SHOULD send a unicast seqno request 1381 whenever it receives an unfeasible update for a route that is 1382 currently selected. The requested sequence number is computed from 1383 the source table as above. 1385 Additionally, since metric computation does not necessarily coincide 1386 with the delay in propagating updates, a node might receive an 1387 unfeasible update from a currently unselected neighbour that is 1388 preferable to the currently selected route (e.g., because it has a 1389 much smaller metric); in that case, the node SHOULD send a unicast 1390 seqno request to the neighbour that advertised the preferable update. 1392 3.8.2.3. Preventing Routes from Expiring 1394 In normal operation, a route's expiry timer should never trigger: 1395 since a route's hold time is computed from an explicit interval 1396 included in Update TLVs, a new update (possibly a retraction) should 1397 arrive in time to prevent a route from expiring. 1399 In the presence of packet loss, however, it may be the case that no 1400 update is successfully received for an extended period of time, 1401 causing a route to expire. In order to avoid such spurious expiry, 1402 shortly before a selected route expires, a Babel node SHOULD send a 1403 unicast route request to the neighbour that advertised this route; 1404 since nodes always send retractions in response to non-wildcard route 1405 requests (Section 3.8.1.1), this will usually result in either the 1406 route being refreshed or a retraction being received. 1408 3.8.2.4. Acquiring New Neighbours 1410 In order to speed up convergence after a mobility event, a node MAY 1411 send a unicast wildcard request after acquiring a new neighbour. 1412 Additionally, a node MAY send a small number of multicast wildcard 1413 requests shortly after booting. Note that doing that carelessly can 1414 cause serious congestion when a whole network is rebooted, especially 1415 on link layers with high per-packet overhead (e.g., IEEE 802.11). 1417 4. Protocol Encoding 1419 A Babel packet is sent as the body of a UDP datagram, with network- 1420 layer hop count set to 1, destined to a well-known multicast address 1421 or to a unicast address, over IPv4 or IPv6; in the case of IPv6, 1422 these addresses are link-local. Both the source and destination UDP 1423 port are set to a well-known port number. A Babel packet MUST be 1424 silently ignored unless its source address is either a link-local 1425 IPv6 address, or an IPv4 address belonging to the local network, and 1426 its source port is the well-known Babel port. Babel packets MUST NOT 1427 be sent as IPv6 Jumbograms. 1429 In order to minimise the number of packets being sent while avoiding 1430 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1431 the size of the packets it sends, up to the outgoing interface's MTU 1432 adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets 1433 for UDP/IPv6). It MUST NOT send packets larger than the attached 1434 interface's MTU (adjusted for lower-layer headers) or 512 octets, 1435 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1436 layer headers. Every Babel speaker MUST be able to receive packets 1437 that are as large as any attached interface's MTU (adjusted for 1438 lower-layer headers) or 512 octets, whichever is larger. 1440 In order to avoid global synchronisation of a Babel network and to 1441 aggregate multiple TLVs into large packets, a Babel node MUST buffer 1442 every TLV and delay sending a UDP packet by a small, randomly chosen 1443 delay [JITTER]. In order to allow accurate computation of packet 1444 loss rates, this delay MUST NOT be larger than half the advertised 1445 Hello interval. 1447 4.1. Data Types 1449 4.1.1. Interval 1451 Relative times are carried as 16-bit values specifying a number of 1452 centiseconds (hundredths of a second). This allows times up to 1453 roughly 11 minutes with a granularity of 10ms, which should cover all 1454 reasonable applications of Babel. 1456 4.1.2. Router-Id 1458 A router-id is an arbitrary 8-octet value. A router-id MUST NOT 1459 consist of either all zeroes or all ones. Router-ids SHOULD be 1460 assigned in modified EUI-64 format [ADDRARCH]. 1462 4.1.3. Address 1464 Since the bulk of the protocol is taken by addresses, multiple ways 1465 of encoding addresses are defined. Additionally, a common subnet 1466 prefix may be omitted when multiple addresses are sent in a single 1467 packet -- this is known as address compression (Section 4.6.9). 1469 Address encodings: 1471 o AE 0: wildcard address. The value is 0 octets long. 1473 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1475 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1477 o AE 3: link-local IPv6 address. Compression is not allowed. The 1478 value is 8 octets long, a prefix of fe80::/64 is implied. 1480 The address family of an address is either IPv4 or IPv6; it is 1481 undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. 1483 4.1.4. Prefixes 1485 A network prefix is encoded just like a network address, but it is 1486 stored in the smallest number of octets that are enough to hold the 1487 significant bits (up to the prefix length). 1489 4.2. Packet Format 1491 A Babel packet consists of a 4-octet header, followed by a sequence 1492 of TLVs. 1494 0 1 2 3 1495 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 1496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1497 | Magic | Version | Body length | 1498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1499 | Packet Body ... 1500 +-+-+-+-+-+-+-+-+-+-+-+-+- 1502 Fields : 1504 Magic The arbitrary but carefully chosen value 42 (decimal); 1505 packets with a first octet different from 42 MUST be 1506 silently ignored. 1508 Version This document specifies version 2 of the Babel protocol. 1509 Packets with a second octet different from 2 MUST be 1510 silently ignored. 1512 Body length The length in octets of the body following the packet 1513 header. 1515 Body The packet body; a sequence of TLVs. 1517 Any data following the body MUST be silently ignored. 1519 4.3. TLV Format 1521 With the exception of Pad1, all TLVs have the following structure: 1523 0 1 2 3 1524 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 1525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1526 | Type | Length | Payload... 1527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1529 Fields : 1531 Type The type of the TLV. 1533 Length The length of the body, exclusive of the Type and Length 1534 fields. If the body is longer than the expected length of 1535 a given type of TLV, any extra data MUST be silently 1536 ignored. 1538 Payload The TLV payload, which consists of a body and, for selected 1539 TLV types, an optional list of sub-TLVs. 1541 TLVs with an unknown type value MUST be silently ignored. 1543 4.4. Sub-TLV Format 1545 Every TLV carries an explicit length in its header; however, most 1546 TLVs are self-terminating, in the sense that it is possible to 1547 determine the length of the body without reference to the explicit 1548 TLV length. If a TLV has a self-terminating format, then it MAY 1549 allow a sequence of sub-TLVs to follow the body. 1551 Sub-TLVs have the same structure as TLVs. With the exception of 1552 PAD1, all TLVs have the following structure: 1554 0 1 2 3 1555 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 1556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1557 | Type | Length | Body... 1558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1560 Fields : 1562 Type The type of the sub-TLV. 1564 Length The length of the body, in octets, exclusive of the Type 1565 and Length fields. 1567 Body The sub-TLV body, the interpretation of which depends on 1568 both the type of the sub-TLV and the type of the TLV within 1569 which it is embedded. 1571 The most-significant bit of the sub-TLV, called the mandatory bit, 1572 indicates how to handle unknown sub-TLVs. If the mandatory bit is 1573 not set, then an unknown sub-TLV MUST be silently ignored, and the 1574 rest of the TLV processed normally. If the mandatory bit is set, 1575 then the whole enclosing TLV MUST be silently ignored (except for 1576 updating the parser state by a Router-ID, Next-Hop or Update TLV, see 1577 Section 4.6.7, Section 4.6.8, and Section 4.6.9). 1579 4.5. Parser state 1581 Babel uses a stateful parser: a TLV may refer to data from a previous 1582 TLV. Babel's parser state consists of the following pieces of data: 1584 o for each address encoding that allows compression, the current 1585 default prefix; this is undefined at the start of the packet, and 1586 is updated by an Update TLV with the PREFIX flag set 1587 (Section 4.6.9); 1589 o for each address family (IPv4 or IPv6), the current next-hop; this 1590 is the source address of the enclosing packet for the matching 1591 address family at the start of a packet, and is updated by the 1592 Next-Hop TLV (Section 4.6.8); 1594 o the current router-id; this is undefined at the start of the 1595 packet, and is updated by both the Router-ID TLV (Section 4.6.7) 1596 and the Update TLV with ROUTER-ID flag set. 1598 Since the parser state is separate from the bulk of Babel's state, 1599 and for correct parsing must be identical across implementations, it 1600 is updated before checking for mandatory TLVs: parsing a TLV updates 1601 the parser state even if the TLV is otherwise ignored due to an 1602 unknown mandatory sub-TLV. 1604 4.6. Details of Specific TLVs 1606 4.6.1. Pad1 1608 0 1609 0 1 2 3 4 5 6 7 1610 +-+-+-+-+-+-+-+-+ 1611 | Type = 0 | 1612 +-+-+-+-+-+-+-+-+ 1614 Fields : 1616 Type Set to 0 to indicate a Pad1 TLV. 1618 This TLV is silently ignored on reception. 1620 4.6.2. PadN 1622 0 1 2 3 1623 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 1624 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1625 | Type = 1 | Length | MBZ... 1626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1628 Fields : 1630 Type Set to 1 to indicate a PadN TLV. 1632 Length The length of the body, exclusive of the Type and Length 1633 fields. 1635 MBZ Set to 0 on transmission. 1637 This TLV is silently ignored on reception. 1639 4.6.3. Acknowledgement Request 1641 0 1 2 3 1642 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 1643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1644 | Type = 2 | Length | Reserved | 1645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1646 | Nonce | Interval | 1647 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1649 This TLV requests that the receiver send an Acknowledgement TLV 1650 within the number of centiseconds specified by the Interval field. 1652 Fields : 1654 Type Set to 2 to indicate an Acknowledgement Request TLV. 1656 Length The length of the body, exclusive of the Type and Length 1657 fields. 1659 Reserved Sent as 0 and MUST be ignored on reception. 1661 Nonce An arbitrary value that will be echoed in the receiver's 1662 Acknowledgement TLV. 1664 Interval A time interval in centiseconds after which the sender will 1665 assume that this packet has been lost. This MUST NOT be 0. 1666 The receiver MUST send an acknowledgement before this time 1667 has elapsed (with a margin allowing for propagation time). 1669 This TLV is self-terminating, and allows sub-TLVs. 1671 4.6.4. Acknowledgement 1673 0 1 2 3 1674 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 1675 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1676 | Type = 3 | Length | Nonce | 1677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1679 This TLV is sent by a node upon receiving an Acknowledgement Request. 1681 Fields : 1683 Type Set to 3 to indicate an Acknowledgement TLV. 1685 Length The length of the body, exclusive of the Type and Length 1686 fields. 1688 Nonce Set to the Nonce value of the Acknowledgement Request that 1689 prompted this Acknowledgement. 1691 Since nonce values are not globally unique, this TLV MUST be sent to 1692 a unicast address. 1694 This TLV is self-terminating, and allows sub-TLVs. 1696 4.6.5. Hello 1698 0 1 2 3 1699 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 1700 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1701 | Type = 4 | Length | Flags | 1702 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1703 | Seqno | Interval | 1704 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1706 This TLV is used for neighbour discovery and for determining a 1707 neighbour's reception cost. 1709 Fields : 1711 Type Set to 4 to indicate a Hello TLV. 1713 Length The length of the body, exclusive of the Type and Length 1714 fields. 1716 Flags The individual bits of this field specify special handling 1717 of this TLV (see below). 1719 Seqno If the UNICAST flag is set, this is the value of the 1720 sending node's outgoing Unicast Hello seqno for this 1721 neighbour. Otherwise, it is the sending node's outgoing 1722 Multicast Hello seqno for this interface. 1724 Interval If non-zero, this is an upper bound, expressed in 1725 centiseconds, on the time after which the sending node will 1726 send a new scheduled Hello TLV with the same setting of the 1727 UNICAST flag. If this is 0, then this Hello represents an 1728 unscheduled Hello, and doesn't carry any new information 1729 about times at which Hellos are sent. 1731 The Flags field is interpreted as follows: 1733 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1734 |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| 1735 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1737 In the description below, a bit being 'set' means its value is '1', 1738 while 'cleared' means its value is '0'. 'X' bits MUST be cleared 1739 when sending and MUST be ignored on receipt. Every node MUST be able 1740 to interpret the UNICAST flag. 1742 o U (UNICAST) flag (8000 hexadecimal): if set, then this Hello 1743 represents a Unicast Hello, otherwise it represents a Multicast 1744 Hello. 1746 Every time a Hello is sent, the corresponding seqno counter MUST be 1747 incremented. Since there is a single seqno counter for all the 1748 Multicast Hellos sent by a given node over a given interface, if the 1749 UNICAST flag is not set, this TLV MUST be sent to all neighbors on 1750 this link, which can be achieved by sending to a multicast 1751 destination, or repeatedly sending unicast to all known neighbours. 1752 Similarly, if the UNICAST flag is set, this TLV MUST be sent to a 1753 single neighbour, which can achieved by sending to a unicast 1754 destination. In order to avoid large discontinuities in link 1755 quality, multiple Hello TLVs SHOULD NOT be sent in the same packet. 1757 This TLV is self-terminating, and allows sub-TLVs. 1759 4.6.6. IHU 1761 0 1 2 3 1762 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 1763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1764 | Type = 5 | Length | AE | Reserved | 1765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1766 | Rxcost | Interval | 1767 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1768 | Address... 1769 +-+-+-+-+-+-+-+-+-+-+-+- 1771 An IHU ("I Heard You") TLV is used for confirming bidirectional 1772 reachability and carrying a link's transmission cost. 1774 Fields : 1776 Type Set to 5 to indicate an IHU TLV. 1778 Length The length of the body, exclusive of the Type and Length 1779 fields. 1781 AE The encoding of the Address field. This should be 1 or 3 1782 in most cases. As an optimisation, it MAY be 0 if the TLV 1783 is sent to a unicast address, if the association is over a 1784 point-to-point link, or when bidirectional reachability is 1785 ascertained by means outside of the Babel protocol. 1787 Reserved Sent as 0 and MUST be ignored on reception. 1789 Rxcost The rxcost according to the sending node of the interface 1790 whose address is specified in the Address field. The value 1791 FFFF hexadecimal (infinity) indicates that this interface 1792 is unreachable. 1794 Interval An upper bound, expressed in centiseconds, on the time 1795 after which the sending node will send a new IHU; this MUST 1796 NOT be 0. The receiving node will use this value in order 1797 to compute a hold time for this symmetric association. 1799 Address The address of the destination node, in the format 1800 specified by the AE field. Address compression is not 1801 allowed. 1803 Conceptually, an IHU is destined to a single neighbour. However, IHU 1804 TLVs contain an explicit destination address, and it MAY be sent to a 1805 multicast address, as this allows aggregation of IHUs destined to 1806 distinct neighbours into a single packet and avoids the need for an 1807 ARP or Neighbour Discovery exchange when a neighbour is not being 1808 used for data traffic. 1810 IHU TLVs with an unknown value for the AE field MUST be silently 1811 ignored. 1813 This TLV is self-terminating, and allows sub-TLVs. 1815 4.6.7. Router-Id 1817 0 1 2 3 1818 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 1819 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1820 | Type = 6 | Length | Reserved | 1821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1822 | | 1823 + Router-Id + 1824 | | 1825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1827 A Router-Id TLV establishes a router-id that is implied by subsequent 1828 Update TLVs. This TLV sets the router-id even if it is otherwise 1829 ignored due to an unknown mandatory sub-TLV. 1831 Fields : 1833 Type Set to 6 to indicate a Router-Id TLV. 1835 Length The length of the body, exclusive of the Type and Length 1836 fields. 1838 Reserved Sent as 0 and MUST be ignored on reception. 1840 Router-Id The router-id for routes advertised in subsequent Update 1841 TLVs. This MUST NOT consist of all zeroes or all ones. 1843 This TLV is self-terminating, and allows sub-TLVs. 1845 4.6.8. Next Hop 1847 0 1 2 3 1848 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 1849 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1850 | Type = 7 | Length | AE | Reserved | 1851 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1852 | Next hop... 1853 +-+-+-+-+-+-+-+-+-+-+-+- 1854 A Next Hop TLV establishes a next-hop address for a given address 1855 family (IPv4 or IPv6) that is implied by subsequent Update TLVs. 1856 This TLV sets up the next-hop for subsequent Update TLVs even if it 1857 is ignored due to an unknown mandatory sub-TLV. 1859 Fields : 1861 Type Set to 7 to indicate a Next Hop TLV. 1863 Length The length of the body, exclusive of the Type and Length 1864 fields. 1866 AE The encoding of the Address field. This SHOULD be 1 or 3 1867 and MUST NOT be 0. 1869 Reserved Sent as 0 and MUST be ignored on reception. 1871 Next hop The next-hop address advertised by subsequent Update TLVs, 1872 for this address family. 1874 When the address family matches the network-layer protocol that this 1875 packet is transported over, a Next Hop TLV is not needed: in that 1876 case, the next hop is taken to be the source address of the packet. 1878 Next Hop TLVs with an unknown value for the AE field MUST be silently 1879 ignored. 1881 This TLV is self-terminating, and allows sub-TLVs. 1883 4.6.9. Update 1885 0 1 2 3 1886 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 1887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1888 | Type = 8 | Length | AE | Flags | 1889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1890 | Plen | Omitted | Interval | 1891 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1892 | Seqno | Metric | 1893 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1894 | Prefix... 1895 +-+-+-+-+-+-+-+-+-+-+-+- 1897 An Update TLV advertises or retracts a route. As an optimisation, 1898 this can also have the side effect of establishing a new implied 1899 router-id and a new default prefix. 1901 Fields : 1903 Type Set to 8 to indicate an Update TLV. 1905 Length The length of the body, exclusive of the Type and Length 1906 fields. 1908 AE The encoding of the Prefix field. 1910 Flags The individual bits of this field specify special handling 1911 of this TLV (see below). 1913 Plen The length of the advertised prefix. 1915 Omitted The number of octets that have been omitted at the 1916 beginning of the advertised prefix and that should be taken 1917 from a preceding Update TLV with the PREFIX flag set. 1919 Interval An upper bound, expressed in centiseconds, on the time 1920 after which the sending node will send a new update for 1921 this prefix. This MUST NOT be 0 and SHOULD NOT be less 1922 than 10. The receiving node will use this value to compute 1923 a hold time for this routing table entry. The value FFFF 1924 hexadecimal (infinity) expresses that this announcement 1925 will not be repeated unless a request is received 1926 (Section 3.8.2.3). 1928 Seqno The originator's sequence number for this update. 1930 Metric The sender's metric for this route. The value FFFF 1931 hexadecimal (infinity) means that this is a route 1932 retraction. 1934 Prefix The prefix being advertised. This field's size is (Plen/8 1935 - Omitted) rounded upwards. 1937 The Flags field is interpreted as follows: 1939 +-+-+-+-+-+-+-+-+ 1940 |P|R|X|X|X|X|X|X| 1941 +-+-+-+-+-+-+-+-+ 1943 In the description below, a bit being 'set' means its value is '1', 1944 while 'cleared' means its value is '0'. 'X' bits MUST be cleared 1945 when sending and MUST be ignored on receipt. Every node MUST be able 1946 to interpret the PREFIX and ROUTER-ID flags. 1948 o P (PREFIX) flag (80 hexadecimal): if set, then this Update 1949 establishes a new default prefix for subsequent Update TLVs with a 1950 matching address encoding within the same packet, even if this TLV 1951 is otherwise ignored due to an unknown mandatory sub-TLV; 1953 o R (ROUTER-ID) flag (40 hexadecimal): if set, then this TLV 1954 establishes a new default router-id for this TLV and subsequent 1955 Update TLVs in the same packet, even if this TLV is otherwise 1956 ignored due to an unknown mandatory sub-TLV. This router-id is 1957 computed from the first address of the advertised prefix as 1958 follows: 1960 * if the length of the address is 8 octets or more, then the new 1961 router-id is taken from the 8 last octets of the address; 1963 * if the length of the address is smaller than 8 octets, then the 1964 new router-id consists of the required number of zero octets 1965 followed by the address, i.e., the address is stored on the 1966 right of the router-id. For example, for an IPv4 address, the 1967 router-id consists of 4 octets of zeroes followed by the IPv4 1968 address. 1970 The prefix being advertised by an Update TLV is computed as follows: 1972 o the first Omitted octets of the prefix are taken from the previous 1973 Update TLV with the PREFIX flag set and the same address encoding, 1974 even if it was ignored due to an unknown mandatory sub-TLV; 1976 o the next (Plen/8 - Omitted) rounded upwards octets are taken from 1977 the Prefix field; 1979 o the remaining octets are set to 0. If AE is 3 (link-local IPv6), 1980 Omitted MUST be 0) 1982 If the Metric field is finite, the router-id of the originating node 1983 for this announcement is taken from the prefix advertised by this 1984 Update if the ROUTER-ID flag is set, computed as described above. 1985 Otherwise, it is taken either from the preceding Router-Id packet, or 1986 the preceding Update packet with the ROUTER-ID flag set, whichever 1987 comes last, even if that TLV is otherwise ignored due to an unknown 1988 mandatory sub-TLV. 1990 The next-hop address for this update is taken from the last preceding 1991 Next Hop TLV with a matching address family (IPv4 or IPv6) in the 1992 same packet even if it was otherwise ignored due to an unknown 1993 mandatory sub-TLV; if no such TLV exists, it is taken from the 1994 network-layer source address of this packet. 1996 If the metric field is FFFF hexadecimal, this TLV specifies a 1997 retraction. In that case, the current router-id and the Seqno are 1998 not used. AE MAY then be 0, in which case this Update retracts all 1999 of the routes previously advertised on this interface. If the metric 2000 is finite, AE MUST NOT be 0. If the metric is infinite and AE is 0, 2001 Plen and Omitted MUST both be 0. 2003 Update TLVs with an unknown value for the AE field MUST be silently 2004 ignored. 2006 This TLV is self-terminating, and allows sub-TLVs. 2008 4.6.10. Route Request 2010 0 1 2 3 2011 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 2012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2013 | Type = 9 | Length | AE | Plen | 2014 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2015 | Prefix... 2016 +-+-+-+-+-+-+-+-+-+-+-+- 2018 A Route Request TLV prompts the receiver to send an update for a 2019 given prefix, or a full routing table dump. 2021 Fields : 2023 Type Set to 9 to indicate a Route Request TLV. 2025 Length The length of the body, exclusive of the Type and Length 2026 fields. 2028 AE The encoding of the Prefix field. The value 0 specifies 2029 that this is a request for a full routing table dump (a 2030 wildcard request). 2032 Plen The length of the requested prefix. 2034 Prefix The prefix being requested. This field's size is Plen/8 2035 rounded upwards. 2037 A Request TLV prompts the receiving node to send an update message 2038 for the prefix specified by the AE, Plen, and Prefix fields, or a 2039 full dump of its routing table if AE is 0 (in which case Plen MUST be 2040 0 and Prefix is of length 0). A Request may be sent to a unicast 2041 address if it is destined to a single node, or to a multicast address 2042 if the request is destined to all of the neighbours of the sending 2043 interface. 2045 This TLV is self-terminating, and allows sub-TLVs. 2047 4.6.11. Seqno Request 2049 0 1 2 3 2050 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 2051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2052 | Type = 10 | Length | AE | Plen | 2053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2054 | Seqno | Hop Count | Reserved | 2055 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2056 | | 2057 + Router-Id + 2058 | | 2059 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2060 | Prefix... 2061 +-+-+-+-+-+-+-+-+-+-+ 2063 A Seqno Request TLV prompts the receiver to send an Update for a 2064 given prefix with a given sequence number, or to forward the request 2065 further if it cannot be satisfied locally. 2067 Fields : 2069 Type Set to 10 to indicate a Seqno Request message. 2071 Length The length of the body, exclusive of the Type and Length 2072 fields. 2074 AE The encoding of the Prefix field. This MUST NOT be 0. 2076 Plen The length of the requested prefix. 2078 Seqno The sequence number that is being requested. 2080 Hop Count The maximum number of times that this TLV may be forwarded, 2081 plus 1. This MUST NOT be 0. 2083 Reserved Sent as 0 and MUST be ignored on reception. 2085 Router Id The Router-Id that is being requested. This MUST NOT 2086 consist of all zeroes or all ones. 2088 Prefix The prefix being requested. This field's size is Plen/8 2089 rounded upwards. 2091 A Seqno Request TLV prompts the receiving node to send an Update for 2092 the prefix specified by the AE, Plen, and Prefix fields, with either 2093 a router-id different from what is specified by the Router-Id field, 2094 or a Seqno no less (modulo 2^16) than what is specified by the Seqno 2095 field. If this request cannot be satisfied locally, then it is 2096 forwarded according to the rules set out in Section 3.8.1.2. 2098 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 2099 be forwarded to a multicast address and MUST NOT be forwarded to more 2100 than one neighbour. A request MUST NOT be forwarded if its Hop Count 2101 field is 1. 2103 This TLV is self-terminating, and allows sub-TLVs. 2105 4.7. Details of specific sub-TLVs 2107 4.7.1. Pad1 2109 0 2110 0 1 2 3 4 5 6 7 2111 +-+-+-+-+-+-+-+-+ 2112 | Type = 0 | 2113 +-+-+-+-+-+-+-+-+ 2115 Fields : 2117 Type Set to 0 to indicate a Pad1 sub-TLV. 2119 This sub-TLV is silently ignored on reception. 2121 4.7.2. PadN 2123 0 1 2 3 2124 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 2125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2126 | Type = 1 | Length | MBZ... 2127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 2129 Fields : 2131 Type Set to 1 to indicate a PadN sub-TLV. 2133 Length The length of the body, in octets, exclusive of the Type 2134 and Length fields. 2136 MBZ Set to 0 on transmission. 2138 This sub-TLV is silently ignored on reception. 2140 5. IANA Considerations 2142 IANA has registered the UDP port number 6696, called "babel", for use 2143 by the Babel protocol. 2145 IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and 2146 the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. 2148 6. Security Considerations 2150 As defined in this document, Babel is a completely insecure protocol. 2151 Any attacker can attract data traffic by advertising routes with a 2152 low metric. This particular issue can be solved either by lower- 2153 layer security mechanisms (e.g., IPsec or link-layer security), or by 2154 appending a cryptographic key to Babel packets; the provision of 2155 ignoring any data contained within a Babel packet beyond the body 2156 length declared by the header is designed for just such a purpose. 2158 The information that a Babel node announces to the whole routing 2159 domain is often sufficient to determine a mobile node's physical 2160 location with reasonable precision. The privacy issues that this 2161 causes can be mitigated somewhat by using randomly chosen router-ids 2162 and randomly chosen IP addresses, and changing them periodically. 2164 When carried over IPv6, Babel packets are ignored unless they are 2165 sent from a link-local IPv6 address; since routers don't forward 2166 link-local IPv6 packets, this provides protection against spoofed 2167 Babel packets being sent from the global Internet. No such natural 2168 protection exists when Babel packets are carried over IPv4. 2170 7. Acknowledgments 2172 A number of people have contributed text and ideas to this 2173 specification. I am particularly indebted to Matthieu Boutier, 2174 Gwendoline Chouasne, Toke Hoiland-Jorgensen, and especially David 2175 Schinazi. The address compression technique was inspired by 2176 [PACKETBB]. 2178 8. References 2180 8.1. Normative References 2182 [ADDRARCH] 2183 Hinden, R. and S. Deering, "IP Version 6 Addressing 2184 Architecture", RFC 4291, February 2006. 2186 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2187 Requirement Levels", RFC 2119, March 1997. 2189 8.2. Informative References 2191 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 2192 Sequenced Distance-Vector Routing (DSDV) for Mobile 2193 Computers", ACM SIGCOMM'94 Conference on Communications 2194 Architectures, Protocols and Applications 234-244, 1994. 2196 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 2197 Computations", IEEE/ACM Transactions on Networking 1:1, 2198 February 1993. 2200 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 2201 "EIGRP -- a Fast Routing Protocol Based on Distance 2202 Vectors", Proc. Interop 94, 1994. 2204 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 2205 high-throughput path metric for multi-hop wireless 2206 networks", Proc. MobiCom 2003, 2003. 2208 [IS-IS] "Information technology -- Telecommunications and 2209 information exchange between systems -- Intermediate 2210 System to Intermediate System intra-domain routeing 2211 information exchange protocol for use in conjunction with 2212 the protocol for providing the connectionless-mode network 2213 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 2215 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 2216 periodic routing messages", IEEE/ACM Transactions on 2217 Networking 2, 2, 122-136, April 1994. 2219 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2221 [PACKETBB] 2222 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2223 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 2224 Format", RFC 5444, February 2009. 2226 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 2228 Appendix A. Cost and Metric Computation 2230 The strategy for computing link costs and route metrics is a local 2231 matter; Babel itself only requires that it comply with the conditions 2232 given in Section 3.4.3 and Section 3.5.2. Different nodes MAY use 2233 different strategies in a single network and MAY use different 2234 strategies on different interface types. This section gives a few 2235 examples of such strategies. 2237 The sample implementation of Babel sends periodic Multicast Hellos, 2238 and never sends Unicast Hellos. It maintains statistics about the 2239 last 16 received Multicast Hello TLVs of each kind (Appendix A.1), 2240 computes costs by using the 2-out-of-3 strategy (Appendix A.2.1) on 2241 wired links, and ETX (Appendix A.2.2) on wireless links. It uses an 2242 additive algebra for metric computation (Appendix A.3.1). 2244 A.1. Maintaining Hello History 2246 For each neighbour, the sample implementation of Babel maintains two 2247 sets of Hello history, one for each kind of Hello, and an expected 2248 sequence number, one for Multicast and one for Unicast Hellos. Each 2249 Hello history is a vector of 16 bits, where a 1 value represents a 2250 received Hello, and a 0 value a missed Hello. For each kind of 2251 Hello, the expected sequence number, written ne, is the sequence 2252 number that is expected to be carried by the next received Hello from 2253 this neighbour. 2255 Whenever it receives a Hello packet of a given kind from a neighbour, 2256 a node compares the received sequence number nr for that kind of 2257 Hello with its expected sequence number ne. Depending on the outcome 2258 of this comparison, one of the following actions is taken: 2260 o if the two differ by more than 16 (modulo 2^16), then the sending 2261 node has probably rebooted and lost its sequence number; the whole 2262 associated neighbour table entry is flushed and a new one created; 2264 o otherwise, if the received nr is smaller (modulo 2^16) than the 2265 expected sequence number ne, then the sending node has increased 2266 its Hello interval without us noticing; the receiving node removes 2267 the last (ne - nr) entries from this neighbour's Hello history (we 2268 "undo history"); 2270 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 2271 node has decreased its Hello interval, and some Hellos were lost; 2272 the receiving node adds (nr - ne) 0 bits to the Hello history (we 2273 "fast-forward"). 2275 The receiving node then appends a 1 bit to the Hello history, resets 2276 the neighbour's hello timer, and sets ne to (nr + 1). If the 2277 Interval field of the received Hello is not zero, it resets the 2278 neighbour's hello timer to 1.5 times the advertised Interval (the 2279 extra margin allows for delay due to jitter). 2281 Whenever either Hello timer associated to a neighbour expires, the 2282 local node adds a 0 bit to this neighbour's Hello history, and 2283 increments the expected Hello number. If both Hello histories are 2284 empty (they contain 0 bits only), the neighbour entry is flushed; 2285 otherwise, the neighbour's hello timer is reset to the value 2286 advertised in the last Hello of that kind received from this 2287 neighbour (no extra margin is necessary in this case, since jitter 2288 was already taken into account when computing the timeout that has 2289 just expired). 2291 A.2. Cost Computation 2293 This section discusses how to compute costs based on Hello history. 2295 A.2.1. k-out-of-j 2297 K-out-of-j link sensing is suitable for wired links that are either 2298 up, in which case they only occasionally drop a packet, or down, in 2299 which case they drop all packets. 2301 The k-out-of-j strategy is parameterised by two small integers k and 2302 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 2303 1. A node keeps a history of the last j hellos; if k or more of 2304 those have been correctly received, the link is assumed to be up, and 2305 the rxcost is set to K; otherwise, the link is assumed to be down, 2306 and the rxcost is set to infinity. 2308 Since Babel supports two kinds of Hellos, a Babel node performs k- 2309 out-of-j twice for each neighbour, once on the Unicast and once on 2310 the Multicast Hello history. If either of the instances of k-out- 2311 of-j indicates that the link is up, then the link is assumed to be 2312 up, and the rxcost is set to K; if both instances indicate that the 2313 link is down, then the link is assumed to be down, and the rxcost is 2314 set to infinity. In other words, the resulting rxcost is the minimum 2315 of the rxcosts yielded by the two instances of k-out-of-j link 2316 sensing. 2318 The cost of a link performing k-out-of-j link sensing is defined as 2319 follows: 2321 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 2323 o cost = txcost otherwise. 2325 A.2.2. ETX 2327 Unlike wired links, which are bimodal (either up or down), wireless 2328 links exhibit continuous variation of the link quality. Naive 2329 application of hop-count routing in networks that use wireless links 2330 for transit tends to select long, lossy links in preference to 2331 shorter, lossless links, which can dramatically reduce throughput. 2333 For that reason, it is essential that a routing protocol designed to 2334 support wireless links perform some form of link-quality estimation. 2336 ETX [ETX] is a simple link-quality estimation algorithm that is 2337 designed to work well with the IEEE 802.11 MAC. The IEEE 802.11 MAC 2338 performs ARQ and rate adaptation on unicast frames, but not on 2339 multicast frames, which are sent at a fixed rate with no ARQ; 2340 therefore, measuring the loss rate of multicast frames yields a 2341 useful estimate of a link's quality. 2343 A node performing ETX link quality estimation uses a neighbour's 2344 Multicast Hello history to compute an estimate, written beta, of the 2345 probability that a Hello TLV is successfully received. Beta can be 2346 simply computed as the fraction of 1 bits within a small number (say, 2347 6) of the most recent entries in the Multicast Hello history, or it 2348 can be an exponential average, or some combination of both 2349 approaches. 2351 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2352 successfully sending a Hello TLV. The cost is then computed by 2354 cost = 256/(alpha * beta) 2356 or, equivalently, 2358 cost = (MAX(txcost, 256) * rxcost) / 256. 2360 Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast 2361 frames do not provide a useful measure of link quality, and therefore 2362 ETX ignores the Unicast Hello history. Thus, a node performing ETX 2363 link-quality estimation will not route through nodes unless they send 2364 periodic Multicast Hellos (possibly in addition to Unicast Hellos). 2366 A.3. Metric Computation 2368 As described in Section 3.5.2, the metric advertised by a neighbour 2369 is combined with the link cost to yield a metric. 2371 A.3.1. Additive Metrics 2373 The simplest approach for obtaining a monotonic, isotonic metric is 2374 to define the metric of a route as the sum of the costs of the 2375 component links. More formally, if a neighbour advertises a route 2376 with metric m over a link with cost c, then the resulting route has 2377 metric M(c, m) = c + m. 2379 A multiplicative metric can be converted to an additive one by taking 2380 the logarithm (in some suitable base) of the link costs. 2382 A.3.2. External Sources of Willingness 2384 A node may want to vary its willingness to forward packets by taking 2385 into account information that is external to the Babel protocol, such 2386 as the monetary cost of a link, the node's battery status, CPU load, 2387 etc. This can be done by adding to every route's metric a value k 2388 that depends on the external data. For example, if a battery-powered 2389 node receives an update with metric m over a link with cost c, it 2390 might compute a metric M(c, m) = k + c + m, where k depends on the 2391 battery status. 2393 In order to preserve strict monotonicity (Section 3.5.2), the value k 2394 must be greater than -c. 2396 A.4. Properties of Multicast and Unicast Hellos 2398 While Multicast and Unicast Hellos can be used together by 2399 implementations, how their timers differ is a local matter. On 2400 reliable wired links, a node may choose to only use Multicast Hellos, 2401 as they are sufficient for discovery and reachability detection, and 2402 Unicast Hellos offer close to no benefits in those scenarios. On 2403 unreliable wireless links where multicast has worse performance than 2404 unicast, a node may rely more on Unicast Hellos and send them 2405 alongside every unicast IHU it sends; it may also use a higher 2406 Multicast Hello Interval as they are no longer necessary for 2407 reachability detection but still allow discovery of new neighbours. 2409 Appendix B. Constants 2411 The choice of time constants is a trade-off between fast detection of 2412 mobility events and protocol overhead. Two implementations of Babel 2413 with different time constants will interoperate, although the 2414 resulting convergence time will most likely be dictated by the 2415 slowest of the two implementations. 2417 Experience with the sample implementation of Babel indicates that the 2418 Hello interval is the most important time constant: a mobility event 2419 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2420 on triggered updates and explicit requests, the Update interval only 2421 has an effect on the time it takes for accurate metrics to be 2422 propagated after variations in link costs too small to trigger an 2423 unscheduled update or in the presence of packet loss. 2425 At the time of writing, the sample implementation of Babel uses the 2426 following default values: 2428 Multicast Hello Interval: 4 seconds. 2430 IHU Interval: the advertised IHU interval is always 3 times the 2431 Multicast Hello interval. IHUs are actually sent with each Hello 2432 on lossy links (as determined from the Hello history), but only 2433 with every third Multicast Hello on lossless links. 2435 Unicast Hello Interval: the sample implementation never sends 2436 scheduled Unicast Hellos; 2438 Update Interval: 4 times the Multicast Hello interval. 2440 IHU Hold Time: 3.5 times the advertised IHU interval. 2442 Route Expiry Time: 3.5 times the advertised update interval. 2444 Source GC time: 3 minutes. 2446 The amount of jitter applied to a packet depends on whether it 2447 contains any urgent TLVs or not. Urgent triggered updates and urgent 2448 requests are delayed by no more than 200ms; other TLVs are delayed by 2449 no more than one-half the Multicast Hello interval. 2451 Appendix C. Considerations for protocol extensions 2453 Babel is an extensible protocol, and this document defines a number 2454 of mechanisms that can be used to extend the protocol in a backwards 2455 compatible manner: 2457 o increasing the version number in the packet header; 2459 o defining new TLVs; 2461 o defining new sub-TLVs (with or without the mandatory bit set); 2463 o defining new AEs; 2465 o using the packet trailer. 2467 New versions of the Babel protocol should only be defined if the new 2468 version is not backwards compatible with the original protocol. 2470 In many cases, an extension could be implemented either by defining a 2471 new TLV, or by adding a new sub-TLV to an existing TLV. For example, 2472 an extension whose purpose is to attach additional data to route 2473 updates can be implemented either by creating a new "enriched" Update 2474 TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by 2475 adding a mandatory TLV. 2477 The various encodings are treated differently by implementations that 2478 do not understand the extension. In the case of a new TLV or of a 2479 sub-TLV with the mandatory bit set, the whole TLV is ignored by 2480 implementations that do not implement the extension, while in the 2481 case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, 2482 and only the unknown sub-TLV is silently ignored. Therefore, a non- 2483 mandatory sub-TLV should be used by extensions that extend the Update 2484 in a compatible manner (the extension data may be silently ignored), 2485 while a mandatory sub-TLV or a new TLV must be used by extensions 2486 that make incompatible extensions to the meaning of the TLV (the 2487 whole TLV must be thrown away if the extension data is not 2488 understood). 2490 Experience shows that additional data tends to crop up in the most 2491 unexpected places. Hence, it is recommended that extensions should 2492 define self-terminating TLVs, and allow attaching sub-TLVs to them. 2494 Adding a new AE is essentially equivalent to adding a new TLV: Update 2495 TLVs with an unknown AE are ignored, just like unknown TLVs. 2496 However, adding a new AE is often more involved than adding a new 2497 TLV, since it creates a new set of compression state. Additionally, 2498 since the Next Hop TLV creates state specific to a given address 2499 family, as opposed to a given AE, a new AE for a previously defined 2500 address family must not be used in the Next Hop TLV if backwards 2501 compatibility is required. A similar issue arises with Update TLVs 2502 with unknown AEs establishing a new router-id (with ROUTER-ID flag 2503 set). Therefore, defining new AEs must be done with care if 2504 compatibility with unextended implementations is required. 2506 The packet trailer -- the space after the declared length of the 2507 packet but within the payload of the UDP datagram -- was originally 2508 intended to carry a cryptographic signature. However, at this time 2509 no extension has used it, and therefore we refrain from making any 2510 recommendations about its use due to the lack of implementation 2511 experience. 2513 Appendix D. Stub Implementations 2515 Babel is a fairly economic protocol. Updates take between 12 and 40 2516 octets per destination, depending on the address family and how 2517 successful compression is; in a double-stack flat network, an average 2518 of less than 24 octets per destination is typical. The route table 2519 occupies about 35 octets per IPv6 entry. To put these values into 2520 perspective, a single full-size Ethernet frame can carry some 65 2521 route updates, and a megabyte of memory can contain a 20000-entry 2522 routing table and the associated source table. 2524 Babel is also a reasonably simple protocol. The sample 2525 implementation consists of less than 12 000 lines of C code, and it 2526 compiles to less than 120 kB of text on a 32-bit CISC architecture; 2527 about half of this figure is due to protocol extensions and user- 2528 interface code. 2530 Nonetheless, in some very constrained environments, such as PDAs, 2531 microwave ovens, or abacuses, it may be desirable to have subset 2532 implementations of the protocol. 2534 There are many different definitions of a stub router, but for the 2535 needs of this section a stub implementation of Babel is one that 2536 announces one or more directly attached prefixes into a Babel network 2537 but doesn't reannounce any routes that it has learnt from its 2538 neighbours. It may either maintain a full routing table, or simply 2539 select a default gateway amongst any one of its neighbours that 2540 announces a default route. Since a stub implementation never 2541 forwards packets except from or to directly attached links, it cannot 2542 possibly participate in a routing loop, and hence it need not 2543 evaluate the feasibility condition or maintain a source table. 2545 No matter how primitive, a stub implementation MUST parse sub-TLVs of 2546 all the TLVs that it understands and check for the mandatory bit. It 2547 MUST answer acknowledgement requests and MUST participate in the 2548 Hello/IHU protocol (it MUST parse both Unicast and Multicast Hellos, 2549 and SHOULD send scheduled Hellos, preferably over multicast in order 2550 to make it discoverable). It MUST also be able to reply to seqno 2551 requests for routes that it announces and SHOULD be able to reply to 2552 route requests. 2554 Experiments show that an IPv6-only stub implementation of Babel can 2555 be written in less than 1000 lines of C code and compile to 13 kB of 2556 text on 32-bit CISC architecture. 2558 Appendix E. Software Availability 2560 The sample implementation of Babel is available from 2561 . 2563 Appendix F. Changes from previous versions 2565 F.1. Changes since RFC 6126 2567 o Changed UDP port number to 6696. 2569 o Consistently use router-id rather than id. 2571 o Clarified that the source garbage collection timer is reset after 2572 sending an update even if the entry was not modified. 2574 o In section "Seqno Requests", fixed an erroneous "route request". 2576 o In the description of the Seqno Request TLV, added the description 2577 of the Router-Id field. 2579 o Made router-ids all-0 and all-1 forbidden. 2581 F.2. Changes since draft-ietf-babel-rfc6126bis-00 2583 o Added security considerations. 2585 F.3. Changes since draft-ietf-babel-rfc6126bis-01 2587 o Integrated the format of sub-TLVs. 2589 o Mentioned for each TLV whether it supports sub-TLVs. 2591 o Added Appendix C. 2593 o Added a mandatory bit in sub-TLVs. 2595 o Changed compression state to be per-AF rather than per-AE. 2597 o Added implementation hint for the route table. 2599 o Clarified how router-ids are computed when bit 0x40 is set in 2600 Updates. 2602 o Relaxed the conditions for sending requests, and tightened the 2603 conditions for forwarding requests. 2605 o Clarified that neighbours should be acquired at some point, but it 2606 doesn't matter when. 2608 F.4. Changes since draft-ietf-babel-rfc6126bis-02 2610 o Added Unicast Hellos. 2612 o Added unscheduled (interval-less) Hellos. 2614 o Changed Appendix A to consider Unicast and unscheduled Hellos. 2616 o Changed Appendix B to agree with the reference implementation. 2618 o Added optional algorithm to avoid the hold time. 2620 o Changed the table of pending seqno requests to be indexed by 2621 router-id in addition to prefixes. 2623 o Relaxed the route acquisition algorithm. 2625 o Replaced minimal implementations by stub implementations. 2627 o Added acknowledgements section. 2629 Author's Address 2631 Juliusz Chroboczek 2632 IRIF, University of Paris-Diderot 2633 Case 7014 2634 75205 Paris Cedex 13 2635 France 2637 Email: jch@irif.fr