Robustness of Class-Based Path-Vector Systems

Aaron D. Jaggard and Vijay Ramachandran

Abstract

Griffin, Jaggard, and Ramachandran introduced a framework for studying design principles for path-vector protocols, such as the Border Gateway Protocol (BGP) used for inter-domain routing in the Internet. They outlined how their framework could describe Hierarchical-BGP-like systems in which routing at a node is determined by the relationship with the next-hop node on a path (e.g., an ISP-peering relationship) and some additional scoping rules (e.g., the use of backup routes). The robustness of these class-based path-vector systems depends on the presence of a global constraint on the system, but an adequate constraint has not yet been given in general. In this paper, we give the best-known sufficient constraint that guarantees robust convergence. We show how to generate this constraint from the design specification of the path-vector system. We also give centralized and distributed algorithms to enforce this constraint, discuss applications of these algorithms, and compare them to algorithms given in previous work on path-vector protocol design.

Current Citation

A. D. Jaggard and Vijay Ramachandran. "Robustness of Class-Based Path-Vector Systems." In Proc. Int'l Conf. Network Protocols (ICNP'04), pp. 84-93, October 2004. Extended version available as Yale Univ. Tech. Rep't YALEU/DCS/TR-1296, March 2005.
 

@inproceedings{jr04,
	title = {Robustness of Class-Based Path-Vector Systems},
	author = {Aaron D.\ Jaggard and Vijay Ramachandran},
	booktitle = {Proc.\ {ICNP}'04},
	month = {October},
	year = {2004},
	publisher = {{IEEE} Press},
	pages = {84--93},
	note = {Ext.\ version available as Yale Univ.\ Tech.\ Report
		{YALEU/DCS/TR--1296}, March 2005.} }

Download
(in reverse chronological order)

Filetype	Version
(200KB)	Extended version (YALEU/DCS/TR-1296)
(148KB)	Conference version (© 2004 IEEE)
(484KB)	Slides from conference talk (extended set)