Relating Two Formal Models of Path-Vector Routing

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 2004
Accession Number
ADA461211

Entities

People

  • Aaron D. Jaggard
  • Vijay Ramachandran

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Commerce
  • Computer Networks
  • Computer Science
  • Construction
  • Convergence
  • Department Of Defense
  • Dynamics
  • Graph Theory
  • Internet Routing
  • Language
  • Network Computing
  • Network Protocols
  • Notation
  • Routing
  • Routing Protocols
  • Specifications

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Mathematical Modeling and Probability Theory.