Scalable and Efficient Multipath Routing: Complexity and Algorithms
Scalable and Efficient Multipath Routing: Complexity and Algorithms
复制标题
DOI：
10.1109/icnp.2015.44
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
János Tapolcai;G. Rétvári;P. Babarczi;Erika R. Kovács;Panna Kristof;G. Enyedi
中科院分区：
文献类型：
--
作者：
János Tapolcai;G. Rétvári;P. Babarczi;Erika R. Kovács;Panna Kristof;G. Enyedi
多路径路由中一个基本的未解决的挑战是提供不相交的端到端路径，每个路径都满足某些操作目标（例如，最短的可能），而不会使数据平面被禁止数量的转发状态压倒。在本文中，我们研究的问题，找到一对最短的不相交的路径，可以表示只有两个转发表条目每个目的地。在最小长度冗余树的先前工作的基础上，我们表明，基本的数学问题是NP-完全的，我们提出了启发式算法，提高了已知的复杂性范围从立方到一个单一的最短路径搜索的顺序。最后，通过大量的模拟，我们发现，这是可能的，非常接近达到绝对最佳的路径长度与我们的算法（差距只有1-5%），最终打开大门，大规模的多路径路由部署。
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.