TY - JOUR
T1 - Stable routing under the Spanning Tree Protocol
AU - Grandoni, Fabrizio
AU - Nicosia, Gaia
AU - Oriolo, Gianpaolo
AU - Sanità, Laura
PY - 2010/9
Y1 - 2010/9
N2 - The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.
AB - The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.
KW - Randomized algorithms
KW - Spanning Tree Protocol
KW - Stable routing
UR - http://www.scopus.com/inward/record.url?scp=77957911017&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2010.05.001
DO - 10.1016/j.orl.2010.05.001
M3 - Article
AN - SCOPUS:77957911017
SN - 0167-6377
VL - 38
SP - 399
EP - 404
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -