Title | ||
---|---|---|
On the Representability of Arbitrary Path Sets as Shortest Paths: Theory, Algorithms, and Complexity |
Abstract | ||
---|---|---|
The question, whether an optional set of routes can be represented as shortest paths, and if yes, then how, has been a rather
scarcely investigated problem up until now. In turn, an algorithm that, given an arbitrary set of traffic engineered paths,
can efficiently compute OSPF link weights as to map the given paths to shortest paths may be of huge importance in today’s
IP networks, which still rely on legacy shortest-path-first routing protocols. This article establishes the fundamental theory
and algorithms of shortest path representability, and concludes that in general it is much more difficult task to compute
shortest path representable paths than to actually calculate link weights for such paths.
|
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/978-3-540-24693-0_97 | Networking |
Keywords | Field | DocType |
ospf,traffic engineering,linear programming,routing,linear program,shortest path,routing protocol | Open Shortest Path First,Any-angle path planning,Shortest path problem,Computer science,Constrained Shortest Path First,Algorithm,Theoretical computer science,Floyd–Warshall algorithm,Yen's algorithm,Shortest Path Faster Algorithm,K shortest path routing,Distributed computing | Conference |
Citations | PageRank | References |
8 | 0.64 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gábor Rétvári | 1 | 194 | 24.87 |
Róbert Szabó | 2 | 116 | 16.29 |
József Bíró | 3 | 89 | 18.01 |