Foundations of Inter-Domain Routing

Vijay Ramachandran (Ph.D. thesis)

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 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.
This dissertation develops a theoretical framework for the design and analysis of path-vector protocols, like BGP, used for inter-domain routing. It presents the path-vector policy system (PVPS), which is an abstract representation of the fundamental components of an inter-domain routing protocol. The 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. Applications of these design principles are explored, 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.

Citation of Most Recent Version

V. Ramachandran. Foundations of Inter-Domain Routing. Ph.D. dissertation, Yale University, December 2005.

@phdthesis{vijayr-thesis,
	title = {Foundations of Inter-Domain Routing},
	author = {Vijay Ramachandran},
	year = {2005},
	month = {December},
	school = {Yale University} }

Download
(in reverse chronological order)

Filetype	Version
(712K)	Final submitted version (December 2005).
(536K)	Slides from thesis defense (April 2005).