[talks] Yi Wang preFPO

Melissa Lawson mml at CS.Princeton.EDU
Wed Nov 26 13:58:44 EST 2008

Yi Wang will present his preFPO on Wednesday December 3 at 1:30 PM in Room 401.  The 
members of his committee are: Jennifer Rexford, advisor; Michael Freedman and Kobus van 
der Merwe (AT&T), readers; Larry Peterson and Ed Felten, nonreaders.  Everyone is invited
attend his talk.  His abstract follows below.

A Principled Approach to Managing Routing in Large ISP Networks

Today's Internet Service Providers (ISPs) face a number of challenges in introducing
changes to their networks at different frequencies. Firstly and most frequently, ISPs need
to perform daily planned maintenance to keep their networks running healthily. However,
despite of the importance and frequency of the planned maintenance operation, there is no
existing method that can handle such operations without causing packet losses and routing
protocol re-convergence. Secondly, once in a while, ISPs have to adjust their routing
policies to meet changing needs and make flexible trade-offs between different policy
objectives (such as business relationships, performance, security, etc.). However, today's
network architecture forces administrators to realize network- wide routing policies
through router-level configurations and makes it very difficult (if not impossible) to
make flexible trade-offs. Thirdly, ISPs also have the incentive to make a one-time change
(transition) from the current restrictive route-selection model, in which each router
selects a single best route for all neighbors, to a neighbor- specific route-selection
model, in which each router can provide value-added customized route- selection services
to different neighbors. However, it is currently unknown if such transition to a more
flexible route-selection model may cause the Internet routing to oscillate.

In this thesis, we take a principled approach to solving these "change-related" challenges
and propose three abstractions that guide the design and implementation of our system
solutions. First, we propose the abstraction of a "neighbor-specific route selection
problem" and a corresponding "Neighbor-Specific BGP" (NS- BGP) model that capture the
requirement of customized route selection for different neighbors. We prove that the
Internet is guaranteed to remain stable even if individual ISPs make transition to this
more flexible route-selection model incrementally.  Second, we propose the abstraction of
"policy configuration as a decision problem of reconciling multiple objectives". Guided by
this abstraction and the Analytic Hierarchy Process, a decision-theoretic technique for
balancing conflicting objectives, we designed and implemented a prototype of an extensible
routing control platform
(Morpheus) that enables an ISP to select routes for different neighbors individually and
make flexible trade-offs among policy objectives through a simple and intuitive
configuration interface. Finally, we propose the abstraction of the separation between
"physical" and "logical" configurations of routers, which leads us to the design and
prototype implementation of "virtual router migration" (VROOM), a new, generic technique
to simplify/enable a broad range of tasks that require the network to adapt in certain
ways, from planned maintenance to reducing power consumption. Collectively, the
contributions of the thesis provide simple and effective solutions for an ISP to
autonomously introduce changes to its network at various frequencies without sacrificing
global routing stability.

More information about the talks mailing list