DIMACS TR: 2008-06
The Impact of Communication Models on Routing-Algorithm Convergence
Authors: Aaron D. Jaggard, Vijay Ramachandran and Rebecca N. Wright
ABSTRACT
Distributed autonomous routing algorithms such as BGP, AODV, and
others are intended to reach a consistent, global solution after nodes
iteratively and independently collect, process, and share information.
However, the important role of the mechanism used to share
information has generally 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 formally 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
then analyze how the algorithm convergence properties of different
models in our taxonomy are related.
We show that algorithm convergence depends on the communication model
in nontrivial ways. For some pairs of models, any execution of the
routing algorithm in one model can be realized as an execution of the
same algorithm in the other models. Conversely, we show by example
that some of the possible executions in some models cannot be realized
in other models; importantly, there are network instances for which
the algorithm always converges in one model but need not converge in
another model. Here we give an extensive description of these types
of relationships among the models in our taxonomy. These results are
important for studying the convergence of distributed autonomous
routing protocols because certain communication models are best for
proving model-independent conditions that guarantee convergence, while
other models are best for proving model-independent conditions that
might permit nonconvergence.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-06.pdf
DIMACS Home Page