idnits 2.17.1 draft-ietf-babel-applicability-09.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (August 7, 2019) is 1721 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-20) exists of draft-ietf-babel-rfc6126bis-07 == Outdated reference: A later version (-02) exists of draft-jonglez-babel-rtt-extension-01 == Outdated reference: A later version (-08) exists of draft-ietf-babel-source-specific-04 == Outdated reference: A later version (-10) exists of draft-ietf-babel-dtls-07 == Outdated reference: A later version (-12) exists of draft-ietf-babel-hmac-07 Summary: 0 errors (**), 0 flaws (~~), 6 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: Informational August 7, 2019 5 Expires: February 8, 2020 7 Applicability of the Babel routing protocol 8 draft-ietf-babel-applicability-09 10 Abstract 12 Babel is a routing protocol based on the distance-vector algorithm 13 augmented with mechanisms for loop avoidance and starvation 14 avoidance. This document describes a number of niches where Babel 15 has been found to be useful and that are arguably not adequately 16 served by more mature protocols. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on February 8, 2020. 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction and background . . . . . . . . . . . . . . . . . 2 53 1.1. Technical overview of the Babel protocol . . . . . . . . 2 54 2. Properties of the Babel protocol . . . . . . . . . . . . . . 3 55 2.1. Simplicity and implementability . . . . . . . . . . . . . 3 56 2.2. Robustness . . . . . . . . . . . . . . . . . . . . . . . 3 57 2.3. Extensibility . . . . . . . . . . . . . . . . . . . . . . 5 58 2.4. Limitations . . . . . . . . . . . . . . . . . . . . . . . 5 59 3. Successful deployments of Babel . . . . . . . . . . . . . . . 6 60 3.1. Heterogeneous networks . . . . . . . . . . . . . . . . . 6 61 3.2. Large scale overlay networks . . . . . . . . . . . . . . 7 62 3.3. Pure mesh networks . . . . . . . . . . . . . . . . . . . 7 63 3.4. Small unmanaged networks . . . . . . . . . . . . . . . . 7 64 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 65 5. Security Considerations . . . . . . . . . . . . . . . . . . . 8 66 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 67 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 68 7.1. Normative References . . . . . . . . . . . . . . . . . . 8 69 7.2. Informational References . . . . . . . . . . . . . . . . 9 70 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11 72 1. Introduction and background 74 Babel [RFC6126bis] is a routing protocol based on the familiar 75 distance-vector algorithm (sometimes known as distributed Bellman- 76 Ford) augmented with mechanisms for loop avoidance (there is no 77 "counting to infinity") and starvation avoidance. This document 78 describes a number of niches where Babel is useful and that are 79 arguably not adequately served by more mature protocols such as OSPF 80 [RFC5340] and IS-IS [RFC1195]. 82 1.1. Technical overview of the Babel protocol 84 At its core, Babel is a distance-vector protocol based on the 85 distributed Bellman-Ford algorithm, similar in principle to RIP 86 [RFC2453], but with two important extensions: provisions for sensing 87 of neighbour reachability, bidirectional reachability and link 88 quality, and support for multiple address families (e.g., IPv6 and 89 IPv4) in a single protocol instance. 91 Algorithms of this class are simple to understand and simple to 92 implement, but unfortunately they do not work very well -- they 93 suffer from "counting to infinity", a case of pathologically slow 94 convergence in some topologies after a link failure. Babel uses a 95 mechanism pioneered by EIGRP [DUAL] [RFC7868], known as 96 "feasibility", which avoids routing loops and therefore makes 97 counting to infinity impossible. 99 Feasibility is a conservative mechanism, one that not only avoids all 100 looping routes but also rejects some loop-free routes. Thus, it can 101 lead to a situation known as "starvation", where a router rejects all 102 routes to a given destination, even those that are loop-free. In 103 order to recover from starvation, Babel uses a mechanism pioneered by 104 DSDV [DSDV] and known as "sequenced routes". In Babel, this 105 mechanism is generalised to deal with prefixes of arbitrary length 106 and routes announced at multiple points in a single routing domain 107 (DSDV was a pure mesh protocol, and only dealt with host routes). 109 In DSDV, the sequenced routes algorithm is slow to react to a 110 starvation episode. In Babel, starvation recovery is accelerated by 111 using explicit requests (known as "seqno requests" in the protocol) 112 that signal a starvation episode and cause a new sequenced route to 113 be propagated in a timely manner. In the absence of packet loss, 114 this mechanism is provably complete and clears the starvation in time 115 proportional to the diameter of the network, at the cost of some 116 additional signalling traffic. 118 2. Properties of the Babel protocol 120 This section describes the properties of the Babel protocol as well 121 as its known limitations. 123 2.1. Simplicity and implementability 125 Babel is a conceptually simple protocol. It consists of a familiar 126 algorithm (distributed Bellman-Ford) augmented with three simple and 127 well-defined mechanisms (feasibility, sequenced routes and explicit 128 requests). Given a sufficiently friendly audience, the principles 129 behind Babel can be explained in 15 minutes, and a full description 130 of the protocol can be done in 52 minutes (one microcentury). 132 An important consequence is that Babel is easy to implement. At the 133 time of writing, there exist four independent, interoperable 134 implementations, including one that was reportedly written and 135 debugged in just two nights. 137 2.2. Robustness 139 The fairly strong properties of the Babel protocol (convergence, loop 140 avoidance, starvation avoidance) rely on some reasonably weak 141 properties of the network and the metric being used. The most 142 significant are: 144 o causality: the "happens-before" relation is acyclic (intuitively, 145 a control message is not received before it has been sent); 147 o strict monotonicity of the metric: for any metric M and link 148 cost C, M < C + M (intuitively, this implies that cycles have a 149 strictly positive metric); 151 o left-distributivity of the metric: for any metrics M and M' and 152 cost C, if M <= M', then C + M <= C + M' (intuitively, this 153 implies that a good choice made by a neighbour B of a node A is 154 also a good choice for A). 156 See [METAROUTING] for more information about these properties and 157 their consequences. 159 In particular, Babel does not assume a reliable transport, it does 160 not assume ordered delivery, it does not assume that communication is 161 transitive, and it does not require that the metric be discrete 162 (continuous metrics are possible, reflecting for example packet loss 163 rates). This is in contrast to link-state routing protocols such as 164 OSPF [RFC5340] or IS-IS [RFC1195], which incorporate a reliable 165 flooding algorithm and make stronger requirements on the underlying 166 network and metric. 168 These weak requirements make Babel a robust protocol: 170 o robust with respect to unusual networks: an unusual network (non- 171 transitive links, unstable link costs, etc.) is likely not to 172 violate the assumptions of the protocol; 174 o robust with respect to novel metrics: an unusual metric 175 (continuous, constantly fluctuating, etc.) is likely not to 176 violate the assumptions of the protocol. 178 Section 3 below gives examples of successful deployments of Babel 179 that illustrate these properties. 181 In addition to the above, our implementation experience indicates 182 that Babel tends to be robust with respect to bugs: in many cases, an 183 implementation bug does not violate the properties on which Babel 184 relies, and therefore slows down convergence or causes sub-optimal 185 routing rather than causing the network to collapse. 187 These robustness properties have important consequences for the 188 applicability of the protocol: Babel works (more or less efficiently) 189 in a range of circumstances where traditional routing protocols don't 190 work well (or at all). 192 2.3. Extensibility 194 Babel's packet format has a number of features that make the protocol 195 extensible (see Appendix C of [RFC6126bis]), and a number of 196 extensions have been designed to make Babel work better in situations 197 that were not envisioned when the protocol was initially designed. 198 The ease of extensibility is not an accident, but a consequence of 199 the design of the protocol: it is reasonably easy to check whether a 200 given extension violates the assumptions on which Babel relies. 202 All of the extensions designed to date interoperate with the base 203 protocol and with each other. This, again, is a consequence of the 204 protocol design: in order to check that two extensions to the Babel 205 protocol are interoperable, it is enough to verify that the 206 interaction of the two does not violate the base protocol's 207 assumptions. 209 Notable extensions deployed to date include: 211 o source-specific routing (SADR) [BABEL-SS] allows forwarding to 212 take a packet's source address into account, thus enabling a cheap 213 form of multihoming [SS-ROUTING]; 215 o RTT-based routing [BABEL-RTT] minimises link delay, which is 216 useful in overlay network (where both hop count and packet loss 217 are poor metrics). 219 Some other extensions have been designed, but have not seen 220 deployment yet (and their usefulness is yet to be demonstrated): 222 o frequency-aware routing [BABEL-Z] aims to minimise radio 223 interference in wireless networks; 225 o ToS-aware routing [BABEL-TOS] allows routing to take a packet's 226 ToS marking into account for selected routes without incurring the 227 full cost of a multi-topology routing protocol. 229 2.4. Limitations 231 Babel has some undesirable properties that make it suboptimal or even 232 unusable in some deployments. 234 2.4.1. Periodic updates 236 The main mechanisms used by Babel to reconverge after a topology 237 change are reactive: triggered updates, triggered retractions and 238 explicit requests. However, in the presence of heavy packet loss, 239 Babel relies on periodic updates to clear pathologies. This reliance 240 on periodic updates makes Babel unsuitable in at least two kinds of 241 deployments: 243 o large, stable networks: since Babel sends periodic updates even in 244 the absence of topology changes, in well-managed, large, stable 245 networks the amount of control traffic will be reduced by using a 246 protocol that uses a reliable transport (such as OSPF, IS-IS or 247 EIGRP); 249 o low-power networks: the periodic updates use up battery power even 250 when there are no topology changes and no user traffic, which 251 makes Babel wasteful in low-power networks. 253 2.4.2. Full routing table 255 While there exist techniques that allow a Babel speaker to function 256 with a partial routing table (e.g., by learning just a default route 257 or, more generally, performing route aggregation), Babel is designed 258 around the assumption that every router has a full routing table. In 259 networks where some nodes are too constrained to hold a full routing 260 table, it might be preferable to use a protocol that was designed 261 from the outset to work with a partial routing table (such as AODVv2 262 [AODVv2], RPL [RFC6550] or LOADng [LOADng]). 264 2.4.3. Slow aggregation 266 Babel's loop-avoidance mechanism relies on making a route unreachable 267 after a retraction until all neighbours have been guaranteed to have 268 acted upon the retraction, even in the presence of packet loss. 269 Unless the optional algorithm described in Section 3.5.5 of 270 [RFC6126bis] is implemented, this entails that a node is unreachable 271 for a few minutes after the most specific route to it has been 272 retracted. This delay may make Babel slow to recover from a topology 273 change in networks that perform automatic route aggregation. 275 3. Successful deployments of Babel 277 This section gives a few examples of environments where Babel has 278 been successfully deployed. 280 3.1. Heterogeneous networks 282 Babel is able to deal with both classical, prefix-based ("Internet- 283 style") routing and flat ("mesh-style") routing over non-transitive 284 link technologies. Just like traditional distance-vector protocols, 285 Babel is able to carry prefixes of arbitrary length, to supress 286 redundant announcements by applying the split-horizon optimisation 287 where applicable, and can be configured to filter out redundant 288 announcements (manual aggregation). Just like specialised mesh 289 protocols, Babel doesn't by default assume that links are transitive 290 or symmetric, can dynamically compute metrics based on an estimation 291 of link quality, and carries large numbers of host routes efficiently 292 by omitting common prefixes. 294 Because of these properties, Babel has seen a number of successful 295 deployments in medium-sized heterogeneous networks, networks that 296 combine a wired, aggregated backbone with meshy wireless bits at the 297 edges. 299 Efficient operation in heterogeneous networks requires the 300 implementation to distinguish between wired and wireless links, and 301 to perform link quality estimation on wireless links. 303 3.2. Large scale overlay networks 305 The algorithms used by Babel (loop avoidance, hysteresis, delayed 306 updates) allow it to remain stable and efficient in the presence of 307 unstable metrics, even in the presence of a feedback loop. For this 308 reason, it has been successfully deployed in large scale overlay 309 networks, built out of thousands of tunnels spanning continents, 310 where it is used with a metric computed from links' latencies. 312 This particular application depends on the extension for RTT- 313 sensitive routing [DELAY-BASED]. 315 3.3. Pure mesh networks 317 While Babel is a general-purpose routing protocol, it has been 318 repeatedly shown to be competitive with dedicated routing protocols 319 for wireless mesh networks [REAL-WORLD] [BRIDGING-LAYERS]. Although 320 this particular niche is already served by a number of mature 321 protocols, notably OLSR-ETX and OLSRv2 [RFC7181] (equipped e.g. with 322 the DAT metric [RFC7779]), Babel has seen a moderate amount of 323 successful deployment in pure mesh networks. 325 3.4. Small unmanaged networks 327 Because of its small size and simple configuration, Babel has been 328 deployed in small, unmanaged networks (e.g., home and small office 329 networks), where it serves as a more efficient replacement for RIP 330 [RFC2453], over which it has two significant advantages: the ability 331 to route multiple address families (IPv6 and IPv4) in a single 332 protocol instance, and good support for using wireless links for 333 transit. 335 4. IANA Considerations 337 This document requires no IANA actions. [RFC Editor: please remove 338 this section before publication.] 340 5. Security Considerations 342 As is the case in all distance-vector routing protocols, a Babel 343 speaker receives reachability information from its neighbours, which 344 by default is trusted by all nodes in the routing domain. 346 In most deployments, the Babel protocol is run over a network that is 347 secured either at the physical layer (e.g., physically protecting 348 Ethernet sockets) or at the link layer (using a protocol such as WiFi 349 Protected Access (WPA2)). If Babel is being run over an unprotected 350 network, then the routing traffic needs to be protected using a 351 sufficiently strong cryptographic mechanism. 353 At the time of writing, two such mechanisms have been defined. 354 Babel-HMAC [HMAC] is a simple and easy to implement mechanism that 355 only guarantees authenticity, integrity and replay protection of the 356 routing traffic, and only supports symmetric keying with a small 357 number of keys (typically just one or two). Babel-DTLS [DTLS] is a 358 more complex mechanism, that requires some minor changes to be made 359 to a typical Babel implementation and depends on a DTLS stack being 360 available, but inherits all of the features of DTLS, notably 361 confidentiality, optional replay protection, and the ability to use 362 asymmetric keys. 364 Due to its simplicity, Babel-HMAC should be the preferred security 365 mechanism in most deployments, with Babel-DTLS available for networks 366 that require its additional features. 368 6. Acknowledgments 370 The author is indebted to Jean-Paul Smetz and Alexander Vainshtein 371 for their input to this document. 373 7. References 375 7.1. Normative References 377 [RFC6126bis] 378 Chroboczek, J. and D. Schinazi, "The Babel Routing 379 Protocol", Internet Draft draft-ietf-babel-rfc6126bis-07, 380 November 2018. 382 7.2. Informational References 384 [AODVv2] Perkins, C., Ratliff, S., Dowdell, J., Steenbrink, L., and 385 V. Mercieca, "Ad Hoc On-demand Distance Vector Version 2 386 (AODVv2) Routing", draft-ietf-manet-aodvv2-16 (work in 387 progress), May 2016. 389 [BABEL-RTT] 390 Jonglez, B. and J. Chroboczek, "Delay-based Metric 391 Extension for the Babel Routing Protocol", draft-jonglez- 392 babel-rtt-extension-01 (work in progress), May 2015. 394 [BABEL-SS] 395 Boutier, M. and J. Chroboczek, "Source-Specific Routing in 396 Babel", draft-ietf-babel-source-specific-04 (work in 397 progress), October 2018. 399 [BABEL-TOS] 400 Chouasne, G. and J. Chroboczek, "TOS-Specific Routing in 401 Babel", draft-chouasne-babel-tos-specific-00 (work in 402 progress), July 2017. 404 [BABEL-Z] Chroboczek, J., "Diversity Routing for the Babel Routing 405 Protocol", draft-chroboczek-babel-diversity-routing-01 406 (work in progress), February 2016. 408 [BRIDGING-LAYERS] 409 Murray, D., Dixon, M., and T. Koziniec, "An Experimental 410 Comparison of Routing Protocols in Multi Hop Ad Hoc 411 Networks", Proc. ATNAC 2010, 2010. 413 [DELAY-BASED] 414 Jonglez, B. and J. Chroboczek, "A delay-based routing 415 metric", March 2014, . 417 [DSDV] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination- 418 Sequenced Distance-Vector Routing (DSDV) for Mobile 419 Computers", ACM SIGCOMM'94 Conference on Communications 420 Architectures, Protocols and Applications 234-244, 1994. 422 [DTLS] Decimo, A., Schinazi, D., and J. Chroboczek, "Babel 423 Routing Protocol over Datagram Transport Layer Security", 424 draft-ietf-babel-dtls-07 (work in progress), July 2019. 426 [DUAL] Garcia Luna Aceves, J., "Loop-Free Routing Using Diffusing 427 Computations", IEEE/ACM Transactions on Networking 1:1, 428 February 1993. 430 [HMAC] Do, C., Kolodziejak, W., and J. Chroboczek, "HMAC 431 authentication for the Babel routing protocol", draft- 432 ietf-babel-hmac-07 (work in progress), June 2019. 434 [LOADng] Clausen, T., Verdiere, A., Yi, J., Niktash, A., Igarashi, 435 Y., Satoh, H., Herberg, U., Lavenu, C., Lys, T., and J. 436 Dean, "The Lightweight On-demand Ad hoc Distance-vector 437 Routing Protocol - Next Generation (LOADng)", draft- 438 clausen-lln-loadng-15 (work in progress), January 2017. 440 [METAROUTING] 441 Griffin, T. and J. Sobrinho, "Metarouting", 2005. 443 In Proceedings of the 2005 conference on Applications, 444 technologies, architectures, and protocols for computer 445 communications (SIGCOMM'05). 447 [REAL-WORLD] 448 Abolhasan, M., Hagelstein, B., and J. Wang, "Real-world 449 performance of current proactive multi-hop mesh 450 protocols", Asia-Pacific Conference on Communication 2009, 451 2009. 453 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 454 dual environments", RFC 1195, December 1990. 456 [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, November 457 1998. 459 [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF 460 for IPv6", RFC 5340, July 2008. 462 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 463 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 464 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 465 Low-Power and Lossy Networks", RFC 6550, March 2012. 467 [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, 468 "The Optimized Link State Routing Protocol Version 2", 469 RFC 7181, April 2014. 471 [RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric 472 Based on Packet Sequence Numbers for Optimized Link State 473 Routing Version 2 (OLSRv2)", RFC 7779, 474 DOI 10.17487/RFC7779, April 2016. 476 [RFC7868] Savage, D., Ng, J., Moore, S., Slice, D., Paluch, P., and 477 R. White, "Cisco's Enhanced Interior Gateway Routing 478 Protocol (EIGRP)", RFC 7868, DOI 10.17487/RFC7868, May 479 2016. 481 [SS-ROUTING] 482 Boutier, M. and J. Chroboczek, "Source-Specific Routing", 483 August 2014, . 485 In Proc. IFIP Networking 2015. 487 Author's Address 489 Juliusz Chroboczek 490 IRIF, University of Paris-Diderot 491 Case 7014 492 75205 Paris Cedex 13 493 France 495 Email: jch@irif.fr