REAL

Scalable and Efficient Multipath Routing: Complexity and Algorithms

Tapolcai, János and Rétvári, Gábor and Babarczi, Péter and Bérczi-Kovács, Erika and Kristóf, Panna and Enyedi, Gábor (2016) Scalable and Efficient Multipath Routing: Complexity and Algorithms. In: 23rd IEEE International Conference on Network Protocols (ICNP), 2015 Nov 10-13, San Francisco, USA.

[img]
Preview
Text
[C17] ICNP 2015.pdf

Download (376kB) | Preview

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.

Item Type: Conference or Workshop Item (Paper)
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr Péter Babarczi
Date Deposited: 17 Sep 2015 17:42
Last Modified: 31 Dec 2017 00:15
URI: http://real.mtak.hu/id/eprint/26862

Actions (login required)

Edit Item Edit Item