Accession Number:

ADA461211

Title:

Relating Two Formal Models of Path-Vector Routing

Descriptive Note:

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Report Date:

2004-07-01

Pagination or Media Count:

14.0

Abstract:

This paper unifies two independently developed formalisms for path-vector routing protocols such as the Border Gateway Protocol BGP, the standard interdomain routing protocol for the Internet. The works of Griffin, Jaggard, and Ramachandran 4 and Sobrinho 8 proved conditions for guaranteed protocol convergence, but as they operate at different levels of abstraction in modeling the protocols, the relationship between them is not obvious. Here we provide a rigorous translation between the two frameworks and use it to connect the convergence results, yielding a more complete set of analysis tools than in either paper 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.

Subject Categories:

  • Linguistics
  • Numerical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE