idnits 2.17.1 draft-ietf-babel-rfc6126bis-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 -- The draft header indicates that this document obsoletes RFC7557, but the abstract doesn't seem to mention this, which it should. -- The draft header indicates that this document obsoletes RFC6126, 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 seems to use 'NOT RECOMMENDED' as an RFC 2119 keyword, but does not include the phrase in its RFC 2119 key words list. -- The document date (October 29, 2017) is 2370 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) ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 3 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 Apple Inc. 6 Expires: May 2, 2018 October 29, 2017 8 The Babel Routing Protocol 9 draft-ietf-babel-rfc6126bis-04 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. 17 Status of This Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on May 2, 2018. 34 Copyright Notice 36 Copyright (c) 2017 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 54 1.3. Specification of Requirements . . . . . . . . . . . . . . 4 55 2. Conceptual Description of the Protocol . . . . . . . . . . . 5 56 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 57 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 5 58 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 59 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 7 60 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 61 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 10 62 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10 63 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11 64 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 12 65 3.1. Message Transmission and Reception . . . . . . . . . . . 12 66 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12 67 3.3. Acknowledgments and acknowledgment requests . . . . . . . 16 68 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 17 69 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 20 70 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 24 71 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 25 72 3.8. Explicit Requests . . . . . . . . . . . . . . . . . . . . 27 73 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 31 74 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 32 75 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 33 76 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 33 77 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 34 78 4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 35 79 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 35 80 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 46 81 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 47 82 6. Security Considerations . . . . . . . . . . . . . . . . . . . 48 83 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 48 84 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 48 85 8.1. Normative References . . . . . . . . . . . . . . . . . . 49 86 8.2. Informative References . . . . . . . . . . . . . . . . . 49 87 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 50 88 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 50 89 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 51 90 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 52 91 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 53 92 Appendix C. Considerations for protocol extensions . . . . . . . 54 93 Appendix D. Stub Implementations . . . . . . . . . . . . . . . . 55 94 Appendix E. Software Availability . . . . . . . . . . . . . . . 56 95 Appendix F. Changes from previous versions . . . . . . . . . . . 56 96 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 56 97 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 57 98 F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 57 99 F.4. Changes since draft-ietf-babel-rfc6126bis-02 . . . . . . 57 100 F.5. Changes since draft-ietf-babel-rfc6126bis-03 . . . . . . 58 101 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 58 103 1. Introduction 105 Babel is a loop-avoiding distance-vector routing protocol that is 106 designed to be robust and efficient both in networks using prefix- 107 based routing and in networks using flat routing ("mesh networks"), 108 and both in relatively stable wired networks and in highly dynamic 109 wireless networks. 111 1.1. Features 113 The main property that makes Babel suitable for unstable networks is 114 that, unlike naive distance-vector routing protocols [RIP], it 115 strongly limits the frequency and duration of routing pathologies 116 such as routing loops and black-holes during reconvergence. Even 117 after a mobility event is detected, a Babel network usually remains 118 loop-free. Babel then quickly reconverges to a configuration that 119 preserves the loop-freedom and connectedness of the network, but is 120 not necessarily optimal; in many cases, this operation requires no 121 packet exchanges at all. Babel then slowly converges, in a time on 122 the scale of minutes, to an optimal configuration. This is achieved 123 by using sequenced routes, a technique pioneered by Destination- 124 Sequenced Distance-Vector routing [DSDV]. 126 More precisely, Babel has the following properties: 128 o when every prefix is originated by at most one router, Babel never 129 suffers from routing loops; 131 o when a single prefix is originated by multiple routers, Babel may 132 occasionally create a transient routing loop for this particular 133 prefix; this loop disappears in a time proportional to its 134 diameter, and never again (up to an arbitrary garbage-collection 135 (GC) time) will the routers involved participate in a routing loop 136 for the same prefix; 138 o assuming bounded packet loss rates, any routing black-holes that 139 may appear after a mobility event are corrected in a time at most 140 proportional to the network's diameter. 142 Babel has provisions for link quality estimation and for fairly 143 arbitrary metrics. When configured suitably, Babel can implement 144 shortest-path routing, or it may use a metric based, for example, on 145 measured packet loss. 147 Babel nodes will successfully establish an association even when they 148 are configured with different parameters. For example, a mobile node 149 that is low on battery may choose to use larger time constants (hello 150 and update intervals, etc.) than a node that has access to wall 151 power. Conversely, a node that detects high levels of mobility may 152 choose to use smaller time constants. The ability to build such 153 heterogeneous networks makes Babel particularly adapted to the 154 unmanaged and wireless environment. 156 Finally, Babel is a hybrid routing protocol, in the sense that it can 157 carry routes for multiple network-layer protocols (IPv4 and IPv6), 158 whichever protocol the Babel packets are themselves being carried 159 over. 161 1.2. Limitations 163 Babel has two limitations that make it unsuitable for use in some 164 environments. First, Babel relies on periodic routing table updates 165 rather than using a reliable transport; hence, in large, stable 166 networks it generates more traffic than protocols that only send 167 updates when the network topology changes. In such networks, 168 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 169 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 170 suitable. 172 Second, unless the optional algorithm described in Section 3.5.5 is 173 implemented, Babel does impose a hold time when a prefix is 174 retracted. While this hold time does not apply to the exact prefix 175 being retracted, and hence does not prevent fast reconvergence should 176 it become available again, it does apply to any shorter prefix that 177 covers it. This may make those implementations of Babel that do not 178 implement the optional algorithm described in Section 3.5.5 179 unsuitable for use in networks that implement automatic prefix 180 aggregation. 182 1.3. Specification of Requirements 184 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 185 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 186 document are to be interpreted as described in [RFC2119]. 188 2. Conceptual Description of the Protocol 190 Babel is a loop-avoiding distance vector protocol: it is based on the 191 Bellman-Ford protocol, just like the venerable RIP [RIP], but 192 includes a number of refinements that either prevent loop formation 193 altogether, or ensure that a loop disappears in a timely manner and 194 doesn't form again. 196 Conceptually, Bellman-Ford is executed in parallel for every source 197 of routing information (destination of data traffic). In the 198 following discussion, we fix a source S; the reader will recall that 199 the same algorithm is executed for all sources. 201 2.1. Costs, Metrics and Neighbourship 203 As many routing algorithms, Babel computes costs of links between any 204 two neighbouring nodes, abstract values attached to the edges between 205 two nodes. We write C(A, B) for the cost of the edge from node A to 206 node B. 208 Given a route between any two nodes, the metric of the route is the 209 sum of the costs of all the edges along the route. The goal of the 210 routing algorithm is to compute, for every source S, the tree of 211 routes of lowest metric to S. 213 Costs and metrics need not be integers. In general, they can be 214 values in any algebra that satisfies two fairly general conditions 215 (Section 3.5.2). 217 A Babel node periodically sends Hello messages to all of its 218 neighbours; it also periodically sends an IHU ("I Heard You") message 219 to every neighbour from which it has recently heard a Hello. From 220 the information derived from Hello and IHU messages received from its 221 neighbour B, a node A computes the cost C(A, B) of the link from A to 222 B. 224 2.2. The Bellman-Ford Algorithm 226 Every node A maintains two pieces of data: its estimated distance to 227 S, written D(A), and its next-hop router to S, written NH(A). 228 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 230 Periodically, every node B sends to all of its neighbours a route 231 update, a message containing D(B). When a neighbour A of B receives 232 the route update, it checks whether B is its selected next hop; if 233 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 234 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 235 its current value of D(A). If that value is smaller, meaning that 236 the received update advertises a route that is better than the 237 currently selected route, then NH(A) is set to B, and D(A) is set to 238 C(A, B) + D(B). 240 A number of refinements to this algorithm are possible, and are used 241 by Babel. In particular, convergence speed may be increased by 242 sending unscheduled "triggered updates" whenever a major change in 243 the topology is detected, in addition to the regular, scheduled 244 updates. Additionally, a node may maintain a number of alternate 245 routes, which are being advertised by neighbours other than its 246 selected neighbour, and which can be used immediately if the selected 247 route were to fail. 249 2.3. Transient Loops in Bellman-Ford 251 It is well known that a naive application of Bellman-Ford to 252 distributed routing can cause transient loops after a topology 253 change. Consider for example the following topology: 255 B 256 1 /| 257 1 / | 258 S --- A |1 259 \ | 260 1 \| 261 C 263 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 265 Suppose now that the link between S and A fails: 267 B 268 1 /| 269 / | 270 S A |1 271 \ | 272 1 \| 273 C 275 When it detects the failure of the link, A switches its next hop to B 276 (which is still advertising a route to S with metric 2), and 277 advertises a metric equal to 3, and then advertises a new route with 278 metric 3. This process of nodes changing selected neighbours and 279 increasing their metric continues until the advertised metric reaches 280 "infinity", a value larger than all the metrics that the routing 281 protocol is able to carry. 283 2.4. Feasibility Conditions 285 Bellman-Ford is a very robust algorithm: its convergence properties 286 are preserved when routers delay route acquisition or when they 287 discard some updates. Babel routers discard received route 288 announcements unless they can prove that accepting them cannot 289 possibly cause a routing loop. 291 More formally, we define a condition over route announcements, known 292 as the "feasibility condition", that guarantees the absence of 293 routing loops whenever all routers ignore route updates that do not 294 satisfy the feasibility condition. In effect, this makes Bellman- 295 Ford into a family of routing algorithms, parameterised by the 296 feasibility condition. 298 Many different feasibility conditions are possible. For example, BGP 299 can be modelled as being a distance-vector protocol with a (rather 300 drastic) feasibility condition: a routing update is only accepted 301 when the receiving node's AS number is not included in the update's 302 AS-Path attribute (note that BGP's feasibility condition does not 303 ensure the absence of transient "micro-loops" during reconvergence). 305 Another simple feasibility condition, used in the Destination- 306 Sequenced Distance-Vector (DSDV) routing protocol [DSDV] and in the 307 Ad hoc On-Demand Distance Vector (AODV) protocol, stems from the 308 following observation: a routing loop can only arise after a router 309 has switched to a route with a larger metric than the route that it 310 had previously selected. Hence, one could decide that a route is 311 feasible only when its metric at the local node would be no larger 312 than the metric of the currently selected route, i.e., an 313 announcement carrying a metric D(B) is accepted by A when C(A, B) + 314 D(B) <= D(A). If all routers obey this constraint, then the metric 315 at every router is nonincreasing, and the following invariant is 316 always preserved: if A has selected B as its successor, then D(B) < 317 D(A), which implies that the forwarding graph is loop-free. 319 Babel uses a slightly more refined feasibility condition, derived 320 from EIGRP [DUAL]. Given a router A, define the feasibility distance 321 of A, written FD(A), as the smallest metric that A has ever 322 advertised for S to any of its neighbours. An update sent by a 323 neighbour B of A is feasible when the metric D(B) advertised by B is 324 strictly smaller than A's feasibility distance, i.e., when D(B) < 325 FD(A). 327 It is easy to see that this latter condition is no more restrictive 328 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 329 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 330 Suppose now that A receives a DSDV-feasible update that advertises a 331 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 332 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 334 To see that it is strictly less restrictive, consider the following 335 diagram, where A has selected the route through B, and D(A) = FD(A) = 336 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 337 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 338 the currently selected route: 340 B 341 1 / \ 1 342 / \ 343 S A 344 \ / 345 1 \ / 4 346 C 348 To show that this feasibility condition still guarantees loop- 349 freedom, recall that at the time when A accepts an update from B, the 350 metric D(B) announced by B is no smaller than FD(B); since it is 351 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 352 property is preserved when A sends updates, it remains true at all 353 times, which ensures that the forwarding graph has no loops. 355 2.5. Solving Starvation: Sequencing Routes 357 Obviously, the feasibility conditions defined above cause starvation 358 when a router runs out of feasible routes. Consider the following 359 diagram, where both A and B have selected the direct route to S: 361 A 362 1 /| D(A) = 1 363 / | FD(A) = 1 364 S |1 365 \ | D(B) = 2 366 2 \| FD(B) = 2 367 B 369 Suppose now that the link between A and S breaks: 371 A 372 | 373 | FD(A) = 1 374 S |1 375 \ | D(B) = 2 376 2 \| FD(B) = 2 377 B 379 The only route available from A to S, the one that goes through B, is 380 not feasible: A suffers from spurious starvation. At this point, the 381 whole network must be rebooted in order to solve the starvation; this 382 is essentially what EIGRP does when it performs a global 383 synchronisation of all the routers in the network with the source 384 (the "active" phase of EIGRP). 386 Babel reacts to starvation in a less drastic manner, by using 387 sequenced routes, a technique introduced by DSDV and adopted by AODV. 388 In addition to a metric, every route carries a sequence number, a 389 nondecreasing integer that is propagated unchanged through the 390 network and is only ever incremented by the source; a pair (s, m), 391 where s is a sequence number and m a metric, is called a distance. 393 A received update is feasible when either it is more recent than the 394 feasibility distance maintained by the receiving node, or it is 395 equally recent and the metric is strictly smaller. More formally, if 396 FD(A) = (s, m), then an update carrying the distance (s', m') is 397 feasible when either s' > s, or s = s' and m' < m. 399 Assuming the sequence number of S is 137, the diagram above becomes: 401 A 402 | 403 | FD(A) = (137, 1) 404 S |1 405 \ | D(B) = (137, 2) 406 2 \| FD(B) = (137, 2) 407 B 409 After S increases its sequence number, and the new sequence number is 410 propagated to B, we have: 412 A 413 | 414 | FD(A) = (137, 1) 415 S |1 416 \ | D(B) = (138, 2) 417 2 \| FD(B) = (138, 2) 418 B 420 at which point the route through B becomes feasible again. 422 Note that while sequence numbers are used for determining 423 feasibility, they are not necessarily used in route selection: a node 424 will normally ignore the sequence number when selecting the best 425 route to a given destination (Section 3.6). 427 2.6. Requests 429 In DSDV, the sequence number of a source is increased periodically. 430 A route becomes feasible again after the source increases its 431 sequence number, and the new sequence number is propagated through 432 the network, which may, in general, require a significant amount of 433 time. 435 Babel takes a different approach. When a node detects that it is 436 suffering from a potentially spurious starvation, it sends an 437 explicit request to the source for a new sequence number. This 438 request is forwarded hop by hop to the source, with no regard to the 439 feasibility condition. Upon receiving the request, the source 440 increases its sequence number and broadcasts an update, which is 441 forwarded to the requesting node. 443 Note that after a change in network topology not all such requests 444 will, in general, reach the source, as some will be sent over links 445 that are now broken. However, if the network is still connected, 446 then at least one among the nodes suffering from spurious starvation 447 has an (unfeasible) route to the source; hence, in the absence of 448 packet loss, at least one such request will reach the source. 449 (Resending requests a small number of times compensates for packet 450 loss.) 452 Since requests are forwarded with no regard to the feasibility 453 condition, they may, in general, be caught in a forwarding loop; this 454 is avoided by having nodes perform duplicate detection for the 455 requests that they forward. 457 2.7. Multiple Routers 459 The above discussion assumes that every prefix is originated by a 460 single router. In real networks, however, it is often necessary to 461 have a single prefix originated by multiple routers: for example, the 462 default route will be originated by all of the edge routers of a 463 routing domain. 465 Since synchronising sequence numbers between distinct routers is 466 problematic, Babel treats routes for the same prefix as distinct 467 entities when they are originated by different routers: every route 468 announcement carries the router-id of its originating router, and 469 feasibility distances are not maintained per prefix, but per source, 470 where a source is a pair of a router-id and a prefix. In effect, 471 Babel guarantees loop-freedom for the forwarding graph to every 472 source; since the union of multiple acyclic graphs is not in general 473 acyclic, Babel does not in general guarantee loop-freedom when a 474 prefix is originated by multiple routers, but any loops will be 475 broken in a time at most proportional to the diameter of the loop -- 476 as soon as an update has "gone around" the routing loop. 478 Consider for example the following topology, where A has selected the 479 default route through S, and B has selected the one through S': 481 1 1 1 482 ::/0 -- S --- A --- B --- S' -- ::/0 484 Suppose that both default routes fail at the same time; then nothing 485 prevents A from switching to B, and B simultaneously switching to A. 486 However, as soon as A has successfully advertised the new route to B, 487 the route through A will become unfeasible for B. Conversely, as 488 soon as B will have advertised the route through A, the route through 489 B will become unfeasible for A. 491 In effect, the routing loop disappears at the latest when routing 492 information has gone around the loop. Since this process can be 493 delayed by lost packets, Babel makes certain efforts to ensure that 494 updates are sent reliably after a router-id change Section 3.7.2. 496 Additionally, after the routers have advertised the two routes, both 497 sources will be in their source tables, which will prevent them from 498 ever again participating in a routing loop involving routes from S 499 and S' (up to the source GC time, which, available memory permitting, 500 can be set to arbitrarily large values). 502 2.8. Overlapping Prefixes 504 In the above discussion, we have assumed that all prefixes are 505 disjoint, as is the case in flat ("mesh") routing. In practice, 506 however, prefixes may overlap: for example, the default route 507 overlaps with all of the routes present in the network. 509 After a route fails, it is not correct in general to switch to a 510 route that subsumes the failed route. Consider for example the 511 following configuration: 513 1 1 514 ::/0 -- A --- B --- C 516 Suppose that node C fails. If B forwards packets destined to C by 517 following the default route, a routing loop will form, and persist 518 until A learns of B's retraction of the direct route to C. B avoids 519 this pitfall by installing an "unreachable" route after a route is 520 retracted; this route is maintained until it can be guaranteed that 521 the former route has been retracted by all of B's neighbours 522 (Section 3.5.5). 524 3. Protocol Operation 526 Every Babel speaker is assigned a router-id, which is an arbitrary 527 string of 8 octets that is assumed unique across the routing domain. 528 For example, routers-ids could be assigned randomly, or they could 529 derived from a link-layer address. (The protocol encoding is 530 slightly more compact when router-ids are assigned in the same manner 531 as the IPv6 layer assigns host IDs.) 533 3.1. Message Transmission and Reception 535 Babel protocol packets are sent in the body of a UDP datagram. Each 536 Babel packet consists of zero or more TLVs. Most TLVs may contain 537 sub-TLVs. 539 The source address of a Babel packet is always a unicast address, 540 link-local in the case of IPv6. Babel packets may be sent to a well- 541 known (link-local) multicast address or to a (link-local) unicast 542 address. In normal operation, a Babel speaker sends both multicast 543 and unicast packets to its neighbours. 545 With the exception of Hello TLVs and acknowledgments, all Babel TLVs 546 can be sent to either unicast or multicast addresses, and their 547 semantics does not depend on whether the destination is a unicast or 548 a multicast address. Hence, a Babel speaker does not need to 549 determine the destination address of a packet that it receives in 550 order to interpret it. 552 A moderate amount of jitter may be applied to packets sent by a Babel 553 speaker: outgoing TLVs are buffered and SHOULD be sent with a small 554 random delay. This is done for two purposes: it avoids 555 synchronisation of multiple Babel speakers across a network [JITTER], 556 and it allows for the aggregation of multiple TLVs into a single 557 packet. 559 The exact delay and amount of jitter applied to a packet depends on 560 whether it contains any urgent TLVs. Acknowledgment TLVs MUST be 561 sent before the deadline specified in the corresponding request. The 562 particular class of updates specified in Section 3.7.2 MUST be sent 563 in a timely manner. The particular class of request and update TLVs 564 specified in Section 3.8.2 SHOULD be sent in a timely manner. 566 3.2. Data Structures 568 In this section, we give a description of the data structures that 569 every Babel speaker maintains. This description is conceptual: a 570 Babel speaker may use different data structures as long as the 571 resulting protocol is the same as the one described in this document. 573 For example, rather than maintaining a single table containing both 574 selected and unselected (fallback) routes, as described in 575 Section 3.2.6 belong, an actual implementation would probably use two 576 tables, one with selected routes and one with fallback routes. 578 3.2.1. Sequence number arithmetic 580 Sequence numbers (seqnos) appear in a number of Babel data 581 structures, and they are interpreted as integers modulo 2^16. For 582 the purposes of this document, arithmetic on sequence numbers is 583 defined as follows. 585 Given a seqno s and an integer n, the sum of s and n is defined by 587 s + n (modulo 2^16) = (s + n) MOD 2^16 589 or, equivalently, 591 s + n (modulo 2^16) = (s + n) AND 65535 593 where MOD is the modulo operation yielding a non-negative integer and 594 AND is the bitwise conjunction operation. 596 Given two sequence numbers s and s', the relation s is less than s' 597 (s < s') is defined by 599 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 601 or equivalently 603 s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. 605 3.2.2. Node Sequence Number 607 A node's sequence number is a 16-bit integer that is included in 608 route updates sent for routes originated by this node. 610 A node increments its sequence number (modulo 2^16) whenever it 611 receives a request for a new sequence number (Section 3.8.1.2). A 612 node SHOULD NOT increment its sequence number (seqno) spontaneously, 613 since increasing seqnos makes it less likely that other nodes will 614 have feasible alternate routes when their selected routes fail. 616 3.2.3. The Interface Table 618 The interface table contains the list of interfaces on which the node 619 speaks the Babel protocol. Every interface table entry contains the 620 interface's outgoing Multicast Hello seqno, a 16-bit integer that is 621 sent with each Multicast Hello TLV on this interface and is 622 incremented (modulo 2^16) whenever a Multicast Hello is sent. (Note 623 that an interface's Multicast Hello seqno is unrelated to the node's 624 seqno.) 626 There are two timers associated with each interface table entry -- 627 the multicast hello timer, which governs the sending of scheduled 628 Multicast Hello and IHU packets, and the update timer, which governs 629 the sending of periodic route updates. 631 3.2.4. The Neighbour Table 633 The neighbour table contains the list of all neighbouring interfaces 634 from which a Babel packet has been recently received. The neighbour 635 table is indexed by pairs of the form (interface, address), and every 636 neighbour table entry contains the following data: 638 o the local node's interface over which this neighbour is reachable; 640 o the address of the neighbouring interface; 642 o a history of recently received Multicast Hello packets from this 643 neighbour; this can, for example, be a sequence of n bits, for 644 some small value n, indicating which of the n hellos most recently 645 sent by this neighbour have been received by the local node; 647 o a history of recently received Unicast Hello packets from this 648 neighbour; 650 o the "transmission cost" value from the last IHU packet received 651 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 652 hold timer for this neighbour has expired; 654 o the neighbour's expected incoming Multicast Hello sequence number, 655 an integer modulo 2^16. 657 o the neighbour's expected incoming Unicast Hello sequence number, 658 an integer modulo 2^16. 660 o the neighbour's outgoing Unicast Hello sequence number, an integer 661 modulo 2^16 that is sent with each Unicast Hello TLV to this 662 neighbour and is incremented (modulo 2^16) whenever a Unicast 663 Hello is sent. (Note that a neighbour's outgoing Unicast Hello 664 seqno is distinct from the interface's outgoing Multicast Hello 665 seqno.) 667 There are three timers associated with each neighbour entry -- the 668 multicast hello timer, which is initialised from the interval value 669 carried by scheduled Multicast Hello TLVs, the unicast hello timer, 670 which is initialised from the interval value carried by scheduled 671 Unicast Hello TLVs, and the IHU timer, which is initialised to a 672 small multiple of the interval carried in IHU TLVs. 674 Note that the neighbour table is indexed by IP addresses, not by 675 router-ids: neighbourship is a relationship between interfaces, not 676 between nodes. Therefore, two nodes with multiple interfaces can 677 participate in multiple neighbourship relationships, a situation that 678 can notably arise when wireless nodes with multiple radios are 679 involved. 681 3.2.5. The Source Table 683 The source table is used to record feasibility distances. It is 684 indexed by triples of the form (prefix, plen, router-id), and every 685 source table entry contains the following data: 687 o the prefix (prefix, plen), where plen is the prefix length, that 688 this entry applies to; 690 o the router-id of a router originating this prefix; 692 o a pair (seqno, metric), this source's feasibility distance. 694 There is one timer associated with each entry in the source table -- 695 the source garbage-collection timer. It is initialised to a time on 696 the order of minutes and reset as specified in Section 3.7.3. 698 3.2.6. The Route Table 700 The route table contains the routes known to this node. It is 701 indexed by triples of the form (prefix, plen, neighbour), and every 702 route table entry contains the following data: 704 o the source (prefix, plen, router-id) for which this route is 705 advertised; 707 o the neighbour that advertised this route; 709 o the metric with which this route was advertised by the neighbour, 710 or FFFF hexadecimal (infinity) for a recently retracted route; 712 o the sequence number with which this route was advertised; 714 o the next-hop address of this route; 715 o a boolean flag indicating whether this route is selected, i.e., 716 whether it is currently being used for forwarding and is being 717 advertised. 719 There is one timer associated with each route table entry -- the 720 route expiry timer. It is initialised and reset as specified in 721 Section 3.5.4. 723 Note that there are two distinct (seqno, metric) pairs associated to 724 each route: the route's distance, which is stored in the route table, 725 and the feasibility distance, stored in the source table and shared 726 between all routes with the same source. 728 3.2.7. The Table of Pending Seqno Requests 730 The table of pending seqno requests contains a list of seqno requests 731 that the local node has sent (either because they have been 732 originated locally, or because they were forwarded) and to which no 733 reply has been received yet. This table is indexed by triples of the 734 form (prefix, plen, router-id), and every entry in this table 735 contains the following data: 737 o the prefix, router-id, and seqno being requested; 739 o the neighbour, if any, on behalf of which we are forwarding this 740 request; 742 o a small integer indicating the number of times that this request 743 will be resent if it remains unsatisfied. 745 There is one timer associated with each pending seqno request; it 746 governs both the resending of requests and their expiry. 748 3.3. Acknowledgments and acknowledgment requests 750 A Babel speaker may request that a neighbour receiving a given packet 751 reply with an explicit acknowledgment within a given time. While the 752 use of acknowledgment requests is optional, every Babel speaker MUST 753 be able to reply to such a request. 755 An acknowledgment MUST be sent to a unicast destination. On the 756 other hand, acknowledgment requests may be sent to either unicast or 757 multicast destinations, in which case they request an acknowledgment 758 from all of the receiving nodes. 760 When to request acknowledgments is a matter of local policy; the 761 simplest strategy is to never request acknowledgments and to rely on 762 periodic updates to ensure that any reachable routes are eventually 763 propagated throughout the routing domain. In order to improve 764 convergence speed and reduce the amount of control traffic, 765 acknowledgment requests MAY be used in order to reliably send urgent 766 updates (Section 3.7.2) and retractions (Section 3.5.5), especially 767 when the number of neighbours on a given interface is small. Since 768 Babel is designed to deal gracefully with packet loss on unreliable 769 media, sending all packets with acknowledgment requests is not 770 necessary, and NOT RECOMMENDED, as the acknowledgments cause 771 additional traffic and may force additional Address Resolution 772 Protocol (ARP) or Neighbour Discovery (ND) exchanges. 774 3.4. Neighbour Acquisition 776 Neighbour acquisition is the process by which a Babel node discovers 777 the set of neighbours heard over each of its interfaces and 778 ascertains bidirectional reachability. On unreliable media, 779 neighbour acquisition additionally provides some statistics that may 780 be useful for link quality computation. 782 Before it can exchange routing information with a neighbour, a Babel 783 node MUST create an entry for that neighbour in the neighbour table. 784 When to do that is implementation-specific; suitable strategies 785 include creating an entry when any Babel packet is received, or 786 creating an entry when a Hello TLV is parsed. Similarly, in order to 787 conserve system resources, an implementation SHOULD discard an entry 788 when it has been unused for long enough; suitable strategies include 789 dropping the neighbour after a timeout, and dropping a neighbour when 790 the associated Hello histories become empty (see Appendix A.2). 792 3.4.1. Reverse Reachability Detection 794 Every Babel node sends Hello TLVs to its neighbours to indicate that 795 it is alive, at regular or irregular intervals. Each Hello TLV 796 carries an increasing (modulo 2^16) sequence number and an upper 797 bound on the time interval until the next Hello of the same type (see 798 below). If the time interval is set to 0, then the Hello TLV does 799 not establish a new promise: the deadline carried by the previous 800 Hello of the same type still applies to the next Hello (if the most 801 recent scheduled Hello of the right kind was received at time t0 and 802 carried interval i, then the previous promise of sending another 803 Hello before time t0 + i still holds). We say that a Hello is 804 "scheduled" if it carries a non-zero interval, and "unscheduled" 805 otherwise. 807 There are two kinds of Hellos: Multicast Hellos, which use a per- 808 interface Hello counter, and Unicast Hellos, which use a per- 809 neighbour counter. A Multicast Hello with a given seqno MUST be sent 810 to all neighbours on a given interface, either by sending it to a 811 multicast address or by sending it to one unicast address per 812 neighbour (hence, the term "Multicast Hello" is a slight misnomer). 813 A Unicast Hello carrying a given seqno should normally be sent to 814 just one neighbour (over unicast), since the sequence numbers of 815 different neighbours are not in general synchronised. 817 Multicast Hellos sent over multicast can be used for neighbour 818 discovery; hence, a node SHOULD send periodic (scheduled) Multicast 819 Hellos unless neighbour discovery is performed by means outside of 820 the Babel protocol. A node MAY send Unicast Hellos or unscheduled 821 Hellos of either kind for any reason, such as reducing the amount of 822 multicast traffic or improving reliability on link technologies with 823 poor support for link-layer multicast. 825 A node MAY send a scheduled Hello ahead of time. A node MAY change 826 its scheduled Hello interval. The Hello interval MAY be decreased at 827 any time; it MAY be increased immediately before sending a Hello TLV, 828 but SHOULD NOT be increased at other times. (Equivalently, a node 829 SHOULD send a scheduled Hello immediately after increasing its Hello 830 interval.) 832 How to deal with received Hello TLVs and what statistics to maintain 833 are considered local implementation matters; typically, a node will 834 maintain some sort of history of recently received Hellos. An 835 example of a suitable algorithm is described in Appendix A.1. 837 After receiving a Hello, or determining that it has missed one, the 838 node recomputes the association's cost (Section 3.4.3) and runs the 839 route selection procedure (Section 3.6). 841 3.4.2. Bidirectional Reachability Detection 843 In order to establish bidirectional reachability, every node sends 844 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 845 IHUs carry an explicit interval value, they MAY be sent less often 846 than Hellos in order to reduce the amount of routing traffic in dense 847 networks; in particular, they SHOULD be sent less often than Hellos 848 over links with little packet loss. While IHUs are conceptually 849 unicast, they MAY be sent to a multicast address in order to avoid an 850 ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 851 into a single packet. 853 In addition to the periodic IHUs, a node MAY, at any time, send an 854 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 855 interval, and it MAY increase its IHU interval immediately before 856 sending an IHU, but SHOULD NOT increase it at any other time. 857 (Equivalently, a node SHOULD send an extra IHU immediately after 858 increasing its Hello interval.) 859 Every IHU TLV contains two pieces of data: the link's rxcost 860 (reception cost) from the sender's perspective, used by the neighbour 861 for computing link costs (Section 3.4.3), and the interval between 862 periodic IHU packets. A node receiving an IHU sets the value of the 863 txcost (transmission cost) maintained in the neighbour table to the 864 value contained in the IHU, and resets the IHU timer associated to 865 this neighbour to a small multiple of the interval value received in 866 the IHU. When a neighbour's IHU timer expires, the neighbour's 867 txcost is set to infinity. 869 After updating a neighbour's txcost, the receiving node recomputes 870 the neighbour's cost (Section 3.4.3) and runs the route selection 871 procedure (Section 3.6). 873 3.4.3. Cost Computation 875 A neighbourship association's link cost is computed from the values 876 maintained in the neighbour table: the statistics kept in the 877 neighbour table about the reception of Hellos, and the txcost 878 computed from received IHU packets. 880 For every neighbour, a Babel node computes a value known as this 881 neighbour's rxcost. This value is usually derived from the Hello 882 history, which may be combined with other data, such as statistics 883 maintained by the link layer. The rxcost is sent to a neighbour in 884 each IHU. 886 Since nodes do not necessarily send periodic Unicast Hellos but do 887 usually send periodic Multicast Hellos (Section 3.4.1), a node SHOULD 888 use an algorithm that yields a finite rxcost when only Multicast 889 Hellos are received, unless interoperability with nodes that only 890 send Multicast Hellos is not required. 892 How the txcost and rxcost are combined in order to compute a link's 893 cost is a matter of local policy; as far as Babel's correctness is 894 concerned, only the following conditions MUST be satisfied: 896 o the cost is strictly positive; 898 o if no Hello TLVs of either kind were received recently, then the 899 cost is infinite; 901 o if the txcost is infinite, then the cost is infinite. 903 Note that while this document does not constrain cost computation any 904 further, not all cost computation strategies will give good results. 905 See Appendix A.2 for examples of strategies for computing a link's 906 cost that are known to work well in practice. 908 3.5. Routing Table Maintenance 910 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 911 seqno, metric), where (prefix, plen) is the prefix for which a route 912 is being advertised, router-id is the router-id of the router 913 originating this update, seqno is a nondecreasing (modulo 2^16) 914 integer that carries the originating router seqno, and metric is the 915 announced metric. 917 Before being accepted, an update is checked against the feasibility 918 condition (Section 3.5.1), which ensures that the route does not 919 create a routing loop. If the feasibility condition is not 920 satisfied, the update is either ignored or prevents the route from 921 being selected, as described in Section 3.5.4. If the feasibility 922 condition is satisfied, then the update cannot possibly cause a 923 routing loop. 925 3.5.1. The Feasibility Condition 927 The feasibility condition is applied to all received updates. The 928 feasibility condition compares the metric in the received update with 929 the metrics of the updates previously sent by the receiving node; 930 updates that fail the feasibility condition, and therefore have 931 metrics large enough to cause a routing loop, are either ignored or 932 prevent the resulting route from being selected. 934 A feasibility distance is a pair (seqno, metric), where seqno is an 935 integer modulo 2^16 and metric is a positive integer. Feasibility 936 distances are compared lexicographically, with the first component 937 inverted: we say that a distance (seqno, metric) is strictly better 938 than a distance (seqno', metric'), written 940 (seqno, metric) < (seqno', metric') 942 when 944 seqno > seqno' or (seqno = seqno' and metric < metric') 946 where sequence numbers are compared modulo 2^16. 948 Given a source (prefix, plen, router-id), a node's feasibility 949 distance for this source is the minimum, according to the ordering 950 defined above, of the distances of all the finite updates ever sent 951 by this particular node for the prefix (prefix, plen) and the given 952 router-id. Feasibility distances are maintained in the source table, 953 the exact procedure is given in Section 3.7.3. 955 A received update is feasible when either it is a retraction (its 956 metric is FFFF hexadecimal), or the advertised distance is strictly 957 better, in the sense defined above, than the feasibility distance for 958 the corresponding source. More precisely, a route advertisement 959 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 960 feasible if one of the following conditions holds: 962 o metric is infinite; or 964 o no entry exists in the source table indexed by (prefix, plen, 965 router-id); or 967 o an entry (prefix, plen, router-id, seqno', metric') exists in the 968 source table, and either 970 * seqno' < seqno or 972 * seqno = seqno' and metric < metric'. 974 Note that the feasibility condition considers the metric advertised 975 by the neighbour, not the route's metric; hence, a fluctuation in a 976 neighbour's cost cannot render a selected route unfeasible. Note 977 further that retractions (updates with infinite metric) are always 978 feasible, since they cannot possibly cause a routing loop. 980 3.5.2. Metric Computation 982 A route's metric is computed from the metric advertised by the 983 neighbour and the neighbour's link cost. Just like cost computation, 984 metric computation is considered a local policy matter; as far as 985 Babel is concerned, the function M(c, m) used for computing a metric 986 from a locally computed link cost and the metric advertised by a 987 neighbour MUST only satisfy the following conditions: 989 o if c is infinite, then M(c, m) is infinite; 991 o M is strictly monotonic: M(c, m) > m. 993 Additionally, the metric SHOULD satisfy the following condition: 995 o M is isotonic: if m <= m', then M(c, m) <= M(c, m'). 997 Note that while strict monotonicity is essential to the integrity of 998 the network (persistent routing loops may arise if it is not 999 satisfied), isotonicity is not: if it is not satisfied, Babel will 1000 still converge to a loop-free configuration, but might not reach a 1001 global optimum (in fact, a global optimum may not even exist). 1003 As with cost computation, not all strategies for computing route 1004 metrics will give good results. In particular, some metrics are more 1005 likely than others to lead to routing instabilities (route flapping). 1006 In Appendix A.3, we give a number of examples of strictly monotonic, 1007 isotonic routing metrics that are known to work well in practice. 1009 3.5.3. Encoding of Updates 1011 In a large network, the bulk of Babel traffic consists of route 1012 updates; hence, some care has been given to encoding them 1013 efficiently. An Update TLV itself only contains the prefix, seqno, 1014 and metric, while the next hop is derived either from the network- 1015 layer source address of the packet or from an explicit Next Hop TLV 1016 in the same packet. The router-id is derived from a separate Router- 1017 Id TLV in the same packet, which optimises the case when multiple 1018 updates are sent with the same router-id. 1020 Additionally, a prefix of the advertised prefix can be omitted in an 1021 Update TLV, in which case it is copied from a previous Update TLV in 1022 the same packet -- this is known as address compression 1023 (Section 4.6.9). 1025 Finally, as a special optimisation for the case when a router-id 1026 coincides with the interface-id part of an IPv6 address, the router- 1027 id can optionally be derived from the low-order bits of the 1028 advertised prefix. 1030 The encoding of updates is described in detail in Section 4.6. 1032 3.5.4. Route Acquisition 1034 When a Babel node receives an update (prefix, plen, router-id, seqno, 1035 metric) from a neighbour neigh with a link cost value equal to cost, 1036 it checks whether it already has a route table entry indexed by 1037 (prefix, plen, neigh). 1039 If no such entry exists: 1041 o if the update is unfeasible, it MAY be ignored; 1043 o if the metric is infinite (the update is a retraction of a route 1044 we do not know about), the update is ignored; 1046 o otherwise, a new entry is created in the route table, indexed by 1047 (prefix, plen, neigh), with source equal to (prefix, plen, router- 1048 id), seqno equal to seqno and an advertised metric equal to the 1049 metric carried by the update. 1051 If such an entry exists: 1053 o if the entry is currently selected, the update is unfeasible, and 1054 the router-id of the update is equal to the router-id of the 1055 entry, then the update MAY be ignored; 1057 o otherwise, the entry's sequence number, advertised metric, metric, 1058 and router-id are updated and, if the advertised metric is not 1059 infinite, the route's expiry timer is reset to a small multiple of 1060 the Interval value included in the update. If the update is 1061 unfeasible, then the (now unfeasible) entry MUST be immediately 1062 unselected. If the update caused the router-id of the entry to 1063 change, an update (possibly a retraction) MUST be sent in a timely 1064 manner (see Section 3.7.2). 1066 Note that the route table may contain unfeasible routes, either 1067 because they were created by an unfeasible update or due to a metric 1068 fluctuation. Such routes are never selected, since they are not 1069 known to be loop-free; should all the feasible routes become 1070 unusable, however, the unfeasible routes can be made feasible and 1071 therefore possible to select by sending requests along them (see 1072 Section 3.8.2). 1074 When a route's expiry timer triggers, the behaviour depends on 1075 whether the route's metric is finite. If the metric is finite, it is 1076 set to infinity and the expiry timer is reset. If the metric is 1077 already infinite, the route is flushed from the route table. 1079 After the route table is updated, the route selection procedure 1080 (Section 3.6) is run. 1082 3.5.5. Hold Time 1084 When a prefix P is retracted, because all routes are unfeasible or 1085 have an infinite metric (whether due to the expiry timer or to other 1086 reasons), and a shorter prefix P' that covers P is reachable, P' 1087 cannot in general be used for routing packets destined to P without 1088 running the risk of creating a routing loop (Section 2.8). 1090 To avoid this issue, whenever a prefix P is retracted, a route table 1091 entry with infinite metric is maintained as described in 1092 Section 3.5.4 above. As long as this entry is maintained, packets 1093 destined to an address within P MUST NOT be forwarded by following a 1094 route for a shorter prefix. This entry is removed as soon as a 1095 finite-metric update for prefix P is received and the resulting route 1096 selected. If no such update is forthcoming, the infinite metric 1097 entry SHOULD be maintained at least until it is guaranteed that no 1098 neighbour has selected the current node as next-hop for prefix P. 1099 This can be achieved by either: 1101 o waiting until the route's expiry timer has expired 1102 (Section 3.5.4); 1104 o sending a retraction with an acknowledgment request (Section 3.3) 1105 to every reachable neighbour that has not explicitly retracted 1106 prefix P and waiting for all acknowledgments. 1108 The former option is simpler and ensures that at that point, any 1109 routes for prefix P pointing at the current node have expired. 1110 However, since the expiry time can be as high as a few minutes, doing 1111 that prevents automatic aggregation by creating spurious black-holes 1112 for aggregated routes. The latter option is RECOMMENDED as it 1113 dramatically reduces the time for which a prefix is unreachable in 1114 the presence of aggregated routes. 1116 3.6. Route Selection 1118 Route selection is the process by which a single route for a given 1119 prefix is selected to be used for forwarding packets and to be re- 1120 advertised to a node's neighbours. 1122 Babel is designed to allow flexible route selection policies. As far 1123 as the protocol's correctness is concerned, the route selection 1124 policy MUST only satisfy the following properties: 1126 o a route with infinite metric (a retracted route) is never 1127 selected; 1129 o an unfeasible route is never selected. 1131 Note, however, that Babel does not naturally guarantee the stability 1132 of routing, and configuring conflicting route selection policies on 1133 different routers may lead to persistent route oscillation. 1135 Route selection is a difficult problem, since a good route selection 1136 policy needs to take into account multiple mutually contradictory 1137 criteria; in roughly decreasing order of importance, these are: 1139 o routes with a small metric should be preferred to routes with a 1140 large metric; 1142 o switching router-ids should be avoided; 1144 o routes through stable neighbours should be preferred to routes 1145 through unstable ones; 1147 o stable routes should be preferred to unstable ones; 1149 o switching next hops should be avoided. 1151 A simple but useful strategy is to choose the feasible route with the 1152 smallest metric, with a small amount of hysteresis applied to avoid 1153 switching router-ids too often. 1155 After the route selection procedure is run, triggered updates 1156 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1158 3.7. Sending Updates 1160 A Babel speaker advertises to its neighbours its set of selected 1161 routes. Normally, this is done by sending one or more multicast 1162 packets containing Update TLVs on all of its connected interfaces; 1163 however, on link technologies where multicast is significantly more 1164 expensive than unicast, a node MAY choose to send multiple copies of 1165 updates in unicast packets, especially when the number of neighbours 1166 is small. 1168 Additionally, in order to ensure that any black-holes are reliably 1169 cleared in a timely manner, a Babel node sends retractions (updates 1170 with an infinite metric) for any recently retracted prefixes. 1172 If an update is for a route injected into the Babel domain by the 1173 local node (e.g., it carries the address of a local interface, the 1174 prefix of a directly attached network, or a prefix redistributed from 1175 a different routing protocol), the router-id is set to the local 1176 node's router-id, the metric is set to some arbitrary finite value 1177 (typically 0), and the seqno is set to the local router's sequence 1178 number. 1180 If an update is for a route learned from another Babel speaker, the 1181 router-id and sequence number are copied from the route table entry, 1182 and the metric is computed as specified in Section 3.5.2. 1184 3.7.1. Periodic Updates 1186 Every Babel speaker periodically advertises all of its selected 1187 routes on all of its interfaces, including any recently retracted 1188 routes. Since Babel doesn't suffer from routing loops (there is no 1189 "counting to infinity") and relies heavily on triggered updates 1190 (Section 3.7.2), this full dump only needs to happen infrequently. 1192 3.7.2. Triggered Updates 1194 In addition to periodic routing updates, a Babel speaker sends 1195 unscheduled, or triggered, updates in order to inform its neighbours 1196 of a significant change in the network topology. 1198 A change of router-id for the selected route to a given prefix may be 1199 indicative of a routing loop in formation; hence, a node MUST send a 1200 triggered update in a timely manner whenever it changes the selected 1201 router-id for a given destination. Additionally, it SHOULD make a 1202 reasonable attempt at ensuring that all reachable neighbours receive 1203 this update. 1205 There are two strategies for ensuring that. If the number of 1206 neighbours is small, then it is reasonable to send the update 1207 together with an acknowledgment request; the update is resent until 1208 all neighbours have acknowledged the packet, up to some number of 1209 times. If the number of neighbours is large, however, requesting 1210 acknowledgments from all of them might cause a non-negligible amount 1211 of network traffic; in that case, it may be preferable to simply 1212 repeat the update some reasonable number of times (say, 5 for 1213 wireless and 2 for wired links). 1215 A route retraction is somewhat less worrying: if the route retraction 1216 doesn't reach all neighbours, a black-hole might be created, which, 1217 unlike a routing loop, does not endanger the integrity of the 1218 network. When a route is retracted, a node SHOULD send a triggered 1219 update and SHOULD make a reasonable attempt at ensuring that all 1220 neighbours receive this retraction. 1222 Finally, a node MAY send a triggered update when the metric for a 1223 given prefix changes in a significant manner, due to a received 1224 update, because a link's cost has changed, or because a different 1225 next hop has been selected. A node SHOULD NOT send triggered updates 1226 for other reasons, such as when there is a minor fluctuation in a 1227 route's metric, when the selected next hop changes, or to propagate a 1228 new sequence number (except to satisfy a request, as specified in 1229 Section 3.8). 1231 3.7.3. Maintaining Feasibility Distances 1233 Before sending an update (prefix, plen, router-id, seqno, metric) 1234 with finite metric (i.e., not a route retraction), a Babel node 1235 updates the feasibility distance maintained in the source table. 1236 This is done as follows. 1238 If no entry indexed by (prefix, plen, router-id) exists in the source 1239 table, then one is created with value (prefix, plen, router-id, 1240 seqno, metric). 1242 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1243 it is updated as follows: 1245 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1247 o if seqno = seqno' and metric' > metric, then metric' := metric; 1249 o otherwise, nothing needs to be done. 1251 The garbage-collection timer for the entry is then reset. Note that 1252 the feasibility distance is not updated and the garbage-collection 1253 timer is not reset when a retraction (an update with infinite metric) 1254 is sent. 1256 When the garbage-collection timer expires, the entry is removed from 1257 the source table. 1259 3.7.4. Split Horizon 1261 When running over a transitive, symmetric link technology, e.g., a 1262 point-to-point link or a wired LAN technology such as Ethernet, a 1263 Babel node SHOULD use an optimisation known as split horizon. When 1264 split horizon is used on a given interface, a routing update for 1265 prefix P is not sent on the particular interface over which the 1266 selected route towards prefix P was learnt. 1268 Split horizon SHOULD NOT be applied to an interface unless the 1269 interface is known to be symmetric and transitive; in particular, 1270 split horizon is not applicable to decentralised wireless link 1271 technologies (e.g., IEEE 802.11 in ad hoc mode) when routing updates 1272 are sent over multicast. 1274 3.8. Explicit Requests 1276 In normal operation, a node's route table is populated by the regular 1277 and triggered updates sent by its neighbours. Under some 1278 circumstances, however, a node sends explicit requests in order to 1279 cause a resynchronisation with the source after a mobility event or 1280 to prevent a route from spuriously expiring. 1282 The Babel protocol provides two kinds of explicit requests: route 1283 requests, which simply request an update for a given prefix, and 1284 seqno requests, which request an update for a given prefix with a 1285 specific sequence number. The former are never forwarded; the latter 1286 are forwarded if they cannot be satisfied by the receiver. 1288 3.8.1. Handling Requests 1290 Upon receiving a request, a node either forwards the request or sends 1291 an update in reply to the request, as described in the following 1292 sections. If this causes an update to be sent, the update is either 1293 sent to a multicast address on the interface on which the request was 1294 received, or to the unicast address of the neighbour that sent the 1295 request. 1297 The exact behaviour is different for route requests and seqno 1298 requests. 1300 3.8.1.1. Route Requests 1302 When a node receives a route request for a given prefix, it checks 1303 its route table for a selected route to this exact prefix. If such a 1304 route exists, it MUST send an update (over unicast or over 1305 multicast); if such a route does not, it MUST send a retraction for 1306 that prefix. 1308 When a node receives a wildcard route request, it SHOULD send a full 1309 route table dump. Full route dumps MAY be rate-limited, especially 1310 if they are sent over multicast. 1312 3.8.1.2. Seqno Requests 1314 When a node receives a seqno request for a given router-id and 1315 sequence number, it checks whether its route table contains a 1316 selected entry for that prefix. If a selected route for the given 1317 prefix exists, it has finite metric, and either the router-ids are 1318 different or the router-ids are equal and the entry's sequence number 1319 is no smaller (modulo 2^16) than the requested sequence number, the 1320 node MUST send an update for the given prefix. If the router-ids 1321 match but the requested seqno is larger (modulo 2^16) than the route 1322 entry's, the node compares the router-id against its own router-id. 1323 If the router-id is its own, then it increases its sequence number by 1324 1 (modulo 2^16) and sends an update. A node MUST NOT increase its 1325 sequence number by more than 1 in response to a seqno request. 1327 Otherwise, if the requested router-id is not its own, the received 1328 request's hop count is 2 or more, and the node is advertising the 1329 prefix to its neighbours, the node selects a neighbour to forward the 1330 request to as follows: 1332 o if the node has one or more feasible routes toward the requested 1333 prefix with a next hop that is not the requesting node, then the 1334 node MUST forward the request to the next hop of one such route; 1336 o otherwise, if the node has one or more (not necessarily feasible) 1337 routes to the requested prefix with a next hop that is not the 1338 requesting node, then the node SHOULD forward the request to the 1339 next hop of one such route. 1341 In order to actually forward the request, the node decrements the hop 1342 count and sends the request in a unicast packet destined to the 1343 selected neighbour. 1345 A node SHOULD maintain a list of recently forwarded seqno requests 1346 and forward the reply (an update with a sufficiently large seqno) in 1347 a timely manner. A node SHOULD compare every incoming seqno request 1348 against its list of recently forwarded seqno requests and avoid 1349 forwarding it if it is redundant (i.e., if it has recently sent a 1350 request with the same prefix, router-id and a seqno that is not 1351 smaller modulo 2^16). 1353 Since the request-forwarding mechanism does not necessarily obey the 1354 feasibility condition, it may get caught in routing loops; hence, 1355 requests carry a hop count to limit the time during which they remain 1356 in the network. However, since requests are only ever forwarded as 1357 unicast packets, the initial hop count need not be kept particularly 1358 low, and performing an expanding horizon search is not necessary. A 1359 single request MUST NOT be duplicated: it MUST NOT be forwarded to a 1360 multicast address, and it MUST NOT be forwarded to multiple 1361 neighbours. However, if a seqno request is resent by its originator, 1362 the subsequent copies MAY be forwarded to a different neighbour than 1363 the initial one. 1365 3.8.2. Sending Requests 1367 A Babel node MAY send a route or seqno request at any time, to a 1368 multicast or a unicast address; there is only one case when 1369 originating requests is required (Section 3.8.2.1). 1371 3.8.2.1. Avoiding Starvation 1373 When a route is retracted or expires, a Babel node usually switches 1374 to another feasible route for the same prefix. It may be the case, 1375 however, that no such routes are available. 1377 A node that has lost all feasible routes to a given destination but 1378 still has unexpired unfeasible routes to that destination MUST send a 1379 seqno request; if it doesn't have any such routes, it MAY still send 1380 a seqno request. The router-id of the request is set to the router- 1381 id of the route that it has just lost, and the requested seqno is the 1382 value contained in the source table plus 1. 1384 If the node has any (unfeasible) routes to the requested destination, 1385 then it MUST send the request to at least one of the next-hop 1386 neighbours that advertised these routes, and SHOULD send it to all of 1387 them; in any case, it MAY send the request to any other neighbours, 1388 whether they advertise a route to the requested destination or not. 1389 A simple implementation strategy is therefore to unconditionally 1390 multicast the request over all interfaces. 1392 Similar requests will be sent by other nodes that are affected by the 1393 route's loss. If the network is still connected, and assuming no 1394 packet loss, then at least one of these requests will be forwarded to 1395 the source, resulting in a route being advertised with a new sequence 1396 number. (Due to duplicate suppression, only a small number of such 1397 requests will actually reach the source.) 1399 In order to compensate for packet loss, a node SHOULD repeat such a 1400 request a small number of times if no route becomes feasible within a 1401 short time. In the presence of heavy packet loss, however, all such 1402 requests might be lost; in that case, the mechanism in the next 1403 section will eventually ensure that a new seqno is received. 1405 3.8.2.2. Dealing with Unfeasible Updates 1407 When a route's metric increases, a node might receive an unfeasible 1408 update for a route that it has currently selected. As specified in 1409 Section 3.5.1, the receiving node will either ignore the update or 1410 unselect the route. 1412 In order to keep routes from spuriously expiring because they have 1413 become unfeasible, a node SHOULD send a unicast seqno request when it 1414 receives an unfeasible update for a route that is currently selected. 1415 The requested sequence number is computed from the source table as in 1416 Section 3.8.2.1 above. 1418 Additionally, since metric computation does not necessarily coincide 1419 with the delay in propagating updates, a node might receive an 1420 unfeasible update from a currently unselected neighbour that is 1421 preferable to the currently selected route (e.g., because it has a 1422 much smaller metric); in that case, the node SHOULD send a unicast 1423 seqno request to the neighbour that advertised the preferable update. 1425 3.8.2.3. Preventing Routes from Expiring 1427 In normal operation, a route's expiry timer never triggers: since a 1428 route's hold time is computed from an explicit interval included in 1429 Update TLVs, a new update (possibly a retraction) should arrive in 1430 time to prevent a route from expiring. 1432 In the presence of packet loss, however, it may be the case that no 1433 update is successfully received for an extended period of time, 1434 causing a route to expire. In order to avoid such spurious expiry, 1435 shortly before a selected route expires, a Babel node SHOULD send a 1436 unicast route request to the neighbour that advertised this route; 1437 since nodes always send either updates or retractions in response to 1438 non-wildcard route requests (Section 3.8.1.1), this will usually 1439 result in the route being either refreshed or retracted. 1441 3.8.2.4. Acquiring New Neighbours 1443 In order to speed up convergence after a mobility event, a node MAY 1444 send a unicast wildcard request after acquiring a new neighbour. 1445 Additionally, a node MAY send a small number of multicast wildcard 1446 requests shortly after booting. Note however that doing that 1447 carelessly can cause serious congestion when a whole network is 1448 rebooted, especially on link layers with high per-packet overhead 1449 (e.g., IEEE 802.11). 1451 4. Protocol Encoding 1453 A Babel packet is sent as the body of a UDP datagram, with network- 1454 layer hop count set to 1, destined to a well-known multicast address 1455 or to a unicast address, over IPv4 or IPv6; in the case of IPv6, 1456 these addresses are link-local. Both the source and destination UDP 1457 port are set to a well-known port number. A Babel packet MUST be 1458 silently ignored unless its source address is either a link-local 1459 IPv6 address or an IPv4 address belonging to the local network, and 1460 its source port is the well-known Babel port. It MAY be silently 1461 ignored if its destination address is a global IPv6 address. 1463 In order to minimise the number of packets being sent while avoiding 1464 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1465 the size of the packets it sends, up to the outgoing interface's MTU 1466 adjusted for lower-layer headers (28 octets for UDP over IPv4, 48 1467 octets for UDP over IPv6). It MUST NOT send packets larger than the 1468 attached interface's MTU adjusted for lower-layer headers or 512 1469 octets, whichever is larger, but not exceeding 2^16 - 1 adjusted for 1470 lower-layer headers. Every Babel speaker MUST be able to receive 1471 packets that are as large as any attached interface's MTU adjusted 1472 for lower-layer headers or 512 octets, whichever is larger. Babel 1473 packets MUST NOT be sent in IPv6 Jumbograms. 1475 In order to avoid global synchronisation of a Babel network and to 1476 aggregate multiple TLVs into large packets, a Babel node SHOULD 1477 buffer every TLV and delay sending a packet by a small, randomly 1478 chosen delay [JITTER]. In order to allow accurate computation of 1479 packet loss rates, this delay MUST NOT be larger than half the 1480 advertised Hello interval. 1482 4.1. Data Types 1484 4.1.1. Interval 1486 Relative times are carried as 16-bit values specifying a number of 1487 centiseconds (hundredths of a second). This allows times up to 1488 roughly 11 minutes with a granularity of 10ms, which should cover all 1489 reasonable applications of Babel. 1491 4.1.2. Router-Id 1493 A router-id is an arbitrary 8-octet value. A router-id MUST NOT 1494 consist of either all zeroes or all ones. 1496 4.1.3. Address 1498 Since the bulk of the protocol is taken by addresses, multiple ways 1499 of encoding addresses are defined. Additionally, a common subnet 1500 prefix may be omitted when multiple addresses are sent in a single 1501 packet -- this is known as address compression (Section 4.6.9). 1503 Address encodings: 1505 o AE 0: wildcard address. The value is 0 octets long. 1507 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1509 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1511 o AE 3: link-local IPv6 address. Compression is not allowed. The 1512 value is 8 octets long, a prefix of fe80::/64 is implied. 1514 The address family associated to an address encoding is either IPv4 1515 or IPv6; it is undefined for AE 0, IPv4 for AE 1, and IPv6 for AEs 2 1516 and 3. 1518 4.1.4. Prefixes 1520 A network prefix is encoded just like a network address, but it is 1521 stored in the smallest number of octets that are enough to hold the 1522 significant bits (up to the prefix length). 1524 4.2. Packet Format 1526 A Babel packet consists of a 4-octet header, followed by a sequence 1527 of TLVs. 1529 0 1 2 3 1530 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 1531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1532 | Magic | Version | Body length | 1533 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1534 | Packet Body ... 1535 +-+-+-+-+-+-+-+-+-+-+-+-+- 1537 Fields : 1539 Magic The arbitrary but carefully chosen value 42 (decimal); 1540 packets with a first octet different from 42 MUST be 1541 silently ignored. 1543 Version This document specifies version 2 of the Babel protocol. 1544 Packets with a second octet different from 2 MUST be 1545 silently ignored. 1547 Body length The length in octets of the body following the packet 1548 header (excluding the Magic, Version and Body length 1549 fields). 1551 Body The packet body; a sequence of TLVs. 1553 Any data following the body MUST be silently ignored. 1555 4.3. TLV Format 1557 With the exception of Pad1, all TLVs have the following structure: 1559 0 1 2 3 1560 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1562 | Type | Length | Payload... 1563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1565 Fields : 1567 Type The type of the TLV. 1569 Length The length of the body, exclusive of the Type and Length 1570 fields. If the body is longer than the expected length of 1571 a given type of TLV, any extra data MUST be silently 1572 ignored. 1574 Payload The TLV payload, which consists of a body and, for selected 1575 TLV types, an optional list of sub-TLVs. 1577 TLVs with an unknown type value MUST be silently ignored. 1579 4.4. Sub-TLV Format 1581 Every TLV carries an explicit length in its header; however, most 1582 TLVs are self-terminating, in the sense that it is possible to 1583 determine the length of the body without reference to the explicit 1584 Length field. If a TLV has a self-terminating format, then it MAY 1585 allow a sequence of sub-TLVs to follow the body. 1587 Sub-TLVs have the same structure as TLVs. With the exception of 1588 PAD1, all TLVs have the following structure: 1590 0 1 2 3 1591 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 1592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1593 | Type | Length | Body... 1594 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1596 Fields : 1598 Type The type of the sub-TLV. 1600 Length The length of the body, in octets, exclusive of the Type 1601 and Length fields. 1603 Body The sub-TLV body, the interpretation of which depends on 1604 both the type of the sub-TLV and the type of the TLV within 1605 which it is embedded. 1607 The most-significant bit of the sub-TLV, called the mandatory bit, 1608 indicates how to handle unknown sub-TLVs. If the mandatory bit is 1609 not set, then an unknown sub-TLV MUST be silently ignored, and the 1610 rest of the TLV processed normally. If the mandatory bit is set, 1611 then the whole enclosing TLV MUST be silently ignored (except for 1612 updating the parser state by a Router-Id, Next-Hop or Update TLV, see 1613 Section 4.6.7, Section 4.6.8, and Section 4.6.9). 1615 4.5. Parser state 1617 Babel uses a stateful parser: a TLV may refer to data from a previous 1618 TLV. The parser state consists of the following pieces of data: 1620 o for each address encoding that allows compression, the current 1621 default prefix; this is undefined at the start of the packet, and 1622 is updated by each Update TLV with the Prefix flag set 1623 (Section 4.6.9); 1625 o for each address family (IPv4 or IPv6), the current next-hop; this 1626 is the source address of the enclosing packet for the matching 1627 address family at the start of a packet, and is updated by each 1628 Next-Hop TLV (Section 4.6.8); 1630 o the current router-id; this is undefined at the start of the 1631 packet, and is updated by each Router-ID TLV (Section 4.6.7) and 1632 by each Update TLV with Router-Id flag set. 1634 Since the parser state is separate from the bulk of Babel's state, 1635 and since for correct parsing it must be identical across 1636 implementations, it is updated before checking for mandatory TLVs: 1637 parsing a TLV MUST update the parser state even if the TLV is 1638 otherwise ignored due to an unknown mandatory sub-TLV. 1640 4.6. Details of Specific TLVs 1642 4.6.1. Pad1 1644 0 1645 0 1 2 3 4 5 6 7 1646 +-+-+-+-+-+-+-+-+ 1647 | Type = 0 | 1648 +-+-+-+-+-+-+-+-+ 1650 Fields : 1652 Type Set to 0 to indicate a Pad1 TLV. 1654 This TLV is silently ignored on reception. 1656 4.6.2. PadN 1658 0 1 2 3 1659 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 1660 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1661 | Type = 1 | Length | MBZ... 1662 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1663 Fields : 1665 Type Set to 1 to indicate a PadN TLV. 1667 Length The length of the body, exclusive of the Type and Length 1668 fields. 1670 MBZ Set to 0 on transmission. 1672 This TLV is silently ignored on reception. 1674 4.6.3. Acknowledgment Request 1676 0 1 2 3 1677 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 1678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1679 | Type = 2 | Length | Reserved | 1680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1681 | Nonce | Interval | 1682 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1684 This TLV requests that the receiver send an Acknowledgment TLV within 1685 the number of centiseconds specified by the Interval field. 1687 Fields : 1689 Type Set to 2 to indicate an Acknowledgment Request TLV. 1691 Length The length of the body, exclusive of the Type and Length 1692 fields. 1694 Reserved Sent as 0 and MUST be ignored on reception. 1696 Nonce An arbitrary value that will be echoed in the receiver's 1697 Acknowledgment TLV. 1699 Interval A time interval in centiseconds after which the sender will 1700 assume that this packet has been lost. This MUST NOT be 0. 1701 The receiver MUST send an Acknowledgment TLV before this 1702 time has elapsed (with a margin allowing for propagation 1703 time). 1705 This TLV is self-terminating, and allows sub-TLVs. 1707 4.6.4. Acknowledgment 1709 0 1 2 3 1710 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 1711 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1712 | Type = 3 | Length | Nonce | 1713 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1715 This TLV is sent by a node upon receiving an Acknowledgment Request. 1717 Fields : 1719 Type Set to 3 to indicate an Acknowledgment TLV. 1721 Length The length of the body, exclusive of the Type and Length 1722 fields. 1724 Nonce Set to the Nonce value of the Acknowledgment Request that 1725 prompted this Acknowledgment. 1727 Since nonce values are not globally unique, this TLV MUST be sent to 1728 a unicast address. 1730 This TLV is self-terminating, and allows sub-TLVs. 1732 4.6.5. Hello 1734 0 1 2 3 1735 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 1736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1737 | Type = 4 | Length | Flags | 1738 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1739 | Seqno | Interval | 1740 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1742 This TLV is used for neighbour discovery and for determining a 1743 neighbour's reception cost. 1745 Fields : 1747 Type Set to 4 to indicate a Hello TLV. 1749 Length The length of the body, exclusive of the Type and Length 1750 fields. 1752 Flags The individual bits of this field specify special handling 1753 of this TLV (see below). 1755 Seqno If the Unicast flag is set, this is the value of the 1756 sending node's outgoing Unicast Hello seqno for this 1757 neighbour. Otherwise, it is the sending node's outgoing 1758 Multicast Hello seqno for this interface. 1760 Interval If non-zero, this is an upper bound, expressed in 1761 centiseconds, on the time after which the sending node will 1762 send a new scheduled Hello TLV with the same setting of the 1763 Unicast flag. If this is 0, then this Hello represents an 1764 unscheduled Hello, and doesn't carry any new information 1765 about times at which Hellos are sent. 1767 The Flags field is interpreted as follows: 1769 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1770 |U|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| 1771 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1773 o U (Unicast) flag (8000 hexadecimal): if set, then this Hello 1774 represents a Unicast Hello, otherwise it represents a Multicast 1775 Hello; 1777 o X: all other bits MUST be sent as 0 and silently ignored on 1778 reception. 1780 Every time a Hello is sent, the corresponding seqno counter MUST be 1781 incremented. Since there is a single seqno counter for all the 1782 Multicast Hellos sent by a given node over a given interface, if the 1783 Unicast flag is not set, this TLV MUST be sent to all neighbors on 1784 this link, which can be achieved by sending to a multicast 1785 destination, or by sending multiple packets to the unicast addresses 1786 of all reachable neighbours. Conversely, if the Unicast flag is set, 1787 this TLV MUST be sent to a single neighbour, which can achieved by 1788 sending to a unicast destination. In order to avoid large 1789 discontinuities in link quality, multiple Hello TLVs SHOULD NOT be 1790 sent in the same packet. 1792 This TLV is self-terminating, and allows sub-TLVs. 1794 4.6.6. IHU 1795 0 1 2 3 1796 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 1797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1798 | Type = 5 | Length | AE | Reserved | 1799 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1800 | Rxcost | Interval | 1801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1802 | Address... 1803 +-+-+-+-+-+-+-+-+-+-+-+- 1805 An IHU ("I Heard You") TLV is used for confirming bidirectional 1806 reachability and carrying a link's transmission cost. 1808 Fields : 1810 Type Set to 5 to indicate an IHU TLV. 1812 Length The length of the body, exclusive of the Type and Length 1813 fields. 1815 AE The encoding of the Address field. This should be 1 or 3 1816 in most cases. As an optimisation, it MAY be 0 if the TLV 1817 is sent to a unicast address, if the association is over a 1818 point-to-point link, or when bidirectional reachability is 1819 ascertained by means outside of the Babel protocol. 1821 Reserved Sent as 0 and MUST be ignored on reception. 1823 Rxcost The rxcost according to the sending node of the interface 1824 whose address is specified in the Address field. The value 1825 FFFF hexadecimal (infinity) indicates that this interface 1826 is unreachable. 1828 Interval An upper bound, expressed in centiseconds, on the time 1829 after which the sending node will send a new IHU; this MUST 1830 NOT be 0. The receiving node will use this value in order 1831 to compute a hold time for this symmetric association. 1833 Address The address of the destination node, in the format 1834 specified by the AE field. Address compression is not 1835 allowed. 1837 Conceptually, an IHU is destined to a single neighbour. However, IHU 1838 TLVs contain an explicit destination address, and MAY be sent to a 1839 multicast address, as this allows aggregation of IHUs destined to 1840 distinct neighbours into a single packet and avoids the need for an 1841 ARP or Neighbour Discovery exchange when a neighbour is not being 1842 used for data traffic. 1844 IHU TLVs with an unknown value in the AE field MUST be silently 1845 ignored. 1847 This TLV is self-terminating, and allows sub-TLVs. 1849 4.6.7. Router-Id 1851 0 1 2 3 1852 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1853 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1854 | Type = 6 | Length | Reserved | 1855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1856 | | 1857 + Router-Id + 1858 | | 1859 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1861 A Router-Id TLV establishes a router-id that is implied by subsequent 1862 Update TLVs. This TLV sets the router-id even if it is otherwise 1863 ignored due to an unknown mandatory sub-TLV. 1865 Fields : 1867 Type Set to 6 to indicate a Router-Id TLV. 1869 Length The length of the body, exclusive of the Type and Length 1870 fields. 1872 Reserved Sent as 0 and MUST be ignored on reception. 1874 Router-Id The router-id for routes advertised in subsequent Update 1875 TLVs. This MUST NOT consist of all zeroes or all ones. 1877 This TLV is self-terminating, and allows sub-TLVs. 1879 4.6.8. Next Hop 1881 0 1 2 3 1882 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 1883 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1884 | Type = 7 | Length | AE | Reserved | 1885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1886 | Next hop... 1887 +-+-+-+-+-+-+-+-+-+-+-+- 1889 A Next Hop TLV establishes a next-hop address for a given address 1890 family (IPv4 or IPv6) that is implied in subsequent Update TLVs. 1892 This TLV sets up the next-hop for subsequent Update TLVs even if it 1893 is otherwise ignored due to an unknown mandatory sub-TLV. 1895 Fields : 1897 Type Set to 7 to indicate a Next Hop TLV. 1899 Length The length of the body, exclusive of the Type and Length 1900 fields. 1902 AE The encoding of the Address field. This SHOULD be 1 or 3 1903 and MUST NOT be 0. 1905 Reserved Sent as 0 and MUST be ignored on reception. 1907 Next hop The next-hop address advertised by subsequent Update TLVs, 1908 for this address family. 1910 When the address family matches the network-layer protocol that this 1911 packet is transported over, a Next Hop TLV is not needed: in the 1912 absence of a Next Hop TLV in a given address family, the next hop 1913 address is taken to be the source address of the packet. 1915 Next Hop TLVs with an unknown value for the AE field MUST be silently 1916 ignored. 1918 This TLV is self-terminating, and allows sub-TLVs. 1920 4.6.9. Update 1922 0 1 2 3 1923 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 1924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1925 | Type = 8 | Length | AE | Flags | 1926 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1927 | Plen | Omitted | Interval | 1928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1929 | Seqno | Metric | 1930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1931 | Prefix... 1932 +-+-+-+-+-+-+-+-+-+-+-+- 1934 An Update TLV advertises or retracts a route. As an optimisation, it 1935 can optionally have the side effect of establishing a new implied 1936 router-id and a new default prefix. 1938 Fields : 1940 Type Set to 8 to indicate an Update TLV. 1942 Length The length of the body, exclusive of the Type and Length 1943 fields. 1945 AE The encoding of the Prefix field. 1947 Flags The individual bits of this field specify special handling 1948 of this TLV (see below). 1950 Plen The length of the advertised prefix. 1952 Omitted The number of octets that have been omitted at the 1953 beginning of the advertised prefix and that should be taken 1954 from a preceding Update TLV in the same address family with 1955 the Prefix flag set. 1957 Interval An upper bound, expressed in centiseconds, on the time 1958 after which the sending node will send a new update for 1959 this prefix. This MUST NOT be 0. The receiving node will 1960 use this value to compute a hold time for the route table 1961 entry. The value FFFF hexadecimal (infinity) expresses 1962 that this announcement will not be repeated unless a 1963 request is received (Section 3.8.2.3). 1965 Seqno The originator's sequence number for this update. 1967 Metric The sender's metric for this route. The value FFFF 1968 hexadecimal (infinity) means that this is a route 1969 retraction. 1971 Prefix The prefix being advertised. This field's size is 1972 (Plen/8 - Omitted) rounded upwards. 1974 The Flags field is interpreted as follows: 1976 +-+-+-+-+-+-+-+-+ 1977 |P|R|X|X|X|X|X|X| 1978 +-+-+-+-+-+-+-+-+ 1980 o P (Prefix) flag (80 hexadecimal): if set, then this Update 1981 establishes a new default prefix for subsequent Update TLVs with a 1982 matching address encoding within the same packet, even if this TLV 1983 is otherwise ignored due to an unknown mandatory sub-TLV; 1985 o R (Router-Id) flag (40 hexadecimal): if set, then this TLV 1986 establishes a new default router-id for this TLV and subsequent 1987 Update TLVs in the same packet, even if this TLV is otherwise 1988 ignored due to an unknown mandatory sub-TLV. This router-id is 1989 computed from the first address of the advertised prefix as 1990 follows: 1992 * if the length of the address is 8 octets or more, then the new 1993 router-id is taken from the 8 last octets of the address; 1995 * if the length of the address is smaller than 8 octets, then the 1996 new router-id consists of the required number of zero octets 1997 followed by the address, i.e., the address is stored on the 1998 right of the router-id. For example, for an IPv4 address, the 1999 router-id consists of 4 octets of zeroes followed by the IPv4 2000 address. 2002 o X: all other bits MUST be sent as 0 and silently ignored on 2003 reception. 2005 The prefix being advertised by an Update TLV is computed as follows: 2007 o the first Omitted octets of the prefix are taken from the previous 2008 Update TLV with the Prefix flag set and the same address encoding, 2009 even if it was ignored due to an unknown mandatory sub-TLV; 2011 o the next (Plen/8 - Omitted) rounded upwards octets are taken from 2012 the Prefix field; 2014 o the remaining octets are set to 0. If AE is 3 (link-local IPv6), 2015 Omitted MUST be 0) 2017 If the Metric field is finite, the router-id of the originating node 2018 for this announcement is taken from the prefix advertised by this 2019 Update if the Router-Id flag is set, computed as described above. 2020 Otherwise, it is taken either from the preceding Router-Id packet, or 2021 the preceding Update packet with the Router-Id flag set, whichever 2022 comes last, even if that TLV is otherwise ignored due to an unknown 2023 mandatory sub-TLV. 2025 The next-hop address for this update is taken from the last preceding 2026 Next Hop TLV with a matching address family (IPv4 or IPv6) in the 2027 same packet even if it was otherwise ignored due to an unknown 2028 mandatory sub-TLV; if no such TLV exists, it is taken from the 2029 network-layer source address of this packet. 2031 If the metric field is FFFF hexadecimal, this TLV specifies a 2032 retraction. In that case, the router-id, next-hop and seqno are not 2033 used. AE MAY then be 0, in which case this Update retracts all of 2034 the routes previously advertised by the sending interface. If the 2035 metric is finite, AE MUST NOT be 0. If the metric is infinite and AE 2036 is 0, Plen and Omitted MUST both be 0. 2038 Update TLVs with an unknown value in the AE field MUST be silently 2039 ignored. 2041 This TLV is self-terminating, and allows sub-TLVs. 2043 4.6.10. Route Request 2045 0 1 2 3 2046 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 2047 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2048 | Type = 9 | Length | AE | Plen | 2049 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2050 | Prefix... 2051 +-+-+-+-+-+-+-+-+-+-+-+- 2053 A Route Request TLV prompts the receiver to send an update for a 2054 given prefix, or a full route table dump. 2056 Fields : 2058 Type Set to 9 to indicate a Route Request TLV. 2060 Length The length of the body, exclusive of the Type and Length 2061 fields. 2063 AE The encoding of the Prefix field. The value 0 specifies 2064 that this is a request for a full route table dump (a 2065 wildcard request). 2067 Plen The length of the requested prefix. 2069 Prefix The prefix being requested. This field's size is Plen/8 2070 rounded upwards. 2072 A Request TLV prompts the receiver to send an update message 2073 (possibly a retraction) for the prefix specified by the AE, Plen, and 2074 Prefix fields, or a full dump of its route table if AE is 0 (in which 2075 case Plen MUST be 0 and Prefix is of length 0). 2077 This TLV is self-terminating, and allows sub-TLVs. 2079 4.6.11. Seqno Request 2081 0 1 2 3 2082 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 2083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2084 | Type = 10 | Length | AE | Plen | 2085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2086 | Seqno | Hop Count | Reserved | 2087 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2088 | | 2089 + Router-Id + 2090 | | 2091 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2092 | Prefix... 2093 +-+-+-+-+-+-+-+-+-+-+ 2095 A Seqno Request TLV prompts the receiver to send an Update for a 2096 given prefix with a given sequence number, or to forward the request 2097 further if it cannot be satisfied locally. 2099 Fields : 2101 Type Set to 10 to indicate a Seqno Request message. 2103 Length The length of the body, exclusive of the Type and Length 2104 fields. 2106 AE The encoding of the Prefix field. This MUST NOT be 0. 2108 Plen The length of the requested prefix. 2110 Seqno The sequence number that is being requested. 2112 Hop Count The maximum number of times that this TLV may be forwarded, 2113 plus 1. This MUST NOT be 0. 2115 Reserved Sent as 0 and MUST be ignored on reception. 2117 Router Id The Router-Id that is being requested. This MUST NOT 2118 consist of all zeroes or all ones. 2120 Prefix The prefix being requested. This field's size is Plen/8 2121 rounded upwards. 2123 A Seqno Request TLV prompts the receiving node to send a finite- 2124 metric Update for the prefix specified by the AE, Plen, and Prefix 2125 fields, with either a router-id different from what is specified by 2126 the Router-Id field, or a Seqno no less (modulo 2^16) than what is 2127 specified by the Seqno field. If this request cannot be satisfied 2128 locally, then it is forwarded according to the rules set out in 2129 Section 3.8.1.2. 2131 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 2132 be forwarded to a multicast address and MUST NOT be forwarded to more 2133 than one neighbour. A request MUST NOT be forwarded if its Hop Count 2134 field is 1. 2136 This TLV is self-terminating, and allows sub-TLVs. 2138 4.7. Details of specific sub-TLVs 2140 4.7.1. Pad1 2142 0 2143 0 1 2 3 4 5 6 7 2144 +-+-+-+-+-+-+-+-+ 2145 | Type = 0 | 2146 +-+-+-+-+-+-+-+-+ 2148 Fields : 2150 Type Set to 0 to indicate a Pad1 sub-TLV. 2152 This sub-TLV is silently ignored on reception. It is allowed within 2153 any TLV that allows sub-TLVs. 2155 4.7.2. PadN 2157 0 1 2 3 2158 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 2159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2160 | Type = 1 | Length | MBZ... 2161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 2163 Fields : 2165 Type Set to 1 to indicate a PadN sub-TLV. 2167 Length The length of the body, in octets, exclusive of the Type 2168 and Length fields. 2170 MBZ Set to 0 on transmission. 2172 This sub-TLV is silently ignored on reception. It is allowed within 2173 any TLV that allows sub-TLVs. 2175 5. IANA Considerations 2177 IANA has registered the UDP port number 6696, called "babel", for use 2178 by the Babel protocol. 2180 IANA has registered the IPv6 multicast group ff02::1:6 and the IPv4 2181 multicast group 224.0.0.111 for use by the Babel protocol. 2183 IANA has created a registry called "Babel TLV Types". The values in 2184 this registry are not changed by this specification. 2186 IANA has created a registry called "Babel sub-TLV Types". Due to the 2187 addition of a Mandatory bit to the Babel protocol, the values in the 2188 "Babel sub-TLV Types" registry are amended as follows: 2190 +---------+-----------------------------------------+---------------+ 2191 | Type | Name | Reference | 2192 +---------+-----------------------------------------+---------------+ 2193 | 0 | Pad1 | this document | 2194 | | | | 2195 | 1 | PadN | this document | 2196 | | | | 2197 | 112-126 | Reserved for Experimental Use | this document | 2198 | | | | 2199 | 127 | Reserved for expansion of the type | this document | 2200 | | space | | 2201 | | | | 2202 | 240-254 | Reserved for Experimental Use | this document | 2203 | | | | 2204 | 255 | Reserved for expansion of the type | this document | 2205 | | space | | 2206 +---------+-----------------------------------------+---------------+ 2208 Existing assignments in the "Babel sub-TLV Types" registry in the 2209 range 2 to 111 are not changed by this specification. The values 224 2210 through 239, previously reserved for Experimental Use, are now 2211 unassigned. 2213 IANA has created a registry called "Babel Flags Values". IANA is 2214 instructed to rename this registry to "Babel Update Flags Values", 2215 with its contents unchanged. 2217 IANA is instructed to create a new registry called "Babel Hello Flags 2218 Values". The allocation policy for this registry is Specification 2219 Required [RFC5226]. The initial values in this registry are as 2220 follows: 2222 +------+------------+---------------+ 2223 | Bit | Name | Reference | 2224 +------+------------+---------------+ 2225 | 0 | Unicast | this document | 2226 | | | | 2227 | 1-15 | Unassigned | | 2228 +------+------------+---------------+ 2230 IANA is instructed to replace all references to RFCs 6126 and 7557 in 2231 all of the registries mentioned above by references to this document. 2233 6. Security Considerations 2235 As defined in this document, Babel is a completely insecure protocol. 2236 Any attacker can misdirect data traffic by advertising routes with a 2237 low metric or a high seqno. This issue can be solved either by a 2238 lower-layer security mechanism (e.g. link-layer security), or by 2239 deploying a suitable authentication mechanism within Babel itself. 2240 With the exception of Hello TLVs used for discovery, Babel control 2241 traffic can be carried over unicast, which makes it possible to 2242 protect Babel traffic with a protocol that can only protect unicast 2243 data, for example IPsec with IKEv2, or DTLS. 2245 The information that a Babel node announces to the whole routing 2246 domain is often sufficient to determine a mobile node's physical 2247 location with reasonable precision. The privacy issues that this 2248 causes can be mitigated somewhat by using randomly chosen router-ids 2249 and randomly chosen IP addresses, and changing them periodically. 2251 When carried over IPv6, Babel packets are ignored unless they are 2252 sent from a link-local IPv6 address; since routers don't forward 2253 link-local IPv6 packets, this provides protection against spoofed 2254 Babel packets being sent from the global Internet. No such natural 2255 protection exists when Babel packets are carried over IPv4. 2257 7. Acknowledgments 2259 A number of people have contributed text and ideas to this 2260 specification. The authors are particularly indebted to Matthieu 2261 Boutier, Gwendoline Chouasne, Margaret Cullen, Donald Eastlake and 2262 Toke Hoiland-Jorgensen. The address compression technique was 2263 inspired by [PACKETBB]. 2265 8. References 2266 8.1. Normative References 2268 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2269 Requirement Levels", RFC 2119, March 1997. 2271 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 2272 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 2273 May 2008. 2275 8.2. Informative References 2277 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 2278 Sequenced Distance-Vector Routing (DSDV) for Mobile 2279 Computers", ACM SIGCOMM'94 Conference on Communications 2280 Architectures, Protocols and Applications 234-244, 1994. 2282 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 2283 Computations", IEEE/ACM Transactions on Networking 1:1, 2284 February 1993. 2286 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 2287 "EIGRP -- a Fast Routing Protocol Based on Distance 2288 Vectors", Proc. Interop 94, 1994. 2290 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 2291 high-throughput path metric for multi-hop wireless 2292 networks", Proc. MobiCom 2003, 2003. 2294 [IS-IS] "Information technology -- Telecommunications and 2295 information exchange between systems -- Intermediate 2296 System to Intermediate System intra-domain routeing 2297 information exchange protocol for use in conjunction with 2298 the protocol for providing the connectionless-mode network 2299 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 2301 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 2302 periodic routing messages", IEEE/ACM Transactions on 2303 Networking 2, 2, 122-136, April 1994. 2305 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2307 [PACKETBB] 2308 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2309 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 2310 Format", RFC 5444, February 2009. 2312 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 2314 Appendix A. Cost and Metric Computation 2316 The strategy for computing link costs and route metrics is a local 2317 matter; Babel itself only requires that it comply with the conditions 2318 given in Section 3.4.3 and Section 3.5.2. Different nodes may use 2319 different strategies in a single network and may use different 2320 strategies on different interface types. This section describes the 2321 strategies used by the sample implementation of Babel. 2323 The sample implementation of Babel sends periodic Multicast Hellos, 2324 and never sends Unicast Hellos. It maintains statistics about the 2325 last 16 received Hello TLVs of each kind (Appendix A.1), computes 2326 costs by using the 2-out-of-3 strategy (Appendix A.2.1) on wired 2327 links, and ETX (Appendix A.2.2) on wireless links. It uses an 2328 additive algebra for metric computation (Appendix A.3.1). 2330 A.1. Maintaining Hello History 2332 For each neighbour, the sample implementation of Babel maintains two 2333 sets of Hello history, one for each kind of Hello, and an expected 2334 sequence number, one for Multicast and one for Unicast Hellos. Each 2335 Hello history is a vector of 16 bits, where a 1 value represents a 2336 received Hello, and a 0 value a missed Hello. For each kind of 2337 Hello, the expected sequence number, written ne, is the sequence 2338 number that is expected to be carried by the next received Hello from 2339 this neighbour. 2341 Whenever it receives a Hello packet of a given kind from a neighbour, 2342 a node compares the received sequence number nr for that kind of 2343 Hello with its expected sequence number ne. Depending on the outcome 2344 of this comparison, one of the following actions is taken: 2346 o if the two differ by more than 16 (modulo 2^16), then the sending 2347 node has probably rebooted and lost its sequence number; the whole 2348 associated neighbour table entry is flushed and a new one is 2349 created; 2351 o otherwise, if the received nr is smaller (modulo 2^16) than the 2352 expected sequence number ne, then the sending node has increased 2353 its Hello interval without us noticing; the receiving node removes 2354 the last (ne - nr) entries from this neighbour's Hello history (we 2355 "undo history"); 2357 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 2358 node has decreased its Hello interval, and some Hellos were lost; 2359 the receiving node adds (nr - ne) 0 bits to the Hello history (we 2360 "fast-forward"). 2362 The receiving node then appends a 1 bit to the Hello history and sets 2363 ne to (nr + 1). If the Interval field of the received Hello is not 2364 zero, it resets the neighbour's hello timer to 1.5 times the 2365 advertised Interval (the extra margin allows for delay due to 2366 jitter). 2368 Whenever either Hello timer associated to a neighbour expires, the 2369 local node adds a 0 bit to this neighbour's Hello history, and 2370 increments the expected Hello number. If both Hello histories are 2371 empty (they contain 0 bits only), the neighbour entry is flushed; 2372 otherwise, the relevant hello timer is reset to the value advertised 2373 in the last Hello of that kind received from this neighbour (no extra 2374 margin is necessary in this case, since jitter was already taken into 2375 account when computing the timeout that has just expired). 2377 A.2. Cost Computation 2379 This section discusses how to compute costs based on Hello history. 2381 A.2.1. k-out-of-j 2383 K-out-of-j link sensing is suitable for wired links that are either 2384 up, in which case they only occasionally drop a packet, or down, in 2385 which case they drop all packets. 2387 The k-out-of-j strategy is parameterised by two small integers k and 2388 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 2389 1. A node keeps a history of the last j hellos; if k or more of 2390 those have been correctly received, the link is assumed to be up, and 2391 the rxcost is set to K; otherwise, the link is assumed to be down, 2392 and the rxcost is set to infinity. 2394 Since Babel supports two kinds of Hellos, a Babel node performs k- 2395 out-of-j twice for each neighbour, once on the Unicast and once on 2396 the Multicast Hello history. If either of the instances of k-out- 2397 of-j indicates that the link is up, then the link is assumed to be 2398 up, and the rxcost is set to K; if both instances indicate that the 2399 link is down, then the link is assumed to be down, and the rxcost is 2400 set to infinity. In other words, the resulting rxcost is the minimum 2401 of the rxcosts yielded by the two instances of k-out-of-j link 2402 sensing. 2404 The cost of a link performing k-out-of-j link sensing is defined as 2405 follows: 2407 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 2409 o cost = txcost otherwise. 2411 A.2.2. ETX 2413 Unlike wired links, which are bimodal (either up or down), wireless 2414 links exhibit continuous variation of the link quality. Naive 2415 application of hop-count routing in networks that use wireless links 2416 for transit tends to select long, lossy links in preference to 2417 shorter, lossless links, which can dramatically reduce throughput. 2418 For that reason, a routing protocol designed to support wireless 2419 links must perform some form of link-quality estimation. 2421 ETX [ETX] is a simple link-quality estimation algorithm that is 2422 designed to work well with the IEEE 802.11 MAC. By default, the 2423 IEEE 802.11 MAC performs ARQ and rate adaptation on unicast frames, 2424 but not on multicast frames, which are sent at a fixed rate with no 2425 ARQ; therefore, measuring the loss rate of multicast frames yields a 2426 useful estimate of a link's quality. 2428 A node performing ETX link quality estimation uses a neighbour's 2429 Multicast Hello history to compute an estimate, written beta, of the 2430 probability that a Hello TLV is successfully received. Beta can be 2431 computed as the fraction of 1 bits within a small number (say, 6) of 2432 the most recent entries in the Multicast Hello history, or it can be 2433 an exponential average, or some combination of both approaches. 2435 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2436 successfully sending a Hello TLV. The cost is then computed by 2438 cost = 256/(alpha * beta) 2440 or, equivalently, 2442 cost = (MAX(txcost, 256) * rxcost) / 256. 2444 Since the IEEE 802.11 MAC performs ARQ on unicast frames, unicast 2445 frames do not provide a useful measure of link quality, and therefore 2446 ETX ignores the Unicast Hello history. Thus, a node performing ETX 2447 link-quality estimation will not route through neighbouring nodes 2448 unless they send periodic Multicast Hellos (possibly in addition to 2449 Unicast Hellos). 2451 A.3. Metric Computation 2453 As described in Section 3.5.2, the metric advertised by a neighbour 2454 is combined with the link cost to yield a metric. 2456 A.3.1. Additive Metrics 2458 The simplest approach for obtaining a monotonic, isotonic metric is 2459 to define the metric of a route as the sum of the costs of the 2460 component links. More formally, if a neighbour advertises a route 2461 with metric m over a link with cost c, then the resulting route has 2462 metric M(c, m) = c + m. 2464 A multiplicative metric can be converted into an additive one by 2465 taking the logarithm (in some suitable base) of the link costs. 2467 A.3.2. External Sources of Willingness 2469 A node may want to vary its willingness to forward packets by taking 2470 into account information that is external to the Babel protocol, such 2471 as the monetary cost of a link, the node's battery status, CPU load, 2472 etc. This can be done by adding to every route's metric a value k 2473 that depends on the external data. For example, if a battery-powered 2474 node receives an update with metric m over a link with cost c, it 2475 might compute a metric M(c, m) = k + c + m, where k depends on the 2476 battery status. 2478 In order to preserve strict monotonicity (Section 3.5.2), the value k 2479 must be greater than -c. 2481 Appendix B. Constants 2483 The choice of time constants is a trade-off between fast detection of 2484 mobility events and protocol overhead. Two implementations of Babel 2485 with different time constants will interoperate, although the 2486 resulting convergence time will most likely be dictated by the slower 2487 of the two. 2489 Experience with the sample implementation of Babel indicates that the 2490 Hello interval is the most important time constant: a mobility event 2491 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2492 on triggered updates and explicit requests, the Update interval only 2493 has an effect on the time it takes for accurate metrics to be 2494 propagated after variations in link costs too small to trigger an 2495 unscheduled update or in the presence of packet loss. 2497 At the time of writing, the sample implementation of Babel uses the 2498 following default values: 2500 Multicast Hello Interval: 4 seconds. 2502 IHU Interval: the advertised IHU interval is always 3 times the 2503 Multicast Hello interval. IHUs are actually sent with each Hello 2504 on lossy links (as determined from the Hello history), but only 2505 with every third Multicast Hello on lossless links. 2507 Unicast Hello Interval: the sample implementation never sends 2508 scheduled Unicast Hellos; 2510 Update Interval: 4 times the Multicast Hello interval. 2512 IHU Hold Time: 3.5 times the advertised IHU interval. 2514 Route Expiry Time: 3.5 times the advertised update interval. 2516 Source GC time: 3 minutes. 2518 Request timeout: initially 2 seconds, doubled every time a request 2519 is resent, up to a maximum of three times. 2521 The amount of jitter applied to a packet depends on whether it 2522 contains any urgent TLVs or not (Section 3.1). Urgent triggered 2523 updates and urgent requests are delayed by no more than 200ms; 2524 acknowledgments, by no more than the associated deadline; and other 2525 TLVs by no more than one-half the Multicast Hello interval. 2527 Appendix C. Considerations for protocol extensions 2529 Babel is an extensible protocol, and this document defines a number 2530 of mechanisms that can be used to extend the protocol in a backwards 2531 compatible manner: 2533 o increasing the version number in the packet header; 2535 o defining new TLVs; 2537 o defining new sub-TLVs (with or without the mandatory bit set); 2539 o defining new AEs; 2541 o using the packet trailer. 2543 This appendix is intended to guide designers of protocol extensions 2544 in chosing a particular encoding. 2546 The version number in the Babel header should only be increased if 2547 the new version is not backwards compatible with the original 2548 protocol. 2550 In many cases, an extension could be implemented either by defining a 2551 new TLV, or by adding a new sub-TLV to an existing TLV. For example, 2552 an extension whose purpose is to attach additional data to route 2553 updates can be implemented either by creating a new "enriched" Update 2554 TLV, by adding a non-mandatory sub-TLV to the Update TLV, or by 2555 adding a mandatory sub-TLV. 2557 The various encodings are treated differently by implementations that 2558 do not understand the extension. In the case of a new TLV or of a 2559 sub-TLV with the mandatory bit set, the whole TLV is ignored by 2560 implementations that do not implement the extension, while in the 2561 case of a non-mandatory sub-TLV, the TLV is parsed and acted upon, 2562 and only the unknown sub-TLV is silently ignored. Therefore, a non- 2563 mandatory sub-TLV should be used by extensions that extend the Update 2564 in a compatible manner (the extension data may be silently ignored), 2565 while a mandatory sub-TLV or a new TLV must be used by extensions 2566 that make incompatible extensions to the meaning of the TLV (the 2567 whole TLV must be thrown away if the extension data is not 2568 understood). 2570 Experience shows that the need for additional data tends to crop up 2571 in the most unexpected places. Hence, it is recommended that 2572 extensions that define new TLVs should make them self-terminating, 2573 and allow attaching sub-TLVs to them. 2575 Adding a new AE is essentially equivalent to adding a new TLV: Update 2576 TLVs with an unknown AE are ignored, just like unknown TLVs. 2577 However, adding a new AE is more involved than adding a new TLV, 2578 since it creates a new set of compression state. Additionally, since 2579 the Next Hop TLV creates state specific to a given address family, as 2580 opposed to a given AE, a new AE for a previously defined address 2581 family must not be used in the Next Hop TLV if backwards 2582 compatibility is required. A similar issue arises with Update TLVs 2583 with unknown AEs establishing a new router-id (due to the Router-Id 2584 flag being set). Therefore, defining new AEs must be done with care 2585 if compatibility with unextended implementations is required. 2587 The packet trailer (the space after the declared length of the packet 2588 but within the payload of the UDP datagram) was originally intended 2589 to carry a cryptographic signature. However, no extension has used 2590 it to date, and therefore we refrain from making any recommendations 2591 about its use due to the lack of implementation experience. 2593 Appendix D. Stub Implementations 2595 Babel is a fairly economic protocol. Updates take between 12 and 40 2596 octets per destination, depending on the address family and how 2597 successful compression is; in a double-stack flat network, an average 2598 of less than 24 octets per update is typical. The route table 2599 occupies about 35 octets per IPv6 entry. To put these values into 2600 perspective, a single full-size Ethernet frame can carry some 65 2601 route updates, and a megabyte of memory can contain a 20000-entry 2602 route table and the associated source table. 2604 Babel is also a reasonably simple protocol. The sample 2605 implementation consists of less than 12 000 lines of C code, and it 2606 compiles to less than 120 kB of text on a 32-bit CISC architecture; 2607 about half of this figure is due to protocol extensions and user- 2608 interface code. 2610 Nonetheless, in some very constrained environments, such as PDAs, 2611 microwave ovens, or abacuses, it may be desirable to have subset 2612 implementations of the protocol. 2614 There are many different definitions of a stub router, but for the 2615 needs of this section a stub implementation of Babel is one that 2616 announces one or more directly attached prefixes into a Babel network 2617 but doesn't reannounce any routes that it has learnt from its 2618 neighbours. It may either maintain a full routing table, or simply 2619 select a default gateway amongst any one of its neighbours that 2620 announces a default route. Since a stub implementation never 2621 forwards packets except from or to directly attached links, it cannot 2622 possibly participate in a routing loop, and hence it need not 2623 evaluate the feasibility condition or maintain a source table. 2625 No matter how primitive, a stub implementation MUST parse sub-TLVs 2626 attached to any TLVs that it understands and check the mandatory bit. 2627 It MUST answer acknowledgment requests and MUST participate in the 2628 Hello/IHU protocol. It MUST also be able to reply to seqno requests 2629 for routes that it announces and SHOULD be able to reply to route 2630 requests. 2632 Experience shows that an IPv6-only stub implementation of Babel can 2633 be written in less than 1000 lines of C code and compile to 13 kB of 2634 text on 32-bit CISC architecture. 2636 Appendix E. Software Availability 2638 The sample implementation of Babel is available from 2639 . 2641 Appendix F. Changes from previous versions 2643 F.1. Changes since RFC 6126 2645 o Changed UDP port number to 6696. 2647 o Consistently use router-id rather than id. 2649 o Clarified that the source garbage collection timer is reset after 2650 sending an update even if the entry was not modified. 2652 o In section "Seqno Requests", fixed an erroneous "route request". 2654 o In the description of the Seqno Request TLV, added the description 2655 of the Router-Id field. 2657 o Made router-ids all-0 and all-1 forbidden. 2659 F.2. Changes since draft-ietf-babel-rfc6126bis-00 2661 o Added security considerations. 2663 F.3. Changes since draft-ietf-babel-rfc6126bis-01 2665 o Integrated the format of sub-TLVs. 2667 o Mentioned for each TLV whether it supports sub-TLVs. 2669 o Added Appendix C. 2671 o Added a mandatory bit in sub-TLVs. 2673 o Changed compression state to be per-AF rather than per-AE. 2675 o Added implementation hint for the routing table. 2677 o Clarified how router-ids are computed when bit 0x40 is set in 2678 Updates. 2680 o Relaxed the conditions for sending requests, and tightened the 2681 conditions for forwarding requests. 2683 o Clarified that neighbours should be acquired at some point, but it 2684 doesn't matter when. 2686 F.4. Changes since draft-ietf-babel-rfc6126bis-02 2688 o Added Unicast Hellos. 2690 o Added unscheduled (interval-less) Hellos. 2692 o Changed Appendix A to consider Unicast and unscheduled Hellos. 2694 o Changed Appendix B to agree with the reference implementation. 2696 o Added optional algorithm to avoid the hold time. 2698 o Changed the table of pending seqno requests to be indexed by 2699 router-id in addition to prefixes. 2701 o Relaxed the route acquisition algorithm. 2703 o Replaced minimal implementations by stub implementations. 2705 o Added acknowledgments section. 2707 F.5. Changes since draft-ietf-babel-rfc6126bis-03 2709 o Clarified that all the data structures are conceptual. 2711 o Made sending and receiving Multicast Hellos a SHOULD, avoids 2712 expressing any opinion about Unicast Hellos. 2714 o Removed opinion about Multicast vs. Unicast Hellos (Appendix A.4). 2716 o Made hold-time into a SHOULD rather than MUST. 2718 o Clarified that Seqno Requests are for a finite-metric Update. 2720 o Clarified that sub-TLVs Pad1 and PadN are allowed within any TLV 2721 that allows sub-TLVs. 2723 o Updated IANA Considerations. 2725 o Updated Security Considerations. 2727 o Renamed routing table back to route table. 2729 o Made buffering outgoing updates a SHOULD. 2731 o Weakened advice to use modified EUI-64 in router-ids. 2733 o Added information about sending requests to Appendix B. 2735 o A number of minor wording changes and clarifications. 2737 Authors' Addresses 2739 Juliusz Chroboczek 2740 IRIF, University of Paris-Diderot 2741 Case 7014 2742 75205 Paris Cedex 13 2743 France 2745 Email: jch@irif.fr 2746 David Schinazi 2747 Apple Inc. 2748 1 Infinite Loop 2749 Cupertino, California 95014 2750 US 2752 Email: dschinazi@apple.com