Swapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast

摘要

Let G = (V, E) be a 2-edge connected, undirected and nonnegatively weighted graph, and let S(r) be a single source shortest paths tree (SPT) of G rooted at r ∈ V. Whenever an edge e in S(r) fails, we are interested in reconnecting the nodes now disconnected from the root by means of a single edge e′ crossing the cut created by the removal of e. Such an edge e′ is named a swap edge for e. Let S_(e/e′) (r) be the swap tree (no longer an SPT, in general) obtained by swapping e with e′, and let S_e be the set of all possible swap trees with respect to e. Let F be a function defined over S_e that expresses some feature of a swap tree, such as the average length of a path from the root r to all the nodes below edge e, or the maximum length, or one of many others. A best swap edge for e with respect to F is a swap edge / such that F(S_(e/f (r)) is minimum. In this paper we present efficient algorithms for the problem of finding a best swap edge, for each edge e of S(r), with respect to several objectives. Our work is motivated by a scenario in which individual connections in a communication network suffer transient failures. As a consequence of an edge failure, the shortest paths to all the nodes below the failed edge might completely change, and it might be desirable to avoid an expensive switch to a new SPT, because the failure is only temporary. As an aside, what we get is not even far from a new SPT: our analysis shows that the trees obtained from the swapping have features very similar to those of the corresponding SPTs rebuilt from scratch.