DYNAMIC TREE DETECTION IN COMPUTER NETWORKS.

Abstract

Most distributed algorithms for computer networks, are designed to work with arbitrary graph structures. Most networks, however, can usually be decomposed into subgraphs with a specific structure. Detecting and exploiting these subgraphs can considerably reduce the storage and communication cost of the algorithm. The authors propose a distributed algorithm for detecting and exploiting tree subgraphs. In a network with fixed topology, the algorithm is optimal in terms of communication complexity. The algorithm also dynamically adapts to changes in network topology caused by link failure and recovery. The dynamic operation of the algorithm is incremental as only nodes that may be affected by the change reinitiate the algorithm. Another important property of this algorithm is that it requires no node identities or sequence numbers. It is examined how this idea can be extended to other subgraph structures.