Paper Info
Title
Scalable and Efficient Multipath Routing via Redundant Trees
Abstract
Nowadays, a majority of the Internet service providers are either piloting or migrating to software-defined networking (SDN) in their networks. In an SDN architecture a central network controller has a top-down view of the network and can directly configure each of their physical switches. It opens up several fundamental unsolved challenges, such as deploying efficient multipath routing that can provide disjoint end-to-end paths, each one satisfying specific operational goals (e.g., shortest possible), without overwhelming the data plane with a prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest (node- or edge-) 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 complexity of the underlying mathematical problem is NP-complete and we present fast heuristic algorithms. 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. Finally, we show that even if a primary tree is already given it remains NP-complete to find a minimum length secondary tree concerning this primary tree.
Year
DOI
Venue
2019
10.1109/JSAC.2019.2906742
IEEE Journal on Selected Areas in Communications
Keywords
Field
DocType
Routing,Heuristic algorithms,Computational complexity,Control systems,Buildings,Tagging
Forwarding plane,Multipath routing,Heuristic,Disjoint sets,Computer science,Computer network,Routing table,Network interface controller,Computational complexity theory,Scalability
Journal
Volume
Issue
ISSN
37
5
0733-8716
Citations 
PageRank 
References 
1
0.36
0
Authors
4
Name
Order
Citations
PageRank
János Tapolcai136441.42
Gábor Rétvári219424.87
Péter Babarczi39213.47
Erika R. Bérczi-Kovács4113.94