Pathlet Routing
We present a new routing protocol, pathlet routing, in which networks advertise fragments of paths, called pathlets, that sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly exible building block, capturing policy constraints as well as enabling an exponentially large number of path choices. In particular, we show that pathlet routing can emulate the policies of BGP, source routing, and several recent multipath proposals.
This exibility lets us address two major challenges for Internet routing: scalability and source-controlled routing. When a router's routing policy has only \local" constraints, it can be represented using a small number of pathlets, leading to very small forwarding tables and many choices of routes for senders. Crucially, pathlet routing does not impose a global requirement on what style of policy is used, but rather allows multiple styles to coexist. The protocol thus supports complex routing policies while enabling and incentivizing the adoption of policies that yield small forwarding plane state and a high degree of path choice.
| Attachment | Size |
|---|---|
| p111.pdf | 1.33 MB |
Some of these (very good)
Some of these (very good) questions are now discussed in the Pathlet Routing FAQ.
this paper is the latest in
this paper is the latest in a recent series of papers for providing
greater flexibility to end users in selecting routes. the primary concern with
bgp is that it does not allow multi-path routing even though the topology is
rich enough to permit better routers, and worse still does not provide an
interface to users to exploit this topological richness for performance and
availability.
the proposed solution, pathlet routing, presents a framework in which isps can
export "pathlets" and "vnodes" to end users and users can then "stitch"
together desired end-to-end paths using source routing. there are several
aspects of the paper that are particularly appealing.
1. first, rather than focus excessively on tweaking/hacking existing
mechanisms to ensure backward compatibility with current infrastructure, the
authors take a clean (and rather refreshing) approach of exploring the kinds of
logical abstractions needed to provide inter-domain routing flexibility.
pathlets and vnodes are the logical building blocks that serve this role. this
level of logical abstraction is both conceptually and practically appealing.
for example, it allows network operators to express policies into these logical
abstractions rather than work at the level of router configurations/ip prefixes
etc.
2. i liked the philosophy that "policy is enforced in the data plane
rather than through obscurity in the control plane"
3. given that there are several proposals to retrofit the requisite routing
flexibility, the authors try to present a systematic framework for reasoning
about the flexibility that each proposal allows. policy expressiveness is a
rather fuzzy term that we do not have a good handle on. in this respect, this
is especially important, since practitioners would like to know what a
mechanism can and cannot achieve in terms of policy expressiveness.
4. since the mechanism works using logical identifiers for the pathlets and
these have only local significance, it allows the forwarding tables at routers
to be very compact.
5. finally, pathlet routing can allow different isps to implement different
policies independently and allows multiple policy mechanisms to coexist, and
the results show that the overhead is manageable in realistic topologies.
however, there are a few issues that i felt were not addressed adequately
in the paper:
1. reading through the proposed scheme, it seemed that we are just
reinventing "label switching" in a different form. it would be really useful
if the authors could elaborate on this a bit more -- what exactly are
the key things that are different from the label switching literature?
2. at some level, we've been taught to believe that routing table size is a bad
thing and compact routing tables are necessary and prefix aggregation etc are
absolutely necessary? at the same time, from what little i know from talking to
folks who have looked at router configs, operational folks dont really seem to
care that much about bloating routing tables or bother aggregating prefixes
etc? how big a deal really is the size of the forwarding table? there seems to
be conflicting data/opinions and no real consensus on this issue and im left
wondering if small routing tables is something really we want to optimize for
or do we just want a "feasible" solution within current technology limits?
3. there are some aspects in bgp that serve as safeguards against either
accidental misconfigurations or malicious intent? would have liked to see some
discussion on the security/stability aspects of pathlet routing. does it make
things (e.g., prefix hijacking, eavesdropping) worse/better?
4. on a similar note to (3), it would also be nice to see some discussion on
how we can ensure compliance from both isps and users regarding the advertised
routes? (one might be tempted to argue that there is no such guarantee in
today's routing infrastructure anyway, and in that sense pathlet routing isnt
really making things any worse!)
5. while the motivation and definitions in section 5 are quite sound, it felt
that the actual analysis in 5.3 was somewhat disappointing. the authors set up
the definitions of "emulate" pretty rigorously, but the actual analysis itself
seemed hand-wavy. also, while i understand/appreciate the intuition behind the
fact that pathlet routing can emulate other proposals because they rely on
"tunnels" in 5.1, the intuition behind allowing policies on a virtual graph
seemed rather vague.