An idea for ID/Locator Split Based Inter-Domain Routing

  1. Problem Statement and Genesis of this idea

    There is currently a perception amongst many ISPs and others that provider independent addressing for end users is an undesirable use of resources. This perception stems from the fact that (in the current routing paradigm) each provider independent prefix requires a slot in the global default free routing table in order to be generally reachable.

    On the other hand, end users really like provider independent addressing because it allows them to freely move from one ISP to another without having to do major renumbering projects on their networks.

    This dichotomy is the pure and unfortunate result of the current routing paradigm. It turns out that what the end users care about is that their End System Identifiers (the unique address of a given end system) is portable and can be moved from one provider to another without being modified. On the other hand, what the ISPs really care about is having a way to determine the next hop route to reach a given system. This can be thought of as a routing locator.

    An unfortunate artifact of current internet design is that the End System Identifier and the Routing Locator are currently merged into a single number (32 bits in IPv4, 128 bits in IPv6).

    This paper seeks to offer an alternative routing paradigm which, while still preserving the current routing mechansim for intra-domain routing (routing within a given Autonomous system), seeks to provide an alternative routing locator mechanism which can be used in the inter-domain routing arena, especially in that portion known as the "Default Free Zone".

  2. Definitions

    In order to provide a common frame of reference in this document, this section attempts to clarify the meanings of some of the terms used.

    End System Identifier
    A 128 bit IPv6 address signifying a particular host
    Routing Locator
    A 32 bit Autonomous System Number used for looking up inter-domain routing information
    Intra-Domain Routing
    Decisions regarding the forwarding of packets entirely within a given autonomous system. A packet between two end stations will generally traverse an area of intra-domain routing, followed by several areas of inter-domain routing, followed by a final area of intra-domain routing.
    Inter-Domain Routing
    Decisions regarding the forwarding of packets which are sourced from or to be delivered to non-local autonomous systems
  3. General Concept

    Packets generally traverse a sequence of areas in the internet which consists of one or more of the following areas, usually in the following order:

    1. Local Network

      Characterized, generally, by minimal routing knowledge and a default route towards the majority of the internet.

    2. Initiating ISP

      For purposes of this discussion, this will be the point in the network where the packet will encounter its first default-free router. This area generally has at least one ASN. This ISP has a direct business relationship with the Local Network.

    3. Transit ISP(s)

      These are ISPs between the Origin ISP and the Destination ISP which transport the packet, but, have no direct business relationship with the source or destination. It is these ISPs which will achieve the greatest benefit from this proposal.

    4. Destination ISP

      This will be the area where the packet leaves the default-free zone (generally) and where under this proposal, the packet will (usually) return to normal prefix-based routing. This ISP has a direct business with the Destination Network.

    5. Destination Network

      This will be the network which contains the system which is the intended destination of the packet.

    The first and last steps are always present, although they may be the same network. Any of the other steps may or may not be present in the routing of a given packet, but, if present, are always encountered in the order presented.

    The idea here is to remove the need for specific prefix data from the portion of the internet defined above as "Transit ISP(s)" to the greatest extent possible. This is based on the following operational theories and assertions:

    1. The transit ISPs don't really care about the destination prefixes, so much as they care about the AS Path and Next Hop information needed to forward the packet on its way.
    2. The primary issue confronting these ISPs with the idea of portable Provider Independent IPv6 addresses for anyone who considers them desirable is the combination of routing table size and the anticipated rate of churn in that routing table.
    3. There will always be relatively few transit autonomous systems, compared to the number of active prefixes.
    4. The churn rate in AS-Path and Next-Hop data is less than the churn rate in full-prefix routing.
    5. The churn rate in Prefix->Origin AS mapping is relatively low, especially if it does not need to change in response to transient network changes.
    6. Separating the two churn rates above allows both to be much lower than the current churn rate, which is the product of these two rates multiplied by some additional factors.
  4. Theory of Operation

    A new IP Version number is assigned for encapsulated IDR packets.

    Capability to support this IP Version is a negotiated feature in BGP.

    When a packet destined for a foreign prefix (one which is not present in the local IGP routing table) arrives at the first router which does not have a default route, that router will perform a loookup (possibly accelerated by onboard or topologically proximate cache) to identify the best "Destination ISP" autonomous system number. If the next hop router (based on shortest ASPATH) to the "Destination ISP" ASN has negotiated appropriate capability, then:

    The header is then modified as follows:

    Subsequent routers which are aware of this mechanism would route entirely on the Destination ASN value unless the value matched the local ASN.

    At the point where a next-hop router is selected which has not negotiated this capability, the packet would be decapsulated prior to forwarding.

    Routers which are not aware of this mechanism would route based on prefix as is current practice.

    Once the packet arrives at the target AS, it will be routed via the local interior routes (by prefix) if possible. If, for some reason, a local interior route is unavailable, the target ASN will be appended to an additional transitive routing option field ("BeenThere"), and a new candidate Destination AS will be selected (one which does not apear in the "BeenThere" field). If no such candidate is available, the packet is dropped and an ICMP unreachable should be returned. If a candidate is selected, then, the packet is rerouted accordingly to the new Destination AS.

    If a packet arrives at a successful Destination AS and contains a "BeenThere" field, the contents of that "BeenThere" field should be sent back to the Encapsulating Router in a new type of ICMP message which, if seen by the encapsulating router could update its cache about the best candidate destinatin AS for future packets. This optional feature has abuse potential and would need better analysis and security prior to actual implementation.

  5. Desired End State

    Once this feature becomes ubiquitous in the core and on the border routers where these headers would be inserted, it becomes possible to remove the prefix data from the eBGP process and limit that data to AS-Path and Next-Hop alone. This will significantly reduce the amount of router memory required to hold full global reachability data and reduce churn to those events affecting locally known next hop for a given AS-Path. These events are far less frequent and have much more localized effect, generally, than the current scheme.

    The mapping data required to map a prefix to a destination ASN (or ASN Set) would only change when a given destination made a permanent (or quasi-permanent) change to their connectivity arrangements. Transient outages would not affect the map. As such, this data would also have a relatively low churn rate and could be distributed through a mechanism very similar to DNS. This mechanism could include a cryptographic signing hierarchy to enable validation of authority for all map entries.

    By labeling packets at the point where they enter the DFZ, the labeling problem becomes relatively distributed and can be scaled relatively easily. Generally, this operation would be occuring on relatively low-end routers with relatively low bandwidth and PPS rates.

  6. Transition Process

    The first step would be to design and deploy the mapping mechanism and IANA/RIR/LIR support for cryptographic signing, or, at least the framework to allow it to be implemented later.

    The next step would be to get IANA to assign routing options for the "Destination AS" and "BeenThere" routing options.

    Proof of concept router code would have to be developed for edge routers to do the labelling and for core routers to parse the labels.

    Next, deploy proof of concept code for enabling core routers to drop prefix information.

    Generate applicable RFCs documenting the proof-of-concept code and functionality. Work to move this through the standards track and encourage router vendors to implement the necessary code changes. Ideally, all required code changes could be implemented in a single release, using a per-neighbor BGP option to control whether prefixes are advertised or not, allowing the software rlease to be compatible with either style of routing.

  7. FAQ and other Notes

    One of the most common questions about this refers to traffic engineering.

    Traffic engineering essentially can be categorized into two broad groups of users. One is the multi-homed end-site attempting to balance the load across their upstream circuits while preserving redundancy. This could be accomplished by the end-site mapping preferences to the different upstream ASNs onto their prefixes in the Prefix->Destination ASN map while still having their upstreams simply maintain route(s) for their full aggregated address space. The other is the backbone ISP attempting to balance where they receive traffic. In this case, the ideal solution is for the ISP to utilize multiple ASNs and map prefixes onto the ASN representing the desired routing policy. While this will remove some of the benefit gained by reducing the IDR table down to just ASN data, it will not remove all of it. Instead of one route table entry per prefix, it will be one route table entry per routing policy (which seems somewhat inevitable). Additionally, ASNs remain 32 bits while IPv6 prefixes are four times that size.

    Path MTU Discovery is another common area of concern. The original idea for this involved simply adding routing-options to the existing IPv6 header. This presented a PMTU-D issue which I was unable to resolve cleanly. Switching to a mechanism where the IP version is changed and the header is modified as a result. This is the genesis of adding the encapsulating router ID field. Absent that need, the only required additional data would be the destination ASN.

    Isn't this like LISP or the other ID/Locator split ideas? Well, yes and no. I believe that this idea is much lighter weight on both the implementation side, and, on the invasiveness in the packet. They all end up requiring some form of map/encap, but, this proposal adds as little as possible to the header and provides V4 and V6 compatible solutions.