idnits 2.17.1 draft-ietf-babel-rfc6126bis-14.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 17, 2019) is 1715 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 == Outdated reference: A later version (-10) exists of draft-ietf-babel-dtls-09 == 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: 0 errors (**), 0 flaws (~~), 7 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 18, 2020 August 17, 2019 8 The Babel Routing Protocol 9 draft-ietf-babel-rfc6126bis-14 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 18, 2020. 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 55 1.3. Specification of Requirements . . . . . . . . . . . . . . 5 56 2. Conceptual Description of the Protocol . . . . . . . . . . . 5 57 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 58 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . 47 82 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 83 6. Security Considerations . . . . . . . . . . . . . . . . . . . 51 84 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 52 85 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 52 86 8.1. Normative References . . . . . . . . . . . . . . . . . . 53 87 8.2. Informative References . . . . . . . . . . . . . . . . . 53 88 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 55 89 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 55 90 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 56 91 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 57 92 Appendix B. Protocol parameters . . . . . . . . . . . . . . . . 58 93 Appendix C. Route filtering . . . . . . . . . . . . . . . . . . 59 94 Appendix D. Considerations for protocol extensions . . . . . . . 60 95 Appendix E. Stub Implementations . . . . . . . . . . . . . . . . 61 96 Appendix F. Compatibility with previous versions . . . . . . . . 62 97 Appendix G. Changes from previous versions . . . . . . . . . . . 63 98 G.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 63 99 G.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 64 100 G.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 64 101 G.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 64 102 G.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 65 103 G.6. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 65 104 G.7. Changes since draft-ietf-babel-rfc6126bis-04 . . . . . . 65 105 G.8. Changes since draft-ietf-babel-rfc6126bis-05 . . . . . . 66 106 G.9. Changes since draft-ietf-babel-rfc6126bis-06 . . . . . . 66 107 G.10. Changes since draft-ietf-babel-rfc6126bis-07 . . . . . . 66 108 G.11. Changes since draft-ietf-babel-rfc6126bis-08 . . . . . . 66 109 G.12. Changes since draft-ietf-babel-rfc6126bis-09 . . . . . . 66 110 G.13. Changes since draft-ietf-babel-rfc6126bis-10 . . . . . . 66 111 G.14. Changes since draft-ietf-babel-rfc6126bis-11 . . . . . . 66 112 G.15. Changes since draft-ietf-babel-rfc6126bis-12 . . . . . . 66 113 G.16. Changes since draft-ietf-babel-rfc6126bis-13 . . . . . . 67 114 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 67 116 1. Introduction 118 Babel is a loop-avoiding distance-vector routing protocol that is 119 designed to be robust and efficient both in networks using prefix- 120 based routing and in networks using flat routing ("mesh networks"), 121 and both in relatively stable wired networks and in highly dynamic 122 wireless networks. This document describes the Babel routing 123 protocol, and obsoletes [RFC6126] and [RFC7557]. 125 1.1. Features 127 The main property that makes Babel suitable for unstable networks is 128 that, unlike naive distance-vector routing protocols [RIP], it 129 strongly limits the frequency and duration of routing pathologies 130 such as routing loops and black-holes during reconvergence. Even 131 after a mobility event is detected, a Babel network usually remains 132 loop-free. Babel then quickly reconverges to a configuration that 133 preserves the loop-freedom and connectedness of the network, but is 134 not necessarily optimal; in many cases, this operation requires no 135 packet exchanges at all. Babel then slowly converges, in a time on 136 the scale of minutes, to an optimal configuration. This is achieved 137 by using sequenced routes, a technique pioneered by Destination- 138 Sequenced Distance-Vector routing [DSDV]. 140 More precisely, Babel has the following properties: 142 o when every prefix is originated by at most one router, Babel never 143 suffers from routing loops; 145 o when a single prefix is originated by multiple routers, Babel may 146 occasionally create a transient routing loop for this particular 147 prefix; this loop disappears in time proportional to the loop's 148 diameter, and never again (up to an arbitrary garbage-collection 149 (GC) time) will the routers involved participate in a routing loop 150 for the same prefix; 152 o assuming bounded packet loss rates, any routing black-holes that 153 may appear after a mobility event are corrected in a time at most 154 proportional to the network's diameter. 156 Babel has provisions for link quality estimation and for fairly 157 arbitrary metrics. When configured suitably, Babel can implement 158 shortest-path routing, or it may use a metric based, for example, on 159 measured packet loss. 161 Babel nodes will successfully establish an association even when they 162 are configured with different parameters. For example, a mobile node 163 that is low on battery may choose to use larger time constants (hello 164 and update intervals, etc.) than a node that has access to wall 165 power. Conversely, a node that detects high levels of mobility may 166 choose to use smaller time constants. The ability to build such 167 heterogeneous networks makes Babel particularly adapted to the 168 unmanaged and wireless environment. 170 Finally, Babel is a hybrid routing protocol, in the sense that it can 171 carry routes for multiple network-layer protocols (IPv4 and IPv6), 172 regardless of which protocol the Babel packets are themselves being 173 carried over. 175 1.2. Limitations 177 Babel has two limitations that make it unsuitable for use in some 178 environments. First, Babel relies on periodic routing table updates 179 rather than using a reliable transport; hence, in large, stable 180 networks it generates more traffic than protocols that only send 181 updates when the network topology changes. In such networks, 182 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 183 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 184 suitable. 186 Second, unless the second algorithm described in Section 3.5.4 is 187 implemented, Babel does impose a hold time when a prefix is 188 retracted. While this hold time does not apply to the exact prefix 189 being retracted, and hence does not prevent fast reconvergence should 190 it become available again, it does apply to any shorter prefix that 191 covers it. This may make those implementations of Babel that do not 192 implement the optional algorithm described in Section 3.5.4 193 unsuitable for use in networks that implement automatic prefix 194 aggregation. 196 1.3. Specification of Requirements 198 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 199 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 200 "OPTIONAL" in this document are to be interpreted as described in BCP 201 14 [RFC2119] [RFC8174] when, and only when, they appear in all 202 capitals, as shown here. 204 2. Conceptual Description of the Protocol 206 Babel is a loop-avoiding distance vector protocol: it is based on the 207 Bellman-Ford algorithm, just like the venerable RIP [RIP], but 208 includes a number of refinements that either prevent loop formation 209 altogether, or ensure that a loop disappears in a timely manner and 210 doesn't form again. 212 Conceptually, Bellman-Ford is executed in parallel for every source 213 of routing information (destination of data traffic). In the 214 following discussion, we fix a source S; the reader will recall that 215 the same algorithm is executed for all sources. 217 2.1. Costs, Metrics and Neighbourship 219 For every pair of neighbouring nodes A and B, Babel computes an 220 abstract value known as the cost of the link from A to B, written 221 C(A, B). Given a route between any two (not necessarily 222 neighbouring) nodes, the metric of the route is the sum of the costs 223 of all the links along the route. The goal of the routing algorithm 224 is to compute, for every source S, the tree of routes of lowest 225 metric to S. 227 Costs and metrics need not be integers. In general, they can be 228 values in any algebra that satisfies two fairly general conditions 229 (Section 3.5.2). 231 A Babel node periodically sends Hello messages to all of its 232 neighbours; it also periodically sends an IHU ("I Heard You") message 233 to every neighbour from which it has recently heard a Hello. From 234 the information derived from Hello and IHU messages received from its 235 neighbour B, a node A computes the cost C(A, B) of the link from A to 236 B. 238 2.2. The Bellman-Ford Algorithm 240 Every node A maintains two pieces of data: its estimated distance to 241 S, written D(A), and its next-hop router to S, written NH(A). 242 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 244 Periodically, every node B sends to all of its neighbours a route 245 update, a message containing D(B). When a neighbour A of B receives 246 the route update, it checks whether B is its selected next hop; if 247 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 248 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 249 its current value of D(A). If that value is smaller, meaning that 250 the received update advertises a route that is better than the 251 currently selected route, then NH(A) is set to B, and D(A) is set to 252 C(A, B) + D(B). 254 A number of refinements to this algorithm are possible, and are used 255 by Babel. In particular, convergence speed may be increased by 256 sending unscheduled "triggered updates" whenever a major change in 257 the topology is detected, in addition to the regular, scheduled 258 updates. Additionally, a node may maintain a number of alternate 259 routes, which are being advertised by neighbours other than its 260 selected neighbour, and which can be used immediately if the selected 261 route were to fail. 263 2.3. Transient Loops in Bellman-Ford 265 It is well known that a naive application of Bellman-Ford to 266 distributed routing can cause transient loops after a topology 267 change. Consider for example the following topology: 269 B 270 1 /| 271 1 / | 272 S --- A |1 273 \ | 274 1 \| 275 C 277 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 279 Suppose now that the link between S and A fails: 281 B 282 1 /| 283 / | 284 S A |1 285 \ | 286 1 \| 287 C 289 When it detects the failure of the link, A switches its next hop to B 290 (which is still advertising a route to S with metric 2), and 291 advertises a metric equal to 3, and then advertises a new route with 292 metric 3. This process of nodes changing selected neighbours and 293 increasing their metric continues until the advertised metric reaches 294 "infinity", a value larger than all the metrics that the routing 295 protocol is able to carry. 297 2.4. Feasibility Conditions 299 Bellman-Ford is a very robust algorithm: its convergence properties 300 are preserved when routers delay route acquisition or when they 301 discard some updates. Babel routers discard received route 302 announcements unless they can prove that accepting them cannot 303 possibly cause a routing loop. 305 More formally, we define a condition over route announcements, known 306 as the "feasibility condition", that guarantees the absence of 307 routing loops whenever all routers ignore route updates that do not 308 satisfy the feasibility condition. In effect, this makes Bellman- 309 Ford into a family of routing algorithms, parameterised by the 310 feasibility condition. 312 Many different feasibility conditions are possible. For example, BGP 313 can be modelled as being a distance-vector protocol with a (rather 314 drastic) feasibility condition: a routing update is only accepted 315 when the receiving node's AS number is not included in the update's 316 AS-Path attribute (note that BGP's feasibility condition does not 317 ensure the absence of transient "micro-loops" during reconvergence). 319 Another simple feasibility condition, used in the Destination- 320 Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the 321 Ad hoc On-Demand Distance Vector (AODV) protocol [RFC3561], stems 322 from the following observation: a routing loop can only arise after a 323 router has switched to a route with a larger metric than the route 324 that it had previously selected. Hence, one may define that a route 325 is feasible when its metric at the local node would be no larger than 326 the metric of the currently selected route, i.e., an announcement 327 carrying a metric D(B) is accepted by A when C(A, B) + D(B) <= D(A). 328 If all routers obey this constraint, then the metric at every router 329 is nonincreasing, and the following invariant is always preserved: if 330 A has selected B as its next hop, then D(B) < D(A), which implies 331 that the forwarding graph is loop-free. 333 Babel uses a slightly more refined feasibility condition, derived 334 from EIGRP [DUAL]. Given a router A, define the feasibility distance 335 of A, written FD(A), as the smallest metric that A has ever 336 advertised for S to any of its neighbours. An update sent by a 337 neighbour B of A is feasible when the metric D(B) advertised by B is 338 strictly smaller than A's feasibility distance, i.e., when D(B) < 339 FD(A). 341 It is easy to see that this latter condition is no more restrictive 342 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 343 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 344 Suppose now that A receives a DSDV-feasible update that advertises a 345 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 346 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 348 To see that it is strictly less restrictive, consider the following 349 diagram, where A has selected the route through B, and D(A) = FD(A) = 350 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 351 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 352 the currently selected route: 354 B 355 1 / \ 1 356 / \ 357 S A 358 \ / 359 1 \ / 4 360 C 362 To show that this feasibility condition still guarantees loop- 363 freedom, recall that at the time when A accepts an update from B, the 364 metric D(B) announced by B is no smaller than FD(B); since it is 365 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 366 property is preserved both when A sends updates and when it picks a 367 different next hop, it remains true at all times, which ensures that 368 the forwarding graph has no loops. 370 2.5. Solving Starvation: Sequencing Routes 372 Obviously, the feasibility conditions defined above cause starvation 373 when a router runs out of feasible routes. Consider the following 374 diagram, where both A and B have selected the direct route to S: 376 A 377 1 /| D(A) = 1 378 / | FD(A) = 1 379 S |1 380 \ | D(B) = 2 381 2 \| FD(B) = 2 382 B 384 Suppose now that the link between A and S breaks: 386 A 387 | 388 | FD(A) = 1 389 S |1 390 \ | D(B) = 2 391 2 \| FD(B) = 2 392 B 394 The only route available from A to S, the one that goes through B, is 395 not feasible: A suffers from spurious starvation. At that point, the 396 whole subtree suffering from starvation must be reset, which is 397 essentially what EIGRP does when it performs a global synchronisation 398 of all the routers in the starving subtree (the "active" phase of 399 EIGRP). 401 Babel reacts to starvation in a less drastic manner, by using 402 sequenced routes, a technique introduced by DSDV and adopted by AODV. 403 In addition to a metric, every route carries a sequence number, a 404 nondecreasing integer that is propagated unchanged through the 405 network and is only ever incremented by the source; a pair (s, m), 406 where s is a sequence number and m a metric, is called a distance. 408 A received update is feasible when either it is more recent than the 409 feasibility distance maintained by the receiving node, or it is 410 equally recent and the metric is strictly smaller. More formally, if 411 FD(A) = (s, m), then an update carrying the distance (s', m') is 412 feasible when either s' > s, or s = s' and m' < m. 414 Assuming the sequence number of S is 137, the diagram above becomes: 416 A 417 | 418 | FD(A) = (137, 1) 419 S |1 420 \ | D(B) = (137, 2) 421 2 \| FD(B) = (137, 2) 422 B 424 After S increases its sequence number, and the new sequence number is 425 propagated to B, we have: 427 A 428 | 429 | FD(A) = (137, 1) 430 S |1 431 \ | D(B) = (138, 2) 432 2 \| FD(B) = (138, 2) 433 B 435 at which point the route through B becomes feasible again. 437 Note that while sequence numbers are used for determining 438 feasibility, they are not used in route selection: a node ignores the 439 sequence number when selecting the best route to a given destination 440 (Section 3.6). Doing otherwise would cause route oscillation while a 441 sequence number propagates through the network, and might even cause 442 persistent blackholes with some exotic metrics. 444 2.6. Requests 446 In DSDV, the sequence number of a source is increased periodically. 447 A route becomes feasible again after the source increases its 448 sequence number, and the new sequence number is propagated through 449 the network, which may, in general, require a significant amount of 450 time. 452 Babel takes a different approach. When a node detects that it is 453 suffering from a potentially spurious starvation, it sends an 454 explicit request to the source for a new sequence number. This 455 request is forwarded hop by hop to the source, with no regard to the 456 feasibility condition. Upon receiving the request, the source 457 increases its sequence number and broadcasts an update, which is 458 forwarded to the requesting node. 460 Note that after a change in network topology not all such requests 461 will, in general, reach the source, as some will be sent over links 462 that are now broken. However, if the network is still connected, 463 then at least one among the nodes suffering from spurious starvation 464 has an (unfeasible) route to the source; hence, in the absence of 465 packet loss, at least one such request will reach the source. 466 (Resending requests a small number of times compensates for packet 467 loss.) 469 Since requests are forwarded with no regard to the feasibility 470 condition, they may, in general, be caught in a forwarding loop; this 471 is avoided by having nodes perform duplicate detection for the 472 requests that they forward. 474 2.7. Multiple Routers 476 The above discussion assumes that each prefix is originated by a 477 single router. In real networks, however, it is often necessary to 478 have a single prefix originated by multiple routers: for example, the 479 default route will be originated by all of the edge routers of a 480 routing domain. 482 Since synchronising sequence numbers between distinct routers is 483 problematic, Babel treats routes for the same prefix as distinct 484 entities when they are originated by different routers: every route 485 announcement carries the router-id of its originating router, and 486 feasibility distances are not maintained per prefix, but per source, 487 where a source is a pair of a router-id and a prefix. In effect, 488 Babel guarantees loop-freedom for the forwarding graph to every 489 source; since the union of multiple acyclic graphs is not in general 490 acyclic, Babel does not in general guarantee loop-freedom when a 491 prefix is originated by multiple routers, but any loops will be 492 broken in a time at most proportional to the diameter of the loop -- 493 as soon as an update has "gone around" the routing loop. 495 Consider for example the following topology, where A has selected the 496 default route through S, and B has selected the one through S': 498 1 1 1 499 ::/0 -- S --- A --- B --- S' -- ::/0 501 Suppose that both default routes fail at the same time; then nothing 502 prevents A from switching to B, and B simultaneously switching to A. 503 However, as soon as A has successfully advertised the new route to B, 504 the route through A will become unfeasible for B. Conversely, as 505 soon as B will have advertised the route through A, the route through 506 B will become unfeasible for A. 508 In effect, the routing loop disappears at the latest when routing 509 information has gone around the loop. Since this process can be 510 delayed by lost packets, Babel makes certain efforts to ensure that 511 updates are sent reliably after a router-id change (Section 3.7.2). 513 Additionally, after the routers have advertised the two routes, both 514 sources will be in their source tables, which will prevent them from 515 ever again participating in a routing loop involving routes from S 516 and S' (up to the source GC time, which, available memory permitting, 517 can be set to arbitrarily large values). 519 2.8. Overlapping Prefixes 521 In the above discussion, we have assumed that all prefixes are 522 disjoint, as is the case in flat ("mesh") routing. In practice, 523 however, prefixes may overlap: for example, the default route 524 overlaps with all of the routes present in the network. 526 After a route fails, it is not correct in general to switch to a 527 route that subsumes the failed route. Consider for example the 528 following configuration: 530 1 1 531 ::/0 -- A --- B --- C 533 Suppose that node C fails. If B forwards packets destined to C by 534 following the default route, a routing loop will form, and persist 535 until A learns of B's retraction of the direct route to C. B avoids 536 this pitfall by installing an "unreachable" route after a route is 537 retracted; this route is maintained until it can be guaranteed that 538 the former route has been retracted by all of B's neighbours 539 (Section 3.5.4). 541 3. Protocol Operation 543 Every Babel speaker is assigned a router-id, which is an arbitrary 544 string of 8 octets that is assumed unique across the routing domain. 545 For example, router-ids could be assigned randomly, or they could be 546 derived from a link-layer address. (The protocol encoding is 547 slightly more compact when router-ids are assigned in the same manner 548 as the IPv6 layer assigns host IDs, see the definition of the "R" 549 flag in Section 4.6.9.) 551 3.1. Message Transmission and Reception 553 Babel protocol packets are sent in the body of a UDP datagram (as 554 described in Section 4 below). Each Babel packet consists of zero or 555 more TLVs. Most TLVs may contain sub-TLVs. 557 The protocol's control traffic can be carried indifferently over IPv6 558 or over IPv4, and prefixes of either address family can be announced 559 over either protocol. Thus, there are at least two natural 560 deployment models: using IPv6 exclusively for all control traffic, or 561 running two distinct protocol instances, one for each address family. 562 The exclusive use of IPv6 for all control traffic is RECOMMENDED, 563 since using both protocols at the same time doubles the amount of 564 traffic devoted to neighbour discovery and link quality estimation. 566 The source address of a Babel packet is always a unicast address, 567 link-local in the case of IPv6. Babel packets may be sent to a well- 568 known (link-local) multicast address or to a (link-local) unicast 569 address. In normal operation, a Babel speaker sends both multicast 570 and unicast packets to its neighbours. 572 With the exception of acknowledgments, all Babel TLVs can be sent to 573 either unicast or multicast addresses, and their semantics does not 574 depend on whether the destination is a unicast or a multicast 575 address. Hence, a Babel speaker does not need to determine the 576 destination address of a packet that it receives in order to 577 interpret it. 579 A moderate amount of jitter may be applied to packets sent by a Babel 580 speaker: outgoing TLVs are buffered and SHOULD be sent with a random 581 delay. This is done for two purposes: it avoids synchronisation of 582 multiple Babel speakers across a network [JITTER], and it allows for 583 the aggregation of multiple TLVs into a single packet. 585 The maximum amount of delay a TLV can be subjected to depends on the 586 TLV. When the protocol description specifies that a TLV is urgent 587 (as in Section 3.7.2 and Section 3.8.2), then the TLV MUST be sent 588 within a short time known as the urgent timeout (see Appendix B for 589 recommended values). When the TLV is governed by a timeout 590 explicitly included in a previous TLV, (such as in the case of 591 Acknowledgements Section 4.6.4), Updates (Section 3.7 and IHUs 592 (Section 3.4.2), then the TLV MUST be sent early enough to meet the 593 explicit deadline (with a small margin to allow for propagation 594 delays). In all other cases, the TLV SHOULD be sent out within one- 595 half of the Multicast Hello interval. 597 In order to avoid packet drops (either at the sender or at the 598 receiver), a delay SHOULD be introduced between successive packets 599 sent out on the same interface, within the constraints of the 600 previous paragraph. 602 3.2. Data Structures 604 In this section, we give a description of the data structures that 605 every Babel speaker maintains. This description is conceptual: a 606 Babel speaker may use different data structures as long as the 607 resulting protocol is the same as the one described in this document. 608 For example, rather than maintaining a single table containing both 609 selected and unselected (fallback) routes, as described in 610 Section 3.2.6 below, an actual implementation would probably use two 611 tables, one with selected routes and one with fallback routes. 613 3.2.1. Sequence number arithmetic 615 Sequence numbers (seqnos) appear in a number of Babel data 616 structures, and they are interpreted as integers modulo 2^16. For 617 the purposes of this document, arithmetic on sequence numbers is 618 defined as follows. 620 Given a seqno s and a non-negative integer n, the sum of s and n is 621 defined by 623 s + n (modulo 2^16) = (s + n) MOD 2^16 625 or, equivalently, 627 s + n (modulo 2^16) = (s + n) AND 65535 629 where MOD is the modulo operation yielding a non-negative integer and 630 AND is the bitwise conjunction operation. 632 Given two sequence numbers s and s', the relation s is less than s' 633 (s < s') is defined by 635 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 637 or equivalently 639 s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. 641 3.2.2. Node Sequence Number 643 A node's sequence number is a 16-bit integer that is included in 644 route updates sent for routes originated by this node. 646 A node increments its sequence number (modulo 2^16) whenever it 647 receives a request for a new sequence number (Section 3.8.1.2). A 648 node SHOULD NOT increment its sequence number (seqno) spontaneously, 649 since increasing seqnos makes it less likely that other nodes will 650 have feasible alternate routes when their selected routes fail. 652 3.2.3. The Interface Table 654 The interface table contains the list of interfaces on which the node 655 speaks the Babel protocol. Every interface table entry contains the 656 interface's outgoing Multicast Hello seqno, a 16-bit integer that is 657 sent with each Multicast Hello TLV on this interface and is 658 incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note 659 that an interface's Multicast Hello seqno is unrelated to the node's 660 seqno.) 661 There are two timers associated with each interface table entry. The 662 periodic Multicast Hello timer governs the sending of scheduled 663 Multicast Hello and IHU packets (Section 3.4. The periodic Update 664 timer governs the sending of periodic route updates (Section 3.7.1). 665 See Appendix B for suggested time constants. 667 3.2.4. The Neighbour Table 669 The neighbour table contains the list of all neighbouring interfaces 670 from which a Babel packet has been recently received. The neighbour 671 table is indexed by pairs of the form (interface, address), and every 672 neighbour table entry contains the following data: 674 o the local node's interface over which this neighbour is reachable; 676 o the address of the neighbouring interface; 678 o a history of recently received Multicast Hello packets from this 679 neighbour; this can, for example, be a sequence of n bits, for 680 some small value n, indicating which of the n hellos most recently 681 sent by this neighbour have been received by the local node; 683 o a history of recently received Unicast Hello packets from this 684 neighbour; 686 o the "transmission cost" value from the last IHU packet received 687 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 688 hold timer for this neighbour has expired; 690 o the expected incoming Multicast Hello sequence number for this 691 neighbour, an integer modulo 2^16. 693 o the expected incoming Unicast Hello sequence number for this 694 neighbour, an integer modulo 2^16. 696 o the outgoing Unicast Hello sequence number for this neighbour, an 697 integer modulo 2^16 that is sent with each Unicast Hello TLV to 698 this neighbour and is incremented (modulo 2^16) whenever a Unicast 699 Hello is sent. (Note that the outgoing Unicast Hello seqno for a 700 neighbour is distinct from the interface's outgoing Multicast 701 Hello seqno.) 703 There are three timers associated with each neighbour entry -- the 704 multicast hello timer, which is set to the interval value carried by 705 scheduled Multicast Hello TLVs sent by this neighbour, the unicast 706 hello timer, which is set to the interval value carried by scheduled 707 Unicast Hello TLVs, and the IHU timer, which is set to a small 708 multiple of the interval carried in IHU TLVs (see "IHU Hold time" in 709 Appendix B for suggested values). 711 Note that the neighbour table is indexed by IP addresses, not by 712 router-ids: neighbourship is a relationship between interfaces, not 713 between nodes. Therefore, two nodes with multiple interfaces can 714 participate in multiple neighbourship relationships, a situation that 715 can notably arise when wireless nodes with multiple radios are 716 involved. 718 3.2.5. The Source Table 720 The source table is used to record feasibility distances. It is 721 indexed by triples of the form (prefix, plen, router-id), and every 722 source table entry contains the following data: 724 o the prefix (prefix, plen), where plen is the prefix length in 725 bits, that this entry applies to; 727 o the router-id of a router originating this prefix; 729 o a pair (seqno, metric), this source's feasibility distance. 731 There is one timer associated with each entry in the source table -- 732 the source garbage-collection timer. It is initialised to a time on 733 the order of minutes and reset as specified in Section 3.7.3. 735 3.2.6. The Route Table 737 The route table contains the routes known to this node. It is 738 indexed by triples of the form (prefix, plen, neighbour), and every 739 route table entry contains the following data: 741 o the source (prefix, plen, router-id) for which this route is 742 advertised; 744 o the neighbour (an entry in the neighbour table) that advertised 745 this route; 747 o the metric with which this route was advertised by the neighbour, 748 or FFFF hexadecimal (infinity) for a recently retracted route; 750 o the sequence number with which this route was advertised; 752 o the next-hop address of this route; 753 o a boolean flag indicating whether this route is selected, i.e., 754 whether it is currently being used for forwarding and is being 755 advertised. 757 There is one timer associated with each route table entry -- the 758 route expiry timer. It is initialised and reset as specified in 759 Section 3.5.3. 761 Note that there are two distinct (seqno, metric) pairs associated to 762 each route: the route's distance, which is stored in the route table, 763 and the feasibility distance, stored in the source table and shared 764 between all routes with the same source. 766 3.2.7. The Table of Pending Seqno Requests 768 The table of pending seqno requests contains a list of seqno requests 769 that the local node has sent (either because they have been 770 originated locally, or because they were forwarded) and to which no 771 reply has been received yet. This table is indexed by triples of the 772 form (prefix, plen, router-id), and every entry in this table 773 contains the following data: 775 o the prefix, plen, router-id, and seqno being requested; 777 o the neighbour, if any, on behalf of which we are forwarding this 778 request; 780 o a small integer indicating the number of times that this request 781 will be resent if it remains unsatisfied. 783 There is one timer associated with each pending seqno request; it 784 governs both the resending of requests and their expiry. 786 3.3. Acknowledgments and acknowledgment requests 788 A Babel speaker may request that a neighbour receiving a given packet 789 reply with an explicit acknowledgment within a given time. While the 790 use of acknowledgment requests is optional, every Babel speaker MUST 791 be able to reply to such a request. 793 An acknowledgment MUST be sent to a unicast destination. On the 794 other hand, acknowledgment requests may be sent to either unicast or 795 multicast destinations, in which case they request an acknowledgment 796 from all of the receiving nodes. 798 When to request acknowledgments is a matter of local policy; the 799 simplest strategy is to never request acknowledgments and to rely on 800 periodic updates to ensure that any reachable routes are eventually 801 propagated throughout the routing domain. In order to improve 802 convergence speed and reduce the amount of control traffic, 803 acknowledgment requests MAY be used in order to reliably send urgent 804 updates (Section 3.7.2) and retractions (Section 3.5.4), especially 805 when the number of neighbours on a given interface is small. Since 806 Babel is designed to deal gracefully with packet loss on unreliable 807 media, sending all packets with acknowledgment requests is not 808 necessary, and NOT RECOMMENDED, as the acknowledgments cause 809 additional traffic and may force additional Address Resolution 810 Protocol (ARP) or Neighbour Discovery (ND) exchanges. 812 3.4. Neighbour Acquisition 814 Neighbour acquisition is the process by which a Babel node discovers 815 the set of neighbours heard over each of its interfaces and 816 ascertains bidirectional reachability. On unreliable media, 817 neighbour acquisition additionally provides some statistics that may 818 be useful for link quality computation. 820 Before it can exchange routing information with a neighbour, a Babel 821 node MUST create an entry for that neighbour in the neighbour table. 822 When to do that is implementation-specific; suitable strategies 823 include creating an entry when any Babel packet is received, or 824 creating an entry when a Hello TLV is parsed. Similarly, in order to 825 conserve system resources, an implementation SHOULD discard an entry 826 when it has been unused for long enough; suitable strategies include 827 dropping the neighbour after a timeout, and dropping a neighbour when 828 the associated Hello histories become empty (see Appendix A.2). 830 3.4.1. Reverse Reachability Detection 832 Every Babel node sends Hello TLVs to its neighbours to indicate that 833 it is alive, at regular or irregular intervals. Each Hello TLV 834 carries an increasing (modulo 2^16) sequence number and an upper 835 bound on the time interval until the next Hello of the same type (see 836 below). If the time interval is set to 0, then the Hello TLV does 837 not establish a new promise: the deadline carried by the previous 838 Hello of the same type still applies to the next Hello (if the most 839 recent scheduled Hello of the right kind was received at time t0 and 840 carried interval i, then the previous promise of sending another 841 Hello before time t0 + i still holds). We say that a Hello is 842 "scheduled" if it carries a non-zero interval, and "unscheduled" 843 otherwise. 845 There are two kinds of Hellos: Multicast Hellos, which use a per- 846 interface Hello counter (the Multicast Hello seqno), and Unicast 847 Hellos, which use a per-neighbour counter (the Unicast Hello seqno). 848 A Multicast Hello with a given seqno MUST be sent to all neighbours 849 on a given interface, either by sending it to a multicast address or 850 by sending it to one unicast address per neighbour (hence, the term 851 "Multicast Hello" is a slight misnomer). A Unicast Hello carrying a 852 given seqno should normally be sent to just one neighbour (over 853 unicast), since the sequence numbers of different neighbours are not 854 in general synchronised. 856 Multicast Hellos sent over multicast can be used for neighbour 857 discovery; hence, a node SHOULD send periodic (scheduled) Multicast 858 Hellos unless neighbour discovery is performed by means outside of 859 the Babel protocol. A node MAY send Unicast Hellos or unscheduled 860 Hellos of either kind for any reason, such as reducing the amount of 861 multicast traffic or improving reliability on link technologies with 862 poor support for link-layer multicast. 864 A node MAY send a scheduled Hello ahead of time. A node MAY change 865 its scheduled Hello interval. The Hello interval MAY be decreased at 866 any time; it MAY be increased immediately before sending a Hello TLV, 867 but SHOULD NOT be increased at other times. (Equivalently, a node 868 SHOULD send a scheduled Hello immediately after increasing its Hello 869 interval.) 871 How to deal with received Hello TLVs and what statistics to maintain 872 are considered local implementation matters; typically, a node will 873 maintain some sort of history of recently received Hellos. An 874 example of a suitable algorithm is described in Appendix A.1. 876 After receiving a Hello, or determining that it has missed one, the 877 node recomputes the association's cost (Section 3.4.3) and runs the 878 route selection procedure (Section 3.6). 880 3.4.2. Bidirectional Reachability Detection 882 In order to establish bidirectional reachability, every node sends 883 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 884 IHUs carry an explicit interval value, they MAY be sent less often 885 than Hellos in order to reduce the amount of routing traffic in dense 886 networks; in particular, they SHOULD be sent less often than Hellos 887 over links with little packet loss. While IHUs are conceptually 888 unicast, they MAY be sent to a multicast address in order to avoid an 889 ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 890 into a single packet. 892 In addition to the periodic IHUs, a node MAY, at any time, send an 893 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 894 interval, and it MAY increase its IHU interval immediately before 895 sending an IHU, but SHOULD NOT increase it at any other time. 897 (Equivalently, a node SHOULD send an extra IHU immediately after 898 increasing its Hello interval.) 900 Every IHU TLV contains two pieces of data: the link's rxcost 901 (reception cost) from the sender's perspective, used by the neighbour 902 for computing link costs (Section 3.4.3), and the interval between 903 periodic IHU packets. A node receiving an IHU sets the value of the 904 txcost (transmission cost) maintained in the neighbour table to the 905 value contained in the IHU, and resets the IHU timer associated to 906 this neighbour to a small multiple of the interval value received in 907 the IHU (see "IHU Hold time" in Appendix B for suggested values). 908 When a neighbour's IHU timer expires, the neighbour's txcost is set 909 to infinity. 911 After updating a neighbour's txcost, the receiving node recomputes 912 the neighbour's cost (Section 3.4.3) and runs the route selection 913 procedure (Section 3.6). 915 3.4.3. Cost Computation 917 A neighbourship association's link cost is computed from the values 918 maintained in the neighbour table: the statistics kept in the 919 neighbour table about the reception of Hellos, and the txcost 920 computed from received IHU packets. 922 For every neighbour, a Babel node computes a value known as this 923 neighbour's rxcost. This value is usually derived from the Hello 924 history, which may be combined with other data, such as statistics 925 maintained by the link layer. The rxcost is sent to a neighbour in 926 each IHU. 928 Since nodes do not necessarily send periodic Unicast Hellos but do 929 usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD 930 use an algorithm that yields a finite rxcost when only Multicast 931 Hellos are received, unless interoperability with nodes that only 932 send Multicast Hellos is not required. 934 How the txcost and rxcost are combined in order to compute a link's 935 cost is a matter of local policy; as far as Babel's correctness is 936 concerned, only the following conditions MUST be satisfied: 938 o the cost is strictly positive; 940 o if no Hello TLVs of either kind were received recently, then the 941 cost is infinite; 943 o if the txcost is infinite, then the cost is infinite. 945 Note that while this document does not constrain cost computation any 946 further, not all cost computation strategies will give good results. 947 See Appendix A.2 for examples of strategies for computing a link's 948 cost that are known to work well in practice. 950 3.5. Routing Table Maintenance 952 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 953 seqno, metric), where (prefix, plen) is the prefix for which a route 954 is being advertised, router-id is the router-id of the router 955 originating this update, seqno is a nondecreasing (modulo 2^16) 956 integer that carries the originating router seqno, and metric is the 957 announced metric. 959 Before being accepted, an update is checked against the feasibility 960 condition (Section 3.5.1), which ensures that the route does not 961 create a routing loop. If the feasibility condition is not 962 satisfied, the update is either ignored or prevents the route from 963 being selected, as described in Section 3.5.3. If the feasibility 964 condition is satisfied, then the update cannot possibly cause a 965 routing loop. 967 3.5.1. The Feasibility Condition 969 The feasibility condition is applied to all received updates. The 970 feasibility condition compares the metric in the received update with 971 the metrics of the updates previously sent by the receiving node; 972 updates that fail the feasibility condition, and therefore have 973 metrics large enough to cause a routing loop, are either ignored or 974 prevent the resulting route from being selected. 976 A feasibility distance is a pair (seqno, metric), where seqno is an 977 integer modulo 2^16 and metric is a positive integer. Feasibility 978 distances are compared lexicographically, with the first component 979 inverted: we say that a distance (seqno, metric) is strictly better 980 than a distance (seqno', metric'), written 982 (seqno, metric) < (seqno', metric') 984 when 986 seqno > seqno' or (seqno = seqno' and metric < metric') 988 where sequence numbers are compared modulo 2^16. 990 Given a source (prefix, plen, router-id), a node's feasibility 991 distance for this source is the minimum, according to the ordering 992 defined above, of the distances of all the finite updates ever sent 993 by this particular node for the prefix (prefix, plen) and the given 994 router-id. Feasibility distances are maintained in the source table, 995 the exact procedure is given in Section 3.7.3. 997 A received update is feasible when either it is a retraction (its 998 metric is FFFF hexadecimal), or the advertised distance is strictly 999 better, in the sense defined above, than the feasibility distance for 1000 the corresponding source. More precisely, a route advertisement 1001 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 1002 feasible if one of the following conditions holds: 1004 o metric is infinite; or 1006 o no entry exists in the source table indexed by (prefix, plen, 1007 router-id); or 1009 o an entry (prefix, plen, router-id, seqno', metric') exists in the 1010 source table, and either 1012 * seqno' < seqno or 1014 * seqno = seqno' and metric < metric'. 1016 Note that the feasibility condition considers the metric advertised 1017 by the neighbour, not the route's metric; hence, a fluctuation in a 1018 neighbour's cost cannot render a selected route unfeasible. Note 1019 further that retractions (updates with infinite metric) are always 1020 feasible, since they cannot possibly cause a routing loop. 1022 3.5.2. Metric Computation 1024 A route's metric is computed from the metric advertised by the 1025 neighbour and the neighbour's link cost. Just like cost computation, 1026 metric computation is considered a local policy matter; as far as 1027 Babel is concerned, the function M(c, m) used for computing a metric 1028 from a locally computed link cost c and the metric m advertised by a 1029 neighbour MUST only satisfy the following conditions: 1031 o if c is infinite, then M(c, m) is infinite; 1033 o M is strictly monotonic: M(c, m) > m. 1035 Additionally, the metric SHOULD satisfy the following condition: 1037 o M is left-distributive: if m <= m', then M(c, m) <= M(c, m'). 1039 Note that while strict monotonicity is essential to the integrity of 1040 the network (persistent routing loops may arise if it is not 1041 satisfied), left distributivity is not: if it is not satisfied, Babel 1042 will still converge to a loop-free configuration, but might not reach 1043 a global optimum (in fact, a global optimum may not even exist). 1045 As with cost computation, not all strategies for computing route 1046 metrics will give good results. In particular, some metrics are more 1047 likely than others to lead to routing instabilities (route flapping). 1048 In Appendix A.3, we give an number of examples of strictly monotonic, 1049 left-distributive routing metrics that are known to work well in 1050 practice. See also Appendix C, which describes a useful way to make 1051 the metric computation configurable by a network administrator. 1053 3.5.3. Route Acquisition 1055 When a Babel node receives an update (prefix, plen, router-id, seqno, 1056 metric) from a neighbour neigh, it checks whether it already has a 1057 route table entry indexed by (prefix, plen, neigh). 1059 If no such entry exists: 1061 o if the update is unfeasible, it MAY be ignored; 1063 o if the metric is infinite (the update is a retraction of a route 1064 we do not know about), the update is ignored; 1066 o otherwise, a new entry is created in the route table, indexed by 1067 (prefix, plen, neigh), with source equal to (prefix, plen, router- 1068 id), seqno equal to seqno and an advertised metric equal to the 1069 metric carried by the update. 1071 If such an entry exists: 1073 o if the entry is currently selected, the update is unfeasible, and 1074 the router-id of the update is equal to the router-id of the 1075 entry, then the update MAY be ignored; 1077 o otherwise, the entry's sequence number, advertised metric, metric, 1078 and router-id are updated and, if the advertised metric is not 1079 infinite, the route's expiry timer is reset to a small multiple of 1080 the Interval value included in the update (see "Route Hold time" 1081 in Appendix B for suggested values). If the update is unfeasible, 1082 then the (now unfeasible) entry MUST be immediately unselected. 1083 If the update caused the router-id of the entry to change, an 1084 update (possibly a retraction) MUST be sent in a timely manner as 1085 described in Section 3.7.2. 1087 Note that the route table may contain unfeasible routes, either 1088 because they were created by an unfeasible update or due to a metric 1089 fluctuation. Such routes are never selected, since they are not 1090 known to be loop-free; should all the feasible routes become 1091 unusable, however, the unfeasible routes can be made feasible and 1092 therefore possible to select by sending requests along them (see 1093 Section 3.8.2). 1095 When a route's expiry timer triggers, the behaviour depends on 1096 whether the route's metric is finite. If the metric is finite, it is 1097 set to infinity and the expiry timer is reset. If the metric is 1098 already infinite, the route is flushed from the route table. 1100 After the route table is updated, the route selection procedure 1101 (Section 3.6) is run. 1103 3.5.4. Hold Time 1105 When a prefix P is retracted, because all routes are unfeasible or 1106 have an infinite metric (whether due to the expiry timer or to other 1107 reasons), and a shorter prefix P' that covers P is reachable, P' 1108 cannot in general be used for routing packets destined to P without 1109 running the risk of creating a routing loop (Section 2.8). 1111 To avoid this issue, whenever a prefix P is retracted, a route table 1112 entry with infinite metric is maintained as described in 1113 Section 3.5.3 above. As long as this entry is maintained, packets 1114 destined to an address within P MUST NOT be forwarded by following a 1115 route for a shorter prefix. This entry is removed as soon as a 1116 finite-metric update for prefix P is received and the resulting route 1117 selected. If no such update is forthcoming, the infinite metric 1118 entry SHOULD be maintained at least until it is guaranteed that no 1119 neighbour has selected the current node as next-hop for prefix P. 1120 This can be achieved by either: 1122 o waiting until the route's expiry timer has expired 1123 (Section 3.5.3); 1125 o sending a retraction with an acknowledgment request (Section 3.3) 1126 to every reachable neighbour that has not explicitly retracted 1127 prefix P, and waiting for all acknowledgments. 1129 The former option is simpler and ensures that at that point, any 1130 routes for prefix P pointing at the current node have expired. 1131 However, since the expiry time can be as high as a few minutes, doing 1132 that prevents automatic aggregation by creating spurious black-holes 1133 for aggregated routes. The latter option is RECOMMENDED as it 1134 dramatically reduces the time for which a prefix is unreachable in 1135 the presence of aggregated routes. 1137 3.6. Route Selection 1139 Route selection is the process by which a single route for a given 1140 prefix is selected to be used for forwarding packets and to be re- 1141 advertised to a node's neighbours. 1143 Babel is designed to allow flexible route selection policies. As far 1144 as the algorithm's correctness is concerned, the route selection 1145 policy MUST only satisfy the following properties: 1147 o a route with infinite metric (a retracted route) is never 1148 selected; 1150 o an unfeasible route is never selected. 1152 Note, however, that Babel does not naturally guarantee the stability 1153 of routing, and configuring conflicting route selection policies on 1154 different routers may lead to persistent route oscillation. 1156 Route selection is a difficult problem, since a good route selection 1157 policy needs to take into account multiple mutually contradictory 1158 criteria; in roughly decreasing order of importance, these are: 1160 o routes with a small metric should be preferred to routes with a 1161 large metric; 1163 o switching router-ids should be avoided; 1165 o routes through stable neighbours should be preferred to routes 1166 through unstable ones; 1168 o stable routes should be preferred to unstable ones; 1170 o switching next hops should be avoided. 1172 Route selection MUST NOT take seqnos into account: a route MUST NOT 1173 be preferred just because it carries a higher (more recent) seqno. 1174 Doing otherwise would cause route oscillation while a new seqno 1175 propagates through the network, possibly following multiple paths of 1176 different latency, and might even create persistent blackholes if the 1177 metric being used is not left-distributive (Section 3.5.2). 1179 A simple but useful strategy is to choose the feasible route with the 1180 smallest metric, with a small amount of hysteresis applied to avoid 1181 switching router-ids too often. 1183 After the route selection procedure is run, triggered updates 1184 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1186 3.7. Sending Updates 1188 A Babel speaker advertises to its neighbours its set of selected 1189 routes. Normally, this is done by sending one or more multicast 1190 packets containing Update TLVs on all of its connected interfaces; 1191 however, on link technologies where multicast is significantly more 1192 expensive than unicast, a node MAY choose to send multiple copies of 1193 updates in unicast packets, especially when the number of neighbours 1194 is small. 1196 Additionally, in order to ensure that any black-holes are reliably 1197 cleared in a timely manner, a Babel node may send retractions 1198 (updates with an infinite metric) for any recently retracted 1199 prefixes. 1201 If an update is for a route injected into the Babel domain by the 1202 local node (e.g., it carries the address of a local interface, the 1203 prefix of a directly attached network, or a prefix redistributed from 1204 a different routing protocol), the router-id is set to the local 1205 node's router-id, the metric is set to some arbitrary finite value 1206 (typically 0), and the seqno is set to the local router's sequence 1207 number. 1209 If an update is for a route learned from another Babel speaker, the 1210 router-id and sequence number are copied from the route table entry, 1211 and the metric is computed as specified in Section 3.5.2. 1213 3.7.1. Periodic Updates 1215 Every Babel speaker MUST advertise each of its selected routes on 1216 every interface, at least once every Update interval. Since Babel 1217 doesn't suffer from routing loops (there is no "counting to 1218 infinity") and relies heavily on triggered updates (Section 3.7.2), 1219 this full dump only needs to happen infrequently (see Appendix B for 1220 suggested intervals). 1222 3.7.2. Triggered Updates 1224 In addition to periodic routing updates, a Babel speaker sends 1225 unscheduled, or triggered, updates in order to inform its neighbours 1226 of a significant change in the network topology. 1228 A change of router-id for the selected route to a given prefix may be 1229 indicative of a routing loop in formation; hence, whenever it changes 1230 the selected router-id for a given destination, a node MUST send an 1231 update as an urgent TLV (as defined in Section 3.1). Additionally, 1232 it SHOULD make a reasonable attempt at ensuring that all reachable 1233 neighbours receive this update. 1235 There are two strategies for ensuring that. If the number of 1236 neighbours is small, then it is reasonable to send the update 1237 together with an acknowledgment request; the update is resent until 1238 all neighbours have acknowledged the packet, up to some number of 1239 times. If the number of neighbours is large, however, requesting 1240 acknowledgments from all of them might cause a non-negligible amount 1241 of network traffic; in that case, it may be preferable to simply 1242 repeat the update some reasonable number of times (say, 3 for 1243 wireless and 2 for wired links). The number of copies MUST NOT 1244 exceed 5, and the copies SHOULD be separated by a small delay, as 1245 described in Section 3.1. 1247 A route retraction is somewhat less worrying: if the route retraction 1248 doesn't reach all neighbours, a black-hole might be created, which, 1249 unlike a routing loop, does not endanger the integrity of the 1250 network. When a route is retracted, a node SHOULD send a triggered 1251 update and SHOULD make a reasonable attempt at ensuring that all 1252 neighbours receive this retraction. 1254 Finally, a node MAY send a triggered update when the metric for a 1255 given prefix changes in a significant manner, due to a received 1256 update, because a link's cost has changed, or because a different 1257 next hop has been selected. A node SHOULD NOT send triggered updates 1258 for other reasons, such as when there is a minor fluctuation in a 1259 route's metric, when the selected next hop changes, or to propagate a 1260 new sequence number (except to satisfy a request, as specified in 1261 Section 3.8). 1263 3.7.3. Maintaining Feasibility Distances 1265 Before sending an update (prefix, plen, router-id, seqno, metric) 1266 with finite metric (i.e., not a route retraction), a Babel node 1267 updates the feasibility distance maintained in the source table. 1268 This is done as follows. 1270 If no entry indexed by (prefix, plen, router-id) exists in the source 1271 table, then one is created with value (prefix, plen, router-id, 1272 seqno, metric). 1274 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1275 it is updated as follows: 1277 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1279 o if seqno = seqno' and metric' > metric, then metric' := metric; 1281 o otherwise, nothing needs to be done. 1283 The garbage-collection timer for the entry is then reset. Note that 1284 the feasibility distance is not updated and the garbage-collection 1285 timer is not reset when a retraction (an update with infinite metric) 1286 is sent. 1288 When the garbage-collection timer expires, the entry is removed from 1289 the source table. 1291 3.7.4. Split Horizon 1293 When running over a transitive, symmetric link technology, e.g., a 1294 point-to-point link or a wired LAN technology such as Ethernet, a 1295 Babel node SHOULD use an optimisation known as split horizon. When 1296 split horizon is used on a given interface, a routing update for 1297 prefix P is not sent on the particular interface over which the 1298 selected route towards prefix P was learnt. 1300 Split horizon SHOULD NOT be applied to an interface unless the 1301 interface is known to be symmetric and transitive; in particular, 1302 split horizon is not applicable to decentralised wireless link 1303 technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates 1304 are sent over multicast. 1306 3.8. Explicit Requests 1308 In normal operation, a node's route table is populated by the regular 1309 and triggered updates sent by its neighbours. Under some 1310 circumstances, however, a node sends explicit requests in order to 1311 cause a resynchronisation with the source after a mobility event or 1312 to prevent a route from spuriously expiring. 1314 The Babel protocol provides two kinds of explicit requests: route 1315 requests, which simply request an update for a given prefix, and 1316 seqno requests, which request an update for a given prefix with a 1317 specific sequence number. The former are never forwarded; the latter 1318 are forwarded if they cannot be satisfied by the receiver. 1320 3.8.1. Handling Requests 1322 Upon receiving a request, a node either forwards the request or sends 1323 an update in reply to the request, as described in the following 1324 sections. If this causes an update to be sent, the update is either 1325 sent to a multicast address on the interface on which the request was 1326 received, or to the unicast address of the neighbour that sent the 1327 request. 1329 The exact behaviour is different for route requests and seqno 1330 requests. 1332 3.8.1.1. Route Requests 1334 When a node receives a route request for a given prefix, it checks 1335 its route table for a selected route to this exact prefix. If such a 1336 route exists, it MUST send an update (over unicast or over 1337 multicast); if such a route does not exist, it MUST send a retraction 1338 for that prefix. 1340 When a node receives a wildcard route request, it SHOULD send a full 1341 route table dump. Full route dumps SHOULD be rate-limited, 1342 especially if they are sent over multicast. 1344 3.8.1.2. Seqno Requests 1346 When a node receives a seqno request for a given router-id and 1347 sequence number, it checks whether its route table contains a 1348 selected entry for that prefix. If a selected route for the given 1349 prefix exists, it has finite metric, and either the router-ids are 1350 different or the router-ids are equal and the entry's sequence number 1351 is no smaller (modulo 2^16) than the requested sequence number, the 1352 node MUST send an update for the given prefix. If the router-ids 1353 match but the requested seqno is larger (modulo 2^16) than the route 1354 entry's, the node compares the router-id against its own router-id. 1355 If the router-id is its own, then it increases its sequence number by 1356 1 (modulo 2^16) and sends an update. A node MUST NOT increase its 1357 sequence number by more than 1 in reaction to a single seqno request. 1359 Otherwise, if the requested router-id is not its own, the received 1360 node consults the hop count field of the request. If the hop count 1361 is 2 or more, and the node is advertising the prefix to its 1362 neighbours, the node selects a neighbour to forward the request to as 1363 follows: 1365 o if the node has one or more feasible routes toward the requested 1366 prefix with a next hop that is not the requesting node, then the 1367 node MUST forward the request to the next hop of one such route; 1369 o otherwise, if the node has one or more (not feasible) routes to 1370 the requested prefix with a next hop that is not the requesting 1371 node, then the node SHOULD forward the request to the next hop of 1372 one such route. 1374 In order to actually forward the request, the node decrements the hop 1375 count and sends the request in a unicast packet destined to the 1376 selected neighbour. The forwarded request SHOULD be sent as an 1377 urgent TLV (as defined in Section 3.1). 1379 A node SHOULD maintain a list of recently forwarded seqno requests 1380 and forward the reply (an update with a seqno sufficiently large to 1381 satisfy the request) as an urgent TLV (as defined in Section 3.1). A 1382 node SHOULD compare every incoming seqno request against its list of 1383 recently forwarded seqno requests and avoid forwarding it if it is 1384 redundant (i.e., if it has recently sent a request with the same 1385 prefix, router-id and a seqno that is not smaller modulo 2^16). 1387 Since the request-forwarding mechanism does not necessarily obey the 1388 feasibility condition, it may get caught in routing loops; hence, 1389 requests carry a hop count to limit the time during which they remain 1390 in the network. However, since requests are only ever forwarded as 1391 unicast packets, the initial hop count need not be kept particularly 1392 low, and performing an expanding horizon search is not necessary. A 1393 single request MUST NOT be duplicated: it MUST NOT be forwarded to a 1394 multicast address, and it MUST NOT be forwarded to multiple 1395 neighbours. However, if a seqno request is resent by its originator, 1396 the subsequent copies may be forwarded to a different neighbour than 1397 the initial one. 1399 3.8.2. Sending Requests 1401 A Babel node MAY send a route or seqno request at any time, to a 1402 multicast or a unicast address; there is only one case when 1403 originating requests is required (Section 3.8.2.1). 1405 3.8.2.1. Avoiding Starvation 1407 When a route is retracted or expires, a Babel node usually switches 1408 to another feasible route for the same prefix. It may be the case, 1409 however, that no such routes are available. 1411 A node that has lost all feasible routes to a given destination but 1412 still has unexpired unfeasible routes to that destination MUST send a 1413 seqno request; if it doesn't have any such routes, it MAY still send 1414 a seqno request. The router-id of the request is set to the router- 1415 id of the route that it has just lost, and the requested seqno is the 1416 value contained in the source table plus 1. The request carries a 1417 hop count, which is used as a last-resort mechanism to ensure that it 1418 eventually vanishes from the network; it MAY be set to any value that 1419 is larger than the diameter of the network (64 is a suitable default 1420 value). 1422 If the node has any (unfeasible) routes to the requested destination, 1423 then it MUST send the request to at least one of the next-hop 1424 neighbours that advertised these routes, and SHOULD send it to all of 1425 them; in any case, it MAY send the request to any other neighbours, 1426 whether they advertise a route to the requested destination or not. 1428 A simple implementation strategy is therefore to unconditionally 1429 multicast the request over all interfaces. 1431 Similar requests will be sent by other nodes that are affected by the 1432 route's loss. If the network is still connected, and assuming no 1433 packet loss, then at least one of these requests will be forwarded to 1434 the source, resulting in a route being advertised with a new sequence 1435 number. (Due to duplicate suppression, only a small number of such 1436 requests are expected to actually reach the source.) 1438 In order to compensate for packet loss, a node SHOULD repeat such a 1439 request a small number of times if no route becomes feasible within a 1440 short time (see "Request Timeout" in Appendix B for suggested 1441 values). In the presence of heavy packet loss, however, all such 1442 requests might be lost; in that case, the mechanism in the next 1443 section will eventually ensure that a new seqno is received. 1445 3.8.2.2. Dealing with Unfeasible Updates 1447 When a route's metric increases, a node might receive an unfeasible 1448 update for a route that it has currently selected. As specified in 1449 Section 3.5.1, the receiving node will either ignore the update or 1450 unselect the route. 1452 In order to keep routes from spuriously expiring because they have 1453 become unfeasible, a node SHOULD send a unicast seqno request when it 1454 receives an unfeasible update for a route that is currently selected. 1455 The requested sequence number is computed from the source table as in 1456 Section 3.8.2.1 above. 1458 Additionally, since metric computation does not necessarily coincide 1459 with the delay in propagating updates, a node might receive an 1460 unfeasible update from a currently unselected neighbour that is 1461 preferable to the currently selected route (e.g., because it has a 1462 much smaller metric); in that case, the node SHOULD send a unicast 1463 seqno request to the neighbour that advertised the preferable update. 1465 3.8.2.3. Preventing Routes from Expiring 1467 In normal operation, a route's expiry timer never triggers: since a 1468 route's hold time is computed from an explicit interval included in 1469 Update TLVs, a new update (possibly a retraction) should arrive in 1470 time to prevent a route from expiring. 1472 In the presence of packet loss, however, it may be the case that no 1473 update is successfully received for an extended period of time, 1474 causing a route to expire. In order to avoid such spurious expiry, 1475 shortly before a selected route expires, a Babel node SHOULD send a 1476 unicast route request to the neighbour that advertised this route; 1477 since nodes always send either updates or retractions in response to 1478 non-wildcard route requests (Section 3.8.1.1), this will usually 1479 result in the route being either refreshed or retracted. 1481 4. Protocol Encoding 1483 A Babel packet MUST be sent as the body of a UDP datagram, with 1484 network-layer hop count set to 1, destined to a well-known multicast 1485 address or to a unicast address, over IPv4 or IPv6; in the case of 1486 IPv6, these addresses are link-local. Both the source and 1487 destination UDP port are set to a well-known port number. A Babel 1488 packet MUST be silently ignored unless its source address is either a 1489 link-local IPv6 address or an IPv4 address belonging to the local 1490 network, and its source port is the well-known Babel port. It MAY be 1491 silently ignored if its destination address is a global IPv6 address. 1493 In order to minimise the number of packets being sent while avoiding 1494 lower-layer fragmentation, a Babel node SHOULD maximise the size of 1495 the packets it sends, up to the outgoing interface's MTU adjusted for 1496 lower-layer headers (28 octets for UDP over IPv4, 48 octets for UDP 1497 over IPv6). It MUST NOT send packets larger than the attached 1498 interface's MTU adjusted for lower-layer headers or 512 octets, 1499 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1500 layer headers. Every Babel speaker MUST be able to receive packets 1501 that are as large as any attached interface's MTU adjusted for lower- 1502 layer headers or 512 octets, whichever is larger. Babel packets MUST 1503 NOT be sent in IPv6 Jumbograms. 1505 4.1. Data Types 1507 4.1.1. Interval 1509 Relative times are carried as 16-bit values specifying a number of 1510 centiseconds (hundredths of a second). This allows times up to 1511 roughly 11 minutes with a granularity of 10ms, which should cover all 1512 reasonable applications of Babel. 1514 4.1.2. Router-Id 1516 A router-id is an arbitrary 8-octet value. A router-id MUST NOT 1517 consist of either all binary zeroes (0000000000000000 hexadecimal) or 1518 all binary ones (FFFFFFFFFFFFFFFF hexadecimal). 1520 4.1.3. Address 1522 Since the bulk of the protocol is taken by addresses, multiple ways 1523 of encoding addresses are defined. Additionally, within Update TLVs 1524 a common subnet prefix may be omitted when multiple addresses are 1525 sent in a single packet -- this is known as address compression 1526 (Section 4.6.9). 1528 Address encodings: 1530 o AE 0: wildcard address. The value is 0 octets long. 1532 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1534 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1536 o AE 3: link-local IPv6 address. Compression is not allowed. The 1537 value is 8 octets long, a prefix of fe80::/64 is implied. 1539 The address family associated to an address encoding is either IPv4 1540 or IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 1541 and 3. 1543 4.1.4. Prefixes 1545 A network prefix is encoded just like a network address, but it is 1546 stored in the smallest number of octets that are enough to hold the 1547 significant bits (up to the prefix length). 1549 4.2. Packet Format 1551 A Babel packet consists of a 4-octet header, followed by a sequence 1552 of TLVs (the packet body), optionally followed by a second sequence 1553 of TLVs (the packet trailer). The format is designed to be 1554 extensible; see Appendix D for extensibility considerations. 1556 0 1 2 3 1557 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 1558 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1559 | Magic | Version | Body length | 1560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1561 | Packet Body ... 1562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1563 | Packet Trailer... 1564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1566 Fields : 1568 Magic The arbitrary but carefully chosen value 42 (decimal); 1569 packets with a first octet different from 42 MUST be 1570 silently ignored. 1572 Version This document specifies version 2 of the Babel protocol. 1573 Packets with a second octet different from 2 MUST be 1574 silently ignored. 1576 Body length The length in octets of the body following the packet 1577 header (excluding the Magic, Version and Body length 1578 fields, and excluding the packet trailer). 1580 Packet Body The packet body; a sequence of TLVs. 1582 Packet Trailer The packet trailer; another sequence of TLVs. 1584 The packet body and trailer are both sequences of TLVs. The packet 1585 body is the normal place to store TLVs; the packet trailer only 1586 contains specialised TLVs that do not need to be protected by 1587 cryptographic security mechanisms. When parsing the trailer, the 1588 receiver MUST ignore any TLV unless its definition explicitly states 1589 that it is allowed to appear there. Among the TLVs defined in this 1590 document, only Pad1 and PadN are allowed in the trailer; since these 1591 TLVs are ignored in any case, an implementation MAY silently ignore 1592 the packet trailer without even parsing it, unless it implements at 1593 least one protocol extension that defines TLVs that are allowed to 1594 appear in the trailer. 1596 4.3. TLV Format 1598 With the exception of Pad1, all TLVs have the following structure: 1600 0 1 2 3 1601 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 1602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1603 | Type | Length | Payload... 1604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1606 Fields : 1608 Type The type of the TLV. 1610 Length The length of the body in octets, exclusive of the Type and 1611 Length fields. 1613 Payload The TLV payload, which consists of a body and, for selected 1614 TLV types, an optional list of sub-TLVs. 1616 TLVs with an unknown type value MUST be silently ignored. 1618 4.4. Sub-TLV Format 1620 Every TLV carries an explicit length in its header; however, most 1621 TLVs are self-terminating, in the sense that it is possible to 1622 determine the length of the body without reference to the explicit 1623 Length field. If a TLV has a self-terminating format, then the space 1624 between the natural size of the TLV and the size announced in the 1625 Length field may be used to store a sequence of sub-TLVs. 1627 Sub-TLVs have the same structure as TLVs. With the exception of 1628 Pad1, all TLVs have the following structure: 1630 0 1 2 3 1631 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 1632 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1633 | Type | Length | Body... 1634 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1636 Fields : 1638 Type The type of the sub-TLV. 1640 Length The length of the body in octets, exclusive of the Type and 1641 Length fields. 1643 Body The sub-TLV body, the interpretation of which depends on 1644 both the type of the sub-TLV and the type of the TLV within 1645 which it is embedded. 1647 The most-significant bit of the sub-TLV type (the bit with value 80 1648 hexadecimal), is called the mandatory bit; in other words, sub-TLV 1649 types 128 through 255 have the mandatory bit set. This bit indicates 1650 how to handle unknown sub-TLVs. If the mandatory bit is not set, 1651 then an unknown sub-TLV MUST be silently ignored, and the rest of the 1652 TLV is processed normally. If the mandatory bit is set, then the 1653 whole enclosing TLV MUST be silently ignored (except for updating the 1654 parser state by a Router-Id, Next-Hop or Update TLV, as described in 1655 the next section). 1657 4.5. Parser state and encoding of updates 1659 In a large network, the bulk of Babel traffic consists of route 1660 updates; hence, some care has been given to encoding them 1661 efficiently. The data conceptually contained in an update 1662 (Section 3.5) is split into three pieces: 1664 o the prefix, seqno and metric are contained in the Update TLV 1665 itself (Section 4.6.9); 1667 o the router-id is taken from Router-Id TLV that precedes the Update 1668 TLV, and may be shared among multiple Update TLVs (Section 4.6.7); 1670 o the next hop is taken either from the source-address of the 1671 network-layer packet that contains the Babel packet, or from an 1672 explicit Next-Hop TLV (Section 4.6.8). 1674 In addition to the above, an Update TLV can omit a prefix of the 1675 prefix being announced, which is then extracted from the preceding 1676 Update TLV in the same address family (IPv4 or IPv6). Finally, as a 1677 special optimisation for the case when a router-id coincides with the 1678 interface-id part of an IPv6 address, Router-ID TLV itself may be 1679 omitted and the router-id derived derived from the low-order bits of 1680 the advertised prefix (Section 4.6.9). 1682 In order to implement these compression techniques, Babel uses a 1683 stateful parser: a TLV may refer to data from a previous TLV. The 1684 parser state consists of the following pieces of data: 1686 o for each address encoding that allows compression, the current 1687 default prefix; this is undefined at the start of the packet, and 1688 is updated by each Update TLV with the Prefix flag set 1689 (Section 4.6.9); 1691 o for each address family (IPv4 or IPv6), the current next-hop; this 1692 is the source address of the enclosing packet for the matching 1693 address family at the start of a packet, and is updated by each 1694 Next-Hop TLV (Section 4.6.8); 1696 o the current router-id; this is undefined at the start of the 1697 packet, and is updated by each Router-ID TLV (Section 4.6.7) and 1698 by each Update TLV with Router-Id flag set. 1700 Since the parser state must be identical across implementations, it 1701 is updated before checking for mandatory sub-TLVs: parsing a TLV MUST 1702 update the parser state even if the TLV is otherwise ignored due to 1703 an unknown mandatory sub-TLV or for any other reason. 1705 None of the TLVs that modify the parser state are allowed in the 1706 packet trailer; hence, an implementation may choose to use a 1707 dedicated stateless parser to parse the packet trailer. 1709 4.6. Details of Specific TLVs 1711 4.6.1. Pad1 1713 0 1714 0 1 2 3 4 5 6 7 1715 +-+-+-+-+-+-+-+-+ 1716 | Type = 0 | 1717 +-+-+-+-+-+-+-+-+ 1719 Fields : 1721 Type Set to 0 to indicate a Pad1 TLV. 1723 This TLV is silently ignored on reception. It is allowed in the 1724 packet trailer. 1726 4.6.2. PadN 1728 0 1 2 3 1729 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 1730 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1731 | Type = 1 | Length | MBZ... 1732 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1734 Fields : 1736 Type Set to 1 to indicate a PadN TLV. 1738 Length The length of the body in octets, exclusive of the Type and 1739 Length fields. 1741 MBZ Must be zero, set to 0 on transmission. 1743 This TLV is silently ignored on reception. It is allowed in the 1744 packet trailer. 1746 4.6.3. Acknowledgment Request 1748 0 1 2 3 1749 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 1750 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1751 | Type = 2 | Length | Reserved | 1752 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1753 | Opaque | Interval | 1754 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1755 This TLV requests that the receiver send an Acknowledgment TLV within 1756 the number of centiseconds specified by the Interval field. 1758 Fields : 1760 Type Set to 2 to indicate an Acknowledgment Request TLV. 1762 Length The length of the body in octets, exclusive of the Type and 1763 Length fields. 1765 Reserved Sent as 0 and MUST be ignored on reception. 1767 Opaque An arbitrary value that will be echoed in the receiver's 1768 Acknowledgment TLV. 1770 Interval A time interval in centiseconds after which the sender will 1771 assume that this packet has been lost. This MUST NOT be 0. 1772 The receiver MUST send an Acknowledgment TLV before this 1773 time has elapsed (with a margin allowing for propagation 1774 time). 1776 This TLV is self-terminating, and allows sub-TLVs. 1778 4.6.4. Acknowledgment 1780 0 1 2 3 1781 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 1782 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1783 | Type = 3 | Length | Opaque | 1784 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1786 This TLV is sent by a node upon receiving an Acknowledgment Request. 1788 Fields : 1790 Type Set to 3 to indicate an Acknowledgment TLV. 1792 Length The length of the body in octets, exclusive of the Type and 1793 Length fields. 1795 Opaque Set to the Opaque value of the Acknowledgment Request that 1796 prompted this Acknowledgment. 1798 Since Opaque values are not globally unique, this TLV MUST be sent to 1799 a unicast address. 1801 This TLV is self-terminating, and allows sub-TLVs. 1803 4.6.5. Hello 1805 0 1 2 3 1806 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 1807 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1808 | Type = 4 | Length | Flags | 1809 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1810 | Seqno | Interval | 1811 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1813 This TLV is used for neighbour discovery and for determining a 1814 neighbour's reception cost. 1816 Fields : 1818 Type Set to 4 to indicate a Hello TLV. 1820 Length The length of the body in octets, exclusive of the Type and 1821 Length fields. 1823 Flags The individual bits of this field specify special handling 1824 of this TLV (see below). 1826 Seqno If the Unicast flag is set, this is the value of the 1827 sending node's outgoing Unicast Hello seqno for this 1828 neighbour. Otherwise, it is the sending node's outgoing 1829 Multicast Hello seqno for this interface. 1831 Interval If non-zero, this is an upper bound, expressed in 1832 centiseconds, on the time after which the sending node will 1833 send a new scheduled Hello TLV with the same setting of the 1834 Unicast flag. If this is 0, then this Hello represents an 1835 unscheduled Hello, and doesn't carry any new information 1836 about times at which Hellos are sent. 1838 The Flags field is interpreted as follows: 1840 0 1 1841 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 1842 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1843 |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| 1844 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1846 o U (Unicast) flag (8000 hexadecimal): if set, then this Hello 1847 represents a Unicast Hello, otherwise it represents a Multicast 1848 Hello; 1850 o X: all other bits MUST be sent as 0 and silently ignored on 1851 reception. 1853 Every time a Hello is sent, the corresponding seqno counter MUST be 1854 incremented. Since there is a single seqno counter for all the 1855 Multicast Hellos sent by a given node over a given interface, if the 1856 Unicast flag is not set, this TLV MUST be sent to all neighbors on 1857 this link, which can be achieved by sending to a multicast 1858 destination, or by sending multiple packets to the unicast addresses 1859 of all reachable neighbours. Conversely, if the Unicast flag is set, 1860 this TLV MUST be sent to a single neighbour, which can achieved by 1861 sending to a unicast destination. In order to avoid large 1862 discontinuities in link quality, multiple Hello TLVs SHOULD NOT be 1863 sent in the same packet. 1865 This TLV is self-terminating, and allows sub-TLVs. 1867 4.6.6. IHU 1869 0 1 2 3 1870 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 1871 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1872 | Type = 5 | Length | AE | Reserved | 1873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1874 | Rxcost | Interval | 1875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1876 | Address... 1877 +-+-+-+-+-+-+-+-+-+-+-+- 1879 An IHU ("I Heard You") TLV is used for confirming bidirectional 1880 reachability and carrying a link's transmission cost. 1882 Fields : 1884 Type Set to 5 to indicate an IHU TLV. 1886 Length The length of the body in octets, exclusive of the Type and 1887 Length fields. 1889 AE The encoding of the Address field. This should be 1 or 3 1890 in most cases. As an optimisation, it MAY be 0 if the TLV 1891 is sent to a unicast address, if the association is over a 1892 point-to-point link, or when bidirectional reachability is 1893 ascertained by means outside of the Babel protocol. 1895 Reserved Sent as 0 and MUST be ignored on reception. 1897 Rxcost The rxcost according to the sending node of the interface 1898 whose address is specified in the Address field. The value 1899 FFFF hexadecimal (infinity) indicates that this interface 1900 is unreachable. 1902 Interval An upper bound, expressed in centiseconds, on the time 1903 after which the sending node will send a new IHU; this MUST 1904 NOT be 0. The receiving node will use this value in order 1905 to compute a hold time for this symmetric association. 1907 Address The address of the destination node, in the format 1908 specified by the AE field. Address compression is not 1909 allowed. 1911 Conceptually, an IHU is destined to a single neighbour. However, IHU 1912 TLVs contain an explicit destination address, and MAY be sent to a 1913 multicast address, as this allows aggregation of IHUs destined to 1914 distinct neighbours into a single packet and avoids the need for an 1915 ARP or Neighbour Discovery exchange when a neighbour is not being 1916 used for data traffic. 1918 IHU TLVs with an unknown value in the AE field MUST be silently 1919 ignored. 1921 This TLV is self-terminating, and allows sub-TLVs. 1923 4.6.7. Router-Id 1925 0 1 2 3 1926 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 1927 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1928 | Type = 6 | Length | Reserved | 1929 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1930 | | 1931 + Router-Id + 1932 | | 1933 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1935 A Router-Id TLV establishes a router-id that is implied by subsequent 1936 Update TLVs, as described in Section 4.5. This TLV sets the router- 1937 id even if it is otherwise ignored due to an unknown mandatory sub- 1938 TLV. 1940 Fields : 1942 Type Set to 6 to indicate a Router-Id TLV. 1944 Length The length of the body in octets, exclusive of the Type and 1945 Length fields. 1947 Reserved Sent as 0 and MUST be ignored on reception. 1949 Router-Id The router-id for routes advertised in subsequent Update 1950 TLVs. This MUST NOT consist of all zeroes or all ones. 1952 This TLV is self-terminating, and allows sub-TLVs. 1954 4.6.8. Next Hop 1956 0 1 2 3 1957 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 1958 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1959 | Type = 7 | Length | AE | Reserved | 1960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1961 | Next hop... 1962 +-+-+-+-+-+-+-+-+-+-+-+- 1964 A Next Hop TLV establishes a next-hop address for a given address 1965 family (IPv4 or IPv6) that is implied in subsequent Update TLVs, as 1966 described in Section 4.5. This TLV sets up the next-hop for 1967 subsequent Update TLVs even if it is otherwise ignored due to an 1968 unknown mandatory sub-TLV. 1970 Fields : 1972 Type Set to 7 to indicate a Next Hop TLV. 1974 Length The length of the body in octets, exclusive of the Type and 1975 Length fields. 1977 AE The encoding of the Address field. This SHOULD be 1 (IPv4) 1978 or 3 (link-local IPv6), and MUST NOT be 0. 1980 Reserved Sent as 0 and MUST be ignored on reception. 1982 Next hop The next-hop address advertised by subsequent Update TLVs, 1983 for this address family. 1985 When the address family matches the network-layer protocol that this 1986 packet is transported over, a Next Hop TLV is not needed: in the 1987 absence of a Next Hop TLV in a given address family, the next hop 1988 address is taken to be the source address of the packet. 1990 Next Hop TLVs with an unknown value for the AE field MUST be silently 1991 ignored. 1993 This TLV is self-terminating, and allows sub-TLVs. 1995 4.6.9. Update 1997 0 1 2 3 1998 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 1999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2000 | Type = 8 | Length | AE | Flags | 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2002 | Plen | Omitted | Interval | 2003 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2004 | Seqno | Metric | 2005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2006 | Prefix... 2007 +-+-+-+-+-+-+-+-+-+-+-+- 2009 An Update TLV advertises or retracts a route. As an optimisation, it 2010 can optionally have the side effect of establishing a new implied 2011 router-id and a new default prefix, as described in Section 4.5. 2013 Fields : 2015 Type Set to 8 to indicate an Update TLV. 2017 Length The length of the body in octets, exclusive of the Type and 2018 Length fields. 2020 AE The encoding of the Prefix field. 2022 Flags The individual bits of this field specify special handling 2023 of this TLV (see below). 2025 Plen The length in bits of the advertised prefix. If AE is 3 2026 (link-local IPv6), Omitted MUST be 0. 2028 Omitted The number of octets that have been omitted at the 2029 beginning of the advertised prefix and that should be taken 2030 from a preceding Update TLV in the same address family with 2031 the Prefix flag set. 2033 Interval An upper bound, expressed in centiseconds, on the time 2034 after which the sending node will send a new update for 2035 this prefix. This MUST NOT be 0. The receiving node will 2036 use this value to compute a hold time for the route table 2037 entry. The value FFFF hexadecimal (infinity) expresses 2038 that this announcement will not be repeated unless a 2039 request is received (Section 3.8.2.3). 2041 Seqno The originator's sequence number for this update. 2043 Metric The sender's metric for this route. The value FFFF 2044 hexadecimal (infinity) means that this is a route 2045 retraction. 2047 Prefix The prefix being advertised. This field's size is 2048 (Plen/8 - Omitted) rounded upwards. 2050 The Flags field is interpreted as follows: 2052 0 1 2 3 4 5 6 7 2053 +-+-+-+-+-+-+-+-+ 2054 |P|R|X|X|X|X|X|X| 2055 +-+-+-+-+-+-+-+-+ 2057 o P (Prefix) flag (80 hexadecimal): if set, then this Update 2058 establishes a new default prefix for subsequent Update TLVs with a 2059 matching address encoding within the same packet, even if this TLV 2060 is otherwise ignored due to an unknown mandatory sub-TLV; 2062 o R (Router-Id) flag (40 hexadecimal): if set, then this TLV 2063 establishes a new default router-id for this TLV and subsequent 2064 Update TLVs in the same packet, even if this TLV is otherwise 2065 ignored due to an unknown mandatory sub-TLV. This router-id is 2066 computed from the first address of the advertised prefix as 2067 follows: 2069 * if the length of the address is 8 octets or more, then the new 2070 router-id is taken from the 8 last octets of the address; 2072 * if the length of the address is smaller than 8 octets, then the 2073 new router-id consists of the required number of zero octets 2074 followed by the address, i.e., the address is stored on the 2075 right of the router-id. For example, for an IPv4 address, the 2076 router-id consists of 4 octets of zeroes followed by the IPv4 2077 address. 2079 o X: all other bits MUST be sent as 0 and silently ignored on 2080 reception. 2082 The prefix being advertised by an Update TLV is computed as follows: 2084 o the first Omitted octets of the prefix are taken from the previous 2085 Update TLV with the Prefix flag set and the same address encoding, 2086 even if it was ignored due to an unknown mandatory sub-TLV; if 2087 Omitted is not zero and there is no such TLV, then this Update 2088 MUST be ignored; 2090 o the next (Plen/8 - Omitted) rounded upwards octets are taken from 2091 the Prefix field; 2093 o if Plen is not a multiple of 8, then any bits beyond Plen (i.e., 2094 the low-order (8 - Plen MOD 8) bits of the last octet) are 2095 cleared; 2097 o the remaining octets are set to 0. 2099 If the Metric field is finite, the router-id of the originating node 2100 for this announcement is taken from the prefix advertised by this 2101 Update if the Router-Id flag is set, computed as described above. 2102 Otherwise, it is taken either from the preceding Router-Id TLV, or 2103 the preceding Update TLV with the Router-Id flag set, whichever comes 2104 last, even if that TLV is otherwise ignored due to an unknown 2105 mandatory sub-TLV; if there is no suitable TLV, then this update is 2106 ignored. 2108 The next-hop address for this update is taken from the last preceding 2109 Next Hop TLV with a matching address family (IPv4 or IPv6) in the 2110 same packet even if it was otherwise ignored due to an unknown 2111 mandatory sub-TLV; if no such TLV exists, it is taken from the 2112 network-layer source address of this packet if it belongs to the same 2113 address family as the prefix being announced; otherwise, this Update 2114 MUST be ignored. 2116 If the metric field is FFFF hexadecimal, this TLV specifies a 2117 retraction. In that case, the router-id, next-hop and seqno are not 2118 used. AE MAY then be 0, in which case this Update retracts all of 2119 the routes previously advertised by the sending interface. If the 2120 metric is finite, AE MUST NOT be 0; Update TLVs with finite metric 2121 and AE equal to 0 MUST be ignored. If the metric is infinite and AE 2122 is 0, Plen and Omitted MUST both be 0. 2124 Update TLVs with an unknown value in the AE field MUST be silently 2125 ignored. 2127 This TLV is self-terminating, and allows sub-TLVs. 2129 4.6.10. Route Request 2131 0 1 2 3 2132 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 2133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2134 | Type = 9 | Length | AE | Plen | 2135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2136 | Prefix... 2137 +-+-+-+-+-+-+-+-+-+-+-+- 2138 A Route Request TLV prompts the receiver to send an update for a 2139 given prefix, or a full route table dump. 2141 Fields : 2143 Type Set to 9 to indicate a Route Request TLV. 2145 Length The length of the body in octets, exclusive of the Type and 2146 Length fields. 2148 AE The encoding of the Prefix field. The value 0 specifies 2149 that this is a request for a full route table dump (a 2150 wildcard request). 2152 Plen The length in bits of the requested prefix. 2154 Prefix The prefix being requested. This field's size is Plen/8 2155 rounded upwards. 2157 A Request TLV prompts the receiver to send an update message 2158 (possibly a retraction) for the prefix specified by the AE, Plen, and 2159 Prefix fields, or a full dump of its route table if AE is 0 (in which 2160 case Plen MUST be 0 and Prefix is of length 0). 2162 This TLV is self-terminating, and allows sub-TLVs. 2164 4.6.11. Seqno Request 2166 0 1 2 3 2167 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 2168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2169 | Type = 10 | Length | AE | Plen | 2170 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2171 | Seqno | Hop Count | Reserved | 2172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2173 | | 2174 + Router-Id + 2175 | | 2176 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2177 | Prefix... 2178 +-+-+-+-+-+-+-+-+-+-+ 2180 A Seqno Request TLV prompts the receiver to send an Update for a 2181 given prefix with a given sequence number, or to forward the request 2182 further if it cannot be satisfied locally. 2184 Fields : 2186 Type Set to 10 to indicate a Seqno Request TLV. 2188 Length The length of the body in octets, exclusive of the Type and 2189 Length fields. 2191 AE The encoding of the Prefix field. This MUST NOT be 0. 2193 Plen The length in bits of the requested prefix. 2195 Seqno The sequence number that is being requested. 2197 Hop Count The maximum number of times that this TLV may be forwarded, 2198 plus 1. This MUST NOT be 0. 2200 Reserved Sent as 0 and MUST be ignored on reception. 2202 Router-Id The Router-Id that is being requested. This MUST NOT 2203 consist of all zeroes or all ones. 2205 Prefix The prefix being requested. This field's size is Plen/8 2206 rounded upwards. 2208 A Seqno Request TLV prompts the receiving node to send a finite- 2209 metric Update for the prefix specified by the AE, Plen, and Prefix 2210 fields, with either a router-id different from what is specified by 2211 the Router-Id field, or a Seqno no less (modulo 2^16) than what is 2212 specified by the Seqno field. If this request cannot be satisfied 2213 locally, then it is forwarded according to the rules set out in 2214 Section 3.8.1.2. 2216 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 2217 be forwarded to a multicast address and MUST NOT be forwarded to more 2218 than one neighbour. A request MUST NOT be forwarded if its Hop Count 2219 field is 1. 2221 This TLV is self-terminating, and allows sub-TLVs. 2223 4.7. Details of specific sub-TLVs 2225 4.7.1. Pad1 2227 0 1 2 3 4 5 6 7 2228 +-+-+-+-+-+-+-+-+ 2229 | Type = 0 | 2230 +-+-+-+-+-+-+-+-+ 2232 Fields : 2234 Type Set to 0 to indicate a Pad1 sub-TLV. 2236 This sub-TLV is silently ignored on reception. It is allowed within 2237 any TLV that allows sub-TLVs. 2239 4.7.2. PadN 2241 0 1 2 3 2242 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 2243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2244 | Type = 1 | Length | MBZ... 2245 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 2247 Fields : 2249 Type Set to 1 to indicate a PadN sub-TLV. 2251 Length The length of the body in octets, exclusive of the Type and 2252 Length fields. 2254 MBZ Must be zero, set to 0 on transmission. 2256 This sub-TLV is silently ignored on reception. It is allowed within 2257 any TLV that allows sub-TLVs. 2259 5. IANA Considerations 2261 IANA has registered the UDP port number 6696, called "babel", for use 2262 by the Babel protocol. 2264 IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4 2265 multicast group 224.0.0.111 for use by the Babel protocol. 2267 IANA has created a registry called "Babel TLV Types". The allocation 2268 policy for this registry is Specification Required [RFC8126] for 2269 Types 0-223, and Experimental Use for Types 224-254. The values in 2270 this registry are as follows: 2272 +---------+-----------------------------------------+---------------+ 2273 | Type | Name | Reference | 2274 +---------+-----------------------------------------+---------------+ 2275 | 0 | Pad1 | this document | 2276 | | | | 2277 | 1 | PadN | this document | 2278 | | | | 2279 | 2 | Acknowledgment Request | this document | 2280 | | | | 2281 | 3 | Acknowledgment | this document | 2282 | | | | 2283 | 4 | Hello | this document | 2284 | | | | 2285 | 5 | IHU | this document | 2286 | | | | 2287 | 6 | Router-Id | this document | 2288 | | | | 2289 | 7 | Next Hop | this document | 2290 | | | | 2291 | 8 | Update | this document | 2292 | | | | 2293 | 9 | Route Request | this document | 2294 | | | | 2295 | 10 | Seqno Request | this document | 2296 | | | | 2297 | 11 | TS/PC | [RFC7298] | 2298 | | | | 2299 | 12 | HMAC | [RFC7298] | 2300 | | | | 2301 | 13 | Source-specific Update | [BABEL-SS] | 2302 | | | | 2303 | 14 | Source-specific Request | [BABEL-SS] | 2304 | | | | 2305 | 15 | Source-specific Seqno Request | [BABEL-SS] | 2306 | | | | 2307 | 16 | MAC | [BABEL-MAC] | 2308 | | | | 2309 | 17 | PC | [BABEL-MAC] | 2310 | | | | 2311 | 18 | Challenge Request | [BABEL-MAC] | 2312 | | | | 2313 | 19 | Challenge Reply | [BABEL-MAC] | 2314 | | | | 2315 | 20-223 | Unassigned | | 2316 | | | | 2317 | 224-254 | Reserved for Experimental Use | this document | 2318 | | | | 2319 | 255 | Reserved for expansion of the type | this document | 2320 | | space | | 2321 +---------+-----------------------------------------+---------------+ 2323 IANA has created a registry called "Babel sub-TLV Types". The 2324 allocation policy for this registry is Specification Required for 2325 Types 0-111 and 128-239, and Experimental Use for Types 112-126 and 2326 240-254. The values in this registry are as follows: 2328 +---------+-------------------------------------+-------------------+ 2329 | Type | Name | Reference | 2330 +---------+-------------------------------------+-------------------+ 2331 | 0 | Pad1 | this document | 2332 | | | | 2333 | 1 | PadN | this document | 2334 | | | | 2335 | 2 | Diversity | [BABEL-DIVERSITY] | 2336 | | | | 2337 | 3 | Timestamp | [BABEL-RTT] | 2338 | | | | 2339 | 4-111 | Unassigned | | 2340 | | | | 2341 | 112-126 | Reserved for Experimental Use | this document | 2342 | | | | 2343 | 127 | Reserved for expansion of the type | this document | 2344 | | space | | 2345 | | | | 2346 | 128 | Source Prefix | [BABEL-SS] | 2347 | | | | 2348 | 129-239 | Unassigned | | 2349 | | | | 2350 | 240-254 | Reserved for Experimental Use | this document | 2351 | | | | 2352 | 255 | Reserved for expansion of the type | this document | 2353 | | space | | 2354 +---------+-------------------------------------+-------------------+ 2356 IANA is instructed to create a registry called "Babel Address 2357 Encodings". The allocation policy for this registry is Specification 2358 Required. The values in this registry are as follows: 2360 +----+-------------------------+---------------+ 2361 | AE | Name | Reference | 2362 +----+-------------------------+---------------+ 2363 | 0 | Wildcard address | this document | 2364 | | | | 2365 | 1 | IPv4 address | this document | 2366 | | | | 2367 | 2 | IPv6 address | this document | 2368 | | | | 2369 | 3 | Link-local IPv6 address | this document | 2370 +----+-------------------------+---------------+ 2372 IANA has created a registry called "Babel Flags Values". The 2373 allocation policy for this registry is Specification Required. IANA 2374 is instructed to rename this registry to "Babel Update Flags Values". 2375 The values in this registry are as follows: 2377 +-----+-------------------+---------------+ 2378 | Bit | Name | Reference | 2379 +-----+-------------------+---------------+ 2380 | 0 | Default prefix | this document | 2381 | | | | 2382 | 1 | Default Router-ID | this document | 2383 | | | | 2384 | 2-7 | Unassigned | | 2385 +-----+-------------------+---------------+ 2387 IANA is instructed to create a new registry called "Babel Hello Flags 2388 Values". The allocation policy for this registry is Specification 2389 Required. The initial values in this registry are as follows: 2391 +------+------------+---------------+ 2392 | Bit | Name | Reference | 2393 +------+------------+---------------+ 2394 | 0 | Unicast | this document | 2395 | | | | 2396 | 1-15 | Unassigned | | 2397 +------+------------+---------------+ 2399 IANA is instructed to replace all references to RFCs 6126 and 7557 in 2400 all of the registries mentioned above by references to this document. 2402 6. Security Considerations 2404 As defined in this document, Babel is a completely insecure protocol. 2405 Without additional security mechanisms, Babel trusts any information 2406 it receives in plaintext UDP datagrams and acts on it. An attacker 2407 that is present on the local network can impact Babel operation in a 2408 variety of ways, for example they can: 2410 o spoof a Babel packet, and redirect traffic by announcing a route 2411 with a smaller metric, a larger sequence number, or a longer 2412 prefix; 2414 o spoof a malformed packet, which could cause an insufficiently 2415 robust implementation to crash or interfere with the rest of the 2416 network; 2418 o replay a previously captured Babel packet, which could cause 2419 traffic to be redirected or otherwise interfere with the network. 2421 When carried over IPv6, Babel packets are ignored unless they are 2422 sent from a link-local IPv6 address; since routers don't forward 2423 link-local IPv6 packets, this mitigates the attacks outlined above by 2424 restricting them to on-link attackers. No such natural protection 2425 exists when Babel packets are carried over IPv4. 2427 These issues can be solved by providing a means for Babel to ensure 2428 datagrams are fresh and originated from a trusted node. This can be 2429 achieved either by a lower-layer security mechanism (e.g., link-layer 2430 security or IPsec), or by deploying a suitable authentication 2431 mechanism within Babel itself. There are currently two such 2432 mechanisms: 2434 o Babel over DTLS [BABEL-DTLS] runs the majority of Babel traffic 2435 over DTLS, and leverages DTLS to authenticate nodes and provide 2436 confidentiality and integrity protection; 2438 o MAC authentication [BABEL-MAC] appends a message authentication 2439 code to all Babel datagrams to prove they originated from a node 2440 that possesses a shared secret. 2442 Both mechanisms enable nodes to ignore packets generated by attackers 2443 without the proper credentials. They also ensure integrity of 2444 messages and prevent message replay. However, only DTLS supports 2445 asymmetric keying and message confidentiality. MAC authentication is 2446 simpler and does not depend on DTLS, and therefore its use is 2447 RECOMMENDED when the target deployment does not require 2448 confidentiality or asymmetric keying. 2450 The information that a mobile Babel node announces to the whole 2451 routing domain is often sufficient to determine a mobile node's 2452 physical location with reasonable precision. The privacy issues that 2453 this causes can be mitigated somewhat by using randomly chosen 2454 router-ids and randomly chosen IP addresses, and changing them often 2455 enough. 2457 7. Acknowledgments 2459 A number of people have contributed text and ideas to this 2460 specification. The authors are particularly indebted to Matthieu 2461 Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake, Toke 2462 Hoiland-Jorgensen, Benjamin Kaduk, Joao Sobrinho and Martin 2463 Vigoureux. Earlier versions of this document greatly benefited from 2464 the input of Joel Halpern. The address compression technique was 2465 inspired by [PACKETBB]. 2467 8. References 2468 8.1. Normative References 2470 [BABEL-MAC] 2471 Do, C., Kolodziejak, W., and J. Chroboczek, "MAC 2472 authentication for the Babel routing protocol", Internet 2473 Draft draft-ietf-babel-hmac-10, August 2019. 2475 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2476 Requirement Levels", BCP 14, RFC 2119, 2477 DOI 10.17487/RFC2119, March 1997. 2479 [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for 2480 Writing an IANA Considerations Section in RFCs", BCP 26, 2481 RFC 8126, June 2017. 2483 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2484 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2485 May 2017. 2487 8.2. Informative References 2489 [BABEL-DIVERSITY] 2490 Chroboczek, J., "Diversity Routing for the Babel Routing 2491 Protocol", draft-chroboczek-babel-diversity-routing-01 2492 (work in progress), February 2016. 2494 [BABEL-DTLS] 2495 Decimo, A., Schinazi, D., and J. Chroboczek, "Babel 2496 Routing Protocol over Datagram Transport Layer Security", 2497 Internet Draft draft-ietf-babel-dtls-09, August 2019. 2499 [BABEL-RTT] 2500 Jonglez, B. and J. Chroboczek, "Delay-based Metric 2501 Extension for the Babel Routing Protocol", draft-ietf- 2502 babel-rtt-extension-00 (work in progress), April 2019. 2504 [BABEL-SS] 2505 Boutier, M. and J. Chroboczek, "Source-Specific Routing in 2506 Babel", draft-ietf-babel-source-specific-05 (work in 2507 progress), April 2019. 2509 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 2510 Sequenced Distance-Vector Routing (DSDV) for Mobile 2511 Computers", ACM SIGCOMM'94 Conference on Communications 2512 Architectures, Protocols and Applications 234-244, 1994. 2514 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 2515 Computations", IEEE/ACM Transactions on Networking 1:1, 2516 February 1993. 2518 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 2519 "EIGRP -- a Fast Routing Protocol Based on Distance 2520 Vectors", Proc. Interop 94, 1994. 2522 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 2523 high-throughput path metric for multi-hop wireless 2524 networks", Proc. MobiCom 2003, 2003. 2526 [IS-IS] "Information technology -- Telecommunications and 2527 information exchange between systems -- Intermediate 2528 System to Intermediate System intra-domain routeing 2529 information exchange protocol for use in conjunction with 2530 the protocol for providing the connectionless-mode network 2531 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 2533 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 2534 periodic routing messages", IEEE/ACM Transactions on 2535 Networking 2, 2, 122-136, April 1994. 2537 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2539 [PACKETBB] 2540 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2541 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 2542 Format", RFC 5444, February 2009. 2544 [RFC3561] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On- 2545 Demand Distance Vector (AODV) Routing", RFC 3561, 2546 DOI 10.17487/RFC3561, July 2003, 2547 . 2549 [RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 2550 DOI 10.17487/RFC6126, April 2011. 2552 [RFC7298] Ovsienko, D., "Babel Hashed Message Authentication Code 2553 (HMAC) Cryptographic Authentication", RFC 7298, 2554 DOI 10.17487/RFC7298, July 2014. 2556 [RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing 2557 Protocol", RFC 7557, DOI 10.17487/RFC7557, May 2015. 2559 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 2561 Appendix A. Cost and Metric Computation 2563 The strategy for computing link costs and route metrics is a local 2564 matter; Babel itself only requires that it comply with the conditions 2565 given in Section 3.4.3 and Section 3.5.2. Different nodes may use 2566 different strategies in a single network and may use different 2567 strategies on different interface types. This section describes a 2568 set of stragies that have been found to work well in actual networks. 2570 In summary, a node maintains per-neighbour statistics about the last 2571 16 received Hello TLVs of each kind (Appendix A.1), it computes costs 2572 by using the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and 2573 ETX (Appendix A.2.2) on wireless links. It uses an additive algebra 2574 for metric computation (Appendix A.3.1). 2576 A.1. Maintaining Hello History 2578 For each neighbour, a node maintains two sets of Hello history, one 2579 for each kind of Hello, and an expected sequence number, one for 2580 Multicast and one for Unicast Hellos. Each Hello history is a vector 2581 of 16 bits, where a 1 value represents a received Hello, and a 0 2582 value a missed Hello. For each kind of Hello, the expected sequence 2583 number, written ne, is the sequence number that is expected to be 2584 carried by the next received Hello from this neighbour. 2586 Whenever it receives a Hello packet of a given kind from a neighbour, 2587 a node compares the received sequence number nr for that kind of 2588 Hello with its expected sequence number ne. Depending on the outcome 2589 of this comparison, one of the following actions is taken: 2591 o if the two differ by more than 16 (modulo 2^16), then the sending 2592 node has probably rebooted and lost its sequence number; the whole 2593 associated neighbour table entry is flushed and a new one is 2594 created; 2596 o otherwise, if the received nr is smaller (modulo 2^16) than the 2597 expected sequence number ne, then the sending node has increased 2598 its Hello interval without us noticing; the receiving node removes 2599 the last (ne - nr) entries from this neighbour's Hello history (we 2600 "undo history"); 2602 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 2603 node has decreased its Hello interval, and some Hellos were lost; 2604 the receiving node adds (nr - ne) 0 bits to the Hello history (we 2605 "fast-forward"). 2607 The receiving node then appends a 1 bit to the Hello history and sets 2608 ne to (nr + 1). If the Interval field of the received Hello is not 2609 zero, it resets the neighbour's hello timer to 1.5 times the 2610 advertised Interval (the extra margin allows for delay due to 2611 jitter). 2613 Whenever either Hello timer associated to a neighbour expires, the 2614 local node adds a 0 bit to the corresponding Hello history, and 2615 increments the expected Hello number. If both Hello histories are 2616 empty (they contain 0 bits only), the neighbour entry is flushed; 2617 otherwise, the relevant hello timer is reset to the value advertised 2618 in the last Hello of that kind received from this neighbour (no extra 2619 margin is necessary in this case, since jitter was already taken into 2620 account when computing the timeout that has just expired). 2622 A.2. Cost Computation 2624 This section discusses how to compute costs based on Hello history. 2626 A.2.1. k-out-of-j 2628 K-out-of-j link sensing is suitable for wired links that are either 2629 up, in which case they only occasionally drop a packet, or down, in 2630 which case they drop all packets. 2632 The k-out-of-j strategy is parameterised by two small integers k and 2633 j, such that 0 < k <= j, and the nominal link cost, a constant C >= 2634 1. A node keeps a history of the last j hellos; if k or more of 2635 those have been correctly received, the link is assumed to be up, and 2636 the rxcost is set to C; otherwise, the link is assumed to be down, 2637 and the rxcost is set to infinity. 2639 Since Babel supports two kinds of Hellos, a Babel node performs k- 2640 out-of-j twice for each neighbour, once on the Unicast and once on 2641 the Multicast Hello history. If either of the instances of k-out- 2642 of-j indicates that the link is up, then the link is assumed to be 2643 up, and the rxcost is set to K; if both instances indicate that the 2644 link is down, then the link is assumed to be down, and the rxcost is 2645 set to infinity. In other words, the resulting rxcost is the minimum 2646 of the rxcosts yielded by the two instances of k-out-of-j link 2647 sensing. 2649 The cost of a link performing k-out-of-j link sensing is defined as 2650 follows: 2652 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 2654 o cost = txcost otherwise. 2656 A.2.2. ETX 2658 Unlike wired links which are bimodal (either up or down), wireless 2659 links exhibit continuous variation of the link quality. Naive 2660 application of hop-count routing in networks that use wireless links 2661 for transit tends to select long, lossy links in preference to 2662 shorter, lossless links, which can dramatically reduce throughput. 2663 For that reason, a routing protocol designed to support wireless 2664 links must perform some form of link-quality estimation. 2666 ETX [ETX] is a simple link-quality estimation algorithm that is 2667 designed to work well with the IEEE 802.11 MAC. By default, the 2668 IEEE 802.11 MAC performs ARQ and rate adaptation on unicast frames, 2669 but not on multicast frames, which are sent at a fixed rate with no 2670 ARQ; therefore, measuring the loss rate of multicast frames yields a 2671 useful estimate of a link's quality. 2673 A node performing ETX link quality estimation uses a neighbour's 2674 Multicast Hello history to compute an estimate, written beta, of the 2675 probability that a Hello TLV is successfully received. Beta can be 2676 computed as the fraction of 1 bits within a small number (say, 6) of 2677 the most recent entries in the Multicast Hello history, or it can be 2678 an exponential average, or some combination of both approaches. Let 2679 rxcost be 256 / beta. 2681 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2682 successfully sending a Hello TLV. The cost is then computed by 2684 cost = 256/(alpha * beta) 2686 or, equivalently, 2688 cost = (MAX(txcost, 256) * rxcost) / 256. 2690 Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast 2691 frames do not provide a useful measure of link quality, and therefore 2692 ETX ignores the Unicast Hello history. Thus, a node performing ETX 2693 link-quality estimation will not route through neighbouring nodes 2694 unless they send periodic Multicast Hellos (possibly in addition to 2695 Unicast Hellos). 2697 A.3. Metric Computation 2699 As described in Section 3.5.2, the metric advertised by a neighbour 2700 is combined with the link cost to yield a metric. 2702 A.3.1. Additive Metrics 2704 The simplest approach for obtaining a monotonic, left-distributive 2705 metric is to define the metric of a route as the sum of the costs of 2706 the component links. More formally, if a neighbour advertises a 2707 route with metric m over a link with cost c, then the resulting route 2708 has metric M(c, m) = c + m. 2710 A multiplicative metric can be converted into an additive one by 2711 taking the logarithm (in some suitable base) of the link costs. 2713 Appendix B. Protocol parameters 2715 The choice of time constants is a trade-off between fast detection of 2716 mobility events and protocol overhead. Two instances of Babel 2717 running with different time constants will interoperate, although the 2718 resulting worst-case convergence time will be dictated by the slower 2719 of the two. 2721 The Hello interval is the most important time constant: an outage or 2722 a mobility event is detected within 1.5 to 3.5 Hello intervals. Due 2723 to Babel's use of a redundant route table, and due to its reliance on 2724 triggered updates and explicit requests, the Update interval has 2725 little influence on the time needed to reconverge after an outage: in 2726 practice, it only has a significant effect on the time needed to 2727 acquire new routes after a mobility event. 2729 The following values are recommended in a network with little 2730 mobility, and where occasional outages of up to 14 seconds are 2731 acceptable: 2733 Multicast Hello Interval: 4 seconds. 2735 Unicast Hello Interval: infinite (no Unicast Hellos are sent). 2737 Link cost: estimated using ETX on wireless links; 2-out-of-3 with 2738 C=96 on wired links. 2740 IHU Interval: the advertised IHU interval is always 3 times the 2741 Multicast Hello interval. IHUs are actually sent with each Hello 2742 on lossy links (as determined from the Hello history), but only 2743 with every third Multicast Hello on lossless links. 2745 Update Interval: 4 times the Multicast Hello interval. 2747 IHU Hold Time: 3.5 times the advertised IHU interval. 2749 Route Expiry Time: 3.5 times the advertised update interval. 2751 Request timeout: initially 2 seconds, doubled every time a request 2752 is resent, up to a maximum of three times. 2754 Urgent timeout: 0.2 seconds. 2756 Source GC time: 3 minutes. 2758 The following values are recommended in a network where reconvergence 2759 within 2 seconds after a mobility event is desired: 2761 Multicast Hello Interval: 0.5 seconds. 2763 Unicast Hello Interval: infinite (no Unicast Hellos are sent). 2765 Link cost, IHU Interval, Update Interval, IHU Hold Time, and Route 2766 Expiry Time: computed as in the first case above. 2768 Request Timeout: initially 0.5 seconds, doubled every time a 2769 request is resent, up to a maximum of three times. 2771 Urgent timeout: 0.2 seconds. 2773 Source GC time: 3 minutes. 2775 Appendix C. Route filtering 2777 Route filtering is a procedure where an instance of a routing 2778 protocol either discards some of the routes announced by its 2779 neighbours, or learns them with a metric that is higher than what 2780 would be expected. Like all distance-vector protocols, Babel has the 2781 ability to apply arbitrary filtering to the routes it learns, and 2782 implementations of Babel that apply different sets of filtering rules 2783 will interoperate without causing routing loops. The protocol's 2784 ability to perform route filtering is a consequence of the latitude 2785 given in Section 3.5.2: Babel can use any metric that is strictly 2786 monotonic, including one that assigns an infinite metric to a 2787 selected subset of routes. (See also Section 3.8.1, where requests 2788 for nonexistent routes are treated in the same way as requests for 2789 routes with infinite metric.) 2791 It is not in general correct to learn a route with a metric smaller 2792 than the one it was announced with, or to replace a route's 2793 destination prefix with a more specific (longer) one. Doing either 2794 of these may cause persistent routing loops. 2796 Route filtering is a useful tool, since it allows fine-grained tuning 2797 of the routing decisions made by the routing protocol. Accordingly, 2798 some implementations of Babel implement a rich configuration language 2799 that allows applying filtering to sets of routes defined, for 2800 example, by incoming interface and destination prefix. 2802 In order to limit the consequences of misconfiguration, Babel 2803 implementations provide a reasonable set of default filtering rules 2804 even when they don't allow configuration of filtering by the user. 2805 At a minimum, they discard routes with a destination prefix in 2806 fe80::/64, ff00::/8, 127.0.0.1/32, 0.0.0.0/32 and 224.0.0.0/8. 2808 Appendix D. Considerations for protocol extensions 2810 Babel is an extensible protocol, and this document defines a number 2811 of mechanisms that can be used to extend the protocol in a backwards 2812 compatible manner: 2814 o increasing the version number in the packet header; 2816 o defining new TLVs; 2818 o defining new sub-TLVs (with or without the mandatory bit set); 2820 o defining new AEs; 2822 o using the packet trailer. 2824 This appendix is intended to guide designers of protocol extensions 2825 in chosing a particular encoding. 2827 The version number in the Babel header should only be increased if 2828 the new version is not backwards compatible with the original 2829 protocol. 2831 In many cases, an extension could be implemented either by defining a 2832 new TLV, or by adding a new sub-TLV to an existing TLV. For example, 2833 an extension whose purpose is to attach additional data to route 2834 updates can be implemented either by creating a new "enriched" Update 2835 TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by 2836 adding a mandatory sub-TLV. 2838 The various encodings are treated differently by implementations that 2839 do not understand the extension. In the case of a new TLV or of a 2840 sub-TLV with the mandatory bit set, the whole TLV is ignored by 2841 implementations that do not implement the extension, while in the 2842 case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, 2843 and only the unknown sub-TLV is silently ignored. Therefore, a non- 2844 mandatory sub-TLV should be used by extensions that extend the Update 2845 in a compatible manner (the extension data may be silently ignored), 2846 while a mandatory sub-TLV or a new TLV must be used by extensions 2847 that make incompatible extensions to the meaning of the TLV (the 2848 whole TLV must be thrown away if the extension data is not 2849 understood). 2851 Experience shows that the need for additional data tends to crop up 2852 in the most unexpected places. Hence, it is recommended that 2853 extensions that define new TLVs should make them self-terminating, 2854 and allow attaching sub-TLVs to them. 2856 Adding a new AE is essentially equivalent to adding a new TLV: Update 2857 TLVs with an unknown AE are ignored, just like unknown TLVs. 2858 However, adding a new AE is more involved than adding a new TLV, 2859 since it creates a new set of compression state. Additionally, since 2860 the Next Hop TLV creates state specific to a given address family, as 2861 opposed to a given AE, a new AE for a previously defined address 2862 family must not be used in the Next Hop TLV if backwards 2863 compatibility is required. A similar issue arises with Update TLVs 2864 with unknown AEs establishing a new router-id (due to the Router-Id 2865 flag being set). Therefore, defining new AEs must be done with care 2866 if compatibility with unextended implementations is required. 2868 The packet trailer is intended to carry cryptographic signatures that 2869 only cover the packet body; storing the cryptographic signatures in 2870 the packet trailer avoids clearing the signature before computing a 2871 hash of the packet body, and makes it possible to check a 2872 cryptographic signature before running the full, stateful TLV parser. 2873 Hence, only TLVs that don't need to be protected by cryptographic 2874 security protocols should be allowed in the packet trailer. Any such 2875 TLVs should be easy to parse, and in particular should not require 2876 stateful parsing. 2878 Appendix E. Stub Implementations 2880 Babel is a fairly economic protocol. Updates take between 12 and 40 2881 octets per destination, depending on the address family and how 2882 successful compression is; in a double-stack flat network, an average 2883 of less than 24 octets per update is typical. The route table 2884 occupies about 35 octets per IPv6 entry. To put these values into 2885 perspective, a single full-size Ethernet frame can carry some 65 2886 route updates, and a megabyte of memory can contain a 20000-entry 2887 route table and the associated source table. 2889 Babel is also a reasonably simple protocol. One complete 2890 implementation consists of less than 12 000 lines of C code, and it 2891 compiles to less than 120 kB of text on a 32-bit CISC architecture; 2892 about half of this figure is due to protocol extensions and user- 2893 interface code. 2895 Nonetheless, in some very constrained environments, such as PDAs, 2896 microwave ovens, or abacuses, it may be desirable to have subset 2897 implementations of the protocol. 2899 There are many different definitions of a stub router, but for the 2900 needs of this section a stub implementation of Babel is one that 2901 announces one or more directly attached prefixes into a Babel network 2902 but doesn't reannounce any routes that it has learnt from its 2903 neighbours, and always prefers the direct route to a directly 2904 attached prefix to a route learned over the Babel protocol, even when 2905 the prefixes are the same. It may either maintain a full routing 2906 table, or simply select a default gateway through any one of its 2907 neighbours that announces a default route. Since a stub 2908 implementation never forwards packets except from or to a directly 2909 attached link, it cannot possibly participate in a routing loop, and 2910 hence it need not evaluate the feasibility condition or maintain a 2911 source table. 2913 No matter how primitive, a stub implementation must parse sub-TLVs 2914 attached to any TLVs that it understands and check the mandatory bit. 2915 It must answer acknowledgment requests and must participate in the 2916 Hello/IHU protocol. It must also be able to reply to seqno requests 2917 for routes that it announces and, and it should be able to reply to 2918 route requests. 2920 Experience shows that an IPv6-only stub implementation of Babel can 2921 be written in less than 1000 lines of C code and compile to 13 kB of 2922 text on 32-bit CISC architecture. 2924 Appendix F. Compatibility with previous versions 2926 The protocol defined in this document is a successor to the protocol 2927 defined in [RFC6126] and [RFC7557]. While the two protocols are not 2928 entirely compatible, the new protocol has been designed so that it 2929 can be deployed in existing RFC 6126 networks without requiring a 2930 flag day. 2932 There are two optioal features that make the new protocol 2933 incompatible with its predecessor. First of all, RFC 6126 did not 2934 define Unicast hellos (Section 3.4.1), and an implementation of RFC 2935 6126 will mis-interpret a Unicast Hello for a Multicast one; since 2936 the sequence number space of Unicast Hellos is distinct from the 2937 sequence space of Multicast Hellos, sending a Unicast Hello to an 2938 implementation of RFC 6126 will confuse its link quality estimator. 2939 Second, RFC 7557 did not define mandatory sub-TLVs (Section 4.4); 2940 thus, an implementation of RFCs 6126 and 7557 will not correctly 2941 ignore a TLV that carries an unknown mandatory sub-TLV; depending on 2942 the sub-TLV, this might cause routing pathologies. 2944 An implementation of this specification that never sends Unicast 2945 Hellos and doesn't implement any extensions that use mandatory sub- 2946 TLVs is safe to deploy in a network in which some nodes implement the 2947 old protocol. 2949 Two changes need to be made to an implementation of RFCs 6126 and 2950 7557 so that it can safely interoperate in all cases with 2951 implementations of this protocol. First, it needs to be modified to 2952 either ignore or process Unicast Hellos. Second, it needs to be 2953 modified to parse sub-TLVs of all the TLVs that it understands and 2954 that allow sub-TLVs, and to ignore the TLV is an unknown mandatory 2955 sub-TLV is found. It is not necessary to parse unknown TLVs, since 2956 these are ignored in any case. 2958 There are other changes, but these are not of a nature to prevent 2959 interoperability: 2961 o the conditions on route acquisition (Section 3.5.3) have been 2962 relaxed; 2964 o route selection should no longer use the route's sequence number 2965 (Section 3.6); 2967 o the format of the packet trailer has been defined (Section 4.2); 2969 o router-ids with a value of all-zeros or all-ones have been 2970 forbidden (Section 4.1.2); 2972 o the compression state is now specific to an address family rather 2973 than an address encoding Section 4.5; 2975 o packet pacing is now recommended (Section 3.1). 2977 Appendix G. Changes from previous versions 2979 G.1. Changes since RFC 6126 2981 o Changed UDP port number to 6696. 2983 o Consistently use router-id rather than id. 2985 o Clarified that the source garbage collection timer is reset after 2986 sending an update even if the entry was not modified. 2988 o In section "Seqno Requests", fixed an erroneous "route request". 2990 o In the description of the Seqno Request TLV, added the description 2991 of the Router-Id field. 2993 o Made router-ids all-0 and all-1 forbidden. 2995 G.2. Changes since draft-ietf-babel-rfc6126bis-00 2997 o Added security considerations. 2999 G.3. Changes since draft-ietf-babel-rfc6126bis-01 3001 o Integrated the format of sub-TLVs. 3003 o Mentioned for each TLV whether it supports sub-TLVs. 3005 o Added Appendix D. 3007 o Added a mandatory bit in sub-TLVs. 3009 o Changed compression state to be per-AF rather than per-AE. 3011 o Added implementation hint for the routing table. 3013 o Clarified how router-ids are computed when bit 0x40 is set in 3014 Updates. 3016 o Relaxed the conditions for sending requests, and tightened the 3017 conditions for forwarding requests. 3019 o Clarified that neighbours should be acquired at some point, but it 3020 doesn't matter when. 3022 G.4. Changes since draft-ietf-babel-rfc6126bis-02 3024 o Added Unicast Hellos. 3026 o Added unscheduled (interval-less) Hellos. 3028 o Changed Appendix A to consider Unicast and unscheduled Hellos. 3030 o Changed Appendix B to agree with the reference implementation. 3032 o Added optional algorithm to avoid the hold time. 3034 o Changed the table of pending seqno requests to be indexed by 3035 router-id in addition to prefixes. 3037 o Relaxed the route acquisition algorithm. 3039 o Replaced minimal implementations by stub implementations. 3041 o Added acknowledgments section. 3043 G.5. Changes since draft-ietf-babel-rfc6126bis-03 3045 o Clarified that all the data structures are conceptual. 3047 o Made sending and receiving Multicast Hellos a SHOULD, avoids 3048 expressing any opinion about Unicast Hellos. 3050 o Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4). 3052 o Made hold-time into a SHOULD rather than MUST. 3054 o Clarified that Seqno Requests are for a finite-metric Update. 3056 o Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV 3057 that allows sub-TLVs. 3059 o Updated IANA Considerations. 3061 o Updated Security Considerations. 3063 o Renamed routing table back to route table. 3065 o Made buffering outgoing updates a SHOULD. 3067 o Weakened advice to use modified EUI-64 in router-ids. 3069 o Added information about sending requests to Appendix B. 3071 o A number of minor wording changes and clarifications. 3073 G.6. Changes since draft-ietf-babel-rfc6126bis-03 3075 Minor editorial changes. 3077 G.7. Changes since draft-ietf-babel-rfc6126bis-04 3079 o Renamed isotonicity to left-distributivity. 3081 o Minor clarifications to unicast hellos. 3083 o Updated requirements boilerplate to RFC 8174. 3085 o Minor editorial changes. 3087 G.8. Changes since draft-ietf-babel-rfc6126bis-05 3089 o Added information about the packet trailer, now that it is used by 3090 draft-ietf-babel-hmac. 3092 G.9. Changes since draft-ietf-babel-rfc6126bis-06 3094 o Added references to security documents. 3096 G.10. Changes since draft-ietf-babel-rfc6126bis-07 3098 o Added list of obsoleted drafts to the abstract. 3100 o Updated references. 3102 G.11. Changes since draft-ietf-babel-rfc6126bis-08 3104 o Added recommendation that route selection should not take seqnos 3105 into account. 3107 G.12. Changes since draft-ietf-babel-rfc6126bis-09 3109 o Editorial changes only. 3111 G.13. Changes since draft-ietf-babel-rfc6126bis-10 3113 o Editorial changes only. 3115 G.14. Changes since draft-ietf-babel-rfc6126bis-11 3117 o Added recommendation that control traffic should be carried over 3118 IPv6 only. 3120 G.15. Changes since draft-ietf-babel-rfc6126bis-12 3122 o Removed appendix about software availability. 3124 o Expanded appendix about recommended values and added more 3125 references to it in the body of the document. 3127 o Added appendix about route filtering. 3129 o Clarified definition of mandatory bit. 3131 o Added recommendations for packet pacing. 3133 o Made time limiting of full updates a SHOULD. 3135 o Normative language in a few more places. 3137 o Removed normative language from stub implementations. 3139 o Added requirement to clear the undefined bits in an Update. 3141 o Added error checking requirements. 3143 o Reworked security considerations. 3145 o Added "in octets" and "in bits" in random places. 3147 o Inserted full IANA registries. 3149 o Editorial changes. 3151 G.16. Changes since draft-ietf-babel-rfc6126bis-13 3153 o Added a section about compatibility with 6126. 3155 o Added AE registry to IANA considerations. 3157 o Replaced Babel-HMAC with Babel-MAC, consistent with the change in 3158 draft-ietf-babel-hmac. 3160 o Removed section about external sources of willingness; filtering 3161 is a better approach. 3163 o Added recommendation to use a cost of 96 on wired links. 3165 o Editorial changes. 3167 Authors' Addresses 3169 Juliusz Chroboczek 3170 IRIF, University of Paris-Diderot 3171 Case 7014 3172 75205 Paris Cedex 13 3173 France 3175 Email: jch@irif.fr 3176 David Schinazi 3177 Google LLC 3178 1600 Amphitheatre Parkway 3179 Mountain View, California 94043 3180 USA 3182 Email: dschinazi.ietf@gmail.com