Abstract | ||
---|---|---|
Protocols belonging to the Spanning Tree Protocol (STP) route traffic demands on tree topologies that are evaluated through shortest path procedures. In this paper we deal with the problem of assigning costs to the arcs of a network in order to guarantee that SPT protocols efficiently re-route traffic demands in failure situations: namely, without redirecting traffic demands that are not affected by the failure. We say that a communication network has the local tree-restoration property if there exists a set of costs for its arcs such that the above property holds.We show that an undirected network has the local tree-restoration property if and only if it is 2-connected. In particular, we provide a quite simple procedure for assigning costs to the arcs of a 2-connected network so that the property holds. For the directed case, we show that deciding whether a network has the local tree-restoration property is NP-hard, even in some "simple" cases. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-642-04576-9_9 | Traffic Management and Traffic Engineering for the Future Internet |
Keywords | Field | DocType |
route traffic demand,undirected network,local tree-restoration property,failure situation,re-route traffic demand,simple procedure,local restoration,2-connected network,redirecting traffic demand,assigning cost,communication network,shortest path,spanning tree protocol | Telecommunications network,Shortest path problem,Existential quantification,Computer network,Network topology,If and only if,Mathematics,Spanning Tree Protocol,Distributed computing | Conference |
Volume | ISSN | Citations |
5464 | 0302-9743 | 2 |
PageRank | References | Authors |
0.44 | 7 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paola Iovanna | 1 | 92 | 13.40 |
Gaia Nicosia | 2 | 143 | 25.16 |
Gianpaolo Oriolo | 3 | 205 | 15.06 |
Laura Sanità | 4 | 257 | 18.36 |
Ezio Sperduto | 5 | 2 | 0.44 |