PARALLEL BROADCAST: A NEW ALGORITHM FOR TOPOLOGY MAINTENANCE IN COMPUTER NETWORKS

Abstract

A topology change in a network of computers is a node or,Iink crashing , or a link or node resuming operations. Topology maintenance involves keeping at each node--the correct graph of the currently operational portion of the network when the network is subject to topology changes. -Here I present a fast topology maintenance algorithm for networks with various speeds, which uses less than three time units for each broadcast by each node. The best previous algorithm required O(log D) broadcasts per node before all nodes knew the correct topology of the network, where D is the diameter of the currently operational portion of the network, whereas this algorithm requires at most five broadcasts per node, before all the nodes know the correct topology of the network.