Computer Science

Colloquium Details

Foundations of Inter-Domain Routing

Abstract

Inter-domain routing protocols establish best-effort connectivity between the independently administered networks that form the Internet. Because of the scale, heterogeneity, and autonomy of the Internet, inter-domain routes are computed using many complex routing policies provided locally at each network with little global coordination. The interaction of these local policies has been shown to produce global routing anomalies, e.g., protocol oscillations and nondeterministic routing. Understanding the interaction of local policies is essential in improving Internet stability. Unfortunately, the current inter-domain routing protocol for the Internet, the Border Gateway Protocol (BGP), allows wide latitude in configuring local policies and has evolved without formal guarantees regarding its behavior.

My work develops a theoretical framework for the design and analysis of path-vector protocols, like BGP, used for inter-domain routing. I will present the path-vector policy system (PVPS), which is an abstract representation of the fundamental components of an inter-domain routing protocol. The PVPS framework includes an explicit notion of policy languages and global assumptions made about the network; it is shown that, while local constraints on policies alone can prevent routing anomalies, implementation of these constraints infringes on other desirable protocol properties. Thus, any design guaranteeing a reasonable combination of protocol properties requires a nontrivial global constraint on the network. I will explore applications of these design principles, including several constraint-enforcement mechanisms. Unlike many previous models of inter-domain routing, the PVPS framework can be extended to include the complexities of combining inter-domain and intra-domain routing and to include policies that cannot be described as a linear preference ordering on paths.

Biography

Vijay Ramachandran just completed his graduate study in Computer Science at Yale University under the guidance of his advisor, Joan Feigenbaum. His area of interest in Internet Algorithmics, in particular, using formal models to better characterize and prove properties about Internet-scale computing tasks. Most recently he has worked on a theoretical framework to model path-vector protocols, used primarily for inter-domain routing. Vijay graduated from Princeton University in 2000 with an A.B. in Mathematics. He was a 2000-01 Connecticut InfoTech Scholar and a 2001-04 Department of Defense NDSEG Fellow.