TY - GEN
T1 - Distributed path computation without transient loops
T2 - 20th International Teletraffic Congress, ITC20 2007
AU - Ray, Saikat
AU - Guérin, Roch
AU - Sofia, Rute
PY - 2007
Y1 - 2007
N2 - Paths with loops, even transient ones, pose significant stability problems in networks. As a result, much effort has been devoted over the past thirty years to designing distributed algorithms capable of avoiding loops. We present a new algorithm, Distributed Path Computation with Intermediate Variables (DIV), that guarantees that no loops, transient or steady-state, can ever form. DIVs novelty is in that it is not restricted to shortest paths, can easily handle arbitrary sequences of changes and updates, and provably outperforms earlier approaches in several key metrics. In addition, when used with distance-vector style path computation algorithms, DIV also prevents counting-to-infinity; hence further improving convergence. The paper introduces DIV and its key properties. Simulation quantifying its performance gains are also presented.
AB - Paths with loops, even transient ones, pose significant stability problems in networks. As a result, much effort has been devoted over the past thirty years to designing distributed algorithms capable of avoiding loops. We present a new algorithm, Distributed Path Computation with Intermediate Variables (DIV), that guarantees that no loops, transient or steady-state, can ever form. DIVs novelty is in that it is not restricted to shortest paths, can easily handle arbitrary sequences of changes and updates, and provably outperforms earlier approaches in several key metrics. In addition, when used with distance-vector style path computation algorithms, DIV also prevents counting-to-infinity; hence further improving convergence. The paper introduces DIV and its key properties. Simulation quantifying its performance gains are also presented.
UR - https://www.scopus.com/pages/publications/38149103192
U2 - 10.1007/978-3-540-72990-7_13
DO - 10.1007/978-3-540-72990-7_13
M3 - Conference contribution
AN - SCOPUS:38149103192
SN - 9783540729891
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 104
EP - 116
BT - Managing Traffic Performance in Converged Networks - 20th International Teletraffic Congress, ITC20 2007, Proceedings
PB - Springer Verlag
Y2 - 17 June 2007 through 21 June 2007
ER -