By: David Meyer
Date: October 7, 2007
The IAB’s Routing and Addressing Workshop(1), held in October 2006 in Amsterdam, rekindled interest in scalable routing and addressing architectures for the Internet. Among the many issues driving current interest are concerns about the scalability of the routing system and the imminent depletion of the IPv4 address space. This article is a summary of the Routing Research Group (RRG) meeting at IETF 69 in Chicago, where discussions took place about the proposals designed to address the problems and issues that were identified in Amsterdam.
Since the Amsterdam workshop, several proposals have emerged that attempt to address concerns expressed both there and elsewhere(2). In general, those proposals are based on the so-called ID/Locator separation(3), which makes the assumption that separating the endpoint identification and routing locator functions of the IP address will lead to advantages for aggregatability (our only real tool to make the core routing system scale), mobility, and security. Among the proposals presented at the RRG meeting at IETF 69 were eFIT(4), LISP(5), and Six/One(6) (an interesting hybrid incorporating elements of shim67 and 8+8/GSE).(8) Note that these proposals seek a degree of incremental deployability, and in general they assume that the core routing system will not change. In addition, several of the proposals also require a system to map from “ID” to “Locator.” (Proposals presented in the mapping space included APT(9), LISP-CONS(10), and NERD).(11)
Most of the existing routing and addressing proposals leverage the one or more levels of indirection inherent in the ID/Locator separation idea to create one or more new namespaces. In most cases, two namespaces are utilised. One namespace-the End-point Identifiers (or EIDs)-is used to address hosts. The other space, known as Routing Locators (or RLOCs), is used for packet routing across a transit domain. The goal of this indirection is to allow efficient aggregation in the RLOC space (which can be thought of as the current Default Free Zone, or DFZ) in order to provide persistent identity in the EID domain and, in some cases, to provide for secure and efficient mobility.
The RRG meeting in Chicago focused on the current set of proposals in this space, which fall into two broad categories: (1) map-and-encap and (2) address rewriting. The approaches differ depending on whether the translation occurs through address rewriting or tunneling and, in one case (Six/One), depending on where the indirection is implemented. The proposals are outlined as follows.
The general idea behind so-called map-and-encap (written map-n-en-cap) schemes, as originally described by Bob Hinden and Steve Deering, is that there are two address spaces: one used within a domain (the EID space) and one used to transit between domains (the RLOC space). The hope is that since the RLOC space is, in theory, decoupled from nontopologically assigned EID space, map-n-encap schemes will provide for efficient aggregation of the RLOC space-that is, the global routing state.
In the map-n-encap scheme, when a packet is generated, both its source and its destination “addresses” are taken from the site’s EID space. When a packet is addressed to a destination in another domain, it traverses the domain’s infrastructure to a border router (or other border element). The border router maps the destination of the EID to an RLOC, which corresponds to an entry point in the destination’s domain (hence the need for an EID-to-RLOC mapping system; mapping proposals are discussed later). This is the “map” phase of map-n-encap. The border router then encapsulates the packet and sets the destination address to the RLOC returned by the mapping infrastructure (if any; it may be statically configured as well). This is the “encap” phase of the map-n-encap model. Note that since map-n-encap works by appending a new header on an existing IP packet, it can work with both IPv4 and IPv6. While the destination EID is mapped to an RLOC in all of the proposals discussed here, the source EID in the packet may be treated differently within each proposal; specifically, it may or may not be mapped to an RLOC in the encapsulated packet. When the packet arrives at the destination border router, it is decapsulated and sent on to its destination. Note that this suggests that EIDs may need to be routable in some scope-most likely scoped to the local domain.
Two map-n-encap proposals were discussed at the RRG meeting: Enable Future Internet Innovation through Transit Wire, or eFIT(12), and the Locator/ID Separation Protocol, or LISP(13). The idea behind eFIT is that user networks and transit networks are separated in terms of both addressing and routing. User networks use EIDs, and transit networks use RLOCs. In eFIT, user and transit network routing domains are also separated. One of the interesting features of this proposal is that provider routing does not interact with routing in the user domains, which is different from the Border Gateway Protocol (BGP), wherein user networks “peer” with provider networks using the same routing protocol and address space. In particular, there is no routing protocol operating across the links between the user networks and the transit core.
In contrast, LISP does not propose any classification of address spaces beyond the EID and RLOC spaces. (More specifically, it has no concept of user or transit network spaces.) Rather, in the LISP formulation, a site is assigned an EID prefix from which it addresses its hosts. When a host wants to send a packet to a remote domain, both the source and the destination in the packet contain an EID. At the domain boundary, routers do the same map-n-encap operation as described earlier.
Another major difference between LISP and eFIT is that LISP assumes there will be no changes to the core routing infrastructure. That is, LISP is transparent to the BGP infrastructure, whereas eFIT introduces boundaries between the user and the transit core networks that are not present in the current interdomain (BGP) routing architecture. In particular, eFIT specifies that “There is no routing protocol operating across the links between the user networks and the transit core,” which represents a change from the current architecture.
It is worth noting that map-n-en-cap schemes have the benefit of not requiring host changes or changes to the core routing infrastructure. However, there is some difference in opinion over whether the encapsulation overhead of map-n-encap schemes is problematic or not.
The idea behind the address rewriting schemes-which were proposed originally by Dave Clark and later by Mike O’Dell(14)-is to take advantage of the 128-bit IPv6 address and use the top 64 bits as the routing locator (otherwise known as routing goop, or RG) and the lower 64 bits as the endpoint identifier. In this scheme, when a host emits a packet destined for another domain, the source address contains its identifier (frequently an IEEE MAC address) in the lower 64 bits and a special value (a unique “unspecified” value) in the RG. The destination address contains the fully specified destination address. (It has been proposed that the Domain Name System [DNS] would be used to find the destination address, but then how does one find the address of the DNS servers?)
When a packet destined for a remote domain arrives at the local domain’s egress router, the source RG is filled in (forming a full 128-bit address) and the packet is routed to the remote domain. On ingress to the remote domain, the destination RG is rewritten with the unspecified value. This ensures that the host doesn’t know what its network prefix is and, as such, enables the renumbering that would be required to maintain the congruence between prefix assignment and physical network topology that is required for the kind of “aggressive envisioned” in the 8+8/GSE specification.
Six/One was the address rewriting approach presented at the RRG meeting. Six/One is interesting because it borrows ideas from both shim6 and 8+8/GSE. In particular, Six/One borrows the shim6 concept that multihomed edge networks use provider-assigned addressing space from each of their providers and that hosts can use addresses from all of their providers interchangeably without breaking active transport sessions. Six/One borrows the 8+8/GSE idea of rewriting the high-order bits while packets are in fiight. It also introduces the concept of edge networks. An edge network can independently route packets between two attached hosts, and predictably, edge networks connect to transit networks for global connectivity.
In Six/One, a host’s addresses differ only in their high-order bits (in much the same way as they do in 8+8/GSE). However, in a Six/One, an edge network (or other service provider) may change the address in a packet depending on the provider to which the packet is being routed. As a result, the destination address a host puts into a packet serves as a suggestion to the edge network about which provider the host’s packets should be routed to. The edge network may choose to either follow that suggestion or rewrite the high-order bits of the address in accordance with a provider of its own choice. Note that this is different than in shim6, where the host selects the transit network; in Six/One, edge networks retain the ability to select a particular provider via rewriting. Hosts adapt to address rewrites in that they modify subsequent packets accordingly before injecting them into the network. Unlike 8+8/GSE, Six/One also adds to packets certain information that enables the receiving hosts to reverse address rewrites.
What’s new about Six/One is that regardless of address changes, an edge network can also use the added information to identify a remote host. The main difference between Six/One and 8+8/GSE, then, is that hosts are aware of their full addresses (including the RG) and can suggest a network provider to their local domain (in the much same way that is enabled by the shim6 protocol). One of the many interesting aspects of the Six/One proposal is that it combines the host-based locator selection feature of shim6 with a modified version of the address-rewriting approach of 8+8/GSE. Finally, note that unlike the map-n-encap solutions described earlier, a Six/One host looks up the entire 128-bit address of the destination host in the DNS (which may return multiple AAAA records for the destination). Therefore, like shim6, no additional mapping system is needed.
Since both map-n-encap and rewriting schemes rely on the addition of a level of indirection to the addressing architecture, it is necessary to map from the locally used address (EID) to the routing locator (RLOC). In the case of the map-n-encap schemes, it is a direct translation: an EID gets mapped to an RLOC. The situation is subtly different for the rewriting schemes: in general, such schemes must look up the entire destination address (which usually resides in the DNS) but it also must somehow find the source RG when rewriting the source address at a domain border. Six/One is a hybrid, since in that model the hosts know their entire address (including the RG), which can be looked up in the DNS, a property that is shared by shim6.
In the case of map-n-encap schemes, an EID-to-RLOC mapping service is required to make the service scale reasonably. (Could the same database be used to lookup RGs in the 8+8/GSE case?) There are three important parameters to consider in the creation of the architecture for a mapping service: the rate of updates to the database, the state required to be held by the mapping service, and the latency incurred during lookup. That is, a mapping system must minimise rate x state while still optimising lookup latency. Because most estimates put the size of the mapping database at O(10 10), the implication is that the update rate must be small. (Note that this is a primary reason that current mapping proposals do not incorporate reachability information into the mapping database.) In addition, the choice of push versus pull also has an effect on latency: if you push the entire database close to the edge, you improve lookup latency at the cost of increased state, and if you build a service that requires a mapping request in order to find an authoritative server for that mapping (in other words, pull), you reduce state in the core but you also increase latency. This suggests that a hybrid push/pull architecture might be the most effective. Regardless, architects need to take care not to import the dynamics (and hence the concomitant problems) of the routing system into the mapping database. If that were to happen, we wouldn’t have solved the problem; we would have only moved it.
Three mapping services were discussed at the RRG meeting: APT (A Practical Transit Mapping Service)15, NERD (a Not-so-Novel EID to RLOC Database)16, and LISP-CONS (a Content Distribution Overlay Network Service for LISP)17. The proposals can be broadly classified as either push or pull (though LISP-CONS might be considered a hybrid protocol) based on how they distribute the database.
Both APT and NERD are push protocols; that is, they push the mapping database to the edges for distribution. APT and NERD differ primarily (1) in how far toward the edge network the database is propagated (for example, APT has the concept of a default mapper so that some nodes can carry less than the complete database, whereas in NERD all nodes hold the complete database; in APT, the default mapper also winds up in the data path whenever it is used); (2) in database format (the APT database format isn’t specified, and NERD uses XML); and (3) in how the database is distributed and maintained (APT uses BGP, and NERD uses HTTP).
On the other hand, LISP-CONS is primarily a pull protocol. That is, mappings must be pulled (via a query mechanism) from the authoritative severs. The actual EID-to-RLOC mappings reside in authoritative Content Access Resources (CARs), and mapping queries and replies traverse a hierarchical overlay from requester to the authoritative CAR (and back).
Over the past 15 years, two major architectural approaches to the IP/Locator split have emerged: map-n-en-cap and address rewriting. Proposals regarding both of those approaches were presented at the IETF 69 RRG meeting. While much progress has been made since the IAB Routing and Addressing workshop in October 2006 in Amsterdam, significant unresolved issues remain within all of the proposals, including the question of whether the ID/Locator separation solution is actually the best approach to a scalable Internet routing architecture. Other questions remain, such as whether map-n-encap schemes are superior to rewriting schemes such as 8+8/GSE. And what about host-based schemes, such as Six/One? How do these schemes interact with other protocols being developed in this space, such as shim6 or HIP18). Finally, since in most cases these schemes require another name resolution (ID to Locator lookup), there are questions about how best to build such a resolution system and whether such a system can be built in a scalable way that also is secure and minimises latency.
Concerns about the scalability of the routing system, the effect of IPv6 on that scalability, and the rapid depletion of the IPv4 “free address pool” have fueled a growing interest in this area as well as in the broader topic of scalable routing and addressing architectures for the Internet. More work needs to be done in the areas of security and mobility. And a deeper understanding of cost/benefit relationships-as in, Who bears the cost and who stands to benefit?-would prove useful. More generally, even transition mechanisms are not well understood. It all adds up to a very interesting set of RRG meetings for IETF 70.
- D. Meyer et al., “Report from the IAB Workshop on Routing and Addressing,” RFC (Request for Proposal) 4984.
- T. Narten et al., “Routing and Addressing Problem Statement,” draft-narten-radir-problem-statement-00.txt.
- N. Chiappa, “Endpoints and Endpoint Names: A Proposed Enhancement to the Internet Architecture,” http://ana.lcs.mit.edu/~jnc//tech/endpoints.txt
- D. Massey, L. Wang, B. Zhang, and L. Zhang, “A Proposal for Scalable Internet Routing and Addressing,” draft-wang-ietf-efit-01.txt
- D. Farinacci et al., “Locator/ID Separation Protocol (LISP),” draft-farinacci-lisp-03.txt
- C. Vogt, “Six/One: A Solution for Routing and Addressing in PIPv6,” draft-vogt-rrg-six-one-00.txt
- E. Nordmark, “Shim6: Level 3 Multihoming Shim Protocol for IPv6,” draft-ietf-shim6-proto-08.txt
- M. O’Dell, “GSE-an Alternate Addressing Architecture for IPv6,”http://www.watersprings.org/pub/id/draft-ietf-ipngwg-gseaddr-00.txt
- D. Jen et al., “APT: A Practical Transit Mapping Service,” draft-jen-apt-00.txt
- D. Meyer et al., “LISP-CONS: A Content Distribution Overlay Network Service for LISP,” draft-meyer-lisp-cons-02.txt
- D. Massey, L. Wang, B. Zhang, and L. Zhang, “A Proposal for Scalable Internet Routing and Addressing,” draft-wang-ietf-efit-00.txt.
- Farinacci, op. cit.
- O’Dell, op. cit