idnits 2.17.1 draft-ietf-babel-rfc6126bis-12.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 -- The draft header indicates that this document obsoletes RFC7557, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (August 7, 2019) is 1723 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) == Outdated reference: A later version (-10) exists of draft-ietf-babel-dtls-07 == Outdated reference: A later version (-12) exists of draft-ietf-babel-hmac-07 Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 2 comments (--). 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 Obsoletes: 6126,7557 (if approved) D. Schinazi 5 Intended status: Standards Track Google LLC 6 Expires: February 8, 2020 August 7, 2019 8 The Babel Routing Protocol 9 draft-ietf-babel-rfc6126bis-12 11 Abstract 13 Babel is a loop-avoiding distance-vector routing protocol that is 14 robust and efficient both in ordinary wired networks and in wireless 15 mesh networks. This document describes the Babel routing protocol, 16 and obsoletes RFCs 6126 and 7557. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on February 8, 2020. 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 55 1.3. Specification of Requirements . . . . . . . . . . . . . . 5 56 2. Conceptual Description of the Protocol . . . . . . . . . . . 5 57 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 58 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 5 59 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 60 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 7 61 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 62 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10 63 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10 64 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11 65 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12 66 3.1. Message Transmission and Reception . . . . . . . . . . . 12 67 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 13 68 3.3. Acknowledgments and acknowledgment requests . . . . . . . 17 69 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17 70 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 20 71 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24 72 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25 73 3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 28 74 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 32 75 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32 76 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33 77 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 34 78 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 35 79 4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 35 80 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 36 81 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 47 82 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 83 6. Security Considerations . . . . . . . . . . . . . . . . . . . 49 84 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 49 85 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 50 86 8.1. Normative References . . . . . . . . . . . . . . . . . . 50 87 8.2. Informative References . . . . . . . . . . . . . . . . . 50 88 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 51 89 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 51 90 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 52 91 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 54 92 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 54 93 Appendix C. Considerations for protocol extensions . . . . . . . 55 94 Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 57 95 Appendix E. Software Availability . . . . . . . . . . . . . . . 58 96 Appendix F. Changes from previous versions . . . . . . . . . . . 58 97 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 58 98 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 58 99 F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 58 100 F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 59 101 F.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 59 102 F.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 60 103 F.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 60 104 F.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 60 105 F.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 60 106 F.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 60 107 F.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 60 108 F.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 61 109 F.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 61 110 F.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 61 111 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 61 113 1. Introduction 115 Babel is a loop-avoiding distance-vector routing protocol that is 116 designed to be robust and efficient both in networks using prefix- 117 based routing and in networks using flat routing ("mesh networks"), 118 and both in relatively stable wired networks and in highly dynamic 119 wireless networks. 121 1.1. Features 123 The main property that makes Babel suitable for unstable networks is 124 that, unlike naive distance-vector routing protocols [RIP], it 125 strongly limits the frequency and duration of routing pathologies 126 such as routing loops and black-holes during reconvergence. Even 127 after a mobility event is detected, a Babel network usually remains 128 loop-free. Babel then quickly reconverges to a configuration that 129 preserves the loop-freedom and connectedness of the network, but is 130 not necessarily optimal; in many cases, this operation requires no 131 packet exchanges at all. Babel then slowly converges, in a time on 132 the scale of minutes, to an optimal configuration. This is achieved 133 by using sequenced routes, a technique pioneered by Destination- 134 Sequenced Distance-Vector routing [DSDV]. 136 More precisely, Babel has the following properties: 138 o when every prefix is originated by at most one router, Babel never 139 suffers from routing loops; 141 o when a single prefix is originated by multiple routers, Babel may 142 occasionally create a transient routing loop for this particular 143 prefix; this loop disappears in time proportional to the loop's 144 diameter, and never again (up to an arbitrary garbage-collection 145 (GC) time) will the routers involved participate in a routing loop 146 for the same prefix; 148 o assuming bounded packet loss rates, any routing black-holes that 149 may appear after a mobility event are corrected in a time at most 150 proportional to the network's diameter. 152 Babel has provisions for link quality estimation and for fairly 153 arbitrary metrics. When configured suitably, Babel can implement 154 shortest-path routing, or it may use a metric based, for example, on 155 measured packet loss. 157 Babel nodes will successfully establish an association even when they 158 are configured with different parameters. For example, a mobile node 159 that is low on battery may choose to use larger time constants (hello 160 and update intervals, etc.) than a node that has access to wall 161 power. Conversely, a node that detects high levels of mobility may 162 choose to use smaller time constants. The ability to build such 163 heterogeneous networks makes Babel particularly adapted to the 164 unmanaged and wireless environment. 166 Finally, Babel is a hybrid routing protocol, in the sense that it can 167 carry routes for multiple network-layer protocols (IPv4 and IPv6), 168 whichever protocol the Babel packets are themselves being carried 169 over. 171 1.2. Limitations 173 Babel has two limitations that make it unsuitable for use in some 174 environments. First, Babel relies on periodic routing table updates 175 rather than using a reliable transport; hence, in large, stable 176 networks it generates more traffic than protocols that only send 177 updates when the network topology changes. In such networks, 178 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 179 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 180 suitable. 182 Second, unless the optional algorithm described in Section 3.5.5 is 183 implemented, Babel does impose a hold time when a prefix is 184 retracted. While this hold time does not apply to the exact prefix 185 being retracted, and hence does not prevent fast reconvergence should 186 it become available again, it does apply to any shorter prefix that 187 covers it. This may make those implementations of Babel that do not 188 implement the optional algorithm described in Section 3.5.5 189 unsuitable for use in networks that implement automatic prefix 190 aggregation. 192 1.3. Specification of Requirements 194 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 195 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 196 "OPTIONAL" in this document are to be interpreted as described in BCP 197 14 [RFC2119] [RFC8174] when, and only when, they appear in all 198 capitals, as shown here. 200 2. Conceptual Description of the Protocol 202 Babel is a loop-avoiding distance vector protocol: it is based on the 203 Bellman-Ford protocol, just like the venerable RIP [RIP], but 204 includes a number of refinements that either prevent loop formation 205 altogether, or ensure that a loop disappears in a timely manner and 206 doesn't form again. 208 Conceptually, Bellman-Ford is executed in parallel for every source 209 of routing information (destination of data traffic). In the 210 following discussion, we fix a source S; the reader will recall that 211 the same algorithm is executed for all sources. 213 2.1. Costs, Metrics and Neighbourship 215 For every pair of neighbouring nodes A and B, Babel computes an 216 abstract value known as the cost of the link from A to B, written 217 C(A, B). Given a route between any two (not necessarily 218 neighbouring) nodes, the metric of the route is the sum of the costs 219 of all the links along the route. The goal of the routing algorithm 220 is to compute, for every source S, the tree of routes of lowest 221 metric to S. 223 Costs and metrics need not be integers. In general, they can be 224 values in any algebra that satisfies two fairly general conditions 225 (Section 3.5.2). 227 A Babel node periodically sends Hello messages to all of its 228 neighbours; it also periodically sends an IHU ("I Heard You") message 229 to every neighbour from which it has recently heard a Hello. From 230 the information derived from Hello and IHU messages received from its 231 neighbour B, a node A computes the cost C(A, B) of the link from A to 232 B. 234 2.2. The Bellman-Ford Algorithm 236 Every node A maintains two pieces of data: its estimated distance to 237 S, written D(A), and its next-hop router to S, written NH(A). 238 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 240 Periodically, every node B sends to all of its neighbours a route 241 update, a message containing D(B). When a neighbour A of B receives 242 the route update, it checks whether B is its selected next hop; if 243 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 244 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 245 its current value of D(A). If that value is smaller, meaning that 246 the received update advertises a route that is better than the 247 currently selected route, then NH(A) is set to B, and D(A) is set to 248 C(A, B) + D(B). 250 A number of refinements to this algorithm are possible, and are used 251 by Babel. In particular, convergence speed may be increased by 252 sending unscheduled "triggered updates" whenever a major change in 253 the topology is detected, in addition to the regular, scheduled 254 updates. Additionally, a node may maintain a number of alternate 255 routes, which are being advertised by neighbours other than its 256 selected neighbour, and which can be used immediately if the selected 257 route were to fail. 259 2.3. Transient Loops in Bellman-Ford 261 It is well known that a naive application of Bellman-Ford to 262 distributed routing can cause transient loops after a topology 263 change. Consider for example the following topology: 265 B 266 1 /| 267 1 / | 268 S --- A |1 269 \ | 270 1 \| 271 C 273 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 275 Suppose now that the link between S and A fails: 277 B 278 1 /| 279 / | 280 S A |1 281 \ | 282 1 \| 283 C 285 When it detects the failure of the link, A switches its next hop to B 286 (which is still advertising a route to S with metric 2), and 287 advertises a metric equal to 3, and then advertises a new route with 288 metric 3. This process of nodes changing selected neighbours and 289 increasing their metric continues until the advertised metric reaches 290 "infinity", a value larger than all the metrics that the routing 291 protocol is able to carry. 293 2.4. Feasibility Conditions 295 Bellman-Ford is a very robust algorithm: its convergence properties 296 are preserved when routers delay route acquisition or when they 297 discard some updates. Babel routers discard received route 298 announcements unless they can prove that accepting them cannot 299 possibly cause a routing loop. 301 More formally, we define a condition over route announcements, known 302 as the "feasibility condition", that guarantees the absence of 303 routing loops whenever all routers ignore route updates that do not 304 satisfy the feasibility condition. In effect, this makes Bellman- 305 Ford into a family of routing algorithms, parameterised by the 306 feasibility condition. 308 Many different feasibility conditions are possible. For example, BGP 309 can be modelled as being a distance-vector protocol with a (rather 310 drastic) feasibility condition: a routing update is only accepted 311 when the receiving node's AS number is not included in the update's 312 AS-Path attribute (note that BGP's feasibility condition does not 313 ensure the absence of transient "micro-loops" during reconvergence). 315 Another simple feasibility condition, used in the Destination- 316 Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the 317 Ad hoc On-Demand Distance Vector (AODV) protocol, stems from the 318 following observation: a routing loop can only arise after a router 319 has switched to a route with a larger metric than the route that it 320 had previously selected. Hence, one could decide that a route is 321 feasible only when its metric at the local node would be no larger 322 than the metric of the currently selected route, i.e., an 323 announcement carrying a metric D(B) is accepted by A when C(A, B) + 324 D(B) <= D(A). If all routers obey this constraint, then the metric 325 at every router is nonincreasing, and the following invariant is 326 always preserved: if A has selected B as its successor, then D(B) < 327 D(A), which implies that the forwarding graph is loop-free. 329 Babel uses a slightly more refined feasibility condition, derived 330 from EIGRP [DUAL]. Given a router A, define the feasibility distance 331 of A, written FD(A), as the smallest metric that A has ever 332 advertised for S to any of its neighbours. An update sent by a 333 neighbour B of A is feasible when the metric D(B) advertised by B is 334 strictly smaller than A's feasibility distance, i.e., when D(B) < 335 FD(A). 337 It is easy to see that this latter condition is no more restrictive 338 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 339 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 340 Suppose now that A receives a DSDV-feasible update that advertises a 341 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 342 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 344 To see that it is strictly less restrictive, consider the following 345 diagram, where A has selected the route through B, and D(A) = FD(A) = 346 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 347 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 348 the currently selected route: 350 B 351 1 / \ 1 352 / \ 353 S A 354 \ / 355 1 \ / 4 356 C 358 To show that this feasibility condition still guarantees loop- 359 freedom, recall that at the time when A accepts an update from B, the 360 metric D(B) announced by B is no smaller than FD(B); since it is 361 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 362 property is preserved when A sends updates, it remains true at all 363 times, which ensures that the forwarding graph has no loops. 365 2.5. Solving Starvation: Sequencing Routes 367 Obviously, the feasibility conditions defined above cause starvation 368 when a router runs out of feasible routes. Consider the following 369 diagram, where both A and B have selected the direct route to S: 371 A 372 1 /| D(A) = 1 373 / | FD(A) = 1 374 S |1 375 \ | D(B) = 2 376 2 \| FD(B) = 2 377 B 379 Suppose now that the link between A and S breaks: 381 A 382 | 383 | FD(A) = 1 384 S |1 385 \ | D(B) = 2 386 2 \| FD(B) = 2 387 B 389 The only route available from A to S, the one that goes through B, is 390 not feasible: A suffers from spurious starvation. At that point, the 391 whole subtree suffering from starvation must be reset, which is 392 essentially what EIGRP does when it performs a global synchronisation 393 of all the routers in the starving subtree (the "active" phase of 394 EIGRP). 396 Babel reacts to starvation in a less drastic manner, by using 397 sequenced routes, a technique introduced by DSDV and adopted by AODV. 398 In addition to a metric, every route carries a sequence number, a 399 nondecreasing integer that is propagated unchanged through the 400 network and is only ever incremented by the source; a pair (s, m), 401 where s is a sequence number and m a metric, is called a distance. 403 A received update is feasible when either it is more recent than the 404 feasibility distance maintained by the receiving node, or it is 405 equally recent and the metric is strictly smaller. More formally, if 406 FD(A) = (s, m), then an update carrying the distance (s', m') is 407 feasible when either s' > s, or s = s' and m' < m. 409 Assuming the sequence number of S is 137, the diagram above becomes: 411 A 412 | 413 | FD(A) = (137, 1) 414 S |1 415 \ | D(B) = (137, 2) 416 2 \| FD(B) = (137, 2) 417 B 419 After S increases its sequence number, and the new sequence number is 420 propagated to B, we have: 422 A 423 | 424 | FD(A) = (137, 1) 425 S |1 426 \ | D(B) = (138, 2) 427 2 \| FD(B) = (138, 2) 428 B 430 at which point the route through B becomes feasible again. 432 Note that while sequence numbers are used for determining 433 feasibility, they are not used in route selection: a node ignores the 434 sequence number when selecting the best route to a given destination 435 (Section 3.6). Doing otherwise would cause route oscillation while a 436 sequence number propagates through the network, and might even cause 437 persistent blackholes with some exotic metrics. 439 2.6. Requests 441 In DSDV, the sequence number of a source is increased periodically. 442 A route becomes feasible again after the source increases its 443 sequence number, and the new sequence number is propagated through 444 the network, which may, in general, require a significant amount of 445 time. 447 Babel takes a different approach. When a node detects that it is 448 suffering from a potentially spurious starvation, it sends an 449 explicit request to the source for a new sequence number. This 450 request is forwarded hop by hop to the source, with no regard to the 451 feasibility condition. Upon receiving the request, the source 452 increases its sequence number and broadcasts an update, which is 453 forwarded to the requesting node. 455 Note that after a change in network topology not all such requests 456 will, in general, reach the source, as some will be sent over links 457 that are now broken. However, if the network is still connected, 458 then at least one among the nodes suffering from spurious starvation 459 has an (unfeasible) route to the source; hence, in the absence of 460 packet loss, at least one such request will reach the source. 461 (Resending requests a small number of times compensates for packet 462 loss.) 464 Since requests are forwarded with no regard to the feasibility 465 condition, they may, in general, be caught in a forwarding loop; this 466 is avoided by having nodes perform duplicate detection for the 467 requests that they forward. 469 2.7. Multiple Routers 471 The above discussion assumes that each prefix is originated by a 472 single router. In real networks, however, it is often necessary to 473 have a single prefix originated by multiple routers: for example, the 474 default route will be originated by all of the edge routers of a 475 routing domain. 477 Since synchronising sequence numbers between distinct routers is 478 problematic, Babel treats routes for the same prefix as distinct 479 entities when they are originated by different routers: every route 480 announcement carries the router-id of its originating router, and 481 feasibility distances are not maintained per prefix, but per source, 482 where a source is a pair of a router-id and a prefix. In effect, 483 Babel guarantees loop-freedom for the forwarding graph to every 484 source; since the union of multiple acyclic graphs is not in general 485 acyclic, Babel does not in general guarantee loop-freedom when a 486 prefix is originated by multiple routers, but any loops will be 487 broken in a time at most proportional to the diameter of the loop -- 488 as soon as an update has "gone around" the routing loop. 490 Consider for example the following topology, where A has selected the 491 default route through S, and B has selected the one through S': 493 1 1 1 494 ::/0 -- S --- A --- B --- S' -- ::/0 496 Suppose that both default routes fail at the same time; then nothing 497 prevents A from switching to B, and B simultaneously switching to A. 498 However, as soon as A has successfully advertised the new route to B, 499 the route through A will become unfeasible for B. Conversely, as 500 soon as B will have advertised the route through A, the route through 501 B will become unfeasible for A. 503 In effect, the routing loop disappears at the latest when routing 504 information has gone around the loop. Since this process can be 505 delayed by lost packets, Babel makes certain efforts to ensure that 506 updates are sent reliably after a router-id change (Section 3.7.2). 508 Additionally, after the routers have advertised the two routes, both 509 sources will be in their source tables, which will prevent them from 510 ever again participating in a routing loop involving routes from S 511 and S' (up to the source GC time, which, available memory permitting, 512 can be set to arbitrarily large values). 514 2.8. Overlapping Prefixes 516 In the above discussion, we have assumed that all prefixes are 517 disjoint, as is the case in flat ("mesh") routing. In practice, 518 however, prefixes may overlap: for example, the default route 519 overlaps with all of the routes present in the network. 521 After a route fails, it is not correct in general to switch to a 522 route that subsumes the failed route. Consider for example the 523 following configuration: 525 1 1 526 ::/0 -- A --- B --- C 528 Suppose that node C fails. If B forwards packets destined to C by 529 following the default route, a routing loop will form, and persist 530 until A learns of B's retraction of the direct route to C. B avoids 531 this pitfall by installing an "unreachable" route after a route is 532 retracted; this route is maintained until it can be guaranteed that 533 the former route has been retracted by all of B's neighbours 534 (Section 3.5.5). 536 3. Protocol Operation 538 Every Babel speaker is assigned a router-id, which is an arbitrary 539 string of 8 octets that is assumed unique across the routing domain. 540 For example, router-ids could be assigned randomly, or they could be 541 derived from a link-layer address. (The protocol encoding is 542 slightly more compact when router-ids are assigned in the same manner 543 as the IPv6 layer assigns host IDs, see the definition of the "R" 544 flag in Section 4.6.9.) 546 3.1. Message Transmission and Reception 548 Babel protocol packets are sent in the body of a UDP datagram (as 549 described in Section 4 below). Each Babel packet consists of zero or 550 more TLVs. Most TLVs may contain sub-TLVs. 552 The protocol's control traffic can be carried indifferently over IPv6 553 or over IPv4, and prefixes of either address family can be announced 554 over either protocol. Thus, there are at least two natural 555 deployment models: using IPv6 exclusively for all control traffic, or 556 running two distinct protocol instances, one for each address family. 557 The exclusive use of IPv6 for all control traffic is RECOMMENDED, 558 since using both protocols at the same time doubles the amount of 559 traffic devoted to neighbour discovery and link quality estimation. 561 The source address of a Babel packet is always a unicast address, 562 link-local in the case of IPv6. Babel packets may be sent to a well- 563 known (link-local) multicast address or to a (link-local) unicast 564 address. In normal operation, a Babel speaker sends both multicast 565 and unicast packets to its neighbours. 567 With the exception of acknowledgments, all Babel TLVs can be sent to 568 either unicast or multicast addresses, and their semantics does not 569 depend on whether the destination is a unicast or a multicast 570 address. Hence, a Babel speaker does not need to determine the 571 destination address of a packet that it receives in order to 572 interpret it. 574 A moderate amount of jitter may be applied to packets sent by a Babel 575 speaker: outgoing TLVs are buffered and SHOULD be sent with a small 576 random delay. This is done for two purposes: it avoids 577 synchronisation of multiple Babel speakers across a network [JITTER], 578 and it allows for the aggregation of multiple TLVs into a single 579 packet. 581 The exact delay and amount of jitter applied to a packet depends on 582 whether it contains any urgent TLVs. Acknowledgment TLVs MUST be 583 sent before the deadline specified in the corresponding request. The 584 particular class of updates specified in Section 3.7.2 MUST be sent 585 in a timely manner. The particular class of request and update TLVs 586 specified in Section 3.8.2 SHOULD be sent in a timely manner. 588 3.2. Data Structures 590 In this section, we give a description of the data structures that 591 every Babel speaker maintains. This description is conceptual: a 592 Babel speaker may use different data structures as long as the 593 resulting protocol is the same as the one described in this document. 594 For example, rather than maintaining a single table containing both 595 selected and unselected (fallback) routes, as described in 596 Section 3.2.6 below, an actual implementation would probably use two 597 tables, one with selected routes and one with fallback routes. 599 3.2.1. Sequence number arithmetic 601 Sequence numbers (seqnos) appear in a number of Babel data 602 structures, and they are interpreted as integers modulo 2^16. For 603 the purposes of this document, arithmetic on sequence numbers is 604 defined as follows. 606 Given a seqno s and an integer n, the sum of s and n is defined by 608 s + n (modulo 2^16) = (s + n) MOD 2^16 610 or, equivalently, 612 s + n (modulo 2^16) = (s + n) AND 65535 614 where MOD is the modulo operation yielding a non-negative integer and 615 AND is the bitwise conjunction operation. 617 Given two sequence numbers s and s', the relation s is less than s' 618 (s < s') is defined by 620 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 622 or equivalently 624 s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. 626 3.2.2. Node Sequence Number 628 A node's sequence number is a 16-bit integer that is included in 629 route updates sent for routes originated by this node. 631 A node increments its sequence number (modulo 2^16) whenever it 632 receives a request for a new sequence number (Section 3.8.1.2). A 633 node SHOULD NOT increment its sequence number (seqno) spontaneously, 634 since increasing seqnos makes it less likely that other nodes will 635 have feasible alternate routes when their selected routes fail. 637 3.2.3. The Interface Table 639 The interface table contains the list of interfaces on which the node 640 speaks the Babel protocol. Every interface table entry contains the 641 interface's outgoing Multicast Hello seqno, a 16-bit integer that is 642 sent with each Multicast Hello TLV on this interface and is 643 incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note 644 that an interface's Multicast Hello seqno is unrelated to the node's 645 seqno.) 647 There are two timers associated with each interface table entry -- 648 the multicast hello timer, which governs the sending of scheduled 649 Multicast Hello and IHU packets, and the update timer, which governs 650 the sending of periodic route updates. 652 3.2.4. The Neighbour Table 654 The neighbour table contains the list of all neighbouring interfaces 655 from which a Babel packet has been recently received. The neighbour 656 table is indexed by pairs of the form (interface, address), and every 657 neighbour table entry contains the following data: 659 o the local node's interface over which this neighbour is reachable; 661 o the address of the neighbouring interface; 663 o a history of recently received Multicast Hello packets from this 664 neighbour; this can, for example, be a sequence of n bits, for 665 some small value n, indicating which of the n hellos most recently 666 sent by this neighbour have been received by the local node; 668 o a history of recently received Unicast Hello packets from this 669 neighbour; 671 o the "transmission cost" value from the last IHU packet received 672 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 673 hold timer for this neighbour has expired; 675 o the expected incoming Multicast Hello sequence number for this 676 neighbour, an integer modulo 2^16. 678 o the expected incoming Unicast Hello sequence number for this 679 neighbour, an integer modulo 2^16. 681 o the outgoing Unicast Hello sequence number for this neighbour, an 682 integer modulo 2^16 that is sent with each Unicast Hello TLV to 683 this neighbour and is incremented (modulo 2^16) whenever a Unicast 684 Hello is sent. (Note that the outgoing Unicast Hello seqno for a 685 neighbour is distinct from the interface's outgoing Multicast 686 Hello seqno.) 688 There are three timers associated with each neighbour entry -- the 689 multicast hello timer, which is initialised from the interval value 690 carried by scheduled Multicast Hello TLVs, the unicast hello timer, 691 which is initialised from the interval value carried by scheduled 692 Unicast Hello TLVs, and the IHU timer, which is initialised to a 693 small multiple of the interval carried in IHU TLVs. 695 Note that the neighbour table is indexed by IP addresses, not by 696 router-ids: neighbourship is a relationship between interfaces, not 697 between nodes. Therefore, two nodes with multiple interfaces can 698 participate in multiple neighbourship relationships, a situation that 699 can notably arise when wireless nodes with multiple radios are 700 involved. 702 3.2.5. The Source Table 704 The source table is used to record feasibility distances. It is 705 indexed by triples of the form (prefix, plen, router-id), and every 706 source table entry contains the following data: 708 o the prefix (prefix, plen), where plen is the prefix length, that 709 this entry applies to; 711 o the router-id of a router originating this prefix; 713 o a pair (seqno, metric), this source's feasibility distance. 715 There is one timer associated with each entry in the source table -- 716 the source garbage-collection timer. It is initialised to a time on 717 the order of minutes and reset as specified in Section 3.7.3. 719 3.2.6. The Route Table 721 The route table contains the routes known to this node. It is 722 indexed by triples of the form (prefix, plen, neighbour), and every 723 route table entry contains the following data: 725 o the source (prefix, plen, router-id) for which this route is 726 advertised; 728 o the neighbour that advertised this route; 730 o the metric with which this route was advertised by the neighbour, 731 or FFFF hexadecimal (infinity) for a recently retracted route; 733 o the sequence number with which this route was advertised; 735 o the next-hop address of this route; 737 o a boolean flag indicating whether this route is selected, i.e., 738 whether it is currently being used for forwarding and is being 739 advertised. 741 There is one timer associated with each route table entry -- the 742 route expiry timer. It is initialised and reset as specified in 743 Section 3.5.4. 745 Note that there are two distinct (seqno, metric) pairs associated to 746 each route: the route's distance, which is stored in the route table, 747 and the feasibility distance, stored in the source table and shared 748 between all routes with the same source. 750 3.2.7. The Table of Pending Seqno Requests 752 The table of pending seqno requests contains a list of seqno requests 753 that the local node has sent (either because they have been 754 originated locally, or because they were forwarded) and to which no 755 reply has been received yet. This table is indexed by triples of the 756 form (prefix, plen, router-id), and every entry in this table 757 contains the following data: 759 o the prefix, plen, router-id, and seqno being requested; 761 o the neighbour, if any, on behalf of which we are forwarding this 762 request; 764 o a small integer indicating the number of times that this request 765 will be resent if it remains unsatisfied. 767 There is one timer associated with each pending seqno request; it 768 governs both the resending of requests and their expiry. 770 3.3. Acknowledgments and acknowledgment requests 772 A Babel speaker may request that a neighbour receiving a given packet 773 reply with an explicit acknowledgment within a given time. While the 774 use of acknowledgment requests is optional, every Babel speaker MUST 775 be able to reply to such a request. 777 An acknowledgment MUST be sent to a unicast destination. On the 778 other hand, acknowledgment requests may be sent to either unicast or 779 multicast destinations, in which case they request an acknowledgment 780 from all of the receiving nodes. 782 When to request acknowledgments is a matter of local policy; the 783 simplest strategy is to never request acknowledgments and to rely on 784 periodic updates to ensure that any reachable routes are eventually 785 propagated throughout the routing domain. In order to improve 786 convergence speed and reduce the amount of control traffic, 787 acknowledgment requests MAY be used in order to reliably send urgent 788 updates (Section 3.7.2) and retractions (Section 3.5.5), especially 789 when the number of neighbours on a given interface is small. Since 790 Babel is designed to deal gracefully with packet loss on unreliable 791 media, sending all packets with acknowledgment requests is not 792 necessary, and NOT RECOMMENDED, as the acknowledgments cause 793 additional traffic and may force additional Address Resolution 794 Protocol (ARP) or Neighbour Discovery (ND) exchanges. 796 3.4. Neighbour Acquisition 798 Neighbour acquisition is the process by which a Babel node discovers 799 the set of neighbours heard over each of its interfaces and 800 ascertains bidirectional reachability. On unreliable media, 801 neighbour acquisition additionally provides some statistics that may 802 be useful for link quality computation. 804 Before it can exchange routing information with a neighbour, a Babel 805 node MUST create an entry for that neighbour in the neighbour table. 806 When to do that is implementation-specific; suitable strategies 807 include creating an entry when any Babel packet is received, or 808 creating an entry when a Hello TLV is parsed. Similarly, in order to 809 conserve system resources, an implementation SHOULD discard an entry 810 when it has been unused for long enough; suitable strategies include 811 dropping the neighbour after a timeout, and dropping a neighbour when 812 the associated Hello histories become empty (see Appendix A.2). 814 3.4.1. Reverse Reachability Detection 816 Every Babel node sends Hello TLVs to its neighbours to indicate that 817 it is alive, at regular or irregular intervals. Each Hello TLV 818 carries an increasing (modulo 2^16) sequence number and an upper 819 bound on the time interval until the next Hello of the same type (see 820 below). If the time interval is set to 0, then the Hello TLV does 821 not establish a new promise: the deadline carried by the previous 822 Hello of the same type still applies to the next Hello (if the most 823 recent scheduled Hello of the right kind was received at time t0 and 824 carried interval i, then the previous promise of sending another 825 Hello before time t0 + i still holds). We say that a Hello is 826 "scheduled" if it carries a non-zero interval, and "unscheduled" 827 otherwise. 829 There are two kinds of Hellos: Multicast Hellos, which use a per- 830 interface Hello counter (the Multicast Hello seqno), and Unicast 831 Hellos, which use a per-neighbour counter (the Unicast Hello seqno). 832 A Multicast Hello with a given seqno MUST be sent to all neighbours 833 on a given interface, either by sending it to a multicast address or 834 by sending it to one unicast address per neighbour (hence, the term 835 "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a 836 given seqno should normally be sent to just one neighbour (over 837 unicast), since the sequence numbers of different neighbours are not 838 in general synchronised. 840 Multicast Hellos sent over multicast can be used for neighbour 841 discovery; hence, a node SHOULD send periodic (scheduled) Multicast 842 Hellos unless neighbour discovery is performed by means outside of 843 the Babel protocol. A node MAY send Unicast Hellos or unscheduled 844 Hellos of either kind for any reason, such as reducing the amount of 845 multicast traffic or improving reliability on link technologies with 846 poor support for link-layer multicast. 848 A node MAY send a scheduled Hello ahead of time. A node MAY change 849 its scheduled Hello interval. The Hello interval MAY be decreased at 850 any time; it MAY be increased immediately before sending a Hello TLV, 851 but SHOULD NOT be increased at other times. (Equivalently, a node 852 SHOULD send a scheduled Hello immediately after increasing its Hello 853 interval.) 855 How to deal with received Hello TLVs and what statistics to maintain 856 are considered local implementation matters; typically, a node will 857 maintain some sort of history of recently received Hellos. An 858 example of a suitable algorithm is described in Appendix A.1. 860 After receiving a Hello, or determining that it has missed one, the 861 node recomputes the association's cost (Section 3.4.3) and runs the 862 route selection procedure (Section 3.6). 864 3.4.2. Bidirectional Reachability Detection 866 In order to establish bidirectional reachability, every node sends 867 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 868 IHUs carry an explicit interval value, they MAY be sent less often 869 than Hellos in order to reduce the amount of routing traffic in dense 870 networks; in particular, they SHOULD be sent less often than Hellos 871 over links with little packet loss. While IHUs are conceptually 872 unicast, they MAY be sent to a multicast address in order to avoid an 873 ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 874 into a single packet. 876 In addition to the periodic IHUs, a node MAY, at any time, send an 877 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 878 interval, and it MAY increase its IHU interval immediately before 879 sending an IHU, but SHOULD NOT increase it at any other time. 880 (Equivalently, a node SHOULD send an extra IHU immediately after 881 increasing its Hello interval.) 883 Every IHU TLV contains two pieces of data: the link's rxcost 884 (reception cost) from the sender's perspective, used by the neighbour 885 for computing link costs (Section 3.4.3), and the interval between 886 periodic IHU packets. A node receiving an IHU sets the value of the 887 txcost (transmission cost) maintained in the neighbour table to the 888 value contained in the IHU, and resets the IHU timer associated to 889 this neighbour to a small multiple of the interval value received in 890 the IHU. When a neighbour's IHU timer expires, the neighbour's 891 txcost is set to infinity. 893 After updating a neighbour's txcost, the receiving node recomputes 894 the neighbour's cost (Section 3.4.3) and runs the route selection 895 procedure (Section 3.6). 897 3.4.3. Cost Computation 899 A neighbourship association's link cost is computed from the values 900 maintained in the neighbour table: the statistics kept in the 901 neighbour table about the reception of Hellos, and the txcost 902 computed from received IHU packets. 904 For every neighbour, a Babel node computes a value known as this 905 neighbour's rxcost. This value is usually derived from the Hello 906 history, which may be combined with other data, such as statistics 907 maintained by the link layer. The rxcost is sent to a neighbour in 908 each IHU. 910 Since nodes do not necessarily send periodic Unicast Hellos but do 911 usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD 912 use an algorithm that yields a finite rxcost when only Multicast 913 Hellos are received, unless interoperability with nodes that only 914 send Multicast Hellos is not required. 916 How the txcost and rxcost are combined in order to compute a link's 917 cost is a matter of local policy; as far as Babel's correctness is 918 concerned, only the following conditions MUST be satisfied: 920 o the cost is strictly positive; 922 o if no Hello TLVs of either kind were received recently, then the 923 cost is infinite; 925 o if the txcost is infinite, then the cost is infinite. 927 Note that while this document does not constrain cost computation any 928 further, not all cost computation strategies will give good results. 929 See Appendix A.2 for examples of strategies for computing a link's 930 cost that are known to work well in practice. 932 3.5. Routing Table Maintenance 934 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 935 seqno, metric), where (prefix, plen) is the prefix for which a route 936 is being advertised, router-id is the router-id of the router 937 originating this update, seqno is a nondecreasing (modulo 2^16) 938 integer that carries the originating router seqno, and metric is the 939 announced metric. 941 Before being accepted, an update is checked against the feasibility 942 condition (Section 3.5.1), which ensures that the route does not 943 create a routing loop. If the feasibility condition is not 944 satisfied, the update is either ignored or prevents the route from 945 being selected, as described in Section 3.5.4. If the feasibility 946 condition is satisfied, then the update cannot possibly cause a 947 routing loop. 949 3.5.1. The Feasibility Condition 951 The feasibility condition is applied to all received updates. The 952 feasibility condition compares the metric in the received update with 953 the metrics of the updates previously sent by the receiving node; 954 updates that fail the feasibility condition, and therefore have 955 metrics large enough to cause a routing loop, are either ignored or 956 prevent the resulting route from being selected. 958 A feasibility distance is a pair (seqno, metric), where seqno is an 959 integer modulo 2^16 and metric is a positive integer. Feasibility 960 distances are compared lexicographically, with the first component 961 inverted: we say that a distance (seqno, metric) is strictly better 962 than a distance (seqno', metric'), written 964 (seqno, metric) < (seqno', metric') 966 when 968 seqno > seqno' or (seqno = seqno' and metric < metric') 970 where sequence numbers are compared modulo 2^16. 972 Given a source (prefix, plen, router-id), a node's feasibility 973 distance for this source is the minimum, according to the ordering 974 defined above, of the distances of all the finite updates ever sent 975 by this particular node for the prefix (prefix, plen) and the given 976 router-id. Feasibility distances are maintained in the source table, 977 the exact procedure is given in Section 3.7.3. 979 A received update is feasible when either it is a retraction (its 980 metric is FFFF hexadecimal), or the advertised distance is strictly 981 better, in the sense defined above, than the feasibility distance for 982 the corresponding source. More precisely, a route advertisement 983 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 984 feasible if one of the following conditions holds: 986 o metric is infinite; or 988 o no entry exists in the source table indexed by (prefix, plen, 989 router-id); or 991 o an entry (prefix, plen, router-id, seqno', metric') exists in the 992 source table, and either 994 * seqno' < seqno or 996 * seqno = seqno' and metric < metric'. 998 Note that the feasibility condition considers the metric advertised 999 by the neighbour, not the route's metric; hence, a fluctuation in a 1000 neighbour's cost cannot render a selected route unfeasible. Note 1001 further that retractions (updates with infinite metric) are always 1002 feasible, since they cannot possibly cause a routing loop. 1004 3.5.2. Metric Computation 1006 A route's metric is computed from the metric advertised by the 1007 neighbour and the neighbour's link cost. Just like cost computation, 1008 metric computation is considered a local policy matter; as far as 1009 Babel is concerned, the function M(c, m) used for computing a metric 1010 from a locally computed link cost and the metric advertised by a 1011 neighbour MUST only satisfy the following conditions: 1013 o if c is infinite, then M(c, m) is infinite; 1015 o M is strictly monotonic: M(c, m) > m. 1017 Additionally, the metric SHOULD satisfy the following condition: 1019 o M is left-distributive: if m <= m', then M(c, m) <= M(c, m'). 1021 Note that while strict monotonicity is essential to the integrity of 1022 the network (persistent routing loops may arise if it is not 1023 satisfied), left distributivity is not: if it is not satisfied, Babel 1024 will still converge to a loop-free configuration, but might not reach 1025 a global optimum (in fact, a global optimum may not even exist). 1027 As with cost computation, not all strategies for computing route 1028 metrics will give good results. In particular, some metrics are more 1029 likely than others to lead to routing instabilities (route flapping). 1030 In Appendix A.3, we give a number of examples of strictly monotonic, 1031 left-distributive routing metrics that are known to work well in 1032 practice. 1034 3.5.3. Encoding of Updates 1036 In a large network, the bulk of Babel traffic consists of route 1037 updates; hence, some care has been given to encoding them 1038 efficiently. An Update TLV itself only contains the prefix, seqno, 1039 and metric, while the next hop is derived either from the network- 1040 layer source address of the packet or from an explicit Next Hop TLV 1041 in the same packet. The router-id is derived from a separate Router- 1042 Id TLV in the same packet, which optimises the case when multiple 1043 updates are sent with the same router-id. 1045 Additionally, a prefix of the advertised prefix can be omitted in an 1046 Update TLV, in which case it is copied from a previous Update TLV in 1047 the same packet -- this is known as address compression 1048 (Section 4.6.9). 1050 Finally, as a special optimisation for the case when a router-id 1051 coincides with the interface-id part of an IPv6 address, the router- 1052 id can optionally be derived from the low-order bits of the 1053 advertised prefix. 1055 The encoding of updates is described in detail in Section 4.6. 1057 3.5.4. Route Acquisition 1059 When a Babel node receives an update (prefix, plen, router-id, seqno, 1060 metric) from a neighbour neigh with a link cost value equal to cost, 1061 it checks whether it already has a route table entry indexed by 1062 (prefix, plen, neigh). 1064 If no such entry exists: 1066 o if the update is unfeasible, it MAY be ignored; 1068 o if the metric is infinite (the update is a retraction of a route 1069 we do not know about), the update is ignored; 1071 o otherwise, a new entry is created in the route table, indexed by 1072 (prefix, plen, neigh), with source equal to (prefix, plen, router- 1073 id), seqno equal to seqno and an advertised metric equal to the 1074 metric carried by the update. 1076 If such an entry exists: 1078 o if the entry is currently selected, the update is unfeasible, and 1079 the router-id of the update is equal to the router-id of the 1080 entry, then the update MAY be ignored; 1082 o otherwise, the entry's sequence number, advertised metric, metric, 1083 and router-id are updated and, if the advertised metric is not 1084 infinite, the route's expiry timer is reset to a small multiple of 1085 the Interval value included in the update. If the update is 1086 unfeasible, then the (now unfeasible) entry MUST be immediately 1087 unselected. If the update caused the router-id of the entry to 1088 change, an update (possibly a retraction) MUST be sent in a timely 1089 manner (see Section 3.7.2). 1091 Note that the route table may contain unfeasible routes, either 1092 because they were created by an unfeasible update or due to a metric 1093 fluctuation. Such routes are never selected, since they are not 1094 known to be loop-free; should all the feasible routes become 1095 unusable, however, the unfeasible routes can be made feasible and 1096 therefore possible to select by sending requests along them (see 1097 Section 3.8.2). 1099 When a route's expiry timer triggers, the behaviour depends on 1100 whether the route's metric is finite. If the metric is finite, it is 1101 set to infinity and the expiry timer is reset. If the metric is 1102 already infinite, the route is flushed from the route table. 1104 After the route table is updated, the route selection procedure 1105 (Section 3.6) is run. 1107 3.5.5. Hold Time 1109 When a prefix P is retracted, because all routes are unfeasible or 1110 have an infinite metric (whether due to the expiry timer or to other 1111 reasons), and a shorter prefix P' that covers P is reachable, P' 1112 cannot in general be used for routing packets destined to P without 1113 running the risk of creating a routing loop (Section 2.8). 1115 To avoid this issue, whenever a prefix P is retracted, a route table 1116 entry with infinite metric is maintained as described in 1117 Section 3.5.4 above. As long as this entry is maintained, packets 1118 destined to an address within P MUST NOT be forwarded by following a 1119 route for a shorter prefix. This entry is removed as soon as a 1120 finite-metric update for prefix P is received and the resulting route 1121 selected. If no such update is forthcoming, the infinite metric 1122 entry SHOULD be maintained at least until it is guaranteed that no 1123 neighbour has selected the current node as next-hop for prefix P. 1124 This can be achieved by either: 1126 o waiting until the route's expiry timer has expired 1127 (Section 3.5.4); 1129 o sending a retraction with an acknowledgment request (Section 3.3) 1130 to every reachable neighbour that has not explicitly retracted 1131 prefix P and waiting for all acknowledgments. 1133 The former option is simpler and ensures that at that point, any 1134 routes for prefix P pointing at the current node have expired. 1135 However, since the expiry time can be as high as a few minutes, doing 1136 that prevents automatic aggregation by creating spurious black-holes 1137 for aggregated routes. The latter option is RECOMMENDED as it 1138 dramatically reduces the time for which a prefix is unreachable in 1139 the presence of aggregated routes. 1141 3.6. Route Selection 1143 Route selection is the process by which a single route for a given 1144 prefix is selected to be used for forwarding packets and to be re- 1145 advertised to a node's neighbours. 1147 Babel is designed to allow flexible route selection policies. As far 1148 as the protocol's correctness is concerned, the route selection 1149 policy MUST only satisfy the following properties: 1151 o a route with infinite metric (a retracted route) is never 1152 selected; 1154 o an unfeasible route is never selected. 1156 Note, however, that Babel does not naturally guarantee the stability 1157 of routing, and configuring conflicting route selection policies on 1158 different routers may lead to persistent route oscillation. 1160 Route selection is a difficult problem, since a good route selection 1161 policy needs to take into account multiple mutually contradictory 1162 criteria; in roughly decreasing order of importance, these are: 1164 o routes with a small metric should be preferred to routes with a 1165 large metric; 1167 o switching router-ids should be avoided; 1169 o routes through stable neighbours should be preferred to routes 1170 through unstable ones; 1172 o stable routes should be preferred to unstable ones; 1174 o switching next hops should be avoided. 1176 Route selection MUST NOT take seqnos into account: a route MUST NOT 1177 be preferred just because it carries a higher (more recent) seqno. 1178 Doing otherwise would cause route oscillation while a new seqno 1179 propagates through the network, possibly following multiple paths of 1180 different latency, and might even create persistent blackholes if the 1181 metric being used is not left-distributive Section 3.5.2. 1183 A simple but useful strategy is to choose the feasible route with the 1184 smallest metric, with a small amount of hysteresis applied to avoid 1185 switching router-ids too often. 1187 After the route selection procedure is run, triggered updates 1188 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1190 3.7. Sending Updates 1192 A Babel speaker advertises to its neighbours its set of selected 1193 routes. Normally, this is done by sending one or more multicast 1194 packets containing Update TLVs on all of its connected interfaces; 1195 however, on link technologies where multicast is significantly more 1196 expensive than unicast, a node MAY choose to send multiple copies of 1197 updates in unicast packets, especially when the number of neighbours 1198 is small. 1200 Additionally, in order to ensure that any black-holes are reliably 1201 cleared in a timely manner, a Babel node sends retractions (updates 1202 with an infinite metric) for any recently retracted prefixes. 1204 If an update is for a route injected into the Babel domain by the 1205 local node (e.g., it carries the address of a local interface, the 1206 prefix of a directly attached network, or a prefix redistributed from 1207 a different routing protocol), the router-id is set to the local 1208 node's router-id, the metric is set to some arbitrary finite value 1209 (typically 0), and the seqno is set to the local router's sequence 1210 number. 1212 If an update is for a route learned from another Babel speaker, the 1213 router-id and sequence number are copied from the route table entry, 1214 and the metric is computed as specified in Section 3.5.2. 1216 3.7.1. Periodic Updates 1218 Every Babel speaker periodically advertises all of its selected 1219 routes on all of its interfaces, including any recently retracted 1220 routes. Since Babel doesn't suffer from routing loops (there is no 1221 "counting to infinity") and relies heavily on triggered updates 1222 (Section 3.7.2), this full dump only needs to happen infrequently. 1224 3.7.2. Triggered Updates 1226 In addition to periodic routing updates, a Babel speaker sends 1227 unscheduled, or triggered, updates in order to inform its neighbours 1228 of a significant change in the network topology. 1230 A change of router-id for the selected route to a given prefix may be 1231 indicative of a routing loop in formation; hence, a node MUST send a 1232 triggered update in a timely manner whenever it changes the selected 1233 router-id for a given destination. Additionally, it SHOULD make a 1234 reasonable attempt at ensuring that all reachable neighbours receive 1235 this update. 1237 There are two strategies for ensuring that. If the number of 1238 neighbours is small, then it is reasonable to send the update 1239 together with an acknowledgment request; the update is resent until 1240 all neighbours have acknowledged the packet, up to some number of 1241 times. If the number of neighbours is large, however, requesting 1242 acknowledgments from all of them might cause a non-negligible amount 1243 of network traffic; in that case, it may be preferable to simply 1244 repeat the update some reasonable number of times (say, 5 for 1245 wireless and 2 for wired links). 1247 A route retraction is somewhat less worrying: if the route retraction 1248 doesn't reach all neighbours, a black-hole might be created, which, 1249 unlike a routing loop, does not endanger the integrity of the 1250 network. When a route is retracted, a node SHOULD send a triggered 1251 update and SHOULD make a reasonable attempt at ensuring that all 1252 neighbours receive this retraction. 1254 Finally, a node MAY send a triggered update when the metric for a 1255 given prefix changes in a significant manner, due to a received 1256 update, because a link's cost has changed, or because a different 1257 next hop has been selected. A node SHOULD NOT send triggered updates 1258 for other reasons, such as when there is a minor fluctuation in a 1259 route's metric, when the selected next hop changes, or to propagate a 1260 new sequence number (except to satisfy a request, as specified in 1261 Section 3.8). 1263 3.7.3. Maintaining Feasibility Distances 1265 Before sending an update (prefix, plen, router-id, seqno, metric) 1266 with finite metric (i.e., not a route retraction), a Babel node 1267 updates the feasibility distance maintained in the source table. 1268 This is done as follows. 1270 If no entry indexed by (prefix, plen, router-id) exists in the source 1271 table, then one is created with value (prefix, plen, router-id, 1272 seqno, metric). 1274 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1275 it is updated as follows: 1277 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1279 o if seqno = seqno' and metric' > metric, then metric' := metric; 1281 o otherwise, nothing needs to be done. 1283 The garbage-collection timer for the entry is then reset. Note that 1284 the feasibility distance is not updated and the garbage-collection 1285 timer is not reset when a retraction (an update with infinite metric) 1286 is sent. 1288 When the garbage-collection timer expires, the entry is removed from 1289 the source table. 1291 3.7.4. Split Horizon 1293 When running over a transitive, symmetric link technology, e.g., a 1294 point-to-point link or a wired LAN technology such as Ethernet, a 1295 Babel node SHOULD use an optimisation known as split horizon. When 1296 split horizon is used on a given interface, a routing update for 1297 prefix P is not sent on the particular interface over which the 1298 selected route towards prefix P was learnt. 1300 Split horizon SHOULD NOT be applied to an interface unless the 1301 interface is known to be symmetric and transitive; in particular, 1302 split horizon is not applicable to decentralised wireless link 1303 technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates 1304 are sent over multicast. 1306 3.8. Explicit Requests 1308 In normal operation, a node's route table is populated by the regular 1309 and triggered updates sent by its neighbours. Under some 1310 circumstances, however, a node sends explicit requests in order to 1311 cause a resynchronisation with the source after a mobility event or 1312 to prevent a route from spuriously expiring. 1314 The Babel protocol provides two kinds of explicit requests: route 1315 requests, which simply request an update for a given prefix, and 1316 seqno requests, which request an update for a given prefix with a 1317 specific sequence number. The former are never forwarded; the latter 1318 are forwarded if they cannot be satisfied by the receiver. 1320 3.8.1. Handling Requests 1322 Upon receiving a request, a node either forwards the request or sends 1323 an update in reply to the request, as described in the following 1324 sections. If this causes an update to be sent, the update is either 1325 sent to a multicast address on the interface on which the request was 1326 received, or to the unicast address of the neighbour that sent the 1327 request. 1329 The exact behaviour is different for route requests and seqno 1330 requests. 1332 3.8.1.1. Route Requests 1334 When a node receives a route request for a given prefix, it checks 1335 its route table for a selected route to this exact prefix. If such a 1336 route exists, it MUST send an update (over unicast or over 1337 multicast); if such a route does not exist, it MUST send a retraction 1338 for that prefix. 1340 When a node receives a wildcard route request, it SHOULD send a full 1341 route table dump. Full route dumps MAY be rate-limited, especially 1342 if they are sent over multicast. 1344 3.8.1.2. Seqno Requests 1346 When a node receives a seqno request for a given router-id and 1347 sequence number, it checks whether its route table contains a 1348 selected entry for that prefix. If a selected route for the given 1349 prefix exists, it has finite metric, and either the router-ids are 1350 different or the router-ids are equal and the entry's sequence number 1351 is no smaller (modulo 2^16) than the requested sequence number, the 1352 node MUST send an update for the given prefix. If the router-ids 1353 match but the requested seqno is larger (modulo 2^16) than the route 1354 entry's, the node compares the router-id against its own router-id. 1355 If the router-id is its own, then it increases its sequence number by 1356 1 (modulo 2^16) and sends an update. A node MUST NOT increase its 1357 sequence number by more than 1 in response to a seqno request. 1359 Otherwise, if the requested router-id is not its own, the received 1360 request's hop count is 2 or more, and the node is advertising the 1361 prefix to its neighbours, the node selects a neighbour to forward the 1362 request to as follows: 1364 o if the node has one or more feasible routes toward the requested 1365 prefix with a next hop that is not the requesting node, then the 1366 node MUST forward the request to the next hop of one such route; 1368 o otherwise, if the node has one or more (not necessarily feasible) 1369 routes to the requested prefix with a next hop that is not the 1370 requesting node, then the node SHOULD forward the request to the 1371 next hop of one such route. 1373 In order to actually forward the request, the node decrements the hop 1374 count and sends the request in a unicast packet destined to the 1375 selected neighbour. 1377 A node SHOULD maintain a list of recently forwarded seqno requests 1378 and forward the reply (an update with a seqno sufficiently large to 1379 satisfy the request) in a timely manner. A node SHOULD compare every 1380 incoming seqno request against its list of recently forwarded seqno 1381 requests and avoid forwarding it if it is redundant (i.e., if it has 1382 recently sent a request with the same prefix, router-id and a seqno 1383 that is not smaller modulo 2^16). 1385 Since the request-forwarding mechanism does not necessarily obey the 1386 feasibility condition, it may get caught in routing loops; hence, 1387 requests carry a hop count to limit the time during which they remain 1388 in the network. However, since requests are only ever forwarded as 1389 unicast packets, the initial hop count need not be kept particularly 1390 low, and performing an expanding horizon search is not necessary. A 1391 single request MUST NOT be duplicated: it MUST NOT be forwarded to a 1392 multicast address, and it MUST NOT be forwarded to multiple 1393 neighbours. However, if a seqno request is resent by its originator, 1394 the subsequent copies MAY be forwarded to a different neighbour than 1395 the initial one. 1397 3.8.2. Sending Requests 1399 A Babel node MAY send a route or seqno request at any time, to a 1400 multicast or a unicast address; there is only one case when 1401 originating requests is required (Section 3.8.2.1). 1403 3.8.2.1. Avoiding Starvation 1405 When a route is retracted or expires, a Babel node usually switches 1406 to another feasible route for the same prefix. It may be the case, 1407 however, that no such routes are available. 1409 A node that has lost all feasible routes to a given destination but 1410 still has unexpired unfeasible routes to that destination MUST send a 1411 seqno request; if it doesn't have any such routes, it MAY still send 1412 a seqno request. The router-id of the request is set to the router- 1413 id of the route that it has just lost, and the requested seqno is the 1414 value contained in the source table plus 1. 1416 If the node has any (unfeasible) routes to the requested destination, 1417 then it MUST send the request to at least one of the next-hop 1418 neighbours that advertised these routes, and SHOULD send it to all of 1419 them; in any case, it MAY send the request to any other neighbours, 1420 whether they advertise a route to the requested destination or not. 1421 A simple implementation strategy is therefore to unconditionally 1422 multicast the request over all interfaces. 1424 Similar requests will be sent by other nodes that are affected by the 1425 route's loss. If the network is still connected, and assuming no 1426 packet loss, then at least one of these requests will be forwarded to 1427 the source, resulting in a route being advertised with a new sequence 1428 number. (Due to duplicate suppression, only a small number of such 1429 requests will actually reach the source.) 1431 In order to compensate for packet loss, a node SHOULD repeat such a 1432 request a small number of times if no route becomes feasible within a 1433 short time. In the presence of heavy packet loss, however, all such 1434 requests might be lost; in that case, the mechanism in the next 1435 section will eventually ensure that a new seqno is received. 1437 3.8.2.2. Dealing with Unfeasible Updates 1439 When a route's metric increases, a node might receive an unfeasible 1440 update for a route that it has currently selected. As specified in 1441 Section 3.5.1, the receiving node will either ignore the update or 1442 unselect the route. 1444 In order to keep routes from spuriously expiring because they have 1445 become unfeasible, a node SHOULD send a unicast seqno request when it 1446 receives an unfeasible update for a route that is currently selected. 1447 The requested sequence number is computed from the source table as in 1448 Section 3.8.2.1 above. 1450 Additionally, since metric computation does not necessarily coincide 1451 with the delay in propagating updates, a node might receive an 1452 unfeasible update from a currently unselected neighbour that is 1453 preferable to the currently selected route (e.g., because it has a 1454 much smaller metric); in that case, the node SHOULD send a unicast 1455 seqno request to the neighbour that advertised the preferable update. 1457 3.8.2.3. Preventing Routes from Expiring 1459 In normal operation, a route's expiry timer never triggers: since a 1460 route's hold time is computed from an explicit interval included in 1461 Update TLVs, a new update (possibly a retraction) should arrive in 1462 time to prevent a route from expiring. 1464 In the presence of packet loss, however, it may be the case that no 1465 update is successfully received for an extended period of time, 1466 causing a route to expire. In order to avoid such spurious expiry, 1467 shortly before a selected route expires, a Babel node SHOULD send a 1468 unicast route request to the neighbour that advertised this route; 1469 since nodes always send either updates or retractions in response to 1470 non-wildcard route requests (Section 3.8.1.1), this will usually 1471 result in the route being either refreshed or retracted. 1473 3.8.2.4. Acquiring New Neighbours 1475 In order to speed up convergence after a mobility event, a node MAY 1476 send a unicast wildcard request after acquiring a new neighbour. 1477 Additionally, a node MAY send a small number of multicast wildcard 1478 requests shortly after booting. Note however that doing that 1479 carelessly can cause serious congestion when a whole network is 1480 rebooted, especially on link layers with high per-packet overhead 1481 (e.g., IEEE 802.11). 1483 4. Protocol Encoding 1485 A Babel packet MUST be sent as the body of a UDP datagram, with 1486 network-layer hop count set to 1, destined to a well-known multicast 1487 address or to a unicast address, over IPv4 or IPv6; in the case of 1488 IPv6, these addresses are link-local. Both the source and 1489 destination UDP port are set to a well-known port number. A Babel 1490 packet MUST be silently ignored unless its source address is either a 1491 link-local IPv6 address or an IPv4 address belonging to the local 1492 network, and its source port is the well-known Babel port. It MAY be 1493 silently ignored if its destination address is a global IPv6 address. 1495 In order to minimise the number of packets being sent while avoiding 1496 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1497 the size of the packets it sends, up to the outgoing interface's MTU 1498 adjusted for lower-layer headers (28 octets for UDP over IPv4, 48 1499 octets for UDP over IPv6). It MUST NOT send packets larger than the 1500 attached interface's MTU adjusted for lower-layer headers or 512 1501 octets, whichever is larger, but not exceeding 2^16 - 1 adjusted for 1502 lower-layer headers. Every Babel speaker MUST be able to receive 1503 packets that are as large as any attached interface's MTU adjusted 1504 for lower-layer headers or 512 octets, whichever is larger. Babel 1505 packets MUST NOT be sent in IPv6 Jumbograms. 1507 In order to avoid global synchronisation of a Babel network and to 1508 aggregate multiple TLVs into large packets, a Babel node SHOULD 1509 buffer every TLV and delay sending a packet by a small, randomly 1510 chosen delay [JITTER]. In order to allow accurate computation of 1511 packet loss rates, this delay MUST NOT be larger than half the 1512 advertised Hello interval. 1514 4.1. Data Types 1516 4.1.1. Interval 1518 Relative times are carried as 16-bit values specifying a number of 1519 centiseconds (hundredths of a second). This allows times up to 1520 roughly 11 minutes with a granularity of 10ms, which should cover all 1521 reasonable applications of Babel. 1523 4.1.2. Router-Id 1525 A router-id is an arbitrary 8-octet value. A router-id MUST NOT 1526 consist of either all binary zeroes (0000000000000000 hexadecimal) or 1527 all binary ones ones (FFFFFFFFFFFFFFFF hexadecimal). 1529 4.1.3. Address 1531 Since the bulk of the protocol is taken by addresses, multiple ways 1532 of encoding addresses are defined. Additionally, a common subnet 1533 prefix may be omitted when multiple addresses are sent in a single 1534 packet -- this is known as address compression (Section 4.6.9). 1536 Address encodings: 1538 o AE 0: wildcard address. The value is 0 octets long. 1540 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1542 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1544 o AE 3: link-local IPv6 address. Compression is not allowed. The 1545 value is 8 octets long, a prefix of fe80::/64 is implied. 1547 The address family associated to an address encoding is either IPv4 1548 or IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 1549 and 3. 1551 4.1.4. Prefixes 1553 A network prefix is encoded just like a network address, but it is 1554 stored in the smallest number of octets that are enough to hold the 1555 significant bits (up to the prefix length). 1557 4.2. Packet Format 1559 A Babel packet consists of a 4-octet header, followed by a sequence 1560 of TLVs (the packet body), optionally followed by a second sequence 1561 of TLVs (the packet trailer). 1563 0 1 2 3 1564 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 1565 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1566 | Magic | Version | Body length | 1567 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1568 | Packet Body ... 1569 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1570 | Packet Trailer... 1571 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1573 Fields : 1575 Magic The arbitrary but carefully chosen value 42 (decimal); 1576 packets with a first octet different from 42 MUST be 1577 silently ignored. 1579 Version This document specifies version 2 of the Babel protocol. 1580 Packets with a second octet different from 2 MUST be 1581 silently ignored. 1583 Body length The length in octets of the body following the packet 1584 header (excluding the Magic, Version and Body length 1585 fields, and excluding the packet trailer). 1587 Packet Body The packet body; a sequence of TLVs. 1589 Packet Trailer The packet trailer; another sequence of TLVs. 1591 The packet body and trailer are both sequences of TLVs. The packet 1592 body is the normal place to store TLVs; the packet trailer only 1593 contains specialised TLVs that do not need to be protected by 1594 cryptographic security mechanisms. When parsing the trailer, the 1595 receiver MUST ignore any TLV unless its definition explicitly states 1596 that it is allowed to appear there. Among the TLVs defined in this 1597 document, only Pad1 and PadN are allowed in the trailer; since these 1598 TLVs are ignored in any case, an implementation MAY silently ignore 1599 the packet trailer without even parsing it, unless it implements at 1600 least one extension that defines TLVs that are allowed to appear in 1601 the trailer. 1603 4.3. TLV Format 1605 With the exception of Pad1, all TLVs have the following structure: 1607 0 1 2 3 1608 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 1609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1610 | Type | Length | Payload... 1611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1613 Fields : 1615 Type The type of the TLV. 1617 Length The length of the body, exclusive of the Type and Length 1618 fields. If the body is longer than the expected length of 1619 a given type of TLV, any extra data MUST be silently 1620 ignored. 1622 Payload The TLV payload, which consists of a body and, for selected 1623 TLV types, an optional list of sub-TLVs. 1625 TLVs with an unknown type value MUST be silently ignored. 1627 4.4. Sub-TLV Format 1629 Every TLV carries an explicit length in its header; however, most 1630 TLVs are self-terminating, in the sense that it is possible to 1631 determine the length of the body without reference to the explicit 1632 Length field. If a TLV has a self-terminating format, then it MAY 1633 allow a sequence of sub-TLVs to follow the body. 1635 Sub-TLVs have the same structure as TLVs. With the exception of 1636 PAD1, all TLVs have the following structure: 1638 0 1 2 3 1639 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 1640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1641 | Type | Length | Body... 1642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1644 Fields : 1646 Type The type of the sub-TLV. 1648 Length The length of the body, in octets, exclusive of the Type 1649 and Length fields. 1651 Body The sub-TLV body, the interpretation of which depends on 1652 both the type of the sub-TLV and the type of the TLV within 1653 which it is embedded. 1655 The most-significant bit of the sub-TLV type (the bit with value 80 1656 hexadecimal), called the mandatory bit, indicates how to handle 1657 unknown sub-TLVs. If the mandatory bit is not set, then an unknown 1658 sub-TLV MUST be silently ignored, and the rest of the TLV is 1659 processed normally. If the mandatory bit is set, then the whole 1660 enclosing TLV MUST be silently ignored (except for updating the 1661 parser state by a Router-Id, Next-Hop or Update TLV, see 1662 Section 4.6.7, Section 4.6.8, and Section 4.6.9). 1664 4.5. Parser state 1666 Babel uses a stateful parser: a TLV may refer to data from a previous 1667 TLV. The parser state consists of the following pieces of data: 1669 o for each address encoding that allows compression, the current 1670 default prefix; this is undefined at the start of the packet, and 1671 is updated by each Update TLV with the Prefix flag set 1672 (Section 4.6.9); 1674 o for each address family (IPv4 or IPv6), the current next-hop; this 1675 is the source address of the enclosing packet for the matching 1676 address family at the start of a packet, and is updated by each 1677 Next-Hop TLV (Section 4.6.8); 1679 o the current router-id; this is undefined at the start of the 1680 packet, and is updated by each Router-ID TLV (Section 4.6.7) and 1681 by each Update TLV with Router-Id flag set. 1683 Since the parser state must be identical across implementations, it 1684 is updated before checking for mandatory TLVs: parsing a TLV MUST 1685 update the parser state even if the TLV is otherwise ignored due to 1686 an unknown mandatory sub-TLV. 1688 None of the TLVs that modify the parser state are allowed in the 1689 packet trailer; hence, an implementation may choose to use a 1690 dedicated stateless parser to parse the packet trailer. 1692 4.6. Details of Specific TLVs 1694 4.6.1. Pad1 1696 0 1697 0 1 2 3 4 5 6 7 1698 +-+-+-+-+-+-+-+-+ 1699 | Type = 0 | 1700 +-+-+-+-+-+-+-+-+ 1702 Fields : 1704 Type Set to 0 to indicate a Pad1 TLV. 1706 This TLV is silently ignored on reception. It is allowed in the 1707 packet trailer. 1709 4.6.2. PadN 1711 0 1 2 3 1712 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 1713 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1714 | Type = 1 | Length | MBZ... 1715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1716 Fields : 1718 Type Set to 1 to indicate a PadN TLV. 1720 Length The length of the body, exclusive of the Type and Length 1721 fields. 1723 MBZ Must be zero, set to 0 on transmission. 1725 This TLV is silently ignored on reception. It is allowed in the 1726 packet trailer. 1728 4.6.3. Acknowledgment Request 1730 0 1 2 3 1731 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 1732 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1733 | Type = 2 | Length | Reserved | 1734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1735 | Nonce | Interval | 1736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1738 This TLV requests that the receiver send an Acknowledgment TLV within 1739 the number of centiseconds specified by the Interval field. 1741 Fields : 1743 Type Set to 2 to indicate an Acknowledgment Request TLV. 1745 Length The length of the body, exclusive of the Type and Length 1746 fields. 1748 Reserved Sent as 0 and MUST be ignored on reception. 1750 Nonce An arbitrary value that will be echoed in the receiver's 1751 Acknowledgment TLV. 1753 Interval A time interval in centiseconds after which the sender will 1754 assume that this packet has been lost. This MUST NOT be 0. 1755 The receiver MUST send an Acknowledgment TLV before this 1756 time has elapsed (with a margin allowing for propagation 1757 time). 1759 This TLV is self-terminating, and allows sub-TLVs. 1761 4.6.4. Acknowledgment 1763 0 1 2 3 1764 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 1765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1766 | Type = 3 | Length | Nonce | 1767 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1769 This TLV is sent by a node upon receiving an Acknowledgment Request. 1771 Fields : 1773 Type Set to 3 to indicate an Acknowledgment TLV. 1775 Length The length of the body, exclusive of the Type and Length 1776 fields. 1778 Nonce Set to the Nonce value of the Acknowledgment Request that 1779 prompted this Acknowledgment. 1781 Since nonce values are not globally unique, this TLV MUST be sent to 1782 a unicast address. 1784 This TLV is self-terminating, and allows sub-TLVs. 1786 4.6.5. Hello 1788 0 1 2 3 1789 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 1790 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1791 | Type = 4 | Length | Flags | 1792 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1793 | Seqno | Interval | 1794 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1796 This TLV is used for neighbour discovery and for determining a 1797 neighbour's reception cost. 1799 Fields : 1801 Type Set to 4 to indicate a Hello TLV. 1803 Length The length of the body, exclusive of the Type and Length 1804 fields. 1806 Flags The individual bits of this field specify special handling 1807 of this TLV (see below). 1809 Seqno If the Unicast flag is set, this is the value of the 1810 sending node's outgoing Unicast Hello seqno for this 1811 neighbour. Otherwise, it is the sending node's outgoing 1812 Multicast Hello seqno for this interface. 1814 Interval If non-zero, this is an upper bound, expressed in 1815 centiseconds, on the time after which the sending node will 1816 send a new scheduled Hello TLV with the same setting of the 1817 Unicast flag. If this is 0, then this Hello represents an 1818 unscheduled Hello, and doesn't carry any new information 1819 about times at which Hellos are sent. 1821 The Flags field is interpreted as follows: 1823 0 1 1824 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 1825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1826 |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| 1827 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1829 o U (Unicast) flag (8000 hexadecimal): if set, then this Hello 1830 represents a Unicast Hello, otherwise it represents a Multicast 1831 Hello; 1833 o X: all other bits MUST be sent as 0 and silently ignored on 1834 reception. 1836 Every time a Hello is sent, the corresponding seqno counter MUST be 1837 incremented. Since there is a single seqno counter for all the 1838 Multicast Hellos sent by a given node over a given interface, if the 1839 Unicast flag is not set, this TLV MUST be sent to all neighbors on 1840 this link, which can be achieved by sending to a multicast 1841 destination, or by sending multiple packets to the unicast addresses 1842 of all reachable neighbours. Conversely, if the Unicast flag is set, 1843 this TLV MUST be sent to a single neighbour, which can achieved by 1844 sending to a unicast destination. In order to avoid large 1845 discontinuities in link quality, multiple Hello TLVs SHOULD NOT be 1846 sent in the same packet. 1848 This TLV is self-terminating, and allows sub-TLVs. 1850 4.6.6. IHU 1851 0 1 2 3 1852 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 1853 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1854 | Type = 5 | Length | AE | Reserved | 1855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1856 | Rxcost | Interval | 1857 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1858 | Address... 1859 +-+-+-+-+-+-+-+-+-+-+-+- 1861 An IHU ("I Heard You") TLV is used for confirming bidirectional 1862 reachability and carrying a link's transmission cost. 1864 Fields : 1866 Type Set to 5 to indicate an IHU TLV. 1868 Length The length of the body, exclusive of the Type and Length 1869 fields. 1871 AE The encoding of the Address field. This should be 1 or 3 1872 in most cases. As an optimisation, it MAY be 0 if the TLV 1873 is sent to a unicast address, if the association is over a 1874 point-to-point link, or when bidirectional reachability is 1875 ascertained by means outside of the Babel protocol. 1877 Reserved Sent as 0 and MUST be ignored on reception. 1879 Rxcost The rxcost according to the sending node of the interface 1880 whose address is specified in the Address field. The value 1881 FFFF hexadecimal (infinity) indicates that this interface 1882 is unreachable. 1884 Interval An upper bound, expressed in centiseconds, on the time 1885 after which the sending node will send a new IHU; this MUST 1886 NOT be 0. The receiving node will use this value in order 1887 to compute a hold time for this symmetric association. 1889 Address The address of the destination node, in the format 1890 specified by the AE field. Address compression is not 1891 allowed. 1893 Conceptually, an IHU is destined to a single neighbour. However, IHU 1894 TLVs contain an explicit destination address, and MAY be sent to a 1895 multicast address, as this allows aggregation of IHUs destined to 1896 distinct neighbours into a single packet and avoids the need for an 1897 ARP or Neighbour Discovery exchange when a neighbour is not being 1898 used for data traffic. 1900 IHU TLVs with an unknown value in the AE field MUST be silently 1901 ignored. 1903 This TLV is self-terminating, and allows sub-TLVs. 1905 4.6.7. Router-Id 1907 0 1 2 3 1908 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 1909 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1910 | Type = 6 | Length | Reserved | 1911 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1912 | | 1913 + Router-Id + 1914 | | 1915 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1917 A Router-Id TLV establishes a router-id that is implied by subsequent 1918 Update TLVs. This TLV sets the router-id even if it is otherwise 1919 ignored due to an unknown mandatory sub-TLV. 1921 Fields : 1923 Type Set to 6 to indicate a Router-Id TLV. 1925 Length The length of the body, exclusive of the Type and Length 1926 fields. 1928 Reserved Sent as 0 and MUST be ignored on reception. 1930 Router-Id The router-id for routes advertised in subsequent Update 1931 TLVs. This MUST NOT consist of all zeroes or all ones. 1933 This TLV is self-terminating, and allows sub-TLVs. 1935 4.6.8. Next Hop 1937 0 1 2 3 1938 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 1939 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1940 | Type = 7 | Length | AE | Reserved | 1941 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1942 | Next hop... 1943 +-+-+-+-+-+-+-+-+-+-+-+- 1945 A Next Hop TLV establishes a next-hop address for a given address 1946 family (IPv4 or IPv6) that is implied in subsequent Update TLVs. 1948 This TLV sets up the next-hop for subsequent Update TLVs even if it 1949 is otherwise ignored due to an unknown mandatory sub-TLV. 1951 Fields : 1953 Type Set to 7 to indicate a Next Hop TLV. 1955 Length The length of the body, exclusive of the Type and Length 1956 fields. 1958 AE The encoding of the Address field. This SHOULD be 1 (IPv4) 1959 or 3 (link-local IPv6), and MUST NOT be 0. 1961 Reserved Sent as 0 and MUST be ignored on reception. 1963 Next hop The next-hop address advertised by subsequent Update TLVs, 1964 for this address family. 1966 When the address family matches the network-layer protocol that this 1967 packet is transported over, a Next Hop TLV is not needed: in the 1968 absence of a Next Hop TLV in a given address family, the next hop 1969 address is taken to be the source address of the packet. 1971 Next Hop TLVs with an unknown value for the AE field MUST be silently 1972 ignored. 1974 This TLV is self-terminating, and allows sub-TLVs. 1976 4.6.9. Update 1978 0 1 2 3 1979 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 1980 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1981 | Type = 8 | Length | AE | Flags | 1982 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1983 | Plen | Omitted | Interval | 1984 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1985 | Seqno | Metric | 1986 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1987 | Prefix... 1988 +-+-+-+-+-+-+-+-+-+-+-+- 1990 An Update TLV advertises or retracts a route. As an optimisation, it 1991 can optionally have the side effect of establishing a new implied 1992 router-id and a new default prefix. 1994 Fields : 1996 Type Set to 8 to indicate an Update TLV. 1998 Length The length of the body, exclusive of the Type and Length 1999 fields. 2001 AE The encoding of the Prefix field. 2003 Flags The individual bits of this field specify special handling 2004 of this TLV (see below). 2006 Plen The length of the advertised prefix. 2008 Omitted The number of octets that have been omitted at the 2009 beginning of the advertised prefix and that should be taken 2010 from a preceding Update TLV in the same address family with 2011 the Prefix flag set. 2013 Interval An upper bound, expressed in centiseconds, on the time 2014 after which the sending node will send a new update for 2015 this prefix. This MUST NOT be 0. The receiving node will 2016 use this value to compute a hold time for the route table 2017 entry. The value FFFF hexadecimal (infinity) expresses 2018 that this announcement will not be repeated unless a 2019 request is received (Section 3.8.2.3). 2021 Seqno The originator's sequence number for this update. 2023 Metric The sender's metric for this route. The value FFFF 2024 hexadecimal (infinity) means that this is a route 2025 retraction. 2027 Prefix The prefix being advertised. This field's size is 2028 (Plen/8 - Omitted) rounded upwards. 2030 The Flags field is interpreted as follows: 2032 0 1 2 3 4 5 6 7 2033 +-+-+-+-+-+-+-+-+ 2034 |P|R|X|X|X|X|X|X| 2035 +-+-+-+-+-+-+-+-+ 2037 o P (Prefix) flag (80 hexadecimal): if set, then this Update 2038 establishes a new default prefix for subsequent Update TLVs with a 2039 matching address encoding within the same packet, even if this TLV 2040 is otherwise ignored due to an unknown mandatory sub-TLV; 2042 o R (Router-Id) flag (40 hexadecimal): if set, then this TLV 2043 establishes a new default router-id for this TLV and subsequent 2044 Update TLVs in the same packet, even if this TLV is otherwise 2045 ignored due to an unknown mandatory sub-TLV. This router-id is 2046 computed from the first address of the advertised prefix as 2047 follows: 2049 * if the length of the address is 8 octets or more, then the new 2050 router-id is taken from the 8 last octets of the address; 2052 * if the length of the address is smaller than 8 octets, then the 2053 new router-id consists of the required number of zero octets 2054 followed by the address, i.e., the address is stored on the 2055 right of the router-id. For example, for an IPv4 address, the 2056 router-id consists of 4 octets of zeroes followed by the IPv4 2057 address. 2059 o X: all other bits MUST be sent as 0 and silently ignored on 2060 reception. 2062 The prefix being advertised by an Update TLV is computed as follows: 2064 o the first Omitted octets of the prefix are taken from the previous 2065 Update TLV with the Prefix flag set and the same address encoding, 2066 even if it was ignored due to an unknown mandatory sub-TLV; 2068 o the next (Plen/8 - Omitted) rounded upwards octets are taken from 2069 the Prefix field; 2071 o the remaining octets are set to 0. If AE is 3 (link-local IPv6), 2072 Omitted MUST be 0) 2074 If the Metric field is finite, the router-id of the originating node 2075 for this announcement is taken from the prefix advertised by this 2076 Update if the Router-Id flag is set, computed as described above. 2077 Otherwise, it is taken either from the preceding Router-Id packet, or 2078 the preceding Update packet with the Router-Id flag set, whichever 2079 comes last, even if that TLV is otherwise ignored due to an unknown 2080 mandatory sub-TLV. 2082 The next-hop address for this update is taken from the last preceding 2083 Next Hop TLV with a matching address family (IPv4 or IPv6) in the 2084 same packet even if it was otherwise ignored due to an unknown 2085 mandatory sub-TLV; if no such TLV exists, it is taken from the 2086 network-layer source address of this packet. 2088 If the metric field is FFFF hexadecimal, this TLV specifies a 2089 retraction. In that case, the router-id, next-hop and seqno are not 2090 used. AE MAY then be 0, in which case this Update retracts all of 2091 the routes previously advertised by the sending interface. If the 2092 metric is finite, AE MUST NOT be 0. If the metric is infinite and AE 2093 is 0, Plen and Omitted MUST both be 0. 2095 Update TLVs with an unknown value in the AE field MUST be silently 2096 ignored. 2098 This TLV is self-terminating, and allows sub-TLVs. 2100 4.6.10. Route Request 2102 0 1 2 3 2103 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 2104 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2105 | Type = 9 | Length | AE | Plen | 2106 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2107 | Prefix... 2108 +-+-+-+-+-+-+-+-+-+-+-+- 2110 A Route Request TLV prompts the receiver to send an update for a 2111 given prefix, or a full route table dump. 2113 Fields : 2115 Type Set to 9 to indicate a Route Request TLV. 2117 Length The length of the body, exclusive of the Type and Length 2118 fields. 2120 AE The encoding of the Prefix field. The value 0 specifies 2121 that this is a request for a full route table dump (a 2122 wildcard request). 2124 Plen The length of the requested prefix. 2126 Prefix The prefix being requested. This field's size is Plen/8 2127 rounded upwards. 2129 A Request TLV prompts the receiver to send an update message 2130 (possibly a retraction) for the prefix specified by the AE, Plen, and 2131 Prefix fields, or a full dump of its route table if AE is 0 (in which 2132 case Plen MUST be 0 and Prefix is of length 0). 2134 This TLV is self-terminating, and allows sub-TLVs. 2136 4.6.11. Seqno Request 2138 0 1 2 3 2139 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 2140 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2141 | Type = 10 | Length | AE | Plen | 2142 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2143 | Seqno | Hop Count | Reserved | 2144 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2145 | | 2146 + Router-Id + 2147 | | 2148 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2149 | Prefix... 2150 +-+-+-+-+-+-+-+-+-+-+ 2152 A Seqno Request TLV prompts the receiver to send an Update for a 2153 given prefix with a given sequence number, or to forward the request 2154 further if it cannot be satisfied locally. 2156 Fields : 2158 Type Set to 10 to indicate a Seqno Request TLV. 2160 Length The length of the body, exclusive of the Type and Length 2161 fields. 2163 AE The encoding of the Prefix field. This MUST NOT be 0. 2165 Plen The length of the requested prefix. 2167 Seqno The sequence number that is being requested. 2169 Hop Count The maximum number of times that this TLV may be forwarded, 2170 plus 1. This MUST NOT be 0. 2172 Reserved Sent as 0 and MUST be ignored on reception. 2174 Router-Id The Router-Id that is being requested. This MUST NOT 2175 consist of all zeroes or all ones. 2177 Prefix The prefix being requested. This field's size is Plen/8 2178 rounded upwards. 2180 A Seqno Request TLV prompts the receiving node to send a finite- 2181 metric Update for the prefix specified by the AE, Plen, and Prefix 2182 fields, with either a router-id different from what is specified by 2183 the Router-Id field, or a Seqno no less (modulo 2^16) than what is 2184 specified by the Seqno field. If this request cannot be satisfied 2185 locally, then it is forwarded according to the rules set out in 2186 Section 3.8.1.2. 2188 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 2189 be forwarded to a multicast address and MUST NOT be forwarded to more 2190 than one neighbour. A request MUST NOT be forwarded if its Hop Count 2191 field is 1. 2193 This TLV is self-terminating, and allows sub-TLVs. 2195 4.7. Details of specific sub-TLVs 2197 4.7.1. Pad1 2199 0 1 2 3 4 5 6 7 2200 +-+-+-+-+-+-+-+-+ 2201 | Type = 0 | 2202 +-+-+-+-+-+-+-+-+ 2204 Fields : 2206 Type Set to 0 to indicate a Pad1 sub-TLV. 2208 This sub-TLV is silently ignored on reception. It is allowed within 2209 any TLV that allows sub-TLVs. 2211 4.7.2. PadN 2213 0 1 2 3 2214 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 2215 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2216 | Type = 1 | Length | MBZ... 2217 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 2219 Fields : 2221 Type Set to 1 to indicate a PadN sub-TLV. 2223 Length The length of the body, in octets, exclusive of the Type 2224 and Length fields. 2226 MBZ Must be zero, set to 0 on transmission. 2228 This sub-TLV is silently ignored on reception. It is allowed within 2229 any TLV that allows sub-TLVs. 2231 5. IANA Considerations 2233 IANA has registered the UDP port number 6696, called "babel", for use 2234 by the Babel protocol. 2236 IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4 2237 multicast group 224.0.0.111 for use by the Babel protocol. 2239 IANA has created a registry called "Babel TLV Types". The values in 2240 this registry are not changed by this specification. 2242 IANA has created a registry called "Babel sub-TLV Types". Due to the 2243 addition of a Mandatory bit to the Babel protocol, the values in the 2244 "Babel sub-TLV Types" registry are amended as follows: 2246 +---------+-----------------------------------------+---------------+ 2247 | Type | Name | Reference | 2248 +---------+-----------------------------------------+---------------+ 2249 | 0 | Pad1 | this document | 2250 | | | | 2251 | 1 | PadN | this document | 2252 | | | | 2253 | 112-126 | Reserved for Experimental Use | this document | 2254 | | | | 2255 | 127 | Reserved for expansion of the type | this document | 2256 | | space | | 2257 | | | | 2258 | 240-254 | Reserved for Experimental Use | this document | 2259 | | | | 2260 | 255 | Reserved for expansion of the type | this document | 2261 | | space | | 2262 +---------+-----------------------------------------+---------------+ 2264 Existing assignments in the "Babel sub-TLV Types" registry in the 2265 range 2 to 111 are not changed by this specification. The values 224 2266 through 239, previously reserved for Experimental Use, are now 2267 unassigned. 2269 IANA has created a registry called "Babel Flags Values". IANA is 2270 instructed to rename this registry to "Babel Update Flags Values", 2271 with its contents unchanged. 2273 IANA is instructed to create a new registry called "Babel Hello Flags 2274 Values". The allocation policy for this registry is Specification 2275 Required [RFC8126]. The initial values in this registry are as 2276 follows: 2278 +------+------------+---------------+ 2279 | Bit | Name | Reference | 2280 +------+------------+---------------+ 2281 | 0 | Unicast | this document | 2282 | | | | 2283 | 1-15 | Unassigned | | 2284 +------+------------+---------------+ 2286 IANA is instructed to replace all references to RFCs 6126 and 7557 in 2287 all of the registries mentioned above by references to this document. 2289 6. Security Considerations 2291 As defined in this document, Babel is a completely insecure protocol. 2292 Any attacker can misdirect data traffic by advertising routes with a 2293 low metric or a high seqno. This issue can be solved either by a 2294 lower-layer security mechanism (e.g., link-layer security or IPsec), 2295 or by deploying a suitable authentication mechanism within Babel 2296 itself. There are currently two such mechanisms: Babel over DTLS 2297 [BABEL-DTLS] and HMAC-based authentication [BABEL-HMAC]. Both 2298 mechanisms ensure integrity of messages and prevent message replay, 2299 but only DTLS supports asymmetric keying and message confidentiality. 2300 HMAC is simpler and does not depend on DTLS, and therefore its use is 2301 RECOMMENDED whenever both mechanisms are applicable. 2303 The information that a Babel node announces to the whole routing 2304 domain is often sufficient to determine a mobile node's physical 2305 location with reasonable precision. The privacy issues that this 2306 causes can be mitigated somewhat by using randomly chosen router-ids 2307 and randomly chosen IP addresses, and changing them periodically. 2309 When carried over IPv6, Babel packets are ignored unless they are 2310 sent from a link-local IPv6 address; since routers don't forward 2311 link-local IPv6 packets, this provides protection against spoofed 2312 Babel packets being sent from the global Internet. No such natural 2313 protection exists when Babel packets are carried over IPv4. 2315 7. Acknowledgments 2317 A number of people have contributed text and ideas to this 2318 specification. The authors are particularly indebted to Matthieu 2319 Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke 2320 Hoiland-Jorgensen, Joao Sobrinho and Martin Vigoureux. Earlier 2321 versions of this document greatly benefited from the input of Joel 2322 Halpern. The address compression technique was inspired by 2323 [PACKETBB]. 2325 8. References 2327 8.1. Normative References 2329 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2330 Requirement Levels", BCP 14, RFC 2119, 2331 DOI 10.17487/RFC2119, March 1997. 2333 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2334 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2335 May 2017. 2337 8.2. Informative References 2339 [BABEL-DTLS] 2340 Decimo, A., Schinazi, D., and J. Chroboczek, "Babel 2341 Routing Protocol over Datagram Transport Layer Security", 2342 Internet Draft draft-ietf-babel-dtls-07, July 2019. 2344 [BABEL-HMAC] 2345 Do, C., Kolodziejak, W., and J. Chroboczek, "HMAC 2346 authentication for the Babel routing protocol", Internet 2347 Draft draft-ietf-babel-hmac-07, June 2019. 2349 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 2350 Sequenced Distance-Vector Routing (DSDV) for Mobile 2351 Computers", ACM SIGCOMM'94 Conference on Communications 2352 Architectures, Protocols and Applications 234-244, 1994. 2354 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 2355 Computations", IEEE/ACM Transactions on Networking 1:1, 2356 February 1993. 2358 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 2359 "EIGRP -- a Fast Routing Protocol Based on Distance 2360 Vectors", Proc. Interop 94, 1994. 2362 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 2363 high-throughput path metric for multi-hop wireless 2364 networks", Proc. MobiCom 2003, 2003. 2366 [IS-IS] "Information technology -- Telecommunications and 2367 information exchange between systems -- Intermediate 2368 System to Intermediate System intra-domain routeing 2369 information exchange protocol for use in conjunction with 2370 the protocol for providing the connectionless-mode network 2371 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 2373 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 2374 periodic routing messages", IEEE/ACM Transactions on 2375 Networking 2, 2, 122-136, April 1994. 2377 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2379 [PACKETBB] 2380 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2381 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 2382 Format", RFC 5444, February 2009. 2384 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2385 Writing an IANA Considerations Section in RFCs", BCP 26, 2386 RFC 8126, June 2017. 2388 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 2390 Appendix A. Cost and Metric Computation 2392 The strategy for computing link costs and route metrics is a local 2393 matter; Babel itself only requires that it comply with the conditions 2394 given in Section 3.4.3 and Section 3.5.2. Different nodes may use 2395 different strategies in a single network and may use different 2396 strategies on different interface types. This section describes the 2397 strategies used by the sample implementation of Babel. 2399 The sample implementation of Babel sends periodic Multicast Hellos, 2400 and never sends Unicast Hellos. It maintains statistics about the 2401 last 16 received Hello TLVs of each kind (Appendix A.1), computes 2402 costs by using the 2-out-of-3 strategy (Appendix A.2.1) on wired 2403 links, and ETX (Appendix A.2.2) on wireless links. It uses an 2404 additive algebra for metric computation (Appendix A.3.1). 2406 A.1. Maintaining Hello History 2408 For each neighbour, the sample implementation of Babel maintains two 2409 sets of Hello history, one for each kind of Hello, and an expected 2410 sequence number, one for Multicast and one for Unicast Hellos. Each 2411 Hello history is a vector of 16 bits, where a 1 value represents a 2412 received Hello, and a 0 value a missed Hello. For each kind of 2413 Hello, the expected sequence number, written ne, is the sequence 2414 number that is expected to be carried by the next received Hello from 2415 this neighbour. 2417 Whenever it receives a Hello packet of a given kind from a neighbour, 2418 a node compares the received sequence number nr for that kind of 2419 Hello with its expected sequence number ne. Depending on the outcome 2420 of this comparison, one of the following actions is taken: 2422 o if the two differ by more than 16 (modulo 2^16), then the sending 2423 node has probably rebooted and lost its sequence number; the whole 2424 associated neighbour table entry is flushed and a new one is 2425 created; 2427 o otherwise, if the received nr is smaller (modulo 2^16) than the 2428 expected sequence number ne, then the sending node has increased 2429 its Hello interval without us noticing; the receiving node removes 2430 the last (ne - nr) entries from this neighbour's Hello history (we 2431 "undo history"); 2433 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 2434 node has decreased its Hello interval, and some Hellos were lost; 2435 the receiving node adds (nr - ne) 0 bits to the Hello history (we 2436 "fast-forward"). 2438 The receiving node then appends a 1 bit to the Hello history and sets 2439 ne to (nr + 1). If the Interval field of the received Hello is not 2440 zero, it resets the neighbour's hello timer to 1.5 times the 2441 advertised Interval (the extra margin allows for delay due to 2442 jitter). 2444 Whenever either Hello timer associated to a neighbour expires, the 2445 local node adds a 0 bit to this neighbour's Hello history, and 2446 increments the expected Hello number. If both Hello histories are 2447 empty (they contain 0 bits only), the neighbour entry is flushed; 2448 otherwise, the relevant hello timer is reset to the value advertised 2449 in the last Hello of that kind received from this neighbour (no extra 2450 margin is necessary in this case, since jitter was already taken into 2451 account when computing the timeout that has just expired). 2453 A.2. Cost Computation 2455 This section discusses how to compute costs based on Hello history. 2457 A.2.1. k-out-of-j 2459 K-out-of-j link sensing is suitable for wired links that are either 2460 up, in which case they only occasionally drop a packet, or down, in 2461 which case they drop all packets. 2463 The k-out-of-j strategy is parameterised by two small integers k and 2464 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 2465 1. A node keeps a history of the last j hellos; if k or more of 2466 those have been correctly received, the link is assumed to be up, and 2467 the rxcost is set to K; otherwise, the link is assumed to be down, 2468 and the rxcost is set to infinity. 2470 Since Babel supports two kinds of Hellos, a Babel node performs k- 2471 out-of-j twice for each neighbour, once on the Unicast and once on 2472 the Multicast Hello history. If either of the instances of k-out- 2473 of-j indicates that the link is up, then the link is assumed to be 2474 up, and the rxcost is set to K; if both instances indicate that the 2475 link is down, then the link is assumed to be down, and the rxcost is 2476 set to infinity. In other words, the resulting rxcost is the minimum 2477 of the rxcosts yielded by the two instances of k-out-of-j link 2478 sensing. 2480 The cost of a link performing k-out-of-j link sensing is defined as 2481 follows: 2483 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 2485 o cost = txcost otherwise. 2487 A.2.2. ETX 2489 Unlike wired links, which are bimodal (either up or down), wireless 2490 links exhibit continuous variation of the link quality. Naive 2491 application of hop-count routing in networks that use wireless links 2492 for transit tends to select long, lossy links in preference to 2493 shorter, lossless links, which can dramatically reduce throughput. 2494 For that reason, a routing protocol designed to support wireless 2495 links must perform some form of link-quality estimation. 2497 ETX [ETX] is a simple link-quality estimation algorithm that is 2498 designed to work well with the IEEE 802.11 MAC. By default, the 2499 IEEE 802.11 MAC performs ARQ and rate adaptation on unicast frames, 2500 but not on multicast frames, which are sent at a fixed rate with no 2501 ARQ; therefore, measuring the loss rate of multicast frames yields a 2502 useful estimate of a link's quality. 2504 A node performing ETX link quality estimation uses a neighbour's 2505 Multicast Hello history to compute an estimate, written beta, of the 2506 probability that a Hello TLV is successfully received. Beta can be 2507 computed as the fraction of 1 bits within a small number (say, 6) of 2508 the most recent entries in the Multicast Hello history, or it can be 2509 an exponential average, or some combination of both approaches. 2511 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2512 successfully sending a Hello TLV. The cost is then computed by 2514 cost = 256/(alpha * beta) 2516 or, equivalently, 2517 cost = (MAX(txcost, 256) * rxcost) / 256. 2519 Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast 2520 frames do not provide a useful measure of link quality, and therefore 2521 ETX ignores the Unicast Hello history. Thus, a node performing ETX 2522 link-quality estimation will not route through neighbouring nodes 2523 unless they send periodic Multicast Hellos (possibly in addition to 2524 Unicast Hellos). 2526 A.3. Metric Computation 2528 As described in Section 3.5.2, the metric advertised by a neighbour 2529 is combined with the link cost to yield a metric. 2531 A.3.1. Additive Metrics 2533 The simplest approach for obtaining a monotonic, left-distributive 2534 metric is to define the metric of a route as the sum of the costs of 2535 the component links. More formally, if a neighbour advertises a 2536 route with metric m over a link with cost c, then the resulting route 2537 has metric M(c, m) = c + m. 2539 A multiplicative metric can be converted into an additive one by 2540 taking the logarithm (in some suitable base) of the link costs. 2542 A.3.2. External Sources of Willingness 2544 A node may want to vary its willingness to forward packets by taking 2545 into account information that is external to the Babel protocol, such 2546 as the monetary cost of a link, the node's battery status, CPU load, 2547 etc. This can be done by adding to every route's metric a value k 2548 that depends on the external data. For example, if a battery-powered 2549 node receives an update with metric m over a link with cost c, it 2550 might compute a metric M(c, m) = k + c + m, where k depends on the 2551 battery status. 2553 In order to preserve strict monotonicity (Section 3.5.2), the value k 2554 must be greater than -c. 2556 Appendix B. Constants 2558 The choice of time constants is a trade-off between fast detection of 2559 mobility events and protocol overhead. Two implementations of Babel 2560 with different time constants will interoperate, although the 2561 resulting convergence time will most likely be dictated by the slower 2562 of the two. 2564 Experience with the sample implementation of Babel indicates that the 2565 Hello interval is the most important time constant: a mobility event 2566 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2567 on triggered updates and explicit requests, the Update interval only 2568 has an effect on the time it takes for accurate metrics to be 2569 propagated after variations in link costs too small to trigger an 2570 unscheduled update or in the presence of packet loss. 2572 At the time of writing, the sample implementation of Babel uses the 2573 following default values: 2575 Multicast Hello Interval: 4 seconds. 2577 IHU Interval: the advertised IHU interval is always 3 times the 2578 Multicast Hello interval. IHUs are actually sent with each Hello 2579 on lossy links (as determined from the Hello history), but only 2580 with every third Multicast Hello on lossless links. 2582 Unicast Hello Interval: the sample implementation never sends 2583 scheduled Unicast Hellos; 2585 Update Interval: 4 times the Multicast Hello interval. 2587 IHU Hold Time: 3.5 times the advertised IHU interval. 2589 Route Expiry Time: 3.5 times the advertised update interval. 2591 Source GC time: 3 minutes. 2593 Request timeout: initially 2 seconds, doubled every time a request 2594 is resent, up to a maximum of three times. 2596 The amount of jitter applied to a packet depends on whether it 2597 contains any urgent TLVs or not (Section 3.1). Urgent triggered 2598 updates and urgent requests are delayed by no more than 200ms; 2599 acknowledgments, by no more than the associated deadline; and other 2600 TLVs by no more than one-half the Multicast Hello interval. 2602 Appendix C. Considerations for protocol extensions 2604 Babel is an extensible protocol, and this document defines a number 2605 of mechanisms that can be used to extend the protocol in a backwards 2606 compatible manner: 2608 o increasing the version number in the packet header; 2610 o defining new TLVs; 2611 o defining new sub-TLVs (with or without the mandatory bit set); 2613 o defining new AEs; 2615 o using the packet trailer. 2617 This appendix is intended to guide designers of protocol extensions 2618 in chosing a particular encoding. 2620 The version number in the Babel header should only be increased if 2621 the new version is not backwards compatible with the original 2622 protocol. 2624 In many cases, an extension could be implemented either by defining a 2625 new TLV, or by adding a new sub-TLV to an existing TLV. For example, 2626 an extension whose purpose is to attach additional data to route 2627 updates can be implemented either by creating a new "enriched" Update 2628 TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by 2629 adding a mandatory sub-TLV. 2631 The various encodings are treated differently by implementations that 2632 do not understand the extension. In the case of a new TLV or of a 2633 sub-TLV with the mandatory bit set, the whole TLV is ignored by 2634 implementations that do not implement the extension, while in the 2635 case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, 2636 and only the unknown sub-TLV is silently ignored. Therefore, a non- 2637 mandatory sub-TLV should be used by extensions that extend the Update 2638 in a compatible manner (the extension data may be silently ignored), 2639 while a mandatory sub-TLV or a new TLV must be used by extensions 2640 that make incompatible extensions to the meaning of the TLV (the 2641 whole TLV must be thrown away if the extension data is not 2642 understood). 2644 Experience shows that the need for additional data tends to crop up 2645 in the most unexpected places. Hence, it is recommended that 2646 extensions that define new TLVs should make them self-terminating, 2647 and allow attaching sub-TLVs to them. 2649 Adding a new AE is essentially equivalent to adding a new TLV: Update 2650 TLVs with an unknown AE are ignored, just like unknown TLVs. 2651 However, adding a new AE is more involved than adding a new TLV, 2652 since it creates a new set of compression state. Additionally, since 2653 the Next Hop TLV creates state specific to a given address family, as 2654 opposed to a given AE, a new AE for a previously defined address 2655 family must not be used in the Next Hop TLV if backwards 2656 compatibility is required. A similar issue arises with Update TLVs 2657 with unknown AEs establishing a new router-id (due to the Router-Id 2658 flag being set). Therefore, defining new AEs must be done with care 2659 if compatibility with unextended implementations is required. 2661 The packet trailer is intended to carry cryptographic signatures that 2662 only cover the packet body; storing the cryptographic signatures in 2663 the packet trailer avoids clearing the signature before computing a 2664 hash of the packet body, and makes it possible to check a 2665 cryptographic signature before running the full, stateful TLV parser. 2666 Hence, only TLVs that don't need to be protected by cryptographic 2667 security protocols should be allowed in the packet trailer. Any such 2668 TLVs should be easy to parse, and in particular should not require 2669 stateful parsing. 2671 Appendix D. Stub Implementations 2673 Babel is a fairly economic protocol. Updates take between 12 and 40 2674 octets per destination, depending on the address family and how 2675 successful compression is; in a double-stack flat network, an average 2676 of less than 24 octets per update is typical. The route table 2677 occupies about 35 octets per IPv6 entry. To put these values into 2678 perspective, a single full-size Ethernet frame can carry some 65 2679 route updates, and a megabyte of memory can contain a 20000-entry 2680 route table and the associated source table. 2682 Babel is also a reasonably simple protocol. The sample 2683 implementation consists of less than 12 000 lines of C code, and it 2684 compiles to less than 120 kB of text on a 32-bit CISC architecture; 2685 about half of this figure is due to protocol extensions and user- 2686 interface code. 2688 Nonetheless, in some very constrained environments, such as PDAs, 2689 microwave ovens, or abacuses, it may be desirable to have subset 2690 implementations of the protocol. 2692 There are many different definitions of a stub router, but for the 2693 needs of this section a stub implementation of Babel is one that 2694 announces one or more directly attached prefixes into a Babel network 2695 but doesn't reannounce any routes that it has learnt from its 2696 neighbours. It may either maintain a full routing table, or simply 2697 select a default gateway amongst any one of its neighbours that 2698 announces a default route. Since a stub implementation never 2699 forwards packets except from or to directly attached links, it cannot 2700 possibly participate in a routing loop, and hence it need not 2701 evaluate the feasibility condition or maintain a source table. 2703 No matter how primitive, a stub implementation MUST parse sub-TLVs 2704 attached to any TLVs that it understands and check the mandatory bit. 2705 It MUST answer acknowledgment requests and MUST participate in the 2706 Hello/IHU protocol. It MUST also be able to reply to seqno requests 2707 for routes that it announces and SHOULD be able to reply to route 2708 requests. 2710 Experience shows that an IPv6-only stub implementation of Babel can 2711 be written in less than 1000 lines of C code and compile to 13 kB of 2712 text on 32-bit CISC architecture. 2714 Appendix E. Software Availability 2716 The sample implementation of Babel is available from 2717 . 2719 Appendix F. Changes from previous versions 2721 F.1. Changes since RFC 6126 2723 o Changed UDP port number to 6696. 2725 o Consistently use router-id rather than id. 2727 o Clarified that the source garbage collection timer is reset after 2728 sending an update even if the entry was not modified. 2730 o In section "Seqno Requests", fixed an erroneous "route request". 2732 o In the description of the Seqno Request TLV, added the description 2733 of the Router-Id field. 2735 o Made router-ids all-0 and all-1 forbidden. 2737 F.2. Changes since draft-ietf-babel-rfc6126bis-00 2739 o Added security considerations. 2741 F.3. Changes since draft-ietf-babel-rfc6126bis-01 2743 o Integrated the format of sub-TLVs. 2745 o Mentioned for each TLV whether it supports sub-TLVs. 2747 o Added Appendix C. 2749 o Added a mandatory bit in sub-TLVs. 2751 o Changed compression state to be per-AF rather than per-AE. 2753 o Added implementation hint for the routing table. 2755 o Clarified how router-ids are computed when bit 0x40 is set in 2756 Updates. 2758 o Relaxed the conditions for sending requests, and tightened the 2759 conditions for forwarding requests. 2761 o Clarified that neighbours should be acquired at some point, but it 2762 doesn't matter when. 2764 F.4. Changes since draft-ietf-babel-rfc6126bis-02 2766 o Added Unicast Hellos. 2768 o Added unscheduled (interval-less) Hellos. 2770 o Changed Appendix A to consider Unicast and unscheduled Hellos. 2772 o Changed Appendix B to agree with the reference implementation. 2774 o Added optional algorithm to avoid the hold time. 2776 o Changed the table of pending seqno requests to be indexed by 2777 router-id in addition to prefixes. 2779 o Relaxed the route acquisition algorithm. 2781 o Replaced minimal implementations by stub implementations. 2783 o Added acknowledgments section. 2785 F.5. Changes since draft-ietf-babel-rfc6126bis-03 2787 o Clarified that all the data structures are conceptual. 2789 o Made sending and receiving Multicast Hellos a SHOULD, avoids 2790 expressing any opinion about Unicast Hellos. 2792 o Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4). 2794 o Made hold-time into a SHOULD rather than MUST. 2796 o Clarified that Seqno Requests are for a finite-metric Update. 2798 o Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV 2799 that allows sub-TLVs. 2801 o Updated IANA Considerations. 2803 o Updated Security Considerations. 2805 o Renamed routing table back to route table. 2807 o Made buffering outgoing updates a SHOULD. 2809 o Weakened advice to use modified EUI-64 in router-ids. 2811 o Added information about sending requests to Appendix B. 2813 o A number of minor wording changes and clarifications. 2815 F.6. Changes since draft-ietf-babel-rfc6126bis-03 2817 Minor editorial changes. 2819 F.7. Changes since draft-ietf-babel-rfc6126bis-04 2821 o Renamed isotonicity to left-distributivity. 2823 o Minor clarifications to unicast hellos. 2825 o Updated requirements boilerplate to RFC 8174. 2827 o Minor editorial changes. 2829 F.8. Changes since draft-ietf-babel-rfc6126bis-05 2831 o Added information about the packet trailer, now that it is used by 2832 draft-ietf-babel-hmac. 2834 F.9. Changes since draft-ietf-babel-rfc6126bis-06 2836 o Added references to security documents. 2838 F.10. Changes since draft-ietf-babel-rfc6126bis-07 2840 o Added list of obsoleted drafts to the abstract. 2842 o Updated references. 2844 F.11. Changes since draft-ietf-babel-rfc6126bis-08 2846 o Added recommendation that route selection should not take seqnos 2847 into account. 2849 F.12. Changes since draft-ietf-babel-rfc6126bis-09 2851 o Editorial changes only. 2853 F.13. Changes since draft-ietf-babel-rfc6126bis-10 2855 o Editorial changes only. 2857 F.14. Changes since draft-ietf-babel-rfc6126bis-11 2859 o Added recommendation that control traffic should be carried over 2860 IPv6 only. 2862 Authors' Addresses 2864 Juliusz Chroboczek 2865 IRIF, University of Paris-Diderot 2866 Case 7014 2867 75205 Paris Cedex 13 2868 France 2870 Email: jch@irif.fr 2872 David Schinazi 2873 Google LLC 2874 1600 Amphitheatre Parkway 2875 Mountain View, California 94043 2876 USA 2878 Email: dschinazi.ietf@gmail.com