idnits 2.17.1 draft-ietf-babel-rfc6126bis-19.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 non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == 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 6, 2020) is 1359 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 (-12) exists of draft-ietf-babel-hmac-10 ** Obsolete normative reference: RFC 793 (Obsoleted by RFC 9293) == Outdated reference: A later version (-07) exists of draft-ietf-babel-rtt-extension-00 == Outdated reference: A later version (-08) exists of draft-ietf-babel-source-specific-05 -- Obsolete informational reference (is this intentional?): RFC 6126 (Obsoleted by RFC 8966) -- Obsolete informational reference (is this intentional?): RFC 7298 (Obsoleted by RFC 8967) -- Obsolete informational reference (is this intentional?): RFC 7557 (Obsoleted by RFC 8966) Summary: 1 error (**), 0 flaws (~~), 6 warnings (==), 5 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 7, 2021 August 6, 2020 8 The Babel Routing Protocol 9 draft-ietf-babel-rfc6126bis-19 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 7, 2021. 35 Copyright Notice 37 Copyright (c) 2020 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 . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . . . . . 11 64 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 12 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 . . . . . . . . . . . . . . . . . . 18 70 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 21 71 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 25 72 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 26 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 and encoding of updates . . . . . . . . . . 35 80 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 37 81 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 48 82 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 49 83 6. Security Considerations . . . . . . . . . . . . . . . . . . . 52 84 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 53 85 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 86 8.1. Normative References . . . . . . . . . . . . . . . . . . 53 87 8.2. Informative References . . . . . . . . . . . . . . . . . 54 88 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 56 89 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 56 90 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 57 91 A.3. Route selection and hysteresis . . . . . . . . . . . . . 59 92 Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 59 93 Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 60 94 Appendix D. Considerations for protocol extensions . . . . . . . 61 95 Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 63 96 Appendix F. Compatibility with previous versions . . . . . . . . 64 97 Appendix G. Changes from previous versions . . . . . . . . . . . 65 98 G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 65 99 G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 65 100 G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 65 101 G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 66 102 G.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 66 103 G.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 67 104 G.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 67 105 G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 67 106 G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 67 107 G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 67 108 G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 67 109 G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 67 110 G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 68 111 G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 68 112 G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 68 113 G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 68 114 G.17. Changes since draft-ietf-babel-rfc6126bis-14 . . . . . . 69 115 G.18. Changes since draft-ietf-babel-rfc6126bis-15 . . . . . . 69 116 G.19. Changes since draft-ietf-babel-rfc6126bis-16 . . . . . . 69 117 G.20. Changes since draft-ietf-babel-rfc6126bis-17 . . . . . . 69 118 G.21. Changes since draft-ietf-babel-rfc6126bis-18 . . . . . . 69 119 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 69 121 1. Introduction 123 Babel is a loop-avoiding distance-vector routing protocol that is 124 designed to be robust and efficient both in networks using prefix- 125 based routing and in networks using flat routing ("mesh networks"), 126 and both in relatively stable wired networks and in highly dynamic 127 wireless networks. This document describes the Babel routing 128 protocol, and obsoletes [RFC6126] and [RFC7557]. 130 1.1. Features 132 The main property that makes Babel suitable for unstable networks is 133 that, unlike naive distance-vector routing protocols [RIP], it 134 strongly limits the frequency and duration of routing pathologies 135 such as routing loops and black-holes during reconvergence. Even 136 after a mobility event is detected, a Babel network usually remains 137 loop-free. Babel then quickly reconverges to a configuration that 138 preserves the loop-freedom and connectedness of the network, but is 139 not necessarily optimal; in many cases, this operation requires no 140 packet exchanges at all. Babel then slowly converges, in a time on 141 the scale of minutes, to an optimal configuration. This is achieved 142 by using sequenced routes, a technique pioneered by Destination- 143 Sequenced Distance-Vector routing [DSDV]. 145 More precisely, Babel has the following properties: 147 o when every prefix is originated by at most one router, Babel never 148 suffers from routing loops; 150 o when a single prefix is originated by multiple routers, Babel may 151 occasionally create a transient routing loop for this particular 152 prefix; this loop disappears in time proportional to the loop's 153 diameter, and never again (up to an arbitrary garbage-collection 154 (GC) time) will the routers involved participate in a routing loop 155 for the same prefix; 157 o assuming bounded packet loss rates, any routing black-holes that 158 may appear after a mobility event are corrected in a time at most 159 proportional to the network's diameter. 161 Babel has provisions for link quality estimation and for fairly 162 arbitrary metrics. When configured suitably, Babel can implement 163 shortest-path routing, or it may use a metric based, for example, on 164 measured packet loss. 166 Babel nodes will successfully establish an association even when they 167 are configured with different parameters. For example, a mobile node 168 that is low on battery may choose to use larger time constants (hello 169 and update intervals, etc.) than a node that has access to wall 170 power. Conversely, a node that detects high levels of mobility may 171 choose to use smaller time constants. The ability to build such 172 heterogeneous networks makes Babel particularly adapted to the 173 unmanaged or wireless environment. 175 Finally, Babel is a hybrid routing protocol, in the sense that it can 176 carry routes for multiple network-layer protocols (IPv4 and IPv6), 177 regardless of which protocol the Babel packets are themselves being 178 carried over. 180 1.2. Limitations 182 Babel has two limitations that make it unsuitable for use in some 183 environments. First, Babel relies on periodic routing table updates 184 rather than using a reliable transport; hence, in large, stable 185 networks it generates more traffic than protocols that only send 186 updates when the network topology changes. In such networks, 187 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 188 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 189 suitable. 191 Second, unless the second algorithm described in Section 3.5.4 is 192 implemented, Babel does impose a hold time when a prefix is 193 retracted. While this hold time does not apply to the exact prefix 194 being retracted, and hence does not prevent fast reconvergence should 195 it become available again, it does apply to any shorter prefix that 196 covers it. This may make those implementations of Babel that do not 197 implement the optional algorithm described in Section 3.5.4 198 unsuitable for use in networks that implement automatic prefix 199 aggregation. 201 1.3. Specification of Requirements 203 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 204 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 205 "OPTIONAL" in this document are to be interpreted as described in BCP 206 14 [RFC2119] [RFC8174] when, and only when, they appear in all 207 capitals, as shown here. 209 2. Conceptual Description of the Protocol 211 Babel is a loop-avoiding distance vector protocol: it is based on the 212 Bellman-Ford algorithm, just like the venerable RIP [RIP], but 213 includes a number of refinements that either prevent loop formation 214 altogether, or ensure that a loop disappears in a timely manner and 215 doesn't form again. 217 Conceptually, Bellman-Ford is executed in parallel for every source 218 of routing information (destination of data traffic). In the 219 following discussion, we fix a source S; the reader will recall that 220 the same algorithm is executed for all sources. 222 2.1. Costs, Metrics and Neighbourship 224 For every pair of neighbouring nodes A and B, Babel computes an 225 abstract value known as the cost of the link from A to B, written 226 C(A, B). Given a route between any two (not necessarily 227 neighbouring) nodes, the metric of the route is the sum of the costs 228 of all the links along the route. The goal of the routing algorithm 229 is to compute, for every source S, the tree of routes of lowest 230 metric to S. 232 Costs and metrics need not be integers. In general, they can be 233 values in any algebra that satisfies two fairly general conditions 234 (Section 3.5.2). 236 A Babel node periodically sends Hello messages to all of its 237 neighbours; it also periodically sends an IHU ("I Heard You") message 238 to every neighbour from which it has recently heard a Hello. From 239 the information derived from Hello and IHU messages received from its 240 neighbour B, a node A computes the cost C(A, B) of the link from A to 241 B. 243 2.2. The Bellman-Ford Algorithm 245 Every node A maintains two pieces of data: its estimated distance to 246 S, written D(A), and its next-hop router to S, written NH(A). 247 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 249 Periodically, every node B sends to all of its neighbours a route 250 update, a message containing D(B). When a neighbour A of B receives 251 the route update, it checks whether B is its selected next hop; if 252 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 253 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 254 its current value of D(A). If that value is smaller, meaning that 255 the received update advertises a route that is better than the 256 currently selected route, then NH(A) is set to B, and D(A) is set to 257 C(A, B) + D(B). 259 A number of refinements to this algorithm are possible, and are used 260 by Babel. In particular, convergence speed may be increased by 261 sending unscheduled "triggered updates" whenever a major change in 262 the topology is detected, in addition to the regular, scheduled 263 updates. Additionally, a node may maintain a number of alternate 264 routes, which are being advertised by neighbours other than its 265 selected neighbour, and which can be used immediately if the selected 266 route were to fail. 268 2.3. Transient Loops in Bellman-Ford 270 It is well known that a naive application of Bellman-Ford to 271 distributed routing can cause transient loops after a topology 272 change. Consider for example the following topology: 274 B 275 1 /| 276 1 / | 277 S --- A |1 278 \ | 279 1 \| 280 C 282 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 284 Suppose now that the link between S and A fails: 286 B 287 1 /| 288 / | 289 S A |1 290 \ | 291 1 \| 292 C 294 When it detects the failure of the link, A switches its next hop to B 295 (which is still advertising a route to S with metric 2), and 296 advertises a metric equal to 3, and then advertises a new route with 297 metric 3. This process of nodes changing selected neighbours and 298 increasing their metric continues until the advertised metric reaches 299 "infinity", a value larger than all the metrics that the routing 300 protocol is able to carry. 302 2.4. Feasibility Conditions 304 Bellman-Ford is a very robust algorithm: its convergence properties 305 are preserved when routers delay route acquisition or when they 306 discard some updates. Babel routers discard received route 307 announcements unless they can prove that accepting them cannot 308 possibly cause a routing loop. 310 More formally, we define a condition over route announcements, known 311 as the "feasibility condition", that guarantees the absence of 312 routing loops whenever all routers ignore route updates that do not 313 satisfy the feasibility condition. In effect, this makes Bellman- 314 Ford into a family of routing algorithms, parameterised by the 315 feasibility condition. 317 Many different feasibility conditions are possible. For example, BGP 318 can be modelled as being a distance-vector protocol with a (rather 319 drastic) feasibility condition: a routing update is only accepted 320 when the receiving node's AS number is not included in the update's 321 AS-Path attribute (note that BGP's feasibility condition does not 322 ensure the absence of transient "micro-loops" during reconvergence). 324 Another simple feasibility condition, used in the Destination- 325 Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the 326 Ad hoc On-Demand Distance Vector (AODV) protocol [RFC3561], stems 327 from the following observation: a routing loop can only arise after a 328 router has switched to a route with a larger metric than the route 329 that it had previously selected. Hence, one may define that a route 330 is feasible when its metric at the local node would be no larger than 331 the metric of the currently selected route, i.e., an announcement 332 carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A). 333 If all routers obey this constraint, then the metric at every router 334 is nonincreasing, and the following invariant is always preserved: if 335 A has selected B as its next hop, then D(B) < D(A), which implies 336 that the forwarding graph is loop-free. 338 Babel uses a slightly more refined feasibility condition, derived 339 from EIGRP [DUAL]. Given a router A, define the feasibility distance 340 of A, written FD(A), as the smallest metric that A has ever 341 advertised for S to any of its neighbours. An update sent by a 342 neighbour B of A is feasible when the metric D(B) advertised by B is 343 strictly smaller than A's feasibility distance, i.e., when D(B) < 344 FD(A). 346 It is easy to see that this latter condition is no more restrictive 347 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 348 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 349 Suppose now that A receives a DSDV-feasible update that advertises a 350 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 351 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 353 To see that it is strictly less restrictive, consider the following 354 diagram, where A has selected the route through B, and D(A) = FD(A) = 355 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 356 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 357 the currently selected route: 359 B 360 1 / \ 1 361 / \ 362 S A 363 \ / 364 1 \ / 4 365 C 367 To show that this feasibility condition still guarantees loop- 368 freedom, recall that at the time when A accepts an update from B, the 369 metric D(B) announced by B is no smaller than FD(B); since it is 370 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 371 property is preserved both when A sends updates and when it picks a 372 different next hop, it remains true at all times, which ensures that 373 the forwarding graph has no loops. 375 2.5. Solving Starvation: Sequencing Routes 377 Obviously, the feasibility conditions defined above cause starvation 378 when a router runs out of feasible routes. Consider the following 379 diagram, where both A and B have selected the direct route to S: 381 A 382 1 /| D(A) = 1 383 / | FD(A) = 1 384 S |1 385 \ | D(B) = 2 386 2 \| FD(B) = 2 387 B 389 Suppose now that the link between A and S breaks: 391 A 392 | 393 | FD(A) = 1 394 S |1 395 \ | D(B) = 2 396 2 \| FD(B) = 2 397 B 399 The only route available from A to S, the one that goes through B, is 400 not feasible: A suffers from spurious starvation. At that point, the 401 whole subtree suffering from starvation must be reset, which is 402 essentially what EIGRP does when it performs a global synchronisation 403 of all the routers in the starving subtree (the "active" phase of 404 EIGRP). 406 Babel reacts to starvation in a less drastic manner, by using 407 sequenced routes, a technique introduced by DSDV and adopted by AODV. 408 In addition to a metric, every route carries a sequence number, a 409 nondecreasing integer that is propagated unchanged through the 410 network and is only ever incremented by the source; a pair (s, m), 411 where s is a sequence number and m a metric, is called a distance. 413 A received update is feasible when either it is more recent than the 414 feasibility distance maintained by the receiving node, or it is 415 equally recent and the metric is strictly smaller. More formally, if 416 FD(A) = (s, m), then an update carrying the distance (s', m') is 417 feasible when either s' > s, or s = s' and m' < m. 419 Assuming the sequence number of S is 137, the diagram above becomes: 421 A 422 | 423 | FD(A) = (137, 1) 424 S |1 425 \ | D(B) = (137, 2) 426 2 \| FD(B) = (137, 2) 427 B 429 After S increases its sequence number, and the new sequence number is 430 propagated to B, we have: 432 A 433 | 434 | FD(A) = (137, 1) 435 S |1 436 \ | D(B) = (138, 2) 437 2 \| FD(B) = (138, 2) 438 B 440 at which point the route through B becomes feasible again. 442 Note that while sequence numbers are used for determining 443 feasibility, they are not used in route selection: a node ignores the 444 sequence number when selecting the best route to a given destination 445 (Section 3.6). Doing otherwise would cause route oscillation while a 446 sequence number propagates through the network, and might even cause 447 persistent blackholes with some exotic metrics. 449 2.6. Requests 451 In DSDV, the sequence number of a source is increased periodically. 452 A route becomes feasible again after the source increases its 453 sequence number, and the new sequence number is propagated through 454 the network, which may, in general, require a significant amount of 455 time. 457 Babel takes a different approach. When a node detects that it is 458 suffering from a potentially spurious starvation, it sends an 459 explicit request to the source for a new sequence number. This 460 request is forwarded hop by hop to the source, with no regard to the 461 feasibility condition. Upon receiving the request, the source 462 increases its sequence number and broadcasts an update, which is 463 forwarded to the requesting node. 465 Note that after a change in network topology not all such requests 466 will, in general, reach the source, as some will be sent over links 467 that are now broken. However, if the network is still connected, 468 then at least one among the nodes suffering from spurious starvation 469 has an (unfeasible) route to the source; hence, in the absence of 470 packet loss, at least one such request will reach the source. 471 (Resending requests a small number of times compensates for packet 472 loss.) 474 Since requests are forwarded with no regard to the feasibility 475 condition, they may, in general, be caught in a forwarding loop; this 476 is avoided by having nodes perform duplicate detection for the 477 requests that they forward. 479 2.7. Multiple Routers 481 The above discussion assumes that each prefix is originated by a 482 single router. In real networks, however, it is often necessary to 483 have a single prefix originated by multiple routers: for example, the 484 default route will be originated by all of the edge routers of a 485 routing domain. 487 Since synchronising sequence numbers between distinct routers is 488 problematic, Babel treats routes for the same prefix as distinct 489 entities when they are originated by different routers: every route 490 announcement carries the router-id of its originating router, and 491 feasibility distances are not maintained per prefix, but per source, 492 where a source is a pair of a router-id and a prefix. In effect, 493 Babel guarantees loop-freedom for the forwarding graph to every 494 source; since the union of multiple acyclic graphs is not in general 495 acyclic, Babel does not in general guarantee loop-freedom when a 496 prefix is originated by multiple routers, but any loops will be 497 broken in a time at most proportional to the diameter of the loop -- 498 as soon as an update has "gone around" the routing loop. 500 Consider for example the following topology, where A has selected the 501 default route through S, and B has selected the one through S': 503 1 1 1 504 ::/0 -- S --- A --- B --- S' -- ::/0 506 Suppose that both default routes fail at the same time; then nothing 507 prevents A from switching to B, and B simultaneously switching to A. 508 However, as soon as A has successfully advertised the new route to B, 509 the route through A will become unfeasible for B. Conversely, as 510 soon as B will have advertised the route through A, the route through 511 B will become unfeasible for A. 513 In effect, the routing loop disappears at the latest when routing 514 information has gone around the loop. Since this process can be 515 delayed by lost packets, Babel makes certain efforts to ensure that 516 updates are sent reliably after a router-id change (Section 3.7.2). 518 Additionally, after the routers have advertised the two routes, both 519 sources will be in their source tables, which will prevent them from 520 ever again participating in a routing loop involving routes from S 521 and S' (up to the source GC time, which, available memory permitting, 522 can be set to arbitrarily large values). 524 2.8. Overlapping Prefixes 526 In the above discussion, we have assumed that all prefixes are 527 disjoint, as is the case in flat ("mesh") routing. In practice, 528 however, prefixes may overlap: for example, the default route 529 overlaps with all of the routes present in the network. 531 After a route fails, it is not correct in general to switch to a 532 route that subsumes the failed route. Consider for example the 533 following configuration: 535 1 1 536 ::/0 -- A --- B --- C 538 Suppose that node C fails. If B forwards packets destined to C by 539 following the default route, a routing loop will form, and persist 540 until A learns of B's retraction of the direct route to C. B avoids 541 this pitfall by installing an "unreachable" route after a route is 542 retracted; this route is maintained until it can be guaranteed that 543 the former route has been retracted by all of B's neighbours 544 (Section 3.5.4). 546 3. Protocol Operation 548 Every Babel speaker is assigned a router-id, which is an arbitrary 549 string of 8 octets that is assumed unique across the routing domain. 550 For example, router-ids could be assigned randomly, or they could be 551 derived from a link-layer address. (The protocol encoding is 552 slightly more compact when router-ids are assigned in the same manner 553 as the IPv6 layer assigns host IDs; see the definition of the "R" 554 flag in Section 4.6.9.) 556 3.1. Message Transmission and Reception 558 Babel protocol packets are sent in the body of a UDP datagram (as 559 described in Section 4 below). Each Babel packet consists of zero or 560 more TLVs. Most TLVs may contain sub-TLVs. 562 The protocol's control traffic can be carried indifferently over IPv6 563 or over IPv4, and prefixes of either address family can be announced 564 over either protocol. Thus, there are at least two natural 565 deployment models: using IPv6 exclusively for all control traffic, or 566 running two distinct protocol instances, one for each address family. 567 The exclusive use of IPv6 for all control traffic is RECOMMENDED, 568 since using both protocols at the same time doubles the amount of 569 traffic devoted to neighbour discovery and link quality estimation. 571 The source address of a Babel packet is always a unicast address, 572 link-local in the case of IPv6. Babel packets may be sent to a well- 573 known (link-local) multicast address or to a (link-local) unicast 574 address. In normal operation, a Babel speaker sends both multicast 575 and unicast packets to its neighbours. 577 With the exception of acknowledgments, all Babel TLVs can be sent to 578 either unicast or multicast addresses, and their semantics does not 579 depend on whether the destination is a unicast or a multicast 580 address. Hence, a Babel speaker does not need to determine the 581 destination address of a packet that it receives in order to 582 interpret it. 584 A moderate amount of jitter may be applied to packets sent by a Babel 585 speaker: outgoing TLVs are buffered and SHOULD be sent with a random 586 delay. This is done for two purposes: it avoids synchronisation of 587 multiple Babel speakers across a network [JITTER], and it allows for 588 the aggregation of multiple TLVs into a single packet. 590 The maximum amount of delay a TLV can be subjected to depends on the 591 TLV. When the protocol description specifies that a TLV is urgent 592 (as in Section 3.7.2 and Section 3.8.2), then the TLV MUST be sent 593 within a short time known as the urgent timeout (see Appendix B for 594 recommended values). When the TLV is governed by a timeout 595 explicitly included in a previous TLV, such as in the case of 596 Acknowledgements (Section 4.6.4), Updates (Section 3.7) and IHUs 597 (Section 3.4.2), then the TLV MUST be sent early enough to meet the 598 explicit deadline (with a small margin to allow for propagation 599 delays). In all other cases, the TLV SHOULD be sent out within one- 600 half of the Multicast Hello interval. 602 In order to avoid packet drops (either at the sender or at the 603 receiver), a delay SHOULD be introduced between successive packets 604 sent out on the same interface, within the constraints of the 605 previous paragraph. Note however that such packet pacing might 606 impair the ability of some link layers (e.g., IEEE 802.11 607 [IEEE802.11]) to perform packet aggregation. 609 3.2. Data Structures 611 In this section, we give a description of the data structures that 612 every Babel speaker maintains. This description is conceptual: a 613 Babel speaker may use different data structures as long as the 614 resulting protocol is the same as the one described in this document. 615 For example, rather than maintaining a single table containing both 616 selected and unselected (fallback) routes, as described in 617 Section 3.2.6 below, an actual implementation would probably use two 618 tables, one with selected routes and one with fallback routes. 620 3.2.1. Sequence number arithmetic 622 Sequence numbers (seqnos) appear in a number of Babel data 623 structures, and they are interpreted as integers modulo 2^16. For 624 the purposes of this document, arithmetic on sequence numbers is 625 defined as follows. 627 Given a seqno s and a non-negative integer n, the sum of s and n is 628 defined by 630 s + n (modulo 2^16) = (s + n) MOD 2^16 632 or, equivalently, 634 s + n (modulo 2^16) = (s + n) AND 65535 636 where MOD is the modulo operation yielding a non-negative integer and 637 AND is the bitwise conjunction operation. 639 Given two sequence numbers s and s', the relation s is less than s' 640 (s < s') is defined by 642 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 644 or equivalently 646 s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. 648 3.2.2. Node Sequence Number 650 A node's sequence number is a 16-bit integer that is included in 651 route updates sent for routes originated by this node. 653 A node increments its sequence number (modulo 2^16) whenever it 654 receives a request for a new sequence number (Section 3.8.1.2). A 655 node SHOULD NOT increment its sequence number (seqno) spontaneously, 656 since increasing seqnos makes it less likely that other nodes will 657 have feasible alternate routes when their selected routes fail. 659 3.2.3. The Interface Table 661 The interface table contains the list of interfaces on which the node 662 speaks the Babel protocol. Every interface table entry contains the 663 interface's outgoing Multicast Hello seqno, a 16-bit integer that is 664 sent with each Multicast Hello TLV on this interface and is 665 incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note 666 that an interface's Multicast Hello seqno is unrelated to the node's 667 seqno.) 668 There are two timers associated with each interface table entry. The 669 periodic Multicast Hello timer governs the sending of scheduled 670 Multicast Hello and IHU packets (Section 3.4. The periodic Update 671 timer governs the sending of periodic route updates (Section 3.7.1). 672 See Appendix B for suggested time constants. 674 3.2.4. The Neighbour Table 676 The neighbour table contains the list of all neighbouring interfaces 677 from which a Babel packet has been recently received. The neighbour 678 table is indexed by pairs of the form (interface, address), and every 679 neighbour table entry contains the following data: 681 o the local node's interface over which this neighbour is reachable; 683 o the address of the neighbouring interface; 685 o a history of recently received Multicast Hello packets from this 686 neighbour; this can, for example, be a sequence of n bits, for 687 some small value n, indicating which of the n hellos most recently 688 sent by this neighbour have been received by the local node; 690 o a history of recently received Unicast Hello packets from this 691 neighbour; 693 o the "transmission cost" value from the last IHU packet received 694 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 695 hold timer for this neighbour has expired; 697 o the expected incoming Multicast Hello sequence number for this 698 neighbour, an integer modulo 2^16. 700 o the expected incoming Unicast Hello sequence number for this 701 neighbour, an integer modulo 2^16. 703 o the outgoing Unicast Hello sequence number for this neighbour, an 704 integer modulo 2^16 that is sent with each Unicast Hello TLV to 705 this neighbour and is incremented (modulo 2^16) whenever a Unicast 706 Hello is sent. (Note that the outgoing Unicast Hello seqno for a 707 neighbour is distinct from the interface's outgoing Multicast 708 Hello seqno.) 710 There are three timers associated with each neighbour entry -- the 711 multicast hello timer, which is set to the interval value carried by 712 scheduled Multicast Hello TLVs sent by this neighbour, the unicast 713 hello timer, which is set to the interval value carried by scheduled 714 Unicast Hello TLVs, and the IHU timer, which is set to a small 715 multiple of the interval carried in IHU TLVs (see "IHU Hold time" in 716 Appendix B for suggested values). 718 Note that the neighbour table is indexed by IP addresses, not by 719 router-ids: neighbourship is a relationship between interfaces, not 720 between nodes. Therefore, two nodes with multiple interfaces can 721 participate in multiple neighbourship relationships, a situation that 722 can notably arise when wireless nodes with multiple radios are 723 involved. 725 3.2.5. The Source Table 727 The source table is used to record feasibility distances. It is 728 indexed by triples of the form (prefix, plen, router-id), and every 729 source table entry contains the following data: 731 o the prefix (prefix, plen), where plen is the prefix length in 732 bits, that this entry applies to; 734 o the router-id of a router originating this prefix; 736 o a pair (seqno, metric), this source's feasibility distance. 738 There is one timer associated with each entry in the source table -- 739 the source garbage-collection timer. It is initialised to a time on 740 the order of minutes and reset as specified in Section 3.7.3. 742 3.2.6. The Route Table 744 The route table contains the routes known to this node. It is 745 indexed by triples of the form (prefix, plen, neighbour), and every 746 route table entry contains the following data: 748 o the source (prefix, plen, router-id) for which this route is 749 advertised; 751 o the neighbour (an entry in the neighbour table) that advertised 752 this route; 754 o the metric with which this route was advertised by the neighbour, 755 or FFFF hexadecimal (infinity) for a recently retracted route; 757 o the sequence number with which this route was advertised; 759 o the next-hop address of this route; 760 o a boolean flag indicating whether this route is selected, i.e., 761 whether it is currently being used for forwarding and is being 762 advertised. 764 There is one timer associated with each route table entry -- the 765 route expiry timer. It is initialised and reset as specified in 766 Section 3.5.3. 768 Note that there are two distinct (seqno, metric) pairs associated to 769 each route: the route's distance, which is stored in the route table, 770 and the feasibility distance, stored in the source table and shared 771 between all routes with the same source. 773 3.2.7. The Table of Pending Seqno Requests 775 The table of pending seqno requests contains a list of seqno requests 776 that the local node has sent (either because they have been 777 originated locally, or because they were forwarded) and to which no 778 reply has been received yet. This table is indexed by triples of the 779 form (prefix, plen, router-id), and every entry in this table 780 contains the following data: 782 o the prefix, plen, router-id, and seqno being requested; 784 o the neighbour, if any, on behalf of which we are forwarding this 785 request; 787 o a small integer indicating the number of times that this request 788 will be resent if it remains unsatisfied. 790 There is one timer associated with each pending seqno request; it 791 governs both the resending of requests and their expiry. 793 3.3. Acknowledgments and acknowledgment requests 795 A Babel speaker may request that a neighbour receiving a given packet 796 reply with an explicit acknowledgment within a given time. While the 797 use of acknowledgment requests is optional, every Babel speaker MUST 798 be able to reply to such a request. 800 An acknowledgment MUST be sent to a unicast destination. On the 801 other hand, acknowledgment requests may be sent to either unicast or 802 multicast destinations, in which case they request an acknowledgment 803 from all of the receiving nodes. 805 When to request acknowledgments is a matter of local policy; the 806 simplest strategy is to never request acknowledgments and to rely on 807 periodic updates to ensure that any reachable routes are eventually 808 propagated throughout the routing domain. In order to improve 809 convergence speed and reduce the amount of control traffic, 810 acknowledgment requests MAY be used in order to reliably send urgent 811 updates (Section 3.7.2) and retractions (Section 3.5.4), especially 812 when the number of neighbours on a given interface is small. Since 813 Babel is designed to deal gracefully with packet loss on unreliable 814 media, sending all packets with acknowledgment requests is not 815 necessary, and NOT RECOMMENDED, as the acknowledgments cause 816 additional traffic and may force additional Address Resolution 817 Protocol (ARP) or Neighbour Discovery (ND) exchanges. 819 3.4. Neighbour Acquisition 821 Neighbour acquisition is the process by which a Babel node discovers 822 the set of neighbours heard over each of its interfaces and 823 ascertains bidirectional reachability. On unreliable media, 824 neighbour acquisition additionally provides some statistics that may 825 be useful for link quality computation. 827 Before it can exchange routing information with a neighbour, a Babel 828 node MUST create an entry for that neighbour in the neighbour table. 829 When to do that is implementation-specific; suitable strategies 830 include creating an entry when any Babel packet is received, or 831 creating an entry when a Hello TLV is parsed. Similarly, in order to 832 conserve system resources, an implementation SHOULD discard an entry 833 when it has been unused for long enough; suitable strategies include 834 dropping the neighbour after a timeout, and dropping a neighbour when 835 the associated Hello histories become empty (see Appendix A.2). 837 3.4.1. Reverse Reachability Detection 839 Every Babel node sends Hello TLVs to its neighbours to indicate that 840 it is alive, at regular or irregular intervals. Each Hello TLV 841 carries an increasing (modulo 2^16) sequence number and an upper 842 bound on the time interval until the next Hello of the same type (see 843 below). If the time interval is set to 0, then the Hello TLV does 844 not establish a new promise: the deadline carried by the previous 845 Hello of the same type still applies to the next Hello (if the most 846 recent scheduled Hello of the right kind was received at time t0 and 847 carried interval i, then the previous promise of sending another 848 Hello before time t0 + i still holds). We say that a Hello is 849 "scheduled" if it carries a non-zero interval, and "unscheduled" 850 otherwise. 852 There are two kinds of Hellos: Multicast Hellos, which use a per- 853 interface Hello counter (the Multicast Hello seqno), and Unicast 854 Hellos, which use a per-neighbour counter (the Unicast Hello seqno). 855 A Multicast Hello with a given seqno MUST be sent to all neighbours 856 on a given interface, either by sending it to a multicast address or 857 by sending it to one unicast address per neighbour (hence, the term 858 "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a 859 given seqno should normally be sent to just one neighbour (over 860 unicast), since the sequence numbers of different neighbours are not 861 in general synchronised. 863 Multicast Hellos sent over multicast can be used for neighbour 864 discovery; hence, a node SHOULD send periodic (scheduled) Multicast 865 Hellos unless neighbour discovery is performed by means outside of 866 the Babel protocol. A node MAY send Unicast Hellos or unscheduled 867 Hellos of either kind for any reason, such as reducing the amount of 868 multicast traffic or improving reliability on link technologies with 869 poor support for link-layer multicast. 871 A node MAY send a scheduled Hello ahead of time. A node MAY change 872 its scheduled Hello interval. The Hello interval MAY be decreased at 873 any time; it MAY be increased immediately before sending a Hello TLV, 874 but SHOULD NOT be increased at other times. (Equivalently, a node 875 SHOULD send a scheduled Hello immediately after increasing its Hello 876 interval.) 878 How to deal with received Hello TLVs and what statistics to maintain 879 are considered local implementation matters; typically, a node will 880 maintain some sort of history of recently received Hellos. An 881 example of a suitable algorithm is described in Appendix A.1. 883 After receiving a Hello, or determining that it has missed one, the 884 node recomputes the association's cost (Section 3.4.3) and runs the 885 route selection procedure (Section 3.6). 887 3.4.2. Bidirectional Reachability Detection 889 In order to establish bidirectional reachability, every node sends 890 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 891 IHUs carry an explicit interval value, they MAY be sent less often 892 than Hellos in order to reduce the amount of routing traffic in dense 893 networks; in particular, they SHOULD be sent less often than Hellos 894 over links with little packet loss. While IHUs are conceptually 895 unicast, they MAY be sent to a multicast address in order to avoid an 896 ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 897 into a single packet. 899 In addition to the periodic IHUs, a node MAY, at any time, send an 900 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 901 interval, and it MAY increase its IHU interval immediately before 902 sending an IHU, but SHOULD NOT increase it at any other time. 904 (Equivalently, a node SHOULD send an extra IHU immediately after 905 increasing its Hello interval.) 907 Every IHU TLV contains two pieces of data: the link's rxcost 908 (reception cost) from the sender's perspective, used by the neighbour 909 for computing link costs (Section 3.4.3), and the interval between 910 periodic IHU packets. A node receiving an IHU sets the value of the 911 txcost (transmission cost) maintained in the neighbour table to the 912 value contained in the IHU, and resets the IHU timer associated to 913 this neighbour to a small multiple of the interval value received in 914 the IHU (see "IHU Hold time" in Appendix B for suggested values). 915 When a neighbour's IHU timer expires, the neighbour's txcost is set 916 to infinity. 918 After updating a neighbour's txcost, the receiving node recomputes 919 the neighbour's cost (Section 3.4.3) and runs the route selection 920 procedure (Section 3.6). 922 3.4.3. Cost Computation 924 A neighbourship association's link cost is computed from the values 925 maintained in the neighbour table: the statistics kept in the 926 neighbour table about the reception of Hellos, and the txcost 927 computed from received IHU packets. 929 For every neighbour, a Babel node computes a value known as this 930 neighbour's rxcost. This value is usually derived from the Hello 931 history, which may be combined with other data, such as statistics 932 maintained by the link layer. The rxcost is sent to a neighbour in 933 each IHU. 935 Since nodes do not necessarily send periodic Unicast Hellos but do 936 usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD 937 use an algorithm that yields a finite rxcost when only Multicast 938 Hellos are received, unless interoperability with nodes that only 939 send Multicast Hellos is not required. 941 How the txcost and rxcost are combined in order to compute a link's 942 cost is a matter of local policy; as far as Babel's correctness is 943 concerned, only the following conditions MUST be satisfied: 945 o the cost is strictly positive; 947 o if no Hello TLVs of either kind were received recently, then the 948 cost is infinite; 950 o if the txcost is infinite, then the cost is infinite. 952 See Appendix A.2 for RECOMMENDED strategies for computing a link's 953 cost. 955 3.5. Routing Table Maintenance 957 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 958 seqno, metric), where (prefix, plen) is the prefix for which a route 959 is being advertised, router-id is the router-id of the router 960 originating this update, seqno is a nondecreasing (modulo 2^16) 961 integer that carries the originating router seqno, and metric is the 962 announced metric. 964 Before being accepted, an update is checked against the feasibility 965 condition (Section 3.5.1), which ensures that the route does not 966 create a routing loop. If the feasibility condition is not 967 satisfied, the update is either ignored or prevents the route from 968 being selected, as described in Section 3.5.3. If the feasibility 969 condition is satisfied, then the update cannot possibly cause a 970 routing loop. 972 3.5.1. The Feasibility Condition 974 The feasibility condition is applied to all received updates. The 975 feasibility condition compares the metric in the received update with 976 the metrics of the updates previously sent by the receiving node; 977 updates that fail the feasibility condition, and therefore have 978 metrics large enough to cause a routing loop, are either ignored or 979 prevent the resulting route from being selected. 981 A feasibility distance is a pair (seqno, metric), where seqno is an 982 integer modulo 2^16 and metric is a positive integer. Feasibility 983 distances are compared lexicographically, with the first component 984 inverted: we say that a distance (seqno, metric) is strictly better 985 than a distance (seqno', metric'), written 987 (seqno, metric) < (seqno', metric') 989 when 991 seqno > seqno' or (seqno = seqno' and metric < metric') 993 where sequence numbers are compared modulo 2^16. 995 Given a source (prefix, plen, router-id), a node's feasibility 996 distance for this source is the minimum, according to the ordering 997 defined above, of the distances of all the finite updates ever sent 998 by this particular node for the prefix (prefix, plen) and the given 999 router-id. Feasibility distances are maintained in the source table, 1000 the exact procedure is given in Section 3.7.3. 1002 A received update is feasible when either it is a retraction (its 1003 metric is FFFF hexadecimal), or the advertised distance is strictly 1004 better, in the sense defined above, than the feasibility distance for 1005 the corresponding source. More precisely, a route advertisement 1006 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 1007 feasible if one of the following conditions holds: 1009 o metric is infinite; or 1011 o no entry exists in the source table indexed by (prefix, plen, 1012 router-id); or 1014 o an entry (prefix, plen, router-id, seqno', metric') exists in the 1015 source table, and either 1017 * seqno' < seqno or 1019 * seqno = seqno' and metric < metric'. 1021 Note that the feasibility condition considers the metric advertised 1022 by the neighbour, not the route's metric; hence, a fluctuation in a 1023 neighbour's cost cannot render a selected route unfeasible. Note 1024 further that retractions (updates with infinite metric) are always 1025 feasible, since they cannot possibly cause a routing loop. 1027 3.5.2. Metric Computation 1029 A route's metric is computed from the metric advertised by the 1030 neighbour and the neighbour's link cost. Just like cost computation, 1031 metric computation is considered a local policy matter; as far as 1032 Babel is concerned, the function M(c, m) used for computing a metric 1033 from a locally computed link cost c and the metric m advertised by a 1034 neighbour MUST only satisfy the following conditions: 1036 o if c is infinite, then M(c, m) is infinite; 1038 o M is strictly monotonic: M(c, m) > m. 1040 Additionally, the metric SHOULD satisfy the following condition: 1042 o M is left-distributive: if m <= m', then M(c, m) <= M(c, m'). 1044 While strict monotonicity is essential to the integrity of the 1045 network (persistent routing loops may arise if it is not satisfied), 1046 left distributivity is not: if it is not satisfied, Babel will still 1047 converge to a loop-free configuration, but might not reach a global 1048 optimum (in fact, a global optimum may not even exist). 1050 The conditions above are easily satisfied by using the additive 1051 metric, i.e., by defining M(c, m) = c + m. Since the additive metric 1052 is useful with a large range of cost computation strategies, it is 1053 the RECOMMENDED default. See also Appendix C, which describes a 1054 technique that makes it possible to tweak the values of individual 1055 metrics without running the risk of creating routing loops. 1057 3.5.3. Route Acquisition 1059 When a Babel node receives an update (prefix, plen, router-id, seqno, 1060 metric) from a neighbour neigh, it checks whether it already has a 1061 route table entry indexed by (prefix, plen, neigh). 1063 If no such entry exists: 1065 o if the update is unfeasible, it MAY be ignored; 1067 o if the metric is infinite (the update is a retraction of a route 1068 we do not know about), the update is ignored; 1070 o otherwise, a new entry is created in the route table, indexed by 1071 (prefix, plen, neigh), with source equal to (prefix, plen, router- 1072 id), seqno equal to seqno and an advertised metric equal to the 1073 metric carried by the update. 1075 If such an entry exists: 1077 o if the entry is currently selected, the update is unfeasible, and 1078 the router-id of the update is equal to the router-id of the 1079 entry, then the update MAY be ignored; 1081 o otherwise, the entry's sequence number, advertised metric, metric, 1082 and router-id are updated and, if the advertised metric is not 1083 infinite, the route's expiry timer is reset to a small multiple of 1084 the Interval value included in the update (see "Route Hold time" 1085 in Appendix B for suggested values). If the update is unfeasible, 1086 then the (now unfeasible) entry MUST be immediately unselected. 1087 If the update caused the router-id of the entry to change, an 1088 update (possibly a retraction) MUST be sent in a timely manner as 1089 described in 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.4. 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.3 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.3); 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 algorithm'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 Babel nodes using different route selection strategies will 1157 interoperate and not create routing loops as long as these two 1158 properties hold. 1160 Route selection MUST NOT take seqnos into account: a route MUST NOT 1161 be preferred just because it carries a higher (more recent) seqno. 1162 Doing otherwise would cause route oscillation while a new seqno 1163 propagates across the network, and might create persistent blackholes 1164 if the metric being used is not left-distributive (Section 3.5.2). 1166 The obvious route selection strategy is to pick, for every 1167 destination, the feasible route with minimal metric. When all 1168 metrics are stable, this approach ensures convergence to a tree of 1169 shortest paths (assuming that the metric is left-distributive, see 1170 Section 3.5.2). There are two reasons, however, why this strategy 1171 may lead to instability in the presence of continuously varying 1172 metrics. First, if two parallel routes oscillate around a common 1173 value, then the smallest metric strategy will keep switching between 1174 the two. Second, when a route is selected, congestion along it 1175 increases, which might increase packet loss, which in turn could 1176 cause its metric to increase; this is a feedback loop, of the kind 1177 that is prone to causing persistent oscillations. 1179 In order to limit this kind of instabilities, a route selection 1180 strategy SHOULD include some form of hysteresis, i.e., be sensitive 1181 to a route's history: if a route is currently selected, then the 1182 strategy should only switch to a different route if the latter has 1183 been consistently good for some period of time. A RECOMMENDED 1184 hysteresis algorithm is given in Appendix A.3. 1186 After the route selection procedure is run, triggered updates 1187 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1189 3.7. Sending Updates 1191 A Babel speaker advertises to its neighbours its set of selected 1192 routes. Normally, this is done by sending one or more multicast 1193 packets containing Update TLVs on all of its connected interfaces; 1194 however, on link technologies where multicast is significantly more 1195 expensive than unicast, a node MAY choose to send multiple copies of 1196 updates in unicast packets, especially when the number of neighbours 1197 is small. 1199 Additionally, in order to ensure that any black-holes are reliably 1200 cleared in a timely manner, a Babel node may send retractions 1201 (updates with an infinite metric) for any recently retracted 1202 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 MUST advertise each of its selected routes on 1219 every interface, at least once every Update interval. Since Babel 1220 doesn't suffer from routing loops (there is no "counting to 1221 infinity") and relies heavily on triggered updates (Section 3.7.2), 1222 this full dump only needs to happen infrequently (see Appendix B for 1223 suggested intervals). 1225 3.7.2. Triggered Updates 1227 In addition to periodic routing updates, a Babel speaker sends 1228 unscheduled, or triggered, updates in order to inform its neighbours 1229 of a significant change in the network topology. 1231 A change of router-id for the selected route to a given prefix may be 1232 indicative of a routing loop in formation; hence, whenever it changes 1233 the selected router-id for a given destination, a node MUST send an 1234 update as an urgent TLV (as defined in Section 3.1). Additionally, 1235 it SHOULD make a reasonable attempt at ensuring that all reachable 1236 neighbours receive this update. 1238 There are two strategies for ensuring that. If the number of 1239 neighbours is small, then it is reasonable to send the update 1240 together with an acknowledgment request; the update is resent until 1241 all neighbours have acknowledged the packet, up to some number of 1242 times. If the number of neighbours is large, however, requesting 1243 acknowledgments from all of them might cause a non-negligible amount 1244 of network traffic; in that case, it may be preferable to simply 1245 repeat the update some reasonable number of times (say, 3 for 1246 wireless and 2 for wired links). The number of copies MUST NOT 1247 exceed 5, and the copies SHOULD be separated by a small delay, as 1248 described in Section 3.1. 1250 A route retraction is somewhat less worrying: if the route retraction 1251 doesn't reach all neighbours, a black-hole might be created, which, 1252 unlike a routing loop, does not endanger the integrity of the 1253 network. When a route is retracted, a node SHOULD send a triggered 1254 update and SHOULD make a reasonable attempt at ensuring that all 1255 neighbours receive this retraction. 1257 Finally, a node MAY send a triggered update when the metric for a 1258 given prefix changes in a significant manner, due to a received 1259 update, because a link's cost has changed, or because a different 1260 next hop has been selected. A node SHOULD NOT send triggered updates 1261 for other reasons, such as when there is a minor fluctuation in a 1262 route's metric, when the selected next hop changes, or to propagate a 1263 new sequence number (except to satisfy a request, as specified in 1264 Section 3.8). 1266 3.7.3. Maintaining Feasibility Distances 1268 Before sending an update (prefix, plen, router-id, seqno, metric) 1269 with finite metric (i.e., not a route retraction), a Babel node 1270 updates the feasibility distance maintained in the source table. 1271 This is done as follows. 1273 If no entry indexed by (prefix, plen, router-id) exists in the source 1274 table, then one is created with value (prefix, plen, router-id, 1275 seqno, metric). 1277 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1278 it is updated as follows: 1280 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1282 o if seqno = seqno' and metric' > metric, then metric' := metric; 1284 o otherwise, nothing needs to be done. 1286 The garbage-collection timer for the entry is then reset. Note that 1287 the feasibility distance is not updated and the garbage-collection 1288 timer is not reset when a retraction (an update with infinite metric) 1289 is sent. 1291 When the garbage-collection timer expires, the entry is removed from 1292 the source table. 1294 3.7.4. Split Horizon 1296 When running over a transitive, symmetric link technology, e.g., a 1297 point-to-point link or a wired LAN technology such as Ethernet, a 1298 Babel node SHOULD use an optimisation known as split horizon. When 1299 split horizon is used on a given interface, a routing update for 1300 prefix P is not sent on the particular interface over which the 1301 selected route towards prefix P was learnt. 1303 Split horizon SHOULD NOT be applied to an interface unless the 1304 interface is known to be symmetric and transitive; in particular, 1305 split horizon is not applicable to decentralised wireless link 1306 technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates 1307 are sent over multicast. 1309 3.8. Explicit Requests 1311 In normal operation, a node's route table is populated by the regular 1312 and triggered updates sent by its neighbours. Under some 1313 circumstances, however, a node sends explicit requests in order to 1314 cause a resynchronisation with the source after a mobility event or 1315 to prevent a route from spuriously expiring. 1317 The Babel protocol provides two kinds of explicit requests: route 1318 requests, which simply request an update for a given prefix, and 1319 seqno requests, which request an update for a given prefix with a 1320 specific sequence number. The former are never forwarded; the latter 1321 are forwarded if they cannot be satisfied by the receiver. 1323 3.8.1. Handling Requests 1325 Upon receiving a request, a node either forwards the request or sends 1326 an update in reply to the request, as described in the following 1327 sections. If this causes an update to be sent, the update is either 1328 sent to a multicast address on the interface on which the request was 1329 received, or to the unicast address of the neighbour that sent the 1330 request. 1332 The exact behaviour is different for route requests and seqno 1333 requests. 1335 3.8.1.1. Route Requests 1337 When a node receives a route request for a given prefix, it checks 1338 its route table for a selected route to this exact prefix. If such a 1339 route exists, it MUST send an update (over unicast or over 1340 multicast); if such a route does not exist, it MUST send a retraction 1341 for that prefix. 1343 When a node receives a wildcard route request, it SHOULD send a full 1344 route table dump. Full route dumps SHOULD be rate-limited, 1345 especially if they are sent over multicast. 1347 3.8.1.2. Seqno Requests 1349 When a node receives a seqno request for a given router-id and 1350 sequence number, it checks whether its route table contains a 1351 selected entry for that prefix. If a selected route for the given 1352 prefix exists, it has finite metric, and either the router-ids are 1353 different or the router-ids are equal and the entry's sequence number 1354 is no smaller (modulo 2^16) than the requested sequence number, the 1355 node MUST send an update for the given prefix. If the router-ids 1356 match but the requested seqno is larger (modulo 2^16) than the route 1357 entry's, the node compares the router-id against its own router-id. 1358 If the router-id is its own, then it increases its sequence number by 1359 1 (modulo 2^16) and sends an update. A node MUST NOT increase its 1360 sequence number by more than 1 in reaction to a single seqno request. 1362 Otherwise, if the requested router-id is not its own, the received 1363 node consults the hop count field of the request. If the hop count 1364 is 2 or more, and the node is advertising the prefix to its 1365 neighbours, the node selects a neighbour to forward the request to as 1366 follows: 1368 o if the node has one or more feasible routes toward the requested 1369 prefix with a next hop that is not the requesting node, then the 1370 node MUST forward the request to the next hop of one such route; 1372 o otherwise, if the node has one or more (not feasible) routes to 1373 the requested prefix with a next hop that is not the requesting 1374 node, then the node SHOULD forward the request to the next hop of 1375 one such route. 1377 In order to actually forward the request, the node decrements the hop 1378 count and sends the request in a unicast packet destined to the 1379 selected neighbour. The forwarded request SHOULD be sent as an 1380 urgent TLV (as defined in Section 3.1). 1382 A node SHOULD maintain a list of recently forwarded seqno requests 1383 and forward the reply (an update with a seqno sufficiently large to 1384 satisfy the request) as an urgent TLV (as defined in Section 3.1). A 1385 node SHOULD compare every incoming seqno request against its list of 1386 recently forwarded seqno requests and avoid forwarding it if it is 1387 redundant (i.e., if it has recently sent a request with the same 1388 prefix, router-id and a seqno that is not smaller modulo 2^16). 1390 Since the request-forwarding mechanism does not necessarily obey the 1391 feasibility condition, it may get caught in routing loops; hence, 1392 requests carry a hop count to limit the time during which they remain 1393 in the network. However, since requests are only ever forwarded as 1394 unicast packets, the initial hop count need not be kept particularly 1395 low, and performing an expanding horizon search is not necessary. A 1396 single request MUST NOT be duplicated: it MUST NOT be forwarded to a 1397 multicast address, and it MUST NOT be forwarded to multiple 1398 neighbours. However, if a seqno request is resent by its originator, 1399 the subsequent copies may be forwarded to a different neighbour than 1400 the initial one. 1402 3.8.2. Sending Requests 1404 A Babel node MAY send a route or seqno request at any time, to a 1405 multicast or a unicast address; there is only one case when 1406 originating requests is required (Section 3.8.2.1). 1408 3.8.2.1. Avoiding Starvation 1410 When a route is retracted or expires, a Babel node usually switches 1411 to another feasible route for the same prefix. It may be the case, 1412 however, that no such routes are available. 1414 A node that has lost all feasible routes to a given destination but 1415 still has unexpired unfeasible routes to that destination MUST send a 1416 seqno request; if it doesn't have any such routes, it MAY still send 1417 a seqno request. The router-id of the request is set to the router- 1418 id of the route that it has just lost, and the requested seqno is the 1419 value contained in the source table plus 1. The request carries a 1420 hop count, which is used as a last-resort mechanism to ensure that it 1421 eventually vanishes from the network; it MAY be set to any value that 1422 is larger than the diameter of the network (64 is a suitable default 1423 value). 1425 If the node has any (unfeasible) routes to the requested destination, 1426 then it MUST send the request to at least one of the next-hop 1427 neighbours that advertised these routes, and SHOULD send it to all of 1428 them; in any case, it MAY send the request to any other neighbours, 1429 whether they advertise a route to the requested destination or not. 1431 A simple implementation strategy is therefore to unconditionally 1432 multicast the request over all interfaces. 1434 Similar requests will be sent by other nodes that are affected by the 1435 route's loss. If the network is still connected, and assuming no 1436 packet loss, then at least one of these requests will be forwarded to 1437 the source, resulting in a route being advertised with a new sequence 1438 number. (Due to duplicate suppression, only a small number of such 1439 requests are expected to actually reach the source.) 1441 In order to compensate for packet loss, a node SHOULD repeat such a 1442 request a small number of times if no route becomes feasible within a 1443 short time (see "Request Timeout" in Appendix B for suggested 1444 values). In the presence of heavy packet loss, however, all such 1445 requests might be lost; in that case, the mechanism in the next 1446 section will eventually ensure that a new seqno is received. 1448 3.8.2.2. Dealing with Unfeasible Updates 1450 When a route's metric increases, a node might receive an unfeasible 1451 update for a route that it has currently selected. As specified in 1452 Section 3.5.1, the receiving node will either ignore the update or 1453 unselect the route. 1455 In order to keep routes from spuriously expiring because they have 1456 become unfeasible, a node SHOULD send a unicast seqno request when it 1457 receives an unfeasible update for a route that is currently selected. 1458 The requested sequence number is computed from the source table as in 1459 Section 3.8.2.1 above. 1461 Additionally, since metric computation does not necessarily coincide 1462 with the delay in propagating updates, a node might receive an 1463 unfeasible update from a currently unselected neighbour that is 1464 preferable to the currently selected route (e.g., because it has a 1465 much smaller metric); in that case, the node SHOULD send a unicast 1466 seqno request to the neighbour that advertised the preferable update. 1468 3.8.2.3. Preventing Routes from Expiring 1470 In normal operation, a route's expiry timer never triggers: since a 1471 route's hold time is computed from an explicit interval included in 1472 Update TLVs, a new update (possibly a retraction) should arrive in 1473 time to prevent a route from expiring. 1475 In the presence of packet loss, however, it may be the case that no 1476 update is successfully received for an extended period of time, 1477 causing a route to expire. In order to avoid such spurious expiry, 1478 shortly before a selected route expires, a Babel node SHOULD send a 1479 unicast route request to the neighbour that advertised this route; 1480 since nodes always send either updates or retractions in response to 1481 non-wildcard route requests (Section 3.8.1.1), this will usually 1482 result in the route being either refreshed or retracted. 1484 4. Protocol Encoding 1486 A Babel packet MUST be sent as the body of a UDP datagram, with 1487 network-layer hop count set to 1, destined to a well-known multicast 1488 address or to a unicast address, over IPv4 or IPv6; in the case of 1489 IPv6, these addresses are link-local. Both the source and 1490 destination UDP port are set to a well-known port number. A Babel 1491 packet MUST be silently ignored unless its source address is either a 1492 link-local IPv6 address or an IPv4 address belonging to the local 1493 network, and its source port is the well-known Babel port. It MAY be 1494 silently ignored if its destination address is a global IPv6 address. 1496 In order to minimise the number of packets being sent while avoiding 1497 lower-layer fragmentation, a Babel node SHOULD maximise the size of 1498 the packets it sends, up to the outgoing interface's MTU adjusted for 1499 lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP 1500 over IPv6). It MUST NOT send packets larger than the attached 1501 interface's MTU adjusted for lower-layer headers or 512 octets, 1502 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1503 layer headers. Every Babel speaker MUST be able to receive packets 1504 that are as large as any attached interface's MTU adjusted for lower- 1505 layer headers or 512 octets, whichever is larger. Babel packets MUST 1506 NOT be sent in IPv6 Jumbograms [RFC2675]. 1508 4.1. Data Types 1510 4.1.1. Interval 1512 Relative times are carried as 16-bit values specifying a number of 1513 centiseconds (hundredths of a second). This allows times up to 1514 roughly 11 minutes with a granularity of 10ms, which should cover all 1515 reasonable applications of Babel (see also Appendix B). 1517 4.1.2. Router-Id 1519 A router-id is an arbitrary 8-octet value. A router-id MUST NOT 1520 consist of either all binary zeroes (0000000000000000 hexadecimal) or 1521 all binary ones (FFFFFFFFFFFFFFFF hexadecimal). 1523 4.1.3. Address 1525 Since the bulk of the protocol is taken by addresses, multiple ways 1526 of encoding addresses are defined. Additionally, within Update TLVs 1527 a common subnet prefix may be omitted when multiple addresses are 1528 sent in a single packet -- this is known as address compression 1529 (Section 4.6.9). 1531 Address encodings: 1533 o AE 0: wildcard address. The value is 0 octets long. 1535 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1537 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1539 o AE 3: link-local IPv6 address. Compression is not allowed. The 1540 value is 8 octets long, a prefix of fe80::/64 is implied. 1542 The address family associated to an address encoding is either IPv4 1543 or IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 1544 and 3. 1546 4.1.4. Prefixes 1548 A network prefix is encoded just like a network address, but it is 1549 stored in the smallest number of octets that are enough to hold the 1550 significant bits (up to the prefix length). 1552 4.2. Packet Format 1554 A Babel packet consists of a 4-octet header, followed by a sequence 1555 of TLVs (the packet body), optionally followed by a second sequence 1556 of TLVs (the packet trailer). The format is designed to be 1557 extensible; see Appendix D for extensibility considerations. 1559 0 1 2 3 1560 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 1561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1562 | Magic | Version | Body length | 1563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1564 | Packet Body ... 1565 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1566 | Packet Trailer... 1567 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1569 Fields : 1571 Magic The arbitrary but carefully chosen value 42 (decimal); 1572 packets with a first octet different from 42 MUST be 1573 silently ignored. 1575 Version This document specifies version 2 of the Babel protocol. 1576 Packets with a second octet different from 2 MUST be 1577 silently ignored. 1579 Body length The length in octets of the body following the packet 1580 header (excluding the Magic, Version and Body length 1581 fields, and excluding the packet trailer). 1583 Packet Body The packet body; a sequence of TLVs. 1585 Packet Trailer The packet trailer; another sequence of TLVs. 1587 The packet body and trailer are both sequences of TLVs. The packet 1588 body is the normal place to store TLVs; the packet trailer only 1589 contains specialised TLVs that do not need to be protected by 1590 cryptographic security mechanisms. When parsing the trailer, the 1591 receiver MUST ignore any TLV unless its definition explicitly states 1592 that it is allowed to appear there. Among the TLVs defined in this 1593 document, only Pad1 and PadN are allowed in the trailer; since these 1594 TLVs are ignored in any case, an implementation MAY silently ignore 1595 the packet trailer without even parsing it, unless it implements at 1596 least one protocol extension that defines TLVs that are allowed to 1597 appear in the trailer. 1599 4.3. TLV Format 1601 With the exception of Pad1, all TLVs have the following structure: 1603 0 1 2 3 1604 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 1605 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1606 | Type | Length | Payload... 1607 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1609 Fields : 1611 Type The type of the TLV. 1613 Length The length of the body in octets, exclusive of the Type and 1614 Length fields. 1616 Payload The TLV payload, which consists of a body and, for selected 1617 TLV types, an optional list of sub-TLVs. 1619 TLVs with an unknown type value MUST be silently ignored. 1621 4.4. Sub-TLV Format 1623 Every TLV carries an explicit length in its header; however, most 1624 TLVs are self-terminating, in the sense that it is possible to 1625 determine the length of the body without reference to the explicit 1626 Length field. If a TLV has a self-terminating format, then the space 1627 between the natural size of the TLV and the size announced in the 1628 Length field may be used to store a sequence of sub-TLVs. 1630 Sub-TLVs have the same structure as TLVs. With the exception of 1631 Pad1, all TLVs have the following structure: 1633 0 1 2 3 1634 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 1635 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1636 | Type | Length | Body... 1637 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1639 Fields : 1641 Type The type of the sub-TLV. 1643 Length The length of the body in octets, exclusive of the Type and 1644 Length fields. 1646 Body The sub-TLV body, the interpretation of which depends on 1647 both the type of the sub-TLV and the type of the TLV within 1648 which it is embedded. 1650 The most-significant bit of the sub-TLV type (the bit with value 80 1651 hexadecimal), is called the mandatory bit; in other words, sub-TLV 1652 types 128 through 255 have the mandatory bit set. This bit indicates 1653 how to handle unknown sub-TLVs. If the mandatory bit is not set, 1654 then an unknown sub-TLV MUST be silently ignored, and the rest of the 1655 TLV is processed normally. If the mandatory bit is set, then the 1656 whole enclosing TLV MUST be silently ignored (except for updating the 1657 parser state by a Router-Id, Next-Hop or Update TLV, as described in 1658 the next section). 1660 4.5. Parser state and encoding of updates 1662 In a large network, the bulk of Babel traffic consists of route 1663 updates; hence, some care has been given to encoding them 1664 efficiently. The data conceptually contained in an update 1665 (Section 3.5) is split into three pieces: 1667 o the prefix, seqno and metric are contained in the Update TLV 1668 itself (Section 4.6.9); 1670 o the router-id is taken from Router-Id TLV that precedes the Update 1671 TLV, and may be shared among multiple Update TLVs (Section 4.6.7); 1673 o the next hop is taken either from the source-address of the 1674 network-layer packet that contains the Babel packet, or from an 1675 explicit Next-Hop TLV (Section 4.6.8). 1677 In addition to the above, an Update TLV can omit a prefix of the 1678 prefix being announced, which is then extracted from the preceding 1679 Update TLV in the same address family (IPv4 or IPv6). Finally, as a 1680 special optimisation for the case when a router-id coincides with the 1681 interface-id part of an IPv6 address, Router-ID TLV itself may be 1682 omitted and the router-id derived derived from the low-order bits of 1683 the advertised prefix (Section 4.6.9). 1685 In order to implement these compression techniques, Babel uses a 1686 stateful parser: a TLV may refer to data from a previous TLV. The 1687 parser state consists of the following pieces of data: 1689 o for each address encoding that allows compression, the current 1690 default prefix; this is undefined at the start of the packet, and 1691 is updated by each Update TLV with the Prefix flag set 1692 (Section 4.6.9); 1694 o for each address family (IPv4 or IPv6), the current next-hop; this 1695 is the source address of the enclosing packet for the matching 1696 address family at the start of a packet, and is updated by each 1697 Next-Hop TLV (Section 4.6.8); 1699 o the current router-id; this is undefined at the start of the 1700 packet, and is updated by each Router-ID TLV (Section 4.6.7) and 1701 by each Update TLV with Router-Id flag set. 1703 Since the parser state must be identical across implementations, it 1704 is updated before checking for mandatory sub-TLVs: parsing a TLV MUST 1705 update the parser state even if the TLV is otherwise ignored due to 1706 an unknown mandatory sub-TLV or for any other reason. 1708 None of the TLVs that modify the parser state are allowed in the 1709 packet trailer; hence, an implementation may choose to use a 1710 dedicated stateless parser to parse the packet trailer. 1712 4.6. Details of Specific TLVs 1714 4.6.1. Pad1 1716 0 1717 0 1 2 3 4 5 6 7 1718 +-+-+-+-+-+-+-+-+ 1719 | Type = 0 | 1720 +-+-+-+-+-+-+-+-+ 1722 Fields : 1724 Type Set to 0 to indicate a Pad1 TLV. 1726 This TLV is silently ignored on reception. It is allowed in the 1727 packet trailer. 1729 4.6.2. PadN 1731 0 1 2 3 1732 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 1733 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1734 | Type = 1 | Length | MBZ... 1735 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1737 Fields : 1739 Type Set to 1 to indicate a PadN TLV. 1741 Length The length of the body in octets, exclusive of the Type and 1742 Length fields. 1744 MBZ Must be zero, set to 0 on transmission. 1746 This TLV is silently ignored on reception. It is allowed in the 1747 packet trailer. 1749 4.6.3. Acknowledgment Request 1751 0 1 2 3 1752 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 1753 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1754 | Type = 2 | Length | Reserved | 1755 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1756 | Opaque | Interval | 1757 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1758 This TLV requests that the receiver send an Acknowledgment TLV within 1759 the number of centiseconds specified by the Interval field. 1761 Fields : 1763 Type Set to 2 to indicate an Acknowledgment Request TLV. 1765 Length The length of the body in octets, exclusive of the Type and 1766 Length fields. 1768 Reserved Sent as 0 and MUST be ignored on reception. 1770 Opaque An arbitrary value that will be echoed in the receiver's 1771 Acknowledgment TLV. 1773 Interval A time interval in centiseconds after which the sender will 1774 assume that this packet has been lost. This MUST NOT be 0. 1775 The receiver MUST send an Acknowledgment TLV before this 1776 time has elapsed (with a margin allowing for propagation 1777 time). 1779 This TLV is self-terminating, and allows sub-TLVs. 1781 4.6.4. Acknowledgment 1783 0 1 2 3 1784 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 1785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1786 | Type = 3 | Length | Opaque | 1787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1789 This TLV is sent by a node upon receiving an Acknowledgment Request. 1791 Fields : 1793 Type Set to 3 to indicate an Acknowledgment TLV. 1795 Length The length of the body in octets, exclusive of the Type and 1796 Length fields. 1798 Opaque Set to the Opaque value of the Acknowledgment Request that 1799 prompted this Acknowledgment. 1801 Since Opaque values are not globally unique, this TLV MUST be sent to 1802 a unicast address. 1804 This TLV is self-terminating, and allows sub-TLVs. 1806 4.6.5. Hello 1808 0 1 2 3 1809 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 1810 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1811 | Type = 4 | Length | Flags | 1812 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1813 | Seqno | Interval | 1814 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1816 This TLV is used for neighbour discovery and for determining a 1817 neighbour's reception cost. 1819 Fields : 1821 Type Set to 4 to indicate a Hello TLV. 1823 Length The length of the body in octets, exclusive of the Type and 1824 Length fields. 1826 Flags The individual bits of this field specify special handling 1827 of this TLV (see below). 1829 Seqno If the Unicast flag is set, this is the value of the 1830 sending node's outgoing Unicast Hello seqno for this 1831 neighbour. Otherwise, it is the sending node's outgoing 1832 Multicast Hello seqno for this interface. 1834 Interval If non-zero, this is an upper bound, expressed in 1835 centiseconds, on the time after which the sending node will 1836 send a new scheduled Hello TLV with the same setting of the 1837 Unicast flag. If this is 0, then this Hello represents an 1838 unscheduled Hello, and doesn't carry any new information 1839 about times at which Hellos are sent. 1841 The Flags field is interpreted as follows: 1843 0 1 1844 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 1845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1846 |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| 1847 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1849 o U (Unicast) flag (8000 hexadecimal): if set, then this Hello 1850 represents a Unicast Hello, otherwise it represents a Multicast 1851 Hello; 1853 o X: all other bits MUST be sent as 0 and silently ignored on 1854 reception. 1856 Every time a Hello is sent, the corresponding seqno counter MUST be 1857 incremented. Since there is a single seqno counter for all the 1858 Multicast Hellos sent by a given node over a given interface, if the 1859 Unicast flag is not set, this TLV MUST be sent to all neighbors on 1860 this link, which can be achieved by sending to a multicast 1861 destination, or by sending multiple packets to the unicast addresses 1862 of all reachable neighbours. Conversely, if the Unicast flag is set, 1863 this TLV MUST be sent to a single neighbour, which can achieved by 1864 sending to a unicast destination. In order to avoid large 1865 discontinuities in link quality, multiple Hello TLVs SHOULD NOT be 1866 sent in the same packet. 1868 This TLV is self-terminating, and allows sub-TLVs. 1870 4.6.6. IHU 1872 0 1 2 3 1873 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 1874 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1875 | Type = 5 | Length | AE | Reserved | 1876 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1877 | Rxcost | Interval | 1878 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1879 | Address... 1880 +-+-+-+-+-+-+-+-+-+-+-+- 1882 An IHU ("I Heard You") TLV is used for confirming bidirectional 1883 reachability and carrying a link's transmission cost. 1885 Fields : 1887 Type Set to 5 to indicate an IHU TLV. 1889 Length The length of the body in octets, exclusive of the Type and 1890 Length fields. 1892 AE The encoding of the Address field. This should be 1 or 3 1893 in most cases. As an optimisation, it MAY be 0 if the TLV 1894 is sent to a unicast address, if the association is over a 1895 point-to-point link, or when bidirectional reachability is 1896 ascertained by means outside of the Babel protocol. 1898 Reserved Sent as 0 and MUST be ignored on reception. 1900 Rxcost The rxcost according to the sending node of the interface 1901 whose address is specified in the Address field. The value 1902 FFFF hexadecimal (infinity) indicates that this interface 1903 is unreachable. 1905 Interval An upper bound, expressed in centiseconds, on the time 1906 after which the sending node will send a new IHU; this MUST 1907 NOT be 0. The receiving node will use this value in order 1908 to compute a hold time for this symmetric association. 1910 Address The address of the destination node, in the format 1911 specified by the AE field. Address compression is not 1912 allowed. 1914 Conceptually, an IHU is destined to a single neighbour. However, IHU 1915 TLVs contain an explicit destination address, and MAY be sent to a 1916 multicast address, as this allows aggregation of IHUs destined to 1917 distinct neighbours into a single packet and avoids the need for an 1918 ARP or Neighbour Discovery exchange when a neighbour is not being 1919 used for data traffic. 1921 IHU TLVs with an unknown value in the AE field MUST be silently 1922 ignored. 1924 This TLV is self-terminating, and allows sub-TLVs. 1926 4.6.7. Router-Id 1928 0 1 2 3 1929 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 1930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1931 | Type = 6 | Length | Reserved | 1932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1933 | | 1934 + Router-Id + 1935 | | 1936 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1938 A Router-Id TLV establishes a router-id that is implied by subsequent 1939 Update TLVs, as described in Section 4.5. This TLV sets the router- 1940 id even if it is otherwise ignored due to an unknown mandatory sub- 1941 TLV. 1943 Fields : 1945 Type Set to 6 to indicate a Router-Id TLV. 1947 Length The length of the body in octets, exclusive of the Type and 1948 Length fields. 1950 Reserved Sent as 0 and MUST be ignored on reception. 1952 Router-Id The router-id for routes advertised in subsequent Update 1953 TLVs. This MUST NOT consist of all zeroes or all ones. 1955 This TLV is self-terminating, and allows sub-TLVs. 1957 4.6.8. Next Hop 1959 0 1 2 3 1960 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 1961 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1962 | Type = 7 | Length | AE | Reserved | 1963 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1964 | Next hop... 1965 +-+-+-+-+-+-+-+-+-+-+-+- 1967 A Next Hop TLV establishes a next-hop address for a given address 1968 family (IPv4 or IPv6) that is implied in subsequent Update TLVs, as 1969 described in Section 4.5. This TLV sets up the next-hop for 1970 subsequent Update TLVs even if it is otherwise ignored due to an 1971 unknown mandatory sub-TLV. 1973 Fields : 1975 Type Set to 7 to indicate a Next Hop TLV. 1977 Length The length of the body in octets, exclusive of the Type and 1978 Length fields. 1980 AE The encoding of the Address field. This SHOULD be 1 (IPv4) 1981 or 3 (link-local IPv6), and MUST NOT be 0. 1983 Reserved Sent as 0 and MUST be ignored on reception. 1985 Next hop The next-hop address advertised by subsequent Update TLVs, 1986 for this address family. 1988 When the address family matches the network-layer protocol that this 1989 packet is transported over, a Next Hop TLV is not needed: in the 1990 absence of a Next Hop TLV in a given address family, the next hop 1991 address is taken to be the source address of the packet. 1993 Next Hop TLVs with an unknown value for the AE field MUST be silently 1994 ignored. 1996 This TLV is self-terminating, and allows sub-TLVs. 1998 4.6.9. Update 2000 0 1 2 3 2001 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 2002 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2003 | Type = 8 | Length | AE | Flags | 2004 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2005 | Plen | Omitted | Interval | 2006 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2007 | Seqno | Metric | 2008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2009 | Prefix... 2010 +-+-+-+-+-+-+-+-+-+-+-+- 2012 An Update TLV advertises or retracts a route. As an optimisation, it 2013 can optionally have the side effect of establishing a new implied 2014 router-id and a new default prefix, as described in Section 4.5. 2016 Fields : 2018 Type Set to 8 to indicate an Update TLV. 2020 Length The length of the body in octets, exclusive of the Type and 2021 Length fields. 2023 AE The encoding of the Prefix field. 2025 Flags The individual bits of this field specify special handling 2026 of this TLV (see below). 2028 Plen The length in bits of the advertised prefix. If AE is 3 2029 (link-local IPv6), Omitted MUST be 0. 2031 Omitted The number of octets that have been omitted at the 2032 beginning of the advertised prefix and that should be taken 2033 from a preceding Update TLV in the same address family with 2034 the Prefix flag set. 2036 Interval An upper bound, expressed in centiseconds, on the time 2037 after which the sending node will send a new update for 2038 this prefix. This MUST NOT be 0. The receiving node will 2039 use this value to compute a hold time for the route table 2040 entry. The value FFFF hexadecimal (infinity) expresses 2041 that this announcement will not be repeated unless a 2042 request is received (Section 3.8.2.3). 2044 Seqno The originator's sequence number for this update. 2046 Metric The sender's metric for this route. The value FFFF 2047 hexadecimal (infinity) means that this is a route 2048 retraction. 2050 Prefix The prefix being advertised. This field's size is 2051 (Plen/8 - Omitted) rounded upwards. 2053 The Flags field is interpreted as follows: 2055 0 1 2 3 4 5 6 7 2056 +-+-+-+-+-+-+-+-+ 2057 |P|R|X|X|X|X|X|X| 2058 +-+-+-+-+-+-+-+-+ 2060 o P (Prefix) flag (80 hexadecimal): if set, then this Update 2061 establishes a new default prefix for subsequent Update TLVs with a 2062 matching address encoding within the same packet, even if this TLV 2063 is otherwise ignored due to an unknown mandatory sub-TLV; 2065 o R (Router-Id) flag (40 hexadecimal): if set, then this TLV 2066 establishes a new default router-id for this TLV and subsequent 2067 Update TLVs in the same packet, even if this TLV is otherwise 2068 ignored due to an unknown mandatory sub-TLV. This router-id is 2069 computed from the first address of the advertised prefix as 2070 follows: 2072 * if the length of the address is 8 octets or more, then the new 2073 router-id is taken from the 8 last octets of the address; 2075 * if the length of the address is smaller than 8 octets, then the 2076 new router-id consists of the required number of zero octets 2077 followed by the address, i.e., the address is stored on the 2078 right of the router-id. For example, for an IPv4 address, the 2079 router-id consists of 4 octets of zeroes followed by the IPv4 2080 address. 2082 o X: all other bits MUST be sent as 0 and silently ignored on 2083 reception. 2085 The prefix being advertised by an Update TLV is computed as follows: 2087 o the first Omitted octets of the prefix are taken from the previous 2088 Update TLV with the Prefix flag set and the same address encoding, 2089 even if it was ignored due to an unknown mandatory sub-TLV; if 2090 Omitted is not zero and there is no such TLV, then this Update 2091 MUST be ignored; 2093 o the next (Plen/8 - Omitted) rounded upwards octets are taken from 2094 the Prefix field; 2096 o if Plen is not a multiple of 8, then any bits beyond Plen (i.e., 2097 the low-order (8 - Plen MOD 8) bits of the last octet) are 2098 cleared; 2100 o the remaining octets are set to 0. 2102 If the Metric field is finite, the router-id of the originating node 2103 for this announcement is taken from the prefix advertised by this 2104 Update if the Router-Id flag is set, computed as described above. 2105 Otherwise, it is taken either from the preceding Router-Id TLV, or 2106 the preceding Update TLV with the Router-Id flag set, whichever comes 2107 last, even if that TLV is otherwise ignored due to an unknown 2108 mandatory sub-TLV; if there is no suitable TLV, then this update is 2109 ignored. 2111 The next-hop address for this update is taken from the last preceding 2112 Next Hop TLV with a matching address family (IPv4 or IPv6) in the 2113 same packet even if it was otherwise ignored due to an unknown 2114 mandatory sub-TLV; if no such TLV exists, it is taken from the 2115 network-layer source address of this packet if it belongs to the same 2116 address family as the prefix being announced; otherwise, this Update 2117 MUST be ignored. 2119 If the metric field is FFFF hexadecimal, this TLV specifies a 2120 retraction. In that case, the router-id, next-hop and seqno are not 2121 used. AE MAY then be 0, in which case this Update retracts all of 2122 the routes previously advertised by the sending interface. If the 2123 metric is finite, AE MUST NOT be 0; Update TLVs with finite metric 2124 and AE equal to 0 MUST be ignored. If the metric is infinite and AE 2125 is 0, Plen and Omitted MUST both be 0; Update TLVs that do not 2126 satisfy this requirement MUST be ignored. 2128 Update TLVs with an unknown value in the AE field MUST be silently 2129 ignored. 2131 This TLV is self-terminating, and allows sub-TLVs. 2133 4.6.10. Route Request 2134 0 1 2 3 2135 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 2136 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2137 | Type = 9 | Length | AE | Plen | 2138 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2139 | Prefix... 2140 +-+-+-+-+-+-+-+-+-+-+-+- 2142 A Route Request TLV prompts the receiver to send an update for a 2143 given prefix, or a full route table dump. 2145 Fields : 2147 Type Set to 9 to indicate a Route Request TLV. 2149 Length The length of the body in octets, exclusive of the Type and 2150 Length fields. 2152 AE The encoding of the Prefix field. The value 0 specifies 2153 that this is a request for a full route table dump (a 2154 wildcard request). 2156 Plen The length in bits of the requested prefix. 2158 Prefix The prefix being requested. This field's size is Plen/8 2159 rounded upwards. 2161 A Request TLV prompts the receiver to send an update message 2162 (possibly a retraction) for the prefix specified by the AE, Plen, and 2163 Prefix fields, or a full dump of its route table if AE is 0 (in which 2164 case Plen must be 0 and Prefix is of length 0). A Request TLV with 2165 AE set to 0 and Plen not set to 0 MUST be ignored. 2167 This TLV is self-terminating, and allows sub-TLVs. 2169 4.6.11. Seqno Request 2170 0 1 2 3 2171 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 2172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2173 | Type = 10 | Length | AE | Plen | 2174 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2175 | Seqno | Hop Count | Reserved | 2176 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2177 | | 2178 + Router-Id + 2179 | | 2180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2181 | Prefix... 2182 +-+-+-+-+-+-+-+-+-+-+ 2184 A Seqno Request TLV prompts the receiver to send an Update for a 2185 given prefix with a given sequence number, or to forward the request 2186 further if it cannot be satisfied locally. 2188 Fields : 2190 Type Set to 10 to indicate a Seqno Request TLV. 2192 Length The length of the body in octets, exclusive of the Type and 2193 Length fields. 2195 AE The encoding of the Prefix field. This MUST NOT be 0. 2197 Plen The length in bits of the requested prefix. 2199 Seqno The sequence number that is being requested. 2201 Hop Count The maximum number of times that this TLV may be forwarded, 2202 plus 1. This MUST NOT be 0. 2204 Reserved Sent as 0 and MUST be ignored on reception. 2206 Router-Id The Router-Id that is being requested. This MUST NOT 2207 consist of all zeroes or all ones. 2209 Prefix The prefix being requested. This field's size is Plen/8 2210 rounded upwards. 2212 A Seqno Request TLV prompts the receiving node to send a finite- 2213 metric Update for the prefix specified by the AE, Plen, and Prefix 2214 fields, with either a router-id different from what is specified by 2215 the Router-Id field, or a Seqno no less (modulo 2^16) than what is 2216 specified by the Seqno field. If this request cannot be satisfied 2217 locally, then it is forwarded according to the rules set out in 2218 Section 3.8.1.2. 2220 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 2221 be forwarded to a multicast address and MUST NOT be forwarded to more 2222 than one neighbour. A request MUST NOT be forwarded if its Hop Count 2223 field is 1. 2225 This TLV is self-terminating, and allows sub-TLVs. 2227 4.7. Details of specific sub-TLVs 2229 4.7.1. Pad1 2231 0 1 2 3 4 5 6 7 2232 +-+-+-+-+-+-+-+-+ 2233 | Type = 0 | 2234 +-+-+-+-+-+-+-+-+ 2236 Fields : 2238 Type Set to 0 to indicate a Pad1 sub-TLV. 2240 This sub-TLV is silently ignored on reception. It is allowed within 2241 any TLV that allows sub-TLVs. 2243 4.7.2. PadN 2245 0 1 2 3 2246 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 2247 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2248 | Type = 1 | Length | MBZ... 2249 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 2251 Fields : 2253 Type Set to 1 to indicate a PadN sub-TLV. 2255 Length The length of the body in octets, exclusive of the Type and 2256 Length fields. 2258 MBZ Must be zero, set to 0 on transmission. 2260 This sub-TLV is silently ignored on reception. It is allowed within 2261 any TLV that allows sub-TLVs. 2263 5. IANA Considerations 2265 IANA has registered the UDP port number 6696, called "babel", for use 2266 by the Babel protocol. 2268 IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4 2269 multicast group 224.0.0.111 for use by the Babel protocol. 2271 IANA has created a registry called "Babel TLV Types". The allocation 2272 policy for this registry is Specification Required [RFC8126] for 2273 Types 0-223, and Experimental Use for Types 224-254. The values in 2274 this registry are as follows: 2276 +---------+-----------------------------------------+---------------+ 2277 | Type | Name | Reference | 2278 +---------+-----------------------------------------+---------------+ 2279 | 0 | Pad1 | this document | 2280 | | | | 2281 | 1 | PadN | this document | 2282 | | | | 2283 | 2 | Acknowledgment Request | this document | 2284 | | | | 2285 | 3 | Acknowledgment | this document | 2286 | | | | 2287 | 4 | Hello | this document | 2288 | | | | 2289 | 5 | IHU | this document | 2290 | | | | 2291 | 6 | Router-Id | this document | 2292 | | | | 2293 | 7 | Next Hop | this document | 2294 | | | | 2295 | 8 | Update | this document | 2296 | | | | 2297 | 9 | Route Request | this document | 2298 | | | | 2299 | 10 | Seqno Request | this document | 2300 | | | | 2301 | 11 | TS/PC | [RFC7298] | 2302 | | | | 2303 | 12 | HMAC | [RFC7298] | 2304 | | | | 2305 | 13 | Source-specific Update | [BABEL-SS] | 2306 | | | | 2307 | 14 | Source-specific Request | [BABEL-SS] | 2308 | | | | 2309 | 15 | Source-specific Seqno Request | [BABEL-SS] | 2310 | | | | 2311 | 16 | MAC | [BABEL-MAC] | 2312 | | | | 2313 | 17 | PC | [BABEL-MAC] | 2314 | | | | 2315 | 18 | Challenge Request | [BABEL-MAC] | 2316 | | | | 2317 | 19 | Challenge Reply | [BABEL-MAC] | 2318 | | | | 2319 | 20-223 | Unassigned | | 2320 | | | | 2321 | 224-254 | Reserved for Experimental Use | this document | 2322 | | | | 2323 | 255 | Reserved for expansion of the type | this document | 2324 | | space | | 2325 +---------+-----------------------------------------+---------------+ 2327 IANA has created a registry called "Babel sub-TLV Types". The 2328 allocation policy for this registry is Specification Required for 2329 Types 0-111 and 128-239, and Experimental Use for Types 112-126 and 2330 240-254. The values in this registry are as follows: 2332 +---------+-------------------------------------+-------------------+ 2333 | Type | Name | Reference | 2334 +---------+-------------------------------------+-------------------+ 2335 | 0 | Pad1 | this document | 2336 | | | | 2337 | 1 | PadN | this document | 2338 | | | | 2339 | 2 | Diversity | [BABEL-DIVERSITY] | 2340 | | | | 2341 | 3 | Timestamp | [BABEL-RTT] | 2342 | | | | 2343 | 4-111 | Unassigned | | 2344 | | | | 2345 | 112-126 | Reserved for Experimental Use | this document | 2346 | | | | 2347 | 127 | Reserved for expansion of the type | this document | 2348 | | space | | 2349 | | | | 2350 | 128 | Source Prefix | [BABEL-SS] | 2351 | | | | 2352 | 129-239 | Unassigned | | 2353 | | | | 2354 | 240-254 | Reserved for Experimental Use | this document | 2355 | | | | 2356 | 255 | Reserved for expansion of the type | this document | 2357 | | space | | 2358 +---------+-------------------------------------+-------------------+ 2359 IANA is instructed to create a registry called "Babel Address 2360 Encodings". The allocation policy for this registry is Specification 2361 Required for Address Encodings (AEs) 0-223, and Experimental Use for 2362 AEs 224-254. The values in this registry are as follows: 2364 +---------+----------------------------------------+---------------+ 2365 | AE | Name | Reference | 2366 +---------+----------------------------------------+---------------+ 2367 | 0 | Wildcard address | this document | 2368 | | | | 2369 | 1 | IPv4 address | this document | 2370 | | | | 2371 | 2 | IPv6 address | this document | 2372 | | | | 2373 | 3 | Link-local IPv6 address | this document | 2374 | | | | 2375 | 4-223 | Unassigned | | 2376 | | | | 2377 | 224-254 | Reserved for Experimental Use | this document | 2378 | | | | 2379 | 255 | Reserved for expansion of the AE space | this document | 2380 +---------+----------------------------------------+---------------+ 2382 IANA has created a registry called "Babel Flags Values". The 2383 allocation policy for this registry is Specification Required. IANA 2384 is instructed to rename this registry to "Babel Update Flags Values". 2385 The values in this registry are as follows: 2387 +-----+-------------------+---------------+ 2388 | Bit | Name | Reference | 2389 +-----+-------------------+---------------+ 2390 | 0 | Default prefix | this document | 2391 | | | | 2392 | 1 | Default Router-ID | this document | 2393 | | | | 2394 | 2-7 | Unassigned | | 2395 +-----+-------------------+---------------+ 2397 IANA is instructed to create a new registry called "Babel Hello Flags 2398 Values". The allocation policy for this registry is Specification 2399 Required. The initial values in this registry are as follows: 2401 +------+------------+---------------+ 2402 | Bit | Name | Reference | 2403 +------+------------+---------------+ 2404 | 0 | Unicast | this document | 2405 | | | | 2406 | 1-15 | Unassigned | | 2407 +------+------------+---------------+ 2409 IANA is instructed to replace all references to RFCs 6126 and 7557 in 2410 all of the registries mentioned above by references to this document. 2412 6. Security Considerations 2414 As defined in this document, Babel is a completely insecure protocol. 2415 Without additional security mechanisms, Babel trusts any information 2416 it receives in plaintext UDP datagrams and acts on it. An attacker 2417 that is present on the local network can impact Babel operation in a 2418 variety of ways; for example they can: 2420 o spoof a Babel packet, and redirect traffic by announcing a route 2421 with a smaller metric, a larger sequence number, or a longer 2422 prefix; 2424 o spoof a malformed packet, which could cause an insufficiently 2425 robust implementation to crash or interfere with the rest of the 2426 network; 2428 o replay a previously captured Babel packet, which could cause 2429 traffic to be redirected, blackholed or otherwise interfere with 2430 the network. 2432 When carried over IPv6, Babel packets are ignored unless they are 2433 sent from a link-local IPv6 address; since routers don't forward 2434 link-local IPv6 packets, this mitigates the attacks outlined above by 2435 restricting them to on-link attackers. No such natural protection 2436 exists when Babel packets are carried over IPv4, which is one of the 2437 reasons why it is recommended to deploy Babel over IPv6 2438 (Section 3.1). 2440 It is usually difficult to ensure that packets arriving at a Babel 2441 node are trusted, even in the case where the local link is believed 2442 to be secure. For that reason, it is RECOMMENDED that all Babel 2443 traffic be protected by an application-layer cryptographic protocol. 2444 There are currently two suitable mechanisms, which implement 2445 different tradeoffs between implementation simplicity and security: 2447 o Babel over DTLS [BABEL-DTLS] runs the majority of Babel traffic 2448 over DTLS, and leverages DTLS to authenticate nodes and provide 2449 confidentiality and integrity protection; 2451 o MAC authentication [BABEL-MAC] appends a message authentication 2452 code (MAC) to every Babel packet to prove that it originated at a 2453 node that knows a shared secret, and includes sufficient 2454 additional information to prove that the packet is fresh (not 2455 replayed). 2457 Both mechanisms enable nodes to ignore packets generated by attackers 2458 without the proper credentials. They also ensure integrity of 2459 messages and prevent message replay. While Babel-DTLS supports 2460 asymmetric keying and ensures confidentiality, Babel-MAC has a much 2461 more limited scope (see Sections 1.1, 1.2 and 7 of [BABEL-MAC]). 2462 Since Babel-MAC is simpler and more lightweight, it is recommended in 2463 preference to Babel-DTLS in deployments where its limitations are 2464 acceptable, i.e., when symmetric keying is sufficient and where the 2465 routing information is not considered confidential. 2467 Every implementation of Babel SHOULD implement BABEL-MAC. 2469 One should be aware that the information that a mobile Babel node 2470 announces to the whole routing domain is sufficient to determine the 2471 mobile node's physical location with reasonable precision, which 2472 might cause privacy concerns even if the control traffic is protected 2473 from unauthenticated attackers by a cryptographic mechanism such as 2474 Babel-DTLS. This issue may be mitigated somewhat by using randomly 2475 chosen router-ids and randomly chosen IP addresses, and changing them 2476 often enough. 2478 7. Acknowledgments 2480 A number of people have contributed text and ideas to this 2481 specification. The authors are particularly indebted to Matthieu 2482 Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke 2483 Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin 2484 Vigoureux. Earlier versions of this document greatly benefited from 2485 the input of Joel Halpern. The address compression technique was 2486 inspired by [PACKETBB]. 2488 8. References 2490 8.1. Normative References 2492 [BABEL-MAC] 2493 Do, C., Kolodziejak, W., and J. Chroboczek, "MAC 2494 authentication for the Babel routing protocol", Internet 2495 Draft draft-ietf-babel-hmac-10, August 2019. 2497 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2498 Requirement Levels", BCP 14, RFC 2119, 2499 DOI 10.17487/RFC2119, March 1997. 2501 [RFC793] Postel, J., "Transmission Control Protocol", RFC 793, 2502 DOI 10.17487/RFC0793, September 1981, 2503 . 2505 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2506 Writing an IANA Considerations Section in RFCs", BCP 26, 2507 RFC 8126, June 2017. 2509 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2510 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2511 May 2017. 2513 8.2. Informative References 2515 [BABEL-DIVERSITY] 2516 Chroboczek, J., "Diversity Routing for the Babel Routing 2517 Protocol", draft-chroboczek-babel-diversity-routing-01 2518 (work in progress), February 2016. 2520 [BABEL-DTLS] 2521 Decimo, A., Schinazi, D., and J. Chroboczek, "Babel 2522 Routing Protocol over Datagram Transport Layer Security", 2523 Internet Draft draft-ietf-babel-dtls-10, June 2020. 2525 [BABEL-RTT] 2526 Jonglez, B. and J. Chroboczek, "Delay-based Metric 2527 Extension for the Babel Routing Protocol", draft-ietf- 2528 babel-rtt-extension-00 (work in progress), April 2019. 2530 [BABEL-SS] 2531 Boutier, M. and J. Chroboczek, "Source-Specific Routing in 2532 Babel", draft-ietf-babel-source-specific-05 (work in 2533 progress), April 2019. 2535 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 2536 Sequenced Distance-Vector Routing (DSDV) for Mobile 2537 Computers", ACM SIGCOMM'94 Conference on Communications 2538 Architectures, Protocols and Applications 234-244, 1994. 2540 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 2541 Computations", IEEE/ACM Transactions on Networking 1:1, 2542 February 1993. 2544 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 2545 "EIGRP -- a Fast Routing Protocol Based on Distance 2546 Vectors", Proc. Interop 94, 1994. 2548 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 2549 high-throughput path metric for multi-hop wireless 2550 networks", Proc. MobiCom 2003, 2003. 2552 [IEEE802.11] 2553 IEEE, "IEEE Standard for Information technology-- 2554 Telecommunications and information exchange between 2555 systems Local and metropolitan area networks--Specific 2556 requirements Part 11: Wireless LAN Medium Access Control 2557 (MAC) and Physical Layer (PHY) Specifications", 2558 IEEE 802.11-2012, DOI 10.1109/ieeestd.2012.6178212, April 2559 2012. 2561 [IS-IS] Standardization, I. O. F., "Information technology -- 2562 Telecommunications and information exchange between 2563 systems -- Intermediate System to Intermediate System 2564 intra-domain routeing information exchange protocol for 2565 use in conjunction with the protocol for providing the 2566 connectionless-mode network service (ISO 8473)", ISO/ 2567 IEC 10589:2002, 2002. 2569 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 2570 periodic routing messages", IEEE/ACM Transactions on 2571 Networking 2, 2, 122-136, April 1994. 2573 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2575 [PACKETBB] 2576 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2577 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 2578 Format", RFC 5444, February 2009. 2580 [RFC2675] Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms", 2581 RFC 2675, DOI 10.17487/RFC2675, August 1999. 2583 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 2584 Demand Distance Vector (AODV) Routing", RFC 3561, 2585 DOI 10.17487/RFC3561, July 2003, 2586 . 2588 [RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 2589 DOI 10.17487/RFC6126, April 2011. 2591 [RFC7298] Ovsienko, D., "Babel Hashed Message Authentication Code 2592 (HMAC) Cryptographic Authentication", RFC 7298, 2593 DOI 10.17487/RFC7298, July 2014. 2595 [RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing 2596 Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015. 2598 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 2600 Appendix A. Cost and Metric Computation 2602 The strategy for computing link costs and route metrics is a local 2603 matter; Babel itself only requires that it comply with the conditions 2604 given in Section 3.4.3 and Section 3.5.2. Different nodes may use 2605 different strategies in a single network and may use different 2606 strategies on different interface types. This section describes a 2607 set of strategies that have been found to work well in actual 2608 networks. 2610 In summary, a node maintains per-neighbour statistics about the last 2611 16 received Hello TLVs of each kind (Appendix A.1), it computes costs 2612 by using the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and 2613 ETX (Appendix A.2.2) on wireless links. It uses an additive algebra 2614 for metric computation (Section 3.5.2). 2616 A.1. Maintaining Hello History 2618 For each neighbour, a node maintains two sets of Hello history, one 2619 for each kind of Hello, and an expected sequence number, one for 2620 Multicast and one for Unicast Hellos. Each Hello history is a vector 2621 of 16 bits, where a 1 value represents a received Hello, and a 0 2622 value a missed Hello. For each kind of Hello, the expected sequence 2623 number, written ne, is the sequence number that is expected to be 2624 carried by the next received Hello from this neighbour. 2626 Whenever it receives a Hello packet of a given kind from a neighbour, 2627 a node compares the received sequence number nr for that kind of 2628 Hello with its expected sequence number ne. Depending on the outcome 2629 of this comparison, one of the following actions is taken: 2631 o if the two differ by more than 16 (modulo 2^16), then the sending 2632 node has probably rebooted and lost its sequence number; the whole 2633 associated neighbour table entry is flushed and a new one is 2634 created; 2636 o otherwise, if the received nr is smaller (modulo 2^16) than the 2637 expected sequence number ne, then the sending node has increased 2638 its Hello interval without us noticing; the receiving node removes 2639 the last (ne - nr) entries from this neighbour's Hello history (we 2640 "undo history"); 2642 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 2643 node has decreased its Hello interval, and some Hellos were lost; 2644 the receiving node adds (nr - ne) 0 bits to the Hello history (we 2645 "fast-forward"). 2647 The receiving node then appends a 1 bit to the Hello history and sets 2648 ne to (nr + 1). If the Interval field of the received Hello is not 2649 zero, it resets the neighbour's hello timer to 1.5 times the 2650 advertised Interval (the extra margin allows for delay due to 2651 jitter). 2653 Whenever either Hello timer associated to a neighbour expires, the 2654 local node adds a 0 bit to the corresponding Hello history, and 2655 increments the expected Hello number. If both Hello histories are 2656 empty (they contain 0 bits only), the neighbour entry is flushed; 2657 otherwise, the relevant hello timer is reset to the value advertised 2658 in the last Hello of that kind received from this neighbour (no extra 2659 margin is necessary in this case, since jitter was already taken into 2660 account when computing the timeout that has just expired). 2662 A.2. Cost Computation 2664 This section describes two algorithms suitable for computing costs 2665 (Section 3.4.3) based on Hello history. Appendix A.2.1 applies to 2666 wired links, and Appendix A.2.2 to wireless links. RECOMMENDED 2667 default values of the parameters that appear in these algorithms are 2668 given in Appendix B. 2670 A.2.1. k-out-of-j 2672 K-out-of-j link sensing is suitable for wired links that are either 2673 up, in which case they only occasionally drop a packet, or down, in 2674 which case they drop all packets. 2676 The k-out-of-j strategy is parameterised by two small integers k and 2677 j, such that 0 < k <= j, and the nominal link cost, a constant C >= 2678 1. A node keeps a history of the last j hellos; if k or more of 2679 those have been correctly received, the link is assumed to be up, and 2680 the rxcost is set to C; otherwise, the link is assumed to be down, 2681 and the rxcost is set to infinity. 2683 Since Babel supports two kinds of Hellos, a Babel node performs k- 2684 out-of-j twice for each neighbour, once on the Unicast and once on 2685 the Multicast Hello history. If either of the instances of k-out- 2686 of-j indicates that the link is up, then the link is assumed to be 2687 up, and the rxcost is set to C; if both instances indicate that the 2688 link is down, then the link is assumed to be down, and the rxcost is 2689 set to infinity. In other words, the resulting rxcost is the minimum 2690 of the rxcosts yielded by the two instances of k-out-of-j link 2691 sensing. 2693 The cost of a link performing k-out-of-j link sensing is defined as 2694 follows: 2696 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 2698 o cost = txcost otherwise. 2700 A.2.2. ETX 2702 Unlike wired links which are bimodal (either up or down), wireless 2703 links exhibit continuous variation of the link quality. Naive 2704 application of hop-count routing in networks that use wireless links 2705 for transit tends to select long, lossy links in preference to 2706 shorter, lossless links, which can dramatically reduce throughput. 2707 For that reason, a routing protocol designed to support wireless 2708 links must perform some form of link-quality estimation. 2710 The Expected Transmission Cost algorithm, or ETX [ETX], is a simple 2711 link-quality estimation algorithm that is designed to work well with 2712 the IEEE 802.11 MAC [IEEE802.11]. By default, the IEEE 802.11 MAC 2713 performs Automatic Repeat Query (ARQ) and rate adaptation on unicast 2714 frames, but not on multicast frames, which are sent at a fixed rate 2715 with no ARQ; therefore, measuring the loss rate of multicast frames 2716 yields a useful estimate of a link's quality. 2718 A node performing ETX link quality estimation uses a neighbour's 2719 Multicast Hello history to compute an estimate, written beta, of the 2720 probability that a Hello TLV is successfully received. Beta can be 2721 computed as the fraction of 1 bits within a small number (say, 6) of 2722 the most recent entries in the Multicast Hello history, or it can be 2723 an exponential average, or some combination of both approaches. Let 2724 rxcost be 256 / beta. 2726 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2727 successfully sending a Hello TLV. The cost is then computed by 2729 cost = 256/(alpha * beta) 2731 or, equivalently, 2733 cost = (MAX(txcost, 256) * rxcost) / 256. 2735 Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast 2736 frames do not provide a useful measure of link quality, and therefore 2737 ETX ignores the Unicast Hello history. Thus, a node performing ETX 2738 link-quality estimation will not route through neighbouring nodes 2739 unless they send periodic Multicast Hellos (possibly in addition to 2740 Unicast Hellos). 2742 A.3. Route selection and hysteresis 2744 Route selection (Section 3.6) is the process by which a node selects 2745 a single route among the routes that it has available towards a given 2746 destination. With Babel, any route selection procedure that only 2747 ever chooses feasible routes with a finite metric will yield a set of 2748 loop-free routes; however, in the presence of continuously variable 2749 metrics such as ETX (Appendix A.2.2), a naive route selection 2750 procedure might lead to persistent oscillations. Such oscillations 2751 can be limited or avoided altogether by implementing hysteresis 2752 within the route selection algorithm, i.e., by making the route 2753 selection algorithm sensitive to a route's history. Any reasonable 2754 hysteresis algorithm should yield good results ; the following 2755 algorithm is simple to implement and has been successfully deployed 2756 in a variety of environments. 2758 For every route R, in addition to the route's metric m(R), maintain a 2759 smoothed version of m(R) written ms(R) (we RECOMMEND computing ms(R) 2760 as an exponentially smoothed average (see Section 3.7 of [RFC793]) of 2761 m(R) with a time constant equal to the Hello interval multiplied by a 2762 small number such as 3). If no route to a given destination is 2763 selected, then select the route with the smallest metric, ignoring 2764 the smoothed metric. If a route R is selected, then switch to a 2765 route R' only when both m(R') < m(R) and ms(R') < ms(R). 2767 Intuitively, the smoothed metric is a long-term estimate of the 2768 quality of a route. The algorithm above works by only switching 2769 routes when both the instantaneous and the long-term estimate of the 2770 route's quality indicate that switching is profitable. 2772 Appendix B. Protocol parameters 2774 The choice of time constants is a trade-off between fast detection of 2775 mobility events and protocol overhead. Two instances of Babel 2776 running with different time constants will interoperate, although the 2777 resulting worst-case convergence time will be dictated by the slower 2778 of the two. 2780 The Hello interval is the most important time constant: an outage or 2781 a mobility event is detected within 1.5 to 3.5 Hello intervals. Due 2782 to Babel's use of a redundant route table, and due to its reliance on 2783 triggered updates and explicit requests, the Update interval has 2784 little influence on the time needed to reconverge after an outage: in 2785 practice, it only has a significant effect on the time needed to 2786 acquire new routes after a mobility event. While the protocol allows 2787 intervals as low as 10ms, such low values would cause significant 2788 amounts of protocol traffic for little practical benefit. 2790 The following values have been found to work well in a variety of 2791 environments, and are therefore RECOMMENDED default values: 2793 Multicast Hello Interval: 4 seconds. 2795 Unicast Hello Interval: infinite (no Unicast Hellos are sent). 2797 Link cost: estimated using ETX on wireless links; 2-out-of-3 with 2798 C=96 on wired links. 2800 IHU Interval: the advertised IHU interval is always 3 times the 2801 Multicast Hello interval. IHUs are actually sent with each Hello 2802 on lossy links (as determined from the Hello history), but only 2803 with every third Multicast Hello on lossless links. 2805 Update Interval: 4 times the Multicast Hello interval. 2807 IHU Hold Time: 3.5 times the advertised IHU interval. 2809 Route Expiry Time: 3.5 times the advertised update interval. 2811 Request timeout: initially 2 seconds, doubled every time a request 2812 is resent, up to a maximum of three times. 2814 Urgent timeout: 0.2 seconds. 2816 Source GC time: 3 minutes. 2818 Appendix C. Route filtering 2820 Route filtering is a procedure where an instance of a routing 2821 protocol either discards some of the routes announced by its 2822 neighbours, or learns them with a metric that is higher than what 2823 would be expected. Like all distance-vector protocols, Babel has the 2824 ability to apply arbitrary filtering to the routes it learns, and 2825 implementations of Babel that apply different sets of filtering rules 2826 will interoperate without causing routing loops. The protocol's 2827 ability to perform route filtering is a consequence of the latitude 2828 given in Section 3.5.2: Babel can use any metric that is strictly 2829 monotonic, including one that assigns an infinite metric to a 2830 selected subset of routes. (See also Section 3.8.1, where requests 2831 for nonexistent routes are treated in the same way as requests for 2832 routes with infinite metric.) 2834 It is not in general correct to learn a route with a metric smaller 2835 than the one it was announced with, or to replace a route's 2836 destination prefix with a more specific (longer) one. Doing either 2837 of these may cause persistent routing loops. 2839 Route filtering is a useful tool, since it allows fine-grained tuning 2840 of the routing decisions made by the routing protocol. Accordingly, 2841 some implementations of Babel implement a rich configuration language 2842 that allows applying filtering to sets of routes defined, for 2843 example, by incoming interface and destination prefix. 2845 In order to limit the consequences of misconfiguration, Babel 2846 implementations provide a reasonable set of default filtering rules 2847 even when they don't allow configuration of filtering by the user. 2848 At a minimum, they discard routes with a destination prefix in 2849 fe80::/64, ff00::/8, 127.0.0.1/32, 0.0.0.0/32 and 224.0.0.0/8. 2851 Appendix D. Considerations for protocol extensions 2853 Babel is an extensible protocol, and this document defines a number 2854 of mechanisms that can be used to extend the protocol in a backwards 2855 compatible manner: 2857 o increasing the version number in the packet header; 2859 o defining new TLVs; 2861 o defining new sub-TLVs (with or without the mandatory bit set); 2863 o defining new AEs; 2865 o using the packet trailer. 2867 This appendix is intended to guide designers of protocol extensions 2868 in choosing a particular encoding. 2870 The version number in the Babel header should only be increased if 2871 the new version is not backwards compatible with the original 2872 protocol. 2874 In many cases, an extension could be implemented either by defining a 2875 new TLV, or by adding a new sub-TLV to an existing TLV. For example, 2876 an extension whose purpose is to attach additional data to route 2877 updates can be implemented either by creating a new "enriched" Update 2878 TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by 2879 adding a mandatory sub-TLV. 2881 The various encodings are treated differently by implementations that 2882 do not understand the extension. In the case of a new TLV or of a 2883 sub-TLV with the mandatory bit set, the whole TLV is ignored by 2884 implementations that do not implement the extension, while in the 2885 case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, 2886 and only the unknown sub-TLV is silently ignored. Therefore, a non- 2887 mandatory sub-TLV should be used by extensions that extend the Update 2888 in a compatible manner (the extension data may be silently ignored), 2889 while a mandatory sub-TLV or a new TLV must be used by extensions 2890 that make incompatible extensions to the meaning of the TLV (the 2891 whole TLV must be thrown away if the extension data is not 2892 understood). 2894 Experience shows that the need for additional data tends to crop up 2895 in the most unexpected places. Hence, it is recommended that 2896 extensions that define new TLVs should make them self-terminating, 2897 and allow attaching sub-TLVs to them. 2899 Adding a new AE is essentially equivalent to adding a new TLV: Update 2900 TLVs with an unknown AE are ignored, just like unknown TLVs. 2901 However, adding a new AE is more involved than adding a new TLV, 2902 since it creates a new set of compression state. Additionally, since 2903 the Next Hop TLV creates state specific to a given address family, as 2904 opposed to a given AE, a new AE for a previously defined address 2905 family must not be used in the Next Hop TLV if backwards 2906 compatibility is required. A similar issue arises with Update TLVs 2907 with unknown AEs establishing a new router-id (due to the Router-Id 2908 flag being set). Therefore, defining new AEs must be done with care 2909 if compatibility with unextended implementations is required. 2911 The packet trailer is intended to carry cryptographic signatures that 2912 only cover the packet body; storing the cryptographic signatures in 2913 the packet trailer avoids clearing the signature before computing a 2914 hash of the packet body, and makes it possible to check a 2915 cryptographic signature before running the full, stateful TLV parser. 2916 Hence, only TLVs that don't need to be protected by cryptographic 2917 security protocols should be allowed in the packet trailer. Any such 2918 TLVs should be easy to parse, and in particular should not require 2919 stateful parsing. 2921 Appendix E. Stub Implementations 2923 Babel is a fairly economic protocol. Updates take between 12 and 40 2924 octets per destination, depending on the address family and how 2925 successful compression is; in a double-stack flat network, an average 2926 of less than 24 octets per update is typical. The route table 2927 occupies about 35 octets per IPv6 entry. To put these values into 2928 perspective, a single full-size Ethernet frame can carry some 65 2929 route updates, and a megabyte of memory can contain a 20000-entry 2930 route table and the associated source table. 2932 Babel is also a reasonably simple protocol. One complete 2933 implementation consists of less than 12 000 lines of C code, and it 2934 compiles to less than 120 kB of text on a 32-bit CISC architecture; 2935 about half of this figure is due to protocol extensions and user- 2936 interface code. 2938 Nonetheless, in some very constrained environments, such as PDAs, 2939 microwave ovens, or abacuses, it may be desirable to have subset 2940 implementations of the protocol. 2942 There are many different definitions of a stub router, but for the 2943 needs of this section a stub implementation of Babel is one that 2944 announces one or more directly attached prefixes into a Babel network 2945 but doesn't reannounce any routes that it has learnt from its 2946 neighbours, and always prefers the direct route to a directly 2947 attached prefix to a route learned over the Babel protocol, even when 2948 the prefixes are the same. It may either maintain a full routing 2949 table, or simply select a default gateway through any one of its 2950 neighbours that announces a default route. Since a stub 2951 implementation never forwards packets except from or to a directly 2952 attached link, it cannot possibly participate in a routing loop, and 2953 hence it need not evaluate the feasibility condition or maintain a 2954 source table. 2956 No matter how primitive, a stub implementation must parse sub-TLVs 2957 attached to any TLVs that it understands and check the mandatory bit. 2958 It must answer acknowledgment requests and must participate in the 2959 Hello/IHU protocol. It must also be able to reply to seqno requests 2960 for routes that it announces and, and it should be able to reply to 2961 route requests. 2963 Experience shows that an IPv6-only stub implementation of Babel can 2964 be written in less than 1000 lines of C code and compile to 13 kB of 2965 text on 32-bit CISC architecture. 2967 Appendix F. Compatibility with previous versions 2969 The protocol defined in this document is a successor to the protocol 2970 defined in [RFC6126] and [RFC7557]. While the two protocols are not 2971 entirely compatible, the new protocol has been designed so that it 2972 can be deployed in existing RFC 6126 networks without requiring a 2973 flag day. 2975 There are three optional features that make this protocol 2976 incompatible with its predecessor. First of all, RFC 6126 did not 2977 define Unicast hellos (Section 3.4.1), and an implementation of RFC 2978 6126 will mis-interpret a Unicast Hello for a Multicast one; since 2979 the sequence number space of Unicast Hellos is distinct from the 2980 sequence space of Multicast Hellos, sending a Unicast Hello to an 2981 implementation of RFC 6126 will confuse its link quality estimator. 2982 Second, RFC 6126 did not define unscheduled Hellos, and an 2983 implementation of RFC 6126 will mis-parse Hellos with an interval 2984 equal to 0. Finally, RFC 7557 did not define mandatory sub-TLVs 2985 (Section 4.4), and thus, an implementation of RFCs 6126 and 7557 will 2986 not correctly ignore a TLV that carries an unknown mandatory sub-TLV; 2987 depending on the sub-TLV, this might cause routing pathologies. 2989 An implementation of this specification that never sends Unicast or 2990 unscheduled Hellos and doesn't implement any extensions that use 2991 mandatory sub-TLVs is safe to deploy in a network in which some nodes 2992 implement the protocol described in RFCs 6126 and 7557. 2994 Two changes need to be made to an implementation of RFCs 6126 and 2995 7557 so that it can safely interoperate in all cases with 2996 implementations of this protocol. First, it needs to be modified to 2997 either ignore or process Unicast and unscheduled Hellos. Second, it 2998 needs to be modified to parse sub-TLVs of all the TLVs that it 2999 understands and that allow sub-TLVs, and to ignore the TLV if an 3000 unknown mandatory sub-TLV is found. It is not necessary to parse 3001 unknown TLVs, as these are ignored in any case. 3003 There are other changes, but these are not of a nature to prevent 3004 interoperability: 3006 o the conditions on route acquisition (Section 3.5.3) have been 3007 relaxed; 3009 o route selection should no longer use the route's sequence number 3010 (Section 3.6); 3012 o the format of the packet trailer has been defined (Section 4.2); 3013 o router-ids with a value of all-zeros or all-ones have been 3014 forbidden (Section 4.1.2); 3016 o the compression state is now specific to an address family rather 3017 than an address encoding (Section 4.5); 3019 o packet pacing is now recommended (Section 3.1). 3021 Appendix G. Changes from previous versions 3023 [RFC Editor: Please delete this section before publication.] 3025 G.1. Changes since RFC 6126 3027 o Changed UDP port number to 6696. 3029 o Consistently use router-id rather than id. 3031 o Clarified that the source garbage collection timer is reset after 3032 sending an update even if the entry was not modified. 3034 o In section "Seqno Requests", fixed an erroneous "route request". 3036 o In the description of the Seqno Request TLV, added the description 3037 of the Router-Id field. 3039 o Made router-ids all-0 and all-1 forbidden. 3041 G.2. Changes since draft-ietf-babel-rfc6126bis-00 3043 o Added security considerations. 3045 G.3. Changes since draft-ietf-babel-rfc6126bis-01 3047 o Integrated the format of sub-TLVs. 3049 o Mentioned for each TLV whether it supports sub-TLVs. 3051 o Added Appendix D. 3053 o Added a mandatory bit in sub-TLVs. 3055 o Changed compression state to be per-AF rather than per-AE. 3057 o Added implementation hint for the routing table. 3059 o Clarified how router-ids are computed when bit 0x40 is set in 3060 Updates. 3062 o Relaxed the conditions for sending requests, and tightened the 3063 conditions for forwarding requests. 3065 o Clarified that neighbours should be acquired at some point, but it 3066 doesn't matter when. 3068 G.4. Changes since draft-ietf-babel-rfc6126bis-02 3070 o Added Unicast Hellos. 3072 o Added unscheduled (interval-less) Hellos. 3074 o Changed Appendix A to consider Unicast and unscheduled Hellos. 3076 o Changed Appendix B to agree with the reference implementation. 3078 o Added optional algorithm to avoid the hold time. 3080 o Changed the table of pending seqno requests to be indexed by 3081 router-id in addition to prefixes. 3083 o Relaxed the route acquisition algorithm. 3085 o Replaced minimal implementations by stub implementations. 3087 o Added acknowledgments section. 3089 G.5. Changes since draft-ietf-babel-rfc6126bis-03 3091 o Clarified that all the data structures are conceptual. 3093 o Made sending and receiving Multicast Hellos a SHOULD, avoids 3094 expressing any opinion about Unicast Hellos. 3096 o Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4). 3098 o Made hold-time into a SHOULD rather than MUST. 3100 o Clarified that Seqno Requests are for a finite-metric Update. 3102 o Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV 3103 that allows sub-TLVs. 3105 o Updated IANA Considerations. 3107 o Updated Security Considerations. 3109 o Renamed routing table back to route table. 3111 o Made buffering outgoing updates a SHOULD. 3113 o Weakened advice to use modified EUI-64 in router-ids. 3115 o Added information about sending requests to Appendix B. 3117 o A number of minor wording changes and clarifications. 3119 G.6. Changes since draft-ietf-babel-rfc6126bis-03 3121 Minor editorial changes. 3123 G.7. Changes since draft-ietf-babel-rfc6126bis-04 3125 o Renamed isotonicity to left-distributivity. 3127 o Minor clarifications to unicast hellos. 3129 o Updated requirements boilerplate to RFC 8174. 3131 o Minor editorial changes. 3133 G.8. Changes since draft-ietf-babel-rfc6126bis-05 3135 o Added information about the packet trailer, now that it is used by 3136 draft-ietf-babel-hmac. 3138 G.9. Changes since draft-ietf-babel-rfc6126bis-06 3140 o Added references to security documents. 3142 G.10. Changes since draft-ietf-babel-rfc6126bis-07 3144 o Added list of obsoleted drafts to the abstract. 3146 o Updated references. 3148 G.11. Changes since draft-ietf-babel-rfc6126bis-08 3150 o Added recommendation that route selection should not take seqnos 3151 into account. 3153 G.12. Changes since draft-ietf-babel-rfc6126bis-09 3155 o Editorial changes only. 3157 G.13. Changes since draft-ietf-babel-rfc6126bis-10 3159 o Editorial changes only. 3161 G.14. Changes since draft-ietf-babel-rfc6126bis-11 3163 o Added recommendation that control traffic should be carried over 3164 IPv6 only. 3166 G.15. Changes since draft-ietf-babel-rfc6126bis-12 3168 o Removed appendix about software availability. 3170 o Expanded appendix about recommended values and added more 3171 references to it in the body of the document. 3173 o Added appendix about route filtering. 3175 o Clarified definition of mandatory bit. 3177 o Added recommendations for packet pacing. 3179 o Made time limiting of full updates a SHOULD. 3181 o Normative language in a few more places. 3183 o Removed normative language from stub implementations. 3185 o Added requirement to clear the undefined bits in an Update. 3187 o Added error checking requirements. 3189 o Reworked security considerations. 3191 o Added "in octets" and "in bits" in random places. 3193 o Inserted full IANA registries. 3195 o Editorial changes. 3197 G.16. Changes since draft-ietf-babel-rfc6126bis-13 3199 o Added a section about compatibility with 6126. 3201 o Added AE registry to IANA considerations. 3203 o Replaced Babel-HMAC with Babel-MAC, consistent with the change in 3204 draft-ietf-babel-hmac. 3206 o Removed section about external sources of willingness; filtering 3207 is a better approach. 3209 o Added recommendation to use a cost of 96 on wired links. 3211 o Editorial changes. 3213 G.17. Changes since draft-ietf-babel-rfc6126bis-14 3215 o Added unscheduled Hellos to compatibility considerations. 3217 o Created new appendix about route selection. 3219 o Reworked security considerations. 3221 o Added some comments about packet pacing and low update intervals. 3223 G.18. Changes since draft-ietf-babel-rfc6126bis-15 3225 o Implementing Babel-MAC is now recommended. 3227 G.19. Changes since draft-ietf-babel-rfc6126bis-16 3229 o Make the values in Appendix B normatively recommended defaults. 3231 G.20. Changes since draft-ietf-babel-rfc6126bis-17 3233 o Hysteresis in route selection is now RECOMMENDED. 3235 o Additive metric algebra is now RECOMMENDED default. 3237 o 2-out-of-3 cost computation is now RECOMMENDED on LANs. 3239 o Reference to RFC 793 Section 3.7 added as exponential smoothing 3240 example. 3242 G.21. Changes since draft-ietf-babel-rfc6126bis-18 3244 o Reserved Address Encodings 224-254 for Experimental Use, and 255 3245 for future expansion. 3247 Authors' Addresses 3248 Juliusz Chroboczek 3249 IRIF, University of Paris-Diderot 3250 Case 7014 3251 75205 Paris Cedex 13 3252 France 3254 Email: jch@irif.fr 3256 David Schinazi 3257 Google LLC 3258 1600 Amphitheatre Parkway 3259 Mountain View, California 94043 3260 USA 3262 Email: dschinazi.ietf@gmail.com