The Locator/Identifier Separation Protocol (LISP)

by David Meyer

Introduction

The IAB’s October 2006 Routing and Addressing Workshop [8] renewed interest in the design of a scalable routing and addressing architecture for the Internet. Key issues driving this renewed interest include concerns about the scalability of the routing system and the impending exhaustion of the IPv4 address space. Since the IAB workshop, several proposals have emerged that attempt to address the concerns expressed both at the workshop and in other forums [7,9,12,13,14]. All of these proposals are based on a common concept: the separation of Locator and Identifier in the numbering of Internet devices, often termed the “Loc/ID split”. This article focuses on one proposal for implementing this concept: the Locator/Identifier Separation Protocol (LISP) [3].

The basic idea behind the Loc/ID split is that the current Internet routing and addressing architecture combines two functions: Routing Locators (RLOCs), which describe how a device is attached to the network, and Endpoint Identifiers (EIDs), which define “who” the device is, in a single numbering space, the IP address. Proponents of the Loc/ID split argue that this “overloading” of functions makes it virtually impossible to build an efficient routing system without forcing unacceptable constraints on end-system use of addresses. Splitting these functions, through the use of different numbering spaces for EIDs and RLOCs, will yield several advantages, including improved scalability of the routing system via greater aggregation of RLOCs. To achieve this aggregation, RLOCs must be allocated in a way that is congruent with the topology of the network (“Rekhter’s Law”). Today’s “Provider Allocated” IP address space is an example of such an allocation scheme. EIDs, on the other hand, are typically allocated along organizational boundaries. Since the network topology and organizational hierarchies are rarely congruent, it is difficult (if not impossible) to make a single numbering space efficiently serve both purposes without imposing unacceptable constraints (such as requiring renumbering upon provider changes) on the use of that space.

LISP, as a specific instance of the Loc/ID split, aims to decouple location and identity. By doing this, it will facilitate improved aggregation of the RLOC space, implement persistent identity in the EID space, and, in some cases, increase the security and efficiency of network mobility.

Implementing the Locator/ID Separation

There are two basic approaches to implementing the Loc/ID split: Map-and-encap and address rewriting. Each is briefly discussed below.

Map-n-encap

In the map-and-encap scheme (generally considered to have evolved from Bob Hinden’s ENCAPS protocol [24]), when a source sends a packet to the EID of a destination outside of the source domain, the packet traverses the domain infrastructure to a border router (or other border element). The border router maps the destination EID to a RLOC which corresponds to an entry point in destination domain (hence there is a need for a EID-to-RLOC mapping system; proposals are discussed below). 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. Thus map-n-encap works by appending a new header to the existing packet; the “inner header” source and destination addresses are EIDs, and the “outer header” source and destination addresses are in most cases RLOCs. When an encapsulated packet arrives at the destination border router, the router decapsulates the packet and sends it on to its destination. Note that this suggests that EIDs may need to be routable in some scope (likely scoped to the domain).

Map-n-encap schemes have the desirable property that they don’t in general require host changes or changes to the core routing infrastructure. In addition, map-n-encap schemes work with both IPv4 and/or IPv6, and retain the original source address (which is useful in various filtering scenarios). Controversy remains, however, as to whether the encapsulation overhead of map-n-encap schemes is problematic or not; opinions exist on both sides of this issue (see for example, [18]).

Address Rewriting

The basic idea behind the address rewriting schemes, originally proposed by Dave Clark and later by Mike O’Dell in his 8+8/GSE specification [11], is to take advantage of the 128-bit IPv6 address and use the top 64 bits as the routing locator (“Routing Goop”, or RG), and the lower 64 bits as the endpoint identifier (hence rewriting works only for IPv6). In this scheme, when a host emits a packet destined for another domain, the source address contains its identifier (frequently a IEEE MAC address) in the lower 64 bits, and a special value (meaning unspecified) in the RG. The destination address contains the fully specified destination address (RG and EID).

When a packet destined for a remote domain arrives at the localdomain’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 RG is; this, in theory, would enable the ease of renumbering that would be required to maintain congruence between prefix assignment and physical network topology that is required for the kind of “aggressive renumbering envisioned” in the 8+8/GSE specification.

The Locator/Identifier Separation Protocol (LISP)

LISP is designed to be a simple, incremental, network-based map-n-encap protocol which implements separation of Internet addresses into EIDs and RLOCs. Since LISP is a map-n-encap protocol, it requires no changes to host stacks and no major changes to existing database infrastructures. It is designed to be implemented in a relatively small number of routers. LISP is also an instance of what is architecturally called a “jack-up”, since the existing network layer is “jacked up” and a new network layer is inserted below it (the term “jacked up” is due to Noel
Chiappa). The LISP “jack-up” is depicted in Figure 1:

The LISP design aims to improve site-multihoming (for example, by controlling site ingress without complex protocols), improve ISP multihoming, decouple site addressing from provider addressing, and to reduce the size and dynamic properties of the core routing tables.

The LISP data plane (the map-n-encap operation) and the LISP control plane (the EID-to-RLOC mapping system) are very modular. In particular, while the base LISP specification defines the format of messages to query the mapping system and to receive responses from that system, it makes no assumptions on the architecture of potential mapping systems. As a result, several mapping systems have been proposed [0,1,4,5,6,10].

LISP Network Elements

The LISP specification defines two network elements: The Egress Tunnel Router (or ETR) and the Ingress Tunnel Router (ITR).

A LISP Egress Tunnel Router (ETR) is a router that receives LISP-encapsulated IP packets from the Internet on one side and sends decapsulated IP packets to site end-systems on the other side. In particular, an ETR accepts an IP packet where destination address in the “outer” IP header is one of its own RLOCs. The router strips the “outer” header and forwards the packet based on the next IP header found.

A LISP Ingress Tunnel Router (ITR) is a router that accepts IP packets from site end-systems on one side and sends LISP-encapsulated IP packets toward the Internet on the other side. In particular, an ITR accepts an IP packet with a single IP header (more precisely, an IP packet that does not contain a LISP header). The router treats this “inner” IP destination address as an EID and performs an EID-to-RLOC mapping lookup if necessary (i.e., it doesn’t already have an EID-to-RLOC mapping for the EID). The router then prepends an “outer” IP header with one of its globally-routable RLOCs in the source address field and the result of the mapping lookup in the destination address field. Note that this destination RLOC may be an intermediate, proxy device that has better knowledge of the EID-to-RLOC mapping closest to the destination EID.

LISP Data Plane Operation

When a host in a LISP capable domain emits a packet, it puts its EID in packet’s source address, and EID of the correspondent host in its destination address (note that hosts will typically look up EIDs in the Domain Name System (DNS)). If the packet’s destination is in another domain, the packet traverses the source domain’s infrastructure to one of its ITRs. The ITR maps destination EID to a RLOC which corresponds to an ETR that is either in the destination domain or proxy’s for the destination domain (how this mapping is accomplished in LISP is discussed below). The ITR then encapsulates the packet, setting the destination address to the RLOC of the ETR returned by the mapping infrastructure or by static configuration. Note that LISP is address family agnostic and as such can be used with both IPv4 and IPv6 (or any other address family). Figure 2 depicts the LISP IPv4 in IPv4 encapsulation.

When the packet arrives at the destination ETR, it decapsulates the packet and sends it on to its destination Again, note that this implies that EIDs need to be routable in some scope (likely scoped to the domain).

As mentioned above, the LISP specification defines three packet types designed to support an EID-to-RLOC mapping system. The first type of packet, the Data Probe, is a data packet that an ITR may send into the mapping system to probe for the mapping; the authoritative ETR will respond to the ITR with a Map-Reply message (see below) when it receives such a data packet. Note that in this case the ETR detects that the packet is a Data Probe by noticing that the inner Destination Address (DA) was copied to the outer DA by the ITR, i.e., the inner DA equals the outer DA and is an EID.

The second type of LISP packet used to support the mapping system is the Map-Request. An ITR may query the mapping system by sending a Map-Request message into the mapping system to request a particular EID-to-RLOC mapping. As in the Data Probe case, the authoritative ETR will respond with a Map-Reply message.

The third type of LISP packet used to support the mapping system is the Map-Reply. An ETR emits a Map-Reply under two conditions. First, if the ETR receives a LISP encapsulated packet in which the outer header’s destination address is the same as the inner header’s destination address, it knows that the packet is a Data Probe and can respond with a Map-Reply to the source ITR. The ETR may also receive a Map-Request, in which case it replies to the requesting ITR with the mapping.

LISP Control Plane

Both map-n-encap and address rewriting models rely on an additional of level of indirection in the addressing architecture to make the routing system scale reasonably. Since packets are sourced with an EID in the destination address field, and EIDs are not in general routable on the global Internet, the destination EID must be mapped to an RLOC in order to deliver the packet to another domain (i.e., across the Internet). In the case of the map-an-encap schemes, it is a direct translation: an EID gets mapped to a RLOC. The situation is subtly different for the rewriting schemes; in general such schemes must lookup the entire destination address (usually proposed to reside in the
DNS) [11,13], but must somehow determine the source RG when rewriting the source address at the domain border.

In either Loc/ID split model, an EID-to-RLOC mapping service is need to make the system scale reasonably and to make it operationally viable. There are three important scale parameters to consider when architecting a mapping service: the rate of updates to the mapping database, the state required to be held by the mapping service, and the latency incurred during database lookup. The scaling properties of the database are frequently characterized as a (rate*state) problem (ignoring for the moment the issue of lookup latency); as most estimates put the size of the mapping database at O(10^10), the database 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 vs. 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; if you architect a service that requires a mapping request find an authoritative server for that mapping (i.e., pull), you reduce state at the cost of increased lookup latency.

LISP-ALT: A LISP Control Plane

The basic idea behind LISP-ALT (or LISP-Alternative-Topology) [4] is to build an alternative logical topology for managing EID to RLOC mappings for LISP. This logical topology uses existing technology and tools, specifically the Border Gateway Protocol [17] and its multi-protocol extension [15], along with the Generic Routing Encapsulation [16] protocol to construct an overlay network of devices that advertise EID-prefixes only. As was the case for the LISP data plane, an important design goal of LISP-ALT is to minimize the number of changes to existing
hardware and/or software that are required to deploy the mapping system. As such, LISP-ALT requires no modifications to either BGP or GRE.

Note that LISP-ALT is a hybrid push/pull architecture. Aggregated EID prefixes are “pushed” among the LISP-ALT routers and, optionally to ITRs (which may elect to receive the aggregated information, as opposed to simply using a default mapping). Specific EID-to-RLOC mappings are “pulled” by ITRs either via Map-Requests or Data Probes, both of which are routed over the alternate topology and result in Map-Replies being generated by ETRs.

The basic idea behind in LISP-ALT, then, is to use BGP running over a GRE overlay to build the reachability required to route Data Probes, Map-Requests, and Map-Replies over the alternate topology. The ALT Routing Information Base (RIB) is comprised of EID prefixes and associated next hops. The LISP-ALT routers talk External BGP (eBGP) to each other in order to propagate EID prefix update information, which is learned either over eBGP connections from the authoritative ETR, or by configuration. ITRs may also eBGP peer with one or more LISP-ALT routers in order to route Data Probe packets or Map-Requests.

In summary, the LISP-ALT uses BGP to propagate EID-prefix reachability information used by ITRs and ETRs to forward Map-Requests, Map-Replies, and Data Probes. This reachability is carried as IPv4 or IPv6 Network Layer Reachability Information (NLRI) without modification (since the EID space has the same syntax as IPv4 or IPv6). LISP-ALT routers eBGP peer with one another, forming the overlay network. A LISP-ALT router near the edge learns EID prefixes which are originated by authoritative ETRs. In general then, LISP-ALT routers aggregate EID prefixes, and forward Data Probes, Map-Requests, and Map-Replies.

Threat Models and Mitigation

As in any Loc/ID split approach, a critical operation is the creation of Locator to ID binding state that devices will use over time. In the case of LISP, the critical operation is the creation of EID-to-RLOC mappings in the ITR and the ETR. These mappings can be obtained in three ways:

• By using the information obtained from a LISP data packet.
• By using the information contained in the Map-Reply message.
• By using a EID-to-RLOC mapping database

LISP mitigates attacks on the first two techniques by including a nonce in the LISP header; the nonce is a 32-bit randomly generated number (generated by the source ITR), and is used to test route-returnability; more specifically, an ETR will echo the nonce back to the ITR in a Map-Reply message. That is, the nonce, combined with the ITR accepting only solicited Map-Replies provides a base-level of authentication for Map-Replies. Note however, that these techniques do not protect against Man-In-The-Middle attacks.

The LISP design assumes that many (if not most) most security mechanisms will be part of the mapping database service when using control-plane procedures for obtaining EID-to-RLOC mappings. DoS attack prevention, on the other hand, will depend on an implementation’s ability to rate-limit Map-Requests and Map-Replies (in the control-plane), as well as its ability to rate-limit the number of data triggered Map-Replies (e.g., in response to Data Probe packets).

See [19] for a more detailed preliminary threat analysis for LISP.

LISP and Fast Endpoint Mobility

Fast endpoint mobility occurs when an endpoint moves relatively rapidly, changing its IP layer network attachment point, and where maintenance of session continuity is a goal. Mobile IPv4 [20] and Mobile IPv6 [21,22] mechanisms can be used in this case; note however, that the interaction of Mobile IP with LISP need further exploration See the LISP specification [3] for additional detail.

In summary, the major problem introduced by a Loc/ID split scheme is that as an endpoint moves, it may require changes to the mapping between its EID and a set of RLOCs for its new network location. When this is added to the overhead of mobile IP binding updates, some packets might be delayed or dropped. In general, the problem is controlling the update rate (i.e., the (rate*state) product described above), and is an area of ongoing research.

Multicast

A multicast group address, as defined in the original Internet architecture, is an identifier of a grouping of topologically independent receiver host locations. The address encoding itself does not determine the location of the receiver(s). The multicast routing protocol, and the network-based state the protocol creates, determines where the receivers are located.

In the LISP context, a multicast group address is both an EID and a RLOC. As such, no specific action need be taken for a destination addresses; a group address that appears in an inner IP header (built by a source host) will be used as the destination EID by an ITR as a destination address when it LISP-encapsulates the packet (i.e., the ITR will use the same group address as the destination RLOC). The source RLOC, as is usually the case, will be the ITR’s IP address (i.e., one of its RLOCs).

At the receiving side, PIM [23] has to translate the source addresses Join/Prune messages from RLOCs to EIDs when mulicast packets are forwarded by the ETR. However, in contrast to the unicast case (where a Map-Request is sent by the ITR at forwarding time), a Map-Request can be sent when the multicast tree is being built.

Putting it all Together: A Day in the Life of a LISP Packet

When a host in a LISP capable domain wants to send a packet, if first looks up the correspondent host’s EID in the DNS. It then puts its EID in packet’s source address, and EID of the correspondent host in its destination address; if the packet’s destination is in another domain, the packet will traverse the source domain’s infrastructure to one of the domain’s ITRs.

If the ITR has cached the EID-to-RLOC mapping for the destination EID, it sets the Destination RLOC in the outer
(encapsulated) header to the cached RLOC, and the Source RLOC to its RLOC (note that the inner header has the Source host’s EID as the source and the Destination’s EID in the destination field). The packet is then sent over the Internet to the ETR indicated in the Destination RLOC, which decapsulates the packet and sends it on to the Destination EID.

If, on the other hand, the ITR doesn’t have a EID-to-RLOC mapping for the destination EID, it encapsulates the packet in a LISP header in which the destination address is the same as the inner header’s destination address, namely, the EID of the destination host. This is a Data Probe packet, and is routed over the LISP-ALT topology to the LISP-ALT router (typically an ETR, but this is not required) that is authoritative for the EID-to-RLOC mapping. When the ETR receives the Data Probe packet, it decapsulates the packet and sends it on to the Destination EID and sends a Map-Reply to the source’s ITR so subsequent packets will be sent natively over the Internet (as opposed to over the LISP-ALT overlay network). This query/response transaction is only required for the first packet sent between sites; all subsequent packets are sent LISP-encapsulated directly between the ITR and the ETR (and in particular, not over the LISP-ALT topology). Finally, note that the ITR could also pre-load its cache with mappings for popular destinations using the Map-Request message, avoiding the Data Probe packet (and associated latency, if any) altogether.

For example, consider the scenario depicted in Figure 3. In this case, a source S with EID 1.0.0.1 wants to send a packet to destination D who’s EID is 2.0.0.2. The packet arrives at ITR S2, which does not have a EID-to-RLOC mapping for 2.0.0.2. S2 LISP-encapsulates the packet with the outer header having its RLOC (11.0.0.1) as the source address, copies the destination EID (2.0.0.2) from the inner header to the outer header destination, and sends the data packet (a Data Probe) to into the LISP-ALT topology. The packet follows the paths computed by BGP in the LISP-ALT topology to ETR D2. When D2 receives the packet, it decapsulates it and forwards the packet to the destination (2.0.0.2); D2 also responds with a Map-Reply message that tells S2 (11.0.0.1) that the EID-to-RLOC mapping for 2.0.0.0/8 has two elements, ETR D1 (who’s RLOC is 12.0.0.2) and ETR D2 (who’s RLOC is 13.0.0.2). After receiving the Map-Reply, ITR S2 can send LISP-encapsulated packets natively over Internet (i.e., not over
the ALT topology).

Note that the mapping has priority (p) and weight (w) attributes. Priorities tell the ITR which ETRs to use in which order, and weights tell the ITR how to split load across ETRs of a given priority (w is a percentage of traffic that should go to each ETR). In this case, both ETRs have the same priority (1), and have weight 50 (i.e., each ETR should receive 50 percent of the traffic).

New Functionality Enabled By The Mapping System

Weights and priorities provide new functionality for multi-homed sites, which can use these features to control how traffic ingressing to the site is spread across its links without the complexity and overhead of running BGP. In particular, a multi-homed site can configure its mapping database so that its links are used in an “active-active” configuration (that is, both links are in use). This situation is depicted in Figure 3, where the mapping databases entry 2.0.0.0/8 has two ETRs at the same priority that are equally weighted. This means that the ITR will spread flows equally among the two ETRs.

This functionality is particularly attractive for Small Office Home Office (SOHO) sites that desire both redundancy in their Internet connections and the ability to easily load share across those links in an active-active configuration, without the complexity and operational expense of running BGP.

Another interesting functionality enabled by the LISP control plane is the ability to mitagate some types of DoS attacks. In particular, if an ETR notices that it the subject of a DoS attack from behind an ITR (i.e., DoS packets are destined to an EID-prefix for which it is authorative), it can use the LISP locator reachability bits (see Figure 2) to tell the the source ITR that the RLOC for that EID-prefix is not available. The ETR accomplishes this by sending a locator-reachability bit of zero for the RLOC to the offending ITR. Note that this functionality is similar to Ioannidis and Bellovin’s “ICMP Pushback” proposal [25].

Performance Considerations

There are two primary performance concerns with the LISP and its associated mapping protocol(s):

• Encapsulation Overhead, and
• EID-to-RLOC Lookup Latency and Packet Loss

In the case of encapsulation overhead, the concern is that the addition of the LISP header will cause the encapsulate packet will exceed the path MTU. As mentioned above, this is still an area of active research (see for example, [18]).

In the case of lookup latency and packet loss, since LISP-ALT uses BGP to find a particular EID-to-RLOC mapping, there could be latency associated with the first few packets in the first flow between sites (note its only the first flow; subsequent flows can use the mapping installed in the ITR). However, this latency is mitigated, and the initial packets are not lost since LISP can send the first few data packets over the control plane; these are the Data Probe packets. There is additional latency associated with the time required for the destination ETR to return the Map-Reply. However, once this initial transaction is completed, there is no additional latency injected by the mapping
system.

As mentioned above, there is a tradeoff in the mapping system among the state required to be held by network elements, the rate of updates to the mapping system, and the latency incurred when looking up an EID-to-RLOC mapping. LISP-ALT is a hybrid (push/pull) architecture that attempts to minimize the state requirements on ITRs, while at the same time minimizing lookup latency.

Conclusions

LISP is a new protocol that implements the Loc/ID split using a map-n-encap protocol. It obtains the advantages of the level of indirection afforded by the Loc/Id split while minimizing changes to hosts and to the core routing system. In addition, LISP enables new functionality such BGP-free multi-homing in an active-active configuration.

Acknowledgments

The LISP specification and supporting documents are the work of many people, including Scott Brim, Noel Chiappa, Dino Farinacci, Vince Fuller, Eliot Lear, Darrel Lewis, and Dave Oran.

References

[0] Brim, S., et. al., EID Mappings Multicast Across Cooperating Systems for LISP, draft-curran-lisp-emacs-00.txt. Work in progress.
[1] Brim, S., et. al., LISP-CONS: A Content distribution Overlay Network Service for LISP, draft-meyer-lisp-cons-03.txt. Work in progress.
[2] Chiappa, N., Endpoints and Endpoint Names: A Proposed Enhancement to the Internet Architecture.
[3] Farinacci, D. et. al., Locator/ID Separation Protocol (LISP), draft-farinacci-lisp-07.txt. Work in progress.
[4] Fuller, V., et. al., LISP Alternative Topology (LISP-ALT), draft-fuller-lisp-alt-02.txt. Work in progress.
[5] Jen, D., et. al., APT: A Practical Transit Mapping Service, draft-jen-apt-01.txt. Work in progress.
[6] Lear, E., NERD: A Not-so-novel EID to RLOC Database, draft-lear-lisp-nerd-03.txt. Work in progress.
[7] Massey, D., Wang, L., Zhang, B., and L. Zhang, A Proposal for Scalable Internet Routing and Addressing, draft-wang-ietf-efit-01.txt. Work in progress.
[8] Meyer, D. et. al., Report from the IAB Workshop on Routing and Addressing, RFC 4984 .
[9] Narten, T. et. al., Routing and Addressing Problem Statement, draft-narten-radir-problem-statement-01.txt. Work in progress.
[10] Nordmark, E., Shim6: Level 3 Multihoming Shim Protocol for IPv6, draft-ietf-shim6-proto-09.txt. Work in progress.
[11] O’Dell, M., GSE – An Alternate Addressing Architecture for IPv6, http://www.watersprings.org/pub/id/draft-ietf-ipngwg-gseaddr-00.txt
[12] Templin, F., The IPvLX Architecture, draft-templin-ipvlx-08.txt. Work in progress.
[13] Vogt, C., Six/One: A Solution for Routing and Addressing in IPv6, draft-vogt-rrg-six-one-01.txt. Work in progress.
[14] Whittle, R., Ivip (Internet Vastly Improved Plumbing) Architecture, draft-whittle-ivip-arch-01.txt. Work in progress.
[15] Bates, T., et. al., Multiprotocol Extensions for BGP-4, RFC 2858.
[16] Farinacci, D., et. al., Generic Routing Encapsulation (GRE), RFC 2784.
[17] Rekhter, Y, (Ed.), et. al., A Border Gateway Protocol 4 (BGP-4), RFC 4271.
[18] Templin, F., Subnetwork Encapsulation and Adaptation Layer, draft-templin-seal-02.txt . Work in progress.
[19] Bagnulo, M., Preliminary LISP Threat Analysis, draft-bagnulo-lisp-threat-01.txt.
[20] Perkins, C., IP Mobility Support for IPv4, revised, draft-ietf-mip4-rfc3344bis-05.txt. Work in progress.
[21] Johnson, D., Perkins, C., and J. Arkko, Mobility Support in IPv6, RFC 3775.
[22] Arkko, J., Vogt, C., and W. Haddad, Enhanced Route Optimization for Mobile IPv6, RFC 4866.
[23] Fenner, B., et. al., Protocol Independent Multicast – Sparse Mode (PIM-SM): Protocol Specification (Revised), RFC 4601.
[24] Hinden, R., New Scheme for Internet Routing and Addressing (ENCAPS) for IPNG, RFC 1955.
[25] Ioannidis John, and Bellovin, S., Pushback: Router-Based Defense Against DDoS Attacks.

---

Last Update: 02.27.2008 by dmm@1-4-5.net