Interdomain Routing: Stability, Security and Selfishness

The Border Gateway Protocol (BGP) establishes routes between the many independently-administered networks that make up the Internet. Over the past two decades there has been exponential growth in the scale and complexity of the Internet. However, BGP has not changed significantly in comparison and, consequently, does not always cope well with modern-day challenges (bounded computational resources, economically driven manipulations, security attacks, and more). Understanding, "fixing" and redesigning interdomain routing necessitates taking a principled approach that bridges theory and systems research, and breaks traditional disciplinary barriers. I shall present conceptual frameworks for addressing today's challenges and novel routing schemes that improve on the existing ones. Specifically, I shall present (1) a necessary condition for BGP safety, i.e., guaranteed BGP convergence to a "stable" routing outcome; (2) an economic approach to BGP security; and (3) Neighbor-Specific BGP -- a modest extension to BGP that allows network administrators more expressive routing policies while improving global network stability. I shall also discuss the surprising implications of these results for other areas of research: distributed computing, game theory and mechanism design. Finally, I shall outline interesting directions for future work.