Stabilization of Maximal-Metric Routing without Knowledge of Network Size

摘要

We present a protocol for maintaining a spanning tree that is maximal with respect to any given (bounded and monotonic) routing metric. This protocol has two interesting adaptive properties. First, the protocol is stabilizing: starting from any state, the protocol stabilizes to a state where a maximal tree is present. Second, contrary to other approaches, the protocol converges in O(L * deg) time, where deg is the node degree in the network and L the longest network path. This is achieved without nodes assuming an upper bound on L.