Name
Abstract | ||
|---|---|---|
A fundamental unsolved challenge in multipath routing is to provide disjoint end-to-end paths, each one satisfying certain operational goals (e.g., shortest possible), without overwhelming the data plane with prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the underlying mathematical problem is NP-complete and we present heuristic algorithms that improve the known complexity bounds from cubic to the order of a single shortest path search. Finally, by extensive simulations we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1 -- 5%), eventually opening the door for wide-scale multipath routing deployments. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/ICNP.2015.44 | 2015 IEEE 23rd International Conference on Network Protocols (ICNP) |
Keywords | Field | DocType |
protection routing,redundant trees,independent spanning trees,not-all-equal 3SAT,minimal path length | Equal-cost multi-path routing,Multipath routing,Link-state routing protocol,Computer science,Static routing,Constrained Shortest Path First,Algorithm,Theoretical computer science,Private Network-to-Network Interface,Routing table,K shortest path routing,Distributed computing | Conference |
ISSN | Citations | PageRank |
1092-1648 | 2 | 0.38 |
References | Authors | |
26 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Tapolcai | 1 | 364 | 41.42 |
| Gábor Rétvári | 2 | 194 | 24.87 |
| Péter Babarczi | 3 | 92 | 13.47 |
| Erika R. Bérczi-Kovács | 4 | 11 | 3.94 |
| Panna Kristof | 5 | 2 | 0.38 |
| Gábor Enyedi | 6 | 52 | 4.45 |