This document attempts to look at abstract architectural issues associated with the BGP routing table growth problem while avoiding engineering details as requested by the Routing Research Group chair.
The root cause of the routing table growth problem is that we're using the same element (IP address) to express both the communications identity (ID) needed by the layer 4 and higher protocols to keep track of communication sessions with other hosts, and the node's present locations (LOC) within the network topography.
Changing a host's identity is hard. It can't be done without ending any active communication sessions. Client systems can mostly change identity with only that sacrifice, but changing a server's identity requires changes in many other hosts' references which are unwieldy or impractical to make. As a result, the ID strongly resists change. Because the LOC is bound to the ID, the LOC strongly resists change even when you desire to move it elsewhere in the network.
Also, hosts find it very difficult to present two LOCs from separate parts of the topography graph. Packets from such hosts would need to be "policy routed" by the source address until they reach a transit-free network level in order to preserve security-required source filtering, a function not inherent to modern dynamic routing protocols. As a result, multihomed systems generally connect distant portions of the network topography instead of presenting a small number of aggretatable stubs.
Thus we end up with a great deal of duplication where more than one LOC holds the same spot in the topography (disaggregation and fragmentation) and trivial multihoming forces a general graph topography with very limited hierarchical aggregation of the LOCations that routers route by.
Strategy A.
Do local routing by the address (which functions as both ID and local LOC) but have each packet flow through an encoder which attaches a second Remote LOC (RLOC) before the packet enters the internetwork core. Do not route by the address in the core; route by RLOC. Limit RLOC routing in the core so that only service providers (ISPs) with significant interconnection have their own RLOCs. Fewer than 10,000 such "core ISPs" exist today and the number is growing much more slowly than the routing table overall. Once the packet reaches the network identified by the RLOC, local routing by address takes over for final delivery. Distribute RLOCs through the core via a typical distance-vector or link-state routing protocol.
Variants include:
A1a. Each core ISP has one RLOC.
A1b. Each core ISP has a small number of RLOCs for traffic engineering (TE).
A1c. Each core ISP has one aggregated set of RLOCs which it may hierarchically assign to customers downstream and/or disaggregate for TE.
Methods for mapping the address to one or more RLOCs include:
A2a. IDs statically mapped to each RLOC are periodically pushed towards a central or distributed registry. The full list is periodically downloaded to the encoders which add RLOCs to the packets.
A2b. IDs dynamically mapped to each RLOC are pushed towards a central or distributed registry as they change. The registry pushes them in near-real time to the encoders which add RLOCs to the packets.
A2c. IDs dynamically mapped to each RLOC are pushed towards a central or distributed registry as they change. Encoders request and briefly cache individual mappings from the registry as needed.
Failure handling approaches include:
Link failures in the Internet core cause the RLOCs to be rerouted with no change to the address-RLOC map.
A3a. RLOC encoders detect when particular RLOCs are no longer reachable at all and fall back on secondary RLOCs for a particular address. Encoders rely on active failure messages from some system in the RLOC-specified network to indicate that a host is no longer available via that RLOC, causing them to fall back on secondary RLOCs for that host.
A3b. Link failures which prevent parts of the RLOC's network from reaching a destination host it serves cause a dynamic change to the address-RLOC map, depreferencing the affected RLOC.
Strategy B.
Assign heirarchically aggregatable LOCs to every host. Assign multiple LOCs to each host such that in the network topography hosts appear as stubs in multiple locations instead of forming distant connections in the graph. Having reduced the network topology to something relatively close to a hierarchy, perform plain old hierarchical aggregation on the LOCs. Add and remove LOCs to each host dynamically during operation as needed to reflect changes in the nearby network heirarchies.
Attach source and destination LOCs when the packet leaves the host. Route by first source then destination LOC: move up the source network hierarchy until you can move laterally toward the destination LOC in a permissioned manner.
LOCs dynamically mapped to each host are pushed towards a distributed registry as they change. Hosts request and temporarily cache individual mappings from the registry as needed.
Variants include:
B1a. Each host has a single, globally unique numeric ID to which the LOCs are attached. This ID is used by the layer-4 and higher protocols to keep track of communication sessions.
B1b. Each service provided by a host has a globally unique, hierarchic character-string ID to which the LOCs are attached. Clients initiating communication with that service negotiate a numeric session ID which is unique only within the scope of that service.