Let $G=(V,E)$ be a 2-edge connected, undirected and non-negatively weighted graph, and let $S(r)$ be a single source shortest paths tree (SPT) of $G$ rooted at $r \in 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 {\em swap edge} for $e$. Let $S_{e/e'}(r)$ be the {\em swap tree} (no longer a SPT, in general) obtained by swapping $e$ with $e'$, and let ${\cal S}_e$ be the set of all possible swap trees with respect to $e$. Let $F$ be a function defined over ${\cal 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 {\em best swap edge} for $e$ with respect to $F$ is a swap edge $f$ 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.
Swapping a Failing Edge of a Single Source Shortest Paths Tree is Good and Fast
Proietti G;
2003
Abstract
Let $G=(V,E)$ be a 2-edge connected, undirected and non-negatively weighted graph, and let $S(r)$ be a single source shortest paths tree (SPT) of $G$ rooted at $r \in 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 {\em swap edge} for $e$. Let $S_{e/e'}(r)$ be the {\em swap tree} (no longer a SPT, in general) obtained by swapping $e$ with $e'$, and let ${\cal S}_e$ be the set of all possible swap trees with respect to $e$. Let $F$ be a function defined over ${\cal 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 {\em best swap edge} for $e$ with respect to $F$ is a swap edge $f$ 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
