DIMACS TR: 2008-06

The Impact of Communication Models on Routing-Algorithm Convergence

Authors: Aaron D. Jaggard, Vijay Ramachandran and Rebecca N. Wright


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