A High-Level overview of CISCO LISP

Recently, there have been a lot of talks around Cisco LISP - location and Identity Separation Protocol. This is a “new” technology aiming to resolve some of the Internet scalability issues and which has been implemented in IOS 15.x. In this blog publication we are going to give a general overview of LISP, pointing out benefits as well as drawbacks of the technology.

Hierarchical Routing and its Problems

Ever since ARPANet launched, routing in packet switched networks (PSNs) has been based on hierarchical network addressing to achieve scalability. The groundbreaking work by Kleinrock and Kamoun named "Hierarchical Routing for Large Networks, Performance Evaluation and Optimization" ([KLEIN]) clearly outlined all ideas of hierarchical routing. The main result of this work is that for a network of arbitrary connected N nodes it is possible to devise a hierarchical clustering scheme where nodes inside a single cluster only have to know routes to the nodes in the same cluster and other clusters, provided that addresses are assigned to the nodes following the hierarchical structure. The routing is assumed to be a classic shortest-path selection process. Under the optimal partitioning scheme, the size of routing table on every router would be of order O(log(N)).

Even though this approach promises compact routing tables if implemented properly, there are three main drawbacks here. Firstly, this approach required strict, topology-based addressing, which was perfect in a static environment but didn't work well with mobile nodes, changing their point of attachment. Secondly, it resulted in suboptimal routes, as every cluster had limited knowledge of the outside topology. The resulting routing paths were longer than shortest paths, or as they say have "stretch" factor above 1 - e.g. a stretch of 2 means that the path is twice as long as optimal shortest path. In addition to these two main issues, hierarchical routing adds the management burden of keeping address space hierarchical, following the network clustering structure.

The modern Internet was built on the same shortest path routing concept using hierarchical addressing for routing scalability (though BGP makes it more complicated than it could have been). This model started showing some signs of instability at the end of the 90s. Dramatic growth of Internet routing tables put a serious burden on the routing systems as a direct result of explosive routing-tables growth. This growth was a result of two main processes: topology-independent addresses that were obtained for Internet multihoming and routing optimization which has been achieved by injecting "longer" or more specific prefixes into Internet routing tables. These processes attempt to overcome limited mobility and suboptimal routing inherent to hierarchical routing. Even though BGP was designed with scalability in mind, carrying modern Internet routing tables in the core networks becomes a huge burden, not only because of the size of RIB and FIB but also because of the network instabilities exposed by poor summarization. There are some approaches to alleviate the problem, such as Virtual Aggregation ([VA-DFZ]) for in-core FIB size reduction or BGP-aware DNS (see [BGP-DNS]) for efficient multihoming based on PA (Provider Aggregatable) addresses, but they do not offer ultimate solution and have not been widely deployed.

What is CISCO LISP

The main problem that causes routing table explosion is inefficient multihoming in topology-aware addressing. With topology-based numbering, a node address represents its relative location in the topology. At the same time, mobility or ability to change attachment to the topology (e.g. multihoming) requires the node address to be more of a node identifier, which does not change with topology re-attachment. The dual function of IPv4 address (or any topology-based address, e.g. IPv6) prevents it from being effectively used in either role, and this fact has been acknowledged for many years. However, business needs do not allow easy transition from a topology-based addressing to any other, more efficient solution, though there have been a lot of those.

What LISP offers is loosening this location/ID duality by creating two parallel IPv4/IPv6 address spaces: one serving to identify locations (RLOCs or routing locators) and another serving to identify endpoint (EID or endpoint identifiers). To separate the two spaces, tunneling is implemented with outer headers using RLOCs and inner headers using EIDs. Effectively, the Internet is partitioned into the "core" based on hierarchical topology-based RLOC addressing and "edge" which uses "mobile" EIDs, with both addresses using the same format. Of course, the use of tunneling implies that EIDs have to be somehow mapped to the closest RLOCs. LISP achieves that by using ITRs (ingress tunnel routers) and ETRs (egress tunnel routers). Both types of routers reside on the "edge" of RLOC Internet and perform encapsulation, decapsulation and mapping functions: ITR receives native packets with EID addressing, finds the corresponding RLOC address of the "optimum" ETR and encapsulates the original packets in RLOC header. The packet is then routed across the network core toward the ETR where it is decapsulated and forwarded based on EID address and potentially using some other routing scheme than used for RLOCs.

In short, LISP creates two parallel namespaces (RLOCs and EIDs) mapped to different topologies (routing and endpoints). The first, underlying topology uses classic IPv4 addressing and the overlay topology may use any other (not necessarily hierarchical) identifiers. So far the EID space is normally based on IPv4 32 bit addresses - this allows for maintaining all applications unchanged. It is important to stress out that in theory EID and RLOC address spaces could be completely different: e.g. EIDs could be MAC addresses while RLOCs could be IPv4 addresses, implementing a sort of Ethernet tunneling. The main LISP workhorse is the mapping layer, which represents a "directory lookup" finding the RLOC "closest" to the destination EID. There could be multiple schemes used for mapping, such as ALT, CORD, NERD, DHT etc. This is probably the most important component of LISP architecture, and hence it desires special attention.

LISP Mapping Layer

The Internet has been dealing with distributed databases for quite some time, starting with DNS and BGP and evolving to Distributed Hash Tables (DHT) used in peer-to-peer overlay networks, such as Chord. You may be surprised to see BGP here, but you should not - with the growth and evolution of the Internet, BGP became more of a universal information distribution protocol than a simple routing solution.

In general, every scheme could be characterized as a Push, Pull or Hybrid model. The Push model works by broadcasting (in some efficient manner) all mapping information to all interested nodes. A good example could be BGP - information such as VPNv4 prefixes, communities and additional attributes is "flooded" to PE routers in SP network. This model presents minimum latency on information retrieval, but requires all interested nodes to store large amounts of state information. Pull models, such as DNS or DHT, distribute information more or less evenly across all participating nodes, and interested nodes need to issue information search requests to locate the mapping. Pull models typically build overlay networks to search for information. Various techniques could be used to improve lookup latency and reliability: e.g. local caching and information duplication in multiple nodes. Pull models are in general more scalable than push, but introduce increased operations delays, sometimes poorly predictable. Finally, Hybrid models attempt to combine the best of Push and Pull by pushing (broadcasting) some condensed information (e.g. discovery hints) to the interested nodes but requiring pull operations to retrieve the actual mappings. Hybrid models are more complex but theoretically offer better performance than pure Pull models.

In addition to the amount of state stored in every participating node, another important scalability factor for the mapping layer is the amount (rate) of changes it may handle. It is obvious that Push models offer rapid propagation of changes (normally in incremental manner) and worse scalability compared to Pull models, due to the fact that changes need to propagate to every interested node. Pull models are not very rapid at propagating changes, as this requires finding the authoritative node and then informing it of the updated information. The use of some performance optimization with the Pull models may further degrade update latency, e.g. it may take some time to expire stale cached information (recall DNS caching). Hybrid models may balance between the two endpoints trading off optimal behavior for extra complexity.

We mentioned multiple mapping models, but mainly going to discuss LISP-ALT (LISP alternative topology), which is being actively tested and supported in the latest IOS releases. The core idea of ATL is to maintain IPv4-based EID address spaces strictly hierarchical and aggregatable and overlay additional MP-BGP mesh (ALT-topology) over existing IPv4 network (RLOC topology). Tunneling techniques such as GRE could be used to implement the overlay topology used to route based on EID, with the tunnel endpoints routed in RLOC space. Since EID space follows a clean hierarchy, EID BGP tables should be small and manageable. Mapping information is not conveyed in overlay BGP mesh, but rather stored in ETRs (or other special devices). The overlay ALT-topology is used to route LISP mapping requests and replies, based on the MP-BGP next-hop values. Effectively, LISP-ALT is a hybrid push and pull model, where an overlay network is used to route LISP requests but the actual LISP mapping information is not propagated in BGP, but rather stored in mapping servers and returned in response to explicit requests. This allows for optimum summarization in EID address space.

In addition to ITR/ETR LIST-ALT also adds the "ALT" routers, which serve the purpose of additional logical endpoints for the ALT space. LISP-ALT topology aims at introducing minimal changes to existing software and, just like LISP technology in general, does not affect network endpoints (hosts) at all. Decoupling RLOC and EID topologies allows for making both of them hierarchical and aggregatable, thus reducing BGP table sizes both in network core and edge. This comes at the expense of additional management burden required to keep EID/RLOC topologies strictly hierarchical. On a positive note, once allocation has been properly done, any changes in physical attachment will not result in EID address space fragmentation - the overlay topology could be simply changed to accommodate for the new connection, without the need of renumbering EID spaces. Additionally, the EID-to-RLOC mapping layer allows for flexible traffic engineering - different RLOCs could be associated with different EID prefixes, even though ALT only propagates aggregated information in BGP.

The idea of separating address spaces and using overlay tunneling is not novel and has been around for years, implemented in MPLS BGP VPNs. In fact, the EID space looks exactly like a VPN implemented by means of VRF and LISP tunnels. The only significant change to this model is the addition of the mapping requests/replies which allow for the use of new unique traffic-engineering capabilities.

Have all problems been solved?

Not completely. Even though in theory the use of LISP-ALT model allows for transitioning to a highly aggregatable EID address space and reducing routing state in both the Internet core and edge domains it requires significant management efforts. This problem boils down to the fact that the same hierarchical routing model is retained with IPv4 LISP-ALT, resulting in the need to carefully manage EID address block allocation and possibly renumbering the Internet core to allow for better aggregation. Other mapping layer implementations, such as LISP-DHT (distributed hash tables) allow for effectively managing non-hierarchical, even flat address space, but have all typical drawbacks of Pull models. Furthermore, the requirement of keeping EID space strictly hierarchical in LISP-ALT seriously impacts "true mobility" implementation, where a single EID could move between its points of attachment. However, the problem of "static" mobility or ISP multihoming/changing is effectively addressed, as the potential points of attachment are known in advance and accounted for in the ALT topology.

Perspective

Theoretically, the LISP model solves the routing table growth problem, at the expense of added management complexity. LISP offers a non-disruptive transition approach, which does not affect end systems and allows for incremental deployment. Special techniques (proxy ITRs/ETRs not covered in this post) allow for LISP-enabled internet to interoperate with classic Internet during the transition period. But there is a significant problem: for any given organization, unless it is a Tier-1 ISP, there is no direct benefit of transition to LISP. Indeed, the main goal of LISP is to reduce the complexity of ever-growing DFZ tables, which is mainly a problem for core ISPs. For any company that sits at the "edge" of the Internet, the only visible effect of implementing Cisco LISP is increased complexity due to the need of renumbering and implementing an overlay topology. At the same time, the Internet edge is where LISP should be mainly deployed. Just like with IPv6, there is no motivation to transition to the new technology, which makes the prospects of rapid LISP adoption tough.

In addition to the deployment issues, there is a theoretical problem. LISP-ALT architecture implements the same hierarchical routing model for EIDs that has been used in the Internet for years. We already mentioned some of the problems of hierarchical routing earlier in this publication. The main problem is high management burden, required to coordinate and maintain hierarchical address space. Another problem is highly suboptimal routing, which manifests in excessive stretch on the topology exhibiting scale-free (power-law) behavior. Unfortunately, modern Internet seems to be a scale-free graph, which means hierarchical routing is not the best choice (see [COMPACT]). However, dismantling the hierarchical routing model requires a clean-slate redesign of the modern Internet, which is simply unacceptable. And thus, just like with IPv6, the Internet society is stuck in a difficult situation, where each solution is either not very effective or requires major Internet redesign.