idnits 2.17.1 draft-ietf-babel-rfc6126bis-00.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 (August 1, 2016) is 2825 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 August 1, 2016 5 Expires: February 2, 2017 7 The Babel Routing Protocol 8 draft-ietf-babel-rfc6126bis-00 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 February 2, 2017. 33 Copyright Notice 35 Copyright (c) 2016 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 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 . . . . . . . . . . . . . . . . . . . . . . . . . 39 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 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 45 91 1. Introduction 93 Babel is a loop-avoiding distance-vector routing protocol that is 94 designed to be robust and efficient both in networks using prefix- 95 based routing and in networks using flat routing ("mesh networks"), 96 and both in relatively stable wired networks and in highly dynamic 97 wireless networks. 99 1.1. Features 101 The main property that makes Babel suitable for unstable networks is 102 that, unlike naive distance-vector routing protocols [RIP], it 103 strongly limits the frequency and duration of routing pathologies 104 such as routing loops and black-holes during reconvergence. Even 105 after a mobility event is detected, a Babel network usually remains 106 loop-free. Babel then quickly reconverges to a configuration that 107 preserves the loop-freedom and connectedness of the network, but is 108 not necessarily optimal; in many cases, this operation requires no 109 packet exchanges at all. Babel then slowly converges, in a time on 110 the scale of minutes, to an optimal configuration. This is achieved 111 by using sequenced routes, a technique pioneered by Destination- 112 Sequenced Distance-Vector routing [DSDV]. 114 More precisely, Babel has the following properties: 116 o when every prefix is originated by at most one router, Babel never 117 suffers from routing loops; 119 o when a prefix is originated by multiple routers, Babel may 120 occasionally create a transient routing loop for this particular 121 prefix; this loop disappears in a time proportional to its 122 diameter, and never again (up to an arbitrary garbage-collection 123 (GC) time) will the routers involved participate in a routing loop 124 for the same prefix; 126 o assuming reasonable packet loss rates, any routing black-holes 127 that may appear after a mobility event are corrected in a time at 128 most proportional to the network's diameter. 130 Babel has provisions for link quality estimation and for fairly 131 arbitrary metrics. When configured suitably, Babel can implement 132 shortest-path routing, or it may use a metric based, for example, on 133 measured packet loss. 135 Babel nodes will successfully establish an association even when they 136 are configured with different parameters. For example, a mobile node 137 that is low on battery may choose to use larger time constants (hello 138 and update intervals, etc.) than a node that has access to wall 139 power. Conversely, a node that detects high levels of mobility may 140 choose to use smaller time constants. The ability to build such 141 heterogeneous networks makes Babel particularly adapted to the 142 wireless environment. 144 Finally, Babel is a hybrid routing protocol, in the sense that it can 145 carry routes for multiple network-layer protocols (IPv4 and IPv6), 146 whichever protocol the Babel packets are themselves being carried 147 over. 149 1.2. Limitations 151 Babel has two limitations that make it unsuitable for use in some 152 environments. First, Babel relies on periodic routing table updates 153 rather than using a reliable transport; hence, in large, stable 154 networks it generates more traffic than protocols that only send 155 updates when the network topology changes. In such networks, 156 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 157 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 158 suitable. 160 Second, Babel does impose a hold time when a prefix is retracted 161 (Section 3.5.5). While this hold time does not apply to the exact 162 prefix being retracted, and hence does not prevent fast reconvergence 163 should it become available again, it does apply to any shorter prefix 164 that covers it. Hence, if a previously deaggregated prefix becomes 165 aggregated, it will be unreachable for a few minutes. This makes 166 Babel unsuitable for use in mobile networks that implement automatic 167 prefix aggregation. 169 1.3. Specification of Requirements 171 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 172 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 173 document are to be interpreted as described in [RFC2119]. 175 2. Conceptual Description of the Protocol 177 Babel is a mostly loop-free distance vector protocol: it is based on 178 the Bellman-Ford protocol, just like the venerable RIP [RIP], but 179 includes a number of refinements that either prevent loop formation 180 altogether, or ensure that a loop disappears in a timely manner and 181 doesn't form again. 183 Conceptually, Bellman-Ford is executed in parallel for every source 184 of routing information (destination of data traffic). In the 185 following discussion, we fix a source S; the reader will recall that 186 the same algorithm is executed for all sources. 188 2.1. Costs, Metrics and Neighbourship 190 As many routing algorithms, Babel computes costs of links between any 191 two neighbouring nodes, abstract values attached to the edges between 192 two nodes. We write C(A, B) for the cost of the edge from node A to 193 node B. 195 Given a route between any two nodes, the metric of the route is the 196 sum of the costs of all the edges along the route. The goal of the 197 routing algorithm is to compute, for every source S, the tree of the 198 routes of lowest metric to S. 200 Costs and metrics need not be integers. In general, they can be 201 values in any algebra that satisfies two fairly general conditions 202 (Section 3.5.2). 204 A Babel node periodically broadcasts Hello messages to all of its 205 neighbours; it also periodically sends an IHU ("I Heard You") message 206 to every neighbour from which it has recently heard a Hello. From 207 the information derived from Hello and IHU messages received from its 208 neighbour B, a node A computes the cost C(A, B) of the link from A to 209 B. 211 2.2. The Bellman-Ford Algorithm 213 Every node A maintains two pieces of data: its estimated distance to 214 S, written D(A), and its next-hop router to S, written NH(A). 215 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 217 Periodically, every node B sends to all of its neighbours a route 218 update, a message containing D(B). When a neighbour A of B receives 219 the route update, it checks whether B is its selected next hop; if 220 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 221 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 222 its current value of D(A). If that value is smaller, meaning that 223 the received update advertises a route that is better than the 224 currently selected route, then NH(A) is set to B, and D(A) is set to 225 C(A, B) + D(B). 227 A number of refinements to this algorithm are possible, and are used 228 by Babel. In particular, convergence speed may be increased by 229 sending unscheduled "triggered updates" whenever a major change in 230 the topology is detected, in addition to the regular, scheduled 231 updates. Additionally, a node may maintain a number of alternate 232 routes, which are being advertised by neighbours other than its 233 selected neighbour, and which can be used immediately if the selected 234 route were to fail. 236 2.3. Transient Loops in Bellman-Ford 238 It is well known that a naive application of Bellman-Ford to 239 distributed routing can cause transient loops after a topology 240 change. Consider for example the following diagram: 242 B 243 1 /| 244 1 / | 245 S --- A |1 246 \ | 247 1 \| 248 C 250 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 252 Suppose now that the link between S and A fails: 254 B 255 1 /| 256 / | 257 S A |1 258 \ | 259 1 \| 260 C 262 When it detects the failure of the link, A switches its next hop to B 263 (which is still advertising a route to S with metric 2), and 264 advertises a metric equal to 3, and then advertises a new route with 265 metric 3. This process of nodes changing selected neighbours and 266 increasing their metric continues until the advertised metric reaches 267 "infinity", a value larger than all the metrics that the routing 268 protocol is able to carry. 270 2.4. Feasibility Conditions 272 Bellman-Ford is a very robust algorithm: its convergence properties 273 are preserved when routers delay route acquisition or when they 274 discard some updates. Babel routers discard received route 275 announcements unless they can prove that accepting them cannot 276 possibly cause a routing loop. 278 More formally, we define a condition over route announcements, known 279 as the feasibility condition, that guarantees the absence of routing 280 loops whenever all routers ignore route updates that do not satisfy 281 the feasibility condition. In effect, this makes Bellman-Ford into a 282 family of routing algorithms, parameterised by the feasibility 283 condition. 285 Many different feasibility conditions are possible. For example, BGP 286 can be modelled as being a distance-vector protocol with a (rather 287 drastic) feasibility condition: a routing update is only accepted 288 when the receiving node's AS number is not included in the update's 289 AS-Path attribute (note that BGP's feasibility condition does not 290 ensure the absence of transitory "micro-loops" during reconvergence). 292 Another simple feasibility condition, used in Destination-Sequenced 293 Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand 294 Distance Vector (AODV) routing, stems from the following observation: 295 a routing loop can only arise after a router has switched to a route 296 with a larger metric than the route that it had previously selected. 297 Hence, one could decide that a route is feasible only when its metric 298 at the local node would be no larger than the metric of the currently 299 selected route, i.e., an announcement carrying a metric D(B) is 300 accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this 301 constraint, then the metric at every router is nonincreasing, and the 302 following invariant is always preserved: if A has selected B as its 303 successor, then D(B) < D(A), which implies that the forwarding graph 304 is loop-free. 306 Babel uses a slightly more refined feasibility condition, used in 307 EIGRP [DUAL]. Given a router A, define the feasibility distance of 308 A, written FD(A), as the smallest metric that A has ever advertised 309 for S to any of its neighbours. An update sent by a neighbour B of A 310 is feasible when the metric D(B) advertised by B is strictly smaller 311 than A's feasibility distance, i.e., when D(B) < FD(A). 313 It is easy to see that this latter condition is no more restrictive 314 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 315 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 316 Suppose now that A receives a DSDV-feasible update that advertises a 317 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 318 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 320 To see that it is strictly less restrictive, consider the following 321 diagram, where A has selected the route through B, and D(A) = FD(A) = 322 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 323 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 324 the currently selected route: 326 B 327 1 / \ 1 328 / \ 329 S A 330 \ / 331 1 \ / 4 332 C 334 To show that this feasibility condition still guarantees loop- 335 freedom, recall that at the time when A accepts an update from B, the 336 metric D(B) announced by B is no smaller than FD(B); since it is 337 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 338 property is preserved when A sends updates, it remains true at all 339 times, which ensures that the forwarding graph has no loops. 341 2.5. Solving Starvation: Sequencing Routes 343 Obviously, the feasibility conditions defined above cause starvation 344 when a router runs out of feasible routes. Consider the following 345 diagram, where both A and B have selected the direct route to S: 347 A 348 1 /| D(A) = 1 349 / | FD(A) = 1 350 S |1 351 \ | D(B) = 2 352 2 \| FD(B) = 2 353 B 355 Suppose now that the link between A and S breaks: 357 A 358 | 359 | FD(A) = 1 360 S |1 361 \ | D(B) = 2 362 2 \| FD(B) = 2 363 B 365 The only route available from A to S, the one that goes through B, is 366 not feasible: A suffers from a spurious starvation. 368 At this point, the whole network must be rebooted in order to solve 369 the starvation; this is essentially what EIGRP does when it performs 370 a global synchronisation of all the routers in the network with the 371 source (the "active" phase of EIGRP). 373 Babel reacts to starvation in a less drastic manner, by using 374 sequenced routes, a technique introduced by DSDV and adopted by AODV. 375 In addition to a metric, every route carries a sequence number, a 376 nondecreasing integer that is propagated unchanged through the 377 network and is only ever incremented by the source; a pair (s, m), 378 where s is a sequence number and m a metric, is called a distance. 380 A received update is feasible when either it is more recent than the 381 feasibility distance maintained by the receiving node, or it is 382 equally recent and the metric is strictly smaller. More formally, if 383 FD(A) = (s, m), then an update carrying the distance (s', m') is 384 feasible when either s' > s, or s = s' and m' < m. 386 Assuming the sequence number of S is 137, the diagram above becomes: 388 A 389 | 390 | FD(A) = (137, 1) 391 S |1 392 \ | D(B) = (137, 2) 393 2 \| FD(B) = (137, 2) 394 B 396 After S increases its sequence number, and the new sequence number is 397 propagated to B, we have: 399 A 400 | 401 | FD(A) = (137, 1) 402 S |1 403 \ | D(B) = (138, 2) 404 2 \| FD(B) = (138, 2) 405 B 407 at which point the route through B becomes feasible again. 409 Note that while sequence numbers are used for determining 410 feasibility, they are not necessarily used in route selection: a node 411 will normally ignore the sequence number when selecting a route 412 (Section 3.6). 414 2.6. Requests 416 In DSDV, the sequence number of a source is increased periodically. 417 A route becomes feasible again after the source increases its 418 sequence number, and the new sequence number is propagated through 419 the network, which may, in general, require a significant amount of 420 time. 422 Babel takes a different approach. When a node detects that it is 423 suffering from a potentially spurious starvation, it sends an 424 explicit request to the source for a new sequence number. This 425 request is forwarded hop by hop to the source, with no regard to the 426 feasibility condition. Upon receiving the request, the source 427 increases its sequence number and broadcasts an update, which is 428 forwarded to the requesting node. 430 Note that after a change in network topology not all such requests 431 will, in general, reach the source, as some will be sent over links 432 that are now broken. However, if the network is still connected, 433 then at least one among the nodes suffering from spurious starvation 434 has an (unfeasible) route to the source; hence, in the absence of 435 packet loss, at least one such request will reach the source. 436 (Resending requests a small number of times compensates for packet 437 loss.) 439 Since requests are forwarded with no regard to the feasibility 440 condition, they may, in general, be caught in a forwarding loop; this 441 is avoided by having nodes perform duplicate detection for the 442 requests that they forward. 444 2.7. Multiple Routers 446 The above discussion assumes that every prefix is originated by a 447 single router. In real networks, however, it is often necessary to 448 have a single prefix originated by multiple routers; for example, the 449 default route will be originated by all of the edge routers of a 450 routing domain. 452 Since synchronising sequence numbers between distinct routers is 453 problematic, Babel treats routes for the same prefix as distinct 454 entities when they are originated by different routers: every route 455 announcement carries the router-id of its originating router, and 456 feasibility distances are not maintained per prefix, but per source, 457 where a source is a pair of a router-id and a prefix. In effect, 458 Babel guarantees loop-freedom for the forwarding graph to every 459 source; since the union of multiple acyclic graphs is not in general 460 acyclic, Babel does not in general guarantee loop-freedom when a 461 prefix is originated by multiple routers, but any loops will be 462 broken in a time at most proportional to the diameter of the loop -- 463 as soon as an update has "gone around" the routing loop. 465 Consider for example the following diagram, where A has selected the 466 default route through S, and B has selected the one through S': 468 1 1 1 469 ::/0 -- S --- A --- B --- S' -- ::/0 471 Suppose that both default routes fail at the same time; then nothing 472 prevents A from switching to B, and B simultaneously switching to A. 473 However, as soon as A has successfully advertised the new route to B, 474 the route through A will become unfeasible for B. Conversely, as 475 soon as B will have advertised the route through A, the route through 476 B will become unfeasible for A. 478 In effect, the routing loop disappears at the latest when routing 479 information has gone around the loop. Since this process can be 480 delayed by lost packets, Babel makes certain efforts to ensure that 481 updates are sent reliably after a router-id change. 483 Additionally, after the routers have advertised the two routes, both 484 sources will be in their source tables, which will prevent them from 485 ever again participating in a routing loop involving routes from S 486 and S' (up to the source GC time, which, available memory permitting, 487 can be set to arbitrarily large values). 489 2.8. Overlapping Prefixes 491 In the above discussion, we have assumed that all prefixes are 492 disjoint, as is the case in flat ("mesh") routing. In practice, 493 however, prefixes may overlap: for example, the default route 494 overlaps with all of the routes present in the network. 496 After a route fails, it is not correct in general to switch to a 497 route that subsumes the failed route. Consider for example the 498 following configuration: 500 1 1 501 ::/0 -- A --- B --- C 503 Suppose that node C fails. If B forwards packets destined to C by 504 following the default route, a routing loop will form, and persist 505 until A learns of B's retraction of the direct route to C. Babel 506 avoids this pitfall by maintaining an "unreachable" route for a few 507 minutes after a route is retracted; the time for which such a route 508 must be maintained should be the worst-case propagation time of the 509 retraction of the route to C. 511 3. Protocol Operation 513 Every Babel speaker is assigned a router-id, which is an arbitrary 514 string of 8 octets that is assumed unique across the routing domain. 515 We suggest that router-ids should be assigned in modified EUI-64 516 format [ADDRARCH]. (As a matter of fact, the protocol encoding is 517 slightly more compact when router-ids are assigned in the same manner 518 as the IPv6 layer assigns host IDs.) 520 3.1. Message Transmission and Reception 522 Babel protocol packets are sent in the body of a UDP datagram. Each 523 Babel packet consists of one or more TLVs. 525 The source address of a Babel packet is always a unicast address, 526 link-local in the case of IPv6. Babel packets may be sent to a well- 527 known (link-local) multicast address (this is the usual case) or to a 528 (link-local) unicast address. In normal operation, a Babel speaker 529 sends both multicast and unicast packets to its neighbours. 531 With the exception of Hello TLVs and acknowledgements, all Babel TLVs 532 can be sent to either unicast or multicast addresses, and their 533 semantics does not depend on whether the destination was a unicast or 534 multicast address. Hence, a Babel speaker does not need to determine 535 the destination address of a packet that it receives in order to 536 interpret it. 538 A moderate amount of jitter is applied to packets sent by a Babel 539 speaker: outgoing TLVs are buffered and SHOULD be sent with a small 540 random delay. This is done for two purposes: it avoids 541 synchronisation of multiple Babel speakers across a network [JITTER], 542 and it allows for the aggregation of multiple TLVs into a single 543 packet. 545 The exact delay and amount of jitter applied to a packet depends on 546 whether it contains any urgent TLVs. Acknowledgement TLVs MUST be 547 sent before the deadline specified in the corresponding request. The 548 particular class of updates specified in Section 3.7.2 MUST be sent 549 in a timely manner. The particular class of request and update TLVs 550 specified in Section 3.8.2 SHOULD be sent in a timely manner. 552 3.2. Data Structures 554 Every Babel speaker maintains a number of data structures. 556 3.2.1. Sequence Number 558 A node's sequence number is a 16-bit integer that is included in 559 route updates sent for routes originated by this node. A node 560 increments its sequence number (modulo 2^16) whenever it receives a 561 request for a new sequence number (Section 3.8.1.2). 563 A node SHOULD NOT increment its sequence number (seqno) 564 spontaneously, since increasing seqnos makes it less likely that 565 other nodes will have feasible alternate routes when their selected 566 routes fail. 568 3.2.2. The Interface Table 570 The interface table contains the list of interfaces on which the node 571 speaks the Babel protocol. Every interface table entry contains the 572 interface's Hello seqno, a 16-bit integer that is sent with each 573 Hello TLV on this interface and is incremented (modulo 2^16) whenever 574 a Hello is sent. (Note that an interface's Hello seqno is unrelated 575 to the node's seqno.) 577 There are two timers associated with each interface table entry -- 578 the Hello timer, which governs the sending of periodic Hello and IHU 579 packets, and the update timer, which governs the sending of periodic 580 route updates. 582 3.2.3. The Neighbour Table 584 The neighbour table contains the list of all neighbouring interfaces 585 from which a Babel packet has been recently received. The neighbour 586 table is indexed by pairs of the form (interface, address), and every 587 neighbour table entry contains the following data: 589 o the local node's interface over which this neighbour is reachable; 591 o the address of the neighbouring interface; 593 o a history of recently received Hello packets from this neighbour; 594 this can, for example, be a sequence of n bits, for some small 595 value n, indicating which of the n hellos most recently sent by 596 this neighbour have been received by the local node; 598 o the "transmission cost" value from the last IHU packet received 599 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 600 hold timer for this neighbour has expired; 602 o the neighbour's expected Hello sequence number, an integer modulo 603 2^16. 605 There are two timers associated with each neighbour entry -- the 606 hello timer, which is initialised from the interval value carried by 607 Hello TLVs, and the IHU timer, which is initialised to a small 608 multiple of the interval carried in IHU TLVs. 610 Note that the neighbour table is indexed by IP addresses, not by 611 router-ids: neighbourship is a relationship between interfaces, not 612 between nodes. Therefore, two nodes with multiple interfaces can 613 participate in multiple neighbourship relationships, a fairly common 614 situation when wireless nodes with multiple radios are involved. 616 3.2.4. The Source Table 618 The source table is used to record feasibility distances. It is 619 indexed by triples of the form (prefix, plen, router-id), and every 620 source table entry contains the following data: 622 o the prefix (prefix, plen), where plen is the prefix length, that 623 this entry applies to; 625 o the router-id of a router originating this prefix; 627 o a pair (seqno, metric), this source's feasibility distance. 629 There is one timer associated with each entry in the source table -- 630 the source garbage-collection timer. It is initialised to a time on 631 the order of minutes and reset as specified in Section 3.7.3. 633 3.2.5. The Route Table 635 The route table contains the routes known to this node. It is 636 indexed by triples of the form (prefix, plen, neighbour), and every 637 route table entry contains the following data: 639 o the source (prefix, plen, router-id) for which this route is 640 advertised; 642 o the neighbour that advertised this route; 644 o the metric with which this route was advertised by the neighbour, 645 or FFFF hexadecimal (infinity) for a recently retracted route; 647 o the sequence number with which this route was advertised; 649 o the next-hop address of this route; 651 o a boolean flag indicating whether this route is selected, i.e., 652 whether it is currently being used for forwarding and is being 653 advertised. 655 There is one timer associated with each route table entry -- the 656 route expiry timer. It is initialised and reset as specified in 657 Section 3.5.4. 659 3.2.6. The Table of Pending Requests 661 The table of pending requests contains a list of seqno requests that 662 the local node has sent (either because they have been originated 663 locally, or because they were forwarded) and to which no reply has 664 been received yet. This table is indexed by prefixes, and every 665 entry in this table contains the following data: 667 o the prefix, router-id, and seqno being requested; 668 o the neighbour, if any, on behalf of which we are forwarding this 669 request; 671 o a small integer indicating the number of times that this request 672 will be resent if it remains unsatisfied. 674 There is one timer associated with each pending request; it governs 675 both the resending of requests and their expiry. 677 3.3. Acknowledged Packets 679 A Babel speaker may request that any neighbour receiving a given 680 packet reply with an explicit acknowledgement within a given time. 681 While the use of acknowledgement requests is optional, every Babel 682 speaker MUST be able to reply to such a request. 684 An acknowledgement MUST be sent to a unicast destination. On the 685 other hand, acknowledgement requests may be sent to either unicast or 686 multicast destinations, in which case they request an acknowledgement 687 from all of the receiving nodes. 689 When to request acknowledgements is a matter of local policy; the 690 simplest strategy is to never request acknowledgements and to rely on 691 periodic updates to ensure that any reachable routes are eventually 692 propagated throughout the routing domain. For increased efficiency, 693 we suggest that acknowledged packets should be used in order to send 694 urgent updates (Section 3.7.2) when the number of neighbours on a 695 given interface is small. Since Babel is designed to deal gracefully 696 with packet loss on unreliable media, sending all packets with 697 acknowledgement requests is not necessary, and not even recommended, 698 as the acknowledgements cause additional traffic and may force 699 additional Address Resolution Protocol (ARP) or Neighbour Discovery 700 exchanges. 702 3.4. Neighbour Acquisition 704 Neighbour acquisition is the process by which a Babel node discovers 705 the set of neighbours heard over each of its interfaces and 706 ascertains bidirectional reachability. On unreliable media, 707 neighbour acquisition additionally provides some statistics that MAY 708 be used in link quality computation. 710 3.4.1. Reverse Reachability Detection 712 Every Babel node sends periodic Hellos over each of its interfaces. 713 Each Hello TLV carries an increasing (modulo 2^16) sequence number 714 and the interval between successive periodic packets sent on this 715 particular interface. 717 In addition to the periodic Hello packets, a node MAY send 718 unscheduled Hello packets, e.g., to accelerate link cost estimation 719 when a new neighbour is discovered, or when link conditions have 720 suddenly changed. 722 A node MAY change its Hello interval. The Hello interval MAY be 723 decreased at any time; it SHOULD NOT be increased, except immediately 724 before sending a Hello packet. (Equivalently, a node SHOULD send an 725 unscheduled Hello immediately after increasing its Hello interval.) 727 How to deal with received Hello TLVs and what statistics to maintain 728 are considered local implementation matters; typically, a node will 729 maintain some sort of history of recently received Hellos. A 730 possible algorithm is described in Appendix A.1. 732 After receiving a Hello, or determining that it has missed one, the 733 node recomputes the association's cost (Section 3.4.3) and runs the 734 route selection procedure (Section 3.6). 736 3.4.2. Bidirectional Reachability Detection 738 In order to establish bidirectional reachability, every node sends 739 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 740 IHUs carry an explicit interval value, they MAY be sent less often 741 than Hellos in order to reduce the amount of routing traffic in dense 742 networks; in particular, they SHOULD be sent less often than Hellos 743 over links with little packet loss. While IHUs are conceptually 744 unicast, they SHOULD be sent to a multicast address in order to avoid 745 an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 746 in a single packet. 748 In addition to the periodic IHUs, a node MAY, at any time, send an 749 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 750 interval, and it MAY increase its IHU interval immediately before 751 sending an IHU. 753 Every IHU TLV contains two pieces of data: the link's rxcost 754 (reception cost) from the sender's perspective, used by the neighbour 755 for computing link costs (Section 3.4.3), and the interval between 756 periodic IHU packets. A node receiving an IHU updates the value of 757 the sending neighbour's txcost (transmission cost), from its 758 perspective, to the value contained in the IHU, and resets this 759 neighbour's IHU timer to a small multiple of the value received in 760 the IHU. 762 When a neighbour's IHU timer expires, its txcost is set to infinity. 764 After updating a neighbour's txcost, the receiving node recomputes 765 the neighbour's cost (Section 3.4.3) and runs the route selection 766 procedure (Section 3.6). 768 3.4.3. Cost Computation 770 A neighbourship association's link cost is computed from the values 771 maintained in the neighbour table -- namely, the statistics kept in 772 the neighbour table about the reception of Hellos, and the txcost 773 computed from received IHU packets. 775 For every neighbour, a Babel node computes a value known as this 776 neighbour's rxcost. This value is usually derived from the Hello 777 history, which may be combined with other data, such as statistics 778 maintained by the link layer. The rxcost is sent to a neighbour in 779 each IHU. 781 How the txcost and rxcost are combined in order to compute a link's 782 cost is a matter of local policy; as far as Babel's correctness is 783 concerned, only the following conditions MUST be satisfied: 785 o the cost is strictly positive; 787 o if no hellos were received recently, then the cost is infinite; 789 o if the txcost is infinite, then the cost is infinite. 791 Note that while this document does not constrain cost computation any 792 further, not all cost computation strategies will give good results. 793 We give a few examples of strategies for computing a link's cost that 794 are known to work well in practice in Appendix A.2. 796 3.5. Routing Table Maintenance 798 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 799 seqno, metric), where (prefix, plen) is the prefix for which a route 800 is being advertised, router-id is the router-id of the router 801 originating this update, seqno is a nondecreasing (modulo 2^16) 802 integer that carries the originating router seqno, and metric is the 803 announced metric. 805 Before being accepted, an update is checked against the feasibility 806 condition (Section 3.5.1), which ensures that the route does not 807 create a routing loop. If the feasibility condition is not 808 satisfied, the update is either ignored or treated as a retraction, 809 depending on some other conditions (Section 3.5.4). If the 810 feasibility condition is satisfied, then the update cannot possibly 811 cause a routing loop, and the update is accepted. 813 3.5.1. The Feasibility Condition 815 The feasibility condition is applied to all received updates. The 816 feasibility condition compares the metric in the received update with 817 the metrics of the updates previously sent by the receiving node; 818 updates with finite metrics large enough to cause a loop are 819 discarded. 821 A feasibility distance is a pair (seqno, metric), where seqno is an 822 integer modulo 2^16 and metric is a positive integer. Feasibility 823 distances are compared lexicographically, with the first component 824 inverted: we say that a distance (seqno, metric) is strictly better 825 than a distance (seqno', metric'), written 827 (seqno, metric) < (seqno', metric') 829 when 831 seqno > seqno' or (seqno = seqno' and metric < metric') 833 where sequence numbers are compared modulo 2^16. 835 Given a source (p, plen, id), a node's feasibility distance for this 836 source is the minimum, according to the ordering defined above, of 837 the distances of all the finite updates ever sent by this particular 838 node for the prefix (p, plen) carrying the router-id id. Feasibility 839 distances are maintained in the source table; the exact procedure is 840 given in Section 3.7.3. 842 A received update is feasible when either it is a retraction (its 843 metric is FFFF hexadecimal), or the advertised distance is strictly 844 better, in the sense defined above, than the feasibility distance for 845 the corresponding source. More precisely, a route advertisement 846 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 847 feasible if one of the following conditions holds: 849 o metric is infinite; or 851 o no entry exists in the source table indexed by (id, prefix, plen); 852 or 854 o an entry (prefix, plen, router-id, seqno', metric') exists in the 855 source table, and either 857 * seqno' < seqno or 859 * seqno = seqno' and metric < metric'. 861 Note that the feasibility condition considers the metric advertised 862 by the neighbour, not the route's metric; hence, a fluctuation in a 863 neighbour's cost cannot render a selected route unfeasible. 865 3.5.2. Metric Computation 867 A route's metric is computed from the metric advertised by the 868 neighbour and the neighbour's link cost. Just like cost computation, 869 metric computation is considered a local policy matter; as far as 870 Babel is concerned, the function M(c, m) used for computing a metric 871 from a locally computed link cost and the metric advertised by a 872 neighbour MUST only satisfy the following conditions: 874 o if c is infinite, then M(c, m) is infinite; 876 o M is strictly monotonic: M(c, m) > m. 878 Additionally, the metric SHOULD satisfy the following condition: 880 o M is isotonic: if m <= m', then M(c, m) <= M(c, m'). 882 Note that while strict monotonicity is essential to the integrity of 883 the network (persistent routing loops may appear if it is not 884 satisfied), isotonicity is not: if it is not satisfied, Babel will 885 still converge to a locally optimal routing table, but might not 886 reach a global optimum (in fact, such a global optimum may not even 887 exist). 889 As with cost computation, not all strategies for computing route 890 metrics will give good results. In particular, some metrics are more 891 likely than others to lead to routing instabilities (route flapping). 892 In Appendix A.3, we give a number of examples of strictly monotonic, 893 isotonic routing metrics that are known to work well in practice. 895 3.5.3. Encoding of Updates 897 In a large network, the bulk of Babel traffic consists of route 898 updates; hence, some care has been given to encoding them 899 efficiently. An Update TLV itself only contains the prefix, seqno, 900 and metric, while the next hop is derived either from the network- 901 layer source address of the packet or from an explicit Next Hop TLV 902 in the same packet. The router-id is derived from a separate Router- 903 Id TLV in the same packet, which optimises the case when multiple 904 updates are sent with the same router-id. 906 Additionally, a prefix of the advertised prefix can be omitted in an 907 Update TLV, in which case it is copied from a previous Update TLV in 908 the same packet -- this is known as address compression [PACKETBB]. 910 Finally, as a special optimisation for the case when a router-id 911 coincides with the interface-id part of an IPv6 address, the router- 912 id can optionally be derived from the low-order bits of the 913 advertised prefix. 915 The encoding of updates is described in detail in Section 4.4. 917 3.5.4. Route Acquisition 919 When a Babel node receives an update (id, prefix, seqno, metric) from 920 a neighbour neigh with a link cost value equal to cost, it checks 921 whether it already has a routing table entry indexed by (neigh, id, 922 prefix). 924 If no such entry exists: 926 o if the update is unfeasible, it is ignored; 928 o if the metric is infinite (the update is a retraction), the update 929 is ignored; 931 o otherwise, a new route table entry is created, indexed by (neigh, 932 id, prefix), with seqno equal to seqno and an advertised metric 933 equal to the metric carried by the update. 935 If such an entry exists: 937 o if the entry is currently installed and the update is unfeasible, 938 then the behaviour depends on whether the router-ids of the two 939 entries match. If the router-ids are different, the update is 940 treated as though it were a retraction (i.e., as though the metric 941 were FFFF hexadecimal). If the router-ids are equal, the update 942 is ignored; 944 o otherwise (i.e., if either the update is feasible or the entry is 945 not currently installed), then the entry's sequence number, 946 advertised metric, metric, and router-id are updated and, unless 947 the advertised metric is infinite, the route's expiry timer is 948 reset to a small multiple of the Interval value included in the 949 update. 951 When a route's expiry timer triggers, the behaviour depends on 952 whether the route's metric is finite. If the metric is finite, it is 953 set to infinity and the expiry timer is reset. If the metric is 954 already infinite, the route is flushed from the route table. 956 After the routing table is updated, the route selection procedure 957 (Section 3.6) is run. 959 3.5.5. Hold Time 961 When a prefix p is retracted, because all routes are unfeasible, too 962 old, or have an infinite metric, and a shorter prefix p' that covers 963 p is reachable, p' cannot in general be used for routing packets 964 destined to p without running the risk of creating a routing loop 965 (Section 2.8). 967 To avoid this issue, whenever a prefix is retracted, a routing table 968 entry with infinite metric is maintained as described in 969 Section 3.5.4 above, and packets destined for that prefix MUST NOT be 970 forwarded by following a route for a shorter prefix. The infinite 971 metric entry is maintained until it is superseded by a feasible 972 update; if no such update arrives within the route hold time, the 973 entry is flushed. 975 3.6. Route Selection 977 Route selection is the process by which a single route for a given 978 prefix is selected to be used for forwarding packets and to be re- 979 advertised to a node's neighbours. 981 Babel is designed to allow flexible route selection policies. As far 982 as the protocol's correctness is concerned, the route selection 983 policy MUST only satisfy the following properties: 985 o a route with infinite metric (a retracted route) is never 986 selected; 988 o an unfeasible route is never selected. 990 Note, however, that Babel does not naturally guarantee the stability 991 of routing, and configuring conflicting route selection policies on 992 different routers may lead to persistent route oscillation. 994 Defining a good route selection policy for Babel is an open research 995 problem. Route selection can take into account multiple mutually 996 contradictory criteria; in roughly decreasing order of importance, 997 these are: 999 o routes with a small metric should be preferred over routes with a 1000 large metric; 1002 o switching router-ids should be avoided; 1004 o routes through stable neighbours should be preferred over routes 1005 through unstable ones; 1007 o stable routes should be preferred over unstable ones; 1009 o switching next hops should be avoided. 1011 A simple strategy is to choose the feasible route with the smallest 1012 metric, with a small amount of hysteresis applied to avoid switching 1013 router-ids. 1015 After the route selection procedure is run, triggered updates 1016 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1018 3.7. Sending Updates 1020 A Babel speaker advertises to its neighbours its set of selected 1021 routes. Normally, this is done by sending one or more multicast 1022 packets containing Update TLVs on all of its connected interfaces; 1023 however, on link technologies where multicast is significantly more 1024 expensive than unicast, a node MAY choose to send multiple copies of 1025 updates in unicast packets when the number of neighbours is small. 1027 Additionally, in order to ensure that any black-holes are reliably 1028 cleared in a timely manner, a Babel node sends retractions (updates 1029 with an infinite metric) for any recently retracted prefixes. 1031 If an update is for a route injected into the Babel domain by the 1032 local node (e.g., the address of a local interface, the prefix of a 1033 directly attached network, or redistributed from a different routing 1034 protocol), the router-id is set to the local id, the metric is set to 1035 some arbitrary finite value (typically 0), and the seqno is set to 1036 the local router's sequence number. 1038 If an update is for a route learned from another Babel speaker, the 1039 router-id and sequence number are copied from the routing table 1040 entry, and the metric is computed as specified in Section 3.5.2. 1042 3.7.1. Periodic Updates 1044 Every Babel speaker periodically advertises all of its selected 1045 routes on all of its interfaces, including any recently retracted 1046 routes. Since Babel doesn't suffer from routing loops (there is no 1047 "counting to infinity") and relies heavily on triggered updates 1048 (Section 3.7.2), this full dump only needs to happen infrequently. 1050 3.7.2. Triggered Updates 1052 In addition to the periodic routing updates, a Babel speaker sends 1053 unscheduled, or triggered, updates in order to inform its neighbours 1054 of a significant change in the network topology. 1056 A change of router-id for the selected route to a given prefix may be 1057 indicative of a routing loop in formation; hence, a node MUST send a 1058 triggered update in a timely manner whenever it changes the selected 1059 router-id for a given destination. Additionally, it SHOULD make a 1060 reasonable attempt at ensuring that all neighbours receive this 1061 update. 1063 There are two strategies for ensuring that. If the number of 1064 neighbours is small, then it is reasonable to send the update 1065 together with an acknowledgement request; the update is resent until 1066 all neighbours have acknowledged the packet, up to some number of 1067 times. If the number of neighbours is large, however, requesting 1068 acknowledgements from all of them might cause a non-negligible amount 1069 of network traffic; in that case, it may be preferable to simply 1070 repeat the update some reasonable number of times (say, 5 for 1071 wireless and 2 for wired links). 1073 A route retraction is somewhat less worrying: if the route retraction 1074 doesn't reach all neighbours, a black-hole might be created, which, 1075 unlike a routing loop, does not endanger the integrity of the 1076 network. When a route is retracted, a node SHOULD send a triggered 1077 update and SHOULD make a reasonable attempt at ensuring that all 1078 neighbours receive this retraction. 1080 Finally, a node MAY send a triggered update when the metric for a 1081 given prefix changes in a significant manner, either due to a 1082 received update or because a link cost has changed. A node SHOULD 1083 NOT send triggered updates for other reasons, such as when there is a 1084 minor fluctuation in a route's metric, when the selected next hop 1085 changes, or to propagate a new sequence number (except to satisfy a 1086 request, as specified in Section 3.8). 1088 3.7.3. Maintaining Feasibility Distances 1090 Before sending an update (prefix, plen, router-id, seqno, metric) 1091 with finite metric (i.e., not a route retraction), a Babel node 1092 updates the feasibility distance maintained in the source table. 1093 This is done as follows. 1095 If no entry indexed by (prefix, plen, router-id) exists in the source 1096 table, then one is created with value (prefix, plen, router-id, 1097 seqno, metric). 1099 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1100 it is updated as follows: 1102 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1103 o if seqno = seqno' and metric' > metric, then metric' := metric; 1105 o otherwise, nothing needs to be done. 1107 The garbage-collection timer for the modified entry is then reset. 1108 Note that the garbage-collection timer is not reset when a retraction 1109 is sent. 1111 3.7.4. Split Horizon 1113 When running over a transitive, symmetric link technology, e.g., a 1114 point-to-point link or a wired LAN technology such as Ethernet, a 1115 Babel node SHOULD use an optimisation known as split horizon. When 1116 split horizon is used on a given interface, a routing update is not 1117 sent on this particular interface when the advertised route was 1118 learnt from a neighbour over the same interface. 1120 Split horizon SHOULD NOT be applied to an interface unless the 1121 interface is known to be symmetric and transitive; in particular, 1122 split horizon is not applicable to decentralised wireless link 1123 technologies (e.g., IEEE 802.11 in ad hoc mode). 1125 3.8. Explicit Route Requests 1127 In normal operation, a node's routing table is populated by the 1128 regular and triggered updates sent by its neighbours. Under some 1129 circumstances, however, a node sends explicit requests to cause a 1130 resynchronisation with the source after a mobility event or to 1131 prevent a route from spuriously expiring. 1133 The Babel protocol provides two kinds of explicit requests: route 1134 requests, which simply request an update for a given prefix, and 1135 seqno requests, which request an update for a given prefix with a 1136 specific sequence number. The former are never forwarded; the latter 1137 are forwarded if they cannot be satisfied by a neighbour. 1139 3.8.1. Handling Requests 1141 Upon receiving a request, a node either forwards the request or sends 1142 an update in reply to the request, as described in the following 1143 sections. If this causes an update to be sent, the update is either 1144 sent to a multicast address on the interface on which the request was 1145 received, or to the unicast address of the neighbour that sent the 1146 update. 1148 The exact behaviour is different for route requests and seqno 1149 requests. 1151 3.8.1.1. Route Requests 1153 When a node receives a route request for a prefix (prefix, plen), it 1154 checks its route table for a selected route to this exact prefix. If 1155 such a route exists, it MUST send an update; if such a route does 1156 not, it MUST send a retraction for that prefix. 1158 When a node receives a wildcard route request, it SHOULD send a full 1159 routing table dump. 1161 3.8.1.2. Seqno Requests 1163 When a node receives a seqno request for a given router-id and 1164 sequence number, it checks whether its routing table contains a 1165 selected entry for that prefix; if no such entry exists, or the entry 1166 has infinite metric, it ignores the request. 1168 If a selected route for the given prefix exists, and either the 1169 router-ids are different or the router-ids are equal and the entry's 1170 sequence number is no smaller than the requested sequence number, it 1171 MUST send an update for the given prefix. 1173 If the router-ids match but the requested seqno is larger than the 1174 route entry's, the node compares the router-id against its own 1175 router-id. If the router-id is its own, then it increases its 1176 sequence number by 1 and sends an update. A node MUST NOT increase 1177 its sequence number by more than 1 in response to a route request. 1179 If the requested router-id is not its own, the received request's hop 1180 count is 2 or more, and the node has a route (not necessarily a 1181 feasible one) for the requested prefix that does not use the 1182 requestor as a next hop, the node SHOULD forward the request. It 1183 does so by decreasing the hop count and sending the request in a 1184 unicast packet destined to a neighbour that advertises the given 1185 prefix (not necessarily the selected neighbour) and that is distinct 1186 from the neighbour from which the request was received. 1188 A node SHOULD maintain a list of recently forwarded requests and 1189 forward the reply in a timely manner. A node SHOULD compare every 1190 incoming request against its list of recently forwarded requests and 1191 avoid forwarding it if it is redundant. 1193 Since the request-forwarding mechanism does not necessarily obey the 1194 feasibility condition, it may get caught in routing loops; hence, 1195 requests carry a hop count to limit the time for which they remain in 1196 the network. However, since requests are only ever forwarded as 1197 unicast packets, the initial hop count need not be kept particularly 1198 low, and performing an expanding horizon search is not necessary. A 1199 request MUST NOT be forwarded to a multicast address, and it MUST be 1200 forwarded to a single neighbour only. 1202 3.8.2. Sending Requests 1204 A Babel node MAY send a route or seqno request at any time, to a 1205 multicast or a unicast address; there is only one case when 1206 originating requests is required (Section 3.8.2.1). 1208 3.8.2.1. Avoiding Starvation 1210 When a route is retracted or expires, a Babel node usually switches 1211 to another feasible route for the same prefix. It may be the case, 1212 however, that no such routes are available. 1214 A node that has lost all feasible routes to a given destination MUST 1215 send a seqno request. The router-id of the request is set to the 1216 router-id of the route that it has just lost, and the requested seqno 1217 is the value contained in the source table, plus 1. 1219 Such a request SHOULD be multicast over all of the node's attached 1220 interfaces. Similar requests will be sent by other nodes that are 1221 affected by the route's loss and will be forwarded by neighbouring 1222 nodes up to the source. If the network is connected, and there is no 1223 packet loss, this will result in a route being advertised with a new 1224 sequence number. (Note that, due to duplicate suppression, only a 1225 small number of such requests will actually reach the source.) 1227 In order to compensate for packet loss, a node SHOULD repeat such a 1228 request a small number of times if no route becomes feasible within a 1229 short time. Under heavy packet loss, however, all such requests may 1230 be lost; in that case, the second mechanism in the next section will 1231 eventually ensure that a new seqno is received. 1233 3.8.2.2. Dealing with Unfeasible Updates 1235 When a route's metric increases, a node might receive an unfeasible 1236 update for a route that it has currently selected. As specified in 1237 Section 3.5.1, the receiving node will either ignore the update or 1238 retract the route. 1240 In order to keep routes from spuriously expiring because they have 1241 become unfeasible, a node SHOULD send a unicast seqno request 1242 whenever it receives an unfeasible update for a route that is 1243 currently selected. The requested sequence number is computed from 1244 the source table as above. 1246 Additionally, a node SHOULD send a unicast seqno request whenever it 1247 receives an unfeasible update from a currently unselected neighbour 1248 that is "good enough", i.e., that would lead to the received route 1249 becoming selected were it feasible. 1251 3.8.2.3. Preventing Routes from Expiring 1253 In normal operation, a route's expiry timer should never trigger: 1254 since a route's hold time is computed from an explicit interval 1255 included in Update TLVs, a new update should arrive in time to 1256 prevent a route from expiring. 1258 In the presence of packet loss, however, it may be the case that no 1259 update is successfully received for an extended period of time, 1260 causing a route to expire. In order to avoid such spurious expiry, 1261 shortly before a selected route expires, a Babel node SHOULD send a 1262 unicast route request to the neighbour that advertised this route; 1263 since nodes always send retractions in response to non-wildcard route 1264 requests (Section 3.8.1.1), this will usually result in either the 1265 route being refreshed or a retraction being received. 1267 3.8.2.4. Acquiring New Neighbours 1269 In order to speed up convergence after a mobility event, a node MAY 1270 send a unicast wildcard request after acquiring a new neighbour. 1271 Additionally, a node MAY send a small number of multicast wildcard 1272 requests shortly after booting. 1274 4. Protocol Encoding 1276 A Babel packet is sent as the body of a UDP datagram, with network- 1277 layer hop count set to 1, destined to a well-known multicast address 1278 or to a unicast address, over IPv4 or IPv6; in the case of IPv6, 1279 these addresses are link-local. Both the source and destination UDP 1280 port are set to a well-known port number. A Babel packet MUST be 1281 silently ignored unless its source address is either a link-local 1282 IPv6 address, or an IPv4 address belonging to the local network, and 1283 its source port is the well-known Babel port. Babel packets MUST NOT 1284 be sent as IPv6 Jumbograms. 1286 In order to minimise the number of packets being sent while avoiding 1287 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1288 the size of the packets it sends, up to the outgoing interface's MTU 1289 adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets 1290 for UDP/IPv6). It MUST NOT send packets larger than the attached 1291 interface's MTU (adjusted for lower-layer headers) or 512 octets, 1292 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1293 layer headers. Every Babel speaker MUST be able to receive packets 1294 that are as large as any attached interface's MTU (adjusted for 1295 lower-layer headers) or 512 octets, whichever is larger. 1297 In order to avoid global synchronisation of a Babel network and to 1298 aggregate multiple TLVs into large packets, a Babel node MUST buffer 1299 every TLV and delay sending a UDP packet by a small, randomly chosen 1300 delay [JITTER]. In order to allow accurate computation of packet 1301 loss rates, this delay MUST NOT be larger than half the advertised 1302 Hello interval. 1304 4.1. Data Types 1306 4.1.1. Interval 1308 Relative times are carried as 16-bit values specifying a number of 1309 centiseconds (hundredths of a second). This allows times up to 1310 roughly 11 minutes with a granularity of 10ms, which should cover all 1311 reasonable applications of Babel. 1313 4.1.2. Router-Id 1315 A router-id is an arbitrary 8-octet value. Router-ids SHOULD be 1316 assigned in modified EUI-64 format [ADDRARCH]. 1318 4.1.3. Address 1320 Since the bulk of the protocol is taken by addresses, multiple ways 1321 of encoding addresses are defined. Additionally, a common subnet 1322 prefix may be omitted when multiple addresses are sent in a single 1323 packet -- this is known as address compression [PACKETBB]. 1325 Address encodings: 1327 o AE 0: wildcard address. The value is 0 octets long. 1329 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1331 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1333 o AE 3: link-local IPv6 address. The value is 8 octets long, a 1334 prefix of fe80::/64 is implied. 1336 The address family of an address is either IPv4 or IPv6; it is 1337 undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. 1339 4.1.4. Prefixes 1341 A network prefix is encoded just like a network address, but it is 1342 stored in the smallest number of octets that are enough to hold the 1343 significant bits (up to the prefix length). 1345 4.2. Packet Format 1347 A Babel packet consists of a 4-octet header, followed by a sequence 1348 of TLVs. 1350 0 1 2 3 1351 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 1352 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1353 | Magic | Version | Body length | 1354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1355 | Packet Body ... 1356 +-+-+-+-+-+-+-+-+-+-+-+-+- 1358 Fields : 1360 Magic The arbitrary but carefully chosen value 42 (decimal); 1361 packets with a first octet different from 42 MUST be 1362 silently ignored. 1364 Version This document specifies version 2 of the Babel protocol. 1365 Packets with a second octet different from 2 MUST be 1366 silently ignored. 1368 Body length The length in octets of the body following the packet 1369 header. 1371 Body The packet body; a sequence of TLVs. 1373 Any data following the body MUST be silently ignored. 1375 4.3. TLV Format 1377 With the exception of Pad1, all TLVs have the following structure: 1379 0 1 2 3 1380 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 1381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1382 | Type | Length | Body... 1383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1385 Fields : 1387 Type The type of the TLV. 1389 Length The length of the body, exclusive of the Type and Length 1390 fields. If the body is longer than the expected length of 1391 a given type of TLV, any extra data MUST be silently 1392 ignored. 1394 Body The TLV body, the interpretation of which depends on the 1395 type. 1397 TLVs with an unknown type value MUST be silently ignored. 1399 4.4. Details of Specific TLVs 1401 4.4.1. Pad1 1403 0 1404 0 1 2 3 4 5 6 7 1405 +-+-+-+-+-+-+-+-+ 1406 | Type = 0 | 1407 +-+-+-+-+-+-+-+-+ 1409 Fields : 1411 Type Set to 0 to indicate a Pad1 TLV. 1413 This TLV is silently ignored on reception. 1415 4.4.2. PadN 1417 0 1 2 3 1418 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 1419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1420 | Type = 1 | Length | MBZ... 1421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1423 Fields : 1425 Type Set to 1 to indicate a PadN TLV. 1427 Length The length of the body, exclusive of the Type and Length 1428 fields. 1430 MBZ Set to 0 on transmission. 1432 This TLV is silently ignored on reception. 1434 4.4.3. Acknowledgement Request 1436 0 1 2 3 1437 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 1438 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1439 | Type = 2 | Length | Reserved | 1440 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1441 | Nonce | Interval | 1442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1444 This TLV requests that the receiver send an Acknowledgement TLV 1445 within the number of centiseconds specified by the Interval field. 1447 Fields : 1449 Type Set to 2 to indicate an Acknowledgement Request TLV. 1451 Length The length of the body, exclusive of the Type and Length 1452 fields. 1454 Reserved Sent as 0 and MUST be ignored on reception. 1456 Nonce An arbitrary value that will be echoed in the receiver's 1457 Acknowledgement TLV. 1459 Interval A time interval in centiseconds after which the sender will 1460 assume that this packet has been lost. This MUST NOT be 0. 1461 The receiver MUST send an acknowledgement before this time 1462 has elapsed (with a margin allowing for propagation time). 1464 4.4.4. Acknowledgement 1466 0 1 2 3 1467 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 1468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1469 | Type = 3 | Length | Nonce | 1470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1472 This TLV is sent by a node upon receiving an Acknowledgement Request. 1474 Fields : 1476 Type Set to 3 to indicate an Acknowledgement TLV. 1478 Length The length of the body, exclusive of the Type and Length 1479 fields. 1481 Nonce Set to the Nonce value of the Acknowledgement Request that 1482 prompted this Acknowledgement. 1484 Since nonce values are not globally unique, this TLV MUST be sent to 1485 a unicast address. 1487 4.4.5. Hello 1489 0 1 2 3 1490 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 1491 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1492 | Type = 4 | Length | Reserved | 1493 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1494 | Seqno | Interval | 1495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1497 This TLV is used for neighbour discovery and for determining a link's 1498 reception cost. 1500 Fields : 1502 Type Set to 4 to indicate a Hello TLV. 1504 Length The length of the body, exclusive of the Type and Length 1505 fields. 1507 Reserved Sent as 0 and MUST be ignored on reception. 1509 Seqno The value of the sending node's Hello seqno for this 1510 interface. 1512 Interval An upper bound, expressed in centiseconds, on the time 1513 after which the sending node will send a new Hello TLV. 1514 This MUST NOT be 0. 1516 Since there is a single seqno counter for all the Hellos sent by a 1517 given node over a given interface, this TLV MUST be sent to a 1518 multicast destination. In order to avoid large discontinuities in 1519 link quality, multiple Hello TLVs SHOULD NOT be sent in the same 1520 packet. 1522 4.4.6. IHU 1523 0 1 2 3 1524 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 1525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1526 | Type = 5 | Length | AE | Reserved | 1527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1528 | Rxcost | Interval | 1529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1530 | Address... 1531 +-+-+-+-+-+-+-+-+-+-+-+- 1533 An IHU ("I Heard You") TLV is used for confirming bidirectional 1534 reachability and carrying a link's transmission cost. 1536 Fields : 1538 Type Set to 5 to indicate an IHU TLV. 1540 Length The length of the body, exclusive of the Type and Length 1541 fields. 1543 AE The encoding of the Address field. This should be 1 or 3 1544 in most cases. As an optimisation, it MAY be 0 if the TLV 1545 is sent to a unicast address, if the association is over a 1546 point-to-point link, or when bidirectional reachability is 1547 ascertained by means outside of the Babel protocol. 1549 Reserved Sent as 0 and MUST be ignored on reception. 1551 Rxcost The rxcost according to the sending node of the interface 1552 whose address is specified in the Address field. The value 1553 FFFF hexadecimal (infinity) indicates that this interface 1554 is unreachable. 1556 Interval An upper bound, expressed in centiseconds, on the time 1557 after which the sending node will send a new IHU; this MUST 1558 NOT be 0. The receiving node will use this value in order 1559 to compute a hold time for this symmetric association. 1561 Address The address of the destination node, in the format 1562 specified by the AE field. Address compression is not 1563 allowed. 1565 Conceptually, an IHU is destined to a single neighbour. However, IHU 1566 TLVs contain an explicit destination address, and it SHOULD be sent 1567 to a multicast address, as this allows aggregation of IHUs destined 1568 to distinct neighbours into a single packet and avoids the need for 1569 an ARP or Neighbour Discovery exchange when a neighbour is not being 1570 used for data traffic. 1572 IHU TLVs with an unknown value for the AE field MUST be silently 1573 ignored. 1575 4.4.7. Router-Id 1577 0 1 2 3 1578 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 1579 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1580 | Type = 6 | Length | Reserved | 1581 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1582 | | 1583 + Router-Id + 1584 | | 1585 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1587 A Router-Id TLV establishes a router-id that is implied by subsequent 1588 Update TLVs. 1590 Fields : 1592 Type Set to 6 to indicate a Router-Id TLV. 1594 Length The length of the body, exclusive of the Type and Length 1595 fields. 1597 Reserved Sent as 0 and MUST be ignored on reception. 1599 Router-Id The router-id for routes advertised in subsequent Update 1600 TLVs 1602 4.4.8. Next Hop 1604 0 1 2 3 1605 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 1606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1607 | Type = 7 | Length | AE | Reserved | 1608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1609 | Next hop... 1610 +-+-+-+-+-+-+-+-+-+-+-+- 1612 A Next Hop TLV establishes a next-hop address for a given address 1613 family (IPv4 or IPv6) that is implied by subsequent Update TLVs. 1615 Fields : 1617 Type Set to 7 to indicate a Next Hop TLV. 1619 Length The length of the body, exclusive of the Type and Length 1620 fields. 1622 AE The encoding of the Address field. This SHOULD be 1 or 3 1623 and MUST NOT be 0. 1625 Reserved Sent as 0 and MUST be ignored on reception. 1627 Next hop The next-hop address advertised by subsequent Update TLVs, 1628 for this address family. 1630 When the address family matches the network-layer protocol that this 1631 packet is transported over, a Next Hop TLV is not needed: in that 1632 case, the next hop is taken to be the source address of the packet. 1634 Next Hop TLVs with an unknown value for the AE field MUST be silently 1635 ignored. 1637 4.4.9. Update 1639 0 1 2 3 1640 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 1641 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1642 | Type = 8 | Length | AE | Flags | 1643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1644 | Plen | Omitted | Interval | 1645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1646 | Seqno | Metric | 1647 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1648 | Prefix... 1649 +-+-+-+-+-+-+-+-+-+-+-+- 1651 An Update TLV advertises or retracts a route. As an optimisation, 1652 this can also have the side effect of establishing a new implied 1653 router-id and a new default prefix. 1655 Fields : 1657 Type Set to 8 to indicate an Update TLV. 1659 Length The length of the body, exclusive of the Type and Length 1660 fields. 1662 AE The encoding of the Prefix field. 1664 Flags The individual bits of this field specify special handling 1665 of this TLV (see below). Every node MUST be able to 1666 interpret the flags with values 80 and 40 hexadecimal; 1667 unknown flags MUST be silently ignored. 1669 Plen The length of the advertised prefix. 1671 Omitted The number of octets that have been omitted at the 1672 beginning of the advertised prefix and that should be taken 1673 from a preceding Update TLV with the flag with value 80 1674 hexadecimal set. 1676 Interval An upper bound, expressed in centiseconds, on the time 1677 after which the sending node will send a new update for 1678 this prefix. This MUST NOT be 0 and SHOULD NOT be less 1679 than 10. The receiving node will use this value to compute 1680 a hold time for this routing table entry. The value FFFF 1681 hexadecimal (infinity) expresses that this announcement 1682 will not be repeated unless a request is received 1683 (Section 3.8.2.3). 1685 Seqno The originator's sequence number for this update. 1687 Metric The sender's metric for this route. The value FFFF 1688 hexadecimal (infinity) means that this is a route 1689 retraction. 1691 Prefix The prefix being advertised. This field's size is (Plen/8 1692 - Omitted) rounded upwards. 1694 The Flags field is interpreted as follows: 1696 o if the bit with value 80 hexadecimal is set, then this Update 1697 establishes a new default prefix for subsequent Update TLVs with a 1698 matching address family within the same packet; 1700 o if the bit with value 40 hexadecimal is set, then the low-order 8 1701 octets of the advertised prefix establish a new default router-id 1702 for this TLV and subsequent Update TLVs in the same packet. 1704 The prefix being advertised by an Update TLV is computed as follows: 1706 o the first Omitted octets of the prefix are taken from the previous 1707 Update TLV with flag 80 hexadecimal set and the same address 1708 family; 1710 o the next (Plen/8 - Omitted) (rounded upwards) octets are taken 1711 from the Prefix field; 1713 o the remaining octets are set to 0. 1715 If the Metric field is finite, the router-id of the originating node 1716 for this announcement is taken from the low-order 8 octets of the 1717 prefix advertised by this Update if the bit with value 40 hexadecimal 1718 is set in the Flags field. Otherwise, it is taken either from the 1719 preceding Router-Id packet, or the preceding Update packet with flag 1720 40 hexadecimal set, whichever comes last. 1722 The next-hop address for this update is taken from the last preceding 1723 Next Hop TLV with a matching address family in the same packet; if no 1724 such TLV exists, it is taken from the network-layer source address of 1725 this packet. 1727 If the metric field is FFFF hexadecimal, this TLV specifies a 1728 retraction. In that case, the current router-id and the Seqno are 1729 not used. AE MAY then be 0, in which case this Update retracts all 1730 of the routes previously advertised on this interface. 1732 Update TLVs with an unknown value for the AE field MUST be silently 1733 ignored. 1735 4.4.10. Route Request 1737 0 1 2 3 1738 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 1739 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1740 | Type = 9 | Length | AE | Plen | 1741 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1742 | Prefix... 1743 +-+-+-+-+-+-+-+-+-+-+-+- 1745 A Route Request TLV prompts the receiver to send an update for a 1746 given prefix, or a full routing table dump. 1748 Fields : 1750 Type Set to 9 to indicate a Route Request TLV. 1752 Length The length of the body, exclusive of the Type and Length 1753 fields. 1755 AE The encoding of the Prefix field. The value 0 specifies 1756 that this is a request for a full routing table dump (a 1757 wildcard request). 1759 Plen The length of the requested prefix. 1761 Prefix The prefix being requested. This field's size is Plen/8 1762 rounded upwards. 1764 A Request TLV prompts the receiving node to send an update message 1765 for the prefix specified by the AE, Plen, and Prefix fields, or a 1766 full dump of its routing table if AE is 0 (in which case Plen MUST be 1767 0 and Prefix is of length 0). A Request may be sent to a unicast 1768 address if it is destined to a single node, or to a multicast address 1769 if the request is destined to all of the neighbours of the sending 1770 interface. 1772 4.4.11. Seqno Request 1774 0 1 2 3 1775 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 1776 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1777 | Type = 10 | Length | AE | Plen | 1778 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1779 | Seqno | Hop Count | Reserved | 1780 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1781 | | 1782 + Router-Id + 1783 | | 1784 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1785 | Prefix... 1786 +-+-+-+-+-+-+-+-+-+-+ 1788 A Seqno Request TLV prompts the receiver to send an Update for a 1789 given prefix with a given sequence number, or to forward the request 1790 further if it cannot be satisfied locally. 1792 Fields : 1794 Type Set to 10 to indicate a Seqno Request message. 1796 Length The length of the body, exclusive of the Type and Length 1797 fields. 1799 AE The encoding of the Prefix field. This MUST NOT be 0. 1801 Plen The length of the requested prefix. 1803 Seqno The sequence number that is being requested. 1805 Hop Count The maximum number of times that this TLV may be forwarded, 1806 plus 1. This MUST NOT be 0. 1808 Prefix The prefix being requested. This field's size is Plen/8 1809 rounded upwards. 1811 A Seqno Request TLV prompts the receiving node to send an Update for 1812 the prefix specified by the AE, Plen, and Prefix fields, with either 1813 a router-id different from what is specified by the Router-Id field, 1814 or a Seqno no less than what is specified by the Seqno field. If 1815 this request cannot be satisfied locally, then it is forwarded 1816 according to the rules set out in Section 3.8.1.2. 1818 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 1819 be forwarded to a multicast address and MUST NOT be forwarded to more 1820 than one neighbour. A request MUST NOT be forwarded if its Hop Count 1821 field is 1. 1823 5. IANA Considerations 1825 IANA has registered the UDP port number 6697, called "babel", for use 1826 by the Babel protocol. 1828 IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and 1829 the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. 1831 6. Security Considerations 1833 As defined in this document, Babel is a completely insecure protocol. 1834 Any attacker can attract data traffic by advertising routes with a 1835 low metric. This particular issue can be solved either by lower- 1836 layer security mechanisms (e.g., IPsec or link-layer security), or by 1837 appending a cryptographic key to Babel packets; the provision of 1838 ignoring any data contained within a Babel packet beyond the body 1839 length declared by the header is designed for just such a purpose. 1841 The information that a Babel node announces to the whole routing 1842 domain is often sufficient to determine a mobile node's physical 1843 location with reasonable precision. The privacy issues that this 1844 causes can be mitigated somewhat by using randomly chosen router-ids 1845 and randomly chosen IP addresses, and changing them periodically. 1847 When carried over IPv6, Babel packets are ignored unless they are 1848 sent from a link-local IPv6 address; since routers don't forward 1849 link-local IPv6 packets, this provides protection against spoofed 1850 Babel packets being sent from the global Internet. No such natural 1851 protection exists when Babel packets are carried over IPv4. 1853 7. References 1854 7.1. Normative References 1856 [ADDRARCH] 1857 Hinden, R. and S. Deering, "IP Version 6 Addressing 1858 Architecture", RFC 4291, February 2006. 1860 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1861 Requirement Levels", RFC 2119, March 1997. 1863 7.2. Informative References 1865 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 1866 Sequenced Distance-Vector Routing (DSDV) for Mobile 1867 Computers", ACM SIGCOMM'94 Conference on Communications 1868 Architectures, Protocols and Applications 234-244, 1994. 1870 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 1871 Computations", IEEE/ACM Transactions on Networking 1:1, 1872 February 1993. 1874 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 1875 "EIGRP -- a Fast Routing Protocol Based on Distance 1876 Vectors", Proc. Interop 94, 1994. 1878 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 1879 high-throughput path metric for multi-hop wireless 1880 networks", Proc. MobiCom 2003, 2003. 1882 [IS-IS] "Information technology -- Telecommunications and 1883 information exchange between systems -- Intermediate 1884 System to Intermediate System intra-domain routeing 1885 information exchange protocol for use in conjunction with 1886 the protocol for providing the connectionless-mode network 1887 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 1889 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 1890 periodic routing messages", IEEE/ACM Transactions on 1891 Networking 2, 2, 122-136, April 1994. 1893 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 1895 [PACKETBB] 1896 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 1897 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 1898 Format", RFC 5444, February 2009. 1900 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 1902 Appendix A. Cost and Metric Computation 1904 The strategy for computing link costs and route metrics is a local 1905 matter; Babel itself only requires that it comply with the conditions 1906 given in Section 3.4.3 and Section 3.5.2. Different nodes MAY use 1907 different strategies in a single network and MAY use different 1908 strategies on different interface types. This section gives a few 1909 examples of such strategies. 1911 The sample implementation of Babel maintains statistics about the 1912 last 16 received Hello TLVs (Appendix A.1), computes costs by using 1913 the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX 1914 (Appendix A.2.2) on wireless links. It uses an additive algebra for 1915 metric computation (Appendix A.3.1). 1917 A.1. Maintaining Hello History 1919 For each neighbour, the sample implementation of Babel maintains a 1920 Hello history and an expected sequence number. The Hello history is 1921 a vector of 16 bits, where a 1 value represents a received Hello, and 1922 a 0 value a missed Hello. The expected sequence number, written ne, 1923 is the sequence number that is expected to be carried by the next 1924 received hello from this neighbour. 1926 Whenever it receives a Hello packet from a neighbour, a node compares 1927 the received sequence number nr with its expected sequence number ne. 1928 Depending on the outcome of this comparison, one of the following 1929 actions is taken: 1931 o if the two differ by more than 16 (modulo 2^16), then the sending 1932 node has probably rebooted and lost its sequence number; the 1933 associated neighbour table entry is flushed; 1935 o otherwise, if the received nr is smaller (modulo 2^16) than the 1936 expected sequence number ne, then the sending node has increased 1937 its Hello interval without our noticing; the receiving node 1938 removes the last (ne - nr) entries from this neighbour's Hello 1939 history (we "undo history"); 1941 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 1942 node has decreased its Hello interval, and some Hellos were lost; 1943 the receiving node adds (nr - ne) 0 bits to the Hello history (we 1944 "fast-forward"). 1946 The receiving node then appends a 1 bit to the neighbour's Hello 1947 history, resets the neighbour's Hello timer, and sets ne to (nr + 1). 1948 It then resets the neighbour's Hello timer to 1.5 times the value 1949 advertised in the received Hello (the extra margin allows for the 1950 delay due to jitter). 1952 Whenever the Hello timer associated to a neighbour expires, the local 1953 node adds a 0 bit to this neighbour's Hello history, and increments 1954 the expected Hello number. If the Hello history is empty (it 1955 contains 0 bits only), the neighbour entry is flushed; otherwise, it 1956 resets the neighbour's Hello timer to the value advertised in the 1957 last Hello received from this neighbour (no extra margin is necessary 1958 in this case). 1960 A.2. Cost Computation 1962 A.2.1. k-out-of-j 1964 K-out-of-j link sensing is suitable for wired links that are either 1965 up, in which case they only occasionally drop a packet, or down, in 1966 which case they drop all packets. 1968 The k-out-of-j strategy is parameterised by two small integers k and 1969 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 1970 1. A node keeps a history of the last j hellos; if k or more of 1971 those have been correctly received, the link is assumed to be up, and 1972 the rxcost is set to K; otherwise, the link is assumed to be down, 1973 and the rxcost is set to infinity. 1975 The cost of such a link is defined as 1977 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 1979 o cost = txcost otherwise. 1981 A.2.2. ETX 1983 The Estimated Transmission Cost metric [ETX] estimates the number of 1984 times that a unicast frame will be retransmitted by the IEEE 802.11 1985 MAC, assuming infinite persistence. 1987 A node uses a neighbour's Hello history to compute an estimate, 1988 written beta, of the probability that a Hello TLV is successfully 1989 received. The rxcost is defined as 256/beta. 1991 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 1992 successfully sending a Hello TLV. The cost is then computed by 1994 cost = 256/(alpha * beta) 1996 or, equivalently, 1997 cost = (MAX(txcost, 256) * rxcost) / 256. 1999 A.3. Metric Computation 2001 A.3.1. Additive Metrics 2003 The simplest approach for obtaining a monotonic, isotonic metric is 2004 to define the metric of a route as the sum of the costs of the 2005 component links. More formally, if a neighbour advertises a route 2006 with metric m over a link with cost c, then the resulting route has 2007 metric M(c, m) = c + m. 2009 A multiplicative metric can be converted to an additive one by taking 2010 the logarithm (in some suitable base) of the link costs. 2012 A.3.2. External Sources of Willingness 2014 A node may want to vary its willingness to forward packets by taking 2015 into account information that is external to the Babel protocol, such 2016 as the monetary cost of a link, the node's battery status, CPU load, 2017 etc. This can be done by adding to every route's metric a value k 2018 that depends on the external data. For example, if a battery-powered 2019 node receives an update with metric m over a link with cost c, it 2020 might compute a metric M(c, m) = k + c + m, where k depends on the 2021 battery status. 2023 In order to preserve strict monotonicity (Section 3.5.2), the value k 2024 must be greater than -c. 2026 Appendix B. Constants 2028 The choice of time constants is a trade-off between fast detection of 2029 mobility events and protocol overhead. Two implementations of Babel 2030 with different time constants will interoperate, although the 2031 resulting convergence time will most likely be dictated by the 2032 slowest of the two implementations. 2034 Experience with the sample implementation of Babel indicates that the 2035 Hello interval is the most important time constant: a mobility event 2036 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2037 on triggered updates and explicit requests, the Update interval only 2038 has an effect on the time it takes for accurate metrics to be 2039 propagated after variations in link costs too small to trigger an 2040 unscheduled update. 2042 At the time of writing, the sample implementation of Babel uses the 2043 following default values: 2045 Hello Interval: 4 seconds on wireless links, 20 seconds on wired 2046 links. 2048 IHU Interval: the advertised IHU interval is always 3 times the 2049 Hello interval. IHUs are actually sent with each Hello on lossy 2050 links (as determined from the Hello history), but only with every 2051 third Hello on lossless links. 2053 Update Interval: 4 times the Hello interval. 2055 IHU Hold Time: 3.5 times the advertised IHU interval. 2057 Route Expiry Time: 3.5 times the advertised update interval. 2059 Source GC time: 3 minutes. 2061 The amount of jitter applied to a packet depends on whether it 2062 contains any urgent TLVs or not. Urgent triggered updates and urgent 2063 requests are delayed by no more than 200ms; other TLVs are delayed by 2064 no more than one-half the Hello interval. 2066 Appendix C. Simplified Implementations 2068 Babel is a fairly economic protocol. Route updates take between 12 2069 and 40 octets per destination, depending on how successful 2070 compression is; in a double-stack mesh network, an average of less 2071 than 24 octets is typical. The route table occupies about 35 octets 2072 per IPv6 entry. To put these values into perspective, a single full- 2073 size Ethernet frame can carry some 65 route updates, and a megabyte 2074 of memory can contain a 20000-entry routing table and the associated 2075 source table. 2077 Babel is also a reasonably simple protocol. The sample 2078 implementation consists of less than 8000 lines of C code, and it 2079 compiles to less than 60 kB of text on a 32-bit CISC architecture. 2081 Nonetheless, in some very constrained environments, such as PDAs, 2082 microwave ovens, or abacuses, it may be desirable to have subset 2083 implementations of the protocol. 2085 A parasitic implementation is one that uses a Babel network for 2086 routing its packets but does not announce any of the routes that it 2087 has learnt from its neighbours. (This is slightly more than a 2088 passive implementation, which doesn't even announce routes to 2089 itself.) It may either maintain a full routing table or simply 2090 select a gateway amongst any one of its neighbours that announces a 2091 default route. Since a parasitic implementation never forwards 2092 packets, it cannot possibly participate in a routing loop; hence, it 2093 need not evaluate the feasibility condition, and need not maintain a 2094 source table. 2096 A parasitic implementation MUST answer acknowledgement requests and 2097 MUST participate in the Hello/IHU protocol. Finally, it MUST be able 2098 to reply to seqno requests for routes that it announces and SHOULD be 2099 able to reply to route requests. 2101 Appendix D. Software Availability 2103 The sample implementation of Babel is available from 2104 . 2106 Author's Address 2108 Juliusz Chroboczek 2109 IRIF, University of Paris-Diderot 2110 Case 7014 2111 75205 Paris Cedex 13 2112 France 2114 Email: jch@pps.univ-paris-diderot.fr