Pathlet Routing

Pathlet routing is a new Internet routing architecture designed for flexibility. In a nutshell, the architecture is source routing over a virtual topology.   By representing the Internet as a virtual topology independent of the physical topology, network owners can declare services and policy constraints very expressively. By allowing users to select any path within this virtual topology, users can select routes that are appropriate to the application or more efficient and can react quickly to dynamics in the network.

In more detail, pathlet routing uses two simple yet powerful building blocks. A vnode is a virtual node that represents arbitrary granularities, such as an entire autonomous system (AS), a geographical region, or a class of policies. A pathlet is a fragment of a path: a sequence of vnodes along which the originating AS is willing to route. Route computation is shifted to the edges: senders concatenate their selection of pathlets into an end-to-end source route represented as a list of identifiers in the packet header.

Examples of pathlet routing's flexible routing policies include the following:

  • Pathlet routing can emulate any routing policy supported by a number of other protocols: BGP, loose and strict source routing, and recent multipath proposals LISP, MIRO, and NIRA.
  • Routing policies that are "local", in that they are a function only of the ingress and egress points in a network, can be represented using very small forwarding tables and lead to many choices of routes for senders—potentially an exponentially large number of path choices.
  • Crucially, pathlet routing does not impose a global requirement on what style of policy is used, but rather allows multiple radically different styles to coexist. For example, one part of the Internet could use permissive policies that allow senders to choose any route while another part could use traditional restrictive BGP-style policies.






Additional documents

  • Solving the AS partitioning problem with Pathlet Routing. Interdomain routing scales because it aggregates routing information. But aggregation can also cause pathological conditions; for example, if an AS partitions internally, then the two halves cannot reach each other even if the Internet is still physically connected. In pathlet routing, there's a clean solution to this problem, taking advantage of the flexible granularity of representing the topology with vnodes.
  • Constructing VPNs in pathlet routing. Describes how virtual private networks can be constructed in pathlet routing. Since pathlet routing effectively routes on a virtual topology to begin with, the construction is quite easy, and in fact it's easy to set up much more sophisticated examples than the one presented here. This document also discusses the design decision of having a single ingress vnode per neighbor, and its equivalence to a multiple-ingress design.


Who selects routes in pathlet routing?

    Pathlet routing allows a spectrum of possible policies which can give control over routes to the network, as well as to the edges (end-hosts or routers acting on their behalf).

    First, autonomous systems (ASes) on the Internet collectively create a virtual topology (of vnodes and pathlets) defining how the network can be used. The virtual topology can take many forms; indeed, this is the flexibility that is pathlet routing's strength. At one extreme, networks may choose to construct one pathlet to every destination, thus effectively performing all the route selection, as in today's Internet.

    At the other extreme, networks may construct pathlets that can be stitched together in exponentially many ways by senders. A "sender" may be the source end-host or a router in the source's domain acting on its behalf. The choice of which entity chooses the routes is outside the scope of the pathlet routing protocol, and likely would vary depending on the end-host's resource constraints (server vs. laptop vs. cell phone).

Is pathlet routing similar to MPLS / label swapping?

    The key idea of pathlet routing is to perform interdomain routing over a virtual topology and allow source routing within that virtual topology. We haven't seen this idea articulated elsewhere, including MPLS.

    In terms of high-level motivation, MPLS and pathlet routing share the goal of building a flexible data plane, though in different contexts (intra- and inter-domain, respectively). In terms of the mechanics of forwarding packets, pathlet routing's popping and (optional) pushing of FIDs is essentially equivalent to popping/pushing (i.e., swapping) labels. But MPLS lacks vnodes, the utility of which we've demonstrated in the paper, e.g., for representing valley-free routes. Pathlet routing contributes the concept of routing over a virtual topology, a viable interdomain control plane, and interdomain use cases such as local transit policies and mixed policies.

Packet forwarding involves changing the header size. Isn't that inconvenient?

    Forwarding a packet as described in the paper does involve popping a pathlet forwarding identifier (FID) and potentially pushing other FIDs onto the header.

    The simplest response is that routers already have the capability to push and pop labels for MPLS, thus running into the same issues, so similar operations for pathlet routing are likely to be feasible.

    But if changing the packet length were problematic, this could be avoided in the protocol, as follows. Note that there are two operations described in the paper which change the length of the packet: popping a FID, and pushing FIDs. We can eliminate each of these cases:

    1. Popping the first FID (shortening the packet). To eliminate this operation, we can add to the packet a "pointer" field which stores the location of the next FID to be processed. Now the router just needs to increase the pointer value to point to the next FID.
    2. Pushing the remaining FIDs (lengthening the packet). To eliminate this operation, the basic idea is to change the FID so that it includes everything that would have been pushed onto the packet. Specifically, suppose originally the pathlet's FID is f, and the pathlet has remaining FIDs r1,...,rk. In the protocol described in the paper, f would be popped and r1,...,rk would be pushed. Instead, we can redefine the pathlet's FID to be f,r1,...,rk. The result is that the source puts f,r1,...,rk in the packet rather than just f, and the router just pops f rather than popping f and pushing r1,...,rk. A possible disadvantage of this approach is that the packet headers are somewhat larger, but it does ensure that the packet header size remains constant. Note also that this approach for eliminating the push operation (1) does not require a modification to the pathlet routing protocol, and therefore (2) each router can decide for itself whether it wants to use this approach.

Pathlet routing can reduce the size of the forwarding table (FIB), but is that really important?

    Most likely, the scalability benefits are not as important as the benefits of flexible policies and choice for senders (improving reliability, path quality, throughput, etc.). The current and near-term future Internet appear to be within the limits of router scalability. However, the dramatic asymptotic reduction in FIB size enabled by pathlet routing may provide (1) insurance against future increase in FIB size due to unforeseen or unpredictable reasons like more widespread deployment of IPv6 or VPNs; and (2) a simpler forwarding architecture that may reduce costs.

    Also note that pathlet routing enables but doesn't enforce small FIBs. The size of a router's FIB is the number of pathlets that begin at the router's vnodes. One way of using pathlet routing is to emulate BGP, in which case the FIBs are the same size as they are today. Another way is to use the "Local Transit" (LT) policies described in our paper. LT policies provide: (1) a large amount of choice in routes for senders, and (2) can be expressed with very small FIBs: on the order of the number of AS-level neighbors, rather than the number of destinations in the Internet.

To emulate MIRO and NIRA, you have to modify the protocol. Isn't that a hack?

    The key point is that emulating these protocols requires no changes to the data plane. (The data plane is what we analyzed in Section 5 of the paper.) The control plane would need some changes. But we expect that there are many different ways of disseminating pathlets (our protocol in the paper, DNS-style as in NIRA, etc.), and these could even be used simultaneously by different parts of the Internet. We therefore consider the data plane to be the more critical fixed foundation of the architecture.

How is it possible to scale source routing, in terms of the state and messaging necessary to dynamically distribute the entire Internet topology?

    "Local Transit" (LT) policies, described in our paper, are one possible way of using pathlet routing. They effectively result in the entire (policy-aware) AS-level Internet topology being distributed globally.

    Although distributing an entire map of the Internet may seem daunting, it's actually about as much state as BGP today already requires. Moreover, in our paper, we show that our pathlet dissemination algorithm is efficient enough that state and messaging is not too much greater than BGP in Internet-like topologies.

    Additionally, there are several ways to limit dynamics:

    • Physical topology failures or recoveries do not have to be exposed to pathlet routing's virtual topology, since ASes should be able to reroute pathlets internally.
    • Since pathlet routing enables multipath, it is possible to delay routing updates (pathlet announce/withdraw) since sources can simply switch to using an alternate paths when they discover a failed pathlet. In the extreme case of LT policies, every policy-compliant path is exposed to sources, so the control plane would never be necessary for transient failure notification.