Analysis of routing table update activity after resource failure in a distributed computer network

Abstract

In a distributed computer network each node participates in the routing process, making routing decisions based on information about network topology which is stored in tables in the node. To maintain the accuracy of these tables without interrupting the functionality of the network, they must be dynamically updated whenever there is a topology change in the network. The purpose of this paper is to analyze update activity required by a topology information maintenance scheme which has been implemented on the three-node MERIT Computer Network in Michigan. The main theorem gives upper and lower bounds on the number of update messages required after failure of a single network resource, either a node or a link.