idnits 2.17.1 draft-ietf-babel-rfc6126bis-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 1 instance of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 31, 2017) is 2635 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Chroboczek 3 Internet-Draft IRIF, University of Paris-Diderot 4 Intended status: Standards Track January 31, 2017 5 Expires: August 4, 2017 7 The Babel Routing Protocol 8 draft-ietf-babel-rfc6126bis-01 10 Abstract 12 Babel is a loop-avoiding distance-vector routing protocol that is 13 robust and efficient both in ordinary wired networks and in wireless 14 mesh networks. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on August 4, 2017. 33 Copyright Notice 35 Copyright (c) 2017 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 51 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 53 1.3. Specification of Requirements . . . . . . . . . . . . . . 4 54 2. Conceptual Description of the Protocol . . . . . . . . . . . 4 55 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 56 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 5 57 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 58 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 6 59 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 60 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 9 61 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10 62 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11 63 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 11 64 3.1. Message Transmission and Reception . . . . . . . . . . . 11 65 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12 66 3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . 15 67 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 15 68 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 17 69 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 21 70 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 22 71 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 24 72 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 27 73 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 28 74 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 29 75 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 29 76 4.4. Details of Specific TLVs . . . . . . . . . . . . . . . . 30 77 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 39 78 6. Security Considerations . . . . . . . . . . . . . . . . . . . 39 79 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 40 80 7.1. Normative References . . . . . . . . . . . . . . . . . . 40 81 7.2. Informative References . . . . . . . . . . . . . . . . . 40 82 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 41 83 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 41 84 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 42 85 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 43 86 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 43 87 Appendix C. Simplified Implementations . . . . . . . . . . . . . 44 88 Appendix D. Software Availability . . . . . . . . . . . . . . . 45 89 Appendix E. Changes from previous versions . . . . . . . . . . . 45 90 E.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 45 91 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 45 93 1. Introduction 95 Babel is a loop-avoiding distance-vector routing protocol that is 96 designed to be robust and efficient both in networks using prefix- 97 based routing and in networks using flat routing ("mesh networks"), 98 and both in relatively stable wired networks and in highly dynamic 99 wireless networks. 101 1.1. Features 103 The main property that makes Babel suitable for unstable networks is 104 that, unlike naive distance-vector routing protocols [RIP], it 105 strongly limits the frequency and duration of routing pathologies 106 such as routing loops and black-holes during reconvergence. Even 107 after a mobility event is detected, a Babel network usually remains 108 loop-free. Babel then quickly reconverges to a configuration that 109 preserves the loop-freedom and connectedness of the network, but is 110 not necessarily optimal; in many cases, this operation requires no 111 packet exchanges at all. Babel then slowly converges, in a time on 112 the scale of minutes, to an optimal configuration. This is achieved 113 by using sequenced routes, a technique pioneered by Destination- 114 Sequenced Distance-Vector routing [DSDV]. 116 More precisely, Babel has the following properties: 118 o when every prefix is originated by at most one router, Babel never 119 suffers from routing loops; 121 o when a prefix is originated by multiple routers, Babel may 122 occasionally create a transient routing loop for this particular 123 prefix; this loop disappears in a time proportional to its 124 diameter, and never again (up to an arbitrary garbage-collection 125 (GC) time) will the routers involved participate in a routing loop 126 for the same prefix; 128 o assuming reasonable packet loss rates, any routing black-holes 129 that may appear after a mobility event are corrected in a time at 130 most proportional to the network's diameter. 132 Babel has provisions for link quality estimation and for fairly 133 arbitrary metrics. When configured suitably, Babel can implement 134 shortest-path routing, or it may use a metric based, for example, on 135 measured packet loss. 137 Babel nodes will successfully establish an association even when they 138 are configured with different parameters. For example, a mobile node 139 that is low on battery may choose to use larger time constants (hello 140 and update intervals, etc.) than a node that has access to wall 141 power. Conversely, a node that detects high levels of mobility may 142 choose to use smaller time constants. The ability to build such 143 heterogeneous networks makes Babel particularly adapted to the 144 wireless environment. 146 Finally, Babel is a hybrid routing protocol, in the sense that it can 147 carry routes for multiple network-layer protocols (IPv4 and IPv6), 148 whichever protocol the Babel packets are themselves being carried 149 over. 151 1.2. Limitations 153 Babel has two limitations that make it unsuitable for use in some 154 environments. First, Babel relies on periodic routing table updates 155 rather than using a reliable transport; hence, in large, stable 156 networks it generates more traffic than protocols that only send 157 updates when the network topology changes. In such networks, 158 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 159 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 160 suitable. 162 Second, Babel does impose a hold time when a prefix is retracted 163 (Section 3.5.5). While this hold time does not apply to the exact 164 prefix being retracted, and hence does not prevent fast reconvergence 165 should it become available again, it does apply to any shorter prefix 166 that covers it. Hence, if a previously deaggregated prefix becomes 167 aggregated, it will be unreachable for a few minutes. This makes 168 Babel unsuitable for use in mobile networks that implement automatic 169 prefix aggregation. 171 1.3. Specification of Requirements 173 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 174 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 175 document are to be interpreted as described in [RFC2119]. 177 2. Conceptual Description of the Protocol 179 Babel is a mostly loop-free distance vector protocol: it is based on 180 the Bellman-Ford protocol, just like the venerable RIP [RIP], but 181 includes a number of refinements that either prevent loop formation 182 altogether, or ensure that a loop disappears in a timely manner and 183 doesn't form again. 185 Conceptually, Bellman-Ford is executed in parallel for every source 186 of routing information (destination of data traffic). In the 187 following discussion, we fix a source S; the reader will recall that 188 the same algorithm is executed for all sources. 190 2.1. Costs, Metrics and Neighbourship 192 As many routing algorithms, Babel computes costs of links between any 193 two neighbouring nodes, abstract values attached to the edges between 194 two nodes. We write C(A, B) for the cost of the edge from node A to 195 node B. 197 Given a route between any two nodes, the metric of the route is the 198 sum of the costs of all the edges along the route. The goal of the 199 routing algorithm is to compute, for every source S, the tree of the 200 routes of lowest metric to S. 202 Costs and metrics need not be integers. In general, they can be 203 values in any algebra that satisfies two fairly general conditions 204 (Section 3.5.2). 206 A Babel node periodically broadcasts Hello messages to all of its 207 neighbours; it also periodically sends an IHU ("I Heard You") message 208 to every neighbour from which it has recently heard a Hello. From 209 the information derived from Hello and IHU messages received from its 210 neighbour B, a node A computes the cost C(A, B) of the link from A to 211 B. 213 2.2. The Bellman-Ford Algorithm 215 Every node A maintains two pieces of data: its estimated distance to 216 S, written D(A), and its next-hop router to S, written NH(A). 217 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 219 Periodically, every node B sends to all of its neighbours a route 220 update, a message containing D(B). When a neighbour A of B receives 221 the route update, it checks whether B is its selected next hop; if 222 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 223 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 224 its current value of D(A). If that value is smaller, meaning that 225 the received update advertises a route that is better than the 226 currently selected route, then NH(A) is set to B, and D(A) is set to 227 C(A, B) + D(B). 229 A number of refinements to this algorithm are possible, and are used 230 by Babel. In particular, convergence speed may be increased by 231 sending unscheduled "triggered updates" whenever a major change in 232 the topology is detected, in addition to the regular, scheduled 233 updates. Additionally, a node may maintain a number of alternate 234 routes, which are being advertised by neighbours other than its 235 selected neighbour, and which can be used immediately if the selected 236 route were to fail. 238 2.3. Transient Loops in Bellman-Ford 240 It is well known that a naive application of Bellman-Ford to 241 distributed routing can cause transient loops after a topology 242 change. Consider for example the following diagram: 244 B 245 1 /| 246 1 / | 247 S --- A |1 248 \ | 249 1 \| 250 C 252 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 254 Suppose now that the link between S and A fails: 256 B 257 1 /| 258 / | 259 S A |1 260 \ | 261 1 \| 262 C 264 When it detects the failure of the link, A switches its next hop to B 265 (which is still advertising a route to S with metric 2), and 266 advertises a metric equal to 3, and then advertises a new route with 267 metric 3. This process of nodes changing selected neighbours and 268 increasing their metric continues until the advertised metric reaches 269 "infinity", a value larger than all the metrics that the routing 270 protocol is able to carry. 272 2.4. Feasibility Conditions 274 Bellman-Ford is a very robust algorithm: its convergence properties 275 are preserved when routers delay route acquisition or when they 276 discard some updates. Babel routers discard received route 277 announcements unless they can prove that accepting them cannot 278 possibly cause a routing loop. 280 More formally, we define a condition over route announcements, known 281 as the feasibility condition, that guarantees the absence of routing 282 loops whenever all routers ignore route updates that do not satisfy 283 the feasibility condition. In effect, this makes Bellman-Ford into a 284 family of routing algorithms, parameterised by the feasibility 285 condition. 287 Many different feasibility conditions are possible. For example, BGP 288 can be modelled as being a distance-vector protocol with a (rather 289 drastic) feasibility condition: a routing update is only accepted 290 when the receiving node's AS number is not included in the update's 291 AS-Path attribute (note that BGP's feasibility condition does not 292 ensure the absence of transitory "micro-loops" during reconvergence). 294 Another simple feasibility condition, used in Destination-Sequenced 295 Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand 296 Distance Vector (AODV) routing, stems from the following observation: 297 a routing loop can only arise after a router has switched to a route 298 with a larger metric than the route that it had previously selected. 299 Hence, one could decide that a route is feasible only when its metric 300 at the local node would be no larger than the metric of the currently 301 selected route, i.e., an announcement carrying a metric D(B) is 302 accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this 303 constraint, then the metric at every router is nonincreasing, and the 304 following invariant is always preserved: if A has selected B as its 305 successor, then D(B) < D(A), which implies that the forwarding graph 306 is loop-free. 308 Babel uses a slightly more refined feasibility condition, used in 309 EIGRP [DUAL]. Given a router A, define the feasibility distance of 310 A, written FD(A), as the smallest metric that A has ever advertised 311 for S to any of its neighbours. An update sent by a neighbour B of A 312 is feasible when the metric D(B) advertised by B is strictly smaller 313 than A's feasibility distance, i.e., when D(B) < FD(A). 315 It is easy to see that this latter condition is no more restrictive 316 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 317 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 318 Suppose now that A receives a DSDV-feasible update that advertises a 319 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 320 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 322 To see that it is strictly less restrictive, consider the following 323 diagram, where A has selected the route through B, and D(A) = FD(A) = 324 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 325 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 326 the currently selected route: 328 B 329 1 / \ 1 330 / \ 331 S A 332 \ / 333 1 \ / 4 334 C 336 To show that this feasibility condition still guarantees loop- 337 freedom, recall that at the time when A accepts an update from B, the 338 metric D(B) announced by B is no smaller than FD(B); since it is 339 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 340 property is preserved when A sends updates, it remains true at all 341 times, which ensures that the forwarding graph has no loops. 343 2.5. Solving Starvation: Sequencing Routes 345 Obviously, the feasibility conditions defined above cause starvation 346 when a router runs out of feasible routes. Consider the following 347 diagram, where both A and B have selected the direct route to S: 349 A 350 1 /| D(A) = 1 351 / | FD(A) = 1 352 S |1 353 \ | D(B) = 2 354 2 \| FD(B) = 2 355 B 357 Suppose now that the link between A and S breaks: 359 A 360 | 361 | FD(A) = 1 362 S |1 363 \ | D(B) = 2 364 2 \| FD(B) = 2 365 B 367 The only route available from A to S, the one that goes through B, is 368 not feasible: A suffers from a spurious starvation. 370 At this point, the whole network must be rebooted in order to solve 371 the starvation; this is essentially what EIGRP does when it performs 372 a global synchronisation of all the routers in the network with the 373 source (the "active" phase of EIGRP). 375 Babel reacts to starvation in a less drastic manner, by using 376 sequenced routes, a technique introduced by DSDV and adopted by AODV. 377 In addition to a metric, every route carries a sequence number, a 378 nondecreasing integer that is propagated unchanged through the 379 network and is only ever incremented by the source; a pair (s, m), 380 where s is a sequence number and m a metric, is called a distance. 382 A received update is feasible when either it is more recent than the 383 feasibility distance maintained by the receiving node, or it is 384 equally recent and the metric is strictly smaller. More formally, if 385 FD(A) = (s, m), then an update carrying the distance (s', m') is 386 feasible when either s' > s, or s = s' and m' < m. 388 Assuming the sequence number of S is 137, the diagram above becomes: 390 A 391 | 392 | FD(A) = (137, 1) 393 S |1 394 \ | D(B) = (137, 2) 395 2 \| FD(B) = (137, 2) 396 B 398 After S increases its sequence number, and the new sequence number is 399 propagated to B, we have: 401 A 402 | 403 | FD(A) = (137, 1) 404 S |1 405 \ | D(B) = (138, 2) 406 2 \| FD(B) = (138, 2) 407 B 409 at which point the route through B becomes feasible again. 411 Note that while sequence numbers are used for determining 412 feasibility, they are not necessarily used in route selection: a node 413 will normally ignore the sequence number when selecting a route 414 (Section 3.6). 416 2.6. Requests 418 In DSDV, the sequence number of a source is increased periodically. 419 A route becomes feasible again after the source increases its 420 sequence number, and the new sequence number is propagated through 421 the network, which may, in general, require a significant amount of 422 time. 424 Babel takes a different approach. When a node detects that it is 425 suffering from a potentially spurious starvation, it sends an 426 explicit request to the source for a new sequence number. This 427 request is forwarded hop by hop to the source, with no regard to the 428 feasibility condition. Upon receiving the request, the source 429 increases its sequence number and broadcasts an update, which is 430 forwarded to the requesting node. 432 Note that after a change in network topology not all such requests 433 will, in general, reach the source, as some will be sent over links 434 that are now broken. However, if the network is still connected, 435 then at least one among the nodes suffering from spurious starvation 436 has an (unfeasible) route to the source; hence, in the absence of 437 packet loss, at least one such request will reach the source. 438 (Resending requests a small number of times compensates for packet 439 loss.) 441 Since requests are forwarded with no regard to the feasibility 442 condition, they may, in general, be caught in a forwarding loop; this 443 is avoided by having nodes perform duplicate detection for the 444 requests that they forward. 446 2.7. Multiple Routers 448 The above discussion assumes that every prefix is originated by a 449 single router. In real networks, however, it is often necessary to 450 have a single prefix originated by multiple routers; for example, the 451 default route will be originated by all of the edge routers of a 452 routing domain. 454 Since synchronising sequence numbers between distinct routers is 455 problematic, Babel treats routes for the same prefix as distinct 456 entities when they are originated by different routers: every route 457 announcement carries the router-id of its originating router, and 458 feasibility distances are not maintained per prefix, but per source, 459 where a source is a pair of a router-id and a prefix. In effect, 460 Babel guarantees loop-freedom for the forwarding graph to every 461 source; since the union of multiple acyclic graphs is not in general 462 acyclic, Babel does not in general guarantee loop-freedom when a 463 prefix is originated by multiple routers, but any loops will be 464 broken in a time at most proportional to the diameter of the loop -- 465 as soon as an update has "gone around" the routing loop. 467 Consider for example the following diagram, where A has selected the 468 default route through S, and B has selected the one through S': 470 1 1 1 471 ::/0 -- S --- A --- B --- S' -- ::/0 473 Suppose that both default routes fail at the same time; then nothing 474 prevents A from switching to B, and B simultaneously switching to A. 475 However, as soon as A has successfully advertised the new route to B, 476 the route through A will become unfeasible for B. Conversely, as 477 soon as B will have advertised the route through A, the route through 478 B will become unfeasible for A. 480 In effect, the routing loop disappears at the latest when routing 481 information has gone around the loop. Since this process can be 482 delayed by lost packets, Babel makes certain efforts to ensure that 483 updates are sent reliably after a router-id change. 485 Additionally, after the routers have advertised the two routes, both 486 sources will be in their source tables, which will prevent them from 487 ever again participating in a routing loop involving routes from S 488 and S' (up to the source GC time, which, available memory permitting, 489 can be set to arbitrarily large values). 491 2.8. Overlapping Prefixes 493 In the above discussion, we have assumed that all prefixes are 494 disjoint, as is the case in flat ("mesh") routing. In practice, 495 however, prefixes may overlap: for example, the default route 496 overlaps with all of the routes present in the network. 498 After a route fails, it is not correct in general to switch to a 499 route that subsumes the failed route. Consider for example the 500 following configuration: 502 1 1 503 ::/0 -- A --- B --- C 505 Suppose that node C fails. If B forwards packets destined to C by 506 following the default route, a routing loop will form, and persist 507 until A learns of B's retraction of the direct route to C. Babel 508 avoids this pitfall by maintaining an "unreachable" route for a few 509 minutes after a route is retracted; the time for which such a route 510 must be maintained should be the worst-case propagation time of the 511 retraction of the route to C. 513 3. Protocol Operation 515 Every Babel speaker is assigned a router-id, which is an arbitrary 516 string of 8 octets that is assumed unique across the routing domain. 517 We suggest that router-ids should be assigned in modified EUI-64 518 format [ADDRARCH]. (As a matter of fact, the protocol encoding is 519 slightly more compact when router-ids are assigned in the same manner 520 as the IPv6 layer assigns host IDs.) 522 3.1. Message Transmission and Reception 524 Babel protocol packets are sent in the body of a UDP datagram. Each 525 Babel packet consists of one or more TLVs. 527 The source address of a Babel packet is always a unicast address, 528 link-local in the case of IPv6. Babel packets may be sent to a well- 529 known (link-local) multicast address (this is the usual case) or to a 530 (link-local) unicast address. In normal operation, a Babel speaker 531 sends both multicast and unicast packets to its neighbours. 533 With the exception of Hello TLVs and acknowledgements, all Babel TLVs 534 can be sent to either unicast or multicast addresses, and their 535 semantics does not depend on whether the destination was a unicast or 536 multicast address. Hence, a Babel speaker does not need to determine 537 the destination address of a packet that it receives in order to 538 interpret it. 540 A moderate amount of jitter is applied to packets sent by a Babel 541 speaker: outgoing TLVs are buffered and SHOULD be sent with a small 542 random delay. This is done for two purposes: it avoids 543 synchronisation of multiple Babel speakers across a network [JITTER], 544 and it allows for the aggregation of multiple TLVs into a single 545 packet. 547 The exact delay and amount of jitter applied to a packet depends on 548 whether it contains any urgent TLVs. Acknowledgement TLVs MUST be 549 sent before the deadline specified in the corresponding request. The 550 particular class of updates specified in Section 3.7.2 MUST be sent 551 in a timely manner. The particular class of request and update TLVs 552 specified in Section 3.8.2 SHOULD be sent in a timely manner. 554 3.2. Data Structures 556 Every Babel speaker maintains a number of data structures. 558 3.2.1. Sequence Number 560 A node's sequence number is a 16-bit integer that is included in 561 route updates sent for routes originated by this node. A node 562 increments its sequence number (modulo 2^16) whenever it receives a 563 request for a new sequence number (Section 3.8.1.2). 565 A node SHOULD NOT increment its sequence number (seqno) 566 spontaneously, since increasing seqnos makes it less likely that 567 other nodes will have feasible alternate routes when their selected 568 routes fail. 570 3.2.2. The Interface Table 572 The interface table contains the list of interfaces on which the node 573 speaks the Babel protocol. Every interface table entry contains the 574 interface's Hello seqno, a 16-bit integer that is sent with each 575 Hello TLV on this interface and is incremented (modulo 2^16) whenever 576 a Hello is sent. (Note that an interface's Hello seqno is unrelated 577 to the node's seqno.) 579 There are two timers associated with each interface table entry -- 580 the Hello timer, which governs the sending of periodic Hello and IHU 581 packets, and the update timer, which governs the sending of periodic 582 route updates. 584 3.2.3. The Neighbour Table 586 The neighbour table contains the list of all neighbouring interfaces 587 from which a Babel packet has been recently received. The neighbour 588 table is indexed by pairs of the form (interface, address), and every 589 neighbour table entry contains the following data: 591 o the local node's interface over which this neighbour is reachable; 593 o the address of the neighbouring interface; 595 o a history of recently received Hello packets from this neighbour; 596 this can, for example, be a sequence of n bits, for some small 597 value n, indicating which of the n hellos most recently sent by 598 this neighbour have been received by the local node; 600 o the "transmission cost" value from the last IHU packet received 601 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 602 hold timer for this neighbour has expired; 604 o the neighbour's expected Hello sequence number, an integer modulo 605 2^16. 607 There are two timers associated with each neighbour entry -- the 608 hello timer, which is initialised from the interval value carried by 609 Hello TLVs, and the IHU timer, which is initialised to a small 610 multiple of the interval carried in IHU TLVs. 612 Note that the neighbour table is indexed by IP addresses, not by 613 router-ids: neighbourship is a relationship between interfaces, not 614 between nodes. Therefore, two nodes with multiple interfaces can 615 participate in multiple neighbourship relationships, a fairly common 616 situation when wireless nodes with multiple radios are involved. 618 3.2.4. The Source Table 620 The source table is used to record feasibility distances. It is 621 indexed by triples of the form (prefix, plen, router-id), and every 622 source table entry contains the following data: 624 o the prefix (prefix, plen), where plen is the prefix length, that 625 this entry applies to; 627 o the router-id of a router originating this prefix; 629 o a pair (seqno, metric), this source's feasibility distance. 631 There is one timer associated with each entry in the source table -- 632 the source garbage-collection timer. It is initialised to a time on 633 the order of minutes and reset as specified in Section 3.7.3. 635 3.2.5. The Route Table 637 The route table contains the routes known to this node. It is 638 indexed by triples of the form (prefix, plen, neighbour), and every 639 route table entry contains the following data: 641 o the source (prefix, plen, router-id) for which this route is 642 advertised; 644 o the neighbour that advertised this route; 646 o the metric with which this route was advertised by the neighbour, 647 or FFFF hexadecimal (infinity) for a recently retracted route; 649 o the sequence number with which this route was advertised; 651 o the next-hop address of this route; 653 o a boolean flag indicating whether this route is selected, i.e., 654 whether it is currently being used for forwarding and is being 655 advertised. 657 There is one timer associated with each route table entry -- the 658 route expiry timer. It is initialised and reset as specified in 659 Section 3.5.4. 661 3.2.6. The Table of Pending Requests 663 The table of pending requests contains a list of seqno requests that 664 the local node has sent (either because they have been originated 665 locally, or because they were forwarded) and to which no reply has 666 been received yet. This table is indexed by prefixes, and every 667 entry in this table contains the following data: 669 o the prefix, router-id, and seqno being requested; 670 o the neighbour, if any, on behalf of which we are forwarding this 671 request; 673 o a small integer indicating the number of times that this request 674 will be resent if it remains unsatisfied. 676 There is one timer associated with each pending request; it governs 677 both the resending of requests and their expiry. 679 3.3. Acknowledged Packets 681 A Babel speaker may request that any neighbour receiving a given 682 packet reply with an explicit acknowledgement within a given time. 683 While the use of acknowledgement requests is optional, every Babel 684 speaker MUST be able to reply to such a request. 686 An acknowledgement MUST be sent to a unicast destination. On the 687 other hand, acknowledgement requests may be sent to either unicast or 688 multicast destinations, in which case they request an acknowledgement 689 from all of the receiving nodes. 691 When to request acknowledgements is a matter of local policy; the 692 simplest strategy is to never request acknowledgements and to rely on 693 periodic updates to ensure that any reachable routes are eventually 694 propagated throughout the routing domain. For increased efficiency, 695 we suggest that acknowledged packets should be used in order to send 696 urgent updates (Section 3.7.2) when the number of neighbours on a 697 given interface is small. Since Babel is designed to deal gracefully 698 with packet loss on unreliable media, sending all packets with 699 acknowledgement requests is not necessary, and not even recommended, 700 as the acknowledgements cause additional traffic and may force 701 additional Address Resolution Protocol (ARP) or Neighbour Discovery 702 exchanges. 704 3.4. Neighbour Acquisition 706 Neighbour acquisition is the process by which a Babel node discovers 707 the set of neighbours heard over each of its interfaces and 708 ascertains bidirectional reachability. On unreliable media, 709 neighbour acquisition additionally provides some statistics that MAY 710 be used in link quality computation. 712 3.4.1. Reverse Reachability Detection 714 Every Babel node sends periodic Hellos over each of its interfaces. 715 Each Hello TLV carries an increasing (modulo 2^16) sequence number 716 and the interval between successive periodic packets sent on this 717 particular interface. 719 In addition to the periodic Hello packets, a node MAY send 720 unscheduled Hello packets, e.g., to accelerate link cost estimation 721 when a new neighbour is discovered, or when link conditions have 722 suddenly changed. 724 A node MAY change its Hello interval. The Hello interval MAY be 725 decreased at any time; it SHOULD NOT be increased, except immediately 726 before sending a Hello packet. (Equivalently, a node SHOULD send an 727 unscheduled Hello immediately after increasing its Hello interval.) 729 How to deal with received Hello TLVs and what statistics to maintain 730 are considered local implementation matters; typically, a node will 731 maintain some sort of history of recently received Hellos. A 732 possible algorithm is described in Appendix A.1. 734 After receiving a Hello, or determining that it has missed one, the 735 node recomputes the association's cost (Section 3.4.3) and runs the 736 route selection procedure (Section 3.6). 738 3.4.2. Bidirectional Reachability Detection 740 In order to establish bidirectional reachability, every node sends 741 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 742 IHUs carry an explicit interval value, they MAY be sent less often 743 than Hellos in order to reduce the amount of routing traffic in dense 744 networks; in particular, they SHOULD be sent less often than Hellos 745 over links with little packet loss. While IHUs are conceptually 746 unicast, they SHOULD be sent to a multicast address in order to avoid 747 an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 748 in a single packet. 750 In addition to the periodic IHUs, a node MAY, at any time, send an 751 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 752 interval, and it MAY increase its IHU interval immediately before 753 sending an IHU. 755 Every IHU TLV contains two pieces of data: the link's rxcost 756 (reception cost) from the sender's perspective, used by the neighbour 757 for computing link costs (Section 3.4.3), and the interval between 758 periodic IHU packets. A node receiving an IHU updates the value of 759 the sending neighbour's txcost (transmission cost), from its 760 perspective, to the value contained in the IHU, and resets this 761 neighbour's IHU timer to a small multiple of the value received in 762 the IHU. 764 When a neighbour's IHU timer expires, its txcost is set to infinity. 766 After updating a neighbour's txcost, the receiving node recomputes 767 the neighbour's cost (Section 3.4.3) and runs the route selection 768 procedure (Section 3.6). 770 3.4.3. Cost Computation 772 A neighbourship association's link cost is computed from the values 773 maintained in the neighbour table -- namely, the statistics kept in 774 the neighbour table about the reception of Hellos, and the txcost 775 computed from received IHU packets. 777 For every neighbour, a Babel node computes a value known as this 778 neighbour's rxcost. This value is usually derived from the Hello 779 history, which may be combined with other data, such as statistics 780 maintained by the link layer. The rxcost is sent to a neighbour in 781 each IHU. 783 How the txcost and rxcost are combined in order to compute a link's 784 cost is a matter of local policy; as far as Babel's correctness is 785 concerned, only the following conditions MUST be satisfied: 787 o the cost is strictly positive; 789 o if no hellos were received recently, then the cost is infinite; 791 o if the txcost is infinite, then the cost is infinite. 793 Note that while this document does not constrain cost computation any 794 further, not all cost computation strategies will give good results. 795 We give a few examples of strategies for computing a link's cost that 796 are known to work well in practice in Appendix A.2. 798 3.5. Routing Table Maintenance 800 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 801 seqno, metric), where (prefix, plen) is the prefix for which a route 802 is being advertised, router-id is the router-id of the router 803 originating this update, seqno is a nondecreasing (modulo 2^16) 804 integer that carries the originating router seqno, and metric is the 805 announced metric. 807 Before being accepted, an update is checked against the feasibility 808 condition (Section 3.5.1), which ensures that the route does not 809 create a routing loop. If the feasibility condition is not 810 satisfied, the update is either ignored or treated as a retraction, 811 depending on some other conditions (Section 3.5.4). If the 812 feasibility condition is satisfied, then the update cannot possibly 813 cause a routing loop, and the update is accepted. 815 3.5.1. The Feasibility Condition 817 The feasibility condition is applied to all received updates. The 818 feasibility condition compares the metric in the received update with 819 the metrics of the updates previously sent by the receiving node; 820 updates with finite metrics large enough to cause a loop are 821 discarded. 823 A feasibility distance is a pair (seqno, metric), where seqno is an 824 integer modulo 2^16 and metric is a positive integer. Feasibility 825 distances are compared lexicographically, with the first component 826 inverted: we say that a distance (seqno, metric) is strictly better 827 than a distance (seqno', metric'), written 829 (seqno, metric) < (seqno', metric') 831 when 833 seqno > seqno' or (seqno = seqno' and metric < metric') 835 where sequence numbers are compared modulo 2^16. 837 Given a source (p, plen, router-id), a node's feasibility distance 838 for this source is the minimum, according to the ordering defined 839 above, of the distances of all the finite updates ever sent by this 840 particular node for the prefix (p, plen) and the given router-id. 841 Feasibility distances are maintained in the source table; the exact 842 procedure is given in Section 3.7.3. 844 A received update is feasible when either it is a retraction (its 845 metric is FFFF hexadecimal), or the advertised distance is strictly 846 better, in the sense defined above, than the feasibility distance for 847 the corresponding source. More precisely, a route advertisement 848 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 849 feasible if one of the following conditions holds: 851 o metric is infinite; or 853 o no entry exists in the source table indexed by (router-id, prefix, 854 plen); or 856 o an entry (prefix, plen, router-id, seqno', metric') exists in the 857 source table, and either 859 * seqno' < seqno or 861 * seqno = seqno' and metric < metric'. 863 Note that the feasibility condition considers the metric advertised 864 by the neighbour, not the route's metric; hence, a fluctuation in a 865 neighbour's cost cannot render a selected route unfeasible. 867 3.5.2. Metric Computation 869 A route's metric is computed from the metric advertised by the 870 neighbour and the neighbour's link cost. Just like cost computation, 871 metric computation is considered a local policy matter; as far as 872 Babel is concerned, the function M(c, m) used for computing a metric 873 from a locally computed link cost and the metric advertised by a 874 neighbour MUST only satisfy the following conditions: 876 o if c is infinite, then M(c, m) is infinite; 878 o M is strictly monotonic: M(c, m) > m. 880 Additionally, the metric SHOULD satisfy the following condition: 882 o M is isotonic: if m <= m', then M(c, m) <= M(c, m'). 884 Note that while strict monotonicity is essential to the integrity of 885 the network (persistent routing loops may appear if it is not 886 satisfied), isotonicity is not: if it is not satisfied, Babel will 887 still converge to a locally optimal routing table, but might not 888 reach a global optimum (in fact, such a global optimum may not even 889 exist). 891 As with cost computation, not all strategies for computing route 892 metrics will give good results. In particular, some metrics are more 893 likely than others to lead to routing instabilities (route flapping). 894 In Appendix A.3, we give a number of examples of strictly monotonic, 895 isotonic routing metrics that are known to work well in practice. 897 3.5.3. Encoding of Updates 899 In a large network, the bulk of Babel traffic consists of route 900 updates; hence, some care has been given to encoding them 901 efficiently. An Update TLV itself only contains the prefix, seqno, 902 and metric, while the next hop is derived either from the network- 903 layer source address of the packet or from an explicit Next Hop TLV 904 in the same packet. The router-id is derived from a separate Router- 905 Id TLV in the same packet, which optimises the case when multiple 906 updates are sent with the same router-id. 908 Additionally, a prefix of the advertised prefix can be omitted in an 909 Update TLV, in which case it is copied from a previous Update TLV in 910 the same packet -- this is known as address compression [PACKETBB]. 912 Finally, as a special optimisation for the case when a router-id 913 coincides with the interface-id part of an IPv6 address, the router- 914 id can optionally be derived from the low-order bits of the 915 advertised prefix. 917 The encoding of updates is described in detail in Section 4.4. 919 3.5.4. Route Acquisition 921 When a Babel node receives an update (router-id, prefix, seqno, 922 metric) from a neighbour neigh with a link cost value equal to cost, 923 it checks whether it already has a routing table entry indexed by 924 (neigh, router-id, prefix). 926 If no such entry exists: 928 o if the update is unfeasible, it is ignored; 930 o if the metric is infinite (the update is a retraction), the update 931 is ignored; 933 o otherwise, a new route table entry is created, indexed by (neigh, 934 router-id, prefix), with seqno equal to seqno and an advertised 935 metric equal to the metric carried by the update. 937 If such an entry exists: 939 o if the entry is currently installed and the update is unfeasible, 940 then the behaviour depends on whether the router-ids of the two 941 entries match. If the router-ids are different, the update is 942 treated as though it were a retraction (i.e., as though the metric 943 were FFFF hexadecimal). If the router-ids are equal, the update 944 is ignored; 946 o otherwise (i.e., if either the update is feasible or the entry is 947 not currently installed), then the entry's sequence number, 948 advertised metric, metric, and router-id are updated and, unless 949 the advertised metric is infinite, the route's expiry timer is 950 reset to a small multiple of the Interval value included in the 951 update. 953 When a route's expiry timer triggers, the behaviour depends on 954 whether the route's metric is finite. If the metric is finite, it is 955 set to infinity and the expiry timer is reset. If the metric is 956 already infinite, the route is flushed from the route table. 958 After the routing table is updated, the route selection procedure 959 (Section 3.6) is run. 961 3.5.5. Hold Time 963 When a prefix p is retracted, because all routes are unfeasible, too 964 old, or have an infinite metric, and a shorter prefix p' that covers 965 p is reachable, p' cannot in general be used for routing packets 966 destined to p without running the risk of creating a routing loop 967 (Section 2.8). 969 To avoid this issue, whenever a prefix is retracted, a routing table 970 entry with infinite metric is maintained as described in 971 Section 3.5.4 above, and packets destined for that prefix MUST NOT be 972 forwarded by following a route for a shorter prefix. The infinite 973 metric entry is maintained until it is superseded by a feasible 974 update; if no such update arrives within the route hold time, the 975 entry is flushed. 977 3.6. Route Selection 979 Route selection is the process by which a single route for a given 980 prefix is selected to be used for forwarding packets and to be re- 981 advertised to a node's neighbours. 983 Babel is designed to allow flexible route selection policies. As far 984 as the protocol's correctness is concerned, the route selection 985 policy MUST only satisfy the following properties: 987 o a route with infinite metric (a retracted route) is never 988 selected; 990 o an unfeasible route is never selected. 992 Note, however, that Babel does not naturally guarantee the stability 993 of routing, and configuring conflicting route selection policies on 994 different routers may lead to persistent route oscillation. 996 Defining a good route selection policy for Babel is an open research 997 problem. Route selection can take into account multiple mutually 998 contradictory criteria; in roughly decreasing order of importance, 999 these are: 1001 o routes with a small metric should be preferred over routes with a 1002 large metric; 1004 o switching router-ids should be avoided; 1006 o routes through stable neighbours should be preferred over routes 1007 through unstable ones; 1009 o stable routes should be preferred over unstable ones; 1011 o switching next hops should be avoided. 1013 A simple strategy is to choose the feasible route with the smallest 1014 metric, with a small amount of hysteresis applied to avoid switching 1015 router-ids. 1017 After the route selection procedure is run, triggered updates 1018 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1020 3.7. Sending Updates 1022 A Babel speaker advertises to its neighbours its set of selected 1023 routes. Normally, this is done by sending one or more multicast 1024 packets containing Update TLVs on all of its connected interfaces; 1025 however, on link technologies where multicast is significantly more 1026 expensive than unicast, a node MAY choose to send multiple copies of 1027 updates in unicast packets when the number of neighbours is small. 1029 Additionally, in order to ensure that any black-holes are reliably 1030 cleared in a timely manner, a Babel node sends retractions (updates 1031 with an infinite metric) for any recently retracted prefixes. 1033 If an update is for a route injected into the Babel domain by the 1034 local node (e.g., the address of a local interface, the prefix of a 1035 directly attached network, or redistributed from a different routing 1036 protocol), the router-id is set to the local id, the metric is set to 1037 some arbitrary finite value (typically 0), and the seqno is set to 1038 the local router's sequence number. 1040 If an update is for a route learned from another Babel speaker, the 1041 router-id and sequence number are copied from the routing table 1042 entry, and the metric is computed as specified in Section 3.5.2. 1044 3.7.1. Periodic Updates 1046 Every Babel speaker periodically advertises all of its selected 1047 routes on all of its interfaces, including any recently retracted 1048 routes. Since Babel doesn't suffer from routing loops (there is no 1049 "counting to infinity") and relies heavily on triggered updates 1050 (Section 3.7.2), this full dump only needs to happen infrequently. 1052 3.7.2. Triggered Updates 1054 In addition to the periodic routing updates, a Babel speaker sends 1055 unscheduled, or triggered, updates in order to inform its neighbours 1056 of a significant change in the network topology. 1058 A change of router-id for the selected route to a given prefix may be 1059 indicative of a routing loop in formation; hence, a node MUST send a 1060 triggered update in a timely manner whenever it changes the selected 1061 router-id for a given destination. Additionally, it SHOULD make a 1062 reasonable attempt at ensuring that all neighbours receive this 1063 update. 1065 There are two strategies for ensuring that. If the number of 1066 neighbours is small, then it is reasonable to send the update 1067 together with an acknowledgement request; the update is resent until 1068 all neighbours have acknowledged the packet, up to some number of 1069 times. If the number of neighbours is large, however, requesting 1070 acknowledgements from all of them might cause a non-negligible amount 1071 of network traffic; in that case, it may be preferable to simply 1072 repeat the update some reasonable number of times (say, 5 for 1073 wireless and 2 for wired links). 1075 A route retraction is somewhat less worrying: if the route retraction 1076 doesn't reach all neighbours, a black-hole might be created, which, 1077 unlike a routing loop, does not endanger the integrity of the 1078 network. When a route is retracted, a node SHOULD send a triggered 1079 update and SHOULD make a reasonable attempt at ensuring that all 1080 neighbours receive this retraction. 1082 Finally, a node MAY send a triggered update when the metric for a 1083 given prefix changes in a significant manner, either due to a 1084 received update or because a link cost has changed. A node SHOULD 1085 NOT send triggered updates for other reasons, such as when there is a 1086 minor fluctuation in a route's metric, when the selected next hop 1087 changes, or to propagate a new sequence number (except to satisfy a 1088 request, as specified in Section 3.8). 1090 3.7.3. Maintaining Feasibility Distances 1092 Before sending an update (prefix, plen, router-id, seqno, metric) 1093 with finite metric (i.e., not a route retraction), a Babel node 1094 updates the feasibility distance maintained in the source table. 1095 This is done as follows. 1097 If no entry indexed by (prefix, plen, router-id) exists in the source 1098 table, then one is created with value (prefix, plen, router-id, 1099 seqno, metric). 1101 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1102 it is updated as follows: 1104 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1105 o if seqno = seqno' and metric' > metric, then metric' := metric; 1107 o otherwise, nothing needs to be done. 1109 The garbage-collection timer for the entry is then reset. Note that 1110 the garbage-collection timer is not reset when a retraction is sent. 1112 3.7.4. Split Horizon 1114 When running over a transitive, symmetric link technology, e.g., a 1115 point-to-point link or a wired LAN technology such as Ethernet, a 1116 Babel node SHOULD use an optimisation known as split horizon. When 1117 split horizon is used on a given interface, a routing update is not 1118 sent on this particular interface when the advertised route was 1119 learnt from a neighbour over the same interface. 1121 Split horizon SHOULD NOT be applied to an interface unless the 1122 interface is known to be symmetric and transitive; in particular, 1123 split horizon is not applicable to decentralised wireless link 1124 technologies (e.g., IEEE 802.11 in ad hoc mode). 1126 3.8. Explicit Route Requests 1128 In normal operation, a node's routing table is populated by the 1129 regular and triggered updates sent by its neighbours. Under some 1130 circumstances, however, a node sends explicit requests to cause a 1131 resynchronisation with the source after a mobility event or to 1132 prevent a route from spuriously expiring. 1134 The Babel protocol provides two kinds of explicit requests: route 1135 requests, which simply request an update for a given prefix, and 1136 seqno requests, which request an update for a given prefix with a 1137 specific sequence number. The former are never forwarded; the latter 1138 are forwarded if they cannot be satisfied by a neighbour. 1140 3.8.1. Handling Requests 1142 Upon receiving a request, a node either forwards the request or sends 1143 an update in reply to the request, as described in the following 1144 sections. If this causes an update to be sent, the update is either 1145 sent to a multicast address on the interface on which the request was 1146 received, or to the unicast address of the neighbour that sent the 1147 update. 1149 The exact behaviour is different for route requests and seqno 1150 requests. 1152 3.8.1.1. Route Requests 1154 When a node receives a route request for a prefix (prefix, plen), it 1155 checks its route table for a selected route to this exact prefix. If 1156 such a route exists, it MUST send an update; if such a route does 1157 not, it MUST send a retraction for that prefix. 1159 When a node receives a wildcard route request, it SHOULD send a full 1160 routing table dump. 1162 3.8.1.2. Seqno Requests 1164 When a node receives a seqno request for a given router-id and 1165 sequence number, it checks whether its routing table contains a 1166 selected entry for that prefix; if no such entry exists, or the entry 1167 has infinite metric, it ignores the request. 1169 If a selected route for the given prefix exists, and either the 1170 router-ids are different or the router-ids are equal and the entry's 1171 sequence number is no smaller than the requested sequence number, it 1172 MUST send an update for the given prefix. 1174 If the router-ids match but the requested seqno is larger than the 1175 route entry's, the node compares the router-id against its own 1176 router-id. If the router-id is its own, then it increases its 1177 sequence number by 1 and sends an update. A node MUST NOT increase 1178 its sequence number by more than 1 in response to a seqno request. 1180 If the requested router-id is not its own, the received request's hop 1181 count is 2 or more, and the node has a route (not necessarily a 1182 feasible one) for the requested prefix that does not use the 1183 requestor as a next hop, the node SHOULD forward the request. It 1184 does so by decreasing the hop count and sending the request in a 1185 unicast packet destined to a neighbour that advertises the given 1186 prefix (not necessarily the selected neighbour) and that is distinct 1187 from the neighbour from which the request was received. 1189 A node SHOULD maintain a list of recently forwarded requests and 1190 forward the reply in a timely manner. A node SHOULD compare every 1191 incoming request against its list of recently forwarded requests and 1192 avoid forwarding it if it is redundant. 1194 Since the request-forwarding mechanism does not necessarily obey the 1195 feasibility condition, it may get caught in routing loops; hence, 1196 requests carry a hop count to limit the time for which they remain in 1197 the network. However, since requests are only ever forwarded as 1198 unicast packets, the initial hop count need not be kept particularly 1199 low, and performing an expanding horizon search is not necessary. A 1200 request MUST NOT be forwarded to a multicast address, and it MUST be 1201 forwarded to a single neighbour only. 1203 3.8.2. Sending Requests 1205 A Babel node MAY send a route or seqno request at any time, to a 1206 multicast or a unicast address; there is only one case when 1207 originating requests is required (Section 3.8.2.1). 1209 3.8.2.1. Avoiding Starvation 1211 When a route is retracted or expires, a Babel node usually switches 1212 to another feasible route for the same prefix. It may be the case, 1213 however, that no such routes are available. 1215 A node that has lost all feasible routes to a given destination MUST 1216 send a seqno request. The router-id of the request is set to the 1217 router-id of the route that it has just lost, and the requested seqno 1218 is the value contained in the source table, plus 1. 1220 Such a request SHOULD be multicast over all of the node's attached 1221 interfaces. Similar requests will be sent by other nodes that are 1222 affected by the route's loss and will be forwarded by neighbouring 1223 nodes up to the source. If the network is connected, and there is no 1224 packet loss, this will result in a route being advertised with a new 1225 sequence number. (Note that, due to duplicate suppression, only a 1226 small number of such requests will actually reach the source.) 1228 In order to compensate for packet loss, a node SHOULD repeat such a 1229 request a small number of times if no route becomes feasible within a 1230 short time. Under heavy packet loss, however, all such requests may 1231 be lost; in that case, the second mechanism in the next section will 1232 eventually ensure that a new seqno is received. 1234 3.8.2.2. Dealing with Unfeasible Updates 1236 When a route's metric increases, a node might receive an unfeasible 1237 update for a route that it has currently selected. As specified in 1238 Section 3.5.1, the receiving node will either ignore the update or 1239 retract the route. 1241 In order to keep routes from spuriously expiring because they have 1242 become unfeasible, a node SHOULD send a unicast seqno request 1243 whenever it receives an unfeasible update for a route that is 1244 currently selected. The requested sequence number is computed from 1245 the source table as above. 1247 Additionally, a node SHOULD send a unicast seqno request whenever it 1248 receives an unfeasible update from a currently unselected neighbour 1249 that is "good enough", i.e., that would lead to the received route 1250 becoming selected were it feasible. 1252 3.8.2.3. Preventing Routes from Expiring 1254 In normal operation, a route's expiry timer should never trigger: 1255 since a route's hold time is computed from an explicit interval 1256 included in Update TLVs, a new update should arrive in time to 1257 prevent a route from expiring. 1259 In the presence of packet loss, however, it may be the case that no 1260 update is successfully received for an extended period of time, 1261 causing a route to expire. In order to avoid such spurious expiry, 1262 shortly before a selected route expires, a Babel node SHOULD send a 1263 unicast route request to the neighbour that advertised this route; 1264 since nodes always send retractions in response to non-wildcard route 1265 requests (Section 3.8.1.1), this will usually result in either the 1266 route being refreshed or a retraction being received. 1268 3.8.2.4. Acquiring New Neighbours 1270 In order to speed up convergence after a mobility event, a node MAY 1271 send a unicast wildcard request after acquiring a new neighbour. 1272 Additionally, a node MAY send a small number of multicast wildcard 1273 requests shortly after booting. 1275 4. Protocol Encoding 1277 A Babel packet is sent as the body of a UDP datagram, with network- 1278 layer hop count set to 1, destined to a well-known multicast address 1279 or to a unicast address, over IPv4 or IPv6; in the case of IPv6, 1280 these addresses are link-local. Both the source and destination UDP 1281 port are set to a well-known port number. A Babel packet MUST be 1282 silently ignored unless its source address is either a link-local 1283 IPv6 address, or an IPv4 address belonging to the local network, and 1284 its source port is the well-known Babel port. Babel packets MUST NOT 1285 be sent as IPv6 Jumbograms. 1287 In order to minimise the number of packets being sent while avoiding 1288 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1289 the size of the packets it sends, up to the outgoing interface's MTU 1290 adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets 1291 for UDP/IPv6). It MUST NOT send packets larger than the attached 1292 interface's MTU (adjusted for lower-layer headers) or 512 octets, 1293 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1294 layer headers. Every Babel speaker MUST be able to receive packets 1295 that are as large as any attached interface's MTU (adjusted for 1296 lower-layer headers) or 512 octets, whichever is larger. 1298 In order to avoid global synchronisation of a Babel network and to 1299 aggregate multiple TLVs into large packets, a Babel node MUST buffer 1300 every TLV and delay sending a UDP packet by a small, randomly chosen 1301 delay [JITTER]. In order to allow accurate computation of packet 1302 loss rates, this delay MUST NOT be larger than half the advertised 1303 Hello interval. 1305 4.1. Data Types 1307 4.1.1. Interval 1309 Relative times are carried as 16-bit values specifying a number of 1310 centiseconds (hundredths of a second). This allows times up to 1311 roughly 11 minutes with a granularity of 10ms, which should cover all 1312 reasonable applications of Babel. 1314 4.1.2. Router-Id 1316 A router-id is an arbitrary 8-octet. A router-id MUST NOT consist of 1317 either all zeroes or all ones. Router-ids SHOULD be assigned in 1318 modified EUI-64 format [ADDRARCH]. 1320 4.1.3. Address 1322 Since the bulk of the protocol is taken by addresses, multiple ways 1323 of encoding addresses are defined. Additionally, a common subnet 1324 prefix may be omitted when multiple addresses are sent in a single 1325 packet -- this is known as address compression [PACKETBB]. 1327 Address encodings: 1329 o AE 0: wildcard address. The value is 0 octets long. 1331 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1333 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1335 o AE 3: link-local IPv6 address. The value is 8 octets long, a 1336 prefix of fe80::/64 is implied. 1338 The address family of an address is either IPv4 or IPv6; it is 1339 undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. 1341 4.1.4. Prefixes 1343 A network prefix is encoded just like a network address, but it is 1344 stored in the smallest number of octets that are enough to hold the 1345 significant bits (up to the prefix length). 1347 4.2. Packet Format 1349 A Babel packet consists of a 4-octet header, followed by a sequence 1350 of TLVs. 1352 0 1 2 3 1353 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 1354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1355 | Magic | Version | Body length | 1356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1357 | Packet Body ... 1358 +-+-+-+-+-+-+-+-+-+-+-+-+- 1360 Fields : 1362 Magic The arbitrary but carefully chosen value 42 (decimal); 1363 packets with a first octet different from 42 MUST be 1364 silently ignored. 1366 Version This document specifies version 2 of the Babel protocol. 1367 Packets with a second octet different from 2 MUST be 1368 silently ignored. 1370 Body length The length in octets of the body following the packet 1371 header. 1373 Body The packet body; a sequence of TLVs. 1375 Any data following the body MUST be silently ignored. 1377 4.3. TLV Format 1379 With the exception of Pad1, all TLVs have the following structure: 1381 0 1 2 3 1382 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 1383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1384 | Type | Length | Body... 1385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1387 Fields : 1389 Type The type of the TLV. 1391 Length The length of the body, exclusive of the Type and Length 1392 fields. If the body is longer than the expected length of 1393 a given type of TLV, any extra data MUST be silently 1394 ignored. 1396 Body The TLV body, the interpretation of which depends on the 1397 type. 1399 TLVs with an unknown type value MUST be silently ignored. 1401 4.4. Details of Specific TLVs 1403 4.4.1. Pad1 1405 0 1406 0 1 2 3 4 5 6 7 1407 +-+-+-+-+-+-+-+-+ 1408 | Type = 0 | 1409 +-+-+-+-+-+-+-+-+ 1411 Fields : 1413 Type Set to 0 to indicate a Pad1 TLV. 1415 This TLV is silently ignored on reception. 1417 4.4.2. PadN 1419 0 1 2 3 1420 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 1421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1422 | Type = 1 | Length | MBZ... 1423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1425 Fields : 1427 Type Set to 1 to indicate a PadN TLV. 1429 Length The length of the body, exclusive of the Type and Length 1430 fields. 1432 MBZ Set to 0 on transmission. 1434 This TLV is silently ignored on reception. 1436 4.4.3. Acknowledgement Request 1438 0 1 2 3 1439 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 1440 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1441 | Type = 2 | Length | Reserved | 1442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1443 | Nonce | Interval | 1444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1446 This TLV requests that the receiver send an Acknowledgement TLV 1447 within the number of centiseconds specified by the Interval field. 1449 Fields : 1451 Type Set to 2 to indicate an Acknowledgement Request TLV. 1453 Length The length of the body, exclusive of the Type and Length 1454 fields. 1456 Reserved Sent as 0 and MUST be ignored on reception. 1458 Nonce An arbitrary value that will be echoed in the receiver's 1459 Acknowledgement TLV. 1461 Interval A time interval in centiseconds after which the sender will 1462 assume that this packet has been lost. This MUST NOT be 0. 1463 The receiver MUST send an acknowledgement before this time 1464 has elapsed (with a margin allowing for propagation time). 1466 4.4.4. Acknowledgement 1468 0 1 2 3 1469 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 1470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1471 | Type = 3 | Length | Nonce | 1472 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1474 This TLV is sent by a node upon receiving an Acknowledgement Request. 1476 Fields : 1478 Type Set to 3 to indicate an Acknowledgement TLV. 1480 Length The length of the body, exclusive of the Type and Length 1481 fields. 1483 Nonce Set to the Nonce value of the Acknowledgement Request that 1484 prompted this Acknowledgement. 1486 Since nonce values are not globally unique, this TLV MUST be sent to 1487 a unicast address. 1489 4.4.5. Hello 1491 0 1 2 3 1492 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 1493 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1494 | Type = 4 | Length | Reserved | 1495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1496 | Seqno | Interval | 1497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1499 This TLV is used for neighbour discovery and for determining a link's 1500 reception cost. 1502 Fields : 1504 Type Set to 4 to indicate a Hello TLV. 1506 Length The length of the body, exclusive of the Type and Length 1507 fields. 1509 Reserved Sent as 0 and MUST be ignored on reception. 1511 Seqno The value of the sending node's Hello seqno for this 1512 interface. 1514 Interval An upper bound, expressed in centiseconds, on the time 1515 after which the sending node will send a new Hello TLV. 1516 This MUST NOT be 0. 1518 Since there is a single seqno counter for all the Hellos sent by a 1519 given node over a given interface, this TLV MUST be sent to a 1520 multicast destination. In order to avoid large discontinuities in 1521 link quality, multiple Hello TLVs SHOULD NOT be sent in the same 1522 packet. 1524 4.4.6. IHU 1525 0 1 2 3 1526 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 1527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1528 | Type = 5 | Length | AE | Reserved | 1529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1530 | Rxcost | Interval | 1531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1532 | Address... 1533 +-+-+-+-+-+-+-+-+-+-+-+- 1535 An IHU ("I Heard You") TLV is used for confirming bidirectional 1536 reachability and carrying a link's transmission cost. 1538 Fields : 1540 Type Set to 5 to indicate an IHU TLV. 1542 Length The length of the body, exclusive of the Type and Length 1543 fields. 1545 AE The encoding of the Address field. This should be 1 or 3 1546 in most cases. As an optimisation, it MAY be 0 if the TLV 1547 is sent to a unicast address, if the association is over a 1548 point-to-point link, or when bidirectional reachability is 1549 ascertained by means outside of the Babel protocol. 1551 Reserved Sent as 0 and MUST be ignored on reception. 1553 Rxcost The rxcost according to the sending node of the interface 1554 whose address is specified in the Address field. The value 1555 FFFF hexadecimal (infinity) indicates that this interface 1556 is unreachable. 1558 Interval An upper bound, expressed in centiseconds, on the time 1559 after which the sending node will send a new IHU; this MUST 1560 NOT be 0. The receiving node will use this value in order 1561 to compute a hold time for this symmetric association. 1563 Address The address of the destination node, in the format 1564 specified by the AE field. Address compression is not 1565 allowed. 1567 Conceptually, an IHU is destined to a single neighbour. However, IHU 1568 TLVs contain an explicit destination address, and it SHOULD be sent 1569 to a multicast address, as this allows aggregation of IHUs destined 1570 to distinct neighbours into a single packet and avoids the need for 1571 an ARP or Neighbour Discovery exchange when a neighbour is not being 1572 used for data traffic. 1574 IHU TLVs with an unknown value for the AE field MUST be silently 1575 ignored. 1577 4.4.7. Router-Id 1579 0 1 2 3 1580 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 1581 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1582 | Type = 6 | Length | Reserved | 1583 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1584 | | 1585 + Router-Id + 1586 | | 1587 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1589 A Router-Id TLV establishes a router-id that is implied by subsequent 1590 Update TLVs. 1592 Fields : 1594 Type Set to 6 to indicate a Router-Id TLV. 1596 Length The length of the body, exclusive of the Type and Length 1597 fields. 1599 Reserved Sent as 0 and MUST be ignored on reception. 1601 Router-Id The router-id for routes advertised in subsequent Update 1602 TLVs. This MUST NOT consist of all zeroes or all ones. 1604 4.4.8. Next Hop 1606 0 1 2 3 1607 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 1608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1609 | Type = 7 | Length | AE | Reserved | 1610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1611 | Next hop... 1612 +-+-+-+-+-+-+-+-+-+-+-+- 1614 A Next Hop TLV establishes a next-hop address for a given address 1615 family (IPv4 or IPv6) that is implied by subsequent Update TLVs. 1617 Fields : 1619 Type Set to 7 to indicate a Next Hop TLV. 1621 Length The length of the body, exclusive of the Type and Length 1622 fields. 1624 AE The encoding of the Address field. This SHOULD be 1 or 3 1625 and MUST NOT be 0. 1627 Reserved Sent as 0 and MUST be ignored on reception. 1629 Next hop The next-hop address advertised by subsequent Update TLVs, 1630 for this address family. 1632 When the address family matches the network-layer protocol that this 1633 packet is transported over, a Next Hop TLV is not needed: in that 1634 case, the next hop is taken to be the source address of the packet. 1636 Next Hop TLVs with an unknown value for the AE field MUST be silently 1637 ignored. 1639 4.4.9. Update 1641 0 1 2 3 1642 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1644 | Type = 8 | Length | AE | Flags | 1645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1646 | Plen | Omitted | Interval | 1647 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1648 | Seqno | Metric | 1649 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1650 | Prefix... 1651 +-+-+-+-+-+-+-+-+-+-+-+- 1653 An Update TLV advertises or retracts a route. As an optimisation, 1654 this can also have the side effect of establishing a new implied 1655 router-id and a new default prefix. 1657 Fields : 1659 Type Set to 8 to indicate an Update TLV. 1661 Length The length of the body, exclusive of the Type and Length 1662 fields. 1664 AE The encoding of the Prefix field. 1666 Flags The individual bits of this field specify special handling 1667 of this TLV (see below). Every node MUST be able to 1668 interpret the flags with values 80 and 40 hexadecimal; 1669 unknown flags MUST be silently ignored. 1671 Plen The length of the advertised prefix. 1673 Omitted The number of octets that have been omitted at the 1674 beginning of the advertised prefix and that should be taken 1675 from a preceding Update TLV with the flag with value 80 1676 hexadecimal set. 1678 Interval An upper bound, expressed in centiseconds, on the time 1679 after which the sending node will send a new update for 1680 this prefix. This MUST NOT be 0 and SHOULD NOT be less 1681 than 10. The receiving node will use this value to compute 1682 a hold time for this routing table entry. The value FFFF 1683 hexadecimal (infinity) expresses that this announcement 1684 will not be repeated unless a request is received 1685 (Section 3.8.2.3). 1687 Seqno The originator's sequence number for this update. 1689 Metric The sender's metric for this route. The value FFFF 1690 hexadecimal (infinity) means that this is a route 1691 retraction. 1693 Prefix The prefix being advertised. This field's size is (Plen/8 1694 - Omitted) rounded upwards. 1696 The Flags field is interpreted as follows: 1698 o if the bit with value 80 hexadecimal is set, then this Update 1699 establishes a new default prefix for subsequent Update TLVs with a 1700 matching address family within the same packet; 1702 o if the bit with value 40 hexadecimal is set, then the low-order 8 1703 octets of the advertised prefix establish a new default router-id 1704 for this TLV and subsequent Update TLVs in the same packet. 1706 The prefix being advertised by an Update TLV is computed as follows: 1708 o the first Omitted octets of the prefix are taken from the previous 1709 Update TLV with flag 80 hexadecimal set and the same address 1710 family; 1712 o the next (Plen/8 - Omitted) (rounded upwards) octets are taken 1713 from the Prefix field; 1715 o the remaining octets are set to 0. 1717 If the Metric field is finite, the router-id of the originating node 1718 for this announcement is taken from the low-order 8 octets of the 1719 prefix advertised by this Update if the bit with value 40 hexadecimal 1720 is set in the Flags field. Otherwise, it is taken either from the 1721 preceding Router-Id packet, or the preceding Update packet with flag 1722 40 hexadecimal set, whichever comes last. 1724 The next-hop address for this update is taken from the last preceding 1725 Next Hop TLV with a matching address family in the same packet; if no 1726 such TLV exists, it is taken from the network-layer source address of 1727 this packet. 1729 If the metric field is FFFF hexadecimal, this TLV specifies a 1730 retraction. In that case, the current router-id and the Seqno are 1731 not used. AE MAY then be 0, in which case this Update retracts all 1732 of the routes previously advertised on this interface. 1734 Update TLVs with an unknown value for the AE field MUST be silently 1735 ignored. 1737 4.4.10. Route Request 1739 0 1 2 3 1740 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 1741 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1742 | Type = 9 | Length | AE | Plen | 1743 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1744 | Prefix... 1745 +-+-+-+-+-+-+-+-+-+-+-+- 1747 A Route Request TLV prompts the receiver to send an update for a 1748 given prefix, or a full routing table dump. 1750 Fields : 1752 Type Set to 9 to indicate a Route Request TLV. 1754 Length The length of the body, exclusive of the Type and Length 1755 fields. 1757 AE The encoding of the Prefix field. The value 0 specifies 1758 that this is a request for a full routing table dump (a 1759 wildcard request). 1761 Plen The length of the requested prefix. 1763 Prefix The prefix being requested. This field's size is Plen/8 1764 rounded upwards. 1766 A Request TLV prompts the receiving node to send an update message 1767 for the prefix specified by the AE, Plen, and Prefix fields, or a 1768 full dump of its routing table if AE is 0 (in which case Plen MUST be 1769 0 and Prefix is of length 0). A Request may be sent to a unicast 1770 address if it is destined to a single node, or to a multicast address 1771 if the request is destined to all of the neighbours of the sending 1772 interface. 1774 4.4.11. Seqno Request 1776 0 1 2 3 1777 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 1778 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1779 | Type = 10 | Length | AE | Plen | 1780 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1781 | Seqno | Hop Count | Reserved | 1782 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1783 | | 1784 + Router-Id + 1785 | | 1786 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1787 | Prefix... 1788 +-+-+-+-+-+-+-+-+-+-+ 1790 A Seqno Request TLV prompts the receiver to send an Update for a 1791 given prefix with a given sequence number, or to forward the request 1792 further if it cannot be satisfied locally. 1794 Fields : 1796 Type Set to 10 to indicate a Seqno Request message. 1798 Length The length of the body, exclusive of the Type and Length 1799 fields. 1801 AE The encoding of the Prefix field. This MUST NOT be 0. 1803 Plen The length of the requested prefix. 1805 Seqno The sequence number that is being requested. 1807 Hop Count The maximum number of times that this TLV may be forwarded, 1808 plus 1. This MUST NOT be 0. 1810 Reserved Sent as 0 and MUST be ignored on reception. 1812 Router Id The Router-Id that is being requested. This MUST NOT 1813 consist of all zeroes or all ones. 1815 Prefix The prefix being requested. This field's size is Plen/8 1816 rounded upwards. 1818 A Seqno Request TLV prompts the receiving node to send an Update for 1819 the prefix specified by the AE, Plen, and Prefix fields, with either 1820 a router-id different from what is specified by the Router-Id field, 1821 or a Seqno no less than what is specified by the Seqno field. If 1822 this request cannot be satisfied locally, then it is forwarded 1823 according to the rules set out in Section 3.8.1.2. 1825 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 1826 be forwarded to a multicast address and MUST NOT be forwarded to more 1827 than one neighbour. A request MUST NOT be forwarded if its Hop Count 1828 field is 1. 1830 5. IANA Considerations 1832 IANA has registered the UDP port number 6696, called "babel", for use 1833 by the Babel protocol. 1835 IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and 1836 the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. 1838 6. Security Considerations 1840 As defined in this document, Babel is a completely insecure protocol. 1841 Any attacker can attract data traffic by advertising routes with a 1842 low metric. This particular issue can be solved either by lower- 1843 layer security mechanisms (e.g., IPsec or link-layer security), or by 1844 appending a cryptographic key to Babel packets; the provision of 1845 ignoring any data contained within a Babel packet beyond the body 1846 length declared by the header is designed for just such a purpose. 1848 The information that a Babel node announces to the whole routing 1849 domain is often sufficient to determine a mobile node's physical 1850 location with reasonable precision. The privacy issues that this 1851 causes can be mitigated somewhat by using randomly chosen router-ids 1852 and randomly chosen IP addresses, and changing them periodically. 1854 When carried over IPv6, Babel packets are ignored unless they are 1855 sent from a link-local IPv6 address; since routers don't forward 1856 link-local IPv6 packets, this provides protection against spoofed 1857 Babel packets being sent from the global Internet. No such natural 1858 protection exists when Babel packets are carried over IPv4. 1860 7. References 1862 7.1. Normative References 1864 [ADDRARCH] 1865 Hinden, R. and S. Deering, "IP Version 6 Addressing 1866 Architecture", RFC 4291, February 2006. 1868 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1869 Requirement Levels", RFC 2119, March 1997. 1871 7.2. Informative References 1873 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 1874 Sequenced Distance-Vector Routing (DSDV) for Mobile 1875 Computers", ACM SIGCOMM'94 Conference on Communications 1876 Architectures, Protocols and Applications 234-244, 1994. 1878 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 1879 Computations", IEEE/ACM Transactions on Networking 1:1, 1880 February 1993. 1882 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 1883 "EIGRP -- a Fast Routing Protocol Based on Distance 1884 Vectors", Proc. Interop 94, 1994. 1886 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 1887 high-throughput path metric for multi-hop wireless 1888 networks", Proc. MobiCom 2003, 2003. 1890 [IS-IS] "Information technology -- Telecommunications and 1891 information exchange between systems -- Intermediate 1892 System to Intermediate System intra-domain routeing 1893 information exchange protocol for use in conjunction with 1894 the protocol for providing the connectionless-mode network 1895 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 1897 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 1898 periodic routing messages", IEEE/ACM Transactions on 1899 Networking 2, 2, 122-136, April 1994. 1901 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 1903 [PACKETBB] 1904 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 1905 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 1906 Format", RFC 5444, February 2009. 1908 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 1910 Appendix A. Cost and Metric Computation 1912 The strategy for computing link costs and route metrics is a local 1913 matter; Babel itself only requires that it comply with the conditions 1914 given in Section 3.4.3 and Section 3.5.2. Different nodes MAY use 1915 different strategies in a single network and MAY use different 1916 strategies on different interface types. This section gives a few 1917 examples of such strategies. 1919 The sample implementation of Babel maintains statistics about the 1920 last 16 received Hello TLVs (Appendix A.1), computes costs by using 1921 the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX 1922 (Appendix A.2.2) on wireless links. It uses an additive algebra for 1923 metric computation (Appendix A.3.1). 1925 A.1. Maintaining Hello History 1927 For each neighbour, the sample implementation of Babel maintains a 1928 Hello history and an expected sequence number. The Hello history is 1929 a vector of 16 bits, where a 1 value represents a received Hello, and 1930 a 0 value a missed Hello. The expected sequence number, written ne, 1931 is the sequence number that is expected to be carried by the next 1932 received hello from this neighbour. 1934 Whenever it receives a Hello packet from a neighbour, a node compares 1935 the received sequence number nr with its expected sequence number ne. 1936 Depending on the outcome of this comparison, one of the following 1937 actions is taken: 1939 o if the two differ by more than 16 (modulo 2^16), then the sending 1940 node has probably rebooted and lost its sequence number; the 1941 associated neighbour table entry is flushed; 1943 o otherwise, if the received nr is smaller (modulo 2^16) than the 1944 expected sequence number ne, then the sending node has increased 1945 its Hello interval without our noticing; the receiving node 1946 removes the last (ne - nr) entries from this neighbour's Hello 1947 history (we "undo history"); 1949 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 1950 node has decreased its Hello interval, and some Hellos were lost; 1951 the receiving node adds (nr - ne) 0 bits to the Hello history (we 1952 "fast-forward"). 1954 The receiving node then appends a 1 bit to the neighbour's Hello 1955 history, resets the neighbour's Hello timer, and sets ne to (nr + 1). 1957 It then resets the neighbour's Hello timer to 1.5 times the value 1958 advertised in the received Hello (the extra margin allows for the 1959 delay due to jitter). 1961 Whenever the Hello timer associated to a neighbour expires, the local 1962 node adds a 0 bit to this neighbour's Hello history, and increments 1963 the expected Hello number. If the Hello history is empty (it 1964 contains 0 bits only), the neighbour entry is flushed; otherwise, it 1965 resets the neighbour's Hello timer to the value advertised in the 1966 last Hello received from this neighbour (no extra margin is necessary 1967 in this case). 1969 A.2. Cost Computation 1971 A.2.1. k-out-of-j 1973 K-out-of-j link sensing is suitable for wired links that are either 1974 up, in which case they only occasionally drop a packet, or down, in 1975 which case they drop all packets. 1977 The k-out-of-j strategy is parameterised by two small integers k and 1978 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 1979 1. A node keeps a history of the last j hellos; if k or more of 1980 those have been correctly received, the link is assumed to be up, and 1981 the rxcost is set to K; otherwise, the link is assumed to be down, 1982 and the rxcost is set to infinity. 1984 The cost of such a link is defined as 1986 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 1988 o cost = txcost otherwise. 1990 A.2.2. ETX 1992 The Estimated Transmission Cost metric [ETX] estimates the number of 1993 times that a unicast frame will be retransmitted by the IEEE 802.11 1994 MAC, assuming infinite persistence. 1996 A node uses a neighbour's Hello history to compute an estimate, 1997 written beta, of the probability that a Hello TLV is successfully 1998 received. The rxcost is defined as 256/beta. 2000 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2001 successfully sending a Hello TLV. The cost is then computed by 2003 cost = 256/(alpha * beta) 2005 or, equivalently, 2007 cost = (MAX(txcost, 256) * rxcost) / 256. 2009 A.3. Metric Computation 2011 A.3.1. Additive Metrics 2013 The simplest approach for obtaining a monotonic, isotonic metric is 2014 to define the metric of a route as the sum of the costs of the 2015 component links. More formally, if a neighbour advertises a route 2016 with metric m over a link with cost c, then the resulting route has 2017 metric M(c, m) = c + m. 2019 A multiplicative metric can be converted to an additive one by taking 2020 the logarithm (in some suitable base) of the link costs. 2022 A.3.2. External Sources of Willingness 2024 A node may want to vary its willingness to forward packets by taking 2025 into account information that is external to the Babel protocol, such 2026 as the monetary cost of a link, the node's battery status, CPU load, 2027 etc. This can be done by adding to every route's metric a value k 2028 that depends on the external data. For example, if a battery-powered 2029 node receives an update with metric m over a link with cost c, it 2030 might compute a metric M(c, m) = k + c + m, where k depends on the 2031 battery status. 2033 In order to preserve strict monotonicity (Section 3.5.2), the value k 2034 must be greater than -c. 2036 Appendix B. Constants 2038 The choice of time constants is a trade-off between fast detection of 2039 mobility events and protocol overhead. Two implementations of Babel 2040 with different time constants will interoperate, although the 2041 resulting convergence time will most likely be dictated by the 2042 slowest of the two implementations. 2044 Experience with the sample implementation of Babel indicates that the 2045 Hello interval is the most important time constant: a mobility event 2046 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2047 on triggered updates and explicit requests, the Update interval only 2048 has an effect on the time it takes for accurate metrics to be 2049 propagated after variations in link costs too small to trigger an 2050 unscheduled update. 2052 At the time of writing, the sample implementation of Babel uses the 2053 following default values: 2055 Hello Interval: 4 seconds on wireless links, 20 seconds on wired 2056 links. 2058 IHU Interval: the advertised IHU interval is always 3 times the 2059 Hello interval. IHUs are actually sent with each Hello on lossy 2060 links (as determined from the Hello history), but only with every 2061 third Hello on lossless links. 2063 Update Interval: 4 times the Hello interval. 2065 IHU Hold Time: 3.5 times the advertised IHU interval. 2067 Route Expiry Time: 3.5 times the advertised update interval. 2069 Source GC time: 3 minutes. 2071 The amount of jitter applied to a packet depends on whether it 2072 contains any urgent TLVs or not. Urgent triggered updates and urgent 2073 requests are delayed by no more than 200ms; other TLVs are delayed by 2074 no more than one-half the Hello interval. 2076 Appendix C. Simplified Implementations 2078 Babel is a fairly economic protocol. Route updates take between 12 2079 and 40 octets per destination, depending on how successful 2080 compression is; in a double-stack mesh network, an average of less 2081 than 24 octets is typical. The route table occupies about 35 octets 2082 per IPv6 entry. To put these values into perspective, a single full- 2083 size Ethernet frame can carry some 65 route updates, and a megabyte 2084 of memory can contain a 20000-entry routing table and the associated 2085 source table. 2087 Babel is also a reasonably simple protocol. The sample 2088 implementation consists of less than 8000 lines of C code, and it 2089 compiles to less than 60 kB of text on a 32-bit CISC architecture. 2091 Nonetheless, in some very constrained environments, such as PDAs, 2092 microwave ovens, or abacuses, it may be desirable to have subset 2093 implementations of the protocol. 2095 A parasitic implementation is one that uses a Babel network for 2096 routing its packets but does not announce any of the routes that it 2097 has learnt from its neighbours. (This is slightly more than a 2098 passive implementation, which doesn't even announce routes to 2099 itself.) It may either maintain a full routing table or simply 2100 select a gateway amongst any one of its neighbours that announces a 2101 default route. Since a parasitic implementation never forwards 2102 packets, it cannot possibly participate in a routing loop; hence, it 2103 need not evaluate the feasibility condition, and need not maintain a 2104 source table. 2106 A parasitic implementation MUST answer acknowledgement requests and 2107 MUST participate in the Hello/IHU protocol. Finally, it MUST be able 2108 to reply to seqno requests for routes that it announces and SHOULD be 2109 able to reply to route requests. 2111 Appendix D. Software Availability 2113 The sample implementation of Babel is available from 2114 . 2116 Appendix E. Changes from previous versions 2118 E.1. Changes since RFC 6126 2120 o Changed UDP port number to 6696. 2122 o Consistently use router-id rather than id. 2124 o Clarified that the source garbage collection timer is reset after 2125 sending an update even if the entry was not modified. 2127 o In section "Seqno Requests", fixed an erroneous "route request". 2129 o In the description of the Seqno Request TLV, added the description 2130 of the Router-Id field. 2132 o Made router-ids all-0 and all-1 forbidden. 2134 Author's Address 2136 Juliusz Chroboczek 2137 IRIF, University of Paris-Diderot 2138 Case 7014 2139 75205 Paris Cedex 13 2140 France 2142 Email: jch@irif.fr