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:
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:
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: