idnits 2.17.1 draft-ietf-babel-rfc6126bis-02.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 (May 24, 2017) is 2528 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 May 24, 2017 5 Expires: November 25, 2017 7 The Babel Routing Protocol 8 draft-ietf-babel-rfc6126bis-02 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 November 25, 2017. 33 Copyright Notice 35 Copyright (c) 2017 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 51 1.1. Features . . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . 4 53 1.3. Specification of Requirements . . . . . . . . . . . . . . 4 54 2. Conceptual Description of the Protocol . . . . . . . . . . . 4 55 2.1. Costs, Metrics and Neighbourship . . . . . . . . . . . . 5 56 2.2. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . 5 57 2.3. Transient Loops in Bellman-Ford . . . . . . . . . . . . . 6 58 2.4. Feasibility Conditions . . . . . . . . . . . . . . . . . 6 59 2.5. Solving Starvation: Sequencing Routes . . . . . . . . . . 8 60 2.6. Requests . . . . . . . . . . . . . . . . . . . . . . . . 9 61 2.7. Multiple Routers . . . . . . . . . . . . . . . . . . . . 10 62 2.8. Overlapping Prefixes . . . . . . . . . . . . . . . . . . 11 63 3. Protocol Operation . . . . . . . . . . . . . . . . . . . . . 11 64 3.1. Message Transmission and Reception . . . . . . . . . . . 12 65 3.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 12 66 3.3. Acknowledged Packets . . . . . . . . . . . . . . . . . . 16 67 3.4. Neighbour Acquisition . . . . . . . . . . . . . . . . . . 16 68 3.5. Routing Table Maintenance . . . . . . . . . . . . . . . . 18 69 3.6. Route Selection . . . . . . . . . . . . . . . . . . . . . 22 70 3.7. Sending Updates . . . . . . . . . . . . . . . . . . . . . 23 71 3.8. Explicit Route Requests . . . . . . . . . . . . . . . . . 25 72 4. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . 29 73 4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 29 74 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 30 75 4.3. TLV Format . . . . . . . . . . . . . . . . . . . . . . . 31 76 4.4. Sub-TLV Format . . . . . . . . . . . . . . . . . . . . . 31 77 4.5. Parser state . . . . . . . . . . . . . . . . . . . . . . 32 78 4.6. Details of Specific TLVs . . . . . . . . . . . . . . . . 33 79 4.7. Details of specific sub-TLVs . . . . . . . . . . . . . . 43 80 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 43 81 6. Security Considerations . . . . . . . . . . . . . . . . . . . 44 82 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 44 83 7.1. Normative References . . . . . . . . . . . . . . . . . . 44 84 7.2. Informative References . . . . . . . . . . . . . . . . . 44 85 Appendix A. Cost and Metric Computation . . . . . . . . . . . . 45 86 A.1. Maintaining Hello History . . . . . . . . . . . . . . . . 45 87 A.2. Cost Computation . . . . . . . . . . . . . . . . . . . . 46 88 A.3. Metric Computation . . . . . . . . . . . . . . . . . . . 47 89 Appendix B. Constants . . . . . . . . . . . . . . . . . . . . . 48 90 Appendix C. Considerations for protocol extensions . . . . . . . 49 91 Appendix D. Simplified Implementations . . . . . . . . . . . . . 50 92 Appendix E. Software Availability . . . . . . . . . . . . . . . 50 93 Appendix F. Changes from previous versions . . . . . . . . . . . 51 94 F.1. Changes since RFC 6126 . . . . . . . . . . . . . . . . . 51 95 F.2. Changes since draft-ietf-babel-rfc6126bis-00 . . . . . . 51 96 F.3. Changes since draft-ietf-babel-rfc6126bis-01 . . . . . . 51 97 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 52 99 1. Introduction 101 Babel is a loop-avoiding distance-vector routing protocol that is 102 designed to be robust and efficient both in networks using prefix- 103 based routing and in networks using flat routing ("mesh networks"), 104 and both in relatively stable wired networks and in highly dynamic 105 wireless networks. 107 1.1. Features 109 The main property that makes Babel suitable for unstable networks is 110 that, unlike naive distance-vector routing protocols [RIP], it 111 strongly limits the frequency and duration of routing pathologies 112 such as routing loops and black-holes during reconvergence. Even 113 after a mobility event is detected, a Babel network usually remains 114 loop-free. Babel then quickly reconverges to a configuration that 115 preserves the loop-freedom and connectedness of the network, but is 116 not necessarily optimal; in many cases, this operation requires no 117 packet exchanges at all. Babel then slowly converges, in a time on 118 the scale of minutes, to an optimal configuration. This is achieved 119 by using sequenced routes, a technique pioneered by Destination- 120 Sequenced Distance-Vector routing [DSDV]. 122 More precisely, Babel has the following properties: 124 o when every prefix is originated by at most one router, Babel never 125 suffers from routing loops; 127 o when a prefix is originated by multiple routers, Babel may 128 occasionally create a transient routing loop for this particular 129 prefix; this loop disappears in a time proportional to its 130 diameter, and never again (up to an arbitrary garbage-collection 131 (GC) time) will the routers involved participate in a routing loop 132 for the same prefix; 134 o assuming reasonable packet loss rates, any routing black-holes 135 that may appear after a mobility event are corrected in a time at 136 most proportional to the network's diameter. 138 Babel has provisions for link quality estimation and for fairly 139 arbitrary metrics. When configured suitably, Babel can implement 140 shortest-path routing, or it may use a metric based, for example, on 141 measured packet loss. 143 Babel nodes will successfully establish an association even when they 144 are configured with different parameters. For example, a mobile node 145 that is low on battery may choose to use larger time constants (hello 146 and update intervals, etc.) than a node that has access to wall 147 power. Conversely, a node that detects high levels of mobility may 148 choose to use smaller time constants. The ability to build such 149 heterogeneous networks makes Babel particularly adapted to the 150 wireless environment. 152 Finally, Babel is a hybrid routing protocol, in the sense that it can 153 carry routes for multiple network-layer protocols (IPv4 and IPv6), 154 whichever protocol the Babel packets are themselves being carried 155 over. 157 1.2. Limitations 159 Babel has two limitations that make it unsuitable for use in some 160 environments. First, Babel relies on periodic routing table updates 161 rather than using a reliable transport; hence, in large, stable 162 networks it generates more traffic than protocols that only send 163 updates when the network topology changes. In such networks, 164 protocols such as OSPF [OSPF], IS-IS [IS-IS], or the Enhanced 165 Interior Gateway Routing Protocol (EIGRP) [EIGRP] might be more 166 suitable. 168 Second, Babel does impose a hold time when a prefix is retracted 169 (Section 3.5.5). While this hold time does not apply to the exact 170 prefix being retracted, and hence does not prevent fast reconvergence 171 should it become available again, it does apply to any shorter prefix 172 that covers it. Hence, if a previously deaggregated prefix becomes 173 aggregated, it will be unreachable for a few minutes. This makes 174 Babel unsuitable for use in mobile networks that implement automatic 175 prefix aggregation. 177 1.3. Specification of Requirements 179 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 180 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 181 document are to be interpreted as described in [RFC2119]. 183 2. Conceptual Description of the Protocol 185 Babel is a mostly loop-free distance vector protocol: it is based on 186 the Bellman-Ford protocol, just like the venerable RIP [RIP], but 187 includes a number of refinements that either prevent loop formation 188 altogether, or ensure that a loop disappears in a timely manner and 189 doesn't form again. 191 Conceptually, Bellman-Ford is executed in parallel for every source 192 of routing information (destination of data traffic). In the 193 following discussion, we fix a source S; the reader will recall that 194 the same algorithm is executed for all sources. 196 2.1. Costs, Metrics and Neighbourship 198 As many routing algorithms, Babel computes costs of links between any 199 two neighbouring nodes, abstract values attached to the edges between 200 two nodes. We write C(A, B) for the cost of the edge from node A to 201 node B. 203 Given a route between any two nodes, the metric of the route is the 204 sum of the costs of all the edges along the route. The goal of the 205 routing algorithm is to compute, for every source S, the tree of the 206 routes of lowest metric to S. 208 Costs and metrics need not be integers. In general, they can be 209 values in any algebra that satisfies two fairly general conditions 210 (Section 3.5.2). 212 A Babel node periodically broadcasts Hello messages to all of its 213 neighbours; it also periodically sends an IHU ("I Heard You") message 214 to every neighbour from which it has recently heard a Hello. From 215 the information derived from Hello and IHU messages received from its 216 neighbour B, a node A computes the cost C(A, B) of the link from A to 217 B. 219 2.2. The Bellman-Ford Algorithm 221 Every node A maintains two pieces of data: its estimated distance to 222 S, written D(A), and its next-hop router to S, written NH(A). 223 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined. 225 Periodically, every node B sends to all of its neighbours a route 226 update, a message containing D(B). When a neighbour A of B receives 227 the route update, it checks whether B is its selected next hop; if 228 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B) 229 + D(B). If that is not the case, then A compares C(A, B) + D(B) to 230 its current value of D(A). If that value is smaller, meaning that 231 the received update advertises a route that is better than the 232 currently selected route, then NH(A) is set to B, and D(A) is set to 233 C(A, B) + D(B). 235 A number of refinements to this algorithm are possible, and are used 236 by Babel. In particular, convergence speed may be increased by 237 sending unscheduled "triggered updates" whenever a major change in 238 the topology is detected, in addition to the regular, scheduled 239 updates. Additionally, a node may maintain a number of alternate 240 routes, which are being advertised by neighbours other than its 241 selected neighbour, and which can be used immediately if the selected 242 route were to fail. 244 2.3. Transient Loops in Bellman-Ford 246 It is well known that a naive application of Bellman-Ford to 247 distributed routing can cause transient loops after a topology 248 change. Consider for example the following diagram: 250 B 251 1 /| 252 1 / | 253 S --- A |1 254 \ | 255 1 \| 256 C 258 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A. 260 Suppose now that the link between S and A fails: 262 B 263 1 /| 264 / | 265 S A |1 266 \ | 267 1 \| 268 C 270 When it detects the failure of the link, A switches its next hop to B 271 (which is still advertising a route to S with metric 2), and 272 advertises a metric equal to 3, and then advertises a new route with 273 metric 3. This process of nodes changing selected neighbours and 274 increasing their metric continues until the advertised metric reaches 275 "infinity", a value larger than all the metrics that the routing 276 protocol is able to carry. 278 2.4. Feasibility Conditions 280 Bellman-Ford is a very robust algorithm: its convergence properties 281 are preserved when routers delay route acquisition or when they 282 discard some updates. Babel routers discard received route 283 announcements unless they can prove that accepting them cannot 284 possibly cause a routing loop. 286 More formally, we define a condition over route announcements, known 287 as the feasibility condition, that guarantees the absence of routing 288 loops whenever all routers ignore route updates that do not satisfy 289 the feasibility condition. In effect, this makes Bellman-Ford into a 290 family of routing algorithms, parameterised by the feasibility 291 condition. 293 Many different feasibility conditions are possible. For example, BGP 294 can be modelled as being a distance-vector protocol with a (rather 295 drastic) feasibility condition: a routing update is only accepted 296 when the receiving node's AS number is not included in the update's 297 AS-Path attribute (note that BGP's feasibility condition does not 298 ensure the absence of transitory "micro-loops" during reconvergence). 300 Another simple feasibility condition, used in Destination-Sequenced 301 Distance-Vector (DSDV) routing [DSDV] and in Ad hoc On-Demand 302 Distance Vector (AODV) routing, stems from the following observation: 303 a routing loop can only arise after a router has switched to a route 304 with a larger metric than the route that it had previously selected. 305 Hence, one could decide that a route is feasible only when its metric 306 at the local node would be no larger than the metric of the currently 307 selected route, i.e., an announcement carrying a metric D(B) is 308 accepted by A when C(A, B) + D(B) <= D(A). If all routers obey this 309 constraint, then the metric at every router is nonincreasing, and the 310 following invariant is always preserved: if A has selected B as its 311 successor, then D(B) < D(A), which implies that the forwarding graph 312 is loop-free. 314 Babel uses a slightly more refined feasibility condition, used in 315 EIGRP [DUAL]. Given a router A, define the feasibility distance of 316 A, written FD(A), as the smallest metric that A has ever advertised 317 for S to any of its neighbours. An update sent by a neighbour B of A 318 is feasible when the metric D(B) advertised by B is strictly smaller 319 than A's feasibility distance, i.e., when D(B) < FD(A). 321 It is easy to see that this latter condition is no more restrictive 322 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility; 323 then D(A) is nonincreasing, hence at all times D(A) <= FD(A). 324 Suppose now that A receives a DSDV-feasible update that advertises a 325 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) <= 326 D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < FD(A). 328 To see that it is strictly less restrictive, consider the following 329 diagram, where A has selected the route through B, and D(A) = FD(A) = 330 2. Since D(C) = 1 < FD(A), the alternate route through C is feasible 331 for A, although its metric C(A, C) + D(C) = 5 is larger than that of 332 the currently selected route: 334 B 335 1 / \ 1 336 / \ 337 S A 338 \ / 339 1 \ / 4 340 C 342 To show that this feasibility condition still guarantees loop- 343 freedom, recall that at the time when A accepts an update from B, the 344 metric D(B) announced by B is no smaller than FD(B); since it is 345 smaller than FD(A), at that point in time FD(B) < FD(A). Since this 346 property is preserved when A sends updates, it remains true at all 347 times, which ensures that the forwarding graph has no loops. 349 2.5. Solving Starvation: Sequencing Routes 351 Obviously, the feasibility conditions defined above cause starvation 352 when a router runs out of feasible routes. Consider the following 353 diagram, where both A and B have selected the direct route to S: 355 A 356 1 /| D(A) = 1 357 / | FD(A) = 1 358 S |1 359 \ | D(B) = 2 360 2 \| FD(B) = 2 361 B 363 Suppose now that the link between A and S breaks: 365 A 366 | 367 | FD(A) = 1 368 S |1 369 \ | D(B) = 2 370 2 \| FD(B) = 2 371 B 373 The only route available from A to S, the one that goes through B, is 374 not feasible: A suffers from a spurious starvation. 376 At this point, the whole network must be rebooted in order to solve 377 the starvation; this is essentially what EIGRP does when it performs 378 a global synchronisation of all the routers in the network with the 379 source (the "active" phase of EIGRP). 381 Babel reacts to starvation in a less drastic manner, by using 382 sequenced routes, a technique introduced by DSDV and adopted by AODV. 383 In addition to a metric, every route carries a sequence number, a 384 nondecreasing integer that is propagated unchanged through the 385 network and is only ever incremented by the source; a pair (s, m), 386 where s is a sequence number and m a metric, is called a distance. 388 A received update is feasible when either it is more recent than the 389 feasibility distance maintained by the receiving node, or it is 390 equally recent and the metric is strictly smaller. More formally, if 391 FD(A) = (s, m), then an update carrying the distance (s', m') is 392 feasible when either s' > s, or s = s' and m' < m. 394 Assuming the sequence number of S is 137, the diagram above becomes: 396 A 397 | 398 | FD(A) = (137, 1) 399 S |1 400 \ | D(B) = (137, 2) 401 2 \| FD(B) = (137, 2) 402 B 404 After S increases its sequence number, and the new sequence number is 405 propagated to B, we have: 407 A 408 | 409 | FD(A) = (137, 1) 410 S |1 411 \ | D(B) = (138, 2) 412 2 \| FD(B) = (138, 2) 413 B 415 at which point the route through B becomes feasible again. 417 Note that while sequence numbers are used for determining 418 feasibility, they are not necessarily used in route selection: a node 419 will normally ignore the sequence number when selecting a route 420 (Section 3.6). 422 2.6. Requests 424 In DSDV, the sequence number of a source is increased periodically. 425 A route becomes feasible again after the source increases its 426 sequence number, and the new sequence number is propagated through 427 the network, which may, in general, require a significant amount of 428 time. 430 Babel takes a different approach. When a node detects that it is 431 suffering from a potentially spurious starvation, it sends an 432 explicit request to the source for a new sequence number. This 433 request is forwarded hop by hop to the source, with no regard to the 434 feasibility condition. Upon receiving the request, the source 435 increases its sequence number and broadcasts an update, which is 436 forwarded to the requesting node. 438 Note that after a change in network topology not all such requests 439 will, in general, reach the source, as some will be sent over links 440 that are now broken. However, if the network is still connected, 441 then at least one among the nodes suffering from spurious starvation 442 has an (unfeasible) route to the source; hence, in the absence of 443 packet loss, at least one such request will reach the source. 444 (Resending requests a small number of times compensates for packet 445 loss.) 447 Since requests are forwarded with no regard to the feasibility 448 condition, they may, in general, be caught in a forwarding loop; this 449 is avoided by having nodes perform duplicate detection for the 450 requests that they forward. 452 2.7. Multiple Routers 454 The above discussion assumes that every prefix is originated by a 455 single router. In real networks, however, it is often necessary to 456 have a single prefix originated by multiple routers; for example, the 457 default route will be originated by all of the edge routers of a 458 routing domain. 460 Since synchronising sequence numbers between distinct routers is 461 problematic, Babel treats routes for the same prefix as distinct 462 entities when they are originated by different routers: every route 463 announcement carries the router-id of its originating router, and 464 feasibility distances are not maintained per prefix, but per source, 465 where a source is a pair of a router-id and a prefix. In effect, 466 Babel guarantees loop-freedom for the forwarding graph to every 467 source; since the union of multiple acyclic graphs is not in general 468 acyclic, Babel does not in general guarantee loop-freedom when a 469 prefix is originated by multiple routers, but any loops will be 470 broken in a time at most proportional to the diameter of the loop -- 471 as soon as an update has "gone around" the routing loop. 473 Consider for example the following diagram, where A has selected the 474 default route through S, and B has selected the one through S': 476 1 1 1 477 ::/0 -- S --- A --- B --- S' -- ::/0 478 Suppose that both default routes fail at the same time; then nothing 479 prevents A from switching to B, and B simultaneously switching to A. 480 However, as soon as A has successfully advertised the new route to B, 481 the route through A will become unfeasible for B. Conversely, as 482 soon as B will have advertised the route through A, the route through 483 B will become unfeasible for A. 485 In effect, the routing loop disappears at the latest when routing 486 information has gone around the loop. Since this process can be 487 delayed by lost packets, Babel makes certain efforts to ensure that 488 updates are sent reliably after a router-id change. 490 Additionally, after the routers have advertised the two routes, both 491 sources will be in their source tables, which will prevent them from 492 ever again participating in a routing loop involving routes from S 493 and S' (up to the source GC time, which, available memory permitting, 494 can be set to arbitrarily large values). 496 2.8. Overlapping Prefixes 498 In the above discussion, we have assumed that all prefixes are 499 disjoint, as is the case in flat ("mesh") routing. In practice, 500 however, prefixes may overlap: for example, the default route 501 overlaps with all of the routes present in the network. 503 After a route fails, it is not correct in general to switch to a 504 route that subsumes the failed route. Consider for example the 505 following configuration: 507 1 1 508 ::/0 -- A --- B --- C 510 Suppose that node C fails. If B forwards packets destined to C by 511 following the default route, a routing loop will form, and persist 512 until A learns of B's retraction of the direct route to C. Babel 513 avoids this pitfall by maintaining an "unreachable" route for a few 514 minutes after a route is retracted; the time for which such a route 515 must be maintained should be the worst-case propagation time of the 516 retraction of the route to C. 518 3. Protocol Operation 520 Every Babel speaker is assigned a router-id, which is an arbitrary 521 string of 8 octets that is assumed unique across the routing domain. 522 We suggest that router-ids should be assigned in modified EUI-64 523 format [ADDRARCH]. (As a matter of fact, the protocol encoding is 524 slightly more compact when router-ids are assigned in the same manner 525 as the IPv6 layer assigns host IDs.) 527 3.1. Message Transmission and Reception 529 Babel protocol packets are sent in the body of a UDP datagram. Each 530 Babel packet consists of zero or more TLVs. Most TLVs may contain 531 sub-TLVs. 533 The source address of a Babel packet is always a unicast address, 534 link-local in the case of IPv6. Babel packets may be sent to a well- 535 known (link-local) multicast address (this is the usual case) or to a 536 (link-local) unicast address. In normal operation, a Babel speaker 537 sends both multicast and unicast packets to its neighbours. 539 With the exception of Hello TLVs and acknowledgements, all Babel TLVs 540 can be sent to either unicast or multicast addresses, and their 541 semantics does not depend on whether the destination was a unicast or 542 multicast address. Hence, a Babel speaker does not need to determine 543 the destination address of a packet that it receives in order to 544 interpret it. 546 A moderate amount of jitter is applied to packets sent by a Babel 547 speaker: outgoing TLVs are buffered and SHOULD be sent with a small 548 random delay. This is done for two purposes: it avoids 549 synchronisation of multiple Babel speakers across a network [JITTER], 550 and it allows for the aggregation of multiple TLVs into a single 551 packet. 553 The exact delay and amount of jitter applied to a packet depends on 554 whether it contains any urgent TLVs. Acknowledgement TLVs MUST be 555 sent before the deadline specified in the corresponding request. The 556 particular class of updates specified in Section 3.7.2 MUST be sent 557 in a timely manner. The particular class of request and update TLVs 558 specified in Section 3.8.2 SHOULD be sent in a timely manner. 560 3.2. Data Structures 562 Every Babel speaker maintains a number of data structures. All of 563 these data structures consist of familiar data types -- integers, IP 564 addresses, etc. -- with the exception of sequence numbers. 566 3.2.1. Sequence number arithmetic 568 Sequence numbers (seqnos) appear in a number of Babel data 569 structures, and they are interpreted as integers modulo 2^16. For 570 the purposes of this document, arithmetic on serial numbers is 571 defined as follows. 573 Given a seqno s and an integer n, the sum of s and n is defined by 574 s + n (modulo 2^16) = (s + n) MOD 2^16 576 or, equivalently, 578 s + n (modulo 2^16) = (s + n) AND 65535 580 where MOD is the modulo operation yielding a non-negative integer and 581 AND is the bitwise conjunction operation. 583 Given two sequence numbers s and s', the relation s is less than s' 584 (s < s') is defined by 586 s < s' (modulo 2^16) when 0 < ((s' - s) MOD 2^16) < 32768 588 or equivalently 590 s < s' (modulo 2^16) when s /= s' and ((s' - s) AND 32768) = 0. 592 3.2.2. Node Sequence Number 594 A node's sequence number is a 16-bit integer that is included in 595 route updates sent for routes originated by this node. 597 A node increments its sequence number (modulo 2^16) whenever it 598 receives a request for a new sequence number (Section 3.8.1.2). A 599 node SHOULD NOT increment its sequence number (seqno) spontaneously, 600 since increasing seqnos makes it less likely that other nodes will 601 have feasible alternate routes when their selected routes fail. 603 3.2.3. The Interface Table 605 The interface table contains the list of interfaces on which the node 606 speaks the Babel protocol. Every interface table entry contains the 607 interface's Hello seqno, a 16-bit integer that is sent with each 608 Hello TLV on this interface and is incremented (modulo 2^16) whenever 609 a Hello is sent. (Note that an interface's Hello seqno is unrelated 610 to the node's seqno.) 612 There are two timers associated with each interface table entry -- 613 the Hello timer, which governs the sending of periodic Hello and IHU 614 packets, and the update timer, which governs the sending of periodic 615 route updates. 617 3.2.4. The Neighbour Table 619 The neighbour table contains the list of all neighbouring interfaces 620 from which a Babel packet has been recently received. The neighbour 621 table is indexed by pairs of the form (interface, address), and every 622 neighbour table entry contains the following data: 624 o the local node's interface over which this neighbour is reachable; 626 o the address of the neighbouring interface; 628 o a history of recently received Hello packets from this neighbour; 629 this can, for example, be a sequence of n bits, for some small 630 value n, indicating which of the n hellos most recently sent by 631 this neighbour have been received by the local node; 633 o the "transmission cost" value from the last IHU packet received 634 from this neighbour, or FFFF hexadecimal (infinity) if the IHU 635 hold timer for this neighbour has expired; 637 o the neighbour's expected Hello sequence number, an integer modulo 638 2^16. 640 There are two timers associated with each neighbour entry -- the 641 hello timer, which is initialised from the interval value carried by 642 Hello TLVs, and the IHU timer, which is initialised to a small 643 multiple of the interval carried in IHU TLVs. 645 Note that the neighbour table is indexed by IP addresses, not by 646 router-ids: neighbourship is a relationship between interfaces, not 647 between nodes. Therefore, two nodes with multiple interfaces can 648 participate in multiple neighbourship relationships, a fairly common 649 situation when wireless nodes with multiple radios are involved. 651 3.2.5. The Source Table 653 The source table is used to record feasibility distances. It is 654 indexed by triples of the form (prefix, plen, router-id), and every 655 source table entry contains the following data: 657 o the prefix (prefix, plen), where plen is the prefix length, that 658 this entry applies to; 660 o the router-id of a router originating this prefix; 662 o a pair (seqno, metric), this source's feasibility distance. 664 There is one timer associated with each entry in the source table -- 665 the source garbage-collection timer. It is initialised to a time on 666 the order of minutes and reset as specified in Section 3.7.3. 668 3.2.6. The Route Table 670 The route table contains the routes known to this node. It is 671 indexed by triples of the form (prefix, plen, neighbour), and every 672 route table entry contains the following data: 674 o the source (prefix, plen, router-id) for which this route is 675 advertised; 677 o the neighbour that advertised this route; 679 o the metric with which this route was advertised by the neighbour, 680 or FFFF hexadecimal (infinity) for a recently retracted route; 682 o the sequence number with which this route was advertised; 684 o the next-hop address of this route; 686 o a boolean flag indicating whether this route is selected, i.e., 687 whether it is currently being used for forwarding and is being 688 advertised. 690 There is one timer associated with each route table entry -- the 691 route expiry timer. It is initialised and reset as specified in 692 Section 3.5.4. 694 Of course, the data structure described above is conceptual: actual 695 implementations will likely use a different data structure, for 696 example a table of installed routes and a set of redundant ones, or 697 some more complicated data structure. 699 3.2.7. The Table of Pending Requests 701 The table of pending requests contains a list of seqno requests that 702 the local node has sent (either because they have been originated 703 locally, or because they were forwarded) and to which no reply has 704 been received yet. This table is indexed by prefixes, and every 705 entry in this table contains the following data: 707 o the prefix, router-id, and seqno being requested; 709 o the neighbour, if any, on behalf of which we are forwarding this 710 request; 712 o a small integer indicating the number of times that this request 713 will be resent if it remains unsatisfied. 715 There is one timer associated with each pending request; it governs 716 both the resending of requests and their expiry. 718 3.3. Acknowledged Packets 720 A Babel speaker may request that any neighbour receiving a given 721 packet reply with an explicit acknowledgement within a given time. 722 While the use of acknowledgement requests is optional, every Babel 723 speaker MUST be able to reply to such a request. 725 An acknowledgement MUST be sent to a unicast destination. On the 726 other hand, acknowledgement requests may be sent to either unicast or 727 multicast destinations, in which case they request an acknowledgement 728 from all of the receiving nodes. 730 When to request acknowledgements is a matter of local policy; the 731 simplest strategy is to never request acknowledgements and to rely on 732 periodic updates to ensure that any reachable routes are eventually 733 propagated throughout the routing domain. For increased efficiency, 734 we suggest that acknowledged packets should be used in order to send 735 urgent updates (Section 3.7.2) when the number of neighbours on a 736 given interface is small. Since Babel is designed to deal gracefully 737 with packet loss on unreliable media, sending all packets with 738 acknowledgement requests is not necessary, and not even recommended, 739 as the acknowledgements cause additional traffic and may force 740 additional Address Resolution Protocol (ARP) or Neighbour Discovery 741 exchanges. 743 3.4. Neighbour Acquisition 745 Neighbour acquisition is the process by which a Babel node discovers 746 the set of neighbours heard over each of its interfaces and 747 ascertains bidirectional reachability. On unreliable media, 748 neighbour acquisition additionally provides some statistics that may 749 be useful for link quality computation. 751 Before it can exchange routing information with a neighbour, a Babel 752 node MUST create an entry for that neighbour in the neighbour table. 753 When to do that is an implementation detail; suitable strategies 754 include creating an entry when any Babel packet is received, or 755 creating an entry when a Hello TLV is parsed. Similarly, in order to 756 conserve system resources, an implementation SHOULD discard an entry 757 when it has been unused for long enough; suitable strategies include 758 dropping the neighbour after a timeout, and dropping a neighbour when 759 the associated Hello history becomes empty (see Appendix A.2). 761 3.4.1. Reverse Reachability Detection 763 Every Babel node sends periodic Hellos over each of its interfaces. 764 Each Hello TLV carries an increasing (modulo 2^16) sequence number 765 and the interval between successive periodic packets sent on this 766 particular interface. 768 In addition to the periodic Hello packets, a node MAY send 769 unscheduled Hello packets, e.g., to accelerate link cost estimation 770 when a new neighbour is discovered, or when link conditions have 771 suddenly changed. 773 A node MAY change its Hello interval. The Hello interval MAY be 774 decreased at any time; it SHOULD NOT be increased, except immediately 775 before sending a Hello packet. (Equivalently, a node SHOULD send an 776 unscheduled Hello immediately after increasing its Hello interval.) 778 How to deal with received Hello TLVs and what statistics to maintain 779 are considered local implementation matters; typically, a node will 780 maintain some sort of history of recently received Hellos. A 781 possible algorithm is described in Appendix A.1. 783 After receiving a Hello, or determining that it has missed one, the 784 node recomputes the association's cost (Section 3.4.3) and runs the 785 route selection procedure (Section 3.6). 787 3.4.2. Bidirectional Reachability Detection 789 In order to establish bidirectional reachability, every node sends 790 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since 791 IHUs carry an explicit interval value, they MAY be sent less often 792 than Hellos in order to reduce the amount of routing traffic in dense 793 networks; in particular, they SHOULD be sent less often than Hellos 794 over links with little packet loss. While IHUs are conceptually 795 unicast, they SHOULD be sent to a multicast address in order to avoid 796 an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs 797 in a single packet. 799 In addition to the periodic IHUs, a node MAY, at any time, send an 800 unscheduled IHU packet. It MAY also, at any time, decrease its IHU 801 interval, and it MAY increase its IHU interval immediately before 802 sending an IHU. 804 Every IHU TLV contains two pieces of data: the link's rxcost 805 (reception cost) from the sender's perspective, used by the neighbour 806 for computing link costs (Section 3.4.3), and the interval between 807 periodic IHU packets. A node receiving an IHU updates the value of 808 the sending neighbour's txcost (transmission cost), from its 809 perspective, to the value contained in the IHU, and resets this 810 neighbour's IHU timer to a small multiple of the value received in 811 the IHU. 813 When a neighbour's IHU timer expires, its txcost is set to infinity. 815 After updating a neighbour's txcost, the receiving node recomputes 816 the neighbour's cost (Section 3.4.3) and runs the route selection 817 procedure (Section 3.6). 819 3.4.3. Cost Computation 821 A neighbourship association's link cost is computed from the values 822 maintained in the neighbour table -- namely, the statistics kept in 823 the neighbour table about the reception of Hellos, and the txcost 824 computed from received IHU packets. 826 For every neighbour, a Babel node computes a value known as this 827 neighbour's rxcost. This value is usually derived from the Hello 828 history, which may be combined with other data, such as statistics 829 maintained by the link layer. The rxcost is sent to a neighbour in 830 each IHU. 832 How the txcost and rxcost are combined in order to compute a link's 833 cost is a matter of local policy; as far as Babel's correctness is 834 concerned, only the following conditions MUST be satisfied: 836 o the cost is strictly positive; 838 o if no hellos were received recently, then the cost is infinite; 840 o if the txcost is infinite, then the cost is infinite. 842 Note that while this document does not constrain cost computation any 843 further, not all cost computation strategies will give good results. 844 We give a few examples of strategies for computing a link's cost that 845 are known to work well in practice in Appendix A.2. 847 3.5. Routing Table Maintenance 849 Conceptually, a Babel update is a quintuple (prefix, plen, router-id, 850 seqno, metric), where (prefix, plen) is the prefix for which a route 851 is being advertised, router-id is the router-id of the router 852 originating this update, seqno is a nondecreasing (modulo 2^16) 853 integer that carries the originating router seqno, and metric is the 854 announced metric. 856 Before being accepted, an update is checked against the feasibility 857 condition (Section 3.5.1), which ensures that the route does not 858 create a routing loop. If the feasibility condition is not 859 satisfied, the update is either ignored or treated as a retraction, 860 depending on some other conditions (Section 3.5.4). If the 861 feasibility condition is satisfied, then the update cannot possibly 862 cause a routing loop, and the update is accepted. 864 3.5.1. The Feasibility Condition 866 The feasibility condition is applied to all received updates. The 867 feasibility condition compares the metric in the received update with 868 the metrics of the updates previously sent by the receiving node; 869 updates with finite metrics large enough to cause a loop are 870 discarded. 872 A feasibility distance is a pair (seqno, metric), where seqno is an 873 integer modulo 2^16 and metric is a positive integer. Feasibility 874 distances are compared lexicographically, with the first component 875 inverted: we say that a distance (seqno, metric) is strictly better 876 than a distance (seqno', metric'), written 878 (seqno, metric) < (seqno', metric') 880 when 882 seqno > seqno' or (seqno = seqno' and metric < metric') 884 where sequence numbers are compared modulo 2^16. 886 Given a source (p, plen, router-id), a node's feasibility distance 887 for this source is the minimum, according to the ordering defined 888 above, of the distances of all the finite updates ever sent by this 889 particular node for the prefix (p, plen) and the given router-id. 890 Feasibility distances are maintained in the source table; the exact 891 procedure is given in Section 3.7.3. 893 A received update is feasible when either it is a retraction (its 894 metric is FFFF hexadecimal), or the advertised distance is strictly 895 better, in the sense defined above, than the feasibility distance for 896 the corresponding source. More precisely, a route advertisement 897 carrying the quintuple (prefix, plen, router-id, seqno, metric) is 898 feasible if one of the following conditions holds: 900 o metric is infinite; or 902 o no entry exists in the source table indexed by (router-id, prefix, 903 plen); or 905 o an entry (prefix, plen, router-id, seqno', metric') exists in the 906 source table, and either 908 * seqno' < seqno or 910 * seqno = seqno' and metric < metric'. 912 Note that the feasibility condition considers the metric advertised 913 by the neighbour, not the route's metric; hence, a fluctuation in a 914 neighbour's cost cannot render a selected route unfeasible. 916 3.5.2. Metric Computation 918 A route's metric is computed from the metric advertised by the 919 neighbour and the neighbour's link cost. Just like cost computation, 920 metric computation is considered a local policy matter; as far as 921 Babel is concerned, the function M(c, m) used for computing a metric 922 from a locally computed link cost and the metric advertised by a 923 neighbour MUST only satisfy the following conditions: 925 o if c is infinite, then M(c, m) is infinite; 927 o M is strictly monotonic: M(c, m) > m. 929 Additionally, the metric SHOULD satisfy the following condition: 931 o M is isotonic: if m <= m', then M(c, m) <= M(c, m'). 933 Note that while strict monotonicity is essential to the integrity of 934 the network (persistent routing loops may appear if it is not 935 satisfied), isotonicity is not: if it is not satisfied, Babel will 936 still converge to a locally optimal routing table, but might not 937 reach a global optimum (in fact, such a global optimum may not even 938 exist). 940 As with cost computation, not all strategies for computing route 941 metrics will give good results. In particular, some metrics are more 942 likely than others to lead to routing instabilities (route flapping). 943 In Appendix A.3, we give a number of examples of strictly monotonic, 944 isotonic routing metrics that are known to work well in practice. 946 3.5.3. Encoding of Updates 948 In a large network, the bulk of Babel traffic consists of route 949 updates; hence, some care has been given to encoding them 950 efficiently. An Update TLV itself only contains the prefix, seqno, 951 and metric, while the next hop is derived either from the network- 952 layer source address of the packet or from an explicit Next Hop TLV 953 in the same packet. The router-id is derived from a separate Router- 954 Id TLV in the same packet, which optimises the case when multiple 955 updates are sent with the same router-id. 957 Additionally, a prefix of the advertised prefix can be omitted in an 958 Update TLV, in which case it is copied from a previous Update TLV in 959 the same packet -- this is known as address compression [PACKETBB]. 961 Finally, as a special optimisation for the case when a router-id 962 coincides with the interface-id part of an IPv6 address, the router- 963 id can optionally be derived from the low-order bits of the 964 advertised prefix. 966 The encoding of updates is described in detail in Section 4.6. 968 3.5.4. Route Acquisition 970 When a Babel node receives an update (router-id, prefix, seqno, 971 metric) from a neighbour neigh with a link cost value equal to cost, 972 it checks whether it already has a routing table entry indexed by 973 (neigh, router-id, prefix). 975 If no such entry exists: 977 o if the update is unfeasible, it is ignored; 979 o if the metric is infinite (the update is a retraction), the update 980 is ignored; 982 o otherwise, a new route table entry is created, indexed by (neigh, 983 router-id, prefix), with seqno equal to seqno and an advertised 984 metric equal to the metric carried by the update. 986 If such an entry exists: 988 o if the entry is currently installed and the update is unfeasible, 989 then the behaviour depends on whether the router-ids of the two 990 entries match. If the router-ids are different, the update is 991 treated as though it were a retraction (i.e., as though the metric 992 were FFFF hexadecimal). If the router-ids are equal, the update 993 is ignored; 995 o otherwise (i.e., if either the update is feasible or the entry is 996 not currently installed), then the entry's sequence number, 997 advertised metric, metric, and router-id are updated and, unless 998 the advertised metric is infinite, the route's expiry timer is 999 reset to a small multiple of the Interval value included in the 1000 update. 1002 When a route's expiry timer triggers, the behaviour depends on 1003 whether the route's metric is finite. If the metric is finite, it is 1004 set to infinity and the expiry timer is reset. If the metric is 1005 already infinite, the route is flushed from the route table. 1007 After the routing table is updated, the route selection procedure 1008 (Section 3.6) is run. 1010 3.5.5. Hold Time 1012 When a prefix p is retracted, because all routes are unfeasible, too 1013 old, or have an infinite metric, and a shorter prefix p' that covers 1014 p is reachable, p' cannot in general be used for routing packets 1015 destined to p without running the risk of creating a routing loop 1016 (Section 2.8). 1018 To avoid this issue, whenever a prefix is retracted, a routing table 1019 entry with infinite metric is maintained as described in 1020 Section 3.5.4 above, and packets destined for that prefix MUST NOT be 1021 forwarded by following a route for a shorter prefix. The infinite 1022 metric entry is maintained until it is superseded by a feasible 1023 update; if no such update arrives within the route hold time, the 1024 entry is flushed. 1026 3.6. Route Selection 1028 Route selection is the process by which a single route for a given 1029 prefix is selected to be used for forwarding packets and to be re- 1030 advertised to a node's neighbours. 1032 Babel is designed to allow flexible route selection policies. As far 1033 as the protocol's correctness is concerned, the route selection 1034 policy MUST only satisfy the following properties: 1036 o a route with infinite metric (a retracted route) is never 1037 selected; 1039 o an unfeasible route is never selected. 1041 Note, however, that Babel does not naturally guarantee the stability 1042 of routing, and configuring conflicting route selection policies on 1043 different routers may lead to persistent route oscillation. 1045 Defining a good route selection policy for Babel is an open research 1046 problem. Route selection can take into account multiple mutually 1047 contradictory criteria; in roughly decreasing order of importance, 1048 these are: 1050 o routes with a small metric should be preferred over routes with a 1051 large metric; 1053 o switching router-ids should be avoided; 1055 o routes through stable neighbours should be preferred over routes 1056 through unstable ones; 1058 o stable routes should be preferred over unstable ones; 1060 o switching next hops should be avoided. 1062 A simple strategy is to choose the feasible route with the smallest 1063 metric, with a small amount of hysteresis applied to avoid switching 1064 router-ids. 1066 After the route selection procedure is run, triggered updates 1067 (Section 3.7.2) and requests (Section 3.8.2) are sent. 1069 3.7. Sending Updates 1071 A Babel speaker advertises to its neighbours its set of selected 1072 routes. Normally, this is done by sending one or more multicast 1073 packets containing Update TLVs on all of its connected interfaces; 1074 however, on link technologies where multicast is significantly more 1075 expensive than unicast, a node MAY choose to send multiple copies of 1076 updates in unicast packets when the number of neighbours is small. 1078 Additionally, in order to ensure that any black-holes are reliably 1079 cleared in a timely manner, a Babel node sends retractions (updates 1080 with an infinite metric) for any recently retracted prefixes. 1082 If an update is for a route injected into the Babel domain by the 1083 local node (e.g., the address of a local interface, the prefix of a 1084 directly attached network, or redistributed from a different routing 1085 protocol), the router-id is set to the local id, the metric is set to 1086 some arbitrary finite value (typically 0), and the seqno is set to 1087 the local router's sequence number. 1089 If an update is for a route learned from another Babel speaker, the 1090 router-id and sequence number are copied from the routing table 1091 entry, and the metric is computed as specified in Section 3.5.2. 1093 3.7.1. Periodic Updates 1095 Every Babel speaker periodically advertises all of its selected 1096 routes on all of its interfaces, including any recently retracted 1097 routes. Since Babel doesn't suffer from routing loops (there is no 1098 "counting to infinity") and relies heavily on triggered updates 1099 (Section 3.7.2), this full dump only needs to happen infrequently. 1101 3.7.2. Triggered Updates 1103 In addition to the periodic routing updates, a Babel speaker sends 1104 unscheduled, or triggered, updates in order to inform its neighbours 1105 of a significant change in the network topology. 1107 A change of router-id for the selected route to a given prefix may be 1108 indicative of a routing loop in formation; hence, a node MUST send a 1109 triggered update in a timely manner whenever it changes the selected 1110 router-id for a given destination. Additionally, it SHOULD make a 1111 reasonable attempt at ensuring that all neighbours receive this 1112 update. 1114 There are two strategies for ensuring that. If the number of 1115 neighbours is small, then it is reasonable to send the update 1116 together with an acknowledgement request; the update is resent until 1117 all neighbours have acknowledged the packet, up to some number of 1118 times. If the number of neighbours is large, however, requesting 1119 acknowledgements from all of them might cause a non-negligible amount 1120 of network traffic; in that case, it may be preferable to simply 1121 repeat the update some reasonable number of times (say, 5 for 1122 wireless and 2 for wired links). 1124 A route retraction is somewhat less worrying: if the route retraction 1125 doesn't reach all neighbours, a black-hole might be created, which, 1126 unlike a routing loop, does not endanger the integrity of the 1127 network. When a route is retracted, a node SHOULD send a triggered 1128 update and SHOULD make a reasonable attempt at ensuring that all 1129 neighbours receive this retraction. 1131 Finally, a node MAY send a triggered update when the metric for a 1132 given prefix changes in a significant manner, either due to a 1133 received update or because a link cost has changed. A node SHOULD 1134 NOT send triggered updates for other reasons, such as when there is a 1135 minor fluctuation in a route's metric, when the selected next hop 1136 changes, or to propagate a new sequence number (except to satisfy a 1137 request, as specified in Section 3.8). 1139 3.7.3. Maintaining Feasibility Distances 1141 Before sending an update (prefix, plen, router-id, seqno, metric) 1142 with finite metric (i.e., not a route retraction), a Babel node 1143 updates the feasibility distance maintained in the source table. 1144 This is done as follows. 1146 If no entry indexed by (prefix, plen, router-id) exists in the source 1147 table, then one is created with value (prefix, plen, router-id, 1148 seqno, metric). 1150 If an entry (prefix, plen, router-id, seqno', metric') exists, then 1151 it is updated as follows: 1153 o if seqno > seqno', then seqno' := seqno, metric' := metric; 1155 o if seqno = seqno' and metric' > metric, then metric' := metric; 1157 o otherwise, nothing needs to be done. 1159 The garbage-collection timer for the entry is then reset. Note that 1160 the garbage-collection timer is not reset when a retraction is sent. 1162 When the garbage-collection timer expires, the entry is removed from 1163 the source table. 1165 3.7.4. Split Horizon 1167 When running over a transitive, symmetric link technology, e.g., a 1168 point-to-point link or a wired LAN technology such as Ethernet, a 1169 Babel node SHOULD use an optimisation known as split horizon. When 1170 split horizon is used on a given interface, a routing update is not 1171 sent on this particular interface when the advertised route was 1172 learnt from a neighbour over the same interface. 1174 Split horizon SHOULD NOT be applied to an interface unless the 1175 interface is known to be symmetric and transitive; in particular, 1176 split horizon is not applicable to decentralised wireless link 1177 technologies (e.g., IEEE 802.11 in ad hoc mode). 1179 3.8. Explicit Route Requests 1181 In normal operation, a node's routing table is populated by the 1182 regular and triggered updates sent by its neighbours. Under some 1183 circumstances, however, a node sends explicit requests to cause a 1184 resynchronisation with the source after a mobility event or to 1185 prevent a route from spuriously expiring. 1187 The Babel protocol provides two kinds of explicit requests: route 1188 requests, which simply request an update for a given prefix, and 1189 seqno requests, which request an update for a given prefix with a 1190 specific sequence number. The former are never forwarded; the latter 1191 are forwarded if they cannot be satisfied by a neighbour. 1193 3.8.1. Handling Requests 1195 Upon receiving a request, a node either forwards the request or sends 1196 an update in reply to the request, as described in the following 1197 sections. If this causes an update to be sent, the update is either 1198 sent to a multicast address on the interface on which the request was 1199 received, or to the unicast address of the neighbour that sent the 1200 update. 1202 The exact behaviour is different for route requests and seqno 1203 requests. 1205 3.8.1.1. Route Requests 1207 When a node receives a route request for a prefix (prefix, plen), it 1208 checks its route table for a selected route to this exact prefix. If 1209 such a route exists, it MUST send an update; if such a route does 1210 not, it MUST send a retraction for that prefix. 1212 When a node receives a wildcard route request, it SHOULD send a full 1213 routing table dump. 1215 3.8.1.2. Seqno Requests 1217 When a node receives a seqno request for a given router-id and 1218 sequence number, it checks whether its routing table contains a 1219 selected entry for that prefix. If a selected route for the given 1220 prefix exists, it has finite metric, and either the router-ids are 1221 different or the router-ids are equal and the entry's sequence number 1222 is no smaller than the requested sequence number, the node MUST send 1223 an update for the given prefix. If the router-ids match but the 1224 requested seqno is larger (modulo 2^16) than the route entry's, the 1225 node compares the router-id against its own router-id. If the 1226 router-id is its own, then it increases its sequence number by 1 and 1227 sends an update. A node MUST NOT increase its sequence number by 1228 more than 1 in response to a seqno request. 1230 Otherwise, if the requested router-id is not its own, the received 1231 request's hop count is 2 or more, and the node has a route (not 1232 necessarily a feasible one) for the requested prefix that does not 1233 use the requestor as a next hop, the node MUST forward the request if 1234 it has a feasible route to the requested prefix and it is advertising 1235 this prefix to neighbours, and SHOULD forward the request if it has a 1236 (not necessarily feasible) route to the requested prefix. It does so 1237 by decreasing the hop count and sending the request in a unicast 1238 packet destined to a neighbour that advertises the given prefix and 1239 that is not the neighbour from which the request was received. 1241 A node SHOULD maintain a list of recently forwarded requests and 1242 forward the reply (an update with a sufficiently large seqno) in a 1243 timely manner. A node SHOULD compare every incoming request against 1244 its list of recently forwarded requests and avoid forwarding it if it 1245 is redundant. 1247 Since the request-forwarding mechanism does not necessarily obey the 1248 feasibility condition, it may get caught in routing loops; hence, 1249 requests carry a hop count to limit the time for which they remain in 1250 the network. However, since requests are only ever forwarded as 1251 unicast packets, the initial hop count need not be kept particularly 1252 low, and performing an expanding horizon search is not necessary. A 1253 request MUST NOT be forwarded to a multicast address, and it MUST NOT 1254 be forwarded to multiple neighbours. 1256 3.8.2. Sending Requests 1258 A Babel node MAY send a route or seqno request at any time, to a 1259 multicast or a unicast address; there is only one case when 1260 originating requests is required (Section 3.8.2.1). 1262 3.8.2.1. Avoiding Starvation 1264 When a route is retracted or expires, a Babel node usually switches 1265 to another feasible route for the same prefix. It may be the case, 1266 however, that no such routes are available. 1268 A node that has lost all feasible routes to a given destination but 1269 still has unexpired unfeasible routes to that destination, MUST send 1270 a seqno request; if it doesn't have any such routes, it MAY still 1271 send a seqno request. The router-id of the request is set to the 1272 router-id of the route that it has just lost, and the requested seqno 1273 is the value contained in the source table, plus 1. 1275 If the node has any (unfeasible) routes to the requested destination, 1276 then it MUST send the request to at least one of the next-hop 1277 neighbours that advertised these routes, and SHOULD send it to all of 1278 them; in any case, it MAY send the request to any other neighbours, 1279 whether they advertise a route to the requested destination or not. 1280 A simple implementation strategy is therefore to unconditionally 1281 multicast the request over all attached interfaces. 1283 Similar requests will be sent by other nodes that are affected by the 1284 route's loss. If the network is still connected, and assuming no 1285 packet loss, then at least one of these requests will be forwarded to 1286 the source, resulting in a route being advertised with a new sequence 1287 number. (Note that, due to duplicate suppression, only a small 1288 number of such requests will actually reach the source.) 1289 In order to compensate for packet loss, a node SHOULD repeat such a 1290 request a small number of times if no route becomes feasible within a 1291 short time. Under heavy packet loss, however, all such requests 1292 might be lost; in that case, the second mechanism in the next section 1293 will eventually ensure that a new seqno is received. 1295 3.8.2.2. Dealing with Unfeasible Updates 1297 When a route's metric increases, a node might receive an unfeasible 1298 update for a route that it has currently selected. As specified in 1299 Section 3.5.1, the receiving node will either ignore the update or 1300 retract the route. 1302 In order to keep routes from spuriously expiring because they have 1303 become unfeasible, a node SHOULD send a unicast seqno request 1304 whenever it receives an unfeasible update for a route that is 1305 currently selected. The requested sequence number is computed from 1306 the source table as above. 1308 Additionally, since metric computation does not necessarily coincide 1309 with the delay in propagating updates, a node might receive an 1310 unfeasible update from a currently unselected neighbour that is 1311 preferable to the currently selected route (e.g., because it has a 1312 much smaller metric); in that case, the node SHOULD send a unicast 1313 seqno request to the neighbour that advertised the preferable update. 1315 3.8.2.3. Preventing Routes from Expiring 1317 In normal operation, a route's expiry timer should never trigger: 1318 since a route's hold time is computed from an explicit interval 1319 included in Update TLVs, a new update (possibly a retraction) should 1320 arrive in time to prevent a route from expiring. 1322 In the presence of packet loss, however, it may be the case that no 1323 update is successfully received for an extended period of time, 1324 causing a route to expire. In order to avoid such spurious expiry, 1325 shortly before a selected route expires, a Babel node SHOULD send a 1326 unicast route request to the neighbour that advertised this route; 1327 since nodes always send retractions in response to non-wildcard route 1328 requests (Section 3.8.1.1), this will usually result in either the 1329 route being refreshed or a retraction being received. 1331 3.8.2.4. Acquiring New Neighbours 1333 In order to speed up convergence after a mobility event, a node MAY 1334 send a unicast wildcard request after acquiring a new neighbour. 1335 Additionally, a node MAY send a small number of multicast wildcard 1336 requests shortly after booting. Note that doing that carelessly can 1337 cause serious congestion when a whole network is rebooted, especially 1338 on link layers with high per-packet overhead (e.g., IEEE 802.11). 1340 4. Protocol Encoding 1342 A Babel packet is sent as the body of a UDP datagram, with network- 1343 layer hop count set to 1, destined to a well-known multicast address 1344 or to a unicast address, over IPv4 or IPv6; in the case of IPv6, 1345 these addresses are link-local. Both the source and destination UDP 1346 port are set to a well-known port number. A Babel packet MUST be 1347 silently ignored unless its source address is either a link-local 1348 IPv6 address, or an IPv4 address belonging to the local network, and 1349 its source port is the well-known Babel port. Babel packets MUST NOT 1350 be sent as IPv6 Jumbograms. 1352 In order to minimise the number of packets being sent while avoiding 1353 lower-layer fragmentation, a Babel node SHOULD attempt to maximise 1354 the size of the packets it sends, up to the outgoing interface's MTU 1355 adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets 1356 for UDP/IPv6). It MUST NOT send packets larger than the attached 1357 interface's MTU (adjusted for lower-layer headers) or 512 octets, 1358 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower- 1359 layer headers. Every Babel speaker MUST be able to receive packets 1360 that are as large as any attached interface's MTU (adjusted for 1361 lower-layer headers) or 512 octets, whichever is larger. 1363 In order to avoid global synchronisation of a Babel network and to 1364 aggregate multiple TLVs into large packets, a Babel node MUST buffer 1365 every TLV and delay sending a UDP packet by a small, randomly chosen 1366 delay [JITTER]. In order to allow accurate computation of packet 1367 loss rates, this delay MUST NOT be larger than half the advertised 1368 Hello interval. 1370 4.1. Data Types 1372 4.1.1. Interval 1374 Relative times are carried as 16-bit values specifying a number of 1375 centiseconds (hundredths of a second). This allows times up to 1376 roughly 11 minutes with a granularity of 10ms, which should cover all 1377 reasonable applications of Babel. 1379 4.1.2. Router-Id 1381 A router-id is an arbitrary 8-octet. A router-id MUST NOT consist of 1382 either all zeroes or all ones. Router-ids SHOULD be assigned in 1383 modified EUI-64 format [ADDRARCH]. 1385 4.1.3. Address 1387 Since the bulk of the protocol is taken by addresses, multiple ways 1388 of encoding addresses are defined. Additionally, a common subnet 1389 prefix may be omitted when multiple addresses are sent in a single 1390 packet -- this is known as address compression [PACKETBB]. 1392 Address encodings: 1394 o AE 0: wildcard address. The value is 0 octets long. 1396 o AE 1: IPv4 address. Compression is allowed. 4 octets or less. 1398 o AE 2: IPv6 address. Compression is allowed. 16 octets or less. 1400 o AE 3: link-local IPv6 address. The value is 8 octets long, a 1401 prefix of fe80::/64 is implied. 1403 The address family of an address is either IPv4 or IPv6; it is 1404 undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3. 1406 4.1.4. Prefixes 1408 A network prefix is encoded just like a network address, but it is 1409 stored in the smallest number of octets that are enough to hold the 1410 significant bits (up to the prefix length). 1412 4.2. Packet Format 1414 A Babel packet consists of a 4-octet header, followed by a sequence 1415 of TLVs. 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 | Magic | Version | Body length | 1421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1422 | Packet Body ... 1423 +-+-+-+-+-+-+-+-+-+-+-+-+- 1425 Fields : 1427 Magic The arbitrary but carefully chosen value 42 (decimal); 1428 packets with a first octet different from 42 MUST be 1429 silently ignored. 1431 Version This document specifies version 2 of the Babel protocol. 1432 Packets with a second octet different from 2 MUST be 1433 silently ignored. 1435 Body length The length in octets of the body following the packet 1436 header. 1438 Body The packet body; a sequence of TLVs. 1440 Any data following the body MUST be silently ignored. 1442 4.3. TLV Format 1444 With the exception of Pad1, all TLVs have the following structure: 1446 0 1 2 3 1447 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 1448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1449 | Type | Length | Payload... 1450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1452 Fields : 1454 Type The type of the TLV. 1456 Length The length of the body, exclusive of the Type and Length 1457 fields. If the body is longer than the expected length of 1458 a given type of TLV, any extra data MUST be silently 1459 ignored. 1461 Payload The TLV payload, which consists of a body and, for selected 1462 TLV types, an optional list of sub-TLVs. 1464 TLVs with an unknown type value MUST be silently ignored. 1466 4.4. Sub-TLV Format 1468 Every TLV carries an explicit length in its header; however, most 1469 TLVs are self-terminating, in the sense that it is possible to 1470 determine the length of the body without reference to the explicit 1471 TLV length. If a TLV has a self-terminating format, then it MAY 1472 allow a sequence of sub-TLVs to follow the body. 1474 Sub-TLVs have the same structure as TLVs. With the exception of 1475 PAD1, all TLVs have the following structure: 1477 0 1 2 3 1478 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 1479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1480 | Type | Length | Body... 1481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1483 Fields : 1485 Type The type of the sub-TLV. 1487 Length The length of the body, in octets, exclusive of the Type 1488 and Length fields. 1490 Body The sub-TLV body, the interpretation of which depends on 1491 both the type of the sub-TLV and the type of the TLV within 1492 which it is embedded. 1494 The most-significant bit of the sub-TLV, called the mandatory bit, 1495 indicates how to handle unknown sub-TLVs. If the mandatory bit is 1496 not set, then an unknown sub-TLV MUST be silently ignored, and the 1497 rest of the TLV processed normally. If the mandatory bit is set, 1498 then the whole enclosing TLV MUST be silently ignored (except for 1499 updating the parser state by a Router-ID, Next-Hop or Update TLV, see 1500 Section 4.6.7, Section 4.6.8, and Section 4.6.9). 1502 4.5. Parser state 1504 Babel uses a stateful parser: a TLV may refer to data from a previous 1505 TLV. Babel's parser state consists of the following pieces of data: 1507 o for each address encoding that allows compression, the current 1508 default prefix; this is undefined at the start of the packet, and 1509 is updated by an Update TLV with flag 80 hexadecimal set 1510 (Section 4.6.9); 1512 o for each address family (IPv4 or IPv6), the current next-hop; this 1513 is the source address of the enclosing packet for the matching 1514 address family at the start of a packet, and is updated by the 1515 Next-Hop TLV (Section 4.6.8); 1517 o the current router-id; this is undefined at the start of the 1518 packet, and is updated by both the Router-ID TLV (Section 4.6.7) 1519 and the Update TLV with flag 40 hexadecimal set. 1521 Since the parser state is separate from the bulk of Babel's state, 1522 and for correct parsing must be identical across implementations, it 1523 is updated before checking for mandatory TLVs: parsing a TLV updates 1524 the parser state even if the TLV is otherwise ignored due to an 1525 unknown mandatory sub-TLV. 1527 4.6. Details of Specific TLVs 1529 4.6.1. Pad1 1531 0 1532 0 1 2 3 4 5 6 7 1533 +-+-+-+-+-+-+-+-+ 1534 | Type = 0 | 1535 +-+-+-+-+-+-+-+-+ 1537 Fields : 1539 Type Set to 0 to indicate a Pad1 TLV. 1541 This TLV is silently ignored on reception. 1543 4.6.2. PadN 1545 0 1 2 3 1546 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 1547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1548 | Type = 1 | Length | MBZ... 1549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 1551 Fields : 1553 Type Set to 1 to indicate a PadN TLV. 1555 Length The length of the body, exclusive of the Type and Length 1556 fields. 1558 MBZ Set to 0 on transmission. 1560 This TLV is silently ignored on reception. 1562 4.6.3. Acknowledgement Request 1564 0 1 2 3 1565 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 1566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1567 | Type = 2 | Length | Reserved | 1568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1569 | Nonce | Interval | 1570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1571 This TLV requests that the receiver send an Acknowledgement TLV 1572 within the number of centiseconds specified by the Interval field. 1574 Fields : 1576 Type Set to 2 to indicate an Acknowledgement Request TLV. 1578 Length The length of the body, exclusive of the Type and Length 1579 fields. 1581 Reserved Sent as 0 and MUST be ignored on reception. 1583 Nonce An arbitrary value that will be echoed in the receiver's 1584 Acknowledgement TLV. 1586 Interval A time interval in centiseconds after which the sender will 1587 assume that this packet has been lost. This MUST NOT be 0. 1588 The receiver MUST send an acknowledgement before this time 1589 has elapsed (with a margin allowing for propagation time). 1591 This TLV is self-terminating, and allows sub-TLVs. 1593 4.6.4. Acknowledgement 1595 0 1 2 3 1596 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 1597 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1598 | Type = 3 | Length | Nonce | 1599 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1601 This TLV is sent by a node upon receiving an Acknowledgement Request. 1603 Fields : 1605 Type Set to 3 to indicate an Acknowledgement TLV. 1607 Length The length of the body, exclusive of the Type and Length 1608 fields. 1610 Nonce Set to the Nonce value of the Acknowledgement Request that 1611 prompted this Acknowledgement. 1613 Since nonce values are not globally unique, this TLV MUST be sent to 1614 a unicast address. 1616 This TLV is self-terminating, and allows sub-TLVs. 1618 4.6.5. Hello 1620 0 1 2 3 1621 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 1622 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1623 | Type = 4 | Length | Reserved | 1624 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1625 | Seqno | Interval | 1626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1628 This TLV is used for neighbour discovery and for determining a link's 1629 reception cost. 1631 Fields : 1633 Type Set to 4 to indicate a Hello TLV. 1635 Length The length of the body, exclusive of the Type and Length 1636 fields. 1638 Reserved Sent as 0 and MUST be ignored on reception. 1640 Seqno The value of the sending node's Hello seqno for this 1641 interface. 1643 Interval An upper bound, expressed in centiseconds, on the time 1644 after which the sending node will send a new Hello TLV. 1645 This MUST NOT be 0. 1647 Since there is a single seqno counter for all the Hellos sent by a 1648 given node over a given interface, this TLV MUST be sent to a 1649 multicast destination. In order to avoid large discontinuities in 1650 link quality, multiple Hello TLVs SHOULD NOT be sent in the same 1651 packet. 1653 This TLV is self-terminating, and allows sub-TLVs. 1655 4.6.6. IHU 1657 0 1 2 3 1658 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 1659 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1660 | Type = 5 | Length | AE | Reserved | 1661 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1662 | Rxcost | Interval | 1663 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1664 | Address... 1665 +-+-+-+-+-+-+-+-+-+-+-+- 1666 An IHU ("I Heard You") TLV is used for confirming bidirectional 1667 reachability and carrying a link's transmission cost. 1669 Fields : 1671 Type Set to 5 to indicate an IHU TLV. 1673 Length The length of the body, exclusive of the Type and Length 1674 fields. 1676 AE The encoding of the Address field. This should be 1 or 3 1677 in most cases. As an optimisation, it MAY be 0 if the TLV 1678 is sent to a unicast address, if the association is over a 1679 point-to-point link, or when bidirectional reachability is 1680 ascertained by means outside of the Babel protocol. 1682 Reserved Sent as 0 and MUST be ignored on reception. 1684 Rxcost The rxcost according to the sending node of the interface 1685 whose address is specified in the Address field. The value 1686 FFFF hexadecimal (infinity) indicates that this interface 1687 is unreachable. 1689 Interval An upper bound, expressed in centiseconds, on the time 1690 after which the sending node will send a new IHU; this MUST 1691 NOT be 0. The receiving node will use this value in order 1692 to compute a hold time for this symmetric association. 1694 Address The address of the destination node, in the format 1695 specified by the AE field. Address compression is not 1696 allowed. 1698 Conceptually, an IHU is destined to a single neighbour. However, IHU 1699 TLVs contain an explicit destination address, and it SHOULD be sent 1700 to a multicast address, as this allows aggregation of IHUs destined 1701 to distinct neighbours into a single packet and avoids the need for 1702 an ARP or Neighbour Discovery exchange when a neighbour is not being 1703 used for data traffic. 1705 IHU TLVs with an unknown value for the AE field MUST be silently 1706 ignored. 1708 This TLV is self-terminating, and allows sub-TLVs. 1710 4.6.7. Router-Id 1712 0 1 2 3 1713 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 1714 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1715 | Type = 6 | Length | Reserved | 1716 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1717 | | 1718 + Router-Id + 1719 | | 1720 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1722 A Router-Id TLV establishes a router-id that is implied by subsequent 1723 Update TLVs. This TLV sets the router-id even if it is otherwise 1724 ignored due to an unknown mandatory sub-TLV. 1726 Fields : 1728 Type Set to 6 to indicate a Router-Id TLV. 1730 Length The length of the body, exclusive of the Type and Length 1731 fields. 1733 Reserved Sent as 0 and MUST be ignored on reception. 1735 Router-Id The router-id for routes advertised in subsequent Update 1736 TLVs. This MUST NOT consist of all zeroes or all ones. 1738 This TLV is self-terminating, and allows sub-TLVs. 1740 4.6.8. Next Hop 1742 0 1 2 3 1743 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 1744 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1745 | Type = 7 | Length | AE | Reserved | 1746 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1747 | Next hop... 1748 +-+-+-+-+-+-+-+-+-+-+-+- 1750 A Next Hop TLV establishes a next-hop address for a given address 1751 family (IPv4 or IPv6) that is implied by subsequent Update TLVs. 1752 This TLV sets up the next-hop for subsequent Update TLVs even if it 1753 is ignored due to an unknown mandatory sub-TLV. 1755 Fields : 1757 Type Set to 7 to indicate a Next Hop TLV. 1759 Length The length of the body, exclusive of the Type and Length 1760 fields. 1762 AE The encoding of the Address field. This SHOULD be 1 or 3 1763 and MUST NOT be 0. 1765 Reserved Sent as 0 and MUST be ignored on reception. 1767 Next hop The next-hop address advertised by subsequent Update TLVs, 1768 for this address family. 1770 When the address family matches the network-layer protocol that this 1771 packet is transported over, a Next Hop TLV is not needed: in that 1772 case, the next hop is taken to be the source address of the packet. 1774 Next Hop TLVs with an unknown value for the AE field MUST be silently 1775 ignored. 1777 This TLV is self-terminating, and allows sub-TLVs. 1779 4.6.9. Update 1781 0 1 2 3 1782 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 1783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1784 | Type = 8 | Length | AE | Flags | 1785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1786 | Plen | Omitted | Interval | 1787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1788 | Seqno | Metric | 1789 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1790 | Prefix... 1791 +-+-+-+-+-+-+-+-+-+-+-+- 1793 An Update TLV advertises or retracts a route. As an optimisation, 1794 this can also have the side effect of establishing a new implied 1795 router-id and a new default prefix. 1797 Fields : 1799 Type Set to 8 to indicate an Update TLV. 1801 Length The length of the body, exclusive of the Type and Length 1802 fields. 1804 AE The encoding of the Prefix field. 1806 Flags The individual bits of this field specify special handling 1807 of this TLV (see below). Every node MUST be able to 1808 interpret the flags with values 80 and 40 hexadecimal; 1809 unknown flags MUST be silently ignored. 1811 Plen The length of the advertised prefix. 1813 Omitted The number of octets that have been omitted at the 1814 beginning of the advertised prefix and that should be taken 1815 from a preceding Update TLV with the flag with value 80 1816 hexadecimal set. 1818 Interval An upper bound, expressed in centiseconds, on the time 1819 after which the sending node will send a new update for 1820 this prefix. This MUST NOT be 0 and SHOULD NOT be less 1821 than 10. The receiving node will use this value to compute 1822 a hold time for this routing table entry. The value FFFF 1823 hexadecimal (infinity) expresses that this announcement 1824 will not be repeated unless a request is received 1825 (Section 3.8.2.3). 1827 Seqno The originator's sequence number for this update. 1829 Metric The sender's metric for this route. The value FFFF 1830 hexadecimal (infinity) means that this is a route 1831 retraction. 1833 Prefix The prefix being advertised. This field's size is (Plen/8 1834 - Omitted) rounded upwards. 1836 The Flags field is interpreted as follows: 1838 o if the bit with value 80 hexadecimal is set, then this Update 1839 establishes a new default prefix for subsequent Update TLVs with a 1840 matching address encoding within the same packet, even if this TLV 1841 is otherwise ignored due to an unknown mandatory sub-TLV; 1843 o if the bit with value 40 hexadecimal is set, then this TLV 1844 establishes a new default router-id for this TLV and subsequent 1845 Update TLVs in the same packet, even if this TLV is otherwise 1846 ignored due to an unknown mandatory sub-TLV. This router-id is 1847 computed from the first address of the advertised prefix as 1848 follows: 1850 * if the length of the address is 8 octets or more, then the new 1851 router-id is taken from the 8 last octets of the address; 1853 * if the length of the address is smaller than 8 octets, then the 1854 new router-id consists of the required number of zero octets 1855 followed by the address, i.e., the address is stored on the 1856 right of the router-id. For example, for an IPv4 address, the 1857 router-id consists of 4 octets of zeroes followed by the IPv4 1858 address. 1860 The prefix being advertised by an Update TLV is computed as follows: 1862 o the first Omitted octets of the prefix are taken from the previous 1863 Update TLV with flag 80 hexadecimal set and the same address 1864 encoding, even if it was ignored due to an unknown mandatory sub- 1865 TLV; 1867 o the next (Plen/8 - Omitted) rounded upwards octets are taken from 1868 the Prefix field; 1870 o the remaining octets are set to 0. 1872 If the Metric field is finite, the router-id of the originating node 1873 for this announcement is taken from the prefix advertised by this 1874 Update if the bit with value 40 hexadecimal is set in the Flags 1875 field, computed as described above. Otherwise, it is taken either 1876 from the preceding Router-Id packet, or the preceding Update packet 1877 with flag 40 hexadecimal set, whichever comes last, even if that TLV 1878 is otherwise ignored due to an unknown mandatory sub-TLV. 1880 The next-hop address for this update is taken from the last preceding 1881 Next Hop TLV with a matching address family (IPv4 or IPv6) in the 1882 same packet even if it was otherwise ignored due to an unknown 1883 mandatory sub-TLV; if no such TLV exists, it is taken from the 1884 network-layer source address of this packet. 1886 If the metric field is FFFF hexadecimal, this TLV specifies a 1887 retraction. In that case, the current router-id and the Seqno are 1888 not used. AE MAY then be 0, in which case this Update retracts all 1889 of the routes previously advertised on this interface. 1891 Update TLVs with an unknown value for the AE field MUST be silently 1892 ignored. 1894 This TLV is self-terminating, and allows sub-TLVs. 1896 4.6.10. Route Request 1897 0 1 2 3 1898 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 1899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1900 | Type = 9 | Length | AE | Plen | 1901 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1902 | Prefix... 1903 +-+-+-+-+-+-+-+-+-+-+-+- 1905 A Route Request TLV prompts the receiver to send an update for a 1906 given prefix, or a full routing table dump. 1908 Fields : 1910 Type Set to 9 to indicate a Route Request TLV. 1912 Length The length of the body, exclusive of the Type and Length 1913 fields. 1915 AE The encoding of the Prefix field. The value 0 specifies 1916 that this is a request for a full routing table dump (a 1917 wildcard request). 1919 Plen The length of the requested prefix. 1921 Prefix The prefix being requested. This field's size is Plen/8 1922 rounded upwards. 1924 A Request TLV prompts the receiving node to send an update message 1925 for the prefix specified by the AE, Plen, and Prefix fields, or a 1926 full dump of its routing table if AE is 0 (in which case Plen MUST be 1927 0 and Prefix is of length 0). A Request may be sent to a unicast 1928 address if it is destined to a single node, or to a multicast address 1929 if the request is destined to all of the neighbours of the sending 1930 interface. 1932 This TLV is self-terminating, and allows sub-TLVs. 1934 4.6.11. Seqno Request 1935 0 1 2 3 1936 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 1937 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1938 | Type = 10 | Length | AE | Plen | 1939 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1940 | Seqno | Hop Count | Reserved | 1941 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1942 | | 1943 + Router-Id + 1944 | | 1945 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1946 | Prefix... 1947 +-+-+-+-+-+-+-+-+-+-+ 1949 A Seqno Request TLV prompts the receiver to send an Update for a 1950 given prefix with a given sequence number, or to forward the request 1951 further if it cannot be satisfied locally. 1953 Fields : 1955 Type Set to 10 to indicate a Seqno Request message. 1957 Length The length of the body, exclusive of the Type and Length 1958 fields. 1960 AE The encoding of the Prefix field. This MUST NOT be 0. 1962 Plen The length of the requested prefix. 1964 Seqno The sequence number that is being requested. 1966 Hop Count The maximum number of times that this TLV may be forwarded, 1967 plus 1. This MUST NOT be 0. 1969 Reserved Sent as 0 and MUST be ignored on reception. 1971 Router Id The Router-Id that is being requested. This MUST NOT 1972 consist of all zeroes or all ones. 1974 Prefix The prefix being requested. This field's size is Plen/8 1975 rounded upwards. 1977 A Seqno Request TLV prompts the receiving node to send an Update for 1978 the prefix specified by the AE, Plen, and Prefix fields, with either 1979 a router-id different from what is specified by the Router-Id field, 1980 or a Seqno no less (modulo 2^16) than what is specified by the Seqno 1981 field. If this request cannot be satisfied locally, then it is 1982 forwarded according to the rules set out in Section 3.8.1.2. 1984 While a Seqno Request MAY be sent to a multicast address, it MUST NOT 1985 be forwarded to a multicast address and MUST NOT be forwarded to more 1986 than one neighbour. A request MUST NOT be forwarded if its Hop Count 1987 field is 1. 1989 This TLV is self-terminating, and allows sub-TLVs. 1991 4.7. Details of specific sub-TLVs 1993 4.7.1. Pad1 1995 0 1996 0 1 2 3 4 5 6 7 1997 +-+-+-+-+-+-+-+-+ 1998 | Type = 0 | 1999 +-+-+-+-+-+-+-+-+ 2001 Fields : 2003 Type Set to 0 to indicate a Pad1 sub-TLV. 2005 This sub-TLV is silently ignored on reception. 2007 4.7.2. PadN 2009 0 1 2 3 2010 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 2011 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2012 | Type = 1 | Length | MBZ... 2013 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- 2015 Fields : 2017 Type Set to 1 to indicate a PadN sub-TLV. 2019 Length The length of the body, in octets, exclusive of the Type 2020 and Length fields. 2022 MBZ Set to 0 on transmission. 2024 This sub-TLV is silently ignored on reception. 2026 5. IANA Considerations 2028 IANA has registered the UDP port number 6696, called "babel", for use 2029 by the Babel protocol. 2031 IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and 2032 the IPv4 multicast group 224.0.0.111 for use by the Babel protocol. 2034 6. Security Considerations 2036 As defined in this document, Babel is a completely insecure protocol. 2037 Any attacker can attract data traffic by advertising routes with a 2038 low metric. This particular issue can be solved either by lower- 2039 layer security mechanisms (e.g., IPsec or link-layer security), or by 2040 appending a cryptographic key to Babel packets; the provision of 2041 ignoring any data contained within a Babel packet beyond the body 2042 length declared by the header is designed for just such a purpose. 2044 The information that a Babel node announces to the whole routing 2045 domain is often sufficient to determine a mobile node's physical 2046 location with reasonable precision. The privacy issues that this 2047 causes can be mitigated somewhat by using randomly chosen router-ids 2048 and randomly chosen IP addresses, and changing them periodically. 2050 When carried over IPv6, Babel packets are ignored unless they are 2051 sent from a link-local IPv6 address; since routers don't forward 2052 link-local IPv6 packets, this provides protection against spoofed 2053 Babel packets being sent from the global Internet. No such natural 2054 protection exists when Babel packets are carried over IPv4. 2056 7. References 2058 7.1. Normative References 2060 [ADDRARCH] 2061 Hinden, R. and S. Deering, "IP Version 6 Addressing 2062 Architecture", RFC 4291, February 2006. 2064 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2065 Requirement Levels", RFC 2119, March 1997. 2067 7.2. Informative References 2069 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 2070 Sequenced Distance-Vector Routing (DSDV) for Mobile 2071 Computers", ACM SIGCOMM'94 Conference on Communications 2072 Architectures, Protocols and Applications 234-244, 1994. 2074 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 2075 Computations", IEEE/ACM Transactions on Networking 1:1, 2076 February 1993. 2078 [EIGRP] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle, 2079 "EIGRP -- a Fast Routing Protocol Based on Distance 2080 Vectors", Proc. Interop 94, 1994. 2082 [ETX] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 2083 high-throughput path metric for multi-hop wireless 2084 networks", Proc. MobiCom 2003, 2003. 2086 [IS-IS] "Information technology -- Telecommunications and 2087 information exchange between systems -- Intermediate 2088 System to Intermediate System intra-domain routeing 2089 information exchange protocol for use in conjunction with 2090 the protocol for providing the connectionless-mode network 2091 service (ISO 8473)", ISO/IEC 10589:2002, 2002. 2093 [JITTER] Floyd, S. and V. Jacobson, "The synchronization of 2094 periodic routing messages", IEEE/ACM Transactions on 2095 Networking 2, 2, 122-136, April 1994. 2097 [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 2099 [PACKETBB] 2100 Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 2101 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 2102 Format", RFC 5444, February 2009. 2104 [RIP] Malkin, G., "RIP Version 2", RFC 2453, November 1998. 2106 Appendix A. Cost and Metric Computation 2108 The strategy for computing link costs and route metrics is a local 2109 matter; Babel itself only requires that it comply with the conditions 2110 given in Section 3.4.3 and Section 3.5.2. Different nodes MAY use 2111 different strategies in a single network and MAY use different 2112 strategies on different interface types. This section gives a few 2113 examples of such strategies. 2115 The sample implementation of Babel maintains statistics about the 2116 last 16 received Hello TLVs (Appendix A.1), computes costs by using 2117 the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX 2118 (Appendix A.2.2) on wireless links. It uses an additive algebra for 2119 metric computation (Appendix A.3.1). 2121 A.1. Maintaining Hello History 2123 For each neighbour, the sample implementation of Babel maintains a 2124 Hello history and an expected sequence number. The Hello history is 2125 a vector of 16 bits, where a 1 value represents a received Hello, and 2126 a 0 value a missed Hello. The expected sequence number, written ne, 2127 is the sequence number that is expected to be carried by the next 2128 received hello from this neighbour. 2130 Whenever it receives a Hello packet from a neighbour, a node compares 2131 the received sequence number nr with its expected sequence number ne. 2132 Depending on the outcome of this comparison, one of the following 2133 actions is taken: 2135 o if the two differ by more than 16 (modulo 2^16), then the sending 2136 node has probably rebooted and lost its sequence number; the 2137 associated neighbour table entry is flushed; 2139 o otherwise, if the received nr is smaller (modulo 2^16) than the 2140 expected sequence number ne, then the sending node has increased 2141 its Hello interval without our noticing; the receiving node 2142 removes the last (ne - nr) entries from this neighbour's Hello 2143 history (we "undo history"); 2145 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending 2146 node has decreased its Hello interval, and some Hellos were lost; 2147 the receiving node adds (nr - ne) 0 bits to the Hello history (we 2148 "fast-forward"). 2150 The receiving node then appends a 1 bit to the neighbour's Hello 2151 history, resets the neighbour's Hello timer, and sets ne to (nr + 1). 2152 It then resets the neighbour's Hello timer to 1.5 times the value 2153 advertised in the received Hello (the extra margin allows for the 2154 delay due to jitter). 2156 Whenever the Hello timer associated to a neighbour expires, the local 2157 node adds a 0 bit to this neighbour's Hello history, and increments 2158 the expected Hello number. If the Hello history is empty (it 2159 contains 0 bits only), the neighbour entry is flushed; otherwise, it 2160 resets the neighbour's Hello timer to the value advertised in the 2161 last Hello received from this neighbour (no extra margin is necessary 2162 in this case). 2164 A.2. Cost Computation 2166 A.2.1. k-out-of-j 2168 K-out-of-j link sensing is suitable for wired links that are either 2169 up, in which case they only occasionally drop a packet, or down, in 2170 which case they drop all packets. 2172 The k-out-of-j strategy is parameterised by two small integers k and 2173 j, such that 0 < k <= j, and the nominal link cost, a constant K >= 2174 1. A node keeps a history of the last j hellos; if k or more of 2175 those have been correctly received, the link is assumed to be up, and 2176 the rxcost is set to K; otherwise, the link is assumed to be down, 2177 and the rxcost is set to infinity. 2179 The cost of such a link is defined as 2181 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal; 2183 o cost = txcost otherwise. 2185 A.2.2. ETX 2187 The Estimated Transmission Cost metric [ETX] estimates the number of 2188 times that a unicast frame will be retransmitted by the IEEE 802.11 2189 MAC, assuming infinite persistence. 2191 A node uses a neighbour's Hello history to compute an estimate, 2192 written beta, of the probability that a Hello TLV is successfully 2193 received. The rxcost is defined as 256/beta. 2195 Let alpha be MIN(1, 256/txcost), an estimate of the probability of 2196 successfully sending a Hello TLV. The cost is then computed by 2198 cost = 256/(alpha * beta) 2200 or, equivalently, 2202 cost = (MAX(txcost, 256) * rxcost) / 256. 2204 A.3. Metric Computation 2206 A.3.1. Additive Metrics 2208 The simplest approach for obtaining a monotonic, isotonic metric is 2209 to define the metric of a route as the sum of the costs of the 2210 component links. More formally, if a neighbour advertises a route 2211 with metric m over a link with cost c, then the resulting route has 2212 metric M(c, m) = c + m. 2214 A multiplicative metric can be converted to an additive one by taking 2215 the logarithm (in some suitable base) of the link costs. 2217 A.3.2. External Sources of Willingness 2219 A node may want to vary its willingness to forward packets by taking 2220 into account information that is external to the Babel protocol, such 2221 as the monetary cost of a link, the node's battery status, CPU load, 2222 etc. This can be done by adding to every route's metric a value k 2223 that depends on the external data. For example, if a battery-powered 2224 node receives an update with metric m over a link with cost c, it 2225 might compute a metric M(c, m) = k + c + m, where k depends on the 2226 battery status. 2228 In order to preserve strict monotonicity (Section 3.5.2), the value k 2229 must be greater than -c. 2231 Appendix B. Constants 2233 The choice of time constants is a trade-off between fast detection of 2234 mobility events and protocol overhead. Two implementations of Babel 2235 with different time constants will interoperate, although the 2236 resulting convergence time will most likely be dictated by the 2237 slowest of the two implementations. 2239 Experience with the sample implementation of Babel indicates that the 2240 Hello interval is the most important time constant: a mobility event 2241 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance 2242 on triggered updates and explicit requests, the Update interval only 2243 has an effect on the time it takes for accurate metrics to be 2244 propagated after variations in link costs too small to trigger an 2245 unscheduled update. 2247 At the time of writing, the sample implementation of Babel uses the 2248 following default values: 2250 Hello Interval: 4 seconds on wireless links, 20 seconds on wired 2251 links. 2253 IHU Interval: the advertised IHU interval is always 3 times the 2254 Hello interval. IHUs are actually sent with each Hello on lossy 2255 links (as determined from the Hello history), but only with every 2256 third Hello on lossless links. 2258 Update Interval: 4 times the Hello interval. 2260 IHU Hold Time: 3.5 times the advertised IHU interval. 2262 Route Expiry Time: 3.5 times the advertised update interval. 2264 Source GC time: 3 minutes. 2266 The amount of jitter applied to a packet depends on whether it 2267 contains any urgent TLVs or not. Urgent triggered updates and urgent 2268 requests are delayed by no more than 200ms; other TLVs are delayed by 2269 no more than one-half the Hello interval. 2271 Appendix C. Considerations for protocol extensions 2273 Babel is an extensible protocol, and this document defines a number 2274 of mechanisms that can be used to extend the protocol in a backwards 2275 compatible manner: 2277 o increasing the version number in the packet header; 2279 o defining new TLVs; 2281 o defining new sub-TLVs (with the mandatory bit set or not); 2283 o defining new AEs; 2285 o using the packet trailer. 2287 New versions of the Babel protocol should only be defined if the new 2288 version is not backwards compatible with the original protocol. 2290 In many cases, an extension could be implemented either by defining a 2291 new TLV, or by adding a new sub-TLV to an existing TLV. For example, 2292 an extension whose purpose is to attach additional data to route 2293 updates can be implemented either by creating a new "enriched" Update 2294 TLV, or by adding a sub-TLV to the Update TLV. 2296 The two encodings are treated differently by implementations that do 2297 not understand the extension. In the case of a new TLV, the whole 2298 unknown TLV is ignored by an implementation of the original protocol, 2299 while in the case of a new sub-TLV, the TLV is parsed and acted upon, 2300 and the unknown sub-TLV is silently ignored. Therefore, a sub-TLV 2301 should be used by extensions that extend the Update in a compatible 2302 manner (the extension data may be silently ignored), while a new TLV 2303 must be used by extensions that make incompatible extensions to the 2304 meaning of the TLV (the whole TLV must be thrown away if the 2305 extension data is not understood). 2307 Adding a new AE is essentially equivalent to adding a new TLV: Update 2308 TLVs with an unknown AE are ignored, just like unknown TLVs. 2309 However, adding a new AE is often more involved than adding a new 2310 TLV, since it creates a new set of compression state. Additionally, 2311 since the Next Hop TLV creates state specific to a given address 2312 family, as opposed to a given AE. A similar issue arises with Update 2313 TLVs with unknown AEs establishing a new router-id (flag 40 2314 hexadecimal). Therefore, defining new AEs must be done with care if 2315 compatibility with unextended implementations is required. 2317 The packet trailer -- the space after the declared length of the 2318 packet but within the payload of the UDP datagram -- was originally 2319 intended to carry a cryptographic signature. However, at this time 2320 no extension has used it, and therefore we refrain from making any 2321 recommendations about its use due to the lack of implementation 2322 experience. 2324 Appendix D. Simplified Implementations 2326 Babel is a fairly economic protocol. Route updates take between 12 2327 and 40 octets per destination, depending on how successful 2328 compression is; in a double-stack mesh network, an average of less 2329 than 24 octets is typical. The route table occupies about 35 octets 2330 per IPv6 entry. To put these values into perspective, a single full- 2331 size Ethernet frame can carry some 65 route updates, and a megabyte 2332 of memory can contain a 20000-entry routing table and the associated 2333 source table. 2335 Babel is also a reasonably simple protocol. The sample 2336 implementation consists of less than 8000 lines of C code, and it 2337 compiles to less than 60 kB of text on a 32-bit CISC architecture. 2339 Nonetheless, in some very constrained environments, such as PDAs, 2340 microwave ovens, or abacuses, it may be desirable to have subset 2341 implementations of the protocol. 2343 A parasitic implementation is one that uses a Babel network for 2344 routing its packets but does not announce any of the routes that it 2345 has learnt from its neighbours. (This is slightly more than a 2346 passive implementation, which doesn't even announce routes to 2347 itself.) It may either maintain a full routing table or simply 2348 select a gateway amongst any one of its neighbours that announces a 2349 default route. Since a parasitic implementation never forwards 2350 packets, it cannot possibly participate in a routing loop; hence, it 2351 need not evaluate the feasibility condition, and need not maintain a 2352 source table. 2354 A parasitic implementation MUST answer acknowledgement requests and 2355 MUST participate in the Hello/IHU protocol. Finally, it MUST be able 2356 to reply to seqno requests for routes that it announces and SHOULD be 2357 able to reply to route requests. 2359 Appendix E. Software Availability 2361 The sample implementation of Babel is available from 2362 . 2364 Appendix F. Changes from previous versions 2366 F.1. Changes since RFC 6126 2368 o Changed UDP port number to 6696. 2370 o Consistently use router-id rather than id. 2372 o Clarified that the source garbage collection timer is reset after 2373 sending an update even if the entry was not modified. 2375 o In section "Seqno Requests", fixed an erroneous "route request". 2377 o In the description of the Seqno Request TLV, added the description 2378 of the Router-Id field. 2380 o Made router-ids all-0 and all-1 forbidden. 2382 F.2. Changes since draft-ietf-babel-rfc6126bis-00 2384 o Added security considerations. 2386 F.3. Changes since draft-ietf-babel-rfc6126bis-01 2388 o Integrated the format of sub-TLVs. 2390 o Mentioned for each TLV whether it supports sub-TLVs. 2392 o Added Appendix C. 2394 o Added a mandatory bit in sub-TLVs. 2396 o Changed compression state to be per-AF rather than per-AE. 2398 o Added implementation hint for the route table. 2400 o Clarified how router-ids are computed when bit 0x40 is set in 2401 Updates. 2403 o Relaxed the conditions for sending requests, and tightened the 2404 conditions for forwarding requests. 2406 o Clarified that neighbours should be acquired at some point, but it 2407 doesn't matter when. 2409 Author's Address 2411 Juliusz Chroboczek 2412 IRIF, University of Paris-Diderot 2413 Case 7014 2414 75205 Paris Cedex 13 2415 France 2417 Email: jch@irif.fr