| Homenet Working Group | M. Wasserman |
| Internet-Draft | Painless Security |
| Intended status: Informational | C. Hopps |
| Expires: August 19, 2015 | Deutsche Telekom |
| J. Chroboczek | |
| University of Paris-Diderot (Paris 7) | |
| February 15, 2015 |
HOMENET IS-IS and Babel Comparison
draft-mrw-homenet-rtg-comparison-01.txt
This document is intended to provide information to members of the IETF Home Networks Working Group (HOMENET WG), so that we can make an informed decision regarding which routing protocol to use in home networks. The routing protocols compared in this document are: The Babel Routing Protocol (Babel) and The Intermediate System to Intermediate System Intra-Domain Routing Protocol (IS-IS).
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on August 19, 2015.
Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
This document compares IS-IS (ISO/IEC 10589:2002) [RFC1142] and Babel [RFC6126] according to several criteria related to their use in home networks (HOMENETs), as defined by the HOMENET WG.
Please note that this document does not represent the consenus of any group, not even the authors. It is an organized collection of facts and well-informed opinions provided by experts on Babel and IS-IS that may be useful to the HOMENET WG in choosing a routing protocol.
The HOMENET environment is different from the environment of a professionally administered network. The most obvious difference is that a HOMENET is not administered: any protocols used must be robust and fully self-configuring, and any tuning knobs that they provide will be unused in the vast majority of deployments.
Another difference is that HOMENETs are usually built out of a specific class of cheap device, the "Plastic Home Router". A Plastic Home Router's firmware is installed at the factory, and is most likely never updated. Additionally, experience shows that home routers are often used way beyond their warranty period, and even after their manufacturer leaves the router business. This, again, argues in favour of simple, robust protocols that are easy to implement and can be expected to keep functioning without software updates.
HOMENETs are built and grow organically, and often end up consisting of multiple link technologies with widely different performance characteristics (twisted-pair Ethernet, IEEE 802.11 and its multiple variants, Powerline Ethernet, etc.). It is desirable for a HOMENET routing protocol to be able to dynamically optimise paths according to the link characteristics.
Contrary to popular perception, the Plastic Home Router is usually equipped with a reasonably fast CPU and reasonable amounts of flash and RAM; at the time of writing, a (non-superscalar) 700MHz MIPS CPU with 16MB of flash and 64MB of RAM is typical. However, we expect smaller devices to participate in the HOMENET protocols, at least as stub routers. The ability to scale down the HOMENET protocols is therefore likely to encourage their wider adoption.
[Isn't it also the case that the HOMENET routing protocol will be implemented on lower-end embedded devices, such as nodes in a low-power wireless network? What is considered to be a reasonable low-end system requirement for a HOMENET router? -- mrw]
Experts appear to disagree on the expected size of a HOMENET; we have heard estimates ranging from just one router up to 250 routers. In any case, while scaling beyond a few thousand nodes is not likely to be relevant to HOMENET in the foreseeable future, the HOMENET protocols, if successful, will be repurposed to larger networks, whether we like it or not, and using a protocol that scales well from the outset may be desirable.
Both IS-IS and Babel are living protocols that are updated and extended over time. This section lists the extensions that were considered in this comparison. Additional protocol extensions could affect some of the information included in this document.
In addition to the base IS-IS protocol specification (ISO/IEC 10589:2002), this comparison considers the following IS-IS extensions:
In addition to the base Babel Protocol specification (RFC 6126), this comparison considers the following Babel extensions:
IS-IS is a Link State routing protocol, and Babel is a Loop-Avoiding Distance Vector routing protocol. There are some differences between these algorithms, particularly in terms of scalability, how much information is exchanged when the routing topology changes, and how far topology changes are propagated.
Link state algorithms distribute information for each node to all other nodes in the network using a flooding algorithm. This database of information is then used by each node to compute the best path to the other nodes in the network.
One benefit of this algorithm is that each node contains the full knowledge of the topology of the network. This information can be used by other applications outside the routing protocol itself.
Additionally the flooding algorithm has been found as an efficient method for other applications to distribute node-specific application data, although some care must be taken with this use so as not to disrupt the fundamental routing function.
Distance-vector algorithms distribute information about the path length to reach each destination through a given neighbor. Packets are forwarded to the neighbor who is advertising the best path towards the destination.
Babel, like EIGRP, DSDV, and to a certain extent BGP, uses a loop-avoiding distance-vector algorithm: it avoids creating a loop even during reconvergence (there is no "counting to infinity", and even short-lived "microloops" are avoided in most cases).
Loop-Avoiding Distance Vector scales to very large networks -- the amount of state is linear in the number of nodes, and, due to the absence of pathologies during reconvergence, does not need to be propagated in a timely manner. It scales badly in extremely dense deployments, where a single node has thousands of direct neighbours; such deployments are unlikely, and clearly outside the scope of HOMENET.
Link state algorithms scales to very large, very dense networks.
IS-IS distributes link and prefix information for each node in a single Logical LSP (possibly fragmented). It uses these LSPs to compute a tree representing the entire network. There is no duplication of state based on the number of adjacencies or unique paths to a given prefix.
Convergence time is defined as the amount of time after a link failure is detected during which the network is not fully operational. It does not include the time necessary to detect a link failure.
Given fast flooding of any change in the network, IS-IS has been shown to acheive sub 200ms end-to-end convergence even in very large provider networks (single area 900+ nodes). Basically the time for convergence is the time to propagate a new LSP from one end of the network to the other plus the SPF (tree computation interval) and FIB loading time. The flooding is done without delay and prior to running the SPF (tree-calculation) algorithm. Thus is roughly proportional to propagation delay across the diameter of the network. The tree calculation is sub 20ms on modern CPUs. FIB load time depends on the FIB hardware and design and not the routing protocol choice.
We easily should expect sub-second convergence for any change in reachability (addition or subtraction) in any conceivable homenet deployment.
Since Babel maintains a redundant routing table, it is most often able to reconverge almost instantaneously after a link failure (this is similar to e.g. EIGRP). In the case where no feasible routes are available, Babel reconverges in 20ms per hop to the source.
Both protocols enjoy fast convergence. However, unless there is a high level of integration between the routing protocol and the link layer, the time needed to reconverge is dwarfed by the amount of time needed to detect a link failure, which is the hold time in IS-IS (30s by default), and two hello intervals on Babel wired links (8s by default). (Babel performs link quality estimation on wireless links, so the delay is somewhat more difficult to quantify there.)
Home networks are not administered, so a routing protocol needs to be entirely self-configuring in order to be suitable for HOMENETs.
The only required configuration for IS-IS is a unique area/system identifier. The HOMENET implementation of IS-IS uses an autoconfiguration extension defined in an Internet Draft [ISIS-AUTOCONF], to set this value.
Babel is a fully self-configuring protocol -- the standard implementation of Babel only requires a list of interfaces in order to start routing.
Source-Specific Routing is a hard requirement for HOMENETs, as it will allow traffic to be routed to the correct outbound network based on host source address selection. Routing packets to the wrong outbound network could result in packets being dropped due to ISP ingress filtering rules.
Both Babel and IS-IS have extensions for source-specific routing.
IS-IS support for source specific routing is implemented with the addition of a sub-TLV to a reachability (prefix) TLV. The implementation assumes that all IS-IS routers have support for the sub-TLV. This assumption is safe to make due to the requirement that all homenet IS-IS routers also use a homenet specific area ID and cleartext password. Mixing in IS-IS routers without support for source specific routing is not supported as it may cause routing loops.
The Source-specific extension to the Babel routing protocol [BABEL-SS] has been implemented for over a year, has been made widely available and has seen a fair amount deployment as part of OpenWRT and CeroWRT. The source-specific code is currently in the process of being merged into the standard Babel implementation, and is scheduled to be included in version 1.6 (planned for March 2015).
Babel's source-specific extensions were carefully designed so that source-specific and ordinary (non-specific) routers can coexist in a single routing domain, without causing routing loops. However, unless there is a connected backbone of source-specific routers, any non-specific routers present in the HOMENET may experience blackholes. Interoperability between plain Babel and Source-Specific Babel is described in detail in Section VI.A of [SS-ROUTING].
Typical HOMENETs are built out of multiple link technologies with very different performance characteristics -- Gigabit Ethernet can easily have three orders of magnitude higher throughput than a marginal wireless link. Both IS-IS and Babel quantify the desirability of a link by assigning a metric to it.
The HOMENET implementation of IS-IS uses the wide-metric (24-bit) link metric. Additionally IS-IS includes multi-topology support allowing for a variable number of metrics per link, as well as per-link and per-prefix tags allowing for coloring of links and reachability, and finally per-link and per-prefix sub-tlv's allowing for any future additional extensions.
Since Babel was originally designed for heterogeneous networks, it is able to dynamically assign metrics to links depending on their lower-layer characteristics. In practice, Babel assigns lower (better) metrics to wired links than to wireless ones, dynamically measures loss rates in order to favour lossless wireless links, favours routes with non-interfering radio frequencies, and avoids high-latency tunnels.
Obviously, such a wealth of information can lead to contradictory data in edge cases; however, Babel's loop-avoidance mechanisms ensure that the network remains in a consistent state in all cases, and a hysteresis mechanism ensures that, should a feedback loop occur, the frequency of oscillations remains bounded [DELAY-BASED].
A stub network is one that is attached to a HOMENET, possibly through multiple HOMENET routers, but must not be used for transit. For example, a stub network could be a sensor network which would collapse under the HOMENET traffic should it ever be used for transit.
In the following example, if the dotted link between C and D is a stub network, then it must not be used for transit even if the link between A and B fails:
---- A ----- B -----
| |
| |
C ..... D
In IS-IS reachability (prefixes) and topology (links/adjacencies) are separate things. IS-IS supports stub-networks as defined above simply by advertising the prefix associated with a link, but not the link itself. This is sometimes referred to as a "passive link".
Babel supports flexible filtering of routes, and a stub network can be designated by simply setting up the necessary filtering rules. For resource-limited deployments, a minimalistic, stub-only implementation of Babel is available.
[I think this section is badly written. We should just state whether each protocol supports auth or encryption, and whether it supports symmetric or something more exciting. -- jch]
IS-IS offers multiple levels of security from none, to simple clear-text (password) authentication, to fully generic cryptographic authentication using any number of hashing algorithms (e.g., HMAC-MD5, HMAC-SHA1, ... HMAC-SHA512). Currently, the HOMENET implementation of IS-IS uses the cleartext password set to a predefined value for auto-configuration purposes.
Babel supports symmetric key authentication using an extensible HMAC-based cryptographic authentication mechanism [RFC7298].
Although the HOMENET WG has not yet determined whether to support multicast in HOMENET Networks, it might be desirable to pick a routing protocol that supports multicast, so that it will be easier to add multicast support in the future.
The IS-IS protocol supports multicast routing. However, none of the available implementations include support for multicast.
There is no support for multicast routing in Babel.
There are HOMENET implementations of both IS-IS and Babel.
The HOMENET implementation of IS-IS is the only IS-IS implementation that supports source-specific routing, which is a hard requirement for HOMENET. If source-specific routing is not required, there are several independent, interoperable proprietary implementations of IS-IS (all major router vendors implement IS-IS). We are not aware of any production-quality open-source implementation of IS-IS other than the HOMENET one.
There are multiple open source implementations of Babel, two of which support source-specific routing. All implementations (except the stub-only version) were originally derived from the same codebase.
The HOMENET implementation of IS-IS consists of 7000 lines of Erlang code and has an installed size of over 11MB. Its initial memory usage (as reported by the operating system) is 22MB, and its working set increases by XXX bytes for each new edge in the network graph. To put these numbers into perspective, in a network with XXX nodes each of which has XXX neighbours, the HOMENET implementation of IS-IS requires XXX bytes for its data structures.
The code size of IS-IS depends greatly on what aspects of the protocol have been implemented. IS-IS supports multiple address families as well as completely different protocol stacks (OSI and IP), multiple area hierachical operation with automatic virtual link support for repairing area partitions, and multiple link types. Additionally many other protocol features have been added over time to augment the protocol or replace previous behavior. The protocol lends itself well to not only extension, but pairing down of features.
For HOMENET we need a level-1 only implementation supporting a common topology for IPv4 and IPv6 over broadcast (i.e., ethernet) link types. Additionally, we only require support of the latest extended metric TLVs (i.e., not implement legacy metric support).
The operational state required by IS-IS is proportional to the number of routers, links, and prefixes in the network. Each router in the network generates and advertises a Link State Protocol Data Unit (LSP) that describes it's attached links and prefixes. A copy of each of these LSPs is stored by each router in the network. IS-IS uses these LSPs to construct a shortest-path-first (SPF) tree with attached prefix information from which routes to the prefixes are created.
Concrete numbers lacking.
The source-specific implementation of Babel, which implements many non-HOMENET extensions to the protocol, consists of roughly 10000 lines of C and has an installed size of less than 130kB on AMD-64. Its initial memory usage (as reported by the operating system) is 300kB.
The amount of state stored by a Babel router is at worst one routing table entry for each destination through each neighbour. In the source-specific implementation, one routing entry occupies roughly 100 bytes of memory. To put these figures into perspective, in a network with 1000 nodes, a Babel router with 10 neighbours needs roughly a megabyte of memory to store its routing table (not counting malloc overhead).
The stub-only implementation of Babel consists of 900 lines of C and compiles to 12kB (dynamically linked). Its memory usage (as reported by the operating system) is 200kB, and remains constant (it doesn't perform any dynamic memory allocation).
Table 1 summarises the sizes of the available HOMENET routing protocol implementations. (Data courtesy of Steven Barth and Markus Stenberg.)
| babeld (source-specific) | sbabeld (stub-only) | AutoISIS | |
|---|---|---|---|
| Version | 2598774 | cc7d681 | 0.8.0 |
| Date | 2014-09-08 | 2014-11-21 | 2014-08-26 |
| License | MIT | MIT | Apache 2.0 |
| Lines of Code | 10.000 (C) | 1.000 (C) | 7.000 (Erlang) |
| Installed size (AMD64) | 129kB | 13kB | 11,385kB |
| Total installed size | 129kB | 13kB | 14,155kB |
| Baseline RSS | ~300kB | ~200kB | ~22,000kB |
In this table, "Installed size" is the size reported by the package manager for the routing daemon's package(s) (including the 1.6MB of the "Beam" Erlang VM in the case of IS-IS), while "Total installed size" is the sum of the size of the deamon's packages and all its dependencies, excluding the C library.
IS-IS is in active use in in the Internet in large non-hierachical (i.e., level-2 or single area level-1) deployments with hundreds of nodes. The protocol has proven to be very scalable.
[Do we have any information about the performance of IS-IS on 802.11 networks, in particular? -- mrw]
Babel has been carefully optimised for 802.11 networks. In particular, it performs link quality estimations of wireless links in a manner that works well with the 802.11 MAC. In addition, Babel has provisions for estimating radio interference [BABEL-Z], which is essential for providing decent throughput on multi-hop radio routes.
Babel was designed to work well on pure mesh networks (networks where a packet might exit through the same interface as the one it came from), but this is probably out of scope for HOMENET.
IS-IS is an ISO Standard documented in ISO/IEC 10589:2002. There is an active IETF IS-IS Working Group (ISIS) that maintains and extends the IS-IS protocol, and the IS-IS protocol has been extended in several ISIS Working Group documents.
The autoconfiguration and source-specific extensions to IS-IS, which are both hard requirements for HOMENET, are documented in (non-WG) Internet Drafts [ISIS-AUTOCONF] [ISIS-SS].
Babel is documented in an Experimental RFC (RFC 6126) published in 2011, and it has been updated in several individual-submission RFCs and Internet Drafts. An Internet Draft establishing an IANA registry of Babel extensions has been submitted for publication as an RFC [BABEL-EXT].
The use of Babel in a Standards Track HOMENET RFC would require a "downref" to non-Standards Track documents. It would also be necessary to finish publishing the extensions that are needed for the HOMENET use case as RFCs.
Does the protocol exhibit one or more of the critical initial success factors as defined in RFC 5218?
IS-IS exhibits the following critical initial success factors:
Babel exhibits the following critical initial success factors:
Are there implementers who are ready to implement the technology in ways that are likely to be deployed?
There is only one implementation of autoconfiguration and source-specific routing for IS-IS. There are some other open source implementations of the base protocol, but they are incomplete (as of February 2015).
As all major routing vendors have (proprietary) IS-IS implementations, the barrier for implmeneting IS-IS for HOMENET use is probably manageable, assuming that the willingness to implement modifications needed for HOMENET use is present.
The Babel implementation is open source software (MIT licensed), and the codebase has proven of sufficiently high quality to be easily extended by people who were not in direct contact with the author [RFC7298].
Are there customers (especially high-profile customers) who are ready to deploy the technology?
Yes. IS-IS is already widely deployed in operational networks.
Source-Specific Babel is currently deployed as part of the OpenWRT and CeroWRT operating systems. Additionally, the current version is used as a testbed for the HOMENET configuration protocol.
Are there potential niches where the technology is compelling?
Babel is a simple and flexible routing protocol. Like most distance-vector protocols, it requires little to no configuration in most topologies, and has proved popular in scenarios where competent network administration was not available. In addition, it has been shown to be particularly useful in scenarios where non-standard dynamically computed metrics are beneficial, notably wireless mesh networks and overlay networks.
If so, can complexity be removed to reduce cost?
As mentioned previously IS-IS can be significantly and easily pared down to fit the more limited scope of homenet use. However, no such pared down implementation exists, and the subset of the protocol that needs to be implemented has never been formally defined.
Babel is a fairly simple protocol -- RFC 6126 is just 40 pages long (not counting informative appendices), and it has been successfully explained to fourth year university students in less than two hours.
The stub-only implementation of Babel consists of 900 lines of C code, and has deliberately been kept as simple as possible. We expect a competent engineer to get up to speed with it within hours.
Is there a potential killer app? Or can the technology work underneath existing unmodified applications?
As IS-IS already qualifies as successful (bordering on wildly) a killer app is not particularly relevant.
Since Babel requires virtually no configuration, it is particularly suitable to scenarios where a dedicated network administrator is not available. Additionally, its support for dynamically computed non-standard metrics makes it particularly appealing in highly heterogeneous networks, (networks built on multiple link-layer technologies with widely varying performance characteristics).
Is the protocol sufficiently extensible to allow potential deficiencies to be addressed in the future?
IS-IS has been shown to be incredibly extensible, originally designed for a completely different protocol stack (OSI) it was easily adapted for IP use, then to multiple address families (IPv4, IPv6) and multi-topology. Indeed one of the major drivers of IS-IS's success is its extensibility and adaptability.
The extension mechanisms built into the Babel protocol [BABEL-EXT] have been shown to be a solid basis on which many backwards-compatible extensions have been built, including one that fundamentally changes the structure of announcements [BABEL-SS] and one that needs a non-trivial extension to the space of metrics [BABEL-Z].
If it is not known whether the protocol will be successful, should the market decide first? Or should the IETF work on multiple alternatives and let the market decide among them? Are there factors listed in this document that may predict which is more likely to succeed?
For IS-IS the market has already decided that the protocol is successful in a fairly wide variety of deployments. [We're speaking of source-specific, autoconfiguring IS-IS here? And are we speaking of small, unadministered networks? -- jch]
Source-specific Babel is probably the only source-specific routing protocol that has seen deployment and is being used in production.
Plain Babel has seen a modest amount of deployment, most notably for routing over wireless mesh networks and large-scale overlay networks. However, it remains a young protocol, certainly much younger than IS-IS.
The authors are grateful for the input of Steven Barth, Denis Ovsienko and Mark Townsley.
| [BABEL-EXT] | Chroboczek, J., "Extension Mechanism for the Babel Routing Protocol", Internet Draft draft-chroboczek-babel-extension-mechanism-03, June 2013. |
| [BABEL-SS] | Boutier, M. and J. Chroboczek, "Source-Specific Routing in Babel", Internet Draft draft-boutier-babel-source-specific-00, November 2014. |
| [BABEL-Z] | Chroboczek, J., "Diversity Routing for the Babel Routing Protocol", Internet Draft draft-chroboczek-babel-diversity-routing-00, July 2014. |
| [DELAY-BASED] | Jonglez, B. and M. Boutier, "A delay-based routing metric", March 2014. |
| [ISIS-AUTOCONF] | Liu, B., "ISIS Auto-Configuration", Internet Draft draft-liu-isis-auto-conf-03, October 2014. |
| [ISIS-SS] | Baker, F. and D. Lamparter, "IPv6 Source/Destination Routing using IS-IS", Internet Draft draft-baker-ipv6-isis-dst-src-routing-02, October 2014. |
| [RFC1142] | Oran, D., "OSI IS-IS Intra-domain Routing Protocol", RFC 1142, February 1990. |
| [RFC6126] | Chroboczek, J., "The Babel Routing Protocol", RFC 6126, April 2011. |
| [RFC7298] | Ovsienko, D., "Babel Hashed Message Authentication Code (HMAC) Cryptographic Authentication", RFC 7298, July 2014. |
| [SS-ROUTING] | Boutier, M. and J. Chroboczek, "Source-sensitive routing", December 2014. |