A Fast Topology Maintenance Algorithm For High-Bandwidth Networks

Informally, a topology change in a network of computers is a link or computer crashing, or link or computer resuming operations. Topology maintenance is the problem of keeping at each computer a correct graph of the currently operational portion of the network when the network is subject to topology changes. We present the fastest time-driven algorithm that we know of for topology maintenance in high-speed networks. Our algorithm uses only four time units for each broadcast by each computer. The best previous algorithm required O(log m) time units for each broadcast by each computer, where m is the number of currently operational computers in the network. In addition to its speed, our algorithm makes several significant contributions. First, Cidon et al. have shown that O(log m) time units are necessary for time-driven topology maintenance algorithms of high-speed networks that do not allow a packet to traverse the same edge in both directions. Our algorithm shows that this lower bound does not hold for networks that do allow a packet to traverse the same edge in both directions. Second, the O(log m) algorithm assumed that it takes each computer at most one time unit to simultaneously broadcast messages to all neighbors of the computer. In contrast, a node in our algorithm can send at most one message per time unit. As in the O(log m) algorithm, our algorithm requires O(D) broadcasts per node before all nodes know the correct topology of the network, where D is the diameter of the currently operational portion of the network.