Abstract:

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