Subtle design issues in the implementation of distributed, dynamic routing algorithms

Abstract

The design of distributed, dynamic routing procedures is highly complex, due to the fact that it relies on cooperation among a number of independent processors located at the nodes of communication networks and the fact that a network may face arbitrary topological changes. As a result, many simple, intuitive, concepts that seem, at first glance, that they should result in correct algorithms do not work. This paper evaluates this theme by exploring a number of examples of this phenomenon. The conclusion is that one must be careful both in the overall design of a distributed algorithm, and in its detailed implementation. This also illustrates the importance of careful formal validation of such protocols, rather than informal, intuitive arguments. © 1986.