A protocol to maintain a minimum spanning tree in a dynamic topology

摘要

We present a distributed protocol for updating and maintaining a minimum-weight spanning tree (MST) in a network with changing topology. The protocol can respond to multiple linkode failures and recoveries that can occur at arbitrary times. Given that an arbitrary finite number of topological changes occur during a period, the protocol finds the MST corresponding to the latest network, within finite time after the last change. The message complexity of the protocol is O(m|E|+k|V|) when k link recoveries and m link failures occur, where |V| and |E| are the total number of nodes and links, respectively.