Title: Pathlet Routing
Speaker: Brighten Godfrey, University of California -- Berkeley
Date: Thursday, April 9, 2009 10:30-11:30am
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Host: Rebecca Wright, DIMACS Deputy Director
Abstract:
One of the major challenges of Internet routing is scalability; routers require a fast-path forwarding table entry for every IP prefix announced in the Internet. A second major challenge is providing multiple paths: using only a single route to each destination leads to unreliability and suboptimal path quality.
We address those two problems in a new protocol, pathlet routing, in which networks advertise fragments of paths (pathlets) which sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly flexible 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 flexibility allows pathlet routing to address the two key challenges of scalability and multiple paths. 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. A somewhat surprising consequence of our architecture is that routers that use local policies obtain the immediate benefit of small forwarding tables, regardless of what the other routers choose. Pathlet routing 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.
This is joint work with Igor Ganichev, Scott Shenker, and Ion Stoica.