Relating Two Formal Models of Path-Vector Routing

Aaron D. Jaggard and Vijay Ramachandran

Abstract

This paper unifies two independently developed formalisms for path-vector routing protocols such as the Border Gateway Protocol (BGP), the standard inter-domain routing protocol for the Internet. Sobrinho and Griffin, Jaggard, and Ramachandran proved conditions for guaranteed protocol convergence, but as these works operate at different levels of abstraction in modeling the protocols, the relationship between them is not obvious. Here we provide a rigorous translation between these two frameworks and use it to connect the convergence results, yielding a more complete set of analysis tools than in either framework alone. We motivate our discussion by presenting an example of applying both frameworks to analyze a set of protocols; in doing so, we show how the models, in conjunction, give important guidelines for protocol design.

Current Citation

A. D. Jaggard and V. Ramachandran. "Relating Two Formal Models of Path-Vector Routing." In IEEE INFOCOM 2005, vol. 1, pp. 619-630, March 2005.
 

@inproceedings{jr05,
	title = {Relating Two Formal Models of Path-Vector Routing},
	author = {Aaron D.\ Jaggard and Vijay Ramachandran},
	booktitle = {Proc.\ {IEEE INFOCOM} 2005},
	month = {March},
	year = {2005},
	publisher = {{IEEE} Press},
	pages = {619--630},
	volume = {1} }

Download
(in reverse chronological order)

Filetype	Version
(164KB)	Conference (final) version
(288KB)	Slides from conference talk
(160KB)	Preliminary version, YALEU/DCS/TR-1301 (July 2004)