Distributed Computation for Swapping a Failing Edge

摘要

We consider the problem of computing the best swap edges of a shortest-path tree T_r rooted in r. That is, given a single link failure: if the path is not affected by the failed link, then the message will be delivered through that path; otherwise, we want to guarantee that, when the message reaches the edge (u, v) where the failure has occurred, the message will then be re-routed using the computed swap edge. There exist highly efficient serial solutions for the problem, but unfortunately because of the structures they use, there is no known (nor foreseeable) efficient distributed implementation for them. A distributed protocol exists only for finding swap edges, not necessarily optimal ones. In [6], distributed solutions to compute the swap edge that minimizes the distance from u to r have been presented. In contrast, in this paper we focus on selecting, efficiently and distributively, the best swap edge according to an objective function suggested in [13]: we choose the swap edge that minimizes the distance from u to v.