.png){kind=icon}
.png){kind=icon}
Return
Scalable and Efficient Multipath Routing via Redundant Trees
.png){kind=icon}
PRE
AI
DOI：10.1109/JSAC.2019.2906742.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Redundant trees
independent spanning trees
not-all-equal 3SAT
minimum length disjoint paths
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
17.2
Papers:
6.4K
Citations:
3.1W