The impact of communication models on routing-algorithm convergence

Aaron D. Jaggard, Vijay Ramachandran, Rebecca N. Wright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Autonomous routing algorithms, such as BGP, are intended to reach a globally consistent set of routes after nodes iteratively and independently collect, process, and share network information. Generally, the important role of the mechanism used to share information has been overlooked in previous analyses of these algorithms. In this paper, we explicitly study how the network-communication model affects algorithm convergence. To do this, we consider a variety of factors, including channel reliability, how much information is processed from channels, and how many channels are processed simultaneously. Using these factors, we define a taxonomy of communication models and identify particular models of interest, including those used in previous theoretical work, those that most closely model real-world implementations of BGP, and those of potential interest for the design of future routing algorithms. We characterize an extensive set of relationships among models in our taxonomy and show that convergence depends on the communication model in nontrivial ways. These results highlight that certain models are best for proving conditions that guarantee convergence, while other models are best for characterizing conditions that might permit nonconvergence.

Original languageEnglish (US)
Title of host publication2009 29th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS, 09
Pages58-67
Number of pages10
DOIs
StatePublished - 2009
Event2009 29th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS, 09 - Montreal, QC, Canada
Duration: Jun 22 2009Jun 26 2009

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other2009 29th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS, 09
Country/TerritoryCanada
CityMontreal, QC
Period6/22/096/26/09

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'The impact of communication models on routing-algorithm convergence'. Together they form a unique fingerprint.

Cite this