Stabilizing Internet Routing: or, A Story of Heterogeneity

Add to your list(s) Download to your calendar using vCal

• Brighten Godfrey (UC Berkeley)
• Thursday 20 March 2008, 16:30-17:30
• Lecture Theatre 2, Computer Laboratory, William Gates Builiding.

If you have a question about this talk, please contact Eiko Yoneki.

A significant cause of the unreliability of end-to-end communications on the Internet is route instability: dynamic changes in routers’ selected paths. Instability is becoming even more problematic due to the increasing prevalence of real-time applications and concerns about the scalability of the Internet routing architecture. Yet Route Flap Damping, the main mechanism for combating instability, has introduced unexpected pathologies and reduced availability.

This talk describes a more principled approach to stabilizing Internet routing. First, we characterize the design space by identifying general approaches to achieve stability, and giving theoretical bounds on optimal strategies within each approach. Second, I will describe Stable Route Selection (StaRS), a new mechanism which uses flexibility in route selection to improve stability without sacrificing availability. Simulation and experimental results show that StaRS improves stability and end-to- end reliability while deviating only slightly from preferred routes, and closely approaching our theoretical lower bound. These results indicate that StaRS is a promising, easily deployable way to safely stabilize Internet routing.

StaRS’s stability improvements are enabled by dramatic heterogeneity in route failure patterns. Time permitting, I will present the case that StaRS is an instance of a much more general principle: that heterogeneity— variation in reliability, processing speed, bandwidth, or other metrics— should quite often be viewed as an advantage. This thesis is supported by practical and theoretical results in a variety of settings including distributed hash tables, overlay multicast, and job scheduling.

Bio: Brighten Godfrey’s research concerns distributed and networked systems, including Internet routing architecture, distributed algorithms, analysis of networks, peer-to-peer systems and overlay networks. He is presently a Ph.D. candidate advised by Ion Stoica at UC Berkeley.

This talk is part of the Computer Laboratory Systems Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• CL's SRG seminar
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Systems Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Lecture Theatre 2, Computer Laboratory, William Gates Builiding
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.