We all know that Internet routing tables grow exponentially. The migration from IPv4 to IPv6 was supposed to solve that problem through strict enforcement of hierarchical IP addresses, but IPv6 architects failed to consider the business needs of service providers and their customers, and no changes were made to the network layers above IP.
For example, the Stream Control Transmission Protocol (SCTP), the protocol that natively supports multihoming, will probably never gain mainstream acceptance. In the end, the hope for hierarchical IPv6 addressing turned to myth.
Three technical factors are making us pollute Internet routing tables with prefixes belonging to end-customer networks: multihoming, traffic engineering, and the lack of security in Border Gateway Protocol (BGP). The first two arise from the fact that IP addresses have dual semantics (owing mainly to broken socket API); they indicate the resource (the Identifier) you are trying to reach as well as the location (the End-User Locator) of the resource. Here's why Internet routing tables are headed for a fall:
- Multihoming. If you want to ensure that a mission-critical server remains reachable through the Internet, you have to advertise its IP address (more precisely, an IP prefix containing its IP address) to more than one service provider. That same prefix is then propagated globally -- through multiple alternate paths -- consuming memory structures in every router carrying the full Internet routing.
- Traffic engineering. The destination-only, hop-by-hop routing paradigm used in the global Internet leaves end users and service providers with a single tool to influence inbound traffic flow. They have to selectively advertise small parts of their IP address space to various upstream service providers or peers. These smaller (more specific) prefixes are yet again spread throughout the global Internet.
- Lack of security within BGP. The lack of BGP security is a less common contributor to exploding Internet routing tables than the first two. To address it, some sites are advertising a large number of /24 prefixes to prevent hijacking attempts.
Possible fixes for the Internet routing table explosion
The only technology that addresses the Internet routing table explosion at the network layer is Locator/ID Separation Protocol (LISP).
NIL Data Communications
Numerous more or less theoretical approaches have been proposed to solve the multihoming and traffic engineering technical problems. These proposals include SCTP, the Host Identity Protocol (HIP) and Site Multihoming by IPv6 Intermediation (shim6). These are briefly described in my Upcoming Internet Challenges presentation.
All of these mechanisms change the TCP/IP protocol stack above the IP layer and must be implemented on end hosts, and so they influence all existing Layer 4 through Layer 7 infrastructure -- firewalls, load balancers and Web application firewalls (WAFs). It is completely unrealistic to expect any one of those mechanisms to be deployed in the near enough future to save us from overloading (and subsequently collapsing) the Internet.
Locator/ID Separation Protocol (LISP): A workable solution
The only technology that addresses the Internet routing table explosion at the network layer is Locator/ID Separation Protocol (LISP), which splits the semantics of an IP address and ideally introduces two IP address spaces: routing locators (RLOCs) and end-point identifiers (EIDs).
- Routing locators ideally belong to a strictly hierarchical transport address, where each ISP would advertise a single (IPv6) prefix to the global Internet. In this address space, each ISP-to-customer connection would be associated with addresses belonging to the ISP's address space, thus preserving the strict hierarchy. Only the customer routers directly connected to an ISP would have a routing locator. Note: During the IPv6 migration period, existing IP addresses would be part of the routing locator address space.
- End-point identifiers (or host addresses) are not globally routable and thus do not need to be hierarchical. Clients do not need to know the path toward the server EID. They should use a default route toward a router with a routing locator.
Packet forwarding across a LISP infrastructure is very similar to packet forwarding in a BGP-free core network or to MPLS VPN packet forwarding.
Ingress tunnel routers (ITRs) perform the mapping between EIDs and RLOCs. When they receive a packet sent toward an EID, they perform an EID-to-RLOC lookup, encapsulate the end user's packet into a LISP envelope (another UDP+ IP packet) using egress RLOC as the destination IP address, and send the resulting LISP packet toward the egress RLOC.
An egress tunnel router (ETR) receives a LISP packet addressed to one of its RLOCs, removes the LISP envelope, caches the source EID-to-RLOC mapping (it will be used for return traffic), and forwards the end user's packet toward the destination EID.
LISP clearly requires an out-of-band EID-to-RLOC mapping service. While the baseline LISP infrastructure is quite stable, the mapping service is still somewhat hazy. Several mapping service proposals have been submitted, and the LISP-ALT (using GRE tunnels to connect to the mapping service and a separate BGP infrastructure to provide the mapping propagation) is the likeliest candidate. LISP-ALT has been implemented (along with the rest of LISP functionality) in Cisco IOS, Cisco IOS XE and Cisco NX-OS to support the early LISP adopters, Facebook among them.
LISP architecture solves multihoming, traffic engineering challenges
The separation between RLOC and EID addresses cleanly solves the multihoming challenges: A single EID is associated with multiple RLOCs. LISP also addresses traffic engineering needs – different ITRs receive different RLOCs for the same EID – or even IP mobility (the RLOC changes when a host is moved, while EID stays the same).
Last but not least, LISP can be gradually introduced into the Internet. Its architecture includes proxy ITRs and ETRs that link native Internet to LISP-enabled Internet, making it a close-to-perfect solution to meet the exploding Internet routing table challenge. The only problem LISP faces is motivation. It works best when deployed on customer premises equipment (CPE) devices, but end users have no motivation to jump into yet another new technology as long as service providers are willing to let them advertise globally routable IPv4/IPv6 address prefixes.
About the author: Ivan Pepelnjak, CCIE No. 1354, is a 25-year veteran of the networking industry. He has more than 10 years of experience in designing, installing, troubleshooting and operating large service provider and enterprise WAN and LAN networks and is currently chief technology advisor at NIL Data Communications, focusing on advanced IP-based networks and Web technologies. His books include MPLS and VPN Architectures and EIGRP Network Design. Check out his IOS Hints blog.
This was first published in August 2010