Stable routing under the Spanning Tree Protocol

Fabrizio Grandoni; Gaia Nicosia; Gianpaolo Oriolo; Laura Sanità

doi:10.1016/j.orl.2010.05.001

Stable routing under the Spanning Tree Protocol

Fabrizio Grandoni
, Gaia Nicosia
, Gianpaolo Oriolo
, Laura Sanità

Discrete Mathematics

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

4 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	399-404
Aantal pagina's	6
Tijdschrift	Operations Research Letters
Volume	38
Nummer van het tijdschrift	5
DOI's	https://doi.org/10.1016/j.orl.2010.05.001
Status	Gepubliceerd - sep. 2010

Financiering

The author Laura Sanità was supported by Swiss National Science Foundation within the project “Robust Network Design”. The authors wish to thank the industrial partners Paola Iovanna, Giorgio Lembo and Fabio Palozza, for introducing them to the problem. They also thank Carlo Mannino, Nicolai Hähnle and Ezio Sperduto for useful discussions. Finally special thanks are due to Martin Skutella, for sparking the idea of a randomized approach.

Toegang tot document

10.1016/j.orl.2010.05.001

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@article{c48f6eed6f1b4480a623afaaa26337c2,

title = "Stable routing under the Spanning Tree Protocol",

abstract = "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.",

keywords = "Randomized algorithms, Spanning Tree Protocol, Stable routing",

author = "Fabrizio Grandoni and Gaia Nicosia and Gianpaolo Oriolo and Laura Sanit{\`a}",

year = "2010",

month = sep,

doi = "10.1016/j.orl.2010.05.001",

language = "English",

volume = "38",

pages = "399--404",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

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 - https://www.scopus.com/pages/publications/77957911017

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 -

Stable routing under the Spanning Tree Protocol

Samenvatting

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit